revmc_codegen/bytecode/
interner.rs

1use indexmap::IndexSet;
2use oxc_index::Idx;
3use std::hash::{BuildHasher, Hash};
4
5/// A generic interner that deduplicates values and returns compact indices.
6///
7/// Backed by an [`IndexSet`] so that insertion is O(1) amortized and
8/// index-to-value lookup is O(1).
9pub(crate) struct Interner<I: Idx, T, S = alloy_primitives::map::DefaultHashBuilder> {
10    set: IndexSet<T, S>,
11    _marker: std::marker::PhantomData<fn() -> I>,
12}
13
14impl<I: Idx, T: Hash + Eq, S: BuildHasher + Default> Default for Interner<I, T, S> {
15    fn default() -> Self {
16        Self::new()
17    }
18}
19
20impl<I: Idx, T: Hash + Eq, S: BuildHasher + Default> Interner<I, T, S> {
21    pub(crate) fn new() -> Self {
22        Self::with_capacity(0)
23    }
24
25    pub(crate) fn with_capacity(capacity: usize) -> Self {
26        Self {
27            set: IndexSet::with_capacity_and_hasher(capacity, S::default()),
28            _marker: std::marker::PhantomData,
29        }
30    }
31
32    /// Interns a value, returning its deduplicated index.
33    pub(crate) fn intern(&mut self, value: T) -> I {
34        let (idx, _) = self.set.insert_full(value);
35        I::from_usize(idx)
36    }
37}
38
39impl<I: Idx, T, S> Interner<I, T, S> {
40    /// Returns the value at the given index.
41    #[inline]
42    pub(crate) fn get(&self, idx: I) -> &T {
43        &self.set[idx.index()]
44    }
45
46    #[inline]
47    #[allow(dead_code)]
48    pub(crate) fn len(&self) -> usize {
49        self.set.len()
50    }
51}
52
53impl<I: Idx, T, S> std::ops::Index<I> for Interner<I, T, S> {
54    type Output = T;
55
56    #[inline]
57    fn index(&self, idx: I) -> &T {
58        &self.set[idx.index()]
59    }
60}
61
62impl<I: Idx, T: std::fmt::Debug, S> std::fmt::Debug for Interner<I, T, S> {
63    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
64        f.debug_set().entries(self.set.iter()).finish()
65    }
66}
67
68#[cfg(test)]
69mod tests {
70    use super::*;
71    use crate::bytecode::Inst as TestIdx;
72
73    #[test]
74    fn deduplication() {
75        let mut interner = Interner::<TestIdx, &str>::new();
76        let a = interner.intern("hello");
77        let b = interner.intern("world");
78        let c = interner.intern("hello");
79        assert_eq!(a, c);
80        assert_ne!(a, b);
81        assert_eq!(interner.len(), 2);
82    }
83
84    #[test]
85    fn get_and_index() {
86        let mut interner = Interner::<TestIdx, u64>::new();
87        let idx = interner.intern(42);
88        assert_eq!(*interner.get(idx), 42);
89        assert_eq!(interner[idx], 42);
90    }
91
92    #[test]
93    fn stable_indices() {
94        let mut interner = Interner::<TestIdx, u64>::new();
95        let indices: Vec<_> = (0..100).map(|i| interner.intern(i)).collect();
96        // Re-interning produces the same indices.
97        for i in 0..100u64 {
98            assert_eq!(interner.intern(i), indices[i as usize]);
99        }
100        assert_eq!(interner.len(), 100);
101    }
102
103    #[test]
104    fn with_capacity() {
105        let mut interner = Interner::<TestIdx, &str>::with_capacity(16);
106        let idx = interner.intern("test");
107        assert_eq!(*interner.get(idx), "test");
108    }
109}
revmc_codegen/bytecode/interner.rs

revmc_codegen/bytecode/
interner.rs
