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, 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 I,
}

impl<I: Interner> Subst<'_, '_, I> {
    /// Applies the substitution by folding
    pub fn apply<T: Fold<I, I>>(
        interner: &I,
        parameters: &[GenericArg<I>],
        value: &T,
    ) -> T::Result {
        value
            .fold_with(
                &mut Subst {
                    parameters,
                    interner,
                },
                DebruijnIndex::INNERMOST,
            )
            .unwrap()
    }
}

impl<'i, I: Interner> Folder<'i, I> for Subst<'_, 'i, I> {
    fn as_dyn(&mut self) -> &mut dyn Folder<'i, I> {
        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.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.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.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.clone()))
        }
    }

    fn interner(&self) -> &'i I {
        self.interner
    }

    fn target_interner(&self) -> &'i I {
        self.interner()
    }
}