use ahash::AHashMap;
use continuity_text::{EditOp, Selection};
use crate::{Revision, UndoGroupId};
#[derive(Clone, Debug)]
pub struct EditRecord {
pub op: EditOp,
pub inverse_op: EditOp,
pub revision_before: Revision,
pub revision_after: Revision,
pub selections_before: Vec<Selection>,
pub selections_after: Vec<Selection>,
}
#[derive(Clone, Debug)]
pub struct UndoGroup {
pub id: UndoGroupId,
pub parent: Option<UndoGroupId>,
pub ops: Vec<EditRecord>,
pub timestamp_ms: i64,
pub command: String,
}
impl UndoGroup {
#[must_use]
pub fn has_ops(&self) -> bool {
!self.ops.is_empty()
}
}
#[derive(Debug, Default, Clone)]
pub struct UndoTree {
groups: Vec<UndoGroup>,
by_id: AHashMap<UndoGroupId, usize>,
current: Option<usize>,
}
impl UndoTree {
#[must_use]
pub fn new() -> Self {
Self::default()
}
#[must_use]
pub fn restore(groups: Vec<UndoGroup>, current: Option<UndoGroupId>) -> Self {
let by_id = groups
.iter()
.enumerate()
.map(|(index, group)| (group.id, index))
.collect::<AHashMap<_, _>>();
let current = current.and_then(|id| by_id.get(&id).copied());
Self {
groups,
by_id,
current,
}
}
pub fn insert_group(
&mut self,
id: UndoGroupId,
parent: Option<UndoGroupId>,
timestamp_ms: i64,
command: impl Into<String>,
) {
let parent = parent.or_else(|| self.current_id());
let group = UndoGroup {
id,
parent,
ops: Vec::new(),
timestamp_ms,
command: command.into(),
};
let idx = self.groups.len();
self.by_id.insert(id, idx);
self.groups.push(group);
self.current = Some(idx);
}
pub fn append_record(&mut self, group_id: UndoGroupId, record: EditRecord) {
let idx = *self
.by_id
.get(&group_id)
.expect("invariant: group recorded into without insert_group");
self.groups[idx].ops.push(record);
self.current = Some(idx);
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.groups.is_empty()
}
#[must_use]
pub fn len(&self) -> usize {
self.groups.len()
}
#[must_use]
pub fn group_count(&self) -> usize {
self.groups.len()
}
#[must_use]
pub fn record_count(&self) -> usize {
self.groups.iter().map(|group| group.ops.len()).sum()
}
#[must_use]
pub fn byte_size_estimate(&self) -> usize {
self.groups.capacity() * std::mem::size_of::<UndoGroup>()
+ self.by_id.capacity()
* (std::mem::size_of::<UndoGroupId>() + std::mem::size_of::<usize>())
+ self.groups.iter().map(undo_group_heap_bytes).sum::<usize>()
}
#[must_use]
pub fn current(&self) -> Option<&UndoGroup> {
self.current.map(|i| &self.groups[i])
}
#[must_use]
pub fn current_id(&self) -> Option<UndoGroupId> {
self.current().map(|g| g.id)
}
#[must_use]
pub fn get(&self, id: UndoGroupId) -> Option<&UndoGroup> {
self.by_id.get(&id).map(|&i| &self.groups[i])
}
#[must_use]
pub fn groups(&self) -> &[UndoGroup] {
&self.groups
}
pub fn set_current(&mut self, id: Option<UndoGroupId>) {
match id {
None => self.current = None,
Some(id) => {
let idx = *self
.by_id
.get(&id)
.expect("invariant: set_current with unknown group id");
self.current = Some(idx);
}
}
}
#[must_use]
pub fn group_to_undo(&self) -> Option<&UndoGroup> {
self.current()
}
#[must_use]
pub fn group_to_redo(&self) -> Option<&UndoGroup> {
self.children(self.current_id()).into_iter().next_back()
}
#[must_use]
pub fn group_to_redo_alternate(&self) -> Option<&UndoGroup> {
let kids = self.children(self.current_id());
if kids.len() < 2 {
return None;
}
let primary = kids.last()?.id;
kids.into_iter().find(|g| g.id != primary)
}
#[must_use]
pub fn children(&self, parent: Option<UndoGroupId>) -> Vec<&UndoGroup> {
self.groups.iter().filter(|g| g.parent == parent).collect()
}
}
fn undo_group_heap_bytes(group: &UndoGroup) -> usize {
group.command.capacity()
+ group.ops.capacity() * std::mem::size_of::<EditRecord>()
+ group.ops.iter().map(edit_record_heap_bytes).sum::<usize>()
}
fn edit_record_heap_bytes(record: &EditRecord) -> usize {
edit_op_heap_bytes(&record.op)
+ edit_op_heap_bytes(&record.inverse_op)
+ record.selections_before.capacity() * std::mem::size_of::<Selection>()
+ record.selections_after.capacity() * std::mem::size_of::<Selection>()
}
fn edit_op_heap_bytes(op: &EditOp) -> usize {
match op {
EditOp::Insert { text, .. } | EditOp::Replace { text, .. } => text.capacity(),
EditOp::Delete { .. } => 0,
}
}
#[cfg(test)]
mod tests {
use continuity_text::{Position, Range};
use super::*;
fn record(rev: u64) -> EditRecord {
EditRecord {
op: EditOp::insert(Position::ZERO, "x"),
inverse_op: EditOp::delete(Range::new(Position::ZERO, Position::new(0, 1))),
revision_before: Revision(rev - 1),
revision_after: Revision(rev),
selections_before: vec![],
selections_after: vec![],
}
}
#[test]
fn empty_tree_has_no_current() {
let t = UndoTree::new();
assert!(t.is_empty());
assert!(t.current().is_none());
}
#[test]
fn inserting_groups_links_parent_chain() {
let mut t = UndoTree::new();
let a = UndoGroupId::new();
t.insert_group(a, None, 0, "editor.insert_char");
t.append_record(a, record(1));
let b = UndoGroupId::new();
t.insert_group(b, None, 1, "editor.insert_char");
t.append_record(b, record(2));
assert_eq!(t.len(), 2);
assert_eq!(t.get(b).unwrap().parent, Some(a));
assert_eq!(t.current_id(), Some(b));
}
#[test]
fn group_to_undo_is_current() {
let mut t = UndoTree::new();
let a = UndoGroupId::new();
t.insert_group(a, None, 0, "x");
t.append_record(a, record(1));
assert_eq!(t.group_to_undo().map(|g| g.id), Some(a));
}
#[test]
fn group_to_redo_picks_most_recent_child() {
let mut t = UndoTree::new();
let a = UndoGroupId::new();
t.insert_group(a, None, 0, "x");
t.append_record(a, record(1));
let b = UndoGroupId::new();
t.insert_group(b, Some(a), 1, "y");
t.append_record(b, record(2));
t.set_current(Some(a));
let c = UndoGroupId::new();
t.insert_group(c, Some(a), 2, "z");
t.append_record(c, record(3));
t.set_current(Some(a));
assert_eq!(t.group_to_redo().map(|g| g.id), Some(c));
}
#[test]
fn restore_preserves_shape_and_head() {
let mut original = UndoTree::new();
let a = UndoGroupId::new();
original.insert_group(a, None, 0, "x");
original.append_record(a, record(1));
let b = UndoGroupId::new();
original.insert_group(b, Some(a), 1, "y");
original.append_record(b, record(2));
original.set_current(Some(a));
let restored = UndoTree::restore(original.groups().to_vec(), original.current_id());
assert_eq!(restored.len(), 2);
assert_eq!(restored.current_id(), Some(a));
assert_eq!(restored.get(b).unwrap().parent, Some(a));
assert_eq!(restored.group_to_redo().map(|g| g.id), Some(b));
}
#[test]
fn restore_with_unknown_head_falls_back_to_pre_history() {
let mut original = UndoTree::new();
let a = UndoGroupId::new();
original.insert_group(a, None, 0, "x");
original.append_record(a, record(1));
let restored = UndoTree::restore(original.groups().to_vec(), Some(UndoGroupId::new()));
assert!(restored.current().is_none());
assert_eq!(restored.len(), 1);
}
#[test]
fn redo_alternate_picks_other_child() {
let mut t = UndoTree::new();
let a = UndoGroupId::new();
t.insert_group(a, None, 0, "x");
t.append_record(a, record(1));
let b = UndoGroupId::new();
t.insert_group(b, Some(a), 1, "y");
t.append_record(b, record(2));
t.set_current(Some(a));
let c = UndoGroupId::new();
t.insert_group(c, Some(a), 2, "z");
t.append_record(c, record(3));
t.set_current(Some(a));
assert_eq!(t.group_to_redo().map(|g| g.id), Some(c));
assert_eq!(t.group_to_redo_alternate().map(|g| g.id), Some(b));
}
}