oo_ide/editor/

history.rs

use std::ops::Range;
use std::time::{Duration, Instant};

use crate::editor::buffer::Version;
use crate::editor::position::Position;
use crate::editor::selection::Selection;

const DEFAULT_MERGE_THRESHOLD_MS: u64 = 500;
const MAX_HISTORY_SIZE: usize = 1000;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ChangeKind {
    InsertText,
    DeleteText,
    Paste,
    Replace,
    CursorMove,
    Structural,
}

#[derive(Debug, Clone)]
pub enum BufferOp {
    Replace {
        range: Range<Position>,
        text: String,
        old_text: String,
        end_position: Position,
    },
    MoveCursor {
        position: Position,
    },
    SetSelection {
        selection: Option<Selection>,
    },
}

impl BufferOp {
    pub fn invert(&self) -> BufferOp {
        match self {
            BufferOp::Replace {
                range,
                text,
                old_text,
                end_position,
            } => {
                // Inverse: replace range.start..*end_position with old_text.
                BufferOp::Replace {
                    range: range.start..*end_position,
                    text: old_text.clone(),
                    old_text: text.clone(),
                    end_position: range.start,
                }
            }
            BufferOp::MoveCursor { position } => BufferOp::MoveCursor {
                position: *position,
            },
            BufferOp::SetSelection { selection } => BufferOp::SetSelection {
                selection: *selection,
            },
        }
    }
}

#[derive(Debug, Clone)]
pub struct ChangeSet {
    pub ops: Vec<BufferOp>,
    pub before_cursor: Position,
    pub after_cursor: Position,
    pub before_selection: Option<Selection>,
    pub after_selection: Option<Selection>,
}

impl ChangeSet {
    pub fn new(
        ops: Vec<BufferOp>,
        before_cursor: Position,
        after_cursor: Position,
        before_selection: Option<Selection>,
        after_selection: Option<Selection>,
    ) -> Self {
        Self {
            ops,
            before_cursor,
            after_cursor,
            before_selection,
            after_selection,
        }
    }

    pub fn invert(&self) -> ChangeSet {
        let inverse_ops: Vec<BufferOp> = self.ops.iter().rev().map(|op| op.invert()).collect();

        ChangeSet {
            ops: inverse_ops,
            before_cursor: self.after_cursor,
            after_cursor: self.before_cursor,
            before_selection: self.after_selection,
            after_selection: self.before_selection,
        }
    }

    pub fn is_empty(&self) -> bool {
        self.ops.is_empty()
    }

    pub fn extend(&mut self, other: &mut ChangeSet) {
        self.ops.append(&mut other.ops);
        self.after_cursor = other.after_cursor;
        self.after_selection = other.after_selection;
    }
}

#[derive(Debug, Clone)]
pub struct HistoryNode {
    pub id: u64,
    pub change: ChangeSet,
    pub inverse: ChangeSet,
    pub kind: ChangeKind,
    pub timestamp: Instant,
    pub version: Version,
}

#[derive(Debug)]
pub struct History {
    timeline: Vec<HistoryNode>,
    cursor: usize,
    merge_threshold: Duration,
    next_id: u64,
}

impl History {
    pub fn new() -> Self {
        Self {
            timeline: Vec::new(),
            cursor: 0,
            merge_threshold: Duration::from_millis(DEFAULT_MERGE_THRESHOLD_MS),
            next_id: 1,
        }
    }

    pub fn with_threshold(merge_threshold_ms: u64) -> Self {
        Self {
            timeline: Vec::new(),
            cursor: 0,
            merge_threshold: Duration::from_millis(merge_threshold_ms),
            next_id: 1,
        }
    }

    pub fn can_undo(&self) -> bool {
        self.cursor > 0
    }

    pub fn can_redo(&self) -> bool {
        self.cursor < self.timeline.len()
    }

    pub fn push(&mut self, change: ChangeSet, kind: ChangeKind, version: Version) {
        let id = self.next_id;
        self.next_id += 1;

        let inverse = change.invert();
        let timestamp = Instant::now();

        let node = HistoryNode {
            id,
            change,
            inverse,
            kind,
            timestamp,
            version,
        };

        if self.cursor < self.timeline.len() {
            self.timeline.truncate(self.cursor);
        }

        self.timeline.push(node);
        self.cursor += 1;

        if self.timeline.len() > MAX_HISTORY_SIZE {
            self.timeline.remove(0);
            self.cursor = self.cursor.saturating_sub(1);
        }
    }

