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