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