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