use std::borrow::Cow;
use std::collections::VecDeque;
pub trait Command: std::fmt::Debug {
type Target;
type Error: std::fmt::Debug;
fn apply(&mut self, target: &mut Self::Target) -> Result<(), Self::Error>;
fn reverse(&mut self, target: &mut Self::Target) -> Result<(), Self::Error>;
#[must_use]
fn description(&self) -> &str;
}
impl<T, E> Command for Box<dyn Command<Target = T, Error = E>>
where
E: std::fmt::Debug,
{
type Target = T;
type Error = E;
fn apply(&mut self, target: &mut T) -> Result<(), E> {
(**self).apply(target)
}
fn reverse(&mut self, target: &mut T) -> Result<(), E> {
(**self).reverse(target)
}
fn description(&self) -> &str {
(**self).description()
}
}
#[derive(Debug, Clone)]
pub struct CompoundCommand<C> {
commands: Vec<C>,
description: Cow<'static, str>,
}
impl<C> CompoundCommand<C> {
#[must_use]
#[inline]
pub fn new(description: &'static str, commands: Vec<C>) -> Self {
Self {
commands,
description: Cow::Borrowed(description),
}
}
#[must_use]
#[inline]
pub fn with_description(description: String, commands: Vec<C>) -> Self {
Self {
commands,
description: Cow::Owned(description),
}
}
#[must_use]
#[inline]
pub fn len(&self) -> usize {
self.commands.len()
}
#[must_use]
#[inline]
pub fn is_empty(&self) -> bool {
self.commands.is_empty()
}
#[must_use]
#[inline]
pub fn commands(&self) -> &[C] {
&self.commands
}
}
impl<C: Command> Command for CompoundCommand<C> {
type Target = C::Target;
type Error = C::Error;
fn apply(&mut self, target: &mut Self::Target) -> Result<(), Self::Error> {
for (i, cmd) in self.commands.iter_mut().enumerate() {
if let Err(e) = cmd.apply(target) {
tracing::error!(
failed_at = i,
total = self.commands.len(),
"compound apply failed, rolling back"
);
for rollback in self.commands[..i].iter_mut().rev() {
if let Err(rollback_err) = rollback.reverse(target) {
tracing::error!(?rollback_err, "rollback failed during compound apply");
}
}
return Err(e);
}
}
tracing::debug!(count = self.commands.len(), desc = %self.description, "compound applied");
Ok(())
}
fn reverse(&mut self, target: &mut Self::Target) -> Result<(), Self::Error> {
for cmd in self.commands.iter_mut().rev() {
cmd.reverse(target)?;
}
tracing::debug!(count = self.commands.len(), desc = %self.description, "compound reversed");
Ok(())
}
#[inline]
fn description(&self) -> &str {
&self.description
}
}
const DEFAULT_MAX_DEPTH: usize = 256;
#[derive(Debug, Clone)]
pub struct CommandHistory<C> {
undo_stack: VecDeque<C>,
redo_stack: Vec<C>,
max_depth: usize,
}
impl<C> CommandHistory<C> {
#[must_use]
pub fn new() -> Self {
Self {
undo_stack: VecDeque::new(),
redo_stack: Vec::new(),
max_depth: DEFAULT_MAX_DEPTH,
}
}
#[must_use]
pub fn with_max_depth(max_depth: usize) -> Self {
Self {
undo_stack: VecDeque::with_capacity(max_depth),
redo_stack: Vec::new(),
max_depth,
}
}
#[must_use]
#[inline]
pub fn can_undo(&self) -> bool {
!self.undo_stack.is_empty()
}
#[must_use]
#[inline]
pub fn can_redo(&self) -> bool {
!self.redo_stack.is_empty()
}
#[must_use]
#[inline]
pub fn undo_count(&self) -> usize {
self.undo_stack.len()
}
#[must_use]
#[inline]
pub fn redo_count(&self) -> usize {
self.redo_stack.len()
}
#[must_use]
#[inline]
pub fn max_depth(&self) -> usize {
self.max_depth
}
pub fn clear(&mut self) {
self.undo_stack.clear();
self.redo_stack.clear();
tracing::debug!("command history cleared");
}
}
impl<C: Command> CommandHistory<C> {
pub fn push(&mut self, cmd: C) {
tracing::debug!(desc = cmd.description(), "command pushed (no apply)");
self.redo_stack.clear();
if self.max_depth == 0 {
return;
}
if self.undo_stack.len() >= self.max_depth {
self.undo_stack.pop_front();
}
self.undo_stack.push_back(cmd);
}
pub fn execute(&mut self, mut cmd: C, target: &mut C::Target) -> Result<(), C::Error> {
cmd.apply(target)?;
tracing::debug!(desc = cmd.description(), "command executed");
self.redo_stack.clear();
if self.max_depth == 0 {
return Ok(());
}
if self.undo_stack.len() >= self.max_depth {
self.undo_stack.pop_front();
}
self.undo_stack.push_back(cmd);
Ok(())
}
pub fn undo(&mut self, target: &mut C::Target) -> Result<bool, C::Error> {
let Some(mut cmd) = self.undo_stack.pop_back() else {
return Ok(false);
};
tracing::debug!(desc = cmd.description(), "undoing");
if let Err(e) = cmd.reverse(target) {
self.undo_stack.push_back(cmd);
return Err(e);
}
self.redo_stack.push(cmd);
Ok(true)
}
pub fn redo(&mut self, target: &mut C::Target) -> Result<bool, C::Error> {
let Some(mut cmd) = self.redo_stack.pop() else {
return Ok(false);
};
tracing::debug!(desc = cmd.description(), "redoing");
if let Err(e) = cmd.apply(target) {
self.redo_stack.push(cmd);
return Err(e);
}
self.undo_stack.push_back(cmd);
Ok(true)
}
}
impl<C> Default for CommandHistory<C> {
fn default() -> Self {
Self::new()
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::convert::Infallible;
#[derive(Debug)]
struct PushCmd {
value: i32,
}
impl Command for PushCmd {
type Target = Vec<i32>;
type Error = Infallible;
fn apply(&mut self, target: &mut Vec<i32>) -> Result<(), Infallible> {
target.push(self.value);
Ok(())
}
fn reverse(&mut self, target: &mut Vec<i32>) -> Result<(), Infallible> {
target.pop();
Ok(())
}
fn description(&self) -> &str {
"push"
}
}
#[derive(Debug)]
struct RemoveLastCmd {
removed: Option<i32>,
}
impl RemoveLastCmd {
fn new() -> Self {
Self { removed: None }
}
}
impl Command for RemoveLastCmd {
type Target = Vec<i32>;
type Error = Infallible;
fn apply(&mut self, target: &mut Vec<i32>) -> Result<(), Infallible> {
self.removed = target.pop();
Ok(())
}
fn reverse(&mut self, target: &mut Vec<i32>) -> Result<(), Infallible> {
if let Some(v) = self.removed {
target.push(v);
}
Ok(())
}
fn description(&self) -> &str {
"remove last"
}
}
#[derive(Debug)]
struct FailOnThreshold {
value: i32,
threshold: usize,
}
impl Command for FailOnThreshold {
type Target = Vec<i32>;
type Error = String;
fn apply(&mut self, target: &mut Vec<i32>) -> Result<(), String> {
if target.len() >= self.threshold {
return Err("threshold reached".into());
}
target.push(self.value);
Ok(())
}
fn reverse(&mut self, target: &mut Vec<i32>) -> Result<(), String> {
target.pop();
Ok(())
}
fn description(&self) -> &str {
"fail on threshold"
}
}
#[test]
fn apply_and_reverse() {
let mut target = vec![];
let mut cmd = PushCmd { value: 42 };
cmd.apply(&mut target).unwrap();
assert_eq!(target, vec![42]);
cmd.reverse(&mut target).unwrap();
assert!(target.is_empty());
}
#[test]
fn lazy_state_capture() {
let mut target = vec![10, 20, 30];
let mut cmd = RemoveLastCmd::new();
assert!(cmd.removed.is_none());
cmd.apply(&mut target).unwrap();
assert_eq!(target, vec![10, 20]);
assert_eq!(cmd.removed, Some(30));
cmd.reverse(&mut target).unwrap();
assert_eq!(target, vec![10, 20, 30]);
}
#[test]
fn infallible_commands_compile() {
let mut target = vec![];
let mut cmd = PushCmd { value: 1 };
let result: Result<(), Infallible> = cmd.apply(&mut target);
assert!(result.is_ok());
}
#[test]
fn compound_apply_in_order() {
let mut target = vec![];
let mut compound = CompoundCommand::new(
"push three",
vec![
PushCmd { value: 1 },
PushCmd { value: 2 },
PushCmd { value: 3 },
],
);
compound.apply(&mut target).unwrap();
assert_eq!(target, vec![1, 2, 3]);
}
#[test]
fn compound_reverse_in_reverse_order() {
let mut target = vec![];
let mut compound = CompoundCommand::new(
"push three",
vec![
PushCmd { value: 1 },
PushCmd { value: 2 },
PushCmd { value: 3 },
],
);
compound.apply(&mut target).unwrap();
compound.reverse(&mut target).unwrap();
assert!(target.is_empty());
}
#[test]
fn compound_partial_failure_rollback() {
let mut target = vec![];
let mut compound = CompoundCommand::new(
"fail on second",
vec![
FailOnThreshold {
value: 1,
threshold: 5,
},
FailOnThreshold {
value: 2,
threshold: 1, },
FailOnThreshold {
value: 3,
threshold: 5,
},
],
);
let result = compound.apply(&mut target);
assert!(result.is_err());
assert!(target.is_empty());
}
#[test]
fn compound_empty() {
let mut target: Vec<i32> = vec![1, 2, 3];
let mut compound: CompoundCommand<PushCmd> = CompoundCommand::new("empty", vec![]);
compound.apply(&mut target).unwrap();
assert_eq!(target, vec![1, 2, 3]);
compound.reverse(&mut target).unwrap();
assert_eq!(target, vec![1, 2, 3]);
}
#[test]
fn compound_accessors() {
let compound =
CompoundCommand::new("test", vec![PushCmd { value: 1 }, PushCmd { value: 2 }]);
assert_eq!(compound.len(), 2);
assert!(!compound.is_empty());
assert_eq!(compound.commands().len(), 2);
assert_eq!(compound.description(), "test");
}
#[test]
fn compound_with_dynamic_description() {
let compound =
CompoundCommand::with_description("dynamic".to_string(), vec![PushCmd { value: 1 }]);
assert_eq!(compound.description(), "dynamic");
}
#[test]
fn history_execute() {
let mut target = vec![];
let mut history = CommandHistory::new();
history.execute(PushCmd { value: 1 }, &mut target).unwrap();
history.execute(PushCmd { value: 2 }, &mut target).unwrap();
history.execute(PushCmd { value: 3 }, &mut target).unwrap();
assert_eq!(target, vec![1, 2, 3]);
assert_eq!(history.undo_count(), 3);
assert_eq!(history.redo_count(), 0);
}
#[test]
fn history_undo() {
let mut target = vec![];
let mut history = CommandHistory::new();
history.execute(PushCmd { value: 1 }, &mut target).unwrap();
history.execute(PushCmd { value: 2 }, &mut target).unwrap();
assert!(history.undo(&mut target).unwrap());
assert_eq!(target, vec![1]);
assert_eq!(history.undo_count(), 1);
assert_eq!(history.redo_count(), 1);
}
#[test]
fn history_redo() {
let mut target = vec![];
let mut history = CommandHistory::new();
history.execute(PushCmd { value: 1 }, &mut target).unwrap();
history.undo(&mut target).unwrap();
assert!(target.is_empty());
assert!(history.redo(&mut target).unwrap());
assert_eq!(target, vec![1]);
}
#[test]
fn history_undo_redo_roundtrip() {
let mut target = vec![];
let mut history = CommandHistory::new();
history.execute(PushCmd { value: 1 }, &mut target).unwrap();
history.execute(PushCmd { value: 2 }, &mut target).unwrap();
history.execute(PushCmd { value: 3 }, &mut target).unwrap();
history.undo(&mut target).unwrap();
history.undo(&mut target).unwrap();
assert_eq!(target, vec![1]);
history.redo(&mut target).unwrap();
history.redo(&mut target).unwrap();
assert_eq!(target, vec![1, 2, 3]);
}
#[test]
fn history_undo_empty() {
let mut target: Vec<i32> = vec![];
let mut history: CommandHistory<PushCmd> = CommandHistory::new();
assert!(!history.undo(&mut target).unwrap());
}
#[test]
fn history_redo_empty() {
let mut target: Vec<i32> = vec![];
let mut history: CommandHistory<PushCmd> = CommandHistory::new();
assert!(!history.redo(&mut target).unwrap());
}
#[test]
fn history_execute_clears_redo() {
let mut target = vec![];
let mut history = CommandHistory::new();
history.execute(PushCmd { value: 1 }, &mut target).unwrap();
history.execute(PushCmd { value: 2 }, &mut target).unwrap();
history.undo(&mut target).unwrap();
assert!(history.can_redo());
history.execute(PushCmd { value: 3 }, &mut target).unwrap();
assert!(!history.can_redo());
assert_eq!(target, vec![1, 3]);
}
#[test]
fn history_max_depth_eviction() {
let mut target = vec![];
let mut history = CommandHistory::with_max_depth(3);
for i in 0..5 {
history.execute(PushCmd { value: i }, &mut target).unwrap();
}
assert_eq!(history.undo_count(), 3); assert_eq!(history.max_depth(), 3);
}
#[test]
fn history_clear() {
let mut target = vec![];
let mut history = CommandHistory::new();
history.execute(PushCmd { value: 1 }, &mut target).unwrap();
history.execute(PushCmd { value: 2 }, &mut target).unwrap();
history.undo(&mut target).unwrap();
history.clear();
assert!(!history.can_undo());
assert!(!history.can_redo());
assert_eq!(history.undo_count(), 0);
assert_eq!(history.redo_count(), 0);
}
#[test]
fn history_push_without_apply() {
let mut target = vec![10, 20];
let mut history = CommandHistory::new();
history.push(PushCmd { value: 99 });
assert_eq!(target, vec![10, 20]);
assert_eq!(history.undo_count(), 1);
assert!(!history.can_redo());
history.undo(&mut target).unwrap();
assert_eq!(target, vec![10]); assert_eq!(history.undo_count(), 0);
assert_eq!(history.redo_count(), 1);
}
#[test]
fn history_push_clears_redo() {
let mut target = vec![];
let mut history = CommandHistory::new();
history.execute(PushCmd { value: 1 }, &mut target).unwrap();
history.undo(&mut target).unwrap();
assert!(history.can_redo());
history.push(PushCmd { value: 2 });
assert!(!history.can_redo());
}
#[test]
fn history_push_respects_max_depth() {
let mut history = CommandHistory::with_max_depth(2);
history.push(PushCmd { value: 1 });
history.push(PushCmd { value: 2 });
history.push(PushCmd { value: 3 });
assert_eq!(history.undo_count(), 2); }
#[test]
fn history_max_depth_zero() {
let mut target = vec![];
let mut history = CommandHistory::with_max_depth(0);
history.execute(PushCmd { value: 1 }, &mut target).unwrap();
assert_eq!(target, vec![1]);
assert_eq!(history.undo_count(), 0);
history.push(PushCmd { value: 2 });
assert_eq!(history.undo_count(), 0);
}
#[test]
fn history_nested_compound() {
let mut target = vec![];
let inner = CompoundCommand::new("inner", vec![PushCmd { value: 1 }, PushCmd { value: 2 }]);
let outer = CompoundCommand::new("outer", vec![inner]);
let mut history: CommandHistory<CompoundCommand<CompoundCommand<PushCmd>>> =
CommandHistory::new();
history.execute(outer, &mut target).unwrap();
assert_eq!(target, vec![1, 2]);
history.undo(&mut target).unwrap();
assert!(target.is_empty());
}
#[test]
fn history_default() {
let history: CommandHistory<PushCmd> = CommandHistory::default();
assert_eq!(history.max_depth(), DEFAULT_MAX_DEPTH);
assert!(history.undo_stack.is_empty());
}
#[derive(Debug)]
struct FailReverse;
impl Command for FailReverse {
type Target = Vec<i32>;
type Error = String;
fn apply(&mut self, target: &mut Vec<i32>) -> Result<(), String> {
target.push(99);
Ok(())
}
fn reverse(&mut self, _target: &mut Vec<i32>) -> Result<(), String> {
Err("reverse failed".into())
}
fn description(&self) -> &str {
"fail reverse"
}
}
#[test]
fn history_failed_undo_preserves_command() {
let mut target = vec![];
let mut history: CommandHistory<FailReverse> = CommandHistory::new();
history.execute(FailReverse, &mut target).unwrap();
assert_eq!(history.undo_count(), 1);
let result = history.undo(&mut target);
assert!(result.is_err());
assert_eq!(history.undo_count(), 1);
assert_eq!(history.redo_count(), 0);
}
#[test]
fn history_failed_redo_preserves_command() {
#[derive(Debug)]
struct FailSecondApply {
count: usize,
}
impl Command for FailSecondApply {
type Target = Vec<i32>;
type Error = String;
fn apply(&mut self, target: &mut Vec<i32>) -> Result<(), String> {
self.count += 1;
if self.count > 1 {
return Err("second apply failed".into());
}
target.push(1);
Ok(())
}
fn reverse(&mut self, target: &mut Vec<i32>) -> Result<(), String> {
target.pop();
Ok(())
}
fn description(&self) -> &str {
"fail second apply"
}
}
let mut target = vec![];
let mut history = CommandHistory::new();
history
.execute(FailSecondApply { count: 0 }, &mut target)
.unwrap();
history.undo(&mut target).unwrap();
assert_eq!(history.redo_count(), 1);
let result = history.redo(&mut target);
assert!(result.is_err());
assert_eq!(history.redo_count(), 1);
assert_eq!(history.undo_count(), 0);
}
#[test]
fn history_max_depth_one() {
let mut target = vec![];
let mut history = CommandHistory::with_max_depth(1);
history.execute(PushCmd { value: 1 }, &mut target).unwrap();
history.execute(PushCmd { value: 2 }, &mut target).unwrap();
assert_eq!(history.undo_count(), 1);
history.undo(&mut target).unwrap();
assert_eq!(target, vec![1]); }
#[test]
fn history_compound_through_history() {
let mut target = vec![];
let mut history: CommandHistory<CompoundCommand<PushCmd>> = CommandHistory::new();
let compound = CompoundCommand::new(
"batch push",
vec![
PushCmd { value: 10 },
PushCmd { value: 20 },
PushCmd { value: 30 },
],
);
history.execute(compound, &mut target).unwrap();
assert_eq!(target, vec![10, 20, 30]);
assert_eq!(history.undo_count(), 1);
history.undo(&mut target).unwrap();
assert!(target.is_empty());
history.redo(&mut target).unwrap();
assert_eq!(target, vec![10, 20, 30]);
}
}