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