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