Skip to main content

rustc_next_trait_solver/canonical/
canonicalizer.rs

1use std::collections::hash_map::Entry;
2
3use rustc_type_ir::inherent::*;
4use rustc_type_ir::solve::{Goal, QueryInput};
5use rustc_type_ir::{
6    self as ty, Canonical, CanonicalParamEnvCacheEntry, CanonicalVarKind, CanonicalizerState,
7    Const, Flags, InferCtxtLike, Interner, PlaceholderConst, PlaceholderRegion, PlaceholderType,
8    PredicateProxy, Region, TypeFlags, TypeFoldable, TypeFolder, TypeSuperFoldable,
9    TypeVisitableExt,
10};
11
12use crate::delegate::SolverDelegate;
13
14/// Does this have infer/placeholder/param, free regions or ReErased?
15// We're explicitly checking for fresh types and consts to trigger an
16// assert if they ever leak into the trait solver. They should never
17// exist with the new solver.
18const NEEDS_CANONICAL: TypeFlags = TypeFlags::from_bits(
19    TypeFlags::HAS_INFER.bits()
20        | TypeFlags::HAS_PLACEHOLDER.bits()
21        | TypeFlags::HAS_PARAM.bits()
22        | TypeFlags::HAS_FREE_REGIONS.bits()
23        | TypeFlags::HAS_RE_ERASED.bits()
24        | TypeFlags::HAS_TY_FRESH.bits()
25        | TypeFlags::HAS_CT_FRESH.bits(),
26)
27.unwrap();
28
29#[derive(#[automatically_derived]impl<I: ::core::fmt::Debug + Interner>
    ::core::fmt::Debug for CanonicalizeInputKind<I> where
    I::CanonicalVarKinds: ::core::fmt::Debug {
    #[inline]
    #[rustc_trivial_field_reads]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        match self {
            Self::ParamEnv =>
                ::core::fmt::Formatter::write_str(f, "ParamEnv"),
            Self::Predicate { param_env_var_kinds: __self_0 } =>
                ::core::fmt::Formatter::debug_struct_field1_finish(f,
                    "Predicate param_env_var_kinds", &__self_0),
        }
    }
}Debug, #[automatically_derived]impl<I: ::core::clone::Clone + Interner>
    ::core::clone::Clone for CanonicalizeInputKind<I> where
    I::CanonicalVarKinds: ::core::clone::Clone {
    #[inline]
    #[rustc_trivial_field_reads]
    fn clone(&self) -> Self {
        match self {
            Self::ParamEnv => CanonicalizeInputKind::ParamEnv,
            Self::Predicate { param_env_var_kinds: __self_0 } =>
                CanonicalizeInputKind::Predicate {
                    param_env_var_kinds: ::core::clone::Clone::clone(__self_0),
                },
        }
    }
}Clone, #[automatically_derived]impl<I: ::core::marker::Copy + Interner>
    ::core::marker::Copy for CanonicalizeInputKind<I> where
    I::CanonicalVarKinds: ::core::marker::Copy {
}Copy)]
30enum CanonicalizeInputKind<I: Interner> {
31    /// When canonicalizing the `param_env`, we keep `'static` as merging
32    /// trait candidates relies on it when deciding whether a where-bound
33    /// is trivial.
34    ParamEnv,
35    /// When canonicalizing predicates, we don't keep `'static`.
36    /// `param_env_var_kinds` caches the interned variable kinds to be
37    /// reused if there are no new vars.
38    Predicate { param_env_var_kinds: Option<I::CanonicalVarKinds> },
39}
40
41/// Whether we're canonicalizing a query input or the query response.
42///
43/// When canonicalizing an input we're in the context of the caller
44/// while canonicalizing the response happens in the context of the
45/// query.
46#[derive(#[automatically_derived]impl<I: ::core::fmt::Debug + Interner>
    ::core::fmt::Debug for CanonicalizeMode<I> {
    #[inline]
    #[rustc_trivial_field_reads]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        match self {
            Self::Input(__self_0) =>
                ::core::fmt::Formatter::debug_struct_field1_finish(f, "Input",
                    &__self_0),
            Self::Response { max_input_universe: __self_0 } =>
                ::core::fmt::Formatter::debug_struct_field1_finish(f,
                    "Response max_input_universe", &__self_0),
        }
    }
}Debug, #[automatically_derived]impl<I: ::core::clone::Clone + Interner>
    ::core::clone::Clone for CanonicalizeMode<I> {
    #[inline]
    #[rustc_trivial_field_reads]
    fn clone(&self) -> Self {
        match self {
            Self::Input(__self_0) =>
                CanonicalizeMode::Input(::core::clone::Clone::clone(__self_0)),
            Self::Response { max_input_universe: __self_0 } =>
                CanonicalizeMode::Response {
                    max_input_universe: ::core::clone::Clone::clone(__self_0),
                },
        }
    }
}Clone, #[automatically_derived]impl<I: ::core::marker::Copy + Interner>
    ::core::marker::Copy for CanonicalizeMode<I> {
}Copy)]
47enum CanonicalizeMode<I: Interner> {
48    Input(CanonicalizeInputKind<I>),
49    /// FIXME: We currently return region constraints referring to
50    /// placeholders and inference variables from a binder instantiated
51    /// inside of the query.
52    ///
53    /// In the long term we should eagerly deal with these constraints
54    /// inside of the query and only propagate constraints which are
55    /// actually nameable by the caller.
56    Response {
57        /// The highest universe nameable by the caller.
58        ///
59        /// All variables in a universe nameable by the caller get mapped
60        /// to the root universe in the response and then mapped back to
61        /// their correct universe when applying the query response in the
62        /// context of the caller.
63        ///
64        /// This doesn't work for universes created inside of the query so
65        /// we do remember their universe in the response.
66        max_input_universe: ty::UniverseIndex,
67    },
68}
69
70pub(super) struct Canonicalizer<'a, D: SolverDelegate<Interner = I>, I: Interner> {
71    delegate: &'a D,
72
73    canonicalize_mode: CanonicalizeMode<I>,
74
75    // Mutable fields.
76    state: Box<CanonicalizerState<I>>,
77}
78
79impl<'a, D: SolverDelegate<Interner = I>, I: Interner> Canonicalizer<'a, D, I> {
80    fn new(delegate: &'a D, canonicalize_mode: CanonicalizeMode<I>) -> Self {
81        Canonicalizer { delegate, canonicalize_mode, state: delegate.obtain_canonicalizer_state() }
82    }
83
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        if !value.has_type_flags(NEEDS_CANONICAL) {
90            let var_kinds = delegate.cx().mk_canonical_var_kinds(&[]);
91            return Canonical { max_universe: ty::UniverseIndex::ROOT, var_kinds, value };
92        }
93
94        let mut canonicalizer =
95            Canonicalizer::new(delegate, CanonicalizeMode::Response { max_input_universe });
96        let value = value.fold_with(&mut canonicalizer);
97        if true {
    if !!value.has_infer() {
        {
            ::core::panicking::panic_fmt(format_args!("unexpected infer in {0:?}",
                    value));
        }
    };
};debug_assert!(!value.has_infer(), "unexpected infer in {value:?}");
98        if true {
    if !!value.has_placeholders() {
        {
            ::core::panicking::panic_fmt(format_args!("unexpected placeholders in {0:?}",
                    value));
        }
    };
};debug_assert!(!value.has_placeholders(), "unexpected placeholders in {value:?}");
99        let (max_universe, var_kinds) = canonicalizer.finalize();
100        Canonical { max_universe, var_kinds, value }
101    }
102
103    /// When canonicalizing query inputs, we keep `'static` in the `param_env`
104    /// but erase it everywhere else. We generally don't want to depend on region
105    /// identity, so while it should not matter whether `'static` is kept in the
106    /// value or opaque type storage as well, this prevents us from accidentally
107    /// relying on it in the future.
108    ///
109    /// We want to keep the option of canonicalizing `'static` to an existential
110    /// variable in the future by changing the way we detect global where-bounds.
111    pub(super) fn canonicalize_input<P: TypeFoldable<I>>(
112        delegate: &'a D,
113        input: QueryInput<I, P>,
114    ) -> (Vec<I::GenericArg>, ty::Canonical<I, QueryInput<I, P>>) {
115        if !input.has_type_flags(NEEDS_CANONICAL) {
116            let max_universe = ty::UniverseIndex::ROOT;
117            let var_kinds = delegate.cx().mk_canonical_var_kinds(&[]);
118            return (::alloc::vec::Vec::new()vec![], Canonical { max_universe, var_kinds, value: input });
119        }
120
121        let param_env = input.goal.param_env;
122
123        // Do the `env` canonicalization, and then convert the canonicalizer to `rest` form for
124        // subsequent use.
125        let do_env_and_make_rest = || {
126            let mut env_canonicalizer = Canonicalizer::new(
127                delegate,
128                CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv),
129            );
130            let param_env = param_env.fold_with(&mut env_canonicalizer);
131
132            if true {
    if !env_canonicalizer.state.sub_root_lookup_table.is_empty() {
        ::core::panicking::panic("assertion failed: env_canonicalizer.state.sub_root_lookup_table.is_empty()")
    };
};debug_assert!(env_canonicalizer.state.sub_root_lookup_table.is_empty());
133
134            // Transform the `env_canonicalizer` into the `rest_canonicalizer`, keeping some things
135            // and replacing others.
136            //
137            // We do not reuse the cache as it may contain entries whose canonicalized
138            // value contains `'static`. While we could alternatively handle this by
139            // checking for `'static` when using cached entries, this does not
140            // feel worth the effort. I do not expect that a `ParamEnv` will ever
141            // contain large enough types for caching to be necessary.
142            //
143            // We clear the cache rather than deleting it or replacing it with an empty cache. This
144            // lets the allocated capacity be reused later.
145            let mut rest_canonicalizer = Canonicalizer {
146                canonicalize_mode: CanonicalizeMode::Input(CanonicalizeInputKind::Predicate {
147                    param_env_var_kinds: None,
148                }),
149                ..env_canonicalizer
150            };
151            rest_canonicalizer.state.cache.clear();
152
153            (param_env, rest_canonicalizer)
154        };
155
156        // First canonicalize the `param_env` while keeping `'static`. This produces a
157        // canonicalizer that can canonicalize the rest of the input without keeping `'static`.
158        //
159        // For this, we first check if `param_env` even needs canonicalization. If it does, then
160        // we check whether we can use the global cache for this param_env. As we only use
161        // the `param_env` itself as the cache key, considering any additional information
162        // during its canonicalization would be incorrect. We always canonicalize region
163        // inference variables in a separate universe, so these are fine. However, we do
164        // track the universe of type and const inference variables so these must not be
165        // globally cached. We don't rely on any additional information when canonicalizing
166        // placeholders.
167        let (param_env, mut rest_canonicalizer) = if !param_env.has_type_flags(NEEDS_CANONICAL) {
168            let rest_canonicalizer = Canonicalizer::new(
169                delegate,
170                CanonicalizeMode::Input(CanonicalizeInputKind::Predicate {
171                    param_env_var_kinds: None,
172                }),
173            );
174
175            (param_env, rest_canonicalizer)
176        } else if !param_env.has_non_region_infer() {
177            delegate.cx().with_canonical_param_env_cache(|cache| match cache.0.entry(param_env) {
178                Entry::Vacant(e) => {
179                    // Cache miss. Do `env` canonicalization and get `rest_canonicalizer`, make the
180                    // interned (i.e., uniquely identified) canonicalized variable kind list so it
181                    // can also be cached, and fill in the cache entry.
182                    let (param_env, mut rest_canonicalizer) = do_env_and_make_rest();
183                    let var_kinds =
184                        delegate.cx().mk_canonical_var_kinds(&rest_canonicalizer.state.var_kinds);
185                    rest_canonicalizer.canonicalize_mode =
186                        CanonicalizeMode::Input(CanonicalizeInputKind::Predicate {
187                            param_env_var_kinds: Some(var_kinds),
188                        });
189                    e.insert(CanonicalParamEnvCacheEntry {
190                        param_env,
191                        variables: rest_canonicalizer.state.variables.clone(),
192                        var_kinds,
193                        // SAFETY: The iterated elements go straight back into a hashmap.
194                        #[allow(rustc::potential_query_instability)]
195                        variable_lookup_table: rest_canonicalizer
196                            .state
197                            .variable_lookup_table
198                            .iter()
199                            .map(|(&arg, &idx)| (arg, idx))
200                            .collect(),
201                    });
202                    (param_env, rest_canonicalizer)
203                }
204                Entry::Occupied(e) => {
205                    // Cache hit; no canonicalization required. Just set up `rest_canonicalizer`.
206                    let e = e.get();
207                    let mut rest_canonicalizer = Canonicalizer::new(
208                        delegate,
209                        CanonicalizeMode::Input(CanonicalizeInputKind::Predicate {
210                            param_env_var_kinds: Some(e.var_kinds),
211                        }),
212                    );
213                    rest_canonicalizer.state.variables.clone_from(&e.variables);
214                    e.var_kinds.as_slice().clone_into(&mut rest_canonicalizer.state.var_kinds);
215                    rest_canonicalizer
216                        .state
217                        .variable_lookup_table
218                        .clone_from(&e.variable_lookup_table);
219                    (e.param_env, rest_canonicalizer)
220                }
221            })
222        } else {
223            // Do `env` canonicalization and get `rest_canonicalizer`.
224            let (param_env, rest_canonicalizer) = do_env_and_make_rest();
225            (param_env, rest_canonicalizer)
226        };
227
228        let predicate = input.goal.predicate;
229        let predicate = predicate.fold_with(&mut rest_canonicalizer);
230        let goal = Goal { param_env, predicate };
231
232        let predefined_opaques_in_body = input.predefined_opaques_in_body;
233        let predefined_opaques_in_body =
234            if predefined_opaques_in_body.has_type_flags(NEEDS_CANONICAL) {
235                predefined_opaques_in_body.fold_with(&mut rest_canonicalizer)
236            } else {
237                predefined_opaques_in_body
238            };
239
240        let value = QueryInput { goal, predefined_opaques_in_body };
241
242        if true {
    if !!value.has_infer() {
        {
            ::core::panicking::panic_fmt(format_args!("unexpected infer in {0:?}",
                    value));
        }
    };
};debug_assert!(!value.has_infer(), "unexpected infer in {value:?}");
243        if true {
    if !!value.has_placeholders() {
        {
            ::core::panicking::panic_fmt(format_args!("unexpected placeholders in {0:?}",
                    value));
        }
    };
};debug_assert!(!value.has_placeholders(), "unexpected placeholders in {value:?}");
244        let variables = rest_canonicalizer.state.variables.clone();
245        let (max_universe, var_kinds) = rest_canonicalizer.finalize();
246        (variables, Canonical { max_universe, var_kinds, 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        // The exact value of 16 here doesn't matter that much (8 and 32 give extremely similar
255        // results). So long as we have protection against the rare cases where the length reaches
256        // 1000+ (e.g. `wg-grammar`).
257        let arg = arg.into();
258        let idx = if self.state.variables.len() > 16 {
259            if self.state.variable_lookup_table.is_empty() {
260                self.state
261                    .variable_lookup_table
262                    .extend(self.state.variables.iter().copied().zip(0..));
263            }
264
265            *self.state.variable_lookup_table.entry(arg).or_insert_with(|| {
266                let var = self.state.variables.len();
267                self.state.variables.push(arg);
268                self.state.var_kinds.push(kind);
269                var
270            })
271        } else {
272            self.state.variables.iter().position(|&v| v == arg).unwrap_or_else(|| {
273                let var = self.state.variables.len();
274                self.state.variables.push(arg);
275                self.state.var_kinds.push(kind);
276                var
277            })
278        };
279
280        ty::BoundVar::from(idx)
281    }
282
283    fn get_or_insert_sub_root(&mut self, vid: ty::TyVid) -> ty::BoundVar {
284        let root_vid = self.delegate.sub_unification_table_root_var(vid);
285        let idx = *self
286            .state
287            .sub_root_lookup_table
288            .entry(root_vid)
289            .or_insert_with(|| self.state.variables.len());
290        ty::BoundVar::from(idx)
291    }
292
293    fn finalize(mut self) -> (ty::UniverseIndex, I::CanonicalVarKinds) {
294        // See the rustc-dev-guide section about how we deal with universes
295        // during canonicalization in the new solver.
296        let max_universe = match self.canonicalize_mode {
297            // All placeholders and vars are canonicalized in the root universe.
298            CanonicalizeMode::Input(_) => {
299                if true {
    if !self.state.var_kinds.iter().all(|var|
                    var.universe() == ty::UniverseIndex::ROOT) {
        {
            ::core::panicking::panic_fmt(format_args!("expected all vars to be canonicalized in root universe: {0:#?}",
                    self.state.var_kinds));
        }
    };
};debug_assert!(
300                    self.state
301                        .var_kinds
302                        .iter()
303                        .all(|var| var.universe() == ty::UniverseIndex::ROOT),
304                    "expected all vars to be canonicalized in root universe: {:#?}",
305                    self.state.var_kinds,
306                );
307                ty::UniverseIndex::ROOT
308            }
309            // When canonicalizing a response we map a universes already entered
310            // by the caller to the root universe and only return useful universe
311            // information for placeholders and inference variables created inside
312            // of the query.
313            CanonicalizeMode::Response { max_input_universe } => {
314                for var in self.state.var_kinds.iter_mut() {
315                    let uv = var.universe();
316                    let new_uv = ty::UniverseIndex::from(
317                        uv.index().saturating_sub(max_input_universe.index()),
318                    );
319                    *var = var.with_updated_universe(new_uv);
320                }
321                self.state
322                    .var_kinds
323                    .iter()
324                    .map(|kind| kind.universe())
325                    .max()
326                    .unwrap_or(ty::UniverseIndex::ROOT)
327            }
328        };
329        let var_kinds = match self.canonicalize_mode {
330            CanonicalizeMode::Input(CanonicalizeInputKind::Predicate {
331                param_env_var_kinds: Some(cached),
332            }) if cached.len() == self.state.variables.len() => {
333                if true {
    {
        match (&cached.as_slice(), &self.state.var_kinds.as_slice()) {
            (left_val, right_val) => {
                if !(*left_val == *right_val) {
                    let kind = ::core::panicking::AssertKind::Eq;
                    ::core::panicking::assert_failed(kind, &*left_val,
                        &*right_val, ::core::option::Option::None);
                }
            }
        }
    };
};debug_assert_eq!(cached.as_slice(), self.state.var_kinds.as_slice());
334                cached
335            }
336            _ => self.delegate.cx().mk_canonical_var_kinds(&self.state.var_kinds),
337        };
338
339        // We have finished with this canonicalizer and can return its state to the delegate for
340        // later reuse.
341        self.delegate.release_canonicalizer_state(self.state);
342
343        (max_universe, var_kinds)
344    }
345
346    fn inner_fold_ty(&mut self, t: I::Ty) -> I::Ty {
347        let kind = match t.kind() {
348            ty::Infer(i) => match i {
349                ty::TyVar(vid) => {
350                    if true {
    {
        match (&self.delegate.shallow_resolve_ty_var(vid), &t) {
            (left_val, right_val) => {
                if !(*left_val == *right_val) {
                    let kind = ::core::panicking::AssertKind::Eq;
                    ::core::panicking::assert_failed(kind, &*left_val,
                        &*right_val,
                        ::core::option::Option::Some(format_args!("ty vid should have been resolved fully before canonicalization")));
                }
            }
        }
    };
};debug_assert_eq!(
351                        self.delegate.shallow_resolve_ty_var(vid),
352                        t,
353                        "ty vid should have been resolved fully before canonicalization"
354                    );
355
356                    let sub_root = self.get_or_insert_sub_root(vid);
357                    let ui = match self.canonicalize_mode {
358                        CanonicalizeMode::Input(_) => ty::UniverseIndex::ROOT,
359                        CanonicalizeMode::Response { .. } => self
360                            .delegate
361                            .universe_of_ty(vid)
362                            .unwrap_or_else(|| {
    ::core::panicking::panic_fmt(format_args!("ty var should have been resolved: {0:?}",
            t));
}panic!("ty var should have been resolved: {t:?}")),
363                    };
364                    CanonicalVarKind::Ty { ui, sub_root }
365                }
366                ty::IntVar(vid) => {
367                    if true {
    {
        match (&self.delegate.shallow_resolve_int_var(vid), &t) {
            (left_val, right_val) => {
                if !(*left_val == *right_val) {
                    let kind = ::core::panicking::AssertKind::Eq;
                    ::core::panicking::assert_failed(kind, &*left_val,
                        &*right_val,
                        ::core::option::Option::Some(format_args!("ty vid should have been resolved fully before canonicalization")));
                }
            }
        }
    };
};debug_assert_eq!(
368                        self.delegate.shallow_resolve_int_var(vid),
369                        t,
370                        "ty vid should have been resolved fully before canonicalization"
371                    );
372                    CanonicalVarKind::Int
373                }
374                ty::FloatVar(vid) => {
375                    if true {
    {
        match (&self.delegate.shallow_resolve_float_var(vid), &t) {
            (left_val, right_val) => {
                if !(*left_val == *right_val) {
                    let kind = ::core::panicking::AssertKind::Eq;
                    ::core::panicking::assert_failed(kind, &*left_val,
                        &*right_val,
                        ::core::option::Option::Some(format_args!("ty vid should have been resolved fully before canonicalization")));
                }
            }
        }
    };
};debug_assert_eq!(
376                        self.delegate.shallow_resolve_float_var(vid),
377                        t,
378                        "ty vid should have been resolved fully before canonicalization"
379                    );
380                    CanonicalVarKind::Float
381                }
382                ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_) => {
383                    {
    ::core::panicking::panic_fmt(format_args!("fresh vars not expected in canonicalization"));
}panic!("fresh vars not expected in canonicalization")
384                }
385            },
386            ty::Placeholder(placeholder) => match self.canonicalize_mode {
387                CanonicalizeMode::Input(_) => self.new_placeholder_ty(),
388                CanonicalizeMode::Response { .. } => CanonicalVarKind::PlaceholderTy(placeholder),
389            },
390            ty::Param(_) => match self.canonicalize_mode {
391                CanonicalizeMode::Input(_) => self.new_placeholder_ty(),
392                CanonicalizeMode::Response { .. } => {
    ::core::panicking::panic_fmt(format_args!("param ty in response: {0:?}",
            t));
}panic!("param ty in response: {t:?}"),
393            },
394            ty::Bool
395            | ty::Char
396            | ty::Int(_)
397            | ty::Uint(_)
398            | ty::Float(_)
399            | ty::Adt(_, _)
400            | ty::Foreign(_)
401            | ty::Str
402            | ty::Array(_, _)
403            | ty::Slice(_)
404            | ty::RawPtr(_, _)
405            | ty::Ref(_, _, _)
406            | ty::Pat(_, _)
407            | ty::FnDef(_, _)
408            | ty::FnPtr(..)
409            | ty::UnsafeBinder(_)
410            | ty::Dynamic(_, _)
411            | ty::Closure(..)
412            | ty::CoroutineClosure(..)
413            | ty::Coroutine(_, _)
414            | ty::CoroutineWitness(..)
415            | ty::Never
416            | ty::Tuple(_)
417            | ty::Alias(_, _)
418            | ty::Bound(_, _)
419            | ty::Error(_) => {
420                return t.super_fold_with(self);
421            }
422
423            // FIXME(scrabsha)
424            ty::View(..) => ::core::panicking::unimplemented_default_msg()unimplemented!(),
425        };
426
427        let var = self.get_or_insert_bound_var(t, kind);
428
429        Ty::new_canonical_bound(self.cx(), var)
430    }
431
432    #[inline]
433    fn new_placeholder_ty(&self) -> CanonicalVarKind<I> {
434        CanonicalVarKind::PlaceholderTy(PlaceholderType::new_anon(
435            ty::UniverseIndex::ROOT,
436            self.state.variables.len().into(),
437        ))
438    }
439
440    #[inline]
441    fn new_placeholder_region(&self) -> CanonicalVarKind<I> {
442        CanonicalVarKind::PlaceholderRegion(PlaceholderRegion::new_anon(
443            ty::UniverseIndex::ROOT,
444            self.state.variables.len().into(),
445        ))
446    }
447
448    #[inline]
449    fn new_placeholder_const(&self) -> CanonicalVarKind<I> {
450        CanonicalVarKind::PlaceholderConst(PlaceholderConst::new_anon(
451            ty::UniverseIndex::ROOT,
452            self.state.variables.len().into(),
453        ))
454    }
455}
456
457impl<D: SolverDelegate<Interner = I>, I: Interner> TypeFolder<I> for Canonicalizer<'_, D, I> {
458    fn cx(&self) -> I {
459        self.delegate.cx()
460    }
461
462    fn fold_region(&mut self, r: Region<I>) -> Region<I> {
463        // We canonicalize free regions from the input into placeholder regions so that
464        // region constraints created in nested contexts can be propagated back to the
465        // caller, instead of unifying them.
466        // See the following Zulip discussion for details:
467        // https://rust-lang.zulipchat.com/#narrow/channel/364551-t-types.2Ftrait-system-refactor/topic/A.20question.20on.20.23251/near/579240238
468        let kind = match r.kind() {
469            ty::ReBound(..) => return r,
470
471            // We don't canonicalize `ReStatic` in the `param_env` as we use it
472            // when checking whether a `ParamEnv` candidate is global.
473            ty::ReStatic => match self.canonicalize_mode {
474                CanonicalizeMode::Input(CanonicalizeInputKind::Predicate { .. }) => {
475                    self.new_placeholder_region()
476                }
477                CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv)
478                | CanonicalizeMode::Response { .. } => return r,
479            },
480
481            // `ReErased` should only be encountered in the hidden
482            // type of an opaque for regions that are ignored for the purposes of
483            // captures.
484            //
485            // FIXME: We should investigate the perf implications of not uniquifying
486            // `ReErased`. We may be able to short-circuit registering region
487            // obligations if we encounter a `ReErased` on one side, for example.
488            ty::ReErased | ty::ReError(_) => match self.canonicalize_mode {
489                CanonicalizeMode::Input(_) => self.new_placeholder_region(),
490                CanonicalizeMode::Response { .. } => return r,
491            },
492
493            ty::ReEarlyParam(_) | ty::ReLateParam(_) => match self.canonicalize_mode {
494                CanonicalizeMode::Input(_) => self.new_placeholder_region(),
495                CanonicalizeMode::Response { .. } => {
496                    {
    ::core::panicking::panic_fmt(format_args!("unexpected region in response: {0:?}",
            r));
}panic!("unexpected region in response: {r:?}")
497                }
498            },
499
500            ty::RePlaceholder(placeholder) => match self.canonicalize_mode {
501                CanonicalizeMode::Input(_) => self.new_placeholder_region(),
502                CanonicalizeMode::Response { max_input_universe } => {
503                    // If we have a placeholder region inside of a query, it must be from
504                    // a new universe, unless from the root universe, which is used for
505                    // canonicalization of any free region from the input.
506                    if placeholder.universe() != ty::UniverseIndex::ROOT
507                        && max_input_universe.can_name(placeholder.universe())
508                    {
509                        {
    ::core::panicking::panic_fmt(format_args!("new placeholder in universe {0:?}: {1:?}",
            max_input_universe, r));
};panic!("new placeholder in universe {max_input_universe:?}: {r:?}");
510                    }
511                    CanonicalVarKind::PlaceholderRegion(placeholder)
512                }
513            },
514
515            ty::ReVar(vid) => {
516                if true {
    {
        match (&self.delegate.shallow_resolve_region_var(vid), &r) {
            (left_val, right_val) => {
                if !(*left_val == *right_val) {
                    let kind = ::core::panicking::AssertKind::Eq;
                    ::core::panicking::assert_failed(kind, &*left_val,
                        &*right_val,
                        ::core::option::Option::Some(format_args!("region vid should have been resolved fully before canonicalization")));
                }
            }
        }
    };
};debug_assert_eq!(
517                    self.delegate.shallow_resolve_region_var(vid),
518                    r,
519                    "region vid should have been resolved fully before canonicalization"
520                );
521                match self.canonicalize_mode {
522                    CanonicalizeMode::Input(_) => self.new_placeholder_region(),
523                    CanonicalizeMode::Response { .. } => {
524                        CanonicalVarKind::Region(self.delegate.universe_of_region(vid).unwrap())
525                    }
526                }
527            }
528        };
529
530        let var = self.get_or_insert_bound_var(r, kind);
531
532        Region::new_canonical_bound(self.cx(), var)
533    }
534
535    fn fold_ty(&mut self, t: I::Ty) -> I::Ty {
536        if !t.flags().intersects(NEEDS_CANONICAL) {
537            t
538        } else if let Some(&ty) = self.state.cache.get(&t) {
539            ty
540        } else {
541            let res = self.inner_fold_ty(t);
542            let is_unseen = self.state.cache.insert(t, res);
543            if !is_unseen { ::core::panicking::panic("assertion failed: is_unseen") };assert!(is_unseen);
544            res
545        }
546    }
547
548    fn fold_const(&mut self, c: Const<I>) -> Const<I> {
549        if !c.flags().intersects(NEEDS_CANONICAL) {
550            return c;
551        }
552
553        let kind = match c.kind() {
554            ty::ConstKind::Infer(i) => match i {
555                ty::InferConst::Var(vid) => {
556                    if true {
    {
        match (&self.delegate.shallow_resolve_const_var(vid), &c) {
            (left_val, right_val) => {
                if !(*left_val == *right_val) {
                    let kind = ::core::panicking::AssertKind::Eq;
                    ::core::panicking::assert_failed(kind, &*left_val,
                        &*right_val,
                        ::core::option::Option::Some(format_args!("const vid should have been resolved fully before canonicalization")));
                }
            }
        }
    };
};debug_assert_eq!(
557                        self.delegate.shallow_resolve_const_var(vid),
558                        c,
559                        "const vid should have been resolved fully before canonicalization"
560                    );
561
562                    match self.canonicalize_mode {
563                        CanonicalizeMode::Input(_) => {
564                            CanonicalVarKind::Const(ty::UniverseIndex::ROOT)
565                        }
566                        CanonicalizeMode::Response { .. } => {
567                            CanonicalVarKind::Const(self.delegate.universe_of_const(vid).unwrap())
568                        }
569                    }
570                }
571                ty::InferConst::Fresh(_) => ::core::panicking::unimplemented_default_msg()unimplemented!(),
572            },
573            ty::ConstKind::Placeholder(placeholder) => match self.canonicalize_mode {
574                CanonicalizeMode::Input(_) => self.new_placeholder_const(),
575                CanonicalizeMode::Response { .. } => {
576                    CanonicalVarKind::PlaceholderConst(placeholder)
577                }
578            },
579            ty::ConstKind::Param(_) => match self.canonicalize_mode {
580                CanonicalizeMode::Input(_) => self.new_placeholder_const(),
581                CanonicalizeMode::Response { .. } => {
    ::core::panicking::panic_fmt(format_args!("param ty in response: {0:?}",
            c));
}panic!("param ty in response: {c:?}"),
582            },
583            // FIXME: See comment above -- we could fold the region separately or something.
584            ty::ConstKind::Bound(_, _)
585            | ty::ConstKind::Alias(_, _)
586            | ty::ConstKind::Value(_)
587            | ty::ConstKind::Error(_)
588            | ty::ConstKind::Expr(_) => return c.super_fold_with(self),
589        };
590
591        let var = self.get_or_insert_bound_var(c, kind);
592
593        Const::new_canonical_bound(self.cx(), var)
594    }
595
596    fn fold_predicate<P: PredicateProxy<I>>(&mut self, p: P) -> P {
597        if !p.flags().intersects(NEEDS_CANONICAL) { p } else { p.super_fold_with(self) }
598    }
599
600    fn fold_clauses(&mut self, c: I::Clauses) -> I::Clauses {
601        match self.canonicalize_mode {
602            CanonicalizeMode::Input(CanonicalizeInputKind::ParamEnv)
603            | CanonicalizeMode::Response { max_input_universe: _ } => {}
604            CanonicalizeMode::Input(CanonicalizeInputKind::Predicate { .. }) => {
605                { ::core::panicking::panic_fmt(format_args!("erasing \'static in env")); }panic!("erasing 'static in env")
606            }
607        }
608        if !c.flags().intersects(NEEDS_CANONICAL) { c } else { c.super_fold_with(self) }
609    }
610}