| 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 | |
| 14 | use crate::{PendingEdit, Result, merge}; |
| 15 | use onestore::{ |
| 16 | Arena, ConflictPage, ExGuid, ObjectSpace, PageCreation, PageEdit, RevisionIndex, Section, |
| 17 | Store, Transaction, |
| 18 | op::{Edit, Op, SectionOp, lower_page}, |
| 19 | }; |
| 20 | use sha2::{Digest, Sha256}; |
| 21 | use 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)] |
| 25 | pub 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. |
| 34 | pub(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. |
| 45 | fn 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. |
| 61 | fn 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. |
| 78 | pub(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. |
| 326 | fn 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. |
| 331 | fn 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 | } |