1use crate::{BinderInfo, Expr, Level, Literal, Name};
6use std::collections::HashMap;
7use std::hash::{Hash, Hasher};
8
9use super::types::{
10 BitSet64, BucketCounter, CacheSessionStats, ConfigNode, DecisionNode, Either2, EvictionTracker,
11 ExprHashcons, ExprId, ExprPool, Fixture, FlatSubstitution, FocusStack, InvalidationSet,
12 LabelSet, MemoTable, MinHeap, NonEmptyVec, PathBuf, PathCache, PrefixCounter, RcExprPool,
13 RewriteRule, RewriteRuleSet, SimpleDag, SlidingSum, SmallMap, SparseVec, StackCalc,
14 StatSummary, Stopwatch, StringPool, TokenBucket, TransformStat, TransitiveClosure,
15 TwoLevelCache, VersionedCache, VersionedRecord, WindowIterator, WriteOnce,
16};
17
18pub(super) fn hash_tag(state: &mut impl Hasher, tag: u8) {
20 state.write_u8(tag);
21}
22pub(super) fn hash_level(level: &Level, state: &mut impl Hasher) {
24 level.hash(state);
25}
26pub(super) fn hash_name(name: &Name, state: &mut impl Hasher) {
28 name.hash(state);
29}
30pub(super) fn hash_binder_info(bi: &BinderInfo, state: &mut impl Hasher) {
32 bi.hash(state);
33}
34pub(super) fn hash_literal(lit: &Literal, state: &mut impl Hasher) {
36 lit.hash(state);
37}
38#[cfg(test)]
39mod tests {
40 use super::*;
41 use crate::{Expr, Level, Name};
42 fn nat_expr() -> Expr {
43 Expr::Const(Name::str("Nat"), vec![])
44 }
45 fn prop_expr() -> Expr {
46 Expr::Sort(Level::Zero)
47 }
48 fn type1_expr() -> Expr {
49 Expr::Sort(Level::succ(Level::Zero))
50 }
51 fn bvar0() -> Expr {
52 Expr::BVar(0)
53 }
54 #[test]
55 fn test_intern_same_expr_twice() {
56 let mut hc = ExprHashcons::new();
57 let (id1, was_new1) = hc.intern(nat_expr());
58 let (id2, was_new2) = hc.intern(nat_expr());
59 assert!(was_new1, "first intern should be new");
60 assert!(!was_new2, "second intern of same expr should be a hit");
61 assert_eq!(id1, id2, "same expr must yield same ExprId");
62 }
63 #[test]
64 fn test_intern_different_exprs() {
65 let mut hc = ExprHashcons::new();
66 let (id1, _) = hc.intern(nat_expr());
67 let (id2, _) = hc.intern(prop_expr());
68 let (id3, _) = hc.intern(bvar0());
69 assert_ne!(id1, id2);
70 assert_ne!(id2, id3);
71 assert_ne!(id1, id3);
72 assert_eq!(hc.size(), 3);
73 }
74 #[test]
75 fn test_hit_rate_empty() {
76 let hc = ExprHashcons::new();
77 assert_eq!(hc.hit_rate(), 0.0, "empty table hit rate should be 0.0");
78 }
79 #[test]
80 fn test_hit_rate_with_duplicates() {
81 let mut hc = ExprHashcons::new();
82 hc.intern(nat_expr());
83 hc.intern(nat_expr());
84 hc.intern(nat_expr());
85 hc.intern(prop_expr());
86 let rate = hc.hit_rate();
87 assert!(
88 (rate - 0.5).abs() < 1e-9,
89 "expected hit rate 0.5, got {}",
90 rate
91 );
92 }
93 #[test]
94 fn test_pool_add_root() {
95 let mut pool = ExprPool::new();
96 let id = pool.add_root(nat_expr());
97 assert_eq!(pool.live_count(), 1);
98 assert_eq!(pool.total_count(), 1);
99 assert_eq!(pool.get(id), Some(&nat_expr()));
100 }
101 #[test]
102 fn test_pool_live_count() {
103 let mut pool = ExprPool::new();
104 let id1 = pool.add_root(nat_expr());
105 let _id2 = pool.add(prop_expr());
106 let id3 = pool.add_root(type1_expr());
107 assert_eq!(pool.live_count(), 2);
108 assert_eq!(pool.total_count(), 3);
109 let prop_id = pool
110 .get_id(&prop_expr())
111 .expect("prop_id should be present");
112 pool.mark_root(prop_id);
113 assert_eq!(pool.live_count(), 3);
114 pool.mark_root(id1);
115 pool.mark_root(id3);
116 assert_eq!(pool.live_count(), 3);
117 }
118 #[test]
119 fn test_dedup_ratio() {
120 let mut pool = ExprPool::new();
121 pool.add(nat_expr());
122 pool.add(nat_expr());
123 pool.add(nat_expr());
124 let ratio = pool.dedup_ratio();
125 assert!(
126 (ratio - 2.0 / 3.0).abs() < 1e-9,
127 "expected dedup_ratio ~0.666, got {}",
128 ratio
129 );
130 }
131 #[test]
132 fn test_get_by_id() {
133 let mut hc = ExprHashcons::new();
134 let e = Expr::BVar(42);
135 let (id, _) = hc.intern(e.clone());
136 let retrieved = hc.get(id);
137 assert_eq!(retrieved, Some(&e));
138 let bad_id = ExprId(9999);
139 assert_eq!(hc.get(bad_id), None);
140 }
141 #[test]
142 fn test_get_id_lookup() {
143 let mut hc = ExprHashcons::new();
144 let (id, _) = hc.intern(nat_expr());
145 let found = hc.get_id(&nat_expr());
146 assert_eq!(found, Some(id));
147 let unknown = hc.get_id(&prop_expr());
148 assert_eq!(unknown, None);
149 }
150}
151#[cfg(test)]
152mod tests_cache_extended {
153 use super::*;
154 #[test]
155 fn test_eviction_tracker_lru_mru() {
156 let mut t = EvictionTracker::new(3);
157 t.access(1);
158 t.access(2);
159 t.access(3);
160 assert_eq!(t.lru(), Some(1));
161 assert_eq!(t.mru(), Some(3));
162 t.access(1);
163 assert_eq!(t.lru(), Some(2));
164 assert_eq!(t.mru(), Some(1));
165 }
166 #[test]
167 fn test_eviction_tracker_capacity() {
168 let mut t = EvictionTracker::new(2);
169 t.access(10);
170 t.access(20);
171 t.access(30);
172 assert_eq!(t.len(), 2);
173 assert_eq!(t.lru(), Some(20));
174 }
175 #[test]
176 fn test_memo_table_insert_get_remove() {
177 let mut m = MemoTable::new();
178 m.insert(100, 999);
179 assert_eq!(m.get(100), Some(999));
180 m.insert(100, 1000);
181 assert_eq!(m.get(100), Some(1000));
182 let old = m.remove(100);
183 assert_eq!(old, Some(1000));
184 assert_eq!(m.get(100), None);
185 }
186 #[test]
187 fn test_cache_session_stats() {
188 let mut s = CacheSessionStats::new();
189 s.hits = 80;
190 s.misses = 20;
191 assert!((s.hit_rate() - 0.8).abs() < 1e-9);
192 let summary = s.summary();
193 assert!(summary.contains("hit_rate=80.0%"));
194 }
195 #[test]
196 fn test_two_level_cache() {
197 let mut cache = TwoLevelCache::new(2);
198 cache.insert(1, 100);
199 cache.insert(2, 200);
200 assert_eq!(cache.get(1), Some(100));
201 assert_eq!(cache.get(2), Some(200));
202 assert_eq!(cache.get(99), None);
203 cache.insert(3, 300);
204 assert_eq!(cache.total_len(), 3);
205 }
206 #[test]
207 fn test_path_cache() {
208 let mut pc = PathCache::new();
209 pc.insert(&[1, 2, 3], 42);
210 pc.insert(&[1, 2, 4], 43);
211 pc.insert(&[5], 99);
212 assert_eq!(pc.get(&[1, 2, 3]), Some(42));
213 assert_eq!(pc.get(&[1, 2, 4]), Some(43));
214 assert_eq!(pc.get(&[5]), Some(99));
215 assert_eq!(pc.get(&[1, 2]), None);
216 assert_eq!(pc.get(&[6]), None);
217 }
218 #[test]
219 fn test_versioned_cache() {
220 let mut vc = VersionedCache::new();
221 vc.insert(10, 100);
222 assert_eq!(vc.get(10), Some(100));
223 vc.bump_version();
224 assert_eq!(vc.get(10), None);
225 vc.insert(10, 200);
226 assert_eq!(vc.get(10), Some(200));
227 vc.evict_stale();
228 assert_eq!(vc.valid_count(), 1);
229 }
230 #[test]
231 fn test_rc_expr_pool_gc() {
232 let mut pool = RcExprPool::new();
233 let i1 = pool.alloc(111);
234 let _i2 = pool.alloc(222);
235 pool.inc_ref(i1);
236 pool.dec_ref(i1);
237 pool.dec_ref(i1);
238 let dead = pool.collect_garbage();
239 assert!(dead.contains(&i1));
240 assert_eq!(pool.live_count(), 1);
241 }
242 #[test]
243 fn test_invalidation_set() {
244 let mut inv = InvalidationSet::new();
245 inv.add(1);
246 inv.add(2);
247 inv.add(1);
248 assert_eq!(inv.len(), 2);
249 assert!(inv.contains(1));
250 assert!(!inv.contains(99));
251 inv.clear();
252 assert!(inv.is_empty());
253 }
254}
255#[cfg(test)]
256mod tests_padding_infra {
257 use super::*;
258 #[test]
259 fn test_stat_summary() {
260 let mut ss = StatSummary::new();
261 ss.record(10.0);
262 ss.record(20.0);
263 ss.record(30.0);
264 assert_eq!(ss.count(), 3);
265 assert!((ss.mean().expect("mean should succeed") - 20.0).abs() < 1e-9);
266 assert_eq!(ss.min().expect("min should succeed") as i64, 10);
267 assert_eq!(ss.max().expect("max should succeed") as i64, 30);
268 }
269 #[test]
270 fn test_transform_stat() {
271 let mut ts = TransformStat::new();
272 ts.record_before(100.0);
273 ts.record_after(80.0);
274 let ratio = ts.mean_ratio().expect("ratio should be present");
275 assert!((ratio - 0.8).abs() < 1e-9);
276 }
277 #[test]
278 fn test_small_map() {
279 let mut m: SmallMap<u32, &str> = SmallMap::new();
280 m.insert(3, "three");
281 m.insert(1, "one");
282 m.insert(2, "two");
283 assert_eq!(m.get(&2), Some(&"two"));
284 assert_eq!(m.len(), 3);
285 let keys = m.keys();
286 assert_eq!(*keys[0], 1);
287 assert_eq!(*keys[2], 3);
288 }
289 #[test]
290 fn test_label_set() {
291 let mut ls = LabelSet::new();
292 ls.add("foo");
293 ls.add("bar");
294 ls.add("foo");
295 assert_eq!(ls.count(), 2);
296 assert!(ls.has("bar"));
297 assert!(!ls.has("baz"));
298 }
299 #[test]
300 fn test_config_node() {
301 let mut root = ConfigNode::section("root");
302 let child = ConfigNode::leaf("key", "value");
303 root.add_child(child);
304 assert_eq!(root.num_children(), 1);
305 }
306 #[test]
307 fn test_versioned_record() {
308 let mut vr = VersionedRecord::new(0u32);
309 vr.update(1);
310 vr.update(2);
311 assert_eq!(*vr.current(), 2);
312 assert_eq!(vr.version(), 2);
313 assert!(vr.has_history());
314 assert_eq!(*vr.at_version(0).expect("value should be present"), 0);
315 }
316 #[test]
317 fn test_simple_dag() {
318 let mut dag = SimpleDag::new(4);
319 dag.add_edge(0, 1);
320 dag.add_edge(1, 2);
321 dag.add_edge(2, 3);
322 assert!(dag.can_reach(0, 3));
323 assert!(!dag.can_reach(3, 0));
324 let order = dag.topological_sort().expect("order should be present");
325 assert_eq!(order, vec![0, 1, 2, 3]);
326 }
327 #[test]
328 fn test_focus_stack() {
329 let mut fs: FocusStack<&str> = FocusStack::new();
330 fs.focus("a");
331 fs.focus("b");
332 assert_eq!(fs.current(), Some(&"b"));
333 assert_eq!(fs.depth(), 2);
334 fs.blur();
335 assert_eq!(fs.current(), Some(&"a"));
336 }
337}
338#[cfg(test)]
339mod tests_extra_iterators {
340 use super::*;
341 #[test]
342 fn test_window_iterator() {
343 let data = vec![1u32, 2, 3, 4, 5];
344 let windows: Vec<_> = WindowIterator::new(&data, 3).collect();
345 assert_eq!(windows.len(), 3);
346 assert_eq!(windows[0], &[1, 2, 3]);
347 assert_eq!(windows[2], &[3, 4, 5]);
348 }
349 #[test]
350 fn test_non_empty_vec() {
351 let mut nev = NonEmptyVec::singleton(10u32);
352 nev.push(20);
353 nev.push(30);
354 assert_eq!(nev.len(), 3);
355 assert_eq!(*nev.first(), 10);
356 assert_eq!(*nev.last(), 30);
357 }
358}
359#[cfg(test)]
360mod tests_padding2 {
361 use super::*;
362 #[test]
363 fn test_sliding_sum() {
364 let mut ss = SlidingSum::new(3);
365 ss.push(1.0);
366 ss.push(2.0);
367 ss.push(3.0);
368 assert!((ss.sum() - 6.0).abs() < 1e-9);
369 ss.push(4.0);
370 assert!((ss.sum() - 9.0).abs() < 1e-9);
371 assert_eq!(ss.count(), 3);
372 }
373 #[test]
374 fn test_path_buf() {
375 let mut pb = PathBuf::new();
376 pb.push("src");
377 pb.push("main");
378 assert_eq!(pb.as_str(), "src/main");
379 assert_eq!(pb.depth(), 2);
380 pb.pop();
381 assert_eq!(pb.as_str(), "src");
382 }
383 #[test]
384 fn test_string_pool() {
385 let mut pool = StringPool::new();
386 let s = pool.take();
387 assert!(s.is_empty());
388 pool.give("hello".to_string());
389 let s2 = pool.take();
390 assert!(s2.is_empty());
391 assert_eq!(pool.free_count(), 0);
392 }
393 #[test]
394 fn test_transitive_closure() {
395 let mut tc = TransitiveClosure::new(4);
396 tc.add_edge(0, 1);
397 tc.add_edge(1, 2);
398 tc.add_edge(2, 3);
399 assert!(tc.can_reach(0, 3));
400 assert!(!tc.can_reach(3, 0));
401 let r = tc.reachable_from(0);
402 assert_eq!(r.len(), 4);
403 }
404 #[test]
405 fn test_token_bucket() {
406 let mut tb = TokenBucket::new(100, 10);
407 assert_eq!(tb.available(), 100);
408 assert!(tb.try_consume(50));
409 assert_eq!(tb.available(), 50);
410 assert!(!tb.try_consume(60));
411 assert_eq!(tb.capacity(), 100);
412 }
413 #[test]
414 fn test_rewrite_rule_set() {
415 let mut rrs = RewriteRuleSet::new();
416 rrs.add(RewriteRule::unconditional(
417 "beta",
418 "App(Lam(x, b), v)",
419 "b[x:=v]",
420 ));
421 rrs.add(RewriteRule::conditional("comm", "a + b", "b + a"));
422 assert_eq!(rrs.len(), 2);
423 assert_eq!(rrs.unconditional_rules().len(), 1);
424 assert_eq!(rrs.conditional_rules().len(), 1);
425 assert!(rrs.get("beta").is_some());
426 let disp = rrs
427 .get("beta")
428 .expect("element at \'beta\' should exist")
429 .display();
430 assert!(disp.contains("→"));
431 }
432}
433#[cfg(test)]
434mod tests_padding3 {
435 use super::*;
436 #[test]
437 fn test_decision_node() {
438 let tree = DecisionNode::Branch {
439 key: "x".into(),
440 val: "1".into(),
441 yes_branch: Box::new(DecisionNode::Leaf("yes".into())),
442 no_branch: Box::new(DecisionNode::Leaf("no".into())),
443 };
444 let mut ctx = std::collections::HashMap::new();
445 ctx.insert("x".into(), "1".into());
446 assert_eq!(tree.evaluate(&ctx), "yes");
447 ctx.insert("x".into(), "2".into());
448 assert_eq!(tree.evaluate(&ctx), "no");
449 assert_eq!(tree.depth(), 1);
450 }
451 #[test]
452 fn test_flat_substitution() {
453 let mut sub = FlatSubstitution::new();
454 sub.add("foo", "bar");
455 sub.add("baz", "qux");
456 assert_eq!(sub.apply("foo and baz"), "bar and qux");
457 assert_eq!(sub.len(), 2);
458 }
459 #[test]
460 fn test_stopwatch() {
461 let mut sw = Stopwatch::start();
462 sw.split();
463 sw.split();
464 assert_eq!(sw.num_splits(), 2);
465 assert!(sw.elapsed_ms() >= 0.0);
466 for &s in sw.splits() {
467 assert!(s >= 0.0);
468 }
469 }
470 #[test]
471 fn test_either2() {
472 let e: Either2<i32, &str> = Either2::First(42);
473 assert!(e.is_first());
474 let mapped = e.map_first(|x| x * 2);
475 assert_eq!(mapped.first(), Some(84));
476 let e2: Either2<i32, &str> = Either2::Second("hello");
477 assert!(e2.is_second());
478 assert_eq!(e2.second(), Some("hello"));
479 }
480 #[test]
481 fn test_write_once() {
482 let wo: WriteOnce<u32> = WriteOnce::new();
483 assert!(!wo.is_written());
484 assert!(wo.write(42));
485 assert!(!wo.write(99));
486 assert_eq!(wo.read(), Some(42));
487 }
488 #[test]
489 fn test_sparse_vec() {
490 let mut sv: SparseVec<i32> = SparseVec::new(100);
491 sv.set(5, 10);
492 sv.set(50, 20);
493 assert_eq!(*sv.get(5), 10);
494 assert_eq!(*sv.get(50), 20);
495 assert_eq!(*sv.get(0), 0);
496 assert_eq!(sv.nnz(), 2);
497 sv.set(5, 0);
498 assert_eq!(sv.nnz(), 1);
499 }
500 #[test]
501 fn test_stack_calc() {
502 let mut calc = StackCalc::new();
503 calc.push(3);
504 calc.push(4);
505 calc.add();
506 assert_eq!(calc.peek(), Some(7));
507 calc.push(2);
508 calc.mul();
509 assert_eq!(calc.peek(), Some(14));
510 }
511}
512#[cfg(test)]
513mod tests_final_padding {
514 use super::*;
515 #[test]
516 fn test_min_heap() {
517 let mut h = MinHeap::new();
518 h.push(5u32);
519 h.push(1u32);
520 h.push(3u32);
521 assert_eq!(h.peek(), Some(&1));
522 assert_eq!(h.pop(), Some(1));
523 assert_eq!(h.pop(), Some(3));
524 assert_eq!(h.pop(), Some(5));
525 assert!(h.is_empty());
526 }
527 #[test]
528 fn test_prefix_counter() {
529 let mut pc = PrefixCounter::new();
530 pc.record("hello");
531 pc.record("help");
532 pc.record("world");
533 assert_eq!(pc.count_with_prefix("hel"), 2);
534 assert_eq!(pc.count_with_prefix("wor"), 1);
535 assert_eq!(pc.count_with_prefix("xyz"), 0);
536 }
537 #[test]
538 fn test_fixture() {
539 let mut f = Fixture::new();
540 f.set("key1", "val1");
541 f.set("key2", "val2");
542 assert_eq!(f.get("key1"), Some("val1"));
543 assert_eq!(f.get("key3"), None);
544 assert_eq!(f.len(), 2);
545 }
546}
547#[cfg(test)]
548mod tests_tiny_padding {
549 use super::*;
550 #[test]
551 fn test_bitset64() {
552 let mut bs = BitSet64::new();
553 bs.insert(0);
554 bs.insert(63);
555 assert!(bs.contains(0));
556 assert!(bs.contains(63));
557 assert!(!bs.contains(1));
558 assert_eq!(bs.len(), 2);
559 bs.remove(0);
560 assert!(!bs.contains(0));
561 }
562 #[test]
563 fn test_bucket_counter() {
564 let mut bc: BucketCounter<4> = BucketCounter::new();
565 bc.inc(0);
566 bc.inc(0);
567 bc.inc(1);
568 assert_eq!(bc.get(0), 2);
569 assert_eq!(bc.total(), 3);
570 assert_eq!(bc.argmax(), 0);
571 }
572}