rustc_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
5pub mod query;
6pub mod select;
7pub mod solve;
8pub mod specialization_graph;
9mod structural_impls;
10
11use std::borrow::Cow;
12use std::hash::{Hash, Hasher};
13use std::sync::Arc;
14
15use rustc_errors::{Applicability, Diag, EmissionGuarantee, ErrorGuaranteed};
16use rustc_hir as hir;
17use rustc_hir::HirId;
18use rustc_hir::def_id::DefId;
19use rustc_macros::{
20    Decodable, Encodable, HashStable, TyDecodable, TyEncodable, TypeFoldable, TypeVisitable,
21};
22use rustc_span::def_id::{CRATE_DEF_ID, LocalDefId};
23use rustc_span::{DUMMY_SP, Span, Symbol};
24use smallvec::{SmallVec, smallvec};
25use thin_vec::ThinVec;
26
27pub use self::select::{EvaluationCache, EvaluationResult, OverflowError, SelectionCache};
28use crate::mir::ConstraintCategory;
29pub use crate::traits::solve::BuiltinImplSource;
30use crate::ty::abstract_const::NotConstEvaluatable;
31use crate::ty::{self, AdtKind, GenericArgsRef, Ty};
32
33/// The reason why we incurred this obligation; used for error reporting.
34///
35/// Non-misc `ObligationCauseCode`s are stored on the heap. This gives the
36/// best trade-off between keeping the type small (which makes copies cheaper)
37/// while not doing too many heap allocations.
38///
39/// We do not want to intern this as there are a lot of obligation causes which
40/// only live for a short period of time.
41#[derive(Clone, Debug, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
42#[derive(TypeVisitable, TypeFoldable)]
43pub struct ObligationCause<'tcx> {
44    pub span: Span,
45
46    /// The ID of the fn body that triggered this obligation. This is
47    /// used for region obligations to determine the precise
48    /// environment in which the region obligation should be evaluated
49    /// (in particular, closures can add new assumptions). See the
50    /// field `region_obligations` of the `FulfillmentContext` for more
51    /// information.
52    pub body_id: LocalDefId,
53
54    code: ObligationCauseCodeHandle<'tcx>,
55}
56
57// This custom hash function speeds up hashing for `Obligation` deduplication
58// greatly by skipping the `code` field, which can be large and complex. That
59// shouldn't affect hash quality much since there are several other fields in
60// `Obligation` which should be unique enough, especially the predicate itself
61// which is hashed as an interned pointer. See #90996.
62impl Hash for ObligationCause<'_> {
63    fn hash<H: Hasher>(&self, state: &mut H) {
64        self.body_id.hash(state);
65        self.span.hash(state);
66    }
67}
68
69impl<'tcx> ObligationCause<'tcx> {
70    #[inline]
71    pub fn new(
72        span: Span,
73        body_id: LocalDefId,
74        code: ObligationCauseCode<'tcx>,
75    ) -> ObligationCause<'tcx> {
76        ObligationCause { span, body_id, code: code.into() }
77    }
78
79    pub fn misc(span: Span, body_id: LocalDefId) -> ObligationCause<'tcx> {
80        ObligationCause::new(span, body_id, ObligationCauseCode::Misc)
81    }
82
83    #[inline(always)]
84    pub fn dummy() -> ObligationCause<'tcx> {
85        ObligationCause::dummy_with_span(DUMMY_SP)
86    }
87
88    #[inline(always)]
89    pub fn dummy_with_span(span: Span) -> ObligationCause<'tcx> {
90        ObligationCause { span, body_id: CRATE_DEF_ID, code: Default::default() }
91    }
92
93    #[inline]
94    pub fn code(&self) -> &ObligationCauseCode<'tcx> {
95        &self.code
96    }
97
98    pub fn map_code(
99        &mut self,
100        f: impl FnOnce(ObligationCauseCodeHandle<'tcx>) -> ObligationCauseCode<'tcx>,
101    ) {
102        self.code = f(std::mem::take(&mut self.code)).into();
103    }
104
105    pub fn derived_cause(
106        mut self,
107        parent_trait_pred: ty::PolyTraitPredicate<'tcx>,
108        variant: impl FnOnce(DerivedCause<'tcx>) -> ObligationCauseCode<'tcx>,
109    ) -> ObligationCause<'tcx> {
110        /*!
111         * Creates a cause for obligations that are derived from
112         * `obligation` by a recursive search (e.g., for a builtin
113         * bound, or eventually a `auto trait Foo`). If `obligation`
114         * is itself a derived obligation, this is just a clone, but
115         * otherwise we create a "derived obligation" cause so as to
116         * keep track of the original root obligation for error
117         * reporting.
118         */
119
120        // NOTE(flaper87): As of now, it keeps track of the whole error
121        // chain. Ideally, we should have a way to configure this either
122        // by using -Z verbose-internals or just a CLI argument.
123        self.code = variant(DerivedCause { parent_trait_pred, parent_code: self.code }).into();
124        self
125    }
126
127    pub fn derived_host_cause(
128        mut self,
129        parent_host_pred: ty::Binder<'tcx, ty::HostEffectPredicate<'tcx>>,
130        variant: impl FnOnce(DerivedHostCause<'tcx>) -> ObligationCauseCode<'tcx>,
131    ) -> ObligationCause<'tcx> {
132        self.code = variant(DerivedHostCause { parent_host_pred, parent_code: self.code }).into();
133        self
134    }
135
136    pub fn to_constraint_category(&self) -> ConstraintCategory<'tcx> {
137        match self.code() {
138            ObligationCauseCode::MatchImpl(cause, _) => cause.to_constraint_category(),
139            ObligationCauseCode::AscribeUserTypeProvePredicate(predicate_span) => {
140                ConstraintCategory::Predicate(*predicate_span)
141            }
142            _ => ConstraintCategory::BoringNoLocation,
143        }
144    }
145}
146
147/// A compact form of `ObligationCauseCode`.
148#[derive(Clone, PartialEq, Eq, Default, HashStable)]
149#[derive(TypeVisitable, TypeFoldable, TyEncodable, TyDecodable)]
150pub struct ObligationCauseCodeHandle<'tcx> {
151    /// `None` for `ObligationCauseCode::Misc` (a common case, occurs ~60% of
152    /// the time). `Some` otherwise.
153    code: Option<Arc<ObligationCauseCode<'tcx>>>,
154}
155
156impl<'tcx> std::fmt::Debug for ObligationCauseCodeHandle<'tcx> {
157    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
158        let cause: &ObligationCauseCode<'_> = self;
159        cause.fmt(f)
160    }
161}
162
163impl<'tcx> ObligationCauseCode<'tcx> {
164    #[inline(always)]
165    fn into(self) -> ObligationCauseCodeHandle<'tcx> {
166        ObligationCauseCodeHandle {
167            code: if let ObligationCauseCode::Misc = self { None } else { Some(Arc::new(self)) },
168        }
169    }
170}
171
172impl<'tcx> std::ops::Deref for ObligationCauseCodeHandle<'tcx> {
173    type Target = ObligationCauseCode<'tcx>;
174
175    fn deref(&self) -> &Self::Target {
176        self.code.as_deref().unwrap_or(&ObligationCauseCode::Misc)
177    }
178}
179
180#[derive(Clone, Debug, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
181#[derive(TypeVisitable, TypeFoldable)]
182pub enum ObligationCauseCode<'tcx> {
183    /// Not well classified or should be obvious from the span.
184    Misc,
185
186    /// A slice or array is WF only if `T: Sized`.
187    SliceOrArrayElem,
188
189    /// An array `[T; N]` can only be indexed (and is only well-formed if) `N` has type usize.
190    ArrayLen(Ty<'tcx>),
191
192    /// A tuple is WF only if its middle elements are `Sized`.
193    TupleElem,
194
195    /// Represents a clause that comes from a specific item.
196    /// The span corresponds to the clause.
197    WhereClause(DefId, Span),
198
199    /// Represents a bound for an opaque we are checking the well-formedness of.
200    /// The def-id corresponds to a specific definition site that we found the
201    /// hidden type from, if any.
202    OpaqueTypeBound(Span, Option<LocalDefId>),
203
204    /// Like `WhereClause`, but also identifies the expression
205    /// which requires the `where` clause to be proven, and also
206    /// identifies the index of the predicate in the `predicates_of`
207    /// list of the item.
208    WhereClauseInExpr(DefId, Span, HirId, usize),
209
210    /// Like `WhereClauseinExpr`, but indexes into the `const_conditions`
211    /// rather than the `predicates_of`.
212    HostEffectInExpr(DefId, Span, HirId, usize),
213
214    /// A type like `&'a T` is WF only if `T: 'a`.
215    ReferenceOutlivesReferent(Ty<'tcx>),
216
217    /// A type like `Box<Foo<'a> + 'b>` is WF only if `'b: 'a`.
218    ObjectTypeBound(Ty<'tcx>, ty::Region<'tcx>),
219
220    /// Obligation incurred due to a coercion.
221    Coercion {
222        source: Ty<'tcx>,
223        target: Ty<'tcx>,
224    },
225
226    /// Various cases where expressions must be `Sized` / `Copy` / etc.
227    /// `L = X` implies that `L` is `Sized`.
228    AssignmentLhsSized,
229    /// `(x1, .., xn)` must be `Sized`.
230    TupleInitializerSized,
231    /// `S { ... }` must be `Sized`.
232    StructInitializerSized,
233    /// Type of each variable must be `Sized`.
234    VariableType(HirId),
235    /// Argument type must be `Sized`.
236    SizedArgumentType(Option<HirId>),
237    /// Return type must be `Sized`.
238    SizedReturnType,
239    /// Return type of a call expression must be `Sized`.
240    SizedCallReturnType,
241    /// Yield type must be `Sized`.
242    SizedYieldType,
243    /// Inline asm operand type must be `Sized`.
244    InlineAsmSized,
245    /// Captured closure type must be `Sized`.
246    SizedClosureCapture(LocalDefId),
247    /// Types live across coroutine yields must be `Sized`.
248    SizedCoroutineInterior(LocalDefId),
249    /// `[expr; N]` requires `type_of(expr): Copy`.
250    RepeatElementCopy {
251        /// If element is a `const fn` or const ctor we display a help message suggesting
252        /// to move it to a new `const` item while saying that `T` doesn't implement `Copy`.
253        is_constable: IsConstable,
254
255        /// Span of the repeat element.
256        ///
257        /// This is used to suggest wrapping it in a `const { ... }` block.
258        elt_span: Span,
259    },
260
261    /// Types of fields (other than the last, except for packed structs) in a struct must be sized.
262    FieldSized {
263        adt_kind: AdtKind,
264        span: Span,
265        last: bool,
266    },
267
268    /// Constant expressions must be sized.
269    SizedConstOrStatic,
270
271    /// `static` items must have `Sync` type.
272    SharedStatic,
273
274    /// Derived obligation (i.e. theoretical `where` clause) on a built-in
275    /// implementation like `Copy` or `Sized`.
276    BuiltinDerived(DerivedCause<'tcx>),
277
278    /// Derived obligation (i.e. `where` clause) on an user-provided impl
279    /// or a trait alias.
280    ImplDerived(Box<ImplDerivedCause<'tcx>>),
281
282    /// Derived obligation for WF goals.
283    WellFormedDerived(DerivedCause<'tcx>),
284
285    /// Derived obligation (i.e. `where` clause) on an user-provided impl
286    /// or a trait alias.
287    ImplDerivedHost(Box<ImplDerivedHostCause<'tcx>>),
288
289    /// Derived obligation (i.e. `where` clause) on an user-provided impl
290    /// or a trait alias.
291    BuiltinDerivedHost(DerivedHostCause<'tcx>),
292
293    /// Derived obligation refined to point at a specific argument in
294    /// a call or method expression.
295    FunctionArg {
296        /// The node of the relevant argument in the function call.
297        arg_hir_id: HirId,
298        /// The node of the function call.
299        call_hir_id: HirId,
300        /// The obligation introduced by this argument.
301        parent_code: ObligationCauseCodeHandle<'tcx>,
302    },
303
304    /// Error derived when checking an impl item is compatible with
305    /// its corresponding trait item's definition
306    CompareImplItem {
307        impl_item_def_id: LocalDefId,
308        trait_item_def_id: DefId,
309        kind: ty::AssocKind,
310    },
311
312    /// Checking that the bounds of a trait's associated type hold for a given impl
313    CheckAssociatedTypeBounds {
314        impl_item_def_id: LocalDefId,
315        trait_item_def_id: DefId,
316    },
317
318    /// Checking that this expression can be assigned to its target.
319    ExprAssignable,
320
321    /// Computing common supertype in the arms of a match expression
322    MatchExpressionArm(Box<MatchExpressionArmCause<'tcx>>),
323
324    /// Type error arising from type checking a pattern against an expected type.
325    Pattern {
326        /// The span of the scrutinee or type expression which caused the `root_ty` type.
327        span: Option<Span>,
328        /// The root expected type induced by a scrutinee or type expression.
329        root_ty: Ty<'tcx>,
330        /// Information about the `Span`, if it came from an expression, otherwise `None`.
331        origin_expr: Option<PatternOriginExpr>,
332    },
333
334    /// Computing common supertype in an if expression
335    IfExpression {
336        expr_id: HirId,
337        // Is the expectation of this match expression an RPIT?
338        tail_defines_return_position_impl_trait: Option<LocalDefId>,
339    },
340
341    /// Computing common supertype of an if expression with no else counter-part
342    IfExpressionWithNoElse,
343
344    /// `main` has wrong type
345    MainFunctionType,
346
347    /// language function has wrong type
348    LangFunctionType(Symbol),
349
350    /// Intrinsic has wrong type
351    IntrinsicType,
352
353    /// A let else block does not diverge
354    LetElse,
355
356    /// Method receiver
357    MethodReceiver,
358
359    /// `return` with no expression
360    ReturnNoExpression,
361
362    /// `return` with an expression
363    ReturnValue(HirId),
364
365    /// Opaque return type of this function
366    OpaqueReturnType(Option<(Ty<'tcx>, HirId)>),
367
368    /// Block implicit return
369    BlockTailExpression(HirId, hir::MatchSource),
370
371    /// #[feature(trivial_bounds)] is not enabled
372    TrivialBound,
373
374    AwaitableExpr(HirId),
375
376    ForLoopIterator,
377
378    QuestionMark,
379
380    /// Well-formed checking. If a `WellFormedLoc` is provided,
381    /// then it will be used to perform HIR-based wf checking
382    /// after an error occurs, in order to generate a more precise error span.
383    /// This is purely for diagnostic purposes - it is always
384    /// correct to use `Misc` instead, or to specify
385    /// `WellFormed(None)`.
386    WellFormed(Option<WellFormedLoc>),
387
388    /// From `match_impl`. The cause for us having to match an impl, and the DefId we are matching
389    /// against.
390    MatchImpl(ObligationCause<'tcx>, DefId),
391
392    BinOp {
393        lhs_hir_id: HirId,
394        rhs_hir_id: Option<HirId>,
395        rhs_span: Option<Span>,
396        rhs_is_lit: bool,
397        output_ty: Option<Ty<'tcx>>,
398    },
399
400    AscribeUserTypeProvePredicate(Span),
401
402    RustCall,
403
404    DynCompatible(Span),
405
406    /// Obligations to prove that a `Drop` or negative auto trait impl is not stronger than
407    /// the ADT it's being implemented for.
408    AlwaysApplicableImpl,
409
410    /// Requirement for a `const N: Ty` to implement `Ty: ConstParamTy`
411    ConstParam(Ty<'tcx>),
412
413    /// Obligations emitted during the normalization of a free type alias.
414    TypeAlias(ObligationCauseCodeHandle<'tcx>, Span, DefId),
415}
416
417/// Whether a value can be extracted into a const.
418/// Used for diagnostics around array repeat expressions.
419#[derive(Copy, Clone, Debug, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
420pub enum IsConstable {
421    No,
422    /// Call to a const fn
423    Fn,
424    /// Use of a const ctor
425    Ctor,
426}
427
428/// The 'location' at which we try to perform HIR-based wf checking.
429/// This information is used to obtain an `hir::Ty`, which
430/// we can walk in order to obtain precise spans for any
431/// 'nested' types (e.g. `Foo` in `Option<Foo>`).
432#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, HashStable, Encodable, Decodable)]
433#[derive(TypeVisitable, TypeFoldable)]
434pub enum WellFormedLoc {
435    /// Use the type of the provided definition.
436    Ty(LocalDefId),
437    /// Use the type of the parameter of the provided function.
438    /// We cannot use `hir::Param`, since the function may
439    /// not have a body (e.g. a trait method definition)
440    Param {
441        /// The function to lookup the parameter in
442        function: LocalDefId,
443        /// The index of the parameter to use.
444        /// Parameters are indexed from 0, with the return type
445        /// being the last 'parameter'
446        param_idx: usize,
447    },
448}
449
450impl<'tcx> ObligationCauseCode<'tcx> {
451    /// Returns the base obligation, ignoring derived obligations.
452    pub fn peel_derives(&self) -> &Self {
453        let mut base_cause = self;
454        while let Some(parent_code) = base_cause.parent() {
455            base_cause = parent_code;
456        }
457        base_cause
458    }
459
460    pub fn parent(&self) -> Option<&Self> {
461        match self {
462            ObligationCauseCode::FunctionArg { parent_code, .. } => Some(parent_code),
463            ObligationCauseCode::BuiltinDerived(derived)
464            | ObligationCauseCode::WellFormedDerived(derived)
465            | ObligationCauseCode::ImplDerived(box ImplDerivedCause { derived, .. }) => {
466                Some(&derived.parent_code)
467            }
468            ObligationCauseCode::BuiltinDerivedHost(derived)
469            | ObligationCauseCode::ImplDerivedHost(box ImplDerivedHostCause { derived, .. }) => {
470                Some(&derived.parent_code)
471            }
472            _ => None,
473        }
474    }
475
476    /// Returns the base obligation and the base trait predicate, if any, ignoring
477    /// derived obligations.
478    pub fn peel_derives_with_predicate(&self) -> (&Self, Option<ty::PolyTraitPredicate<'tcx>>) {
479        let mut base_cause = self;
480        let mut base_trait_pred = None;
481        while let Some((parent_code, parent_pred)) = base_cause.parent_with_predicate() {
482            base_cause = parent_code;
483            if let Some(parent_pred) = parent_pred {
484                base_trait_pred = Some(parent_pred);
485            }
486        }
487
488        (base_cause, base_trait_pred)
489    }
490
491    pub fn parent_with_predicate(&self) -> Option<(&Self, Option<ty::PolyTraitPredicate<'tcx>>)> {
492        match self {
493            ObligationCauseCode::FunctionArg { parent_code, .. } => Some((parent_code, None)),
494            ObligationCauseCode::BuiltinDerived(derived)
495            | ObligationCauseCode::WellFormedDerived(derived)
496            | ObligationCauseCode::ImplDerived(box ImplDerivedCause { derived, .. }) => {
497                Some((&derived.parent_code, Some(derived.parent_trait_pred)))
498            }
499            _ => None,
500        }
501    }
502
503    pub fn peel_match_impls(&self) -> &Self {
504        match self {
505            ObligationCauseCode::MatchImpl(cause, _) => cause.code(),
506            _ => self,
507        }
508    }
509}
510
511// `ObligationCauseCode` is used a lot. Make sure it doesn't unintentionally get bigger.
512#[cfg(target_pointer_width = "64")]
513rustc_data_structures::static_assert_size!(ObligationCauseCode<'_>, 48);
514
515#[derive(Clone, Debug, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
516#[derive(TypeVisitable, TypeFoldable)]
517pub struct MatchExpressionArmCause<'tcx> {
518    pub arm_block_id: Option<HirId>,
519    pub arm_ty: Ty<'tcx>,
520    pub arm_span: Span,
521    pub prior_arm_block_id: Option<HirId>,
522    pub prior_arm_ty: Ty<'tcx>,
523    pub prior_arm_span: Span,
524    /// Span of the scrutinee of the match (the matched value).
525    pub scrut_span: Span,
526    /// Source of the match, i.e. `match` or a desugaring.
527    pub source: hir::MatchSource,
528    /// Span of the *whole* match expr.
529    pub expr_span: Span,
530    /// Spans of the previous arms except for those that diverge (i.e. evaluate to `!`).
531    ///
532    /// These are used for pointing out errors that may affect several arms.
533    pub prior_non_diverging_arms: Vec<Span>,
534    /// Is the expectation of this match expression an RPIT?
535    pub tail_defines_return_position_impl_trait: Option<LocalDefId>,
536}
537
538/// Information about the origin expression of a pattern, relevant to diagnostics.
539/// Fields here refer to the scrutinee of a pattern.
540/// If the scrutinee isn't given in the diagnostic, then this won't exist.
541#[derive(Copy, Clone, Debug, PartialEq, Eq)]
542#[derive(TypeFoldable, TypeVisitable, HashStable, TyEncodable, TyDecodable)]
543pub struct PatternOriginExpr {
544    /// A span representing the scrutinee expression, with all leading references
545    /// peeled from the expression.
546    /// Only references in the expression are peeled - if the expression refers to a variable
547    /// whose type is a reference, then that reference is kept because it wasn't created
548    /// in the expression.
549    pub peeled_span: Span,
550    /// The number of references that were peeled to produce `peeled_span`.
551    pub peeled_count: usize,
552    /// Does the peeled expression need to be wrapped in parentheses for
553    /// a prefix suggestion (i.e., dereference) to be valid.
554    pub peeled_prefix_suggestion_parentheses: bool,
555}
556
557#[derive(Clone, Debug, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
558#[derive(TypeVisitable, TypeFoldable)]
559pub struct DerivedCause<'tcx> {
560    /// The trait predicate of the parent obligation that led to the
561    /// current obligation. Note that only trait obligations lead to
562    /// derived obligations, so we just store the trait predicate here
563    /// directly.
564    pub parent_trait_pred: ty::PolyTraitPredicate<'tcx>,
565
566    /// The parent trait had this cause.
567    pub parent_code: ObligationCauseCodeHandle<'tcx>,
568}
569
570#[derive(Clone, Debug, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
571#[derive(TypeVisitable, TypeFoldable)]
572pub struct ImplDerivedCause<'tcx> {
573    pub derived: DerivedCause<'tcx>,
574    /// The `DefId` of the `impl` that gave rise to the `derived` obligation.
575    /// If the `derived` obligation arose from a trait alias, which conceptually has a synthetic
576    /// impl, then this will be the `DefId` of that trait alias. Care should therefore be taken to
577    /// handle that exceptional case where appropriate.
578    pub impl_or_alias_def_id: DefId,
579    /// The index of the derived predicate in the parent impl's predicates.
580    pub impl_def_predicate_index: Option<usize>,
581    pub span: Span,
582}
583
584#[derive(Clone, Debug, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
585#[derive(TypeVisitable, TypeFoldable)]
586pub struct DerivedHostCause<'tcx> {
587    /// The trait predicate of the parent obligation that led to the
588    /// current obligation. Note that only trait obligations lead to
589    /// derived obligations, so we just store the trait predicate here
590    /// directly.
591    pub parent_host_pred: ty::Binder<'tcx, ty::HostEffectPredicate<'tcx>>,
592
593    /// The parent trait had this cause.
594    pub parent_code: ObligationCauseCodeHandle<'tcx>,
595}
596
597#[derive(Clone, Debug, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
598#[derive(TypeVisitable, TypeFoldable)]
599pub struct ImplDerivedHostCause<'tcx> {
600    pub derived: DerivedHostCause<'tcx>,
601    /// The `DefId` of the `impl` that gave rise to the `derived` obligation.
602    pub impl_def_id: DefId,
603    pub span: Span,
604}
605
606#[derive(Clone, Debug, PartialEq, Eq, TypeVisitable)]
607pub enum SelectionError<'tcx> {
608    /// The trait is not implemented.
609    Unimplemented,
610    /// After a closure impl has selected, its "outputs" were evaluated
611    /// (which for closures includes the "input" type params) and they
612    /// didn't resolve. See `confirm_poly_trait_refs` for more.
613    SignatureMismatch(Box<SignatureMismatchData<'tcx>>),
614    /// The trait pointed by `DefId` is dyn-incompatible.
615    TraitDynIncompatible(DefId),
616    /// A given constant couldn't be evaluated.
617    NotConstEvaluatable(NotConstEvaluatable),
618    /// Exceeded the recursion depth during type projection.
619    Overflow(OverflowError),
620    /// Computing an opaque type's hidden type caused an error (e.g. a cycle error).
621    /// We can thus not know whether the hidden type implements an auto trait, so
622    /// we should not presume anything about it.
623    OpaqueTypeAutoTraitLeakageUnknown(DefId),
624    /// Error for a `ConstArgHasType` goal
625    ConstArgHasWrongType { ct: ty::Const<'tcx>, ct_ty: Ty<'tcx>, expected_ty: Ty<'tcx> },
626}
627
628#[derive(Clone, Debug, PartialEq, Eq, TypeVisitable)]
629pub struct SignatureMismatchData<'tcx> {
630    pub found_trait_ref: ty::TraitRef<'tcx>,
631    pub expected_trait_ref: ty::TraitRef<'tcx>,
632    pub terr: ty::error::TypeError<'tcx>,
633}
634
635/// When performing resolution, it is typically the case that there
636/// can be one of three outcomes:
637///
638/// - `Ok(Some(r))`: success occurred with result `r`
639/// - `Ok(None)`: could not definitely determine anything, usually due
640///   to inconclusive type inference.
641/// - `Err(e)`: error `e` occurred
642pub type SelectionResult<'tcx, T> = Result<Option<T>, SelectionError<'tcx>>;
643
644/// Given the successful resolution of an obligation, the `ImplSource`
645/// indicates where the impl comes from.
646///
647/// For example, the obligation may be satisfied by a specific impl (case A),
648/// or it may be relative to some bound that is in scope (case B).
649///
650/// ```ignore (illustrative)
651/// impl<T:Clone> Clone<T> for Option<T> { ... } // Impl_1
652/// impl<T:Clone> Clone<T> for Box<T> { ... }    // Impl_2
653/// impl Clone for i32 { ... }                   // Impl_3
654///
655/// fn foo<T: Clone>(concrete: Option<Box<i32>>, param: T, mixed: Option<T>) {
656///     // Case A: ImplSource points at a specific impl. Only possible when
657///     // type is concretely known. If the impl itself has bounded
658///     // type parameters, ImplSource will carry resolutions for those as well:
659///     concrete.clone(); // ImplSource(Impl_1, [ImplSource(Impl_2, [ImplSource(Impl_3)])])
660///
661///     // Case B: ImplSource must be provided by caller. This applies when
662///     // type is a type parameter.
663///     param.clone();    // ImplSource::Param
664///
665///     // Case C: A mix of cases A and B.
666///     mixed.clone();    // ImplSource(Impl_1, [ImplSource::Param])
667/// }
668/// ```
669///
670/// ### The type parameter `N`
671///
672/// See explanation on `ImplSourceUserDefinedData`.
673#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable)]
674#[derive(TypeFoldable, TypeVisitable)]
675pub enum ImplSource<'tcx, N> {
676    /// ImplSource identifying a particular impl.
677    UserDefined(ImplSourceUserDefinedData<'tcx, N>),
678
679    /// Successful resolution to an obligation provided by the caller
680    /// for some type parameter. The `Vec<N>` represents the
681    /// obligations incurred from normalizing the where-clause (if
682    /// any).
683    Param(ThinVec<N>),
684
685    /// Successful resolution for a builtin impl.
686    Builtin(BuiltinImplSource, ThinVec<N>),
687}
688
689impl<'tcx, N> ImplSource<'tcx, N> {
690    pub fn nested_obligations(self) -> ThinVec<N> {
691        match self {
692            ImplSource::UserDefined(i) => i.nested,
693            ImplSource::Param(n) | ImplSource::Builtin(_, n) => n,
694        }
695    }
696
697    pub fn borrow_nested_obligations(&self) -> &[N] {
698        match self {
699            ImplSource::UserDefined(i) => &i.nested,
700            ImplSource::Param(n) | ImplSource::Builtin(_, n) => n,
701        }
702    }
703
704    pub fn borrow_nested_obligations_mut(&mut self) -> &mut [N] {
705        match self {
706            ImplSource::UserDefined(i) => &mut i.nested,
707            ImplSource::Param(n) | ImplSource::Builtin(_, n) => n,
708        }
709    }
710
711    pub fn map<M, F>(self, f: F) -> ImplSource<'tcx, M>
712    where
713        F: FnMut(N) -> M,
714    {
715        match self {
716            ImplSource::UserDefined(i) => ImplSource::UserDefined(ImplSourceUserDefinedData {
717                impl_def_id: i.impl_def_id,
718                args: i.args,
719                nested: i.nested.into_iter().map(f).collect(),
720            }),
721            ImplSource::Param(n) => ImplSource::Param(n.into_iter().map(f).collect()),
722            ImplSource::Builtin(source, n) => {
723                ImplSource::Builtin(source, n.into_iter().map(f).collect())
724            }
725        }
726    }
727}
728
729/// Identifies a particular impl in the source, along with a set of
730/// generic parameters from the impl's type/lifetime parameters. The
731/// `nested` vector corresponds to the nested obligations attached to
732/// the impl's type parameters.
733///
734/// The type parameter `N` indicates the type used for "nested
735/// obligations" that are required by the impl. During type-check, this
736/// is `Obligation`, as one might expect. During codegen, however, this
737/// is `()`, because codegen only requires a shallow resolution of an
738/// impl, and nested obligations are satisfied later.
739#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable)]
740#[derive(TypeFoldable, TypeVisitable)]
741pub struct ImplSourceUserDefinedData<'tcx, N> {
742    pub impl_def_id: DefId,
743    pub args: GenericArgsRef<'tcx>,
744    pub nested: ThinVec<N>,
745}
746
747#[derive(Clone, Debug, PartialEq, Eq, Hash, HashStable, PartialOrd, Ord)]
748pub enum DynCompatibilityViolation {
749    /// `Self: Sized` declared on the trait.
750    SizedSelf(SmallVec<[Span; 1]>),
751
752    /// Supertrait reference references `Self` an in illegal location
753    /// (e.g., `trait Foo : Bar<Self>`).
754    SupertraitSelf(SmallVec<[Span; 1]>),
755
756    // Supertrait has a non-lifetime `for<T>` binder.
757    SupertraitNonLifetimeBinder(SmallVec<[Span; 1]>),
758
759    /// Method has something illegal.
760    Method(Symbol, MethodViolationCode, Span),
761
762    /// Associated const.
763    AssocConst(Symbol, Span),
764
765    /// GAT
766    GAT(Symbol, Span),
767}
768
769impl DynCompatibilityViolation {
770    pub fn error_msg(&self) -> Cow<'static, str> {
771        match self {
772            DynCompatibilityViolation::SizedSelf(_) => "it requires `Self: Sized`".into(),
773            DynCompatibilityViolation::SupertraitSelf(spans) => {
774                if spans.iter().any(|sp| *sp != DUMMY_SP) {
775                    "it uses `Self` as a type parameter".into()
776                } else {
777                    "it cannot use `Self` as a type parameter in a supertrait or `where`-clause"
778                        .into()
779                }
780            }
781            DynCompatibilityViolation::SupertraitNonLifetimeBinder(_) => {
782                "where clause cannot reference non-lifetime `for<...>` variables".into()
783            }
784            DynCompatibilityViolation::Method(name, MethodViolationCode::StaticMethod(_), _) => {
785                format!("associated function `{name}` has no `self` parameter").into()
786            }
787            DynCompatibilityViolation::Method(
788                name,
789                MethodViolationCode::ReferencesSelfInput(_),
790                DUMMY_SP,
791            ) => format!("method `{name}` references the `Self` type in its parameters").into(),
792            DynCompatibilityViolation::Method(
793                name,
794                MethodViolationCode::ReferencesSelfInput(_),
795                _,
796            ) => format!("method `{name}` references the `Self` type in this parameter").into(),
797            DynCompatibilityViolation::Method(
798                name,
799                MethodViolationCode::ReferencesSelfOutput,
800                _,
801            ) => format!("method `{name}` references the `Self` type in its return type").into(),
802            DynCompatibilityViolation::Method(
803                name,
804                MethodViolationCode::ReferencesImplTraitInTrait(_),
805                _,
806            ) => {
807                format!("method `{name}` references an `impl Trait` type in its return type").into()
808            }
809            DynCompatibilityViolation::Method(name, MethodViolationCode::AsyncFn, _) => {
810                format!("method `{name}` is `async`").into()
811            }
812            DynCompatibilityViolation::Method(
813                name,
814                MethodViolationCode::WhereClauseReferencesSelf,
815                _,
816            ) => format!("method `{name}` references the `Self` type in its `where` clause").into(),
817            DynCompatibilityViolation::Method(name, MethodViolationCode::Generic, _) => {
818                format!("method `{name}` has generic type parameters").into()
819            }
820            DynCompatibilityViolation::Method(
821                name,
822                MethodViolationCode::UndispatchableReceiver(_),
823                _,
824            ) => format!("method `{name}`'s `self` parameter cannot be dispatched on").into(),
825            DynCompatibilityViolation::AssocConst(name, DUMMY_SP) => {
826                format!("it contains associated `const` `{name}`").into()
827            }
828            DynCompatibilityViolation::AssocConst(..) => {
829                "it contains this associated `const`".into()
830            }
831            DynCompatibilityViolation::GAT(name, _) => {
832                format!("it contains the generic associated type `{name}`").into()
833            }
834        }
835    }
836
837    pub fn solution(&self) -> DynCompatibilityViolationSolution {
838        match self {
839            DynCompatibilityViolation::SizedSelf(_)
840            | DynCompatibilityViolation::SupertraitSelf(_)
841            | DynCompatibilityViolation::SupertraitNonLifetimeBinder(..) => {
842                DynCompatibilityViolationSolution::None
843            }
844            DynCompatibilityViolation::Method(
845                name,
846                MethodViolationCode::StaticMethod(Some((add_self_sugg, make_sized_sugg))),
847                _,
848            ) => DynCompatibilityViolationSolution::AddSelfOrMakeSized {
849                name: *name,
850                add_self_sugg: add_self_sugg.clone(),
851                make_sized_sugg: make_sized_sugg.clone(),
852            },
853            DynCompatibilityViolation::Method(
854                name,
855                MethodViolationCode::UndispatchableReceiver(Some(span)),
856                _,
857            ) => DynCompatibilityViolationSolution::ChangeToRefSelf(*name, *span),
858            DynCompatibilityViolation::AssocConst(name, _)
859            | DynCompatibilityViolation::GAT(name, _)
860            | DynCompatibilityViolation::Method(name, ..) => {
861                DynCompatibilityViolationSolution::MoveToAnotherTrait(*name)
862            }
863        }
864    }
865
866    pub fn spans(&self) -> SmallVec<[Span; 1]> {
867        // When `span` comes from a separate crate, it'll be `DUMMY_SP`. Treat it as `None` so
868        // diagnostics use a `note` instead of a `span_label`.
869        match self {
870            DynCompatibilityViolation::SupertraitSelf(spans)
871            | DynCompatibilityViolation::SizedSelf(spans)
872            | DynCompatibilityViolation::SupertraitNonLifetimeBinder(spans) => spans.clone(),
873            DynCompatibilityViolation::AssocConst(_, span)
874            | DynCompatibilityViolation::GAT(_, span)
875            | DynCompatibilityViolation::Method(_, _, span)
876                if *span != DUMMY_SP =>
877            {
878                smallvec![*span]
879            }
880            _ => smallvec![],
881        }
882    }
883}
884
885#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
886pub enum DynCompatibilityViolationSolution {
887    None,
888    AddSelfOrMakeSized {
889        name: Symbol,
890        add_self_sugg: (String, Span),
891        make_sized_sugg: (String, Span),
892    },
893    ChangeToRefSelf(Symbol, Span),
894    MoveToAnotherTrait(Symbol),
895}
896
897impl DynCompatibilityViolationSolution {
898    pub fn add_to<G: EmissionGuarantee>(self, err: &mut Diag<'_, G>) {
899        match self {
900            DynCompatibilityViolationSolution::None => {}
901            DynCompatibilityViolationSolution::AddSelfOrMakeSized {
902                name,
903                add_self_sugg,
904                make_sized_sugg,
905            } => {
906                err.span_suggestion(
907                    add_self_sugg.1,
908                    format!(
909                        "consider turning `{name}` into a method by giving it a `&self` argument"
910                    ),
911                    add_self_sugg.0,
912                    Applicability::MaybeIncorrect,
913                );
914                err.span_suggestion(
915                    make_sized_sugg.1,
916                    format!(
917                        "alternatively, consider constraining `{name}` so it does not apply to \
918                             trait objects"
919                    ),
920                    make_sized_sugg.0,
921                    Applicability::MaybeIncorrect,
922                );
923            }
924            DynCompatibilityViolationSolution::ChangeToRefSelf(name, span) => {
925                err.span_suggestion(
926                    span,
927                    format!("consider changing method `{name}`'s `self` parameter to be `&self`"),
928                    "&Self",
929                    Applicability::MachineApplicable,
930                );
931            }
932            DynCompatibilityViolationSolution::MoveToAnotherTrait(name) => {
933                err.help(format!("consider moving `{name}` to another trait"));
934            }
935        }
936    }
937}
938
939/// Reasons a method might not be dyn-compatible.
940#[derive(Clone, Debug, PartialEq, Eq, Hash, HashStable, PartialOrd, Ord)]
941pub enum MethodViolationCode {
942    /// e.g., `fn foo()`
943    StaticMethod(Option<(/* add &self */ (String, Span), /* add Self: Sized */ (String, Span))>),
944
945    /// e.g., `fn foo(&self, x: Self)`
946    ReferencesSelfInput(Option<Span>),
947
948    /// e.g., `fn foo(&self) -> Self`
949    ReferencesSelfOutput,
950
951    /// e.g., `fn foo(&self) -> impl Sized`
952    ReferencesImplTraitInTrait(Span),
953
954    /// e.g., `async fn foo(&self)`
955    AsyncFn,
956
957    /// e.g., `fn foo(&self) where Self: Clone`
958    WhereClauseReferencesSelf,
959
960    /// e.g., `fn foo<A>()`
961    Generic,
962
963    /// the method's receiver (`self` argument) can't be dispatched on
964    UndispatchableReceiver(Option<Span>),
965}
966
967/// These are the error cases for `codegen_select_candidate`.
968#[derive(Copy, Clone, Debug, Hash, HashStable, Encodable, Decodable)]
969pub enum CodegenObligationError {
970    /// Ambiguity can happen when monomorphizing during trans
971    /// expands to some humongous type that never occurred
972    /// statically -- this humongous type can then overflow,
973    /// leading to an ambiguous result. So report this as an
974    /// overflow bug, since I believe this is the only case
975    /// where ambiguity can result.
976    Ambiguity,
977    /// This can trigger when we have a global bound that is not actually satisfied
978    /// due to trivial bounds.
979    Unimplemented,
980    /// The selected impl has unconstrained generic parameters. This will emit an error
981    /// during impl WF checking.
982    UnconstrainedParam(ErrorGuaranteed),
983}