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