caretline 0.2.0

// Vendored from Helix (https://github.com/helix-editor/helix), `helix-core/src/history.rs`
// at commit ba40e547426b0f9896c8bdc699a4ab11f2b37dbc.
// SPDX-License-Identifier: MPL-2.0. This file is under the Mozilla Public License 2.0;
// see LICENSE-MPL-2.0 in the `helix` directory.
// Changes from upstream: `current_transaction` and `current_inversion` accessors; module paths; revision timestamps are caller-supplied milliseconds (`Timestamp`) instead of `std::time::Instant`, so no clock is read; removed `commit_revision` (it read the clock) and the regex-based duration parser; serde derives; added `amend_current_revision`, `len`, `is_empty`, `can_redo` and `rebase_over` (operational transform over a change made elsewhere).

use crate::helix::{Assoc, ChangeSet, Range, Rope, Selection, Transaction};
use std::num::NonZeroUsize;
use std::time::Duration;

/// A revision timestamp in milliseconds. The caller supplies it, so the history never
/// reads a clock (caretline: replaces `std::time::Instant`).
pub type Timestamp = u64;

#[derive(Debug, Clone)]
pub struct State {
    pub doc: Rope,
    pub selection: Selection,
}

/// Stores the history of changes to a buffer.
///
/// Currently the history is represented as a vector of revisions. The vector
/// always has at least one element: the empty root revision. Each revision
/// with the exception of the root has a parent revision, a [Transaction]
/// that can be applied to its parent to transition from the parent to itself,
/// and an inversion of that transaction to transition from the parent to its
/// latest child.
///
/// When using `u` to undo a change, an inverse of the stored transaction will
/// be applied which will transition the buffer to the parent state.
///
/// Each revision with the exception of the last in the vector also has a
/// last child revision. When using `U` to redo a change, the last child transaction
/// will be applied to the current state of the buffer.
///
/// The current revision is the one currently displayed in the buffer.
///
/// Committing a new revision to the history will update the last child of the
/// current revision, and push a new revision to the end of the vector.
///
/// Revisions are committed with a timestamp. :earlier and :later can be used
/// to jump to the closest revision to a moment in time relative to the timestamp
/// of the current revision plus (:later) or minus (:earlier) the duration
/// given to the command. If a single integer is given, the editor will instead
/// jump the given number of revisions in the vector.
///
/// Limitations:
///  * Changes in selections currently don't commit history changes. The selection
///    will only be updated to the state after a committed buffer change.
///  * The vector of history revisions is currently unbounded. This might
///    cause the memory consumption to grow significantly large during long
///    editing sessions.
///  * Because delete transactions currently don't store the text that they
///    delete, we also store an inversion of the transaction.
///
/// Using time to navigate the history: <https://github.com/helix-editor/helix/pull/194>
#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
pub struct History {
    revisions: Vec<Revision>,
    current: usize,
}

/// One revision kept by [`History::rebase_over`].
///
/// caretline addition: not in upstream Helix.
#[derive(Debug, Clone)]
pub struct Rebased {
    /// Its index before.
    pub old: usize,
    /// The remote change as it applies to its document before (`R_k`).
    pub remote: ChangeSet,
    /// Its document after: the old one with the remote change.
    pub text: Rope,
}

/// A single point in history. See [History] for more information.
#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
struct Revision {
    parent: usize,
    last_child: Option<NonZeroUsize>,
    transaction: Transaction,
    // We need an inversion for undos because delete transactions don't store
    // the deleted text.
    inversion: Transaction,
    timestamp: Timestamp,
}

impl Default for History {
    fn default() -> Self {
        // Add a dummy root revision with empty transaction
        Self {
            revisions: vec![Revision {
                parent: 0,
                last_child: None,
                transaction: Transaction::from(ChangeSet::new("".into())),
                inversion: Transaction::from(ChangeSet::new("".into())),
                timestamp: 0,
            }],
            current: 0,
        }
    }
}

impl History {
    pub fn commit_revision_at_timestamp(
        &mut self,
        transaction: &Transaction,
        original: &State,
        timestamp: Timestamp,
    ) {
        let inversion = transaction
            .invert(&original.doc)
            // Store the current cursor position
            .with_selection(original.selection.clone());

        let new_current = self.revisions.len();
        self.revisions[self.current].last_child = NonZeroUsize::new(new_current);
        self.revisions.push(Revision {
            parent: self.current,
            last_child: None,
            transaction: transaction.clone(),
            inversion,
            timestamp,
        });
        self.current = new_current;
    }

