]> git.lizzy.rs Git - rust.git/blob - src/librustc_const_eval/check_match.rs
move projection mode into parameter environment
[rust.git] / src / librustc_const_eval / check_match.rs
1 // Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT
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
11 use _match::{MatchCheckCtxt, Matrix, expand_pattern, is_useful};
12 use _match::Usefulness::*;
13 use _match::WitnessPreference::*;
14
15 use pattern::{Pattern, PatternContext, PatternError, PatternKind};
16
17 use rustc::middle::expr_use_visitor::{ConsumeMode, Delegate, ExprUseVisitor};
18 use rustc::middle::expr_use_visitor::{LoanCause, MutateMode};
19 use rustc::middle::expr_use_visitor as euv;
20 use rustc::middle::mem_categorization::{cmt};
21 use rustc::middle::region::RegionMaps;
22 use rustc::session::Session;
23 use rustc::ty::{self, Ty, TyCtxt};
24 use rustc::lint;
25 use rustc_errors::{Diagnostic, Level, DiagnosticBuilder};
26
27 use rustc::hir::def::*;
28 use rustc::hir::intravisit::{self, Visitor, FnKind, NestedVisitorMap};
29 use rustc::hir::{self, Pat, PatKind};
30
31 use rustc_back::slice;
32
33 use syntax::ast;
34 use syntax::ptr::P;
35 use syntax_pos::{Span, DUMMY_SP};
36
37 struct OuterVisitor<'a, 'tcx: 'a> { tcx: TyCtxt<'a, 'tcx, 'tcx> }
38
39 impl<'a, 'tcx> Visitor<'tcx> for OuterVisitor<'a, 'tcx> {
40     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
41         NestedVisitorMap::OnlyBodies(&self.tcx.hir)
42     }
43
44     fn visit_fn(&mut self, fk: FnKind<'tcx>, fd: &'tcx hir::FnDecl,
45                 b: hir::BodyId, s: Span, id: ast::NodeId) {
46         intravisit::walk_fn(self, fk, fd, b, s, id);
47
48         let def_id = self.tcx.hir.local_def_id(id);
49
50         MatchVisitor {
51             tcx: self.tcx,
52             tables: self.tcx.body_tables(b),
53             region_maps: &self.tcx.region_maps(def_id),
54             param_env: self.tcx.param_env(def_id)
55         }.visit_body(self.tcx.hir.body(b));
56     }
57 }
58
59 pub fn check_crate<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) {
60     tcx.hir.krate().visit_all_item_likes(&mut OuterVisitor { tcx: tcx }.as_deep_visitor());
61     tcx.sess.abort_if_errors();
62 }
63
64 fn create_e0004<'a>(sess: &'a Session, sp: Span, error_message: String) -> DiagnosticBuilder<'a> {
65     struct_span_err!(sess, sp, E0004, "{}", &error_message)
66 }
67
68 struct MatchVisitor<'a, 'tcx: 'a> {
69     tcx: TyCtxt<'a, 'tcx, 'tcx>,
70     tables: &'a ty::TypeckTables<'tcx>,
71     param_env: ty::ParamEnv<'tcx>,
72     region_maps: &'a RegionMaps,
73 }
74
75 impl<'a, 'tcx> Visitor<'tcx> for MatchVisitor<'a, 'tcx> {
76     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
77         NestedVisitorMap::None
78     }
79
80     fn visit_expr(&mut self, ex: &'tcx hir::Expr) {
81         intravisit::walk_expr(self, ex);
82
83         match ex.node {
84             hir::ExprMatch(ref scrut, ref arms, source) => {
85                 self.check_match(scrut, arms, source);
86             }
87             _ => {}
88         }
89     }
90
91     fn visit_local(&mut self, loc: &'tcx hir::Local) {
92         intravisit::walk_local(self, loc);
93
94         self.check_irrefutable(&loc.pat, false);
95
96         // Check legality of move bindings and `@` patterns.
97         self.check_patterns(false, slice::ref_slice(&loc.pat));
98     }
99
100     fn visit_body(&mut self, body: &'tcx hir::Body) {
101         intravisit::walk_body(self, body);
102
103         for arg in &body.arguments {
104             self.check_irrefutable(&arg.pat, true);
105             self.check_patterns(false, slice::ref_slice(&arg.pat));
106         }
107     }
108 }
109
110 impl<'a, 'gcx, 'tcx> PatternContext<'a, 'gcx, 'tcx> {
111     fn report_inlining_errors(&self, pat_span: Span) {
112         for error in &self.errors {
113             match *error {
114                 PatternError::StaticInPattern(span) => {
115                     span_err!(self.tcx.sess, span, E0158,
116                               "statics cannot be referenced in patterns");
117                 }
118                 PatternError::ConstEval(ref err) => {
119                     err.report(self.tcx, pat_span, "pattern");
120                 }
121             }
122         }
123     }
124 }
125
126 impl<'a, 'tcx> MatchVisitor<'a, 'tcx> {
127     fn check_patterns(&self, has_guard: bool, pats: &[P<Pat>]) {
128         check_legality_of_move_bindings(self, has_guard, pats);
129         for pat in pats {
130             check_legality_of_bindings_in_at_patterns(self, pat);
131         }
132     }
133
134     fn check_match(
135         &self,
136         scrut: &hir::Expr,
137         arms: &[hir::Arm],
138         source: hir::MatchSource)
139     {
140         for arm in arms {
141             // First, check legality of move bindings.
142             self.check_patterns(arm.guard.is_some(), &arm.pats);
143
144             // Second, if there is a guard on each arm, make sure it isn't
145             // assigning or borrowing anything mutably.
146             if let Some(ref guard) = arm.guard {
147                 check_for_mutation_in_guard(self, &guard);
148             }
149
150             // Third, perform some lints.
151             for pat in &arm.pats {
152                 check_for_bindings_named_the_same_as_variants(self, pat);
153             }
154         }
155
156         let module = self.tcx.hir.get_module_parent(scrut.id);
157         MatchCheckCtxt::create_and_enter(self.tcx, module, |ref mut cx| {
158             let mut have_errors = false;
159
160             let inlined_arms : Vec<(Vec<_>, _)> = arms.iter().map(|arm| (
161                 arm.pats.iter().map(|pat| {
162                     let mut patcx = PatternContext::new(self.tcx, self.tables);
163                     let pattern = expand_pattern(cx, patcx.lower_pattern(&pat));
164                     if !patcx.errors.is_empty() {
165                         patcx.report_inlining_errors(pat.span);
166                         have_errors = true;
167                     }
168                     (pattern, &**pat)
169                 }).collect(),
170                 arm.guard.as_ref().map(|e| &**e)
171             )).collect();
172
173             // Bail out early if inlining failed.
174             if have_errors {
175                 return;
176             }
177
178             // Fourth, check for unreachable arms.
179             check_arms(cx, &inlined_arms, source);
180
181             // Then, if the match has no arms, check whether the scrutinee
182             // is uninhabited.
183             let pat_ty = self.tables.node_id_to_type(scrut.id);
184             let module = self.tcx.hir.get_module_parent(scrut.id);
185             if inlined_arms.is_empty() {
186                 let scrutinee_is_uninhabited = if self.tcx.sess.features.borrow().never_type {
187                     pat_ty.is_uninhabited_from(module, self.tcx)
188                 } else {
189                     self.conservative_is_uninhabited(pat_ty)
190                 };
191                 if !scrutinee_is_uninhabited {
192                     // We know the type is inhabited, so this must be wrong
193                     let mut err = create_e0004(self.tcx.sess, scrut.span,
194                                                format!("non-exhaustive patterns: type {} \
195                                                         is non-empty",
196                                                        pat_ty));
197                     span_help!(&mut err, scrut.span,
198                                "Please ensure that all possible cases are being handled; \
199                                 possibly adding wildcards or more match arms.");
200                     err.emit();
201                 }
202                 // If the type *is* uninhabited, it's vacuously exhaustive
203                 return;
204             }
205
206             let matrix: Matrix = inlined_arms
207                 .iter()
208                 .filter(|&&(_, guard)| guard.is_none())
209                 .flat_map(|arm| &arm.0)
210                 .map(|pat| vec![pat.0])
211                 .collect();
212             let scrut_ty = self.tables.node_id_to_type(scrut.id);
213             check_exhaustive(cx, scrut_ty, scrut.span, &matrix, source);
214         })
215     }
216
217     fn conservative_is_uninhabited(&self, scrutinee_ty: Ty<'tcx>) -> bool {
218         // "rustc-1.0-style" uncontentious uninhabitableness check
219         match scrutinee_ty.sty {
220             ty::TyNever => true,
221             ty::TyAdt(def, _) => def.variants.is_empty(),
222             _ => false
223         }
224     }
225
226     fn check_irrefutable(&self, pat: &Pat, is_fn_arg: bool) {
227         let origin = if is_fn_arg {
228             "function argument"
229         } else {
230             "local binding"
231         };
232
233         let module = self.tcx.hir.get_module_parent(pat.id);
234         MatchCheckCtxt::create_and_enter(self.tcx, module, |ref mut cx| {
235             let mut patcx = PatternContext::new(self.tcx, self.tables);
236             let pattern = patcx.lower_pattern(pat);
237             let pattern_ty = pattern.ty;
238             let pats : Matrix = vec![vec![
239                 expand_pattern(cx, pattern)
240             ]].into_iter().collect();
241
242             let wild_pattern = Pattern {
243                 ty: pattern_ty,
244                 span: DUMMY_SP,
245                 kind: box PatternKind::Wild,
246             };
247             let witness = match is_useful(cx, &pats, &[&wild_pattern], ConstructWitness) {
248                 UsefulWithWitness(witness) => witness,
249                 NotUseful => return,
250                 Useful => bug!()
251             };
252
253             let pattern_string = witness[0].single_pattern().to_string();
254             let mut diag = struct_span_err!(
255                 self.tcx.sess, pat.span, E0005,
256                 "refutable pattern in {}: `{}` not covered",
257                 origin, pattern_string
258             );
259             diag.span_label(pat.span, format!("pattern `{}` not covered", pattern_string));
260             diag.emit();
261         });
262     }
263 }
264
265 fn check_for_bindings_named_the_same_as_variants(cx: &MatchVisitor, pat: &Pat) {
266     pat.walk(|p| {
267         if let PatKind::Binding(hir::BindByValue(hir::MutImmutable), _, name, None) = p.node {
268             let pat_ty = cx.tables.pat_ty(p);
269             if let ty::TyAdt(edef, _) = pat_ty.sty {
270                 if edef.is_enum() && edef.variants.iter().any(|variant| {
271                     variant.name == name.node && variant.ctor_kind == CtorKind::Const
272                 }) {
273                     let ty_path = cx.tcx.item_path_str(edef.did);
274                     let mut err = struct_span_warn!(cx.tcx.sess, p.span, E0170,
275                         "pattern binding `{}` is named the same as one \
276                          of the variants of the type `{}`",
277                         name.node, ty_path);
278                     help!(err,
279                         "if you meant to match on a variant, \
280                         consider making the path in the pattern qualified: `{}::{}`",
281                         ty_path, name.node);
282                     err.emit();
283                 }
284             }
285         }
286         true
287     });
288 }
289
290 /// Checks for common cases of "catchall" patterns that may not be intended as such.
291 fn pat_is_catchall(pat: &Pat) -> bool {
292     match pat.node {
293         PatKind::Binding(.., None) => true,
294         PatKind::Binding(.., Some(ref s)) => pat_is_catchall(s),
295         PatKind::Ref(ref s, _) => pat_is_catchall(s),
296         PatKind::Tuple(ref v, _) => v.iter().all(|p| {
297             pat_is_catchall(&p)
298         }),
299         _ => false
300     }
301 }
302
303 // Check for unreachable patterns
304 fn check_arms<'a, 'tcx>(cx: &mut MatchCheckCtxt<'a, 'tcx>,
305                         arms: &[(Vec<(&'a Pattern<'tcx>, &hir::Pat)>, Option<&hir::Expr>)],
306                         source: hir::MatchSource)
307 {
308     let mut seen = Matrix::empty();
309     let mut catchall = None;
310     let mut printed_if_let_err = false;
311     for (arm_index, &(ref pats, guard)) in arms.iter().enumerate() {
312         for &(pat, hir_pat) in pats {
313             let v = vec![pat];
314
315             match is_useful(cx, &seen, &v, LeaveOutWitness) {
316                 NotUseful => {
317                     match source {
318                         hir::MatchSource::IfLetDesugar { .. } => {
319                             if printed_if_let_err {
320                                 // we already printed an irrefutable if-let pattern error.
321                                 // We don't want two, that's just confusing.
322                             } else {
323                                 // find the first arm pattern so we can use its span
324                                 let &(ref first_arm_pats, _) = &arms[0];
325                                 let first_pat = &first_arm_pats[0];
326                                 let span = first_pat.0.span;
327                                 struct_span_err!(cx.tcx.sess, span, E0162,
328                                                 "irrefutable if-let pattern")
329                                     .span_label(span, "irrefutable pattern")
330                                     .emit();
331                                 printed_if_let_err = true;
332                             }
333                         },
334
335                         hir::MatchSource::WhileLetDesugar => {
336                             // find the first arm pattern so we can use its span
337                             let &(ref first_arm_pats, _) = &arms[0];
338                             let first_pat = &first_arm_pats[0];
339                             let span = first_pat.0.span;
340
341                             // check which arm we're on.
342                             match arm_index {
343                                 // The arm with the user-specified pattern.
344                                 0 => {
345                                     let mut diagnostic = Diagnostic::new(Level::Warning,
346                                                                          "unreachable pattern");
347                                     diagnostic.set_span(pat.span);
348                                     cx.tcx.sess.add_lint_diagnostic(
349                                             lint::builtin::UNREACHABLE_PATTERNS,
350                                             hir_pat.id, diagnostic);
351                                 },
352                                 // The arm with the wildcard pattern.
353                                 1 => {
354                                     struct_span_err!(cx.tcx.sess, span, E0165,
355                                                      "irrefutable while-let pattern")
356                                         .span_label(span, "irrefutable pattern")
357                                         .emit();
358                                 },
359                                 _ => bug!(),
360                             }
361                         },
362
363                         hir::MatchSource::ForLoopDesugar |
364                         hir::MatchSource::Normal => {
365                             let mut diagnostic = Diagnostic::new(Level::Warning,
366                                                                  "unreachable pattern");
367                             diagnostic.set_span(pat.span);
368                             // if we had a catchall pattern, hint at that
369                             if let Some(catchall) = catchall {
370                                 diagnostic.span_label(pat.span, "this is an unreachable pattern");
371                                 diagnostic.span_note(catchall, "this pattern matches any value");
372                             }
373                             cx.tcx.sess.add_lint_diagnostic(lint::builtin::UNREACHABLE_PATTERNS,
374                                                             hir_pat.id, diagnostic);
375                         },
376
377                         // Unreachable patterns in try expressions occur when one of the arms
378                         // are an uninhabited type. Which is OK.
379                         hir::MatchSource::TryDesugar => {}
380                     }
381                 }
382                 Useful => (),
383                 UsefulWithWitness(_) => bug!()
384             }
385             if guard.is_none() {
386                 seen.push(v);
387                 if catchall.is_none() && pat_is_catchall(hir_pat) {
388                     catchall = Some(pat.span);
389                 }
390             }
391         }
392     }
393 }
394
395 fn check_exhaustive<'a, 'tcx>(cx: &mut MatchCheckCtxt<'a, 'tcx>,
396                               scrut_ty: Ty<'tcx>,
397                               sp: Span,
398                               matrix: &Matrix<'a, 'tcx>,
399                               source: hir::MatchSource) {
400     let wild_pattern = Pattern {
401         ty: scrut_ty,
402         span: DUMMY_SP,
403         kind: box PatternKind::Wild,
404     };
405     match is_useful(cx, matrix, &[&wild_pattern], ConstructWitness) {
406         UsefulWithWitness(pats) => {
407             let witnesses = if pats.is_empty() {
408                 vec![&wild_pattern]
409             } else {
410                 pats.iter().map(|w| w.single_pattern()).collect()
411             };
412             match source {
413                 hir::MatchSource::ForLoopDesugar => {
414                     // `witnesses[0]` has the form `Some(<head>)`, peel off the `Some`
415                     let witness = match *witnesses[0].kind {
416                         PatternKind::Variant { ref subpatterns, .. } => match &subpatterns[..] {
417                             &[ref pat] => &pat.pattern,
418                             _ => bug!(),
419                         },
420                         _ => bug!(),
421                     };
422                     let pattern_string = witness.to_string();
423                     struct_span_err!(cx.tcx.sess, sp, E0297,
424                         "refutable pattern in `for` loop binding: \
425                                 `{}` not covered",
426                                 pattern_string)
427                         .span_label(sp, format!("pattern `{}` not covered", pattern_string))
428                         .emit();
429                 },
430                 _ => {
431                     const LIMIT: usize = 3;
432                     let joined_patterns = match witnesses.len() {
433                         0 => bug!(),
434                         1 => format!("`{}`", witnesses[0]),
435                         2...LIMIT => {
436                             let (tail, head) = witnesses.split_last().unwrap();
437                             let head: Vec<_> = head.iter().map(|w| w.to_string()).collect();
438                             format!("`{}` and `{}`", head.join("`, `"), tail)
439                         },
440                         _ => {
441                             let (head, tail) = witnesses.split_at(LIMIT);
442                             let head: Vec<_> = head.iter().map(|w| w.to_string()).collect();
443                             format!("`{}` and {} more", head.join("`, `"), tail.len())
444                         }
445                     };
446
447                     let label_text = match witnesses.len() {
448                         1 => format!("pattern {} not covered", joined_patterns),
449                         _ => format!("patterns {} not covered", joined_patterns)
450                     };
451                     create_e0004(cx.tcx.sess, sp,
452                                  format!("non-exhaustive patterns: {} not covered",
453                                          joined_patterns))
454                         .span_label(sp, label_text)
455                         .emit();
456                 },
457             }
458         }
459         NotUseful => {
460             // This is good, wildcard pattern isn't reachable
461         },
462         _ => bug!()
463     }
464 }
465
466 // Legality of move bindings checking
467 fn check_legality_of_move_bindings(cx: &MatchVisitor,
468                                    has_guard: bool,
469                                    pats: &[P<Pat>]) {
470     let mut by_ref_span = None;
471     for pat in pats {
472         pat.each_binding(|bm, _, span, _path| {
473             if let hir::BindByRef(..) = bm {
474                 by_ref_span = Some(span);
475             }
476         })
477     }
478
479     let check_move = |p: &Pat, sub: Option<&Pat>| {
480         // check legality of moving out of the enum
481
482         // x @ Foo(..) is legal, but x @ Foo(y) isn't.
483         if sub.map_or(false, |p| p.contains_bindings()) {
484             struct_span_err!(cx.tcx.sess, p.span, E0007,
485                              "cannot bind by-move with sub-bindings")
486                 .span_label(p.span, "binds an already bound by-move value by moving it")
487                 .emit();
488         } else if has_guard {
489             struct_span_err!(cx.tcx.sess, p.span, E0008,
490                       "cannot bind by-move into a pattern guard")
491                 .span_label(p.span, "moves value into pattern guard")
492                 .emit();
493         } else if by_ref_span.is_some() {
494             struct_span_err!(cx.tcx.sess, p.span, E0009,
495                             "cannot bind by-move and by-ref in the same pattern")
496                     .span_label(p.span, "by-move pattern here")
497                     .span_label(by_ref_span.unwrap(), "both by-ref and by-move used")
498                     .emit();
499         }
500     };
501
502     for pat in pats {
503         pat.walk(|p| {
504             if let PatKind::Binding(hir::BindByValue(..), _, _, ref sub) = p.node {
505                 let pat_ty = cx.tables.node_id_to_type(p.id);
506                 if pat_ty.moves_by_default(cx.tcx, cx.param_env, pat.span) {
507                     check_move(p, sub.as_ref().map(|p| &**p));
508                 }
509             }
510             true
511         });
512     }
513 }
514
515 /// Ensures that a pattern guard doesn't borrow by mutable reference or
516 /// assign.
517 ///
518 /// FIXME: this should be done by borrowck.
519 fn check_for_mutation_in_guard(cx: &MatchVisitor, guard: &hir::Expr) {
520     cx.tcx.infer_ctxt((cx.tables, cx.param_env)).enter(|infcx| {
521         let mut checker = MutationChecker {
522             cx: cx,
523         };
524         ExprUseVisitor::new(&mut checker, cx.region_maps, &infcx).walk_expr(guard);
525     });
526 }
527
528 struct MutationChecker<'a, 'gcx: 'a> {
529     cx: &'a MatchVisitor<'a, 'gcx>,
530 }
531
532 impl<'a, 'gcx, 'tcx> Delegate<'tcx> for MutationChecker<'a, 'gcx> {
533     fn matched_pat(&mut self, _: &Pat, _: cmt, _: euv::MatchMode) {}
534     fn consume(&mut self, _: ast::NodeId, _: Span, _: cmt, _: ConsumeMode) {}
535     fn consume_pat(&mut self, _: &Pat, _: cmt, _: ConsumeMode) {}
536     fn borrow(&mut self,
537               _: ast::NodeId,
538               span: Span,
539               _: cmt,
540               _: ty::Region<'tcx>,
541               kind:ty:: BorrowKind,
542               _: LoanCause) {
543         match kind {
544             ty::MutBorrow => {
545                 struct_span_err!(self.cx.tcx.sess, span, E0301,
546                           "cannot mutably borrow in a pattern guard")
547                     .span_label(span, "borrowed mutably in pattern guard")
548                     .emit();
549             }
550             ty::ImmBorrow | ty::UniqueImmBorrow => {}
551         }
552     }
553     fn decl_without_init(&mut self, _: ast::NodeId, _: Span) {}
554     fn mutate(&mut self, _: ast::NodeId, span: Span, _: cmt, mode: MutateMode) {
555         match mode {
556             MutateMode::JustWrite | MutateMode::WriteAndRead => {
557                 struct_span_err!(self.cx.tcx.sess, span, E0302, "cannot assign in a pattern guard")
558                     .span_label(span, "assignment in pattern guard")
559                     .emit();
560             }
561             MutateMode::Init => {}
562         }
563     }
564 }
565
566 /// Forbids bindings in `@` patterns. This is necessary for memory safety,
567 /// because of the way rvalues are handled in the borrow check. (See issue
568 /// #14587.)
569 fn check_legality_of_bindings_in_at_patterns(cx: &MatchVisitor, pat: &Pat) {
570     AtBindingPatternVisitor { cx: cx, bindings_allowed: true }.visit_pat(pat);
571 }
572
573 struct AtBindingPatternVisitor<'a, 'b:'a, 'tcx:'b> {
574     cx: &'a MatchVisitor<'b, 'tcx>,
575     bindings_allowed: bool
576 }
577
578 impl<'a, 'b, 'tcx, 'v> Visitor<'v> for AtBindingPatternVisitor<'a, 'b, 'tcx> {
579     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
580         NestedVisitorMap::None
581     }
582
583     fn visit_pat(&mut self, pat: &Pat) {
584         match pat.node {
585             PatKind::Binding(.., ref subpat) => {
586                 if !self.bindings_allowed {
587                     struct_span_err!(self.cx.tcx.sess, pat.span, E0303,
588                                      "pattern bindings are not allowed after an `@`")
589                         .span_label(pat.span,  "not allowed after `@`")
590                         .emit();
591                 }
592
593                 if subpat.is_some() {
594                     let bindings_were_allowed = self.bindings_allowed;
595                     self.bindings_allowed = false;
596                     intravisit::walk_pat(self, pat);
597                     self.bindings_allowed = bindings_were_allowed;
598                 }
599             }
600             _ => intravisit::walk_pat(self, pat),
601         }
602     }
603 }