crates/oxy-core/src/tree.rs at 50a046e439e9 · andymccall/oxygen

# 50a046e439e9 oxygen / crates / oxy-core / src / tree.rs

22.1 KiB · Rust · last changed Checkpoints: serialized states per bookmark, automatic every core.checkpoint-interval changes, oxy checkpoint, checkpoint-accelerated load_state; states keep change metadata only 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>>,
}

#[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) {
        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.
    pub fn 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

ff0af1ee unknown 1 month ago	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	}
	33
	34	#[derive(Clone, Debug, PartialEq, Eq)]
	35	pub enum TreeConflict {
	36	/// Two live nodes share `(parent, name)`.
	37	Name { parent: NodeId, name: String, nodes: Vec<NodeId> },
	38	/// One node has several live placements.
	39	MultiPlacement { node: NodeId, placements: Vec<OpKey> },
	40	/// A live node's parent is not live.
	41	Orphan { node: NodeId, parent: NodeId },
	42	/// A directory is placed inside its own descendant.
	43	Cycle { node: NodeId },
	44	/// Several live mode atoms.
	45	Mode { node: NodeId, modes: Vec<Mode> },
	46	}
	47
	48	/// A node as it appears in the working copy.
	49	#[derive(Clone, Debug, PartialEq, Eq)]
	50	pub struct TreeEntry {
	51	pub path: String,
	52	pub node: NodeId,
	53	pub kind: NodeKind,
	54	pub mode: Mode,
	55	/// The placement this entry materializes (for building `RemoveNode`/`Move`).
	56	pub placement: OpKey,
	57	/// The live mode atom (for building `SetMode`).
	58	pub mode_atom: Option<OpKey>,
	59	}
	60
	61	#[derive(Clone, Debug, Default, PartialEq, Eq)]
	62	pub struct TreeView {
	63	/// Path → entry, paths use `/` and have no leading slash; conflicted
	64	/// entries carry a `.oxy-conflict-<n>` suffix.
65	pub entries: BTreeMap<String, TreeEntry>,
66	pub conflicts: Vec<TreeConflict>,
67	}
68
69	impl TreeView {
70	pub fn is_conflicted(&self) -> bool {
71	!self.conflicts.is_empty()
72	}
73	pub fn by_node(&self) -> HashMap<NodeId, &TreeEntry> {
74	self.entries.values().map(\|e\| (e.node, e)).collect()
75	}
76	}
77
78	impl TreeGraph {
79	pub fn new() -> Self {
80	Self::default()
81	}
82
83	/// Apply tree op `index` of `change`; `OpRef` self references must already be resolved.
84	pub fn apply(&mut self, change: ChangeHash, index: u32, op: &TreeOp) {
85	let key = (change, index);
86	match op {
87	TreeOp::AddNode { node, kind, mode, parent, name } => {
88	self.kinds.insert(node, kind);
89	self.introduced.insert(*node, change);
90	self.placements.insert(key, Placement { node: node, parent: parent, name: name.clone() });
91	self.placements_of.entry(*node).or_default().insert(key);
92	if *kind != NodeKind::Dir {
93	self.modes.insert(key, (node, mode));
94	self.modes_of.entry(*node).or_default().insert(key);
95	}
96	}
97	TreeOp::RemoveNode { placement, .. } => {
98	self.deleted_placements.entry(op_key(*placement)).or_default().insert(change);
99	}
100	TreeOp::Move { node, old, parent, name } => {
101	self.deleted_placements.entry(op_key(*old)).or_default().insert(change);
102	self.placements.insert(key, Placement { node: node, parent: parent, name: name.clone() });
103	self.placements_of.entry(*node).or_default().insert(key);
104	}
105	TreeOp::SetMode { node, old, mode } => {
106	self.deleted_modes.entry(op_key(*old)).or_default().insert(change);
107	self.modes.insert(key, (node, mode));
108	self.modes_of.entry(*node).or_default().insert(key);
109	}
110	}
111	}
112
113	fn placement_live(&self, k: &OpKey) -> bool {
114	self.deleted_placements.get(k).is_none_or(\|d\| d.is_empty())
115	}
116	fn mode_live(&self, k: &OpKey) -> bool {
117	self.deleted_modes.get(k).is_none_or(\|d\| d.is_empty())
118	}
119
120	pub fn kind(&self, node: &NodeId) -> Option<NodeKind> {
121	if node.is_root() { Some(NodeKind::Dir) } else { self.kinds.get(node).copied() }
122	}
123
124	/// The change whose `AddNode` introduced `node`.
125	pub fn introducer(&self, node: &NodeId) -> Option<ChangeHash> {
126	self.introduced.get(node).copied()
127	}
128
129	pub fn placement(&self, k: &OpKey) -> Option<&Placement> {
130	self.placements.get(k)
131	}
132
133	pub fn live_placements(&self, node: &NodeId) -> Vec<(OpKey, &Placement)> {
134	self.placements_of
135	.get(node)
136	.into_iter()
137	.flat_map(\|ks\| ks.iter())
138	.filter(\|k\| self.placement_live(k))
139	.filter_map(\|k\| self.placements.get(k).map(\|p\| (*k, p)))
140	.collect()
141	}
142
143	pub fn live_modes(&self, node: &NodeId) -> Vec<(OpKey, Mode)> {
144	self.modes_of
145	.get(node)
146	.into_iter()
147	.flat_map(\|ks\| ks.iter())
148	.filter(\|k\| self.mode_live(k))
149	.filter_map(\|k\| self.modes.get(k).map(\|(_, m)\| (k, m)))
150	.collect()
151	}
152
153	/// Every node that has at least one live placement.
154	pub fn placed_nodes(&self) -> impl Iterator<Item = NodeId> + '_ {
155	self.placements_of.keys().copied().filter(\|n\| !self.live_placements(n).is_empty())
156	}
157
158	/// Resolve the tree: assign paths, find conflicts.
159	pub fn view(&self) -> TreeView {
160	let mut view = TreeView::default();
161
162	// Live placements grouped by parent.
163	let mut children: HashMap<NodeId, Vec<(OpKey, &Placement)>> = HashMap::new();
164	for (k, p) in &self.placements {
165	if self.placement_live(k) {
166	children.entry(p.parent).or_default().push((*k, p));
167	}
168	}
169	for c in children.values_mut() {
170	c.sort_by(\|a, b\| a.1.name.cmp(&b.1.name).then(a.0.cmp(&b.0)));
171	}
172
173	// Multi-placement and mode conflicts.
174	let mut nodes: Vec<NodeId> = self.placements_of.keys().copied().collect();
175	nodes.sort();
176	let mut multi: HashSet<NodeId> = HashSet::new();
177	for n in &nodes {
178	let lp = self.live_placements(n);
179	let distinct_places: BTreeSet<(&NodeId, &str)> = lp.iter().map(\|(_, p)\| (&p.parent, p.name.as_str())).collect();
180	if distinct_places.len() > 1 {
181	multi.insert(*n);
182	view.conflicts.push(TreeConflict::MultiPlacement { node: n, placements: lp.iter().map(\|(k, _)\| k).collect() });
183	}
184	let lm = self.live_modes(n);
185	let distinct_modes: BTreeSet<Mode> = lm.iter().map(\|(_, m)\| *m).collect();
186	if distinct_modes.len() > 1 {
187	view.conflicts.push(TreeConflict::Mode { node: *n, modes: distinct_modes.into_iter().collect() });
188	}
189	}
190
191	// BFS from the root, assigning paths.
192	let mut reached: HashSet<NodeId> = HashSet::new();
193	reached.insert(NodeId::ROOT);
194	let mut queue: Vec<(NodeId, String)> = vec![(NodeId::ROOT, String::new())];
195	let mut on_path: HashSet<NodeId> = HashSet::new();
196	while let Some((dir, dir_path)) = queue.pop() {
197	let Some(kids) = children.get(&dir) else { continue };
198	// Name conflicts within this directory.
199	let mut by_name: BTreeMap<&str, Vec<(OpKey, &Placement)>> = BTreeMap::new();
200	for (k, p) in kids {
201	by_name.entry(p.name.as_str()).or_default().push((*k, p));
202	}
203	for (name, group) in by_name {
204	let distinct: BTreeSet<NodeId> = group.iter().map(\|(_, p)\| p.node).collect();
205	if distinct.len() > 1 {
206	view.conflicts.push(TreeConflict::Name { parent: dir, name: name.to_string(), nodes: distinct.iter().copied().collect() });
207	}
208	let suffixed = distinct.len() > 1;
209	for (i, (k, p)) in group.iter().enumerate() {
210	let node = p.node;
211	if node == dir \|\| on_path.contains(&node) {
212	view.conflicts.push(TreeConflict::Cycle { node });
213	continue;
214	}
215	let needs_suffix = suffixed \|\| multi.contains(&node);
216	let leaf = if needs_suffix { format!("{name}.oxy-conflict-{}", i + 1) } else { name.to_string() };
217	let path = if dir_path.is_empty() { leaf } else { format!("{dir_path}/{leaf}") };
218	let kind = self.kind(&node).unwrap_or(NodeKind::File);
219	let modes = self.live_modes(&node);
220	let mode_atom = modes.iter().map(\|(k, _)\| *k).max();
221	let mode = mode_atom.and_then(\|k\| self.modes.get(&k).map(\|(_, m)\| *m)).unwrap_or_default();
222	view.entries.insert(path.clone(), TreeEntry { path: path.clone(), node, kind, mode, placement: *k, mode_atom });
223	if kind == NodeKind::Dir && reached.insert(node) {
224	on_path.insert(dir);
225	queue.push((node, path));
226	} else {
227	reached.insert(node);
228	}
229	}
230	}
231	}
232
233	// Nodes with live placements that were never reached: orphans or cycles.
234	for n in &nodes {
235	if reached.contains(n) {
236	continue;
237	}
238	let lp = self.live_placements(n);
239	if lp.is_empty() {
240	continue;
241	}
242	let mut seen = HashSet::new();
243	let mut cur = *n;
244	let conflict = loop {
245	if !seen.insert(cur) {
246	break TreeConflict::Cycle { node: *n };
247	}
248	let lp = self.live_placements(&cur);
249	let Some((_, p)) = lp.first() else {
250	break TreeConflict::Orphan { node: *n, parent: cur };
251	};
252	if reached.contains(&p.parent) {
253	// Parent reached but this node was not: the parent is not a
254	// directory, so this is a name/kind problem surfaced as orphan.
255	break TreeConflict::Orphan { node: *n, parent: p.parent };
256	}
257	cur = p.parent;
258	};
259	if !view.conflicts.contains(&conflict) {
260	view.conflicts.push(conflict);
261	}
262	}
263	view
264	}
265	}
266
252e8cb2 Andy McCall 1 month ago ↶	267	impl TreeGraph {
	268	/// Serialize for a checkpoint.
	269	pub fn to_value(&self) -> crate::cbor::Value {
	270	use crate::cbor::Value;
	271	let opkey = \|k: &OpKey\| vec![Value::Bytes(k.0 .0.to_vec()), Value::Uint(k.1 as u64)];
	272	let deleters = \|m: &HashMap<OpKey, BTreeSet<ChangeHash>>\| {
	273	let mut ks: Vec<&OpKey> = m.keys().collect();
	274	ks.sort();
	275	Value::Array(
	276	ks.into_iter()
	277	.map(\|k\| {
	278	let mut v = opkey(k);
	279	v.push(Value::Array(m[k].iter().map(\|d\| Value::Bytes(d.0.to_vec())).collect()));
	280	Value::Array(v)
	281	})
	282	.collect(),
	283	)
	284	};
	285	let mut nodes: Vec<&NodeId> = self.kinds.keys().collect();
	286	nodes.sort();
	287	let mut pks: Vec<&OpKey> = self.placements.keys().collect();
	288	pks.sort();
	289	let mut mks: Vec<&OpKey> = self.modes.keys().collect();
	290	mks.sort();
	291	Value::map([
	292	(
	293	0,
	294	Value::Array(
	295	nodes
	296	.into_iter()
	297	.map(\|n\| {
	298	Value::Array(vec![
	299	Value::Bytes(n.0.to_vec()),
	300	Value::Uint(self.kinds[n].tag()),
	301	self.introduced.get(n).map(\|h\| Value::Bytes(h.0.to_vec())).unwrap_or(Value::Null),
	302	])
	303	})
	304	.collect(),
	305	),
	306	),
	307	(
	308	1,
	309	Value::Array(
	310	pks.into_iter()
	311	.map(\|k\| {
	312	let p = &self.placements[k];
	313	let mut v = opkey(k);
	314	v.extend([Value::Bytes(p.node.0.to_vec()), Value::Bytes(p.parent.0.to_vec()), Value::Text(p.name.clone())]);
	315	Value::Array(v)
	316	})
	317	.collect(),
	318	),
	319	),
	320	(2, deleters(&self.deleted_placements)),
	321	(
	322	3,
	323	Value::Array(
	324	mks.into_iter()
	325	.map(\|k\| {
	326	let (n, m) = &self.modes[k];
	327	let mut v = opkey(k);
	328	v.extend([Value::Bytes(n.0.to_vec()), Value::Uint(m.bits())]);
	329	Value::Array(v)
	330	})
331	.collect(),
332	),
333	),
334	(4, deleters(&self.deleted_modes)),
335	])
336	}
337
338	pub fn from_value(v: &crate::cbor::Value) -> Result<TreeGraph, crate::objects::ObjectError> {
339	use crate::objects::{array, bytes, field, map, oref, text, u32_, uint, ObjectError};
340	let m = map(v, "tree graph")?;
341	let node = \|v: &crate::cbor::Value\| NodeId::from_slice(bytes(v, "node")?).ok_or_else(\|\| ObjectError::Schema("node: expected 16 bytes".into()));
342	let opkey = \|e: &[crate::cbor::Value]\| -> Result<OpKey, ObjectError> { Ok((oref(&e[0], "op change")?, u32_(&e[1], "op index")?)) };
343	let mut g = TreeGraph::default();
344	for n in array(field(m, 0, "nodes")?, "nodes")? {
345	let e = array(n, "node entry")?;
346	if e.len() != 3 {
347	return Err(ObjectError::Schema("node entry: expected 3 fields".into()));
348	}
349	let id = node(&e[0])?;
350	g.kinds.insert(id, NodeKind::from_tag(uint(&e[1], "kind")?)?);
351	if !e[2].is_null() {
352	g.introduced.insert(id, oref(&e[2], "introducer")?);
353	}
354	}
355	for p in array(field(m, 1, "placements")?, "placements")? {
356	let e = array(p, "placement")?;
357	if e.len() != 5 {
358	return Err(ObjectError::Schema("placement: expected 5 fields".into()));
359	}
360	let k = opkey(e)?;
361	let pl = Placement { node: node(&e[2])?, parent: node(&e[3])?, name: text(&e[4], "name")?.to_owned() };
362	g.placements_of.entry(pl.node).or_default().insert(k);
363	g.placements.insert(k, pl);
364	}
365	let deleters = \|v: &crate::cbor::Value, what: &str\| -> Result<HashMap<OpKey, BTreeSet<ChangeHash>>, ObjectError> {
366	let mut out = HashMap::new();
367	for d in array(v, what)? {
368	let e = array(d, what)?;
369	if e.len() != 3 {
370	return Err(ObjectError::Schema(format!("{what}: expected 3 fields")));
371	}
372	out.insert(opkey(e)?, array(&e[2], "deleters")?.iter().map(\|x\| oref(x, "deleter")).collect::<Result<BTreeSet<_>, _>>()?);
373	}
374	Ok(out)
375	};
376	g.deleted_placements = deleters(field(m, 2, "deleted placements")?, "deleted placement")?;
377	for md in array(field(m, 3, "modes")?, "modes")? {
378	let e = array(md, "mode")?;
379	if e.len() != 4 {
380	return Err(ObjectError::Schema("mode: expected 4 fields".into()));
381	}
382	let k = opkey(e)?;
383	let n = node(&e[2])?;
384	g.modes.insert(k, (n, Mode::from_bits(uint(&e[3], "mode bits")?)?));
385	g.modes_of.entry(n).or_default().insert(k);
386	}
387	g.deleted_modes = deleters(field(m, 4, "deleted modes")?, "deleted mode")?;
388	Ok(g)
389	}
390	}
391
ff0af1ee unknown 1 month ago	392	pub fn op_key(r: OpRef) -> OpKey {
	393	(r.change, r.index)
	394	}
	395
	396	#[cfg(test)]
	397	mod tests {
	398	use super::*;
	399	use crate::hash::ObjectRef;
	400
	401	fn h(n: u8) -> ChangeHash {
	402	ObjectRef([n; 32])
	403	}
	404	fn nid(n: u8) -> NodeId {
	405	NodeId([n; 16])
	406	}
	407	fn add(g: &mut TreeGraph, c: u8, i: u32, node: u8, kind: NodeKind, parent: NodeId, name: &str) {
	408	g.apply(h(c), i, &TreeOp::AddNode { node: nid(node), kind, mode: Mode::TEXT, parent, name: name.into() });
	409	}
	410	fn paths(v: &TreeView) -> Vec<String> {
	411	v.entries.keys().cloned().collect()
	412	}
	413
	414	#[test]
	415	fn nested_paths_and_rename() {
	416	let mut g = TreeGraph::new();
	417	add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "src");
	418	add(&mut g, 1, 1, 2, NodeKind::File, nid(1), "main.rs");
	419	add(&mut g, 1, 2, 3, NodeKind::File, NodeId::ROOT, "README");
	420	let v = g.view();
	421	assert_eq!(paths(&v), ["README", "src", "src/main.rs"]);
	422	assert!(!v.is_conflicted());
	423
	424	// Rename src/main.rs → src/lib.rs, move src → lib (subtree follows).
	425	g.apply(h(2), 0, &TreeOp::Move { node: nid(2), old: OpRef { change: h(1), index: 1 }, parent: nid(1), name: "lib.rs".into() });
	426	g.apply(h(2), 1, &TreeOp::Move { node: nid(1), old: OpRef { change: h(1), index: 0 }, parent: NodeId::ROOT, name: "lib".into() });
	427	let v = g.view();
	428	assert_eq!(paths(&v), ["README", "lib", "lib/lib.rs"]);
	429	assert_eq!(v.entries["lib/lib.rs"].placement, (h(2), 0));
	430
	431	g.apply(h(3), 0, &TreeOp::RemoveNode { node: nid(3), placement: OpRef { change: h(1), index: 2 } });
	432	assert_eq!(paths(&g.view()), ["lib", "lib/lib.rs"]);
	433	}
	434
	435	#[test]
	436	fn name_conflict_gets_suffixes() {
	437	let mut g = TreeGraph::new();
	438	add(&mut g, 1, 0, 1, NodeKind::File, NodeId::ROOT, "a.txt");
	439	add(&mut g, 2, 0, 2, NodeKind::File, NodeId::ROOT, "a.txt");
	440	let v = g.view();
	441	assert_eq!(paths(&v), ["a.txt.oxy-conflict-1", "a.txt.oxy-conflict-2"]);
	442	assert_eq!(v.conflicts, vec![TreeConflict::Name { parent: NodeId::ROOT, name: "a.txt".into(), nodes: vec![nid(1), nid(2)] }]);
	443	}
	444
	445	#[test]
	446	fn concurrent_renames_are_multi_placement() {
	447	let mut g = TreeGraph::new();
	448	add(&mut g, 1, 0, 1, NodeKind::File, NodeId::ROOT, "a");
	449	g.apply(h(2), 0, &TreeOp::Move { node: nid(1), old: OpRef { change: h(1), index: 0 }, parent: NodeId::ROOT, name: "b".into() });
	450	g.apply(h(3), 0, &TreeOp::Move { node: nid(1), old: OpRef { change: h(1), index: 0 }, parent: NodeId::ROOT, name: "c".into() });
	451	let v = g.view();
	452	assert_eq!(paths(&v), ["b.oxy-conflict-1", "c.oxy-conflict-1"]);
	453	assert!(matches!(v.conflicts[0], TreeConflict::MultiPlacement { node, .. } if node == nid(1)));
	454	}
	455
