crates/oxy-core/src/graph.rs at v0.10.0 · andymccall/oxygen

◆ v0.10.0 oxygen / crates / oxy-core / src / graph.rs
66.5 KiB · Rust · last changed oxy resolve --both keeps both sides of an adjacent insertion (closes #121) 9 days ago source blame history raw
//! The per-file atom graph (spec §7.3), its materialization, and text conflict
//! detection (spec §9.1, §9.5).
//!
//! The graph is a pure function of the set of changes applied to it: inserts
//! add vertices and edges, deletes set a flag, and nothing is ever removed.

use crate::fasthash::{FastMap as HashMap, FastSet as HashSet};
use crate::hash::ChangeHash;
use crate::lines::{LineRef, Lines};
use crate::objects::AtomRange;
use std::collections::{BTreeMap, BTreeSet};

/// `(introducing change, index within that change for this node)`.
pub type AtomKey = (ChangeHash, u32);

#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
pub enum Vertex {
    Start,
    Atom(AtomKey),
    End,
}

/// Transitive dependency test between changes; `depends_on(a, a)` is true.
pub trait DepOracle {
    fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool;
}

/// Another oracle's answers, each asked once: rendering one file asks about
/// the same few pairs over and over (a change deleting a block of lines
/// another inserted), and in a long history each answer is a walk through
/// thousands of changes (oxygen#96).
struct MemoDeps<'a> {
    inner: &'a dyn DepOracle,
    known: std::cell::RefCell<crate::fasthash::FastMap<(ChangeHash, ChangeHash), bool>>,
}

impl DepOracle for MemoDeps<'_> {
    fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool {
        if let Some(v) = self.known.borrow().get(&(*a, *b)) {
            return *v;
        }
        let v = self.inner.depends_on(a, b);
        self.known.borrow_mut().insert((*a, *b), v);
        v
    }
}

/// No change depends on any other: every pair commutes.
pub struct NoDeps;
impl DepOracle for NoDeps {
    fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool {
        a == b
    }
}

#[derive(Default, Clone, Debug)]
struct AtomInfo {
    /// `None` until the introducing change has been applied; a line of the
    /// insert's shared buffer.
    content: Option<LineRef>,
    deleted_by: BTreeSet<ChangeHash>,
}

#[derive(Clone, Debug)]
pub struct FileGraph {
    atoms: HashMap<AtomKey, AtomInfo>,
    /// Every vertex, with its direct successors.
    succ: HashMap<Vertex, Edges>,
    /// The live atoms' order, once known to be the graph's only one.
    order: OrderSlot,
}

/// A file graph's live atoms in order, when the graph orders them one way
/// only: found by [`FileGraph::materialize`] and brought up to date by
/// [`Order::splice`] as a change's edits apply, so a long-lived file
/// renders in time that follows its live lines rather than every line it
/// ever had. Any other change to the graph drops it.
#[derive(Debug)]
pub struct Order {
    atoms: Vec<AtomKey>,
    /// Atoms deleted since the order was last confirmed: it holds while
    /// none of them is a ghost (spec §9.1), which only a render can ask,
    /// since it needs to know how the changes depend on each other.
    unchecked: Vec<AtomKey>,
    confirmed: std::sync::atomic::AtomicBool,
}

/// Holds a graph's [`Order`]; filled in by a render, which only reads the
/// graph.
#[derive(Debug, Default)]
struct OrderSlot(std::sync::Mutex<Option<std::sync::Arc<Order>>>);

impl OrderSlot {
    fn get(&self) -> Option<std::sync::Arc<Order>> {
        self.0.lock().unwrap_or_else(|e| e.into_inner()).clone()
    }
    fn set(&self, o: Option<std::sync::Arc<Order>>) {
        *self.0.lock().unwrap_or_else(|e| e.into_inner()) = o;
    }
    fn take(&mut self) -> Option<std::sync::Arc<Order>> {
        self.0.get_mut().unwrap_or_else(|e| e.into_inner()).take()
    }
}

impl Clone for OrderSlot {
    fn clone(&self) -> Self {
        OrderSlot(std::sync::Mutex::new(self.get()))
    }
}

impl Order {
    fn known(atoms: Vec<AtomKey>) -> Order {
        Order {
            atoms,
            unchecked: Vec::new(),
            confirmed: std::sync::atomic::AtomicBool::new(true),
        }
    }

    /// The order after change `h` inserts the runs `inserts` (after,
    /// before, first index, count) and deletes `deleted`, as its edits
    /// apply; `None` where that is not certain to be the graph's only
    /// order: an anchor not in the order, live lines between an insert's
    /// anchors, or two inserts with nothing kept between them.
    fn splice(
        &self,
        h: ChangeHash,
        inserts: &[(Vertex, Vertex, u32, u32)],
        deleted: &[AtomKey],
    ) -> Option<std::sync::Arc<Order>> {
        let mut want: HashSet<AtomKey> = deleted.iter().copied().collect();
        for (a, b, _, _) in inserts {
            for v in [a, b] {
                if let Vertex::Atom(k) = v {
                    want.insert(*k);
                }
            }
        }
        let mut pos: HashMap<AtomKey, usize> = HashMap::default();
        for (i, k) in self.atoms.iter().enumerate() {
            if want.contains(k) {
                pos.insert(*k, i);
            }
        }
        let len = self.atoms.len();
        let mut gone = vec![false; len];
        let mut unchecked = if self.confirmed.load(std::sync::atomic::Ordering::Relaxed) {
            Vec::new()
        } else {
            self.unchecked.clone()
        };
        for k in deleted {
            if k.0 == h {
                return None;
            }
            if let Some(&i) = pos.get(k) {
                if !gone[i] {
                    gone[i] = true;
                    unchecked.push(*k);
                }
            }
        }
        // Each run goes in the gap its anchors leave (slot `i`: before
        // `atoms[i]`), which must hold nothing that stays.
        let mut slots: Vec<(usize, usize, u32, u32)> = Vec::with_capacity(inserts.len());
        for &(a, b, first, count) in inserts {
            let from = match a {
                Vertex::Start => 0,
                Vertex::Atom(k) => pos.get(&k)? + 1,
                Vertex::End => return None,
            };
            let to = match b {
                Vertex::End => len,
                Vertex::Atom(k) => *pos.get(&k)?,
                Vertex::Start => return None,
            };
            if from > to || gone[from..to].iter().any(|g| !g) {
                return None;
            }
            slots.push((from, to, first, count));
        }
        // Runs one after another need a kept line between them, or the
        // graph would not say which comes first.
        slots.sort_unstable();
        for w in slots.windows(2) {
            let (end, next) = (w[0].1, w[1].0);
            if end >= next || !gone[end..next].iter().any(|g| !g) {
                return None;
            }
        }
        let added: usize = slots.iter().map(|s| s.3 as usize).sum();
        let mut atoms = Vec::with_capacity(len + added);
        let mut slots = slots.into_iter().peekable();
        let mut runs_at = |i: usize, atoms: &mut Vec<AtomKey>| {
            while let Some(&(from, _, first, count)) = slots.peek() {
                if from != i {
                    break;
                }
                atoms.extend((first..first + count).map(|j| (h, j)));
                slots.next();
            }
        };
        for (i, (k, g)) in self.atoms.iter().zip(&gone).enumerate() {
            runs_at(i, &mut atoms);
            if !g {
                atoms.push(*k);
            }
        }
        runs_at(len, &mut atoms);
        let confirmed = unchecked.is_empty();
        Some(std::sync::Arc::new(Order {
            atoms,
            unchecked,
            confirmed: std::sync::atomic::AtomicBool::new(confirmed),
        }))
    }
}

