fast_mesh_store/
history.rs

1use std::collections::VecDeque;
2
3use crate::compact::Remap;
4use crate::{ChangeSet, Mesh, Patch, PatchSide, Result, StoreError};
5
6/// Undo/redo stacks of [`Patch`]es for one mesh, limited by a memory budget.
7///
8/// Every commit on the mesh must be pushed here (or the history cleared): undo and
9/// redo only work when the mesh revision matches the top patch. A history belongs to
10/// the mesh of its first pushed patch; every method that takes a mesh rejects any
11/// other mesh with [`StoreError::PatchMismatch`].
12///
13/// The history also decides when removed slots may be reused. A slot freed by a
14/// patch stays reserved while that patch can still be undone, and a slot created by
15/// an undone patch stays reserved while it can be redone. Evicting or discarding the
16/// patch releases the slot. Patches kept outside a `History` release their slots
17/// through [`Mesh::release_patch_slots`], at most once and only once no history
18/// still holds the patch; slots never released that way are reclaimed by
19/// [`Mesh::compact`]. Patches made stale by a direct [`Mesh::compact`] release
20/// nothing: their slots no longer exist.
21///
22/// The budget counts undo and redo patches together, but eviction only drops undo
23/// patches (oldest first). While a large redo stack exists, [`History::bytes`] may
24/// therefore exceed [`History::budget`]; the redo stack is dropped by the next push.
25pub struct History {
26    undo: VecDeque<Patch>,
27    redo: Vec<Patch>,
28    budget: usize,
29    bytes: usize,
30    /// Uid of the mesh this history belongs to, set by the first push.
31    mesh_uid: Option<u64>,
32}
33
34impl History {
35    /// A history that keeps at most `budget_bytes` of patches (undo and redo combined).
36    pub fn new(budget_bytes: usize) -> Self {
37        Self {
38            undo: VecDeque::new(),
39            redo: Vec::new(),
40            budget: budget_bytes,
41            bytes: 0,
42            mesh_uid: None,
43        }
44    }
45
46    fn check_mesh(&self, mesh: &Mesh) -> Result<()> {
47        match self.mesh_uid {
48            Some(uid) if uid != mesh.uid => Err(StoreError::PatchMismatch),
49            _ => Ok(()),
50        }
51    }
52
53    /// Records a just-committed patch. Empty patches are ignored and keep the redo
54    /// stack. Otherwise the redo stack is discarded and the oldest patches are evicted
55    /// until the budget is met (possibly including this one, if it alone is too large).
56    pub fn push(&mut self, mesh: &mut Mesh, patch: Patch) -> Result<()> {
57        self.check_mesh(mesh)?;
58        if patch.mesh_uid != mesh.uid || patch.revision != mesh.revision {
59            return Err(StoreError::PatchMismatch);
60        }
61        self.mesh_uid = Some(mesh.uid);
62        if patch.is_empty() {
63            return Ok(());
64        }
65        for p in self.redo.drain(..) {
66            self.bytes -= p.byte_size();
67            p.release(mesh, PatchSide::Redoable);
68        }
69        self.bytes += patch.byte_size();
70        self.undo.push_back(patch);
71        self.evict(mesh);
72        Ok(())
73    }
74
75    /// Undoes the latest patch. Returns `None` when there is nothing to undo.
76    pub fn undo(&mut self, mesh: &mut Mesh) -> Result<Option<ChangeSet>> {
77        self.check_mesh(mesh)?;
78        let Some(patch) = self.undo.pop_back() else {
79            return Ok(None);
80        };
81        match patch.revert(mesh) {
82            Ok(changes) => {
83                self.redo.push(patch);
84                Ok(Some(changes))
85            }
86            Err(e) => {
87                self.undo.push_back(patch);
88                Err(e)
89            }
90        }
91    }
92
93    /// Redoes the latest undone patch. Returns `None` when there is nothing to redo.
94    pub fn redo(&mut self, mesh: &mut Mesh) -> Result<Option<ChangeSet>> {
95        self.check_mesh(mesh)?;
96        let Some(patch) = self.redo.pop() else {
97            return Ok(None);
98        };
99        match patch.apply(mesh) {
100            Ok(changes) => {
101                self.undo.push_back(patch);
102                Ok(Some(changes))
103            }
104            Err(e) => {
105                self.redo.push(patch);
106                Err(e)
107            }
108        }
109    }
110
111    /// Drops all patches and releases the slots they reserved.
112    pub fn clear(&mut self, mesh: &mut Mesh) -> Result<()> {
113        self.check_mesh(mesh)?;
114        for p in self.undo.drain(..) {
115            p.release(mesh, PatchSide::Undoable);
116        }
117        for p in self.redo.drain(..) {
118            p.release(mesh, PatchSide::Redoable);
119        }
120        self.bytes = 0;
121        Ok(())
122    }
123
124    /// Clears the history and compacts the mesh (see [`Mesh::compact`]).
125    pub fn compact(&mut self, mesh: &mut Mesh) -> Result<Remap> {
126        self.check_mesh(mesh)?;
127        let remap = mesh.compact()?;
128        // Old patches are stale now, so their reserved slots are simply dropped.
129        self.undo.clear();
130        self.redo.clear();
131        self.bytes = 0;
132        Ok(remap)
133    }
134
135    /// Changes the budget, evicting old undo patches if needed.
136    pub fn set_budget(&mut self, mesh: &mut Mesh, budget_bytes: usize) -> Result<()> {
137        self.check_mesh(mesh)?;
138        self.budget = budget_bytes;
139        self.evict(mesh);
140        Ok(())
141    }
142
143    fn evict(&mut self, mesh: &mut Mesh) {
144        while self.bytes > self.budget {
145            let Some(p) = self.undo.pop_front() else {
146                break;
147            };
148            self.bytes -= p.byte_size();
149            p.release(mesh, PatchSide::Undoable);
150        }
151    }
152
153    pub fn can_undo(&self) -> bool {
154        !self.undo.is_empty()
155    }
156
157    pub fn can_redo(&self) -> bool {
158        !self.redo.is_empty()
159    }
160
161    pub fn undo_len(&self) -> usize {
162        self.undo.len()
163    }
164
165    pub fn redo_len(&self) -> usize {
166        self.redo.len()
167    }
168
169    /// Memory held by all patches (undo and redo), in bytes. Can exceed the budget
170    /// while a redo stack exists; see the type docs.
171    pub fn bytes(&self) -> usize {
172        self.bytes
173    }
174
175    pub fn budget(&self) -> usize {
176        self.budget
177    }
178}
179
180#[cfg(test)]
181mod tests {
182    use super::*;
183
184    fn quad() -> Mesh {
185        Mesh::from_buffers(
186            &[0., 0., 0., 1., 0., 0., 1., 1., 0., 0., 1., 0.],
187            &[0, 1, 2, 0, 2, 3],
188        )
189        .unwrap()
190    }
191
192    fn move_vertex(m: &mut Mesh, h: &mut History, v: u32, x: f32) {
193        let mut tx = m.begin_edit();
194        tx.set_positions(&[v], &[[x, 0., 0.]]).unwrap();
195        let p = tx.commit().unwrap();
196        h.push(m, p).unwrap();
197    }
198
199    #[test]
200    fn undo_and_redo_walk_the_stack() {
201        let mut m = quad();
202        let mut h = History::new(1 << 20);
203        move_vertex(&mut m, &mut h, 0, 5.0);
204        move_vertex(&mut m, &mut h, 0, 6.0);
205        assert_eq!(h.undo(&mut m).unwrap().unwrap().vertices_moved, vec![0]);
206        assert_eq!(m.position(0).unwrap()[0], 5.0);
207        h.undo(&mut m).unwrap();
208        assert_eq!(m.position(0).unwrap()[0], 0.0);
209        assert!(h.undo(&mut m).unwrap().is_none());
210        h.redo(&mut m).unwrap();
211        h.redo(&mut m).unwrap();
212        assert_eq!(m.position(0).unwrap()[0], 6.0);
213        assert!(h.redo(&mut m).unwrap().is_none());
214    }
215
216    #[test]
217    fn a_new_commit_discards_redo() {
218        let mut m = quad();
219        let mut h = History::new(1 << 20);
220        move_vertex(&mut m, &mut h, 0, 5.0);
221        h.undo(&mut m).unwrap();
222        move_vertex(&mut m, &mut h, 1, 7.0);
223        assert!(!h.can_redo());
224        assert_eq!(h.undo_len(), 1);
225    }
226
227    #[test]
228    fn empty_commits_keep_redo() {
229        let mut m = quad();
230        let mut h = History::new(1 << 20);
231        move_vertex(&mut m, &mut h, 0, 5.0);
232        h.undo(&mut m).unwrap();
233        let empty = m.begin_edit().commit().unwrap();
234        h.push(&mut m, empty).unwrap();
235        assert!(h.can_redo());
236    }
237
238    #[test]
239    fn budget_evicts_the_oldest_patches() {
240        let mut m = quad();
241        let mut h = History::new(1 << 20);
242        move_vertex(&mut m, &mut h, 0, 1.0);
243        let one = h.bytes();
244        h.set_budget(&mut m, one * 2).unwrap();
245        move_vertex(&mut m, &mut h, 0, 2.0);
246        move_vertex(&mut m, &mut h, 0, 3.0);
247        assert_eq!(h.undo_len(), 2);
248        assert!(h.bytes() <= h.budget());
249        h.undo(&mut m).unwrap();
250        h.undo(&mut m).unwrap();
251        assert_eq!(
252            m.position(0).unwrap()[0],
253            1.0,
254            "the first edit can no longer be undone"
255        );
256    }
257
258    #[test]
259    fn removed_slots_are_reserved_until_their_patch_is_evicted() {
260        let mut m = quad();
261        let mut h = History::new(1 << 20);
262        let mut tx = m.begin_edit();
263        tx.remove_triangles(&[1]).unwrap();
264        tx.remove_vertices(&[3]).unwrap();
265        let p = tx.commit().unwrap();
266        h.push(&mut m, p).unwrap();
267        assert!(m.free_vertex_slots().is_empty(), "reserved while undoable");
268
269        let mut tx = m.begin_edit();
270        assert_eq!(
271            tx.add_vertices(&[[0.; 3]]).unwrap(),
272            vec![4],
273            "slot 3 is not reused"
274        );
275        tx.rollback();
276
277        h.clear(&mut m).unwrap();
278        assert_eq!(m.free_vertex_slots(), &[3]);
279        assert_eq!(m.free_triangle_slots(), &[1]);
280    }
281
282    #[test]
283    fn created_slots_of_discarded_redo_are_released() {
284        let mut m = quad();
285        let mut h = History::new(1 << 20);
286        let mut tx = m.begin_edit();
287        tx.add_vertices(&[[0.; 3]]).unwrap();
288        let p = tx.commit().unwrap();
289        h.push(&mut m, p).unwrap();
290        h.undo(&mut m).unwrap();
291        assert!(m.free_vertex_slots().is_empty(), "reserved for redo");
292        move_vertex(&mut m, &mut h, 0, 1.0);
293        assert_eq!(m.free_vertex_slots(), &[4]);
294    }
295
296    #[test]
297    fn history_compact_empties_history_and_applies_remap() {
298        let mut m = quad();
299        let mut h = History::new(1 << 20);
300        let mut tx = m.begin_edit();
301        tx.remove_triangles(&[0]).unwrap();
302        tx.remove_vertices(&[1]).unwrap();
303        let p = tx.commit().unwrap();
304        h.push(&mut m, p).unwrap();
305
306        let remap = h.compact(&mut m).unwrap();
307        assert!(!h.can_undo());
308        assert_eq!(h.bytes(), 0);
309        assert_eq!(remap.vertex(1), None);
310        assert_eq!(remap.vertex(2), Some(1));
311        assert_eq!(remap.vertex(3), Some(2));
312        assert_eq!(remap.triangle(0), None);
313        assert_eq!(remap.triangle(1), Some(0));
314        assert_eq!(m.vertex_count(), 3);
315        assert_eq!(m.position(1), Some([1., 1., 0.]));
316        assert_eq!(m.triangle(0), Some([0, 1, 2]));
317    }
318
319    /// Four vertices, no triangles.
320    fn points() -> Mesh {
321        Mesh::from_buffers(&[0.; 12], &[]).unwrap()
322    }
323
324    fn remove_vertex(m: &mut Mesh, h: &mut History, v: u32) {
325        let mut tx = m.begin_edit();
326        tx.remove_vertices(&[v]).unwrap();
327        let p = tx.commit().unwrap();
328        h.push(m, p).unwrap();
329    }
330
331    #[test]
332    fn direct_compact_then_clear_does_not_corrupt() {
333        let mut m = quad();
334        let mut h = History::new(1 << 20);
335        let mut tx = m.begin_edit();
336        tx.remove_triangles(&[0]).unwrap();
337        tx.remove_vertices(&[1]).unwrap();
338        let p = tx.commit().unwrap();
339        h.push(&mut m, p).unwrap();
340        m.compact().unwrap();
341        // The patch is stale: its reserved slot 1 no longer exists (vertex 1 is now
342        // the old vertex 2, alive).
343        h.clear(&mut m).unwrap();
344        assert!(m.free_vertex_slots().is_empty());
345        assert!(m.free_triangle_slots().is_empty());
346        let mut tx = m.begin_edit();
347        assert_eq!(tx.add_vertices(&[[0.; 3]]).unwrap(), vec![3]);
348    }
349
350    #[test]
351    fn direct_compact_then_push_or_set_budget_does_not_corrupt() {
352        let mut m = points();
353        let mut h = History::new(1 << 20);
354        remove_vertex(&mut m, &mut h, 0);
355        h.clear(&mut m).unwrap();
356        assert_eq!(m.free_vertex_slots(), &[0]);
357        // Re-create slot 0, then undo: the redo patch reserves slot 0.
358        let mut tx = m.begin_edit();
359        assert_eq!(tx.add_vertices(&[[1.; 3]]).unwrap(), vec![0]);
360        let p = tx.commit().unwrap();
361        h.push(&mut m, p).unwrap();
362        remove_vertex(&mut m, &mut h, 3);
363        h.undo(&mut m).unwrap();
364        h.undo(&mut m).unwrap();
365        // Now: vertices 1, 2, 3 alive; redo holds "remove 3" and "add 0".
366        m.compact().unwrap();
367        assert_eq!(m.vertex_count(), 3);
368        move_vertex(&mut m, &mut h, 0, 5.0); // discards the stale redo patches
369        assert!(m.free_vertex_slots().is_empty(), "slot 0 is alive again");
370        h.set_budget(&mut m, 0).unwrap();
371        assert!(m.free_vertex_slots().is_empty());
372        let mut tx = m.begin_edit();
373        assert_eq!(tx.add_vertices(&[[0.; 3]]).unwrap(), vec![3]);
374    }
375
376    #[test]
377    fn undo_of_a_patch_made_stale_by_direct_compact_fails_cleanly() {
378        let mut m = points();
379        let mut h = History::new(1 << 20);
380        remove_vertex(&mut m, &mut h, 1);
381        m.compact().unwrap();
382        let revision = m.revision();
383        assert_eq!(h.undo(&mut m).err(), Some(StoreError::StalePatch));
384        assert_eq!(m.revision(), revision);
385        assert_eq!(m.vertex_count(), 3);
386        h.clear(&mut m).unwrap();
387        assert!(m.free_vertex_slots().is_empty());
388    }
389
390    #[test]
391    fn history_used_with_a_second_mesh_is_rejected() {
392        let mut a = points();
393        let mut b = points();
394        let mut h = History::new(1 << 20);
395        remove_vertex(&mut a, &mut h, 1);
396        assert_eq!(h.clear(&mut b).err(), Some(StoreError::PatchMismatch));
397        assert_eq!(
398            h.set_budget(&mut b, 0).err(),
399            Some(StoreError::PatchMismatch)
400        );
401        assert_eq!(h.undo(&mut b).err(), Some(StoreError::PatchMismatch));
402        assert_eq!(h.redo(&mut b).err(), Some(StoreError::PatchMismatch));
403        assert_eq!(h.compact(&mut b).err(), Some(StoreError::PatchMismatch));
404        let mut tx = b.begin_edit();
405        tx.remove_vertices(&[2]).unwrap();
406        let pb = tx.commit().unwrap();
407        assert_eq!(h.push(&mut b, pb).err(), Some(StoreError::PatchMismatch));
408        assert!(b.free_vertex_slots().is_empty());
409        assert_eq!(b.vertex_slots(), 4, "b was not compacted");
410        assert_eq!(h.undo_len(), 1, "history is unchanged");
411        h.clear(&mut a).unwrap();
412        assert_eq!(a.free_vertex_slots(), &[1]);
413    }
414
415    #[test]
416    fn rejects_patches_that_are_not_the_latest_commit() {
417        let mut m = quad();
418        let mut h = History::new(1 << 20);
419        let mut tx = m.begin_edit();
420        tx.set_positions(&[0], &[[1.; 3]]).unwrap();
421        let first = tx.commit().unwrap();
422        let mut tx = m.begin_edit();
423        tx.set_positions(&[0], &[[2.; 3]]).unwrap();
424        let _second = tx.commit().unwrap();
425        assert_eq!(h.push(&mut m, first).err(), Some(StoreError::PatchMismatch));
426    }
427}
fast_mesh_store/history.rs

fast_mesh_store/
history.rs
