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