clover's git

snowbound

1	//! Rebasing queued edits onto a changed remote section. Each op replays on the remote
2	//! section when the objects it reads are as the base image had them; text ops on a text
3	//! the remote also changed shift past the remote's changes when they stay clear of them;
4	//! a move, deletion or outline setting the remote already made is dropped as done.
5	//! An op on a page the remote changed where it did is dropped, with every later op naming
6	//! the objects it named, and the page conflicts: as OneNote 2010 does, the remote's version
7	//! stays the page and the local one becomes a conflict page under it (`conflict_page`).
8	//! Page-list edits merge as OneNote 2010 merges page series: a page the remote moved keeps
9	//! the remote's place, and a page the queue placed goes before the next page in the queue's
10	//! order the remote left in place (`corpus/conflict-page/native-pages`, `native-restore`).
11	//! Objects the queue itself created are not in the base, so nothing remote can have
12	//! changed them.
13
14	use crate::{PendingEdit, Result};
15	use onestore::{
16	ExGuid, OutlineEdit, PageCreation, PageEdit, PagePosition, Section,
17	document::{Format, Layout, Tag},
18	op::{Edit, Op, OpError, PageOp, SectionOp, TableEdit},
19	page::{
20	Attachment, Image, Ink, MediaIndex, Outline, Page, PageObject, PageParagraph, Paragraph,
21	ParagraphContent, TableColumn, TextObject, Unsupported,
22	},
23	};
24	use std::{
25	collections::{BTreeMap, BTreeSet},
26	ops::Range,
27	};
28
29	/// The remote changed what an op reads: the op does not replay.
30	struct Conflicting;
31
32	/// The queue replayed on the remote section.
33	pub(crate) struct Merged {
34	/// Edits whose ops changed. An edit whose ops were all dropped stays, empty, to be
35	/// published and acknowledged with its batch.
36	pub rewritten: Vec<(u64, Edit)>,
37	/// Pages whose local version the remote could not take, with who made the first edit
38	/// that did not replay and the objects the dropped ops named.
39	pub conflicts: BTreeMap<ExGuid, (String, BTreeSet<ExGuid>)>,
40	/// Pages the base listed that the remote moved (`moved`).
41	pub moved: BTreeSet<ExGuid>,
42	}
43
44	/// Replays `edits` on `new`, the remote section; `old` is the base they were made on.
45	/// Ops on the pages in `converged`, which the remote holds as the edits leave them, are done.
46	pub(crate) fn rebase(
47	old: &mut Section<'_>,
48	new: &mut Section<'_>,
49	edits: &[PendingEdit],
50	converged: &BTreeSet<ExGuid>,
51	) -> Result<Merged> {
52	let before: BTreeMap<ExGuid, ExGuid> = old.revisions().collect();
53	let after: BTreeMap<ExGuid, ExGuid> = new.revisions().collect();
54	let orders = (order(old)?, order(new)?);
55	let mut state = Replay {
56	before,
57	after,
58	local: orders.0.clone(),
59	moved: moved(old, new)?,
60	orders,
61	created: BTreeSet::new(),
62	diffs: BTreeMap::new(),
63	};
64	let mut merged = Merged {
65	rewritten: Vec::new(),
66	conflicts: BTreeMap::new(),
67	moved: state.moved.clone(),
68	};
69	for queued in edits {
70	let mut ops = Vec::new();
71	let mut changed = false;
72	for op in &queued.edit.ops {
73	let apply = |state: &mut Replay, new: &mut Section<'_>, op: &Op| {
74	state.apply(new, &queued.author, queued.edit.at, op)
75	};
76	match op {
77	Op::Page { space, op: page_op } => {
78	if converged.contains(space) {
79	changed = true;
80	continue;
81	}
82	// An op naming what a dropped op named would build on it.
83	let named = named(page_op);
84	if let Some((_, dropped)) = merged.conflicts.get_mut(space)
85	&& named.iter().any(|id| dropped.contains(id))
86	{
87	dropped.extend(named);
88	changed = true;
89	continue;
90	}
91	let replayed = match state.check(old, new, *space, page_op)? {
92	Ok(None) => {
93	changed = true;
94	continue;
95	}
96	Ok(Some(mapped)) => {
97	let mapped = Op::Page {
98	space: *space,
99	op: mapped,
100	};
101	apply(&mut state, new, &mapped)?.then_some(mapped)
102	}
103	Err(Conflicting) => None,
104	};
105	match replayed {
106	Some(mapped) => {
107	changed |= mapped != *op;
108	ops.push(mapped);
109	}
110	None => {
111	changed = true;
112	merged
113	.conflicts
114	.entry(*space)
115	.or_insert_with(|| (queued.author.clone(), BTreeSet::new()))
116	.1
117	.extend(named);
118	}
119	}
120	}
121	Op::Section(section_op) => {
122	advance(&mut state.local, section_op);
123	let mut kept = state.form(old, new, section_op)?.map(Op::Section);
124	if let Some(form) = &kept
125	&& !apply(&mut state, new, form)?
126	{
127	kept = None;
128	}
129	changed |= kept.as_ref() != Some(op);
130	ops.extend(kept);
131	}
132	}
133	}
134	if changed {
135	merged.rewritten.push((
136	queued.id,
137	Edit {
138	at: queued.edit.at,
139	ops,
140	},
141	));
142	}
143	}
144	Ok(merged)
145	}
146
147	/// The stored objects a page op names; a conflict page marks those it holds.
148	fn named(op: &PageOp) -> Vec<ExGuid> {
149	match op {
150	PageOp::Text { text, .. }
151	| PageOp::Format { text, .. }
152	| PageOp::Link { text, .. }
153	| PageOp::Equation { text, .. }
154	| PageOp::Split { text, .. } => vec![*text],
155	PageOp::Date { fields, .. } => fields.iter().map(|(text, _)| *text).collect(),
156	PageOp::Color(_) | PageOp::RuleLines(_) | PageOp::Restyle { .. } => Vec::new(),
157	PageOp::Join { left, right } => vec![*left, *right],
158	PageOp::Insert { container, .. } => vec![*container],
159	PageOp::Move { object, .. }
160	| PageOp::Delete { object }
161	| PageOp::Outline { object, .. } => {
162	vec![*object]
163	}
164	PageOp::Level { paragraph, .. }
165	| PageOp::Paragraph { paragraph, .. }
166	| PageOp::Style { paragraph, .. }
167	| PageOp::Unstyle { paragraph }
168	| PageOp::Media { paragraph, .. }
169	| PageOp::List { paragraph, .. } => vec![*paragraph],
170	PageOp::Tags { target, .. } => vec![*target],
171	PageOp::Add { object, .. } => vec![object.id()],
172	PageOp::Picture {
173	picture: object, ..
174	}
175	| PageOp::Attachment {
176	attachment: object, ..
177	}
178	| PageOp::Strokes { ink: object, .. } => vec![*object],
179	PageOp::Table { table, edit } => match edit {
180	TableEdit::Cell { cell, .. } => vec![*cell],
181	TableEdit::DeleteRow(row) => vec![*row],
182	_ => vec![*table],
183	},
184	}
185	}
186
187	/// The edit keeping `page`, the version of page `space` the remote could not take, and
188	/// applies it to `new`, the merged section: a conflict page under the remote's page
189	/// marking `objects` where `page` holds them, or, where the remote removed the page, the
190	/// page put back as a copy before the next page after it in `local`, the section as the
191	/// queue leaves it, that the remote did not move (`moved`). The page it makes is in the space
192	/// `guid` names, or a fresh one. Content outside the page model stays on the remote's page
193	/// only; `at` is now.
194	#[allow(clippy::too_many_arguments)]
195	pub(crate) fn conflict_page(
196	new: &mut Section<'_>,
197	local: &mut Section<'_>,
198	moved: &BTreeSet<ExGuid>,
199	space: ExGuid,
200	page: &Page,
201	author: &str,
202	objects: &BTreeSet<ExGuid>,
203	at: u64,
204	guid: Option<[u8; 16]>,
205	) -> Result<Edit> {
206	let placed = |creation: PageCreation| match guid {
207	Some(guid) => creation.in_space(guid),
208	None => Ok(creation),
209	};
210	let mut page = page.clone();
211	page.objects
212	.retain(|object| !matches!(object, PageObject::Unsupported(_)));
213	let listed = order(new)?;
214	let ops = if listed.iter().any(|(listed, _)| *listed == space) {
215	let index = Index::of(&page);
216	let mut marked: Vec<ExGuid> = objects
217	.iter()
218	.copied()
219	.filter(|id| index.nodes.contains_key(id))
220	.collect();
221	let copy = page.copy_with(&mut marked)?;
222	let titled = page
223	.objects
224	.iter()
225	.any(|object| matches!(object, PageObject::Title(_)));
226	vec![Op::Section(SectionOp::Conflict {
227	of: space,
228	creation: placed(PageCreation::new(
229	None,
230	titled.then_some(page.title.as_str()),
231	author,
232	)?)?,
233	page: copy,
234	objects: marked,
235	})]
236	} else {
237	// A copy under fresh identities, as OneNote 2010 puts a removed page back.
238	let queued = order(local)?;
239	let at = queued.iter().position(|(queued, _)| *queued == space);
240	let before = at
241	.map_or(&[][..], |at| &queued[at + 1..])
242	.iter()
243	.map(|(next, _)| *next)
244	.find(|next| !moved.contains(next) && listed.iter().any(|(listed, _)| listed == next));
245	let before = series_start(new, before)?;
246	let creation = placed(PageCreation::new(before, Some(&page.title), author)?)?;
247	let mut ops = vec![Op::Section(SectionOp::Import {
248	creation: creation.clone(),
249	page: page.copy()?,
250	})];
251	if let Some(level) = at.map(|at| queued[at].1).filter(|level| *level > 1) {
252	ops.push(Op::Section(SectionOp::Pages(vec![PageEdit::set_level(
253	creation.space(),
254	level,
255	)?])));
256	}
257	ops
258	};
259	let edit = Edit { at, ops };
260	new.apply(author, &edit)?;
261	Ok(edit)
262	}
263
264	/// Pages the base and the remote both list that the remote moved: into another series or
265	/// level, or out of base order among the rest. OneNote 2010 and this writer give a moved
266	/// page a series of its own; older builds of this writer moved a page within its series.
267	pub(crate) fn moved(old: &mut Section<'_>, new: &mut Section<'_>) -> Result<BTreeSet<ExGuid>> {
268	let series = (old.series()?, new.series()?);
269	let base: BTreeMap<ExGuid, (usize, u32)> = order(old)?
270	.into_iter()
271	.enumerate()
272	.map(|(at, (space, level))| (space, (at, level)))
273	.collect();
274	let listed = order(new)?;
275	let kept: Vec<(ExGuid, usize)> = listed
276	.iter()
277	.filter_map(|&(space, level)| {
278	let (at, before) = base.get(&space)?;
279	(*before == level && series.0.get(&space) == series.1.get(&space))
280	.then_some((space, *at))
281	})
282	.collect();
283	// A longest subsequence of `kept` in base order (patience sorting).
284	let mut tails: Vec<usize> = Vec::new();
285	let mut previous = vec![None; kept.len()];
286	for (i, (_, at)) in kept.iter().enumerate() {
287	let k = tails.partition_point(|tail| kept[*tail].1 < *at);
288	previous[i] = k.checked_sub(1).map(|k| tails[k]);
289	if k == tails.len() {
290	tails.push(i);
291	} else {
292	tails[k] = i;
293	}
294	}
295	let mut unmoved = BTreeSet::new();
296	let mut next = tails.last().copied();
297	while let Some(i) = next {
298	unmoved.insert(kept[i].0);
299	next = previous[i];
300	}
301	Ok(listed
302	.into_iter()
303	.map(|(space, _)| space)
304	.filter(|space| base.contains_key(space) && !unmoved.contains(space))
305	.collect())
306	}
307
308	/// Where a page made before `before` goes in `section`: before it where it starts a page
309	/// series, else before the next page that starts one, or last; a page is made only before a
310	/// series' first page.
311	fn series_start(section: &mut Section<'_>, before: Option<ExGuid>) -> Result<Option<ExGuid>> {
312	Ok(starting(&order(section)?, &section.series()?, before))
313	}
314
315	fn starting(
316	listed: &Order,
317	series: &BTreeMap<ExGuid, ExGuid>,
318	before: Option<ExGuid>,
319	) -> Option<ExGuid> {
320	let at = listed
321	.iter()
322	.position(|(space, _)| Some(*space) == before)?;
323	(at..listed.len())
324	.find(|&k| k == 0 || series.get(&listed[k - 1].0) != series.get(&listed[k].0))
325	.map(|k| listed[k].0)
326	}
327
328	/// Applies a queued page-list edit to `local`, the page order as the queue leaves it.
329	fn advance(local: &mut Order, op: &SectionOp) {
330	let insert = |local: &mut Order, page: (ExGuid, u32), before: Option<ExGuid>| {
331	let at = before
332	.and_then(|before| local.iter().position(|(space, _)| *space == before))
333	.unwrap_or(local.len());
334	local.insert(at, page);
335	};
336	match op {
337	SectionOp::Create(creation) | SectionOp::Import { creation, .. } => {
338	insert(local, (creation.space(), 1), creation.before());
339	}
340	SectionOp::Pages(edits) => {
341	for edit in edits {
342	let Some(at) = local.iter().position(|(space, _)| *space == edit.space()) else {
343	continue;
344	};
345	local[at].1 = edit.level();
346	if let PagePosition::Before(before) = edit.position() {
347	let page = local.remove(at);
348	insert(local, page, before);
349	}
350	}
351	}
352	SectionOp::Delete(spaces) => local.retain(|(space, _)| !spaces.contains(space)),
353	SectionOp::Conflict { .. }
354	| SectionOp::Color(_)
355	| SectionOp::RestoreVersion { .. }
356	| SectionOp::DeleteVersions { .. } => {}
357	}
358	}
359
360	fn order(section: &mut Section<'_>) -> Result<Order> {
361	Ok(section
362	.pages()?
363	.into_iter()
364	.map(|(space, _, level)| (space, level))
365	.collect())
366	}
367
368	/// Page spaces in section order with their levels.
369	type Order = Vec<(ExGuid, u32)>;
370
371	struct Replay {
372	/// Active revisions of the base and the remote.
373	before: BTreeMap<ExGuid, ExGuid>,
374	after: BTreeMap<ExGuid, ExGuid>,
375	/// Page order of the base and the remote.
376	orders: (Order, Order),
377	/// Page order as the queue leaves it, up to the op replaying.
378	local: Order,
379	/// Pages the base listed that the remote moved (`moved`).
380	moved: BTreeSet<ExGuid>,
381	/// Page spaces the replayed edits created.
382	created: BTreeSet<ExGuid>,
383	/// Per page the remote changed, what it changed; `None` when it left the page alone.
384	diffs: BTreeMap<ExGuid, Option<Diff>>,
385	}
386
387	impl Replay {
388	/// Applies one op to the remote section; false when the section refused it.
389	fn apply(&mut self, new: &mut Section<'_>, author: &str, at: u64, op: &Op) -> Result<bool> {
390	match new.apply(
391	author,
392	&Edit {
393	at,
394	ops: vec![op.clone()],
395	},
396	) {
397	Ok(()) => {
398	if let Op::Section(
399	SectionOp::Create(creation)
400	| SectionOp::Import { creation, .. }
401	| SectionOp::Conflict { creation, .. },
402	) = op
403	{
404	self.created.insert(creation.space());
405	}
406	Ok(true)
407	}
408	Err(OpError::Failed(error)) => Err(error.into()),
409	Err(_) => Ok(false),
410	}
411	}
412
413	/// The page op as it replays on the remote section; `None` when the remote made it.
414	fn check(
415	&mut self,
416	old: &mut Section<'_>,
417	new: &mut Section<'_>,
418	space: ExGuid,
419	op: &PageOp,
420	) -> Result<std::result::Result<Option<PageOp>, Conflicting>> {
421	if !self.listed(space) {
422	return Ok(Err(Conflicting));
423	}
424	let diff = match self.diffs.get_mut(&space) {
425	Some(diff) => diff,
426	None => {
427	let diff = match (self.before.get(&space), self.after.get(&space)) {
428	(Some(before), Some(after)) => {
429	let (old, new) = (old.page(space)?, new.page(space)?);
430	// A host's merged batch retains its guest's revision identity.
431	(before != after || old != new).then(|| Diff {
432	old: Index::of(&old),
433	new: Index::of(&new),
434	regions: BTreeMap::new(),
435	})
436	}
437	_ => None,
438	};
439	self.diffs.entry(space).or_insert(diff)
440	}
441	};
442	Ok(match diff {
443	None => Ok(Some(op.clone())),
444	Some(diff) => diff.check(op),
445	})
446	}
447
448	/// Whether the remote section lists the page, or the replayed edits created it; a page
449	/// removed from the list keeps its stored revisions.
450	fn listed(&self, space: ExGuid) -> bool {
451	self.created.contains(&space) || self.orders.1.iter().any(|(page, _)| *page == space)
452	}
453
454	/// Where a page the queue put before `before` goes on the remote: before the first page
455	/// from `before` on, in the queue's order, that the remote lists where the base had it,
456	/// or last, as OneNote 2010 places a page series only one side changed.
457	fn anchor(&self, listed: &Order, page: ExGuid, before: Option<ExGuid>) -> Option<ExGuid> {
458	let from = self
459	.local
460	.iter()
461	.position(|(space, _)| Some(*space) == before)?;
462	self.local[from..]
463	.iter()
464	.map(|(space, _)| *space)
465	.find(|space| {
466	*space != page
467	&& !self.moved.contains(space)
468	&& listed.iter().any(|(listed, _)| listed == space)
469	})
470	}
471
472	/// A section op as it replays on the remote section, or `None`: a page placed by
473	/// `anchor`, the page edits of pages the remote still has and did not move, removals of
474	/// pages the remote still has (a page it changed is not removed), a conflict page's
475	/// content as a page of its own where the remote removed its page.
476	fn form(
477	&self,
478	old: &mut Section<'_>,
479	new: &mut Section<'_>,
480	op: &SectionOp,
481	) -> Result<Option<SectionOp>> {
482	let conflicts: BTreeSet<ExGuid> = new
483	.conflicts()?
484	.into_iter()
485	.flat_map(|(_, pages)| pages.into_iter().map(|page| page.space))
486	.collect();
487	let listed = order(new)?;
488	let series = new.series()?;
489	let anchored = |creation: &PageCreation| {
490	let anchor = self.anchor(&listed, creation.space(), creation.before());
491	creation.reposition(starting(&listed, &series, anchor))
492	};
493	Ok(match op {
494	SectionOp::Create(creation) => Some(SectionOp::Create(anchored(creation)?)),
495	SectionOp::Import { creation, page } => Some(SectionOp::Import {
496	creation: anchored(creation)?,
497	page: page.clone(),
498	}),
499	SectionOp::Color(_) => Some(op.clone()),
500	SectionOp::Conflict {
501	of, creation, page, ..
502	} => Some(if self.listed(*of) {
503	op.clone()
504	} else {
505	SectionOp::Import {
506	creation: creation.clone(),
507	page: page.clone(),
508	}
509	}),
510	// A page the remote moved or re-leveled keeps the remote's placement.
511	SectionOp::Pages(edits) => {
512	let mut kept = Vec::new();
513	for edit in edits {
514	if self.moved.contains(&edit.space())
515	|| listed.iter().all(|(listed, _)| *listed != edit.space())
516	{
517	continue;
518	}
519	kept.push(match edit.position() {
520	PagePosition::Keep => edit.clone(),
521	PagePosition::Before(before) => edit.reposition(
522	PagePosition::Before(self.anchor(&listed, edit.space(), before)),
523	edit.level(),
524	)?,
525	});
526	}
527	(!kept.is_empty()).then_some(SectionOp::Pages(kept))
528	}
529	// A version the remote deleted is gone; restoring one keeps the remote's page as
530	// the newest version.
531	SectionOp::RestoreVersion { page, version, .. } => (self.listed(*page)
532	&& listed_versions(new, *page)?.contains(version))
533	.then(|| op.clone()),
534	SectionOp::DeleteVersions { page, versions } => {
535	let listed = listed_versions(new, *page)?;
536	let versions: Vec<ExGuid> = versions
537	.iter()
538	.filter(|version| listed.contains(version))
539	.copied()
540	.collect();
541	(!versions.is_empty()).then_some(SectionOp::DeleteVersions {
542	page: *page,
543	versions,
544	})
545	}
546	SectionOp::Delete(deleted) => {
547	let deleted: Vec<ExGuid> = deleted
548	.iter()
549	.filter(|space| {
550	self.listed(**space) && self.before.get(space) == self.after.get(space)
551	&& matches!((old.page(**space), new.page(**space)), (Ok(a), Ok(b)) if a == b)
552	|| conflicts.contains(space)
553	})
554	.copied()
555	.collect();
556	(!deleted.is_empty()).then_some(SectionOp::Delete(deleted))
557	}
558	})
559	}
560	}
561
562	/// The versions `section` lists for `page`.
563	fn listed_versions(section: &mut Section<'_>, page: ExGuid) -> Result<Vec<ExGuid>> {
564	Ok(section
565	.versions()?
566	.into_iter()
567	.filter(|(listed, _)| *listed == page)
568	.flat_map(|(_, versions)| versions.into_iter().map(|version| version.context))
569	.collect())
570	}
571
572	/// One page as the base stored it and as the remote does, with the remote's text changes
573	/// in the coordinates of the replayed edits.
574	struct Diff {
575	old: Index,
576	new: Index,
577	regions: BTreeMap<ExGuid, Changes>,
578	}
579
580	impl Diff {
581	fn ours(&self, id: ExGuid) -> bool {
582	!self.old.nodes.contains_key(&id)
583	}
584
585	/// Whether the remote left the object's own data as the base had it.
586	fn kept(&self, id: ExGuid) -> bool {
587	self.ours(id)
588	|| matches!((self.old.nodes.get(&id), self.new.nodes.get(&id)), (Some(a), Some(b)) if a.own == b.own)
589	}
590
591	/// Whether the remote left the object and everything under it as the base had it.
592	fn untouched(&self, id: ExGuid) -> bool {
593	if self.ours(id) {
594	return true;
595	}
596	let (Some(a), Some(b)) = (self.old.nodes.get(&id), self.new.nodes.get(&id)) else {
597	return false;
598	};
599	a.own == b.own
600	&& a.parent == b.parent
601	&& a.children == b.children
602	&& a.below().all(|child| self.untouched(child))
603	}
604
605	/// Whether the remote kept the object under the same parent, in the same order among
606	/// the siblings both sides have.
607	fn placed(&self, id: ExGuid) -> bool {
608	if self.ours(id) {
609	return true;
610	}
611	let (Some(a), Some(b)) = (self.old.nodes.get(&id), self.new.nodes.get(&id)) else {
612	return false;
613	};
614	if a.parent != b.parent {
615	return false;
616	}
617	let siblings = |index: &Index| index.children(a.parent).to_vec();
618	let (old, new) = (siblings(&self.old), siblings(&self.new));
619	let at = |list: &[ExGuid], id: ExGuid| list.iter().position(|x| *x == id);
620	let (Some(i), Some(j)) = (at(&old, id), at(&new, id)) else {
621	return false;
622	};
623	old.iter()
624	.enumerate()
625	.all(|(k, peer)| *peer == id || at(&new, *peer).is_none_or(|l| (k < i) == (l < j)))
626	}
627
628	/// Where the remote changed a text's characters and formats; its tags and date field
629	/// are not positions an op names.
630	fn region(&mut self, text: ExGuid) -> std::result::Result<Option<&mut Changes>, Conflicting> {
631	if !self.regions.contains_key(&text) {
632	if self.ours(text) {
633	return Ok(None);
634	}
635	let (Some(Own::Text(a)), Some(Own::Text(b))) = (
636	self.old.nodes.get(&text).map(|node| &node.own),
637	self.new.nodes.get(&text).map(|node| &node.own),
638	) else {
639	return Err(Conflicting);
640	};
641	if a.text == b.text {
642	return Ok(None);
643	}
644	let region = Changes::between(&a.text, &b.text);
645	self.regions.insert(text, region);
646	}
647	Ok(self.regions.get_mut(&text))
648	}
649
650	/// The op as it replays on the remote page; `None` when the remote already made it.
651	fn check(&mut self, op: &PageOp) -> std::result::Result<Option<PageOp>, Conflicting> {
652	let require = |ok: bool| if ok { Ok(()) } else { Err(Conflicting) };
653	let mut op = op.clone();
654	match &mut op {
655	PageOp::Text { text, range, with } => {
656	if let Some(region) = self.region(*text)? {
657	let mapped = region.map(range).ok_or(Conflicting)?;
658	region.replaced(range, with.encode_utf16().count() as u32);
659	*range = mapped;
660	}
661	}
662	PageOp::Format { text, range, .. } => {
663	if let Some(region) = self.region(*text)? {
664	*range = region.map(range).ok_or(Conflicting)?;
665	}
666	}
667	PageOp::Link { text, .. } | PageOp::Equation { text, .. } => {
668	require(self.region(*text)?.is_none())?;
669	}
670	PageOp::Date { fields, .. } => {
671	for (text, _) in fields.iter() {
672	require(self.region(*text)?.is_none())?;
673	}
674	}
675	PageOp::Split {
676	text, at, right, ..
677	} => {
678	// The new paragraph copies the holder's placement and formats; lists and tags
679	// stay with the holder unless the split names copies of them.
680	let holder = self.holder(*text);
681	require(holder.is_none_or(|holder| self.splits_alike(holder)))?;
682	if let Some(region) = self.region(*text)? {
683	// The cut moves with the character after it: text the remote typed at
684	// the cut stays left of it.
685	let cut = region.map(&(*at..*at + 1)).ok_or(Conflicting)?;
686	let right_changes = region.split(*at);
687	if !right_changes.0.is_empty() {
688	self.regions.insert(*right, right_changes);
689	}
690	*at = cut.start;
691	}
692	}
693	PageOp::Join { left, right } => {
694	require(self.untouched(*right))?;
695	require(
696	self.holder_text(*right)
697	.is_none_or(|text| !self.regions.contains_key(&text)),
698	)?;
699	if let Some(text) = self.holder_text(*left) {
700	self.region(text)?;
701	}
702	}
703	// A page's colour and rule lines are the latest set, whichever side set them.
704	PageOp::Insert { .. }
705	| PageOp::Add { .. }
706	| PageOp::Color(_)
707	| PageOp::RuleLines(_) => {}
708	PageOp::Move {
709	object,
710	parent,
711	before,
712	} => require(self.placed(*object) || self.placed_at(*object, *parent, *before))?,
713	PageOp::Delete { object } => {
714	if !self.ours(*object) && !self.new.nodes.contains_key(object) {
715	return Ok(None);
716	}
717	require(self.untouched(*object))?
718	}
719	PageOp::Level { paragraph, .. } => require(
720	self.ours(*paragraph) || {
721	let level = |index: &Index| {
722	index.nodes.get(paragraph).map(|node| {
723	(
724	node.parent,
725	match &node.own {
726	Own::Paragraph { level, .. } => *level,
727	_ => 0,
728	},
729	)
730	})
731	};
732	level(&self.old).is_some() && level(&self.old) == level(&self.new)
733	},
734	)?,
735	PageOp::Outline { object, edit } => {
736	if self.ours(*object) {
737	return Ok(Some(op));
738	}
739	let edit: &OutlineEdit = edit;
740	// What the edit sets, as each side has it.
741	let part = |index: &Index| {
742	index.nodes.get(object).map(|node| match (&node.own, edit) {
743	(
744	Own::Outline { layout, .. }
745	| Own::Ink(Ink { layout, .. })
746	| Own::Attachment(Attachment { layout, .. }),
747	OutlineEdit::Position { .. },
748	) => (layout.x, layout.y, None, None),
749	(Own::Outline { layout, .. }, OutlineEdit::Width { .. }) => (
750	layout.max_width,
751	layout.reserved_width,
752	layout.width_set_by_user,
753	None,
754	),
755	(Own::Paragraph { collapsed, .. }, OutlineEdit::Collapsed(_)) => {
756	(None, None, None, Some(*collapsed))
757	}
758	_ => (None, None, None, None),
759	})
760	};
761	let (before, after) = (part(&self.old), part(&self.new));
762	if before.is_some() && before != after {
763	// The remote set the same value: the edit is done.
764	let near = |a: Option<f32>, b: f32| a.is_some_and(|a| (a - b).abs() < 1e-3);
765	let done = match (after, edit) {
766	(Some((x, y, ..)), OutlineEdit::Position { x: px, y: py }) => {
767	near(x, *px) && near(y, *py)
768	}
769	(
770	Some((width, reserved, set, _)),
771	OutlineEdit::Width { points, user_set },
772	) => near(width, *points) && reserved.is_none() && set == Some(*user_set),
773	(Some((.., collapsed)), OutlineEdit::Collapsed(value)) => {
774	collapsed == Some(*value)
775	}
776	_ => false,
777	};
778	return if done { Ok(None) } else { Err(Conflicting) };
779	}
780	require(before.is_some())?
781	}
782	PageOp::Paragraph { paragraph, .. }
783	| PageOp::Style { paragraph, .. }
784	| PageOp::Unstyle { paragraph }
785	| PageOp::Media { paragraph, .. }
786	| PageOp::List { paragraph, .. } => {
787	require(self.kept(*paragraph) && self.new_has(*paragraph))?
788	}
789	PageOp::Tags { target, .. } => require(self.same_tags(*target))?,
790	// A theme reaches the style's paragraphs as the remote left them; a style the
791	// remote no longer uses is restyled when the page next opens.
792	PageOp::Restyle { style, .. } => {
793	if self.old.styles.contains(style) && !self.new.styles.contains(style) {
794	return Ok(None);
795	}
796	}
797	PageOp::Picture {
798	picture: object, ..
799	}
800	| PageOp::Attachment {
801	attachment: object, ..
802	}
803	| PageOp::Strokes { ink: object, .. } => {
804	require(self.kept(*object) && self.new_has(*object))?
805	}
806	PageOp::Table { table, edit } => match edit {
807	TableEdit::Cell { cell, .. } => require(self.kept(*cell) && self.new_has(*cell))?,
808	TableEdit::DeleteRow(row) => require(self.kept(*table) && self.untouched(*row))?,
809	TableEdit::DeleteColumn(_) => require(self.untouched(*table))?,
810	TableEdit::Rows { .. }
811	| TableEdit::Column { .. }
812	| TableEdit::Columns(_)
813	| TableEdit::Borders(_) => require(self.kept(*table) && self.new_has(*table))?,
814	},
815	}
816	Ok(Some(op))
817	}
818
819	/// Whether the remote put the object where a move places it: under `parent` (the page
820	/// when `None`), before `before` or last.
821	fn placed_at(&self, id: ExGuid, parent: Option<ExGuid>, before: Option<ExGuid>) -> bool {
822	let Some(node) = self.new.nodes.get(&id) else {
823	return false;
824	};
825	let container = parent.unwrap_or(PAGE);
826	let siblings = self.new.children(container);
827	node.parent == container
828	&& siblings
829	.iter()
830	.position(|sibling| *sibling == id)
831	.is_some_and(|at| siblings.get(at + 1).copied() == before)
832	}
833
834	/// Whether the remote kept a paragraph's, text's or table's tags.
835	fn same_tags(&self, id: ExGuid) -> bool {
836	if self.ours(id) {
837	return true;
838	}
839	let tags = |index: &Index| {
840	index.nodes.get(&id).map(|node| match &node.own {
841	Own::Paragraph { tags, .. } | Own::Table { tags, .. } => Some(tags.clone()),
842	Own::Text(text) => Some(text.tags.clone()),
843	_ => None,
844	})
845	};
846	let before = tags(&self.old);
847	before.is_some() && before == tags(&self.new)
848	}
849
850	fn new_has(&self, id: ExGuid) -> bool {
851	self.ours(id) || self.new.nodes.contains_key(&id)
852	}
853
854	/// The paragraph holding a text, as the base stored it.
855	fn holder(&self, text: ExGuid) -> Option<ExGuid> {
856	self.old.nodes.get(&text).map(|node| node.parent)
857	}
858
859	fn holder_text(&self, paragraph: ExGuid) -> Option<ExGuid> {
860	match self.old.nodes.get(&paragraph).map(|node| &node.own) {
861	Some(Own::Paragraph { content, .. }) => Some(*content),
862	_ => None,
863	}
864	}
865
866	/// Whether a split of the paragraph makes the same new paragraph on both sides: its
867	/// container, style, format and children are as the base had them.
868	fn splits_alike(&self, id: ExGuid) -> bool {
869	if self.ours(id) {
870	return true;
871	}
872	let shape = |index: &Index| {
873	index.nodes.get(&id).map(|node| match &node.own {
874	Own::Paragraph { style, format, .. } => {
875	Some((node.parent, *style, format.clone(), node.children.clone()))
876	}
877	_ => None,
878	})
879	};
880	let before = shape(&self.old);
881	before.is_some() && before == shape(&self.new)
882	}
883	}
884
885	/// Where the remote replaced parts of a text, in order: each `start..end` of the text as
886	/// the replayed edits see it holds what the remote replaced by `end - start + delta` UTF-16
887	/// units. Outside them both texts hold the same characters in the same formats.
888	#[derive(Debug, Clone, Default, PartialEq)]
889	struct Changes(Vec<Region>);
890
891	#[derive(Debug, Clone, Copy, PartialEq)]
892	struct Region {
893	start: u32,
894	end: u32,
895	delta: i64,
896	}
897
898	/// The characters of a text with their formats and UTF-16 widths.
899	fn units(paragraph: &Paragraph) -> Vec<(char, Format)> {
900	let mut out = Vec::new();
901	let mut spans = paragraph.spans().iter();
902	let mut span = spans.next();
903	for (byte, character) in paragraph.text().char_indices() {
904	while span.is_some_and(|span| span.end <= byte) {
905	span = spans.next();
906	}
907	out.push((
908	character,
909	span.map(|span| span.format.clone()).unwrap_or_default(),
910	));
911	}
912	out
913	}
914
915	/// Beyond this many cells of the alignment table the changed middle counts as one change.
916	const CELLS: usize = 4_000_000;
917
918	impl Changes {
919	/// The runs where `new` differs from `old` in characters or formats, from a longest
920	/// common subsequence of the two: where several align equally, one is chosen, which
921	/// places an op among repeated characters one way of the equally valid ones.
922	fn between(old: &Paragraph, new: &Paragraph) -> Self {
923	let (a, b) = (units(old), units(new));
924	let prefix = a.iter().zip(&b).take_while(|(x, y)| x == y).count();
925	let suffix = a[prefix..]
926	.iter()
927	.rev()
928	.zip(b[prefix..].iter().rev())
929	.take_while(|(x, y)| x == y)
930	.count();
931	let (x, y) = (&a[prefix..a.len() - suffix], &b[prefix..b.len() - suffix]);
932	// Matched pairs of the middles, in order.
933	let mut matched = Vec::new();
934	if x.len().saturating_mul(y.len()) <= CELLS {
935	let width = y.len() + 1;
936	let mut table = vec![0_u32; (x.len() + 1) * width];
937	for i in (0..x.len()).rev() {
938	for j in (0..y.len()).rev() {
939	table[i * width + j] = if x[i] == y[j] {
940	table[(i + 1) * width + j + 1] + 1
941	} else {
942	table[(i + 1) * width + j].max(table[i * width + j + 1])
943	};
944	}
945	}
946	let (mut i, mut j) = (0, 0);
947	while i < x.len() && j < y.len() {
948	if x[i] == y[j] {
949	matched.push((i, j));
950	i += 1;
951	j += 1;
952	} else if table[(i + 1) * width + j] >= table[i * width + j + 1] {
953	i += 1;
954	} else {
955	j += 1;
956	}
957	}
958	}
959	matched.push((x.len(), y.len()));
960	let width = |units: &[(char, Format)]| -> u32 {
961	units
962	.iter()
963	.map(|(character, _)| character.len_utf16() as u32)
964	.sum()
965	};
966	let mut regions = Vec::new();
967	let (mut at, mut i, mut j) = (width(&a[..prefix]), 0, 0);
968	for (k, l) in matched {
969	if (k, l) != (i, j) {
970	let (removed, inserted) = (width(&x[i..k]), width(&y[j..l]));
971	regions.push(Region {
972	start: at,
973	end: at + removed,
974	delta: i64::from(inserted) - i64::from(removed),
975	});
976	at += removed;
977	}
978	if k < x.len() {
979	at += width(&x[k..k + 1]);
980	}
981	(i, j) = (k + 1, l + 1);
982	}
983	Self(regions)
984	}
985
986	/// The range on the remote text, when it lies clear of every change: a range may end
987	/// where a change starts or start where one ends, an insertion point may not.
988	fn map(&self, range: &Range<u32>) -> Option<Range<u32>> {
989	let empty = range.start == range.end;
990	let mut shift = 0;
991	for region in &self.0 {
992	if range.end < region.start || (!empty && range.end == region.start) {
993	break;
994	}
995	if range.start > region.end || (!empty && range.start == region.end) {
996	shift += region.delta;
997	} else {
998	return None;
999	}
1000	}
1001	let shifted = |at: u32| u32::try_from(i64::from(at) + shift).ok();
1002	Some(shifted(range.start)?..shifted(range.end)?)
1003	}
1004
1005	/// Follows a replacement of `range`, clear of every change, by `length` units.
1006	fn replaced(&mut self, range: &Range<u32>, length: u32) {
1007	let moved = i64::from(length) - i64::from(range.end - range.start);
1008	for region in &mut self.0 {
1009	if region.start >= range.end {
1010	region.start = (i64::from(region.start) + moved) as u32;
1011	region.end = (i64::from(region.end) + moved) as u32;
1012	}
1013	}
1014	}
1015
1016	/// Cuts the text at `at`, clear of every change, keeping the changes left of it (text
1017	/// typed at the cut included) and returning those right of it, measured from the cut.
1018	fn split(&mut self, at: u32) -> Self {
1019	let right = self
1020	.0
1021	.iter()
1022	.filter(|region| region.end > at)
1023	.map(|region| Region {
1024	start: region.start - at,
1025	end: region.end - at,
1026	delta: region.delta,
1027	})
1028	.collect();
1029	self.0.retain(|region| region.end <= at);
1030	Self(right)
1031	}
1032	}
1033
1034	/// What an object holds apart from the objects under it.
1035	#[derive(Debug, Clone, PartialEq)]
1036	enum Own {
1037	Outline {
1038	title: bool,
1039	min_width: Option<f32>,
1040	layout: Layout,
1041	indents: Vec<f32>,
1042	unsupported: Vec<Unsupported>,
1043	},
1044	Title {
1045	date: Option<ExGuid>,
1046	layout: Layout,
1047	},
1048	Paragraph {
1049	level: u32,
1050	style: Option<ExGuid>,
1051	format: Format,
1052	lists: Vec<ExGuid>,
1053	tags: Vec<Tag>,
1054	media: MediaIndex,
1055	collapsed: bool,
1056	content: ExGuid,
1057	},
1058	Text(TextObject),
1059	Table {
1060	columns: Vec<TableColumn>,
1061	borders: Option<bool>,
1062	layout: Layout,
1063	tags: Vec<Tag>,
1064	},
1065	Row,
1066	Cell {
1067	layout: Layout,
1068	indents: Vec<f32>,
1069	shading: Option<u32>,
1070	unsupported: Vec<Unsupported>,
1071	},
1072	Image(Image),
1073	Attachment(Attachment),
1074	Ink(Ink),
1075	Unsupported(Unsupported),
1076	}
1077
1078	#[derive(Debug)]
1079	struct Node {
1080	own: Own,
1081	/// The containing object; the page is the default identity.
1082	parent: ExGuid,
1083	children: Vec<ExGuid>,
1084	}
1085
1086	impl Node {
1087	/// Everything directly under the object, a paragraph's content included.
1088	fn below(&self) -> impl Iterator<Item = ExGuid> + '_ {
1089	let content = match &self.own {
1090	Own::Paragraph { content, .. } => Some(*content),
1091	_ => None,
1092	};
1093	content.into_iter().chain(self.children.iter().copied())
1094	}
1095	}
1096
1097	#[derive(Default)]
1098	struct Index {
1099	nodes: BTreeMap<ExGuid, Node>,
1100	page: Vec<ExGuid>,
1101	/// The paragraph styles the page's paragraphs use.
1102	styles: BTreeSet<ExGuid>,
1103	}
1104
1105	const PAGE: ExGuid = ExGuid {
1106	guid: [0; 16],
1107	n: 0,
1108	};
1109
1110	impl Index {
1111	fn of(page: &Page) -> Self {
1112	let mut index = Self {
1113	styles: page
1114	.definitions
1115	.iter()
1116	.filter(|(_, definition)| {
1117	matches!(definition.kind, onestore::document::Kind::Style { .. })
1118	})
1119	.map(|(id, _)| *id)
1120	.collect(),
1121	..Self::default()
1122	};
1123	for object in &page.objects {
1124	index.page.push(object.id());
1125	match object {
1126	PageObject::Outline(outline) => index.outline(outline, PAGE),
1127	PageObject::Title(title) => {
1128	index.add(
1129	title.id,
1130	PAGE,
1131	Own::Title {
1132	date: title.date,
1133	layout: title.layout.clone(),
1134	},
1135	title.outlines.iter().map(|outline| outline.id).collect(),
1136	);
1137	for outline in &title.outlines {
1138	index.outline(outline, title.id);
1139	}
1140	}
1141	PageObject::Image(image) => {
1142	index.add(image.id, PAGE, Own::Image(image.clone()), Vec::new())
1143	}
1144	PageObject::Attachment(file) => {
1145	index.add(file.id, PAGE, Own::Attachment(file.clone()), Vec::new())
1146	}
1147	PageObject::Ink(ink) => index.add(ink.id, PAGE, Own::Ink(ink.clone()), Vec::new()),
1148	PageObject::Unsupported(object) => index.add(
1149	object.id,
1150	PAGE,
1151	Own::Unsupported(object.clone()),
1152	Vec::new(),
1153	),
1154	}
1155	}
1156	index
1157	}
1158
1159	fn children(&self, id: ExGuid) -> &[ExGuid] {
1160	if id == PAGE {
1161	&self.page
1162	} else {
1163	self.nodes.get(&id).map_or(&[], |node| &node.children)
1164	}
1165	}
1166
1167	fn add(&mut self, id: ExGuid, parent: ExGuid, own: Own, children: Vec<ExGuid>) {
1168	self.nodes.insert(
1169	id,
1170	Node {
1171	own,
1172	parent,
1173	children,
1174	},
1175	);
1176	}
1177
1178	fn outline(&mut self, outline: &Outline, parent: ExGuid) {
1179	let children = self.paragraphs(&outline.paragraphs, outline.id);
1180	self.add(
1181	outline.id,
1182	parent,
1183	Own::Outline {
1184	title: outline.title,
1185	min_width: outline.min_width,
1186	layout: outline.layout.clone(),
1187	indents: outline.indents.clone(),
1188	unsupported: outline.unsupported.clone(),
1189	},
1190	children,
1191	);
1192	}
1193
1194	/// Indexes a flat paragraph list; returns the container's direct children.
1195	fn paragraphs(&mut self, list: &[PageParagraph], container: ExGuid) -> Vec<ExGuid> {
1196	let mut children: BTreeMap<ExGuid, Vec<ExGuid>> = BTreeMap::new();
1197	for paragraph in list {
1198	children
1199	.entry(paragraph.parent.unwrap_or(container))
1200	.or_default()
1201	.push(paragraph.id);
1202	}
1203	for paragraph in list {
1204	let content = match &paragraph.content {
1205	ParagraphContent::Text(text) => {
1206	self.add(text.id, paragraph.id, Own::Text(text.clone()), Vec::new());
1207	text.id
1208	}
1209	ParagraphContent::Table(table) => {
1210	let rows = table.rows.iter().map(|row| row.id).collect();
1211	for row in &table.rows {
1212	let cells = row.cells.iter().map(|cell| cell.id).collect();
1213	for cell in &row.cells {
1214	let children = self.paragraphs(&cell.paragraphs, cell.id);
1215	self.add(
1216	cell.id,
1217	row.id,
1218	Own::Cell {
1219	layout: cell.layout.clone(),
1220	indents: cell.indents.clone(),
1221	shading: cell.shading,
1222	unsupported: cell.unsupported.clone(),
1223	},
1224	children,
1225	);
1226	}
1227	self.add(row.id, table.id, Own::Row, cells);
1228	}
1229	self.add(
1230	table.id,
1231	paragraph.id,
1232	Own::Table {
1233	columns: table.columns.clone(),
1234	borders: table.borders,
1235	layout: table.layout.clone(),
1236	tags: table.tags.clone(),
1237	},
1238	rows,
1239	);
1240	table.id
1241	}
1242	ParagraphContent::Image(image) => {
1243	self.add(
1244	image.id,
1245	paragraph.id,
1246	Own::Image(image.clone()),
1247	Vec::new(),
1248	);
1249	image.id
1250	}
1251	ParagraphContent::Attachment(attachment) => {
1252	self.add(
1253	attachment.id,
1254	paragraph.id,
1255	Own::Attachment(attachment.clone()),
1256	Vec::new(),
1257	);
1258	attachment.id
1259	}
1260	ParagraphContent::Ink(ink) => {
1261	self.add(ink.id, paragraph.id, Own::Ink(ink.clone()), Vec::new());
1262	ink.id
1263	}
1264	ParagraphContent::Unsupported(object) => {
1265	self.add(
1266	object.id,
1267	paragraph.id,
1268	Own::Unsupported(object.clone()),
1269	Vec::new(),
1270	);
1271	object.id
1272	}
1273	};
1274	self.add(
1275	paragraph.id,
1276	paragraph.parent.unwrap_or(container),
1277	Own::Paragraph {
1278	level: paragraph.level,
1279	style: paragraph.style,
1280	format: paragraph.format.clone(),
1281	lists: paragraph.lists.clone(),
1282	tags: paragraph.tags.clone(),
1283	media: paragraph.media.clone(),
1284	collapsed: paragraph.collapsed,
1285	content,
1286	},
1287	children.remove(&paragraph.id).unwrap_or_default(),
1288	);
1289	}
1290	children.remove(&container).unwrap_or_default()
1291	}
1292	}
1293
1294	#[cfg(test)]
1295	mod tests {
1296	use super::*;
1297
1298	fn text(s: &str) -> Paragraph {
1299	Paragraph::new(s.into(), Format::default())
1300	}
1301
1302	#[test]
1303	fn ranges_clear_of_the_remote_changes_shift_past_them() {
1304	let region = |start, end, delta| Region { start, end, delta };
1305	let changes = Changes::between(&text("one two three"), &text("one 2 three"));
1306	assert_eq!(changes.0, [region(4, 7, -2)]);
1307	assert_eq!(changes.map(&(0..3)), Some(0..3));
1308	assert_eq!(changes.map(&(0..4)), Some(0..4));
1309	assert_eq!(changes.map(&(8..13)), Some(6..11));
1310	assert_eq!(changes.map(&(7..8)), Some(5..6));
1311	assert_eq!(changes.map(&(13..13)), Some(11..11));
1312	assert_eq!(changes.map(&(4..4)), None);
1313	assert_eq!(changes.map(&(7..7)), None);
1314	assert_eq!(changes.map(&(3..5)), None);
1315	let mut moved = changes.clone();
1316	moved.replaced(&(0..0), 5);
1317	assert_eq!(moved.0, [region(9, 12, -2)]);
1318	let both = Changes::between(&text("ab🦀cd"), &text("Xab🦀cYd"));
1319	assert_eq!(both.0, [region(0, 0, 1), region(5, 5, 1)]);
1320	assert_eq!(both.map(&(2..4)), Some(3..5));
1321	assert_eq!(both.map(&(1..1)), Some(2..2));
1322	assert_eq!(both.map(&(0..0)), None);
1323	assert_eq!(both.map(&(3..6)), None);
1324	let bold = Format {
1325	bold: Some(true),
1326	..Default::default()
1327	};
1328	let formatted = Changes::between(
1329	&text("abc"),
1330	&Paragraph::from_runs([
1331	("a".to_owned(), Format::default()),
1332	("b".to_owned(), bold),
1333	("c".to_owned(), Format::default()),
1334	]),
1335	);
1336	assert_eq!(formatted.0, [region(1, 2, 0)]);
1337	let emoji = Changes::between(&text("🦀a"), &text("🦀ab"));
1338	assert_eq!(emoji.0, [region(3, 3, 1)]);
1339	let mut cut = Changes::between(&text("abcdef"), &text("aXbcdeYf"));
1340	assert_eq!(cut.map(&(3..4)), Some(4..5));
1341	let right = cut.split(3);
1342	assert_eq!(
1343	(cut.0, right.0),
1344	(vec![region(1, 1, 1)], vec![region(2, 2, 1)])
1345	);
1346	let mut typed = Changes::between(&text("ab🦀cd"), &text("abX🦀cd"));
1347	assert_eq!(typed.map(&(2..3)), Some(3..4));
1348	assert!(typed.split(2).0.is_empty());
1349	assert_eq!(typed.0, [region(2, 2, 1)]);
1350	}
1351	}