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}