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

rustc_next_trait_solver/canonical/
canonicalizer.rs
