rustc_next_trait_solver/
placeholder.rs

1use core::panic;
2
3use rustc_type_ir::data_structures::IndexMap;
4use rustc_type_ir::inherent::*;
5use rustc_type_ir::{
6    self as ty, InferCtxtLike, Interner, TypeFoldable, TypeFolder, TypeSuperFoldable,
7    TypeVisitableExt,
8};
9
10pub struct BoundVarReplacer<'a, Infcx, I = <Infcx as InferCtxtLike>::Interner>
11where
12    Infcx: InferCtxtLike<Interner = I>,
13    I: Interner,
14{
15    infcx: &'a Infcx,
16    // These three maps track the bound variable that were replaced by placeholders. It might be
17    // nice to remove these since we already have the `kind` in the placeholder; we really just need
18    // the `var` (but we *could* bring that into scope if we were to track them as we pass them).
19    mapped_regions: IndexMap<I::PlaceholderRegion, I::BoundRegion>,
20    mapped_types: IndexMap<I::PlaceholderTy, I::BoundTy>,
21    mapped_consts: IndexMap<I::PlaceholderConst, I::BoundConst>,
22    // The current depth relative to *this* folding, *not* the entire normalization. In other words,
23    // the depth of binders we've passed here.
24    current_index: ty::DebruijnIndex,
25    // The `UniverseIndex` of the binding levels above us. These are optional, since we are lazy:
26    // we don't actually create a universe until we see a bound var we have to replace.
27    universe_indices: &'a mut Vec<Option<ty::UniverseIndex>>,
28}
29
30impl<'a, Infcx, I> BoundVarReplacer<'a, Infcx, I>
31where
32    Infcx: InferCtxtLike<Interner = I>,
33    I: Interner,
34{
35    /// Returns `Some` if we *were* able to replace bound vars. If there are any bound vars that
36    /// use a binding level above `universe_indices.len()`, we fail.
37    pub fn replace_bound_vars<T: TypeFoldable<I>>(
38        infcx: &'a Infcx,
39        universe_indices: &'a mut Vec<Option<ty::UniverseIndex>>,
40        value: T,
41    ) -> (
42        T,
43        IndexMap<I::PlaceholderRegion, I::BoundRegion>,
44        IndexMap<I::PlaceholderTy, I::BoundTy>,
45        IndexMap<I::PlaceholderConst, I::BoundConst>,
46    ) {
47        let mut replacer = BoundVarReplacer {
48            infcx,
49            mapped_regions: Default::default(),
50            mapped_types: Default::default(),
51            mapped_consts: Default::default(),
52            current_index: ty::INNERMOST,
53            universe_indices,
54        };
55
56        let value = value.fold_with(&mut replacer);
57
58        (value, replacer.mapped_regions, replacer.mapped_types, replacer.mapped_consts)
59    }
60
61    fn universe_for(&mut self, debruijn: ty::DebruijnIndex) -> ty::UniverseIndex {
62        let infcx = self.infcx;
63        let index =
64            self.universe_indices.len() + self.current_index.as_usize() - debruijn.as_usize() - 1;
65        let universe = self.universe_indices[index].unwrap_or_else(|| {
66            for i in self.universe_indices.iter_mut().take(index + 1) {
67                *i = i.or_else(|| Some(infcx.create_next_universe()))
68            }
69            self.universe_indices[index].unwrap()
70        });
71        universe
72    }
73}
74
75impl<Infcx, I> TypeFolder<I> for BoundVarReplacer<'_, Infcx, I>
76where
77    Infcx: InferCtxtLike<Interner = I>,
78    I: Interner,
79{
80    fn cx(&self) -> I {
81        self.infcx.cx()
82    }
83
84    fn fold_binder<T: TypeFoldable<I>>(&mut self, t: ty::Binder<I, T>) -> ty::Binder<I, T> {
85        self.current_index.shift_in(1);
86        let t = t.super_fold_with(self);
87        self.current_index.shift_out(1);
88        t
89    }
90
91    fn fold_region(&mut self, r: I::Region) -> I::Region {
92        match r.kind() {
93            ty::ReBound(debruijn, _)
94                if debruijn.as_usize()
95                    >= self.current_index.as_usize() + self.universe_indices.len() =>
96            {
97                panic!(
98                    "Bound vars {r:#?} outside of `self.universe_indices`: {:#?}",
99                    self.universe_indices
100                );
101            }
102            ty::ReBound(debruijn, br) if debruijn >= self.current_index => {
103                let universe = self.universe_for(debruijn);
104                let p = PlaceholderLike::new(universe, br);
105                self.mapped_regions.insert(p, br);
106                Region::new_placeholder(self.cx(), p)
107            }
108            _ => r,
109        }
110    }
111
112    fn fold_ty(&mut self, t: I::Ty) -> I::Ty {
113        match t.kind() {
114            ty::Bound(debruijn, _)
115                if debruijn.as_usize() + 1
116                    > self.current_index.as_usize() + self.universe_indices.len() =>
117            {
118                panic!(
119                    "Bound vars {t:#?} outside of `self.universe_indices`: {:#?}",
120                    self.universe_indices
121                );
122            }
123            ty::Bound(debruijn, bound_ty) if debruijn >= self.current_index => {
124                let universe = self.universe_for(debruijn);
125                let p = PlaceholderLike::new(universe, bound_ty);
126                self.mapped_types.insert(p, bound_ty);
127                Ty::new_placeholder(self.cx(), p)
128            }
129            _ if t.has_vars_bound_at_or_above(self.current_index) => t.super_fold_with(self),
130            _ => t,
131        }
132    }
133
134    fn fold_const(&mut self, ct: I::Const) -> I::Const {
135        match ct.kind() {
136            ty::ConstKind::Bound(debruijn, _)
137                if debruijn.as_usize() + 1
138                    > self.current_index.as_usize() + self.universe_indices.len() =>
139            {
140                panic!(
141                    "Bound vars {ct:#?} outside of `self.universe_indices`: {:#?}",
142                    self.universe_indices
143                );
144            }
145            ty::ConstKind::Bound(debruijn, bound_const) if debruijn >= self.current_index => {
146                let universe = self.universe_for(debruijn);
147                let p = PlaceholderLike::new(universe, bound_const);
148                self.mapped_consts.insert(p, bound_const);
149                Const::new_placeholder(self.cx(), p)
150            }
151            _ => ct.super_fold_with(self),
152        }
153    }
154
155    fn fold_predicate(&mut self, p: I::Predicate) -> I::Predicate {
156        if p.has_vars_bound_at_or_above(self.current_index) { p.super_fold_with(self) } else { p }
157    }
158}
rustc_next_trait_solver/placeholder.rs

rustc_next_trait_solver/
placeholder.rs
