OXYGENHUB
# 8b7986dd3cb0 oxygen / crates / oxy-core / src / tree.rs
40.7 KiB · Rust · last changed Tree views updated in place, and a faster render of edited files 1 month ago source blame history raw
1 
//! The tree graph: nodes, placements, and modes as atoms (spec §7.1, §7.2),
2 
//! with tree conflict detection and path assignment (spec §9.2).
3
4 
use crate::hash::ChangeHash;
5 
use crate::ids::NodeId;
6 
use crate::objects::{Mode, NodeKind, OpRef, TreeOp};
7 
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
8
9 
/// `(change, index into that change's tree_ops)`.
10 
pub type OpKey = (ChangeHash, u32);
11
12 
#[derive(Clone, Debug, PartialEq, Eq)]
13 
pub struct Placement {
14 
    pub node: NodeId,
15 
    pub parent: NodeId,
16 
    pub name: String,
17 
}
18
19 
#[derive(Clone, Debug, Default)]
20 
pub struct TreeGraph {
21 
    kinds: HashMap<NodeId, NodeKind>,
22 
    introduced: HashMap<NodeId, ChangeHash>,
23 
    placements: HashMap<OpKey, Placement>,
24 
    modes: HashMap<OpKey, (NodeId, Mode)>,
25 
    /// Placement atoms retired by `RemoveNode`/`Move`, and mode atoms retired
26 
    /// by `SetMode`. Kept apart because `AddNode` introduces one of each
27 
    /// under the same key.
28 
    deleted_placements: HashMap<OpKey, BTreeSet<ChangeHash>>,
29 
    deleted_modes: HashMap<OpKey, BTreeSet<ChangeHash>>,
30 
    placements_of: HashMap<NodeId, BTreeSet<OpKey>>,
31 
    modes_of: HashMap<NodeId, BTreeSet<OpKey>>,
32 
    /// The live subsets of `placements_of` and `modes_of`, kept as changes
33 
    /// apply, so the view walks what is live rather than all history.
34 
    live_placements_of: HashMap<NodeId, BTreeSet<OpKey>>,
35 
    live_modes_of: HashMap<NodeId, BTreeSet<OpKey>>,
36 
    /// The view, once computed, with the path of each directory in it;
37 
    /// kept up to date as ops apply when that is simple (see
38 
    /// `update_view`), cleared otherwise.
39 
    view_cache: std::sync::OnceLock<CachedView>,
40 
}
41
42 
#[derive(Clone, Debug, PartialEq, Eq)]
43 
pub enum TreeConflict {
44 
    /// Two live nodes share `(parent, name)`.
45 
    Name {
46 
        parent: NodeId,
47 
        name: String,
48 
        nodes: Vec<NodeId>,
49 
    },
50 
    /// One node has several live placements.
51 
    MultiPlacement {
52 
        node: NodeId,
53 
        placements: Vec<OpKey>,
54 
    },
55 
    /// A live node's parent is not live.
56 
    Orphan { node: NodeId, parent: NodeId },
57 
    /// A directory is placed inside its own descendant.
58 
    Cycle { node: NodeId },
59 
    /// Several live mode atoms.
60 
    Mode { node: NodeId, modes: Vec<Mode> },
61 
}
62
63 
/// A node as it appears in the working copy.
64 
#[derive(Clone, Debug, PartialEq, Eq)]
65 
pub struct TreeEntry {
66 
    pub path: String,
67 
    pub node: NodeId,
68 
    pub kind: NodeKind,
69 
    pub mode: Mode,
70 
    /// The placement this entry materializes (for building `RemoveNode`/`Move`).
71 
    pub placement: OpKey,
72 
    /// The live mode atom (for building `SetMode`).
73 
    pub mode_atom: Option<OpKey>,
74 
}
75
76 
#[derive(Clone, Debug, Default)]
77 
struct CachedView {
78 
    view: TreeView,
79 
    dirs: HashMap<NodeId, String>,
80 
}
81
82 
impl CachedView {
83 
    fn new(view: TreeView) -> CachedView {
84 
        let mut dirs: HashMap<NodeId, String> = view
85 
            .entries
86 
            .values()
87 
            .filter(|e| e.kind == NodeKind::Dir)
88 
            .map(|e| (e.node, e.path.clone()))
89 
            .collect();
90 
        dirs.insert(NodeId::ROOT, String::new());
91 
        CachedView { view, dirs }
92 
    }
93 
}
94
95 
#[derive(Clone, Debug, Default, PartialEq, Eq)]
96 
pub struct TreeView {
97 
    /// Path → entry, paths use `/` and have no leading slash; conflicted
98 
    /// entries carry a `.oxy-conflict-<n>` suffix. Shared, so a view is
99 
    /// cheap to clone.
100 
    pub entries: std::sync::Arc<BTreeMap<String, TreeEntry>>,
101 
    pub conflicts: Vec<TreeConflict>,
102 
}
103
104 
impl TreeView {
105 
    pub fn is_conflicted(&self) -> bool {
106 
        !self.conflicts.is_empty()
107 
    }
108 
    pub fn by_node(&self) -> HashMap<NodeId, &TreeEntry> {
109 
        self.entries.values().map(|e| (e.node, e)).collect()
110 
    }
111 
}
112
113 
impl TreeGraph {
114 
    pub fn new() -> Self {
115 
        Self::default()
116 
    }
117
118 
    /// Apply tree op `index` of `change`; `OpRef` self references must already be resolved.
119 
    pub fn apply(&mut self, change: ChangeHash, index: u32, op: &TreeOp) {
120 
        let cached = self.view_cache.take();
121 
        // Whether the placement or mode atom this op retires was live.
122 
        let was_live = match op {
123 
            TreeOp::RemoveNode { placement, .. } => self.placement_live(&op_key(*placement)),
124 
            TreeOp::Move { old, .. } => self.placement_live(&op_key(*old)),
125 
            TreeOp::SetMode { old, .. } => self.mode_live(&op_key(*old)),
126 
            TreeOp::AddNode { .. } => false,
127 
        };
128 
        self.apply_to_graph(change, index, op);
129 
        if let Some(mut c) = cached {
130 
            if self.update_view(&mut c, (change, index), op, was_live) {
131 
                #[cfg(test)]
132 
                assert_eq!(
133 
                    c.view,
134 
                    self.compute_view(),
135 
                    "view kept up to date by {op:?}"
136 
                );
137 
                self.view_cache = std::sync::OnceLock::from(c);
138 
            }
139 
        }
140 
    }
141
142 
    fn apply_to_graph(&mut self, change: ChangeHash, index: u32, op: &TreeOp) {
143 
        let key = (change, index);
144 
        match op {
145 
            TreeOp::AddNode {
146 
                node,
147 
                kind,
148 
                mode,
149 
                parent,
150 
                name,
151 
            } => {
152 
                self.kinds.insert(*node, *kind);
153 
                self.introduced.insert(*node, change);
154 
                self.placements.insert(
155 
                    key,
156 
                    Placement {
157 
                        node: *node,
158 
                        parent: *parent,
159 
                        name: name.clone(),
160 
                    },
161 
                );
162 
                self.placements_of.entry(*node).or_default().insert(key);
163 
                self.index_placement(key);
164 
                if *kind != NodeKind::Dir {
165 
                    self.modes.insert(key, (*node, *mode));
166 
                    self.modes_of.entry(*node).or_default().insert(key);
167 
                    self.index_mode(key);
168 
                }
169 
            }
170 
            TreeOp::RemoveNode { placement, .. } => {
171 
                self.deleted_placements
172 
                    .entry(op_key(*placement))
173 
                    .or_default()
174 
                    .insert(change);
175 
                self.index_placement(op_key(*placement));
176 
            }
177 
            TreeOp::Move {
178 
                node,
179 
                old,
180 
                parent,
181 
                name,
182 
            } => {
183 
                self.deleted_placements
184 
                    .entry(op_key(*old))
185 
                    .or_default()
186 
                    .insert(change);
187 
                self.index_placement(op_key(*old));
188 
                self.placements.insert(
189 
                    key,
190 
                    Placement {
191 
                        node: *node,
192 
                        parent: *parent,
193 
                        name: name.clone(),
194 
                    },
195 
                );
196 
                self.placements_of.entry(*node).or_default().insert(key);
197 
                self.index_placement(key);
198 
            }
199 
            TreeOp::SetMode { node, old, mode } => {
200 
                self.deleted_modes
201 
                    .entry(op_key(*old))
202 
                    .or_default()
203 
                    .insert(change);
204 
                self.index_mode(op_key(*old));
205 
                self.modes.insert(key, (*node, *mode));
206 
                self.modes_of.entry(*node).or_default().insert(key);
207 
                self.index_mode(key);
208 
            }
209 
        }
210 
    }
211
212 
    /// Bring the cached view `c` up to date with `op` (already applied as
213 
    /// `key`) where that is simple and the view has no conflicts; false
214 
    /// when it must be computed again. `was_live`: whether the placement or
215 
    /// mode atom `op` retires was live before it.
216 
    fn update_view(&self, c: &mut CachedView, key: OpKey, op: &TreeOp, was_live: bool) -> bool {
217 
        if !c.view.conflicts.is_empty() {
218 
            return false;
219 
        }
220 
        match op {
221 
            TreeOp::AddNode { node, .. } => self.view_add(c, *node, key),
222 
            TreeOp::RemoveNode { node, placement } => {
223 
                !was_live || self.view_remove(c, *node, op_key(*placement))
224 
            }
225 
            TreeOp::Move { node, old, .. } => {
226 
                (!was_live || self.view_remove(c, *node, op_key(*old)))
227 
                    && self.view_add(c, *node, key)
228 
            }
229 
            TreeOp::SetMode { node, .. } => {
230 
                let live = self.live_placements(node);
231 
                match live.as_slice() {
232 
                    [] => true,
233 
                    [(k, p)] => {
234 
                        let Some(path) = c.dirs.get(&p.parent).map(|d| join(d, &p.name)) else {
235 
                            return false;
236 
                        };
237 
                        let Some(mode) = self.entry_mode(node) else {
238 
                            return false;
239 
                        };
240 
                        let entries = std::sync::Arc::make_mut(&mut c.view.entries);
241 
                        match entries.get_mut(&path) {
242 
                            Some(e) if e.node == *node && e.placement == *k => {
243 
                                (e.mode_atom, e.mode) = mode;
244 
                                true
245 
                            }
246 
                            _ => false,
247 
                        }
248 
                    }
249 
                    _ => false,
250 
                }
251 
            }
252 
        }
253 
    }
254
255 
    /// The view entry for `node`'s placement `key`, just made live.
256 
    fn view_add(&self, c: &mut CachedView, node: NodeId, key: OpKey) -> bool {
257 
        if !self.placement_live(&key) {
258 
            return true;
259 
        }
260 
        if self
261 
            .live_placements_of
262 
            .get(&node)
263 
            .is_none_or(|s| s.len() != 1)
264 
        {
265 
            return false;
266 
        }
267 
        let Some(p) = self.placements.get(&key) else {
268 
            return false;
269 
        };
270 
        let Some(path) = c.dirs.get(&p.parent).map(|d| join(d, &p.name)) else {
271 
            return false;
272 
        };
273 
        let Some((mode_atom, mode)) = self.entry_mode(&node) else {
274 
            return false;
275 
        };
276 
        let kind = self.kind(&node).unwrap_or(NodeKind::File);
277 
        let entries = std::sync::Arc::make_mut(&mut c.view.entries);
278 
        if entries.contains_key(&path) || node == NodeId::ROOT {
279 
            return false;
280 
        }
281 
        // Nothing can be placed under a directory that was not in the view
282 
        // yet: it would have been an orphan, and the view had no conflicts.
283 
        if kind == NodeKind::Dir {
284 
            c.dirs.insert(node, path.clone());
285 
        }
286 
        entries.insert(
287 
            path.clone(),
288 
            TreeEntry {
289 
                path,
290 
                node,
291 
                kind,
292 
                mode,
293 
                placement: key,
294 
                mode_atom,
295 
            },
296 
        );
297 
        true
298 
    }
299
300 
    /// Drop the view entry of `node`'s placement `key`, just retired.
301 
    fn view_remove(&self, c: &mut CachedView, node: NodeId, key: OpKey) -> bool {
302 
        if self.live_placements_of.contains_key(&node) {
303 
            return false;
304 
        }
305 
        let Some(p) = self.placements.get(&key) else {
306 
            return false;
307 
        };
308 
        let Some(path) = c.dirs.get(&p.parent).map(|d| join(d, &p.name)) else {
309 
            return false;
310 
        };
311 
        let entries = std::sync::Arc::make_mut(&mut c.view.entries);
312 
        match entries.get(&path) {
313 
            Some(e) if e.node == node && e.placement == key => {}
314 
            _ => return false,
315 
        }
316 
        if entries.get(&path).is_some_and(|e| e.kind == NodeKind::Dir) {
317 
            let prefix = format!("{path}/");
318 
            if entries
319 
                .range(prefix.clone()..)
320 
                .next()
321 
                .is_some_and(|(k, _)| k.starts_with(&prefix))
322 
            {
323 
                return false;
324 
            }
325 
            c.dirs.remove(&node);
326 
        }
327 
        entries.remove(&path);
328 
        true
329 
    }
330
331 
    /// The mode atom and mode of `node`'s entry, as `compute_view` finds
332 
    /// them; `None` when its live modes conflict.
333 
    fn entry_mode(&self, node: &NodeId) -> Option<(Option<OpKey>, Mode)> {
334 
        let lm = self.live_modes(node);
335 
        let distinct: BTreeSet<Mode> = lm.iter().map(|(_, m)| *m).collect();
336 
        if distinct.len() > 1 {
337 
            return None;
338 
        }
339 
        let mode_atom = lm.iter().map(|(k, _)| *k).max();
340 
        let mode = mode_atom
341 
            .and_then(|k| self.modes.get(&k).map(|(_, m)| *m))
342 
            .unwrap_or_default();
343 
        Some((mode_atom, mode))
344 
    }
345
346 
    /// Bring placement `k` in the live index up to date.
347 
    fn index_placement(&mut self, k: OpKey) {
348 
        let Some(node) = self.placements.get(&k).map(|p| p.node) else {
349 
            return;
350 
        };
351 
        if self.placement_live(&k) {
352 
            self.live_placements_of.entry(node).or_default().insert(k);
353 
        } else if let Some(set) = self.live_placements_of.get_mut(&node) {
354 
            set.remove(&k);
355 
            if set.is_empty() {
356 
                self.live_placements_of.remove(&node);
357 
            }
358 
        }
359 
    }
360
361 
    /// Bring mode atom `k` in the live index up to date.
362 
    fn index_mode(&mut self, k: OpKey) {
363 
        let Some(node) = self.modes.get(&k).map(|(n, _)| *n) else {
364 
            return;
365 
        };
366 
        if self.mode_live(&k) {
367 
            self.live_modes_of.entry(node).or_default().insert(k);
368 
        } else if let Some(set) = self.live_modes_of.get_mut(&node) {
369 
            set.remove(&k);
370 
            if set.is_empty() {
371 
                self.live_modes_of.remove(&node);
372 
            }
373 
        }
374 
    }
375
376 
    /// Directories no longer placed anywhere, by the (parent, name) they
377 
    /// were last placed at, with that placement: what an import can bring
378 
    /// back rather than make a second node for one Git path.
379 
    pub fn dead_dirs(&self) -> HashMap<(NodeId, String), (NodeId, OpKey)> {
380 
        let mut out: HashMap<(NodeId, String), (NodeId, OpKey)> = HashMap::new();
381 
        for (k, p) in &self.placements {
382 
            if self.kind(&p.node) != Some(NodeKind::Dir)
383 
                || self.placement_live(k)
384 
                || !self.live_placements(&p.node).is_empty()
385 
            {
386 
                continue;
387 
            }
388 
            let slot = out
389 
                .entry((p.parent, p.name.clone()))
390 
                .or_insert((p.node, *k));
391 
            // The newest placement, by key: the same answer in any order.
392 
            if *k > slot.1 {
393 
                *slot = (p.node, *k);
394 
            }
395 
        }
396 
        out
397 
    }
398
399 
    /// Every placement `node` ever had, live or not, with the changes that
400 
    /// retired it (none while live).
401 
    pub fn placement_history(&self, node: &NodeId) -> Vec<(OpKey, &Placement, Vec<ChangeHash>)> {
402 
        self.placements_of
403 
            .get(node)
404 
            .into_iter()
405 
            .flatten()
406 
            .filter_map(|k| {
407 
                let p = self.placements.get(k)?;
408 
                let by = self
409 
                    .deleted_placements
410 
                    .get(k)
411 
                    .map(|d| d.iter().copied().collect())
412 
                    .unwrap_or_default();
413 
                Some((*k, p, by))
414 
            })
415 
            .collect()
416 
    }
417
418 
    fn placement_live(&self, k: &OpKey) -> bool {
419 
        self.deleted_placements.get(k).is_none_or(|d| d.is_empty())
420 
    }
421 
    fn mode_live(&self, k: &OpKey) -> bool {
422 
        self.deleted_modes.get(k).is_none_or(|d| d.is_empty())
423 
    }
424
425 
    pub fn kind(&self, node: &NodeId) -> Option<NodeKind> {
426 
        if node.is_root() {
427 
            Some(NodeKind::Dir)
428 
        } else {
429 
            self.kinds.get(node).copied()
430 
        }
431 
    }
432
433 
    /// The change whose `AddNode` introduced `node`.
434 
    pub fn introducer(&self, node: &NodeId) -> Option<ChangeHash> {
435 
        self.introduced.get(node).copied()
436 
    }
437
438 
    pub fn placement(&self, k: &OpKey) -> Option<&Placement> {
439 
        self.placements.get(k)
440 
    }
441
442 
    pub fn live_placements(&self, node: &NodeId) -> Vec<(OpKey, &Placement)> {
443 
        self.live_placements_of
444 
            .get(node)
445 
            .into_iter()
446 
            .flat_map(|ks| ks.iter())
447 
            .filter_map(|k| self.placements.get(k).map(|p| (*k, p)))
448 
            .collect()
449 
    }
450
451 
    pub fn live_modes(&self, node: &NodeId) -> Vec<(OpKey, Mode)> {
452 
        self.live_modes_of
453 
            .get(node)
454 
            .into_iter()
455 
            .flat_map(|ks| ks.iter())
456 
            .filter_map(|k| self.modes.get(k).map(|(_, m)| (*k, *m)))
457 
            .collect()
458 
    }
459
460 
    /// Every node that has at least one live placement.
461 
    pub fn placed_nodes(&self) -> impl Iterator<Item = NodeId> + '_ {
462 
        self.live_placements_of.keys().copied()
463 
    }
