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