crates/oxy-core/src/tree.rs at 206c76cad4bf · andymccall/oxygen

# 206c76cad4bf oxygen / crates / oxy-core / src / tree.rs

27.7 KiB · Rust · last changed Compute a state's tree view once 1 month ago source blame history raw

//! The tree graph: nodes, placements, and modes as atoms (spec §7.1, §7.2),
//! with tree conflict detection and path assignment (spec §9.2).

use crate::hash::ChangeHash;
use crate::ids::NodeId;
use crate::objects::{Mode, NodeKind, OpRef, TreeOp};
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};

/// `(change, index into that change's tree_ops)`.
pub type OpKey = (ChangeHash, u32);

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Placement {
    pub node: NodeId,
    pub parent: NodeId,
    pub name: String,
}

#[derive(Clone, Debug, Default)]
pub struct TreeGraph {
    kinds: HashMap<NodeId, NodeKind>,
    introduced: HashMap<NodeId, ChangeHash>,
    placements: HashMap<OpKey, Placement>,
    modes: HashMap<OpKey, (NodeId, Mode)>,
    /// Placement atoms retired by `RemoveNode`/`Move`, and mode atoms retired
    /// by `SetMode`. Kept apart because `AddNode` introduces one of each
    /// under the same key.
    deleted_placements: HashMap<OpKey, BTreeSet<ChangeHash>>,
    deleted_modes: HashMap<OpKey, BTreeSet<ChangeHash>>,
    placements_of: HashMap<NodeId, BTreeSet<OpKey>>,
    modes_of: HashMap<NodeId, BTreeSet<OpKey>>,
    /// The view, once computed; cleared by every change to the graph.
    view_cache: std::sync::OnceLock<TreeView>,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum TreeConflict {
    /// Two live nodes share `(parent, name)`.
    Name {
        parent: NodeId,
        name: String,
        nodes: Vec<NodeId>,
    },
    /// One node has several live placements.
    MultiPlacement {
        node: NodeId,
        placements: Vec<OpKey>,
    },
    /// A live node's parent is not live.
    Orphan { node: NodeId, parent: NodeId },
    /// A directory is placed inside its own descendant.
    Cycle { node: NodeId },
    /// Several live mode atoms.
    Mode { node: NodeId, modes: Vec<Mode> },
}

/// A node as it appears in the working copy.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct TreeEntry {
    pub path: String,
    pub node: NodeId,
    pub kind: NodeKind,
    pub mode: Mode,
    /// The placement this entry materializes (for building `RemoveNode`/`Move`).
    pub placement: OpKey,
    /// The live mode atom (for building `SetMode`).
    pub mode_atom: Option<OpKey>,
}

#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct TreeView {
    /// Path → entry, paths use `/` and have no leading slash; conflicted
    /// entries carry a `.oxy-conflict-<n>` suffix.
    pub entries: BTreeMap<String, TreeEntry>,
    pub conflicts: Vec<TreeConflict>,
}

impl TreeView {
    pub fn is_conflicted(&self) -> bool {
        !self.conflicts.is_empty()
    }
    pub fn by_node(&self) -> HashMap<NodeId, &TreeEntry> {
        self.entries.values().map(|e| (e.node, e)).collect()
    }
}

impl TreeGraph {
    pub fn new() -> Self {
        Self::default()
    }

    /// Apply tree op `index` of `change`; `OpRef` self references must already be resolved.
    pub fn apply(&mut self, change: ChangeHash, index: u32, op: &TreeOp) {
        self.view_cache = std::sync::OnceLock::new();
        let key = (change, index);
        match op {
            TreeOp::AddNode {
                node,
                kind,
                mode,
                parent,
                name,
            } => {
                self.kinds.insert(*node, *kind);
                self.introduced.insert(*node, change);
                self.placements.insert(
                    key,
                    Placement {
                        node: *node,
                        parent: *parent,
                        name: name.clone(),
                    },
                );
                self.placements_of.entry(*node).or_default().insert(key);
                if *kind != NodeKind::Dir {
                    self.modes.insert(key, (*node, *mode));
                    self.modes_of.entry(*node).or_default().insert(key);
                }
            }
            TreeOp::RemoveNode { placement, .. } => {
                self.deleted_placements
                    .entry(op_key(*placement))
                    .or_default()
                    .insert(change);
            }
            TreeOp::Move {
                node,
                old,
                parent,
                name,
            } => {
                self.deleted_placements
                    .entry(op_key(*old))
                    .or_default()
                    .insert(change);
                self.placements.insert(
                    key,
                    Placement {
                        node: *node,
                        parent: *parent,
                        name: name.clone(),
                    },
                );
                self.placements_of.entry(*node).or_default().insert(key);
            }
            TreeOp::SetMode { node, old, mode } => {
                self.deleted_modes
                    .entry(op_key(*old))
                    .or_default()
                    .insert(change);
                self.modes.insert(key, (*node, *mode));
                self.modes_of.entry(*node).or_default().insert(key);
            }
        }
    }

    fn placement_live(&self, k: &OpKey) -> bool {
        self.deleted_placements.get(k).is_none_or(|d| d.is_empty())
    }
    fn mode_live(&self, k: &OpKey) -> bool {
        self.deleted_modes.get(k).is_none_or(|d| d.is_empty())
    }

    pub fn kind(&self, node: &NodeId) -> Option<NodeKind> {
        if node.is_root() {
            Some(NodeKind::Dir)
        } else {
            self.kinds.get(node).copied()
        }
    }

    /// The change whose `AddNode` introduced `node`.
    pub fn introducer(&self, node: &NodeId) -> Option<ChangeHash> {
        self.introduced.get(node).copied()
    }

    pub fn placement(&self, k: &OpKey) -> Option<&Placement> {
        self.placements.get(k)
    }

    pub fn live_placements(&self, node: &NodeId) -> Vec<(OpKey, &Placement)> {
        self.placements_of
            .get(node)
            .into_iter()
            .flat_map(|ks| ks.iter())
            .filter(|k| self.placement_live(k))
            .filter_map(|k| self.placements.get(k).map(|p| (*k, p)))
            .collect()
    }

    pub fn live_modes(&self, node: &NodeId) -> Vec<(OpKey, Mode)> {
        self.modes_of
            .get(node)
            .into_iter()
            .flat_map(|ks| ks.iter())
            .filter(|k| self.mode_live(k))
            .filter_map(|k| self.modes.get(k).map(|(_, m)| (*k, *m)))
            .collect()
    }