464
465 
    /// Resolve the tree: assign paths, find conflicts.
466 
    /// The materialized tree (spec §7.1): computed once per graph and
467 
    /// cloned for each caller.
468 
    pub fn view(&self) -> TreeView {
469 
        self.view_cache
470 
            .get_or_init(|| CachedView::new(self.compute_view()))
471 
            .view
472 
            .clone()
473 
    }
474
475 
    fn compute_view(&self) -> TreeView {
476 
        let mut view = TreeView::default();
477 
        let mut entries: BTreeMap<String, TreeEntry> = BTreeMap::new();
478
479 
        // Live placements grouped by parent.
480 
        let mut children: HashMap<NodeId, Vec<(OpKey, &Placement)>> = HashMap::new();
481 
        for ks in self.live_placements_of.values() {
482 
            for k in ks {
483 
                if let Some(p) = self.placements.get(k) {
484 
                    children.entry(p.parent).or_default().push((*k, p));
485 
                }
486 
            }
487 
        }
488 
        for c in children.values_mut() {
489 
            c.sort_by(|a, b| a.1.name.cmp(&b.1.name).then(a.0.cmp(&b.0)));
490 
        }
491
492 
        // Multi-placement and mode conflicts.
493 
        // Only placed nodes: one with no live placement is not in the tree.
494 
        let mut nodes: Vec<NodeId> = self.live_placements_of.keys().copied().collect();
495 
        nodes.sort();
496 
        let mut multi: HashSet<NodeId> = HashSet::new();
497 
        // Each node's mode and the atom it comes from, for the entries.
498 
        let mut modes: HashMap<NodeId, (Option<OpKey>, Mode)> = HashMap::new();
499 
        for n in &nodes {
500 
            let lp = self.live_placements(n);
501 
            // One placement (nearly every node) cannot be in two places.
502 
            if lp.len() > 1 {
503 
                let distinct_places: BTreeSet<(&NodeId, &str)> = lp
504 
                    .iter()
505 
                    .map(|(_, p)| (&p.parent, p.name.as_str()))
506 
                    .collect();
507 
                if distinct_places.len() > 1 {
508 
                    multi.insert(*n);
509 
                    view.conflicts.push(TreeConflict::MultiPlacement {
510 
                        node: *n,
511 
                        placements: lp.iter().map(|(k, _)| *k).collect(),
512 
                    });
513 
                }
514 
            }
515 
            let lm = self.live_modes(n);
516 
            if lm.len() > 1 {
517 
                let distinct_modes: BTreeSet<Mode> = lm.iter().map(|(_, m)| *m).collect();
518 
                if distinct_modes.len() > 1 {
519 
                    view.conflicts.push(TreeConflict::Mode {
520 
                        node: *n,
521 
                        modes: distinct_modes.into_iter().collect(),
522 
                    });
523 
                }
524 
            }
525 
            let mode_atom = lm.iter().map(|(k, _)| *k).max();
526 
            let mode = mode_atom
527 
                .and_then(|k| self.modes.get(&k).map(|(_, m)| *m))
528 
                .unwrap_or_default();
529 
            modes.insert(*n, (mode_atom, mode));
530 
        }
531
532 
        // BFS from the root, assigning paths.
533 
        let mut reached: HashSet<NodeId> = HashSet::new();
534 
        reached.insert(NodeId::ROOT);
535 
        let mut queue: Vec<(NodeId, String)> = vec![(NodeId::ROOT, String::new())];
536 
        let mut on_path: HashSet<NodeId> = HashSet::new();
537 
        while let Some((dir, dir_path)) = queue.pop() {
538 
            let Some(kids) = children.get(&dir) else {
539 
                continue;
540 
            };
541 
            // Name conflicts within this directory: the children are sorted
542 
            // by name, so each name's group is a run of them.
543 
            let mut groups: Vec<(&str, &[(OpKey, &Placement)])> = Vec::new();
544 
            let mut start = 0;
545 
            for i in 1..=kids.len() {
546 
                if i == kids.len() || kids[i].1.name != kids[start].1.name {
547 
                    groups.push((kids[start].1.name.as_str(), &kids[start..i]));
548 
                    start = i;
549 
                }
550 
            }
551 
            for (name, group) in groups {
552 
                let distinct: BTreeSet<NodeId> = group.iter().map(|(_, p)| p.node).collect();
553 
                if distinct.len() > 1 {
554 
                    view.conflicts.push(TreeConflict::Name {
555 
                        parent: dir,
556 
                        name: name.to_string(),
557 
                        nodes: distinct.iter().copied().collect(),
558 
                    });
559 
                }
560 
                let suffixed = distinct.len() > 1;
561 
                for (i, (k, p)) in group.iter().enumerate() {
562 
                    let node = p.node;
563 
                    if node == dir || on_path.contains(&node) {
564 
                        view.conflicts.push(TreeConflict::Cycle { node });
565 
                        continue;
566 
                    }
567 
                    let needs_suffix = suffixed || multi.contains(&node);
568 
                    let leaf = if needs_suffix {
569 
                        format!("{name}.oxy-conflict-{}", i + 1)
570 
                    } else {
571 
                        name.to_string()
572 
                    };
573 
                    let path = if dir_path.is_empty() {
574 
                        leaf
575 
                    } else {
576 
                        format!("{dir_path}/{leaf}")
577 
                    };
578 
                    let kind = self.kind(&node).unwrap_or(NodeKind::File);
579 
                    let (mode_atom, mode) = modes.get(&node).copied().unwrap_or_default();
580 
                    entries.insert(
581 
                        path.clone(),
582 
                        TreeEntry {
583 
                            path: path.clone(),
584 
                            node,
585 
                            kind,
586 
                            mode,
587 
                            placement: *k,
588 
                            mode_atom,
589 
                        },
590 
                    );
591 
                    if kind == NodeKind::Dir && reached.insert(node) {
592 
                        on_path.insert(dir);
593 
                        queue.push((node, path));
594 
                    } else {
595 
                        reached.insert(node);
596 
                    }
597 
                }
598 
            }
599 
        }
600
601 
        // Nodes with live placements that were never reached: orphans or cycles.
602 
        for n in &nodes {
603 
            if reached.contains(n) {
604 
                continue;
605 
            }
606 
            let lp = self.live_placements(n);
607 
            if lp.is_empty() {
608 
                continue;
609 
            }
610 
            let mut seen = HashSet::new();
611 
            let mut cur = *n;
612 
            let conflict = loop {
613 
                if !seen.insert(cur) {
614 
                    break TreeConflict::Cycle { node: *n };
615 
                }
616 
                let lp = self.live_placements(&cur);
617 
                let Some((_, p)) = lp.first() else {
618 
                    break TreeConflict::Orphan {
619 
                        node: *n,
620 
                        parent: cur,
621 
                    };
622 
                };
623 
                if reached.contains(&p.parent) {
624 
                    // Parent reached but this node was not: the parent is not a
625 
                    // directory, so this is a name/kind problem surfaced as orphan.
626 
                    break TreeConflict::Orphan {
627 
                        node: *n,
628 
                        parent: p.parent,
629 
                    };
630 
                }
631 
                cur = p.parent;
632 
            };
633 
            if !view.conflicts.contains(&conflict) {
634 
                view.conflicts.push(conflict);
635 
            }
636 
        }
637 
        view.entries = std::sync::Arc::new(entries);
638 
        view
639 
    }
