]>
Commit | Line | Data |
---|---|---|
e9174d1e SL |
1 | // Testing candidates |
2 | // | |
3 | // After candidates have been simplified, the only match pairs that | |
4 | // remain are those that require some sort of test. The functions here | |
5 | // identify what tests are needed, perform the tests, and then filter | |
6 | // the candidates based on the result. | |
7 | ||
9fa01778 | 8 | use crate::build::matches::{Candidate, MatchPair, Test, TestKind}; |
dfeec247 | 9 | use crate::build::Builder; |
3dfed10e XL |
10 | use crate::thir::pattern::compare_const_vals; |
11 | use crate::thir::*; | |
12 | use rustc_data_structures::fx::FxIndexMap; | |
13 | use rustc_hir::{LangItem, RangeEnd}; | |
dfeec247 | 14 | use rustc_index::bit_set::BitSet; |
ba9703b0 XL |
15 | use rustc_middle::mir::*; |
16 | use rustc_middle::ty::util::IntTypeExt; | |
17 | use rustc_middle::ty::{self, adjustment::PointerCast, Ty}; | |
dfeec247 | 18 | use rustc_span::symbol::sym; |
ba9703b0 | 19 | use rustc_target::abi::VariantIdx; |
dc9dc135 | 20 | |
3157f602 | 21 | use std::cmp::Ordering; |
e9174d1e | 22 | |
dc9dc135 | 23 | impl<'a, 'tcx> Builder<'a, 'tcx> { |
e9174d1e SL |
24 | /// Identifies what test is needed to decide if `match_pair` is applicable. |
25 | /// | |
a1dfa0c6 | 26 | /// It is a bug to call this with a simplifiable pattern. |
74b04a01 | 27 | pub(super) fn test<'pat>(&mut self, match_pair: &MatchPair<'pat, 'tcx>) -> Test<'tcx> { |
92a42be0 | 28 | match *match_pair.pattern.kind { |
dfeec247 XL |
29 | PatKind::Variant { ref adt_def, substs: _, variant_index: _, subpatterns: _ } => Test { |
30 | span: match_pair.pattern.span, | |
31 | kind: TestKind::Switch { | |
32 | adt_def, | |
33 | variants: BitSet::new_empty(adt_def.variants.len()), | |
34 | }, | |
35 | }, | |
e9174d1e | 36 | |
e74abb32 | 37 | PatKind::Constant { .. } if is_switch_ty(match_pair.pattern.ty) => { |
9fa01778 XL |
38 | // For integers, we use a `SwitchInt` match, which allows |
39 | // us to handle more cases. | |
92a42be0 SL |
40 | Test { |
41 | span: match_pair.pattern.span, | |
42 | kind: TestKind::SwitchInt { | |
43 | switch_ty: match_pair.pattern.ty, | |
44 | ||
45 | // these maps are empty to start; cases are | |
46 | // added below in add_cases_to_switch | |
3dfed10e | 47 | options: Default::default(), |
dfeec247 | 48 | }, |
92a42be0 SL |
49 | } |
50 | } | |
51 | ||
dfeec247 XL |
52 | PatKind::Constant { value } => Test { |
53 | span: match_pair.pattern.span, | |
54 | kind: TestKind::Eq { value, ty: match_pair.pattern.ty.clone() }, | |
55 | }, | |
e9174d1e | 56 | |
e74abb32 | 57 | PatKind::Range(range) => { |
e1599b0c XL |
58 | assert_eq!(range.lo.ty, match_pair.pattern.ty); |
59 | assert_eq!(range.hi.ty, match_pair.pattern.ty); | |
dfeec247 | 60 | Test { span: match_pair.pattern.span, kind: TestKind::Range(range) } |
e9174d1e SL |
61 | } |
62 | ||
e74abb32 | 63 | PatKind::Slice { ref prefix, ref slice, ref suffix } => { |
e9174d1e | 64 | let len = prefix.len() + suffix.len(); |
dfeec247 | 65 | let op = if slice.is_some() { BinOp::Ge } else { BinOp::Eq }; |
74b04a01 | 66 | Test { span: match_pair.pattern.span, kind: TestKind::Len { len: len as u64, op } } |
e9174d1e SL |
67 | } |
68 | ||
74b04a01 | 69 | PatKind::Or { .. } => bug!("or-patterns should have already been handled"), |
dfeec247 XL |
70 | |
71 | PatKind::AscribeUserType { .. } | |
72 | | PatKind::Array { .. } | |
73 | | PatKind::Wild | |
74 | | PatKind::Binding { .. } | |
75 | | PatKind::Leaf { .. } | |
76 | | PatKind::Deref { .. } => self.error_simplifyable(match_pair), | |
e9174d1e SL |
77 | } |
78 | } | |
79 | ||
74b04a01 | 80 | pub(super) fn add_cases_to_switch<'pat>( |
dfeec247 XL |
81 | &mut self, |
82 | test_place: &Place<'tcx>, | |
83 | candidate: &Candidate<'pat, 'tcx>, | |
84 | switch_ty: Ty<'tcx>, | |
3dfed10e | 85 | options: &mut FxIndexMap<&'tcx ty::Const<'tcx>, u128>, |
dfeec247 | 86 | ) -> bool { |
ff7c6d11 | 87 | let match_pair = match candidate.match_pairs.iter().find(|mp| mp.place == *test_place) { |
92a42be0 | 88 | Some(match_pair) => match_pair, |
dfeec247 XL |
89 | _ => { |
90 | return false; | |
91 | } | |
92a42be0 SL |
92 | }; |
93 | ||
94 | match *match_pair.pattern.kind { | |
e74abb32 | 95 | PatKind::Constant { value } => { |
3dfed10e XL |
96 | options.entry(value).or_insert_with(|| { |
97 | value.eval_bits(self.hir.tcx(), self.hir.param_env, switch_ty) | |
dfeec247 | 98 | }); |
92a42be0 SL |
99 | true |
100 | } | |
e74abb32 | 101 | PatKind::Variant { .. } => { |
3157f602 XL |
102 | panic!("you should have called add_variants_to_switch instead!"); |
103 | } | |
e74abb32 | 104 | PatKind::Range(range) => { |
0731742a | 105 | // Check that none of the switch values are in the range. |
3dfed10e | 106 | self.values_not_contained_in_range(range, options).unwrap_or(false) |
0731742a | 107 | } |
dfeec247 XL |
108 | PatKind::Slice { .. } |
109 | | PatKind::Array { .. } | |
110 | | PatKind::Wild | |
111 | | PatKind::Or { .. } | |
112 | | PatKind::Binding { .. } | |
113 | | PatKind::AscribeUserType { .. } | |
114 | | PatKind::Leaf { .. } | |
115 | | PatKind::Deref { .. } => { | |
92a42be0 SL |
116 | // don't know how to add these patterns to a switch |
117 | false | |
118 | } | |
119 | } | |
120 | } | |
121 | ||
74b04a01 | 122 | pub(super) fn add_variants_to_switch<'pat>( |
dfeec247 XL |
123 | &mut self, |
124 | test_place: &Place<'tcx>, | |
125 | candidate: &Candidate<'pat, 'tcx>, | |
126 | variants: &mut BitSet<VariantIdx>, | |
127 | ) -> bool { | |
ff7c6d11 | 128 | let match_pair = match candidate.match_pairs.iter().find(|mp| mp.place == *test_place) { |
3157f602 | 129 | Some(match_pair) => match_pair, |
dfeec247 XL |
130 | _ => { |
131 | return false; | |
132 | } | |
3157f602 XL |
133 | }; |
134 | ||
135 | match *match_pair.pattern.kind { | |
dfeec247 | 136 | PatKind::Variant { adt_def: _, variant_index, .. } => { |
3157f602 XL |
137 | // We have a pattern testing for variant `variant_index` |
138 | // set the corresponding index to true | |
139 | variants.insert(variant_index); | |
140 | true | |
141 | } | |
142 | _ => { | |
143 | // don't know how to add these patterns to a switch | |
144 | false | |
145 | } | |
146 | } | |
147 | } | |
148 | ||
74b04a01 | 149 | pub(super) fn perform_test( |
dc9dc135 XL |
150 | &mut self, |
151 | block: BasicBlock, | |
74b04a01 | 152 | place: Place<'tcx>, |
dc9dc135 XL |
153 | test: &Test<'tcx>, |
154 | make_target_blocks: impl FnOnce(&mut Self) -> Vec<BasicBlock>, | |
155 | ) { | |
dfeec247 XL |
156 | debug!( |
157 | "perform_test({:?}, {:?}: {:?}, {:?})", | |
158 | block, | |
159 | place, | |
160 | place.ty(&self.local_decls, self.hir.tcx()), | |
161 | test | |
162 | ); | |
dc9dc135 | 163 | |
3157f602 | 164 | let source_info = self.source_info(test.span); |
92a42be0 | 165 | match test.kind { |
3157f602 | 166 | TestKind::Switch { adt_def, ref variants } => { |
dc9dc135 | 167 | let target_blocks = make_target_blocks(self); |
8bb4bdeb | 168 | // Variants is a BitVec of indexes into adt_def.variants. |
ff7c6d11 | 169 | let num_enum_variants = adt_def.variants.len(); |
dc9dc135 XL |
170 | debug_assert_eq!(target_blocks.len(), num_enum_variants + 1); |
171 | let otherwise_block = *target_blocks.last().unwrap(); | |
8bb4bdeb | 172 | let tcx = self.hir.tcx(); |
29967ef6 XL |
173 | let switch_targets = SwitchTargets::new( |
174 | adt_def.discriminants(tcx).filter_map(|(idx, discr)| { | |
175 | if variants.contains(idx) { | |
176 | debug_assert_ne!( | |
177 | target_blocks[idx.index()], | |
178 | otherwise_block, | |
179 | "no canididates for tested discriminant: {:?}", | |
180 | discr, | |
181 | ); | |
182 | Some((discr.val, target_blocks[idx.index()])) | |
183 | } else { | |
184 | debug_assert_eq!( | |
185 | target_blocks[idx.index()], | |
186 | otherwise_block, | |
187 | "found canididates for untested discriminant: {:?}", | |
188 | discr, | |
189 | ); | |
190 | None | |
191 | } | |
192 | }), | |
193 | otherwise_block, | |
dfeec247 | 194 | ); |
29967ef6 | 195 | debug!("num_enum_variants: {}, variants: {:?}", num_enum_variants, variants); |
8bb4bdeb | 196 | let discr_ty = adt_def.repr.discr_type().to_ty(tcx); |
cc61c64b | 197 | let discr = self.temp(discr_ty, test.span); |
ba9703b0 | 198 | self.cfg.push_assign(block, source_info, discr, Rvalue::Discriminant(place)); |
dfeec247 XL |
199 | self.cfg.terminate( |
200 | block, | |
201 | source_info, | |
202 | TerminatorKind::SwitchInt { | |
203 | discr: Operand::Move(discr), | |
204 | switch_ty: discr_ty, | |
29967ef6 | 205 | targets: switch_targets, |
dfeec247 XL |
206 | }, |
207 | ); | |
e9174d1e SL |
208 | } |
209 | ||
3dfed10e | 210 | TestKind::SwitchInt { switch_ty, ref options } => { |
dc9dc135 | 211 | let target_blocks = make_target_blocks(self); |
1b1a35ee | 212 | let terminator = if *switch_ty.kind() == ty::Bool { |
74b04a01 | 213 | assert!(!options.is_empty() && options.len() <= 2); |
dc9dc135 XL |
214 | if let [first_bb, second_bb] = *target_blocks { |
215 | let (true_bb, false_bb) = match options[0] { | |
216 | 1 => (first_bb, second_bb), | |
217 | 0 => (second_bb, first_bb), | |
dfeec247 | 218 | v => span_bug!(test.span, "expected boolean value but got {:?}", v), |
dc9dc135 | 219 | }; |
74b04a01 | 220 | TerminatorKind::if_(self.hir.tcx(), Operand::Copy(place), true_bb, false_bb) |
dc9dc135 XL |
221 | } else { |
222 | bug!("`TestKind::SwitchInt` on `bool` should have two targets") | |
223 | } | |
8bb4bdeb | 224 | } else { |
dc9dc135 XL |
225 | // The switch may be inexhaustive so we have a catch all block |
226 | debug_assert_eq!(options.len() + 1, target_blocks.len()); | |
29967ef6 XL |
227 | let otherwise_block = *target_blocks.last().unwrap(); |
228 | let switch_targets = SwitchTargets::new( | |
229 | options.values().copied().zip(target_blocks), | |
230 | otherwise_block, | |
231 | ); | |
dc9dc135 | 232 | TerminatorKind::SwitchInt { |
74b04a01 | 233 | discr: Operand::Copy(place), |
3b2f2976 | 234 | switch_ty, |
29967ef6 | 235 | targets: switch_targets, |
dc9dc135 | 236 | } |
3157f602 | 237 | }; |
8bb4bdeb | 238 | self.cfg.terminate(block, source_info, terminator); |
92a42be0 SL |
239 | } |
240 | ||
dc9dc135 | 241 | TestKind::Eq { value, ty } => { |
0531ce1d | 242 | if !ty.is_scalar() { |
dc9dc135 XL |
243 | // Use `PartialEq::eq` instead of `BinOp::Eq` |
244 | // (the binop can only handle primitives) | |
245 | self.non_scalar_compare( | |
246 | block, | |
247 | make_target_blocks, | |
248 | source_info, | |
249 | value, | |
250 | place, | |
0531ce1d | 251 | ty, |
dc9dc135 | 252 | ); |
29967ef6 XL |
253 | } else if let [success, fail] = *make_target_blocks(self) { |
254 | assert_eq!(value.ty, ty); | |
255 | let expect = self.literal_operand(test.span, value); | |
256 | let val = Operand::Copy(place); | |
257 | self.compare(block, success, fail, source_info, BinOp::Eq, expect, val); | |
54a0048b | 258 | } else { |
29967ef6 | 259 | bug!("`TestKind::Eq` should have two target blocks"); |
54a0048b | 260 | } |
e9174d1e SL |
261 | } |
262 | ||
e74abb32 | 263 | TestKind::Range(PatRange { ref lo, ref hi, ref end }) => { |
dc9dc135 XL |
264 | let lower_bound_success = self.cfg.start_new_block(); |
265 | let target_blocks = make_target_blocks(self); | |
266 | ||
9cc50fc6 | 267 | // Test `val` by computing `lo <= val && val <= hi`, using primitive comparisons. |
e1599b0c XL |
268 | let lo = self.literal_operand(test.span, lo); |
269 | let hi = self.literal_operand(test.span, hi); | |
74b04a01 | 270 | let val = Operand::Copy(place); |
e9174d1e | 271 | |
dc9dc135 XL |
272 | if let [success, fail] = *target_blocks { |
273 | self.compare( | |
274 | block, | |
275 | lower_bound_success, | |
276 | fail, | |
277 | source_info, | |
278 | BinOp::Le, | |
279 | lo, | |
280 | val.clone(), | |
281 | ); | |
282 | let op = match *end { | |
283 | RangeEnd::Included => BinOp::Le, | |
284 | RangeEnd::Excluded => BinOp::Lt, | |
285 | }; | |
286 | self.compare(lower_bound_success, success, fail, source_info, op, val, hi); | |
287 | } else { | |
288 | bug!("`TestKind::Range` should have two target blocks"); | |
289 | } | |
e9174d1e SL |
290 | } |
291 | ||
292 | TestKind::Len { len, op } => { | |
dc9dc135 XL |
293 | let target_blocks = make_target_blocks(self); |
294 | ||
295 | let usize_ty = self.hir.usize_ty(); | |
296 | let actual = self.temp(usize_ty, test.span); | |
e9174d1e | 297 | |
ff7c6d11 | 298 | // actual = len(place) |
ba9703b0 | 299 | self.cfg.push_assign(block, source_info, actual, Rvalue::Len(place)); |
e9174d1e SL |
300 | |
301 | // expected = <N> | |
3157f602 | 302 | let expected = self.push_usize(block, source_info, len); |
e9174d1e | 303 | |
dc9dc135 XL |
304 | if let [true_bb, false_bb] = *target_blocks { |
305 | // result = actual == expected OR result = actual < expected | |
306 | // branch based on result | |
307 | self.compare( | |
308 | block, | |
309 | true_bb, | |
310 | false_bb, | |
311 | source_info, | |
312 | op, | |
313 | Operand::Move(actual), | |
314 | Operand::Move(expected), | |
315 | ); | |
316 | } else { | |
317 | bug!("`TestKind::Len` should have two target blocks"); | |
318 | } | |
e9174d1e SL |
319 | } |
320 | } | |
321 | } | |
322 | ||
dc9dc135 XL |
323 | /// Compare using the provided built-in comparison operator |
324 | fn compare( | |
325 | &mut self, | |
326 | block: BasicBlock, | |
327 | success_block: BasicBlock, | |
328 | fail_block: BasicBlock, | |
329 | source_info: SourceInfo, | |
330 | op: BinOp, | |
331 | left: Operand<'tcx>, | |
332 | right: Operand<'tcx>, | |
333 | ) { | |
e9174d1e | 334 | let bool_ty = self.hir.bool_ty(); |
dc9dc135 | 335 | let result = self.temp(bool_ty, source_info.span); |
9cc50fc6 SL |
336 | |
337 | // result = op(left, right) | |
ba9703b0 | 338 | self.cfg.push_assign(block, source_info, result, Rvalue::BinaryOp(op, left, right)); |
9cc50fc6 SL |
339 | |
340 | // branch based on result | |
dc9dc135 XL |
341 | self.cfg.terminate( |
342 | block, | |
343 | source_info, | |
dfeec247 | 344 | TerminatorKind::if_(self.hir.tcx(), Operand::Move(result), success_block, fail_block), |
dc9dc135 XL |
345 | ); |
346 | } | |
347 | ||
348 | /// Compare two `&T` values using `<T as std::compare::PartialEq>::eq` | |
349 | fn non_scalar_compare( | |
350 | &mut self, | |
351 | block: BasicBlock, | |
352 | make_target_blocks: impl FnOnce(&mut Self) -> Vec<BasicBlock>, | |
353 | source_info: SourceInfo, | |
354 | value: &'tcx ty::Const<'tcx>, | |
74b04a01 | 355 | place: Place<'tcx>, |
dc9dc135 XL |
356 | mut ty: Ty<'tcx>, |
357 | ) { | |
e1599b0c | 358 | let mut expect = self.literal_operand(source_info.span, value); |
74b04a01 | 359 | let mut val = Operand::Copy(place); |
dc9dc135 XL |
360 | |
361 | // If we're using `b"..."` as a pattern, we need to insert an | |
362 | // unsizing coercion, as the byte string has the type `&[u8; N]`. | |
363 | // | |
364 | // We want to do this even when the scrutinee is a reference to an | |
365 | // array, so we can call `<[u8]>::eq` rather than having to find an | |
366 | // `<[u8; N]>::eq`. | |
1b1a35ee XL |
367 | let unsize = |ty: Ty<'tcx>| match ty.kind() { |
368 | ty::Ref(region, rty, _) => match rty.kind() { | |
dc9dc135 XL |
369 | ty::Array(inner_ty, n) => Some((region, inner_ty, n)), |
370 | _ => None, | |
371 | }, | |
372 | _ => None, | |
373 | }; | |
374 | let opt_ref_ty = unsize(ty); | |
375 | let opt_ref_test_ty = unsize(value.ty); | |
376 | match (opt_ref_ty, opt_ref_test_ty) { | |
377 | // nothing to do, neither is an array | |
dfeec247 XL |
378 | (None, None) => {} |
379 | (Some((region, elem_ty, _)), _) | (None, Some((region, elem_ty, _))) => { | |
dc9dc135 XL |
380 | let tcx = self.hir.tcx(); |
381 | // make both a slice | |
382 | ty = tcx.mk_imm_ref(region, tcx.mk_slice(elem_ty)); | |
383 | if opt_ref_ty.is_some() { | |
384 | let temp = self.temp(ty, source_info.span); | |
385 | self.cfg.push_assign( | |
dfeec247 XL |
386 | block, |
387 | source_info, | |
ba9703b0 | 388 | temp, |
dfeec247 | 389 | Rvalue::Cast(CastKind::Pointer(PointerCast::Unsize), val, ty), |
dc9dc135 XL |
390 | ); |
391 | val = Operand::Move(temp); | |
392 | } | |
393 | if opt_ref_test_ty.is_some() { | |
394 | let slice = self.temp(ty, source_info.span); | |
395 | self.cfg.push_assign( | |
dfeec247 XL |
396 | block, |
397 | source_info, | |
ba9703b0 | 398 | slice, |
dfeec247 | 399 | Rvalue::Cast(CastKind::Pointer(PointerCast::Unsize), expect, ty), |
dc9dc135 XL |
400 | ); |
401 | expect = Operand::Move(slice); | |
402 | } | |
dfeec247 | 403 | } |
dc9dc135 XL |
404 | } |
405 | ||
1b1a35ee | 406 | let deref_ty = match *ty.kind() { |
dc9dc135 XL |
407 | ty::Ref(_, deref_ty, _) => deref_ty, |
408 | _ => bug!("non_scalar_compare called on non-reference type: {}", ty), | |
409 | }; | |
410 | ||
3dfed10e | 411 | let eq_def_id = self.hir.tcx().require_lang_item(LangItem::PartialEq, None); |
e1599b0c | 412 | let method = self.hir.trait_method(eq_def_id, sym::eq, deref_ty, &[deref_ty.into()]); |
dc9dc135 XL |
413 | |
414 | let bool_ty = self.hir.bool_ty(); | |
415 | let eq_result = self.temp(bool_ty, source_info.span); | |
416 | let eq_block = self.cfg.start_new_block(); | |
dfeec247 XL |
417 | self.cfg.terminate( |
418 | block, | |
419 | source_info, | |
420 | TerminatorKind::Call { | |
421 | func: Operand::Constant(box Constant { | |
422 | span: source_info.span, | |
423 | ||
424 | // FIXME(#54571): This constant comes from user input (a | |
425 | // constant in a pattern). Are there forms where users can add | |
426 | // type annotations here? For example, an associated constant? | |
427 | // Need to experiment. | |
428 | user_ty: None, | |
429 | ||
430 | literal: method, | |
431 | }), | |
432 | args: vec![val, expect], | |
433 | destination: Some((eq_result, eq_block)), | |
29967ef6 | 434 | cleanup: None, |
dfeec247 | 435 | from_hir_call: false, |
3dfed10e | 436 | fn_span: source_info.span, |
dfeec247 XL |
437 | }, |
438 | ); | |
29967ef6 | 439 | self.diverge_from(block); |
dc9dc135 XL |
440 | |
441 | if let [success_block, fail_block] = *make_target_blocks(self) { | |
442 | // check the result | |
443 | self.cfg.terminate( | |
444 | eq_block, | |
445 | source_info, | |
446 | TerminatorKind::if_( | |
447 | self.hir.tcx(), | |
448 | Operand::Move(eq_result), | |
449 | success_block, | |
450 | fail_block, | |
451 | ), | |
452 | ); | |
453 | } else { | |
454 | bug!("`TestKind::Eq` should have two target blocks") | |
455 | } | |
e9174d1e SL |
456 | } |
457 | ||
9fa01778 XL |
458 | /// Given that we are performing `test` against `test_place`, this job |
459 | /// sorts out what the status of `candidate` will be after the test. See | |
460 | /// `test_candidates` for the usage of this function. The returned index is | |
60c5eb7d | 461 | /// the index that this candidate should be placed in the |
9fa01778 XL |
462 | /// `target_candidates` vec. The candidate may be modified to update its |
463 | /// `match_pairs`. | |
e9174d1e | 464 | /// |
9fa01778 XL |
465 | /// So, for example, if this candidate is `x @ Some(P0)` and the `Test` is |
466 | /// a variant test, then we would modify the candidate to be `(x as | |
467 | /// Option).0 @ P0` and return the index corresponding to the variant | |
468 | /// `Some`. | |
92a42be0 | 469 | /// |
9fa01778 XL |
470 | /// However, in some cases, the test may just not be relevant to candidate. |
471 | /// For example, suppose we are testing whether `foo.x == 22`, but in one | |
472 | /// match arm we have `Foo { x: _, ... }`... in that case, the test for | |
473 | /// what value `x` has has no particular relevance to this candidate. In | |
474 | /// such cases, this function just returns None without doing anything. | |
475 | /// This is used by the overall `match_candidates` algorithm to structure | |
476 | /// the match as a whole. See `match_candidates` for more details. | |
92a42be0 | 477 | /// |
9fa01778 XL |
478 | /// FIXME(#29623). In some cases, we have some tricky choices to make. for |
479 | /// example, if we are testing that `x == 22`, but the candidate is `x @ | |
480 | /// 13..55`, what should we do? In the event that the test is true, we know | |
481 | /// that the candidate applies, but in the event of false, we don't know | |
482 | /// that it *doesn't* apply. For now, we return false, indicate that the | |
483 | /// test does not apply to this candidate, but it might be we can get | |
92a42be0 | 484 | /// tighter match code if we do something a bit different. |
74b04a01 | 485 | pub(super) fn sort_candidate<'pat>( |
9fa01778 XL |
486 | &mut self, |
487 | test_place: &Place<'tcx>, | |
488 | test: &Test<'tcx>, | |
489 | candidate: &mut Candidate<'pat, 'tcx>, | |
490 | ) -> Option<usize> { | |
ff7c6d11 | 491 | // Find the match_pair for this place (if any). At present, |
92a42be0 SL |
492 | // afaik, there can be at most one. (In the future, if we |
493 | // adopted a more general `@` operator, there might be more | |
494 | // than one, but it'd be very unusual to have two sides that | |
495 | // both require tests; you'd expect one side to be simplified | |
496 | // away.) | |
dfeec247 XL |
497 | let (match_pair_index, match_pair) = |
498 | candidate.match_pairs.iter().enumerate().find(|&(_, mp)| mp.place == *test_place)?; | |
92a42be0 | 499 | |
3157f602 | 500 | match (&test.kind, &*match_pair.pattern.kind) { |
92a42be0 SL |
501 | // If we are performing a variant switch, then this |
502 | // informs variant patterns, but nothing else. | |
dfeec247 XL |
503 | ( |
504 | &TestKind::Switch { adt_def: tested_adt_def, .. }, | |
505 | &PatKind::Variant { adt_def, variant_index, ref subpatterns, .. }, | |
506 | ) => { | |
3157f602 | 507 | assert_eq!(adt_def, tested_adt_def); |
dfeec247 XL |
508 | self.candidate_after_variant_switch( |
509 | match_pair_index, | |
510 | adt_def, | |
511 | variant_index, | |
512 | subpatterns, | |
513 | candidate, | |
514 | ); | |
9fa01778 | 515 | Some(variant_index.as_usize()) |
e9174d1e | 516 | } |
9fa01778 XL |
517 | |
518 | (&TestKind::Switch { .. }, _) => None, | |
e9174d1e | 519 | |
92a42be0 SL |
520 | // If we are performing a switch over integers, then this informs integer |
521 | // equality, but nothing else. | |
522 | // | |
e74abb32 | 523 | // FIXME(#29623) we could use PatKind::Range to rule |
92a42be0 | 524 | // things out here, in some cases. |
dfeec247 | 525 | ( |
3dfed10e | 526 | &TestKind::SwitchInt { switch_ty: _, ref options }, |
dfeec247 XL |
527 | &PatKind::Constant { ref value }, |
528 | ) if is_switch_ty(match_pair.pattern.ty) => { | |
3dfed10e | 529 | let index = options.get_index_of(value).unwrap(); |
9fa01778 XL |
530 | self.candidate_without_match_pair(match_pair_index, candidate); |
531 | Some(index) | |
3157f602 | 532 | } |
0731742a | 533 | |
3dfed10e | 534 | (&TestKind::SwitchInt { switch_ty: _, ref options }, &PatKind::Range(range)) => { |
dfeec247 | 535 | let not_contained = |
3dfed10e | 536 | self.values_not_contained_in_range(range, options).unwrap_or(false); |
0731742a XL |
537 | |
538 | if not_contained { | |
539 | // No switch values are contained in the pattern range, | |
540 | // so the pattern can be matched only if this test fails. | |
541 | let otherwise = options.len(); | |
9fa01778 | 542 | Some(otherwise) |
0731742a | 543 | } else { |
9fa01778 | 544 | None |
0731742a XL |
545 | } |
546 | } | |
547 | ||
9fa01778 | 548 | (&TestKind::SwitchInt { .. }, _) => None, |
3157f602 | 549 | |
dfeec247 XL |
550 | ( |
551 | &TestKind::Len { len: test_len, op: BinOp::Eq }, | |
552 | &PatKind::Slice { ref prefix, ref slice, ref suffix }, | |
553 | ) => { | |
3157f602 XL |
554 | let pat_len = (prefix.len() + suffix.len()) as u64; |
555 | match (test_len.cmp(&pat_len), slice) { | |
556 | (Ordering::Equal, &None) => { | |
557 | // on true, min_len = len = $actual_length, | |
558 | // on false, len != $actual_length | |
dfeec247 XL |
559 | self.candidate_after_slice_test( |
560 | match_pair_index, | |
561 | candidate, | |
562 | prefix, | |
563 | slice.as_ref(), | |
564 | suffix, | |
565 | ); | |
9fa01778 | 566 | Some(0) |
92a42be0 | 567 | } |
3157f602 XL |
568 | (Ordering::Less, _) => { |
569 | // test_len < pat_len. If $actual_len = test_len, | |
570 | // then $actual_len < pat_len and we don't have | |
571 | // enough elements. | |
9fa01778 | 572 | Some(1) |
3157f602 | 573 | } |
ba9703b0 | 574 | (Ordering::Equal | Ordering::Greater, &Some(_)) => { |
3157f602 XL |
575 | // This can match both if $actual_len = test_len >= pat_len, |
576 | // and if $actual_len > test_len. We can't advance. | |
9fa01778 | 577 | None |
92a42be0 | 578 | } |
3157f602 XL |
579 | (Ordering::Greater, &None) => { |
580 | // test_len != pat_len, so if $actual_len = test_len, then | |
581 | // $actual_len != pat_len. | |
9fa01778 | 582 | Some(1) |
3157f602 | 583 | } |
e9174d1e | 584 | } |
e9174d1e SL |
585 | } |
586 | ||
dfeec247 XL |
587 | ( |
588 | &TestKind::Len { len: test_len, op: BinOp::Ge }, | |
589 | &PatKind::Slice { ref prefix, ref slice, ref suffix }, | |
590 | ) => { | |
3157f602 XL |
591 | // the test is `$actual_len >= test_len` |
592 | let pat_len = (prefix.len() + suffix.len()) as u64; | |
593 | match (test_len.cmp(&pat_len), slice) { | |
dfeec247 | 594 | (Ordering::Equal, &Some(_)) => { |
3157f602 XL |
595 | // $actual_len >= test_len = pat_len, |
596 | // so we can match. | |
dfeec247 XL |
597 | self.candidate_after_slice_test( |
598 | match_pair_index, | |
599 | candidate, | |
600 | prefix, | |
601 | slice.as_ref(), | |
602 | suffix, | |
603 | ); | |
9fa01778 | 604 | Some(0) |
3157f602 XL |
605 | } |
606 | (Ordering::Less, _) | (Ordering::Equal, &None) => { | |
607 | // test_len <= pat_len. If $actual_len < test_len, | |
608 | // then it is also < pat_len, so the test passing is | |
609 | // necessary (but insufficient). | |
9fa01778 | 610 | Some(0) |
54a0048b | 611 | } |
3157f602 XL |
612 | (Ordering::Greater, &None) => { |
613 | // test_len > pat_len. If $actual_len >= test_len > pat_len, | |
614 | // then we know we won't have a match. | |
9fa01778 | 615 | Some(1) |
3157f602 XL |
616 | } |
617 | (Ordering::Greater, &Some(_)) => { | |
618 | // test_len < pat_len, and is therefore less | |
619 | // strict. This can still go both ways. | |
9fa01778 | 620 | None |
3157f602 | 621 | } |
54a0048b SL |
622 | } |
623 | } | |
624 | ||
dfeec247 | 625 | (&TestKind::Range(test), &PatKind::Range(pat)) => { |
0731742a | 626 | if test == pat { |
dfeec247 | 627 | self.candidate_without_match_pair(match_pair_index, candidate); |
9fa01778 | 628 | return Some(0); |
0731742a XL |
629 | } |
630 | ||
631 | let no_overlap = (|| { | |
dfeec247 | 632 | use rustc_hir::RangeEnd::*; |
0731742a | 633 | use std::cmp::Ordering::*; |
0731742a | 634 | |
0731742a XL |
635 | let tcx = self.hir.tcx(); |
636 | ||
e1599b0c XL |
637 | let test_ty = test.lo.ty; |
638 | let lo = compare_const_vals(tcx, test.lo, pat.hi, self.hir.param_env, test_ty)?; | |
639 | let hi = compare_const_vals(tcx, test.hi, pat.lo, self.hir.param_env, test_ty)?; | |
0731742a XL |
640 | |
641 | match (test.end, pat.end, lo, hi) { | |
642 | // pat < test | |
643 | (_, _, Greater, _) | | |
644 | (_, Excluded, Equal, _) | | |
645 | // pat > test | |
646 | (_, _, _, Less) | | |
647 | (Excluded, _, _, Equal) => Some(true), | |
648 | _ => Some(false), | |
649 | } | |
650 | })(); | |
651 | ||
60c5eb7d | 652 | if let Some(true) = no_overlap { |
0731742a XL |
653 | // Testing range does not overlap with pattern range, |
654 | // so the pattern can be matched only if this test fails. | |
9fa01778 | 655 | Some(1) |
0731742a | 656 | } else { |
9fa01778 | 657 | None |
0731742a XL |
658 | } |
659 | } | |
660 | ||
e74abb32 | 661 | (&TestKind::Range(range), &PatKind::Constant { value }) => { |
60c5eb7d | 662 | if let Some(false) = self.const_range_contains(range, value) { |
0731742a XL |
663 | // `value` is not contained in the testing range, |
664 | // so `value` can be matched only if this test fails. | |
9fa01778 | 665 | Some(1) |
0731742a | 666 | } else { |
9fa01778 | 667 | None |
0731742a XL |
668 | } |
669 | } | |
670 | ||
9fa01778 | 671 | (&TestKind::Range { .. }, _) => None, |
0731742a | 672 | |
ba9703b0 | 673 | (&TestKind::Eq { .. } | &TestKind::Len { .. }, _) => { |
92a42be0 SL |
674 | // These are all binary tests. |
675 | // | |
676 | // FIXME(#29623) we can be more clever here | |
677 | let pattern_test = self.test(&match_pair); | |
678 | if pattern_test.kind == test.kind { | |
9fa01778 XL |
679 | self.candidate_without_match_pair(match_pair_index, candidate); |
680 | Some(0) | |
e9174d1e | 681 | } else { |
9fa01778 | 682 | None |
e9174d1e SL |
683 | } |
684 | } | |
92a42be0 SL |
685 | } |
686 | } | |
e9174d1e | 687 | |
9fa01778 XL |
688 | fn candidate_without_match_pair( |
689 | &mut self, | |
690 | match_pair_index: usize, | |
691 | candidate: &mut Candidate<'_, 'tcx>, | |
692 | ) { | |
693 | candidate.match_pairs.remove(match_pair_index); | |
92a42be0 | 694 | } |
e9174d1e | 695 | |
dfeec247 XL |
696 | fn candidate_after_slice_test<'pat>( |
697 | &mut self, | |
698 | match_pair_index: usize, | |
699 | candidate: &mut Candidate<'pat, 'tcx>, | |
700 | prefix: &'pat [Pat<'tcx>], | |
701 | opt_slice: Option<&'pat Pat<'tcx>>, | |
702 | suffix: &'pat [Pat<'tcx>], | |
703 | ) { | |
9fa01778 | 704 | let removed_place = candidate.match_pairs.remove(match_pair_index).place; |
3157f602 | 705 | self.prefix_slice_suffix( |
9fa01778 XL |
706 | &mut candidate.match_pairs, |
707 | &removed_place, | |
3157f602 XL |
708 | prefix, |
709 | opt_slice, | |
dfeec247 XL |
710 | suffix, |
711 | ); | |
3157f602 XL |
712 | } |
713 | ||
9fa01778 XL |
714 | fn candidate_after_variant_switch<'pat>( |
715 | &mut self, | |
716 | match_pair_index: usize, | |
717 | adt_def: &'tcx ty::AdtDef, | |
718 | variant_index: VariantIdx, | |
e74abb32 | 719 | subpatterns: &'pat [FieldPat<'tcx>], |
9fa01778 XL |
720 | candidate: &mut Candidate<'pat, 'tcx>, |
721 | ) { | |
722 | let match_pair = candidate.match_pairs.remove(match_pair_index); | |
e74abb32 | 723 | let tcx = self.hir.tcx(); |
92a42be0 SL |
724 | |
725 | // So, if we have a match-pattern like `x @ Enum::Variant(P1, P2)`, | |
726 | // we want to create a set of derived match-patterns like | |
727 | // `(x as Variant).0 @ P1` and `(x as Variant).1 @ P1`. | |
532ac7d7 | 728 | let elem = ProjectionElem::Downcast( |
dfeec247 XL |
729 | Some(adt_def.variants[variant_index].ident.name), |
730 | variant_index, | |
731 | ); | |
e74abb32 XL |
732 | let downcast_place = tcx.mk_place_elem(match_pair.place, elem); // `(x as Variant)` |
733 | let consequent_match_pairs = subpatterns.iter().map(|subpattern| { | |
734 | // e.g., `(x as Variant).0` | |
74b04a01 | 735 | let place = tcx.mk_place_field(downcast_place, subpattern.field, subpattern.pattern.ty); |
e74abb32 XL |
736 | // e.g., `(x as Variant).0 @ P1` |
737 | MatchPair::new(place, &subpattern.pattern) | |
738 | }); | |
92a42be0 | 739 | |
9fa01778 | 740 | candidate.match_pairs.extend(consequent_match_pairs); |
e9174d1e SL |
741 | } |
742 | ||
92a42be0 | 743 | fn error_simplifyable<'pat>(&mut self, match_pair: &MatchPair<'pat, 'tcx>) -> ! { |
dfeec247 | 744 | span_bug!(match_pair.pattern.span, "simplifyable pattern found: {:?}", match_pair.pattern) |
e9174d1e | 745 | } |
0731742a XL |
746 | |
747 | fn const_range_contains( | |
748 | &self, | |
e74abb32 | 749 | range: PatRange<'tcx>, |
dc9dc135 | 750 | value: &'tcx ty::Const<'tcx>, |
0731742a XL |
751 | ) -> Option<bool> { |
752 | use std::cmp::Ordering::*; | |
753 | ||
0731742a XL |
754 | let tcx = self.hir.tcx(); |
755 | ||
e1599b0c XL |
756 | let a = compare_const_vals(tcx, range.lo, value, self.hir.param_env, range.lo.ty)?; |
757 | let b = compare_const_vals(tcx, value, range.hi, self.hir.param_env, range.lo.ty)?; | |
0731742a XL |
758 | |
759 | match (b, range.end) { | |
dfeec247 | 760 | (Less, _) | (Equal, RangeEnd::Included) if a != Greater => Some(true), |
0731742a XL |
761 | _ => Some(false), |
762 | } | |
763 | } | |
764 | ||
765 | fn values_not_contained_in_range( | |
766 | &self, | |
e74abb32 | 767 | range: PatRange<'tcx>, |
3dfed10e | 768 | options: &FxIndexMap<&'tcx ty::Const<'tcx>, u128>, |
0731742a | 769 | ) -> Option<bool> { |
3dfed10e | 770 | for &val in options.keys() { |
0731742a XL |
771 | if self.const_range_contains(range, val)? { |
772 | return Some(false); | |
773 | } | |
774 | } | |
775 | ||
776 | Some(true) | |
777 | } | |
e9174d1e | 778 | } |
92a42be0 | 779 | |
dc9dc135 XL |
780 | impl Test<'_> { |
781 | pub(super) fn targets(&self) -> usize { | |
782 | match self.kind { | |
dfeec247 | 783 | TestKind::Eq { .. } | TestKind::Range(_) | TestKind::Len { .. } => 2, |
dc9dc135 XL |
784 | TestKind::Switch { adt_def, .. } => { |
785 | // While the switch that we generate doesn't test for all | |
786 | // variants, we have a target for each variant and the | |
787 | // otherwise case, and we make sure that all of the cases not | |
788 | // specified have the same block. | |
789 | adt_def.variants.len() + 1 | |
790 | } | |
791 | TestKind::SwitchInt { switch_ty, ref options, .. } => { | |
792 | if switch_ty.is_bool() { | |
793 | // `bool` is special cased in `perform_test` to always | |
794 | // branch to two blocks. | |
795 | 2 | |
796 | } else { | |
797 | options.len() + 1 | |
798 | } | |
799 | } | |
800 | } | |
801 | } | |
802 | } | |
803 | ||
416331ca | 804 | fn is_switch_ty(ty: Ty<'_>) -> bool { |
92a42be0 SL |
805 | ty.is_integral() || ty.is_char() || ty.is_bool() |
806 | } |