Skip to main content

continuity_buffer/
undo.rs

1//! Per-buffer undo **tree**, persisted in `undo_groups` (and the edit log).
2//!
3//! Branches form when the user undoes a group and then makes a different
4//! edit instead of redoing — the new edit becomes a sibling rather than
5//! overwriting the redo branch (per spec §8).
6//!
7//! **Thread ownership**: only the caller-selected engine thread mutates an `UndoTree`;
8//! it lives inside [`crate::Buffer`].
9
10use ahash::AHashMap;
11use continuity_text::{EditOp, Selection};
12
13use crate::{Revision, UndoGroupId};
14
15/// One atomic edit recorded in an undo group, alongside the inverse op the
16/// undo path replays to revert it.
17#[derive(Clone, Debug)]
18pub struct EditRecord {
19    /// The op that was applied.
20    pub op: EditOp,
21    /// The op that, applied to the *post-edit* rope, restores the
22    /// *pre-edit* rope. Computed at record time when both the original
23    /// removed text and the post-edit positions are still in scope.
24    pub inverse_op: EditOp,
25    /// Buffer revision before [`Self::op`] was applied.
26    pub revision_before: Revision,
27    /// Buffer revision after [`Self::op`] was applied.
28    pub revision_after: Revision,
29    /// Selections at the time of the edit, before mutation.
30    pub selections_before: Vec<Selection>,
31    /// Selections after mutation.
32    pub selections_after: Vec<Selection>,
33}
34
35/// A coalesced unit of undo (typing in a single 500ms run, one paste, one
36/// multi-cursor edit, one find-replace fanout, etc.).
37#[derive(Clone, Debug)]
38pub struct UndoGroup {
39    /// Stable id (UUIDv7).
40    pub id: UndoGroupId,
41    /// The group's parent in the tree. `None` for the root group.
42    pub parent: Option<UndoGroupId>,
43    /// Edits in application order.
44    pub ops: Vec<EditRecord>,
45    /// Wall-clock millis of group creation.
46    pub timestamp_ms: i64,
47    /// The command that produced this group (for display in the picker and
48    /// the persisted `undo_groups.command_name` column).
49    pub command: String,
50}
51
52impl UndoGroup {
53    /// True iff this group has at least one recorded edit.
54    #[must_use]
55    pub fn has_ops(&self) -> bool {
56        !self.ops.is_empty()
57    }
58}
59
60/// The full per-buffer undo history.
61///
62/// The tree is append-only (groups never disappear from `groups` once
63/// recorded; the history-cap policy is implemented by snapshotting the
64/// content and dropping covered edit rows at the persistence layer).
65#[derive(Debug, Default, Clone)]
66pub struct UndoTree {
67    groups: Vec<UndoGroup>,
68    by_id: AHashMap<UndoGroupId, usize>,
69    /// Index of the group whose ops have been applied to the buffer; `None`
70    /// when the buffer is at the pre-history state.
71    current: Option<usize>,
72}
73
74impl UndoTree {
75    /// An empty tree (current = pre-history).
76    #[must_use]
77    pub fn new() -> Self {
78        Self::default()
79    }
80
81    /// Rebuild a tree from previously recorded groups and a head pointer.
82    ///
83    /// Distinct from replaying [`Self::insert_group`] per group: that call
84    /// re-parents a `None` parent onto whatever the head currently is, which
85    /// silently re-roots every root-level branch onto the group inserted
86    /// before it. A restore has to preserve the recorded shape exactly, so it
87    /// takes the groups as given. Unknown `current` ids fall back to
88    /// pre-history rather than panicking, because the input crossed a
89    /// serialization boundary and is not a caller invariant.
90    #[must_use]
91    pub fn restore(groups: Vec<UndoGroup>, current: Option<UndoGroupId>) -> Self {
92        let by_id = groups
93            .iter()
94            .enumerate()
95            .map(|(index, group)| (group.id, index))
96            .collect::<AHashMap<_, _>>();
97        let current = current.and_then(|id| by_id.get(&id).copied());
98        Self {
99            groups,
100            by_id,
101            current,
102        }
103    }
104
105    /// Insert an empty group rooted at `parent` (or at the current head if
106    /// `parent` is `None` and a current group exists). Returns the group's
107    /// stable id.
108    ///
109    /// Used both at edit time (when the engine mints a new group) and
110    /// at recovery time (when persisted rows are replayed).
111    pub fn insert_group(
112        &mut self,
113        id: UndoGroupId,
114        parent: Option<UndoGroupId>,
115        timestamp_ms: i64,
116        command: impl Into<String>,
117    ) {
118        let parent = parent.or_else(|| self.current_id());
119        let group = UndoGroup {
120            id,
121            parent,
122            ops: Vec::new(),
123            timestamp_ms,
124            command: command.into(),
125        };
126        let idx = self.groups.len();
127        self.by_id.insert(id, idx);
128        self.groups.push(group);
129        self.current = Some(idx);
130    }
131
132    /// Append an edit record to the named group. Touches `current` to point
133    /// at that group.
134    ///
135    /// # Panics
136    ///
137    /// Panics if `group_id` is unknown (caller-bug only — the core thread
138    /// always inserts the group before recording into it).
139    pub fn append_record(&mut self, group_id: UndoGroupId, record: EditRecord) {
140        let idx = *self
141            .by_id
142            .get(&group_id)
143            .expect("invariant: group recorded into without insert_group");
144        self.groups[idx].ops.push(record);
145        self.current = Some(idx);
146    }
147
148    /// True when no groups have been recorded.
149    #[must_use]
150    pub fn is_empty(&self) -> bool {
151        self.groups.is_empty()
152    }
153
154    /// Number of groups in the tree.
155    #[must_use]
156    pub fn len(&self) -> usize {
157        self.groups.len()
158    }
159
160    /// Number of [`UndoGroup`]s recorded. Alias for [`Self::len`],
161    /// surfaced separately because the trace stream emits
162    /// `undo_tree_groups=` and `undo_tree_records=` side by side.
163    #[must_use]
164    pub fn group_count(&self) -> usize {
165        self.groups.len()
166    }
167
168    /// Total number of [`EditRecord`]s across every group. Bumped by
169    /// every [`Self::append_record`] call; combined with
170    /// [`Self::byte_size_estimate`] this lets the memory_breakdown line
171    /// report bytes-per-record so Block 4.1 can prove its
172    /// `SmallVec<[Selection; 1]>` rewrite shrank per-record overhead.
173    #[must_use]
174    pub fn record_count(&self) -> usize {
175        self.groups.iter().map(|group| group.ops.len()).sum()
176    }
177
178    /// Estimated heap bytes retained by the undo tree.
179    #[must_use]
180    pub fn byte_size_estimate(&self) -> usize {
181        self.groups.capacity() * std::mem::size_of::<UndoGroup>()
182            + self.by_id.capacity()
183                * (std::mem::size_of::<UndoGroupId>() + std::mem::size_of::<usize>())
184            + self.groups.iter().map(undo_group_heap_bytes).sum::<usize>()
185    }
186
187    /// The currently-applied group, if any.
188    #[must_use]
189    pub fn current(&self) -> Option<&UndoGroup> {
190        self.current.map(|i| &self.groups[i])
191    }
192
193    /// Id of the currently-applied group.
194    #[must_use]
195    pub fn current_id(&self) -> Option<UndoGroupId> {
196        self.current().map(|g| g.id)
197    }
198
199    /// Borrow a group by id.
200    #[must_use]
201    pub fn get(&self, id: UndoGroupId) -> Option<&UndoGroup> {
202        self.by_id.get(&id).map(|&i| &self.groups[i])
203    }
204
205    /// Borrow every group in insertion order. Used by the picker UI.
206    #[must_use]
207    pub fn groups(&self) -> &[UndoGroup] {
208        &self.groups
209    }
210
211    /// Step the current pointer to `id`, asserting the group exists.
212    ///
213    /// # Panics
214    ///
215    /// Panics if `id` is unknown — the call sites compute targets only from
216    /// existing groups, so this is a structural invariant.
217    pub fn set_current(&mut self, id: Option<UndoGroupId>) {
218        match id {
219            None => self.current = None,
220            Some(id) => {
221                let idx = *self
222                    .by_id
223                    .get(&id)
224                    .expect("invariant: set_current with unknown group id");
225                self.current = Some(idx);
226            }
227        }
228    }
229
230    /// The group that an `editor.undo` from the current head would revert,
231    /// i.e. the current group itself.
232    #[must_use]
233    pub fn group_to_undo(&self) -> Option<&UndoGroup> {
234        self.current()
235    }
236
237    /// The group that an `editor.redo` from the current head would re-apply
238    /// — the most-recently-recorded direct child of the current head (or of
239    /// the pre-history root if `current` is `None`).
240    ///
241    /// The "most recent" tie-breaker matches the user's most recent intent:
242    /// if you undo and then redo, you redo the branch you just left.
243    #[must_use]
244    pub fn group_to_redo(&self) -> Option<&UndoGroup> {
245        self.children(self.current_id()).into_iter().next_back()
246    }
247
248    /// An alternate redo target: a child of the current pointer that is not
249    /// the one [`Self::group_to_redo`] would pick. Returns `None` when the
250    /// current pointer has fewer than two children.
251    ///
252    /// Used to step through fork branches after the user has undone past
253    /// the divergence point.
254    #[must_use]
255    pub fn group_to_redo_alternate(&self) -> Option<&UndoGroup> {
256        let kids = self.children(self.current_id());
257        if kids.len() < 2 {
258            return None;
259        }
260        let primary = kids.last()?.id;
261        kids.into_iter().find(|g| g.id != primary)
262    }
263
264    /// Direct children of `parent` in insertion order (oldest first).
265    /// `parent = None` returns the root-level branches.
266    #[must_use]
267    pub fn children(&self, parent: Option<UndoGroupId>) -> Vec<&UndoGroup> {
268        self.groups.iter().filter(|g| g.parent == parent).collect()
269    }
270}
271
272// Reserved trace event: `event:undo_tree_trim`. Emitted from the
273// trimming code path introduced by Block 4.2 of the memory
274// optimization plan (Emacs-style three-tier byte-budget undo cap).
275// The event is not produced anywhere yet — when the trimmer lands it
276// should emit `event:undo_tree_trim buffer=<id> tier=<soft|hard|panic>
277// dropped_groups=<n> dropped_records=<n> freed_bytes=<n>` so xtask
278// perf-report can correlate undo-tree shrinkage with the budget
279// trigger.
280
281fn undo_group_heap_bytes(group: &UndoGroup) -> usize {
282    group.command.capacity()
283        + group.ops.capacity() * std::mem::size_of::<EditRecord>()
284        + group.ops.iter().map(edit_record_heap_bytes).sum::<usize>()
285}
286
287fn edit_record_heap_bytes(record: &EditRecord) -> usize {
288    edit_op_heap_bytes(&record.op)
289        + edit_op_heap_bytes(&record.inverse_op)
290        + record.selections_before.capacity() * std::mem::size_of::<Selection>()
291        + record.selections_after.capacity() * std::mem::size_of::<Selection>()
292}
293
294fn edit_op_heap_bytes(op: &EditOp) -> usize {
295    match op {
296        EditOp::Insert { text, .. } | EditOp::Replace { text, .. } => text.capacity(),
297        EditOp::Delete { .. } => 0,
298    }
299}
300
301#[cfg(test)]
302mod tests {
303    use continuity_text::{Position, Range};
304
305    use super::*;
306
307    fn record(rev: u64) -> EditRecord {
308        EditRecord {
309            op: EditOp::insert(Position::ZERO, "x"),
310            inverse_op: EditOp::delete(Range::new(Position::ZERO, Position::new(0, 1))),
311            revision_before: Revision(rev - 1),
312            revision_after: Revision(rev),
313            selections_before: vec![],
314            selections_after: vec![],
315        }
316    }
317
318    #[test]
319    fn empty_tree_has_no_current() {
320        let t = UndoTree::new();
321        assert!(t.is_empty());
322        assert!(t.current().is_none());
323    }
324
325    #[test]
326    fn inserting_groups_links_parent_chain() {
327        let mut t = UndoTree::new();
328        let a = UndoGroupId::new();
329        t.insert_group(a, None, 0, "editor.insert_char");
330        t.append_record(a, record(1));
331        let b = UndoGroupId::new();
332        t.insert_group(b, None, 1, "editor.insert_char");
333        t.append_record(b, record(2));
334        assert_eq!(t.len(), 2);
335        assert_eq!(t.get(b).unwrap().parent, Some(a));
336        assert_eq!(t.current_id(), Some(b));
337    }
338
339    #[test]
340    fn group_to_undo_is_current() {
341        let mut t = UndoTree::new();
342        let a = UndoGroupId::new();
343        t.insert_group(a, None, 0, "x");
344        t.append_record(a, record(1));
345        assert_eq!(t.group_to_undo().map(|g| g.id), Some(a));
346    }
347
348    #[test]
349    fn group_to_redo_picks_most_recent_child() {
350        let mut t = UndoTree::new();
351        let a = UndoGroupId::new();
352        t.insert_group(a, None, 0, "x");
353        t.append_record(a, record(1));
354        let b = UndoGroupId::new();
355        t.insert_group(b, Some(a), 1, "y");
356        t.append_record(b, record(2));
357        // Branch after undoing back to a:
358        t.set_current(Some(a));
359        let c = UndoGroupId::new();
360        t.insert_group(c, Some(a), 2, "z");
361        t.append_record(c, record(3));
362        t.set_current(Some(a));
363        assert_eq!(t.group_to_redo().map(|g| g.id), Some(c));
364    }
365
366    #[test]
367    fn restore_preserves_shape_and_head() {
368        let mut original = UndoTree::new();
369        let a = UndoGroupId::new();
370        original.insert_group(a, None, 0, "x");
371        original.append_record(a, record(1));
372        let b = UndoGroupId::new();
373        original.insert_group(b, Some(a), 1, "y");
374        original.append_record(b, record(2));
375        original.set_current(Some(a));
376
377        let restored = UndoTree::restore(original.groups().to_vec(), original.current_id());
378        assert_eq!(restored.len(), 2);
379        assert_eq!(restored.current_id(), Some(a));
380        assert_eq!(restored.get(b).unwrap().parent, Some(a));
381        assert_eq!(restored.group_to_redo().map(|g| g.id), Some(b));
382    }
383
384    #[test]
385    fn restore_with_unknown_head_falls_back_to_pre_history() {
386        let mut original = UndoTree::new();
387        let a = UndoGroupId::new();
388        original.insert_group(a, None, 0, "x");
389        original.append_record(a, record(1));
390        let restored = UndoTree::restore(original.groups().to_vec(), Some(UndoGroupId::new()));
391        assert!(restored.current().is_none());
392        assert_eq!(restored.len(), 1);
393    }
394
395    #[test]
396    fn redo_alternate_picks_other_child() {
397        let mut t = UndoTree::new();
398        let a = UndoGroupId::new();
399        t.insert_group(a, None, 0, "x");
400        t.append_record(a, record(1));
401        let b = UndoGroupId::new();
402        t.insert_group(b, Some(a), 1, "y");
403        t.append_record(b, record(2));
404        t.set_current(Some(a));
405        let c = UndoGroupId::new();
406        t.insert_group(c, Some(a), 2, "z");
407        t.append_record(c, record(3));
408        t.set_current(Some(a));
409        // From parent `a`, the most-recent child is `c`; the alternate is `b`.
410        assert_eq!(t.group_to_redo().map(|g| g.id), Some(c));
411        assert_eq!(t.group_to_redo_alternate().map(|g| g.id), Some(b));
412    }
413}