1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
use super::*;
use crate::fold::shift::Shift;
/// Substitution used during folding
pub struct Subst<'s, I: Interner> {
/// Values to substitute. A reference to a free variable with
/// index `i` will be mapped to `parameters[i]` -- if `i >
/// parameters.len()`, then we will leave the variable untouched.
parameters: &'s [GenericArg<I>],
interner: I,
}
impl<I: Interner> Subst<'_, I> {
/// Applies the substitution by folding
pub fn apply<T: Fold<I>>(interner: I, parameters: &[GenericArg<I>], value: T) -> T::Result {
value
.fold_with(
&mut Subst {
parameters,
interner,
},
DebruijnIndex::INNERMOST,
)
.unwrap()
}
}
impl<I: Interner> Folder<I> for Subst<'_, I> {
type Error = NoSolution;
fn as_dyn(&mut self) -> &mut dyn Folder<I, Error = Self::Error> {
self
}
/// We are eliminating one binder, but binders outside of that get preserved.
///
/// So e.g. consider this:
///
/// ```notrust
/// for<A, B> { for<C> { [A, C] } }
/// // ^ the binder we are substituing with `[u32]`
/// ```
///
/// Here, `A` would be `^1.0` and `C` would be `^0.0`. We will replace `^0.0` with the
/// 0th index from the list (`u32`). We will convert `^1.0` (A) to `^0.0` -- i.e., shift
/// it **out** of one level of binder (the `for<C>` binder we are eliminating).
///
/// This gives us as a result:
///
/// ```notrust
/// for<A, B> { [A, u32] }
/// ^ represented as `^0.0`
/// ```
fn fold_free_var_ty(
&mut self,
bound_var: BoundVar,
outer_binder: DebruijnIndex,
) -> Fallible<Ty<I>> {
if let Some(index) = bound_var.index_if_innermost() {
match self.parameters[index].data(self.interner()) {
GenericArgData::Ty(t) => {
Ok(t.clone().shifted_in_from(self.interner(), outer_binder))
}
_ => panic!("mismatched kinds in substitution"),
}
} else {
Ok(bound_var
.shifted_out()
.expect("cannot fail because this is not the innermost")
.shifted_in_from(outer_binder)
.to_ty(self.interner()))
}
}
/// see `fold_free_var_ty`
fn fold_free_var_lifetime(
&mut self,
bound_var: BoundVar,
outer_binder: DebruijnIndex,
) -> Fallible<Lifetime<I>> {
if let Some(index) = bound_var.index_if_innermost() {
match self.parameters[index].data(self.interner()) {
GenericArgData::Lifetime(l) => {
Ok(l.clone().shifted_in_from(self.interner(), outer_binder))
}
_ => panic!("mismatched kinds in substitution"),
}
} else {
Ok(bound_var
.shifted_out()
.unwrap()
.shifted_in_from(outer_binder)
.to_lifetime(self.interner()))
}
}
/// see `fold_free_var_ty`
fn fold_free_var_const(
&mut self,
ty: Ty<I>,
bound_var: BoundVar,
outer_binder: DebruijnIndex,
) -> Fallible<Const<I>> {
if let Some(index) = bound_var.index_if_innermost() {
match self.parameters[index].data(self.interner()) {
GenericArgData::Const(c) => {
Ok(c.clone().shifted_in_from(self.interner(), outer_binder))
}
_ => panic!("mismatched kinds in substitution"),
}
} else {
Ok(bound_var
.shifted_out()
.unwrap()
.shifted_in_from(outer_binder)
.to_const(self.interner(), ty))
}
}
fn interner(&self) -> I {
self.interner
}
}