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