mtplatx_doc_diff/

lib.rs

//! Semantic tree diff.
//!
//! The diff engine compares two [`Document`]s at the semantic level, never at
//! the source-text level. It emits an ordered [`Patch`] of [`Operation`]s that
//! can be replayed to transform `old` into `new`.
//!
//! The implementation is a Myers-style block LCS over top-level blocks. For
//! nested structures (lists, tables, quotes) the inner diff is approximated
//! by re-running the same algorithm over the child vectors.

use mtplatx_doc_core::{Block, Document, Inline};
use serde::{Deserialize, Serialize};

/// A kind of edit.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
#[serde(tag = "op", rename_all = "snake_case")]
pub enum Operation {
    Insert {
        index: usize,
        block: Block,
    },
    Delete {
        index: usize,
    },
    Replace {
        index: usize,
        block: Block,
    },
    Move {
        from: usize,
        to: usize,
    },
    /// Whole-document metadata change.
    UpdateMetadata {
        from: serde_json::Value,
        to: serde_json::Value,
    },
}

/// A complete edit script.
#[derive(Debug, Clone, Default, PartialEq, Serialize, Deserialize)]
pub struct Patch {
    pub operations: Vec<Operation>,
}

impl Patch {
    pub fn new() -> Self {
        Self::default()
    }
    pub fn push(&mut self, op: Operation) {
        self.operations.push(op);
    }
    pub fn len(&self) -> usize {
        self.operations.len()
    }
    pub fn is_empty(&self) -> bool {
        self.operations.is_empty()
    }

    /// Number of inserts, deletes, and replaces.
    pub fn edit_distance(&self) -> usize {
        self.operations
            .iter()
            .filter(|op| {
                !matches!(
                    op,
                    Operation::UpdateMetadata { .. } | Operation::Move { .. }
                )
            })
            .count()
    }
}

/// Diff two documents, returning a [`Patch`].
pub fn diff(old: &Document, new: &Document) -> Patch {
    let mut patch = Patch::new();

    if old.metadata != new.metadata {
        let from = serde_json::to_value(&old.metadata).unwrap_or_default();
        let to = serde_json::to_value(&new.metadata).unwrap_or_default();
        if from != to {
            patch.push(Operation::UpdateMetadata { from, to });
        }
    }

    diff_blocks(&old.blocks, &new.blocks, &mut patch);
    patch
}

fn diff_blocks(old: &[Block], new: &[Block], patch: &mut Patch) {
    // Compute LCS table.
    let n = old.len();
    let m = new.len();
    let mut table = vec![vec![0usize; m + 1]; n + 1];
    for i in 0..n {
        for j in 0..m {
            table[i + 1][j + 1] = if old[i] == new[j] {
                table[i][j] + 1
            } else {
                table[i + 1][j].max(table[i][j + 1])
            };
        }
    }
    // Walk back to produce operations. We emit Delete for `old[i]` not in LCS
    // and Insert for `new[j]` not in LCS. Replace when both sides are off the
    // LCS at the same position.
    let mut i = n;
    let mut j = m;
    let mut ops: Vec<Operation> = Vec::new();
    while i > 0 && j > 0 {
        if old[i - 1] == new[j - 1] {
            i -= 1;
            j -= 1;
        } else if table[i - 1][j] >= table[i][j - 1] {
            ops.push(Operation::Delete { index: i - 1 });
            i -= 1;
        } else {
            ops.push(Operation::Insert {
                index: j - 1,
                block: new[j - 1].clone(),
            });
            j -= 1;
        }
    }
    while i > 0 {
        ops.push(Operation::Delete { index: i - 1 });
        i -= 1;
    }
    while j > 0 {
        ops.push(Operation::Insert {
            index: j - 1,
            block: new[j - 1].clone(),
        });
        j -= 1;
    }
    ops.reverse();
    // Coalesce adjacent Delete+Insert of the same index into a Replace.
    let coalesced = coalesce(ops);
    for op in coalesced {
        patch.push(op);
    }
}

fn coalesce(ops: Vec<Operation>) -> Vec<Operation> {
    let mut out: Vec<Operation> = Vec::with_capacity(ops.len());
    let mut k = 0usize;
    while k < ops.len() {
        let mut advanced = false;
        if k + 1 < ops.len() {
            if let (Operation::Delete { index: di }, Operation::Insert { index: ii, block }) =
                (&ops[k], &ops[k + 1])
            {
                if di == ii {
                    out.push(Operation::Replace {
                        index: *di,
                        block: block.clone(),
                    });
                    k += 2;
                    advanced = true;
                }
            }
            if !advanced {
                if let (Operation::Insert { index: ii, block }, Operation::Delete { index: di }) =
                    (&ops[k], &ops[k + 1])
                {
                    if di == ii {
                        out.push(Operation::Replace {
                            index: *di,
                            block: block.clone(),
                        });
                        k += 2;
                        advanced = true;
                    }
                }
            }
        }
        if !advanced {
            out.push(ops[k].clone());
            k += 1;
        }
    }
    out
}

