src/librustc_middle/traits/mod.rs

   1 //! Trait Resolution. See the [rustc dev guide] for more information on how this works.
   2 //!
   3 //! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html
   4
   5 mod chalk;
   6 pub mod query;
   7 pub mod select;
   8 pub mod specialization_graph;
   9 mod structural_impls;
  10
  11 use crate::infer::canonical::Canonical;
  12 use crate::mir::interpret::ErrorHandled;
  13 use crate::ty::subst::SubstsRef;
  14 use crate::ty::{self, AdtKind, Ty, TyCtxt};
  15
  16 use rustc_hir as hir;
  17 use rustc_hir::def_id::DefId;
  18 use rustc_span::symbol::Symbol;
  19 use rustc_span::{Span, DUMMY_SP};
  20 use smallvec::SmallVec;
  21
  22 use std::borrow::Cow;
  23 use std::fmt;
  24 use std::ops::Deref;
  25 use std::rc::Rc;
  26
  27 pub use self::select::{EvaluationCache, EvaluationResult, OverflowError, SelectionCache};
  28
  29 pub type ChalkCanonicalGoal<'tcx> = Canonical<'tcx, ChalkEnvironmentAndGoal<'tcx>>;
  30
  31 pub use self::ObligationCauseCode::*;
  32 pub use self::SelectionError::*;
  33 pub use self::Vtable::*;
  34
  35 pub use self::chalk::{
  36     ChalkEnvironmentAndGoal, ChalkEnvironmentClause, RustDefId as ChalkRustDefId,
  37     RustInterner as ChalkRustInterner,
  38 };
  39
  40 /// Depending on the stage of compilation, we want projection to be
  41 /// more or less conservative.
  42 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, HashStable)]
  43 pub enum Reveal {
  44     /// At type-checking time, we refuse to project any associated
  45     /// type that is marked `default`. Non-`default` ("final") types
  46     /// are always projected. This is necessary in general for
  47     /// soundness of specialization. However, we *could* allow
  48     /// projections in fully-monomorphic cases. We choose not to,
  49     /// because we prefer for `default type` to force the type
  50     /// definition to be treated abstractly by any consumers of the
  51     /// impl. Concretely, that means that the following example will
  52     /// fail to compile:
  53     ///
  54     /// ```
  55     /// trait Assoc {
  56     ///     type Output;
  57     /// }
  58     ///
  59     /// impl<T> Assoc for T {
  60     ///     default type Output = bool;
  61     /// }
  62     ///
  63     /// fn main() {
  64     ///     let <() as Assoc>::Output = true;
  65     /// }
  66     /// ```
  67     UserFacing,
  68
  69     /// At codegen time, all monomorphic projections will succeed.
  70     /// Also, `impl Trait` is normalized to the concrete type,
  71     /// which has to be already collected by type-checking.
  72     ///
  73     /// NOTE: as `impl Trait`'s concrete type should *never*
  74     /// be observable directly by the user, `Reveal::All`
  75     /// should not be used by checks which may expose
  76     /// type equality or type contents to the user.
  77     /// There are some exceptions, e.g., around OIBITS and
  78     /// transmute-checking, which expose some details, but
  79     /// not the whole concrete type of the `impl Trait`.
  80     All,
  81 }
  82
  83 /// The reason why we incurred this obligation; used for error reporting.
  84 ///
  85 /// As the happy path does not care about this struct, storing this on the heap
  86 /// ends up increasing performance.
  87 ///
  88 /// We do not want to intern this as there are a lot of obligation causes which
  89 /// only live for a short period of time.
  90 #[derive(Clone, PartialEq, Eq, Hash)]
  91 pub struct ObligationCause<'tcx> {
  92     data: Rc<ObligationCauseData<'tcx>>,
  93 }
  94
  95 // A dummy obligation. As the parralel compiler does not share `Obligation`s between
  96 // threads, we use a `thread_local` here so we can keep using an `Rc` inside of `ObligationCause`.
  97 thread_local! {
  98     static DUMMY_OBLIGATION_CAUSE: ObligationCause<'static> = ObligationCause::new(DUMMY_SP, hir::CRATE_HIR_ID, MiscObligation);
  99 }
 100
 101 // Correctly format `ObligationCause::dummy`.
 102 impl<'tcx> fmt::Debug for ObligationCause<'tcx> {
 103     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 104         ObligationCauseData::fmt(self, f)
 105     }
 106 }
 107
 108 impl Deref for ObligationCause<'tcx> {
 109     type Target = ObligationCauseData<'tcx>;
 110
 111     fn deref(&self) -> &Self::Target {
 112         &self.data
 113     }
 114 }
 115
 116 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 117 pub struct ObligationCauseData<'tcx> {
 118     pub span: Span,
 119
 120     /// The ID of the fn body that triggered this obligation. This is
 121     /// used for region obligations to determine the precise
 122     /// environment in which the region obligation should be evaluated
 123     /// (in particular, closures can add new assumptions). See the
 124     /// field `region_obligations` of the `FulfillmentContext` for more
 125     /// information.
 126     pub body_id: hir::HirId,
 127
 128     pub code: ObligationCauseCode<'tcx>,
 129 }
 130
 131 impl<'tcx> ObligationCause<'tcx> {
 132     #[inline]
 133     pub fn new(
 134         span: Span,
 135         body_id: hir::HirId,
 136         code: ObligationCauseCode<'tcx>,
 137     ) -> ObligationCause<'tcx> {
 138         ObligationCause { data: Rc::new(ObligationCauseData { span, body_id, code }) }
 139     }
 140
 141     pub fn misc(span: Span, body_id: hir::HirId) -> ObligationCause<'tcx> {
 142         ObligationCause::new(span, body_id, MiscObligation)
 143     }
 144
 145     pub fn dummy_with_span(span: Span) -> ObligationCause<'tcx> {
 146         ObligationCause::new(span, hir::CRATE_HIR_ID, MiscObligation)
 147     }
 148
 149     #[inline(always)]
 150     pub fn dummy() -> ObligationCause<'tcx> {
 151         DUMMY_OBLIGATION_CAUSE.with(Clone::clone)
 152     }
 153
 154     pub fn make_mut(&mut self) -> &mut ObligationCauseData<'tcx> {
 155         Rc::make_mut(&mut self.data)
 156     }
 157
 158     pub fn span(&self, tcx: TyCtxt<'tcx>) -> Span {
 159         match self.code {
 160             ObligationCauseCode::CompareImplMethodObligation { .. }
 161             | ObligationCauseCode::MainFunctionType
 162             | ObligationCauseCode::StartFunctionType => {
 163                 tcx.sess.source_map().guess_head_span(self.span)
 164             }
 165             ObligationCauseCode::MatchExpressionArm(box MatchExpressionArmCause {
 166                 arm_span,
 167                 ..
 168             }) => arm_span,
 169             _ => self.span,
 170         }
 171     }
 172 }
 173
 174 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 175 pub enum ObligationCauseCode<'tcx> {
 176     /// Not well classified or should be obvious from the span.
 177     MiscObligation,
 178
 179     /// A slice or array is WF only if `T: Sized`.
 180     SliceOrArrayElem,
 181
 182     /// A tuple is WF only if its middle elements are `Sized`.
 183     TupleElem,
 184
 185     /// This is the trait reference from the given projection.
 186     ProjectionWf(ty::ProjectionTy<'tcx>),
 187
 188     /// In an impl of trait `X` for type `Y`, type `Y` must
 189     /// also implement all supertraits of `X`.
 190     ItemObligation(DefId),
 191
 192     /// Like `ItemObligation`, but with extra detail on the source of the obligation.
 193     BindingObligation(DefId, Span),
 194
 195     /// A type like `&'a T` is WF only if `T: 'a`.
 196     ReferenceOutlivesReferent(Ty<'tcx>),
 197
 198     /// A type like `Box<Foo<'a> + 'b>` is WF only if `'b: 'a`.
 199     ObjectTypeBound(Ty<'tcx>, ty::Region<'tcx>),
 200
 201     /// Obligation incurred due to an object cast.
 202     ObjectCastObligation(/* Object type */ Ty<'tcx>),
 203
 204     /// Obligation incurred due to a coercion.
 205     Coercion {
 206         source: Ty<'tcx>,
 207         target: Ty<'tcx>,
 208     },
 209
 210     /// Various cases where expressions must be `Sized` / `Copy` / etc.
 211     /// `L = X` implies that `L` is `Sized`.
 212     AssignmentLhsSized,
 213     /// `(x1, .., xn)` must be `Sized`.
 214     TupleInitializerSized,
 215     /// `S { ... }` must be `Sized`.
 216     StructInitializerSized,
 217     /// Type of each variable must be `Sized`.
 218     VariableType(hir::HirId),
 219     /// Argument type must be `Sized`.
 220     SizedArgumentType,
 221     /// Return type must be `Sized`.
 222     SizedReturnType,
 223     /// Yield type must be `Sized`.
 224     SizedYieldType,
 225     /// Inline asm operand type must be `Sized`.
 226     InlineAsmSized,
 227     /// `[T, ..n]` implies that `T` must be `Copy`.
 228     /// If `true`, suggest `const_in_array_repeat_expressions` feature flag.
 229     RepeatVec(bool),
 230
 231     /// Types of fields (other than the last, except for packed structs) in a struct must be sized.
 232     FieldSized {
 233         adt_kind: AdtKind,
 234         last: bool,
 235     },
 236
 237     /// Constant expressions must be sized.
 238     ConstSized,
 239
 240     /// `static` items must have `Sync` type.
 241     SharedStatic,
 242
 243     BuiltinDerivedObligation(DerivedObligationCause<'tcx>),
 244
 245     ImplDerivedObligation(DerivedObligationCause<'tcx>),
 246
 247     DerivedObligation(DerivedObligationCause<'tcx>),
 248
 249     /// Error derived when matching traits/impls; see ObligationCause for more details
 250     CompareImplConstObligation,
 251
 252     /// Error derived when matching traits/impls; see ObligationCause for more details
 253     CompareImplMethodObligation {
 254         item_name: Symbol,
 255         impl_item_def_id: DefId,
 256         trait_item_def_id: DefId,
 257     },
 258
 259     /// Error derived when matching traits/impls; see ObligationCause for more details
 260     CompareImplTypeObligation {
 261         item_name: Symbol,
 262         impl_item_def_id: DefId,
 263         trait_item_def_id: DefId,
 264     },
 265
 266     /// Checking that this expression can be assigned where it needs to be
 267     // FIXME(eddyb) #11161 is the original Expr required?
 268     ExprAssignable,
 269
 270     /// Computing common supertype in the arms of a match expression
 271     MatchExpressionArm(Box<MatchExpressionArmCause<'tcx>>),
 272
 273     /// Type error arising from type checking a pattern against an expected type.
 274     Pattern {
 275         /// The span of the scrutinee or type expression which caused the `root_ty` type.
 276         span: Option<Span>,
 277         /// The root expected type induced by a scrutinee or type expression.
 278         root_ty: Ty<'tcx>,
 279         /// Whether the `Span` came from an expression or a type expression.
 280         origin_expr: bool,
 281     },
 282
 283     /// Constants in patterns must have `Structural` type.
 284     ConstPatternStructural,
 285
 286     /// Computing common supertype in an if expression
 287     IfExpression(Box<IfExpressionCause>),
 288
 289     /// Computing common supertype of an if expression with no else counter-part
 290     IfExpressionWithNoElse,
 291
 292     /// `main` has wrong type
 293     MainFunctionType,
 294
 295     /// `start` has wrong type
 296     StartFunctionType,
 297
 298     /// Intrinsic has wrong type
 299     IntrinsicType,
 300
 301     /// Method receiver
 302     MethodReceiver,
 303
 304     /// `return` with no expression
 305     ReturnNoExpression,
 306
 307     /// `return` with an expression
 308     ReturnValue(hir::HirId),
 309
 310     /// Return type of this function
 311     ReturnType,
 312
 313     /// Block implicit return
 314     BlockTailExpression(hir::HirId),
 315
 316     /// #[feature(trivial_bounds)] is not enabled
 317     TrivialBound,
 318 }
 319
 320 impl ObligationCauseCode<'_> {
 321     // Return the base obligation, ignoring derived obligations.
 322     pub fn peel_derives(&self) -> &Self {
 323         let mut base_cause = self;
 324         while let BuiltinDerivedObligation(cause)
 325         | ImplDerivedObligation(cause)
 326         | DerivedObligation(cause) = base_cause
 327         {
 328             base_cause = &cause.parent_code;
 329         }
 330         base_cause
 331     }
 332 }
 333
 334 // `ObligationCauseCode` is used a lot. Make sure it doesn't unintentionally get bigger.
 335 #[cfg(target_arch = "x86_64")]
 336 static_assert_size!(ObligationCauseCode<'_>, 32);
 337
 338 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 339 pub struct MatchExpressionArmCause<'tcx> {
 340     pub arm_span: Span,
 341     pub source: hir::MatchSource,
 342     pub prior_arms: Vec<Span>,
 343     pub last_ty: Ty<'tcx>,
 344     pub scrut_hir_id: hir::HirId,
 345 }
 346
 347 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 348 pub struct IfExpressionCause {
 349     pub then: Span,
 350     pub outer: Option<Span>,
 351     pub semicolon: Option<Span>,
 352 }
 353
 354 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 355 pub struct DerivedObligationCause<'tcx> {
 356     /// The trait reference of the parent obligation that led to the
 357     /// current obligation. Note that only trait obligations lead to
 358     /// derived obligations, so we just store the trait reference here
 359     /// directly.
 360     pub parent_trait_ref: ty::PolyTraitRef<'tcx>,
 361
 362     /// The parent trait had this cause.
 363     pub parent_code: Rc<ObligationCauseCode<'tcx>>,
 364 }
 365
 366 #[derive(Clone, Debug, TypeFoldable)]
 367 pub enum SelectionError<'tcx> {
 368     Unimplemented,
 369     OutputTypeParameterMismatch(
 370         ty::PolyTraitRef<'tcx>,
 371         ty::PolyTraitRef<'tcx>,
 372         ty::error::TypeError<'tcx>,
 373     ),
 374     TraitNotObjectSafe(DefId),
 375     ConstEvalFailure(ErrorHandled),
 376     Overflow,
 377 }
 378
 379 /// When performing resolution, it is typically the case that there
 380 /// can be one of three outcomes:
 381 ///
 382 /// - `Ok(Some(r))`: success occurred with result `r`
 383 /// - `Ok(None)`: could not definitely determine anything, usually due
 384 ///   to inconclusive type inference.
 385 /// - `Err(e)`: error `e` occurred
 386 pub type SelectionResult<'tcx, T> = Result<Option<T>, SelectionError<'tcx>>;
 387
 388 /// Given the successful resolution of an obligation, the `Vtable`
 389 /// indicates where the vtable comes from. Note that while we call this
 390 /// a "vtable", it does not necessarily indicate dynamic dispatch at
 391 /// runtime. `Vtable` instances just tell the compiler where to find
 392 /// methods, but in generic code those methods are typically statically
 393 /// dispatched -- only when an object is constructed is a `Vtable`
 394 /// instance reified into an actual vtable.
 395 ///
 396 /// For example, the vtable may be tied to a specific impl (case A),
 397 /// or it may be relative to some bound that is in scope (case B).
 398 ///
 399 /// ```
 400 /// impl<T:Clone> Clone<T> for Option<T> { ... } // Impl_1
 401 /// impl<T:Clone> Clone<T> for Box<T> { ... }    // Impl_2
 402 /// impl Clone for int { ... }             // Impl_3
 403 ///
 404 /// fn foo<T:Clone>(concrete: Option<Box<int>>,
 405 ///                 param: T,
 406 ///                 mixed: Option<T>) {
 407 ///
 408 ///    // Case A: Vtable points at a specific impl. Only possible when
 409 ///    // type is concretely known. If the impl itself has bounded
 410 ///    // type parameters, Vtable will carry resolutions for those as well:
 411 ///    concrete.clone(); // Vtable(Impl_1, [Vtable(Impl_2, [Vtable(Impl_3)])])
 412 ///
 413 ///    // Case B: Vtable must be provided by caller. This applies when
 414 ///    // type is a type parameter.
 415 ///    param.clone();    // VtableParam
 416 ///
 417 ///    // Case C: A mix of cases A and B.
 418 ///    mixed.clone();    // Vtable(Impl_1, [VtableParam])
 419 /// }
 420 /// ```
 421 ///
 422 /// ### The type parameter `N`
 423 ///
 424 /// See explanation on `VtableImplData`.
 425 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 426 pub enum Vtable<'tcx, N> {
 427     /// Vtable identifying a particular impl.
 428     VtableImpl(VtableImplData<'tcx, N>),
 429
 430     /// Vtable for auto trait implementations.
 431     /// This carries the information and nested obligations with regards
 432     /// to an auto implementation for a trait `Trait`. The nested obligations
 433     /// ensure the trait implementation holds for all the constituent types.
 434     VtableAutoImpl(VtableAutoImplData<N>),
 435
 436     /// Successful resolution to an obligation provided by the caller
 437     /// for some type parameter. The `Vec<N>` represents the
 438     /// obligations incurred from normalizing the where-clause (if
 439     /// any).
 440     VtableParam(Vec<N>),
 441
 442     /// Virtual calls through an object.
 443     VtableObject(VtableObjectData<'tcx, N>),
 444
 445     /// Successful resolution for a builtin trait.
 446     VtableBuiltin(VtableBuiltinData<N>),
 447
 448     /// Vtable automatically generated for a closure. The `DefId` is the ID
 449     /// of the closure expression. This is a `VtableImpl` in spirit, but the
 450     /// impl is generated by the compiler and does not appear in the source.
 451     VtableClosure(VtableClosureData<'tcx, N>),
 452
 453     /// Same as above, but for a function pointer type with the given signature.
 454     VtableFnPointer(VtableFnPointerData<'tcx, N>),
 455
 456     /// Vtable for a builtin `DeterminantKind` trait implementation.
 457     VtableDiscriminantKind(VtableDiscriminantKindData),
 458
 459     /// Vtable automatically generated for a generator.
 460     VtableGenerator(VtableGeneratorData<'tcx, N>),
 461
 462     /// Vtable for a trait alias.
 463     VtableTraitAlias(VtableTraitAliasData<'tcx, N>),
 464 }
 465
 466 impl<'tcx, N> Vtable<'tcx, N> {
 467     pub fn nested_obligations(self) -> Vec<N> {
 468         match self {
 469             VtableImpl(i) => i.nested,
 470             VtableParam(n) => n,
 471             VtableBuiltin(i) => i.nested,
 472             VtableAutoImpl(d) => d.nested,
 473             VtableClosure(c) => c.nested,
 474             VtableGenerator(c) => c.nested,
 475             VtableObject(d) => d.nested,
 476             VtableFnPointer(d) => d.nested,
 477             VtableDiscriminantKind(VtableDiscriminantKindData) => Vec::new(),
 478             VtableTraitAlias(d) => d.nested,
 479         }
 480     }
 481
 482     pub fn borrow_nested_obligations(&self) -> &[N] {
 483         match &self {
 484             VtableImpl(i) => &i.nested[..],
 485             VtableParam(n) => &n[..],
 486             VtableBuiltin(i) => &i.nested[..],
 487             VtableAutoImpl(d) => &d.nested[..],
 488             VtableClosure(c) => &c.nested[..],
 489             VtableGenerator(c) => &c.nested[..],
 490             VtableObject(d) => &d.nested[..],
 491             VtableFnPointer(d) => &d.nested[..],
 492             VtableDiscriminantKind(VtableDiscriminantKindData) => &[],
 493             VtableTraitAlias(d) => &d.nested[..],
 494         }
 495     }
 496
 497     pub fn map<M, F>(self, f: F) -> Vtable<'tcx, M>
 498     where
 499         F: FnMut(N) -> M,
 500     {
 501         match self {
 502             VtableImpl(i) => VtableImpl(VtableImplData {
 503                 impl_def_id: i.impl_def_id,
 504                 substs: i.substs,
 505                 nested: i.nested.into_iter().map(f).collect(),
 506             }),
 507             VtableParam(n) => VtableParam(n.into_iter().map(f).collect()),
 508             VtableBuiltin(i) => {
 509                 VtableBuiltin(VtableBuiltinData { nested: i.nested.into_iter().map(f).collect() })
 510             }
 511             VtableObject(o) => VtableObject(VtableObjectData {
 512                 upcast_trait_ref: o.upcast_trait_ref,
 513                 vtable_base: o.vtable_base,
 514                 nested: o.nested.into_iter().map(f).collect(),
 515             }),
 516             VtableAutoImpl(d) => VtableAutoImpl(VtableAutoImplData {
 517                 trait_def_id: d.trait_def_id,
 518                 nested: d.nested.into_iter().map(f).collect(),
 519             }),
 520             VtableClosure(c) => VtableClosure(VtableClosureData {
 521                 closure_def_id: c.closure_def_id,
 522                 substs: c.substs,
 523                 nested: c.nested.into_iter().map(f).collect(),
 524             }),
 525             VtableGenerator(c) => VtableGenerator(VtableGeneratorData {
 526                 generator_def_id: c.generator_def_id,
 527                 substs: c.substs,
 528                 nested: c.nested.into_iter().map(f).collect(),
 529             }),
 530             VtableFnPointer(p) => VtableFnPointer(VtableFnPointerData {
 531                 fn_ty: p.fn_ty,
 532                 nested: p.nested.into_iter().map(f).collect(),
 533             }),
 534             VtableDiscriminantKind(VtableDiscriminantKindData) => {
 535                 VtableDiscriminantKind(VtableDiscriminantKindData)
 536             }
 537             VtableTraitAlias(d) => VtableTraitAlias(VtableTraitAliasData {
 538                 alias_def_id: d.alias_def_id,
 539                 substs: d.substs,
 540                 nested: d.nested.into_iter().map(f).collect(),
 541             }),
 542         }
 543     }
 544 }
 545
 546 /// Identifies a particular impl in the source, along with a set of
 547 /// substitutions from the impl's type/lifetime parameters. The
 548 /// `nested` vector corresponds to the nested obligations attached to
 549 /// the impl's type parameters.
 550 ///
 551 /// The type parameter `N` indicates the type used for "nested
 552 /// obligations" that are required by the impl. During type-check, this
 553 /// is `Obligation`, as one might expect. During codegen, however, this
 554 /// is `()`, because codegen only requires a shallow resolution of an
 555 /// impl, and nested obligations are satisfied later.
 556 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 557 pub struct VtableImplData<'tcx, N> {
 558     pub impl_def_id: DefId,
 559     pub substs: SubstsRef<'tcx>,
 560     pub nested: Vec<N>,
 561 }
 562
 563 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 564 pub struct VtableGeneratorData<'tcx, N> {
 565     pub generator_def_id: DefId,
 566     pub substs: SubstsRef<'tcx>,
 567     /// Nested obligations. This can be non-empty if the generator
 568     /// signature contains associated types.
 569     pub nested: Vec<N>,
 570 }
 571
 572 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 573 pub struct VtableClosureData<'tcx, N> {
 574     pub closure_def_id: DefId,
 575     pub substs: SubstsRef<'tcx>,
 576     /// Nested obligations. This can be non-empty if the closure
 577     /// signature contains associated types.
 578     pub nested: Vec<N>,
 579 }
 580
 581 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 582 pub struct VtableAutoImplData<N> {
 583     pub trait_def_id: DefId,
 584     pub nested: Vec<N>,
 585 }
 586
 587 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 588 pub struct VtableBuiltinData<N> {
 589     pub nested: Vec<N>,
 590 }
 591
 592 /// A vtable for some object-safe trait `Foo` automatically derived
 593 /// for the object type `Foo`.
 594 #[derive(PartialEq, Eq, Clone, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 595 pub struct VtableObjectData<'tcx, N> {
 596     /// `Foo` upcast to the obligation trait. This will be some supertrait of `Foo`.
 597     pub upcast_trait_ref: ty::PolyTraitRef<'tcx>,
 598
 599     /// The vtable is formed by concatenating together the method lists of
 600     /// the base object trait and all supertraits; this is the start of
 601     /// `upcast_trait_ref`'s methods in that vtable.
 602     pub vtable_base: usize,
 603
 604     pub nested: Vec<N>,
 605 }
 606
 607 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 608 pub struct VtableFnPointerData<'tcx, N> {
 609     pub fn_ty: Ty<'tcx>,
 610     pub nested: Vec<N>,
 611 }
 612
 613 // FIXME(@lcnr): This should be  refactored and merged with other builtin vtables.
 614 #[derive(Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 615 pub struct VtableDiscriminantKindData;
 616
 617 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 618 pub struct VtableTraitAliasData<'tcx, N> {
 619     pub alias_def_id: DefId,
 620     pub substs: SubstsRef<'tcx>,
 621     pub nested: Vec<N>,
 622 }
 623
 624 #[derive(Clone, Debug, PartialEq, Eq, Hash, HashStable)]
 625 pub enum ObjectSafetyViolation {
 626     /// `Self: Sized` declared on the trait.
 627     SizedSelf(SmallVec<[Span; 1]>),
 628
 629     /// Supertrait reference references `Self` an in illegal location
 630     /// (e.g., `trait Foo : Bar<Self>`).
 631     SupertraitSelf(SmallVec<[Span; 1]>),
 632
 633     /// Method has something illegal.
 634     Method(Symbol, MethodViolationCode, Span),
 635
 636     /// Associated const.
 637     AssocConst(Symbol, Span),
 638 }
 639
 640 impl ObjectSafetyViolation {
 641     pub fn error_msg(&self) -> Cow<'static, str> {
 642         match *self {
 643             ObjectSafetyViolation::SizedSelf(_) => "it requires `Self: Sized`".into(),
 644             ObjectSafetyViolation::SupertraitSelf(ref spans) => {
 645                 if spans.iter().any(|sp| *sp != DUMMY_SP) {
 646                     "it uses `Self` as a type parameter in this".into()
 647                 } else {
 648                     "it cannot use `Self` as a type parameter in a supertrait or `where`-clause"
 649                         .into()
 650                 }
 651             }
 652             ObjectSafetyViolation::Method(name, MethodViolationCode::StaticMethod(_), _) => {
 653                 format!("associated function `{}` has no `self` parameter", name).into()
 654             }
 655             ObjectSafetyViolation::Method(
 656                 name,
 657                 MethodViolationCode::ReferencesSelfInput(_),
 658                 DUMMY_SP,
 659             ) => format!("method `{}` references the `Self` type in its parameters", name).into(),
 660             ObjectSafetyViolation::Method(name, MethodViolationCode::ReferencesSelfInput(_), _) => {
 661                 format!("method `{}` references the `Self` type in this parameter", name).into()
 662             }
 663             ObjectSafetyViolation::Method(name, MethodViolationCode::ReferencesSelfOutput, _) => {
 664                 format!("method `{}` references the `Self` type in its return type", name).into()
 665             }
 666             ObjectSafetyViolation::Method(
 667                 name,
 668                 MethodViolationCode::WhereClauseReferencesSelf,
 669                 _,
 670             ) => {
 671                 format!("method `{}` references the `Self` type in its `where` clause", name).into()
 672             }
 673             ObjectSafetyViolation::Method(name, MethodViolationCode::Generic, _) => {
 674                 format!("method `{}` has generic type parameters", name).into()
 675             }
 676             ObjectSafetyViolation::Method(name, MethodViolationCode::UndispatchableReceiver, _) => {
 677                 format!("method `{}`'s `self` parameter cannot be dispatched on", name).into()
 678             }
 679             ObjectSafetyViolation::AssocConst(name, DUMMY_SP) => {
 680                 format!("it contains associated `const` `{}`", name).into()
 681             }
 682             ObjectSafetyViolation::AssocConst(..) => "it contains this associated `const`".into(),
 683         }
 684     }
 685
 686     pub fn solution(&self) -> Option<(String, Option<(String, Span)>)> {
 687         Some(match *self {
 688             ObjectSafetyViolation::SizedSelf(_) | ObjectSafetyViolation::SupertraitSelf(_) => {
 689                 return None;
 690             }
 691             ObjectSafetyViolation::Method(name, MethodViolationCode::StaticMethod(sugg), _) => (
 692                 format!(
 693                     "consider turning `{}` into a method by giving it a `&self` argument or \
 694                      constraining it so it does not apply to trait objects",
 695                     name
 696                 ),
 697                 sugg.map(|(sugg, sp)| (sugg.to_string(), sp)),
 698             ),
 699             ObjectSafetyViolation::Method(
 700                 name,
 701                 MethodViolationCode::UndispatchableReceiver,
 702                 span,
 703             ) => (
 704                 format!("consider changing method `{}`'s `self` parameter to be `&self`", name),
 705                 Some(("&Self".to_string(), span)),
 706             ),
 707             ObjectSafetyViolation::AssocConst(name, _)
 708             | ObjectSafetyViolation::Method(name, ..) => {
 709                 (format!("consider moving `{}` to another trait", name), None)
 710             }
 711         })
 712     }
 713
 714     pub fn spans(&self) -> SmallVec<[Span; 1]> {
 715         // When `span` comes from a separate crate, it'll be `DUMMY_SP`. Treat it as `None` so
 716         // diagnostics use a `note` instead of a `span_label`.
 717         match self {
 718             ObjectSafetyViolation::SupertraitSelf(spans)
 719             | ObjectSafetyViolation::SizedSelf(spans) => spans.clone(),
 720             ObjectSafetyViolation::AssocConst(_, span)
 721             | ObjectSafetyViolation::Method(_, _, span)
 722                 if *span != DUMMY_SP =>
 723             {
 724                 smallvec![*span]
 725             }
 726             _ => smallvec![],
 727         }
 728     }
 729 }
 730
 731 /// Reasons a method might not be object-safe.
 732 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, HashStable)]
 733 pub enum MethodViolationCode {
 734     /// e.g., `fn foo()`
 735     StaticMethod(Option<(&'static str, Span)>),
 736
 737     /// e.g., `fn foo(&self, x: Self)`
 738     ReferencesSelfInput(usize),
 739
 740     /// e.g., `fn foo(&self) -> Self`
 741     ReferencesSelfOutput,
 742
 743     /// e.g., `fn foo(&self) where Self: Clone`
 744     WhereClauseReferencesSelf,
 745
 746     /// e.g., `fn foo<A>()`
 747     Generic,
 748
 749     /// the method's receiver (`self` argument) can't be dispatched on
 750     UndispatchableReceiver,
 751 }