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(ty::BoundVarIndexKind::Bound(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(ty::BoundVarIndexKind::Bound(debruijn), br)
103                if debruijn >= self.current_index =>
104            {
105                let universe = self.universe_for(debruijn);
106                let p = PlaceholderLike::new(universe, br);
107                self.mapped_regions.insert(p, br);
108                Region::new_placeholder(self.cx(), p)
109            }
110            _ => r,
111        }
112    }
113
114    fn fold_ty(&mut self, t: I::Ty) -> I::Ty {
115        match t.kind() {
116            ty::Bound(ty::BoundVarIndexKind::Bound(debruijn), _)
117                if debruijn.as_usize() + 1
118                    > self.current_index.as_usize() + self.universe_indices.len() =>
119            {
120                panic!(
121                    "Bound vars {t:#?} outside of `self.universe_indices`: {:#?}",
122                    self.universe_indices
123                );
124            }
125            ty::Bound(ty::BoundVarIndexKind::Bound(debruijn), bound_ty)
126                if debruijn >= self.current_index =>
127            {
128                let universe = self.universe_for(debruijn);
129                let p = PlaceholderLike::new(universe, bound_ty);
130                self.mapped_types.insert(p, bound_ty);
131                Ty::new_placeholder(self.cx(), p)
132            }
133            _ if t.has_vars_bound_at_or_above(self.current_index) => t.super_fold_with(self),
134            _ => t,
135        }
136    }
137
138    fn fold_const(&mut self, ct: I::Const) -> I::Const {
139        match ct.kind() {
140            ty::ConstKind::Bound(ty::BoundVarIndexKind::Bound(debruijn), _)
141                if debruijn.as_usize() + 1
142                    > self.current_index.as_usize() + self.universe_indices.len() =>
143            {
144                panic!(
145                    "Bound vars {ct:#?} outside of `self.universe_indices`: {:#?}",
146                    self.universe_indices
147                );
148            }
149            ty::ConstKind::Bound(ty::BoundVarIndexKind::Bound(debruijn), bound_const)
150                if debruijn >= self.current_index =>
151            {
152                let universe = self.universe_for(debruijn);
153                let p = PlaceholderLike::new(universe, bound_const);
154                self.mapped_consts.insert(p, bound_const);
155                Const::new_placeholder(self.cx(), p)
156            }
157            _ => ct.super_fold_with(self),
158        }
159    }
160
161    fn fold_predicate(&mut self, p: I::Predicate) -> I::Predicate {
162        if p.has_vars_bound_at_or_above(self.current_index) { p.super_fold_with(self) } else { p }
163    }
164}
rustc_next_trait_solver/placeholder.rs

rustc_next_trait_solver/
placeholder.rs
