Timeline Merge Strategies

ELI5

Merging timelines is like combining two shopping lists. Canonical keeps everything from both lists with no duplicates. KeepBranches hands you back the branch list unchanged. Manual throws the lists at you and says “you decide” — which fails if nobody’s home to catch them.

Technical Deep Dive

MergeStrategy Enum

pub enum MergeStrategy {
    Canonical,     // first-write-wins union; default
    KeepBranches,  // return branch nodes unmodified
    Manual,        // returns Err immediately
}

TimelineMerger::new() selects Canonical. Use TimelineMerger::with_strategy(s) to override.

Merge Dispatch

flowchart TD
    CALL["merger.merge(canonical, branch)"]
    CALL --> SW{MergeStrategy}
    SW -- Canonical --> MC["merge_canonical:\ncanonical.nodes.clone()\n+ branch nodes not in canonical"]
    SW -- KeepBranches --> KB["return branch.nodes.clone()"]
    SW -- Manual --> ERR["Err('Manual merge requires user decision')"]
    MC --> OK["Ok(Vec<NodeID>)"]
    KB --> OK

merge_canonical Detail

fn merge_canonical(&self, canonical: &Timeline, branch: &Timeline) -> Result<Vec<NodeID>, String> {
    let mut merged = canonical.nodes.clone();
    for node in &branch.nodes {
        if !merged.contains(node) {
            merged.push(node.clone());
        }
    }
    Ok(merged)
}

• Output preserves canonical ordering first; branch-exclusive nodes appended in branch insertion order.
• Uses Vec::contains (O(n) per check); no hash-set acceleration. For large timelines this is O(|canonical| × |branch|).
• Does not modify either input timeline — the merged list is returned; callers own re-insertion.

Diff Operation

sequenceDiagram
    participant Caller
    participant TimelineMerger as Merger
    participant Canonical as Canonical Timeline
    participant Branch as Branch Timeline

    Caller->>Merger: diff(canonical, branch)
    Merger->>Canonical: iterate nodes
    Merger->>Branch: iterate nodes
    Merger-->>Caller: (only_canonical: Vec<NodeID>, only_branch: Vec<NodeID>)

diff returns a two-tuple:

• only_canonical: nodes in canonical but not branch
• only_branch: nodes in branch but not canonical

The intersection (shared nodes) is not returned explicitly.

Key Terms

• MergeStrategy → three-variant enum selecting merge behaviour
• merge_canonical → union of canonical and branch nodes, canonical-ordered, no duplicates
• KeepBranches → no-op merge; returns branch node list verbatim
• diff → symmetric difference split into two vecs; does not mutate state

Q&A

Q: If the branch is a strict prefix of canonical, what does merge_canonical return? A: A clone of canonical’s nodes — the branch adds nothing new and the contains check filters every branch node.

Q: Does TimelineMerger::merge mutate the canonical Timeline? A: No. Both canonical and branch are borrowed as &Timeline. The result is a fresh Vec<NodeID> that callers can use to rebuild or extend a timeline.

Q: Is there a three-way merge (base, canonical, branch)? A: Not in the current source. merge takes exactly two timelines; no common-ancestor base is used.

Examples

let merger = TimelineMerger::new(); // Canonical strategy
let result = merger.merge(&canonical, &branch).unwrap();
// result = canonical.nodes ++ branch-exclusive nodes

let manual = TimelineMerger::with_strategy(MergeStrategy::Manual);
let err = manual.merge(&canonical, &branch);
assert!(err.is_err());

let (only_c, only_b) = merger.diff(&canonical, &branch);
// only_c: nodes canonical has that branch lacks
// only_b: nodes branch has that canonical lacks