1use onestore::{
2 CommitState, ExGuid, RevisionIndex, Store,
3 document::{Document, Kind, Revision},
4 op::{Op, PageOp},
5 page::Page,
6};
7use std::{collections::BTreeMap, sync::LazyLock};
8
9use crate::{current, disk, ops};
10
11static SOURCE: LazyLock<Vec<u8>> = LazyLock::new(|| {
12 let source = onestore::create_section("tree.one", "Original", "Author").unwrap();
13 let store = Store::parse(&source).unwrap();
14 let index = RevisionIndex::parse(&store).unwrap();
15 let document = Document::parse(&index).unwrap();
16 let (sid, page) = document.pages().unwrap()[0];
17 let space = &document.spaces[&sid];
18 let view = &space.revisions[&space.contexts[&ExGuid::default()]];
19 let outline = *view.nodes[&page]
20 .children
21 .iter()
22 .find(|id| matches!(view.nodes[id].kind, Kind::Outline { .. }))
23 .unwrap();
24 let (add, other, _) = ops::new_outline(360.0, 72.0, "Other");
25 let mut edits = vec![add];
26 for container in [outline, other] {
27 let mut paragraphs = Vec::new();
28 for text in ["First 🦀 é", "Second 東京", "Third"] {
29 let paragraph = ops::paragraph(text);
30 let mut child = ops::paragraph("Child");
31 child.parent = Some(paragraph.id);
32 child.level = 2;
33 paragraphs.extend([paragraph, child]);
34 }
35 edits.push(PageOp::Insert {
36 container,
37 before: None,
38 paragraphs,
39 });
40 }
41 ops::page_edited(&source, sid, edits).unwrap()
42});
43
44fn forest(view: &Revision<'_>, root: ExGuid) -> BTreeMap<ExGuid, (ExGuid, u32, usize)> {
45 let mut positions = BTreeMap::new();
46 let mut pending = vec![(root, root, 0)];
47 while let Some((id, mut scope, mut level)) = pending.pop() {
48 let node = &view.nodes[&id];
49 if matches!(node.kind, Kind::Outline { .. } | Kind::Cell { .. }) {
50 scope = id;
51 level = 0;
52 }
53 assert!(
54 positions
55 .insert(id, (scope, level, positions.len()))
56 .is_none()
57 );
58 pending.extend(
59 node.children
60 .iter()
61 .rev()
62 .map(|id| (*id, scope, level + u32::from(node.child_level.unwrap_or(1)))),
63 );
64 pending.extend(node.content.iter().rev().map(|id| (*id, scope, level)));
65 }
66 positions
67}
68
69/// Random subtree moves and deletions by twelve clients, each on its own possibly stale
70/// image, committed under injected storage faults: an edit stores the page the model
71/// predicts, and the file always holds a complete old or new graph.
72pub fn run(input: &[u8]) {
73 let Some((&selector, input)) = input.split_first() else {
74 return;
75 };
76 let source = if selector & 1 == 0 {
77 SOURCE.as_slice()
78 } else {
79 include_bytes!("../../../../corpus/outline-edit/tree/before/notebook/synthetic.one")
80 };
81 let mut persisted = source.to_vec();
82 let mut clients = vec![persisted.clone(); 12];
83 for step in input.chunks_exact(10).take(36) {
84 let client = usize::from(step[0]) % clients.len();
85 if step[1] & 1 != 0 {
86 clients[client] = persisted.clone();
87 }
88 let source = &clients[client];
89 let store = Store::parse(source).unwrap();
90 let index = RevisionIndex::parse(&store).unwrap();
91 let document = Document::parse(&index).unwrap();
92 let pages = document.pages().unwrap();
93 let (sid, page) = pages[usize::from(step[2]) % pages.len()];
94 let space = &document.spaces[&sid];
95 let view = &space.revisions[&space.contexts[&ExGuid::default()]];
96 let before = forest(view, page);
97 let mut targets: Vec<_> = before
98 .keys()
99 .copied()
100 .filter(|id| {
101 matches!(
102 view.nodes[id].kind,
103 Kind::Paragraph { .. } | Kind::Outline { .. }
104 )
105 })
106 .collect();
107 targets.sort_by_key(|id| before[id].2);
108 if targets.is_empty() {
109 continue;
110 }
111 let target = targets[usize::from(step[3]) % targets.len()];
112 let subtree = forest(view, target);
113 let outline = matches!(view.nodes[&target].kind, Kind::Outline { .. });
114 let deleting = step[1] & 6 == 0;
115 let (op, cycle) = if deleting {
116 (PageOp::Delete { object: target }, false)
117 } else {
118 let mut destinations: Vec<_> = before
119 .keys()
120 .copied()
121 .filter(|id| {
122 if outline {
123 *id == page
124 } else {
125 matches!(
126 view.nodes[id].kind,
127 Kind::Outline { .. } | Kind::Paragraph { .. } | Kind::Cell { .. }
128 )
129 }
130 })
131 .collect();
132 destinations.sort_by_key(|id| before[id].2);
133 let destination = destinations[usize::from(step[4]) % destinations.len()];
134 // Outline groups are the writers' business: anchors are the paragraphs in them.
135 let mut children = Vec::new();
136 let mut pending: Vec<ExGuid> = view.nodes[&destination]
137 .children
138 .iter()
139 .rev()
140 .copied()
141 .collect();
142 while let Some(id) = pending.pop() {
143 match view.nodes[&id].kind {
144 Kind::OutlineGroup => pending.extend(view.nodes[&id].children.iter().rev()),
145 _ if id == target => {}
146 _ => children.push(id),
147 }
148 }
149 let before = children
150 .get(usize::from(step[5]) % (children.len() + 1))
151 .copied();
152 let op = PageOp::Move {
153 object: target,
154 parent: (!outline).then_some(destination),
155 before,
156 };
157 (op, subtree.contains_key(&destination))
158 };
159 let model = Page::from_space(&document, sid).unwrap();
160 let ops = vec![Op::Page {
161 space: sid,
162 op: op.clone(),
163 }];
164 let Ok(edit) = ops::apply(source, "Tree schedule", ops) else {
165 continue;
166 };
167 assert!(!cycle, "{op:?}");
168 let after_store = Store::parse(edit.as_bytes()).unwrap();
169 let after_index = RevisionIndex::parse(&after_store).unwrap();
170 after_index.validate_current().unwrap();
171 let after_document = Document::parse(&after_index).unwrap();
172 let mut predicted = model.clone();
173 onestore::op::predict(&mut predicted, &op).unwrap();
174 let stored = Page::from_space(&after_document, sid).unwrap();
175 if stored != predicted {
176 let (a, b) = (format!("{stored:?}"), format!("{predicted:?}"));
177 let at = a.bytes().zip(b.bytes()).take_while(|(x, y)| x == y).count();
178 panic!(
179 "{op:?}\n stored …{}\n predicted …{}",
180 &a[a.floor_char_boundary(at.saturating_sub(300))
181 ..a.floor_char_boundary((at + 200).min(a.len()))],
182 &b[b.floor_char_boundary(at.saturating_sub(300))
183 ..b.floor_char_boundary((at + 200).min(b.len()))]
184 );
185 }
186 let space = &after_document.spaces[&sid];
187 let after = &space.revisions[&space.contexts[&ExGuid::default()]];
188 for (id, _) in forest(after, page) {
189 let node = &after.nodes[&id];
190 if before.contains_key(&id) {
191 assert_eq!(node.content, view.nodes[&id].content);
192 assert_eq!(
193 serde_json::to_value(&node.tags).unwrap(),
194 serde_json::to_value(&view.nodes[&id].tags).unwrap()
195 );
196 }
197 if matches!(
198 node.kind,
199 Kind::Outline { .. } | Kind::OutlineGroup | Kind::Cell { .. }
200 ) {
201 assert!(
202 node.children
203 .iter()
204 .any(|id| matches!(after.nodes[id].kind, Kind::Paragraph { .. }))
205 );
206 }
207 }
208 let before = current::current(&persisted);
209 let after = current::current(edit.as_bytes());
210 let mut disk = disk::Disk {
211 visible: persisted.clone(),
212 durable: persisted.clone(),
213 operation: 0,
214 fail_at: (step[6] != 0).then_some(usize::from(u16::from_le_bytes([step[6], step[7]]))),
215 write_limit: if step[8] & 1 == 0 { 17 } else { 4096 },
216 random: u64::from(step[9]) + 1,
217 };
218 let Some(transaction) = &edit.transaction else {
219 continue;
220 };
221 let result = transaction.commit(&mut disk);
222 let actual = current::current(&disk.durable);
223 match result {
224 Ok(()) => assert_eq!(actual, after),
225 Err(error) => {
226 assert!(actual == before || actual == after);
227 match error.state {
228 CommitState::NotCommitted => assert_eq!(actual, before),
229 CommitState::Committed => assert_eq!(actual, after),
230 CommitState::Unknown => {}
231 }
232 }
233 }
234 persisted = disk.durable;
235 }
236}