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 /*!
  12
  13 Some code that abstracts away much of the boilerplate of writing
  14 `deriving` instances for traits. Among other things it manages getting
  15 access to the fields of the 4 different sorts of structs and enum
  16 variants, as well as creating the method and impl ast instances.
  17
  18 Supported features (fairly exhaustive):
  19
  20 - Methods taking any number of parameters of any type, and returning
  21   any type, other than vectors, bottom and closures.
  22 - Generating `impl`s for types with type parameters and lifetimes
  23   (e.g. `Option<T>`), the parameters are automatically given the
  24   current trait as a bound. (This includes separate type parameters
  25   and lifetimes for methods.)
  26 - Additional bounds on the type parameters, e.g. the `Ord` instance
  27   requires an explicit `PartialEq` bound at the
  28   moment. (`TraitDef.additional_bounds`)
  29
  30 Unsupported: FIXME #6257: calling methods on reference fields,
  31 e.g. deriving Eq/Ord/Clone don't work on `struct A(&int)`,
  32 because of how the auto-dereferencing happens.
  33
  34 The most important thing for implementers is the `Substructure` and
  35 `SubstructureFields` objects. The latter groups 5 possibilities of the
  36 arguments:
  37
  38 - `Struct`, when `Self` is a struct (including tuple structs, e.g
  39   `struct T(int, char)`).
  40 - `EnumMatching`, when `Self` is an enum and all the arguments are the
  41   same variant of the enum (e.g. `Some(1)`, `Some(3)` and `Some(4)`)
  42 - `EnumNonMatching` when `Self` is an enum and the arguments are not
  43   the same variant (e.g. `None`, `Some(1)` and `None`). If
  44   `const_nonmatching` is true, this will contain an empty list.
  45 - `StaticEnum` and `StaticStruct` for static methods, where the type
  46   being derived upon is either an enum or struct respectively. (Any
  47   argument with type Self is just grouped among the non-self
  48   arguments.)
  49
  50 In the first two cases, the values from the corresponding fields in
  51 all the arguments are grouped together. In the `EnumNonMatching` case
  52 this isn't possible (different variants have different fields), so the
  53 fields are grouped by which argument they come from. There are no
  54 fields with values in the static cases, so these are treated entirely
  55 differently.
  56
  57 The non-static cases have `Option<ident>` in several places associated
  58 with field `expr`s. This represents the name of the field it is
  59 associated with. It is only not `None` when the associated field has
  60 an identifier in the source code. For example, the `x`s in the
  61 following snippet
  62
  63 ```rust
  64 struct A { x : int }
  65
  66 struct B(int);
  67
  68 enum C {
  69     C0(int),
  70     C1 { x: int }
  71 }
  72 ```
  73
  74 The `int`s in `B` and `C0` don't have an identifier, so the
  75 `Option<ident>`s would be `None` for them.
  76
  77 In the static cases, the structure is summarised, either into the just
  78 spans of the fields or a list of spans and the field idents (for tuple
  79 structs and record structs, respectively), or a list of these, for
  80 enums (one for each variant). For empty struct and empty enum
  81 variants, it is represented as a count of 0.
  82
  83 # Examples
  84
  85 The following simplified `PartialEq` is used for in-code examples:
  86
  87 ```rust
  88 trait PartialEq {
  89     fn eq(&self, other: &Self);
  90 }
  91 impl PartialEq for int {
  92     fn eq(&self, other: &int) -> bool {
  93         *self == *other
  94     }
  95 }
  96 ```
  97
  98 Some examples of the values of `SubstructureFields` follow, using the
  99 above `PartialEq`, `A`, `B` and `C`.
 100
 101 ## Structs
 102
 103 When generating the `expr` for the `A` impl, the `SubstructureFields` is
 104
 105 ~~~text
 106 Struct(~[FieldInfo {
 107            span: <span of x>
 108            name: Some(<ident of x>),
 109            self_: <expr for &self.x>,
 110            other: ~[<expr for &other.x]
 111          }])
 112 ~~~
 113
 114 For the `B` impl, called with `B(a)` and `B(b)`,
 115
 116 ~~~text
 117 Struct(~[FieldInfo {
 118           span: <span of `int`>,
 119           name: None,
 120           <expr for &a>
 121           ~[<expr for &b>]
 122          }])
 123 ~~~
 124
 125 ## Enums
 126
 127 When generating the `expr` for a call with `self == C0(a)` and `other
 128 == C0(b)`, the SubstructureFields is
 129
 130 ~~~text
 131 EnumMatching(0, <ast::Variant for C0>,
 132              ~[FieldInfo {
 133                 span: <span of int>
 134                 name: None,
 135                 self_: <expr for &a>,
 136                 other: ~[<expr for &b>]
 137               }])
 138 ~~~
 139
 140 For `C1 {x}` and `C1 {x}`,
 141
 142 ~~~text
 143 EnumMatching(1, <ast::Variant for C1>,
 144              ~[FieldInfo {
 145                 span: <span of x>
 146                 name: Some(<ident of x>),
 147                 self_: <expr for &self.x>,
 148                 other: ~[<expr for &other.x>]
 149                }])
 150 ~~~
 151
 152 For `C0(a)` and `C1 {x}` ,
 153
 154 ~~~text
 155 EnumNonMatching(~[(0, <ast::Variant for B0>,
 156                    ~[(<span of int>, None, <expr for &a>)]),
 157                   (1, <ast::Variant for B1>,
 158                    ~[(<span of x>, Some(<ident of x>),
 159                       <expr for &other.x>)])])
 160 ~~~
 161
 162 (and vice versa, but with the order of the outermost list flipped.)
 163
 164 ## Static
 165
 166 A static method on the above would result in,
 167
 168 ~~~text
 169 StaticStruct(<ast::StructDef of A>, Named(~[(<ident of x>, <span of x>)]))
 170
 171 StaticStruct(<ast::StructDef of B>, Unnamed(~[<span of x>]))
 172
 173 StaticEnum(<ast::EnumDef of C>, ~[(<ident of C0>, <span of C0>, Unnamed(~[<span of int>])),
 174                                   (<ident of C1>, <span of C1>,
 175                                    Named(~[(<ident of x>, <span of x>)]))])
 176 ~~~
 177
 178 */
 179
 180 use std::cell::RefCell;
 181
 182 use ast;
 183 use ast::{P, EnumDef, Expr, Ident, Generics, StructDef};
 184 use ast_util;
 185 use attr;
 186 use attr::AttrMetaMethods;
 187 use ext::base::ExtCtxt;
 188 use ext::build::AstBuilder;
 189 use codemap;
 190 use codemap::Span;
 191 use owned_slice::OwnedSlice;
 192 use parse::token::InternedString;
 193
 194 use self::ty::*;
 195
 196 pub mod ty;
 197
 198 pub struct TraitDef<'a> {
 199     /// The span for the current #[deriving(Foo)] header.
 200     pub span: Span,
 201
 202     pub attributes: Vec<ast::Attribute>,
 203
 204     /// Path of the trait, including any type parameters
 205     pub path: Path<'a>,
 206
 207     /// Additional bounds required of any type parameters of the type,
 208     /// other than the current trait
 209     pub additional_bounds: Vec<Ty<'a>>,
 210
 211     /// Any extra lifetimes and/or bounds, e.g. `D: serialize::Decoder`
 212     pub generics: LifetimeBounds<'a>,
 213
 214     pub methods: Vec<MethodDef<'a>>,
 215 }
 216
 217
 218 pub struct MethodDef<'a> {
 219     /// name of the method
 220     pub name: &'a str,
 221     /// List of generics, e.g. `R: rand::Rng`
 222     pub generics: LifetimeBounds<'a>,
 223
 224     /// Whether there is a self argument (outer Option) i.e. whether
 225     /// this is a static function, and whether it is a pointer (inner
 226     /// Option)
 227     pub explicit_self: Option<Option<PtrTy<'a>>>,
 228
 229     /// Arguments other than the self argument
 230     pub args: Vec<Ty<'a>>,
 231
 232     /// Return type
 233     pub ret_ty: Ty<'a>,
 234
 235     pub attributes: Vec<ast::Attribute>,
 236
 237     /// if the value of the nonmatching enums is independent of the
 238     /// actual enum variants, i.e. can use _ => .. match.
 239     pub const_nonmatching: bool,
 240
 241     pub combine_substructure: RefCell<CombineSubstructureFunc<'a>>,
 242 }
 243
 244 /// All the data about the data structure/method being derived upon.
 245 pub struct Substructure<'a> {
 246     /// ident of self
 247     pub type_ident: Ident,
 248     /// ident of the method
 249     pub method_ident: Ident,
 250     /// dereferenced access to any Self or Ptr(Self, _) arguments
 251     pub self_args: &'a [@Expr],
 252     /// verbatim access to any other arguments
 253     pub nonself_args: &'a [@Expr],
 254     pub fields: &'a SubstructureFields<'a>
 255 }
 256
 257 /// Summary of the relevant parts of a struct/enum field.
 258 pub struct FieldInfo {
 259     pub span: Span,
 260     /// None for tuple structs/normal enum variants, Some for normal
 261     /// structs/struct enum variants.
 262     pub name: Option<Ident>,
 263     /// The expression corresponding to this field of `self`
 264     /// (specifically, a reference to it).
 265     pub self_: @Expr,
 266     /// The expressions corresponding to references to this field in
 267     /// the other Self arguments.
 268     pub other: Vec<@Expr>,
 269 }
 270
 271 /// Fields for a static method
 272 pub enum StaticFields {
 273     /// Tuple structs/enum variants like this
 274     Unnamed(Vec<Span> ),
 275     /// Normal structs/struct variants.
 276     Named(Vec<(Ident, Span)> )
 277 }
 278
 279 /// A summary of the possible sets of fields. See above for details
 280 /// and examples
 281 pub enum SubstructureFields<'a> {
 282     Struct(Vec<FieldInfo> ),
 283     /**
 284     Matching variants of the enum: variant index, ast::Variant,
 285     fields: the field name is only non-`None` in the case of a struct
 286     variant.
 287     */
 288     EnumMatching(uint, &'a ast::Variant, Vec<FieldInfo> ),
 289
 290     /**
 291     non-matching variants of the enum, [(variant index, ast::Variant,
 292     [field span, field ident, fields])] \(i.e. all fields for self are in the
 293     first tuple, for other1 are in the second tuple, etc.)
 294     */
 295     EnumNonMatching(&'a [(uint, P<ast::Variant>, Vec<(Span, Option<Ident>, @Expr)> )]),
 296
 297     /// A static method where Self is a struct.
 298     StaticStruct(&'a ast::StructDef, StaticFields),
 299     /// A static method where Self is an enum.
 300     StaticEnum(&'a ast::EnumDef, Vec<(Ident, Span, StaticFields)> )
 301 }
 302
 303
 304
 305 /**
 306 Combine the values of all the fields together. The last argument is
 307 all the fields of all the structures, see above for details.
 308 */
 309 pub type CombineSubstructureFunc<'a> =
 310     |&mut ExtCtxt, Span, &Substructure|: 'a -> @Expr;
 311
 312 /**
 313 Deal with non-matching enum variants, the arguments are a list
 314 representing each variant: (variant index, ast::Variant instance,
 315 [variant fields]), and a list of the nonself args of the type
 316 */
 317 pub type EnumNonMatchFunc<'a> =
 318     |&mut ExtCtxt,
 319            Span,
 320            &[(uint, P<ast::Variant>, Vec<(Span, Option<Ident>, @Expr)> )],
 321            &[@Expr]|: 'a
 322            -> @Expr;
 323
 324 pub fn combine_substructure<'a>(f: CombineSubstructureFunc<'a>)
 325     -> RefCell<CombineSubstructureFunc<'a>> {
 326     RefCell::new(f)
 327 }
 328
 329
 330 impl<'a> TraitDef<'a> {
 331     pub fn expand(&self,
 332                   cx: &mut ExtCtxt,
 333                   _mitem: @ast::MetaItem,
 334                   item: @ast::Item,
 335                   push: |@ast::Item|) {
 336         let newitem = match item.node {
 337             ast::ItemStruct(struct_def, ref generics) => {
 338                 self.expand_struct_def(cx,
 339                                        struct_def,
 340                                        item.ident,
 341                                        generics)
 342             }
 343             ast::ItemEnum(ref enum_def, ref generics) => {
 344                 self.expand_enum_def(cx,
 345                                      enum_def,
 346                                      item.ident,
 347                                      generics)
 348             }
 349             _ => return
 350         };
 351         // Keep the lint attributes of the previous item to control how the
 352         // generated implementations are linted
 353         let mut attrs = newitem.attrs.clone();
 354         attrs.extend(item.attrs.iter().filter(|a| {
 355             match a.name().get() {
 356                 "allow" | "warn" | "deny" | "forbid" => true,
 357                 _ => false,
 358             }
 359         }).map(|a| a.clone()));
 360         push(@ast::Item {
 361             attrs: attrs,
 362             ..(*newitem).clone()
 363         })
 364     }
 365
 366     /**
 367      *
 368      * Given that we are deriving a trait `Tr` for a type `T<'a, ...,
 369      * 'z, A, ..., Z>`, creates an impl like:
 370      *
 371      * ```ignore
 372      *      impl<'a, ..., 'z, A:Tr B1 B2, ..., Z: Tr B1 B2> Tr for T<A, ..., Z> { ... }
 373      * ```
 374      *
 375      * where B1, B2, ... are the bounds given by `bounds_paths`.'
 376      *
 377      */
 378     fn create_derived_impl(&self,
 379                            cx: &mut ExtCtxt,
 380                            type_ident: Ident,
 381                            generics: &Generics,
 382                            methods: Vec<@ast::Method> ) -> @ast::Item {
 383         let trait_path = self.path.to_path(cx, self.span, type_ident, generics);
 384
 385         let Generics { mut lifetimes, ty_params } =
 386             self.generics.to_generics(cx, self.span, type_ident, generics);
 387         let mut ty_params = ty_params.into_vec();
 388
 389         // Copy the lifetimes
 390         lifetimes.extend(generics.lifetimes.iter().map(|l| *l));
 391
 392         // Create the type parameters.
 393         ty_params.extend(generics.ty_params.iter().map(|ty_param| {
 394             // I don't think this can be moved out of the loop, since
 395             // a TyParamBound requires an ast id
 396             let mut bounds: Vec<_> =
 397                 // extra restrictions on the generics parameters to the type being derived upon
 398                 self.additional_bounds.iter().map(|p| {
 399                     cx.typarambound(p.to_path(cx, self.span,
 400                                                   type_ident, generics))
 401                 }).collect();
 402             // require the current trait
 403             bounds.push(cx.typarambound(trait_path.clone()));
 404
 405             cx.typaram(self.span,
 406                        ty_param.ident,
 407                        ty_param.sized,
 408                        OwnedSlice::from_vec(bounds),
 409                        None)
 410         }));
 411         let trait_generics = Generics {
 412             lifetimes: lifetimes,
 413             ty_params: OwnedSlice::from_vec(ty_params)
 414         };
 415
 416         // Create the reference to the trait.
 417         let trait_ref = cx.trait_ref(trait_path);
 418
 419         // Create the type parameters on the `self` path.
 420         let self_ty_params = generics.ty_params.map(|ty_param| {
 421             cx.ty_ident(self.span, ty_param.ident)
 422         });
 423
 424         let self_lifetimes = generics.lifetimes.clone();
 425
 426         // Create the type of `self`.
 427         let self_type = cx.ty_path(
 428             cx.path_all(self.span, false, vec!( type_ident ), self_lifetimes,
 429                         self_ty_params.into_vec()), None);
 430
 431         let attr = cx.attribute(
 432             self.span,
 433             cx.meta_word(self.span,
 434                          InternedString::new("automatically_derived")));
 435         // Just mark it now since we know that it'll end up used downstream
 436         attr::mark_used(&attr);
 437         let opt_trait_ref = Some(trait_ref);
 438         let ident = ast_util::impl_pretty_name(&opt_trait_ref, self_type);
 439         cx.item(
 440             self.span,
 441             ident,
 442             (vec!(attr)).append(self.attributes.as_slice()),
 443             ast::ItemImpl(trait_generics, opt_trait_ref,
 444                           self_type, methods))
 445     }
 446
 447     fn expand_struct_def(&self,
 448                          cx: &mut ExtCtxt,
 449                          struct_def: &StructDef,
 450                          type_ident: Ident,
 451                          generics: &Generics) -> @ast::Item {
 452         let methods = self.methods.iter().map(|method_def| {
 453             let (explicit_self, self_args, nonself_args, tys) =
 454                 method_def.split_self_nonself_args(
 455                     cx, self, type_ident, generics);
 456
 457             let body = if method_def.is_static() {
 458                 method_def.expand_static_struct_method_body(
 459                     cx,
 460                     self,
 461                     struct_def,
 462                     type_ident,
 463                     self_args.as_slice(),
 464                     nonself_args.as_slice())
 465             } else {
 466                 method_def.expand_struct_method_body(cx,
 467                                                      self,
 468                                                      struct_def,
 469                                                      type_ident,
 470                                                      self_args.as_slice(),
 471                                                      nonself_args.as_slice())
 472             };
 473
 474             method_def.create_method(cx, self,
 475                                      type_ident, generics,
 476                                      explicit_self, tys,
 477                                      body)
 478         }).collect();
 479
 480         self.create_derived_impl(cx, type_ident, generics, methods)
 481     }
 482
 483     fn expand_enum_def(&self,
 484                        cx: &mut ExtCtxt,
 485                        enum_def: &EnumDef,
 486                        type_ident: Ident,
 487                        generics: &Generics) -> @ast::Item {
 488         let methods = self.methods.iter().map(|method_def| {
 489             let (explicit_self, self_args, nonself_args, tys) =
 490                 method_def.split_self_nonself_args(cx, self,
 491                                                    type_ident, generics);
 492
 493             let body = if method_def.is_static() {
 494                 method_def.expand_static_enum_method_body(
 495                     cx,
 496                     self,
 497                     enum_def,
 498                     type_ident,
 499                     self_args.as_slice(),
 500                     nonself_args.as_slice())
 501             } else {
 502                 method_def.expand_enum_method_body(cx,
 503                                                    self,
 504                                                    enum_def,
 505                                                    type_ident,
 506                                                    self_args.as_slice(),
 507                                                    nonself_args.as_slice())
 508             };
 509
 510             method_def.create_method(cx, self,
 511                                      type_ident, generics,
 512                                      explicit_self, tys,
 513                                      body)
 514         }).collect();
 515
 516         self.create_derived_impl(cx, type_ident, generics, methods)
 517     }
 518 }
 519
 520 impl<'a> MethodDef<'a> {
 521     fn call_substructure_method(&self,
 522                                 cx: &mut ExtCtxt,
 523                                 trait_: &TraitDef,
 524                                 type_ident: Ident,
 525                                 self_args: &[@Expr],
 526                                 nonself_args: &[@Expr],
 527                                 fields: &SubstructureFields)
 528         -> @Expr {
 529         let substructure = Substructure {
 530             type_ident: type_ident,
 531             method_ident: cx.ident_of(self.name),
 532             self_args: self_args,
 533             nonself_args: nonself_args,
 534             fields: fields
 535         };
 536         let mut f = self.combine_substructure.borrow_mut();
 537         let f: &mut CombineSubstructureFunc = &mut *f;
 538         (*f)(cx, trait_.span, &substructure)
 539     }
 540
 541     fn get_ret_ty(&self,
 542                   cx: &mut ExtCtxt,
 543                   trait_: &TraitDef,
 544                   generics: &Generics,
 545                   type_ident: Ident)
 546                   -> P<ast::Ty> {
 547         self.ret_ty.to_ty(cx, trait_.span, type_ident, generics)
 548     }
 549
 550     fn is_static(&self) -> bool {
 551         self.explicit_self.is_none()
 552     }
 553
 554     fn split_self_nonself_args(&self,
 555                                cx: &mut ExtCtxt,
 556                                trait_: &TraitDef,
 557                                type_ident: Ident,
 558                                generics: &Generics)
 559         -> (ast::ExplicitSelf, Vec<@Expr> , Vec<@Expr> , Vec<(Ident, P<ast::Ty>)> ) {
 560
 561         let mut self_args = Vec::new();
 562         let mut nonself_args = Vec::new();
 563         let mut arg_tys = Vec::new();
 564         let mut nonstatic = false;
 565
 566         let ast_explicit_self = match self.explicit_self {
 567             Some(ref self_ptr) => {
 568                 let (self_expr, explicit_self) =
 569                     ty::get_explicit_self(cx, trait_.span, self_ptr);
 570
 571                 self_args.push(self_expr);
 572                 nonstatic = true;
 573
 574                 explicit_self
 575             }
 576             None => codemap::respan(trait_.span, ast::SelfStatic),
 577         };
 578
 579         for (i, ty) in self.args.iter().enumerate() {
 580             let ast_ty = ty.to_ty(cx, trait_.span, type_ident, generics);
 581             let ident = cx.ident_of(format!("__arg_{}", i).as_slice());
 582             arg_tys.push((ident, ast_ty));
 583
 584             let arg_expr = cx.expr_ident(trait_.span, ident);
 585
 586             match *ty {
 587                 // for static methods, just treat any Self
 588                 // arguments as a normal arg
 589                 Self if nonstatic  => {
 590                     self_args.push(arg_expr);
 591                 }
 592                 Ptr(box Self, _) if nonstatic => {
 593                     self_args.push(cx.expr_deref(trait_.span, arg_expr))
 594                 }
 595                 _ => {
 596                     nonself_args.push(arg_expr);
 597                 }
 598             }
 599         }
 600
 601         (ast_explicit_self, self_args, nonself_args, arg_tys)
 602     }
 603
 604     fn create_method(&self,
 605                      cx: &mut ExtCtxt,
 606                      trait_: &TraitDef,
 607                      type_ident: Ident,
 608                      generics: &Generics,
 609                      explicit_self: ast::ExplicitSelf,
 610                      arg_types: Vec<(Ident, P<ast::Ty>)> ,
 611                      body: @Expr) -> @ast::Method {
 612         // create the generics that aren't for Self
 613         let fn_generics = self.generics.to_generics(cx, trait_.span, type_ident, generics);
 614
 615         let self_arg = match explicit_self.node {
 616             ast::SelfStatic => None,
 617             _ => Some(ast::Arg::new_self(trait_.span, ast::MutImmutable))
 618         };
 619         let args = {
 620             let args = arg_types.move_iter().map(|(name, ty)| {
 621                     cx.arg(trait_.span, name, ty)
 622                 });
 623             self_arg.move_iter().chain(args).collect()
 624         };
 625
 626         let ret_type = self.get_ret_ty(cx, trait_, generics, type_ident);
 627
 628         let method_ident = cx.ident_of(self.name);
 629         let fn_decl = cx.fn_decl(args, ret_type);
 630         let body_block = cx.block_expr(body);
 631
 632         // Create the method.
 633         @ast::Method {
 634             ident: method_ident,
 635             attrs: self.attributes.clone(),
 636             generics: fn_generics,
 637             explicit_self: explicit_self,
 638             fn_style: ast::NormalFn,
 639             decl: fn_decl,
 640             body: body_block,
 641             id: ast::DUMMY_NODE_ID,
 642             span: trait_.span,
 643             vis: ast::Inherited,
 644         }
 645     }
 646
 647     /**
 648    ~~~
 649     #[deriving(PartialEq)]
 650     struct A { x: int, y: int }
 651
 652     // equivalent to:
 653     impl PartialEq for A {
 654         fn eq(&self, __arg_1: &A) -> bool {
 655             match *self {
 656                 A {x: ref __self_0_0, y: ref __self_0_1} => {
 657                     match *__arg_1 {
 658                         A {x: ref __self_1_0, y: ref __self_1_1} => {
 659                             __self_0_0.eq(__self_1_0) && __self_0_1.eq(__self_1_1)
 660                         }
 661                     }
 662                 }
 663             }
 664         }
 665     }
 666    ~~~
 667     */
 668     fn expand_struct_method_body(&self,
 669                                  cx: &mut ExtCtxt,
 670                                  trait_: &TraitDef,
 671                                  struct_def: &StructDef,
 672                                  type_ident: Ident,
 673                                  self_args: &[@Expr],
 674                                  nonself_args: &[@Expr])
 675         -> @Expr {
 676
 677         let mut raw_fields = Vec::new(); // ~[[fields of self],
 678                                  // [fields of next Self arg], [etc]]
 679         let mut patterns = Vec::new();
 680         for i in range(0u, self_args.len()) {
 681             let (pat, ident_expr) =
 682                 trait_.create_struct_pattern(cx,
 683                                              type_ident,
 684                                              struct_def,
 685                                              format!("__self_{}",
 686                                                      i).as_slice(),
 687                                              ast::MutImmutable);
 688             patterns.push(pat);
 689             raw_fields.push(ident_expr);
 690         }
 691
 692         // transpose raw_fields
 693         let fields = if raw_fields.len() > 0 {
 694             raw_fields.get(0)
 695                       .iter()
 696                       .enumerate()
 697                       .map(|(i, &(span, opt_id, field))| {
 698                 let other_fields = raw_fields.tail().iter().map(|l| {
 699                     match l.get(i) {
 700                         &(_, _, ex) => ex
 701                     }
 702                 }).collect();
 703                 FieldInfo {
 704                     span: span,
 705                     name: opt_id,
 706                     self_: field,
 707                     other: other_fields
 708                 }
 709             }).collect()
 710         } else {
 711             cx.span_bug(trait_.span,
 712                         "no self arguments to non-static method in generic \
 713                          `deriving`")
 714         };
 715
 716         // body of the inner most destructuring match
 717         let mut body = self.call_substructure_method(
 718             cx,
 719             trait_,
 720             type_ident,
 721             self_args,
 722             nonself_args,
 723             &Struct(fields));
 724
 725         // make a series of nested matches, to destructure the
 726         // structs. This is actually right-to-left, but it shouldn't
 727         // matter.
 728         for (&arg_expr, &pat) in self_args.iter().zip(patterns.iter()) {
 729             body = cx.expr_match(trait_.span, arg_expr,
 730                                      vec!( cx.arm(trait_.span, vec!(pat), body) ))
 731         }
 732         body
 733     }
 734
 735     fn expand_static_struct_method_body(&self,
 736                                         cx: &mut ExtCtxt,
 737                                         trait_: &TraitDef,
 738                                         struct_def: &StructDef,
 739                                         type_ident: Ident,
 740                                         self_args: &[@Expr],
 741                                         nonself_args: &[@Expr])
 742         -> @Expr {
 743         let summary = trait_.summarise_struct(cx, struct_def);
 744
 745         self.call_substructure_method(cx,
 746                                       trait_,
 747                                       type_ident,
 748                                       self_args, nonself_args,
 749                                       &StaticStruct(struct_def, summary))
 750     }
 751
 752     /**
 753    ~~~
 754     #[deriving(PartialEq)]
 755     enum A {
 756         A1
 757         A2(int)
 758     }
 759
 760     // is equivalent to (with const_nonmatching == false)
 761
 762     impl PartialEq for A {
 763         fn eq(&self, __arg_1: &A) {
 764             match *self {
 765                 A1 => match *__arg_1 {
 766                     A1 => true
 767                     A2(ref __arg_1_1) => false
 768                 },
 769                 A2(self_1) => match *__arg_1 {
 770                     A1 => false,
 771                     A2(ref __arg_1_1) => self_1.eq(__arg_1_1)
 772                 }
 773             }
 774         }
 775     }
 776    ~~~
 777     */
 778     fn expand_enum_method_body(&self,
 779                                cx: &mut ExtCtxt,
 780                                trait_: &TraitDef,
 781                                enum_def: &EnumDef,
 782                                type_ident: Ident,
 783                                self_args: &[@Expr],
 784                                nonself_args: &[@Expr])
 785                                -> @Expr {
 786         let mut matches = Vec::new();
 787         self.build_enum_match(cx, trait_, enum_def, type_ident,
 788                               self_args, nonself_args,
 789                               None, &mut matches, 0)
 790     }
 791
 792
 793     /**
 794     Creates the nested matches for an enum definition recursively, i.e.
 795
 796    ~~~text
 797     match self {
 798        Variant1 => match other { Variant1 => matching, Variant2 => nonmatching, ... },
 799        Variant2 => match other { Variant1 => nonmatching, Variant2 => matching, ... },
 800        ...
 801     }
 802    ~~~
 803
 804     It acts in the most naive way, so every branch (and subbranch,
 805     subsubbranch, etc) exists, not just the ones where all the variants in
 806     the tree are the same. Hopefully the optimisers get rid of any
 807     repetition, otherwise derived methods with many Self arguments will be
 808     exponentially large.
 809
 810     `matching` is Some(n) if all branches in the tree above the
 811     current position are variant `n`, `None` otherwise (including on
 812     the first call).
 813     */
 814     fn build_enum_match(&self,
 815                         cx: &mut ExtCtxt,
 816                         trait_: &TraitDef,
 817                         enum_def: &EnumDef,
 818                         type_ident: Ident,
 819                         self_args: &[@Expr],
 820                         nonself_args: &[@Expr],
 821                         matching: Option<uint>,
 822                         matches_so_far: &mut Vec<(uint, P<ast::Variant>,
 823                                               Vec<(Span, Option<Ident>, @Expr)> )> ,
 824                         match_count: uint) -> @Expr {
 825         if match_count == self_args.len() {
 826             // we've matched against all arguments, so make the final
 827             // expression at the bottom of the match tree
 828             if matches_so_far.len() == 0 {
 829                 cx.span_bug(trait_.span,
 830                                 "no self match on an enum in \
 831                                 generic `deriving`");
 832             }
 833
 834             // `ref` inside let matches is buggy. Causes havoc wih rusc.
 835             // let (variant_index, ref self_vec) = matches_so_far[0];
 836             let (variant, self_vec) = match matches_so_far.get(0) {
 837                 &(_, v, ref s) => (v, s)
 838             };
 839
 840             // we currently have a vec of vecs, where each
 841             // subvec is the fields of one of the arguments,
 842             // but if the variants all match, we want this as
 843             // vec of tuples, where each tuple represents a
 844             // field.
 845
 846             // most arms don't have matching variants, so do a
 847             // quick check to see if they match (even though
 848             // this means iterating twice) instead of being
 849             // optimistic and doing a pile of allocations etc.
 850             let substructure = match matching {
 851                 Some(variant_index) => {
 852                     let mut enum_matching_fields = Vec::from_elem(self_vec.len(), Vec::new());
 853
 854                     for triple in matches_so_far.tail().iter() {
 855                         match triple {
 856                             &(_, _, ref other_fields) => {
 857                                 for (i, &(_, _, e)) in other_fields.iter().enumerate() {
 858                                     enum_matching_fields.get_mut(i).push(e);
 859                                 }
 860                             }
 861                         }
 862                     }
 863                     let field_tuples =
 864                         self_vec.iter()
 865                                 .zip(enum_matching_fields.iter())
 866                                 .map(|(&(span, id, self_f), other)| {
 867                         FieldInfo {
 868                             span: span,
 869                             name: id,
 870                             self_: self_f,
 871                             other: (*other).clone()
 872                         }
 873                     }).collect();
 874                     EnumMatching(variant_index, variant, field_tuples)
 875                 }
 876                 None => {
 877                     EnumNonMatching(matches_so_far.as_slice())
 878                 }
 879             };
 880             self.call_substructure_method(cx, trait_, type_ident,
 881                                           self_args, nonself_args,
 882                                           &substructure)
 883
 884         } else {  // there are still matches to create
 885             let current_match_str = if match_count == 0 {
 886                 "__self".to_string()
 887             } else {
 888                 format!("__arg_{}", match_count)
 889             };
 890
 891             let mut arms = Vec::new();
 892
 893             // the code for nonmatching variants only matters when
 894             // we've seen at least one other variant already
 895             if self.const_nonmatching && match_count > 0 {
 896                 // make a matching-variant match, and a _ match.
 897                 let index = match matching {
 898                     Some(i) => i,
 899                     None => cx.span_bug(trait_.span,
 900                                         "non-matching variants when required to \
 901                                         be matching in generic `deriving`")
 902                 };
 903
 904                 // matching-variant match
 905                 let variant = *enum_def.variants.get(index);
 906                 let (pattern, idents) = trait_.create_enum_variant_pattern(
 907                     cx,
 908                     variant,
 909                     current_match_str.as_slice(),
 910                     ast::MutImmutable);
 911
 912                 matches_so_far.push((index, variant, idents));
 913                 let arm_expr = self.build_enum_match(cx,
 914                                                      trait_,
 915                                                      enum_def,
 916                                                      type_ident,
 917                                                      self_args, nonself_args,
 918                                                      matching,
 919                                                      matches_so_far,
 920                                                      match_count + 1);
 921                 matches_so_far.pop().unwrap();
 922                 arms.push(cx.arm(trait_.span, vec!( pattern ), arm_expr));
 923
 924                 if enum_def.variants.len() > 1 {
 925                     let e = &EnumNonMatching(&[]);
 926                     let wild_expr = self.call_substructure_method(cx, trait_, type_ident,
 927                                                                   self_args, nonself_args,
 928                                                                   e);
 929                     let wild_arm = cx.arm(
 930                         trait_.span,
 931                         vec!( cx.pat_wild(trait_.span) ),
 932                         wild_expr);
 933                     arms.push(wild_arm);
 934                 }
 935             } else {
 936                 // create an arm matching on each variant
 937                 for (index, &variant) in enum_def.variants.iter().enumerate() {
 938                     let (pattern, idents) =
 939                         trait_.create_enum_variant_pattern(
 940                             cx,
 941                             variant,
 942                             current_match_str.as_slice(),
 943                             ast::MutImmutable);
 944
 945                     matches_so_far.push((index, variant, idents));
 946                     let new_matching =
 947                         match matching {
 948                             _ if match_count == 0 => Some(index),
 949                             Some(i) if index == i => Some(i),
 950                             _ => None
 951                         };
 952                     let arm_expr = self.build_enum_match(cx,
 953                                                          trait_,
 954                                                          enum_def,
 955                                                          type_ident,
 956                                                          self_args, nonself_args,
 957                                                          new_matching,
 958                                                          matches_so_far,
 959                                                          match_count + 1);
 960                     matches_so_far.pop().unwrap();
 961
 962                     let arm = cx.arm(trait_.span, vec!( pattern ), arm_expr);
 963                     arms.push(arm);
 964                 }
 965             }
 966
 967             // match foo { arm, arm, arm, ... }
 968             cx.expr_match(trait_.span, self_args[match_count], arms)
 969         }
 970     }
 971
 972     fn expand_static_enum_method_body(&self,
 973                                       cx: &mut ExtCtxt,
 974                                       trait_: &TraitDef,
 975                                       enum_def: &EnumDef,
 976                                       type_ident: Ident,
 977                                       self_args: &[@Expr],
 978                                       nonself_args: &[@Expr])
 979         -> @Expr {
 980         let summary = enum_def.variants.iter().map(|v| {
 981             let ident = v.node.name;
 982             let summary = match v.node.kind {
 983                 ast::TupleVariantKind(ref args) => {
 984                     Unnamed(args.iter().map(|va| trait_.set_expn_info(cx, va.ty.span)).collect())
 985                 }
 986                 ast::StructVariantKind(struct_def) => {
 987                     trait_.summarise_struct(cx, struct_def)
 988                 }
 989             };
 990             (ident, v.span, summary)
 991         }).collect();
 992         self.call_substructure_method(cx, trait_, type_ident,
 993                                       self_args, nonself_args,
 994                                       &StaticEnum(enum_def, summary))
 995     }
 996 }
 997
 998 #[deriving(PartialEq)] // dogfooding!
 999 enum StructType {
1000     Unknown, Record, Tuple
1001 }
1002
1003 // general helper methods.
1004 impl<'a> TraitDef<'a> {
1005     fn set_expn_info(&self,
1006                      cx: &mut ExtCtxt,
1007                      mut to_set: Span) -> Span {
1008         let trait_name = match self.path.path.last() {
1009             None => cx.span_bug(self.span, "trait with empty path in generic `deriving`"),
1010             Some(name) => *name
1011         };
1012         to_set.expn_info = Some(@codemap::ExpnInfo {
1013             call_site: to_set,
1014             callee: codemap::NameAndSpan {
1015                 name: format!("deriving({})", trait_name).to_string(),
1016                 format: codemap::MacroAttribute,
1017                 span: Some(self.span)
1018             }
1019         });
1020         to_set
1021     }
1022
1023     fn summarise_struct(&self,
1024                         cx: &mut ExtCtxt,
1025                         struct_def: &StructDef) -> StaticFields {
1026         let mut named_idents = Vec::new();
1027         let mut just_spans = Vec::new();
1028         for field in struct_def.fields.iter(){
1029             let sp = self.set_expn_info(cx, field.span);
1030             match field.node.kind {
1031                 ast::NamedField(ident, _) => named_idents.push((ident, sp)),
1032                 ast::UnnamedField(..) => just_spans.push(sp),
1033             }
1034         }
1035
1036         match (just_spans.is_empty(), named_idents.is_empty()) {
1037             (false, false) => cx.span_bug(self.span,
1038                                           "a struct with named and unnamed \
1039                                           fields in generic `deriving`"),
1040             // named fields
1041             (_, false) => Named(named_idents),
1042             // tuple structs (includes empty structs)
1043             (_, _)     => Unnamed(just_spans)
1044         }
1045     }
1046
1047     fn create_subpatterns(&self,
1048                           cx: &mut ExtCtxt,
1049                           field_paths: Vec<ast::Path> ,
1050                           mutbl: ast::Mutability)
1051                           -> Vec<@ast::Pat> {
1052         field_paths.iter().map(|path| {
1053             cx.pat(path.span,
1054                         ast::PatIdent(ast::BindByRef(mutbl), (*path).clone(), None))
1055             }).collect()
1056     }
1057
1058     fn create_struct_pattern(&self,
1059                              cx: &mut ExtCtxt,
1060                              struct_ident: Ident,
1061                              struct_def: &StructDef,
1062                              prefix: &str,
1063                              mutbl: ast::Mutability)
1064                              -> (@ast::Pat, Vec<(Span, Option<Ident>, @Expr)> ) {
1065         if struct_def.fields.is_empty() {
1066             return (
1067                 cx.pat_ident_binding_mode(
1068                     self.span, struct_ident, ast::BindByValue(ast::MutImmutable)),
1069                 Vec::new());
1070         }
1071
1072         let matching_path = cx.path(self.span, vec!( struct_ident ));
1073
1074         let mut paths = Vec::new();
1075         let mut ident_expr = Vec::new();
1076         let mut struct_type = Unknown;
1077
1078         for (i, struct_field) in struct_def.fields.iter().enumerate() {
1079             let sp = self.set_expn_info(cx, struct_field.span);
1080             let opt_id = match struct_field.node.kind {
1081                 ast::NamedField(ident, _) if (struct_type == Unknown ||
1082                                               struct_type == Record) => {
1083                     struct_type = Record;
1084                     Some(ident)
1085                 }
1086                 ast::UnnamedField(..) if (struct_type == Unknown ||
1087                                           struct_type == Tuple) => {
1088                     struct_type = Tuple;
1089                     None
1090                 }
1091                 _ => {
1092                     cx.span_bug(sp, "a struct with named and unnamed fields in `deriving`");
1093                 }
1094             };
1095             let path =
1096                 cx.path_ident(sp,
1097                               cx.ident_of(format!("{}_{}",
1098                                                   prefix,
1099                                                   i).as_slice()));
1100             paths.push(path.clone());
1101             let val = cx.expr(
1102                 sp, ast::ExprParen(
1103                     cx.expr_deref(sp, cx.expr_path(path))));
1104             ident_expr.push((sp, opt_id, val));
1105         }
1106
1107         let subpats = self.create_subpatterns(cx, paths, mutbl);
1108
1109         // struct_type is definitely not Unknown, since struct_def.fields
1110         // must be nonempty to reach here
1111         let pattern = if struct_type == Record {
1112             let field_pats = subpats.iter().zip(ident_expr.iter()).map(|(&pat, &(_, id, _))| {
1113                 // id is guaranteed to be Some
1114                 ast::FieldPat { ident: id.unwrap(), pat: pat }
1115             }).collect();
1116             cx.pat_struct(self.span, matching_path, field_pats)
1117         } else {
1118             cx.pat_enum(self.span, matching_path, subpats)
1119         };
1120
1121         (pattern, ident_expr)
1122     }
1123
1124     fn create_enum_variant_pattern(&self,
1125                                    cx: &mut ExtCtxt,
1126                                    variant: &ast::Variant,
1127                                    prefix: &str,
1128                                    mutbl: ast::Mutability)
1129         -> (@ast::Pat, Vec<(Span, Option<Ident>, @Expr)> ) {
1130         let variant_ident = variant.node.name;
1131         match variant.node.kind {
1132             ast::TupleVariantKind(ref variant_args) => {
1133                 if variant_args.is_empty() {
1134                     return (cx.pat_ident_binding_mode(variant.span, variant_ident,
1135                                                           ast::BindByValue(ast::MutImmutable)),
1136                             Vec::new());
1137                 }
1138
1139                 let matching_path = cx.path_ident(variant.span, variant_ident);
1140
1141                 let mut paths = Vec::new();
1142                 let mut ident_expr = Vec::new();
1143                 for (i, va) in variant_args.iter().enumerate() {
1144                     let sp = self.set_expn_info(cx, va.ty.span);
1145                     let path =
1146                         cx.path_ident(sp,
1147                                       cx.ident_of(format!("{}_{}",
1148                                                           prefix,
1149                                                           i).as_slice()));
1150
1151                     paths.push(path.clone());
1152                     let val = cx.expr(
1153                         sp, ast::ExprParen(cx.expr_deref(sp, cx.expr_path(path))));
1154                     ident_expr.push((sp, None, val));
1155                 }
1156
1157                 let subpats = self.create_subpatterns(cx, paths, mutbl);
1158
1159                 (cx.pat_enum(variant.span, matching_path, subpats),
1160                  ident_expr)
1161             }
1162             ast::StructVariantKind(struct_def) => {
1163                 self.create_struct_pattern(cx, variant_ident, struct_def,
1164                                            prefix, mutbl)
1165             }
1166         }
1167     }
1168 }
1169
1170 /* helpful premade recipes */
1171
1172 /**
1173 Fold the fields. `use_foldl` controls whether this is done
1174 left-to-right (`true`) or right-to-left (`false`).
1175 */
1176 pub fn cs_fold(use_foldl: bool,
1177                f: |&mut ExtCtxt, Span, @Expr, @Expr, &[@Expr]| -> @Expr,
1178                base: @Expr,
1179                enum_nonmatch_f: EnumNonMatchFunc,
1180                cx: &mut ExtCtxt,
1181                trait_span: Span,
1182                substructure: &Substructure)
1183                -> @Expr {
1184     match *substructure.fields {
1185         EnumMatching(_, _, ref all_fields) | Struct(ref all_fields) => {
1186             if use_foldl {
1187                 all_fields.iter().fold(base, |old, field| {
1188                     f(cx,
1189                       field.span,
1190                       old,
1191                       field.self_,
1192                       field.other.as_slice())
1193                 })
1194             } else {
1195                 all_fields.iter().rev().fold(base, |old, field| {
1196                     f(cx,
1197                       field.span,
1198                       old,
1199                       field.self_,
1200                       field.other.as_slice())
1201                 })
1202             }
1203         },
1204         EnumNonMatching(ref all_enums) => enum_nonmatch_f(cx, trait_span,
1205                                                           *all_enums,
1206                                                           substructure.nonself_args),
1207         StaticEnum(..) | StaticStruct(..) => {
1208             cx.span_bug(trait_span, "static function in `deriving`")
1209         }
1210     }
1211 }
1212
1213
1214 /**
1215 Call the method that is being derived on all the fields, and then
1216 process the collected results. i.e.
1217
1218 ~~~
1219 f(cx, span, ~[self_1.method(__arg_1_1, __arg_2_1),
1220               self_2.method(__arg_1_2, __arg_2_2)])
1221 ~~~
1222 */
1223 #[inline]
1224 pub fn cs_same_method(f: |&mut ExtCtxt, Span, Vec<@Expr> | -> @Expr,
1225                       enum_nonmatch_f: EnumNonMatchFunc,
1226                       cx: &mut ExtCtxt,
1227                       trait_span: Span,
1228                       substructure: &Substructure)
1229                       -> @Expr {
1230     match *substructure.fields {
1231         EnumMatching(_, _, ref all_fields) | Struct(ref all_fields) => {
1232             // call self_n.method(other_1_n, other_2_n, ...)
1233             let called = all_fields.iter().map(|field| {
1234                 cx.expr_method_call(field.span,
1235                                     field.self_,
1236                                     substructure.method_ident,
1237                                     field.other.iter()
1238                                                .map(|e| cx.expr_addr_of(field.span, *e))
1239                                                .collect())
1240             }).collect();
1241
1242             f(cx, trait_span, called)
1243         },
1244         EnumNonMatching(ref all_enums) => enum_nonmatch_f(cx, trait_span,
1245                                                           *all_enums,
1246                                                           substructure.nonself_args),
1247         StaticEnum(..) | StaticStruct(..) => {
1248             cx.span_bug(trait_span, "static function in `deriving`")
1249         }
1250     }
1251 }
1252
1253 /**
1254 Fold together the results of calling the derived method on all the
1255 fields. `use_foldl` controls whether this is done left-to-right
1256 (`true`) or right-to-left (`false`).
1257 */
1258 #[inline]
1259 pub fn cs_same_method_fold(use_foldl: bool,
1260                            f: |&mut ExtCtxt, Span, @Expr, @Expr| -> @Expr,
1261                            base: @Expr,
1262                            enum_nonmatch_f: EnumNonMatchFunc,
1263                            cx: &mut ExtCtxt,
1264                            trait_span: Span,
1265                            substructure: &Substructure)
1266                            -> @Expr {
1267     cs_same_method(
1268         |cx, span, vals| {
1269             if use_foldl {
1270                 vals.iter().fold(base, |old, &new| {
1271                     f(cx, span, old, new)
1272                 })
1273             } else {
1274                 vals.iter().rev().fold(base, |old, &new| {
1275                     f(cx, span, old, new)
1276                 })
1277             }
1278         },
1279         enum_nonmatch_f,
1280         cx, trait_span, substructure)
1281 }
1282
1283 /**
1284 Use a given binop to combine the result of calling the derived method
1285 on all the fields.
1286 */
1287 #[inline]
1288 pub fn cs_binop(binop: ast::BinOp, base: @Expr,
1289                 enum_nonmatch_f: EnumNonMatchFunc,
1290                 cx: &mut ExtCtxt, trait_span: Span,
1291                 substructure: &Substructure) -> @Expr {
1292     cs_same_method_fold(
1293         true, // foldl is good enough
1294         |cx, span, old, new| {
1295             cx.expr_binary(span,
1296                            binop,
1297                            old, new)
1298
1299         },
1300         base,
1301         enum_nonmatch_f,
1302         cx, trait_span, substructure)
1303 }
1304
1305 /// cs_binop with binop == or
1306 #[inline]
1307 pub fn cs_or(enum_nonmatch_f: EnumNonMatchFunc,
1308              cx: &mut ExtCtxt, span: Span,
1309              substructure: &Substructure) -> @Expr {
1310     cs_binop(ast::BiOr, cx.expr_bool(span, false),
1311              enum_nonmatch_f,
1312              cx, span, substructure)
1313 }
1314
1315 /// cs_binop with binop == and
1316 #[inline]
1317 pub fn cs_and(enum_nonmatch_f: EnumNonMatchFunc,
1318               cx: &mut ExtCtxt, span: Span,
1319               substructure: &Substructure) -> @Expr {
1320     cs_binop(ast::BiAnd, cx.expr_bool(span, true),
1321              enum_nonmatch_f,
1322              cx, span, substructure)
1323 }