640 
}
641
642 
impl TreeGraph {
643 
    /// Serialize for a checkpoint.
644 
    pub fn to_value(&self) -> crate::cbor::Value {
645 
        use crate::cbor::Value;
646 
        let opkey = |k: &OpKey| vec![Value::Bytes(k.0 .0.to_vec()), Value::Uint(k.1 as u64)];
647 
        let deleters = |m: &HashMap<OpKey, BTreeSet<ChangeHash>>| {
648 
            let mut ks: Vec<&OpKey> = m.keys().collect();
649 
            ks.sort();
650 
            Value::Array(
651 
                ks.into_iter()
652 
                    .map(|k| {
653 
                        let mut v = opkey(k);
654 
                        v.push(Value::Array(
655 
                            m[k].iter().map(|d| Value::Bytes(d.0.to_vec())).collect(),
656 
                        ));
657 
                        Value::Array(v)
658 
                    })
659 
                    .collect(),
660 
            )
661 
        };
662 
        let mut nodes: Vec<&NodeId> = self.kinds.keys().collect();
663 
        nodes.sort();
664 
        let mut pks: Vec<&OpKey> = self.placements.keys().collect();
665 
        pks.sort();
666 
        let mut mks: Vec<&OpKey> = self.modes.keys().collect();
667 
        mks.sort();
668 
        Value::map([
669 
            (
670 
                0,
671 
                Value::Array(
672 
                    nodes
673 
                        .into_iter()
674 
                        .map(|n| {
675 
                            Value::Array(vec![
676 
                                Value::Bytes(n.0.to_vec()),
677 
                                Value::Uint(self.kinds[n].tag()),
678 
                                self.introduced
679 
                                    .get(n)
680 
                                    .map(|h| Value::Bytes(h.0.to_vec()))
681 
                                    .unwrap_or(Value::Null),
682 
                            ])
683 
                        })
684 
                        .collect(),
685 
                ),
686 
            ),
687 
            (
688 
                1,
689 
                Value::Array(
690 
                    pks.into_iter()
691 
                        .map(|k| {
692 
                            let p = &self.placements[k];
693 
                            let mut v = opkey(k);
694 
                            v.extend([
695 
                                Value::Bytes(p.node.0.to_vec()),
696 
                                Value::Bytes(p.parent.0.to_vec()),
697 
                                Value::Text(p.name.clone()),
698 
                            ]);
699 
                            Value::Array(v)
700 
                        })
701 
                        .collect(),
702 
                ),
703 
            ),
704 
            (2, deleters(&self.deleted_placements)),
705 
            (
706 
                3,
707 
                Value::Array(
708 
                    mks.into_iter()
709 
                        .map(|k| {
710 
                            let (n, m) = &self.modes[k];
711 
                            let mut v = opkey(k);
712 
                            v.extend([Value::Bytes(n.0.to_vec()), Value::Uint(m.bits())]);
713 
                            Value::Array(v)
714 
                        })
715 
                        .collect(),
716 
                ),
717 
            ),
718 
            (4, deleters(&self.deleted_modes)),
719 
        ])
720 
    }
721
722 
    pub fn from_value(v: &crate::cbor::Value) -> Result<TreeGraph, crate::objects::ObjectError> {
723 
        use crate::objects::{array, bytes, field, map, oref, text, u32_, uint, ObjectError};
724 
        let m = map(v, "tree graph")?;
725 
        let node = |v: &crate::cbor::Value| {
726 
            NodeId::from_slice(bytes(v, "node")?)
727 
                .ok_or_else(|| ObjectError::Schema("node: expected 16 bytes".into()))
728 
        };
729 
        let opkey = |e: &[crate::cbor::Value]| -> Result<OpKey, ObjectError> {
730 
            Ok((oref(&e[0], "op change")?, u32_(&e[1], "op index")?))
731 
        };
732 
        let mut g = TreeGraph::default();
733 
        for n in array(field(m, 0, "nodes")?, "nodes")? {
734 
            let e = array(n, "node entry")?;
735 
            if e.len() != 3 {
736 
                return Err(ObjectError::Schema("node entry: expected 3 fields".into()));
737 
            }
738 
            let id = node(&e[0])?;
739 
            g.kinds
740 
                .insert(id, NodeKind::from_tag(uint(&e[1], "kind")?)?);
741 
            if !e[2].is_null() {
742 
                g.introduced.insert(id, oref(&e[2], "introducer")?);
743 
            }
744 
        }
745 
        for p in array(field(m, 1, "placements")?, "placements")? {
746 
            let e = array(p, "placement")?;
747 
            if e.len() != 5 {
748 
                return Err(ObjectError::Schema("placement: expected 5 fields".into()));
749 
            }
750 
            let k = opkey(e)?;
751 
            let pl = Placement {
752 
                node: node(&e[2])?,
753 
                parent: node(&e[3])?,
754 
                name: text(&e[4], "name")?.to_owned(),
755 
            };
756 
            g.placements_of.entry(pl.node).or_default().insert(k);
757 
            g.placements.insert(k, pl);
758 
        }
759 
        let deleters = |v: &crate::cbor::Value,
760 
                        what: &str|
761 
         -> Result<HashMap<OpKey, BTreeSet<ChangeHash>>, ObjectError> {
762 
            let mut out = HashMap::new();
763 
            for d in array(v, what)? {
764 
                let e = array(d, what)?;
765 
                if e.len() != 3 {
766 
                    return Err(ObjectError::Schema(format!("{what}: expected 3 fields")));
767 
                }
768 
                out.insert(
769 
                    opkey(e)?,
770 
                    array(&e[2], "deleters")?
771 
                        .iter()
772 
                        .map(|x| oref(x, "deleter"))
773 
                        .collect::<Result<BTreeSet<_>, _>>()?,
774 
                );
775 
            }
776 
            Ok(out)
777 
        };
778 
        g.deleted_placements = deleters(field(m, 2, "deleted placements")?, "deleted placement")?;
779 
        for md in array(field(m, 3, "modes")?, "modes")? {
780 
            let e = array(md, "mode")?;
781 
            if e.len() != 4 {
782 
                return Err(ObjectError::Schema("mode: expected 4 fields".into()));
783 
            }
784 
            let k = opkey(e)?;
785 
            let n = node(&e[2])?;
786 
            g.modes
787 
                .insert(k, (n, Mode::from_bits(uint(&e[3], "mode bits")?)?));
788 
            g.modes_of.entry(n).or_default().insert(k);
789 
        }
790 
        g.deleted_modes = deleters(field(m, 4, "deleted modes")?, "deleted mode")?;
791 
        let keys: Vec<OpKey> = g.placements.keys().copied().collect();
792 
        for k in keys {
793 
            g.index_placement(k);
794 
        }
795 
        let keys: Vec<OpKey> = g.modes.keys().copied().collect();
796 
        for k in keys {
797 
            g.index_mode(k);
798 
        }
799 
        Ok(g)
800 
    }
801 
}
802
803 
fn join(dir: &str, name: &str) -> String {
804 
    if dir.is_empty() {
805 
        name.to_string()
806 
    } else {
807 
        format!("{dir}/{name}")
808 
    }
809 
}
810
811 
pub fn op_key(r: OpRef) -> OpKey {
812 
    (r.change, r.index)
813 
}
814
815 
#[cfg(test)]
816 
mod tests {
817 
    use super::*;
818 
    use crate::hash::ObjectRef;
819
820 
    fn h(n: u8) -> ChangeHash {
821 
        ObjectRef([n; 32])
822 
    }
823 
    fn nid(n: u8) -> NodeId {
824 
        NodeId([n; 16])
825 
    }
826 
    fn add(g: &mut TreeGraph, c: u8, i: u32, node: u8, kind: NodeKind, parent: NodeId, name: &str) {
827 
        g.apply(
828 
            h(c),
829 
            i,
830 
            &TreeOp::AddNode {
831 
                node: nid(node),
832 
                kind,
833 
                mode: Mode::TEXT,
834 
                parent,
835 
                name: name.into(),
836 
            },
837 
        );
838 
    }
839 
    fn paths(v: &TreeView) -> Vec<String> {
840 
        v.entries.keys().cloned().collect()
841 
    }
842
843 
    /// Each op applied to a graph whose view is cached keeps it up to date
844 
    /// or drops it: `apply` checks every kept view against a full one.
845 
    #[test]
846 
    fn cached_view_follows_ops() {
847 
        let at = |c: u8, i: u32| OpRef {
848 
            change: h(c),
849 
            index: i,
850 
        };
851 
        let mut g = TreeGraph::new();
852 
        let ops = [
853 
            TreeOp::AddNode {
854 
                node: nid(1),
855 
                kind: NodeKind::Dir,
856 
                mode: Mode::TEXT,
857 
                parent: NodeId::ROOT,
858 
                name: "src".into(),
859 
            },
860 
            TreeOp::AddNode {
861 
                node: nid(2),
862 
                kind: NodeKind::File,
863 
                mode: Mode::TEXT,
864 
                parent: nid(1),
865 
                name: "a.rs".into(),
866 
            },
867 
            TreeOp::SetMode {
868 
                node: nid(2),
869 
                old: at(1, 1),
870 
                mode: Mode {
871 
                    exec: true,
872 
                    opaque: false,
873 
                },
874 
            },
875 
            TreeOp::Move {
876 
                node: nid(2),
877 
                old: at(1, 1),
878 
                parent: NodeId::ROOT,
879 
                name: "b.rs".into(),
880 
            },
881 
            // Moving an empty directory, then removing it.
882 
            TreeOp::Move {
883 
                node: nid(1),
884 
                old: at(1, 0),
885 
                parent: NodeId::ROOT,
886 
                name: "lib".into(),
887 
            },
888 
            TreeOp::RemoveNode {
889 
                node: nid(1),
890 
                placement: at(1, 4),
891 
            },
892 
            // A name taken twice: a conflict, so the view is computed again.
893 
            TreeOp::AddNode {
894 
                node: nid(3),
895 
                kind: NodeKind::File,
896 
                mode: Mode::TEXT,
897 
                parent: NodeId::ROOT,
898 
                name: "b.rs".into(),
899 
            },
900 
        ];
901 
        for (i, op) in ops.iter().enumerate() {
902 
            let _ = g.view();
903 
            g.apply(h(1), i as u32, op);
904 
            assert_eq!(g.view(), g.compute_view());
905 
        }
906 
        let v = g.view();
907 
        assert_eq!(paths(&v), ["b.rs.oxy-conflict-1", "b.rs.oxy-conflict-2"]);
908 
        assert!(v.entries.values().any(|e| e.mode.exec));
909 
    }
910
911 
    #[test]
912 
    fn nested_paths_and_rename() {
913 
        let mut g = TreeGraph::new();
914 
        add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "src");
915 
        add(&mut g, 1, 1, 2, NodeKind::File, nid(1), "main.rs");
916 
        add(&mut g, 1, 2, 3, NodeKind::File, NodeId::ROOT, "README");
917 
        let v = g.view();
918 
        assert_eq!(paths(&v), ["README", "src", "src/main.rs"]);
919 
        assert!(!v.is_conflicted());
920
921 
        // Rename src/main.rs → src/lib.rs, move src → lib (subtree follows).
922 
        g.apply(
923 
            h(2),
924 
            0,
925 
            &TreeOp::Move {
926 
                node: nid(2),
927 
                old: OpRef {
928 
                    change: h(1),
929 
                    index: 1,
930 
                },
931 
                parent: nid(1),
932 
                name: "lib.rs".into(),
933 
            },
934 
        );
935 
        g.apply(
936 
            h(2),
937 
            1,
938 
            &TreeOp::Move {
939 
                node: nid(1),
940 
                old: OpRef {
941 
                    change: h(1),
942 
                    index: 0,
943 
                },
944 
                parent: NodeId::ROOT,
945 
                name: "lib".into(),
946 
            },
947 
        );
948 
        let v = g.view();
949 
        assert_eq!(paths(&v), ["README", "lib", "lib/lib.rs"]);
950 
        assert_eq!(v.entries["lib/lib.rs"].placement, (h(2), 0));
951
952 
        g.apply(
953 
            h(3),
954 
            0,
955 
            &TreeOp::RemoveNode {
956 
                node: nid(3),
957 
                placement: OpRef {
958 
                    change: h(1),
959 
                    index: 2,
960 
                },
961 
            },
962 
        );
963 
        assert_eq!(paths(&g.view()), ["lib", "lib/lib.rs"]);
964 
    }
