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.
8 use crate::build::Builder;
9 use crate::build::matches::{Candidate, MatchPair, Test, TestKind};
11 use crate::hair::pattern::compare_const_vals;
12 use rustc_data_structures::bit_set::BitSet;
13 use rustc_data_structures::fx::FxHashMap;
14 use rustc::ty::{self, Ty};
15 use rustc::ty::util::IntTypeExt;
16 use rustc::ty::layout::VariantIdx;
18 use rustc::hir::{RangeEnd, Mutability};
20 use std::cmp::Ordering;
22 impl<'a, 'gcx, 'tcx> Builder<'a, 'gcx, 'tcx> {
23 /// Identifies what test is needed to decide if `match_pair` is applicable.
25 /// It is a bug to call this with a simplifiable pattern.
26 pub fn test<'pat>(&mut self, match_pair: &MatchPair<'pat, 'tcx>) -> Test<'tcx> {
27 match *match_pair.pattern.kind {
28 PatternKind::Variant { ref adt_def, substs: _, variant_index: _, subpatterns: _ } => {
30 span: match_pair.pattern.span,
31 kind: TestKind::Switch {
32 adt_def: adt_def.clone(),
33 variants: BitSet::new_empty(adt_def.variants.len()),
38 PatternKind::Constant { .. } if is_switch_ty(match_pair.pattern.ty) => {
39 // For integers, we use a `SwitchInt` match, which allows
40 // us to handle more cases.
42 span: match_pair.pattern.span,
43 kind: TestKind::SwitchInt {
44 switch_ty: match_pair.pattern.ty,
46 // these maps are empty to start; cases are
47 // added below in add_cases_to_switch
49 indices: Default::default(),
54 PatternKind::Constant { value } => {
56 span: match_pair.pattern.span,
59 ty: match_pair.pattern.ty.clone()
64 PatternKind::Range(range) => {
65 assert!(range.ty == match_pair.pattern.ty);
67 span: match_pair.pattern.span,
68 kind: TestKind::Range(range),
72 PatternKind::Slice { ref prefix, ref slice, ref suffix } => {
73 let len = prefix.len() + suffix.len();
74 let op = if slice.is_some() {
80 span: match_pair.pattern.span,
81 kind: TestKind::Len { len: len as u64, op: op },
85 PatternKind::AscribeUserType { .. } |
86 PatternKind::Array { .. } |
88 PatternKind::Binding { .. } |
89 PatternKind::Leaf { .. } |
90 PatternKind::Deref { .. } => {
91 self.error_simplifyable(match_pair)
96 pub fn add_cases_to_switch<'pat>(&mut self,
97 test_place: &Place<'tcx>,
98 candidate: &Candidate<'pat, 'tcx>,
100 options: &mut Vec<u128>,
101 indices: &mut FxHashMap<ty::Const<'tcx>, usize>)
104 let match_pair = match candidate.match_pairs.iter().find(|mp| mp.place == *test_place) {
105 Some(match_pair) => match_pair,
106 _ => { return false; }
109 match *match_pair.pattern.kind {
110 PatternKind::Constant { value } => {
111 let switch_ty = ty::ParamEnv::empty().and(switch_ty);
114 options.push(value.unwrap_bits(self.hir.tcx(), switch_ty));
119 PatternKind::Variant { .. } => {
120 panic!("you should have called add_variants_to_switch instead!");
122 PatternKind::Range(range) => {
123 // Check that none of the switch values are in the range.
124 self.values_not_contained_in_range(range, indices)
127 PatternKind::Slice { .. } |
128 PatternKind::Array { .. } |
130 PatternKind::Binding { .. } |
131 PatternKind::AscribeUserType { .. } |
132 PatternKind::Leaf { .. } |
133 PatternKind::Deref { .. } => {
134 // don't know how to add these patterns to a switch
140 pub fn add_variants_to_switch<'pat>(&mut self,
141 test_place: &Place<'tcx>,
142 candidate: &Candidate<'pat, 'tcx>,
143 variants: &mut BitSet<VariantIdx>)
146 let match_pair = match candidate.match_pairs.iter().find(|mp| mp.place == *test_place) {
147 Some(match_pair) => match_pair,
148 _ => { return false; }
151 match *match_pair.pattern.kind {
152 PatternKind::Variant { adt_def: _ , variant_index, .. } => {
153 // We have a pattern testing for variant `variant_index`
154 // set the corresponding index to true
155 variants.insert(variant_index);
159 // don't know how to add these patterns to a switch
165 /// Generates the code to perform a test.
166 pub fn perform_test(&mut self,
171 debug!("perform_test({:?}, {:?}: {:?}, {:?})",
174 place.ty(&self.local_decls, self.hir.tcx()),
176 let source_info = self.source_info(test.span);
178 TestKind::Switch { adt_def, ref variants } => {
179 // Variants is a BitVec of indexes into adt_def.variants.
180 let num_enum_variants = adt_def.variants.len();
181 let used_variants = variants.count();
182 let mut otherwise_block = None;
183 let mut target_blocks = Vec::with_capacity(num_enum_variants);
184 let mut targets = Vec::with_capacity(used_variants + 1);
185 let mut values = Vec::with_capacity(used_variants);
186 let tcx = self.hir.tcx();
187 for (idx, discr) in adt_def.discriminants(tcx) {
188 target_blocks.push(if variants.contains(idx) {
189 values.push(discr.val);
190 let block = self.cfg.start_new_block();
195 .get_or_insert_with(|| self.cfg.start_new_block())
200 .unwrap_or_else(|| self.unreachable_block()),
202 debug!("num_enum_variants: {}, tested variants: {:?}, variants: {:?}",
203 num_enum_variants, values, variants);
204 let discr_ty = adt_def.repr.discr_type().to_ty(tcx);
205 let discr = self.temp(discr_ty, test.span);
206 self.cfg.push_assign(block, source_info, &discr,
207 Rvalue::Discriminant(place.clone()));
208 assert_eq!(values.len() + 1, targets.len());
209 self.cfg.terminate(block, source_info, TerminatorKind::SwitchInt {
210 discr: Operand::Move(discr),
212 values: From::from(values),
218 TestKind::SwitchInt { switch_ty, ref options, indices: _ } => {
219 let (ret, terminator) = if switch_ty.sty == ty::Bool {
220 assert!(options.len() > 0 && options.len() <= 2);
221 let (true_bb, false_bb) = (self.cfg.start_new_block(),
222 self.cfg.start_new_block());
223 let ret = match options[0] {
224 1 => vec![true_bb, false_bb],
225 0 => vec![false_bb, true_bb],
226 v => span_bug!(test.span, "expected boolean value but got {:?}", v)
228 (ret, TerminatorKind::if_(self.hir.tcx(), Operand::Copy(place.clone()),
231 // The switch may be inexhaustive so we
232 // add a catch all block
233 let otherwise = self.cfg.start_new_block();
234 let targets: Vec<_> =
236 .map(|_| self.cfg.start_new_block())
237 .chain(Some(otherwise))
239 (targets.clone(), TerminatorKind::SwitchInt {
240 discr: Operand::Copy(place.clone()),
242 values: options.clone().into(),
246 self.cfg.terminate(block, source_info, terminator);
250 TestKind::Eq { value, mut ty } => {
251 let val = Operand::Copy(place.clone());
252 let mut expect = self.literal_operand(test.span, ty, value);
253 // Use `PartialEq::eq` instead of `BinOp::Eq`
254 // (the binop can only handle primitives)
255 let fail = self.cfg.start_new_block();
257 // If we're using `b"..."` as a pattern, we need to insert an
258 // unsizing coercion, as the byte string has the type `&[u8; N]`.
260 // We want to do this even when the scrutinee is a reference to an
261 // array, so we can call `<[u8]>::eq` rather than having to find an
263 let unsize = |ty: Ty<'tcx>| match ty.sty {
264 ty::Ref(region, rty, _) => match rty.sty {
265 ty::Array(inner_ty, n) => Some((region, inner_ty, n)),
270 let opt_ref_ty = unsize(ty);
271 let opt_ref_test_ty = unsize(value.ty);
272 let mut place = place.clone();
273 match (opt_ref_ty, opt_ref_test_ty) {
274 // nothing to do, neither is an array
276 (Some((region, elem_ty, _)), _) |
277 (None, Some((region, elem_ty, _))) => {
278 let tcx = self.hir.tcx();
280 ty = tcx.mk_imm_ref(region, tcx.mk_slice(elem_ty));
281 if opt_ref_ty.is_some() {
282 place = self.temp(ty, test.span);
283 self.cfg.push_assign(block, source_info, &place,
284 Rvalue::Cast(CastKind::Unsize, val, ty));
286 if opt_ref_test_ty.is_some() {
287 let array = self.literal_operand(
293 let slice = self.temp(ty, test.span);
294 self.cfg.push_assign(block, source_info, &slice,
295 Rvalue::Cast(CastKind::Unsize, array, ty));
296 expect = Operand::Move(slice);
300 let eq_def_id = self.hir.tcx().lang_items().eq_trait().unwrap();
301 let (mty, method) = self.hir.trait_method(eq_def_id, "eq", ty, &[ty.into()]);
302 let method = self.hir.tcx().mk_lazy_const(ty::LazyConst::Evaluated(method));
304 let re_erased = self.hir.tcx().types.re_erased;
305 // take the argument by reference
306 let tam = ty::TypeAndMut {
308 mutbl: Mutability::MutImmutable,
310 let ref_ty = self.hir.tcx().mk_ref(re_erased, tam);
312 // let lhs_ref_place = &lhs;
313 let ref_rvalue = Rvalue::Ref(re_erased, BorrowKind::Shared, place);
314 let lhs_ref_place = self.temp(ref_ty, test.span);
315 self.cfg.push_assign(block, source_info, &lhs_ref_place, ref_rvalue);
316 let val = Operand::Move(lhs_ref_place);
318 // let rhs_place = rhs;
319 let rhs_place = self.temp(ty, test.span);
320 self.cfg.push_assign(block, source_info, &rhs_place, Rvalue::Use(expect));
322 // let rhs_ref_place = &rhs_place;
323 let ref_rvalue = Rvalue::Ref(re_erased, BorrowKind::Shared, rhs_place);
324 let rhs_ref_place = self.temp(ref_ty, test.span);
325 self.cfg.push_assign(block, source_info, &rhs_ref_place, ref_rvalue);
326 let expect = Operand::Move(rhs_ref_place);
328 let bool_ty = self.hir.bool_ty();
329 let eq_result = self.temp(bool_ty, test.span);
330 let eq_block = self.cfg.start_new_block();
331 let cleanup = self.diverge_cleanup();
332 self.cfg.terminate(block, source_info, TerminatorKind::Call {
333 func: Operand::Constant(box Constant {
337 // FIXME(#54571): This constant comes from user
338 // input (a constant in a pattern). Are
339 // there forms where users can add type
340 // annotations here? For example, an
341 // associated constant? Need to
347 args: vec![val, expect],
348 destination: Some((eq_result.clone(), eq_block)),
349 cleanup: Some(cleanup),
350 from_hir_call: false,
354 let block = self.cfg.start_new_block();
355 self.cfg.terminate(eq_block, source_info,
356 TerminatorKind::if_(self.hir.tcx(),
357 Operand::Move(eq_result),
361 let block = self.compare(block, fail, test.span, BinOp::Eq, expect, val);
366 TestKind::Range(PatternRange { ref lo, ref hi, ty, ref end }) => {
367 // Test `val` by computing `lo <= val && val <= hi`, using primitive comparisons.
368 let lo = self.literal_operand(test.span, ty.clone(), lo.clone());
369 let hi = self.literal_operand(test.span, ty.clone(), hi.clone());
370 let val = Operand::Copy(place.clone());
372 let fail = self.cfg.start_new_block();
373 let block = self.compare(block, fail, test.span, BinOp::Le, lo, val.clone());
374 let block = match *end {
375 RangeEnd::Included => self.compare(block, fail, test.span, BinOp::Le, val, hi),
376 RangeEnd::Excluded => self.compare(block, fail, test.span, BinOp::Lt, val, hi),
382 TestKind::Len { len, op } => {
383 let (usize_ty, bool_ty) = (self.hir.usize_ty(), self.hir.bool_ty());
384 let (actual, result) = (self.temp(usize_ty, test.span),
385 self.temp(bool_ty, test.span));
387 // actual = len(place)
388 self.cfg.push_assign(block, source_info,
389 &actual, Rvalue::Len(place.clone()));
392 let expected = self.push_usize(block, source_info, len);
394 // result = actual == expected OR result = actual < expected
395 self.cfg.push_assign(block, source_info, &result,
397 Operand::Move(actual),
398 Operand::Move(expected)));
400 // branch based on result
401 let (false_bb, true_bb) = (self.cfg.start_new_block(),
402 self.cfg.start_new_block());
403 self.cfg.terminate(block, source_info,
404 TerminatorKind::if_(self.hir.tcx(), Operand::Move(result),
406 vec![true_bb, false_bb]
411 fn compare(&mut self,
413 fail_block: BasicBlock,
417 right: Operand<'tcx>) -> BasicBlock {
418 let bool_ty = self.hir.bool_ty();
419 let result = self.temp(bool_ty, span);
421 // result = op(left, right)
422 let source_info = self.source_info(span);
423 self.cfg.push_assign(block, source_info, &result,
424 Rvalue::BinaryOp(op, left, right));
426 // branch based on result
427 let target_block = self.cfg.start_new_block();
428 self.cfg.terminate(block, source_info,
429 TerminatorKind::if_(self.hir.tcx(), Operand::Move(result),
430 target_block, fail_block));
434 /// Given that we are performing `test` against `test_place`, this job
435 /// sorts out what the status of `candidate` will be after the test. See
436 /// `test_candidates` for the usage of this function. The returned index is
437 /// the index that this candiate should be placed in the
438 /// `target_candidates` vec. The candidate may be modified to update its
441 /// So, for example, if this candidate is `x @ Some(P0)` and the `Test` is
442 /// a variant test, then we would modify the candidate to be `(x as
443 /// Option).0 @ P0` and return the index corresponding to the variant
446 /// However, in some cases, the test may just not be relevant to candidate.
447 /// For example, suppose we are testing whether `foo.x == 22`, but in one
448 /// match arm we have `Foo { x: _, ... }`... in that case, the test for
449 /// what value `x` has has no particular relevance to this candidate. In
450 /// such cases, this function just returns None without doing anything.
451 /// This is used by the overall `match_candidates` algorithm to structure
452 /// the match as a whole. See `match_candidates` for more details.
454 /// FIXME(#29623). In some cases, we have some tricky choices to make. for
455 /// example, if we are testing that `x == 22`, but the candidate is `x @
456 /// 13..55`, what should we do? In the event that the test is true, we know
457 /// that the candidate applies, but in the event of false, we don't know
458 /// that it *doesn't* apply. For now, we return false, indicate that the
459 /// test does not apply to this candidate, but it might be we can get
460 /// tighter match code if we do something a bit different.
461 pub fn sort_candidate<'pat, 'cand>(
463 test_place: &Place<'tcx>,
465 candidate: &mut Candidate<'pat, 'tcx>,
467 // Find the match_pair for this place (if any). At present,
468 // afaik, there can be at most one. (In the future, if we
469 // adopted a more general `@` operator, there might be more
470 // than one, but it'd be very unusual to have two sides that
471 // both require tests; you'd expect one side to be simplified
473 let (match_pair_index, match_pair) = candidate.match_pairs
476 .find(|&(_, mp)| mp.place == *test_place)?;
478 match (&test.kind, &*match_pair.pattern.kind) {
479 // If we are performing a variant switch, then this
480 // informs variant patterns, but nothing else.
481 (&TestKind::Switch { adt_def: tested_adt_def, .. },
482 &PatternKind::Variant { adt_def, variant_index, ref subpatterns, .. }) => {
483 assert_eq!(adt_def, tested_adt_def);
484 self.candidate_after_variant_switch(match_pair_index,
489 Some(variant_index.as_usize())
492 (&TestKind::Switch { .. }, _) => None,
494 // If we are performing a switch over integers, then this informs integer
495 // equality, but nothing else.
497 // FIXME(#29623) we could use PatternKind::Range to rule
498 // things out here, in some cases.
499 (&TestKind::SwitchInt { switch_ty: _, options: _, ref indices },
500 &PatternKind::Constant { ref value })
501 if is_switch_ty(match_pair.pattern.ty) => {
502 let index = indices[value];
503 self.candidate_without_match_pair(match_pair_index, candidate);
507 (&TestKind::SwitchInt { switch_ty: _, ref options, ref indices },
508 &PatternKind::Range(range)) => {
509 let not_contained = self
510 .values_not_contained_in_range(range, indices)
514 // No switch values are contained in the pattern range,
515 // so the pattern can be matched only if this test fails.
516 let otherwise = options.len();
523 (&TestKind::SwitchInt { .. }, _) => None,
525 (&TestKind::Len { len: test_len, op: BinOp::Eq },
526 &PatternKind::Slice { ref prefix, ref slice, ref suffix }) => {
527 let pat_len = (prefix.len() + suffix.len()) as u64;
528 match (test_len.cmp(&pat_len), slice) {
529 (Ordering::Equal, &None) => {
530 // on true, min_len = len = $actual_length,
531 // on false, len != $actual_length
532 self.candidate_after_slice_test(match_pair_index,
539 (Ordering::Less, _) => {
540 // test_len < pat_len. If $actual_len = test_len,
541 // then $actual_len < pat_len and we don't have
545 (Ordering::Equal, &Some(_)) | (Ordering::Greater, &Some(_)) => {
546 // This can match both if $actual_len = test_len >= pat_len,
547 // and if $actual_len > test_len. We can't advance.
550 (Ordering::Greater, &None) => {
551 // test_len != pat_len, so if $actual_len = test_len, then
552 // $actual_len != pat_len.
558 (&TestKind::Len { len: test_len, op: BinOp::Ge },
559 &PatternKind::Slice { ref prefix, ref slice, ref suffix }) => {
560 // the test is `$actual_len >= test_len`
561 let pat_len = (prefix.len() + suffix.len()) as u64;
562 match (test_len.cmp(&pat_len), slice) {
563 (Ordering::Equal, &Some(_)) => {
564 // $actual_len >= test_len = pat_len,
566 self.candidate_after_slice_test(match_pair_index,
573 (Ordering::Less, _) | (Ordering::Equal, &None) => {
574 // test_len <= pat_len. If $actual_len < test_len,
575 // then it is also < pat_len, so the test passing is
576 // necessary (but insufficient).
579 (Ordering::Greater, &None) => {
580 // test_len > pat_len. If $actual_len >= test_len > pat_len,
581 // then we know we won't have a match.
584 (Ordering::Greater, &Some(_)) => {
585 // test_len < pat_len, and is therefore less
586 // strict. This can still go both ways.
592 (&TestKind::Range(test),
593 &PatternKind::Range(pat)) => {
595 self.candidate_without_match_pair(
602 let no_overlap = (|| {
603 use std::cmp::Ordering::*;
604 use rustc::hir::RangeEnd::*;
606 let param_env = ty::ParamEnv::empty().and(test.ty);
607 let tcx = self.hir.tcx();
609 let lo = compare_const_vals(tcx, test.lo, pat.hi, param_env)?;
610 let hi = compare_const_vals(tcx, test.hi, pat.lo, param_env)?;
612 match (test.end, pat.end, lo, hi) {
615 (_, Excluded, Equal, _) |
618 (Excluded, _, _, Equal) => Some(true),
623 if no_overlap == Some(true) {
624 // Testing range does not overlap with pattern range,
625 // so the pattern can be matched only if this test fails.
632 (&TestKind::Range(range), &PatternKind::Constant { value }) => {
633 if self.const_range_contains(range, value) == Some(false) {
634 // `value` is not contained in the testing range,
635 // so `value` can be matched only if this test fails.
642 (&TestKind::Range { .. }, _) => None,
644 (&TestKind::Eq { .. }, _) |
645 (&TestKind::Len { .. }, _) => {
646 // These are all binary tests.
648 // FIXME(#29623) we can be more clever here
649 let pattern_test = self.test(&match_pair);
650 if pattern_test.kind == test.kind {
651 self.candidate_without_match_pair(match_pair_index, candidate);
660 fn candidate_without_match_pair(
662 match_pair_index: usize,
663 candidate: &mut Candidate<'_, 'tcx>,
665 candidate.match_pairs.remove(match_pair_index);
668 fn candidate_after_slice_test<'pat>(&mut self,
669 match_pair_index: usize,
670 candidate: &mut Candidate<'pat, 'tcx>,
671 prefix: &'pat [Pattern<'tcx>],
672 opt_slice: Option<&'pat Pattern<'tcx>>,
673 suffix: &'pat [Pattern<'tcx>]) {
674 let removed_place = candidate.match_pairs.remove(match_pair_index).place;
675 self.prefix_slice_suffix(
676 &mut candidate.match_pairs,
683 fn candidate_after_variant_switch<'pat>(
685 match_pair_index: usize,
686 adt_def: &'tcx ty::AdtDef,
687 variant_index: VariantIdx,
688 subpatterns: &'pat [FieldPattern<'tcx>],
689 candidate: &mut Candidate<'pat, 'tcx>,
691 let match_pair = candidate.match_pairs.remove(match_pair_index);
693 // So, if we have a match-pattern like `x @ Enum::Variant(P1, P2)`,
694 // we want to create a set of derived match-patterns like
695 // `(x as Variant).0 @ P1` and `(x as Variant).1 @ P1`.
696 let elem = ProjectionElem::Downcast(adt_def, variant_index);
697 let downcast_place = match_pair.place.elem(elem); // `(x as Variant)`
698 let consequent_match_pairs =
701 // e.g., `(x as Variant).0`
702 let place = downcast_place.clone().field(subpattern.field,
703 subpattern.pattern.ty);
704 // e.g., `(x as Variant).0 @ P1`
705 MatchPair::new(place, &subpattern.pattern)
708 candidate.match_pairs.extend(consequent_match_pairs);
711 fn error_simplifyable<'pat>(&mut self, match_pair: &MatchPair<'pat, 'tcx>) -> ! {
712 span_bug!(match_pair.pattern.span,
713 "simplifyable pattern found: {:?}",
717 fn const_range_contains(
719 range: PatternRange<'tcx>,
720 value: ty::Const<'tcx>,
722 use std::cmp::Ordering::*;
724 let param_env = ty::ParamEnv::empty().and(range.ty);
725 let tcx = self.hir.tcx();
727 let a = compare_const_vals(tcx, range.lo, value, param_env)?;
728 let b = compare_const_vals(tcx, value, range.hi, param_env)?;
730 match (b, range.end) {
732 (Equal, RangeEnd::Included) if a != Greater => Some(true),
737 fn values_not_contained_in_range(
739 range: PatternRange<'tcx>,
740 indices: &FxHashMap<ty::Const<'tcx>, usize>,
742 for &val in indices.keys() {
743 if self.const_range_contains(range, val)? {
752 fn is_switch_ty<'tcx>(ty: Ty<'tcx>) -> bool {
753 ty.is_integral() || ty.is_char() || ty.is_bool()