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

rustc_next_trait_solver/canonical/
canonicalizer.rs
