Tree views updated in place, and a faster render of edited files e83354cdac22

        if let Some(order) = self.as_chain().or_else(|| self.as_order(deps)) {

    /// The live atoms in order when, with the dead ones contracted away,

    /// the graph orders them one way only: no deleted atom is a ghost, and

    /// at every step of the topological sort one vertex is next. A file

    /// edited without concurrent edits is such a graph, however long its

    /// history. `None` otherwise, for [`FileGraph::materialize_general`]

    /// to find the conflicts; where this answers, it gives the same order.

    fn as_order(&self, deps: &dyn DepOracle) -> Option<Vec<AtomKey>> {

        // Kept vertices by dense index: Start, End, then the live atoms.

        let mut index: HashMap<Vertex, u32> =

            HashMap::with_capacity_and_hasher(self.atoms.len() + 2, Default::default());

        let mut verts: Vec<Vertex> = Vec::with_capacity(self.atoms.len() + 2);

        verts.extend([Vertex::Start, Vertex::End]);

        index.insert(Vertex::Start, 0);

        index.insert(Vertex::End, 1);

        for (k, info) in &self.atoms {

            if info.content.is_none() {

                continue;

            }

            if info.deleted_by.is_empty() {

                index.insert(Vertex::Atom(*k), verts.len() as u32);

                verts.push(Vertex::Atom(*k));

            } else if self.is_ghost(k, info, deps) {

                return None;

            }

        }

        // Each kept vertex's successors, contracting the others: what a

        // contracted vertex reaches is worked out once (post-order).

        let mut reach: HashMap<Vertex, Vec<u32>> = HashMap::default();

        let contracted = |v: Vertex, reach: &mut HashMap<Vertex, Vec<u32>>| {

            let mut stack: Vec<(Vertex, bool)> = vec![(v, false)];

            while let Some((x, done)) = stack.pop() {

                if reach.contains_key(&x) {

                    continue;

                }

                let next = self.succ.get(&x).map(Edges::as_slice).unwrap_or_default();

                if !done {

                    stack.push((x, true));

                    for s in next {

                        if !index.contains_key(s) && !reach.contains_key(s) {

                            stack.push((*s, false));

                        }

                    }

                    continue;

                }

                let mut out: Vec<u32> = Vec::new();

                for s in next {

                    match index.get(s) {

                        Some(i) => out.push(*i),

                        None => out.extend(reach.get(s).into_iter().flatten()),

                    }

                }

                out.sort_unstable();

                out.dedup();

                reach.insert(x, out);

            }

        };

        // Successors of vertex `i`: `succ[starts[i]..starts[i + 1]]`.

        let mut succ: Vec<u32> = Vec::with_capacity(verts.len() * 2);

        let mut starts: Vec<usize> = Vec::with_capacity(verts.len() + 1);

        let mut indeg: Vec<u32> = vec![0; verts.len()];

        for v in &verts {

            let from = succ.len();

            starts.push(from);

            for s in self.succ.get(v).map(Edges::as_slice).unwrap_or_default() {

                match index.get(s) {

                    Some(i) => succ.push(*i),

                    None => {

                        contracted(*s, &mut reach);

                        succ.extend(reach.get(s).into_iter().flatten());

                    }

                }

            }

            if succ.len() - from > 1 {

                succ[from..].sort_unstable();

                let mut kept = from;

                for i in from..succ.len() {

                    if i == from || succ[i] != succ[kept - 1] {

                        succ[kept] = succ[i];

                        kept += 1;

                    }

                }

                succ.truncate(kept);

            }

            for &w in &succ[from..] {

                indeg[w as usize] += 1;

            }

        }

        starts.push(succ.len());

        // Kahn's algorithm, giving up where two vertices are ready at once.

        let mut ready: Vec<u32> = (0..verts.len() as u32)

            .filter(|&i| indeg[i as usize] == 0)

            .collect();

        let mut order: Vec<AtomKey> = Vec::with_capacity(verts.len());

        let mut seen = 0;

        while let Some(v) = ready.pop() {

            if !ready.is_empty() {

                return None;

            }

            seen += 1;

            if let Vertex::Atom(k) = verts[v as usize] {

                order.push(k);

            }

            for &w in &succ[starts[v as usize]..starts[v as usize + 1]] {

                indeg[w as usize] -= 1;

                if indeg[w as usize] == 0 {

                    ready.push(w);

                }

            }

            if ready.len() > 1 {

                return None;

            }

        }

        (seen == verts.len()).then_some(order)

    }

        }

    }

    /// Linear history: each change depends on every earlier one.

    struct Linear;

    impl DepOracle for Linear {

        fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool {

            a.0[..2] >= b.0[..2]

        }

    }

    /// A file of `n` lines edited `revs` times, `per` lines replaced each

    /// time, as a long-lived file is: most atoms dead, one live chain.

    fn edited_file(n: usize, revs: usize, per: usize) -> FileGraph {

        let hn = |i: usize| {

            let mut b = [0u8; 32];

            b[..2].copy_from_slice(&(i as u16).to_be_bytes());

            ObjectRef(b)

        };

        let mut g = FileGraph::new();

        let first: Vec<String> = (0..n).map(|i| format!("line {i}\n")).collect();

        let first: Vec<&str> = first.iter().map(String::as_str).collect();

        g.insert(hn(1), 0, Vertex::Start, Vertex::End, &lines(&first));

        for r in 2..revs + 2 {

            let order = g.materialize(&Linear).live_atoms();

            let step = order.len() / per;

            for j in 0..per {

                let at = j * step + (r % step.max(1));

                let k = order[at];

                g.delete(

                    hn(r),

                    &AtomRange {

                        change: k.0,

                        from: k.1,

                        to: k.1 + 1,

                    },

                );

                let after = if at == 0 {

                    Vertex::Start

                } else {

                    Vertex::Atom(order[at - 1])

                };

                let before = order

                    .get(at + 1)

                    .map(|k| Vertex::Atom(*k))

                    .unwrap_or(Vertex::End);

                g.insert(hn(r), j as u32, after, before, &lines(&["new\n"]));

            }

        g

    }

    /// The single-order shortcut gives what the general algorithm gives.

    #[test]

    fn the_order_shortcut_agrees_with_the_general_order() {

        let g = edited_file(500, 10, 20);

        assert!(g.as_chain().is_none());

        let fast = g.as_order(&Linear).expect("a single order");

        assert_eq!(

            Materialized {

                segments: vec![Segment::Lines(fast)]

            },

            g.materialize_general(&Linear)

        );

        // Two changes inserting at one place concurrently: a conflict,

        // which the shortcut leaves to the general algorithm.

        let mut g = FileGraph::new();

        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n"]));

        let a = Vertex::Atom((h(1), 0));

        g.insert(h(2), 0, a, Vertex::End, &lines(&["b\n"]));

        g.insert(h(3), 0, a, Vertex::End, &lines(&["c\n"]));

        assert!(g.as_order(&NoDeps).is_none());

        assert!(g.materialize(&NoDeps).is_conflicted());

    }

    /// How long rendering a long-lived file takes (run by hand, in release).

    #[test]

    #[ignore]

    fn bench_materialize_edited_file() {

        let g = edited_file(20_000, 50, 100);

        let t = std::time::Instant::now();

        let mut n = 0;

        for _ in 0..20 {

            n += g.materialize(&Linear).live_atoms().len();

        }

        eprintln!(

            "materialize: {:.2} ms each ({n} atoms)",

            t.elapsed().as_secs_f64() * 1000.0 / 20.0

        );

        for (path, e) in tview.entries.iter() {

            // It shares the base's tree view, which applying the change

            // then updates in place rather than copying.

            drop(base_snapshot);

            drop(entries);

                return Ok(());

            }

            if !st.is_history_only() {

                let c = self.store.get_change(h)?;

                touched.extend(c.edits.iter().map(|e| e.node()));

                touched.extend(c.tree_ops.iter().map(|o| o.node()));

                st.add_unchecked(c);

            }

            // History only: the text of an edit waits unread unless its

            // file's graph is built.

            let (skeleton, texts) = self.store.get_change_lazy(h)?;

            touched.extend(skeleton.edits.iter().map(|e| e.node()));

            touched.extend(skeleton.tree_ops.iter().map(|o| o.node()));

            let built = skeleton

                .edits

                .iter()

                .any(|e| !matches!(e, Edit::Replace { .. }) && st.is_built(&e.node()));

            if built {

                let full = self.store.get_change(h)?;

                st.add_known_mixed(*h, full, skeleton, texts);

            } else {

                st.add_known(*h, skeleton, texts);

            for (path, e) in view.entries.iter() {

            for (p, e) in view.entries.iter() {

        for (p, e) in base_snapshot.tree.entries.iter() {

    /// Whether `node`'s file graph is built (always, in a full state).

    pub fn is_built(&self, node: &NodeId) -> bool {

        self.deferred.is_none() || self.files.contains_key(node)

    }

    /// The view, once computed, with the path of each directory in it;

    /// kept up to date as ops apply when that is simple (see

    /// `update_view`), cleared otherwise.

    view_cache: std::sync::OnceLock<CachedView>,

}

#[derive(Clone, Debug, Default)]

struct CachedView {

    view: TreeView,

    dirs: HashMap<NodeId, String>,

impl CachedView {

    fn new(view: TreeView) -> CachedView {

        let mut dirs: HashMap<NodeId, String> = view

            .entries

            .values()

            .filter(|e| e.kind == NodeKind::Dir)

            .map(|e| (e.node, e.path.clone()))

            .collect();

        dirs.insert(NodeId::ROOT, String::new());

        CachedView { view, dirs }

    }

}

    /// entries carry a `.oxy-conflict-<n>` suffix. Shared, so a view is

    /// cheap to clone.

    pub entries: std::sync::Arc<BTreeMap<String, TreeEntry>>,

        let cached = self.view_cache.take();

        // Whether the placement or mode atom this op retires was live.

        let was_live = match op {

            TreeOp::RemoveNode { placement, .. } => self.placement_live(&op_key(*placement)),

            TreeOp::Move { old, .. } => self.placement_live(&op_key(*old)),

            TreeOp::SetMode { old, .. } => self.mode_live(&op_key(*old)),

            TreeOp::AddNode { .. } => false,

        };

        self.apply_to_graph(change, index, op);

        if let Some(mut c) = cached {

            if self.update_view(&mut c, (change, index), op, was_live) {

                #[cfg(test)]

                assert_eq!(

                    c.view,

                    self.compute_view(),

                    "view kept up to date by {op:?}"

                );

                self.view_cache = std::sync::OnceLock::from(c);

            }

        }

    }

    fn apply_to_graph(&mut self, change: ChangeHash, index: u32, op: &TreeOp) {

    /// Bring the cached view `c` up to date with `op` (already applied as

    /// `key`) where that is simple and the view has no conflicts; false

    /// when it must be computed again. `was_live`: whether the placement or

    /// mode atom `op` retires was live before it.

    fn update_view(&self, c: &mut CachedView, key: OpKey, op: &TreeOp, was_live: bool) -> bool {

        if !c.view.conflicts.is_empty() {

            return false;

        }

        match op {

            TreeOp::AddNode { node, .. } => self.view_add(c, *node, key),

            TreeOp::RemoveNode { node, placement } => {

                !was_live || self.view_remove(c, *node, op_key(*placement))

            }

            TreeOp::Move { node, old, .. } => {

                (!was_live || self.view_remove(c, *node, op_key(*old)))

                    && self.view_add(c, *node, key)

            }

            TreeOp::SetMode { node, .. } => {

                let live = self.live_placements(node);

                match live.as_slice() {

                    [] => true,

                    [(k, p)] => {

                        let Some(path) = c.dirs.get(&p.parent).map(|d| join(d, &p.name)) else {

                            return false;

                        };

                        let Some(mode) = self.entry_mode(node) else {

                            return false;

                        };

                        let entries = std::sync::Arc::make_mut(&mut c.view.entries);

                        match entries.get_mut(&path) {

                            Some(e) if e.node == *node && e.placement == *k => {

                                (e.mode_atom, e.mode) = mode;

                                true

                            }

                            _ => false,

                        }

                    }

                    _ => false,

                }

            }

        }

    }

    /// The view entry for `node`'s placement `key`, just made live.

    fn view_add(&self, c: &mut CachedView, node: NodeId, key: OpKey) -> bool {

        if !self.placement_live(&key) {

            return true;

        }

        if self

            .live_placements_of

            .get(&node)

            .is_none_or(|s| s.len() != 1)

        {

            return false;

        }

        let Some(p) = self.placements.get(&key) else {

            return false;

        };

        let Some(path) = c.dirs.get(&p.parent).map(|d| join(d, &p.name)) else {

            return false;

        };

        let Some((mode_atom, mode)) = self.entry_mode(&node) else {

            return false;

        };

        let kind = self.kind(&node).unwrap_or(NodeKind::File);

        let entries = std::sync::Arc::make_mut(&mut c.view.entries);

        if entries.contains_key(&path) || node == NodeId::ROOT {

            return false;

        }

        // Nothing can be placed under a directory that was not in the view

        // yet: it would have been an orphan, and the view had no conflicts.

        if kind == NodeKind::Dir {

            c.dirs.insert(node, path.clone());

        }

        entries.insert(

            path.clone(),

            TreeEntry {

                path,

                node,

                kind,

                mode,

                placement: key,

                mode_atom,

            },

        );

        true

    }

    /// Drop the view entry of `node`'s placement `key`, just retired.

    fn view_remove(&self, c: &mut CachedView, node: NodeId, key: OpKey) -> bool {

        if self.live_placements_of.contains_key(&node) {

            return false;

        }

        let Some(p) = self.placements.get(&key) else {

            return false;

        };

        let Some(path) = c.dirs.get(&p.parent).map(|d| join(d, &p.name)) else {

            return false;

        };

        let entries = std::sync::Arc::make_mut(&mut c.view.entries);

        match entries.get(&path) {

            Some(e) if e.node == node && e.placement == key => {}

            _ => return false,

        }

        if entries.get(&path).is_some_and(|e| e.kind == NodeKind::Dir) {

            let prefix = format!("{path}/");

            if entries

                .range(prefix.clone()..)

                .next()

                .is_some_and(|(k, _)| k.starts_with(&prefix))

            {

                return false;

            }

            c.dirs.remove(&node);

        }

        entries.remove(&path);

        true

    }

    /// The mode atom and mode of `node`'s entry, as `compute_view` finds

    /// them; `None` when its live modes conflict.

    fn entry_mode(&self, node: &NodeId) -> Option<(Option<OpKey>, Mode)> {

        let lm = self.live_modes(node);

        let distinct: BTreeSet<Mode> = lm.iter().map(|(_, m)| *m).collect();

        if distinct.len() > 1 {

            return None;

        }

        let mode_atom = lm.iter().map(|(k, _)| *k).max();

        let mode = mode_atom

            .and_then(|k| self.modes.get(&k).map(|(_, m)| *m))

            .unwrap_or_default();

        Some((mode_atom, mode))

    }

        self.view_cache

            .get_or_init(|| CachedView::new(self.compute_view()))

            .view

            .clone()

        let mut entries: BTreeMap<String, TreeEntry> = BTreeMap::new();

                    entries.insert(

        view.entries = std::sync::Arc::new(entries);

    }

}

fn join(dir: &str, name: &str) -> String {

    if dir.is_empty() {

        name.to_string()

    } else {

        format!("{dir}/{name}")

    }

    /// Each op applied to a graph whose view is cached keeps it up to date

    /// or drops it: `apply` checks every kept view against a full one.

    #[test]

    fn cached_view_follows_ops() {

        let at = |c: u8, i: u32| OpRef {

            change: h(c),

            index: i,

        };

        let mut g = TreeGraph::new();

        let ops = [

            TreeOp::AddNode {

                node: nid(1),

                kind: NodeKind::Dir,

                mode: Mode::TEXT,

                parent: NodeId::ROOT,

                name: "src".into(),

            },

            TreeOp::AddNode {

                node: nid(2),

                kind: NodeKind::File,

                mode: Mode::TEXT,

                parent: nid(1),

                name: "a.rs".into(),

            },

            TreeOp::SetMode {

                node: nid(2),

                old: at(1, 1),

                mode: Mode {

                    exec: true,

                    opaque: false,

                },

            },

            TreeOp::Move {

                node: nid(2),

                old: at(1, 1),

                parent: NodeId::ROOT,

                name: "b.rs".into(),

            },

            // Moving an empty directory, then removing it.

            TreeOp::Move {

                node: nid(1),

                old: at(1, 0),

                parent: NodeId::ROOT,

                name: "lib".into(),

            },

            TreeOp::RemoveNode {

                node: nid(1),

                placement: at(1, 4),

            },

            // A name taken twice: a conflict, so the view is computed again.

            TreeOp::AddNode {

                node: nid(3),

                kind: NodeKind::File,

                mode: Mode::TEXT,

                parent: NodeId::ROOT,

                name: "b.rs".into(),

            },

        ];

        for (i, op) in ops.iter().enumerate() {

            let _ = g.view();

            g.apply(h(1), i as u32, op);

            assert_eq!(g.view(), g.compute_view());

        }

        let v = g.view();

        assert_eq!(paths(&v), ["b.rs.oxy-conflict-1", "b.rs.oxy-conflict-2"]);

        assert!(v.entries.values().any(|e| e.mode.exec));