    /// Every node that has at least one live placement.
    pub fn placed_nodes(&self) -> impl Iterator<Item = NodeId> + '_ {
        self.placements_of
            .keys()
            .copied()
            .filter(|n| !self.live_placements(n).is_empty())
    }

    /// Resolve the tree: assign paths, find conflicts.
    /// The materialized tree (spec §7.1): computed once per graph and
    /// cloned for each caller.
    pub fn view(&self) -> TreeView {
        self.view_cache.get_or_init(|| self.compute_view()).clone()
    }

    fn compute_view(&self) -> TreeView {
        let mut view = TreeView::default();

        // Live placements grouped by parent.
        let mut children: HashMap<NodeId, Vec<(OpKey, &Placement)>> = HashMap::new();
        for (k, p) in &self.placements {
            if self.placement_live(k) {
                children.entry(p.parent).or_default().push((*k, p));
            }
        }
        for c in children.values_mut() {
            c.sort_by(|a, b| a.1.name.cmp(&b.1.name).then(a.0.cmp(&b.0)));
        }

        // Multi-placement and mode conflicts.
        let mut nodes: Vec<NodeId> = self.placements_of.keys().copied().collect();
        nodes.sort();
        let mut multi: HashSet<NodeId> = HashSet::new();
        for n in &nodes {
            let lp = self.live_placements(n);
            let distinct_places: BTreeSet<(&NodeId, &str)> = lp
                .iter()
                .map(|(_, p)| (&p.parent, p.name.as_str()))
                .collect();
            if distinct_places.len() > 1 {
                multi.insert(*n);
                view.conflicts.push(TreeConflict::MultiPlacement {
                    node: *n,
                    placements: lp.iter().map(|(k, _)| *k).collect(),
                });
            }
            let lm = self.live_modes(n);
            let distinct_modes: BTreeSet<Mode> = lm.iter().map(|(_, m)| *m).collect();
            if distinct_modes.len() > 1 {
                view.conflicts.push(TreeConflict::Mode {
                    node: *n,
                    modes: distinct_modes.into_iter().collect(),
                });
            }
        }

        // BFS from the root, assigning paths.
        let mut reached: HashSet<NodeId> = HashSet::new();
        reached.insert(NodeId::ROOT);
        let mut queue: Vec<(NodeId, String)> = vec![(NodeId::ROOT, String::new())];
        let mut on_path: HashSet<NodeId> = HashSet::new();
        while let Some((dir, dir_path)) = queue.pop() {
            let Some(kids) = children.get(&dir) else {
                continue;
            };
            // Name conflicts within this directory.
            let mut by_name: BTreeMap<&str, Vec<(OpKey, &Placement)>> = BTreeMap::new();
            for (k, p) in kids {
                by_name.entry(p.name.as_str()).or_default().push((*k, p));
            }
            for (name, group) in by_name {
                let distinct: BTreeSet<NodeId> = group.iter().map(|(_, p)| p.node).collect();
                if distinct.len() > 1 {
                    view.conflicts.push(TreeConflict::Name {
                        parent: dir,
                        name: name.to_string(),
                        nodes: distinct.iter().copied().collect(),
                    });
                }
                let suffixed = distinct.len() > 1;
                for (i, (k, p)) in group.iter().enumerate() {
                    let node = p.node;
                    if node == dir || on_path.contains(&node) {
                        view.conflicts.push(TreeConflict::Cycle { node });
                        continue;
                    }
                    let needs_suffix = suffixed || multi.contains(&node);
                    let leaf = if needs_suffix {
                        format!("{name}.oxy-conflict-{}", i + 1)
                    } else {
                        name.to_string()
                    };
                    let path = if dir_path.is_empty() {
                        leaf
                    } else {
                        format!("{dir_path}/{leaf}")
                    };
                    let kind = self.kind(&node).unwrap_or(NodeKind::File);
                    let modes = self.live_modes(&node);
                    let mode_atom = modes.iter().map(|(k, _)| *k).max();
                    let mode = mode_atom
                        .and_then(|k| self.modes.get(&k).map(|(_, m)| *m))
                        .unwrap_or_default();
                    view.entries.insert(
                        path.clone(),
                        TreeEntry {
                            path: path.clone(),
                            node,
                            kind,
                            mode,
                            placement: *k,
                            mode_atom,
                        },
                    );
                    if kind == NodeKind::Dir && reached.insert(node) {
                        on_path.insert(dir);
                        queue.push((node, path));
                    } else {
                        reached.insert(node);
                    }
                }
            }
        }

        // Nodes with live placements that were never reached: orphans or cycles.
        for n in &nodes {
            if reached.contains(n) {
                continue;
            }
            let lp = self.live_placements(n);
            if lp.is_empty() {
                continue;
            }
            let mut seen = HashSet::new();
            let mut cur = *n;
            let conflict = loop {
                if !seen.insert(cur) {
                    break TreeConflict::Cycle { node: *n };
                }
                let lp = self.live_placements(&cur);
                let Some((_, p)) = lp.first() else {
                    break TreeConflict::Orphan {
                        node: *n,
                        parent: cur,
                    };
                };
                if reached.contains(&p.parent) {
                    // Parent reached but this node was not: the parent is not a
                    // directory, so this is a name/kind problem surfaced as orphan.
                    break TreeConflict::Orphan {
                        node: *n,
                        parent: p.parent,
                    };
                }
                cur = p.parent;
            };
            if !view.conflicts.contains(&conflict) {
                view.conflicts.push(conflict);
            }
        }
        view
    }
}

impl TreeGraph {
    /// Serialize for a checkpoint.
    pub fn to_value(&self) -> crate::cbor::Value {
        use crate::cbor::Value;
        let opkey = |k: &OpKey| vec![Value::Bytes(k.0 .0.to_vec()), Value::Uint(k.1 as u64)];
        let deleters = |m: &HashMap<OpKey, BTreeSet<ChangeHash>>| {
            let mut ks: Vec<&OpKey> = m.keys().collect();
            ks.sort();
            Value::Array(
                ks.into_iter()
                    .map(|k| {
                        let mut v = opkey(k);
                        v.push(Value::Array(
                            m[k].iter().map(|d| Value::Bytes(d.0.to_vec())).collect(),
                        ));
                        Value::Array(v)
                    })
                    .collect(),
            )
        };
        let mut nodes: Vec<&NodeId> = self.kinds.keys().collect();
        nodes.sort();
        let mut pks: Vec<&OpKey> = self.placements.keys().collect();
        pks.sort();
        let mut mks: Vec<&OpKey> = self.modes.keys().collect();
        mks.sort();
        Value::map([
            (
                0,
                Value::Array(
                    nodes
                        .into_iter()
                        .map(|n| {
                            Value::Array(vec![
                                Value::Bytes(n.0.to_vec()),
                                Value::Uint(self.kinds[n].tag()),
                                self.introduced
                                    .get(n)
                                    .map(|h| Value::Bytes(h.0.to_vec()))
                                    .unwrap_or(Value::Null),
                            ])
                        })
                        .collect(),
                ),
            ),
            (
                1,
                Value::Array(
                    pks.into_iter()
                        .map(|k| {
                            let p = &self.placements[k];
                            let mut v = opkey(k);
                            v.extend([
                                Value::Bytes(p.node.0.to_vec()),
                                Value::Bytes(p.parent.0.to_vec()),
                                Value::Text(p.name.clone()),
                            ]);
                            Value::Array(v)
                        })
                        .collect(),
                ),
            ),
            (2, deleters(&self.deleted_placements)),
            (
                3,
                Value::Array(
                    mks.into_iter()
                        .map(|k| {
                            let (n, m) = &self.modes[k];
                            let mut v = opkey(k);
                            v.extend([Value::Bytes(n.0.to_vec()), Value::Uint(m.bits())]);
                            Value::Array(v)
                        })
                        .collect(),
                ),
            ),
            (4, deleters(&self.deleted_modes)),
        ])
    }

