]> git.lizzy.rs Git - rust.git/blob - compiler/rustc_middle/src/traits/select.rs
Auto merge of #87345 - Xanewok:update-rls, r=Mark-Simulacrum
[rust.git] / compiler / rustc_middle / src / traits / select.rs
1 //! Candidate selection. 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#selection
4
5 use self::EvaluationResult::*;
6
7 use super::{SelectionError, SelectionResult};
8
9 use crate::ty;
10
11 use rustc_hir::def_id::DefId;
12 use rustc_query_system::cache::Cache;
13
14 pub type SelectionCache<'tcx> = Cache<
15     ty::ParamEnvAnd<'tcx, ty::TraitRef<'tcx>>,
16     SelectionResult<'tcx, SelectionCandidate<'tcx>>,
17 >;
18
19 pub type EvaluationCache<'tcx> =
20     Cache<ty::ParamEnvAnd<'tcx, ty::PolyTraitRef<'tcx>>, EvaluationResult>;
21
22 /// The selection process begins by considering all impls, where
23 /// clauses, and so forth that might resolve an obligation. Sometimes
24 /// we'll be able to say definitively that (e.g.) an impl does not
25 /// apply to the obligation: perhaps it is defined for `usize` but the
26 /// obligation is for `i32`. In that case, we drop the impl out of the
27 /// list. But the other cases are considered *candidates*.
28 ///
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.
33 ///
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
38 /// "type annotations needed" error.
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 ///
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 /// ```
54 ///
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`.
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 ///
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 } }
77 ///
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 /// ```
83 ///
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`,
86 /// so the program prints "false". However, if the where-clause is omitted,
87 /// the blanket impl is selected, we unify `$0=()`, and the program prints
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
94 /// present), and we just pick the where-clause. This is, for example,
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.
98 #[derive(PartialEq, Eq, Debug, Clone, TypeFoldable)]
99 pub enum SelectionCandidate<'tcx> {
100     BuiltinCandidate {
101         /// `false` if there are no *further* obligations.
102         has_nested: bool,
103     },
104     ParamCandidate(ty::ConstnessAnd<ty::PolyTraitRef<'tcx>>),
105     ImplCandidate(DefId),
106     AutoImplCandidate(DefId),
107
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),
112
113     /// Implementation of a `Fn`-family trait by one of the anonymous types
114     /// generated for a `||` expression.
115     ClosureCandidate,
116
117     /// Implementation of a `Generator` trait by one of the anonymous types
118     /// generated for a generator.
119     GeneratorCandidate,
120
121     /// Implementation of a `Fn`-family trait by one of the anonymous
122     /// types generated for a fn pointer type (e.g., `fn(int) -> int`)
123     FnPointerCandidate,
124
125     /// Builtin implementation of `DiscriminantKind`.
126     DiscriminantKindCandidate,
127
128     /// Builtin implementation of `Pointee`.
129     PointeeCandidate,
130
131     TraitAliasCandidate(DefId),
132
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),
137
138     BuiltinObjectCandidate,
139
140     BuiltinUnsizeCandidate,
141 }
142
143 /// The result of trait evaluation. The order is important
144 /// here as the evaluation of a list is the maximum of the
145 /// evaluations.
146 ///
147 /// The evaluation results are ordered:
148 ///     - `EvaluatedToOk` implies `EvaluatedToOkModuloRegions`
149 ///       implies `EvaluatedToAmbig` implies `EvaluatedToUnknown`
150 ///     - `EvaluatedToErr` implies `EvaluatedToRecur`
151 ///     - the "union" of evaluation results is equal to their maximum -
152 ///     all the "potential success" candidates can potentially succeed,
153 ///     so they are noops when unioned with a definite error, and within
154 ///     the categories it's easy to see that the unions are correct.
155 #[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq, HashStable)]
156 pub enum EvaluationResult {
157     /// Evaluation successful.
158     EvaluatedToOk,
159     /// Evaluation successful, but there were unevaluated region obligations.
160     EvaluatedToOkModuloRegions,
161     /// Evaluation is known to be ambiguous -- it *might* hold for some
162     /// assignment of inference variables, but it might not.
163     ///
164     /// While this has the same meaning as `EvaluatedToUnknown` -- we can't
165     /// know whether this obligation holds or not -- it is the result we
166     /// would get with an empty stack, and therefore is cacheable.
167     EvaluatedToAmbig,
168     /// Evaluation failed because of recursion involving inference
169     /// variables. We are somewhat imprecise there, so we don't actually
170     /// know the real result.
171     ///
172     /// This can't be trivially cached for the same reason as `EvaluatedToRecur`.
173     EvaluatedToUnknown,
174     /// Evaluation failed because we encountered an obligation we are already
175     /// trying to prove on this branch.
176     ///
177     /// We know this branch can't be a part of a minimal proof-tree for
178     /// the "root" of our cycle, because then we could cut out the recursion
179     /// and maintain a valid proof tree. However, this does not mean
180     /// that all the obligations on this branch do not hold -- it's possible
181     /// that we entered this branch "speculatively", and that there
182     /// might be some other way to prove this obligation that does not
183     /// go through this cycle -- so we can't cache this as a failure.
184     ///
185     /// For example, suppose we have this:
186     ///
187     /// ```rust,ignore (pseudo-Rust)
188     /// pub trait Trait { fn xyz(); }
189     /// // This impl is "useless", but we can still have
190     /// // an `impl Trait for SomeUnsizedType` somewhere.
191     /// impl<T: Trait + Sized> Trait for T { fn xyz() {} }
192     ///
193     /// pub fn foo<T: Trait + ?Sized>() {
194     ///     <T as Trait>::xyz();
195     /// }
196     /// ```
197     ///
198     /// When checking `foo`, we have to prove `T: Trait`. This basically
199     /// translates into this:
200     ///
201     /// ```plain,ignore
202     /// (T: Trait + Sized →_\impl T: Trait), T: Trait ⊢ T: Trait
203     /// ```
204     ///
205     /// When we try to prove it, we first go the first option, which
206     /// recurses. This shows us that the impl is "useless" -- it won't
207     /// tell us that `T: Trait` unless it already implemented `Trait`
208     /// by some other means. However, that does not prevent `T: Trait`
209     /// does not hold, because of the bound (which can indeed be satisfied
210     /// by `SomeUnsizedType` from another crate).
211     //
212     // FIXME: when an `EvaluatedToRecur` goes past its parent root, we
213     // ought to convert it to an `EvaluatedToErr`, because we know
214     // there definitely isn't a proof tree for that obligation. Not
215     // doing so is still sound -- there isn't any proof tree, so the
216     // branch still can't be a part of a minimal one -- but does not re-enable caching.
217     EvaluatedToRecur,
218     /// Evaluation failed.
219     EvaluatedToErr,
220 }
221
222 impl EvaluationResult {
223     /// Returns `true` if this evaluation result is known to apply, even
224     /// considering outlives constraints.
225     pub fn must_apply_considering_regions(self) -> bool {
226         self == EvaluatedToOk
227     }
228
229     /// Returns `true` if this evaluation result is known to apply, ignoring
230     /// outlives constraints.
231     pub fn must_apply_modulo_regions(self) -> bool {
232         self <= EvaluatedToOkModuloRegions
233     }
234
235     pub fn may_apply(self) -> bool {
236         match self {
237             EvaluatedToOk | EvaluatedToOkModuloRegions | EvaluatedToAmbig | EvaluatedToUnknown => {
238                 true
239             }
240
241             EvaluatedToErr | EvaluatedToRecur => false,
242         }
243     }
244
245     pub fn is_stack_dependent(self) -> bool {
246         match self {
247             EvaluatedToUnknown | EvaluatedToRecur => true,
248
249             EvaluatedToOk | EvaluatedToOkModuloRegions | EvaluatedToAmbig | EvaluatedToErr => false,
250         }
251     }
252 }
253
254 /// Indicates that trait evaluation caused overflow.
255 #[derive(Copy, Clone, Debug, PartialEq, Eq, HashStable)]
256 pub struct OverflowError;
257
258 impl<'tcx> From<OverflowError> for SelectionError<'tcx> {
259     fn from(OverflowError: OverflowError) -> SelectionError<'tcx> {
260         SelectionError::Overflow
261     }
262 }