compiler/rustc_builtin_macros/src/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 //! - `EnumTag` when `Self` is an enum, for comparing the enum tags.
  25 //! - `StaticEnum` and `StaticStruct` for static methods, where the type
  26 //!   being derived upon is either an enum or struct respectively. (Any
  27 //!   argument with type Self is just grouped among the non-self
  28 //!   arguments.)
  29 //!
  30 //! In the first two cases, the values from the corresponding fields in
  31 //! all the arguments are grouped together.
  32 //!
  33 //! The non-static cases have `Option<ident>` in several places associated
  34 //! with field `expr`s. This represents the name of the field it is
  35 //! associated with. It is only not `None` when the associated field has
  36 //! an identifier in the source code. For example, the `x`s in the
  37 //! following snippet
  38 //!
  39 //! ```rust
  40 //! # #![allow(dead_code)]
  41 //! struct A { x : i32 }
  42 //!
  43 //! struct B(i32);
  44 //!
  45 //! enum C {
  46 //!     C0(i32),
  47 //!     C1 { x: i32 }
  48 //! }
  49 //! ```
  50 //!
  51 //! The `i32`s in `B` and `C0` don't have an identifier, so the
  52 //! `Option<ident>`s would be `None` for them.
  53 //!
  54 //! In the static cases, the structure is summarized, either into the just
  55 //! spans of the fields or a list of spans and the field idents (for tuple
  56 //! structs and record structs, respectively), or a list of these, for
  57 //! enums (one for each variant). For empty struct and empty enum
  58 //! variants, it is represented as a count of 0.
  59 //!
  60 //! # "`cs`" functions
  61 //!
  62 //! The `cs_...` functions ("combine substructure") are designed to
  63 //! make life easier by providing some pre-made recipes for common
  64 //! threads; mostly calling the function being derived on all the
  65 //! arguments and then combining them back together in some way (or
  66 //! letting the user chose that). They are not meant to be the only
  67 //! way to handle the structures that this code creates.
  68 //!
  69 //! # Examples
  70 //!
  71 //! The following simplified `PartialEq` is used for in-code examples:
  72 //!
  73 //! ```rust
  74 //! trait PartialEq {
  75 //!     fn eq(&self, other: &Self) -> bool;
  76 //! }
  77 //! impl PartialEq for i32 {
  78 //!     fn eq(&self, other: &i32) -> bool {
  79 //!         *self == *other
  80 //!     }
  81 //! }
  82 //! ```
  83 //!
  84 //! Some examples of the values of `SubstructureFields` follow, using the
  85 //! above `PartialEq`, `A`, `B` and `C`.
  86 //!
  87 //! ## Structs
  88 //!
  89 //! When generating the `expr` for the `A` impl, the `SubstructureFields` is
  90 //!
  91 //! ```{.text}
  92 //! Struct(vec![FieldInfo {
  93 //!            span: <span of x>
  94 //!            name: Some(<ident of x>),
  95 //!            self_: <expr for &self.x>,
  96 //!            other: vec![<expr for &other.x]
  97 //!          }])
  98 //! ```
  99 //!
 100 //! For the `B` impl, called with `B(a)` and `B(b)`,
 101 //!
 102 //! ```{.text}
 103 //! Struct(vec![FieldInfo {
 104 //!           span: <span of `i32`>,
 105 //!           name: None,
 106 //!           self_: <expr for &a>
 107 //!           other: vec![<expr for &b>]
 108 //!          }])
 109 //! ```
 110 //!
 111 //! ## Enums
 112 //!
 113 //! When generating the `expr` for a call with `self == C0(a)` and `other
 114 //! == C0(b)`, the SubstructureFields is
 115 //!
 116 //! ```{.text}
 117 //! EnumMatching(0, <ast::Variant for C0>,
 118 //!              vec![FieldInfo {
 119 //!                 span: <span of i32>
 120 //!                 name: None,
 121 //!                 self_: <expr for &a>,
 122 //!                 other: vec![<expr for &b>]
 123 //!               }])
 124 //! ```
 125 //!
 126 //! For `C1 {x}` and `C1 {x}`,
 127 //!
 128 //! ```{.text}
 129 //! EnumMatching(1, <ast::Variant for C1>,
 130 //!              vec![FieldInfo {
 131 //!                 span: <span of x>
 132 //!                 name: Some(<ident of x>),
 133 //!                 self_: <expr for &self.x>,
 134 //!                 other: vec![<expr for &other.x>]
 135 //!                }])
 136 //! ```
 137 //!
 138 //! For the tags,
 139 //!
 140 //! ```{.text}
 141 //! EnumTag(
 142 //!     &[<ident of self tag>, <ident of other tag>], <expr to combine with>)
 143 //! ```
 144 //! Note that this setup doesn't allow for the brute-force "match every variant
 145 //! against every other variant" approach, which is bad because it produces a
 146 //! quadratic amount of code (see #15375).
 147 //!
 148 //! ## Static
 149 //!
 150 //! A static method on the types above would result in,
 151 //!
 152 //! ```{.text}
 153 //! StaticStruct(<ast::VariantData of A>, Named(vec![(<ident of x>, <span of x>)]))
 154 //!
 155 //! StaticStruct(<ast::VariantData of B>, Unnamed(vec![<span of x>]))
 156 //!
 157 //! StaticEnum(<ast::EnumDef of C>,
 158 //!            vec![(<ident of C0>, <span of C0>, Unnamed(vec![<span of i32>])),
 159 //!                 (<ident of C1>, <span of C1>, Named(vec![(<ident of x>, <span of x>)]))])
 160 //! ```
 161
 162 pub use StaticFields::*;
 163 pub use SubstructureFields::*;
 164
 165 use crate::deriving;
 166 use rustc_ast::ptr::P;
 167 use rustc_ast::{
 168     self as ast, BindingAnnotation, ByRef, EnumDef, Expr, Generics, Mutability, PatKind,
 169 };
 170 use rustc_ast::{GenericArg, GenericParamKind, VariantData};
 171 use rustc_attr as attr;
 172 use rustc_expand::base::{Annotatable, ExtCtxt};
 173 use rustc_span::symbol::{kw, sym, Ident, Symbol};
 174 use rustc_span::{Span, DUMMY_SP};
 175 use std::cell::RefCell;
 176 use std::iter;
 177 use std::ops::Not;
 178 use std::vec;
 179 use thin_vec::thin_vec;
 180 use ty::{Bounds, Path, Ref, Self_, Ty};
 181
 182 pub mod ty;
 183
 184 pub struct TraitDef<'a> {
 185     /// The span for the current #[derive(Foo)] header.
 186     pub span: Span,
 187
 188     /// Path of the trait, including any type parameters
 189     pub path: Path,
 190
 191     /// Whether to skip adding the current trait as a bound to the type parameters of the type.
 192     pub skip_path_as_bound: bool,
 193
 194     /// Additional bounds required of any type parameters of the type,
 195     /// other than the current trait
 196     pub additional_bounds: Vec<Ty>,
 197
 198     /// Can this trait be derived for unions?
 199     pub supports_unions: bool,
 200
 201     pub methods: Vec<MethodDef<'a>>,
 202
 203     pub associated_types: Vec<(Ident, Ty)>,
 204
 205     pub is_const: bool,
 206 }
 207
 208 pub struct MethodDef<'a> {
 209     /// name of the method
 210     pub name: Symbol,
 211     /// List of generics, e.g., `R: rand::Rng`
 212     pub generics: Bounds,
 213
 214     /// Is there is a `&self` argument? If not, it is a static function.
 215     pub explicit_self: bool,
 216
 217     /// Arguments other than the self argument.
 218     pub nonself_args: Vec<(Ty, Symbol)>,
 219
 220     /// Returns type
 221     pub ret_ty: Ty,
 222
 223     pub attributes: ast::AttrVec,
 224
 225     pub fieldless_variants_strategy: FieldlessVariantsStrategy,
 226
 227     pub combine_substructure: RefCell<CombineSubstructureFunc<'a>>,
 228 }
 229
 230 /// How to handle fieldless enum variants.
 231 #[derive(PartialEq)]
 232 pub enum FieldlessVariantsStrategy {
 233     /// Combine fieldless variants into a single match arm.
 234     /// This assumes that relevant information has been handled
 235     /// by looking at the enum's discriminant.
 236     Unify,
 237     /// Don't do anything special about fieldless variants. They are
 238     /// handled like any other variant.
 239     Default,
 240     /// If all variants of the enum are fieldless, expand the special
 241     /// `AllFieldLessEnum` substructure, so that the entire enum can be handled
 242     /// at once.
 243     SpecializeIfAllVariantsFieldless,
 244 }
 245
 246 /// All the data about the data structure/method being derived upon.
 247 pub struct Substructure<'a> {
 248     /// ident of self
 249     pub type_ident: Ident,
 250     /// Verbatim access to any non-selflike arguments, i.e. arguments that
 251     /// don't have type `&Self`.
 252     pub nonselflike_args: &'a [P<Expr>],
 253     pub fields: &'a SubstructureFields<'a>,
 254 }
 255
 256 /// Summary of the relevant parts of a struct/enum field.
 257 pub struct FieldInfo {
 258     pub span: Span,
 259     /// None for tuple structs/normal enum variants, Some for normal
 260     /// structs/struct enum variants.
 261     pub name: Option<Ident>,
 262     /// The expression corresponding to this field of `self`
 263     /// (specifically, a reference to it).
 264     pub self_expr: P<Expr>,
 265     /// The expressions corresponding to references to this field in
 266     /// the other selflike arguments.
 267     pub other_selflike_exprs: Vec<P<Expr>>,
 268 }
 269
 270 /// Fields for a static method
 271 pub enum StaticFields {
 272     /// Tuple and unit structs/enum variants like this.
 273     Unnamed(Vec<Span>, bool /*is tuple*/),
 274     /// Normal structs/struct variants.
 275     Named(Vec<(Ident, Span)>),
 276 }
 277
 278 /// A summary of the possible sets of fields.
 279 pub enum SubstructureFields<'a> {
 280     /// A non-static method where `Self` is a struct.
 281     Struct(&'a ast::VariantData, Vec<FieldInfo>),
 282
 283     /// A non-static method handling the entire enum at once
 284     /// (after it has been determined that none of the enum
 285     /// variants has any fields).
 286     AllFieldlessEnum(&'a ast::EnumDef),
 287
 288     /// Matching variants of the enum: variant index, variant count, ast::Variant,
 289     /// fields: the field name is only non-`None` in the case of a struct
 290     /// variant.
 291     EnumMatching(usize, usize, &'a ast::Variant, Vec<FieldInfo>),
 292
 293     /// The tag of an enum. The first field is a `FieldInfo` for the tags, as
 294     /// if they were fields. The second field is the expression to combine the
 295     /// tag expression with; it will be `None` if no match is necessary.
 296     EnumTag(FieldInfo, Option<P<Expr>>),
 297
 298     /// A static method where `Self` is a struct.
 299     StaticStruct(&'a ast::VariantData, StaticFields),
 300
 301     /// A static method where `Self` is an enum.
 302     StaticEnum(&'a ast::EnumDef, Vec<(Ident, Span, StaticFields)>),
 303 }
 304
 305 /// Combine the values of all the fields together. The last argument is
 306 /// all the fields of all the structures.
 307 pub type CombineSubstructureFunc<'a> =
 308     Box<dyn FnMut(&mut ExtCtxt<'_>, Span, &Substructure<'_>) -> BlockOrExpr + 'a>;
 309
 310 pub fn combine_substructure(
 311     f: CombineSubstructureFunc<'_>,
 312 ) -> RefCell<CombineSubstructureFunc<'_>> {
 313     RefCell::new(f)
 314 }
 315
 316 struct TypeParameter {
 317     bound_generic_params: Vec<ast::GenericParam>,
 318     ty: P<ast::Ty>,
 319 }
 320
 321 /// The code snippets built up for derived code are sometimes used as blocks
 322 /// (e.g. in a function body) and sometimes used as expressions (e.g. in a match
 323 /// arm). This structure avoids committing to either form until necessary,
 324 /// avoiding the insertion of any unnecessary blocks.
 325 ///
 326 /// The statements come before the expression.
 327 pub struct BlockOrExpr(Vec<ast::Stmt>, Option<P<Expr>>);
 328
 329 impl BlockOrExpr {
 330     pub fn new_stmts(stmts: Vec<ast::Stmt>) -> BlockOrExpr {
 331         BlockOrExpr(stmts, None)
 332     }
 333
 334     pub fn new_expr(expr: P<Expr>) -> BlockOrExpr {
 335         BlockOrExpr(vec![], Some(expr))
 336     }
 337
 338     pub fn new_mixed(stmts: Vec<ast::Stmt>, expr: Option<P<Expr>>) -> BlockOrExpr {
 339         BlockOrExpr(stmts, expr)
 340     }
 341
 342     // Converts it into a block.
 343     fn into_block(mut self, cx: &ExtCtxt<'_>, span: Span) -> P<ast::Block> {
 344         if let Some(expr) = self.1 {
 345             self.0.push(cx.stmt_expr(expr));
 346         }
 347         cx.block(span, self.0)
 348     }
 349
 350     // Converts it into an expression.
 351     fn into_expr(self, cx: &ExtCtxt<'_>, span: Span) -> P<Expr> {
 352         if self.0.is_empty() {
 353             match self.1 {
 354                 None => cx.expr_block(cx.block(span, vec![])),
 355                 Some(expr) => expr,
 356             }
 357         } else if self.0.len() == 1
 358             && let ast::StmtKind::Expr(expr) = &self.0[0].kind
 359             && self.1.is_none()
 360         {
 361             // There's only a single statement expression. Pull it out.
 362             expr.clone()
 363         } else {
 364             // Multiple statements and/or expressions.
 365             cx.expr_block(self.into_block(cx, span))
 366         }
 367     }
 368 }
 369
 370 /// This method helps to extract all the type parameters referenced from a
 371 /// type. For a type parameter `<T>`, it looks for either a `TyPath` that
 372 /// is not global and starts with `T`, or a `TyQPath`.
 373 /// Also include bound generic params from the input type.
 374 fn find_type_parameters(
 375     ty: &ast::Ty,
 376     ty_param_names: &[Symbol],
 377     cx: &ExtCtxt<'_>,
 378 ) -> Vec<TypeParameter> {
 379     use rustc_ast::visit;
 380
 381     struct Visitor<'a, 'b> {
 382         cx: &'a ExtCtxt<'b>,
 383         ty_param_names: &'a [Symbol],
 384         bound_generic_params_stack: Vec<ast::GenericParam>,
 385         type_params: Vec<TypeParameter>,
 386     }
 387
 388     impl<'a, 'b> visit::Visitor<'a> for Visitor<'a, 'b> {
 389         fn visit_ty(&mut self, ty: &'a ast::Ty) {
 390             if let ast::TyKind::Path(_, path) = &ty.kind
 391                 && let Some(segment) = path.segments.first()
 392                 && self.ty_param_names.contains(&segment.ident.name)
 393             {
 394                 self.type_params.push(TypeParameter {
 395                     bound_generic_params: self.bound_generic_params_stack.clone(),
 396                     ty: P(ty.clone()),
 397                 });
 398             }
 399
 400             visit::walk_ty(self, ty)
 401         }
 402
 403         // Place bound generic params on a stack, to extract them when a type is encountered.
 404         fn visit_poly_trait_ref(&mut self, trait_ref: &'a ast::PolyTraitRef) {
 405             let stack_len = self.bound_generic_params_stack.len();
 406             self.bound_generic_params_stack.extend(trait_ref.bound_generic_params.iter().cloned());
 407
 408             visit::walk_poly_trait_ref(self, trait_ref);
 409
 410             self.bound_generic_params_stack.truncate(stack_len);
 411         }
 412
 413         fn visit_mac_call(&mut self, mac: &ast::MacCall) {
 414             self.cx.span_err(mac.span(), "`derive` cannot be used on items with type macros");
 415         }
 416     }
 417
 418     let mut visitor = Visitor {
 419         cx,
 420         ty_param_names,
 421         bound_generic_params_stack: Vec::new(),
 422         type_params: Vec::new(),
 423     };
 424     visit::Visitor::visit_ty(&mut visitor, ty);
 425
 426     visitor.type_params
 427 }
 428
 429 impl<'a> TraitDef<'a> {
 430     pub fn expand(
 431         self,
 432         cx: &mut ExtCtxt<'_>,
 433         mitem: &ast::MetaItem,
 434         item: &'a Annotatable,
 435         push: &mut dyn FnMut(Annotatable),
 436     ) {
 437         self.expand_ext(cx, mitem, item, push, false);
 438     }
 439
 440     pub fn expand_ext(
 441         self,
 442         cx: &mut ExtCtxt<'_>,
 443         mitem: &ast::MetaItem,
 444         item: &'a Annotatable,
 445         push: &mut dyn FnMut(Annotatable),
 446         from_scratch: bool,
 447     ) {
 448         match item {
 449             Annotatable::Item(item) => {
 450                 let is_packed = item.attrs.iter().any(|attr| {
 451                     for r in attr::find_repr_attrs(&cx.sess, attr) {
 452                         if let attr::ReprPacked(_) = r {
 453                             return true;
 454                         }
 455                     }
 456                     false
 457                 });
 458                 let has_no_type_params = match &item.kind {
 459                     ast::ItemKind::Struct(_, generics)
 460                     | ast::ItemKind::Enum(_, generics)
 461                     | ast::ItemKind::Union(_, generics) => !generics
 462                         .params
 463                         .iter()
 464                         .any(|param| matches!(param.kind, ast::GenericParamKind::Type { .. })),
 465                     _ => unreachable!(),
 466                 };
 467                 let container_id = cx.current_expansion.id.expn_data().parent.expect_local();
 468                 let copy_fields =
 469                     is_packed && has_no_type_params && cx.resolver.has_derive_copy(container_id);
 470
 471                 let newitem = match &item.kind {
 472                     ast::ItemKind::Struct(struct_def, generics) => self.expand_struct_def(
 473                         cx,
 474                         &struct_def,
 475                         item.ident,
 476                         generics,
 477                         from_scratch,
 478                         copy_fields,
 479                     ),
 480                     ast::ItemKind::Enum(enum_def, generics) => {
 481                         // We ignore `is_packed` here, because `repr(packed)`
 482                         // enums cause an error later on.
 483                         //
 484                         // This can only cause further compilation errors
 485                         // downstream in blatantly illegal code, so it is fine.
 486                         self.expand_enum_def(cx, enum_def, item.ident, generics, from_scratch)
 487                     }
 488                     ast::ItemKind::Union(struct_def, generics) => {
 489                         if self.supports_unions {
 490                             self.expand_struct_def(
 491                                 cx,
 492                                 &struct_def,
 493                                 item.ident,
 494                                 generics,
 495                                 from_scratch,
 496                                 copy_fields,
 497                             )
 498                         } else {
 499                             cx.span_err(mitem.span, "this trait cannot be derived for unions");
 500                             return;
 501                         }
 502                     }
 503                     _ => unreachable!(),
 504                 };
 505                 // Keep the lint attributes of the previous item to control how the
 506                 // generated implementations are linted
 507                 let mut attrs = newitem.attrs.clone();
 508                 attrs.extend(
 509                     item.attrs
 510                         .iter()
 511                         .filter(|a| {
 512                             [
 513                                 sym::allow,
 514                                 sym::warn,
 515                                 sym::deny,
 516                                 sym::forbid,
 517                                 sym::stable,
 518                                 sym::unstable,
 519                             ]
 520                             .contains(&a.name_or_empty())
 521                         })
 522                         .cloned(),
 523                 );
 524                 push(Annotatable::Item(P(ast::Item { attrs, ..(*newitem).clone() })))
 525             }
 526             _ => unreachable!(),
 527         }
 528     }
 529
 530     /// Given that we are deriving a trait `DerivedTrait` for a type like:
 531     ///
 532     /// ```ignore (only-for-syntax-highlight)
 533     /// struct Struct<'a, ..., 'z, A, B: DeclaredTrait, C, ..., Z> where C: WhereTrait {
 534     ///     a: A,
 535     ///     b: B::Item,
 536     ///     b1: <B as DeclaredTrait>::Item,
 537     ///     c1: <C as WhereTrait>::Item,
 538     ///     c2: Option<<C as WhereTrait>::Item>,
 539     ///     ...
 540     /// }
 541     /// ```
 542     ///
 543     /// create an impl like:
 544     ///
 545     /// ```ignore (only-for-syntax-highlight)
 546     /// impl<'a, ..., 'z, A, B: DeclaredTrait, C, ... Z> where
 547     ///     C:                       WhereTrait,
 548     ///     A: DerivedTrait + B1 + ... + BN,
 549     ///     B: DerivedTrait + B1 + ... + BN,
 550     ///     C: DerivedTrait + B1 + ... + BN,
 551     ///     B::Item:                 DerivedTrait + B1 + ... + BN,
 552     ///     <C as WhereTrait>::Item: DerivedTrait + B1 + ... + BN,
 553     ///     ...
 554     /// {
 555     ///     ...
 556     /// }
 557     /// ```
 558     ///
 559     /// where B1, ..., BN are the bounds given by `bounds_paths`.'. Z is a phantom type, and
 560     /// therefore does not get bound by the derived trait.
 561     fn create_derived_impl(
 562         &self,
 563         cx: &mut ExtCtxt<'_>,
 564         type_ident: Ident,
 565         generics: &Generics,
 566         field_tys: Vec<P<ast::Ty>>,
 567         methods: Vec<P<ast::AssocItem>>,
 568     ) -> P<ast::Item> {
 569         let trait_path = self.path.to_path(cx, self.span, type_ident, generics);
 570
 571         // Transform associated types from `deriving::ty::Ty` into `ast::AssocItem`
 572         let associated_types = self.associated_types.iter().map(|&(ident, ref type_def)| {
 573             P(ast::AssocItem {
 574                 id: ast::DUMMY_NODE_ID,
 575                 span: self.span,
 576                 ident,
 577                 vis: ast::Visibility {
 578                     span: self.span.shrink_to_lo(),
 579                     kind: ast::VisibilityKind::Inherited,
 580                     tokens: None,
 581                 },
 582                 attrs: ast::AttrVec::new(),
 583                 kind: ast::AssocItemKind::Type(Box::new(ast::TyAlias {
 584                     defaultness: ast::Defaultness::Final,
 585                     generics: Generics::default(),
 586                     where_clauses: (
 587                         ast::TyAliasWhereClause::default(),
 588                         ast::TyAliasWhereClause::default(),
 589                     ),
 590                     where_predicates_split: 0,
 591                     bounds: Vec::new(),
 592                     ty: Some(type_def.to_ty(cx, self.span, type_ident, generics)),
 593                 })),
 594                 tokens: None,
 595             })
 596         });
 597
 598         let mut where_clause = ast::WhereClause::default();
 599         where_clause.span = generics.where_clause.span;
 600         let ctxt = self.span.ctxt();
 601         let span = generics.span.with_ctxt(ctxt);
 602
 603         // Create the generic parameters
 604         let params: Vec<_> = generics
 605             .params
 606             .iter()
 607             .map(|param| match &param.kind {
 608                 GenericParamKind::Lifetime { .. } => param.clone(),
 609                 GenericParamKind::Type { .. } => {
 610                     // I don't think this can be moved out of the loop, since
 611                     // a GenericBound requires an ast id
 612                     let bounds: Vec<_> =
 613                     // extra restrictions on the generics parameters to the
 614                     // type being derived upon
 615                     self.additional_bounds.iter().map(|p| {
 616                         cx.trait_bound(p.to_path(cx, self.span, type_ident, generics))
 617                     }).chain(
 618                         // require the current trait
 619                         self.skip_path_as_bound.not().then(|| cx.trait_bound(trait_path.clone()))
 620                     ).chain(
 621                         // also add in any bounds from the declaration
 622                         param.bounds.iter().cloned()
 623                     ).collect();
 624
 625                     cx.typaram(param.ident.span.with_ctxt(ctxt), param.ident, bounds, None)
 626                 }
 627                 GenericParamKind::Const { ty, kw_span, .. } => {
 628                     let const_nodefault_kind = GenericParamKind::Const {
 629                         ty: ty.clone(),
 630                         kw_span: kw_span.with_ctxt(ctxt),
 631
 632                         // We can't have default values inside impl block
 633                         default: None,
 634                     };
 635                     let mut param_clone = param.clone();
 636                     param_clone.kind = const_nodefault_kind;
 637                     param_clone
 638                 }
 639             })
 640             .collect();
 641
 642         // and similarly for where clauses
 643         where_clause.predicates.extend(generics.where_clause.predicates.iter().map(|clause| {
 644             match clause {
 645                 ast::WherePredicate::BoundPredicate(wb) => {
 646                     let span = wb.span.with_ctxt(ctxt);
 647                     ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate {
 648                         span,
 649                         ..wb.clone()
 650                     })
 651                 }
 652                 ast::WherePredicate::RegionPredicate(wr) => {
 653                     let span = wr.span.with_ctxt(ctxt);
 654                     ast::WherePredicate::RegionPredicate(ast::WhereRegionPredicate {
 655                         span,
 656                         ..wr.clone()
 657                     })
 658                 }
 659                 ast::WherePredicate::EqPredicate(we) => {
 660                     let span = we.span.with_ctxt(ctxt);
 661                     ast::WherePredicate::EqPredicate(ast::WhereEqPredicate { span, ..we.clone() })
 662                 }
 663             }
 664         }));
 665
 666         {
 667             // Extra scope required here so ty_params goes out of scope before params is moved
 668
 669             let mut ty_params = params
 670                 .iter()
 671                 .filter(|param| matches!(param.kind, ast::GenericParamKind::Type { .. }))
 672                 .peekable();
 673
 674             if ty_params.peek().is_some() {
 675                 let ty_param_names: Vec<Symbol> =
 676                     ty_params.map(|ty_param| ty_param.ident.name).collect();
 677
 678                 for field_ty in field_tys {
 679                     let field_ty_params = find_type_parameters(&field_ty, &ty_param_names, cx);
 680
 681                     for field_ty_param in field_ty_params {
 682                         // if we have already handled this type, skip it
 683                         if let ast::TyKind::Path(_, p) = &field_ty_param.ty.kind
 684                             && let [sole_segment] = &*p.segments
 685                             && ty_param_names.contains(&sole_segment.ident.name)
 686                         {
 687                             continue;
 688                         }
 689                         let mut bounds: Vec<_> = self
 690                             .additional_bounds
 691                             .iter()
 692                             .map(|p| cx.trait_bound(p.to_path(cx, self.span, type_ident, generics)))
 693                             .collect();
 694
 695                         // require the current trait
 696                         bounds.push(cx.trait_bound(trait_path.clone()));
 697
 698                         let predicate = ast::WhereBoundPredicate {
 699                             span: self.span,
 700                             bound_generic_params: field_ty_param.bound_generic_params,
 701                             bounded_ty: field_ty_param.ty,
 702                             bounds,
 703                         };
 704
 705                         let predicate = ast::WherePredicate::BoundPredicate(predicate);
 706                         where_clause.predicates.push(predicate);
 707                     }
 708                 }
 709             }
 710         }
 711
 712         let trait_generics = Generics { params, where_clause, span };
 713
 714         // Create the reference to the trait.
 715         let trait_ref = cx.trait_ref(trait_path);
 716
 717         let self_params: Vec<_> = generics
 718             .params
 719             .iter()
 720             .map(|param| match param.kind {
 721                 GenericParamKind::Lifetime { .. } => {
 722                     GenericArg::Lifetime(cx.lifetime(param.ident.span.with_ctxt(ctxt), param.ident))
 723                 }
 724                 GenericParamKind::Type { .. } => {
 725                     GenericArg::Type(cx.ty_ident(param.ident.span.with_ctxt(ctxt), param.ident))
 726                 }
 727                 GenericParamKind::Const { .. } => {
 728                     GenericArg::Const(cx.const_ident(param.ident.span.with_ctxt(ctxt), param.ident))
 729                 }
 730             })
 731             .collect();
 732
 733         // Create the type of `self`.
 734         let path = cx.path_all(self.span, false, vec![type_ident], self_params);
 735         let self_type = cx.ty_path(path);
 736
 737         let attr = cx.attr_word(sym::automatically_derived, self.span);
 738         let attrs = thin_vec![attr];
 739         let opt_trait_ref = Some(trait_ref);
 740
 741         cx.item(
 742             self.span,
 743             Ident::empty(),
 744             attrs,
 745             ast::ItemKind::Impl(Box::new(ast::Impl {
 746                 unsafety: ast::Unsafe::No,
 747                 polarity: ast::ImplPolarity::Positive,
 748                 defaultness: ast::Defaultness::Final,
 749                 constness: if self.is_const { ast::Const::Yes(DUMMY_SP) } else { ast::Const::No },
 750                 generics: trait_generics,
 751                 of_trait: opt_trait_ref,
 752                 self_ty: self_type,
 753                 items: methods.into_iter().chain(associated_types).collect(),
 754             })),
 755         )
 756     }
 757
 758     fn expand_struct_def(
 759         &self,
 760         cx: &mut ExtCtxt<'_>,
 761         struct_def: &'a VariantData,
 762         type_ident: Ident,
 763         generics: &Generics,
 764         from_scratch: bool,
 765         copy_fields: bool,
 766     ) -> P<ast::Item> {
 767         let field_tys: Vec<P<ast::Ty>> =
 768             struct_def.fields().iter().map(|field| field.ty.clone()).collect();
 769
 770         let methods = self
 771             .methods
 772             .iter()
 773             .map(|method_def| {
 774                 let (explicit_self, selflike_args, nonselflike_args, nonself_arg_tys) =
 775                     method_def.extract_arg_details(cx, self, type_ident, generics);
 776
 777                 let body = if from_scratch || method_def.is_static() {
 778                     method_def.expand_static_struct_method_body(
 779                         cx,
 780                         self,
 781                         struct_def,
 782                         type_ident,
 783                         &nonselflike_args,
 784                     )
 785                 } else {
 786                     method_def.expand_struct_method_body(
 787                         cx,
 788                         self,
 789                         struct_def,
 790                         type_ident,
 791                         &selflike_args,
 792                         &nonselflike_args,
 793                         copy_fields,
 794                     )
 795                 };
 796
 797                 method_def.create_method(
 798                     cx,
 799                     self,
 800                     type_ident,
 801                     generics,
 802                     explicit_self,
 803                     nonself_arg_tys,
 804                     body,
 805                 )
 806             })
 807             .collect();
 808
 809         self.create_derived_impl(cx, type_ident, generics, field_tys, methods)
 810     }
 811
 812     fn expand_enum_def(
 813         &self,
 814         cx: &mut ExtCtxt<'_>,
 815         enum_def: &'a EnumDef,
 816         type_ident: Ident,
 817         generics: &Generics,
 818         from_scratch: bool,
 819     ) -> P<ast::Item> {
 820         let mut field_tys = Vec::new();
 821
 822         for variant in &enum_def.variants {
 823             field_tys.extend(variant.data.fields().iter().map(|field| field.ty.clone()));
 824         }
 825
 826         let methods = self
 827             .methods
 828             .iter()
 829             .map(|method_def| {
 830                 let (explicit_self, selflike_args, nonselflike_args, nonself_arg_tys) =
 831                     method_def.extract_arg_details(cx, self, type_ident, generics);
 832
 833                 let body = if from_scratch || method_def.is_static() {
 834                     method_def.expand_static_enum_method_body(
 835                         cx,
 836                         self,
 837                         enum_def,
 838                         type_ident,
 839                         &nonselflike_args,
 840                     )
 841                 } else {
 842                     method_def.expand_enum_method_body(
 843                         cx,
 844                         self,
 845                         enum_def,
 846                         type_ident,
 847                         selflike_args,
 848                         &nonselflike_args,
 849                     )
 850                 };
 851
 852                 method_def.create_method(
 853                     cx,
 854                     self,
 855                     type_ident,
 856                     generics,
 857                     explicit_self,
 858                     nonself_arg_tys,
 859                     body,
 860                 )
 861             })
 862             .collect();
 863
 864         self.create_derived_impl(cx, type_ident, generics, field_tys, methods)
 865     }
 866 }
 867
 868 impl<'a> MethodDef<'a> {
 869     fn call_substructure_method(
 870         &self,
 871         cx: &mut ExtCtxt<'_>,
 872         trait_: &TraitDef<'_>,
 873         type_ident: Ident,
 874         nonselflike_args: &[P<Expr>],
 875         fields: &SubstructureFields<'_>,
 876     ) -> BlockOrExpr {
 877         let span = trait_.span;
 878         let substructure = Substructure { type_ident, nonselflike_args, fields };
 879         let mut f = self.combine_substructure.borrow_mut();
 880         let f: &mut CombineSubstructureFunc<'_> = &mut *f;
 881         f(cx, span, &substructure)
 882     }
 883
 884     fn get_ret_ty(
 885         &self,
 886         cx: &mut ExtCtxt<'_>,
 887         trait_: &TraitDef<'_>,
 888         generics: &Generics,
 889         type_ident: Ident,
 890     ) -> P<ast::Ty> {
 891         self.ret_ty.to_ty(cx, trait_.span, type_ident, generics)
 892     }
 893
 894     fn is_static(&self) -> bool {
 895         !self.explicit_self
 896     }
 897
 898     // The return value includes:
 899     // - explicit_self: The `&self` arg, if present.
 900     // - selflike_args: Expressions for `&self` (if present) and also any other
 901     //   args with the same type (e.g. the `other` arg in `PartialEq::eq`).
 902     // - nonselflike_args: Expressions for all the remaining args.
 903     // - nonself_arg_tys: Additional information about all the args other than
 904     //   `&self`.
 905     fn extract_arg_details(
 906         &self,
 907         cx: &mut ExtCtxt<'_>,
 908         trait_: &TraitDef<'_>,
 909         type_ident: Ident,
 910         generics: &Generics,
 911     ) -> (Option<ast::ExplicitSelf>, Vec<P<Expr>>, Vec<P<Expr>>, Vec<(Ident, P<ast::Ty>)>) {
 912         let mut selflike_args = Vec::new();
 913         let mut nonselflike_args = Vec::new();
 914         let mut nonself_arg_tys = Vec::new();
 915         let span = trait_.span;
 916
 917         let explicit_self = if self.explicit_self {
 918             let (self_expr, explicit_self) = ty::get_explicit_self(cx, span);
 919             selflike_args.push(self_expr);
 920             Some(explicit_self)
 921         } else {
 922             None
 923         };
 924
 925         for (ty, name) in self.nonself_args.iter() {
 926             let ast_ty = ty.to_ty(cx, span, type_ident, generics);
 927             let ident = Ident::new(*name, span);
 928             nonself_arg_tys.push((ident, ast_ty));
 929
 930             let arg_expr = cx.expr_ident(span, ident);
 931
 932             match ty {
 933                 // Selflike (`&Self`) arguments only occur in non-static methods.
 934                 Ref(box Self_, _) if !self.is_static() => selflike_args.push(arg_expr),
 935                 Self_ => cx.span_bug(span, "`Self` in non-return position"),
 936                 _ => nonselflike_args.push(arg_expr),
 937             }
 938         }
 939
 940         (explicit_self, selflike_args, nonselflike_args, nonself_arg_tys)
 941     }
 942
 943     fn create_method(
 944         &self,
 945         cx: &mut ExtCtxt<'_>,
 946         trait_: &TraitDef<'_>,
 947         type_ident: Ident,
 948         generics: &Generics,
 949         explicit_self: Option<ast::ExplicitSelf>,
 950         nonself_arg_tys: Vec<(Ident, P<ast::Ty>)>,
 951         body: BlockOrExpr,
 952     ) -> P<ast::AssocItem> {
 953         let span = trait_.span;
 954         // Create the generics that aren't for `Self`.
 955         let fn_generics = self.generics.to_generics(cx, span, type_ident, generics);
 956
 957         let args = {
 958             let self_arg = explicit_self.map(|explicit_self| {
 959                 let ident = Ident::with_dummy_span(kw::SelfLower).with_span_pos(span);
 960                 ast::Param::from_self(ast::AttrVec::default(), explicit_self, ident)
 961             });
 962             let nonself_args =
 963                 nonself_arg_tys.into_iter().map(|(name, ty)| cx.param(span, name, ty));
 964             self_arg.into_iter().chain(nonself_args).collect()
 965         };
 966
 967         let ret_type = self.get_ret_ty(cx, trait_, generics, type_ident);
 968
 969         let method_ident = Ident::new(self.name, span);
 970         let fn_decl = cx.fn_decl(args, ast::FnRetTy::Ty(ret_type));
 971         let body_block = body.into_block(cx, span);
 972
 973         let trait_lo_sp = span.shrink_to_lo();
 974
 975         let sig = ast::FnSig { header: ast::FnHeader::default(), decl: fn_decl, span };
 976         let defaultness = ast::Defaultness::Final;
 977
 978         // Create the method.
 979         P(ast::AssocItem {
 980             id: ast::DUMMY_NODE_ID,
 981             attrs: self.attributes.clone(),
 982             span,
 983             vis: ast::Visibility {
 984                 span: trait_lo_sp,
 985                 kind: ast::VisibilityKind::Inherited,
 986                 tokens: None,
 987             },
 988             ident: method_ident,
 989             kind: ast::AssocItemKind::Fn(Box::new(ast::Fn {
 990                 defaultness,
 991                 sig,
 992                 generics: fn_generics,
 993                 body: Some(body_block),
 994             })),
 995             tokens: None,
 996         })
 997     }
 998
 999     /// The normal case uses field access.
1000     /// ```
1001     /// #[derive(PartialEq)]
1002     /// # struct Dummy;
1003     /// struct A { x: u8, y: u8 }
1004     ///
1005     /// // equivalent to:
1006     /// impl PartialEq for A {
1007     ///     fn eq(&self, other: &A) -> bool {
1008     ///         self.x == other.x && self.y == other.y
1009     ///     }
1010     /// }
1011     /// ```
1012     /// But if the struct is `repr(packed)`, we can't use something like
1013     /// `&self.x` because that might cause an unaligned ref. So for any trait
1014     /// method that takes a reference, if the struct impls `Copy` then we use a
1015     /// local block to force a copy:
1016     /// ```
1017     /// # struct A { x: u8, y: u8 }
1018     /// impl PartialEq for A {
1019     ///     fn eq(&self, other: &A) -> bool {
1020     ///         // Desugars to `{ self.x }.eq(&{ other.y }) && ...`
1021     ///         { self.x } == { other.y } && { self.y } == { other.y }
1022     ///     }
1023     /// }
1024     /// impl Hash for A {
1025     ///     fn hash<__H: ::core::hash::Hasher>(&self, state: &mut __H) -> () {
1026     ///         ::core::hash::Hash::hash(&{ self.x }, state);
1027     ///         ::core::hash::Hash::hash(&{ self.y }, state)
1028     ///     }
1029     /// }
1030     /// ```
1031     /// If the struct doesn't impl `Copy`, we use the normal `&self.x`. This
1032     /// only works if the fields match the alignment required by the
1033     /// `packed(N)` attribute. (We'll get errors later on if not.)
1034     fn expand_struct_method_body<'b>(
1035         &self,
1036         cx: &mut ExtCtxt<'_>,
1037         trait_: &TraitDef<'b>,
1038         struct_def: &'b VariantData,
1039         type_ident: Ident,
1040         selflike_args: &[P<Expr>],
1041         nonselflike_args: &[P<Expr>],
1042         copy_fields: bool,
1043     ) -> BlockOrExpr {
1044         assert!(selflike_args.len() == 1 || selflike_args.len() == 2);
1045
1046         let selflike_fields =
1047             trait_.create_struct_field_access_fields(cx, selflike_args, struct_def, copy_fields);
1048         self.call_substructure_method(
1049             cx,
1050             trait_,
1051             type_ident,
1052             nonselflike_args,
1053             &Struct(struct_def, selflike_fields),
1054         )
1055     }
1056
1057     fn expand_static_struct_method_body(
1058         &self,
1059         cx: &mut ExtCtxt<'_>,
1060         trait_: &TraitDef<'_>,
1061         struct_def: &VariantData,
1062         type_ident: Ident,
1063         nonselflike_args: &[P<Expr>],
1064     ) -> BlockOrExpr {
1065         let summary = trait_.summarise_struct(cx, struct_def);
1066
1067         self.call_substructure_method(
1068             cx,
1069             trait_,
1070             type_ident,
1071             nonselflike_args,
1072             &StaticStruct(struct_def, summary),
1073         )
1074     }
1075
1076     /// ```
1077     /// #[derive(PartialEq)]
1078     /// # struct Dummy;
1079     /// enum A {
1080     ///     A1,
1081     ///     A2(i32)
1082     /// }
1083     /// ```
1084     /// is equivalent to:
1085     /// ```
1086     /// #![feature(core_intrinsics)]
1087     /// enum A {
1088     ///     A1,
1089     ///     A2(i32)
1090     /// }
1091     /// impl ::core::cmp::PartialEq for A {
1092     ///     #[inline]
1093     ///     fn eq(&self, other: &A) -> bool {
1094     ///         let __self_tag = ::core::intrinsics::discriminant_value(self);
1095     ///         let __arg1_tag = ::core::intrinsics::discriminant_value(other);
1096     ///         __self_tag == __arg1_tag &&
1097     ///             match (self, other) {
1098     ///                 (A::A2(__self_0), A::A2(__arg1_0)) =>
1099     ///                     *__self_0 == *__arg1_0,
1100     ///                 _ => true,
1101     ///             }
1102     ///     }
1103     /// }
1104     /// ```
1105     /// Creates a tag check combined with a match for a tuple of all
1106     /// `selflike_args`, with an arm for each variant with fields, possibly an
1107     /// arm for each fieldless variant (if `unify_fieldless_variants` is not
1108     /// `Unify`), and possibly a default arm.
1109     fn expand_enum_method_body<'b>(
1110         &self,
1111         cx: &mut ExtCtxt<'_>,
1112         trait_: &TraitDef<'b>,
1113         enum_def: &'b EnumDef,
1114         type_ident: Ident,
1115         selflike_args: Vec<P<Expr>>,
1116         nonselflike_args: &[P<Expr>],
1117     ) -> BlockOrExpr {
1118         let span = trait_.span;
1119         let variants = &enum_def.variants;
1120
1121         // Traits that unify fieldless variants always use the tag(s).
1122         let unify_fieldless_variants =
1123             self.fieldless_variants_strategy == FieldlessVariantsStrategy::Unify;
1124
1125         // There is no sensible code to be generated for *any* deriving on a
1126         // zero-variant enum. So we just generate a failing expression.
1127         if variants.is_empty() {
1128             return BlockOrExpr(vec![], Some(deriving::call_unreachable(cx, span)));
1129         }
1130
1131         let prefixes = iter::once("__self".to_string())
1132             .chain(
1133                 selflike_args
1134                     .iter()
1135                     .enumerate()
1136                     .skip(1)
1137                     .map(|(arg_count, _selflike_arg)| format!("__arg{}", arg_count)),
1138             )
1139             .collect::<Vec<String>>();
1140
1141         // Build a series of let statements mapping each selflike_arg
1142         // to its discriminant value.
1143         //
1144         // e.g. for `PartialEq::eq` builds two statements:
1145         // ```
1146         // let __self_tag = ::core::intrinsics::discriminant_value(self);
1147         // let __arg1_tag = ::core::intrinsics::discriminant_value(other);
1148         // ```
1149         let get_tag_pieces = |cx: &ExtCtxt<'_>| {
1150             let tag_idents: Vec<_> = prefixes
1151                 .iter()
1152                 .map(|name| Ident::from_str_and_span(&format!("{}_tag", name), span))
1153                 .collect();
1154
1155             let mut tag_exprs: Vec<_> = tag_idents
1156                 .iter()
1157                 .map(|&ident| cx.expr_addr_of(span, cx.expr_ident(span, ident)))
1158                 .collect();
1159
1160             let self_expr = tag_exprs.remove(0);
1161             let other_selflike_exprs = tag_exprs;
1162             let tag_field = FieldInfo { span, name: None, self_expr, other_selflike_exprs };
1163
1164             let tag_let_stmts: Vec<_> = iter::zip(&tag_idents, &selflike_args)
1165                 .map(|(&ident, selflike_arg)| {
1166                     let variant_value = deriving::call_intrinsic(
1167                         cx,
1168                         span,
1169                         sym::discriminant_value,
1170                         vec![selflike_arg.clone()],
1171                     );
1172                     cx.stmt_let(span, false, ident, variant_value)
1173                 })
1174                 .collect();
1175
1176             (tag_field, tag_let_stmts)
1177         };
1178
1179         // There are some special cases involving fieldless enums where no
1180         // match is necessary.
1181         let all_fieldless = variants.iter().all(|v| v.data.fields().is_empty());
1182         if all_fieldless {
1183             if variants.len() > 1 {
1184                 match self.fieldless_variants_strategy {
1185                     FieldlessVariantsStrategy::Unify => {
1186                         // If the type is fieldless and the trait uses the tag and
1187                         // there are multiple variants, we need just an operation on
1188                         // the tag(s).
1189                         let (tag_field, mut tag_let_stmts) = get_tag_pieces(cx);
1190                         let mut tag_check = self.call_substructure_method(
1191                             cx,
1192                             trait_,
1193                             type_ident,
1194                             nonselflike_args,
1195                             &EnumTag(tag_field, None),
1196                         );
1197                         tag_let_stmts.append(&mut tag_check.0);
1198                         return BlockOrExpr(tag_let_stmts, tag_check.1);
1199                     }
1200                     FieldlessVariantsStrategy::SpecializeIfAllVariantsFieldless => {
1201                         return self.call_substructure_method(
1202                             cx,
1203                             trait_,
1204                             type_ident,
1205                             nonselflike_args,
1206                             &AllFieldlessEnum(enum_def),
1207                         );
1208                     }
1209                     FieldlessVariantsStrategy::Default => (),
1210                 }
1211             } else if variants.len() == 1 {
1212                 // If there is a single variant, we don't need an operation on
1213                 // the tag(s). Just use the most degenerate result.
1214                 return self.call_substructure_method(
1215                     cx,
1216                     trait_,
1217                     type_ident,
1218                     nonselflike_args,
1219                     &EnumMatching(0, 1, &variants[0], Vec::new()),
1220                 );
1221             }
1222         }
1223
1224         // These arms are of the form:
1225         // (Variant1, Variant1, ...) => Body1
1226         // (Variant2, Variant2, ...) => Body2
1227         // ...
1228         // where each tuple has length = selflike_args.len()
1229         let mut match_arms: Vec<ast::Arm> = variants
1230             .iter()
1231             .enumerate()
1232             .filter(|&(_, v)| !(unify_fieldless_variants && v.data.fields().is_empty()))
1233             .map(|(index, variant)| {
1234                 // A single arm has form (&VariantK, &VariantK, ...) => BodyK
1235                 // (see "Final wrinkle" note below for why.)
1236
1237                 let fields = trait_.create_struct_pattern_fields(cx, &variant.data, &prefixes);
1238
1239                 let sp = variant.span.with_ctxt(trait_.span.ctxt());
1240                 let variant_path = cx.path(sp, vec![type_ident, variant.ident]);
1241                 let by_ref = ByRef::No; // because enums can't be repr(packed)
1242                 let mut subpats: Vec<_> = trait_.create_struct_patterns(
1243                     cx,
1244                     variant_path,
1245                     &variant.data,
1246                     &prefixes,
1247                     by_ref,
1248                 );
1249
1250                 // `(VariantK, VariantK, ...)` or just `VariantK`.
1251                 let single_pat = if subpats.len() == 1 {
1252                     subpats.pop().unwrap()
1253                 } else {
1254                     cx.pat_tuple(span, subpats)
1255                 };
1256
1257                 // For the BodyK, we need to delegate to our caller,
1258                 // passing it an EnumMatching to indicate which case
1259                 // we are in.
1260                 //
1261                 // Now, for some given VariantK, we have built up
1262                 // expressions for referencing every field of every
1263                 // Self arg, assuming all are instances of VariantK.
1264                 // Build up code associated with such a case.
1265                 let substructure = EnumMatching(index, variants.len(), variant, fields);
1266                 let arm_expr = self
1267                     .call_substructure_method(
1268                         cx,
1269                         trait_,
1270                         type_ident,
1271                         nonselflike_args,
1272                         &substructure,
1273                     )
1274                     .into_expr(cx, span);
1275
1276                 cx.arm(span, single_pat, arm_expr)
1277             })
1278             .collect();
1279
1280         // Add a default arm to the match, if necessary.
1281         let first_fieldless = variants.iter().find(|v| v.data.fields().is_empty());
1282         let default = match first_fieldless {
1283             Some(v) if unify_fieldless_variants => {
1284                 // We need a default case that handles all the fieldless
1285                 // variants. The index and actual variant aren't meaningful in
1286                 // this case, so just use dummy values.
1287                 Some(
1288                     self.call_substructure_method(
1289                         cx,
1290                         trait_,
1291                         type_ident,
1292                         nonselflike_args,
1293                         &EnumMatching(0, variants.len(), v, Vec::new()),
1294                     )
1295                     .into_expr(cx, span),
1296                 )
1297             }
1298             _ if variants.len() > 1 && selflike_args.len() > 1 => {
1299                 // Because we know that all the arguments will match if we reach
1300                 // the match expression we add the unreachable intrinsics as the
1301                 // result of the default which should help llvm in optimizing it.
1302                 Some(deriving::call_unreachable(cx, span))
1303             }
1304             _ => None,
1305         };
1306         if let Some(arm) = default {
1307             match_arms.push(cx.arm(span, cx.pat_wild(span), arm));
1308         }
1309
1310         // Create a match expression with one arm per discriminant plus
1311         // possibly a default arm, e.g.:
1312         //      match (self, other) {
1313         //          (Variant1, Variant1, ...) => Body1
1314         //          (Variant2, Variant2, ...) => Body2,
1315         //          ...
1316         //          _ => ::core::intrinsics::unreachable()
1317         //      }
1318         let get_match_expr = |mut selflike_args: Vec<P<Expr>>| {
1319             let match_arg = if selflike_args.len() == 1 {
1320                 selflike_args.pop().unwrap()
1321             } else {
1322                 cx.expr(span, ast::ExprKind::Tup(selflike_args))
1323             };
1324             cx.expr_match(span, match_arg, match_arms)
1325         };
1326
1327         // If the trait uses the tag and there are multiple variants, we need
1328         // to add a tag check operation before the match. Otherwise, the match
1329         // is enough.
1330         if unify_fieldless_variants && variants.len() > 1 {
1331             let (tag_field, mut tag_let_stmts) = get_tag_pieces(cx);
1332
1333             // Combine a tag check with the match.
1334             let mut tag_check_plus_match = self.call_substructure_method(
1335                 cx,
1336                 trait_,
1337                 type_ident,
1338                 nonselflike_args,
1339                 &EnumTag(tag_field, Some(get_match_expr(selflike_args))),
1340             );
1341             tag_let_stmts.append(&mut tag_check_plus_match.0);
1342             BlockOrExpr(tag_let_stmts, tag_check_plus_match.1)
1343         } else {
1344             BlockOrExpr(vec![], Some(get_match_expr(selflike_args)))
1345         }
1346     }
1347
1348     fn expand_static_enum_method_body(
1349         &self,
1350         cx: &mut ExtCtxt<'_>,
1351         trait_: &TraitDef<'_>,
1352         enum_def: &EnumDef,
1353         type_ident: Ident,
1354         nonselflike_args: &[P<Expr>],
1355     ) -> BlockOrExpr {
1356         let summary = enum_def
1357             .variants
1358             .iter()
1359             .map(|v| {
1360                 let sp = v.span.with_ctxt(trait_.span.ctxt());
1361                 let summary = trait_.summarise_struct(cx, &v.data);
1362                 (v.ident, sp, summary)
1363             })
1364             .collect();
1365         self.call_substructure_method(
1366             cx,
1367             trait_,
1368             type_ident,
1369             nonselflike_args,
1370             &StaticEnum(enum_def, summary),
1371         )
1372     }
1373 }
1374
1375 // general helper methods.
1376 impl<'a> TraitDef<'a> {
1377     fn summarise_struct(&self, cx: &mut ExtCtxt<'_>, struct_def: &VariantData) -> StaticFields {
1378         let mut named_idents = Vec::new();
1379         let mut just_spans = Vec::new();
1380         for field in struct_def.fields() {
1381             let sp = field.span.with_ctxt(self.span.ctxt());
1382             match field.ident {
1383                 Some(ident) => named_idents.push((ident, sp)),
1384                 _ => just_spans.push(sp),
1385             }
1386         }
1387
1388         let is_tuple = matches!(struct_def, ast::VariantData::Tuple(..));
1389         match (just_spans.is_empty(), named_idents.is_empty()) {
1390             (false, false) => {
1391                 cx.span_bug(self.span, "a struct with named and unnamed fields in generic `derive`")
1392             }
1393             // named fields
1394             (_, false) => Named(named_idents),
1395             // unnamed fields
1396             (false, _) => Unnamed(just_spans, is_tuple),
1397             // empty
1398             _ => Named(Vec::new()),
1399         }
1400     }
1401
1402     fn create_struct_patterns(
1403         &self,
1404         cx: &mut ExtCtxt<'_>,
1405         struct_path: ast::Path,
1406         struct_def: &'a VariantData,
1407         prefixes: &[String],
1408         by_ref: ByRef,
1409     ) -> Vec<P<ast::Pat>> {
1410         prefixes
1411             .iter()
1412             .map(|prefix| {
1413                 let pieces_iter =
1414                     struct_def.fields().iter().enumerate().map(|(i, struct_field)| {
1415                         let sp = struct_field.span.with_ctxt(self.span.ctxt());
1416                         let ident = self.mk_pattern_ident(prefix, i);
1417                         let path = ident.with_span_pos(sp);
1418                         (
1419                             sp,
1420                             struct_field.ident,
1421                             cx.pat(
1422                                 path.span,
1423                                 PatKind::Ident(
1424                                     BindingAnnotation(by_ref, Mutability::Not),
1425                                     path,
1426                                     None,
1427                                 ),
1428                             ),
1429                         )
1430                     });
1431
1432                 let struct_path = struct_path.clone();
1433                 match *struct_def {
1434                     VariantData::Struct(..) => {
1435                         let field_pats = pieces_iter
1436                             .map(|(sp, ident, pat)| {
1437                                 if ident.is_none() {
1438                                     cx.span_bug(
1439                                         sp,
1440                                         "a braced struct with unnamed fields in `derive`",
1441                                     );
1442                                 }
1443                                 ast::PatField {
1444                                     ident: ident.unwrap(),
1445                                     is_shorthand: false,
1446                                     attrs: ast::AttrVec::new(),
1447                                     id: ast::DUMMY_NODE_ID,
1448                                     span: pat.span.with_ctxt(self.span.ctxt()),
1449                                     pat,
1450                                     is_placeholder: false,
1451                                 }
1452                             })
1453                             .collect();
1454                         cx.pat_struct(self.span, struct_path, field_pats)
1455                     }
1456                     VariantData::Tuple(..) => {
1457                         let subpats = pieces_iter.map(|(_, _, subpat)| subpat).collect();
1458                         cx.pat_tuple_struct(self.span, struct_path, subpats)
1459                     }
1460                     VariantData::Unit(..) => cx.pat_path(self.span, struct_path),
1461                 }
1462             })
1463             .collect()
1464     }
1465
1466     fn create_fields<F>(&self, struct_def: &'a VariantData, mk_exprs: F) -> Vec<FieldInfo>
1467     where
1468         F: Fn(usize, &ast::FieldDef, Span) -> Vec<P<ast::Expr>>,
1469     {
1470         struct_def
1471             .fields()
1472             .iter()
1473             .enumerate()
1474             .map(|(i, struct_field)| {
1475                 // For this field, get an expr for each selflike_arg. E.g. for
1476                 // `PartialEq::eq`, one for each of `&self` and `other`.
1477                 let sp = struct_field.span.with_ctxt(self.span.ctxt());
1478                 let mut exprs: Vec<_> = mk_exprs(i, struct_field, sp);
1479                 let self_expr = exprs.remove(0);
1480                 let other_selflike_exprs = exprs;
1481                 FieldInfo {
1482                     span: sp.with_ctxt(self.span.ctxt()),
1483                     name: struct_field.ident,
1484                     self_expr,
1485                     other_selflike_exprs,
1486                 }
1487             })
1488             .collect()
1489     }
1490
1491     fn mk_pattern_ident(&self, prefix: &str, i: usize) -> Ident {
1492         Ident::from_str_and_span(&format!("{}_{}", prefix, i), self.span)
1493     }
1494
1495     fn create_struct_pattern_fields(
1496         &self,
1497         cx: &mut ExtCtxt<'_>,
1498         struct_def: &'a VariantData,
1499         prefixes: &[String],
1500     ) -> Vec<FieldInfo> {
1501         self.create_fields(struct_def, |i, _struct_field, sp| {
1502             prefixes
1503                 .iter()
1504                 .map(|prefix| {
1505                     let ident = self.mk_pattern_ident(prefix, i);
1506                     cx.expr_path(cx.path_ident(sp, ident))
1507                 })
1508                 .collect()
1509         })
1510     }
1511
1512     fn create_struct_field_access_fields(
1513         &self,
1514         cx: &mut ExtCtxt<'_>,
1515         selflike_args: &[P<Expr>],
1516         struct_def: &'a VariantData,
1517         copy_fields: bool,
1518     ) -> Vec<FieldInfo> {
1519         self.create_fields(struct_def, |i, struct_field, sp| {
1520             selflike_args
1521                 .iter()
1522                 .map(|selflike_arg| {
1523                     // Note: we must use `struct_field.span` rather than `sp` in the
1524                     // `unwrap_or_else` case otherwise the hygiene is wrong and we get
1525                     // "field `0` of struct `Point` is private" errors on tuple
1526                     // structs.
1527                     let mut field_expr = cx.expr(
1528                         sp,
1529                         ast::ExprKind::Field(
1530                             selflike_arg.clone(),
1531                             struct_field.ident.unwrap_or_else(|| {
1532                                 Ident::from_str_and_span(&i.to_string(), struct_field.span)
1533                             }),
1534                         ),
1535                     );
1536                     if copy_fields {
1537                         field_expr = cx.expr_block(
1538                             cx.block(struct_field.span, vec![cx.stmt_expr(field_expr)]),
1539                         );
1540                     }
1541                     cx.expr_addr_of(sp, field_expr)
1542                 })
1543                 .collect()
1544         })
1545     }
1546 }
1547
1548 /// The function passed to `cs_fold` is called repeatedly with a value of this
1549 /// type. It describes one part of the code generation. The result is always an
1550 /// expression.
1551 pub enum CsFold<'a> {
1552     /// The basic case: a field expression for one or more selflike args. E.g.
1553     /// for `PartialEq::eq` this is something like `self.x == other.x`.
1554     Single(&'a FieldInfo),
1555
1556     /// The combination of two field expressions. E.g. for `PartialEq::eq` this
1557     /// is something like `<field1 equality> && <field2 equality>`.
1558     Combine(Span, P<Expr>, P<Expr>),
1559
1560     // The fallback case for a struct or enum variant with no fields.
1561     Fieldless,
1562 }
1563
1564 /// Folds over fields, combining the expressions for each field in a sequence.
1565 /// Statics may not be folded over.
1566 pub fn cs_fold<F>(
1567     use_foldl: bool,
1568     cx: &mut ExtCtxt<'_>,
1569     trait_span: Span,
1570     substructure: &Substructure<'_>,
1571     mut f: F,
1572 ) -> P<Expr>
1573 where
1574     F: FnMut(&mut ExtCtxt<'_>, CsFold<'_>) -> P<Expr>,
1575 {
1576     match substructure.fields {
1577         EnumMatching(.., all_fields) | Struct(_, all_fields) => {
1578             if all_fields.is_empty() {
1579                 return f(cx, CsFold::Fieldless);
1580             }
1581
1582             let (base_field, rest) = if use_foldl {
1583                 all_fields.split_first().unwrap()
1584             } else {
1585                 all_fields.split_last().unwrap()
1586             };
1587
1588             let base_expr = f(cx, CsFold::Single(base_field));
1589
1590             let op = |old, field: &FieldInfo| {
1591                 let new = f(cx, CsFold::Single(field));
1592                 f(cx, CsFold::Combine(field.span, old, new))
1593             };
1594
1595             if use_foldl {
1596                 rest.iter().fold(base_expr, op)
1597             } else {
1598                 rest.iter().rfold(base_expr, op)
1599             }
1600         }
1601         EnumTag(tag_field, match_expr) => {
1602             let tag_check_expr = f(cx, CsFold::Single(tag_field));
1603             if let Some(match_expr) = match_expr {
1604                 if use_foldl {
1605                     f(cx, CsFold::Combine(trait_span, tag_check_expr, match_expr.clone()))
1606                 } else {
1607                     f(cx, CsFold::Combine(trait_span, match_expr.clone(), tag_check_expr))
1608                 }
1609             } else {
1610                 tag_check_expr
1611             }
1612         }
1613         StaticEnum(..) | StaticStruct(..) => cx.span_bug(trait_span, "static function in `derive`"),
1614         AllFieldlessEnum(..) => cx.span_bug(trait_span, "fieldless enum in `derive`"),
1615     }
1616 }