clover's git

snowbound

1	//! The ops that turn one page model into another, computed from the models alone: each op
2	//! is interpreted on a prediction of the page (`model::apply`) so later ones see what earlier
3	//! ones leave, as the typed writers would store it.
4
5	use super::{PageOp, TableEdit, TextProperty, Values, model};
6	use crate::{
7	Error, ExGuid, TextAttribute,
8	document::{Format, Kind, Tag},
9	page::{
10	Definition, Outline, Page, PageObject, PageParagraph, Paragraph, ParagraphContent, Table,
11	TableCell, TextObject, text::new_id,
12	},
13	};
14	use std::{
15	collections::{BTreeMap, BTreeSet},
16	ops::Range,
17	};
18
19	fn invalid(message: &'static str) -> Error {
20	Error { offset: 0, message }
21	}
22
23	/// The ops that turn `before`, a page as stored, into `after`: O(page), for importing a
24	/// page, converting queued whole-page edits and resolving a conflict, never per keystroke.
25	pub fn lower_page(before: &Page, after: &Page) -> Result<Vec<PageOp>, Error> {
26	let old = View::new(before, false)?;
27	let new = View::new(after, false)?;
28	Lowering::new(before.clone(), None).run(before, after, &old, &new)
29	}
30
31	/// The ops that replace `before`, consecutive paragraphs of outline or table cell
32	/// `container` with their parents listed first or outside the range, by `after`. `next`
33	/// is the paragraph following the range; `definitions` holds the lists, tags and styles
34	/// the paragraphs reference. Only the paragraphs given are read.
35	pub fn lower(
36	container: ExGuid,
37	before: &[PageParagraph],
38	after: &[PageParagraph],
39	next: Option<&PageParagraph>,
40	definitions: &BTreeMap<ExGuid, Definition>,
41	) -> Result<Vec<PageOp>, Error> {
42	let page = |paragraphs: &[PageParagraph]| Page {
43	title: String::new(),
44	identity: None,
45	created: None,
46	margin_origin: [0.0; 2],
47	rtl: false,
48	color: None,
49	rule_lines: None,
50	objects: vec![PageObject::Outline(Outline {
51	id: container,
52	title: false,
53	min_width: None,
54	layout: Default::default(),
55	indents: Vec::new(),
56	paragraphs: paragraphs.to_vec(),
57	unsupported: Vec::new(),
58	})],
59	definitions: definitions.clone(),
60	};
61	let (before, after) = (page(before), page(after));
62	let old = View::new(&before, true)?;
63	let new = View::new(&after, true)?;
64	let tail = next.map(|next| (next.parent.unwrap_or(container), next.id));
65	Lowering::new(before.clone(), tail).run(&before, &after, &old, &new)
66	}
67
68	/// Direct children of every container, in model order, plus lookups by identity.
69	pub(crate) struct View<'a> {
70	pub page: &'a Page,
71	pub outlines: BTreeMap<ExGuid, &'a Outline>,
72	/// Outlines owned by a title object rather than the page.
73	pub title_outlines: BTreeSet<ExGuid>,
74	pub paragraphs: BTreeMap<ExGuid, &'a PageParagraph>,
75	pub children: BTreeMap<ExGuid, Vec<ExGuid>>,
76	pub container: BTreeMap<ExGuid, ExGuid>,
77	pub page_children: Vec<ExGuid>,
78	/// Containers a partial model names as parents without holding them, in order.
79	pub external: Vec<ExGuid>,
80	partial: bool,
81	}
82
83	impl<'a> View<'a> {
84	/// `partial` accepts parents outside the model, as a range of paragraphs has.
85	pub(crate) fn new(page: &'a Page, partial: bool) -> Result<Self, Error> {
86	let mut view = Self {
87	page,
88	outlines: BTreeMap::new(),
89	title_outlines: BTreeSet::new(),
90	paragraphs: BTreeMap::new(),
91	children: BTreeMap::new(),
92	container: BTreeMap::new(),
93	page_children: Vec::new(),
94	external: Vec::new(),
95	partial,
96	};
97	for object in &page.objects {
98	view.page_children.push(object.id());
99	match object {
100	PageObject::Outline(outline) => view.outline(outline)?,
101	PageObject::Title(title) => {
102	for outline in &title.outlines {
103	view.title_outlines.insert(outline.id);
104	view.outline(outline)?;
105	}
106	}
107	PageObject::Image(_)
108	| PageObject::Attachment(_)
109	| PageObject::Ink(_)
110	| PageObject::Unsupported(_) => {}
111	}
112	}
113	Ok(view)
114	}
115
116	fn outline(&mut self, outline: &'a Outline) -> Result<(), Error> {
117	if self.outlines.insert(outline.id, outline).is_some() {
118	return Err(invalid("The page model repeats an outline identity"));
119	}
120	self.children.entry(outline.id).or_default();
121	self.paragraphs_of(outline.id, &outline.paragraphs)
122	}
123
124	fn paragraphs_of(&mut self, root: ExGuid, list: &'a [PageParagraph]) -> Result<(), Error> {
125	let listed: BTreeSet<ExGuid> = if self.partial {
126	list.iter().map(|p| p.id).collect()
127	} else {
128	BTreeSet::new()
129	};
130	for paragraph in list {
131	let container = paragraph.parent.unwrap_or(root);
132	if let Some(parent) = paragraph.parent
133	&& !self.paragraphs.contains_key(&parent)
134	{
135	if !self.partial || listed.contains(&parent) {
136	return Err(invalid(
137	"A paragraph's parent must precede it in its container",
138	));
139	}
140	if !self.external.contains(&parent) {
141	self.external.push(parent);
142	}
143	}
144	if self.paragraphs.insert(paragraph.id, paragraph).is_some() {
145	return Err(invalid("The page model repeats a paragraph identity"));
146	}
147	self.children
148	.entry(container)
149	.or_default()
150	.push(paragraph.id);
151	self.children.entry(paragraph.id).or_default();
152	self.container.insert(paragraph.id, container);
153	if let ParagraphContent::Table(table) = &paragraph.content {
154	for row in &table.rows {
155	for cell in &row.cells {
156	if self.children.contains_key(&cell.id) {
157	return Err(invalid("The page model repeats a cell identity"));
158	}
159	self.children.entry(cell.id).or_default();
160	self.paragraphs_of(cell.id, &cell.paragraphs)?;
161	}
162	}
163	}
164	}
165	Ok(())
166	}
167
168	pub(crate) fn text(&self, paragraph: ExGuid) -> Option<&'a TextObject> {
169	self.paragraphs.get(&paragraph).and_then(|p| p.text())
170	}
171
172	/// Each outline's paragraphs in document order, a table's cells following its paragraph.
173	pub(crate) fn documents(&self) -> impl Iterator<Item = Vec<&'a PageParagraph>> + '_ {
174	fn walk<'a>(list: &'a [PageParagraph], out: &mut Vec<&'a PageParagraph>) {
175	for paragraph in list {
176	out.push(paragraph);
177	if let ParagraphContent::Table(table) = &paragraph.content {
178	for cell in table.rows.iter().flat_map(|row| &row.cells) {
179	walk(&cell.paragraphs, out);
180	}
181	}
182	}
183	}
184	self.outlines.values().map(|outline| {
185	let mut out = Vec::new();
186	walk(&outline.paragraphs, &mut out);
187	out
188	})
189	}
190
191	/// Every container in document order: outlines, external parents, paragraphs and cells.
192	fn containers(&self) -> Vec<ExGuid> {
193	let mut containers = Vec::new();
194	for object in &self.page.objects {
195	let outlines: Vec<&Outline> = match object {
196	PageObject::Outline(outline) => vec![outline],
197	PageObject::Title(title) => title.outlines.iter().collect(),
198	PageObject::Image(_)
199	| PageObject::Attachment(_)
200	| PageObject::Ink(_)
201	| PageObject::Unsupported(_) => Vec::new(),
202	};
203	for outline in outlines {
204	containers.push(outline.id);
205	containers.extend(&self.external);
206	collect_containers(&outline.paragraphs, &mut containers);
207	}
208	}
209	containers
210	}
211	}
212
213	pub(crate) fn collect_containers(list: &[PageParagraph], out: &mut Vec<ExGuid>) {
214	for paragraph in list {
215	out.push(paragraph.id);
216	if let ParagraphContent::Table(table) = &paragraph.content {
217	for row in &table.rows {
218	for cell in &row.cells {
219	out.push(cell.id);
220	collect_containers(&cell.paragraphs, out);
221	}
222	}
223	}
224	}
225	}
226
227	/// What the writers keep as stored, checked before any op: titles, unsupported objects,
228	/// definitions other than lists and tags, outline roles, paragraph styles and formats,
229	/// fields and content types.
230	pub(crate) fn validate(
231	before: &Page,
232	after: &Page,
233	old: &View<'_>,
234	new: &View<'_>,
235	) -> Result<(), Error> {
236	if after.margin_origin != before.margin_origin {
237	return Err(invalid("Page margins cannot be edited"));
238	}
239	for (id, definition) in &after.definitions {
240	if before
241	.definitions
242	.get(id)
243	.is_some_and(|stored| stored != definition)
244	&& !matches!(
245	definition.kind,
246	Kind::List { .. } | Kind::TagDefinition { .. }
247	)
248	{
249	return Err(invalid("Style definitions cannot be edited"));
250	}
251	}
252	for paragraph in new.paragraphs.values() {
253	if let ParagraphContent::Table(table) = &paragraph.content {
254	super::table::validate_table(table)?;
255	}
256	}
257	let fixed = |page: &Page| -> Vec<String> {
258	let mut fixed: Vec<String> = page
259	.objects
260	.iter()
261	.filter_map(|object| match object {
262	PageObject::Unsupported(unsupported) => Some(format!("{unsupported:?}")),
263	PageObject::Title(title) => Some(format!(
264	"{:?} {:?} {:?} {:?}",
265	title.id,
266	title.date,
267	title.layout,
268	title.outlines.iter().map(|o| o.id).collect::<Vec<_>>()
269	)),
270	PageObject::Outline(_)
271	| PageObject::Image(_)
272	| PageObject::Attachment(_)
273	| PageObject::Ink(_) => None,
274	})
275	.collect();
276	fixed.sort();
277	fixed
278	};
279	if fixed(before) != fixed(after) {
280	return Err(invalid(
281	"Titles and unsupported objects cannot be edited through the page model",
282	));
283	}
284	for (id, outline) in &new.outlines {
285	if outline.paragraphs.is_empty() {
286	return Err(invalid(
287	"An outline needs a paragraph; remove the outline instead",
288	));
289	}
290	let Some(previous) = old.outlines.get(id) else {
291	continue;
292	};
293	let same = outline.title == previous.title
294	&& outline.min_width == previous.min_width
295	&& outline.indents == previous.indents
296	&& outline.unsupported == previous.unsupported
297	&& (!new.title_outlines.contains(id) || outline.layout == previous.layout);
298	if !same {
299	return Err(invalid(
300	"Outline roles, indentation tables and title geometry cannot be edited",
301	));
302	}
303	}
304	let owners: BTreeMap<ExGuid, &PageParagraph> = old
305	.paragraphs
306	.values()
307	.filter_map(|owner| Some((owner.text()?.id, *owner)))
308	.collect();
309	for (id, paragraph) in &new.paragraphs {
310	let Some(previous) = old.paragraphs.get(id) else {
311	continue;
312	};
313	// A join moves a text object, with its style, into an emptied paragraph.
314	let owner = paragraph.text().map(|text| owners.get(&text.id));
315	let style = match owner {
316	Some(Some(owner)) => owner.style,
317	Some(None) => paragraph.style,
318	None => previous.style,
319	};
320	// `Style` and `Unstyle` give a paragraph of text a style and take it away.
321	let restyled = paragraph.style != style && paragraph.text().is_none();
322	if restyled || paragraph.format != previous.format {
323	return Err(invalid(
324	"Paragraph styles and paragraph formatting cannot be edited",
325	));
326	}
327	match (&paragraph.content, &previous.content) {
328	(ParagraphContent::Text(text), ParagraphContent::Text(previous)) => {
329	if text.date_field != previous.date_field {
330	return Err(invalid("Text fields cannot be edited"));
331	}
332	}
333	(ParagraphContent::Table(table), ParagraphContent::Table(previous)) => {
334	if table.id != previous.id || table.layout != previous.layout {
335	return Err(invalid("Table identity and layout cannot be edited"));
336	}
337	let cells: BTreeMap<ExGuid, &TableCell> = previous
338	.rows
339	.iter()
340	.flat_map(|row| &row.cells)
341	.map(|cell| (cell.id, cell))
342	.collect();
343	let unchanged_cells = table.rows.iter().flat_map(|row| &row.cells).all(|cell| {
344	cells.get(&cell.id).is_none_or(|before| {
345	cell.layout == before.layout && cell.unsupported == before.unsupported
346	})
347	});
348	if !unchanged_cells {
349	return Err(invalid("Cell layout cannot be edited"));
350	}
351	}
352	(ParagraphContent::Unsupported(a), ParagraphContent::Unsupported(b)) if a == b => {}
353	(ParagraphContent::Ink(a), ParagraphContent::Ink(b)) => {
354	if a.id != b.id {
355	return Err(invalid("Ink identity cannot change"));
356	}
357	}
358	(ParagraphContent::Image(a), ParagraphContent::Image(b)) => {
359	super::content::picture_fixed_fields(a, b)?;
360	if (a.layout.x, a.layout.y) != (b.layout.x, b.layout.y) {
361	return Err(invalid("A paragraph picture has no position of its own"));
362	}
363	}
364	(ParagraphContent::Attachment(a), ParagraphContent::Attachment(b)) => {
365	if a.id != b.id {
366	return Err(invalid("Attachment identity cannot change"));
367	}
368	}
369	_ => return Err(invalid("Paragraph content type cannot change")),
370	}
371	}
372	Ok(())
373	}
374
375	/// Identities that keep their stored position: a longest increasing run of survivors,
376	/// always including immovable ones. `after` may contain identities absent from `before`.
377	pub(crate) fn kept_set(
378	before: &[ExGuid],
379	after: &[ExGuid],
380	movable: impl Fn(ExGuid) -> bool,
381	) -> Result<BTreeSet<ExGuid>, Error> {
382	let position: BTreeMap<ExGuid, usize> =
383	after.iter().enumerate().map(|(i, id)| (*id, i)).collect();
384	let sequence: Vec<(ExGuid, usize)> = before
385	.iter()
386	.filter_map(|id| position.get(id).map(|at| (*id, *at)))
387	.collect();
388	let fixed: Vec<usize> = sequence
389	.iter()
390	.filter(|(id, _)| !movable(*id))
391	.map(|(_, at)| *at)
392	.collect();
393	if fixed.windows(2).any(|w| w[0] > w[1]) {
394	return Err(invalid(
395	"Images and unsupported objects cannot be reordered",
396	));
397	}
398	if sequence.windows(2).all(|pair| pair[0].1 < pair[1].1) {
399	return Ok(sequence.into_iter().map(|(id, _)| id).collect());
400	}
401	// Longest increasing subsequence over `after` positions, forced through immovable items.
402	let n = sequence.len();
403	let mut best = vec![1usize; n];
404	let mut previous = vec![usize::MAX; n];
405	for i in 0..n {
406	let (id, at) = sequence[i];
407	let mandatory_before = sequence[..i]
408	.iter()
409	.filter(|(other, _)| !movable(*other))
410	.map(|(_, at)| *at)
411	.max();
412	if movable(id) && mandatory_before.is_some_and(|m| m > at) {
413	best[i] = 0;
414	continue;
415	}
416	let mandatory_after = sequence[i + 1..]
417	.iter()
418	.filter(|(other, _)| !movable(*other))
419	.map(|(_, at)| *at)
420	.min();
421	if movable(id) && mandatory_after.is_some_and(|m| m < at) {
422	best[i] = 0;
423	continue;
424	}
425	for j in 0..i {
426	if best[j] > 0 && sequence[j].1 < at && best[j] + 1 > best[i] {
427	best[i] = best[j] + 1;
428	previous[i] = j;
429	}
430	}
431	}
432	let mut kept = BTreeSet::new();
433	if let Some((mut i, _)) = best
434	.iter()
435	.enumerate()
436	.max_by_key(|(i, b)| (**b, usize::MAX - i))
437	&& best[i] > 0
438	{
439	loop {
440	kept.insert(sequence[i].0);
441	if previous[i] == usize::MAX {
442	break;
443	}
444	i = previous[i];
445	}
446	}
447	for (id, _) in &sequence {
448	if !movable(*id) && !kept.contains(id) {
449	return Err(invalid(
450	"Images and unsupported objects cannot be reordered",
451	));
452	}
453	}
454	Ok(kept)
455	}
456
457	/// The format of the span containing the UTF-16 position `at` (the following span at a
458	/// boundary, the last at the end), which text inserted there takes.
459	pub(crate) fn format_in(paragraph: &Paragraph, at: u32) -> Result<&Format, Error> {
460	let byte = paragraph.byte_offset(at)?;
461	let spans = paragraph.spans();
462	let index = spans
463	.partition_point(|span| span.end <= byte)
464	.min(spans.len() - 1);
465	Ok(&spans[index].format)
466	}
467
468	/// The smallest UTF-16 range whose replacement turns `before` into `after`.
469	pub(crate) fn text_edit(before: &str, after: &str) -> Result<(Range<u32>, String), Error> {
470	let prefix = before
471	.char_indices()
472	.zip(after.chars())
473	.take_while(|((_, a), b)| a == b)
474	.map(|((i, a), _)| i + a.len_utf8())
475	.last()
476	.unwrap_or(0);
477	let suffix = before[prefix..]
478	.chars()
479	.rev()
480	.zip(after[prefix..].chars().rev())
481	.take_while(|(a, b)| a == b)
482	.map(|(a, _)| a.len_utf8())
483	.sum::<usize>();
484	let units = |s: &str| -> Result<u32, Error> {
485	u32::try_from(s.encode_utf16().count())
486	.map_err(|_| invalid("Text exceeds UTF-16 offset range"))
487	};
488	let start = units(&before[..prefix])?;
489	let end = start + units(&before[prefix..before.len() - suffix])?;
490	Ok((start..end, after[prefix..after.len() - suffix].to_owned()))
491	}
492
493	/// A character-format change over a range: attributes to set and properties to clear.
494	pub(crate) type FormatEdit = (Range<u32>, Vec<TextAttribute>, Vec<TextProperty>);
495
496	/// The format edits turning `stored`'s spans into `target`'s, which has the same text. A
497	/// `fresh` text object was created by this edit, so an unset language keeps the writer's.
498	pub(crate) fn format_edits(
499	stored: &Paragraph,
500	target: &Paragraph,
501	fresh: bool,
502	) -> Result<Vec<FormatEdit>, Error> {
503	let mut boundaries = BTreeSet::new();
504	for paragraph in [stored, target] {
505	for span in paragraph.spans() {
506	boundaries.insert(paragraph.utf16_offset(span.end)?);
507	}
508	}
509	boundaries.insert(0);
510	let boundaries: Vec<u32> = boundaries.into_iter().collect();
511	let mut pending: Option<FormatEdit> = None;
512	let mut edits = Vec::new();
513	for window in boundaries.windows(2) {
514	let (start, end) = (window[0], window[1]);
515	if start == end {
516	continue;
517	}
518	let (set, clear) = attributes(format_in(stored, start)?, format_in(target, start)?, fresh)?;
519	match &mut pending {
520	Some((range, previous_set, previous_clear))
521	if *previous_set == set && *previous_clear == clear && range.end == start =>
522	{
523	range.end = end;
524	}
525	_ => {
526	if let Some(edit) = pending.take() {
527	edits.push(edit);
528	}
529	pending = Some((start..end, set, clear));
530	}
531	}
532	}
533	edits.extend(pending);
534	if target.text().is_empty() {
535	let (set, clear) = attributes(format_in(stored, 0)?, format_in(target, 0)?, fresh)?;
536	edits.push((0..0, set, clear));
537	}
538	edits.retain(|(_, set, clear)| !set.is_empty() || !clear.is_empty());
539	Ok(edits)
540	}
541
542	/// The change turning `current` into `target`; unsupported differences are errors. A value the
543	/// target leaves unset is cleared from the run, as the model's formats are complete.
544	fn attributes(
545	current: &Format,
546	target: &Format,
547	fresh: bool,
548	) -> Result<(Vec<TextAttribute>, Vec<TextProperty>), Error> {
549	let mut out = Vec::new();
550	let mut cleared = Vec::new();
551	macro_rules! boolean {
552	($field:ident, $variant:ident) => {
553	match target.$field {
554	Some(value) if current.$field != Some(value) => {
555	out.push(TextAttribute::$variant(value))
556	}
557	None if current.$field.is_some() => cleared.push(TextProperty::$variant),
558	_ => {}
559	}
560	};
561	}
562	boolean!(bold, Bold);
563	boolean!(italic, Italic);
564	boolean!(underline, Underline);
565	boolean!(strike, Strike);
566	boolean!(superscript, Superscript);
567	boolean!(subscript, Subscript);
568	boolean!(hidden, Hidden);
569	boolean!(hyperlink, Hyperlink);
570	boolean!(hyperlink_label, HyperlinkLabel);
571	boolean!(math, Math);
572	macro_rules! value {
573	($field:ident, $property:ident, $attribute:expr) => {
574	if current.$field != target.$field {
575	match &target.$field {
576	Some(value) => out.push($attribute(value)),
577	None => cleared.push(TextProperty::$property),
578	}
579	}
580	};
581	}
582	let color =
583	|value: u32| (value != 0xff000000).then(|| value.to_le_bytes()[..3].try_into().unwrap());
584	value!(font, Font, |font: &String| TextAttribute::Font(
585	font.clone()
586	));
587	value!(font_size, FontSize, |size: &f32| TextAttribute::FontSize(
588	*size
589	));
590	value!(color, Color, |value: &u32| TextAttribute::Color(color(
591	*value
592	)));
593	value!(highlight, Highlight, |value: &u32| {
594	TextAttribute::Highlight(color(*value))
595	});
596	if current.language != target.language {
597	match target.language {
598	Some(language) => out.push(TextAttribute::Language(language)),
599	None if fresh => {}
600	None => {
601	return Err(invalid("Inherited character formatting cannot be restored"));
602	}
603	}
604	}
605	// An absent value and its stored default are the same formatting.
606	let flag = |a: Option<bool>, b: Option<bool>| a.unwrap_or(false) == b.unwrap_or(false);
607	let points = |a: Option<f32>, b: Option<f32>| a.unwrap_or(0.0) == b.unwrap_or(0.0);
608	let same_rest = flag(current.embedded_object, target.embedded_object)
609	&& current.alignment.unwrap_or(0) == target.alignment.unwrap_or(0)
610	&& flag(current.rtl, target.rtl)
611	&& points(current.space_before, target.space_before)
612	&& points(current.space_after, target.space_after)
613	&& points(current.line_spacing, target.line_spacing)
614	&& points(current.list_spacing, target.list_spacing);
615	if !same_rest {
616	return Err(invalid(
617	"Fields and paragraph spacing cannot be edited through the page model",
618	));
619	}
620	Ok((out, cleared))
621	}
622
623	/// Paragraph formatting a text object stores: alignment, direction, spacing and language.
624	#[derive(Clone, Copy, Debug, Default, PartialEq)]
625	pub(crate) struct ParagraphFields {
626	pub alignment: Option<u8>,
627	pub rtl: Option<bool>,
628	pub space_before: Option<f32>,
629	pub space_after: Option<f32>,
630	pub line_spacing: Option<f32>,
631	pub language: Option<u32>,
632	}
633
634	impl ParagraphFields {
635	pub(crate) fn values(&self) -> Result<Values, Error> {
636	super::properties::paragraph_values(
637	self.alignment,
638	self.rtl,
639	self.space_before,
640	self.space_after,
641	self.line_spacing,
642	self.language,
643	)
644	}
645	}
646
647	/// The paragraph formatting `target` sets throughout that `stored` lacks somewhere.
648	pub(crate) fn paragraph_fields(
649	stored: &Paragraph,
650	target: &Paragraph,
651	) -> Result<ParagraphFields, Error> {
652	let first = format_in(target, 0)?;
653	macro_rules! field {
654	($field:ident) => {{
655	let value = first.$field.unwrap_or_default();
656	(target
657	.spans()
658	.iter()
659	.all(|span| span.format.$field.unwrap_or_default() == value)
660	&& stored
661	.spans()
662	.iter()
663	.any(|span| span.format.$field.unwrap_or_default() != value))
664	.then_some(value)
665	}};
666	}
667	Ok(ParagraphFields {
668	alignment: field!(alignment),
669	rtl: field!(rtl),
670	space_before: field!(space_before),
671	space_after: field!(space_after),
672	line_spacing: field!(line_spacing),
673	// An unset language is the writer's default, not LCID 0, which OneNote never stores
674	// on a text object and which runs without their own language would then read.
675	language: first.language.filter(|value| {
676	target
677	.spans()
678	.iter()
679	.all(|span| span.format.language == Some(*value))
680	&& stored
681	.spans()
682	.iter()
683	.any(|span| span.format.language != Some(*value))
684	}),
685	})
686	}
687
688	/// Whether two tag lists store the same tags.
689	pub(crate) fn same_tags(a: &[Tag], b: &[Tag]) -> bool {
690	let key = |t: &Tag| {
691	(
692	t.definition,
693	t.action_type,
694	t.shape,
695	t.property_status,
696	t.status,
697	t.created,
698	t.completed,
699	t.start,
700	t.due,
701	t.task_id,
702	)
703	};
704	a.len() == b.len() && a.iter().zip(b).all(|(x, y)| key(x) == key(y))
705	}
706
707	/// Whether the writers can split or join this text: ordinary text without generated fields,
708	/// equations or embedded objects.
709	fn ordinary(text: &TextObject) -> bool {
710	text.date_field.is_none()
711	&& !text.text.text().contains('\u{fffc}')
712	&& text
713	.text
714	.spans()
715	.iter()
716	.all(|span| span.format.math != Some(true) && span.format.embedded_object != Some(true))
717	}
718
719	/// Whether a split at `offset` would divide a hyperlink, which the writer refuses.
720	fn divides_link(text: &Paragraph, offset: u32) -> Result<bool, Error> {
721	let byte = text.byte_offset(offset)?;
722	let link = |span: &crate::page::text::Span| span.format.hyperlink == Some(true);
723	let spans = text.spans();
724	let mut start = 0;
725	for (i, span) in spans.iter().enumerate() {
726	if start < byte && byte < span.end {
727	return Ok(link(span));
728	}
729	if byte == span.end && byte > 0 && i + 1 < spans.len() {
730	let next = &spans[i + 1];
731	return Ok(link(span) && link(next) && !text.text()[byte..].starts_with('\u{fddf}'));
732	}
733	start = span.end;
734	}
735	Ok(false)
736	}
737
738	/// A paragraph as `Insert` and `Add` create it: structure and content, without the
739	/// properties their own ops set.
740	fn bare(paragraph: &PageParagraph) -> PageParagraph {
741	let mut stripped = paragraph.clone();
742	stripped.style = None;
743	stripped.lists.clear();
744	stripped.tags.clear();
745	stripped.collapsed = false;
746	stripped.media = Default::default();
747	match &mut stripped.content {
748	ParagraphContent::Text(text) => text.tags.clear(),
749	ParagraphContent::Image(image) => image.tags.clear(),
750	ParagraphContent::Attachment(file) => file.tags.clear(),
751	ParagraphContent::Table(table) => {
752	table.tags.clear();
753	for cell in table.rows.iter_mut().flat_map(|row| &mut row.cells) {
754	cell.paragraphs = cell.paragraphs.iter().map(bare).collect();
755	}
756	}
757	_ => {}
758	}
759	stripped
760	}
761
762	fn bare_cells(cells: &[TableCell]) -> Vec<TableCell> {
763	cells
764	.iter()
765	.map(|cell| TableCell {
766	paragraphs: cell.paragraphs.iter().map(bare).collect(),
767	..cell.clone()
768	})
769	.collect()
770	}
771
772	struct Lowering {
773	ops: Vec<PageOp>,
774	/// The page as the ops so far leave it.
775	current: Page,
776	/// The paragraph after a partial model's range: its container and identity.
777	tail: Option<(ExGuid, ExGuid)>,
778	/// Paragraphs and text objects the ops so far created.
779	created: BTreeSet<ExGuid>,
780	}
781
782	impl Lowering {
783	fn new(current: Page, tail: Option<(ExGuid, ExGuid)>) -> Self {
784	Self {
785	ops: Vec::new(),
786	current,
787	tail,
788	created: BTreeSet::new(),
789	}
790	}
791
792	fn emit(&mut self, op: PageOp) -> Result<(), Error> {
793	model::apply(&mut self.current, &op)?;
794	self.ops.push(op);
795	Ok(())
796	}
797
798	/// Whether the page, as the ops so far leave it, holds `id` as a paragraph, text,
799	/// list node or table part.
800	fn holds(&self, id: ExGuid) -> bool {
801	model::holds(&self.current, id)
802	}
803
804	fn run(
805	mut self,
806	before: &Page,
807	after: &Page,
808	old: &View<'_>,
809	new: &View<'_>,
810	) -> Result<Vec<PageOp>, Error> {
811	validate(before, after, old, new)?;
812	let mut placed: BTreeMap<ExGuid, Vec<ExGuid>> = old.children.clone();
813	let mut consumed = BTreeSet::new();
814	self.split_and_join(old, new, &mut placed, &mut consumed)?;
815	self.place_page(old, new)?;
816	self.place(old, new, &placed)?;
817	self.delete(old, new, &consumed)?;
818	self.levels(new)?;
819	self.equations(new)?;
820	self.date(before, after)?;
821	self.text(new)?;
822	self.styles(after, new)?;
823	self.lists(after, new)?;
824	self.tags(after, new)?;
825	self.media(new)?;
826	self.paragraph_formatting(new)?;
827	self.formatting(old, new)?;
828	self.layout(old, new)?;
829	Ok(self.ops)
830	}
831
832	/// Splits and joins stored paragraphs as OneNote's Enter, Backspace and Delete do.
833	fn split_and_join(
834	&mut self,
835	old: &View<'_>,
836	new: &View<'_>,
837	placed: &mut BTreeMap<ExGuid, Vec<ExGuid>>,
838	consumed: &mut BTreeSet<ExGuid>,
839	) -> Result<(), Error> {
840	// A new paragraph may be split from the stored paragraph nearest before it, whatever
841	// placement or pasted paragraphs the same edit adds between them.
842	let mut splits = Vec::new();
843	for document in new.documents() {
844	let mut left = None;
845	for paragraph in document {
846	if old.paragraphs.contains_key(&paragraph.id) {
847	left = paragraph.text().is_some().then_some(paragraph.id);
848	} else if let Some(left) = left
849	// A new cell arrives with its paragraphs.
850	&& old.children.contains_key(&root(new, paragraph.id))
851	{
852	let container = new.container[&paragraph.id];
853	let at = new.children[&container]
854	.iter()
855	.position(|id| *id == paragraph.id);
856	splits.push(((container, at), left, paragraph.id));
857	}
858	}
859	}
860	splits.sort();
861	let mut split = BTreeSet::new();
862	for (_, left, right) in splits {
863	let (Some(previous), Some(after), Some(next)) =
864	(old.text(left), new.text(left), new.text(right))
865	else {
866	continue;
867	};
868	if split.contains(&left)
869	|| after.id != previous.id
870	|| new.paragraphs[&right].style != old.paragraphs[&left].style
871	|| !ordinary(previous)
872	|| old.title_outlines.contains(&root(old, left))
873	{
874	continue;
875	}
876	let Ok(offset) = after.text.utf16_offset(after.text.text().len()) else {
877	continue;
878	};
879	let length = previous.text.utf16_offset(previous.text.text().len())?;
880	// Splitting at the end only differs from appending a paragraph by the copied
881	// paragraph style; without one, an appended empty paragraph is an insertion.
882	if offset == length && new.paragraphs[&right].style.is_none() {
883	continue;
884	}
885	let (Ok(head), Ok(tail)) = (
886	previous.text.slice(0..offset),
887	previous.text.slice(offset..length),
888	) else {
889	continue;
890	};
891	// An emptied side takes the writer's insertion style, so only its text must agree.
892	let same = |expected: &Paragraph, actual: &Paragraph| {
893	expected.text() == actual.text()
894	&& (expected.text().is_empty() || expected == actual)
895	};
896	if !same(&head, &after.text)
897	|| !same(&tail, &next.text)
898	|| divides_link(&previous.text, offset)?
899	|| old.paragraphs[&left].lists.len() > 251
900	{
901	continue;
902	}
903	// A text object a join moved into the paragraph keeps its identity there.
904	let right_text = if self.holds(next.id) {
905	new_id().map_err(|_| invalid("System random source failed"))?
906	} else {
907	next.id
908	};
909	// The split copies the left paragraph's list nodes in order; a node the model
910	// shares with a stored paragraph stays that paragraph's.
911	let stored_lists = old.paragraphs[&left].lists.len();
912	let model_lists = &new.paragraphs[&right].lists;
913	let mut lists = Vec::new();
914	for i in 0..stored_lists {
915	lists.push(match model_lists.get(i) {
916	Some(list) if model_lists.len() == stored_lists && !self.holds(*list) => *list,
917	_ => new_id().map_err(|_| invalid("System random source failed"))?,
918	});
919	}
920	self.emit(PageOp::Split {
921	text: previous.id,
922	at: offset,
923	paragraph: right,
924	right: right_text,
925	lists,
926	})?;
927	self.created.extend([right, right_text]);
928	split.insert(left);
929	// An earlier split may have carried the left paragraph to its tail.
930	let list = placed
931	.values_mut()
932	.find(|list| list.contains(&left))
933	.unwrap();
934	let at = list.iter().position(|id| *id == left).unwrap();
935	list.insert(at + 1, right);
936	placed.insert(right, placed[&left].clone());
937	placed.insert(left, Vec::new());
938	}
939	for (container, children) in &old.children {
940	if !new.children.contains_key(container) {
941	continue;
942	}
943	for pair in children.windows(2) {
944	let [left, right] = [pair[0], pair[1]];
945	let (Some(previous), Some(after), Some(removed)) =
946	(old.text(left), new.text(left), old.text(right))
947	else {
948	continue;
949	};
950	if new.paragraphs.contains_key(&right)
951	|| !old.children[&left].is_empty()
952	|| !old.children[&right].is_empty()
953	|| removed.text.text().is_empty()
954	|| !ordinary(previous)
955	|| !ordinary(removed)
956	|| old.title_outlines.contains(&root(old, left))
957	{
958	continue;
959	}
960	let mut joined = previous.text.clone();
961	if joined.append(removed.text.clone()).is_err() || joined != after.text {
962	continue;
963	}
964	let adopts_right = previous.text.text().is_empty();
965	if after.id
966	!= if adopts_right {
967	removed.id
968	} else {
969	previous.id
970	}
971	{
972	continue;
973	}
974	self.emit(PageOp::Join {
975	left: previous.id,
976	right: removed.id,
977	})?;
978	consumed.insert(right);
979	placed.get_mut(container).unwrap().retain(|id| *id != right);
980	placed.remove(&right);
981	}
982	}
983	Ok(())
984	}
985
986	/// Adds, changes and orders what the page holds directly: outlines, pictures and ink.
987	fn place_page(&mut self, old: &View<'_>, new: &View<'_>) -> Result<(), Error> {
988	let pictures = |page: &Page| -> BTreeMap<ExGuid, crate::page::Image> {
989	page.objects
990	.iter()
991	.filter_map(|object| match object {
992	PageObject::Image(image) => Some((image.id, image.clone())),
993	_ => None,
994	})
995	.collect()
996	};
997	let stored = pictures(old.page);
998	for (id, image) in pictures(new.page) {
999	let Some(previous) = stored.get(&id) else {
1000	continue;
1001	};
1002	super::content::picture_fixed_fields(previous, &image)?;
1003	if (&previous.layout, &previous.alt) != (&image.layout, &image.alt) {
1004	self.emit(PageOp::Picture {
1005	picture: id,
1006	layout: image.layout.clone(),
1007	alt: image.alt.clone(),
1008	})?;
1009	}
1010	self.set_tags(new.page, id, &image.tags, &previous.tags)?;
1011	}
1012	let files = |page: &Page| -> BTreeMap<ExGuid, crate::page::Attachment> {
1013	page.objects
1014	.iter()
1015	.filter_map(|object| match object {
1016	PageObject::Attachment(file) => Some((file.id, file.clone())),
1017	_ => None,
1018	})
1019	.collect()
1020	};
1021	let stored = files(old.page);
1022	for (id, file) in files(new.page) {
1023	let Some(previous) = stored.get(&id) else {
1024	continue;
1025	};
1026	let (from, to) = (&previous.layout, &file.layout);
1027	if (
1028	from.max_width,
1029	from.max_height,
1030	from.width_set_by_user,
1031	from.reserved_width,
1032	) != (
1033	to.max_width,
1034	to.max_height,
1035	to.width_set_by_user,
1036	to.reserved_width,
1037	) {
1038	return Err(invalid("A file on the page keeps its extent"));
1039	}
1040	if (from.x, from.y) != (to.x, to.y) {
1041	let (Some(x), Some(y)) = (to.x, to.y) else {
1042	return Err(invalid("A file position needs both coordinates"));
1043	};
1044	self.emit(PageOp::Outline {
1045	object: id,
1046	edit: crate::OutlineEdit::Position { x, y },
1047	})?;
1048	}
1049	if (&previous.filename, &previous.source_path, previous.size)
1050	!= (&file.filename, &file.source_path, file.size)
1051	{
1052	self.emit(PageOp::Attachment {
1053	attachment: id,
1054	filename: file.filename.clone(),
1055	source_path: file.source_path.clone(),
1056	size: file.size,
1057	})?;
1058	}
1059	self.set_tags(new.page, id, &file.tags, &previous.tags)?;
1060	}
1061	let inks = |page: &Page| -> BTreeMap<ExGuid, crate::page::Ink> {
1062	page.objects
1063	.iter()
1064	.filter_map(|object| match object {
1065	PageObject::Ink(ink) => Some((ink.id, ink.clone())),
1066	_ => None,
1067	})
1068	.collect()
1069	};
1070	let stored = inks(old.page);
1071	for (id, ink) in inks(new.page) {
1072	if let Some(previous) = stored.get(&id)
1073	&& *previous != ink
1074	{
1075	self.strokes(previous, &ink)?;
1076	}
1077	}
1078	let title = |page: &Page, id: ExGuid| {
1079	page.objects
1080	.iter()
1081	.any(|object| matches!(object, PageObject::Title(title) if title.id == id))
1082	};
1083	let survivors: Vec<ExGuid> = old
1084	.page_children
1085	.iter()
1086	.copied()
1087	.filter(|id| {
1088	!title(old.page, *id) && new.page.objects.iter().any(|object| object.id() == *id)
1089	})
1090	.collect();
1091	let after: Vec<&PageObject> = new
1092	.page
1093	.objects
1094	.iter()
1095	.filter(|object| !title(new.page, object.id()))
1096	.collect();
1097	let order: Vec<ExGuid> = after.iter().map(|object| object.id()).collect();
1098	let kept = kept_set(&survivors, &order, |id| {
1099	new.outlines.contains_key(&id) && !new.title_outlines.contains(&id)
1100	})?;
1101	let mut next = None;
1102	for object in after.iter().rev() {
1103	let id = object.id();
1104	let stored = old.page_children.contains(&id);
1105	if !stored {
1106	if new.title_outlines.contains(&id) {
1107	return Err(invalid("Title outlines cannot be added"));
1108	}
1109	let added = match object {
1110	PageObject::Outline(outline) => {
1111	if outline
1112	.paragraphs
1113	.iter()
1114	.any(|p| old.paragraphs.contains_key(&p.id))
1115	{
1116	return Err(invalid(
1117	"A new outline holds new paragraphs; move stored ones after",
1118	));
1119	}
1120	self.created.extend(model::identities(&outline.paragraphs));
1121	PageObject::Outline(Outline {
1122	paragraphs: outline.paragraphs.iter().map(bare).collect(),
1123	..(*outline).clone()
1124	})
1125	}
1126	PageObject::Image(image) => PageObject::Image(crate::page::Image {
1127	tags: Vec::new(),
1128	..image.clone()
1129	}),
1130	PageObject::Attachment(file) => {
1131	PageObject::Attachment(crate::page::Attachment {
1132	tags: Vec::new(),
1133	..file.clone()
1134	})
1135	}
1136	PageObject::Ink(_) => (*object).clone(),
1137	PageObject::Title(_) | PageObject::Unsupported(_) => {
1138	return Err(invalid(
1139	"Titles and unsupported objects cannot be edited through the page model",
1140	));
1141	}
1142	};
1143	self.emit(PageOp::Add {
1144	object: added,
1145	before: next,
1146	})?;
1147	let tags = match object {
1148	PageObject::Image(image) => image.tags.as_slice(),
1149	PageObject::Attachment(file) => file.tags.as_slice(),
1150	_ => &[],
1151	};
1152	self.set_tags(new.page, id, tags, &[])?;
1153	} else if !kept.contains(&id) {
1154	self.emit(PageOp::Move {
1155	object: id,
1156	parent: None,
1157	before: next,
1158	})?;
1159	}
1160	next = Some(id);
1161	}
1162	Ok(())
1163	}
1164
1165	/// Inserts new paragraphs and moves stored ones to the containers and order the model
1166	/// gives them, then edits the stored tables and paragraph content.
1167	fn place(
1168	&mut self,
1169	old: &View<'_>,
1170	new: &View<'_>,
1171	placed: &BTreeMap<ExGuid, Vec<ExGuid>>,
1172	) -> Result<(), Error> {
1173	let mut inserted: BTreeSet<ExGuid> = BTreeSet::new();
1174	// New outlines and cells, whose paragraphs arrive with them.
1175	let arriving: BTreeSet<ExGuid> = new
1176	.children
1177	.keys()
1178	.filter(|id| {
1179	!old.children.contains_key(id)
1180	&& !new.paragraphs.contains_key(id)
1181	&& !new.external.contains(id)
1182	})
1183	.copied()
1184	.collect();
1185	for container in new.containers() {
1186	if arriving.contains(&root(new, container)) {
1187	continue;
1188	}
1189	let Some(children) = new.children.get(&container) else {
1190	continue;
1191	};
1192	let current: Vec<ExGuid> = placed
1193	.get(&container)
1194	.map(|list| {
1195	list.iter()
1196	.copied()
1197	.filter(|id| new.paragraphs.contains_key(id))
1198	.collect()
1199	})
1200	.unwrap_or_default();
1201	let kept = kept_set(&current, children, |_| true)?;
1202	let tail = self
1203	.tail
1204	.filter(|(parent, _)| *parent == container)
1205	.map(|(_, id)| id);
1206	let mut next = tail;
1207	let mut run: Vec<ExGuid> = Vec::new();
1208	for id in children.iter().rev() {
1209	let fresh = !old.paragraphs.contains_key(id) && !self.created.contains(id);
1210	if fresh && !inserted.contains(id) {
1211	run.push(*id);
1212	continue;
1213	}
1214	self.insert(container, next, &mut run, new, &mut inserted)?;
1215	if !kept.contains(id) && !inserted.contains(id) {
1216	self.emit(PageOp::Move {
1217	object: *id,
1218	parent: Some(container),
1219	before: next,
1220	})?;
1221	}
1222	next = Some(*id);
1223	}
1224	self.insert(container, next, &mut run, new, &mut inserted)?;
1225	}
1226	self.tables(old, new)?;
1227	self.content(old, new)?;
1228	Ok(())
1229	}
1230
1231	/// Inserts `run`, new siblings in reverse order, with their new descendants.
1232	fn insert(
1233	&mut self,
1234	container: ExGuid,
1235	before: Option<ExGuid>,
1236	run: &mut Vec<ExGuid>,
1237	new: &View<'_>,
1238	inserted: &mut BTreeSet<ExGuid>,
1239	) -> Result<(), Error> {
1240	if run.is_empty() {
1241	return Ok(());
1242	}
1243	run.reverse();
1244	let mut paragraphs = Vec::new();
1245	let mut pending: Vec<ExGuid> = run.drain(..).rev().collect();
1246	while let Some(id) = pending.pop() {
1247	let paragraph = new.paragraphs[&id];
1248	paragraphs.push(bare(paragraph));
1249	inserted.insert(id);
1250	self.created.insert(id);
1251	if let Some(text) = paragraph.text() {
1252	self.created.insert(text.id);
1253	}
1254	if let ParagraphContent::Table(table) = &paragraph.content {
1255	for cell in table.rows.iter().flat_map(|row| &row.cells) {
1256	self.created.extend(model::identities(&cell.paragraphs));
1257	}
1258	}
1259	// New children follow their parent; stored ones move there later.
1260	pending.extend(
1261	new.children[&id]
1262	.iter()
1263	.rev()
1264	.filter(|child| !self.holds(**child) && !inserted.contains(child)),
1265	);
1266	}
1267	self.emit(PageOp::Insert {
1268	container,
1269	before,
1270	paragraphs,
1271	})
1272	}
1273
1274	/// Row, column, width, border and cell edits of stored tables.
1275	fn tables(&mut self, old: &View<'_>, new: &View<'_>) -> Result<(), Error> {
1276	let stored: BTreeMap<ExGuid, &Table> = old
1277	.paragraphs
1278	.values()
1279	.filter_map(|p| match &p.content {
1280	ParagraphContent::Table(table) => Some((table.id, table)),
1281	_ => None,
1282	})
1283	.collect();
1284	for paragraph in new.paragraphs.values() {
1285	let ParagraphContent::Table(table) = &paragraph.content else {
1286	continue;
1287	};
1288	let Some(previous) = stored.get(&table.id) else {
1289	continue;
1290	};
1291	self.table(previous, table)?;
1292	let cells: BTreeMap<ExGuid, &TableCell> = previous
1293	.rows
1294	.iter()
1295	.flat_map(|row| &row.cells)
1296	.map(|cell| (cell.id, cell))
1297	.collect();
1298	for cell in table.rows.iter().flat_map(|row| &row.cells) {
1299	let Some(before) = cells.get(&cell.id) else {
1300	continue;
1301	};
1302	if (cell.shading, &cell.indents) != (before.shading, &before.indents) {
1303	self.emit(PageOp::Table {
1304	table: table.id,
1305	edit: TableEdit::Cell {
1306	cell: cell.id,
1307	shading: cell.shading,
1308	indents: cell.indents.clone(),
1309	},
1310	})?;
1311	}
1312	}
1313	}
1314	Ok(())
1315	}
1316
1317	/// The row and column edits turning stored table `before` into `after`.
1318	fn table(&mut self, before: &Table, after: &Table) -> Result<(), Error> {
1319	let id = after.id;
1320	let unsupported = || invalid("Table rows and cells keep their order; add or remove them");
1321	let old_rows: Vec<ExGuid> = before.rows.iter().map(|row| row.id).collect();
1322	let new_rows: Vec<ExGuid> = after.rows.iter().map(|row| row.id).collect();
1323	let kept_rows: Vec<ExGuid> = old_rows
1324	.iter()
1325	.copied()
1326	.filter(|row| new_rows.contains(row))
1327	.collect();
1328	if new_rows
1329	.iter()
1330	.filter(|row| old_rows.contains(row))
1331	.ne(kept_rows.iter())
1332	{
1333	return Err(unsupported());
1334	}
1335	// The column pattern every kept row shares: which stored cells stay, which are new.
1336	let mut deleted: Option<Vec<u32>> = None;
1337	let mut added: Option<Vec<u32>> = None;
1338	for row in &kept_rows {
1339	let old_cells: Vec<ExGuid> = before
1340	.rows
1341	.iter()
1342	.find(|r| r.id == *row)
1343	.unwrap()
1344	.cells
1345	.iter()
1346	.map(|cell| cell.id)
1347	.collect();
1348	let new_cells: Vec<ExGuid> = after
1349	.rows
1350	.iter()
1351	.find(|r| r.id == *row)
1352	.unwrap()
1353	.cells
1354	.iter()
1355	.map(|cell| cell.id)
1356	.collect();
1357	let gone: Vec<u32> = (0..old_cells.len() as u32)
1358	.filter(|i| !new_cells.contains(&old_cells[*i as usize]))
1359	.collect();
1360	let fresh: Vec<u32> = (0..new_cells.len() as u32)
1361	.filter(|i| !old_cells.contains(&new_cells[*i as usize]))
1362	.collect();
1363	if old_cells
1364	.iter()
1365	.filter(|cell| new_cells.contains(cell))
1366	.ne(new_cells.iter().filter(|cell| old_cells.contains(cell)))
1367	|| deleted.as_ref().is_some_and(|known| *known != gone)
1368	|| added.as_ref().is_some_and(|known| *known != fresh)
1369	{
1370	return Err(unsupported());
1371	}
1372	deleted = Some(gone);
1373	added = Some(fresh);
1374	}
1375	let (deleted, added) = (deleted.unwrap_or_default(), added.unwrap_or_default());
1376	if kept_rows.is_empty() && before.columns.len() != after.columns.len() {
1377	return Err(unsupported());
1378	}
1379	for row in &old_rows {
1380	if !new_rows.contains(row) && !kept_rows.is_empty() {
1381	self.emit(PageOp::Table {
1382	table: id,
1383	edit: TableEdit::DeleteRow(*row),
1384	})?;
1385	}
1386	}
1387	for at in deleted.iter().rev() {
1388	self.emit(PageOp::Table {
1389	table: id,
1390	edit: TableEdit::DeleteColumn(*at),
1391	})?;
1392	}
1393	for at in &added {
1394	let cells = kept_rows
1395	.iter()
1396	.map(|row| {
1397	let row = after.rows.iter().find(|r| r.id == *row).unwrap();
1398	bare_cells(&row.cells[*at as usize..=*at as usize]).remove(0)
1399	})
1400	.collect::<Vec<_>>();
1401	for cell in &cells {
1402	self.created.extend(model::identities(&cell.paragraphs));
1403	}
1404	self.emit(PageOp::Table {
1405	table: id,
1406	edit: TableEdit::Column {
1407	at: *at,
1408	width: after.columns[*at as usize].width,
1409	cells,
1410	},
1411	})?;
1412	}
1413	// New rows, each run before the stored row that follows it.
1414	let mut run = Vec::new();
1415	let mut next = None;
1416	for row in after.rows.iter().rev() {
1417	if old_rows.contains(&row.id) {
1418	self.rows(id, next, &mut run)?;
1419	next = Some(row.id);
1420	} else {
1421	run.push(row.clone());
1422	}
1423	}
1424	self.rows(id, next, &mut run)?;
1425	if kept_rows.is_empty() {
1426	for row in &old_rows {
1427	self.emit(PageOp::Table {
1428	table: id,
1429	edit: TableEdit::DeleteRow(*row),
1430	})?;
1431	}
1432	}
1433	let current = model::table(&self.current, id)
1434	.ok_or_else(|| invalid("A table is missing after row edits"))?;
1435	if current.columns != after.columns {
1436	self.emit(PageOp::Table {
1437	table: id,
1438	edit: TableEdit::Columns(after.columns.clone()),
1439	})?;
1440	}
1441	let current = model::table(&self.current, id).unwrap();
1442	if current.borders != after.borders
1443	&& let Some(borders) = after.borders
1444	{
1445	self.emit(PageOp::Table {
1446	table: id,
1447	edit: TableEdit::Borders(borders),
1448	})?;
1449	}
1450	Ok(())
1451	}
1452
1453	fn rows(
1454	&mut self,
1455	table: ExGuid,
1456	before: Option<ExGuid>,
1457	run: &mut Vec<crate::page::TableRow>,
1458	) -> Result<(), Error> {
1459	if run.is_empty() {
1460	return Ok(());
1461	}
1462	run.reverse();
1463	let rows: Vec<crate::page::TableRow> = run
1464	.drain(..)
1465	.map(|row| crate::page::TableRow {
1466	id: row.id,
1467	cells: bare_cells(&row.cells),
1468	})
1469	.collect();
1470	for cell in rows.iter().flat_map(|row| &row.cells) {
1471	self.created.extend(model::identities(&cell.paragraphs));
1472	}
1473	self.emit(PageOp::Table {
1474	table,
1475	edit: TableEdit::Rows { before, rows },
1476	})
1477	}
1478
1479	/// Edits of stored pictures, ink and attachments that paragraphs hold.
1480	fn content(&mut self, old: &View<'_>, new: &View<'_>) -> Result<(), Error> {
1481	for (id, paragraph) in &new.paragraphs {
1482	let Some(previous) = old.paragraphs.get(id) else {
1483	continue;
1484	};
1485	match (&previous.content, &paragraph.content) {
1486	(ParagraphContent::Image(stored), ParagraphContent::Image(image))
1487	if stored != image =>
1488	{
1489	self.emit(PageOp::Picture {
1490	picture: image.id,
1491	layout: image.layout.clone(),
1492	alt: image.alt.clone(),
1493	})?;
1494	}
1495	(ParagraphContent::Ink(stored), ParagraphContent::Ink(ink)) if stored != ink => {
1496	self.strokes(stored, ink)?;
1497	}
1498	(
1499	ParagraphContent::Attachment(stored),
1500	ParagraphContent::Attachment(attachment),
1501	) if stored != attachment => {
1502	self.emit(PageOp::Attachment {
1503	attachment: attachment.id,
1504	filename: attachment.filename.clone(),
1505	source_path: attachment.source_path.clone(),
1506	size: attachment.size,
1507	})?;
1508	}
1509	_ => {}
1510	}
1511	}
1512	Ok(())
1513	}
1514
1515	fn strokes(&mut self, stored: &crate::page::Ink, ink: &crate::page::Ink) -> Result<(), Error> {
1516	let placed = |layout: &crate::document::Layout| crate::document::Layout {
1517	x: None,
1518	y: None,
1519	..layout.clone()
1520	};
1521	if placed(&stored.layout) != placed(&ink.layout) || stored.groups != ink.groups {
1522	return Err(invalid("Ink size and groups stay as stored"));
1523	}
1524	if (stored.layout.x, stored.layout.y) != (ink.layout.x, ink.layout.y) {
1525	let (Some(x), Some(y)) = (ink.layout.x, ink.layout.y) else {
1526	return Err(invalid("An ink position needs both coordinates"));
1527	};
1528	self.emit(PageOp::Outline {
1529	object: ink.id,
1530	edit: crate::OutlineEdit::Position { x, y },
1531	})?;
1532	if stored.strokes == ink.strokes {
1533	return Ok(());
1534	}
1535	}
1536	let mut add = Vec::new();
1537	for stroke in &ink.strokes {
1538	match stored.strokes.iter().find(|s| s.id == stroke.id) {
1539	Some(previous) if previous == stroke => {}
1540	Some(_) => return Err(invalid("A stored stroke keeps its path and pen")),
1541	None => add.push(stroke.clone()),
1542	}
1543	}
1544	let remove: Vec<ExGuid> = stored
1545	.strokes
1546	.iter()
1547	.filter(|stroke| !ink.strokes.iter().any(|s| s.id == stroke.id))
1548	.map(|stroke| stroke.id)
1549	.collect();
1550	if ink.strokes.iter().map(|s| s.id).ne(stored
1551	.strokes
1552	.iter()
1553	.filter(|s| !remove.contains(&s.id))
1554	.map(|s| s.id)
1555	.chain(add.iter().map(|s| s.id)))
1556	{
1557	return Err(invalid("Stored strokes keep their order; new ones follow"));
1558	}
1559	self.emit(PageOp::Strokes {
1560	ink: ink.id,
1561	add,
1562	remove,
1563	})
1564	}
1565
1566	fn delete(
1567	&mut self,
1568	old: &View<'_>,
1569	new: &View<'_>,
1570	consumed: &BTreeSet<ExGuid>,
1571	) -> Result<(), Error> {
1572	let removed_outline =
1573	|id: ExGuid| old.outlines.contains_key(&id) && !new.outlines.contains_key(&id);
1574	for id in old.paragraphs.keys() {
1575	if new.paragraphs.contains_key(id) || consumed.contains(id) {
1576	continue;
1577	}
1578	let mut ancestor = old.container[id];
1579	let mut covered = false;
1580	// A surviving ancestor is placed where the model says, carrying this paragraph along.
1581	while !new.paragraphs.contains_key(&ancestor) {
1582	if removed_outline(ancestor)
1583	|| (old.paragraphs.contains_key(&ancestor) && !consumed.contains(&ancestor))
1584	|| (old.children.contains_key(&ancestor)
1585	&& !old.paragraphs.contains_key(&ancestor)
1586	&& !old.outlines.contains_key(&ancestor)
1587	&& !new.children.contains_key(&ancestor)
1588	&& !old.external.contains(&ancestor))
1589	{
1590	covered = true;
1591	break;
1592	}
1593	match old.container.get(&ancestor) {
1594	Some(parent) => ancestor = *parent,
1595	None => break,
1596	}
1597	}
1598	if !covered {
1599	self.emit(PageOp::Delete { object: *id })?;
1600	}
1601	}
1602	let kept: BTreeSet<ExGuid> = new.page.objects.iter().map(PageObject::id).collect();
1603	for object in &old.page.objects {
1604	if matches!(
1605	object,
1606	PageObject::Image(_) | PageObject::Attachment(_) | PageObject::Ink(_)
1607	) && !kept.contains(&object.id())
1608	{
1609	self.emit(PageOp::Delete {
1610	object: object.id(),
1611	})?;
1612	}
1613	}
1614	for id in old.outlines.keys() {
1615	if removed_outline(*id) {
1616	if old.title_outlines.contains(id) {
1617	return Err(invalid("Title outlines cannot be removed"));
1618	}
1619	self.emit(PageOp::Delete { object: *id })?;
1620	}
1621	}
1622	Ok(())
1623	}
1624
1625	/// Gives paragraphs the levels the model does, parents first.
1626	fn levels(&mut self, new: &View<'_>) -> Result<(), Error> {
1627	for document in new.documents() {
1628	for paragraph in document {
1629	let current = model::paragraph(&self.current, paragraph.id)
1630	.ok_or_else(|| invalid("A paragraph is missing after structural edits"))?;
1631	if current.level != paragraph.level {
1632	self.emit(PageOp::Level {
1633	paragraph: paragraph.id,
1634	level: paragraph.level,
1635	})?;
1636	}
1637	}
1638	}
1639	Ok(())
1640	}
1641
1642	fn equations(&mut self, new: &View<'_>) -> Result<(), Error> {
1643	for (id, paragraph) in &new.paragraphs {
1644	let Some(text) = paragraph.text() else {
1645	continue;
1646	};
1647	let stored = model::paragraph(&self.current, *id).and_then(|p| p.text().cloned());
1648	// Deleting an equation leaves no math in the model, but its stored runs are still math.
1649	if !crate::page::Math::is_equation(&text.text)
1650	&& !stored
1651	.as_ref()
1652	.is_some_and(|stored| crate::page::Math::is_equation(&stored.text))
1653	{
1654	continue;
1655	}
1656	let stored = stored
1657	.ok_or_else(|| invalid("An equation paragraph is missing after placement"))?;
1658	if stored.text != text.text {
1659	self.emit(PageOp::Equation {
1660	text: stored.id,
1661	math: text.text.clone(),
1662	})?;
1663	}
1664	}
1665	Ok(())
1666	}
1667
1668	/// The page's date, with every date and time field of the title showing it.
1669	fn date(&mut self, before: &Page, after: &Page) -> Result<(), Error> {
1670	let fields: Vec<(ExGuid, String)> = model::date_fields(after)
1671	.into_iter()
1672	.map(|text| (text.id, text.text.text().to_owned()))
1673	.collect();
1674	let shown = fields.iter().all(|(id, shown)| {
1675	model::paragraph_text(&self.current, *id).is_some_and(|text| text.text.text() == shown)
1676	});
1677	if before.color != after.color {
1678	self.emit(PageOp::Color(after.color))?;
1679	}
1680	if before.rule_lines != after.rule_lines {
1681	self.emit(PageOp::RuleLines(after.rule_lines))?;
1682	}
1683	if before.created == after.created && shown {
1684	return Ok(());
1685	}
1686	let created = after
1687	.created
1688	.ok_or_else(|| invalid("A page date cannot be removed"))?;
1689	self.emit(PageOp::Date { created, fields })
1690	}
1691
1692	fn text(&mut self, new: &View<'_>) -> Result<(), Error> {
1693	for (id, paragraph) in &new.paragraphs {
1694	let Some(text) = paragraph.text() else {
1695	continue;
1696	};
1697	let Some(stored) = model::paragraph(&self.current, *id).and_then(|p| p.text().cloned())
1698	else {
1699	return Err(invalid("A paragraph is missing after structural edits"));
1700	};
1701	if stored.id != text.id {
1702	return Err(invalid("Text object identities cannot change"));
1703	}
1704	if stored.text.text() == text.text.text() {
1705	continue;
1706	}
1707	let (range, with) = text_edit(stored.text.text(), text.text.text())?;
1708	self.emit(PageOp::Text {
1709	text: stored.id,
1710	range,
1711	with,
1712	})?;
1713	}
1714	Ok(())
1715	}
1716
1717	fn styles(&mut self, after: &Page, new: &View<'_>) -> Result<(), Error> {
1718	for (id, paragraph) in &new.paragraphs {
1719	let current = model::paragraph(&self.current, *id)
1720	.ok_or_else(|| invalid("A paragraph is missing after text edits"))?;
1721	let Some(style) = paragraph.style else {
1722	if current.style.is_some() {
1723	self.emit(PageOp::Unstyle { paragraph: *id })?;
1724	}
1725	continue;
1726	};
1727	if current.style == Some(style) {
1728	continue;
1729	}
1730	if paragraph.text().is_none() {
1731	return Err(invalid("Only text paragraphs take a paragraph style"));
1732	}
1733	let definition = after
1734	.definitions
1735	.get(&style)
1736	.ok_or_else(|| invalid("A paragraph references a missing style definition"))?;
1737	self.emit(PageOp::Style {
1738	paragraph: *id,
1739	style,
1740	definition: definition.clone(),
1741	})?;
1742	}
1743	Ok(())
1744	}
1745
1746	/// Gives each paragraph the list nodes its model references; one another paragraph
1747	/// owns is copied, as native list nodes belong to one paragraph.
1748	fn lists(&mut self, after: &Page, new: &View<'_>) -> Result<(), Error> {
1749	for (id, paragraph) in &new.paragraphs {
1750	let current = model::paragraph(&self.current, *id)
1751	.ok_or_else(|| invalid("A paragraph is missing after text edits"))?;
1752	let same = paragraph.lists.len() == current.lists.len()
1753	&& paragraph
1754	.lists
1755	.iter()
1756	.zip(&current.lists)
1757	.all(|(model, node)| {
1758	model == node
1759	&& after.definitions.get(model) == self.current.definitions.get(node)
1760	});
1761	if same {
1762	continue;
1763	}
1764	let own = current.lists.clone();
1765	let mut lists = Vec::new();
1766	for list in &paragraph.lists {
1767	let definition = after
1768	.definitions
1769	.get(list)
1770	.ok_or_else(|| invalid("A paragraph references a missing list definition"))?;
1771	let node = if own.contains(list) || !model::owns_list(&self.current, *list) {
1772	*list
1773	} else {
1774	new_id().map_err(|_| invalid("System random source failed"))?
1775	};
1776	lists.push((node, definition.clone()));
1777	}
1778	self.emit(PageOp::List {
1779	paragraph: *id,
1780	lists,
1781	})?;
1782	}
1783	Ok(())
1784	}
1785
1786	fn tags(&mut self, after: &Page, new: &View<'_>) -> Result<(), Error> {
1787	for (id, paragraph) in &new.paragraphs {
1788	let current = model::paragraph(&self.current, *id)
1789	.ok_or_else(|| invalid("A paragraph is missing after text edits"))?
1790	.clone();
1791	let mut targets = vec![(*id, &paragraph.tags, current.tags.clone())];
1792	match (&paragraph.content, &current.content) {
1793	(ParagraphContent::Text(text), ParagraphContent::Text(stored)) => {
1794	targets.push((text.id, &text.tags, stored.tags.clone()))
1795	}
1796	(ParagraphContent::Table(table), ParagraphContent::Table(stored)) => {
1797	targets.push((table.id, &table.tags, stored.tags.clone()))
1798	}
1799	(ParagraphContent::Image(image), ParagraphContent::Image(stored)) => {
1800	targets.push((image.id, &image.tags, stored.tags.clone()))
1801	}
1802	(ParagraphContent::Attachment(file), ParagraphContent::Attachment(stored)) => {
1803	targets.push((file.id, &file.tags, stored.tags.clone()))
1804	}
1805	_ => {}
1806	}
1807	for (target, tags, stored) in targets {
1808	self.set_tags(after, target, tags, &stored)?;
1809	}
1810	}
1811	Ok(())
1812	}
1813
1814	/// Emits the op giving `target` `tags` where it stores others.
1815	fn set_tags(
1816	&mut self,
1817	after: &Page,
1818	target: ExGuid,
1819	tags: &[Tag],
1820	stored: &[Tag],
1821	) -> Result<(), Error> {
1822	if same_tags(tags, stored) {
1823	return Ok(());
1824	}
1825	let mut definitions = Vec::new();
1826	for tag in tags {
1827	let Some(definition) = tag.definition else {
1828	continue;
1829	};
1830	if let Some(model) = after.definitions.get(&definition)
1831	&& !definitions.iter().any(|(id, _)| *id == definition)
1832	{
1833	definitions.push((definition, model.clone()));
1834	}
1835	}
1836	self.emit(PageOp::Tags {
1837	target,
1838	tags: tags.to_vec(),
1839	definitions,
1840	})
1841	}
1842
1843	fn media(&mut self, new: &View<'_>) -> Result<(), Error> {
1844	for (id, paragraph) in &new.paragraphs {
1845	let current = model::paragraph(&self.current, *id)
1846	.ok_or_else(|| invalid("A paragraph is missing after text edits"))?;
1847	if current.media != paragraph.media {
1848	self.emit(PageOp::Media {
1849	paragraph: *id,
1850	media: paragraph.media.clone(),
1851	})?;
1852	}
1853	}
1854	Ok(())
1855	}
1856
1857	fn paragraph_formatting(&mut self, new: &View<'_>) -> Result<(), Error> {
1858	for (id, paragraph) in &new.paragraphs {
1859	let Some(text) = paragraph.text() else {
1860	continue;
1861	};
1862	let stored = model::paragraph(&self.current, *id)
1863	.and_then(|p| p.text().cloned())
1864	.ok_or_else(|| invalid("A paragraph is missing after text edits"))?;
1865	let fields = paragraph_fields(&stored.text, &text.text)?;
1866	if fields == ParagraphFields::default() {
1867	continue;
1868	}
1869	if text.date_field.is_some() {
1870	return Err(invalid(
1871	"Generated title fields cannot be formatted as ordinary text",
1872	));
1873	}
1874	self.emit(PageOp::Paragraph {
1875	paragraph: *id,
1876	alignment: fields.alignment,
1877	rtl: fields.rtl,
1878	space_before: fields.space_before,
1879	space_after: fields.space_after,
1880	line_spacing: fields.line_spacing,
1881	language: fields.language,
1882	})?;
1883	}
1884	Ok(())
1885	}
1886
1887	fn formatting(&mut self, old: &View<'_>, new: &View<'_>) -> Result<(), Error> {
1888	let stored_texts: BTreeSet<ExGuid> = old
1889	.paragraphs
1890	.values()
1891	.filter_map(|p| Some(p.text()?.id))
1892	.collect();
1893	for (id, paragraph) in &new.paragraphs {
1894	let Some(text) = paragraph.text() else {
1895	continue;
1896	};
1897	let stored = model::paragraph(&self.current, *id)
1898	.and_then(|p| p.text().cloned())
1899	.ok_or_else(|| invalid("A paragraph is missing after text edits"))?;
1900	if stored.text.text() != text.text.text() {
1901	return Err(invalid("Text edits did not converge on the model"));
1902	}
1903	let fresh = !stored_texts.contains(&text.id);
1904	let edits = format_edits(&stored.text, &text.text, fresh)?;
1905	// Math runs refuse formatting, so a style that restyled them is undone whole.
1906	let math = |at: u32| {
1907	stored
1908	.text
1909	.format_at(at + 1)
1910	.is_ok_and(|format| format.math == Some(true))
1911	};
1912	if edits.iter().any(|(range, ..)| range.clone().any(math)) {
1913	self.emit(PageOp::Equation {
1914	text: stored.id,
1915	math: text.text.clone(),
1916	})?;
1917	continue;
1918	}
1919	for (range, set, clear) in edits {
1920	self.emit(PageOp::Format {
1921	text: stored.id,
1922	range,
1923	set,
1924	clear,
1925	})?;
1926	}
1927	}
1928	Ok(())
1929	}
1930
1931	fn layout(&mut self, old: &View<'_>, new: &View<'_>) -> Result<(), Error> {
1932	for (id, paragraph) in &new.paragraphs {
1933	let current = model::paragraph(&self.current, *id)
1934	.ok_or_else(|| invalid("A paragraph is missing after text edits"))?;
1935	if current.collapsed != paragraph.collapsed {
1936	self.emit(PageOp::Outline {
1937	object: *id,
1938	edit: crate::OutlineEdit::Collapsed(paragraph.collapsed),
1939	})?;
1940	}
1941	}
1942	for (id, outline) in &new.outlines {
1943	if new.title_outlines.contains(id) || !old.outlines.contains_key(id) {
1944	continue;
1945	}
1946	let stored = model::outline(&self.current, *id)
1947	.ok_or_else(|| invalid("An outline is missing after text edits"))?;
1948	let (stored_position, stored_width) = (
1949	(stored.layout.x, stored.layout.y),
1950	(stored.layout.max_width, stored.layout.width_set_by_user),
1951	);
1952	if (outline.layout.x, outline.layout.y) != stored_position {
1953	let (Some(x), Some(y)) = (outline.layout.x, outline.layout.y) else {
1954	return Err(invalid("An outline position needs both coordinates"));
1955	};
1956	self.emit(PageOp::Outline {
1957	object: *id,
1958	edit: crate::OutlineEdit::Position { x, y },
1959	})?;
1960	}
1961	if (outline.layout.max_width, outline.layout.width_set_by_user) != stored_width {
1962	let Some(points) = outline.layout.max_width else {
1963	return Err(invalid("An outline width cannot be removed"));
1964	};
1965	self.emit(PageOp::Outline {
1966	object: *id,
1967	edit: crate::OutlineEdit::Width {
1968	points,
1969	user_set: outline.layout.width_set_by_user == Some(true),
1970	},
1971	})?;
1972	}
1973	}
1974	Ok(())
1975	}
1976	}
1977
1978	/// The outline or cell a paragraph of `view` lies in.
1979	fn root(view: &View<'_>, paragraph: ExGuid) -> ExGuid {
1980	let mut at = paragraph;
1981	while let Some(parent) = view.container.get(&at) {
1982	at = *parent;
1983	}
1984	at
1985	}