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 let mut attach = Vec::new();
237 let mut detach = Vec::new();
238 let mut gone = BTreeMap::new();
239 for id in touched {
240 let reachable = self.live.is_reachable(id);
241 let viewed = self.view.nodes.contains_key(&id);
242 if reachable == viewed && !(reachable && replaced.contains(&id)) {
243 continue;
244 }
245 let fresh = if reachable {
246 Some(self.element(&self.live.revision.objects[&id])?)
247 } else {
248 None
249 };
250 let old = self.view.nodes.remove(&id);
251 // An element leaving the view detaches with its last parent.
252 if let Some(node) = &fresh
253 && (self.parents.contains_key(&id) || self.pages.contains(&id))
254 {
255 let before: Vec<ExGuid> = old.iter().flat_map(edges).collect();
256 let after: Vec<ExGuid> = edges(node).collect();
257 let (removed, added) = differing(&before, &after);
258 detach.extend(removed.iter().map(|child| (id, *child)));
259 attach.extend(added.iter().map(|child| (id, *child)));
260 }
261 self.titles.remove(&id);
262 if let Some(node) = fresh {
263 if is_title(&node) {
264 self.titles.insert(id);
265 }
266 self.view.nodes.insert(id, node);
267 } else if let Some(node) = old {
268 gone.insert(id, node);
269 }
270 }
271 let node = |nodes: &BTreeMap<ExGuid, Element<'a>>, id: ExGuid| {
272 nodes
273 .get(&id)
274 .or_else(|| gone.get(&id))
275 .map(|node| edges(node).collect::<Vec<_>>())
276 .ok_or(Error {
277 offset: 0,
278 message: "Page content is unavailable",
279 })
280 };
281 // Attaching before detaching keeps a moved subtree from being walked twice.
282 while let Some((parent, child)) = attach.pop() {
283 let parents = self.parents.entry(child).or_default();
284 parents.push(parent);
285 if parents.len() == 1 && !self.pages.contains(&child) {
286 attach.extend(
287 node(&self.view.nodes, child)?
288 .into_iter()
289 .map(|grandchild| (child, grandchild)),
290 );
291 }
292 }
293 while let Some((parent, child)) = detach.pop() {
294 let parents = self.parents.get_mut(&child).unwrap();
295 let at = parents.iter().position(|id| *id == parent).unwrap();
296 parents.remove(at);
297 if parents.is_empty() {
298 self.parents.remove(&child);
299 if !self.pages.contains(&child) {
300 detach.extend(
301 node(&self.view.nodes, child)?
302 .into_iter()
303 .map(|grandchild| (child, grandchild)),
304 );
305 }
306 }
307 }
308 Ok(())
309 }
310}
311
312/// The pages a page space's manifest lists.
313pub(crate) fn manifest_pages(view: &Revision<'_>) -> Vec<ExGuid> {
314 match view.roots.get(&1).and_then(|id| view.nodes.get(id)) {
315 Some(manifest) if matches!(manifest.kind, Kind::Manifest { .. }) => manifest
316 .content
317 .iter()
318 .filter(|id| {
319 matches!(
320 view.nodes.get(id).map(|node| &node.kind),
321 Some(Kind::Page { .. })
322 )
323 })
324 .copied()
325 .collect(),
326 _ => Vec::new(),
327 }
328}
329
330fn edges<'n>(node: &'n Element<'_>) -> impl Iterator<Item = ExGuid> + 'n {
331 node.children
332 .iter()
333 .chain(&node.content)
334 .chain(&node.structure)
335 .copied()
336}
337
338fn is_title(node: &Element<'_>) -> bool {
339 node.extra
340 .first()
341 .is_some_and(|fields| fields.iter().any(|field| field.id == 0x88001cb4))
342}
343
344#[cfg(test)]
345pub(crate) mod tests {
346 use super::*;
347 use crate::{Insertion, ParagraphSplit, TextAttribute, TreeEdit, document::Kind};
348
349 /// An identity from `fresh_guid`, which seeded tests draw deterministically per thread.
350 fn new_id() -> Result<ExGuid> {
351 Ok(ExGuid {
352 guid: crate::write::fresh_guid()?,
353 n: 1,
354 })
355 }
356
357 /// A seeded source of the typed writers' changes: insertions, moves, deletions, splits
358 /// and formatting of what a page holds.
359 pub(crate) struct Writes(pub u64);
360
361 impl Writes {
362 fn pick(&mut self, count: usize) -> usize {
363 self.0 = self
364 .0
365 .wrapping_mul(6364136223846793005)
366 .wrapping_add(1442695040888963407);
367 (self.0 >> 33) as usize % count.max(1)
368 }
369
370 pub(crate) fn next(&mut self, active: &ActivePage<'_>) -> Result<Changes> {
371 let nodes = &active.view.nodes;
372 let listed = |kind: fn(&Kind<'_>) -> bool| -> Vec<ExGuid> {
373 nodes
374 .iter()
375 .filter(|(id, node)| kind(&node.kind) && active.parents.contains_key(id))
376 .map(|(id, _)| *id)
377 .collect()
378 };
379 let paragraphs = listed(|kind| matches!(kind, Kind::Paragraph { .. }));
380 let containers = listed(|kind| {
381 matches!(
382 kind,
383 Kind::Paragraph { .. } | Kind::Outline { .. } | Kind::Cell { .. }
384 )
385 });
386 let texts = listed(|kind| matches!(kind, Kind::RichText { .. }));
387 let unavailable = Error {
388 offset: 0,
389 message: "The page has nothing to edit",
390 };
391 let paragraph = *paragraphs
392 .get(self.pick(paragraphs.len()))
393 .ok_or(unavailable)?;
394 let container = *containers
395 .get(self.pick(containers.len()))
396 .ok_or(unavailable)?;
397 let anchor = nodes[&container].children.get(self.pick(4)).copied();
398 let text = *texts.get(self.pick(texts.len())).ok_or(unavailable)?;
399 let words = ["", "a", "Two words", "東京 🦀", "longer text here"];
400 let word = words[self.pick(words.len())];
401 // `Section::apply` refuses an edit ending with a table cell emptied.
402 let fills_a_cell = active.parents[&paragraph].iter().any(|parent| {
403 matches!(nodes[parent].kind, Kind::Cell { .. })
404 && nodes[parent].children == [paragraph]
405 });
406 let choice = match self.pick(8) {
407 4 | 5 if fills_a_cell => 0,
408 choice => choice,
409 };
410 match choice {
411 0..=3 => {
412 Insertion::paragraph(container, anchor, word, "Author").and_then(|insertion| {
413 let paragraph = new_id()?;
414 insertion.changes_as(active, paragraph, paragraph, new_id()?)
415 })
416 }
417 4 => TreeEdit::move_to(paragraph, container, anchor, "Author")
418 .and_then(|edit| edit.changes(active)),
419 5 => TreeEdit::delete(paragraph, "Author").and_then(|edit| edit.changes(active)),
420 6 => {
421 let at = self.pick(3) as u32;
422 let lists = (0..8).map(|_| new_id()).collect::<Result<Vec<_>>>()?;
423 ParagraphSplit::new(text, at, "Author")
424 .and_then(|split| split.changes_as(active, new_id()?, new_id()?, &lists))
425 }
426 _ => {
427 let end = self.pick(2) as u32;
428 let bold = self.pick(2) == 0;
429 crate::formatting::format_changes(
430 active,
431 text,
432 0..end,
433 &[TextAttribute::Bold(bold)],
434 &[],
435 )
436 }
437 }
438 }
439 }
440
441 /// `active` equals the page `image` stores, views included.
442 fn assert_stores(active: &ActivePage<'_>, image: &[u8], space: ExGuid) {
443 let store = Store::parse(image).unwrap();
444 let index = RevisionIndex::parse(&store).unwrap();
445 let read = ActivePage::parse(&index, space).unwrap();
446 assert_eq!(read.live.revision.roots, active.live.revision.roots);
447 let objects = |page: &ActivePage<'_>| -> Vec<String> {
448 page.live
449 .revision
450 .objects
451 .iter()
452 .map(|(id, object)| format!("{id} {object:?}"))
453 .collect()
454 };
455 assert_eq!(objects(&read), objects(active));
456 assert_eq!(format!("{:?}", read.view), format!("{:?}", active.view));
457 let parents = |page: &ActivePage<'_>| -> Vec<(ExGuid, Vec<ExGuid>)> {
458 page.parents
459 .iter()
460 .map(|(child, parents)| {
461 let mut parents = parents.clone();
462 parents.sort();
463 (*child, parents)
464 })
465 .collect()
466 };
467 assert_eq!(parents(&read), parents(active));
468 assert_eq!(read.titles, active.titles);
469 }
470
471 /// Applies `steps` random writes to the first page of `source` both in memory and by
472 /// appending each revision, comparing the two as it goes.
473 fn check_writes(source: &[u8], steps: usize) {
474 let mut image = source.to_vec();
475 let store = Store::parse(source).unwrap();
476 let index = RevisionIndex::parse(&store).unwrap();
477 let (space, _) = Document::parse(&index).unwrap().pages().unwrap()[0];
478 let arena = Bump::new();
479 let mut active = ActivePage::parse(&index, space).unwrap();
480 let mut writes = Writes(7);
481 for step in 0..steps {
482 let changes = writes.next(&active);
483 let Ok(changes) = changes else {
484 continue;
485 };
486 let store = Store::parse(&image).unwrap();
487 let index = RevisionIndex::parse(&store).unwrap();
488 let written =
489 crate::write::write_revision_on(&index, space, |_| Ok(changes.clone())).unwrap();
490 assert_eq!(
491 active.write(&arena, &[], changes).unwrap(),
492 written != image,
493 "step {step}"
494 );
495 image = written;
496 if step % 40 == 0 {
497 assert_stores(&active, &image, space);
498 }
499 }
500 assert_stores(&active, &image, space);
501 }
502
503 #[test]
504 fn writes_leave_the_page_that_appending_and_reading_their_revisions_does() {
505 // Seeded identities: the writes pick nodes in identity order.
506 crate::write::GUIDS.set(Some(1 << 61));
507 // Past 512 revisions, so the chain checkpoints once.
508 check_writes(
509 include_bytes!(
510 "../../../corpus/native/20260905-05/snapshots/02-text/notebook/synthetic.one"
511 ),
512 720,
513 );
514 check_writes(
515 include_bytes!("../../../corpus/m6/native-features-01/notebook/Features.one"),
516 160,
517 );
518 check_writes(
519 &crate::create_section("model.one", "First", "Author").unwrap(),
520 160,
521 );
522 }
523}