/// A vertex's direct successors, sorted and without repeats. Nearly every
/// vertex has one, which is kept inline without an allocation.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
enum Edges {
    #[default]
    None,
    One(Vertex),
    Many(Vec<Vertex>),
}

impl Edges {
    fn insert(&mut self, v: Vertex) {
        match self {
            Edges::None => *self = Edges::One(v),
            Edges::One(a) if *a == v => {}
            Edges::One(a) => {
                let a = *a;
                *self = Edges::Many(if a < v { vec![a, v] } else { vec![v, a] });
            }
            Edges::Many(list) => {
                if let Err(i) = list.binary_search(&v) {
                    list.insert(i, v);
                }
            }
        }
    }

    fn as_slice(&self) -> &[Vertex] {
        match self {
            Edges::None => &[],
            Edges::One(v) => std::slice::from_ref(v),
            Edges::Many(list) => list,
        }
    }

    fn iter(&self) -> std::slice::Iter<'_, Vertex> {
        self.as_slice().iter()
    }
}

impl Default for FileGraph {
    fn default() -> Self {
        Self::new()
    }
}

/// One piece of a materialized file.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Segment {
    Lines(Vec<AtomKey>),
    /// Order conflict: alternatives that cannot be ordered against each other.
    Conflict(Vec<Vec<AtomKey>>),
    /// Delete/insert conflict: `inserted` was anchored to `deleted` by a change
    /// that commutes with the deletion.
    Zombie {
        deleted: Vec<AtomKey>,
        inserted: Vec<AtomKey>,
    },
}

#[derive(Clone, Debug, PartialEq, Eq, Default)]
pub struct Materialized {
    pub segments: Vec<Segment>,
}

impl Materialized {
    pub fn is_conflicted(&self) -> bool {
        self.segments
            .iter()
            .any(|s| !matches!(s, Segment::Lines(_)))
    }
    pub fn conflict_count(&self) -> usize {
        self.segments
            .iter()
            .filter(|s| !matches!(s, Segment::Lines(_)))
            .count()
    }
    /// Every live atom in materialized order, conflict sides concatenated.
    pub fn live_atoms(&self) -> Vec<AtomKey> {
        let mut out = Vec::new();
        for s in &self.segments {
            match s {
                Segment::Lines(a) => out.extend(a),
                Segment::Conflict(sides) => sides.iter().for_each(|x| out.extend(x)),
                Segment::Zombie { inserted, .. } => out.extend(inserted),
            }
        }
        out
    }
}

impl FileGraph {
    pub fn new() -> Self {
        let mut g = FileGraph {
            atoms: HashMap::default(),
            succ: HashMap::default(),
            order: OrderSlot::default(),
        };
        g.edge(Vertex::Start, Vertex::End);
        g
    }

    fn edge(&mut self, a: Vertex, b: Vertex) {
        self.succ.entry(a).or_default().insert(b);
        self.succ.entry(b).or_default();
    }

    /// Apply an `Insert` by `change` whose first new atom has index `first_index`.
    pub fn insert(
        &mut self,
        change: ChangeHash,
        first_index: u32,
        after: Vertex,
        before: Vertex,
        lines: &Lines,
    ) {
        self.insert_owned(change, first_index, after, before, lines.clone());
    }

    /// [`FileGraph::insert`] taking the lines, so loading a state moves
    /// them in rather than copying. Each new atom's entry is made once, as
    /// the source of the next edge, and the chain's ends are ensured last.
    pub fn insert_owned(
        &mut self,
        change: ChangeHash,
        first_index: u32,
        after: Vertex,
        before: Vertex,
        lines: Lines,
    ) {
        self.order.take();
        self.atoms.reserve(lines.len());
        self.succ.reserve(lines.len() + 1);
        let mut prev = after;
        for i in 0..lines.len() {
            let key = (change, first_index + i as u32);
            self.atoms.entry(key).or_default().content =
                Some(LineRef::new(lines.clone(), i as u32));
            let v = Vertex::Atom(key);
            self.succ.entry(prev).or_default().insert(v);
            prev = v;
        }
        self.succ.entry(prev).or_default().insert(before);
        self.succ.entry(before).or_default();
    }

    /// Apply a `Delete` of `range` by change `by`.
    pub fn delete(&mut self, by: ChangeHash, range: &AtomRange) {
        self.order.take();
        for i in range.from..range.to {
            self.atoms
                .entry((range.change, i))
                .or_default()
                .deleted_by
                .insert(by);
        }
    }

    pub fn is_live(&self, k: &AtomKey) -> bool {
        self.atoms
            .get(k)
            .is_some_and(|a| a.content.is_some() && a.deleted_by.is_empty())
    }

    pub fn content(&self, k: &AtomKey) -> Option<&[u8]> {
        self.atoms
            .get(k)
            .and_then(|a| a.content.as_ref().map(LineRef::bytes))
    }

    pub fn deleters(&self, k: &AtomKey) -> impl Iterator<Item = &ChangeHash> {
        self.atoms
            .get(k)
            .into_iter()
            .flat_map(|a| a.deleted_by.iter())
    }

    /// Whether the conflict at `m.segments[i]` is an adjacent insertion
    /// (oxygen#121): its sides only add lines between two lines that were
    /// next to each other, so keeping every side repeats nothing. It is not
    /// when a line there was deleted by a change only some sides build on:
    /// two changes that each replaced the same line conflict the same way,
    /// and keeping both would keep two versions of it. A line deleted in
    /// history every side shares does not count.
    pub fn adjacent_insertion(&self, m: &Materialized, i: usize, deps: &dyn DepOracle) -> bool {
        let Some(Segment::Conflict(sides)) = m.segments.get(i) else {
            return false;
        };
        let before = match i.checked_sub(1).map(|j| &m.segments[j]) {
            None => Vertex::Start,
            Some(Segment::Lines(a)) => match a.last() {
                Some(k) => Vertex::Atom(*k),
                None => return false,
            },
            Some(_) => return false,
        };
        let on_side: HashSet<AtomKey> = sides.iter().flatten().copied().collect();
        let side_changes: Vec<BTreeSet<ChangeHash>> = sides
            .iter()
            .map(|s| s.iter().map(|a| a.0).collect())
            .collect();
        let shared = |d: &ChangeHash| {
            side_changes
                .iter()
                .all(|s| s.iter().any(|c| deps.depends_on(c, d)))
        };
        // From the line before, through the sides' lines and deleted ones,
        // up to the next live line.
        let mut seen: HashSet<AtomKey> = HashSet::default();
        let mut todo = vec![before];
        while let Some(v) = todo.pop() {
            for &w in self.succ.get(&v).map(Edges::as_slice).unwrap_or(&[]) {
                let Vertex::Atom(k) = w else { continue };
                if !seen.insert(k) {
                    continue;
                }
                if !on_side.contains(&k) {
                    if self.is_live(&k) {
                        continue;
                    }
                    if self.deleters(&k).any(|d| !shared(d)) {
                        return false;
                    }
                }
                todo.push(w);
            }
        }
        true
    }