965
966 
    #[test]
967 
    fn name_conflict_gets_suffixes() {
968 
        let mut g = TreeGraph::new();
969 
        add(&mut g, 1, 0, 1, NodeKind::File, NodeId::ROOT, "a.txt");
970 
        add(&mut g, 2, 0, 2, NodeKind::File, NodeId::ROOT, "a.txt");
971 
        let v = g.view();
972 
        assert_eq!(paths(&v), ["a.txt.oxy-conflict-1", "a.txt.oxy-conflict-2"]);
973 
        assert_eq!(
974 
            v.conflicts,
975 
            vec![TreeConflict::Name {
976 
                parent: NodeId::ROOT,
977 
                name: "a.txt".into(),
978 
                nodes: vec![nid(1), nid(2)]
979 
            }]
980 
        );
981 
    }
982
983 
    #[test]
984 
    fn concurrent_renames_are_multi_placement() {
985 
        let mut g = TreeGraph::new();
986 
        add(&mut g, 1, 0, 1, NodeKind::File, NodeId::ROOT, "a");
987 
        g.apply(
988 
            h(2),
989 
            0,
990 
            &TreeOp::Move {
991 
                node: nid(1),
992 
                old: OpRef {
993 
                    change: h(1),
994 
                    index: 0,
995 
                },
996 
                parent: NodeId::ROOT,
997 
                name: "b".into(),
998 
            },
999 
        );
1000 
        g.apply(
1001 
            h(3),
1002 
            0,
1003 
            &TreeOp::Move {
1004 
                node: nid(1),
1005 
                old: OpRef {
1006 
                    change: h(1),
1007 
                    index: 0,
1008 
                },
1009 
                parent: NodeId::ROOT,
1010 
                name: "c".into(),
1011 
            },
1012 
        );
1013 
        let v = g.view();
1014 
        assert_eq!(paths(&v), ["b.oxy-conflict-1", "c.oxy-conflict-1"]);
1015 
        assert!(
1016 
            matches!(v.conflicts[0], TreeConflict::MultiPlacement { node, .. } if node == nid(1))
1017 
        );
1018 
    }
