]>
Commit | Line | Data |
---|---|---|
1a4d82fc | 1 | // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT |
223e47cc LB |
2 | // file at the top-level directory of this distribution and at |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
1a4d82fc JJ |
11 | pub use self::Constructor::*; |
12 | use self::Usefulness::*; | |
13 | use self::WitnessPreference::*; | |
223e47cc | 14 | |
62682a34 | 15 | use middle::const_eval::{compare_const_vals, ConstVal}; |
c34b1796 AL |
16 | use middle::const_eval::{eval_const_expr, eval_const_expr_partial}; |
17 | use middle::const_eval::{const_expr_to_pat, lookup_const_by_id}; | |
c1a9b12d | 18 | use middle::const_eval::EvalHint::ExprTypeChecked; |
1a4d82fc JJ |
19 | use middle::def::*; |
20 | use middle::expr_use_visitor::{ConsumeMode, Delegate, ExprUseVisitor, Init}; | |
21 | use middle::expr_use_visitor::{JustWrite, LoanCause, MutateMode}; | |
c34b1796 | 22 | use middle::expr_use_visitor::WriteAndRead; |
1a4d82fc | 23 | use middle::expr_use_visitor as euv; |
c1a9b12d SL |
24 | use middle::infer; |
25 | use middle::mem_categorization::{cmt}; | |
223e47cc LB |
26 | use middle::pat_util::*; |
27 | use middle::ty::*; | |
28 | use middle::ty; | |
85aaf69f | 29 | use std::cmp::Ordering; |
1a4d82fc | 30 | use std::fmt; |
9346a6ac | 31 | use std::iter::{range_inclusive, FromIterator, IntoIterator, repeat}; |
1a4d82fc JJ |
32 | use std::slice; |
33 | use syntax::ast::{self, DUMMY_NODE_ID, NodeId, Pat}; | |
85aaf69f | 34 | use syntax::ast_util; |
1a4d82fc JJ |
35 | use syntax::codemap::{Span, Spanned, DUMMY_SP}; |
36 | use syntax::fold::{Folder, noop_fold_pat}; | |
37 | use syntax::print::pprust::pat_to_string; | |
1a4d82fc JJ |
38 | use syntax::ptr::P; |
39 | use syntax::visit::{self, Visitor, FnKind}; | |
85aaf69f | 40 | use util::nodemap::FnvHashMap; |
1a4d82fc JJ |
41 | |
42 | pub const DUMMY_WILD_PAT: &'static Pat = &Pat { | |
43 | id: DUMMY_NODE_ID, | |
44 | node: ast::PatWild(ast::PatWildSingle), | |
45 | span: DUMMY_SP | |
46 | }; | |
47 | ||
48 | struct Matrix<'a>(Vec<Vec<&'a Pat>>); | |
49 | ||
50 | /// Pretty-printer for matrices of patterns, example: | |
51 | /// ++++++++++++++++++++++++++ | |
52 | /// + _ + [] + | |
53 | /// ++++++++++++++++++++++++++ | |
54 | /// + true + [First] + | |
55 | /// ++++++++++++++++++++++++++ | |
56 | /// + true + [Second(true)] + | |
57 | /// ++++++++++++++++++++++++++ | |
58 | /// + false + [_] + | |
59 | /// ++++++++++++++++++++++++++ | |
60 | /// + _ + [_, _, ..tail] + | |
61 | /// ++++++++++++++++++++++++++ | |
85aaf69f | 62 | impl<'a> fmt::Debug for Matrix<'a> { |
1a4d82fc JJ |
63 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
64 | try!(write!(f, "\n")); | |
65 | ||
66 | let &Matrix(ref m) = self; | |
67 | let pretty_printed_matrix: Vec<Vec<String>> = m.iter().map(|row| { | |
68 | row.iter() | |
69 | .map(|&pat| pat_to_string(&*pat)) | |
70 | .collect::<Vec<String>>() | |
71 | }).collect(); | |
72 | ||
85aaf69f | 73 | let column_count = m.iter().map(|row| row.len()).max().unwrap_or(0); |
1a4d82fc | 74 | assert!(m.iter().all(|row| row.len() == column_count)); |
c34b1796 | 75 | let column_widths: Vec<usize> = (0..column_count).map(|col| { |
85aaf69f | 76 | pretty_printed_matrix.iter().map(|row| row[col].len()).max().unwrap_or(0) |
1a4d82fc JJ |
77 | }).collect(); |
78 | ||
9346a6ac | 79 | let total_width = column_widths.iter().cloned().sum::<usize>() + column_count * 3 + 1; |
1a4d82fc JJ |
80 | let br = repeat('+').take(total_width).collect::<String>(); |
81 | try!(write!(f, "{}\n", br)); | |
85aaf69f | 82 | for row in pretty_printed_matrix { |
1a4d82fc JJ |
83 | try!(write!(f, "+")); |
84 | for (column, pat_str) in row.into_iter().enumerate() { | |
85 | try!(write!(f, " ")); | |
86 | try!(write!(f, "{:1$}", pat_str, column_widths[column])); | |
87 | try!(write!(f, " +")); | |
88 | } | |
89 | try!(write!(f, "\n")); | |
90 | try!(write!(f, "{}\n", br)); | |
91 | } | |
92 | Ok(()) | |
93 | } | |
223e47cc LB |
94 | } |
95 | ||
1a4d82fc | 96 | impl<'a> FromIterator<Vec<&'a Pat>> for Matrix<'a> { |
85aaf69f SL |
97 | fn from_iter<T: IntoIterator<Item=Vec<&'a Pat>>>(iter: T) -> Matrix<'a> { |
98 | Matrix(iter.into_iter().collect()) | |
223e47cc | 99 | } |
1a4d82fc JJ |
100 | } |
101 | ||
c1a9b12d | 102 | //NOTE: appears to be the only place other then InferCtxt to contain a ParamEnv |
1a4d82fc JJ |
103 | pub struct MatchCheckCtxt<'a, 'tcx: 'a> { |
104 | pub tcx: &'a ty::ctxt<'tcx>, | |
105 | pub param_env: ParameterEnvironment<'a, 'tcx>, | |
106 | } | |
107 | ||
108 | #[derive(Clone, PartialEq)] | |
109 | pub enum Constructor { | |
110 | /// The constructor of all patterns that don't vary by constructor, | |
111 | /// e.g. struct patterns and fixed-length arrays. | |
112 | Single, | |
113 | /// Enum variants. | |
114 | Variant(ast::DefId), | |
115 | /// Literal values. | |
62682a34 | 116 | ConstantValue(ConstVal), |
1a4d82fc | 117 | /// Ranges of literal values (2..5). |
62682a34 | 118 | ConstantRange(ConstVal, ConstVal), |
1a4d82fc | 119 | /// Array patterns of length n. |
c34b1796 | 120 | Slice(usize), |
1a4d82fc | 121 | /// Array patterns with a subslice. |
c34b1796 | 122 | SliceWithSubslice(usize, usize) |
1a4d82fc | 123 | } |
223e47cc | 124 | |
1a4d82fc JJ |
125 | #[derive(Clone, PartialEq)] |
126 | enum Usefulness { | |
127 | Useful, | |
128 | UsefulWithWitness(Vec<P<Pat>>), | |
129 | NotUseful | |
223e47cc LB |
130 | } |
131 | ||
c34b1796 | 132 | #[derive(Copy, Clone)] |
1a4d82fc JJ |
133 | enum WitnessPreference { |
134 | ConstructWitness, | |
135 | LeaveOutWitness | |
136 | } | |
137 | ||
138 | impl<'a, 'tcx, 'v> Visitor<'v> for MatchCheckCtxt<'a, 'tcx> { | |
139 | fn visit_expr(&mut self, ex: &ast::Expr) { | |
140 | check_expr(self, ex); | |
141 | } | |
142 | fn visit_local(&mut self, l: &ast::Local) { | |
143 | check_local(self, l); | |
144 | } | |
145 | fn visit_fn(&mut self, fk: FnKind<'v>, fd: &'v ast::FnDecl, | |
146 | b: &'v ast::Block, s: Span, n: NodeId) { | |
147 | check_fn(self, fk, fd, b, s, n); | |
148 | } | |
149 | } | |
150 | ||
151 | pub fn check_crate(tcx: &ty::ctxt) { | |
152 | visit::walk_crate(&mut MatchCheckCtxt { | |
153 | tcx: tcx, | |
c1a9b12d | 154 | param_env: tcx.empty_parameter_environment(), |
1a4d82fc JJ |
155 | }, tcx.map.krate()); |
156 | tcx.sess.abort_if_errors(); | |
157 | } | |
158 | ||
159 | fn check_expr(cx: &mut MatchCheckCtxt, ex: &ast::Expr) { | |
160 | visit::walk_expr(cx, ex); | |
223e47cc | 161 | match ex.node { |
1a4d82fc | 162 | ast::ExprMatch(ref scrut, ref arms, source) => { |
85aaf69f | 163 | for arm in arms { |
1a4d82fc JJ |
164 | // First, check legality of move bindings. |
165 | check_legality_of_move_bindings(cx, | |
166 | arm.guard.is_some(), | |
c34b1796 | 167 | &arm.pats); |
1a4d82fc JJ |
168 | |
169 | // Second, if there is a guard on each arm, make sure it isn't | |
170 | // assigning or borrowing anything mutably. | |
171 | match arm.guard { | |
172 | Some(ref guard) => check_for_mutation_in_guard(cx, &**guard), | |
173 | None => {} | |
174 | } | |
175 | } | |
176 | ||
85aaf69f | 177 | let mut static_inliner = StaticInliner::new(cx.tcx, None); |
1a4d82fc JJ |
178 | let inlined_arms = arms.iter().map(|arm| { |
179 | (arm.pats.iter().map(|pat| { | |
180 | static_inliner.fold_pat((*pat).clone()) | |
181 | }).collect(), arm.guard.as_ref().map(|e| &**e)) | |
182 | }).collect::<Vec<(Vec<P<Pat>>, Option<&ast::Expr>)>>(); | |
183 | ||
184 | // Bail out early if inlining failed. | |
185 | if static_inliner.failed { | |
186 | return; | |
187 | } | |
188 | ||
189 | for pat in inlined_arms | |
190 | .iter() | |
62682a34 | 191 | .flat_map(|&(ref pats, _)| pats) { |
1a4d82fc JJ |
192 | // Third, check legality of move bindings. |
193 | check_legality_of_bindings_in_at_patterns(cx, &**pat); | |
194 | ||
195 | // Fourth, check if there are any references to NaN that we should warn about. | |
196 | check_for_static_nan(cx, &**pat); | |
197 | ||
198 | // Fifth, check if for any of the patterns that match an enumerated type | |
199 | // are bindings with the same name as one of the variants of said type. | |
200 | check_for_bindings_named_the_same_as_variants(cx, &**pat); | |
201 | } | |
202 | ||
203 | // Fourth, check for unreachable arms. | |
85aaf69f | 204 | check_arms(cx, &inlined_arms[..], source); |
223e47cc | 205 | |
1a4d82fc JJ |
206 | // Finally, check if the whole match expression is exhaustive. |
207 | // Check for empty enum, because is_useful only works on inhabited types. | |
c1a9b12d | 208 | let pat_ty = cx.tcx.node_id_to_type(scrut.id); |
1a4d82fc | 209 | if inlined_arms.is_empty() { |
c1a9b12d | 210 | if !pat_ty.is_empty(cx.tcx) { |
1a4d82fc JJ |
211 | // We know the type is inhabited, so this must be wrong |
212 | span_err!(cx.tcx.sess, ex.span, E0002, | |
62682a34 SL |
213 | "non-exhaustive patterns: type {} is non-empty", |
214 | pat_ty); | |
1a4d82fc JJ |
215 | } |
216 | // If the type *is* empty, it's vacuously exhaustive | |
217 | return; | |
223e47cc | 218 | } |
1a4d82fc JJ |
219 | |
220 | let matrix: Matrix = inlined_arms | |
221 | .iter() | |
222 | .filter(|&&(_, guard)| guard.is_none()) | |
62682a34 | 223 | .flat_map(|arm| &arm.0) |
1a4d82fc JJ |
224 | .map(|pat| vec![&**pat]) |
225 | .collect(); | |
85aaf69f | 226 | check_exhaustive(cx, ex.span, &matrix, source); |
1a4d82fc | 227 | }, |
1a4d82fc JJ |
228 | _ => () |
229 | } | |
230 | } | |
231 | ||
1a4d82fc | 232 | fn check_for_bindings_named_the_same_as_variants(cx: &MatchCheckCtxt, pat: &Pat) { |
85aaf69f | 233 | ast_util::walk_pat(pat, |p| { |
1a4d82fc JJ |
234 | match p.node { |
235 | ast::PatIdent(ast::BindByValue(ast::MutImmutable), ident, None) => { | |
c1a9b12d | 236 | let pat_ty = cx.tcx.pat_ty(p); |
62682a34 | 237 | if let ty::TyEnum(def_id, _) = pat_ty.sty { |
c34b1796 | 238 | let def = cx.tcx.def_map.borrow().get(&p.id).map(|d| d.full_def()); |
1a4d82fc | 239 | if let Some(DefLocal(_)) = def { |
c1a9b12d SL |
240 | if cx.tcx.enum_variants(def_id).iter().any(|variant| |
241 | variant.name == ident.node.name | |
9346a6ac | 242 | && variant.args.is_empty() |
1a4d82fc JJ |
243 | ) { |
244 | span_warn!(cx.tcx.sess, p.span, E0170, | |
245 | "pattern binding `{}` is named the same as one \ | |
246 | of the variants of the type `{}`", | |
c1a9b12d | 247 | ident.node, pat_ty); |
c34b1796 | 248 | fileline_help!(cx.tcx.sess, p.span, |
1a4d82fc JJ |
249 | "if you meant to match on a variant, \ |
250 | consider making the path in the pattern qualified: `{}::{}`", | |
c1a9b12d | 251 | pat_ty, ident.node); |
1a4d82fc JJ |
252 | } |
253 | } | |
254 | } | |
255 | } | |
256 | _ => () | |
257 | } | |
258 | true | |
259 | }); | |
260 | } | |
261 | ||
262 | // Check that we do not match against a static NaN (#6804) | |
263 | fn check_for_static_nan(cx: &MatchCheckCtxt, pat: &Pat) { | |
85aaf69f | 264 | ast_util::walk_pat(pat, |p| { |
c34b1796 | 265 | if let ast::PatLit(ref expr) = p.node { |
c1a9b12d | 266 | match eval_const_expr_partial(cx.tcx, &**expr, ExprTypeChecked) { |
62682a34 | 267 | Ok(ConstVal::Float(f)) if f.is_nan() => { |
c34b1796 AL |
268 | span_warn!(cx.tcx.sess, p.span, E0003, |
269 | "unmatchable NaN in pattern, \ | |
270 | use the is_nan method in a guard instead"); | |
271 | } | |
272 | Ok(_) => {} | |
273 | ||
274 | Err(err) => { | |
275 | let subspan = p.span.lo <= err.span.lo && err.span.hi <= p.span.hi; | |
276 | cx.tcx.sess.span_err(err.span, | |
277 | &format!("constant evaluation error: {}", | |
278 | err.description())); | |
279 | if !subspan { | |
280 | cx.tcx.sess.span_note(p.span, | |
281 | "in pattern here") | |
282 | } | |
283 | } | |
1a4d82fc | 284 | } |
1a4d82fc JJ |
285 | } |
286 | true | |
287 | }); | |
288 | } | |
289 | ||
223e47cc | 290 | // Check for unreachable patterns |
1a4d82fc JJ |
291 | fn check_arms(cx: &MatchCheckCtxt, |
292 | arms: &[(Vec<P<Pat>>, Option<&ast::Expr>)], | |
293 | source: ast::MatchSource) { | |
294 | let mut seen = Matrix(vec![]); | |
295 | let mut printed_if_let_err = false; | |
85aaf69f SL |
296 | for &(ref pats, guard) in arms { |
297 | for pat in pats { | |
1a4d82fc JJ |
298 | let v = vec![&**pat]; |
299 | ||
85aaf69f | 300 | match is_useful(cx, &seen, &v[..], LeaveOutWitness) { |
1a4d82fc JJ |
301 | NotUseful => { |
302 | match source { | |
303 | ast::MatchSource::IfLetDesugar { .. } => { | |
304 | if printed_if_let_err { | |
305 | // we already printed an irrefutable if-let pattern error. | |
306 | // We don't want two, that's just confusing. | |
307 | } else { | |
308 | // find the first arm pattern so we can use its span | |
309 | let &(ref first_arm_pats, _) = &arms[0]; | |
310 | let first_pat = &first_arm_pats[0]; | |
311 | let span = first_pat.span; | |
312 | span_err!(cx.tcx.sess, span, E0162, "irrefutable if-let pattern"); | |
313 | printed_if_let_err = true; | |
314 | } | |
315 | }, | |
316 | ||
317 | ast::MatchSource::WhileLetDesugar => { | |
318 | // find the first arm pattern so we can use its span | |
319 | let &(ref first_arm_pats, _) = &arms[0]; | |
320 | let first_pat = &first_arm_pats[0]; | |
321 | let span = first_pat.span; | |
322 | span_err!(cx.tcx.sess, span, E0165, "irrefutable while-let pattern"); | |
323 | }, | |
324 | ||
85aaf69f SL |
325 | ast::MatchSource::ForLoopDesugar => { |
326 | // this is a bug, because on `match iter.next()` we cover | |
327 | // `Some(<head>)` and `None`. It's impossible to have an unreachable | |
328 | // pattern | |
329 | // (see libsyntax/ext/expand.rs for the full expansion of a for loop) | |
330 | cx.tcx.sess.span_bug(pat.span, "unreachable for-loop pattern") | |
331 | }, | |
332 | ||
1a4d82fc JJ |
333 | ast::MatchSource::Normal => { |
334 | span_err!(cx.tcx.sess, pat.span, E0001, "unreachable pattern") | |
335 | }, | |
336 | } | |
337 | } | |
338 | Useful => (), | |
339 | UsefulWithWitness(_) => unreachable!() | |
340 | } | |
341 | if guard.is_none() { | |
342 | let Matrix(mut rows) = seen; | |
343 | rows.push(v); | |
344 | seen = Matrix(rows); | |
223e47cc | 345 | } |
223e47cc LB |
346 | } |
347 | } | |
348 | } | |
349 | ||
1a4d82fc | 350 | fn raw_pat<'a>(p: &'a Pat) -> &'a Pat { |
223e47cc | 351 | match p.node { |
1a4d82fc JJ |
352 | ast::PatIdent(_, _, Some(ref s)) => raw_pat(&**s), |
353 | _ => p | |
223e47cc LB |
354 | } |
355 | } | |
356 | ||
85aaf69f | 357 | fn check_exhaustive(cx: &MatchCheckCtxt, sp: Span, matrix: &Matrix, source: ast::MatchSource) { |
1a4d82fc JJ |
358 | match is_useful(cx, matrix, &[DUMMY_WILD_PAT], ConstructWitness) { |
359 | UsefulWithWitness(pats) => { | |
85aaf69f | 360 | let witness = match &pats[..] { |
1a4d82fc JJ |
361 | [ref witness] => &**witness, |
362 | [] => DUMMY_WILD_PAT, | |
363 | _ => unreachable!() | |
364 | }; | |
85aaf69f SL |
365 | match source { |
366 | ast::MatchSource::ForLoopDesugar => { | |
367 | // `witness` has the form `Some(<head>)`, peel off the `Some` | |
368 | let witness = match witness.node { | |
369 | ast::PatEnum(_, Some(ref pats)) => match &pats[..] { | |
370 | [ref pat] => &**pat, | |
371 | _ => unreachable!(), | |
372 | }, | |
373 | _ => unreachable!(), | |
374 | }; | |
375 | ||
376 | span_err!(cx.tcx.sess, sp, E0297, | |
377 | "refutable pattern in `for` loop binding: \ | |
378 | `{}` not covered", | |
379 | pat_to_string(witness)); | |
380 | }, | |
381 | _ => { | |
382 | span_err!(cx.tcx.sess, sp, E0004, | |
383 | "non-exhaustive patterns: `{}` not covered", | |
384 | pat_to_string(witness) | |
385 | ); | |
386 | }, | |
387 | } | |
1a4d82fc JJ |
388 | } |
389 | NotUseful => { | |
223e47cc | 390 | // This is good, wildcard pattern isn't reachable |
1a4d82fc JJ |
391 | }, |
392 | _ => unreachable!() | |
393 | } | |
394 | } | |
395 | ||
62682a34 | 396 | fn const_val_to_expr(value: &ConstVal) -> P<ast::Expr> { |
1a4d82fc | 397 | let node = match value { |
62682a34 | 398 | &ConstVal::Bool(b) => ast::LitBool(b), |
1a4d82fc JJ |
399 | _ => unreachable!() |
400 | }; | |
401 | P(ast::Expr { | |
402 | id: 0, | |
403 | node: ast::ExprLit(P(Spanned { node: node, span: DUMMY_SP })), | |
404 | span: DUMMY_SP | |
405 | }) | |
406 | } | |
407 | ||
408 | pub struct StaticInliner<'a, 'tcx: 'a> { | |
409 | pub tcx: &'a ty::ctxt<'tcx>, | |
85aaf69f SL |
410 | pub failed: bool, |
411 | pub renaming_map: Option<&'a mut FnvHashMap<(NodeId, Span), NodeId>>, | |
1a4d82fc JJ |
412 | } |
413 | ||
414 | impl<'a, 'tcx> StaticInliner<'a, 'tcx> { | |
85aaf69f SL |
415 | pub fn new<'b>(tcx: &'b ty::ctxt<'tcx>, |
416 | renaming_map: Option<&'b mut FnvHashMap<(NodeId, Span), NodeId>>) | |
417 | -> StaticInliner<'b, 'tcx> { | |
1a4d82fc JJ |
418 | StaticInliner { |
419 | tcx: tcx, | |
85aaf69f SL |
420 | failed: false, |
421 | renaming_map: renaming_map | |
223e47cc | 422 | } |
1a4d82fc JJ |
423 | } |
424 | } | |
425 | ||
85aaf69f SL |
426 | struct RenamingRecorder<'map> { |
427 | substituted_node_id: NodeId, | |
428 | origin_span: Span, | |
429 | renaming_map: &'map mut FnvHashMap<(NodeId, Span), NodeId> | |
430 | } | |
431 | ||
432 | impl<'map> ast_util::IdVisitingOperation for RenamingRecorder<'map> { | |
433 | fn visit_id(&mut self, node_id: NodeId) { | |
434 | let key = (node_id, self.origin_span); | |
435 | self.renaming_map.insert(key, self.substituted_node_id); | |
436 | } | |
437 | } | |
438 | ||
1a4d82fc JJ |
439 | impl<'a, 'tcx> Folder for StaticInliner<'a, 'tcx> { |
440 | fn fold_pat(&mut self, pat: P<Pat>) -> P<Pat> { | |
85aaf69f | 441 | return match pat.node { |
d9579d0f | 442 | ast::PatIdent(..) | ast::PatEnum(..) | ast::PatQPath(..) => { |
c34b1796 | 443 | let def = self.tcx.def_map.borrow().get(&pat.id).map(|d| d.full_def()); |
1a4d82fc | 444 | match def { |
c1a9b12d | 445 | Some(DefAssociatedConst(did)) | |
d9579d0f | 446 | Some(DefConst(did)) => match lookup_const_by_id(self.tcx, did, Some(pat.id)) { |
1a4d82fc | 447 | Some(const_expr) => { |
85aaf69f SL |
448 | const_expr_to_pat(self.tcx, const_expr, pat.span).map(|new_pat| { |
449 | ||
450 | if let Some(ref mut renaming_map) = self.renaming_map { | |
451 | // Record any renamings we do here | |
452 | record_renamings(const_expr, &pat, renaming_map); | |
453 | } | |
454 | ||
1a4d82fc JJ |
455 | new_pat |
456 | }) | |
457 | } | |
223e47cc | 458 | None => { |
1a4d82fc JJ |
459 | self.failed = true; |
460 | span_err!(self.tcx.sess, pat.span, E0158, | |
461 | "statics cannot be referenced in patterns"); | |
462 | pat | |
223e47cc | 463 | } |
1a4d82fc JJ |
464 | }, |
465 | _ => noop_fold_pat(pat, self) | |
223e47cc | 466 | } |
1a4d82fc JJ |
467 | } |
468 | _ => noop_fold_pat(pat, self) | |
85aaf69f SL |
469 | }; |
470 | ||
471 | fn record_renamings(const_expr: &ast::Expr, | |
472 | substituted_pat: &ast::Pat, | |
473 | renaming_map: &mut FnvHashMap<(NodeId, Span), NodeId>) { | |
474 | let mut renaming_recorder = RenamingRecorder { | |
475 | substituted_node_id: substituted_pat.id, | |
476 | origin_span: substituted_pat.span, | |
477 | renaming_map: renaming_map, | |
478 | }; | |
479 | ||
480 | let mut id_visitor = ast_util::IdVisitor { | |
481 | operation: &mut renaming_recorder, | |
482 | pass_through_items: true, | |
483 | visited_outermost: false, | |
484 | }; | |
485 | ||
486 | id_visitor.visit_expr(const_expr); | |
1a4d82fc JJ |
487 | } |
488 | } | |
489 | } | |
490 | ||
491 | /// Constructs a partial witness for a pattern given a list of | |
492 | /// patterns expanded by the specialization step. | |
493 | /// | |
494 | /// When a pattern P is discovered to be useful, this function is used bottom-up | |
495 | /// to reconstruct a complete witness, e.g. a pattern P' that covers a subset | |
496 | /// of values, V, where each value in that set is not covered by any previously | |
497 | /// used patterns and is covered by the pattern P'. Examples: | |
498 | /// | |
499 | /// left_ty: tuple of 3 elements | |
500 | /// pats: [10, 20, _] => (10, 20, _) | |
501 | /// | |
c34b1796 | 502 | /// left_ty: struct X { a: (bool, &'static str), b: usize} |
1a4d82fc JJ |
503 | /// pats: [(false, "foo"), 42] => X { a: (false, "foo"), b: 42 } |
504 | fn construct_witness(cx: &MatchCheckCtxt, ctor: &Constructor, | |
505 | pats: Vec<&Pat>, left_ty: Ty) -> P<Pat> { | |
506 | let pats_len = pats.len(); | |
507 | let mut pats = pats.into_iter().map(|p| P((*p).clone())); | |
508 | let pat = match left_ty.sty { | |
62682a34 | 509 | ty::TyTuple(_) => ast::PatTup(pats.collect()), |
1a4d82fc | 510 | |
62682a34 | 511 | ty::TyEnum(cid, _) | ty::TyStruct(cid, _) => { |
1a4d82fc JJ |
512 | let (vid, is_structure) = match ctor { |
513 | &Variant(vid) => | |
c1a9b12d | 514 | (vid, cx.tcx.enum_variant_with_id(cid, vid).arg_names.is_some()), |
1a4d82fc | 515 | _ => |
c1a9b12d | 516 | (cid, !cx.tcx.is_tuple_struct(cid)) |
1a4d82fc JJ |
517 | }; |
518 | if is_structure { | |
c1a9b12d | 519 | let fields = cx.tcx.lookup_struct_fields(vid); |
1a4d82fc JJ |
520 | let field_pats: Vec<_> = fields.into_iter() |
521 | .zip(pats) | |
522 | .filter(|&(_, ref pat)| pat.node != ast::PatWild(ast::PatWildSingle)) | |
523 | .map(|(field, pat)| Spanned { | |
524 | span: DUMMY_SP, | |
525 | node: ast::FieldPat { | |
526 | ident: ast::Ident::new(field.name), | |
527 | pat: pat, | |
528 | is_shorthand: false, | |
529 | } | |
530 | }).collect(); | |
531 | let has_more_fields = field_pats.len() < pats_len; | |
532 | ast::PatStruct(def_to_path(cx.tcx, vid), field_pats, has_more_fields) | |
533 | } else { | |
534 | ast::PatEnum(def_to_path(cx.tcx, vid), Some(pats.collect())) | |
535 | } | |
536 | } | |
537 | ||
c1a9b12d | 538 | ty::TyRef(_, ty::TypeAndMut { ty, mutbl }) => { |
1a4d82fc | 539 | match ty.sty { |
62682a34 | 540 | ty::TyArray(_, n) => match ctor { |
1a4d82fc JJ |
541 | &Single => { |
542 | assert_eq!(pats_len, n); | |
543 | ast::PatVec(pats.collect(), None, vec!()) | |
544 | }, | |
545 | _ => unreachable!() | |
546 | }, | |
62682a34 | 547 | ty::TySlice(_) => match ctor { |
1a4d82fc JJ |
548 | &Slice(n) => { |
549 | assert_eq!(pats_len, n); | |
550 | ast::PatVec(pats.collect(), None, vec!()) | |
551 | }, | |
552 | _ => unreachable!() | |
553 | }, | |
62682a34 | 554 | ty::TyStr => ast::PatWild(ast::PatWildSingle), |
1a4d82fc JJ |
555 | |
556 | _ => { | |
557 | assert_eq!(pats_len, 1); | |
558 | ast::PatRegion(pats.nth(0).unwrap(), mutbl) | |
223e47cc | 559 | } |
1a4d82fc JJ |
560 | } |
561 | } | |
562 | ||
62682a34 | 563 | ty::TyArray(_, len) => { |
1a4d82fc JJ |
564 | assert_eq!(pats_len, len); |
565 | ast::PatVec(pats.collect(), None, vec![]) | |
566 | } | |
567 | ||
568 | _ => { | |
569 | match *ctor { | |
570 | ConstantValue(ref v) => ast::PatLit(const_val_to_expr(v)), | |
571 | _ => ast::PatWild(ast::PatWildSingle), | |
223e47cc LB |
572 | } |
573 | } | |
574 | }; | |
1a4d82fc JJ |
575 | |
576 | P(ast::Pat { | |
577 | id: 0, | |
578 | node: pat, | |
579 | span: DUMMY_SP | |
580 | }) | |
223e47cc LB |
581 | } |
582 | ||
1a4d82fc | 583 | fn missing_constructor(cx: &MatchCheckCtxt, &Matrix(ref rows): &Matrix, |
c34b1796 | 584 | left_ty: Ty, max_slice_length: usize) -> Option<Constructor> { |
1a4d82fc | 585 | let used_constructors: Vec<Constructor> = rows.iter() |
62682a34 | 586 | .flat_map(|row| pat_constructors(cx, row[0], left_ty, max_slice_length)) |
1a4d82fc JJ |
587 | .collect(); |
588 | all_constructors(cx, left_ty, max_slice_length) | |
589 | .into_iter() | |
590 | .find(|c| !used_constructors.contains(c)) | |
591 | } | |
592 | ||
593 | /// This determines the set of all possible constructors of a pattern matching | |
594 | /// values of type `left_ty`. For vectors, this would normally be an infinite set | |
595 | /// but is instead bounded by the maximum fixed length of slice patterns in | |
596 | /// the column of patterns being analyzed. | |
597 | fn all_constructors(cx: &MatchCheckCtxt, left_ty: Ty, | |
c34b1796 | 598 | max_slice_length: usize) -> Vec<Constructor> { |
1a4d82fc | 599 | match left_ty.sty { |
62682a34 SL |
600 | ty::TyBool => |
601 | [true, false].iter().map(|b| ConstantValue(ConstVal::Bool(*b))).collect(), | |
223e47cc | 602 | |
c1a9b12d | 603 | ty::TyRef(_, ty::TypeAndMut { ty, .. }) => match ty.sty { |
62682a34 | 604 | ty::TySlice(_) => |
1a4d82fc JJ |
605 | range_inclusive(0, max_slice_length).map(|length| Slice(length)).collect(), |
606 | _ => vec!(Single) | |
607 | }, | |
223e47cc | 608 | |
62682a34 | 609 | ty::TyEnum(eid, _) => |
c1a9b12d | 610 | cx.tcx.enum_variants(eid) |
1a4d82fc JJ |
611 | .iter() |
612 | .map(|va| Variant(va.id)) | |
613 | .collect(), | |
614 | ||
615 | _ => | |
616 | vec!(Single) | |
617 | } | |
223e47cc LB |
618 | } |
619 | ||
620 | // Algorithm from http://moscova.inria.fr/~maranget/papers/warn/index.html | |
621 | // | |
622 | // Whether a vector `v` of patterns is 'useful' in relation to a set of such | |
623 | // vectors `m` is defined as there being a set of inputs that will match `v` | |
624 | // but not any of the sets in `m`. | |
625 | // | |
626 | // This is used both for reachability checking (if a pattern isn't useful in | |
627 | // relation to preceding patterns, it is not reachable) and exhaustiveness | |
628 | // checking (if a wildcard pattern is useful in relation to a matrix, the | |
629 | // matrix isn't exhaustive). | |
630 | ||
631 | // Note: is_useful doesn't work on empty types, as the paper notes. | |
632 | // So it assumes that v is non-empty. | |
1a4d82fc JJ |
633 | fn is_useful(cx: &MatchCheckCtxt, |
634 | matrix: &Matrix, | |
635 | v: &[&Pat], | |
636 | witness: WitnessPreference) | |
637 | -> Usefulness { | |
638 | let &Matrix(ref rows) = matrix; | |
639 | debug!("{:?}", matrix); | |
9346a6ac | 640 | if rows.is_empty() { |
1a4d82fc JJ |
641 | return match witness { |
642 | ConstructWitness => UsefulWithWitness(vec!()), | |
643 | LeaveOutWitness => Useful | |
644 | }; | |
645 | } | |
9346a6ac | 646 | if rows[0].is_empty() { |
1a4d82fc JJ |
647 | return NotUseful; |
648 | } | |
c34b1796 | 649 | assert!(rows.iter().all(|r| r.len() == v.len())); |
1a4d82fc JJ |
650 | let real_pat = match rows.iter().find(|r| (*r)[0].id != DUMMY_NODE_ID) { |
651 | Some(r) => raw_pat(r[0]), | |
9346a6ac | 652 | None if v.is_empty() => return NotUseful, |
1a4d82fc | 653 | None => v[0] |
223e47cc | 654 | }; |
1a4d82fc | 655 | let left_ty = if real_pat.id == DUMMY_NODE_ID { |
c1a9b12d | 656 | cx.tcx.mk_nil() |
1a4d82fc | 657 | } else { |
c1a9b12d | 658 | let left_ty = cx.tcx.pat_ty(&*real_pat); |
c34b1796 AL |
659 | |
660 | match real_pat.node { | |
c1a9b12d SL |
661 | ast::PatIdent(ast::BindByRef(..), _, _) => { |
662 | left_ty.builtin_deref(false).unwrap().ty | |
663 | } | |
c34b1796 AL |
664 | _ => left_ty, |
665 | } | |
1a4d82fc JJ |
666 | }; |
667 | ||
668 | let max_slice_length = rows.iter().filter_map(|row| match row[0].node { | |
669 | ast::PatVec(ref before, _, ref after) => Some(before.len() + after.len()), | |
670 | _ => None | |
671 | }).max().map_or(0, |v| v + 1); | |
672 | ||
673 | let constructors = pat_constructors(cx, v[0], left_ty, max_slice_length); | |
674 | if constructors.is_empty() { | |
675 | match missing_constructor(cx, matrix, left_ty, max_slice_length) { | |
676 | None => { | |
677 | all_constructors(cx, left_ty, max_slice_length).into_iter().map(|c| { | |
678 | match is_useful_specialized(cx, matrix, v, c.clone(), left_ty, witness) { | |
679 | UsefulWithWitness(pats) => UsefulWithWitness({ | |
680 | let arity = constructor_arity(cx, &c, left_ty); | |
681 | let mut result = { | |
85aaf69f SL |
682 | let pat_slice = &pats[..]; |
683 | let subpats: Vec<_> = (0..arity).map(|i| { | |
1a4d82fc JJ |
684 | pat_slice.get(i).map_or(DUMMY_WILD_PAT, |p| &**p) |
685 | }).collect(); | |
686 | vec![construct_witness(cx, &c, subpats, left_ty)] | |
687 | }; | |
688 | result.extend(pats.into_iter().skip(arity)); | |
689 | result | |
690 | }), | |
691 | result => result | |
223e47cc | 692 | } |
1a4d82fc JJ |
693 | }).find(|result| result != &NotUseful).unwrap_or(NotUseful) |
694 | }, | |
695 | ||
696 | Some(constructor) => { | |
697 | let matrix = rows.iter().filter_map(|r| { | |
698 | if pat_is_binding_or_wild(&cx.tcx.def_map, raw_pat(r[0])) { | |
c1a9b12d | 699 | Some(r[1..].to_vec()) |
1a4d82fc JJ |
700 | } else { |
701 | None | |
223e47cc | 702 | } |
1a4d82fc | 703 | }).collect(); |
c1a9b12d | 704 | match is_useful(cx, &matrix, &v[1..], witness) { |
1a4d82fc JJ |
705 | UsefulWithWitness(pats) => { |
706 | let arity = constructor_arity(cx, &constructor, left_ty); | |
c1a9b12d | 707 | let wild_pats = vec![DUMMY_WILD_PAT; arity]; |
1a4d82fc JJ |
708 | let enum_pat = construct_witness(cx, &constructor, wild_pats, left_ty); |
709 | let mut new_pats = vec![enum_pat]; | |
62682a34 | 710 | new_pats.extend(pats); |
1a4d82fc JJ |
711 | UsefulWithWitness(new_pats) |
712 | }, | |
713 | result => result | |
223e47cc | 714 | } |
223e47cc | 715 | } |
223e47cc | 716 | } |
1a4d82fc JJ |
717 | } else { |
718 | constructors.into_iter().map(|c| | |
719 | is_useful_specialized(cx, matrix, v, c.clone(), left_ty, witness) | |
720 | ).find(|result| result != &NotUseful).unwrap_or(NotUseful) | |
223e47cc LB |
721 | } |
722 | } | |
723 | ||
1a4d82fc JJ |
724 | fn is_useful_specialized(cx: &MatchCheckCtxt, &Matrix(ref m): &Matrix, |
725 | v: &[&Pat], ctor: Constructor, lty: Ty, | |
726 | witness: WitnessPreference) -> Usefulness { | |
727 | let arity = constructor_arity(cx, &ctor, lty); | |
728 | let matrix = Matrix(m.iter().filter_map(|r| { | |
85aaf69f | 729 | specialize(cx, &r[..], &ctor, 0, arity) |
1a4d82fc | 730 | }).collect()); |
85aaf69f SL |
731 | match specialize(cx, v, &ctor, 0, arity) { |
732 | Some(v) => is_useful(cx, &matrix, &v[..], witness), | |
1a4d82fc | 733 | None => NotUseful |
223e47cc LB |
734 | } |
735 | } | |
736 | ||
1a4d82fc JJ |
737 | /// Determines the constructors that the given pattern can be specialized to. |
738 | /// | |
739 | /// In most cases, there's only one constructor that a specific pattern | |
740 | /// represents, such as a specific enum variant or a specific literal value. | |
741 | /// Slice patterns, however, can match slices of different lengths. For instance, | |
742 | /// `[a, b, ..tail]` can match a slice of length 2, 3, 4 and so on. | |
743 | /// | |
744 | /// On the other hand, a wild pattern and an identifier pattern cannot be | |
745 | /// specialized in any way. | |
746 | fn pat_constructors(cx: &MatchCheckCtxt, p: &Pat, | |
c34b1796 | 747 | left_ty: Ty, max_slice_length: usize) -> Vec<Constructor> { |
223e47cc LB |
748 | let pat = raw_pat(p); |
749 | match pat.node { | |
1a4d82fc | 750 | ast::PatIdent(..) => |
c34b1796 | 751 | match cx.tcx.def_map.borrow().get(&pat.id).map(|d| d.full_def()) { |
d9579d0f | 752 | Some(DefConst(..)) | Some(DefAssociatedConst(..)) => |
1a4d82fc JJ |
753 | cx.tcx.sess.span_bug(pat.span, "const pattern should've \ |
754 | been rewritten"), | |
c34b1796 AL |
755 | Some(DefStruct(_)) => vec!(Single), |
756 | Some(DefVariant(_, id, _)) => vec!(Variant(id)), | |
1a4d82fc JJ |
757 | _ => vec!() |
758 | }, | |
759 | ast::PatEnum(..) => | |
c34b1796 | 760 | match cx.tcx.def_map.borrow().get(&pat.id).map(|d| d.full_def()) { |
d9579d0f | 761 | Some(DefConst(..)) | Some(DefAssociatedConst(..)) => |
1a4d82fc JJ |
762 | cx.tcx.sess.span_bug(pat.span, "const pattern should've \ |
763 | been rewritten"), | |
c34b1796 | 764 | Some(DefVariant(_, id, _)) => vec!(Variant(id)), |
1a4d82fc JJ |
765 | _ => vec!(Single) |
766 | }, | |
d9579d0f AL |
767 | ast::PatQPath(..) => |
768 | cx.tcx.sess.span_bug(pat.span, "const pattern should've \ | |
769 | been rewritten"), | |
1a4d82fc | 770 | ast::PatStruct(..) => |
c34b1796 | 771 | match cx.tcx.def_map.borrow().get(&pat.id).map(|d| d.full_def()) { |
d9579d0f | 772 | Some(DefConst(..)) | Some(DefAssociatedConst(..)) => |
1a4d82fc JJ |
773 | cx.tcx.sess.span_bug(pat.span, "const pattern should've \ |
774 | been rewritten"), | |
c34b1796 | 775 | Some(DefVariant(_, id, _)) => vec!(Variant(id)), |
1a4d82fc JJ |
776 | _ => vec!(Single) |
777 | }, | |
778 | ast::PatLit(ref expr) => | |
779 | vec!(ConstantValue(eval_const_expr(cx.tcx, &**expr))), | |
780 | ast::PatRange(ref lo, ref hi) => | |
781 | vec!(ConstantRange(eval_const_expr(cx.tcx, &**lo), eval_const_expr(cx.tcx, &**hi))), | |
782 | ast::PatVec(ref before, ref slice, ref after) => | |
783 | match left_ty.sty { | |
62682a34 | 784 | ty::TyArray(_, _) => vec!(Single), |
1a4d82fc JJ |
785 | _ => if slice.is_some() { |
786 | range_inclusive(before.len() + after.len(), max_slice_length) | |
787 | .map(|length| Slice(length)) | |
788 | .collect() | |
789 | } else { | |
790 | vec!(Slice(before.len() + after.len())) | |
791 | } | |
792 | }, | |
793 | ast::PatBox(_) | ast::PatTup(_) | ast::PatRegion(..) => | |
794 | vec!(Single), | |
795 | ast::PatWild(_) => | |
796 | vec!(), | |
797 | ast::PatMac(_) => | |
798 | cx.tcx.sess.bug("unexpanded macro") | |
223e47cc LB |
799 | } |
800 | } | |
801 | ||
1a4d82fc JJ |
802 | /// This computes the arity of a constructor. The arity of a constructor |
803 | /// is how many subpattern patterns of that constructor should be expanded to. | |
804 | /// | |
85aaf69f | 805 | /// For instance, a tuple pattern (_, 42, Some([])) has the arity of 3. |
1a4d82fc | 806 | /// A struct pattern's arity is the number of fields it contains, etc. |
c34b1796 | 807 | pub fn constructor_arity(cx: &MatchCheckCtxt, ctor: &Constructor, ty: Ty) -> usize { |
1a4d82fc | 808 | match ty.sty { |
62682a34 SL |
809 | ty::TyTuple(ref fs) => fs.len(), |
810 | ty::TyBox(_) => 1, | |
c1a9b12d | 811 | ty::TyRef(_, ty::TypeAndMut { ty, .. }) => match ty.sty { |
62682a34 | 812 | ty::TySlice(_) => match *ctor { |
1a4d82fc | 813 | Slice(length) => length, |
85aaf69f | 814 | ConstantValue(_) => 0, |
1a4d82fc JJ |
815 | _ => unreachable!() |
816 | }, | |
62682a34 | 817 | ty::TyStr => 0, |
85aaf69f | 818 | _ => 1 |
1a4d82fc | 819 | }, |
62682a34 | 820 | ty::TyEnum(eid, _) => { |
1a4d82fc | 821 | match *ctor { |
c1a9b12d | 822 | Variant(id) => cx.tcx.enum_variant_with_id(eid, id).args.len(), |
1a4d82fc | 823 | _ => unreachable!() |
223e47cc LB |
824 | } |
825 | } | |
c1a9b12d | 826 | ty::TyStruct(cid, _) => cx.tcx.lookup_struct_fields(cid).len(), |
62682a34 | 827 | ty::TyArray(_, n) => n, |
85aaf69f | 828 | _ => 0 |
223e47cc LB |
829 | } |
830 | } | |
831 | ||
1a4d82fc | 832 | fn range_covered_by_constructor(ctor: &Constructor, |
62682a34 | 833 | from: &ConstVal, to: &ConstVal) -> Option<bool> { |
1a4d82fc JJ |
834 | let (c_from, c_to) = match *ctor { |
835 | ConstantValue(ref value) => (value, value), | |
836 | ConstantRange(ref from, ref to) => (from, to), | |
837 | Single => return Some(true), | |
838 | _ => unreachable!() | |
839 | }; | |
840 | let cmp_from = compare_const_vals(c_from, from); | |
841 | let cmp_to = compare_const_vals(c_to, to); | |
842 | match (cmp_from, cmp_to) { | |
85aaf69f SL |
843 | (Some(cmp_from), Some(cmp_to)) => { |
844 | Some(cmp_from != Ordering::Less && cmp_to != Ordering::Greater) | |
845 | } | |
1a4d82fc | 846 | _ => None |
223e47cc LB |
847 | } |
848 | } | |
849 | ||
1a4d82fc JJ |
850 | /// This is the main specialization step. It expands the first pattern in the given row |
851 | /// into `arity` patterns based on the constructor. For most patterns, the step is trivial, | |
852 | /// for instance tuple patterns are flattened and box patterns expand into their inner pattern. | |
853 | /// | |
854 | /// OTOH, slice patterns with a subslice pattern (..tail) can be expanded into multiple | |
855 | /// different patterns. | |
856 | /// Structure patterns with a partial wild pattern (Foo { a: 42, .. }) have their missing | |
857 | /// fields filled with wild patterns. | |
858 | pub fn specialize<'a>(cx: &MatchCheckCtxt, r: &[&'a Pat], | |
c34b1796 | 859 | constructor: &Constructor, col: usize, arity: usize) -> Option<Vec<&'a Pat>> { |
1a4d82fc JJ |
860 | let &Pat { |
861 | id: pat_id, ref node, span: pat_span | |
862 | } = raw_pat(r[col]); | |
863 | let head: Option<Vec<&Pat>> = match *node { | |
864 | ast::PatWild(_) => | |
c1a9b12d | 865 | Some(vec![DUMMY_WILD_PAT; arity]), |
223e47cc | 866 | |
1a4d82fc | 867 | ast::PatIdent(_, _, _) => { |
c34b1796 | 868 | let opt_def = cx.tcx.def_map.borrow().get(&pat_id).map(|d| d.full_def()); |
1a4d82fc | 869 | match opt_def { |
d9579d0f | 870 | Some(DefConst(..)) | Some(DefAssociatedConst(..)) => |
1a4d82fc JJ |
871 | cx.tcx.sess.span_bug(pat_span, "const pattern should've \ |
872 | been rewritten"), | |
873 | Some(DefVariant(_, id, _)) => if *constructor == Variant(id) { | |
874 | Some(vec!()) | |
875 | } else { | |
876 | None | |
877 | }, | |
c1a9b12d | 878 | _ => Some(vec![DUMMY_WILD_PAT; arity]) |
223e47cc | 879 | } |
1a4d82fc JJ |
880 | } |
881 | ||
882 | ast::PatEnum(_, ref args) => { | |
c34b1796 | 883 | let def = cx.tcx.def_map.borrow().get(&pat_id).unwrap().full_def(); |
1a4d82fc | 884 | match def { |
d9579d0f | 885 | DefConst(..) | DefAssociatedConst(..) => |
1a4d82fc JJ |
886 | cx.tcx.sess.span_bug(pat_span, "const pattern should've \ |
887 | been rewritten"), | |
888 | DefVariant(_, id, _) if *constructor != Variant(id) => None, | |
889 | DefVariant(..) | DefStruct(..) => { | |
890 | Some(match args { | |
891 | &Some(ref args) => args.iter().map(|p| &**p).collect(), | |
c1a9b12d | 892 | &None => vec![DUMMY_WILD_PAT; arity], |
1a4d82fc | 893 | }) |
223e47cc | 894 | } |
1a4d82fc | 895 | _ => None |
223e47cc | 896 | } |
1a4d82fc JJ |
897 | } |
898 | ||
d9579d0f AL |
899 | ast::PatQPath(_, _) => { |
900 | cx.tcx.sess.span_bug(pat_span, "const pattern should've \ | |
901 | been rewritten") | |
902 | } | |
903 | ||
1a4d82fc JJ |
904 | ast::PatStruct(_, ref pattern_fields, _) => { |
905 | // Is this a struct or an enum variant? | |
c34b1796 | 906 | let def = cx.tcx.def_map.borrow().get(&pat_id).unwrap().full_def(); |
1a4d82fc | 907 | let class_id = match def { |
d9579d0f | 908 | DefConst(..) | DefAssociatedConst(..) => |
1a4d82fc JJ |
909 | cx.tcx.sess.span_bug(pat_span, "const pattern should've \ |
910 | been rewritten"), | |
911 | DefVariant(_, variant_id, _) => if *constructor == Variant(variant_id) { | |
912 | Some(variant_id) | |
913 | } else { | |
914 | None | |
915 | }, | |
916 | _ => { | |
917 | // Assume this is a struct. | |
c1a9b12d | 918 | match cx.tcx.node_id_to_type(pat_id).ty_to_def_id() { |
1a4d82fc JJ |
919 | None => { |
920 | cx.tcx.sess.span_bug(pat_span, | |
921 | "struct pattern wasn't of a \ | |
922 | type with a def ID?!") | |
223e47cc | 923 | } |
1a4d82fc | 924 | Some(def_id) => Some(def_id), |
223e47cc | 925 | } |
223e47cc | 926 | } |
1a4d82fc JJ |
927 | }; |
928 | class_id.map(|variant_id| { | |
c1a9b12d | 929 | let struct_fields = cx.tcx.lookup_struct_fields(variant_id); |
1a4d82fc JJ |
930 | let args = struct_fields.iter().map(|sf| { |
931 | match pattern_fields.iter().find(|f| f.node.ident.name == sf.name) { | |
932 | Some(ref f) => &*f.node.pat, | |
933 | _ => DUMMY_WILD_PAT | |
223e47cc | 934 | } |
1a4d82fc JJ |
935 | }).collect(); |
936 | args | |
937 | }) | |
938 | } | |
939 | ||
940 | ast::PatTup(ref args) => | |
941 | Some(args.iter().map(|p| &**p).collect()), | |
942 | ||
943 | ast::PatBox(ref inner) | ast::PatRegion(ref inner, _) => | |
944 | Some(vec![&**inner]), | |
945 | ||
946 | ast::PatLit(ref expr) => { | |
947 | let expr_value = eval_const_expr(cx.tcx, &**expr); | |
948 | match range_covered_by_constructor(constructor, &expr_value, &expr_value) { | |
949 | Some(true) => Some(vec![]), | |
950 | Some(false) => None, | |
951 | None => { | |
85aaf69f | 952 | span_err!(cx.tcx.sess, pat_span, E0298, "mismatched types between arms"); |
1a4d82fc | 953 | None |
223e47cc LB |
954 | } |
955 | } | |
1a4d82fc JJ |
956 | } |
957 | ||
958 | ast::PatRange(ref from, ref to) => { | |
959 | let from_value = eval_const_expr(cx.tcx, &**from); | |
960 | let to_value = eval_const_expr(cx.tcx, &**to); | |
961 | match range_covered_by_constructor(constructor, &from_value, &to_value) { | |
962 | Some(true) => Some(vec![]), | |
963 | Some(false) => None, | |
964 | None => { | |
85aaf69f | 965 | span_err!(cx.tcx.sess, pat_span, E0299, "mismatched types between arms"); |
1a4d82fc | 966 | None |
970d7e83 LB |
967 | } |
968 | } | |
1a4d82fc JJ |
969 | } |
970 | ||
971 | ast::PatVec(ref before, ref slice, ref after) => { | |
972 | match *constructor { | |
973 | // Fixed-length vectors. | |
974 | Single => { | |
975 | let mut pats: Vec<&Pat> = before.iter().map(|p| &**p).collect(); | |
976 | pats.extend(repeat(DUMMY_WILD_PAT).take(arity - before.len() - after.len())); | |
977 | pats.extend(after.iter().map(|p| &**p)); | |
978 | Some(pats) | |
979 | }, | |
980 | Slice(length) if before.len() + after.len() <= length && slice.is_some() => { | |
981 | let mut pats: Vec<&Pat> = before.iter().map(|p| &**p).collect(); | |
982 | pats.extend(repeat(DUMMY_WILD_PAT).take(arity - before.len() - after.len())); | |
983 | pats.extend(after.iter().map(|p| &**p)); | |
984 | Some(pats) | |
985 | }, | |
986 | Slice(length) if before.len() + after.len() == length => { | |
987 | let mut pats: Vec<&Pat> = before.iter().map(|p| &**p).collect(); | |
988 | pats.extend(after.iter().map(|p| &**p)); | |
989 | Some(pats) | |
990 | }, | |
991 | SliceWithSubslice(prefix, suffix) | |
992 | if before.len() == prefix | |
993 | && after.len() == suffix | |
994 | && slice.is_some() => { | |
995 | let mut pats: Vec<&Pat> = before.iter().map(|p| &**p).collect(); | |
996 | pats.extend(after.iter().map(|p| &**p)); | |
997 | Some(pats) | |
223e47cc | 998 | } |
1a4d82fc | 999 | _ => None |
223e47cc LB |
1000 | } |
1001 | } | |
223e47cc | 1002 | |
1a4d82fc | 1003 | ast::PatMac(_) => { |
85aaf69f | 1004 | span_err!(cx.tcx.sess, pat_span, E0300, "unexpanded macro"); |
1a4d82fc JJ |
1005 | None |
1006 | } | |
1007 | }; | |
1008 | head.map(|mut head| { | |
85aaf69f SL |
1009 | head.push_all(&r[..col]); |
1010 | head.push_all(&r[col + 1..]); | |
1a4d82fc JJ |
1011 | head |
1012 | }) | |
223e47cc LB |
1013 | } |
1014 | ||
1a4d82fc JJ |
1015 | fn check_local(cx: &mut MatchCheckCtxt, loc: &ast::Local) { |
1016 | visit::walk_local(cx, loc); | |
223e47cc | 1017 | |
c1a9b12d SL |
1018 | let pat = StaticInliner::new(cx.tcx, None).fold_pat(loc.pat.clone()); |
1019 | check_irrefutable(cx, &pat, false); | |
1a4d82fc JJ |
1020 | |
1021 | // Check legality of move bindings and `@` patterns. | |
1022 | check_legality_of_move_bindings(cx, false, slice::ref_slice(&loc.pat)); | |
1023 | check_legality_of_bindings_in_at_patterns(cx, &*loc.pat); | |
223e47cc LB |
1024 | } |
1025 | ||
1a4d82fc JJ |
1026 | fn check_fn(cx: &mut MatchCheckCtxt, |
1027 | kind: FnKind, | |
1028 | decl: &ast::FnDecl, | |
1029 | body: &ast::Block, | |
1030 | sp: Span, | |
1031 | fn_id: NodeId) { | |
1032 | match kind { | |
1033 | visit::FkFnBlock => {} | |
1034 | _ => cx.param_env = ParameterEnvironment::for_item(cx.tcx, fn_id), | |
223e47cc LB |
1035 | } |
1036 | ||
1a4d82fc JJ |
1037 | visit::walk_fn(cx, kind, decl, body, sp); |
1038 | ||
85aaf69f | 1039 | for input in &decl.inputs { |
c1a9b12d | 1040 | check_irrefutable(cx, &input.pat, true); |
1a4d82fc JJ |
1041 | check_legality_of_move_bindings(cx, false, slice::ref_slice(&input.pat)); |
1042 | check_legality_of_bindings_in_at_patterns(cx, &*input.pat); | |
223e47cc LB |
1043 | } |
1044 | } | |
1045 | ||
c1a9b12d SL |
1046 | fn check_irrefutable(cx: &MatchCheckCtxt, pat: &Pat, is_fn_arg: bool) { |
1047 | let origin = if is_fn_arg { | |
1048 | "function argument" | |
1049 | } else { | |
1050 | "local binding" | |
1051 | }; | |
1052 | ||
1053 | is_refutable(cx, pat, |uncovered_pat| { | |
1054 | span_err!(cx.tcx.sess, pat.span, E0005, | |
1055 | "refutable pattern in {}: `{}` not covered", | |
1056 | origin, | |
1057 | pat_to_string(uncovered_pat), | |
1058 | ); | |
1059 | }); | |
1060 | } | |
1061 | ||
1a4d82fc JJ |
1062 | fn is_refutable<A, F>(cx: &MatchCheckCtxt, pat: &Pat, refutable: F) -> Option<A> where |
1063 | F: FnOnce(&Pat) -> A, | |
1064 | { | |
1065 | let pats = Matrix(vec!(vec!(pat))); | |
1066 | match is_useful(cx, &pats, &[DUMMY_WILD_PAT], ConstructWitness) { | |
1067 | UsefulWithWitness(pats) => { | |
1068 | assert_eq!(pats.len(), 1); | |
1069 | Some(refutable(&*pats[0])) | |
1070 | }, | |
1071 | NotUseful => None, | |
1072 | Useful => unreachable!() | |
1073 | } | |
1074 | } | |
223e47cc | 1075 | |
1a4d82fc JJ |
1076 | // Legality of move bindings checking |
1077 | fn check_legality_of_move_bindings(cx: &MatchCheckCtxt, | |
1078 | has_guard: bool, | |
1079 | pats: &[P<Pat>]) { | |
223e47cc | 1080 | let tcx = cx.tcx; |
1a4d82fc | 1081 | let def_map = &tcx.def_map; |
223e47cc | 1082 | let mut by_ref_span = None; |
85aaf69f | 1083 | for pat in pats { |
1a4d82fc | 1084 | pat_bindings(def_map, &**pat, |bm, _, span, _path| { |
223e47cc | 1085 | match bm { |
1a4d82fc | 1086 | ast::BindByRef(_) => { |
223e47cc LB |
1087 | by_ref_span = Some(span); |
1088 | } | |
1a4d82fc | 1089 | ast::BindByValue(_) => { |
223e47cc LB |
1090 | } |
1091 | } | |
1a4d82fc | 1092 | }) |
223e47cc LB |
1093 | } |
1094 | ||
85aaf69f | 1095 | let check_move = |p: &Pat, sub: Option<&Pat>| { |
223e47cc | 1096 | // check legality of moving out of the enum |
1a4d82fc JJ |
1097 | |
1098 | // x @ Foo(..) is legal, but x @ Foo(y) isn't. | |
1099 | if sub.map_or(false, |p| pat_contains_bindings(def_map, &*p)) { | |
1100 | span_err!(cx.tcx.sess, p.span, E0007, "cannot bind by-move with sub-bindings"); | |
223e47cc | 1101 | } else if has_guard { |
1a4d82fc | 1102 | span_err!(cx.tcx.sess, p.span, E0008, "cannot bind by-move into a pattern guard"); |
223e47cc | 1103 | } else if by_ref_span.is_some() { |
1a4d82fc JJ |
1104 | span_err!(cx.tcx.sess, p.span, E0009, |
1105 | "cannot bind by-move and by-ref in the same pattern"); | |
1106 | span_note!(cx.tcx.sess, by_ref_span.unwrap(), "by-ref binding occurs here"); | |
223e47cc LB |
1107 | } |
1108 | }; | |
1109 | ||
85aaf69f SL |
1110 | for pat in pats { |
1111 | ast_util::walk_pat(&**pat, |p| { | |
1a4d82fc | 1112 | if pat_is_binding(def_map, &*p) { |
223e47cc | 1113 | match p.node { |
1a4d82fc | 1114 | ast::PatIdent(ast::BindByValue(_), _, ref sub) => { |
c1a9b12d SL |
1115 | let pat_ty = tcx.node_id_to_type(p.id); |
1116 | //FIXME: (@jroesch) this code should be floated up as well | |
1117 | let infcx = infer::new_infer_ctxt(cx.tcx, | |
1118 | &cx.tcx.tables, | |
1119 | Some(cx.param_env.clone()), | |
1120 | false); | |
1121 | if infcx.type_moves_by_default(pat_ty, pat.span) { | |
1a4d82fc | 1122 | check_move(p, sub.as_ref().map(|p| &**p)); |
223e47cc LB |
1123 | } |
1124 | } | |
1a4d82fc JJ |
1125 | ast::PatIdent(ast::BindByRef(_), _, _) => { |
1126 | } | |
223e47cc LB |
1127 | _ => { |
1128 | cx.tcx.sess.span_bug( | |
1129 | p.span, | |
1a4d82fc JJ |
1130 | &format!("binding pattern {} is not an \ |
1131 | identifier: {:?}", | |
1132 | p.id, | |
c34b1796 | 1133 | p.node)); |
223e47cc LB |
1134 | } |
1135 | } | |
1136 | } | |
1a4d82fc JJ |
1137 | true |
1138 | }); | |
1139 | } | |
1140 | } | |
1141 | ||
1142 | /// Ensures that a pattern guard doesn't borrow by mutable reference or | |
1143 | /// assign. | |
1144 | fn check_for_mutation_in_guard<'a, 'tcx>(cx: &'a MatchCheckCtxt<'a, 'tcx>, | |
1145 | guard: &ast::Expr) { | |
1146 | let mut checker = MutationChecker { | |
1147 | cx: cx, | |
1148 | }; | |
c1a9b12d SL |
1149 | |
1150 | let infcx = infer::new_infer_ctxt(cx.tcx, | |
1151 | &cx.tcx.tables, | |
1152 | Some(checker.cx.param_env.clone()), | |
1153 | false); | |
1154 | ||
1155 | let mut visitor = ExprUseVisitor::new(&mut checker, &infcx); | |
1a4d82fc JJ |
1156 | visitor.walk_expr(guard); |
1157 | } | |
1158 | ||
1159 | struct MutationChecker<'a, 'tcx: 'a> { | |
1160 | cx: &'a MatchCheckCtxt<'a, 'tcx>, | |
1161 | } | |
1162 | ||
1163 | impl<'a, 'tcx> Delegate<'tcx> for MutationChecker<'a, 'tcx> { | |
1164 | fn matched_pat(&mut self, _: &Pat, _: cmt, _: euv::MatchMode) {} | |
1165 | fn consume(&mut self, _: NodeId, _: Span, _: cmt, _: ConsumeMode) {} | |
1166 | fn consume_pat(&mut self, _: &Pat, _: cmt, _: ConsumeMode) {} | |
1167 | fn borrow(&mut self, | |
1168 | _: NodeId, | |
1169 | span: Span, | |
1170 | _: cmt, | |
1171 | _: Region, | |
1172 | kind: BorrowKind, | |
1173 | _: LoanCause) { | |
1174 | match kind { | |
1175 | MutBorrow => { | |
85aaf69f SL |
1176 | span_err!(self.cx.tcx.sess, span, E0301, |
1177 | "cannot mutably borrow in a pattern guard") | |
1a4d82fc JJ |
1178 | } |
1179 | ImmBorrow | UniqueImmBorrow => {} | |
1180 | } | |
1181 | } | |
1182 | fn decl_without_init(&mut self, _: NodeId, _: Span) {} | |
1183 | fn mutate(&mut self, _: NodeId, span: Span, _: cmt, mode: MutateMode) { | |
1184 | match mode { | |
1185 | JustWrite | WriteAndRead => { | |
85aaf69f | 1186 | span_err!(self.cx.tcx.sess, span, E0302, "cannot assign in a pattern guard") |
1a4d82fc JJ |
1187 | } |
1188 | Init => {} | |
1189 | } | |
1190 | } | |
1191 | } | |
1192 | ||
1193 | /// Forbids bindings in `@` patterns. This is necessary for memory safety, | |
1194 | /// because of the way rvalues are handled in the borrow check. (See issue | |
1195 | /// #14587.) | |
1196 | fn check_legality_of_bindings_in_at_patterns(cx: &MatchCheckCtxt, pat: &Pat) { | |
1197 | AtBindingPatternVisitor { cx: cx, bindings_allowed: true }.visit_pat(pat); | |
1198 | } | |
1199 | ||
1200 | struct AtBindingPatternVisitor<'a, 'b:'a, 'tcx:'b> { | |
1201 | cx: &'a MatchCheckCtxt<'b, 'tcx>, | |
1202 | bindings_allowed: bool | |
1203 | } | |
1204 | ||
1205 | impl<'a, 'b, 'tcx, 'v> Visitor<'v> for AtBindingPatternVisitor<'a, 'b, 'tcx> { | |
1206 | fn visit_pat(&mut self, pat: &Pat) { | |
1207 | if !self.bindings_allowed && pat_is_binding(&self.cx.tcx.def_map, pat) { | |
85aaf69f | 1208 | span_err!(self.cx.tcx.sess, pat.span, E0303, |
1a4d82fc JJ |
1209 | "pattern bindings are not allowed \ |
1210 | after an `@`"); | |
1211 | } | |
1212 | ||
1213 | match pat.node { | |
1214 | ast::PatIdent(_, _, Some(_)) => { | |
1215 | let bindings_were_allowed = self.bindings_allowed; | |
1216 | self.bindings_allowed = false; | |
1217 | visit::walk_pat(self, pat); | |
1218 | self.bindings_allowed = bindings_were_allowed; | |
1219 | } | |
1220 | _ => visit::walk_pat(self, pat), | |
223e47cc | 1221 | } |
223e47cc LB |
1222 | } |
1223 | } |