ochrepad_core/
history.rs

1//! Undo/redo over [`Transaction`]s, with coalescing of consecutive typing,
2//! and the history kept between sessions ([`SavedHistory`], PLAN_v0.3.0
3//! 3.3).
4
5use std::time::Duration;
6
7use serde::{Deserialize, Serialize};
8
9use crate::changeset::ChangeSet;
10use crate::selection::SelectionSet;
11use crate::text::Document;
12
13/// The concrete result of resolving an action: the edits plus the selections
14/// before and after.
15#[derive(Clone, Debug, Serialize, Deserialize)]
16pub struct Transaction {
17    pub changes: ChangeSet,
18    pub inverse: ChangeSet,
19    pub before: SelectionSet,
20    pub after: SelectionSet,
21}
22
23/// Which consecutive edits may merge into one undo step.
24#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
25pub enum EditKind {
26    /// A single grapheme typed at every caret (not a newline).
27    Insert,
28    DeleteBackward,
29    DeleteForward,
30    /// Never coalesces.
31    Other,
32}
33
34/// Typing pauses longer than this start a new undo step.
35pub const COALESCE_TIMEOUT: Duration = Duration::from_secs(1);
36
37/// Identifies a document state. Undo/redo restore the state's revision, so
38/// `revision == saved_revision` exactly when the text matches the saved file.
39pub type Revision = u64;
40
41#[derive(Clone, Debug, Serialize, Deserialize)]
42pub struct UndoStep {
43    pub txns: Vec<Transaction>,
44    pub kind: EditKind,
45    pub rev_before: Revision,
46    pub rev_after: Revision,
47    /// For coalescing; not kept between sessions.
48    #[serde(skip)]
49    last_edit_at: Duration,
50}
51
52impl UndoStep {
53    /// Roughly how many bytes the step takes saved: its text, and a little
54    /// for each edit and selection.
55    pub fn approx_size(&self) -> usize {
56        self.txns
57            .iter()
58            .map(|t| {
59                let edits = t.changes.edits().iter().chain(t.inverse.edits());
60                let sels = t.before.len() + t.after.len();
61                edits.map(|e| e.text.len() + 48).sum::<usize>() + sels * 40 + 64
62            })
63            .sum()
64    }
65}
66
67/// An undo history as kept between sessions: the steps, and the revision of
68/// the text they end at. It belongs to one exact text; whoever stores it
69/// also stores that text's [`sha256_hex`] and restores it only onto the
70/// same text.
71#[derive(Clone, Debug, Default, Serialize, Deserialize)]
72pub struct SavedHistory {
73    /// Oldest first, like [`History`]'s stacks.
74    pub undo: Vec<UndoStep>,
75    /// The next step to redo last.
76    pub redo: Vec<UndoStep>,
77    /// The revision of the text the history ends at.
78    pub revision: Revision,
79    /// Greater than every revision in the history.
80    pub next_revision: Revision,
81}
82
83impl SavedHistory {
84    pub fn is_empty(&self) -> bool {
85        self.undo.is_empty() && self.redo.is_empty()
86    }
87
88    /// Checks the history against `doc`, the text it should end at: the
89    /// revisions connect, and every step's edits and selections fit the
90    /// text they apply to (the earlier texts are rebuilt by undoing, the
91    /// later ones by redoing). A damaged or mismatched file fails here
92    /// instead of corrupting the document or crashing later.
93    pub fn check(&self, doc: &Document) -> Result<(), String> {
94        // Revisions only ever count up from 0 by one per edit.
95        if self.next_revision > Revision::MAX / 2 || self.revision >= self.next_revision {
96            return Err("a revision is out of range".into());
97        }
98        let all = self.undo.iter().chain(&self.redo);
99        if all
100            .clone()
101            .any(|s| s.rev_before >= self.next_revision || s.rev_after >= self.next_revision)
102        {
103            return Err("a revision is out of range".into());
104        }
105        if self
106            .undo
107            .last()
108            .is_some_and(|s| s.rev_after != self.revision)
109            || self
110                .redo
111                .last()
112                .is_some_and(|s| s.rev_before != self.revision)
113            || self
114                .undo
115                .windows(2)
116                .any(|w| w[0].rev_after != w[1].rev_before)
117            || self
118                .redo
119                .windows(2)
120                .any(|w| w[1].rev_after != w[0].rev_before)
121        {
122            return Err("the steps do not connect".into());
123        }
124        if all.clone().any(|s| s.txns.is_empty()) {
125            return Err("a step is empty".into());
126        }
127        let bad = |what: &str| Err(format!("{what} does not fit the text"));
128        let mut d = doc.clone();
129        for t in self.undo.iter().rev().flat_map(|s| s.txns.iter().rev()) {
130            if !t.after.fits(&d) || !t.inverse.fits(&d) {
131                return bad("an undo step");
132            }
133            t.inverse.apply(&mut d);
134            if !t.changes.fits(&d) || !t.before.fits(&d) {
135                return bad("an undo step");
136            }
137        }
138        let mut d = doc.clone();
139        for t in self.redo.iter().rev().flat_map(|s| s.txns.iter()) {
140            if !t.before.fits(&d) || !t.changes.fits(&d) {
141                return bad("a redo step");
142            }
143            t.changes.apply(&mut d);
144            if !t.inverse.fits(&d) || !t.after.fits(&d) {
145                return bad("a redo step");
146            }
147        }
148        Ok(())
149    }
150}
151
152/// The SHA-256 of a document's text, as lowercase hex: what a saved history
153/// is checked against.
154pub fn sha256_hex(doc: &Document) -> String {
155    use sha2::{Digest, Sha256};
156    let mut hasher = Sha256::new();
157    for chunk in doc.chunks() {
158        hasher.update(chunk.as_bytes());
159    }
160    hasher
161        .finalize()
162        .iter()
163        .map(|b| format!("{b:02x}"))
164        .collect()
165}
166
167#[derive(Clone, Debug, Default)]
168pub struct History {
169    undo: Vec<UndoStep>,
170    redo: Vec<UndoStep>,
171    /// False after cursor movement, undo/redo or save: the next edit starts a
172    /// new step even if it would otherwise coalesce.
173    coalesce_open: bool,
174    /// Nesting depth of explicit groups (macro playback, replace all).
175    group_depth: usize,
176    /// Whether the open group already has a step on the undo stack.
177    group_started: bool,
178}
179
180impl History {
181    pub fn push(
182        &mut self,
183        txn: Transaction,
184        kind: EditKind,
185        rev_before: Revision,
186        rev_after: Revision,
187        now: Duration,
188    ) {
189        self.redo.clear();
190        let extend_top = if self.group_depth > 0 {
191            self.group_started
192        } else {
193            self.coalesce_open
194                && kind != EditKind::Other
195                && self.undo.last().is_some_and(|top| {
196                    top.kind == kind
197                        && top.rev_after == rev_before
198                        && now.saturating_sub(top.last_edit_at) <= COALESCE_TIMEOUT
199                })
200        };
201        match self.undo.last_mut() {
202            Some(top) if extend_top => {
203                top.txns.push(txn);
204                top.rev_after = rev_after;
205                top.last_edit_at = now;
206            }
207            _ => self.undo.push(UndoStep {
208                txns: vec![txn],
209                kind,
210                rev_before,
211                rev_after,
212                last_edit_at: now,
213            }),
214        }
215        self.group_started = self.group_depth > 0;
216        self.coalesce_open = true;
217    }
218
219    pub fn break_coalescing(&mut self) {
220        self.coalesce_open = false;
221    }
222
223    /// Everything pushed until the matching `end_group` becomes one undo step.
224    pub fn begin_group(&mut self) {
225        if self.group_depth == 0 {
226            self.group_started = false;
227        }
228        self.group_depth += 1;
229    }
230
231    pub fn end_group(&mut self) {
232        self.group_depth = self.group_depth.saturating_sub(1);
233        if self.group_depth == 0 {
234            self.group_started = false;
235            self.coalesce_open = false;
236        }
237    }
238
239    pub fn can_undo(&self) -> bool {
240        !self.undo.is_empty()
241    }
242
243    pub fn can_redo(&self) -> bool {
244        !self.redo.is_empty()
245    }
246
247    pub(crate) fn pop_undo(&mut self) -> Option<UndoStep> {
248        self.coalesce_open = false;
249        self.group_started = false;
250        self.undo.pop()
251    }
252
253    pub(crate) fn push_redo(&mut self, step: UndoStep) {
254        self.redo.push(step);
255    }
256
257    pub(crate) fn pop_redo(&mut self) -> Option<UndoStep> {
258        self.coalesce_open = false;
259        self.group_started = false;
260        self.redo.pop()
261    }
262
263    pub(crate) fn push_undo(&mut self, step: UndoStep) {
264        self.undo.push(step);
265    }
266
267    /// The newest steps whose [`approx_size`](UndoStep::approx_size) adds
268    /// up to at most `max_bytes`: the redo steps nearest the current text
269    /// first, then undo steps from the most recent back. Returns (undo,
270    /// redo), oldest first.
271    pub(crate) fn newest(&self, max_bytes: usize) -> (Vec<UndoStep>, Vec<UndoStep>) {
272        let mut budget = max_bytes;
273        let mut take = |steps: &[UndoStep]| {
274            let mut kept: Vec<UndoStep> = Vec::new();
275            for s in steps.iter().rev() {
276                let size = s.approx_size();
277                if size > budget {
278                    break;
279                }
280                budget -= size;
281                kept.push(s.clone());
282            }
283            kept.reverse();
284            kept
285        };
286        let redo = take(&self.redo);
287        let undo = take(&self.undo);
288        (undo, redo)
289    }
290
291    /// Replaces the stacks with ones from an earlier session. Coalescing
292    /// starts afresh: the next edit is a new step.
293    pub(crate) fn replace(&mut self, undo: Vec<UndoStep>, redo: Vec<UndoStep>) {
294        *self = History {
295            undo,
296            redo,
297            ..History::default()
298        };
299    }
300
301    /// Forgets every step.
302    pub fn clear(&mut self) {
303        *self = History::default();
304    }
305
306    /// Text was appended to the document outside the history (follow
307    /// mode): every step still applies, to a document `by` bytes longer.
308    /// The appended text stays when steps are undone. The current text is
309    /// now revision `new` (it was `old`), so undoing and redoing back to it
310    /// finds the new revision.
311    pub(crate) fn extend_base(&mut self, by: usize, old: Revision, new: Revision) {
312        for step in self.undo.iter_mut().chain(self.redo.iter_mut()) {
313            for t in &mut step.txns {
314                t.changes.extend_base(by);
315                t.inverse.extend_base(by);
316            }
317        }
318        if let Some(top) = self.undo.last_mut().filter(|s| s.rev_after == old) {
319            top.rev_after = new;
320        }
321        if let Some(next) = self.redo.last_mut().filter(|s| s.rev_before == old) {
322            next.rev_before = new;
323        }
324        self.coalesce_open = false;
325    }
326}
ochrepad_core/history.rs

ochrepad_core/
history.rs
