oxilean_kernel/termination/
functions.rs

1//! Auto-generated module
2//!
3//! 🤖 Generated with [SplitRS](https://github.com/cool-japan/splitrs)
4
5use crate::Node;
6use crate::{Expr, Name};
7use std::collections::{HashMap, HashSet};
8use std::rc::Rc;
9
10use super::types::{
11    ConfigNode, DecisionNode, DetailedTerminationResult, Either2, Fixture, FlatSubstitution,
12    FocusStack, LabelSet, MinHeap, NameIndex, NonEmptyVec, ParamInfo, PathBuf, PrefixCounter,
13    RecCallInfo, RewriteRule, RewriteRuleSet, SimpleDag, SlidingSum, SmallMap, SparseVec,
14    StackCalc, StatSummary, Stopwatch, StringPool, StringTrie, TerminationCache,
15    TerminationChecker, TokenBucket, TransformStat, TransitiveClosure, VersionedRecord,
16    WfRelationKind, WindowIterator, WriteOnce,
17};
18
19/// Collect function head and arguments from a nested application.
20pub(super) fn collect_app_args(expr: &Expr) -> (&Expr, Vec<&Expr>) {
21    let mut args = Vec::new();
22    let mut e = expr;
23    while let Expr::App(f, a) = e {
24        args.push(a.as_ref());
25        e = f;
26    }
27    args.reverse();
28    (e, args)
29}
30#[cfg(test)]
31mod tests {
32    use super::*;
33    use crate::Level;
34    #[test]
35    fn test_non_recursive() {
36        let mut checker = TerminationChecker::new();
37        let body = Expr::Lit(crate::Literal::nat(42));
38        assert!(checker.check_terminates(&Name::str("f"), &body).is_ok());
39    }
40    #[test]
41    fn test_simple_recursive() {
42        let mut checker = TerminationChecker::new();
43        let f = Name::str("fact");
44        let n_var = Expr::BVar(0);
45        checker.add_smaller(n_var.clone(), Expr::BVar(1));
46        let body = Expr::App(
47            Node::new(Expr::Const(f.clone(), vec![])),
48            Node::new(Expr::BVar(1)),
49        );
50        assert!(checker.check_terminates(&f, &body).is_ok());
51    }
52    #[test]
53    fn test_lambda_body() {
54        let mut checker = TerminationChecker::new();
55        let f = Name::str("f");
56        let body = Expr::Lam(
57            crate::BinderInfo::Default,
58            Name::str("x"),
59            Node::new(Expr::Sort(Level::zero())),
60            Node::new(Expr::BVar(0)),
61        );
62        assert!(checker.check_terminates(&f, &body).is_ok());
63    }
64    #[test]
65    fn test_depth_limit() {
66        let mut checker = TerminationChecker::new();
67        let f = Name::str("f");
68        let mut body = Expr::BVar(0);
69        for _ in 0..250 {
70            body = Expr::App(
71                Node::new(Expr::Const(Name::str("succ"), vec![])),
72                Node::new(body),
73            );
74        }
75        let result = checker.check_terminates(&f, &body);
76        assert!(result.is_err());
77        assert!(result.unwrap_err().contains("too deeply nested"));
78    }
79    #[test]
80    fn test_smaller_transitivity() {
81        let mut checker = TerminationChecker::new();
82        let a = Expr::Lit(crate::Literal::nat(3));
83        let b = Expr::Lit(crate::Literal::nat(2));
84        let c = Expr::Lit(crate::Literal::nat(1));
85        checker.add_smaller(a.clone(), b.clone());
86        checker.add_smaller(b, c.clone());
87        assert!(checker.is_smaller(&a, &c));
88    }
89    #[test]
90    fn test_collect_app_args() {
91        let f = Expr::Const(Name::str("f"), vec![]);
92        let a = Expr::Lit(crate::Literal::nat(1));
93        let b = Expr::Lit(crate::Literal::nat(2));
94        let app = Expr::App(
95            Node::new(Expr::App(Node::new(f.clone()), Node::new(a.clone()))),
96            Node::new(b.clone()),
97        );
98        let (head, args) = collect_app_args(&app);
99        assert_eq!(head, &f);
100        assert_eq!(args.len(), 2);
101        assert_eq!(args[0], &a);
102        assert_eq!(args[1], &b);
103    }
104    #[test]
105    fn test_register_params() {
106        let mut checker = TerminationChecker::new();
107        checker.register_params(
108            Name::str("f"),
109            vec![ParamInfo {
110                name: Name::str("n"),
111                pos: 0,
112                inductive_type: Some(Name::str("Nat")),
113            }],
114        );
115    }
116    #[test]
117    fn test_no_recursive_calls() {
118        let mut checker = TerminationChecker::new();
119        let f = Name::str("const_fn");
120        let body = Expr::Lit(crate::Literal::nat(0));
121        assert!(checker.check_terminates(&f, &body).is_ok());
122        assert!(checker
123            .get_calls(&f)
124            .expect("value should be present")
125            .is_empty());
126    }
127}
128/// Guard against infinite descent.
129#[allow(dead_code)]
130pub fn has_obvious_nontermination(calls: &[RecCallInfo]) -> bool {
131    calls.iter().any(|c| !c.is_decreasing)
132}
133/// Build a termination certificate for a structurally recursive function.
134#[allow(dead_code)]
135pub fn try_structural_certificate(
136    _function_name: &Name,
137    calls: &[RecCallInfo],
138    param_infos: &[ParamInfo],
139) -> Option<WfRelationKind> {
140    if calls.is_empty() {
141        return None;
142    }
143    for param in param_infos {
144        let all_decrease_at_param = calls
145            .iter()
146            .all(|c| c.arg_pos == param.pos && c.is_decreasing);
147        if all_decrease_at_param {
148            if let Some(ind_ty) = &param.inductive_type {
149                return Some(WfRelationKind::Structural {
150                    inductive_type: ind_ty.clone(),
151                    param_index: param.pos,
152                });
153            }
154        }
155    }
156    if calls.iter().all(|c| c.is_decreasing) {
157        return Some(WfRelationKind::NatSub);
158    }
159    None
160}
161#[cfg(test)]
162mod extended_termination_tests {
163    use super::*;
164    #[test]
165    fn test_wf_relation_structural() {
166        let wf = WfRelationKind::Structural {
167            inductive_type: Name::str("Nat"),
168            param_index: 0,
169        };
170        assert!(wf.is_structural());
171        assert_eq!(wf.lex_depth(), 1);
172    }
173    #[test]
174    fn test_wf_relation_measure() {
175        let wf = WfRelationKind::Measure {
176            measure_fn: Name::str("size"),
177        };
178        assert!(!wf.is_structural());
179        assert!(wf.description().contains("size"));
180    }
181    #[test]
182    fn test_wf_relation_lex_depth() {
183        let wf = WfRelationKind::Lexicographic {
184            components: vec![WfRelationKind::NatSub, WfRelationKind::NatSub],
185        };
186        assert_eq!(wf.lex_depth(), 2);
187    }
188    #[test]
189    fn test_wf_relation_nat_sub() {
190        let wf = WfRelationKind::NatSub;
191        assert_eq!(wf.description(), "nat subtraction");
192    }
193    #[test]
194    fn test_detailed_result_non_recursive() {
195        let r = DetailedTerminationResult::non_recursive(Name::str("f"));
196        assert!(r.terminates);
197        assert!(r.wf_relation.is_none());
198        assert!(r.recursive_calls.is_empty());
199    }
200    #[test]
201    fn test_detailed_result_success() {
202        let wf = WfRelationKind::NatSub;
203        let r = DetailedTerminationResult::success(Name::str("f"), wf, vec![]);
204        assert!(r.terminates);
205        assert!(r.wf_relation.is_some());
206    }
207    #[test]
208    fn test_detailed_result_failure() {
209        let r = DetailedTerminationResult::failure(Name::str("f"), vec![], "not structural");
210        assert!(!r.terminates);
211        assert_eq!(r.explanation, "not structural");
212    }
213    #[test]
214    fn test_obvious_nontermination() {
215        let calls = vec![RecCallInfo {
216            callee: Name::str("f"),
217            arg_pos: 0,
218            arg: Expr::BVar(0),
219            is_decreasing: false,
220        }];
221        assert!(has_obvious_nontermination(&calls));
222        let good = vec![RecCallInfo {
223            callee: Name::str("f"),
224            arg_pos: 0,
225            arg: Expr::BVar(0),
226            is_decreasing: true,
227        }];
228        assert!(!has_obvious_nontermination(&good));
229    }
230    #[test]
231    fn test_termination_cache() {
232        let mut cache = TerminationCache::new();
233        assert!(cache.is_empty());
234        cache.mark_terminating(Name::str("fact"));
235        cache.mark_nonterminating(Name::str("loop"));
236        assert_eq!(cache.is_known_terminating(&Name::str("fact")), Some(true));
237        assert_eq!(cache.is_known_terminating(&Name::str("loop")), Some(false));
238        assert_eq!(cache.is_known_terminating(&Name::str("unknown")), None);
239        assert_eq!(cache.len(), 2);
240    }
241    #[test]
242    fn test_termination_cache_clear() {
243        let mut cache = TerminationCache::new();
244        cache.mark_terminating(Name::str("f"));
245        cache.clear();
246        assert!(cache.is_empty());
247    }
248    #[test]
249    fn test_try_structural_certificate_empty() {
250        let result = try_structural_certificate(&Name::str("f"), &[], &[]);
251        assert!(result.is_none());
252    }
253    #[test]
254    fn test_try_structural_certificate_success() {
255        let calls = vec![RecCallInfo {
256            callee: Name::str("f"),
257            arg_pos: 0,
258            arg: Expr::BVar(0),
259            is_decreasing: true,
260        }];
261        let params = vec![ParamInfo {
262            name: Name::str("n"),
263            pos: 0,
264            inductive_type: Some(Name::str("Nat")),
265        }];
266        let result = try_structural_certificate(&Name::str("f"), &calls, &params);
267        assert!(result.is_some());
268        assert!(result.expect("result should be valid").is_structural());
269    }
270    #[test]
271    fn test_wf_custom_description() {
272        let wf = WfRelationKind::Custom {
273            relation: Name::str("myRel"),
274        };
275        assert!(wf.description().contains("myRel"));
276    }
277}
278/// Version tag for this module.
279#[allow(dead_code)]
280pub const MODULE_VERSION: &str = "1.0.0";
281/// Marker trait for types that can be used in module-specific contexts.
282///
283/// This is a doc-only trait providing context about the module's design philosophy.
284#[allow(dead_code)]
285pub trait ModuleMarker: Sized + Clone + std::fmt::Debug {}
286/// Generic result type for operations in this module.
287#[allow(dead_code)]
288pub type ModuleResult<T> = Result<T, String>;
289/// Create a module-level error string.
290#[allow(dead_code)]
291pub fn module_err(msg: impl Into<String>) -> String {
292    format!("[{module}] {msg}", module = "termination", msg = msg.into())
293}
294/// Compute the Levenshtein distance between two string slices.
295///
296/// This is used for providing "did you mean?" suggestions in error messages.
297#[allow(dead_code)]
298pub fn levenshtein_distance(a: &str, b: &str) -> usize {
299    let la = a.len();
300    let lb = b.len();
301    if la == 0 {
302        return lb;
303    }
304    if lb == 0 {
305        return la;
306    }
307    let mut row: Vec<usize> = (0..=lb).collect();
308    for (i, ca) in a.chars().enumerate() {
309        let mut prev = i;
310        row[0] = i + 1;
311        for (j, cb) in b.chars().enumerate() {
312            let old = row[j + 1];
313            row[j + 1] = if ca == cb {
314                prev
315            } else {
316                1 + old.min(row[j]).min(prev)
317            };
318            prev = old;
319        }
320    }
321    row[lb]
322}
323/// Find the closest match in a list of candidates using Levenshtein distance.
324///
325/// Returns None if candidates is empty.
326#[allow(dead_code)]
327pub fn closest_match<'a>(query: &str, candidates: &[&'a str]) -> Option<&'a str> {
328    candidates
329        .iter()
330        .min_by_key(|&&c| levenshtein_distance(query, c))
331        .copied()
332}
333/// Format a list of names for display in an error message.
334#[allow(dead_code)]
335pub fn format_name_list(names: &[&str]) -> String {
336    match names.len() {
337        0 => "(none)".to_string(),
338        1 => names[0].to_string(),
339        2 => format!("{} and {}", names[0], names[1]),
340        _ => {
341            let mut s = names[..names.len() - 1].join(", ");
342            s.push_str(", and ");
343            s.push_str(names[names.len() - 1]);
344            s
345        }
346    }
347}
348/// Collect all strings from a trie node.
349pub(super) fn collect_strings(node: &StringTrie, results: &mut Vec<String>) {
350    if let Some(v) = &node.value {
351        results.push(v.clone());
352    }
353    for child in node.children.values() {
354        collect_strings(child, results);
355    }
356}
357#[cfg(test)]
358mod utility_tests {
359    use super::*;
360    #[test]
361    fn test_levenshtein_same_string() {
362        assert_eq!(levenshtein_distance("hello", "hello"), 0);
363    }
364    #[test]
365    fn test_levenshtein_empty() {
366        assert_eq!(levenshtein_distance("", "abc"), 3);
367        assert_eq!(levenshtein_distance("abc", ""), 3);
368    }
369    #[test]
370    fn test_levenshtein_one_edit() {
371        assert_eq!(levenshtein_distance("cat", "bat"), 1);
372        assert_eq!(levenshtein_distance("cat", "cats"), 1);
373        assert_eq!(levenshtein_distance("cats", "cat"), 1);
374    }
375    #[test]
376    fn test_closest_match_found() {
377        let candidates = &["intro", "intros", "exact", "apply"];
378        let result = closest_match("intoo", candidates);
379        assert!(result.is_some());
380        assert_eq!(result.expect("result should be valid"), "intro");
381    }
382    #[test]
383    fn test_closest_match_empty() {
384        let result = closest_match("x", &[]);
385        assert!(result.is_none());
386    }
387    #[test]
388    fn test_format_name_list_empty() {
389        assert_eq!(format_name_list(&[]), "(none)");
390    }
391    #[test]
392    fn test_format_name_list_one() {
393        assert_eq!(format_name_list(&["foo"]), "foo");
394    }
395    #[test]
396    fn test_format_name_list_two() {
397        assert_eq!(format_name_list(&["a", "b"]), "a and b");
398    }
399    #[test]
400    fn test_format_name_list_many() {
401        let result = format_name_list(&["a", "b", "c"]);
402        assert!(result.contains("a"));
403        assert!(result.contains("b"));
404        assert!(result.contains("c"));
405        assert!(result.contains("and"));
406    }
407    #[test]
408    fn test_string_trie_insert_contains() {
409        let mut trie = StringTrie::new();
410        trie.insert("hello");
411        trie.insert("help");
412        trie.insert("world");
413        assert!(trie.contains("hello"));
414        assert!(trie.contains("help"));
415        assert!(trie.contains("world"));
416        assert!(!trie.contains("hell"));
417        assert_eq!(trie.len(), 3);
418    }
419    #[test]
420    fn test_string_trie_starts_with() {
421        let mut trie = StringTrie::new();
422        trie.insert("hello");
423        trie.insert("help");
424        trie.insert("world");
425        let results = trie.starts_with("hel");
426        assert_eq!(results.len(), 2);
427    }
428    #[test]
429    fn test_string_trie_empty_prefix() {
430        let mut trie = StringTrie::new();
431        trie.insert("a");
432        trie.insert("b");
433        let results = trie.starts_with("");
434        assert_eq!(results.len(), 2);
435    }
436    #[test]
437    fn test_name_index_basic() {
438        let mut idx = NameIndex::new();
439        let id1 = idx.insert("Nat");
440        let id2 = idx.insert("Bool");
441        let id3 = idx.insert("Nat");
442        assert_eq!(id1, id3);
443        assert_ne!(id1, id2);
444        assert_eq!(idx.len(), 2);
445    }
446    #[test]
447    fn test_name_index_get() {
448        let mut idx = NameIndex::new();
449        let id = idx.insert("test");
450        assert_eq!(idx.get_id("test"), Some(id));
451        assert_eq!(idx.get_name(id), Some("test"));
452        assert_eq!(idx.get_id("missing"), None);
453    }
454    #[test]
455    fn test_name_index_empty() {
456        let idx = NameIndex::new();
457        assert!(idx.is_empty());
458        assert_eq!(idx.len(), 0);
459    }
460}
461#[cfg(test)]
462mod tests_padding_infra {
463    use super::*;
464    #[test]
465    fn test_stat_summary() {
466        let mut ss = StatSummary::new();
467        ss.record(10.0);
468        ss.record(20.0);
469        ss.record(30.0);
470        assert_eq!(ss.count(), 3);
471        assert!((ss.mean().expect("mean should succeed") - 20.0).abs() < 1e-9);
472        assert_eq!(ss.min().expect("min should succeed") as i64, 10);
473        assert_eq!(ss.max().expect("max should succeed") as i64, 30);
474    }
475    #[test]
476    fn test_transform_stat() {
477        let mut ts = TransformStat::new();
478        ts.record_before(100.0);
479        ts.record_after(80.0);
480        let ratio = ts.mean_ratio().expect("ratio should be present");
481        assert!((ratio - 0.8).abs() < 1e-9);
482    }
483    #[test]
484    fn test_small_map() {
485        let mut m: SmallMap<u32, &str> = SmallMap::new();
486        m.insert(3, "three");
487        m.insert(1, "one");
488        m.insert(2, "two");
489        assert_eq!(m.get(&2), Some(&"two"));
490        assert_eq!(m.len(), 3);
491        let keys = m.keys();
492        assert_eq!(*keys[0], 1);
493        assert_eq!(*keys[2], 3);
494    }
495    #[test]
496    fn test_label_set() {
497        let mut ls = LabelSet::new();
498        ls.add("foo");
499        ls.add("bar");
500        ls.add("foo");
501        assert_eq!(ls.count(), 2);
502        assert!(ls.has("bar"));
503        assert!(!ls.has("baz"));
504    }
505    #[test]
506    fn test_config_node() {
507        let mut root = ConfigNode::section("root");
508        let child = ConfigNode::leaf("key", "value");
509        root.add_child(child);
510        assert_eq!(root.num_children(), 1);
511    }
512    #[test]
513    fn test_versioned_record() {
514        let mut vr = VersionedRecord::new(0u32);
515        vr.update(1);
516        vr.update(2);
517        assert_eq!(*vr.current(), 2);
518        assert_eq!(vr.version(), 2);
519        assert!(vr.has_history());
520        assert_eq!(*vr.at_version(0).expect("value should be present"), 0);
521    }
522    #[test]
523    fn test_simple_dag() {
524        let mut dag = SimpleDag::new(4);
525        dag.add_edge(0, 1);
526        dag.add_edge(1, 2);
527        dag.add_edge(2, 3);
528        assert!(dag.can_reach(0, 3));
529        assert!(!dag.can_reach(3, 0));
530        let order = dag.topological_sort().expect("order should be present");
531        assert_eq!(order, vec![0, 1, 2, 3]);
532    }
533    #[test]
534    fn test_focus_stack() {
535        let mut fs: FocusStack<&str> = FocusStack::new();
536        fs.focus("a");
537        fs.focus("b");
538        assert_eq!(fs.current(), Some(&"b"));
539        assert_eq!(fs.depth(), 2);
540        fs.blur();
541        assert_eq!(fs.current(), Some(&"a"));
542    }
543}
544#[cfg(test)]
545mod tests_extra_iterators {
546    use super::*;
547    #[test]
548    fn test_window_iterator() {
549        let data = vec![1u32, 2, 3, 4, 5];
550        let windows: Vec<_> = WindowIterator::new(&data, 3).collect();
551        assert_eq!(windows.len(), 3);
552        assert_eq!(windows[0], &[1, 2, 3]);
553        assert_eq!(windows[2], &[3, 4, 5]);
554    }
555    #[test]
556    fn test_non_empty_vec() {
557        let mut nev = NonEmptyVec::singleton(10u32);
558        nev.push(20);
559        nev.push(30);
560        assert_eq!(nev.len(), 3);
561        assert_eq!(*nev.first(), 10);
562        assert_eq!(*nev.last(), 30);
563    }
564}
565#[cfg(test)]
566mod tests_padding2 {
567    use super::*;
568    #[test]
569    fn test_sliding_sum() {
570        let mut ss = SlidingSum::new(3);
571        ss.push(1.0);
572        ss.push(2.0);
573        ss.push(3.0);
574        assert!((ss.sum() - 6.0).abs() < 1e-9);
575        ss.push(4.0);
576        assert!((ss.sum() - 9.0).abs() < 1e-9);
577        assert_eq!(ss.count(), 3);
578    }
579    #[test]
580    fn test_path_buf() {
581        let mut pb = PathBuf::new();
582        pb.push("src");
583        pb.push("main");
584        assert_eq!(pb.as_str(), "src/main");
585        assert_eq!(pb.depth(), 2);
586        pb.pop();
587        assert_eq!(pb.as_str(), "src");
588    }
589    #[test]
590    fn test_string_pool() {
591        let mut pool = StringPool::new();
592        let s = pool.take();
593        assert!(s.is_empty());
594        pool.give("hello".to_string());
595        let s2 = pool.take();
596        assert!(s2.is_empty());
597        assert_eq!(pool.free_count(), 0);
598    }
599    #[test]
600    fn test_transitive_closure() {
601        let mut tc = TransitiveClosure::new(4);
602        tc.add_edge(0, 1);
603        tc.add_edge(1, 2);
604        tc.add_edge(2, 3);
605        assert!(tc.can_reach(0, 3));
606        assert!(!tc.can_reach(3, 0));
607        let r = tc.reachable_from(0);
608        assert_eq!(r.len(), 4);
609    }
610    #[test]
611    fn test_token_bucket() {
612        let mut tb = TokenBucket::new(100, 0);
613        assert_eq!(tb.available(), 100);
614        assert!(tb.try_consume(50));
615        assert_eq!(tb.available(), 50);
616        assert!(!tb.try_consume(60));
617        assert_eq!(tb.capacity(), 100);
618    }
619    #[test]
620    fn test_rewrite_rule_set() {
621        let mut rrs = RewriteRuleSet::new();
622        rrs.add(RewriteRule::unconditional(
623            "beta",
624            "App(Lam(x, b), v)",
625            "b[x:=v]",
626        ));
627        rrs.add(RewriteRule::conditional("comm", "a + b", "b + a"));
628        assert_eq!(rrs.len(), 2);
629        assert_eq!(rrs.unconditional_rules().len(), 1);
630        assert_eq!(rrs.conditional_rules().len(), 1);
631        assert!(rrs.get("beta").is_some());
632        let disp = rrs
633            .get("beta")
634            .expect("element at \'beta\' should exist")
635            .display();
636        assert!(disp.contains("→"));
637    }
638}
639#[cfg(test)]
640mod tests_padding3 {
641    use super::*;
642    #[test]
643    fn test_decision_node() {
644        let tree = DecisionNode::Branch {
645            key: "x".into(),
646            val: "1".into(),
647            yes_branch: Box::new(DecisionNode::Leaf("yes".into())),
648            no_branch: Box::new(DecisionNode::Leaf("no".into())),
649        };
650        let mut ctx = std::collections::HashMap::new();
651        ctx.insert("x".into(), "1".into());
652        assert_eq!(tree.evaluate(&ctx), "yes");
653        ctx.insert("x".into(), "2".into());
654        assert_eq!(tree.evaluate(&ctx), "no");
655        assert_eq!(tree.depth(), 1);
656    }
657    #[test]
658    fn test_flat_substitution() {
659        let mut sub = FlatSubstitution::new();
660        sub.add("foo", "bar");
661        sub.add("baz", "qux");
662        assert_eq!(sub.apply("foo and baz"), "bar and qux");
663        assert_eq!(sub.len(), 2);
664    }
665    #[test]
666    fn test_stopwatch() {
667        let mut sw = Stopwatch::start();
668        sw.split();
669        sw.split();
670        assert_eq!(sw.num_splits(), 2);
671        assert!(sw.elapsed_ms() >= 0.0);
672        for &s in sw.splits() {
673            assert!(s >= 0.0);
674        }
675    }
676    #[test]
677    fn test_either2() {
678        let e: Either2<i32, &str> = Either2::First(42);
679        assert!(e.is_first());
680        let mapped = e.map_first(|x| x * 2);
681        assert_eq!(mapped.first(), Some(84));
682        let e2: Either2<i32, &str> = Either2::Second("hello");
683        assert!(e2.is_second());
684        assert_eq!(e2.second(), Some("hello"));
685    }
686    #[test]
687    fn test_write_once() {
688        let wo: WriteOnce<u32> = WriteOnce::new();
689        assert!(!wo.is_written());
690        assert!(wo.write(42));
691        assert!(!wo.write(99));
692        assert_eq!(wo.read(), Some(42));
693    }
694    #[test]
695    fn test_sparse_vec() {
696        let mut sv: SparseVec<i32> = SparseVec::new(100);
697        sv.set(5, 10);
698        sv.set(50, 20);
699        assert_eq!(*sv.get(5), 10);
700        assert_eq!(*sv.get(50), 20);
701        assert_eq!(*sv.get(0), 0);
702        assert_eq!(sv.nnz(), 2);
703        sv.set(5, 0);
704        assert_eq!(sv.nnz(), 1);
705    }
706    #[test]
707    fn test_stack_calc() {
708        let mut calc = StackCalc::new();
709        calc.push(3);
710        calc.push(4);
711        assert_eq!(calc.add(), Some(7));
712        assert_eq!(calc.peek(), Some(7));
713        calc.push(2);
714        assert_eq!(calc.mul(), Some(14));
715        assert_eq!(calc.peek(), Some(14));
716    }
717}
718#[cfg(test)]
719mod tests_final_padding {
720    use super::*;
721    #[test]
722    fn test_min_heap() {
723        let mut h = MinHeap::new();
724        h.push(5u32);
725        h.push(1u32);
726        h.push(3u32);
727        assert_eq!(h.peek(), Some(&1));
728        assert_eq!(h.pop(), Some(1));
729        assert_eq!(h.pop(), Some(3));
730        assert_eq!(h.pop(), Some(5));
731        assert!(h.is_empty());
732    }
733    #[test]
734    fn test_prefix_counter() {
735        let mut pc = PrefixCounter::new();
736        pc.record("hello");
737        pc.record("help");
738        pc.record("world");
739        assert_eq!(pc.count_with_prefix("hel"), 2);
740        assert_eq!(pc.count_with_prefix("wor"), 1);
741        assert_eq!(pc.count_with_prefix("xyz"), 0);
742    }
743    #[test]
744    fn test_fixture() {
745        let mut f = Fixture::new();
746        f.set("key1", "val1");
747        f.set("key2", "val2");
748        assert_eq!(f.get("key1"), Some("val1"));
749        assert_eq!(f.get("key3"), None);
750        assert_eq!(f.len(), 2);
751    }
752}
oxilean_kernel/termination/functions.rs

oxilean_kernel/termination/
functions.rs
