src/libsyntax/ext/deriving/generic.rs

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