path: root/src/buffer/transaction.rs

//! Change sets and transactions — after Helix's `helix-core/src/transaction.rs`.
//!
//! Every buffer modification is expressed as a [`Transaction`]. Undo is not a
//! separate mechanism: it is the *inverse* transaction, computed against the
//! document as it stood before the change (MJB-HLR-011).
//!
//! All counts are **byte** lengths.

use ropey::Rope;

use super::selection::Selection;

/// MJB-LLR-040
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Operation {
    /// Leave `n` bytes untouched.
    Retain(usize),
    /// Remove `n` bytes.
    Delete(usize),
    /// Insert this text.
    Insert(String),
}

impl Operation {
    /// Bytes of the *pre-application* document this operation consumes.
    fn consumed(&self) -> usize {
        match self {
            Operation::Retain(n) | Operation::Delete(n) => *n,
            Operation::Insert(_) => 0,
        }
    }

    /// Bytes this operation contributes to the *post-application* document.
    fn produced(&self) -> usize {
        match self {
            Operation::Retain(n) => *n,
            Operation::Delete(_) => 0,
            Operation::Insert(s) => s.len(),
        }
    }
}

#[derive(Debug, thiserror::Error, PartialEq, Eq)]
pub enum ChangeError {
    #[error("change set expects a document of {expected} bytes, got {actual}")]
    LengthMismatch { expected: usize, actual: usize },
    #[error("operation boundary at byte {0} is not a character boundary")]
    NonCharBoundary(usize),
    #[error("operation at byte {0} extends past the end of the document")]
    OutOfBounds(usize),
}

/// MJB-LLR-041
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct ChangeSet {
    changes: Vec<Operation>,
    /// Document length this change set requires before application.
    len: usize,
    /// Document length after application.
    len_after: usize,
}

impl ChangeSet {
    pub fn new(rope: &Rope) -> Self {
        let len = rope.len();
        Self {
            changes: Vec::new(),
            len,
            len_after: len,
        }
    }

    pub fn from_ops(ops: Vec<Operation>) -> Self {
        let len = ops.iter().map(Operation::consumed).sum();
        let len_after = ops.iter().map(Operation::produced).sum();
        Self {
            changes: ops,
            len,
            len_after,
        }
    }

    pub fn ops(&self) -> &[Operation] {
        &self.changes
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn len_after(&self) -> usize {
        self.len_after
    }

    pub fn is_empty(&self) -> bool {
        self.changes
            .iter()
            .all(|op| matches!(op, Operation::Retain(_)))
    }

    /// MJB-LLR-042, MJB-LLR-043, MJB-LLR-044: apply to `rope`.
    ///
    /// Validation runs to completion *before* any mutation, so a rejected
    /// change set leaves the rope untouched rather than half-applied.
    pub fn apply(&self, rope: &mut Rope) -> Result<(), ChangeError> {
        // MJB-LLR-042
        if rope.len() != self.len {
            return Err(ChangeError::LengthMismatch {
                expected: self.len,
                actual: rope.len(),
            });
        }

        // MJB-LLR-044: verify every boundary first. ropey panics on a non-char
        // boundary, and a panic is not an acceptable failure mode (MJB-DR-002).
        let mut probe = 0usize;
        for op in &self.changes {
            if !rope.is_char_boundary(probe) {
                return Err(ChangeError::NonCharBoundary(probe));
            }
            probe += op.consumed();
            if probe > rope.len() {
                return Err(ChangeError::OutOfBounds(probe));
            }
        }
        if !rope.is_char_boundary(probe) {
            return Err(ChangeError::NonCharBoundary(probe));
        }

        // MJB-LLR-043: apply front-to-back in a single pass.
        //
        // `pos` tracks the cursor in the *output*, which is what makes this
        // work without buffering the edits or walking backwards: `Retain`
        // advances over text present in both images, `Delete` removes at `pos`
        // and so leaves it pointing at the next surviving byte, and `Insert`
        // advances past what it added. Later offsets therefore stay valid as
        // the rope shifts beneath them.
        let mut pos = 0usize;
        for op in &self.changes {
            match op {
                Operation::Retain(n) => pos += n,
                Operation::Delete(n) => rope.remove(pos..pos + n),
                Operation::Insert(s) => {
                    rope.insert(pos, s);
                    pos += s.len();
                }
            }
        }

        debug_assert_eq!(rope.len(), self.len_after);
        Ok(())
    }

    /// MJB-LLR-045: the change set that undoes this one.
    ///
    /// MJB-LLR-046: applying this change set and then its inverse reproduces
    /// the original contents exactly — the property undo rests on.
    ///
    /// `original` must be the document as it stood *before* this change set was
    /// applied — deleted text is recovered from it.
    pub fn invert(&self, original: &Rope) -> ChangeSet {
        let mut ops = Vec::with_capacity(self.changes.len());
        let mut pos = 0usize;

        for op in &self.changes {
            match op {
                Operation::Retain(n) => {
                    ops.push(Operation::Retain(*n));
                    pos += n;
                }
                Operation::Delete(n) => {
                    let text: String = original.slice(pos..pos + n).chunks().collect();
                    ops.push(Operation::Insert(text));
                    pos += n;
                }
                Operation::Insert(s) => ops.push(Operation::Delete(s.len())),
            }
        }

        ChangeSet {
            changes: ops,
            len: self.len_after,
            len_after: self.len,
        }
    }
}

/// MJB-LLR-047: a change set plus the selection that should result from it.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Transaction {
    pub changes: ChangeSet,
    pub selection: Option<Selection>,
}

