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}
;
25 use rustc
::ty
::util
::IntTypeExt
;
27 use rustc
::hir
::RangeEnd
;
29 use std
::cmp
::Ordering
;
31 impl<'a
, 'gcx
, 'tcx
> Builder
<'a
, 'gcx
, 'tcx
> {
32 /// Identifies what test is needed to decide if `match_pair` is applicable.
34 /// It is a bug to call this with a simplifyable pattern.
35 pub fn test
<'pat
>(&mut self, match_pair
: &MatchPair
<'pat
, 'tcx
>) -> Test
<'tcx
> {
36 match *match_pair
.pattern
.kind
{
37 PatternKind
::Variant { ref adt_def, substs: _, variant_index: _, subpatterns: _ }
=> {
39 span
: match_pair
.pattern
.span
,
40 kind
: TestKind
::Switch
{
41 adt_def
: adt_def
.clone(),
42 variants
: BitVector
::new(self.hir
.num_variants(adt_def
)),
47 PatternKind
::Constant { .. }
48 if is_switch_ty(match_pair
.pattern
.ty
) => {
49 // for integers, we use a SwitchInt match, which allows
50 // us to handle more cases
52 span
: match_pair
.pattern
.span
,
53 kind
: TestKind
::SwitchInt
{
54 switch_ty
: match_pair
.pattern
.ty
,
56 // these maps are empty to start; cases are
57 // added below in add_cases_to_switch
64 PatternKind
::Constant { ref value }
=> {
66 span
: match_pair
.pattern
.span
,
69 ty
: match_pair
.pattern
.ty
.clone()
74 PatternKind
::Range { ref lo, ref hi, ref end }
=> {
76 span
: match_pair
.pattern
.span
,
77 kind
: TestKind
::Range
{
78 lo
: Literal
::Value { value: lo.clone() }
,
79 hi
: Literal
::Value { value: hi.clone() }
,
80 ty
: match_pair
.pattern
.ty
.clone(),
86 PatternKind
::Slice { ref prefix, ref slice, ref suffix }
87 if !match_pair
.slice_len_checked
=> {
88 let len
= prefix
.len() + suffix
.len();
89 let op
= if slice
.is_some() {
95 span
: match_pair
.pattern
.span
,
96 kind
: TestKind
::Len { len: len as u64, op: op }
,
100 PatternKind
::Array { .. }
|
101 PatternKind
::Slice { .. }
|
103 PatternKind
::Binding { .. }
|
104 PatternKind
::Leaf { .. }
|
105 PatternKind
::Deref { .. }
=> {
106 self.error_simplifyable(match_pair
)
111 pub fn add_cases_to_switch
<'pat
>(&mut self,
112 test_lvalue
: &Lvalue
<'tcx
>,
113 candidate
: &Candidate
<'pat
, 'tcx
>,
115 options
: &mut Vec
<ConstVal
<'tcx
>>,
116 indices
: &mut FxHashMap
<ConstVal
<'tcx
>, usize>)
119 let match_pair
= match candidate
.match_pairs
.iter().find(|mp
| mp
.lvalue
== *test_lvalue
) {
120 Some(match_pair
) => match_pair
,
121 _
=> { return false; }
124 match *match_pair
.pattern
.kind
{
125 PatternKind
::Constant { ref value }
=> {
126 // if the lvalues match, the type should match
127 assert_eq
!(match_pair
.pattern
.ty
, switch_ty
);
129 indices
.entry(value
.clone())
131 options
.push(value
.clone());
136 PatternKind
::Variant { .. }
=> {
137 panic
!("you should have called add_variants_to_switch instead!");
139 PatternKind
::Range { .. }
|
140 PatternKind
::Slice { .. }
|
141 PatternKind
::Array { .. }
|
143 PatternKind
::Binding { .. }
|
144 PatternKind
::Leaf { .. }
|
145 PatternKind
::Deref { .. }
=> {
146 // don't know how to add these patterns to a switch
152 pub fn add_variants_to_switch
<'pat
>(&mut self,
153 test_lvalue
: &Lvalue
<'tcx
>,
154 candidate
: &Candidate
<'pat
, 'tcx
>,
155 variants
: &mut BitVector
)
158 let match_pair
= match candidate
.match_pairs
.iter().find(|mp
| mp
.lvalue
== *test_lvalue
) {
159 Some(match_pair
) => match_pair
,
160 _
=> { return false; }
163 match *match_pair
.pattern
.kind
{
164 PatternKind
::Variant { adt_def: _ , variant_index, .. }
=> {
165 // We have a pattern testing for variant `variant_index`
166 // set the corresponding index to true
167 variants
.insert(variant_index
);
171 // don't know how to add these patterns to a switch
177 /// Generates the code to perform a test.
178 pub fn perform_test(&mut self,
180 lvalue
: &Lvalue
<'tcx
>,
183 let source_info
= self.source_info(test
.span
);
185 TestKind
::Switch { adt_def, ref variants }
=> {
186 // Variants is a BitVec of indexes into adt_def.variants.
187 let num_enum_variants
= self.hir
.num_variants(adt_def
);
188 let used_variants
= variants
.count();
189 let mut otherwise_block
= None
;
190 let mut target_blocks
= Vec
::with_capacity(num_enum_variants
);
191 let mut targets
= Vec
::with_capacity(used_variants
+ 1);
192 let mut values
= Vec
::with_capacity(used_variants
);
193 let tcx
= self.hir
.tcx();
194 for (idx
, discr
) in adt_def
.discriminants(tcx
).enumerate() {
195 target_blocks
.place_back() <- if variants
.contains(idx
) {
197 *(targets
.place_back() <- self.cfg
.start_new_block())
199 if otherwise_block
.is_none() {
200 otherwise_block
= Some(self.cfg
.start_new_block());
202 otherwise_block
.unwrap()
205 if let Some(otherwise_block
) = otherwise_block
{
206 targets
.push(otherwise_block
);
210 debug
!("num_enum_variants: {}, tested variants: {:?}, variants: {:?}",
211 num_enum_variants
, values
, variants
);
212 let discr_ty
= adt_def
.repr
.discr_type().to_ty(tcx
);
213 let discr
= self.temp(discr_ty
);
214 self.cfg
.push_assign(block
, source_info
, &discr
,
215 Rvalue
::Discriminant(lvalue
.clone()));
216 assert_eq
!(values
.len() + 1, targets
.len());
217 self.cfg
.terminate(block
, source_info
, TerminatorKind
::SwitchInt
{
218 discr
: Operand
::Consume(discr
),
220 values
: From
::from(values
),
226 TestKind
::SwitchInt { switch_ty, ref options, indices: _ }
=> {
227 let (ret
, terminator
) = if switch_ty
.sty
== ty
::TyBool
{
228 assert
!(options
.len() > 0 && options
.len() <= 2);
229 let (true_bb
, false_bb
) = (self.cfg
.start_new_block(),
230 self.cfg
.start_new_block());
231 let ret
= match &options
[0] {
232 &ConstVal
::Bool(true) => vec
![true_bb
, false_bb
],
233 &ConstVal
::Bool(false) => vec
![false_bb
, true_bb
],
234 v
=> span_bug
!(test
.span
, "expected boolean value but got {:?}", v
)
236 (ret
, TerminatorKind
::if_(self.hir
.tcx(), Operand
::Consume(lvalue
.clone()),
239 // The switch may be inexhaustive so we
240 // add a catch all block
241 let otherwise
= self.cfg
.start_new_block();
242 let targets
: Vec
<_
> =
244 .map(|_
| self.cfg
.start_new_block())
245 .chain(Some(otherwise
))
247 let values
: Vec
<_
> = options
.iter().map(|v
|
248 v
.to_const_int().expect("switching on integral")
250 (targets
.clone(), TerminatorKind
::SwitchInt
{
251 discr
: Operand
::Consume(lvalue
.clone()),
252 switch_ty
: switch_ty
,
253 values
: From
::from(values
),
257 self.cfg
.terminate(block
, source_info
, terminator
);
261 TestKind
::Eq { ref value, mut ty }
=> {
262 let mut val
= Operand
::Consume(lvalue
.clone());
264 // If we're using b"..." as a pattern, we need to insert an
265 // unsizing coercion, as the byte string has the type &[u8; N].
266 let expect
= if let ConstVal
::ByteStr(ref bytes
) = *value
{
267 let tcx
= self.hir
.tcx();
269 // Unsize the lvalue to &[u8], too, if necessary.
270 if let ty
::TyRef(region
, mt
) = ty
.sty
{
271 if let ty
::TyArray(_
, _
) = mt
.ty
.sty
{
272 ty
= tcx
.mk_imm_ref(region
, tcx
.mk_slice(tcx
.types
.u8));
273 let val_slice
= self.temp(ty
);
274 self.cfg
.push_assign(block
, source_info
, &val_slice
,
275 Rvalue
::Cast(CastKind
::Unsize
, val
, ty
));
276 val
= Operand
::Consume(val_slice
);
280 assert
!(ty
.is_slice());
282 let array_ty
= tcx
.mk_array(tcx
.types
.u8, bytes
.len());
283 let array_ref
= tcx
.mk_imm_ref(tcx
.mk_region(ty
::ReStatic
), array_ty
);
284 let array
= self.literal_operand(test
.span
, array_ref
, Literal
::Value
{
288 let slice
= self.temp(ty
);
289 self.cfg
.push_assign(block
, source_info
, &slice
,
290 Rvalue
::Cast(CastKind
::Unsize
, array
, ty
));
291 Operand
::Consume(slice
)
293 self.literal_operand(test
.span
, ty
, Literal
::Value
{
298 // Use PartialEq::eq for &str and &[u8] slices, instead of BinOp::Eq.
299 let fail
= self.cfg
.start_new_block();
300 if let ty
::TyRef(_
, mt
) = ty
.sty
{
301 assert
!(ty
.is_slice());
302 let eq_def_id
= self.hir
.tcx().lang_items
.eq_trait().unwrap();
304 let (mty
, method
) = self.hir
.trait_method(eq_def_id
, "eq", ty
, &[ty
]);
306 let bool_ty
= self.hir
.bool_ty();
307 let eq_result
= self.temp(bool_ty
);
308 let eq_block
= self.cfg
.start_new_block();
309 let cleanup
= self.diverge_cleanup();
310 self.cfg
.terminate(block
, source_info
, TerminatorKind
::Call
{
311 func
: Operand
::Constant(Constant
{
316 args
: vec
![val
, expect
],
317 destination
: Some((eq_result
.clone(), eq_block
)),
322 let block
= self.cfg
.start_new_block();
323 self.cfg
.terminate(eq_block
, source_info
,
324 TerminatorKind
::if_(self.hir
.tcx(),
325 Operand
::Consume(eq_result
),
329 let block
= self.compare(block
, fail
, test
.span
, BinOp
::Eq
, expect
, val
);
334 TestKind
::Range { ref lo, ref hi, ty, ref end }
=> {
335 // Test `val` by computing `lo <= val && val <= hi`, using primitive comparisons.
336 let lo
= self.literal_operand(test
.span
, ty
.clone(), lo
.clone());
337 let hi
= self.literal_operand(test
.span
, ty
.clone(), hi
.clone());
338 let val
= Operand
::Consume(lvalue
.clone());
340 let fail
= self.cfg
.start_new_block();
341 let block
= self.compare(block
, fail
, test
.span
, BinOp
::Le
, lo
, val
.clone());
342 let block
= match *end
{
343 RangeEnd
::Included
=> self.compare(block
, fail
, test
.span
, BinOp
::Le
, val
, hi
),
344 RangeEnd
::Excluded
=> self.compare(block
, fail
, test
.span
, BinOp
::Lt
, val
, hi
),
350 TestKind
::Len { len, op }
=> {
351 let (usize_ty
, bool_ty
) = (self.hir
.usize_ty(), self.hir
.bool_ty());
352 let (actual
, result
) = (self.temp(usize_ty
), self.temp(bool_ty
));
354 // actual = len(lvalue)
355 self.cfg
.push_assign(block
, source_info
,
356 &actual
, Rvalue
::Len(lvalue
.clone()));
359 let expected
= self.push_usize(block
, source_info
, len
);
361 // result = actual == expected OR result = actual < expected
362 self.cfg
.push_assign(block
, source_info
, &result
,
364 Operand
::Consume(actual
),
365 Operand
::Consume(expected
)));
367 // branch based on result
368 let (false_bb
, true_bb
) = (self.cfg
.start_new_block(),
369 self.cfg
.start_new_block());
370 self.cfg
.terminate(block
, source_info
,
371 TerminatorKind
::if_(self.hir
.tcx(), Operand
::Consume(result
),
373 vec
![true_bb
, false_bb
]
378 fn compare(&mut self,
380 fail_block
: BasicBlock
,
384 right
: Operand
<'tcx
>) -> BasicBlock
{
385 let bool_ty
= self.hir
.bool_ty();
386 let result
= self.temp(bool_ty
);
388 // result = op(left, right)
389 let source_info
= self.source_info(span
);
390 self.cfg
.push_assign(block
, source_info
, &result
,
391 Rvalue
::BinaryOp(op
, left
, right
));
393 // branch based on result
394 let target_block
= self.cfg
.start_new_block();
395 self.cfg
.terminate(block
, source_info
,
396 TerminatorKind
::if_(self.hir
.tcx(), Operand
::Consume(result
),
397 target_block
, fail_block
));
401 /// Given that we are performing `test` against `test_lvalue`,
402 /// this job sorts out what the status of `candidate` will be
403 /// after the test. The `resulting_candidates` vector stores, for
404 /// each possible outcome of `test`, a vector of the candidates
405 /// that will result. This fn should add a (possibly modified)
406 /// clone of candidate into `resulting_candidates` wherever
409 /// So, for example, if this candidate is `x @ Some(P0)` and the
410 /// test is a variant test, then we would add `(x as Option).0 @
411 /// P0` to the `resulting_candidates` entry corresponding to the
414 /// However, in some cases, the test may just not be relevant to
415 /// candidate. For example, suppose we are testing whether `foo.x == 22`,
416 /// but in one match arm we have `Foo { x: _, ... }`... in that case,
417 /// the test for what value `x` has has no particular relevance
418 /// to this candidate. In such cases, this function just returns false
419 /// without doing anything. This is used by the overall `match_candidates`
420 /// algorithm to structure the match as a whole. See `match_candidates` for
423 /// FIXME(#29623). In some cases, we have some tricky choices to
424 /// make. for example, if we are testing that `x == 22`, but the
425 /// candidate is `x @ 13..55`, what should we do? In the event
426 /// that the test is true, we know that the candidate applies, but
427 /// in the event of false, we don't know that it *doesn't*
428 /// apply. For now, we return false, indicate that the test does
429 /// not apply to this candidate, but it might be we can get
430 /// tighter match code if we do something a bit different.
431 pub fn sort_candidate
<'pat
>(&mut self,
432 test_lvalue
: &Lvalue
<'tcx
>,
434 candidate
: &Candidate
<'pat
, 'tcx
>,
435 resulting_candidates
: &mut [Vec
<Candidate
<'pat
, 'tcx
>>])
437 // Find the match_pair for this lvalue (if any). At present,
438 // afaik, there can be at most one. (In the future, if we
439 // adopted a more general `@` operator, there might be more
440 // than one, but it'd be very unusual to have two sides that
441 // both require tests; you'd expect one side to be simplified
443 let tested_match_pair
= candidate
.match_pairs
.iter()
445 .filter(|&(_
, mp
)| mp
.lvalue
== *test_lvalue
)
447 let (match_pair_index
, match_pair
) = match tested_match_pair
{
450 // We are not testing this lvalue. Therefore, this
451 // candidate applies to ALL outcomes.
456 match (&test
.kind
, &*match_pair
.pattern
.kind
) {
457 // If we are performing a variant switch, then this
458 // informs variant patterns, but nothing else.
459 (&TestKind
::Switch { adt_def: tested_adt_def, .. }
,
460 &PatternKind
::Variant { adt_def, variant_index, ref subpatterns, .. }
) => {
461 assert_eq
!(adt_def
, tested_adt_def
);
463 self.candidate_after_variant_switch(match_pair_index
,
468 resulting_candidates
[variant_index
].push(new_candidate
);
471 (&TestKind
::Switch { .. }
, _
) => false,
473 // If we are performing a switch over integers, then this informs integer
474 // equality, but nothing else.
476 // FIXME(#29623) we could use PatternKind::Range to rule
477 // things out here, in some cases.
478 (&TestKind
::SwitchInt { switch_ty: _, options: _, ref indices }
,
479 &PatternKind
::Constant { ref value }
)
480 if is_switch_ty(match_pair
.pattern
.ty
) => {
481 let index
= indices
[value
];
482 let new_candidate
= self.candidate_without_match_pair(match_pair_index
,
484 resulting_candidates
[index
].push(new_candidate
);
487 (&TestKind
::SwitchInt { .. }
, _
) => false,
490 (&TestKind
::Len { len: test_len, op: BinOp::Eq }
,
491 &PatternKind
::Slice { ref prefix, ref slice, ref suffix }
) => {
492 let pat_len
= (prefix
.len() + suffix
.len()) as u64;
493 match (test_len
.cmp(&pat_len
), slice
) {
494 (Ordering
::Equal
, &None
) => {
495 // on true, min_len = len = $actual_length,
496 // on false, len != $actual_length
497 resulting_candidates
[0].push(
498 self.candidate_after_slice_test(match_pair_index
,
506 (Ordering
::Less
, _
) => {
507 // test_len < pat_len. If $actual_len = test_len,
508 // then $actual_len < pat_len and we don't have
510 resulting_candidates
[1].push(candidate
.clone());
513 (Ordering
::Equal
, &Some(_
)) | (Ordering
::Greater
, &Some(_
)) => {
514 // This can match both if $actual_len = test_len >= pat_len,
515 // and if $actual_len > test_len. We can't advance.
518 (Ordering
::Greater
, &None
) => {
519 // test_len != pat_len, so if $actual_len = test_len, then
520 // $actual_len != pat_len.
521 resulting_candidates
[1].push(candidate
.clone());
527 (&TestKind
::Len { len: test_len, op: BinOp::Ge }
,
528 &PatternKind
::Slice { ref prefix, ref slice, ref suffix }
) => {
529 // the test is `$actual_len >= test_len`
530 let pat_len
= (prefix
.len() + suffix
.len()) as u64;
531 match (test_len
.cmp(&pat_len
), slice
) {
532 (Ordering
::Equal
, &Some(_
)) => {
533 // $actual_len >= test_len = pat_len,
535 resulting_candidates
[0].push(
536 self.candidate_after_slice_test(match_pair_index
,
544 (Ordering
::Less
, _
) | (Ordering
::Equal
, &None
) => {
545 // test_len <= pat_len. If $actual_len < test_len,
546 // then it is also < pat_len, so the test passing is
547 // necessary (but insufficient).
548 resulting_candidates
[0].push(candidate
.clone());
551 (Ordering
::Greater
, &None
) => {
552 // test_len > pat_len. If $actual_len >= test_len > pat_len,
553 // then we know we won't have a match.
554 resulting_candidates
[1].push(candidate
.clone());
557 (Ordering
::Greater
, &Some(_
)) => {
558 // test_len < pat_len, and is therefore less
559 // strict. This can still go both ways.
565 (&TestKind
::Eq { .. }
, _
) |
566 (&TestKind
::Range { .. }
, _
) |
567 (&TestKind
::Len { .. }
, _
) => {
568 // These are all binary tests.
570 // FIXME(#29623) we can be more clever here
571 let pattern_test
= self.test(&match_pair
);
572 if pattern_test
.kind
== test
.kind
{
573 let new_candidate
= self.candidate_without_match_pair(match_pair_index
,
575 resulting_candidates
[0].push(new_candidate
);
584 fn candidate_without_match_pair
<'pat
>(&mut self,
585 match_pair_index
: usize,
586 candidate
: &Candidate
<'pat
, 'tcx
>)
587 -> Candidate
<'pat
, 'tcx
> {
588 let other_match_pairs
=
589 candidate
.match_pairs
.iter()
591 .filter(|&(index
, _
)| index
!= match_pair_index
)
592 .map(|(_
, mp
)| mp
.clone())
595 span
: candidate
.span
,
596 match_pairs
: other_match_pairs
,
597 bindings
: candidate
.bindings
.clone(),
598 guard
: candidate
.guard
.clone(),
599 arm_index
: candidate
.arm_index
,
603 fn candidate_after_slice_test
<'pat
>(&mut self,
604 match_pair_index
: usize,
605 candidate
: &Candidate
<'pat
, 'tcx
>,
606 prefix
: &'pat
[Pattern
<'tcx
>],
607 opt_slice
: Option
<&'pat Pattern
<'tcx
>>,
608 suffix
: &'pat
[Pattern
<'tcx
>])
609 -> Candidate
<'pat
, 'tcx
> {
610 let mut new_candidate
=
611 self.candidate_without_match_pair(match_pair_index
, candidate
);
612 self.prefix_slice_suffix(
613 &mut new_candidate
.match_pairs
,
614 &candidate
.match_pairs
[match_pair_index
].lvalue
,
622 fn candidate_after_variant_switch
<'pat
>(&mut self,
623 match_pair_index
: usize,
624 adt_def
: &'tcx ty
::AdtDef
,
625 variant_index
: usize,
626 subpatterns
: &'pat
[FieldPattern
<'tcx
>],
627 candidate
: &Candidate
<'pat
, 'tcx
>)
628 -> Candidate
<'pat
, 'tcx
> {
629 let match_pair
= &candidate
.match_pairs
[match_pair_index
];
631 // So, if we have a match-pattern like `x @ Enum::Variant(P1, P2)`,
632 // we want to create a set of derived match-patterns like
633 // `(x as Variant).0 @ P1` and `(x as Variant).1 @ P1`.
634 let elem
= ProjectionElem
::Downcast(adt_def
, variant_index
);
635 let downcast_lvalue
= match_pair
.lvalue
.clone().elem(elem
); // `(x as Variant)`
636 let consequent_match_pairs
=
639 // e.g., `(x as Variant).0`
640 let lvalue
= downcast_lvalue
.clone().field(subpattern
.field
,
641 subpattern
.pattern
.ty
);
642 // e.g., `(x as Variant).0 @ P1`
643 MatchPair
::new(lvalue
, &subpattern
.pattern
)
646 // In addition, we need all the other match pairs from the old candidate.
647 let other_match_pairs
=
648 candidate
.match_pairs
.iter()
650 .filter(|&(index
, _
)| index
!= match_pair_index
)
651 .map(|(_
, mp
)| mp
.clone());
653 let all_match_pairs
= consequent_match_pairs
.chain(other_match_pairs
).collect();
656 span
: candidate
.span
,
657 match_pairs
: all_match_pairs
,
658 bindings
: candidate
.bindings
.clone(),
659 guard
: candidate
.guard
.clone(),
660 arm_index
: candidate
.arm_index
,
664 fn error_simplifyable
<'pat
>(&mut self, match_pair
: &MatchPair
<'pat
, 'tcx
>) -> ! {
665 span_bug
!(match_pair
.pattern
.span
,
666 "simplifyable pattern found: {:?}",
671 fn is_switch_ty
<'tcx
>(ty
: Ty
<'tcx
>) -> bool
{
672 ty
.is_integral() || ty
.is_char() || ty
.is_bool()