src/librustc_mir/hair/pattern/mod.rs

   1 //! Validation of patterns/matches.
   2
   3 mod _match;
   4 mod check_match;
   5
   6 pub(crate) use self::check_match::check_match;
   7
   8 use crate::const_eval::const_variant_index;
   9
  10 use crate::hair::util::UserAnnotatedTyHelpers;
  11 use crate::hair::constant::*;
  12
  13 use rustc::lint;
  14 use rustc::mir::{Field, BorrowKind, Mutability};
  15 use rustc::mir::{UserTypeProjection};
  16 use rustc::mir::interpret::{GlobalId, ConstValue, sign_extend, AllocId, Pointer};
  17 use rustc::traits::{ObligationCause, PredicateObligation};
  18 use rustc::ty::{self, Region, TyCtxt, AdtDef, Ty, UserType, DefIdTree};
  19 use rustc::ty::{CanonicalUserType, CanonicalUserTypeAnnotation, CanonicalUserTypeAnnotations};
  20 use rustc::ty::subst::{SubstsRef, Kind};
  21 use rustc::ty::layout::{VariantIdx, Size};
  22 use rustc::hir::{self, PatKind, RangeEnd};
  23 use rustc::hir::def::{CtorOf, Res, DefKind, CtorKind};
  24 use rustc::hir::pat_util::EnumerateAndAdjustIterator;
  25 use rustc::hir::ptr::P;
  26
  27 use rustc_data_structures::indexed_vec::Idx;
  28 use rustc_data_structures::fx::FxHashSet;
  29
  30 use std::cmp::Ordering;
  31 use std::fmt;
  32 use syntax::ast;
  33 use syntax::symbol::sym;
  34 use syntax_pos::Span;
  35
  36 #[derive(Clone, Debug)]
  37 pub enum PatternError {
  38     AssocConstInPattern(Span),
  39     StaticInPattern(Span),
  40     FloatBug,
  41     NonConstPath(Span),
  42 }
  43
  44 #[derive(Copy, Clone, Debug)]
  45 pub enum BindingMode {
  46     ByValue,
  47     ByRef(BorrowKind),
  48 }
  49
  50 #[derive(Clone, Debug)]
  51 pub struct FieldPattern<'tcx> {
  52     pub field: Field,
  53     pub pattern: Pattern<'tcx>,
  54 }
  55
  56 #[derive(Clone, Debug)]
  57 pub struct Pattern<'tcx> {
  58     pub ty: Ty<'tcx>,
  59     pub span: Span,
  60     pub kind: Box<PatternKind<'tcx>>,
  61 }
  62
  63
  64 #[derive(Copy, Clone, Debug, PartialEq)]
  65 pub struct PatternTypeProjection<'tcx> {
  66     pub user_ty: CanonicalUserType<'tcx>,
  67 }
  68
  69 impl<'tcx> PatternTypeProjection<'tcx> {
  70     pub(crate) fn from_user_type(user_annotation: CanonicalUserType<'tcx>) -> Self {
  71         Self {
  72             user_ty: user_annotation,
  73         }
  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 pub struct Ascription<'tcx> {
  95     pub user_ty: PatternTypeProjection<'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     pub variance: ty::Variance,
 115     pub user_ty_span: Span,
 116 }
 117
 118 #[derive(Clone, Debug)]
 119 pub enum PatternKind<'tcx> {
 120     Wild,
 121
 122     AscribeUserType {
 123         ascription: Ascription<'tcx>,
 124         subpattern: Pattern<'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<Pattern<'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<FieldPattern<'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<FieldPattern<'tcx>>,
 150     },
 151
 152     /// `box P`, `&P`, `&mut P`, etc.
 153     Deref {
 154         subpattern: Pattern<'tcx>,
 155     },
 156
 157     Constant {
 158         value: &'tcx ty::Const<'tcx>,
 159     },
 160
 161     Range(PatternRange<'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<Pattern<'tcx>>,
 168         slice: Option<Pattern<'tcx>>,
 169         suffix: Vec<Pattern<'tcx>>,
 170     },
 171
 172     /// Fixed match against an array; irrefutable.
 173     Array {
 174         prefix: Vec<Pattern<'tcx>>,
 175         slice: Option<Pattern<'tcx>>,
 176         suffix: Vec<Pattern<'tcx>>,
 177     },
 178 }
 179
 180 #[derive(Copy, Clone, Debug, PartialEq)]
 181 pub struct PatternRange<'tcx> {
 182     pub lo: &'tcx ty::Const<'tcx>,
 183     pub hi: &'tcx ty::Const<'tcx>,
 184     pub ty: Ty<'tcx>,
 185     pub end: RangeEnd,
 186 }
 187
 188 impl<'tcx> fmt::Display for Pattern<'tcx> {
 189     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 190         match *self.kind {
 191             PatternKind::Wild => write!(f, "_"),
 192             PatternKind::AscribeUserType { ref subpattern, .. } =>
 193                 write!(f, "{}: _", subpattern),
 194             PatternKind::Binding { mutability, name, mode, ref subpattern, .. } => {
 195                 let is_mut = match mode {
 196                     BindingMode::ByValue => mutability == Mutability::Mut,
 197                     BindingMode::ByRef(bk) => {
 198                         write!(f, "ref ")?;
 199                         match bk { BorrowKind::Mut { .. } => true, _ => false }
 200                     }
 201                 };
 202                 if is_mut {
 203                     write!(f, "mut ")?;
 204                 }
 205                 write!(f, "{}", name)?;
 206                 if let Some(ref subpattern) = *subpattern {
 207                     write!(f, " @ {}", subpattern)?;
 208                 }
 209                 Ok(())
 210             }
 211             PatternKind::Variant { ref subpatterns, .. } |
 212             PatternKind::Leaf { ref subpatterns } => {
 213                 let variant = match *self.kind {
 214                     PatternKind::Variant { adt_def, variant_index, .. } => {
 215                         Some(&adt_def.variants[variant_index])
 216                     }
 217                     _ => if let ty::Adt(adt, _) = self.ty.sty {
 218                         if !adt.is_enum() {
 219                             Some(&adt.variants[VariantIdx::new(0)])
 220                         } else {
 221                             None
 222                         }
 223                     } else {
 224                         None
 225                     }
 226                 };
 227
 228                 let mut first = true;
 229                 let mut start_or_continue = || if first { first = false; "" } else { ", " };
 230
 231                 if let Some(variant) = variant {
 232                     write!(f, "{}", variant.ident)?;
 233
 234                     // Only for Adt we can have `S {...}`,
 235                     // which we handle separately here.
 236                     if variant.ctor_kind == CtorKind::Fictive {
 237                         write!(f, " {{ ")?;
 238
 239                         let mut printed = 0;
 240                         for p in subpatterns {
 241                             if let PatternKind::Wild = *p.pattern.kind {
 242                                 continue;
 243                             }
 244                             let name = variant.fields[p.field.index()].ident;
 245                             write!(f, "{}{}: {}", start_or_continue(), name, p.pattern)?;
 246                             printed += 1;
 247                         }
 248
 249                         if printed < variant.fields.len() {
 250                             write!(f, "{}..", start_or_continue())?;
 251                         }
 252
 253                         return write!(f, " }}");
 254                     }
 255                 }
 256
 257                 let num_fields = variant.map_or(subpatterns.len(), |v| v.fields.len());
 258                 if num_fields != 0 || variant.is_none() {
 259                     write!(f, "(")?;
 260                     for i in 0..num_fields {
 261                         write!(f, "{}", start_or_continue())?;
 262
 263                         // Common case: the field is where we expect it.
 264                         if let Some(p) = subpatterns.get(i) {
 265                             if p.field.index() == i {
 266                                 write!(f, "{}", p.pattern)?;
 267                                 continue;
 268                             }
 269                         }
 270
 271                         // Otherwise, we have to go looking for it.
 272                         if let Some(p) = subpatterns.iter().find(|p| p.field.index() == i) {
 273                             write!(f, "{}", p.pattern)?;
 274                         } else {
 275                             write!(f, "_")?;
 276                         }
 277                     }
 278                     write!(f, ")")?;
 279                 }
 280
 281                 Ok(())
 282             }
 283             PatternKind::Deref { ref subpattern } => {
 284                 match self.ty.sty {
 285                     ty::Adt(def, _) if def.is_box() => write!(f, "box ")?,
 286                     ty::Ref(_, _, mutbl) => {
 287                         write!(f, "&")?;
 288                         if mutbl == hir::MutMutable {
 289                             write!(f, "mut ")?;
 290                         }
 291                     }
 292                     _ => bug!("{} is a bad Deref pattern type", self.ty)
 293                 }
 294                 write!(f, "{}", subpattern)
 295             }
 296             PatternKind::Constant { value } => {
 297                 write!(f, "{}", value)
 298             }
 299             PatternKind::Range(PatternRange { lo, hi, ty: _, end }) => {
 300                 write!(f, "{}", lo)?;
 301                 match end {
 302                     RangeEnd::Included => write!(f, "..=")?,
 303                     RangeEnd::Excluded => write!(f, "..")?,
 304                 }
 305                 write!(f, "{}", hi)
 306             }
 307             PatternKind::Slice { ref prefix, ref slice, ref suffix } |
 308             PatternKind::Array { ref prefix, ref slice, ref suffix } => {
 309                 let mut first = true;
 310                 let mut start_or_continue = || if first { first = false; "" } else { ", " };
 311                 write!(f, "[")?;
 312                 for p in prefix {
 313                     write!(f, "{}{}", start_or_continue(), p)?;
 314                 }
 315                 if let Some(ref slice) = *slice {
 316                     write!(f, "{}", start_or_continue())?;
 317                     match *slice.kind {
 318                         PatternKind::Wild => {}
 319                         _ => write!(f, "{}", slice)?
 320                     }
 321                     write!(f, "..")?;
 322                 }
 323                 for p in suffix {
 324                     write!(f, "{}{}", start_or_continue(), p)?;
 325                 }
 326                 write!(f, "]")
 327             }
 328         }
 329     }
 330 }
 331
 332 pub struct PatternContext<'a, 'tcx> {
 333     pub tcx: TyCtxt<'tcx>,
 334     pub param_env: ty::ParamEnv<'tcx>,
 335     pub tables: &'a ty::TypeckTables<'tcx>,
 336     pub substs: SubstsRef<'tcx>,
 337     pub errors: Vec<PatternError>,
 338     include_lint_checks: bool,
 339 }
 340
 341 impl<'a, 'tcx> Pattern<'tcx> {
 342     pub fn from_hir(
 343         tcx: TyCtxt<'tcx>,
 344         param_env_and_substs: ty::ParamEnvAnd<'tcx, SubstsRef<'tcx>>,
 345         tables: &'a ty::TypeckTables<'tcx>,
 346         pat: &'tcx hir::Pat,
 347     ) -> Self {
 348         let mut pcx = PatternContext::new(tcx, param_env_and_substs, tables);
 349         let result = pcx.lower_pattern(pat);
 350         if !pcx.errors.is_empty() {
 351             let msg = format!("encountered errors lowering pattern: {:?}", pcx.errors);
 352             tcx.sess.delay_span_bug(pat.span, &msg);
 353         }
 354         debug!("Pattern::from_hir({:?}) = {:?}", pat, result);
 355         result
 356     }
 357 }
 358
 359 impl<'a, 'tcx> PatternContext<'a, 'tcx> {
 360     pub fn new(
 361         tcx: TyCtxt<'tcx>,
 362         param_env_and_substs: ty::ParamEnvAnd<'tcx, SubstsRef<'tcx>>,
 363         tables: &'a ty::TypeckTables<'tcx>,
 364     ) -> Self {
 365         PatternContext {
 366             tcx,
 367             param_env: param_env_and_substs.param_env,
 368             tables,
 369             substs: param_env_and_substs.value,
 370             errors: vec![],
 371             include_lint_checks: false,
 372         }
 373     }
 374
 375     pub fn include_lint_checks(&mut self) -> &mut Self {
 376         self.include_lint_checks = true;
 377         self
 378     }
 379
 380     pub fn lower_pattern(&mut self, pat: &'tcx hir::Pat) -> Pattern<'tcx> {
 381         // When implicit dereferences have been inserted in this pattern, the unadjusted lowered
 382         // pattern has the type that results *after* dereferencing. For example, in this code:
 383         //
 384         // ```
 385         // match &&Some(0i32) {
 386         //     Some(n) => { ... },
 387         //     _ => { ... },
 388         // }
 389         // ```
 390         //
 391         // the type assigned to `Some(n)` in `unadjusted_pat` would be `Option<i32>` (this is
 392         // determined in rustc_typeck::check::match). The adjustments would be
 393         //
 394         // `vec![&&Option<i32>, &Option<i32>]`.
 395         //
 396         // Applying the adjustments, we want to instead output `&&Some(n)` (as a HAIR pattern). So
 397         // we wrap the unadjusted pattern in `PatternKind::Deref` repeatedly, consuming the
 398         // adjustments in *reverse order* (last-in-first-out, so that the last `Deref` inserted
 399         // gets the least-dereferenced type).
 400         let unadjusted_pat = self.lower_pattern_unadjusted(pat);
 401         self.tables
 402             .pat_adjustments()
 403             .get(pat.hir_id)
 404             .unwrap_or(&vec![])
 405             .iter()
 406             .rev()
 407             .fold(unadjusted_pat, |pat, ref_ty| {
 408                     debug!("{:?}: wrapping pattern with type {:?}", pat, ref_ty);
 409                     Pattern {
 410                         span: pat.span,
 411                         ty: ref_ty,
 412                         kind: Box::new(PatternKind::Deref { subpattern: pat }),
 413                     }
 414                 },
 415             )
 416     }
 417
 418     fn lower_range_expr(
 419         &mut self,
 420         expr: &'tcx hir::Expr,
 421     ) -> (PatternKind<'tcx>, Option<Ascription<'tcx>>) {
 422         match self.lower_lit(expr) {
 423             PatternKind::AscribeUserType {
 424                 ascription: lo_ascription,
 425                 subpattern: Pattern { kind: box kind, .. },
 426             } => (kind, Some(lo_ascription)),
 427             kind => (kind, None),
 428         }
 429     }
 430
 431     fn lower_pattern_unadjusted(&mut self, pat: &'tcx hir::Pat) -> Pattern<'tcx> {
 432         let mut ty = self.tables.node_type(pat.hir_id);
 433
 434         let kind = match pat.node {
 435             PatKind::Wild => PatternKind::Wild,
 436
 437             PatKind::Lit(ref value) => self.lower_lit(value),
 438
 439             PatKind::Range(ref lo_expr, ref hi_expr, end) => {
 440                 let (lo, lo_ascription) = self.lower_range_expr(lo_expr);
 441                 let (hi, hi_ascription) = self.lower_range_expr(hi_expr);
 442
 443                 let mut kind = match (lo, hi) {
 444                     (PatternKind::Constant { value: lo }, PatternKind::Constant { value: hi }) => {
 445                         let cmp = compare_const_vals(
 446                             self.tcx,
 447                             lo,
 448                             hi,
 449                             self.param_env,
 450                             ty,
 451                         );
 452                         match (end, cmp) {
 453                             (RangeEnd::Excluded, Some(Ordering::Less)) =>
 454                                 PatternKind::Range(PatternRange { lo, hi, ty, end }),
 455                             (RangeEnd::Excluded, _) => {
 456                                 span_err!(
 457                                     self.tcx.sess,
 458                                     lo_expr.span,
 459                                     E0579,
 460                                     "lower range bound must be less than upper",
 461                                 );
 462                                 PatternKind::Wild
 463                             }
 464                             (RangeEnd::Included, Some(Ordering::Equal)) => {
 465                                 PatternKind::Constant { value: lo }
 466                             }
 467                             (RangeEnd::Included, Some(Ordering::Less)) => {
 468                                 PatternKind::Range(PatternRange { lo, hi, ty, end })
 469                             }
 470                             (RangeEnd::Included, _) => {
 471                                 let mut err = struct_span_err!(
 472                                     self.tcx.sess,
 473                                     lo_expr.span,
 474                                     E0030,
 475                                     "lower range bound must be less than or equal to upper"
 476                                 );
 477                                 err.span_label(
 478                                     lo_expr.span,
 479                                     "lower bound larger than upper bound",
 480                                 );
 481                                 if self.tcx.sess.teach(&err.get_code().unwrap()) {
 482                                     err.note("When matching against a range, the compiler \
 483                                               verifies that the range is non-empty. Range \
 484                                               patterns include both end-points, so this is \
 485                                               equivalent to requiring the start of the range \
 486                                               to be less than or equal to the end of the range.");
 487                                 }
 488                                 err.emit();
 489                                 PatternKind::Wild
 490                             }
 491                         }
 492                     },
 493                     ref pats => {
 494                         self.tcx.sess.delay_span_bug(
 495                             pat.span,
 496                             &format!(
 497                                 "found bad range pattern `{:?}` outside of error recovery",
 498                                 pats,
 499                             ),
 500                         );
 501
 502                         PatternKind::Wild
 503                     },
 504                 };
 505
 506                 // If we are handling a range with associated constants (e.g.
 507                 // `Foo::<'a>::A..=Foo::B`), we need to put the ascriptions for the associated
 508                 // constants somewhere. Have them on the range pattern.
 509                 for ascription in &[lo_ascription, hi_ascription] {
 510                     if let Some(ascription) = ascription {
 511                         kind = PatternKind::AscribeUserType {
 512                             ascription: *ascription,
 513                             subpattern: Pattern { span: pat.span, ty, kind: Box::new(kind), },
 514                         };
 515                     }
 516                 }
 517
 518                 kind
 519             }
 520
 521             PatKind::Path(ref qpath) => {
 522                 return self.lower_path(qpath, pat.hir_id, pat.span);
 523             }
 524
 525             PatKind::Ref(ref subpattern, _) |
 526             PatKind::Box(ref subpattern) => {
 527                 PatternKind::Deref { subpattern: self.lower_pattern(subpattern) }
 528             }
 529
 530             PatKind::Slice(ref prefix, ref slice, ref suffix) => {
 531                 match ty.sty {
 532                     ty::Ref(_, ty, _) =>
 533                         PatternKind::Deref {
 534                             subpattern: Pattern {
 535                                 ty,
 536                                 span: pat.span,
 537                                 kind: Box::new(self.slice_or_array_pattern(
 538                                     pat.span, ty, prefix, slice, suffix))
 539                             },
 540                         },
 541                     ty::Slice(..) |
 542                     ty::Array(..) =>
 543                         self.slice_or_array_pattern(pat.span, ty, prefix, slice, suffix),
 544                     ty::Error => { // Avoid ICE
 545                         return Pattern { span: pat.span, ty, kind: Box::new(PatternKind::Wild) };
 546                     }
 547                     _ =>
 548                         span_bug!(
 549                             pat.span,
 550                             "unexpanded type for vector pattern: {:?}",
 551                             ty),
 552                 }
 553             }
 554
 555             PatKind::Tuple(ref subpatterns, ddpos) => {
 556                 match ty.sty {
 557                     ty::Tuple(ref tys) => {
 558                         let subpatterns =
 559                             subpatterns.iter()
 560                                        .enumerate_and_adjust(tys.len(), ddpos)
 561                                        .map(|(i, subpattern)| FieldPattern {
 562                                             field: Field::new(i),
 563                                             pattern: self.lower_pattern(subpattern)
 564                                        })
 565                                        .collect();
 566
 567                         PatternKind::Leaf { subpatterns }
 568                     }
 569                     ty::Error => { // Avoid ICE (#50577)
 570                         return Pattern { span: pat.span, ty, kind: Box::new(PatternKind::Wild) };
 571                     }
 572                     _ => span_bug!(pat.span, "unexpected type for tuple pattern: {:?}", ty),
 573                 }
 574             }
 575
 576             PatKind::Binding(_, id, ident, ref sub) => {
 577                 let var_ty = self.tables.node_type(pat.hir_id);
 578                 if let ty::Error = var_ty.sty {
 579                     // Avoid ICE
 580                     return Pattern { span: pat.span, ty, kind: Box::new(PatternKind::Wild) };
 581                 };
 582                 let bm = *self.tables.pat_binding_modes().get(pat.hir_id)
 583                                                          .expect("missing binding mode");
 584                 let (mutability, mode) = match bm {
 585                     ty::BindByValue(hir::MutMutable) =>
 586                         (Mutability::Mut, BindingMode::ByValue),
 587                     ty::BindByValue(hir::MutImmutable) =>
 588                         (Mutability::Not, BindingMode::ByValue),
 589                     ty::BindByReference(hir::MutMutable) =>
 590                         (Mutability::Not, BindingMode::ByRef(
 591                             BorrowKind::Mut { allow_two_phase_borrow: false })),
 592                     ty::BindByReference(hir::MutImmutable) =>
 593                         (Mutability::Not, BindingMode::ByRef(
 594                             BorrowKind::Shared)),
 595                 };
 596
 597                 // A ref x pattern is the same node used for x, and as such it has
 598                 // x's type, which is &T, where we want T (the type being matched).
 599                 if let ty::BindByReference(_) = bm {
 600                     if let ty::Ref(_, rty, _) = ty.sty {
 601                         ty = rty;
 602                     } else {
 603                         bug!("`ref {}` has wrong type {}", ident, ty);
 604                     }
 605                 }
 606
 607                 PatternKind::Binding {
 608                     mutability,
 609                     mode,
 610                     name: ident.name,
 611                     var: id,
 612                     ty: var_ty,
 613                     subpattern: self.lower_opt_pattern(sub),
 614                 }
 615             }
 616
 617             PatKind::TupleStruct(ref qpath, ref subpatterns, ddpos) => {
 618                 let res = self.tables.qpath_res(qpath, pat.hir_id);
 619                 let adt_def = match ty.sty {
 620                     ty::Adt(adt_def, _) => adt_def,
 621                     ty::Error => { // Avoid ICE (#50585)
 622                         return Pattern { span: pat.span, ty, kind: Box::new(PatternKind::Wild) };
 623                     }
 624                     _ => span_bug!(pat.span,
 625                                    "tuple struct pattern not applied to an ADT {:?}",
 626                                    ty),
 627                 };
 628                 let variant_def = adt_def.variant_of_res(res);
 629
 630                 let subpatterns =
 631                         subpatterns.iter()
 632                                    .enumerate_and_adjust(variant_def.fields.len(), ddpos)
 633                                    .map(|(i, field)| FieldPattern {
 634                                        field: Field::new(i),
 635                                        pattern: self.lower_pattern(field),
 636                                    })
 637                     .collect();
 638
 639                 self.lower_variant_or_leaf(res, pat.hir_id, pat.span, ty, subpatterns)
 640             }
 641
 642             PatKind::Struct(ref qpath, ref fields, _) => {
 643                 let res = self.tables.qpath_res(qpath, pat.hir_id);
 644                 let subpatterns =
 645                     fields.iter()
 646                           .map(|field| {
 647                               FieldPattern {
 648                                   field: Field::new(self.tcx.field_index(field.node.hir_id,
 649                                                                          self.tables)),
 650                                   pattern: self.lower_pattern(&field.node.pat),
 651                               }
 652                           })
 653                           .collect();
 654
 655                 self.lower_variant_or_leaf(res, pat.hir_id, pat.span, ty, subpatterns)
 656             }
 657         };
 658
 659         Pattern {
 660             span: pat.span,
 661             ty,
 662             kind: Box::new(kind),
 663         }
 664     }
 665
 666     fn lower_patterns(&mut self, pats: &'tcx [P<hir::Pat>]) -> Vec<Pattern<'tcx>> {
 667         pats.iter().map(|p| self.lower_pattern(p)).collect()
 668     }
 669
 670     fn lower_opt_pattern(&mut self, pat: &'tcx Option<P<hir::Pat>>) -> Option<Pattern<'tcx>>
 671     {
 672         pat.as_ref().map(|p| self.lower_pattern(p))
 673     }
 674
 675     fn flatten_nested_slice_patterns(
 676         &mut self,
 677         prefix: Vec<Pattern<'tcx>>,
 678         slice: Option<Pattern<'tcx>>,
 679         suffix: Vec<Pattern<'tcx>>)
 680         -> (Vec<Pattern<'tcx>>, Option<Pattern<'tcx>>, Vec<Pattern<'tcx>>)
 681     {
 682         let orig_slice = match slice {
 683             Some(orig_slice) => orig_slice,
 684             None => return (prefix, slice, suffix)
 685         };
 686         let orig_prefix = prefix;
 687         let orig_suffix = suffix;
 688
 689         // dance because of intentional borrow-checker stupidity.
 690         let kind = *orig_slice.kind;
 691         match kind {
 692             PatternKind::Slice { prefix, slice, mut suffix } |
 693             PatternKind::Array { prefix, slice, mut suffix } => {
 694                 let mut orig_prefix = orig_prefix;
 695
 696                 orig_prefix.extend(prefix);
 697                 suffix.extend(orig_suffix);
 698
 699                 (orig_prefix, slice, suffix)
 700             }
 701             _ => {
 702                 (orig_prefix, Some(Pattern {
 703                     kind: box kind, ..orig_slice
 704                 }), orig_suffix)
 705             }
 706         }
 707     }
 708
 709     fn slice_or_array_pattern(
 710         &mut self,
 711         span: Span,
 712         ty: Ty<'tcx>,
 713         prefix: &'tcx [P<hir::Pat>],
 714         slice: &'tcx Option<P<hir::Pat>>,
 715         suffix: &'tcx [P<hir::Pat>])
 716         -> PatternKind<'tcx>
 717     {
 718         let prefix = self.lower_patterns(prefix);
 719         let slice = self.lower_opt_pattern(slice);
 720         let suffix = self.lower_patterns(suffix);
 721         let (prefix, slice, suffix) =
 722             self.flatten_nested_slice_patterns(prefix, slice, suffix);
 723
 724         match ty.sty {
 725             ty::Slice(..) => {
 726                 // matching a slice or fixed-length array
 727                 PatternKind::Slice { prefix: prefix, slice: slice, suffix: suffix }
 728             }
 729
 730             ty::Array(_, len) => {
 731                 // fixed-length array
 732                 let len = len.eval_usize(self.tcx, self.param_env);
 733                 assert!(len >= prefix.len() as u64 + suffix.len() as u64);
 734                 PatternKind::Array { prefix: prefix, slice: slice, suffix: suffix }
 735             }
 736
 737             _ => {
 738                 span_bug!(span, "bad slice pattern type {:?}", ty);
 739             }
 740         }
 741     }
 742
 743     fn lower_variant_or_leaf(
 744         &mut self,
 745         res: Res,
 746         hir_id: hir::HirId,
 747         span: Span,
 748         ty: Ty<'tcx>,
 749         subpatterns: Vec<FieldPattern<'tcx>>,
 750     ) -> PatternKind<'tcx> {
 751         let res = match res {
 752             Res::Def(DefKind::Ctor(CtorOf::Variant, ..), variant_ctor_id) => {
 753                 let variant_id = self.tcx.parent(variant_ctor_id).unwrap();
 754                 Res::Def(DefKind::Variant, variant_id)
 755             },
 756             res => res,
 757         };
 758
 759         let mut kind = match res {
 760             Res::Def(DefKind::Variant, variant_id) => {
 761                 let enum_id = self.tcx.parent(variant_id).unwrap();
 762                 let adt_def = self.tcx.adt_def(enum_id);
 763                 if adt_def.is_enum() {
 764                     let substs = match ty.sty {
 765                         ty::Adt(_, substs) |
 766                         ty::FnDef(_, substs) => substs,
 767                         ty::Error => {  // Avoid ICE (#50585)
 768                             return PatternKind::Wild;
 769                         }
 770                         _ => bug!("inappropriate type for def: {:?}", ty),
 771                     };
 772                     PatternKind::Variant {
 773                         adt_def,
 774                         substs,
 775                         variant_index: adt_def.variant_index_with_id(variant_id),
 776                         subpatterns,
 777                     }
 778                 } else {
 779                     PatternKind::Leaf { subpatterns }
 780                 }
 781             }
 782
 783             Res::Def(DefKind::Struct, _)
 784             | Res::Def(DefKind::Ctor(CtorOf::Struct, ..), _)
 785             | Res::Def(DefKind::Union, _)
 786             | Res::Def(DefKind::TyAlias, _)
 787             | Res::Def(DefKind::AssocTy, _)
 788             | Res::SelfTy(..)
 789             | Res::SelfCtor(..) => {
 790                 PatternKind::Leaf { subpatterns }
 791             }
 792
 793             _ => {
 794                 self.errors.push(PatternError::NonConstPath(span));
 795                 PatternKind::Wild
 796             }
 797         };
 798
 799         if let Some(user_ty) = self.user_substs_applied_to_ty_of_hir_id(hir_id) {
 800             debug!("lower_variant_or_leaf: kind={:?} user_ty={:?} span={:?}", kind, user_ty, span);
 801             kind = PatternKind::AscribeUserType {
 802                 subpattern: Pattern {
 803                     span,
 804                     ty,
 805                     kind: Box::new(kind),
 806                 },
 807                 ascription: Ascription {
 808                     user_ty: PatternTypeProjection::from_user_type(user_ty),
 809                     user_ty_span: span,
 810                     variance: ty::Variance::Covariant,
 811                 },
 812             };
 813         }
 814
 815         kind
 816     }
 817
 818     /// Takes a HIR Path. If the path is a constant, evaluates it and feeds
 819     /// it to `const_to_pat`. Any other path (like enum variants without fields)
 820     /// is converted to the corresponding pattern via `lower_variant_or_leaf`.
 821     fn lower_path(&mut self,
 822                   qpath: &hir::QPath,
 823                   id: hir::HirId,
 824                   span: Span)
 825                   -> Pattern<'tcx> {
 826         let ty = self.tables.node_type(id);
 827         let res = self.tables.qpath_res(qpath, id);
 828         let is_associated_const = match res {
 829             Res::Def(DefKind::AssocConst, _) => true,
 830             _ => false,
 831         };
 832         let kind = match res {
 833             Res::Def(DefKind::Const, def_id) | Res::Def(DefKind::AssocConst, def_id) => {
 834                 let substs = self.tables.node_substs(id);
 835                 match ty::Instance::resolve(
 836                     self.tcx,
 837                     self.param_env,
 838                     def_id,
 839                     substs,
 840                 ) {
 841                     Some(instance) => {
 842                         let cid = GlobalId {
 843                             instance,
 844                             promoted: None,
 845                         };
 846                         match self.tcx.at(span).const_eval(self.param_env.and(cid)) {
 847                             Ok(value) => {
 848                                 let pattern = self.const_to_pat(instance, value, id, span);
 849                                 if !is_associated_const {
 850                                     return pattern;
 851                                 }
 852
 853                                 let user_provided_types = self.tables().user_provided_types();
 854                                 return if let Some(u_ty) = user_provided_types.get(id) {
 855                                     let user_ty = PatternTypeProjection::from_user_type(*u_ty);
 856                                     Pattern {
 857                                         span,
 858                                         kind: Box::new(
 859                                             PatternKind::AscribeUserType {
 860                                                 subpattern: pattern,
 861                                                 ascription: Ascription {
 862                                                     /// Note that use `Contravariant` here. See the
 863                                                     /// `variance` field documentation for details.
 864                                                     variance: ty::Variance::Contravariant,
 865                                                     user_ty,
 866                                                     user_ty_span: span,
 867                                                 },
 868                                             }
 869                                         ),
 870                                         ty: value.ty,
 871                                     }
 872                                 } else {
 873                                     pattern
 874                                 }
 875                             },
 876                             Err(_) => {
 877                                 self.tcx.sess.span_err(
 878                                     span,
 879                                     "could not evaluate constant pattern",
 880                                 );
 881                                 PatternKind::Wild
 882                             }
 883                         }
 884                     },
 885                     None => {
 886                         self.errors.push(if is_associated_const {
 887                             PatternError::AssocConstInPattern(span)
 888                         } else {
 889                             PatternError::StaticInPattern(span)
 890                         });
 891                         PatternKind::Wild
 892                     },
 893                 }
 894             }
 895             _ => self.lower_variant_or_leaf(res, id, span, ty, vec![]),
 896         };
 897
 898         Pattern {
 899             span,
 900             ty,
 901             kind: Box::new(kind),
 902         }
 903     }
 904
 905     /// Converts literals, paths and negation of literals to patterns.
 906     /// The special case for negation exists to allow things like `-128_i8`
 907     /// which would overflow if we tried to evaluate `128_i8` and then negate
 908     /// afterwards.
 909     fn lower_lit(&mut self, expr: &'tcx hir::Expr) -> PatternKind<'tcx> {
 910         match expr.node {
 911             hir::ExprKind::Lit(ref lit) => {
 912                 let ty = self.tables.expr_ty(expr);
 913                 match lit_to_const(&lit.node, self.tcx, ty, false) {
 914                     Ok(val) => {
 915                         let instance = ty::Instance::new(
 916                             self.tables.local_id_root.expect("literal outside any scope"),
 917                             self.substs,
 918                         );
 919                         *self.const_to_pat(instance, val, expr.hir_id, lit.span).kind
 920                     },
 921                     Err(LitToConstError::UnparseableFloat) => {
 922                         self.errors.push(PatternError::FloatBug);
 923                         PatternKind::Wild
 924                     },
 925                     Err(LitToConstError::Reported) => PatternKind::Wild,
 926                 }
 927             },
 928             hir::ExprKind::Path(ref qpath) => *self.lower_path(qpath, expr.hir_id, expr.span).kind,
 929             hir::ExprKind::Unary(hir::UnNeg, ref expr) => {
 930                 let ty = self.tables.expr_ty(expr);
 931                 let lit = match expr.node {
 932                     hir::ExprKind::Lit(ref lit) => lit,
 933                     _ => span_bug!(expr.span, "not a literal: {:?}", expr),
 934                 };
 935                 match lit_to_const(&lit.node, self.tcx, ty, true) {
 936                     Ok(val) => {
 937                         let instance = ty::Instance::new(
 938                             self.tables.local_id_root.expect("literal outside any scope"),
 939                             self.substs,
 940                         );
 941                         *self.const_to_pat(instance, val, expr.hir_id, lit.span).kind
 942                     },
 943                     Err(LitToConstError::UnparseableFloat) => {
 944                         self.errors.push(PatternError::FloatBug);
 945                         PatternKind::Wild
 946                     },
 947                     Err(LitToConstError::Reported) => PatternKind::Wild,
 948                 }
 949             }
 950             _ => span_bug!(expr.span, "not a literal: {:?}", expr),
 951         }
 952     }
 953
 954     /// Converts an evaluated constant to a pattern (if possible).
 955     /// This means aggregate values (like structs and enums) are converted
 956     /// to a pattern that matches the value (as if you'd compared via structural equality).
 957     fn const_to_pat(
 958         &self,
 959         instance: ty::Instance<'tcx>,
 960         cv: &'tcx ty::Const<'tcx>,
 961         id: hir::HirId,
 962         span: Span,
 963     ) -> Pattern<'tcx> {
 964         // This method is just a warpper handling a validity check; the heavy lifting is
 965         // performed by the recursive const_to_pat_inner method, which is not meant to be
 966         // invoked except by this method.
 967         //
 968         // once indirect_structural_match is a full fledged error, this
 969         // level of indirection can be eliminated
 970
 971         debug!("const_to_pat: cv={:#?} id={:?}", cv, id);
 972         debug!("const_to_pat: cv.ty={:?} span={:?}", cv.ty, span);
 973
 974         let mut saw_error = false;
 975         let inlined_const_as_pat = self.const_to_pat_inner(instance, cv, id, span, &mut saw_error);
 976
 977         if self.include_lint_checks && !saw_error {
 978             // If we were able to successfully convert the const to some pat, double-check
 979             // that the type of the const obeys `#[structural_match]` constraint.
 980             if let Some(adt_def) = search_for_adt_without_structural_match(self.tcx, cv.ty) {
 981
 982                 let path = self.tcx.def_path_str(adt_def.did);
 983                 let msg = format!(
 984                     "to use a constant of type `{}` in a pattern, \
 985                      `{}` must be annotated with `#[derive(PartialEq, Eq)]`",
 986                     path,
 987                     path,
 988                 );
 989
 990                 // before issuing lint, double-check there even *is* a
 991                 // semantic PartialEq for us to dispatch to.
 992                 //
 993                 // (If there isn't, then we can safely issue a hard
 994                 // error, because that's never worked, due to compiler
 995                 // using PartialEq::eq in this scenario in the past.)
 996
 997                 let ty_is_partial_eq: bool = {
 998                     let partial_eq_trait_id = self.tcx.lang_items().eq_trait().unwrap();
 999                     let obligation: PredicateObligation<'_> =
1000                         self.tcx.predicate_for_trait_def(self.param_env,
1001                                                          ObligationCause::misc(span, id),
1002                                                          partial_eq_trait_id,
1003                                                          0,
1004                                                          cv.ty,
1005                                                          &[]);
1006                     self.tcx
1007                         .infer_ctxt()
1008                         .enter(|infcx| infcx.predicate_may_hold(&obligation))
1009                 };
1010
1011                 if !ty_is_partial_eq {
1012                     // span_fatal avoids ICE from resolution of non-existent method (rare case).
1013                     self.tcx.sess.span_fatal(span, &msg);
1014                 } else {
1015                     self.tcx.lint_hir(lint::builtin::INDIRECT_STRUCTURAL_MATCH, id, span, &msg);
1016                 }
1017             }
1018         }
1019
1020         inlined_const_as_pat
1021     }
1022
1023     /// Recursive helper for `const_to_pat`; invoke that (instead of calling this directly).
1024     fn const_to_pat_inner(
1025         &self,
1026         instance: ty::Instance<'tcx>,
1027         cv: &'tcx ty::Const<'tcx>,
1028         id: hir::HirId,
1029         span: Span,
1030         // This tracks if we signal some hard error for a given const
1031         // value, so that we will not subsequently issue an irrelevant
1032         // lint for the same const value.
1033         saw_const_match_error: &mut bool,
1034     ) -> Pattern<'tcx> {
1035
1036         let mut adt_subpattern = |i, variant_opt| {
1037             let field = Field::new(i);
1038             let val = crate::const_eval::const_field(
1039                 self.tcx, self.param_env, variant_opt, field, cv
1040             );
1041             self.const_to_pat_inner(instance, val, id, span, saw_const_match_error)
1042         };
1043         let mut adt_subpatterns = |n, variant_opt| {
1044             (0..n).map(|i| {
1045                 let field = Field::new(i);
1046                 FieldPattern {
1047                     field,
1048                     pattern: adt_subpattern(i, variant_opt),
1049                 }
1050             }).collect::<Vec<_>>()
1051         };
1052
1053
1054         let kind = match cv.ty.sty {
1055             ty::Float(_) => {
1056                 self.tcx.lint_hir(
1057                     ::rustc::lint::builtin::ILLEGAL_FLOATING_POINT_LITERAL_PATTERN,
1058                     id,
1059                     span,
1060                     "floating-point types cannot be used in patterns",
1061                 );
1062                 PatternKind::Constant {
1063                     value: cv,
1064                 }
1065             }
1066             ty::Adt(adt_def, _) if adt_def.is_union() => {
1067                 // Matching on union fields is unsafe, we can't hide it in constants
1068                 *saw_const_match_error = true;
1069                 self.tcx.sess.span_err(span, "cannot use unions in constant patterns");
1070                 PatternKind::Wild
1071             }
1072             // keep old code until future-compat upgraded to errors.
1073             ty::Adt(adt_def, _) if !self.tcx.has_attr(adt_def.did, sym::structural_match) => {
1074                 let path = self.tcx.def_path_str(adt_def.did);
1075                 let msg = format!(
1076                     "to use a constant of type `{}` in a pattern, \
1077                      `{}` must be annotated with `#[derive(PartialEq, Eq)]`",
1078                     path,
1079                     path,
1080                 );
1081                 *saw_const_match_error = true;
1082                 self.tcx.sess.span_err(span, &msg);
1083                 PatternKind::Wild
1084             }
1085             // keep old code until future-compat upgraded to errors.
1086             ty::Ref(_, ty::TyS { sty: ty::Adt(adt_def, _), .. }, _)
1087             if !self.tcx.has_attr(adt_def.did, sym::structural_match) => {
1088                 // HACK(estebank): Side-step ICE #53708, but anything other than erroring here
1089                 // would be wrong. Returnging `PatternKind::Wild` is not technically correct.
1090                 let path = self.tcx.def_path_str(adt_def.did);
1091                 let msg = format!(
1092                     "to use a constant of type `{}` in a pattern, \
1093                      `{}` must be annotated with `#[derive(PartialEq, Eq)]`",
1094                     path,
1095                     path,
1096                 );
1097                 *saw_const_match_error = true;
1098                 self.tcx.sess.span_err(span, &msg);
1099                 PatternKind::Wild
1100             }
1101             ty::Adt(adt_def, substs) if adt_def.is_enum() => {
1102                 let variant_index = const_variant_index(self.tcx, self.param_env, cv);
1103                 let subpatterns = adt_subpatterns(
1104                     adt_def.variants[variant_index].fields.len(),
1105                     Some(variant_index),
1106                 );
1107                 PatternKind::Variant {
1108                     adt_def,
1109                     substs,
1110                     variant_index,
1111                     subpatterns,
1112                 }
1113             }
1114             ty::Adt(adt_def, _) => {
1115                 let struct_var = adt_def.non_enum_variant();
1116                 PatternKind::Leaf {
1117                     subpatterns: adt_subpatterns(struct_var.fields.len(), None),
1118                 }
1119             }
1120             ty::Tuple(fields) => {
1121                 PatternKind::Leaf {
1122                     subpatterns: adt_subpatterns(fields.len(), None),
1123                 }
1124             }
1125             ty::Array(_, n) => {
1126                 PatternKind::Array {
1127                     prefix: (0..n.eval_usize(self.tcx, self.param_env))
1128                         .map(|i| adt_subpattern(i as usize, None))
1129                         .collect(),
1130                     slice: None,
1131                     suffix: Vec::new(),
1132                 }
1133             }
1134             _ => {
1135                 PatternKind::Constant {
1136                     value: cv,
1137                 }
1138             }
1139         };
1140
1141         Pattern {
1142             span,
1143             ty: cv.ty,
1144             kind: Box::new(kind),
1145         }
1146     }
1147 }
1148
1149 /// This method traverses the structure of `ty`, trying to find an
1150 /// instance of an ADT (i.e. struct or enum) that was declared without
1151 /// the `#[structural_match]` attribute.
1152 ///
1153 /// The "structure of a type" includes all components that would be
1154 /// considered when doing a pattern match on a constant of that
1155 /// type.
1156 ///
1157 ///  * This means this method descends into fields of structs/enums,
1158 ///    and also descends into the inner type `T` of `&T` and `&mut T`
1159 ///
1160 ///  * The traversal doesn't dereference unsafe pointers (`*const T`,
1161 ///    `*mut T`), and it does not visit the type arguments of an
1162 ///    instantiated generic like `PhantomData<T>`.
1163 ///
1164 /// The reason we do this search is Rust currently require all ADT's
1165 /// reachable from a constant's type to be annotated with
1166 /// `#[structural_match]`, an attribute which essentially says that
1167 /// the implementation of `PartialEq::eq` behaves *equivalently* to a
1168 /// comparison against the unfolded structure.
1169 ///
1170 /// For more background on why Rust has this requirement, and issues
1171 /// that arose when the requirement was not enforced completely, see
1172 /// Rust RFC 1445, rust-lang/rust#61188, and rust-lang/rust#62307.
1173 fn search_for_adt_without_structural_match<'tcx>(tcx: TyCtxt<'tcx>,
1174                                                  ty: Ty<'tcx>)
1175                                                  -> Option<&'tcx AdtDef>
1176 {
1177     // Import here (not mod level), because `TypeFoldable::fold_with`
1178     // conflicts with `PatternFoldable::fold_with`
1179     use crate::rustc::ty::fold::TypeVisitor;
1180     use crate::rustc::ty::TypeFoldable;
1181
1182     let mut search = Search { tcx, found: None, seen: FxHashSet::default() };
1183     ty.visit_with(&mut search);
1184     return search.found;
1185
1186     struct Search<'tcx> {
1187         tcx: TyCtxt<'tcx>,
1188
1189         // records the first ADT we find without `#[structural_match`
1190         found: Option<&'tcx AdtDef>,
1191
1192         // tracks ADT's previously encountered during search, so that
1193         // we will not recur on them again.
1194         seen: FxHashSet<&'tcx AdtDef>,
1195     }
1196
1197     impl<'tcx> TypeVisitor<'tcx> for Search<'tcx> {
1198         fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool {
1199             debug!("Search visiting ty: {:?}", ty);
1200
1201             let (adt_def, substs) = match ty.sty {
1202                 ty::Adt(adt_def, substs) => (adt_def, substs),
1203                 ty::RawPtr(..) => {
1204                     // `#[structural_match]` ignores substructure of
1205                     // `*const _`/`*mut _`, so skip super_visit_with
1206
1207                     // (But still tell caller to continue search.)
1208                     return false;
1209                 }
1210                 ty::Array(_, n) if n.try_eval_usize(self.tcx, ty::ParamEnv::reveal_all()) == Some(0)
1211                 => {
1212                     // rust-lang/rust#62336: ignore type of contents
1213                     // for empty array.
1214                     return false;
1215                 }
1216                 _ => {
1217                     ty.super_visit_with(self);
1218                     return false;
1219                 }
1220             };
1221
1222             if !self.tcx.has_attr(adt_def.did, sym::structural_match) {
1223                 self.found = Some(&adt_def);
1224                 debug!("Search found adt_def: {:?}", adt_def);
1225                 return true // Halt visiting!
1226             }
1227
1228             if self.seen.contains(adt_def) {
1229                 debug!("Search already seen adt_def: {:?}", adt_def);
1230                 // let caller continue its search
1231                 return false;
1232             }
1233
1234             self.seen.insert(adt_def);
1235
1236             // `#[structural_match]` does not care about the
1237             // instantiation of the generics in an ADT (it
1238             // instead looks directly at its fields outside
1239             // this match), so we skip super_visit_with.
1240             //
1241             // (Must not recur on substs for `PhantomData<T>` cf
1242             // rust-lang/rust#55028 and rust-lang/rust#55837; but also
1243             // want to skip substs when only uses of generic are
1244             // behind unsafe pointers `*const T`/`*mut T`.)
1245
1246             // even though we skip super_visit_with, we must recur on
1247             // fields of ADT.
1248             let tcx = self.tcx;
1249             for field_ty in adt_def.all_fields().map(|field| field.ty(tcx, substs)) {
1250                 if field_ty.visit_with(self) {
1251                     // found an ADT without `#[structural_match]`; halt visiting!
1252                     assert!(self.found.is_some());
1253                     return true;
1254                 }
1255             }
1256
1257             // Even though we do not want to recur on substs, we do
1258             // want our caller to continue its own search.
1259             false
1260         }
1261     }
1262 }
1263
1264 impl UserAnnotatedTyHelpers<'tcx> for PatternContext<'_, 'tcx> {
1265     fn tcx(&self) -> TyCtxt<'tcx> {
1266         self.tcx
1267     }
1268
1269     fn tables(&self) -> &ty::TypeckTables<'tcx> {
1270         self.tables
1271     }
1272 }
1273
1274
1275 pub trait PatternFoldable<'tcx> : Sized {
1276     fn fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
1277         self.super_fold_with(folder)
1278     }
1279
1280     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self;
1281 }
1282
1283 pub trait PatternFolder<'tcx> : Sized {
1284     fn fold_pattern(&mut self, pattern: &Pattern<'tcx>) -> Pattern<'tcx> {
1285         pattern.super_fold_with(self)
1286     }
1287
1288     fn fold_pattern_kind(&mut self, kind: &PatternKind<'tcx>) -> PatternKind<'tcx> {
1289         kind.super_fold_with(self)
1290     }
1291 }
1292
1293
1294 impl<'tcx, T: PatternFoldable<'tcx>> PatternFoldable<'tcx> for Box<T> {
1295     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
1296         let content: T = (**self).fold_with(folder);
1297         box content
1298     }
1299 }
1300
1301 impl<'tcx, T: PatternFoldable<'tcx>> PatternFoldable<'tcx> for Vec<T> {
1302     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
1303         self.iter().map(|t| t.fold_with(folder)).collect()
1304     }
1305 }
1306
1307 impl<'tcx, T: PatternFoldable<'tcx>> PatternFoldable<'tcx> for Option<T> {
1308     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self{
1309         self.as_ref().map(|t| t.fold_with(folder))
1310     }
1311 }
1312
1313 macro_rules! CloneImpls {
1314     (<$lt_tcx:tt> $($ty:ty),+) => {
1315         $(
1316             impl<$lt_tcx> PatternFoldable<$lt_tcx> for $ty {
1317                 fn super_fold_with<F: PatternFolder<$lt_tcx>>(&self, _: &mut F) -> Self {
1318                     Clone::clone(self)
1319                 }
1320             }
1321         )+
1322     }
1323 }
1324
1325 CloneImpls!{ <'tcx>
1326     Span, Field, Mutability, ast::Name, hir::HirId, usize, ty::Const<'tcx>,
1327     Region<'tcx>, Ty<'tcx>, BindingMode, &'tcx AdtDef,
1328     SubstsRef<'tcx>, &'tcx Kind<'tcx>, UserType<'tcx>,
1329     UserTypeProjection, PatternTypeProjection<'tcx>
1330 }
1331
1332 impl<'tcx> PatternFoldable<'tcx> for FieldPattern<'tcx> {
1333     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
1334         FieldPattern {
1335             field: self.field.fold_with(folder),
1336             pattern: self.pattern.fold_with(folder)
1337         }
1338     }
1339 }
1340
1341 impl<'tcx> PatternFoldable<'tcx> for Pattern<'tcx> {
1342     fn fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
1343         folder.fold_pattern(self)
1344     }
1345
1346     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
1347         Pattern {
1348             ty: self.ty.fold_with(folder),
1349             span: self.span.fold_with(folder),
1350             kind: self.kind.fold_with(folder)
1351         }
1352     }
1353 }
1354
1355 impl<'tcx> PatternFoldable<'tcx> for PatternKind<'tcx> {
1356     fn fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
1357         folder.fold_pattern_kind(self)
1358     }
1359
1360     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
1361         match *self {
1362             PatternKind::Wild => PatternKind::Wild,
1363             PatternKind::AscribeUserType {
1364                 ref subpattern,
1365                 ascription: Ascription {
1366                     variance,
1367                     ref user_ty,
1368                     user_ty_span,
1369                 },
1370             } => PatternKind::AscribeUserType {
1371                 subpattern: subpattern.fold_with(folder),
1372                 ascription: Ascription {
1373                     user_ty: user_ty.fold_with(folder),
1374                     variance,
1375                     user_ty_span,
1376                 },
1377             },
1378             PatternKind::Binding {
1379                 mutability,
1380                 name,
1381                 mode,
1382                 var,
1383                 ty,
1384                 ref subpattern,
1385             } => PatternKind::Binding {
1386                 mutability: mutability.fold_with(folder),
1387                 name: name.fold_with(folder),
1388                 mode: mode.fold_with(folder),
1389                 var: var.fold_with(folder),
1390                 ty: ty.fold_with(folder),
1391                 subpattern: subpattern.fold_with(folder),
1392             },
1393             PatternKind::Variant {
1394                 adt_def,
1395                 substs,
1396                 variant_index,
1397                 ref subpatterns,
1398             } => PatternKind::Variant {
1399                 adt_def: adt_def.fold_with(folder),
1400                 substs: substs.fold_with(folder),
1401                 variant_index,
1402                 subpatterns: subpatterns.fold_with(folder)
1403             },
1404             PatternKind::Leaf {
1405                 ref subpatterns,
1406             } => PatternKind::Leaf {
1407                 subpatterns: subpatterns.fold_with(folder),
1408             },
1409             PatternKind::Deref {
1410                 ref subpattern,
1411             } => PatternKind::Deref {
1412                 subpattern: subpattern.fold_with(folder),
1413             },
1414             PatternKind::Constant {
1415                 value
1416             } => PatternKind::Constant {
1417                 value,
1418             },
1419             PatternKind::Range(PatternRange {
1420                 lo,
1421                 hi,
1422                 ty,
1423                 end,
1424             }) => PatternKind::Range(PatternRange {
1425                 lo,
1426                 hi,
1427                 ty: ty.fold_with(folder),
1428                 end,
1429             }),
1430             PatternKind::Slice {
1431                 ref prefix,
1432                 ref slice,
1433                 ref suffix,
1434             } => PatternKind::Slice {
1435                 prefix: prefix.fold_with(folder),
1436                 slice: slice.fold_with(folder),
1437                 suffix: suffix.fold_with(folder)
1438             },
1439             PatternKind::Array {
1440                 ref prefix,
1441                 ref slice,
1442                 ref suffix
1443             } => PatternKind::Array {
1444                 prefix: prefix.fold_with(folder),
1445                 slice: slice.fold_with(folder),
1446                 suffix: suffix.fold_with(folder)
1447             },
1448         }
1449     }
1450 }
1451
1452 pub fn compare_const_vals<'tcx>(
1453     tcx: TyCtxt<'tcx>,
1454     a: &'tcx ty::Const<'tcx>,
1455     b: &'tcx ty::Const<'tcx>,
1456     param_env: ty::ParamEnv<'tcx>,
1457     ty: Ty<'tcx>,
1458 ) -> Option<Ordering> {
1459     trace!("compare_const_vals: {:?}, {:?}", a, b);
1460
1461     let from_bool = |v: bool| {
1462         if v {
1463             Some(Ordering::Equal)
1464         } else {
1465             None
1466         }
1467     };
1468
1469     let fallback = || from_bool(a == b);
1470
1471     // Use the fallback if any type differs
1472     if a.ty != b.ty || a.ty != ty {
1473         return fallback();
1474     }
1475
1476     let a_bits = a.try_eval_bits(tcx, param_env, ty);
1477     let b_bits = b.try_eval_bits(tcx, param_env, ty);
1478
1479     if let (Some(a), Some(b)) = (a_bits, b_bits) {
1480         use ::rustc_apfloat::Float;
1481         return match ty.sty {
1482             ty::Float(ast::FloatTy::F32) => {
1483                 let l = ::rustc_apfloat::ieee::Single::from_bits(a);
1484                 let r = ::rustc_apfloat::ieee::Single::from_bits(b);
1485                 l.partial_cmp(&r)
1486             }
1487             ty::Float(ast::FloatTy::F64) => {
1488                 let l = ::rustc_apfloat::ieee::Double::from_bits(a);
1489                 let r = ::rustc_apfloat::ieee::Double::from_bits(b);
1490                 l.partial_cmp(&r)
1491             }
1492             ty::Int(ity) => {
1493                 use rustc::ty::layout::{Integer, IntegerExt};
1494                 use syntax::attr::SignedInt;
1495                 let size = Integer::from_attr(&tcx, SignedInt(ity)).size();
1496                 let a = sign_extend(a, size);
1497                 let b = sign_extend(b, size);
1498                 Some((a as i128).cmp(&(b as i128)))
1499             }
1500             _ => Some(a.cmp(&b)),
1501         }
1502     }
1503
1504     if let ty::Str = ty.sty {
1505         match (a.val, b.val) {
1506             (
1507                 ConstValue::Slice { data: alloc_a, start: offset_a, end: end_a },
1508                 ConstValue::Slice { data: alloc_b, start: offset_b, end: end_b },
1509             ) => {
1510                 let len_a = end_a - offset_a;
1511                 let len_b = end_b - offset_b;
1512                 let a = alloc_a.get_bytes(
1513                     &tcx,
1514                     // invent a pointer, only the offset is relevant anyway
1515                     Pointer::new(AllocId(0), Size::from_bytes(offset_a as u64)),
1516                     Size::from_bytes(len_a as u64),
1517                 );
1518                 let b = alloc_b.get_bytes(
1519                     &tcx,
1520                     // invent a pointer, only the offset is relevant anyway
1521                     Pointer::new(AllocId(0), Size::from_bytes(offset_b as u64)),
1522                     Size::from_bytes(len_b as u64),
1523                 );
1524                 if let (Ok(a), Ok(b)) = (a, b) {
1525                     return from_bool(a == b);
1526                 }
1527             }
1528             _ => (),
1529         }
1530     }
1531
1532     fallback()
1533 }