From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- vendor/chalk-ir-0.80.0/src/fold/binder_impls.rs | 78 +++++++ vendor/chalk-ir-0.80.0/src/fold/boring_impls.rs | 256 +++++++++++++++++++++++ vendor/chalk-ir-0.80.0/src/fold/in_place.rs | 263 ++++++++++++++++++++++++ vendor/chalk-ir-0.80.0/src/fold/shift.rs | 185 +++++++++++++++++ vendor/chalk-ir-0.80.0/src/fold/subst.rs | 123 +++++++++++ 5 files changed, 905 insertions(+) create mode 100644 vendor/chalk-ir-0.80.0/src/fold/binder_impls.rs create mode 100644 vendor/chalk-ir-0.80.0/src/fold/boring_impls.rs create mode 100644 vendor/chalk-ir-0.80.0/src/fold/in_place.rs create mode 100644 vendor/chalk-ir-0.80.0/src/fold/shift.rs create mode 100644 vendor/chalk-ir-0.80.0/src/fold/subst.rs (limited to 'vendor/chalk-ir-0.80.0/src/fold') diff --git a/vendor/chalk-ir-0.80.0/src/fold/binder_impls.rs b/vendor/chalk-ir-0.80.0/src/fold/binder_impls.rs new file mode 100644 index 000000000..baa912499 --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/fold/binder_impls.rs @@ -0,0 +1,78 @@ +//! This module contains impls of `Fold` for those types that +//! introduce binders. +//! +//! The more interesting impls of `Fold` remain in the `fold` module. + +use crate::*; + +impl Fold for FnPointer { + type Result = FnPointer; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let FnPointer { + num_binders, + substitution, + sig, + } = self; + Ok(FnPointer { + num_binders, + substitution: substitution.fold_with(folder, outer_binder.shifted_in())?, + sig: FnSig { + abi: sig.abi, + safety: sig.safety, + variadic: sig.variadic, + }, + }) + } +} + +impl Fold for Binders +where + T: HasInterner + Fold, + >::Result: HasInterner, + I: Interner, +{ + type Result = Binders; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let Binders { + binders: self_binders, + value: self_value, + } = self; + let value = self_value.fold_with(folder, outer_binder.shifted_in())?; + let binders = VariableKinds { + interned: self_binders.interned().clone(), + }; + Ok(Binders::new(binders, value)) + } +} + +impl Fold for Canonical +where + I: Interner, + T: HasInterner + Fold, + >::Result: HasInterner, +{ + type Result = Canonical; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let Canonical { + binders: self_binders, + value: self_value, + } = self; + let value = self_value.fold_with(folder, outer_binder.shifted_in())?; + let binders = CanonicalVarKinds { + interned: self_binders.interned().clone(), + }; + Ok(Canonical { binders, value }) + } +} diff --git a/vendor/chalk-ir-0.80.0/src/fold/boring_impls.rs b/vendor/chalk-ir-0.80.0/src/fold/boring_impls.rs new file mode 100644 index 000000000..9210ecac8 --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/fold/boring_impls.rs @@ -0,0 +1,256 @@ +//! This module contains "rote and uninteresting" impls of `Fold` for +//! various types. In general, we prefer to derive `Fold`, but +//! sometimes that doesn't work for whatever reason. +//! +//! The more interesting impls of `Fold` remain in the `fold` module. + +use super::in_place; +use crate::*; +use std::marker::PhantomData; + +impl, I: Interner> Fold for Vec { + type Result = Vec; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + in_place::fallible_map_vec(self, |e| e.fold_with(folder, outer_binder)) + } +} + +impl, I: Interner> Fold for Box { + type Result = Box; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + in_place::fallible_map_box(self, |e| e.fold_with(folder, outer_binder)) + } +} + +macro_rules! tuple_fold { + ($($n:ident),*) => { + impl<$($n: Fold,)* I: Interner> Fold for ($($n,)*) { + type Result = ($($n::Result,)*); + fn fold_with(self, folder: &mut dyn Folder, outer_binder: DebruijnIndex) -> Result + { + #[allow(non_snake_case)] + let ($($n),*) = self; + Ok(($($n.fold_with(folder, outer_binder)?,)*)) + } + } + } +} + +tuple_fold!(A, B); +tuple_fold!(A, B, C); +tuple_fold!(A, B, C, D); +tuple_fold!(A, B, C, D, E); + +impl, I: Interner> Fold for Option { + type Result = Option; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + match self { + None => Ok(None), + Some(e) => Ok(Some(e.fold_with(folder, outer_binder)?)), + } + } +} + +impl Fold for GenericArg { + type Result = GenericArg; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let interner = folder.interner(); + + let data = self + .data(interner) + .clone() + .fold_with(folder, outer_binder)?; + Ok(GenericArg::new(interner, data)) + } +} + +impl Fold for Substitution { + type Result = Substitution; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let interner = folder.interner(); + + let folded = self + .iter(interner) + .cloned() + .map(|p| p.fold_with(folder, outer_binder)); + Substitution::from_fallible(interner, folded) + } +} + +impl Fold for Goals { + type Result = Goals; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let interner = folder.interner(); + let folded = self + .iter(interner) + .cloned() + .map(|p| p.fold_with(folder, outer_binder)); + Goals::from_fallible(interner, folded) + } +} + +impl Fold for ProgramClauses { + type Result = ProgramClauses; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let interner = folder.interner(); + let folded = self + .iter(interner) + .cloned() + .map(|p| p.fold_with(folder, outer_binder)); + ProgramClauses::from_fallible(interner, folded) + } +} + +impl Fold for QuantifiedWhereClauses { + type Result = QuantifiedWhereClauses; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let interner = folder.interner(); + let folded = self + .iter(interner) + .cloned() + .map(|p| p.fold_with(folder, outer_binder)); + QuantifiedWhereClauses::from_fallible(interner, folded) + } +} + +impl Fold for Constraints { + type Result = Constraints; + fn fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> Result { + let interner = folder.interner(); + let folded = self + .iter(interner) + .cloned() + .map(|p| p.fold_with(folder, outer_binder)); + Constraints::from_fallible(interner, folded) + } +} + +#[doc(hidden)] +#[macro_export] +macro_rules! copy_fold { + ($t:ty) => { + impl $crate::fold::Fold for $t { + type Result = Self; + fn fold_with( + self, + _folder: &mut dyn ($crate::fold::Folder), + _outer_binder: DebruijnIndex, + ) -> ::std::result::Result { + Ok(self) + } + } + }; +} + +copy_fold!(bool); +copy_fold!(usize); +copy_fold!(UniverseIndex); +copy_fold!(PlaceholderIndex); +copy_fold!(QuantifierKind); +copy_fold!(DebruijnIndex); +copy_fold!(()); +copy_fold!(UintTy); +copy_fold!(IntTy); +copy_fold!(FloatTy); +copy_fold!(Scalar); +copy_fold!(ClausePriority); +copy_fold!(Mutability); +copy_fold!(Safety); + +#[doc(hidden)] +#[macro_export] +macro_rules! id_fold { + ($t:ident) => { + impl $crate::fold::Fold for $t { + type Result = $t; + fn fold_with( + self, + _folder: &mut dyn ($crate::fold::Folder), + _outer_binder: DebruijnIndex, + ) -> ::std::result::Result { + Ok(self) + } + } + }; +} + +id_fold!(ImplId); +id_fold!(AdtId); +id_fold!(TraitId); +id_fold!(AssocTypeId); +id_fold!(OpaqueTyId); +id_fold!(FnDefId); +id_fold!(ClosureId); +id_fold!(GeneratorId); +id_fold!(ForeignDefId); + +impl SuperFold for ProgramClauseData { + fn super_fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> ::std::result::Result { + Ok(ProgramClauseData(self.0.fold_with(folder, outer_binder)?)) + } +} + +impl SuperFold for ProgramClause { + fn super_fold_with( + self, + folder: &mut dyn Folder, + outer_binder: DebruijnIndex, + ) -> ::std::result::Result { + let clause = self.data(folder.interner()).clone(); + Ok(clause + .super_fold_with(folder, outer_binder)? + .intern(folder.interner())) + } +} + +impl Fold for PhantomData { + type Result = PhantomData; + + fn fold_with( + self, + _folder: &mut dyn Folder, + _outer_binder: DebruijnIndex, + ) -> ::std::result::Result { + Ok(PhantomData) + } +} diff --git a/vendor/chalk-ir-0.80.0/src/fold/in_place.rs b/vendor/chalk-ir-0.80.0/src/fold/in_place.rs new file mode 100644 index 000000000..c81d9113a --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/fold/in_place.rs @@ -0,0 +1,263 @@ +//! Subroutines to help implementers of `Fold` avoid unnecessary heap allocations. + +use std::marker::PhantomData; +use std::{mem, ptr}; + +fn is_zst() -> bool { + mem::size_of::() == 0 +} + +fn is_layout_identical() -> bool { + mem::size_of::() == mem::size_of::() && mem::align_of::() == mem::align_of::() +} + +/// Maps a `Box` to a `Box`, reusing the underlying storage if possible. +pub(super) fn fallible_map_box( + b: Box, + map: impl FnOnce(T) -> Result, +) -> Result, E> { + // This optimization is only valid when `T` and `U` have the same size/alignment and is not + // useful for ZSTs. + if !is_layout_identical::() || is_zst::() { + return map(*b).map(Box::new); + } + + let raw = Box::into_raw(b); + unsafe { + let val = ptr::read(raw); + + // Box -> Box> + let mut raw: Box> = Box::from_raw(raw.cast()); + + // If `map` panics or returns an error, `raw` will free the memory associated with `b`, but + // not drop the boxed value itself since it is wrapped in `MaybeUninit`. This is what we + // want since the boxed value was moved into `map`. + let mapped_val = map(val)?; + ptr::write(raw.as_mut_ptr(), mapped_val); + + // Box> -> Box + Ok(Box::from_raw(Box::into_raw(raw).cast())) + } +} + +/// Maps a `Vec` to a `Vec`, reusing the underlying storage if possible. +pub(super) fn fallible_map_vec( + vec: Vec, + mut map: impl FnMut(T) -> Result, +) -> Result, E> { + // This optimization is only valid when `T` and `U` have the same size/alignment and is not + // useful for ZSTs. + if !is_layout_identical::() || is_zst::() { + return vec.into_iter().map(map).collect(); + } + + let mut vec = VecMappedInPlace::::new(vec); + + unsafe { + for i in 0..vec.len { + let place = vec.ptr.add(i); + let val = ptr::read(place); + + // Set `map_in_progress` so the drop impl for `VecMappedInPlace` can handle the other + // elements correctly in case `map` panics or returns an error. + vec.map_in_progress = i; + let mapped_val = map(val)?; + + ptr::write(place as *mut U, mapped_val); + } + + Ok(vec.finish()) + } +} + +/// Takes ownership of a `Vec` that is being mapped in place, cleaning up if the map fails. +struct VecMappedInPlace { + ptr: *mut T, + len: usize, + cap: usize, + + map_in_progress: usize, + _elem_tys: PhantomData<(T, U)>, +} + +impl VecMappedInPlace { + fn new(mut vec: Vec) -> Self { + assert!(is_layout_identical::()); + + // FIXME: This is just `Vec::into_raw_parts`. Use that instead when it is stabilized. + let ptr = vec.as_mut_ptr(); + let len = vec.len(); + let cap = vec.capacity(); + mem::forget(vec); + + VecMappedInPlace { + ptr, + len, + cap, + + map_in_progress: 0, + _elem_tys: PhantomData, + } + } + + /// Converts back into a `Vec` once the map is complete. + unsafe fn finish(self) -> Vec { + let this = mem::ManuallyDrop::new(self); + Vec::from_raw_parts(this.ptr as *mut U, this.len, this.cap) + } +} + +/// `VecMappedInPlace` drops everything but the element that was passed to `map` when it panicked or +/// returned an error. Everything before that index in the vector has type `U` (it has been mapped) +/// and everything after it has type `T` (it has not been mapped). +/// +/// ```text +/// mapped +/// | not yet mapped +/// |----| |-----| +/// [UUUU UxTT TTTT] +/// ^ +/// `map_in_progress` (not dropped) +/// ``` +impl Drop for VecMappedInPlace { + fn drop(&mut self) { + // Drop mapped elements of type `U`. + for i in 0..self.map_in_progress { + unsafe { + ptr::drop_in_place(self.ptr.add(i) as *mut U); + } + } + + // Drop unmapped elements of type `T`. + for i in (self.map_in_progress + 1)..self.len { + unsafe { + ptr::drop_in_place(self.ptr.add(i)); + } + } + + // Free the underlying storage for the `Vec`. + // `len` is 0 because the elements were handled above. + unsafe { + Vec::from_raw_parts(self.ptr, 0, self.cap); + } + } +} + +#[cfg(test)] +mod tests { + use std::fmt; + use std::sync::{Arc, Mutex}; + + /// A wrapper around `T` that records when it is dropped. + struct RecordDrop { + id: T, + drops: Arc>>, + } + + impl RecordDrop { + fn new(id: T, drops: &Arc>>) -> Self { + RecordDrop { + id, + drops: drops.clone(), + } + } + } + + impl RecordDrop { + fn map_to_char(self) -> RecordDrop { + let this = std::mem::ManuallyDrop::new(self); + RecordDrop { + id: (this.id + b'A') as char, + drops: this.drops.clone(), + } + } + } + + impl Drop for RecordDrop { + fn drop(&mut self) { + self.drops.lock().unwrap().push(format!("{}", self.id)); + } + } + + #[test] + fn vec_no_cleanup_after_success() { + let drops = Arc::new(Mutex::new(Vec::new())); + let to_fold = (0u8..5).map(|i| RecordDrop::new(i, &drops)).collect(); + + let res: Result<_, ()> = super::fallible_map_vec(to_fold, |x| Ok(x.map_to_char())); + + assert!(res.is_ok()); + assert!(drops.lock().unwrap().is_empty()); + } + + #[test] + fn vec_cleanup_after_panic() { + let drops = Arc::new(Mutex::new(Vec::new())); + let to_fold = (0u8..5).map(|i| RecordDrop::new(i, &drops)).collect(); + + let res = std::panic::catch_unwind(|| { + let _: Result<_, ()> = super::fallible_map_vec(to_fold, |x| { + if x.id == 3 { + panic!(); + } + + Ok(x.map_to_char()) + }); + }); + + assert!(res.is_err()); + assert_eq!(*drops.lock().unwrap(), &["3", "A", "B", "C", "4"]); + } + + #[test] + fn vec_cleanup_after_early_return() { + let drops = Arc::new(Mutex::new(Vec::new())); + let to_fold = (0u8..5).map(|i| RecordDrop::new(i, &drops)).collect(); + + let res = super::fallible_map_vec(to_fold, |x| { + if x.id == 2 { + return Err(()); + } + + Ok(x.map_to_char()) + }); + + assert!(res.is_err()); + assert_eq!(*drops.lock().unwrap(), &["2", "A", "B", "3", "4"]); + } + + #[test] + fn box_no_cleanup_after_success() { + let drops = Arc::new(Mutex::new(Vec::new())); + let to_fold = Box::new(RecordDrop::new(0, &drops)); + + let res: Result, ()> = super::fallible_map_box(to_fold, |x| Ok(x.map_to_char())); + + assert!(res.is_ok()); + assert!(drops.lock().unwrap().is_empty()); + } + + #[test] + fn box_cleanup_after_panic() { + let drops = Arc::new(Mutex::new(Vec::new())); + let to_fold = Box::new(RecordDrop::new(0, &drops)); + + let res = std::panic::catch_unwind(|| { + let _: Result, ()> = super::fallible_map_box(to_fold, |_| panic!()); + }); + + assert!(res.is_err()); + assert_eq!(*drops.lock().unwrap(), &["0"]); + } + + #[test] + fn box_cleanup_after_early_return() { + let drops = Arc::new(Mutex::new(Vec::new())); + let to_fold = Box::new(RecordDrop::new(0, &drops)); + + let res: Result, _> = super::fallible_map_box(to_fold, |_| Err(())); + + assert!(res.is_err()); + assert_eq!(*drops.lock().unwrap(), &["0"]); + } +} diff --git a/vendor/chalk-ir-0.80.0/src/fold/shift.rs b/vendor/chalk-ir-0.80.0/src/fold/shift.rs new file mode 100644 index 000000000..2ea957b28 --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/fold/shift.rs @@ -0,0 +1,185 @@ +//! Shifting of debruijn indices + +use super::Fold; +use crate::*; + +/// Methods for converting debruijn indices to move values into or out +/// of binders. +pub trait Shift: Fold { + /// Shifts this term in one level of binders. + fn shifted_in(self, interner: I) -> Self::Result; + + /// Shifts a term valid at `outer_binder` so that it is + /// valid at the innermost binder. See [`DebruijnIndex::shifted_in_from`] + /// for a detailed explanation. + fn shifted_in_from(self, interner: I, source_binder: DebruijnIndex) -> Self::Result; + + /// Shifts this term out one level of binders. + fn shifted_out(self, interner: I) -> Fallible; + + /// Shifts a term valid at the innermost binder so that it is + /// valid at `outer_binder`. See [`DebruijnIndex::shifted_out_to`] + /// for a detailed explanation. + fn shifted_out_to(self, interner: I, target_binder: DebruijnIndex) -> Fallible; +} + +impl, I: Interner> Shift for T { + fn shifted_in(self, interner: I) -> Self::Result { + self.shifted_in_from(interner, DebruijnIndex::ONE) + } + + fn shifted_in_from(self, interner: I, source_binder: DebruijnIndex) -> T::Result { + self.fold_with( + &mut Shifter { + source_binder, + interner, + }, + DebruijnIndex::INNERMOST, + ) + .unwrap() + } + + fn shifted_out_to(self, interner: I, target_binder: DebruijnIndex) -> Fallible { + self.fold_with( + &mut DownShifter { + target_binder, + interner, + }, + DebruijnIndex::INNERMOST, + ) + } + + fn shifted_out(self, interner: I) -> Fallible { + self.shifted_out_to(interner, DebruijnIndex::ONE) + } +} + +/// A folder that adjusts debruijn indices by a certain amount. +struct Shifter { + source_binder: DebruijnIndex, + interner: I, +} + +impl Shifter { + /// Given a free variable at `depth`, shifts that depth to `depth + /// + self.adjustment`, and then wraps *that* within the internal + /// set `binders`. + fn adjust(&self, bound_var: BoundVar, outer_binder: DebruijnIndex) -> BoundVar { + bound_var + .shifted_in_from(self.source_binder) + .shifted_in_from(outer_binder) + } +} + +impl Folder for Shifter { + type Error = NoSolution; + + fn as_dyn(&mut self) -> &mut dyn Folder { + self + } + + fn fold_free_var_ty( + &mut self, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + Ok(TyKind::::BoundVar(self.adjust(bound_var, outer_binder)).intern(self.interner())) + } + + fn fold_free_var_lifetime( + &mut self, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + Ok( + LifetimeData::::BoundVar(self.adjust(bound_var, outer_binder)) + .intern(self.interner()), + ) + } + + fn fold_free_var_const( + &mut self, + ty: Ty, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + // const types don't have free variables, so we can skip folding `ty` + Ok(self + .adjust(bound_var, outer_binder) + .to_const(self.interner(), ty)) + } + + fn interner(&self) -> I { + self.interner + } +} + +//--------------------------------------------------------------------------- + +/// A shifter that reduces debruijn indices -- in other words, which lifts a value +/// *out* from binders. Consider this example: +/// +struct DownShifter { + target_binder: DebruijnIndex, + interner: I, +} + +impl DownShifter { + /// Given a reference to a free variable at depth `depth` + /// (appearing within `binders` internal binders), attempts to + /// lift that free variable out from `adjustment` levels of + /// binders (i.e., convert it to depth `depth - + /// self.adjustment`). If the free variable is bound by one of + /// those internal binders (i.e., `depth < self.adjustment`) the + /// this will fail with `Err`. Otherwise, returns the variable at + /// this new depth (but adjusted to appear within `binders`). + fn adjust(&self, bound_var: BoundVar, outer_binder: DebruijnIndex) -> Fallible { + match bound_var.shifted_out_to(self.target_binder) { + Some(bound_var1) => Ok(bound_var1.shifted_in_from(outer_binder)), + None => Err(NoSolution), + } + } +} + +impl Folder for DownShifter { + type Error = NoSolution; + + fn as_dyn(&mut self) -> &mut dyn Folder { + self + } + + fn fold_free_var_ty( + &mut self, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + Ok(TyKind::::BoundVar(self.adjust(bound_var, outer_binder)?).intern(self.interner())) + } + + fn fold_free_var_lifetime( + &mut self, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + Ok( + LifetimeData::::BoundVar(self.adjust(bound_var, outer_binder)?) + .intern(self.interner()), + ) + } + + fn fold_free_var_const( + &mut self, + ty: Ty, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + // const types don't have free variables, so we can skip folding `ty` + Ok(self + .adjust(bound_var, outer_binder)? + .to_const(self.interner(), ty)) + } + + fn interner(&self) -> I { + self.interner + } +} diff --git a/vendor/chalk-ir-0.80.0/src/fold/subst.rs b/vendor/chalk-ir-0.80.0/src/fold/subst.rs new file mode 100644 index 000000000..f7a0b2d69 --- /dev/null +++ b/vendor/chalk-ir-0.80.0/src/fold/subst.rs @@ -0,0 +1,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], + interner: I, +} + +impl Subst<'_, I> { + /// Applies the substitution by folding + pub fn apply>(interner: I, parameters: &[GenericArg], value: T) -> T::Result { + value + .fold_with( + &mut Subst { + parameters, + interner, + }, + DebruijnIndex::INNERMOST, + ) + .unwrap() + } +} + +impl Folder for Subst<'_, I> { + type Error = NoSolution; + + fn as_dyn(&mut self) -> &mut dyn Folder { + self + } + + /// We are eliminating one binder, but binders outside of that get preserved. + /// + /// So e.g. consider this: + /// + /// ```notrust + /// for { for { [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` binder we are eliminating). + /// + /// This gives us as a result: + /// + /// ```notrust + /// for { [A, u32] } + /// ^ represented as `^0.0` + /// ``` + fn fold_free_var_ty( + &mut self, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + 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> { + 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, + bound_var: BoundVar, + outer_binder: DebruijnIndex, + ) -> Fallible> { + 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 + } +} -- cgit v1.2.3