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