1use onestore::{
2 ExGuid, RevisionIndex, Store,
3 document::{Document, Kind, Revision},
4 op::{Op, PageOp},
5};
6use std::collections::{BTreeMap, BTreeSet};
7
8#[path = "support/current.rs"]
9mod current;
10#[path = "support/disk.rs"]
11mod disk;
12#[path = "support/metadata.rs"]
13mod metadata;
14#[path = "support/ops.rs"]
15mod ops;
16#[path = "support/sweep.rs"]
17mod sweep;
18#[path = "support/tree_model.rs"]
19mod tree_model;
20
21const FIXTURES: [(&[u8], &[u8]); 2] = [
22 (
23 include_bytes!("../../../corpus/outline-edit/before/notebook/synthetic.one"),
24 include_bytes!("../../../corpus/outline-edit/after/notebook/synthetic.one"),
25 ),
26 (
27 include_bytes!("../../../corpus/outline-edit/tree/before/notebook/synthetic.one"),
28 include_bytes!("../../../corpus/outline-edit/tree/after/notebook/synthetic.one"),
29 ),
30];
31
32#[test]
33fn twelve_client_tree_schedules_preserve_content_and_indentation() {
34 let runs = sweep::seeds(0..80, 4);
35 let mut random = 1932 + runs.start;
36 for _ in runs {
37 let input: Vec<_> = (0..241)
38 .map(|_| {
39 random ^= random << 13;
40 random ^= random >> 7;
41 random ^= random << 17;
42 random as u8
43 })
44 .collect();
45 tree_model::run(&input);
46 }
47}
48
49fn active(view: &Revision<'_>, page: ExGuid) -> BTreeSet<ExGuid> {
50 let mut pending = vec![page];
51 let mut ids = BTreeSet::new();
52 while let Some(id) = pending.pop() {
53 assert!(ids.insert(id), "Repeated active identity: {id}");
54 let node = &view.nodes[&id];
55 pending.extend(
56 node.children
57 .iter()
58 .chain(&node.content)
59 .chain(&node.structure)
60 .copied(),
61 );
62 }
63 ids
64}
65
66/// The container `id` lies in, outline groups passed over.
67fn container(view: &Revision<'_>, ids: &BTreeSet<ExGuid>, id: ExGuid) -> ExGuid {
68 let mut at = *ids
69 .iter()
70 .find(|parent| view.nodes[parent].children.contains(&id))
71 .unwrap();
72 while matches!(view.nodes[&at].kind, Kind::OutlineGroup) {
73 at = container(view, ids, at);
74 }
75 at
76}
77
78/// The outline level of each paragraph in `outline`.
79fn levels(view: &Revision<'_>, outline: ExGuid) -> BTreeMap<ExGuid, u32> {
80 let mut levels = BTreeMap::new();
81 let mut pending = vec![(outline, 0)];
82 while let Some((id, level)) = pending.pop() {
83 let node = &view.nodes[&id];
84 if matches!(node.kind, Kind::Paragraph { .. }) {
85 levels.insert(id, level);
86 }
87 let child = level + u32::from(node.child_level.unwrap_or(1));
88 pending.extend(node.children.iter().map(|id| (*id, child)));
89 }
90 levels
91}
92
93/// The named edit of a fixture page as ops, with the object it acts on.
94fn operation(view: &Revision<'_>, page: ExGuid) -> Option<(String, ExGuid, Vec<PageOp>)> {
95 let Kind::Metadata {
96 title: Some(name), ..
97 } = &view.nodes[&view.roots[&2]].kind
98 else {
99 panic!()
100 };
101 let ids = active(view, page);
102 let paragraphs: BTreeMap<_, _> = ids
103 .iter()
104 .filter_map(|id| {
105 let node = &view.nodes[id];
106 let text = node.content.first()?;
107 match &view.nodes[text].kind {
108 Kind::RichText { text, .. } if matches!(node.kind, Kind::Paragraph { .. }) => {
109 Some((text.as_str(), *id))
110 }
111 _ => None,
112 }
113 })
114 .collect();
115 let target = *paragraphs
116 .iter()
117 .find(|(text, _)| text.starts_with("Target "))?
118 .1;
119 let outline = *view.nodes[&page]
120 .children
121 .iter()
122 .find(|id| matches!(view.nodes[id].kind, Kind::Outline { .. }))
123 .unwrap();
124 let parent = container(view, &ids, target);
125 let move_to = |parent, before| PageOp::Move {
126 object: target,
127 parent: Some(parent),
128 before,
129 };
130 let edit = match name.as_str() {
131 "Delete outline" => vec![PageOp::Delete { object: outline }],
132 "Delete sole cell paragraph" => vec![
133 PageOp::Insert {
134 container: parent,
135 before: None,
136 paragraphs: vec![ops::paragraph("")],
137 },
138 PageOp::Delete { object: target },
139 ],
140 name if name.starts_with("Delete") => vec![PageOp::Delete { object: target }],
141 "Move leaf down"
142 | "Move subtree down"
143 | "Move numbered subtree down"
144 | "Move cell subtree down" => vec![move_to(parent, None)],
145 "Move subtree up" => vec![move_to(parent, Some(paragraphs["Anchor"]))],
146 "Indent subtree" | "Indent bullet subtree" => vec![move_to(paragraphs["Anchor"], None)],
147 "Outdent subtree" | "Outdent first group" => {
148 // Levels are absolute: the subtree moves up to the outline's first level.
149 let levels = levels(view, outline);
150 let shift = levels[&target] - 1;
151 let mut ops = vec![move_to(outline, Some(paragraphs["Trailing sibling"]))];
152 let mut pending = vec![target];
153 while let Some(paragraph) = pending.pop() {
154 ops.push(PageOp::Level {
155 paragraph,
156 level: levels[&paragraph] - shift,
157 });
158 pending.extend(view.nodes[&paragraph].children.iter().rev());
159 }
160 ops
161 }
162 _ => return None,
163 };
164 Some((
165 name.clone(),
166 if name == "Delete outline" {
167 outline
168 } else {
169 target
170 },
171 edit,
172 ))
173}
174
175#[test]
176fn native_subtree_controls_match_with_preserved_fields_and_history() {
177 let mut count = 0;
178 for (source, native) in FIXTURES {
179 let store = Store::parse(source).unwrap();
180 let index = RevisionIndex::parse(&store).unwrap();
181 let document = Document::parse(&index).unwrap();
182 let native_store = Store::parse(native).unwrap();
183 let native_index = RevisionIndex::parse(&native_store).unwrap();
184 let native_document = Document::parse(&native_index).unwrap();
185 let mut candidate = source.to_vec();
186 for (sid, page) in document.pages().unwrap() {
187 let space = &document.spaces[&sid];
188 let before = &space.revisions[&space.contexts[&ExGuid::default()]];
189 let Some((name, object, edit)) = operation(before, page) else {
190 continue;
191 };
192 let edit: Vec<Op> = edit
193 .into_iter()
194 .map(|op| Op::Page { space: sid, op })
195 .collect();
196 let started = ops::now();
197 let prepared = ops::apply(source, "Tree author", edit.clone())
198 .unwrap_or_else(|error| panic!("{name}: {error}"));
199 let finished = ops::now();
200 let after_store = Store::parse(prepared.as_bytes()).unwrap();
201 assert!(after_store.checksum_mismatches.is_empty());
202 let after_index = RevisionIndex::parse(&after_store).unwrap();
203 after_index.validate_current().unwrap();
204 let after_document = Document::parse(&after_index).unwrap();
205 let space = &after_document.spaces[&sid];
206 let after = &space.revisions[&space.contexts[&ExGuid::default()]];
207 let old_raw = index.resolve_active(sid).unwrap();
208 let new_raw = after_index.resolve_active(sid).unwrap();
209 let at = metadata::check(&old_raw, &new_raw, "Tree author");
210 assert!((started..=finished).contains(&at));
211 let author = metadata::author(&new_raw.objects[&new_raw.roots[&4]]);
212 let space = &native_document.spaces[&sid];
213 let reference = &space.revisions[&space.contexts[&ExGuid::default()]];
214 let old_ids = active(before, page);
215 let actual = active(after, page);
216 let native_ids = active(reference, page);
217 assert_eq!(
218 actual.intersection(&old_ids).collect::<Vec<_>>(),
219 native_ids.intersection(&old_ids).collect::<Vec<_>>(),
220 "{name}"
221 );
222 assert_eq!(actual.len(), native_ids.len(), "{name}");
223 let mut mutable = BTreeSet::new();
224 for view in [before, after] {
225 let ids = active(view, page);
226 if !ids.contains(&object) {
227 continue;
228 }
229 let mut pending = vec![object];
230 while let Some(id) = pending.pop() {
231 mutable.insert(id);
232 pending.extend(
233 ids.iter()
234 .filter(|parent| {
235 view.nodes[parent]
236 .children
237 .iter()
238 .chain(&view.nodes[parent].content)
239 .chain(&view.nodes[parent].structure)
240 .any(|child| *child == id)
241 })
242 .copied(),
243 );
244 }
245 }
246 let mut remap = BTreeMap::new();
247 if name == "Delete sole cell paragraph" {
248 for kind in ["Paragraph", "RichText"] {
249 let selected = |view: &Revision<'_>, ids: &BTreeSet<ExGuid>| {
250 *ids.difference(&old_ids)
251 .find(|id| {
252 serde_json::to_value(&view.nodes[id].kind).unwrap()["type"] == kind
253 })
254 .unwrap()
255 };
256 remap.insert(selected(reference, &native_ids), selected(after, &actual));
257 }
258 }
259 for id in &actual {
260 let reference_id = remap
261 .iter()
262 .find_map(|(a, b)| (b == id).then_some(*a))
263 .unwrap_or(*id);
264 let wanted = &reference.nodes[&reference_id];
265 let node = &after.nodes[id];
266 for (a, b) in [
267 (&node.children, &wanted.children),
268 (&node.content, &wanted.content),
269 (&node.structure, &wanted.structure),
270 ] {
271 assert_eq!(
272 *a,
273 b.iter()
274 .map(|id| remap.get(id).copied().unwrap_or(*id))
275 .collect::<Vec<_>>(),
276 "{name}: {id}"
277 );
278 }
279 if !node.children.is_empty() {
280 assert_eq!(node.child_level, wanted.child_level, "{name}: {id}");
281 }
282 if old_ids.contains(id) {
283 let old = &before.nodes[id];
284 let mut expected = serde_json::to_value(old).unwrap();
285 let mut actual = serde_json::to_value(node).unwrap();
286 expected["children"] = actual["children"].clone();
287 if !node.children.is_empty() {
288 expected["child_level"] = actual["child_level"].clone();
289 }
290 if mutable.contains(id)
291 || node.child_level != old.child_level
292 || node.children != old.children
293 {
294 assert!(node.modified >= old.modified);
295 expected["modified"] = actual["modified"].clone();
296 if matches!(node.kind, Kind::Paragraph { .. }) {
297 assert_eq!(node.latest_author, Some(author));
298 assert_eq!(
299 node.modified.map(u64::from),
300 Some(at / 10_000_000 - 11_960_006_400)
301 );
302 expected["latest_author"] = actual["latest_author"].clone();
303 }
304 }
305 for value in [&mut expected, &mut actual] {
306 value["extra"][0]
307 .as_array_mut()
308 .unwrap()
309 .sort_by_key(|field| field["id"].as_u64().unwrap());
310 }
311 assert_eq!(actual, expected, "{name}: preserved {id}");
312 if matches!(old.kind, Kind::RichText { .. }) {
313 assert_eq!(
314 serde_json::to_value(node).unwrap(),
315 serde_json::to_value(old).unwrap(),
316 "{name}: text {id}"
317 );
318 }
319 assert_eq!(
320 serde_json::to_value(&node.kind).unwrap(),
321 serde_json::to_value(&old.kind).unwrap(),
322 "{name}: kind {id}"
323 );
324 assert_eq!(
325 serde_json::to_value(&node.tags).unwrap(),
326 serde_json::to_value(&old.tags).unwrap(),
327 "{name}: tags {id}"
328 );
329 } else if let (
330 Kind::RichText {
331 text, boilerplate, ..
332 },
333 Kind::RichText {
334 text: native,
335 boilerplate: native_boilerplate,
336 ..
337 },
338 ) = (&node.kind, &wanted.kind)
339 {
340 // A new run carries the language MS-ONE requires, which OneNote omits.
341 assert_eq!((text, boilerplate), (native, native_boilerplate));
342 }
343 }
344 for (sid, space) in &index.spaces {
345 for rid in space.revisions.keys() {
346 let old = index.resolve(*sid, *rid).unwrap();
347 let retained = after_index.resolve(*sid, *rid).unwrap();
348 assert_eq!(old.roots, retained.roots);
349 for (id, object) in old.objects {
350 assert_eq!(object.data, retained.objects[&id].data);
351 }
352 }
353 }
354 let another = ops::apply(source, "Tree author", edit.clone()).unwrap();
355 let second_store = Store::parse(another.as_bytes()).unwrap();
356 let second_index = RevisionIndex::parse(&second_store).unwrap();
357 let second_doc = Document::parse(&second_index).unwrap();
358 let space = &second_doc.spaces[&sid];
359 assert_eq!(
360 actual,
361 active(&space.revisions[&space.contexts[&ExGuid::default()]], page)
362 );
363 candidate = ops::apply(&candidate, "Tree author", edit).unwrap().image;
364 count += 1;
365 }
366 if let Some(output) = std::env::var_os("ONESTORE_TREE_OUTPUT") {
367 let output = std::path::PathBuf::from(output).join(if source == FIXTURES[0].0 {
368 "ordinary"
369 } else {
370 "groups-cells"
371 });
372 assert!(output.is_absolute());
373 std::fs::create_dir_all(&output).unwrap();
374 std::fs::write(output.join("synthetic.one"), candidate).unwrap();
375 }
376 }
377 assert_eq!(count, 18);
378}
379
380#[test]
381fn moves_reject_cycles_wrong_parents_and_stale_siblings() {
382 let source = onestore::create_section("tree.one", "Text", "Author").unwrap();
383 let store = Store::parse(&source).unwrap();
384 let index = RevisionIndex::parse(&store).unwrap();
385 let document = Document::parse(&index).unwrap();
386 let (sid, page) = document.pages().unwrap()[0];
387 let space = &document.spaces[&sid];
388 let view = &space.revisions[&space.contexts[&ExGuid::default()]];
389 let outline = *view.nodes[&page]
390 .children
391 .iter()
392 .find(|id| matches!(view.nodes[id].kind, Kind::Outline { .. }))
393 .unwrap();
394 let paragraph = view.nodes[&outline].children[0];
395 let text = view.nodes[&paragraph].content[0];
396 let move_to = |object, parent, before| PageOp::Move {
397 object,
398 parent: Some(parent),
399 before,
400 };
401 for op in [
402 PageOp::Delete { object: page },
403 PageOp::Delete { object: text },
404 move_to(outline, paragraph, None),
405 move_to(paragraph, paragraph, None),
406 move_to(paragraph, text, None),
407 move_to(paragraph, outline, Some(page)),
408 ] {
409 assert!(ops::page_op(&source, sid, op).is_err());
410 }
411 for before in [None, Some(paragraph)] {
412 let op = move_to(paragraph, outline, before);
413 assert_eq!(ops::page_op(&source, sid, op).unwrap().as_bytes(), source);
414 }
415}
416
417#[test]
418fn publication_interruptions_expose_complete_old_or_new_trees() {
419 let source = FIXTURES[1].0;
420 let store = Store::parse(source).unwrap();
421 let index = RevisionIndex::parse(&store).unwrap();
422 let document = Document::parse(&index).unwrap();
423 let before = current::current(source);
424 let mut count = 0;
425 for (sid, page) in document.pages().unwrap() {
426 let space = &document.spaces[&sid];
427 let view = &space.revisions[&space.contexts[&ExGuid::default()]];
428 let Some((name, _, intent)) = operation(view, page) else {
429 continue;
430 };
431 if !matches!(
432 name.as_str(),
433 "Delete sole cell paragraph"
434 | "Delete unindented sibling after group"
435 | "Move cell subtree down"
436 ) {
437 continue;
438 }
439 let intent = intent
440 .into_iter()
441 .map(|op| Op::Page { space: sid, op })
442 .collect();
443 let edit = ops::apply(source, "Tree author", intent).unwrap();
444 let after = current::current(edit.as_bytes());
445 for write_limit in [17, 4096] {
446 let disk = |fail_at| disk::Disk {
447 visible: source.to_vec(),
448 durable: source.to_vec(),
449 operation: 0,
450 fail_at,
451 write_limit,
452 random: 1931,
453 };
454 let mut success = disk(None);
455 edit.commit(&mut success).unwrap();
456 assert_eq!(success.durable, edit.as_bytes());
457 for at in 1..=success.operation {
458 let mut interrupted = disk(Some(at));
459 let failure = edit.commit(&mut interrupted).unwrap_err();
460 let actual = current::current(&interrupted.durable);
461 assert!(actual == before || actual == after, "{name}: {at}");
462 match failure.state {
463 onestore::CommitState::NotCommitted => assert_eq!(actual, before),
464 onestore::CommitState::Committed => assert_eq!(actual, after),
465 onestore::CommitState::Unknown => {}
466 }
467 }
468 }
469 count += 1;
470 }
471 assert_eq!(count, 3);
472}
473
474#[test]
475fn cross_container_moves_keep_tables_and_replace_emptied_cells() {
476 let source = FIXTURES[1].0;
477 let store = Store::parse(source).unwrap();
478 let index = RevisionIndex::parse(&store).unwrap();
479 let document = Document::parse(&index).unwrap();
480 let mut candidate = source.to_vec();
481 let mut count = 0;
482 for (sid, page) in document.pages().unwrap() {
483 let space = &document.spaces[&sid];
484 let view = &space.revisions[&space.contexts[&ExGuid::default()]];
485 let Kind::Metadata {
486 title: Some(name), ..
487 } = &view.nodes[&view.roots[&2]].kind
488 else {
489 panic!()
490 };
491 if !matches!(
492 name.as_str(),
493 "Outdent first group"
494 | "Delete sole cell paragraph"
495 | "Move cell subtree down"
496 | "Delete cell subtree"
497 ) {
498 continue;
499 }
500 let ids = active(view, page);
501 let parents: BTreeMap<_, _> = ids
502 .iter()
503 .flat_map(|id| view.nodes[id].children.iter().map(|child| (*child, *id)))
504 .collect();
505 let target=*ids.iter().find(|id| view.nodes[id].content.first().is_some_and(|text| matches!(&view.nodes[text].kind,Kind::RichText{text,..} if text.starts_with("Target ")))).unwrap();
506 let outlines: Vec<_> = view.nodes[&page]
507 .children
508 .iter()
509 .copied()
510 .filter(|id| matches!(view.nodes[id].kind, Kind::Outline { .. }))
511 .collect();
512 let cells: Vec<_> = ids
513 .iter()
514 .copied()
515 .filter(|id| matches!(view.nodes[id].kind, Kind::Cell { .. }))
516 .collect();
517 let (object, destination) = match name.as_str() {
518 "Outdent first group" => (*view.nodes[&outlines[0]].children.last().unwrap(), target),
519 "Delete sole cell paragraph" => (
520 target,
521 *cells.iter().find(|id| **id != parents[&target]).unwrap(),
522 ),
523 "Move cell subtree down" => (target, outlines[1]),
524 _ => (view.nodes[&outlines[0]].children[0], outlines[1]),
525 };
526 let mut intent = vec![Op::Page {
527 space: sid,
528 op: PageOp::Move {
529 object,
530 parent: Some(destination),
531 before: None,
532 },
533 }];
534 // A cell keeps a paragraph: its replacement goes in first.
535 if name == "Delete sole cell paragraph" {
536 let op = PageOp::Insert {
537 container: parents[&target],
538 before: None,
539 paragraphs: vec![ops::paragraph("")],
540 };
541 intent.insert(0, Op::Page { space: sid, op });
542 }
543 let edit = ops::apply(source, "Tree author", intent.clone()).unwrap();
544 let store = Store::parse(edit.as_bytes()).unwrap();
545 let index = RevisionIndex::parse(&store).unwrap();
546 let document = Document::parse(&index).unwrap();
547 let space = &document.spaces[&sid];
548 let after = &space.revisions[&space.contexts[&ExGuid::default()]];
549 assert_eq!(after.nodes[&destination].children.last(), Some(&object));
550 let actual = active(after, page);
551 for id in ids.intersection(&actual) {
552 let old = &view.nodes[id];
553 let node = &after.nodes[id];
554 assert_eq!(node.content, old.content, "{name}: {id}");
555 assert_eq!(
556 serde_json::to_value(&node.kind).unwrap(),
557 serde_json::to_value(&old.kind).unwrap()
558 );
559 if matches!(
560 node.kind,
561 Kind::RichText { .. } | Kind::Table { .. } | Kind::Row | Kind::Cell { .. }
562 ) {
563 assert_eq!(
564 serde_json::to_value(&node.format).unwrap(),
565 serde_json::to_value(&old.format).unwrap()
566 );
567 assert_eq!(
568 serde_json::to_value(&node.layout).unwrap(),
569 serde_json::to_value(&old.layout).unwrap()
570 );
571 }
572 }
573 match name.as_str() {
574 "Outdent first group" => {
575 assert_eq!(after.nodes[&outlines[0]].children, [target]);
576 assert_eq!(after.nodes[&outlines[0]].child_level, Some(2));
577 assert!(!actual.contains(&parents[&target]));
578 }
579 "Delete sole cell paragraph" => {
580 let old_cell = parents[&target];
581 let replacement = after.nodes[&old_cell].children[0];
582 assert!(!ids.contains(&replacement));
583 assert_eq!(after.nodes[&old_cell].children.len(), 1);
584 let text = after.nodes[&replacement].content[0];
585 assert!(
586 matches!(&after.nodes[&text].kind,Kind::RichText{text,..} if text.is_empty())
587 );
588 }
589 "Delete cell subtree" => assert!(!actual.contains(&outlines[0])),
590 _ => assert_eq!(after.nodes[&parents[&target]].children.len(), 1),
591 }
592 candidate = ops::apply(&candidate, "Tree author", intent).unwrap().image;
593 count += 1;
594 }
595 assert_eq!(count, 4);
596 if let Some(output) = std::env::var_os("ONESTORE_TREE_OUTPUT") {
597 let output = std::path::PathBuf::from(output).join("cross-container");
598 assert!(output.is_absolute());
599 std::fs::create_dir_all(output.parent().unwrap()).unwrap();
600 std::fs::create_dir(&output).unwrap();
601 std::fs::write(output.join("synthetic.one"), candidate).unwrap();
602 }
603}