src/librustc_mir/hair/pattern/mod.rs

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