Skip to main content

common/database/
rope_store.rs

1//! Ropey-backed storage backend.
2//!
3//! Holds character data in a single document-wide `ropey::Rope`,
4//! with structural entities (Frames, Tables, Lists, Resources) in
5//! `im::HashMap` tables and per-block character formatting in
6//! `format_runs`. See the migration plan §1.5 for the relationship
7//! inlining and §1.6 for the rope layout (block boundary `\n` +
8//! U+FFFC table anchor).
9
10use crate::database::block_offset_index::BlockOffsetIndex;
11use crate::entities::*;
12use crate::format_runs::{FootnoteRefAnchor, FormatRun, ImageAnchor};
13use crate::snapshot::{StoreSnapshot, StoreSnapshotTrait};
14use crate::types::EntityId;
15use im::HashMap;
16use parking_lot::{Mutex, RwLock};
17use ropey::Rope;
18use std::collections::HashMap as StdHashMap;
19use std::collections::HashSet as StdHashSet;
20use std::thread::ThreadId;
21
22// ─────────────────────────────────────────────────────────────────────────────
23// The Store
24// ─────────────────────────────────────────────────────────────────────────────
25
26#[derive(Debug, Default)]
27pub struct RopeStore {
28    // ── Character content (shared across all blocks, including cells) ──
29    pub rope: RwLock<Rope>,
30
31    // ── Structural entity tables ──────────────────────────────────────
32    pub roots: RwLock<HashMap<EntityId, Root>>,
33    pub documents: RwLock<HashMap<EntityId, Document>>,
34    pub frames: RwLock<HashMap<EntityId, Frame>>,
35    pub blocks: RwLock<HashMap<EntityId, Block>>,
36    pub lists: RwLock<HashMap<EntityId, List>>,
37    pub resources: RwLock<HashMap<EntityId, Resource>>,
38    pub tables: RwLock<HashMap<EntityId, Table>>,
39    pub table_cells: RwLock<HashMap<EntityId, TableCell>>,
40
41    // ── Per-block character formatting + image anchors ────────────────
42    pub format_runs: RwLock<HashMap<EntityId, Vec<FormatRun>>>,
43    pub block_images: RwLock<HashMap<EntityId, Vec<ImageAnchor>>>,
44    /// Footnote references anchored in each block, byte-ordered.
45    ///
46    /// Beside `block_images` rather than merged with it: the two are written by
47    /// different editing paths and read together only through
48    /// `format_runs::block_anchors`, which is the one place their interleaving is
49    /// decided.
50    pub block_footnote_refs: RwLock<HashMap<EntityId, Vec<FootnoteRefAnchor>>>,
51    /// Host-supplied markers by footnote label — what a reference *prints*.
52    ///
53    /// Ambient and presentation-only, like a syntax highlighter: never serialised,
54    /// never part of the document, and consulted when a reference is rendered.
55    ///
56    /// It exists because the number is a fact about the **host's** manuscript, not
57    /// about this document. Skribisto compiles one chapter into a document of its
58    /// own, and that document's reading order would number the chapter's notes from
59    /// one — disagreeing with the badge the writer sees in the editor, for the same
60    /// note, at the same moment. Empty means "number them yourself", which is the
61    /// right answer for a document that *is* the whole text.
62    pub footnote_markers: RwLock<StdHashMap<String, String>>,
63
64    // ── Document-wide block ordering (sorted by rope position) ────────
65    pub block_offsets: RwLock<BlockOffsetIndex>,
66
67    // ── ID counters ───────────────────────────────────────────────────
68    // Never restored by undo (only by transaction rollback).
69    pub counters: RwLock<StdHashMap<String, EntityId>>,
70
71    // ── Savepoints (in-memory, transaction-scoped) ────────────────────
72    savepoints: RwLock<StdHashMap<u64, RopeStoreSnapshot>>,
73    next_savepoint_id: RwLock<u64>,
74
75    // ── Transient edits (see `begin_transient_write`) ─────────────────
76    transient: Mutex<TransientEdits>,
77}
78
79/// Edits that no undo history holds, made over the content as it is recorded, and the
80/// writes that are open while they begin.
81#[derive(Debug, Default)]
82struct TransientEdits {
83    /// The store as it stood before the first outstanding transient edit, which a revert
84    /// puts back. `None` while there are none.
85    base: Option<RopeStoreSnapshot>,
86    /// The thread inside a [`TransientWrite`]: while `base` is held, the only one a write
87    /// transaction may be opened for.
88    writer: Option<ThreadId>,
89    /// The auto-savepoints of the writes open now: every write transaction, and every
90    /// other write begun through [`RopeStore::check_write_allowed`]. A write discards its
91    /// auto-savepoint as it ends, committed, rolled back or dropped, which is how the store
92    /// sees it end.
93    open_writes: StdHashSet<u64>,
94    /// The threads that passed [`RopeStore::check_write_allowed`] and have still to take
95    /// the auto-savepoint of the write they begin, which is the next one they take.
96    beginning: StdHashSet<ThreadId>,
97}
98
99impl TransientEdits {
100    /// Whether a write is open, or being begun on a thread other than `besides`.
101    fn writes_open(&self, besides: Option<ThreadId>) -> bool {
102        !self.open_writes.is_empty() || self.beginning.iter().any(|thread| Some(*thread) != besides)
103    }
104}
105
106/// A transient write, or a revert of transient edits, was refused: what they need of the
107/// store does not hold. See [`RopeStore::begin_transient_write`] and
108/// [`RopeStore::revert_transient_edits`].
109#[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)]
110#[non_exhaustive]
111pub enum TransientWriteRefused {
112    /// Another transient write is in progress, on this thread or another.
113    #[error("a transient write is in progress: transient writes do not nest")]
114    TransientWriteInProgress,
115    /// A write is open (a write transaction, or another write begun through
116    /// [`RopeStore::check_write_allowed`]): the first transient write's snapshot would be
117    /// taken over it, and a revert would take what it then records away.
118    #[error("a write is open on the store: a transient write begins once it ends")]
119    WriteInProgress,
120}
121
122/// A write transaction was asked for while transient edits are outstanding, from outside
123/// the transient write that makes them.
124///
125/// The recorded history names positions and blocks of the content as it is recorded.
126/// A write landing over transient edits would be recorded against content that a revert
127/// then takes away, and the revert, which puts the recorded content back as it was, would
128/// take the write away with it. So the write is refused before it changes anything: revert
129/// the transient edits first. `text_document` does so itself before every edit, undo and
130/// redo; this is what stops a write begun some other way. Every write of this workspace
131/// begins through [`RopeStore::check_write_allowed`]: a write transaction, and the streaming
132/// appends, which write the rope directly. What the store cannot stop is code writing its
133/// public fields without beginning a write.
134#[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)]
135#[error(
136    "transient edits are outstanding: revert them before writing the document's recorded content"
137)]
138pub struct TransientEditsOutstanding;
139
140impl RopeStore {
141    pub fn new() -> Self {
142        Self::default()
143    }
144
145    /// O(1) snapshot of the entire store (rope is Arc-shared, all
146    /// `im::HashMap`s are HAMT-shared; `BlockOffsetIndex` is a small
147    /// `Vec` cloned outright).
148    pub fn snapshot(&self) -> RopeStoreSnapshot {
149        RopeStoreSnapshot {
150            rope: self.rope.read().clone(),
151            roots: self.roots.read().clone(),
152            documents: self.documents.read().clone(),
153            frames: self.frames.read().clone(),
154            blocks: self.blocks.read().clone(),
155            lists: self.lists.read().clone(),
156            resources: self.resources.read().clone(),
157            tables: self.tables.read().clone(),
158            table_cells: self.table_cells.read().clone(),
159            format_runs: self.format_runs.read().clone(),
160            block_images: self.block_images.read().clone(),
161            block_footnote_refs: self.block_footnote_refs.read().clone(),
162            footnote_markers: self.footnote_markers.read().clone(),
163            block_offsets: self.block_offsets.read().clone(),
164            counters: self.counters.read().clone(),
165        }
166    }
167
168    /// Restore from a snapshot. Overwrites counters too — used for
169    /// transaction rollback (`Drop` of an uncommitted write txn).
170    pub fn restore(&self, snap: &RopeStoreSnapshot) {
171        *self.rope.write() = snap.rope.clone();
172        *self.roots.write() = snap.roots.clone();
173        *self.documents.write() = snap.documents.clone();
174        *self.frames.write() = snap.frames.clone();
175        *self.blocks.write() = snap.blocks.clone();
176        *self.lists.write() = snap.lists.clone();
177        *self.resources.write() = snap.resources.clone();
178        *self.tables.write() = snap.tables.clone();
179        *self.table_cells.write() = snap.table_cells.clone();
180        *self.format_runs.write() = snap.format_runs.clone();
181        *self.block_images.write() = snap.block_images.clone();
182        *self.block_footnote_refs.write() = snap.block_footnote_refs.clone();
183        *self.footnote_markers.write() = snap.footnote_markers.clone();
184        *self.block_offsets.write() = snap.block_offsets.clone();
185        *self.counters.write() = snap.counters.clone();
186    }
187
188    /// Restore everything *except* counters — used for undo, where IDs
189    /// must remain monotonically increasing across undo/redo cycles.
190    pub fn restore_without_counters(&self, snap: &RopeStoreSnapshot) {
191        *self.rope.write() = snap.rope.clone();
192        *self.roots.write() = snap.roots.clone();
193        *self.documents.write() = snap.documents.clone();
194        *self.frames.write() = snap.frames.clone();
195        *self.blocks.write() = snap.blocks.clone();
196        *self.lists.write() = snap.lists.clone();
197        *self.resources.write() = snap.resources.clone();
198        *self.tables.write() = snap.tables.clone();
199        *self.table_cells.write() = snap.table_cells.clone();
200        *self.format_runs.write() = snap.format_runs.clone();
201        *self.block_images.write() = snap.block_images.clone();
202        *self.block_footnote_refs.write() = snap.block_footnote_refs.clone();
203        *self.footnote_markers.write() = snap.footnote_markers.clone();
204        *self.block_offsets.write() = snap.block_offsets.clone();
205        // counters intentionally not restored
206    }
207
208    pub fn create_savepoint(&self) -> u64 {
209        let snap = self.snapshot();
210        let mut id_counter = self.next_savepoint_id.write();
211        let id = *id_counter;
212        *id_counter += 1;
213        drop(id_counter);
214        self.savepoints.write().insert(id, snap);
215        // The first savepoint a thread takes after `check_write_allowed` is the
216        // auto-savepoint of the write it begins: the write is open until it is discarded.
217        let mut state = self.transient.lock();
218        if state.beginning.remove(&std::thread::current().id()) {
219            state.open_writes.insert(id);
220        }
221        id
222    }
223
224    pub fn restore_savepoint(&self, savepoint_id: u64) {
225        let snap = self
226            .savepoints
227            .read()
228            .get(&savepoint_id)
229            .expect("savepoint not found")
230            .clone();
231        self.restore(&snap);
232    }
233
234    pub fn discard_savepoint(&self, savepoint_id: u64) {
235        self.savepoints.write().remove(&savepoint_id);
236        self.transient.lock().open_writes.remove(&savepoint_id);
237    }
238
239    /// How many savepoints the store holds: one for each write transaction still open, and
240    /// each one created explicitly and not discarded yet.
241    pub fn savepoint_count(&self) -> usize {
242        self.savepoints.read().len()
243    }
244
245    /// Get-and-increment counter for an entity type.
246    pub(crate) fn next_id(&self, entity_name: &str) -> EntityId {
247        let mut counters = self.counters.write();
248        let counter = counters.entry(entity_name.to_string()).or_insert(1);
249        let id = *counter;
250        *counter += 1;
251        id
252    }
253
254    /// Type-erased store snapshot (for the generic undo path).
255    pub fn store_snapshot(&self) -> StoreSnapshot {
256        StoreSnapshot::new(self.snapshot())
257    }
258
259    /// Restore from a type-erased store snapshot (undo semantic —
260    /// counters preserved).
261    pub fn restore_store_snapshot(&self, snap: &StoreSnapshot) {
262        let s = snap
263            .downcast_ref::<RopeStoreSnapshot>()
264            .expect("StoreSnapshot must contain RopeStoreSnapshot");
265        self.restore_without_counters(s);
266    }
267
268    // ── Transient edits ───────────────────────────────────────────────
269
270    /// Begin a write that no undo history will hold, over the content as it is recorded.
271    ///
272    /// The first one takes a snapshot of the store, the **base**: the recorded content,
273    /// which [`revert_transient_edits`](Self::revert_transient_edits) puts back. Every write
274    /// made inside a [`TransientWrite`], up to that revert, is a transient edit over the
275    /// same base, so the revert takes them all away at once and gives back the very content
276    /// they were made over: the same text, formats and block identities, which is what the
277    /// recorded history refers to.
278    ///
279    /// While the base is held, a write is begun only by the thread inside a
280    /// `TransientWrite` (see [`check_write_allowed`](Self::check_write_allowed)).
281    ///
282    /// The write is kept only by [`TransientWrite::keep`]. Dropped without it, the store
283    /// goes back to where it was when the write began, and the base is let go when this
284    /// write is the one that took it, so a transient edit that failed partway or changed
285    /// nothing leaves nothing outstanding.
286    ///
287    /// Refused, with nothing changed:
288    ///
289    /// * while another transient write is in progress, on this thread or another
290    ///   ([`TransientWriteRefused::TransientWriteInProgress`]): they do not nest, since the
291    ///   writer's permission is one thread's and each write goes back to its own starting
292    ///   point;
293    /// * while any other write is open ([`TransientWriteRefused::WriteInProgress`]): its
294    ///   snapshot would hold half of that write, and a revert would take what the write
295    ///   then records away.
296    ///
297    /// The snapshot is taken under the store's transient-edit lock, which every write takes
298    /// as it begins, so no write begins or ends between the check and the snapshot.
299    pub fn begin_transient_write(&self) -> Result<TransientWrite<'_>, TransientWriteRefused> {
300        let mut state = self.transient.lock();
301        if state.writer.is_some() {
302            return Err(TransientWriteRefused::TransientWriteInProgress);
303        }
304        let thread = std::thread::current().id();
305        if state.writes_open(Some(thread)) {
306            return Err(TransientWriteRefused::WriteInProgress);
307        }
308        // This thread is not in the middle of beginning a write, since it is here: a check
309        // it made without a write after it is dropped, and does not hold the store up.
310        state.beginning.remove(&thread);
311        let before = self.snapshot();
312        let opens = state.base.is_none();
313        // The first write's starting point is the base itself, and the base is what it
314        // goes back to: one snapshot serves both.
315        let before = if opens {
316            state.base = Some(before);
317            None
318        } else {
319            Some(before)
320        };
321        state.writer = Some(std::thread::current().id());
322        Ok(TransientWrite {
323            store: self,
324            before,
325            opens,
326            kept: false,
327        })
328    }
329
330    /// Whether transient edits are outstanding.
331    pub fn has_transient_edits(&self) -> bool {
332        self.transient.lock().base.is_some()
333    }
334
335    /// The content as it is recorded, while transient edits are outstanding: what
336    /// [`revert_transient_edits`](Self::revert_transient_edits) would put back, with the
337    /// footnote markers as they are now, which a revert keeps. `None` while there are none.
338    ///
339    /// O(1), as every snapshot is. For a reader that has to show the recorded content while
340    /// the store holds transient edits over it: restored into a store of its own, it reads
341    /// as this store will once they are reverted.
342    pub fn recorded_snapshot(&self) -> Option<RopeStoreSnapshot> {
343        let mut recorded = self.transient.lock().base.clone()?;
344        recorded.footnote_markers = self.footnote_markers.read().clone();
345        Some(recorded)
346    }
347
348    /// Put back the content the outstanding transient edits were made over, and end them.
349    /// Returns whether there were any.
350    ///
351    /// Restores everything the base holds except the id counters, as an undo does (an id
352    /// handed out stays spent), and the footnote markers, which the host sets and which are
353    /// not part of the content.
354    ///
355    /// Refused, with nothing changed, while a transient write is in progress
356    /// ([`TransientWriteRefused::TransientWriteInProgress`]), whose own end would put its
357    /// starting point back over the revert, and while any other write is open
358    /// ([`TransientWriteRefused::WriteInProgress`]), whose rollback would put back the
359    /// transient content its savepoint holds.
360    ///
361    /// The content is put back under the store's transient-edit lock, before the base is let
362    /// go: no write and no transient write begins until the store holds the recorded content
363    /// again.
364    pub fn revert_transient_edits(&self) -> Result<bool, TransientWriteRefused> {
365        let mut state = self.transient.lock();
366        if state.writer.is_some() {
367            return Err(TransientWriteRefused::TransientWriteInProgress);
368        }
369        if state.writes_open(None) {
370            return Err(TransientWriteRefused::WriteInProgress);
371        }
372        let Some(base) = state.base.as_ref() else {
373            return Ok(false);
374        };
375        self.restore_content(base);
376        state.base = None;
377        Ok(true)
378    }
379
380    /// Begin a write, or refuse it while transient edits are outstanding unless the thread
381    /// beginning it is inside a [`TransientWrite`] (see [`TransientEditsOutstanding`]).
382    ///
383    /// Every write calls it first and then takes its auto-savepoint
384    /// ([`create_savepoint`](Self::create_savepoint)), which it discards as it ends: a write
385    /// transaction does so as it begins and ends, and so does any other write to the store.
386    /// The store counts the write open from that savepoint to its discard, and refuses a
387    /// transient write and a revert meanwhile. A write ends at that discard: a transaction
388    /// written through after its commit is not counted.
389    ///
390    /// It begins a write, so the next savepoint the thread takes is taken as the write's,
391    /// and until it takes one, transient writes on other threads are refused. To ask
392    /// whether a write would be allowed without beginning one, call
393    /// [`is_write_allowed`](Self::is_write_allowed).
394    pub fn check_write_allowed(&self) -> anyhow::Result<()> {
395        let mut state = self.transient.lock();
396        let thread = std::thread::current().id();
397        if state.base.is_some() && state.writer != Some(thread) {
398            return Err(TransientEditsOutstanding.into());
399        }
400        state.beginning.insert(thread);
401        Ok(())
402    }
403
404    /// Whether a write begun now would be allowed (see
405    /// [`check_write_allowed`](Self::check_write_allowed)), without beginning one.
406    pub fn is_write_allowed(&self) -> bool {
407        let state = self.transient.lock();
408        state.base.is_none() || state.writer == Some(std::thread::current().id())
409    }
410
411    /// `snap`'s content, without its id counters or footnote markers.
412    fn restore_content(&self, snap: &RopeStoreSnapshot) {
413        let markers = self.footnote_markers.read().clone();
414        self.restore_without_counters(snap);
415        *self.footnote_markers.write() = markers;
416    }
417}
418
419/// A write in progress that no undo history will hold. See
420/// [`RopeStore::begin_transient_write`].
421#[derive(Debug)]
422pub struct TransientWrite<'a> {
423    store: &'a RopeStore,
424    /// The store as the write found it, when that is not the base (see `opens`): put back
425    /// unless the write is kept.
426    before: Option<RopeStoreSnapshot>,
427    /// Whether this write took the base, which is then also where it started.
428    opens: bool,
429    kept: bool,
430}
431
432impl TransientWrite<'_> {
433    /// Whether this is the first of the outstanding transient edits.
434    pub fn opens(&self) -> bool {
435        self.opens
436    }
437
438    /// Keep what the write changed, as a transient edit over the base.
439    pub fn keep(mut self) {
440        self.kept = true;
441    }
442}
443
444impl Drop for TransientWrite<'_> {
445    fn drop(&mut self) {
446        let mut state = self.store.transient.lock();
447        // The one transient write in progress (see `begin_transient_write`).
448        state.writer = None;
449        if self.kept {
450            return;
451        }
452        // Not kept: back to where the write started, which for the first one is the base,
453        // let go with it. Put back under the lock, as a revert does, so that nothing begins
454        // over the content being put back. The writes the transient write opened end inside
455        // it: one still open would put its savepoint back over this afterwards.
456        debug_assert!(
457            !state.writes_open(None),
458            "a transient write ended with a write it opened still open"
459        );
460        if self.opens {
461            if let Some(base) = state.base.as_ref() {
462                self.store.restore_content(base);
463            }
464            state.base = None;
465        } else if let Some(before) = self.before.take() {
466            self.store.restore_content(&before);
467        }
468    }
469}
470
471// ─────────────────────────────────────────────────────────────────────────────
472// Snapshot
473// ─────────────────────────────────────────────────────────────────────────────
474
475/// O(1)-clone snapshot. `Rope::clone()` shares the Arc-d B+ tree root;
476/// every `im::HashMap::clone()` is HAMT-structural.
477#[derive(Debug, Clone, Default)]
478pub struct RopeStoreSnapshot {
479    pub(crate) rope: Rope,
480    pub(crate) roots: HashMap<EntityId, Root>,
481    pub(crate) documents: HashMap<EntityId, Document>,
482    pub(crate) frames: HashMap<EntityId, Frame>,
483    pub(crate) blocks: HashMap<EntityId, Block>,
484    pub(crate) lists: HashMap<EntityId, List>,
485    pub(crate) resources: HashMap<EntityId, Resource>,
486    pub(crate) tables: HashMap<EntityId, Table>,
487    pub(crate) table_cells: HashMap<EntityId, TableCell>,
488    pub(crate) format_runs: HashMap<EntityId, Vec<FormatRun>>,
489    pub(crate) block_images: HashMap<EntityId, Vec<ImageAnchor>>,
490    pub(crate) block_footnote_refs: HashMap<EntityId, Vec<FootnoteRefAnchor>>,
491    pub(crate) footnote_markers: StdHashMap<String, String>,
492    pub(crate) block_offsets: BlockOffsetIndex,
493    pub(crate) counters: StdHashMap<String, EntityId>,
494}
495
496impl StoreSnapshotTrait for RopeStoreSnapshot {
497    fn clone_box(&self) -> Box<dyn StoreSnapshotTrait> {
498        Box::new(self.clone())
499    }
500
501    fn as_any(&self) -> &dyn std::any::Any {
502        self
503    }
504}