vendor/chalk-ir-0.14.0/src/fold/shift.rs

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