kernoid_sync/
plan.rs

1// SPDX-License-Identifier: MIT
2//! What to do to bring a folder and a store into step – decided from three views of every path: as both sides were
3//! when they last agreed (the base), as the store is now, as the folder is now. Pure: no I/O, so every case is tested.
4//!
5//! A change on one side is carried to the other. A change on both sides is a conflict: the server's version wins the
6//! name, the local one is kept beside it as a copy – never merged, never lost (the copy is uploaded in the next round).
7//! A deletion never takes a change of the other side with it: a file deleted here but changed on the server comes
8//! back, a file deleted on the server but changed here is uploaded again. A move is a deletion and a creation (OPEN:
9//! moves as moves).
10
11use std::collections::{BTreeMap, BTreeSet};
12
13/// A path relative to the folder, `/`-separated, without a leading `/` (`Projects/plan.txt`).
14pub type RelPath = String;
15
16/// A node of the store at a path.
17#[derive(Debug, Clone, PartialEq, Eq)]
18pub struct Remote {
19    pub id: String,
20    pub directory: bool,
21    /// The content's blob; `None` for a directory.
22    pub blob: Option<String>,
23    pub size: u64,
24}
25
26/// A file or directory of the folder at a path.
27#[derive(Debug, Clone, Copy, PartialEq, Eq)]
28pub struct Local {
29    pub directory: bool,
30    pub size: u64,
31    /// Modification time, nanoseconds since 1970 – with the size, what tells a change without reading the file.
32    pub modified: i128,
33}
34
35/// A path as both sides were when they last agreed.
36#[derive(Debug, Clone, PartialEq, Eq)]
37pub struct Base {
38    pub remote: Remote,
39    pub local: Local,
40}
41
42#[derive(Debug, Clone, PartialEq, Eq)]
43pub enum Action {
44    /// Make the directory here.
45    MakeLocalDirectory(RelPath),
46    /// Make the directory in the store (its parent first).
47    MakeRemoteDirectory(RelPath),
48    /// Download the node's content to the path (replacing what is there).
49    Download { path: RelPath, id: String, blob: String },
50    /// Upload the file as a new node (`id: None`) or as new content of a node.
51    Upload { path: RelPath, id: Option<String> },
52    /// Delete here (a directory with what is in it).
53    DeleteLocal(RelPath),
54    /// Move the node to the store's trash.
55    DeleteRemote { path: RelPath, id: String },
56    /// Rename the local file to a conflict copy beside it, before the server's version is downloaded.
57    KeepLocalCopy(RelPath),
58    /// Both sides agree already (both made the same directory): remember it.
59    Adopt(RelPath),
60}
61
62/// The actions in the order they must run: local directories and copies first, then downloads; remote directories
63/// shallow before deep, then uploads; deletions deep before shallow.
64pub fn plan(
65    base: &BTreeMap<RelPath, Base>,
66    remote: &BTreeMap<RelPath, Remote>,
67    local: &BTreeMap<RelPath, Local>,
68) -> Vec<Action> {
69    let paths: BTreeSet<&RelPath> = base.keys().chain(remote.keys()).chain(local.keys()).collect();
70    let mut actions = Vec::new();
71    // Deleted directories take what is below them along; their contents need no actions of their own.
72    let mut gone_here: Vec<&str> = Vec::new();
73    let mut gone_there: Vec<&str> = Vec::new();
74    let under = |path: &str, roots: &[&str]| roots.iter().any(|root| path.starts_with(&format!("{root}/")));
75    for path in &paths {
76        let (b, r, l) = (base.get(*path), remote.get(*path), local.get(*path));
77        let remote_changed = match (b, r) {
78            (Some(b), Some(r)) => b.remote.id != r.id || b.remote.blob != r.blob || b.remote.directory != r.directory,
79            (None, Some(_)) => true,
80            _ => false,
81        };
82        let local_changed = match (b, l) {
83            (Some(b), Some(l)) => {
84                b.local.directory != l.directory
85                    || (!l.directory && (b.local.size != l.size || b.local.modified != l.modified))
86            }
87            (None, Some(_)) => true,
88            _ => false,
89        };
90        if under(path, &gone_here) || under(path, &gone_there) {
91            continue;
92        }
93        match (b, r, l) {
94            (_, None, None) => {}
95            // New on one side only.
96            (None, Some(r), None) => actions.push(fetch(path, r)),
97            (None, None, Some(l)) => actions.push(send(path, l, None)),
98            // New on both sides.
99            (None, Some(r), Some(l)) => {
100                if r.directory && l.directory {
101                    actions.push(Action::Adopt((*path).clone()));
102                } else {
103                    // Two files, or a file and a directory, of one name: the server's keeps the name.
104                    actions.push(Action::KeepLocalCopy((*path).clone()));
105                    actions.push(fetch(path, r));
106                }
107            }
108            // Known to both before.
109            (Some(_), Some(r), Some(l)) => match (remote_changed, local_changed) {
110                (false, false) => {}
111                (true, false) => {
112                    // A file replaced by a directory on the server, or the other way round.
113                    if l.directory != r.directory {
114                        actions.push(Action::DeleteLocal((*path).clone()));
115                    }
116                    actions.push(fetch(path, r));
117                }
118                (false, true) => {
119                    if r.directory && !l.directory {
120                        // A directory replaced by a file here.
121                        actions.push(Action::KeepLocalCopy((*path).clone()));
122                        actions.push(fetch(path, r));
123                    } else if !l.directory {
124                        actions.push(send(path, l, Some(r.id.clone())));
125                    }
126                }
127                (true, true) => {
128                    if r.directory && l.directory {
129                        actions.push(Action::Adopt((*path).clone()));
130                    } else {
131                        actions.push(Action::KeepLocalCopy((*path).clone()));
132                        actions.push(fetch(path, r));
133                    }
134                }
135            },
136            // Gone on the server.
137            (Some(b), None, Some(l)) => {
138                if local_changed || (l.directory && changed_below(path, base, local)) {
139                    actions.push(send(path, l, None));
140                } else {
141                    actions.push(Action::DeleteLocal((*path).clone()));
142                    if b.local.directory {
143                        gone_here.push(path);
144                    }
145                }
146            }
147            // Gone here.
148            (Some(b), Some(r), None) => {
149                if remote_changed || (r.directory && changed_below(path, base, remote)) {
150                    actions.push(fetch(path, r));
151                } else {
152                    actions.push(Action::DeleteRemote { path: (*path).clone(), id: r.id.clone() });
153                    if b.remote.directory {
154                        gone_there.push(path);
155                    }
156                }
157            }
158        }
159    }
160    order(actions)
161}
162
163fn fetch(path: &RelPath, remote: &Remote) -> Action {
164    if remote.directory {
165        Action::MakeLocalDirectory(path.clone())
166    } else {
167        Action::Download { path: path.clone(), id: remote.id.clone(), blob: remote.blob.clone().unwrap_or_default() }
168    }
169}
170
171fn send(path: &RelPath, local: &Local, id: Option<String>) -> Action {
172    if local.directory { Action::MakeRemoteDirectory(path.clone()) } else { Action::Upload { path: path.clone(), id } }
173}
174
175/// Whether anything below a directory changed on the side `now` describes, against the base.
176fn changed_below<T: Changed>(directory: &str, base: &BTreeMap<RelPath, Base>, now: &BTreeMap<RelPath, T>) -> bool {
177    let prefix = format!("{directory}/");
178    now.iter().filter(|(path, _)| path.starts_with(&prefix)).any(|(path, node)| match base.get(path) {
179        Some(base) => node.differs(base),
180        None => true,
181    })
182}
183
184trait Changed {
185    fn differs(&self, base: &Base) -> bool;
186}
187
188impl Changed for Local {
189    fn differs(&self, base: &Base) -> bool {
190        base.local.directory != self.directory
191            || (!self.directory && (base.local.size != self.size || base.local.modified != self.modified))
192    }
193}
194
195impl Changed for Remote {
196    fn differs(&self, base: &Base) -> bool {
197        base.remote.id != self.id || base.remote.blob != self.blob
198    }
199}
200
201fn depth(path: &str) -> usize {
202    path.matches('/').count()
203}
204
205fn order(actions: Vec<Action>) -> Vec<Action> {
206    let rank = |action: &Action| -> (u8, isize) {
207        match action {
208            Action::KeepLocalCopy(path) => (0, depth(path) as isize),
209            Action::DeleteLocal(path) => (1, -(depth(path) as isize)),
210            Action::MakeLocalDirectory(path) => (2, depth(path) as isize),
211            Action::Download { path, .. } => (3, depth(path) as isize),
212            Action::MakeRemoteDirectory(path) => (4, depth(path) as isize),
213            Action::Upload { path, .. } => (5, depth(path) as isize),
214            Action::DeleteRemote { path, .. } => (6, -(depth(path) as isize)),
215            Action::Adopt(path) => (7, depth(path) as isize),
216        }
217    };
218    let mut actions = actions;
219    actions.sort_by_key(rank);
220    actions
221}
222
223#[cfg(test)]
224mod tests {
225    use super::*;
226
227    fn file(id: &str, blob: &str) -> Remote {
228        Remote { id: id.into(), directory: false, blob: Some(blob.into()), size: 1 }
229    }
230    fn dir(id: &str) -> Remote {
231        Remote { id: id.into(), directory: true, blob: None, size: 0 }
232    }
233    fn here(size: u64, modified: i128) -> Local {
234        Local { directory: false, size, modified }
235    }
236    fn here_dir() -> Local {
237        Local { directory: true, size: 0, modified: 0 }
238    }
239    fn map<T: Clone>(entries: &[(&str, T)]) -> BTreeMap<RelPath, T> {
240        entries.iter().map(|(path, value)| ((*path).to_owned(), value.clone())).collect()
241    }
242    fn agreed(entries: &[(&str, Remote, Local)]) -> BTreeMap<RelPath, Base> {
243        entries.iter().map(|(p, r, l)| ((*p).to_owned(), Base { remote: r.clone(), local: *l })).collect()
244    }
245
246    #[test]
247    fn nothing_changed_nothing_to_do() {
248        let base = agreed(&[("a.txt", file("n1", "b1"), here(1, 10)), ("D", dir("n2"), here_dir())]);
249        let remote = map(&[("a.txt", file("n1", "b1")), ("D", dir("n2"))]);
250        let local = map(&[("a.txt", here(1, 10)), ("D", here_dir())]);
251        assert!(plan(&base, &remote, &local).is_empty());
252    }
253
254    #[test]
255    fn the_first_round_brings_both_sides_together() {
256        let remote = map(&[("D", dir("n1")), ("D/x.txt", file("n2", "b2")), ("same", dir("n3"))]);
257        let local = map(&[("E", here_dir()), ("E/y.txt", here(3, 1)), ("same", here_dir())]);
258        assert_eq!(
259            plan(&BTreeMap::new(), &remote, &local),
260            [
261                Action::MakeLocalDirectory("D".into()),
262                Action::Download { path: "D/x.txt".into(), id: "n2".into(), blob: "b2".into() },
263                Action::MakeRemoteDirectory("E".into()),
264                Action::Upload { path: "E/y.txt".into(), id: None },
265                Action::Adopt("same".into()),
266            ]
267        );
268    }
269
270    #[test]
271    fn a_change_goes_to_the_other_side() {
272        let base = agreed(&[("a", file("n1", "b1"), here(1, 10)), ("b", file("n2", "b2"), here(1, 10))]);
273        let remote = map(&[("a", file("n1", "b9")), ("b", file("n2", "b2"))]);
274        let local = map(&[("a", here(1, 10)), ("b", here(2, 11))]);
275        assert_eq!(
276            plan(&base, &remote, &local),
277            [
278                Action::Download { path: "a".into(), id: "n1".into(), blob: "b9".into() },
279                Action::Upload { path: "b".into(), id: Some("n2".into()) },
280            ]
281        );
282    }
283
284    #[test]
285    fn a_change_on_both_sides_keeps_both() {
286        let base = agreed(&[("a", file("n1", "b1"), here(1, 10))]);
287        let remote = map(&[("a", file("n1", "b2"))]);
288        let local = map(&[("a", here(5, 20))]);
289        assert_eq!(
290            plan(&base, &remote, &local),
291            [
292                Action::KeepLocalCopy("a".into()),
293                Action::Download { path: "a".into(), id: "n1".into(), blob: "b2".into() },
294            ]
295        );
296        // New on both sides, never seen before: the same.
297        let remote = map(&[("n", file("n5", "b5"))]);
298        let local = map(&[("n", here(1, 1))]);
299        assert_eq!(plan(&BTreeMap::new(), &remote, &local)[0], Action::KeepLocalCopy("n".into()));
300    }
301
302    #[test]
303    fn deletions_carry_over_but_never_take_a_change_along() {
304        let base = agreed(&[
305            ("gone-there", file("n1", "b1"), here(1, 10)),
306            ("gone-here", file("n2", "b2"), here(1, 10)),
307            ("gone-there-changed-here", file("n3", "b3"), here(1, 10)),
308            ("gone-here-changed-there", file("n4", "b4"), here(1, 10)),
309        ]);
310        let remote = map(&[("gone-here", file("n2", "b2")), ("gone-here-changed-there", file("n4", "b5"))]);
311        let local = map(&[("gone-there", here(1, 10)), ("gone-there-changed-here", here(7, 11))]);
312        assert_eq!(
313            plan(&base, &remote, &local),
314            [
315                Action::DeleteLocal("gone-there".into()),
316                Action::Download { path: "gone-here-changed-there".into(), id: "n4".into(), blob: "b5".into() },
317                Action::Upload { path: "gone-there-changed-here".into(), id: None },
318                Action::DeleteRemote { path: "gone-here".into(), id: "n2".into() },
319            ]
320        );
321    }
322
323    #[test]
324    fn a_deleted_directory_goes_whole_unless_something_in_it_changed() {
325        let base = agreed(&[
326            ("D", dir("n1"), here_dir()),
327            ("D/a", file("n2", "b2"), here(1, 10)),
328            ("E", dir("n3"), here_dir()),
329            ("E/b", file("n4", "b4"), here(1, 10)),
330        ]);
331        // D gone on the server, unchanged here: deleted here, with what is in it. E gone on the server, but E/b
332        // changed here: E and E/b go up again.
333        let remote = BTreeMap::new();
334        let local = map(&[("D", here_dir()), ("D/a", here(1, 10)), ("E", here_dir()), ("E/b", here(2, 12))]);
335        assert_eq!(
336            plan(&base, &remote, &local),
337            [
338                Action::DeleteLocal("D".into()),
339                Action::MakeRemoteDirectory("E".into()),
340                Action::Upload { path: "E/b".into(), id: None },
341            ]
342        );
343        // The same the other way round.
344        let remote = map(&[("D", dir("n1")), ("D/a", file("n2", "b2")), ("E", dir("n3")), ("E/b", file("n4", "b9"))]);
345        assert_eq!(
346            plan(&base, &remote, &BTreeMap::new()),
347            [
348                Action::MakeLocalDirectory("E".into()),
349                Action::Download { path: "E/b".into(), id: "n4".into(), blob: "b9".into() },
350                Action::DeleteRemote { path: "D".into(), id: "n1".into() },
351            ]
352        );
353    }
354
355    #[test]
356    fn deep_directories_are_made_after_their_parents_and_deleted_before() {
357        let remote = map(&[("A/B/C", dir("c")), ("A", dir("a")), ("A/B", dir("b"))]);
358        let made = plan(&BTreeMap::new(), &remote, &BTreeMap::new());
359        assert_eq!(
360            made,
361            [
362                Action::MakeLocalDirectory("A".into()),
363                Action::MakeLocalDirectory("A/B".into()),
364                Action::MakeLocalDirectory("A/B/C".into()),
365            ]
366        );
367    }
368}
kernoid_sync/plan.rs

kernoid_sync/
plan.rs
