Skip to main content

vibe/
dag.rs

1//! A6 — Multi-Agent DAGs & Autonomous Control Units.
2//!
3//! Native DAG (Directed Acyclic Graph) pipeline definitions for multi-agent
4//! orchestration. Each node represents an agent step; edges represent
5//! dependencies. Control Units (autonomous routers) can select the next
6//! node based on blackboard state and policy constraints.
7//!
8//! ## Design
9//!
10//! - **DagNode**: A single agent step with inputs, outputs, effect class,
11//!   and an optional capability requirement.
12//! - **DagEdge**: A dependency edge (producer → consumer).
13//! - **DagPipeline**: The full DAG with topological ordering and cycle
14//!   detection.
15//! - **ControlUnit**: An autonomous router that selects the next node(s)
16//!   to execute based on the current state and policy constraints.
17//! - **JudgeFrame**: An isolated verification frame for checking agent
18//!   outputs before committing them.
19//!
20//! ## Integration
21//!
22//! - Uses A4 (`ast_query`) for policy enforcement on node definitions.
23//! - Uses A5 (`blackboard`) for inter-agent state channels.
24//! - Verification frames use bounded arrays (zero-heap on hot paths).
25
26// ── DAG Node ───────────────────────────────────────────────────────────────
27
28/// Maximum nodes per DAG.
29pub const MAX_DAG_NODES: usize = 256;
30/// Maximum edges per DAG.
31pub const MAX_DAG_EDGES: usize = 1024;
32/// Maximum inputs/outputs per node.
33pub const MAX_NODE_IO: usize = 16;
34
35/// Effect class for a DAG node (mirrors `ast::EffectClass`).
36#[derive(Debug, Clone, Copy, PartialEq, Eq)]
37pub enum NodeEffect {
38    Pure,
39    Hot,
40    Cold,
41    Async,
42    External,
43}
44
45/// A single agent step in the DAG.
46#[derive(Debug, Clone)]
47pub struct DagNode {
48    /// Unique node ID (0..MAX_DAG_NODES).
49    pub id: u32,
50    /// Human-readable name.
51    pub name: String,
52    /// Effect class.
53    pub effect: NodeEffect,
54    /// Required capability IDs.
55    pub capabilities: Vec<String>,
56    /// Input channel names (from blackboard or upstream nodes).
57    pub inputs: Vec<String>,
58    /// Output channel names (to blackboard or downstream nodes).
59    pub outputs: Vec<String>,
60    /// Budget (max tokens / max steps).
61    pub budget: u32,
62    /// Whether this node is a Control Unit (autonomous router).
63    pub is_control_unit: bool,
64}
65
66impl DagNode {
67    /// Creates a new `DagNode`.
68    pub fn new(id: u32, name: &str, effect: NodeEffect) -> Self {
69        Self {
70            id,
71            name: name.to_string(),
72            effect,
73            capabilities: Vec::new(),
74            inputs: Vec::new(),
75            outputs: Vec::new(),
76            budget: 0,
77            is_control_unit: false,
78        }
79    }
80
81    /// Builder — sets capability.
82    pub fn with_capability(mut self, cap: &str) -> Self {
83        self.capabilities.push(cap.to_string());
84        self
85    }
86
87    /// Builder — sets input.
88    pub fn with_input(mut self, channel: &str) -> Self {
89        self.inputs.push(channel.to_string());
90        self
91    }
92
93    /// Builder — sets output.
94    pub fn with_output(mut self, channel: &str) -> Self {
95        self.outputs.push(channel.to_string());
96        self
97    }
98
99    /// Builder — sets budget.
100    pub fn with_budget(mut self, budget: u32) -> Self {
101        self.budget = budget;
102        self
103    }
104
105    /// `control-unit` form.
106    pub fn as_control_unit(mut self) -> Self {
107        self.is_control_unit = true;
108        self
109    }
110}
111
112// ── DAG Edge ───────────────────────────────────────────────────────────────
113
114/// A dependency edge: `from` must complete before `to` starts.
115#[derive(Debug, Clone, Copy, PartialEq, Eq)]
116pub struct DagEdge {
117    pub from: u32,
118    pub to: u32,
119}
120
121impl DagEdge {
122    /// Creates a new `DagEdge`.
123    pub fn new(from: u32, to: u32) -> Self {
124        Self { from, to }
125    }
126}
127
128// ── DAG Pipeline ───────────────────────────────────────────────────────────
129
130/// Errors that can occur during DAG construction or execution.
131#[derive(Debug, Clone, PartialEq, Eq)]
132pub enum DagError {
133    /// Node ID exceeds MAX_DAG_NODES.
134    NodeIdOverflow,
135    /// Too many edges.
136    EdgeOverflow,
137    /// Duplicate node ID.
138    DuplicateNode,
139    /// Edge references non-existent node.
140    InvalidEdge,
141    /// Cycle detected.
142    CycleDetected,
143    /// Node has no budget set.
144    MissingBudget,
145    /// Required capability not available.
146    MissingCapability(String),
147}
148
149/// Execution status of a DAG node.
150#[derive(Debug, Clone, Copy, PartialEq, Eq)]
151pub enum NodeStatus {
152    Pending,
153    Running,
154    Completed,
155    Failed,
156    Skipped,
157}
158
159/// The DAG pipeline definition.
160pub struct DagPipeline {
161    slots: [Option<usize>; MAX_DAG_NODES],
162    nodes: Vec<DagNode>,
163    edges: Vec<DagEdge>,
164    /// Adjacency list indexed by node slot: slot → list of downstream node_ids.
165    adjacency: Vec<Vec<u32>>,
166    /// Reverse adjacency indexed by node slot: slot → list of upstream node_ids.
167    reverse_adjacency: Vec<Vec<u32>>,
168}
169
170impl DagPipeline {
171    /// Creates a new `DagPipeline`.
172    pub fn new() -> Self {
173        Self {
174            slots: [None; MAX_DAG_NODES],
175            nodes: Vec::new(),
176            edges: Vec::new(),
177            adjacency: Vec::new(),
178            reverse_adjacency: Vec::new(),
179        }
180    }
181
182    fn slot_of(&self, id: u32) -> Option<usize> {
183        usize::try_from(id)
184            .ok()
185            .and_then(|idx| self.slots.get(idx).copied().flatten())
186    }
187
188    /// Add a node to the DAG.
189    pub fn add_node(&mut self, node: DagNode) -> Result<(), DagError> {
190        let id_idx = node.id as usize;
191        if id_idx >= MAX_DAG_NODES {
192            return Err(DagError::NodeIdOverflow);
193        }
194        if self.slots[id_idx].is_some() {
195            return Err(DagError::DuplicateNode);
196        }
197        let slot = self.nodes.len();
198        self.slots[id_idx] = Some(slot);
199        self.nodes.push(node);
200        self.adjacency.push(Vec::new());
201        self.reverse_adjacency.push(Vec::new());
202        Ok(())
203    }
204
205    /// Add an edge to the DAG.
206    pub fn add_edge(&mut self, edge: DagEdge) -> Result<(), DagError> {
207        if self.edges.len() >= MAX_DAG_EDGES {
208            return Err(DagError::EdgeOverflow);
209        }
210        let Some(from_slot) = self.slot_of(edge.from) else {
211            return Err(DagError::InvalidEdge);
212        };
213        let Some(to_slot) = self.slot_of(edge.to) else {
214            return Err(DagError::InvalidEdge);
215        };
216        self.edges.push(edge.clone());
217        self.adjacency[from_slot].push(edge.to);
218        self.reverse_adjacency[to_slot].push(edge.from);
219        Ok(())
220    }
221
222    /// Get a node by ID.
223    pub fn get_node(&self, id: u32) -> Option<&DagNode> {
224        self.slot_of(id).and_then(|slot| self.nodes.get(slot))
225    }
226
227    /// Get all nodes.
228    pub fn nodes(&self) -> &[DagNode] {
229        &self.nodes
230    }
231
232    /// Iterate present node IDs in deterministic ascending ID order.
233    pub fn node_ids(&self) -> impl Iterator<Item = u32> + '_ {
234        self.slots
235            .iter()
236            .enumerate()
237            .filter_map(|(id, slot)| slot.map(|_| id as u32))
238    }
239
240    /// Get all edges.
241    pub fn edges(&self) -> &[DagEdge] {
242        &self.edges
243    }
244
245    /// Get the downstream nodes of a given node.
246    pub fn downstream(&self, id: u32) -> &[u32] {
247        self.slot_of(id)
248            .and_then(|slot| self.adjacency.get(slot))
249            .map(|v| v.as_slice())
250            .unwrap_or(&[])
251    }
252
253    /// Get the upstream nodes of a given node.
254    pub fn upstream(&self, id: u32) -> &[u32] {
255        self.slot_of(id)
256            .and_then(|slot| self.reverse_adjacency.get(slot))
257            .map(|v| v.as_slice())
258            .unwrap_or(&[])
259    }
260
261    /// Detect cycles using DFS. Returns true if a cycle is found.
262    pub fn has_cycle(&self) -> bool {
263        // 0=unvisited, 1=in-progress, 2=done; zero-heap stack buffer.
264        let mut visited = [0u8; MAX_DAG_NODES];
265        for id in self.node_ids() {
266            if visited[id as usize] == 0 && self.dfs_cycle(id, &mut visited) {
267                return true;
268            }
269        }
270        false
271    }
272
273    fn dfs_cycle(&self, id: u32, visited: &mut [u8; MAX_DAG_NODES]) -> bool {
274        visited[id as usize] = 1;
275        for &next in self.downstream(id) {
276            let state = visited[next as usize];
277            if state == 1 {
278                return true; // Back edge → cycle.
279            }
280            if state == 0 && self.dfs_cycle(next, visited) {
281                return true;
282            }
283        }
284        visited[id as usize] = 2;
285        false
286    }
287
288    /// Topological sort. Returns node IDs in dependency order.
289    /// Returns Err if a cycle is detected.
290    pub fn topological_sort(&self) -> Result<Vec<u32>, DagError> {
291        if self.has_cycle() {
292            return Err(DagError::CycleDetected);
293        }
294        let mut in_degree = [0usize; MAX_DAG_NODES];
295        let mut queue = [0u32; MAX_DAG_NODES];
296        let mut q_len = 0usize;
297        for id in self.node_ids() {
298            let deg = self.upstream(id).len();
299            in_degree[id as usize] = deg;
300            if deg == 0 {
301                queue[q_len] = id;
302                q_len += 1;
303            }
304        }
305        queue[..q_len].sort_unstable();
306        let mut result = Vec::with_capacity(self.nodes.len());
307        while q_len > 0 {
308            q_len -= 1;
309            let id = queue[q_len];
310            result.push(id);
311            for &next in self.downstream(id) {
312                let d = &mut in_degree[next as usize];
313                *d -= 1;
314                if *d == 0 {
315                    queue[q_len] = next;
316                    q_len += 1;
317                    queue[..q_len].sort_unstable();
318                }
319            }
320        }
321        Ok(result)
322    }
323
324    /// Get the entry nodes (nodes with no upstream dependencies).
325    pub fn entry_nodes(&self) -> Vec<u32> {
326        self.node_ids()
327            .filter(|&id| self.upstream(id).is_empty())
328            .collect()
329    }
330
331    /// Get the exit nodes (nodes with no downstream dependencies).
332    pub fn exit_nodes(&self) -> Vec<u32> {
333        self.node_ids()
334            .filter(|&id| self.downstream(id).is_empty())
335            .collect()
336    }
337
338    /// Validate the DAG: check for cycles, missing budgets on hot nodes,
339    /// and missing capabilities.
340    pub fn validate(&self, available_caps: &[String]) -> Result<(), DagError> {
341        if self.has_cycle() {
342            return Err(DagError::CycleDetected);
343        }
344        for node in &self.nodes {
345            // Hot and Async nodes must have a budget.
346            if (node.effect == NodeEffect::Hot || node.effect == NodeEffect::Async)
347                && node.budget == 0
348            {
349                return Err(DagError::MissingBudget);
350            }
351            // Check capabilities.
352            for cap in &node.capabilities {
353                if !available_caps.contains(cap) {
354                    return Err(DagError::MissingCapability(cap.clone()));
355                }
356            }
357        }
358        Ok(())
359    }
360
361    /// Number of nodes.
362    pub fn node_count(&self) -> usize {
363        self.nodes.len()
364    }
365
366    /// Number of edges.
367    pub fn edge_count(&self) -> usize {
368        self.edges.len()
369    }
370}
371
372impl Default for DagPipeline {
373    fn default() -> Self {
374        Self::new()
375    }
376}
377
378// ── Control Unit (Autonomous Router) ───────────────────────────────────────
379
380/// A Control Unit selects the next node(s) to execute based on the current
381/// execution state and policy constraints.
382pub struct ControlUnit {
383    /// The node ID this control unit is attached to.
384    pub node_id: u32,
385    /// Strategy for selecting the next node.
386    pub strategy: RouterStrategy,
387}
388
389/// Routing strategy for the control unit.
390#[derive(Debug, Clone, PartialEq)]
391pub enum RouterStrategy {
392    /// Execute all downstream nodes in parallel.
393    AllDownstream,
394    /// Execute only the first downstream node (sequential).
395    FirstDownstream,
396    /// Execute the downstream node whose name matches.
397    Named(String),
398    /// Conditionally route based on a channel value.
399    Conditional {
400        channel: String,
401        /// If the channel has any data, route to `if_present`.
402        if_present: u32,
403        /// Otherwise, route to `if_empty`.
404        if_empty: u32,
405    },
406}
407
408impl ControlUnit {
409    /// Creates a new `ControlUnit`.
410    pub fn new(node_id: u32, strategy: RouterStrategy) -> Self {
411        Self { node_id, strategy }
412    }
413
414    /// Select the next node(s) to execute given the current pipeline state
415    /// and channel data.
416    pub fn select_next(
417        &self,
418        pipeline: &DagPipeline,
419        channel_has_data: &dyn Fn(&str) -> bool,
420    ) -> Vec<u32> {
421        match &self.strategy {
422            RouterStrategy::AllDownstream => pipeline.downstream(self.node_id).to_vec(),
423            RouterStrategy::FirstDownstream => pipeline
424                .downstream(self.node_id)
425                .first()
426                .copied()
427                .into_iter()
428                .collect(),
429            RouterStrategy::Named(name) => pipeline
430                .downstream(self.node_id)
431                .iter()
432                .filter(|&&id| {
433                    pipeline
434                        .get_node(id)
435                        .map(|n| n.name == *name)
436                        .unwrap_or(false)
437                })
438                .copied()
439                .collect(),
440            RouterStrategy::Conditional {
441                channel,
442                if_present,
443                if_empty,
444            } => {
445                if channel_has_data(channel) {
446                    vec![*if_present]
447                } else {
448                    vec![*if_empty]
449                }
450            }
451        }
452    }
453}
454
455// ── Execution State ────────────────────────────────────────────────────────
456
457/// Tracks the execution state of all nodes in the DAG using zero-heap inline storage.
458pub struct ExecutionState {
459    statuses: [Option<NodeStatus>; MAX_DAG_NODES],
460    /// Completed node IDs in order.
461    completed_order: [u32; MAX_DAG_NODES],
462    completed_len: usize,
463}
464
465impl ExecutionState {
466    /// Creates a new `ExecutionState`.
467    pub fn new(pipeline: &DagPipeline) -> Self {
468        let mut statuses = [None; MAX_DAG_NODES];
469        for id in pipeline.node_ids() {
470            statuses[id as usize] = Some(NodeStatus::Pending);
471        }
472        Self {
473            statuses,
474            completed_order: [0; MAX_DAG_NODES],
475            completed_len: 0,
476        }
477    }
478
479    /// Get the status of a node.
480    pub fn status(&self, id: u32) -> NodeStatus {
481        usize::try_from(id)
482            .ok()
483            .and_then(|idx| self.statuses.get(idx).copied().flatten())
484            .unwrap_or(NodeStatus::Pending)
485    }
486
487    /// Set the status of a node.
488    pub fn set_status(&mut self, id: u32, status: NodeStatus) {
489        if status == NodeStatus::Completed && self.completed_len < MAX_DAG_NODES {
490            self.completed_order[self.completed_len] = id;
491            self.completed_len += 1;
492        }
493        if let Ok(idx) = usize::try_from(id) {
494            if let Some(slot) = self.statuses.get_mut(idx) {
495                *slot = Some(status);
496            }
497        }
498    }
499
500    /// Get all nodes that are ready to execute (all upstream completed).
501    pub fn ready_nodes(&self, pipeline: &DagPipeline) -> Vec<u32> {
502        pipeline
503            .node_ids()
504            .filter(|&id| {
505                self.status(id) == NodeStatus::Pending
506                    && pipeline
507                        .upstream(id)
508                        .iter()
509                        .all(|&up| self.status(up) == NodeStatus::Completed)
510            })
511            .collect()
512    }
513
514    /// Are all nodes completed?
515    pub fn all_completed(&self) -> bool {
516        self.statuses
517            .iter()
518            .flatten()
519            .all(|&s| s == NodeStatus::Completed)
520    }
521
522    /// Get the completion order.
523    pub fn completed_order(&self) -> &[u32] {
524        &self.completed_order[..self.completed_len]
525    }
526
527    /// Count nodes by status.
528    pub fn count_by_status(&self, status: NodeStatus) -> usize {
529        self.statuses
530            .iter()
531            .flatten()
532            .filter(|&&s| s == status)
533            .count()
534    }
535}
536
537// ── Judge Frame (Isolated Verification) ────────────────────────────────────
538
539/// Maximum claims per judge frame.
540pub const MAX_JUDGE_CLAIMS: usize = 64;
541
542/// A claim submitted to the judge frame for verification.
543#[derive(Debug, Clone, PartialEq)]
544pub struct JudgeClaim {
545    /// The node that produced this claim.
546    pub node_id: u32,
547    /// The output channel name.
548    pub channel: String,
549    /// Whether the node claims success.
550    pub success: bool,
551    /// Optional error message.
552    pub error: Option<String>,
553}
554
555/// A judge frame verifies agent outputs before committing them.
556/// Uses a bounded array (zero-heap on hot paths).
557pub struct JudgeFrame {
558    claims: Vec<JudgeClaim>,
559    verdicts: Vec<bool>,
560}
561
562impl JudgeFrame {
563    /// Creates a new `JudgeFrame`.
564    pub fn new() -> Self {
565        Self {
566            claims: Vec::with_capacity(MAX_JUDGE_CLAIMS),
567            verdicts: Vec::with_capacity(MAX_JUDGE_CLAIMS),
568        }
569    }
570
571    /// Submit a claim for verification.
572    pub fn submit(&mut self, claim: JudgeClaim) -> Result<(), DagError> {
573        if self.claims.len() >= MAX_JUDGE_CLAIMS {
574            return Err(DagError::EdgeOverflow); // Reuse for capacity.
575        }
576        self.claims.push(claim);
577        Ok(())
578    }
579
580    /// Evaluate all submitted claims. A claim passes if:
581    /// - The node claims success and has no error, OR
582    /// - The node claims failure with an error message (honest failure).
583    /// A claim fails if:
584    /// - The node claims success but has an error, OR
585    /// - The node claims failure but has no error message.
586    pub fn evaluate(&mut self) {
587        self.verdicts.clear();
588        for claim in &self.claims {
589            let passes = if claim.success {
590                claim.error.is_none()
591            } else {
592                claim.error.is_some()
593            };
594            self.verdicts.push(passes);
595        }
596    }
597
598    /// Get the verdicts.
599    pub fn verdicts(&self) -> &[bool] {
600        &self.verdicts
601    }
602
603    /// Did all claims pass?
604    pub fn all_passed(&self) -> bool {
605        !self.verdicts.is_empty() && self.verdicts.iter().all(|&v| v)
606    }
607
608    /// Get the number of submitted claims.
609    pub fn claim_count(&self) -> usize {
610        self.claims.len()
611    }
612
613    /// Reset the judge frame for reuse.
614    pub fn reset(&mut self) {
615        self.claims.clear();
616        self.verdicts.clear();
617    }
618}
619
620impl Default for JudgeFrame {
621    fn default() -> Self {
622        Self::new()
623    }
624}
625
626// ── Tests ──────────────────────────────────────────────────────────────────
627
628#[cfg(test)]
629mod tests {
630    use super::*;
631
632    #[test]
633    fn dag_node_construction() {
634        let node = DagNode::new(0, "input", NodeEffect::Pure)
635            .with_capability("math")
636            .with_input("raw")
637            .with_output("processed")
638            .with_budget(100);
639        assert_eq!(node.id, 0);
640        assert_eq!(node.name, "input");
641        assert_eq!(node.effect, NodeEffect::Pure);
642        assert_eq!(node.capabilities, vec!["math"]);
643        assert_eq!(node.inputs, vec!["raw"]);
644        assert_eq!(node.outputs, vec!["processed"]);
645        assert_eq!(node.budget, 100);
646    }
647
648    #[test]
649    fn dag_pipeline_add_nodes_and_edges() {
650        let mut dag = DagPipeline::new();
651        dag.add_node(DagNode::new(0, "a", NodeEffect::Pure))
652            .unwrap();
653        dag.add_node(DagNode::new(1, "b", NodeEffect::Pure))
654            .unwrap();
655        dag.add_node(DagNode::new(2, "c", NodeEffect::Pure))
656            .unwrap();
657        dag.add_edge(DagEdge::new(0, 1)).unwrap();
658        dag.add_edge(DagEdge::new(1, 2)).unwrap();
659        assert_eq!(dag.node_count(), 3);
660        assert_eq!(dag.edge_count(), 2);
661    }
662
663    #[test]
664    fn dag_pipeline_duplicate_node() {
665        let mut dag = DagPipeline::new();
666        dag.add_node(DagNode::new(0, "a", NodeEffect::Pure))
667            .unwrap();
668        let result = dag.add_node(DagNode::new(0, "b", NodeEffect::Pure));
669        assert_eq!(result, Err(DagError::DuplicateNode));
670    }
671
672    #[test]
673    fn dag_pipeline_invalid_edge() {
674        let mut dag = DagPipeline::new();
675        dag.add_node(DagNode::new(0, "a", NodeEffect::Pure))
676            .unwrap();
677        let result = dag.add_edge(DagEdge::new(0, 99));
678        assert_eq!(result, Err(DagError::InvalidEdge));
679    }
680
681    #[test]
682    fn dag_pipeline_no_cycle() {
683        let mut dag = DagPipeline::new();
684        dag.add_node(DagNode::new(0, "a", NodeEffect::Pure))
685            .unwrap();
686        dag.add_node(DagNode::new(1, "b", NodeEffect::Pure))
687            .unwrap();
688        dag.add_node(DagNode::new(2, "c", NodeEffect::Pure))
689            .unwrap();
690        dag.add_edge(DagEdge::new(0, 1)).unwrap();
691        dag.add_edge(DagEdge::new(1, 2)).unwrap();
692        assert!(!dag.has_cycle());
693    }
694
695    #[test]
696    fn dag_pipeline_cycle_detected() {
697        let mut dag = DagPipeline::new();
698        dag.add_node(DagNode::new(0, "a", NodeEffect::Pure))
699            .unwrap();
700        dag.add_node(DagNode::new(1, "b", NodeEffect::Pure))
701            .unwrap();
702        dag.add_edge(DagEdge::new(0, 1)).unwrap();
703        dag.add_edge(DagEdge::new(1, 0)).unwrap();
704        assert!(dag.has_cycle());
705    }
706
707    #[test]
708    fn dag_topological_sort() {
709        let mut dag = DagPipeline::new();
710        dag.add_node(DagNode::new(0, "a", NodeEffect::Pure))
711            .unwrap();
712        dag.add_node(DagNode::new(1, "b", NodeEffect::Pure))
713            .unwrap();
714        dag.add_node(DagNode::new(2, "c", NodeEffect::Pure))
715            .unwrap();
716        dag.add_edge(DagEdge::new(0, 1)).unwrap();
717        dag.add_edge(DagEdge::new(1, 2)).unwrap();
718        let sorted = dag.topological_sort().unwrap();
719        assert_eq!(sorted, vec![0, 1, 2]);
720    }
721
722    #[test]
723    fn dag_topological_sort_cycle_fails() {
724        let mut dag = DagPipeline::new();
725        dag.add_node(DagNode::new(0, "a", NodeEffect::Pure))
726            .unwrap();
727        dag.add_node(DagNode::new(1, "b", NodeEffect::Pure))
728            .unwrap();
729        dag.add_edge(DagEdge::new(0, 1)).unwrap();
730        dag.add_edge(DagEdge::new(1, 0)).unwrap();
731        assert_eq!(dag.topological_sort(), Err(DagError::CycleDetected));
732    }
733
734    #[test]
735    fn dag_entry_and_exit_nodes() {
736        let mut dag = DagPipeline::new();
737        dag.add_node(DagNode::new(0, "a", NodeEffect::Pure))
738            .unwrap();
739        dag.add_node(DagNode::new(1, "b", NodeEffect::Pure))
740            .unwrap();
741        dag.add_node(DagNode::new(2, "c", NodeEffect::Pure))
742            .unwrap();
743        dag.add_edge(DagEdge::new(0, 1)).unwrap();
744        dag.add_edge(DagEdge::new(1, 2)).unwrap();
745        let entries = dag.entry_nodes();
746        let exits = dag.exit_nodes();
747        assert!(entries.contains(&0));
748        assert!(exits.contains(&2));
749    }
750
751    #[test]
752    fn dag_validate_missing_budget() {
753        let mut dag = DagPipeline::new();
754        dag.add_node(DagNode::new(0, "a", NodeEffect::Hot)).unwrap();
755        let result = dag.validate(&[]);
756        assert_eq!(result, Err(DagError::MissingBudget));
757    }
758
759    #[test]
760    fn dag_validate_missing_capability() {
761        let mut dag = DagPipeline::new();
762        dag.add_node(DagNode::new(0, "a", NodeEffect::Pure).with_capability("missing"))
763            .unwrap();
764        let result = dag.validate(&[]);
765        assert_eq!(
766            result,
767            Err(DagError::MissingCapability("missing".to_string()))
768        );
769    }
770
771    #[test]
772    fn dag_validate_passes() {
773        let mut dag = DagPipeline::new();
774        dag.add_node(
775            DagNode::new(0, "a", NodeEffect::Hot)
776                .with_capability("math")
777                .with_budget(100),
778        )
779        .unwrap();
780        let result = dag.validate(&["math".to_string()]);
781        assert!(result.is_ok());
782    }
783
784    #[test]
785    fn control_unit_all_downstream() {
786        let mut dag = DagPipeline::new();
787        dag.add_node(DagNode::new(0, "router", NodeEffect::Pure))
788            .unwrap();
789        dag.add_node(DagNode::new(1, "a", NodeEffect::Pure))
790            .unwrap();
791        dag.add_node(DagNode::new(2, "b", NodeEffect::Pure))
792            .unwrap();
793        dag.add_edge(DagEdge::new(0, 1)).unwrap();
794        dag.add_edge(DagEdge::new(0, 2)).unwrap();
795        let cu = ControlUnit::new(0, RouterStrategy::AllDownstream);
796        let next = cu.select_next(&dag, &|_| false);
797        assert!(next.contains(&1));
798        assert!(next.contains(&2));
799    }
800
801    #[test]
802    fn control_unit_first_downstream() {
803        let mut dag = DagPipeline::new();
804        dag.add_node(DagNode::new(0, "router", NodeEffect::Pure))
805            .unwrap();
806        dag.add_node(DagNode::new(1, "a", NodeEffect::Pure))
807            .unwrap();
808        dag.add_node(DagNode::new(2, "b", NodeEffect::Pure))
809            .unwrap();
810        dag.add_edge(DagEdge::new(0, 1)).unwrap();
811        dag.add_edge(DagEdge::new(0, 2)).unwrap();
812        let cu = ControlUnit::new(0, RouterStrategy::FirstDownstream);
813        let next = cu.select_next(&dag, &|_| false);
814        assert_eq!(next.len(), 1);
815    }
816
817    #[test]
818    fn control_unit_named() {
819        let mut dag = DagPipeline::new();
820        dag.add_node(DagNode::new(0, "router", NodeEffect::Pure))
821            .unwrap();
822        dag.add_node(DagNode::new(1, "alpha", NodeEffect::Pure))
823            .unwrap();
824        dag.add_node(DagNode::new(2, "beta", NodeEffect::Pure))
825            .unwrap();
826        dag.add_edge(DagEdge::new(0, 1)).unwrap();
827        dag.add_edge(DagEdge::new(0, 2)).unwrap();
828        let cu = ControlUnit::new(0, RouterStrategy::Named("beta".to_string()));
829        let next = cu.select_next(&dag, &|_| false);
830        assert_eq!(next, vec![2]);
831    }
832
833    #[test]
834    fn control_unit_conditional_if_present() {
835        let mut dag = DagPipeline::new();
836        dag.add_node(DagNode::new(0, "router", NodeEffect::Pure))
837            .unwrap();
838        dag.add_node(DagNode::new(1, "yes", NodeEffect::Pure))
839            .unwrap();
840        dag.add_node(DagNode::new(2, "no", NodeEffect::Pure))
841            .unwrap();
842        let cu = ControlUnit::new(
843            0,
844            RouterStrategy::Conditional {
845                channel: "check".to_string(),
846                if_present: 1,
847                if_empty: 2,
848            },
849        );
850        let next = cu.select_next(&dag, &|ch| ch == "check");
851        assert_eq!(next, vec![1]);
852    }
853
854    #[test]
855    fn control_unit_conditional_if_empty() {
856        let mut dag = DagPipeline::new();
857        dag.add_node(DagNode::new(0, "router", NodeEffect::Pure))
858            .unwrap();
859        dag.add_node(DagNode::new(1, "yes", NodeEffect::Pure))
860            .unwrap();
861        dag.add_node(DagNode::new(2, "no", NodeEffect::Pure))
862            .unwrap();
863        let cu = ControlUnit::new(
864            0,
865            RouterStrategy::Conditional {
866                channel: "check".to_string(),
867                if_present: 1,
868                if_empty: 2,
869            },
870        );
871        let next = cu.select_next(&dag, &|_| false);
872        assert_eq!(next, vec![2]);
873    }
874
875    #[test]
876    fn execution_state_ready_nodes() {
877        let mut dag = DagPipeline::new();
878        dag.add_node(DagNode::new(0, "a", NodeEffect::Pure))
879            .unwrap();
880        dag.add_node(DagNode::new(1, "b", NodeEffect::Pure))
881            .unwrap();
882        dag.add_edge(DagEdge::new(0, 1)).unwrap();
883        let mut state = ExecutionState::new(&dag);
884        // Initially, only node 0 is ready (no upstream).
885        let ready = state.ready_nodes(&dag);
886        assert!(ready.contains(&0));
887        assert!(!ready.contains(&1));
888        // Complete node 0.
889        state.set_status(0, NodeStatus::Completed);
890        let ready = state.ready_nodes(&dag);
891        assert!(ready.contains(&1));
892    }
893
894    #[test]
895    fn execution_state_all_completed() {
896        let mut dag = DagPipeline::new();
897        dag.add_node(DagNode::new(0, "a", NodeEffect::Pure))
898            .unwrap();
899        dag.add_node(DagNode::new(1, "b", NodeEffect::Pure))
900            .unwrap();
901        dag.add_edge(DagEdge::new(0, 1)).unwrap();
902        let mut state = ExecutionState::new(&dag);
903        assert!(!state.all_completed());
904        state.set_status(0, NodeStatus::Completed);
905        assert!(!state.all_completed());
906        state.set_status(1, NodeStatus::Completed);
907        assert!(state.all_completed());
908    }
909
910    #[test]
911    fn execution_state_completed_order() {
912        let mut dag = DagPipeline::new();
913        dag.add_node(DagNode::new(0, "a", NodeEffect::Pure))
914            .unwrap();
915        dag.add_node(DagNode::new(1, "b", NodeEffect::Pure))
916            .unwrap();
917        let mut state = ExecutionState::new(&dag);
918        state.set_status(1, NodeStatus::Completed);
919        state.set_status(0, NodeStatus::Completed);
920        assert_eq!(state.completed_order(), &[1, 0]);
921    }
922
923    #[test]
924    fn execution_state_count_by_status() {
925        let mut dag = DagPipeline::new();
926        dag.add_node(DagNode::new(0, "a", NodeEffect::Pure))
927            .unwrap();
928        dag.add_node(DagNode::new(1, "b", NodeEffect::Pure))
929            .unwrap();
930        dag.add_node(DagNode::new(2, "c", NodeEffect::Pure))
931            .unwrap();
932        let mut state = ExecutionState::new(&dag);
933        state.set_status(0, NodeStatus::Completed);
934        state.set_status(1, NodeStatus::Failed);
935        assert_eq!(state.count_by_status(NodeStatus::Completed), 1);
936        assert_eq!(state.count_by_status(NodeStatus::Failed), 1);
937        assert_eq!(state.count_by_status(NodeStatus::Pending), 1);
938    }
939
940    #[test]
941    fn judge_frame_submit_and_evaluate() {
942        let mut frame = JudgeFrame::new();
943        frame
944            .submit(JudgeClaim {
945                node_id: 0,
946                channel: "out".to_string(),
947                success: true,
948                error: None,
949            })
950            .unwrap();
951        frame
952            .submit(JudgeClaim {
953                node_id: 1,
954                channel: "out".to_string(),
955                success: false,
956                error: Some("timeout".to_string()),
957            })
958            .unwrap();
959        frame.evaluate();
960        assert_eq!(frame.verdicts(), &[true, true]);
961        assert!(frame.all_passed());
962    }
963
964    #[test]
965    fn judge_frame_inconsistent_claim_fails() {
966        let mut frame = JudgeFrame::new();
967        // Claims success but has an error — inconsistent.
968        frame
969            .submit(JudgeClaim {
970                node_id: 0,
971                channel: "out".to_string(),
972                success: true,
973                error: Some("error".to_string()),
974            })
975            .unwrap();
976        frame.evaluate();
977        assert_eq!(frame.verdicts(), &[false]);
978        assert!(!frame.all_passed());
979    }
980
981    #[test]
982    fn judge_frame_reset() {
983        let mut frame = JudgeFrame::new();
984        frame
985            .submit(JudgeClaim {
986                node_id: 0,
987                channel: "out".to_string(),
988                success: true,
989                error: None,
990            })
991            .unwrap();
992        frame.evaluate();
993        frame.reset();
994        assert_eq!(frame.claim_count(), 0);
995        assert!(frame.verdicts().is_empty());
996    }
997
998    #[test]
999    fn judge_frame_capacity() {
1000        let mut frame = JudgeFrame::new();
1001        for i in 0..MAX_JUDGE_CLAIMS {
1002            frame
1003                .submit(JudgeClaim {
1004                    node_id: i as u32,
1005                    channel: "out".to_string(),
1006                    success: true,
1007                    error: None,
1008                })
1009                .unwrap();
1010        }
1011        let result = frame.submit(JudgeClaim {
1012            node_id: 99,
1013            channel: "out".to_string(),
1014            success: true,
1015            error: None,
1016        });
1017        assert!(result.is_err());
1018    }
1019
1020    #[test]
1021    fn dag_node_as_control_unit() {
1022        let node = DagNode::new(0, "router", NodeEffect::Pure).as_control_unit();
1023        assert!(node.is_control_unit);
1024    }
1025}