]>
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 | ||
6a06907d | 15 | use crate::build::expr::as_place::PlaceBuilder; |
dfeec247 | 16 | use crate::build::matches::{Ascription, Binding, Candidate, MatchPair}; |
9fa01778 | 17 | use crate::build::Builder; |
dfeec247 | 18 | use rustc_hir::RangeEnd; |
17df50a5 | 19 | use rustc_middle::thir::{self, *}; |
ba9703b0 XL |
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 }] = | |
6a06907d | 71 | &*match_pairs |
74b04a01 | 72 | { |
29967ef6 XL |
73 | existing_bindings.extend_from_slice(&new_bindings); |
74 | mem::swap(&mut candidate.bindings, &mut existing_bindings); | |
6a06907d XL |
75 | candidate.subcandidates = |
76 | self.create_or_subcandidates(candidate, place.clone(), pats); | |
74b04a01 XL |
77 | return true; |
78 | } | |
79 | ||
0731742a | 80 | let mut changed = false; |
e9174d1e | 81 | for match_pair in match_pairs { |
3157f602 | 82 | match self.simplify_match_pair(match_pair, candidate) { |
0731742a XL |
83 | Ok(()) => { |
84 | changed = true; | |
85 | } | |
e9174d1e SL |
86 | Err(match_pair) => { |
87 | candidate.match_pairs.push(match_pair); | |
e9174d1e SL |
88 | } |
89 | } | |
90 | } | |
29967ef6 XL |
91 | // Avoid issue #69971: the binding order should be right to left if there are more |
92 | // bindings after `@` to please the borrow checker | |
93 | // Ex | |
94 | // struct NonCopyStruct { | |
95 | // copy_field: u32, | |
96 | // } | |
97 | // | |
98 | // fn foo1(x: NonCopyStruct) { | |
99 | // let y @ NonCopyStruct { copy_field: z } = x; | |
100 | // // the above should turn into | |
101 | // let z = x.copy_field; | |
102 | // let y = x; | |
103 | // } | |
104 | candidate.bindings.extend_from_slice(&new_bindings); | |
105 | mem::swap(&mut candidate.bindings, &mut new_bindings); | |
106 | candidate.bindings.clear(); | |
107 | ||
0731742a | 108 | if !changed { |
29967ef6 XL |
109 | existing_bindings.extend_from_slice(&new_bindings); |
110 | mem::swap(&mut candidate.bindings, &mut existing_bindings); | |
74b04a01 XL |
111 | // Move or-patterns to the end, because they can result in us |
112 | // creating additional candidates, so we want to test them as | |
113 | // late as possible. | |
114 | candidate | |
115 | .match_pairs | |
116 | .sort_by_key(|pair| matches!(*pair.pattern.kind, PatKind::Or { .. })); | |
29967ef6 | 117 | debug!(simplified = ?candidate, "simplify_candidate"); |
74b04a01 | 118 | return false; // if we were not able to simplify any, done. |
e9174d1e SL |
119 | } |
120 | } | |
121 | } | |
122 | ||
74b04a01 XL |
123 | /// Given `candidate` that has a single or-pattern for its match-pairs, |
124 | /// creates a fresh candidate for each of its input subpatterns passed via | |
125 | /// `pats`. | |
126 | fn create_or_subcandidates<'pat>( | |
127 | &mut self, | |
128 | candidate: &Candidate<'pat, 'tcx>, | |
6a06907d | 129 | place: PlaceBuilder<'tcx>, |
74b04a01 XL |
130 | pats: &'pat [Pat<'tcx>], |
131 | ) -> Vec<Candidate<'pat, 'tcx>> { | |
132 | pats.iter() | |
133 | .map(|pat| { | |
6a06907d | 134 | let mut candidate = Candidate::new(place.clone(), pat, candidate.has_guard); |
74b04a01 XL |
135 | self.simplify_candidate(&mut candidate); |
136 | candidate | |
137 | }) | |
138 | .collect() | |
139 | } | |
140 | ||
9fa01778 | 141 | /// Tries to simplify `match_pair`, returning `Ok(())` if |
e9174d1e | 142 | /// successful. If successful, new match pairs and bindings will |
b039eaaf | 143 | /// have been pushed into the candidate. If no simplification is |
9fa01778 | 144 | /// possible, `Err` is returned and no changes are made to |
b039eaaf | 145 | /// candidate. |
dfeec247 XL |
146 | fn simplify_match_pair<'pat>( |
147 | &mut self, | |
148 | match_pair: MatchPair<'pat, 'tcx>, | |
149 | candidate: &mut Candidate<'pat, 'tcx>, | |
150 | ) -> Result<(), MatchPair<'pat, 'tcx>> { | |
6a06907d | 151 | let tcx = self.tcx; |
92a42be0 | 152 | match *match_pair.pattern.kind { |
e74abb32 | 153 | PatKind::AscribeUserType { |
0731742a | 154 | ref subpattern, |
17df50a5 | 155 | ascription: thir::Ascription { variance, user_ty, user_ty_span }, |
0731742a XL |
156 | } => { |
157 | // Apply the type ascription to the value at `match_pair.place`, which is the | |
b7449926 | 158 | candidate.ascriptions.push(Ascription { |
0bf4aa26 | 159 | span: user_ty_span, |
74b04a01 | 160 | user_ty, |
6a06907d | 161 | source: match_pair.place.clone().into_place(self.tcx, self.typeck_results), |
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, |
6a06907d | 180 | source: match_pair.place.clone().into_place(self.tcx, self.typeck_results), |
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 || { |
6a06907d | 254 | self.tcx.features().exhaustive_patterns |
dfeec247 | 255 | && !v |
ba9703b0 | 256 | .uninhabited_from( |
6a06907d | 257 | self.tcx, |
ba9703b0 XL |
258 | substs, |
259 | adt_def.adt_kind(), | |
6a06907d | 260 | self.param_env, |
ba9703b0 | 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 { |
6a06907d XL |
267 | let place_builder = match_pair.place.downcast(adt_def, variant_index); |
268 | candidate | |
269 | .match_pairs | |
270 | .extend(self.field_match_pairs(place_builder, subpatterns)); | |
ff7c6d11 | 271 | Ok(()) |
32a655c1 SL |
272 | } else { |
273 | Err(match_pair) | |
274 | } | |
9fa01778 | 275 | } |
32a655c1 | 276 | |
e74abb32 | 277 | PatKind::Array { ref prefix, ref slice, ref suffix } => { |
dfeec247 XL |
278 | self.prefix_slice_suffix( |
279 | &mut candidate.match_pairs, | |
280 | &match_pair.place, | |
281 | prefix, | |
282 | slice.as_ref(), | |
283 | suffix, | |
284 | ); | |
3157f602 | 285 | Ok(()) |
e9174d1e SL |
286 | } |
287 | ||
e74abb32 | 288 | PatKind::Leaf { ref subpatterns } => { |
e9174d1e | 289 | // tuple struct, match subpats (if any) |
dfeec247 | 290 | candidate.match_pairs.extend(self.field_match_pairs(match_pair.place, subpatterns)); |
3157f602 | 291 | Ok(()) |
e9174d1e SL |
292 | } |
293 | ||
e74abb32 | 294 | PatKind::Deref { ref subpattern } => { |
6a06907d XL |
295 | let place_builder = match_pair.place.deref(); |
296 | candidate.match_pairs.push(MatchPair::new(place_builder, subpattern)); | |
3157f602 | 297 | Ok(()) |
e9174d1e | 298 | } |
e1599b0c | 299 | |
dfeec247 | 300 | PatKind::Or { .. } => Err(match_pair), |
e9174d1e SL |
301 | } |
302 | } | |
303 | } |