Rollup merge of #67258 - Centril:open-ended-ranges, r=oli-obk

Introduce `X..`, `..X`, and `..=X` range patterns

Tracking issue: https://github.com/rust-lang/rust/issues/67264
Feature gate: `#![feature(half_open_range_patterns)]`

---------------------------

In this PR, we introduce range-from (`X..`), range-to (`..X`), and range-to-inclusive (`..=X`) patterns.
These correspond to the `RangeFrom`, `RangeTo`, and `RangeToInclusive` expression forms introduced with the same syntaxes. The correspondence is both syntactic and semantic (in the sense that e.g. a `X..` pattern matching on a scrutinee `s` holds exactly when `(X..).contains(&s)` holds).

---------------------------

Noteworthy:

- The compiler complexity added with this PR is around 10 lines (discounting new tests, which account for the large PR size).

- `...X` is accepted syntactically with the same meaning as `..=X`. This is done primarily to simplify and unify the implementation & spec. If-and-when we decide to make `X...Y` a hard error on a new edition, we can do the same for `...X` patterns as well.

- `X...` and `X..=` is rejected syntactically just like it is for the expression equivalents. We should perhaps make these into semantic restrictions (cc @petrochenkov).

- In HAIR, these half-open ranges are represented by inserting the max/min values for the approprate types. That is, `X..` where `X: u8` would become `X..=u8::MAX` in HAIR (note the `..=` since `RangeFrom` includes the end).

- Exhaustive integer / char matching does not (yet) allow for e.g. exhaustive matching on `0usize..` or `..5usize | 5..` (same idea for `isize`). This would be a substantially more invasive change, and could be added in some other PR.

- The issues with slice pattern syntax has been resolved as we decided to use `..` to mean a "rest-pattern" and `[xs @ ..]` to bind the rest to a name in a slice pattern.

- Like with https://github.com/rust-lang/rust/pull/35712, which provided `X..Y` range patterns, this is not yet backed up by an RFC. I'm providing this experimental implementation now to have something concrete to discuss. I would be happy to provide an RFC for this PR as well as for #35712 to finalize and confirm the ideas with the larger community.

Closes https://github.com/rust-lang/rfcs/issues/947.

---------------------------

r? @varkor cc @matthewjasper @oli-obk

I would recommend reviewing this (in particular HAIR-lowering and pattern parsing changes) with whitespace changes ignored.

1 files changed, 73 insertions, 22 deletions

diff --git a/src/librustc/ty/util.rs b/src/librustc/ty/util.rs
index ddff8258c6d..8d22ac9dbbe 100644
--- a/src/librustc/ty/util.rs
+++ b/src/librustc/ty/util.rs
@@ -3,18 +3,18 @@
 use crate::hir::map::DefPathData;
 use crate::ich::NodeIdHashingMode;
 use crate::mir::interpret::{sign_extend, truncate};
-use crate::ty::layout::{Integer, IntegerExt};
+use crate::ty::layout::{Integer, IntegerExt, Size};
 use crate::ty::query::TyCtxtAt;
 use crate::ty::subst::{GenericArgKind, InternalSubsts, Subst, SubstsRef};
 use crate::ty::TyKind::*;
 use crate::ty::{self, DefIdTree, GenericParamDefKind, Ty, TyCtxt, TypeFoldable};
 use crate::util::common::ErrorReported;
+use rustc_apfloat::Float as _;
+use rustc_data_structures::fx::{FxHashMap, FxHashSet};
+use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 use rustc_hir as hir;
 use rustc_hir::def::DefKind;
 use rustc_hir::def_id::DefId;
-
-use rustc_data_structures::fx::{FxHashMap, FxHashSet};
-use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 use rustc_macros::HashStable;
 use rustc_span::Span;
 use std::{cmp, fmt};
@@ -43,26 +43,38 @@ impl<'tcx> fmt::Display for Discr<'tcx> {
     }
 }
 
