wasm4pm_types/
dense_kernel.rs

1//! dense_kernel.rs
2
3use serde::{Deserialize, Serialize};
4
5// ============================================================================
6// FNV-1a HASHING
7// ============================================================================
8
9#[inline]
10pub fn fnv1a_64(bytes: &[u8]) -> u64 {
11    const OFFSET: u64 = 0xcbf29ce484222325;
12    const PRIME: u64 = 0x100000001b3;
13
14    let mut h = OFFSET;
15    for &b in bytes {
16        h ^= b as u64;
17        h = h.wrapping_mul(PRIME);
18    }
19    h
20}
21
22// ============================================================================
23// BASIC TYPES
24// ============================================================================
25
26pub type DenseId = u32;
27
28#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
29pub enum NodeKind {
30    Generic,
31    Place,
32    Transition,
33    Port,
34}
35
36#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
37pub enum DenseError {
38    HashCollision {
39        hash: u64,
40        left: String,
41        right: String,
42    },
43    DuplicateSymbol {
44        id: String,
45    },
46    UnknownSymbol {
47        id: String,
48    },
49    UnknownDenseId {
50        id: DenseId,
51    },
52    InvalidArc {
53        from: String,
54        to: String,
55        reason: &'static str,
56    },
57    CapacityExceeded {
58        requested: usize,
59        capacity: usize,
60    },
61}
62
63// ============================================================================
64// DENSE INDEX
65// ============================================================================
66
67#[derive(Debug, Clone, Serialize, Deserialize)]
68pub struct DenseIndex {
69    entries: Vec<IndexEntry>,
70    dense_to_hash: Vec<u64>,
71    symbols: Vec<String>,
72    kinds: Vec<NodeKind>,
73}
74
75#[derive(Debug, Clone, Copy, Serialize, Deserialize)]
76struct IndexEntry {
77    hash: u64,
78    dense: DenseId,
79}
80
81impl DenseIndex {
82    pub fn compile<I, S>(symbols: I) -> Result<Self, DenseError>
83    where
84        I: IntoIterator<Item = (S, NodeKind)>,
85        S: Into<String>,
86    {
87        let mut tmp: Vec<(u64, String, NodeKind)> = Vec::new();
88
89        for (sym, kind) in symbols {
90            let id = sym.into();
91            let hash = fnv1a_64(id.as_bytes());
92            tmp.push((hash, id, kind));
93        }
94
95        // Use a separate sorted vector to check for duplicates and collisions
96        let mut sorted_hashes: Vec<(u64, &String, &NodeKind)> =
97            tmp.iter().map(|(h, s, k)| (*h, s, k)).collect();
98
99        sorted_hashes.sort_by(|a, b| a.0.cmp(&b.0).then_with(|| a.1.cmp(b.1)));
100
101        for pair in sorted_hashes.windows(2) {
102            let (h1, s1, _) = &pair[0];
103            let (h2, s2, _) = &pair[1];
104
105            if s1 == s2 {
106                return Err(DenseError::DuplicateSymbol { id: (*s1).clone() });
107            }
108
109            if h1 == h2 {
110                return Err(DenseError::HashCollision {
111                    hash: *h1,
112                    left: (*s1).clone(),
113                    right: (*s2).clone(),
114                });
115            }
116        }
117
118        // Sort by symbol name so dense IDs are assigned in sorted order,
119        // making symbols() deterministic regardless of input order.
120        tmp.sort_by(|a, b| a.1.cmp(&b.1));
121
122        let mut entries = Vec::with_capacity(tmp.len());
123        let mut dense_to_hash = Vec::with_capacity(tmp.len());
124        let mut symbols = Vec::with_capacity(tmp.len());
125        let mut kinds = Vec::with_capacity(tmp.len());
126
127        for (dense, (hash, symbol, kind)) in tmp.into_iter().enumerate() {
128            let dense = dense as DenseId;
129
130            entries.push(IndexEntry { hash, dense });
131            dense_to_hash.push(hash);
132            symbols.push(symbol);
133            kinds.push(kind);
134        }
135
136        // Sort entries by hash for binary search, but they still point to original dense IDs
137        entries.sort_by_key(|e| e.hash);
138
139        Ok(Self {
140            entries,
141            dense_to_hash,
142            symbols,
143            kinds,
144        })
145    }
146
147    #[inline]
148    pub fn len(&self) -> usize {
149        self.symbols.len()
150    }
151    #[inline]
152    pub fn is_empty(&self) -> bool {
153        self.symbols.is_empty()
154    }
155    #[inline]
156    pub fn symbols(&self) -> &[String] {
157        &self.symbols
158    }
159    #[inline]
160    pub fn dense_id_by_symbol(&self, symbol: &str) -> Option<DenseId> {
161        self.dense_id(symbol)
162    }
163    #[inline]
164    pub fn dense_id(&self, symbol: &str) -> Option<DenseId> {
165        self.dense_id_by_hash(fnv1a_64(symbol.as_bytes()))
166    }
167    #[inline]
168    pub fn dense_id_by_hash(&self, hash: u64) -> Option<DenseId> {
169        self.entries
170            .binary_search_by_key(&hash, |e| e.hash)
171            .ok()
172            .map(|i| self.entries[i].dense)
173    }
174    #[inline]
175    pub fn symbol(&self, dense: DenseId) -> Option<&str> {
176        self.symbols.get(dense as usize).map(|s| s.as_str())
177    }
178    #[inline]
179    pub fn kind(&self, dense: DenseId) -> Option<NodeKind> {
180        self.kinds.get(dense as usize).copied()
181    }
182}
183
184// ============================================================================
185// K-BITSET
186// ============================================================================
187
188#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
189pub struct KBitSet<const WORDS: usize> {
190    pub words: [u64; WORDS],
191}
192
193impl<const WORDS: usize> Serialize for KBitSet<WORDS> {
194    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
195    where
196        S: serde::Serializer,
197    {
198        use serde::ser::SerializeTuple;
199        let mut tup = serializer.serialize_tuple(WORDS)?;
200        for w in &self.words {
201            tup.serialize_element(w)?;
202        }
203        tup.end()
204    }
205}
206
207impl<'de, const WORDS: usize> Deserialize<'de> for KBitSet<WORDS> {
208    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
209    where
210        D: serde::Deserializer<'de>,
211    {
212        struct KBitSetVisitor<const W: usize>;
213
214        impl<'de, const W: usize> serde::de::Visitor<'de> for KBitSetVisitor<W> {
215            type Value = [u64; W];
216
217            fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
218                formatter.write_str("a bitset array")
219            }
220
221            fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
222            where
223                A: serde::de::SeqAccess<'de>,
224            {
225                let mut words = [0u64; W];
226                for (i, word) in words.iter_mut().enumerate() {
227                    *word = seq
228                        .next_element()?
229                        .ok_or_else(|| serde::de::Error::invalid_length(i, &self))?;
230                }
231                Ok(words)
232            }
233        }
234
235        let words = deserializer.deserialize_tuple(WORDS, KBitSetVisitor::<WORDS>)?;
236        Ok(KBitSet { words })
237    }
238}
239
240impl<const WORDS: usize> Default for KBitSet<WORDS> {
241    #[inline]
242    fn default() -> Self {
243        Self {
244            words: [0u64; WORDS],
245        }
246    }
247}
248
249impl<const WORDS: usize> KBitSet<WORDS> {
250    pub const BITS: usize = WORDS * 64;
251    #[inline]
252    pub const fn zero() -> Self {
253        Self {
254            words: [0u64; WORDS],
255        }
256    }
257    #[inline]
258    pub fn clear(&mut self) {
259        for w in &mut self.words {
260            *w = 0;
261        }
262    }
263    #[inline]
264    pub fn set(&mut self, bit: usize) -> Result<(), DenseError> {
265        if bit >= Self::BITS {
266            return Err(DenseError::CapacityExceeded {
267                requested: bit + 1,
268                capacity: Self::BITS,
269            });
270        }
271        self.words[bit >> 6] |= 1u64 << (bit & 63);
272        Ok(())
273    }
274    #[inline]
275    pub fn contains(&self, bit: usize) -> bool {
276        if bit >= Self::BITS {
277            return false;
278        }
279        ((self.words[bit >> 6] >> (bit & 63)) & 1) != 0
280    }
281
282    #[inline]
283    pub fn contains_all(self, required: Self) -> bool {
284        for i in 0..WORDS {
285            if (required.words[i] & !self.words[i]) != 0 {
286                return false;
287            }
288        }
289        true
290    }
291
292    #[inline]
293    pub fn missing_count(self, required: Self) -> u32 {
294        let mut n = 0u32;
295        for i in 0..WORDS {
296            n += (required.words[i] & !self.words[i]).count_ones();
297        }
298        n
299    }
300
301    #[inline]
302    pub fn bitwise_or(&self, other: Self) -> Self {
303        let mut res = Self::zero();
304        for i in 0..WORDS {
305            res.words[i] = self.words[i] | other.words[i];
306        }
307        res
308    }
309
310    #[inline]
311    pub fn bitwise_and(&self, other: Self) -> Self {
312        let mut res = Self::zero();
313        for i in 0..WORDS {
314            res.words[i] = self.words[i] & other.words[i];
315        }
316        res
317    }
318
319    #[inline]
320    pub fn bitwise_not(&self) -> Self {
321        let mut res = Self::zero();
322        for i in 0..WORDS {
323            res.words[i] = !self.words[i];
324        }
325        res
326    }
327
328    #[inline]
329    pub fn is_empty(&self) -> bool {
330        for w in &self.words {
331            if *w != 0 {
332                return false;
333            }
334        }
335        true
336    }
337}
338
339pub type K64 = KBitSet<1>;
340
341// ============================================================================
342// PACKED KEY TABLE
343// ============================================================================
344
345const EMPTY_INDEX: u32 = u32::MAX;
346
347#[derive(Debug, Clone, Serialize, Deserialize)]
348pub struct PackedKeyTable<K, V> {
349    entries: Vec<(u64, K, V)>,
350    #[serde(skip, default = "default_indices")]
351    indices: Vec<u32>,
352}
353
354fn default_indices() -> Vec<u32> {
355    Vec::new()
356}
357
358impl<K: PartialEq, V: PartialEq> PartialEq for PackedKeyTable<K, V> {
359    fn eq(&self, other: &Self) -> bool {
360        self.entries == other.entries
361    }
362}
363
364impl<K, V> PackedKeyTable<K, V> {
365    #[inline(always)]
366    pub fn new() -> Self {
367        Self {
368            entries: Vec::new(),
369            indices: Vec::new(),
370        }
371    }
372
373    #[inline(always)]
374    pub fn with_capacity(cap: usize) -> Self {
375        if cap == 0 {
376            return Self::new();
377        }
378        let cap = cap.next_power_of_two().max(16);
379        Self {
380            entries: Vec::with_capacity(cap),
381            indices: vec![EMPTY_INDEX; cap],
382        }
383    }
384
385    #[inline(never)]
386    fn rebuild_indices_if_needed(&mut self) {
387        if !self.indices.is_empty() && self.indices.len() > self.entries.len() * 2 {
388            return;
389        }
390        let cap = self.entries.len().next_power_of_two().max(16) * 2;
391        self.indices.clear();
392        self.indices.resize(cap, EMPTY_INDEX);
393        let mask = (cap - 1) as u64;
394        for (i, &(hash, _, _)) in self.entries.iter().enumerate() {
395            let mut idx = (hash & mask) as usize;
396            loop {
397                if self.indices[idx] == EMPTY_INDEX {
398                    self.indices[idx] = i as u32;
399                    break;
400                }
401                idx = (idx + 1) & mask as usize;
402            }
403        }
404    }
405
406    #[inline(always)]
407    pub fn insert(&mut self, hash: u64, key: K, value: V) {
408        if self.indices.is_empty() || self.entries.len() * 2 >= self.indices.len() {
409            self.rebuild_indices_if_needed();
410        }
411        let mask = (self.indices.len() - 1) as u64;
412        let mut idx = (hash & mask) as usize;
413        loop {
414            let entry_idx = self.indices[idx];
415            if entry_idx == EMPTY_INDEX {
416                let new_idx = self.entries.len() as u32;
417                self.indices[idx] = new_idx;
418                self.entries.push((hash, key, value));
419                return;
420            }
421            // SAFETY: `entry_idx` is guaranteed to be a valid index in `self.entries`
422            // because it was only ever inserted as `self.entries.len()` during insertion time,
423            // and is only accessed if it's not EMPTY_INDEX.
424            if unsafe { self.entries.get_unchecked(entry_idx as usize).0 } == hash {
425                // SAFETY: Same invariant as above; `entry_idx` is a valid entry index.
426                unsafe { *self.entries.get_unchecked_mut(entry_idx as usize) = (hash, key, value) };
427                return;
428            }
429            idx = (idx + 1) & mask as usize;
430        }
431    }
432
433    #[inline(always)]
434    pub fn get(&self, hash: u64) -> Option<&V> {
435        if self.indices.is_empty() {
436            return None;
437        }
438        let mask = (self.indices.len() - 1) as u64;
439        let mut idx = (hash & mask) as usize;
440        loop {
441            // SAFETY: `idx` is guaranteed to be in bounds because
442            // `idx = hash & mask` and `mask = indices.len() - 1`, so `idx < indices.len()`.
443            let entry_idx = unsafe { *self.indices.get_unchecked(idx) };
444            if entry_idx == EMPTY_INDEX {
445                return None;
446            }
447            // SAFETY: `entry_idx` is guaranteed to be a valid index in `self.entries`
448            // because it was only ever inserted as `self.entries.len()` at insertion time.
449            let entry = unsafe { self.entries.get_unchecked(entry_idx as usize) };
450            if entry.0 == hash {
451                return Some(&entry.2);
452            }
453            idx = (idx + 1) & mask as usize;
454        }
455    }
456
457    #[inline(always)]
458    pub fn get_mut(&mut self, hash: u64) -> Option<&mut V> {
459        if self.indices.is_empty() {
460            return None;
461        }
462        let mask = (self.indices.len() - 1) as u64;
463        let mut idx = (hash & mask) as usize;
464        loop {
465            // SAFETY: `idx` is guaranteed to be in bounds because
466            // `idx = hash & mask` and `mask = indices.len() - 1`, so `idx < indices.len()`.
467            let entry_idx = unsafe { *self.indices.get_unchecked(idx) };
468            if entry_idx == EMPTY_INDEX {
469                return None;
470            }
471            // SAFETY: `entry_idx` is guaranteed to be a valid index in `self.entries`
472            // because it was only ever inserted as `self.entries.len()` at insertion time.
473            if unsafe { self.entries.get_unchecked(entry_idx as usize).0 } == hash {
474                // SAFETY: Same invariant; `entry_idx` is valid.
475                return Some(&mut unsafe { self.entries.get_unchecked_mut(entry_idx as usize) }.2);
476            }
477            idx = (idx + 1) & mask as usize;
478        }
479    }
480
481    #[inline(always)]
482    pub fn len(&self) -> usize {
483        self.entries.len()
484    }
485
486    #[inline(always)]
487    pub fn is_empty(&self) -> bool {
488        self.entries.is_empty()
489    }
490
491    #[inline(always)]
492    pub fn iter(&self) -> impl Iterator<Item = &(u64, K, V)> {
493        self.entries.iter()
494    }
495
496    #[inline(always)]
497    pub fn clear(&mut self) {
498        self.entries.clear();
499        self.indices.fill(EMPTY_INDEX);
500    }
501}
502
503impl<K, V> Default for PackedKeyTable<K, V> {
504    fn default() -> Self {
505        Self::new()
506    }
507}
wasm4pm_types/dense_kernel.rs

wasm4pm_types/
dense_kernel.rs
