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