blockworx_doc/

trail.rs

//! The undo trail: which revs a session can step back to, and which
//! forward.
//!
//! See `docs/log-vs-snapshot.md`. A step back is not an erasure — it is a
//! new rev that adopts an older document — so the trail holds positions
//! rather than commits: an [`Entry`] names the record it stands for and
//! the rev whose document taking it adopts. Nothing here knows how a
//! session finds that document; a container reads a rev file and a
//! session with no files folds its log prefix, and both then run this
//! same policy.

use crate::rev::Rev;

/// Which stack a record's entry lands on, and what it does to the other —
/// the whole undo/redo policy, stated once.
///
/// It is also a durable record's *kind*, in the only spelling this
/// headless crate knows: a replayed log hands each record's kind over as
/// one of these, so a reopened document rebuilds its trail by running
/// this policy rather than a second copy of it.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum JournalAs {
    Edit,
    Undo { of: Rev },
    Redo { of: Rev },
}

/// Which way a history step goes. Two variants, so "an edit is a history
/// step" cannot be spelled.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Direction {
    Undo,
    Redo,
}

impl Direction {
    /// How the record this step writes names itself, ahead of the label of
    /// the record it moved.
    pub fn verb(self) -> &'static str {
        match self {
            Direction::Undo => "Undo",
            Direction::Redo => "Redo",
        }
    }

    pub(crate) fn journal(self, of: Rev) -> JournalAs {
        match self {
            Direction::Undo => JournalAs::Undo { of },
            Direction::Redo => JournalAs::Redo { of },
        }
    }
}

/// One step this trail can take: the record it stands for, and the rev
/// whose document taking it adopts.
///
/// `restores` is the rev the session stood on when the record was
/// written, which is why a step and its reverse land on the same document
/// however many times they are repeated.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct Entry {
    pub rev: Rev,
    pub restores: Rev,
}

/// Why a history step did not happen.
///
/// [`Self::Stale`] earns its place: a caller keeping its own history can
/// name a rev this trail does not hold on top, and stepping its neighbour
/// instead would be silent.
#[derive(Debug, thiserror::Error, PartialEq)]
pub enum UndoRefusal {
    #[error("nothing stands ready to be taken back")]
    Spent,
    #[error("the step names a rev this trail no longer holds on top ({top:?})")]
    Stale { top: Rev },
}

/// Where a session's history stands: what one press would take back, what
/// one would put back, and which rev's document the head currently holds.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct Trail {
    undo: Vec<Entry>,
    redo: Vec<Entry>,
    standing: Rev,
}

impl Trail {
    /// The rev whose document the head holds. An edit at N stands at N; a
    /// step stands at the rev it restored, so an undo and its redo return
    /// the session to the position it started from rather than to a rev
    /// that merely looks like it.
    pub fn standing(&self) -> Rev {
        self.standing
    }

    /// Stand at `rev` with nothing new to take back: a commit that is the
    /// document's past rather than a step this session took — the seeding
    /// path, and a repo built by folding a log before a session opened
    /// over it.
    ///
    /// Without it the first edit over such a document would offer to
    /// restore the empty document, since that is where a fresh trail
    /// stands.
    pub fn seeded(&mut self, rev: Rev) {
        self.standing = rev;
    }

    /// Take a record of `rev` into the trail: an edit or a redo is a step
    /// somebody can take back, an undo is one they can put back, and each
    /// step retires the entry it consumed.
    ///
    /// This is the only place the policy lives, so a live session and a
    /// replayed log cannot disagree about the trail they end up with.
    pub fn record(&mut self, rev: Rev, journal_as: JournalAs) {
        let entry = Entry {
            rev,
            restores: self.standing,
        };
        match journal_as {
            JournalAs::Edit => {
                self.redo.clear();
                self.undo.push(entry);
                self.standing = rev;
            }
            JournalAs::Undo { of } => {
                self.redo.push(entry);
                let retired = retire(&mut self.undo, of);
                self.stand_where(retired);
            }
            JournalAs::Redo { of } => {
                self.undo.push(entry);
                let retired = retire(&mut self.redo, of);
                self.stand_where(retired);
            }
        }
    }

    /// The entry a step naming `edit` would take, without taking it.
    ///
    /// # Errors
    /// [`UndoRefusal::Spent`] when nothing stands ready, and
    /// [`UndoRefusal::Stale`] — reporting its own top — when the top is a
    /// different rev than `edit`.
    pub fn stepping(&self, edit: Rev, direction: Direction) -> Result<Entry, UndoRefusal> {
        let top = *self.stack(direction).last().ok_or(UndoRefusal::Spent)?;
        if top.rev != edit {
            return Err(UndoRefusal::Stale { top: top.rev });
        }
        Ok(top)
    }

    pub fn can_undo(&self) -> bool {
        !self.undo.is_empty()
    }

    pub fn can_redo(&self) -> bool {
        !self.redo.is_empty()
    }

    /// How many steps stand ready to be taken back. The editor keeps a
    /// parallel stack that interleaves view steps with these, and the two
    /// depths must agree — exposed so the mismatch is checkable rather
    /// than silent.
    pub fn undo_depth(&self) -> usize {
        self.undo.len()
    }

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

    /// The rev an undo would move, and the one a redo would — so a caller
    /// holding its own history can tell whether the step it is about to
    /// take is still the step this trail would take.
    pub fn next_undo(&self) -> Option<Rev> {
        self.undo.last().map(|entry| entry.rev)
    }

