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