codetree 0.2.0

AI-native version control system for autonomous agents
Documentation
//! Convergence of divergent commits (jj-style `jj converge`).
//!
//! When two agents work the *same* operation, their commits can diverge:
//! both are children of the same tip, but only one of them is on the branch
//! ref. The other agent's commit is orphaned — invisible in `smartlog`,
//! invisible in `finish`, and easy to lose.
//!
//! `converge` finds those divergent heads (via the provenance sidecar, which
//! maps every commit to the operation that produced it) and combines them
//! into a single merge commit with two parents, then re-points the
//! operation's branch at it. Nothing is rewritten and no commit is
//! discarded — the divergent work is *combined*, not dropped.
//!
//! Like every other conflict path in CodeTree, convergence never aborts a
//! merge on conflict: when the divergent commits cannot be combined
//! cleanly, the operation is left untouched and the conflicting files are
//! reported for the agent to resolve.

use crate::error::{Context, Result};
use crate::resolution::ConflictInfo;
use std::collections::HashSet;

use super::objects::{Commit, Tree};
use super::manager::VcsManager;

/// Outcome of a convergence attempt.
#[derive(Debug)]
pub struct ConvergeOutcome {
    /// The converged commit (None when nothing was converged).
    pub commit: Option<String>,
    /// Files that could not be combined cleanly (empty on success).
    pub conflicts: Vec<ConflictInfo>,
}

impl VcsManager {
    /// All ancestors of a commit, including the commit itself.
    pub fn ancestor_set(&self, commit: &str) -> Result<HashSet<String>> {
        let mut seen = HashSet::new();
        let mut stack = vec![commit.to_string()];
        while let Some(id) = stack.pop() {
            if !seen.insert(id.clone()) {
                continue;
            }
            if let Ok(c) = self.repo.read_commit(&id) {
                for p in &c.parents {
                    stack.push(p.clone());
                }
            }
        }
        Ok(seen)
    }

    /// Heads among a set of commits: those that are not an ancestor of any
    /// other commit in the set. More than one head means divergence.
    pub fn commit_heads(&self, commits: &[String]) -> Result<Vec<String>> {
        let mut heads: Vec<String> = Vec::new();
        for c in commits {
            // A head is a commit no other candidate descends from.
            let covered_by_other = commits.iter().any(|other| {
                other != c && self.ancestor_set(other).map(|a| a.contains(c)).unwrap_or(false)
            });
            if !covered_by_other {
                heads.push(c.clone());
            }
        }
        heads.sort();
        heads.dedup();
        Ok(heads)
    }

    /// Collapse heads that carry the same tree.
    ///
    /// A rewrite (`reword`, `squash`) replaces a commit with a new id that
    /// has the *same content* — the old id is then a sibling of the new one
    /// and would look like divergence. Heads with identical trees are
    /// versions of the same change: keep the newest, drop the rest.
    pub fn dedupe_heads_by_tree(&self, heads: &[String]) -> Result<Vec<String>> {
        let mut unique: Vec<(String, String, u64)> = Vec::new(); // (commit, tree, timestamp)
        for h in heads {
            let c = self.repo.read_commit(h)?;
            match unique.iter_mut().find(|(_, tree, _)| *tree == c.tree) {
                Some(existing) => {
                    if c.timestamp >= existing.2 {
                        existing.0 = h.clone();
                        existing.2 = c.timestamp;
                    }
                }
                None => unique.push((h.clone(), c.tree.clone(), c.timestamp)),
            }
        }
        let mut out: Vec<String> = unique.into_iter().map(|(c, _, _)| c).collect();
        out.sort();
        Ok(out)
    }

    /// Combine divergent heads into a single commit.
    ///
    /// Two heads → one merge commit with two parents. More than two heads
    /// are combined pairwise (the result is a chain of merge commits, each
    /// with two parents). If any step conflicts, nothing is written and the
    /// conflicting files are returned.
    pub fn converge_heads(&self, heads: &[String]) -> Result<ConvergeOutcome> {
        let heads = self.dedupe_heads_by_tree(heads)?;
        if heads.len() < 2 {
            return Ok(ConvergeOutcome { commit: None, conflicts: vec![] });
        }

        let mut current = heads[0].clone();
        for next in &heads[1..] {
            let base = self.find_merge_base(&current, next)?;
            let base_tree = self.commit_tree(&base)?;
            let our_tree = self.commit_tree(&current)?;
            let their_tree = self.commit_tree(next)?;

            let (merged_entries, conflicts) = self.merge_trees(&base_tree, &our_tree, &their_tree)?;
            if !conflicts.is_empty() {
                // Cannot combine cleanly — leave everything untouched and
                // report the conflicting files (jj's non-interactive abort).
                return Ok(ConvergeOutcome { commit: None, conflicts });
            }

            let tree = Tree::new(merged_entries);
            let tree_id = self.repo.write_tree(&tree)?;
            let timestamp = std::time::SystemTime::now()
                .duration_since(std::time::UNIX_EPOCH)
                .map(|d| d.as_secs())
                .unwrap_or(0);
            let commit = Commit::new(
                tree_id,
                vec![current.clone(), next.clone()],
                "CodeTree <agent@codetree>".to_string(),
                format!("Converge divergent commits ({} and {})", &current[..7.min(current.len())], &next[..7.min(next.len())]),
                timestamp,
            );
            current = self.repo.write_commit(&commit)?;
        }

        Ok(ConvergeOutcome { commit: Some(current), conflicts: vec![] })
    }

    /// Point a branch at a commit (used to re-point an operation after
    /// convergence).
    pub fn set_branch_tip(&self, branch: &str, commit: &str) -> Result<()> {
        self.repo.refs().set_branch(branch, commit)
    }

    /// Read a commit's parents (helper for reporting).
    pub fn commit_parents(&self, commit: &str) -> Result<Vec<String>> {
        let c = self
            .repo
            .read_commit(&commit.to_string())
            .with_context(|| format!("Commit '{}' not found", commit))?;
        Ok(c.parents)
    }
}