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                     })
 736                 };
 737                 coercion.coerce(self, &cause, &arm.body, arm_ty);
 738             }
 739             other_arms.push(arm_span);
 740             if other_arms.len() > 5 {
 741                 other_arms.remove(0);
 742             }
 743             prior_arm_ty = Some(arm_ty);
 744         }
 745
 746         // We won't diverge unless the discriminant or all arms diverge.
 747         self.diverges.set(discrim_diverges | all_arms_diverge);
 748
 749         coercion.complete(self)
 750     }
 751
 752     fn check_pat_struct(
 753         &self,
 754         pat: &'gcx hir::Pat,
 755         qpath: &hir::QPath,
 756         fields: &'gcx [Spanned<hir::FieldPat>],
 757         etc: bool,
 758         expected: Ty<'tcx>,
 759         def_bm: ty::BindingMode,
 760         match_discrim_span: Option<Span>,
 761     ) -> Ty<'tcx>
 762     {
 763         // Resolve the path and check the definition for errors.
 764         let (variant, pat_ty) = if let Some(variant_ty) = self.check_struct_path(qpath, pat.hir_id)
 765         {
 766             variant_ty
 767         } else {
 768             for field in fields {
 769                 self.check_pat_walk(
 770                     &field.node.pat,
 771                     self.tcx.types.err,
 772                     def_bm,
 773                     match_discrim_span,
 774                 );
 775             }
 776             return self.tcx.types.err;
 777         };
 778
 779         // Type-check the path.
 780         self.demand_eqtype_pat(pat.span, expected, pat_ty, match_discrim_span);
 781
 782         // Type-check subpatterns.
 783         if self.check_struct_pat_fields(pat_ty, pat.hir_id, pat.span, variant, fields, etc, def_bm)
 784         {
 785             pat_ty
 786         } else {
 787             self.tcx.types.err
 788         }
 789     }
 790
 791     fn check_pat_path(
 792         &self,
 793         pat: &hir::Pat,
 794         qpath: &hir::QPath,
 795         expected: Ty<'tcx>,
 796     ) -> Ty<'tcx> {
 797         let tcx = self.tcx;
 798
 799         // Resolve the path and check the definition for errors.
 800         let (def, opt_ty, segments) = self.resolve_ty_and_def_ufcs(qpath, pat.hir_id, pat.span);
 801         match def {
 802             Def::Err => {
 803                 self.set_tainted_by_errors();
 804                 return tcx.types.err;
 805             }
 806             Def::Method(..) => {
 807                 report_unexpected_variant_def(tcx, &def, pat.span, qpath);
 808                 return tcx.types.err;
 809             }
 810             Def::Ctor(_, _, CtorKind::Fictive) |
 811             Def::Ctor(_, _, CtorKind::Fn) => {
 812                 report_unexpected_variant_def(tcx, &def, pat.span, qpath);
 813                 return tcx.types.err;
 814             }
 815             Def::Ctor(_, _, CtorKind::Const) | Def::SelfCtor(..) |
 816             Def::Const(..) | Def::AssociatedConst(..) => {} // OK
 817             _ => bug!("unexpected pattern definition: {:?}", def)
 818         }
 819
 820         // Type-check the path.
 821         let pat_ty = self.instantiate_value_path(segments, opt_ty, def, pat.span, pat.hir_id).0;
 822         self.demand_suptype(pat.span, expected, pat_ty);
 823         pat_ty
 824     }
 825
 826     fn check_pat_tuple_struct(
 827         &self,
 828         pat: &hir::Pat,
 829         qpath: &hir::QPath,
 830         subpats: &'gcx [P<hir::Pat>],
 831         ddpos: Option<usize>,
 832         expected: Ty<'tcx>,
 833         def_bm: ty::BindingMode,
 834         match_arm_pat_span: Option<Span>,
 835     ) -> Ty<'tcx> {
 836         let tcx = self.tcx;
 837         let on_error = || {
 838             for pat in subpats {
 839                 self.check_pat_walk(&pat, tcx.types.err, def_bm, match_arm_pat_span);
 840             }
 841         };
 842         let report_unexpected_def = |def: Def| {
 843             let msg = format!("expected tuple struct/variant, found {} `{}`",
 844                               def.kind_name(),
 845                               hir::print::to_string(tcx.hir(), |s| s.print_qpath(qpath, false)));
 846             struct_span_err!(tcx.sess, pat.span, E0164, "{}", msg)
 847                 .span_label(pat.span, "not a tuple variant or struct").emit();
 848             on_error();
 849         };
 850
 851         // Resolve the path and check the definition for errors.
 852         let (def, opt_ty, segments) = self.resolve_ty_and_def_ufcs(qpath, pat.hir_id, pat.span);
 853         if def == Def::Err {
 854             self.set_tainted_by_errors();
 855             on_error();
 856             return self.tcx.types.err;
 857         }
 858
 859         // Type-check the path.
 860         let (pat_ty, def) = self.instantiate_value_path(segments, opt_ty, def, pat.span,
 861             pat.hir_id);
 862         if !pat_ty.is_fn() {
 863             report_unexpected_def(def);
 864             return self.tcx.types.err;
 865         }
 866
 867         let variant = match def {
 868             Def::Err => {
 869                 self.set_tainted_by_errors();
 870                 on_error();
 871                 return tcx.types.err;
 872             }
 873             Def::AssociatedConst(..) | Def::Method(..) => {
 874                 report_unexpected_def(def);
 875                 return tcx.types.err;
 876             }
 877             Def::Ctor(_, _, CtorKind::Fn) => {
 878                 tcx.expect_variant_def(def)
 879             }
 880             _ => bug!("unexpected pattern definition: {:?}", def)
 881         };
 882
 883         // Replace constructor type with constructed type for tuple struct patterns.
 884         let pat_ty = pat_ty.fn_sig(tcx).output();
 885         let pat_ty = pat_ty.no_bound_vars().expect("expected fn type");
 886
 887         self.demand_eqtype_pat(pat.span, expected, pat_ty, match_arm_pat_span);
 888
 889         // Type-check subpatterns.
 890         if subpats.len() == variant.fields.len() ||
 891                 subpats.len() < variant.fields.len() && ddpos.is_some() {
 892             let substs = match pat_ty.sty {
 893                 ty::Adt(_, substs) => substs,
 894                 _ => bug!("unexpected pattern type {:?}", pat_ty),
 895             };
 896             for (i, subpat) in subpats.iter().enumerate_and_adjust(variant.fields.len(), ddpos) {
 897                 let field_ty = self.field_ty(subpat.span, &variant.fields[i], substs);
 898                 self.check_pat_walk(&subpat, field_ty, def_bm, match_arm_pat_span);
 899
 900                 self.tcx.check_stability(variant.fields[i].did, Some(pat.hir_id), subpat.span);
 901             }
 902         } else {
 903             let subpats_ending = if subpats.len() == 1 { "" } else { "s" };
 904             let fields_ending = if variant.fields.len() == 1 { "" } else { "s" };
 905             struct_span_err!(tcx.sess, pat.span, E0023,
 906                              "this pattern has {} field{}, but the corresponding {} has {} field{}",
 907                              subpats.len(), subpats_ending, def.kind_name(),
 908                              variant.fields.len(),  fields_ending)
 909                 .span_label(pat.span, format!("expected {} field{}, found {}",
 910                                               variant.fields.len(), fields_ending, subpats.len()))
 911                 .emit();
 912             on_error();
 913             return tcx.types.err;
 914         }
 915         pat_ty
 916     }
 917
 918     fn check_struct_pat_fields(
 919         &self,
 920         adt_ty: Ty<'tcx>,
 921         pat_id: hir::HirId,
 922         span: Span,
 923         variant: &'tcx ty::VariantDef,
 924         fields: &'gcx [Spanned<hir::FieldPat>],
 925         etc: bool,
 926         def_bm: ty::BindingMode,
 927     ) -> bool {
 928         let tcx = self.tcx;
 929
 930         let (substs, adt) = match adt_ty.sty {
 931             ty::Adt(adt, substs) => (substs, adt),
 932             _ => span_bug!(span, "struct pattern is not an ADT")
 933         };
 934         let kind_name = adt.variant_descr();
 935
 936         // Index the struct fields' types.
 937         let field_map = variant.fields
 938             .iter()
 939             .enumerate()
 940             .map(|(i, field)| (field.ident.modern(), (i, field)))
 941             .collect::<FxHashMap<_, _>>();
 942
 943         // Keep track of which fields have already appeared in the pattern.
 944         let mut used_fields = FxHashMap::default();
 945         let mut no_field_errors = true;
 946
 947         let mut inexistent_fields = vec![];
 948         // Typecheck each field.
 949         for &Spanned { node: ref field, span } in fields {
 950             let ident = tcx.adjust_ident(field.ident, variant.def_id, self.body_id).0;
 951             let field_ty = match used_fields.entry(ident) {
 952                 Occupied(occupied) => {
 953                     struct_span_err!(tcx.sess, span, E0025,
 954                                      "field `{}` bound multiple times \
 955                                       in the pattern",
 956                                      field.ident)
 957                         .span_label(span,
 958                                     format!("multiple uses of `{}` in pattern", field.ident))
 959                         .span_label(*occupied.get(), format!("first use of `{}`", field.ident))
 960                         .emit();
 961                     no_field_errors = false;
 962                     tcx.types.err
 963                 }
 964                 Vacant(vacant) => {
 965                     vacant.insert(span);
 966                     field_map.get(&ident)
 967                         .map(|(i, f)| {
 968                             self.write_field_index(field.hir_id, *i);
 969                             self.tcx.check_stability(f.did, Some(pat_id), span);
 970                             self.field_ty(span, f, substs)
 971                         })
 972                         .unwrap_or_else(|| {
 973                             inexistent_fields.push(field.ident);
 974                             no_field_errors = false;
 975                             tcx.types.err
 976                         })
 977                 }
 978             };
 979
 980             self.check_pat_walk(&field.pat, field_ty, def_bm, None);
 981         }
 982         let mut unmentioned_fields = variant.fields
 983                 .iter()
 984                 .map(|field| field.ident.modern())
 985                 .filter(|ident| !used_fields.contains_key(&ident))
 986                 .collect::<Vec<_>>();
 987         if inexistent_fields.len() > 0 && !variant.recovered {
 988             let (field_names, t, plural) = if inexistent_fields.len() == 1 {
 989                 (format!("a field named `{}`", inexistent_fields[0]), "this", "")
 990             } else {
 991                 (format!("fields named {}",
 992                          inexistent_fields.iter()
 993                             .map(|ident| format!("`{}`", ident))
 994                             .collect::<Vec<String>>()
 995                             .join(", ")), "these", "s")
 996             };
 997             let spans = inexistent_fields.iter().map(|ident| ident.span).collect::<Vec<_>>();
 998             let mut err = struct_span_err!(tcx.sess,
 999                                            spans,
1000                                            E0026,
1001                                            "{} `{}` does not have {}",
1002                                            kind_name,
1003                                            tcx.def_path_str(variant.def_id),
1004                                            field_names);
1005             if let Some(ident) = inexistent_fields.last() {
1006                 err.span_label(ident.span,
1007                                format!("{} `{}` does not have {} field{}",
1008                                        kind_name,
1009                                        tcx.def_path_str(variant.def_id),
1010                                        t,
1011                                        plural));
1012                 if plural == "" {
1013                     let input = unmentioned_fields.iter().map(|field| &field.name);
1014                     let suggested_name =
1015                         find_best_match_for_name(input, &ident.as_str(), None);
1016                     if let Some(suggested_name) = suggested_name {
1017                         err.span_suggestion(
1018                             ident.span,
1019                             "a field with a similar name exists",
1020                             suggested_name.to_string(),
1021                             Applicability::MaybeIncorrect,
1022                         );
1023
1024                         // we don't want to throw `E0027` in case we have thrown `E0026` for them
1025                         unmentioned_fields.retain(|&x| x.as_str() != suggested_name.as_str());
1026                     }
1027                 }
1028             }
1029             if tcx.sess.teach(&err.get_code().unwrap()) {
1030                 err.note(
1031                     "This error indicates that a struct pattern attempted to \
1032                      extract a non-existent field from a struct. Struct fields \
1033                      are identified by the name used before the colon : so struct \
1034                      patterns should resemble the declaration of the struct type \
1035                      being matched.\n\n\
1036                      If you are using shorthand field patterns but want to refer \
1037                      to the struct field by a different name, you should rename \
1038                      it explicitly."
1039                 );
1040             }
1041             err.emit();
1042         }
1043
1044         // Require `..` if struct has non_exhaustive attribute.
1045         if variant.is_field_list_non_exhaustive() && !adt.did.is_local() && !etc {
1046             span_err!(tcx.sess, span, E0638,
1047                       "`..` required with {} marked as non-exhaustive",
1048                       kind_name);
1049         }
1050
1051         // Report an error if incorrect number of the fields were specified.
1052         if kind_name == "union" {
1053             if fields.len() != 1 {
1054                 tcx.sess.span_err(span, "union patterns should have exactly one field");
1055             }
1056             if etc {
1057                 tcx.sess.span_err(span, "`..` cannot be used in union patterns");
1058             }
1059         } else if !etc {
1060             if unmentioned_fields.len() > 0 {
1061                 let field_names = if unmentioned_fields.len() == 1 {
1062                     format!("field `{}`", unmentioned_fields[0])
1063                 } else {
1064                     format!("fields {}",
1065                             unmentioned_fields.iter()
1066                                 .map(|name| format!("`{}`", name))
1067                                 .collect::<Vec<String>>()
1068                                 .join(", "))
1069                 };
1070                 let mut diag = struct_span_err!(tcx.sess, span, E0027,
1071                                                 "pattern does not mention {}",
1072                                                 field_names);
1073                 diag.span_label(span, format!("missing {}", field_names));
1074                 if variant.ctor_kind == CtorKind::Fn {
1075                     diag.note("trying to match a tuple variant with a struct variant pattern");
1076                 }
1077                 if tcx.sess.teach(&diag.get_code().unwrap()) {
1078                     diag.note(
1079                         "This error indicates that a pattern for a struct fails to specify a \
1080                          sub-pattern for every one of the struct's fields. Ensure that each field \
1081                          from the struct's definition is mentioned in the pattern, or use `..` to \
1082                          ignore unwanted fields."
1083                     );
1084                 }
1085                 diag.emit();
1086             }
1087         }
1088         no_field_errors
1089     }
1090 }