src/libsyntax_ext/deriving/generic/mod.rs

   1 // Copyright 2013-2014 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 //! Some code that abstracts away much of the boilerplate of writing
  12 //! `derive` instances for traits. Among other things it manages getting
  13 //! access to the fields of the 4 different sorts of structs and enum
  14 //! variants, as well as creating the method and impl ast instances.
  15 //!
  16 //! Supported features (fairly exhaustive):
  17 //!
  18 //! - Methods taking any number of parameters of any type, and returning
  19 //!   any type, other than vectors, bottom and closures.
  20 //! - Generating `impl`s for types with type parameters and lifetimes
  21 //!   (e.g. `Option<T>`), the parameters are automatically given the
  22 //!   current trait as a bound. (This includes separate type parameters
  23 //!   and lifetimes for methods.)
  24 //! - Additional bounds on the type parameters (`TraitDef.additional_bounds`)
  25 //!
  26 //! The most important thing for implementers is the `Substructure` and
  27 //! `SubstructureFields` objects. The latter groups 5 possibilities of the
  28 //! arguments:
  29 //!
  30 //! - `Struct`, when `Self` is a struct (including tuple structs, e.g
  31 //!   `struct T(i32, char)`).
  32 //! - `EnumMatching`, when `Self` is an enum and all the arguments are the
  33 //!   same variant of the enum (e.g. `Some(1)`, `Some(3)` and `Some(4)`)
  34 //! - `EnumNonMatchingCollapsed` when `Self` is an enum and the arguments
  35 //!   are not the same variant (e.g. `None`, `Some(1)` and `None`).
  36 //! - `StaticEnum` and `StaticStruct` for static methods, where the type
  37 //!   being derived upon is either an enum or struct respectively. (Any
  38 //!   argument with type Self is just grouped among the non-self
  39 //!   arguments.)
  40 //!
  41 //! In the first two cases, the values from the corresponding fields in
  42 //! all the arguments are grouped together. For `EnumNonMatchingCollapsed`
  43 //! this isn't possible (different variants have different fields), so the
  44 //! fields are inaccessible. (Previous versions of the deriving infrastructure
  45 //! had a way to expand into code that could access them, at the cost of
  46 //! generating exponential amounts of code; see issue #15375). There are no
  47 //! fields with values in the static cases, so these are treated entirely
  48 //! differently.
  49 //!
  50 //! The non-static cases have `Option<ident>` in several places associated
  51 //! with field `expr`s. This represents the name of the field it is
  52 //! associated with. It is only not `None` when the associated field has
  53 //! an identifier in the source code. For example, the `x`s in the
  54 //! following snippet
  55 //!
  56 //! ```rust
  57 //! # #![allow(dead_code)]
  58 //! struct A { x : i32 }
  59 //!
  60 //! struct B(i32);
  61 //!
  62 //! enum C {
  63 //!     C0(i32),
  64 //!     C1 { x: i32 }
  65 //! }
  66 //! ```
  67 //!
  68 //! The `i32`s in `B` and `C0` don't have an identifier, so the
  69 //! `Option<ident>`s would be `None` for them.
  70 //!
  71 //! In the static cases, the structure is summarised, either into the just
  72 //! spans of the fields or a list of spans and the field idents (for tuple
  73 //! structs and record structs, respectively), or a list of these, for
  74 //! enums (one for each variant). For empty struct and empty enum
  75 //! variants, it is represented as a count of 0.
  76 //!
  77 //! # "`cs`" functions
  78 //!
  79 //! The `cs_...` functions ("combine substructure) are designed to
  80 //! make life easier by providing some pre-made recipes for common
  81 //! threads; mostly calling the function being derived on all the
  82 //! arguments and then combining them back together in some way (or
  83 //! letting the user chose that). They are not meant to be the only
  84 //! way to handle the structures that this code creates.
  85 //!
  86 //! # Examples
  87 //!
  88 //! The following simplified `PartialEq` is used for in-code examples:
  89 //!
  90 //! ```rust
  91 //! trait PartialEq {
  92 //!     fn eq(&self, other: &Self) -> bool;
  93 //! }
  94 //! impl PartialEq for i32 {
  95 //!     fn eq(&self, other: &i32) -> bool {
  96 //!         *self == *other
  97 //!     }
  98 //! }
  99 //! ```
 100 //!
 101 //! Some examples of the values of `SubstructureFields` follow, using the
 102 //! above `PartialEq`, `A`, `B` and `C`.
 103 //!
 104 //! ## Structs
 105 //!
 106 //! When generating the `expr` for the `A` impl, the `SubstructureFields` is
 107 //!
 108 //! ```{.text}
 109 //! Struct(vec![FieldInfo {
 110 //!            span: <span of x>
 111 //!            name: Some(<ident of x>),
 112 //!            self_: <expr for &self.x>,
 113 //!            other: vec![<expr for &other.x]
 114 //!          }])
 115 //! ```
 116 //!
 117 //! For the `B` impl, called with `B(a)` and `B(b)`,
 118 //!
 119 //! ```{.text}
 120 //! Struct(vec![FieldInfo {
 121 //!           span: <span of `i32`>,
 122 //!           name: None,
 123 //!           self_: <expr for &a>
 124 //!           other: vec![<expr for &b>]
 125 //!          }])
 126 //! ```
 127 //!
 128 //! ## Enums
 129 //!
 130 //! When generating the `expr` for a call with `self == C0(a)` and `other
 131 //! == C0(b)`, the SubstructureFields is
 132 //!
 133 //! ```{.text}
 134 //! EnumMatching(0, <ast::Variant for C0>,
 135 //!              vec![FieldInfo {
 136 //!                 span: <span of i32>
 137 //!                 name: None,
 138 //!                 self_: <expr for &a>,
 139 //!                 other: vec![<expr for &b>]
 140 //!               }])
 141 //! ```
 142 //!
 143 //! For `C1 {x}` and `C1 {x}`,
 144 //!
 145 //! ```{.text}
 146 //! EnumMatching(1, <ast::Variant for C1>,
 147 //!              vec![FieldInfo {
 148 //!                 span: <span of x>
 149 //!                 name: Some(<ident of x>),
 150 //!                 self_: <expr for &self.x>,
 151 //!                 other: vec![<expr for &other.x>]
 152 //!                }])
 153 //! ```
 154 //!
 155 //! For `C0(a)` and `C1 {x}` ,
 156 //!
 157 //! ```{.text}
 158 //! EnumNonMatchingCollapsed(
 159 //!     vec![<ident of self>, <ident of __arg_1>],
 160 //!     &[<ast::Variant for C0>, <ast::Variant for C1>],
 161 //!     &[<ident for self index value>, <ident of __arg_1 index value>])
 162 //! ```
 163 //!
 164 //! It is the same for when the arguments are flipped to `C1 {x}` and
 165 //! `C0(a)`; the only difference is what the values of the identifiers
 166 //! <ident for self index value> and <ident of __arg_1 index value> will
 167 //! be in the generated code.
 168 //!
 169 //! `EnumNonMatchingCollapsed` deliberately provides far less information
 170 //! than is generally available for a given pair of variants; see #15375
 171 //! for discussion.
 172 //!
 173 //! ## Static
 174 //!
 175 //! A static method on the types above would result in,
 176 //!
 177 //! ```{.text}
 178 //! StaticStruct(<ast::VariantData of A>, Named(vec![(<ident of x>, <span of x>)]))
 179 //!
 180 //! StaticStruct(<ast::VariantData of B>, Unnamed(vec![<span of x>]))
 181 //!
 182 //! StaticEnum(<ast::EnumDef of C>,
 183 //!            vec![(<ident of C0>, <span of C0>, Unnamed(vec![<span of i32>])),
 184 //!                 (<ident of C1>, <span of C1>, Named(vec![(<ident of x>, <span of x>)]))])
 185 //! ```
 186
 187 pub use self::StaticFields::*;
 188 pub use self::SubstructureFields::*;
 189 use self::StructType::*;
 190
 191 use std::cell::RefCell;
 192 use std::collections::HashSet;
 193 use std::vec;
 194
 195 use syntax::abi::Abi;
 196 use syntax::abi;
 197 use syntax::ast;
 198 use syntax::ast::{EnumDef, Expr, Ident, Generics, VariantData};
 199 use syntax::ast_util;
 200 use syntax::attr;
 201 use syntax::attr::AttrMetaMethods;
 202 use syntax::ext::base::{ExtCtxt, Annotatable};
 203 use syntax::ext::build::AstBuilder;
 204 use syntax::codemap::{self, DUMMY_SP};
 205 use syntax::codemap::Span;
 206 use syntax::errors::Handler;
 207 use syntax::util::move_map::MoveMap;
 208 use syntax::owned_slice::OwnedSlice;
 209 use syntax::parse::token::{intern, InternedString};
 210 use syntax::parse::token::special_idents;
 211 use syntax::ptr::P;
 212
 213 use self::ty::{LifetimeBounds, Path, Ptr, PtrTy, Self_, Ty};
 214
 215 pub mod ty;
 216
 217 pub struct TraitDef<'a> {
 218     /// The span for the current #[derive(Foo)] header.
 219     pub span: Span,
 220
 221     pub attributes: Vec<ast::Attribute>,
 222
 223     /// Path of the trait, including any type parameters
 224     pub path: Path<'a>,
 225
 226     /// Additional bounds required of any type parameters of the type,
 227     /// other than the current trait
 228     pub additional_bounds: Vec<Ty<'a>>,
 229
 230     /// Any extra lifetimes and/or bounds, e.g. `D: serialize::Decoder`
 231     pub generics: LifetimeBounds<'a>,
 232
 233     /// Is it an `unsafe` trait?
 234     pub is_unsafe: bool,
 235
 236     pub methods: Vec<MethodDef<'a>>,
 237
 238     pub associated_types: Vec<(ast::Ident, Ty<'a>)>,
 239 }
 240
 241
 242 pub struct MethodDef<'a> {
 243     /// name of the method
 244     pub name: &'a str,
 245     /// List of generics, e.g. `R: rand::Rng`
 246     pub generics: LifetimeBounds<'a>,
 247
 248     /// Whether there is a self argument (outer Option) i.e. whether
 249     /// this is a static function, and whether it is a pointer (inner
 250     /// Option)
 251     pub explicit_self: Option<Option<PtrTy<'a>>>,
 252
 253     /// Arguments other than the self argument
 254     pub args: Vec<Ty<'a>>,
 255
 256     /// Return type
 257     pub ret_ty: Ty<'a>,
 258
 259     pub attributes: Vec<ast::Attribute>,
 260
 261     // Is it an `unsafe fn`?
 262     pub is_unsafe: bool,
 263
 264     pub combine_substructure: RefCell<CombineSubstructureFunc<'a>>,
 265 }
 266
 267 /// All the data about the data structure/method being derived upon.
 268 pub struct Substructure<'a> {
 269     /// ident of self
 270     pub type_ident: Ident,
 271     /// ident of the method
 272     pub method_ident: Ident,
 273     /// dereferenced access to any `Self_` or `Ptr(Self_, _)` arguments
 274     pub self_args: &'a [P<Expr>],
 275     /// verbatim access to any other arguments
 276     pub nonself_args: &'a [P<Expr>],
 277     pub fields: &'a SubstructureFields<'a>
 278 }
 279
 280 /// Summary of the relevant parts of a struct/enum field.
 281 pub struct FieldInfo<'a> {
 282     pub span: Span,
 283     /// None for tuple structs/normal enum variants, Some for normal
 284     /// structs/struct enum variants.
 285     pub name: Option<Ident>,
 286     /// The expression corresponding to this field of `self`
 287     /// (specifically, a reference to it).
 288     pub self_: P<Expr>,
 289     /// The expressions corresponding to references to this field in
 290     /// the other `Self` arguments.
 291     pub other: Vec<P<Expr>>,
 292     /// The attributes on the field
 293     pub attrs: &'a [ast::Attribute],
 294 }
 295
 296 /// Fields for a static method
 297 pub enum StaticFields {
 298     /// Tuple structs/enum variants like this.
 299     Unnamed(Vec<Span>),
 300     /// Normal structs/struct variants.
 301     Named(Vec<(Ident, Span)>),
 302 }
 303
 304 /// A summary of the possible sets of fields.
 305 pub enum SubstructureFields<'a> {
 306     Struct(Vec<FieldInfo<'a>>),
 307     /// Matching variants of the enum: variant index, ast::Variant,
 308     /// fields: the field name is only non-`None` in the case of a struct
 309     /// variant.
 310     EnumMatching(usize, &'a ast::Variant, Vec<FieldInfo<'a>>),
 311
 312     /// Non-matching variants of the enum, but with all state hidden from
 313     /// the consequent code.  The first component holds `Ident`s for all of
 314     /// the `Self` arguments; the second component is a slice of all of the
 315     /// variants for the enum itself, and the third component is a list of
 316     /// `Ident`s bound to the variant index values for each of the actual
 317     /// input `Self` arguments.
 318     EnumNonMatchingCollapsed(Vec<Ident>, &'a [P<ast::Variant>], &'a [Ident]),
 319
 320     /// A static method where `Self` is a struct.
 321     StaticStruct(&'a ast::VariantData, StaticFields),
 322     /// A static method where `Self` is an enum.
 323     StaticEnum(&'a ast::EnumDef, Vec<(Ident, Span, StaticFields)>),
 324 }
 325
 326
 327
 328 /// Combine the values of all the fields together. The last argument is
 329 /// all the fields of all the structures.
 330 pub type CombineSubstructureFunc<'a> =
 331     Box<FnMut(&mut ExtCtxt, Span, &Substructure) -> P<Expr> + 'a>;
 332
 333 /// Deal with non-matching enum variants.  The tuple is a list of
 334 /// identifiers (one for each `Self` argument, which could be any of the
 335 /// variants since they have been collapsed together) and the identifiers
 336 /// holding the variant index value for each of the `Self` arguments.  The
 337 /// last argument is all the non-`Self` args of the method being derived.
 338 pub type EnumNonMatchCollapsedFunc<'a> =
 339     Box<FnMut(&mut ExtCtxt, Span, (&[Ident], &[Ident]), &[P<Expr>]) -> P<Expr> + 'a>;
 340
 341 pub fn combine_substructure<'a>(f: CombineSubstructureFunc<'a>)
 342     -> RefCell<CombineSubstructureFunc<'a>> {
 343     RefCell::new(f)
 344 }
 345
 346 /// This method helps to extract all the type parameters referenced from a
 347 /// type. For a type parameter `<T>`, it looks for either a `TyPath` that
 348 /// is not global and starts with `T`, or a `TyQPath`.
 349 fn find_type_parameters(ty: &ast::Ty, ty_param_names: &[ast::Name]) -> Vec<P<ast::Ty>> {
 350     use syntax::visit;
 351
 352     struct Visitor<'a> {
 353         ty_param_names: &'a [ast::Name],
 354         types: Vec<P<ast::Ty>>,
 355     }
 356
 357     impl<'a> visit::Visitor<'a> for Visitor<'a> {
 358         fn visit_ty(&mut self, ty: &'a ast::Ty) {
 359             match ty.node {
 360                 ast::TyPath(_, ref path) if !path.global => {
 361                     match path.segments.first() {
 362                         Some(segment) => {
 363                             if self.ty_param_names.contains(&segment.identifier.name) {
 364                                 self.types.push(P(ty.clone()));
 365                             }
 366                         }
 367                         None => {}
 368                     }
 369                 }
 370                 _ => {}
 371             }
 372
 373             visit::walk_ty(self, ty)
 374         }
 375     }
 376
 377     let mut visitor = Visitor {
 378         ty_param_names: ty_param_names,
 379         types: Vec::new(),
 380     };
 381
 382     visit::Visitor::visit_ty(&mut visitor, ty);
 383
 384     visitor.types
 385 }
 386
 387 impl<'a> TraitDef<'a> {
 388     pub fn expand(&self,
 389                   cx: &mut ExtCtxt,
 390                   mitem: &ast::MetaItem,
 391                   item: &'a Annotatable,
 392                   push: &mut FnMut(Annotatable))
 393     {
 394         match *item {
 395             Annotatable::Item(ref item) => {
 396                 let newitem = match item.node {
 397                     ast::ItemStruct(ref struct_def, ref generics) => {
 398                         self.expand_struct_def(cx,
 399                                                &struct_def,
 400                                                item.ident,
 401                                                generics)
 402                     }
 403                     ast::ItemEnum(ref enum_def, ref generics) => {
 404                         self.expand_enum_def(cx,
 405                                              enum_def,
 406                                              &item.attrs,
 407                                              item.ident,
 408                                              generics)
 409                     }
 410                     _ => {
 411                         cx.span_err(mitem.span,
 412                                     "`derive` may only be applied to structs and enums");
 413                         return;
 414                     }
 415                 };
 416                 // Keep the lint attributes of the previous item to control how the
 417                 // generated implementations are linted
 418                 let mut attrs = newitem.attrs.clone();
 419                 attrs.extend(item.attrs.iter().filter(|a| {
 420                     match &a.name()[..] {
 421                         "allow" | "warn" | "deny" | "forbid" | "stable" | "unstable" => true,
 422                         _ => false,
 423                     }
 424                 }).cloned());
 425                 push(Annotatable::Item(P(ast::Item {
 426                     attrs: attrs,
 427                     ..(*newitem).clone()
 428                 })))
 429             }
 430             _ => {
 431                 cx.span_err(mitem.span, "`derive` may only be applied to structs and enums");
 432             }
 433         }
 434     }
 435
 436     /// Given that we are deriving a trait `DerivedTrait` for a type like:
 437     ///
 438     /// ```ignore
 439     /// struct Struct<'a, ..., 'z, A, B: DeclaredTrait, C, ..., Z> where C: WhereTrait {
 440     ///     a: A,
 441     ///     b: B::Item,
 442     ///     b1: <B as DeclaredTrait>::Item,
 443     ///     c1: <C as WhereTrait>::Item,
 444     ///     c2: Option<<C as WhereTrait>::Item>,
 445     ///     ...
 446     /// }
 447     /// ```
 448     ///
 449     /// create an impl like:
 450     ///
 451     /// ```ignore
 452     /// impl<'a, ..., 'z, A, B: DeclaredTrait, C, ...  Z> where
 453     ///     C:                       WhereTrait,
 454     ///     A: DerivedTrait + B1 + ... + BN,
 455     ///     B: DerivedTrait + B1 + ... + BN,
 456     ///     C: DerivedTrait + B1 + ... + BN,
 457     ///     B::Item:                 DerivedTrait + B1 + ... + BN,
 458     ///     <C as WhereTrait>::Item: DerivedTrait + B1 + ... + BN,
 459     ///     ...
 460     /// {
 461     ///     ...
 462     /// }
 463     /// ```
 464     ///
 465     /// where B1, ..., BN are the bounds given by `bounds_paths`.'. Z is a phantom type, and
 466     /// therefore does not get bound by the derived trait.
 467     fn create_derived_impl(&self,
 468                            cx: &mut ExtCtxt,
 469                            type_ident: Ident,
 470                            generics: &Generics,
 471                            field_tys: Vec<P<ast::Ty>>,
 472                            methods: Vec<P<ast::ImplItem>>) -> P<ast::Item> {
 473         let trait_path = self.path.to_path(cx, self.span, type_ident, generics);
 474
 475         // Transform associated types from `deriving::ty::Ty` into `ast::ImplItem`
 476         let associated_types = self.associated_types.iter().map(|&(ident, ref type_def)| {
 477             P(ast::ImplItem {
 478                 id: ast::DUMMY_NODE_ID,
 479                 span: self.span,
 480                 ident: ident,
 481                 vis: ast::Inherited,
 482                 attrs: Vec::new(),
 483                 node: ast::ImplItemKind::Type(type_def.to_ty(cx,
 484                     self.span,
 485                     type_ident,
 486                     generics
 487                 )),
 488             })
 489         });
 490
 491         let Generics { mut lifetimes, ty_params, mut where_clause } =
 492             self.generics.to_generics(cx, self.span, type_ident, generics);
 493         let mut ty_params = ty_params.into_vec();
 494
 495         // Copy the lifetimes
 496         lifetimes.extend(generics.lifetimes.iter().cloned());
 497
 498         // Create the type parameters.
 499         ty_params.extend(generics.ty_params.iter().map(|ty_param| {
 500             // I don't think this can be moved out of the loop, since
 501             // a TyParamBound requires an ast id
 502             let mut bounds: Vec<_> =
 503                 // extra restrictions on the generics parameters to the type being derived upon
 504                 self.additional_bounds.iter().map(|p| {
 505                     cx.typarambound(p.to_path(cx, self.span,
 506                                                   type_ident, generics))
 507                 }).collect();
 508
 509             // require the current trait
 510             bounds.push(cx.typarambound(trait_path.clone()));
 511
 512             // also add in any bounds from the declaration
 513             for declared_bound in ty_param.bounds.iter() {
 514                 bounds.push((*declared_bound).clone());
 515             }
 516
 517             cx.typaram(self.span,
 518                        ty_param.ident,
 519                        OwnedSlice::from_vec(bounds),
 520                        None)
 521         }));
 522
 523         // and similarly for where clauses
 524         where_clause.predicates.extend(generics.where_clause.predicates.iter().map(|clause| {
 525             match *clause {
 526                 ast::WherePredicate::BoundPredicate(ref wb) => {
 527                     ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate {
 528                         span: self.span,
 529                         bound_lifetimes: wb.bound_lifetimes.clone(),
 530                         bounded_ty: wb.bounded_ty.clone(),
 531                         bounds: OwnedSlice::from_vec(wb.bounds.iter().cloned().collect())
 532                     })
 533                 }
 534                 ast::WherePredicate::RegionPredicate(ref rb) => {
 535                     ast::WherePredicate::RegionPredicate(ast::WhereRegionPredicate {
 536                         span: self.span,
 537                         lifetime: rb.lifetime,
 538                         bounds: rb.bounds.iter().cloned().collect()
 539                     })
 540                 }
 541                 ast::WherePredicate::EqPredicate(ref we) => {
 542                     ast::WherePredicate::EqPredicate(ast::WhereEqPredicate {
 543                         id: ast::DUMMY_NODE_ID,
 544                         span: self.span,
 545                         path: we.path.clone(),
 546                         ty: we.ty.clone()
 547                     })
 548                 }
 549             }
 550         }));
 551
 552         if !ty_params.is_empty() {
 553             let ty_param_names: Vec<ast::Name> = ty_params.iter()
 554                 .map(|ty_param| ty_param.ident.name)
 555                 .collect();
 556
 557             let mut processed_field_types = HashSet::new();
 558             for field_ty in field_tys {
 559                 let tys = find_type_parameters(&*field_ty, &ty_param_names);
 560
 561                 for ty in tys {
 562                     // if we have already handled this type, skip it
 563                     if let ast::TyPath(_, ref p) = ty.node {
 564                         if p.segments.len() == 1
 565                             && ty_param_names.contains(&p.segments[0].identifier.name)
 566                             || processed_field_types.contains(&p.segments) {
 567                             continue;
 568                         };
 569                         processed_field_types.insert(p.segments.clone());
 570                     }
 571                     let mut bounds: Vec<_> = self.additional_bounds.iter().map(|p| {
 572                         cx.typarambound(p.to_path(cx, self.span, type_ident, generics))
 573                     }).collect();
 574
 575                     // require the current trait
 576                     bounds.push(cx.typarambound(trait_path.clone()));
 577
 578                     let predicate = ast::WhereBoundPredicate {
 579                         span: self.span,
 580                         bound_lifetimes: vec![],
 581                         bounded_ty: ty,
 582                         bounds: OwnedSlice::from_vec(bounds),
 583                     };
 584
 585                     let predicate = ast::WherePredicate::BoundPredicate(predicate);
 586                     where_clause.predicates.push(predicate);
 587                 }
 588             }
 589         }
 590
 591         let trait_generics = Generics {
 592             lifetimes: lifetimes,
 593             ty_params: OwnedSlice::from_vec(ty_params),
 594             where_clause: where_clause
 595         };
 596
 597         // Create the reference to the trait.
 598         let trait_ref = cx.trait_ref(trait_path);
 599
 600         // Create the type parameters on the `self` path.
 601         let self_ty_params = generics.ty_params.map(|ty_param| {
 602             cx.ty_ident(self.span, ty_param.ident)
 603         });
 604
 605         let self_lifetimes: Vec<ast::Lifetime> =
 606             generics.lifetimes
 607             .iter()
 608             .map(|ld| ld.lifetime)
 609             .collect();
 610
 611         // Create the type of `self`.
 612         let self_type = cx.ty_path(
 613             cx.path_all(self.span, false, vec!( type_ident ), self_lifetimes,
 614                         self_ty_params.into_vec(), Vec::new()));
 615
 616         let attr = cx.attribute(
 617             self.span,
 618             cx.meta_word(self.span,
 619                          InternedString::new("automatically_derived")));
 620         // Just mark it now since we know that it'll end up used downstream
 621         attr::mark_used(&attr);
 622         let opt_trait_ref = Some(trait_ref);
 623         let ident = ast_util::impl_pretty_name(&opt_trait_ref, Some(&*self_type));
 624         let unused_qual = cx.attribute(
 625             self.span,
 626             cx.meta_list(self.span,
 627                          InternedString::new("allow"),
 628                          vec![cx.meta_word(self.span,
 629                                            InternedString::new("unused_qualifications"))]));
 630         let mut a = vec![attr, unused_qual];
 631         a.extend(self.attributes.iter().cloned());
 632
 633         let unsafety = if self.is_unsafe {
 634             ast::Unsafety::Unsafe
 635         } else {
 636             ast::Unsafety::Normal
 637         };
 638
 639         cx.item(
 640             self.span,
 641             ident,
 642             a,
 643             ast::ItemImpl(unsafety,
 644                           ast::ImplPolarity::Positive,
 645                           trait_generics,
 646                           opt_trait_ref,
 647                           self_type,
 648                           methods.into_iter().chain(associated_types).collect()))
 649     }
 650
 651     fn expand_struct_def(&self,
 652                          cx: &mut ExtCtxt,
 653                          struct_def: &'a VariantData,
 654                          type_ident: Ident,
 655                          generics: &Generics) -> P<ast::Item> {
 656         let field_tys: Vec<P<ast::Ty>> = struct_def.fields().iter()
 657             .map(|field| field.node.ty.clone())
 658             .collect();
 659
 660         let methods = self.methods.iter().map(|method_def| {
 661             let (explicit_self, self_args, nonself_args, tys) =
 662                 method_def.split_self_nonself_args(
 663                     cx, self, type_ident, generics);
 664
 665             let body = if method_def.is_static() {
 666                 method_def.expand_static_struct_method_body(
 667                     cx,
 668                     self,
 669                     struct_def,
 670                     type_ident,
 671                     &self_args[..],
 672                     &nonself_args[..])
 673             } else {
 674                 method_def.expand_struct_method_body(cx,
 675                                                      self,
 676                                                      struct_def,
 677                                                      type_ident,
 678                                                      &self_args[..],
 679                                                      &nonself_args[..])
 680             };
 681
 682             method_def.create_method(cx,
 683                                      self,
 684                                      type_ident,
 685                                      generics,
 686                                      abi::Rust,
 687                                      explicit_self,
 688                                      tys,
 689                                      body)
 690         }).collect();
 691
 692         self.create_derived_impl(cx, type_ident, generics, field_tys, methods)
 693     }
 694
 695     fn expand_enum_def(&self,
 696                        cx: &mut ExtCtxt,
 697                        enum_def: &'a EnumDef,
 698                        type_attrs: &[ast::Attribute],
 699                        type_ident: Ident,
 700                        generics: &Generics) -> P<ast::Item> {
 701         let mut field_tys = Vec::new();
 702
 703         for variant in &enum_def.variants {
 704             field_tys.extend(variant.node.data.fields().iter()
 705                 .map(|field| field.node.ty.clone()));
 706         }
 707
 708         let methods = self.methods.iter().map(|method_def| {
 709             let (explicit_self, self_args, nonself_args, tys) =
 710                 method_def.split_self_nonself_args(cx, self,
 711                                                    type_ident, generics);
 712
 713             let body = if method_def.is_static() {
 714                 method_def.expand_static_enum_method_body(
 715                     cx,
 716                     self,
 717                     enum_def,
 718                     type_ident,
 719                     &self_args[..],
 720                     &nonself_args[..])
 721             } else {
 722                 method_def.expand_enum_method_body(cx,
 723                                                    self,
 724                                                    enum_def,
 725                                                    type_attrs,
 726                                                    type_ident,
 727                                                    self_args,
 728                                                    &nonself_args[..])
 729             };
 730
 731             method_def.create_method(cx,
 732                                      self,
 733                                      type_ident,
 734                                      generics,
 735                                      abi::Rust,
 736                                      explicit_self,
 737                                      tys,
 738                                      body)
 739         }).collect();
 740
 741         self.create_derived_impl(cx, type_ident, generics, field_tys, methods)
 742     }
 743 }
 744
 745 fn find_repr_type_name(diagnostic: &Handler,
 746                        type_attrs: &[ast::Attribute]) -> &'static str {
 747     let mut repr_type_name = "i32";
 748     for a in type_attrs {
 749         for r in &attr::find_repr_attrs(diagnostic, a) {
 750             repr_type_name = match *r {
 751                 attr::ReprAny | attr::ReprPacked | attr::ReprSimd => continue,
 752                 attr::ReprExtern => "i32",
 753
 754                 attr::ReprInt(_, attr::SignedInt(ast::TyIs)) => "isize",
 755                 attr::ReprInt(_, attr::SignedInt(ast::TyI8)) => "i8",
 756                 attr::ReprInt(_, attr::SignedInt(ast::TyI16)) => "i16",
 757                 attr::ReprInt(_, attr::SignedInt(ast::TyI32)) => "i32",
 758                 attr::ReprInt(_, attr::SignedInt(ast::TyI64)) => "i64",
 759
 760                 attr::ReprInt(_, attr::UnsignedInt(ast::TyUs)) => "usize",
 761                 attr::ReprInt(_, attr::UnsignedInt(ast::TyU8)) => "u8",
 762                 attr::ReprInt(_, attr::UnsignedInt(ast::TyU16)) => "u16",
 763                 attr::ReprInt(_, attr::UnsignedInt(ast::TyU32)) => "u32",
 764                 attr::ReprInt(_, attr::UnsignedInt(ast::TyU64)) => "u64",
 765             }
 766         }
 767     }
 768     repr_type_name
 769 }
 770
 771 impl<'a> MethodDef<'a> {
 772     fn call_substructure_method(&self,
 773                                 cx: &mut ExtCtxt,
 774                                 trait_: &TraitDef,
 775                                 type_ident: Ident,
 776                                 self_args: &[P<Expr>],
 777                                 nonself_args: &[P<Expr>],
 778                                 fields: &SubstructureFields)
 779         -> P<Expr> {
 780         let substructure = Substructure {
 781             type_ident: type_ident,
 782             method_ident: cx.ident_of(self.name),
 783             self_args: self_args,
 784             nonself_args: nonself_args,
 785             fields: fields
 786         };
 787         let mut f = self.combine_substructure.borrow_mut();
 788         let f: &mut CombineSubstructureFunc = &mut *f;
 789         f(cx, trait_.span, &substructure)
 790     }
 791
 792     fn get_ret_ty(&self,
 793                   cx: &mut ExtCtxt,
 794                   trait_: &TraitDef,
 795                   generics: &Generics,
 796                   type_ident: Ident)
 797                   -> P<ast::Ty> {
 798         self.ret_ty.to_ty(cx, trait_.span, type_ident, generics)
 799     }
 800
 801     fn is_static(&self) -> bool {
 802         self.explicit_self.is_none()
 803     }
 804
 805     fn split_self_nonself_args(&self,
 806                                cx: &mut ExtCtxt,
 807                                trait_: &TraitDef,
 808                                type_ident: Ident,
 809                                generics: &Generics)
 810         -> (ast::ExplicitSelf, Vec<P<Expr>>, Vec<P<Expr>>, Vec<(Ident, P<ast::Ty>)>) {
 811
 812         let mut self_args = Vec::new();
 813         let mut nonself_args = Vec::new();
 814         let mut arg_tys = Vec::new();
 815         let mut nonstatic = false;
 816
 817         let ast_explicit_self = match self.explicit_self {
 818             Some(ref self_ptr) => {
 819                 let (self_expr, explicit_self) =
 820                     ty::get_explicit_self(cx, trait_.span, self_ptr);
 821
 822                 self_args.push(self_expr);
 823                 nonstatic = true;
 824
 825                 explicit_self
 826             }
 827             None => codemap::respan(trait_.span, ast::SelfStatic),
 828         };
 829
 830         for (i, ty) in self.args.iter().enumerate() {
 831             let ast_ty = ty.to_ty(cx, trait_.span, type_ident, generics);
 832             let ident = cx.ident_of(&format!("__arg_{}", i));
 833             arg_tys.push((ident, ast_ty));
 834
 835             let arg_expr = cx.expr_ident(trait_.span, ident);
 836
 837             match *ty {
 838                 // for static methods, just treat any Self
 839                 // arguments as a normal arg
 840                 Self_ if nonstatic  => {
 841                     self_args.push(arg_expr);
 842                 }
 843                 Ptr(ref ty, _) if **ty == Self_ && nonstatic => {
 844                     self_args.push(cx.expr_deref(trait_.span, arg_expr))
 845                 }
 846                 _ => {
 847                     nonself_args.push(arg_expr);
 848                 }
 849             }
 850         }
 851
 852         (ast_explicit_self, self_args, nonself_args, arg_tys)
 853     }
 854
 855     fn create_method(&self,
 856                      cx: &mut ExtCtxt,
 857                      trait_: &TraitDef,
 858                      type_ident: Ident,
 859                      generics: &Generics,
 860                      abi: Abi,
 861                      explicit_self: ast::ExplicitSelf,
 862                      arg_types: Vec<(Ident, P<ast::Ty>)> ,
 863                      body: P<Expr>) -> P<ast::ImplItem> {
 864         // create the generics that aren't for Self
 865         let fn_generics = self.generics.to_generics(cx, trait_.span, type_ident, generics);
 866
 867         let self_arg = match explicit_self.node {
 868             ast::SelfStatic => None,
 869             // creating fresh self id
 870             _ => Some(ast::Arg::new_self(trait_.span, ast::MutImmutable, special_idents::self_))
 871         };
 872         let args = {
 873             let args = arg_types.into_iter().map(|(name, ty)| {
 874                     cx.arg(trait_.span, name, ty)
 875                 });
 876             self_arg.into_iter().chain(args).collect()
 877         };
 878
 879         let ret_type = self.get_ret_ty(cx, trait_, generics, type_ident);
 880
 881         let method_ident = cx.ident_of(self.name);
 882         let fn_decl = cx.fn_decl(args, ret_type);
 883         let body_block = cx.block_expr(body);
 884
 885         let unsafety = if self.is_unsafe {
 886             ast::Unsafety::Unsafe
 887         } else {
 888             ast::Unsafety::Normal
 889         };
 890
 891         // Create the method.
 892         P(ast::ImplItem {
 893             id: ast::DUMMY_NODE_ID,
 894             attrs: self.attributes.clone(),
 895             span: trait_.span,
 896             vis: ast::Inherited,
 897             ident: method_ident,
 898             node: ast::ImplItemKind::Method(ast::MethodSig {
 899                 generics: fn_generics,
 900                 abi: abi,
 901                 explicit_self: explicit_self,
 902                 unsafety: unsafety,
 903                 constness: ast::Constness::NotConst,
 904                 decl: fn_decl
 905             }, body_block)
 906         })
 907     }
 908
 909     /// ```ignore
 910     /// #[derive(PartialEq)]
 911     /// struct A { x: i32, y: i32 }
 912     ///
 913     /// // equivalent to:
 914     /// impl PartialEq for A {
 915     ///     fn eq(&self, __arg_1: &A) -> bool {
 916     ///         match *self {
 917     ///             A {x: ref __self_0_0, y: ref __self_0_1} => {
 918     ///                 match *__arg_1 {
 919     ///                     A {x: ref __self_1_0, y: ref __self_1_1} => {
 920     ///                         __self_0_0.eq(__self_1_0) && __self_0_1.eq(__self_1_1)
 921     ///                     }
 922     ///                 }
 923     ///             }
 924     ///         }
 925     ///     }
 926     /// }
 927     /// ```
 928     fn expand_struct_method_body<'b>(&self,
 929                                  cx: &mut ExtCtxt,
 930                                  trait_: &TraitDef<'b>,
 931                                  struct_def: &'b VariantData,
 932                                  type_ident: Ident,
 933                                  self_args: &[P<Expr>],
 934                                  nonself_args: &[P<Expr>])
 935         -> P<Expr> {
 936
 937         let mut raw_fields = Vec::new(); // Vec<[fields of self],
 938                                  // [fields of next Self arg], [etc]>
 939         let mut patterns = Vec::new();
 940         for i in 0..self_args.len() {
 941             let struct_path= cx.path(DUMMY_SP, vec!( type_ident ));
 942             let (pat, ident_expr) =
 943                 trait_.create_struct_pattern(cx,
 944                                              struct_path,
 945                                              struct_def,
 946                                              &format!("__self_{}",
 947                                                      i),
 948                                              ast::MutImmutable);
 949             patterns.push(pat);
 950             raw_fields.push(ident_expr);
 951         }
 952
 953         // transpose raw_fields
 954         let fields = if !raw_fields.is_empty() {
 955             let mut raw_fields = raw_fields.into_iter().map(|v| v.into_iter());
 956             let first_field = raw_fields.next().unwrap();
 957             let mut other_fields: Vec<vec::IntoIter<_>>
 958                 = raw_fields.collect();
 959             first_field.map(|(span, opt_id, field, attrs)| {
 960                 FieldInfo {
 961                     span: span,
 962                     name: opt_id,
 963                     self_: field,
 964                     other: other_fields.iter_mut().map(|l| {
 965                         match l.next().unwrap() {
 966                             (_, _, ex, _) => ex
 967                         }
 968                     }).collect(),
 969                     attrs: attrs,
 970                 }
 971             }).collect()
 972         } else {
 973             cx.span_bug(trait_.span,
 974                         "no self arguments to non-static method in generic \
 975                          `derive`")
 976         };
 977
 978         // body of the inner most destructuring match
 979         let mut body = self.call_substructure_method(
 980             cx,
 981             trait_,
 982             type_ident,
 983             self_args,
 984             nonself_args,
 985             &Struct(fields));
 986
 987         // make a series of nested matches, to destructure the
 988         // structs. This is actually right-to-left, but it shouldn't
 989         // matter.
 990         for (arg_expr, pat) in self_args.iter().zip(patterns) {
 991             body = cx.expr_match(trait_.span, arg_expr.clone(),
 992                                      vec!( cx.arm(trait_.span, vec!(pat.clone()), body) ))
 993         }
 994         body
 995     }
 996
 997     fn expand_static_struct_method_body(&self,
 998                                         cx: &mut ExtCtxt,
 999                                         trait_: &TraitDef,
1000                                         struct_def: &VariantData,
1001                                         type_ident: Ident,
1002                                         self_args: &[P<Expr>],
1003                                         nonself_args: &[P<Expr>])
1004         -> P<Expr> {
1005         let summary = trait_.summarise_struct(cx, struct_def);
1006
1007         self.call_substructure_method(cx,
1008                                       trait_,
1009                                       type_ident,
1010                                       self_args, nonself_args,
1011                                       &StaticStruct(struct_def, summary))
1012     }
1013
1014     /// ```ignore
1015     /// #[derive(PartialEq)]
1016     /// enum A {
1017     ///     A1,
1018     ///     A2(i32)
1019     /// }
1020     ///
1021     /// // is equivalent to
1022     ///
1023     /// impl PartialEq for A {
1024     ///     fn eq(&self, __arg_1: &A) -> ::bool {
1025     ///         match (&*self, &*__arg_1) {
1026     ///             (&A1, &A1) => true,
1027     ///             (&A2(ref __self_0),
1028     ///              &A2(ref __arg_1_0)) => (*__self_0).eq(&(*__arg_1_0)),
1029     ///             _ => {
1030     ///                 let __self_vi = match *self { A1(..) => 0, A2(..) => 1 };
1031     ///                 let __arg_1_vi = match *__arg_1 { A1(..) => 0, A2(..) => 1 };
1032     ///                 false
1033     ///             }
1034     ///         }
1035     ///     }
1036     /// }
1037     /// ```
1038     ///
1039     /// (Of course `__self_vi` and `__arg_1_vi` are unused for
1040     /// `PartialEq`, and those subcomputations will hopefully be removed
1041     /// as their results are unused.  The point of `__self_vi` and
1042     /// `__arg_1_vi` is for `PartialOrd`; see #15503.)
1043     fn expand_enum_method_body<'b>(&self,
1044                                cx: &mut ExtCtxt,
1045                                trait_: &TraitDef<'b>,
1046                                enum_def: &'b EnumDef,
1047                                type_attrs: &[ast::Attribute],
1048                                type_ident: Ident,
1049                                self_args: Vec<P<Expr>>,
1050                                nonself_args: &[P<Expr>])
1051                                -> P<Expr> {
1052         self.build_enum_match_tuple(
1053             cx, trait_, enum_def, type_attrs, type_ident, self_args, nonself_args)
1054     }
1055
1056
1057     /// Creates a match for a tuple of all `self_args`, where either all
1058     /// variants match, or it falls into a catch-all for when one variant
1059     /// does not match.
1060
1061     /// There are N + 1 cases because is a case for each of the N
1062     /// variants where all of the variants match, and one catch-all for
1063     /// when one does not match.
1064
1065     /// As an optimization we generate code which checks whether all variants
1066     /// match first which makes llvm see that C-like enums can be compiled into
1067     /// a simple equality check (for PartialEq).
1068
1069     /// The catch-all handler is provided access the variant index values
1070     /// for each of the self-args, carried in precomputed variables.
1071
1072     /// ```{.text}
1073     /// let __self0_vi = unsafe {
1074     ///     std::intrinsics::discriminant_value(&self) } as i32;
1075     /// let __self1_vi = unsafe {
1076     ///     std::intrinsics::discriminant_value(&__arg1) } as i32;
1077     /// let __self2_vi = unsafe {
1078     ///     std::intrinsics::discriminant_value(&__arg2) } as i32;
1079     ///
1080     /// if __self0_vi == __self1_vi && __self0_vi == __self2_vi && ... {
1081     ///     match (...) {
1082     ///         (Variant1, Variant1, ...) => Body1
1083     ///         (Variant2, Variant2, ...) => Body2,
1084     ///         ...
1085     ///         _ => ::core::intrinsics::unreachable()
1086     ///     }
1087     /// }
1088     /// else {
1089     ///     ... // catch-all remainder can inspect above variant index values.
1090     /// }
1091     /// ```
1092     fn build_enum_match_tuple<'b>(
1093         &self,
1094         cx: &mut ExtCtxt,
1095         trait_: &TraitDef<'b>,
1096         enum_def: &'b EnumDef,
1097         type_attrs: &[ast::Attribute],
1098         type_ident: Ident,
1099         self_args: Vec<P<Expr>>,
1100         nonself_args: &[P<Expr>]) -> P<Expr> {
1101
1102         let sp = trait_.span;
1103         let variants = &enum_def.variants;
1104
1105         let self_arg_names = self_args.iter().enumerate()
1106             .map(|(arg_count, _self_arg)| {
1107                 if arg_count == 0 {
1108                     "__self".to_string()
1109                 } else {
1110                     format!("__arg_{}", arg_count)
1111                 }
1112             })
1113             .collect::<Vec<String>>();
1114
1115         let self_arg_idents = self_arg_names.iter()
1116             .map(|name|cx.ident_of(&name[..]))
1117             .collect::<Vec<ast::Ident>>();
1118
1119         // The `vi_idents` will be bound, solely in the catch-all, to
1120         // a series of let statements mapping each self_arg to an int
1121         // value corresponding to its discriminant.
1122         let vi_idents: Vec<ast::Ident> = self_arg_names.iter()
1123             .map(|name| { let vi_suffix = format!("{}_vi", &name[..]);
1124                           cx.ident_of(&vi_suffix[..]) })
1125             .collect::<Vec<ast::Ident>>();
1126
1127         // Builds, via callback to call_substructure_method, the
1128         // delegated expression that handles the catch-all case,
1129         // using `__variants_tuple` to drive logic if necessary.
1130         let catch_all_substructure = EnumNonMatchingCollapsed(
1131             self_arg_idents, &variants[..], &vi_idents[..]);
1132
1133         // These arms are of the form:
1134         // (Variant1, Variant1, ...) => Body1
1135         // (Variant2, Variant2, ...) => Body2
1136         // ...
1137         // where each tuple has length = self_args.len()
1138         let mut match_arms: Vec<ast::Arm> = variants.iter().enumerate()
1139             .map(|(index, variant)| {
1140                 let mk_self_pat = |cx: &mut ExtCtxt, self_arg_name: &str| {
1141                     let (p, idents) = trait_.create_enum_variant_pattern(cx, type_ident,
1142                                                                          &**variant,
1143                                                                          self_arg_name,
1144                                                                          ast::MutImmutable);
1145                     (cx.pat(sp, ast::PatRegion(p, ast::MutImmutable)), idents)
1146                 };
1147
1148                 // A single arm has form (&VariantK, &VariantK, ...) => BodyK
1149                 // (see "Final wrinkle" note below for why.)
1150                 let mut subpats = Vec::with_capacity(self_arg_names.len());
1151                 let mut self_pats_idents = Vec::with_capacity(self_arg_names.len() - 1);
1152                 let first_self_pat_idents = {
1153                     let (p, idents) = mk_self_pat(cx, &self_arg_names[0]);
1154                     subpats.push(p);
1155                     idents
1156                 };
1157                 for self_arg_name in &self_arg_names[1..] {
1158                     let (p, idents) = mk_self_pat(cx, &self_arg_name[..]);
1159                     subpats.push(p);
1160                     self_pats_idents.push(idents);
1161                 }
1162
1163                 // Here is the pat = `(&VariantK, &VariantK, ...)`
1164                 let single_pat = cx.pat_tuple(sp, subpats);
1165
1166                 // For the BodyK, we need to delegate to our caller,
1167                 // passing it an EnumMatching to indicate which case
1168                 // we are in.
1169
1170                 // All of the Self args have the same variant in these
1171                 // cases.  So we transpose the info in self_pats_idents
1172                 // to gather the getter expressions together, in the
1173                 // form that EnumMatching expects.
1174
1175                 // The transposition is driven by walking across the
1176                 // arg fields of the variant for the first self pat.
1177                 let field_tuples = first_self_pat_idents.into_iter().enumerate()
1178                     // For each arg field of self, pull out its getter expr ...
1179                     .map(|(field_index, (sp, opt_ident, self_getter_expr, attrs))| {
1180                         // ... but FieldInfo also wants getter expr
1181                         // for matching other arguments of Self type;
1182                         // so walk across the *other* self_pats_idents
1183                         // and pull out getter for same field in each
1184                         // of them (using `field_index` tracked above).
1185                         // That is the heart of the transposition.
1186                         let others = self_pats_idents.iter().map(|fields| {
1187                             let (_, _opt_ident, ref other_getter_expr, _) =
1188                                 fields[field_index];
1189
1190                             // All Self args have same variant, so
1191                             // opt_idents are the same.  (Assert
1192                             // here to make it self-evident that
1193                             // it is okay to ignore `_opt_ident`.)
1194                             assert!(opt_ident == _opt_ident);
1195
1196                             other_getter_expr.clone()
1197                         }).collect::<Vec<P<Expr>>>();
1198
1199                         FieldInfo { span: sp,
1200                                     name: opt_ident,
1201                                     self_: self_getter_expr,
1202                                     other: others,
1203                                     attrs: attrs,
1204                         }
1205                     }).collect::<Vec<FieldInfo>>();
1206
1207                 // Now, for some given VariantK, we have built up
1208                 // expressions for referencing every field of every
1209                 // Self arg, assuming all are instances of VariantK.
1210                 // Build up code associated with such a case.
1211                 let substructure = EnumMatching(index,
1212                                                 &**variant,
1213                                                 field_tuples);
1214                 let arm_expr = self.call_substructure_method(
1215                     cx, trait_, type_ident, &self_args[..], nonself_args,
1216                     &substructure);
1217
1218                 cx.arm(sp, vec![single_pat], arm_expr)
1219             }).collect();
1220         // We will usually need the catch-all after matching the
1221         // tuples `(VariantK, VariantK, ...)` for each VariantK of the
1222         // enum.  But:
1223         //
1224         // * when there is only one Self arg, the arms above suffice
1225         // (and the deriving we call back into may not be prepared to
1226         // handle EnumNonMatchCollapsed), and,
1227         //
1228         // * when the enum has only one variant, the single arm that
1229         // is already present always suffices.
1230         //
1231         // * In either of the two cases above, if we *did* add a
1232         //   catch-all `_` match, it would trigger the
1233         //   unreachable-pattern error.
1234         //
1235         if variants.len() > 1 && self_args.len() > 1 {
1236             // Build a series of let statements mapping each self_arg
1237             // to its discriminant value. If this is a C-style enum
1238             // with a specific repr type, then casts the values to
1239             // that type.  Otherwise casts to `i32` (the default repr
1240             // type).
1241             //
1242             // i.e. for `enum E<T> { A, B(1), C(T, T) }`, and a deriving
1243             // with three Self args, builds three statements:
1244             //
1245             // ```
1246             // let __self0_vi = unsafe {
1247             //     std::intrinsics::discriminant_value(&self) } as i32;
1248             // let __self1_vi = unsafe {
1249             //     std::intrinsics::discriminant_value(&__arg1) } as i32;
1250             // let __self2_vi = unsafe {
1251             //     std::intrinsics::discriminant_value(&__arg2) } as i32;
1252             // ```
1253             let mut index_let_stmts: Vec<P<ast::Stmt>> = Vec::new();
1254
1255             //We also build an expression which checks whether all discriminants are equal
1256             // discriminant_test = __self0_vi == __self1_vi && __self0_vi == __self2_vi && ...
1257             let mut discriminant_test = cx.expr_bool(sp, true);
1258
1259             let target_type_name =
1260                 find_repr_type_name(&cx.parse_sess.span_diagnostic, type_attrs);
1261
1262             let mut first_ident = None;
1263             for (&ident, self_arg) in vi_idents.iter().zip(&self_args) {
1264                 let path = cx.std_path(&["intrinsics", "discriminant_value"]);
1265                 let call = cx.expr_call_global(
1266                     sp, path, vec![cx.expr_addr_of(sp, self_arg.clone())]);
1267                 let variant_value = cx.expr_block(P(ast::Block {
1268                     stmts: vec![],
1269                     expr: Some(call),
1270                     id: ast::DUMMY_NODE_ID,
1271                     rules: ast::UnsafeBlock(ast::CompilerGenerated),
1272                     span: sp }));
1273
1274                 let target_ty = cx.ty_ident(sp, cx.ident_of(target_type_name));
1275                 let variant_disr = cx.expr_cast(sp, variant_value, target_ty);
1276                 let let_stmt = cx.stmt_let(sp, false, ident, variant_disr);
1277                 index_let_stmts.push(let_stmt);
1278
1279                 match first_ident {
1280                     Some(first) => {
1281                         let first_expr = cx.expr_ident(sp, first);
1282                         let id = cx.expr_ident(sp, ident);
1283                         let test = cx.expr_binary(sp, ast::BiEq, first_expr, id);
1284                         discriminant_test = cx.expr_binary(sp, ast::BiAnd, discriminant_test, test)
1285                     }
1286                     None => {
1287                         first_ident = Some(ident);
1288                     }
1289                 }
1290             }
1291
1292             let arm_expr = self.call_substructure_method(
1293                 cx, trait_, type_ident, &self_args[..], nonself_args,
1294                 &catch_all_substructure);
1295
1296             //Since we know that all the arguments will match if we reach the match expression we
1297             //add the unreachable intrinsics as the result of the catch all which should help llvm
1298             //in optimizing it
1299             let path = cx.std_path(&["intrinsics", "unreachable"]);
1300             let call = cx.expr_call_global(
1301                 sp, path, vec![]);
1302             let unreachable = cx.expr_block(P(ast::Block {
1303                 stmts: vec![],
1304                 expr: Some(call),
1305                 id: ast::DUMMY_NODE_ID,
1306                 rules: ast::UnsafeBlock(ast::CompilerGenerated),
1307                 span: sp }));
1308             match_arms.push(cx.arm(sp, vec![cx.pat_wild(sp)], unreachable));
1309
1310             // Final wrinkle: the self_args are expressions that deref
1311             // down to desired l-values, but we cannot actually deref
1312             // them when they are fed as r-values into a tuple
1313             // expression; here add a layer of borrowing, turning
1314             // `(*self, *__arg_0, ...)` into `(&*self, &*__arg_0, ...)`.
1315             let borrowed_self_args = self_args.move_map(|self_arg| cx.expr_addr_of(sp, self_arg));
1316             let match_arg = cx.expr(sp, ast::ExprTup(borrowed_self_args));
1317
1318             //Lastly we create an expression which branches on all discriminants being equal
1319             //  if discriminant_test {
1320             //      match (...) {
1321             //          (Variant1, Variant1, ...) => Body1
1322             //          (Variant2, Variant2, ...) => Body2,
1323             //          ...
1324             //          _ => ::core::intrinsics::unreachable()
1325             //      }
1326             //  }
1327             //  else {
1328             //      <delegated expression referring to __self0_vi, et al.>
1329             //  }
1330             let all_match = cx.expr_match(sp, match_arg, match_arms);
1331             let arm_expr = cx.expr_if(sp, discriminant_test, all_match, Some(arm_expr));
1332             cx.expr_block(
1333                 cx.block_all(sp, index_let_stmts, Some(arm_expr)))
1334         } else if variants.is_empty() {
1335             // As an additional wrinkle, For a zero-variant enum A,
1336             // currently the compiler
1337             // will accept `fn (a: &Self) { match   *a   { } }`
1338             // but rejects `fn (a: &Self) { match (&*a,) { } }`
1339             // as well as  `fn (a: &Self) { match ( *a,) { } }`
1340             //
1341             // This means that the strategy of building up a tuple of
1342             // all Self arguments fails when Self is a zero variant
1343             // enum: rustc rejects the expanded program, even though
1344             // the actual code tends to be impossible to execute (at
1345             // least safely), according to the type system.
1346             //
1347             // The most expedient fix for this is to just let the
1348             // code fall through to the catch-all.  But even this is
1349             // error-prone, since the catch-all as defined above would
1350             // generate code like this:
1351             //
1352             //     _ => { let __self0 = match *self { };
1353             //            let __self1 = match *__arg_0 { };
1354             //            <catch-all-expr> }
1355             //
1356             // Which is yields bindings for variables which type
1357             // inference cannot resolve to unique types.
1358             //
1359             // One option to the above might be to add explicit type
1360             // annotations.  But the *only* reason to go down that path
1361             // would be to try to make the expanded output consistent
1362             // with the case when the number of enum variants >= 1.
1363             //
1364             // That just isn't worth it.  In fact, trying to generate
1365             // sensible code for *any* deriving on a zero-variant enum
1366             // does not make sense.  But at the same time, for now, we
1367             // do not want to cause a compile failure just because the
1368             // user happened to attach a deriving to their
1369             // zero-variant enum.
1370             //
1371             // Instead, just generate a failing expression for the
1372             // zero variant case, skipping matches and also skipping
1373             // delegating back to the end user code entirely.
1374             //
1375             // (See also #4499 and #12609; note that some of the
1376             // discussions there influence what choice we make here;
1377             // e.g. if we feature-gate `match x { ... }` when x refers
1378             // to an uninhabited type (e.g. a zero-variant enum or a
1379             // type holding such an enum), but do not feature-gate
1380             // zero-variant enums themselves, then attempting to
1381             // derive Debug on such a type could here generate code
1382             // that needs the feature gate enabled.)
1383
1384             cx.expr_unreachable(sp)
1385         }
1386         else {
1387
1388             // Final wrinkle: the self_args are expressions that deref
1389             // down to desired l-values, but we cannot actually deref
1390             // them when they are fed as r-values into a tuple
1391             // expression; here add a layer of borrowing, turning
1392             // `(*self, *__arg_0, ...)` into `(&*self, &*__arg_0, ...)`.
1393             let borrowed_self_args = self_args.move_map(|self_arg| cx.expr_addr_of(sp, self_arg));
1394             let match_arg = cx.expr(sp, ast::ExprTup(borrowed_self_args));
1395             cx.expr_match(sp, match_arg, match_arms)
1396         }
1397     }
1398
1399     fn expand_static_enum_method_body(&self,
1400                                       cx: &mut ExtCtxt,
1401                                       trait_: &TraitDef,
1402                                       enum_def: &EnumDef,
1403                                       type_ident: Ident,
1404                                       self_args: &[P<Expr>],
1405                                       nonself_args: &[P<Expr>])
1406         -> P<Expr> {
1407         let summary = enum_def.variants.iter().map(|v| {
1408             let ident = v.node.name;
1409             let summary = trait_.summarise_struct(cx, &v.node.data);
1410             (ident, v.span, summary)
1411         }).collect();
1412         self.call_substructure_method(cx, trait_, type_ident,
1413                                       self_args, nonself_args,
1414                                       &StaticEnum(enum_def, summary))
1415     }
1416 }
1417
1418 #[derive(PartialEq)] // dogfooding!
1419 enum StructType {
1420     Unknown, Record, Tuple
1421 }
1422
1423 // general helper methods.
1424 impl<'a> TraitDef<'a> {
1425     fn set_expn_info(&self,
1426                      cx: &mut ExtCtxt,
1427                      mut to_set: Span) -> Span {
1428         let trait_name = match self.path.path.last() {
1429             None => cx.span_bug(self.span, "trait with empty path in generic `derive`"),
1430             Some(name) => *name
1431         };
1432         to_set.expn_id = cx.codemap().record_expansion(codemap::ExpnInfo {
1433             call_site: to_set,
1434             callee: codemap::NameAndSpan {
1435                 format: codemap::MacroAttribute(intern(&format!("derive({})", trait_name))),
1436                 span: Some(self.span),
1437                 allow_internal_unstable: false,
1438             }
1439         });
1440         to_set
1441     }
1442
1443     fn summarise_struct(&self,
1444                         cx: &mut ExtCtxt,
1445                         struct_def: &VariantData) -> StaticFields {
1446         let mut named_idents = Vec::new();
1447         let mut just_spans = Vec::new();
1448         for field in struct_def.fields(){
1449             let sp = self.set_expn_info(cx, field.span);
1450             match field.node.kind {
1451                 ast::NamedField(ident, _) => named_idents.push((ident, sp)),
1452                 ast::UnnamedField(..) => just_spans.push(sp),
1453             }
1454         }
1455
1456         match (just_spans.is_empty(), named_idents.is_empty()) {
1457             (false, false) => cx.span_bug(self.span,
1458                                           "a struct with named and unnamed \
1459                                           fields in generic `derive`"),
1460             // named fields
1461             (_, false) => Named(named_idents),
1462             // tuple structs (includes empty structs)
1463             (_, _)     => Unnamed(just_spans)
1464         }
1465     }
1466
1467     fn create_subpatterns(&self,
1468                           cx: &mut ExtCtxt,
1469                           field_paths: Vec<ast::SpannedIdent> ,
1470                           mutbl: ast::Mutability)
1471                           -> Vec<P<ast::Pat>> {
1472         field_paths.iter().map(|path| {
1473             cx.pat(path.span,
1474                         ast::PatIdent(ast::BindByRef(mutbl), (*path).clone(), None))
1475         }).collect()
1476     }
1477
1478     fn create_struct_pattern(&self,
1479                              cx: &mut ExtCtxt,
1480                              struct_path: ast::Path,
1481                              struct_def: &'a VariantData,
1482                              prefix: &str,
1483                              mutbl: ast::Mutability)
1484                              -> (P<ast::Pat>, Vec<(Span, Option<Ident>,
1485                                                    P<Expr>,
1486                                                    &'a [ast::Attribute])>) {
1487         if struct_def.fields().is_empty() {
1488             return (cx.pat_enum(self.span, struct_path, vec![]), vec![]);
1489         }
1490
1491         let mut paths = Vec::new();
1492         let mut ident_expr = Vec::new();
1493         let mut struct_type = Unknown;
1494
1495         for (i, struct_field) in struct_def.fields().iter().enumerate() {
1496             let sp = self.set_expn_info(cx, struct_field.span);
1497             let opt_id = match struct_field.node.kind {
1498                 ast::NamedField(ident, _) if (struct_type == Unknown ||
1499                                               struct_type == Record) => {
1500                     struct_type = Record;
1501                     Some(ident)
1502                 }
1503                 ast::UnnamedField(..) if (struct_type == Unknown ||
1504                                           struct_type == Tuple) => {
1505                     struct_type = Tuple;
1506                     None
1507                 }
1508                 _ => {
1509                     cx.span_bug(sp, "a struct with named and unnamed fields in `derive`");
1510                 }
1511             };
1512             let ident = cx.ident_of(&format!("{}_{}", prefix, i));
1513             paths.push(codemap::Spanned{span: sp, node: ident});
1514             let val = cx.expr(
1515                 sp, ast::ExprParen(cx.expr_deref(sp, cx.expr_path(cx.path_ident(sp,ident)))));
1516             ident_expr.push((sp, opt_id, val, &struct_field.node.attrs[..]));
1517         }
1518
1519         let subpats = self.create_subpatterns(cx, paths, mutbl);
1520
1521         // struct_type is definitely not Unknown, since struct_def.fields
1522         // must be nonempty to reach here
1523         let pattern = if struct_type == Record {
1524             let field_pats = subpats.into_iter().zip(&ident_expr)
1525                                     .map(|(pat, &(_, id, _, _))| {
1526                 // id is guaranteed to be Some
1527                 codemap::Spanned {
1528                     span: pat.span,
1529                     node: ast::FieldPat { ident: id.unwrap(), pat: pat, is_shorthand: false },
1530                 }
1531             }).collect();
1532             cx.pat_struct(self.span, struct_path, field_pats)
1533         } else {
1534             cx.pat_enum(self.span, struct_path, subpats)
1535         };
1536
1537         (pattern, ident_expr)
1538     }
1539
1540     fn create_enum_variant_pattern(&self,
1541                                    cx: &mut ExtCtxt,
1542                                    enum_ident: ast::Ident,
1543                                    variant: &'a ast::Variant,
1544                                    prefix: &str,
1545                                    mutbl: ast::Mutability)
1546         -> (P<ast::Pat>, Vec<(Span, Option<Ident>, P<Expr>, &'a [ast::Attribute])>) {
1547         let variant_ident = variant.node.name;
1548         let variant_path = cx.path(variant.span, vec![enum_ident, variant_ident]);
1549         self.create_struct_pattern(cx, variant_path, &variant.node.data, prefix, mutbl)
1550     }
1551 }
1552
1553 /* helpful premade recipes */
1554
1555 /// Fold the fields. `use_foldl` controls whether this is done
1556 /// left-to-right (`true`) or right-to-left (`false`).
1557 pub fn cs_fold<F>(use_foldl: bool,
1558                   mut f: F,
1559                   base: P<Expr>,
1560                   mut enum_nonmatch_f: EnumNonMatchCollapsedFunc,
1561                   cx: &mut ExtCtxt,
1562                   trait_span: Span,
1563                   substructure: &Substructure)
1564                   -> P<Expr> where
1565     F: FnMut(&mut ExtCtxt, Span, P<Expr>, P<Expr>, &[P<Expr>]) -> P<Expr>,
1566 {
1567     match *substructure.fields {
1568         EnumMatching(_, _, ref all_fields) | Struct(ref all_fields) => {
1569             if use_foldl {
1570                 all_fields.iter().fold(base, |old, field| {
1571                     f(cx,
1572                       field.span,
1573                       old,
1574                       field.self_.clone(),
1575                       &field.other)
1576                 })
1577             } else {
1578                 all_fields.iter().rev().fold(base, |old, field| {
1579                     f(cx,
1580                       field.span,
1581                       old,
1582                       field.self_.clone(),
1583                       &field.other)
1584                 })
1585             }
1586         },
1587         EnumNonMatchingCollapsed(ref all_args, _, tuple) =>
1588             enum_nonmatch_f(cx, trait_span, (&all_args[..], tuple),
1589                             substructure.nonself_args),
1590         StaticEnum(..) | StaticStruct(..) => {
1591             cx.span_bug(trait_span, "static function in `derive`")
1592         }
1593     }
1594 }
1595
1596
1597 /// Call the method that is being derived on all the fields, and then
1598 /// process the collected results. i.e.
1599 ///
1600 /// ```ignore
1601 /// f(cx, span, vec![self_1.method(__arg_1_1, __arg_2_1),
1602 ///                  self_2.method(__arg_1_2, __arg_2_2)])
1603 /// ```
1604 #[inline]
1605 pub fn cs_same_method<F>(f: F,
1606                          mut enum_nonmatch_f: EnumNonMatchCollapsedFunc,
1607                          cx: &mut ExtCtxt,
1608                          trait_span: Span,
1609                          substructure: &Substructure)
1610                          -> P<Expr> where
1611     F: FnOnce(&mut ExtCtxt, Span, Vec<P<Expr>>) -> P<Expr>,
1612 {
1613     match *substructure.fields {
1614         EnumMatching(_, _, ref all_fields) | Struct(ref all_fields) => {
1615             // call self_n.method(other_1_n, other_2_n, ...)
1616             let called = all_fields.iter().map(|field| {
1617                 cx.expr_method_call(field.span,
1618                                     field.self_.clone(),
1619                                     substructure.method_ident,
1620                                     field.other.iter()
1621                                                .map(|e| cx.expr_addr_of(field.span, e.clone()))
1622                                                .collect())
1623             }).collect();
1624
1625             f(cx, trait_span, called)
1626         },
1627         EnumNonMatchingCollapsed(ref all_self_args, _, tuple) =>
1628             enum_nonmatch_f(cx, trait_span, (&all_self_args[..], tuple),
1629                             substructure.nonself_args),
1630         StaticEnum(..) | StaticStruct(..) => {
1631             cx.span_bug(trait_span, "static function in `derive`")
1632         }
1633     }
1634 }