1019
1020 
    #[test]
1021 
    fn orphan_and_cycle() {
1022 
        let mut g = TreeGraph::new();
1023 
        add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "d");
1024 
        add(&mut g, 1, 1, 2, NodeKind::File, nid(1), "f");
1025 
        // Concurrently: 2 removes d, 3 adds d/g.
1026 
        g.apply(
1027 
            h(2),
1028 
            0,
1029 
            &TreeOp::RemoveNode {
1030 
                node: nid(1),
1031 
                placement: OpRef {
1032 
                    change: h(1),
1033 
                    index: 0,
1034 
                },
1035 
            },
1036 
        );
1037 
        add(&mut g, 3, 0, 3, NodeKind::File, nid(1), "g");
1038 
        let v = g.view();
1039 
        assert_eq!(paths(&v), Vec::<String>::new());
1040 
        assert!(v.conflicts.contains(&TreeConflict::Orphan {
1041 
            node: nid(2),
1042 
            parent: nid(1)
1043 
        }));
1044 
        assert!(v.conflicts.contains(&TreeConflict::Orphan {
1045 
            node: nid(3),
1046 
            parent: nid(1)
1047 
        }));
1048
1049 
        // Cycle: a/b, then concurrently move a under b and b under a's parent... simplest: move a into b.
