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