foundry_evm_symbolic/runtime/expr/
hashcons.rs

1use alloy_primitives::map::foldhash::fast::FixedState;
2use hashbrown::{HashTable, hash_table::Entry};
3use std::{
4    cmp::Ordering,
5    fmt,
6    hash::{BuildHasher, Hash, Hasher},
7    sync::{Arc, Weak},
8};
9
10/// Shared handle for a hash-consed value.
11///
12/// Equality is pointer equality only. Hashing writes the cached structural hash
13/// instead of walking the value.
14pub(in crate::runtime) struct HashConsed<T> {
15    inner: Arc<HashConsedInner<T>>,
16}
17
18struct HashConsedInner<T> {
19    hash: u64,
20    value: T,
21}
22
23impl<T> HashConsed<T> {
24    #[inline]
25    pub(in crate::runtime::expr) fn stable_hash_cmp(&self, other: &Self) -> Ordering {
26        self.inner.hash.cmp(&other.inner.hash)
27    }
28
29    /// Orders nodes within one hash-consing context without inspecting or rendering their value.
30    ///
31    /// The cached structural hash handles the common case. Pointer identity is only a tie-breaker
32    /// for distinct nodes with the same hash; structurally equal values share one node.
33    #[inline]
34    pub(in crate::runtime::expr) fn identity_cmp(&self, other: &Self) -> Ordering {
35        self.stable_hash_cmp(other).then_with(|| {
36            let left = Arc::as_ptr(&self.inner);
37            let right = Arc::as_ptr(&other.inner);
38            left.cmp(&right)
39        })
40    }
41
42    #[inline]
43    pub(in crate::runtime) fn value(&self) -> &T {
44        &self.inner.value
45    }
46}
47
48impl<T> Clone for HashConsed<T> {
49    #[inline]
50    fn clone(&self) -> Self {
51        Self { inner: self.inner.clone() }
52    }
53}
54
55impl<T> PartialEq for HashConsed<T> {
56    #[inline]
57    fn eq(&self, other: &Self) -> bool {
58        Arc::ptr_eq(&self.inner, &other.inner)
59    }
60}
61
62impl<T> Eq for HashConsed<T> {}
63
64impl<T> Hash for HashConsed<T> {
65    #[inline]
66    fn hash<H: Hasher>(&self, state: &mut H) {
67        self.inner.hash.hash(state);
68    }
69}
70
71impl<T: PartialOrd> PartialOrd for HashConsed<T> {
72    #[inline]
73    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
74        self.value().partial_cmp(other.value())
75    }
76}
77
78impl<T: Ord> Ord for HashConsed<T> {
79    #[inline]
80    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
81        self.value().cmp(other.value())
82    }
83}
84
85impl<T: fmt::Debug> fmt::Debug for HashConsed<T> {
86    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
87        self.value().fmt(f)
88    }
89}
90
91const MIN_GC_THRESHOLD: usize = 1024;
92
93/// Hash-consing table for sharing structurally equal immutable values.
94///
95/// The table stores weak references so interned values disappear when the rest of
96/// the symbolic state stops using them. `make` removes dead entries encountered
97/// during lookup and periodically sweeps distinct dead values before they can
98/// grow the table without bound.
99pub(in crate::runtime) struct HashCons<T> {
100    table: HashTable<HashConsEntry<T>>,
101    hash_builder: FixedState,
102    gc_threshold: usize,
103}
104
105struct HashConsEntry<T> {
106    hash: u64,
107    value: Weak<HashConsedInner<T>>,
108}
109
110impl<T> HashConsEntry<T> {
111    const fn hash(&self) -> u64 {
112        self.hash
113    }
114}
115
116impl<T> HashCons<T> {
117    pub(in crate::runtime) fn new() -> Self {
118        Self {
119            table: HashTable::new(),
120            hash_builder: FixedState::default(),
121            gc_threshold: MIN_GC_THRESHOLD,
122        }
123    }
124
125    fn hash<Q: Hash + ?Sized>(&self, value: &Q) -> u64 {
126        self.hash_builder.hash_one(value)
127    }
128}
129
130impl<T: Eq + Hash> HashCons<T> {
131    pub(in crate::runtime) fn make(&mut self, value: T) -> HashConsed<T> {
132        if self.table.len() >= self.gc_threshold {
133            self.table.retain(|entry| entry.value.strong_count() != 0);
134            self.gc_threshold = self.table.len().saturating_mul(2).max(MIN_GC_THRESHOLD);
135        }
136
137        let hash = self.hash(&value);
138        loop {
139            let mut found = None;
140            let mut matched_dead_entry = false;
141            match self.table.entry(
142                hash,
143                |entry| {
144                    if entry.hash() != hash {
145                        return false;
146                    }
147                    match entry.value.upgrade() {
148                        Some(existing) if existing.value == value => {
149                            found = Some(existing);
150                            true
151                        }
152                        None => {
153                            matched_dead_entry = true;
154                            true
155                        }
156                        Some(_) => false,
157                    }
158                },
159                HashConsEntry::hash,
160            ) {
161                Entry::Occupied(entry) => {
162                    if let Some(inner) = found {
163                        return HashConsed { inner };
164                    }
165                    debug_assert!(matched_dead_entry);
166                    let _ = entry.remove();
167                }
168                Entry::Vacant(entry) => {
169                    let inner = Arc::new(HashConsedInner { hash, value });
170                    entry.insert(HashConsEntry { hash, value: Arc::downgrade(&inner) });
171                    return HashConsed { inner };
172                }
173            }
174        }
175    }
176}
foundry_evm_symbolic/runtime/expr/hashcons.rs

foundry_evm_symbolic/runtime/expr/
hashcons.rs