    /// Number of atoms introduced by `change` in this graph (for index bookkeeping).
    pub fn atom_count(&self) -> usize {
        self.atoms.len()
    }

    /// The changes that inserted a live atom directly after `k`. A change
    /// that deletes `k` must depend on them (spec §8.1), or `is_ghost`
    /// reads the deletion as concurrent with those insertions.
    /// Every atom on some path from `first` to `last`, both included, live
    /// or deleted (spec §8): the atoms a range of lines is made of, and
    /// those that were deleted from between them. Empty when `last` does
    /// not follow `first`.
    pub fn between(&self, first: &AtomKey, last: &AtomKey) -> Vec<AtomKey> {
        let (from, to) = (Vertex::Atom(*first), Vertex::Atom(*last));
        let mut ahead: HashSet<Vertex> = HashSet::default();
        let mut stack = vec![from];
        while let Some(v) = stack.pop() {
            if ahead.insert(v) {
                stack.extend(
                    self.succ
                        .get(&v)
                        .map(|e| e.as_slice())
                        .unwrap_or(&[])
                        .iter()
                        .copied(),
                );
            }
        }
        if !ahead.contains(&to) {
            return vec![];
        }
        let mut pred: HashMap<Vertex, Vec<Vertex>> = HashMap::default();
        for (u, es) in &self.succ {
            if ahead.contains(u) {
                for w in es.iter() {
                    pred.entry(*w).or_default().push(*u);
                }
            }
        }
        let mut behind: HashSet<Vertex> = HashSet::default();
        let mut stack = vec![to];
        while let Some(v) = stack.pop() {
            if behind.insert(v) {
                stack.extend(pred.get(&v).into_iter().flatten().copied());
            }
        }
        let mut out: Vec<AtomKey> = ahead
            .intersection(&behind)
            .filter_map(|v| match v {
                Vertex::Atom(k) if self.atoms.contains_key(k) => Some(*k),
                _ => None,
            })
            .collect();
        out.sort();
        out
    }

    /// The changes that inserted or deleted any of `atoms`.
    pub fn touching(&self, atoms: &[AtomKey]) -> BTreeSet<ChangeHash> {
        let mut out = BTreeSet::new();
        for k in atoms {
            out.insert(k.0);
            if let Some(info) = self.atoms.get(k) {
                out.extend(info.deleted_by.iter().copied());
            }
        }
        out
    }

    pub fn live_successor_changes(&self, k: &AtomKey) -> Vec<ChangeHash> {
        self.succ
            .get(&Vertex::Atom(*k))
            .map(|ss| {
                ss.iter()
                    .filter_map(|s| match s {
                        Vertex::Atom(y) if self.is_live(y) => Some(y.0),
                        _ => None,
                    })
                    .collect()
            })
            .unwrap_or_default()
    }

    fn is_ghost(&self, k: &AtomKey, info: &AtomInfo, deps: &dyn DepOracle) -> bool {
        // A deleted atom is a ghost when a live direct successor was inserted
        // by a change that commutes with every deleter: neither depends on
        // the other (spec §9.1, delete/insert). If the inserter came after the
        // deletion, or the deleter saw the insertion, there is no conflict.
        self.succ.get(&Vertex::Atom(*k)).is_some_and(|ss| {
            ss.iter().any(|s| match s {
                Vertex::Atom(y) if self.is_live(y) => !info
                    .deleted_by
                    .iter()
                    .any(|d| deps.depends_on(d, &y.0) || deps.depends_on(&y.0, d)),
                _ => false,
            })
        })
    }

    /// Successors of `v` in the graph with non-kept vertices contracted away.
    fn reduced_succ(
        &self,
        v: Vertex,
        kept: &HashSet<Vertex>,
        memo: &mut HashMap<Vertex, BTreeSet<Vertex>>,
    ) -> BTreeSet<Vertex> {
        let direct = self.succ.get(&v).map(Edges::as_slice).unwrap_or_default();
        // The common case, a successor that is itself kept: nothing to
        // contract.
        if direct.iter().all(|s| kept.contains(s)) {
            return direct.iter().copied().collect();
        }
        let mut out = BTreeSet::new();
        let mut stack: Vec<Vertex> = direct.to_vec();
        let mut seen = HashSet::default();
        while let Some(s) = stack.pop() {
            if kept.contains(&s) {
                out.insert(s);
            } else if seen.insert(s) {
                if let Some(m) = memo.get(&s) {
                    out.extend(m.iter().copied());
                } else if let Some(next) = self.succ.get(&s) {
                    stack.extend(next.iter().copied());
                }
            }
        }
        out
    }

    /// The atoms in order when the graph is one chain from Start to End with
    /// nothing deleted: a file only ever inserted into in sequence, as every
    /// file of a fresh commit or a clone is. Such a graph has no conflict.
    /// An edge to End besides the chain's next atom (Start's own, or an
    /// append's anchor) orders nothing, since End is last anyway.
    fn as_chain(&self) -> Option<Vec<AtomKey>> {
        if self
            .atoms
            .values()
            .any(|a| a.content.is_none() || !a.deleted_by.is_empty())
        {
            return None;
        }
        let mut order = Vec::with_capacity(self.atoms.len());
        let mut v = Vertex::Start;
        loop {
            let succ = self.succ.get(&v)?.as_slice();
            let mut atoms = succ.iter().filter(|s| **s != Vertex::End);
            match (atoms.next(), atoms.next()) {
                (None, _) if succ.contains(&Vertex::End) => break,
                (Some(Vertex::Atom(k)), None) if order.len() < self.atoms.len() => {
                    order.push(*k);
                    v = Vertex::Atom(*k);
                }
                _ => return None,
            }
        }
        (order.len() == self.atoms.len()).then_some(order)
    }