    pub fn from_value(v: &crate::cbor::Value) -> Result<TreeGraph, crate::objects::ObjectError> {
        use crate::objects::{array, bytes, field, map, oref, text, u32_, uint, ObjectError};
        let m = map(v, "tree graph")?;
        let node = |v: &crate::cbor::Value| {
            NodeId::from_slice(bytes(v, "node")?)
                .ok_or_else(|| ObjectError::Schema("node: expected 16 bytes".into()))
        };
        let opkey = |e: &[crate::cbor::Value]| -> Result<OpKey, ObjectError> {
            Ok((oref(&e[0], "op change")?, u32_(&e[1], "op index")?))
        };
        let mut g = TreeGraph::default();
        for n in array(field(m, 0, "nodes")?, "nodes")? {
            let e = array(n, "node entry")?;
            if e.len() != 3 {
                return Err(ObjectError::Schema("node entry: expected 3 fields".into()));
            }
            let id = node(&e[0])?;
            g.kinds
                .insert(id, NodeKind::from_tag(uint(&e[1], "kind")?)?);
            if !e[2].is_null() {
                g.introduced.insert(id, oref(&e[2], "introducer")?);
            }
        }
        for p in array(field(m, 1, "placements")?, "placements")? {
            let e = array(p, "placement")?;
            if e.len() != 5 {
                return Err(ObjectError::Schema("placement: expected 5 fields".into()));
            }
            let k = opkey(e)?;
            let pl = Placement {
                node: node(&e[2])?,
                parent: node(&e[3])?,
                name: text(&e[4], "name")?.to_owned(),
            };
            g.placements_of.entry(pl.node).or_default().insert(k);
            g.placements.insert(k, pl);
        }
        let deleters = |v: &crate::cbor::Value,
                        what: &str|
         -> Result<HashMap<OpKey, BTreeSet<ChangeHash>>, ObjectError> {
            let mut out = HashMap::new();
            for d in array(v, what)? {
                let e = array(d, what)?;
                if e.len() != 3 {
                    return Err(ObjectError::Schema(format!("{what}: expected 3 fields")));
                }
                out.insert(
                    opkey(e)?,
                    array(&e[2], "deleters")?
                        .iter()
                        .map(|x| oref(x, "deleter"))
                        .collect::<Result<BTreeSet<_>, _>>()?,
                );
            }
            Ok(out)
        };
        g.deleted_placements = deleters(field(m, 2, "deleted placements")?, "deleted placement")?;
        for md in array(field(m, 3, "modes")?, "modes")? {
            let e = array(md, "mode")?;
            if e.len() != 4 {
                return Err(ObjectError::Schema("mode: expected 4 fields".into()));
            }
            let k = opkey(e)?;
            let n = node(&e[2])?;
            g.modes
                .insert(k, (n, Mode::from_bits(uint(&e[3], "mode bits")?)?));
            g.modes_of.entry(n).or_default().insert(k);
        }
        g.deleted_modes = deleters(field(m, 4, "deleted modes")?, "deleted mode")?;
        Ok(g)
    }
}

