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

# c3069537d7c5 oxygen / crates / oxy-core / src / graph.rs

22.8 KiB · Rust · last changed Import the Oxygen specification and the first Rust implementation (root change) 1 month 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::hash::ChangeHash;
use crate::objects::AtomRange;
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};

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

/// 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.
    content: Option<Vec<u8>>,
    deleted_by: BTreeSet<ChangeHash>,
}

#[derive(Clone, Debug)]
pub struct FileGraph {
    atoms: HashMap<AtomKey, AtomInfo>,
    succ: HashMap<Vertex, BTreeSet<Vertex>>,
    pred: HashMap<Vertex, BTreeSet<Vertex>>,
}

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::new(), succ: HashMap::new(), pred: HashMap::new() };
        g.edge(Vertex::Start, Vertex::End);
        g
    }

    fn edge(&mut self, a: Vertex, b: Vertex) {
        self.succ.entry(a).or_default().insert(b);
        self.pred.entry(b).or_default().insert(a);
        self.succ.entry(b).or_default();
        self.pred.entry(a).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: &[Vec<u8>]) {
        let mut prev = after;
        for (i, line) in lines.iter().enumerate() {
            let key = (change, first_index + i as u32);
            self.atoms.entry(key).or_default().content = Some(line.clone());
            let v = Vertex::Atom(key);
            self.edge(prev, v);
            prev = v;
        }
        self.edge(prev, before);
    }

    /// Apply a `Delete` of `range` by change `by`.
    pub fn delete(&mut self, by: ChangeHash, range: &AtomRange) {
        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_deref())
    }

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

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

    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 no deleter depends on (spec §9.1, delete/insert).
        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)),
                _ => 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 mut out = BTreeSet::new();
        let mut stack: Vec<Vertex> = self.succ.get(&v).map(|s| s.iter().copied().collect()).unwrap_or_default();
        let mut seen = HashSet::new();
        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
    }

    /// Order the live atoms and locate conflicts.
    pub fn materialize(&self, deps: &dyn DepOracle) -> Materialized {
        // 1. Vertices that survive contraction: live atoms, ghosts, Start, End.
        let mut kept: HashSet<Vertex> = HashSet::new();
        let mut ghosts: HashSet<AtomKey> = HashSet::new();
        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::new();
        let mut rsucc: HashMap<Vertex, BTreeSet<Vertex>> = HashMap::new();
        let mut indeg: HashMap<Vertex, usize> = HashMap::new();
        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::new();
        let mut joins: HashSet<Vertex> = HashSet::new();
        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
    }
}

/// 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]) -> Vec<Vec<u8>> {
        v.iter().map(|s| s.as_bytes().to_vec()).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::new();
            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
        }
    }

    #[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 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");
    }

    /// 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, Vec<Vec<u8>>)>, 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

ff0af1ee unknown 1 month ago	1	//! The per-file atom graph (spec §7.3), its materialization, and text conflict
	2	//! detection (spec §9.1, §9.5).
	3	//!
	4	//! The graph is a pure function of the set of changes applied to it: inserts
	5	//! add vertices and edges, deletes set a flag, and nothing is ever removed.
	6
	7	use crate::hash::ChangeHash;
	8	use crate::objects::AtomRange;
	9	use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
	10
	11	/// `(introducing change, index within that change for this node)`.
	12	pub type AtomKey = (ChangeHash, u32);
	13
	14	#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
	15	pub enum Vertex {
	16	Start,
	17	Atom(AtomKey),
	18	End,
	19	}
	20
	21	/// Transitive dependency test between changes; `depends_on(a, a)` is true.
	22	pub trait DepOracle {
	23	fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool;
	24	}
	25
	26	/// No change depends on any other: every pair commutes.
	27	pub struct NoDeps;
	28	impl DepOracle for NoDeps {
	29	fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool {
	30	a == b
	31	}
	32	}
	33
	34	#[derive(Default, Clone, Debug)]
	35	struct AtomInfo {
	36	/// `None` until the introducing change has been applied.
	37	content: Option<Vec<u8>>,
	38	deleted_by: BTreeSet<ChangeHash>,
	39	}
	40
	41	#[derive(Clone, Debug)]
	42	pub struct FileGraph {
	43	atoms: HashMap<AtomKey, AtomInfo>,
	44	succ: HashMap<Vertex, BTreeSet<Vertex>>,
	45	pred: HashMap<Vertex, BTreeSet<Vertex>>,
	46	}
	47
	48	impl Default for FileGraph {
	49	fn default() -> Self {
	50	Self::new()
	51	}
	52	}
	53
	54	/// One piece of a materialized file.
	55	#[derive(Clone, Debug, PartialEq, Eq)]
	56	pub enum Segment {
	57	Lines(Vec<AtomKey>),
	58	/// Order conflict: alternatives that cannot be ordered against each other.
	59	Conflict(Vec<Vec<AtomKey>>),
	60	/// Delete/insert conflict: `inserted` was anchored to `deleted` by a change
	61	/// that commutes with the deletion.
	62	Zombie { deleted: Vec<AtomKey>, inserted: Vec<AtomKey> },
	63	}
	64
