chalk_ir/fold/
shift.rs

1//! Shifting of debruijn indices
2
3use crate::*;
4
5/// Methods for converting debruijn indices to move values into or out
6/// of binders.
7pub trait Shift<I: Interner>: TypeFoldable<I> {
8    /// Shifts this term in one level of binders.
9    fn shifted_in(self, interner: I) -> Self;
10
11    /// Shifts a term valid at `outer_binder` so that it is
12    /// valid at the innermost binder. See [`DebruijnIndex::shifted_in_from`]
13    /// for a detailed explanation.
14    fn shifted_in_from(self, interner: I, source_binder: DebruijnIndex) -> Self;
15
16    /// Shifts this term out one level of binders.
17    fn shifted_out(self, interner: I) -> Fallible<Self>;
18
19    /// Shifts a term valid at the innermost binder so that it is
20    /// valid at `outer_binder`. See [`DebruijnIndex::shifted_out_to`]
21    /// for a detailed explanation.
22    fn shifted_out_to(self, interner: I, target_binder: DebruijnIndex) -> Fallible<Self>;
23}
24
25impl<T: TypeFoldable<I>, I: Interner> Shift<I> for T {
26    fn shifted_in(self, interner: I) -> Self {
27        self.shifted_in_from(interner, DebruijnIndex::ONE)
28    }
29
30    fn shifted_in_from(self, interner: I, source_binder: DebruijnIndex) -> T {
31        self.try_fold_with(
32            &mut Shifter {
33                source_binder,
34                interner,
35            },
36            DebruijnIndex::INNERMOST,
37        )
38        .unwrap()
39    }
40
41    fn shifted_out_to(self, interner: I, target_binder: DebruijnIndex) -> Fallible<T> {
42        self.try_fold_with(
43            &mut DownShifter {
44                target_binder,
45                interner,
46            },
47            DebruijnIndex::INNERMOST,
48        )
49    }
50
51    fn shifted_out(self, interner: I) -> Fallible<Self> {
52        self.shifted_out_to(interner, DebruijnIndex::ONE)
53    }
54}
55
56/// A folder that adjusts debruijn indices by a certain amount.
57#[derive(FallibleTypeFolder)]
58struct Shifter<I: Interner> {
59    source_binder: DebruijnIndex,
60    interner: I,
61}
62
63impl<I: Interner> Shifter<I> {
64    /// Given a free variable at `depth`, shifts that depth to `depth
65    /// + self.adjustment`, and then wraps *that* within the internal
66    /// set `binders`.
67    fn adjust(&self, bound_var: BoundVar, outer_binder: DebruijnIndex) -> BoundVar {
68        bound_var
69            .shifted_in_from(self.source_binder)
70            .shifted_in_from(outer_binder)
71    }
72}
73
74impl<I: Interner> TypeFolder<I> for Shifter<I> {
75    fn as_dyn(&mut self) -> &mut dyn TypeFolder<I> {
76        self
77    }
78
79    fn fold_free_var_ty(&mut self, bound_var: BoundVar, outer_binder: DebruijnIndex) -> Ty<I> {
80        TyKind::<I>::BoundVar(self.adjust(bound_var, outer_binder))
81            .intern(TypeFolder::interner(self))
82    }
83
84    fn fold_free_var_lifetime(
85        &mut self,
86        bound_var: BoundVar,
87        outer_binder: DebruijnIndex,
88    ) -> Lifetime<I> {
89        LifetimeData::<I>::BoundVar(self.adjust(bound_var, outer_binder))
90            .intern(TypeFolder::interner(self))
91    }
92
93    fn fold_free_var_const(
94        &mut self,
95        ty: Ty<I>,
96        bound_var: BoundVar,
97        outer_binder: DebruijnIndex,
98    ) -> Const<I> {
99        // const types don't have free variables, so we can skip folding `ty`
100        self.adjust(bound_var, outer_binder)
101            .to_const(TypeFolder::interner(self), ty)
102    }
103
104    fn interner(&self) -> I {
105        self.interner
106    }
107}
108
109//---------------------------------------------------------------------------
110
111/// A shifter that reduces debruijn indices -- in other words, which lifts a value
112/// *out* from binders. Consider this example:
113///
114struct DownShifter<I> {
115    target_binder: DebruijnIndex,
116    interner: I,
117}
118
119impl<I> DownShifter<I> {
120    /// Given a reference to a free variable at depth `depth`
121    /// (appearing within `binders` internal binders), attempts to
122    /// lift that free variable out from `adjustment` levels of
123    /// binders (i.e., convert it to depth `depth -
124    /// self.adjustment`). If the free variable is bound by one of
125    /// those internal binders (i.e., `depth < self.adjustment`) the
126    /// this will fail with `Err`. Otherwise, returns the variable at
127    /// this new depth (but adjusted to appear within `binders`).
128    fn adjust(&self, bound_var: BoundVar, outer_binder: DebruijnIndex) -> Fallible<BoundVar> {
129        match bound_var.shifted_out_to(self.target_binder) {
130            Some(bound_var1) => Ok(bound_var1.shifted_in_from(outer_binder)),
131            None => Err(NoSolution),
132        }
133    }
134}
135
136impl<I: Interner> FallibleTypeFolder<I> for DownShifter<I> {
137    type Error = NoSolution;
138
139    fn as_dyn(&mut self) -> &mut dyn FallibleTypeFolder<I, Error = Self::Error> {
140        self
141    }
142
143    fn try_fold_free_var_ty(
144        &mut self,
145        bound_var: BoundVar,
146        outer_binder: DebruijnIndex,
147    ) -> Fallible<Ty<I>> {
148        Ok(TyKind::<I>::BoundVar(self.adjust(bound_var, outer_binder)?).intern(self.interner()))
149    }
150
151    fn try_fold_free_var_lifetime(
152        &mut self,
153        bound_var: BoundVar,
154        outer_binder: DebruijnIndex,
155    ) -> Fallible<Lifetime<I>> {
156        Ok(
157            LifetimeData::<I>::BoundVar(self.adjust(bound_var, outer_binder)?)
158                .intern(self.interner()),
159        )
160    }
161
162    fn try_fold_free_var_const(
163        &mut self,
164        ty: Ty<I>,
165        bound_var: BoundVar,
166        outer_binder: DebruijnIndex,
167    ) -> Fallible<Const<I>> {
168        // const types don't have free variables, so we can skip folding `ty`
169        Ok(self
170            .adjust(bound_var, outer_binder)?
171            .to_const(self.interner(), ty))
172    }
173
174    fn interner(&self) -> I {
175        self.interner
176    }
177}
chalk_ir/fold/shift.rs

chalk_ir/fold/
shift.rs
