bones_core/dag/
lca.rs

1//! Lowest Common Ancestor (LCA) finding for the event DAG.
2//!
3//! Given two tip events in a DAG, the LCA is the most recent event that is
4//! an ancestor of **both** tips. Finding the LCA identifies the point where
5//! two branches diverged, which is the key input for divergent-branch replay.
6//!
7//! # Algorithm
8//!
9//! We use a bidirectional BFS: walk upward from both tips simultaneously,
10//! alternating between them. The first node visited by **both** walks is
11//! the LCA. This runs in O(divergent) — proportional to the events since
12//! divergence, not the total DAG size.
13//!
14//! # Edge Cases
15//!
16//! - If one tip is an ancestor of the other, the ancestor tip **is** the LCA.
17//! - If both tips are the same event, that event is the LCA.
18//! - If the tips have no common ancestor (disjoint roots), returns `None`.
19
20use std::collections::{HashSet, VecDeque};
21
22use super::graph::EventDag;
23
24/// Errors from LCA computation.
25#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
26pub enum LcaError {
27    /// One or both tip hashes were not found in the DAG.
28    #[error("event not found in DAG: {0}")]
29    EventNotFound(String),
30}
31
32/// Find the Lowest Common Ancestor of two events in the DAG.
33///
34/// Returns `Ok(Some(hash))` with the LCA event hash, or `Ok(None)` if the
35/// two events share no common ancestor (disjoint roots).
36///
37/// # Special cases
38///
39/// - If `tip_a == tip_b`, returns `Ok(Some(tip_a))`.
40/// - If `tip_a` is an ancestor of `tip_b`, returns `Ok(Some(tip_a))`.
41/// - If `tip_b` is an ancestor of `tip_a`, returns `Ok(Some(tip_b))`.
42///
43/// # Errors
44///
45/// Returns [`LcaError::EventNotFound`] if either tip hash is not in the DAG.
46///
47/// # Performance
48///
49/// Runs in O(D) where D is the number of events between the tips and their
50/// LCA — proportional to the divergent portion, not the entire DAG.
51pub fn find_lca(dag: &EventDag, tip_a: &str, tip_b: &str) -> Result<Option<String>, LcaError> {
52    // Validate both tips exist.
53    if !dag.contains(tip_a) {
54        return Err(LcaError::EventNotFound(tip_a.to_string()));
55    }
56    if !dag.contains(tip_b) {
57        return Err(LcaError::EventNotFound(tip_b.to_string()));
58    }
59
60    // Same tip → trivial LCA.
61    if tip_a == tip_b {
62        return Ok(Some(tip_a.to_string()));
63    }
64
65    // Bidirectional BFS: walk upward from both tips.
66    // visited_a and visited_b track which nodes each walk has seen.
67    let mut visited_a: HashSet<String> = HashSet::new();
68    let mut visited_b: HashSet<String> = HashSet::new();
69    let mut queue_a: VecDeque<String> = VecDeque::new();
70    let mut queue_b: VecDeque<String> = VecDeque::new();
71
72    // Seed both queues with the tips themselves.
73    visited_a.insert(tip_a.to_string());
74    visited_b.insert(tip_b.to_string());
75    queue_a.push_back(tip_a.to_string());
76    queue_b.push_back(tip_b.to_string());
77
78    // Check initial cross-containment (one tip is ancestor of the other).
79    if visited_b.contains(tip_a) {
80        return Ok(Some(tip_a.to_string()));
81    }
82    if visited_a.contains(tip_b) {
83        return Ok(Some(tip_b.to_string()));
84    }
85
86    // Alternate BFS steps between the two walks.
87    loop {
88        let a_done = queue_a.is_empty();
89        let b_done = queue_b.is_empty();
90
91        if a_done && b_done {
92            // Both walks exhausted — no common ancestor.
93            return Ok(None);
94        }
95
96        // Step walk A.
97        if !a_done && let Some(lca) = bfs_step(dag, &mut queue_a, &mut visited_a, &visited_b) {
98            return Ok(Some(lca));
99        }
100
101        // Step walk B.
102        if !b_done && let Some(lca) = bfs_step(dag, &mut queue_b, &mut visited_b, &visited_a) {
103            return Ok(Some(lca));
104        }
105    }
106}
107
108/// Perform one BFS step: dequeue a node, enqueue its parents.
109/// Returns `Some(hash)` if any newly visited node is in `other_visited`.
110fn bfs_step(
111    dag: &EventDag,
112    queue: &mut VecDeque<String>,
113    visited: &mut HashSet<String>,
114    other_visited: &HashSet<String>,
115) -> Option<String> {
116    let current = queue.pop_front()?;
117
118    if let Some(node) = dag.get(&current) {
119        for parent_hash in &node.parents {
120            if visited.insert(parent_hash.clone()) {
121                // First time this walk sees this node.
122                if other_visited.contains(parent_hash) {
123                    // Both walks have now visited this node → LCA found.
124                    return Some(parent_hash.clone());
125                }
126                queue.push_back(parent_hash.clone());
127            }
128        }
129    }
130
131    None
132}
133
134/// Find **all** LCAs (there can be multiple in a DAG with diamond merges).
135///
136/// An LCA is a common ancestor of both tips such that no descendant of it
137/// is also a common ancestor. In practice, most divergent branches have a
138/// single LCA, but complex merge histories can produce multiple.
139///
140/// Returns the hashes in no particular order. Returns an empty vec if the
141/// tips share no common ancestor.
142///
143/// # Errors
144///
145/// Returns [`LcaError::EventNotFound`] if either tip is not in the DAG.
146pub fn find_all_lcas(dag: &EventDag, tip_a: &str, tip_b: &str) -> Result<Vec<String>, LcaError> {
147    if !dag.contains(tip_a) {
148        return Err(LcaError::EventNotFound(tip_a.to_string()));
149    }
150    if !dag.contains(tip_b) {
151        return Err(LcaError::EventNotFound(tip_b.to_string()));
152    }
153
154    if tip_a == tip_b {
155        return Ok(vec![tip_a.to_string()]);
156    }
157
158    // Compute full ancestor sets for both tips (including the tips themselves).
159    let mut ancestors_a = dag.ancestors(tip_a);
160    ancestors_a.insert(tip_a.to_string());
161    let mut ancestors_b = dag.ancestors(tip_b);
162    ancestors_b.insert(tip_b.to_string());
163
164    // Common ancestors = intersection.
165    let common: HashSet<&String> = ancestors_a.intersection(&ancestors_b).collect();
166
167    if common.is_empty() {
168        return Ok(vec![]);
169    }
170
171    // LCAs are common ancestors that have no descendants that are also common ancestors.
172    // A common ancestor C is an LCA iff no child of C is also a common ancestor.
173    let mut lcas: Vec<String> = Vec::new();
174    for &ca in &common {
175        let has_common_child = dag
176            .get(ca)
177            .is_some_and(|node| node.children.iter().any(|c| common.contains(c)));
178
179        if !has_common_child {
180            lcas.push(ca.clone());
181        }
182    }
183
184    lcas.sort(); // deterministic order
185    Ok(lcas)
186}
187
188// ---------------------------------------------------------------------------
189// Tests
190// ---------------------------------------------------------------------------
191
192#[cfg(test)]
193mod tests {
194    use super::*;
195    use crate::dag::graph::EventDag;
196    use crate::event::Event;
197    use crate::event::data::{CreateData, EventData, MoveData, UpdateData};
198    use crate::event::types::EventType;
199    use crate::event::writer::write_event;
200    use crate::model::item::{Kind, State, Urgency};
201    use crate::model::item_id::ItemId;
202    use std::collections::BTreeMap;
203
204    // -------------------------------------------------------------------
205    // Helpers (same pattern as graph.rs tests)
206    // -------------------------------------------------------------------
207
208    fn make_root(ts: i64, agent: &str) -> Event {
209        let mut event = Event {
210            wall_ts_us: ts,
211            agent: agent.into(),
212            itc: "itc:AQ".into(),
213            parents: vec![],
214            event_type: EventType::Create,
215            item_id: ItemId::new_unchecked("bn-test"),
216            data: EventData::Create(CreateData {
217                title: format!("Root by {agent}"),
218                kind: Kind::Task,
219                size: None,
220                urgency: Urgency::Default,
221                labels: vec![],
222                parent: None,
223                causation: None,
224                description: None,
225                extra: BTreeMap::new(),
226            }),
227            event_hash: String::new(),
228        };
229        write_event(&mut event).unwrap();
230        event
231    }
232
233    fn make_child(ts: i64, parents: &[&str], agent: &str) -> Event {
234        let mut event = Event {
235            wall_ts_us: ts,
236            agent: agent.into(),
237            itc: format!("itc:AQ.{ts}"),
238            parents: parents.iter().map(|s| (*s).to_string()).collect(),
239            event_type: EventType::Move,
240            item_id: ItemId::new_unchecked("bn-test"),
241            data: EventData::Move(MoveData {
242                state: State::Doing,
243                reason: None,
244                extra: BTreeMap::new(),
245            }),
246            event_hash: String::new(),
247        };
248        write_event(&mut event).unwrap();
249        event
250    }
251
252    fn make_update(ts: i64, parents: &[&str], field: &str, agent: &str) -> Event {
253        let mut event = Event {
254            wall_ts_us: ts,
255            agent: agent.into(),
256            itc: format!("itc:AQ.{ts}"),
257            parents: parents.iter().map(|s| (*s).to_string()).collect(),
258            event_type: EventType::Update,
259            item_id: ItemId::new_unchecked("bn-test"),
260            data: EventData::Update(UpdateData {
261                field: field.into(),
262                value: serde_json::json!("new-value"),
263                extra: BTreeMap::new(),
264            }),
265            event_hash: String::new(),
266        };
267        write_event(&mut event).unwrap();
268        event
269    }
270
271    // ===================================================================
272    // find_lca tests
273    // ===================================================================
274
275    #[test]
276    fn lca_same_tip() {
277        let root = make_root(1_000, "agent-a");
278        let dag = EventDag::from_events(&[root.clone()]);
279
280        let lca = find_lca(&dag, &root.event_hash, &root.event_hash).unwrap();
281        assert_eq!(lca, Some(root.event_hash));
282    }
283
284    #[test]
285    fn lca_event_not_found() {
286        let dag = EventDag::new();
287        let err = find_lca(&dag, "blake3:nope", "blake3:also-nope").unwrap_err();
288        assert!(matches!(err, LcaError::EventNotFound(_)));
289    }
290
291    #[test]
292    fn lca_one_is_ancestor_of_other() {
293        // root → child
294        let root = make_root(1_000, "agent-a");
295        let child = make_child(2_000, &[&root.event_hash], "agent-a");
296        let dag = EventDag::from_events(&[root.clone(), child.clone()]);
297
298        // LCA(root, child) = root
299        let lca = find_lca(&dag, &root.event_hash, &child.event_hash).unwrap();
300        assert_eq!(lca, Some(root.event_hash.clone()));
301
302        // LCA(child, root) = root (symmetric)
303        let lca2 = find_lca(&dag, &child.event_hash, &root.event_hash).unwrap();
304        assert_eq!(lca2, Some(root.event_hash));
305    }
306
307    #[test]
308    fn lca_simple_fork() {
309        //      root
310        //     /    \
311        //   left   right
312        let root = make_root(1_000, "agent-a");
313        let left = make_child(2_000, &[&root.event_hash], "agent-a");
314        let right = make_child(2_100, &[&root.event_hash], "agent-b");
315        let dag = EventDag::from_events(&[root.clone(), left.clone(), right.clone()]);
316
317        let lca = find_lca(&dag, &left.event_hash, &right.event_hash).unwrap();
318        assert_eq!(lca, Some(root.event_hash));
319    }
320
321    #[test]
322    fn lca_deep_fork() {
323        //  root → a → b → left
324        //               \→ right
325        let root = make_root(1_000, "agent-a");
326        let a = make_child(2_000, &[&root.event_hash], "agent-a");
327        let b = make_child(3_000, &[&a.event_hash], "agent-a");
328        let left = make_child(4_000, &[&b.event_hash], "agent-a");
329        let right = make_child(4_100, &[&b.event_hash], "agent-b");
330
331        let dag = EventDag::from_events(&[
332            root.clone(),
333            a.clone(),
334            b.clone(),
335            left.clone(),
336            right.clone(),
337        ]);
338
339        let lca = find_lca(&dag, &left.event_hash, &right.event_hash).unwrap();
340        assert_eq!(lca, Some(b.event_hash));
341    }
342
343    #[test]
344    fn lca_asymmetric_depth() {
345        //  root → a → b → c → left
346        //       \→ right
347        let root = make_root(1_000, "agent-a");
348        let a = make_child(2_000, &[&root.event_hash], "agent-a");
349        let b = make_child(3_000, &[&a.event_hash], "agent-a");
350        let c = make_child(4_000, &[&b.event_hash], "agent-a");
351        let left = make_child(5_000, &[&c.event_hash], "agent-a");
352        let right = make_child(2_100, &[&root.event_hash], "agent-b");
353
354        let dag = EventDag::from_events(&[
355            root.clone(),
356            a.clone(),
357            b.clone(),
358            c.clone(),
359            left.clone(),
360            right.clone(),
361        ]);
362
363        let lca = find_lca(&dag, &left.event_hash, &right.event_hash).unwrap();
364        assert_eq!(lca, Some(root.event_hash));
365    }
366
367    #[test]
368    fn lca_diamond_after_fork() {
369        //     root
370        //    /    \
371        //  a1      b1
372        //    \    /
373        //    merge
374        //    /    \
375        //  a2      b2
376        let root = make_root(1_000, "agent-a");
377        let a1 = make_child(2_000, &[&root.event_hash], "agent-a");
378        let b1 = make_child(2_100, &[&root.event_hash], "agent-b");
379        let merge = make_child(3_000, &[&a1.event_hash, &b1.event_hash], "agent-a");
380        let a2 = make_child(4_000, &[&merge.event_hash], "agent-a");
381        let b2 = make_child(4_100, &[&merge.event_hash], "agent-b");
382
383        let dag = EventDag::from_events(&[
384            root.clone(),
385            a1.clone(),
386            b1.clone(),
387            merge.clone(),
388            a2.clone(),
389            b2.clone(),
390        ]);
391
392        // LCA of the second fork should be the merge point
393        let lca = find_lca(&dag, &a2.event_hash, &b2.event_hash).unwrap();
394        assert_eq!(lca, Some(merge.event_hash));
395    }
396
397    #[test]
398    fn lca_disjoint_roots_returns_none() {
399        // Two independent roots with no common ancestor
400        let root_a = make_root(1_000, "agent-a");
401        let root_b = make_root(1_100, "agent-b");
402        let dag = EventDag::from_events(&[root_a.clone(), root_b.clone()]);
403
404        let lca = find_lca(&dag, &root_a.event_hash, &root_b.event_hash).unwrap();
405        assert_eq!(lca, None);
406    }
407
408    #[test]
409    fn lca_is_symmetric() {
410        let root = make_root(1_000, "agent-a");
411        let left = make_child(2_000, &[&root.event_hash], "agent-a");
412        let right = make_child(2_100, &[&root.event_hash], "agent-b");
413        let dag = EventDag::from_events(&[root.clone(), left.clone(), right.clone()]);
414
415        let lca_ab = find_lca(&dag, &left.event_hash, &right.event_hash).unwrap();
416        let lca_ba = find_lca(&dag, &right.event_hash, &left.event_hash).unwrap();
417        assert_eq!(lca_ab, lca_ba, "LCA must be symmetric");
418    }
419
420    // ===================================================================
421    // find_all_lcas tests
422    // ===================================================================
423
424    #[test]
425    fn all_lcas_simple_fork() {
426        let root = make_root(1_000, "agent-a");
427        let left = make_child(2_000, &[&root.event_hash], "agent-a");
428        let right = make_child(2_100, &[&root.event_hash], "agent-b");
429        let dag = EventDag::from_events(&[root.clone(), left.clone(), right.clone()]);
430
431        let lcas = find_all_lcas(&dag, &left.event_hash, &right.event_hash).unwrap();
432        assert_eq!(lcas, vec![root.event_hash]);
433    }
434
435    #[test]
436    fn all_lcas_criss_cross_merge() {
437        // Criss-cross produces TWO LCAs:
438        //
439        //     root
440        //    /    \
441        //  a1      b1
442        //  |  \  / |
443        //  | merge1 |
444        //  |  /  \  |
445        //  a2      b2
446        //
447        // Actually, a true criss-cross:
448        //     root
449        //    /    \
450        //  a1      b1
451        //  | \    / |
452        //  |  m1    |     (m1 = merge of a1+b1)
453        //  |    \   |
454        //  |     m2 |     (m2 = merge of a1+b1 from other side)
455        //  |    /   |
456        //  a2      b2
457        //
458        // For simplicity, test the diamond-with-two-paths case:
459        //     root
460        //    /    \
461        //  a1      b1
462        //    \    /
463        //    merge
464        // This has exactly 1 LCA (merge for tips on different branches after merge).
465        //
466        // A real 2-LCA case requires parallel merge points:
467        //     root
468        //    /    \
469        //  a1      b1
470        //   |\ /|
471        //   | X |
472        //   |/ \|
473        //  ma    mb    (ma merges a1+b1, mb merges a1+b1 independently)
474        //   |    |
475        //  a2   b2
476        let root = make_root(1_000, "agent-a");
477        let a1 = make_child(2_000, &[&root.event_hash], "agent-a");
478        let b1 = make_child(2_100, &[&root.event_hash], "agent-b");
479        // Two independent merges of a1+b1
480        let ma = make_child(3_000, &[&a1.event_hash, &b1.event_hash], "agent-a");
481        let mb = make_update(3_100, &[&a1.event_hash, &b1.event_hash], "title", "agent-b");
482        // Further work on each merge
483        let a2 = make_child(4_000, &[&ma.event_hash], "agent-a");
484        let b2 = make_update(4_100, &[&mb.event_hash], "desc", "agent-b");
485
486        let dag = EventDag::from_events(&[
487            root.clone(),
488            a1.clone(),
489            b1.clone(),
490            ma.clone(),
491            mb.clone(),
492            a2.clone(),
493            b2.clone(),
494        ]);
495
496        let mut lcas = find_all_lcas(&dag, &a2.event_hash, &b2.event_hash).unwrap();
497        lcas.sort();
498        // ma is only an ancestor of a2 (not b2), and mb is only an ancestor
499        // of b2 (not a2), so neither is a *common* ancestor. The actual
500        // common ancestors are a1 and b1, and neither is an ancestor of
501        // the other, so both are LCAs.
502        assert_eq!(lcas.len(), 2);
503        let mut expected = vec![a1.event_hash.clone(), b1.event_hash.clone()];
504        expected.sort();
505        assert_eq!(lcas, expected);
506    }
507
508    #[test]
509    fn all_lcas_same_tip() {
510        let root = make_root(1_000, "agent-a");
511        let dag = EventDag::from_events(&[root.clone()]);
512
513        let lcas = find_all_lcas(&dag, &root.event_hash, &root.event_hash).unwrap();
514        assert_eq!(lcas, vec![root.event_hash]);
515    }
516
517    #[test]
518    fn all_lcas_disjoint() {
519        let root_a = make_root(1_000, "agent-a");
520        let root_b = make_root(1_100, "agent-b");
521        let dag = EventDag::from_events(&[root_a.clone(), root_b.clone()]);
522
523        let lcas = find_all_lcas(&dag, &root_a.event_hash, &root_b.event_hash).unwrap();
524        assert!(lcas.is_empty());
525    }
526
527    #[test]
528    fn all_lcas_event_not_found() {
529        let dag = EventDag::new();
530        let err = find_all_lcas(&dag, "blake3:nope", "blake3:also-nope").unwrap_err();
531        assert!(matches!(err, LcaError::EventNotFound(_)));
532    }
533}
bones_core/dag/lca.rs

bones_core/dag/
lca.rs
