]>
Commit | Line | Data |
---|---|---|
e9174d1e SL |
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. | |
4 | // | |
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. | |
10 | ||
11 | // Testing candidates | |
12 | // | |
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. | |
17 | ||
92a42be0 | 18 | use build::Builder; |
e9174d1e SL |
19 | use build::matches::{Candidate, MatchPair, Test, TestKind}; |
20 | use hair::*; | |
476ff2be | 21 | use rustc_data_structures::fx::FxHashMap; |
3157f602 | 22 | use rustc_data_structures::bitvec::BitVector; |
54a0048b | 23 | use rustc::ty::{self, Ty}; |
8bb4bdeb | 24 | use rustc::ty::util::IntTypeExt; |
c30ab7b3 | 25 | use rustc::mir::*; |
0531ce1d | 26 | use rustc::hir::{RangeEnd, Mutability}; |
3157f602 XL |
27 | use syntax_pos::Span; |
28 | use std::cmp::Ordering; | |
e9174d1e | 29 | |
a7813a04 | 30 | impl<'a, 'gcx, 'tcx> Builder<'a, 'gcx, 'tcx> { |
e9174d1e SL |
31 | /// Identifies what test is needed to decide if `match_pair` is applicable. |
32 | /// | |
33 | /// It is a bug to call this with a simplifyable pattern. | |
92a42be0 SL |
34 | pub fn test<'pat>(&mut self, match_pair: &MatchPair<'pat, 'tcx>) -> Test<'tcx> { |
35 | match *match_pair.pattern.kind { | |
32a655c1 | 36 | PatternKind::Variant { ref adt_def, substs: _, variant_index: _, subpatterns: _ } => { |
e9174d1e SL |
37 | Test { |
38 | span: match_pair.pattern.span, | |
3157f602 XL |
39 | kind: TestKind::Switch { |
40 | adt_def: adt_def.clone(), | |
ff7c6d11 | 41 | variants: BitVector::new(adt_def.variants.len()), |
3157f602 | 42 | }, |
e9174d1e SL |
43 | } |
44 | } | |
45 | ||
9cc50fc6 | 46 | PatternKind::Constant { .. } |
92a42be0 SL |
47 | if is_switch_ty(match_pair.pattern.ty) => { |
48 | // for integers, we use a SwitchInt match, which allows | |
49 | // us to handle more cases | |
50 | Test { | |
51 | span: match_pair.pattern.span, | |
52 | kind: TestKind::SwitchInt { | |
53 | switch_ty: match_pair.pattern.ty, | |
54 | ||
55 | // these maps are empty to start; cases are | |
56 | // added below in add_cases_to_switch | |
57 | options: vec![], | |
476ff2be | 58 | indices: FxHashMap(), |
92a42be0 SL |
59 | } |
60 | } | |
61 | } | |
62 | ||
ea8adc8c | 63 | PatternKind::Constant { value } => { |
e9174d1e SL |
64 | Test { |
65 | span: match_pair.pattern.span, | |
b039eaaf | 66 | kind: TestKind::Eq { |
ea8adc8c | 67 | value, |
9cc50fc6 | 68 | ty: match_pair.pattern.ty.clone() |
92a42be0 | 69 | } |
e9174d1e SL |
70 | } |
71 | } | |
72 | ||
ea8adc8c | 73 | PatternKind::Range { lo, hi, end } => { |
e9174d1e SL |
74 | Test { |
75 | span: match_pair.pattern.span, | |
b039eaaf | 76 | kind: TestKind::Range { |
ea8adc8c XL |
77 | lo: Literal::Value { value: lo }, |
78 | hi: Literal::Value { value: hi }, | |
b039eaaf | 79 | ty: match_pair.pattern.ty.clone(), |
ea8adc8c | 80 | end, |
b039eaaf | 81 | }, |
e9174d1e SL |
82 | } |
83 | } | |
84 | ||
54a0048b SL |
85 | PatternKind::Slice { ref prefix, ref slice, ref suffix } |
86 | if !match_pair.slice_len_checked => { | |
e9174d1e | 87 | let len = prefix.len() + suffix.len(); |
b039eaaf SL |
88 | let op = if slice.is_some() { |
89 | BinOp::Ge | |
90 | } else { | |
91 | BinOp::Eq | |
92 | }; | |
e9174d1e SL |
93 | Test { |
94 | span: match_pair.pattern.span, | |
54a0048b | 95 | kind: TestKind::Len { len: len as u64, op: op }, |
e9174d1e SL |
96 | } |
97 | } | |
98 | ||
99 | PatternKind::Array { .. } | | |
54a0048b | 100 | PatternKind::Slice { .. } | |
e9174d1e SL |
101 | PatternKind::Wild | |
102 | PatternKind::Binding { .. } | | |
103 | PatternKind::Leaf { .. } | | |
104 | PatternKind::Deref { .. } => { | |
105 | self.error_simplifyable(match_pair) | |
106 | } | |
107 | } | |
108 | } | |
109 | ||
92a42be0 | 110 | pub fn add_cases_to_switch<'pat>(&mut self, |
ff7c6d11 | 111 | test_place: &Place<'tcx>, |
92a42be0 SL |
112 | candidate: &Candidate<'pat, 'tcx>, |
113 | switch_ty: Ty<'tcx>, | |
0531ce1d | 114 | options: &mut Vec<u128>, |
ea8adc8c | 115 | indices: &mut FxHashMap<&'tcx ty::Const<'tcx>, usize>) |
92a42be0 SL |
116 | -> bool |
117 | { | |
ff7c6d11 | 118 | let match_pair = match candidate.match_pairs.iter().find(|mp| mp.place == *test_place) { |
92a42be0 SL |
119 | Some(match_pair) => match_pair, |
120 | _ => { return false; } | |
121 | }; | |
122 | ||
123 | match *match_pair.pattern.kind { | |
ea8adc8c | 124 | PatternKind::Constant { value } => { |
ff7c6d11 | 125 | // if the places match, the type should match |
92a42be0 SL |
126 | assert_eq!(match_pair.pattern.ty, switch_ty); |
127 | ||
ea8adc8c | 128 | indices.entry(value) |
92a42be0 | 129 | .or_insert_with(|| { |
0531ce1d | 130 | options.push(value.val.to_raw_bits().expect("switching on int")); |
92a42be0 SL |
131 | options.len() - 1 |
132 | }); | |
133 | true | |
134 | } | |
3157f602 XL |
135 | PatternKind::Variant { .. } => { |
136 | panic!("you should have called add_variants_to_switch instead!"); | |
137 | } | |
92a42be0 | 138 | PatternKind::Range { .. } | |
92a42be0 SL |
139 | PatternKind::Slice { .. } | |
140 | PatternKind::Array { .. } | | |
141 | PatternKind::Wild | | |
142 | PatternKind::Binding { .. } | | |
143 | PatternKind::Leaf { .. } | | |
144 | PatternKind::Deref { .. } => { | |
145 | // don't know how to add these patterns to a switch | |
146 | false | |
147 | } | |
148 | } | |
149 | } | |
150 | ||
3157f602 | 151 | pub fn add_variants_to_switch<'pat>(&mut self, |
ff7c6d11 | 152 | test_place: &Place<'tcx>, |
3157f602 XL |
153 | candidate: &Candidate<'pat, 'tcx>, |
154 | variants: &mut BitVector) | |
155 | -> bool | |
156 | { | |
ff7c6d11 | 157 | let match_pair = match candidate.match_pairs.iter().find(|mp| mp.place == *test_place) { |
3157f602 XL |
158 | Some(match_pair) => match_pair, |
159 | _ => { return false; } | |
160 | }; | |
161 | ||
162 | match *match_pair.pattern.kind { | |
163 | PatternKind::Variant { adt_def: _ , variant_index, .. } => { | |
164 | // We have a pattern testing for variant `variant_index` | |
165 | // set the corresponding index to true | |
166 | variants.insert(variant_index); | |
167 | true | |
168 | } | |
169 | _ => { | |
170 | // don't know how to add these patterns to a switch | |
171 | false | |
172 | } | |
173 | } | |
174 | } | |
175 | ||
e9174d1e SL |
176 | /// Generates the code to perform a test. |
177 | pub fn perform_test(&mut self, | |
178 | block: BasicBlock, | |
ff7c6d11 | 179 | place: &Place<'tcx>, |
b039eaaf | 180 | test: &Test<'tcx>) |
e9174d1e | 181 | -> Vec<BasicBlock> { |
ff7c6d11 XL |
182 | debug!("perform_test({:?}, {:?}: {:?}, {:?})", |
183 | block, | |
184 | place, | |
185 | place.ty(&self.local_decls, self.hir.tcx()), | |
186 | test); | |
3157f602 | 187 | let source_info = self.source_info(test.span); |
92a42be0 | 188 | match test.kind { |
3157f602 | 189 | TestKind::Switch { adt_def, ref variants } => { |
8bb4bdeb | 190 | // Variants is a BitVec of indexes into adt_def.variants. |
ff7c6d11 | 191 | let num_enum_variants = adt_def.variants.len(); |
8bb4bdeb | 192 | let used_variants = variants.count(); |
3157f602 | 193 | let mut otherwise_block = None; |
8bb4bdeb XL |
194 | let mut target_blocks = Vec::with_capacity(num_enum_variants); |
195 | let mut targets = Vec::with_capacity(used_variants + 1); | |
196 | let mut values = Vec::with_capacity(used_variants); | |
197 | let tcx = self.hir.tcx(); | |
198 | for (idx, discr) in adt_def.discriminants(tcx).enumerate() { | |
199 | target_blocks.place_back() <- if variants.contains(idx) { | |
0531ce1d | 200 | values.push(discr.val); |
8bb4bdeb | 201 | *(targets.place_back() <- self.cfg.start_new_block()) |
3157f602 XL |
202 | } else { |
203 | if otherwise_block.is_none() { | |
204 | otherwise_block = Some(self.cfg.start_new_block()); | |
205 | } | |
206 | otherwise_block.unwrap() | |
8bb4bdeb XL |
207 | }; |
208 | } | |
209 | if let Some(otherwise_block) = otherwise_block { | |
210 | targets.push(otherwise_block); | |
211 | } else { | |
abe05a73 | 212 | targets.push(self.unreachable_block()); |
8bb4bdeb XL |
213 | } |
214 | debug!("num_enum_variants: {}, tested variants: {:?}, variants: {:?}", | |
215 | num_enum_variants, values, variants); | |
216 | let discr_ty = adt_def.repr.discr_type().to_ty(tcx); | |
cc61c64b | 217 | let discr = self.temp(discr_ty, test.span); |
8bb4bdeb | 218 | self.cfg.push_assign(block, source_info, &discr, |
ff7c6d11 | 219 | Rvalue::Discriminant(place.clone())); |
8bb4bdeb XL |
220 | assert_eq!(values.len() + 1, targets.len()); |
221 | self.cfg.terminate(block, source_info, TerminatorKind::SwitchInt { | |
ff7c6d11 | 222 | discr: Operand::Move(discr), |
8bb4bdeb XL |
223 | switch_ty: discr_ty, |
224 | values: From::from(values), | |
3b2f2976 | 225 | targets, |
e9174d1e SL |
226 | }); |
227 | target_blocks | |
228 | } | |
229 | ||
92a42be0 | 230 | TestKind::SwitchInt { switch_ty, ref options, indices: _ } => { |
8bb4bdeb XL |
231 | let (ret, terminator) = if switch_ty.sty == ty::TyBool { |
232 | assert!(options.len() > 0 && options.len() <= 2); | |
233 | let (true_bb, false_bb) = (self.cfg.start_new_block(), | |
234 | self.cfg.start_new_block()); | |
0531ce1d XL |
235 | let ret = match options[0] { |
236 | 1 => vec![true_bb, false_bb], | |
237 | 0 => vec![false_bb, true_bb], | |
8bb4bdeb XL |
238 | v => span_bug!(test.span, "expected boolean value but got {:?}", v) |
239 | }; | |
ff7c6d11 | 240 | (ret, TerminatorKind::if_(self.hir.tcx(), Operand::Copy(place.clone()), |
8bb4bdeb XL |
241 | true_bb, false_bb)) |
242 | } else { | |
243 | // The switch may be inexhaustive so we | |
244 | // add a catch all block | |
245 | let otherwise = self.cfg.start_new_block(); | |
246 | let targets: Vec<_> = | |
247 | options.iter() | |
248 | .map(|_| self.cfg.start_new_block()) | |
249 | .chain(Some(otherwise)) | |
250 | .collect(); | |
8bb4bdeb | 251 | (targets.clone(), TerminatorKind::SwitchInt { |
ff7c6d11 | 252 | discr: Operand::Copy(place.clone()), |
3b2f2976 | 253 | switch_ty, |
0531ce1d | 254 | values: options.clone().into(), |
3b2f2976 | 255 | targets, |
8bb4bdeb | 256 | }) |
3157f602 | 257 | }; |
8bb4bdeb XL |
258 | self.cfg.terminate(block, source_info, terminator); |
259 | ret | |
92a42be0 SL |
260 | } |
261 | ||
0531ce1d | 262 | TestKind::Eq { value, mut ty } => { |
ff7c6d11 | 263 | let mut val = Operand::Copy(place.clone()); |
0531ce1d XL |
264 | let mut expect = self.literal_operand(test.span, ty, Literal::Value { |
265 | value | |
266 | }); | |
267 | // Use PartialEq::eq instead of BinOp::Eq | |
268 | // (the binop can only handle primitives) | |
9cc50fc6 | 269 | let fail = self.cfg.start_new_block(); |
0531ce1d XL |
270 | if !ty.is_scalar() { |
271 | // If we're using b"..." as a pattern, we need to insert an | |
272 | // unsizing coercion, as the byte string has the type &[u8; N]. | |
273 | // | |
274 | // We want to do this even when the scrutinee is a reference to an | |
275 | // array, so we can call `<[u8]>::eq` rather than having to find an | |
276 | // `<[u8; N]>::eq`. | |
277 | let unsize = |ty: Ty<'tcx>| match ty.sty { | |
278 | ty::TyRef(region, tam) => match tam.ty.sty { | |
279 | ty::TyArray(inner_ty, n) => Some((region, inner_ty, n)), | |
280 | _ => None, | |
281 | }, | |
282 | _ => None, | |
283 | }; | |
284 | let opt_ref_ty = unsize(ty); | |
285 | let opt_ref_test_ty = unsize(value.ty); | |
286 | let mut place = place.clone(); | |
287 | match (opt_ref_ty, opt_ref_test_ty) { | |
288 | // nothing to do, neither is an array | |
289 | (None, None) => {}, | |
290 | (Some((region, elem_ty, _)), _) | | |
291 | (None, Some((region, elem_ty, _))) => { | |
292 | let tcx = self.hir.tcx(); | |
293 | // make both a slice | |
294 | ty = tcx.mk_imm_ref(region, tcx.mk_slice(elem_ty)); | |
295 | if opt_ref_ty.is_some() { | |
296 | place = self.temp(ty, test.span); | |
297 | self.cfg.push_assign(block, source_info, &place, | |
298 | Rvalue::Cast(CastKind::Unsize, val, ty)); | |
299 | } | |
300 | if opt_ref_test_ty.is_some() { | |
301 | let array = self.literal_operand( | |
302 | test.span, | |
303 | value.ty, | |
304 | Literal::Value { | |
305 | value | |
306 | }, | |
307 | ); | |
308 | ||
309 | let slice = self.temp(ty, test.span); | |
310 | self.cfg.push_assign(block, source_info, &slice, | |
311 | Rvalue::Cast(CastKind::Unsize, array, ty)); | |
312 | expect = Operand::Move(slice); | |
313 | } | |
314 | }, | |
315 | } | |
ea8adc8c | 316 | let eq_def_id = self.hir.tcx().lang_items().eq_trait().unwrap(); |
9e0c209e | 317 | let (mty, method) = self.hir.trait_method(eq_def_id, "eq", ty, &[ty]); |
54a0048b | 318 | |
0531ce1d XL |
319 | // take the argument by reference |
320 | let region_scope = self.topmost_scope(); | |
321 | let region = self.hir.tcx().mk_region(ty::ReScope(region_scope)); | |
322 | let tam = ty::TypeAndMut { | |
323 | ty, | |
324 | mutbl: Mutability::MutImmutable, | |
325 | }; | |
326 | let ref_ty = self.hir.tcx().mk_ref(region, tam); | |
327 | ||
328 | // let lhs_ref_place = &lhs; | |
329 | let ref_rvalue = Rvalue::Ref(region, BorrowKind::Shared, place.clone()); | |
330 | let lhs_ref_place = self.temp(ref_ty, test.span); | |
331 | self.cfg.push_assign(block, source_info, &lhs_ref_place, ref_rvalue); | |
332 | let val = Operand::Move(lhs_ref_place); | |
333 | ||
334 | // let rhs_place = rhs; | |
335 | let rhs_place = self.temp(ty, test.span); | |
336 | self.cfg.push_assign(block, source_info, &rhs_place, Rvalue::Use(expect)); | |
337 | ||
338 | // let rhs_ref_place = &rhs_place; | |
339 | let ref_rvalue = Rvalue::Ref(region, BorrowKind::Shared, rhs_place); | |
340 | let rhs_ref_place = self.temp(ref_ty, test.span); | |
341 | self.cfg.push_assign(block, source_info, &rhs_ref_place, ref_rvalue); | |
342 | let expect = Operand::Move(rhs_ref_place); | |
343 | ||
54a0048b | 344 | let bool_ty = self.hir.bool_ty(); |
cc61c64b | 345 | let eq_result = self.temp(bool_ty, test.span); |
54a0048b | 346 | let eq_block = self.cfg.start_new_block(); |
3b2f2976 | 347 | let cleanup = self.diverge_cleanup(); |
3157f602 | 348 | self.cfg.terminate(block, source_info, TerminatorKind::Call { |
cc61c64b | 349 | func: Operand::Constant(box Constant { |
54a0048b SL |
350 | span: test.span, |
351 | ty: mty, | |
352 | literal: method | |
353 | }), | |
354 | args: vec![val, expect], | |
355 | destination: Some((eq_result.clone(), eq_block)), | |
ff7c6d11 | 356 | cleanup: Some(cleanup), |
54a0048b SL |
357 | }); |
358 | ||
359 | // check the result | |
360 | let block = self.cfg.start_new_block(); | |
8bb4bdeb XL |
361 | self.cfg.terminate(eq_block, source_info, |
362 | TerminatorKind::if_(self.hir.tcx(), | |
ff7c6d11 | 363 | Operand::Move(eq_result), |
8bb4bdeb | 364 | block, fail)); |
54a0048b SL |
365 | vec![block, fail] |
366 | } else { | |
367 | let block = self.compare(block, fail, test.span, BinOp::Eq, expect, val); | |
368 | vec![block, fail] | |
369 | } | |
e9174d1e SL |
370 | } |
371 | ||
32a655c1 | 372 | TestKind::Range { ref lo, ref hi, ty, ref end } => { |
9cc50fc6 | 373 | // Test `val` by computing `lo <= val && val <= hi`, using primitive comparisons. |
92a42be0 SL |
374 | let lo = self.literal_operand(test.span, ty.clone(), lo.clone()); |
375 | let hi = self.literal_operand(test.span, ty.clone(), hi.clone()); | |
ff7c6d11 | 376 | let val = Operand::Copy(place.clone()); |
e9174d1e | 377 | |
9cc50fc6 SL |
378 | let fail = self.cfg.start_new_block(); |
379 | let block = self.compare(block, fail, test.span, BinOp::Le, lo, val.clone()); | |
32a655c1 SL |
380 | let block = match *end { |
381 | RangeEnd::Included => self.compare(block, fail, test.span, BinOp::Le, val, hi), | |
382 | RangeEnd::Excluded => self.compare(block, fail, test.span, BinOp::Lt, val, hi), | |
383 | }; | |
e9174d1e | 384 | |
9cc50fc6 | 385 | vec![block, fail] |
e9174d1e SL |
386 | } |
387 | ||
388 | TestKind::Len { len, op } => { | |
389 | let (usize_ty, bool_ty) = (self.hir.usize_ty(), self.hir.bool_ty()); | |
cc61c64b XL |
390 | let (actual, result) = (self.temp(usize_ty, test.span), |
391 | self.temp(bool_ty, test.span)); | |
e9174d1e | 392 | |
ff7c6d11 | 393 | // actual = len(place) |
3157f602 | 394 | self.cfg.push_assign(block, source_info, |
ff7c6d11 | 395 | &actual, Rvalue::Len(place.clone())); |
e9174d1e SL |
396 | |
397 | // expected = <N> | |
3157f602 | 398 | let expected = self.push_usize(block, source_info, len); |
e9174d1e SL |
399 | |
400 | // result = actual == expected OR result = actual < expected | |
3157f602 | 401 | self.cfg.push_assign(block, source_info, &result, |
b039eaaf | 402 | Rvalue::BinaryOp(op, |
ff7c6d11 XL |
403 | Operand::Move(actual), |
404 | Operand::Move(expected))); | |
e9174d1e SL |
405 | |
406 | // branch based on result | |
8bb4bdeb XL |
407 | let (false_bb, true_bb) = (self.cfg.start_new_block(), |
408 | self.cfg.start_new_block()); | |
409 | self.cfg.terminate(block, source_info, | |
ff7c6d11 | 410 | TerminatorKind::if_(self.hir.tcx(), Operand::Move(result), |
8bb4bdeb XL |
411 | true_bb, false_bb)); |
412 | vec![true_bb, false_bb] | |
e9174d1e SL |
413 | } |
414 | } | |
415 | } | |
416 | ||
9cc50fc6 SL |
417 | fn compare(&mut self, |
418 | block: BasicBlock, | |
419 | fail_block: BasicBlock, | |
420 | span: Span, | |
421 | op: BinOp, | |
422 | left: Operand<'tcx>, | |
423 | right: Operand<'tcx>) -> BasicBlock { | |
e9174d1e | 424 | let bool_ty = self.hir.bool_ty(); |
cc61c64b | 425 | let result = self.temp(bool_ty, span); |
9cc50fc6 SL |
426 | |
427 | // result = op(left, right) | |
3157f602 XL |
428 | let source_info = self.source_info(span); |
429 | self.cfg.push_assign(block, source_info, &result, | |
54a0048b | 430 | Rvalue::BinaryOp(op, left, right)); |
9cc50fc6 SL |
431 | |
432 | // branch based on result | |
433 | let target_block = self.cfg.start_new_block(); | |
8bb4bdeb | 434 | self.cfg.terminate(block, source_info, |
ff7c6d11 | 435 | TerminatorKind::if_(self.hir.tcx(), Operand::Move(result), |
8bb4bdeb | 436 | target_block, fail_block)); |
9cc50fc6 | 437 | target_block |
e9174d1e SL |
438 | } |
439 | ||
ff7c6d11 | 440 | /// Given that we are performing `test` against `test_place`, |
92a42be0 SL |
441 | /// this job sorts out what the status of `candidate` will be |
442 | /// after the test. The `resulting_candidates` vector stores, for | |
443 | /// each possible outcome of `test`, a vector of the candidates | |
444 | /// that will result. This fn should add a (possibly modified) | |
445 | /// clone of candidate into `resulting_candidates` wherever | |
446 | /// appropriate. | |
e9174d1e | 447 | /// |
92a42be0 SL |
448 | /// So, for example, if this candidate is `x @ Some(P0)` and the |
449 | /// test is a variant test, then we would add `(x as Option).0 @ | |
450 | /// P0` to the `resulting_candidates` entry corresponding to the | |
451 | /// variant `Some`. | |
452 | /// | |
453 | /// However, in some cases, the test may just not be relevant to | |
454 | /// candidate. For example, suppose we are testing whether `foo.x == 22`, | |
455 | /// but in one match arm we have `Foo { x: _, ... }`... in that case, | |
456 | /// the test for what value `x` has has no particular relevance | |
457 | /// to this candidate. In such cases, this function just returns false | |
458 | /// without doing anything. This is used by the overall `match_candidates` | |
459 | /// algorithm to structure the match as a whole. See `match_candidates` for | |
460 | /// more details. | |
461 | /// | |
462 | /// FIXME(#29623). In some cases, we have some tricky choices to | |
463 | /// make. for example, if we are testing that `x == 22`, but the | |
464 | /// candidate is `x @ 13..55`, what should we do? In the event | |
465 | /// that the test is true, we know that the candidate applies, but | |
466 | /// in the event of false, we don't know that it *doesn't* | |
467 | /// apply. For now, we return false, indicate that the test does | |
468 | /// not apply to this candidate, but it might be we can get | |
469 | /// tighter match code if we do something a bit different. | |
470 | pub fn sort_candidate<'pat>(&mut self, | |
ff7c6d11 | 471 | test_place: &Place<'tcx>, |
92a42be0 SL |
472 | test: &Test<'tcx>, |
473 | candidate: &Candidate<'pat, 'tcx>, | |
474 | resulting_candidates: &mut [Vec<Candidate<'pat, 'tcx>>]) | |
475 | -> bool { | |
ff7c6d11 | 476 | // Find the match_pair for this place (if any). At present, |
92a42be0 SL |
477 | // afaik, there can be at most one. (In the future, if we |
478 | // adopted a more general `@` operator, there might be more | |
479 | // than one, but it'd be very unusual to have two sides that | |
480 | // both require tests; you'd expect one side to be simplified | |
481 | // away.) | |
482 | let tested_match_pair = candidate.match_pairs.iter() | |
483 | .enumerate() | |
ff7c6d11 | 484 | .filter(|&(_, mp)| mp.place == *test_place) |
92a42be0 SL |
485 | .next(); |
486 | let (match_pair_index, match_pair) = match tested_match_pair { | |
487 | Some(pair) => pair, | |
488 | None => { | |
ff7c6d11 | 489 | // We are not testing this place. Therefore, this |
92a42be0 SL |
490 | // candidate applies to ALL outcomes. |
491 | return false; | |
e9174d1e | 492 | } |
92a42be0 SL |
493 | }; |
494 | ||
3157f602 | 495 | match (&test.kind, &*match_pair.pattern.kind) { |
92a42be0 SL |
496 | // If we are performing a variant switch, then this |
497 | // informs variant patterns, but nothing else. | |
3157f602 | 498 | (&TestKind::Switch { adt_def: tested_adt_def, .. }, |
32a655c1 | 499 | &PatternKind::Variant { adt_def, variant_index, ref subpatterns, .. }) => { |
3157f602 XL |
500 | assert_eq!(adt_def, tested_adt_def); |
501 | let new_candidate = | |
502 | self.candidate_after_variant_switch(match_pair_index, | |
503 | adt_def, | |
504 | variant_index, | |
505 | subpatterns, | |
506 | candidate); | |
507 | resulting_candidates[variant_index].push(new_candidate); | |
508 | true | |
e9174d1e | 509 | } |
3157f602 | 510 | (&TestKind::Switch { .. }, _) => false, |
e9174d1e | 511 | |
92a42be0 SL |
512 | // If we are performing a switch over integers, then this informs integer |
513 | // equality, but nothing else. | |
514 | // | |
3157f602 | 515 | // FIXME(#29623) we could use PatternKind::Range to rule |
92a42be0 | 516 | // things out here, in some cases. |
3157f602 XL |
517 | (&TestKind::SwitchInt { switch_ty: _, options: _, ref indices }, |
518 | &PatternKind::Constant { ref value }) | |
519 | if is_switch_ty(match_pair.pattern.ty) => { | |
520 | let index = indices[value]; | |
521 | let new_candidate = self.candidate_without_match_pair(match_pair_index, | |
522 | candidate); | |
523 | resulting_candidates[index].push(new_candidate); | |
524 | true | |
525 | } | |
526 | (&TestKind::SwitchInt { .. }, _) => false, | |
527 | ||
528 | ||
529 | (&TestKind::Len { len: test_len, op: BinOp::Eq }, | |
530 | &PatternKind::Slice { ref prefix, ref slice, ref suffix }) => { | |
531 | let pat_len = (prefix.len() + suffix.len()) as u64; | |
532 | match (test_len.cmp(&pat_len), slice) { | |
533 | (Ordering::Equal, &None) => { | |
534 | // on true, min_len = len = $actual_length, | |
535 | // on false, len != $actual_length | |
536 | resulting_candidates[0].push( | |
537 | self.candidate_after_slice_test(match_pair_index, | |
538 | candidate, | |
539 | prefix, | |
540 | slice.as_ref(), | |
541 | suffix) | |
542 | ); | |
92a42be0 SL |
543 | true |
544 | } | |
3157f602 XL |
545 | (Ordering::Less, _) => { |
546 | // test_len < pat_len. If $actual_len = test_len, | |
547 | // then $actual_len < pat_len and we don't have | |
548 | // enough elements. | |
549 | resulting_candidates[1].push(candidate.clone()); | |
550 | true | |
551 | } | |
552 | (Ordering::Equal, &Some(_)) | (Ordering::Greater, &Some(_)) => { | |
553 | // This can match both if $actual_len = test_len >= pat_len, | |
554 | // and if $actual_len > test_len. We can't advance. | |
92a42be0 SL |
555 | false |
556 | } | |
3157f602 XL |
557 | (Ordering::Greater, &None) => { |
558 | // test_len != pat_len, so if $actual_len = test_len, then | |
559 | // $actual_len != pat_len. | |
560 | resulting_candidates[1].push(candidate.clone()); | |
561 | true | |
562 | } | |
e9174d1e | 563 | } |
e9174d1e SL |
564 | } |
565 | ||
3157f602 XL |
566 | (&TestKind::Len { len: test_len, op: BinOp::Ge }, |
567 | &PatternKind::Slice { ref prefix, ref slice, ref suffix }) => { | |
568 | // the test is `$actual_len >= test_len` | |
569 | let pat_len = (prefix.len() + suffix.len()) as u64; | |
570 | match (test_len.cmp(&pat_len), slice) { | |
571 | (Ordering::Equal, &Some(_)) => { | |
572 | // $actual_len >= test_len = pat_len, | |
573 | // so we can match. | |
574 | resulting_candidates[0].push( | |
575 | self.candidate_after_slice_test(match_pair_index, | |
576 | candidate, | |
577 | prefix, | |
578 | slice.as_ref(), | |
579 | suffix) | |
580 | ); | |
581 | true | |
582 | } | |
583 | (Ordering::Less, _) | (Ordering::Equal, &None) => { | |
584 | // test_len <= pat_len. If $actual_len < test_len, | |
585 | // then it is also < pat_len, so the test passing is | |
586 | // necessary (but insufficient). | |
587 | resulting_candidates[0].push(candidate.clone()); | |
54a0048b SL |
588 | true |
589 | } | |
3157f602 XL |
590 | (Ordering::Greater, &None) => { |
591 | // test_len > pat_len. If $actual_len >= test_len > pat_len, | |
592 | // then we know we won't have a match. | |
593 | resulting_candidates[1].push(candidate.clone()); | |
594 | true | |
595 | } | |
596 | (Ordering::Greater, &Some(_)) => { | |
597 | // test_len < pat_len, and is therefore less | |
598 | // strict. This can still go both ways. | |
599 | false | |
600 | } | |
54a0048b SL |
601 | } |
602 | } | |
603 | ||
3157f602 XL |
604 | (&TestKind::Eq { .. }, _) | |
605 | (&TestKind::Range { .. }, _) | | |
606 | (&TestKind::Len { .. }, _) => { | |
92a42be0 SL |
607 | // These are all binary tests. |
608 | // | |
609 | // FIXME(#29623) we can be more clever here | |
610 | let pattern_test = self.test(&match_pair); | |
611 | if pattern_test.kind == test.kind { | |
612 | let new_candidate = self.candidate_without_match_pair(match_pair_index, | |
613 | candidate); | |
614 | resulting_candidates[0].push(new_candidate); | |
615 | true | |
e9174d1e | 616 | } else { |
92a42be0 | 617 | false |
e9174d1e SL |
618 | } |
619 | } | |
92a42be0 SL |
620 | } |
621 | } | |
e9174d1e | 622 | |
92a42be0 SL |
623 | fn candidate_without_match_pair<'pat>(&mut self, |
624 | match_pair_index: usize, | |
625 | candidate: &Candidate<'pat, 'tcx>) | |
626 | -> Candidate<'pat, 'tcx> { | |
627 | let other_match_pairs = | |
628 | candidate.match_pairs.iter() | |
629 | .enumerate() | |
630 | .filter(|&(index, _)| index != match_pair_index) | |
631 | .map(|(_, mp)| mp.clone()) | |
632 | .collect(); | |
633 | Candidate { | |
54a0048b | 634 | span: candidate.span, |
92a42be0 SL |
635 | match_pairs: other_match_pairs, |
636 | bindings: candidate.bindings.clone(), | |
637 | guard: candidate.guard.clone(), | |
638 | arm_index: candidate.arm_index, | |
abe05a73 XL |
639 | pre_binding_block: candidate.pre_binding_block, |
640 | next_candidate_pre_binding_block: candidate.next_candidate_pre_binding_block, | |
92a42be0 SL |
641 | } |
642 | } | |
e9174d1e | 643 | |
3157f602 XL |
644 | fn candidate_after_slice_test<'pat>(&mut self, |
645 | match_pair_index: usize, | |
646 | candidate: &Candidate<'pat, 'tcx>, | |
647 | prefix: &'pat [Pattern<'tcx>], | |
648 | opt_slice: Option<&'pat Pattern<'tcx>>, | |
649 | suffix: &'pat [Pattern<'tcx>]) | |
650 | -> Candidate<'pat, 'tcx> { | |
651 | let mut new_candidate = | |
652 | self.candidate_without_match_pair(match_pair_index, candidate); | |
653 | self.prefix_slice_suffix( | |
654 | &mut new_candidate.match_pairs, | |
ff7c6d11 | 655 | &candidate.match_pairs[match_pair_index].place, |
3157f602 XL |
656 | prefix, |
657 | opt_slice, | |
658 | suffix); | |
659 | ||
660 | new_candidate | |
661 | } | |
662 | ||
92a42be0 SL |
663 | fn candidate_after_variant_switch<'pat>(&mut self, |
664 | match_pair_index: usize, | |
476ff2be | 665 | adt_def: &'tcx ty::AdtDef, |
92a42be0 SL |
666 | variant_index: usize, |
667 | subpatterns: &'pat [FieldPattern<'tcx>], | |
668 | candidate: &Candidate<'pat, 'tcx>) | |
669 | -> Candidate<'pat, 'tcx> { | |
670 | let match_pair = &candidate.match_pairs[match_pair_index]; | |
671 | ||
672 | // So, if we have a match-pattern like `x @ Enum::Variant(P1, P2)`, | |
673 | // we want to create a set of derived match-patterns like | |
674 | // `(x as Variant).0 @ P1` and `(x as Variant).1 @ P1`. | |
675 | let elem = ProjectionElem::Downcast(adt_def, variant_index); | |
ff7c6d11 | 676 | let downcast_place = match_pair.place.clone().elem(elem); // `(x as Variant)` |
92a42be0 SL |
677 | let consequent_match_pairs = |
678 | subpatterns.iter() | |
679 | .map(|subpattern| { | |
680 | // e.g., `(x as Variant).0` | |
ff7c6d11 | 681 | let place = downcast_place.clone().field(subpattern.field, |
54a0048b | 682 | subpattern.pattern.ty); |
92a42be0 | 683 | // e.g., `(x as Variant).0 @ P1` |
ff7c6d11 | 684 | MatchPair::new(place, &subpattern.pattern) |
92a42be0 SL |
685 | }); |
686 | ||
687 | // In addition, we need all the other match pairs from the old candidate. | |
688 | let other_match_pairs = | |
689 | candidate.match_pairs.iter() | |
690 | .enumerate() | |
691 | .filter(|&(index, _)| index != match_pair_index) | |
692 | .map(|(_, mp)| mp.clone()); | |
693 | ||
694 | let all_match_pairs = consequent_match_pairs.chain(other_match_pairs).collect(); | |
695 | ||
696 | Candidate { | |
54a0048b | 697 | span: candidate.span, |
92a42be0 SL |
698 | match_pairs: all_match_pairs, |
699 | bindings: candidate.bindings.clone(), | |
700 | guard: candidate.guard.clone(), | |
701 | arm_index: candidate.arm_index, | |
abe05a73 XL |
702 | pre_binding_block: candidate.pre_binding_block, |
703 | next_candidate_pre_binding_block: candidate.next_candidate_pre_binding_block, | |
e9174d1e SL |
704 | } |
705 | } | |
706 | ||
92a42be0 | 707 | fn error_simplifyable<'pat>(&mut self, match_pair: &MatchPair<'pat, 'tcx>) -> ! { |
54a0048b SL |
708 | span_bug!(match_pair.pattern.span, |
709 | "simplifyable pattern found: {:?}", | |
710 | match_pair.pattern) | |
e9174d1e SL |
711 | } |
712 | } | |
92a42be0 SL |
713 | |
714 | fn is_switch_ty<'tcx>(ty: Ty<'tcx>) -> bool { | |
715 | ty.is_integral() || ty.is_char() || ty.is_bool() | |
716 | } |