Auto merge of #118879 - Nadrieril:lint-range-gap, r=estebank

Lint singleton gaps after exclusive ranges

In the discussion to stabilize exclusive range patterns (https://github.com/rust-lang/rust/issues/37854), it has often come up that they're likely to cause off-by-one mistakes. We already have the `overlapping_range_endpoints` lint, so I [proposed](https://github.com/rust-lang/rust/issues/37854#issuecomment-1845580712) a lint to catch the complementary mistake.

This PR adds a new `non_contiguous_range_endpoints` lint that catches likely off-by-one errors with exclusive range patterns. Here's the idea (see the test file for more examples):
```rust
match x {
    0..10 => ..., // WARN: this range doesn't match `10_u8` because `..` is an exclusive range
    11..20 => ..., // this could appear to continue range `0_u8..10_u8`, but `10_u8` isn't matched by either of them
    _ => ...,
}
// help: use an inclusive range instead: `0_u8..=10_u8`
```

More precisely: for any exclusive range `lo..hi`, if `hi+1` is matched by another range but `hi` isn't, we suggest writing an inclusive range `lo..=hi` instead. We also catch `lo..T::MAX`.

5 files changed, 197 insertions, 32 deletions

diff --git a/compiler/rustc_pattern_analysis/src/constructor.rs b/compiler/rustc_pattern_analysis/src/constructor.rs
index 767227619b0..69e294e47a5 100644
--- a/compiler/rustc_pattern_analysis/src/constructor.rs
+++ b/compiler/rustc_pattern_analysis/src/constructor.rs
@@ -192,7 +192,7 @@ impl fmt::Display for RangeEnd {
 #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
 pub enum MaybeInfiniteInt {
     NegInfinity,
-    /// Encoded value. DO NOT CONSTRUCT BY HAND; use `new_finite`.
+    /// Encoded value. DO NOT CONSTRUCT BY HAND; use `new_finite_{int,uint}`.
     #[non_exhaustive]
     Finite(u128),
     /// The integer after `u128::MAX`. We need it to represent `x..=u128::MAX` as an exclusive range.
@@ -229,25 +229,22 @@ impl MaybeInfiniteInt {
     }
 
     /// Note: this will not turn a finite value into an infinite one or vice-versa.
-    pub fn minus_one(self) -> Self {
+    pub fn minus_one(self) -> Option<Self> {
         match self {
-            Finite(n) => match n.checked_sub(1) {
-                Some(m) => Finite(m),
-                None => panic!("Called `MaybeInfiniteInt::minus_one` on 0"),
-            },
-            JustAfterMax => Finite(u128::MAX),
-            x => x,
+            Finite(n) => n.checked_sub(1).map(Finite),
+            JustAfterMax => Some(Finite(u128::MAX)),
+            x => Some(x),
         }
     }
     /// Note: this will not turn a finite value into an infinite one or vice-versa.
-    pub fn plus_one(self) -> Self {
+    pub fn plus_one(self) -> Option<Self> {
         match self {
             Finite(n) => match n.checked_add(1) {
-                Some(m) => Finite(m),
-                None => JustAfterMax,
+                Some(m) => Some(Finite(m)),
+                None => Some(JustAfterMax),
             },
-            JustAfterMax => panic!("Called `MaybeInfiniteInt::plus_one` on u128::MAX+1"),
-            x => x,
+            JustAfterMax => None,
+            x => Some(x),
         }
     }
 }
@@ -268,18 +265,24 @@ impl IntRange {
     pub fn is_singleton(&self) -> bool {
         // Since `lo` and `hi` can't be the same `Infinity` and `plus_one` never changes from finite
         // to infinite, this correctly only detects ranges that contain exacly one `Finite(x)`.
-        self.lo.plus_one() == self.hi
+        self.lo.plus_one() == Some(self.hi)
     }
 
+    /// Construct a singleton range.
+    /// `x` must be a `Finite(_)` value.
     #[inline]
     pub fn from_singleton(x: MaybeInfiniteInt) -> IntRange {
-        IntRange { lo: x, hi: x.plus_one() }
+        // `unwrap()` is ok on a finite value
+        IntRange { lo: x, hi: x.plus_one().unwrap() }
     }
 
+    /// Construct a range with these boundaries.
+    /// `lo` must not be `PosInfinity` or `JustAfterMax`. `hi` must not be `NegInfinity`.
+    /// If `end` is `Included`, `hi` must also not be `JustAfterMax`.
     #[inline]
     pub fn from_range(lo: MaybeInfiniteInt, mut hi: MaybeInfiniteInt, end: RangeEnd) -> IntRange {
         if end == RangeEnd::Included {
-            hi = hi.plus_one();
+            hi = hi.plus_one().unwrap();
         }
         if lo >= hi {
             // This should have been caught earlier by E0030.
diff --git a/compiler/rustc_pattern_analysis/src/errors.rs b/compiler/rustc_pattern_analysis/src/errors.rs
index d0f56f0268d..e471b8abd73 100644
--- a/compiler/rustc_pattern_analysis/src/errors.rs
+++ b/compiler/rustc_pattern_analysis/src/errors.rs
@@ -77,6 +77,57 @@ impl<'tcx> AddToDiagnostic for Overlap<'tcx> {
 }
 
 #[derive(LintDiagnostic)]
+#[diag(pattern_analysis_excluside_range_missing_max)]
+pub struct ExclusiveRangeMissingMax<'tcx> {
+    #[label]
+    #[suggestion(code = "{suggestion}", applicability = "maybe-incorrect")]
+    /// This is an exclusive range that looks like `lo..max` (i.e. doesn't match `max`).
+    pub first_range: Span,
+    /// Suggest `lo..=max` instead.
+    pub suggestion: String,
+    pub max: Pat<'tcx>,
+}
+
+#[derive(LintDiagnostic)]
+#[diag(pattern_analysis_excluside_range_missing_gap)]
+pub struct ExclusiveRangeMissingGap<'tcx> {
+    #[label]
+    #[suggestion(code = "{suggestion}", applicability = "maybe-incorrect")]
+    /// This is an exclusive range that looks like `lo..gap` (i.e. doesn't match `gap`).
+    pub first_range: Span,
+    pub gap: Pat<'tcx>,
+    /// Suggest `lo..=gap` instead.
+    pub suggestion: String,
+    #[subdiagnostic]
+    /// All these ranges skipped over `gap` which we think is probably a mistake.
+    pub gap_with: Vec<GappedRange<'tcx>>,
+}
+
+pub struct GappedRange<'tcx> {
+    pub span: Span,
+    pub gap: Pat<'tcx>,
+    pub first_range: Pat<'tcx>,
+}
+
+impl<'tcx> AddToDiagnostic for GappedRange<'tcx> {
+    fn add_to_diagnostic_with<G: EmissionGuarantee, F: SubdiagMessageOp<G>>(
+        self,
+        diag: &mut Diag<'_, G>,
+        _: F,
+    ) {
+        let GappedRange { span, gap, first_range } = self;
+
+        // FIXME(mejrs) unfortunately `#[derive(LintDiagnostic)]`
+        // does not support `#[subdiagnostic(eager)]`...
+        let message = format!(
+            "this could appear to continue range `{first_range}`, but `{gap}` isn't matched by \
+            either of them"
+        );
+        diag.span_label(span, message);
+    }
+}
+
+#[derive(LintDiagnostic)]
 #[diag(pattern_analysis_non_exhaustive_omitted_pattern)]
 #[help]
 #[note]
diff --git a/compiler/rustc_pattern_analysis/src/lib.rs b/compiler/rustc_pattern_analysis/src/lib.rs
index 4b0955699fc..f632eaf7ea4 100644
--- a/compiler/rustc_pattern_analysis/src/lib.rs
+++ b/compiler/rustc_pattern_analysis/src/lib.rs
@@ -70,14 +70,8 @@ use rustc_middle::ty::Ty;
 use rustc_span::ErrorGuaranteed;
 
 use crate::constructor::{Constructor, ConstructorSet, IntRange};
-#[cfg(feature = "rustc")]
-use crate::lints::lint_nonexhaustive_missing_variants;
 use crate::pat::DeconstructedPat;
 use crate::pat_column::PatternColumn;
-#[cfg(feature = "rustc")]
-use crate::rustc::RustcMatchCheckCtxt;
-#[cfg(feature = "rustc")]
-use crate::usefulness::{compute_match_usefulness, ValidityConstraint};
 
 pub trait Captures<'a> {}
 impl<'a, T: ?Sized> Captures<'a> for T {}
@@ -145,6 +139,18 @@ pub trait TypeCx: Sized + fmt::Debug {
 
     /// The maximum pattern complexity limit was reached.
     fn complexity_exceeded(&self) -> Result<(), Self::Error>;
+
+    /// Lint that there is a gap `gap` between `pat` and all of `gapped_with` such that the gap is
+    /// not matched by another range. If `gapped_with` is empty, then `gap` is `T::MAX`. We only
+    /// detect singleton gaps.
+    /// The default implementation does nothing.
+    fn lint_non_contiguous_range_endpoints(
+        &self,
+        _pat: &DeconstructedPat<Self>,
+        _gap: IntRange,
+        _gapped_with: &[&DeconstructedPat<Self>],
+    ) {
+    }
 }
 
 /// The arm of a match expression.
@@ -167,11 +173,14 @@ impl<'p, Cx: TypeCx> Copy for MatchArm<'p, Cx> {}
 /// useful, and runs some lints.
 #[cfg(feature = "rustc")]
 pub fn analyze_match<'p, 'tcx>(
-    tycx: &RustcMatchCheckCtxt<'p, 'tcx>,
+    tycx: &rustc::RustcMatchCheckCtxt<'p, 'tcx>,
     arms: &[rustc::MatchArm<'p, 'tcx>],
     scrut_ty: Ty<'tcx>,
     pattern_complexity_limit: Option<usize>,
 ) -> Result<rustc::UsefulnessReport<'p, 'tcx>, ErrorGuaranteed> {
+    use lints::lint_nonexhaustive_missing_variants;
+    use usefulness::{compute_match_usefulness, ValidityConstraint};
+
     let scrut_ty = tycx.reveal_opaque_ty(scrut_ty);
     let scrut_validity = ValidityConstraint::from_bool(tycx.known_valid_scrutinee);
     let report =
diff --git a/compiler/rustc_pattern_analysis/src/rustc.rs b/compiler/rustc_pattern_analysis/src/rustc.rs
index 5f5bfa7154a..0085f0ab656 100644
--- a/compiler/rustc_pattern_analysis/src/rustc.rs
+++ b/compiler/rustc_pattern_analysis/src/rustc.rs
@@ -8,7 +8,7 @@ use rustc_index::{Idx, IndexVec};
 use rustc_middle::middle::stability::EvalResult;
 use rustc_middle::mir::interpret::Scalar;
 use rustc_middle::mir::{self, Const};
-use rustc_middle::thir::{FieldPat, Pat, PatKind, PatRange, PatRangeBoundary};
+use rustc_middle::thir::{self, FieldPat, Pat, PatKind, PatRange, PatRangeBoundary};
 use rustc_middle::ty::layout::IntegerExt;
 use rustc_middle::ty::{self, FieldDef, OpaqueTypeKey, Ty, TyCtxt, TypeVisitableExt, VariantDef};
 use rustc_session::lint;
@@ -718,12 +718,12 @@ impl<'p, 'tcx: 'p> RustcMatchCheckCtxt<'p, 'tcx> {
                 let value = mir::Const::from_ty_const(c, cx.tcx);
                 lo = PatRangeBoundary::Finite(value);
             }
-            let hi = if matches!(range.hi, Finite(0)) {
+            let hi = if let Some(hi) = range.hi.minus_one() {
+                hi
+            } else {
                 // The range encodes `..ty::MIN`, so we can't convert it to an inclusive range.
                 end = rustc_hir::RangeEnd::Excluded;
                 range.hi
-            } else {
-                range.hi.minus_one()
             };
             let hi = cx.hoist_pat_range_bdy(hi, ty);
             PatKind::Range(Box::new(PatRange { lo, hi, end, ty: ty.inner() }))
@@ -900,6 +900,70 @@ impl<'p, 'tcx: 'p> TypeCx for RustcMatchCheckCtxt<'p, 'tcx> {
         let span = self.whole_match_span.unwrap_or(self.scrut_span);
         Err(self.tcx.dcx().span_err(span, "reached pattern complexity limit"))
     }
+
+    fn lint_non_contiguous_range_endpoints(
+        &self,
+        pat: &crate::pat::DeconstructedPat<Self>,
+        gap: IntRange,
+        gapped_with: &[&crate::pat::DeconstructedPat<Self>],
+    ) {
+        let Some(&thir_pat) = pat.data() else { return };
+        let thir::PatKind::Range(range) = &thir_pat.kind else { return };
+        // Only lint when the left range is an exclusive range.
+        if range.end != rustc_hir::RangeEnd::Excluded {
+            return;
+        }
+        // `pat` is an exclusive range like `lo..gap`. `gapped_with` contains ranges that start with
+        // `gap+1`.
+        let suggested_range: thir::Pat<'_> = {
+            // Suggest `lo..=gap` instead.
+            let mut suggested_range = thir_pat.clone();
+            let thir::PatKind::Range(range) = &mut suggested_range.kind else { unreachable!() };
+            range.end = rustc_hir::RangeEnd::Included;
+            suggested_range
+        };
+        let gap_as_pat = self.hoist_pat_range(&gap, *pat.ty());
+        if gapped_with.is_empty() {
+            // If `gapped_with` is empty, `gap == T::MAX`.
+            self.tcx.emit_node_span_lint(
+                lint::builtin::NON_CONTIGUOUS_RANGE_ENDPOINTS,
+                self.match_lint_level,
+                thir_pat.span,
+                errors::ExclusiveRangeMissingMax {
+                    // Point at this range.
+                    first_range: thir_pat.span,
+                    // That's the gap that isn't covered.
+                    max: gap_as_pat.clone(),
+                    // Suggest `lo..=max` instead.
+                    suggestion: suggested_range.to_string(),
+                },
+            );
+        } else {
+            self.tcx.emit_node_span_lint(
+                lint::builtin::NON_CONTIGUOUS_RANGE_ENDPOINTS,
+                self.match_lint_level,
+                thir_pat.span,
+                errors::ExclusiveRangeMissingGap {
+                    // Point at this range.
+                    first_range: thir_pat.span,
+                    // That's the gap that isn't covered.
+                    gap: gap_as_pat.clone(),
+                    // Suggest `lo..=gap` instead.
+                    suggestion: suggested_range.to_string(),
+                    // All these ranges skipped over `gap` which we think is probably a
+                    // mistake.
+                    gap_with: gapped_with
+                        .iter()
+                        .map(|pat| errors::GappedRange {
+                            span: pat.data().unwrap().span,
+                            gap: gap_as_pat.clone(),
+                            first_range: thir_pat.clone(),
+                        })
+                        .collect(),
+                },
+            );
+        }
+    }
 }
 
 /// Recursively expand this pattern into its subpatterns. Only useful for or-patterns.
diff --git a/compiler/rustc_pattern_analysis/src/usefulness.rs b/compiler/rustc_pattern_analysis/src/usefulness.rs
index c518844cc5e..a067bf1f0c2 100644
--- a/compiler/rustc_pattern_analysis/src/usefulness.rs
+++ b/compiler/rustc_pattern_analysis/src/usefulness.rs
@@ -1489,7 +1489,7 @@ impl<Cx: TypeCx> WitnessMatrix<Cx> {
 /// We can however get false negatives because exhaustiveness does not explore all cases. See the
 /// section on relevancy at the top of the file.
 fn collect_overlapping_range_endpoints<'p, Cx: TypeCx>(
-    mcx: &mut UsefulnessCtxt<'_, Cx>,
+    cx: &Cx,
     overlap_range: IntRange,
     matrix: &Matrix<'p, Cx>,
     specialized_matrix: &Matrix<'p, Cx>,
@@ -1522,11 +1522,11 @@ fn collect_overlapping_range_endpoints<'p, Cx: TypeCx>(
                     .map(|&(_, pat)| pat)
                     .collect();
                 if !overlaps_with.is_empty() {
-                    mcx.tycx.lint_overlapping_range_endpoints(pat, overlap_range, &overlaps_with);
+                    cx.lint_overlapping_range_endpoints(pat, overlap_range, &overlaps_with);
                 }
             }
             suffixes.push((child_row_id, pat))
-        } else if this_range.hi == overlap.plus_one() {
+        } else if Some(this_range.hi) == overlap.plus_one() {
             // `this_range` looks like `this_range.lo..=overlap`; it overlaps with any
             // ranges that look like `overlap..=hi`.
             if !suffixes.is_empty() {
@@ -1538,7 +1538,7 @@ fn collect_overlapping_range_endpoints<'p, Cx: TypeCx>(
                     .map(|&(_, pat)| pat)
                     .collect();
                 if !overlaps_with.is_empty() {
-                    mcx.tycx.lint_overlapping_range_endpoints(pat, overlap_range, &overlaps_with);
+                    cx.lint_overlapping_range_endpoints(pat, overlap_range, &overlaps_with);
                 }
             }
             prefixes.push((child_row_id, pat))
@@ -1546,6 +1546,33 @@ fn collect_overlapping_range_endpoints<'p, Cx: TypeCx>(
     }
 }
 