456	#[test]
457	fn orphan_and_cycle() {
458	let mut g = TreeGraph::new();
459	add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "d");
460	add(&mut g, 1, 1, 2, NodeKind::File, nid(1), "f");
461	// Concurrently: 2 removes d, 3 adds d/g.
462	g.apply(h(2), 0, &TreeOp::RemoveNode { node: nid(1), placement: OpRef { change: h(1), index: 0 } });
463	add(&mut g, 3, 0, 3, NodeKind::File, nid(1), "g");
464	let v = g.view();
465	assert_eq!(paths(&v), Vec::<String>::new());
466	assert!(v.conflicts.contains(&TreeConflict::Orphan { node: nid(2), parent: nid(1) }));
467	assert!(v.conflicts.contains(&TreeConflict::Orphan { node: nid(3), parent: nid(1) }));
468
469	// Cycle: a/b, then concurrently move a under b and b under a's parent... simplest: move a into b.
470	let mut g = TreeGraph::new();
471	add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "a");
472	add(&mut g, 1, 1, 2, NodeKind::Dir, nid(1), "b");
473	g.apply(h(2), 0, &TreeOp::Move { node: nid(1), old: OpRef { change: h(1), index: 0 }, parent: nid(2), name: "a".into() });
474	let v = g.view();
475	assert!(v.conflicts.iter().any(\|c\| matches!(c, TreeConflict::Cycle { .. })), "{:?}", v.conflicts);
476	}
477
478	#[test]
252e8cb2 Andy McCall 1 month ago ↶	479	fn serialization_round_trip() {
	480	let mut g = TreeGraph::new();
	481	add(&mut g, 1, 0, 1, NodeKind::Dir, NodeId::ROOT, "src");
	482	add(&mut g, 1, 1, 2, NodeKind::File, nid(1), "main.rs");
	483	g.apply(h(2), 0, &TreeOp::Move { node: nid(2), old: OpRef { change: h(1), index: 1 }, parent: nid(1), name: "lib.rs".into() });
	484	g.apply(h(3), 0, &TreeOp::SetMode { node: nid(2), old: OpRef { change: h(1), index: 1 }, mode: Mode { exec: true, opaque: false } });
	485	let bytes = crate::cbor::encode(&g.to_value());
	486	let back = TreeGraph::from_value(&crate::cbor::decode(&bytes).unwrap()).unwrap();
	487	assert_eq!(back.view(), g.view());
	488	assert_eq!(back.introducer(&nid(2)), Some(h(1)));
	489	assert_eq!(crate::cbor::encode(&back.to_value()), bytes);
	490	}
	491
	492	#[test]