impl Transaction {
    pub fn new(changes: ChangeSet) -> Self {
        Self {
            changes,
            selection: None,
        }
    }

    pub fn with_selection(mut self, selection: Selection) -> Self {
        self.selection = Some(selection);
        self
    }

    /// MJB-LLR-048: build from `(from, to, Option<text>)` triples, which must
    /// arrive ordered by ascending `from` and must not overlap.
    pub fn change<I>(rope: &Rope, changes: I) -> Self
    where
        I: IntoIterator<Item = (usize, usize, Option<String>)>,
    {
        let mut ops = Vec::new();
        let mut pos = 0usize;

        for (from, to, text) in changes {
            if from > pos {
                ops.push(Operation::Retain(from - pos));
            }
            if to > from {
                ops.push(Operation::Delete(to - from));
            }
            if let Some(s) = text
                && !s.is_empty()
            {
                ops.push(Operation::Insert(s));
            }
            pos = to.max(from);
        }

        let len = rope.len();
        if pos < len {
            ops.push(Operation::Retain(len - pos));
        }

        Self::new(ChangeSet::from_ops(ops))
    }

    /// MJB-LLR-049: insert `text` at the selection's cursor.
    pub fn insert(rope: &Rope, selection: &Selection, text: &str) -> Self {
        let at = selection.primary().cursor(rope.slice(..));
        Self::change(rope, [(at, at, Some(text.to_owned()))])
    }

