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

rustc_next_trait_solver/
canonicalizer.rs
