src/librustc_typeck/check/_match.rs

   1 use crate::check::{FnCtxt, Expectation, Diverges, Needs};
   2 use crate::check::coercion::CoerceMany;
   3 use crate::util::nodemap::FxHashMap;
   4 use errors::Applicability;
   5 use rustc::hir::{self, PatKind};
   6 use rustc::hir::def::{Def, CtorKind};
   7 use rustc::hir::pat_util::EnumerateAndAdjustIterator;
   8 use rustc::infer;
   9 use rustc::infer::type_variable::TypeVariableOrigin;
  10 use rustc::traits::ObligationCauseCode;
  11 use rustc::ty::{self, Ty, TypeFoldable};
  12 use syntax::ast;
  13 use syntax::source_map::Spanned;
  14 use syntax::ptr::P;
  15 use syntax::util::lev_distance::find_best_match_for_name;
  16 use syntax_pos::Span;
  17
  18 use std::collections::hash_map::Entry::{Occupied, Vacant};
  19 use std::cmp;
  20
  21 use super::report_unexpected_variant_def;
  22
  23 impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
  24     /// `match_discrim_span` argument having a `Span` indicates that this pattern is part of
  25     /// a match expression arm guard, and it points to the match discriminant to add context
  26     /// in type errors. In the folloowing example, `match_discrim_span` corresponds to the
  27     /// `a + b` expression:
  28     ///
  29     /// ```text
  30     /// error[E0308]: mismatched types
  31     ///  --> src/main.rs:5:9
  32     ///   |
  33     /// 4 |    let temp: usize = match a + b {
  34     ///   |                            ----- this expression has type `usize`
  35     /// 5 |         Ok(num) => num,
  36     ///   |         ^^^^^^^ expected usize, found enum `std::result::Result`
  37     ///   |
  38     ///   = note: expected type `usize`
  39     ///              found type `std::result::Result<_, _>`
  40     /// ```
  41     pub fn check_pat_walk(
  42         &self,
  43         pat: &'gcx hir::Pat,
  44         mut expected: Ty<'tcx>,
  45         mut def_bm: ty::BindingMode,
  46         match_discrim_span: Option<Span>,
  47     ) {
  48         let tcx = self.tcx;
  49
  50         debug!("check_pat_walk(pat={:?},expected={:?},def_bm={:?})", pat, expected, def_bm);
  51
  52         let is_non_ref_pat = match pat.node {
  53             PatKind::Struct(..) |
  54             PatKind::TupleStruct(..) |
  55             PatKind::Tuple(..) |
  56             PatKind::Box(_) |
  57             PatKind::Range(..) |
  58             PatKind::Slice(..) => true,
  59             PatKind::Lit(ref lt) => {
  60                 let ty = self.check_expr(lt);
  61                 match ty.sty {
  62                     ty::Ref(..) => false,
  63                     _ => true,
  64                 }
  65             }
  66             PatKind::Path(ref qpath) => {
  67                 let (def, _, _) = self.resolve_ty_and_def_ufcs(qpath, pat.hir_id, pat.span);
  68                 match def {
  69                     Def::Const(..) | Def::AssociatedConst(..) => false,
  70                     _ => true,
  71                 }
  72             }
  73             PatKind::Wild |
  74             PatKind::Binding(..) |
  75             PatKind::Ref(..) => false,
  76         };
  77         if is_non_ref_pat {
  78             debug!("pattern is non reference pattern");
  79             let mut exp_ty = self.resolve_type_vars_with_obligations(&expected);
  80
  81             // Peel off as many `&` or `&mut` from the discriminant as possible. For example,
  82             // for `match &&&mut Some(5)` the loop runs three times, aborting when it reaches
  83             // the `Some(5)` which is not of type Ref.
  84             //
  85             // For each ampersand peeled off, update the binding mode and push the original
  86             // type into the adjustments vector.
  87             //
  88             // See the examples in `run-pass/match-defbm*.rs`.
  89             let mut pat_adjustments = vec![];
  90             while let ty::Ref(_, inner_ty, inner_mutability) = exp_ty.sty {
  91                 debug!("inspecting {:?}", exp_ty);
  92
  93                 debug!("current discriminant is Ref, inserting implicit deref");
  94                 // Preserve the reference type. We'll need it later during HAIR lowering.
  95                 pat_adjustments.push(exp_ty);
  96
  97                 exp_ty = inner_ty;
  98                 def_bm = match def_bm {
  99                     // If default binding mode is by value, make it `ref` or `ref mut`
 100                     // (depending on whether we observe `&` or `&mut`).
 101                     ty::BindByValue(_) =>
 102                         ty::BindByReference(inner_mutability),
 103
 104                     // Once a `ref`, always a `ref`. This is because a `& &mut` can't mutate
 105                     // the underlying value.
 106                     ty::BindByReference(hir::Mutability::MutImmutable) =>
 107                         ty::BindByReference(hir::Mutability::MutImmutable),
 108
 109                     // When `ref mut`, stay a `ref mut` (on `&mut`) or downgrade to `ref`
 110                     // (on `&`).
 111                     ty::BindByReference(hir::Mutability::MutMutable) =>
 112                         ty::BindByReference(inner_mutability),
 113                 };
 114             }
 115             expected = exp_ty;
 116
 117             if pat_adjustments.len() > 0 {
 118                 debug!("default binding mode is now {:?}", def_bm);
 119                 self.inh.tables.borrow_mut()
 120                     .pat_adjustments_mut()
 121                     .insert(pat.hir_id, pat_adjustments);
 122             }
 123         } else if let PatKind::Ref(..) = pat.node {
 124             // When you encounter a `&pat` pattern, reset to "by
 125             // value". This is so that `x` and `y` here are by value,
 126             // as they appear to be:
 127             //
 128             // ```
 129             // match &(&22, &44) {
 130             //   (&x, &y) => ...
 131             // }
 132             // ```
 133             //
 134             // cc #46688
 135             def_bm = ty::BindByValue(hir::MutImmutable);
 136         }
 137
 138         // Lose mutability now that we know binding mode and discriminant type.
 139         let def_bm = def_bm;
 140         let expected = expected;
 141
 142         let ty = match pat.node {
 143             PatKind::Wild => {
 144                 expected
 145             }
 146             PatKind::Lit(ref lt) => {
 147                 // We've already computed the type above (when checking for a non-ref pat), so
 148                 // avoid computing it again.
 149                 let ty = self.node_ty(lt.hir_id);
 150
 151                 // Byte string patterns behave the same way as array patterns
 152                 // They can denote both statically and dynamically sized byte arrays
 153                 let mut pat_ty = ty;
 154                 if let hir::ExprKind::Lit(ref lt) = lt.node {
 155                     if let ast::LitKind::ByteStr(_) = lt.node {
 156                         let expected_ty = self.structurally_resolved_type(pat.span, expected);
 157                         if let ty::Ref(_, r_ty, _) = expected_ty.sty {
 158                             if let ty::Slice(_) = r_ty.sty {
 159                                 pat_ty = tcx.mk_imm_ref(tcx.types.re_static,
 160                                                         tcx.mk_slice(tcx.types.u8))
 161                             }
 162                         }
 163                     }
 164                 }
 165
 166                 // somewhat surprising: in this case, the subtyping
 167                 // relation goes the opposite way as the other
 168                 // cases. Actually what we really want is not a subtyping
 169                 // relation at all but rather that there exists a LUB (so
 170                 // that they can be compared). However, in practice,
 171                 // constants are always scalars or strings.  For scalars
 172                 // subtyping is irrelevant, and for strings `ty` is
 173                 // type is `&'static str`, so if we say that
 174                 //
 175                 //     &'static str <: expected
 176                 //
 177                 // that's equivalent to there existing a LUB.
 178                 self.demand_suptype(pat.span, expected, pat_ty);
 179                 pat_ty
 180             }
 181             PatKind::Range(ref begin, ref end, _) => {
 182                 let lhs_ty = self.check_expr(begin);
 183                 let rhs_ty = self.check_expr(end);
 184
 185                 // Check that both end-points are of numeric or char type.
 186                 let numeric_or_char = |ty: Ty<'_>| ty.is_numeric() || ty.is_char();
 187                 let lhs_compat = numeric_or_char(lhs_ty);
 188                 let rhs_compat = numeric_or_char(rhs_ty);
 189
 190                 if !lhs_compat || !rhs_compat {
 191                     let span = if !lhs_compat && !rhs_compat {
 192                         pat.span
 193                     } else if !lhs_compat {
 194                         begin.span
 195                     } else {
 196                         end.span
 197                     };
 198
 199                     let mut err = struct_span_err!(
 200                         tcx.sess,
 201                         span,
 202                         E0029,
 203                         "only char and numeric types are allowed in range patterns"
 204                     );
 205                     err.span_label(span, "ranges require char or numeric types");
 206                     err.note(&format!("start type: {}", self.ty_to_string(lhs_ty)));
 207                     err.note(&format!("end type: {}", self.ty_to_string(rhs_ty)));
 208                     if tcx.sess.teach(&err.get_code().unwrap()) {
 209                         err.note(
 210                             "In a match expression, only numbers and characters can be matched \
 211                              against a range. This is because the compiler checks that the range \
 212                              is non-empty at compile-time, and is unable to evaluate arbitrary \
 213                              comparison functions. If you want to capture values of an orderable \
 214                              type between two end-points, you can use a guard."
 215                          );
 216                     }
 217                     err.emit();
 218                     return;
 219                 }
 220
 221                 // Now that we know the types can be unified we find the unified type and use
 222                 // it to type the entire expression.
 223                 let common_type = self.resolve_type_vars_if_possible(&lhs_ty);
 224
 225                 // subtyping doesn't matter here, as the value is some kind of scalar
 226                 self.demand_eqtype_pat(pat.span, expected, lhs_ty, match_discrim_span);
 227                 self.demand_eqtype_pat(pat.span, expected, rhs_ty, match_discrim_span);
 228                 common_type
 229             }
 230             PatKind::Binding(ba, var_id, _, ref sub) => {
 231                 let bm = if ba == hir::BindingAnnotation::Unannotated {
 232                     def_bm
 233                 } else {
 234                     ty::BindingMode::convert(ba)
 235                 };
 236                 self.inh
 237                     .tables
 238                     .borrow_mut()
 239                     .pat_binding_modes_mut()
 240                     .insert(pat.hir_id, bm);
 241                 debug!("check_pat_walk: pat.hir_id={:?} bm={:?}", pat.hir_id, bm);
 242                 let local_ty = self.local_ty(pat.span, pat.hir_id).decl_ty;
 243                 match bm {
 244                     ty::BindByReference(mutbl) => {
 245                         // if the binding is like
 246                         //    ref x | ref const x | ref mut x
 247                         // then `x` is assigned a value of type `&M T` where M is the mutability
 248                         // and T is the expected type.
 249                         let region_var = self.next_region_var(infer::PatternRegion(pat.span));
 250                         let mt = ty::TypeAndMut { ty: expected, mutbl: mutbl };
 251                         let region_ty = tcx.mk_ref(region_var, mt);
 252
 253                         // `x` is assigned a value of type `&M T`, hence `&M T <: typeof(x)` is
 254                         // required. However, we use equality, which is stronger. See (*) for
 255                         // an explanation.
 256                         self.demand_eqtype_pat(pat.span, region_ty, local_ty, match_discrim_span);
 257                     }
 258                     // otherwise the type of x is the expected type T
 259                     ty::BindByValue(_) => {
 260                         // As above, `T <: typeof(x)` is required but we
 261                         // use equality, see (*) below.
 262                         self.demand_eqtype_pat(pat.span, expected, local_ty, match_discrim_span);
 263                     }
 264                 }
 265
 266                 // if there are multiple arms, make sure they all agree on
 267                 // what the type of the binding `x` ought to be
 268                 if var_id != pat.hir_id {
 269                     let vt = self.local_ty(pat.span, var_id).decl_ty;
 270                     self.demand_eqtype_pat(pat.span, vt, local_ty, match_discrim_span);
 271                 }
 272
 273                 if let Some(ref p) = *sub {
 274                     self.check_pat_walk(&p, expected, def_bm, match_discrim_span);
 275                 }
 276
 277                 local_ty
 278             }
 279             PatKind::TupleStruct(ref qpath, ref subpats, ddpos) => {
 280                 self.check_pat_tuple_struct(
 281                     pat,
 282                     qpath,
 283                     &subpats,
 284                     ddpos,
 285                     expected,
 286                     def_bm,
 287                     match_discrim_span,
 288                 )
 289             }
 290             PatKind::Path(ref qpath) => {
 291                 self.check_pat_path(pat, qpath, expected)
 292             }
 293             PatKind::Struct(ref qpath, ref fields, etc) => {
 294                 self.check_pat_struct(pat, qpath, fields, etc, expected, def_bm, match_discrim_span)
 295             }
 296             PatKind::Tuple(ref elements, ddpos) => {
 297                 let mut expected_len = elements.len();
 298                 if ddpos.is_some() {
 299                     // Require known type only when `..` is present.
 300                     if let ty::Tuple(ref tys) =
 301                             self.structurally_resolved_type(pat.span, expected).sty {
 302                         expected_len = tys.len();
 303                     }
 304                 }
 305                 let max_len = cmp::max(expected_len, elements.len());
 306
 307                 let element_tys_iter = (0..max_len).map(|_| self.next_ty_var(
 308                     // FIXME: `MiscVariable` for now -- obtaining the span and name information
 309                     // from all tuple elements isn't trivial.
 310                     TypeVariableOrigin::TypeInference(pat.span)));
 311                 let element_tys = tcx.mk_type_list(element_tys_iter);
 312                 let pat_ty = tcx.mk_ty(ty::Tuple(element_tys));
 313                 if let Some(mut err) = self.demand_eqtype_diag(pat.span, expected, pat_ty) {
 314                     err.emit();
 315                     // Walk subpatterns with an expected type of `err` in this case to silence
 316                     // further errors being emitted when using the bindings. #50333
 317                     let element_tys_iter = (0..max_len).map(|_| tcx.types.err);
 318                     for (_, elem) in elements.iter().enumerate_and_adjust(max_len, ddpos) {
 319                         self.check_pat_walk(elem, &tcx.types.err, def_bm, match_discrim_span);
 320                     }
 321                     tcx.mk_tup(element_tys_iter)
 322                 } else {
 323                     for (i, elem) in elements.iter().enumerate_and_adjust(max_len, ddpos) {
 324                         self.check_pat_walk(elem, &element_tys[i], def_bm, match_discrim_span);
 325                     }
 326                     pat_ty
 327                 }
 328             }
 329             PatKind::Box(ref inner) => {
 330                 let inner_ty = self.next_ty_var(TypeVariableOrigin::TypeInference(inner.span));
 331                 let uniq_ty = tcx.mk_box(inner_ty);
 332
 333                 if self.check_dereferencable(pat.span, expected, &inner) {
 334                     // Here, `demand::subtype` is good enough, but I don't
 335                     // think any errors can be introduced by using
 336                     // `demand::eqtype`.
 337                     self.demand_eqtype_pat(pat.span, expected, uniq_ty, match_discrim_span);
 338                     self.check_pat_walk(&inner, inner_ty, def_bm, match_discrim_span);
 339                     uniq_ty
 340                 } else {
 341                     self.check_pat_walk(&inner, tcx.types.err, def_bm, match_discrim_span);
 342                     tcx.types.err
 343                 }
 344             }
 345             PatKind::Ref(ref inner, mutbl) => {
 346                 let expected = self.shallow_resolve(expected);
 347                 if self.check_dereferencable(pat.span, expected, &inner) {
 348                     // `demand::subtype` would be good enough, but using
 349                     // `eqtype` turns out to be equally general. See (*)
 350                     // below for details.
 351
 352                     // Take region, inner-type from expected type if we
 353                     // can, to avoid creating needless variables.  This
 354                     // also helps with the bad interactions of the given
 355                     // hack detailed in (*) below.
 356                     debug!("check_pat_walk: expected={:?}", expected);
 357                     let (rptr_ty, inner_ty) = match expected.sty {
 358                         ty::Ref(_, r_ty, r_mutbl) if r_mutbl == mutbl => {
 359                             (expected, r_ty)
 360                         }
 361                         _ => {
 362                             let inner_ty = self.next_ty_var(
 363                                 TypeVariableOrigin::TypeInference(inner.span));
 364                             let mt = ty::TypeAndMut { ty: inner_ty, mutbl: mutbl };
 365                             let region = self.next_region_var(infer::PatternRegion(pat.span));
 366                             let rptr_ty = tcx.mk_ref(region, mt);
 367                             debug!("check_pat_walk: demanding {:?} = {:?}", expected, rptr_ty);
 368                             let err = self.demand_eqtype_diag(pat.span, expected, rptr_ty);
 369
 370                             // Look for a case like `fn foo(&foo: u32)` and suggest
 371                             // `fn foo(foo: &u32)`
 372                             if let Some(mut err) = err {
 373                                 if let PatKind::Binding(..) = inner.node {
 374                                     if let Ok(snippet) = tcx.sess.source_map()
 375                                                                     .span_to_snippet(pat.span)
 376                                     {
 377                                         err.help(&format!("did you mean `{}: &{}`?",
 378                                                             &snippet[1..],
 379                                                             expected));
 380                                     }
 381                                 }
 382                                 err.emit();
 383                             }
 384                             (rptr_ty, inner_ty)
 385                         }
 386                     };
 387
 388                     self.check_pat_walk(&inner, inner_ty, def_bm, match_discrim_span);
 389                     rptr_ty
 390                 } else {
 391                     self.check_pat_walk(&inner, tcx.types.err, def_bm, match_discrim_span);
 392                     tcx.types.err
 393                 }
 394             }
 395             PatKind::Slice(ref before, ref slice, ref after) => {
 396                 let expected_ty = self.structurally_resolved_type(pat.span, expected);
 397                 let (inner_ty, slice_ty) = match expected_ty.sty {
 398                     ty::Array(inner_ty, size) => {
 399                         let size = size.unwrap_usize(tcx);
 400                         let min_len = before.len() as u64 + after.len() as u64;
 401                         if slice.is_none() {
 402                             if min_len != size {
 403                                 struct_span_err!(
 404                                     tcx.sess, pat.span, E0527,
 405                                     "pattern requires {} elements but array has {}",
 406                                     min_len, size)
 407                                     .span_label(pat.span, format!("expected {} elements", size))
 408                                     .emit();
 409                             }
 410                             (inner_ty, tcx.types.err)
 411                         } else if let Some(rest) = size.checked_sub(min_len) {
 412                             (inner_ty, tcx.mk_array(inner_ty, rest))
 413                         } else {
 414                             struct_span_err!(tcx.sess, pat.span, E0528,
 415                                     "pattern requires at least {} elements but array has {}",
 416                                     min_len, size)
 417                                 .span_label(pat.span,
 418                                     format!("pattern cannot match array of {} elements", size))
 419                                 .emit();
 420                             (inner_ty, tcx.types.err)
 421                         }
 422                     }
 423                     ty::Slice(inner_ty) => (inner_ty, expected_ty),
 424                     _ => {
 425                         if !expected_ty.references_error() {
 426                             let mut err = struct_span_err!(
 427                                 tcx.sess, pat.span, E0529,
 428                                 "expected an array or slice, found `{}`",
 429                                 expected_ty);
 430                             if let ty::Ref(_, ty, _) = expected_ty.sty {
 431                                 match ty.sty {
 432                                     ty::Array(..) | ty::Slice(..) => {
 433                                         err.help("the semantics of slice patterns changed \
 434                                                   recently; see issue #23121");
 435                                     }
 436                                     _ => {}
 437                                 }
 438                             }
 439
 440                             err.span_label( pat.span,
 441                                 format!("pattern cannot match with input type `{}`", expected_ty)
 442                             ).emit();
 443                         }
 444                         (tcx.types.err, tcx.types.err)
 445                     }
 446                 };
 447
 448                 for elt in before {
 449                     self.check_pat_walk(&elt, inner_ty, def_bm, match_discrim_span);
 450                 }
 451                 if let Some(ref slice) = *slice {
 452                     self.check_pat_walk(&slice, slice_ty, def_bm, match_discrim_span);
 453                 }
 454                 for elt in after {
 455                     self.check_pat_walk(&elt, inner_ty, def_bm, match_discrim_span);
 456                 }
 457                 expected_ty
 458             }
 459         };
 460
 461         self.write_ty(pat.hir_id, ty);
 462
 463         // (*) In most of the cases above (literals and constants being
 464         // the exception), we relate types using strict equality, even
 465         // though subtyping would be sufficient. There are a few reasons
 466         // for this, some of which are fairly subtle and which cost me
 467         // (nmatsakis) an hour or two debugging to remember, so I thought
 468         // I'd write them down this time.
 469         //
 470         // 1. There is no loss of expressiveness here, though it does
 471         // cause some inconvenience. What we are saying is that the type
 472         // of `x` becomes *exactly* what is expected. This can cause unnecessary
 473         // errors in some cases, such as this one:
 474         //
 475         // ```
 476         // fn foo<'x>(x: &'x int) {
 477         //    let a = 1;
 478         //    let mut z = x;
 479         //    z = &a;
 480         // }
 481         // ```
 482         //
 483         // The reason we might get an error is that `z` might be
 484         // assigned a type like `&'x int`, and then we would have
 485         // a problem when we try to assign `&a` to `z`, because
 486         // the lifetime of `&a` (i.e., the enclosing block) is
 487         // shorter than `'x`.
 488         //
 489         // HOWEVER, this code works fine. The reason is that the
 490         // expected type here is whatever type the user wrote, not
 491         // the initializer's type. In this case the user wrote
 492         // nothing, so we are going to create a type variable `Z`.
 493         // Then we will assign the type of the initializer (`&'x
 494         // int`) as a subtype of `Z`: `&'x int <: Z`. And hence we
 495         // will instantiate `Z` as a type `&'0 int` where `'0` is
 496         // a fresh region variable, with the constraint that `'x :
 497         // '0`.  So basically we're all set.
 498         //
 499         // Note that there are two tests to check that this remains true
 500         // (`regions-reassign-{match,let}-bound-pointer.rs`).
 501         //
 502         // 2. Things go horribly wrong if we use subtype. The reason for
 503         // THIS is a fairly subtle case involving bound regions. See the
 504         // `givens` field in `region_constraints`, as well as the test
 505         // `regions-relate-bound-regions-on-closures-to-inference-variables.rs`,
 506         // for details. Short version is that we must sometimes detect
 507         // relationships between specific region variables and regions
 508         // bound in a closure signature, and that detection gets thrown
 509         // off when we substitute fresh region variables here to enable
 510         // subtyping.
 511     }
 512
 513     pub fn check_dereferencable(&self, span: Span, expected: Ty<'tcx>, inner: &hir::Pat) -> bool {
 514         if let PatKind::Binding(..) = inner.node {
 515             if let Some(mt) = self.shallow_resolve(expected).builtin_deref(true) {
 516                 if let ty::Dynamic(..) = mt.ty.sty {
 517                     // This is "x = SomeTrait" being reduced from
 518                     // "let &x = &SomeTrait" or "let box x = Box<SomeTrait>", an error.
 519                     let type_str = self.ty_to_string(expected);
 520                     let mut err = struct_span_err!(
 521                         self.tcx.sess,
 522                         span,
 523                         E0033,
 524                         "type `{}` cannot be dereferenced",
 525                         type_str
 526                     );
 527                     err.span_label(span, format!("type `{}` cannot be dereferenced", type_str));
 528                     if self.tcx.sess.teach(&err.get_code().unwrap()) {
 529                         err.note("\
 530 This error indicates that a pointer to a trait type cannot be implicitly dereferenced by a \
 531 pattern. Every trait defines a type, but because the size of trait implementors isn't fixed, \
 532 this type has no compile-time size. Therefore, all accesses to trait types must be through \
 533 pointers. If you encounter this error you should try to avoid dereferencing the pointer.
 534
 535 You can read more about trait objects in the Trait Objects section of the Reference: \
 536 https://doc.rust-lang.org/reference/types.html#trait-objects");
 537                     }
 538                     err.emit();
 539                     return false
 540                 }
 541             }
 542         }
 543         true
 544     }
 545
 546     pub fn check_match(
 547         &self,
 548         expr: &'gcx hir::Expr,
 549         discrim: &'gcx hir::Expr,
 550         arms: &'gcx [hir::Arm],
 551         expected: Expectation<'tcx>,
 552         match_src: hir::MatchSource,
 553     ) -> Ty<'tcx> {
 554         let tcx = self.tcx;
 555
 556         // Not entirely obvious: if matches may create ref bindings, we want to
 557         // use the *precise* type of the discriminant, *not* some supertype, as
 558         // the "discriminant type" (issue #23116).
 559         //
 560         // arielb1 [writes here in this comment thread][c] that there
 561         // is certainly *some* potential danger, e.g., for an example
 562         // like:
 563         //
 564         // [c]: https://github.com/rust-lang/rust/pull/43399#discussion_r130223956
 565         //
 566         // ```
 567         // let Foo(x) = f()[0];
 568         // ```
 569         //
 570         // Then if the pattern matches by reference, we want to match
 571         // `f()[0]` as a lexpr, so we can't allow it to be
 572         // coerced. But if the pattern matches by value, `f()[0]` is
 573         // still syntactically a lexpr, but we *do* want to allow
 574         // coercions.
 575         //
 576         // However, *likely* we are ok with allowing coercions to
 577         // happen if there are no explicit ref mut patterns - all
 578         // implicit ref mut patterns must occur behind a reference, so
 579         // they will have the "correct" variance and lifetime.
 580         //
 581         // This does mean that the following pattern would be legal:
 582         //
 583         // ```
 584         // struct Foo(Bar);
 585         // struct Bar(u32);
 586         // impl Deref for Foo {
 587         //     type Target = Bar;
 588         //     fn deref(&self) -> &Bar { &self.0 }
 589         // }
 590         // impl DerefMut for Foo {
 591         //     fn deref_mut(&mut self) -> &mut Bar { &mut self.0 }
 592         // }
 593         // fn foo(x: &mut Foo) {
 594         //     {
 595         //         let Bar(z): &mut Bar = x;
 596         //         *z = 42;
 597         //     }
 598         //     assert_eq!(foo.0.0, 42);
 599         // }
 600         // ```
 601         //
 602         // FIXME(tschottdorf): don't call contains_explicit_ref_binding, which
 603         // is problematic as the HIR is being scraped, but ref bindings may be
 604         // implicit after #42640. We need to make sure that pat_adjustments
 605         // (once introduced) is populated by the time we get here.
 606         //
 607         // See #44848.
 608         let contains_ref_bindings = arms.iter()
 609                                         .filter_map(|a| a.contains_explicit_ref_binding())
 610                                         .max_by_key(|m| match *m {
 611                                             hir::MutMutable => 1,
 612                                             hir::MutImmutable => 0,
 613                                         });
 614         let discrim_ty;
 615         if let Some(m) = contains_ref_bindings {
 616             discrim_ty = self.check_expr_with_needs(discrim, Needs::maybe_mut_place(m));
 617         } else {
 618             // ...but otherwise we want to use any supertype of the
 619             // discriminant. This is sort of a workaround, see note (*) in
 620             // `check_pat` for some details.
 621             discrim_ty = self.next_ty_var(TypeVariableOrigin::TypeInference(discrim.span));
 622             self.check_expr_has_type_or_error(discrim, discrim_ty);
 623         };
 624
 625         // If there are no arms, that is a diverging match; a special case.
 626         if arms.is_empty() {
 627             self.diverges.set(self.diverges.get() | Diverges::Always);
 628             return tcx.types.never;
 629         }
 630
 631         if self.diverges.get().always() {
 632             for arm in arms {
 633                 self.warn_if_unreachable(arm.body.hir_id, arm.body.span, "arm");
 634             }
 635         }
 636
 637         // Otherwise, we have to union together the types that the
 638         // arms produce and so forth.
 639         let discrim_diverges = self.diverges.get();
 640         self.diverges.set(Diverges::Maybe);
 641
 642         // rust-lang/rust#55810: Typecheck patterns first (via eager
 643         // collection into `Vec`), so we get types for all bindings.
 644         let all_arm_pats_diverge: Vec<_> = arms.iter().map(|arm| {
 645             let mut all_pats_diverge = Diverges::WarnedAlways;
 646             for p in &arm.pats {
 647                 self.diverges.set(Diverges::Maybe);
 648                 self.check_pat_walk(
 649                     &p,
 650                     discrim_ty,
 651                     ty::BindingMode::BindByValue(hir::Mutability::MutImmutable),
 652                     Some(discrim.span),
 653                 );
 654                 all_pats_diverge &= self.diverges.get();
 655             }
 656
 657             // As discussed with @eddyb, this is for disabling unreachable_code
 658             // warnings on patterns (they're now subsumed by unreachable_patterns
 659             // warnings).
 660             match all_pats_diverge {
 661                 Diverges::Maybe => Diverges::Maybe,
 662                 Diverges::Always | Diverges::WarnedAlways => Diverges::WarnedAlways,
 663             }
 664         }).collect();
 665
 666         // Now typecheck the blocks.
 667         //
 668         // The result of the match is the common supertype of all the
 669         // arms. Start out the value as bottom, since it's the, well,
 670         // bottom the type lattice, and we'll be moving up the lattice as
 671         // we process each arm. (Note that any match with 0 arms is matching
 672         // on any empty type and is therefore unreachable; should the flow
 673         // of execution reach it, we will panic, so bottom is an appropriate
 674         // type in that case)
 675         let mut all_arms_diverge = Diverges::WarnedAlways;
 676
 677         let expected = expected.adjust_for_branches(self);
 678
 679         let mut coercion = {
 680             let coerce_first = match expected {
 681                 // We don't coerce to `()` so that if the match expression is a
 682                 // statement it's branches can have any consistent type. That allows
 683                 // us to give better error messages (pointing to a usually better
 684                 // arm for inconsistent arms or to the whole match when a `()` type
 685                 // is required).
 686                 Expectation::ExpectHasType(ety) if ety != self.tcx.mk_unit() => ety,
 687                 _ => self.next_ty_var(TypeVariableOrigin::MiscVariable(expr.span)),
 688             };
 689             CoerceMany::with_coercion_sites(coerce_first, arms)
 690         };
 691
 692         let mut other_arms = vec![];  // used only for diagnostics
 693         let mut prior_arm_ty = None;
 694         for (i, (arm, pats_diverge)) in arms.iter().zip(all_arm_pats_diverge).enumerate() {
 695             if let Some(ref g) = arm.guard {
 696                 self.diverges.set(pats_diverge);
 697                 match g {
 698                     hir::Guard::If(e) => self.check_expr_has_type_or_error(e, tcx.types.bool),
 699                 };
 700             }
 701
 702             self.diverges.set(pats_diverge);
 703             let arm_ty = self.check_expr_with_expectation(&arm.body, expected);
 704             all_arms_diverge &= self.diverges.get();
 705
 706             // Handle the fallback arm of a desugared if-let like a missing else.
 707             let is_if_let_fallback = match match_src {
 708                 hir::MatchSource::IfLetDesugar { contains_else_clause: false } => {
 709                     i == arms.len() - 1 && arm_ty.is_unit()
 710                 }
 711                 _ => false
 712             };
 713
 714             let arm_span = if let hir::ExprKind::Block(ref blk, _) = arm.body.node {
 715                 // Point at the block expr instead of the entire block
 716                 blk.expr.as_ref().map(|e| e.span).unwrap_or(arm.body.span)
 717             } else {
 718                 arm.body.span
 719             };
 720             if is_if_let_fallback {
 721                 let cause = self.cause(expr.span, ObligationCauseCode::IfExpressionWithNoElse);
 722                 assert!(arm_ty.is_unit());
 723                 coercion.coerce_forced_unit(self, &cause, &mut |_| (), true);
 724             } else {
 725                 let cause = if i == 0 {
 726                     // The reason for the first arm to fail is not that the match arms diverge,
 727                     // but rather that there's a prior obligation that doesn't hold.
 728                     self.cause(arm_span, ObligationCauseCode::BlockTailExpression(arm.body.hir_id))
 729                 } else {
 730                     self.cause(expr.span, ObligationCauseCode::MatchExpressionArm {
 731                         arm_span,
 732                         source: match_src,
 733                         prior_arms: other_arms.clone(),
 734                         last_ty: prior_arm_ty.unwrap(),
 735                         discrim_hir_id: discrim.hir_id,
 736                     })
 737                 };
 738                 coercion.coerce(self, &cause, &arm.body, arm_ty);
 739             }
 740             other_arms.push(arm_span);
 741             if other_arms.len() > 5 {
 742                 other_arms.remove(0);
 743             }
 744             prior_arm_ty = Some(arm_ty);
 745         }
 746
 747         // We won't diverge unless the discriminant or all arms diverge.
 748         self.diverges.set(discrim_diverges | all_arms_diverge);
 749
 750         coercion.complete(self)
 751     }
 752
 753     fn check_pat_struct(
 754         &self,
 755         pat: &'gcx hir::Pat,
 756         qpath: &hir::QPath,
 757         fields: &'gcx [Spanned<hir::FieldPat>],
 758         etc: bool,
 759         expected: Ty<'tcx>,
 760         def_bm: ty::BindingMode,
 761         match_discrim_span: Option<Span>,
 762     ) -> Ty<'tcx>
 763     {
 764         // Resolve the path and check the definition for errors.
 765         let (variant, pat_ty) = if let Some(variant_ty) = self.check_struct_path(qpath, pat.hir_id)
 766         {
 767             variant_ty
 768         } else {
 769             for field in fields {
 770                 self.check_pat_walk(
 771                     &field.node.pat,
 772                     self.tcx.types.err,
 773                     def_bm,
 774                     match_discrim_span,
 775                 );
 776             }
 777             return self.tcx.types.err;
 778         };
 779
 780         // Type-check the path.
 781         self.demand_eqtype_pat(pat.span, expected, pat_ty, match_discrim_span);
 782
 783         // Type-check subpatterns.
 784         if self.check_struct_pat_fields(pat_ty, pat.hir_id, pat.span, variant, fields, etc, def_bm)
 785         {
 786             pat_ty
 787         } else {
 788             self.tcx.types.err
 789         }
 790     }
 791
 792     fn check_pat_path(
 793         &self,
 794         pat: &hir::Pat,
 795         qpath: &hir::QPath,
 796         expected: Ty<'tcx>,
 797     ) -> Ty<'tcx> {
 798         let tcx = self.tcx;
 799
 800         // Resolve the path and check the definition for errors.
 801         let (def, opt_ty, segments) = self.resolve_ty_and_def_ufcs(qpath, pat.hir_id, pat.span);
 802         match def {
 803             Def::Err => {
 804                 self.set_tainted_by_errors();
 805                 return tcx.types.err;
 806             }
 807             Def::Method(..) => {
 808                 report_unexpected_variant_def(tcx, &def, pat.span, qpath);
 809                 return tcx.types.err;
 810             }
 811             Def::Ctor(_, _, CtorKind::Fictive) |
 812             Def::Ctor(_, _, CtorKind::Fn) => {
 813                 report_unexpected_variant_def(tcx, &def, pat.span, qpath);
 814                 return tcx.types.err;
 815             }
 816             Def::Ctor(_, _, CtorKind::Const) | Def::SelfCtor(..) |
 817             Def::Const(..) | Def::AssociatedConst(..) => {} // OK
 818             _ => bug!("unexpected pattern definition: {:?}", def)
 819         }
 820
 821         // Type-check the path.
 822         let pat_ty = self.instantiate_value_path(segments, opt_ty, def, pat.span, pat.hir_id).0;
 823         self.demand_suptype(pat.span, expected, pat_ty);
 824         pat_ty
 825     }
 826
 827     fn check_pat_tuple_struct(
 828         &self,
 829         pat: &hir::Pat,
 830         qpath: &hir::QPath,
 831         subpats: &'gcx [P<hir::Pat>],
 832         ddpos: Option<usize>,
 833         expected: Ty<'tcx>,
 834         def_bm: ty::BindingMode,
 835         match_arm_pat_span: Option<Span>,
 836     ) -> Ty<'tcx> {
 837         let tcx = self.tcx;
 838         let on_error = || {
 839             for pat in subpats {
 840                 self.check_pat_walk(&pat, tcx.types.err, def_bm, match_arm_pat_span);
 841             }
 842         };
 843         let report_unexpected_def = |def: Def| {
 844             let msg = format!("expected tuple struct/variant, found {} `{}`",
 845                               def.kind_name(),
 846                               hir::print::to_string(tcx.hir(), |s| s.print_qpath(qpath, false)));
 847             struct_span_err!(tcx.sess, pat.span, E0164, "{}", msg)
 848                 .span_label(pat.span, "not a tuple variant or struct").emit();
 849             on_error();
 850         };
 851
 852         // Resolve the path and check the definition for errors.
 853         let (def, opt_ty, segments) = self.resolve_ty_and_def_ufcs(qpath, pat.hir_id, pat.span);
 854         if def == Def::Err {
 855             self.set_tainted_by_errors();
 856             on_error();
 857             return self.tcx.types.err;
 858         }
 859
 860         // Type-check the path.
 861         let (pat_ty, def) = self.instantiate_value_path(segments, opt_ty, def, pat.span,
 862             pat.hir_id);
 863         if !pat_ty.is_fn() {
 864             report_unexpected_def(def);
 865             return self.tcx.types.err;
 866         }
 867
 868         let variant = match def {
 869             Def::Err => {
 870                 self.set_tainted_by_errors();
 871                 on_error();
 872                 return tcx.types.err;
 873             }
 874             Def::AssociatedConst(..) | Def::Method(..) => {
 875                 report_unexpected_def(def);
 876                 return tcx.types.err;
 877             }
 878             Def::Ctor(_, _, CtorKind::Fn) => {
 879                 tcx.expect_variant_def(def)
 880             }
 881             _ => bug!("unexpected pattern definition: {:?}", def)
 882         };
 883
 884         // Replace constructor type with constructed type for tuple struct patterns.
 885         let pat_ty = pat_ty.fn_sig(tcx).output();
 886         let pat_ty = pat_ty.no_bound_vars().expect("expected fn type");
 887
 888         self.demand_eqtype_pat(pat.span, expected, pat_ty, match_arm_pat_span);
 889
 890         // Type-check subpatterns.
 891         if subpats.len() == variant.fields.len() ||
 892                 subpats.len() < variant.fields.len() && ddpos.is_some() {
 893             let substs = match pat_ty.sty {
 894                 ty::Adt(_, substs) => substs,
 895                 _ => bug!("unexpected pattern type {:?}", pat_ty),
 896             };
 897             for (i, subpat) in subpats.iter().enumerate_and_adjust(variant.fields.len(), ddpos) {
 898                 let field_ty = self.field_ty(subpat.span, &variant.fields[i], substs);
 899                 self.check_pat_walk(&subpat, field_ty, def_bm, match_arm_pat_span);
 900
 901                 self.tcx.check_stability(variant.fields[i].did, Some(pat.hir_id), subpat.span);
 902             }
 903         } else {
 904             let subpats_ending = if subpats.len() == 1 { "" } else { "s" };
 905             let fields_ending = if variant.fields.len() == 1 { "" } else { "s" };
 906             struct_span_err!(tcx.sess, pat.span, E0023,
 907                              "this pattern has {} field{}, but the corresponding {} has {} field{}",
 908                              subpats.len(), subpats_ending, def.kind_name(),
 909                              variant.fields.len(),  fields_ending)
 910                 .span_label(pat.span, format!("expected {} field{}, found {}",
 911                                               variant.fields.len(), fields_ending, subpats.len()))
 912                 .emit();
 913             on_error();
 914             return tcx.types.err;
 915         }
 916         pat_ty
 917     }
 918
 919     fn check_struct_pat_fields(
 920         &self,
 921         adt_ty: Ty<'tcx>,
 922         pat_id: hir::HirId,
 923         span: Span,
 924         variant: &'tcx ty::VariantDef,
 925         fields: &'gcx [Spanned<hir::FieldPat>],
 926         etc: bool,
 927         def_bm: ty::BindingMode,
 928     ) -> bool {
 929         let tcx = self.tcx;
 930
 931         let (substs, adt) = match adt_ty.sty {
 932             ty::Adt(adt, substs) => (substs, adt),
 933             _ => span_bug!(span, "struct pattern is not an ADT")
 934         };
 935         let kind_name = adt.variant_descr();
 936
 937         // Index the struct fields' types.
 938         let field_map = variant.fields
 939             .iter()
 940             .enumerate()
 941             .map(|(i, field)| (field.ident.modern(), (i, field)))
 942             .collect::<FxHashMap<_, _>>();
 943
 944         // Keep track of which fields have already appeared in the pattern.
 945         let mut used_fields = FxHashMap::default();
 946         let mut no_field_errors = true;
 947
 948         let mut inexistent_fields = vec![];
 949         // Typecheck each field.
 950         for &Spanned { node: ref field, span } in fields {
 951             let ident = tcx.adjust_ident(field.ident, variant.def_id, self.body_id).0;
 952             let field_ty = match used_fields.entry(ident) {
 953                 Occupied(occupied) => {
 954                     struct_span_err!(tcx.sess, span, E0025,
 955                                      "field `{}` bound multiple times \
 956                                       in the pattern",
 957                                      field.ident)
 958                         .span_label(span,
 959                                     format!("multiple uses of `{}` in pattern", field.ident))
 960                         .span_label(*occupied.get(), format!("first use of `{}`", field.ident))
 961                         .emit();
 962                     no_field_errors = false;
 963                     tcx.types.err
 964                 }
 965                 Vacant(vacant) => {
 966                     vacant.insert(span);
 967                     field_map.get(&ident)
 968                         .map(|(i, f)| {
 969                             self.write_field_index(field.hir_id, *i);
 970                             self.tcx.check_stability(f.did, Some(pat_id), span);
 971                             self.field_ty(span, f, substs)
 972                         })
 973                         .unwrap_or_else(|| {
 974                             inexistent_fields.push(field.ident);
 975                             no_field_errors = false;
 976                             tcx.types.err
 977                         })
 978                 }
 979             };
 980
 981             self.check_pat_walk(&field.pat, field_ty, def_bm, None);
 982         }
 983         let mut unmentioned_fields = variant.fields
 984                 .iter()
 985                 .map(|field| field.ident.modern())
 986                 .filter(|ident| !used_fields.contains_key(&ident))
 987                 .collect::<Vec<_>>();
 988         if inexistent_fields.len() > 0 && !variant.recovered {
 989             let (field_names, t, plural) = if inexistent_fields.len() == 1 {
 990                 (format!("a field named `{}`", inexistent_fields[0]), "this", "")
 991             } else {
 992                 (format!("fields named {}",
 993                          inexistent_fields.iter()
 994                             .map(|ident| format!("`{}`", ident))
 995                             .collect::<Vec<String>>()
 996                             .join(", ")), "these", "s")
 997             };
 998             let spans = inexistent_fields.iter().map(|ident| ident.span).collect::<Vec<_>>();
 999             let mut err = struct_span_err!(tcx.sess,
1000                                            spans,
1001                                            E0026,
1002                                            "{} `{}` does not have {}",
1003                                            kind_name,
1004                                            tcx.def_path_str(variant.def_id),
1005                                            field_names);
1006             if let Some(ident) = inexistent_fields.last() {
1007                 err.span_label(ident.span,
1008                                format!("{} `{}` does not have {} field{}",
1009                                        kind_name,
1010                                        tcx.def_path_str(variant.def_id),
1011                                        t,
1012                                        plural));
1013                 if plural == "" {
1014                     let input = unmentioned_fields.iter().map(|field| &field.name);
1015                     let suggested_name =
1016                         find_best_match_for_name(input, &ident.as_str(), None);
1017                     if let Some(suggested_name) = suggested_name {
1018                         err.span_suggestion(
1019                             ident.span,
1020                             "a field with a similar name exists",
1021                             suggested_name.to_string(),
1022                             Applicability::MaybeIncorrect,
1023                         );
1024
1025                         // we don't want to throw `E0027` in case we have thrown `E0026` for them
1026                         unmentioned_fields.retain(|&x| x.as_str() != suggested_name.as_str());
1027                     }
1028                 }
1029             }
1030             if tcx.sess.teach(&err.get_code().unwrap()) {
1031                 err.note(
1032                     "This error indicates that a struct pattern attempted to \
1033                      extract a non-existent field from a struct. Struct fields \
1034                      are identified by the name used before the colon : so struct \
1035                      patterns should resemble the declaration of the struct type \
1036                      being matched.\n\n\
1037                      If you are using shorthand field patterns but want to refer \
1038                      to the struct field by a different name, you should rename \
1039                      it explicitly."
1040                 );
1041             }
1042             err.emit();
1043         }
1044
1045         // Require `..` if struct has non_exhaustive attribute.
1046         if variant.is_field_list_non_exhaustive() && !adt.did.is_local() && !etc {
1047             span_err!(tcx.sess, span, E0638,
1048                       "`..` required with {} marked as non-exhaustive",
1049                       kind_name);
1050         }
1051
1052         // Report an error if incorrect number of the fields were specified.
1053         if kind_name == "union" {
1054             if fields.len() != 1 {
1055                 tcx.sess.span_err(span, "union patterns should have exactly one field");
1056             }
1057             if etc {
1058                 tcx.sess.span_err(span, "`..` cannot be used in union patterns");
1059             }
1060         } else if !etc {
1061             if unmentioned_fields.len() > 0 {
1062                 let field_names = if unmentioned_fields.len() == 1 {
1063                     format!("field `{}`", unmentioned_fields[0])
1064                 } else {
1065                     format!("fields {}",
1066                             unmentioned_fields.iter()
1067                                 .map(|name| format!("`{}`", name))
1068                                 .collect::<Vec<String>>()
1069                                 .join(", "))
1070                 };
1071                 let mut diag = struct_span_err!(tcx.sess, span, E0027,
1072                                                 "pattern does not mention {}",
1073                                                 field_names);
1074                 diag.span_label(span, format!("missing {}", field_names));
1075                 if variant.ctor_kind == CtorKind::Fn {
1076                     diag.note("trying to match a tuple variant with a struct variant pattern");
1077                 }
1078                 if tcx.sess.teach(&diag.get_code().unwrap()) {
1079                     diag.note(
1080                         "This error indicates that a pattern for a struct fails to specify a \
1081                          sub-pattern for every one of the struct's fields. Ensure that each field \
1082                          from the struct's definition is mentioned in the pattern, or use `..` to \
1083                          ignore unwanted fields."
1084                     );
1085                 }
1086                 diag.emit();
1087             }
1088         }
1089         no_field_errors
1090     }
1091 }