vendor/chalk-solve/src/clauses/generalize.rs

   1 //! This gets rid of free variables in a type by replacing them by fresh bound
   2 //! ones. We use this when building clauses that contain types passed to
   3 //! `program_clauses`; these may contain variables, and just copying those
   4 //! variables verbatim leads to problems. Instead, we return a slightly more
   5 //! general program clause, with new variables in those places. This can only
   6 //! happen with `dyn Trait` currently; that's the only case where we use the
   7 //! types passed to `program_clauses` in the clauses we generate.
   8
   9 use chalk_ir::{
  10     fold::{Fold, Folder},
  11     interner::{HasInterner, Interner},
  12     Binders, BoundVar, DebruijnIndex, Fallible, Lifetime, LifetimeData, Ty, TyData, TyKind,
  13     VariableKind, VariableKinds,
  14 };
  15 use rustc_hash::FxHashMap;
  16
  17 pub struct Generalize<'i, I: Interner> {
  18     binders: Vec<VariableKind<I>>,
  19     mapping: FxHashMap<BoundVar, usize>,
  20     interner: &'i I,
  21 }
  22
  23 impl<I: Interner> Generalize<'_, I> {
  24     pub fn apply<T>(interner: &I, value: &T) -> Binders<T::Result>
  25     where
  26         T: HasInterner<Interner = I> + Fold<I, I>,
  27         T::Result: HasInterner<Interner = I>,
  28     {
  29         let mut generalize = Generalize {
  30             binders: Vec::new(),
  31             mapping: FxHashMap::default(),
  32             interner,
  33         };
  34         let value = value
  35             .fold_with(&mut generalize, DebruijnIndex::INNERMOST)
  36             .unwrap();
  37         Binders::new(
  38             VariableKinds::from_iter(interner, generalize.binders),
  39             value,
  40         )
  41     }
  42 }
  43
  44 impl<'i, I: Interner> Folder<'i, I> for Generalize<'i, I> {
  45     fn as_dyn(&mut self) -> &mut dyn Folder<'i, I> {
  46         self
  47     }
  48
  49     fn fold_free_var_ty(
  50         &mut self,
  51         bound_var: BoundVar,
  52         outer_binder: DebruijnIndex,
  53     ) -> Fallible<Ty<I>> {
  54         let binder_vec = &mut self.binders;
  55         let new_index = self.mapping.entry(bound_var).or_insert_with(|| {
  56             let i = binder_vec.len();
  57             binder_vec.push(VariableKind::Ty(TyKind::General));
  58             i
  59         });
  60         let new_var = BoundVar::new(outer_binder, *new_index);
  61         Ok(TyData::BoundVar(new_var).intern(self.interner()))
  62     }
  63
  64     fn fold_free_var_lifetime(
  65         &mut self,
  66         bound_var: BoundVar,
  67         outer_binder: DebruijnIndex,
  68     ) -> Fallible<Lifetime<I>> {
  69         let binder_vec = &mut self.binders;
  70         let new_index = self.mapping.entry(bound_var).or_insert_with(|| {
  71             let i = binder_vec.len();
  72             binder_vec.push(VariableKind::Lifetime);
  73             i
  74         });
  75         let new_var = BoundVar::new(outer_binder, *new_index);
  76         Ok(LifetimeData::BoundVar(new_var).intern(self.interner()))
  77     }
  78
  79     fn interner(&self) -> &'i I {
  80         self.interner
  81     }
  82
  83     fn target_interner(&self) -> &'i I {
  84         self.interner
  85     }
  86 }