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