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

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