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
72    oxc_index::define_index_type! {
73        struct TestIdx = u32;
74    }
75
76    #[test]
77    fn deduplication() {
78        let mut interner = Interner::<TestIdx, &str>::new();
79        let a = interner.intern("hello");
80        let b = interner.intern("world");
81        let c = interner.intern("hello");
82        assert_eq!(a, c);
83        assert_ne!(a, b);
84        assert_eq!(interner.len(), 2);
85    }
86
87    #[test]
88    fn get_and_index() {
89        let mut interner = Interner::<TestIdx, u64>::new();
90        let idx = interner.intern(42);
91        assert_eq!(*interner.get(idx), 42);
92        assert_eq!(interner[idx], 42);
93    }
94
95    #[test]
96    fn stable_indices() {
97        let mut interner = Interner::<TestIdx, u64>::new();
98        let indices: Vec<_> = (0..100).map(|i| interner.intern(i)).collect();
99        // Re-interning produces the same indices.
100        for i in 0..100u64 {
101            assert_eq!(interner.intern(i), indices[i as usize]);
102        }
103        assert_eq!(interner.len(), 100);
104    }
105
106    #[test]
107    fn with_capacity() {
108        let mut interner = Interner::<TestIdx, &str>::with_capacity(16);
109        let idx = interner.intern("test");
110        assert_eq!(*interner.get(idx), "test");
111    }
112}
revmc_codegen/bytecode/interner.rs

revmc_codegen/bytecode/
interner.rs
