src/librustc_mir_build/hair/pattern/mod.rs

   1 //! Validation of patterns/matches.
   2
   3 mod _match;
   4 mod check_match;
   5 mod const_to_pat;
   6
   7 pub(crate) use self::check_match::check_match;
   8
   9 use crate::hair::util::UserAnnotatedTyHelpers;
  10
  11 use rustc::mir::interpret::{get_slice_bytes, sign_extend, ConstValue, ErrorHandled};
  12 use rustc::mir::interpret::{LitToConstError, LitToConstInput};
  13 use rustc::mir::UserTypeProjection;
  14 use rustc::mir::{BorrowKind, Field, Mutability};
  15 use rustc::ty::layout::VariantIdx;
  16 use rustc::ty::subst::{GenericArg, SubstsRef};
  17 use rustc::ty::{self, AdtDef, DefIdTree, Region, Ty, TyCtxt, UserType};
  18 use rustc::ty::{CanonicalUserType, CanonicalUserTypeAnnotation, CanonicalUserTypeAnnotations};
  19 use rustc_errors::struct_span_err;
  20 use rustc_hir as hir;
  21 use rustc_hir::def::{CtorKind, CtorOf, DefKind, Res};
  22 use rustc_hir::pat_util::EnumerateAndAdjustIterator;
  23 use rustc_hir::RangeEnd;
  24 use rustc_index::vec::Idx;
  25 use rustc_span::{Span, DUMMY_SP};
  26 use syntax::ast;
  27
  28 use std::cmp::Ordering;
  29 use std::fmt;
  30
  31 use rustc_error_codes::*;
  32
  33 #[derive(Clone, Debug)]
  34 crate enum PatternError {
  35     AssocConstInPattern(Span),
  36     StaticInPattern(Span),
  37     FloatBug,
  38     NonConstPath(Span),
  39 }
  40
  41 #[derive(Copy, Clone, Debug)]
  42 crate enum BindingMode {
  43     ByValue,
  44     ByRef(BorrowKind),
  45 }
  46
  47 #[derive(Clone, Debug)]
  48 crate struct FieldPat<'tcx> {
  49     crate field: Field,
  50     crate pattern: Pat<'tcx>,
  51 }
  52
  53 #[derive(Clone, Debug)]
  54 crate struct Pat<'tcx> {
  55     crate ty: Ty<'tcx>,
  56     crate span: Span,
  57     crate kind: Box<PatKind<'tcx>>,
  58 }
  59
  60 impl<'tcx> Pat<'tcx> {
  61     pub(crate) fn wildcard_from_ty(ty: Ty<'tcx>) -> Self {
  62         Pat { ty, span: DUMMY_SP, kind: Box::new(PatKind::Wild) }
  63     }
  64 }
  65
  66 #[derive(Copy, Clone, Debug, PartialEq)]
  67 crate struct PatTyProj<'tcx> {
  68     crate user_ty: CanonicalUserType<'tcx>,
  69 }
  70
  71 impl<'tcx> PatTyProj<'tcx> {
  72     pub(crate) fn from_user_type(user_annotation: CanonicalUserType<'tcx>) -> Self {
  73         Self { user_ty: user_annotation }
  74     }
  75
  76     pub(crate) fn user_ty(
  77         self,
  78         annotations: &mut CanonicalUserTypeAnnotations<'tcx>,
  79         inferred_ty: Ty<'tcx>,
  80         span: Span,
  81     ) -> UserTypeProjection {
  82         UserTypeProjection {
  83             base: annotations.push(CanonicalUserTypeAnnotation {
  84                 span,
  85                 user_ty: self.user_ty,
  86                 inferred_ty,
  87             }),
  88             projs: Vec::new(),
  89         }
  90     }
  91 }
  92
  93 #[derive(Copy, Clone, Debug, PartialEq)]
  94 crate struct Ascription<'tcx> {
  95     crate user_ty: PatTyProj<'tcx>,
  96     /// Variance to use when relating the type `user_ty` to the **type of the value being
  97     /// matched**. Typically, this is `Variance::Covariant`, since the value being matched must
  98     /// have a type that is some subtype of the ascribed type.
  99     ///
 100     /// Note that this variance does not apply for any bindings within subpatterns. The type
 101     /// assigned to those bindings must be exactly equal to the `user_ty` given here.
 102     ///
 103     /// The only place where this field is not `Covariant` is when matching constants, where
 104     /// we currently use `Contravariant` -- this is because the constant type just needs to
 105     /// be "comparable" to the type of the input value. So, for example:
 106     ///
 107     /// ```text
 108     /// match x { "foo" => .. }
 109     /// ```
 110     ///
 111     /// requires that `&'static str <: T_x`, where `T_x` is the type of `x`. Really, we should
 112     /// probably be checking for a `PartialEq` impl instead, but this preserves the behavior
 113     /// of the old type-check for now. See #57280 for details.
 114     crate variance: ty::Variance,
 115     crate user_ty_span: Span,
 116 }
 117
 118 #[derive(Clone, Debug)]
 119 crate enum PatKind<'tcx> {
 120     Wild,
 121
 122     AscribeUserType {
 123         ascription: Ascription<'tcx>,
 124         subpattern: Pat<'tcx>,
 125     },
 126
 127     /// `x`, `ref x`, `x @ P`, etc.
 128     Binding {
 129         mutability: Mutability,
 130         name: ast::Name,
 131         mode: BindingMode,
 132         var: hir::HirId,
 133         ty: Ty<'tcx>,
 134         subpattern: Option<Pat<'tcx>>,
 135     },
 136
 137     /// `Foo(...)` or `Foo{...}` or `Foo`, where `Foo` is a variant name from an ADT with
 138     /// multiple variants.
 139     Variant {
 140         adt_def: &'tcx AdtDef,
 141         substs: SubstsRef<'tcx>,
 142         variant_index: VariantIdx,
 143         subpatterns: Vec<FieldPat<'tcx>>,
 144     },
 145
 146     /// `(...)`, `Foo(...)`, `Foo{...}`, or `Foo`, where `Foo` is a variant name from an ADT with
 147     /// a single variant.
 148     Leaf {
 149         subpatterns: Vec<FieldPat<'tcx>>,
 150     },
 151
 152     /// `box P`, `&P`, `&mut P`, etc.
 153     Deref {
 154         subpattern: Pat<'tcx>,
 155     },
 156
 157     Constant {
 158         value: &'tcx ty::Const<'tcx>,
 159     },
 160
 161     Range(PatRange<'tcx>),
 162
 163     /// Matches against a slice, checking the length and extracting elements.
 164     /// irrefutable when there is a slice pattern and both `prefix` and `suffix` are empty.
 165     /// e.g., `&[ref xs @ ..]`.
 166     Slice {
 167         prefix: Vec<Pat<'tcx>>,
 168         slice: Option<Pat<'tcx>>,
 169         suffix: Vec<Pat<'tcx>>,
 170     },
 171
 172     /// Fixed match against an array; irrefutable.
 173     Array {
 174         prefix: Vec<Pat<'tcx>>,
 175         slice: Option<Pat<'tcx>>,
 176         suffix: Vec<Pat<'tcx>>,
 177     },
 178
 179     /// An or-pattern, e.g. `p | q`.
 180     /// Invariant: `pats.len() >= 2`.
 181     Or {
 182         pats: Vec<Pat<'tcx>>,
 183     },
 184 }
 185
 186 #[derive(Copy, Clone, Debug, PartialEq)]
 187 crate struct PatRange<'tcx> {
 188     crate lo: &'tcx ty::Const<'tcx>,
 189     crate hi: &'tcx ty::Const<'tcx>,
 190     crate end: RangeEnd,
 191 }
 192
 193 impl<'tcx> fmt::Display for Pat<'tcx> {
 194     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 195         // Printing lists is a chore.
 196         let mut first = true;
 197         let mut start_or_continue = |s| {
 198             if first {
 199                 first = false;
 200                 ""
 201             } else {
 202                 s
 203             }
 204         };
 205         let mut start_or_comma = || start_or_continue(", ");
 206
 207         match *self.kind {
 208             PatKind::Wild => write!(f, "_"),
 209             PatKind::AscribeUserType { ref subpattern, .. } => write!(f, "{}: _", subpattern),
 210             PatKind::Binding { mutability, name, mode, ref subpattern, .. } => {
 211                 let is_mut = match mode {
 212                     BindingMode::ByValue => mutability == Mutability::Mut,
 213                     BindingMode::ByRef(bk) => {
 214                         write!(f, "ref ")?;
 215                         match bk {
 216                             BorrowKind::Mut { .. } => true,
 217                             _ => false,
 218                         }
 219                     }
 220                 };
 221                 if is_mut {
 222                     write!(f, "mut ")?;
 223                 }
 224                 write!(f, "{}", name)?;
 225                 if let Some(ref subpattern) = *subpattern {
 226                     write!(f, " @ {}", subpattern)?;
 227                 }
 228                 Ok(())
 229             }
 230             PatKind::Variant { ref subpatterns, .. } | PatKind::Leaf { ref subpatterns } => {
 231                 let variant = match *self.kind {
 232                     PatKind::Variant { adt_def, variant_index, .. } => {
 233                         Some(&adt_def.variants[variant_index])
 234                     }
 235                     _ => {
 236                         if let ty::Adt(adt, _) = self.ty.kind {
 237                             if !adt.is_enum() {
 238                                 Some(&adt.variants[VariantIdx::new(0)])
 239                             } else {
 240                                 None
 241                             }
 242                         } else {
 243                             None
 244                         }
 245                     }
 246                 };
 247
 248                 if let Some(variant) = variant {
 249                     write!(f, "{}", variant.ident)?;
 250
 251                     // Only for Adt we can have `S {...}`,
 252                     // which we handle separately here.
 253                     if variant.ctor_kind == CtorKind::Fictive {
 254                         write!(f, " {{ ")?;
 255
 256                         let mut printed = 0;
 257                         for p in subpatterns {
 258                             if let PatKind::Wild = *p.pattern.kind {
 259                                 continue;
 260                             }
 261                             let name = variant.fields[p.field.index()].ident;
 262                             write!(f, "{}{}: {}", start_or_comma(), name, p.pattern)?;
 263                             printed += 1;
 264                         }
 265
 266                         if printed < variant.fields.len() {
 267                             write!(f, "{}..", start_or_comma())?;
 268                         }
 269
 270                         return write!(f, " }}");
 271                     }
 272                 }
 273
 274                 let num_fields = variant.map_or(subpatterns.len(), |v| v.fields.len());
 275                 if num_fields != 0 || variant.is_none() {
 276                     write!(f, "(")?;
 277                     for i in 0..num_fields {
 278                         write!(f, "{}", start_or_comma())?;
 279
 280                         // Common case: the field is where we expect it.
 281                         if let Some(p) = subpatterns.get(i) {
 282                             if p.field.index() == i {
 283                                 write!(f, "{}", p.pattern)?;
 284                                 continue;
 285                             }
 286                         }
 287
 288                         // Otherwise, we have to go looking for it.
 289                         if let Some(p) = subpatterns.iter().find(|p| p.field.index() == i) {
 290                             write!(f, "{}", p.pattern)?;
 291                         } else {
 292                             write!(f, "_")?;
 293                         }
 294                     }
 295                     write!(f, ")")?;
 296                 }
 297
 298                 Ok(())
 299             }
 300             PatKind::Deref { ref subpattern } => {
 301                 match self.ty.kind {
 302                     ty::Adt(def, _) if def.is_box() => write!(f, "box ")?,
 303                     ty::Ref(_, _, mutbl) => {
 304                         write!(f, "&{}", mutbl.prefix_str())?;
 305                     }
 306                     _ => bug!("{} is a bad Deref pattern type", self.ty),
 307                 }
 308                 write!(f, "{}", subpattern)
 309             }
 310             PatKind::Constant { value } => write!(f, "{}", value),
 311             PatKind::Range(PatRange { lo, hi, end }) => {
 312                 write!(f, "{}", lo)?;
 313                 write!(f, "{}", end)?;
 314                 write!(f, "{}", hi)
 315             }
 316             PatKind::Slice { ref prefix, ref slice, ref suffix }
 317             | PatKind::Array { ref prefix, ref slice, ref suffix } => {
 318                 write!(f, "[")?;
 319                 for p in prefix {
 320                     write!(f, "{}{}", start_or_comma(), p)?;
 321                 }
 322                 if let Some(ref slice) = *slice {
 323                     write!(f, "{}", start_or_comma())?;
 324                     match *slice.kind {
 325                         PatKind::Wild => {}
 326                         _ => write!(f, "{}", slice)?,
 327                     }
 328                     write!(f, "..")?;
 329                 }
 330                 for p in suffix {
 331                     write!(f, "{}{}", start_or_comma(), p)?;
 332                 }
 333                 write!(f, "]")
 334             }
 335             PatKind::Or { ref pats } => {
 336                 for pat in pats {
 337                     write!(f, "{}{}", start_or_continue(" | "), pat)?;
 338                 }
 339                 Ok(())
 340             }
 341         }
 342     }
 343 }
 344
 345 crate struct PatCtxt<'a, 'tcx> {
 346     crate tcx: TyCtxt<'tcx>,
 347     crate param_env: ty::ParamEnv<'tcx>,
 348     crate tables: &'a ty::TypeckTables<'tcx>,
 349     crate errors: Vec<PatternError>,
 350     include_lint_checks: bool,
 351 }
 352
 353 impl<'a, 'tcx> Pat<'tcx> {
 354     crate fn from_hir(
 355         tcx: TyCtxt<'tcx>,
 356         param_env: ty::ParamEnv<'tcx>,
 357         tables: &'a ty::TypeckTables<'tcx>,
 358         pat: &'tcx hir::Pat<'tcx>,
 359     ) -> Self {
 360         let mut pcx = PatCtxt::new(tcx, param_env, tables);
 361         let result = pcx.lower_pattern(pat);
 362         if !pcx.errors.is_empty() {
 363             let msg = format!("encountered errors lowering pattern: {:?}", pcx.errors);
 364             tcx.sess.delay_span_bug(pat.span, &msg);
 365         }
 366         debug!("Pat::from_hir({:?}) = {:?}", pat, result);
 367         result
 368     }
 369 }
 370
 371 impl<'a, 'tcx> PatCtxt<'a, 'tcx> {
 372     crate fn new(
 373         tcx: TyCtxt<'tcx>,
 374         param_env: ty::ParamEnv<'tcx>,
 375         tables: &'a ty::TypeckTables<'tcx>,
 376     ) -> Self {
 377         PatCtxt { tcx, param_env, tables, errors: vec![], include_lint_checks: false }
 378     }
 379
 380     crate fn include_lint_checks(&mut self) -> &mut Self {
 381         self.include_lint_checks = true;
 382         self
 383     }
 384
 385     crate fn lower_pattern(&mut self, pat: &'tcx hir::Pat<'tcx>) -> Pat<'tcx> {
 386         // When implicit dereferences have been inserted in this pattern, the unadjusted lowered
 387         // pattern has the type that results *after* dereferencing. For example, in this code:
 388         //
 389         // ```
 390         // match &&Some(0i32) {
 391         //     Some(n) => { ... },
 392         //     _ => { ... },
 393         // }
 394         // ```
 395         //
 396         // the type assigned to `Some(n)` in `unadjusted_pat` would be `Option<i32>` (this is
 397         // determined in rustc_typeck::check::match). The adjustments would be
 398         //
 399         // `vec![&&Option<i32>, &Option<i32>]`.
 400         //
 401         // Applying the adjustments, we want to instead output `&&Some(n)` (as a HAIR pattern). So
 402         // we wrap the unadjusted pattern in `PatKind::Deref` repeatedly, consuming the
 403         // adjustments in *reverse order* (last-in-first-out, so that the last `Deref` inserted
 404         // gets the least-dereferenced type).
 405         let unadjusted_pat = self.lower_pattern_unadjusted(pat);
 406         self.tables.pat_adjustments().get(pat.hir_id).unwrap_or(&vec![]).iter().rev().fold(
 407             unadjusted_pat,
 408             |pat, ref_ty| {
 409                 debug!("{:?}: wrapping pattern with type {:?}", pat, ref_ty);
 410                 Pat {
 411                     span: pat.span,
 412                     ty: ref_ty,
 413                     kind: Box::new(PatKind::Deref { subpattern: pat }),
 414                 }
 415             },
 416         )
 417     }
 418
 419     fn lower_range_expr(
 420         &mut self,
 421         expr: &'tcx hir::Expr<'tcx>,
 422     ) -> (PatKind<'tcx>, Option<Ascription<'tcx>>) {
 423         match self.lower_lit(expr) {
 424             PatKind::AscribeUserType { ascription, subpattern: Pat { kind: box kind, .. } } => {
 425                 (kind, Some(ascription))
 426             }
 427             kind => (kind, None),
 428         }
 429     }
 430
 431     fn lower_pattern_range(
 432         &mut self,
 433         ty: Ty<'tcx>,
 434         lo: &'tcx ty::Const<'tcx>,
 435         hi: &'tcx ty::Const<'tcx>,
 436         end: RangeEnd,
 437         span: Span,
 438     ) -> PatKind<'tcx> {
 439         assert_eq!(lo.ty, ty);
 440         assert_eq!(hi.ty, ty);
 441         let cmp = compare_const_vals(self.tcx, lo, hi, self.param_env, ty);
 442         match (end, cmp) {
 443             // `x..y` where `x < y`.
 444             // Non-empty because the range includes at least `x`.
 445             (RangeEnd::Excluded, Some(Ordering::Less)) => PatKind::Range(PatRange { lo, hi, end }),
 446             // `x..y` where `x >= y`. The range is empty => error.
 447             (RangeEnd::Excluded, _) => {
 448                 struct_span_err!(
 449                     self.tcx.sess,
 450                     span,
 451                     E0579,
 452                     "lower range bound must be less than upper"
 453                 )
 454                 .emit();
 455                 PatKind::Wild
 456             }
 457             // `x..=y` where `x == y`.
 458             (RangeEnd::Included, Some(Ordering::Equal)) => PatKind::Constant { value: lo },
 459             // `x..=y` where `x < y`.
 460             (RangeEnd::Included, Some(Ordering::Less)) => PatKind::Range(PatRange { lo, hi, end }),
 461             // `x..=y` where `x > y` hence the range is empty => error.
 462             (RangeEnd::Included, _) => {
 463                 let mut err = struct_span_err!(
 464                     self.tcx.sess,
 465                     span,
 466                     E0030,
 467                     "lower range bound must be less than or equal to upper"
 468                 );
 469                 err.span_label(span, "lower bound larger than upper bound");
 470                 if self.tcx.sess.teach(&err.get_code().unwrap()) {
 471                     err.note(
 472                         "When matching against a range, the compiler \
 473                               verifies that the range is non-empty. Range \
 474                               patterns include both end-points, so this is \
 475                               equivalent to requiring the start of the range \
 476                               to be less than or equal to the end of the range.",
 477                     );
 478                 }
 479                 err.emit();
 480                 PatKind::Wild
 481             }
 482         }
 483     }
 484
 485     fn normalize_range_pattern_ends(
 486         &self,
 487         ty: Ty<'tcx>,
 488         lo: Option<&PatKind<'tcx>>,
 489         hi: Option<&PatKind<'tcx>>,
 490     ) -> Option<(&'tcx ty::Const<'tcx>, &'tcx ty::Const<'tcx>)> {
 491         match (lo, hi) {
 492             (Some(PatKind::Constant { value: lo }), Some(PatKind::Constant { value: hi })) => {
 493                 Some((lo, hi))
 494             }
 495             (Some(PatKind::Constant { value: lo }), None) => {
 496                 Some((lo, ty.numeric_max_val(self.tcx)?))
 497             }
 498             (None, Some(PatKind::Constant { value: hi })) => {
 499                 Some((ty.numeric_min_val(self.tcx)?, hi))
 500             }
 501             _ => None,
 502         }
 503     }
 504
 505     fn lower_pattern_unadjusted(&mut self, pat: &'tcx hir::Pat<'tcx>) -> Pat<'tcx> {
 506         let mut ty = self.tables.node_type(pat.hir_id);
 507
 508         if let ty::Error = ty.kind {
 509             // Avoid ICEs (e.g., #50577 and #50585).
 510             return Pat { span: pat.span, ty, kind: Box::new(PatKind::Wild) };
 511         }
 512
 513         let kind = match pat.kind {
 514             hir::PatKind::Wild => PatKind::Wild,
 515
 516             hir::PatKind::Lit(ref value) => self.lower_lit(value),
 517
 518             hir::PatKind::Range(ref lo_expr, ref hi_expr, end) => {
 519                 let (lo_expr, hi_expr) = (lo_expr.as_deref(), hi_expr.as_deref());
 520                 let lo_span = lo_expr.map_or(pat.span, |e| e.span);
 521                 let lo = lo_expr.map(|e| self.lower_range_expr(e));
 522                 let hi = hi_expr.map(|e| self.lower_range_expr(e));
 523
 524                 let (lp, hp) = (lo.as_ref().map(|x| &x.0), hi.as_ref().map(|x| &x.0));
 525                 let mut kind = match self.normalize_range_pattern_ends(ty, lp, hp) {
 526                     Some((lc, hc)) => self.lower_pattern_range(ty, lc, hc, end, lo_span),
 527                     None => {
 528                         let msg = &format!(
 529                             "found bad range pattern `{:?}` outside of error recovery",
 530                             (&lo, &hi),
 531                         );
 532                         self.tcx.sess.delay_span_bug(pat.span, msg);
 533                         PatKind::Wild
 534                     }
 535                 };
 536
 537                 // If we are handling a range with associated constants (e.g.
 538                 // `Foo::<'a>::A..=Foo::B`), we need to put the ascriptions for the associated
 539                 // constants somewhere. Have them on the range pattern.
 540                 for end in &[lo, hi] {
 541                     if let Some((_, Some(ascription))) = end {
 542                         let subpattern = Pat { span: pat.span, ty, kind: Box::new(kind) };
 543                         kind = PatKind::AscribeUserType { ascription: *ascription, subpattern };
 544                     }
 545                 }
 546
 547                 kind
 548             }
 549
 550             hir::PatKind::Path(ref qpath) => {
 551                 return self.lower_path(qpath, pat.hir_id, pat.span);
 552             }
 553
 554             hir::PatKind::Ref(ref subpattern, _) | hir::PatKind::Box(ref subpattern) => {
 555                 PatKind::Deref { subpattern: self.lower_pattern(subpattern) }
 556             }
 557
 558             hir::PatKind::Slice(ref prefix, ref slice, ref suffix) => {
 559                 self.slice_or_array_pattern(pat.span, ty, prefix, slice, suffix)
 560             }
 561
 562             hir::PatKind::Tuple(ref pats, ddpos) => {
 563                 let tys = match ty.kind {
 564                     ty::Tuple(ref tys) => tys,
 565                     _ => span_bug!(pat.span, "unexpected type for tuple pattern: {:?}", ty),
 566                 };
 567                 let subpatterns = self.lower_tuple_subpats(pats, tys.len(), ddpos);
 568                 PatKind::Leaf { subpatterns }
 569             }
 570
 571             hir::PatKind::Binding(_, id, ident, ref sub) => {
 572                 let bm =
 573                     *self.tables.pat_binding_modes().get(pat.hir_id).expect("missing binding mode");
 574                 let (mutability, mode) = match bm {
 575                     ty::BindByValue(mutbl) => (mutbl, BindingMode::ByValue),
 576                     ty::BindByReference(hir::Mutability::Mut) => (
 577                         Mutability::Not,
 578                         BindingMode::ByRef(BorrowKind::Mut { allow_two_phase_borrow: false }),
 579                     ),
 580                     ty::BindByReference(hir::Mutability::Not) => {
 581                         (Mutability::Not, BindingMode::ByRef(BorrowKind::Shared))
 582                     }
 583                 };
 584
 585                 // A ref x pattern is the same node used for x, and as such it has
 586                 // x's type, which is &T, where we want T (the type being matched).
 587                 let var_ty = ty;
 588                 if let ty::BindByReference(_) = bm {
 589                     if let ty::Ref(_, rty, _) = ty.kind {
 590                         ty = rty;
 591                     } else {
 592                         bug!("`ref {}` has wrong type {}", ident, ty);
 593                     }
 594                 };
 595
 596                 PatKind::Binding {
 597                     mutability,
 598                     mode,
 599                     name: ident.name,
 600                     var: id,
 601                     ty: var_ty,
 602                     subpattern: self.lower_opt_pattern(sub),
 603                 }
 604             }
 605
 606             hir::PatKind::TupleStruct(ref qpath, ref pats, ddpos) => {
 607                 let res = self.tables.qpath_res(qpath, pat.hir_id);
 608                 let adt_def = match ty.kind {
 609                     ty::Adt(adt_def, _) => adt_def,
 610                     _ => span_bug!(pat.span, "tuple struct pattern not applied to an ADT {:?}", ty),
 611                 };
 612                 let variant_def = adt_def.variant_of_res(res);
 613                 let subpatterns = self.lower_tuple_subpats(pats, variant_def.fields.len(), ddpos);
 614                 self.lower_variant_or_leaf(res, pat.hir_id, pat.span, ty, subpatterns)
 615             }
 616
 617             hir::PatKind::Struct(ref qpath, ref fields, _) => {
 618                 let res = self.tables.qpath_res(qpath, pat.hir_id);
 619                 let subpatterns = fields
 620                     .iter()
 621                     .map(|field| FieldPat {
 622                         field: Field::new(self.tcx.field_index(field.hir_id, self.tables)),
 623                         pattern: self.lower_pattern(&field.pat),
 624                     })
 625                     .collect();
 626
 627                 self.lower_variant_or_leaf(res, pat.hir_id, pat.span, ty, subpatterns)
 628             }
 629
 630             hir::PatKind::Or(ref pats) => PatKind::Or { pats: self.lower_patterns(pats) },
 631         };
 632
 633         Pat { span: pat.span, ty, kind: Box::new(kind) }
 634     }
 635
 636     fn lower_tuple_subpats(
 637         &mut self,
 638         pats: &'tcx [&'tcx hir::Pat<'tcx>],
 639         expected_len: usize,
 640         gap_pos: Option<usize>,
 641     ) -> Vec<FieldPat<'tcx>> {
 642         pats.iter()
 643             .enumerate_and_adjust(expected_len, gap_pos)
 644             .map(|(i, subpattern)| FieldPat {
 645                 field: Field::new(i),
 646                 pattern: self.lower_pattern(subpattern),
 647             })
 648             .collect()
 649     }
 650
 651     fn lower_patterns(&mut self, pats: &'tcx [&'tcx hir::Pat<'tcx>]) -> Vec<Pat<'tcx>> {
 652         pats.iter().map(|p| self.lower_pattern(p)).collect()
 653     }
 654
 655     fn lower_opt_pattern(&mut self, pat: &'tcx Option<&'tcx hir::Pat<'tcx>>) -> Option<Pat<'tcx>> {
 656         pat.as_ref().map(|p| self.lower_pattern(p))
 657     }
 658
 659     fn slice_or_array_pattern(
 660         &mut self,
 661         span: Span,
 662         ty: Ty<'tcx>,
 663         prefix: &'tcx [&'tcx hir::Pat<'tcx>],
 664         slice: &'tcx Option<&'tcx hir::Pat<'tcx>>,
 665         suffix: &'tcx [&'tcx hir::Pat<'tcx>],
 666     ) -> PatKind<'tcx> {
 667         let prefix = self.lower_patterns(prefix);
 668         let slice = self.lower_opt_pattern(slice);
 669         let suffix = self.lower_patterns(suffix);
 670         match ty.kind {
 671             // Matching a slice, `[T]`.
 672             ty::Slice(..) => PatKind::Slice { prefix, slice, suffix },
 673             // Fixed-length array, `[T; len]`.
 674             ty::Array(_, len) => {
 675                 let len = len.eval_usize(self.tcx, self.param_env);
 676                 assert!(len >= prefix.len() as u64 + suffix.len() as u64);
 677                 PatKind::Array { prefix, slice, suffix }
 678             }
 679             _ => span_bug!(span, "bad slice pattern type {:?}", ty),
 680         }
 681     }
 682
 683     fn lower_variant_or_leaf(
 684         &mut self,
 685         res: Res,
 686         hir_id: hir::HirId,
 687         span: Span,
 688         ty: Ty<'tcx>,
 689         subpatterns: Vec<FieldPat<'tcx>>,
 690     ) -> PatKind<'tcx> {
 691         let res = match res {
 692             Res::Def(DefKind::Ctor(CtorOf::Variant, ..), variant_ctor_id) => {
 693                 let variant_id = self.tcx.parent(variant_ctor_id).unwrap();
 694                 Res::Def(DefKind::Variant, variant_id)
 695             }
 696             res => res,
 697         };
 698
 699         let mut kind = match res {
 700             Res::Def(DefKind::Variant, variant_id) => {
 701                 let enum_id = self.tcx.parent(variant_id).unwrap();
 702                 let adt_def = self.tcx.adt_def(enum_id);
 703                 if adt_def.is_enum() {
 704                     let substs = match ty.kind {
 705                         ty::Adt(_, substs) | ty::FnDef(_, substs) => substs,
 706                         ty::Error => {
 707                             // Avoid ICE (#50585)
 708                             return PatKind::Wild;
 709                         }
 710                         _ => bug!("inappropriate type for def: {:?}", ty),
 711                     };
 712                     PatKind::Variant {
 713                         adt_def,
 714                         substs,
 715                         variant_index: adt_def.variant_index_with_id(variant_id),
 716                         subpatterns,
 717                     }
 718                 } else {
 719                     PatKind::Leaf { subpatterns }
 720                 }
 721             }
 722
 723             Res::Def(DefKind::Struct, _)
 724             | Res::Def(DefKind::Ctor(CtorOf::Struct, ..), _)
 725             | Res::Def(DefKind::Union, _)
 726             | Res::Def(DefKind::TyAlias, _)
 727             | Res::Def(DefKind::AssocTy, _)
 728             | Res::SelfTy(..)
 729             | Res::SelfCtor(..) => PatKind::Leaf { subpatterns },
 730
 731             _ => {
 732                 self.errors.push(PatternError::NonConstPath(span));
 733                 PatKind::Wild
 734             }
 735         };
 736
 737         if let Some(user_ty) = self.user_substs_applied_to_ty_of_hir_id(hir_id) {
 738             debug!("lower_variant_or_leaf: kind={:?} user_ty={:?} span={:?}", kind, user_ty, span);
 739             kind = PatKind::AscribeUserType {
 740                 subpattern: Pat { span, ty, kind: Box::new(kind) },
 741                 ascription: Ascription {
 742                     user_ty: PatTyProj::from_user_type(user_ty),
 743                     user_ty_span: span,
 744                     variance: ty::Variance::Covariant,
 745                 },
 746             };
 747         }
 748
 749         kind
 750     }
 751
 752     /// Takes a HIR Path. If the path is a constant, evaluates it and feeds
 753     /// it to `const_to_pat`. Any other path (like enum variants without fields)
 754     /// is converted to the corresponding pattern via `lower_variant_or_leaf`.
 755     fn lower_path(&mut self, qpath: &hir::QPath<'_>, id: hir::HirId, span: Span) -> Pat<'tcx> {
 756         let ty = self.tables.node_type(id);
 757         let res = self.tables.qpath_res(qpath, id);
 758         let is_associated_const = match res {
 759             Res::Def(DefKind::AssocConst, _) => true,
 760             _ => false,
 761         };
 762         let kind = match res {
 763             Res::Def(DefKind::Const, def_id) | Res::Def(DefKind::AssocConst, def_id) => {
 764                 let substs = self.tables.node_substs(id);
 765                 // Use `Reveal::All` here because patterns are always monomorphic even if their function isn't.
 766                 match self.tcx.const_eval_resolve(
 767                     self.param_env.with_reveal_all(),
 768                     def_id,
 769                     substs,
 770                     None,
 771                     Some(span),
 772                 ) {
 773                     Ok(value) => {
 774                         let pattern = self.const_to_pat(value, id, span);
 775                         if !is_associated_const {
 776                             return pattern;
 777                         }
 778
 779                         let user_provided_types = self.tables().user_provided_types();
 780                         return if let Some(u_ty) = user_provided_types.get(id) {
 781                             let user_ty = PatTyProj::from_user_type(*u_ty);
 782                             Pat {
 783                                 span,
 784                                 kind: Box::new(PatKind::AscribeUserType {
 785                                     subpattern: pattern,
 786                                     ascription: Ascription {
 787                                         /// Note that use `Contravariant` here. See the
 788                                         /// `variance` field documentation for details.
 789                                         variance: ty::Variance::Contravariant,
 790                                         user_ty,
 791                                         user_ty_span: span,
 792                                     },
 793                                 }),
 794                                 ty: value.ty,
 795                             }
 796                         } else {
 797                             pattern
 798                         };
 799                     }
 800                     Err(ErrorHandled::TooGeneric) => {
 801                         self.errors.push(if is_associated_const {
 802                             PatternError::AssocConstInPattern(span)
 803                         } else {
 804                             PatternError::StaticInPattern(span)
 805                         });
 806                         PatKind::Wild
 807                     }
 808                     Err(_) => {
 809                         self.tcx.sess.span_err(span, "could not evaluate constant pattern");
 810                         PatKind::Wild
 811                     }
 812                 }
 813             }
 814             _ => self.lower_variant_or_leaf(res, id, span, ty, vec![]),
 815         };
 816
 817         Pat { span, ty, kind: Box::new(kind) }
 818     }
 819
 820     /// Converts literals, paths and negation of literals to patterns.
 821     /// The special case for negation exists to allow things like `-128_i8`
 822     /// which would overflow if we tried to evaluate `128_i8` and then negate
 823     /// afterwards.
 824     fn lower_lit(&mut self, expr: &'tcx hir::Expr<'tcx>) -> PatKind<'tcx> {
 825         if let hir::ExprKind::Path(ref qpath) = expr.kind {
 826             *self.lower_path(qpath, expr.hir_id, expr.span).kind
 827         } else {
 828             let (lit, neg) = match expr.kind {
 829                 hir::ExprKind::Lit(ref lit) => (lit, false),
 830                 hir::ExprKind::Unary(hir::UnOp::UnNeg, ref expr) => {
 831                     let lit = match expr.kind {
 832                         hir::ExprKind::Lit(ref lit) => lit,
 833                         _ => span_bug!(expr.span, "not a literal: {:?}", expr),
 834                     };
 835                     (lit, true)
 836                 }
 837                 _ => span_bug!(expr.span, "not a literal: {:?}", expr),
 838             };
 839
 840             let lit_input = LitToConstInput { lit: &lit.node, ty: self.tables.expr_ty(expr), neg };
 841             match self.tcx.at(expr.span).lit_to_const(lit_input) {
 842                 Ok(val) => *self.const_to_pat(val, expr.hir_id, lit.span).kind,
 843                 Err(LitToConstError::UnparseableFloat) => {
 844                     self.errors.push(PatternError::FloatBug);
 845                     PatKind::Wild
 846                 }
 847                 Err(LitToConstError::Reported) => PatKind::Wild,
 848             }
 849         }
 850     }
 851 }
 852
 853 impl<'tcx> UserAnnotatedTyHelpers<'tcx> for PatCtxt<'_, 'tcx> {
 854     fn tcx(&self) -> TyCtxt<'tcx> {
 855         self.tcx
 856     }
 857
 858     fn tables(&self) -> &ty::TypeckTables<'tcx> {
 859         self.tables
 860     }
 861 }
 862
 863 crate trait PatternFoldable<'tcx>: Sized {
 864     fn fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
 865         self.super_fold_with(folder)
 866     }
 867
 868     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self;
 869 }
 870
 871 crate trait PatternFolder<'tcx>: Sized {
 872     fn fold_pattern(&mut self, pattern: &Pat<'tcx>) -> Pat<'tcx> {
 873         pattern.super_fold_with(self)
 874     }
 875
 876     fn fold_pattern_kind(&mut self, kind: &PatKind<'tcx>) -> PatKind<'tcx> {
 877         kind.super_fold_with(self)
 878     }
 879 }
 880
 881 impl<'tcx, T: PatternFoldable<'tcx>> PatternFoldable<'tcx> for Box<T> {
 882     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
 883         let content: T = (**self).fold_with(folder);
 884         box content
 885     }
 886 }
 887
 888 impl<'tcx, T: PatternFoldable<'tcx>> PatternFoldable<'tcx> for Vec<T> {
 889     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
 890         self.iter().map(|t| t.fold_with(folder)).collect()
 891     }
 892 }
 893
 894 impl<'tcx, T: PatternFoldable<'tcx>> PatternFoldable<'tcx> for Option<T> {
 895     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
 896         self.as_ref().map(|t| t.fold_with(folder))
 897     }
 898 }
 899
 900 macro_rules! CloneImpls {
 901     (<$lt_tcx:tt> $($ty:ty),+) => {
 902         $(
 903             impl<$lt_tcx> PatternFoldable<$lt_tcx> for $ty {
 904                 fn super_fold_with<F: PatternFolder<$lt_tcx>>(&self, _: &mut F) -> Self {
 905                     Clone::clone(self)
 906                 }
 907             }
 908         )+
 909     }
 910 }
 911
 912 CloneImpls! { <'tcx>
 913     Span, Field, Mutability, ast::Name, hir::HirId, usize, ty::Const<'tcx>,
 914     Region<'tcx>, Ty<'tcx>, BindingMode, &'tcx AdtDef,
 915     SubstsRef<'tcx>, &'tcx GenericArg<'tcx>, UserType<'tcx>,
 916     UserTypeProjection, PatTyProj<'tcx>
 917 }
 918
 919 impl<'tcx> PatternFoldable<'tcx> for FieldPat<'tcx> {
 920     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
 921         FieldPat { field: self.field.fold_with(folder), pattern: self.pattern.fold_with(folder) }
 922     }
 923 }
 924
 925 impl<'tcx> PatternFoldable<'tcx> for Pat<'tcx> {
 926     fn fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
 927         folder.fold_pattern(self)
 928     }
 929
 930     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
 931         Pat {
 932             ty: self.ty.fold_with(folder),
 933             span: self.span.fold_with(folder),
 934             kind: self.kind.fold_with(folder),
 935         }
 936     }
 937 }
 938
 939 impl<'tcx> PatternFoldable<'tcx> for PatKind<'tcx> {
 940     fn fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
 941         folder.fold_pattern_kind(self)
 942     }
 943
 944     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
 945         match *self {
 946             PatKind::Wild => PatKind::Wild,
 947             PatKind::AscribeUserType {
 948                 ref subpattern,
 949                 ascription: Ascription { variance, ref user_ty, user_ty_span },
 950             } => PatKind::AscribeUserType {
 951                 subpattern: subpattern.fold_with(folder),
 952                 ascription: Ascription {
 953                     user_ty: user_ty.fold_with(folder),
 954                     variance,
 955                     user_ty_span,
 956                 },
 957             },
 958             PatKind::Binding { mutability, name, mode, var, ty, ref subpattern } => {
 959                 PatKind::Binding {
 960                     mutability: mutability.fold_with(folder),
 961                     name: name.fold_with(folder),
 962                     mode: mode.fold_with(folder),
 963                     var: var.fold_with(folder),
 964                     ty: ty.fold_with(folder),
 965                     subpattern: subpattern.fold_with(folder),
 966                 }
 967             }
 968             PatKind::Variant { adt_def, substs, variant_index, ref subpatterns } => {
 969                 PatKind::Variant {
 970                     adt_def: adt_def.fold_with(folder),
 971                     substs: substs.fold_with(folder),
 972                     variant_index,
 973                     subpatterns: subpatterns.fold_with(folder),
 974                 }
 975             }
 976             PatKind::Leaf { ref subpatterns } => {
 977                 PatKind::Leaf { subpatterns: subpatterns.fold_with(folder) }
 978             }
 979             PatKind::Deref { ref subpattern } => {
 980                 PatKind::Deref { subpattern: subpattern.fold_with(folder) }
 981             }
 982             PatKind::Constant { value } => PatKind::Constant { value },
 983             PatKind::Range(range) => PatKind::Range(range),
 984             PatKind::Slice { ref prefix, ref slice, ref suffix } => PatKind::Slice {
 985                 prefix: prefix.fold_with(folder),
 986                 slice: slice.fold_with(folder),
 987                 suffix: suffix.fold_with(folder),
 988             },
 989             PatKind::Array { ref prefix, ref slice, ref suffix } => PatKind::Array {
 990                 prefix: prefix.fold_with(folder),
 991                 slice: slice.fold_with(folder),
 992                 suffix: suffix.fold_with(folder),
 993             },
 994             PatKind::Or { ref pats } => PatKind::Or { pats: pats.fold_with(folder) },
 995         }
 996     }
 997 }
 998
 999 crate fn compare_const_vals<'tcx>(
