1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
13 // After candidates have been simplified, the only match pairs that
14 // remain are those that require some sort of test. The functions here
15 // identify what tests are needed, perform the tests, and then filter
16 // the candidates based on the result.
19 use build
::matches
::{Candidate, MatchPair, Test, TestKind}
;
21 use rustc_data_structures
::fx
::FxHashMap
;
22 use rustc_data_structures
::bitvec
::BitVector
;
23 use rustc
::middle
::const_val
::ConstVal
;
24 use rustc
::ty
::{self, Ty}
;
27 use std
::cmp
::Ordering
;
29 impl<'a
, 'gcx
, 'tcx
> Builder
<'a
, 'gcx
, 'tcx
> {
30 /// Identifies what test is needed to decide if `match_pair` is applicable.
32 /// It is a bug to call this with a simplifyable pattern.
33 pub fn test
<'pat
>(&mut self, match_pair
: &MatchPair
<'pat
, 'tcx
>) -> Test
<'tcx
> {
34 match *match_pair
.pattern
.kind
{
35 PatternKind
::Variant { ref adt_def, variant_index: _, subpatterns: _ }
=> {
37 span
: match_pair
.pattern
.span
,
38 kind
: TestKind
::Switch
{
39 adt_def
: adt_def
.clone(),
40 variants
: BitVector
::new(self.hir
.num_variants(adt_def
)),
45 PatternKind
::Constant { .. }
46 if is_switch_ty(match_pair
.pattern
.ty
) => {
47 // for integers, we use a SwitchInt match, which allows
48 // us to handle more cases
50 span
: match_pair
.pattern
.span
,
51 kind
: TestKind
::SwitchInt
{
52 switch_ty
: match_pair
.pattern
.ty
,
54 // these maps are empty to start; cases are
55 // added below in add_cases_to_switch
62 PatternKind
::Constant { ref value }
=> {
64 span
: match_pair
.pattern
.span
,
67 ty
: match_pair
.pattern
.ty
.clone()
72 PatternKind
::Range { ref lo, ref hi }
=> {
74 span
: match_pair
.pattern
.span
,
75 kind
: TestKind
::Range
{
76 lo
: Literal
::Value { value: lo.clone() }
,
77 hi
: Literal
::Value { value: hi.clone() }
,
78 ty
: match_pair
.pattern
.ty
.clone(),
83 PatternKind
::Slice { ref prefix, ref slice, ref suffix }
84 if !match_pair
.slice_len_checked
=> {
85 let len
= prefix
.len() + suffix
.len();
86 let op
= if slice
.is_some() {
92 span
: match_pair
.pattern
.span
,
93 kind
: TestKind
::Len { len: len as u64, op: op }
,
97 PatternKind
::Array { .. }
|
98 PatternKind
::Slice { .. }
|
100 PatternKind
::Binding { .. }
|
101 PatternKind
::Leaf { .. }
|
102 PatternKind
::Deref { .. }
=> {
103 self.error_simplifyable(match_pair
)
108 pub fn add_cases_to_switch
<'pat
>(&mut self,
109 test_lvalue
: &Lvalue
<'tcx
>,
110 candidate
: &Candidate
<'pat
, 'tcx
>,
112 options
: &mut Vec
<ConstVal
>,
113 indices
: &mut FxHashMap
<ConstVal
, usize>)
116 let match_pair
= match candidate
.match_pairs
.iter().find(|mp
| mp
.lvalue
== *test_lvalue
) {
117 Some(match_pair
) => match_pair
,
118 _
=> { return false; }
121 match *match_pair
.pattern
.kind
{
122 PatternKind
::Constant { ref value }
=> {
123 // if the lvalues match, the type should match
124 assert_eq
!(match_pair
.pattern
.ty
, switch_ty
);
126 indices
.entry(value
.clone())
128 options
.push(value
.clone());
133 PatternKind
::Variant { .. }
=> {
134 panic
!("you should have called add_variants_to_switch instead!");
136 PatternKind
::Range { .. }
|
137 PatternKind
::Slice { .. }
|
138 PatternKind
::Array { .. }
|
140 PatternKind
::Binding { .. }
|
141 PatternKind
::Leaf { .. }
|
142 PatternKind
::Deref { .. }
=> {
143 // don't know how to add these patterns to a switch
149 pub fn add_variants_to_switch
<'pat
>(&mut self,
150 test_lvalue
: &Lvalue
<'tcx
>,
151 candidate
: &Candidate
<'pat
, 'tcx
>,
152 variants
: &mut BitVector
)
155 let match_pair
= match candidate
.match_pairs
.iter().find(|mp
| mp
.lvalue
== *test_lvalue
) {
156 Some(match_pair
) => match_pair
,
157 _
=> { return false; }
160 match *match_pair
.pattern
.kind
{
161 PatternKind
::Variant { adt_def: _ , variant_index, .. }
=> {
162 // We have a pattern testing for variant `variant_index`
163 // set the corresponding index to true
164 variants
.insert(variant_index
);
168 // don't know how to add these patterns to a switch
174 /// Generates the code to perform a test.
175 pub fn perform_test(&mut self,
177 lvalue
: &Lvalue
<'tcx
>,
180 let source_info
= self.source_info(test
.span
);
182 TestKind
::Switch { adt_def, ref variants }
=> {
183 let num_enum_variants
= self.hir
.num_variants(adt_def
);
184 let mut otherwise_block
= None
;
185 let target_blocks
: Vec
<_
> = (0..num_enum_variants
).map(|i
| {
186 if variants
.contains(i
) {
187 self.cfg
.start_new_block()
189 if otherwise_block
.is_none() {
190 otherwise_block
= Some(self.cfg
.start_new_block());
192 otherwise_block
.unwrap()
195 debug
!("num_enum_variants: {}, num tested variants: {}, variants: {:?}",
196 num_enum_variants
, variants
.iter().count(), variants
);
197 self.cfg
.terminate(block
, source_info
, TerminatorKind
::Switch
{
198 discr
: lvalue
.clone(),
200 targets
: target_blocks
.clone()
205 TestKind
::SwitchInt { switch_ty, ref options, indices: _ }
=> {
206 let (targets
, term
) = match switch_ty
.sty
{
207 // If we're matching on boolean we can
208 // use the If TerminatorKind instead
210 assert
!(options
.len() > 0 && options
.len() <= 2);
212 let (true_bb
, else_bb
) =
213 (self.cfg
.start_new_block(),
214 self.cfg
.start_new_block());
216 let targets
= match &options
[0] {
217 &ConstVal
::Bool(true) => vec
![true_bb
, else_bb
],
218 &ConstVal
::Bool(false) => vec
![else_bb
, true_bb
],
219 v
=> span_bug
!(test
.span
, "expected boolean value but got {:?}", v
)
224 cond
: Operand
::Consume(lvalue
.clone()),
225 targets
: (true_bb
, else_bb
)
230 // The switch may be inexhaustive so we
231 // add a catch all block
232 let otherwise
= self.cfg
.start_new_block();
233 let targets
: Vec
<_
> =
235 .map(|_
| self.cfg
.start_new_block())
236 .chain(Some(otherwise
))
240 TerminatorKind
::SwitchInt
{
241 discr
: lvalue
.clone(),
242 switch_ty
: switch_ty
,
243 values
: options
.clone(),
249 self.cfg
.terminate(block
, source_info
, term
);
253 TestKind
::Eq { ref value, mut ty }
=> {
254 let mut val
= Operand
::Consume(lvalue
.clone());
256 // If we're using b"..." as a pattern, we need to insert an
257 // unsizing coercion, as the byte string has the type &[u8; N].
258 let expect
= if let ConstVal
::ByteStr(ref bytes
) = *value
{
259 let tcx
= self.hir
.tcx();
261 // Unsize the lvalue to &[u8], too, if necessary.
262 if let ty
::TyRef(region
, mt
) = ty
.sty
{
263 if let ty
::TyArray(_
, _
) = mt
.ty
.sty
{
264 ty
= tcx
.mk_imm_ref(region
, tcx
.mk_slice(tcx
.types
.u8));
265 let val_slice
= self.temp(ty
);
266 self.cfg
.push_assign(block
, source_info
, &val_slice
,
267 Rvalue
::Cast(CastKind
::Unsize
, val
, ty
));
268 val
= Operand
::Consume(val_slice
);
272 assert
!(ty
.is_slice());
274 let array_ty
= tcx
.mk_array(tcx
.types
.u8, bytes
.len());
275 let array_ref
= tcx
.mk_imm_ref(tcx
.mk_region(ty
::ReStatic
), array_ty
);
276 let array
= self.literal_operand(test
.span
, array_ref
, Literal
::Value
{
280 let slice
= self.temp(ty
);
281 self.cfg
.push_assign(block
, source_info
, &slice
,
282 Rvalue
::Cast(CastKind
::Unsize
, array
, ty
));
283 Operand
::Consume(slice
)
285 self.literal_operand(test
.span
, ty
, Literal
::Value
{
290 // Use PartialEq::eq for &str and &[u8] slices, instead of BinOp::Eq.
291 let fail
= self.cfg
.start_new_block();
292 if let ty
::TyRef(_
, mt
) = ty
.sty
{
293 assert
!(ty
.is_slice());
294 let eq_def_id
= self.hir
.tcx().lang_items
.eq_trait().unwrap();
296 let (mty
, method
) = self.hir
.trait_method(eq_def_id
, "eq", ty
, &[ty
]);
298 let bool_ty
= self.hir
.bool_ty();
299 let eq_result
= self.temp(bool_ty
);
300 let eq_block
= self.cfg
.start_new_block();
301 let cleanup
= self.diverge_cleanup();
302 self.cfg
.terminate(block
, source_info
, TerminatorKind
::Call
{
303 func
: Operand
::Constant(Constant
{
308 args
: vec
![val
, expect
],
309 destination
: Some((eq_result
.clone(), eq_block
)),
314 let block
= self.cfg
.start_new_block();
315 self.cfg
.terminate(eq_block
, source_info
, TerminatorKind
::If
{
316 cond
: Operand
::Consume(eq_result
),
317 targets
: (block
, fail
),
322 let block
= self.compare(block
, fail
, test
.span
, BinOp
::Eq
, expect
, val
);
327 TestKind
::Range { ref lo, ref hi, ty }
=> {
328 // Test `val` by computing `lo <= val && val <= hi`, using primitive comparisons.
329 let lo
= self.literal_operand(test
.span
, ty
.clone(), lo
.clone());
330 let hi
= self.literal_operand(test
.span
, ty
.clone(), hi
.clone());
331 let val
= Operand
::Consume(lvalue
.clone());
333 let fail
= self.cfg
.start_new_block();
334 let block
= self.compare(block
, fail
, test
.span
, BinOp
::Le
, lo
, val
.clone());
335 let block
= self.compare(block
, fail
, test
.span
, BinOp
::Le
, val
, hi
);
340 TestKind
::Len { len, op }
=> {
341 let (usize_ty
, bool_ty
) = (self.hir
.usize_ty(), self.hir
.bool_ty());
342 let (actual
, result
) = (self.temp(usize_ty
), self.temp(bool_ty
));
344 // actual = len(lvalue)
345 self.cfg
.push_assign(block
, source_info
,
346 &actual
, Rvalue
::Len(lvalue
.clone()));
349 let expected
= self.push_usize(block
, source_info
, len
);
351 // result = actual == expected OR result = actual < expected
352 self.cfg
.push_assign(block
, source_info
, &result
,
354 Operand
::Consume(actual
),
355 Operand
::Consume(expected
)));
357 // branch based on result
358 let target_blocks
: Vec
<_
> = vec
![self.cfg
.start_new_block(),
359 self.cfg
.start_new_block()];
360 self.cfg
.terminate(block
, source_info
, TerminatorKind
::If
{
361 cond
: Operand
::Consume(result
),
362 targets
: (target_blocks
[0], target_blocks
[1])
370 fn compare(&mut self,
372 fail_block
: BasicBlock
,
376 right
: Operand
<'tcx
>) -> BasicBlock
{
377 let bool_ty
= self.hir
.bool_ty();
378 let result
= self.temp(bool_ty
);
380 // result = op(left, right)
381 let source_info
= self.source_info(span
);
382 self.cfg
.push_assign(block
, source_info
, &result
,
383 Rvalue
::BinaryOp(op
, left
, right
));
385 // branch based on result
386 let target_block
= self.cfg
.start_new_block();
387 self.cfg
.terminate(block
, source_info
, TerminatorKind
::If
{
388 cond
: Operand
::Consume(result
),
389 targets
: (target_block
, fail_block
)
395 /// Given that we are performing `test` against `test_lvalue`,
396 /// this job sorts out what the status of `candidate` will be
397 /// after the test. The `resulting_candidates` vector stores, for
398 /// each possible outcome of `test`, a vector of the candidates
399 /// that will result. This fn should add a (possibly modified)
400 /// clone of candidate into `resulting_candidates` wherever
403 /// So, for example, if this candidate is `x @ Some(P0)` and the
404 /// test is a variant test, then we would add `(x as Option).0 @
405 /// P0` to the `resulting_candidates` entry corresponding to the
408 /// However, in some cases, the test may just not be relevant to
409 /// candidate. For example, suppose we are testing whether `foo.x == 22`,
410 /// but in one match arm we have `Foo { x: _, ... }`... in that case,
411 /// the test for what value `x` has has no particular relevance
412 /// to this candidate. In such cases, this function just returns false
413 /// without doing anything. This is used by the overall `match_candidates`
414 /// algorithm to structure the match as a whole. See `match_candidates` for
417 /// FIXME(#29623). In some cases, we have some tricky choices to
418 /// make. for example, if we are testing that `x == 22`, but the
419 /// candidate is `x @ 13..55`, what should we do? In the event
420 /// that the test is true, we know that the candidate applies, but
421 /// in the event of false, we don't know that it *doesn't*
422 /// apply. For now, we return false, indicate that the test does
423 /// not apply to this candidate, but it might be we can get
424 /// tighter match code if we do something a bit different.
425 pub fn sort_candidate
<'pat
>(&mut self,
426 test_lvalue
: &Lvalue
<'tcx
>,
428 candidate
: &Candidate
<'pat
, 'tcx
>,
429 resulting_candidates
: &mut [Vec
<Candidate
<'pat
, 'tcx
>>])
431 // Find the match_pair for this lvalue (if any). At present,
432 // afaik, there can be at most one. (In the future, if we
433 // adopted a more general `@` operator, there might be more
434 // than one, but it'd be very unusual to have two sides that
435 // both require tests; you'd expect one side to be simplified
437 let tested_match_pair
= candidate
.match_pairs
.iter()
439 .filter(|&(_
, mp
)| mp
.lvalue
== *test_lvalue
)
441 let (match_pair_index
, match_pair
) = match tested_match_pair
{
444 // We are not testing this lvalue. Therefore, this
445 // candidate applies to ALL outcomes.
450 match (&test
.kind
, &*match_pair
.pattern
.kind
) {
451 // If we are performing a variant switch, then this
452 // informs variant patterns, but nothing else.
453 (&TestKind
::Switch { adt_def: tested_adt_def, .. }
,
454 &PatternKind
::Variant { adt_def, variant_index, ref subpatterns }
) => {
455 assert_eq
!(adt_def
, tested_adt_def
);
457 self.candidate_after_variant_switch(match_pair_index
,
462 resulting_candidates
[variant_index
].push(new_candidate
);
465 (&TestKind
::Switch { .. }
, _
) => false,
467 // If we are performing a switch over integers, then this informs integer
468 // equality, but nothing else.
470 // FIXME(#29623) we could use PatternKind::Range to rule
471 // things out here, in some cases.
472 (&TestKind
::SwitchInt { switch_ty: _, options: _, ref indices }
,
473 &PatternKind
::Constant { ref value }
)
474 if is_switch_ty(match_pair
.pattern
.ty
) => {
475 let index
= indices
[value
];
476 let new_candidate
= self.candidate_without_match_pair(match_pair_index
,
478 resulting_candidates
[index
].push(new_candidate
);
481 (&TestKind
::SwitchInt { .. }
, _
) => false,
484 (&TestKind
::Len { len: test_len, op: BinOp::Eq }
,
485 &PatternKind
::Slice { ref prefix, ref slice, ref suffix }
) => {
486 let pat_len
= (prefix
.len() + suffix
.len()) as u64;
487 match (test_len
.cmp(&pat_len
), slice
) {
488 (Ordering
::Equal
, &None
) => {
489 // on true, min_len = len = $actual_length,
490 // on false, len != $actual_length
491 resulting_candidates
[0].push(
492 self.candidate_after_slice_test(match_pair_index
,
500 (Ordering
::Less
, _
) => {
501 // test_len < pat_len. If $actual_len = test_len,
502 // then $actual_len < pat_len and we don't have
504 resulting_candidates
[1].push(candidate
.clone());
507 (Ordering
::Equal
, &Some(_
)) | (Ordering
::Greater
, &Some(_
)) => {
508 // This can match both if $actual_len = test_len >= pat_len,
509 // and if $actual_len > test_len. We can't advance.
512 (Ordering
::Greater
, &None
) => {
513 // test_len != pat_len, so if $actual_len = test_len, then
514 // $actual_len != pat_len.
515 resulting_candidates
[1].push(candidate
.clone());
521 (&TestKind
::Len { len: test_len, op: BinOp::Ge }
,
522 &PatternKind
::Slice { ref prefix, ref slice, ref suffix }
) => {
523 // the test is `$actual_len >= test_len`
524 let pat_len
= (prefix
.len() + suffix
.len()) as u64;
525 match (test_len
.cmp(&pat_len
), slice
) {
526 (Ordering
::Equal
, &Some(_
)) => {
527 // $actual_len >= test_len = pat_len,
529 resulting_candidates
[0].push(
530 self.candidate_after_slice_test(match_pair_index
,
538 (Ordering
::Less
, _
) | (Ordering
::Equal
, &None
) => {
539 // test_len <= pat_len. If $actual_len < test_len,
540 // then it is also < pat_len, so the test passing is
541 // necessary (but insufficient).
542 resulting_candidates
[0].push(candidate
.clone());
545 (Ordering
::Greater
, &None
) => {
546 // test_len > pat_len. If $actual_len >= test_len > pat_len,
547 // then we know we won't have a match.
548 resulting_candidates
[1].push(candidate
.clone());
551 (Ordering
::Greater
, &Some(_
)) => {
552 // test_len < pat_len, and is therefore less
553 // strict. This can still go both ways.
559 (&TestKind
::Eq { .. }
, _
) |
560 (&TestKind
::Range { .. }
, _
) |
561 (&TestKind
::Len { .. }
, _
) => {
562 // These are all binary tests.
564 // FIXME(#29623) we can be more clever here
565 let pattern_test
= self.test(&match_pair
);
566 if pattern_test
.kind
== test
.kind
{
567 let new_candidate
= self.candidate_without_match_pair(match_pair_index
,
569 resulting_candidates
[0].push(new_candidate
);
578 fn candidate_without_match_pair
<'pat
>(&mut self,
579 match_pair_index
: usize,
580 candidate
: &Candidate
<'pat
, 'tcx
>)
581 -> Candidate
<'pat
, 'tcx
> {
582 let other_match_pairs
=
583 candidate
.match_pairs
.iter()
585 .filter(|&(index
, _
)| index
!= match_pair_index
)
586 .map(|(_
, mp
)| mp
.clone())
589 span
: candidate
.span
,
590 match_pairs
: other_match_pairs
,
591 bindings
: candidate
.bindings
.clone(),
592 guard
: candidate
.guard
.clone(),
593 arm_index
: candidate
.arm_index
,
597 fn candidate_after_slice_test
<'pat
>(&mut self,
598 match_pair_index
: usize,
599 candidate
: &Candidate
<'pat
, 'tcx
>,
600 prefix
: &'pat
[Pattern
<'tcx
>],
601 opt_slice
: Option
<&'pat Pattern
<'tcx
>>,
602 suffix
: &'pat
[Pattern
<'tcx
>])
603 -> Candidate
<'pat
, 'tcx
> {
604 let mut new_candidate
=
605 self.candidate_without_match_pair(match_pair_index
, candidate
);
606 self.prefix_slice_suffix(
607 &mut new_candidate
.match_pairs
,
608 &candidate
.match_pairs
[match_pair_index
].lvalue
,
616 fn candidate_after_variant_switch
<'pat
>(&mut self,
617 match_pair_index
: usize,
618 adt_def
: &'tcx ty
::AdtDef
,
619 variant_index
: usize,
620 subpatterns
: &'pat
[FieldPattern
<'tcx
>],
621 candidate
: &Candidate
<'pat
, 'tcx
>)
622 -> Candidate
<'pat
, 'tcx
> {
623 let match_pair
= &candidate
.match_pairs
[match_pair_index
];
625 // So, if we have a match-pattern like `x @ Enum::Variant(P1, P2)`,
626 // we want to create a set of derived match-patterns like
627 // `(x as Variant).0 @ P1` and `(x as Variant).1 @ P1`.
628 let elem
= ProjectionElem
::Downcast(adt_def
, variant_index
);
629 let downcast_lvalue
= match_pair
.lvalue
.clone().elem(elem
); // `(x as Variant)`
630 let consequent_match_pairs
=
633 // e.g., `(x as Variant).0`
634 let lvalue
= downcast_lvalue
.clone().field(subpattern
.field
,
635 subpattern
.pattern
.ty
);
636 // e.g., `(x as Variant).0 @ P1`
637 MatchPair
::new(lvalue
, &subpattern
.pattern
)
640 // In addition, we need all the other match pairs from the old candidate.
641 let other_match_pairs
=
642 candidate
.match_pairs
.iter()
644 .filter(|&(index
, _
)| index
!= match_pair_index
)
645 .map(|(_
, mp
)| mp
.clone());
647 let all_match_pairs
= consequent_match_pairs
.chain(other_match_pairs
).collect();
650 span
: candidate
.span
,
651 match_pairs
: all_match_pairs
,
652 bindings
: candidate
.bindings
.clone(),
653 guard
: candidate
.guard
.clone(),
654 arm_index
: candidate
.arm_index
,
658 fn error_simplifyable
<'pat
>(&mut self, match_pair
: &MatchPair
<'pat
, 'tcx
>) -> ! {
659 span_bug
!(match_pair
.pattern
.span
,
660 "simplifyable pattern found: {:?}",
665 fn is_switch_ty
<'tcx
>(ty
: Ty
<'tcx
>) -> bool
{
666 ty
.is_integral() || ty
.is_char() || ty
.is_bool()