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