src/librustc_mir/hair/pattern/mod.rs

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