+/// Collect ranges that have a singleton gap between them.
+fn collect_non_contiguous_range_endpoints<'p, Cx: TypeCx>(
+    cx: &Cx,
+    gap_range: &IntRange,
+    matrix: &Matrix<'p, Cx>,
+) {
+    let gap = gap_range.lo;
+    // Ranges that look like `lo..gap`.
+    let mut onebefore: SmallVec<[_; 1]> = Default::default();
+    // Ranges that start on `gap+1` or singletons `gap+1`.
+    let mut oneafter: SmallVec<[_; 1]> = Default::default();
+    // Look through the column for ranges near the gap.
+    for pat in matrix.heads() {
+        let PatOrWild::Pat(pat) = pat else { continue };
+        let Constructor::IntRange(this_range) = pat.ctor() else { continue };
+        if gap == this_range.hi {
+            onebefore.push(pat)
+        } else if gap.plus_one() == Some(this_range.lo) {
+            oneafter.push(pat)
+        }
+    }
+
+    for pat_before in onebefore {
+        cx.lint_non_contiguous_range_endpoints(pat_before, *gap_range, oneafter.as_slice());
+    }
+}
+
 /// The core of the algorithm.
 ///
 /// This recursively computes witnesses of the non-exhaustiveness of `matrix` (if any). Also tracks
@@ -1626,13 +1653,24 @@ fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>(
                 && spec_matrix.rows.len() >= 2
                 && spec_matrix.rows.iter().any(|row| !row.intersects.is_empty())
             {
-                collect_overlapping_range_endpoints(mcx, overlap_range, matrix, &spec_matrix);
+                collect_overlapping_range_endpoints(mcx.tycx, overlap_range, matrix, &spec_matrix);
             }
         }
 
         matrix.unspecialize(spec_matrix);
     }
 
+    // Detect singleton gaps between ranges.
+    if missing_ctors.iter().any(|c| matches!(c, Constructor::IntRange(..))) {
+        for missing in &missing_ctors {
+            if let Constructor::IntRange(gap) = missing {
+                if gap.is_singleton() {
+                    collect_non_contiguous_range_endpoints(mcx.tycx, gap, matrix);
+                }
+            }
+        }
+    }
+
     // Record usefulness in the patterns.
     for row in matrix.rows() {
         if row.useful {