oxilean_kernel/termination/
functions.rs

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

oxilean_kernel/termination/
functions.rs
