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