rustc_next_trait_solver/
canonicalizer.rs

1use rustc_type_ir::data_structures::{HashMap, ensure_sufficient_stack};
2use rustc_type_ir::inherent::*;
3use rustc_type_ir::solve::{Goal, QueryInput};
4use rustc_type_ir::{
5    self as ty, Canonical, CanonicalParamEnvCacheEntry, CanonicalTyVarKind, CanonicalVarKind,
6    Flags, InferCtxtLike, Interner, TypeFlags, TypeFoldable, TypeFolder, TypeSuperFoldable,
7    TypeVisitableExt,
8};
9
10use crate::delegate::SolverDelegate;
11
12/// Does this have infer/placeholder/param, free regions or ReErased?
13const NEEDS_CANONICAL: TypeFlags = TypeFlags::from_bits(
14    TypeFlags::HAS_INFER.bits()
15        | TypeFlags::HAS_PLACEHOLDER.bits()
16        | TypeFlags::HAS_PARAM.bits()
17        | TypeFlags::HAS_FREE_REGIONS.bits()
18        | TypeFlags::HAS_RE_ERASED.bits(),
19)
20.unwrap();
21
22#[derive(Debug, Clone, Copy)]
23enum CanonicalizeInputKind {
24    /// When canonicalizing the `param_env`, we keep `'static` as merging
25    /// trait candidates relies on it when deciding whether a where-bound
26    /// is trivial.
27    ParamEnv,
28    /// When canonicalizing predicates, we don't keep `'static`. If we're
29    /// currently outside of the trait solver and canonicalize the root goal
30    /// during HIR typeck, we replace each occurance of a region with a
31    /// unique region variable. See the comment on `InferCtxt::in_hir_typeck`
32    /// for more details.
33    Predicate { is_hir_typeck_root_goal: bool },
34}
35
36/// Whether we're canonicalizing a query input or the query response.
37///
38/// When canonicalizing an input we're in the context of the caller
39/// while canonicalizing the response happens in the context of the
40/// query.
41#[derive(Debug, Clone, Copy)]
42enum CanonicalizeMode {
43    Input(CanonicalizeInputKind),
44    /// FIXME: We currently return region constraints referring to
45    /// placeholders and inference variables from a binder instantiated
46    /// inside of the query.
47    ///
48    /// In the long term we should eagerly deal with these constraints
49    /// inside of the query and only propagate constraints which are
50    /// actually nameable by the caller.
51    Response {
52        /// The highest universe nameable by the caller.
53        ///
54        /// All variables in a universe nameable by the caller get mapped
55        /// to the root universe in the response and then mapped back to
56        /// their correct universe when applying the query response in the
57        /// context of the caller.
58        ///
59        /// This doesn't work for universes created inside of the query so
60        /// we do remember their universe in the response.
61        max_input_universe: ty::UniverseIndex,
62    },
63}
64
65pub struct Canonicalizer<'a, D: SolverDelegate<Interner = I>, I: Interner> {
66    delegate: &'a D,
67
68    // Immutable field.
69    canonicalize_mode: CanonicalizeMode,
70
71    // Mutable fields.
72    variables: &'a mut Vec<I::GenericArg>,
73    var_kinds: Vec<CanonicalVarKind<I>>,
74    variable_lookup_table: HashMap<I::GenericArg, usize>,
75    binder_index: ty::DebruijnIndex,
76
77    /// We only use the debruijn index during lookup. We don't need to
78    /// track the `variables` as each generic arg only results in a single
79    /// bound variable regardless of how many times it is encountered.
80    cache: HashMap<(ty::DebruijnIndex, I::Ty), I::Ty>,
81}
82
83impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> {
84    pub fn canonicalize_response<T: TypeFoldable<I>>(
85        delegate: &'a D,
86        max_input_universe: ty::UniverseIndex,
87        variables: &'a mut Vec<I::GenericArg>,
88        value: T,
89    ) -> ty::Canonical<I, T> {
90        let mut canonicalizer = Canonicalizer {
91            delegate,
92            canonicalize_mode: CanonicalizeMode::Response { max_input_universe },
93
94            variables,
95            variable_lookup_table: Default::default(),
96            var_kinds: Vec::new(),
97            binder_index: ty::INNERMOST,
98
99            cache: Default::default(),
100        };
101
102        let value = if value.has_type_flags(NEEDS_CANONICAL) {
103            value.fold_with(&mut canonicalizer)
104        } else {
105            value
106        };
107        debug_assert!(!value.has_infer(), "unexpected infer in {value:?}");
108        debug_assert!(!value.has_placeholders(), "unexpected placeholders in {value:?}");
109        let (max_universe, variables) = canonicalizer.finalize();
110        Canonical { max_universe, variables, value }
111    }
112
113    fn canonicalize_param_env(
114        delegate: &'a D,
115        variables: &'a mut Vec<I::GenericArg>,
116        param_env: I::ParamEnv,
117    ) -> (I::ParamEnv, HashMap<I::GenericArg, usize>, Vec<CanonicalVarKind<I>>) {
118        if !param_env.has_type_flags(NEEDS_CANONICAL) {
119            return (param_env, Default::default(), Vec::new());
120        }
121
122        // Check whether we can use the global cache for this param_env. As we only use
123        // the `param_env` itself as the cache key, considering any additional information
124        // durnig its canonicalization would be incorrect. We always canonicalize region
125        // inference variables in a separate universe, so these are fine. However, we do
126        // track the universe of type and const inference variables so these must not be
127        // globally cached. We don't rely on any additional information when canonicalizing
128        // placeholders.
129        if !param_env.has_non_region_infer() {
130            delegate.cx().canonical_param_env_cache_get_or_insert(
131                param_env,
132                || {
133                    let mut variables = Vec::new();
134                    let mut env_canonicalizer = Canonicalizer {
135                        delegate,
136                        canonicalize_mode: CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv),
137
138                        variables: &mut variables,
139                        variable_lookup_table: Default::default(),
140                        var_kinds: Vec::new(),
141                        binder_index: ty::INNERMOST,
142
143                        cache: Default::default(),
144                    };
145                    let param_env = param_env.fold_with(&mut env_canonicalizer);
146                    debug_assert_eq!(env_canonicalizer.binder_index, ty::INNERMOST);
147                    CanonicalParamEnvCacheEntry {
148                        param_env,
149                        variable_lookup_table: env_canonicalizer.variable_lookup_table,
150                        var_kinds: env_canonicalizer.var_kinds,
151                        variables,
152                    }
153                },
154                |&CanonicalParamEnvCacheEntry {
155                     param_env,
156                     variables: ref cache_variables,
157                     ref variable_lookup_table,
158                     ref var_kinds,
159                 }| {
160                    debug_assert!(variables.is_empty());
161                    variables.extend(cache_variables.iter().copied());
162                    (param_env, variable_lookup_table.clone(), var_kinds.clone())
163                },
164            )
165        } else {
166            let mut env_canonicalizer = Canonicalizer {
167                delegate,
168                canonicalize_mode: CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv),
169
170                variables,
171                variable_lookup_table: Default::default(),
172                var_kinds: Vec::new(),
173                binder_index: ty::INNERMOST,
174
175                cache: Default::default(),
176            };
177            let param_env = param_env.fold_with(&mut env_canonicalizer);
178            debug_assert_eq!(env_canonicalizer.binder_index, ty::INNERMOST);
179            (param_env, env_canonicalizer.variable_lookup_table, env_canonicalizer.var_kinds)
180        }
181    }
182
183    /// When canonicalizing query inputs, we keep `'static` in the `param_env`
184    /// but erase it everywhere else. We generally don't want to depend on region
185    /// identity, so while it should not matter whether `'static` is kept in the
186    /// value or opaque type storage as well, this prevents us from accidentally
187    /// relying on it in the future.
188    ///
189    /// We want to keep the option of canonicalizing `'static` to an existential
190    /// variable in the future by changing the way we detect global where-bounds.
191    pub fn canonicalize_input<P: TypeFoldable<I>>(
192        delegate: &'a D,
193        variables: &'a mut Vec<I::GenericArg>,
194        is_hir_typeck_root_goal: bool,
195        input: QueryInput<I, P>,
196    ) -> ty::Canonical<I, QueryInput<I, P>> {
197        // First canonicalize the `param_env` while keeping `'static`
198        let (param_env, variable_lookup_table, var_kinds) =
199            Canonicalizer::canonicalize_param_env(delegate, variables, input.goal.param_env);
200        // Then canonicalize the rest of the input without keeping `'static`
201        // while *mostly* reusing the canonicalizer from above.
202        let mut rest_canonicalizer = Canonicalizer {
203            delegate,
204            canonicalize_mode: CanonicalizeMode::Input(CanonicalizeInputKind::Predicate {
205                is_hir_typeck_root_goal,
206            }),
207
208            variables,
209            variable_lookup_table,
210            var_kinds,
211            binder_index: ty::INNERMOST,
212
213            // We do not reuse the cache as it may contain entries whose canonicalized
214            // value contains `'static`. While we could alternatively handle this by
215            // checking for `'static` when using cached entries, this does not
216            // feel worth the effort. I do not expect that a `ParamEnv` will ever
217            // contain large enough types for caching to be necessary.
218            cache: Default::default(),
219        };
220
221        let predicate = input.goal.predicate;
222        let predicate = if predicate.has_type_flags(NEEDS_CANONICAL) {
223            predicate.fold_with(&mut rest_canonicalizer)
224        } else {
225            predicate
226        };
227        let goal = Goal { param_env, predicate };
228
229        let predefined_opaques_in_body = input.predefined_opaques_in_body;
230        let predefined_opaques_in_body =
231            if input.predefined_opaques_in_body.has_type_flags(NEEDS_CANONICAL) {
232                predefined_opaques_in_body.fold_with(&mut rest_canonicalizer)
233            } else {
234                predefined_opaques_in_body
235            };
236
237        let value = QueryInput { goal, predefined_opaques_in_body };
238
239        debug_assert!(!value.has_infer(), "unexpected infer in {value:?}");
240        debug_assert!(!value.has_placeholders(), "unexpected placeholders in {value:?}");
241        let (max_universe, variables) = rest_canonicalizer.finalize();
242        Canonical { max_universe, variables, value }
243    }
244
245    fn get_or_insert_bound_var(
246        &mut self,
247        arg: impl Into<I::GenericArg>,
248        kind: CanonicalVarKind<I>,
249    ) -> ty::BoundVar {
250        // FIXME: 16 is made up and arbitrary. We should look at some
251        // perf data here.
252        let arg = arg.into();
253        let idx = if self.variables.len() > 16 {
254            if self.variable_lookup_table.is_empty() {
255                self.variable_lookup_table.extend(self.variables.iter().copied().zip(0..));
256            }
257
258            *self.variable_lookup_table.entry(arg).or_insert_with(|| {
259                let var = self.variables.len();
260                self.variables.push(arg);
261                self.var_kinds.push(kind);
262                var
263            })
264        } else {
265            self.variables.iter().position(|&v| v == arg).unwrap_or_else(|| {
266                let var = self.variables.len();
267                self.variables.push(arg);
268                self.var_kinds.push(kind);
269                var
270            })
271        };
272
273        ty::BoundVar::from(idx)
274    }
275
276    fn finalize(self) -> (ty::UniverseIndex, I::CanonicalVarKinds) {
277        let mut var_kinds = self.var_kinds;
278        // See the rustc-dev-guide section about how we deal with universes
279        // during canonicalization in the new solver.
280        match self.canonicalize_mode {
281            // All placeholders and vars are canonicalized in the root universe.
282            CanonicalizeMode::Input { .. } => {
283                debug_assert!(
284                    var_kinds.iter().all(|var| var.universe() == ty::UniverseIndex::ROOT),
285                    "expected all vars to be canonicalized in root universe: {var_kinds:#?}"
286                );
287                let var_kinds = self.delegate.cx().mk_canonical_var_kinds(&var_kinds);
288                (ty::UniverseIndex::ROOT, var_kinds)
289            }
290            // When canonicalizing a response we map a universes already entered
291            // by the caller to the root universe and only return useful universe
292            // information for placeholders and inference variables created inside
293            // of the query.
294            CanonicalizeMode::Response { max_input_universe } => {
295                for var in var_kinds.iter_mut() {
296                    let uv = var.universe();
297                    let new_uv = ty::UniverseIndex::from(
298                        uv.index().saturating_sub(max_input_universe.index()),
299                    );
300                    *var = var.with_updated_universe(new_uv);
301                }
302                let max_universe = var_kinds
303                    .iter()
304                    .map(|kind| kind.universe())
305                    .max()
306                    .unwrap_or(ty::UniverseIndex::ROOT);
307                let var_kinds = self.delegate.cx().mk_canonical_var_kinds(&var_kinds);
308                (max_universe, var_kinds)
309            }
310        }
311    }
312
313    fn inner_fold_ty(&mut self, t: I::Ty) -> I::Ty {
314        let kind = match t.kind() {
315            ty::Infer(i) => match i {
316                ty::TyVar(vid) => {
317                    debug_assert_eq!(
318                        self.delegate.opportunistic_resolve_ty_var(vid),
319                        t,
320                        "ty vid should have been resolved fully before canonicalization"
321                    );
322
323                    match self.canonicalize_mode {
324                        CanonicalizeMode::Input { .. } => CanonicalVarKind::Ty(
325                            CanonicalTyVarKind::General(ty::UniverseIndex::ROOT),
326                        ),
327                        CanonicalizeMode::Response { .. } => {
328                            CanonicalVarKind::Ty(CanonicalTyVarKind::General(
329                                self.delegate.universe_of_ty(vid).unwrap_or_else(|| {
330                                    panic!("ty var should have been resolved: {t:?}")
331                                }),
332                            ))
333                        }
334                    }
335                }
336                ty::IntVar(vid) => {
337                    debug_assert_eq!(
338                        self.delegate.opportunistic_resolve_int_var(vid),
339                        t,
340                        "ty vid should have been resolved fully before canonicalization"
341                    );
342                    CanonicalVarKind::Ty(CanonicalTyVarKind::Int)
343                }
344                ty::FloatVar(vid) => {
345                    debug_assert_eq!(
346                        self.delegate.opportunistic_resolve_float_var(vid),
347                        t,
348                        "ty vid should have been resolved fully before canonicalization"
349                    );
350                    CanonicalVarKind::Ty(CanonicalTyVarKind::Float)
351                }
352                ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_) => {
353                    panic!("fresh vars not expected in canonicalization")
354                }
355            },
356            ty::Placeholder(placeholder) => match self.canonicalize_mode {
357                CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderTy(
358                    PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()),
359                ),
360                CanonicalizeMode::Response { .. } => CanonicalVarKind::PlaceholderTy(placeholder),
361            },
362            ty::Param(_) => match self.canonicalize_mode {
363                CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderTy(
364                    PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()),
365                ),
366                CanonicalizeMode::Response { .. } => panic!("param ty in response: {t:?}"),
367            },
368            ty::Bool
369            | ty::Char
370            | ty::Int(_)
371            | ty::Uint(_)
372            | ty::Float(_)
373            | ty::Adt(_, _)
374            | ty::Foreign(_)
375            | ty::Str
376            | ty::Array(_, _)
377            | ty::Slice(_)
378            | ty::RawPtr(_, _)
379            | ty::Ref(_, _, _)
380            | ty::Pat(_, _)
381            | ty::FnDef(_, _)
382            | ty::FnPtr(..)
383            | ty::UnsafeBinder(_)
384            | ty::Dynamic(_, _, _)
385            | ty::Closure(..)
386            | ty::CoroutineClosure(..)
387            | ty::Coroutine(_, _)
388            | ty::CoroutineWitness(..)
389            | ty::Never
390            | ty::Tuple(_)
391            | ty::Alias(_, _)
392            | ty::Bound(_, _)
393            | ty::Error(_) => {
394                return if t.has_type_flags(NEEDS_CANONICAL) {
395                    ensure_sufficient_stack(|| t.super_fold_with(self))
396                } else {
397                    t
398                };
399            }
400        };
401
402        let var = self.get_or_insert_bound_var(t, kind);
403
404        Ty::new_anon_bound(self.cx(), self.binder_index, var)
405    }
406}
407
408impl<D: SolverDelegate<Interner = I>, I: Interner> TypeFolder<I> for Canonicalizer<'_, D, I> {
409    fn cx(&self) -> I {
410        self.delegate.cx()
411    }
412
413    fn fold_binder<T>(&mut self, t: ty::Binder<I, T>) -> ty::Binder<I, T>
414    where
415        T: TypeFoldable<I>,
416    {
417        self.binder_index.shift_in(1);
418        let t = t.super_fold_with(self);
419        self.binder_index.shift_out(1);
420        t
421    }
422
423    fn fold_region(&mut self, r: I::Region) -> I::Region {
424        let kind = match r.kind() {
425            ty::ReBound(..) => return r,
426
427            // We don't canonicalize `ReStatic` in the `param_env` as we use it
428            // when checking whether a `ParamEnv` candidate is global.
429            ty::ReStatic => match self.canonicalize_mode {
430                CanonicalizeMode::Input(CanonicalizeInputKind::Predicate { .. }) => {
431                    CanonicalVarKind::Region(ty::UniverseIndex::ROOT)
432                }
433                CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv)
434                | CanonicalizeMode::Response { .. } => return r,
435            },
436
437            // `ReErased` should only be encountered in the hidden
438            // type of an opaque for regions that are ignored for the purposes of
439            // captures.
440            //
441            // FIXME: We should investigate the perf implications of not uniquifying
442            // `ReErased`. We may be able to short-circuit registering region
443            // obligations if we encounter a `ReErased` on one side, for example.
444            ty::ReErased | ty::ReError(_) => match self.canonicalize_mode {
445                CanonicalizeMode::Input(_) => CanonicalVarKind::Region(ty::UniverseIndex::ROOT),
446                CanonicalizeMode::Response { .. } => return r,
447            },
448
449            ty::ReEarlyParam(_) | ty::ReLateParam(_) => match self.canonicalize_mode {
450                CanonicalizeMode::Input(_) => CanonicalVarKind::Region(ty::UniverseIndex::ROOT),
451                CanonicalizeMode::Response { .. } => {
452                    panic!("unexpected region in response: {r:?}")
453                }
454            },
455
456            ty::RePlaceholder(placeholder) => match self.canonicalize_mode {
457                // We canonicalize placeholder regions as existentials in query inputs.
458                CanonicalizeMode::Input(_) => CanonicalVarKind::Region(ty::UniverseIndex::ROOT),
459                CanonicalizeMode::Response { max_input_universe } => {
460                    // If we have a placeholder region inside of a query, it must be from
461                    // a new universe.
462                    if max_input_universe.can_name(placeholder.universe()) {
463                        panic!("new placeholder in universe {max_input_universe:?}: {r:?}");
464                    }
465                    CanonicalVarKind::PlaceholderRegion(placeholder)
466                }
467            },
468
469            ty::ReVar(vid) => {
470                debug_assert_eq!(
471                    self.delegate.opportunistic_resolve_lt_var(vid),
472                    r,
473                    "region vid should have been resolved fully before canonicalization"
474                );
475                match self.canonicalize_mode {
476                    CanonicalizeMode::Input(_) => CanonicalVarKind::Region(ty::UniverseIndex::ROOT),
477                    CanonicalizeMode::Response { .. } => {
478                        CanonicalVarKind::Region(self.delegate.universe_of_lt(vid).unwrap())
479                    }
480                }
481            }
482        };
483
484        let var = if let CanonicalizeMode::Input(CanonicalizeInputKind::Predicate {
485            is_hir_typeck_root_goal: true,
486        }) = self.canonicalize_mode
487        {
488            let var = ty::BoundVar::from(self.variables.len());
489            self.variables.push(r.into());
490            self.var_kinds.push(kind);
491            var
492        } else {
493            self.get_or_insert_bound_var(r, kind)
494        };
495
496        Region::new_anon_bound(self.cx(), self.binder_index, var)
497    }
498
499    fn fold_ty(&mut self, t: I::Ty) -> I::Ty {
500        if let CanonicalizeMode::Input(CanonicalizeInputKind::Predicate {
501            is_hir_typeck_root_goal: true,
502        }) = self.canonicalize_mode
503        {
504            // If we're canonicalizing a root goal during HIR typeck, we
505            // must not use the `cache` as we want to map each occurrence
506            // of a region to a unique existential variable.
507            self.inner_fold_ty(t)
508        } else if let Some(&ty) = self.cache.get(&(self.binder_index, t)) {
509            ty
510        } else {
511            let res = self.inner_fold_ty(t);
512            let old = self.cache.insert((self.binder_index, t), res);
513            assert_eq!(old, None);
514            res
515        }
516    }
517
518    fn fold_const(&mut self, c: I::Const) -> I::Const {
519        let kind = match c.kind() {
520            ty::ConstKind::Infer(i) => match i {
521                ty::InferConst::Var(vid) => {
522                    debug_assert_eq!(
523                        self.delegate.opportunistic_resolve_ct_var(vid),
524                        c,
525                        "const vid should have been resolved fully before canonicalization"
526                    );
527
528                    match self.canonicalize_mode {
529                        CanonicalizeMode::Input { .. } => {
530                            CanonicalVarKind::Const(ty::UniverseIndex::ROOT)
531                        }
532                        CanonicalizeMode::Response { .. } => {
533                            CanonicalVarKind::Const(self.delegate.universe_of_ct(vid).unwrap())
534                        }
535                    }
536                }
537                ty::InferConst::Fresh(_) => todo!(),
538            },
539            ty::ConstKind::Placeholder(placeholder) => match self.canonicalize_mode {
540                CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderConst(
541                    PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()),
542                ),
543                CanonicalizeMode::Response { .. } => {
544                    CanonicalVarKind::PlaceholderConst(placeholder)
545                }
546            },
547            ty::ConstKind::Param(_) => match self.canonicalize_mode {
548                CanonicalizeMode::Input { .. } => CanonicalVarKind::PlaceholderConst(
549                    PlaceholderLike::new_anon(ty::UniverseIndex::ROOT, self.variables.len().into()),
550                ),
551                CanonicalizeMode::Response { .. } => panic!("param ty in response: {c:?}"),
552            },
553            // FIXME: See comment above -- we could fold the region separately or something.
554            ty::ConstKind::Bound(_, _)
555            | ty::ConstKind::Unevaluated(_)
556            | ty::ConstKind::Value(_)
557            | ty::ConstKind::Error(_)
558            | ty::ConstKind::Expr(_) => {
559                return if c.has_type_flags(NEEDS_CANONICAL) { c.super_fold_with(self) } else { c };
560            }
561        };
562
563        let var = self.get_or_insert_bound_var(c, kind);
564
565        Const::new_anon_bound(self.cx(), self.binder_index, var)
566    }
567
568    fn fold_predicate(&mut self, p: I::Predicate) -> I::Predicate {
569        if p.flags().intersects(NEEDS_CANONICAL) { p.super_fold_with(self) } else { p }
570    }
571
572    fn fold_clauses(&mut self, c: I::Clauses) -> I::Clauses {
573        match self.canonicalize_mode {
574            CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv)
575            | CanonicalizeMode::Response { max_input_universe: _ } => {}
576            CanonicalizeMode::Input(CanonicalizeInputKind::Predicate { .. }) => {
577                panic!("erasing 'static in env")
578            }
579        }
580        if c.flags().intersects(NEEDS_CANONICAL) { c.super_fold_with(self) } else { c }
581    }
582}
rustc_next_trait_solver/canonicalizer.rs

rustc_next_trait_solver/
canonicalizer.rs
