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

rustc_next_trait_solver/
canonicalizer.rs
