src/librustc_const_eval/pattern.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 use eval;
  12
  13 use rustc::middle::const_val::{ConstEvalErr, ConstVal};
  14 use rustc::mir::{Field, BorrowKind, Mutability};
  15 use rustc::ty::{self, TyCtxt, AdtDef, Ty, Region};
  16 use rustc::ty::subst::{Substs, Kind};
  17 use rustc::hir::{self, PatKind, RangeEnd};
  18 use rustc::hir::def::{Def, CtorKind};
  19 use rustc::hir::pat_util::EnumerateAndAdjustIterator;
  20
  21 use rustc_data_structures::indexed_vec::Idx;
  22
  23 use std::fmt;
  24 use syntax::ast;
  25 use syntax::ptr::P;
  26 use syntax_pos::Span;
  27
  28 #[derive(Clone, Debug)]
  29 pub enum PatternError<'tcx> {
  30     AssociatedConstInPattern(Span),
  31     StaticInPattern(Span),
  32     ConstEval(ConstEvalErr<'tcx>),
  33 }
  34
  35 #[derive(Copy, Clone, Debug)]
  36 pub enum BindingMode<'tcx> {
  37     ByValue,
  38     ByRef(Region<'tcx>, BorrowKind),
  39 }
  40
  41 #[derive(Clone, Debug)]
  42 pub struct FieldPattern<'tcx> {
  43     pub field: Field,
  44     pub pattern: Pattern<'tcx>,
  45 }
  46
  47 #[derive(Clone, Debug)]
  48 pub struct Pattern<'tcx> {
  49     pub ty: Ty<'tcx>,
  50     pub span: Span,
  51     pub kind: Box<PatternKind<'tcx>>,
  52 }
  53
  54 #[derive(Clone, Debug)]
  55 pub enum PatternKind<'tcx> {
  56     Wild,
  57
  58     /// x, ref x, x @ P, etc
  59     Binding {
  60         mutability: Mutability,
  61         name: ast::Name,
  62         mode: BindingMode<'tcx>,
  63         var: ast::NodeId,
  64         ty: Ty<'tcx>,
  65         subpattern: Option<Pattern<'tcx>>,
  66     },
  67
  68     /// Foo(...) or Foo{...} or Foo, where `Foo` is a variant name from an adt with >1 variants
  69     Variant {
  70         adt_def: &'tcx AdtDef,
  71         substs: &'tcx Substs<'tcx>,
  72         variant_index: usize,
  73         subpatterns: Vec<FieldPattern<'tcx>>,
  74     },
  75
  76     /// (...), Foo(...), Foo{...}, or Foo, where `Foo` is a variant name from an adt with 1 variant
  77     Leaf {
  78         subpatterns: Vec<FieldPattern<'tcx>>,
  79     },
  80
  81     /// box P, &P, &mut P, etc
  82     Deref {
  83         subpattern: Pattern<'tcx>,
  84     },
  85
  86     Constant {
  87         value: &'tcx ty::Const<'tcx>,
  88     },
  89
  90     Range {
  91         lo: &'tcx ty::Const<'tcx>,
  92         hi: &'tcx ty::Const<'tcx>,
  93         end: RangeEnd,
  94     },
  95
  96     /// matches against a slice, checking the length and extracting elements.
  97     /// irrefutable when there is a slice pattern and both `prefix` and `suffix` are empty.
  98     /// e.g. `&[ref xs..]`.
  99     Slice {
 100         prefix: Vec<Pattern<'tcx>>,
 101         slice: Option<Pattern<'tcx>>,
 102         suffix: Vec<Pattern<'tcx>>,
 103     },
 104
 105     /// fixed match against an array, irrefutable
 106     Array {
 107         prefix: Vec<Pattern<'tcx>>,
 108         slice: Option<Pattern<'tcx>>,
 109         suffix: Vec<Pattern<'tcx>>,
 110     },
 111 }
 112
 113 fn print_const_val(value: &ConstVal, f: &mut fmt::Formatter) -> fmt::Result {
 114     match *value {
 115         ConstVal::Float(ref x) => write!(f, "{}", x),
 116         ConstVal::Integral(ref i) => write!(f, "{}", i),
 117         ConstVal::Str(ref s) => write!(f, "{:?}", &s[..]),
 118         ConstVal::ByteStr(b) => write!(f, "{:?}", b.data),
 119         ConstVal::Bool(b) => write!(f, "{:?}", b),
 120         ConstVal::Char(c) => write!(f, "{:?}", c),
 121         ConstVal::Variant(_) |
 122         ConstVal::Function(..) |
 123         ConstVal::Aggregate(_) |
 124         ConstVal::Unevaluated(..) => bug!("{:?} not printable in a pattern", value)
 125     }
 126 }
 127
 128 impl<'tcx> fmt::Display for Pattern<'tcx> {
 129     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 130         match *self.kind {
 131             PatternKind::Wild => write!(f, "_"),
 132             PatternKind::Binding { mutability, name, mode, ref subpattern, .. } => {
 133                 let is_mut = match mode {
 134                     BindingMode::ByValue => mutability == Mutability::Mut,
 135                     BindingMode::ByRef(_, bk) => {
 136                         write!(f, "ref ")?;
 137                         match bk { BorrowKind::Mut { .. } => true, _ => false }
 138                     }
 139                 };
 140                 if is_mut {
 141                     write!(f, "mut ")?;
 142                 }
 143                 write!(f, "{}", name)?;
 144                 if let Some(ref subpattern) = *subpattern {
 145                     write!(f, " @ {}", subpattern)?;
 146                 }
 147                 Ok(())
 148             }
 149             PatternKind::Variant { ref subpatterns, .. } |
 150             PatternKind::Leaf { ref subpatterns } => {
 151                 let variant = match *self.kind {
 152                     PatternKind::Variant { adt_def, variant_index, .. } => {
 153                         Some(&adt_def.variants[variant_index])
 154                     }
 155                     _ => if let ty::TyAdt(adt, _) = self.ty.sty {
 156                         if !adt.is_enum() {
 157                             Some(&adt.variants[0])
 158                         } else {
 159                             None
 160                         }
 161                     } else {
 162                         None
 163                     }
 164                 };
 165
 166                 let mut first = true;
 167                 let mut start_or_continue = || if first { first = false; "" } else { ", " };
 168
 169                 if let Some(variant) = variant {
 170                     write!(f, "{}", variant.name)?;
 171
 172                     // Only for TyAdt we can have `S {...}`,
 173                     // which we handle separately here.
 174                     if variant.ctor_kind == CtorKind::Fictive {
 175                         write!(f, " {{ ")?;
 176
 177                         let mut printed = 0;
 178                         for p in subpatterns {
 179                             if let PatternKind::Wild = *p.pattern.kind {
 180                                 continue;
 181                             }
 182                             let name = variant.fields[p.field.index()].name;
 183                             write!(f, "{}{}: {}", start_or_continue(), name, p.pattern)?;
 184                             printed += 1;
 185                         }
 186
 187                         if printed < variant.fields.len() {
 188                             write!(f, "{}..", start_or_continue())?;
 189                         }
 190
 191                         return write!(f, " }}");
 192                     }
 193                 }
 194
 195                 let num_fields = variant.map_or(subpatterns.len(), |v| v.fields.len());
 196                 if num_fields != 0 || variant.is_none() {
 197                     write!(f, "(")?;
 198                     for i in 0..num_fields {
 199                         write!(f, "{}", start_or_continue())?;
 200
 201                         // Common case: the field is where we expect it.
 202                         if let Some(p) = subpatterns.get(i) {
 203                             if p.field.index() == i {
 204                                 write!(f, "{}", p.pattern)?;
 205                                 continue;
 206                             }
 207                         }
 208
 209                         // Otherwise, we have to go looking for it.
 210                         if let Some(p) = subpatterns.iter().find(|p| p.field.index() == i) {
 211                             write!(f, "{}", p.pattern)?;
 212                         } else {
 213                             write!(f, "_")?;
 214                         }
 215                     }
 216                     write!(f, ")")?;
 217                 }
 218
 219                 Ok(())
 220             }
 221             PatternKind::Deref { ref subpattern } => {
 222                 match self.ty.sty {
 223                     ty::TyAdt(def, _) if def.is_box() => write!(f, "box ")?,
 224                     ty::TyRef(_, mt) => {
 225                         write!(f, "&")?;
 226                         if mt.mutbl == hir::MutMutable {
 227                             write!(f, "mut ")?;
 228                         }
 229                     }
 230                     _ => bug!("{} is a bad Deref pattern type", self.ty)
 231                 }
 232                 write!(f, "{}", subpattern)
 233             }
 234             PatternKind::Constant { value } => {
 235                 print_const_val(&value.val, f)
 236             }
 237             PatternKind::Range { lo, hi, end } => {
 238                 print_const_val(&lo.val, f)?;
 239                 match end {
 240                     RangeEnd::Included => write!(f, "...")?,
 241                     RangeEnd::Excluded => write!(f, "..")?,
 242                 }
 243                 print_const_val(&hi.val, f)
 244             }
 245             PatternKind::Slice { ref prefix, ref slice, ref suffix } |
 246             PatternKind::Array { ref prefix, ref slice, ref suffix } => {
 247                 let mut first = true;
 248                 let mut start_or_continue = || if first { first = false; "" } else { ", " };
 249                 write!(f, "[")?;
 250                 for p in prefix {
 251                     write!(f, "{}{}", start_or_continue(), p)?;
 252                 }
 253                 if let Some(ref slice) = *slice {
 254                     write!(f, "{}", start_or_continue())?;
 255                     match *slice.kind {
 256                         PatternKind::Wild => {}
 257                         _ => write!(f, "{}", slice)?
 258                     }
 259                     write!(f, "..")?;
 260                 }
 261                 for p in suffix {
 262                     write!(f, "{}{}", start_or_continue(), p)?;
 263                 }
 264                 write!(f, "]")
 265             }
 266         }
 267     }
 268 }
 269
 270 pub struct PatternContext<'a, 'tcx: 'a> {
 271     pub tcx: TyCtxt<'a, 'tcx, 'tcx>,
 272     pub param_env: ty::ParamEnv<'tcx>,
 273     pub tables: &'a ty::TypeckTables<'tcx>,
 274     pub substs: &'tcx Substs<'tcx>,
 275     pub errors: Vec<PatternError<'tcx>>,
 276 }
 277
 278 impl<'a, 'tcx> Pattern<'tcx> {
 279     pub fn from_hir(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 280                     param_env_and_substs: ty::ParamEnvAnd<'tcx, &'tcx Substs<'tcx>>,
 281                     tables: &'a ty::TypeckTables<'tcx>,
 282                     pat: &'tcx hir::Pat) -> Self {
 283         let mut pcx = PatternContext::new(tcx, param_env_and_substs, tables);
 284         let result = pcx.lower_pattern(pat);
 285         if !pcx.errors.is_empty() {
 286             let msg = format!("encountered errors lowering pattern: {:?}", pcx.errors);
 287             tcx.sess.delay_span_bug(pat.span, &msg);
 288         }
 289         debug!("Pattern::from_hir({:?}) = {:?}", pat, result);
 290         result
 291     }
 292 }
 293
 294 impl<'a, 'tcx> PatternContext<'a, 'tcx> {
 295     pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 296                param_env_and_substs: ty::ParamEnvAnd<'tcx, &'tcx Substs<'tcx>>,
 297                tables: &'a ty::TypeckTables<'tcx>) -> Self {
 298         PatternContext {
 299             tcx,
 300             param_env: param_env_and_substs.param_env,
 301             tables,
 302             substs: param_env_and_substs.value,
 303             errors: vec![]
 304         }
 305     }
 306
 307     pub fn lower_pattern(&mut self, pat: &'tcx hir::Pat) -> Pattern<'tcx> {
 308         // When implicit dereferences have been inserted in this pattern, the unadjusted lowered
 309         // pattern has the type that results *after* dereferencing. For example, in this code:
 310         //
 311         // ```
 312         // match &&Some(0i32) {
 313         //     Some(n) => { ... },
 314         //     _ => { ... },
 315         // }
 316         // ```
 317         //
 318         // the type assigned to `Some(n)` in `unadjusted_pat` would be `Option<i32>` (this is
 319         // determined in rustc_typeck::check::match). The adjustments would be
 320         //
 321         // `vec![&&Option<i32>, &Option<i32>]`.
 322         //
 323         // Applying the adjustments, we want to instead output `&&Some(n)` (as a HAIR pattern). So
 324         // we wrap the unadjusted pattern in `PatternKind::Deref` repeatedly, consuming the
 325         // adjustments in *reverse order* (last-in-first-out, so that the last `Deref` inserted
 326         // gets the least-dereferenced type).
 327         let unadjusted_pat = self.lower_pattern_unadjusted(pat);
 328         self.tables
 329             .pat_adjustments()
 330             .get(pat.hir_id)
 331             .unwrap_or(&vec![])
 332             .iter()
 333             .rev()
 334             .fold(unadjusted_pat, |pat, ref_ty| {
 335                     debug!("{:?}: wrapping pattern with type {:?}", pat, ref_ty);
 336                     Pattern {
 337                         span: pat.span,
 338                         ty: ref_ty,
 339                         kind: Box::new(PatternKind::Deref { subpattern: pat }),
 340                     }
 341                 },
 342             )
 343     }
 344
 345     fn lower_pattern_unadjusted(&mut self, pat: &'tcx hir::Pat) -> Pattern<'tcx> {
 346         let mut ty = self.tables.node_id_to_type(pat.hir_id);
 347
 348         let kind = match pat.node {
 349             PatKind::Wild => PatternKind::Wild,
 350
 351             PatKind::Lit(ref value) => self.lower_lit(value),
 352
 353             PatKind::Range(ref lo, ref hi, end) => {
 354                 match (self.lower_lit(lo), self.lower_lit(hi)) {
 355                     (PatternKind::Constant { value: lo },
 356                      PatternKind::Constant { value: hi }) => {
 357                         PatternKind::Range { lo, hi, end }
 358                     }
 359                     _ => PatternKind::Wild
 360                 }
 361             }
 362
 363             PatKind::Path(ref qpath) => {
 364                 return self.lower_path(qpath, pat.hir_id, pat.id, pat.span);
 365             }
 366
 367             PatKind::Ref(ref subpattern, _) |
 368             PatKind::Box(ref subpattern) => {
 369                 PatternKind::Deref { subpattern: self.lower_pattern(subpattern) }
 370             }
 371
 372             PatKind::Slice(ref prefix, ref slice, ref suffix) => {
 373                 let ty = self.tables.node_id_to_type(pat.hir_id);
 374                 match ty.sty {
 375                     ty::TyRef(_, mt) =>
 376                         PatternKind::Deref {
 377                             subpattern: Pattern {
 378                                 ty: mt.ty,
 379                                 span: pat.span,
 380                                 kind: Box::new(self.slice_or_array_pattern(
 381                                     pat.span, mt.ty, prefix, slice, suffix))
 382                             },
 383                         },
 384
 385                     ty::TySlice(..) |
 386                     ty::TyArray(..) =>
 387                         self.slice_or_array_pattern(pat.span, ty, prefix, slice, suffix),
 388
 389                     ref sty =>
 390                         span_bug!(
 391                             pat.span,
 392                             "unexpanded type for vector pattern: {:?}",
 393                             sty),
 394                 }
 395             }
 396
 397             PatKind::Tuple(ref subpatterns, ddpos) => {
 398                 let ty = self.tables.node_id_to_type(pat.hir_id);
 399                 match ty.sty {
 400                     ty::TyTuple(ref tys, _) => {
 401                         let subpatterns =
 402                             subpatterns.iter()
 403                                        .enumerate_and_adjust(tys.len(), ddpos)
 404                                        .map(|(i, subpattern)| FieldPattern {
 405                                             field: Field::new(i),
 406                                             pattern: self.lower_pattern(subpattern)
 407                                        })
 408                                        .collect();
 409
 410                         PatternKind::Leaf { subpatterns: subpatterns }
 411                     }
 412
 413                     ref sty => span_bug!(pat.span, "unexpected type for tuple pattern: {:?}", sty),
 414                 }
 415             }
 416
 417             PatKind::Binding(_, id, ref ident, ref sub) => {
 418                 let var_ty = self.tables.node_id_to_type(pat.hir_id);
 419                 let region = match var_ty.sty {
 420                     ty::TyRef(r, _) => Some(r),
 421                     _ => None,
 422                 };
 423                 let bm = *self.tables.pat_binding_modes().get(pat.hir_id)
 424                                                          .expect("missing binding mode");
 425                 let (mutability, mode) = match bm {
 426                     ty::BindByValue(hir::MutMutable) =>
 427                         (Mutability::Mut, BindingMode::ByValue),
 428                     ty::BindByValue(hir::MutImmutable) =>
 429                         (Mutability::Not, BindingMode::ByValue),
 430                     ty::BindByReference(hir::MutMutable) =>
 431                         (Mutability::Not, BindingMode::ByRef(
 432                             region.unwrap(), BorrowKind::Mut { allow_two_phase_borrow: false })),
 433                     ty::BindByReference(hir::MutImmutable) =>
 434                         (Mutability::Not, BindingMode::ByRef(
 435                             region.unwrap(), BorrowKind::Shared)),
 436                 };
 437
 438                 // A ref x pattern is the same node used for x, and as such it has
 439                 // x's type, which is &T, where we want T (the type being matched).
 440                 if let ty::BindByReference(_) = bm {
 441                     if let ty::TyRef(_, mt) = ty.sty {
 442                         ty = mt.ty;
 443                     } else {
 444                         bug!("`ref {}` has wrong type {}", ident.node, ty);
 445                     }
 446                 }
 447
 448                 PatternKind::Binding {
 449                     mutability,
 450                     mode,
 451                     name: ident.node,
 452                     var: id,
 453                     ty: var_ty,
 454                     subpattern: self.lower_opt_pattern(sub),
 455                 }
 456             }
 457
 458             PatKind::TupleStruct(ref qpath, ref subpatterns, ddpos) => {
 459                 let def = self.tables.qpath_def(qpath, pat.hir_id);
 460                 let adt_def = match ty.sty {
 461                     ty::TyAdt(adt_def, _) => adt_def,
 462                     _ => span_bug!(pat.span, "tuple struct pattern not applied to an ADT"),
 463                 };
 464                 let variant_def = adt_def.variant_of_def(def);
 465
 466                 let subpatterns =
 467                         subpatterns.iter()
 468                                    .enumerate_and_adjust(variant_def.fields.len(), ddpos)
 469                                    .map(|(i, field)| FieldPattern {
 470                                        field: Field::new(i),
 471                                        pattern: self.lower_pattern(field),
 472                                    })
 473                                    .collect();
 474                 self.lower_variant_or_leaf(def, ty, subpatterns)
 475             }
 476
 477             PatKind::Struct(ref qpath, ref fields, _) => {
 478                 let def = self.tables.qpath_def(qpath, pat.hir_id);
 479                 let adt_def = match ty.sty {
 480                     ty::TyAdt(adt_def, _) => adt_def,
 481                     _ => {
 482                         span_bug!(
 483                             pat.span,
 484                             "struct pattern not applied to an ADT");
 485                     }
 486                 };
 487                 let variant_def = adt_def.variant_of_def(def);
 488
 489                 let subpatterns =
 490                     fields.iter()
 491                           .map(|field| {
 492                               let index = variant_def.index_of_field_named(field.node.name);
 493                               let index = index.unwrap_or_else(|| {
 494                                   span_bug!(
 495                                       pat.span,
 496                                       "no field with name {:?}",
 497                                       field.node.name);
 498                               });
 499                               FieldPattern {
 500                                   field: Field::new(index),
 501                                   pattern: self.lower_pattern(&field.node.pat),
 502                               }
 503                           })
 504                           .collect();
 505
 506                 self.lower_variant_or_leaf(def, ty, subpatterns)
 507             }
 508         };
 509
 510         Pattern {
 511             span: pat.span,
 512             ty,
 513             kind: Box::new(kind),
 514         }
 515     }
 516
 517     fn lower_patterns(&mut self, pats: &'tcx [P<hir::Pat>]) -> Vec<Pattern<'tcx>> {
 518         pats.iter().map(|p| self.lower_pattern(p)).collect()
 519     }
 520
 521     fn lower_opt_pattern(&mut self, pat: &'tcx Option<P<hir::Pat>>) -> Option<Pattern<'tcx>>
 522     {
 523         pat.as_ref().map(|p| self.lower_pattern(p))
 524     }
 525
 526     fn flatten_nested_slice_patterns(
 527         &mut self,
 528         prefix: Vec<Pattern<'tcx>>,
 529         slice: Option<Pattern<'tcx>>,
 530         suffix: Vec<Pattern<'tcx>>)
 531         -> (Vec<Pattern<'tcx>>, Option<Pattern<'tcx>>, Vec<Pattern<'tcx>>)
 532     {
 533         let orig_slice = match slice {
 534             Some(orig_slice) => orig_slice,
 535             None => return (prefix, slice, suffix)
 536         };
 537         let orig_prefix = prefix;
 538         let orig_suffix = suffix;
 539
 540         // dance because of intentional borrow-checker stupidity.
 541         let kind = *orig_slice.kind;
 542         match kind {
 543             PatternKind::Slice { prefix, slice, mut suffix } |
 544             PatternKind::Array { prefix, slice, mut suffix } => {
 545                 let mut orig_prefix = orig_prefix;
 546
 547                 orig_prefix.extend(prefix);
 548                 suffix.extend(orig_suffix);
 549
 550                 (orig_prefix, slice, suffix)
 551             }
 552             _ => {
 553                 (orig_prefix, Some(Pattern {
 554                     kind: box kind, ..orig_slice
 555                 }), orig_suffix)
 556             }
 557         }
 558     }
 559
 560     fn slice_or_array_pattern(
 561         &mut self,
 562         span: Span,
 563         ty: Ty<'tcx>,
 564         prefix: &'tcx [P<hir::Pat>],
 565         slice: &'tcx Option<P<hir::Pat>>,
 566         suffix: &'tcx [P<hir::Pat>])
 567         -> PatternKind<'tcx>
 568     {
 569         let prefix = self.lower_patterns(prefix);
 570         let slice = self.lower_opt_pattern(slice);
 571         let suffix = self.lower_patterns(suffix);
 572         let (prefix, slice, suffix) =
 573             self.flatten_nested_slice_patterns(prefix, slice, suffix);
 574
 575         match ty.sty {
 576             ty::TySlice(..) => {
 577                 // matching a slice or fixed-length array
 578                 PatternKind::Slice { prefix: prefix, slice: slice, suffix: suffix }
 579             }
 580
 581             ty::TyArray(_, len) => {
 582                 // fixed-length array
 583                 let len = len.val.to_const_int().unwrap().to_u64().unwrap();
 584                 assert!(len >= prefix.len() as u64 + suffix.len() as u64);
 585                 PatternKind::Array { prefix: prefix, slice: slice, suffix: suffix }
 586             }
 587
 588             _ => {
 589                 span_bug!(span, "bad slice pattern type {:?}", ty);
 590             }
 591         }
 592     }
 593
 594     fn lower_variant_or_leaf(
 595         &mut self,
 596         def: Def,
 597         ty: Ty<'tcx>,
 598         subpatterns: Vec<FieldPattern<'tcx>>)
 599         -> PatternKind<'tcx>
 600     {
 601         match def {
 602             Def::Variant(variant_id) | Def::VariantCtor(variant_id, ..) => {
 603                 let enum_id = self.tcx.parent_def_id(variant_id).unwrap();
 604                 let adt_def = self.tcx.adt_def(enum_id);
 605                 if adt_def.is_enum() {
 606                     let substs = match ty.sty {
 607                         ty::TyAdt(_, substs) |
 608                         ty::TyFnDef(_, substs) => substs,
 609                         _ => bug!("inappropriate type for def: {:?}", ty.sty),
 610                     };
 611                     PatternKind::Variant {
 612                         adt_def,
 613                         substs,
 614                         variant_index: adt_def.variant_index_with_id(variant_id),
 615                         subpatterns,
 616                     }
 617                 } else {
 618                     PatternKind::Leaf { subpatterns: subpatterns }
 619                 }
 620             }
 621
 622             Def::Struct(..) | Def::StructCtor(..) | Def::Union(..) |
 623             Def::TyAlias(..) | Def::AssociatedTy(..) | Def::SelfTy(..) => {
 624                 PatternKind::Leaf { subpatterns: subpatterns }
 625             }
 626
 627             _ => bug!()
 628         }
 629     }
 630
 631     fn lower_path(&mut self,
 632                   qpath: &hir::QPath,
 633                   id: hir::HirId,
 634                   pat_id: ast::NodeId,
 635                   span: Span)
 636                   -> Pattern<'tcx> {
 637         let ty = self.tables.node_id_to_type(id);
 638         let def = self.tables.qpath_def(qpath, id);
 639         let is_associated_const = match def {
 640             Def::AssociatedConst(_) => true,
 641             _ => false,
 642         };
 643         let kind = match def {
 644             Def::Const(def_id) | Def::AssociatedConst(def_id) => {
 645                 let substs = self.tables.node_substs(id);
 646                 match eval::lookup_const_by_id(self.tcx, self.param_env.and((def_id, substs))) {
 647                     Some((def_id, substs)) => {
 648                         // Enter the inlined constant's tables&substs temporarily.
 649                         let old_tables = self.tables;
 650                         let old_substs = self.substs;
 651                         self.tables = self.tcx.typeck_tables_of(def_id);
 652                         self.substs = substs;
 653                         let body = if let Some(id) = self.tcx.hir.as_local_node_id(def_id) {
 654                             self.tcx.hir.body(self.tcx.hir.body_owned_by(id))
 655                         } else {
 656                             self.tcx.extern_const_body(def_id).body
 657                         };
 658                         let pat = self.lower_const_expr(&body.value, pat_id, span);
 659                         self.tables = old_tables;
 660                         self.substs = old_substs;
 661                         return pat;
 662                     }
 663                     None => {
 664                         self.errors.push(if is_associated_const {
 665                             PatternError::AssociatedConstInPattern(span)
 666                         } else {
 667                             PatternError::StaticInPattern(span)
 668                         });
 669                         PatternKind::Wild
 670                     }
 671                 }
 672             }
 673             _ => self.lower_variant_or_leaf(def, ty, vec![]),
 674         };
 675
 676         Pattern {
 677             span,
 678             ty,
 679             kind: Box::new(kind),
 680         }
 681     }
 682
 683     fn lower_lit(&mut self, expr: &'tcx hir::Expr) -> PatternKind<'tcx> {
 684         let const_cx = eval::ConstContext::new(self.tcx,
 685                                                self.param_env.and(self.substs),
 686                                                self.tables);
 687         match const_cx.eval(expr) {
 688             Ok(value) => {
 689                 if let ConstVal::Variant(def_id) = value.val {
 690                     let ty = self.tables.expr_ty(expr);
 691                     self.lower_variant_or_leaf(Def::Variant(def_id), ty, vec![])
 692                 } else {
 693                     PatternKind::Constant { value }
 694                 }
 695             }
 696             Err(e) => {
 697                 self.errors.push(PatternError::ConstEval(e));
 698                 PatternKind::Wild
 699             }
 700         }
 701     }
 702
 703     fn lower_const_expr(&mut self,
 704                         expr: &'tcx hir::Expr,
 705                         pat_id: ast::NodeId,
 706                         span: Span)
 707                         -> Pattern<'tcx> {
 708         let pat_ty = self.tables.expr_ty(expr);
 709         debug!("expr={:?} pat_ty={:?} pat_id={}", expr, pat_ty, pat_id);
 710         match pat_ty.sty {
 711             ty::TyFloat(_) => {
 712                 self.tcx.sess.span_err(span, "floating point constants cannot be used in patterns");
 713             }
 714             ty::TyAdt(adt_def, _) if adt_def.is_union() => {
 715                 // Matching on union fields is unsafe, we can't hide it in constants
 716                 self.tcx.sess.span_err(span, "cannot use unions in constant patterns");
 717             }
 718             ty::TyAdt(adt_def, _) => {
 719                 if !self.tcx.has_attr(adt_def.did, "structural_match") {
 720                     let msg = format!("to use a constant of type `{}` in a pattern, \
 721                                        `{}` must be annotated with `#[derive(PartialEq, Eq)]`",
 722                                       self.tcx.item_path_str(adt_def.did),
 723                                       self.tcx.item_path_str(adt_def.did));
 724                     self.tcx.sess.span_err(span, &msg);
 725                 }
 726             }
 727             _ => { }
 728         }
 729         let kind = match expr.node {
 730             hir::ExprTup(ref exprs) => {
 731                 PatternKind::Leaf {
 732                     subpatterns: exprs.iter().enumerate().map(|(i, expr)| {
 733                         FieldPattern {
 734                             field: Field::new(i),
 735                             pattern: self.lower_const_expr(expr, pat_id, span)
 736                         }
 737                     }).collect()
 738                 }
 739             }
 740
 741             hir::ExprCall(ref callee, ref args) => {
 742                 let qpath = match callee.node {
 743                     hir::ExprPath(ref qpath) => qpath,
 744                     _ => bug!()
 745                 };
 746                 let ty = self.tables.node_id_to_type(callee.hir_id);
 747                 let def = self.tables.qpath_def(qpath, callee.hir_id);
 748                 match def {
 749                     Def::Fn(..) | Def::Method(..) => self.lower_lit(expr),
 750                     _ => {
 751                         let subpatterns = args.iter().enumerate().map(|(i, expr)| {
 752                             FieldPattern {
 753                                 field: Field::new(i),
 754                                 pattern: self.lower_const_expr(expr, pat_id, span)
 755                             }
 756                         }).collect();
 757                         self.lower_variant_or_leaf(def, ty, subpatterns)
 758                     }
 759                 }
 760             }
 761
 762             hir::ExprStruct(ref qpath, ref fields, None) => {
 763                 let def = self.tables.qpath_def(qpath, expr.hir_id);
 764                 let adt_def = match pat_ty.sty {
 765                     ty::TyAdt(adt_def, _) => adt_def,
 766                     _ => {
 767                         span_bug!(
 768                             expr.span,
 769                             "struct expr without ADT type");
 770                     }
 771                 };
 772                 let variant_def = adt_def.variant_of_def(def);
 773
 774                 let subpatterns =
 775                     fields.iter()
 776                           .map(|field| {
 777                               let index = variant_def.index_of_field_named(field.name.node);
 778                               let index = index.unwrap_or_else(|| {
 779                                   span_bug!(
 780                                       expr.span,
 781                                       "no field with name {:?}",
 782                                       field.name);
 783                               });
 784                               FieldPattern {
 785                                   field: Field::new(index),
 786                                   pattern: self.lower_const_expr(&field.expr, pat_id, span),
 787                               }
 788                           })
 789                           .collect();
 790
 791                 self.lower_variant_or_leaf(def, pat_ty, subpatterns)
 792             }
 793
 794             hir::ExprArray(ref exprs) => {
 795                 let pats = exprs.iter()
 796                                 .map(|expr| self.lower_const_expr(expr, pat_id, span))
 797                                 .collect();
 798                 PatternKind::Array {
 799                     prefix: pats,
 800                     slice: None,
 801                     suffix: vec![]
 802                 }
 803             }
 804
 805             hir::ExprPath(ref qpath) => {
 806                 return self.lower_path(qpath, expr.hir_id, pat_id, span);
 807             }
 808
 809             _ => self.lower_lit(expr)
 810         };
 811
 812         Pattern {
 813             span,
 814             ty: pat_ty,
 815             kind: Box::new(kind),
 816         }
 817     }
 818 }
 819
 820 pub trait PatternFoldable<'tcx> : Sized {
 821     fn fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
 822         self.super_fold_with(folder)
 823     }
 824
 825     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self;
 826 }
 827
 828 pub trait PatternFolder<'tcx> : Sized {
 829     fn fold_pattern(&mut self, pattern: &Pattern<'tcx>) -> Pattern<'tcx> {
 830         pattern.super_fold_with(self)
 831     }
 832
 833     fn fold_pattern_kind(&mut self, kind: &PatternKind<'tcx>) -> PatternKind<'tcx> {
 834         kind.super_fold_with(self)
 835     }
 836 }
 837
 838
 839 impl<'tcx, T: PatternFoldable<'tcx>> PatternFoldable<'tcx> for Box<T> {
 840     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
 841         let content: T = (**self).fold_with(folder);
 842         box content
 843     }
 844 }
 845
 846 impl<'tcx, T: PatternFoldable<'tcx>> PatternFoldable<'tcx> for Vec<T> {
 847     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
 848         self.iter().map(|t| t.fold_with(folder)).collect()
 849     }
 850 }
 851
 852 impl<'tcx, T: PatternFoldable<'tcx>> PatternFoldable<'tcx> for Option<T> {
 853     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self{
 854         self.as_ref().map(|t| t.fold_with(folder))
 855     }
 856 }
 857
 858 macro_rules! CloneImpls {
 859     (<$lt_tcx:tt> $($ty:ty),+) => {
 860         $(
 861             impl<$lt_tcx> PatternFoldable<$lt_tcx> for $ty {
 862                 fn super_fold_with<F: PatternFolder<$lt_tcx>>(&self, _: &mut F) -> Self {
 863                     Clone::clone(self)
 864                 }
 865             }
 866         )+
 867     }
 868 }
 869
 870 CloneImpls!{ <'tcx>
 871     Span, Field, Mutability, ast::Name, ast::NodeId, usize, &'tcx ty::Const<'tcx>,
 872     Region<'tcx>, Ty<'tcx>, BindingMode<'tcx>, &'tcx AdtDef,
 873     &'tcx Substs<'tcx>, &'tcx Kind<'tcx>
 874 }
 875
 876 impl<'tcx> PatternFoldable<'tcx> for FieldPattern<'tcx> {
 877     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
 878         FieldPattern {
 879             field: self.field.fold_with(folder),
 880             pattern: self.pattern.fold_with(folder)
 881         }
 882     }
 883 }
 884
 885 impl<'tcx> PatternFoldable<'tcx> for Pattern<'tcx> {
 886     fn fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
 887         folder.fold_pattern(self)
 888     }
 889
 890     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
 891         Pattern {
 892             ty: self.ty.fold_with(folder),
 893             span: self.span.fold_with(folder),
 894             kind: self.kind.fold_with(folder)
 895         }
 896     }
 897 }
 898
 899 impl<'tcx> PatternFoldable<'tcx> for PatternKind<'tcx> {
 900     fn fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
 901         folder.fold_pattern_kind(self)
 902     }
 903
 904     fn super_fold_with<F: PatternFolder<'tcx>>(&self, folder: &mut F) -> Self {
 905         match *self {
 906             PatternKind::Wild => PatternKind::Wild,
 907             PatternKind::Binding {
 908                 mutability,
 909                 name,
 910                 mode,
 911                 var,
 912                 ty,
 913                 ref subpattern,
 914             } => PatternKind::Binding {
 915                 mutability: mutability.fold_with(folder),
 916                 name: name.fold_with(folder),
 917                 mode: mode.fold_with(folder),
 918                 var: var.fold_with(folder),
 919                 ty: ty.fold_with(folder),
 920                 subpattern: subpattern.fold_with(folder),
 921             },
 922             PatternKind::Variant {
 923                 adt_def,
 924                 substs,
 925                 variant_index,
 926                 ref subpatterns,
 927             } => PatternKind::Variant {
 928                 adt_def: adt_def.fold_with(folder),
 929                 substs: substs.fold_with(folder),
 930                 variant_index: variant_index.fold_with(folder),
 931                 subpatterns: subpatterns.fold_with(folder)
 932             },
 933             PatternKind::Leaf {
 934                 ref subpatterns,
 935             } => PatternKind::Leaf {
 936                 subpatterns: subpatterns.fold_with(folder),
 937             },
 938             PatternKind::Deref {
 939                 ref subpattern,
 940             } => PatternKind::Deref {
 941                 subpattern: subpattern.fold_with(folder),
 942             },
 943             PatternKind::Constant {
 944                 value
 945             } => PatternKind::Constant {
 946                 value: value.fold_with(folder)
 947             },
 948             PatternKind::Range {
 949                 lo,
 950                 hi,
 951                 end,
 952             } => PatternKind::Range {
 953                 lo: lo.fold_with(folder),
 954                 hi: hi.fold_with(folder),
 955                 end,
 956             },
 957             PatternKind::Slice {
 958                 ref prefix,
 959                 ref slice,
 960                 ref suffix,
 961             } => PatternKind::Slice {
 962                 prefix: prefix.fold_with(folder),
 963                 slice: slice.fold_with(folder),
 964                 suffix: suffix.fold_with(folder)
 965             },
 966             PatternKind::Array {
 967                 ref prefix,
 968                 ref slice,
 969                 ref suffix
 970             } => PatternKind::Array {
 971                 prefix: prefix.fold_with(folder),
 972                 slice: slice.fold_with(folder),
 973                 suffix: suffix.fold_with(folder)
 974             },
 975         }
 976     }
 977 }