pub fn op_key(r: OpRef) -> OpKey {
    (r.change, r.index)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::hash::ObjectRef;

    fn h(n: u8) -> ChangeHash {
        ObjectRef([n; 32])
    }
    fn nid(n: u8) -> NodeId {
        NodeId([n; 16])
    }
    fn add(g: &mut TreeGraph, c: u8, i: u32, node: u8, kind: NodeKind, parent: NodeId, name: &str) {
        g.apply(
            h(c),
            i,
            &TreeOp::AddNode {
                node: nid(node),
                kind,
                mode: Mode::TEXT,
                parent,
                name: name.into(),
            },
        );
    }
    fn paths(v: &TreeView) -> Vec<String> {
        v.entries.keys().cloned().collect()
    }

    #[test]
    fn nested_paths_and_rename() {
        let mut g = TreeGraph::new();
        add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "src");
        add(&mut g, 1, 1, 2, NodeKind::File, nid(1), "main.rs");
        add(&mut g, 1, 2, 3, NodeKind::File, NodeId::ROOT, "README");
        let v = g.view();
        assert_eq!(paths(&v), ["README", "src", "src/main.rs"]);
        assert!(!v.is_conflicted());

        // Rename src/main.rs → src/lib.rs, move src → lib (subtree follows).
        g.apply(
            h(2),
            0,
            &TreeOp::Move {
                node: nid(2),
                old: OpRef {
                    change: h(1),
                    index: 1,
                },
                parent: nid(1),
                name: "lib.rs".into(),
            },
        );
        g.apply(
            h(2),
            1,
            &TreeOp::Move {
                node: nid(1),
                old: OpRef {
                    change: h(1),
                    index: 0,
                },
                parent: NodeId::ROOT,
                name: "lib".into(),
            },
        );
        let v = g.view();
        assert_eq!(paths(&v), ["README", "lib", "lib/lib.rs"]);
        assert_eq!(v.entries["lib/lib.rs"].placement, (h(2), 0));

        g.apply(
            h(3),
            0,
            &TreeOp::RemoveNode {
                node: nid(3),
                placement: OpRef {
                    change: h(1),
                    index: 2,
                },
            },
        );
        assert_eq!(paths(&g.view()), ["lib", "lib/lib.rs"]);
    }

    #[test]
    fn name_conflict_gets_suffixes() {
        let mut g = TreeGraph::new();
        add(&mut g, 1, 0, 1, NodeKind::File, NodeId::ROOT, "a.txt");
        add(&mut g, 2, 0, 2, NodeKind::File, NodeId::ROOT, "a.txt");
        let v = g.view();
        assert_eq!(paths(&v), ["a.txt.oxy-conflict-1", "a.txt.oxy-conflict-2"]);
        assert_eq!(
            v.conflicts,
            vec![TreeConflict::Name {
                parent: NodeId::ROOT,
                name: "a.txt".into(),
                nodes: vec![nid(1), nid(2)]
            }]
        );
    }

    #[test]
    fn concurrent_renames_are_multi_placement() {
        let mut g = TreeGraph::new();
        add(&mut g, 1, 0, 1, NodeKind::File, NodeId::ROOT, "a");
        g.apply(
            h(2),
            0,
            &TreeOp::Move {
                node: nid(1),
                old: OpRef {
                    change: h(1),
                    index: 0,
                },
                parent: NodeId::ROOT,
                name: "b".into(),
            },
        );
        g.apply(
            h(3),
            0,
            &TreeOp::Move {
                node: nid(1),
                old: OpRef {
                    change: h(1),
                    index: 0,
                },
                parent: NodeId::ROOT,
                name: "c".into(),
            },
        );
        let v = g.view();
        assert_eq!(paths(&v), ["b.oxy-conflict-1", "c.oxy-conflict-1"]);
        assert!(
            matches!(v.conflicts[0], TreeConflict::MultiPlacement { node, .. } if node == nid(1))
        );
    }

    #[test]
    fn orphan_and_cycle() {
        let mut g = TreeGraph::new();
        add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "d");
        add(&mut g, 1, 1, 2, NodeKind::File, nid(1), "f");
        // Concurrently: 2 removes d, 3 adds d/g.
        g.apply(
            h(2),
            0,
            &TreeOp::RemoveNode {
                node: nid(1),
                placement: OpRef {
                    change: h(1),
                    index: 0,
                },
            },
        );
        add(&mut g, 3, 0, 3, NodeKind::File, nid(1), "g");
        let v = g.view();
        assert_eq!(paths(&v), Vec::<String>::new());
        assert!(v.conflicts.contains(&TreeConflict::Orphan {
            node: nid(2),
            parent: nid(1)
        }));
        assert!(v.conflicts.contains(&TreeConflict::Orphan {
            node: nid(3),
            parent: nid(1)
        }));

        // Cycle: a/b, then concurrently move a under b and b under a's parent... simplest: move a into b.
        let mut g = TreeGraph::new();
        add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "a");
        add(&mut g, 1, 1, 2, NodeKind::Dir, nid(1), "b");
        g.apply(
            h(2),
            0,
            &TreeOp::Move {
                node: nid(1),
                old: OpRef {
                    change: h(1),
                    index: 0,
                },
                parent: nid(2),
                name: "a".into(),
            },
        );
        let v = g.view();
        assert!(
            v.conflicts
                .iter()
                .any(|c| matches!(c, TreeConflict::Cycle { .. })),
            "{:?}",
            v.conflicts
        );
    }

    #[test]
    fn serialization_round_trip() {
        let mut g = TreeGraph::new();
        add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "src");
        add(&mut g, 1, 1, 2, NodeKind::File, nid(1), "main.rs");
        g.apply(
            h(2),
            0,
            &TreeOp::Move {
                node: nid(2),
                old: OpRef {
                    change: h(1),
                    index: 1,
                },
                parent: nid(1),
                name: "lib.rs".into(),
            },
        );
        g.apply(
            h(3),
            0,
            &TreeOp::SetMode {
                node: nid(2),
                old: OpRef {
                    change: h(1),
                    index: 1,
                },
                mode: Mode {
                    exec: true,
                    opaque: false,
                },
            },
        );
        let bytes = crate::cbor::encode(&g.to_value());
        let back = TreeGraph::from_value(&crate::cbor::decode(&bytes).unwrap()).unwrap();
        assert_eq!(back.view(), g.view());
        assert_eq!(back.introducer(&nid(2)), Some(h(1)));
        assert_eq!(crate::cbor::encode(&back.to_value()), bytes);
    }

    #[test]
    fn mode_conflict_and_resolution() {
        let mut g = TreeGraph::new();
        add(&mut g, 1, 0, 1, NodeKind::File, NodeId::ROOT, "run.sh");
        g.apply(
            h(2),
            0,
            &TreeOp::SetMode {
                node: nid(1),
                old: OpRef {
                    change: h(1),
                    index: 0,
                },
                mode: Mode {
                    exec: true,
                    opaque: false,
                },
            },
        );
        g.apply(
            h(3),
            0,
            &TreeOp::SetMode {
                node: nid(1),
                old: OpRef {
                    change: h(1),
                    index: 0,
                },
                mode: Mode {
                    exec: false,
                    opaque: true,
                },
            },
        );
        let v = g.view();
        assert!(matches!(v.conflicts[0], TreeConflict::Mode { .. }));
        // Materialized with the greatest mode atom.
        assert_eq!(
            v.entries["run.sh"].mode,
            Mode {
                exec: false,
                opaque: true
            }
        );
        // The placement introduced by the same AddNode is unaffected.
        assert_eq!(v.entries["run.sh"].placement, (h(1), 0));
        // Resolution: retire both live mode atoms; identical live values do not conflict.
        g.apply(
            h(4),
            0,
            &TreeOp::SetMode {
                node: nid(1),
                old: OpRef {
                    change: h(2),
                    index: 0,
                },
                mode: Mode {
                    exec: true,
                    opaque: false,
                },
            },
        );
        g.apply(
            h(4),
            1,
            &TreeOp::SetMode {
                node: nid(1),
                old: OpRef {
                    change: h(3),
                    index: 0,
                },
                mode: Mode {
                    exec: true,
                    opaque: false,
                },
            },
        );
        let v = g.view();
        assert!(!v.is_conflicted(), "{:?}", v.conflicts);
        assert_eq!(
            v.entries["run.sh"].mode,
            Mode {
                exec: true,
                opaque: false
            }
        );
    }
}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

