bones_core/dag/
graph.rs

1//! In-memory DAG structure with parent/descendant traversal.
2//!
3//! The [`EventDag`] indexes events by their content-addressed hash for efficient
4//! parent lookup, descendant traversal, and topological iteration.
5//!
6//! # Construction
7//!
8//! The DAG is built incrementally via [`EventDag::insert`]. Events can be
9//! inserted in any order; parent/child links are resolved lazily as events
10//! arrive. This supports both full replay and incremental appending.
11//!
12//! # Deduplication
13//!
14//! Duplicate events (same hash) are silently skipped on insert. This is
15//! inherent to content-addressed design and supports scenarios like
16//! git merges that bring both sides of a branch.
17
18use std::collections::{HashMap, HashSet, VecDeque};
19
20use crate::event::Event;
21
22// ---------------------------------------------------------------------------
23// DagNode
24// ---------------------------------------------------------------------------
25
26/// A node in the event DAG, storing the event and its bidirectional links.
27#[derive(Debug, Clone)]
28pub struct DagNode {
29    /// The event stored at this node.
30    pub event: Event,
31    /// Hashes of this node's parent events (events that causally precede it).
32    pub parents: Vec<String>,
33    /// Hashes of this node's child events (events that causally follow it).
34    pub children: Vec<String>,
35}
36
37// ---------------------------------------------------------------------------
38// EventDag
39// ---------------------------------------------------------------------------
40
41/// An in-memory DAG of events, indexed by content-addressed hash.
42///
43/// Provides O(1) insertion, O(1) node lookup, and efficient traversal
44/// in both causal directions (ancestors and descendants).
45#[derive(Debug, Clone)]
46pub struct EventDag {
47    /// All nodes, keyed by event hash.
48    nodes: HashMap<String, DagNode>,
49}
50
51impl EventDag {
52    /// Create an empty DAG.
53    #[must_use]
54    pub fn new() -> Self {
55        Self {
56            nodes: HashMap::new(),
57        }
58    }
59
60    /// Insert an event into the DAG.
61    ///
62    /// - Registers the event as a node with its declared parents.
63    /// - Creates bidirectional parent→child links for any parents already in the DAG.
64    /// - If a later-inserted parent references this event, the link is created then.
65    /// - Duplicate events (same `event_hash`) are silently skipped.
66    ///
67    /// Runs in O(P) where P is the number of parents for this event.
68    pub fn insert(&mut self, event: Event) {
69        let hash = event.event_hash.clone();
70
71        // Deduplicate: skip if already present.
72        if self.nodes.contains_key(&hash) {
73            return;
74        }
75
76        let parents = event.parents.clone();
77
78        // Insert the new node.
79        self.nodes.insert(
80            hash.clone(),
81            DagNode {
82                event,
83                parents: parents.clone(),
84                children: Vec::new(),
85            },
86        );
87
88        // Link parents → this child.
89        for parent_hash in &parents {
90            if let Some(parent_node) = self.nodes.get_mut(parent_hash) {
91                parent_node.children.push(hash.clone());
92            }
93        }
94
95        // Link this node as child of any already-inserted events that
96        // we haven't linked yet. This handles out-of-order insertion:
97        // if an event was inserted before its children arrived, we need
98        // to update the child's children list when the child is finally
99        // found as a parent.
100        //
101        // Actually, the above parent→child link already handles the
102        // forward direction. For out-of-order, we also need to check
103        // if any existing node lists `hash` as a parent but hasn't
104        // been linked yet.
105        //
106        // Re-scan: for any node that has `hash` in its parents list,
107        // add it as a child of the newly inserted node.
108        // This is O(N) in the worst case but only needed for out-of-order.
109        // We optimize by doing a single pass only for new inserts.
110        let children_to_add: Vec<String> = self
111            .nodes
112            .iter()
113            .filter(|(k, _)| *k != &hash)
114            .filter(|(_, node)| node.parents.contains(&hash))
115            .map(|(k, _)| k.clone())
116            .collect();
117
118        if let Some(node) = self.nodes.get_mut(&hash) {
119            for child_hash in children_to_add {
120                if !node.children.contains(&child_hash) {
121                    node.children.push(child_hash);
122                }
123            }
124        }
125    }
126
127    /// Build a DAG from a slice of events.
128    ///
129    /// Events are inserted in the order given. For replay from an event log,
130    /// this is typically chronological order.
131    #[must_use]
132    pub fn from_events(events: &[Event]) -> Self {
133        let mut dag = Self::with_capacity(events.len());
134        for event in events {
135            dag.insert(event.clone());
136        }
137        dag
138    }
139
140    /// Create an empty DAG with pre-allocated capacity.
141    #[must_use]
142    pub fn with_capacity(capacity: usize) -> Self {
143        Self {
144            nodes: HashMap::with_capacity(capacity),
145        }
146    }
147
148    /// Number of events in the DAG.
149    #[must_use]
150    pub fn len(&self) -> usize {
151        self.nodes.len()
152    }
153
154    /// Returns `true` if the DAG has no events.
155    #[must_use]
156    pub fn is_empty(&self) -> bool {
157        self.nodes.is_empty()
158    }
159
160    /// Look up a node by its event hash.
161    #[must_use]
162    pub fn get(&self, hash: &str) -> Option<&DagNode> {
163        self.nodes.get(hash)
164    }
165
166    /// Return the event for a given hash.
167    #[must_use]
168    pub fn get_event(&self, hash: &str) -> Option<&Event> {
169        self.nodes.get(hash).map(|n| &n.event)
170    }
171
172    /// Returns `true` if the DAG contains an event with the given hash.
173    #[must_use]
174    pub fn contains(&self, hash: &str) -> bool {
175        self.nodes.contains_key(hash)
176    }
177
178    /// Return the hashes of all root events (events with no parents in the DAG).
179    ///
180    /// Multiple roots occur when agents create items concurrently without
181    /// seeing each other's genesis events.
182    #[must_use]
183    pub fn roots(&self) -> Vec<&str> {
184        self.nodes
185            .iter()
186            .filter(|(_, node)| node.parents.is_empty())
187            .map(|(hash, _)| hash.as_str())
188            .collect()
189    }
190
191    /// Return the hashes of all tip events (events with no children).
192    ///
193    /// Tips are the "current heads" of the DAG — events that no other
194    /// event has yet referenced as a parent.
195    #[must_use]
196    pub fn tips(&self) -> Vec<&str> {
197        self.nodes
198            .iter()
199            .filter(|(_, node)| node.children.is_empty())
200            .map(|(hash, _)| hash.as_str())
201            .collect()
202    }
203
204    /// Get all ancestor hashes of the given event (transitive parents).
205    ///
206    /// Performs a BFS walk up the parent chain. Returns an empty set
207    /// for root events. Does NOT include the starting event itself.
208    #[must_use]
209    pub fn ancestors(&self, hash: &str) -> HashSet<String> {
210        let mut visited = HashSet::new();
211        let mut queue = VecDeque::new();
212
213        if let Some(node) = self.nodes.get(hash) {
214            for parent in &node.parents {
215                if visited.insert(parent.clone()) {
216                    queue.push_back(parent.clone());
217                }
218            }
219        }
220
221        while let Some(current) = queue.pop_front() {
222            if let Some(node) = self.nodes.get(&current) {
223                for parent in &node.parents {
224                    if visited.insert(parent.clone()) {
225                        queue.push_back(parent.clone());
226                    }
227                }
228            }
229        }
230
231        visited
232    }
233
234    /// Get all descendant hashes of the given event (transitive children).
235    ///
236    /// Performs a BFS walk down the children chain. Returns an empty set
237    /// for tip events. Does NOT include the starting event itself.
238    #[must_use]
239    pub fn descendants(&self, hash: &str) -> HashSet<String> {
240        let mut visited = HashSet::new();
241        let mut queue = VecDeque::new();
242
243        if let Some(node) = self.nodes.get(hash) {
244            for child in &node.children {
245                if visited.insert(child.clone()) {
246                    queue.push_back(child.clone());
247                }
248            }
249        }
250
251        while let Some(current) = queue.pop_front() {
252            if let Some(node) = self.nodes.get(&current) {
253                for child in &node.children {
254                    if visited.insert(child.clone()) {
255                        queue.push_back(child.clone());
256                    }
257                }
258            }
259        }
260
261        visited
262    }
263
264    /// Iterate events in topological (causal) order via Kahn's algorithm.
265    ///
266    /// Events with no unresolved parents come first. If multiple events
267    /// are ready simultaneously, they are returned in hash-sorted order
268    /// for determinism.
269    ///
270    /// # Multiple Roots
271    ///
272    /// The algorithm handles multiple roots naturally — all root events
273    /// start in the ready set.
274    #[must_use]
275    pub fn topological_order(&self) -> Vec<&Event> {
276        use std::cmp::Reverse;
277        use std::collections::BinaryHeap;
278
279        // Count in-degree (number of parents in the DAG) per node.
280        let mut in_degree: HashMap<&str, usize> = HashMap::with_capacity(self.nodes.len());
281        for (hash, node) in &self.nodes {
282            // Count only parents that are actually in the DAG.
283            let parent_count = node
284                .parents
285                .iter()
286                .filter(|p| self.nodes.contains_key(p.as_str()))
287                .count();
288            in_degree.insert(hash.as_str(), parent_count);
289        }
290
291        // Seed with all roots (in-degree 0). Use a Min-Heap for determinism.
292        let mut ready: BinaryHeap<Reverse<&str>> = in_degree
293            .iter()
294            .filter(|(_, deg)| **deg == 0)
295            .map(|(&hash, _)| Reverse(hash))
296            .collect();
297
298        let mut result = Vec::with_capacity(self.nodes.len());
299
300        while let Some(Reverse(current)) = ready.pop() {
301            if let Some(node) = self.nodes.get(current) {
302                result.push(&node.event);
303
304                // Decrement in-degree for all children.
305                for child_hash in &node.children {
306                    if let Some(deg) = in_degree.get_mut(child_hash.as_str()) {
307                        *deg = deg.saturating_sub(1);
308                        if *deg == 0 {
309                            ready.push(Reverse(child_hash.as_str()));
310                        }
311                    }
312                }
313            }
314        }
315
316        result
317    }
318
319    /// Check if event `a` is a causal ancestor of event `b`.
320    ///
321    /// Returns `true` if there is a directed path from `a` to `b` in the DAG
322    /// (i.e., `a` happened before `b`).
323    #[must_use]
324    pub fn is_ancestor(&self, a: &str, b: &str) -> bool {
325        if a == b {
326            return false;
327        }
328        self.ancestors(b).contains(a)
329    }
330
331    /// Check if two events are concurrent (neither is an ancestor of the other).
332    #[must_use]
333    pub fn are_concurrent(&self, a: &str, b: &str) -> bool {
334        if a == b {
335            return false;
336        }
337        !self.is_ancestor(a, b) && !self.is_ancestor(b, a)
338    }
339
340    /// Return an iterator over all event hashes in the DAG.
341    pub fn hashes(&self) -> impl Iterator<Item = &str> {
342        self.nodes.keys().map(String::as_str)
343    }
344
345    /// Return an iterator over all nodes in the DAG.
346    pub fn nodes(&self) -> impl Iterator<Item = (&str, &DagNode)> {
347        self.nodes.iter().map(|(k, v)| (k.as_str(), v))
348    }
349}
350
351impl Default for EventDag {
352    fn default() -> Self {
353        Self::new()
354    }
355}
356
357// ---------------------------------------------------------------------------
358// Tests
359// ---------------------------------------------------------------------------
360
361#[cfg(test)]
362mod tests {
363    use std::collections::BTreeMap;
364
365    use super::*;
366    use crate::event::data::{CreateData, EventData, MoveData, UpdateData};
367    use crate::event::types::EventType;
368    use crate::event::writer::write_event;
369    use crate::model::item::{Kind, State, Urgency};
370    use crate::model::item_id::ItemId;
371
372    // -------------------------------------------------------------------
373    // Helpers
374    // -------------------------------------------------------------------
375
376    fn make_root(ts: i64, agent: &str) -> Event {
377        let mut event = Event {
378            wall_ts_us: ts,
379            agent: agent.into(),
380            itc: "itc:AQ".into(),
381            parents: vec![],
382            event_type: EventType::Create,
383            item_id: ItemId::new_unchecked("bn-test"),
384            data: EventData::Create(CreateData {
385                title: format!("Root by {agent}"),
386                kind: Kind::Task,
387                size: None,
388                urgency: Urgency::Default,
389                labels: vec![],
390                parent: None,
391                causation: None,
392                description: None,
393                extra: BTreeMap::new(),
394            }),
395            event_hash: String::new(),
396        };
397        write_event(&mut event).unwrap();
398        event
399    }
400
401    fn make_child(ts: i64, parents: &[&str], agent: &str) -> Event {
402        let mut event = Event {
403            wall_ts_us: ts,
404            agent: agent.into(),
405            itc: format!("itc:AQ.{ts}"),
406            parents: parents.iter().map(|s| (*s).to_string()).collect(),
407            event_type: EventType::Move,
408            item_id: ItemId::new_unchecked("bn-test"),
409            data: EventData::Move(MoveData {
410                state: State::Doing,
411                reason: None,
412                extra: BTreeMap::new(),
413            }),
414            event_hash: String::new(),
415        };
416        write_event(&mut event).unwrap();
417        event
418    }
419
420    fn make_update(ts: i64, parents: &[&str], field: &str) -> Event {
421        let mut event = Event {
422            wall_ts_us: ts,
423            agent: "agent-a".into(),
424            itc: format!("itc:AQ.{ts}"),
425            parents: parents.iter().map(|s| (*s).to_string()).collect(),
426            event_type: EventType::Update,
427            item_id: ItemId::new_unchecked("bn-test"),
428            data: EventData::Update(UpdateData {
429                field: field.into(),
430                value: serde_json::json!("new-value"),
431                extra: BTreeMap::new(),
432            }),
433            event_hash: String::new(),
434        };
435        write_event(&mut event).unwrap();
436        event
437    }
438
439    // -------------------------------------------------------------------
440    // Construction
441    // -------------------------------------------------------------------
442
443    #[test]
444    fn empty_dag() {
445        let dag = EventDag::new();
446        assert_eq!(dag.len(), 0);
447        assert!(dag.is_empty());
448        assert!(dag.roots().is_empty());
449        assert!(dag.tips().is_empty());
450    }
451
452    #[test]
453    fn single_root() {
454        let root = make_root(1_000, "agent-a");
455        let dag = EventDag::from_events(&[root.clone()]);
456
457        assert_eq!(dag.len(), 1);
458        assert!(!dag.is_empty());
459        assert!(dag.contains(&root.event_hash));
460        assert_eq!(dag.roots(), vec![root.event_hash.as_str()]);
461        assert_eq!(dag.tips(), vec![root.event_hash.as_str()]);
462    }
463
464    #[test]
465    fn linear_chain() {
466        let root = make_root(1_000, "agent-a");
467        let child = make_child(2_000, &[&root.event_hash], "agent-a");
468        let grandchild = make_child(3_000, &[&child.event_hash], "agent-a");
469
470        let dag = EventDag::from_events(&[root.clone(), child.clone(), grandchild.clone()]);
471
472        assert_eq!(dag.len(), 3);
473
474        // Root detection
475        let roots = dag.roots();
476        assert_eq!(roots.len(), 1);
477        assert!(roots.contains(&root.event_hash.as_str()));
478
479        // Tip detection
480        let tips = dag.tips();
481        assert_eq!(tips.len(), 1);
482        assert!(tips.contains(&grandchild.event_hash.as_str()));
483
484        // Parent/child links
485        let root_node = dag.get(&root.event_hash).unwrap();
486        assert!(root_node.parents.is_empty());
487        assert_eq!(root_node.children, vec![child.event_hash.clone()]);
488
489        let child_node = dag.get(&child.event_hash).unwrap();
490        assert_eq!(child_node.parents, vec![root.event_hash.clone()]);
491        assert_eq!(child_node.children, vec![grandchild.event_hash.clone()]);
492
493        let gc_node = dag.get(&grandchild.event_hash).unwrap();
494        assert_eq!(gc_node.parents, vec![child.event_hash.clone()]);
495        assert!(gc_node.children.is_empty());
496    }
497
498    #[test]
499    fn fork_topology() {
500        //      root
501        //     /    \
502        //   left   right
503        let root = make_root(1_000, "agent-a");
504        let left = make_child(2_000, &[&root.event_hash], "agent-a");
505        let right = make_child(2_100, &[&root.event_hash], "agent-b");
506
507        let dag = EventDag::from_events(&[root.clone(), left.clone(), right.clone()]);
508
509        assert_eq!(dag.len(), 3);
510        assert_eq!(dag.roots().len(), 1);
511
512        let tips = dag.tips();
513        assert_eq!(tips.len(), 2);
514        assert!(tips.contains(&left.event_hash.as_str()));
515        assert!(tips.contains(&right.event_hash.as_str()));
516
517        // Root has two children
518        let root_node = dag.get(&root.event_hash).unwrap();
519        assert_eq!(root_node.children.len(), 2);
520    }
521
522    #[test]
523    fn merge_topology() {
524        //    root
525        //   /    \
526        // left   right
527        //   \    /
528        //   merge
529        let root = make_root(1_000, "agent-a");
530        let left = make_child(2_000, &[&root.event_hash], "agent-a");
531        let right = make_child(2_100, &[&root.event_hash], "agent-b");
532        let merge = make_child(3_000, &[&left.event_hash, &right.event_hash], "agent-a");
533
534        let dag =
535            EventDag::from_events(&[root.clone(), left.clone(), right.clone(), merge.clone()]);
536
537        assert_eq!(dag.len(), 4);
538        assert_eq!(dag.tips().len(), 1);
539        assert!(dag.tips().contains(&merge.event_hash.as_str()));
540
541        let merge_node = dag.get(&merge.event_hash).unwrap();
542        assert_eq!(merge_node.parents.len(), 2);
543    }
544
545    #[test]
546    fn multiple_roots() {
547        // Two independent genesis events (concurrent agents).
548        let root_a = make_root(1_000, "agent-a");
549        let root_b = make_root(1_100, "agent-b");
550
551        let dag = EventDag::from_events(&[root_a.clone(), root_b.clone()]);
552
553        assert_eq!(dag.len(), 2);
554        let roots = dag.roots();
555        assert_eq!(roots.len(), 2);
556        assert!(roots.contains(&root_a.event_hash.as_str()));
557        assert!(roots.contains(&root_b.event_hash.as_str()));
558    }
559
560    // -------------------------------------------------------------------
561    // Deduplication
562    // -------------------------------------------------------------------
563
564    #[test]
565    fn duplicate_insert_is_noop() {
566        let root = make_root(1_000, "agent-a");
567        let mut dag = EventDag::new();
568
569        dag.insert(root.clone());
570        dag.insert(root.clone()); // duplicate
571
572        assert_eq!(dag.len(), 1);
573    }
574
575    #[test]
576    fn duplicate_in_from_events() {
577        let root = make_root(1_000, "agent-a");
578        let dag = EventDag::from_events(&[root.clone(), root.clone()]);
579
580        assert_eq!(dag.len(), 1);
581    }
582
583    // -------------------------------------------------------------------
584    // Out-of-order insertion
585    // -------------------------------------------------------------------
586
587    #[test]
588    fn out_of_order_insertion() {
589        let root = make_root(1_000, "agent-a");
590        let child = make_child(2_000, &[&root.event_hash], "agent-a");
591
592        // Insert child BEFORE parent.
593        let dag = EventDag::from_events(&[child.clone(), root.clone()]);
594
595        assert_eq!(dag.len(), 2);
596
597        // Parent→child links should still be correct.
598        let root_node = dag.get(&root.event_hash).unwrap();
599        assert!(root_node.children.contains(&child.event_hash));
600
601        let child_node = dag.get(&child.event_hash).unwrap();
602        assert!(child_node.parents.contains(&root.event_hash));
603    }
604
605    // -------------------------------------------------------------------
606    // Traversal
607    // -------------------------------------------------------------------
608
609    #[test]
610    fn ancestors_of_root_is_empty() {
611        let root = make_root(1_000, "agent-a");
612        let dag = EventDag::from_events(&[root.clone()]);
613
614        assert!(dag.ancestors(&root.event_hash).is_empty());
615    }
616
617    #[test]
618    fn ancestors_of_child() {
619        let root = make_root(1_000, "agent-a");
620        let child = make_child(2_000, &[&root.event_hash], "agent-a");
621        let grandchild = make_child(3_000, &[&child.event_hash], "agent-a");
622
623        let dag = EventDag::from_events(&[root.clone(), child.clone(), grandchild.clone()]);
624
625        let ancestors = dag.ancestors(&grandchild.event_hash);
626        assert_eq!(ancestors.len(), 2);
627        assert!(ancestors.contains(&root.event_hash));
628        assert!(ancestors.contains(&child.event_hash));
629    }
630
631    #[test]
632    fn ancestors_of_merge_event() {
633        let root = make_root(1_000, "agent-a");
634        let left = make_child(2_000, &[&root.event_hash], "agent-a");
635        let right = make_child(2_100, &[&root.event_hash], "agent-b");
636        let merge = make_child(3_000, &[&left.event_hash, &right.event_hash], "agent-a");
637
638        let dag =
639            EventDag::from_events(&[root.clone(), left.clone(), right.clone(), merge.clone()]);
640
641        let ancestors = dag.ancestors(&merge.event_hash);
642        assert_eq!(ancestors.len(), 3);
643        assert!(ancestors.contains(&root.event_hash));
644        assert!(ancestors.contains(&left.event_hash));
645        assert!(ancestors.contains(&right.event_hash));
646    }
647
648    #[test]
649    fn descendants_of_root() {
650        let root = make_root(1_000, "agent-a");
651        let child = make_child(2_000, &[&root.event_hash], "agent-a");
652        let grandchild = make_child(3_000, &[&child.event_hash], "agent-a");
653
654        let dag = EventDag::from_events(&[root.clone(), child.clone(), grandchild.clone()]);
655
656        let descendants = dag.descendants(&root.event_hash);
657        assert_eq!(descendants.len(), 2);
658        assert!(descendants.contains(&child.event_hash));
659        assert!(descendants.contains(&grandchild.event_hash));
660    }
661
662    #[test]
663    fn descendants_of_tip_is_empty() {
664        let root = make_root(1_000, "agent-a");
665        let child = make_child(2_000, &[&root.event_hash], "agent-a");
666
667        let dag = EventDag::from_events(&[root.clone(), child.clone()]);
668
669        assert!(dag.descendants(&child.event_hash).is_empty());
670    }
671
672    #[test]
673    fn descendants_of_fork_root() {
674        let root = make_root(1_000, "agent-a");
675        let left = make_child(2_000, &[&root.event_hash], "agent-a");
676        let right = make_child(2_100, &[&root.event_hash], "agent-b");
677
678        let dag = EventDag::from_events(&[root.clone(), left.clone(), right.clone()]);
679
680        let descendants = dag.descendants(&root.event_hash);
681        assert_eq!(descendants.len(), 2);
682        assert!(descendants.contains(&left.event_hash));
683        assert!(descendants.contains(&right.event_hash));
684    }
685
686    // -------------------------------------------------------------------
687    // Topological order
688    // -------------------------------------------------------------------
689
690    #[test]
691    fn topological_order_empty() {
692        let dag = EventDag::new();
693        assert!(dag.topological_order().is_empty());
694    }
695
696    #[test]
697    fn topological_order_single() {
698        let root = make_root(1_000, "agent-a");
699        let dag = EventDag::from_events(&[root.clone()]);
700
701        let order = dag.topological_order();
702        assert_eq!(order.len(), 1);
703        assert_eq!(order[0].event_hash, root.event_hash);
704    }
705
706    #[test]
707    fn topological_order_linear_chain() {
708        let root = make_root(1_000, "agent-a");
709        let child = make_child(2_000, &[&root.event_hash], "agent-a");
710        let grandchild = make_child(3_000, &[&child.event_hash], "agent-a");
711
712        let dag = EventDag::from_events(&[root.clone(), child.clone(), grandchild.clone()]);
713
714        let order = dag.topological_order();
715        assert_eq!(order.len(), 3);
716        assert_eq!(order[0].event_hash, root.event_hash);
717        assert_eq!(order[1].event_hash, child.event_hash);
718        assert_eq!(order[2].event_hash, grandchild.event_hash);
719    }
720
721    #[test]
722    fn topological_order_respects_causality() {
723        // In any valid topological order, every parent must appear before
724        // all of its children.
725        let root = make_root(1_000, "agent-a");
726        let left = make_child(2_000, &[&root.event_hash], "agent-a");
727        let right = make_child(2_100, &[&root.event_hash], "agent-b");
728        let merge = make_child(3_000, &[&left.event_hash, &right.event_hash], "agent-a");
729
730        let dag =
731            EventDag::from_events(&[root.clone(), left.clone(), right.clone(), merge.clone()]);
732
733        let order = dag.topological_order();
734        assert_eq!(order.len(), 4);
735
736        // Build position map.
737        let pos: HashMap<&str, usize> = order
738            .iter()
739            .enumerate()
740            .map(|(i, e)| (e.event_hash.as_str(), i))
741            .collect();
742
743        // Root before everything.
744        assert!(pos[root.event_hash.as_str()] < pos[left.event_hash.as_str()]);
745        assert!(pos[root.event_hash.as_str()] < pos[right.event_hash.as_str()]);
746
747        // Both branches before merge.
748        assert!(pos[left.event_hash.as_str()] < pos[merge.event_hash.as_str()]);
749        assert!(pos[right.event_hash.as_str()] < pos[merge.event_hash.as_str()]);
750    }
751
752    #[test]
753    fn topological_order_is_deterministic() {
754        let root = make_root(1_000, "agent-a");
755        let left = make_child(2_000, &[&root.event_hash], "agent-a");
756        let right = make_child(2_100, &[&root.event_hash], "agent-b");
757
758        let dag = EventDag::from_events(&[root.clone(), left.clone(), right.clone()]);
759
760        let order1: Vec<_> = dag
761            .topological_order()
762            .iter()
763            .map(|e| e.event_hash.clone())
764            .collect();
765        let order2: Vec<_> = dag
766            .topological_order()
767            .iter()
768            .map(|e| e.event_hash.clone())
769            .collect();
770
771        assert_eq!(order1, order2, "topological order must be deterministic");
772    }
773
774    #[test]
775    fn topological_order_multiple_roots() {
776        let root_a = make_root(1_000, "agent-a");
777        let root_b = make_root(1_100, "agent-b");
778        let child = make_child(2_000, &[&root_a.event_hash, &root_b.event_hash], "agent-a");
779
780        let dag = EventDag::from_events(&[root_a.clone(), root_b.clone(), child.clone()]);
781
782        let order = dag.topological_order();
783        assert_eq!(order.len(), 3);
784
785        // Both roots before child.
786        let pos: HashMap<&str, usize> = order
787            .iter()
788            .enumerate()
789            .map(|(i, e)| (e.event_hash.as_str(), i))
790            .collect();
791
792        assert!(pos[root_a.event_hash.as_str()] < pos[child.event_hash.as_str()]);
793        assert!(pos[root_b.event_hash.as_str()] < pos[child.event_hash.as_str()]);
794    }
795
796    // -------------------------------------------------------------------
797    // Ancestry queries
798    // -------------------------------------------------------------------
799
800    #[test]
801    fn is_ancestor_linear() {
802        let root = make_root(1_000, "agent-a");
803        let child = make_child(2_000, &[&root.event_hash], "agent-a");
804        let grandchild = make_child(3_000, &[&child.event_hash], "agent-a");
805
806        let dag = EventDag::from_events(&[root.clone(), child.clone(), grandchild.clone()]);
807
808        assert!(dag.is_ancestor(&root.event_hash, &grandchild.event_hash));
809        assert!(dag.is_ancestor(&root.event_hash, &child.event_hash));
810        assert!(dag.is_ancestor(&child.event_hash, &grandchild.event_hash));
811
812        // Not ancestor in reverse.
813        assert!(!dag.is_ancestor(&grandchild.event_hash, &root.event_hash));
814        assert!(!dag.is_ancestor(&child.event_hash, &root.event_hash));
815
816        // Not ancestor of self.
817        assert!(!dag.is_ancestor(&root.event_hash, &root.event_hash));
818    }
819
820    #[test]
821    fn are_concurrent() {
822        let root = make_root(1_000, "agent-a");
823        let left = make_child(2_000, &[&root.event_hash], "agent-a");
824        let right = make_child(2_100, &[&root.event_hash], "agent-b");
825
826        let dag = EventDag::from_events(&[root.clone(), left.clone(), right.clone()]);
827
828        assert!(dag.are_concurrent(&left.event_hash, &right.event_hash));
829        assert!(!dag.are_concurrent(&root.event_hash, &left.event_hash));
830        assert!(!dag.are_concurrent(&left.event_hash, &left.event_hash));
831    }
832
833    // -------------------------------------------------------------------
834    // Node / event accessors
835    // -------------------------------------------------------------------
836
837    #[test]
838    fn get_event_returns_correct_event() {
839        let root = make_root(1_000, "agent-a");
840        let dag = EventDag::from_events(&[root.clone()]);
841
842        let event = dag.get_event(&root.event_hash).unwrap();
843        assert_eq!(event.agent, "agent-a");
844    }
845
846    #[test]
847    fn get_nonexistent_returns_none() {
848        let dag = EventDag::new();
849        assert!(dag.get("blake3:nonexistent").is_none());
850        assert!(dag.get_event("blake3:nonexistent").is_none());
851    }
852
853    #[test]
854    fn contains_works() {
855        let root = make_root(1_000, "agent-a");
856        let dag = EventDag::from_events(&[root.clone()]);
857
858        assert!(dag.contains(&root.event_hash));
859        assert!(!dag.contains("blake3:other"));
860    }
861
862    #[test]
863    fn hashes_iterator() {
864        let root = make_root(1_000, "agent-a");
865        let child = make_child(2_000, &[&root.event_hash], "agent-a");
866
867        let dag = EventDag::from_events(&[root.clone(), child.clone()]);
868
869        let hashes: HashSet<&str> = dag.hashes().collect();
870        assert_eq!(hashes.len(), 2);
871        assert!(hashes.contains(root.event_hash.as_str()));
872        assert!(hashes.contains(child.event_hash.as_str()));
873    }
874
875    // -------------------------------------------------------------------
876    // Ancestors/descendants for nonexistent hash
877    // -------------------------------------------------------------------
878
879    #[test]
880    fn ancestors_of_nonexistent_is_empty() {
881        let dag = EventDag::new();
882        assert!(dag.ancestors("blake3:none").is_empty());
883    }
884
885    #[test]
886    fn descendants_of_nonexistent_is_empty() {
887        let dag = EventDag::new();
888        assert!(dag.descendants("blake3:none").is_empty());
889    }
890
891    // -------------------------------------------------------------------
892    // Incremental insert
893    // -------------------------------------------------------------------
894
895    #[test]
896    fn incremental_insert() {
897        let root = make_root(1_000, "agent-a");
898        let child = make_child(2_000, &[&root.event_hash], "agent-a");
899
900        let mut dag = EventDag::new();
901
902        dag.insert(root.clone());
903        assert_eq!(dag.len(), 1);
904        assert_eq!(dag.tips().len(), 1);
905
906        dag.insert(child.clone());
907        assert_eq!(dag.len(), 2);
908        assert_eq!(dag.tips().len(), 1);
909        assert!(dag.tips().contains(&child.event_hash.as_str()));
910
911        // Root is no longer a tip.
912        assert!(!dag.tips().contains(&root.event_hash.as_str()));
913    }
914
915    // -------------------------------------------------------------------
916    // Large DAG stress test
917    // -------------------------------------------------------------------
918
919    #[test]
920    fn large_linear_chain() {
921        let mut events = Vec::with_capacity(100);
922        let root = make_root(1_000, "agent-a");
923        events.push(root);
924
925        for i in 1..100 {
926            let parent_hash = events[i - 1].event_hash.clone();
927            let child = make_child(1_000 + i as i64, &[&parent_hash], "agent-a");
928            events.push(child);
929        }
930
931        let dag = EventDag::from_events(&events);
932        assert_eq!(dag.len(), 100);
933        assert_eq!(dag.roots().len(), 1);
934        assert_eq!(dag.tips().len(), 1);
935
936        let topo = dag.topological_order();
937        assert_eq!(topo.len(), 100);
938
939        // Verify ordering.
940        for i in 0..99 {
941            assert_eq!(topo[i].event_hash, events[i].event_hash);
942        }
943    }
944
945    #[test]
946    fn diamond_dag_with_updates() {
947        //   root
948        //  /    \
949        // u1    u2
950        //  \    /
951        //  merge
952        let root = make_root(1_000, "agent-a");
953        let u1 = make_update(2_000, &[&root.event_hash], "title");
954        let u2 = make_update(2_100, &[&root.event_hash], "priority");
955        let merge = make_child(3_000, &[&u1.event_hash, &u2.event_hash], "agent-a");
956
957        let dag = EventDag::from_events(&[root.clone(), u1.clone(), u2.clone(), merge.clone()]);
958
959        assert_eq!(dag.len(), 4);
960        assert_eq!(dag.roots().len(), 1);
961        assert_eq!(dag.tips().len(), 1);
962
963        // Ancestors of merge includes all 3 predecessors.
964        let anc = dag.ancestors(&merge.event_hash);
965        assert_eq!(anc.len(), 3);
966
967        // Descendants of root includes all 3 successors.
968        let desc = dag.descendants(&root.event_hash);
969        assert_eq!(desc.len(), 3);
970    }
971}
bones_core/dag/graph.rs

bones_core/dag/
graph.rs