    /// MJB-LLR-050: delete the selection's primary span.
    pub fn delete(rope: &Rope, selection: &Selection) -> Self {
        let r = selection.primary();
        Self::change(rope, [(r.from(), r.to(), None)])
    }
}

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

    fn rope(s: &str) -> Rope {
        Rope::from_str(s)
    }

    /// MJB-LLR-040: operation counts are byte lengths, so a multi-byte
    /// character contributes its byte width.
    #[test]
    fn mjb_llr_040_operation_counts_are_byte_lengths() {
        let insert = Operation::Insert("文".to_owned());
        assert_eq!(insert.produced(), 3, "one character, three bytes");
        assert_eq!(insert.consumed(), 0, "an insert consumes no input");

        assert_eq!(Operation::Retain(4).consumed(), 4);
        assert_eq!(Operation::Retain(4).produced(), 4);
        assert_eq!(Operation::Delete(4).consumed(), 4);
        assert_eq!(Operation::Delete(4).produced(), 0);
    }

    /// MJB-LLR-041: `len` is the required pre-image length, `len_after` the
    /// post-image length.
    #[test]
    fn mjb_llr_041_changeset_records_both_lengths() {
        let r = rope("abcdef");
        // Replace two bytes with three.
        let t = Transaction::change(&r, [(1, 3, Some("XYZ".into()))]);
        assert_eq!(t.changes.len(), 6, "must match the source document");
        assert_eq!(t.changes.len_after(), 7, "6 - 2 + 3");

        let mut m = r.clone();
        t.changes.apply(&mut m).unwrap();
        assert_eq!(m.len(), t.changes.len_after());
    }

    #[test]
    fn mjb_llr_041_empty_changeset_reports_equal_lengths() {
        let r = rope("abc");
        let cs = ChangeSet::new(&r);
        assert_eq!(cs.len(), 3);
        assert_eq!(cs.len_after(), 3);
        assert!(cs.is_empty());
    }

    /// MJB-LLR-047: a transaction carries the selection that should result.
    #[test]
    fn mjb_llr_047_transaction_carries_a_selection() {
        use super::super::selection::Range;
        let r = rope("abcdef");
        let t = Transaction::change(&r, [(0, 1, None)]);
        assert_eq!(t.selection, None, "none by default");

        let sel = Selection::single(Range::new(0, 2));
        let t = t.with_selection(sel.clone());
        assert_eq!(t.selection, Some(sel));
    }

    #[test]
    fn mjb_llr_043_apply_insert_and_delete() {
        let mut r = rope("hello world");
        let t = Transaction::change(&r, [(0, 5, Some("goodbye".into()))]);
        t.changes.apply(&mut r).unwrap();
        assert_eq!(r.to_string(), "goodbye world");
    }

    #[test]
    fn mjb_llr_042_length_mismatch_is_rejected() {
        let r = rope("abcdef");
        let t = Transaction::change(&r, [(0, 1, None)]);
        let mut other = rope("shorter than expected? no — different");
        let err = t.changes.apply(&mut other).unwrap_err();
        assert!(matches!(err, ChangeError::LengthMismatch { .. }));
    }

    #[test]
    fn mjb_llr_042_rejected_change_leaves_rope_untouched() {
        let r = rope("abcdef");
        let t = Transaction::change(&r, [(0, 3, Some("xyz".into()))]);
        let mut other = rope("12345678");
        let before = other.to_string();
        assert!(t.changes.apply(&mut other).is_err());
        assert_eq!(other.to_string(), before, "must not partially apply");
    }

    #[test]
    fn mjb_llr_044_non_char_boundary_errors_rather_than_panics() {
        // Split "文" (3 bytes) after its first byte.
        let mut r = rope("文");
        let cs = ChangeSet::from_ops(vec![Operation::Retain(1), Operation::Delete(2)]);
        let err = cs.apply(&mut r).unwrap_err();
        assert_eq!(err, ChangeError::NonCharBoundary(1));
        assert_eq!(r.to_string(), "文", "rope must be unchanged");
    }

    #[test]
    fn mjb_llr_045_invert_maps_each_operation() {
        let r = rope("abcdef");
        let t = Transaction::change(&r, [(1, 3, Some("XY".into()))]);
        let inv = t.changes.invert(&r);
        // Delete(2) became Insert("bc"); Insert("XY") became Delete(2).
        assert!(inv.ops().contains(&Operation::Insert("bc".into())));
        assert!(inv.ops().contains(&Operation::Delete(2)));
    }

    #[test]
    fn mjb_llr_046_apply_then_invert_round_trips() {
        for (text, from, to, ins) in [
            ("hello world", 0usize, 5usize, Some("goodbye")),
            ("hello world", 5, 11, None),
            ("", 0, 0, Some("new")),
            ("文字化け", 0, 3, Some("X")),
            ("no trailing newline", 3, 3, Some(" inserted")),
        ] {
            let original = rope(text);
            let mut r = original.clone();
            let t = Transaction::change(&r, [(from, to, ins.map(str::to_owned))]);
            let inverse = t.changes.invert(&original);

            t.changes.apply(&mut r).unwrap();
            inverse.apply(&mut r).unwrap();

            assert_eq!(
                r.to_string(),
                original.to_string(),
                "round trip failed for {text:?}"
            );
        }
    }

    #[test]
    fn mjb_llr_048_multiple_ordered_changes() {
        let mut r = rope("aaa bbb ccc");
        let t = Transaction::change(&r, [(0, 3, Some("XXX".into())), (8, 11, Some("ZZZ".into()))]);
        t.changes.apply(&mut r).unwrap();
        assert_eq!(r.to_string(), "XXX bbb ZZZ");
    }

    #[test]
    fn mjb_llr_049_insert_at_cursor() {
        let r = rope("ab");
        let sel = Selection::point(1);
        let mut m = r.clone();
        Transaction::insert(&r, &sel, "X")
            .changes
            .apply(&mut m)
            .unwrap();
        assert_eq!(m.to_string(), "aXb");
    }

    #[test]
    fn mjb_llr_050_delete_selection_span() {
        use super::super::selection::Range;
        let r = rope("abcdef");
        let sel = Selection::single(Range::new(1, 4));
        let mut m = r.clone();
        Transaction::delete(&r, &sel)
            .changes
            .apply(&mut m)
            .unwrap();
        assert_eq!(m.to_string(), "aef");
    }

    #[test]
    fn empty_document_accepts_insert() {
        let mut r = rope("");
        let t = Transaction::change(&r, [(0, 0, Some("x".into()))]);
        t.changes.apply(&mut r).unwrap();
        assert_eq!(r.to_string(), "x");
    }
}