    pub fn next_redo(&self) -> Option<Rev> {
        self.redo.last().map(|entry| entry.rev)
    }

    /// Every rev standing ready to be taken back, oldest first — for a
    /// caller whose own stack must agree with this one, entry for entry.
    pub fn undo_revs(&self) -> Vec<Rev> {
        self.undo.iter().map(|entry| entry.rev).collect()
    }

    /// The forward half of [`Self::undo_revs`].
    pub fn redo_revs(&self) -> Vec<Rev> {
        self.redo.iter().map(|entry| entry.rev).collect()
    }

    /// Everywhere this trail can stand, deepest past first, with
    /// [`Self::standing`] at index [`Self::undo_depth`] — one point per
    /// step a walk from either end would take, which is what a session
    /// rebuilding its own stack from a reopened document needs.
    pub fn standings(&self) -> Vec<Rev> {
        self.undo
            .iter()
            .map(|entry| entry.restores)
            .chain(std::iter::once(self.standing))
            .chain(self.redo.iter().rev().map(|entry| entry.restores))
            .collect()
    }

    fn stack(&self, direction: Direction) -> &[Entry] {
        match direction {
            Direction::Undo => &self.undo,
            Direction::Redo => &self.redo,
        }
    }

    fn stand_where(&mut self, retired: Option<Entry>) {
        if let Some(entry) = retired {
            self.standing = entry.restores;
        }
    }
}

/// Drop the entry a step just consumed and say where it left the session
/// standing. A step has already refused a name that is not the top, and a
/// replayed record names what its own session's step did; a name the
/// stack does not hold is left alone rather than taken as "the top one".
fn retire(stack: &mut Vec<Entry>, edit: Rev) -> Option<Entry> {
    let at = stack.iter().rposition(|entry| entry.rev == edit)?;
    Some(stack.remove(at))
}

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

    /// The trail a run of edits leaves: each stands on itself, and each
    /// entry restores the one before it.
    fn edited(n: u64) -> Trail {
        let mut trail = Trail::default();
        for at in 1..=n {
            trail.record(rev(at), JournalAs::Edit);
        }
        trail
    }

    #[test]
    fn an_edit_stands_on_itself_and_restores_the_one_before_it() {
        let trail = edited(3);
        assert_eq!(trail.standing(), rev(3));
        assert_eq!(trail.undo_revs(), [rev(1), rev(2), rev(3)]);
        assert_eq!(trail.standings(), [rev(0), rev(1), rev(2), rev(3)]);
        assert_eq!(
            trail.stepping(rev(3), Direction::Undo),
            Ok(Entry {
                rev: rev(3),
                restores: rev(2)
            }),
        );
    }

    #[test]
    fn a_step_naming_anything_but_the_top_is_refused() {
        let trail = edited(2);
        assert_eq!(
            trail.stepping(rev(1), Direction::Undo),
            Err(UndoRefusal::Stale { top: rev(2) }),
        );
        assert_eq!(
            trail.stepping(rev(1), Direction::Redo),
            Err(UndoRefusal::Spent),
        );
    }

    /// The property the walk depends on: an undo and its redo return the
    /// session to the rev it started from, however deep into a mixed trail
    /// the pair happens.
    #[test]
    fn a_step_and_its_reverse_return_to_the_rev_they_started_from() {
        let mut trail = edited(3);
        // Undo twice, redo once, edit — the shape that made a naive
        // "restores is the rev before" rule leave the trail standing on a
        // rev it had never stood on.
        trail.record(rev(4), JournalAs::Undo { of: rev(3) });
        trail.record(rev(5), JournalAs::Undo { of: rev(2) });
        assert_eq!(trail.standing(), rev(1));

        let before = trail.clone();
        let put_back = trail.next_redo().expect("a step to put back");
        trail.record(rev(6), JournalAs::Redo { of: put_back });
        assert_eq!(trail.standing(), rev(2));
        let take_back = trail.next_undo().expect("a step to take back");
        trail.record(rev(7), JournalAs::Undo { of: take_back });

        assert_eq!(trail.standing(), before.standing());
        assert_eq!(trail.undo_revs().len(), before.undo_revs().len());
        assert_eq!(trail.standings(), before.standings());
    }

    /// What the editor's walk needs: standing falls with every undo and
    /// rises with every redo, so a walk toward a target terminates.
    #[test]
    fn standing_falls_along_the_undo_stack_and_rises_along_the_redo_stack() {
        let mut trail = edited(3);
        trail.record(rev(4), JournalAs::Undo { of: rev(3) });
        trail.record(rev(5), JournalAs::Edit);
        trail.record(rev(6), JournalAs::Undo { of: rev(5) });
        trail.record(rev(7), JournalAs::Redo { of: rev(6) });

        let line = trail.standings();
        assert!(
            line.windows(2).all(|pair| pair[0] < pair[1]),
            "the trail's positions must be ordered for a walk to terminate: {line:?}",
        );
        assert_eq!(line[trail.undo_depth()], trail.standing());
    }

    #[test]
    fn an_edit_abandons_the_redo_future() {
        let mut trail = edited(2);
        trail.record(rev(3), JournalAs::Undo { of: rev(2) });
        assert!(trail.can_redo());
        trail.record(rev(4), JournalAs::Edit);
        assert!(!trail.can_redo(), "a new edit forks the history");
        assert_eq!(trail.standing(), rev(4));
    }
}