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