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