    /// Order the live atoms and locate conflicts.
    pub fn materialize(&self, deps: &dyn DepOracle) -> Materialized {
        let deps = &MemoDeps {
            inner: deps,
            known: Default::default(),
        };
        let lines = |order: Vec<AtomKey>| Materialized {
            segments: if order.is_empty() {
                vec![]
            } else {
                vec![Segment::Lines(order)]
            },
        };
        use std::sync::atomic::Ordering::Relaxed;
        // Which way it went, and how long it took (`OXY_TIMINGS`).
        let started = crate::timing::enabled().then(std::time::Instant::now);
        let took = |name: &'static str| {
            if let Some(t) = started {
                crate::timing::add(name, t.elapsed());
            }
        };
        if let Some(o) = self.order.get() {
            let holds = o.confirmed.load(Relaxed)
                || o.unchecked.iter().all(|k| {
                    self.atoms
                        .get(k)
                        .is_none_or(|info| !self.is_ghost(k, info, deps))
                });
            if holds {
                o.confirmed.store(true, Relaxed);
                took("graph: kept order");
                return lines(o.atoms.clone());
            }
            self.order.set(None);
        }
        // A chain (nothing ever deleted) is quick to walk, and a fresh tree
        // is all chains: no order is kept for one.
        if let Some(order) = self.as_chain() {
            took("graph: chain");
            return lines(order);
        }
        if let Some(order) = self.as_order(deps) {
            self.order
                .set(Some(std::sync::Arc::new(Order::known(order.clone()))));
            took("graph: single order");
            return lines(order);
        }
        let m = self.materialize_general(deps);
        took("graph: general");
        m
    }

    /// Take the kept order, to [`Order::splice`] it once a change's edits
    /// have applied (they drop it).
    pub fn take_order(&mut self) -> Option<std::sync::Arc<Order>> {
        self.order.take()
    }

    /// Keep `order` (taken before change `h`'s edits applied) spliced by
    /// them: `inserts` (after, before, first index, count) and `deleted`.
    /// Changes may apply in any order, so a line may arrive already
    /// deleted by a change applied before it: then the order is dropped.
    pub fn keep_spliced(
        &mut self,
        order: std::sync::Arc<Order>,
        h: ChangeHash,
        inserts: &[(Vertex, Vertex, u32, u32)],
        deleted: &[AtomKey],
    ) {
        let live = inserts
            .iter()
            .all(|&(_, _, first, count)| (first..first + count).all(|i| self.is_live(&(h, i))));
        let spliced = if live {
            order.splice(h, inserts, deleted)
        } else {
            None
        };
        *self.order.0.get_mut().unwrap_or_else(|e| e.into_inner()) = spliced;
    }

    /// 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)
    }

    /// [`FileGraph::materialize`] for any graph: contraction, then a
    /// topological order with conflict regions.
    fn materialize_general(&self, deps: &dyn DepOracle) -> Materialized {
        // 1. Vertices that survive contraction: live atoms, ghosts, Start, End.
        let mut kept: HashSet<Vertex> = HashSet::default();
        let mut ghosts: HashSet<AtomKey> = HashSet::default();
        kept.insert(Vertex::Start);
        kept.insert(Vertex::End);
        for (k, info) in &self.atoms {
            if info.content.is_none() {
                continue;
            }
            if info.deleted_by.is_empty() {
                kept.insert(Vertex::Atom(*k));
            } else if self.is_ghost(k, info, deps) {
                kept.insert(Vertex::Atom(*k));
                ghosts.insert(*k);
            }
        }

        // 2. Reduced graph over kept vertices.
        let mut memo = HashMap::default();
        let mut rsucc: HashMap<Vertex, BTreeSet<Vertex>> = HashMap::default();
        let mut indeg: HashMap<Vertex, usize> = HashMap::default();
        for &u in &kept {
            indeg.entry(u).or_insert(0);
            let rs = self.reduced_succ(u, &kept, &mut memo);
            for &w in &rs {
                *indeg.entry(w).or_insert(0) += 1;
            }
            rsucc.insert(u, rs);
        }

        // 3. Kahn's algorithm with side labelling for conflict regions.
        let mut ready: BTreeSet<Vertex> = indeg
            .iter()
            .filter(|(_, &d)| d == 0)
            .map(|(v, _)| *v)
            .collect();
        let mut side: HashMap<Vertex, u32> = HashMap::default();
        let mut joins: HashSet<Vertex> = HashSet::default();
        let mut next_side = 0u32;
        let mut plain: Vec<Vertex> = Vec::new();
        let mut conflict: Option<BTreeMap<u32, Vec<Vertex>>> = None;
        let mut segments: Vec<Segment> = Vec::new();

        let flush_plain = |plain: &mut Vec<Vertex>, segments: &mut Vec<Segment>| {
            let atoms: Vec<AtomKey> = plain
                .iter()
                .filter_map(|v| {
                    if let Vertex::Atom(k) = v {
                        Some(*k)
                    } else {
                        None
                    }
                })
                .collect();
            plain.clear();
            if !atoms.is_empty() {
                segments.extend(split_zombies(atoms, &ghosts));
            }
        };
        let finish_conflict = |c: BTreeMap<u32, Vec<Vertex>>, segments: &mut Vec<Segment>| {
            let sides: Vec<Vec<AtomKey>> = c
                .into_values()
                .map(|vs| {
                    vs.into_iter()
                        .filter_map(|v| match v {
                            Vertex::Atom(k) if !ghosts.contains(&k) => Some(k),
                            _ => None,
                        })
                        .collect::<Vec<_>>()
                })
                .filter(|s| !s.is_empty())
                .collect();
            match sides.len() {
                0 => {}
                1 => segments.push(Segment::Lines(sides.into_iter().next().unwrap())),
                _ => segments.push(Segment::Conflict(sides)),
            }
        };

        while !ready.is_empty() {
            if ready.len() >= 2 {
                if conflict.is_none() {
                    flush_plain(&mut plain, &mut segments);
                    conflict = Some(BTreeMap::new());
                }
                for r in &ready {
                    if !side.contains_key(r) {
                        side.insert(*r, next_side);
                        next_side += 1;
                    }
                }
            }
            let v = ready.pop_first().unwrap();
            let my_side = side.get(&v).copied();
            match (&mut conflict, my_side) {
                (Some(c), Some(s)) => c.entry(s).or_default().push(v),
                (Some(_), None) => {
                    let c = conflict.take().unwrap();
                    finish_conflict(c, &mut segments);
                    plain.push(v);
                }
                (None, _) => plain.push(v),
            }
            for &w in &rsucc[&v] {
                let d = indeg.get_mut(&w).unwrap();
                *d -= 1;
                if conflict.is_some() && !joins.contains(&w) {
                    match (my_side, side.get(&w).copied()) {
                        (Some(s), None) => {
                            side.insert(w, s);
                        }
                        (Some(s), Some(t)) if s != t => {
                            side.remove(&w);
                            joins.insert(w);
                        }
                        (None, Some(_)) => {
                            side.remove(&w);
                            joins.insert(w);
                        }
                        _ => {}
                    }
                }
                if *d == 0 {
                    ready.insert(w);
                }
            }
        }
        if let Some(c) = conflict.take() {
            finish_conflict(c, &mut segments);
        }
        flush_plain(&mut plain, &mut segments);
        Materialized { segments }
    }

    /// Render a materialization to bytes with conflict markers (spec §9.5).
    /// `label` gives the short description of a change for marker headers.
    pub fn render(&self, m: &Materialized, label: &dyn Fn(&ChangeHash) -> String) -> Vec<u8> {
        let total = m.conflict_count();
        let mut n = 0;
        let mut out: Vec<u8> = Vec::new();
        let push_atoms = |out: &mut Vec<u8>, atoms: &[AtomKey]| {
            for a in atoms {
                if let Some(c) = self.content(a) {
                    out.extend_from_slice(c);
                }
            }
        };
        let newline_if_needed = |out: &mut Vec<u8>| {
            if !out.is_empty() && *out.last().unwrap() != b'\n' {
                out.push(b'\n');
            }
        };
        for seg in &m.segments {
            match seg {
                Segment::Lines(a) => push_atoms(&mut out, a),
                Segment::Conflict(sides) => {
                    n += 1;
                    let k = sides.len();
                    for (i, s) in sides.iter().enumerate() {
                        newline_if_needed(&mut out);
                        let who = s.first().map(|a| label(&a.0)).unwrap_or_default();
                        let marker = if i == 0 { "<<<<<<<" } else { "=======" };
                        out.extend_from_slice(
                            format!("{marker} oxy conflict {n} of {total}, side {} of {k}: change {who}\n", i + 1).as_bytes(),
                        );
                        push_atoms(&mut out, s);
                    }
                    newline_if_needed(&mut out);
                    out.extend_from_slice(
                        format!(">>>>>>> oxy conflict {n} of {total} end\n").as_bytes(),
                    );
                }
                Segment::Zombie { deleted, inserted } => {
                    n += 1;
                    newline_if_needed(&mut out);
                    let deleter = deleted
                        .first()
                        .and_then(|a| self.deleters(a).next().copied())
                        .map(|d| label(&d))
                        .unwrap_or_default();
                    let inserter = inserted.first().map(|a| label(&a.0)).unwrap_or_default();
                    out.extend_from_slice(
                        format!("<<<<<<< oxy conflict {n} of {total}, side 1 of 2: deleted by change {deleter}\n-------\n").as_bytes(),
                    );
                    push_atoms(&mut out, deleted);
                    newline_if_needed(&mut out);
                    out.extend_from_slice(
                        format!(
                            "======= oxy conflict {n} of {total}, side 2 of 2: change {inserter}\n"
                        )
                        .as_bytes(),
                    );
                    push_atoms(&mut out, inserted);
                    newline_if_needed(&mut out);
                    out.extend_from_slice(
                        format!(">>>>>>> oxy conflict {n} of {total} end\n").as_bytes(),
                    );
                }
            }
        }
        out
    }
}