ff0af1ee unknown 1 month ago	493	fn mode_conflict_and_resolution() {
	494	let mut g = TreeGraph::new();
	495	add(&mut g, 1, 0, 1, NodeKind::File, NodeId::ROOT, "run.sh");
	496	g.apply(h(2), 0, &TreeOp::SetMode { node: nid(1), old: OpRef { change: h(1), index: 0 }, mode: Mode { exec: true, opaque: false } });
	497	g.apply(h(3), 0, &TreeOp::SetMode { node: nid(1), old: OpRef { change: h(1), index: 0 }, mode: Mode { exec: false, opaque: true } });
	498	let v = g.view();
	499	assert!(matches!(v.conflicts[0], TreeConflict::Mode { .. }));
	500	// Materialized with the greatest mode atom.
	501	assert_eq!(v.entries["run.sh"].mode, Mode { exec: false, opaque: true });
	502	// The placement introduced by the same AddNode is unaffected.
	503	assert_eq!(v.entries["run.sh"].placement, (h(1), 0));
	504	// Resolution: retire both live mode atoms; identical live values do not conflict.
	505	g.apply(h(4), 0, &TreeOp::SetMode { node: nid(1), old: OpRef { change: h(2), index: 0 }, mode: Mode { exec: true, opaque: false } });
	506	g.apply(h(4), 1, &TreeOp::SetMode { node: nid(1), old: OpRef { change: h(3), index: 0 }, mode: Mode { exec: true, opaque: false } });
	507	let v = g.view();
	508	assert!(!v.is_conflicted(), "{:?}", v.conflicts);
	509	assert_eq!(v.entries["run.sh"].mode, Mode { exec: true, opaque: false });
	510	}
	511	}

Keyboard