aboutsummaryrefslogtreecommitdiff
path: root/crates
diff options
context:
space:
mode:
Diffstat (limited to 'crates')
-rw-r--r--crates/hir_ty/src/diagnostics/pattern.rs26
-rw-r--r--crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs165
2 files changed, 182 insertions, 9 deletions
diff --git a/crates/hir_ty/src/diagnostics/pattern.rs b/crates/hir_ty/src/diagnostics/pattern.rs
index 3e90461cc..044506d66 100644
--- a/crates/hir_ty/src/diagnostics/pattern.rs
+++ b/crates/hir_ty/src/diagnostics/pattern.rs
@@ -121,4 +121,30 @@ fn main(v: E) {
121"#, 121"#,
122 ); 122 );
123 } 123 }
124
125 #[test]
126 fn boolean() {
127 check_diagnostics(
128 r#"
129fn main() {
130 match true {
131 true => {}
132 false => {}
133 }
134 match true {
135 true | false => {}
136 }
137 match true {
138 true => {}
139 _ => {}
140 }
141 match true {}
142 //^^^^ Missing match arm
143 match true { true => {} }
144 //^^^^ Missing match arm
145
146}
147"#,
148 );
149 }
124} 150}
diff --git a/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs b/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs
index 3c1811f95..393d99997 100644
--- a/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs
+++ b/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs
@@ -1,12 +1,17 @@
1use std::{
2 cmp::{max, min},
3 iter::once,
4 ops::RangeInclusive,
5};
6
1use hir_def::{ 7use hir_def::{
2 expr::{Pat, PatId, RecordFieldPat}, 8 expr::{Expr, Literal, Pat, PatId, RecordFieldPat},
3 find_path::find_path, 9 find_path::find_path,
4 item_scope::ItemInNs, 10 item_scope::ItemInNs,
5 path::Path, 11 path::Path,
6 type_ref::Mutability, 12 type_ref::Mutability,
7 AttrDefId, EnumVariantId, HasModule, VariantId, 13 AttrDefId, EnumVariantId, HasModule, VariantId,
8}; 14};
9
10use smallvec::{smallvec, SmallVec}; 15use smallvec::{smallvec, SmallVec};
11 16
12use crate::{AdtId, Interner, Scalar, Ty, TyExt, TyKind}; 17use crate::{AdtId, Interner, Scalar, Ty, TyExt, TyKind};
@@ -20,7 +25,7 @@ pub(super) enum ToDo {}
20 25
21#[derive(Clone, Debug, PartialEq, Eq)] 26#[derive(Clone, Debug, PartialEq, Eq)]
22pub(super) struct IntRange { 27pub(super) struct IntRange {
23 range: ToDo, 28 range: RangeInclusive<u128>,
24} 29}
25 30
26impl IntRange { 31impl IntRange {
@@ -36,12 +41,147 @@ impl IntRange {
36 } 41 }
37 42
38 fn is_singleton(&self) -> bool { 43 fn is_singleton(&self) -> bool {
39 todo!() 44 self.range.start() == self.range.end()
45 }
46
47 fn boundaries(&self) -> (u128, u128) {
48 (*self.range.start(), *self.range.end())
49 }
50
51 #[inline]
52 fn from_bool(value: bool) -> IntRange {
53 let val = value as u128;
54 IntRange { range: val..=val }
55 }
56
57 #[inline]
58 fn from_range(cx: &MatchCheckCtx<'_>, lo: u128, hi: u128, scalar_ty: Scalar) -> IntRange {
59 if let Scalar::Bool = scalar_ty {
60 IntRange { range: lo..=hi }
61 } else {
62 todo!()
63 }
64 }
65
66 fn is_subrange(&self, other: &Self) -> bool {
67 other.range.start() <= self.range.start() && self.range.end() <= other.range.end()
68 }
69
70 fn intersection(&self, other: &Self) -> Option<Self> {
71 let (lo, hi) = self.boundaries();
72 let (other_lo, other_hi) = other.boundaries();
73 if lo <= other_hi && other_lo <= hi {
74 Some(IntRange { range: max(lo, other_lo)..=min(hi, other_hi) })
75 } else {
76 None
77 }
40 } 78 }
41 79
42 /// See `Constructor::is_covered_by` 80 /// See `Constructor::is_covered_by`
43 fn is_covered_by(&self, other: &Self) -> bool { 81 fn is_covered_by(&self, other: &Self) -> bool {
44 todo!() 82 if self.intersection(other).is_some() {
83 // Constructor splitting should ensure that all intersections we encounter are actually
84 // inclusions.
85 assert!(self.is_subrange(other));
86 true
87 } else {
88 false
89 }
90 }
91}
92
93/// Represents a border between 2 integers. Because the intervals spanning borders must be able to
94/// cover every integer, we need to be able to represent 2^128 + 1 such borders.
95#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
96enum IntBorder {
97 JustBefore(u128),
98 AfterMax,
99}
100
101/// A range of integers that is partitioned into disjoint subranges. This does constructor
102/// splitting for integer ranges as explained at the top of the file.
103///
104/// This is fed multiple ranges, and returns an output that covers the input, but is split so that
105/// the only intersections between an output range and a seen range are inclusions. No output range
106/// straddles the boundary of one of the inputs.
107///
108/// The following input:
109/// ```
110/// |-------------------------| // `self`
111/// |------| |----------| |----|
112/// |-------| |-------|
113/// ```
114/// would be iterated over as follows:
115/// ```
116/// ||---|--||-|---|---|---|--|
117/// ```
118#[derive(Debug, Clone)]
119struct SplitIntRange {
120 /// The range we are splitting
121 range: IntRange,
122 /// The borders of ranges we have seen. They are all contained within `range`. This is kept
123 /// sorted.
124 borders: Vec<IntBorder>,
125}
126
127impl SplitIntRange {
128 fn new(range: IntRange) -> Self {
129 SplitIntRange { range, borders: Vec::new() }
130 }
131
132 /// Internal use
133 fn to_borders(r: IntRange) -> [IntBorder; 2] {
134 use IntBorder::*;
135 let (lo, hi) = r.boundaries();
136 let lo = JustBefore(lo);
137 let hi = match hi.checked_add(1) {
138 Some(m) => JustBefore(m),
139 None => AfterMax,
140 };
141 [lo, hi]
142 }
143
144 /// Add ranges relative to which we split.
145 fn split(&mut self, ranges: impl Iterator<Item = IntRange>) {
146 let this_range = &self.range;
147 let included_ranges = ranges.filter_map(|r| this_range.intersection(&r));
148 let included_borders = included_ranges.flat_map(|r| {
149 let borders = Self::to_borders(r);
150 once(borders[0]).chain(once(borders[1]))
151 });
152 self.borders.extend(included_borders);
153 self.borders.sort_unstable();
154 }
155
156 /// Iterate over the contained ranges.
157 fn iter(&self) -> impl Iterator<Item = IntRange> + '_ {
158 use IntBorder::*;
159
160 let self_range = Self::to_borders(self.range.clone());
161 // Start with the start of the range.
162 let mut prev_border = self_range[0];
163 self.borders
164 .iter()
165 .copied()
166 // End with the end of the range.
167 .chain(once(self_range[1]))
168 // List pairs of adjacent borders.
169 .map(move |border| {
170 let ret = (prev_border, border);
171 prev_border = border;
172 ret
173 })
174 // Skip duplicates.
175 .filter(|(prev_border, border)| prev_border != border)
176 // Finally, convert to ranges.
177 .map(|(prev_border, border)| {
178 let range = match (prev_border, border) {
179 (JustBefore(n), JustBefore(m)) if n < m => n..=(m - 1),
180 (JustBefore(n), AfterMax) => n..=u128::MAX,
181 _ => unreachable!(), // Ruled out by the sorting and filtering we did
182 };
183 IntRange { range }
184 })
45 } 185 }
46} 186}
47 187
@@ -143,13 +283,16 @@ impl Constructor {
143 VariantId::StructId(_) | VariantId::UnionId(_) => Single, 283 VariantId::StructId(_) | VariantId::UnionId(_) => Single,
144 } 284 }
145 } 285 }
286 &Pat::Lit(expr_id) => match cx.body[expr_id] {
287 Expr::Literal(Literal::Bool(val)) => IntRange(IntRange::from_bool(val)),
288 _ => todo!(),
289 },
146 290
147 Pat::Or(..) => panic!("bug: Or-pattern should have been expanded earlier on."), 291 Pat::Or(..) => panic!("bug: Or-pattern should have been expanded earlier on."),
148 Pat::Missing => todo!("Fail gracefully when there is an error in a pattern"), 292 Pat::Missing => todo!("Fail gracefully when there is an error in a pattern"),
149 pat => todo!("Constructor::from_pat {:?}", pat), 293 pat => todo!("Constructor::from_pat {:?}", pat),
150 // Pat::Range { start, end } => {} 294 // Pat::Range { start, end } => {}
151 // Pat::Slice { prefix, slice, suffix } => {} 295 // Pat::Slice { prefix, slice, suffix } => {}
152 // Pat::Lit(_) => {}
153 // Pat::ConstBlock(_) => {} 296 // Pat::ConstBlock(_) => {}
154 } 297 }
155 } 298 }
@@ -181,7 +324,10 @@ impl Constructor {
181 // Fast-track if the range is trivial. In particular, we don't do the overlapping 324 // Fast-track if the range is trivial. In particular, we don't do the overlapping
182 // ranges check. 325 // ranges check.
183 IntRange(ctor_range) if !ctor_range.is_singleton() => { 326 IntRange(ctor_range) if !ctor_range.is_singleton() => {
184 todo!("Constructor::split IntRange") 327 let mut split_range = SplitIntRange::new(ctor_range.clone());
328 let int_ranges = ctors.filter_map(|ctor| ctor.as_int_range());
329 split_range.split(int_ranges.cloned());
330 split_range.iter().map(IntRange).collect()
185 } 331 }
186 Slice(_) => todo!("Constructor::split Slice"), 332 Slice(_) => todo!("Constructor::split Slice"),
187 // Any other constructor can be used unchanged. 333 // Any other constructor can be used unchanged.
@@ -282,7 +428,8 @@ pub(super) struct SplitWildcard {
282impl SplitWildcard { 428impl SplitWildcard {
283 pub(super) fn new(pcx: PatCtxt<'_>) -> Self { 429 pub(super) fn new(pcx: PatCtxt<'_>) -> Self {
284 let cx = pcx.cx; 430 let cx = pcx.cx;
285 // let make_range = |start, end| IntRange(todo!()); 431 let make_range =
432 |start, end, scalar| IntRange(IntRange::from_range(cx, start, end, scalar));
286 433
287 // This determines the set of all possible constructors for the type `pcx.ty`. For numbers, 434 // This determines the set of all possible constructors for the type `pcx.ty`. For numbers,
288 // arrays and slices we use ranges and variable-length slices when appropriate. 435 // arrays and slices we use ranges and variable-length slices when appropriate.
@@ -293,7 +440,7 @@ impl SplitWildcard {
293 // Invariant: this is empty if and only if the type is uninhabited (as determined by 440 // Invariant: this is empty if and only if the type is uninhabited (as determined by
294 // `cx.is_uninhabited()`). 441 // `cx.is_uninhabited()`).
295 let all_ctors = match pcx.ty.kind(&Interner) { 442 let all_ctors = match pcx.ty.kind(&Interner) {
296 TyKind::Scalar(Scalar::Bool) => todo!(), 443 TyKind::Scalar(Scalar::Bool) => smallvec![make_range(0, 1, Scalar::Bool)],
297 // TyKind::Array(..) if ... => todo!(), 444 // TyKind::Array(..) if ... => todo!(),
298 TyKind::Array(..) | TyKind::Slice(..) => todo!(), 445 TyKind::Array(..) | TyKind::Slice(..) => todo!(),
299 &TyKind::Adt(AdtId(hir_def::AdtId::EnumId(enum_id)), ref _substs) => { 446 &TyKind::Adt(AdtId(hir_def::AdtId::EnumId(enum_id)), ref _substs) => {