Skip to content

Commit 8872fef

Browse files
NadrierilNadrieril
committed
Lint overlapping ranges as a separate pass
1 parent e20cb77 commit 8872fef

File tree

5 files changed

+179
-105
lines changed

5 files changed

+179
-105
lines changed

‎compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs

+17-74
Original file line numberDiff line numberDiff line change
@@ -53,22 +53,20 @@ use smallvec::{smallvec, SmallVec};
5353
use rustc_apfloat::ieee::{DoubleS, IeeeFloat, SingleS};
5454
use rustc_data_structures::captures::Captures;
5555
use rustc_data_structures::fx::FxHashSet;
56-
use rustc_hir::{HirId, RangeEnd};
56+
use rustc_hir::RangeEnd;
5757
use rustc_index::Idx;
5858
use rustc_middle::middle::stability::EvalResult;
5959
use rustc_middle::mir;
6060
use rustc_middle::thir::{FieldPat, Pat, PatKind, PatRange};
6161
use rustc_middle::ty::layout::IntegerExt;
6262
use rustc_middle::ty::{self, Ty, TyCtxt, VariantDef};
63-
use rustc_session::lint;
6463
use rustc_span::{Span, DUMMY_SP};
6564
use rustc_target::abi::{FieldIdx, Integer, VariantIdx, FIRST_VARIANT};
6665

6766
use self::Constructor::*;
6867
use self::SliceKind::*;
6968

7069
use super::usefulness::{MatchCheckCtxt, PatCtxt};
71-
use crate::errors::{Overlap, OverlappingRangeEndpoints};
7270

