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://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html
24 use crate::infer::MemberConstraint;
25 use crate::mir::ConstraintCategory;
26 use crate::ty::subst::GenericArg;
27 use crate::ty::{self, BoundVar, List, Region, Ty, TyCtxt};
28 use rustc_macros::HashStable;
29 use smallvec::SmallVec;
32 /// A "canonicalized" type `V` is one where all free inference
33 /// variables have been rewritten to "canonical vars". These are
34 /// numbered starting from 0 in order of first appearance.
35 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable)]
36 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
37 pub struct Canonical<'tcx, V> {
38 pub max_universe: ty::UniverseIndex,
39 pub variables: CanonicalVarInfos<'tcx>,
43 pub type CanonicalVarInfos<'tcx> = &'tcx List<CanonicalVarInfo<'tcx>>;
45 impl<'tcx> ty::TypeFoldable<'tcx> for CanonicalVarInfos<'tcx> {
46 fn try_fold_with<F: ty::FallibleTypeFolder<'tcx>>(
49 ) -> Result<Self, F::Error> {
50 ty::util::fold_list(self, folder, |tcx, v| tcx.intern_canonical_var_infos(v))
54 /// A set of values corresponding to the canonical variables from some
55 /// `Canonical`. You can give these values to
56 /// `canonical_value.substitute` to substitute them into the canonical
57 /// value at the right places.
59 /// When you canonicalize a value `V`, you get back one of these
60 /// vectors with the original values that were replaced by canonical
61 /// variables. You will need to supply it later to instantiate the
62 /// canonicalized query response.
63 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable)]
64 #[derive(HashStable, TypeFoldable, TypeVisitable, Lift)]
65 pub struct CanonicalVarValues<'tcx> {
66 pub var_values: ty::SubstsRef<'tcx>,
69 impl CanonicalVarValues<'_> {
70 pub fn is_identity(&self) -> bool {
71 self.var_values.iter().enumerate().all(|(bv, arg)| match arg.unpack() {
72 ty::GenericArgKind::Lifetime(r) => {
73 matches!(*r, ty::ReLateBound(ty::INNERMOST, br) if br.var.as_usize() == bv)
75 ty::GenericArgKind::Type(ty) => {
76 matches!(*ty.kind(), ty::Bound(ty::INNERMOST, bt) if bt.var.as_usize() == bv)
78 ty::GenericArgKind::Const(ct) => {
79 matches!(ct.kind(), ty::ConstKind::Bound(ty::INNERMOST, bc) if bc.as_usize() == bv)
85 /// When we canonicalize a value to form a query, we wind up replacing
86 /// various parts of it with canonical variables. This struct stores
87 /// those replaced bits to remember for when we process the query
89 #[derive(Clone, Debug)]
90 pub struct OriginalQueryValues<'tcx> {
91 /// Map from the universes that appear in the query to the universes in the
92 /// caller context. For all queries except `evaluate_goal` (used by Chalk),
93 /// we only ever put ROOT values into the query, so this map is very
95 pub universe_map: SmallVec<[ty::UniverseIndex; 4]>,
97 /// This is equivalent to `CanonicalVarValues`, but using a
98 /// `SmallVec` yields a significant performance win.
99 pub var_values: SmallVec<[GenericArg<'tcx>; 8]>,
102 impl<'tcx> Default for OriginalQueryValues<'tcx> {
103 fn default() -> Self {
104 let mut universe_map = SmallVec::default();
105 universe_map.push(ty::UniverseIndex::ROOT);
107 Self { universe_map, var_values: SmallVec::default() }
111 /// Information about a canonical variable that is included with the
112 /// canonical value. This is sufficient information for code to create
113 /// a copy of the canonical value in some other inference context,
114 /// with fresh inference variables replacing the canonical values.
115 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable, HashStable)]
116 #[derive(TypeFoldable, TypeVisitable)]
117 pub struct CanonicalVarInfo<'tcx> {
118 pub kind: CanonicalVarKind<'tcx>,
121 impl<'tcx> CanonicalVarInfo<'tcx> {
122 pub fn universe(&self) -> ty::UniverseIndex {
126 pub fn is_existential(&self) -> bool {
128 CanonicalVarKind::Ty(_) => true,
129 CanonicalVarKind::PlaceholderTy(_) => false,
130 CanonicalVarKind::Region(_) => true,
131 CanonicalVarKind::PlaceholderRegion(..) => false,
132 CanonicalVarKind::Const(..) => true,
133 CanonicalVarKind::PlaceholderConst(_, _) => false,
138 /// Describes the "kind" of the canonical variable. This is a "kind"
139 /// in the type-theory sense of the term -- i.e., a "meta" type system
140 /// that analyzes type-like values.
141 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable, HashStable)]
142 #[derive(TypeFoldable, TypeVisitable)]
143 pub enum CanonicalVarKind<'tcx> {
144 /// Some kind of type inference variable.
145 Ty(CanonicalTyVarKind),
147 /// A "placeholder" that represents "any type".
148 PlaceholderTy(ty::PlaceholderType),
150 /// Region variable `'?R`.
151 Region(ty::UniverseIndex),
153 /// A "placeholder" that represents "any region". Created when you
154 /// are solving a goal like `for<'a> T: Foo<'a>` to represent the
155 /// bound region `'a`.
156 PlaceholderRegion(ty::PlaceholderRegion),
158 /// Some kind of const inference variable.
159 Const(ty::UniverseIndex, Ty<'tcx>),
161 /// A "placeholder" that represents "any const".
162 PlaceholderConst(ty::PlaceholderConst<'tcx>, Ty<'tcx>),
165 impl<'tcx> CanonicalVarKind<'tcx> {
166 pub fn universe(self) -> ty::UniverseIndex {
168 CanonicalVarKind::Ty(kind) => match kind {
169 CanonicalTyVarKind::General(ui) => ui,
170 CanonicalTyVarKind::Float | CanonicalTyVarKind::Int => ty::UniverseIndex::ROOT,
173 CanonicalVarKind::PlaceholderTy(placeholder) => placeholder.universe,
174 CanonicalVarKind::Region(ui) => ui,
175 CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.universe,
176 CanonicalVarKind::Const(ui, _) => ui,
177 CanonicalVarKind::PlaceholderConst(placeholder, _) => placeholder.universe,
182 /// Rust actually has more than one category of type variables;
183 /// notably, the type variables we create for literals (e.g., 22 or
184 /// 22.) can only be instantiated with integral/float types (e.g.,
185 /// usize or f32). In order to faithfully reproduce a type, we need to
186 /// know what set of types a given type variable can be unified with.
187 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable, HashStable)]
188 pub enum CanonicalTyVarKind {
189 /// General type variable `?T` that can be unified with arbitrary types.
190 General(ty::UniverseIndex),
192 /// Integral type variable `?I` (that can only be unified with integral types).
195 /// Floating-point type variable `?F` (that can only be unified with float types).
199 /// After we execute a query with a canonicalized key, we get back a
200 /// `Canonical<QueryResponse<..>>`. You can use
201 /// `instantiate_query_result` to access the data in this result.
202 #[derive(Clone, Debug, HashStable, TypeFoldable, TypeVisitable, Lift)]
203 pub struct QueryResponse<'tcx, R> {
204 pub var_values: CanonicalVarValues<'tcx>,
205 pub region_constraints: QueryRegionConstraints<'tcx>,
206 pub certainty: Certainty,
207 /// List of opaque types which we tried to compare to another type.
208 /// Inside the query we don't know yet whether the opaque type actually
209 /// should get its hidden type inferred. So we bubble the opaque type
210 /// and the type it was compared against upwards and let the query caller
212 pub opaque_types: Vec<(Ty<'tcx>, Ty<'tcx>)>,
216 #[derive(Clone, Debug, Default, HashStable, TypeFoldable, TypeVisitable, Lift)]
217 pub struct QueryRegionConstraints<'tcx> {
218 pub outlives: Vec<QueryOutlivesConstraint<'tcx>>,
219 pub member_constraints: Vec<MemberConstraint<'tcx>>,
222 impl QueryRegionConstraints<'_> {
223 /// Represents an empty (trivially true) set of region
225 pub fn is_empty(&self) -> bool {
226 self.outlives.is_empty() && self.member_constraints.is_empty()
230 pub type CanonicalQueryResponse<'tcx, T> = &'tcx Canonical<'tcx, QueryResponse<'tcx, T>>;
232 /// Indicates whether or not we were able to prove the query to be
234 #[derive(Copy, Clone, Debug, HashStable)]
236 /// The query is known to be true, presuming that you apply the
237 /// given `var_values` and the region-constraints are satisfied.
240 /// The query is not known to be true, but also not known to be
241 /// false. The `var_values` represent *either* values that must
242 /// hold in order for the query to be true, or helpful tips that
243 /// *might* make it true. Currently rustc's trait solver cannot
244 /// distinguish the two (e.g., due to our preference for where
245 /// clauses over impls).
247 /// After some unification and things have been done, it makes
248 /// sense to try and prove again -- of course, at that point, the
249 /// canonical form will be different, making this a distinct
255 pub fn is_proven(&self) -> bool {
257 Certainty::Proven => true,
258 Certainty::Ambiguous => false,
263 impl<'tcx, R> QueryResponse<'tcx, R> {
264 pub fn is_proven(&self) -> bool {
265 self.certainty.is_proven()
269 impl<'tcx, R> Canonical<'tcx, QueryResponse<'tcx, R>> {
270 pub fn is_proven(&self) -> bool {
271 self.value.is_proven()
274 pub fn is_ambiguous(&self) -> bool {
279 impl<'tcx, R> Canonical<'tcx, ty::ParamEnvAnd<'tcx, R>> {
281 pub fn without_const(mut self) -> Self {
282 self.value = self.value.without_const();
287 impl<'tcx, V> Canonical<'tcx, V> {
288 /// Allows you to map the `value` of a canonical while keeping the
289 /// same set of bound variables.
291 /// **WARNING:** This function is very easy to mis-use, hence the
292 /// name! In particular, the new value `W` must use all **the
293 /// same type/region variables** in **precisely the same order**
294 /// as the original! (The ordering is defined by the
295 /// `TypeFoldable` implementation of the type in question.)
297 /// An example of a **correct** use of this:
299 /// ```rust,ignore (not real code)
300 /// let a: Canonical<'_, T> = ...;
301 /// let b: Canonical<'_, (T,)> = a.unchecked_map(|v| (v, ));
304 /// An example of an **incorrect** use of this:
306 /// ```rust,ignore (not real code)
307 /// let a: Canonical<'tcx, T> = ...;
308 /// let ty: Ty<'tcx> = ...;
309 /// let b: Canonical<'tcx, (T, Ty<'tcx>)> = a.unchecked_map(|v| (v, ty));
311 pub fn unchecked_map<W>(self, map_op: impl FnOnce(V) -> W) -> Canonical<'tcx, W> {
312 let Canonical { max_universe, variables, value } = self;
313 Canonical { max_universe, variables, value: map_op(value) }
316 /// Allows you to map the `value` of a canonical while keeping the same set of
319 /// **WARNING:** This function is very easy to mis-use, hence the name! See
320 /// the comment of [Canonical::unchecked_map] for more details.
321 pub fn unchecked_rebind<W>(self, value: W) -> Canonical<'tcx, W> {
322 let Canonical { max_universe, variables, value: _ } = self;
323 Canonical { max_universe, variables, value }
327 pub type QueryOutlivesConstraint<'tcx> = (
328 ty::Binder<'tcx, ty::OutlivesPredicate<GenericArg<'tcx>, Region<'tcx>>>,
329 ConstraintCategory<'tcx>,
332 TrivialTypeTraversalAndLiftImpls! {
334 crate::infer::canonical::Certainty,
335 crate::infer::canonical::CanonicalTyVarKind,
339 impl<'tcx> CanonicalVarValues<'tcx> {
340 /// Creates dummy var values which should not be used in a
341 /// canonical response.
342 pub fn dummy() -> CanonicalVarValues<'tcx> {
343 CanonicalVarValues { var_values: ty::List::empty() }
347 pub fn len(&self) -> usize {
348 self.var_values.len()
351 /// Makes an identity substitution from this one: each bound var
352 /// is matched to the same bound var, preserving the original kinds.
353 /// For example, if we have:
354 /// `self.var_values == [Type(u32), Lifetime('a), Type(u64)]`
355 /// we'll return a substitution `subst` with:
356 /// `subst.var_values == [Type(^0), Lifetime(^1), Type(^2)]`.
357 pub fn make_identity(&self, tcx: TyCtxt<'tcx>) -> Self {
358 use crate::ty::subst::GenericArgKind;
361 var_values: tcx.mk_substs(self.var_values.iter().enumerate().map(
362 |(i, kind)| -> ty::GenericArg<'tcx> {
363 match kind.unpack() {
364 GenericArgKind::Type(..) => tcx
365 .mk_ty(ty::Bound(ty::INNERMOST, ty::BoundVar::from_usize(i).into()))
367 GenericArgKind::Lifetime(..) => {
368 let br = ty::BoundRegion {
369 var: ty::BoundVar::from_usize(i),
370 kind: ty::BrAnon(i as u32, None),
372 tcx.mk_region(ty::ReLateBound(ty::INNERMOST, br)).into()
374 GenericArgKind::Const(ct) => tcx
376 ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from_usize(i)),
387 impl<'a, 'tcx> IntoIterator for &'a CanonicalVarValues<'tcx> {
388 type Item = GenericArg<'tcx>;
389 type IntoIter = ::std::iter::Copied<::std::slice::Iter<'a, GenericArg<'tcx>>>;
391 fn into_iter(self) -> Self::IntoIter {
392 self.var_values.iter()
396 impl<'tcx> Index<BoundVar> for CanonicalVarValues<'tcx> {
397 type Output = GenericArg<'tcx>;
399 fn index(&self, value: BoundVar) -> &GenericArg<'tcx> {
400 &self.var_values[value.as_usize()]