diff options
Diffstat (limited to 'vendor/chalk-solve-0.87.0/src/display/state.rs')
-rw-r--r-- | vendor/chalk-solve-0.87.0/src/display/state.rs | 352 |
1 files changed, 352 insertions, 0 deletions
diff --git a/vendor/chalk-solve-0.87.0/src/display/state.rs b/vendor/chalk-solve-0.87.0/src/display/state.rs new file mode 100644 index 000000000..fed2f5ca5 --- /dev/null +++ b/vendor/chalk-solve-0.87.0/src/display/state.rs @@ -0,0 +1,352 @@ +//! Persistent state passed down between writers. +//! +//! This is essentially `InternalWriterState` and other things supporting that. +use core::hash::Hash; +use std::{ + borrow::Borrow, + collections::BTreeMap, + fmt::{Debug, Display, Formatter, Result}, + marker::PhantomData, + rc::Rc, + sync::{Arc, Mutex}, +}; + +use crate::RustIrDatabase; +use chalk_ir::{interner::Interner, *}; +use indexmap::IndexMap; +use itertools::Itertools; + +/// Like a BoundVar, but with the debrujin index inverted so as to create a +/// canonical name we can use anywhere for each bound variable. +/// +/// In BoundVar, the innermost bound variables have debrujin index `0`, and +/// each further out BoundVar has a debrujin index `1` higher. +/// +/// In InvertedBoundVar, the outermost variables have inverted_debrujin_idx `0`, +/// and the innermost have their depth, not the other way around. +#[derive(Debug, Copy, Clone, PartialOrd, Ord, PartialEq, Eq)] +pub struct InvertedBoundVar { + /// The inverted debrujin index. Corresponds roughly to an inverted `DebrujinIndex::depth`. + inverted_debrujin_idx: i64, + /// The index within the debrujin index. Corresponds to `BoundVar::index`. + within_idx: IndexWithinBinding, +} + +impl Display for InvertedBoundVar { + fn fmt(&self, f: &mut Formatter<'_>) -> Result { + write!(f, "_{}_{}", self.inverted_debrujin_idx, self.within_idx) + } +} + +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] +enum UnifiedId<I: Interner> { + AdtId(I::InternedAdtId), + DefId(I::DefId), +} + +#[derive(Debug)] +pub struct IdAliasStore<T> { + /// Map from the DefIds we've encountered to a u32 alias id unique to all ids + /// the same name. + aliases: IndexMap<T, u32>, + /// Map from each name to the next unused u32 alias id. + next_unused_for_name: BTreeMap<String, u32>, +} + +impl<T> Default for IdAliasStore<T> { + fn default() -> Self { + IdAliasStore { + aliases: IndexMap::default(), + next_unused_for_name: BTreeMap::default(), + } + } +} + +impl<T: Copy + Eq + Hash> IdAliasStore<T> { + fn alias_for_id_name(&mut self, id: T, name: String) -> String { + let next_unused_for_name = &mut self.next_unused_for_name; + let alias = *self.aliases.entry(id).or_insert_with(|| { + let next_unused: &mut u32 = next_unused_for_name.entry(name.clone()).or_default(); + let id = *next_unused; + *next_unused += 1; + id + }); + // If there are no conflicts, keep the name the same so that we don't + // need name-agnostic equality in display tests. + if alias == 0 { + name + } else { + format!("{}_{}", name, alias) + } + } +} + +#[derive(Debug)] +struct IdAliases<I: Interner> { + id_aliases: IdAliasStore<UnifiedId<I>>, +} + +impl<I: Interner> Default for IdAliases<I> { + fn default() -> Self { + IdAliases { + id_aliases: IdAliasStore::default(), + } + } +} + +/// Writer state which persists across multiple writes. +/// +/// Currently, this means keeping track of what IDs have been given what names, +/// including deduplication information. +/// +/// This data is stored using interior mutability - clones will point to the same underlying +/// data. +/// +/// Uses a separate type, `P`, for the database stored inside to account for +/// `Arc` or wrapping other storage mediums. +#[derive(Debug)] +pub struct WriterState<I, DB: ?Sized, P = DB> +where + DB: RustIrDatabase<I>, + P: Borrow<DB>, + I: Interner, +{ + pub(super) db: P, + id_aliases: Arc<Mutex<IdAliases<I>>>, + _phantom: PhantomData<DB>, +} + +impl<I, DB: ?Sized, P> Clone for WriterState<I, DB, P> +where + DB: RustIrDatabase<I>, + P: Borrow<DB> + Clone, + I: Interner, +{ + fn clone(&self) -> Self { + WriterState { + db: self.db.clone(), + id_aliases: self.id_aliases.clone(), + _phantom: PhantomData, + } + } +} + +impl<I, DB: ?Sized, P> WriterState<I, DB, P> +where + DB: RustIrDatabase<I>, + P: Borrow<DB>, + I: Interner, +{ + pub fn new(db: P) -> Self { + WriterState { + db, + id_aliases: Arc::new(Mutex::new(IdAliases::default())), + _phantom: PhantomData, + } + } + + /// Returns a new version of self containing a wrapped database which + /// references the outer data. + /// + /// `f` will be run on the internal database, and the returned result will + /// wrap the result from `f`. For consistency, `f` should always contain the + /// given database, and must keep the same ID<->item relationships. + pub(super) fn wrap_db_ref<'a, DB2: ?Sized, P2, F>(&'a self, f: F) -> WriterState<I, DB2, P2> + where + DB2: RustIrDatabase<I>, + P2: Borrow<DB2>, + // We need to pass in `&'a P` specifically to guarantee that the `&P` + // can outlive the function body, and thus that it's safe to store `&P` + // in `P2`. + F: FnOnce(&'a P) -> P2, + { + WriterState { + db: f(&self.db), + id_aliases: self.id_aliases.clone(), + _phantom: PhantomData, + } + } + + pub(crate) fn db(&self) -> &DB { + self.db.borrow() + } +} + +/// Writer state for a single write call, persistent only as long as necessary +/// to write a single item. +/// +/// Stores things necessary for . +#[derive(Clone, Debug)] +pub(super) struct InternalWriterState<'a, I: Interner> { + persistent_state: WriterState<I, dyn RustIrDatabase<I> + 'a, &'a dyn RustIrDatabase<I>>, + indent_level: usize, + debrujin_indices_deep: u32, + // lowered_(inverted_debrujin_idx, index) -> src_correct_(inverted_debrujin_idx, index) + remapping: Rc<BTreeMap<InvertedBoundVar, InvertedBoundVar>>, + // the inverted_bound_var which maps to "Self" + self_mapping: Option<InvertedBoundVar>, +} + +type IndexWithinBinding = usize; + +impl<'a, I: Interner> InternalWriterState<'a, I> { + pub fn new<DB, P>(persistent_state: &'a WriterState<I, DB, P>) -> Self + where + DB: RustIrDatabase<I>, + P: Borrow<DB>, + { + InternalWriterState { + persistent_state: persistent_state + .wrap_db_ref(|db| db.borrow() as &dyn RustIrDatabase<I>), + indent_level: 0, + debrujin_indices_deep: 0, + remapping: Rc::new(BTreeMap::new()), + self_mapping: None, + } + } + + pub(super) fn db(&self) -> &dyn RustIrDatabase<I> { + self.persistent_state.db + } + + pub(super) fn add_indent(&self) -> Self { + InternalWriterState { + indent_level: self.indent_level + 1, + ..self.clone() + } + } + + pub(super) fn indent(&self) -> impl Display { + std::iter::repeat(" ").take(self.indent_level).format("") + } + + pub(super) fn alias_for_adt_id_name(&self, id: I::InternedAdtId, name: String) -> impl Display { + self.persistent_state + .id_aliases + .lock() + .unwrap() + .id_aliases + .alias_for_id_name(UnifiedId::AdtId(id), name) + } + + pub(super) fn alias_for_id_name(&self, id: I::DefId, name: String) -> impl Display { + self.persistent_state + .id_aliases + .lock() + .unwrap() + .id_aliases + .alias_for_id_name(UnifiedId::DefId(id), name) + } + + /// Adds a level of debrujin index, and possibly a "Self" parameter. + /// + /// This should be called whenever recursing into the value within a + /// [`Binders`]. + /// + /// If `self_binding` is `Some`, then it will introduce a new variable named + /// `Self` with the within-debrujin index given within and the innermost + /// debrujian index after increasing debrujin index. + #[must_use = "this returns a new `InternalWriterState`, and does not modify the existing one"] + pub(super) fn add_debrujin_index(&self, self_binding: Option<IndexWithinBinding>) -> Self { + let mut new_state = self.clone(); + new_state.debrujin_indices_deep += 1; + new_state.self_mapping = self_binding + .map(|idx| new_state.indices_for_introduced_bound_var(idx)) + .or(self.self_mapping); + new_state + } + + /// Adds parameter remapping. + /// + /// Each of the parameters in `lowered_vars` will be mapped to its + /// corresponding variable in `original_vars` when printed through the + /// `InternalWriterState` returned from this method. + /// + /// `lowered_vars` and `original_vars` must have the same length. + pub(super) fn add_parameter_mapping( + &self, + lowered_vars: impl Iterator<Item = InvertedBoundVar>, + original_vars: impl Iterator<Item = InvertedBoundVar>, + ) -> Self { + let remapping = self + .remapping + .iter() + .map(|(a, b)| (*a, *b)) + .chain(lowered_vars.zip(original_vars)) + .collect::<BTreeMap<_, _>>(); + + InternalWriterState { + remapping: Rc::new(remapping), + ..self.clone() + } + } + + /// Inverts the debrujin index so as to create a canonical name we can + /// anywhere for each bound variable. + /// + /// See [`InvertedBoundVar`][InvertedBoundVar]. + pub(super) fn invert_debrujin_idx( + &self, + debrujin_idx: u32, + index: IndexWithinBinding, + ) -> InvertedBoundVar { + InvertedBoundVar { + inverted_debrujin_idx: (self.debrujin_indices_deep as i64) - (debrujin_idx as i64), + within_idx: index, + } + } + + pub(super) fn apply_mappings(&self, b: InvertedBoundVar) -> impl Display { + let remapped = self.remapping.get(&b).copied().unwrap_or(b); + if self.self_mapping == Some(remapped) { + "Self".to_owned() + } else { + remapped.to_string() + } + } + + pub(super) fn indices_for_bound_var(&self, b: &BoundVar) -> InvertedBoundVar { + self.invert_debrujin_idx(b.debruijn.depth(), b.index) + } + + pub(super) fn indices_for_introduced_bound_var( + &self, + idx: IndexWithinBinding, + ) -> InvertedBoundVar { + // freshly introduced bound vars will always have debrujin index of 0, + // they're always "innermost". + self.invert_debrujin_idx(0, idx) + } + + pub(super) fn display_bound_var(&self, b: &BoundVar) -> impl Display { + self.apply_mappings(self.indices_for_bound_var(b)) + } + + pub(super) fn name_for_introduced_bound_var(&self, idx: IndexWithinBinding) -> impl Display { + self.apply_mappings(self.indices_for_introduced_bound_var(idx)) + } + + pub(super) fn binder_var_indices<'b>( + &'b self, + binders: &'b VariableKinds<I>, + ) -> impl Iterator<Item = InvertedBoundVar> + 'b { + binders + .iter(self.db().interner()) + .enumerate() + .map(move |(idx, _param)| self.indices_for_introduced_bound_var(idx)) + } + + pub(super) fn binder_var_display<'b>( + &'b self, + binders: &'b VariableKinds<I>, + ) -> impl Iterator<Item = String> + 'b { + binders + .iter(self.db().interner()) + .zip(self.binder_var_indices(binders)) + .map(move |(parameter, var)| match parameter { + VariableKind::Ty(_) => format!("{}", self.apply_mappings(var)), + VariableKind::Lifetime => format!("'{}", self.apply_mappings(var)), + VariableKind::Const(_ty) => format!("const {}", self.apply_mappings(var)), + }) + } +} |