use std::{collections::VecDeque, fmt, rc::Rc, sync::Arc};
use crate::{EventContext, Global, KeyBinding};
pub const MAX_UNDO_ENTRIES: usize = 256;
pub const MAX_UNDO_GROUP_ENTRIES: usize = 1_024;
pub const MAX_UNDO_ACTION_NAME_BYTES: usize = 256;
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub struct Undo;
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub struct Redo;
pub fn undo_key_bindings() -> [KeyBinding; 3] {
[
KeyBinding::new("cmd-z", Undo, None),
KeyBinding::new("cmd-shift-z", Redo, None),
KeyBinding::new("ctrl-y", Redo, None),
]
}
type UndoCallback<C> = Rc<dyn Fn(&mut C)>;
pub struct UndoEntry<C = EventContext> {
name: Arc<str>,
undo: UndoCallback<C>,
redo: UndoCallback<C>,
}
impl<C: 'static> UndoEntry<C> {
pub fn new(
name: impl Into<Arc<str>>,
undo: impl Fn(&mut C) + 'static,
redo: impl Fn(&mut C) + 'static,
) -> Self {
Self {
name: bounded_name(name.into()),
undo: Rc::new(undo),
redo: Rc::new(redo),
}
}
pub fn name(&self) -> &Arc<str> {
&self.name
}
}
impl<C> Clone for UndoEntry<C> {
fn clone(&self) -> Self {
Self {
name: self.name.clone(),
undo: self.undo.clone(),
redo: self.redo.clone(),
}
}
}
impl<C> fmt::Debug for UndoEntry<C> {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
formatter
.debug_struct("UndoEntry")
.field("name", &self.name)
.finish_non_exhaustive()
}
}
#[derive(Clone, Debug, Eq, PartialEq)]
#[must_use = "an UndoableChange has no effect until it is registered"]
pub struct UndoableChange<T> {
name: Arc<str>,
before: T,
after: T,
}
impl<T: Clone + 'static> UndoableChange<T> {
pub fn new(name: impl Into<Arc<str>>, before: T, after: T) -> Self {
Self {
name: bounded_name(name.into()),
before,
after,
}
}
pub fn name(&self) -> &Arc<str> {
&self.name
}
pub const fn before(&self) -> &T {
&self.before
}
pub const fn after(&self) -> &T {
&self.after
}
pub fn into_entry<C: 'static>(self, apply: impl Fn(&mut C, &T) + 'static) -> UndoEntry<C> {
let apply = Rc::new(apply);
let undo_apply = apply.clone();
let before = self.before;
let after = self.after;
UndoEntry::new(
self.name,
move |context: &mut C| undo_apply(context, &before),
move |context: &mut C| apply(context, &after),
)
}
}
#[derive(Debug)]
struct OpenGroup<C> {
name: Arc<str>,
entries: Vec<UndoEntry<C>>,
truncated: bool,
}
pub struct UndoManager<C = EventContext> {
undo: VecDeque<UndoEntry<C>>,
redo: VecDeque<UndoEntry<C>>,
group: Option<OpenGroup<C>>,
}
impl<C: 'static> Default for UndoManager<C> {
fn default() -> Self {
Self::new()
}
}
impl<C: 'static> Global for UndoManager<C> {}
impl<C> fmt::Debug for UndoManager<C> {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
formatter
.debug_struct("UndoManager")
.field("undo", &self.undo.len())
.field("redo", &self.redo.len())
.field("grouping", &self.group.is_some())
.finish()
}
}
impl<C: 'static> UndoManager<C> {
pub fn new() -> Self {
Self {
undo: VecDeque::new(),
redo: VecDeque::new(),
group: None,
}
}
pub fn register(&mut self, entry: UndoEntry<C>) {
if let Some(group) = &mut self.group {
if group.entries.len() == MAX_UNDO_GROUP_ENTRIES {
group.truncated = true;
return;
}
group.entries.push(entry);
return;
}
push_bounded(&mut self.undo, entry);
self.redo.clear();
}
pub fn begin_group(&mut self, name: impl Into<Arc<str>>) -> bool {
if self.group.is_some() {
return false;
}
self.group = Some(OpenGroup {
name: bounded_name(name.into()),
entries: Vec::new(),
truncated: false,
});
true
}
pub fn end_group(&mut self) -> bool {
let Some(group) = self.group.take() else {
return false;
};
if group.entries.is_empty() {
return false;
}
let undo_entries = group.entries.clone();
let redo_entries = group.entries;
let entry = UndoEntry {
name: group.name,
undo: Rc::new(move |context: &mut C| {
for entry in undo_entries.iter().rev() {
(entry.undo)(context);
}
}),
redo: Rc::new(move |context: &mut C| {
for entry in &redo_entries {
(entry.redo)(context);
}
}),
};
push_bounded(&mut self.undo, entry);
self.redo.clear();
true
}
pub fn cancel_group(&mut self) -> bool {
self.group.take().is_some()
}
pub const fn is_grouping(&self) -> bool {
self.group.is_some()
}
pub fn can_undo(&self) -> bool {
!self.undo.is_empty()
}
pub fn can_redo(&self) -> bool {
!self.redo.is_empty()
}
pub fn undo_action_name(&self) -> Option<&Arc<str>> {
self.undo.back().map(UndoEntry::name)
}
pub fn redo_action_name(&self) -> Option<&Arc<str>> {
self.redo.back().map(UndoEntry::name)
}
pub fn undo_len(&self) -> usize {
self.undo.len()
}
pub fn redo_len(&self) -> usize {
self.redo.len()
}
pub fn clear(&mut self) {
self.undo.clear();
self.redo.clear();
self.group = None;
}
pub fn undo(&mut self, context: &mut C) -> bool {
let Some(entry) = self.undo.pop_back() else {
return false;
};
(entry.undo)(context);
push_bounded(&mut self.redo, entry);
true
}
pub fn redo(&mut self, context: &mut C) -> bool {
let Some(entry) = self.redo.pop_back() else {
return false;
};
(entry.redo)(context);
push_bounded(&mut self.undo, entry);
true
}
pub fn undo_unless_handled(&mut self, handled_by_text_input: bool, context: &mut C) -> bool {
!handled_by_text_input && self.undo(context)
}
pub fn redo_unless_handled(&mut self, handled_by_text_input: bool, context: &mut C) -> bool {
!handled_by_text_input && self.redo(context)
}
}
fn push_bounded<C>(stack: &mut VecDeque<UndoEntry<C>>, entry: UndoEntry<C>) {
while stack.len() >= MAX_UNDO_ENTRIES {
stack.pop_front();
}
stack.push_back(entry);
}
fn bounded_name(name: Arc<str>) -> Arc<str> {
if name.len() <= MAX_UNDO_ACTION_NAME_BYTES {
return name;
}
let mut end = MAX_UNDO_ACTION_NAME_BYTES;
while !name.is_char_boundary(end) {
end -= 1;
}
Arc::from(&name[..end])
}
#[cfg(test)]
mod tests {
use super::*;
use std::cell::RefCell;
#[derive(Default)]
struct Document {
text: String,
applied: usize,
}
fn set_text(name: &str, before: &str, after: &str) -> UndoEntry<Document> {
UndoableChange::new(name, before.to_owned(), after.to_owned()).into_entry(
|document: &mut Document, value: &String| {
document.text = value.clone();
document.applied += 1;
},
)
}
#[test]
fn undo_and_redo_replay_named_changes() {
let mut manager = UndoManager::<Document>::new();
let mut document = Document::default();
assert!(!manager.can_undo());
assert!(manager.undo_action_name().is_none());
document.text = "one".to_owned();
manager.register(set_text("Typing", "", "one"));
document.text = "one two".to_owned();
manager.register(set_text("Paste", "one", "one two"));
assert_eq!(manager.undo_action_name().map(Arc::as_ref), Some("Paste"));
assert!(manager.undo(&mut document));
assert_eq!(document.text, "one");
assert_eq!(manager.redo_action_name().map(Arc::as_ref), Some("Paste"));
assert_eq!(manager.undo_action_name().map(Arc::as_ref), Some("Typing"));
assert!(manager.redo(&mut document));
assert_eq!(document.text, "one two");
assert!(manager.undo(&mut document));
assert!(manager.undo(&mut document));
assert_eq!(document.text, "");
assert!(!manager.undo(&mut document));
}
#[test]
fn registering_a_change_clears_the_redo_stack() {
let mut manager = UndoManager::<Document>::new();
let mut document = Document::default();
manager.register(set_text("Typing", "", "a"));
assert!(manager.undo(&mut document));
assert!(manager.can_redo());
manager.register(set_text("Typing", "", "b"));
assert!(!manager.can_redo());
assert!(manager.redo_action_name().is_none());
}
#[test]
fn groups_undo_and_redo_as_one_named_entry_in_the_right_order() {
let order = Rc::new(RefCell::new(Vec::new()));
let mut manager = UndoManager::<Document>::new();
let mut document = Document::default();
assert!(manager.begin_group("Format Table"));
assert!(!manager.begin_group("Nested"));
assert!(manager.is_grouping());
for step in 0..3_usize {
let order = order.clone();
let undo_order = order.clone();
manager.register(UndoEntry::new(
"step",
move |_: &mut Document| undo_order.borrow_mut().push(format!("undo {step}")),
move |_: &mut Document| order.borrow_mut().push(format!("redo {step}")),
));
}
assert_eq!(manager.undo_len(), 0);
assert!(manager.end_group());
assert_eq!(manager.undo_len(), 1);
assert_eq!(
manager.undo_action_name().map(Arc::as_ref),
Some("Format Table")
);
assert!(manager.undo(&mut document));
assert_eq!(
order.borrow().as_slice(),
["undo 2", "undo 1", "undo 0"].map(str::to_owned)
);
order.borrow_mut().clear();
assert!(manager.redo(&mut document));
assert_eq!(
order.borrow().as_slice(),
["redo 0", "redo 1", "redo 2"].map(str::to_owned)
);
}
#[test]
fn empty_and_cancelled_groups_record_nothing() {
let mut manager = UndoManager::<Document>::new();
assert!(manager.begin_group("Empty"));
assert!(!manager.end_group());
assert_eq!(manager.undo_len(), 0);
assert!(manager.begin_group("Cancelled"));
manager.register(set_text("step", "", "x"));
assert!(manager.cancel_group());
assert_eq!(manager.undo_len(), 0);
assert!(!manager.cancel_group());
assert!(!manager.end_group());
}
#[test]
fn history_and_names_stay_bounded() {
let mut manager = UndoManager::<Document>::new();
for index in 0..(MAX_UNDO_ENTRIES + 64) {
manager.register(set_text("Typing", "", &index.to_string()));
}
assert_eq!(manager.undo_len(), MAX_UNDO_ENTRIES);
let long = "é".repeat(MAX_UNDO_ACTION_NAME_BYTES);
manager.register(set_text(&long, "", ""));
let name = manager.undo_action_name().unwrap();
assert!(name.len() <= MAX_UNDO_ACTION_NAME_BYTES);
assert!(std::str::from_utf8(name.as_bytes()).is_ok());
manager.begin_group("Wide");
for index in 0..(MAX_UNDO_GROUP_ENTRIES + 8) {
manager.register(set_text("step", "", &index.to_string()));
}
assert!(manager.end_group());
assert_eq!(manager.undo_action_name().map(Arc::as_ref), Some("Wide"));
manager.clear();
assert!(!manager.can_undo());
assert!(!manager.can_redo());
assert!(!manager.is_grouping());
}
#[test]
fn routing_defers_to_a_focused_text_input() {
let mut manager = UndoManager::<Document>::new();
let mut document = Document::default();
manager.register(set_text("Typing", "", "a"));
assert!(!manager.undo_unless_handled(true, &mut document));
assert_eq!(manager.undo_len(), 1);
assert!(manager.undo_unless_handled(false, &mut document));
assert_eq!(manager.undo_len(), 0);
assert!(!manager.redo_unless_handled(true, &mut document));
assert!(manager.redo_unless_handled(false, &mut document));
assert_eq!(document.applied, 2);
}
#[test]
fn undo_key_bindings_cover_both_platform_conventions() {
let bindings = undo_key_bindings();
assert_eq!(bindings.len(), 3);
assert!(
bindings
.iter()
.any(|binding| binding.action().downcast_ref::<Undo>().is_some())
);
assert_eq!(
bindings
.iter()
.filter(|binding| binding.action().downcast_ref::<Redo>().is_some())
.count(),
2
);
}
}