src/librustc_mir/hair/pattern/mod.rs

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