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