    pub fn try_merge(&mut self, new_change: ChangeSet, kind: ChangeKind, version: Version) -> bool {
        if self.timeline.is_empty() || self.cursor == 0 {
            return false;
        }

        let last_idx = self.cursor - 1;
        let last_node = &self.timeline[last_idx];

        if last_node.kind != kind {
            return false;
        }

        if last_node.timestamp.elapsed() > self.merge_threshold {
            return false;
        }

        if !can_merge_changes(&last_node.change, &new_change, kind) {
            return false;
        }

        let last_node = &mut self.timeline[last_idx];
        last_node.change.extend(&mut new_change.clone());
        last_node.inverse = last_node.change.invert();
        last_node.version = version;

        true
    }

    pub fn undo(&mut self) -> Option<&HistoryNode> {
        if !self.can_undo() {
            return None;
        }

        self.cursor -= 1;
        Some(&self.timeline[self.cursor])
    }

    pub fn redo(&mut self) -> Option<&HistoryNode> {
        if !self.can_redo() {
            return None;
        }

        let node = &self.timeline[self.cursor];
        self.cursor += 1;
        Some(node)
    }

    pub fn clear(&mut self) {
        self.timeline.clear();
        self.cursor = 0;
    }

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

    pub fn is_empty(&self) -> bool {
        self.timeline.is_empty()
    }

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

    pub fn restore_from_snapshots(
        &mut self,
        undo_stack: Vec<super::buffer::SerializableSnapshot>,
        redo_stack: Vec<super::buffer::SerializableSnapshot>,
        _current_version: super::buffer::Version,
    ) {
        self.timeline.clear();
        let undo_count = undo_stack.len();
        self.cursor = undo_count;
        self.next_id = 1;

        for (i, snapshot) in undo_stack.into_iter().enumerate() {
            let change = ChangeSet::new(
                vec![],
                Position::new(0, 0),
                snapshot.cursor(),
                snapshot.selection(),
                None,
            );
            let inverse = ChangeSet::new(
                vec![],
                snapshot.cursor(),
                Position::new(0, 0),
                None,
                snapshot.selection(),
            );
            self.timeline.push(HistoryNode {
                id: i as u64 + 1,
                change,
                inverse,
                kind: ChangeKind::Structural,
                timestamp: Instant::now(),
                version: snapshot.version(),
            });
            self.next_id = (i as u64 + 2).max(self.next_id);
        }

        for snapshot in redo_stack {
            let change = ChangeSet::new(
                vec![],
                Position::new(0, 0),
                snapshot.cursor(),
                snapshot.selection(),
                None,
            );
            let inverse = ChangeSet::new(
                vec![],
                snapshot.cursor(),
                Position::new(0, 0),
                None,
                snapshot.selection(),
            );
            self.timeline.push(HistoryNode {
                id: self.next_id,
                change,
                inverse,
                kind: ChangeKind::Structural,
                timestamp: Instant::now(),
                version: snapshot.version(),
            });
            self.next_id += 1;
        }
    }
}

impl Default for History {
    fn default() -> Self {
        Self::new()
    }
}

fn can_merge_changes(a: &ChangeSet, b: &ChangeSet, kind: ChangeKind) -> bool {
    if a.after_cursor != b.before_cursor || a.after_selection != b.before_selection {
        return false;
    }

    match kind {
        ChangeKind::InsertText => can_merge_op(a, b, true),
        ChangeKind::DeleteText => can_merge_op(a, b, false),
        _ => false,
    }
}

fn can_merge_op(a: &ChangeSet, b: &ChangeSet, is_insert: bool) -> bool {
    // The new change must be a single-op edit.  The existing entry may already hold
    // multiple ops from prior merges, so we only require it to be non-empty and
    // check its *last* op for adjacency.
    if a.ops.is_empty() || b.ops.len() != 1 {
        return false;
    }

    let last_op_a = &a.ops[a.ops.len() - 1];
    let op_b = &b.ops[0];

    match (last_op_a, op_b) {
        (
            BufferOp::Replace {
                range: ra,
                text: ta,
                old_text: oa,
                end_position: ea,
            },
            BufferOp::Replace {
                range: rb,
                text: tb,
                old_text: ob,
                ..
            },
        ) => {
            if is_insert {
                // For insert: old_text must be empty, and new text can't span lines.
                if !oa.is_empty() || !ob.is_empty() {
                    return false;
                }
                if ta.contains('\n') || tb.contains('\n') {
                    return false;
                }
                *ea == rb.start
            } else {
                // For delete: new text must be empty, and old text can't span lines.
                if !ta.is_empty() || !tb.is_empty() {
                    return false;
                }
                if oa.contains('\n') || ob.contains('\n') {
                    return false;
                }
                rb.end == ra.start
            }
        }
        _ => false,
    }
}

