src/libsyntax/ext/deriving/generic.rs

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