oxilean_kernel/equiv_manager/
functions.rs

1//! Auto-generated module
2//!
3//! 🤖 Generated with [SplitRS](https://github.com/cool-japan/splitrs)
4
5use crate::Expr;
6use std::collections::{HashMap, HashSet};
7
8use super::types::{
9    AnnotationTable, BeforeAfter, BiMap, CheckedEquiv, DiagMeta, EquivClass, EquivManager,
10    EquivManagerStats, EquivProofTerm, EquivQuery, EquivStats, EquivalenceTable, EventCounter,
11    ExprEquivCache, FrequencyTable, Generation, IdDispenser, IndexEquivManager,
12    InstrumentedEquivManager, IntervalSet, LoopClock, MemoSlot, PersistentEquivManager, RingBuffer,
13    ScopeStack, ScopedEquivManager, SeqNum, SimpleLruCache, Slot, SparseBitSet, StringInterner,
14    SymmetricRelation, Timestamp, TypedId, UnionFind, WorkQueue, WorkStack,
15};
16
17/// Create a canonical pair ordering for cache lookups.
18///
19/// We need `(a, b)` and `(b, a)` to map to the same cache key.
20/// We use a deterministic ordering based on expression debug representation.
21pub(super) fn canonicalize_pair(a: Expr, b: Expr) -> (Expr, Expr) {
22    if format!("{:?}", a) <= format!("{:?}", b) {
23        (a, b)
24    } else {
25        (b, a)
26    }
27}
28#[cfg(test)]
29mod tests {
30    use super::*;
31    use crate::{Level, Name};
32    fn nat() -> Expr {
33        Expr::Const(Name::str("Nat"), vec![])
34    }
35    fn bool_expr() -> Expr {
36        Expr::Const(Name::str("Bool"), vec![])
37    }
38    fn int() -> Expr {
39        Expr::Const(Name::str("Int"), vec![])
40    }
41    #[test]
42    fn test_equiv_reflexive() {
43        let mut mgr = EquivManager::new();
44        assert!(mgr.is_equiv(&nat(), &nat()));
45    }
46    #[test]
47    fn test_add_and_check_equiv() {
48        let mut mgr = EquivManager::new();
49        mgr.add_equiv(&nat(), &bool_expr());
50        assert!(mgr.is_equiv(&nat(), &bool_expr()));
51        assert!(mgr.is_equiv(&bool_expr(), &nat()));
52    }
53    #[test]
54    fn test_equiv_transitivity() {
55        let mut mgr = EquivManager::new();
56        mgr.add_equiv(&nat(), &bool_expr());
57        mgr.add_equiv(&bool_expr(), &int());
58        assert!(mgr.is_equiv(&nat(), &int()));
59    }
60    #[test]
61    fn test_failure_cache() {
62        let mut mgr = EquivManager::new();
63        mgr.add_failure(&nat(), &bool_expr());
64        assert!(mgr.is_failure(&nat(), &bool_expr()));
65        assert!(mgr.is_failure(&bool_expr(), &nat()));
66        assert!(!mgr.is_failure(&nat(), &int()));
67    }
68    #[test]
69    fn test_not_equiv() {
70        let mut mgr = EquivManager::new();
71        assert!(!mgr.is_equiv(&nat(), &bool_expr()));
72    }
73    #[test]
74    fn test_clear() {
75        let mut mgr = EquivManager::new();
76        mgr.add_equiv(&nat(), &bool_expr());
77        mgr.add_failure(&nat(), &int());
78        assert_eq!(mgr.num_equiv(), 1);
79        assert_eq!(mgr.num_failures(), 1);
80        mgr.clear();
81        assert_eq!(mgr.num_equiv(), 0);
82        assert_eq!(mgr.num_failures(), 0);
83        assert!(!mgr.is_equiv(&nat(), &bool_expr()));
84    }
85    #[test]
86    fn test_many_equivalences() {
87        let mut mgr = EquivManager::new();
88        let exprs: Vec<Expr> = (0..10)
89            .map(|i| Expr::Const(Name::str(format!("T{}", i)), vec![]))
90            .collect();
91        for i in 0..9 {
92            mgr.add_equiv(&exprs[i], &exprs[i + 1]);
93        }
94        assert!(mgr.is_equiv(&exprs[0], &exprs[9]));
95        assert!(mgr.is_equiv(&exprs[3], &exprs[7]));
96    }
97    #[test]
98    fn test_sort_equivalence() {
99        let mut mgr = EquivManager::new();
100        let s0 = Expr::Sort(Level::zero());
101        let s1 = Expr::Sort(Level::succ(Level::zero()));
102        mgr.add_equiv(&s0, &s1);
103        assert!(mgr.is_equiv(&s0, &s1));
104    }
105}
106#[cfg(test)]
107mod equiv_extended_tests {
108    use super::*;
109    use crate::Name;
110    fn nat() -> Expr {
111        Expr::Const(Name::str("Nat"), vec![])
112    }
113    fn bool_expr() -> Expr {
114        Expr::Const(Name::str("Bool"), vec![])
115    }
116    fn int() -> Expr {
117        Expr::Const(Name::str("Int"), vec![])
118    }
119    fn str_ty() -> Expr {
120        Expr::Const(Name::str("String"), vec![])
121    }
122    #[test]
123    fn test_scoped_manager_basic() {
124        let mut mgr = ScopedEquivManager::new();
125        mgr.add_equiv(&nat(), &bool_expr());
126        assert!(mgr.is_equiv(&nat(), &bool_expr()));
127        assert_eq!(mgr.scope_depth(), 1);
128    }
129    #[test]
130    fn test_scoped_manager_push_pop() {
131        let mut mgr = ScopedEquivManager::new();
132        mgr.add_equiv(&nat(), &bool_expr());
133        mgr.push_scope();
134        assert_eq!(mgr.scope_depth(), 2);
135        mgr.add_equiv(&nat(), &int());
136        assert!(mgr.is_equiv(&nat(), &int()));
137        mgr.pop_scope();
138        assert_eq!(mgr.scope_depth(), 1);
139        assert!(mgr.is_equiv(&nat(), &bool_expr()));
140    }
141    #[test]
142    fn test_scoped_manager_total_equivs() {
143        let mut mgr = ScopedEquivManager::new();
144        mgr.add_equiv(&nat(), &bool_expr());
145        mgr.push_scope();
146        mgr.add_equiv(&int(), &str_ty());
147        assert_eq!(mgr.total_equivs(), 2);
148    }
149    #[test]
150    fn test_equiv_stats_default() {
151        let stats = EquivStats::new();
152        assert_eq!(stats.total_queries, 0);
153        assert_eq!(stats.hit_rate(), 1.0);
154    }
155    #[test]
156    fn test_equiv_stats_recording() {
157        let mut stats = EquivStats::new();
158        stats.record_equiv_hit();
159        stats.record_equiv_hit();
160        stats.record_miss();
161        assert_eq!(stats.total_queries, 3);
162        assert_eq!(stats.equiv_hits, 2);
163        assert!((stats.hit_rate() - 2.0 / 3.0).abs() < 1e-9);
164    }
165    #[test]
166    fn test_instrumented_manager() {
167        let mut mgr = InstrumentedEquivManager::new();
168        mgr.add_equiv(&nat(), &bool_expr());
169        let result = mgr.is_equiv(&nat(), &bool_expr());
170        assert!(result);
171        assert_eq!(mgr.stats().equiv_additions, 1);
172        assert_eq!(mgr.stats().total_queries, 1);
173    }
174    #[test]
175    fn test_instrumented_manager_clear() {
176        let mut mgr = InstrumentedEquivManager::new();
177        mgr.add_equiv(&nat(), &bool_expr());
178        mgr.clear();
179        assert_eq!(mgr.stats().total_queries, 0);
180        assert_eq!(mgr.stats().equiv_additions, 0);
181    }
182    #[test]
183    fn test_equiv_query() {
184        let mut mgr = EquivManager::new();
185        mgr.add_failure(&nat(), &bool_expr());
186        let query = EquivQuery::new(&mgr);
187        assert!(query.is_known_failure(&nat(), &bool_expr()));
188        assert!(!query.is_known_failure(&nat(), &int()));
189        assert_eq!(query.num_failures(), 1);
190    }
191    #[test]
192    fn test_scoped_manager_pop_at_root() {
193        let mut mgr = ScopedEquivManager::new();
194        mgr.pop_scope();
195        assert_eq!(mgr.scope_depth(), 1);
196    }
197    #[test]
198    fn test_instrumented_add_failure() {
199        let mut mgr = InstrumentedEquivManager::new();
200        mgr.add_failure(&nat(), &bool_expr());
201        assert!(mgr.is_failure(&nat(), &bool_expr()));
202        assert_eq!(mgr.stats().failure_additions, 1);
203    }
204}
205/// Compute the equivalence classes of a set of expressions.
206///
207/// Groups expressions that are known to be equivalent with each other.
208/// Uses simple transitive closure via repeated passes.
209pub fn compute_equiv_classes(exprs: &[Expr], pairs: &[(Expr, Expr)]) -> Vec<Vec<usize>> {
210    let n = exprs.len();
211    let mut parent: Vec<usize> = (0..n).collect();
212    fn find(parent: &mut Vec<usize>, x: usize) -> usize {
213        if parent[x] != x {
214            parent[x] = find(parent, parent[x]);
215        }
216        parent[x]
217    }
218    fn union(parent: &mut Vec<usize>, x: usize, y: usize) {
219        let rx = find(parent, x);
220        let ry = find(parent, y);
221        if rx != ry {
222            parent[rx] = ry;
223        }
224    }
225    for (a, b) in pairs {
226        let ia = exprs.iter().position(|e| e == a);
227        let ib = exprs.iter().position(|e| e == b);
228        if let (Some(i), Some(j)) = (ia, ib) {
229            union(&mut parent, i, j);
230        }
231    }
232    let mut classes: std::collections::HashMap<usize, Vec<usize>> =
233        std::collections::HashMap::new();
234    for i in 0..n {
235        let root = find(&mut parent, i);
236        classes.entry(root).or_default().push(i);
237    }
238    classes.into_values().collect()
239}
240#[cfg(test)]
241mod persistent_equiv_tests {
242    use super::*;
243    use crate::Name;
244    fn nat() -> Expr {
245        Expr::Const(Name::str("Nat"), vec![])
246    }
247    fn bool_expr() -> Expr {
248        Expr::Const(Name::str("Bool"), vec![])
249    }
250    fn int() -> Expr {
251        Expr::Const(Name::str("Int"), vec![])
252    }
253    #[test]
254    fn test_persistent_manager_basic() {
255        let mut mgr = PersistentEquivManager::new();
256        mgr.add_equiv(&nat(), &bool_expr());
257        assert!(mgr.is_equiv(&nat(), &bool_expr()));
258        assert!(mgr.is_equiv(&bool_expr(), &nat()));
259        assert!(!mgr.is_equiv(&nat(), &int()));
260    }
261    #[test]
262    fn test_persistent_manager_reflexive() {
263        let mgr = PersistentEquivManager::new();
264        assert!(mgr.is_equiv(&nat(), &nat()));
265    }
266    #[test]
267    fn test_persistent_manager_no_dups() {
268        let mut mgr = PersistentEquivManager::new();
269        mgr.add_equiv(&nat(), &bool_expr());
270        mgr.add_equiv(&nat(), &bool_expr());
271        assert_eq!(mgr.len(), 1);
272    }
273    #[test]
274    fn test_persistent_manager_serialize() {
275        let mut mgr = PersistentEquivManager::new();
276        mgr.add_equiv(&nat(), &bool_expr());
277        let serialized = mgr.serialize();
278        assert_eq!(serialized.len(), 1);
279    }
280    #[test]
281    fn test_compute_equiv_classes_basic() {
282        let exprs = vec![
283            Expr::Const(Name::str("A"), vec![]),
284            Expr::Const(Name::str("B"), vec![]),
285            Expr::Const(Name::str("C"), vec![]),
286        ];
287        let pairs = vec![(exprs[0].clone(), exprs[1].clone())];
288        let classes = compute_equiv_classes(&exprs, &pairs);
289        assert_eq!(classes.len(), 2);
290        let sizes: std::collections::HashSet<usize> = classes.iter().map(|c| c.len()).collect();
291        assert!(sizes.contains(&2));
292        assert!(sizes.contains(&1));
293    }
294    #[test]
295    fn test_compute_equiv_classes_all_separate() {
296        let exprs = vec![
297            Expr::Const(Name::str("A"), vec![]),
298            Expr::Const(Name::str("B"), vec![]),
299        ];
300        let classes = compute_equiv_classes(&exprs, &[]);
301        assert_eq!(classes.len(), 2);
302        assert!(classes.iter().all(|c| c.len() == 1));
303    }
304    #[test]
305    fn test_compute_equiv_classes_all_same() {
306        let nat = Expr::Const(Name::str("A"), vec![]);
307        let bool_e = Expr::Const(Name::str("B"), vec![]);
308        let int_e = Expr::Const(Name::str("C"), vec![]);
309        let exprs = vec![nat.clone(), bool_e.clone(), int_e.clone()];
310        let pairs = vec![
311            (nat.clone(), bool_e.clone()),
312            (bool_e.clone(), int_e.clone()),
313        ];
314        let classes = compute_equiv_classes(&exprs, &pairs);
315        assert_eq!(classes.len(), 1);
316        assert_eq!(classes[0].len(), 3);
317    }
318    #[test]
319    fn test_persistent_manager_is_empty() {
320        let mgr = PersistentEquivManager::new();
321        assert!(mgr.is_empty());
322        let mut mgr2 = PersistentEquivManager::new();
323        mgr2.add_equiv(&nat(), &bool_expr());
324        assert!(!mgr2.is_empty());
325    }
326    #[test]
327    fn test_persistent_manager_sorted_output() {
328        let mut mgr = PersistentEquivManager::new();
329        mgr.add_equiv(&int(), &nat());
330        mgr.add_equiv(&bool_expr(), &nat());
331        let serialized = mgr.serialize();
332        for i in 0..serialized.len().saturating_sub(1) {
333            assert!(serialized[i] <= serialized[i + 1]);
334        }
335    }
336}
337/// Compute the transitive closure of a relation on a set of expressions.
338///
339/// Given a list of initial pairs, returns all pairs (i, j) such that
340/// i and j are in the same equivalence class.
341#[allow(dead_code)]
342pub fn transitive_closure(pairs: &[(usize, usize)], n: usize) -> Vec<(usize, usize)> {
343    let mut parent: Vec<usize> = (0..n).collect();
344    fn find(parent: &mut Vec<usize>, x: usize) -> usize {
345        if parent[x] != x {
346            parent[x] = find(parent, parent[x]);
347        }
348        parent[x]
349    }
350    for &(a, b) in pairs {
351        if a < n && b < n {
352            let ra = find(&mut parent, a);
353            let rb = find(&mut parent, b);
354            if ra != rb {
355                parent[ra] = rb;
356            }
357        }
358    }
359    let mut result = Vec::new();
360    for i in 0..n {
361        for j in (i + 1)..n {
362            if find(&mut parent, i) == find(&mut parent, j) {
363                result.push((i, j));
364            }
365        }
366    }
367    result
368}
369/// Map an expression list to its equivalence-class representatives.
370///
371/// Returns an index array where `repr[i]` is the representative index for `i`.
372#[allow(dead_code)]
373pub fn compute_representatives(pairs: &[(usize, usize)], n: usize) -> Vec<usize> {
374    let mut parent: Vec<usize> = (0..n).collect();
375    fn find(parent: &mut Vec<usize>, x: usize) -> usize {
376        if parent[x] != x {
377            parent[x] = find(parent, parent[x]);
378        }
379        parent[x]
380    }
381    for &(a, b) in pairs {
382        if a < n && b < n {
383            let ra = find(&mut parent, a);
384            let rb = find(&mut parent, b);
385            if ra != rb {
386                parent[ra] = rb;
387            }
388        }
389    }
390    (0..n).map(|i| find(&mut parent, i)).collect()
391}
392/// Find all equivalence classes given an explicit list of pairs.
393///
394/// Returns a `Vec<Vec<usize>>` where each inner vec is one class.
395#[allow(dead_code)]
396pub fn find_classes(pairs: &[(usize, usize)], n: usize) -> Vec<Vec<usize>> {
397    let repr = compute_representatives(pairs, n);
398    let mut classes: std::collections::HashMap<usize, Vec<usize>> =
399        std::collections::HashMap::new();
400    for (i, r) in repr.into_iter().enumerate() {
401        classes.entry(r).or_default().push(i);
402    }
403    classes.into_values().collect()
404}
405#[cfg(test)]
406mod extra_equiv_tests {
407    use super::*;
408    use crate::Name;
409    #[test]
410    fn test_transitive_closure_basic() {
411        let pairs = vec![(0, 1), (1, 2)];
412        let closure = transitive_closure(&pairs, 3);
413        assert!(closure.contains(&(0, 2)));
414    }
415    #[test]
416    fn test_transitive_closure_empty() {
417        let closure = transitive_closure(&[], 3);
418        assert!(closure.is_empty());
419    }
420    #[test]
421    fn test_compute_representatives_basic() {
422        let pairs = vec![(0, 1)];
423        let repr = compute_representatives(&pairs, 3);
424        assert_eq!(repr[0], repr[1]);
425        assert_ne!(repr[0], repr[2]);
426    }
427    #[test]
428    fn test_find_classes_two_classes() {
429        let pairs = vec![(0, 1), (2, 3)];
430        let classes = find_classes(&pairs, 4);
431        assert_eq!(classes.len(), 2);
432    }
433    #[test]
434    fn test_index_equiv_manager_basic() {
435        let mut mgr = IndexEquivManager::new(5);
436        mgr.union(0, 1);
437        mgr.union(1, 2);
438        assert!(mgr.same_class(0, 2));
439        assert!(!mgr.same_class(0, 3));
440    }
441    #[test]
442    fn test_index_equiv_manager_num_classes() {
443        let mut mgr = IndexEquivManager::new(5);
444        assert_eq!(mgr.num_classes(), 5);
445        mgr.union(0, 1);
446        mgr.union(2, 3);
447        assert_eq!(mgr.num_classes(), 3);
448    }
449    #[test]
450    fn test_index_equiv_manager_find_self() {
451        let mut mgr = IndexEquivManager::new(3);
452        assert_eq!(mgr.find(0), 0);
453    }
454    #[test]
455    fn test_equiv_manager_default() {
456        let mgr = EquivManager::default();
457        assert_eq!(mgr.num_equiv(), 0);
458        assert_eq!(mgr.num_failures(), 0);
459    }
460    #[test]
461    fn test_persistent_equiv_manager_clone() {
462        let mut mgr = PersistentEquivManager::new();
463        mgr.add_equiv(
464            &Expr::Const(Name::str("A"), vec![]),
465            &Expr::Const(Name::str("B"), vec![]),
466        );
467        let cloned = mgr.clone();
468        assert_eq!(cloned.len(), 1);
469    }
470    #[test]
471    fn test_scoped_manager_reflexive() {
472        let mut mgr = ScopedEquivManager::new();
473        let e = Expr::Const(Name::str("A"), vec![]);
474        assert!(mgr.is_equiv(&e, &e));
475    }
476    #[test]
477    fn test_union_find_all_separate() {
478        let pairs: Vec<(usize, usize)> = vec![];
479        let repr = compute_representatives(&pairs, 4);
480        let classes: std::collections::HashSet<_> = repr.into_iter().collect();
481        assert_eq!(classes.len(), 4);
482    }
483    #[test]
484    fn test_find_classes_all_same() {
485        let pairs = vec![(0, 1), (1, 2), (2, 3)];
486        let classes = find_classes(&pairs, 4);
487        assert_eq!(classes.len(), 1);
488        assert_eq!(classes[0].len(), 4);
489    }
490}
491#[cfg(test)]
492mod tests_equiv_extra {
493    use super::*;
494    #[test]
495    fn test_equiv_class() {
496        let mut ec = EquivClass::singleton(0);
497        ec.members.push(1);
498        assert!(ec.contains(0));
499        assert!(ec.contains(1));
500        assert!(!ec.contains(2));
501        assert_eq!(ec.size(), 2);
502    }
503    #[test]
504    fn test_union_find() {
505        let mut uf = UnionFind::new(5);
506        assert_eq!(uf.num_classes(), 5);
507        assert!(uf.union(0, 1));
508        assert!(uf.union(2, 3));
509        assert_eq!(uf.num_classes(), 3);
510        assert!(uf.same(0, 1));
511        assert!(!uf.same(0, 2));
512        uf.union(1, 2);
513        assert!(uf.same(0, 3));
514    }
515    #[test]
516    fn test_equivalence_table() {
517        let mut tbl = EquivalenceTable::new(8);
518        tbl.register(100);
519        tbl.register(200);
520        assert!(!tbl.equiv(100, 200));
521        tbl.merge(100, 200);
522        assert!(tbl.equiv(100, 200));
523    }
524    #[test]
525    fn test_expr_equiv_cache() {
526        let mut cache = ExprEquivCache::new();
527        assert_eq!(cache.query(1, 2), None);
528        cache.mark_equal(1, 2);
529        assert_eq!(cache.query(1, 2), Some(true));
530        assert_eq!(cache.query(2, 1), Some(true));
531        cache.mark_unequal(3, 4);
532        assert_eq!(cache.query(3, 4), Some(false));
533        assert_eq!(cache.proven_count(), 1);
534    }
535    #[test]
536    fn test_equiv_manager_stats() {
537        let mut stats = EquivManagerStats::new();
538        stats.checks = 100;
539        stats.hits = 80;
540        assert!((stats.hit_rate() - 0.8).abs() < 1e-9);
541    }
542}
543#[cfg(test)]
544mod tests_equiv_proof {
545    use super::*;
546    #[test]
547    fn test_equiv_proof_term() {
548        let refl = EquivProofTerm::Refl(42);
549        assert_eq!(refl.depth(), 0);
550        assert!(refl.is_refl());
551        let symm = EquivProofTerm::Symm(Box::new(EquivProofTerm::Axiom("h".into())));
552        assert_eq!(symm.depth(), 1);
553        assert!(!symm.is_refl());
554    }
555    #[test]
556    fn test_checked_equiv() {
557        let eq = CheckedEquiv::refl(99);
558        assert!(eq.is_trivial());
559        assert!(eq.proof().is_refl());
560        let ax = CheckedEquiv::by_axiom(1, 2, "comm");
561        assert!(!ax.is_trivial());
562        assert_eq!(ax.lhs(), 1);
563        assert_eq!(ax.rhs(), 2);
564    }
565}
566#[cfg(test)]
567mod tests_symmetric_relation {
568    use super::*;
569    #[test]
570    fn test_symmetric_relation() {
571        let mut rel = SymmetricRelation::new();
572        rel.add(1, 2);
573        assert!(rel.contains(1, 2));
574        assert!(rel.contains(2, 1));
575        assert!(!rel.contains(1, 3));
576        assert_eq!(rel.len(), 1);
577    }
578}
579#[cfg(test)]
580mod tests_common_infra {
581    use super::*;
582    #[test]
583    fn test_event_counter() {
584        let mut ec = EventCounter::new();
585        ec.inc("hit");
586        ec.inc("hit");
587        ec.inc("miss");
588        assert_eq!(ec.get("hit"), 2);
589        assert_eq!(ec.get("miss"), 1);
590        assert_eq!(ec.total(), 3);
591        ec.reset();
592        assert_eq!(ec.total(), 0);
593    }
594    #[test]
595    fn test_diag_meta() {
596        let mut m = DiagMeta::new();
597        m.add("os", "linux");
598        m.add("arch", "x86_64");
599        assert_eq!(m.get("os"), Some("linux"));
600        assert_eq!(m.len(), 2);
601        let s = m.to_string();
602        assert!(s.contains("os=linux"));
603    }
604    #[test]
605    fn test_scope_stack() {
606        let mut ss = ScopeStack::new();
607        ss.push("Nat");
608        ss.push("succ");
609        assert_eq!(ss.current(), Some("succ"));
610        assert_eq!(ss.depth(), 2);
611        assert_eq!(ss.path(), "Nat.succ");
612        ss.pop();
613        assert_eq!(ss.current(), Some("Nat"));
614    }
615    #[test]
616    fn test_annotation_table() {
617        let mut tbl = AnnotationTable::new();
618        tbl.annotate("doc", "first line");
619        tbl.annotate("doc", "second line");
620        assert_eq!(tbl.get_all("doc").len(), 2);
621        assert!(tbl.has("doc"));
622        assert!(!tbl.has("other"));
623    }
624    #[test]
625    fn test_work_stack() {
626        let mut ws = WorkStack::new();
627        ws.push(1u32);
628        ws.push(2u32);
629        assert_eq!(ws.pop(), Some(2));
630        assert_eq!(ws.len(), 1);
631    }
632    #[test]
633    fn test_work_queue() {
634        let mut wq = WorkQueue::new();
635        wq.enqueue(1u32);
636        wq.enqueue(2u32);
637        assert_eq!(wq.dequeue(), Some(1));
638        assert_eq!(wq.len(), 1);
639    }
640    #[test]
641    fn test_sparse_bit_set() {
642        let mut bs = SparseBitSet::new(128);
643        bs.set(5);
644        bs.set(63);
645        bs.set(64);
646        assert!(bs.get(5));
647        assert!(bs.get(63));
648        assert!(bs.get(64));
649        assert!(!bs.get(0));
650        assert_eq!(bs.count_ones(), 3);
651        bs.clear(5);
652        assert!(!bs.get(5));
653    }
654    #[test]
655    fn test_loop_clock() {
656        let mut clk = LoopClock::start();
657        for _ in 0..10 {
658            clk.tick();
659        }
660        assert_eq!(clk.iters(), 10);
661        assert!(clk.elapsed_us() >= 0.0);
662    }
663}
664#[cfg(test)]
665mod tests_extra_data_structures {
666    use super::*;
667    #[test]
668    fn test_simple_lru_cache() {
669        let mut cache: SimpleLruCache<&str, u32> = SimpleLruCache::new(3);
670        cache.put("a", 1);
671        cache.put("b", 2);
672        cache.put("c", 3);
673        assert_eq!(cache.get(&"a"), Some(&1));
674        cache.put("d", 4);
675        assert!(cache.len() <= 3);
676    }
677    #[test]
678    fn test_string_interner() {
679        let mut si = StringInterner::new();
680        let id1 = si.intern("hello");
681        let id2 = si.intern("hello");
682        assert_eq!(id1, id2);
683        let id3 = si.intern("world");
684        assert_ne!(id1, id3);
685        assert_eq!(si.get(id1), Some("hello"));
686        assert_eq!(si.len(), 2);
687    }
688    #[test]
689    fn test_frequency_table() {
690        let mut ft = FrequencyTable::new();
691        ft.record("a");
692        ft.record("b");
693        ft.record("a");
694        ft.record("a");
695        assert_eq!(ft.freq(&"a"), 3);
696        assert_eq!(ft.freq(&"b"), 1);
697        assert_eq!(ft.most_frequent(), Some((&"a", 3)));
698        assert_eq!(ft.total(), 4);
699        assert_eq!(ft.distinct(), 2);
700    }
701    #[test]
702    fn test_bimap() {
703        let mut bm: BiMap<u32, &str> = BiMap::new();
704        bm.insert(1, "one");
705        bm.insert(2, "two");
706        assert_eq!(bm.get_b(&1), Some(&"one"));
707        assert_eq!(bm.get_a(&"two"), Some(&2));
708        assert_eq!(bm.len(), 2);
709    }
710}
711#[cfg(test)]
712mod tests_interval_set {
713    use super::*;
714    #[test]
715    fn test_interval_set() {
716        let mut s = IntervalSet::new();
717        s.add(1, 5);
718        s.add(3, 8);
719        assert_eq!(s.num_intervals(), 1);
720        assert_eq!(s.cardinality(), 8);
721        assert!(s.contains(4));
722        assert!(!s.contains(9));
723        s.add(10, 15);
724        assert_eq!(s.num_intervals(), 2);
725    }
726}
727/// Returns the current timestamp.
728#[allow(dead_code)]
729pub fn now_us() -> Timestamp {
730    let us = std::time::SystemTime::UNIX_EPOCH
731        .elapsed()
732        .map(|d| d.as_micros() as u64)
733        .unwrap_or(0);
734    Timestamp::from_us(us)
735}
736#[cfg(test)]
737mod tests_typed_utilities {
738    use super::*;
739    #[test]
740    fn test_timestamp() {
741        let t1 = Timestamp::from_us(1000);
742        let t2 = Timestamp::from_us(1500);
743        assert_eq!(t2.elapsed_since(t1), 500);
744        assert!(t1 < t2);
745    }
746    #[test]
747    fn test_typed_id() {
748        struct Foo;
749        let id: TypedId<Foo> = TypedId::new(42);
750        assert_eq!(id.raw(), 42);
751        assert_eq!(format!("{id}"), "#42");
752    }
753    #[test]
754    fn test_id_dispenser() {
755        struct Bar;
756        let mut disp: IdDispenser<Bar> = IdDispenser::new();
757        let a = disp.next();
758        let b = disp.next();
759        assert_eq!(a.raw(), 0);
760        assert_eq!(b.raw(), 1);
761        assert_eq!(disp.count(), 2);
762    }
763    #[test]
764    fn test_slot() {
765        let mut slot: Slot<u32> = Slot::empty();
766        assert!(!slot.is_filled());
767        slot.fill(99);
768        assert!(slot.is_filled());
769        assert_eq!(slot.get(), Some(&99));
770        let v = slot.take();
771        assert_eq!(v, Some(99));
772        assert!(!slot.is_filled());
773    }
774    #[test]
775    #[should_panic]
776    fn test_slot_double_fill() {
777        let mut slot: Slot<u32> = Slot::empty();
778        slot.fill(1);
779        slot.fill(2);
780    }
781    #[test]
782    fn test_memo_slot() {
783        let mut ms: MemoSlot<u32> = MemoSlot::new();
784        assert!(!ms.is_cached());
785        let val = ms.get_or_compute(|| 42);
786        assert_eq!(*val, 42);
787        assert!(ms.is_cached());
788        ms.invalidate();
789        assert!(!ms.is_cached());
790    }
791}
792#[cfg(test)]
793mod tests_ring_buffer {
794    use super::*;
795    #[test]
796    fn test_ring_buffer() {
797        let mut rb = RingBuffer::new(3);
798        rb.push(1u32);
799        rb.push(2u32);
800        rb.push(3u32);
801        assert!(rb.is_full());
802        rb.push(4u32);
803        assert_eq!(rb.pop(), Some(2));
804        assert_eq!(rb.len(), 2);
805    }
806    #[test]
807    fn test_before_after() {
808        let ba = BeforeAfter::new(10u32, 10u32);
809        assert!(ba.unchanged());
810        let ba2 = BeforeAfter::new(10u32, 20u32);
811        assert!(!ba2.unchanged());
812    }
813    #[test]
814    fn test_seq_num() {
815        let s = SeqNum::ZERO;
816        assert_eq!(s.value(), 0);
817        let s2 = s.next();
818        assert_eq!(s2.value(), 1);
819        assert!(s < s2);
820    }
821    #[test]
822    fn test_generation() {
823        let g0 = Generation::INITIAL;
824        let g1 = g0.advance();
825        assert_eq!(g0.number(), 0);
826        assert_eq!(g1.number(), 1);
827        assert_ne!(g0, g1);
828    }
829}
oxilean_kernel/equiv_manager/functions.rs

oxilean_kernel/equiv_manager/
functions.rs
