rustc_next_trait_solver/
normalize.rs

1use rustc_type_ir::data_structures::ensure_sufficient_stack;
2use rustc_type_ir::inherent::*;
3use rustc_type_ir::solve::{Goal, NoSolution};
4use rustc_type_ir::{
5    self as ty, AliasTerm, Binder, FallibleTypeFolder, InferConst, InferCtxtLike, InferTy,
6    Interner, TypeFoldable, TypeSuperFoldable, TypeSuperVisitable, TypeVisitable, TypeVisitableExt,
7    TypeVisitor, UniverseIndex,
8};
9use tracing::instrument;
10
11use crate::placeholder::{BoundVarReplacer, PlaceholderReplacer};
12
13/// This folder normalizes value and collects ambiguous goals.
14///
15/// Note that for ambiguous alias which contains escaping bound vars,
16/// we just return the original alias and don't collect the ambiguous goal.
17pub struct NormalizationFolder<'a, Infcx, I, F>
18where
19    Infcx: InferCtxtLike<Interner = I>,
20    I: Interner,
21{
22    infcx: &'a Infcx,
23    universes: Vec<Option<UniverseIndex>>,
24    stalled_goals: Vec<Goal<I, I::Predicate>>,
25    normalize: F,
26}
27
28#[derive(#[automatically_derived]
impl ::core::cmp::PartialEq for HasEscapingBoundVars {
    #[inline]
    fn eq(&self, other: &HasEscapingBoundVars) -> bool {
        let __self_discr = ::core::intrinsics::discriminant_value(self);
        let __arg1_discr = ::core::intrinsics::discriminant_value(other);
        __self_discr == __arg1_discr
    }
}PartialEq, #[automatically_derived]
impl ::core::cmp::Eq for HasEscapingBoundVars {
    #[inline]
    #[doc(hidden)]
    #[coverage(off)]
    fn assert_fields_are_eq(&self) {}
}Eq)]
29enum HasEscapingBoundVars {
30    Yes,
31    No,
32}
33
34/// Finds the max universe present in infer vars.
35struct MaxUniverse<'a, Infcx, I>
36where
37    Infcx: InferCtxtLike<Interner = I>,
38    I: Interner,
39{
40    infcx: &'a Infcx,
41    max_universe: ty::UniverseIndex,
42}
43
44impl<'a, Infcx, I> MaxUniverse<'a, Infcx, I>
45where
46    Infcx: InferCtxtLike<Interner = I>,
47    I: Interner,
48{
49    fn new(infcx: &'a Infcx) -> Self {
50        MaxUniverse { infcx, max_universe: ty::UniverseIndex::ROOT }
51    }
52
53    fn max_universe(self) -> ty::UniverseIndex {
54        self.max_universe
55    }
56}
57
58impl<'a, Infcx, I> TypeVisitor<I> for MaxUniverse<'a, Infcx, I>
59where
60    Infcx: InferCtxtLike<Interner = I>,
61    I: Interner,
62{
63    type Result = ();
64
65    fn visit_ty(&mut self, t: I::Ty) {
66        if !t.has_infer() {
67            return;
68        }
69
70        if let ty::Infer(InferTy::TyVar(vid)) = t.kind() {
71            // We shallow resolved the infer var before.
72            // So it should be a unresolved infer var with an universe.
73            self.max_universe = self.max_universe.max(self.infcx.universe_of_ty(vid).unwrap());
74        }
75
76        t.super_visit_with(self)
77    }
78
79    fn visit_const(&mut self, c: I::Const) {
80        if !c.has_infer() {
81            return;
82        }
83
84        if let ty::ConstKind::Infer(InferConst::Var(vid)) = c.kind() {
85            // We shallow resolved the infer var before.
86            // So it should be a unresolved infer var with an universe.
87            self.max_universe = self.max_universe.max(self.infcx.universe_of_ct(vid).unwrap());
88        }
89
90        c.super_visit_with(self)
91    }
92
93    fn visit_region(&mut self, r: I::Region) {
94        if let ty::ReVar(vid) = r.kind() {
95            self.max_universe = self.max_universe.max(self.infcx.universe_of_lt(vid).unwrap());
96        }
97    }
98}
99
100impl<'a, Infcx, I, F> NormalizationFolder<'a, Infcx, I, F>
101where
102    Infcx: InferCtxtLike<Interner = I>,
103    I: Interner,
104    F: FnMut(AliasTerm<I>) -> Result<(I::Term, Option<Goal<I, I::Predicate>>), NoSolution>,
105{
106    pub fn new(
107        infcx: &'a Infcx,
108        universes: Vec<Option<UniverseIndex>>,
109        stalled_goals: Vec<Goal<I, I::Predicate>>,
110        normalize: F,
111    ) -> Self {
112        Self { infcx, universes, stalled_goals, normalize }
113    }
114
115    pub fn stalled_goals(self) -> Vec<Goal<I, I::Predicate>> {
116        self.stalled_goals
117    }
118
119    fn normalize_alias_term(
120        &mut self,
121        alias_term: AliasTerm<I>,
122        has_escaping: HasEscapingBoundVars,
123    ) -> Result<Option<I::Term>, NoSolution> {
124        let current_universe = self.infcx.universe();
125        self.infcx.create_next_universe();
126
127        let (normalized, ambig_goal) = (self.normalize)(alias_term)?;
128
129        // Return ambiguous higher ranked alias as is, if
130        //   - it contains escaping vars, and
131        //   - the normalized term contains infer vars newly created
132        //     in the normalization above.
133        // The problem is that they may be resolved to types
134        // referencing the temporary placeholders.
135        //
136        // We can normalize the ambiguous alias again after the binder is instantiated.
137        if ambig_goal.is_some() && has_escaping == HasEscapingBoundVars::Yes {
138            let mut visitor = MaxUniverse::new(self.infcx);
139            normalized.visit_with(&mut visitor);
140            let max_universe = visitor.max_universe();
141            if current_universe.cannot_name(max_universe) {
142                return Ok(None);
143            }
144        }
145
146        self.stalled_goals.extend(ambig_goal);
147        Ok(Some(normalized))
148    }
149}
150
151impl<'a, Infcx, I, F> FallibleTypeFolder<I> for NormalizationFolder<'a, Infcx, I, F>
152where
153    Infcx: InferCtxtLike<Interner = I>,
154    I: Interner,
155    F: FnMut(AliasTerm<I>) -> Result<(I::Term, Option<Goal<I, I::Predicate>>), NoSolution>,
156{
157    type Error = NoSolution;
158
159    fn cx(&self) -> I {
160        self.infcx.cx()
161    }
162
163    fn try_fold_binder<T: TypeFoldable<I>>(
164        &mut self,
165        t: Binder<I, T>,
166    ) -> Result<Binder<I, T>, Self::Error> {
167        self.universes.push(None);
168        let t = t.try_super_fold_with(self)?;
169        self.universes.pop();
170        Ok(t)
171    }
172
173    x;#[instrument(level = "trace", skip(self), ret)]
174    fn try_fold_ty(&mut self, ty: I::Ty) -> Result<I::Ty, Self::Error> {
175        let infcx = self.infcx;
176        if !ty.has_aliases() {
177            return Ok(ty);
178        }
179
180        // With eager normalization, we should normalize the args of alias before
181        // normalizing the alias itself.
182        let ty = ty.try_super_fold_with(self)?;
183        let ty::Alias(alias_ty) = ty.kind() else { return Ok(ty) };
184
185        if ty.has_escaping_bound_vars() {
186            let (alias_ty, mapped_regions, mapped_types, mapped_consts) =
187                BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, alias_ty);
188            let Some(result) = ensure_sufficient_stack(|| {
189                self.normalize_alias_term(alias_ty.into(), HasEscapingBoundVars::Yes)
190            })?
191            else {
192                return Ok(ty);
193            };
194
195            Ok(PlaceholderReplacer::replace_placeholders(
196                infcx,
197                mapped_regions,
198                mapped_types,
199                mapped_consts,
200                &self.universes,
201                result.expect_ty(),
202            ))
203        } else {
204            Ok(ensure_sufficient_stack(|| {
205                self.normalize_alias_term(alias_ty.into(), HasEscapingBoundVars::No)
206            })?
207            .map(|term| term.expect_ty())
208            .unwrap_or(ty))
209        }
210    }
211
212    x;#[instrument(level = "trace", skip(self), ret)]
213    fn try_fold_const(&mut self, ct: I::Const) -> Result<I::Const, Self::Error> {
214        let infcx = self.infcx;
215        if !ct.has_aliases() {
216            return Ok(ct);
217        }
218
219        // With eager normalization, we should normalize the args of alias before
220        // normalizing the alias itself.
221        let ct = ct.try_super_fold_with(self)?;
222        let ty::ConstKind::Unevaluated(uv) = ct.kind() else { return Ok(ct) };
223
224        if ct.has_escaping_bound_vars() {
225            let (uv, mapped_regions, mapped_types, mapped_consts) =
226                BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, uv);
227            let Some(result) = ensure_sufficient_stack(|| {
228                self.normalize_alias_term(uv.into(), HasEscapingBoundVars::Yes)
229            })?
230            else {
231                return Ok(ct);
232            };
233            Ok(PlaceholderReplacer::replace_placeholders(
234                infcx,
235                mapped_regions,
236                mapped_types,
237                mapped_consts,
238                &self.universes,
239                result.expect_const(),
240            ))
241        } else {
242            Ok(ensure_sufficient_stack(|| {
243                self.normalize_alias_term(uv.into(), HasEscapingBoundVars::No)
244            })?
245            .map(|term| term.expect_const())
246            .unwrap_or(ct))
247        }
248    }
249}
rustc_next_trait_solver/normalize.rs

rustc_next_trait_solver/
normalize.rs
