rustc_middle/traits/
mod.rs

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

rustc_middle/traits/
mod.rs