    /// Folds `transaction` into the current revision instead of committing a new one, so a
    /// run of edits (typing, for example) undoes as one step. `original_doc` is the document
    /// before `transaction`. The revision keeps the selection from before its first edit.
    /// Returns `false`, changing nothing, unless the current revision is the newest leaf.
    ///
    /// caretline addition: not in upstream Helix.
    pub fn amend_current_revision(
        &mut self,
        transaction: &Transaction,
        original_doc: &Rope,
        timestamp: Timestamp,
    ) -> bool {
        if self.current == 0
            || self.current != self.revisions.len() - 1
            || self.revisions[self.current].last_child.is_some()
        {
            return false;
        }
        let rev = &mut self.revisions[self.current];
        let composed = std::mem::take(&mut rev.transaction).compose(transaction.clone());
        rev.transaction = composed;
        // Undo the newest edit first, then the earlier ones. `compose` keeps the selection of
        // its right-hand side, which is the selection from before the run.
        let inversion = std::mem::take(&mut rev.inversion);
        rev.inversion = transaction.invert(original_doc).compose(inversion);
        rev.timestamp = timestamp;
        true
    }

    /// Transforms the history over `remote`, a change made elsewhere to the current
    /// document, so that undo takes back only the local edits and keeps `remote` (operational
    /// transform). `doc` is the document after `remote`. Walking from the current revision
    /// back to the root, each revision's inversion is mapped over the remote change as it
    /// stood at that revision (`I'_k = I_k.map(R_k)`), the remote change is carried one
    /// revision back (`R_{k-1} = R_k.map(I_k, before)`), and each transaction becomes the
    /// inverse of its new inversion. Selections are mapped the same way. Revisions off the
    /// path from the root to the current one (redo branches) are dropped.
    ///
    /// Returns, for each revision kept (by new index), its old index, the remote change as it
    /// applies to that revision's old document (`R_k`) and the revision's new document, for
    /// callers that keep data per revision.
    ///
    /// caretline addition: not in upstream Helix.
    pub fn rebase_over(&mut self, remote: &ChangeSet, doc: &Rope) -> Vec<Rebased> {
        let path = self.path_up(self.current, 0);
        // `path` runs from the current revision down to the root's child.
        let mut r = remote.clone();
        let mut text = doc.clone();
        let mut rebuilt: Vec<(Rebased, Transaction, Transaction, Timestamp)> = Vec::with_capacity(path.len());
        for &k in &path {
            let rev = &self.revisions[k];
            let inv = rev.inversion.changes();
            let inv2 = inv.map_ordered(&r, false);
            let r_prev = r.map_ordered(inv, true);
            let transaction = {
                let t = Transaction::from(inv2.invert(&text));
                match rev.transaction.selection() {
                    Some(sel) => t.with_selection(map_selection(sel, &r)),
                    None => t,
                }
            };
            let mut prev_text = text.clone();
            inv2.apply(&mut prev_text);
            let inversion = {
                let t = Transaction::from(inv2);
                match rev.inversion.selection() {
                    Some(sel) => t.with_selection(map_selection(sel, &r_prev)),
                    None => t,
                }
            };
            let remote_k = std::mem::replace(&mut r, r_prev);
            let text_k = std::mem::replace(&mut text, prev_text);
            rebuilt.push((Rebased { old: k, remote: remote_k, text: text_k }, transaction, inversion, rev.timestamp));
        }
        let mut kept = vec![Rebased { old: 0, remote: r, text }];
        let mut revisions = vec![Revision {
            parent: 0,
            last_child: None,
            transaction: std::mem::take(&mut self.revisions[0].transaction),
            inversion: std::mem::take(&mut self.revisions[0].inversion),
            timestamp: self.revisions[0].timestamp,
        }];
        for (rebased, transaction, inversion, timestamp) in rebuilt.into_iter().rev() {
            let i = revisions.len();
            revisions[i - 1].last_child = NonZeroUsize::new(i);
            revisions.push(Revision { parent: i - 1, last_child: None, transaction, inversion, timestamp });
            kept.push(rebased);
        }
        self.current = revisions.len() - 1;
        self.revisions = revisions;
        kept
    }

