blockworx/

history.rs

//! The editor's undo stack: spec §7's two kinds of entry on one stack.
//!
//! A `doc` entry authors an inverse rev at the head; a `view` entry restores
//! where the camera stood and which scope was open, and touches no log. Both
//! are the same thing here — a [`State`] the editor once stood in — and one
//! press walks to the previous one, authoring only as much of the document as
//! the walk crosses.
//!
//! **The stack is egui's [`Undoer`], not one of ours.** It is fed the current
//! state every frame and decides for itself when a change has settled into an
//! entry, which is exactly §7.2's coalescing rule with [`COALESCE`] as its
//! `stable_time`: a camera worked continuously never settles, so a pinch
//! leaves one entry rather than one per frame, and two moves inside the window
//! are one press to take back.
//!
//! The document half is *not* moved here. `blockworx_doc::trail`'s [`Trail`]
//! remains what holds the steps — it is durable, and F6's reopened undo
//! depth comes from it — and a state names which of its positions the
//! document stands on through [`Stood`]. This stack is the session-level
//! interleaving over that trail, and its own emptiness on reload is spec
//! §6.2's "viewing state does not survive a reload".

use core::time::Duration;

use blockworx_doc::{rev::Rev, trail::Trail};
use blockworx_geom::Pos2;
use egui::util::undoer::Undoer;

use crate::{
    canvas::Vantage,
    path::BlockPath,
    tools::{
        SelectTool,
        multi_pin_select::MultiPinSelect,
        multi_select::MultiSelect,
        resize_block::ResizeBlock,
        tool::{Deletable, Tool, select_tool_for_anchor},
    },
    widget::drawing::Drawing,
};
/// §7.2: consecutive same-type view entries inside this window are one entry.
/// It is the [`Undoer`]'s `stable_time`, so it is also what makes a gesture
/// end — rather than a gesture frame — the point an entry lands.
pub const COALESCE: Duration = Duration::from_millis(1500);

/// How many states the stack remembers. egui's own default; past it the
/// history panel is the surface, as it is for the log.
const DEPTH: usize = 100;

/// A selection, with the point a route was picked at.
///
/// Bundled because the anchor only means anything beside the thing it
/// anchors: a route spans a wide box but is picked at one spot, and an
/// anchor without a selection names nothing.
#[derive(Clone, Debug, PartialEq)]
pub struct Selection {
    pub what: Deletable,
    pub anchor: Option<Pos2>,
}

/// Which of the trail's positions the document stands on: the rev whose
/// document the head currently holds (S6).
///
/// **Not the head rev.** A step authors a commit of its own, so the head
/// moves *forward* when the document steps back; feeding it would make
/// every undo look like a fresh state and the stack would grow instead of
/// walking. What the trail tracks instead is where a step *left* the
/// session, which is stable across a round trip — an undo and its redo
/// return to the same `Stood` — and ordered along both halves of the
/// trail, which is what makes a walk toward one terminate.
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug, Default)]
pub struct Stood(Rev);

impl Stood {
    pub fn of(trail: &Trail) -> Self {
        Self(trail.standing())
    }
}

/// What made a state, in the words §7.2's tooltip names it by.
///
/// Panning and zooming are one kind: a hand navigating with both would
/// otherwise leave entries that alternate and so never coalesce.
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
pub enum Moved {
    #[default]
    Camera,
    Fit,
    Focus,
    Scope,
    /// A document edit. Its words come from the commit, not from here.
    Edit,
}

impl Moved {
    /// What one press would take back, for a `view` entry. A `doc` entry is
    /// named by its commit's own label instead.
    pub fn label(self) -> &'static str {
        match self {
            Moved::Camera => "the camera move",
            Moved::Fit => "zoom to fit",
            Moved::Focus => "the focus",
            Moved::Scope => "the change of scope",
            Moved::Edit => "the edit",
        }
    }
}