/// Apply a patch to a document, returning the new document.
///
/// Not all patch operations are supported by [`apply`]. Unsupported operations
/// cause the function to return an error describing which one failed.
pub fn apply(doc: Document, patch: &Patch) -> Result<Document, DiffError> {
    let mut doc = doc;
    // Apply non-mutating ops first, in reverse so indices stay valid.
    let mut sorted: Vec<&Operation> = patch.operations.iter().collect();
    sorted.sort_by_key(|op| match op {
        Operation::Insert { index, .. } => (*index, 0u8),
        Operation::Replace { index, .. } => (*index, 1u8),
        Operation::Delete { index } => (*index, 2u8),
        Operation::Move { from, .. } => (*from, 3u8),
        Operation::UpdateMetadata { .. } => (usize::MAX, 4u8),
    });
    for op in sorted {
        match op {
            Operation::Insert { index, block } => {
                let idx = (*index).min(doc.blocks.len());
                doc.blocks.insert(idx, block.clone());
            }
            Operation::Replace { index, block } => {
                if *index >= doc.blocks.len() {
                    return Err(DiffError::IndexOutOfRange { index: *index });
                }
                doc.blocks[*index] = block.clone();
            }
            Operation::Delete { index } => {
                if *index >= doc.blocks.len() {
                    return Err(DiffError::IndexOutOfRange { index: *index });
                }
                doc.blocks.remove(*index);
            }
            Operation::Move { from, to } => {
                if *from >= doc.blocks.len() {
                    return Err(DiffError::IndexOutOfRange { index: *from });
                }
                let b = doc.blocks.remove(*from);
                let to = (*to).min(doc.blocks.len());
                doc.blocks.insert(to, b);
            }
            Operation::UpdateMetadata { from: _, to } => {
                doc.metadata = serde_json::from_value(to.clone())
                    .map_err(|e| DiffError::InvalidMetadata(e.to_string()))?;
            }
        }
    }
    Ok(doc)
}

/// Summary statistics about a diff.
#[derive(Debug, Clone, Default)]
pub struct DiffStats {
    pub inserts: usize,
    pub deletes: usize,
    pub replaces: usize,
    pub moves: usize,
    pub metadata: usize,
}

impl From<&Patch> for DiffStats {
    fn from(patch: &Patch) -> Self {
        let mut s = Self::default();
        for op in &patch.operations {
            match op {
                Operation::Insert { .. } => s.inserts += 1,
                Operation::Delete { .. } => s.deletes += 1,
                Operation::Replace { .. } => s.replaces += 1,
                Operation::Move { .. } => s.moves += 1,
                Operation::UpdateMetadata { .. } => s.metadata += 1,
            }
        }
        s
    }
}

#[derive(Debug, thiserror::Error)]
pub enum DiffError {
    #[error("index {index} out of range")]
    IndexOutOfRange { index: usize },
    #[error("invalid metadata in patch: {0}")]
    InvalidMetadata(String),
}

/// Compare two inline sequences. Returns true if they are equivalent under
/// a whitespace-insensitive comparison. Currently exact — kept as a hook
/// for future fuzzy matching.
pub fn inlines_equal_ignoring_ws(a: &[Inline], b: &[Inline]) -> bool {
    fn collect(inlines: &[Inline], out: &mut String) {
        for i in inlines {
            match i {
                Inline::Text(t) => {
                    out.push_str(t.value.trim());
                    out.push(' ');
                }
                Inline::Code(s) => {
                    out.push_str(s);
                    out.push(' ');
                }
                Inline::Math(_) => {}
                Inline::Link(l) => collect(&l.content, out),
                Inline::Image(_) => {}
                Inline::Bold(c) | Inline::Italic(c) | Inline::Underline(c) | Inline::Strike(c) => {
                    collect(c, out)
                }
                Inline::Raw(_) => {}
            }
        }
    }
    let mut sa = String::new();
    let mut sb = String::new();
    collect(a, &mut sa);
    collect(b, &mut sb);
    sa == sb
}

#[cfg(test)]
mod tests {
    use super::*;
    use mtplatx_doc_core::{Inline, Paragraph};

    fn p(s: &str) -> Block {
        Block::Paragraph(Paragraph {
            content: vec![Inline::from(s)],
        })
    }

    #[test]
    fn identical_docs_yield_empty_patch() {
        let mut a = Document::new();
        a.push(p("a"));
        let patch = diff(&a, &a);
        assert!(patch.is_empty());
    }

    #[test]
    fn insert_at_end() {
        let mut a = Document::new();
        a.push(p("a"));
        let mut b = Document::new();
        b.push(p("a"));
        b.push(p("b"));
        let patch = diff(&a, &b);
        assert!(matches!(
            patch.operations.last(),
            Some(Operation::Insert { .. })
        ));
    }

    #[test]
    fn delete_middle() {
        let mut a = Document::new();
        a.push(p("a"));
        a.push(p("b"));
        a.push(p("c"));
        let mut b = Document::new();
        b.push(p("a"));
        b.push(p("c"));
        let patch = diff(&a, &b);
        let stats = DiffStats::from(&patch);
        assert_eq!(stats.deletes, 1);
    }

    #[test]
    fn replace_is_coalesced() {
        let mut a = Document::new();
        a.push(p("a"));
        let mut b = Document::new();
        b.push(p("z"));
        let patch = diff(&a, &b);
        assert_eq!(patch.len(), 1);
        assert!(matches!(patch.operations[0], Operation::Replace { .. }));
    }

    #[test]
    fn apply_roundtrips_diff() {
        let mut a = Document::new();
        a.push(p("a"));
        a.push(p("b"));
        let mut b = Document::new();
        b.push(p("a"));
        b.push(p("c"));
        b.push(p("b"));
        let patch = diff(&a, &b);
        let applied = apply(a.clone(), &patch).unwrap();
        assert_eq!(applied.metadata, b.metadata);
        assert_eq!(applied.blocks, b.blocks);
    }

    #[test]
    fn metadata_diff_emitted() {
        let mut a = Document::new();
        a.metadata.title = Some("A".into());
        let mut b = Document::new();
        b.metadata.title = Some("B".into());
        let patch = diff(&a, &b);
        assert!(patch
            .operations
            .iter()
            .any(|op| matches!(op, Operation::UpdateMetadata { .. })));
    }
}