codetree 0.1.2

AI-native version control system for autonomous agents
Documentation
//! Megamerge state + line-diff utilities.
//!
//! A *megamerge* is a working state that merges every active operation into
//! one tree, so an agent can work across operation boundaries and resolve
//! cross-operation conflicts *before* `finish` time (jj's megamerge pattern).
//!
//! The state sidecar (`.codetree/megamerge.json`) records the megamerge
//! commit, the operations it spans, and the branch to return to — the
//! megamerge commit itself lives on no branch (HEAD is detached at it, jj
//! style).

use crate::error::Result;
use serde::{Deserialize, Serialize};
use std::path::Path;

/// State of an active megamerge session.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct MegamergeState {
    /// The megamerge commit (multi-parent, detached HEAD).
    pub commit: String,
    /// Operations whose work is merged into the megamerge.
    pub operations: Vec<String>,
    /// Branch to return to when the megamerge is finished or aborted.
    pub base_branch: String,
    /// Unix timestamp (seconds).
    pub timestamp: u64,
}

impl MegamergeState {
    /// Load the megamerge state (None when no megamerge is active).
    pub fn load(root: &Path) -> Result<Option<Self>> {
        let path = root.join(".codetree").join("megamerge.json");
        if !path.exists() {
            return Ok(None);
        }
        let content = std::fs::read_to_string(&path)?;
        Ok(Some(serde_json::from_str(&content)?))
    }

    /// Save the megamerge state (atomic).
    pub fn save(&self, root: &Path) -> Result<()> {
        let path = root.join(".codetree").join("megamerge.json");
        crate::atomic::write_atomic(&path, serde_json::to_string_pretty(self)?.as_bytes())?;
        Ok(())
    }

    /// Clear the megamerge state (no-op when none exists).
    pub fn clear(root: &Path) -> Result<()> {
        let path = root.join(".codetree").join("megamerge.json");
        if path.exists() {
            std::fs::remove_file(&path)?;
        }
        Ok(())
    }
}

/// A line-level change: `old[start..end)` (1-based, end exclusive) is
/// replaced by `lines`.
#[derive(Debug, Clone, PartialEq)]
pub struct Hunk {
    /// First replaced line in the old text (1-based).
    pub start: usize,
    /// One past the last replaced line in the old text (1-based).
    pub end: usize,
    /// Replacement lines.
    pub lines: Vec<String>,
}

/// Compute line-level hunks between two texts (LCS-based).
///
/// Falls back to a whole-file replacement for very large inputs (the DP
/// table is quadratic) — correctness is preserved, precision is not.
pub fn diff_hunks(old: &[String], new: &[String]) -> Vec<Hunk> {
    let n = old.len();
    let m = new.len();
    if n * m > 1_000_000 {
        if old == new {
            return vec![];
        }
        return vec![Hunk { start: 1, end: n + 1, lines: new.to_vec() }];
    }

    // LCS length table.
    let width = m + 1;
    let mut dp = vec![0u32; (n + 1) * width];
    for i in (0..n).rev() {
        for j in (0..m).rev() {
            dp[i * width + j] = if old[i] == new[j] {
                dp[(i + 1) * width + j + 1] + 1
            } else {
                dp[(i + 1) * width + j].max(dp[i * width + j + 1])
            };
        }
    }

    // Backtrack into matching pairs.
    let mut matches: Vec<(usize, usize)> = Vec::new();
    let (mut i, mut j) = (0usize, 0usize);
    while i < n && j < m {
        if old[i] == new[j] {
            matches.push((i, j));
            i += 1;
            j += 1;
        } else if dp[(i + 1) * width + j] >= dp[i * width + j + 1] {
            i += 1;
        } else {
            j += 1;
        }
    }

    // Convert matching pairs into replacement hunks.
    let mut hunks = Vec::new();
    let mut old_i = 0usize;
    let mut new_i = 0usize;
    for (mo, mn) in &matches {
        if *mo > old_i || *mn > new_i {
            hunks.push(Hunk {
                start: old_i + 1,
                end: *mo + 1,
                lines: new[new_i..*mn].to_vec(),
            });
        }
        old_i = mo + 1;
        new_i = mn + 1;
    }
    if old_i < n || new_i < m {
        hunks.push(Hunk { start: old_i + 1, end: n + 1, lines: new[new_i..].to_vec() });
    }
    hunks
}

/// Apply hunks (in old-text coordinates) to a base text.
pub fn apply_hunks(base: &[String], hunks: &[Hunk]) -> Vec<String> {
    let mut out = Vec::new();
    let mut pos = 0usize;
    for h in hunks {
        let start = h.start.saturating_sub(1).min(base.len());
        let end = h.end.saturating_sub(1).min(base.len()).max(start);
        out.extend_from_slice(&base[pos..start]);
        out.extend_from_slice(&h.lines);
        pos = end;
    }
    out.extend_from_slice(&base[pos..]);
    out
}

#[cfg(test)]
mod tests {
    use super::*;

    fn lines(s: &str) -> Vec<String> {
        s.lines().map(|l| l.to_string()).collect()
    }

    #[test]
    fn test_diff_no_change() {
        let a = lines("a\nb\n");
        assert!(diff_hunks(&a, &a).is_empty());
    }

    #[test]
    fn test_diff_single_line_change() {
        let a = lines("a\nb\nc\n");
        let b = lines("a\nB\nc\n");
        let hunks = diff_hunks(&a, &b);
        assert_eq!(hunks.len(), 1);
        assert_eq!(hunks[0].start, 2);
        assert_eq!(hunks[0].end, 3);
        assert_eq!(hunks[0].lines, vec!["B".to_string()]);
        assert_eq!(apply_hunks(&a, &hunks), b);
    }

    #[test]
    fn test_diff_insertion_and_deletion() {
        let a = lines("a\nb\nc\n");
        let b = lines("a\nx\nb\nc\n");
        let hunks = diff_hunks(&a, &b);
        assert_eq!(apply_hunks(&a, &hunks), b);

        let c = lines("a\nc\n");
        let hunks = diff_hunks(&a, &c);
        assert_eq!(apply_hunks(&a, &hunks), c);
    }

    #[test]
    fn test_diff_appends_at_end() {
        let a = lines("a\n");
        let b = lines("a\nb\n");
        let hunks = diff_hunks(&a, &b);
        assert_eq!(apply_hunks(&a, &hunks), b);
    }
}