|
| 1 | +//! Data structures for interning interior nodes. |
| 2 | +//! |
| 3 | +//! Each graph needs stable IDs for its nodes and a way to reuse an existing ID when the same |
| 4 | +//! node is constructed again. The indexed vector owns the nodes; a hash table of IDs provides |
| 5 | +//! lookup without storing another copy of each node. |
| 6 | +
|
| 7 | +use std::hash::{BuildHasher, Hash}; |
| 8 | +use std::ops::Index; |
| 9 | + |
| 10 | +use hashbrown::{HashTable, hash_table::Entry}; |
| 11 | +use ruff_index::{Idx, IndexVec}; |
| 12 | +use rustc_hash::FxBuildHasher; |
| 13 | + |
| 14 | +/// An indexed collection of distinct nodes with a reverse table of their IDs. |
| 15 | +/// |
| 16 | +/// The vector owns each node at the index given by its stable ID. The hash table stores only |
| 17 | +/// IDs, hashing and comparing them by reading the corresponding nodes from the vector. Both |
| 18 | +/// collections are private, and [`Self::intern`] updates them together: every table entry |
| 19 | +/// refers to a node in the vector, and an equal node reuses that node's ID. Once the graph is |
| 20 | +/// built, [`Self::into_nodes_boxed_slice`] returns a boxed slice of nodes and drops the table. |
| 21 | +#[derive(Debug)] |
| 22 | +pub(crate) struct InternedNodes<I: Idx, N> { |
| 23 | + nodes: IndexVec<I, N>, |
| 24 | + ids: HashTable<I>, |
| 25 | +} |
| 26 | + |
| 27 | +impl<I: Idx, N> Default for InternedNodes<I, N> { |
| 28 | + fn default() -> Self { |
| 29 | + Self { |
| 30 | + nodes: IndexVec::default(), |
| 31 | + ids: HashTable::default(), |
| 32 | + } |
| 33 | + } |
| 34 | +} |
| 35 | + |
| 36 | +impl<I: Idx, N> InternedNodes<I, N> { |
| 37 | + pub(crate) const fn len(&self) -> usize { |
| 38 | + self.nodes.raw.len() |
| 39 | + } |
| 40 | + |
| 41 | + /// Consume `self` and return an iterator over the interned nodes. |
| 42 | + pub(crate) fn into_node_iterator(self) -> impl Iterator<Item = N> { |
| 43 | + self.nodes.into_iter() |
| 44 | + } |
| 45 | + |
| 46 | + /// Consume `self` and return a boxed slice of the interned nodes. |
| 47 | + pub(crate) fn into_nodes_boxed_slice(self) -> Box<[N]> { |
| 48 | + self.nodes.raw.into_boxed_slice() |
| 49 | + } |
| 50 | +} |
| 51 | + |
| 52 | +impl<I: Idx, N: Eq + Hash> InternedNodes<I, N> { |
| 53 | + pub(crate) fn find(&self, node: &N) -> Option<I> { |
| 54 | + self.ids |
| 55 | + .find(FxBuildHasher.hash_one(node), |id| self.nodes[*id].eq(node)) |
| 56 | + .copied() |
| 57 | + } |
| 58 | + |
| 59 | + /// Returns the node ID and whether the node was newly inserted. |
| 60 | + pub(crate) fn intern(&mut self, node: N) -> (I, bool) { |
| 61 | + let nodes = &mut self.nodes; |
| 62 | + match self.ids.entry( |
| 63 | + FxBuildHasher.hash_one(&node), |
| 64 | + |id| nodes[*id].eq(&node), |
| 65 | + |id| FxBuildHasher.hash_one(&nodes[*id]), |
| 66 | + ) { |
| 67 | + Entry::Occupied(entry) => (*entry.get(), false), |
| 68 | + Entry::Vacant(entry) => { |
| 69 | + let id = nodes.push(node); |
| 70 | + entry.insert(id); |
| 71 | + (id, true) |
| 72 | + } |
| 73 | + } |
| 74 | + } |
| 75 | +} |
| 76 | + |
| 77 | +impl<I: Idx, N> Index<I> for InternedNodes<I, N> { |
| 78 | + type Output = N; |
| 79 | + |
| 80 | + fn index(&self, id: I) -> &N { |
| 81 | + &self.nodes[id] |
| 82 | + } |
| 83 | +} |
0 commit comments