    /// The current revision's transaction (from its parent to it). The root's is empty.
    pub fn current_transaction(&self) -> &Transaction {
        &self.revisions[self.current].transaction
    }

    /// The current revision's inversion (from it back to its parent).
    pub fn current_inversion(&self) -> &Transaction {
        &self.revisions[self.current].inversion
    }

    /// The number of revisions, including the root.
    pub fn len(&self) -> usize {
        self.revisions.len()
    }

    /// Whether only the root revision exists.
    pub fn is_empty(&self) -> bool {
        self.revisions.len() == 1
    }

    /// Whether there is a revision to redo.
    pub fn can_redo(&self) -> bool {
        self.revisions[self.current].last_child.is_some()
    }

    #[inline]
    pub fn current_revision(&self) -> usize {
        self.current
    }

    #[inline]
    pub const fn at_root(&self) -> bool {
        self.current == 0
    }

    /// Returns the changes since the given revision composed into a transaction.
    /// Returns None if there are no changes between the current and given revisions.
    pub fn changes_since(&self, revision: usize) -> Option<Transaction> {
        let lca = self.lowest_common_ancestor(revision, self.current);
        let up = self.path_up(revision, lca);
        let down = self.path_up(self.current, lca);
        let up_txns = up
            .iter()
            .rev()
            .map(|&n| self.revisions[n].inversion.clone());
        let down_txns = down.iter().map(|&n| self.revisions[n].transaction.clone());

        down_txns.chain(up_txns).reduce(|acc, tx| tx.compose(acc))
    }

    /// Undo the last edit.
    pub fn undo(&mut self) -> Option<&Transaction> {
        if self.at_root() {
            return None;
        }

        let current_revision = &self.revisions[self.current];
        self.current = current_revision.parent;
        Some(&current_revision.inversion)
    }

    /// Redo the last edit.
    pub fn redo(&mut self) -> Option<&Transaction> {
        let current_revision = &self.revisions[self.current];
        let last_child = current_revision.last_child?;
        self.current = last_child.get();

        Some(&self.revisions[last_child.get()].transaction)
    }

    // Get the position of last change
    pub fn last_edit_pos(&self) -> Option<usize> {
        if self.current == 0 {
            return None;
        }
        let current_revision = &self.revisions[self.current];
        let primary_selection = current_revision
            .inversion
            .selection()
            .expect("inversion always contains a selection")
            .primary();
        let (_from, to, _fragment) = current_revision
            .transaction
            .changes_iter()
            // find a change that matches the primary selection
            .find(|(from, to, _fragment)| Range::new(*from, *to).overlaps(&primary_selection))
            // or use the first change
            .or_else(|| current_revision.transaction.changes_iter().next())
            .unwrap();
        let pos = current_revision
            .transaction
            .changes()
            .map_pos(to, Assoc::After);
        Some(pos)
    }

    fn lowest_common_ancestor(&self, mut a: usize, mut b: usize) -> usize {
        use std::collections::HashSet;
        let mut a_path_set = HashSet::new();
        let mut b_path_set = HashSet::new();
        loop {
            a_path_set.insert(a);
            b_path_set.insert(b);
            if a_path_set.contains(&b) {
                return b;
            }
            if b_path_set.contains(&a) {
                return a;
            }
            a = self.revisions[a].parent; // Relies on the parent of 0 being 0.
            b = self.revisions[b].parent; // Same as above.
        }
    }

    /// List of nodes on the way from `n` to 'a`. Doesn't include `a`.
    /// Includes `n` unless `a == n`. `a` must be an ancestor of `n`.
    fn path_up(&self, mut n: usize, a: usize) -> Vec<usize> {
        let mut path = Vec::new();
        while n != a {
            path.push(n);
            n = self.revisions[n].parent;
        }
        path
    }

    /// Create a [`Transaction`] that will jump to a specific revision in the history.
    fn jump_to(&mut self, to: usize) -> Vec<Transaction> {
        let lca = self.lowest_common_ancestor(self.current, to);
        let up = self.path_up(self.current, lca);
        let down = self.path_up(to, lca);
        self.current = to;
        let up_txns = up.iter().map(|&n| self.revisions[n].inversion.clone());
        let down_txns = down
            .iter()
            .rev()
            .map(|&n| self.revisions[n].transaction.clone());
        up_txns.chain(down_txns).collect()
    }

