1//! A section file kept parsed across edits. Edits apply to its object spaces in memory and
2//! seal into one transaction appending one revision per changed space.
3
4use crate::{
5 Chunk, Error, ExGuid, FileType, ObjectData, Reference, ResolvedRevision, RevisionIndex, Stamp,
6 Store, Transaction,
7 active::{ActivePage, Changes, Files},
8 document::Revision,
9 page::Page,
10 protected::{Key, Opened},
11 store::StoreState,
12 write::{
13 Appending, Commit, LiveRevision, PropertyObject, Protection, Sealing, Written, chain_depth,
14 check_transaction, declared, label_payload, node, replacement, unchanged,
15 },
16};
17use bumpalo::Bump;
18use std::{
19 collections::{BTreeMap, BTreeSet},
20 sync::Arc,
21};
22
23mod versions;
24pub(crate) use versions::HISTORY;
25pub use versions::PageVersion;
26
27type Result<T> = std::result::Result<T, Error>;
28
29/// Holds the bytes a `Section` reads: the image it opened and each transaction it sealed.
30#[derive(Default)]
31pub struct Arena(Bump);
32
33/// A section file as its image and the transactions sealed on it leave it.
34pub struct Section<'a> {
35 arena: &'a Arena,
36 /// The opened image, then the bytes each sealed transaction appended, at their offsets.
37 segments: Vec<(u64, &'a [u8])>,
38 /// The in-place writes of the sealed transactions, in order.
39 patches: Vec<(u64, Vec<u8>)>,
40 state: StoreState,
41 /// Payloads the opened images embed, by identity, as they read.
42 files: &'a [([u8; 16], Result<&'a [u8]>)],
43 /// Payload identities the file-data store declares.
44 declared: BTreeSet<[u8; 16]>,
45 spaces: BTreeMap<ExGuid, Space<'a>>,
46 /// Payloads applied changes embed, in order, until sealed.
47 payloads: Vec<([u8; 16], &'a [u8])>,
48 /// Whether an operation failed after it began changing state; the section must be
49 /// reopened.
50 broken: bool,
51 /// The root object space, which lists the pages.
52 root: ExGuid,
53 /// While an edit applies, the spaces it changed as they were before it.
54 undo: Option<Undo<'a>>,
55 /// A password-protected section's key and what it decoded.
56 unlocked: Option<Opened<'a>>,
57}
58
59#[derive(Default)]
60struct Undo<'a> {
61 /// `None` for a space the edit created.
62 spaces: BTreeMap<ExGuid, Option<Space<'a>>>,
63 payloads: usize,
64}
65
66#[derive(Clone)]
67struct Space<'a> {
68 /// The active revision the file stores; none before a new space's first seal.
69 rid: Option<ExGuid>,
70 state: SpaceState<'a>,
71 /// The version a restore took the open revision from: the revision it depends on, which
72 /// the seal writes even unchanged.
73 restored: Option<ExGuid>,
74 /// Page states restores made versions of, which the seal writes before the open revision.
75 frozen: Vec<Frozen<'a>>,
76 history: Option<History<'a>>,
77 /// Revisions the seal labels as versions, with their contexts.
78 labels: Vec<(ExGuid, ExGuid)>,
79 /// The newest revision a seal appended to the space.
80 newest: Option<ExGuid>,
81}
82
83impl<'a> Space<'a> {
84 fn new(rid: Option<ExGuid>, state: SpaceState<'a>, history: Option<History<'a>>) -> Self {
85 Self {
86 rid,
87 state,
88 restored: None,
89 frozen: Vec::new(),
90 history,
91 labels: Vec::new(),
92 newest: None,
93 }
94 }
95}
96
97/// A page state a restore made a version of: a revision under the identity it chose.
98#[derive(Clone)]
99struct Frozen<'a> {
100 rid: ExGuid,
101 previous: Option<ExGuid>,
102 live: LiveRevision<'a>,
103 revised: Revised,
104}
105
106/// A revision `changed` committed: what it declares, and of those the objects whose bytes it
107/// stores and the objects new to the space.
108#[derive(Clone)]
109struct Revised {
110 commit: Commit,
111 replaced: BTreeSet<ExGuid>,
112 created: BTreeSet<ExGuid>,
113}
114
115/// A page's version history (`versions::HISTORY`), with the objects edits since the last
116/// seal replaced in it.
117#[derive(Clone)]
118struct History<'a> {
119 rid: ExGuid,
120 revision: ResolvedRevision<'a>,
121 depth: usize,
122 pending: BTreeMap<ExGuid, PropertyObject>,
123}
124
125#[derive(Clone)]
126enum SpaceState<'a> {
127 /// As the opened image stores it, until first edited.
128 Stored {
129 revision: ResolvedRevision<'a>,
130 depth: usize,
131 },
132 Open(Box<Open<'a>>),
133}
134
135#[derive(Clone)]
136struct Open<'a> {
137 /// The revision the file stores.
138 file: LiveRevision<'a>,
139 /// `file` with the changes applied since the last seal.
140 page: ActivePage<'a>,
141 /// Objects whose content, reachability or count changed since the last seal.
142 pending: BTreeSet<ExGuid>,
143}
144
145impl<'a> Section<'a> {
146 /// Parses and fully validates a section image.
147 pub fn open(arena: &'a Arena, image: Vec<u8>) -> Result<Self> {
148 Ok(Self::open_with(arena, vec![image], None, current)?)
149 }
150
151 /// `open` for a password-protected section, decoding it under `key`, which edits are
152 /// sealed under too. Decoded bytes live in `arena` until it drops.
153 pub fn unlock(
154 arena: &'a Arena,
155 image: Vec<u8>,
156 key: &Key,
157 ) -> std::result::Result<Self, crate::protected::Error> {
158 Self::open_with(arena, vec![image], Some(key), current)
159 }
160
161 /// Opens an earlier state of a section: each object space in `revisions` at the revision
162 /// given, taken from the first of `images` that stores it, and no other space; the first
163 /// image is the section's. For reading, as a merge reads the state two copies of a section
164 /// last shared, which may lie partly in each copy.
165 pub fn open_at(
166 arena: &'a Arena,
167 images: Vec<Vec<u8>>,
168 revisions: &BTreeMap<ExGuid, ExGuid>,
169 ) -> Result<Self> {
170 let section = Self::open_with(arena, images, None, |id, space| {
171 revisions
172 .get(id)
173 .copied()
174 .filter(|rid| space.revisions.contains_key(rid))
175 })?;
176 if !section.spaces.contains_key(&section.root) {
177 return Err(Error {
178 offset: 0,
179 message: "The earlier state names no revision of the section's root",
180 });
181 }
182 Ok(section)
183 }
184
185 /// `open`, each object space at the revision `revision` chooses in the first image where it
186 /// chooses one; a space it chooses none for is left out. Payloads are read from the image
187 /// that first declares them. A protected section opens under `key`.
188 fn open_with(
189 arena: &'a Arena,
190 images: Vec<Vec<u8>>,
191 key: Option<&Key>,
192 revision: impl Fn(&ExGuid, &crate::ObjectSpace<'_>) -> Option<ExGuid>,
193 ) -> std::result::Result<Self, crate::protected::Error> {
194 let mut opened = None;
195 let mut unlocked = None;
196 let mut spaces = BTreeMap::new();
197 let mut files: Vec<([u8; 16], Result<&'a [u8]>)> = Vec::new();
198 for image in images {
199 let bytes: &'a [u8] = arena.0.alloc_slice_copy(&image);
200 drop(image);
201 let store = Store::parse(bytes)?;
202 if let Some(offset) = store.checksum_mismatches.first() {
203 return Err(Error {
204 offset: *offset,
205 message: "Cannot write a file with transaction checksum damage",
206 }
207 .into());
208 }
209 if store.header.file_type != FileType::Section {
210 return Err(Error {
211 offset: 0,
212 message: "Choose a section file",
213 }
214 .into());
215 }
216 let index = RevisionIndex::parse(&store)?;
217 if let (Some(key), None) = (key, &unlocked) {
218 unlocked = Some(Opened::new(&store, key)?);
219 }
220 // The parse borrows `bytes` only as long as its store; its slices lie in `bytes`,
221 // which the arena keeps.
222 let bound = |resolved| {
223 bind(arena, unlocked.as_ref(), resolved, |part| {
224 Ok(within(bytes, part))
225 })
226 };
227 index.validate_with(|space, rid| bound(index.resolve(space, rid)?))?;
228 for (id, space) in &index.spaces {
229 let Some(rid) = revision(id, space).filter(|_| !spaces.contains_key(id)) else {
230 continue;
231 };
232 let revision = bound(index.resolve(*id, rid)?)?;
233 let history = space
234 .labels
235 .get(&(versions::HISTORY, 1))
236 .map(|history| -> Result<History<'a>> {
237 Ok(History {
238 rid: *history,
239 revision: bound(index.resolve(*id, *history)?)?,
240 depth: chain_depth(&index, *id, *history),
241 pending: BTreeMap::new(),
242 })
243 })
244 .transpose()?;
245 let state = SpaceState::Stored {
246 revision,
247 depth: chain_depth(&index, *id, rid),
248 };
249 spaces.insert(*id, Space::new(Some(rid), state, history));
250 }
251 let known = files.len();
252 for node in store.lists.values().flat_map(|list| &list.nodes) {
253 if node.id != 0x94 || node.freed() {
254 continue;
255 }
256 let (Some(guid), Some(Reference::Data(chunk))) =
257 (node.payload.first_chunk(), node.reference)
258 else {
259 return Err(Error {
260 offset: node.offset,
261 message: "File-data object lacks a data reference",
262 }
263 .into());
264 };
265 // A payload an earlier image declares is the same bytes: it names them.
266 if !files[..known].iter().any(|(declared, ..)| declared == guid) {
267 let (offset, length) = (chunk.offset as usize, chunk.length as usize);
268 let payload = bytes
269 .get(offset..offset + length)
270 .ok_or(Error {
271 offset,
272 message: "Chunk extends outside the data area",
273 })
274 .and_then(|blob| crate::files::payload(blob, offset))
275 .and_then(|payload| match &unlocked {
276 Some(unlocked) => unlocked.file(&arena.0, payload),
277 None => Ok(payload),
278 });
279 files.push((*guid, payload));
280 }
281 }
282 if opened.is_none() {
283 opened = Some((bytes, store.state()?, index.root));
284 }
285 }
286 let (bytes, state, root) = opened.ok_or(Error {
287 offset: 0,
288 message: "Choose a section file",
289 })?;
290 files.sort_by_key(|(guid, ..)| *guid);
291 Ok(Self {
292 arena,
293 segments: vec![(0, bytes)],
294 patches: Vec::new(),
295 state,
296 declared: files.iter().map(|(guid, ..)| *guid).collect(),
297 files: arena.0.alloc_slice_copy(&files),
298 spaces,
299 payloads: Vec::new(),
300 broken: false,
301 root,
302 undo: None,
303 unlocked,
304 })
305 }
306
307 /// The header and length of the image this section's sealed transactions leave.
308 pub fn stamp(&self) -> &Stamp {
309 &self.state.stamp
310 }
311
312 /// The image this section's sealed transactions leave; for tests and seeding caches.
313 pub fn image(&self) -> Vec<u8> {
314 let mut image = self
315 .segments
316 .iter()
317 .flat_map(|(_, bytes)| *bytes)
318 .copied()
319 .collect::<Vec<_>>();
320 for (offset, bytes) in &self.patches {
321 let offset = *offset as usize;
322 image[offset..offset + bytes.len()].copy_from_slice(bytes);
323 }
324 image[..1024].copy_from_slice(&self.state.stamp.header);
325 image
326 }
327
328 /// Each object space with the active revision the sealed image stores for it.
329 pub fn revisions(&self) -> impl Iterator<Item = (ExGuid, ExGuid)> + '_ {
330 self.spaces
331 .iter()
332 .filter_map(|(space, stored)| Some((*space, stored.rid?)))
333 }
334
335 /// Each object space with the revision this section last sealed in it, where one did, or
336 /// its active revision: a seal that changes only a page's versions leaves the page's
337 /// active revision as it was.
338 pub fn newest(&self) -> impl Iterator<Item = (ExGuid, ExGuid)> + '_ {
339 self.spaces
340 .iter()
341 .filter_map(|(space, stored)| Some((*space, stored.newest.or(stored.rid)?)))
342 }
343
344 /// The page an object space holds, with the changes applied since the last seal.
345 pub fn page(&self, space: ExGuid) -> Result<Page> {
346 let stored = self.spaces.get(&space).ok_or(Error {
347 offset: 0,
348 message: "Object space has no active default revision",
349 })?;
350 match &stored.state {
351 SpaceState::Open(open) => one_page(&open.page.view, &open.page.pages),
352 SpaceState::Stored { revision, .. } => {
353 let files = self.files();
354 let (view, _) =
355 Revision::parse(space, revision, FileType::Section, &mut |guid| files(guid))?;
356 one_page(&view, &crate::active::manifest_pages(&view))
357 }
358 }
359 }
360
361 /// The conflict pages of each page that has them, in section order, each page's in the
362 /// order OneNote 2010 lists them under it: the last stored first. Read from the pages'
363 /// manifests and the conflict pages' metadata alone.
364 pub fn conflicts(&mut self) -> Result<Vec<(ExGuid, Vec<crate::ConflictPage>)>> {
365 let listed: Vec<ExGuid> = self.pages()?.into_iter().map(|(space, ..)| space).collect();
366 let element = |object: &crate::Object<'a>| {
367 crate::document::Element::parse_with(object, FileType::Section, &mut |_| {
368 Err(Error {
369 offset: 0,
370 message: "Page metadata holds no payload",
371 })
372 })
373 };
374 let mut conflicts = Vec::new();
375 for page in listed {
376 let revision = self.revision(page)?;
377 let Some(manifest) = revision
378 .roots
379 .get(&1)
380 .and_then(|id| revision.objects.get(id))
381 else {
382 continue;
383 };
384 let mut pages = Vec::new();
385 for space in element(manifest)?.spaces.into_iter().rev() {
386 let Some(metadata) = self.revision(space).ok().and_then(|revision| {
387 revision
388 .roots
389 .get(&2)
390 .and_then(|id| revision.objects.get(id))
391 }) else {
392 continue;
393 };
394 let metadata = element(metadata)?;
395 let crate::document::Kind::ConflictMetadata { title, author, .. } = metadata.kind
396 else {
397 continue;
398 };
399 let created = metadata.extra[0]
400 .iter()
401 .find_map(|field| match field.value {
402 crate::document::FieldValue::Bytes(bytes) if field.id == 0x18001c65 => {
403 bytes.try_into().ok().map(u64::from_le_bytes)
404 }
405 _ => None,
406 });
407 let mut objects = Vec::new();
408 for (id, object) in &self.revision(space)?.objects {
409 let ObjectData::Properties(bytes) = object.data else {
410 continue;
411 };
412 if crate::PropertySets::parse(bytes)?.sets[0]
413 .iter()
414 .any(|property| property.id == 0x88001d96)
415 {
416 objects.push(*id);
417 }
418 }
419 pages.push(crate::ConflictPage {
420 space,
421 title: title.unwrap_or_default(),
422 user: author.unwrap_or_default(),
423 created,
424 objects,
425 });
426 }
427 if !pages.is_empty() {
428 conflicts.push((page, pages));
429 }
430 }
431 Ok(conflicts)
432 }
433
434 /// The page series holding each listed page. Moving a page gives it a series of its
435 /// own, so a page in another series than before was moved.
436 pub fn series(&mut self) -> Result<BTreeMap<ExGuid, ExGuid>> {
437 let view = &self.active(self.root)?.view;
438 let section = view
439 .roots
440 .get(&1)
441 .and_then(|id| view.nodes.get(id))
442 .ok_or(Error {
443 offset: 0,
444 message: "Section root is unavailable",
445 })?;
446 Ok(section
447 .children
448 .iter()
449 .filter_map(|series| Some((*series, view.nodes.get(series)?)))
450 .flat_map(|(series, node)| node.spaces.iter().map(move |page| (*page, series)))
451 .collect())
452 }
453
454 /// Each listed page's notebook-management identity, which internal links name, read
455 /// from its metadata alone.
456 pub fn identities(&mut self) -> Result<Vec<(ExGuid, Option<[u8; 16]>)>> {
457 let spaces: Vec<ExGuid> = self.series()?.into_keys().collect();
458 let mut identities = Vec::new();
459 for space in spaces {
460 let revision = self.revision(space)?;
461 let identity = match (revision.roots.get(&2)).and_then(|id| revision.objects.get(id)) {
462 Some(metadata) => {
463 let metadata = crate::document::Element::parse_with(
464 metadata,
465 FileType::Section,
466 &mut |_| {
467 Err(Error {
468 offset: 0,
469 message: "Page metadata holds no payload",
470 })
471 },
472 )?;
473 crate::page::Page::metadata_identity(&metadata)
474 }
475 None => None,
476 };
477 identities.push((space, identity));
478 }
479 Ok(identities)
480 }
481
482 /// Page spaces in section order with the title and outline level (1 at the top) the
483 /// page list shows, read from each page's metadata alone.
484 pub fn pages(&mut self) -> Result<Vec<(ExGuid, String, u32)>> {
485 let root = self.root;
486 let view = &self.active(root)?.view;
487 let section = view
488 .roots
489 .get(&1)
490 .and_then(|id| view.nodes.get(id))
491 .ok_or(Error {
492 offset: 0,
493 message: "Section root is unavailable",
494 })?;
495 let spaces: Vec<ExGuid> = section
496 .children
497 .iter()
498 .filter_map(|series| view.nodes.get(series))
499 .flat_map(|series| series.spaces.clone())
500 .collect();
501 let element = |object: &crate::Object<'a>| {
502 crate::document::Element::parse_with(object, FileType::Section, &mut |_| {
503 Err(Error {
504 offset: 0,
505 message: "Page metadata holds no payload",
506 })
507 })
508 };
509 let mut pages = Vec::new();
510 for space in spaces {
511 let revision = self.revision(space)?;
512 let (mut title, mut level) = (None, 1);
513 if let Some(metadata) = revision
514 .roots
515 .get(&2)
516 .and_then(|id| revision.objects.get(id))
517 && let crate::document::Kind::Metadata {
518 title: stored,
519 level: stored_level,
520 } = element(metadata)?.kind
521 {
522 title = stored;
523 level = stored_level.unwrap_or(1);
524 }
525 if title.is_none() {
526 let manifest = revision
527 .roots
528 .get(&1)
529 .and_then(|id| revision.objects.get(id));
530 if let Some(manifest) = manifest
531 && let Some(page) = element(manifest)?
532 .content
533 .first()
534 .and_then(|id| revision.objects.get(id))
535 && let crate::document::Kind::Page {
536 alternate_title, ..
537 } = element(page)?.kind
538 {
539 title = alternate_title;
540 }
541 }
542 let title = crate::edit::without_fields(&title.unwrap_or_default());
543 pages.push((space, title, level));
544 }
545 Ok(pages)
546 }
547
548 /// Reads a payload of the opened image by identity.
549 fn files(&self) -> Files<'a> {
550 let files = self.files;
551 std::rc::Rc::new(move |guid| {
552 let start = files.partition_point(|(id, _)| *id < guid);
553 let mut declared = files[start..].iter().take_while(|(id, _)| *id == guid);
554 match (declared.next(), declared.next()) {
555 (None, _) => Err(Error {
556 offset: 0,
557 message: "File-data object is not declared",
558 }),
559 (Some((_, payload)), None) => *payload,
560 _ => Err(Error {
561 offset: 0,
562 message: "Duplicate file-data identity",
563 }),
564 }
565 })
566 }
567
568 fn usable(&self) -> Result<()> {
569 if self.broken {
570 return Err(Error {
571 offset: 0,
572 message: "A failed edit left the section to be reopened",
573 });
574 }
575 Ok(())
576 }
577
578 /// The editable state of an object space, opened on first use.
579 pub(crate) fn active(&mut self, space: ExGuid) -> Result<&ActivePage<'a>> {
580 Ok(&self.editable(space)?.page)
581 }
582
583 fn editable(&mut self, id: ExGuid) -> Result<&mut Open<'a>> {
584 let files = self.files();
585 let space = self.spaces.get_mut(&id).ok_or(Error {
586 offset: 0,
587 message: "Object space has no active default revision",
588 })?;
589 if let SpaceState::Stored { revision, depth } = &space.state {
590 let file = LiveRevision::new(revision.clone(), *depth)?;
591 let page = ActivePage::open(id, file.clone(), FileType::Section, files)?;
592 space.state = SpaceState::Open(Box::new(Open {
593 file,
594 page,
595 pending: BTreeSet::new(),
596 }));
597 }
598 let SpaceState::Open(open) = &mut space.state else {
599 unreachable!()
600 };
601 Ok(open)
602 }
603
604 /// Keeps a space as it is for the running edit to return to, the first time it changes it.
605 pub(crate) fn remember(&mut self, space: ExGuid) {
606 if let Some(undo) = &mut self.undo
607 && !undo.spaces.contains_key(&space)
608 {
609 undo.spaces.insert(space, self.spaces.get(&space).cloned());
610 }
611 }
612
613 /// Stores a writer's objects and payloads in a space until the next seal; false when
614 /// it stores nothing. An error leaves the section to be reopened.
615 pub(crate) fn apply_changes(
616 &mut self,
617 space: ExGuid,
618 payloads: &[([u8; 16], &[u8])],
619 changes: Changes,
620 ) -> Result<bool> {
621 self.usable()?;
622 self.remember(space);
623 let arena = &self.arena.0;
624 self.broken = true;
625 let open = self.editable(space)?;
626 let embedded = open.page.payloads.len();
627 let Some(touched) = open.page.store(arena, payloads, changes)? else {
628 self.broken = false;
629 return Ok(false);
630 };
631 open.pending.extend(touched);
632 let embedded = open.page.payloads[embedded..].to_vec();
633 self.payloads.extend(embedded);
634 self.broken = false;
635 Ok(true)
636 }
637
638 pub(crate) fn attribute(
639 &mut self,
640 space: ExGuid,
641 author: &str,
642 paragraphs: Vec<ExGuid>,
643 ) -> Result<()> {
644 self.broken = true;
645 let guid = crate::write::fresh_guid()?;
646 let named = |n| ExGuid { guid, n };
647 let page = self.active(space)?;
648 let revision = &page.live.revision;
649 let author_id = page.view.nodes.iter().find_map(|(id, node)| {
650 matches!(&node.kind, crate::document::Kind::Author { name } if name.as_deref() == Some(author))
651 .then_some(*id)
652 }).unwrap_or(named(2));
653 let mut changes = Changes::new();
654 if author_id == named(2) {
655 changes.insert(
656 author_id,
657 PropertyObject {
658 jcid: 0x120001,
659 bytes: crate::create::properties(&crate::create::author_properties(author))?,
660 global_ids: Arc::new(BTreeMap::from([(0, guid)])),
661 },
662 );
663 }
664 let metadata_id = revision.roots.get(&4).copied().unwrap_or(named(1));
665 let mut metadata = match revision.objects.get(&metadata_id) {
666 Some(object) if object.jcid == 0x20044 => PropertyObject::from_object(object)?,
667 Some(_) => {
668 return Err(Error {
669 offset: 0,
670 message: "The page's revision metadata is unavailable",
671 });
672 }
673 None => PropertyObject {
674 jcid: 0x20044,
675 bytes: crate::create::properties(&[])?,
676 global_ids: Arc::new(BTreeMap::from([(0, guid)])),
677 },
678 };
679 let (modified, filetime) = crate::create::current_timestamps()?;
680 let reference = metadata.reference(author_id)?;
681 metadata.set(&[
682 (0x18001d77, &filetime.to_le_bytes()),
683 (0x20001d79, &reference),
684 ])?;
685 changes.insert(metadata_id, metadata);
686 for id in paragraphs {
687 let mut paragraph = PropertyObject::from_object(&revision.objects[&id])?;
688 let reference = paragraph.reference(author_id)?;
689 paragraph.set(&[
690 (0x14001d7a, &modified.to_le_bytes()),
691 (0x20001d79, &reference),
692 ])?;
693 changes.insert(id, paragraph);
694 }
695 self.remember(space);
696 self.editable(space)?
697 .page
698 .live
699 .revision
700 .roots
701 .insert(4, metadata_id);
702 self.broken = false;
703 self.apply_changes(space, &[], changes)?;
704 Ok(())
705 }
706
707 /// Creates an object space holding `changes` under `roots` until the next seal, which
708 /// declares it. An error after validation leaves the section to be reopened.
709 pub(crate) fn create_space(
710 &mut self,
711 space: ExGuid,
712 roots: BTreeMap<u32, ExGuid>,
713 changes: Changes,
714 ) -> Result<()> {
715 self.usable()?;
716 if space.guid == [0; 16] || self.spaces.contains_key(&space) {
717 return Err(Error {
718 offset: 0,
719 message: "Choose a new object-space identity in a section file",
720 });
721 }
722 if roots.is_empty() || changes.is_empty() {
723 return Err(Error {
724 offset: 0,
725 message: "New object space needs roots and objects",
726 });
727 }
728 let file = LiveRevision::new(
729 ResolvedRevision {
730 roots,
731 objects: BTreeMap::new(),
732 },
733 0,
734 )?;
735 let mut work = file.clone();
736 let changes = work.prepare(changes, true)?;
737 let mut objects = Vec::new();
738 for (id, change) in changes {
739 let bytes = self.arena.0.alloc_slice_copy(&change.bytes);
740 objects.push((id, declared(change.jcid, bytes, change.global_ids)?));
741 }
742 if let Some(undo) = &mut self.undo {
743 undo.spaces.entry(space).or_insert(None);
744 }
745 self.broken = true;
746 let pending = work.commit(objects)?.touched;
747 let all: Vec<ExGuid> = work.revision.objects.keys().copied().collect();
748 work.settle(all)?;
749 let page = ActivePage::open(space, work, FileType::Section, self.files())?;
750 let state = SpaceState::Open(Box::new(Open {
751 file,
752 page,
753 pending,
754 }));
755 self.spaces.insert(space, Space::new(None, state, None));
756 self.broken = false;
757 Ok(())
758 }
759
760 /// The root object space, which lists the pages.
761 pub fn root(&self) -> ExGuid {
762 self.root
763 }
764
765 /// The stored revision of a space, as edits since the last seal leave it.
766 pub(crate) fn revision(&self, space: ExGuid) -> Result<&ResolvedRevision<'a>> {
767 match self.spaces.get(&space).map(|space| &space.state) {
768 Some(SpaceState::Stored { revision, .. }) => Ok(revision),
769 Some(SpaceState::Open(open)) => Ok(&open.page.live.revision),
770 None => Err(Error {
771 offset: 0,
772 message: "Object space has no active default revision",
773 }),
774 }
775 }
776
777 /// Runs `f`, returning the section to its state before it when `f` fails; `undo`
778 /// saves each space before `f` first changes it, which costs a copy of that space.
779 pub(crate) fn atomically<T, E>(
780 &mut self,
781 undo: bool,
782 f: impl FnOnce(&mut Self) -> std::result::Result<T, E>,
783 ) -> std::result::Result<T, E> {
784 if undo {
785 self.undo = Some(Undo {
786 spaces: BTreeMap::new(),
787 payloads: self.payloads.len(),
788 });
789 }
790 let result = f(self);
791 if let Some(undo) = self.undo.take()
792 && result.is_err()
793 {
794 for (id, space) in undo.spaces {
795 match space {
796 Some(space) => self.spaces.insert(id, space),
797 None => self.spaces.remove(&id),
798 };
799 }
800 self.payloads.truncate(undo.payloads);
801 self.broken = false;
802 }
803 result
804 }
805
806 /// Whether a failed operation left the section to be reopened.
807 pub(crate) fn broken(&self) -> bool {
808 self.broken
809 }
810
811 /// Appends one revision per space changed since the last seal, and the payloads they
812 /// embed, as one transaction on `stamp`; none when nothing changed. An error leaves the
813 /// section to be reopened.
814 pub fn seal(&mut self) -> Result<Option<Transaction>> {
815 self.seal_as(&BTreeMap::new())
816 }
817
818 /// `seal`, each space in `names` taking the revision identity named there, one the space
819 /// does not store, instead of a fresh one: a merge names what it wrote after what it
820 /// merged, so that the next merge knows it holds that.
821 pub fn seal_as(&mut self, names: &BTreeMap<ExGuid, ExGuid>) -> Result<Option<Transaction>> {
822 self.usable()?;
823 if !names.is_empty() {
824 let image = self.image();
825 let store = Store::parse(&image)?;
826 let index = RevisionIndex::parse(&store)?;
827 if names.iter().any(|(space, name)| {
828 name.guid == [0; 16]
829 || (index.spaces.get(space))
830 .is_some_and(|stored| stored.revisions.contains_key(name))
831 }) {
832 return Err(Error {
833 offset: 0,
834 message: "Name each revision anew",
835 });
836 }
837 }
838 self.broken = true;
839 let arena = &self.arena.0;
840 let protection = self
841 .unlocked
842 .as_ref()
843 .map(|unlocked| unlocked as &dyn Protection);
844 let mut appending = Appending::new(self.state.clone());
845 let mut sealed = Vec::new();
846 for (id, space) in &mut self.spaces {
847 // A space's revisions and labels go in one fragment: page states restores made
848 // versions of, the open revision, the version history, then the labels.
849 let mut manifest = Vec::new();
850 for frozen in &space.frozen {
851 appending.manifest(
852 &Sealing {
853 space: *id,
854 previous: frozen.previous,
855 new_space: false,
856 label: (ExGuid::default(), 1),
857 rid: Some(frozen.rid),
858 live: &frozen.live,
859 commit: &frozen.revised.commit,
860 replaced: &frozen.revised.replaced,
861 created: &frozen.revised.created,
862 },
863 &self.segments,
864 protection,
865 &mut manifest,
866 )?;
867 }
868 let mut page = None;
869 if let SpaceState::Open(open) = &mut space.state
870 && (!open.pending.is_empty() || space.restored.is_some())
871 {
872 let file = &mut open.file;
873 let restored = space.restored.is_some();
874 let written = match changed(arena, &open.page.live, &open.pending, file, restored)?
875 {
876 Some(Revised {
877 commit,
878 replaced,
879 created,
880 }) => {
881 let (rid, stored) = appending.manifest(
882 &Sealing {
883 space: *id,
884 previous: space.restored.or(space.rid),
885 new_space: space.rid.is_none(),
886 label: (ExGuid::default(), 1),
887 rid: names.get(id).copied(),
888 live: file,
889 commit: &commit,
890 replaced: &replaced,
891 created: &created,
892 },
893 &self.segments,
894 protection,
895 &mut manifest,
896 )?;
897 if commit.checkpoint {
898 let all: Vec<ExGuid> = file.revision.objects.keys().copied().collect();
899 file.settle(all)?;
900 } else {
901 file.settle(commit.changed.iter().copied())?;
902 }
903 Some((rid, stored, commit))
904 }
905 None => None,
906 };
907 page = Some(written);
908 }
909 let mut history = None;
910 if let Some(stored) = &space.history
911 && !stored.pending.is_empty()
912 {
913 let mut live = LiveRevision::new(stored.revision.clone(), stored.depth)?;
914 let replacements = live.prepare(stored.pending.clone(), true)?;
915 if !replacements.is_empty() {
916 let replaced: BTreeSet<ExGuid> = replacements.keys().copied().collect();
917 let created = replaced
918 .iter()
919 .filter(|id| !live.revision.objects.contains_key(id))
920 .copied()
921 .collect();
922 let mut objects = Vec::new();
923 for (object_id, change) in replacements {
924 let bytes = arena.alloc_slice_copy(&change.bytes);
925 objects.push((object_id, declared(change.jcid, bytes, change.global_ids)?));
926 }
927 let commit = live.commit(objects)?;
928 let (rid, chunks) = appending.manifest(
929 &Sealing {
930 space: *id,
931 previous: Some(stored.rid),
932 new_space: false,
933 label: (versions::HISTORY, 1),
934 rid: None,
935 live: &live,
936 commit: &commit,
937 replaced: &replaced,
938 created: &created,
939 },
940 &self.segments,
941 protection,
942 &mut manifest,
943 )?;
944 if commit.checkpoint {
945 let all: Vec<ExGuid> = live.revision.objects.keys().copied().collect();
946 live.settle(all)?;
947 } else {
948 live.settle(commit.changed.iter().copied())?;
949 }
950 history = Some((rid, chunks, live, commit));
951 }
952 }
953 for (rid, context) in &space.labels {
954 manifest.push(node(0x5d, None, &label_payload(*rid, *context))?);
955 }
956 if !manifest.is_empty() {
957 appending.close(*id, space.rid.is_none(), &manifest)?;
958 }
959 if page.is_some() || !manifest.is_empty() {
960 sealed.push((*id, page, history));
961 }
962 }
963 let payloads: Vec<_> = self
964 .payloads
965 .iter()
966 .filter(|(guid, _)| !self.declared.contains(guid))
967 .copied()
968 .collect();
969 appending.payloads(&payloads, protection)?;
970 #[cfg_attr(not(test), expect(unused_mut))]
971 let mut transaction = appending.finish()?;
972 #[cfg(test)]
973 if let (Some(tamper), Some((transaction, _))) = (tests::TAMPER.get(), &mut transaction) {
974 tamper(transaction);
975 }
976 if let Some((transaction, state)) = &transaction {
977 let mut written = Vec::new();
978 let mut labels = Vec::new();
979 for (id, page, history) in &sealed {
980 let space = &self.spaces[id];
981 for frozen in &space.frozen {
982 written.push(Written {
983 space: *id,
984 rid: frozen.rid,
985 previous: frozen.previous,
986 label: (ExGuid::default(), 1),
987 live: &frozen.live,
988 commit: &frozen.revised.commit,
989 });
990 }
991 if let (Some(Some((rid, _, commit))), SpaceState::Open(open)) = (page, &space.state)
992 {
993 written.push(Written {
994 space: *id,
995 rid: *rid,
996 previous: space.restored.or(space.rid),
997 label: (ExGuid::default(), 1),
998 live: &open.file,
999 commit,
1000 });
1001 }
1002 if let (Some((rid, _, live, commit)), Some(stored)) = (history, &space.history) {
1003 written.push(Written {
1004 space: *id,
1005 rid: *rid,
1006 previous: Some(stored.rid),
1007 label: (versions::HISTORY, 1),
1008 live,
1009 commit,
1010 });
1011 }
1012 labels.extend(
1013 space
1014 .labels
1015 .iter()
1016 .map(|(rid, context)| (*id, *rid, *context)),
1017 );
1018 }
1019 check_transaction(
1020 &self.state,
1021 state,
1022 transaction,
1023 &self.segments,
1024 &written,
1025 &labels,
1026 &payloads,
1027 protection,
1028 )?;
1029 let base = transaction.base.length;
1030 let segment: &'a [u8] = arena.alloc_slice_copy(&transaction.append);
1031 self.segments.push((base, segment));
1032 self.patches.extend(transaction.patches.iter().cloned());
1033 self.state = state.clone();
1034 self.declared.extend(payloads.iter().map(|(guid, _)| *guid));
1035 // An object now reads from where it is stored, or a protected one's clear bytes
1036 // from where they are.
1037 let unlocked = &self.unlocked;
1038 let rebind = |revision: &mut ResolvedRevision<'a>, stored: &[(ExGuid, Chunk)]| {
1039 for (object_id, chunk) in stored {
1040 let start = (chunk.offset - base) as usize;
1041 let bytes = &segment[start..start + chunk.length as usize];
1042 let data = &mut revision.objects.get_mut(object_id).unwrap().data;
1043 match (unlocked, *data) {
1044 (Some(unlocked), ObjectData::Properties(clear)) => {
1045 unlocked.sealed(clear, bytes)
1046 }
1047 _ => *data = ObjectData::Properties(bytes),
1048 }
1049 }
1050 };
1051 for (id, page, history) in &mut sealed {
1052 let space = self.spaces.get_mut(id).unwrap();
1053 space.frozen.clear();
1054 space.labels.clear();
1055 if let (Some(Some((rid, stored, _))), SpaceState::Open(open)) =
1056 (&*page, &mut space.state)
1057 {
1058 space.rid = Some(*rid);
1059 space.restored = None;
1060 space.newest = Some(*rid);
1061 rebind(&mut open.file.revision, stored);
1062 }
1063 if let Some((rid, stored, live, _)) = history.take() {
1064 let mut revision = live.revision;
1065 rebind(&mut revision, &stored);
1066 space.history = Some(History {
1067 rid,
1068 revision,
1069 depth: live.depth,
1070 pending: BTreeMap::new(),
1071 });
1072 space.newest = Some(rid);
1073 }
1074 }
1075 }
1076 for (id, page, _) in sealed {
1077 let Some(revision) = page else {
1078 continue;
1079 };
1080 let SpaceState::Open(open) = &mut self.spaces.get_mut(&id).unwrap().state else {
1081 unreachable!()
1082 };
1083 let mut compare = std::mem::take(&mut open.pending);
1084 if let Some((_, _, commit)) = revision {
1085 if commit.checkpoint {
1086 compare.extend(open.file.revision.objects.keys());
1087 } else {
1088 compare.extend(commit.touched);
1089 }
1090 }
1091 open.page.adopt(&open.file, compare)?;
1092 }
1093 self.payloads.clear();
1094 self.broken = false;
1095 Ok(transaction.map(|(transaction, _)| transaction))
1096 }
1097
1098 /// Applies a transaction sealed on this section's stamp, as reopening the image it
1099 /// leaves would; nothing may be applied since the last seal.
1100 pub fn replay(&mut self, transaction: &Transaction) -> Result<()> {
1101 self.usable()?;
1102 if !self.payloads.is_empty()
1103 || self.spaces.values().any(
1104 |space| matches!(&space.state, SpaceState::Open(open) if !open.pending.is_empty()),
1105 )
1106 {
1107 return Err(Error {
1108 offset: 0,
1109 message: "Seal applied changes before replaying a transaction",
1110 });
1111 }
1112 let mut image = self.image();
1113 transaction.apply(&mut image)?;
1114 let key = self
1115 .unlocked
1116 .as_ref()
1117 .map(|unlocked| unlocked.key().clone());
1118 *self = Self::open_with(self.arena, vec![image], key.as_ref(), current)?;
1119 Ok(())
1120 }
1121}
1122
1123/// Commits to `file` the objects `pending` names that `page` changed, with what the revision
1124/// declares, replaces and creates; none when that changes nothing, unless `force`.
1125fn changed<'a>(
1126 arena: &'a Bump,
1127 page: &LiveRevision<'a>,
1128 pending: &BTreeSet<ExGuid>,
1129 file: &mut LiveRevision<'a>,
1130 force: bool,
1131) -> Result<Option<Revised>> {
1132 let mut replacements = BTreeMap::new();
1133 for object_id in pending {
1134 if !page.is_reachable(*object_id) {
1135 continue;
1136 }
1137 let object = &page.revision.objects[object_id];
1138 if let Some(stored) = file.revision.objects.get(object_id)
1139 && unchanged(stored, object)?
1140 {
1141 continue;
1142 }
1143 replacements.insert(*object_id, replacement(*object_id, object)?);
1144 }
1145 let replacements = file.prepare(replacements, true)?;
1146 if replacements.is_empty() && !force {
1147 return Ok(None);
1148 }
1149 let replaced: BTreeSet<ExGuid> = replacements.keys().copied().collect();
1150 let created = replaced
1151 .iter()
1152 .filter(|id| !file.revision.objects.contains_key(id))
1153 .copied()
1154 .collect();
1155 let mut objects = Vec::new();
1156 for (object_id, change) in replacements {
1157 // The page holds these bytes already unless preparing remapped them.
1158 let bytes = match page.revision.objects.get(&object_id).map(|o| o.data) {
1159 Some(ObjectData::Properties(bytes)) if bytes == change.bytes => bytes,
1160 _ => arena.alloc_slice_copy(&change.bytes),
1161 };
1162 objects.push((object_id, declared(change.jcid, bytes, change.global_ids)?));
1163 }
1164 Ok(Some(Revised {
1165 commit: file.commit_as(objects, page.revision.roots.clone())?,
1166 replaced,
1167 created,
1168 }))
1169}
1170
1171/// `resolved` with every slice moved into bytes that live as long as the section by `bytes`,
1172/// a protected section's objects decoded under `unlocked`.
1173fn bind<'a>(
1174 arena: &'a Arena,
1175 unlocked: Option<&Opened<'a>>,
1176 resolved: ResolvedRevision<'_>,
1177 bytes: impl Fn(&[u8]) -> Result<&'a [u8]>,
1178) -> Result<ResolvedRevision<'a>> {
1179 let mut objects = BTreeMap::new();
1180 for (id, object) in resolved.objects {
1181 let data = match (object.data, unlocked) {
1182 (ObjectData::Properties(data), _) => ObjectData::Properties(bytes(data)?),
1183 (ObjectData::Encrypted(data), Some(unlocked)) => {
1184 ObjectData::Properties(unlocked.property(&arena.0, bytes(data)?)?)
1185 }
1186 (ObjectData::Encrypted(data), None) => ObjectData::Encrypted(bytes(data)?),
1187 (
1188 ObjectData::File {
1189 reference,
1190 extension,
1191 },
1192 _,
1193 ) => ObjectData::File {
1194 reference: bytes(reference)?,
1195 extension: bytes(extension)?,
1196 },
1197 };
1198 let object = crate::Object {
1199 jcid: object.jcid,
1200 reference_count: object.reference_count,
1201 data,
1202 global_ids: object.global_ids,
1203 };
1204 objects.insert(id, object);
1205 }
1206 Ok(ResolvedRevision {
1207 roots: resolved.roots,
1208 objects,
1209 })
1210}
1211
1212/// The revision a space is current under.
1213fn current(_: &ExGuid, space: &crate::ObjectSpace<'_>) -> Option<ExGuid> {
1214 space.labels.get(&(ExGuid::default(), 1)).copied()
1215}
1216
1217/// `part`, a slice of `image`, with the image's lifetime.
1218fn within<'a>(image: &'a [u8], part: &[u8]) -> &'a [u8] {
1219 let start = part.as_ptr().addr() - image.as_ptr().addr();
1220 &image[start..start + part.len()]
1221}
1222
1223fn one_page(view: &Revision<'_>, pages: &[ExGuid]) -> Result<Page> {
1224 let [page] = pages else {
1225 return Err(Error {
1226 offset: 0,
1227 message: "Choose an object space containing one active page",
1228 });
1229 };
1230 Page::from_revision(view, *page)
1231}
1232
1233#[cfg(test)]
1234mod tests {
1235 use super::*;
1236 use crate::{Insertion, active::tests::Writes, document::Document, write::GUIDS};
1237
1238 thread_local! {
1239 /// Changes a transaction after it is built and before it is checked.
1240 pub(super) static TAMPER: std::cell::Cell<Option<fn(&mut Transaction)>> =
1241 const { std::cell::Cell::new(None) };
1242 }
1243
1244 /// Page identities read from metadata alone are those the whole page holds.
1245 #[test]
1246 fn identities_are_those_the_pages_hold() {
1247 let bytes = include_bytes!("../../../corpus/link-edit/native-links/notebook/links.one");
1248 let arena = Arena::default();
1249 let mut section = Section::open(&arena, bytes.to_vec()).unwrap();
1250 let identities = section.identities().unwrap();
1251 assert_eq!(identities.len(), section.pages().unwrap().len());
1252 for (space, identity) in identities {
1253 assert!(identity.is_some());
1254 assert_eq!(identity, section.page(space).unwrap().identity);
1255 }
1256 }
1257
1258 /// `f` with `fresh_guid` counting from `seed`.
1259 fn seeded<T>(seed: u64, f: impl FnOnce() -> T) -> T {
1260 let outer = GUIDS.replace(Some(seed));
1261 let result = f();
1262 GUIDS.set(outer);
1263 result
1264 }
1265
1266 /// The image the image writer leaves: the `edited` revisions squashed onto the source
1267 /// `index` parsed.
1268 fn squashed(
1269 index: &RevisionIndex<'_>,
1270 edited: &[(ExGuid, &ResolvedRevision<'_>)],
1271 payloads: &[([u8; 16], &[u8])],
1272 ) -> Vec<u8> {
1273 let transaction = crate::write::squash(index, edited, payloads).unwrap();
1274 crate::write::applied(index.store.data, transaction.as_ref()).unwrap()
1275 }
1276
1277 /// The page spaces of an image, fullest first.
1278 fn page_spaces(image: &[u8]) -> Vec<ExGuid> {
1279 let store = Store::parse(image).unwrap();
1280 let index = RevisionIndex::parse(&store).unwrap();
1281 let document = Document::parse(&index).unwrap();
1282 let mut spaces: Vec<_> = document
1283 .pages()
1284 .unwrap()
1285 .into_iter()
1286 .map(|(space, _)| (document.active(space).unwrap().nodes.len(), space))
1287 .collect();
1288 spaces.sort_by(|a, b| b.cmp(a));
1289 spaces.into_iter().map(|(_, space)| space).collect()
1290 }
1291
1292 /// Applies seeded batches of typed-writer changes to the pages of `source` through a
1293 /// `Section` and through the writer that parses the image and squashes a batch into
1294 /// one revision, requiring equal bytes after every seal.
1295 fn differential(
1296 source: &[u8],
1297 seed: u64,
1298 batches: usize,
1299 largest: usize,
1300 pages: usize,
1301 ) -> usize {
1302 let arena = Arena::default();
1303 let mut section = Section::open(&arena, source.to_vec()).unwrap();
1304 let spaces = page_spaces(source);
1305 let mut image = source.to_vec();
1306 let mut writes = Writes(seed);
1307 // New objects count from far above the identities builds draw.
1308 GUIDS.set(Some(1 << 62 | seed << 40));
1309 let (mut sealed, mut checkpoints) = (0, 0);
1310 for batch in 0..batches {
1311 // The writers stamp modification times; a fixed clock keeps the batches alike.
1312 let at = 134_000_000_000_000_000 + batch as u64 * 10_000_000;
1313 crate::create::at(at, || {
1314 let space = spaces[batch % spaces.len().min(pages)];
1315 let store = Store::parse(&image).unwrap();
1316 let index = RevisionIndex::parse(&store).unwrap();
1317 let bump = Bump::new();
1318 let mut legacy = ActivePage::parse(&index, space).unwrap();
1319 for _ in 0..1 + (writes.0 as usize >> 40) % largest {
1320 let Ok(changes) = writes.next(section.active(space).unwrap()) else {
1321 continue;
1322 };
1323 let stored = legacy.write(&bump, &[], changes.clone()).unwrap();
1324 assert_eq!(
1325 section.apply_changes(space, &[], changes).unwrap(),
1326 stored,
1327 "batch {batch}"
1328 );
1329 }
1330 let guids = (batch as u64 + 1) << 32;
1331 let expected = seeded(guids, || {
1332 squashed(&index, &[(space, &legacy.live.revision)], &legacy.payloads)
1333 });
1334 let before = section.stamp().clone();
1335 let chains = depths(&section);
1336 let transaction = seeded(guids, || section.seal().unwrap());
1337 checkpoints += depths(&section)
1338 .iter()
1339 .filter(|(id, depth)| chains.get(id).is_some_and(|before| before > depth))
1340 .count();
1341 let mut written = image.clone();
1342 if let Some(transaction) = &transaction {
1343 assert_eq!(transaction.base, before);
1344 transaction.apply(&mut written).unwrap();
1345 sealed += 1;
1346 }
1347 assert!(written == expected, "batch {batch}");
1348 assert_eq!(Stamp::of(&written).unwrap(), *section.stamp());
1349 drop(legacy);
1350 drop(index);
1351 drop(store);
1352 image = expected;
1353 if batch % 25 == 0 || batch + 1 == batches {
1354 assert!(section.image() == image);
1355 let store = Store::parse(&image).unwrap();
1356 let index = RevisionIndex::parse(&store).unwrap();
1357 index.validate_current().unwrap();
1358 let document = Document::parse(&index).unwrap();
1359 for space in &spaces {
1360 assert_eq!(
1361 section.page(*space).unwrap(),
1362 Page::from_space(&document, *space).unwrap()
1363 );
1364 }
1365 }
1366 });
1367 }
1368 GUIDS.set(None);
1369 assert!(sealed > 0, "no batch of {batches} sealed");
1370 checkpoints
1371 }
1372
1373 /// Chain depths of the spaces a section has opened.
1374 fn depths(section: &Section<'_>) -> BTreeMap<ExGuid, usize> {
1375 section
1376 .spaces
1377 .iter()
1378 .filter_map(|(id, space)| match &space.state {
1379 SpaceState::Open(open) => Some((*id, open.file.depth)),
1380 SpaceState::Stored { .. } => None,
1381 })
1382 .collect()
1383 }
1384
1385 #[test]
1386 fn seals_append_the_bytes_the_image_writer_does() {
1387 let corpus = [
1388 include_bytes!(
1389 "../../../corpus/native/20260905-05/snapshots/02-text/notebook/synthetic.one"
1390 )
1391 .as_slice(),
1392 include_bytes!("../../../corpus/m6/native-features-01/notebook/Features.one"),
1393 include_bytes!("../../../corpus/outline-edit/tree/before/notebook/synthetic.one"),
1394 include_bytes!("../../../corpus/paragraph-edit/before/notebook/synthetic.one"),
1395 ];
1396 let shift = crate::sweep::full().unwrap_or(0);
1397 for (seed, source) in (shift..).zip(corpus) {
1398 differential(source, seed, 60, 1, 2);
1399 differential(source, seed + 100, 60, 5, 2);
1400 }
1401 // Seeded identities: the writes pick nodes in identity order.
1402 let created = seeded(7, || {
1403 crate::create_section("model.one", "First", "Author").unwrap()
1404 });
1405 differential(&created, 7 + shift, 60, 3, 1);
1406 }
1407
1408 #[test]
1409 fn wide_batches_regroup_and_alias_as_the_image_writer_does() {
1410 // These seeds make a seal alias read-only objects or group tables across writes
1411 // differently from the writes themselves, so the pages adopt the sealed form.
1412 let corpus = [
1413 include_bytes!("../../../corpus/m6/native-features-01/notebook/Features.one")
1414 .as_slice(),
1415 include_bytes!("../../../corpus/outline-edit/tree/before/notebook/synthetic.one"),
1416 include_bytes!("../../../corpus/paragraph-edit/before/notebook/synthetic.one"),
1417 ];
1418 for seed in crate::sweep::seeds(4..9, 5) {
1419 for source in corpus {
1420 differential(source, seed, 30, 12, 3);
1421 }
1422 }
1423 }
1424
1425 #[test]
1426 fn a_long_chain_checkpoints_as_the_image_writer_does() {
1427 // Past 512 revisions of one space, so the chain checkpoints once.
1428 let checkpoints = differential(
1429 include_bytes!(
1430 "../../../corpus/native/20260905-05/snapshots/02-text/notebook/synthetic.one"
1431 ),
1432 11,
1433 560,
1434 2,
1435 1,
1436 );
1437 assert_eq!(checkpoints, 1);
1438 }
1439
1440 #[test]
1441 fn a_created_space_seals_as_the_image_writer_creates_it() {
1442 let source = &crate::create_section("model.one", "First", "Author").unwrap();
1443 let store = Store::parse(source).unwrap();
1444 let index = RevisionIndex::parse(&store).unwrap();
1445 // A page without history, whose objects name no other space or context.
1446 let (copied, revision, reachable) = page_spaces(source)
1447 .into_iter()
1448 .map(|space| {
1449 let revision = index.resolve_active(space).unwrap();
1450 let reachable = revision.reachable().unwrap();
1451 (space, revision, reachable)
1452 })
1453 .find(|(_, revision, reachable)| {
1454 reachable.iter().all(|id| {
1455 let references = revision.objects[id].references().unwrap();
1456 references.object_spaces.is_empty() && references.contexts.is_empty()
1457 })
1458 })
1459 .unwrap();
1460 let objects: Changes = reachable
1461 .iter()
1462 .map(|id| (*id, replacement(*id, &revision.objects[id]).unwrap()))
1463 .collect();
1464 let space = ExGuid {
1465 guid: [7; 16],
1466 n: 0,
1467 };
1468 let expected = seeded(1, || {
1469 crate::write::write_revisions(source, |_| {
1470 Ok(BTreeMap::from([(
1471 space,
1472 crate::write::RevisionEdit::Create {
1473 roots: revision.roots.clone(),
1474 objects: objects.clone(),
1475 },
1476 )]))
1477 })
1478 .unwrap()
1479 });
1480 let arena = Arena::default();
1481 let mut section = Section::open(&arena, source.to_vec()).unwrap();
1482 section
1483 .create_space(space, revision.roots.clone(), objects)
1484 .unwrap();
1485 assert_eq!(section.page(space).unwrap(), section.page(copied).unwrap());
1486 seeded(1, || section.seal().unwrap()).unwrap();
1487 assert!(section.image() == expected);
1488 // The space's next revision depends on the one creating it.
1489 let mut writes = Writes(5);
1490 let mut image = expected;
1491 let mut written = 0;
1492 for batch in 0..6 {
1493 let Ok(changes) = writes.next(section.active(space).unwrap()) else {
1494 continue;
1495 };
1496 written += 1;
1497 section.apply_changes(space, &[], changes.clone()).unwrap();
1498 let guids = (batch + 2) << 32;
1499 let store = Store::parse(&image).unwrap();
1500 let index = RevisionIndex::parse(&store).unwrap();
1501 let bump = Bump::new();
1502 // The root lists no page in this space, so no document reaches it.
1503 let rid = index.active(space).unwrap();
1504 let live = LiveRevision::new(
1505 index.resolve(space, rid).unwrap(),
1506 chain_depth(&index, space, rid),
1507 )
1508 .unwrap();
1509 let store = &store;
1510 let files: Files<'_> = std::rc::Rc::new(|guid| store.file_data(guid));
1511 let mut legacy = ActivePage::open(space, live, FileType::Section, files).unwrap();
1512 legacy.write(&bump, &[], changes).unwrap();
1513 let expected = seeded(guids, || {
1514 let revision = &legacy.live.revision;
1515 squashed(&index, &[(space, revision)], &[])
1516 });
1517 drop(legacy);
1518 drop(index);
1519 image = expected;
1520 seeded(guids, || section.seal().unwrap());
1521 assert!(section.image() == image, "batch {batch}");
1522 }
1523 assert!(written > 2);
1524 let reopened = Section::open(&arena, image).unwrap();
1525 assert_eq!(reopened.page(space).unwrap(), section.page(space).unwrap());
1526 }
1527
1528 #[test]
1529 fn payloads_embed_once_as_the_image_writer_embeds_them() {
1530 let source = include_bytes!("../../../corpus/m6/native-features-01/notebook/Features.one");
1531 let space = page_spaces(source)[0];
1532 let payload = ([9; 16], b"payload bytes".as_slice());
1533 let arena = Arena::default();
1534 let mut section = Section::open(&arena, source.to_vec()).unwrap();
1535 let mut image = source.to_vec();
1536 for seed in [1_u64 << 32, 2 << 32] {
1537 assert!(
1538 section
1539 .apply_changes(space, &[payload], Changes::new())
1540 .unwrap()
1541 );
1542 let store = Store::parse(&image).unwrap();
1543 let index = RevisionIndex::parse(&store).unwrap();
1544 let legacy = ActivePage::parse(&index, space).unwrap();
1545 let expected = seeded(seed, || {
1546 let revision = &legacy.live.revision;
1547 squashed(&index, &[(space, revision)], &[payload])
1548 });
1549 let transaction = seeded(seed, || section.seal().unwrap());
1550 assert_eq!(transaction.is_some(), expected != image);
1551 assert!(section.image() == expected);
1552 drop(legacy);
1553 drop(index);
1554 drop(store);
1555 image = expected;
1556 }
1557 let store = Store::parse(&image).unwrap();
1558 assert_eq!(store.file_data(payload.0).unwrap(), payload.1);
1559 }
1560
1561 #[test]
1562 fn a_seal_checks_the_bytes_it_appends() {
1563 fn utf16(text: &str) -> Vec<u8> {
1564 text.encode_utf16().flat_map(u16::to_le_bytes).collect()
1565 }
1566 fn object_bytes(transaction: &mut Transaction) {
1567 let text = utf16("Tampered text");
1568 let at = transaction
1569 .append
1570 .windows(text.len())
1571 .position(|w| w == text)
1572 .unwrap();
1573 transaction.append[at] ^= 1;
1574 }
1575 fn link(transaction: &mut Transaction) {
1576 let (_, bytes) = transaction
1577 .patches
1578 .iter_mut()
1579 .find(|(_, b)| b.len() == 12)
1580 .unwrap();
1581 bytes[0] ^= 8;
1582 }
1583 fn sentinel(transaction: &mut Transaction) {
1584 let (_, bytes) = transaction.patches.last_mut().unwrap();
1585 *bytes.last_mut().unwrap() ^= 1;
1586 }
1587 fn header(transaction: &mut Transaction) {
1588 transaction.header[96] ^= 2;
1589 }
1590 let source = include_bytes!("../../../corpus/m6/native-features-01/notebook/Features.one");
1591 let space = page_spaces(source)[0];
1592 let seal = |tamper: Option<fn(&mut Transaction)>| {
1593 let arena = Arena::default();
1594 let mut section = Section::open(&arena, source.to_vec()).unwrap();
1595 let page = section.active(space).unwrap();
1596 let changes = page
1597 .view
1598 .nodes
1599 .iter()
1600 .filter(|(id, node)| {
1601 matches!(node.kind, crate::document::Kind::Outline { .. })
1602 && page.parents.contains_key(id)
1603 })
1604 .find_map(|(outline, _)| {
1605 let paragraph = crate::page::text::new_id().ok()?;
1606 let text = crate::page::text::new_id().ok()?;
1607 Insertion::paragraph(*outline, None, "Tampered text", "Author")
1608 .and_then(|insertion| {
1609 insertion.changes_as(page, paragraph, paragraph, text)
1610 })
1611 .ok()
1612 })
1613 .unwrap();
1614 section.apply_changes(space, &[], changes).unwrap();
1615 TAMPER.set(tamper);
1616 let sealed = section.seal();
1617 TAMPER.set(None);
1618 let error = sealed.as_ref().err().map(|error| error.message);
1619 assert_eq!(section.seal().is_err(), error.is_some());
1620 error
1621 };
1622 assert_eq!(seal(None), None);
1623 for tamper in [object_bytes, link, sentinel, header] {
1624 assert!(seal(Some(tamper)).is_some());
1625 }
1626 }
1627
1628 #[test]
1629 fn a_seal_refuses_a_root_naming_another_object() {
1630 thread_local! {
1631 static OTHER: std::cell::Cell<ExGuid> = const { std::cell::Cell::new(ExGuid {
1632 guid: [0; 16],
1633 n: 0,
1634 }) };
1635 }
1636 // The new metadata root declared as the page's content root, an object it holds.
1637 fn root(transaction: &mut Transaction) {
1638 let header = 0x8000705a_u32.to_le_bytes();
1639 let at = 4 + transaction
1640 .append
1641 .windows(4)
1642 .position(|w| w == header)
1643 .unwrap();
1644 let mut other = Vec::new();
1645 OTHER.get().encode(&mut other);
1646 transaction.append[at..at + 20].copy_from_slice(&other);
1647 }
1648 let source = crate::create_section("root.one", "Original", "Author").unwrap();
1649 let space = page_spaces(&source)[0];
1650 let seal = |tamper: Option<fn(&mut Transaction)>| {
1651 let arena = Arena::default();
1652 let mut section = Section::open(&arena, source.clone()).unwrap();
1653 section.attribute(space, "Author", Vec::new()).unwrap();
1654 OTHER.set(section.active(space).unwrap().live.revision.roots[&1]);
1655 TAMPER.set(tamper);
1656 let sealed = section.seal();
1657 TAMPER.set(None);
1658 sealed.err().map(|error| error.message)
1659 };
1660 assert_eq!(seal(None), None);
1661 assert_eq!(
1662 seal(Some(root)),
1663 Some("A revision declares other objects or roots than it changed")
1664 );
1665 }
1666
1667 #[test]
1668 fn a_replayed_transaction_leaves_the_sealing_section() {
1669 let source = include_bytes!("../../../corpus/m6/native-features-01/notebook/Features.one");
1670 let space = page_spaces(source)[0];
1671 let arena = Arena::default();
1672 let mut sealing = Section::open(&arena, source.to_vec()).unwrap();
1673 let mut replaying = Section::open(&arena, source.to_vec()).unwrap();
1674 let mut writes = Writes(3);
1675 for _ in 0..8 {
1676 for _ in 0..3 {
1677 if let Ok(changes) = writes.next(sealing.active(space).unwrap()) {
1678 sealing.apply_changes(space, &[], changes).unwrap();
1679 }
1680 }
1681 let Some(transaction) = sealing.seal().unwrap() else {
1682 continue;
1683 };
1684 let queued: Transaction =
1685 serde_json::from_str(&serde_json::to_string(&transaction).unwrap()).unwrap();
1686 assert_eq!(queued, transaction);
1687 replaying.replay(&queued).unwrap();
1688 assert_eq!(replaying.stamp(), sealing.stamp());
1689 assert!(replaying.image() == sealing.image());
1690 assert_eq!(replaying.page(space).unwrap(), sealing.page(space).unwrap());
1691 }
1692 }
1693}
1694
1695#[cfg(test)]
1696mod probe {
1697 use super::*;
1698 use crate::{document::Kind, edit::text_changes};
1699 use std::time::{Duration, Instant};
1700
1701 fn median(mut samples: Vec<Duration>) -> Duration {
1702 samples.sort();
1703 samples[samples.len() / 2]
1704 }
1705
1706 /// The fullest page space of `image` and a rich-text object in its middle.
1707 fn target(image: &[u8]) -> (ExGuid, ExGuid, usize) {
1708 let store = Store::parse(image).unwrap();
1709 let index = RevisionIndex::parse(&store).unwrap();
1710 let document = crate::document::Document::parse(&index).unwrap();
1711 let texts = |space: ExGuid| -> Vec<ExGuid> {
1712 document
1713 .active(space)
1714 .unwrap()
1715 .nodes
1716 .iter()
1717 .filter(|(_, node)| {
1718 matches!(
1719 node.kind,
1720 Kind::RichText {
1721 boilerplate: false,
1722 ..
1723 }
1724 )
1725 })
1726 .map(|(id, _)| *id)
1727 .collect()
1728 };
1729 let (space, _) = document
1730 .pages()
1731 .unwrap()
1732 .into_iter()
1733 .max_by_key(|(space, _)| texts(*space).len())
1734 .unwrap();
1735 let texts = texts(space);
1736 (space, texts[texts.len() / 2], texts.len())
1737 }
1738
1739 /// One-character edits of a large page through a `Section`: `SECTION_PROBE=path cargo test --release -p onestore --lib probe -- --ignored --nocapture`.
1740 #[test]
1741 #[ignore]
1742 fn keystrokes() {
1743 let path = std::env::var("SECTION_PROBE").unwrap_or("/tmp/probe3000.one".into());
1744 let image = std::fs::read(&path).unwrap();
1745 let (space, text, count) = target(&image);
1746 println!(
1747 "{path}: {} bytes, {count} text objects on the page",
1748 image.len()
1749 );
1750
1751 let arena = Arena::default();
1752 let start = Instant::now();
1753 let mut section = Section::open(&arena, image.clone()).unwrap();
1754 println!("Section::open: {:?}", start.elapsed());
1755 let start = Instant::now();
1756 section.active(space).unwrap();
1757 println!("first edit opens the page: {:?}", start.elapsed());
1758 let (mut applies, mut seals, mut sizes) = (Vec::new(), Vec::new(), Vec::new());
1759 for keystroke in 0..200u32 {
1760 let start = Instant::now();
1761 let changes = text_changes(
1762 section.active(space).unwrap(),
1763 text,
1764 keystroke..keystroke,
1765 "x",
1766 )
1767 .unwrap();
1768 section.apply_changes(space, &[], changes).unwrap();
1769 applies.push(start.elapsed());
1770 let start = Instant::now();
1771 let transaction = section.seal().unwrap().unwrap();
1772 seals.push(start.elapsed());
1773 sizes.push((
1774 transaction.append.len(),
1775 transaction
1776 .patches
1777 .iter()
1778 .map(|(_, bytes)| bytes.len())
1779 .sum::<usize>(),
1780 ));
1781 }
1782 println!(
1783 "first seal: appended {} bytes, patched {} bytes",
1784 sizes[0].0, sizes[0].1
1785 );
1786 sizes.sort();
1787 println!(
1788 "Section, one keystroke: apply {:?}, seal {:?}; appended {:?} bytes, patched {:?} bytes (median)",
1789 median(applies),
1790 median(seals),
1791 sizes[sizes.len() / 2].0,
1792 sizes[sizes.len() / 2].1,
1793 );
1794 let start = Instant::now();
1795 let reopened = Section::open(&arena, section.image()).unwrap();
1796 println!("reopen after 200 seals: {:?}", start.elapsed());
1797 assert_eq!(reopened.page(space).unwrap(), section.page(space).unwrap());
1798 }
1799}