]> git.proxmox.com Git - rustc.git/blame - compiler/rustc_middle/src/traits/select.rs
New upstream version 1.56.0+dfsg1
[rustc.git] / compiler / rustc_middle / src / traits / select.rs
CommitLineData
ba9703b0 1//! Candidate selection. See the [rustc dev guide] for more information on how this works.
0531ce1d 2//!
ba9703b0 3//! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html#selection
1a4d82fc 4
1a4d82fc
JJ
5use self::EvaluationResult::*;
6
74b04a01 7use super::{SelectionError, SelectionResult};
0bf4aa26 8
3dfed10e 9use crate::ty;
9fa01778 10
74b04a01 11use rustc_hir::def_id::DefId;
3dfed10e 12use rustc_query_system::cache::Cache;
1a4d82fc 13
3dfed10e 14pub type SelectionCache<'tcx> = Cache<
94222f64 15 ty::ConstnessAnd<ty::ParamEnvAnd<'tcx, ty::TraitRef<'tcx>>>,
3dfed10e
XL
16 SelectionResult<'tcx, SelectionCandidate<'tcx>>,
17>;
1a4d82fc 18
3dfed10e 19pub type EvaluationCache<'tcx> =
94222f64 20 Cache<ty::ParamEnvAnd<'tcx, ty::ConstnessAnd<ty::PolyTraitRef<'tcx>>>, EvaluationResult>;
74b04a01 21
1a4d82fc 22/// The selection process begins by considering all impls, where
9fa01778 23/// clauses, and so forth that might resolve an obligation. Sometimes
1a4d82fc 24/// we'll be able to say definitively that (e.g.) an impl does not
c34b1796 25/// apply to the obligation: perhaps it is defined for `usize` but the
f9f354fc 26/// obligation is for `i32`. In that case, we drop the impl out of the
9fa01778 27/// list. But the other cases are considered *candidates*.
1a4d82fc 28///
d9579d0f
AL
29/// For selection to succeed, there must be exactly one matching
30/// candidate. If the obligation is fully known, this is guaranteed
31/// by coherence. However, if the obligation contains type parameters
32/// or variables, there may be multiple such impls.
1a4d82fc 33///
d9579d0f
AL
34/// It is not a real problem if multiple matching impls exist because
35/// of type variables - it just means the obligation isn't sufficiently
36/// elaborated. In that case we report an ambiguity, and the caller can
37/// try again after more type information has been gathered or report a
e74abb32 38/// "type annotations needed" error.
d9579d0f
AL
39///
40/// However, with type parameters, this can be a real problem - type
41/// parameters don't unify with regular types, but they *can* unify
42/// with variables from blanket impls, and (unless we know its bounds
43/// will always be satisfied) picking the blanket impl will be wrong
44/// for at least *some* substitutions. To make this concrete, if we have
45///
f9f354fc
XL
46/// ```rust, ignore
47/// trait AsDebug { type Out: fmt::Debug; fn debug(self) -> Self::Out; }
48/// impl<T: fmt::Debug> AsDebug for T {
49/// type Out = T;
50/// fn debug(self) -> fmt::Debug { self }
51/// }
52/// fn foo<T: AsDebug>(t: T) { println!("{:?}", <T as AsDebug>::debug(t)); }
53/// ```
d9579d0f 54///
60c5eb7d
XL
55/// we can't just use the impl to resolve the `<T as AsDebug>` obligation
56/// -- a type from another crate (that doesn't implement `fmt::Debug`) could
57/// implement `AsDebug`.
d9579d0f
AL
58///
59/// Because where-clauses match the type exactly, multiple clauses can
60/// only match if there are unresolved variables, and we can mostly just
61/// report this ambiguity in that case. This is still a problem - we can't
62/// *do anything* with ambiguities that involve only regions. This is issue
63/// #21974.
64///
65/// If a single where-clause matches and there are no inference
66/// variables left, then it definitely matches and we can just select
67/// it.
68///
69/// In fact, we even select the where-clause when the obligation contains
70/// inference variables. The can lead to inference making "leaps of logic",
71/// for example in this situation:
72///
f9f354fc
XL
73/// ```rust, ignore
74/// pub trait Foo<T> { fn foo(&self) -> T; }
75/// impl<T> Foo<()> for T { fn foo(&self) { } }
76/// impl Foo<bool> for bool { fn foo(&self) -> bool { *self } }
d9579d0f 77///
f9f354fc
XL
78/// pub fn foo<T>(t: T) where T: Foo<bool> {
79/// println!("{:?}", <T as Foo<_>>::foo(&t));
80/// }
81/// fn main() { foo(false); }
82/// ```
d9579d0f 83///
60c5eb7d
XL
84/// Here the obligation `<T as Foo<$0>>` can be matched by both the blanket
85/// impl and the where-clause. We select the where-clause and unify `$0=bool`,
d9579d0f 86/// so the program prints "false". However, if the where-clause is omitted,
60c5eb7d 87/// the blanket impl is selected, we unify `$0=()`, and the program prints
d9579d0f
AL
88/// "()".
89///
90/// Exactly the same issues apply to projection and object candidates, except
91/// that we can have both a projection candidate and a where-clause candidate
92/// for the same obligation. In that case either would do (except that
93/// different "leaps of logic" would occur if inference variables are
e9174d1e 94/// present), and we just pick the where-clause. This is, for example,
d9579d0f
AL
95/// required for associated types to work in default impls, as the bounds
96/// are visible both as projection bounds and as where-clauses from the
97/// parameter environment.
60c5eb7d 98#[derive(PartialEq, Eq, Debug, Clone, TypeFoldable)]
74b04a01 99pub enum SelectionCandidate<'tcx> {
0bf4aa26 100 BuiltinCandidate {
60c5eb7d 101 /// `false` if there are no *further* obligations.
0bf4aa26
XL
102 has_nested: bool,
103 },
fc512014 104 ParamCandidate(ty::ConstnessAnd<ty::PolyTraitRef<'tcx>>),
e9174d1e 105 ImplCandidate(DefId),
abe05a73 106 AutoImplCandidate(DefId),
1a4d82fc 107
29967ef6
XL
108 /// This is a trait matching with a projected type as `Self`, and we found
109 /// an applicable bound in the trait definition. The `usize` is an index
110 /// into the list returned by `tcx.item_bounds`.
111 ProjectionCandidate(usize),
1a4d82fc 112
a7813a04 113 /// Implementation of a `Fn`-family trait by one of the anonymous types
94222f64 114 /// generated for an `||` expression.
ea8adc8c
XL
115 ClosureCandidate,
116
117 /// Implementation of a `Generator` trait by one of the anonymous types
118 /// generated for a generator.
119 GeneratorCandidate,
1a4d82fc
JJ
120
121 /// Implementation of a `Fn`-family trait by one of the anonymous
60c5eb7d 122 /// types generated for a fn pointer type (e.g., `fn(int) -> int`)
1a4d82fc
JJ
123 FnPointerCandidate,
124
f9f354fc
XL
125 /// Builtin implementation of `DiscriminantKind`.
126 DiscriminantKindCandidate,
127
6a06907d
XL
128 /// Builtin implementation of `Pointee`.
129 PointeeCandidate,
130
a1dfa0c6
XL
131 TraitAliasCandidate(DefId),
132
29967ef6
XL
133 /// Matching `dyn Trait` with a supertrait of `Trait`. The index is the
134 /// position in the iterator returned by
135 /// `rustc_infer::traits::util::supertraits`.
136 ObjectCandidate(usize),
1a4d82fc 137
94222f64
XL
138 /// Perform trait upcasting coercion of `dyn Trait` to a supertrait of `Trait`.
139 /// The index is the position in the iterator returned by
140 /// `rustc_infer::traits::util::supertraits`.
141 TraitUpcastingUnsizeCandidate(usize),
142
c34b1796
AL
143 BuiltinObjectCandidate,
144
d9579d0f 145 BuiltinUnsizeCandidate,
1a4d82fc
JJ
146}
147
92a42be0
SL
148/// The result of trait evaluation. The order is important
149/// here as the evaluation of a list is the maximum of the
150/// evaluations.
3b2f2976
XL
151///
152/// The evaluation results are ordered:
0731742a
XL
153/// - `EvaluatedToOk` implies `EvaluatedToOkModuloRegions`
154/// implies `EvaluatedToAmbig` implies `EvaluatedToUnknown`
3b2f2976
XL
155/// - `EvaluatedToErr` implies `EvaluatedToRecur`
156/// - the "union" of evaluation results is equal to their maximum -
157/// all the "potential success" candidates can potentially succeed,
9fa01778 158/// so they are noops when unioned with a definite error, and within
3b2f2976 159/// the categories it's easy to see that the unions are correct.
60c5eb7d 160#[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq, HashStable)]
83c7162d 161pub enum EvaluationResult {
60c5eb7d 162 /// Evaluation successful.
1a4d82fc 163 EvaluatedToOk,
60c5eb7d 164 /// Evaluation successful, but there were unevaluated region obligations.
0731742a 165 EvaluatedToOkModuloRegions,
60c5eb7d 166 /// Evaluation is known to be ambiguous -- it *might* hold for some
3b2f2976
XL
167 /// assignment of inference variables, but it might not.
168 ///
60c5eb7d
XL
169 /// While this has the same meaning as `EvaluatedToUnknown` -- we can't
170 /// know whether this obligation holds or not -- it is the result we
3b2f2976 171 /// would get with an empty stack, and therefore is cacheable.
1a4d82fc 172 EvaluatedToAmbig,
3b2f2976
XL
173 /// Evaluation failed because of recursion involving inference
174 /// variables. We are somewhat imprecise there, so we don't actually
175 /// know the real result.
176 ///
177 /// This can't be trivially cached for the same reason as `EvaluatedToRecur`.
178 EvaluatedToUnknown,
179 /// Evaluation failed because we encountered an obligation we are already
180 /// trying to prove on this branch.
181 ///
182 /// We know this branch can't be a part of a minimal proof-tree for
183 /// the "root" of our cycle, because then we could cut out the recursion
184 /// and maintain a valid proof tree. However, this does not mean
60c5eb7d 185 /// that all the obligations on this branch do not hold -- it's possible
3b2f2976
XL
186 /// that we entered this branch "speculatively", and that there
187 /// might be some other way to prove this obligation that does not
60c5eb7d 188 /// go through this cycle -- so we can't cache this as a failure.
3b2f2976
XL
189 ///
190 /// For example, suppose we have this:
191 ///
192 /// ```rust,ignore (pseudo-Rust)
60c5eb7d
XL
193 /// pub trait Trait { fn xyz(); }
194 /// // This impl is "useless", but we can still have
195 /// // an `impl Trait for SomeUnsizedType` somewhere.
196 /// impl<T: Trait + Sized> Trait for T { fn xyz() {} }
3b2f2976 197 ///
60c5eb7d
XL
198 /// pub fn foo<T: Trait + ?Sized>() {
199 /// <T as Trait>::xyz();
200 /// }
3b2f2976
XL
201 /// ```
202 ///
203 /// When checking `foo`, we have to prove `T: Trait`. This basically
204 /// translates into this:
205 ///
83c7162d 206 /// ```plain,ignore
60c5eb7d 207 /// (T: Trait + Sized →_\impl T: Trait), T: Trait ⊢ T: Trait
83c7162d 208 /// ```
3b2f2976
XL
209 ///
210 /// When we try to prove it, we first go the first option, which
9fa01778 211 /// recurses. This shows us that the impl is "useless" -- it won't
3b2f2976
XL
212 /// tell us that `T: Trait` unless it already implemented `Trait`
213 /// by some other means. However, that does not prevent `T: Trait`
214 /// does not hold, because of the bound (which can indeed be satisfied
215 /// by `SomeUnsizedType` from another crate).
9fa01778
XL
216 //
217 // FIXME: when an `EvaluatedToRecur` goes past its parent root, we
218 // ought to convert it to an `EvaluatedToErr`, because we know
219 // there definitely isn't a proof tree for that obligation. Not
220 // doing so is still sound -- there isn't any proof tree, so the
221 // branch still can't be a part of a minimal one -- but does not re-enable caching.
3b2f2976 222 EvaluatedToRecur,
9fa01778 223 /// Evaluation failed.
92a42be0
SL
224 EvaluatedToErr,
225}
226
3b2f2976 227impl EvaluationResult {
9fa01778 228 /// Returns `true` if this evaluation result is known to apply, even
0731742a
XL
229 /// considering outlives constraints.
230 pub fn must_apply_considering_regions(self) -> bool {
231 self == EvaluatedToOk
232 }
233
9fa01778 234 /// Returns `true` if this evaluation result is known to apply, ignoring
0731742a
XL
235 /// outlives constraints.
236 pub fn must_apply_modulo_regions(self) -> bool {
237 self <= EvaluatedToOkModuloRegions
238 }
239
83c7162d 240 pub fn may_apply(self) -> bool {
3b2f2976 241 match self {
0731742a
XL
242 EvaluatedToOk | EvaluatedToOkModuloRegions | EvaluatedToAmbig | EvaluatedToUnknown => {
243 true
244 }
3b2f2976 245
0bf4aa26 246 EvaluatedToErr | EvaluatedToRecur => false,
3b2f2976
XL
247 }
248 }
249
74b04a01 250 pub fn is_stack_dependent(self) -> bool {
3b2f2976 251 match self {
0bf4aa26 252 EvaluatedToUnknown | EvaluatedToRecur => true,
3b2f2976 253
0731742a 254 EvaluatedToOk | EvaluatedToOkModuloRegions | EvaluatedToAmbig | EvaluatedToErr => false,
3b2f2976
XL
255 }
256 }
257}
258
83c7162d 259/// Indicates that trait evaluation caused overflow.
60c5eb7d 260#[derive(Copy, Clone, Debug, PartialEq, Eq, HashStable)]
83c7162d
XL
261pub struct OverflowError;
262
83c7162d
XL
263impl<'tcx> From<OverflowError> for SelectionError<'tcx> {
264 fn from(OverflowError: OverflowError) -> SelectionError<'tcx> {
265 SelectionError::Overflow
266 }
267}