1050 
        let mut g = TreeGraph::new();
1051 
        add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "a");
1052 
        add(&mut g, 1, 1, 2, NodeKind::Dir, nid(1), "b");
1053 
        g.apply(
1054 
            h(2),
1055 
            0,
1056 
            &TreeOp::Move {
1057 
                node: nid(1),
1058 
                old: OpRef {
1059 
                    change: h(1),
1060 
                    index: 0,
1061 
                },
1062 
                parent: nid(2),
1063 
                name: "a".into(),
1064 
            },
1065 
        );
1066 
        let v = g.view();
1067 
        assert!(
1068 
            v.conflicts
1069 
                .iter()
1070 
                .any(|c| matches!(c, TreeConflict::Cycle { .. })),
1071 
            "{:?}",
1072 
            v.conflicts
1073 
        );
1074 
    }
1075
1076 
    #[test]
1077 
    fn serialization_round_trip() {
1078 
        let mut g = TreeGraph::new();
1079 
        add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "src");
1080 
        add(&mut g, 1, 1, 2, NodeKind::File, nid(1), "main.rs");
1081 
        g.apply(
1082 
            h(2),
1083 
            0,
1084 
            &TreeOp::Move {
1085 
                node: nid(2),
1086 
                old: OpRef {
1087 
                    change: h(1),
1088 
                    index: 1,
1089 
                },
1090 
                parent: nid(1),
1091 
                name: "lib.rs".into(),
1092 
            },
1093 
        );
