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 //! `derive` 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 (`TraitDef.additional_bounds`)
  25 //!
  26 //! The most important thing for implementors is the `Substructure` and
  27 //! `SubstructureFields` objects. The latter groups 5 possibilities of the
  28 //! arguments:
  29 //!
  30 //! - `Struct`, when `Self` is a struct (including tuple structs, e.g
  31 //!   `struct T(i32, char)`).
  32 //! - `EnumMatching`, when `Self` is an enum and all the arguments are the
  33 //!   same variant of the enum (e.g. `Some(1)`, `Some(3)` and `Some(4)`)
  34 //! - `EnumNonMatchingCollapsed` when `Self` is an enum and the arguments
  35 //!   are not the same variant (e.g. `None`, `Some(1)` and `None`).
  36 //! - `StaticEnum` and `StaticStruct` for static methods, where the type
  37 //!   being derived upon is either an enum or struct respectively. (Any
  38 //!   argument with type Self is just grouped among the non-self
  39 //!   arguments.)
  40 //!
  41 //! In the first two cases, the values from the corresponding fields in
  42 //! all the arguments are grouped together. For `EnumNonMatchingCollapsed`
  43 //! this isn't possible (different variants have different fields), so the
  44 //! fields are inaccessible. (Previous versions of the deriving infrastructure
  45 //! had a way to expand into code that could access them, at the cost of
  46 //! generating exponential amounts of code; see issue #15375). There are no
  47 //! fields with values in the static cases, so these are treated entirely
  48 //! differently.
  49 //!
  50 //! The non-static cases have `Option<ident>` in several places associated
  51 //! with field `expr`s. This represents the name of the field it is
  52 //! associated with. It is only not `None` when the associated field has
  53 //! an identifier in the source code. For example, the `x`s in the
  54 //! following snippet
  55 //!
  56 //! ```rust
  57 //! # #![allow(dead_code)]
  58 //! struct A { x : i32 }
  59 //!
  60 //! struct B(i32);
  61 //!
  62 //! enum C {
  63 //!     C0(i32),
  64 //!     C1 { x: i32 }
  65 //! }
  66 //! ```
  67 //!
  68 //! The `i32`s in `B` and `C0` don't have an identifier, so the
  69 //! `Option<ident>`s would be `None` for them.
  70 //!
  71 //! In the static cases, the structure is summarised, either into the just
  72 //! spans of the fields or a list of spans and the field idents (for tuple
  73 //! structs and record structs, respectively), or a list of these, for
  74 //! enums (one for each variant). For empty struct and empty enum
  75 //! variants, it is represented as a count of 0.
  76 //!
  77 //! # "`cs`" functions
  78 //!
  79 //! The `cs_...` functions ("combine substructure) are designed to
  80 //! make life easier by providing some pre-made recipes for common
  81 //! threads; mostly calling the function being derived on all the
  82 //! arguments and then combining them back together in some way (or
  83 //! letting the user chose that). They are not meant to be the only
  84 //! way to handle the structures that this code creates.
  85 //!
  86 //! # Examples
  87 //!
  88 //! The following simplified `PartialEq` is used for in-code examples:
  89 //!
  90 //! ```rust
  91 //! trait PartialEq {
  92 //!     fn eq(&self, other: &Self) -> bool;
  93 //! }
  94 //! impl PartialEq for i32 {
  95 //!     fn eq(&self, other: &i32) -> bool {
  96 //!         *self == *other
  97 //!     }
  98 //! }
  99 //! ```
 100 //!
 101 //! Some examples of the values of `SubstructureFields` follow, using the
 102 //! above `PartialEq`, `A`, `B` and `C`.
 103 //!
 104 //! ## Structs
 105 //!
 106 //! When generating the `expr` for the `A` impl, the `SubstructureFields` is
 107 //!
 108 //! ```{.text}
 109 //! Struct(vec![FieldInfo {
 110 //!            span: <span of x>
 111 //!            name: Some(<ident of x>),
 112 //!            self_: <expr for &self.x>,
 113 //!            other: vec![<expr for &other.x]
 114 //!          }])
 115 //! ```
 116 //!
 117 //! For the `B` impl, called with `B(a)` and `B(b)`,
 118 //!
 119 //! ```{.text}
 120 //! Struct(vec![FieldInfo {
 121 //!           span: <span of `i32`>,
 122 //!           name: None,
 123 //!           self_: <expr for &a>
 124 //!           other: vec![<expr for &b>]
 125 //!          }])
 126 //! ```
 127 //!
 128 //! ## Enums
 129 //!
 130 //! When generating the `expr` for a call with `self == C0(a)` and `other
 131 //! == C0(b)`, the SubstructureFields is
 132 //!
 133 //! ```{.text}
 134 //! EnumMatching(0, <ast::Variant for C0>,
 135 //!              vec![FieldInfo {
 136 //!                 span: <span of i32>
 137 //!                 name: None,
 138 //!                 self_: <expr for &a>,
 139 //!                 other: vec![<expr for &b>]
 140 //!               }])
 141 //! ```
 142 //!
 143 //! For `C1 {x}` and `C1 {x}`,
 144 //!
 145 //! ```{.text}
 146 //! EnumMatching(1, <ast::Variant for C1>,
 147 //!              vec![FieldInfo {
 148 //!                 span: <span of x>
 149 //!                 name: Some(<ident of x>),
 150 //!                 self_: <expr for &self.x>,
 151 //!                 other: vec![<expr for &other.x>]
 152 //!                }])
 153 //! ```
 154 //!
 155 //! For `C0(a)` and `C1 {x}` ,
 156 //!
 157 //! ```{.text}
 158 //! EnumNonMatchingCollapsed(
 159 //!     vec![<ident of self>, <ident of __arg_1>],
 160 //!     &[<ast::Variant for C0>, <ast::Variant for C1>],
 161 //!     &[<ident for self index value>, <ident of __arg_1 index value>])
 162 //! ```
 163 //!
 164 //! It is the same for when the arguments are flipped to `C1 {x}` and
 165 //! `C0(a)`; the only difference is what the values of the identifiers
 166 //! <ident for self index value> and <ident of __arg_1 index value> will
 167 //! be in the generated code.
 168 //!
 169 //! `EnumNonMatchingCollapsed` deliberately provides far less information
 170 //! than is generally available for a given pair of variants; see #15375
 171 //! for discussion.
 172 //!
 173 //! ## Static
 174 //!
 175 //! A static method on the types above would result in,
 176 //!
 177 //! ```{.text}
 178 //! StaticStruct(<ast::VariantData of A>, Named(vec![(<ident of x>, <span of x>)]))
 179 //!
 180 //! StaticStruct(<ast::VariantData of B>, Unnamed(vec![<span of x>]))
 181 //!
 182 //! StaticEnum(<ast::EnumDef of C>,
 183 //!            vec![(<ident of C0>, <span of C0>, Unnamed(vec![<span of i32>])),
 184 //!                 (<ident of C1>, <span of C1>, Named(vec![(<ident of x>, <span of x>)]))])
 185 //! ```
 186
 187 pub use self::StaticFields::*;
 188 pub use self::SubstructureFields::*;
 189
 190 use std::cell::RefCell;
 191 use std::collections::HashSet;
 192 use std::vec;
 193
 194 use rustc_target::spec::abi::Abi;
 195 use syntax::ast::{
 196     self, BinOpKind, EnumDef, Expr, GenericParam, Generics, Ident, PatKind, VariantData
 197 };
 198
 199 use syntax::attr;
 200 use syntax::ext::base::{Annotatable, ExtCtxt};
 201 use syntax::ext::build::AstBuilder;
 202 use syntax::codemap::{self, dummy_spanned, respan};
 203 use syntax::util::move_map::MoveMap;
 204 use syntax::ptr::P;
 205 use syntax::symbol::{Symbol, keywords};
 206 use syntax_pos::{DUMMY_SP, Span};
 207 use errors::Handler;
 208
 209 use self::ty::{LifetimeBounds, Path, Ptr, PtrTy, Self_, Ty};
 210
 211 use deriving;
 212
 213 pub mod ty;
 214
 215 pub struct TraitDef<'a> {
 216     /// The span for the current #[derive(Foo)] header.
 217     pub span: Span,
 218
 219     pub attributes: Vec<ast::Attribute>,
 220
 221     /// Path of the trait, including any type parameters
 222     pub path: Path<'a>,
 223
 224     /// Additional bounds required of any type parameters of the type,
 225     /// other than the current trait
 226     pub additional_bounds: Vec<Ty<'a>>,
 227
 228     /// Any extra lifetimes and/or bounds, e.g. `D: serialize::Decoder`
 229     pub generics: LifetimeBounds<'a>,
 230
 231     /// Is it an `unsafe` trait?
 232     pub is_unsafe: bool,
 233
 234     /// Can this trait be derived for unions?
 235     pub supports_unions: bool,
 236
 237     pub methods: Vec<MethodDef<'a>>,
 238
 239     pub associated_types: Vec<(ast::Ident, Ty<'a>)>,
 240 }
 241
 242
 243 pub struct MethodDef<'a> {
 244     /// name of the method
 245     pub name: &'a str,
 246     /// List of generics, e.g. `R: rand::Rng`
 247     pub generics: LifetimeBounds<'a>,
 248
 249     /// Whether there is a self argument (outer Option) i.e. whether
 250     /// this is a static function, and whether it is a pointer (inner
 251     /// Option)
 252     pub explicit_self: Option<Option<PtrTy<'a>>>,
 253
 254     /// Arguments other than the self argument
 255     pub args: Vec<(Ty<'a>, &'a str)>,
 256
 257     /// Return type
 258     pub ret_ty: Ty<'a>,
 259
 260     pub attributes: Vec<ast::Attribute>,
 261
 262     // Is it an `unsafe fn`?
 263     pub is_unsafe: bool,
 264
 265     /// Can we combine fieldless variants for enums into a single match arm?
 266     pub unify_fieldless_variants: bool,
 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 [P<Expr>],
 279     /// verbatim access to any other arguments
 280     pub nonself_args: &'a [P<Expr>],
 281     pub fields: &'a SubstructureFields<'a>,
 282 }
 283
 284 /// Summary of the relevant parts of a struct/enum field.
 285 pub struct FieldInfo<'a> {
 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_: P<Expr>,
 293     /// The expressions corresponding to references to this field in
 294     /// the other `Self` arguments.
 295     pub other: Vec<P<Expr>>,
 296     /// The attributes on the field
 297     pub attrs: &'a [ast::Attribute],
 298 }
 299
 300 /// Fields for a static method
 301 pub enum StaticFields {
 302     /// Tuple and unit structs/enum variants like this.
 303     Unnamed(Vec<Span>, bool /*is tuple*/),
 304     /// Normal structs/struct variants.
 305     Named(Vec<(Ident, Span)>),
 306 }
 307
 308 /// A summary of the possible sets of fields.
 309 pub enum SubstructureFields<'a> {
 310     Struct(&'a ast::VariantData, Vec<FieldInfo<'a>>),
 311     /// Matching variants of the enum: variant index, variant count, ast::Variant,
 312     /// fields: the field name is only non-`None` in the case of a struct
 313     /// variant.
 314     EnumMatching(usize, usize, &'a ast::Variant, Vec<FieldInfo<'a>>),
 315
 316     /// Non-matching variants of the enum, but with all state hidden from
 317     /// the consequent code.  The first component holds `Ident`s for all of
 318     /// the `Self` arguments; the second component is a slice of all of the
 319     /// variants for the enum itself, and the third component is a list of
 320     /// `Ident`s bound to the variant index values for each of the actual
 321     /// input `Self` arguments.
 322     EnumNonMatchingCollapsed(Vec<Ident>, &'a [ast::Variant], &'a [Ident]),
 323
 324     /// A static method where `Self` is a struct.
 325     StaticStruct(&'a ast::VariantData, StaticFields),
 326     /// A static method where `Self` is an enum.
 327     StaticEnum(&'a ast::EnumDef, Vec<(Ident, Span, StaticFields)>),
 328 }
 329
 330
 331
 332 /// Combine the values of all the fields together. The last argument is
 333 /// all the fields of all the structures.
 334 pub type CombineSubstructureFunc<'a> =
 335     Box<FnMut(&mut ExtCtxt, Span, &Substructure) -> P<Expr> + 'a>;
 336
 337 /// Deal with non-matching enum variants.  The tuple is a list of
 338 /// identifiers (one for each `Self` argument, which could be any of the
 339 /// variants since they have been collapsed together) and the identifiers
 340 /// holding the variant index value for each of the `Self` arguments.  The
 341 /// last argument is all the non-`Self` args of the method being derived.
 342 pub type EnumNonMatchCollapsedFunc<'a> =
 343     Box<FnMut(&mut ExtCtxt, Span, (&[Ident], &[Ident]), &[P<Expr>]) -> P<Expr> + 'a>;
 344
 345 pub fn combine_substructure<'a>(f: CombineSubstructureFunc<'a>)
 346                                 -> RefCell<CombineSubstructureFunc<'a>> {
 347     RefCell::new(f)
 348 }
 349
 350 /// This method helps to extract all the type parameters referenced from a
 351 /// type. For a type parameter `<T>`, it looks for either a `TyPath` that
 352 /// is not global and starts with `T`, or a `TyQPath`.
 353 fn find_type_parameters(ty: &ast::Ty,
 354                         ty_param_names: &[ast::Name],
 355                         span: Span,
 356                         cx: &ExtCtxt)
 357                         -> Vec<P<ast::Ty>> {
 358     use syntax::visit;
 359
 360     struct Visitor<'a, 'b: 'a> {
 361         cx: &'a ExtCtxt<'b>,
 362         span: Span,
 363         ty_param_names: &'a [ast::Name],
 364         types: Vec<P<ast::Ty>>,
 365     }
 366
 367     impl<'a, 'b> visit::Visitor<'a> for Visitor<'a, 'b> {
 368         fn visit_ty(&mut self, ty: &'a ast::Ty) {
 369             if let ast::TyKind::Path(_, ref path) = ty.node {
 370                 if let Some(segment) = path.segments.first() {
 371                     if self.ty_param_names.contains(&segment.ident.name) {
 372                         self.types.push(P(ty.clone()));
 373                     }
 374                 }
 375             }
 376
 377             visit::walk_ty(self, ty)
 378         }
 379
 380         fn visit_mac(&mut self, mac: &ast::Mac) {
 381             let span = mac.span.with_ctxt(self.span.ctxt());
 382             self.cx.span_err(span, "`derive` cannot be used on items with type macros");
 383         }
 384     }
 385
 386     let mut visitor = Visitor {
 387         ty_param_names,
 388         types: Vec::new(),
 389         span,
 390         cx,
 391     };
 392
 393     visit::Visitor::visit_ty(&mut visitor, ty);
 394
 395     visitor.types
 396 }
 397
 398 impl<'a> TraitDef<'a> {
 399     pub fn expand(self,
 400                   cx: &mut ExtCtxt,
 401                   mitem: &ast::MetaItem,
 402                   item: &'a Annotatable,
 403                   push: &mut FnMut(Annotatable)) {
 404         self.expand_ext(cx, mitem, item, push, false);
 405     }
 406
 407     pub fn expand_ext(self,
 408                       cx: &mut ExtCtxt,
 409                       mitem: &ast::MetaItem,
 410                       item: &'a Annotatable,
 411                       push: &mut FnMut(Annotatable),
 412                       from_scratch: bool) {
 413         match *item {
 414             Annotatable::Item(ref item) => {
 415                 let is_packed = item.attrs.iter().any(|attr| {
 416                     for r in attr::find_repr_attrs(&cx.parse_sess.span_diagnostic, attr) {
 417                         if let attr::ReprPacked(_) = r {
 418                             return true;
 419                         }
 420                     }
 421                     false
 422                 });
 423                 let has_no_type_params = match item.node {
 424                     ast::ItemKind::Struct(_, ref generics) |
 425                     ast::ItemKind::Enum(_, ref generics) |
 426                     ast::ItemKind::Union(_, ref generics) => {
 427                         !generics.params.iter().any(|p| p.is_type_param())
 428                     }
 429                     _ => {
 430                         // Non-ADT derive is an error, but it should have been
 431                         // set earlier; see
 432                         // libsyntax/ext/expand.rs:MacroExpander::expand()
 433                         return;
 434                     }
 435                 };
 436                 let is_always_copy =
 437                     attr::contains_name(&item.attrs, "rustc_copy_clone_marker") &&
 438                     has_no_type_params;
 439                 let use_temporaries = is_packed && is_always_copy;
 440
 441                 let newitem = match item.node {
 442                     ast::ItemKind::Struct(ref struct_def, ref generics) => {
 443                         self.expand_struct_def(cx, &struct_def, item.ident, generics, from_scratch,
 444                                                use_temporaries)
 445                     }
 446                     ast::ItemKind::Enum(ref enum_def, ref generics) => {
 447                         // We ignore `use_temporaries` here, because
 448                         // `repr(packed)` enums cause an error later on.
 449                         //
 450                         // This can only cause further compilation errors
 451                         // downstream in blatantly illegal code, so it
 452                         // is fine.
 453                         self.expand_enum_def(cx, enum_def, &item.attrs,
 454                                              item.ident, generics, from_scratch)
 455                     }
 456                     ast::ItemKind::Union(ref struct_def, ref generics) => {
 457                         if self.supports_unions {
 458                             self.expand_struct_def(cx, &struct_def, item.ident,
 459                                                    generics, from_scratch,
 460                                                    use_temporaries)
 461                         } else {
 462                             cx.span_err(mitem.span,
 463                                         "this trait cannot be derived for unions");
 464                             return;
 465                         }
 466                     }
 467                     _ => unreachable!(),
 468                 };
 469                 // Keep the lint attributes of the previous item to control how the
 470                 // generated implementations are linted
 471                 let mut attrs = newitem.attrs.clone();
 472                 attrs.extend(item.attrs
 473                     .iter()
 474                     .filter(|a| {
 475                         match &*a.name().as_str() {
 476                             "allow" | "warn" | "deny" | "forbid" | "stable" | "unstable" => true,
 477                             _ => false,
 478                         }
 479                     })
 480                     .cloned());
 481                 push(Annotatable::Item(P(ast::Item { attrs: attrs, ..(*newitem).clone() })))
 482             }
 483             _ => {
 484                 // Non-Item derive is an error, but it should have been
 485                 // set earlier; see
 486                 // libsyntax/ext/expand.rs:MacroExpander::expand()
 487                 return;
 488             }
 489         }
 490     }
 491
 492     /// Given that we are deriving a trait `DerivedTrait` for a type like:
 493     ///
 494     /// ```ignore (only-for-syntax-highlight)
 495     /// struct Struct<'a, ..., 'z, A, B: DeclaredTrait, C, ..., Z> where C: WhereTrait {
 496     ///     a: A,
 497     ///     b: B::Item,
 498     ///     b1: <B as DeclaredTrait>::Item,
 499     ///     c1: <C as WhereTrait>::Item,
 500     ///     c2: Option<<C as WhereTrait>::Item>,
 501     ///     ...
 502     /// }
 503     /// ```
 504     ///
 505     /// create an impl like:
 506     ///
 507     /// ```ignore (only-for-syntax-highlight)
 508     /// impl<'a, ..., 'z, A, B: DeclaredTrait, C, ...  Z> where
 509     ///     C:                       WhereTrait,
 510     ///     A: DerivedTrait + B1 + ... + BN,
 511     ///     B: DerivedTrait + B1 + ... + BN,
 512     ///     C: DerivedTrait + B1 + ... + BN,
 513     ///     B::Item:                 DerivedTrait + B1 + ... + BN,
 514     ///     <C as WhereTrait>::Item: DerivedTrait + B1 + ... + BN,
 515     ///     ...
 516     /// {
 517     ///     ...
 518     /// }
 519     /// ```
 520     ///
 521     /// where B1, ..., BN are the bounds given by `bounds_paths`.'. Z is a phantom type, and
 522     /// therefore does not get bound by the derived trait.
 523     fn create_derived_impl(&self,
 524                            cx: &mut ExtCtxt,
 525                            type_ident: Ident,
 526                            generics: &Generics,
 527                            field_tys: Vec<P<ast::Ty>>,
 528                            methods: Vec<ast::ImplItem>)
 529                            -> P<ast::Item> {
 530         let trait_path = self.path.to_path(cx, self.span, type_ident, generics);
 531
 532         // Transform associated types from `deriving::ty::Ty` into `ast::ImplItem`
 533         let associated_types = self.associated_types.iter().map(|&(ident, ref type_def)| {
 534             ast::ImplItem {
 535                 id: ast::DUMMY_NODE_ID,
 536                 span: self.span,
 537                 ident,
 538                 vis: respan(self.span.shrink_to_lo(), ast::VisibilityKind::Inherited),
 539                 defaultness: ast::Defaultness::Final,
 540                 attrs: Vec::new(),
 541                 generics: Generics::default(),
 542                 node: ast::ImplItemKind::Type(type_def.to_ty(cx, self.span, type_ident, generics)),
 543                 tokens: None,
 544             }
 545         });
 546
 547         let Generics { mut params, mut where_clause, span } = self.generics
 548             .to_generics(cx, self.span, type_ident, generics);
 549
 550         // Create the generic parameters
 551         params.extend(generics.params.iter().map(|param| {
 552             match *param {
 553                 ref l @ GenericParam::Lifetime(_) => l.clone(),
 554                 GenericParam::Type(ref ty_param) => {
 555                     // I don't think this can be moved out of the loop, since
 556                     // a TyParamBound requires an ast id
 557                     let mut bounds: Vec<_> =
 558                         // extra restrictions on the generics parameters to the
 559                         // type being derived upon
 560                         self.additional_bounds.iter().map(|p| {
 561                             cx.typarambound(p.to_path(cx, self.span,
 562                                                         type_ident, generics))
 563                         }).collect();
 564
 565                     // require the current trait
 566                     bounds.push(cx.typarambound(trait_path.clone()));
 567
 568                     // also add in any bounds from the declaration
 569                     for declared_bound in ty_param.bounds.iter() {
 570                         bounds.push((*declared_bound).clone());
 571                     }
 572
 573                     GenericParam::Type(cx.typaram(self.span, ty_param.ident, vec![], bounds, None))
 574                 }
 575             }
 576         }));
 577
 578         // and similarly for where clauses
 579         where_clause.predicates.extend(generics.where_clause.predicates.iter().map(|clause| {
 580             match *clause {
 581                 ast::WherePredicate::BoundPredicate(ref wb) => {
 582                     ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate {
 583                         span: self.span,
 584                         bound_generic_params: wb.bound_generic_params.clone(),
 585                         bounded_ty: wb.bounded_ty.clone(),
 586                         bounds: wb.bounds.iter().cloned().collect(),
 587                     })
 588                 }
 589                 ast::WherePredicate::RegionPredicate(ref rb) => {
 590                     ast::WherePredicate::RegionPredicate(ast::WhereRegionPredicate {
 591                         span: self.span,
 592                         lifetime: rb.lifetime,
 593                         bounds: rb.bounds.iter().cloned().collect(),
 594                     })
 595                 }
 596                 ast::WherePredicate::EqPredicate(ref we) => {
 597                     ast::WherePredicate::EqPredicate(ast::WhereEqPredicate {
 598                         id: ast::DUMMY_NODE_ID,
 599                         span: self.span,
 600                         lhs_ty: we.lhs_ty.clone(),
 601                         rhs_ty: we.rhs_ty.clone(),
 602                     })
 603                 }
 604             }
 605         }));
 606
 607         {
 608             // Extra scope required here so ty_params goes out of scope before params is moved
 609
 610             let mut ty_params = params.iter()
 611                 .filter_map(|param| match *param {
 612                     ast::GenericParam::Type(ref t) => Some(t),
 613                     _ => None,
 614                 })
 615                 .peekable();
 616
 617             if ty_params.peek().is_some() {
 618                 let ty_param_names: Vec<ast::Name> = ty_params
 619                     .map(|ty_param| ty_param.ident.name)
 620                     .collect();
 621
 622                 let mut processed_field_types = HashSet::new();
 623                 for field_ty in field_tys {
 624                     let tys = find_type_parameters(&field_ty, &ty_param_names, self.span, cx);
 625
 626                     for ty in tys {
 627                         // if we have already handled this type, skip it
 628                         if let ast::TyKind::Path(_, ref p) = ty.node {
 629                             if p.segments.len() == 1 &&
 630                             ty_param_names.contains(&p.segments[0].ident.name) ||
 631                             processed_field_types.contains(&p.segments) {
 632                                 continue;
 633                             };
 634                             processed_field_types.insert(p.segments.clone());
 635                         }
 636                         let mut bounds: Vec<_> = self.additional_bounds
 637                             .iter()
 638                             .map(|p| {
 639                                 cx.typarambound(p.to_path(cx, self.span, type_ident, generics))
 640                             })
 641                             .collect();
 642
 643                         // require the current trait
 644                         bounds.push(cx.typarambound(trait_path.clone()));
 645
 646                         let predicate = ast::WhereBoundPredicate {
 647                             span: self.span,
 648                             bound_generic_params: Vec::new(),
 649                             bounded_ty: ty,
 650                             bounds,
 651                         };
 652
 653                         let predicate = ast::WherePredicate::BoundPredicate(predicate);
 654                         where_clause.predicates.push(predicate);
 655                     }
 656                 }
 657             }
 658         }
 659
 660         let trait_generics = Generics {
 661             params,
 662             where_clause,
 663             span,
 664         };
 665
 666         // Create the reference to the trait.
 667         let trait_ref = cx.trait_ref(trait_path);
 668
 669         // Create the type parameters on the `self` path.
 670         let self_ty_params = generics.params
 671             .iter()
 672             .filter_map(|param| match *param {
 673                 GenericParam::Type(ref ty_param)
 674                     => Some(cx.ty_ident(self.span, ty_param.ident)),
 675                 _ => None,
 676             })
 677             .collect();
 678
 679         let self_lifetimes: Vec<ast::Lifetime> = generics.params
 680             .iter()
 681             .filter_map(|param| match *param {
 682                 GenericParam::Lifetime(ref ld) => Some(ld.lifetime),
 683                 _ => None,
 684             })
 685             .collect();
 686
 687         // Create the type of `self`.
 688         let self_type = cx.ty_path(cx.path_all(self.span,
 689                                                false,
 690                                                vec![type_ident],
 691                                                self_lifetimes,
 692                                                self_ty_params,
 693                                                Vec::new()));
 694
 695         let attr = cx.attribute(self.span,
 696                                 cx.meta_word(self.span,
 697                                              Symbol::intern("automatically_derived")));
 698         // Just mark it now since we know that it'll end up used downstream
 699         attr::mark_used(&attr);
 700         let opt_trait_ref = Some(trait_ref);
 701         let unused_qual = {
 702             let word = cx.meta_list_item_word(self.span, Symbol::intern("unused_qualifications"));
 703             cx.attribute(self.span, cx.meta_list(self.span, Symbol::intern("allow"), vec![word]))
 704         };
 705
 706         let mut a = vec![attr, unused_qual];
 707         a.extend(self.attributes.iter().cloned());
 708
 709         let unsafety = if self.is_unsafe {
 710             ast::Unsafety::Unsafe
 711         } else {
 712             ast::Unsafety::Normal
 713         };
 714
 715         cx.item(self.span,
 716                 keywords::Invalid.ident(),
 717                 a,
 718                 ast::ItemKind::Impl(unsafety,
 719                                     ast::ImplPolarity::Positive,
 720                                     ast::Defaultness::Final,
 721                                     trait_generics,
 722                                     opt_trait_ref,
 723                                     self_type,
 724                                     methods.into_iter().chain(associated_types).collect()))
 725     }
 726
 727     fn expand_struct_def(&self,
 728                          cx: &mut ExtCtxt,
 729                          struct_def: &'a VariantData,
 730                          type_ident: Ident,
 731                          generics: &Generics,
 732                          from_scratch: bool,
 733                          use_temporaries: bool)
 734                          -> P<ast::Item> {
 735         let field_tys: Vec<P<ast::Ty>> = struct_def.fields()
 736             .iter()
 737             .map(|field| field.ty.clone())
 738             .collect();
 739
 740         let methods = self.methods
 741             .iter()
 742             .map(|method_def| {
 743                 let (explicit_self, self_args, nonself_args, tys) =
 744                     method_def.split_self_nonself_args(cx, self, type_ident, generics);
 745
 746                 let body = if from_scratch || method_def.is_static() {
 747                     method_def.expand_static_struct_method_body(cx,
 748                                                                 self,
 749                                                                 struct_def,
 750                                                                 type_ident,
 751                                                                 &self_args[..],
 752                                                                 &nonself_args[..])
 753                 } else {
 754                     method_def.expand_struct_method_body(cx,
 755                                                          self,
 756                                                          struct_def,
 757                                                          type_ident,
 758                                                          &self_args[..],
 759                                                          &nonself_args[..],
 760                                                          use_temporaries)
 761                 };
 762
 763                 method_def.create_method(cx,
 764                                          self,
 765                                          type_ident,
 766                                          generics,
 767                                          Abi::Rust,
 768                                          explicit_self,
 769                                          tys,
 770                                          body)
 771             })
 772             .collect();
 773
 774         self.create_derived_impl(cx, type_ident, generics, field_tys, methods)
 775     }
 776
 777     fn expand_enum_def(&self,
 778                        cx: &mut ExtCtxt,
 779                        enum_def: &'a EnumDef,
 780                        type_attrs: &[ast::Attribute],
 781                        type_ident: Ident,
 782                        generics: &Generics,
 783                        from_scratch: bool)
 784                        -> P<ast::Item> {
 785         let mut field_tys = Vec::new();
 786
 787         for variant in &enum_def.variants {
 788             field_tys.extend(variant.node
 789                 .data
 790                 .fields()
 791                 .iter()
 792                 .map(|field| field.ty.clone()));
 793         }
 794
 795         let methods = self.methods
 796             .iter()
 797             .map(|method_def| {
 798                 let (explicit_self, self_args, nonself_args, tys) =
 799                     method_def.split_self_nonself_args(cx, self, type_ident, generics);
 800
 801                 let body = if from_scratch || method_def.is_static() {
 802                     method_def.expand_static_enum_method_body(cx,
 803                                                               self,
 804                                                               enum_def,
 805                                                               type_ident,
 806                                                               &self_args[..],
 807                                                               &nonself_args[..])
 808                 } else {
 809                     method_def.expand_enum_method_body(cx,
 810                                                        self,
 811                                                        enum_def,
 812                                                        type_attrs,
 813                                                        type_ident,
 814                                                        self_args,
 815                                                        &nonself_args[..])
 816                 };
 817
 818                 method_def.create_method(cx,
 819                                          self,
 820                                          type_ident,
 821                                          generics,
 822                                          Abi::Rust,
 823                                          explicit_self,
 824                                          tys,
 825                                          body)
 826             })
 827             .collect();
 828
 829         self.create_derived_impl(cx, type_ident, generics, field_tys, methods)
 830     }
 831 }
 832
 833 fn find_repr_type_name(diagnostic: &Handler, type_attrs: &[ast::Attribute]) -> &'static str {
 834     let mut repr_type_name = "isize";
 835     for a in type_attrs {
 836         for r in &attr::find_repr_attrs(diagnostic, a) {
 837             repr_type_name = match *r {
 838                 attr::ReprPacked(_) | attr::ReprSimd | attr::ReprAlign(_) | attr::ReprTransparent =>
 839                     continue,
 840
 841                 attr::ReprC => "i32",
 842
 843                 attr::ReprInt(attr::SignedInt(ast::IntTy::Isize)) => "isize",
 844                 attr::ReprInt(attr::SignedInt(ast::IntTy::I8)) => "i8",
 845                 attr::ReprInt(attr::SignedInt(ast::IntTy::I16)) => "i16",
 846                 attr::ReprInt(attr::SignedInt(ast::IntTy::I32)) => "i32",
 847                 attr::ReprInt(attr::SignedInt(ast::IntTy::I64)) => "i64",
 848                 attr::ReprInt(attr::SignedInt(ast::IntTy::I128)) => "i128",
 849
 850                 attr::ReprInt(attr::UnsignedInt(ast::UintTy::Usize)) => "usize",
 851                 attr::ReprInt(attr::UnsignedInt(ast::UintTy::U8)) => "u8",
 852                 attr::ReprInt(attr::UnsignedInt(ast::UintTy::U16)) => "u16",
 853                 attr::ReprInt(attr::UnsignedInt(ast::UintTy::U32)) => "u32",
 854                 attr::ReprInt(attr::UnsignedInt(ast::UintTy::U64)) => "u64",
 855                 attr::ReprInt(attr::UnsignedInt(ast::UintTy::U128)) => "u128",
 856             }
 857         }
 858     }
 859     repr_type_name
 860 }
 861
 862 impl<'a> MethodDef<'a> {
 863     fn call_substructure_method(&self,
 864                                 cx: &mut ExtCtxt,
 865                                 trait_: &TraitDef,
 866                                 type_ident: Ident,
 867                                 self_args: &[P<Expr>],
 868                                 nonself_args: &[P<Expr>],
 869                                 fields: &SubstructureFields)
 870                                 -> P<Expr> {
 871         let substructure = Substructure {
 872             type_ident,
 873             method_ident: cx.ident_of(self.name),
 874             self_args,
 875             nonself_args,
 876             fields,
 877         };
 878         let mut f = self.combine_substructure.borrow_mut();
 879         let f: &mut CombineSubstructureFunc = &mut *f;
 880         f(cx, trait_.span, &substructure)
 881     }
 882
 883     fn get_ret_ty(&self,
 884                   cx: &mut ExtCtxt,
 885                   trait_: &TraitDef,
 886                   generics: &Generics,
 887                   type_ident: Ident)
 888                   -> P<ast::Ty> {
 889         self.ret_ty.to_ty(cx, trait_.span, type_ident, generics)
 890     }
 891
 892     fn is_static(&self) -> bool {
 893         self.explicit_self.is_none()
 894     }
 895
 896     fn split_self_nonself_args
 897         (&self,
 898          cx: &mut ExtCtxt,
 899          trait_: &TraitDef,
 900          type_ident: Ident,
 901          generics: &Generics)
 902          -> (Option<ast::ExplicitSelf>, Vec<P<Expr>>, Vec<P<Expr>>, Vec<(Ident, P<ast::Ty>)>) {
 903
 904         let mut self_args = Vec::new();
 905         let mut nonself_args = Vec::new();
 906         let mut arg_tys = Vec::new();
 907         let mut nonstatic = false;
 908
 909         let ast_explicit_self = self.explicit_self.as_ref().map(|self_ptr| {
 910             let (self_expr, explicit_self) = ty::get_explicit_self(cx, trait_.span, self_ptr);
 911
 912             self_args.push(self_expr);
 913             nonstatic = true;
 914
 915             explicit_self
 916         });
 917
 918         for (ty, name) in self.args.iter() {
 919             let ast_ty = ty.to_ty(cx, trait_.span, type_ident, generics);
 920             let ident = cx.ident_of(name).gensym();
 921             arg_tys.push((ident, ast_ty));
 922
 923             let arg_expr = cx.expr_ident(trait_.span, ident);
 924
 925             match *ty {
 926                 // for static methods, just treat any Self
 927                 // arguments as a normal arg
 928                 Self_ if nonstatic => {
 929                     self_args.push(arg_expr);
 930                 }
 931                 Ptr(ref ty, _) if **ty == Self_ && nonstatic => {
 932                     self_args.push(cx.expr_deref(trait_.span, arg_expr))
 933                 }
 934                 _ => {
 935                     nonself_args.push(arg_expr);
 936                 }
 937             }
 938         }
 939
 940         (ast_explicit_self, self_args, nonself_args, arg_tys)
 941     }
 942
 943     fn create_method(&self,
 944                      cx: &mut ExtCtxt,
 945                      trait_: &TraitDef,
 946                      type_ident: Ident,
 947                      generics: &Generics,
 948                      abi: Abi,
 949                      explicit_self: Option<ast::ExplicitSelf>,
 950                      arg_types: Vec<(Ident, P<ast::Ty>)>,
 951                      body: P<Expr>)
 952                      -> ast::ImplItem {
 953
 954         // create the generics that aren't for Self
 955         let fn_generics = self.generics.to_generics(cx, trait_.span, type_ident, generics);
 956
 957         let args = {
 958             let self_args = explicit_self.map(|explicit_self| {
 959                 ast::Arg::from_self(explicit_self,
 960                                     keywords::SelfValue.ident().with_span_pos(trait_.span))
 961             });
 962             let nonself_args = arg_types.into_iter()
 963                 .map(|(name, ty)| cx.arg(trait_.span, name, ty));
 964             self_args.into_iter().chain(nonself_args).collect()
 965         };
 966
 967         let ret_type = self.get_ret_ty(cx, trait_, generics, type_ident);
 968
 969         let method_ident = cx.ident_of(self.name);
 970         let fn_decl = cx.fn_decl(args, ast::FunctionRetTy::Ty(ret_type));
 971         let body_block = cx.block_expr(body);
 972
 973         let unsafety = if self.is_unsafe {
 974             ast::Unsafety::Unsafe
 975         } else {
 976             ast::Unsafety::Normal
 977         };
 978
 979         // Create the method.
 980         ast::ImplItem {
 981             id: ast::DUMMY_NODE_ID,
 982             attrs: self.attributes.clone(),
 983             generics: fn_generics,
 984             span: trait_.span,
 985             vis: respan(trait_.span.shrink_to_lo(), ast::VisibilityKind::Inherited),
 986             defaultness: ast::Defaultness::Final,
 987             ident: method_ident,
 988             node: ast::ImplItemKind::Method(ast::MethodSig {
 989                                                 abi,
 990                                                 unsafety,
 991                                                 constness:
 992                                                     dummy_spanned(ast::Constness::NotConst),
 993                                                 decl: fn_decl,
 994                                             },
 995                                             body_block),
 996             tokens: None,
 997         }
 998     }
 999
1000     /// ```
1001     /// #[derive(PartialEq)]
1002     /// # struct Dummy;
1003     /// struct A { x: i32, y: i32 }
1004     ///
1005     /// // equivalent to:
1006     /// impl PartialEq for A {
1007     ///     fn eq(&self, other: &A) -> bool {
1008     ///         match *self {
1009     ///             A {x: ref __self_0_0, y: ref __self_0_1} => {
1010     ///                 match *other {
1011     ///                     A {x: ref __self_1_0, y: ref __self_1_1} => {
1012     ///                         __self_0_0.eq(__self_1_0) && __self_0_1.eq(__self_1_1)
1013     ///                     }
1014     ///                 }
1015     ///             }
1016     ///         }
1017     ///     }
1018     /// }
1019     ///
1020     /// // or if A is repr(packed) - note fields are matched by-value
1021     /// // instead of by-reference.
1022     /// impl PartialEq for A {
1023     ///     fn eq(&self, other: &A) -> bool {
1024     ///         match *self {
1025     ///             A {x: __self_0_0, y: __self_0_1} => {
1026     ///                 match other {
1027     ///                     A {x: __self_1_0, y: __self_1_1} => {
1028     ///                         __self_0_0.eq(&__self_1_0) && __self_0_1.eq(&__self_1_1)
1029     ///                     }
1030     ///                 }
1031     ///             }
1032     ///         }
1033     ///     }
1034     /// }
1035     /// ```
1036     fn expand_struct_method_body<'b>(&self,
1037                                      cx: &mut ExtCtxt,
1038                                      trait_: &TraitDef<'b>,
1039                                      struct_def: &'b VariantData,
1040                                      type_ident: Ident,
1041                                      self_args: &[P<Expr>],
1042                                      nonself_args: &[P<Expr>],
1043                                      use_temporaries: bool)
1044                                      -> P<Expr> {
1045
1046         let mut raw_fields = Vec::new(); // Vec<[fields of self],
1047                                  // [fields of next Self arg], [etc]>
1048         let mut patterns = Vec::new();
1049         for i in 0..self_args.len() {
1050             let struct_path = cx.path(DUMMY_SP, vec![type_ident]);
1051             let (pat, ident_expr) = trait_.create_struct_pattern(cx,
1052                                                                  struct_path,
1053                                                                  struct_def,
1054                                                                  &format!("__self_{}", i),
1055                                                                  ast::Mutability::Immutable,
1056                                                                  use_temporaries);
1057             patterns.push(pat);
1058             raw_fields.push(ident_expr);
1059         }
1060
1061         // transpose raw_fields
1062         let fields = if !raw_fields.is_empty() {
1063             let mut raw_fields = raw_fields.into_iter().map(|v| v.into_iter());
1064             let first_field = raw_fields.next().unwrap();
1065             let mut other_fields: Vec<vec::IntoIter<_>> = raw_fields.collect();
1066             first_field.map(|(span, opt_id, field, attrs)| {
1067                     FieldInfo {
1068                         span,
1069                         name: opt_id,
1070                         self_: field,
1071                         other: other_fields.iter_mut()
1072                             .map(|l| {
1073                                 match l.next().unwrap() {
1074                                     (.., ex, _) => ex,
1075                                 }
1076                             })
1077                             .collect(),
1078                         attrs,
1079                     }
1080                 })
1081                 .collect()
1082         } else {
1083             cx.span_bug(trait_.span,
1084                         "no self arguments to non-static method in generic \
1085                          `derive`")
1086         };
1087
1088         // body of the inner most destructuring match
1089         let mut body = self.call_substructure_method(cx,
1090                                                      trait_,
1091                                                      type_ident,
1092                                                      self_args,
1093                                                      nonself_args,
1094                                                      &Struct(struct_def, fields));
1095
1096         // make a series of nested matches, to destructure the
1097         // structs. This is actually right-to-left, but it shouldn't
1098         // matter.
1099         for (arg_expr, pat) in self_args.iter().zip(patterns) {
1100             body = cx.expr_match(trait_.span,
1101                                  arg_expr.clone(),
1102                                  vec![cx.arm(trait_.span, vec![pat.clone()], body)])
1103         }
1104
1105         body
1106     }
1107
1108     fn expand_static_struct_method_body(&self,
1109                                         cx: &mut ExtCtxt,
1110                                         trait_: &TraitDef,
1111                                         struct_def: &VariantData,
1112                                         type_ident: Ident,
1113                                         self_args: &[P<Expr>],
1114                                         nonself_args: &[P<Expr>])
1115                                         -> P<Expr> {
1116         let summary = trait_.summarise_struct(cx, struct_def);
1117
1118         self.call_substructure_method(cx,
1119                                       trait_,
1120                                       type_ident,
1121                                       self_args,
1122                                       nonself_args,
1123                                       &StaticStruct(struct_def, summary))
1124     }
1125
1126     /// ```
1127     /// #[derive(PartialEq)]
1128     /// # struct Dummy;
1129     /// enum A {
1130     ///     A1,
1131     ///     A2(i32)
1132     /// }
1133     ///
1134     /// // is equivalent to
1135     ///
1136     /// impl PartialEq for A {
1137     ///     fn eq(&self, other: &A) -> ::bool {
1138     ///         match (&*self, &*other) {
1139     ///             (&A1, &A1) => true,
1140     ///             (&A2(ref self_0),
1141     ///              &A2(ref __arg_1_0)) => (*self_0).eq(&(*__arg_1_0)),
1142     ///             _ => {
1143     ///                 let __self_vi = match *self { A1(..) => 0, A2(..) => 1 };
1144     ///                 let __arg_1_vi = match *other { A1(..) => 0, A2(..) => 1 };
1145     ///                 false
1146     ///             }
1147     ///         }
1148     ///     }
1149     /// }
1150     /// ```
1151     ///
1152     /// (Of course `__self_vi` and `__arg_1_vi` are unused for
1153     /// `PartialEq`, and those subcomputations will hopefully be removed
1154     /// as their results are unused.  The point of `__self_vi` and
1155     /// `__arg_1_vi` is for `PartialOrd`; see #15503.)
1156     fn expand_enum_method_body<'b>(&self,
1157                                    cx: &mut ExtCtxt,
1158                                    trait_: &TraitDef<'b>,
1159                                    enum_def: &'b EnumDef,
1160                                    type_attrs: &[ast::Attribute],
1161                                    type_ident: Ident,
1162                                    self_args: Vec<P<Expr>>,
1163                                    nonself_args: &[P<Expr>])
1164                                    -> P<Expr> {
1165         self.build_enum_match_tuple(cx,
1166                                     trait_,
1167                                     enum_def,
1168                                     type_attrs,
1169                                     type_ident,
1170                                     self_args,
1171                                     nonself_args)
1172     }
1173
1174
1175     /// Creates a match for a tuple of all `self_args`, where either all
1176     /// variants match, or it falls into a catch-all for when one variant
1177     /// does not match.
1178
1179     /// There are N + 1 cases because is a case for each of the N
1180     /// variants where all of the variants match, and one catch-all for
1181     /// when one does not match.
1182
1183     /// As an optimization we generate code which checks whether all variants
1184     /// match first which makes llvm see that C-like enums can be compiled into
1185     /// a simple equality check (for PartialEq).
1186
1187     /// The catch-all handler is provided access the variant index values
1188     /// for each of the self-args, carried in precomputed variables.
1189
1190     /// ```{.text}
1191     /// let __self0_vi = unsafe {
1192     ///     std::intrinsics::discriminant_value(&self) } as i32;
1193     /// let __self1_vi = unsafe {
1194     ///     std::intrinsics::discriminant_value(&arg1) } as i32;
1195     /// let __self2_vi = unsafe {
1196     ///     std::intrinsics::discriminant_value(&arg2) } as i32;
1197     ///
1198     /// if __self0_vi == __self1_vi && __self0_vi == __self2_vi && ... {
1199     ///     match (...) {
1200     ///         (Variant1, Variant1, ...) => Body1
1201     ///         (Variant2, Variant2, ...) => Body2,
1202     ///         ...
1203     ///         _ => ::core::intrinsics::unreachable()
1204     ///     }
1205     /// }
1206     /// else {
1207     ///     ... // catch-all remainder can inspect above variant index values.
1208     /// }
1209     /// ```
1210     fn build_enum_match_tuple<'b>(&self,
1211                                   cx: &mut ExtCtxt,
1212                                   trait_: &TraitDef<'b>,
1213                                   enum_def: &'b EnumDef,
1214                                   type_attrs: &[ast::Attribute],
1215                                   type_ident: Ident,
1216                                   self_args: Vec<P<Expr>>,
1217                                   nonself_args: &[P<Expr>])
1218                                   -> P<Expr> {
1219         let sp = trait_.span;
1220         let variants = &enum_def.variants;
1221
1222         let self_arg_names = self_args.iter()
1223             .enumerate()
1224             .map(|(arg_count, _self_arg)| {
1225                 if arg_count == 0 {
1226                     "__self".to_string()
1227                 } else {
1228                     format!("__arg_{}", arg_count)
1229                 }
1230             })
1231             .collect::<Vec<String>>();
1232
1233         let self_arg_idents = self_arg_names.iter()
1234             .map(|name| cx.ident_of(&name[..]))
1235             .collect::<Vec<ast::Ident>>();
1236
1237         // The `vi_idents` will be bound, solely in the catch-all, to
1238         // a series of let statements mapping each self_arg to an int
1239         // value corresponding to its discriminant.
1240         let vi_idents: Vec<ast::Ident> = self_arg_names.iter()
1241             .map(|name| {
1242                 let vi_suffix = format!("{}_vi", &name[..]);
1243                 cx.ident_of(&vi_suffix[..]).gensym()
1244             })
1245             .collect::<Vec<ast::Ident>>();
1246
1247         // Builds, via callback to call_substructure_method, the
1248         // delegated expression that handles the catch-all case,
1249         // using `__variants_tuple` to drive logic if necessary.
1250         let catch_all_substructure =
1251             EnumNonMatchingCollapsed(self_arg_idents, &variants[..], &vi_idents[..]);
1252
1253         let first_fieldless = variants.iter().find(|v| v.node.data.fields().is_empty());
1254
1255         // These arms are of the form:
1256         // (Variant1, Variant1, ...) => Body1
1257         // (Variant2, Variant2, ...) => Body2
1258         // ...
1259         // where each tuple has length = self_args.len()
1260         let mut match_arms: Vec<ast::Arm> = variants.iter()
1261             .enumerate()
1262             .filter(|&(_, v)| !(self.unify_fieldless_variants && v.node.data.fields().is_empty()))
1263             .map(|(index, variant)| {
1264                 let mk_self_pat = |cx: &mut ExtCtxt, self_arg_name: &str| {
1265                     let (p, idents) = trait_.create_enum_variant_pattern(cx,
1266                                                      type_ident,
1267                                                      variant,
1268                                                      self_arg_name,
1269                                                      ast::Mutability::Immutable);
1270                     (cx.pat(sp, PatKind::Ref(p, ast::Mutability::Immutable)), idents)
1271                 };
1272
1273                 // A single arm has form (&VariantK, &VariantK, ...) => BodyK
1274                 // (see "Final wrinkle" note below for why.)
1275                 let mut subpats = Vec::with_capacity(self_arg_names.len());
1276                 let mut self_pats_idents = Vec::with_capacity(self_arg_names.len() - 1);
1277                 let first_self_pat_idents = {
1278                     let (p, idents) = mk_self_pat(cx, &self_arg_names[0]);
1279                     subpats.push(p);
1280                     idents
1281                 };
1282                 for self_arg_name in &self_arg_names[1..] {
1283                     let (p, idents) = mk_self_pat(cx, &self_arg_name[..]);
1284                     subpats.push(p);
1285                     self_pats_idents.push(idents);
1286                 }
1287
1288                 // Here is the pat = `(&VariantK, &VariantK, ...)`
1289                 let single_pat = cx.pat_tuple(sp, subpats);
1290
1291                 // For the BodyK, we need to delegate to our caller,
1292                 // passing it an EnumMatching to indicate which case
1293                 // we are in.
1294
1295                 // All of the Self args have the same variant in these
1296                 // cases.  So we transpose the info in self_pats_idents
1297                 // to gather the getter expressions together, in the
1298                 // form that EnumMatching expects.
1299
1300                 // The transposition is driven by walking across the
1301                 // arg fields of the variant for the first self pat.
1302                 let field_tuples = first_self_pat_idents.into_iter().enumerate()
1303                     // For each arg field of self, pull out its getter expr ...
1304                     .map(|(field_index, (sp, opt_ident, self_getter_expr, attrs))| {
1305                         // ... but FieldInfo also wants getter expr
1306                         // for matching other arguments of Self type;
1307                         // so walk across the *other* self_pats_idents
1308                         // and pull out getter for same field in each
1309                         // of them (using `field_index` tracked above).
1310                         // That is the heart of the transposition.
1311                         let others = self_pats_idents.iter().map(|fields| {
1312                             let (_, _opt_ident, ref other_getter_expr, _) =
1313                                 fields[field_index];
1314
1315                             // All Self args have same variant, so
1316                             // opt_idents are the same.  (Assert
1317                             // here to make it self-evident that
1318                             // it is okay to ignore `_opt_ident`.)
1319                             assert!(opt_ident == _opt_ident);
1320
1321                             other_getter_expr.clone()
1322                         }).collect::<Vec<P<Expr>>>();
1323
1324                         FieldInfo { span: sp,
1325                                     name: opt_ident,
1326                                     self_: self_getter_expr,
1327                                     other: others,
1328                                     attrs,
1329                         }
1330                     }).collect::<Vec<FieldInfo>>();
1331
1332                 // Now, for some given VariantK, we have built up
1333                 // expressions for referencing every field of every
1334                 // Self arg, assuming all are instances of VariantK.
1335                 // Build up code associated with such a case.
1336                 let substructure = EnumMatching(index, variants.len(), variant, field_tuples);
1337                 let arm_expr = self.call_substructure_method(cx,
1338                                                              trait_,
1339                                                              type_ident,
1340                                                              &self_args[..],
1341                                                              nonself_args,
1342                                                              &substructure);
1343
1344                 cx.arm(sp, vec![single_pat], arm_expr)
1345             })
1346             .collect();
1347
1348         let default = match first_fieldless {
1349             Some(v) if self.unify_fieldless_variants => {
1350                 // We need a default case that handles the fieldless variants.
1351                 // The index and actual variant aren't meaningful in this case,
1352                 // so just use whatever
1353                 let substructure = EnumMatching(0, variants.len(), v, Vec::new());
1354                 Some(self.call_substructure_method(cx,
1355                                                    trait_,
1356                                                    type_ident,
1357                                                    &self_args[..],
1358                                                    nonself_args,
1359                                                    &substructure))
1360             }
1361             _ if variants.len() > 1 && self_args.len() > 1 => {
1362                 // Since we know that all the arguments will match if we reach
1363                 // the match expression we add the unreachable intrinsics as the
1364                 // result of the catch all which should help llvm in optimizing it
1365                 Some(deriving::call_intrinsic(cx, sp, "unreachable", vec![]))
1366             }
1367             _ => None,
1368         };
1369         if let Some(arm) = default {
1370             match_arms.push(cx.arm(sp, vec![cx.pat_wild(sp)], arm));
1371         }
1372
1373         // We will usually need the catch-all after matching the
1374         // tuples `(VariantK, VariantK, ...)` for each VariantK of the
1375         // enum.  But:
1376         //
1377         // * when there is only one Self arg, the arms above suffice
1378         // (and the deriving we call back into may not be prepared to
1379         // handle EnumNonMatchCollapsed), and,
1380         //
1381         // * when the enum has only one variant, the single arm that
1382         // is already present always suffices.
1383         //
1384         // * In either of the two cases above, if we *did* add a
1385         //   catch-all `_` match, it would trigger the
1386         //   unreachable-pattern error.
1387         //
1388         if variants.len() > 1 && self_args.len() > 1 {
1389             // Build a series of let statements mapping each self_arg
1390             // to its discriminant value. If this is a C-style enum
1391             // with a specific repr type, then casts the values to
1392             // that type.  Otherwise casts to `i32` (the default repr
1393             // type).
1394             //
1395             // i.e. for `enum E<T> { A, B(1), C(T, T) }`, and a deriving
1396             // with three Self args, builds three statements:
1397             //
1398             // ```
1399             // let __self0_vi = unsafe {
1400             //     std::intrinsics::discriminant_value(&self) } as i32;
1401             // let __self1_vi = unsafe {
1402             //     std::intrinsics::discriminant_value(&arg1) } as i32;
1403             // let __self2_vi = unsafe {
1404             //     std::intrinsics::discriminant_value(&arg2) } as i32;
1405             // ```
1406             let mut index_let_stmts: Vec<ast::Stmt> = Vec::new();
1407
1408             // We also build an expression which checks whether all discriminants are equal
1409             // discriminant_test = __self0_vi == __self1_vi && __self0_vi == __self2_vi && ...
1410             let mut discriminant_test = cx.expr_bool(sp, true);
1411
1412             let target_type_name = find_repr_type_name(&cx.parse_sess.span_diagnostic, type_attrs);
1413
1414             let mut first_ident = None;
1415             for (&ident, self_arg) in vi_idents.iter().zip(&self_args) {
1416                 let self_addr = cx.expr_addr_of(sp, self_arg.clone());
1417                 let variant_value =
1418                     deriving::call_intrinsic(cx, sp, "discriminant_value", vec![self_addr]);
1419
1420                 let target_ty = cx.ty_ident(sp, cx.ident_of(target_type_name));
1421                 let variant_disr = cx.expr_cast(sp, variant_value, target_ty);
1422                 let let_stmt = cx.stmt_let(sp, false, ident, variant_disr);
1423                 index_let_stmts.push(let_stmt);
1424
1425                 match first_ident {
1426                     Some(first) => {
1427                         let first_expr = cx.expr_ident(sp, first);
1428                         let id = cx.expr_ident(sp, ident);
1429                         let test = cx.expr_binary(sp, BinOpKind::Eq, first_expr, id);
1430                         discriminant_test =
1431                             cx.expr_binary(sp, BinOpKind::And, discriminant_test, test)
1432                     }
1433                     None => {
1434                         first_ident = Some(ident);
1435                     }
1436                 }
1437             }
1438
1439             let arm_expr = self.call_substructure_method(cx,
1440                                                          trait_,
1441                                                          type_ident,
1442                                                          &self_args[..],
1443                                                          nonself_args,
1444                                                          &catch_all_substructure);
1445
1446             // Final wrinkle: the self_args are expressions that deref
1447             // down to desired places, but we cannot actually deref
1448             // them when they are fed as r-values into a tuple
1449             // expression; here add a layer of borrowing, turning
1450             // `(*self, *__arg_0, ...)` into `(&*self, &*__arg_0, ...)`.
1451             let borrowed_self_args = self_args.move_map(|self_arg| cx.expr_addr_of(sp, self_arg));
1452             let match_arg = cx.expr(sp, ast::ExprKind::Tup(borrowed_self_args));
1453
1454             // Lastly we create an expression which branches on all discriminants being equal
1455             //  if discriminant_test {
1456             //      match (...) {
1457             //          (Variant1, Variant1, ...) => Body1
1458             //          (Variant2, Variant2, ...) => Body2,
1459             //          ...
1460             //          _ => ::core::intrinsics::unreachable()
1461             //      }
1462             //  }
1463             //  else {
1464             //      <delegated expression referring to __self0_vi, et al.>
1465             //  }
1466             let all_match = cx.expr_match(sp, match_arg, match_arms);
1467             let arm_expr = cx.expr_if(sp, discriminant_test, all_match, Some(arm_expr));
1468             index_let_stmts.push(cx.stmt_expr(arm_expr));
1469             cx.expr_block(cx.block(sp, index_let_stmts))
1470         } else if variants.is_empty() {
1471             // As an additional wrinkle, For a zero-variant enum A,
1472             // currently the compiler
1473             // will accept `fn (a: &Self) { match   *a   { } }`
1474             // but rejects `fn (a: &Self) { match (&*a,) { } }`
1475             // as well as  `fn (a: &Self) { match ( *a,) { } }`
1476             //
1477             // This means that the strategy of building up a tuple of
1478             // all Self arguments fails when Self is a zero variant
1479             // enum: rustc rejects the expanded program, even though
1480             // the actual code tends to be impossible to execute (at
1481             // least safely), according to the type system.
1482             //
1483             // The most expedient fix for this is to just let the
1484             // code fall through to the catch-all.  But even this is
1485             // error-prone, since the catch-all as defined above would
1486             // generate code like this:
1487             //
1488             //     _ => { let __self0 = match *self { };
1489             //            let __self1 = match *__arg_0 { };
1490             //            <catch-all-expr> }
1491             //
1492             // Which is yields bindings for variables which type
1493             // inference cannot resolve to unique types.
1494             //
1495             // One option to the above might be to add explicit type
1496             // annotations.  But the *only* reason to go down that path
1497             // would be to try to make the expanded output consistent
1498             // with the case when the number of enum variants >= 1.
1499             //
1500             // That just isn't worth it.  In fact, trying to generate
1501             // sensible code for *any* deriving on a zero-variant enum
1502             // does not make sense.  But at the same time, for now, we
1503             // do not want to cause a compile failure just because the
1504             // user happened to attach a deriving to their
1505             // zero-variant enum.
1506             //
1507             // Instead, just generate a failing expression for the
1508             // zero variant case, skipping matches and also skipping
1509             // delegating back to the end user code entirely.
1510             //
1511             // (See also #4499 and #12609; note that some of the
1512             // discussions there influence what choice we make here;
1513             // e.g. if we feature-gate `match x { ... }` when x refers
1514             // to an uninhabited type (e.g. a zero-variant enum or a
1515             // type holding such an enum), but do not feature-gate
1516             // zero-variant enums themselves, then attempting to
1517             // derive Debug on such a type could here generate code
1518             // that needs the feature gate enabled.)
1519
1520             deriving::call_intrinsic(cx, sp, "unreachable", vec![])
1521         } else {
1522
1523             // Final wrinkle: the self_args are expressions that deref
1524             // down to desired places, but we cannot actually deref
1525             // them when they are fed as r-values into a tuple
1526             // expression; here add a layer of borrowing, turning
1527             // `(*self, *__arg_0, ...)` into `(&*self, &*__arg_0, ...)`.
1528             let borrowed_self_args = self_args.move_map(|self_arg| cx.expr_addr_of(sp, self_arg));
1529             let match_arg = cx.expr(sp, ast::ExprKind::Tup(borrowed_self_args));
1530             cx.expr_match(sp, match_arg, match_arms)
1531         }
1532     }
1533
1534     fn expand_static_enum_method_body(&self,
1535                                       cx: &mut ExtCtxt,
1536                                       trait_: &TraitDef,
1537                                       enum_def: &EnumDef,
1538                                       type_ident: Ident,
1539                                       self_args: &[P<Expr>],
1540                                       nonself_args: &[P<Expr>])
1541                                       -> P<Expr> {
1542         let summary = enum_def.variants
1543             .iter()
1544             .map(|v| {
1545                 let sp = v.span.with_ctxt(trait_.span.ctxt());
1546                 let summary = trait_.summarise_struct(cx, &v.node.data);
1547                 (v.node.ident, sp, summary)
1548             })
1549             .collect();
1550         self.call_substructure_method(cx,
1551                                       trait_,
1552                                       type_ident,
1553                                       self_args,
1554                                       nonself_args,
1555                                       &StaticEnum(enum_def, summary))
1556     }
1557 }
1558
1559 // general helper methods.
1560 impl<'a> TraitDef<'a> {
1561     fn summarise_struct(&self, cx: &mut ExtCtxt, struct_def: &VariantData) -> StaticFields {
1562         let mut named_idents = Vec::new();
1563         let mut just_spans = Vec::new();
1564         for field in struct_def.fields() {
1565             let sp = field.span.with_ctxt(self.span.ctxt());
1566             match field.ident {
1567                 Some(ident) => named_idents.push((ident, sp)),
1568                 _ => just_spans.push(sp),
1569             }
1570         }
1571
1572         match (just_spans.is_empty(), named_idents.is_empty()) {
1573             (false, false) => {
1574                 cx.span_bug(self.span,
1575                             "a struct with named and unnamed \
1576                                           fields in generic `derive`")
1577             }
1578             // named fields
1579             (_, false) => Named(named_idents),
1580             // empty structs
1581             _ if struct_def.is_struct() => Named(named_idents),
1582             _ => Unnamed(just_spans, struct_def.is_tuple()),
1583         }
1584     }
1585
1586     fn create_subpatterns(&self,
1587                           cx: &mut ExtCtxt,
1588                           field_paths: Vec<ast::Ident>,
1589                           mutbl: ast::Mutability,
1590                           use_temporaries: bool)
1591                           -> Vec<P<ast::Pat>> {
1592         field_paths.iter()
1593             .map(|path| {
1594                 let binding_mode = if use_temporaries {
1595                     ast::BindingMode::ByValue(ast::Mutability::Immutable)
1596                 } else {
1597                     ast::BindingMode::ByRef(mutbl)
1598                 };
1599                 cx.pat(path.span,
1600                        PatKind::Ident(binding_mode, (*path).clone(), None))
1601             })
1602             .collect()
1603     }
1604
1605     fn create_struct_pattern
1606         (&self,
1607          cx: &mut ExtCtxt,
1608          struct_path: ast::Path,
1609          struct_def: &'a VariantData,
1610          prefix: &str,
1611          mutbl: ast::Mutability,
1612          use_temporaries: bool)
1613          -> (P<ast::Pat>, Vec<(Span, Option<Ident>, P<Expr>, &'a [ast::Attribute])>)
1614     {
1615         let mut paths = Vec::new();
1616         let mut ident_exprs = Vec::new();
1617         for (i, struct_field) in struct_def.fields().iter().enumerate() {
1618             let sp = struct_field.span.with_ctxt(self.span.ctxt());
1619             let ident = cx.ident_of(&format!("{}_{}", prefix, i)).gensym();
1620             paths.push(ident.with_span_pos(sp));
1621             let val = cx.expr_path(cx.path_ident(sp, ident));
1622             let val = if use_temporaries {
1623                 val
1624             } else {
1625                 cx.expr_deref(sp, val)
1626             };
1627             let val = cx.expr(sp, ast::ExprKind::Paren(val));
1628
1629             ident_exprs.push((sp, struct_field.ident, val, &struct_field.attrs[..]));
1630         }
1631
1632         let subpats = self.create_subpatterns(cx, paths, mutbl, use_temporaries);
1633         let pattern = match *struct_def {
1634             VariantData::Struct(..) => {
1635                 let field_pats = subpats.into_iter()
1636                     .zip(&ident_exprs)
1637                     .map(|(pat, &(sp, ident, ..))| {
1638                         if ident.is_none() {
1639                             cx.span_bug(sp, "a braced struct with unnamed fields in `derive`");
1640                         }
1641                         codemap::Spanned {
1642                             span: pat.span.with_ctxt(self.span.ctxt()),
1643                             node: ast::FieldPat {
1644                                 ident: ident.unwrap(),
1645                                 pat,
1646                                 is_shorthand: false,
1647                                 attrs: ast::ThinVec::new(),
1648                             },
1649                         }
1650                     })
1651                     .collect();
1652                 cx.pat_struct(self.span, struct_path, field_pats)
1653             }
1654             VariantData::Tuple(..) => {
1655                 cx.pat_tuple_struct(self.span, struct_path, subpats)
1656             }
1657             VariantData::Unit(..) => {
1658                 cx.pat_path(self.span, struct_path)
1659             }
1660         };
1661
1662         (pattern, ident_exprs)
1663     }
1664
1665     fn create_enum_variant_pattern
1666         (&self,
1667          cx: &mut ExtCtxt,
1668          enum_ident: ast::Ident,
1669          variant: &'a ast::Variant,
1670          prefix: &str,
1671          mutbl: ast::Mutability)
1672          -> (P<ast::Pat>, Vec<(Span, Option<Ident>, P<Expr>, &'a [ast::Attribute])>) {
1673         let sp = variant.span.with_ctxt(self.span.ctxt());
1674         let variant_path = cx.path(sp, vec![enum_ident, variant.node.ident]);
1675         let use_temporaries = false; // enums can't be repr(packed)
1676         self.create_struct_pattern(cx, variant_path, &variant.node.data, prefix, mutbl,
1677                                    use_temporaries)
1678     }
1679 }
1680
1681 // helpful premade recipes
1682
1683 pub fn cs_fold_fields<'a, F>(use_foldl: bool,
1684                              mut f: F,
1685                              base: P<Expr>,
1686                              cx: &mut ExtCtxt,
1687                              all_fields: &[FieldInfo<'a>])
1688                              -> P<Expr>
1689     where F: FnMut(&mut ExtCtxt, Span, P<Expr>, P<Expr>, &[P<Expr>]) -> P<Expr>
1690 {
1691     if use_foldl {
1692         all_fields.iter().fold(base, |old, field| {
1693             f(cx, field.span, old, field.self_.clone(), &field.other)
1694         })
1695     } else {
1696         all_fields.iter().rev().fold(base, |old, field| {
1697             f(cx, field.span, old, field.self_.clone(), &field.other)
1698         })
1699     }
1700 }
1701
1702 pub fn cs_fold_enumnonmatch(mut enum_nonmatch_f: EnumNonMatchCollapsedFunc,
1703                             cx: &mut ExtCtxt,
1704                             trait_span: Span,
1705                             substructure: &Substructure)
1706                             -> P<Expr>
1707 {
1708     match *substructure.fields {
1709         EnumNonMatchingCollapsed(ref all_args, _, tuple) => {
1710             enum_nonmatch_f(cx,
1711                             trait_span,
1712                             (&all_args[..], tuple),
1713                             substructure.nonself_args)
1714         }
1715         _ => cx.span_bug(trait_span, "cs_fold_enumnonmatch expected an EnumNonMatchingCollapsed")
1716     }
1717 }
1718
1719 pub fn cs_fold_static(cx: &mut ExtCtxt,
1720                       trait_span: Span)
1721                       -> P<Expr>
1722 {
1723     cx.span_bug(trait_span, "static function in `derive`")
1724 }
1725
1726 /// Fold the fields. `use_foldl` controls whether this is done
1727 /// left-to-right (`true`) or right-to-left (`false`).
1728 pub fn cs_fold<F>(use_foldl: bool,
1729                   f: F,
1730                   base: P<Expr>,
1731                   enum_nonmatch_f: EnumNonMatchCollapsedFunc,
1732                   cx: &mut ExtCtxt,
1733                   trait_span: Span,
1734                   substructure: &Substructure)
1735                   -> P<Expr>
1736     where F: FnMut(&mut ExtCtxt, Span, P<Expr>, P<Expr>, &[P<Expr>]) -> P<Expr>
1737 {
1738     match *substructure.fields {
1739         EnumMatching(.., ref all_fields) |
1740         Struct(_, ref all_fields) => {
1741             cs_fold_fields(use_foldl, f, base, cx, all_fields)
1742         }
1743         EnumNonMatchingCollapsed(..) => {
1744             cs_fold_enumnonmatch(enum_nonmatch_f, cx, trait_span, substructure)
1745         }
1746         StaticEnum(..) | StaticStruct(..) => {
1747             cs_fold_static(cx, trait_span)
1748         }
1749     }
1750 }
1751
1752 /// Function to fold over fields, with three cases, to generate more efficient and concise code.
1753 /// When the `substructure` has grouped fields, there are two cases:
1754 /// Zero fields: call the base case function with None (like the usual base case of `cs_fold`).
1755 /// One or more fields: call the base case function on the first value (which depends on
1756 /// `use_fold`), and use that as the base case. Then perform `cs_fold` on the remainder of the
1757 /// fields.
1758 /// When the `substructure` is a `EnumNonMatchingCollapsed`, the result of `enum_nonmatch_f`
1759 /// is returned. Statics may not be folded over.
1760 /// See `cs_op` in `partial_ord.rs` for a model example.
1761 pub fn cs_fold1<F, B>(use_foldl: bool,
1762                       f: F,
1763                       mut b: B,
1764                       enum_nonmatch_f: EnumNonMatchCollapsedFunc,
1765                       cx: &mut ExtCtxt,
1766                       trait_span: Span,
1767                       substructure: &Substructure)
1768                       -> P<Expr>
1769     where F: FnMut(&mut ExtCtxt, Span, P<Expr>, P<Expr>, &[P<Expr>]) -> P<Expr>,
1770           B: FnMut(&mut ExtCtxt, Option<(Span, P<Expr>, &[P<Expr>])>) -> P<Expr>
1771 {
1772     match *substructure.fields {
1773         EnumMatching(.., ref all_fields) |
1774         Struct(_, ref all_fields) => {
1775             let (base, all_fields) = match (all_fields.is_empty(), use_foldl) {
1776                 (false, true) => {
1777                     let field = &all_fields[0];
1778                     let args = (field.span, field.self_.clone(), &field.other[..]);
1779                     (b(cx, Some(args)), &all_fields[1..])
1780                 }
1781                 (false, false) => {
1782                     let idx = all_fields.len() - 1;
1783                     let field = &all_fields[idx];
1784                     let args = (field.span, field.self_.clone(), &field.other[..]);
1785                     (b(cx, Some(args)), &all_fields[..idx])
1786                 }
1787                 (true, _) => (b(cx, None), &all_fields[..])
1788             };
1789
1790             cs_fold_fields(use_foldl, f, base, cx, all_fields)
1791         }
1792         EnumNonMatchingCollapsed(..) => {
1793             cs_fold_enumnonmatch(enum_nonmatch_f, cx, trait_span, substructure)
1794         }
1795         StaticEnum(..) | StaticStruct(..) => {
1796             cs_fold_static(cx, trait_span)
1797         }
1798     }
1799 }
1800
1801 /// Call the method that is being derived on all the fields, and then
1802 /// process the collected results. i.e.
1803 ///
1804 /// ```ignore (only-for-syntax-highlight)
1805 /// f(cx, span, vec![self_1.method(__arg_1_1, __arg_2_1),
1806 ///                  self_2.method(__arg_1_2, __arg_2_2)])
1807 /// ```
1808 #[inline]
1809 pub fn cs_same_method<F>(f: F,
1810                          mut enum_nonmatch_f: EnumNonMatchCollapsedFunc,
1811                          cx: &mut ExtCtxt,
1812                          trait_span: Span,
1813                          substructure: &Substructure)
1814                          -> P<Expr>
1815     where F: FnOnce(&mut ExtCtxt, Span, Vec<P<Expr>>) -> P<Expr>
1816 {
1817     match *substructure.fields {
1818         EnumMatching(.., ref all_fields) |
1819         Struct(_, ref all_fields) => {
1820             // call self_n.method(other_1_n, other_2_n, ...)
1821             let called = all_fields.iter()
1822                 .map(|field| {
1823                     cx.expr_method_call(field.span,
1824                                         field.self_.clone(),
1825                                         substructure.method_ident,
1826                                         field.other
1827                                             .iter()
1828                                             .map(|e| cx.expr_addr_of(field.span, e.clone()))
1829                                             .collect())
1830                 })
1831                 .collect();
1832
1833             f(cx, trait_span, called)
1834         }
1835         EnumNonMatchingCollapsed(ref all_self_args, _, tuple) => {
1836             enum_nonmatch_f(cx,
1837                             trait_span,
1838                             (&all_self_args[..], tuple),
1839                             substructure.nonself_args)
1840         }
1841         StaticEnum(..) | StaticStruct(..) => cx.span_bug(trait_span, "static function in `derive`"),
1842     }
1843 }
1844
1845 /// Return true if the type has no value fields
1846 /// (for an enum, no variant has any fields)
1847 pub fn is_type_without_fields(item: &Annotatable) -> bool {
1848     if let Annotatable::Item(ref item) = *item {
1849         match item.node {
1850             ast::ItemKind::Enum(ref enum_def, _) => {
1851                 enum_def.variants.iter().all(|v| v.node.data.fields().is_empty())
1852             }
1853             ast::ItemKind::Struct(ref variant_data, _) => variant_data.fields().is_empty(),
1854             _ => false,
1855         }
1856     } else {
1857         false
1858     }
1859 }