1use crate::{
2 Error, ExGuid, FileType, Object,
3 document::{Element, Kind, Revision},
4 write::{Commit, LiveRevision, PropertyObject, declared, differing},
5};
6#[cfg(test)]
7use crate::{RevisionIndex, Store, document::Document, write::chain_depth};
8use bumpalo::Bump;
9use std::{
10 collections::{BTreeMap, BTreeSet},
11 sync::Arc,
12};
13
14type Result<T> = std::result::Result<T, Error>;
15
16/// Objects a writer stores in one revision of a page space.
17pub(crate) type Changes = BTreeMap<ExGuid, PropertyObject>;
18
19/// Payloads a store holds, by identity.
20pub(crate) type Files<'a> = std::rc::Rc<dyn Fn([u8; 16]) -> Result<&'a [u8]> + 'a>;
21
22/// A page space's active revision with the views its writers read, kept as appending
23/// their revisions and parsing the result would leave it.
24#[derive(Clone)]
25pub(crate) struct ActivePage<'a> {
26 files: Files<'a>,
27 pub pages: Vec<ExGuid>,
28 pub live: LiveRevision<'a>,
29 /// Elements of the reachable objects.
30 pub view: Revision<'a>,
31 /// `view.parents(&pages)`.
32 pub parents: BTreeMap<ExGuid, Vec<ExGuid>>,
33 /// Elements of `view` carrying the page-title flag.
34 titles: BTreeSet<ExGuid>,
35 /// Payloads embedded by revisions `write` applied, in order.
36 pub payloads: Vec<([u8; 16], &'a [u8])>,
37}
38
39impl<'a> ActivePage<'a> {
40 /// The active page of `space`, for tests comparing writers.
41 #[cfg(test)]
42 pub(crate) fn parse(index: &'a RevisionIndex<'a>, space: ExGuid) -> Result<Self> {
43 index.validate_current()?;
44 let mut document = Document::parse(index)?;
45 let pages = document.pages_in(space)?;
46 let view = document
47 .spaces
48 .remove(&space)
49 .and_then(|mut space| {
50 let active = *space.contexts.get(&ExGuid::default())?;
51 space.revisions.remove(&active)
52 })
53 .ok_or(Error {
54 offset: 0,
55 message: "The active page is unavailable",
56 })?;
57 let rid = index.active(space)?;
58 let live = LiveRevision::new(index.resolve(space, rid)?, chain_depth(index, space, rid))?;
59 let store: &'a Store<'a> = index.store;
60 Self::viewed(
61 std::rc::Rc::new(|guid| store.file_data(guid)),
62 pages,
63 live,
64 view,
65 )
66 }
67
68 /// The page space `live` holds, whose stored payloads `files` reads.
69 pub(crate) fn open(
70 space: ExGuid,
71 live: LiveRevision<'a>,
72 file_type: FileType,
73 files: Files<'a>,
74 ) -> Result<Self> {
75 let (view, _) = Revision::parse(space, &live.revision, file_type, &mut |guid| files(guid))?;
76 let pages = manifest_pages(&view);
77 Self::viewed(files, pages, live, view)
78 }
79
80 fn viewed(
81 files: Files<'a>,
82 pages: Vec<ExGuid>,
83 live: LiveRevision<'a>,
84 view: Revision<'a>,
85 ) -> Result<Self> {
86 let parents = view.parents(&pages)?;
87 let titles = view
88 .nodes
89 .iter()
90 .filter(|(_, node)| is_title(node))
91 .map(|(id, _)| *id)
92 .collect();
93 Ok(Self {
94 files,
95 pages,
96 live,
97 view,
98 parents,
99 titles,
100 payloads: Vec::new(),
101 })
102 }
103
104 /// The element of an object, reading payloads `write` embedded as well as stored ones.
105 pub(crate) fn element<'o>(&self, object: &Object<'o>) -> Result<Element<'o>>
106 where
107 'a: 'o,
108 {
109 Element::parse_with(object, FileType::Section, &mut |guid| match self
110 .payloads
111 .iter()
112 .find(|(id, _)| *id == guid)
113 {
114 Some((_, payload)) => Ok(*payload),
115 None => (self.files)(guid),
116 })
117 }
118
119 /// `parents`, after checking that `object` and its ancestors are editable.
120 pub(crate) fn editable_parents(
121 &self,
122 object: ExGuid,
123 ) -> Result<&BTreeMap<ExGuid, Vec<ExGuid>>> {
124 crate::edit::check_editable(&self.view, &self.parents, &self.pages, object)?;
125 Ok(&self.parents)
126 }
127
128 /// `edit::page_title` of the view with `overlay` replacing or adding elements that
129 /// neither carry the title flag nor detach any element that does.
130 pub(crate) fn title(
131 &self,
132 overlay: &BTreeMap<ExGuid, Element<'_>>,
133 text_update: Option<(ExGuid, &str)>,
134 ) -> Result<Option<(ExGuid, bool, String)>> {
135 crate::edit::title_of(
136 |id| overlay.get(&id).or_else(|| self.view.nodes.get(&id)),
137 &self.parents,
138 self.titles.iter().copied(),
139 &self.pages,
140 text_update,
141 )
142 }
143
144 /// Stores a writer's objects and payloads as the next revision; false when it stores
145 /// nothing, as appending it would leave the image unchanged.
146 #[cfg(test)]
147 pub(crate) fn write(
148 &mut self,
149 arena: &'a Bump,
150 payloads: &[([u8; 16], &[u8])],
151 changes: Changes,
152 ) -> Result<bool> {
153 Ok(self.store(arena, payloads, changes)?.is_some())
154 }
155
156 /// `write`, returning the objects whose content, reachability or reference count may
157 /// have moved; none when it stores nothing.
158 pub(crate) fn store(
159 &mut self,
160 arena: &'a Bump,
161 payloads: &[([u8; 16], &[u8])],
162 changes: Changes,
163 ) -> Result<Option<BTreeSet<ExGuid>>> {
164 let changes = self.live.prepare(changes, true)?;
165 for (guid, payload) in payloads {
166 self.payloads.push((*guid, arena.alloc_slice_copy(payload)));
167 }
168 if changes.is_empty() {
169 return Ok((!payloads.is_empty()).then(BTreeSet::new));
170 }
171 let mut objects = Vec::new();
172 for (id, change) in changes {
173 let bytes = arena.alloc_slice_copy(&change.bytes);
174 objects.push((id, declared(change.jcid, bytes, change.global_ids)?));
175 }
176 let replaced: BTreeSet<ExGuid> = objects.iter().map(|(id, _)| *id).collect();
177 let Commit {
178 checkpoint,
179 changed,
180 touched,
181 } = self.live.commit(objects)?;
182 if checkpoint {
183 let all: Vec<ExGuid> = self.live.revision.objects.keys().copied().collect();
184 self.live.settle(all)?;
185 } else {
186 self.live.settle(changed)?;
187 }
188 self.refresh(&replaced, touched.clone())?;
189 Ok(Some(touched))
190 }
191
192 /// Takes the stored form of `ids` from `file`, the revision a seal appended, where the
193 /// revisions written here since the previous seal left them otherwise: a seal groups
194 /// tables and aliases read-only objects across all of them at once.
195 pub(crate) fn adopt(
196 &mut self,
197 file: &LiveRevision<'a>,
198 ids: impl IntoIterator<Item = ExGuid>,
199 ) -> Result<()> {
200 let mut replacements = Vec::new();
201 for id in ids {
202 let Some(stored) = file.revision.objects.get(&id) else {
203 continue;
204 };
205 match self.live.revision.objects.get_mut(&id) {
206 Some(object) if object.jcid == stored.jcid && object.data == stored.data => {
207 object.global_ids = Arc::clone(&stored.global_ids);
208 object.reference_count = stored.reference_count;
209 }
210 _ if file.is_reachable(id) => replacements.push((id, stored.clone())),
211 // Nothing reads an object the file leaves unreachable.
212 _ => {}
213 }
214 }
215 if !replacements.is_empty() {
216 let replaced = replacements.iter().map(|(id, _)| *id).collect();
217 let Commit { touched, .. } = self.live.commit(replacements)?;
218 for id in &touched {
219 if let (Some(object), Some(stored)) = (
220 self.live.revision.objects.get_mut(id),
221 file.revision.objects.get(id),
222 ) {
223 object.global_ids = Arc::clone(&stored.global_ids);
224 object.reference_count = stored.reference_count;
225 }
226 }
227 self.refresh(&replaced, touched)?;
228 }
229 self.live.depth = file.depth;
230 Ok(())
231 }
232
233 /// Brings the view, parents and titles up to date with the revision for the objects a
234 /// commit touched, which include those it replaced.
235 fn refresh(&mut self, replaced: &BTreeSet<ExGuid>, touched: BTreeSet<ExGuid>) -> Result<()> {
236 self.view.roots.clone_from(&self.live.revision.roots);
237 let mut attach = Vec::new();
238 let mut detach = Vec::new();
239 let mut gone = BTreeMap::new();
240 for id in touched {
241 let reachable = self.live.is_reachable(id);
242 let viewed = self.view.nodes.contains_key(&id);
243 if reachable == viewed && !(reachable && replaced.contains(&id)) {
244 continue;
245 }
246 let fresh = if reachable {
247 Some(self.element(&self.live.revision.objects[&id])?)
248 } else {
249 None
250 };
251 let old = self.view.nodes.remove(&id);
252 // An element leaving the view detaches with its last parent.
253 if let Some(node) = &fresh
254 && (self.parents.contains_key(&id) || self.pages.contains(&id))
255 {
256 let before: Vec<ExGuid> = old.iter().flat_map(edges).collect();
257 let after: Vec<ExGuid> = edges(node).collect();
258 let (removed, added) = differing(&before, &after);
259 detach.extend(removed.iter().map(|child| (id, *child)));
260 attach.extend(added.iter().map(|child| (id, *child)));
261 }
262 self.titles.remove(&id);
263 if let Some(node) = fresh {
264 if is_title(&node) {
265 self.titles.insert(id);
266 }
267 self.view.nodes.insert(id, node);
268 } else if let Some(node) = old {
269 gone.insert(id, node);
270 }
271 }
272 let node = |nodes: &BTreeMap<ExGuid, Element<'a>>, id: ExGuid| {
273 nodes
274 .get(&id)
275 .or_else(|| gone.get(&id))
276 .map(|node| edges(node).collect::<Vec<_>>())
277 .ok_or(Error {
278 offset: 0,
279 message: "Page content is unavailable",
280 })
281 };
282 // Attaching before detaching keeps a moved subtree from being walked twice.
283 while let Some((parent, child)) = attach.pop() {
284 let parents = self.parents.entry(child).or_default();
285 parents.push(parent);
286 if parents.len() == 1 && !self.pages.contains(&child) {
287 attach.extend(
288 node(&self.view.nodes, child)?
289 .into_iter()
290 .map(|grandchild| (child, grandchild)),
291 );
292 }
293 }
294 while let Some((parent, child)) = detach.pop() {
295 let parents = self.parents.get_mut(&child).unwrap();
296 let at = parents.iter().position(|id| *id == parent).unwrap();
297 parents.remove(at);
298 if parents.is_empty() {
299 self.parents.remove(&child);
300 if !self.pages.contains(&child) {
301 detach.extend(
302 node(&self.view.nodes, child)?
303 .into_iter()
304 .map(|grandchild| (child, grandchild)),
305 );
306 }
307 }
308 }
309 Ok(())
310 }
311}
312
313/// The pages a page space's manifest lists.
314pub(crate) fn manifest_pages(view: &Revision<'_>) -> Vec<ExGuid> {
315 match view.roots.get(&1).and_then(|id| view.nodes.get(id)) {
316 Some(manifest) if matches!(manifest.kind, Kind::Manifest { .. }) => manifest
317 .content
318 .iter()
319 .filter(|id| {
320 matches!(
321 view.nodes.get(id).map(|node| &node.kind),
322 Some(Kind::Page { .. })
323 )
324 })
325 .copied()
326 .collect(),
327 _ => Vec::new(),
328 }
329}
330
331fn edges<'n>(node: &'n Element<'_>) -> impl Iterator<Item = ExGuid> + 'n {
332 node.children
333 .iter()
334 .chain(&node.content)
335 .chain(&node.structure)
336 .copied()
337}
338
339fn is_title(node: &Element<'_>) -> bool {
340 node.extra
341 .first()
342 .is_some_and(|fields| fields.iter().any(|field| field.id == 0x88001cb4))
343}
344
345#[cfg(test)]
346pub(crate) mod tests {
347 use super::*;
348 use crate::{Insertion, ParagraphSplit, TextAttribute, TreeEdit, document::Kind};
349
350 /// An identity from `fresh_guid`, which seeded tests draw deterministically per thread.
351 fn new_id() -> Result<ExGuid> {
352 Ok(ExGuid {
353 guid: crate::write::fresh_guid()?,
354 n: 1,
355 })
356 }
357
358 /// A seeded source of the typed writers' changes: insertions, moves, deletions, splits
359 /// and formatting of what a page holds.
360 pub(crate) struct Writes(pub u64);
361
362 impl Writes {
363 fn pick(&mut self, count: usize) -> usize {
364 self.0 = self
365 .0
366 .wrapping_mul(6364136223846793005)
367 .wrapping_add(1442695040888963407);
368 (self.0 >> 33) as usize % count.max(1)
369 }
370
371 pub(crate) fn next(&mut self, active: &ActivePage<'_>) -> Result<Changes> {
372 let nodes = &active.view.nodes;
373 let listed = |kind: fn(&Kind<'_>) -> bool| -> Vec<ExGuid> {
374 nodes
375 .iter()
376 .filter(|(id, node)| kind(&node.kind) && active.parents.contains_key(id))
377 .map(|(id, _)| *id)
378 .collect()
379 };
380 let paragraphs = listed(|kind| matches!(kind, Kind::Paragraph { .. }));
381 let containers = listed(|kind| {
382 matches!(
383 kind,
384 Kind::Paragraph { .. } | Kind::Outline { .. } | Kind::Cell { .. }
385 )
386 });
387 let texts = listed(|kind| matches!(kind, Kind::RichText { .. }));
388 let unavailable = Error {
389 offset: 0,
390 message: "The page has nothing to edit",
391 };
392 let paragraph = *paragraphs
393 .get(self.pick(paragraphs.len()))
394 .ok_or(unavailable)?;
395 let container = *containers
396 .get(self.pick(containers.len()))
397 .ok_or(unavailable)?;
398 let anchor = nodes[&container].children.get(self.pick(4)).copied();
399 let text = *texts.get(self.pick(texts.len())).ok_or(unavailable)?;
400 let words = ["", "a", "Two words", "東京 🦀", "longer text here"];
401 let word = words[self.pick(words.len())];
402 // `Section::apply` refuses an edit ending with a table cell emptied.
403 let fills_a_cell = active.parents[&paragraph].iter().any(|parent| {
404 matches!(nodes[parent].kind, Kind::Cell { .. })
405 && nodes[parent].children == [paragraph]
406 });
407 let choice = match self.pick(8) {
408 4 | 5 if fills_a_cell => 0,
409 choice => choice,
410 };
411 match choice {
412 0..=3 => {
413 Insertion::paragraph(container, anchor, word, "Author").and_then(|insertion| {
414 let paragraph = new_id()?;
415 insertion.changes_as(active, paragraph, paragraph, new_id()?)
416 })
417 }
418 4 => TreeEdit::move_to(paragraph, container, anchor, "Author")
419 .and_then(|edit| edit.changes(active)),
420 5 => TreeEdit::delete(paragraph, "Author").and_then(|edit| edit.changes(active)),
421 6 => {
422 let at = self.pick(3) as u32;
423 let lists = (0..8).map(|_| new_id()).collect::<Result<Vec<_>>>()?;
424 ParagraphSplit::new(text, at, "Author")
425 .and_then(|split| split.changes_as(active, new_id()?, new_id()?, &lists))
426 }
427 _ => {
428 let end = self.pick(2) as u32;
429 let bold = self.pick(2) == 0;
430 crate::formatting::format_changes(
431 active,
432 text,
433 0..end,
434 &[TextAttribute::Bold(bold)],
435 &[],
436 )
437 }
438 }
439 }
440 }
441
442 /// `active` equals the page `image` stores, views included.
443 fn assert_stores(active: &ActivePage<'_>, image: &[u8], space: ExGuid) {
444 let store = Store::parse(image).unwrap();
445 let index = RevisionIndex::parse(&store).unwrap();
446 let read = ActivePage::parse(&index, space).unwrap();
447 assert_eq!(read.live.revision.roots, active.live.revision.roots);
448 let objects = |page: &ActivePage<'_>| -> Vec<String> {
449 page.live
450 .revision
451 .objects
452 .iter()
453 .map(|(id, object)| format!("{id} {object:?}"))
454 .collect()
455 };
456 assert_eq!(objects(&read), objects(active));
457 assert_eq!(format!("{:?}", read.view), format!("{:?}", active.view));
458 let parents = |page: &ActivePage<'_>| -> Vec<(ExGuid, Vec<ExGuid>)> {
459 page.parents
460 .iter()
461 .map(|(child, parents)| {
462 let mut parents = parents.clone();
463 parents.sort();
464 (*child, parents)
465 })
466 .collect()
467 };
468 assert_eq!(parents(&read), parents(active));
469 assert_eq!(read.titles, active.titles);
470 }
471
472 /// Applies `steps` random writes to the first page of `source` both in memory and by
473 /// appending each revision, comparing the two as it goes.
474 fn check_writes(source: &[u8], steps: usize) {
475 let mut image = source.to_vec();
476 let store = Store::parse(source).unwrap();
477 let index = RevisionIndex::parse(&store).unwrap();
478 let (space, _) = Document::parse(&index).unwrap().pages().unwrap()[0];
479 let arena = Bump::new();
480 let mut active = ActivePage::parse(&index, space).unwrap();
481 let mut writes = Writes(7);
482 for step in 0..steps {
483 let changes = writes.next(&active);
484 let Ok(changes) = changes else {
485 continue;
486 };
487 let store = Store::parse(&image).unwrap();
488 let index = RevisionIndex::parse(&store).unwrap();
489 let written =
490 crate::write::write_revision_on(&index, space, |_| Ok(changes.clone())).unwrap();
491 assert_eq!(
492 active.write(&arena, &[], changes).unwrap(),
493 written != image,
494 "step {step}"
495 );
496 image = written;
497 if step % 40 == 0 {
498 assert_stores(&active, &image, space);
499 }
500 }
501 assert_stores(&active, &image, space);
502 }
503
504 #[test]
505 fn writes_leave_the_page_that_appending_and_reading_their_revisions_does() {
506 // Seeded identities: the writes pick nodes in identity order.
507 crate::write::GUIDS.set(Some(1 << 61));
508 // Past 512 revisions, so the chain checkpoints once.
509 check_writes(
510 include_bytes!(
511 "../../../corpus/native/20260905-05/snapshots/02-text/notebook/synthetic.one"
512 ),
513 720,
514 );
515 check_writes(
516 include_bytes!("../../../corpus/m6/native-features-01/notebook/Features.one"),
517 160,
518 );
519 check_writes(
520 &crate::create_section("model.one", "First", "Author").unwrap(),
521 160,
522 );
523 }
524}