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