1094 
        g.apply(
1095 
            h(3),
1096 
            0,
1097 
            &TreeOp::SetMode {
1098 
                node: nid(2),
1099 
                old: OpRef {
1100 
                    change: h(1),
1101 
                    index: 1,
1102 
                },
1103 
                mode: Mode {
1104 
                    exec: true,
1105 
                    opaque: false,
1106 
                },
1107 
            },
1108 
        );
1109 
        let bytes = crate::cbor::encode(&g.to_value());
1110 
        let back = TreeGraph::from_value(&crate::cbor::decode(&bytes).unwrap()).unwrap();
1111 
        assert_eq!(back.view(), g.view());
1112 
        assert_eq!(back.introducer(&nid(2)), Some(h(1)));
1113 
        assert_eq!(crate::cbor::encode(&back.to_value()), bytes);
1114 
    }
1115
1116 
    #[test]
1117 
    fn mode_conflict_and_resolution() {
1118 
        let mut g = TreeGraph::new();
1119 
        add(&mut g, 1, 0, 1, NodeKind::File, NodeId::ROOT, "run.sh");
1120 
        g.apply(
1121 
            h(2),
1122 
            0,
1123 
            &TreeOp::SetMode {
1124 
                node: nid(1),
1125 
                old: OpRef {
1126 
                    change: h(1),
1127 
                    index: 0,
1128 
                },
1129 
                mode: Mode {
1130 
                    exec: true,
1131 
                    opaque: false,
1132 
                },
1133 
            },
1134 
        );
1135 
        g.apply(
1136 
            h(3),
1137 
            0,
1138 
            &TreeOp::SetMode {
1139 
                node: nid(1),
1140 
                old: OpRef {
1141 
                    change: h(1),
1142 
                    index: 0,
1143 
                },
1144 
                mode: Mode {
1145 
                    exec: false,
1146 
                    opaque: true,
1147 
                },
1148 
            },
1149 
        );
1150 
        let v = g.view();
1151 
        assert!(matches!(v.conflicts[0], TreeConflict::Mode { .. }));
1152 
        // Materialized with the greatest mode atom.
1153 
        assert_eq!(
1154 
            v.entries["run.sh"].mode,
1155 
            Mode {
1156 
                exec: false,
1157 
                opaque: true
1158 
            }
1159 
        );
1160 
        // The placement introduced by the same AddNode is unaffected.
1161 
        assert_eq!(v.entries["run.sh"].placement, (h(1), 0));
1162 
        // Resolution: retire both live mode atoms; identical live values do not conflict.
1163 
        g.apply(
1164 
            h(4),
1165 
            0,
1166 
            &TreeOp::SetMode {
1167 
                node: nid(1),
1168 
                old: OpRef {
1169 
                    change: h(2),
1170 
                    index: 0,
1171 
                },
1172 
                mode: Mode {
1173 
                    exec: true,
1174 
                    opaque: false,
1175 
                },
1176 
            },
1177 
        );
1178 
        g.apply(
1179 
            h(4),
1180 
            1,
1181 
            &TreeOp::SetMode {
1182 
                node: nid(1),
1183 
                old: OpRef {
1184 
                    change: h(3),
1185 
                    index: 0,
1186 
                },
1187 
                mode: Mode {
1188 
                    exec: true,
1189 
                    opaque: false,
1190 
                },
1191 
            },
1192 
        );
1193 
        let v = g.view();
1194 
        assert!(!v.is_conflicted(), "{:?}", v.conflicts);
1195 
        assert_eq!(
1196 
            v.entries["run.sh"].mode,
1197 
            Mode {
1198 
                exec: true,
1199 
                opaque: false
1200 
            }
1201 
        );
1202 
    }
1203 
}