ifc_model/mutation/inverse.rs
1//! The recorded inverse of a run of model writes, applied exactly.
2//!
3//! # Why not an inverse transaction
4//!
5//! A `Create` appends to the end of file order and of its type bucket, so an
6//! inverse built from the staged edits could never put a removed entity back
7//! where it was, nor restore the id allocator. An [`Inverse`] therefore holds
8//! the primitive steps the model itself recorded (`step.rs`), including those
9//! positions. Applying one restores file order, type-index order, attribute
10//! counts, the header and the next free id, so a codec writes the same bytes.
11//!
12//! # Revisions
13//!
14//! The revision is never restored: an undo is a new change and bumps it, or a
15//! transaction opened before the undo could commit against different state.
16//! An inverse therefore applies only to the revision it was recorded up to,
17//! and applying it returns the inverse of the application (redo).
18//!
19//! Revisions are process-unique (see `Model::revision`), so an inverse is
20//! also refused by a model that is not the one it was recorded on, or a clone
21//! of it that has since diverged. A clone taken at the recorded revision
22//! accepts it, which is correct: it holds the same state.
23//!
24//! To look at a change and drop it without a new revision, use
25//! [`Model::preview`].
26
27use std::panic::{catch_unwind, resume_unwind, AssertUnwindSafe};
28
29use ahash::AHashMap;
30
31use crate::model::Model;
32use crate::mutation::step::Step;
33use crate::value::EntityId;
34
35/// The recorded undo of a run of writes. See the module docs.
36#[derive(Debug, Clone, PartialEq)]
37pub struct Inverse {
38 /// Undoing steps, already in the order they apply.
39 steps: Vec<Step>,
40 /// `max_id` as it was before the writes.
41 max_id: u64,
42 /// The revision when recording began.
43 before: u64,
44 /// The revision the inverse applies to.
45 after: u64,
46}
47
48/// The net effect of applying an [`Inverse`].
49#[derive(Debug, Clone, Default, PartialEq, Eq)]
50#[non_exhaustive]
51pub struct Restored {
52 /// Absent before the application, present after.
53 pub created: Vec<EntityId>,
54 /// Present before the application, absent after.
55 pub removed: Vec<EntityId>,
56 /// Present both times and touched.
57 pub modified: Vec<EntityId>,
58 /// Whether the header was replaced.
59 pub header: bool,
60}
61
62/// Why an [`Inverse`] was not applied.
63#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
64#[non_exhaustive]
65pub enum InverseError {
66 /// The model changed since the inverse was recorded.
67 #[error("model moved from revision {expected} to {found} since the change was recorded")]
68 StaleRevision {
69 /// The revision the inverse applies to.
70 expected: u64,
71 /// The model's revision.
72 found: u64,
73 },
74}
75
76impl Inverse {
77 pub(crate) fn new(steps: Vec<Step>, max_id: u64, before: u64, after: u64) -> Self {
78 Self {
79 steps,
80 max_id,
81 before,
82 after,
83 }
84 }
85
86 /// Run `change` on `model` and return its result with the inverse of
87 /// every write it made.
88 ///
89 /// If `change` panics the recording is closed before the panic resumes.
90 pub fn record<T>(model: &mut Model, change: impl FnOnce(&mut Model) -> T) -> (T, Inverse) {
91 let depth = model.recording_depth();
92 model.begin_recording();
93 let outcome = catch_unwind(AssertUnwindSafe(|| change(model)));
94 // A change that began a recording and did not end it must not make
95 // this call return the wrong inverse.
96 model.unwind_recording(depth + 1);
97 assert!(
98 model.recording_depth() == depth + 1,
99 "the change ended a recording it did not begin"
100 );
101 let inverse = model
102 .end_recording()
103 .expect("the recording opened above is still open");
104 match outcome {
105 Ok(value) => (value, inverse),
106 Err(panic) => resume_unwind(panic),
107 }
108 }
109
110 /// Whether the writes changed nothing.
111 pub fn is_empty(&self) -> bool {
112 self.steps.is_empty()
113 }
114
115 /// Number of primitive steps.
116 pub fn len(&self) -> usize {
117 self.steps.len()
118 }
119
120 /// The model revision this inverse applies to.
121 pub fn revision(&self) -> u64 {
122 self.after
123 }
124
125 pub(crate) fn before(&self) -> u64 {
126 self.before
127 }
128
129 /// Re-targets the inverse at `revision`; the caller has checked the model
130 /// is at that revision and the entry still describes it.
131 pub(crate) fn rebase(&mut self, revision: u64) {
132 self.after = revision;
133 }
134
135 /// The net effect of applying this inverse to `model`, computed without
136 /// applying it.
137 #[must_use]
138 pub fn summary(&self, model: &Model) -> Restored {
139 // id -> (present before, present now), in order of first touch.
140 let mut seen: AHashMap<EntityId, (bool, bool)> = AHashMap::new();
141 let mut order: Vec<EntityId> = Vec::new();
142 let mut restored = Restored::default();
143 for step in &self.steps {
144 let (id, now) = match step {
145 Step::Header(_) => {
146 restored.header = true;
147 continue;
148 }
149 Step::IdFloor { .. } => continue,
150 Step::Remove { id } => (*id, Some(false)),
151 Step::Insert { id, .. } => (*id, Some(true)),
152 Step::Replace { id, .. } | Step::Slot { id, .. } | Step::Retype { id, .. } => {
153 (*id, None)
154 }
155 };
156 let entry = seen.entry(id).or_insert_with(|| {
157 order.push(id);
158 let present = model.contains(id);
159 (present, present)
160 });
161 if let Some(now) = now {
162 entry.1 = now;
163 }
164 }
165 for id in order {
166 match seen[&id] {
167 (false, true) => restored.created.push(id),
168 (true, false) => restored.removed.push(id),
169 (true, true) => restored.modified.push(id),
170 (false, false) => {}
171 }
172 }
173 restored
174 }
175
176 /// Restore the model to the state before the recorded writes.
177 ///
178 /// Returns what changed and the inverse of this application, which redoes
179 /// the writes. A model that moved on since recording is refused and left
180 /// untouched.
181 pub fn apply(self, model: &mut Model) -> Result<(Restored, Inverse), InverseError> {
182 if model.revision() != self.after {
183 return Err(InverseError::StaleRevision {
184 expected: self.after,
185 found: model.revision(),
186 });
187 }
188 let restored = self.summary(model);
189 let before = model.revision();
190 let prior_max_id = model.max_id();
191 let recording = model.is_recording();
192 let mut opposite = Vec::with_capacity(self.steps.len());
193 for step in self.steps {
194 let undone = step.apply(model);
195 if recording {
196 model.record(undone.clone());
197 }
198 opposite.push(undone);
199 }
200 model.set_max_id(self.max_id);
201 if !opposite.is_empty() {
202 model.bump_revision();
203 }
204 opposite.reverse();
205 let redo = Inverse::new(opposite, prior_max_id, before, model.revision());
206 Ok((restored, redo))
207 }
208}