    /// Creates a [`Transaction`] that will undo `delta` revisions.
    fn jump_backward(&mut self, delta: usize) -> Vec<Transaction> {
        self.jump_to(self.current.saturating_sub(delta))
    }

    /// Creates a [`Transaction`] that will redo `delta` revisions.
    fn jump_forward(&mut self, delta: usize) -> Vec<Transaction> {
        self.jump_to(
            self.current
                .saturating_add(delta)
                .min(self.revisions.len() - 1),
        )
    }

    /// Helper for a binary search case below.
    fn revision_closer_to_instant(&self, i: usize, instant: Timestamp) -> usize {
        let dur_im1 = instant.saturating_sub(self.revisions[i - 1].timestamp);
        let dur_i = self.revisions[i].timestamp.saturating_sub(instant);
        use std::cmp::Ordering::*;
        match dur_im1.cmp(&dur_i) {
            Less => i - 1,
            Equal | Greater => i,
        }
    }

    /// Creates a [`Transaction`] that will match a revision created at around
    /// `instant`.
    fn jump_instant(&mut self, instant: Timestamp) -> Vec<Transaction> {
        let search_result = self
            .revisions
            .binary_search_by(|rev| rev.timestamp.cmp(&instant));
        let revision = match search_result {
            Ok(revision) => revision,
            Err(insert_point) => match insert_point {
                0 => 0,
                n if n == self.revisions.len() => n - 1,
                i => self.revision_closer_to_instant(i, instant),
            },
        };
        self.jump_to(revision)
    }

    /// Creates a [`Transaction`] that will match a revision created `duration` ago
    /// from the timestamp of current revision.
    fn jump_duration_backward(&mut self, duration: Duration) -> Vec<Transaction> {
        match self.revisions[self.current]
            .timestamp
            .checked_sub(duration.as_millis() as Timestamp) {
            Some(instant) => self.jump_instant(instant),
            None => self.jump_to(0),
        }
    }

    /// Creates a [`Transaction`] that will match a revision created `duration` in
    /// the future from the timestamp of the current revision.
    fn jump_duration_forward(&mut self, duration: Duration) -> Vec<Transaction> {
        match self.revisions[self.current]
            .timestamp
            .checked_add(duration.as_millis() as Timestamp) {
            Some(instant) => self.jump_instant(instant),
            None => self.jump_to(self.revisions.len() - 1),
        }
    }

    /// Creates an undo [`Transaction`].
    pub fn earlier(&mut self, uk: UndoKind) -> Vec<Transaction> {
        use UndoKind::*;
        match uk {
            Steps(n) => self.jump_backward(n),
            TimePeriod(d) => self.jump_duration_backward(d),
        }
    }

    /// Creates a redo [`Transaction`].
    pub fn later(&mut self, uk: UndoKind) -> Vec<Transaction> {
        use UndoKind::*;
        match uk {
            Steps(n) => self.jump_forward(n),
            TimePeriod(d) => self.jump_duration_forward(d),
        }
    }
}

/// Whether to undo by a number of edits or a duration of time.
#[derive(Debug, PartialEq, Eq, Clone, Copy)]
pub enum UndoKind {
    Steps(usize),
    TimePeriod(std::time::Duration),
}

#[cfg(test)]
mod test {
    use super::*;
    use crate::helix::Selection;

    #[test]
    fn test_undo_redo() {
        let mut history = History::default();
        let doc = Rope::from("hello");
        let mut state = State {
            doc,
            selection: Selection::point(0),
        };

        let transaction1 =
            Transaction::change(&state.doc, vec![(5, 5, Some(" world!".into()))].into_iter());

        // Need to commit before applying!
        history.commit_revision_at_timestamp(&transaction1, &state, 0);
        transaction1.apply(&mut state.doc);
        assert_eq!("hello world!", state.doc);

        // ---

        let transaction2 =
            Transaction::change(&state.doc, vec![(6, 11, Some("世界".into()))].into_iter());

        // Need to commit before applying!
        history.commit_revision_at_timestamp(&transaction2, &state, 0);
        transaction2.apply(&mut state.doc);
        assert_eq!("hello 世界!", state.doc);

        // ---
        fn undo(history: &mut History, state: &mut State) {
            if let Some(transaction) = history.undo() {
                transaction.apply(&mut state.doc);
            }
        }
        fn redo(history: &mut History, state: &mut State) {
            if let Some(transaction) = history.redo() {
                transaction.apply(&mut state.doc);
            }
        }

        undo(&mut history, &mut state);
        assert_eq!("hello world!", state.doc);
        redo(&mut history, &mut state);
        assert_eq!("hello 世界!", state.doc);
        undo(&mut history, &mut state);
        undo(&mut history, &mut state);
        assert_eq!("hello", state.doc);

        // undo at root is a no-op
        undo(&mut history, &mut state);
        assert_eq!("hello", state.doc);
    }