7371
/// Recursively expand this pattern into its subpatterns. Only useful for or-patterns.
7472
fn expand_or_pat<'p, 'tcx>(pat: &'p Pat<'tcx>) -> Vec<&'p Pat<'tcx>> {
@@ -111,15 +109,15 @@ pub(crate) struct IntRange {
111109

112110
impl IntRange {
113111
#[inline]
114-
fn is_integral(ty: Ty<'_>) -> bool {
112+
pub(super) fn is_integral(ty: Ty<'_>) -> bool {
115113
matches!(ty.kind(), ty::Char | ty::Int(_) | ty::Uint(_) | ty::Bool)
116114
}
117115

118-
fn is_singleton(&self) -> bool {
116+
pub(super) fn is_singleton(&self) -> bool {
119117
self.range.start() == self.range.end()
120118
}
121119

122-
fn boundaries(&self) -> (u128, u128) {
120+
pub(super) fn boundaries(&self) -> (u128, u128) {
123121
(*self.range.start(), *self.range.end())
124122
}
125123

@@ -177,23 +175,6 @@ impl IntRange {
177175
}
178176
}
179177

180-
fn suspicious_intersection(&self, other: &Self) -> bool {
181-
// `false` in the following cases:
182-
// 1 ---- // 1 ---------- // 1 ---- // 1 ----
183-
// 2 ---------- // 2 ---- // 2 ---- // 2 ----
184-
//
185-
// The following are currently `false`, but could be `true` in the future (#64007):
186-
// 1 --------- // 1 ---------
187-
// 2 ---------- // 2 ----------
188-
//
189-
// `true` in the following cases:
190-
// 1 ------- // 1 -------
191-
// 2 -------- // 2 -------
192-
let (lo, hi) = self.boundaries();
193-
let (other_lo, other_hi) = other.boundaries();
194-
(lo == other_hi || hi == other_lo) && !self.is_singleton() && !other.is_singleton()
195-
}
196-
197178
/// Partition a range of integers into disjoint subranges. This does constructor splitting for
198179
/// integer ranges as explained at the top of the file.
199180
///
@@ -293,7 +274,7 @@ impl IntRange {
293274
}
294275

295276
/// Only used for displaying the range.
296-
fn to_pat<'tcx>(&self, tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> Pat<'tcx> {
277+
pub(super) fn to_pat<'tcx>(&self, tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> Pat<'tcx> {
297278
let (lo, hi) = self.boundaries();
298279

299280
let bias = IntRange::signed_bias(tcx, ty);
@@ -315,51 +296,6 @@ impl IntRange {
315296

316297
Pat { ty, span: DUMMY_SP, kind }
317298
}
318-
319-
/// Lint on likely incorrect range patterns (#63987)
320-
pub(super) fn lint_overlapping_range_endpoints<'a, 'p: 'a, 'tcx: 'a>(
321-
&self,
322-
pcx: &PatCtxt<'_, 'p, 'tcx>,
323-
pats: impl Iterator<Item = &'a DeconstructedPat<'p, 'tcx>>,
324-
column_count: usize,
325-
lint_root: HirId,
326-
) {
327-
if self.is_singleton() {
328-
return;
329-
}
330-
331-
if column_count != 1 {
332-
// FIXME: for now, only check for overlapping ranges on simple range
333-
// patterns. Otherwise with the current logic the following is detected
334-
// as overlapping:
335-
// ```
336-
// match (0u8, true) {
337-
// (0 ..= 125, false) => {}
338-
// (125 ..= 255, true) => {}
339-
// _ => {}
340-
// }
341-
// ```
342-
return;
343-
}
344-
345-
let overlap: Vec<_> = pats
346-
.filter_map(|pat| Some((pat.ctor().as_int_range()?, pat.span())))
347-
.filter(|(range, _)| self.suspicious_intersection(range))
348-
.map(|(range, span)| Overlap {
349-
range: self.intersection(&range).unwrap().to_pat(pcx.cx.tcx, pcx.ty),
350-
span,
351-
})
352-
.collect();
353-
354-
if !overlap.is_empty() {
355-
pcx.cx.tcx.emit_spanned_lint(
356-
lint::builtin::OVERLAPPING_RANGE_ENDPOINTS,
357-
lint_root,
358-
pcx.span,
359-
OverlappingRangeEndpoints { overlap, range: pcx.span },
360-
);
361-
}
362-
}
363299
}
364300

365301
/// Note: this is often not what we want: e.g. `false` is converted into the range `0..=0` and
@@ -651,7 +587,7 @@ impl<'tcx> Constructor<'tcx> {
651587
_ => None,
652588
}
653589
}
654-
fn as_int_range(&self) -> Option<&IntRange> {
590+
pub(super) fn as_int_range(&self) -> Option<&IntRange> {
655591
match self {
656592
IntRange(range) => Some(range),
657593
_ => None,
@@ -905,9 +841,9 @@ pub(super) enum ConstructorSet {
905841
/// either fully included in or disjoint from each constructor in the column. This avoids
906842
/// non-trivial intersections like between `0..10` and `5..15`.
907843
#[derive(Debug)]
908-
struct SplitConstructorSet<'tcx> {
909-
present: SmallVec<[Constructor<'tcx>; 1]>,
910-
missing: Vec<Constructor<'tcx>>,
844+
pub(super) struct SplitConstructorSet<'tcx> {
845+
pub(super) present: SmallVec<[Constructor<'tcx>; 1]>,
846+
pub(super) missing: Vec<Constructor<'tcx>>,
911847
/// For the `non_exhaustive_omitted_patterns` lint.
912848
nonexhaustive_enum_missing_visible_variants: bool,
913849
}
@@ -1039,7 +975,7 @@ impl ConstructorSet {
1039975
/// constructors to 1/ determine which constructors of the type (if any) are missing; 2/ split
1040976
/// constructors to handle non-trivial intersections e.g. on ranges or slices.
1041977
#[instrument(level = "debug", skip(self, pcx, ctors), ret)]
1042-
fn split<'a, 'tcx>(
978+
pub(super) fn split<'a, 'tcx>(
1043979
&self,
1044980
pcx: &PatCtxt<'_, '_, 'tcx>,
1045981
ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone,
@@ -1621,6 +1557,13 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
16211557
pub(super) fn is_or_pat(&self) -> bool {
16221558
matches!(self.ctor, Or)
16231559
}
1560+
pub(super) fn flatten_or_pat(&'p self) -> SmallVec<[&'p Self; 1]> {
1561+
if self.is_or_pat() {
1562+
self.iter_fields().flat_map(|p| p.flatten_or_pat()).collect()
1563+
} else {
1564+
smallvec![self]
1565+
}
1566+
}
16241567

16251568
pub(super) fn ctor(&self) -> &Constructor<'tcx> {
16261569
&self.ctor

‎compiler/rustc_mir_build/src/thir/pattern/usefulness.rs

+103-16
Original file line numberDiff line numberDiff line change
@@ -307,8 +307,8 @@
307307
308308
use self::ArmType::*;
309309
use self::Usefulness::*;
310-
use super::deconstruct_pat::{Constructor, ConstructorSet, DeconstructedPat, Fields};
311-
use crate::errors::{NonExhaustiveOmittedPattern, Uncovered};
310+
use super::deconstruct_pat::{Constructor, ConstructorSet, DeconstructedPat, Fields, IntRange};
311+
use crate::errors::{NonExhaustiveOmittedPattern, Overlap, OverlappingRangeEndpoints, Uncovered};
312312

313313
use rustc_data_structures::captures::Captures;
314314

@@ -317,6 +317,7 @@ use rustc_data_structures::stack::ensure_sufficient_stack;
317317
use rustc_hir::def_id::DefId;
318318
use rustc_hir::HirId;
319319
use rustc_middle::ty::{self, Ty, TyCtxt};
320+
use rustc_session::lint;
320321
use rustc_session::lint::builtin::NON_EXHAUSTIVE_OMITTED_PATTERNS;
321322
use rustc_span::{Span, DUMMY_SP};
322323

@@ -474,11 +475,6 @@ impl<'p, 'tcx> Matrix<'p, 'tcx> {
474475
Matrix { patterns: vec![] }
475476
}
476477

477-
/// Number of columns of this matrix. `None` is the matrix is empty.
478-
pub(super) fn column_count(&self) -> Option<usize> {
479-
self.patterns.get(0).map(|r| r.len())
480-
}
481-
482478
/// Pushes a new row to the matrix. If the row starts with an or-pattern, this recursively
483479
/// expands it.
484480
fn push(&mut self, row: PatStack<'p, 'tcx>) {
@@ -826,15 +822,6 @@ fn is_useful<'p, 'tcx>(
826822

827823
let v_ctor = v.head().ctor();
828824
debug!(?v_ctor);
829-
if let Constructor::IntRange(ctor_range) = &v_ctor {
830-
// Lint on likely incorrect range patterns (#63987)
831-
ctor_range.lint_overlapping_range_endpoints(
832-
pcx,
833-
matrix.heads(),
834-
matrix.column_count().unwrap_or(0),
835-
lint_root,
836-
)
837-
}
838825
// We split the head constructor of `v`.
839826
let split_ctors = v_ctor.split(pcx, matrix.heads().map(DeconstructedPat::ctor));
840827
let is_non_exhaustive_and_wild =
@@ -914,6 +901,102 @@ fn is_useful<'p, 'tcx>(
914901
ret
915902
}
916903

904+
/// Traverse the patterns to warn the user about ranges that overlap on their endpoints.
905+
/// This traverses patterns column-by-column, where a column is the intuitive notion of "subpatterns
906+
/// that inspect the same subvalue". Despite similarities with `is_useful`, this traversal is
907+
/// different. Notably this is linear in the depth of patterns, whereas `is_useful` is worst-case
908+
/// exponential (exhaustiveness is NP-complete).
909+
fn lint_overlapping_range_endpoints<'p, 'tcx>(
910+
cx: &MatchCheckCtxt<'p, 'tcx>,
911+
column: &[&DeconstructedPat<'p, 'tcx>],
912+
lint_root: HirId,
913+
) {
914+
if column.is_empty() {
915+
return;
916+
}
917+
let ty = column[0].ty();
918+
let pcx = &PatCtxt { cx, ty, span: DUMMY_SP, is_top_level: false };
919+
920+
let column_ctors = column.iter().map(|p| p.ctor());
921+
let set = ConstructorSet::for_ty(pcx.cx, pcx.ty).split(pcx, column_ctors);
922+
923+
if IntRange::is_integral(ty) {
924+
// If two ranges overlapped, the split set will contain their intersection as a singleton.
925+
let split_int_ranges = set.present.iter().filter_map(|c| c.as_int_range());
926+
for overlap_range in split_int_ranges.clone() {
927+
if overlap_range.is_singleton() {
928+
let overlap: u128 = overlap_range.boundaries().0;
929+
// Spans of ranges that start or end with the overlap.
930+
let mut prefixes: SmallVec<[_; 1]> = Default::default();
931+
let mut suffixes: SmallVec<[_; 1]> = Default::default();
932+
// Iterate on patterns that contained `overlap`.
933+
for pat in column {
934+
let this_span = pat.span();
935+
let Constructor::IntRange(this_range) = pat.ctor() else { continue };
936+
if this_range.is_singleton() {
937+
// Don't lint when one of the ranges is a singleton.
938+
continue;
939+
}
940+
let mut this_overlaps: SmallVec<[_; 1]> = Default::default();
941+
let (start, end) = this_range.boundaries();
942+
if start == overlap {
943+
if !prefixes.is_empty() {
944+
this_overlaps = prefixes.clone();
945+
}
946+
suffixes.push(this_span)
947+
} else if end == overlap {
948+
if !suffixes.is_empty() {
949+
this_overlaps = suffixes.clone();
950+
}
951+
prefixes.push(this_span)
952+
}
953+
if !this_overlaps.is_empty() {
954+
let overlap_as_pat = overlap_range.to_pat(pcx.cx.tcx, pcx.ty);
955+
let overlaps: Vec<_> = this_overlaps
956+
.into_iter()
957+
.map(|span| Overlap { range: overlap_as_pat.clone(), span })
958+
.collect();
959+
pcx.cx.tcx.emit_spanned_lint(
960+
lint::builtin::OVERLAPPING_RANGE_ENDPOINTS,
961+
lint_root,
962+
this_span,
963+
OverlappingRangeEndpoints { overlap: overlaps, range: this_span },
964+
);
965+
}
966+
}
967+
}
968+
}
969+
}
970+
971+
// Recurse into the fields.
972+
for ctor in set.present {
973+
let arity = ctor.arity(pcx);
974+
if arity == 0 {
975+
continue;
976+
}
977+
978+
// We specialize the column by `ctor`. This gives us `arity`-many columns of patterns. These
979+
// columns may have different lengths in the presence of or-patterns (this is why we can't
980+
// reuse `Matrix`).
981+
let mut specialized_columns: Vec<Vec<_>> = (0..arity).map(|_| Vec::new()).collect();
982+
let relevant_patterns = column.iter().filter(|pat| ctor.is_covered_by(pcx, pat.ctor()));
983+
for pat in relevant_patterns {
984+
let specialized = pat.specialize(pcx, &ctor);
985+
for (subpat, sub_column) in specialized.iter().zip(&mut specialized_columns) {
986+
if subpat.is_or_pat() {
987+
sub_column.extend(subpat.iter_fields())
988+
} else {
989+
sub_column.push(subpat)
990+
}
991+
}
992+
}
993+
994+
for col in specialized_columns.iter() {
995+
lint_overlapping_range_endpoints(cx, col.as_slice(), lint_root);
996+
}
997+
}
998+
}
999+
9171000
/// The arm of a match expression.
9181001
#[derive(Clone, Copy, Debug)]
9191002
pub(crate) struct MatchArm<'p, 'tcx> {
@@ -982,5 +1065,9 @@ pub(crate) fn compute_match_usefulness<'p, 'tcx>(
9821065
WithWitnesses(pats) => pats.into_iter().map(|w| w.single_pattern()).collect(),
9831066
NoWitnesses { .. } => bug!(),
9841067
};
1068+
1069+
let pat_column = arms.iter().flat_map(|arm| arm.pat.flatten_or_pat()).collect::<Vec<_>>();
1070+
lint_overlapping_range_endpoints(cx, &pat_column, lint_root);
1071+
9851072
UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses }
9861073
}

‎tests/ui/mir/mir_match_test.rs

+1
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
11
#![feature(exclusive_range_pattern)]
2+
#![allow(overlapping_range_endpoints)]
23

34
// run-pass
45

‎tests/ui/pattern/usefulness/integer-ranges/overlapping_range_endpoints.rs

+11-9
Original file line numberDiff line numberDiff line change
@@ -8,17 +8,17 @@ macro_rules! m {
88
$t2 => {}
99
_ => {}
1010
}
11-
}
11+
};
1212
}
1313

1414
fn main() {
1515
m!(0u8, 20..=30, 30..=40); //~ ERROR multiple patterns overlap on their endpoints
1616
m!(0u8, 30..=40, 20..=30); //~ ERROR multiple patterns overlap on their endpoints
1717
m!(0u8, 20..=30, 31..=40);
1818
m!(0u8, 20..=30, 29..=40);
19-
m!(0u8, 20.. 30, 29..=40); //~ ERROR multiple patterns overlap on their endpoints
20-
m!(0u8, 20.. 30, 28..=40);
21-
m!(0u8, 20.. 30, 30..=40);
19+
m!(0u8, 20..30, 29..=40); //~ ERROR multiple patterns overlap on their endpoints
20+
m!(0u8, 20..30, 28..=40);
21+
m!(0u8, 20..30, 30..=40);
2222
m!(0u8, 20..=30, 30..=30);
2323
m!(0u8, 20..=30, 30..=31); //~ ERROR multiple patterns overlap on their endpoints
2424
m!(0u8, 20..=30, 29..=30);
@@ -28,27 +28,29 @@ fn main() {
2828
m!(0u8, 20..=30, 20);
2929
m!(0u8, 20..=30, 25);
3030
m!(0u8, 20..=30, 30);
31-
m!(0u8, 20.. 30, 29);
31+
m!(0u8, 20..30, 29);
3232
m!(0u8, 20, 20..=30);
3333
m!(0u8, 25, 20..=30);
3434
m!(0u8, 30, 20..=30);
3535

3636
match 0u8 {
3737
0..=10 => {}
3838
20..=30 => {}
39-
10..=20 => {} //~ ERROR multiple patterns overlap on their endpoints
39+
10..=20 => {}
40+
//~^ ERROR multiple patterns overlap on their endpoints
41+
//~| ERROR multiple patterns overlap on their endpoints
4042
_ => {}
4143
}
4244
match (0u8, true) {
4345
(0..=10, true) => {}
44-
(10..20, true) => {} // not detected
45-
(10..20, false) => {}
46+
(10..20, true) => {} //~ ERROR multiple patterns overlap on their endpoints
47+
(10..20, false) => {} //~ ERROR multiple patterns overlap on their endpoints
4648
_ => {}
4749
}
4850
match (true, 0u8) {
4951
(true, 0..=10) => {}
5052
(true, 10..20) => {} //~ ERROR multiple patterns overlap on their endpoints
51-
(false, 10..20) => {}
53+
(false, 10..20) => {} //~ ERROR multiple patterns overlap on their endpoints
5254
_ => {}
5355
}
5456
match Some(0u8) {

0 commit comments

Comments
 (0)