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    #[inline]
30    pub(in crate::runtime) fn value(&self) -> &T {
31        &self.inner.value
32    }
33
34    #[inline]
35    pub(in crate::runtime) fn into_value(self) -> T
36    where
37        T: Clone,
38    {
39        match Arc::try_unwrap(self.inner) {
40            Ok(inner) => inner.value,
41            Err(inner) => inner.value.clone(),
42        }
43    }
44}
45
46impl<T> Clone for HashConsed<T> {
47    #[inline]
48    fn clone(&self) -> Self {
49        Self { inner: self.inner.clone() }
50    }
51}
52
53impl<T> PartialEq for HashConsed<T> {
54    #[inline]
55    fn eq(&self, other: &Self) -> bool {
56        Arc::ptr_eq(&self.inner, &other.inner)
57    }
58}
59
60impl<T> Eq for HashConsed<T> {}
61
62impl<T> Hash for HashConsed<T> {
63    #[inline]
64    fn hash<H: Hasher>(&self, state: &mut H) {
65        self.inner.hash.hash(state);
66    }
67}
68
69impl<T: PartialOrd> PartialOrd for HashConsed<T> {
70    #[inline]
71    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
72        self.value().partial_cmp(other.value())
73    }
74}
75
76impl<T: Ord> Ord for HashConsed<T> {
77    #[inline]
78    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
79        self.value().cmp(other.value())
80    }
81}
82
83impl<T: fmt::Debug> fmt::Debug for HashConsed<T> {
84    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
85        self.value().fmt(f)
86    }
87}
88
89type HashConsHasher = FixedState;
90
91/// Hash-consing table for sharing structurally equal immutable values.
92///
93/// The table stores weak references so interned values disappear when the rest of
94/// the symbolic state stops using them. `make` only looks up and inserts; dead
95/// weak entries are ignored and left in the table until the context is dropped.
96pub(in crate::runtime) struct HashCons<T> {
97    table: HashTable<HashConsEntry<T>>,
98    hash_builder: HashConsHasher,
99}
100
101struct HashConsEntry<T> {
102    hash: u64,
103    value: Weak<HashConsedInner<T>>,
104}
105
106impl<T> HashConsEntry<T> {
107    const fn hash(&self) -> u64 {
108        self.hash
109    }
110}
111
112impl<T> HashCons<T> {
113    pub(in crate::runtime) fn new() -> Self {
114        Self { table: HashTable::new(), hash_builder: HashConsHasher::default() }
115    }
116
117    fn hash<Q: Hash + ?Sized>(&self, value: &Q) -> u64 {
118        self.hash_builder.hash_one(value)
119    }
120}
121
122impl<T: Eq + Hash> HashCons<T> {
123    pub(in crate::runtime) fn make(&mut self, value: T) -> HashConsed<T> {
124        let hash = self.hash(&value);
125        let mut found = None;
126        match self.table.entry(
127            hash,
128            |entry| {
129                if entry.hash == hash
130                    && let Some(existing) = entry.value.upgrade()
131                    && existing.value == value
132                {
133                    found = Some(existing);
134                    true
135                } else {
136                    false
137                }
138            },
139            HashConsEntry::hash,
140        ) {
141            Entry::Occupied(_) => HashConsed { inner: found.expect("matched live value") },
142            Entry::Vacant(entry) => {
143                let inner = HashConsedInner { hash, value };
144                let inner = Arc::new(inner);
145                entry.insert(HashConsEntry { hash, value: Arc::downgrade(&inner) });
146                HashConsed { inner }
147            }
148        }
149    }
150}
151
152#[cfg(test)]
153mod tests {
154    use super::*;
155
156    #[test]
157    fn make_reuses_existing_value() {
158        let mut table = HashCons::<String>::new();
159
160        let first = table.make("same".to_string());
161        let second = table.make("same".to_string());
162
163        assert_eq!(first, second);
164        assert_eq!(first.inner.hash, second.inner.hash);
165    }
166
167    #[test]
168    fn make_keeps_distinct_values_apart() {
169        let mut table = HashCons::<String>::new();
170
171        let first = table.make("first".to_string());
172        let second = table.make("second".to_string());
173
174        assert_ne!(first, second);
175    }
176
177    #[test]
178    fn dropped_values_are_not_reused() {
179        let mut table = HashCons::<String>::new();
180
181        let first = table.make("same".to_string());
182        let weak = Arc::downgrade(&first.inner);
183        drop(first);
184        assert!(weak.upgrade().is_none());
185
186        let second = table.make("same".to_string());
187
188        assert_eq!(second.value().as_str(), "same");
189        assert!(weak.upgrade().is_none());
190    }
191
192    #[test]
193    fn equality_is_pointer_only() {
194        let mut first_table = HashCons::<String>::new();
195        let mut second_table = HashCons::<String>::new();
196
197        let first = first_table.make("same".to_string());
198        let second = second_table.make("same".to_string());
199
200        assert_ne!(first, second);
201        assert_eq!(first.value(), second.value());
202    }
203}
foundry_evm_symbolic/runtime/expr/hashcons.rs

foundry_evm_symbolic/runtime/expr/
hashcons.rs
