src/libsyntax_ext/deriving/generic/mod.rs

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