//! 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; } /// 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, deleted_by: BTreeSet, } #[derive(Clone, Debug)] pub struct FileGraph { atoms: HashMap, /// Every vertex, with its direct successors. succ: HashMap, /// 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, /// 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, 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>>); impl OrderSlot { fn get(&self) -> Option> { self.0.lock().unwrap_or_else(|e| e.into_inner()).clone() } fn set(&self, o: Option>) { *self.0.lock().unwrap_or_else(|e| e.into_inner()) = o; } fn take(&mut self) -> Option> { 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) -> 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> { let mut want: HashSet = 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 = 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| { 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), } 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), /// Order conflict: alternatives that cannot be ordered against each other. Conflict(Vec>), /// Delete/insert conflict: `inserted` was anchored to `deleted` by a change /// that commutes with the deletion. Zombie { deleted: Vec, inserted: Vec, }, } #[derive(Clone, Debug, PartialEq, Eq, Default)] pub struct Materialized { pub segments: Vec, } 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 { 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 { 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() } /// 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 { let (from, to) = (Vertex::Atom(*first), Vertex::Atom(*last)); let mut ahead: HashSet = 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> = 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 = 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 = 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 { 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 { 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, memo: &mut HashMap>, ) -> BTreeSet { 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 = 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> { 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 lines = |order: Vec| Materialized { segments: if order.is_empty() { vec![] } else { vec![Segment::Lines(order)] }, }; use std::sync::atomic::Ordering::Relaxed; 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); 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() { return lines(order); } if let Some(order) = self.as_order(deps) { self.order .set(Some(std::sync::Arc::new(Order::known(order.clone())))); return lines(order); } self.materialize_general(deps) } /// 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> { 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, 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> { // Kept vertices by dense index: Start, End, then the live atoms. let mut index: HashMap = HashMap::with_capacity_and_hasher(self.atoms.len() + 2, Default::default()); let mut verts: Vec = 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> = HashMap::default(); let contracted = |v: Vertex, reach: &mut HashMap>| { 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 = 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 = Vec::with_capacity(verts.len() * 2); let mut starts: Vec = Vec::with_capacity(verts.len() + 1); let mut indeg: Vec = 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 = (0..verts.len() as u32) .filter(|&i| indeg[i as usize] == 0) .collect(); let mut order: Vec = 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 = HashSet::default(); let mut ghosts: HashSet = 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> = HashMap::default(); let mut indeg: HashMap = 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 = indeg .iter() .filter(|(_, &d)| d == 0) .map(|(v, _)| *v) .collect(); let mut side: HashMap = HashMap::default(); let mut joins: HashSet = HashSet::default(); let mut next_side = 0u32; let mut plain: Vec = Vec::new(); let mut conflict: Option>> = None; let mut segments: Vec = Vec::new(); let flush_plain = |plain: &mut Vec, segments: &mut Vec| { let atoms: Vec = 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>, segments: &mut Vec| { let sides: Vec> = c .into_values() .map(|vs| { vs.into_iter() .filter_map(|v| match v { Vertex::Atom(k) if !ghosts.contains(&k) => Some(k), _ => None, }) .collect::>() }) .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 { let total = m.conflict_count(); let mut n = 0; let mut out: Vec = Vec::new(); let push_atoms = |out: &mut Vec, 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| { 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 { 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 { 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::, _>>()?; 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, ghosts: &HashSet) -> Vec { let mut out = Vec::new(); let mut lines: Vec = 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>); 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 = (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 = (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) { 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 = (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 = 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, ); let ops: Vec = 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 = (0..ops.len()).collect(); for _ in 0..50 { order.shuffle(&mut rng); assert_eq!(build(&order), reference, "order {order:?}"); } } }