1pub trait UndoLogs<T> {
17 fn in_snapshot(&self) -> bool {
19 self.num_open_snapshots() > 0
20 }
21
22 fn num_open_snapshots(&self) -> usize;
24
25 fn push(&mut self, undo: T);
29
30 fn clear(&mut self);
32
33 fn extend<I>(&mut self, undos: I)
35 where
36 Self: Sized,
37 I: IntoIterator<Item = T>,
38 {
39 undos.into_iter().for_each(|undo| self.push(undo));
40 }
41}
42
43impl<'a, T, U> UndoLogs<T> for &'a mut U
44where
45 U: UndoLogs<T>,
46{
47 fn in_snapshot(&self) -> bool {
48 U::in_snapshot(self)
49 }
50 fn num_open_snapshots(&self) -> usize {
51 U::num_open_snapshots(self)
52 }
53 fn push(&mut self, undo: T) {
54 U::push(self, undo)
55 }
56 fn clear(&mut self) {
57 U::clear(self);
58 }
59 fn extend<I>(&mut self, undos: I)
60 where
61 I: IntoIterator<Item = T>,
62 {
63 U::extend(self, undos)
64 }
65}
66
67pub trait Snapshots<T>: UndoLogs<T> {
72 type Snapshot;
73
74 fn has_changes(&self, snapshot: &Self::Snapshot) -> bool {
76 !self.actions_since_snapshot(snapshot).is_empty()
77 }
78
79 fn actions_since_snapshot(&self, snapshot: &Self::Snapshot) -> &[T];
81
82 fn start_snapshot(&mut self) -> Self::Snapshot;
87
88 fn rollback_to<R>(&mut self, storage: impl FnOnce() -> R, snapshot: Self::Snapshot)
90 where
91 R: Rollback<T>;
92
93 fn commit(&mut self, snapshot: Self::Snapshot);
95}
96
97impl<T, U> Snapshots<T> for &'_ mut U
98where
99 U: Snapshots<T>,
100{
101 type Snapshot = U::Snapshot;
102 fn has_changes(&self, snapshot: &Self::Snapshot) -> bool {
103 U::has_changes(self, snapshot)
104 }
105 fn actions_since_snapshot(&self, snapshot: &Self::Snapshot) -> &[T] {
106 U::actions_since_snapshot(self, snapshot)
107 }
108
109 fn start_snapshot(&mut self) -> Self::Snapshot {
110 U::start_snapshot(self)
111 }
112 fn rollback_to<R>(&mut self, storage: impl FnOnce() -> R, snapshot: Self::Snapshot)
113 where
114 R: Rollback<T>,
115 {
116 U::rollback_to(self, storage, snapshot)
117 }
118
119 fn commit(&mut self, snapshot: Self::Snapshot) {
120 U::commit(self, snapshot)
121 }
122}
123
124pub struct NoUndo;
125impl<T> UndoLogs<T> for NoUndo {
126 fn num_open_snapshots(&self) -> usize {
127 0
128 }
129 fn push(&mut self, _undo: T) {}
130 fn clear(&mut self) {}
131}
132
133#[derive(Clone, Debug)]
135pub struct VecLog<T> {
136 log: Vec<T>,
137 num_open_snapshots: usize,
138}
139
140impl<T> Default for VecLog<T> {
141 fn default() -> Self {
142 VecLog {
143 log: Vec::new(),
144 num_open_snapshots: 0,
145 }
146 }
147}
148
149impl<T> UndoLogs<T> for VecLog<T> {
150 fn num_open_snapshots(&self) -> usize {
151 self.num_open_snapshots
152 }
153 fn push(&mut self, undo: T) {
154 self.log.push(undo);
155 }
156 fn clear(&mut self) {
157 self.log.clear();
158 self.num_open_snapshots = 0;
159 }
160}
161
162impl<T> Snapshots<T> for VecLog<T> {
163 type Snapshot = Snapshot;
164
165 fn has_changes(&self, snapshot: &Self::Snapshot) -> bool {
166 self.log.len() > snapshot.undo_len
167 }
168 fn actions_since_snapshot(&self, snapshot: &Snapshot) -> &[T] {
169 &self.log[snapshot.undo_len..]
170 }
171
172 fn start_snapshot(&mut self) -> Snapshot {
173 self.num_open_snapshots += 1;
174 Snapshot {
175 undo_len: self.log.len(),
176 }
177 }
178
179 fn rollback_to<R>(&mut self, values: impl FnOnce() -> R, snapshot: Snapshot)
180 where
181 R: Rollback<T>,
182 {
183 debug!("rollback_to({})", snapshot.undo_len);
184
185 self.assert_open_snapshot(&snapshot);
186
187 if self.log.len() > snapshot.undo_len {
188 let mut values = values();
189 while self.log.len() > snapshot.undo_len {
190 values.reverse(self.log.pop().unwrap());
191 }
192 }
193
194 self.num_open_snapshots -= 1;
195 }
196
197 fn commit(&mut self, snapshot: Snapshot) {
198 debug!("commit({})", snapshot.undo_len);
199
200 self.assert_open_snapshot(&snapshot);
201
202 if self.num_open_snapshots == 1 {
203 assert!(snapshot.undo_len == 0);
207 self.log.clear();
208 }
209
210 self.num_open_snapshots -= 1;
211 }
212}
213
214impl<T> VecLog<T> {
215 fn assert_open_snapshot(&self, snapshot: &Snapshot) {
216 assert!(self.log.len() >= snapshot.undo_len);
218 assert!(self.num_open_snapshots > 0);
219 }
220}
221
222impl<T> std::ops::Index<usize> for VecLog<T> {
223 type Output = T;
224 fn index(&self, key: usize) -> &T {
225 &self.log[key]
226 }
227}
228
229pub trait Rollback<U> {
231 fn reverse(&mut self, undo: U);
232}
233
234impl<T, U> Rollback<U> for &'_ mut T
235where
236 T: Rollback<U>,
237{
238 fn reverse(&mut self, undo: U) {
239 T::reverse(self, undo)
240 }
241}
242
243pub struct Snapshot {
245 undo_len: usize,
247}