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, Binder, FallibleTypeFolder, InferConst, InferCtxtLike, InferTy, Interner,
6    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(I::Term) -> 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: I::Term,
122        has_escaping: HasEscapingBoundVars,
123    ) -> Result<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(alias_term);
143            }
144        }
145
146        self.stalled_goals.extend(ambig_goal);
147        Ok(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(I::Term) -> 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(..) = ty.kind() else { return Ok(ty) };
184
185        if ty.has_escaping_bound_vars() {
186            let (ty, mapped_regions, mapped_types, mapped_consts) =
187                BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, ty);
188            let result = ensure_sufficient_stack(|| {
189                self.normalize_alias_term(ty.into(), HasEscapingBoundVars::Yes)
190            })?
191            .expect_ty();
192            Ok(PlaceholderReplacer::replace_placeholders(
193                infcx,
194                mapped_regions,
195                mapped_types,
196                mapped_consts,
197                &self.universes,
198                result,
199            ))
200        } else {
201            Ok(ensure_sufficient_stack(|| {
202                self.normalize_alias_term(ty.into(), HasEscapingBoundVars::No)
203            })?
204            .expect_ty())
205        }
206    }
207
208    x;#[instrument(level = "trace", skip(self), ret)]
209    fn try_fold_const(&mut self, ct: I::Const) -> Result<I::Const, Self::Error> {
210        let infcx = self.infcx;
211        if !ct.has_aliases() {
212            return Ok(ct);
213        }
214
215        // With eager normalization, we should normalize the args of alias before
216        // normalizing the alias itself.
217        let ct = ct.try_super_fold_with(self)?;
218        let ty::ConstKind::Unevaluated(..) = ct.kind() else { return Ok(ct) };
219
220        if ct.has_escaping_bound_vars() {
221            let (ct, mapped_regions, mapped_types, mapped_consts) =
222                BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, ct);
223            let result = ensure_sufficient_stack(|| {
224                self.normalize_alias_term(ct.into(), HasEscapingBoundVars::Yes)
225            })?
226            .expect_const();
227            Ok(PlaceholderReplacer::replace_placeholders(
228                infcx,
229                mapped_regions,
230                mapped_types,
231                mapped_consts,
232                &self.universes,
233                result,
234            ))
235        } else {
236            Ok(ensure_sufficient_stack(|| {
237                self.normalize_alias_term(ct.into(), HasEscapingBoundVars::No)
238            })?
239            .expect_const())
240        }
241    }
242}
rustc_next_trait_solver/normalize.rs

rustc_next_trait_solver/
normalize.rs
