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

   1 //! Shifting of debruijn indices
   2
   3 use crate::*;
   4
   5 /// Methods for converting debruijn indices to move values into or out
   6 /// of binders.
   7 pub 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
  25 impl<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)]
  58 struct Shifter<I: Interner> {
  59     source_binder: DebruijnIndex,
  60     interner: I,
  61 }
  62
  63 impl<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
  74 impl<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 ///
 114 struct DownShifter<I> {
 115     target_binder: DebruijnIndex,
 116     interner: I,
 117 }
 118
 119 impl<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
 136 impl<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 }