vendor/chalk-solve/src/display/state.rs

   1 //! Persistent state passed down between writers.
   2 //!
   3 //! This is essentially `InternalWriterState` and other things supporting that.
   4 use core::hash::Hash;
   5 use std::{
   6     borrow::Borrow,
   7     collections::BTreeMap,
   8     fmt::{Debug, Display, Formatter, Result},
   9     marker::PhantomData,
  10     rc::Rc,
  11     sync::{Arc, Mutex},
  12 };
  13
  14 use crate::RustIrDatabase;
  15 use chalk_ir::{interner::Interner, *};
  16 use indexmap::IndexMap;
  17 use itertools::Itertools;
  18
  19 /// Like a BoundVar, but with the debrujin index inverted so as to create a
  20 /// canonical name we can use anywhere for each bound variable.
  21 ///
  22 /// In BoundVar, the innermost bound variables have debrujin index `0`, and
  23 /// each further out BoundVar has a debrujin index `1` higher.
  24 ///
  25 /// In InvertedBoundVar, the outermost variables have inverted_debrujin_idx `0`,
  26 /// and the innermost have their depth, not the other way around.
  27 #[derive(Debug, Copy, Clone, PartialOrd, Ord, PartialEq, Eq)]
  28 pub struct InvertedBoundVar {
  29     /// The inverted debrujin index. Corresponds roughly to an inverted `DebrujinIndex::depth`.
  30     inverted_debrujin_idx: i64,
  31     /// The index within the debrujin index. Corresponds to `BoundVar::index`.
  32     within_idx: IndexWithinBinding,
  33 }
  34
  35 impl Display for InvertedBoundVar {
  36     fn fmt(&self, f: &mut Formatter<'_>) -> Result {
  37         write!(f, "_{}_{}", self.inverted_debrujin_idx, self.within_idx)
  38     }
  39 }
  40
  41 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
  42 enum UnifiedId<I: Interner> {
  43     AdtId(I::InternedAdtId),
  44     DefId(I::DefId),
  45 }
  46
  47 #[derive(Debug)]
  48 pub struct IdAliasStore<T> {
  49     /// Map from the DefIds we've encountered to a u32 alias id unique to all ids
  50     /// the same name.
  51     aliases: IndexMap<T, u32>,
  52     /// Map from each name to the next unused u32 alias id.
  53     next_unused_for_name: BTreeMap<String, u32>,
  54 }
  55
  56 impl<T> Default for IdAliasStore<T> {
  57     fn default() -> Self {
  58         IdAliasStore {
  59             aliases: IndexMap::default(),
  60             next_unused_for_name: BTreeMap::default(),
  61         }
  62     }
  63 }
  64
  65 impl<T: Copy + Eq + Hash> IdAliasStore<T> {
  66     fn alias_for_id_name(&mut self, id: T, name: String) -> String {
  67         let next_unused_for_name = &mut self.next_unused_for_name;
  68         let alias = *self.aliases.entry(id).or_insert_with(|| {
  69             let next_unused: &mut u32 = next_unused_for_name.entry(name.clone()).or_default();
  70             let id = *next_unused;
  71             *next_unused += 1;
  72             id
  73         });
  74         // If there are no conflicts, keep the name the same so that we don't
  75         // need name-agnostic equality in display tests.
  76         if alias == 0 {
  77             name
  78         } else {
  79             format!("{}_{}", name, alias)
  80         }
  81     }
  82 }
  83
  84 #[derive(Debug)]
  85 struct IdAliases<I: Interner> {
  86     id_aliases: IdAliasStore<UnifiedId<I>>,
  87 }
  88
  89 impl<I: Interner> Default for IdAliases<I> {
  90     fn default() -> Self {
  91         IdAliases {
  92             id_aliases: IdAliasStore::default(),
  93         }
  94     }
  95 }
  96
  97 /// Writer state which persists across multiple writes.
  98 ///
  99 /// Currently, this means keeping track of what IDs have been given what names,
 100 /// including deduplication information.
 101 ///
 102 /// This data is stored using interior mutability - clones will point to the same underlying
 103 /// data.
 104 ///
 105 /// Uses a separate type, `P`, for the database stored inside to account for
 106 /// `Arc` or wrapping other storage mediums.
 107 #[derive(Debug)]
 108 pub struct WriterState<I, DB: ?Sized, P = DB>
 109 where
 110     DB: RustIrDatabase<I>,
 111     P: Borrow<DB>,
 112     I: Interner,
 113 {
 114     pub(super) db: P,
 115     id_aliases: Arc<Mutex<IdAliases<I>>>,
 116     _phantom: PhantomData<DB>,
 117 }
 118
 119 impl<I, DB: ?Sized, P> Clone for WriterState<I, DB, P>
 120 where
 121     DB: RustIrDatabase<I>,
 122     P: Borrow<DB> + Clone,
 123     I: Interner,
 124 {
 125     fn clone(&self) -> Self {
 126         WriterState {
 127             db: self.db.clone(),
 128             id_aliases: self.id_aliases.clone(),
 129             _phantom: PhantomData,
 130         }
 131     }
 132 }
 133
 134 impl<I, DB: ?Sized, P> WriterState<I, DB, P>
 135 where
 136     DB: RustIrDatabase<I>,
 137     P: Borrow<DB>,
 138     I: Interner,
 139 {
 140     pub fn new(db: P) -> Self {
 141         WriterState {
 142             db,
 143             id_aliases: Arc::new(Mutex::new(IdAliases::default())),
 144             _phantom: PhantomData,
 145         }
 146     }
 147
 148     /// Returns a new version of self containing a wrapped database which
 149     /// references the outer data.
 150     ///
 151     /// `f` will be run on the internal database, and the returned result will
 152     /// wrap the result from `f`. For consistency, `f` should always contain the
 153     /// given database, and must keep the same ID<->item relationships.
 154     pub(super) fn wrap_db_ref<'a, DB2: ?Sized, P2, F>(&'a self, f: F) -> WriterState<I, DB2, P2>
 155     where
 156         DB2: RustIrDatabase<I>,
 157         P2: Borrow<DB2>,
 158         // We need to pass in `&'a P` specifically to guarantee that the `&P`
 159         // can outlive the function body, and thus that it's safe to store `&P`
 160         // in `P2`.
 161         F: FnOnce(&'a P) -> P2,
 162     {
 163         WriterState {
 164             db: f(&self.db),
 165             id_aliases: self.id_aliases.clone(),
 166             _phantom: PhantomData,
 167         }
 168     }
 169
 170     pub(crate) fn db(&self) -> &DB {
 171         self.db.borrow()
 172     }
 173 }
 174
 175 /// Writer state for a single write call, persistent only as long as necessary
 176 /// to write a single item.
 177 ///
 178 /// Stores things necessary for .
 179 #[derive(Clone, Debug)]
 180 pub(super) struct InternalWriterState<'a, I: Interner> {
 181     persistent_state: WriterState<I, dyn RustIrDatabase<I> + 'a, &'a dyn RustIrDatabase<I>>,
 182     indent_level: usize,
 183     debrujin_indices_deep: u32,
 184     // lowered_(inverted_debrujin_idx, index) -> src_correct_(inverted_debrujin_idx, index)
 185     remapping: Rc<BTreeMap<InvertedBoundVar, InvertedBoundVar>>,
 186     // the inverted_bound_var which maps to "Self"
 187     self_mapping: Option<InvertedBoundVar>,
 188 }
 189
 190 type IndexWithinBinding = usize;
 191
 192 impl<'a, I: Interner> InternalWriterState<'a, I> {
 193     pub fn new<DB, P>(persistent_state: &'a WriterState<I, DB, P>) -> Self
 194     where
 195         DB: RustIrDatabase<I>,
 196         P: Borrow<DB>,
 197     {
 198         InternalWriterState {
 199             persistent_state: persistent_state
 200                 .wrap_db_ref(|db| db.borrow() as &dyn RustIrDatabase<I>),
 201             indent_level: 0,
 202             debrujin_indices_deep: 0,
 203             remapping: Rc::new(BTreeMap::new()),
 204             self_mapping: None,
 205         }
 206     }
 207
 208     pub(super) fn db(&self) -> &dyn RustIrDatabase<I> {
 209         self.persistent_state.db
 210     }
 211
 212     pub(super) fn add_indent(&self) -> Self {
 213         InternalWriterState {
 214             indent_level: self.indent_level + 1,
 215             ..self.clone()
 216         }
 217     }
 218
 219     pub(super) fn indent(&self) -> impl Display {
 220         std::iter::repeat("  ").take(self.indent_level).format("")
 221     }
 222
 223     pub(super) fn alias_for_adt_id_name(&self, id: I::InternedAdtId, name: String) -> impl Display {
 224         self.persistent_state
 225             .id_aliases
 226             .lock()
 227             .unwrap()
 228             .id_aliases
 229             .alias_for_id_name(UnifiedId::AdtId(id), name)
 230     }
 231
 232     pub(super) fn alias_for_id_name(&self, id: I::DefId, name: String) -> impl Display {
 233         self.persistent_state
 234             .id_aliases
 235             .lock()
 236             .unwrap()
 237             .id_aliases
 238             .alias_for_id_name(UnifiedId::DefId(id), name)
 239     }
 240
 241     /// Adds a level of debrujin index, and possibly a "Self" parameter.
 242     ///
 243     /// This should be called whenever recursing into the value within a
 244     /// [`Binders`].
 245     ///
 246     /// If `self_binding` is `Some`, then it will introduce a new variable named
 247     /// `Self` with the within-debrujin index given within and the innermost
 248     /// debrujian index after increasing debrujin index.
 249     #[must_use = "this returns a new `InternalWriterState`, and does not modify the existing one"]
 250     pub(super) fn add_debrujin_index(&self, self_binding: Option<IndexWithinBinding>) -> Self {
 251         let mut new_state = self.clone();
 252         new_state.debrujin_indices_deep += 1;
 253         new_state.self_mapping = self_binding
 254             .map(|idx| new_state.indices_for_introduced_bound_var(idx))
 255             .or(self.self_mapping);
 256         new_state
 257     }
 258
 259     /// Adds parameter remapping.
 260     ///
 261     /// Each of the parameters in `lowered_vars` will be mapped to its
 262     /// corresponding variable in `original_vars` when printed through the
 263     /// `InternalWriterState` returned from this method.
 264     ///
 265     /// `lowered_vars` and `original_vars` must have the same length.
 266     pub(super) fn add_parameter_mapping(
 267         &self,
 268         lowered_vars: impl Iterator<Item = InvertedBoundVar>,
 269         original_vars: impl Iterator<Item = InvertedBoundVar>,
 270     ) -> Self {
 271         let remapping = self
 272             .remapping
 273             .iter()
 274             .map(|(a, b)| (*a, *b))
 275             .chain(lowered_vars.zip(original_vars))
 276             .collect::<BTreeMap<_, _>>();
 277
 278         InternalWriterState {
 279             remapping: Rc::new(remapping),
 280             ..self.clone()
 281         }
 282     }
 283
 284     /// Inverts the debrujin index so as to create a canonical name we can
 285     /// anywhere for each bound variable.
 286     ///
 287     /// See [`InvertedBoundVar`][InvertedBoundVar].
 288     pub(super) fn invert_debrujin_idx(
 289         &self,
 290         debrujin_idx: u32,
 291         index: IndexWithinBinding,
 292     ) -> InvertedBoundVar {
 293         InvertedBoundVar {
 294             inverted_debrujin_idx: (self.debrujin_indices_deep as i64) - (debrujin_idx as i64),
 295             within_idx: index,
 296         }
 297     }
 298
 299     pub(super) fn apply_mappings(&self, b: InvertedBoundVar) -> impl Display {
 300         let remapped = self.remapping.get(&b).copied().unwrap_or(b);
 301         if self.self_mapping == Some(remapped) {
 302             "Self".to_owned()
 303         } else {
 304             remapped.to_string()
 305         }
 306     }
 307
 308     pub(super) fn indices_for_bound_var(&self, b: &BoundVar) -> InvertedBoundVar {
 309         self.invert_debrujin_idx(b.debruijn.depth(), b.index)
 310     }
 311
 312     pub(super) fn indices_for_introduced_bound_var(
 313         &self,
 314         idx: IndexWithinBinding,
 315     ) -> InvertedBoundVar {
 316         // freshly introduced bound vars will always have debrujin index of 0,
 317         // they're always "innermost".
 318         self.invert_debrujin_idx(0, idx)
 319     }
 320
 321     pub(super) fn display_bound_var(&self, b: &BoundVar) -> impl Display {
 322         self.apply_mappings(self.indices_for_bound_var(b))
 323     }
 324
 325     pub(super) fn name_for_introduced_bound_var(&self, idx: IndexWithinBinding) -> impl Display {
 326         self.apply_mappings(self.indices_for_introduced_bound_var(idx))
 327     }
 328
 329     pub(super) fn binder_var_indices<'b>(
 330         &'b self,
 331         binders: &'b VariableKinds<I>,
 332     ) -> impl Iterator<Item = InvertedBoundVar> + 'b {
 333         binders
 334             .iter(self.db().interner())
 335             .enumerate()
 336             .map(move |(idx, _param)| self.indices_for_introduced_bound_var(idx))
 337     }
 338
 339     pub(super) fn binder_var_display<'b>(
 340         &'b self,
 341         binders: &'b VariableKinds<I>,
 342     ) -> impl Iterator<Item = String> + 'b {
 343         binders
 344             .iter(self.db().interner())
 345             .zip(self.binder_var_indices(binders))
 346             .map(move |(parameter, var)| match parameter {
 347                 VariableKind::Ty(_) => format!("{}", self.apply_mappings(var)),
 348                 VariableKind::Lifetime => format!("'{}", self.apply_mappings(var)),
 349                 VariableKind::Const(_ty) => format!("const {}", self.apply_mappings(var)),
 350             })
 351     }
 352 }