clover's git

snowbound

1	use onestore::page::text::{EditError, Paragraph, new_id};
2	use onestore::page::{PageParagraph, ParagraphContent, TableCell, TextObject};
3	use onestore::{ExGuid, document::Format};
4	use std::{
5	collections::{BTreeMap, BTreeSet},
6	ops::Range,
7	};
8
9	#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
10	pub struct TextPosition {
11	pub paragraph: usize,
12	pub offset: u32,
13	}
14
15	/// Paragraph positions enumerate text leaves in document order, including table cells.
16	#[derive(Clone, Debug, PartialEq)]
17	pub struct TextDocument {
18	nodes: Vec<PageParagraph>,
19	/// The paragraph position of each root node's first text leaf, then the paragraph count, so
20	/// a position finds its node by search instead of walking every leaf before it.
21	starts: Vec<usize>,
22	/// Root indices of the tables, so a cell is found without walking every node.
23	tables: Vec<usize>,
24	}
25
26	#[derive(Clone, Debug, PartialEq)]
27	pub(crate) struct DocumentEdit {
28	/// Cell identity, or None for the document root.
29	pub(crate) container: Option<ExGuid>,
30	pub(crate) range: Range<usize>,
31	pub(crate) replacement: Vec<PageParagraph>,
32	/// Width patches address surviving tables outside the replacement subtree.
33	pub(crate) columns: BTreeMap<ExGuid, Vec<f32>>,
34	}
35
36	pub(crate) fn node(text: Paragraph, format: Format) -> Result<PageParagraph, EditError> {
37	Ok(PageParagraph {
38	id: new_id()?,
39	parent: None,
40	level: 1,
41	format,
42	content: onestore::page::ParagraphContent::Text(TextObject {
43	date_field: None,
44	id: new_id()?,
45	text,
46	tags: Vec::new(),
47	}),
48	lists: Vec::new(),
49	tags: Vec::new(),
50	media: Default::default(),
51	collapsed: false,
52	style: None,
53	})
54	}
55
56	pub(crate) fn edited_nodes<'a>(
57	nodes: &'a [PageParagraph],
58	container: Option<ExGuid>,
59	edit: Option<&'a DocumentEdit>,
60	) -> impl Clone + Iterator<Item = &'a PageParagraph> {
61	let (range, replacement) = match edit.filter(|edit| edit.container == container) {
62	Some(edit) => (edit.range.clone(), edit.replacement.as_slice()),
63	None => (0..0, &[][..]),
64	};
65	nodes[..range.start]
66	.iter()
67	.chain(replacement)
68	.chain(&nodes[range.end..])
69	}
70
71	pub(crate) fn leaves<'a>(
72	nodes: &'a [PageParagraph],
73	edit: Option<&'a DocumentEdit>,
74	) -> impl Iterator<Item = (Option<ExGuid>, usize, &'a PageParagraph)> {
75	descendants(nodes, edit).filter(|(_, _, node)| node.text().is_some())
76	}
77
78	pub(crate) fn descendants<'a>(
79	nodes: &'a [PageParagraph],
80	edit: Option<&'a DocumentEdit>,
81	) -> impl Iterator<Item = (Option<ExGuid>, usize, &'a PageParagraph)> {
82	let mut current = (None, edited_nodes(nodes, None, edit).enumerate());
83	let mut pending = Vec::new();
84	std::iter::from_fn(move || {
85	loop {
86	let Some((index, node)) = current.1.next() else {
87	current = pending.pop()?;
88	continue;
89	};
90	let container = current.0;
91	if let ParagraphContent::Table(table) = &node.content {
92	pending.push(current.clone());
93	pending.extend(
94	table
95	.rows
96	.iter()
97	.rev()
98	.flat_map(|row| row.cells.iter().rev())
99	.map(|cell| {
100	(
101	Some(cell.id),
102	edited_nodes(&cell.paragraphs, Some(cell.id), edit).enumerate(),
103	)
104	}),
105	);
106	current = pending.pop().unwrap();
107	}
108	return Some((container, index, node));
109	}
110	})
111	}
112
113	pub(crate) fn swap_columns(nodes: &mut [PageParagraph], widths: &mut BTreeMap<ExGuid, Vec<f32>>) {
114	if widths.is_empty() {
115	return;
116	}
117	for node in nodes {
118	if let ParagraphContent::Table(table) = &mut node.content {
119	if let Some(widths) = widths.get_mut(&table.id) {
120	for (column, width) in table.columns.iter_mut().zip(widths) {
121	std::mem::swap(&mut column.width, width);
122	}
123	}
124	for cell in table.rows.iter_mut().flat_map(|row| &mut row.cells) {
125	swap_columns(&mut cell.paragraphs, widths);
126	}
127	}
128	}
129	}
130
131	/// Identities a node holds itself; paragraphs in its cells hold their own.
132	fn owned_ids(node: &PageParagraph) -> impl Iterator<Item = ExGuid> + '_ {
133	let (content, rows) = match &node.content {
134	ParagraphContent::Text(text) => (text.id, &[][..]),
135	ParagraphContent::Image(image) => (image.id, &[][..]),
136	ParagraphContent::Attachment(file) => (file.id, &[][..]),
137	ParagraphContent::Ink(ink) => (ink.id, &[][..]),
138	ParagraphContent::Unsupported(unsupported) => (unsupported.id, &[][..]),
139	ParagraphContent::Table(table) => (table.id, table.rows.as_slice()),
140	};
141	[node.id, content].into_iter().chain(
142	rows.iter()
143	.flat_map(|row| std::iter::once(row.id).chain(row.cells.iter().map(|cell| cell.id))),
144	)
145	}
146
147	pub(crate) fn validate_nodes(
148	nodes: &[PageParagraph],
149	ids: &mut BTreeSet<ExGuid>,
150	) -> Result<(), EditError> {
151	if nodes.is_empty() {
152	return Err(EditError::InvalidRange);
153	}
154	validate_run(nodes, &[], 0, ids)
155	}
156
157	/// Validates `nodes`, which follow `earlier` in a container at `depth`, and every container
158	/// nested in them; `earlier` is searched only for parents the run lacks.
159	fn validate_run(
160	nodes: &[PageParagraph],
161	earlier: &[PageParagraph],
162	depth: usize,
163	ids: &mut BTreeSet<ExGuid>,
164	) -> Result<(), EditError> {
165	let mut pending = vec![(nodes, earlier, depth)];
166	while let Some((nodes, earlier, depth)) = pending.pop() {
167	if depth > 64 {
168	return Err(EditError::InvalidStructure);
169	}
170	let mut parents = BTreeMap::new();
171	for node in nodes {
172	let parent = |id| {
173	parents.get(&id).copied().or_else(|| {
174	earlier
175	.iter()
176	.rev()
177	.find(|node| node.id == id)
178	.map(|node| node.level)
179	})
180	};
181	if owned_ids(node).any(|id| !ids.insert(id))
182	|| node.level == 0
183	|| node
184	.parent
185	.is_some_and(|id| parent(id).is_none_or(|level| level >= node.level))
186	{
187	return Err(EditError::InvalidStructure);
188	}
189	parents.insert(node.id, node.level);
190	match &node.content {
191	ParagraphContent::Image(image) => {
192	crate::outline::image_size(image).ok_or(EditError::UnsupportedContent)?;
193	}
194	ParagraphContent::Table(table) => {
195	if table.rows.is_empty()
196	|| table.columns.is_empty()
197	|| table.columns.len() > 255
198	|| table
199	.columns
200	.iter()
201	.any(|column| !column.width.is_finite() || column.width < 36.0)
202	|| table
203	.rows
204	.iter()
205	.any(|row| row.cells.len() != table.columns.len())
206	{
207	return Err(EditError::InvalidStructure);
208	}
209	for cell in table.rows.iter().flat_map(|row| &row.cells) {
210	if !cell.unsupported.is_empty() {
211	return Err(EditError::UnsupportedContent);
212	}
213	if cell.paragraphs.is_empty() {
214	return Err(EditError::InvalidRange);
215	}
216	pending.push((cell.paragraphs.as_slice(), &[][..], depth + 1));
217	}
218	}
219	ParagraphContent::Text(_)
220	| ParagraphContent::Attachment(_)
221	| ParagraphContent::Ink(_)
222	| ParagraphContent::Unsupported(_) => {}
223	}
224	}
225	}
226	Ok(())
227	}
228
229	fn validate_text(nodes: &[PageParagraph]) -> Result<(), EditError> {
230	for (_, _, node) in leaves(nodes, None) {
231	let text = &node.text().unwrap().text;
232	text.utf16_offset(text.text().len())?;
233	}
234	Ok(())
235	}
236
237	/// Whether UTF-16 `offset` lies inside a hyperlink field, which OneNote has not been seen
238	/// splitting between paragraphs.
239	fn divides_link(text: &Paragraph, offset: u32) -> Result<bool, EditError> {
240	let at = text.byte_offset(offset)?;
241	let link = |byte: usize| {
242	text.spans()
243	.iter()
244	.find(|span| byte < span.end)
245	.is_some_and(|span| span.format.hyperlink == Some(true))
246	};
247	Ok(at > 0 && link(at - 1) && link(at) && !text.text()[at..].starts_with('\u{fddf}'))
248	}
249
250	/// What deleting `range`, which crosses a table's edge, leaves of `nodes`, whose
251	/// first text leaf is paragraph `*next`, and whether all of them lay inside it. As OneNote 2010
252	/// deletes such a selection, each container keeps what lies outside it and nothing joins
253	/// across a container's edge: the end paragraphs keep their outer text, a cell inside keeps
254	/// one empty paragraph, except that where the selection runs on past a table its rows with
255	/// every cell inside go, and the table when all of them do. A paragraph that goes leaves its
256	/// children to its parent.
257	fn cut(
258	nodes: &[PageParagraph],
259	next: &mut usize,
260	range: &Range<TextPosition>,
261	) -> Result<(Vec<PageParagraph>, bool), EditError> {
262	let (start, end) = (range.start, range.end);
263	let mut kept = Vec::new();
264	let mut gone = BTreeMap::new();
265	for node in nodes {
266	let inside = match &node.content {
267	ParagraphContent::Text(text) => {
268	let at = *next;
269	*next += 1;
270	let text = &text.text;
271	let length = text.utf16_offset(text.text().len())?;
272	let shown = match at {
273	at if at == start.paragraph => Some(text.slice(0..start.offset)?),
274	at if at == end.paragraph => Some(text.slice(end.offset..length)?),
275	_ => None,
276	};
277	if let Some(shown) = shown {
278	let mut node = node.clone();
279	node.text_mut().unwrap().text = shown;
280	kept.push(node);
281	continue;
282	}
283	start.paragraph < at && at < end.paragraph
284	}
285	ParagraphContent::Table(table) => {
286	let mut table = table.clone();
287	let mut whole_rows = Vec::new();
288	for row in &mut table.rows {
289	let mut cells = Vec::new();
290	for cell in &row.cells {
291	let (paragraphs, inside) = cut(&cell.paragraphs, next, range)?;
292	cells.push((cell, paragraphs, inside));
293	}
294	let whole = cells.iter().all(|(_, _, inside)| *inside);
295	row.cells = cells
296	.into_iter()
297	.map(|(cell, paragraphs, inside)| {
298	let paragraphs = if inside {
299	let (_, _, leaf) = leaves(&cell.paragraphs, None)
300	.next()
301	.ok_or(EditError::InvalidStructure)?;
302	let mut leaf = leaf.clone();
303	let text = &mut leaf.text_mut().unwrap().text;
304	*text = text.slice(0..0)?;
305	leaf.parent = None;
306	leaf.level = 1;
307	vec![leaf]
308	} else {
309	paragraphs
310	};
311	Ok(TableCell {
312	paragraphs,
313	..cell.clone()
314	})
315	})
316	.collect::<Result<_, EditError>>()?;
317	whole_rows.push(whole);
318	}
319	// Rows go only where the selection runs on past the table.
320	if end.paragraph >= *next {
321	let mut whole = whole_rows.into_iter();
322	table.rows.retain(|_| !whole.next().unwrap_or(false));
323	}
324	if table.rows.is_empty() {
325	true
326	} else {
327	let mut node = node.clone();
328	node.content = ParagraphContent::Table(table);
329	kept.push(node);
330	continue;
331	}
332	}
333	_ => start.paragraph < *next && *next <= end.paragraph,
334	};
335	if inside {
336	gone.insert(node.id, node.parent);
337	} else {
338	kept.push(node.clone());
339	}
340	}
341	let whole = kept.is_empty();
342	for node in &mut kept {
343	while let Some(parent) = node.parent.and_then(|parent| gone.get(&parent)) {
344	node.parent = *parent;
345	}
346	}
347	Ok((kept, whole))
348	}
349
350	/// Whether a split or join keeping `first` up to UTF-16 `start` and `last` from `end` on meets
351	/// an embedded object at the seam or carries one to another paragraph, or joins inside an
352	/// equation's objects: the object's run data belongs to its paragraph, and an equation divides
353	/// only at its edges (Enter inside one breaks its line instead, `CanvasEditor::enter`).
354	fn moves_object(
355	first: &Paragraph,
356	start: u32,
357	last: &Paragraph,
358	end: u32,
359	) -> Result<bool, EditError> {
360	let math = |text: &Paragraph, offset: u32| {
361	text.format_at(offset)
362	.is_ok_and(|format| format.math == Some(true))
363	};
364	let (before, after) = (first.byte_offset(start)?, last.byte_offset(end)?);
365	let following = last.text()[after..]
366	.chars()
367	.next()
368	.map(|c| end + c.len_utf16() as u32);
369	// An equation joins where both seams lie outside its objects (fractions, scripts and the
370	// like), as OneNote 2010 joins two equations a deletion meets.
371	let nested = |text: &str| {
372	text.chars().fold(0_i32, |depth, c| match c {
373	'\u{fdd0}' => depth + 1,
374	'\u{fdef}' => depth - 1,
375	_ => depth,
376	}) > 0
377	};
378	Ok(first.text()[..before].ends_with('\u{fffc}')
379	|| last.text()[after..].contains('\u{fffc}')
380	|| start > 0
381	&& math(first, start)
382	&& following.is_some_and(|next| math(last, next))
383	&& (nested(&first.text()[..before]) || nested(&last.text()[..after])))
384	}
385
386	/// Paragraph positions of each node's first text leaf, counting from `first`.
387	fn starts(nodes: &[PageParagraph], first: usize) -> impl Iterator<Item = usize> + '_ {
388	nodes.iter().scan(first, |next, node| {
389	let start = *next;
390	*next += leaves(std::slice::from_ref(node), None).count();
391	Some(start)
392	})
393	}
394
395	fn enclosing(
396	nodes: &[PageParagraph],
397	first: usize,
398	paragraph: usize,
399	ranges: &mut Vec<Range<usize>>,
400	) {
401	let count = |nodes: &[PageParagraph]| leaves(nodes, None).count();
402	let Some((index, start)) = starts(nodes, first)
403	.enumerate()
404	.take_while(|(_, start)| *start <= paragraph)
405	.last()
406	else {
407	return;
408	};
409	let ParagraphContent::Table(table) = &nodes[index].content else {
410	let end = subtree_end(nodes, index);
411	if end > index + 1 {
412	ranges.push(start..start + count(&nodes[index..end]));
413	}
414	return;
415	};
416	let mut cell_start = start;
417	for row in &table.rows {
418	let row_start = cell_start;
419	let mut holder = None;
420	for cell in &row.cells {
421	let cell_end = cell_start + count(&cell.paragraphs);
422	if (cell_start..cell_end).contains(&paragraph) {
423	holder = Some((cell, cell_start..cell_end));
424	}
425	cell_start = cell_end;
426	}
427	if let Some((cell, range)) = holder {
428	enclosing(&cell.paragraphs, range.start, paragraph, ranges);
429	ranges.extend([
430	range,
431	row_start..cell_start,
432	start..start + count(&nodes[index..=index]),
433	]);
434	return;
435	}
436	}
437	}
438
439	/// The index after `nodes[index]`'s last descendant. Descendants follow their ancestor
440	/// contiguously; a paragraph only an outline group indents has no parent to descend from.
441	pub(crate) fn subtree_end(nodes: &[PageParagraph], index: usize) -> usize {
442	let mut members = BTreeSet::from([nodes[index].id]);
443	index
444	+ 1
445	+ nodes[index + 1..]
446	.iter()
447	.take_while(|node| {
448	node.parent.is_some_and(|parent| members.contains(&parent))
449	&& members.insert(node.id)
450	})
451	.count()
452	}
453
454	/// The nodes from `from` on that descend from a paragraph in `moves` or `shifts`, rebuilt so
455	/// the children of each paragraph in `moves` belong to its new parent, one level below it, and
456	/// every subtree keeps its depth below its root; ends at the last node that changes.
457	fn adopt(
458	nodes: &[PageParagraph],
459	from: usize,
460	moves: &BTreeMap<ExGuid, &PageParagraph>,
461	mut shifts: BTreeMap<ExGuid, i64>,
462	) -> Result<Vec<PageParagraph>, EditError> {
463	let mut adopted = Vec::new();
464	let mut changed = 0;
465	for node in &nodes[from..] {
466	let Some(parent) = node.parent else { break };
467	let mut node = node.clone();
468	let shift = match (moves.get(&parent), shifts.get(&parent)) {
469	(Some(holder), _) => {
470	node.parent = Some(holder.id);
471	i64::from(holder.level) + 1 - i64::from(node.level)
472	}
473	(None, Some(shift)) => *shift,
474	(None, None) => break,
475	};
476	node.level = u32::try_from(i64::from(node.level) + shift)
477	.map_err(|_| EditError::InvalidStructure)?;
478	shifts.insert(node.id, shift);
479	if shift != 0 || moves.contains_key(&parent) {
480	changed = adopted.len() + 1;
481	}
482	adopted.push(node);
483	}
484	adopted.truncate(changed);
485	Ok(adopted)
486	}
487
488	/// The sibling `nodes[index]` follows, passing over `skipped` siblings, when everything
489	/// between them descends from it or from a skipped paragraph.
490	pub(crate) fn previous_sibling(
491	nodes: &[PageParagraph],
492	index: usize,
493	skipped: &BTreeSet<ExGuid>,
494	) -> Option<usize> {
495	let node = &nodes[index];
496	let sibling = (0..index).rev().find(|&at| {
497	nodes[at].level <= node.level
498	&& !(nodes[at].level == node.level && skipped.contains(&nodes[at].id))
499	})?;
500	if nodes[sibling].level != node.level || nodes[sibling].parent != node.parent {
501	return None;
502	}
503	let mut members = BTreeSet::from([nodes[sibling].id]);
504	nodes[sibling + 1..index]
505	.iter()
506	.all(|node| {
507	let inside = skipped.contains(&node.id)
508	|| node.parent.is_some_and(|parent| members.contains(&parent));
509	members.insert(node.id);
510	inside
511	})
512	.then_some(sibling)
513	}
514
515	/// Tab or Shift+Tab on `range` of `nodes` as OneNote does, moving each paragraph with its
516	/// subtree: indenting makes a paragraph the last child of its previous sibling, or without one
517	/// indents it within its group; outdenting a child makes it its parent's sibling, adopting the
518	/// siblings after it. None when nothing moves.
519	pub(crate) fn indent(
520	nodes: &[PageParagraph],
521	container: Option<ExGuid>,
522	range: Range<usize>,
523	outdent: bool,
524	) -> Option<DocumentEdit> {
525	let selected = nodes[range.clone()]
526	.iter()
527	.map(|node| node.id)
528	.collect::<BTreeSet<_>>();
529	let mut end = range.end;
530	let mut tops = BTreeMap::new();
531	let mut adopters = BTreeMap::new();
532	for index in range.clone() {
533	let node = &nodes[index];
534	if node.parent.is_some_and(|parent| selected.contains(&parent)) {
535	continue;
536	}
537	end = end.max(subtree_end(nodes, index));
538	if !outdent {
539	let parent = previous_sibling(nodes, index, &selected).map(|at| nodes[at].id);
540	tops.insert(node.id, (parent.or(node.parent), 1));
541	} else if node.level > 1 {
542	let parent = node
543	.parent
544	.and_then(|id| nodes[..index].iter().rposition(|node| node.id == id))
545	.filter(|&at| nodes[at].level + 1 == node.level);
546	let parent = match parent {
547	Some(at) => {
548	end = end.max(subtree_end(nodes, at));
549	adopters.insert(nodes[at].id, node.id);
550	nodes[at].parent
551	}
552	None => node.parent,
553	};
554	tops.insert(node.id, (parent, -1));
555	}
556	}
557	if tops.is_empty() {
558	return None;
559	}
560	let mut shifts = BTreeMap::new();
561	let replacement = nodes[range.start..end]
562	.iter()
563	.map(|node| {
564	let mut node = node.clone();
565	let shift = match (tops.get(&node.id), node.parent) {
566	(Some(&(parent, shift)), _) => {
567	node.parent = parent;
568	shift
569	}
570	(None, Some(parent))
571	if !selected.contains(&node.id) && adopters.contains_key(&parent) =>
572	{
573	node.parent = Some(adopters[&parent]);
574	0
575	}
576	(None, parent) => parent
577	.and_then(|parent| shifts.get(&parent).copied())
578	.unwrap_or(0),
579	};
580	node.level = node.level.saturating_add_signed(shift);
581	shifts.insert(node.id, shift);
582	node
583	})
584	.collect();
585	Some(DocumentEdit {
586	columns: BTreeMap::new(),
587	container,
588	range: range.start..end,
589	replacement,
590	})
591	}
592
593	pub(crate) fn container_mut(
594	nodes: &mut Vec<PageParagraph>,
595	id: Option<ExGuid>,
596	) -> Option<&mut Vec<PageParagraph>> {
597	match id {
598	None => Some(nodes),
599	Some(id) => cell_mut(nodes, id),
600	}
601	}
602
603	fn cell_mut(nodes: &mut [PageParagraph], id: ExGuid) -> Option<&mut Vec<PageParagraph>> {
604	for node in nodes {
605	if let ParagraphContent::Table(table) = &mut node.content {
606	for cell in table.rows.iter_mut().flat_map(|row| &mut row.cells) {
607	if cell.id == id {
608	return Some(&mut cell.paragraphs);
609	}
610	if let Some(nodes) = cell_mut(&mut cell.paragraphs, id) {
611	return Some(nodes);
612	}
613	}
614	}
615	}
616	None
617	}
618
619	fn tables(nodes: &[PageParagraph], first: usize) -> impl Iterator<Item = usize> + '_ {
620	nodes
621	.iter()
622	.enumerate()
623	.filter(|(_, node)| matches!(node.content, ParagraphContent::Table(_)))
624	.map(move |(index, _)| first + index)
625	}
626
627	impl TextDocument {
628	pub fn new(paragraphs: Vec<Paragraph>) -> Result<Self, EditError> {
629	Self::from_nodes(
630	paragraphs
631	.into_iter()
632	.map(|text| node(text, Format::default()))
633	.collect::<Result<_, _>>()?,
634	)
635	}
636
637	pub fn from_nodes(nodes: Vec<PageParagraph>) -> Result<Self, EditError> {
638	validate_nodes(&nodes, &mut BTreeSet::new())?;
639	validate_text(&nodes)?;
640	let mut starts = starts(&nodes, 0).collect::<Vec<_>>();
641	starts.push(leaves(&nodes, None).count());
642	Ok(Self {
643	tables: tables(&nodes, 0).collect(),
644	nodes,
645	starts,
646	})
647	}
648
649	pub fn nodes(&self) -> &[PageParagraph] {
650	&self.nodes
651	}
652
653	pub fn text_nodes(&self) -> impl Iterator<Item = &PageParagraph> {
654	leaves(&self.nodes, None).map(|(_, _, node)| node)
655	}
656
657	pub fn paragraphs(&self) -> impl Iterator<Item = &Paragraph> {
658	self.text_nodes().map(|node| &node.text().unwrap().text)
659	}
660
661	/// The text leaf at a paragraph position, with its container and index there.
662	pub(crate) fn leaf(&self, paragraph: usize) -> Option<(Option<ExGuid>, usize, &PageParagraph)> {
663	let root = self
664	.starts
665	.partition_point(|start| *start <= paragraph)
666	.checked_sub(1)?;
667	let node = self.nodes.get(root)?;
668	match node.text() {
669	Some(_) => Some((None, root, node)),
670	None => leaves(std::slice::from_ref(node), None).nth(paragraph - self.starts[root]),
671	}
672	}
673
674	/// The text leaf at a paragraph position once a valid `edit` applies, with the position it
675	/// has now unless the edit supplies it.
676	pub(crate) fn edited_leaf<'a>(
677	&'a self,
678	edit: &'a DocumentEdit,
679	paragraph: usize,
680	) -> Option<(&'a PageParagraph, Option<usize>)> {
681	let nodes = self.container(edit.container).ok()?;
682	let first = match edit.container {
683	None => self.starts[edit.range.start],
684	Some(cell) => {
685	let root = self.root(cell).ok()?;
686	self.starts[root]
687	+ descendants(std::slice::from_ref(&self.nodes[root]), None)
688	.take_while(|(container, _, _)| *container != edit.container)
689	.filter(|(_, _, node)| node.text().is_some())
690	.count()
691	+ leaves(&nodes[..edit.range.start], None).count()
692	}
693	};
694	let added = leaves(&edit.replacement, None).count();
695	match paragraph.checked_sub(first) {
696	Some(offset) if offset < added => leaves(&edit.replacement, None)
697	.nth(offset)
698	.map(|(_, _, node)| (node, None)),
699	Some(_) => {
700	let before = paragraph - added + leaves(&nodes[edit.range.clone()], None).count();
701	self.leaf(before).map(|(_, _, node)| (node, Some(before)))
702	}
703	None => self
704	.leaf(paragraph)
705	.map(|(_, _, node)| (node, Some(paragraph))),
706	}
707	}
708
709	/// Text leaf ranges holding `paragraph`, innermost first: its subtree when it has
710	/// descendants, then the cell, row and table of each table around it.
711	pub(crate) fn enclosing(&self, paragraph: usize) -> Vec<Range<usize>> {
712	let mut ranges = Vec::new();
713	enclosing(&self.nodes, 0, paragraph, &mut ranges);
714	ranges
715	}
716
717	/// The root node holding a table cell.
718	pub(crate) fn root(&self, cell: ExGuid) -> Result<usize, EditError> {
719	self.tables
720	.iter()
721	.copied()
722	.find(|&root| {
723	descendants(std::slice::from_ref(&self.nodes[root]), None)
724	.any(|(container, _, _)| container == Some(cell))
725	})
726	.ok_or(EditError::InvalidRange)
727	}
728
729	pub(crate) fn paragraph(&self, index: usize) -> Option<&Paragraph> {
730	self.leaf(index)
731	.map(|(_, _, node)| &node.text().unwrap().text)
732	}
733
734	pub(crate) fn container(&self, id: Option<ExGuid>) -> Result<&[PageParagraph], EditError> {
735	self.nested_container(id).map(|(nodes, _)| nodes)
736	}
737
738	/// The container's paragraphs and how many tables enclose them.
739	fn nested_container(&self, id: Option<ExGuid>) -> Result<(&[PageParagraph], usize), EditError> {
740	let Some(id) = id else {
741	return Ok((&self.nodes, 0));
742	};
743	let root = self.root(id)?;
744	let mut pending = vec![(std::slice::from_ref(&self.nodes[root]), 0)];
745	while let Some((nodes, depth)) = pending.pop() {
746	for node in nodes {
747	if let ParagraphContent::Table(table) = &node.content {
748	for cell in table.rows.iter().flat_map(|row| &row.cells) {
749	if cell.id == id {
750	return Ok((&cell.paragraphs, depth + 1));
751	}
752	pending.push((&cell.paragraphs, depth + 1));
753	}
754	}
755	}
756	}
757	Err(EditError::InvalidRange)
758	}
759
760	/// The nodes `range` covers, its end paragraphs cut to it: those of its container from
761	/// one end to the other, or where it crosses a table's edge, the root nodes holding them.
762	pub(crate) fn selected(
763	&self,
764	range: Range<TextPosition>,
765	) -> Result<Vec<PageParagraph>, EditError> {
766	let (start_container, start, first) = self
767	.leaf(range.start.paragraph)
768	.ok_or(EditError::InvalidRange)?;
769	let (end_container, end, last) = self
770	.leaf(range.end.paragraph)
771	.ok_or(EditError::InvalidRange)?;
772	let (first, last) = (first.id, last.id);
773	let (nodes, start, end) = if self.crosses_table(range.clone())? {
774	let root = |container: Option<ExGuid>, index| match container {
775	Some(cell) => self.root(cell),
776	None => Ok(index),
777	};
778	(
779	&self.nodes[..],
780	root(start_container, start)?,
781	root(end_container, end)?,
782	)
783	} else {
784	(self.container(start_container)?, start, end)
785	};
786	let mut nodes = nodes[start..=end].to_vec();
787	let tail = nodes.len() - 1;
788	if nodes[tail].id == last {
789	let from = if first == last { range.start.offset } else { 0 };
790	let text = &mut nodes[tail].text_mut().unwrap().text;
791	*text = text.slice(from..range.end.offset)?;
792	}
793	if nodes[0].id == first && first != last {
794	let text = &mut nodes[0].text_mut().unwrap().text;
795	let length = text.utf16_offset(text.text().len())?;
796	*text = text.slice(range.start.offset..length)?;
797	}
798	Ok(nodes)
799	}
800
801	/// Replaces `range` as OneNote's typing, Enter and deletion do: the first paragraph keeps
802	/// its identity and properties, and a paragraph the replacement adds takes its level,
803	/// parent, style and lists but no note tags, except that a range's last paragraph stays
804	/// itself when the replacement ends in one. The last paragraph holds the children of the
805	/// paragraphs the edit removes or splits.
806	pub(crate) fn replace(
807	&self,
808	range: Range<TextPosition>,
809	replacement: Vec<Paragraph>,
810	) -> Result<DocumentEdit, EditError> {
811	if range.start > range.end {
812	return Err(EditError::InvalidRange);
813	}
814	if self.crosses_table(range.clone())? {
815	return self.replace_across(range, replacement);
816	}
817	let (container, start, first) = self
818	.leaf(range.start.paragraph)
819	.ok_or(EditError::InvalidRange)?;
820	let (_, end, last) = self
821	.leaf(range.end.paragraph)
822	.ok_or(EditError::InvalidRange)?;
823	let nodes = self.container(container)?;
824	let first_text = &first.text().unwrap().text;
825	let last_text = &last.text().unwrap().text;
826	let split = replacement.len() > 1;
827	if (split || start != end)
828	&& (moves_object(first_text, range.start.offset, last_text, range.end.offset)?
829	|| split
830	&& (divides_link(first_text, range.start.offset)?
831	|| divides_link(last_text, range.end.offset)?))
832	{
833	return Err(EditError::UnsupportedContent);
834	}
835	let mut prefix = first_text.slice(0..range.start.offset)?;
836	let suffix =
837	last_text.slice(range.end.offset..last_text.utf16_offset(last_text.text().len())?)?;
838	let mut replacement = replacement.into_iter();
839	prefix.append(replacement.next().ok_or(EditError::InvalidRange)?)?;
840	let mut head = first.clone();
841	head.text_mut().unwrap().text = prefix;
842	let following = replacement.len();
843	let keeps_last = start != end && following > 0;
844	let mut added = Vec::new();
845	for (index, text) in replacement.enumerate() {
846	let mut next = if keeps_last && index + 1 == following {
847	let mut end = last.clone();
848	end.text_mut().unwrap().text = text;
849	end
850	} else {
851	let mut next = node(text, first.format.clone())?;
852	next.style = first.style;
853	next.lists.clone_from(&first.lists);
854	next
855	};
856	next.parent = first.parent;
857	next.level = first.level;
858	added.push(next);
859	}
860	if let Some(tail) = added.last_mut() {
861	tail.collapsed |= std::mem::take(&mut head.collapsed);
862	}
863	let tail = added.last_mut().unwrap_or(&mut head);
864	if !suffix.text().is_empty() {
865	tail.text_mut().unwrap().text.append(suffix)?;
866	}
867	let tail = added.last().unwrap_or(&head);
868	let mut moves = nodes[start + 1..end + usize::from(!keeps_last)]
869	.iter()
870	.map(|node| (node.id, tail))
871	.collect::<BTreeMap<_, _>>();
872	if tail.id != head.id {
873	moves.insert(head.id, tail);
874	}
875	let shifts = keeps_last
876	.then(|| (last.id, i64::from(first.level) - i64::from(last.level)))
877	.into_iter()
878	.collect();
879	let adopted = adopt(nodes, end + 1, &moves, shifts)?;
880	Ok(DocumentEdit {
881	columns: BTreeMap::new(),
882	container,
883	range: start..end + 1 + adopted.len(),
884	replacement: [head].into_iter().chain(added).chain(adopted).collect(),
885	})
886	}
887
888	/// Whether `range` crosses a table's edge: its ends lie in different containers, or a table
889	/// lies between them.
890	pub(crate) fn crosses_table(&self, range: Range<TextPosition>) -> Result<bool, EditError> {
891	let (container, start, _) = self
892	.leaf(range.start.paragraph)
893	.ok_or(EditError::InvalidRange)?;
894	let (end_container, end, _) = self
895	.leaf(range.end.paragraph)
896	.ok_or(EditError::InvalidRange)?;
897	Ok(container != end_container
898	|| self.container(container)?[start..end]
899	.iter()
900	.any(|node| matches!(node.content, ParagraphContent::Table(_))))
901	}
902
903	/// `replace` of a range crossing a table's edge, as OneNote 2010 deletes such a selection
904	/// before inserting at its start: see [`cut`].
905	fn replace_across(
906	&self,
907	range: Range<TextPosition>,
908	replacement: Vec<Paragraph>,
909	) -> Result<DocumentEdit, EditError> {
910	// A caret never stands inside hidden text, such as a link's field code.
911	for end in [range.start, range.end] {
912	let text = self
913	.paragraph(end.paragraph)
914	.ok_or(EditError::InvalidRange)?;
915	let at = text.byte_offset(end.offset)?;
916	let hidden = |byte: usize| {
917	text.spans()
918	.iter()
919	.find(|span| byte < span.end)
920	.is_some_and(|span| span.format.hidden == Some(true))
921	};
922	if at > 0 && hidden(at - 1) && hidden(at) {
923	return Err(EditError::InvalidRange);
924	}
925	}
926	let root = |paragraph: usize| self.starts.partition_point(|start| *start <= paragraph) - 1;
927	let (first, last) = (root(range.start.paragraph), root(range.end.paragraph));
928	let (kept, _) = cut(
929	&self.nodes[first..=last],
930	&mut self.starts[first].clone(),
931	&range,
932	)?;
933	let mut nodes = self.nodes[..first].to_vec();
934	nodes.extend(kept);
935	nodes.extend_from_slice(&self.nodes[last + 1..]);
936	let mut cut = Self::from_nodes(nodes)?;
937	let insertion = cut.replace(range.start..range.start, replacement)?;
938	cut.apply(insertion)?;
939	let end = cut.nodes.len() + last + 1 - self.nodes.len();
940	Ok(DocumentEdit {
941	columns: BTreeMap::new(),
942	container: None,
943	range: first..last + 1,
944	replacement: cut.nodes.drain(first..end).collect(),
945	})
946	}
947
948	/// Appends text leaf `lower`'s text to `upper`'s, keeping the upper paragraph's properties
949	/// and giving it the lower one's children; None unless nothing but `upper`'s hidden subtree
950	/// lies between them in one container. The lower text keeps its look under `base`, the
951	/// upper paragraph's style: as OneNote stores it, a flag it leaves unset becomes false and
952	/// an unset colour automatic where the style sets them. An emptied upper paragraph takes
953	/// the lower text whole.
954	pub(crate) fn join(
955	&self,
956	upper: usize,
957	lower: usize,
958	base: &Format,
959	) -> Result<Option<DocumentEdit>, EditError> {
960	let (container, first, top) = self.leaf(upper).ok_or(EditError::InvalidRange)?;
961	let (end_container, last, bottom) = self.leaf(lower).ok_or(EditError::InvalidRange)?;
962	let nodes = self.container(container)?;
963	let (above, below) = (&top.text().unwrap().text, &bottom.text().unwrap().text);
964	if container != end_container
965	|| last <= first
966	|| last > first + 1 && !(top.collapsed && subtree_end(nodes, first) == last)
967	|| moves_object(above, above.utf16_offset(above.text().len())?, below, 0)?
968	{
969	return Ok(None);
970	}
971	let mut head = top.clone();
972	let text = head.text_mut().unwrap();
973	if above.text().is_empty() {
974	// OneNote moves the lower text object, with its style and any recording link, into
975	// an emptied upper paragraph, which keeps its own note tags.
976	let tags = std::mem::take(&mut text.tags);
977	*text = bottom.text().unwrap().clone();
978	text.tags = tags;
979	head.style = bottom.style;
980	head.media.clone_from(&bottom.media);
981	} else {
982	let automatic = |color: Option<u32>| color.map(|_| 0xff000000);
983	let reset = Format {
984	bold: base.bold.map(|_| false),
985	italic: base.italic.map(|_| false),
986	underline: base.underline.map(|_| false),
987	strike: base.strike.map(|_| false),
988	superscript: base.superscript.map(|_| false),
989	subscript: base.subscript.map(|_| false),
990	hidden: base.hidden.map(|_| false),
991	hyperlink: base.hyperlink.map(|_| false),
992	math: base.math.map(|_| false),
993	color: automatic(base.color),
994	highlight: automatic(base.highlight),
995	..Format::default()
996	};
997	// The joined text lies in the upper paragraph, whose spacing and alignment it takes.
998	let paragraph = &above.spans()[0].format;
999	let mut start = 0;
1000	text.text
1001	.append(Paragraph::from_runs(below.spans().iter().map(|span| {
1002	let run = below.text()[start..span.end].to_owned();
1003	start = span.end;
1004	let format = Format {
1005	alignment: paragraph.alignment,
1006	space_before: paragraph.space_before,
1007	space_after: paragraph.space_after,
1008	line_spacing: paragraph.line_spacing,
1009	list_spacing: paragraph.list_spacing,
1010	..span.format.inherit(&reset)
1011	};
1012	(run, format)
1013	})))?;
1014	}
1015	let moves = BTreeMap::from([(bottom.id, &head)]);
1016	let adopted = adopt(nodes, last + 1, &moves, BTreeMap::new())?;
1017	Ok(Some(DocumentEdit {
1018	columns: BTreeMap::new(),
1019	container,
1020	range: first..last + 1 + adopted.len(),
1021	replacement: [head]
1022	.into_iter()
1023	.chain(nodes[first + 1..last].iter().cloned())
1024	.chain(adopted)
1025	.collect(),
1026	}))
1027	}
1028
1029	/// Rejects exactly the edits after which [`validate_nodes`] would reject the document, or
1030	/// whose column widths or text are invalid, looking only where the edit can conflict.
1031	pub(crate) fn validate_edit(&self, edit: &DocumentEdit) -> Result<(), EditError> {
1032	let (nodes, depth) = self.nested_container(edit.container)?;
1033	if edit.range.start > edit.range.end
1034	|| edit.range.end > nodes.len()
1035	|| nodes.len() - edit.range.len() + edit.replacement.len() == 0
1036	{
1037	return Err(EditError::InvalidRange);
1038	}
1039	let mut ids = BTreeSet::new();
1040	validate_run(
1041	&edit.replacement,
1042	&nodes[..edit.range.start],
1043	depth,
1044	&mut ids,
1045	)?;
1046	let removed = &nodes[edit.range.clone()];
1047	let levels = edit
1048	.replacement
1049	.iter()
1050	.map(|node| (node.id, node.level))
1051	.collect::<BTreeMap<_, _>>();
1052	// A later paragraph may name a removed or deepened paragraph as its parent.
1053	let moved = removed
1054	.iter()
1055	.filter_map(|node| {
1056	let level = levels.get(&node.id).copied();
1057	level
1058	.is_none_or(|level| level > node.level)
1059	.then_some((node.id, level))
1060	})
1061	.collect::<BTreeMap<_, _>>();
1062	if !moved.is_empty()
1063	&& nodes[edit.range.end..].iter().any(|node| {
1064	node.parent
1065	.and_then(|id| moved.get(&id))
1066	.is_some_and(|level| level.is_none_or(|level| level >= node.level))
1067	})
1068	{
1069	return Err(EditError::InvalidStructure);
1070	}
1071	// Only identities the removed nodes did not hold can collide elsewhere.
1072	for (_, _, node) in descendants(removed, None) {
1073	for id in owned_ids(node) {
1074	ids.remove(&id);
1075	}
1076	}
1077	if !ids.is_empty()
1078	&& descendants(&self.nodes, None)
1079	.any(|(_, _, node)| owned_ids(node).any(|id| ids.contains(&id)))
1080	{
1081	return Err(EditError::InvalidStructure);
1082	}
1083	if !edit.columns.is_empty() {
1084	let replaced = descendants(&edit.replacement, None)
1085	.filter_map(|(_, _, node)| match &node.content {
1086	ParagraphContent::Table(table) => Some(table.id),
1087	_ => None,
1088	})
1089	.collect::<BTreeSet<_>>();
1090	let tables = descendants(&self.nodes, Some(edit))
1091	.filter_map(|(_, _, node)| match &node.content {
1092	ParagraphContent::Table(table) => Some((table.id, table)),
1093	_ => None,
1094	})
1095	.collect::<BTreeMap<_, _>>();
1096	for (id, widths) in &edit.columns {
1097	if replaced.contains(id)
1098	|| tables
1099	.get(id)
1100	.is_none_or(|table| table.columns.len() != widths.len())
1101	|| widths
1102	.iter()
1103	.any(|width| !width.is_finite() || *width < 36.0)
1104	{
1105	return Err(EditError::InvalidStructure);
1106	}
1107	}
1108	}
1109	validate_text(&edit.replacement)
1110	}
1111
1112	pub(crate) fn apply(&mut self, edit: DocumentEdit) -> Result<DocumentEdit, EditError> {
1113	self.validate_edit(&edit)?;
1114	Ok(self.splice(edit))
1115	}
1116
1117	/// Applies an edit [`Self::validate_edit`] accepted, returning its inverse.
1118	pub(crate) fn splice(&mut self, edit: DocumentEdit) -> DocumentEdit {
1119	let range = edit.range.start..edit.range.start + edit.replacement.len();
1120	let root = edit.container.map(|cell| {
1121	(
1122	cell,
1123	self.root(cell).expect("a validated edit's cell exists"),
1124	)
1125	});
1126	let nodes = match root {
1127	Some((cell, root)) => cell_mut(std::slice::from_mut(&mut self.nodes[root]), cell)
1128	.expect("a validated edit's cell exists"),
1129	None => &mut self.nodes,
1130	};
1131	let replacement: Vec<_> = nodes.splice(edit.range.clone(), edit.replacement).collect();
1132	let delta = leaves(&nodes[range.clone()], None).count() as isize
1133	- leaves(&replacement, None).count() as isize;
1134	let after = match root {
1135	Some((_, root)) => root + 1,
1136	None => {
1137	let first = self.starts[range.start];
1138	self.starts.splice(
1139	edit.range.clone(),
1140	starts(&self.nodes[range.clone()], first),
1141	);
1142	let [start, end] = [edit.range.start, edit.range.end]
1143	.map(|index| self.tables.partition_point(|table| *table < index));
1144	let added = tables(&self.nodes[range.clone()], range.start).collect::<Vec<_>>();
1145	let later = start + added.len();
1146	self.tables.splice(start..end, added);
1147	for table in &mut self.tables[later..] {
1148	*table =
1149	table.wrapping_add_signed(range.len() as isize - edit.range.len() as isize);
1150	}
1151	range.end
1152	}
1153	};
1154	if delta != 0 {
1155	for start in &mut self.starts[after..] {
1156	*start = start.wrapping_add_signed(delta);
1157	}
1158	}
1159	let mut columns = edit.columns;
1160	swap_columns(&mut self.nodes, &mut columns);
1161	DocumentEdit {
1162	container: edit.container,
1163	range,
1164	replacement,
1165	columns,
1166	}
1167	}
1168	}
1169
1170	#[cfg(test)]
1171	mod tests {
1172	use super::*;
1173	use onestore::document::Format;
1174	use onestore::page::{Table, TableCell, TableColumn, TableRow};
1175
1176	fn position(paragraph: usize, offset: u32) -> TextPosition {
1177	TextPosition { paragraph, offset }
1178	}
1179
1180	fn table_document() -> TextDocument {
1181	let format = Format::default();
1182	let mut cells = Vec::new();
1183	for texts in [vec!["a🌲b", "second"], vec!["right"]] {
1184	cells.push(TableCell {
1185	id: new_id().unwrap(),
1186	layout: Default::default(),
1187	indents: vec![18.0, 0.0, 27.0, 27.0],
1188	shading: None,
1189	paragraphs: texts
1190	.into_iter()
1191	.map(|text| {
1192	node(Paragraph::new(text.into(), format.clone()), format.clone()).unwrap()
1193	})
1194	.collect(),
1195	unsupported: Vec::new(),
1196	});
1197	}
1198	let table = PageParagraph {
1199	id: new_id().unwrap(),
1200	parent: None,
1201	level: 1,
1202	style: None,
1203	format: format.clone(),
1204	lists: Vec::new(),
1205	tags: Vec::new(),
1206	media: Default::default(),
1207	collapsed: false,
1208	content: ParagraphContent::Table(Table {
1209	id: new_id().unwrap(),
1210	columns: vec![
1211	TableColumn {
1212	width: 72.0,
1213	locked: true
1214	};
1215	2
1216	],
1217	rows: vec![TableRow {
1218	id: new_id().unwrap(),
1219	cells,
1220	}],
1221	borders: Some(true),
1222	layout: Default::default(),
1223	tags: Vec::new(),
1224	}),
1225	};
1226	TextDocument::from_nodes(vec![
1227	node(
1228	Paragraph::new("before".into(), format.clone()),
1229	format.clone(),
1230	)
1231	.unwrap(),
1232	table,
1233	node(Paragraph::new("after".into(), format.clone()), format).unwrap(),
1234	])
1235	.unwrap()
1236	}
1237
1238	#[test]
1239	fn text_and_column_widths_share_an_exact_inverse() {
1240	let mut document = table_document();
1241	let source = document.clone();
1242	let ParagraphContent::Table(table) = &source.nodes()[1].content else {
1243	panic!()
1244	};
1245	let id = table.id;
1246	let neighbor = document.paragraphs().nth(3).unwrap().text().as_ptr();
1247	let mut edit = document
1248	.replace(
1249	position(1, 1)..position(1, 1),
1250	vec![Paragraph::new("X".into(), Format::default())],
1251	)
1252	.unwrap();
1253	edit.columns.insert(id, vec![81.24, 36.0]);
1254	let mut undo = document.apply(edit).unwrap();
1255	assert_eq!(undo.columns[&id], [72.0, 72.0]);
1256	let after = document.clone();
1257	for _ in 0..3 {
1258	let redo = document.apply(undo).unwrap();
1259	assert_eq!(document, source);
1260	assert_eq!(
1261	document.paragraphs().nth(3).unwrap().text().as_ptr(),
1262	neighbor
1263	);
1264	undo = document.apply(redo).unwrap();
1265	assert_eq!(document, after);
1266	assert_eq!(
1267	document.paragraphs().nth(3).unwrap().text().as_ptr(),
1268	neighbor
1269	);
1270	}
1271	let resize = DocumentEdit {
1272	container: None,
1273	range: 0..0,
1274	replacement: Vec::new(),
1275	columns: [(id, vec![37.11, 99.875])].into(),
1276	};
1277	let undo = document.apply(resize).unwrap();
1278	document.apply(undo).unwrap();
1279	assert_eq!(document, after);
1280	}
1281
1282	#[test]
1283	fn invalid_column_patches_do_not_partially_edit_text() {
1284	let mut document = table_document();
1285	let source = document.clone();
1286	let ParagraphContent::Table(table) = &source.nodes()[1].content else {
1287	panic!()
1288	};
1289	let id = table.id;
1290	for widths in [
1291	vec![],
1292	vec![72.0],
1293	vec![72.0, 72.0, 72.0],
1294	vec![72.0, 35.99],
1295	vec![f32::NAN, 72.0],
1296	vec![f32::INFINITY, 72.0],
1297	] {
1298	let mut edit = document
1299	.replace(
1300	position(1, 1)..position(1, 1),
1301	vec![Paragraph::new("X".into(), Format::default())],
1302	)
1303	.unwrap();
1304	edit.columns.insert(id, widths);
1305	assert!(document.apply(edit).is_err());
1306	assert_eq!(document, source);
1307	}
1308	for (range, replacement, id) in [
1309	(0..0, Vec::new(), new_id().unwrap()),
1310	(1..2, Vec::new(), id),
1311	(1..2, vec![source.nodes()[1].clone()], id),
1312	] {
1313	let edit = DocumentEdit {
1314	container: None,
1315	range,
1316	replacement,
1317	columns: [(id, vec![81.0, 90.0])].into(),
1318	};
1319	assert!(document.apply(edit).is_err());
1320	assert_eq!(document, source);
1321	}
1322	}
1323
1324	#[test]
1325	fn cell_text_edits_preserve_the_table_and_restore_paragraph_identity() {
1326	let mut document = table_document();
1327	let original = document.clone();
1328	let ParagraphContent::Table(table) = &document.nodes()[1].content else {
1329	panic!()
1330	};
1331	let cell = table.rows[0].cells[0].id;
1332	let other_text = table.rows[0].cells[1].paragraphs[0]
1333	.text()
1334	.unwrap()
1335	.text
1336	.text()
1337	.as_ptr();
1338	assert_eq!(
1339	document
1340	.paragraphs()
1341	.map(Paragraph::text)
1342	.collect::<Vec<_>>(),
1343	["before", "a🌲b", "second", "right", "after"]
1344	);
1345	let shown = |nodes: Vec<PageParagraph>| {
1346	leaves(&nodes, None)
1347	.map(|(.., node)| node.text().unwrap().text.text().to_owned())
1348	.collect::<Vec<_>>()
1349	};
1350	let selected = |range| shown(document.selected(range).unwrap());
1351	assert_eq!(selected(position(1, 1)..position(2, 3)), ["🌲b", "sec"]);
1352	assert_eq!(
1353	selected(position(1, 1)..position(3, 2)),
1354	["a🌲b", "second", "right"]
1355	);
1356	assert_eq!(
1357	selected(position(0, 2)..position(4, 1)),
1358	["fore", "a🌲b", "second", "right", "a"]
1359	);
1360	let edit = document
1361	.replace(
1362	position(1, 1)..position(2, 3),
1363	vec![Paragraph::new("NEW".into(), Format::default())],
1364	)
1365	.unwrap();
1366	assert_eq!(edit.container, Some(cell));
1367	assert_eq!(edit.range, 0..2);
1368	let undo = document.apply(edit).unwrap();
1369	assert_eq!(
1370	document
1371	.paragraphs()
1372	.map(Paragraph::text)
1373	.collect::<Vec<_>>(),
1374	["before", "aNEWond", "right", "after"]
1375	);
1376	let ParagraphContent::Table(table) = &document.nodes()[1].content else {
1377	panic!()
1378	};
1379	assert_eq!(
1380	table.rows[0].cells[1].paragraphs[0]
1381	.text()
1382	.unwrap()
1383	.text
1384	.text()
1385	.as_ptr(),
1386	other_text
1387	);
1388	assert_eq!(
1389	document.text_nodes().nth(1).unwrap().id,
1390	original.text_nodes().nth(1).unwrap().id
1391	);
1392	assert_eq!(undo.container, Some(cell));
1393	assert_eq!(undo.range, 0..1);
1394	let redo = document.apply(undo).unwrap();
1395	assert_eq!(document, original);
1396	let undo = document.apply(redo).unwrap();
1397	document.apply(undo).unwrap();
1398	assert_eq!(document, original);
1399	}
1400
1401	#[test]
1402	fn surrounding_text_splits_without_flattening_the_table() {
1403	let mut document = table_document();
1404	let original = document.clone();
1405	let edit = document
1406	.replace(
1407	position(4, 2)..position(4, 2),
1408	vec![Paragraph::new(String::new(), Format::default()); 2],
1409	)
1410	.unwrap();
1411	assert_eq!(edit.container, None);
1412	assert_eq!(edit.range, 2..3);
1413	let undo = document.apply(edit).unwrap();
1414	assert_eq!(
1415	document
1416	.paragraphs()
1417	.map(Paragraph::text)
1418	.collect::<Vec<_>>(),
1419	["before", "a🌲b", "second", "right", "af", "ter"]
1420	);
1421	assert_eq!(document.nodes()[1], original.nodes()[1]);
1422	document.apply(undo).unwrap();
1423	assert_eq!(document, original);
1424	let edit = document
1425	.replace(
1426	position(0, 0)..position(4, 0),
1427	vec![Paragraph::new(String::new(), Format::default())],
1428	)
1429	.unwrap();
1430	document.apply(edit).unwrap();
1431	assert_eq!(
1432	document
1433	.paragraphs()
1434	.map(Paragraph::text)
1435	.collect::<Vec<_>>(),
1436	["", "after"]
1437	);
1438	assert_eq!(document.nodes().len(), 2);
1439	}
1440
1441	#[test]
1442	fn cell_edits_validate_utf16_and_container_boundaries_before_mutation() {
1443	let mut document = table_document();
1444	let original = document.clone();
1445	let text = || vec![Paragraph::new("X".into(), Format::default())];
1446	assert_eq!(
1447	document.replace(position(1, 2)..position(1, 3), text()),
1448	Err(EditError::InvalidRange)
1449	);
1450	let across = document
1451	.replace(position(1, 1)..position(3, 1), text())
1452	.unwrap();
1453	let mut deleted = document.clone();
1454	deleted.apply(across).unwrap();
1455	assert_eq!(
1456	deleted
1457	.paragraphs()
1458	.map(Paragraph::text)
1459	.collect::<Vec<_>>(),
1460	["before", "aX", "ight", "after"],
1461	);
1462	let ParagraphContent::Table(table) = &document.nodes()[1].content else {
1463	panic!()
1464	};
1465	let cell = table.rows[0].cells[1].id;
1466	for edit in [
1467	DocumentEdit {
1468	columns: BTreeMap::new(),
1469	container: Some(cell),
1470	range: 0..1,
1471	replacement: Vec::new(),
1472	},
1473	DocumentEdit {
1474	columns: BTreeMap::new(),
1475	container: Some(new_id().unwrap()),
1476	range: 0..1,
1477	replacement: vec![document.nodes()[0].clone()],
1478	},
1479	DocumentEdit {
1480	columns: BTreeMap::new(),
1481	container: Some(cell),
1482	range: 0..usize::MAX,
1483	replacement: Vec::new(),
1484	},
1485	] {
1486	assert_eq!(document.apply(edit), Err(EditError::InvalidRange));
1487	assert_eq!(document, original);
1488	}
1489	let alias = DocumentEdit {
1490	columns: BTreeMap::new(),
1491	container: Some(cell),
1492	range: 0..1,
1493	replacement: vec![document.nodes()[0].clone()],
1494	};
1495	assert_eq!(document.apply(alias), Err(EditError::InvalidStructure));
1496	assert_eq!(document, original);
1497	}
1498
1499	#[test]
1500	fn nested_cell_edits_keep_leaf_order_and_split_paragraphs_locally() {
1501	let mut document = table_document();
1502	let nested = table_document().nodes.remove(1);
1503	let ParagraphContent::Table(table) = &document.nodes()[1].content else {
1504	panic!()
1505	};
1506	let parent = table.rows[0].cells[0].id;
1507	document
1508	.apply(DocumentEdit {
1509	columns: BTreeMap::new(),
1510	container: Some(parent),
1511	range: 0..2,
1512	replacement: vec![nested],
1513	})
1514	.unwrap();
1515	let original = document.clone();
1516	let edit = document
1517	.replace(
1518	position(2, 3)..position(2, 3),
1519	vec![
1520	Paragraph::new("X".into(), Format::default()),
1521	Paragraph::new("Y".into(), Format::default()),
1522	],
1523	)
1524	.unwrap();
1525	assert_ne!(edit.container, Some(parent));
1526	assert_eq!(edit.range, 1..2);
1527	let undo = document.apply(edit).unwrap();
1528	assert_eq!(
1529	document
1530	.paragraphs()
1531	.map(Paragraph::text)
1532	.collect::<Vec<_>>(),
1533	["before", "a🌲b", "secX", "Yond", "right", "right", "after"]
1534	);
1535	document.apply(undo).unwrap();
1536	assert_eq!(document, original);
1537	}
1538
1539	#[test]
1540	#[ignore = "requires CANVAS_TEST_SECTION and CANVAS_TEST_PAGE private fixture inputs"]
1541	fn imported_nodes_preserve_identity_through_edit_and_undo() {
1542	use onestore::page::{Page, PageObject};
1543	use onestore::{RevisionIndex, Store, document::Document};
1544	let bytes = std::fs::read(std::env::var_os("CANVAS_TEST_SECTION").unwrap()).unwrap();
1545	let page = {
1546	let store = Store::parse(&bytes).unwrap();
1547	let index = RevisionIndex::parse(&store).unwrap();
1548	Page::from_document(
1549	&Document::parse(&index).unwrap(),
1550	&std::env::var("CANVAS_TEST_PAGE").unwrap(),
1551	)
1552	.unwrap()
1553	};
1554	drop(bytes);
1555	let mut outlines = 0;
1556	let mut paragraphs = 0;
1557	for outline in page.objects.iter().flat_map(|object| match object {
1558	PageObject::Outline(outline) => std::slice::from_ref(outline),
1559	PageObject::Title(title) => &title.outlines,
1560	_ => &[],
1561	}) {
1562	let original = TextDocument::from_nodes(outline.paragraphs.clone()).unwrap();
1563	for paragraph in 0..original.nodes().len() {
1564	let mut document = original.clone();
1565	let position = TextPosition {
1566	paragraph,
1567	offset: 0,
1568	};
1569	let format = document
1570	.paragraphs()
1571	.nth(paragraph)
1572	.unwrap()
1573	.format_at(0)
1574	.unwrap()
1575	.clone();
1576	let edit = document
1577	.replace(
1578	position..position,
1579	vec![Paragraph::new("probe".into(), format)],
1580	)
1581	.unwrap();
1582	let undo = document.apply(edit).unwrap();
1583	let edited = document.clone();
1584	assert_eq!(edited.nodes()[paragraph].id, original.nodes()[paragraph].id);
1585	assert_eq!(
1586	edited.nodes()[paragraph].text().unwrap().id,
1587	original.nodes()[paragraph].text().unwrap().id
1588	);
1589	let mut restored_text = edited.nodes().to_vec();
1590	restored_text[paragraph].text_mut().unwrap().text =
1591	original.nodes()[paragraph].text().unwrap().text.clone();
1592	assert_eq!(restored_text, original.nodes());
1593	let redo = document.apply(undo).unwrap();
1594	assert_eq!(document, original);
1595	document.apply(redo).unwrap();
1596	assert_eq!(document, edited);
1597	paragraphs += 1;
1598	}
1599	assert_eq!(outline.paragraphs, original.nodes());
1600	outlines += 1;
1601	}
1602	assert!(outlines > 0);
1603	eprintln!(
1604	"Edited and restored {outlines} imported outlines containing {paragraphs} paragraphs"
1605	);
1606	}
1607
1608	#[test]
1609	fn structural_edits_preserve_surviving_node_identity_and_undo_all_metadata() {
1610	let mut source = ["A🌲B", "", "tail"]
1611	.into_iter()
1612	.enumerate()
1613	.map(|(index, text)| {
1614	node(
1615	Paragraph::new(text.into(), Format::default()),
1616	Format {
1617	language: Some(1033 + index as u32),
1618	..Format::default()
1619	},
1620	)
1621	.unwrap()
1622	})
1623	.collect::<Vec<_>>();
1624	source[2].text_mut().unwrap().text = Paragraph::new(
1625	"tail".into(),
1626	Format {
1627	bold: Some(true),
1628	..Format::default()
1629	},
1630	);
1631	let original = TextDocument::from_nodes(source).unwrap();
1632	let mut document = original.clone();
1633	let edit = document
1634	.replace(
1635	position(0, 1)..position(2, 2),
1636	["x", "y", "z"]
1637	.into_iter()
1638	.map(|s| Paragraph::new(s.into(), Format::default()))
1639	.collect(),
1640	)
1641	.unwrap();
1642	let undo = document.apply(edit).unwrap();
1643	assert_eq!(
1644	document
1645	.paragraphs()
1646	.map(Paragraph::text)
1647	.collect::<Vec<_>>(),
1648	["Ax", "y", "zil"]
1649	);
1650	for index in [0, 2] {
1651	assert_eq!(document.nodes()[index].id, original.nodes()[index].id);
1652	assert_eq!(
1653	document.nodes()[index].text().unwrap().id,
1654	original.nodes()[index].text().unwrap().id
1655	);
1656	assert_eq!(
1657	document.nodes()[index].format,
1658	original.nodes()[index].format
1659	);
1660	}
1661	let old_ids: BTreeSet<_> = original
1662	.nodes()
1663	.iter()
1664	.flat_map(|n| [n.id, n.text().unwrap().id])
1665	.collect();
1666	assert!(!old_ids.contains(&document.nodes()[1].id));
1667	assert!(!old_ids.contains(&document.nodes()[1].text().unwrap().id));
1668	let edited = document.clone();
1669	let redo = document.apply(undo).unwrap();
1670	assert_eq!(document, original);
1671	document.apply(redo).unwrap();
1672	assert_eq!(document, edited);
1673	let mut split = original.clone();
1674	let edit = split
1675	.replace(
1676	position(0, 1)..position(0, 1),
1677	vec![Paragraph::new(String::new(), Format::default()); 2],
1678	)
1679	.unwrap();
1680	split.apply(edit).unwrap();
1681	assert_eq!(split.nodes()[0].id, original.nodes()[0].id);
1682	assert!(!old_ids.contains(&split.nodes()[1].id));
1683	assert_eq!(&split.nodes()[2..], &original.nodes()[1..]);
1684	}
1685
1686	#[test]
1687	fn replacement_cannot_alias_existing_objects() {
1688	let mut document =
1689	TextDocument::new(vec![Paragraph::new("text".into(), Format::default())]).unwrap();
1690	let original = document.clone();
1691	let duplicate = DocumentEdit {
1692	columns: BTreeMap::new(),
1693	container: None,
1694	range: 1..1,
1695	replacement: original.nodes().to_vec(),
1696	};
1697	assert_eq!(document.apply(duplicate), Err(EditError::InvalidStructure));
1698	let mut unsupported = original.nodes().to_vec();
1699	unsupported[0].content =
1700	onestore::page::ParagraphContent::Unsupported(onestore::page::Unsupported {
1701	id: new_id().unwrap(),
1702	jcid: 0x60012,
1703	layout: Default::default(),
1704	});
1705	// Content the canvas cannot draw is kept as a placeholder paragraph, once.
1706	assert!(TextDocument::from_nodes(unsupported.clone()).is_ok());
1707	let mut twice = unsupported.clone();
1708	twice[0].id = new_id().unwrap();
1709	twice.extend(unsupported);
1710	assert_eq!(
1711	TextDocument::from_nodes(twice),
1712	Err(EditError::InvalidStructure)
1713	);
1714	assert_eq!(document, original);
1715	}
1716
1717	#[test]
1718	fn paragraph_links_require_an_earlier_parent_at_a_shallower_level() {
1719	let mut nodes = TextDocument::new(
1720	["parent", "child", "grandchild"]
1721	.into_iter()
1722	.map(|text| Paragraph::new(text.into(), Format::default()))
1723	.collect(),
1724	)
1725	.unwrap()
1726	.nodes;
1727	nodes[1].parent = Some(nodes[0].id);
1728	nodes[1].level = 3;
1729	nodes[2].parent = Some(nodes[1].id);
1730	nodes[2].level = 5;
1731	let original = TextDocument::from_nodes(nodes.clone()).unwrap();
1732	for parent in [nodes[2].id, nodes[0].text().unwrap().id, new_id().unwrap()] {
1733	let mut invalid = nodes.clone();
1734	invalid[1].parent = Some(parent);
1735	assert_eq!(
1736	TextDocument::from_nodes(invalid),
1737	Err(EditError::InvalidStructure)
1738	);
1739	}
1740	for level in [0, 1] {
1741	let mut invalid = nodes.clone();
1742	invalid[1].level = level;
1743	assert_eq!(
1744	TextDocument::from_nodes(invalid),
1745	Err(EditError::InvalidStructure)
1746	);
1747	}
1748	let mut document = original.clone();
1749	assert_eq!(
1750	document.apply(DocumentEdit {
1751	columns: BTreeMap::new(),
1752	container: None,
1753	range: 0..1,
1754	replacement: Vec::new()
1755	}),
1756	Err(EditError::InvalidStructure)
1757	);
1758	assert_eq!(document, original);
1759	}
1760
1761	#[test]
1762	fn editing_nested_tagged_text_preserves_metadata_through_structural_changes() {
1763	let mut nodes = TextDocument::new(
1764	["parent", "a🌳e\u{301}z", "child"]
1765	.into_iter()
1766	.map(|text| Paragraph::new(text.into(), Format::default()))
1767	.collect(),
1768	)
1769	.unwrap()
1770	.nodes;
1771	nodes[1].parent = Some(nodes[0].id);
1772	nodes[1].level = 2;
1773	nodes[1].lists.push(new_id().unwrap());
1774	nodes[1].tags.push(onestore::document::Tag {
1775	definition: Some(new_id().unwrap()),
1776	action_type: Some(0),
1777	shape: None,
1778	property_status: None,
1779	status: 1,
1780	created: Some(123),
1781	completed: None,
1782	start: Some(124),
1783	due: Some(456),
1784	task_id: Some([7; 16]),
1785	extra_set: 0,
1786	});
1787	nodes[1].text_mut().unwrap().tags = nodes[1].tags.clone();
1788	nodes[1].collapsed = true;
1789	nodes[2].parent = Some(nodes[1].id);
1790	nodes[2].level = 3;
1791	let original = TextDocument::from_nodes(nodes).unwrap();
1792	let text = original.paragraphs().nth(1).unwrap();
1793	let offsets: Vec<_> = text
1794	.text()
1795	.char_indices()
1796	.map(|(byte, _)| text.utf16_offset(byte).unwrap())
1797	.chain(std::iter::once(
1798	text.utf16_offset(text.text().len()).unwrap(),
1799	))
1800	.collect();
1801	for &start in &offsets {
1802	for &end in offsets.iter().filter(|&&end| end >= start) {
1803	let mut document = original.clone();
1804	let edit = document
1805	.replace(
1806	position(1, start)..position(1, end),
1807	vec![Paragraph::new(
1808	"👩🏽‍💻".into(),
1809	Format {
1810	bold: Some(true),
1811	..Format::default()
1812	},
1813	)],
1814	)
1815	.unwrap();
1816	let undo = document.apply(edit).unwrap();
1817	let edited = document.clone();
1818	let mut restored = edited.nodes().to_vec();
1819	restored[1].text_mut().unwrap().text = text.clone();
1820	assert_eq!(restored, original.nodes());
1821	let redo = document.apply(undo).unwrap();
1822	assert_eq!(document, original);
1823	document.apply(redo).unwrap();
1824	assert_eq!(document, edited);
1825	}
1826	}
1827	let structure = |range: Range<TextPosition>, count| {
1828	let mut document = original.clone();
1829	let edit = document
1830	.replace(
1831	range,
1832	vec![Paragraph::new(String::new(), Format::default()); count],
1833	)
1834	.unwrap();
1835	let undo = document.apply(edit).unwrap();
1836	let edited = document.nodes().to_vec();
1837	document.apply(undo).unwrap();
1838	assert_eq!(document, original);
1839	edited
1840	};
1841	let [parent, item, child] = original.nodes() else {
1842	unreachable!()
1843	};
1844	// The new half takes the list, the children and their collapsed state, not the tags.
1845	let split = structure(position(1, 0)..position(1, 0), 2);
1846	assert_eq!(split[1].id, item.id);
1847	assert!(split[1].text().unwrap().text.text().is_empty() && !split[1].collapsed);
1848	assert_eq!(split[1].tags, item.tags);
1849	let tail = &split[2];
1850	assert_eq!(tail.text().unwrap().text, item.text().unwrap().text);
1851	assert_eq!((tail.parent, tail.level), (Some(parent.id), 2));
1852	assert_eq!(tail.lists, item.lists);
1853	assert!(tail.tags.is_empty() && tail.text().unwrap().tags.is_empty() && tail.collapsed);
1854	assert_eq!((split[3].parent, split[3].level), (Some(tail.id), 3));
1855	// The upper paragraph wins a join and adopts the lower one's children.
1856	let joined = structure(position(0, 6)..position(1, 0), 1);
1857	assert_eq!(joined[0].text().unwrap().text.text(), "parenta🌳e\u{301}z");
1858	assert_eq!((joined[0].id, joined[0].lists.len()), (parent.id, 0));
1859	assert_eq!(
1860	(joined[1].id, joined[1].parent, joined[1].level),
1861	(child.id, Some(parent.id), 2)
1862	);
1863	let joined = structure(position(1, 6)..position(2, 0), 1);
1864	assert_eq!(joined.len(), 2);
1865	assert_eq!(
1866	PageParagraph {
1867	content: item.content.clone(),
1868	..joined[1].clone()
1869	},
1870	*item
1871	);
1872	}
1873
1874	#[test]
1875	fn split_join_and_undo_preserve_empty_paragraph_formats() {
1876	let regular = Format::default();
1877	let bold = Format {
1878	bold: Some(true),
1879	..Format::default()
1880	};
1881	let original = TextDocument::new(vec![
1882	Paragraph::new("left".into(), regular.clone()),
1883	Paragraph::new(String::new(), bold.clone()),
1884	Paragraph::new("right".into(), bold.clone()),
1885	])
1886	.unwrap();
1887	let mut document = original.clone();
1888	let split = document
1889	.replace(
1890	position(0, 2)..position(0, 2),
1891	vec![Paragraph::new(String::new(), regular.clone()); 2],
1892	)
1893	.unwrap();
1894	let undo = document.apply(split).unwrap();
1895	assert_eq!(
1896	document
1897	.paragraphs()
1898	.map(Paragraph::text)
1899	.collect::<Vec<_>>(),
1900	["le", "ft", "", "right"]
1901	);
1902	let redo = document.apply(undo).unwrap();
1903	assert_eq!(document, original);
1904	document.apply(redo).unwrap();
1905	let join = document
1906	.replace(
1907	position(1, 2)..position(3, 0),
1908	vec![Paragraph::new(String::new(), regular)],
1909	)
1910	.unwrap();
1911	let before_join = document.clone();
1912	let undo = document.apply(join).unwrap();
1913	assert_eq!(document.paragraphs().nth(1).unwrap().text(), "ftright");
1914	assert_eq!(
1915	document.paragraphs().nth(1).unwrap().spans()[1].format,
1916	bold
1917	);
1918	document.apply(undo).unwrap();
1919	assert_eq!(document, before_join);
1920	}
1921
1922	#[test]
1923	fn every_scalar_range_replaces_across_paragraphs_and_round_trips() {
1924	let regular = Format::default();
1925	let bold = Format {
1926	bold: Some(true),
1927	..Format::default()
1928	};
1929	let original = TextDocument::new(vec![
1930	Paragraph::from_runs([
1931	("a🌳".into(), regular.clone()),
1932	("e\u{301}".into(), bold.clone()),
1933	]),
1934	Paragraph::new(String::new(), bold.clone()),
1935	Paragraph::new("日本z".into(), regular.clone()),
1936	])
1937	.unwrap();
1938	for (original, regions) in [
1939	(original, vec![0, 0, 0]),
1940	(table_document(), vec![0, 1, 1, 2, 0]),
1941	] {
1942	let positions: Vec<_> = original
1943	.paragraphs()
1944	.enumerate()
1945	.flat_map(|(index, paragraph)| {
1946	(0..=paragraph.text().len()).filter_map(move |byte| {
1947	paragraph
1948	.utf16_offset(byte)
1949	.ok()
1950	.map(|offset| position(index, offset))
1951	})
1952	})
1953	.collect();
1954	let replacements = [
1955	vec![Paragraph::new(String::new(), regular.clone())],
1956	vec![Paragraph::new("x👩🏽‍💻".into(), bold.clone())],
1957	vec![
1958	Paragraph::new(String::new(), bold.clone()),
1959	Paragraph::new(String::new(), regular.clone()),
1960	],
1961	vec![
1962	Paragraph::new("one".into(), bold.clone()),
1963	Paragraph::new(String::new(), regular.clone()),
1964	Paragraph::new("two".into(), bold.clone()),
1965	],
1966	];
1967	let plain = original
1968	.paragraphs()
1969	.map(Paragraph::text)
1970	.collect::<Vec<_>>()
1971	.join("\n");
1972	for &start in &positions {
1973	for &end in positions.iter().filter(|&&end| end >= start) {
1974	for replacement in &replacements {
1975	let mut document = original.clone();
1976	let planned = document.replace(start..end, replacement.clone());
1977	if regions[start.paragraph..=end.paragraph]
1978	.iter()
1979	.any(|region| *region != regions[start.paragraph])
1980	{
1981	// Across a container's edge nothing joins: the start keeps what
1982	// precedes it, followed by the replacement, and the end what
1983	// follows it.
1984	let planned = planned.unwrap();
1985	assert_eq!(document, original);
1986	let undo = document.apply(planned).unwrap();
1987	let texts: Vec<_> =
1988	document.paragraphs().map(Paragraph::text).collect();
1989	let before: Vec<_> =
1990	original.paragraphs().map(Paragraph::text).collect();
1991	assert_eq!(texts[..start.paragraph], before[..start.paragraph]);
1992	let text = |position: TextPosition| before[position.paragraph];
1993	let byte = |position: TextPosition| {
1994	original
1995	.paragraphs()
1996	.nth(position.paragraph)
1997	.unwrap()
1998	.byte_offset(position.offset)
1999	.unwrap()
2000	};
2001	let mut inserted: Vec<String> =
2002	replacement.iter().map(|p| p.text().to_owned()).collect();
2003	inserted[0].insert_str(0, &text(start)[..byte(start)]);
2004	let at = start.paragraph;
2005	assert_eq!(texts[at..at + inserted.len()], inserted);
2006	assert!(
2007	texts[at + inserted.len()..].contains(&&text(end)[byte(end)..])
2008	);
2009	let after = document.clone();
2010	let redo = document.apply(undo).unwrap();
2011	assert_eq!(document, original, "{start:?}..{end:?}");
2012	document.apply(redo).unwrap();
2013	assert_eq!(document, after);
2014	continue;
2015	}
2016	let planned = planned.unwrap();
2017	assert_eq!(document, original);
2018	let undo = document.apply(planned).unwrap();
2019	assert!(document.paragraphs().next().is_some());
2020	let byte = |position: TextPosition| {
2021	original
2022	.paragraphs()
2023	.take(position.paragraph)
2024	.map(|p| p.text().len() + 1)
2025	.sum::<usize>()
2026	+ original
2027	.paragraphs()
2028	.nth(position.paragraph)
2029	.unwrap()
2030	.byte_offset(position.offset)
2031	.unwrap()
2032	};
2033	let mut expected = plain.clone();
2034	expected.replace_range(
2035	byte(start)..byte(end),
2036	&replacement
2037	.iter()
2038	.map(Paragraph::text)
2039	.collect::<Vec<_>>()
2040	.join("\n"),
2041	);
2042	assert_eq!(
2043	document
2044	.paragraphs()
2045	.map(Paragraph::text)
2046	.collect::<Vec<_>>()
2047	.join("\n"),
2048	expected
2049	);
2050	let after = document.clone();
2051	let redo = document.apply(undo).unwrap();
2052	assert_eq!(document, original, "{start:?}..{end:?}");
2053	document.apply(redo).unwrap();
2054	assert_eq!(document, after);
2055	}
2056	}
2057	}
2058	}
2059	}
2060
2061	/// Validates the materialized edited document from scratch.
2062	fn full_validation(document: &TextDocument, edit: &DocumentEdit) -> Result<(), EditError> {
2063	let mut nodes = document.nodes.clone();
2064	let container = container_mut(&mut nodes, edit.container).ok_or(EditError::InvalidRange)?;
2065	if edit.range.start > edit.range.end || edit.range.end > container.len() {
2066	return Err(EditError::InvalidRange);
2067	}
2068	container.splice(edit.range.clone(), edit.replacement.iter().cloned());
2069	validate_nodes(&nodes, &mut BTreeSet::new())?;
2070	let tables = |nodes| {
2071	descendants(nodes, None)
2072	.filter_map(|(_, _, node)| match &node.content {
2073	ParagraphContent::Table(table) => Some((table.id, table.columns.len())),
2074	_ => None,
2075	})
2076	.collect::<BTreeMap<_, _>>()
2077	};
2078	let replaced = tables(&edit.replacement);
2079	let tables = tables(&nodes);
2080	for (id, widths) in &edit.columns {
2081	if replaced.contains_key(id)
2082	|| tables.get(id) != Some(&widths.len())
2083	|| widths
2084	.iter()
2085	.any(|width| !width.is_finite() || *width < 36.0)
2086	{
2087	return Err(EditError::InvalidStructure);
2088	}
2089	}
2090	validate_text(&edit.replacement)
2091	}
2092
2093	#[test]
2094	fn incremental_validation_matches_full_validation_of_random_edits() {
2095	let mut seed = 0x9e37_79b9_u64;
2096	let mut next = |n: usize| {
2097	seed = seed
2098	.wrapping_mul(6364136223846793005)
2099	.wrapping_add(1442695040888963407);
2100	(seed >> 33) as usize % n.max(1)
2101	};
2102	let fresh = |text: &str| {
2103	node(
2104	Paragraph::new(text.into(), Format::default()),
2105	Format::default(),
2106	)
2107	.unwrap()
2108	};
2109	let mut document = table_document();
2110	let [mut accepted, mut rejected] = [0; 2];
2111	for step in 0..4000 {
2112	let all = descendants(&document.nodes, None)
2113	.map(|(_, _, node)| node.clone())
2114	.collect::<Vec<_>>();
2115	let cells = all
2116	.iter()
2117	.filter_map(|node| match &node.content {
2118	ParagraphContent::Table(table) => Some(table),
2119	_ => None,
2120	})
2121	.flat_map(|table| table.rows.iter().flat_map(|row| &row.cells))
2122	.map(|cell| Some(cell.id))
2123	.collect::<Vec<_>>();
2124	let tables = all
2125	.iter()
2126	.filter_map(|node| match &node.content {
2127	ParagraphContent::Table(table) => Some(table.id),
2128	_ => None,
2129	})
2130	.collect::<Vec<_>>();
2131	let container = match next(8) {
2132	0..4 => None,
2133	7 if step % 5 == 0 => Some(new_id().unwrap()),
2134	_ => cells.get(next(cells.len())).copied().flatten(),
2135	};
2136	let nodes = document.container(container).unwrap_or(&[]).to_vec();
2137	let start = next(nodes.len() + 2);
2138	let range = if next(16) == 0 {
2139	start..start.saturating_sub(1)
2140	} else {
2141	start..(start + next(3)).min(nodes.len() + usize::from(next(8) == 0))
2142	};
2143	let removed = nodes.get(range.clone()).unwrap_or_default();
2144	let prefix = &nodes[..range.start.min(nodes.len())];
2145	let suffix = nodes.get(range.end..).unwrap_or_default();
2146	let ids =
2147	|nodes: &[PageParagraph]| nodes.iter().map(|node| node.id).collect::<Vec<_>>();
2148	let parents = [ids(prefix), ids(removed), ids(suffix), ids(&all)].concat();
2149	let mut replacement = Vec::new();
2150	for _ in 0..next(4) {
2151	let mut node = match next(10) {
2152	0..3 if !removed.is_empty() => removed[next(removed.len())].clone(),
2153	3 if !all.is_empty() => all[next(all.len())].clone(),
2154	4 => {
2155	let mut table = table_document().nodes.remove(1);
2156	let ParagraphContent::Table(inner) = &mut table.content else {
2157	unreachable!()
2158	};
2159	match next(6) {
2160	0 => inner.rows[0].cells[0].paragraphs.clear(),
2161	1 => inner.columns[0].width = 35.0,
2162	2 => {
2163	inner.rows[0].cells.pop();
2164	}
2165	3 => {
2166	inner.rows[0].cells[1].paragraphs[0].parent =
2167	Some(inner.rows[0].cells[0].paragraphs[0].id);
2168	}
2169	_ => {}
2170	}
2171	table
2172	}
2173	_ => fresh("new"),
2174	};
2175	match next(6) {
2176	0 => node.level = next(4) as u32,
2177	1 => node.level += 1,
2178	2 => {
2179	node.level = 1 + next(4) as u32;
2180	node.parent = (!parents.is_empty()).then(|| parents[next(parents.len())]);
2181	}
2182	3 => node.parent = None,
2183	_ => {}
2184	}
2185	replacement.push(node);
2186	}
2187	let mut columns = BTreeMap::new();
2188	if next(12) == 0 {
2189	let id = tables
2190	.get(next(tables.len() + 1))
2191	.copied()
2192	.unwrap_or_else(|| new_id().unwrap());
2193	columns.insert(id, vec![[72.0, 30.0, f32::NAN][next(3)]; 1 + next(3)]);
2194	}
2195	let edit = if next(4) == 0 {
2196	let positions = document.paragraphs().count();
2197	let paragraph = next(positions);
2198	let offset = document.paragraphs().nth(paragraph).unwrap().text().len() as u32;
2199	let start = TextPosition {
2200	paragraph,
2201	offset: next(offset as usize + 1) as u32,
2202	};
2203	let end = TextPosition {
2204	paragraph: paragraph + usize::from(paragraph + 1 < positions && next(2) == 0),
2205	offset: 0,
2206	};
2207	let texts = vec![Paragraph::new("typed".into(), Format::default()); 1 + next(2)];
2208	match document.replace(start..end.max(start), texts) {
2209	Ok(edit) => edit,
2210	Err(_) => continue,
2211	}
2212	} else {
2213	DocumentEdit {
2214	container,
2215	range,
2216	replacement,
2217	columns,
2218	}
2219	};
2220	let expected = full_validation(&document, &edit);
2221	assert_eq!(
2222	document.validate_edit(&edit).is_ok(),
2223	expected.is_ok(),
2224	"step {step}: {expected:?} for {edit:#?}"
2225	);
2226	if expected.is_ok() {
2227	accepted += 1;
2228	let edited = leaves(&document.nodes, Some(&edit)).collect::<Vec<_>>();
2229	let supplied = descendants(&edit.replacement, None)
2230	.map(|(_, _, node)| node.id)
2231	.collect::<BTreeSet<_>>();
2232	for paragraph in 0..=edited.len() {
2233	let leaf = document.edited_leaf(&edit, paragraph);
2234	assert_eq!(
2235	leaf.map(|(node, _)| node),
2236	edited.get(paragraph).map(|(_, _, node)| *node)
2237	);
2238	if let Some((node, before)) = leaf {
2239	assert_eq!(before.is_none(), supplied.contains(&node.id));
2240	assert!(
2241	before.is_none_or(|before| document.leaf(before).unwrap().2 == node)
2242	);
2243	}
2244	}
2245	document.apply(edit).unwrap();
2246	assert_eq!(
2247	document,
2248	TextDocument::from_nodes(document.nodes.clone()).unwrap()
2249	);
2250	let walked = leaves(&document.nodes, None).collect::<Vec<_>>();
2251	for paragraph in 0..=walked.len() {
2252	assert_eq!(document.leaf(paragraph), walked.get(paragraph).copied());
2253	}
2254	} else {
2255	rejected += 1;
2256	}
2257	}
2258	assert!(accepted > 500 && rejected > 500, "{accepted} {rejected}");
2259	let nest = |mut node, depth| {
2260	for _ in 0..depth {
2261	let mut table = table_document().nodes.remove(1);
2262	let ParagraphContent::Table(inner) = &mut table.content else {
2263	unreachable!()
2264	};
2265	inner.rows[0].cells[0].paragraphs = vec![node];
2266	node = table;
2267	}
2268	node
2269	};
2270	let document = TextDocument::from_nodes(vec![nest(fresh("leaf"), 64)]).unwrap();
2271	let (innermost, _, _) = leaves(&document.nodes, None)
2272	.find(|(_, _, node)| node.text().unwrap().text.text() == "leaf")
2273	.unwrap();
2274	for (container, depth, valid) in [
2275	(innermost, 0, true),
2276	(innermost, 1, false),
2277	(None, 64, true),
2278	(None, 65, false),
2279	] {
2280	let edit = DocumentEdit {
2281	container,
2282	range: 0..0,
2283	replacement: vec![nest(fresh("deep"), depth)],
2284	columns: BTreeMap::new(),
2285	};
2286	assert_eq!(
2287	document.validate_edit(&edit).is_ok(),
2288	full_validation(&document, &edit).is_ok()
2289	);
2290	assert_eq!(document.validate_edit(&edit).is_ok(), valid);
2291	}
2292	}
2293
2294	#[test]
2295	fn invalid_ranges_and_last_paragraph_removal_are_atomic() {
2296	let original =
2297	TextDocument::new(vec![Paragraph::new("🌳".into(), Format::default())]).unwrap();
2298	for range in [
2299	position(0, 1)..position(0, 2),
2300	position(0, 0)..position(1, 0),
2301	position(0, 2)..position(0, 0),
2302	] {
2303	assert!(
2304	original
2305	.replace(
2306	range,
2307	vec![Paragraph::new(String::new(), Format::default())]
2308	)
2309	.is_err()
2310	);
2311	}
2312	for range in [0..1, 0..2, Range { start: 2, end: 1 }] {
2313	let mut document = original.clone();
2314	assert!(
2315	document
2316	.apply(DocumentEdit {
2317	columns: BTreeMap::new(),
2318	container: None,
2319	range,
2320	replacement: Vec::new()
2321	})
2322	.is_err()
2323	);
2324	assert_eq!(document, original);
2325	}
2326	assert!(TextDocument::new(Vec::new()).is_err());
2327	}
2328
2329	#[test]
2330	#[ignore = "requires CANVAS_TEST_SECTION pointing to the native Tab table capture"]
2331	fn native_table_import() {
2332	use onestore::{
2333	RevisionIndex, Store,
2334	document::Document,
2335	page::{Page, PageObject, ParagraphContent},
2336	};
2337	let page = {
2338	let bytes = std::fs::read(std::env::var_os("CANVAS_TEST_SECTION").unwrap()).unwrap();
2339	let store = Store::parse(&bytes).unwrap();
2340	let index = RevisionIndex::parse(&store).unwrap();
2341	let document = Document::parse(&index).unwrap();
2342	for (space, page) in document.pages().unwrap() {
2343	let space = &document.spaces[&space];
2344	let revision = &space.revisions[&space.contexts[&ExGuid::default()]];
2345	Page::from_revision(revision, page).unwrap();
2346	}
2347	Page::from_document(&document, "rows").unwrap()
2348	};
2349	let table = page
2350	.objects
2351	.iter()
2352	.find_map(|object| match object {
2353	PageObject::Outline(outline) => {
2354	outline.paragraphs.iter().find_map(|p| match &p.content {
2355	ParagraphContent::Table(table) => Some(table),
2356	_ => None,
2357	})
2358	}
2359	_ => None,
2360	})
2361	.unwrap();
2362	assert_eq!(table.rows.len(), 3);
2363	assert_eq!(table.columns.len(), 2);
2364	assert!(table.columns.iter().all(|c| !c.locked));
2365	let cells: Vec<_> = table.rows.iter().flat_map(|row| &row.cells).collect();
2366	let text: Vec<_> = cells
2367	.iter()
2368	.map(|cell| cell.paragraphs[0].text().unwrap().text.text())
2369	.collect();
2370	assert_eq!(text, ["Alpha", "Beta", "Gamma", "Delta", "Epsilon", ""]);
2371	assert!(cells.iter().all(|c| c.indents == [18.0, 0.0, 27.0, 27.0]));
2372	let outline = page
2373	.objects
2374	.iter()
2375	.find_map(|object| match object {
2376	PageObject::Outline(outline)
2377	if outline
2378	.paragraphs
2379	.iter()
2380	.any(|p| matches!(p.content, ParagraphContent::Table(_))) =>
2381	{
2382	Some(outline)
2383	}
2384	_ => None,
2385	})
2386	.unwrap();
2387	let mut document = TextDocument::from_nodes(outline.paragraphs.clone()).unwrap();
2388	let original = document.clone();
2389	for (index, cell) in cells.iter().enumerate() {
2390	let position = TextPosition {
2391	paragraph: index,
2392	offset: 0,
2393	};
2394	let edit = document
2395	.replace(
2396	position..position,
2397	vec![
2398	Paragraph::new("🧊".into(), Format::default()),
2399	Paragraph::new("text".into(), Format::default()),
2400	],
2401	)
2402	.unwrap();
2403	assert_eq!(edit.container, Some(cell.id));
2404	let undo = document.apply(edit).unwrap();
2405	assert_eq!(document.paragraphs().nth(index).unwrap().text(), "🧊");
2406	document.apply(undo).unwrap();
2407	assert_eq!(document, original);
2408	}
2409	}
2410	}