1 //! **Canonicalization** is the key to constructing a query in the
2 //! middle of type inference. Ordinarily, it is not possible to store
3 //! types from type inference in query keys, because they contain
4 //! references to inference variables whose lifetimes are too short
5 //! and so forth. Canonicalizing a value T1 using `canonicalize_query`
6 //! produces two things:
8 //! - a value T2 where each unbound inference variable has been
9 //! replaced with a **canonical variable**;
10 //! - a map M (of type `CanonicalVarValues`) from those canonical
11 //! variables back to the original.
13 //! We can then do queries using T2. These will give back constraints
14 //! on the canonical variables which can be translated, using the map
15 //! M, into constraints in our source context. This process of
16 //! translating the results back is done by the
17 //! `instantiate_query_result` method.
19 //! For a more detailed look at what is happening here, check
20 //! out the [chapter in the rustc dev guide][c].
22 //! [c]: https://rustc-dev-guide.rust-lang.org/traits/canonicalization.html
24 use crate::infer::MemberConstraint;
25 use crate::ty::subst::GenericArg;
26 use crate::ty::{self, BoundVar, List, Region, TyCtxt};
27 use rustc_index::vec::IndexVec;
28 use rustc_macros::HashStable;
29 use rustc_serialize::UseSpecializedDecodable;
30 use smallvec::SmallVec;
33 /// A "canonicalized" type `V` is one where all free inference
34 /// variables have been rewritten to "canonical vars". These are
35 /// numbered starting from 0 in order of first appearance.
36 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
37 #[derive(HashStable, TypeFoldable, Lift)]
38 pub struct Canonical<'tcx, V> {
39 pub max_universe: ty::UniverseIndex,
40 pub variables: CanonicalVarInfos<'tcx>,
44 pub type CanonicalVarInfos<'tcx> = &'tcx List<CanonicalVarInfo>;
46 impl<'tcx> UseSpecializedDecodable for CanonicalVarInfos<'tcx> {}
48 /// A set of values corresponding to the canonical variables from some
49 /// `Canonical`. You can give these values to
50 /// `canonical_value.substitute` to substitute them into the canonical
51 /// value at the right places.
53 /// When you canonicalize a value `V`, you get back one of these
54 /// vectors with the original values that were replaced by canonical
55 /// variables. You will need to supply it later to instantiate the
56 /// canonicalized query response.
57 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
58 #[derive(HashStable, TypeFoldable, Lift)]
59 pub struct CanonicalVarValues<'tcx> {
60 pub var_values: IndexVec<BoundVar, GenericArg<'tcx>>,
63 /// When we canonicalize a value to form a query, we wind up replacing
64 /// various parts of it with canonical variables. This struct stores
65 /// those replaced bits to remember for when we process the query
67 #[derive(Clone, Debug)]
68 pub struct OriginalQueryValues<'tcx> {
69 /// Map from the universes that appear in the query to the
70 /// universes in the caller context. For the time being, we only
71 /// ever put ROOT values into the query, so this map is very
73 pub universe_map: SmallVec<[ty::UniverseIndex; 4]>,
75 /// This is equivalent to `CanonicalVarValues`, but using a
76 /// `SmallVec` yields a significant performance win.
77 pub var_values: SmallVec<[GenericArg<'tcx>; 8]>,
80 impl Default for OriginalQueryValues<'tcx> {
81 fn default() -> Self {
82 let mut universe_map = SmallVec::default();
83 universe_map.push(ty::UniverseIndex::ROOT);
85 Self { universe_map, var_values: SmallVec::default() }
89 /// Information about a canonical variable that is included with the
90 /// canonical value. This is sufficient information for code to create
91 /// a copy of the canonical value in some other inference context,
92 /// with fresh inference variables replacing the canonical values.
93 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)]
94 pub struct CanonicalVarInfo {
95 pub kind: CanonicalVarKind,
98 impl CanonicalVarInfo {
99 pub fn universe(&self) -> ty::UniverseIndex {
103 pub fn is_existential(&self) -> bool {
105 CanonicalVarKind::Ty(_) => true,
106 CanonicalVarKind::PlaceholderTy(_) => false,
107 CanonicalVarKind::Region(_) => true,
108 CanonicalVarKind::PlaceholderRegion(..) => false,
109 CanonicalVarKind::Const(_) => true,
110 CanonicalVarKind::PlaceholderConst(_) => false,
115 /// Describes the "kind" of the canonical variable. This is a "kind"
116 /// in the type-theory sense of the term -- i.e., a "meta" type system
117 /// that analyzes type-like values.
118 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)]
119 pub enum CanonicalVarKind {
120 /// Some kind of type inference variable.
121 Ty(CanonicalTyVarKind),
123 /// A "placeholder" that represents "any type".
124 PlaceholderTy(ty::PlaceholderType),
126 /// Region variable `'?R`.
127 Region(ty::UniverseIndex),
129 /// A "placeholder" that represents "any region". Created when you
130 /// are solving a goal like `for<'a> T: Foo<'a>` to represent the
131 /// bound region `'a`.
132 PlaceholderRegion(ty::PlaceholderRegion),
134 /// Some kind of const inference variable.
135 Const(ty::UniverseIndex),
137 /// A "placeholder" that represents "any const".
138 PlaceholderConst(ty::PlaceholderConst),
141 impl CanonicalVarKind {
142 pub fn universe(self) -> ty::UniverseIndex {
144 CanonicalVarKind::Ty(kind) => match kind {
145 CanonicalTyVarKind::General(ui) => ui,
146 CanonicalTyVarKind::Float | CanonicalTyVarKind::Int => ty::UniverseIndex::ROOT,
149 CanonicalVarKind::PlaceholderTy(placeholder) => placeholder.universe,
150 CanonicalVarKind::Region(ui) => ui,
151 CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.universe,
152 CanonicalVarKind::Const(ui) => ui,
153 CanonicalVarKind::PlaceholderConst(placeholder) => placeholder.universe,
158 /// Rust actually has more than one category of type variables;
159 /// notably, the type variables we create for literals (e.g., 22 or
160 /// 22.) can only be instantiated with integral/float types (e.g.,
161 /// usize or f32). In order to faithfully reproduce a type, we need to
162 /// know what set of types a given type variable can be unified with.
163 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)]
164 pub enum CanonicalTyVarKind {
165 /// General type variable `?T` that can be unified with arbitrary types.
166 General(ty::UniverseIndex),
168 /// Integral type variable `?I` (that can only be unified with integral types).
171 /// Floating-point type variable `?F` (that can only be unified with float types).
175 /// After we execute a query with a canonicalized key, we get back a
176 /// `Canonical<QueryResponse<..>>`. You can use
177 /// `instantiate_query_result` to access the data in this result.
178 #[derive(Clone, Debug, HashStable, TypeFoldable, Lift)]
179 pub struct QueryResponse<'tcx, R> {
180 pub var_values: CanonicalVarValues<'tcx>,
181 pub region_constraints: QueryRegionConstraints<'tcx>,
182 pub certainty: Certainty,
186 #[derive(Clone, Debug, Default, HashStable, TypeFoldable, Lift)]
187 pub struct QueryRegionConstraints<'tcx> {
188 pub outlives: Vec<QueryOutlivesConstraint<'tcx>>,
189 pub member_constraints: Vec<MemberConstraint<'tcx>>,
192 impl QueryRegionConstraints<'_> {
193 /// Represents an empty (trivially true) set of region
195 pub fn is_empty(&self) -> bool {
196 self.outlives.is_empty() && self.member_constraints.is_empty()
200 pub type Canonicalized<'tcx, V> = Canonical<'tcx, V>;
202 pub type CanonicalizedQueryResponse<'tcx, T> = &'tcx Canonical<'tcx, QueryResponse<'tcx, T>>;
204 /// Indicates whether or not we were able to prove the query to be
206 #[derive(Copy, Clone, Debug, HashStable)]
208 /// The query is known to be true, presuming that you apply the
209 /// given `var_values` and the region-constraints are satisfied.
212 /// The query is not known to be true, but also not known to be
213 /// false. The `var_values` represent *either* values that must
214 /// hold in order for the query to be true, or helpful tips that
215 /// *might* make it true. Currently rustc's trait solver cannot
216 /// distinguish the two (e.g., due to our preference for where
217 /// clauses over impls).
219 /// After some unifiations and things have been done, it makes
220 /// sense to try and prove again -- of course, at that point, the
221 /// canonical form will be different, making this a distinct
227 pub fn is_proven(&self) -> bool {
229 Certainty::Proven => true,
230 Certainty::Ambiguous => false,
234 pub fn is_ambiguous(&self) -> bool {
239 impl<'tcx, R> QueryResponse<'tcx, R> {
240 pub fn is_proven(&self) -> bool {
241 self.certainty.is_proven()
244 pub fn is_ambiguous(&self) -> bool {
249 impl<'tcx, R> Canonical<'tcx, QueryResponse<'tcx, R>> {
250 pub fn is_proven(&self) -> bool {
251 self.value.is_proven()
254 pub fn is_ambiguous(&self) -> bool {
259 impl<'tcx, V> Canonical<'tcx, V> {
260 /// Allows you to map the `value` of a canonical while keeping the
261 /// same set of bound variables.
263 /// **WARNING:** This function is very easy to mis-use, hence the
264 /// name! In particular, the new value `W` must use all **the
265 /// same type/region variables** in **precisely the same order**
266 /// as the original! (The ordering is defined by the
267 /// `TypeFoldable` implementation of the type in question.)
269 /// An example of a **correct** use of this:
271 /// ```rust,ignore (not real code)
272 /// let a: Canonical<'_, T> = ...;
273 /// let b: Canonical<'_, (T,)> = a.unchecked_map(|v| (v, ));
276 /// An example of an **incorrect** use of this:
278 /// ```rust,ignore (not real code)
279 /// let a: Canonical<'tcx, T> = ...;
280 /// let ty: Ty<'tcx> = ...;
281 /// let b: Canonical<'tcx, (T, Ty<'tcx>)> = a.unchecked_map(|v| (v, ty));
283 pub fn unchecked_map<W>(self, map_op: impl FnOnce(V) -> W) -> Canonical<'tcx, W> {
284 let Canonical { max_universe, variables, value } = self;
285 Canonical { max_universe, variables, value: map_op(value) }
289 pub type QueryOutlivesConstraint<'tcx> =
290 ty::Binder<ty::OutlivesPredicate<GenericArg<'tcx>, Region<'tcx>>>;
292 CloneTypeFoldableAndLiftImpls! {
293 crate::infer::canonical::Certainty,
294 crate::infer::canonical::CanonicalVarInfo,
295 crate::infer::canonical::CanonicalVarKind,
298 CloneTypeFoldableImpls! {
300 crate::infer::canonical::CanonicalVarInfos<'tcx>,
304 impl<'tcx> CanonicalVarValues<'tcx> {
305 pub fn len(&self) -> usize {
306 self.var_values.len()
309 /// Makes an identity substitution from this one: each bound var
310 /// is matched to the same bound var, preserving the original kinds.
311 /// For example, if we have:
312 /// `self.var_values == [Type(u32), Lifetime('a), Type(u64)]`
313 /// we'll return a substitution `subst` with:
314 /// `subst.var_values == [Type(^0), Lifetime(^1), Type(^2)]`.
315 pub fn make_identity(&self, tcx: TyCtxt<'tcx>) -> Self {
316 use crate::ty::subst::GenericArgKind;
323 .map(|(kind, i)| match kind.unpack() {
324 GenericArgKind::Type(..) => {
325 tcx.mk_ty(ty::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i).into())).into()
327 GenericArgKind::Lifetime(..) => tcx
328 .mk_region(ty::ReLateBound(ty::INNERMOST, ty::BoundRegion::BrAnon(i)))
330 GenericArgKind::Const(ct) => tcx
331 .mk_const(ty::Const {
333 val: ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i)),
342 impl<'a, 'tcx> IntoIterator for &'a CanonicalVarValues<'tcx> {
343 type Item = GenericArg<'tcx>;
344 type IntoIter = ::std::iter::Cloned<::std::slice::Iter<'a, GenericArg<'tcx>>>;
346 fn into_iter(self) -> Self::IntoIter {
347 self.var_values.iter().cloned()
351 impl<'tcx> Index<BoundVar> for CanonicalVarValues<'tcx> {
352 type Output = GenericArg<'tcx>;
354 fn index(&self, value: BoundVar) -> &GenericArg<'tcx> {
355 &self.var_values[value]