]>
Commit | Line | Data |
---|---|---|
e9174d1e SL |
1 | //! Simplifying Candidates |
2 | //! | |
ff7c6d11 | 3 | //! *Simplifying* a match pair `place @ pattern` means breaking it down |
e9174d1e SL |
4 | //! into bindings or other, simpler match pairs. For example: |
5 | //! | |
ff7c6d11 XL |
6 | //! - `place @ (P1, P2)` can be simplified to `[place.0 @ P1, place.1 @ P2]` |
7 | //! - `place @ x` can be simplified to `[]` by binding `x` to `place` | |
e9174d1e SL |
8 | //! |
9 | //! The `simplify_candidate` routine just repeatedly applies these | |
10 | //! sort of simplifications until there is nothing left to | |
11 | //! simplify. Match pairs cannot be simplified if they require some | |
12 | //! sort of test: for example, testing which variant an enum is, or | |
13 | //! testing a value against a constant. | |
14 | ||
dfeec247 | 15 | use crate::build::matches::{Ascription, Binding, Candidate, MatchPair}; |
9fa01778 | 16 | use crate::build::Builder; |
3dfed10e | 17 | use crate::thir::{self, *}; |
dfeec247 | 18 | use rustc_hir::RangeEnd; |
ba9703b0 XL |
19 | use rustc_middle::mir::Place; |
20 | use rustc_middle::ty; | |
21 | use rustc_middle::ty::layout::IntegerExt; | |
22 | use rustc_target::abi::{Integer, Size}; | |
e9174d1e SL |
23 | |
24 | use std::mem; | |
25 | ||
dc9dc135 | 26 | impl<'a, 'tcx> Builder<'a, 'tcx> { |
74b04a01 XL |
27 | /// Simplify a candidate so that all match pairs require a test. |
28 | /// | |
29967ef6 XL |
29 | /// This method will also split a candidate, in which the only |
30 | /// match-pair is an or-pattern, into multiple candidates. | |
31 | /// This is so that | |
74b04a01 XL |
32 | /// |
33 | /// match x { | |
34 | /// 0 | 1 => { ... }, | |
35 | /// 2 | 3 => { ... }, | |
36 | /// } | |
37 | /// | |
38 | /// only generates a single switch. If this happens this method returns | |
39 | /// `true`. | |
40 | pub(super) fn simplify_candidate<'pat>( | |
41 | &mut self, | |
42 | candidate: &mut Candidate<'pat, 'tcx>, | |
43 | ) -> bool { | |
e9174d1e | 44 | // repeatedly simplify match pairs until fixed point is reached |
29967ef6 XL |
45 | debug!(?candidate, "simplify_candidate"); |
46 | ||
47 | // existing_bindings and new_bindings exists to keep the semantics in order. | |
48 | // Reversing the binding order for bindings after `@` changes the binding order in places | |
49 | // it shouldn't be changed, for example `let (Some(a), Some(b)) = (x, y)` | |
50 | // | |
51 | // To avoid this, the binding occurs in the following manner: | |
52 | // * the bindings for one iteration of the following loop occurs in order (i.e. left to | |
53 | // right) | |
54 | // * the bindings from the previous iteration of the loop is prepended to the bindings from | |
55 | // the current iteration (in the implementation this is done by mem::swap and extend) | |
56 | // * after all iterations, these new bindings are then appended to the bindings that were | |
5869c6ff | 57 | // preexisting (i.e. `candidate.binding` when the function was called). |
29967ef6 XL |
58 | // |
59 | // example: | |
60 | // candidate.bindings = [1, 2, 3] | |
61 | // binding in iter 1: [4, 5] | |
62 | // binding in iter 2: [6, 7] | |
63 | // | |
64 | // final binding: [1, 2, 3, 6, 7, 4, 5] | |
65 | let mut existing_bindings = mem::take(&mut candidate.bindings); | |
66 | let mut new_bindings = Vec::new(); | |
e9174d1e | 67 | loop { |
416331ca | 68 | let match_pairs = mem::take(&mut candidate.match_pairs); |
74b04a01 XL |
69 | |
70 | if let [MatchPair { pattern: Pat { kind: box PatKind::Or { pats }, .. }, place }] = | |
71 | *match_pairs | |
72 | { | |
29967ef6 XL |
73 | existing_bindings.extend_from_slice(&new_bindings); |
74 | mem::swap(&mut candidate.bindings, &mut existing_bindings); | |
74b04a01 XL |
75 | candidate.subcandidates = self.create_or_subcandidates(candidate, place, pats); |
76 | return true; | |
77 | } | |
78 | ||
0731742a | 79 | let mut changed = false; |
e9174d1e | 80 | for match_pair in match_pairs { |
3157f602 | 81 | match self.simplify_match_pair(match_pair, candidate) { |
0731742a XL |
82 | Ok(()) => { |
83 | changed = true; | |
84 | } | |
e9174d1e SL |
85 | Err(match_pair) => { |
86 | candidate.match_pairs.push(match_pair); | |
e9174d1e SL |
87 | } |
88 | } | |
89 | } | |
29967ef6 XL |
90 | // Avoid issue #69971: the binding order should be right to left if there are more |
91 | // bindings after `@` to please the borrow checker | |
92 | // Ex | |
93 | // struct NonCopyStruct { | |
94 | // copy_field: u32, | |
95 | // } | |
96 | // | |
97 | // fn foo1(x: NonCopyStruct) { | |
98 | // let y @ NonCopyStruct { copy_field: z } = x; | |
99 | // // the above should turn into | |
100 | // let z = x.copy_field; | |
101 | // let y = x; | |
102 | // } | |
103 | candidate.bindings.extend_from_slice(&new_bindings); | |
104 | mem::swap(&mut candidate.bindings, &mut new_bindings); | |
105 | candidate.bindings.clear(); | |
106 | ||
0731742a | 107 | if !changed { |
29967ef6 XL |
108 | existing_bindings.extend_from_slice(&new_bindings); |
109 | mem::swap(&mut candidate.bindings, &mut existing_bindings); | |
74b04a01 XL |
110 | // Move or-patterns to the end, because they can result in us |
111 | // creating additional candidates, so we want to test them as | |
112 | // late as possible. | |
113 | candidate | |
114 | .match_pairs | |
115 | .sort_by_key(|pair| matches!(*pair.pattern.kind, PatKind::Or { .. })); | |
29967ef6 | 116 | debug!(simplified = ?candidate, "simplify_candidate"); |
74b04a01 | 117 | return false; // if we were not able to simplify any, done. |
e9174d1e SL |
118 | } |
119 | } | |
120 | } | |
121 | ||
74b04a01 XL |
122 | /// Given `candidate` that has a single or-pattern for its match-pairs, |
123 | /// creates a fresh candidate for each of its input subpatterns passed via | |
124 | /// `pats`. | |
125 | fn create_or_subcandidates<'pat>( | |
126 | &mut self, | |
127 | candidate: &Candidate<'pat, 'tcx>, | |
128 | place: Place<'tcx>, | |
129 | pats: &'pat [Pat<'tcx>], | |
130 | ) -> Vec<Candidate<'pat, 'tcx>> { | |
131 | pats.iter() | |
132 | .map(|pat| { | |
133 | let mut candidate = Candidate::new(place, pat, candidate.has_guard); | |
134 | self.simplify_candidate(&mut candidate); | |
135 | candidate | |
136 | }) | |
137 | .collect() | |
138 | } | |
139 | ||
9fa01778 | 140 | /// Tries to simplify `match_pair`, returning `Ok(())` if |
e9174d1e | 141 | /// successful. If successful, new match pairs and bindings will |
b039eaaf | 142 | /// have been pushed into the candidate. If no simplification is |
9fa01778 | 143 | /// possible, `Err` is returned and no changes are made to |
b039eaaf | 144 | /// candidate. |
dfeec247 XL |
145 | fn simplify_match_pair<'pat>( |
146 | &mut self, | |
147 | match_pair: MatchPair<'pat, 'tcx>, | |
148 | candidate: &mut Candidate<'pat, 'tcx>, | |
149 | ) -> Result<(), MatchPair<'pat, 'tcx>> { | |
0731742a | 150 | let tcx = self.hir.tcx(); |
92a42be0 | 151 | match *match_pair.pattern.kind { |
e74abb32 | 152 | PatKind::AscribeUserType { |
0731742a | 153 | ref subpattern, |
3dfed10e | 154 | ascription: thir::pattern::Ascription { variance, user_ty, user_ty_span }, |
0731742a XL |
155 | } => { |
156 | // Apply the type ascription to the value at `match_pair.place`, which is the | |
157 | // value being matched, taking the variance field into account. | |
b7449926 | 158 | candidate.ascriptions.push(Ascription { |
0bf4aa26 | 159 | span: user_ty_span, |
74b04a01 | 160 | user_ty, |
dfeec247 | 161 | source: match_pair.place, |
0731742a | 162 | variance, |
b7449926 XL |
163 | }); |
164 | ||
165 | candidate.match_pairs.push(MatchPair::new(match_pair.place, subpattern)); | |
166 | ||
167 | Ok(()) | |
168 | } | |
169 | ||
e74abb32 | 170 | PatKind::Wild => { |
e9174d1e | 171 | // nothing left to do |
3157f602 | 172 | Ok(()) |
e9174d1e SL |
173 | } |
174 | ||
f9f354fc | 175 | PatKind::Binding { name, mutability, mode, var, ty, ref subpattern, is_primary: _ } => { |
e9174d1e | 176 | candidate.bindings.push(Binding { |
3b2f2976 XL |
177 | name, |
178 | mutability, | |
e9174d1e | 179 | span: match_pair.pattern.span, |
dfeec247 | 180 | source: match_pair.place, |
e9174d1e SL |
181 | var_id: var, |
182 | var_ty: ty, | |
183 | binding_mode: mode, | |
184 | }); | |
185 | ||
92a42be0 | 186 | if let Some(subpattern) = subpattern.as_ref() { |
e9174d1e | 187 | // this is the `x @ P` case; have to keep matching against `P` now |
ff7c6d11 | 188 | candidate.match_pairs.push(MatchPair::new(match_pair.place, subpattern)); |
e9174d1e SL |
189 | } |
190 | ||
3157f602 | 191 | Ok(()) |
e9174d1e SL |
192 | } |
193 | ||
e74abb32 | 194 | PatKind::Constant { .. } => { |
e9174d1e SL |
195 | // FIXME normalize patterns when possible |
196 | Err(match_pair) | |
197 | } | |
198 | ||
e74abb32 | 199 | PatKind::Range(PatRange { lo, hi, end }) => { |
1b1a35ee | 200 | let (range, bias) = match *lo.ty.kind() { |
0731742a XL |
201 | ty::Char => { |
202 | (Some(('\u{0000}' as u128, '\u{10FFFF}' as u128, Size::from_bits(32))), 0) | |
203 | } | |
204 | ty::Int(ity) => { | |
5869c6ff | 205 | let size = Integer::from_int_ty(&tcx, ity).size(); |
29967ef6 | 206 | let max = size.truncate(u128::MAX); |
0731742a XL |
207 | let bias = 1u128 << (size.bits() - 1); |
208 | (Some((0, max, size)), bias) | |
209 | } | |
210 | ty::Uint(uty) => { | |
5869c6ff | 211 | let size = Integer::from_uint_ty(&tcx, uty).size(); |
29967ef6 | 212 | let max = size.truncate(u128::MAX); |
0731742a XL |
213 | (Some((0, max, size)), 0) |
214 | } | |
215 | _ => (None, 0), | |
216 | }; | |
217 | if let Some((min, max, sz)) = range { | |
218 | if let (Some(lo), Some(hi)) = (lo.val.try_to_bits(sz), hi.val.try_to_bits(sz)) { | |
219 | // We want to compare ranges numerically, but the order of the bitwise | |
220 | // representation of signed integers does not match their numeric order. | |
221 | // Thus, to correct the ordering, we need to shift the range of signed | |
222 | // integers to correct the comparison. This is achieved by XORing with a | |
223 | // bias (see pattern/_match.rs for another pertinent example of this | |
224 | // pattern). | |
225 | let (lo, hi) = (lo ^ bias, hi ^ bias); | |
226 | if lo <= min && (hi > max || hi == max && end == RangeEnd::Included) { | |
227 | // Irrefutable pattern match. | |
228 | return Ok(()); | |
229 | } | |
230 | } | |
231 | } | |
54a0048b SL |
232 | Err(match_pair) |
233 | } | |
234 | ||
e74abb32 | 235 | PatKind::Slice { ref prefix, ref slice, ref suffix } => { |
2c00a5a8 XL |
236 | if prefix.is_empty() && slice.is_some() && suffix.is_empty() { |
237 | // irrefutable | |
dfeec247 XL |
238 | self.prefix_slice_suffix( |
239 | &mut candidate.match_pairs, | |
240 | &match_pair.place, | |
241 | prefix, | |
242 | slice.as_ref(), | |
243 | suffix, | |
244 | ); | |
2c00a5a8 XL |
245 | Ok(()) |
246 | } else { | |
247 | Err(match_pair) | |
248 | } | |
249 | } | |
250 | ||
e74abb32 | 251 | PatKind::Variant { adt_def, substs, variant_index, ref subpatterns } => { |
a1dfa0c6 | 252 | let irrefutable = adt_def.variants.iter_enumerated().all(|(i, v)| { |
ff7c6d11 | 253 | i == variant_index || { |
dfeec247 XL |
254 | self.hir.tcx().features().exhaustive_patterns |
255 | && !v | |
ba9703b0 XL |
256 | .uninhabited_from( |
257 | self.hir.tcx(), | |
258 | substs, | |
259 | adt_def.adt_kind(), | |
260 | self.hir.param_env, | |
261 | ) | |
dfeec247 | 262 | .is_empty() |
32a655c1 | 263 | } |
dfeec247 XL |
264 | }) && (adt_def.did.is_local() |
265 | || !adt_def.is_variant_list_non_exhaustive()); | |
ff7c6d11 | 266 | if irrefutable { |
e74abb32 | 267 | let place = tcx.mk_place_downcast(match_pair.place, adt_def, variant_index); |
ff7c6d11 XL |
268 | candidate.match_pairs.extend(self.field_match_pairs(place, subpatterns)); |
269 | Ok(()) | |
32a655c1 SL |
270 | } else { |
271 | Err(match_pair) | |
272 | } | |
9fa01778 | 273 | } |
32a655c1 | 274 | |
e74abb32 | 275 | PatKind::Array { ref prefix, ref slice, ref suffix } => { |
dfeec247 XL |
276 | self.prefix_slice_suffix( |
277 | &mut candidate.match_pairs, | |
278 | &match_pair.place, | |
279 | prefix, | |
280 | slice.as_ref(), | |
281 | suffix, | |
282 | ); | |
3157f602 | 283 | Ok(()) |
e9174d1e SL |
284 | } |
285 | ||
e74abb32 | 286 | PatKind::Leaf { ref subpatterns } => { |
e9174d1e | 287 | // tuple struct, match subpats (if any) |
dfeec247 | 288 | candidate.match_pairs.extend(self.field_match_pairs(match_pair.place, subpatterns)); |
3157f602 | 289 | Ok(()) |
e9174d1e SL |
290 | } |
291 | ||
e74abb32 XL |
292 | PatKind::Deref { ref subpattern } => { |
293 | let place = tcx.mk_place_deref(match_pair.place); | |
ff7c6d11 | 294 | candidate.match_pairs.push(MatchPair::new(place, subpattern)); |
3157f602 | 295 | Ok(()) |
e9174d1e | 296 | } |
e1599b0c | 297 | |
dfeec247 | 298 | PatKind::Or { .. } => Err(match_pair), |
e9174d1e SL |
299 | } |
300 | } | |
301 | } |