hir_ty/next_solver/infer/canonical/
instantiate.rs

1//! This module contains code to instantiate new values into a
2//! `Canonical<'db, T>`.
3//!
4//! For an overview of what canonicalization is and how it fits into
5//! rustc, check out the [chapter in the rustc dev guide][c].
6//!
7//! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html
8
9use std::{fmt::Debug, iter};
10
11use crate::next_solver::{
12    BoundConst, BoundRegion, BoundTy, Canonical, CanonicalVarKind, CanonicalVarValues, Clauses,
13    Const, ConstKind, DbInterner, GenericArg, ParamEnv, Predicate, Region, RegionKind, Ty, TyKind,
14    fold::FnMutDelegate,
15    infer::{
16        InferCtxt, InferOk, InferResult,
17        canonical::{QueryRegionConstraints, QueryResponse, canonicalizer::OriginalQueryValues},
18        opaque_types::table::OpaqueTypeStorageEntries,
19        traits::{ObligationCause, PredicateObligations},
20    },
21};
22use rustc_hash::FxHashMap;
23use rustc_index::{Idx as _, IndexVec};
24use rustc_type_ir::{
25    BoundVar, BoundVarIndexKind, GenericArgKind, TypeFlags, TypeFoldable, TypeFolder,
26    TypeSuperFoldable, TypeVisitableExt, UniverseIndex,
27    inherent::{GenericArg as _, IntoKind},
28};
29use tracing::{debug, instrument};
30
31pub trait CanonicalExt<'db, V> {
32    fn instantiate(&self, tcx: DbInterner<'db>, var_values: &CanonicalVarValues<'db>) -> V
33    where
34        V: TypeFoldable<DbInterner<'db>>;
35    fn instantiate_projected<T>(
36        &self,
37        tcx: DbInterner<'db>,
38        var_values: &CanonicalVarValues<'db>,
39        projection_fn: impl FnOnce(&V) -> T,
40    ) -> T
41    where
42        T: TypeFoldable<DbInterner<'db>>;
43}
44
45/// FIXME(-Znext-solver): This or public because it is shared with the
46/// new trait solver implementation. We should deduplicate canonicalization.
47impl<'db, V> CanonicalExt<'db, V> for Canonical<'db, V> {
48    /// Instantiate the wrapped value, replacing each canonical value
49    /// with the value given in `var_values`.
50    fn instantiate(&self, tcx: DbInterner<'db>, var_values: &CanonicalVarValues<'db>) -> V
51    where
52        V: TypeFoldable<DbInterner<'db>>,
53    {
54        self.instantiate_projected(tcx, var_values, |value| value.clone())
55    }
56
57    /// Allows one to apply a instantiation to some subset of
58    /// `self.value`. Invoke `projection_fn` with `self.value` to get
59    /// a value V that is expressed in terms of the same canonical
60    /// variables bound in `self` (usually this extracts from subset
61    /// of `self`). Apply the instantiation `var_values` to this value
62    /// V, replacing each of the canonical variables.
63    fn instantiate_projected<T>(
64        &self,
65        tcx: DbInterner<'db>,
66        var_values: &CanonicalVarValues<'db>,
67        projection_fn: impl FnOnce(&V) -> T,
68    ) -> T
69    where
70        T: TypeFoldable<DbInterner<'db>>,
71    {
72        assert_eq!(self.var_kinds.len(), var_values.len());
73        let value = projection_fn(&self.value);
74        instantiate_value(tcx, var_values, value)
75    }
76}
77
78/// Instantiate the values from `var_values` into `value`. `var_values`
79/// must be values for the set of canonical variables that appear in
80/// `value`.
81pub(super) fn instantiate_value<'db, T>(
82    tcx: DbInterner<'db>,
83    var_values: &CanonicalVarValues<'db>,
84    value: T,
85) -> T
86where
87    T: TypeFoldable<DbInterner<'db>>,
88{
89    if var_values.var_values.is_empty() {
90        value
91    } else {
92        let delegate = FnMutDelegate {
93            regions: &mut |br: BoundRegion<'db>| match var_values[br.var].kind() {
94                GenericArgKind::Lifetime(l) => l,
95                r => panic!("{br:?} is a region but value is {r:?}"),
96            },
97            types: &mut |bound_ty: BoundTy<'db>| match var_values[bound_ty.var].kind() {
98                GenericArgKind::Type(ty) => ty,
99                r => panic!("{bound_ty:?} is a type but value is {r:?}"),
100            },
101            consts: &mut |bound_ct: BoundConst<'db>| match var_values[bound_ct.var].kind() {
102                GenericArgKind::Const(ct) => ct,
103                c => panic!("{bound_ct:?} is a const but value is {c:?}"),
104            },
105        };
106
107        let value = tcx.replace_escaping_bound_vars_uncached(value, delegate);
108        value.fold_with(&mut CanonicalInstantiator {
109            tcx,
110            var_values: var_values.var_values.as_slice(),
111            cache: Default::default(),
112        })
113    }
114}
115
116/// Replaces the bound vars in a canonical binder with var values.
117struct CanonicalInstantiator<'db, 'a> {
118    tcx: DbInterner<'db>,
119
120    // The values that the bound vars are being instantiated with.
121    var_values: &'a [GenericArg<'db>],
122
123    // Because we use `BoundVarIndexKind::Canonical`, we can cache
124    // based only on the entire ty, not worrying about a `DebruijnIndex`
125    cache: FxHashMap<Ty<'db>, Ty<'db>>,
126}
127
128impl<'db, 'a> TypeFolder<DbInterner<'db>> for CanonicalInstantiator<'db, 'a> {
129    fn cx(&self) -> DbInterner<'db> {
130        self.tcx
131    }
132
133    fn fold_ty(&mut self, t: Ty<'db>) -> Ty<'db> {
134        match t.kind() {
135            TyKind::Bound(BoundVarIndexKind::Canonical, bound_ty) => {
136                self.var_values[bound_ty.var.as_usize()].expect_ty()
137            }
138            _ => {
139                if !t.has_type_flags(TypeFlags::HAS_CANONICAL_BOUND) {
140                    t
141                } else if let Some(&t) = self.cache.get(&t) {
142                    t
143                } else {
144                    let res = t.super_fold_with(self);
145                    assert!(self.cache.insert(t, res).is_none());
146                    res
147                }
148            }
149        }
150    }
151
152    fn fold_region(&mut self, r: Region<'db>) -> Region<'db> {
153        match r.kind() {
154            RegionKind::ReBound(BoundVarIndexKind::Canonical, br) => {
155                self.var_values[br.var.as_usize()].expect_region()
156            }
157            _ => r,
158        }
159    }
160
161    fn fold_const(&mut self, ct: Const<'db>) -> Const<'db> {
162        match ct.kind() {
163            ConstKind::Bound(BoundVarIndexKind::Canonical, bound_const) => {
164                self.var_values[bound_const.var.as_usize()].expect_const()
165            }
166            _ => ct.super_fold_with(self),
167        }
168    }
169
170    fn fold_predicate(&mut self, p: Predicate<'db>) -> Predicate<'db> {
171        if p.has_type_flags(TypeFlags::HAS_CANONICAL_BOUND) { p.super_fold_with(self) } else { p }
172    }
173
174    fn fold_clauses(&mut self, c: Clauses<'db>) -> Clauses<'db> {
175        if !c.has_type_flags(TypeFlags::HAS_CANONICAL_BOUND) {
176            return c;
177        }
178
179        // FIXME: We might need cache here for perf like rustc
180        c.super_fold_with(self)
181    }
182}
183
184impl<'db> InferCtxt<'db> {
185    /// A version of `make_canonicalized_query_response` that does
186    /// not pack in obligations, for contexts that want to drop
187    /// pending obligations instead of treating them as an ambiguity (e.g.
188    /// typeck "probing" contexts).
189    ///
190    /// If you DO want to keep track of pending obligations (which
191    /// include all region obligations, so this includes all cases
192    /// that care about regions) with this function, you have to
193    /// do it yourself, by e.g., having them be a part of the answer.
194    pub fn make_query_response_ignoring_pending_obligations<T>(
195        &self,
196        inference_vars: CanonicalVarValues<'db>,
197        answer: T,
198        prev_entries: OpaqueTypeStorageEntries,
199    ) -> Canonical<'db, QueryResponse<'db, T>>
200    where
201        T: TypeFoldable<DbInterner<'db>>,
202    {
203        // While we ignore region constraints and pending obligations,
204        // we do return constrained opaque types to avoid unconstrained
205        // inference variables in the response. This is important as we want
206        // to check that opaques in deref steps stay unconstrained.
207        //
208        // This doesn't handle the more general case for non-opaques as
209        // ambiguous `Projection` obligations have same the issue.
210        let opaque_types = self
211            .inner
212            .borrow_mut()
213            .opaque_type_storage
214            .opaque_types_added_since(prev_entries)
215            .map(|(k, v)| (k, v.ty))
216            .collect();
217
218        self.canonicalize_response(QueryResponse {
219            var_values: inference_vars,
220            region_constraints: QueryRegionConstraints::default(),
221            opaque_types,
222            value: answer,
223        })
224    }
225
226    /// Given the (canonicalized) result to a canonical query,
227    /// instantiates the result so it can be used, plugging in the
228    /// values from the canonical query. (Note that the result may
229    /// have been ambiguous; you should check the certainty level of
230    /// the query before applying this function.)
231    ///
232    /// To get a good understanding of what is happening here, check
233    /// out the [chapter in the rustc dev guide][c].
234    ///
235    /// [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html#processing-the-canonicalized-query-result
236    pub fn instantiate_query_response_and_region_obligations<R>(
237        &self,
238        cause: &ObligationCause,
239        param_env: ParamEnv<'db>,
240        original_values: &OriginalQueryValues<'db>,
241        query_response: &Canonical<'db, QueryResponse<'db, R>>,
242    ) -> InferResult<'db, R>
243    where
244        R: TypeFoldable<DbInterner<'db>>,
245    {
246        let InferOk { value: result_args, obligations } =
247            self.query_response_instantiation(cause, param_env, original_values, query_response)?;
248
249        for predicate in &query_response.value.region_constraints.outlives {
250            let predicate = instantiate_value(self.interner, &result_args, *predicate);
251            self.register_outlives_constraint(predicate);
252        }
253
254        for assumption in &query_response.value.region_constraints.assumptions {
255            let assumption = instantiate_value(self.interner, &result_args, *assumption);
256            self.register_region_assumption(assumption);
257        }
258
259        let user_result: R =
260            query_response
261                .instantiate_projected(self.interner, &result_args, |q_r| q_r.value.clone());
262
263        Ok(InferOk { value: user_result, obligations })
264    }
265
266    /// Given the original values and the (canonicalized) result from
267    /// computing a query, returns an instantiation that can be applied
268    /// to the query result to convert the result back into the
269    /// original namespace.
270    ///
271    /// The instantiation also comes accompanied with subobligations
272    /// that arose from unification; these might occur if (for
273    /// example) we are doing lazy normalization and the value
274    /// assigned to a type variable is unified with an unnormalized
275    /// projection.
276    fn query_response_instantiation<R>(
277        &self,
278        cause: &ObligationCause,
279        param_env: ParamEnv<'db>,
280        original_values: &OriginalQueryValues<'db>,
281        query_response: &Canonical<'db, QueryResponse<'db, R>>,
282    ) -> InferResult<'db, CanonicalVarValues<'db>>
283    where
284        R: Debug + TypeFoldable<DbInterner<'db>>,
285    {
286        debug!(
287            "query_response_instantiation(original_values={:#?}, query_response={:#?})",
288            original_values, query_response,
289        );
290
291        let mut value = self.query_response_instantiation_guess(
292            cause,
293            param_env,
294            original_values,
295            query_response,
296        )?;
297
298        value.obligations.extend(
299            self.unify_query_response_instantiation_guess(
300                cause,
301                param_env,
302                original_values,
303                &value.value,
304                query_response,
305            )?
306            .into_obligations(),
307        );
308
309        Ok(value)
310    }
311
312    /// Given the original values and the (canonicalized) result from
313    /// computing a query, returns a **guess** at an instantiation that
314    /// can be applied to the query result to convert the result back
315    /// into the original namespace. This is called a **guess**
316    /// because it uses a quick heuristic to find the values for each
317    /// canonical variable; if that quick heuristic fails, then we
318    /// will instantiate fresh inference variables for each canonical
319    /// variable instead. Therefore, the result of this method must be
320    /// properly unified
321    #[instrument(level = "debug", skip(self, param_env))]
322    fn query_response_instantiation_guess<R>(
323        &self,
324        cause: &ObligationCause,
325        param_env: ParamEnv<'db>,
326        original_values: &OriginalQueryValues<'db>,
327        query_response: &Canonical<'db, QueryResponse<'db, R>>,
328    ) -> InferResult<'db, CanonicalVarValues<'db>>
329    where
330        R: Debug + TypeFoldable<DbInterner<'db>>,
331    {
332        // For each new universe created in the query result that did
333        // not appear in the original query, create a local
334        // superuniverse.
335        let mut universe_map = original_values.universe_map.clone();
336        let num_universes_in_query = original_values.universe_map.len();
337        let num_universes_in_response = query_response.max_universe.as_usize() + 1;
338        for _ in num_universes_in_query..num_universes_in_response {
339            universe_map.push(self.create_next_universe());
340        }
341        assert!(!universe_map.is_empty()); // always have the root universe
342        assert_eq!(universe_map[UniverseIndex::ROOT.as_usize()], UniverseIndex::ROOT);
343
344        // Every canonical query result includes values for each of
345        // the inputs to the query. Therefore, we begin by unifying
346        // these values with the original inputs that were
347        // canonicalized.
348        let result_values = &query_response.value.var_values;
349        assert_eq!(original_values.var_values.len(), result_values.len());
350
351        // Quickly try to find initial values for the canonical
352        // variables in the result in terms of the query. We do this
353        // by iterating down the values that the query gave to each of
354        // the canonical inputs. If we find that one of those values
355        // is directly equal to one of the canonical variables in the
356        // result, then we can type the corresponding value from the
357        // input. See the example above.
358        let mut opt_values: IndexVec<BoundVar, Option<GenericArg<'db>>> =
359            IndexVec::from_elem_n(None, query_response.var_kinds.len());
360
361        for (original_value, result_value) in iter::zip(&original_values.var_values, result_values)
362        {
363            match result_value.kind() {
364                GenericArgKind::Type(result_value) => {
365                    // We disable the instantiation guess for inference variables
366                    // and only use it for placeholders. We need to handle the
367                    // `sub_root` of type inference variables which would make this
368                    // more involved. They are also a lot rarer than region variables.
369                    if let TyKind::Bound(index_kind, b) = result_value.kind()
370                        && !matches!(
371                            query_response.var_kinds.as_slice()[b.var.as_usize()],
372                            CanonicalVarKind::Ty { .. }
373                        )
374                    {
375                        // We only allow a `Canonical` index in generic parameters.
376                        assert!(matches!(index_kind, BoundVarIndexKind::Canonical));
377                        opt_values[b.var] = Some(*original_value);
378                    }
379                }
380                GenericArgKind::Lifetime(result_value) => {
381                    if let RegionKind::ReBound(index_kind, b) = result_value.kind() {
382                        // We only allow a `Canonical` index in generic parameters.
383                        assert!(matches!(index_kind, BoundVarIndexKind::Canonical));
384                        opt_values[b.var] = Some(*original_value);
385                    }
386                }
387                GenericArgKind::Const(result_value) => {
388                    if let ConstKind::Bound(index_kind, b) = result_value.kind() {
389                        // We only allow a `Canonical` index in generic parameters.
390                        assert!(matches!(index_kind, BoundVarIndexKind::Canonical));
391                        opt_values[b.var] = Some(*original_value);
392                    }
393                }
394            }
395        }
396
397        // Create result arguments: if we found a value for a
398        // given variable in the loop above, use that. Otherwise, use
399        // a fresh inference variable.
400        let interner = self.interner;
401        let variables = query_response.var_kinds;
402        let var_values =
403            CanonicalVarValues::instantiate(interner, variables, |var_values, kind| {
404                if kind.universe() != UniverseIndex::ROOT {
405                    // A variable from inside a binder of the query. While ideally these shouldn't
406                    // exist at all, we have to deal with them for now.
407                    self.instantiate_canonical_var(cause.span(), kind, var_values, |u| {
408                        universe_map[u.as_usize()]
409                    })
410                } else if kind.is_existential() {
411                    match opt_values[BoundVar::new(var_values.len())] {
412                        Some(k) => k,
413                        None => {
414                            self.instantiate_canonical_var(cause.span(), kind, var_values, |u| {
415                                universe_map[u.as_usize()]
416                            })
417                        }
418                    }
419                } else {
420                    // For placeholders which were already part of the input, we simply map this
421                    // universal bound variable back the placeholder of the input.
422                    opt_values[BoundVar::new(var_values.len())]
423                        .expect("expected placeholder to be unified with itself during response")
424                }
425            });
426
427        let mut obligations = PredicateObligations::new();
428
429        // Carry all newly resolved opaque types to the caller's scope
430        for &(a, b) in &query_response.value.opaque_types {
431            let a = instantiate_value(self.interner, &var_values, a);
432            let b = instantiate_value(self.interner, &var_values, b);
433            debug!(?a, ?b, "constrain opaque type");
434            // We use equate here instead of, for example, just registering the
435            // opaque type's hidden value directly, because the hidden type may have been an inference
436            // variable that got constrained to the opaque type itself. In that case we want to equate
437            // the generic args of the opaque with the generic params of its hidden type version.
438            obligations.extend(
439                self.at(cause, param_env)
440                    .eq(Ty::new_opaque(self.interner, a.def_id.0, a.args), b)?
441                    .obligations,
442            );
443        }
444
445        Ok(InferOk { value: var_values, obligations })
446    }
447
448    /// Given a "guess" at the values for the canonical variables in
449    /// the input, try to unify with the *actual* values found in the
450    /// query result. Often, but not always, this is a no-op, because
451    /// we already found the mapping in the "guessing" step.
452    ///
453    /// See also: [`Self::query_response_instantiation_guess`]
454    fn unify_query_response_instantiation_guess<R>(
455        &self,
456        cause: &ObligationCause,
457        param_env: ParamEnv<'db>,
458        original_values: &OriginalQueryValues<'db>,
459        result_args: &CanonicalVarValues<'db>,
460        query_response: &Canonical<'db, QueryResponse<'db, R>>,
461    ) -> InferResult<'db, ()>
462    where
463        R: Debug + TypeFoldable<DbInterner<'db>>,
464    {
465        // A closure that yields the result value for the given
466        // canonical variable; this is taken from
467        // `query_response.var_values` after applying the instantiation
468        // by `result_args`.
469        let instantiated_query_response = |index: BoundVar| -> GenericArg<'db> {
470            query_response
471                .instantiate_projected(self.interner, result_args, |v| v.var_values[index])
472        };
473
474        // Unify the original value for each variable with the value
475        // taken from `query_response` (after applying `result_args`).
476        self.unify_canonical_vars(cause, param_env, original_values, instantiated_query_response)
477    }
478
479    /// Given two sets of values for the same set of canonical variables, unify them.
480    /// The second set is produced lazily by supplying indices from the first set.
481    fn unify_canonical_vars(
482        &self,
483        cause: &ObligationCause,
484        param_env: ParamEnv<'db>,
485        variables1: &OriginalQueryValues<'db>,
486        variables2: impl Fn(BoundVar) -> GenericArg<'db>,
487    ) -> InferResult<'db, ()> {
488        let mut obligations = PredicateObligations::new();
489        for (index, value1) in variables1.var_values.iter().enumerate() {
490            let value2 = variables2(BoundVar::new(index));
491
492            match (value1.kind(), value2.kind()) {
493                (GenericArgKind::Type(v1), GenericArgKind::Type(v2)) => {
494                    obligations.extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations());
495                }
496                (GenericArgKind::Lifetime(re1), GenericArgKind::Lifetime(re2))
497                    if re1.is_erased() && re2.is_erased() =>
498                {
499                    // no action needed
500                }
501                (GenericArgKind::Lifetime(v1), GenericArgKind::Lifetime(v2)) => {
502                    self.inner.borrow_mut().unwrap_region_constraints().make_eqregion(v1, v2);
503                }
504                (GenericArgKind::Const(v1), GenericArgKind::Const(v2)) => {
505                    let ok = self.at(cause, param_env).eq(v1, v2)?;
506                    obligations.extend(ok.into_obligations());
507                }
508                _ => {
509                    panic!("kind mismatch, cannot unify {:?} and {:?}", value1, value2,);
510                }
511            }
512        }
513        Ok(InferOk { value: (), obligations })
514    }
515}
hir_ty/next_solver/infer/canonical/instantiate.rs

hir_ty/next_solver/infer/canonical/
instantiate.rs