+fn signed_min(size: Size) -> i128 {
+    sign_extend(1_u128 << (size.bits() - 1), size) as i128
+}
+
+fn signed_max(size: Size) -> i128 {
+    i128::max_value() >> (128 - size.bits())
+}
+
+fn unsigned_max(size: Size) -> u128 {
+    u128::max_value() >> (128 - size.bits())
+}
+
+fn int_size_and_signed<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> (Size, bool) {
+    let (int, signed) = match ty.kind {
+        Int(ity) => (Integer::from_attr(&tcx, SignedInt(ity)), true),
+        Uint(uty) => (Integer::from_attr(&tcx, UnsignedInt(uty)), false),
+        _ => bug!("non integer discriminant"),
+    };
+    (int.size(), signed)
+}
+
 impl<'tcx> Discr<'tcx> {
     /// Adds `1` to the value and wraps around if the maximum for the type is reached.
     pub fn wrap_incr(self, tcx: TyCtxt<'tcx>) -> Self {
         self.checked_add(tcx, 1).0
     }
     pub fn checked_add(self, tcx: TyCtxt<'tcx>, n: u128) -> (Self, bool) {
-        let (int, signed) = match self.ty.kind {
-            Int(ity) => (Integer::from_attr(&tcx, SignedInt(ity)), true),
-            Uint(uty) => (Integer::from_attr(&tcx, UnsignedInt(uty)), false),
-            _ => bug!("non integer discriminant"),
-        };
-
-        let size = int.size();
-        let bit_size = int.size().bits();
-        let shift = 128 - bit_size;
-        if signed {
-            let sext = |u| sign_extend(u, size) as i128;
-            let min = sext(1_u128 << (bit_size - 1));
-            let max = i128::max_value() >> shift;
-            let val = sext(self.val);
+        let (size, signed) = int_size_and_signed(tcx, self.ty);
+        let (val, oflo) = if signed {
+            let min = signed_min(size);
+            let max = signed_max(size);
+            let val = sign_extend(self.val, size) as i128;
             assert!(n < (i128::max_value() as u128));
             let n = n as i128;
             let oflo = val > max - n;
@@ -70,14 +82,15 @@ impl<'tcx> Discr<'tcx> {
             // zero the upper bits
             let val = val as u128;
             let val = truncate(val, size);
-            (Self { val: val as u128, ty: self.ty }, oflo)
+            (val, oflo)
         } else {
-            let max = u128::max_value() >> shift;
+            let max = unsigned_max(size);
             let val = self.val;
             let oflo = val > max - n;
             let val = if oflo { n - (max - val) - 1 } else { val + n };
-            (Self { val: val, ty: self.ty }, oflo)
-        }
+            (val, oflo)
+        };
+        (Self { val, ty: self.ty }, oflo)
     }
 }
 
@@ -621,6 +634,44 @@ impl<'tcx> TyCtxt<'tcx> {
 }
 
 impl<'tcx> ty::TyS<'tcx> {
+    /// Returns the maximum value for the given numeric type (including `char`s)
+    /// or returns `None` if the type is not numeric.
+    pub fn numeric_max_val(&'tcx self, tcx: TyCtxt<'tcx>) -> Option<&'tcx ty::Const<'tcx>> {
+        let val = match self.kind {
+            ty::Int(_) | ty::Uint(_) => {
+                let (size, signed) = int_size_and_signed(tcx, self);
+                let val = if signed { signed_max(size) as u128 } else { unsigned_max(size) };
+                Some(val)
+            }
+            ty::Char => Some(std::char::MAX as u128),
+            ty::Float(fty) => Some(match fty {
+                ast::FloatTy::F32 => ::rustc_apfloat::ieee::Single::INFINITY.to_bits(),
+                ast::FloatTy::F64 => ::rustc_apfloat::ieee::Double::INFINITY.to_bits(),
+            }),
+            _ => None,
+        };
+        val.map(|v| ty::Const::from_bits(tcx, v, ty::ParamEnv::empty().and(self)))
+    }
+
+    /// Returns the minimum value for the given numeric type (including `char`s)
+    /// or returns `None` if the type is not numeric.
+    pub fn numeric_min_val(&'tcx self, tcx: TyCtxt<'tcx>) -> Option<&'tcx ty::Const<'tcx>> {
+        let val = match self.kind {
+            ty::Int(_) | ty::Uint(_) => {
+                let (size, signed) = int_size_and_signed(tcx, self);
+                let val = if signed { truncate(signed_min(size) as u128, size) } else { 0 };
+                Some(val)
+            }
+            ty::Char => Some(0),
+            ty::Float(fty) => Some(match fty {
+                ast::FloatTy::F32 => (-::rustc_apfloat::ieee::Single::INFINITY).to_bits(),
+                ast::FloatTy::F64 => (-::rustc_apfloat::ieee::Double::INFINITY).to_bits(),
+            }),
+            _ => None,
+        };
+        val.map(|v| ty::Const::from_bits(tcx, v, ty::ParamEnv::empty().and(self)))
+    }
+
     /// Checks whether values of this type `T` are *moved* or *copied*
     /// when referenced -- this amounts to a check for whether `T:
     /// Copy`, but note that we **don't** consider lifetimes when