/// One point on the stack: everywhere the editor was, as far as undo cares.
///
/// Equality is what the [`Undoer`] asks every frame to decide whether
/// anything happened, so it covers exactly the camera, the scope and the
/// document — §7.1's two kinds and nothing else. Two fields ride along
/// outside it:
///
/// - the **selection**, because picking something is how you *reach* an edit;
///   a step per selection would cost several presses to get back past one
///   edit and Cmd+Z would stop meaning "take back what I did". It still comes
///   back with the state that holds it.
/// - the **label**, because a fit that lands the camera where it already was
///   is not a step.
#[derive(Clone, Debug)]
pub struct State {
    pub camera: Vantage,
    pub scope: BlockPath,
    pub stood: Stood,
    pub moved: Moved,
    pub selection: Option<Selection>,
}

impl PartialEq for State {
    fn eq(&self, other: &Self) -> bool {
        self.camera == other.camera && self.scope == other.scope && self.stood == other.stood
    }
}

/// §7.1's two kinds of entry, told apart by whether taking the step back
/// crosses a [`Stood`] boundary.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Kind {
    /// Authors an inverse rev at the head.
    Doc,
    /// Restores a camera and a scope. Touches no log.
    View,
}

/// What one press of undo — or of redo — would do: the thing it names, and
/// what it costs the log. Invariant 8's whole content.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Consequence {
    pub target: String,
    pub kind: Kind,
}

/// 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 {
    Back,
    Forward,
}

/// Whether a frame's own recording should happen. An undo or redo restores a
/// state by definition, so the frame it runs in must not read the inverse
/// commits it authored as fresh edits — which would push the step it just
/// took straight back onto the stack.
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
pub enum Recording {
    #[default]
    On,
    Suspended,
}

pub struct UndoStack {
    undoer: Undoer<State>,
}

impl UndoStack {
    /// A stack holding nothing but where the session opens.
    pub fn opening(at: &State) -> Self {
        let mut stack = Self {
            undoer: Undoer::with_settings(egui::util::undoer::Settings {
                max_undos: DEPTH,
                stable_time: COALESCE.as_secs_f32(),
                ..Default::default()
            }),
        };
        stack.undoer.add_undo(at);
        stack
    }

    /// The stack a document that was replayed rather than edited opens on:
    /// one point per entry of `trail`, both ways, in the trail's own order
    /// — so F6's reopened undo depth is what the user sees from the first
    /// frame.
    ///
    /// A reconstructed point has no camera or scope of its own: those are
    /// session state and genuinely do not survive a restart (§6.2), so every
    /// point holds the one the document opens at. That is also why the walk
    /// they drive is a document walk and lands the camera where it already
    /// is.
    pub fn reconstructed(trail: &Trail, at: &State) -> Self {
        let line = trail.standings();
        let point = |depth: usize| State {
            stood: Stood(line[depth]),
            ..at.clone()
        };
        let mut stack = Self::opening(&point(0));
        let past = trail.undo_depth();
        let future = trail.redo_depth();
        for depth in 1..=(past + future) {
            stack.undoer.add_undo(&point(depth));
        }
        // Nothing can push a redo directly, so the future is walked back out
        // of the past: each step moves one point across, and the last of them
        // lands on the state the document actually stands in.
        for depth in ((past + 1)..=(past + future)).rev() {
            stack.undoer.undo(&point(depth));
        }
        stack
    }

    /// Offer the stack this frame's state. Whether it becomes an entry is the
    /// [`Undoer`]'s call, and [`COALESCE`] is the rule it makes it by.
    pub fn feed(&mut self, at: Duration, now: &State) {
        self.undoer.feed_state(at.as_secs_f64(), now);
    }

    /// Punctuate the stack with an edit: the state either side of it becomes
    /// an entry immediately, so two edits inside the coalescing window are
    /// still two presses to take back. View entries coalesce; document edits
    /// are what the coalescing exists to stop burying.
    ///
    /// The feed goes first because it is what drops the forward history the
    /// edit has just invalidated — the trail has already dropped its own half.
    pub fn edited(&mut self, at: Duration, before: &State, now: &State) {
        self.undoer.feed_state(at.as_secs_f64(), now);
        self.undoer.add_undo(before);
        self.undoer.add_undo(now);
    }

