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