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

   1 // Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Some code that abstracts away much of the boilerplate of writing
  12 //! `deriving` instances for traits. Among other things it manages getting
  13 //! access to the fields of the 4 different sorts of structs and enum
  14 //! variants, as well as creating the method and impl ast instances.
  15 //!
  16 //! Supported features (fairly exhaustive):
  17 //!
  18 //! - Methods taking any number of parameters of any type, and returning
  19 //!   any type, other than vectors, bottom and closures.
  20 //! - Generating `impl`s for types with type parameters and lifetimes
  21 //!   (e.g. `Option<T>`), the parameters are automatically given the
  22 //!   current trait as a bound. (This includes separate type parameters
  23 //!   and lifetimes for methods.)
  24 //! - Additional bounds on the type parameters, e.g. the `Ord` instance
  25 //!   requires an explicit `PartialEq` bound at the
  26 //!   moment. (`TraitDef.additional_bounds`)
  27 //!
  28 //! Unsupported: FIXME #6257: calling methods on reference fields,
  29 //! e.g. deriving Eq/Ord/Clone don't work on `struct A(&int)`,
  30 //! because of how the auto-dereferencing happens.
  31 //!
  32 //! The most important thing for implementers is the `Substructure` and
  33 //! `SubstructureFields` objects. The latter groups 5 possibilities of the
  34 //! arguments:
  35 //!
  36 //! - `Struct`, when `Self` is a struct (including tuple structs, e.g
  37 //!   `struct T(int, char)`).
  38 //! - `EnumMatching`, when `Self` is an enum and all the arguments are the
  39 //!   same variant of the enum (e.g. `Some(1)`, `Some(3)` and `Some(4)`)
  40 //! - `EnumNonMatching` when `Self` is an enum and the arguments are not
  41 //!   the same variant (e.g. `None`, `Some(1)` and `None`). If
  42 //!   `on_nonmatching == NonMatchesCollapse`, this will contain an empty list.
  43 //! - `StaticEnum` and `StaticStruct` for static methods, where the type
  44 //!   being derived upon is either an enum or struct respectively. (Any
  45 //!   argument with type Self is just grouped among the non-self
  46 //!   arguments.)
  47 //!
  48 //! In the first two cases, the values from the corresponding fields in
  49 //! all the arguments are grouped together. In the `EnumNonMatching` case
  50 //! this isn't possible (different variants have different fields), so the
  51 //! fields are grouped by which argument they come from. There are no
  52 //! fields with values in the static cases, so these are treated entirely
  53 //! differently.
  54 //!
  55 //! The non-static cases have `Option<ident>` in several places associated
  56 //! with field `expr`s. This represents the name of the field it is
  57 //! associated with. It is only not `None` when the associated field has
  58 //! an identifier in the source code. For example, the `x`s in the
  59 //! following snippet
  60 //!
  61 //! ```rust
  62 //! struct A { x : int }
  63 //!
  64 //! struct B(int);
  65 //!
  66 //! enum C {
  67 //!     C0(int),
  68 //!     C1 { x: int }
  69 //! }
  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 just
  76 //! spans of the fields or a list of spans and the field idents (for tuple
  77 //! structs and record structs, respectively), or a list of these, for
  78 //! enums (one for each variant). For empty struct and empty enum
  79 //! variants, it is represented as a count of 0.
  80 //!
  81 //! # Examples
  82 //!
  83 //! The following simplified `PartialEq` is used for in-code examples:
  84 //!
  85 //! ```rust
  86 //! trait PartialEq {
  87 //!     fn eq(&self, other: &Self);
  88 //! }
  89 //! impl PartialEq 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 `PartialEq`, `A`, `B` and `C`.
  98 //!
  99 //! ## Structs
 100 //!
 101 //! When generating the `expr` for the `A` impl, the `SubstructureFields` is
 102 //!
 103 //! ~~~text
 104 //! Struct(~[FieldInfo {
 105 //!            span: <span of x>
 106 //!            name: Some(<ident of x>),
 107 //!            self_: <expr for &self.x>,
 108 //!            other: ~[<expr for &other.x]
 109 //!          }])
 110 //! ~~~
 111 //!
 112 //! For the `B` impl, called with `B(a)` and `B(b)`,
 113 //!
 114 //! ~~~text
 115 //! Struct(~[FieldInfo {
 116 //!           span: <span of `int`>,
 117 //!           name: None,
 118 //!           <expr for &a>
 119 //!           ~[<expr for &b>]
 120 //!          }])
 121 //! ~~~
 122 //!
 123 //! ## Enums
 124 //!
 125 //! When generating the `expr` for a call with `self == C0(a)` and `other
 126 //! == C0(b)`, the SubstructureFields is
 127 //!
 128 //! ~~~text
 129 //! EnumMatching(0, <ast::Variant for C0>,
 130 //!              ~[FieldInfo {
 131 //!                 span: <span of int>
 132 //!                 name: None,
 133 //!                 self_: <expr for &a>,
 134 //!                 other: ~[<expr for &b>]
 135 //!               }])
 136 //! ~~~
 137 //!
 138 //! For `C1 {x}` and `C1 {x}`,
 139 //!
 140 //! ~~~text
 141 //! EnumMatching(1, <ast::Variant for C1>,
 142 //!              ~[FieldInfo {
 143 //!                 span: <span of x>
 144 //!                 name: Some(<ident of x>),
 145 //!                 self_: <expr for &self.x>,
 146 //!                 other: ~[<expr for &other.x>]
 147 //!                }])
 148 //! ~~~
 149 //!
 150 //! For `C0(a)` and `C1 {x}` ,
 151 //!
 152 //! ~~~text
 153 //! EnumNonMatchingCollapsed(
 154 //!     ~[<ident of self>, <ident of __arg_1>],
 155 //!     &[<ast::Variant for C0>, <ast::Variant for C1>],
 156 //!     &[<ident for self index value>, <ident of __arg_1 index value>])
 157 //! ~~~
 158 //!
 159 //! It is the same for when the arguments are flipped to `C1 {x}` and
 160 //! `C0(a)`; the only difference is what the values of the identifiers
 161 //! <ident for self index value> and <ident of __arg_1 index value> will
 162 //! be in the generated code.
 163 //!
 164 //! `EnumNonMatchingCollapsed` deliberately provides far less information
 165 //! than is generally available for a given pair of variants; see #15375
 166 //! for discussion.
 167 //!
 168 //! ## Static
 169 //!
 170 //! A static method on the above would result in,
 171 //!
 172 //! ~~~text
 173 //! StaticStruct(<ast::StructDef of A>, Named(~[(<ident of x>, <span of x>)]))
 174 //!
 175 //! StaticStruct(<ast::StructDef of B>, Unnamed(~[<span of x>]))
 176 //!
 177 //! StaticEnum(<ast::EnumDef of C>, ~[(<ident of C0>, <span of C0>, Unnamed(~[<span of int>])),
 178 //!                                   (<ident of C1>, <span of C1>,
 179 //!                                    Named(~[(<ident of x>, <span of x>)]))])
 180 //! ~~~
 181
 182 use std::cell::RefCell;
 183 use std::gc::{Gc, GC};
 184
 185 use ast;
 186 use ast::{P, EnumDef, Expr, Ident, Generics, StructDef};
 187 use ast_util;
 188 use attr;
 189 use attr::AttrMetaMethods;
 190 use ext::base::ExtCtxt;
 191 use ext::build::AstBuilder;
 192 use codemap;
 193 use codemap::Span;
 194 use owned_slice::OwnedSlice;
 195 use parse::token::InternedString;
 196 use parse::token::special_idents;
 197
 198 use self::ty::*;
 199
 200 pub mod ty;
 201
 202 pub struct TraitDef<'a> {
 203     /// The span for the current #[deriving(Foo)] header.
 204     pub span: Span,
 205
 206     pub attributes: Vec<ast::Attribute>,
 207
 208     /// Path of the trait, including any type parameters
 209     pub path: Path<'a>,
 210
 211     /// Additional bounds required of any type parameters of the type,
 212     /// other than the current trait
 213     pub additional_bounds: Vec<Ty<'a>>,
 214
 215     /// Any extra lifetimes and/or bounds, e.g. `D: serialize::Decoder`
 216     pub generics: LifetimeBounds<'a>,
 217
 218     pub methods: Vec<MethodDef<'a>>,
 219 }
 220
 221 #[deriving(PartialEq, Eq)]
 222 pub enum HandleNonMatchingEnums {
 223     /// handle all non-matches via one `_ => ..` clause
 224     NonMatchesCollapse,
 225
 226     /// handle all non-matches via one `_ => ..` clause that has
 227     /// access to a tuple of tags indicating each variant index.
 228     NonMatchesCollapseWithTags,
 229
 230     /// handle via n^k cases for n variants and k self-args
 231     NonMatchesExplode,
 232
 233     /// cannot encounter two enums of Self type
 234     NonMatchHandlingIrrelevant,
 235 }
 236
 237 pub struct MethodDef<'a> {
 238     /// name of the method
 239     pub name: &'a str,
 240     /// List of generics, e.g. `R: rand::Rng`
 241     pub generics: LifetimeBounds<'a>,
 242
 243     /// Whether there is a self argument (outer Option) i.e. whether
 244     /// this is a static function, and whether it is a pointer (inner
 245     /// Option)
 246     pub explicit_self: Option<Option<PtrTy<'a>>>,
 247
 248     /// Arguments other than the self argument
 249     pub args: Vec<Ty<'a>>,
 250
 251     /// Return type
 252     pub ret_ty: Ty<'a>,
 253
 254     pub attributes: Vec<ast::Attribute>,
 255
 256     /// How to handle nonmatching enums; `NonMatchesCollapse`
 257     /// indicates value is independent of the actual enum variants,
 258     /// i.e. can use _ => .. match.
 259     ///
 260     /// Note that if this is `NonMatchesExplode`, then deriving will
 261     /// generate `Omega(n^k)` code, where `n` is the number of
 262     /// variants and `k` is the number of arguments of `Self` type for
 263     /// the method (including the `self` argument, if any).  Strive to
 264     /// avoid use of `NonMatchesExplode`, to avoid generating
 265     /// quadratic amounts of code (#15375) or worse.
 266     pub on_nonmatching: HandleNonMatchingEnums,
 267
 268     pub combine_substructure: RefCell<CombineSubstructureFunc<'a>>,
 269 }
 270
 271 /// All the data about the data structure/method being derived upon.
 272 pub struct Substructure<'a> {
 273     /// ident of self
 274     pub type_ident: Ident,
 275     /// ident of the method
 276     pub method_ident: Ident,
 277     /// dereferenced access to any Self or Ptr(Self, _) arguments
 278     pub self_args: &'a [Gc<Expr>],
 279     /// verbatim access to any other arguments
 280     pub nonself_args: &'a [Gc<Expr>],
 281     pub fields: &'a SubstructureFields<'a>
 282 }
 283
 284 /// Summary of the relevant parts of a struct/enum field.
 285 pub struct FieldInfo {
 286     pub span: Span,
 287     /// None for tuple structs/normal enum variants, Some for normal
 288     /// structs/struct enum variants.
 289     pub name: Option<Ident>,
 290     /// The expression corresponding to this field of `self`
 291     /// (specifically, a reference to it).
 292     pub self_: Gc<Expr>,
 293     /// The expressions corresponding to references to this field in
 294     /// the other Self arguments.
 295     pub other: Vec<Gc<Expr>>,
 296 }
 297
 298 /// Fields for a static method
 299 pub enum StaticFields {
 300     /// Tuple structs/enum variants like this
 301     Unnamed(Vec<Span>),
 302     /// Normal structs/struct variants.
 303     Named(Vec<(Ident, Span)>),
 304 }
 305
 306 /// A summary of the possible sets of fields. See above for details
 307 /// and examples
 308 pub enum SubstructureFields<'a> {
 309     Struct(Vec<FieldInfo>),
 310     /**
 311     Matching variants of the enum: variant index, ast::Variant,
 312     fields: the field name is only non-`None` in the case of a struct
 313     variant.
 314     */
 315     EnumMatching(uint, &'a ast::Variant, Vec<FieldInfo>),
 316
 317     /**
 318     non-matching variants of the enum, [(variant index, ast::Variant,
 319     [field span, field ident, fields])] \(i.e. all fields for self are in the
 320     first tuple, for other1 are in the second tuple, etc.)
 321     */
 322     EnumNonMatching(&'a [(uint, P<ast::Variant>,
 323                           Vec<(Span, Option<Ident>, Gc<Expr>)>)]),
 324
 325     /**
 326     non-matching variants of the enum, but with all state hidden from
 327     the consequent code.  The first component holds Idents for all of
 328     the Self arguments; the second component is a slice of all of the
 329     variants for the enum itself, and the third component is a list of
 330     Idents bound to the variant index values for each of the actual
 331     input Self arguments.
 332     */
 333     EnumNonMatchingCollapsed(Vec<Ident>, &'a [Gc<ast::Variant>], &'a [Ident]),
 334
 335     /// A static method where Self is a struct.
 336     StaticStruct(&'a ast::StructDef, StaticFields),
 337     /// A static method where Self is an enum.
 338     StaticEnum(&'a ast::EnumDef, Vec<(Ident, Span, StaticFields)>),
 339 }
 340
 341
 342
 343 /**
 344 Combine the values of all the fields together. The last argument is
 345 all the fields of all the structures, see above for details.
 346 */
 347 pub type CombineSubstructureFunc<'a> =
 348     |&mut ExtCtxt, Span, &Substructure|: 'a -> Gc<Expr>;
 349
 350 /**
 351 Deal with non-matching enum variants.  The tuple is a list of
 352 identifiers (one for each Self argument, which could be any of the
 353 variants since they have been collapsed together) and the identifiers
 354 holding the variant index value for each of the Self arguments.  The
 355 last argument is all the non-Self args of the method being derived.
 356 */
 357 pub type EnumNonMatchCollapsedFunc<'a> =
 358     |&mut ExtCtxt,
 359            Span,
 360            (&[Ident], &[Ident]),
 361            &[Gc<Expr>]|: 'a
 362            -> Gc<Expr>;
 363
 364 pub fn combine_substructure<'a>(f: CombineSubstructureFunc<'a>)
 365     -> RefCell<CombineSubstructureFunc<'a>> {
 366     RefCell::new(f)
 367 }
 368
 369
 370 impl<'a> TraitDef<'a> {
 371     pub fn expand(&self,
 372                   cx: &mut ExtCtxt,
 373                   _mitem: Gc<ast::MetaItem>,
 374                   item: Gc<ast::Item>,
 375                   push: |Gc<ast::Item>|) {
 376         let newitem = match item.node {
 377             ast::ItemStruct(ref struct_def, ref generics) => {
 378                 self.expand_struct_def(cx,
 379                                        &**struct_def,
 380                                        item.ident,
 381                                        generics)
 382             }
 383             ast::ItemEnum(ref enum_def, ref generics) => {
 384                 self.expand_enum_def(cx,
 385                                      enum_def,
 386                                      item.ident,
 387                                      generics)
 388             }
 389             _ => return
 390         };
 391         // Keep the lint attributes of the previous item to control how the
 392         // generated implementations are linted
 393         let mut attrs = newitem.attrs.clone();
 394         attrs.extend(item.attrs.iter().filter(|a| {
 395             match a.name().get() {
 396                 "allow" | "warn" | "deny" | "forbid" => true,
 397                 _ => false,
 398             }
 399         }).map(|a| a.clone()));
 400         push(box(GC) ast::Item {
 401             attrs: attrs,
 402             ..(*newitem).clone()
 403         })
 404     }
 405
 406     /**
 407      *
 408      * Given that we are deriving a trait `Tr` for a type `T<'a, ...,
 409      * 'z, A, ..., Z>`, creates an impl like:
 410      *
 411      * ```ignore
 412      *      impl<'a, ..., 'z, A:Tr B1 B2, ..., Z: Tr B1 B2> Tr for T<A, ..., Z> { ... }
 413      * ```
 414      *
 415      * where B1, B2, ... are the bounds given by `bounds_paths`.'
 416      *
 417      */
 418     fn create_derived_impl(&self,
 419                            cx: &mut ExtCtxt,
 420                            type_ident: Ident,
 421                            generics: &Generics,
 422                            methods: Vec<Gc<ast::Method>> ) -> Gc<ast::Item> {
 423         let trait_path = self.path.to_path(cx, self.span, type_ident, generics);
 424
 425         let Generics { mut lifetimes, ty_params } =
 426             self.generics.to_generics(cx, self.span, type_ident, generics);
 427         let mut ty_params = ty_params.into_vec();
 428
 429         // Copy the lifetimes
 430         lifetimes.extend(generics.lifetimes.iter().map(|l| *l));
 431
 432         // Create the type parameters.
 433         ty_params.extend(generics.ty_params.iter().map(|ty_param| {
 434             // I don't think this can be moved out of the loop, since
 435             // a TyParamBound requires an ast id
 436             let mut bounds: Vec<_> =
 437                 // extra restrictions on the generics parameters to the type being derived upon
 438                 self.additional_bounds.iter().map(|p| {
 439                     cx.typarambound(p.to_path(cx, self.span,
 440                                                   type_ident, generics))
 441                 }).collect();
 442             // require the current trait
 443             bounds.push(cx.typarambound(trait_path.clone()));
 444
 445             cx.typaram(self.span,
 446                        ty_param.ident,
 447                        OwnedSlice::from_vec(bounds),
 448                        ty_param.unbound.clone(),
 449                        None)
 450         }));
 451         let trait_generics = Generics {
 452             lifetimes: lifetimes,
 453             ty_params: OwnedSlice::from_vec(ty_params)
 454         };
 455
 456         // Create the reference to the trait.
 457         let trait_ref = cx.trait_ref(trait_path);
 458
 459         // Create the type parameters on the `self` path.
 460         let self_ty_params = generics.ty_params.map(|ty_param| {
 461             cx.ty_ident(self.span, ty_param.ident)
 462         });
 463
 464         let self_lifetimes = generics.lifetimes.clone();
 465
 466         // Create the type of `self`.
 467         let self_type = cx.ty_path(
 468             cx.path_all(self.span, false, vec!( type_ident ), self_lifetimes,
 469                         self_ty_params.into_vec()), None);
 470
 471         let attr = cx.attribute(
 472             self.span,
 473             cx.meta_word(self.span,
 474                          InternedString::new("automatically_derived")));
 475         // Just mark it now since we know that it'll end up used downstream
 476         attr::mark_used(&attr);
 477         let opt_trait_ref = Some(trait_ref);
 478         let ident = ast_util::impl_pretty_name(&opt_trait_ref, &*self_type);
 479         cx.item(
 480             self.span,
 481             ident,
 482             (vec!(attr)).append(self.attributes.as_slice()),
 483             ast::ItemImpl(trait_generics, opt_trait_ref,
 484                           self_type, methods))
 485     }
 486
 487     fn expand_struct_def(&self,
 488                          cx: &mut ExtCtxt,
 489                          struct_def: &StructDef,
 490                          type_ident: Ident,
 491                          generics: &Generics) -> Gc<ast::Item> {
 492         let methods = self.methods.iter().map(|method_def| {
 493             let (explicit_self, self_args, nonself_args, tys) =
 494                 method_def.split_self_nonself_args(
 495                     cx, self, type_ident, generics);
 496
 497             let body = if method_def.is_static() {
 498                 method_def.expand_static_struct_method_body(
 499                     cx,
 500                     self,
 501                     struct_def,
 502                     type_ident,
 503                     self_args.as_slice(),
 504                     nonself_args.as_slice())
 505             } else {
 506                 method_def.expand_struct_method_body(cx,
 507                                                      self,
 508                                                      struct_def,
 509                                                      type_ident,
 510                                                      self_args.as_slice(),
 511                                                      nonself_args.as_slice())
 512             };
 513
 514             method_def.create_method(cx, self,
 515                                      type_ident, generics,
 516                                      explicit_self, tys,
 517                                      body)
 518         }).collect();
 519
 520         self.create_derived_impl(cx, type_ident, generics, methods)
 521     }
 522
 523     fn expand_enum_def(&self,
 524                        cx: &mut ExtCtxt,
 525                        enum_def: &EnumDef,
 526                        type_ident: Ident,
 527                        generics: &Generics) -> Gc<ast::Item> {
 528         let methods = self.methods.iter().map(|method_def| {
 529             let (explicit_self, self_args, nonself_args, tys) =
 530                 method_def.split_self_nonself_args(cx, self,
 531                                                    type_ident, generics);
 532
 533             let body = if method_def.is_static() {
 534                 method_def.expand_static_enum_method_body(
 535                     cx,
 536                     self,
 537                     enum_def,
 538                     type_ident,
 539                     self_args.as_slice(),
 540                     nonself_args.as_slice())
 541             } else {
 542                 method_def.expand_enum_method_body(cx,
 543                                                    self,
 544                                                    enum_def,
 545                                                    type_ident,
 546                                                    self_args.as_slice(),
 547                                                    nonself_args.as_slice())
 548             };
 549
 550             method_def.create_method(cx, self,
 551                                      type_ident, generics,
 552                                      explicit_self, tys,
 553                                      body)
 554         }).collect();
 555
 556         self.create_derived_impl(cx, type_ident, generics, methods)
 557     }
 558 }
 559
 560 fn variant_to_pat(cx: &mut ExtCtxt, sp: Span, variant: &ast::Variant)
 561                   -> Gc<ast::Pat> {
 562     let ident = cx.path_ident(sp, variant.node.name);
 563     cx.pat(sp, match variant.node.kind {
 564         ast::TupleVariantKind(..) => ast::PatEnum(ident, None),
 565         ast::StructVariantKind(..) => ast::PatStruct(ident, Vec::new(), true),
 566     })
 567 }
 568
 569 impl<'a> MethodDef<'a> {
 570     fn call_substructure_method(&self,
 571                                 cx: &mut ExtCtxt,
 572                                 trait_: &TraitDef,
 573                                 type_ident: Ident,
 574                                 self_args: &[Gc<Expr>],
 575                                 nonself_args: &[Gc<Expr>],
 576                                 fields: &SubstructureFields)
 577         -> Gc<Expr> {
 578         let substructure = Substructure {
 579             type_ident: type_ident,
 580             method_ident: cx.ident_of(self.name),
 581             self_args: self_args,
 582             nonself_args: nonself_args,
 583             fields: fields
 584         };
 585         let mut f = self.combine_substructure.borrow_mut();
 586         let f: &mut CombineSubstructureFunc = &mut *f;
 587         (*f)(cx, trait_.span, &substructure)
 588     }
 589
 590     fn get_ret_ty(&self,
 591                   cx: &mut ExtCtxt,
 592                   trait_: &TraitDef,
 593                   generics: &Generics,
 594                   type_ident: Ident)
 595                   -> P<ast::Ty> {
 596         self.ret_ty.to_ty(cx, trait_.span, type_ident, generics)
 597     }
 598
 599     fn is_static(&self) -> bool {
 600         self.explicit_self.is_none()
 601     }
 602
 603     fn split_self_nonself_args(&self,
 604                                cx: &mut ExtCtxt,
 605                                trait_: &TraitDef,
 606                                type_ident: Ident,
 607                                generics: &Generics)
 608         -> (ast::ExplicitSelf, Vec<Gc<Expr>>, Vec<Gc<Expr>>,
 609             Vec<(Ident, P<ast::Ty>)>) {
 610
 611         let mut self_args = Vec::new();
 612         let mut nonself_args = Vec::new();
 613         let mut arg_tys = Vec::new();
 614         let mut nonstatic = false;
 615
 616         let ast_explicit_self = match self.explicit_self {
 617             Some(ref self_ptr) => {
 618                 let (self_expr, explicit_self) =
 619                     ty::get_explicit_self(cx, trait_.span, self_ptr);
 620
 621                 self_args.push(self_expr);
 622                 nonstatic = true;
 623
 624                 explicit_self
 625             }
 626             None => codemap::respan(trait_.span, ast::SelfStatic),
 627         };
 628
 629         for (i, ty) in self.args.iter().enumerate() {
 630             let ast_ty = ty.to_ty(cx, trait_.span, type_ident, generics);
 631             let ident = cx.ident_of(format!("__arg_{}", i).as_slice());
 632             arg_tys.push((ident, ast_ty));
 633
 634             let arg_expr = cx.expr_ident(trait_.span, ident);
 635
 636             match *ty {
 637                 // for static methods, just treat any Self
 638                 // arguments as a normal arg
 639                 Self if nonstatic  => {
 640                     self_args.push(arg_expr);
 641                 }
 642                 Ptr(box Self, _) if nonstatic => {
 643                     self_args.push(cx.expr_deref(trait_.span, arg_expr))
 644                 }
 645                 _ => {
 646                     nonself_args.push(arg_expr);
 647                 }
 648             }
 649         }
 650
 651         (ast_explicit_self, self_args, nonself_args, arg_tys)
 652     }
 653
 654     fn create_method(&self,
 655                      cx: &mut ExtCtxt,
 656                      trait_: &TraitDef,
 657                      type_ident: Ident,
 658                      generics: &Generics,
 659                      explicit_self: ast::ExplicitSelf,
 660                      arg_types: Vec<(Ident, P<ast::Ty>)> ,
 661                      body: Gc<Expr>) -> Gc<ast::Method> {
 662         // create the generics that aren't for Self
 663         let fn_generics = self.generics.to_generics(cx, trait_.span, type_ident, generics);
 664
 665         let self_arg = match explicit_self.node {
 666             ast::SelfStatic => None,
 667             // creating fresh self id
 668             _ => Some(ast::Arg::new_self(trait_.span, ast::MutImmutable, special_idents::self_))
 669         };
 670         let args = {
 671             let args = arg_types.move_iter().map(|(name, ty)| {
 672                     cx.arg(trait_.span, name, ty)
 673                 });
 674             self_arg.move_iter().chain(args).collect()
 675         };
 676
 677         let ret_type = self.get_ret_ty(cx, trait_, generics, type_ident);
 678
 679         let method_ident = cx.ident_of(self.name);
 680         let fn_decl = cx.fn_decl(args, ret_type);
 681         let body_block = cx.block_expr(body);
 682
 683         // Create the method.
 684         box(GC) ast::Method {
 685             ident: method_ident,
 686             attrs: self.attributes.clone(),
 687             generics: fn_generics,
 688             explicit_self: explicit_self,
 689             fn_style: ast::NormalFn,
 690             decl: fn_decl,
 691             body: body_block,
 692             id: ast::DUMMY_NODE_ID,
 693             span: trait_.span,
 694             vis: ast::Inherited,
 695         }
 696     }
 697
 698     /**
 699    ~~~
 700     #[deriving(PartialEq)]
 701     struct A { x: int, y: int }
 702
 703     // equivalent to:
 704     impl PartialEq for A {
 705         fn eq(&self, __arg_1: &A) -> bool {
 706             match *self {
 707                 A {x: ref __self_0_0, y: ref __self_0_1} => {
 708                     match *__arg_1 {
 709                         A {x: ref __self_1_0, y: ref __self_1_1} => {
 710                             __self_0_0.eq(__self_1_0) && __self_0_1.eq(__self_1_1)
 711                         }
 712                     }
 713                 }
 714             }
 715         }
 716     }
 717    ~~~
 718     */
 719     fn expand_struct_method_body(&self,
 720                                  cx: &mut ExtCtxt,
 721                                  trait_: &TraitDef,
 722                                  struct_def: &StructDef,
 723                                  type_ident: Ident,
 724                                  self_args: &[Gc<Expr>],
 725                                  nonself_args: &[Gc<Expr>])
 726         -> Gc<Expr> {
 727
 728         let mut raw_fields = Vec::new(); // ~[[fields of self],
 729                                  // [fields of next Self arg], [etc]]
 730         let mut patterns = Vec::new();
 731         for i in range(0u, self_args.len()) {
 732             let (pat, ident_expr) =
 733                 trait_.create_struct_pattern(cx,
 734                                              type_ident,
 735                                              struct_def,
 736                                              format!("__self_{}",
 737                                                      i).as_slice(),
 738                                              ast::MutImmutable);
 739             patterns.push(pat);
 740             raw_fields.push(ident_expr);
 741         }
 742
 743         // transpose raw_fields
 744         let fields = if raw_fields.len() > 0 {
 745             raw_fields.get(0)
 746                       .iter()
 747                       .enumerate()
 748                       .map(|(i, &(span, opt_id, field))| {
 749                 let other_fields = raw_fields.tail().iter().map(|l| {
 750                     match l.get(i) {
 751                         &(_, _, ex) => ex
 752                     }
 753                 }).collect();
 754                 FieldInfo {
 755                     span: span,
 756                     name: opt_id,
 757                     self_: field,
 758                     other: other_fields
 759                 }
 760             }).collect()
 761         } else {
 762             cx.span_bug(trait_.span,
 763                         "no self arguments to non-static method in generic \
 764                          `deriving`")
 765         };
 766
 767         // body of the inner most destructuring match
 768         let mut body = self.call_substructure_method(
 769             cx,
 770             trait_,
 771             type_ident,
 772             self_args,
 773             nonself_args,
 774             &Struct(fields));
 775
 776         // make a series of nested matches, to destructure the
 777         // structs. This is actually right-to-left, but it shouldn't
 778         // matter.
 779         for (&arg_expr, &pat) in self_args.iter().zip(patterns.iter()) {
 780             body = cx.expr_match(trait_.span, arg_expr,
 781                                      vec!( cx.arm(trait_.span, vec!(pat), body) ))
 782         }
 783         body
 784     }
 785
 786     fn expand_static_struct_method_body(&self,
 787                                         cx: &mut ExtCtxt,
 788                                         trait_: &TraitDef,
 789                                         struct_def: &StructDef,
 790                                         type_ident: Ident,
 791                                         self_args: &[Gc<Expr>],
 792                                         nonself_args: &[Gc<Expr>])
 793         -> Gc<Expr> {
 794         let summary = trait_.summarise_struct(cx, struct_def);
 795
 796         self.call_substructure_method(cx,
 797                                       trait_,
 798                                       type_ident,
 799                                       self_args, nonself_args,
 800                                       &StaticStruct(struct_def, summary))
 801     }
 802
 803     /**
 804    ~~~
 805     #[deriving(PartialEq)]
 806     enum A {
 807         A1,
 808         A2(int)
 809     }
 810
 811     // is equivalent to
 812
 813     impl PartialEq for A {
 814         fn eq(&self, __arg_1: &A) -> ::bool {
 815             match (&*self, &*__arg_1) {
 816                 (&A1, &A1) => true,
 817                 (&A2(ref __self_0),
 818                  &A2(ref __arg_1_0)) => (*__self_0).eq(&(*__arg_1_0)),
 819                 _ => {
 820                     let __self_vi = match *self { A1(..) => 0u, A2(..) => 1u };
 821                     let __arg_1_vi = match *__arg_1 { A1(..) => 0u, A2(..) => 1u };
 822                     false
 823                 }
 824             }
 825         }
 826     }
 827    ~~~
 828
 829     (Of course `__self_vi` and `__arg_1_vi` are unused for
 830      `PartialEq`, and those subcomputations will hopefully be removed
 831      as their results are unused.  The point of `__self_vi` and
 832      `__arg_1_vi` is for `PartialOrd`; see #15503.)
 833     */
 834     fn expand_enum_method_body(&self,
 835                                cx: &mut ExtCtxt,
 836                                trait_: &TraitDef,
 837                                enum_def: &EnumDef,
 838                                type_ident: Ident,
 839                                self_args: &[Gc<Expr>],
 840                                nonself_args: &[Gc<Expr>])
 841                                -> Gc<Expr> {
 842         let mut matches = Vec::new();
 843         match self.on_nonmatching {
 844             NonMatchesCollapseWithTags =>
 845                 self.build_enum_match_tuple(
 846                     cx, trait_, enum_def, type_ident, self_args, nonself_args),
 847             NonMatchesCollapse | NonMatchesExplode | NonMatchHandlingIrrelevant =>
 848                 self.build_enum_match(
 849                     cx, trait_, enum_def, type_ident, self_args, nonself_args,
 850                     None, &mut matches, 0),
 851         }
 852     }
 853
 854
 855     /**
 856     Creates the nested matches for an enum definition recursively, i.e.
 857
 858    ~~~text
 859     match self {
 860        Variant1 => match other { Variant1 => matching, Variant2 => nonmatching, ... },
 861        Variant2 => match other { Variant1 => nonmatching, Variant2 => matching, ... },
 862        ...
 863     }
 864    ~~~
 865
 866     It acts in the most naive way, so every branch (and subbranch,
 867     subsubbranch, etc) exists, not just the ones where all the variants in
 868     the tree are the same. Hopefully the optimisers get rid of any
 869     repetition, otherwise derived methods with many Self arguments will be
 870     exponentially large.
 871
 872     `matching` is Some(n) if all branches in the tree above the
 873     current position are variant `n`, `None` otherwise (including on
 874     the first call).
 875     */
 876     fn build_enum_match(&self,
 877                         cx: &mut ExtCtxt,
 878                         trait_: &TraitDef,
 879                         enum_def: &EnumDef,
 880                         type_ident: Ident,
 881                         self_args: &[Gc<Expr>],
 882                         nonself_args: &[Gc<Expr>],
 883                         matching: Option<uint>,
 884                         matches_so_far: &mut Vec<(uint, P<ast::Variant>,
 885                                               Vec<(Span, Option<Ident>, Gc<Expr>)>)> ,
 886                         match_count: uint) -> Gc<Expr> {
 887         if match_count == self_args.len() {
 888             // we've matched against all arguments, so make the final
 889             // expression at the bottom of the match tree
 890             if matches_so_far.len() == 0 {
 891                 cx.span_bug(trait_.span,
 892                                 "no self match on an enum in \
 893                                 generic `deriving`");
 894             }
 895
 896             // `ref` inside let matches is buggy. Causes havoc with rusc.
 897             // let (variant_index, ref self_vec) = matches_so_far[0];
 898             let (variant, self_vec) = match matches_so_far.get(0) {
 899                 &(_, v, ref s) => (v, s)
 900             };
 901
 902             // we currently have a vec of vecs, where each
 903             // subvec is the fields of one of the arguments,
 904             // but if the variants all match, we want this as
 905             // vec of tuples, where each tuple represents a
 906             // field.
 907
 908             // most arms don't have matching variants, so do a
 909             // quick check to see if they match (even though
 910             // this means iterating twice) instead of being
 911             // optimistic and doing a pile of allocations etc.
 912             let substructure = match matching {
 913                 Some(variant_index) => {
 914                     let mut enum_matching_fields = Vec::from_elem(self_vec.len(), Vec::new());
 915
 916                     for triple in matches_so_far.tail().iter() {
 917                         match triple {
 918                             &(_, _, ref other_fields) => {
 919                                 for (i, &(_, _, e)) in other_fields.iter().enumerate() {
 920                                     enum_matching_fields.get_mut(i).push(e);
 921                                 }
 922                             }
 923                         }
 924                     }
 925                     let field_tuples =
 926                         self_vec.iter()
 927                                 .zip(enum_matching_fields.iter())
 928                                 .map(|(&(span, id, self_f), other)| {
 929                         FieldInfo {
 930                             span: span,
 931                             name: id,
 932                             self_: self_f,
 933                             other: (*other).clone()
 934                         }
 935                     }).collect();
 936                     EnumMatching(variant_index, &*variant, field_tuples)
 937                 }
 938                 None => {
 939                     EnumNonMatching(matches_so_far.as_slice())
 940                 }
 941             };
 942             self.call_substructure_method(cx, trait_, type_ident,
 943                                           self_args, nonself_args,
 944                                           &substructure)
 945
 946         } else {  // there are still matches to create
 947             let current_match_str = if match_count == 0 {
 948                 "__self".to_string()
 949             } else {
 950                 format!("__arg_{}", match_count)
 951             };
 952
 953             let mut arms = Vec::new();
 954
 955             assert!(self.on_nonmatching == NonMatchesCollapse ||
 956                     self.on_nonmatching == NonMatchesExplode ||
 957                     self.on_nonmatching == NonMatchHandlingIrrelevant);
 958
 959             // the code for nonmatching variants only matters when
 960             // we've seen at least one other variant already
 961             assert!(match_count == 0 ||
 962                     self.on_nonmatching != NonMatchHandlingIrrelevant);
 963             if self.on_nonmatching == NonMatchesCollapse && match_count > 0 {
 964                 // make a matching-variant match, and a _ match.
 965                 let index = match matching {
 966                     Some(i) => i,
 967                     None => cx.span_bug(trait_.span,
 968                                         "non-matching variants when required to \
 969                                         be matching in generic `deriving`")
 970                 };
 971
 972                 // matching-variant match
 973                 let variant = *enum_def.variants.get(index);
 974                 let (pattern, idents) = trait_.create_enum_variant_pattern(
 975                     cx,
 976                     &*variant,
 977                     current_match_str.as_slice(),
 978                     ast::MutImmutable);
 979
 980                 matches_so_far.push((index, variant, idents));
 981                 let arm_expr = self.build_enum_match(cx,
 982                                                      trait_,
 983                                                      enum_def,
 984                                                      type_ident,
 985                                                      self_args, nonself_args,
 986                                                      matching,
 987                                                      matches_so_far,
 988                                                      match_count + 1);
 989                 matches_so_far.pop().unwrap();
 990                 arms.push(cx.arm(trait_.span, vec!( pattern ), arm_expr));
 991
 992                 if enum_def.variants.len() > 1 {
 993                     let e = &EnumNonMatching(&[]);
 994                     let wild_expr = self.call_substructure_method(cx, trait_, type_ident,
 995                                                                   self_args, nonself_args,
 996                                                                   e);
 997                     let wild_arm = cx.arm(
 998                         trait_.span,
 999                         vec!( cx.pat_wild(trait_.span) ),
1000                         wild_expr);
1001                     arms.push(wild_arm);
1002                 }
1003             } else {
1004                 // create an arm matching on each variant
1005                 for (index, &variant) in enum_def.variants.iter().enumerate() {
1006                     let (pattern, idents) =
1007                         trait_.create_enum_variant_pattern(
1008                             cx,
1009                             &*variant,
1010                             current_match_str.as_slice(),
1011                             ast::MutImmutable);
1012
1013                     matches_so_far.push((index, variant, idents));
1014                     let new_matching =
1015                         match matching {
1016                             _ if match_count == 0 => Some(index),
1017                             Some(i) if index == i => Some(i),
1018                             _ => None
1019                         };
1020                     let arm_expr = self.build_enum_match(cx,
1021                                                          trait_,
1022                                                          enum_def,
1023                                                          type_ident,
1024                                                          self_args, nonself_args,
1025                                                          new_matching,
1026                                                          matches_so_far,
1027                                                          match_count + 1);
1028                     matches_so_far.pop().unwrap();
1029
1030                     let arm = cx.arm(trait_.span, vec!( pattern ), arm_expr);
1031                     arms.push(arm);
1032                 }
1033             }
1034
1035             // match foo { arm, arm, arm, ... }
1036             cx.expr_match(trait_.span, self_args[match_count], arms)
1037         }
1038     }
1039
1040     /**
1041     Creates a match for a tuple of all `self_args`, where either all
1042     variants match, or it falls into a catch-all for when one variant
1043     does not match.
1044
1045     There are N + 1 cases because is a case for each of the N
1046     variants where all of the variants match, and one catch-all for
1047     when one does not match.
1048
1049     The catch-all handler is provided access the variant index values
1050     for each of the self-args, carried in precomputed variables. (Nota
1051     bene: the variant index values are not necessarily the
1052     discriminant values.  See issue #15523.)
1053
1054     ~~~text
1055     match (this, that, ...) {
1056       (Variant1, Variant1, Variant1) => ... // delegate Matching on Variant1
1057       (Variant2, Variant2, Variant2) => ... // delegate Matching on Variant2
1058       ...
1059       _ => {
1060         let __this_vi = match this { Variant1 => 0u, Variant2 => 1u, ... };
1061         let __that_vi = match that { Variant1 => 0u, Variant2 => 1u, ... };
1062         ... // catch-all remainder can inspect above variant index values.
1063       }
1064     }
1065     ~~~
1066     */
1067     fn build_enum_match_tuple(
1068         &self,
1069         cx: &mut ExtCtxt,
1070         trait_: &TraitDef,
1071         enum_def: &EnumDef,
1072         type_ident: Ident,
1073         self_args: &[Gc<Expr>],
1074         nonself_args: &[Gc<Expr>]) -> Gc<Expr> {
1075
1076         let sp = trait_.span;
1077         let variants = &enum_def.variants;
1078
1079         let self_arg_names = self_args.iter().enumerate()
1080             .map(|(arg_count, _self_arg)| {
1081                 if arg_count == 0 {
1082                     "__self".to_string()
1083                 } else {
1084                     format!("__arg_{}", arg_count)
1085                 }
1086             })
1087             .collect::<Vec<String>>();
1088
1089         let self_arg_idents = self_arg_names.iter()
1090             .map(|name|cx.ident_of(name.as_slice()))
1091             .collect::<Vec<ast::Ident>>();
1092
1093         // The `vi_idents` will be bound, solely in the catch-all, to
1094         // a series of let statements mapping each self_arg to a uint
1095         // corresponding to its variant index.
1096         let vi_idents : Vec<ast::Ident> = self_arg_names.iter()
1097             .map(|name| { let vi_suffix = format!("{:s}_vi", name.as_slice());
1098                           cx.ident_of(vi_suffix.as_slice()) })
1099             .collect::<Vec<ast::Ident>>();
1100
1101         // Builds, via callback to call_substructure_method, the
1102         // delegated expression that handles the catch-all case,
1103         // using `__variants_tuple` to drive logic if necessary.
1104         let catch_all_substructure = EnumNonMatchingCollapsed(
1105             self_arg_idents, variants.as_slice(), vi_idents.as_slice());
1106
1107         // These arms are of the form:
1108         // (Variant1, Variant1, ...) => Body1
1109         // (Variant2, Variant2, ...) => Body2
1110         // ...
1111         // where each tuple has length = self_args.len()
1112         let mut match_arms : Vec<ast::Arm> = variants.iter().enumerate()
1113             .map(|(index, &variant)| {
1114
1115                 // These self_pats have form Variant1, Variant2, ...
1116                 let self_pats : Vec<(Gc<ast::Pat>,
1117                                      Vec<(Span, Option<Ident>, Gc<Expr>)>)>;
1118                 self_pats = self_arg_names.iter()
1119                     .map(|self_arg_name|
1120                          trait_.create_enum_variant_pattern(
1121                              cx, &*variant, self_arg_name.as_slice(),
1122                              ast::MutImmutable))
1123                     .collect();
1124
1125                 // A single arm has form (&VariantK, &VariantK, ...) => BodyK
1126                 // (see "Final wrinkle" note below for why.)
1127                 let subpats = self_pats.iter()
1128                     .map(|&(p, ref _idents)| cx.pat(sp, ast::PatRegion(p)))
1129                     .collect::<Vec<Gc<ast::Pat>>>();
1130
1131                 // Here is the pat = `(&VariantK, &VariantK, ...)`
1132                 let single_pat = cx.pat(sp, ast::PatTup(subpats));
1133
1134                 // For the BodyK, we need to delegate to our caller,
1135                 // passing it an EnumMatching to indicate which case
1136                 // we are in.
1137
1138                 // All of the Self args have the same variant in these
1139                 // cases.  So we transpose the info in self_pats to
1140                 // gather the getter expressions together, in the form
1141                 // that EnumMatching expects.
1142
1143                 // The transposition is driven by walking across the
1144                 // arg fields of the variant for the first self pat.
1145                 let &(_, ref self_arg_fields) = self_pats.get(0);
1146
1147                 let field_tuples : Vec<FieldInfo>;
1148
1149                 field_tuples = self_arg_fields.iter().enumerate()
1150                     // For each arg field of self, pull out its getter expr ...
1151                     .map(|(field_index, &(sp, opt_ident, self_getter_expr))| {
1152                         // ... but FieldInfo also wants getter expr
1153                         // for matching other arguments of Self type;
1154                         // so walk across the *other* self_pats and
1155                         // pull out getter for same field in each of
1156                         // them (using `field_index` tracked above).
1157                         // That is the heart of the transposition.
1158                         let others = self_pats.tail().iter()
1159                             .map(|&(_pat, ref fields)| {
1160
1161                                 let &(_, _opt_ident, other_getter_expr) =
1162                                     fields.get(field_index);
1163
1164                                 // All Self args have same variant, so
1165                                 // opt_idents are the same.  (Assert
1166                                 // here to make it self-evident that
1167                                 // it is okay to ignore `_opt_ident`.)
1168                                 assert!(opt_ident == _opt_ident);
1169
1170                                 other_getter_expr
1171                             }).collect::<Vec<Gc<Expr>>>();
1172
1173                         FieldInfo { span: sp,
1174                                     name: opt_ident,
1175                                     self_: self_getter_expr,
1176                                     other: others,
1177                         }
1178                     }).collect::<Vec<FieldInfo>>();
1179
1180                 // Now, for some given VariantK, we have built up
1181                 // expressions for referencing every field of every
1182                 // Self arg, assuming all are instances of VariantK.
1183                 // Build up code associated with such a case.
1184                 let substructure = EnumMatching(index, variant, field_tuples);
1185                 let arm_expr = self.call_substructure_method(
1186                     cx, trait_, type_ident, self_args, nonself_args,
1187                     &substructure);
1188
1189                 cx.arm(sp, vec![single_pat], arm_expr)
1190             }).collect();
1191
1192         // We will usually need the catch-all after matching the
1193         // tuples `(VariantK, VariantK, ...)` for each VariantK of the
1194         // enum.  But:
1195         //
1196         // * when there is only one Self arg, the arms above suffice
1197         // (and the deriving we call back into may not be prepared to
1198         // handle EnumNonMatchCollapsed), and,
1199         //
1200         // * when the enum has only one variant, the single arm that
1201         // is already present always suffices.
1202         //
1203         // * In either of the two cases above, if we *did* add a
1204         //   catch-all `_` match, it would trigger the
1205         //   unreachable-pattern error.
1206         //
1207         if variants.len() > 1 && self_args.len() > 1 {
1208             let arms : Vec<ast::Arm> = variants.iter().enumerate()
1209                 .map(|(index, &variant)| {
1210                     let pat = variant_to_pat(cx, sp, &*variant);
1211                     let lit = ast::LitUint(index as u64, ast::TyU);
1212                     cx.arm(sp, vec![pat], cx.expr_lit(sp, lit))
1213                 }).collect();
1214
1215             // Build a series of let statements mapping each self_arg
1216             // to a uint corresponding to its variant index.
1217             // i.e. for `enum E<T> { A, B(1), C(T, T) }`, and a deriving
1218             // with three Self args, builds three statements:
1219             //
1220             // ```
1221             // let __self0_vi = match   self {
1222             //     A => 0u, B(..) => 1u, C(..) => 2u
1223             // };
1224             // let __self1_vi = match __arg1 {
1225             //     A => 0u, B(..) => 1u, C(..) => 2u
1226             // };
1227             // let __self2_vi = match __arg2 {
1228             //     A => 0u, B(..) => 1u, C(..) => 2u
1229             // };
1230             // ```
1231             let mut index_let_stmts : Vec<Gc<ast::Stmt>> = Vec::new();
1232             for (&ident, &self_arg) in vi_idents.iter().zip(self_args.iter()) {
1233                 let variant_idx = cx.expr_match(sp, self_arg, arms.clone());
1234                 let let_stmt = cx.stmt_let(sp, false, ident, variant_idx);
1235                 index_let_stmts.push(let_stmt);
1236             }
1237
1238             let arm_expr = self.call_substructure_method(
1239                 cx, trait_, type_ident, self_args, nonself_args,
1240                 &catch_all_substructure);
1241
1242             // Builds the expression:
1243             // {
1244             //   let __self0_vi = ...;
1245             //   let __self1_vi = ...;
1246             //   ...
1247             //   <delegated expression referring to __self0_vi, et al.>
1248             // }
1249             let arm_expr = cx.expr_block(
1250                 cx.block_all(sp, Vec::new(), index_let_stmts, Some(arm_expr)));
1251
1252             // Builds arm:
1253             // _ => { let __self0_vi = ...;
1254             //        let __self1_vi = ...;
1255             //        ...
1256             //        <delegated expression as above> }
1257             let catch_all_match_arm =
1258                 cx.arm(sp, vec![cx.pat_wild(sp)], arm_expr);
1259
1260             match_arms.push(catch_all_match_arm);
1261
1262         } else if variants.len() == 0 {
1263             // As an additional wrinkle, For a zero-variant enum A,
1264             // currently the compiler
1265             // will accept `fn (a: &Self) { match   *a   { } }`
1266             // but rejects `fn (a: &Self) { match (&*a,) { } }`
1267             // as well as  `fn (a: &Self) { match ( *a,) { } }`
1268             //
1269             // This means that the strategy of building up a tuple of
1270             // all Self arguments fails when Self is a zero variant
1271             // enum: rustc rejects the expanded program, even though
1272             // the actual code tends to be impossible to execute (at
1273             // least safely), according to the type system.
1274             //
1275             // The most expedient fix for this is to just let the
1276             // code fall through to the catch-all.  But even this is
1277             // error-prone, since the catch-all as defined above would
1278             // generate code like this:
1279             //
1280             //     _ => { let __self0 = match *self { };
1281             //            let __self1 = match *__arg_0 { };
1282             //            <catch-all-expr> }
1283             //
1284             // Which is yields bindings for variables which type
1285             // inference cannot resolve to unique types.
1286             //
1287             // One option to the above might be to add explicit type
1288             // annotations.  But the *only* reason to go down that path
1289             // would be to try to make the expanded output consistent
1290             // with the case when the number of enum variants >= 1.
1291             //
1292             // That just isn't worth it.  In fact, trying to generate
1293             // sensible code for *any* deriving on a zero-variant enum
1294             // does not make sense.  But at the same time, for now, we
1295             // do not want to cause a compile failure just because the
1296             // user happened to attach a deriving to their
1297             // zero-variant enum.
1298             //
1299             // Instead, just generate a failing expression for the
1300             // zero variant case, skipping matches and also skipping
1301             // delegating back to the end user code entirely.
1302             //
1303             // (See also #4499 and #12609; note that some of the
1304             // discussions there influence what choice we make here;
1305             // e.g. if we feature-gate `match x { ... }` when x refers
1306             // to an uninhabited type (e.g. a zero-variant enum or a
1307             // type holding such an enum), but do not feature-gate
1308             // zero-variant enums themselves, then attempting to
1309             // derive Show on such a type could here generate code
1310             // that needs the feature gate enabled.)
1311
1312             return cx.expr_unreachable(sp);
1313         }
1314
1315         // Final wrinkle: the self_args are expressions that deref
1316         // down to desired l-values, but we cannot actually deref
1317         // them when they are fed as r-values into a tuple
1318         // expression; here add a layer of borrowing, turning
1319         // `(*self, *__arg_0, ...)` into `(&*self, &*__arg_0, ...)`.
1320         let borrowed_self_args = self_args.iter()
1321             .map(|&self_arg| cx.expr_addr_of(sp, self_arg))
1322             .collect::<Vec<Gc<ast::Expr>>>();
1323         let match_arg = cx.expr(sp, ast::ExprTup(borrowed_self_args));
1324         cx.expr_match(sp, match_arg, match_arms)
1325     }
1326
1327     fn expand_static_enum_method_body(&self,
1328                                       cx: &mut ExtCtxt,
1329                                       trait_: &TraitDef,
1330                                       enum_def: &EnumDef,
1331                                       type_ident: Ident,
1332                                       self_args: &[Gc<Expr>],
1333                                       nonself_args: &[Gc<Expr>])
1334         -> Gc<Expr> {
1335         let summary = enum_def.variants.iter().map(|v| {
1336             let ident = v.node.name;
1337             let summary = match v.node.kind {
1338                 ast::TupleVariantKind(ref args) => {
1339                     Unnamed(args.iter().map(|va| trait_.set_expn_info(cx, va.ty.span)).collect())
1340                 }
1341                 ast::StructVariantKind(ref struct_def) => {
1342                     trait_.summarise_struct(cx, &**struct_def)
1343                 }
1344             };
1345             (ident, v.span, summary)
1346         }).collect();
1347         self.call_substructure_method(cx, trait_, type_ident,
1348                                       self_args, nonself_args,
1349                                       &StaticEnum(enum_def, summary))
1350     }
1351 }
1352
1353 #[deriving(PartialEq)] // dogfooding!
1354 enum StructType {
1355     Unknown, Record, Tuple
1356 }
1357
1358 // general helper methods.
1359 impl<'a> TraitDef<'a> {
1360     fn set_expn_info(&self,
1361                      cx: &mut ExtCtxt,
1362                      mut to_set: Span) -> Span {
1363         let trait_name = match self.path.path.last() {
1364             None => cx.span_bug(self.span, "trait with empty path in generic `deriving`"),
1365             Some(name) => *name
1366         };
1367         to_set.expn_info = Some(box(GC) codemap::ExpnInfo {
1368             call_site: to_set,
1369             callee: codemap::NameAndSpan {
1370                 name: format!("deriving({})", trait_name),
1371                 format: codemap::MacroAttribute,
1372                 span: Some(self.span)
1373             }
1374         });
1375         to_set
1376     }
1377
1378     fn summarise_struct(&self,
1379                         cx: &mut ExtCtxt,
1380                         struct_def: &StructDef) -> StaticFields {
1381         let mut named_idents = Vec::new();
1382         let mut just_spans = Vec::new();
1383         for field in struct_def.fields.iter(){
1384             let sp = self.set_expn_info(cx, field.span);
1385             match field.node.kind {
1386                 ast::NamedField(ident, _) => named_idents.push((ident, sp)),
1387                 ast::UnnamedField(..) => just_spans.push(sp),
1388             }
1389         }
1390
1391         match (just_spans.is_empty(), named_idents.is_empty()) {
1392             (false, false) => cx.span_bug(self.span,
1393                                           "a struct with named and unnamed \
1394                                           fields in generic `deriving`"),
1395             // named fields
1396             (_, false) => Named(named_idents),
1397             // tuple structs (includes empty structs)
1398             (_, _)     => Unnamed(just_spans)
1399         }
1400     }
1401
1402     fn create_subpatterns(&self,
1403                           cx: &mut ExtCtxt,
1404                           field_paths: Vec<ast::SpannedIdent> ,
1405                           mutbl: ast::Mutability)
1406                           -> Vec<Gc<ast::Pat>> {
1407         field_paths.iter().map(|path| {
1408             cx.pat(path.span,
1409                         ast::PatIdent(ast::BindByRef(mutbl), (*path).clone(), None))
1410             }).collect()
1411     }
1412
1413     fn create_struct_pattern(&self,
1414                              cx: &mut ExtCtxt,
1415                              struct_ident: Ident,
1416                              struct_def: &StructDef,
1417                              prefix: &str,
1418                              mutbl: ast::Mutability)
1419                              -> (Gc<ast::Pat>, Vec<(Span, Option<Ident>, Gc<Expr>)>) {
1420         if struct_def.fields.is_empty() {
1421             return (
1422                 cx.pat_ident_binding_mode(
1423                     self.span, struct_ident, ast::BindByValue(ast::MutImmutable)),
1424                 Vec::new());
1425         }
1426
1427         let matching_path = cx.path(self.span, vec!( struct_ident ));
1428
1429         let mut paths = Vec::new();
1430         let mut ident_expr = Vec::new();
1431         let mut struct_type = Unknown;
1432
1433         for (i, struct_field) in struct_def.fields.iter().enumerate() {
1434             let sp = self.set_expn_info(cx, struct_field.span);
1435             let opt_id = match struct_field.node.kind {
1436                 ast::NamedField(ident, _) if (struct_type == Unknown ||
1437                                               struct_type == Record) => {
1438                     struct_type = Record;
1439                     Some(ident)
1440                 }
1441                 ast::UnnamedField(..) if (struct_type == Unknown ||
1442                                           struct_type == Tuple) => {
1443                     struct_type = Tuple;
1444                     None
1445                 }
1446                 _ => {
1447                     cx.span_bug(sp, "a struct with named and unnamed fields in `deriving`");
1448                 }
1449             };
1450             let ident = cx.ident_of(format!("{}_{}", prefix, i).as_slice());
1451             paths.push(codemap::Spanned{span: sp, node: ident});
1452             let val = cx.expr(
1453                 sp, ast::ExprParen(cx.expr_deref(sp, cx.expr_path(cx.path_ident(sp,ident)))));
1454             ident_expr.push((sp, opt_id, val));
1455         }
1456
1457         let subpats = self.create_subpatterns(cx, paths, mutbl);
1458
1459         // struct_type is definitely not Unknown, since struct_def.fields
1460         // must be nonempty to reach here
1461         let pattern = if struct_type == Record {
1462             let field_pats = subpats.iter().zip(ident_expr.iter()).map(|(&pat, &(_, id, _))| {
1463                 // id is guaranteed to be Some
1464                 ast::FieldPat { ident: id.unwrap(), pat: pat }
1465             }).collect();
1466             cx.pat_struct(self.span, matching_path, field_pats)
1467         } else {
1468             cx.pat_enum(self.span, matching_path, subpats)
1469         };
1470
1471         (pattern, ident_expr)
1472     }
1473
1474     fn create_enum_variant_pattern(&self,
1475                                    cx: &mut ExtCtxt,
1476                                    variant: &ast::Variant,
1477                                    prefix: &str,
1478                                    mutbl: ast::Mutability)
1479         -> (Gc<ast::Pat>, Vec<(Span, Option<Ident>, Gc<Expr>)> ) {
1480         let variant_ident = variant.node.name;
1481         match variant.node.kind {
1482             ast::TupleVariantKind(ref variant_args) => {
1483                 if variant_args.is_empty() {
1484                     return (cx.pat_ident_binding_mode(variant.span, variant_ident,
1485                                                           ast::BindByValue(ast::MutImmutable)),
1486                             Vec::new());
1487                 }
1488
1489                 let matching_path = cx.path_ident(variant.span, variant_ident);
1490
1491                 let mut paths = Vec::new();
1492                 let mut ident_expr = Vec::new();
1493                 for (i, va) in variant_args.iter().enumerate() {
1494                     let sp = self.set_expn_info(cx, va.ty.span);
1495                     let ident = cx.ident_of(format!("{}_{}", prefix, i).as_slice());
1496                     let path1 = codemap::Spanned{span: sp, node: ident};
1497                     paths.push(path1);
1498                     let expr_path = cx.expr_path(cx.path_ident(sp, ident));
1499                     let val = cx.expr(sp, ast::ExprParen(cx.expr_deref(sp, expr_path)));
1500                     ident_expr.push((sp, None, val));
1501                 }
1502
1503                 let subpats = self.create_subpatterns(cx, paths, mutbl);
1504
1505                 (cx.pat_enum(variant.span, matching_path, subpats),
1506                  ident_expr)
1507             }
1508             ast::StructVariantKind(ref struct_def) => {
1509                 self.create_struct_pattern(cx, variant_ident, &**struct_def,
1510                                            prefix, mutbl)
1511             }
1512         }
1513     }
1514 }
1515
1516 /* helpful premade recipes */
1517
1518 /**
1519 Fold the fields. `use_foldl` controls whether this is done
1520 left-to-right (`true`) or right-to-left (`false`).
1521 */
1522 pub fn cs_fold(use_foldl: bool,
1523                f: |&mut ExtCtxt, Span, Gc<Expr>, Gc<Expr>, &[Gc<Expr>]| -> Gc<Expr>,
1524                base: Gc<Expr>,
1525                enum_nonmatch_f: EnumNonMatchFunc,
1526                enum_nonmatch_g: EnumNonMatchCollapsedFunc,
1527                cx: &mut ExtCtxt,
1528                trait_span: Span,
1529                substructure: &Substructure)
1530                -> Gc<Expr> {
1531     match *substructure.fields {
1532         EnumMatching(_, _, ref all_fields) | Struct(ref all_fields) => {
1533             if use_foldl {
1534                 all_fields.iter().fold(base, |old, field| {
1535                     f(cx,
1536                       field.span,
1537                       old,
1538                       field.self_,
1539                       field.other.as_slice())
1540                 })
1541             } else {
1542                 all_fields.iter().rev().fold(base, |old, field| {
1543                     f(cx,
1544                       field.span,
1545                       old,
1546                       field.self_,
1547                       field.other.as_slice())
1548                 })
1549             }
1550         },
1551         EnumNonMatching(ref all_enums) =>
1552             enum_nonmatch_f(cx, trait_span, *all_enums,
1553                             substructure.nonself_args),
1554         EnumNonMatchingCollapsed(ref all_args, _, tuple) =>
1555             enum_nonmatch_g(cx, trait_span, (all_args.as_slice(), tuple),
1556                             substructure.nonself_args),
1557         StaticEnum(..) | StaticStruct(..) => {
1558             cx.span_bug(trait_span, "static function in `deriving`")
1559         }
1560     }
1561 }
1562
1563
1564 /**
1565 Call the method that is being derived on all the fields, and then
1566 process the collected results. i.e.
1567
1568 ~~~
1569 f(cx, span, ~[self_1.method(__arg_1_1, __arg_2_1),
1570               self_2.method(__arg_1_2, __arg_2_2)])
1571 ~~~
1572 */
1573 #[inline]
1574 pub fn cs_same_method(f: |&mut ExtCtxt, Span, Vec<Gc<Expr>>| -> Gc<Expr>,
1575                       enum_nonmatch_f: EnumNonMatchFunc,
1576                       enum_nonmatch_g: EnumNonMatchCollapsedFunc,
1577                       cx: &mut ExtCtxt,
1578                       trait_span: Span,
1579                       substructure: &Substructure)
1580                       -> Gc<Expr> {
1581     match *substructure.fields {
1582         EnumMatching(_, _, ref all_fields) | Struct(ref all_fields) => {
1583             // call self_n.method(other_1_n, other_2_n, ...)
1584             let called = all_fields.iter().map(|field| {
1585                 cx.expr_method_call(field.span,
1586                                     field.self_,
1587                                     substructure.method_ident,
1588                                     field.other.iter()
1589                                                .map(|e| cx.expr_addr_of(field.span, *e))
1590                                                .collect())
1591             }).collect();
1592
1593             f(cx, trait_span, called)
1594         },
1595         EnumNonMatching(ref all_enums) =>
1596             enum_nonmatch_f(cx, trait_span, *all_enums,
1597                             substructure.nonself_args),
1598         EnumNonMatchingCollapsed(ref all_self_args, _, tuple) =>
1599             enum_nonmatch_g(cx, trait_span, (all_self_args.as_slice(), tuple),
1600                             substructure.nonself_args),
1601         StaticEnum(..) | StaticStruct(..) => {
1602             cx.span_bug(trait_span, "static function in `deriving`")
1603         }
1604     }
1605 }
1606
1607 /**
1608 Fold together the results of calling the derived method on all the
1609 fields. `use_foldl` controls whether this is done left-to-right
1610 (`true`) or right-to-left (`false`).
1611 */
1612 #[inline]
1613 pub fn cs_same_method_fold(use_foldl: bool,
1614                            f: |&mut ExtCtxt, Span, Gc<Expr>, Gc<Expr>| -> Gc<Expr>,
1615                            base: Gc<Expr>,
1616                            enum_nonmatch_f: EnumNonMatchFunc,
1617                            enum_nonmatch_g: EnumNonMatchCollapsedFunc,
1618                            cx: &mut ExtCtxt,
1619                            trait_span: Span,
1620                            substructure: &Substructure)
1621                            -> Gc<Expr> {
1622     cs_same_method(
1623         |cx, span, vals| {
1624             if use_foldl {
1625                 vals.iter().fold(base, |old, &new| {
1626                     f(cx, span, old, new)
1627                 })
1628             } else {
1629                 vals.iter().rev().fold(base, |old, &new| {
1630                     f(cx, span, old, new)
1631                 })
1632             }
1633         },
1634         enum_nonmatch_f,
1635         enum_nonmatch_g,
1636         cx, trait_span, substructure)
1637 }
1638
1639 /**
1640 Use a given binop to combine the result of calling the derived method
1641 on all the fields.
1642 */
1643 #[inline]
1644 pub fn cs_binop(binop: ast::BinOp, base: Gc<Expr>,
1645                 enum_nonmatch_f: EnumNonMatchFunc,
1646                 enum_nonmatch_g: EnumNonMatchCollapsedFunc,
1647                 cx: &mut ExtCtxt, trait_span: Span,
1648                 substructure: &Substructure) -> Gc<Expr> {
1649     cs_same_method_fold(
1650         true, // foldl is good enough
1651         |cx, span, old, new| {
1652             cx.expr_binary(span,
1653                            binop,
1654                            old, new)
1655
1656         },
1657         base,
1658         enum_nonmatch_f,
1659         enum_nonmatch_g,
1660         cx, trait_span, substructure)
1661 }
1662
1663 /// cs_binop with binop == or
1664 #[inline]
1665 pub fn cs_or(enum_nonmatch_f: EnumNonMatchFunc,
1666              enum_nonmatch_g: EnumNonMatchCollapsedFunc,
1667              cx: &mut ExtCtxt, span: Span,
1668              substructure: &Substructure) -> Gc<Expr> {
1669     cs_binop(ast::BiOr, cx.expr_bool(span, false),
1670              enum_nonmatch_f,
1671              enum_nonmatch_g,
1672              cx, span, substructure)
1673 }
1674
1675 /// cs_binop with binop == and
1676 #[inline]
1677 pub fn cs_and(enum_nonmatch_f: EnumNonMatchFunc,
1678               enum_nonmatch_g: EnumNonMatchCollapsedFunc,
1679               cx: &mut ExtCtxt, span: Span,
1680               substructure: &Substructure) -> Gc<Expr> {
1681     cs_binop(ast::BiAnd, cx.expr_bool(span, true),
1682              enum_nonmatch_f,
1683              enum_nonmatch_g,
1684              cx, span, substructure)
1685 }