    /// Pin where a step actually came to rest.
    ///
    /// A step that framed what it changed does not land on the point it
    /// popped — the camera moved to bring the change into sight — and the
    /// stack has to hold *that*, or the next frame's [`Self::feed`] would
    /// read the framing as a fresh move and abandon the future the step just
    /// created. Framing nothing lands on the popped point exactly, and this
    /// is then the no-op it should be.
    pub fn landed(&mut self, at: &State) {
        self.undoer.add_undo(at);
    }

    /// The state one step would land on, without taking it.
    ///
    /// egui's `Undoer` keeps its points private and offers no peek, so the
    /// question is asked of a copy. That is the honest way to ask it: a
    /// second stack kept alongside to answer it would be the drift this
    /// module exists to avoid.
    pub fn peek(&self, direction: Direction, now: &State) -> Option<State> {
        let mut asked = UndoStack {
            undoer: self.undoer.clone(),
        };
        asked.step(direction, now)
    }

    /// Take one step, and say where it lands.
    pub fn step(&mut self, direction: Direction, now: &State) -> Option<State> {
        match direction {
            Direction::Back => self.undoer.undo(now).cloned(),
            Direction::Forward => self.undoer.redo(now).cloned(),
        }
    }
}

/// The tool a restored selection resolves to — the one place that maps a
/// selection back to the tool that holds it, so restoring and selecting
/// cannot disagree about what "a block is selected" means.
///
/// `candidates` are tried in order and the first the document still holds
/// wins; a step offers more than one because an undo can remove the thing
/// its edit selected. None surviving means no selection, not a tool pointed
/// at nothing.
pub fn tool_for(data: &Drawing<'_>, candidates: &[&Selection]) -> Tool {
    candidates
        .iter()
        .find_map(|selection| resolve(data, selection))
        .unwrap_or_else(|| SelectTool.into())
}

