ftui_runtime/
reversible.rs

1//! Reversible computing primitives for undo.
2//!
3//! Each mutation knows its own inverse. This complements the command-pattern
4//! undo system in [`crate::undo`] with operation-level reversibility that
5//! composes algebraically.
6//!
7//! # Core Idea
8//!
9//! A [`Reversible`] operation can be run forward or backward:
10//! ```
11//! use ftui_runtime::reversible::{Reversible, AddOp, Sequence};
12//!
13//! let mut x = 10u64;
14//! let op = AddOp::new(3);
15//!
16//! op.forward(&mut x);
17//! assert_eq!(x, 13);
18//!
19//! op.backward(&mut x);
20//! assert_eq!(x, 10);
21//! ```
22//!
23//! Operations compose into sequences that undo in reverse order:
24//! ```
25//! use ftui_runtime::reversible::{Reversible, AddOp, Sequence};
26//!
27//! let mut x = 0u64;
28//! let ops = Sequence::new(vec![
29//!     Box::new(AddOp::new(10)),
30//!     Box::new(AddOp::new(20)),
31//! ]);
32//!
33//! ops.forward(&mut x);
34//! assert_eq!(x, 30);
35//!
36//! ops.backward(&mut x);
37//! assert_eq!(x, 0);
38//! ```
39
40use std::fmt;
41
42/// A reversible operation on state `S`.
43///
44/// # Laws
45///
46/// 1. **Round-trip**: `forward(s); backward(s)` restores `s` to its original value.
47/// 2. **Round-trip (reverse)**: `backward(s); forward(s)` also restores `s`.
48pub trait Reversible<S>: fmt::Debug {
49    /// Apply the operation.
50    fn forward(&self, state: &mut S);
51
52    /// Undo the operation (apply the inverse).
53    fn backward(&self, state: &mut S);
54
55    /// Human-readable description of this operation.
56    fn description(&self) -> &str {
57        "reversible op"
58    }
59}
60
61// ── Arithmetic ops ──────────────────────────────────────────────────
62
63/// Reversible addition: `state += delta` / `state -= delta`.
64#[derive(Debug, Clone, Copy)]
65pub struct AddOp<T> {
66    delta: T,
67}
68
69impl<T> AddOp<T> {
70    pub fn new(delta: T) -> Self {
71        Self { delta }
72    }
73}
74
75macro_rules! impl_add_op {
76    ($($ty:ty),*) => {
77        $(
78            impl Reversible<$ty> for AddOp<$ty> {
79                fn forward(&self, state: &mut $ty) {
80                    *state = state.wrapping_add(self.delta);
81                }
82
83                fn backward(&self, state: &mut $ty) {
84                    *state = state.wrapping_sub(self.delta);
85                }
86
87                fn description(&self) -> &str {
88                    "add"
89                }
90            }
91        )*
92    };
93}
94
95impl_add_op!(u8, u16, u32, u64, usize, i8, i16, i32, i64, isize);
96
97impl Reversible<f64> for AddOp<f64> {
98    fn forward(&self, state: &mut f64) {
99        *state += self.delta;
100    }
101
102    fn backward(&self, state: &mut f64) {
103        *state -= self.delta;
104    }
105
106    fn description(&self) -> &str {
107        "add_f64"
108    }
109}
110
111impl Reversible<f32> for AddOp<f32> {
112    fn forward(&self, state: &mut f32) {
113        *state += self.delta;
114    }
115
116    fn backward(&self, state: &mut f32) {
117        *state -= self.delta;
118    }
119
120    fn description(&self) -> &str {
121        "add_f32"
122    }
123}
124
125/// Reversible XOR: `state ^= mask` (self-inverse).
126#[derive(Debug, Clone, Copy)]
127pub struct XorOp<T> {
128    mask: T,
129}
130
131impl<T> XorOp<T> {
132    pub fn new(mask: T) -> Self {
133        Self { mask }
134    }
135}
136
137macro_rules! impl_xor_op {
138    ($($ty:ty),*) => {
139        $(
140            impl Reversible<$ty> for XorOp<$ty> {
141                fn forward(&self, state: &mut $ty) {
142                    *state ^= self.mask;
143                }
144
145                fn backward(&self, state: &mut $ty) {
146                    // XOR is its own inverse
147                    *state ^= self.mask;
148                }
149
150                fn description(&self) -> &str {
151                    "xor"
152                }
153            }
154        )*
155    };
156}
157
158impl_xor_op!(u8, u16, u32, u64, usize);
159
160/// Reversible multiplication: `state *= factor` / `state /= factor`.
161///
162/// Only valid for non-zero factors. For integer types, uses wrapping arithmetic.
163#[derive(Debug, Clone, Copy)]
164pub struct MulOp<T> {
165    factor: T,
166}
167
168impl<T> MulOp<T> {
169    pub fn new(factor: T) -> Self {
170        Self { factor }
171    }
172}
173
174impl Reversible<f64> for MulOp<f64> {
175    fn forward(&self, state: &mut f64) {
176        *state *= self.factor;
177    }
178
179    fn backward(&self, state: &mut f64) {
180        *state /= self.factor;
181    }
182
183    fn description(&self) -> &str {
184        "mul_f64"
185    }
186}
187
188// ── Swap ops ────────────────────────────────────────────────────────
189
190/// Reversible swap of two elements in a slice.
191#[derive(Debug, Clone, Copy)]
192pub struct SwapOp {
193    i: usize,
194    j: usize,
195}
196
197impl SwapOp {
198    pub fn new(i: usize, j: usize) -> Self {
199        Self { i, j }
200    }
201}
202
203impl<T> Reversible<Vec<T>> for SwapOp {
204    fn forward(&self, state: &mut Vec<T>) {
205        state.swap(self.i, self.j);
206    }
207
208    fn backward(&self, state: &mut Vec<T>) {
209        // Swap is its own inverse
210        state.swap(self.i, self.j);
211    }
212
213    fn description(&self) -> &str {
214        "swap"
215    }
216}
217
218// ── Set/Replace ops ─────────────────────────────────────────────────
219
220/// Reversible field set: captures old value for undo.
221#[derive(Debug, Clone)]
222pub struct SetOp<T> {
223    new_value: T,
224    old_value: T,
225}
226
227impl<T: Clone> SetOp<T> {
228    /// Create a set operation. `old_value` is the current value before the set.
229    pub fn new(old_value: T, new_value: T) -> Self {
230        Self {
231            new_value,
232            old_value,
233        }
234    }
235}
236
237impl<T: Clone + fmt::Debug> Reversible<T> for SetOp<T> {
238    fn forward(&self, state: &mut T) {
239        *state = self.new_value.clone();
240    }
241
242    fn backward(&self, state: &mut T) {
243        *state = self.old_value.clone();
244    }
245
246    fn description(&self) -> &str {
247        "set"
248    }
249}
250
251// ── Collection ops ──────────────────────────────────────────────────
252
253/// Reversible push to a Vec.
254#[derive(Debug, Clone)]
255pub struct PushOp<T> {
256    value: T,
257}
258
259impl<T: Clone> PushOp<T> {
260    pub fn new(value: T) -> Self {
261        Self { value }
262    }
263}
264
265impl<T: Clone + fmt::Debug> Reversible<Vec<T>> for PushOp<T> {
266    fn forward(&self, state: &mut Vec<T>) {
267        state.push(self.value.clone());
268    }
269
270    fn backward(&self, state: &mut Vec<T>) {
271        state.pop();
272    }
273
274    fn description(&self) -> &str {
275        "push"
276    }
277}
278
279/// Reversible insert at index.
280#[derive(Debug, Clone)]
281pub struct InsertOp<T> {
282    index: usize,
283    value: T,
284}
285
286impl<T: Clone> InsertOp<T> {
287    pub fn new(index: usize, value: T) -> Self {
288        Self { index, value }
289    }
290}
291
292impl<T: Clone + fmt::Debug> Reversible<Vec<T>> for InsertOp<T> {
293    fn forward(&self, state: &mut Vec<T>) {
294        state.insert(self.index, self.value.clone());
295    }
296
297    fn backward(&self, state: &mut Vec<T>) {
298        state.remove(self.index);
299    }
300
301    fn description(&self) -> &str {
302        "insert"
303    }
304}
305
306/// Reversible remove at index (captures removed value for undo).
307#[derive(Debug, Clone)]
308pub struct RemoveOp<T> {
309    index: usize,
310    removed: Option<T>,
311}
312
313impl<T: Clone> RemoveOp<T> {
314    pub fn new(index: usize) -> Self {
315        Self {
316            index,
317            removed: None,
318        }
319    }
320}
321
322impl<T: Clone + fmt::Debug> Reversible<Vec<T>> for RemoveOp<T> {
323    fn forward(&self, state: &mut Vec<T>) {
324        state.remove(self.index);
325    }
326
327    fn backward(&self, state: &mut Vec<T>) {
328        if let Some(val) = &self.removed {
329            state.insert(self.index, val.clone());
330        }
331    }
332
333    fn description(&self) -> &str {
334        "remove"
335    }
336}
337
338/// Create a `RemoveOp` that captures the value at `index` for undo.
339pub fn remove_capturing<T: Clone>(state: &[T], index: usize) -> RemoveOp<T> {
340    RemoveOp {
341        index,
342        removed: state.get(index).cloned(),
343    }
344}
345
346// ── Sequence (composition) ──────────────────────────────────────────
347
348/// A sequence of reversible operations applied in order.
349///
350/// `forward` applies all operations left-to-right.
351/// `backward` undoes them right-to-left (stack discipline).
352pub struct Sequence<S> {
353    ops: Vec<Box<dyn Reversible<S>>>,
354    label: &'static str,
355}
356
357impl<S> fmt::Debug for Sequence<S> {
358    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
359        f.debug_struct("Sequence")
360            .field("len", &self.ops.len())
361            .field("label", &self.label)
362            .finish()
363    }
364}
365
366impl<S> Sequence<S> {
367    /// Create a sequence from a list of operations.
368    pub fn new(ops: Vec<Box<dyn Reversible<S>>>) -> Self {
369        Self {
370            ops,
371            label: "sequence",
372        }
373    }
374
375    /// Create an empty sequence.
376    pub fn empty() -> Self {
377        Self {
378            ops: Vec::new(),
379            label: "sequence",
380        }
381    }
382
383    /// Set a label for this sequence.
384    pub fn with_label(mut self, label: &'static str) -> Self {
385        self.label = label;
386        self
387    }
388
389    /// Add an operation to the sequence.
390    pub fn push(&mut self, op: Box<dyn Reversible<S>>) {
391        self.ops.push(op);
392    }
393
394    /// Number of operations in the sequence.
395    pub fn len(&self) -> usize {
396        self.ops.len()
397    }
398
399    /// Whether the sequence is empty.
400    pub fn is_empty(&self) -> bool {
401        self.ops.is_empty()
402    }
403}
404
405impl<S> Reversible<S> for Sequence<S> {
406    fn forward(&self, state: &mut S) {
407        for op in &self.ops {
408            op.forward(state);
409        }
410    }
411
412    fn backward(&self, state: &mut S) {
413        for op in self.ops.iter().rev() {
414            op.backward(state);
415        }
416    }
417
418    fn description(&self) -> &str {
419        self.label
420    }
421}
422
423// ── Recording journal ───────────────────────────────────────────────
424
425/// A journal that records operations as they are applied, enabling undo.
426pub struct Journal<S> {
427    applied: Vec<Box<dyn Reversible<S>>>,
428    undone: Vec<Box<dyn Reversible<S>>>,
429}
430
431impl<S> fmt::Debug for Journal<S> {
432    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
433        f.debug_struct("Journal")
434            .field("applied", &self.applied.len())
435            .field("undone", &self.undone.len())
436            .finish()
437    }
438}
439
440impl<S> Journal<S> {
441    /// Create an empty journal.
442    pub fn new() -> Self {
443        Self {
444            applied: Vec::new(),
445            undone: Vec::new(),
446        }
447    }
448
449    /// Apply an operation and record it.
450    pub fn apply(&mut self, op: Box<dyn Reversible<S>>, state: &mut S) {
451        op.forward(state);
452        self.applied.push(op);
453        self.undone.clear(); // new operations invalidate redo stack
454    }
455
456    /// Undo the last operation.
457    pub fn undo(&mut self, state: &mut S) -> bool {
458        if let Some(op) = self.applied.pop() {
459            op.backward(state);
460            self.undone.push(op);
461            true
462        } else {
463            false
464        }
465    }
466
467    /// Redo the last undone operation.
468    pub fn redo(&mut self, state: &mut S) -> bool {
469        if let Some(op) = self.undone.pop() {
470            op.forward(state);
471            self.applied.push(op);
472            true
473        } else {
474            false
475        }
476    }
477
478    /// Number of operations that can be undone.
479    pub fn undo_count(&self) -> usize {
480        self.applied.len()
481    }
482
483    /// Number of operations that can be redone.
484    pub fn redo_count(&self) -> usize {
485        self.undone.len()
486    }
487
488    /// Clear all history.
489    pub fn clear(&mut self) {
490        self.applied.clear();
491        self.undone.clear();
492    }
493}
494
495impl<S> Default for Journal<S> {
496    fn default() -> Self {
497        Self::new()
498    }
499}
500
501#[cfg(test)]
502mod tests {
503    use super::*;
504
505    // ── AddOp ───────────────────────────────────────────────────────
506
507    #[test]
508    fn add_forward_backward() {
509        let mut x = 10u64;
510        let op = AddOp::new(5u64);
511        op.forward(&mut x);
512        assert_eq!(x, 15);
513        op.backward(&mut x);
514        assert_eq!(x, 10);
515    }
516
517    #[test]
518    fn add_signed() {
519        let mut x = 0i32;
520        let op = AddOp::new(-5i32);
521        op.forward(&mut x);
522        assert_eq!(x, -5);
523        op.backward(&mut x);
524        assert_eq!(x, 0);
525    }
526
527    #[test]
528    fn add_f64_roundtrip() {
529        let mut x = 1.0f64;
530        let op = AddOp::new(0.5);
531        op.forward(&mut x);
532        assert!((x - 1.5).abs() < f64::EPSILON);
533        op.backward(&mut x);
534        assert!((x - 1.0).abs() < f64::EPSILON);
535    }
536
537    // ── XorOp ───────────────────────────────────────────────────────
538
539    #[test]
540    fn xor_is_self_inverse() {
541        let mut x = 0xFFu8;
542        let op = XorOp::new(0x0Fu8);
543        op.forward(&mut x);
544        assert_eq!(x, 0xF0);
545        op.backward(&mut x);
546        assert_eq!(x, 0xFF);
547    }
548
549    #[test]
550    fn xor_double_apply_is_identity() {
551        let mut x = 42u64;
552        let op = XorOp::new(123u64);
553        op.forward(&mut x);
554        op.forward(&mut x); // XOR twice = identity
555        assert_eq!(x, 42);
556    }
557
558    // ── MulOp ───────────────────────────────────────────────────────
559
560    #[test]
561    fn mul_f64_roundtrip() {
562        let mut x = 4.0f64;
563        let op = MulOp::new(2.5);
564        op.forward(&mut x);
565        assert!((x - 10.0).abs() < f64::EPSILON);
566        op.backward(&mut x);
567        assert!((x - 4.0).abs() < f64::EPSILON);
568    }
569
570    // ── SwapOp ──────────────────────────────────────────────────────
571
572    #[test]
573    fn swap_roundtrip() {
574        let mut v = vec![1, 2, 3, 4, 5];
575        let op = SwapOp::new(0, 4);
576        op.forward(&mut v);
577        assert_eq!(v, vec![5, 2, 3, 4, 1]);
578        op.backward(&mut v);
579        assert_eq!(v, vec![1, 2, 3, 4, 5]);
580    }
581
582    #[test]
583    fn swap_same_index_is_noop() {
584        let mut v = vec![1, 2, 3];
585        let op = SwapOp::new(1, 1);
586        op.forward(&mut v);
587        assert_eq!(v, vec![1, 2, 3]);
588    }
589
590    // ── SetOp ───────────────────────────────────────────────────────
591
592    #[test]
593    fn set_roundtrip() {
594        let mut x = "hello".to_string();
595        let op = SetOp::new("hello".to_string(), "world".to_string());
596        op.forward(&mut x);
597        assert_eq!(x, "world");
598        op.backward(&mut x);
599        assert_eq!(x, "hello");
600    }
601
602    // ── PushOp ──────────────────────────────────────────────────────
603
604    #[test]
605    fn push_roundtrip() {
606        let mut v: Vec<u32> = vec![1, 2];
607        let op = PushOp::new(3u32);
608        op.forward(&mut v);
609        assert_eq!(v, vec![1, 2, 3]);
610        op.backward(&mut v);
611        assert_eq!(v, vec![1, 2]);
612    }
613
614    // ── InsertOp ────────────────────────────────────────────────────
615
616    #[test]
617    fn insert_roundtrip() {
618        let mut v = vec![1, 3, 4];
619        let op = InsertOp::new(1, 2);
620        op.forward(&mut v);
621        assert_eq!(v, vec![1, 2, 3, 4]);
622        op.backward(&mut v);
623        assert_eq!(v, vec![1, 3, 4]);
624    }
625
626    // ── RemoveOp ────────────────────────────────────────────────────
627
628    #[test]
629    fn remove_with_capture_roundtrip() {
630        let mut v = vec![10, 20, 30];
631        let op = remove_capturing(&v, 1);
632        op.forward(&mut v);
633        assert_eq!(v, vec![10, 30]);
634        op.backward(&mut v);
635        assert_eq!(v, vec![10, 20, 30]);
636    }
637
638    // ── Sequence ────────────────────────────────────────────────────
639
640    #[test]
641    fn sequence_forward_backward() {
642        let mut x = 0u64;
643        let seq = Sequence::new(vec![
644            Box::new(AddOp::new(10u64)),
645            Box::new(AddOp::new(20u64)),
646            Box::new(AddOp::new(30u64)),
647        ]);
648
649        seq.forward(&mut x);
650        assert_eq!(x, 60);
651
652        seq.backward(&mut x);
653        assert_eq!(x, 0);
654    }
655
656    #[test]
657    fn sequence_backward_reverses_order() {
658        let mut v = Vec::<u32>::new();
659        let seq = Sequence::new(vec![
660            Box::new(PushOp::new(1u32)),
661            Box::new(PushOp::new(2u32)),
662            Box::new(PushOp::new(3u32)),
663        ]);
664
665        seq.forward(&mut v);
666        assert_eq!(v, vec![1, 2, 3]);
667
668        seq.backward(&mut v);
669        assert!(v.is_empty());
670    }
671
672    #[test]
673    fn sequence_empty() {
674        let mut x = 42u64;
675        let seq = Sequence::<u64>::empty();
676        seq.forward(&mut x);
677        assert_eq!(x, 42);
678        seq.backward(&mut x);
679        assert_eq!(x, 42);
680    }
681
682    #[test]
683    fn sequence_push() {
684        let mut seq = Sequence::<u64>::empty();
685        seq.push(Box::new(AddOp::new(5u64)));
686        assert_eq!(seq.len(), 1);
687
688        let mut x = 0u64;
689        seq.forward(&mut x);
690        assert_eq!(x, 5);
691    }
692
693    #[test]
694    fn sequence_with_label() {
695        let seq = Sequence::<u64>::empty().with_label("batch insert");
696        assert_eq!(seq.description(), "batch insert");
697    }
698
699    // ── Journal ─────────────────────────────────────────────────────
700
701    #[test]
702    fn journal_apply_and_undo() {
703        let mut state = 0u64;
704        let mut journal = Journal::new();
705
706        journal.apply(Box::new(AddOp::new(10u64)), &mut state);
707        assert_eq!(state, 10);
708        assert_eq!(journal.undo_count(), 1);
709
710        journal.apply(Box::new(AddOp::new(20u64)), &mut state);
711        assert_eq!(state, 30);
712        assert_eq!(journal.undo_count(), 2);
713
714        assert!(journal.undo(&mut state));
715        assert_eq!(state, 10);
716        assert_eq!(journal.undo_count(), 1);
717        assert_eq!(journal.redo_count(), 1);
718
719        assert!(journal.undo(&mut state));
720        assert_eq!(state, 0);
721
722        assert!(!journal.undo(&mut state)); // nothing to undo
723    }
724
725    #[test]
726    fn journal_redo() {
727        let mut state = 0u64;
728        let mut journal = Journal::new();
729
730        journal.apply(Box::new(AddOp::new(10u64)), &mut state);
731        journal.apply(Box::new(AddOp::new(20u64)), &mut state);
732        assert_eq!(state, 30);
733
734        journal.undo(&mut state);
735        assert_eq!(state, 10);
736
737        assert!(journal.redo(&mut state));
738        assert_eq!(state, 30);
739
740        assert!(!journal.redo(&mut state)); // nothing to redo
741    }
742
743    #[test]
744    fn journal_new_op_clears_redo() {
745        let mut state = 0u64;
746        let mut journal = Journal::new();
747
748        journal.apply(Box::new(AddOp::new(10u64)), &mut state);
749        journal.undo(&mut state);
750        assert_eq!(journal.redo_count(), 1);
751
752        journal.apply(Box::new(AddOp::new(5u64)), &mut state);
753        assert_eq!(journal.redo_count(), 0); // redo stack cleared
754        assert_eq!(state, 5);
755    }
756
757    #[test]
758    fn journal_clear() {
759        let mut state = 0u64;
760        let mut journal = Journal::new();
761
762        journal.apply(Box::new(AddOp::new(10u64)), &mut state);
763        journal.undo(&mut state);
764        journal.clear();
765
766        assert_eq!(journal.undo_count(), 0);
767        assert_eq!(journal.redo_count(), 0);
768    }
769
770    #[test]
771    fn journal_complex_sequence() {
772        let mut state = vec![1u32, 2, 3];
773        let mut journal = Journal::new();
774
775        // Push 4
776        journal.apply(Box::new(PushOp::new(4u32)), &mut state);
777        assert_eq!(state, vec![1, 2, 3, 4]);
778
779        // Swap first and last
780        journal.apply(Box::new(SwapOp::new(0, 3)), &mut state);
781        assert_eq!(state, vec![4, 2, 3, 1]);
782
783        // Insert at position 2
784        journal.apply(Box::new(InsertOp::new(2, 99u32)), &mut state);
785        assert_eq!(state, vec![4, 2, 99, 3, 1]);
786
787        // Undo all
788        journal.undo(&mut state);
789        assert_eq!(state, vec![4, 2, 3, 1]);
790        journal.undo(&mut state);
791        assert_eq!(state, vec![1, 2, 3, 4]);
792        journal.undo(&mut state);
793        assert_eq!(state, vec![1, 2, 3]);
794
795        // Redo all
796        journal.redo(&mut state);
797        journal.redo(&mut state);
798        journal.redo(&mut state);
799        assert_eq!(state, vec![4, 2, 99, 3, 1]);
800    }
801
802    #[test]
803    fn description_returns_op_name() {
804        assert_eq!(AddOp::new(1u64).description(), "add");
805        assert_eq!(XorOp::new(1u64).description(), "xor");
806        assert_eq!(
807            Reversible::<Vec<u32>>::description(&SwapOp::new(0, 1)),
808            "swap"
809        );
810        assert_eq!(SetOp::new(0u32, 1u32).description(), "set");
811        assert_eq!(PushOp::new(1u32).description(), "push");
812        assert_eq!(InsertOp::new(0, 1u32).description(), "insert");
813    }
814
815    #[test]
816    fn debug_impls() {
817        let op = AddOp::new(5u64);
818        assert!(format!("{op:?}").contains("AddOp"));
819
820        let seq = Sequence::<u64>::empty();
821        assert!(format!("{seq:?}").contains("Sequence"));
822
823        let journal = Journal::<u64>::new();
824        assert!(format!("{journal:?}").contains("Journal"));
825    }
826}
ftui_runtime/reversible.rs

ftui_runtime/
reversible.rs
