1//! Merging a version of a section file that a file provider kept beside the file, as iCloud
2//! Drive keeps a commit that lost to another device's (a conflict version, `NSFileVersion`).
3//! The version's changes since the state it last shared with the file replay on the file
4//! (`merge.rs`), with conflict pages where they clash, as a queue replays on a changed
5//! remote.
6//!
7//! Each revision the merge writes is named after the version's revision it merged and the
8//! file's revision it merged onto (`merged`), and older builds' names (`named`) still count.
9//! A space whose newest revision the file holds, or holds merged, needs nothing; older ones
10//! are where the version and the file last agreed. So a version merged once, by this device or
11//! another, merges as nothing the next time, and two devices merging it onto one state write
12//! revisions of the same names, which the next merge of the two finds held.
13
14use crate::{PendingEdit, Result, merge};
15use onestore::{
16 Arena, ConflictPage, ExGuid, ObjectSpace, PageCreation, PageEdit, RevisionIndex, Section,
17 Store, Transaction,
18 op::{Edit, Op, SectionOp, lower_page},
19};
20use sha2::{Digest, Sha256};
21use std::collections::{BTreeMap, BTreeSet};
22
23/// A version of a section file its file provider keeps beside the file.
24#[derive(Debug, Clone, PartialEq, Eq)]
25pub struct Version {
26 /// Names the version to `Remote::version` and `Remote::retire`.
27 pub id: String,
28 /// The computer or device that saved it (`localizedNameOfSavingComputer`), which labels
29 /// the conflict pages it gives.
30 pub device: Option<String>,
31}
32
33/// What merging a version into the file comes to.
34pub(crate) enum Merged {
35 /// The file already holds every change the version holds.
36 Held,
37 /// The revisions bringing the version's changes onto the file.
38 Publish(Box<Transaction>),
39 /// Another section, which only shares the file's name.
40 Foreign,
41}
42
43/// What older builds named a merge of the version's revision `rid`: the revisions it wrote
44/// (`"page"`), and the conflict pages it made (`"conflict"`), which keep the name.
45fn named(rid: ExGuid, kind: &str) -> ExGuid {
46 let digest = Sha256::new()
47 .chain_update(b"snowbound merge ")
48 .chain_update(kind)
49 .chain_update(rid.guid)
50 .chain_update(rid.n.to_le_bytes())
51 .finalize();
52 let mut guid = [0; 16];
53 guid.copy_from_slice(&digest[..16]);
54 ExGuid { guid, n: 1 }
55}
56
57/// The name of the revision a merge writes for the version's revision `rid` onto the file's
58/// revision `onto` of that space, which it depends on: two merges of one version onto
59/// different states are different revisions. Onto no revision, as in a space the merge
60/// creates, it is the name older builds gave.
61fn merged(rid: ExGuid, onto: Option<ExGuid>) -> ExGuid {
62 let mut digest = Sha256::new()
63 .chain_update(b"snowbound merge page")
64 .chain_update(rid.guid)
65 .chain_update(rid.n.to_le_bytes());
66 if let Some(onto) = onto {
67 digest = digest
68 .chain_update(onto.guid)
69 .chain_update(onto.n.to_le_bytes());
70 }
71 let mut guid = [0; 16];
72 guid.copy_from_slice(&digest.finalize()[..16]);
73 ExGuid { guid, n: 1 }
74}
75
76/// Merges `version` into `current`, the file as it stands, `device` naming who saved the
77/// version.
78pub(crate) fn merge(current: &[u8], version: &[u8], device: &str) -> Result<Merged> {
79 let (store, theirs) = (Store::parse(current)?, Store::parse(version)?);
80 let (file, stored) = (
81 RevisionIndex::parse(&store)?,
82 RevisionIndex::parse(&theirs)?,
83 );
84 if file.root != stored.root {
85 return Ok(Merged::Foreign);
86 }
87 // Per space of the version: where it last agreed with the file, and its newest revision.
88 let mut shared = BTreeMap::new();
89 let mut heads = BTreeMap::new();
90 for (space, revisions) in &stored.spaces {
91 let Some(head) = revisions.labels.get(&(ExGuid::default(), 1)).copied() else {
92 continue;
93 };
94 heads.insert(*space, head);
95 let ours = file.spaces.get(space);
96 // Where the version's revision `rid` meets the file: the file holds it, or holds it
97 // merged (a page the file had removed comes back as a copy in a space of its own), or
98 // it is the file's revision merged the other way, the state then the base.
99 let meets = |rid: ExGuid| {
100 let held = ours.is_some_and(|ours| {
101 ours.revisions.contains_key(&rid)
102 || ours.revisions.contains_key(&named(rid, "page"))
103 || (ours.revisions.iter())
104 .any(|(merge, revision)| *merge == merged(rid, revision.dependency))
105 }) || file.spaces.contains_key(&named(rid, "conflict"));
106 if held {
107 return Some(rid);
108 }
109 let onto = revisions.revisions.get(&rid)?.dependency;
110 (ours?.revisions.keys())
111 .find(|theirs| merged(**theirs, onto) == rid || named(**theirs, "page") == rid)
112 .copied()
113 };
114 // Failing that, as when the version's chain stops at a checkpoint, the newest state of
115 // the file's that the version passed through, or that merged one of the version's.
116 let base = chain(revisions, head).find_map(meets).or_else(|| {
117 let ours = ours?;
118 chain(ours, *ours.labels.get(&(ExGuid::default(), 1))?).find_map(|rid| {
119 if revisions.revisions.contains_key(&rid) {
120 return Some(rid);
121 }
122 let onto = ours.revisions.get(&rid)?.dependency;
123 (revisions.revisions.keys())
124 .find(|theirs| merged(**theirs, onto) == rid || named(**theirs, "page") == rid)
125 .copied()
126 })
127 });
128 if let Some(base) = base {
129 shared.insert(*space, base);
130 }
131 }
132 let head = |space: &ExGuid| heads.get(space).copied();
133 let changed: BTreeSet<ExGuid> = heads
134 .iter()
135 .filter(|(space, head)| shared.get(space) != Some(head))
136 .map(|(space, _)| *space)
137 .collect();
138 // Spaces both hold with no state in common read as the version leaves them: its page list
139 // as unchanged, so with every page it lists, and a page as one kept beside the file's when
140 // they differ.
141 let unshared: BTreeSet<ExGuid> = heads
142 .keys()
143 .filter(|space| !shared.contains_key(space) && file.spaces.contains_key(space))
144 .copied()
145 .collect();
146 // Pages with a state both share, under which the base's conflict pages are both's.
147 let common: BTreeSet<ExGuid> = shared.keys().copied().collect();
148 let listless = unshared.contains(&file.root);
149 for (space, head) in &heads {
150 if listless || unshared.contains(space) {
151 shared.entry(*space).or_insert(*head);
152 }
153 }
154 let arenas = (Arena::default(), Arena::default(), Arena::default());
155 let mut ancestor =
156 Section::open_at(&arenas.0, vec![version.to_vec(), current.to_vec()], &shared)?;
157 let mut theirs = Section::open(&arenas.1, version.to_vec())?;
158 let ours = Section::open(&arenas.2, current.to_vec())?;
159 let stored_here = |space: &ExGuid| file.spaces.contains_key(space);
160
161 let listed = theirs.pages()?;
162 let before: Vec<ExGuid> = ancestor
163 .pages()?
164 .into_iter()
165 .map(|(space, ..)| space)
166 .collect();
167 let moved = merge::moved(&mut ancestor, &mut theirs)?;
168 let mut ops = Vec::new();
169 // From the last page to the first, so that each goes before a page already placed.
170 for (at, (space, _, level)) in listed.iter().enumerate().rev() {
171 let next = listed.get(at + 1).map(|(next, ..)| *next);
172 if !stored_here(space) {
173 let page = theirs.page(*space)?;
174 let mut creation = PageCreation::new(next, titled(&page), device)?;
175 if let (Some(identity), Some(created)) = (page.identity, page.created) {
176 creation = creation.keeping(identity, created)?;
177 }
178 // The page keeps its identities, so that each merge of the version makes it alike.
179 let (creation, page) = match space.n {
180 1 => (creation.in_space(space.guid)?, page),
181 _ => (creation, page.copy()?),
182 };
183 let space = creation.space();
184 ops.push(Op::Section(SectionOp::Import { creation, page }));
185 if *level > 1 {
186 ops.push(Op::Section(SectionOp::Pages(vec![PageEdit::set_level(
187 space, *level,
188 )?])));
189 }
190 } else if moved.contains(space) {
191 ops.push(Op::Section(SectionOp::Pages(vec![PageEdit::move_to(
192 *space, next, *level,
193 )?])));
194 }
195 }
196 let kept: BTreeSet<ExGuid> = listed.iter().map(|(space, ..)| *space).collect();
197 let conflicts =
198 |section: &mut Section<'_>| -> Result<BTreeMap<ExGuid, (ExGuid, ConflictPage)>> {
199 Ok(section
200 .conflicts()?
201 .into_iter()
202 .flat_map(|(of, pages)| pages.into_iter().map(move |page| (page.space, (of, page))))
203 .collect())
204 };
205 let mut was = conflicts(&mut ancestor)?;
206 was.retain(|_, (of, _)| common.contains(of));
207 let now = conflicts(&mut theirs)?;
208 let removed: Vec<ExGuid> = before
209 .iter()
210 .filter(|space| !kept.contains(space))
211 .chain(was.keys().filter(|space| !now.contains_key(space)))
212 .copied()
213 .collect();
214 if !removed.is_empty() {
215 ops.push(Op::Section(SectionOp::Delete(removed)));
216 }
217 // Pages both hold with no state in common, or that do not lower to ops: the version's is
218 // kept beside the file's.
219 let mut unrelated = BTreeSet::new();
220 for (space, ..) in &listed {
221 if !changed.contains(space) || !stored_here(space) {
222 continue;
223 }
224 let page = theirs.page(*space)?;
225 let lowered = if unshared.contains(space) {
226 (ours.page(*space).ok().as_ref() == Some(&page)).then(Vec::new)
227 } else {
228 lower_page(&ancestor.page(*space)?, &page).ok()
229 };
230 match lowered {
231 Some(lowered) => {
232 ops.extend(lowered.into_iter().map(|op| Op::Page { space: *space, op }))
233 }
234 None => {
235 unrelated.insert(*space);
236 }
237 }
238 }
239 for (space, (of, conflict)) in now {
240 if stored_here(&space) || was.contains_key(&space) {
241 continue;
242 }
243 let page = theirs.page(space)?;
244 let user = Some(conflict.user).filter(|user| !user.is_empty());
245 ops.push(Op::Section(SectionOp::Conflict {
246 of,
247 creation: PageCreation::new(None, titled(&page), user.as_deref().unwrap_or(device))?
248 .in_space(space.guid)?,
249 page,
250 objects: conflict.objects,
251 }));
252 }
253 let edits = [PendingEdit {
254 id: 0,
255 author: device.to_owned(),
256 edit: Edit {
257 at: crate::now(),
258 ops,
259 },
260 }];
261
262 // As a queue rebases (`working::rebase`): pages the file already holds as the version
263 // leaves them are done; the rest that cannot replay become conflict pages.
264 let mut converged = BTreeSet::new();
265 loop {
266 let arena = Arena::default();
267 let mut new = Section::open(&arena, current.to_vec())?;
268 let replayed = merge::rebase(&mut ancestor, &mut new, &edits, &converged)?;
269 let mut clashes: BTreeMap<ExGuid, BTreeSet<ExGuid>> = replayed
270 .conflicts
271 .into_iter()
272 .map(|(space, (_, objects))| (space, objects))
273 .collect();
274 let settled: Vec<ExGuid> = clashes
275 .keys()
276 .filter(|space| {
277 matches!((ours.page(**space), theirs.page(**space)), (Ok(a), Ok(b)) if a == b)
278 })
279 .copied()
280 .collect();
281 if !settled.is_empty() {
282 converged.extend(settled);
283 continue;
284 }
285 for space in &unrelated {
286 clashes.entry(*space).or_default();
287 }
288 let onto = |space: &ExGuid| {
289 let labels = &file.spaces.get(space)?.labels;
290 labels.get(&(ExGuid::default(), 1)).copied()
291 };
292 let mut names: BTreeMap<ExGuid, ExGuid> = changed
293 .iter()
294 .filter_map(|space| Some((*space, merged(head(space)?, onto(space)))))
295 .collect();
296 for (space, objects) in &clashes {
297 let Ok(page) = theirs.page(*space) else {
298 continue;
299 };
300 let Some(rid) = head(space) else {
301 continue;
302 };
303 // Named after the version's page, so that every merge of it makes the same page.
304 let guid = named(rid, "conflict").guid;
305 merge::conflict_page(
306 &mut new,
307 &mut theirs,
308 &replayed.moved,
309 *space,
310 &page,
311 device,
312 objects,
313 crate::now(),
314 Some(guid),
315 )?;
316 names.insert(ExGuid { guid, n: 1 }, merged(rid, onto(space)));
317 }
318 return Ok(match new.seal_as(&names)? {
319 Some(transaction) => Merged::Publish(Box::new(transaction)),
320 None => Merged::Held,
321 });
322 }
323}
324
325/// `from` and the revisions it depends on, newest first.
326fn chain<'s>(space: &'s ObjectSpace<'_>, from: ExGuid) -> impl Iterator<Item = ExGuid> + 's {
327 std::iter::successors(Some(from), |rid| space.revisions.get(rid)?.dependency)
328}
329
330/// A page's title, where it has one, as a page made for it takes.
331fn titled(page: &onestore::page::Page) -> Option<&str> {
332 page.objects
333 .iter()
334 .any(|object| matches!(object, onestore::page::PageObject::Title(_)))
335 .then_some(page.title.as_str())
336}