ipfrs_tensorlogic/
rule_dependency.rs

1//! Rule Dependency Graph
2//!
3//! Before executing inference, rules must be evaluated in a well-defined order
4//! determined by their interdependencies. This module builds a directed dependency
5//! graph over rule IDs and computes a topological evaluation schedule so that every
6//! rule is processed only after the rules it depends upon have already been applied.
7//!
8//! # Dependency types
9//!
10//! | Variant | Meaning |
11//! |---------|---------|
12//! | [`DependencyType::UsesConclusion`] | The head of one rule appears in the body of another. |
13//! | [`DependencyType::SharesBody`] | Two rules share at least one body predicate. |
14//! | [`DependencyType::Negation`] | A rule uses the negation of another rule's conclusion. |
15//! | [`DependencyType::Subsumption`] | One rule's conclusion is subsumed by another. |
16//!
17//! # Examples
18//!
19//! ```
20//! use ipfrs_tensorlogic::rule_dependency::{
21//!     DependencyType, EvaluationSchedule, RuleDependencyGraph,
22//! };
23//!
24//! let mut g = RuleDependencyGraph::new();
25//! g.add_rule("base").expect("example: should succeed in docs");
26//! g.add_rule("derived").expect("example: should succeed in docs");
27//! g.add_dependency("derived", "base", DependencyType::UsesConclusion).expect("example: should succeed in docs");
28//!
29//! let order = g.topological_sort().expect("example: should succeed in docs");
30//! assert_eq!(order, vec!["base".to_string(), "derived".to_string()]);
31//!
32//! let sched = EvaluationSchedule::build(&g).expect("example: should succeed in docs");
33//! assert_eq!(sched.layer_count(), 2);
34//! assert_eq!(sched.total_rules(), 2);
35//! ```
36
37use std::collections::{HashMap, HashSet, VecDeque};
38use std::fmt;
39
40use thiserror::Error;
41
42// ─── RuleId ──────────────────────────────────────────────────────────────────
43
44/// A newtype wrapping a [`String`] that uniquely identifies a rule.
45#[derive(Debug, Clone, PartialEq, Eq, Hash)]
46pub struct RuleId(pub String);
47
48impl fmt::Display for RuleId {
49    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
50        f.write_str(&self.0)
51    }
52}
53
54impl From<String> for RuleId {
55    fn from(s: String) -> Self {
56        RuleId(s)
57    }
58}
59
60impl From<&str> for RuleId {
61    fn from(s: &str) -> Self {
62        RuleId(s.to_string())
63    }
64}
65
66// ─── DependencyType ──────────────────────────────────────────────────────────
67
68/// Characterises the semantic relationship between two rules in the dependency
69/// graph.
70#[derive(Debug, Clone, PartialEq, Eq, Hash)]
71pub enum DependencyType {
72    /// The conclusion (head) of the `to` rule is used in the body of the
73    /// `from` rule.
74    UsesConclusion,
75    /// Both rules share at least one body predicate, so evaluation order
76    /// matters for consistency.
77    SharesBody,
78    /// The `from` rule uses the negation of a predicate derived by the `to`
79    /// rule; must be evaluated after `to` under stratified semantics.
80    Negation,
81    /// The conclusion of the `from` rule is subsumed by (i.e. is a special
82    /// case of) the conclusion of the `to` rule.
83    Subsumption,
84}
85
86// ─── RuleDependency ──────────────────────────────────────────────────────────
87
88/// A directed edge in the rule dependency graph.
89///
90/// Semantics: `from` depends on `to`.  `to` must be evaluated before `from`.
91#[derive(Debug, Clone, PartialEq, Eq)]
92pub struct RuleDependency {
93    /// The rule that depends on another.
94    pub from: RuleId,
95    /// The rule that must be evaluated first.
96    pub to: RuleId,
97    /// The nature of the dependency.
98    pub dep_type: DependencyType,
99}
100
101// ─── DepError ────────────────────────────────────────────────────────────────
102
103/// Errors produced by [`RuleDependencyGraph`] and [`EvaluationSchedule`].
104#[derive(Debug, Error)]
105pub enum DepError {
106    /// A rule with this ID was registered more than once.
107    #[error("duplicate rule: {0}")]
108    DuplicateRule(String),
109
110    /// A referenced rule ID does not exist in the graph.
111    #[error("rule not found: {0}")]
112    RuleNotFound(String),
113
114    /// The graph contains at least one cycle, making topological ordering
115    /// impossible.  `involved` holds the IDs of the rules participating in the
116    /// cycle.
117    #[error("cycle detected among rules: {}", involved.join(", "))]
118    CycleDetected {
119        /// Rule IDs that are part of the cycle.
120        involved: Vec<String>,
121    },
122
123    /// At least one endpoint of a dependency edge was not registered.
124    #[error("dependency endpoint missing: from={from}, to={to}")]
125    DependencyEndpointMissing {
126        /// The `from` rule ID that was not found.
127        from: String,
128        /// The `to` rule ID that was not found.
129        to: String,
130    },
131}
132
133// ─── RuleDependencyGraph ─────────────────────────────────────────────────────
134
135/// A directed graph that records dependencies between rules and can derive a
136/// safe topological evaluation order.
137///
138/// Nodes are rule IDs (plain [`String`]s kept in a [`HashSet`] for O(1)
139/// membership tests).  Edges are [`RuleDependency`] values stored in a
140/// [`Vec`].
141///
142/// # Invariants
143///
144/// * Both endpoints of every [`RuleDependency`] must already be registered
145///   via [`add_rule`][Self::add_rule] before the edge can be added.
146/// * Duplicate rule IDs are rejected with [`DepError::DuplicateRule`].
147#[derive(Debug, Default)]
148pub struct RuleDependencyGraph {
149    /// Set of registered rule IDs.
150    pub rules: HashSet<String>,
151    /// All dependency edges.
152    pub deps: Vec<RuleDependency>,
153}
154
155impl RuleDependencyGraph {
156    /// Create an empty graph.
157    pub fn new() -> Self {
158        Self::default()
159    }
160
161    /// Register a new rule.
162    ///
163    /// # Errors
164    ///
165    /// Returns [`DepError::DuplicateRule`] if a rule with the same ID is
166    /// already present.
167    pub fn add_rule(&mut self, id: &str) -> Result<(), DepError> {
168        if self.rules.contains(id) {
169            return Err(DepError::DuplicateRule(id.to_string()));
170        }
171        self.rules.insert(id.to_string());
172        Ok(())
173    }
174
175    /// Add a directed dependency edge `from` → `to` (meaning `from` depends
176    /// on `to`).
177    ///
178    /// # Errors
179    ///
180    /// Returns [`DepError::DependencyEndpointMissing`] if either endpoint has
181    /// not been registered.
182    pub fn add_dependency(
183        &mut self,
184        from: &str,
185        to: &str,
186        dep_type: DependencyType,
187    ) -> Result<(), DepError> {
188        let from_exists = self.rules.contains(from);
189        let to_exists = self.rules.contains(to);
190        if !from_exists || !to_exists {
191            return Err(DepError::DependencyEndpointMissing {
192                from: from.to_string(),
193                to: to.to_string(),
194            });
195        }
196        self.deps.push(RuleDependency {
197            from: RuleId::from(from),
198            to: RuleId::from(to),
199            dep_type,
200        });
201        Ok(())
202    }
203
204    /// Compute a topological ordering of all registered rules using
205    /// [Kahn's algorithm].
206    ///
207    /// The ordering guarantees that for every dependency edge `from` → `to`,
208    /// `to` appears *before* `from` in the returned vector.
209    ///
210    /// [Kahn's algorithm]: https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm
211    ///
212    /// # Errors
213    ///
214    /// Returns [`DepError::CycleDetected`] if the graph contains a cycle.
215    pub fn topological_sort(&self) -> Result<Vec<String>, DepError> {
216        // Build adjacency list and in-degree map.
217        // Edge direction: (to -> from) for adjacency (from depends on to).
218        // In-degree counts how many `to` nodes point *into* each `from` node.
219        let mut in_degree: HashMap<String, usize> =
220            self.rules.iter().map(|r| (r.clone(), 0)).collect();
221
222        // adjacency: to -> list of `from` rules that depend on it
223        let mut adj: HashMap<String, Vec<String>> =
224            self.rules.iter().map(|r| (r.clone(), Vec::new())).collect();
225
226        for dep in &self.deps {
227            let from_str = dep.from.0.clone();
228            let to_str = dep.to.0.clone();
229            adj.entry(to_str).or_default().push(from_str.clone());
230            *in_degree.entry(from_str).or_insert(0) += 1;
231        }
232
233        // Initialise queue with all zero-in-degree nodes (sorted for determinism).
234        let mut queue: VecDeque<String> = {
235            let mut zeros: Vec<String> = in_degree
236                .iter()
237                .filter(|(_, &d)| d == 0)
238                .map(|(r, _)| r.clone())
239                .collect();
240            zeros.sort();
241            VecDeque::from(zeros)
242        };
243
244        let mut result: Vec<String> = Vec::with_capacity(self.rules.len());
245
246        while let Some(node) = queue.pop_front() {
247            result.push(node.clone());
248            if let Some(dependents) = adj.get(&node) {
249                let mut next_batch: Vec<String> = Vec::new();
250                for dep_node in dependents {
251                    let deg = in_degree.get_mut(dep_node).expect("node always present");
252                    *deg -= 1;
253                    if *deg == 0 {
254                        next_batch.push(dep_node.clone());
255                    }
256                }
257                next_batch.sort();
258                for n in next_batch {
259                    queue.push_back(n);
260                }
261            }
262        }
263
264        if result.len() != self.rules.len() {
265            // Collect all nodes that still have non-zero in-degree — they are
266            // part of the cycle.
267            let mut involved: Vec<String> = in_degree
268                .into_iter()
269                .filter(|(_, d)| *d > 0)
270                .map(|(r, _)| r)
271                .collect();
272            involved.sort();
273            return Err(DepError::CycleDetected { involved });
274        }
275
276        Ok(result)
277    }
278
279    /// Return the IDs of rules that `rule_id` directly depends on (i.e. the
280    /// `to` endpoints of all edges whose `from` is `rule_id`).
281    pub fn dependencies_of(&self, rule_id: &str) -> Vec<String> {
282        let mut deps: Vec<String> = self
283            .deps
284            .iter()
285            .filter(|d| d.from.0 == rule_id)
286            .map(|d| d.to.0.clone())
287            .collect();
288        deps.sort();
289        deps.dedup();
290        deps
291    }
292
293    /// Return the IDs of rules that directly depend on `rule_id` (i.e. the
294    /// `from` endpoints of all edges whose `to` is `rule_id`).
295    pub fn dependents_of(&self, rule_id: &str) -> Vec<String> {
296        let mut deps: Vec<String> = self
297            .deps
298            .iter()
299            .filter(|d| d.to.0 == rule_id)
300            .map(|d| d.from.0.clone())
301            .collect();
302        deps.sort();
303        deps.dedup();
304        deps
305    }
306
307    /// Return `true` if the dependency graph contains at least one cycle.
308    pub fn has_cycle(&self) -> bool {
309        self.topological_sort().is_err()
310    }
311
312    /// Return the number of registered rules.
313    pub fn rule_count(&self) -> usize {
314        self.rules.len()
315    }
316
317    /// Return the number of dependency edges.
318    pub fn dep_count(&self) -> usize {
319        self.deps.len()
320    }
321}
322
323// ─── EvaluationSchedule ──────────────────────────────────────────────────────
324
325/// A layered evaluation schedule derived from a [`RuleDependencyGraph`].
326///
327/// Layer 0 contains all rules that have no dependencies.  Layer *k* contains
328/// all rules whose dependencies are entirely contained in layers 0 … *k-1*.
329///
330/// Within each layer, rules can in principle be evaluated in parallel because
331/// they are independent of each other.
332#[derive(Debug, Clone)]
333pub struct EvaluationSchedule {
334    /// Rules grouped by evaluation layer.
335    ///
336    /// `layers[0]` holds rules with no dependencies; `layers[k]` holds rules
337    /// whose latest dependency is in layer `k-1`.
338    pub layers: Vec<Vec<String>>,
339}
340
341impl EvaluationSchedule {
342    /// Build an [`EvaluationSchedule`] from a [`RuleDependencyGraph`].
343    ///
344    /// The implementation performs a BFS / Kahn-style traversal and assigns
345    /// each rule to the layer immediately after its deepest dependency.
346    ///
347    /// # Errors
348    ///
349    /// Propagates [`DepError::CycleDetected`] if the graph contains a cycle.
350    pub fn build(graph: &RuleDependencyGraph) -> Result<Self, DepError> {
351        // Build in-degree and adjacency the same way as topological_sort.
352        let mut in_degree: HashMap<String, usize> =
353            graph.rules.iter().map(|r| (r.clone(), 0)).collect();
354
355        // adjacency: to -> list of `from` rules
356        let mut adj: HashMap<String, Vec<String>> = graph
357            .rules
358            .iter()
359            .map(|r| (r.clone(), Vec::new()))
360            .collect();
361
362        for dep in &graph.deps {
363            let from_str = dep.from.0.clone();
364            let to_str = dep.to.0.clone();
365            adj.entry(to_str).or_default().push(from_str.clone());
366            *in_degree.entry(from_str).or_insert(0) += 1;
367        }
368
369        let mut layers: Vec<Vec<String>> = Vec::new();
370        let mut processed = 0usize;
371
372        // Seed the first layer with all zero-in-degree nodes.
373        let mut current_layer: Vec<String> = {
374            let mut v: Vec<String> = in_degree
375                .iter()
376                .filter(|(_, &d)| d == 0)
377                .map(|(r, _)| r.clone())
378                .collect();
379            v.sort();
380            v
381        };
382
383        while !current_layer.is_empty() {
384            processed += current_layer.len();
385            let mut next_layer: Vec<String> = Vec::new();
386
387            for node in &current_layer {
388                if let Some(dependents) = adj.get(node) {
389                    for dep_node in dependents {
390                        let deg = in_degree.get_mut(dep_node).expect("node always present");
391                        *deg -= 1;
392                        if *deg == 0 {
393                            next_layer.push(dep_node.clone());
394                        }
395                    }
396                }
397            }
398
399            layers.push(current_layer);
400            next_layer.sort();
401            next_layer.dedup();
402            current_layer = next_layer;
403        }
404
405        if processed != graph.rules.len() {
406            let mut involved: Vec<String> = in_degree
407                .into_iter()
408                .filter(|(_, d)| *d > 0)
409                .map(|(r, _)| r)
410                .collect();
411            involved.sort();
412            return Err(DepError::CycleDetected { involved });
413        }
414
415        Ok(EvaluationSchedule { layers })
416    }
417
418    /// Return the number of evaluation layers.
419    pub fn layer_count(&self) -> usize {
420        self.layers.len()
421    }
422
423    /// Return the total number of rules across all layers.
424    pub fn total_rules(&self) -> usize {
425        self.layers.iter().map(|l| l.len()).sum()
426    }
427}
428
429// ─── Tests ───────────────────────────────────────────────────────────────────
430
431#[cfg(test)]
432mod tests {
433    use super::*;
434
435    // ── helpers ──────────────────────────────────────────────────────────────
436
437    fn make_linear_chain(n: usize) -> RuleDependencyGraph {
438        let mut g = RuleDependencyGraph::new();
439        for i in 0..n {
440            g.add_rule(&format!("r{i}")).expect("test: should succeed");
441        }
442        // r1 depends on r0, r2 depends on r1, …
443        for i in 1..n {
444            g.add_dependency(
445                &format!("r{i}"),
446                &format!("r{}", i - 1),
447                DependencyType::UsesConclusion,
448            )
449            .expect("test: should succeed");
450        }
451        g
452    }
453
454    // ── 1: add rules ─────────────────────────────────────────────────────────
455
456    #[test]
457    fn test_add_rules_increases_count() {
458        let mut g = RuleDependencyGraph::new();
459        assert_eq!(g.rule_count(), 0);
460        g.add_rule("a").expect("test: should succeed");
461        g.add_rule("b").expect("test: should succeed");
462        assert_eq!(g.rule_count(), 2);
463    }
464
465    // ── 2: duplicate rule error ───────────────────────────────────────────────
466
467    #[test]
468    fn test_duplicate_rule_error() {
469        let mut g = RuleDependencyGraph::new();
470        g.add_rule("x").expect("test: should succeed");
471        let err = g.add_rule("x").unwrap_err();
472        assert!(matches!(err, DepError::DuplicateRule(ref s) if s == "x"));
473    }
474
475    // ── 3: add dependency increases dep_count ────────────────────────────────
476
477    #[test]
478    fn test_add_dependency_increases_count() {
479        let mut g = RuleDependencyGraph::new();
480        g.add_rule("a").expect("test: should succeed");
481        g.add_rule("b").expect("test: should succeed");
482        g.add_dependency("a", "b", DependencyType::SharesBody)
483            .expect("test: should succeed");
484        assert_eq!(g.dep_count(), 1);
485    }
486
487    // ── 4: dependency with missing endpoint error ─────────────────────────────
488
489    #[test]
490    fn test_dependency_missing_endpoint_from() {
491        let mut g = RuleDependencyGraph::new();
492        g.add_rule("b").expect("test: should succeed");
493        let err = g
494            .add_dependency("ghost", "b", DependencyType::Negation)
495            .unwrap_err();
496        assert!(
497            matches!(err, DepError::DependencyEndpointMissing { ref from, .. } if from == "ghost")
498        );
499    }
500
501    #[test]
502    fn test_dependency_missing_endpoint_to() {
503        let mut g = RuleDependencyGraph::new();
504        g.add_rule("a").expect("test: should succeed");
505        let err = g
506            .add_dependency("a", "ghost", DependencyType::Negation)
507            .unwrap_err();
508        assert!(matches!(err, DepError::DependencyEndpointMissing { ref to, .. } if to == "ghost"));
509    }
510
511    // ── 5: topological_sort — linear chain ───────────────────────────────────
512
513    #[test]
514    fn test_topo_sort_linear_chain() {
515        let g = make_linear_chain(4);
516        let order = g.topological_sort().expect("test: should succeed");
517        // r0 must appear before r1, r1 before r2, etc.
518        let pos: HashMap<_, _> = order
519            .iter()
520            .enumerate()
521            .map(|(i, r)| (r.as_str(), i))
522            .collect();
523        for i in 1..4usize {
524            assert!(
525                pos[&format!("r{}", i - 1).as_str()] < pos[&format!("r{i}").as_str()],
526                "r{} must precede r{}",
527                i - 1,
528                i
529            );
530        }
531    }
532
533    // ── 6: topological_sort — diamond ────────────────────────────────────────
534
535    #[test]
536    fn test_topo_sort_diamond() {
537        // a <- b <- d
538        //      ^
539        //      c <- d
540        // d depends on both b and c; b and c depend on a.
541        let mut g = RuleDependencyGraph::new();
542        for r in ["a", "b", "c", "d"] {
543            g.add_rule(r).expect("test: should succeed");
544        }
545        g.add_dependency("b", "a", DependencyType::UsesConclusion)
546            .expect("test: should succeed");
547        g.add_dependency("c", "a", DependencyType::UsesConclusion)
548            .expect("test: should succeed");
549        g.add_dependency("d", "b", DependencyType::UsesConclusion)
550            .expect("test: should succeed");
551        g.add_dependency("d", "c", DependencyType::UsesConclusion)
552            .expect("test: should succeed");
553
554        let order = g.topological_sort().expect("test: should succeed");
555        let pos: HashMap<&str, usize> = order
556            .iter()
557            .enumerate()
558            .map(|(i, r)| (r.as_str(), i))
559            .collect();
560        assert!(pos["a"] < pos["b"]);
561        assert!(pos["a"] < pos["c"]);
562        assert!(pos["b"] < pos["d"]);
563        assert!(pos["c"] < pos["d"]);
564    }
565
566    // ── 7: topological_sort — cycle → error ──────────────────────────────────
567
568    #[test]
569    fn test_topo_sort_cycle_error() {
570        let mut g = RuleDependencyGraph::new();
571        g.add_rule("x").expect("test: should succeed");
572        g.add_rule("y").expect("test: should succeed");
573        g.add_dependency("x", "y", DependencyType::UsesConclusion)
574            .expect("test: should succeed");
575        g.add_dependency("y", "x", DependencyType::UsesConclusion)
576            .expect("test: should succeed");
577
578        let err = g.topological_sort().unwrap_err();
579        assert!(matches!(err, DepError::CycleDetected { .. }));
580    }
581
582    // ── 8: has_cycle — false ─────────────────────────────────────────────────
583
584    #[test]
585    fn test_has_cycle_false() {
586        let g = make_linear_chain(5);
587        assert!(!g.has_cycle());
588    }
589
590    // ── 9: has_cycle — true ──────────────────────────────────────────────────
591
592    #[test]
593    fn test_has_cycle_true() {
594        let mut g = RuleDependencyGraph::new();
595        g.add_rule("a").expect("test: should succeed");
596        g.add_rule("b").expect("test: should succeed");
597        g.add_rule("c").expect("test: should succeed");
598        g.add_dependency("a", "b", DependencyType::Subsumption)
599            .expect("test: should succeed");
600        g.add_dependency("b", "c", DependencyType::Subsumption)
601            .expect("test: should succeed");
602        g.add_dependency("c", "a", DependencyType::Subsumption)
603            .expect("test: should succeed");
604        assert!(g.has_cycle());
605    }
606
607    // ── 10: dependencies_of ──────────────────────────────────────────────────
608
609    #[test]
610    fn test_dependencies_of() {
611        let mut g = RuleDependencyGraph::new();
612        for r in ["a", "b", "c", "d"] {
613            g.add_rule(r).expect("test: should succeed");
614        }
615        g.add_dependency("d", "b", DependencyType::UsesConclusion)
616            .expect("test: should succeed");
617        g.add_dependency("d", "c", DependencyType::UsesConclusion)
618            .expect("test: should succeed");
619        g.add_dependency("b", "a", DependencyType::UsesConclusion)
620            .expect("test: should succeed");
621
622        let mut deps = g.dependencies_of("d");
623        deps.sort();
624        assert_eq!(deps, vec!["b".to_string(), "c".to_string()]);
625
626        let deps_b = g.dependencies_of("b");
627        assert_eq!(deps_b, vec!["a".to_string()]);
628
629        let deps_a = g.dependencies_of("a");
630        assert!(deps_a.is_empty());
631    }
632
633    // ── 11: dependents_of ────────────────────────────────────────────────────
634
635    #[test]
636    fn test_dependents_of() {
637        let mut g = RuleDependencyGraph::new();
638        for r in ["a", "b", "c"] {
639            g.add_rule(r).expect("test: should succeed");
640        }
641        g.add_dependency("b", "a", DependencyType::UsesConclusion)
642            .expect("test: should succeed");
643        g.add_dependency("c", "a", DependencyType::UsesConclusion)
644            .expect("test: should succeed");
645
646        let mut deps = g.dependents_of("a");
647        deps.sort();
648        assert_eq!(deps, vec!["b".to_string(), "c".to_string()]);
649
650        let empty = g.dependents_of("b");
651        assert!(empty.is_empty());
652    }
653
654    // ── 12: EvaluationSchedule — basic layers ────────────────────────────────
655
656    #[test]
657    fn test_evaluation_schedule_build_basic() {
658        let mut g = RuleDependencyGraph::new();
659        for r in ["a", "b", "c"] {
660            g.add_rule(r).expect("test: should succeed");
661        }
662        // b depends on a; c depends on b
663        g.add_dependency("b", "a", DependencyType::UsesConclusion)
664            .expect("test: should succeed");
665        g.add_dependency("c", "b", DependencyType::UsesConclusion)
666            .expect("test: should succeed");
667
668        let sched = EvaluationSchedule::build(&g).expect("test: should succeed");
669        assert_eq!(sched.layer_count(), 3);
670        assert_eq!(sched.total_rules(), 3);
671        assert_eq!(sched.layers[0], vec!["a".to_string()]);
672        assert_eq!(sched.layers[1], vec!["b".to_string()]);
673        assert_eq!(sched.layers[2], vec!["c".to_string()]);
674    }
675
676    // ── 13: Layer 0 contains independent rules ───────────────────────────────
677
678    #[test]
679    fn test_layer_zero_contains_independent_rules() {
680        let mut g = RuleDependencyGraph::new();
681        // i0, i1, i2 are independent; d depends on i0.
682        for r in ["i0", "i1", "i2", "d"] {
683            g.add_rule(r).expect("test: should succeed");
684        }
685        g.add_dependency("d", "i0", DependencyType::UsesConclusion)
686            .expect("test: should succeed");
687
688        let sched = EvaluationSchedule::build(&g).expect("test: should succeed");
689        // layer 0 must include i1, i2 and i0 (all have in-degree 0).
690        let mut layer0 = sched.layers[0].clone();
691        layer0.sort();
692        assert!(layer0.contains(&"i0".to_string()));
693        assert!(layer0.contains(&"i1".to_string()));
694        assert!(layer0.contains(&"i2".to_string()));
695        assert!(!layer0.contains(&"d".to_string()));
696    }
697
698    // ── 14: Rules in later layers have all deps in earlier layers ────────────
699
700    #[test]
701    fn test_later_layers_deps_in_earlier_layers() {
702        let g = make_linear_chain(6);
703        let sched = EvaluationSchedule::build(&g).expect("test: should succeed");
704
705        // Build a map: rule → layer index.
706        let mut layer_of: HashMap<String, usize> = HashMap::new();
707        for (idx, layer) in sched.layers.iter().enumerate() {
708            for r in layer {
709                layer_of.insert(r.clone(), idx);
710            }
711        }
712
713        for dep in &g.deps {
714            let from_layer = layer_of[&dep.from.0];
715            let to_layer = layer_of[&dep.to.0];
716            assert!(
717                to_layer < from_layer,
718                "dep.to ({}) must be in an earlier layer than dep.from ({})",
719                dep.to,
720                dep.from
721            );
722        }
723    }
724
725    // ── 15: EvaluationSchedule — diamond layers ───────────────────────────────
726
727    #[test]
728    fn test_schedule_diamond_layers() {
729        let mut g = RuleDependencyGraph::new();
730        for r in ["a", "b", "c", "d"] {
731            g.add_rule(r).expect("test: should succeed");
732        }
733        g.add_dependency("b", "a", DependencyType::UsesConclusion)
734            .expect("test: should succeed");
735        g.add_dependency("c", "a", DependencyType::UsesConclusion)
736            .expect("test: should succeed");
737        g.add_dependency("d", "b", DependencyType::UsesConclusion)
738            .expect("test: should succeed");
739        g.add_dependency("d", "c", DependencyType::UsesConclusion)
740            .expect("test: should succeed");
741
742        let sched = EvaluationSchedule::build(&g).expect("test: should succeed");
743        assert_eq!(sched.total_rules(), 4);
744        // Layer 0: a, Layer 1: b, c, Layer 2: d
745        assert_eq!(sched.layers[0], vec!["a".to_string()]);
746        let mut l1 = sched.layers[1].clone();
747        l1.sort();
748        assert_eq!(l1, vec!["b".to_string(), "c".to_string()]);
749        assert_eq!(sched.layers[2], vec!["d".to_string()]);
750    }
751
752    // ── 16: EvaluationSchedule — cycle → error ───────────────────────────────
753
754    #[test]
755    fn test_schedule_cycle_error() {
756        let mut g = RuleDependencyGraph::new();
757        g.add_rule("p").expect("test: should succeed");
758        g.add_rule("q").expect("test: should succeed");
759        g.add_dependency("p", "q", DependencyType::Negation)
760            .expect("test: should succeed");
761        g.add_dependency("q", "p", DependencyType::Negation)
762            .expect("test: should succeed");
763
764        let err = EvaluationSchedule::build(&g).unwrap_err();
765        assert!(matches!(err, DepError::CycleDetected { .. }));
766    }
767
768    // ── 17: RuleId conversions ────────────────────────────────────────────────
769
770    #[test]
771    fn test_rule_id_conversions() {
772        let from_str: RuleId = RuleId::from("hello");
773        let from_string: RuleId = RuleId::from("hello".to_string());
774        assert_eq!(from_str, from_string);
775        assert_eq!(from_str.to_string(), "hello");
776    }
777
778    // ── 18: rule_count / dep_count ───────────────────────────────────────────
779
780    #[test]
781    fn test_rule_count_and_dep_count() {
782        let g = make_linear_chain(5);
783        assert_eq!(g.rule_count(), 5);
784        assert_eq!(g.dep_count(), 4); // 4 edges for 5 nodes in a chain
785    }
786}
ipfrs_tensorlogic/rule_dependency.rs

ipfrs_tensorlogic/
rule_dependency.rs