1	//! The tree graph: nodes, placements, and modes as atoms (spec §7.1, §7.2),
2	//! with tree conflict detection and path assignment (spec §9.2).
3
4	use crate::hash::ChangeHash;
5	use crate::ids::NodeId;
6	use crate::objects::{Mode, NodeKind, OpRef, TreeOp};
7	use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
8
9	/// `(change, index into that change's tree_ops)`.
10	pub type OpKey = (ChangeHash, u32);
11
12	#[derive(Clone, Debug, PartialEq, Eq)]
13	pub struct Placement {
14	pub node: NodeId,
15	pub parent: NodeId,
16	pub name: String,
17	}
18
19	#[derive(Clone, Debug, Default)]
20	pub struct TreeGraph {
21	kinds: HashMap<NodeId, NodeKind>,
22	introduced: HashMap<NodeId, ChangeHash>,
23	placements: HashMap<OpKey, Placement>,
24	modes: HashMap<OpKey, (NodeId, Mode)>,
25	/// Placement atoms retired by `RemoveNode`/`Move`, and mode atoms retired
26	/// by `SetMode`. Kept apart because `AddNode` introduces one of each
27	/// under the same key.
28	deleted_placements: HashMap<OpKey, BTreeSet<ChangeHash>>,
29	deleted_modes: HashMap<OpKey, BTreeSet<ChangeHash>>,
30	placements_of: HashMap<NodeId, BTreeSet<OpKey>>,
31	modes_of: HashMap<NodeId, BTreeSet<OpKey>>,
32	/// The view, once computed; cleared by every change to the graph.
33	view_cache: std::sync::OnceLock<TreeView>,
34	}
35
36	#[derive(Clone, Debug, PartialEq, Eq)]
37	pub enum TreeConflict {
38	/// Two live nodes share `(parent, name)`.
39	Name {
40	parent: NodeId,
41	name: String,
42	nodes: Vec<NodeId>,
43	},
44	/// One node has several live placements.
45	MultiPlacement {
46	node: NodeId,
47	placements: Vec<OpKey>,
48	},
49	/// A live node's parent is not live.
50	Orphan { node: NodeId, parent: NodeId },
51	/// A directory is placed inside its own descendant.
52	Cycle { node: NodeId },
53	/// Several live mode atoms.
54	Mode { node: NodeId, modes: Vec<Mode> },
55	}
56
57	/// A node as it appears in the working copy.
58	#[derive(Clone, Debug, PartialEq, Eq)]
59	pub struct TreeEntry {
60	pub path: String,
61	pub node: NodeId,
62	pub kind: NodeKind,
63	pub mode: Mode,
64	/// The placement this entry materializes (for building `RemoveNode`/`Move`).
65	pub placement: OpKey,
66	/// The live mode atom (for building `SetMode`).
67	pub mode_atom: Option<OpKey>,
68	}
69
70	#[derive(Clone, Debug, Default, PartialEq, Eq)]
71	pub struct TreeView {
72	/// Path → entry, paths use `/` and have no leading slash; conflicted
73	/// entries carry a `.oxy-conflict-<n>` suffix.
74	pub entries: BTreeMap<String, TreeEntry>,
75	pub conflicts: Vec<TreeConflict>,
76	}
77
78	impl TreeView {
79	pub fn is_conflicted(&self) -> bool {
80	!self.conflicts.is_empty()
81	}
82	pub fn by_node(&self) -> HashMap<NodeId, &TreeEntry> {
83	self.entries.values().map(\|e\| (e.node, e)).collect()
84	}
85	}
86
87	impl TreeGraph {
88	pub fn new() -> Self {
89	Self::default()
90	}
91
92	/// Apply tree op `index` of `change`; `OpRef` self references must already be resolved.
93	pub fn apply(&mut self, change: ChangeHash, index: u32, op: &TreeOp) {
94	self.view_cache = std::sync::OnceLock::new();
95	let key = (change, index);
96	match op {
97	TreeOp::AddNode {
98	node,
99	kind,
100	mode,
101	parent,
102	name,
103	} => {
104	self.kinds.insert(node, kind);
105	self.introduced.insert(*node, change);
106	self.placements.insert(
107	key,
108	Placement {
109	node: *node,
110	parent: *parent,
111	name: name.clone(),
112	},
113	);
114	self.placements_of.entry(*node).or_default().insert(key);
115	if *kind != NodeKind::Dir {
116	self.modes.insert(key, (node, mode));
117	self.modes_of.entry(*node).or_default().insert(key);
118	}
119	}
120	TreeOp::RemoveNode { placement, .. } => {
121	self.deleted_placements
122	.entry(op_key(*placement))
123	.or_default()
124	.insert(change);
125	}
126	TreeOp::Move {
127	node,
128	old,
129	parent,
130	name,
131	} => {
132	self.deleted_placements
133	.entry(op_key(*old))
134	.or_default()
135	.insert(change);
136	self.placements.insert(
137	key,
138	Placement {
139	node: *node,
140	parent: *parent,
141	name: name.clone(),
142	},
143	);
144	self.placements_of.entry(*node).or_default().insert(key);
145	}
146	TreeOp::SetMode { node, old, mode } => {
147	self.deleted_modes
148	.entry(op_key(*old))
149	.or_default()
150	.insert(change);
151	self.modes.insert(key, (node, mode));
152	self.modes_of.entry(*node).or_default().insert(key);
153	}
154	}
155	}
156
157	fn placement_live(&self, k: &OpKey) -> bool {
158	self.deleted_placements.get(k).is_none_or(\|d\| d.is_empty())
159	}
160	fn mode_live(&self, k: &OpKey) -> bool {
161	self.deleted_modes.get(k).is_none_or(\|d\| d.is_empty())
162	}
163
164	pub fn kind(&self, node: &NodeId) -> Option<NodeKind> {
165	if node.is_root() {
166	Some(NodeKind::Dir)
167	} else {
168	self.kinds.get(node).copied()
169	}
170	}
171
172	/// The change whose `AddNode` introduced `node`.
173	pub fn introducer(&self, node: &NodeId) -> Option<ChangeHash> {
174	self.introduced.get(node).copied()
175	}
176
177	pub fn placement(&self, k: &OpKey) -> Option<&Placement> {
178	self.placements.get(k)
179	}
180
181	pub fn live_placements(&self, node: &NodeId) -> Vec<(OpKey, &Placement)> {
182	self.placements_of
183	.get(node)
184	.into_iter()
185	.flat_map(\|ks\| ks.iter())
186	.filter(\|k\| self.placement_live(k))
187	.filter_map(\|k\| self.placements.get(k).map(\|p\| (*k, p)))
188	.collect()
189	}
190
191	pub fn live_modes(&self, node: &NodeId) -> Vec<(OpKey, Mode)> {
192	self.modes_of
193	.get(node)
194	.into_iter()
195	.flat_map(\|ks\| ks.iter())
196	.filter(\|k\| self.mode_live(k))
197	.filter_map(\|k\| self.modes.get(k).map(\|(_, m)\| (k, m)))
198	.collect()
199	}
200
201	/// Every node that has at least one live placement.
202	pub fn placed_nodes(&self) -> impl Iterator<Item = NodeId> + '_ {
203	self.placements_of
204	.keys()
205	.copied()
206	.filter(\|n\| !self.live_placements(n).is_empty())
207	}
208
209	/// Resolve the tree: assign paths, find conflicts.
210	/// The materialized tree (spec §7.1): computed once per graph and
211	/// cloned for each caller.
212	pub fn view(&self) -> TreeView {
213	self.view_cache.get_or_init(\|\| self.compute_view()).clone()
214	}
215
216	fn compute_view(&self) -> TreeView {
217	let mut view = TreeView::default();
218
219	// Live placements grouped by parent.
220	let mut children: HashMap<NodeId, Vec<(OpKey, &Placement)>> = HashMap::new();
221	for (k, p) in &self.placements {
222	if self.placement_live(k) {
223	children.entry(p.parent).or_default().push((*k, p));
224	}
225	}
226	for c in children.values_mut() {
227	c.sort_by(\|a, b\| a.1.name.cmp(&b.1.name).then(a.0.cmp(&b.0)));
228	}
229
230	// Multi-placement and mode conflicts.
231	let mut nodes: Vec<NodeId> = self.placements_of.keys().copied().collect();
232	nodes.sort();
233	let mut multi: HashSet<NodeId> = HashSet::new();
234	for n in &nodes {
235	let lp = self.live_placements(n);
236	let distinct_places: BTreeSet<(&NodeId, &str)> = lp
237	.iter()
238	.map(\|(_, p)\| (&p.parent, p.name.as_str()))
239	.collect();
240	if distinct_places.len() > 1 {
241	multi.insert(*n);
242	view.conflicts.push(TreeConflict::MultiPlacement {
243	node: *n,
244	placements: lp.iter().map(\|(k, _)\| *k).collect(),
245	});
246	}
247	let lm = self.live_modes(n);
248	let distinct_modes: BTreeSet<Mode> = lm.iter().map(\|(_, m)\| *m).collect();
249	if distinct_modes.len() > 1 {
250	view.conflicts.push(TreeConflict::Mode {
251	node: *n,
252	modes: distinct_modes.into_iter().collect(),
253	});
254	}
255	}
256
257	// BFS from the root, assigning paths.
258	let mut reached: HashSet<NodeId> = HashSet::new();
259	reached.insert(NodeId::ROOT);
260	let mut queue: Vec<(NodeId, String)> = vec![(NodeId::ROOT, String::new())];
261	let mut on_path: HashSet<NodeId> = HashSet::new();
262	while let Some((dir, dir_path)) = queue.pop() {
263	let Some(kids) = children.get(&dir) else {
264	continue;
265	};
266	// Name conflicts within this directory.
267	let mut by_name: BTreeMap<&str, Vec<(OpKey, &Placement)>> = BTreeMap::new();
268	for (k, p) in kids {
269	by_name.entry(p.name.as_str()).or_default().push((*k, p));
270	}
271	for (name, group) in by_name {
272	let distinct: BTreeSet<NodeId> = group.iter().map(\|(_, p)\| p.node).collect();
273	if distinct.len() > 1 {
274	view.conflicts.push(TreeConflict::Name {
275	parent: dir,
276	name: name.to_string(),
277	nodes: distinct.iter().copied().collect(),
278	});
279	}
280	let suffixed = distinct.len() > 1;
281	for (i, (k, p)) in group.iter().enumerate() {
282	let node = p.node;
283	if node == dir \|\| on_path.contains(&node) {
284	view.conflicts.push(TreeConflict::Cycle { node });
285	continue;
286	}
287	let needs_suffix = suffixed \|\| multi.contains(&node);
288	let leaf = if needs_suffix {
289	format!("{name}.oxy-conflict-{}", i + 1)
290	} else {
291	name.to_string()
292	};
293	let path = if dir_path.is_empty() {
294	leaf
295	} else {
296	format!("{dir_path}/{leaf}")
297	};
298	let kind = self.kind(&node).unwrap_or(NodeKind::File);
299	let modes = self.live_modes(&node);
300	let mode_atom = modes.iter().map(\|(k, _)\| *k).max();
301	let mode = mode_atom
302	.and_then(\|k\| self.modes.get(&k).map(\|(_, m)\| *m))
303	.unwrap_or_default();
304	view.entries.insert(
305	path.clone(),
306	TreeEntry {
307	path: path.clone(),
308	node,
309	kind,
310	mode,
311	placement: *k,
312	mode_atom,
313	},
314	);
315	if kind == NodeKind::Dir && reached.insert(node) {
316	on_path.insert(dir);
317	queue.push((node, path));
318	} else {
319	reached.insert(node);
320	}
321	}
322	}
323	}
324
325	// Nodes with live placements that were never reached: orphans or cycles.
326	for n in &nodes {
327	if reached.contains(n) {
328	continue;
329	}
330	let lp = self.live_placements(n);
331	if lp.is_empty() {
332	continue;
333	}
334	let mut seen = HashSet::new();
335	let mut cur = *n;
336	let conflict = loop {
337	if !seen.insert(cur) {
338	break TreeConflict::Cycle { node: *n };
339	}
340	let lp = self.live_placements(&cur);
341	let Some((_, p)) = lp.first() else {
342	break TreeConflict::Orphan {
343	node: *n,
344	parent: cur,
345	};
346	};
347	if reached.contains(&p.parent) {
348	// Parent reached but this node was not: the parent is not a
349	// directory, so this is a name/kind problem surfaced as orphan.
350	break TreeConflict::Orphan {
351	node: *n,
352	parent: p.parent,
353	};
354	}
355	cur = p.parent;
356	};
357	if !view.conflicts.contains(&conflict) {
358	view.conflicts.push(conflict);
359	}
360	}
361	view
362	}
363	}
364
365	impl TreeGraph {
366	/// Serialize for a checkpoint.
367	pub fn to_value(&self) -> crate::cbor::Value {
368	use crate::cbor::Value;
369	let opkey = \|k: &OpKey\| vec![Value::Bytes(k.0 .0.to_vec()), Value::Uint(k.1 as u64)];
370	let deleters = \|m: &HashMap<OpKey, BTreeSet<ChangeHash>>\| {
371	let mut ks: Vec<&OpKey> = m.keys().collect();
372	ks.sort();
373	Value::Array(
374	ks.into_iter()
375	.map(\|k\| {
376	let mut v = opkey(k);
377	v.push(Value::Array(
378	m[k].iter().map(\|d\| Value::Bytes(d.0.to_vec())).collect(),
379	));
380	Value::Array(v)
381	})
382	.collect(),
383	)
384	};
385	let mut nodes: Vec<&NodeId> = self.kinds.keys().collect();
386	nodes.sort();
387	let mut pks: Vec<&OpKey> = self.placements.keys().collect();
388	pks.sort();
389	let mut mks: Vec<&OpKey> = self.modes.keys().collect();
390	mks.sort();
391	Value::map([
392	(
393	0,
394	Value::Array(
395	nodes
396	.into_iter()
397	.map(\|n\| {
398	Value::Array(vec![
399	Value::Bytes(n.0.to_vec()),
400	Value::Uint(self.kinds[n].tag()),
401	self.introduced
402	.get(n)
403	.map(\|h\| Value::Bytes(h.0.to_vec()))
404	.unwrap_or(Value::Null),
405	])
406	})
407	.collect(),
408	),
409	),
410	(
411	1,
412	Value::Array(
413	pks.into_iter()
414	.map(\|k\| {
415	let p = &self.placements[k];
416	let mut v = opkey(k);
417	v.extend([
418	Value::Bytes(p.node.0.to_vec()),
419	Value::Bytes(p.parent.0.to_vec()),
420	Value::Text(p.name.clone()),
421	]);
422	Value::Array(v)
423	})
424	.collect(),
425	),
426	),
427	(2, deleters(&self.deleted_placements)),
428	(
429	3,
430	Value::Array(
431	mks.into_iter()
432	.map(\|k\| {
433	let (n, m) = &self.modes[k];
434	let mut v = opkey(k);
435	v.extend([Value::Bytes(n.0.to_vec()), Value::Uint(m.bits())]);
436	Value::Array(v)
437	})
438	.collect(),
439	),
440	),
441	(4, deleters(&self.deleted_modes)),
442	])
443	}
444
445	pub fn from_value(v: &crate::cbor::Value) -> Result<TreeGraph, crate::objects::ObjectError> {
446	use crate::objects::{array, bytes, field, map, oref, text, u32_, uint, ObjectError};
447	let m = map(v, "tree graph")?;
448	let node = \|v: &crate::cbor::Value\| {
449	NodeId::from_slice(bytes(v, "node")?)
450	.ok_or_else(\|\| ObjectError::Schema("node: expected 16 bytes".into()))
451	};
452	let opkey = \|e: &[crate::cbor::Value]\| -> Result<OpKey, ObjectError> {
453	Ok((oref(&e[0], "op change")?, u32_(&e[1], "op index")?))
454	};
455	let mut g = TreeGraph::default();
456	for n in array(field(m, 0, "nodes")?, "nodes")? {
457	let e = array(n, "node entry")?;
458	if e.len() != 3 {
459	return Err(ObjectError::Schema("node entry: expected 3 fields".into()));
460	}
461	let id = node(&e[0])?;
462	g.kinds
463	.insert(id, NodeKind::from_tag(uint(&e[1], "kind")?)?);
464	if !e[2].is_null() {
465	g.introduced.insert(id, oref(&e[2], "introducer")?);
466	}
467	}
468	for p in array(field(m, 1, "placements")?, "placements")? {
469	let e = array(p, "placement")?;
470	if e.len() != 5 {
471	return Err(ObjectError::Schema("placement: expected 5 fields".into()));
472	}
473	let k = opkey(e)?;
474	let pl = Placement {
475	node: node(&e[2])?,
476	parent: node(&e[3])?,
477	name: text(&e[4], "name")?.to_owned(),
478	};
479	g.placements_of.entry(pl.node).or_default().insert(k);
480	g.placements.insert(k, pl);
481	}
482	let deleters = \|v: &crate::cbor::Value,
483	what: &str\|
484	-> Result<HashMap<OpKey, BTreeSet<ChangeHash>>, ObjectError> {
485	let mut out = HashMap::new();
486	for d in array(v, what)? {
487	let e = array(d, what)?;
488	if e.len() != 3 {
489	return Err(ObjectError::Schema(format!("{what}: expected 3 fields")));
490	}
491	out.insert(
492	opkey(e)?,
493	array(&e[2], "deleters")?
494	.iter()
495	.map(\|x\| oref(x, "deleter"))
496	.collect::<Result<BTreeSet<_>, _>>()?,
497	);
498	}
499	Ok(out)
500	};
501	g.deleted_placements = deleters(field(m, 2, "deleted placements")?, "deleted placement")?;
502	for md in array(field(m, 3, "modes")?, "modes")? {
503	let e = array(md, "mode")?;
504	if e.len() != 4 {
505	return Err(ObjectError::Schema("mode: expected 4 fields".into()));
506	}
507	let k = opkey(e)?;
508	let n = node(&e[2])?;
509	g.modes
510	.insert(k, (n, Mode::from_bits(uint(&e[3], "mode bits")?)?));
511	g.modes_of.entry(n).or_default().insert(k);
512	}
513	g.deleted_modes = deleters(field(m, 4, "deleted modes")?, "deleted mode")?;
514	Ok(g)
515	}
516	}
517
518	pub fn op_key(r: OpRef) -> OpKey {
519	(r.change, r.index)
520	}
521
522	#[cfg(test)]
523	mod tests {
524	use super::*;
525	use crate::hash::ObjectRef;
526
527	fn h(n: u8) -> ChangeHash {
528	ObjectRef([n; 32])
529	}
530	fn nid(n: u8) -> NodeId {
531	NodeId([n; 16])
532	}
533	fn add(g: &mut TreeGraph, c: u8, i: u32, node: u8, kind: NodeKind, parent: NodeId, name: &str) {
534	g.apply(
535	h(c),
536	i,
537	&TreeOp::AddNode {
538	node: nid(node),
539	kind,
540	mode: Mode::TEXT,
541	parent,
542	name: name.into(),
543	},
544	);
545	}
546	fn paths(v: &TreeView) -> Vec<String> {
547	v.entries.keys().cloned().collect()
548	}
549
550	#[test]
551	fn nested_paths_and_rename() {
552	let mut g = TreeGraph::new();
553	add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "src");
554	add(&mut g, 1, 1, 2, NodeKind::File, nid(1), "main.rs");
555	add(&mut g, 1, 2, 3, NodeKind::File, NodeId::ROOT, "README");
556	let v = g.view();
557	assert_eq!(paths(&v), ["README", "src", "src/main.rs"]);
558	assert!(!v.is_conflicted());
559
560	// Rename src/main.rs → src/lib.rs, move src → lib (subtree follows).
561	g.apply(
562	h(2),
563	0,
564	&TreeOp::Move {
565	node: nid(2),
566	old: OpRef {
567	change: h(1),
568	index: 1,
569	},
570	parent: nid(1),
571	name: "lib.rs".into(),
572	},
573	);
574	g.apply(
575	h(2),
576	1,
577	&TreeOp::Move {
578	node: nid(1),
579	old: OpRef {
580	change: h(1),
581	index: 0,
582	},
583	parent: NodeId::ROOT,
584	name: "lib".into(),
585	},
586	);
587	let v = g.view();
588	assert_eq!(paths(&v), ["README", "lib", "lib/lib.rs"]);
589	assert_eq!(v.entries["lib/lib.rs"].placement, (h(2), 0));
590
591	g.apply(
592	h(3),
593	0,
594	&TreeOp::RemoveNode {
595	node: nid(3),
596	placement: OpRef {
597	change: h(1),
598	index: 2,
599	},
600	},
601	);
602	assert_eq!(paths(&g.view()), ["lib", "lib/lib.rs"]);
603	}
604
605	#[test]
606	fn name_conflict_gets_suffixes() {
607	let mut g = TreeGraph::new();
608	add(&mut g, 1, 0, 1, NodeKind::File, NodeId::ROOT, "a.txt");
609	add(&mut g, 2, 0, 2, NodeKind::File, NodeId::ROOT, "a.txt");
610	let v = g.view();
611	assert_eq!(paths(&v), ["a.txt.oxy-conflict-1", "a.txt.oxy-conflict-2"]);
612	assert_eq!(
613	v.conflicts,
614	vec![TreeConflict::Name {
615	parent: NodeId::ROOT,
616	name: "a.txt".into(),
617	nodes: vec![nid(1), nid(2)]
618	}]
619	);
620	}
621
622	#[test]
623	fn concurrent_renames_are_multi_placement() {
624	let mut g = TreeGraph::new();
625	add(&mut g, 1, 0, 1, NodeKind::File, NodeId::ROOT, "a");
626	g.apply(
627	h(2),
628	0,
629	&TreeOp::Move {
630	node: nid(1),
631	old: OpRef {
632	change: h(1),
633	index: 0,
634	},
635	parent: NodeId::ROOT,
636	name: "b".into(),
637	},
638	);
639	g.apply(
640	h(3),
641	0,
642	&TreeOp::Move {
643	node: nid(1),
644	old: OpRef {
645	change: h(1),
646	index: 0,
647	},
648	parent: NodeId::ROOT,
649	name: "c".into(),
650	},
651	);
652	let v = g.view();
653	assert_eq!(paths(&v), ["b.oxy-conflict-1", "c.oxy-conflict-1"]);
654	assert!(
655	matches!(v.conflicts[0], TreeConflict::MultiPlacement { node, .. } if node == nid(1))
656	);
657	}
658
659	#[test]
660	fn orphan_and_cycle() {
661	let mut g = TreeGraph::new();
662	add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "d");
663	add(&mut g, 1, 1, 2, NodeKind::File, nid(1), "f");
664	// Concurrently: 2 removes d, 3 adds d/g.
665	g.apply(
666	h(2),
667	0,
668	&TreeOp::RemoveNode {
669	node: nid(1),
670	placement: OpRef {
671	change: h(1),
672	index: 0,
673	},
674	},
675	);
676	add(&mut g, 3, 0, 3, NodeKind::File, nid(1), "g");
677	let v = g.view();
678	assert_eq!(paths(&v), Vec::<String>::new());
679	assert!(v.conflicts.contains(&TreeConflict::Orphan {
680	node: nid(2),
681	parent: nid(1)
682	}));
683	assert!(v.conflicts.contains(&TreeConflict::Orphan {
684	node: nid(3),
685	parent: nid(1)
686	}));
687
688	// Cycle: a/b, then concurrently move a under b and b under a's parent... simplest: move a into b.
689	let mut g = TreeGraph::new();
690	add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "a");
691	add(&mut g, 1, 1, 2, NodeKind::Dir, nid(1), "b");
692	g.apply(
693	h(2),
694	0,
695	&TreeOp::Move {
696	node: nid(1),
697	old: OpRef {
698	change: h(1),
699	index: 0,
700	},
701	parent: nid(2),
702	name: "a".into(),
703	},
704	);
705	let v = g.view();
706	assert!(
707	v.conflicts
708	.iter()
709	.any(\|c\| matches!(c, TreeConflict::Cycle { .. })),
710	"{:?}",
711	v.conflicts
712	);
713	}
714
715	#[test]
716	fn serialization_round_trip() {
717	let mut g = TreeGraph::new();
718	add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "src");
719	add(&mut g, 1, 1, 2, NodeKind::File, nid(1), "main.rs");
720	g.apply(
721	h(2),
722	0,
723	&TreeOp::Move {
724	node: nid(2),
725	old: OpRef {
726	change: h(1),
727	index: 1,
728	},
729	parent: nid(1),
730	name: "lib.rs".into(),
731	},
732	);
733	g.apply(
734	h(3),
735	0,
736	&TreeOp::SetMode {
737	node: nid(2),
738	old: OpRef {
739	change: h(1),
740	index: 1,
741	},
742	mode: Mode {
743	exec: true,
744	opaque: false,
745	},
746	},
747	);
748	let bytes = crate::cbor::encode(&g.to_value());
749	let back = TreeGraph::from_value(&crate::cbor::decode(&bytes).unwrap()).unwrap();
750	assert_eq!(back.view(), g.view());
751	assert_eq!(back.introducer(&nid(2)), Some(h(1)));
752	assert_eq!(crate::cbor::encode(&back.to_value()), bytes);
753	}
754
755	#[test]
756	fn mode_conflict_and_resolution() {
757	let mut g = TreeGraph::new();
758	add(&mut g, 1, 0, 1, NodeKind::File, NodeId::ROOT, "run.sh");
759	g.apply(
760	h(2),
761	0,
762	&TreeOp::SetMode {
763	node: nid(1),
764	old: OpRef {
765	change: h(1),
766	index: 0,
767	},
768	mode: Mode {
769	exec: true,
770	opaque: false,
771	},
772	},
773	);
774	g.apply(
775	h(3),
776	0,
777	&TreeOp::SetMode {
778	node: nid(1),
779	old: OpRef {
780	change: h(1),
781	index: 0,
782	},
783	mode: Mode {
784	exec: false,
785	opaque: true,
786	},
787	},
788	);
789	let v = g.view();
790	assert!(matches!(v.conflicts[0], TreeConflict::Mode { .. }));
791	// Materialized with the greatest mode atom.
792	assert_eq!(
793	v.entries["run.sh"].mode,
794	Mode {
795	exec: false,
796	opaque: true
797	}
798	);
799	// The placement introduced by the same AddNode is unaffected.
800	assert_eq!(v.entries["run.sh"].placement, (h(1), 0));
801	// Resolution: retire both live mode atoms; identical live values do not conflict.
802	g.apply(
803	h(4),
804	0,
805	&TreeOp::SetMode {
806	node: nid(1),
807	old: OpRef {
808	change: h(2),
809	index: 0,
810	},
811	mode: Mode {
812	exec: true,
813	opaque: false,
814	},
815	},
816	);
817	g.apply(
818	h(4),
819	1,
820	&TreeOp::SetMode {
821	node: nid(1),
822	old: OpRef {
823	change: h(3),
824	index: 0,
825	},
826	mode: Mode {
827	exec: true,
828	opaque: false,
829	},
830	},
831	);
832	let v = g.view();
833	assert!(!v.is_conflicted(), "{:?}", v.conflicts);
834	assert_eq!(
835	v.entries["run.sh"].mode,
836	Mode {
837	exec: true,
838	opaque: false
839	}
840	);
841	}
842	}

Keyboard