]>
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 | ||
c620b35d | 8 | use crate::build::matches::{Candidate, MatchPair, Test, TestBranch, TestCase, TestKind}; |
dfeec247 | 9 | use crate::build::Builder; |
3dfed10e XL |
10 | use rustc_data_structures::fx::FxIndexMap; |
11 | use rustc_hir::{LangItem, RangeEnd}; | |
ba9703b0 XL |
12 | use rustc_middle::mir::*; |
13 | use rustc_middle::ty::util::IntTypeExt; | |
2b03887a | 14 | use rustc_middle::ty::GenericArg; |
fe692bf9 | 15 | use rustc_middle::ty::{self, adjustment::PointerCoercion, Ty, TyCtxt}; |
6a06907d | 16 | use rustc_span::def_id::DefId; |
c0240ec0 | 17 | use rustc_span::source_map::Spanned; |
6a06907d | 18 | use rustc_span::symbol::{sym, Symbol}; |
c0240ec0 | 19 | use rustc_span::{Span, DUMMY_SP}; |
dc9dc135 | 20 | |
3157f602 | 21 | use std::cmp::Ordering; |
e9174d1e | 22 | |
dc9dc135 | 23 | impl<'a, 'tcx> Builder<'a, 'tcx> { |
e9174d1e SL |
24 | /// Identifies what test is needed to decide if `match_pair` is applicable. |
25 | /// | |
5869c6ff | 26 | /// It is a bug to call this with a not-fully-simplified pattern. |
74b04a01 | 27 | pub(super) fn test<'pat>(&mut self, match_pair: &MatchPair<'pat, 'tcx>) -> Test<'tcx> { |
c620b35d FG |
28 | let kind = match match_pair.test_case { |
29 | TestCase::Variant { adt_def, variant_index: _ } => TestKind::Switch { adt_def }, | |
92a42be0 | 30 | |
c620b35d FG |
31 | TestCase::Constant { .. } if match_pair.pattern.ty.is_bool() => TestKind::If, |
32 | TestCase::Constant { .. } if is_switch_ty(match_pair.pattern.ty) => TestKind::SwitchInt, | |
33 | TestCase::Constant { value } => TestKind::Eq { value, ty: match_pair.pattern.ty }, | |
e9174d1e | 34 | |
c620b35d | 35 | TestCase::Range(range) => { |
ed00b5ec | 36 | assert_eq!(range.ty, match_pair.pattern.ty); |
c620b35d | 37 | TestKind::Range(Box::new(range.clone())) |
e9174d1e SL |
38 | } |
39 | ||
c620b35d FG |
40 | TestCase::Slice { len, variable_length } => { |
41 | let op = if variable_length { BinOp::Ge } else { BinOp::Eq }; | |
42 | TestKind::Len { len: len as u64, op } | |
e9174d1e SL |
43 | } |
44 | ||
e8be2606 FG |
45 | TestCase::Deref { temp, mutability } => TestKind::Deref { temp, mutability }, |
46 | ||
c620b35d | 47 | TestCase::Or { .. } => bug!("or-patterns should have already been handled"), |
e9174d1e | 48 | |
c620b35d FG |
49 | TestCase::Irrefutable { .. } => span_bug!( |
50 | match_pair.pattern.span, | |
51 | "simplifiable pattern found: {:?}", | |
52 | match_pair.pattern | |
53 | ), | |
92a42be0 SL |
54 | }; |
55 | ||
c620b35d | 56 | Test { span: match_pair.pattern.span, kind } |
3157f602 XL |
57 | } |
58 | ||
e8be2606 | 59 | #[instrument(skip(self, target_blocks, place), level = "debug")] |
74b04a01 | 60 | pub(super) fn perform_test( |
dc9dc135 | 61 | &mut self, |
94222f64 XL |
62 | match_start_span: Span, |
63 | scrutinee_span: Span, | |
dc9dc135 | 64 | block: BasicBlock, |
c620b35d | 65 | otherwise_block: BasicBlock, |
e8be2606 | 66 | place: Place<'tcx>, |
dc9dc135 | 67 | test: &Test<'tcx>, |
c620b35d | 68 | target_blocks: FxIndexMap<TestBranch<'tcx>, BasicBlock>, |
dc9dc135 | 69 | ) { |
2b03887a | 70 | let place_ty = place.ty(&self.local_decls, self.tcx); |
c620b35d FG |
71 | debug!(?place, ?place_ty); |
72 | let target_block = |branch| target_blocks.get(&branch).copied().unwrap_or(otherwise_block); | |
dc9dc135 | 73 | |
3157f602 | 74 | let source_info = self.source_info(test.span); |
92a42be0 | 75 | match test.kind { |
c620b35d FG |
76 | TestKind::Switch { adt_def } => { |
77 | let otherwise_block = target_block(TestBranch::Failure); | |
29967ef6 | 78 | let switch_targets = SwitchTargets::new( |
c620b35d FG |
79 | adt_def.discriminants(self.tcx).filter_map(|(idx, discr)| { |
80 | if let Some(&block) = target_blocks.get(&TestBranch::Variant(idx)) { | |
81 | Some((discr.val, block)) | |
29967ef6 | 82 | } else { |
29967ef6 XL |
83 | None |
84 | } | |
85 | }), | |
86 | otherwise_block, | |
dfeec247 | 87 | ); |
c620b35d FG |
88 | debug!("num_enum_variants: {}", adt_def.variants().len()); |
89 | let discr_ty = adt_def.repr().discr_type().to_ty(self.tcx); | |
cc61c64b | 90 | let discr = self.temp(discr_ty, test.span); |
94222f64 XL |
91 | self.cfg.push_assign( |
92 | block, | |
93 | self.source_info(scrutinee_span), | |
94 | discr, | |
95 | Rvalue::Discriminant(place), | |
96 | ); | |
dfeec247 XL |
97 | self.cfg.terminate( |
98 | block, | |
94222f64 | 99 | self.source_info(match_start_span), |
dfeec247 XL |
100 | TerminatorKind::SwitchInt { |
101 | discr: Operand::Move(discr), | |
29967ef6 | 102 | targets: switch_targets, |
dfeec247 XL |
103 | }, |
104 | ); | |
e9174d1e SL |
105 | } |
106 | ||
c620b35d FG |
107 | TestKind::SwitchInt => { |
108 | // The switch may be inexhaustive so we have a catch-all block | |
109 | let otherwise_block = target_block(TestBranch::Failure); | |
110 | let switch_targets = SwitchTargets::new( | |
111 | target_blocks.iter().filter_map(|(&branch, &block)| { | |
112 | if let TestBranch::Constant(_, bits) = branch { | |
113 | Some((bits, block)) | |
114 | } else { | |
115 | None | |
116 | } | |
117 | }), | |
118 | otherwise_block, | |
119 | ); | |
120 | let terminator = TerminatorKind::SwitchInt { | |
121 | discr: Operand::Copy(place), | |
122 | targets: switch_targets, | |
3157f602 | 123 | }; |
94222f64 | 124 | self.cfg.terminate(block, self.source_info(match_start_span), terminator); |
92a42be0 SL |
125 | } |
126 | ||
c620b35d FG |
127 | TestKind::If => { |
128 | let success_block = target_block(TestBranch::Success); | |
129 | let fail_block = target_block(TestBranch::Failure); | |
130 | let terminator = | |
131 | TerminatorKind::if_(Operand::Copy(place), success_block, fail_block); | |
132 | self.cfg.terminate(block, self.source_info(match_start_span), terminator); | |
133 | } | |
134 | ||
dc9dc135 | 135 | TestKind::Eq { value, ty } => { |
487cf647 | 136 | let tcx = self.tcx; |
c620b35d FG |
137 | let success_block = target_block(TestBranch::Success); |
138 | let fail_block = target_block(TestBranch::Failure); | |
ed00b5ec FG |
139 | if let ty::Adt(def, _) = ty.kind() |
140 | && Some(def.did()) == tcx.lang_items().string() | |
141 | { | |
487cf647 | 142 | if !tcx.features().string_deref_patterns { |
ed00b5ec FG |
143 | bug!( |
144 | "matching on `String` went through without enabling string_deref_patterns" | |
145 | ); | |
487cf647 FG |
146 | } |
147 | let re_erased = tcx.lifetimes.re_erased; | |
ed00b5ec | 148 | let ref_str_ty = Ty::new_imm_ref(tcx, re_erased, tcx.types.str_); |
487cf647 | 149 | let ref_str = self.temp(ref_str_ty, test.span); |
487cf647 | 150 | let eq_block = self.cfg.start_new_block(); |
e8be2606 FG |
151 | // `let ref_str: &str = <String as Deref>::deref(&place);` |
152 | self.call_deref( | |
487cf647 | 153 | block, |
e8be2606 FG |
154 | eq_block, |
155 | place, | |
156 | Mutability::Not, | |
157 | ty, | |
158 | ref_str, | |
159 | test.span, | |
ed00b5ec FG |
160 | ); |
161 | self.non_scalar_compare( | |
162 | eq_block, | |
4b012472 FG |
163 | success_block, |
164 | fail_block, | |
ed00b5ec FG |
165 | source_info, |
166 | value, | |
167 | ref_str, | |
168 | ref_str_ty, | |
487cf647 | 169 | ); |
4b012472 | 170 | } else if !ty.is_scalar() { |
dc9dc135 XL |
171 | // Use `PartialEq::eq` instead of `BinOp::Eq` |
172 | // (the binop can only handle primitives) | |
173 | self.non_scalar_compare( | |
174 | block, | |
4b012472 FG |
175 | success_block, |
176 | fail_block, | |
dc9dc135 XL |
177 | source_info, |
178 | value, | |
179 | place, | |
0531ce1d | 180 | ty, |
dc9dc135 | 181 | ); |
4b012472 | 182 | } else { |
5099ac24 | 183 | assert_eq!(value.ty(), ty); |
923072b8 | 184 | let expect = self.literal_operand(test.span, value); |
29967ef6 | 185 | let val = Operand::Copy(place); |
4b012472 FG |
186 | self.compare( |
187 | block, | |
188 | success_block, | |
189 | fail_block, | |
190 | source_info, | |
191 | BinOp::Eq, | |
192 | expect, | |
193 | val, | |
194 | ); | |
54a0048b | 195 | } |
e9174d1e SL |
196 | } |
197 | ||
ed00b5ec | 198 | TestKind::Range(ref range) => { |
c620b35d FG |
199 | let success = target_block(TestBranch::Success); |
200 | let fail = target_block(TestBranch::Failure); | |
9cc50fc6 | 201 | // Test `val` by computing `lo <= val && val <= hi`, using primitive comparisons. |
74b04a01 | 202 | let val = Operand::Copy(place); |
e9174d1e | 203 | |
c620b35d FG |
204 | let intermediate_block = if !range.lo.is_finite() { |
205 | block | |
206 | } else if !range.hi.is_finite() { | |
207 | success | |
208 | } else { | |
209 | self.cfg.start_new_block() | |
5099ac24 | 210 | }; |
c620b35d FG |
211 | |
212 | if let Some(lo) = range.lo.as_finite() { | |
213 | let lo = self.literal_operand(test.span, lo); | |
214 | self.compare( | |
215 | block, | |
216 | intermediate_block, | |
217 | fail, | |
218 | source_info, | |
219 | BinOp::Le, | |
220 | lo, | |
221 | val.clone(), | |
222 | ); | |
5099ac24 | 223 | }; |
c620b35d FG |
224 | |
225 | if let Some(hi) = range.hi.as_finite() { | |
226 | let hi = self.literal_operand(test.span, hi); | |
227 | let op = match range.end { | |
228 | RangeEnd::Included => BinOp::Le, | |
229 | RangeEnd::Excluded => BinOp::Lt, | |
230 | }; | |
231 | self.compare(intermediate_block, success, fail, source_info, op, val, hi); | |
232 | } | |
e9174d1e SL |
233 | } |
234 | ||
235 | TestKind::Len { len, op } => { | |
6a06907d | 236 | let usize_ty = self.tcx.types.usize; |
dc9dc135 | 237 | let actual = self.temp(usize_ty, test.span); |
e9174d1e | 238 | |
ff7c6d11 | 239 | // actual = len(place) |
ba9703b0 | 240 | self.cfg.push_assign(block, source_info, actual, Rvalue::Len(place)); |
e9174d1e SL |
241 | |
242 | // expected = <N> | |
3157f602 | 243 | let expected = self.push_usize(block, source_info, len); |
e9174d1e | 244 | |
c620b35d FG |
245 | let success_block = target_block(TestBranch::Success); |
246 | let fail_block = target_block(TestBranch::Failure); | |
5099ac24 FG |
247 | // result = actual == expected OR result = actual < expected |
248 | // branch based on result | |
249 | self.compare( | |
250 | block, | |
c620b35d FG |
251 | success_block, |
252 | fail_block, | |
5099ac24 FG |
253 | source_info, |
254 | op, | |
255 | Operand::Move(actual), | |
256 | Operand::Move(expected), | |
257 | ); | |
e9174d1e | 258 | } |
e8be2606 FG |
259 | |
260 | TestKind::Deref { temp, mutability } => { | |
261 | let ty = place_ty.ty; | |
262 | let target = target_block(TestBranch::Success); | |
263 | self.call_deref(block, target, place, mutability, ty, temp, test.span); | |
264 | } | |
e9174d1e SL |
265 | } |
266 | } | |
267 | ||
e8be2606 FG |
268 | /// Perform `let temp = <ty as Deref>::deref(&place)`. |
269 | /// or `let temp = <ty as DerefMut>::deref_mut(&mut place)`. | |
270 | pub(super) fn call_deref( | |
271 | &mut self, | |
272 | block: BasicBlock, | |
273 | target_block: BasicBlock, | |
274 | place: Place<'tcx>, | |
275 | mutability: Mutability, | |
276 | ty: Ty<'tcx>, | |
277 | temp: Place<'tcx>, | |
278 | span: Span, | |
279 | ) { | |
280 | let (trait_item, method) = match mutability { | |
281 | Mutability::Not => (LangItem::Deref, sym::deref), | |
282 | Mutability::Mut => (LangItem::DerefMut, sym::deref_mut), | |
283 | }; | |
284 | let borrow_kind = super::util::ref_pat_borrow_kind(mutability); | |
285 | let source_info = self.source_info(span); | |
286 | let re_erased = self.tcx.lifetimes.re_erased; | |
287 | let trait_item = self.tcx.require_lang_item(trait_item, None); | |
288 | let method = trait_method(self.tcx, trait_item, method, [ty]); | |
289 | let ref_src = self.temp(Ty::new_ref(self.tcx, re_erased, ty, mutability), span); | |
290 | // `let ref_src = &src_place;` | |
291 | // or `let ref_src = &mut src_place;` | |
292 | self.cfg.push_assign( | |
293 | block, | |
294 | source_info, | |
295 | ref_src, | |
296 | Rvalue::Ref(re_erased, borrow_kind, place), | |
297 | ); | |
298 | // `let temp = <Ty as Deref>::deref(ref_src);` | |
299 | // or `let temp = <Ty as DerefMut>::deref_mut(ref_src);` | |
300 | self.cfg.terminate( | |
301 | block, | |
302 | source_info, | |
303 | TerminatorKind::Call { | |
304 | func: Operand::Constant(Box::new(ConstOperand { | |
305 | span, | |
306 | user_ty: None, | |
307 | const_: method, | |
308 | })), | |
309 | args: vec![Spanned { node: Operand::Move(ref_src), span }], | |
310 | destination: temp, | |
311 | target: Some(target_block), | |
312 | unwind: UnwindAction::Continue, | |
313 | call_source: CallSource::Misc, | |
314 | fn_span: source_info.span, | |
315 | }, | |
316 | ); | |
317 | } | |
318 | ||
dc9dc135 XL |
319 | /// Compare using the provided built-in comparison operator |
320 | fn compare( | |
321 | &mut self, | |
322 | block: BasicBlock, | |
323 | success_block: BasicBlock, | |
324 | fail_block: BasicBlock, | |
325 | source_info: SourceInfo, | |
326 | op: BinOp, | |
327 | left: Operand<'tcx>, | |
328 | right: Operand<'tcx>, | |
329 | ) { | |
6a06907d | 330 | let bool_ty = self.tcx.types.bool; |
dc9dc135 | 331 | let result = self.temp(bool_ty, source_info.span); |
9cc50fc6 SL |
332 | |
333 | // result = op(left, right) | |
94222f64 XL |
334 | self.cfg.push_assign( |
335 | block, | |
336 | source_info, | |
337 | result, | |
338 | Rvalue::BinaryOp(op, Box::new((left, right))), | |
339 | ); | |
9cc50fc6 SL |
340 | |
341 | // branch based on result | |
dc9dc135 XL |
342 | self.cfg.terminate( |
343 | block, | |
344 | source_info, | |
9c376795 | 345 | TerminatorKind::if_(Operand::Move(result), success_block, fail_block), |
dc9dc135 XL |
346 | ); |
347 | } | |
348 | ||
49aad941 FG |
349 | /// Compare two values using `<T as std::compare::PartialEq>::eq`. |
350 | /// If the values are already references, just call it directly, otherwise | |
351 | /// take a reference to the values first and then call it. | |
dc9dc135 XL |
352 | fn non_scalar_compare( |
353 | &mut self, | |
354 | block: BasicBlock, | |
4b012472 FG |
355 | success_block: BasicBlock, |
356 | fail_block: BasicBlock, | |
dc9dc135 | 357 | source_info: SourceInfo, |
781aab86 | 358 | value: Const<'tcx>, |
49aad941 | 359 | mut val: Place<'tcx>, |
dc9dc135 XL |
360 | mut ty: Ty<'tcx>, |
361 | ) { | |
923072b8 | 362 | let mut expect = self.literal_operand(source_info.span, value); |
dc9dc135 XL |
363 | |
364 | // If we're using `b"..."` as a pattern, we need to insert an | |
365 | // unsizing coercion, as the byte string has the type `&[u8; N]`. | |
366 | // | |
367 | // We want to do this even when the scrutinee is a reference to an | |
368 | // array, so we can call `<[u8]>::eq` rather than having to find an | |
369 | // `<[u8; N]>::eq`. | |
1b1a35ee XL |
370 | let unsize = |ty: Ty<'tcx>| match ty.kind() { |
371 | ty::Ref(region, rty, _) => match rty.kind() { | |
dc9dc135 XL |
372 | ty::Array(inner_ty, n) => Some((region, inner_ty, n)), |
373 | _ => None, | |
374 | }, | |
375 | _ => None, | |
376 | }; | |
377 | let opt_ref_ty = unsize(ty); | |
5099ac24 | 378 | let opt_ref_test_ty = unsize(value.ty()); |
dc9dc135 XL |
379 | match (opt_ref_ty, opt_ref_test_ty) { |
380 | // nothing to do, neither is an array | |
dfeec247 XL |
381 | (None, None) => {} |
382 | (Some((region, elem_ty, _)), _) | (None, Some((region, elem_ty, _))) => { | |
6a06907d | 383 | let tcx = self.tcx; |
dc9dc135 | 384 | // make both a slice |
fe692bf9 | 385 | ty = Ty::new_imm_ref(tcx, *region, Ty::new_slice(tcx, *elem_ty)); |
dc9dc135 XL |
386 | if opt_ref_ty.is_some() { |
387 | let temp = self.temp(ty, source_info.span); | |
388 | self.cfg.push_assign( | |
dfeec247 XL |
389 | block, |
390 | source_info, | |
ba9703b0 | 391 | temp, |
49aad941 | 392 | Rvalue::Cast( |
fe692bf9 | 393 | CastKind::PointerCoercion(PointerCoercion::Unsize), |
49aad941 FG |
394 | Operand::Copy(val), |
395 | ty, | |
396 | ), | |
dc9dc135 | 397 | ); |
49aad941 | 398 | val = temp; |
dc9dc135 XL |
399 | } |
400 | if opt_ref_test_ty.is_some() { | |
401 | let slice = self.temp(ty, source_info.span); | |
402 | self.cfg.push_assign( | |
dfeec247 XL |
403 | block, |
404 | source_info, | |
ba9703b0 | 405 | slice, |
fe692bf9 FG |
406 | Rvalue::Cast( |
407 | CastKind::PointerCoercion(PointerCoercion::Unsize), | |
408 | expect, | |
409 | ty, | |
410 | ), | |
dc9dc135 XL |
411 | ); |
412 | expect = Operand::Move(slice); | |
413 | } | |
dfeec247 | 414 | } |
dc9dc135 XL |
415 | } |
416 | ||
49aad941 FG |
417 | match *ty.kind() { |
418 | ty::Ref(_, deref_ty, _) => ty = deref_ty, | |
419 | _ => { | |
420 | // non_scalar_compare called on non-reference type | |
421 | let temp = self.temp(ty, source_info.span); | |
422 | self.cfg.push_assign(block, source_info, temp, Rvalue::Use(expect)); | |
fe692bf9 | 423 | let ref_ty = Ty::new_imm_ref(self.tcx, self.tcx.lifetimes.re_erased, ty); |
49aad941 FG |
424 | let ref_temp = self.temp(ref_ty, source_info.span); |
425 | ||
426 | self.cfg.push_assign( | |
427 | block, | |
428 | source_info, | |
429 | ref_temp, | |
430 | Rvalue::Ref(self.tcx.lifetimes.re_erased, BorrowKind::Shared, temp), | |
431 | ); | |
432 | expect = Operand::Move(ref_temp); | |
433 | ||
434 | let ref_temp = self.temp(ref_ty, source_info.span); | |
435 | self.cfg.push_assign( | |
436 | block, | |
437 | source_info, | |
438 | ref_temp, | |
439 | Rvalue::Ref(self.tcx.lifetimes.re_erased, BorrowKind::Shared, val), | |
440 | ); | |
441 | val = ref_temp; | |
442 | } | |
443 | } | |
dc9dc135 | 444 | |
487cf647 | 445 | let eq_def_id = self.tcx.require_lang_item(LangItem::PartialEq, Some(source_info.span)); |
4b012472 FG |
446 | let method = trait_method( |
447 | self.tcx, | |
448 | eq_def_id, | |
449 | sym::eq, | |
450 | self.tcx.with_opt_host_effect_param(self.def_id, eq_def_id, [ty, ty]), | |
451 | ); | |
dc9dc135 | 452 | |
6a06907d | 453 | let bool_ty = self.tcx.types.bool; |
dc9dc135 XL |
454 | let eq_result = self.temp(bool_ty, source_info.span); |
455 | let eq_block = self.cfg.start_new_block(); | |
dfeec247 XL |
456 | self.cfg.terminate( |
457 | block, | |
458 | source_info, | |
459 | TerminatorKind::Call { | |
781aab86 | 460 | func: Operand::Constant(Box::new(ConstOperand { |
dfeec247 XL |
461 | span: source_info.span, |
462 | ||
463 | // FIXME(#54571): This constant comes from user input (a | |
9c376795 | 464 | // constant in a pattern). Are there forms where users can add |
dfeec247 XL |
465 | // type annotations here? For example, an associated constant? |
466 | // Need to experiment. | |
467 | user_ty: None, | |
468 | ||
781aab86 | 469 | const_: method, |
94222f64 | 470 | })), |
c0240ec0 FG |
471 | args: vec![ |
472 | Spanned { node: Operand::Copy(val), span: DUMMY_SP }, | |
473 | Spanned { node: expect, span: DUMMY_SP }, | |
474 | ], | |
923072b8 FG |
475 | destination: eq_result, |
476 | target: Some(eq_block), | |
353b0b11 | 477 | unwind: UnwindAction::Continue, |
fe692bf9 | 478 | call_source: CallSource::MatchCmp, |
3dfed10e | 479 | fn_span: source_info.span, |
dfeec247 XL |
480 | }, |
481 | ); | |
29967ef6 | 482 | self.diverge_from(block); |
dc9dc135 | 483 | |
5099ac24 FG |
484 | // check the result |
485 | self.cfg.terminate( | |
486 | eq_block, | |
487 | source_info, | |
9c376795 | 488 | TerminatorKind::if_(Operand::Move(eq_result), success_block, fail_block), |
5099ac24 | 489 | ); |
e9174d1e SL |
490 | } |
491 | ||
9fa01778 XL |
492 | /// Given that we are performing `test` against `test_place`, this job |
493 | /// sorts out what the status of `candidate` will be after the test. See | |
c620b35d FG |
494 | /// `test_candidates` for the usage of this function. The candidate may |
495 | /// be modified to update its `match_pairs`. | |
e9174d1e | 496 | /// |
9fa01778 XL |
497 | /// So, for example, if this candidate is `x @ Some(P0)` and the `Test` is |
498 | /// a variant test, then we would modify the candidate to be `(x as | |
499 | /// Option).0 @ P0` and return the index corresponding to the variant | |
500 | /// `Some`. | |
92a42be0 | 501 | /// |
9fa01778 XL |
502 | /// However, in some cases, the test may just not be relevant to candidate. |
503 | /// For example, suppose we are testing whether `foo.x == 22`, but in one | |
504 | /// match arm we have `Foo { x: _, ... }`... in that case, the test for | |
49aad941 | 505 | /// the value of `x` has no particular relevance to this candidate. In |
9fa01778 XL |
506 | /// such cases, this function just returns None without doing anything. |
507 | /// This is used by the overall `match_candidates` algorithm to structure | |
508 | /// the match as a whole. See `match_candidates` for more details. | |
92a42be0 | 509 | /// |
9c376795 | 510 | /// FIXME(#29623). In some cases, we have some tricky choices to make. for |
9fa01778 XL |
511 | /// example, if we are testing that `x == 22`, but the candidate is `x @ |
512 | /// 13..55`, what should we do? In the event that the test is true, we know | |
513 | /// that the candidate applies, but in the event of false, we don't know | |
514 | /// that it *doesn't* apply. For now, we return false, indicate that the | |
515 | /// test does not apply to this candidate, but it might be we can get | |
92a42be0 | 516 | /// tighter match code if we do something a bit different. |
c620b35d | 517 | pub(super) fn sort_candidate( |
9fa01778 | 518 | &mut self, |
e8be2606 | 519 | test_place: Place<'tcx>, |
9fa01778 | 520 | test: &Test<'tcx>, |
c620b35d FG |
521 | candidate: &mut Candidate<'_, 'tcx>, |
522 | sorted_candidates: &FxIndexMap<TestBranch<'tcx>, Vec<&mut Candidate<'_, 'tcx>>>, | |
523 | ) -> Option<TestBranch<'tcx>> { | |
ff7c6d11 | 524 | // Find the match_pair for this place (if any). At present, |
92a42be0 SL |
525 | // afaik, there can be at most one. (In the future, if we |
526 | // adopted a more general `@` operator, there might be more | |
527 | // than one, but it'd be very unusual to have two sides that | |
528 | // both require tests; you'd expect one side to be simplified | |
529 | // away.) | |
e8be2606 FG |
530 | let (match_pair_index, match_pair) = candidate |
531 | .match_pairs | |
532 | .iter() | |
533 | .enumerate() | |
534 | .find(|&(_, mp)| mp.place == Some(test_place))?; | |
92a42be0 | 535 | |
c620b35d FG |
536 | let fully_matched; |
537 | let ret = match (&test.kind, &match_pair.test_case) { | |
92a42be0 SL |
538 | // If we are performing a variant switch, then this |
539 | // informs variant patterns, but nothing else. | |
dfeec247 | 540 | ( |
c620b35d FG |
541 | &TestKind::Switch { adt_def: tested_adt_def }, |
542 | &TestCase::Variant { adt_def, variant_index }, | |
dfeec247 | 543 | ) => { |
3157f602 | 544 | assert_eq!(adt_def, tested_adt_def); |
c620b35d FG |
545 | fully_matched = true; |
546 | Some(TestBranch::Variant(variant_index)) | |
e9174d1e | 547 | } |
9fa01778 | 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. |
c620b35d | 554 | (TestKind::SwitchInt, &TestCase::Constant { value }) |
9c376795 FG |
555 | if is_switch_ty(match_pair.pattern.ty) => |
556 | { | |
c620b35d FG |
557 | // Beware: there might be some ranges sorted into the failure case; we must not add |
558 | // a success case that could be matched by one of these ranges. | |
559 | let is_covering_range = |test_case: &TestCase<'_, 'tcx>| { | |
560 | test_case.as_range().is_some_and(|range| { | |
561 | matches!(range.contains(value, self.tcx, self.param_env), None | Some(true)) | |
562 | }) | |
563 | }; | |
564 | let is_conflicting_candidate = |candidate: &&mut Candidate<'_, 'tcx>| { | |
565 | candidate | |
566 | .match_pairs | |
567 | .iter() | |
e8be2606 | 568 | .any(|mp| mp.place == Some(test_place) && is_covering_range(&mp.test_case)) |
c620b35d FG |
569 | }; |
570 | if sorted_candidates | |
571 | .get(&TestBranch::Failure) | |
572 | .is_some_and(|candidates| candidates.iter().any(is_conflicting_candidate)) | |
573 | { | |
574 | fully_matched = false; | |
575 | None | |
576 | } else { | |
577 | fully_matched = true; | |
578 | let bits = value.eval_bits(self.tcx, self.param_env); | |
579 | Some(TestBranch::Constant(value, bits)) | |
580 | } | |
3157f602 | 581 | } |
c620b35d FG |
582 | (TestKind::SwitchInt, TestCase::Range(range)) => { |
583 | fully_matched = false; | |
dfeec247 | 584 | let not_contained = |
c620b35d FG |
585 | sorted_candidates.keys().filter_map(|br| br.as_constant()).copied().all( |
586 | |val| matches!(range.contains(val, self.tcx, self.param_env), Some(false)), | |
587 | ); | |
0731742a | 588 | |
9ffffee4 | 589 | not_contained.then(|| { |
0731742a XL |
590 | // No switch values are contained in the pattern range, |
591 | // so the pattern can be matched only if this test fails. | |
c620b35d | 592 | TestBranch::Failure |
9ffffee4 | 593 | }) |
0731742a XL |
594 | } |
595 | ||
c620b35d FG |
596 | (TestKind::If, TestCase::Constant { value }) => { |
597 | fully_matched = true; | |
598 | let value = value.try_eval_bool(self.tcx, self.param_env).unwrap_or_else(|| { | |
599 | span_bug!(test.span, "expected boolean value but got {value:?}") | |
600 | }); | |
601 | Some(if value { TestBranch::Success } else { TestBranch::Failure }) | |
602 | } | |
3157f602 | 603 | |
dfeec247 XL |
604 | ( |
605 | &TestKind::Len { len: test_len, op: BinOp::Eq }, | |
c620b35d | 606 | &TestCase::Slice { len, variable_length }, |
dfeec247 | 607 | ) => { |
c620b35d FG |
608 | match (test_len.cmp(&(len as u64)), variable_length) { |
609 | (Ordering::Equal, false) => { | |
3157f602 XL |
610 | // on true, min_len = len = $actual_length, |
611 | // on false, len != $actual_length | |
c620b35d FG |
612 | fully_matched = true; |
613 | Some(TestBranch::Success) | |
92a42be0 | 614 | } |
3157f602 XL |
615 | (Ordering::Less, _) => { |
616 | // test_len < pat_len. If $actual_len = test_len, | |
617 | // then $actual_len < pat_len and we don't have | |
618 | // enough elements. | |
c620b35d FG |
619 | fully_matched = false; |
620 | Some(TestBranch::Failure) | |
3157f602 | 621 | } |
c620b35d | 622 | (Ordering::Equal | Ordering::Greater, true) => { |
3157f602 XL |
623 | // This can match both if $actual_len = test_len >= pat_len, |
624 | // and if $actual_len > test_len. We can't advance. | |
c620b35d | 625 | fully_matched = false; |
9fa01778 | 626 | None |
92a42be0 | 627 | } |
c620b35d | 628 | (Ordering::Greater, false) => { |
3157f602 XL |
629 | // test_len != pat_len, so if $actual_len = test_len, then |
630 | // $actual_len != pat_len. | |
c620b35d FG |
631 | fully_matched = false; |
632 | Some(TestBranch::Failure) | |
3157f602 | 633 | } |
e9174d1e | 634 | } |
e9174d1e | 635 | } |
dfeec247 XL |
636 | ( |
637 | &TestKind::Len { len: test_len, op: BinOp::Ge }, | |
c620b35d | 638 | &TestCase::Slice { len, variable_length }, |
dfeec247 | 639 | ) => { |
3157f602 | 640 | // the test is `$actual_len >= test_len` |
c620b35d FG |
641 | match (test_len.cmp(&(len as u64)), variable_length) { |
642 | (Ordering::Equal, true) => { | |
3157f602 XL |
643 | // $actual_len >= test_len = pat_len, |
644 | // so we can match. | |
c620b35d FG |
645 | fully_matched = true; |
646 | Some(TestBranch::Success) | |
3157f602 | 647 | } |
c620b35d | 648 | (Ordering::Less, _) | (Ordering::Equal, false) => { |
3157f602 XL |
649 | // test_len <= pat_len. If $actual_len < test_len, |
650 | // then it is also < pat_len, so the test passing is | |
651 | // necessary (but insufficient). | |
c620b35d FG |
652 | fully_matched = false; |
653 | Some(TestBranch::Success) | |
54a0048b | 654 | } |
c620b35d | 655 | (Ordering::Greater, false) => { |
3157f602 XL |
656 | // test_len > pat_len. If $actual_len >= test_len > pat_len, |
657 | // then we know we won't have a match. | |
c620b35d FG |
658 | fully_matched = false; |
659 | Some(TestBranch::Failure) | |
3157f602 | 660 | } |
c620b35d | 661 | (Ordering::Greater, true) => { |
3157f602 XL |
662 | // test_len < pat_len, and is therefore less |
663 | // strict. This can still go both ways. | |
c620b35d | 664 | fully_matched = false; |
9fa01778 | 665 | None |
3157f602 | 666 | } |
54a0048b SL |
667 | } |
668 | } | |
669 | ||
c620b35d FG |
670 | (TestKind::Range(test), &TestCase::Range(pat)) => { |
671 | if test.as_ref() == pat { | |
672 | fully_matched = true; | |
673 | Some(TestBranch::Success) | |
674 | } else { | |
675 | fully_matched = false; | |
676 | // If the testing range does not overlap with pattern range, | |
677 | // the pattern can be matched only if this test fails. | |
678 | if !test.overlaps(pat, self.tcx, self.param_env)? { | |
679 | Some(TestBranch::Failure) | |
680 | } else { | |
681 | None | |
682 | } | |
0731742a | 683 | } |
0731742a | 684 | } |
c620b35d FG |
685 | (TestKind::Range(range), &TestCase::Constant { value }) => { |
686 | fully_matched = false; | |
ed00b5ec | 687 | if !range.contains(value, self.tcx, self.param_env)? { |
0731742a XL |
688 | // `value` is not contained in the testing range, |
689 | // so `value` can be matched only if this test fails. | |
c620b35d | 690 | Some(TestBranch::Failure) |
0731742a | 691 | } else { |
9fa01778 | 692 | None |
0731742a XL |
693 | } |
694 | } | |
695 | ||
e8be2606 FG |
696 | (TestKind::Eq { value: test_val, .. }, TestCase::Constant { value: case_val }) => { |
697 | if test_val == case_val { | |
698 | fully_matched = true; | |
699 | Some(TestBranch::Success) | |
700 | } else { | |
701 | fully_matched = false; | |
702 | Some(TestBranch::Failure) | |
703 | } | |
704 | } | |
705 | ||
706 | (TestKind::Deref { temp: test_temp, .. }, TestCase::Deref { temp, .. }) | |
707 | if test_temp == temp => | |
c620b35d FG |
708 | { |
709 | fully_matched = true; | |
710 | Some(TestBranch::Success) | |
e9174d1e SL |
711 | } |
712 | ||
c620b35d FG |
713 | ( |
714 | TestKind::Switch { .. } | |
715 | | TestKind::SwitchInt { .. } | |
716 | | TestKind::If | |
717 | | TestKind::Len { .. } | |
718 | | TestKind::Range { .. } | |
e8be2606 FG |
719 | | TestKind::Eq { .. } |
720 | | TestKind::Deref { .. }, | |
c620b35d FG |
721 | _, |
722 | ) => { | |
723 | fully_matched = false; | |
724 | None | |
0731742a | 725 | } |
c620b35d | 726 | }; |
92a42be0 | 727 | |
c620b35d FG |
728 | if fully_matched { |
729 | // Replace the match pair by its sub-pairs. | |
730 | let match_pair = candidate.match_pairs.remove(match_pair_index); | |
731 | candidate.match_pairs.extend(match_pair.subpairs); | |
732 | // Move or-patterns to the end. | |
733 | candidate.match_pairs.sort_by_key(|pair| matches!(pair.test_case, TestCase::Or { .. })); | |
dc9dc135 | 734 | } |
c620b35d FG |
735 | |
736 | ret | |
dc9dc135 XL |
737 | } |
738 | } | |
739 | ||
416331ca | 740 | fn is_switch_ty(ty: Ty<'_>) -> bool { |
c620b35d | 741 | ty.is_integral() || ty.is_char() |
92a42be0 | 742 | } |
6a06907d XL |
743 | |
744 | fn trait_method<'tcx>( | |
745 | tcx: TyCtxt<'tcx>, | |
746 | trait_def_id: DefId, | |
747 | method_name: Symbol, | |
add651ee | 748 | args: impl IntoIterator<Item: Into<GenericArg<'tcx>>>, |
781aab86 | 749 | ) -> Const<'tcx> { |
6a06907d XL |
750 | // The unhygienic comparison here is acceptable because this is only |
751 | // used on known traits. | |
752 | let item = tcx | |
753 | .associated_items(trait_def_id) | |
754 | .filter_by_name_unhygienic(method_name) | |
755 | .find(|item| item.kind == ty::AssocKind::Fn) | |
756 | .expect("trait method not found"); | |
757 | ||
add651ee | 758 | let method_ty = Ty::new_fn_def(tcx, item.def_id, args); |
04454e1e | 759 | |
781aab86 | 760 | Const::zero_sized(method_ty) |
6a06907d | 761 | } |