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