    #[test]
    fn test_earlier_later() {
        let mut history = History::default();
        let doc = Rope::from("a\n");
        let mut state = State {
            doc,
            selection: Selection::point(0),
        };

        fn undo(history: &mut History, state: &mut State) {
            if let Some(transaction) = history.undo() {
                transaction.apply(&mut state.doc);
            }
        }

        fn earlier(history: &mut History, state: &mut State, uk: UndoKind) {
            let txns = history.earlier(uk);
            for txn in txns {
                txn.apply(&mut state.doc);
            }
        }

        fn later(history: &mut History, state: &mut State, uk: UndoKind) {
            let txns = history.later(uk);
            for txn in txns {
                txn.apply(&mut state.doc);
            }
        }

        fn commit_change(
            history: &mut History,
            state: &mut State,
            change: crate::helix::transaction::Change,
            instant: Timestamp,
        ) {
            let txn = Transaction::change(&state.doc, vec![change].into_iter());
            history.commit_revision_at_timestamp(&txn, state, instant);
            txn.apply(&mut state.doc);
        }

        let t = |n: u64| n * 1000;

        commit_change(&mut history, &mut state, (1, 1, Some(" b".into())), t(0));
        assert_eq!("a b\n", state.doc);

        commit_change(&mut history, &mut state, (3, 3, Some(" c".into())), t(10));
        assert_eq!("a b c\n", state.doc);

        commit_change(&mut history, &mut state, (5, 5, Some(" d".into())), t(20));
        assert_eq!("a b c d\n", state.doc);

        undo(&mut history, &mut state);
        assert_eq!("a b c\n", state.doc);

        commit_change(&mut history, &mut state, (5, 5, Some(" e".into())), t(30));
        assert_eq!("a b c e\n", state.doc);

        undo(&mut history, &mut state);
        undo(&mut history, &mut state);
        assert_eq!("a b\n", state.doc);

        commit_change(&mut history, &mut state, (1, 3, None), t(40));
        assert_eq!("a\n", state.doc);

        commit_change(&mut history, &mut state, (1, 1, Some(" f".into())), t(50));
        assert_eq!("a f\n", state.doc);

        use UndoKind::*;

        earlier(&mut history, &mut state, Steps(3));
        assert_eq!("a b c d\n", state.doc);

        later(&mut history, &mut state, TimePeriod(Duration::new(20, 0)));
        assert_eq!("a\n", state.doc);

        earlier(&mut history, &mut state, TimePeriod(Duration::new(19, 0)));
        assert_eq!("a b c d\n", state.doc);

        earlier(
            &mut history,
            &mut state,
            TimePeriod(Duration::new(10000, 0)),
        );
        assert_eq!("a\n", state.doc);

        later(&mut history, &mut state, Steps(50));
        assert_eq!("a f\n", state.doc);

        earlier(&mut history, &mut state, Steps(4));
        assert_eq!("a b c\n", state.doc);

        later(&mut history, &mut state, TimePeriod(Duration::new(1, 0)));
        assert_eq!("a b c\n", state.doc);

        later(&mut history, &mut state, TimePeriod(Duration::new(5, 0)));
        assert_eq!("a b c d\n", state.doc);

        later(&mut history, &mut state, TimePeriod(Duration::new(6, 0)));
        assert_eq!("a b c e\n", state.doc);

        later(&mut history, &mut state, Steps(1));
        assert_eq!("a\n", state.doc);
    }

}

/// Maps a selection stored in a revision through `changes`, clamping it to the document the
/// changes apply to first (a stored selection is always inside it; this only guards against
/// a hand-edited state).
fn map_selection(sel: &Selection, changes: &ChangeSet) -> Selection {
    let len = changes.len();
    sel.clone()
        .transform(|r| Range { anchor: r.anchor.min(len), head: r.head.min(len), old_visual_position: None })
        .map(changes)
}