src/librustc_mir/hair/pattern/mod.rs

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