1000     tcx: TyCtxt<'tcx>,
1001     a: &'tcx ty::Const<'tcx>,
1002     b: &'tcx ty::Const<'tcx>,
1003     param_env: ty::ParamEnv<'tcx>,
1004     ty: Ty<'tcx>,
1005 ) -> Option<Ordering> {
1006     trace!("compare_const_vals: {:?}, {:?}", a, b);
1007
1008     let from_bool = |v: bool| v.then_some(Ordering::Equal);
1009
1010     let fallback = || from_bool(a == b);
1011
1012     // Use the fallback if any type differs
1013     if a.ty != b.ty || a.ty != ty {
1014         return fallback();
1015     }
1016
1017     // Early return for equal constants (so e.g. references to ZSTs can be compared, even if they
1018     // are just integer addresses).
1019     if a.val == b.val {
1020         return from_bool(true);
1021     }
1022
1023     let a_bits = a.try_eval_bits(tcx, param_env, ty);
1024     let b_bits = b.try_eval_bits(tcx, param_env, ty);
1025
1026     if let (Some(a), Some(b)) = (a_bits, b_bits) {
1027         use ::rustc_apfloat::Float;
1028         return match ty.kind {
1029             ty::Float(ast::FloatTy::F32) => {
1030                 let l = ::rustc_apfloat::ieee::Single::from_bits(a);
1031                 let r = ::rustc_apfloat::ieee::Single::from_bits(b);
1032                 l.partial_cmp(&r)
1033             }
1034             ty::Float(ast::FloatTy::F64) => {
1035                 let l = ::rustc_apfloat::ieee::Double::from_bits(a);
1036                 let r = ::rustc_apfloat::ieee::Double::from_bits(b);
1037                 l.partial_cmp(&r)
1038             }
1039             ty::Int(ity) => {
1040                 use rustc::ty::layout::{Integer, IntegerExt};
1041                 use syntax::attr::SignedInt;
1042                 let size = Integer::from_attr(&tcx, SignedInt(ity)).size();
1043                 let a = sign_extend(a, size);
1044                 let b = sign_extend(b, size);
1045                 Some((a as i128).cmp(&(b as i128)))
1046             }
1047             _ => Some(a.cmp(&b)),
1048         };
1049     }
1050
1051     if let ty::Str = ty.kind {
1052         match (a.val, b.val) {
1053             (
1054                 ty::ConstKind::Value(a_val @ ConstValue::Slice { .. }),
1055                 ty::ConstKind::Value(b_val @ ConstValue::Slice { .. }),
1056             ) => {
1057                 let a_bytes = get_slice_bytes(&tcx, a_val);
1058                 let b_bytes = get_slice_bytes(&tcx, b_val);
1059                 return from_bool(a_bytes == b_bytes);
1060             }
1061             _ => (),
1062         }
1063     }
1064
1065     fallback()
1066 }