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