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