src/libsyntax/ext/deriving/generic/mod.rs

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