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