/// `None` when the document no longer holds what the selection names.
fn resolve(data: &Drawing<'_>, selection: &Selection) -> Option<Tool> {
    match &selection.what {
        Deletable::Shape(shape) => data
            .shape(*shape)
            .is_some()
            .then(|| ResizeBlock::Selected { shape: *shape }.into()),
        Deletable::Route(id) => {
            let anchor = selection.anchor?;
            data.auto_route(*id)
                .is_some()
                .then(|| crate::tools::EditRoute::Selected { id: *id, anchor }.into())
        }
        Deletable::Shapes(shapes) => {
            let live: Vec<_> = shapes
                .iter()
                .copied()
                .filter(|id| data.shape(*id).is_some())
                .collect();
            match live.len() {
                0 => None,
                1 => Some(ResizeBlock::Selected { shape: live[0] }.into()),
                _ => Some(MultiSelect::Selected { shapes: live }.into()),
            }
        }
        Deletable::Pins(pins) => {
            let live: Vec<_> = pins
                .iter()
                .copied()
                .filter(|id| data.pin_on_shape(*id).is_some())
                .collect();
            match live.len() {
                0 => None,
                1 => Some(select_tool_for_anchor(data, live[0])),
                _ => Some(MultiPinSelect::Selected { pins: live }.into()),
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use blockworx_doc::fixtures::{block_id, rev};
    use blockworx_geom::{Vec2, pos2, vec2};

    fn vantage(x: f32) -> Vantage {
        Vantage {
            zoom: blockworx_paint::Zoom::unity(),
            translation: vec2(x, 0.0),
        }
    }

    fn state() -> State {
        State {
            camera: Vantage {
                zoom: blockworx_paint::Zoom::unity(),
                translation: Vec2::ZERO,
            },
            scope: BlockPath::empty(),
            stood: Stood::default(),
            moved: Moved::default(),
            selection: None,
        }
    }

    fn looking_at(x: f32) -> State {
        State {
            camera: vantage(x),
            ..state()
        }
    }

    fn inside(n: u32) -> State {
        let mut scope = BlockPath::empty();
        scope.push(block_id(n));
        State { scope, ..state() }
    }

    fn edited(depth: u64) -> State {
        State {
            stood: Stood(rev(depth)),
            moved: Moved::Edit,
            ..state()
        }
    }

    fn shape(n: u32) -> Selection {
        Selection {
            what: Deletable::Shape(crate::shape::ShapeId::Rect(block_id(n))),
            anchor: None,
        }
    }

    /// A moment past the coalescing window.
    fn later(at: Duration) -> Duration {
        at + COALESCE + Duration::from_millis(1)
    }

    /// Feed one state until the stack has had time to settle on it, as the
    /// app does frame after frame with nothing changing.
    fn settle(stack: &mut UndoStack, at: Duration, now: &State) -> Duration {
        stack.feed(at, now);
        let at = later(at);
        stack.feed(at, now);
        at
    }

    /// §7.2's coalescing rule, which is the whole reason navigation does not
    /// bury document edits: two camera moves inside the window are one press
    /// to take back, a third outside it is a second.
    #[test]
    fn two_camera_moves_inside_the_window_are_one_entry_and_a_third_outside_is_a_second() {
        let start = state();
        let mut stack = UndoStack::opening(&start);
        let mut at = Duration::ZERO;

        // Two moves in quick succession: neither settles, so neither is an
        // entry of its own.
        stack.feed(at, &looking_at(10.0));
        at += COALESCE / 3;
        stack.feed(at, &looking_at(20.0));
        at = settle(&mut stack, at, &looking_at(20.0));

        // A third, well clear of the window, and settled in turn.
        stack.feed(at, &looking_at(30.0));
        let at = settle(&mut stack, at, &looking_at(30.0));
        assert!(at > COALESCE, "precondition: the third move is a new entry");

        let here = looking_at(30.0);
        let first = stack.step(Direction::Back, &here).expect("one step back");
        assert_eq!(
            first.camera,
            vantage(20.0),
            "the third move was buried in the pair before it",
        );
        let second = stack.step(Direction::Back, &first).expect("two steps back");
        assert_eq!(
            second.camera, start.camera,
            "the two moves inside the window cost two presses instead of one",
        );
        assert!(
            stack.peek(Direction::Back, &second).is_none(),
            "the stack held more entries than the moves that were made",
        );
    }

    /// The other half of the same rule: a camera worked continuously — a
    /// pinch, a wheel spun down — never settles, so it leaves one entry
    /// rather than one per frame.
    #[test]
    fn a_camera_worked_without_pause_leaves_one_entry() {
        let start = state();
        let mut stack = UndoStack::opening(&start);
        let mut at = Duration::ZERO;
        for step in 1..=40 {
            at += COALESCE / 4;
            stack.feed(at, &looking_at(step as f32));
        }
        let here = looking_at(40.0);
        settle(&mut stack, at, &here);

        let back = stack.step(Direction::Back, &here).expect("one step back");
        assert_eq!(
            back.camera, start.camera,
            "a gesture's frames became entries of their own",
        );
        assert!(
            stack.peek(Direction::Back, &back).is_none(),
            "and only the one entry"
        );
    }

    /// The interleaving §7.1 asks for: entries of both kinds come back
    /// newest first, and an edit between two view moves keeps its own turn.
    #[test]
    fn doc_and_view_entries_come_back_in_the_order_they_were_made() {
        let start = state();
        let mut stack = UndoStack::opening(&start);
        let at = Duration::ZERO;

        let moved = looking_at(10.0);
        let at = settle(&mut stack, at, &moved);
        let one_edit = State {
            camera: moved.camera,
            ..edited(1)
        };
        stack.edited(at, &moved, &one_edit);
        let two_edits = State {
            camera: moved.camera,
            ..edited(2)
        };
        stack.edited(at, &one_edit, &two_edits);
        let wandered = State {
            camera: vantage(20.0),
            ..two_edits.clone()
        };
        let _ = settle(&mut stack, at, &wandered);

        let mut here = wandered;
        let mut walked = Vec::new();
        while let Some(back) = stack.step(Direction::Back, &here) {
            walked.push((back.stood, back.camera));
            here = back;
        }
        assert_eq!(
            walked,
            vec![
                (Stood(rev(2)), vantage(10.0)),
                (Stood(rev(1)), vantage(10.0)),
                (Stood(rev(0)), vantage(10.0)),
                (Stood(rev(0)), start.camera),
            ],
            "the walk skipped a kind or reordered the two",
        );
    }

    /// Two edits inside the coalescing window are still two presses: the
    /// window is §7.2's rule for *view* entries, and burying an edit under
    /// another edit is the thing it exists to prevent.
    #[test]
    fn edits_inside_the_coalescing_window_do_not_merge() {
        let start = state();
        let mut stack = UndoStack::opening(&start);
        let at = Duration::ZERO;
        let one = edited(1);
        let two = edited(2);
        stack.edited(at, &start, &one);
        stack.edited(at + COALESCE / 10, &one, &two);

        let back = stack.step(Direction::Back, &two).expect("one step back");
        assert_eq!(back.stood, Stood(rev(1)), "one press took back two edits");
    }

    /// Redo mirrors undo, and a new entry abandons the future — the one-stack
    /// rule, which a view entry obeys exactly as a document one does.
    #[test]
    fn redo_returns_to_where_undo_found_us_and_a_new_move_abandons_it() {
        let start = state();
        let mut stack = UndoStack::opening(&start);
        let moved = looking_at(10.0);
        let at = settle(&mut stack, Duration::ZERO, &moved);

        let back = stack.step(Direction::Back, &moved).expect("a step back");
        assert_eq!(back.camera, start.camera);
        assert!(
            stack.peek(Direction::Forward, &back).is_some(),
            "the move is not on the forward half"
        );
        let forward = stack.step(Direction::Forward, &back).expect("a step on");
        assert_eq!(forward.camera, moved.camera);

        let back = stack.step(Direction::Back, &forward).expect("a step back");
        let elsewhere = looking_at(99.0);
        stack.feed(later(at), &elsewhere);
        assert!(
            stack.peek(Direction::Forward, &back).is_none(),
            "a fresh move outlived the future it forked away from",
        );
    }

    /// A scope change is a view entry like a camera move — §7.1's table says
    /// `view` entries hold "camera state", and the scope is which drawing
    /// that camera is pointed at.
    #[test]
    fn a_scope_change_is_a_view_entry() {
        let start = state();
        let mut stack = UndoStack::opening(&start);
        let deeper = inside(7);
        assert_ne!(deeper.scope, start.scope, "precondition: the scope moved");
        settle(&mut stack, Duration::ZERO, &deeper);

        let back = stack.step(Direction::Back, &deeper).expect("a step back");
        assert_eq!(back.scope, start.scope);
        assert_eq!(back.stood, start.stood, "a scope change touched the log");
    }

    /// F6's editor half: a document whose trail came back from a log hands
    /// this stack a point per entry, both ways and in the trail's order.
    #[test]
    fn a_reconstructed_stack_walks_the_trail_it_came_from() {
        use blockworx_doc::trail::JournalAs;

        let mut trail = Trail::default();
        for at in 1..=3 {
            trail.record(rev(at), JournalAs::Edit);
        }
        trail.record(rev(4), JournalAs::Undo { of: rev(3) });
        assert_eq!(
            (trail.undo_depth(), trail.redo_depth()),
            (2, 1),
            "precondition: the trail has depth both ways to reproduce",
        );

        let here = State {
            stood: Stood::of(&trail),
            ..state()
        };
        let mut stack = UndoStack::reconstructed(&trail, &here);
        assert!(
            stack.peek(Direction::Back, &here).is_some(),
            "the reopened depth was not offered"
        );
        assert!(
            stack.peek(Direction::Forward, &here).is_some(),
            "the forward half was dropped"
        );

        let forward = stack.step(Direction::Forward, &here).expect("a step on");
        assert_eq!(
            forward.stood,
            Stood(rev(3)),
            "redo did not reach the trail's own future",
        );
        let mut walking = forward;
        let mut stops = Vec::new();
        while let Some(back) = stack.step(Direction::Back, &walking) {
            stops.push(back.stood);
            walking = back;
        }
        assert_eq!(
            stops,
            vec![Stood(rev(2)), Stood(rev(1)), Stood(rev(0))],
            "the walk back does not match the trail it was built from",
        );
    }

    /// The selection rides with a state but is not itself a state: picking
    /// something is how you reach an edit, not something to take back.
    #[test]
    fn a_selection_change_is_not_an_entry_of_its_own() {
        let start = state();
        let mut stack = UndoStack::opening(&start);
        let picked = State {
            selection: Some(shape(4)),
            ..state()
        };
        assert_eq!(picked, start, "the selection is outside the comparison");
        settle(&mut stack, Duration::ZERO, &picked);
        assert!(
            stack.peek(Direction::Back, &picked).is_none(),
            "picking something became something to take back",
        );
    }

    /// The selection-to-tool map, against a real document.
    #[test]
    fn a_restored_selection_resolves_to_the_tool_that_holds_it() {
        use crate::widget::test_fixtures::two_blocks_with_a_routed_waypoint;
        let mut scene = two_blocks_with_a_routed_waypoint();
        let drawing = scene.drawing();

        assert!(
            matches!(tool_for(&drawing, &[&shape(1)]), Tool::ResizeBlock(_)),
            "a selected block restores to the tool that shows its overlay",
        );
        assert!(
            matches!(tool_for(&drawing, &[]), Tool::Select(_)),
            "no candidate restores to plain select",
        );
    }

    /// The fallback in action: the first candidate is gone, so the second
    /// takes it — which is what stops an undo landing on nothing.
    #[test]
    fn a_candidate_the_document_lost_gives_way_to_the_next() {
        use crate::widget::test_fixtures::two_blocks_with_a_routed_waypoint;
        let mut scene = two_blocks_with_a_routed_waypoint();
        let drawing = scene.drawing();
        let gone = shape(200);
        assert!(
            drawing
                .shape(gone.what.shapes().expect("a shape")[0])
                .is_none(),
            "precondition: the document does not hold the first candidate",
        );

        assert!(
            matches!(
                tool_for(&drawing, &[&gone, &shape(1)]),
                Tool::ResizeBlock(_)
            ),
            "the surviving candidate is taken",
        );
        assert!(
            matches!(tool_for(&drawing, &[&gone]), Tool::Select(_)),
            "and with none surviving, nothing is selected",
        );
    }

    /// A route is picked at a point, not over its whole box, so restoring one
    /// needs the anchor back — without it there is no honest place to put the
    /// overlay, and the candidate is passed over.
    #[test]
    fn a_route_candidate_without_its_anchor_is_passed_over() {
        use crate::widget::test_fixtures::two_blocks_with_a_routed_waypoint;
        let mut scene = two_blocks_with_a_routed_waypoint();
        let drawing = scene.drawing();
        let route = drawing
            .auto_routes()
            .next()
            .map(|(id, _)| id)
            .expect("the fixture's route");

        let anchored = Selection {
            what: Deletable::Route(route),
            anchor: Some(pos2(30.0, 30.0)),
        };
        assert!(
            matches!(tool_for(&drawing, &[&anchored]), Tool::EditRoute(_)),
            "with its anchor, a route restores to the route editor",
        );
        let anchorless = Selection {
            anchor: None,
            ..anchored
        };
        assert!(matches!(
            tool_for(&drawing, &[&anchorless]),
            Tool::Select(_)
        ));
    }
}