vertep_core/
bitset.rs

1//! A small fixed-capacity bitset over dense state indices.
2//!
3//! The interpreter numbers states in document order, so ascending iteration is document order
4//! (entry order) and descending iteration is reverse document order (exit order). The set is a
5//! plain vector of words: no interior mutability, no unsafe code and no trait objects, which keeps
6//! it inside the subset that a later Aeneas translation supports.
7
8use alloc::vec;
9use alloc::vec::Vec;
10
11const BITS: usize = 64;
12
13/// A set of state indices in `0..capacity`.
14#[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
15#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
16pub struct StateSet {
17    words: Vec<u64>,
18}
19
20impl StateSet {
21    /// An empty set able to hold indices `0..capacity`.
22    pub fn new(capacity: usize) -> Self {
23        StateSet {
24            words: vec![0; capacity.div_ceil(BITS)],
25        }
26    }
27
28    /// The number of indices the set can hold (rounded up to a whole word).
29    pub fn capacity(&self) -> usize {
30        self.words.len() * BITS
31    }
32
33    /// Add `i`. Indices beyond the capacity grow the set.
34    pub fn insert(&mut self, i: usize) {
35        let w = i / BITS;
36        if w >= self.words.len() {
37            self.words.resize(w + 1, 0);
38        }
39        self.words[w] |= 1u64 << (i % BITS);
40    }
41
42    /// Remove `i`.
43    pub fn remove(&mut self, i: usize) {
44        let w = i / BITS;
45        if w < self.words.len() {
46            self.words[w] &= !(1u64 << (i % BITS));
47        }
48    }
49
50    /// Whether `i` is a member.
51    pub fn contains(&self, i: usize) -> bool {
52        let w = i / BITS;
53        w < self.words.len() && (self.words[w] >> (i % BITS)) & 1 == 1
54    }
55
56    /// Whether the set is empty.
57    pub fn is_empty(&self) -> bool {
58        self.words.iter().all(|w| *w == 0)
59    }
60
61    /// The number of members.
62    pub fn len(&self) -> usize {
63        self.words.iter().map(|w| w.count_ones() as usize).sum()
64    }
65
66    /// Remove every member.
67    pub fn clear(&mut self) {
68        for w in self.words.iter_mut() {
69            *w = 0;
70        }
71    }
72
73    /// Add every member of `other`.
74    pub fn union_with(&mut self, other: &StateSet) {
75        if other.words.len() > self.words.len() {
76            self.words.resize(other.words.len(), 0);
77        }
78        for (a, b) in self.words.iter_mut().zip(other.words.iter()) {
79            *a |= *b;
80        }
81    }
82
83    /// Remove every member of `other`.
84    pub fn difference_with(&mut self, other: &StateSet) {
85        for (a, b) in self.words.iter_mut().zip(other.words.iter()) {
86            *a &= !*b;
87        }
88    }
89
90    /// Whether the two sets share a member.
91    pub fn intersects(&self, other: &StateSet) -> bool {
92        self.words
93            .iter()
94            .zip(other.words.iter())
95            .any(|(a, b)| a & b != 0)
96    }
97
98    /// Whether any index in `lo..=hi` is a member.
99    pub fn any_in_range(&self, lo: usize, hi: usize) -> bool {
100        let mut i = lo;
101        while i <= hi {
102            if self.contains(i) {
103                return true;
104            }
105            i += 1;
106        }
107        false
108    }
109
110    /// Members in ascending order (document order).
111    pub fn to_vec(&self) -> Vec<usize> {
112        let mut out = Vec::new();
113        for (wi, w) in self.words.iter().enumerate() {
114            let mut bits = *w;
115            while bits != 0 {
116                let b = bits.trailing_zeros() as usize;
117                out.push(wi * BITS + b);
118                bits &= bits - 1;
119            }
120        }
121        out
122    }
123
124    /// Members in descending order (reverse document order).
125    pub fn to_vec_rev(&self) -> Vec<usize> {
126        let mut v = self.to_vec();
127        v.reverse();
128        v
129    }
130}
131
132#[cfg(test)]
133mod tests {
134    use super::*;
135
136    #[test]
137    fn insert_remove_iterate() {
138        let mut s = StateSet::new(130);
139        s.insert(0);
140        s.insert(64);
141        s.insert(129);
142        assert!(s.contains(64));
143        assert_eq!(s.to_vec(), vec![0, 64, 129]);
144        assert_eq!(s.to_vec_rev(), vec![129, 64, 0]);
145        s.remove(64);
146        assert_eq!(s.len(), 2);
147        assert!(s.any_in_range(100, 129));
148        assert!(!s.any_in_range(1, 128));
149        let mut t = StateSet::new(130);
150        t.insert(129);
151        assert!(s.intersects(&t));
152        s.difference_with(&t);
153        assert_eq!(s.to_vec(), vec![0]);
154        s.insert(300);
155        assert!(s.contains(300));
156        s.clear();
157        assert!(s.is_empty());
158    }
159}
vertep_core/bitset.rs

vertep_core/
bitset.rs
