Skip to main content

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}