65	#[derive(Clone, Debug, PartialEq, Eq, Default)]
66	pub struct Materialized {
67	pub segments: Vec<Segment>,
68	}
69
70	impl Materialized {
71	pub fn is_conflicted(&self) -> bool {
72	self.segments.iter().any(\|s\| !matches!(s, Segment::Lines(_)))
73	}
74	pub fn conflict_count(&self) -> usize {
75	self.segments.iter().filter(\|s\| !matches!(s, Segment::Lines(_))).count()
76	}
77	/// Every live atom in materialized order, conflict sides concatenated.
78	pub fn live_atoms(&self) -> Vec<AtomKey> {
79	let mut out = Vec::new();
80	for s in &self.segments {
81	match s {
82	Segment::Lines(a) => out.extend(a),
83	Segment::Conflict(sides) => sides.iter().for_each(\|x\| out.extend(x)),
84	Segment::Zombie { inserted, .. } => out.extend(inserted),
85	}
86	}
87	out
88	}
89	}
90
91	impl FileGraph {
92	pub fn new() -> Self {
93	let mut g = FileGraph { atoms: HashMap::new(), succ: HashMap::new(), pred: HashMap::new() };
94	g.edge(Vertex::Start, Vertex::End);
95	g
96	}
97
98	fn edge(&mut self, a: Vertex, b: Vertex) {
99	self.succ.entry(a).or_default().insert(b);
100	self.pred.entry(b).or_default().insert(a);
101	self.succ.entry(b).or_default();
102	self.pred.entry(a).or_default();
103	}
104
105	/// Apply an `Insert` by `change` whose first new atom has index `first_index`.
106	pub fn insert(&mut self, change: ChangeHash, first_index: u32, after: Vertex, before: Vertex, lines: &[Vec<u8>]) {
107	let mut prev = after;
108	for (i, line) in lines.iter().enumerate() {
109	let key = (change, first_index + i as u32);
110	self.atoms.entry(key).or_default().content = Some(line.clone());
111	let v = Vertex::Atom(key);
112	self.edge(prev, v);
113	prev = v;
114	}
115	self.edge(prev, before);
116	}
117
118	/// Apply a `Delete` of `range` by change `by`.
119	pub fn delete(&mut self, by: ChangeHash, range: &AtomRange) {
120	for i in range.from..range.to {
121	self.atoms.entry((range.change, i)).or_default().deleted_by.insert(by);
122	}
123	}
124
125	pub fn is_live(&self, k: &AtomKey) -> bool {
126	self.atoms.get(k).is_some_and(\|a\| a.content.is_some() && a.deleted_by.is_empty())
127	}
128
129	pub fn content(&self, k: &AtomKey) -> Option<&[u8]> {
130	self.atoms.get(k).and_then(\|a\| a.content.as_deref())
131	}
132
133	pub fn deleters(&self, k: &AtomKey) -> impl Iterator<Item = &ChangeHash> {
134	self.atoms.get(k).into_iter().flat_map(\|a\| a.deleted_by.iter())
135	}
136
137	/// Number of atoms introduced by `change` in this graph (for index bookkeeping).
138	pub fn atom_count(&self) -> usize {
139	self.atoms.len()
140	}
141
142	fn is_ghost(&self, k: &AtomKey, info: &AtomInfo, deps: &dyn DepOracle) -> bool {
143	// A deleted atom is a ghost when a live direct successor was inserted by
144	// a change that no deleter depends on (spec §9.1, delete/insert).
145	self.succ.get(&Vertex::Atom(*k)).is_some_and(\|ss\| {
146	ss.iter().any(\|s\| match s {
147	Vertex::Atom(y) if self.is_live(y) => !info.deleted_by.iter().any(\|d\| deps.depends_on(d, &y.0)),
148	_ => false,
149	})
150	})
151	}
152
153	/// Successors of `v` in the graph with non-kept vertices contracted away.
154	fn reduced_succ(&self, v: Vertex, kept: &HashSet<Vertex>, memo: &mut HashMap<Vertex, BTreeSet<Vertex>>) -> BTreeSet<Vertex> {
155	let mut out = BTreeSet::new();
156	let mut stack: Vec<Vertex> = self.succ.get(&v).map(\|s\| s.iter().copied().collect()).unwrap_or_default();
157	let mut seen = HashSet::new();
158	while let Some(s) = stack.pop() {
159	if kept.contains(&s) {
160	out.insert(s);
161	} else if seen.insert(s) {
162	if let Some(m) = memo.get(&s) {
163	out.extend(m.iter().copied());
164	} else if let Some(next) = self.succ.get(&s) {
165	stack.extend(next.iter().copied());
166	}
167	}
168	}
169	out
170	}
171
172	/// Order the live atoms and locate conflicts.
173	pub fn materialize(&self, deps: &dyn DepOracle) -> Materialized {
174	// 1. Vertices that survive contraction: live atoms, ghosts, Start, End.
175	let mut kept: HashSet<Vertex> = HashSet::new();
176	let mut ghosts: HashSet<AtomKey> = HashSet::new();
177	kept.insert(Vertex::Start);
178	kept.insert(Vertex::End);
179	for (k, info) in &self.atoms {
180	if info.content.is_none() {
181	continue;
182	}
183	if info.deleted_by.is_empty() {
184	kept.insert(Vertex::Atom(*k));
185	} else if self.is_ghost(k, info, deps) {
186	kept.insert(Vertex::Atom(*k));
187	ghosts.insert(*k);
188	}
189	}
190
191	// 2. Reduced graph over kept vertices.
192	let mut memo = HashMap::new();
193	let mut rsucc: HashMap<Vertex, BTreeSet<Vertex>> = HashMap::new();
194	let mut indeg: HashMap<Vertex, usize> = HashMap::new();
195	for &u in &kept {
196	indeg.entry(u).or_insert(0);
197	let rs = self.reduced_succ(u, &kept, &mut memo);
198	for &w in &rs {
199	*indeg.entry(w).or_insert(0) += 1;
200	}
201	rsucc.insert(u, rs);
202	}
203
204	// 3. Kahn's algorithm with side labelling for conflict regions.
205	let mut ready: BTreeSet<Vertex> = indeg.iter().filter(\|(_, &d)\| d == 0).map(\|(v, _)\| *v).collect();
206	let mut side: HashMap<Vertex, u32> = HashMap::new();
207	let mut joins: HashSet<Vertex> = HashSet::new();
208	let mut next_side = 0u32;
209	let mut plain: Vec<Vertex> = Vec::new();
210	let mut conflict: Option<BTreeMap<u32, Vec<Vertex>>> = None;
211	let mut segments: Vec<Segment> = Vec::new();
212
213	let flush_plain = \|plain: &mut Vec<Vertex>, segments: &mut Vec<Segment>\| {
214	let atoms: Vec<AtomKey> = plain.iter().filter_map(\|v\| if let Vertex::Atom(k) = v { Some(*k) } else { None }).collect();
215	plain.clear();
216	if !atoms.is_empty() {
217	segments.extend(split_zombies(atoms, &ghosts));
218	}
219	};
220	let finish_conflict = \|c: BTreeMap<u32, Vec<Vertex>>, segments: &mut Vec<Segment>\| {
221	let sides: Vec<Vec<AtomKey>> = c
222	.into_values()
223	.map(\|vs\| {
224	vs.into_iter()
225	.filter_map(\|v\| match v {
226	Vertex::Atom(k) if !ghosts.contains(&k) => Some(k),
227	_ => None,
228	})
229	.collect::<Vec<_>>()
230	})
231	.filter(\|s\| !s.is_empty())
232	.collect();
233	match sides.len() {
234	0 => {}
235	1 => segments.push(Segment::Lines(sides.into_iter().next().unwrap())),
236	_ => segments.push(Segment::Conflict(sides)),
237	}
238	};
239
240	while !ready.is_empty() {
241	if ready.len() >= 2 {
242	if conflict.is_none() {
243	flush_plain(&mut plain, &mut segments);
244	conflict = Some(BTreeMap::new());
245	}
246	for r in &ready {
247	if !side.contains_key(r) {
248	side.insert(*r, next_side);
249	next_side += 1;
250	}
251	}
252	}
253	let v = ready.pop_first().unwrap();
254	let my_side = side.get(&v).copied();
255	match (&mut conflict, my_side) {
256	(Some(c), Some(s)) => c.entry(s).or_default().push(v),
257	(Some(_), None) => {
258	let c = conflict.take().unwrap();
259	finish_conflict(c, &mut segments);
260	plain.push(v);
261	}
262	(None, _) => plain.push(v),
263	}
264	for &w in &rsucc[&v] {
265	let d = indeg.get_mut(&w).unwrap();
266	*d -= 1;
267	if conflict.is_some() && !joins.contains(&w) {
268	match (my_side, side.get(&w).copied()) {
269	(Some(s), None) => {
270	side.insert(w, s);
271	}
272	(Some(s), Some(t)) if s != t => {
273	side.remove(&w);
274	joins.insert(w);
275	}
276	(None, Some(_)) => {
277	side.remove(&w);
278	joins.insert(w);
279	}
280	_ => {}
281	}
282	}
283	if *d == 0 {
284	ready.insert(w);
285	}
286	}
287	}
288	if let Some(c) = conflict.take() {
289	finish_conflict(c, &mut segments);
290	}
291	flush_plain(&mut plain, &mut segments);
292	Materialized { segments }
293	}
294
295	/// Render a materialization to bytes with conflict markers (spec §9.5).
296	/// `label` gives the short description of a change for marker headers.
297	pub fn render(&self, m: &Materialized, label: &dyn Fn(&ChangeHash) -> String) -> Vec<u8> {
298	let total = m.conflict_count();
299	let mut n = 0;
300	let mut out: Vec<u8> = Vec::new();
301	let push_atoms = \|out: &mut Vec<u8>, atoms: &[AtomKey]\| {
302	for a in atoms {
303	if let Some(c) = self.content(a) {
304	out.extend_from_slice(c);
305	}
306	}
307	};
308	let newline_if_needed = \|out: &mut Vec<u8>\| {
309	if !out.is_empty() && *out.last().unwrap() != b'\n' {
310	out.push(b'\n');
311	}
312	};
313	for seg in &m.segments {
314	match seg {
315	Segment::Lines(a) => push_atoms(&mut out, a),
316	Segment::Conflict(sides) => {
317	n += 1;
318	let k = sides.len();
319	for (i, s) in sides.iter().enumerate() {
320	newline_if_needed(&mut out);
321	let who = s.first().map(\|a\| label(&a.0)).unwrap_or_default();
322	let marker = if i == 0 { "<<<<<<<" } else { "=======" };
323	out.extend_from_slice(
324	format!("{marker} oxy conflict {n} of {total}, side {} of {k}: change {who}\n", i + 1).as_bytes(),
325	);
326	push_atoms(&mut out, s);
327	}
328	newline_if_needed(&mut out);
329	out.extend_from_slice(format!(">>>>>>> oxy conflict {n} of {total} end\n").as_bytes());
330	}
331	Segment::Zombie { deleted, inserted } => {
332	n += 1;
333	newline_if_needed(&mut out);
334	let deleter = deleted
335	.first()
336	.and_then(\|a\| self.deleters(a).next().copied())
337	.map(\|d\| label(&d))
338	.unwrap_or_default();
339	let inserter = inserted.first().map(\|a\| label(&a.0)).unwrap_or_default();
340	out.extend_from_slice(
341	format!("<<<<<<< oxy conflict {n} of {total}, side 1 of 2: deleted by change {deleter}\n-------\n").as_bytes(),
342	);
343	push_atoms(&mut out, deleted);
344	newline_if_needed(&mut out);
345	out.extend_from_slice(format!("======= oxy conflict {n} of {total}, side 2 of 2: change {inserter}\n").as_bytes());
346	push_atoms(&mut out, inserted);
347	newline_if_needed(&mut out);
348	out.extend_from_slice(format!(">>>>>>> oxy conflict {n} of {total} end\n").as_bytes());
349	}
350	}
351	}
352	out
353	}
354	}
355
356	/// Split a plain run into `Lines` and `Zombie` segments around ghost atoms.
357	fn split_zombies(atoms: Vec<AtomKey>, ghosts: &HashSet<AtomKey>) -> Vec<Segment> {
358	let mut out = Vec::new();
359	let mut lines: Vec<AtomKey> = Vec::new();
360	let mut i = 0;
361	while i < atoms.len() {
362	if !ghosts.contains(&atoms[i]) {
363	lines.push(atoms[i]);
364	i += 1;
365	continue;
366	}
367	if !lines.is_empty() {
368	out.push(Segment::Lines(std::mem::take(&mut lines)));
369	}
370	let mut deleted = Vec::new();
371	while i < atoms.len() && ghosts.contains(&atoms[i]) {
372	deleted.push(atoms[i]);
373	i += 1;
374	}
375	let mut inserted = Vec::new();
376	if i < atoms.len() {
377	let ch = atoms[i].0;
378	while i < atoms.len() && atoms[i].0 == ch && !ghosts.contains(&atoms[i]) {
379	inserted.push(atoms[i]);
380	i += 1;
381	}
382	}
383	out.push(Segment::Zombie { deleted, inserted });
384	}
385	if !lines.is_empty() {
386	out.push(Segment::Lines(lines));
387	}
388	out
389	}
390
391	#[cfg(test)]
392	mod tests {
393	use super::*;
394	use crate::hash::ObjectRef;
395
396	fn h(n: u8) -> ChangeHash {
397	ObjectRef([n; 32])
398	}
399	fn lines(v: &[&str]) -> Vec<Vec<u8>> {
400	v.iter().map(\|s\| s.as_bytes().to_vec()).collect()
401	}
402	fn text(g: &FileGraph, m: &Materialized) -> String {
403	String::from_utf8(g.render(m, &\|c\| c.short(4))).unwrap()
404	}
405
406	struct Deps(HashMap<ChangeHash, Vec<ChangeHash>>);
407	impl DepOracle for Deps {
408	fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool {
409	if a == b {
410	return true;
411	}
412	let mut stack = vec![*a];
413	let mut seen = HashSet::new();
414	while let Some(x) = stack.pop() {
415	if let Some(ds) = self.0.get(&x) {
416	for d in ds {
417	if d == b {
418	return true;
419	}
420	if seen.insert(*d) {
421	stack.push(*d);
422	}
423	}
424	}
425	}
426	false
427	}
428	}
429
430	#[test]
431	fn sequential_inserts_and_deletes() {
432	let mut g = FileGraph::new();
433	g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n", "c\n"]));
434	let m = g.materialize(&NoDeps);
435	assert!(!m.is_conflicted());
436	assert_eq!(text(&g, &m), "a\nb\nc\n");
437
438	// Change 2 depends on 1, inserts between b and c and deletes a.
439	g.insert(h(2), 0, Vertex::Atom((h(1), 1)), Vertex::Atom((h(1), 2)), &lines(&["x\n"]));
440	g.delete(h(2), &AtomRange { change: h(1), from: 0, to: 1 });
441	let deps = Deps([(h(2), vec![h(1)])].into_iter().collect());
442	let m = g.materialize(&deps);
443	assert!(!m.is_conflicted());
444	assert_eq!(text(&g, &m), "b\nx\nc\n");
445	assert_eq!(m.live_atoms(), vec![(h(1), 1), (h(2), 0), (h(1), 2)]);
446	}
447
448	#[test]
449	fn concurrent_inserts_at_same_anchor_conflict() {
450	let mut g = FileGraph::new();
451	g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
452	g.insert(h(2), 0, Vertex::Atom((h(1), 0)), Vertex::Atom((h(1), 1)), &lines(&["from-2\n"]));
453	g.insert(h(3), 0, Vertex::Atom((h(1), 0)), Vertex::Atom((h(1), 1)), &lines(&["from-3\n", "more-3\n"]));
454	let deps = Deps([(h(2), vec![h(1)]), (h(3), vec![h(1)])].into_iter().collect());
455	let m = g.materialize(&deps);
456	assert!(m.is_conflicted());
457	assert_eq!(m.conflict_count(), 1);
458	assert_eq!(
459	m.segments,
460	vec![
461	Segment::Lines(vec![(h(1), 0)]),
462	Segment::Conflict(vec![vec![(h(2), 0)], vec![(h(3), 0), (h(3), 1)]]),
463	Segment::Lines(vec![(h(1), 1)]),
464	]
465	);
466	let t = text(&g, &m);
467	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}");
468	}
469
470	#[test]
471	fn concurrent_inserts_at_different_anchors_do_not_conflict() {
472	let mut g = FileGraph::new();
473	g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n", "c\n"]));
474	g.insert(h(2), 0, Vertex::Start, Vertex::Atom((h(1), 0)), &lines(&["top\n"]));
475	g.insert(h(3), 0, Vertex::Atom((h(1), 2)), Vertex::End, &lines(&["bottom\n"]));
476	let deps = Deps([(h(2), vec![h(1)]), (h(3), vec![h(1)])].into_iter().collect());
477	let m = g.materialize(&deps);
478	assert!(!m.is_conflicted());
479	assert_eq!(text(&g, &m), "top\na\nb\nc\nbottom\n");
480	}
481
482	#[test]
483	fn concurrent_deletes_of_the_same_line_agree() {
484	let mut g = FileGraph::new();
485	g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
486	g.delete(h(2), &AtomRange { change: h(1), from: 0, to: 1 });
487	g.delete(h(3), &AtomRange { change: h(1), from: 0, to: 1 });
488	let deps = Deps([(h(2), vec![h(1)]), (h(3), vec![h(1)])].into_iter().collect());
489	let m = g.materialize(&deps);
490	assert!(!m.is_conflicted());
491	assert_eq!(text(&g, &m), "b\n");
492	}
493
494	#[test]
495	fn delete_insert_conflict_is_a_zombie() {
496	let mut g = FileGraph::new();
497	g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
498	// 2 deletes a; 3 (concurrent) inserts after a.
499	g.delete(h(2), &AtomRange { change: h(1), from: 0, to: 1 });
500	g.insert(h(3), 0, Vertex::Atom((h(1), 0)), Vertex::Atom((h(1), 1)), &lines(&["after-a\n"]));
501	let deps = Deps([(h(2), vec![h(1)]), (h(3), vec![h(1)])].into_iter().collect());
502	let m = g.materialize(&deps);
503	assert!(m.is_conflicted());
504	assert_eq!(
505	m.segments,
506	vec![
507	Segment::Zombie { deleted: vec![(h(1), 0)], inserted: vec![(h(3), 0)] },
508	Segment::Lines(vec![(h(1), 1)]),
509	]
510	);
511	let t = text(&g, &m);
512	assert!(t.contains("-------\na\n======="), "{t}");
513	assert!(t.contains("after-a\n>>>>>>>"), "{t}");
514
515	// If the deleter saw the insert (depends on 3), there is no conflict.
516	let deps = Deps([(h(2), vec![h(1), h(3)]), (h(3), vec![h(1)])].into_iter().collect());
517	let m = g.materialize(&deps);
518	assert!(!m.is_conflicted());
519	assert_eq!(text(&g, &m), "after-a\nb\n");
520	}
521
522	#[test]
523	fn resolution_collapses_a_conflict() {
524	let mut g = FileGraph::new();
525	g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n"]));
526	g.insert(h(2), 0, Vertex::Start, Vertex::Atom((h(1), 0)), &lines(&["x\n"]));
527	g.insert(h(3), 0, Vertex::Start, Vertex::Atom((h(1), 0)), &lines(&["y\n"]));
528	let mut deps: HashMap<_, _> = [(h(2), vec![h(1)]), (h(3), vec![h(1)])].into_iter().collect();
529	assert!(g.materialize(&Deps(deps.clone())).is_conflicted());
530	// Resolution keeps y, drops x.
531	g.delete(h(4), &AtomRange { change: h(2), from: 0, to: 1 });
532	deps.insert(h(4), vec![h(2), h(3)]);
533	let m = g.materialize(&Deps(deps));
534	assert!(!m.is_conflicted());
535	assert_eq!(text(&g, &m), "y\na\n");
536	}
537
538	#[test]
539	fn empty_and_unterminated_files() {
540	let g = FileGraph::new();
541	let m = g.materialize(&NoDeps);
542	assert_eq!(m.segments, vec![]);
543	assert_eq!(text(&g, &m), "");
544	let mut g = FileGraph::new();
545	g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["no newline"]));
546	assert_eq!(text(&g, &g.materialize(&NoDeps)), "no newline");
547	}
548
549	/// Spec §7.3: the graph is a function of the set of changes, not their order.
550	#[test]
551	fn application_order_is_irrelevant() {
552	use rand::seq::SliceRandom;
553	type Op = (ChangeHash, Vec<(u32, Vertex, Vertex, Vec<Vec<u8>>)>, Vec<AtomRange>);
554	let ops: Vec<Op> = vec![
555	(h(1), vec![(0, Vertex::Start, Vertex::End, lines(&["a\n", "b\n", "c\n"]))], vec![]),
556	(h(2), vec![(0, Vertex::Atom((h(1), 0)), Vertex::Atom((h(1), 1)), lines(&["p\n"]))], vec![]),
557	(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 }]),
558	(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 }]),
559	(h(5), vec![(0, Vertex::Atom((h(1), 2)), Vertex::End, lines(&["z\n"]))], vec![]),
560	];
561	let deps = Deps(
562	[(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(),
563	);
564	let build = \|order: &[usize]\| {
565	let mut g = FileGraph::new();
566	for &i in order {
567	let (c, ins, dels) = &ops[i];
568	for (idx, a, b, l) in ins {
569	g.insert(c, idx, a, b, l);
570	}
571	for d in dels {
572	g.delete(*c, d);
573	}
574	}
575	let m = g.materialize(&deps);
576	(m.clone(), text(&g, &m))
577	};
578	let reference = build(&[0, 1, 2, 3, 4]);
579	assert!(reference.0.is_conflicted());
580	let mut rng = rand::thread_rng();
581	let mut order: Vec<usize> = (0..ops.len()).collect();
582	for _ in 0..50 {
583	order.shuffle(&mut rng);
584	assert_eq!(build(&order), reference, "order {order:?}");
585	}
586	}
587	}

Keyboard