fast_mesh_store/
patch.rs

1use crate::channel::Channel;
2use crate::column::ColumnPatch;
3use crate::{Mesh, Result, StoreError, TriangleId, VertexId};
4
5/// What an edit, undo or redo changed. All lists are sorted and free of duplicates.
6#[derive(Debug, Clone, Default, PartialEq, Eq)]
7pub struct ChangeSet {
8    pub vertices_added: Vec<VertexId>,
9    pub vertices_removed: Vec<VertexId>,
10    /// Existing vertices whose position changed. In a set produced by
11    /// [`ChangeSet::merge`], such a vertex may also have changed values in any
12    /// channel, so treat it as dirty for all channels.
13    pub vertices_moved: Vec<VertexId>,
14    pub triangles_added: Vec<TriangleId>,
15    pub triangles_removed: Vec<TriangleId>,
16    /// Existing triangles whose vertex ids changed.
17    pub triangles_changed: Vec<TriangleId>,
18    /// Source channels written for existing vertices: (channel name, vertex ids).
19    pub channels: Vec<(String, Vec<VertexId>)>,
20    /// Channels that went away or came back whole (a
21    /// [`crate::Transaction::drop_channel`], its undo or redo), sorted by name:
22    /// read [`Mesh::channel`] for where they stand now. Their values are not
23    /// listed in [`ChangeSet::channels`].
24    pub channels_toggled: Vec<String>,
25}
26
27impl ChangeSet {
28    /// True when triangles were added, removed or rewritten.
29    pub fn topology_changed(&self) -> bool {
30        !(self.triangles_added.is_empty()
31            && self.triangles_removed.is_empty()
32            && self.triangles_changed.is_empty())
33    }
34
35    pub fn is_empty(&self) -> bool {
36        !self.topology_changed()
37            && self.vertices_added.is_empty()
38            && self.vertices_removed.is_empty()
39            && self.vertices_moved.is_empty()
40            && self.channels.iter().all(|(_, v)| v.is_empty())
41            && self.channels_toggled.is_empty()
42    }
43
44    /// Folds `later`, the change set of an edit (or undo or redo) made after `self`,
45    /// into `self`, so that `self` describes the net effect of both. Per slot:
46    ///
47    /// - added, then removed: reported as neither;
48    /// - removed, then added again (slot reuse): reported as moved (vertex) or changed
49    ///   (triangle), because the slot was alive before and is alive after;
50    /// - moved and changed are unions, minus slots that end up added or removed;
51    /// - channel lists are unioned per channel name, minus vertices that end up added
52    ///   or removed. A reused (removed, then added) vertex is added to every channel
53    ///   list named in either input, because its slot got brand-new contents. Names
54    ///   are kept even when their list ends up empty.
55    ///
56    /// A slot that was written and then restored to its original value stays in the
57    /// moved, changed and channel lists; the lists are supersets of the real
58    /// differences. All lists stay sorted, duplicate-free and disjoint.
59    ///
60    /// In a merged set, a vertex in `vertices_moved` may have changed values in any
61    /// channel (a reused slot may differ in channels no input named), so consumers
62    /// must treat it as dirty for all channels.
63    ///
64    /// Both sets must satisfy the `ChangeSet` invariants: every list sorted and
65    /// duplicate-free, added, removed and moved/changed disjoint, and channel lists
66    /// free of added and removed vertices. Sets returned by this crate do.
67    pub fn merge(&mut self, later: &ChangeSet) {
68        for cs in [&*self, later] {
69            let strictly_sorted = |l: &Vec<u32>| l.windows(2).all(|w| w[0] < w[1]);
70            debug_assert!(
71                strictly_sorted(&cs.vertices_added)
72                    && strictly_sorted(&cs.vertices_removed)
73                    && strictly_sorted(&cs.vertices_moved)
74                    && strictly_sorted(&cs.triangles_added)
75                    && strictly_sorted(&cs.triangles_removed)
76                    && strictly_sorted(&cs.triangles_changed)
77                    && cs.channels.iter().all(|(_, v)| strictly_sorted(v)),
78                "change set lists must be sorted and duplicate-free"
79            );
80        }
81        let (vertices_added, vertices_removed, reborn_v) = merge_slots(
82            &self.vertices_added,
83            &self.vertices_removed,
84            &later.vertices_added,
85            &later.vertices_removed,
86        );
87        let (triangles_added, triangles_removed, reborn_t) = merge_slots(
88            &self.triangles_added,
89            &self.triangles_removed,
90            &later.triangles_added,
91            &later.triangles_removed,
92        );
93        let ended = union(&vertices_added, &vertices_removed);
94        let moved = union(
95            &union(&self.vertices_moved, &later.vertices_moved),
96            &reborn_v,
97        );
98        self.vertices_moved = difference(&moved, &ended);
99        let ended_t = union(&triangles_added, &triangles_removed);
100        let changed = union(
101            &union(&self.triangles_changed, &later.triangles_changed),
102            &reborn_t,
103        );
104        self.triangles_changed = difference(&changed, &ended_t);
105
106        for (name, ids) in &later.channels {
107            match self.channels.iter_mut().find(|(n, _)| n == name) {
108                Some((_, mine)) => *mine = union(mine, ids),
109                None => self.channels.push((name.clone(), ids.clone())),
110            }
111        }
112        for (_, ids) in &mut self.channels {
113            *ids = difference(ids, &ended);
114        }
115        for (_, ids) in &mut self.channels {
116            *ids = union(ids, &reborn_v);
117        }
118
119        for name in &later.channels_toggled {
120            if let Err(at) = self.channels_toggled.binary_search(name) {
121                self.channels_toggled.insert(at, name.clone());
122            }
123        }
124
125        self.vertices_added = vertices_added;
126        self.vertices_removed = vertices_removed;
127        self.triangles_added = triangles_added;
128        self.triangles_removed = triangles_removed;
129    }
130
131    fn inverted(mut self) -> Self {
132        std::mem::swap(&mut self.vertices_added, &mut self.vertices_removed);
133        std::mem::swap(&mut self.triangles_added, &mut self.triangles_removed);
134        self
135    }
136}
137
138/// Sorted union of two sorted, duplicate-free lists.
139fn union(a: &[u32], b: &[u32]) -> Vec<u32> {
140    let mut out = Vec::with_capacity(a.len() + b.len());
141    let (mut i, mut j) = (0, 0);
142    while i < a.len() && j < b.len() {
143        match a[i].cmp(&b[j]) {
144            std::cmp::Ordering::Less => {
145                out.push(a[i]);
146                i += 1;
147            }
148            std::cmp::Ordering::Greater => {
149                out.push(b[j]);
150                j += 1;
151            }
152            std::cmp::Ordering::Equal => {
153                out.push(a[i]);
154                i += 1;
155                j += 1;
156            }
157        }
158    }
159    out.extend_from_slice(&a[i..]);
160    out.extend_from_slice(&b[j..]);
161    out
162}
163
164/// Elements of `a` that are not in `b` (both sorted, duplicate-free).
165fn difference(a: &[u32], b: &[u32]) -> Vec<u32> {
166    let mut j = 0;
167    a.iter()
168        .copied()
169        .filter(|&x| {
170            while j < b.len() && b[j] < x {
171                j += 1;
172            }
173            !(j < b.len() && b[j] == x)
174        })
175        .collect()
176}
177
178/// Net added and removed slots of two consecutive change sets, plus the slots that
179/// were removed and then added again.
180fn merge_slots(
181    add1: &[u32],
182    rem1: &[u32],
183    add2: &[u32],
184    rem2: &[u32],
185) -> (Vec<u32>, Vec<u32>, Vec<u32>) {
186    let added = union(&difference(add1, rem2), &difference(add2, rem1));
187    let removed = union(&difference(rem1, add2), &difference(rem2, add1));
188    let reborn = difference(rem1, &difference(rem1, add2));
189    (added, removed, reborn)
190}
191
192/// Which slots of a [`Patch`] to release, see [`Patch::release`].
193#[derive(Debug, Clone, Copy, PartialEq, Eq)]
194pub enum PatchSide {
195    /// The patch sits on an undo stack: release the slots it removed.
196    Undoable,
197    /// The patch was undone and sits on a redo stack: release the slots it created.
198    Redoable,
199}
200
201/// Whether an externally held [`Patch`]'s edit is currently applied to the mesh,
202/// see [`Mesh::release_patch_slots`].
203#[derive(Debug, Clone, Copy, PartialEq, Eq)]
204pub enum PatchState {
205    /// The patch's edit is applied (as on an undo stack): release the slots it removed.
206    Applied,
207    /// The patch was undone (as on a redo stack): release the slots it created.
208    Undone,
209}
210
211/// The recorded effect of one committed transaction. Re-apply it with
212/// [`Patch::apply`] (redo) or undo it with [`Patch::revert`].
213///
214/// A patch only applies to the mesh that produced it, at the matching revision:
215/// `revert` needs the mesh exactly as the commit left it, `apply` needs it exactly as
216/// it was before the commit.
217#[derive(Debug, Clone)]
218pub struct Patch {
219    pub(crate) mesh_uid: u64,
220    pub(crate) epoch: u32,
221    pub(crate) base_revision: u64,
222    pub(crate) revision: u64,
223    pub(crate) positions: ColumnPatch<[f32; 3]>,
224    pub(crate) triangles: ColumnPatch<[u32; 3]>,
225    pub(crate) vertex_live: ColumnPatch<u64>,
226    pub(crate) triangle_live: ColumnPatch<u64>,
227    pub(crate) vertex_refs: ColumnPatch<u32>,
228    /// Per source channel, keyed by channel id (not name).
229    pub(crate) channel_data: Vec<(u64, ColumnPatch<f32>)>,
230    /// Ids of the channels this edit dropped: hidden when applied, back when
231    /// reverted.
232    pub(crate) dropped_channels: Vec<u64>,
233    /// Bytes of the dropped channels' values, kept on the mesh for this patch.
234    pub(crate) dropped_bytes: usize,
235    /// The channel id the next added channel would have got when this patch was
236    /// recorded: a channel at or past it is newer than the patch.
237    pub(crate) channels_before: u64,
238    pub(crate) changes: ChangeSet,
239}
240
241impl Patch {
242    /// The changes this patch makes when applied.
243    pub fn changes(&self) -> &ChangeSet {
244        &self.changes
245    }
246
247    /// True when the transaction changed nothing.
248    pub fn is_empty(&self) -> bool {
249        self.base_revision == self.revision
250    }
251
252    /// Mesh revision before the commit.
253    pub fn base_revision(&self) -> u64 {
254        self.base_revision
255    }
256
257    /// Mesh revision after the commit.
258    pub fn revision(&self) -> u64 {
259        self.revision
260    }
261
262    /// Approximate heap memory held by this patch.
263    pub fn byte_size(&self) -> usize {
264        let c = &self.changes;
265        let ids = c.vertices_added.len()
266            + c.vertices_removed.len()
267            + c.vertices_moved.len()
268            + c.triangles_added.len()
269            + c.triangles_removed.len()
270            + c.triangles_changed.len()
271            + c.channels.iter().map(|(_, v)| v.len()).sum::<usize>();
272        self.positions.byte_size()
273            + self.triangles.byte_size()
274            + self.vertex_live.byte_size()
275            + self.triangle_live.byte_size()
276            + self.vertex_refs.byte_size()
277            + self
278                .channel_data
279                .iter()
280                .map(|(_, p)| 8 + p.byte_size())
281                .sum::<usize>()
282            + ids * 4
283            + self.dropped_bytes
284    }
285
286    /// Re-applies the patch (redo). The mesh must be at [`Patch::base_revision`].
287    /// If memory runs out, the mesh is left unchanged.
288    pub fn apply(&self, mesh: &mut Mesh) -> Result<ChangeSet> {
289        self.check(mesh, self.base_revision)?;
290        // Phase A (the only fallible step): reserve capacity on every column. This
291        // never changes a length, so a failure leaves the mesh exactly as it was.
292        let vertex_slots = mesh.positions.len().max(self.positions.required_len());
293        mesh.positions
294            .try_reserve_to(self.positions.required_len())?;
295        mesh.triangles
296            .try_reserve_to(self.triangles.required_len())?;
297        mesh.vertex_live
298            .try_reserve_to(self.vertex_live.required_len())?;
299        mesh.triangle_live
300            .try_reserve_to(self.triangle_live.required_len())?;
301        mesh.vertex_refs
302            .try_reserve_to(self.vertex_refs.required_len())?;
303        for c in &mut mesh.channels {
304            c.data.try_reserve_to(self.channel_len(c, vertex_slots))?;
305        }
306
307        // Phase B: grow within the reserved capacity. Only adds dead slots.
308        mesh.positions
309            .resize_reserved(self.positions.required_len(), [0.0; 3]);
310        mesh.triangles
311            .resize_reserved(self.triangles.required_len(), [0; 3]);
312        mesh.vertex_live
313            .resize_reserved(self.vertex_live.required_len(), 0);
314        mesh.triangle_live
315            .resize_reserved(self.triangle_live.required_len(), 0);
316        mesh.vertex_refs
317            .resize_reserved(self.vertex_refs.required_len(), 0);
318        for c in &mut mesh.channels {
319            let len = self.channel_len(c, vertex_slots);
320            c.data.resize_reserved(len, c.desc.default);
321        }
322
323        // Phase C: write. From here on nothing can fail (the incidence index is
324        // dropped instead if it cannot follow).
325        self.forget_newer_bound_channels(mesh);
326        let c = &self.changes;
327        let ids = [
328            &c.triangles_added[..],
329            &c.triangles_removed[..],
330            &c.triangles_changed[..],
331        ];
332        mesh.with_incidence(|inc, m| inc.remove_alive(m, &ids));
333        self.positions.apply(&mut mesh.positions);
334        self.triangles.apply(&mut mesh.triangles);
335        self.vertex_live.apply(&mut mesh.vertex_live);
336        self.triangle_live.apply(&mut mesh.triangle_live);
337        self.vertex_refs.apply(&mut mesh.vertex_refs);
338        for (id, p) in &self.channel_data {
339            if let Some(i) = mesh.channel_index_by_id(*id) {
340                p.apply(&mut mesh.channels[i].data);
341            }
342        }
343        for &id in &self.dropped_channels {
344            if let Some(i) = mesh.channel_index_by_id(id) {
345                mesh.channels[i].hidden = true;
346            }
347        }
348        mesh.live_vertices = mesh.live_vertices + c.vertices_added.len() - c.vertices_removed.len();
349        mesh.live_triangles =
350            mesh.live_triangles + c.triangles_added.len() - c.triangles_removed.len();
351        mesh.revision = self.revision;
352        if c.topology_changed() {
353            mesh.adjacency = None;
354            mesh.with_incidence(|inc, m| inc.insert_alive(m, &ids));
355        }
356        Ok(self.changes.clone())
357    }
358
359    /// Removes the [`topology_bound`](crate::ChannelDesc::topology_bound)
360    /// channels added after this patch was recorded: its undo or redo takes the
361    /// mesh to a state they never described.
362    fn forget_newer_bound_channels(&self, mesh: &mut Mesh) {
363        mesh.channels
364            .retain(|c| !(c.desc.topology_bound && c.id >= self.channels_before));
365    }
366
367    /// Undoes the patch. The mesh must be at [`Patch::revision`].
368    pub fn revert(&self, mesh: &mut Mesh) -> Result<ChangeSet> {
369        self.check(mesh, self.revision)?;
370        self.forget_newer_bound_channels(mesh);
371        let c = &self.changes;
372        let ids = [
373            &c.triangles_added[..],
374            &c.triangles_removed[..],
375            &c.triangles_changed[..],
376        ];
377        mesh.with_incidence(|inc, m| inc.remove_alive(m, &ids));
378        self.positions.revert(&mut mesh.positions);
379        self.triangles.revert(&mut mesh.triangles);
380        self.vertex_live.revert(&mut mesh.vertex_live);
381        self.triangle_live.revert(&mut mesh.triangle_live);
382        self.vertex_refs.revert(&mut mesh.vertex_refs);
383        for (id, p) in &self.channel_data {
384            if let Some(i) = mesh.channel_index_by_id(*id) {
385                p.revert(&mut mesh.channels[i].data);
386            }
387        }
388        for &id in &self.dropped_channels {
389            if let Some(i) = mesh.channel_index_by_id(id) {
390                // A channel added since under the same name gives way.
391                let name = mesh.channels[i].desc.name.clone();
392                if let Some(newer) = mesh.channel_index(&name) {
393                    mesh.channels.remove(newer);
394                }
395                if let Some(i) = mesh.channel_index_by_id(id) {
396                    mesh.channels[i].hidden = false;
397                }
398            }
399        }
400        mesh.live_vertices = mesh.live_vertices + c.vertices_removed.len() - c.vertices_added.len();
401        mesh.live_triangles =
402            mesh.live_triangles + c.triangles_removed.len() - c.triangles_added.len();
403        mesh.revision = self.base_revision;
404        if c.topology_changed() {
405            mesh.adjacency = None;
406            mesh.with_incidence(|inc, m| inc.insert_alive(m, &ids));
407        }
408        Ok(self.changes.clone().inverted())
409    }
410
411    /// Returns the slots this patch reserves to the mesh's free lists, for a patch
412    /// that is dropped without being undone or redone again: the removed slots for
413    /// [`PatchSide::Undoable`], the created slots for [`PatchSide::Redoable`].
414    /// Does nothing when the patch is stale (another mesh, or the mesh was compacted),
415    /// because its slots no longer exist.
416    ///
417    /// Call it at most once per patch, and only when the patch is discarded from a
418    /// history. Calling it twice, or while a history still holds the patch, corrupts
419    /// slot reuse.
420    pub fn release(&self, mesh: &mut Mesh, side: PatchSide) {
421        if self.mesh_uid != mesh.uid || self.epoch != mesh.epoch {
422            return;
423        }
424        let c = &self.changes;
425        match side {
426            PatchSide::Undoable => {
427                mesh.release_vertices(&c.vertices_removed);
428                mesh.release_triangles(&c.triangles_removed);
429                // The edit stays for good: so does the drop.
430                mesh.channels
431                    .retain(|ch| !(ch.hidden && self.dropped_channels.contains(&ch.id)));
432            }
433            PatchSide::Redoable => {
434                mesh.release_vertices(&c.vertices_added);
435                mesh.release_triangles(&c.triangles_added);
436            }
437        }
438    }
439
440    /// Length channel `c` needs after [`Patch::apply`]: every vertex slot, and
441    /// everything this patch writes to it.
442    fn channel_len(&self, c: &Channel, vertex_slots: usize) -> usize {
443        let own = self
444            .channel_data
445            .iter()
446            .find(|(id, _)| *id == c.id)
447            .map_or(0, |(_, p)| p.required_len());
448        own.max(vertex_slots * c.desc.width)
449    }
450
451    fn check(&self, mesh: &Mesh, expected_revision: u64) -> Result<()> {
452        if self.mesh_uid != mesh.uid {
453            return Err(StoreError::PatchMismatch);
454        }
455        if self.epoch != mesh.epoch {
456            return Err(StoreError::StalePatch);
457        }
458        if mesh.revision != expected_revision {
459            return Err(StoreError::PatchMismatch);
460        }
461        Ok(())
462    }
463}
464
465#[cfg(test)]
466mod tests {
467    use crate::column::fail_allocations_after;
468    use crate::{ChangeSet, ChannelDesc, Mesh, PatchSide, StoreError};
469
470    fn quad() -> Mesh {
471        Mesh::from_buffers(
472            &[0., 0., 0., 1., 0., 0., 1., 1., 0., 0., 1., 0.],
473            &[0, 1, 2, 0, 2, 3],
474        )
475        .unwrap()
476    }
477
478    #[test]
479    fn release_matches_history_eviction() {
480        let mut m = quad();
481        let mut tx = m.begin_edit();
482        tx.remove_triangles(&[1]).unwrap();
483        tx.remove_vertices(&[3]).unwrap();
484        let removal = tx.commit().unwrap();
485        assert!(m.free_vertex_slots().is_empty(), "reserved by the patch");
486        // The wrong side releases nothing.
487        removal.release(&mut m, PatchSide::Redoable);
488        assert!(m.free_vertex_slots().is_empty());
489        removal.release(&mut m, PatchSide::Undoable);
490        assert_eq!(m.free_vertex_slots(), &[3]);
491        assert_eq!(m.free_triangle_slots(), &[1]);
492
493        let mut tx = m.begin_edit();
494        tx.add_vertices(&[[0.; 3]]).unwrap();
495        let creation = tx.commit().unwrap();
496        creation.revert(&mut m).unwrap();
497        assert!(m.free_vertex_slots().is_empty(), "reserved for redo");
498        creation.release(&mut m, PatchSide::Redoable);
499        assert_eq!(m.free_vertex_slots(), &[3]);
500    }
501
502    #[test]
503    fn merge_applies_net_effect_rules() {
504        let mut a = ChangeSet {
505            vertices_added: vec![5],
506            vertices_removed: vec![2],
507            vertices_moved: vec![1, 3],
508            triangles_added: vec![4],
509            triangles_removed: vec![0],
510            triangles_changed: vec![1],
511            channels: vec![("c".into(), vec![1, 3])],
512            channels_toggled: vec![],
513        };
514        let b = ChangeSet {
515            vertices_added: vec![2],
516            vertices_removed: vec![3, 5],
517            vertices_moved: vec![1],
518            triangles_added: vec![0],
519            triangles_removed: vec![4],
520            triangles_changed: vec![],
521            channels: vec![("c".into(), vec![0]), ("d".into(), vec![1])],
522            channels_toggled: vec![],
523        };
524        a.merge(&b);
525        assert_eq!(a.vertices_added, Vec::<u32>::new());
526        assert_eq!(a.vertices_removed, vec![3]);
527        assert_eq!(a.vertices_moved, vec![1, 2]);
528        assert_eq!(a.triangles_added, Vec::<u32>::new());
529        assert_eq!(a.triangles_removed, Vec::<u32>::new());
530        assert_eq!(a.triangles_changed, vec![0, 1]);
531        assert_eq!(
532            a.channels,
533            vec![
534                ("c".to_string(), vec![0, 1, 2]),
535                ("d".to_string(), vec![1, 2])
536            ]
537        );
538    }
539
540    /// Lengths of every column that must stay aligned with the slot counts.
541    fn lengths(m: &Mesh) -> Vec<usize> {
542        let mut l = vec![
543            m.positions.len(),
544            m.vertex_refs.len(),
545            m.vertex_live.len(),
546            m.triangles.len(),
547            m.triangle_live.len(),
548        ];
549        l.extend(m.channels.iter().map(|c| c.data.len()));
550        l
551    }
552
553    #[test]
554    fn apply_that_runs_out_of_memory_leaves_every_column_unchanged() {
555        let mut m = quad();
556        m.add_channel(ChannelDesc::source("c", 2)).unwrap();
557        m.add_channel(ChannelDesc::derived("d", 1)).unwrap();
558        let mut tx = m.begin_edit();
559        // 4 + 70 vertices: the liveness bitset grows past one word.
560        let vs = tx.add_vertices(&[[2.; 3]; 70]).unwrap();
561        tx.add_triangles(&[[0, vs[0], vs[1]]]).unwrap();
562        tx.write_channel("c", &[0], &[5., 6.]).unwrap();
563        let patch = tx.commit().unwrap();
564        patch.revert(&mut m).unwrap();
565        // Recreate the exact pre-commit layout (revert keeps appended slots allocated).
566        m.positions.truncate(4);
567        m.vertex_refs.truncate(4);
568        m.vertex_live.truncate(1);
569        m.triangles.truncate(2);
570        m.triangle_live.truncate(1);
571        for c in &mut m.channels {
572            let w = c.desc.width;
573            c.data.truncate(4 * w);
574        }
575        let before = lengths(&m);
576        let revision = m.revision();
577        for k in 0.. {
578            fail_allocations_after(Some(k));
579            let result = patch.apply(&mut m);
580            fail_allocations_after(None);
581            match result {
582                Err(e) => {
583                    assert_eq!(e, StoreError::OutOfMemory);
584                    assert_eq!(lengths(&m), before, "failed after {k} allocations");
585                    assert_eq!(m.revision(), revision);
586                    assert_eq!((m.vertex_count(), m.triangle_count()), (4, 2));
587                }
588                Ok(_) => {
589                    assert!(k > 0, "apply needs to allocate");
590                    assert_eq!((m.vertex_count(), m.triangle_count()), (74, 3));
591                    assert_eq!(lengths(&m), vec![74, 74, 2, 3, 1, 148, 74]);
592                    assert_eq!(&m.channel("c").unwrap()[..2], &[5., 6.]);
593                    assert_eq!(m.triangle(2), Some([0, vs[0], vs[1]]));
594                    break;
595                }
596            }
597        }
598    }
599}
fast_mesh_store/patch.rs

fast_mesh_store/
patch.rs
