1use ahash::AHashMap;
11use continuity_text::{EditOp, Selection};
12
13use crate::{Revision, UndoGroupId};
14
15#[derive(Clone, Debug)]
18pub struct EditRecord {
19 pub op: EditOp,
21 pub inverse_op: EditOp,
25 pub revision_before: Revision,
27 pub revision_after: Revision,
29 pub selections_before: Vec<Selection>,
31 pub selections_after: Vec<Selection>,
33}
34
35#[derive(Clone, Debug)]
38pub struct UndoGroup {
39 pub id: UndoGroupId,
41 pub parent: Option<UndoGroupId>,
43 pub ops: Vec<EditRecord>,
45 pub timestamp_ms: i64,
47 pub command: String,
50}
51
52impl UndoGroup {
53 #[must_use]
55 pub fn has_ops(&self) -> bool {
56 !self.ops.is_empty()
57 }
58}
59
60#[derive(Debug, Default, Clone)]
66pub struct UndoTree {
67 groups: Vec<UndoGroup>,
68 by_id: AHashMap<UndoGroupId, usize>,
69 current: Option<usize>,
72}
73
74impl UndoTree {
75 #[must_use]
77 pub fn new() -> Self {
78 Self::default()
79 }
80
81 #[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 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 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 #[must_use]
150 pub fn is_empty(&self) -> bool {
151 self.groups.is_empty()
152 }
153
154 #[must_use]
156 pub fn len(&self) -> usize {
157 self.groups.len()
158 }
159
160 #[must_use]
164 pub fn group_count(&self) -> usize {
165 self.groups.len()
166 }
167
168 #[must_use]
174 pub fn record_count(&self) -> usize {
175 self.groups.iter().map(|group| group.ops.len()).sum()
176 }
177
178 #[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 #[must_use]
189 pub fn current(&self) -> Option<&UndoGroup> {
190 self.current.map(|i| &self.groups[i])
191 }
192
193 #[must_use]
195 pub fn current_id(&self) -> Option<UndoGroupId> {
196 self.current().map(|g| g.id)
197 }
198
199 #[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 #[must_use]
207 pub fn groups(&self) -> &[UndoGroup] {
208 &self.groups
209 }
210
211 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 #[must_use]
233 pub fn group_to_undo(&self) -> Option<&UndoGroup> {
234 self.current()
235 }
236
237 #[must_use]
244 pub fn group_to_redo(&self) -> Option<&UndoGroup> {
245 self.children(self.current_id()).into_iter().next_back()
246 }
247
248 #[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 #[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
272fn 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 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 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}