Struct PatchDag 

pub struct PatchDag { /* private fields */ }

The Patch-DAG — a directed acyclic graph of patches.

Internally stores:

• A HashMap of PatchId -> DagNode
• A HashMap of branch name -> target PatchId
• An ancestor cache (lazy, stable across mutations since adding new nodes never changes existing nodes’ ancestor sets)

Implementations

impl PatchDag

pub fn branch_exists(&self, name: &BranchName) -> bool

Check if a branch exists.

pub fn head(&self) -> Option<(String, PatchId)>

Get the current HEAD branch (the branch named “main”, or the first branch).

pub fn branch_divergence( &self, branch_a: &BranchName, branch_b: &BranchName, ) -> Result<(usize, usize), DagError>

Get the number of commits ahead/behind between two branches.

Returns (ahead, behind) where:

• ahead is the number of patches on branch_a since the LCA
• behind is the number of patches on branch_b since the LCA

Computed by finding the Lowest Common Ancestor (LCA) and counting patches on each branch’s chain between the LCA and the branch tip.

impl PatchDag

pub fn new() -> Self

Create a new empty DAG.

pub fn add_patch( &mut self, patch: Patch, parent_ids: Vec<PatchId>, ) -> Result<PatchId, DagError>

Add a patch to the DAG.

Arguments

• patch - The patch to add
• parent_ids - Parent patch IDs (empty for root commit)

Errors

• DuplicatePatch if a patch with the same ID already exists
• ParentNotFound if a parent doesn’t exist (unless it’s a root commit)
• CycleDetected if adding this edge would create a cycle

pub fn get_patch(&self, id: &PatchId) -> Option<&Patch>

Get a patch by ID.

pub fn get_node(&self, id: &PatchId) -> Option<&DagNode>

Get a node by ID.

pub fn has_patch(&self, id: &PatchId) -> bool

Check if a patch exists.

pub fn ancestors(&self, id: &PatchId) -> HashSet<PatchId>

Get all transitive ancestors of a patch (excluding the patch itself).

Uses BFS traversal. Results are cached: the first call for a given patch ID computes the ancestor set via BFS; subsequent calls return the cached result in O(1). The cache is safe without invalidation because add_patch() only creates new nodes — existing nodes’ ancestor sets never change.

pub fn lca(&self, a: &PatchId, b: &PatchId) -> Option<PatchId>

Find the Lowest Common Ancestor (LCA) of two patches.

The LCA is the most recent patch that is an ancestor of both. Returns None if no common ancestor exists.

Uses generation numbers for O(1) depth comparison instead of BFS-based ancestor_depth(), reducing complexity from O(n²) to O(n).

pub fn create_branch( &mut self, name: BranchName, target: PatchId, ) -> Result<(), DagError>

Create a new branch pointing to a patch.

pub fn get_branch(&self, name: &BranchName) -> Option<PatchId>

Get the target patch ID of a branch.

pub fn update_branch( &mut self, name: &BranchName, target: PatchId, ) -> Result<(), DagError>

Update a branch to point to a new patch.

pub fn delete_branch(&mut self, name: &BranchName) -> Result<(), DagError>

Delete a branch.

pub fn list_branches(&self) -> Vec<(String, PatchId)>

List all branches.

pub fn patch_count(&self) -> usize

Get the total number of patches in the DAG.

pub fn patch_ids(&self) -> Vec<PatchId>

Get all patch IDs in the DAG.

pub fn patch_chain(&self, id: &PatchId) -> Vec<PatchId>

Get patches from a specific node back to root (inclusive).

pub fn reachable_patches(&self, id: &PatchId) -> Vec<Patch>

Collect all patches reachable from a given patch ID (inclusive).

impl PatchDag

pub fn merge_branches( &self, branch_a: &BranchName, branch_b: &BranchName, ) -> Result<MergeResult, DagError>

Compute a merge plan for two branches.

Returns a MergeResult containing the patches to merge and any conflicts. This does NOT modify the DAG — it only computes the plan.

Trait Implementations

impl Default for PatchDag

fn default() -> Self

Returns the “default value” for a type.