fn vertex_value(v: &Vertex) -> crate::cbor::Value {
    use crate::cbor::Value;
    match v {
        Vertex::Start => Value::Uint(0),
        Vertex::End => Value::Uint(1),
        Vertex::Atom((c, i)) => {
            Value::Array(vec![Value::Bytes(c.0.to_vec()), Value::Uint(*i as u64)])
        }
    }
}

fn vertex_from(v: &crate::cbor::Value) -> Result<Vertex, crate::objects::ObjectError> {
    use crate::cbor::Value;
    use crate::objects::ObjectError;
    match v {
        Value::Uint(0) => Ok(Vertex::Start),
        Value::Uint(1) => Ok(Vertex::End),
        Value::Array(a) if a.len() == 2 => Ok(Vertex::Atom((
            crate::objects::oref(&a[0], "vertex")?,
            crate::objects::u32_(&a[1], "vertex")?,
        ))),
        _ => Err(ObjectError::Schema(
            "vertex: expected 0, 1, or [hash, index]".into(),
        )),
    }
}

impl FileGraph {
    /// Serialize for a checkpoint: `{0: atoms [[hash, index, content|null, [deleters]]], 1: edges [[from, to]]}`.
    pub fn to_value(&self) -> crate::cbor::Value {
        use crate::cbor::Value;
        let mut atoms: Vec<(&AtomKey, &AtomInfo)> = self.atoms.iter().collect();
        atoms.sort_by_key(|(k, _)| **k);
        let mut edges: Vec<(Vertex, Vertex)> = self
            .succ
            .iter()
            .flat_map(|(a, bs)| bs.iter().map(move |b| (*a, *b)))
            .collect();
        edges.sort();
        Value::map([
            (
                0,
                Value::Array(
                    atoms
                        .into_iter()
                        .map(|((c, i), info)| {
                            Value::Array(vec![
                                Value::Bytes(c.0.to_vec()),
                                Value::Uint(*i as u64),
                                info.content
                                    .as_ref()
                                    .map(|b| Value::Bytes(b.bytes().to_vec()))
                                    .unwrap_or(Value::Null),
                                Value::Array(
                                    info.deleted_by
                                        .iter()
                                        .map(|d| Value::Bytes(d.0.to_vec()))
                                        .collect(),
                                ),
                            ])
                        })
                        .collect(),
                ),
            ),
            (
                1,
                Value::Array(
                    edges
                        .iter()
                        .map(|(a, b)| Value::Array(vec![vertex_value(a), vertex_value(b)]))
                        .collect(),
                ),
            ),
        ])
    }

    pub fn from_value(v: &crate::cbor::Value) -> Result<FileGraph, crate::objects::ObjectError> {
        use crate::objects::{array, bytes, field, map, oref, u32_, ObjectError};
        let m = map(v, "file graph")?;
        let mut g = FileGraph {
            atoms: HashMap::default(),
            succ: HashMap::default(),
            order: OrderSlot::default(),
        };
        let atoms = array(field(m, 0, "atoms")?, "atoms")?;
        // Every atom's line in one buffer.
        let mut texts: Vec<&[u8]> = Vec::new();
        for a in atoms {
            let e = array(a, "atom")?;
            if e.len() == 4 && !e[2].is_null() {
                texts.push(bytes(&e[2], "atom content")?);
            }
        }
        let all: Lines = texts.into_iter().collect();
        let mut next = 0u32;
        for a in atoms {
            let e = array(a, "atom")?;
            if e.len() != 4 {
                return Err(ObjectError::Schema("atom: expected 4 fields".into()));
            }
            let key = (oref(&e[0], "atom change")?, u32_(&e[1], "atom index")?);
            let content = if e[2].is_null() {
                None
            } else {
                next += 1;
                Some(LineRef::new(all.clone(), next - 1))
            };
            let deleted_by = array(&e[3], "deleters")?
                .iter()
                .map(|d| oref(d, "deleter"))
                .collect::<Result<BTreeSet<_>, _>>()?;
            g.atoms.insert(
                key,
                AtomInfo {
                    content,
                    deleted_by,
                },
            );
        }
        for e in array(field(m, 1, "edges")?, "edges")? {
            let pair = array(e, "edge")?;
            if pair.len() != 2 {
                return Err(ObjectError::Schema("edge: expected [from, to]".into()));
            }
            g.edge(vertex_from(&pair[0])?, vertex_from(&pair[1])?);
        }
        Ok(g)
    }
}