pub fn apply_changeset(buffer: &mut crate::editor::buffer::Buffer, cs: &ChangeSet) {
    for op in &cs.ops {
        apply_op(buffer, op);
    }

    buffer.set_cursor(cs.after_cursor);
    buffer.normalize_cursor();
    buffer.set_selection(cs.after_selection);
}

fn apply_op(buffer: &mut crate::editor::buffer::Buffer, op: &BufferOp) {
    buffer.apply_op_without_history(op);
}

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

    #[test]
    fn test_changeset_invert_swaps_cursor() {
        let cs = ChangeSet::new(
            vec![],
            Position::new(1, 2),
            Position::new(3, 4),
            Some(Selection::new(Position::new(1, 2), Position::new(1, 5))),
            Some(Selection::new(Position::new(3, 4), Position::new(3, 7))),
        );

        let inv = cs.invert();

        assert_eq!(inv.before_cursor, Position::new(3, 4));
        assert_eq!(inv.after_cursor, Position::new(1, 2));
        assert_eq!(inv.before_selection.unwrap().anchor, Position::new(3, 4));
        assert_eq!(inv.after_selection.unwrap().anchor, Position::new(1, 2));
    }

    #[test]
    fn test_history_push_truncates_future() {
        let mut history = History::new();
        let cs = create_empty_changeset(Position::new(0, 0));

        history.push(cs.clone(), ChangeKind::InsertText, Version::new());
        history.push(cs.clone(), ChangeKind::InsertText, Version::new());
        assert_eq!(history.len(), 2);
        assert!(history.can_undo());
        assert!(!history.can_redo());

        history.undo();
        history.push(cs, ChangeKind::DeleteText, Version::new());
        assert_eq!(history.len(), 2);
        assert!(!history.can_redo());
    }

    #[test]
    fn test_history_undo_redo() {
        let mut history = History::new();
        let _buffer = create_test_buffer();

        let cs = create_changeset(
            Position::new(0, 0),
            Position::new(0, 5),
            vec![BufferOp::Replace {
                range: Position::new(0, 0)..Position::new(0, 0),
                text: "hello".to_string(),
                old_text: String::new(),
                end_position: Position::new(0, 5),
            }],
        );

        history.push(cs, ChangeKind::InsertText, Version::new());
        assert!(history.undo().is_some());
        assert!(history.redo().is_some());
    }

    #[test]
    fn test_try_merge_same_kind_within_threshold() {
        let mut history = History::new();

        let cs1 = create_changeset(
            Position::new(0, 0),
            Position::new(0, 1),
            vec![BufferOp::Replace {
                range: Position::new(0, 0)..Position::new(0, 1),
                text: "h".to_string(),
                old_text: String::new(),
                end_position: Position::new(0, 1),
            }],
        );

        let cs2 = create_changeset(
            Position::new(0, 1),
            Position::new(0, 2),
            vec![BufferOp::Replace {
                range: Position::new(0, 1)..Position::new(0, 2),
                text: "e".to_string(),
                old_text: String::new(),
                end_position: Position::new(0, 2),
            }],
        );

        history.push(cs1, ChangeKind::InsertText, Version::new());
        let merged = history.try_merge(cs2, ChangeKind::InsertText, Version::new());

        assert!(merged);
        assert_eq!(history.len(), 1);
    }

    #[test]
    fn test_try_merge_different_kind_fails() {
        let mut history = History::new();

        let cs1 = create_empty_changeset(Position::new(0, 0));
        let cs2 = create_empty_changeset(Position::new(0, 1));

        history.push(cs1, ChangeKind::InsertText, Version::new());
        let merged = history.try_merge(cs2, ChangeKind::DeleteText, Version::new());

        assert!(!merged);
        assert_eq!(history.len(), 1);
    }

    #[test]
    fn test_try_merge_different_cursor_fails() {
        let mut history = History::new();

        let cs1 = create_changeset(Position::new(0, 0), Position::new(0, 1), vec![]);
        let cs2 = create_changeset(Position::new(1, 0), Position::new(1, 1), vec![]);

        history.push(cs1, ChangeKind::InsertText, Version::new());
        let merged = history.try_merge(cs2, ChangeKind::InsertText, Version::new());

        assert!(!merged);
    }

    fn create_test_buffer() -> crate::editor::buffer::Buffer {
        crate::editor::buffer::Buffer::new()
    }

    fn create_empty_changeset(cursor: Position) -> ChangeSet {
        ChangeSet::new(vec![], cursor, cursor, None, None)
    }

    fn create_changeset(
        before_cursor: Position,
        after_cursor: Position,
        ops: Vec<BufferOp>,
    ) -> ChangeSet {
        ChangeSet::new(ops, before_cursor, after_cursor, None, None)
    }
}