/// Split a plain run into `Lines` and `Zombie` segments around ghost atoms.
fn split_zombies(atoms: Vec<AtomKey>, ghosts: &HashSet<AtomKey>) -> Vec<Segment> {
    let mut out = Vec::new();
    let mut lines: Vec<AtomKey> = Vec::new();
    let mut i = 0;
    while i < atoms.len() {
        if !ghosts.contains(&atoms[i]) {
            lines.push(atoms[i]);
            i += 1;
            continue;
        }
        if !lines.is_empty() {
            out.push(Segment::Lines(std::mem::take(&mut lines)));
        }
        let mut deleted = Vec::new();
        while i < atoms.len() && ghosts.contains(&atoms[i]) {
            deleted.push(atoms[i]);
            i += 1;
        }
        let mut inserted = Vec::new();
        if i < atoms.len() {
            let ch = atoms[i].0;
            while i < atoms.len() && atoms[i].0 == ch && !ghosts.contains(&atoms[i]) {
                inserted.push(atoms[i]);
                i += 1;
            }
        }
        out.push(Segment::Zombie { deleted, inserted });
    }
    if !lines.is_empty() {
        out.push(Segment::Lines(lines));
    }
    out
}

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

    fn h(n: u8) -> ChangeHash {
        ObjectRef([n; 32])
    }
    fn lines(v: &[&str]) -> Lines {
        v.iter().map(|s| s.as_bytes()).collect()
    }
    fn text(g: &FileGraph, m: &Materialized) -> String {
        String::from_utf8(g.render(m, &|c| c.short(4))).unwrap()
    }

    struct Deps(HashMap<ChangeHash, Vec<ChangeHash>>);
    impl DepOracle for Deps {
        fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool {
            if a == b {
                return true;
            }
            let mut stack = vec![*a];
            let mut seen = HashSet::default();
            while let Some(x) = stack.pop() {
                if let Some(ds) = self.0.get(&x) {
                    for d in ds {
                        if d == b {
                            return true;
                        }
                        if seen.insert(*d) {
                            stack.push(*d);
                        }
                    }
                }
            }
            false
        }
    }

    /// 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());
    }

    /// Applied as the state applies a change's edits: the kept order is
    /// spliced by them.
    fn apply_spliced(
        g: &mut FileGraph,
        h: ChangeHash,
        inserts: &[(Vertex, Vertex, usize)],
        deleted: &[AtomKey],
    ) {
        let order = g.take_order();
        let mut runs = Vec::new();
        let mut next = 0u32;
        for (i, &(a, b, n)) in inserts.iter().enumerate() {
            let text: Vec<String> = (0..n).map(|j| format!("{i}.{j}\n")).collect();
            let text: Vec<&str> = text.iter().map(String::as_str).collect();
            g.insert(h, next, a, b, &lines(&text));
            runs.push((a, b, next, n as u32));
            next += n as u32;
        }
        for k in deleted {
            g.delete(
                h,
                &AtomRange {
                    change: k.0,
                    from: k.1,
                    to: k.1 + 1,
                },
            );
        }
        if let Some(o) = order {
            g.keep_spliced(o, h, &runs, deleted);
        }
    }

    /// Edits as a diff makes them from the order `l`: hunks with a kept
    /// line between them, each deleting some lines and inserting some.
    fn random_edits(
        l: &[AtomKey],
        rnd: &mut impl FnMut(usize) -> usize,
    ) -> (Vec<(Vertex, Vertex, usize)>, Vec<AtomKey>) {
        let (mut inserts, mut deleted) = (Vec::new(), Vec::new());
        let mut i = rnd(3);
        while i <= l.len() {
            let del = rnd(3).min(l.len() - i);
            let add = rnd(3);
            let after = if i == 0 {
                Vertex::Start
            } else {
                Vertex::Atom(l[i - 1])
            };
            let before = l.get(i).map(|k| Vertex::Atom(*k)).unwrap_or(Vertex::End);
            deleted.extend(&l[i..i + del]);
            if add > 0 {
                inserts.push((after, before, add));
            }
            i += del + 1 + rnd(6);
        }
        (inserts, deleted)
    }

    /// The kept order, spliced change by change, is what the general
    /// algorithm finds, through sequential edits and through concurrent
    /// ones that leave conflicts and ghosts (where it must stand aside).
    #[test]
    fn the_kept_order_follows_edits() {
        let hn = |i: usize| {
            let mut b = [0u8; 32];
            b[..2].copy_from_slice(&(i as u16).to_be_bytes());
            ObjectRef(b)
        };
        let mut seed = 7u64;
        let mut rnd = move |n: usize| {
            seed = seed
                .wrapping_mul(6364136223846793005)
                .wrapping_add(1442695040888963407);
            ((seed >> 33) as usize) % n.max(1)
        };
        let mut deps = Deps(HashMap::default());
        let mut g = FileGraph::new();
        let first: Vec<String> = (0..40).map(|i| format!("{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));
        let mut known: Vec<ChangeHash> = vec![hn(1)];
        let mut c = 2;
        let (mut spliced, mut conflicted) = (0, 0);
        for step in 0..400 {
            let l = g.materialize(&deps).live_atoms();
            // Now and then two changes from the same base, neither knowing
            // the other.
            let pair = step % 7 == 3;
            let base = known.clone();
            for _ in 0..if pair { 2 } else { 1 } {
                let h = hn(c);
                c += 1;
                let (inserts, deleted) = random_edits(&l, &mut rnd);
                deps.0.insert(h, base.clone());
                apply_spliced(&mut g, h, &inserts, &deleted);
                known.push(h);
                if g.order.get().is_some() {
                    spliced += 1;
                }
                let m = g.materialize(&deps);
                assert_eq!(m, g.materialize_general(&deps), "step {step}");
                if m.is_conflicted() {
                    conflicted += 1;
                }
            }
            // A change that knows everything settles any conflict by
            // rewriting the file.
            if g.materialize(&deps).is_conflicted() {
                let h = hn(c);
                c += 1;
                let all = g.materialize(&deps).live_atoms();
                deps.0.insert(h, known.clone());
                apply_spliced(&mut g, h, &[(Vertex::Start, Vertex::End, 5)], &all);
                known.push(h);
                assert_eq!(g.materialize(&deps), g.materialize_general(&deps));
            }
        }
        assert!(
            spliced > 100 && conflicted > 0,
            "{spliced} spliced, {conflicted} conflicted"
        );
    }

    /// A change applied before the one whose line it deletes (as a merge
    /// adds the other side, newest first): the line arrives dead, and the
    /// kept order must not take it in.
    #[test]
    fn the_kept_order_takes_no_line_that_arrives_deleted() {
        let mut deps = Deps(HashMap::default());
        let mut g = FileGraph::new();
        g.insert(
            h(1),
            0,
            Vertex::Start,
            Vertex::End,
            &lines(&["a\n", "b\n", "c\n"]),
        );
        // A deletion, so the order is kept rather than walked as a chain.
        apply_spliced(&mut g, h(2), &[], &[(h(1), 2)]);
        deps.0.insert(h(2), vec![h(1)]);
        let _ = g.materialize(&deps);
        assert!(g.order.get().is_some());
        let (a, b) = (Vertex::Atom((h(1), 0)), Vertex::Atom((h(1), 1)));
        // h(3) inserts x between a and b; h(4) deletes it. h(4) first.
        deps.0.insert(h(3), vec![h(2)]);
        deps.0.insert(h(4), vec![h(3)]);
        apply_spliced(&mut g, h(4), &[], &[(h(3), 0)]);
        apply_spliced(&mut g, h(3), &[(a, b, 1)], &[]);
        let m = g.materialize(&deps);
        assert_eq!(m, g.materialize_general(&deps));
        assert_eq!(text(&g, &m), "a\nb\n");
    }

    /// 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
        );
    }

    /// The chain shortcut agrees with the general algorithm wherever it
    /// applies, and stands aside wherever it does not.
    #[test]
    fn the_chain_shortcut_agrees_with_the_general_order() {
        let mut g = FileGraph::new();
        g.insert(
            h(1),
            0,
            Vertex::Start,
            Vertex::End,
            &lines(&["a\n", "b\n", "c\n"]),
        );
        assert!(g.as_chain().is_some());
        assert_eq!(g.materialize(&NoDeps), g.materialize_general(&NoDeps));
        // Appended after the last line: still a chain.
        g.insert(
            h(2),
            0,
            Vertex::Atom((h(1), 2)),
            Vertex::End,
            &lines(&["d\n"]),
        );
        assert!(g.as_chain().is_some());
        assert_eq!(g.materialize(&NoDeps), g.materialize_general(&NoDeps));
        // Inserted between two lines: not a chain (a has two successors).
        g.insert(
            h(4),
            0,
            Vertex::Atom((h(1), 0)),
            Vertex::Atom((h(1), 1)),
            &lines(&["x\n"]),
        );
        assert!(g.as_chain().is_none());
        assert_eq!(text(&g, &g.materialize(&NoDeps)), "a\nx\nb\nc\nd\n");
        // Two inserts at one anchor: a conflict, never a chain.
        let mut c = FileGraph::new();
        c.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n"]));
        c.insert(h(2), 0, Vertex::Start, Vertex::End, &lines(&["b\n"]));
        assert!(c.as_chain().is_none());
        assert!(c.materialize(&NoDeps).is_conflicted());
        // A deletion: not a chain.
        let mut d = FileGraph::new();
        d.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
        d.delete(
            h(3),
            &AtomRange {
                change: h(1),
                from: 0,
                to: 1,
            },
        );
        assert!(d.as_chain().is_none());
        assert_eq!(d.materialize(&NoDeps), d.materialize_general(&NoDeps));
        // Empty.
        let e = FileGraph::new();
        assert_eq!(e.materialize(&NoDeps), e.materialize_general(&NoDeps));
    }

    #[test]
    fn sequential_inserts_and_deletes() {
        let mut g = FileGraph::new();
        g.insert(
            h(1),
            0,
            Vertex::Start,
            Vertex::End,
            &lines(&["a\n", "b\n", "c\n"]),
        );
        let m = g.materialize(&NoDeps);
        assert!(!m.is_conflicted());
        assert_eq!(text(&g, &m), "a\nb\nc\n");

        // Change 2 depends on 1, inserts between b and c and deletes a.
        g.insert(
            h(2),
            0,
            Vertex::Atom((h(1), 1)),
            Vertex::Atom((h(1), 2)),
            &lines(&["x\n"]),
        );
        g.delete(
            h(2),
            &AtomRange {
                change: h(1),
                from: 0,
                to: 1,
            },
        );
        let deps = Deps([(h(2), vec![h(1)])].into_iter().collect());
        let m = g.materialize(&deps);
        assert!(!m.is_conflicted());
        assert_eq!(text(&g, &m), "b\nx\nc\n");
        assert_eq!(m.live_atoms(), vec![(h(1), 1), (h(2), 0), (h(1), 2)]);
    }

    #[test]
    fn concurrent_inserts_at_same_anchor_conflict() {
        let mut g = FileGraph::new();
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
        g.insert(
            h(2),
            0,
            Vertex::Atom((h(1), 0)),
            Vertex::Atom((h(1), 1)),
            &lines(&["from-2\n"]),
        );
        g.insert(
            h(3),
            0,
            Vertex::Atom((h(1), 0)),
            Vertex::Atom((h(1), 1)),
            &lines(&["from-3\n", "more-3\n"]),
        );
        let deps = Deps(
            [(h(2), vec![h(1)]), (h(3), vec![h(1)])]
                .into_iter()
                .collect(),
        );
        let m = g.materialize(&deps);
        assert!(m.is_conflicted());
        assert_eq!(m.conflict_count(), 1);
        assert_eq!(
            m.segments,
            vec![
                Segment::Lines(vec![(h(1), 0)]),
                Segment::Conflict(vec![vec![(h(2), 0)], vec![(h(3), 0), (h(3), 1)]]),
                Segment::Lines(vec![(h(1), 1)]),
            ]
        );
        let t = text(&g, &m);
        assert!(t.starts_with("a\n<<<<<<< oxy conflict 1 of 1, side 1 of 2: change 0202\nfrom-2\n======= oxy conflict 1 of 1, side 2 of 2: change 0303\nfrom-3\nmore-3\n>>>>>>> oxy conflict 1 of 1 end\nb\n"), "{t}");
    }

    #[test]
    fn concurrent_inserts_at_different_anchors_do_not_conflict() {
        let mut g = FileGraph::new();
        g.insert(
            h(1),
            0,
            Vertex::Start,
            Vertex::End,
            &lines(&["a\n", "b\n", "c\n"]),
        );
        g.insert(
            h(2),
            0,
            Vertex::Start,
            Vertex::Atom((h(1), 0)),
            &lines(&["top\n"]),
        );
        g.insert(
            h(3),
            0,
            Vertex::Atom((h(1), 2)),
            Vertex::End,
            &lines(&["bottom\n"]),
        );
        let deps = Deps(
            [(h(2), vec![h(1)]), (h(3), vec![h(1)])]
                .into_iter()
                .collect(),
        );
        let m = g.materialize(&deps);
        assert!(!m.is_conflicted());
        assert_eq!(text(&g, &m), "top\na\nb\nc\nbottom\n");
    }

    #[test]
    fn concurrent_deletes_of_the_same_line_agree() {
        let mut g = FileGraph::new();
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
        g.delete(
            h(2),
            &AtomRange {
                change: h(1),
                from: 0,
                to: 1,
            },
        );
        g.delete(
            h(3),
            &AtomRange {
                change: h(1),
                from: 0,
                to: 1,
            },
        );
        let deps = Deps(
            [(h(2), vec![h(1)]), (h(3), vec![h(1)])]
                .into_iter()
                .collect(),
        );
        let m = g.materialize(&deps);
        assert!(!m.is_conflicted());
        assert_eq!(text(&g, &m), "b\n");
    }

    #[test]
    fn delete_insert_conflict_is_a_zombie() {
        let mut g = FileGraph::new();
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
        // 2 deletes a; 3 (concurrent) inserts after a.
        g.delete(
            h(2),
            &AtomRange {
                change: h(1),
                from: 0,
                to: 1,
            },
        );
        g.insert(
            h(3),
            0,
            Vertex::Atom((h(1), 0)),
            Vertex::Atom((h(1), 1)),
            &lines(&["after-a\n"]),
        );
        let deps = Deps(
            [(h(2), vec![h(1)]), (h(3), vec![h(1)])]
                .into_iter()
                .collect(),
        );
        let m = g.materialize(&deps);
        assert!(m.is_conflicted());
        assert_eq!(
            m.segments,
            vec![
                Segment::Zombie {
                    deleted: vec![(h(1), 0)],
                    inserted: vec![(h(3), 0)]
                },
                Segment::Lines(vec![(h(1), 1)]),
            ]
        );
        let t = text(&g, &m);
        assert!(t.contains("-------\na\n======="), "{t}");
        assert!(t.contains("after-a\n>>>>>>>"), "{t}");

        // If the deleter saw the insert (depends on 3), there is no conflict.
        let deps = Deps(
            [(h(2), vec![h(1), h(3)]), (h(3), vec![h(1)])]
                .into_iter()
                .collect(),
        );
        let m = g.materialize(&deps);
        assert!(!m.is_conflicted());
        assert_eq!(text(&g, &m), "after-a\nb\n");
    }

    #[test]
    fn insert_after_a_line_deleted_by_a_dependency_is_not_a_conflict() {
        // 1 inserts a,b; 2 deletes b (depends on 1); 3 depends on 2 yet anchors
        // after the dead b (a rewritten change may do this): no conflict.
        let mut g = FileGraph::new();
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
        g.delete(
            h(2),
            &AtomRange {
                change: h(1),
                from: 1,
                to: 2,
            },
        );
        g.insert(
            h(3),
            0,
            Vertex::Atom((h(1), 1)),
            Vertex::End,
            &lines(&["c\n"]),
        );
        let deps = Deps(
            [(h(2), vec![h(1)]), (h(3), vec![h(2)])]
                .into_iter()
                .collect(),
        );
        let m = g.materialize(&deps);
        assert!(!m.is_conflicted(), "{:?}", m.segments);
        assert_eq!(text(&g, &m), "a\nc\n");
        // A change that deletes a line it introduced itself, with a dependent
        // anchoring after it, is likewise fine.
        let mut g = FileGraph::new();
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["x\n"]));
        g.delete(
            h(1),
            &AtomRange {
                change: h(1),
                from: 0,
                to: 1,
            },
        );
        g.insert(
            h(2),
            0,
            Vertex::Atom((h(1), 0)),
            Vertex::End,
            &lines(&["y\n"]),
        );
        let deps = Deps([(h(2), vec![h(1)])].into_iter().collect());
        let m = g.materialize(&deps);
        assert!(!m.is_conflicted());
        assert_eq!(text(&g, &m), "y\n");
    }

    #[test]
    fn resolution_collapses_a_conflict() {
        let mut g = FileGraph::new();
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n"]));
        g.insert(
            h(2),
            0,
            Vertex::Start,
            Vertex::Atom((h(1), 0)),
            &lines(&["x\n"]),
        );
        g.insert(
            h(3),
            0,
            Vertex::Start,
            Vertex::Atom((h(1), 0)),
            &lines(&["y\n"]),
        );
        let mut deps: HashMap<_, _> = [(h(2), vec![h(1)]), (h(3), vec![h(1)])]
            .into_iter()
            .collect();
        assert!(g.materialize(&Deps(deps.clone())).is_conflicted());
        // Resolution keeps y, drops x.
        g.delete(
            h(4),
            &AtomRange {
                change: h(2),
                from: 0,
                to: 1,
            },
        );
        deps.insert(h(4), vec![h(2), h(3)]);
        let m = g.materialize(&Deps(deps));
        assert!(!m.is_conflicted());
        assert_eq!(text(&g, &m), "y\na\n");
    }

    #[test]
    fn empty_and_unterminated_files() {
        let g = FileGraph::new();
        let m = g.materialize(&NoDeps);
        assert_eq!(m.segments, vec![]);
        assert_eq!(text(&g, &m), "");
        let mut g = FileGraph::new();
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["no newline"]));
        assert_eq!(text(&g, &g.materialize(&NoDeps)), "no newline");
    }

    #[test]
    fn serialization_round_trip() {
        let mut g = FileGraph::new();
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
        g.insert(
            h(2),
            0,
            Vertex::Atom((h(1), 0)),
            Vertex::Atom((h(1), 1)),
            &lines(&["x\n"]),
        );
        g.delete(
            h(3),
            &AtomRange {
                change: h(1),
                from: 1,
                to: 2,
            },
        );
        let v = g.to_value();
        let bytes = crate::cbor::encode(&v);
        let back = FileGraph::from_value(&crate::cbor::decode(&bytes).unwrap()).unwrap();
        let deps = Deps(
            [(h(2), vec![h(1)]), (h(3), vec![h(1)])]
                .into_iter()
                .collect(),
        );
        assert_eq!(back.materialize(&deps), g.materialize(&deps));
        assert_eq!(text(&back, &back.materialize(&deps)), "a\nx\n");
        assert_eq!(
            crate::cbor::encode(&back.to_value()),
            bytes,
            "deterministic"
        );
    }

    /// Spec §7.3: the graph is a function of the set of changes, not their order.
    #[test]
    fn application_order_is_irrelevant() {
        use rand::seq::SliceRandom;
        type Op = (
            ChangeHash,
            Vec<(u32, Vertex, Vertex, Lines)>,
            Vec<AtomRange>,
        );
        let ops: Vec<Op> = vec![
            (
                h(1),
                vec![(0, Vertex::Start, Vertex::End, lines(&["a\n", "b\n", "c\n"]))],
                vec![],
            ),
            (
                h(2),
                vec![(
                    0,
                    Vertex::Atom((h(1), 0)),
                    Vertex::Atom((h(1), 1)),
                    lines(&["p\n"]),
                )],
                vec![],
            ),
            (
                h(3),
                vec![(
                    0,
                    Vertex::Atom((h(1), 0)),
                    Vertex::Atom((h(1), 1)),
                    lines(&["q\n", "r\n"]),
                )],
                vec![AtomRange {
                    change: h(1),
                    from: 2,
                    to: 3,
                }],
            ),
            (
                h(4),
                vec![(
                    0,
                    Vertex::Atom((h(3), 1)),
                    Vertex::Atom((h(1), 1)),
                    lines(&["s\n"]),
                )],
                vec![AtomRange {
                    change: h(1),
                    from: 1,
                    to: 2,
                }],
            ),
            (
                h(5),
                vec![(0, Vertex::Atom((h(1), 2)), Vertex::End, lines(&["z\n"]))],
                vec![],
            ),
        ];
        let deps = Deps(
            [
                (h(2), vec![h(1)]),
                (h(3), vec![h(1)]),
                (h(4), vec![h(3), h(1)]),
                (h(5), vec![h(1)]),
            ]
            .into_iter()
            .collect(),
        );
        let build = |order: &[usize]| {
            let mut g = FileGraph::new();
            for &i in order {
                let (c, ins, dels) = &ops[i];
                for (idx, a, b, l) in ins {
                    g.insert(*c, *idx, *a, *b, l);
                }
                for d in dels {
                    g.delete(*c, d);
                }
            }
            let m = g.materialize(&deps);
            (m.clone(), text(&g, &m))
        };
        let reference = build(&[0, 1, 2, 3, 4]);
        assert!(reference.0.is_conflicted());
        let mut rng = rand::thread_rng();
        let mut order: Vec<usize> = (0..ops.len()).collect();
        for _ in 0..50 {
            order.shuffle(&mut rng);
            assert_eq!(build(&order), reference, "order {order:?}");
        }
    }
}
`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet
Keyboard
