OXYGENHUB
◆ v0.3.0 oxygen / crates / oxy-core / src / graph.rs
63.5 KiB · Rust · last changed A kept order takes no line that arrives deleted 1 month ago source blame history raw
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::fasthash::{FastMap as HashMap, FastSet as HashSet};
8 
use crate::hash::ChangeHash;
9 
use crate::lines::{LineRef, Lines};
10 
use crate::objects::AtomRange;
11 
use std::collections::{BTreeMap, BTreeSet};
12
13 
/// `(introducing change, index within that change for this node)`.
14 
pub type AtomKey = (ChangeHash, u32);
15
16 
#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
17 
pub enum Vertex {
18 
    Start,
19 
    Atom(AtomKey),
20 
    End,
21 
}
22
23 
/// Transitive dependency test between changes; `depends_on(a, a)` is true.
24 
pub trait DepOracle {
25 
    fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool;
26 
}
27
28 
/// No change depends on any other: every pair commutes.
29 
pub struct NoDeps;
30 
impl DepOracle for NoDeps {
31 
    fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool {
32 
        a == b
33 
    }
34 
}
35
36 
#[derive(Default, Clone, Debug)]
37 
struct AtomInfo {
38 
    /// `None` until the introducing change has been applied; a line of the
39 
    /// insert's shared buffer.
40 
    content: Option<LineRef>,
41 
    deleted_by: BTreeSet<ChangeHash>,
42 
}
43
44 
#[derive(Clone, Debug)]
45 
pub struct FileGraph {
46 
    atoms: HashMap<AtomKey, AtomInfo>,
47 
    /// Every vertex, with its direct successors.
48 
    succ: HashMap<Vertex, Edges>,
49 
    /// The live atoms' order, once known to be the graph's only one.
50 
    order: OrderSlot,
51 
}
52
53 
/// A file graph's live atoms in order, when the graph orders them one way
54 
/// only: found by [`FileGraph::materialize`] and brought up to date by
55 
/// [`Order::splice`] as a change's edits apply, so a long-lived file
56 
/// renders in time that follows its live lines rather than every line it
57 
/// ever had. Any other change to the graph drops it.
58 
#[derive(Debug)]
59 
pub struct Order {
60 
    atoms: Vec<AtomKey>,
61 
    /// Atoms deleted since the order was last confirmed: it holds while
62 
    /// none of them is a ghost (spec §9.1), which only a render can ask,
63 
    /// since it needs to know how the changes depend on each other.
64 
    unchecked: Vec<AtomKey>,
65 
    confirmed: std::sync::atomic::AtomicBool,
66 
}
67
68 
/// Holds a graph's [`Order`]; filled in by a render, which only reads the
69 
/// graph.
70 
#[derive(Debug, Default)]
71 
struct OrderSlot(std::sync::Mutex<Option<std::sync::Arc<Order>>>);
72
73 
impl OrderSlot {
74 
    fn get(&self) -> Option<std::sync::Arc<Order>> {
75 
        self.0.lock().unwrap_or_else(|e| e.into_inner()).clone()
76 
    }
77 
    fn set(&self, o: Option<std::sync::Arc<Order>>) {
78 
        *self.0.lock().unwrap_or_else(|e| e.into_inner()) = o;
79 
    }
80 
    fn take(&mut self) -> Option<std::sync::Arc<Order>> {
81 
        self.0.get_mut().unwrap_or_else(|e| e.into_inner()).take()
82 
    }
83 
}
84
85 
impl Clone for OrderSlot {
86 
    fn clone(&self) -> Self {
87 
        OrderSlot(std::sync::Mutex::new(self.get()))
88 
    }
89 
}
90
91 
impl Order {
92 
    fn known(atoms: Vec<AtomKey>) -> Order {
93 
        Order {
94 
            atoms,
95 
            unchecked: Vec::new(),
96 
            confirmed: std::sync::atomic::AtomicBool::new(true),
97 
        }
98 
    }
99
100 
    /// The order after change `h` inserts the runs `inserts` (after,
101 
    /// before, first index, count) and deletes `deleted`, as its edits
102 
    /// apply; `None` where that is not certain to be the graph's only
103 
    /// order: an anchor not in the order, live lines between an insert's
104 
    /// anchors, or two inserts with nothing kept between them.
105 
    fn splice(
106 
        &self,
107 
        h: ChangeHash,
108 
        inserts: &[(Vertex, Vertex, u32, u32)],
109 
        deleted: &[AtomKey],
110 
    ) -> Option<std::sync::Arc<Order>> {
111 
        let mut want: HashSet<AtomKey> = deleted.iter().copied().collect();
112 
        for (a, b, _, _) in inserts {
113 
            for v in [a, b] {
114 
                if let Vertex::Atom(k) = v {
115 
                    want.insert(*k);
116 
                }
117 
            }
118 
        }
119 
        let mut pos: HashMap<AtomKey, usize> = HashMap::default();
120 
        for (i, k) in self.atoms.iter().enumerate() {
121 
            if want.contains(k) {
122 
                pos.insert(*k, i);
123 
            }
124 
        }
125 
        let len = self.atoms.len();
126 
        let mut gone = vec![false; len];
127 
        let mut unchecked = if self.confirmed.load(std::sync::atomic::Ordering::Relaxed) {
128 
            Vec::new()
129 
        } else {
130 
            self.unchecked.clone()
131 
        };
132 
        for k in deleted {
133 
            if k.0 == h {
134 
                return None;
135 
            }
136 
            if let Some(&i) = pos.get(k) {
137 
                if !gone[i] {
138 
                    gone[i] = true;
139 
                    unchecked.push(*k);
140 
                }
141 
            }
142 
        }
143 
        // Each run goes in the gap its anchors leave (slot `i`: before
144 
        // `atoms[i]`), which must hold nothing that stays.
145 
        let mut slots: Vec<(usize, usize, u32, u32)> = Vec::with_capacity(inserts.len());
146 
        for &(a, b, first, count) in inserts {
147 
            let from = match a {
148 
                Vertex::Start => 0,
149 
                Vertex::Atom(k) => pos.get(&k)? + 1,
150 
                Vertex::End => return None,
151 
            };
152 
            let to = match b {
153 
                Vertex::End => len,
154 
                Vertex::Atom(k) => *pos.get(&k)?,
155 
                Vertex::Start => return None,
156 
            };
157 
            if from > to || gone[from..to].iter().any(|g| !g) {
158 
                return None;
159 
            }
160 
            slots.push((from, to, first, count));
161 
        }
162 
        // Runs one after another need a kept line between them, or the
163 
        // graph would not say which comes first.
164 
        slots.sort_unstable();
165 
        for w in slots.windows(2) {
166 
            let (end, next) = (w[0].1, w[1].0);
167 
            if end >= next || !gone[end..next].iter().any(|g| !g) {
168 
                return None;
169 
            }
170 
        }
171 
        let added: usize = slots.iter().map(|s| s.3 as usize).sum();
172 
        let mut atoms = Vec::with_capacity(len + added);
173 
        let mut slots = slots.into_iter().peekable();
174 
        let mut runs_at = |i: usize, atoms: &mut Vec<AtomKey>| {
175 
            while let Some(&(from, _, first, count)) = slots.peek() {
176 
                if from != i {
177 
                    break;
178 
                }
179 
                atoms.extend((first..first + count).map(|j| (h, j)));
180 
                slots.next();
181 
            }
182 
        };
183 
        for (i, (k, g)) in self.atoms.iter().zip(&gone).enumerate() {
184 
            runs_at(i, &mut atoms);
185 
            if !g {
186 
                atoms.push(*k);
187 
            }
188 
        }
189 
        runs_at(len, &mut atoms);
190 
        let confirmed = unchecked.is_empty();
191 
        Some(std::sync::Arc::new(Order {
192 
            atoms,
193 
            unchecked,
194 
            confirmed: std::sync::atomic::AtomicBool::new(confirmed),
195 
        }))
196 
    }
197 
}
198
199 
/// A vertex's direct successors, sorted and without repeats. Nearly every
200 
/// vertex has one, which is kept inline without an allocation.
201 
#[derive(Clone, Debug, Default, PartialEq, Eq)]
202 
enum Edges {
203 
    #[default]
204 
    None,
205 
    One(Vertex),
206 
    Many(Vec<Vertex>),
207 
}
208
209 
impl Edges {
210 
    fn insert(&mut self, v: Vertex) {
211 
        match self {
212 
            Edges::None => *self = Edges::One(v),
213 
            Edges::One(a) if *a == v => {}
214 
            Edges::One(a) => {
215 
                let a = *a;
216 
                *self = Edges::Many(if a < v { vec![a, v] } else { vec![v, a] });
217 
            }
218 
            Edges::Many(list) => {
219 
                if let Err(i) = list.binary_search(&v) {
220 
                    list.insert(i, v);
221 
                }
222 
            }
223 
        }
224 
    }
225
226 
    fn as_slice(&self) -> &[Vertex] {
227 
        match self {
228 
            Edges::None => &[],
229 
            Edges::One(v) => std::slice::from_ref(v),
230 
            Edges::Many(list) => list,
231 
        }
232 
    }
233
234 
    fn iter(&self) -> std::slice::Iter<'_, Vertex> {
235 
        self.as_slice().iter()
236 
    }
237 
}
238
239 
impl Default for FileGraph {
240 
    fn default() -> Self {
241 
        Self::new()
242 
    }
243 
}
244
245 
/// One piece of a materialized file.
246 
#[derive(Clone, Debug, PartialEq, Eq)]
247 
pub enum Segment {
248 
    Lines(Vec<AtomKey>),
249 
    /// Order conflict: alternatives that cannot be ordered against each other.
250 
    Conflict(Vec<Vec<AtomKey>>),
251 
    /// Delete/insert conflict: `inserted` was anchored to `deleted` by a change
252 
    /// that commutes with the deletion.
253 
    Zombie {
254 
        deleted: Vec<AtomKey>,
255 
        inserted: Vec<AtomKey>,
256 
    },
257 
}
258
259 
#[derive(Clone, Debug, PartialEq, Eq, Default)]
260 
pub struct Materialized {
261 
    pub segments: Vec<Segment>,
262 
}
263
264 
impl Materialized {
265 
    pub fn is_conflicted(&self) -> bool {
266 
        self.segments
267 
            .iter()
268 
            .any(|s| !matches!(s, Segment::Lines(_)))
269 
    }
270 
    pub fn conflict_count(&self) -> usize {
271 
        self.segments
272 
            .iter()
273 
            .filter(|s| !matches!(s, Segment::Lines(_)))
274 
            .count()
275 
    }
276 
    /// Every live atom in materialized order, conflict sides concatenated.
277 
    pub fn live_atoms(&self) -> Vec<AtomKey> {
278 
        let mut out = Vec::new();
279 
        for s in &self.segments {
280 
            match s {
281 
                Segment::Lines(a) => out.extend(a),
282 
                Segment::Conflict(sides) => sides.iter().for_each(|x| out.extend(x)),
283 
                Segment::Zombie { inserted, .. } => out.extend(inserted),
284 
            }
285 
        }
286 
        out
287 
    }
288 
}
289
290 
impl FileGraph {
291 
    pub fn new() -> Self {
292 
        let mut g = FileGraph {
293 
            atoms: HashMap::default(),
294 
            succ: HashMap::default(),
295 
            order: OrderSlot::default(),
296 
        };
297 
        g.edge(Vertex::Start, Vertex::End);
298 
        g
299 
    }
300
301 
    fn edge(&mut self, a: Vertex, b: Vertex) {
302 
        self.succ.entry(a).or_default().insert(b);
303 
        self.succ.entry(b).or_default();
304 
    }
305
306 
    /// Apply an `Insert` by `change` whose first new atom has index `first_index`.
307 
    pub fn insert(
308 
        &mut self,
309 
        change: ChangeHash,
310 
        first_index: u32,
311 
        after: Vertex,
312 
        before: Vertex,
313 
        lines: &Lines,
314 
    ) {
315 
        self.insert_owned(change, first_index, after, before, lines.clone());
316 
    }
317
318 
    /// [`FileGraph::insert`] taking the lines, so loading a state moves
319 
    /// them in rather than copying. Each new atom's entry is made once, as
320 
    /// the source of the next edge, and the chain's ends are ensured last.
321 
    pub fn insert_owned(
322 
        &mut self,
323 
        change: ChangeHash,
324 
        first_index: u32,
325 
        after: Vertex,
326 
        before: Vertex,
327 
        lines: Lines,
328 
    ) {
329 
        self.order.take();
330 
        self.atoms.reserve(lines.len());
331 
        self.succ.reserve(lines.len() + 1);
332 
        let mut prev = after;
333 
        for i in 0..lines.len() {
334 
            let key = (change, first_index + i as u32);
335 
            self.atoms.entry(key).or_default().content =
336 
                Some(LineRef::new(lines.clone(), i as u32));
337 
            let v = Vertex::Atom(key);
338 
            self.succ.entry(prev).or_default().insert(v);
339 
            prev = v;
340 
        }
341 
        self.succ.entry(prev).or_default().insert(before);
342 
        self.succ.entry(before).or_default();
343 
    }
344
345 
    /// Apply a `Delete` of `range` by change `by`.
346 
    pub fn delete(&mut self, by: ChangeHash, range: &AtomRange) {
347 
        self.order.take();
348 
        for i in range.from..range.to {
349 
            self.atoms
350 
                .entry((range.change, i))
351 
                .or_default()
352 
                .deleted_by
353 
                .insert(by);
354 
        }
355 
    }
356
357 
    pub fn is_live(&self, k: &AtomKey) -> bool {
358 
        self.atoms
359 
            .get(k)
360 
            .is_some_and(|a| a.content.is_some() && a.deleted_by.is_empty())
361 
    }
362
363 
    pub fn content(&self, k: &AtomKey) -> Option<&[u8]> {
364 
        self.atoms
365 
            .get(k)
366 
            .and_then(|a| a.content.as_ref().map(LineRef::bytes))
367 
    }
368
369 
    pub fn deleters(&self, k: &AtomKey) -> impl Iterator<Item = &ChangeHash> {
370 
        self.atoms
371 
            .get(k)
372 
            .into_iter()
373 
            .flat_map(|a| a.deleted_by.iter())
374 
    }
375
376 
    /// Number of atoms introduced by `change` in this graph (for index bookkeeping).
377 
    pub fn atom_count(&self) -> usize {
378 
        self.atoms.len()
379 
    }
380
381 
    /// The changes that inserted a live atom directly after `k`. A change
382 
    /// that deletes `k` must depend on them (spec §8.1), or `is_ghost`
383 
    /// reads the deletion as concurrent with those insertions.
384 
    /// Every atom on some path from `first` to `last`, both included, live
385 
    /// or deleted (spec §8): the atoms a range of lines is made of, and
386 
    /// those that were deleted from between them. Empty when `last` does
387 
    /// not follow `first`.
388 
    pub fn between(&self, first: &AtomKey, last: &AtomKey) -> Vec<AtomKey> {
389 
        let (from, to) = (Vertex::Atom(*first), Vertex::Atom(*last));
390 
        let mut ahead: HashSet<Vertex> = HashSet::default();
391 
        let mut stack = vec![from];
392 
        while let Some(v) = stack.pop() {
393 
            if ahead.insert(v) {
394 
                stack.extend(
395 
                    self.succ
396 
                        .get(&v)
397 
                        .map(|e| e.as_slice())
398 
                        .unwrap_or(&[])
399 
                        .iter()
400 
                        .copied(),
401 
                );
402 
            }
403 
        }
404 
        if !ahead.contains(&to) {
405 
            return vec![];
406 
        }
407 
        let mut pred: HashMap<Vertex, Vec<Vertex>> = HashMap::default();
408 
        for (u, es) in &self.succ {
409 
            if ahead.contains(u) {
410 
                for w in es.iter() {
411 
                    pred.entry(*w).or_default().push(*u);
412 
                }
413 
            }
414 
        }
415 
        let mut behind: HashSet<Vertex> = HashSet::default();
416 
        let mut stack = vec![to];
417 
        while let Some(v) = stack.pop() {
418 
            if behind.insert(v) {
419 
                stack.extend(pred.get(&v).into_iter().flatten().copied());
420 
            }
421 
        }
422 
        let mut out: Vec<AtomKey> = ahead
423 
            .intersection(&behind)
424 
            .filter_map(|v| match v {
425 
                Vertex::Atom(k) if self.atoms.contains_key(k) => Some(*k),
426 
                _ => None,
427 
            })
428 
            .collect();
429 
        out.sort();
430 
        out
431 
    }
432
433 
    /// The changes that inserted or deleted any of `atoms`.
434 
    pub fn touching(&self, atoms: &[AtomKey]) -> BTreeSet<ChangeHash> {
435 
        let mut out = BTreeSet::new();
436 
        for k in atoms {
437 
            out.insert(k.0);
438 
            if let Some(info) = self.atoms.get(k) {
439 
                out.extend(info.deleted_by.iter().copied());
440 
            }
441 
        }
442 
        out
443 
    }
444
445 
    pub fn live_successor_changes(&self, k: &AtomKey) -> Vec<ChangeHash> {
446 
        self.succ
447 
            .get(&Vertex::Atom(*k))
448 
            .map(|ss| {
449 
                ss.iter()
450 
                    .filter_map(|s| match s {
451 
                        Vertex::Atom(y) if self.is_live(y) => Some(y.0),
452 
                        _ => None,
453 
                    })
454 
                    .collect()
455 
            })
456 
            .unwrap_or_default()
457 
    }
458
459 
    fn is_ghost(&self, k: &AtomKey, info: &AtomInfo, deps: &dyn DepOracle) -> bool {
460 
        // A deleted atom is a ghost when a live direct successor was inserted
461 
        // by a change that commutes with every deleter: neither depends on
462 
        // the other (spec §9.1, delete/insert). If the inserter came after the
463 
        // deletion, or the deleter saw the insertion, there is no conflict.
464 
        self.succ.get(&Vertex::Atom(*k)).is_some_and(|ss| {
465 
            ss.iter().any(|s| match s {
466 
                Vertex::Atom(y) if self.is_live(y) => !info
467 
                    .deleted_by
468 
                    .iter()
469 
                    .any(|d| deps.depends_on(d, &y.0) || deps.depends_on(&y.0, d)),
470 
                _ => false,
471 
            })
472 
        })
473 
    }
474
475 
    /// Successors of `v` in the graph with non-kept vertices contracted away.
476 
    fn reduced_succ(
477 
        &self,
478 
        v: Vertex,
479 
        kept: &HashSet<Vertex>,
480 
        memo: &mut HashMap<Vertex, BTreeSet<Vertex>>,
481 
    ) -> BTreeSet<Vertex> {
482 
        let direct = self.succ.get(&v).map(Edges::as_slice).unwrap_or_default();
483 
        // The common case, a successor that is itself kept: nothing to
484 
        // contract.
485 
        if direct.iter().all(|s| kept.contains(s)) {
486 
            return direct.iter().copied().collect();
487 
        }
488 
        let mut out = BTreeSet::new();
489 
        let mut stack: Vec<Vertex> = direct.to_vec();
490 
        let mut seen = HashSet::default();
491 
        while let Some(s) = stack.pop() {
492 
            if kept.contains(&s) {
493 
                out.insert(s);
494 
            } else if seen.insert(s) {
495 
                if let Some(m) = memo.get(&s) {
496 
                    out.extend(m.iter().copied());
497 
                } else if let Some(next) = self.succ.get(&s) {
498 
                    stack.extend(next.iter().copied());
499 
                }
500 
            }
501 
        }
502 
        out
503 
    }
504
505 
    /// The atoms in order when the graph is one chain from Start to End with
506 
    /// nothing deleted: a file only ever inserted into in sequence, as every
507 
    /// file of a fresh commit or a clone is. Such a graph has no conflict.
508 
    /// An edge to End besides the chain's next atom (Start's own, or an
509 
    /// append's anchor) orders nothing, since End is last anyway.
510 
    fn as_chain(&self) -> Option<Vec<AtomKey>> {
511 
        if self
512 
            .atoms
513 
            .values()
514 
            .any(|a| a.content.is_none() || !a.deleted_by.is_empty())
515 
        {
516 
            return None;
517 
        }
518 
        let mut order = Vec::with_capacity(self.atoms.len());
519 
        let mut v = Vertex::Start;
520 
        loop {
521 
            let succ = self.succ.get(&v)?.as_slice();
522 
            let mut atoms = succ.iter().filter(|s| **s != Vertex::End);
523 
            match (atoms.next(), atoms.next()) {
524 
                (None, _) if succ.contains(&Vertex::End) => break,
525 
                (Some(Vertex::Atom(k)), None) if order.len() < self.atoms.len() => {
526 
                    order.push(*k);
527 
                    v = Vertex::Atom(*k);
528 
                }
529 
                _ => return None,
530 
            }
531 
        }
532 
        (order.len() == self.atoms.len()).then_some(order)
533 
    }
534
535 
    /// Order the live atoms and locate conflicts.
536 
    pub fn materialize(&self, deps: &dyn DepOracle) -> Materialized {
537 
        let lines = |order: Vec<AtomKey>| Materialized {
538 
            segments: if order.is_empty() {
539 
                vec![]
540 
            } else {
541 
                vec![Segment::Lines(order)]
542 
            },
543 
        };
544 
        use std::sync::atomic::Ordering::Relaxed;
545 
        // Which way it went, and how long it took (`OXY_TIMINGS`).
546 
        let started = crate::timing::enabled().then(std::time::Instant::now);
547 
        let took = |name: &'static str| {
548 
            if let Some(t) = started {
549 
                crate::timing::add(name, t.elapsed());
550 
            }
551 
        };
552 
        if let Some(o) = self.order.get() {
553 
            let holds = o.confirmed.load(Relaxed)
554 
                || o.unchecked.iter().all(|k| {
555 
                    self.atoms
556 
                        .get(k)
557 
                        .is_none_or(|info| !self.is_ghost(k, info, deps))
558 
                });
559 
            if holds {
560 
                o.confirmed.store(true, Relaxed);
561 
                took("graph: kept order");
562 
                return lines(o.atoms.clone());
563 
            }
564 
            self.order.set(None);
565 
        }
566 
        // A chain (nothing ever deleted) is quick to walk, and a fresh tree
567 
        // is all chains: no order is kept for one.
568 
        if let Some(order) = self.as_chain() {
569 
            took("graph: chain");
570 
            return lines(order);
571 
        }
572 
        if let Some(order) = self.as_order(deps) {
573 
            self.order
574 
                .set(Some(std::sync::Arc::new(Order::known(order.clone()))));
575 
            took("graph: single order");
576 
            return lines(order);
577 
        }
578 
        let m = self.materialize_general(deps);
579 
        took("graph: general");
580 
        m
581 
    }
582
583 
    /// Take the kept order, to [`Order::splice`] it once a change's edits
584 
    /// have applied (they drop it).
585 
    pub fn take_order(&mut self) -> Option<std::sync::Arc<Order>> {
586 
        self.order.take()
587 
    }
588
589 
    /// Keep `order` (taken before change `h`'s edits applied) spliced by
590 
    /// them: `inserts` (after, before, first index, count) and `deleted`.
591 
    /// Changes may apply in any order, so a line may arrive already
592 
    /// deleted by a change applied before it: then the order is dropped.
593 
    pub fn keep_spliced(
594 
        &mut self,
595 
        order: std::sync::Arc<Order>,
596 
        h: ChangeHash,
597 
        inserts: &[(Vertex, Vertex, u32, u32)],
598 
        deleted: &[AtomKey],
599 
    ) {
600 
        let live = inserts
601 
            .iter()
602 
            .all(|&(_, _, first, count)| (first..first + count).all(|i| self.is_live(&(h, i))));
603 
        let spliced = if live {
604 
            order.splice(h, inserts, deleted)
605 
        } else {
606 
            None
607 
        };
608 
        *self.order.0.get_mut().unwrap_or_else(|e| e.into_inner()) = spliced;
609 
    }
610
611 
    /// The live atoms in order when, with the dead ones contracted away,
612 
    /// the graph orders them one way only: no deleted atom is a ghost, and
613 
    /// at every step of the topological sort one vertex is next. A file
614 
    /// edited without concurrent edits is such a graph, however long its
615 
    /// history. `None` otherwise, for [`FileGraph::materialize_general`]
616 
    /// to find the conflicts; where this answers, it gives the same order.
617 
    fn as_order(&self, deps: &dyn DepOracle) -> Option<Vec<AtomKey>> {
618 
        // Kept vertices by dense index: Start, End, then the live atoms.
619 
        let mut index: HashMap<Vertex, u32> =
620 
            HashMap::with_capacity_and_hasher(self.atoms.len() + 2, Default::default());
621 
        let mut verts: Vec<Vertex> = Vec::with_capacity(self.atoms.len() + 2);
622 
        verts.extend([Vertex::Start, Vertex::End]);
623 
        index.insert(Vertex::Start, 0);
624 
        index.insert(Vertex::End, 1);
625 
        for (k, info) in &self.atoms {
626 
            if info.content.is_none() {
627 
                continue;
628 
            }
629 
            if info.deleted_by.is_empty() {
630 
                index.insert(Vertex::Atom(*k), verts.len() as u32);
631 
                verts.push(Vertex::Atom(*k));
632 
            } else if self.is_ghost(k, info, deps) {
633 
                return None;
634 
            }
635 
        }
636 
        // Each kept vertex's successors, contracting the others: what a
637 
        // contracted vertex reaches is worked out once (post-order).
638 
        let mut reach: HashMap<Vertex, Vec<u32>> = HashMap::default();
639 
        let contracted = |v: Vertex, reach: &mut HashMap<Vertex, Vec<u32>>| {
640 
            let mut stack: Vec<(Vertex, bool)> = vec![(v, false)];
641 
            while let Some((x, done)) = stack.pop() {
642 
                if reach.contains_key(&x) {
643 
                    continue;
644 
                }
645 
                let next = self.succ.get(&x).map(Edges::as_slice).unwrap_or_default();
646 
                if !done {
647 
                    stack.push((x, true));
648 
                    for s in next {
649 
                        if !index.contains_key(s) && !reach.contains_key(s) {
650 
                            stack.push((*s, false));
651 
                        }
652 
                    }
653 
                    continue;
654 
                }
655 
                let mut out: Vec<u32> = Vec::new();
656 
                for s in next {
657 
                    match index.get(s) {
658 
                        Some(i) => out.push(*i),
659 
                        None => out.extend(reach.get(s).into_iter().flatten()),
660 
                    }
661 
                }
662 
                out.sort_unstable();
663 
                out.dedup();
664 
                reach.insert(x, out);
665 
            }
666 
        };
667 
        // Successors of vertex `i`: `succ[starts[i]..starts[i + 1]]`.
668 
        let mut succ: Vec<u32> = Vec::with_capacity(verts.len() * 2);
669 
        let mut starts: Vec<usize> = Vec::with_capacity(verts.len() + 1);
670 
        let mut indeg: Vec<u32> = vec![0; verts.len()];
671 
        for v in &verts {
672 
            let from = succ.len();
673 
            starts.push(from);
674 
            for s in self.succ.get(v).map(Edges::as_slice).unwrap_or_default() {
675 
                match index.get(s) {
676 
                    Some(i) => succ.push(*i),
677 
                    None => {
678 
                        contracted(*s, &mut reach);
679 
                        succ.extend(reach.get(s).into_iter().flatten());
680 
                    }
681 
                }
682 
            }
683 
            if succ.len() - from > 1 {
684 
                succ[from..].sort_unstable();
685 
                let mut kept = from;
686 
                for i in from..succ.len() {
687 
                    if i == from || succ[i] != succ[kept - 1] {
688 
                        succ[kept] = succ[i];
689 
                        kept += 1;
690 
                    }
691 
                }
692 
                succ.truncate(kept);
693 
            }
694 
            for &w in &succ[from..] {
695 
                indeg[w as usize] += 1;
696 
            }
697 
        }
698 
        starts.push(succ.len());
699 
        // Kahn's algorithm, giving up where two vertices are ready at once.
700 
        let mut ready: Vec<u32> = (0..verts.len() as u32)
701 
            .filter(|&i| indeg[i as usize] == 0)
702 
            .collect();
703 
        let mut order: Vec<AtomKey> = Vec::with_capacity(verts.len());
704 
        let mut seen = 0;
705 
        while let Some(v) = ready.pop() {
706 
            if !ready.is_empty() {
707 
                return None;
708 
            }
709 
            seen += 1;
710 
            if let Vertex::Atom(k) = verts[v as usize] {
711 
                order.push(k);
712 
            }
713 
            for &w in &succ[starts[v as usize]..starts[v as usize + 1]] {
714 
                indeg[w as usize] -= 1;
715 
                if indeg[w as usize] == 0 {
716 
                    ready.push(w);
717 
                }
718 
            }
719 
            if ready.len() > 1 {
720 
                return None;
721 
            }
722 
        }
723 
        (seen == verts.len()).then_some(order)
724 
    }
725
726 
    /// [`FileGraph::materialize`] for any graph: contraction, then a
727 
    /// topological order with conflict regions.
728 
    fn materialize_general(&self, deps: &dyn DepOracle) -> Materialized {
729 
        // 1. Vertices that survive contraction: live atoms, ghosts, Start, End.
730 
        let mut kept: HashSet<Vertex> = HashSet::default();
731 
        let mut ghosts: HashSet<AtomKey> = HashSet::default();
732 
        kept.insert(Vertex::Start);
733 
        kept.insert(Vertex::End);
734 
        for (k, info) in &self.atoms {
735 
            if info.content.is_none() {
736 
                continue;
737 
            }
738 
            if info.deleted_by.is_empty() {
739 
                kept.insert(Vertex::Atom(*k));
740 
            } else if self.is_ghost(k, info, deps) {
741 
                kept.insert(Vertex::Atom(*k));
742 
                ghosts.insert(*k);
743 
            }
744 
        }
745
746 
        // 2. Reduced graph over kept vertices.
747 
        let mut memo = HashMap::default();
748 
        let mut rsucc: HashMap<Vertex, BTreeSet<Vertex>> = HashMap::default();
749 
        let mut indeg: HashMap<Vertex, usize> = HashMap::default();
750 
        for &u in &kept {
751 
            indeg.entry(u).or_insert(0);
752 
            let rs = self.reduced_succ(u, &kept, &mut memo);
753 
            for &w in &rs {
754 
                *indeg.entry(w).or_insert(0) += 1;
755 
            }
756 
            rsucc.insert(u, rs);
757 
        }
758
759 
        // 3. Kahn's algorithm with side labelling for conflict regions.
760 
        let mut ready: BTreeSet<Vertex> = indeg
761 
            .iter()
762 
            .filter(|(_, &d)| d == 0)
763 
            .map(|(v, _)| *v)
764 
            .collect();
765 
        let mut side: HashMap<Vertex, u32> = HashMap::default();
766 
        let mut joins: HashSet<Vertex> = HashSet::default();
767 
        let mut next_side = 0u32;
768 
        let mut plain: Vec<Vertex> = Vec::new();
769 
        let mut conflict: Option<BTreeMap<u32, Vec<Vertex>>> = None;
770 
        let mut segments: Vec<Segment> = Vec::new();
771
772 
        let flush_plain = |plain: &mut Vec<Vertex>, segments: &mut Vec<Segment>| {
773 
            let atoms: Vec<AtomKey> = plain
774 
                .iter()
775 
                .filter_map(|v| {
776 
                    if let Vertex::Atom(k) = v {
777 
                        Some(*k)
778 
                    } else {
779 
                        None
780 
                    }
781 
                })
782 
                .collect();
783 
            plain.clear();
784 
            if !atoms.is_empty() {
785 
                segments.extend(split_zombies(atoms, &ghosts));
786 
            }
787 
        };
788 
        let finish_conflict = |c: BTreeMap<u32, Vec<Vertex>>, segments: &mut Vec<Segment>| {
789 
            let sides: Vec<Vec<AtomKey>> = c
790 
                .into_values()
791 
                .map(|vs| {
792 
                    vs.into_iter()
793 
                        .filter_map(|v| match v {
794 
                            Vertex::Atom(k) if !ghosts.contains(&k) => Some(k),
795 
                            _ => None,
796 
                        })
797 
                        .collect::<Vec<_>>()
798 
                })
799 
                .filter(|s| !s.is_empty())
800 
                .collect();
801 
            match sides.len() {
802 
                0 => {}
803 
                1 => segments.push(Segment::Lines(sides.into_iter().next().unwrap())),
804 
                _ => segments.push(Segment::Conflict(sides)),
805 
            }
806 
        };
807
808 
        while !ready.is_empty() {
809 
            if ready.len() >= 2 {
810 
                if conflict.is_none() {
811 
                    flush_plain(&mut plain, &mut segments);
812 
                    conflict = Some(BTreeMap::new());
813 
                }
814 
                for r in &ready {
815 
                    if !side.contains_key(r) {
816 
                        side.insert(*r, next_side);
817 
                        next_side += 1;
818 
                    }
819 
                }
820 
            }
821 
            let v = ready.pop_first().unwrap();
822 
            let my_side = side.get(&v).copied();
823 
            match (&mut conflict, my_side) {
824 
                (Some(c), Some(s)) => c.entry(s).or_default().push(v),
825 
                (Some(_), None) => {
826 
                    let c = conflict.take().unwrap();
827 
                    finish_conflict(c, &mut segments);
828 
                    plain.push(v);
829 
                }
830 
                (None, _) => plain.push(v),
831 
            }
832 
            for &w in &rsucc[&v] {
833 
                let d = indeg.get_mut(&w).unwrap();
834 
                *d -= 1;
835 
                if conflict.is_some() && !joins.contains(&w) {
836 
                    match (my_side, side.get(&w).copied()) {
837 
                        (Some(s), None) => {
838 
                            side.insert(w, s);
839 
                        }
840 
                        (Some(s), Some(t)) if s != t => {
841 
                            side.remove(&w);
842 
                            joins.insert(w);
843 
                        }
844 
                        (None, Some(_)) => {
845 
                            side.remove(&w);
846 
                            joins.insert(w);
847 
                        }
848 
                        _ => {}
849 
                    }
850 
                }
851 
                if *d == 0 {
852 
                    ready.insert(w);
853 
                }
854 
            }
855 
        }
856 
        if let Some(c) = conflict.take() {
857 
            finish_conflict(c, &mut segments);
858 
        }
859 
        flush_plain(&mut plain, &mut segments);
860 
        Materialized { segments }
861 
    }
862
863 
    /// Render a materialization to bytes with conflict markers (spec §9.5).
864 
    /// `label` gives the short description of a change for marker headers.
865 
    pub fn render(&self, m: &Materialized, label: &dyn Fn(&ChangeHash) -> String) -> Vec<u8> {
866 
        let total = m.conflict_count();
867 
        let mut n = 0;
868 
        let mut out: Vec<u8> = Vec::new();
869 
        let push_atoms = |out: &mut Vec<u8>, atoms: &[AtomKey]| {
870 
            for a in atoms {
871 
                if let Some(c) = self.content(a) {
872 
                    out.extend_from_slice(c);
873 
                }
874 
            }
875 
        };
876 
        let newline_if_needed = |out: &mut Vec<u8>| {
877 
            if !out.is_empty() && *out.last().unwrap() != b'\n' {
878 
                out.push(b'\n');
879 
            }
880 
        };
881 
        for seg in &m.segments {
882 
            match seg {
883 
                Segment::Lines(a) => push_atoms(&mut out, a),
884 
                Segment::Conflict(sides) => {
885 
                    n += 1;
886 
                    let k = sides.len();
887 
                    for (i, s) in sides.iter().enumerate() {
888 
                        newline_if_needed(&mut out);
889 
                        let who = s.first().map(|a| label(&a.0)).unwrap_or_default();
890 
                        let marker = if i == 0 { "<<<<<<<" } else { "=======" };
891 
                        out.extend_from_slice(
892 
                            format!("{marker} oxy conflict {n} of {total}, side {} of {k}: change {who}\n", i + 1).as_bytes(),
893 
                        );
894 
                        push_atoms(&mut out, s);
895 
                    }
896 
                    newline_if_needed(&mut out);
897 
                    out.extend_from_slice(
898 
                        format!(">>>>>>> oxy conflict {n} of {total} end\n").as_bytes(),
899 
                    );
900 
                }
901 
                Segment::Zombie { deleted, inserted } => {
902 
                    n += 1;
903 
                    newline_if_needed(&mut out);
904 
                    let deleter = deleted
905 
                        .first()
906 
                        .and_then(|a| self.deleters(a).next().copied())
907 
                        .map(|d| label(&d))
908 
                        .unwrap_or_default();
909 
                    let inserter = inserted.first().map(|a| label(&a.0)).unwrap_or_default();
910 
                    out.extend_from_slice(
911 
                        format!("<<<<<<< oxy conflict {n} of {total}, side 1 of 2: deleted by change {deleter}\n-------\n").as_bytes(),
912 
                    );
913 
                    push_atoms(&mut out, deleted);
914 
                    newline_if_needed(&mut out);
915 
                    out.extend_from_slice(
916 
                        format!(
917 
                            "======= oxy conflict {n} of {total}, side 2 of 2: change {inserter}\n"
918 
                        )
919 
                        .as_bytes(),
920 
                    );
921 
                    push_atoms(&mut out, inserted);
922 
                    newline_if_needed(&mut out);
923 
                    out.extend_from_slice(
924 
                        format!(">>>>>>> oxy conflict {n} of {total} end\n").as_bytes(),
925 
                    );
926 
                }
927 
            }
928 
        }
929 
        out
930 
    }
931 
}
932
933 
fn vertex_value(v: &Vertex) -> crate::cbor::Value {
934 
    use crate::cbor::Value;
935 
    match v {
936 
        Vertex::Start => Value::Uint(0),
937 
        Vertex::End => Value::Uint(1),
938 
        Vertex::Atom((c, i)) => {
939 
            Value::Array(vec![Value::Bytes(c.0.to_vec()), Value::Uint(*i as u64)])
940 
        }
941 
    }
942 
}
943
944 
fn vertex_from(v: &crate::cbor::Value) -> Result<Vertex, crate::objects::ObjectError> {
945 
    use crate::cbor::Value;
946 
    use crate::objects::ObjectError;
947 
    match v {
948 
        Value::Uint(0) => Ok(Vertex::Start),
949 
        Value::Uint(1) => Ok(Vertex::End),
950 
        Value::Array(a) if a.len() == 2 => Ok(Vertex::Atom((
951 
            crate::objects::oref(&a[0], "vertex")?,
952 
            crate::objects::u32_(&a[1], "vertex")?,
953 
        ))),
954 
        _ => Err(ObjectError::Schema(
955 
            "vertex: expected 0, 1, or [hash, index]".into(),
956 
        )),
957 
    }
958 
}
959
960 
impl FileGraph {
961 
    /// Serialize for a checkpoint: `{0: atoms [[hash, index, content|null, [deleters]]], 1: edges [[from, to]]}`.
962 
    pub fn to_value(&self) -> crate::cbor::Value {
963 
        use crate::cbor::Value;
964 
        let mut atoms: Vec<(&AtomKey, &AtomInfo)> = self.atoms.iter().collect();
965 
        atoms.sort_by_key(|(k, _)| **k);
966 
        let mut edges: Vec<(Vertex, Vertex)> = self
967 
            .succ
968 
            .iter()
969 
            .flat_map(|(a, bs)| bs.iter().map(move |b| (*a, *b)))
970 
            .collect();
971 
        edges.sort();
972 
        Value::map([
973 
            (
974 
                0,
975 
                Value::Array(
976 
                    atoms
977 
                        .into_iter()
978 
                        .map(|((c, i), info)| {
979 
                            Value::Array(vec![
980 
                                Value::Bytes(c.0.to_vec()),
981 
                                Value::Uint(*i as u64),
982 
                                info.content
983 
                                    .as_ref()
984 
                                    .map(|b| Value::Bytes(b.bytes().to_vec()))
985 
                                    .unwrap_or(Value::Null),
986 
                                Value::Array(
987 
                                    info.deleted_by
988 
                                        .iter()
989 
                                        .map(|d| Value::Bytes(d.0.to_vec()))
990 
                                        .collect(),
991 
                                ),
992 
                            ])
993 
                        })
994 
                        .collect(),
995 
                ),
996 
            ),
997 
            (
998 
                1,
999 
                Value::Array(
1000 
                    edges
1001 
                        .iter()
1002 
                        .map(|(a, b)| Value::Array(vec![vertex_value(a), vertex_value(b)]))
1003 
                        .collect(),
1004 
                ),
1005 
            ),
1006 
        ])
1007 
    }
1008
1009 
    pub fn from_value(v: &crate::cbor::Value) -> Result<FileGraph, crate::objects::ObjectError> {
1010 
        use crate::objects::{array, bytes, field, map, oref, u32_, ObjectError};
1011 
        let m = map(v, "file graph")?;
1012 
        let mut g = FileGraph {
1013 
            atoms: HashMap::default(),
1014 
            succ: HashMap::default(),
1015 
            order: OrderSlot::default(),
1016 
        };
1017 
        let atoms = array(field(m, 0, "atoms")?, "atoms")?;
1018 
        // Every atom's line in one buffer.
1019 
        let mut texts: Vec<&[u8]> = Vec::new();
1020 
        for a in atoms {
1021 
            let e = array(a, "atom")?;
1022 
            if e.len() == 4 && !e[2].is_null() {
1023 
                texts.push(bytes(&e[2], "atom content")?);
1024 
            }
1025 
        }
1026 
        let all: Lines = texts.into_iter().collect();
1027 
        let mut next = 0u32;
1028 
        for a in atoms {
1029 
            let e = array(a, "atom")?;
1030 
            if e.len() != 4 {
1031 
                return Err(ObjectError::Schema("atom: expected 4 fields".into()));
1032 
            }
1033 
            let key = (oref(&e[0], "atom change")?, u32_(&e[1], "atom index")?);
1034 
            let content = if e[2].is_null() {
1035 
                None
1036 
            } else {
1037 
                next += 1;
1038 
                Some(LineRef::new(all.clone(), next - 1))
1039 
            };
1040 
            let deleted_by = array(&e[3], "deleters")?
1041 
                .iter()
1042 
                .map(|d| oref(d, "deleter"))
1043 
                .collect::<Result<BTreeSet<_>, _>>()?;
1044 
            g.atoms.insert(
1045 
                key,
1046 
                AtomInfo {
1047 
                    content,
1048 
                    deleted_by,
1049 
                },
1050 
            );
1051 
        }
1052 
        for e in array(field(m, 1, "edges")?, "edges")? {
1053 
            let pair = array(e, "edge")?;
1054 
            if pair.len() != 2 {
1055 
                return Err(ObjectError::Schema("edge: expected [from, to]".into()));
1056 
            }
1057 
            g.edge(vertex_from(&pair[0])?, vertex_from(&pair[1])?);
1058 
        }
1059 
        Ok(g)
1060 
    }
1061 
}
1062
1063 
/// Split a plain run into `Lines` and `Zombie` segments around ghost atoms.
1064 
fn split_zombies(atoms: Vec<AtomKey>, ghosts: &HashSet<AtomKey>) -> Vec<Segment> {
1065 
    let mut out = Vec::new();
1066 
    let mut lines: Vec<AtomKey> = Vec::new();
1067 
    let mut i = 0;
1068 
    while i < atoms.len() {
1069 
        if !ghosts.contains(&atoms[i]) {
1070 
            lines.push(atoms[i]);
1071 
            i += 1;
1072 
            continue;
1073 
        }
1074 
        if !lines.is_empty() {
1075 
            out.push(Segment::Lines(std::mem::take(&mut lines)));
1076 
        }
1077 
        let mut deleted = Vec::new();
1078 
        while i < atoms.len() && ghosts.contains(&atoms[i]) {
1079 
            deleted.push(atoms[i]);
1080 
            i += 1;
1081 
        }
1082 
        let mut inserted = Vec::new();
1083 
        if i < atoms.len() {
1084 
            let ch = atoms[i].0;
1085 
            while i < atoms.len() && atoms[i].0 == ch && !ghosts.contains(&atoms[i]) {
1086 
                inserted.push(atoms[i]);
1087 
                i += 1;
1088 
            }
1089 
        }
1090 
        out.push(Segment::Zombie { deleted, inserted });
1091 
    }
1092 
    if !lines.is_empty() {
1093 
        out.push(Segment::Lines(lines));
1094 
    }
1095 
    out
1096 
}
1097
1098 
#[cfg(test)]
1099 
mod tests {
1100 
    use super::*;
1101 
    use crate::hash::ObjectRef;
1102
1103 
    fn h(n: u8) -> ChangeHash {
1104 
        ObjectRef([n; 32])
1105 
    }
1106 
    fn lines(v: &[&str]) -> Lines {
1107 
        v.iter().map(|s| s.as_bytes()).collect()
1108 
    }
1109 
    fn text(g: &FileGraph, m: &Materialized) -> String {
1110 
        String::from_utf8(g.render(m, &|c| c.short(4))).unwrap()
1111 
    }
1112
1113 
    struct Deps(HashMap<ChangeHash, Vec<ChangeHash>>);
1114 
    impl DepOracle for Deps {
1115 
        fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool {
1116 
            if a == b {
1117 
                return true;
1118 
            }
1119 
            let mut stack = vec![*a];
1120 
            let mut seen = HashSet::default();
1121 
            while let Some(x) = stack.pop() {
1122 
                if let Some(ds) = self.0.get(&x) {
1123 
                    for d in ds {
1124 
                        if d == b {
1125 
                            return true;
1126 
                        }
1127 
                        if seen.insert(*d) {
1128 
                            stack.push(*d);
1129 
                        }
1130 
                    }
1131 
                }
1132 
            }
1133 
            false
1134 
        }
1135 
    }
1136
1137 
    /// Linear history: each change depends on every earlier one.
1138 
    struct Linear;
1139 
    impl DepOracle for Linear {
1140 
        fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool {
1141 
            a.0[..2] >= b.0[..2]
1142 
        }
1143 
    }
1144
1145 
    /// A file of `n` lines edited `revs` times, `per` lines replaced each
1146 
    /// time, as a long-lived file is: most atoms dead, one live chain.
1147 
    fn edited_file(n: usize, revs: usize, per: usize) -> FileGraph {
1148 
        let hn = |i: usize| {
1149 
            let mut b = [0u8; 32];
1150 
            b[..2].copy_from_slice(&(i as u16).to_be_bytes());
1151 
            ObjectRef(b)
1152 
        };
1153 
        let mut g = FileGraph::new();
1154 
        let first: Vec<String> = (0..n).map(|i| format!("line {i}\n")).collect();
1155 
        let first: Vec<&str> = first.iter().map(String::as_str).collect();
1156 
        g.insert(hn(1), 0, Vertex::Start, Vertex::End, &lines(&first));
1157 
        for r in 2..revs + 2 {
1158 
            let order = g.materialize(&Linear).live_atoms();
1159 
            let step = order.len() / per;
1160 
            for j in 0..per {
1161 
                let at = j * step + (r % step.max(1));
1162 
                let k = order[at];
1163 
                g.delete(
1164 
                    hn(r),
1165 
                    &AtomRange {
1166 
                        change: k.0,
1167 
                        from: k.1,
1168 
                        to: k.1 + 1,
1169 
                    },
1170 
                );
1171 
                let after = if at == 0 {
1172 
                    Vertex::Start
1173 
                } else {
1174 
                    Vertex::Atom(order[at - 1])
1175 
                };
1176 
                let before = order
1177 
                    .get(at + 1)
1178 
                    .map(|k| Vertex::Atom(*k))
1179 
                    .unwrap_or(Vertex::End);
1180 
                g.insert(hn(r), j as u32, after, before, &lines(&["new\n"]));
1181 
            }
1182 
        }
1183 
        g
1184 
    }
1185
1186 
    /// The single-order shortcut gives what the general algorithm gives.
1187 
    #[test]
1188 
    fn the_order_shortcut_agrees_with_the_general_order() {
1189 
        let g = edited_file(500, 10, 20);
1190 
        assert!(g.as_chain().is_none());
1191 
        let fast = g.as_order(&Linear).expect("a single order");
1192 
        assert_eq!(
1193 
            Materialized {
1194 
                segments: vec![Segment::Lines(fast)]
1195 
            },
1196 
            g.materialize_general(&Linear)
1197 
        );
1198 
        // Two changes inserting at one place concurrently: a conflict,
1199 
        // which the shortcut leaves to the general algorithm.
1200 
        let mut g = FileGraph::new();
1201 
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n"]));
1202 
        let a = Vertex::Atom((h(1), 0));
1203 
        g.insert(h(2), 0, a, Vertex::End, &lines(&["b\n"]));
1204 
        g.insert(h(3), 0, a, Vertex::End, &lines(&["c\n"]));
1205 
        assert!(g.as_order(&NoDeps).is_none());
1206 
        assert!(g.materialize(&NoDeps).is_conflicted());
1207 
    }
1208
1209 
    /// Applied as the state applies a change's edits: the kept order is
1210 
    /// spliced by them.
1211 
    fn apply_spliced(
1212 
        g: &mut FileGraph,
1213 
        h: ChangeHash,
1214 
        inserts: &[(Vertex, Vertex, usize)],
1215 
        deleted: &[AtomKey],
1216 
    ) {
1217 
        let order = g.take_order();
1218 
        let mut runs = Vec::new();
1219 
        let mut next = 0u32;
1220 
        for (i, &(a, b, n)) in inserts.iter().enumerate() {
1221 
            let text: Vec<String> = (0..n).map(|j| format!("{i}.{j}\n")).collect();
1222 
            let text: Vec<&str> = text.iter().map(String::as_str).collect();
1223 
            g.insert(h, next, a, b, &lines(&text));
1224 
            runs.push((a, b, next, n as u32));
1225 
            next += n as u32;
1226 
        }
1227 
        for k in deleted {
1228 
            g.delete(
1229 
                h,
1230 
                &AtomRange {
1231 
                    change: k.0,
1232 
                    from: k.1,
1233 
                    to: k.1 + 1,
1234 
                },
1235 
            );
1236 
        }
1237 
        if let Some(o) = order {
1238 
            g.keep_spliced(o, h, &runs, deleted);
1239 
        }
1240 
    }
1241
1242 
    /// Edits as a diff makes them from the order `l`: hunks with a kept
1243 
    /// line between them, each deleting some lines and inserting some.
1244 
    fn random_edits(
1245 
        l: &[AtomKey],
1246 
        rnd: &mut impl FnMut(usize) -> usize,
1247 
    ) -> (Vec<(Vertex, Vertex, usize)>, Vec<AtomKey>) {
1248 
        let (mut inserts, mut deleted) = (Vec::new(), Vec::new());
1249 
        let mut i = rnd(3);
1250 
        while i <= l.len() {
1251 
            let del = rnd(3).min(l.len() - i);
1252 
            let add = rnd(3);
1253 
            let after = if i == 0 {
1254 
                Vertex::Start
1255 
            } else {
1256 
                Vertex::Atom(l[i - 1])
1257 
            };
1258 
            let before = l.get(i).map(|k| Vertex::Atom(*k)).unwrap_or(Vertex::End);
1259 
            deleted.extend(&l[i..i + del]);
1260 
            if add > 0 {
1261 
                inserts.push((after, before, add));
1262 
            }
1263 
            i += del + 1 + rnd(6);
1264 
        }
1265 
        (inserts, deleted)
1266 
    }
1267
1268 
    /// The kept order, spliced change by change, is what the general
1269 
    /// algorithm finds, through sequential edits and through concurrent
1270 
    /// ones that leave conflicts and ghosts (where it must stand aside).
1271 
    #[test]
1272 
    fn the_kept_order_follows_edits() {
1273 
        let hn = |i: usize| {
1274 
            let mut b = [0u8; 32];
1275 
            b[..2].copy_from_slice(&(i as u16).to_be_bytes());
1276 
            ObjectRef(b)
1277 
        };
1278 
        let mut seed = 7u64;
1279 
        let mut rnd = move |n: usize| {
1280 
            seed = seed
1281 
                .wrapping_mul(6364136223846793005)
1282 
                .wrapping_add(1442695040888963407);
1283 
            ((seed >> 33) as usize) % n.max(1)
1284 
        };
1285 
        let mut deps = Deps(HashMap::default());
1286 
        let mut g = FileGraph::new();
1287 
        let first: Vec<String> = (0..40).map(|i| format!("{i}\n")).collect();
1288 
        let first: Vec<&str> = first.iter().map(String::as_str).collect();
1289 
        g.insert(hn(1), 0, Vertex::Start, Vertex::End, &lines(&first));
1290 
        let mut known: Vec<ChangeHash> = vec![hn(1)];
1291 
        let mut c = 2;
1292 
        let (mut spliced, mut conflicted) = (0, 0);
1293 
        for step in 0..400 {
1294 
            let l = g.materialize(&deps).live_atoms();
1295 
            // Now and then two changes from the same base, neither knowing
1296 
            // the other.
1297 
            let pair = step % 7 == 3;
1298 
            let base = known.clone();
1299 
            for _ in 0..if pair { 2 } else { 1 } {
1300 
                let h = hn(c);
1301 
                c += 1;
1302 
                let (inserts, deleted) = random_edits(&l, &mut rnd);
1303 
                deps.0.insert(h, base.clone());
1304 
                apply_spliced(&mut g, h, &inserts, &deleted);
1305 
                known.push(h);
1306 
                if g.order.get().is_some() {
1307 
                    spliced += 1;
1308 
                }
1309 
                let m = g.materialize(&deps);
1310 
                assert_eq!(m, g.materialize_general(&deps), "step {step}");
1311 
                if m.is_conflicted() {
1312 
                    conflicted += 1;
1313 
                }
1314 
            }
1315 
            // A change that knows everything settles any conflict by
1316 
            // rewriting the file.
1317 
            if g.materialize(&deps).is_conflicted() {
1318 
                let h = hn(c);
1319 
                c += 1;
1320 
                let all = g.materialize(&deps).live_atoms();
1321 
                deps.0.insert(h, known.clone());
1322 
                apply_spliced(&mut g, h, &[(Vertex::Start, Vertex::End, 5)], &all);
1323 
                known.push(h);
1324 
                assert_eq!(g.materialize(&deps), g.materialize_general(&deps));
1325 
            }
1326 
        }
1327 
        assert!(
1328 
            spliced > 100 && conflicted > 0,
1329 
            "{spliced} spliced, {conflicted} conflicted"
1330 
        );
1331 
    }
1332
1333 
    /// A change applied before the one whose line it deletes (as a merge
1334 
    /// adds the other side, newest first): the line arrives dead, and the
1335 
    /// kept order must not take it in.
1336 
    #[test]
1337 
    fn the_kept_order_takes_no_line_that_arrives_deleted() {
1338 
        let mut deps = Deps(HashMap::default());
1339 
        let mut g = FileGraph::new();
1340 
        g.insert(
1341 
            h(1),
1342 
            0,
1343 
            Vertex::Start,
1344 
            Vertex::End,
1345 
            &lines(&["a\n", "b\n", "c\n"]),
1346 
        );
1347 
        // A deletion, so the order is kept rather than walked as a chain.
1348 
        apply_spliced(&mut g, h(2), &[], &[(h(1), 2)]);
1349 
        deps.0.insert(h(2), vec![h(1)]);
1350 
        let _ = g.materialize(&deps);
1351 
        assert!(g.order.get().is_some());
1352 
        let (a, b) = (Vertex::Atom((h(1), 0)), Vertex::Atom((h(1), 1)));
1353 
        // h(3) inserts x between a and b; h(4) deletes it. h(4) first.
1354 
        deps.0.insert(h(3), vec![h(2)]);
1355 
        deps.0.insert(h(4), vec![h(3)]);
1356 
        apply_spliced(&mut g, h(4), &[], &[(h(3), 0)]);
1357 
        apply_spliced(&mut g, h(3), &[(a, b, 1)], &[]);
1358 
        let m = g.materialize(&deps);
1359 
        assert_eq!(m, g.materialize_general(&deps));
1360 
        assert_eq!(text(&g, &m), "a\nb\n");
1361 
    }
1362
1363 
    /// How long rendering a long-lived file takes (run by hand, in release).
1364 
    #[test]
1365 
    #[ignore]
1366 
    fn bench_materialize_edited_file() {
1367 
        let g = edited_file(20_000, 50, 100);
1368 
        let t = std::time::Instant::now();
1369 
        let mut n = 0;
1370 
        for _ in 0..20 {
1371 
            n += g.materialize(&Linear).live_atoms().len();
1372 
        }
1373 
        eprintln!(
1374 
            "materialize: {:.2} ms each ({n} atoms)",
1375 
            t.elapsed().as_secs_f64() * 1000.0 / 20.0
1376 
        );
1377 
    }
1378
1379 
    /// The chain shortcut agrees with the general algorithm wherever it
1380 
    /// applies, and stands aside wherever it does not.
1381 
    #[test]
1382 
    fn the_chain_shortcut_agrees_with_the_general_order() {
1383 
        let mut g = FileGraph::new();
1384 
        g.insert(
1385 
            h(1),
1386 
            0,
1387 
            Vertex::Start,
1388 
            Vertex::End,
1389 
            &lines(&["a\n", "b\n", "c\n"]),
1390 
        );
1391 
        assert!(g.as_chain().is_some());
1392 
        assert_eq!(g.materialize(&NoDeps), g.materialize_general(&NoDeps));
1393 
        // Appended after the last line: still a chain.
1394 
        g.insert(
1395 
            h(2),
1396 
            0,
1397 
            Vertex::Atom((h(1), 2)),
1398 
            Vertex::End,
1399 
            &lines(&["d\n"]),
1400 
        );
1401 
        assert!(g.as_chain().is_some());
1402 
        assert_eq!(g.materialize(&NoDeps), g.materialize_general(&NoDeps));
1403 
        // Inserted between two lines: not a chain (a has two successors).
1404 
        g.insert(
1405 
            h(4),
1406 
            0,
1407 
            Vertex::Atom((h(1), 0)),
1408 
            Vertex::Atom((h(1), 1)),
1409 
            &lines(&["x\n"]),
1410 
        );
1411 
        assert!(g.as_chain().is_none());
1412 
        assert_eq!(text(&g, &g.materialize(&NoDeps)), "a\nx\nb\nc\nd\n");
1413 
        // Two inserts at one anchor: a conflict, never a chain.
1414 
        let mut c = FileGraph::new();
1415 
        c.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n"]));
1416 
        c.insert(h(2), 0, Vertex::Start, Vertex::End, &lines(&["b\n"]));
1417 
        assert!(c.as_chain().is_none());
1418 
        assert!(c.materialize(&NoDeps).is_conflicted());
1419 
        // A deletion: not a chain.
1420 
        let mut d = FileGraph::new();
1421 
        d.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
1422 
        d.delete(
1423 
            h(3),
1424 
            &AtomRange {
1425 
                change: h(1),
1426 
                from: 0,
1427 
                to: 1,
1428 
            },
1429 
        );
1430 
        assert!(d.as_chain().is_none());
1431 
        assert_eq!(d.materialize(&NoDeps), d.materialize_general(&NoDeps));
1432 
        // Empty.
1433 
        let e = FileGraph::new();
1434 
        assert_eq!(e.materialize(&NoDeps), e.materialize_general(&NoDeps));
1435 
    }
1436
1437 
    #[test]
1438 
    fn sequential_inserts_and_deletes() {
1439 
        let mut g = FileGraph::new();
1440 
        g.insert(
1441 
            h(1),
1442 
            0,
1443 
            Vertex::Start,
1444 
            Vertex::End,
1445 
            &lines(&["a\n", "b\n", "c\n"]),
1446 
        );
1447 
        let m = g.materialize(&NoDeps);
1448 
        assert!(!m.is_conflicted());
1449 
        assert_eq!(text(&g, &m), "a\nb\nc\n");
1450
1451 
        // Change 2 depends on 1, inserts between b and c and deletes a.
1452 
        g.insert(
1453 
            h(2),
1454 
            0,
1455 
            Vertex::Atom((h(1), 1)),
1456 
            Vertex::Atom((h(1), 2)),
1457 
            &lines(&["x\n"]),
1458 
        );
1459 
        g.delete(
1460 
            h(2),
1461 
            &AtomRange {
1462 
                change: h(1),
1463 
                from: 0,
1464 
                to: 1,
1465 
            },
1466 
        );
1467 
        let deps = Deps([(h(2), vec![h(1)])].into_iter().collect());
1468 
        let m = g.materialize(&deps);
1469 
        assert!(!m.is_conflicted());
1470 
        assert_eq!(text(&g, &m), "b\nx\nc\n");
1471 
        assert_eq!(m.live_atoms(), vec![(h(1), 1), (h(2), 0), (h(1), 2)]);
1472 
    }
1473
1474 
    #[test]
1475 
    fn concurrent_inserts_at_same_anchor_conflict() {
1476 
        let mut g = FileGraph::new();
1477 
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
1478 
        g.insert(
1479 
            h(2),
1480 
            0,
1481 
            Vertex::Atom((h(1), 0)),
1482 
            Vertex::Atom((h(1), 1)),
1483 
            &lines(&["from-2\n"]),
1484 
        );
1485 
        g.insert(
1486 
            h(3),
1487 
            0,
1488 
            Vertex::Atom((h(1), 0)),
1489 
            Vertex::Atom((h(1), 1)),
1490 
            &lines(&["from-3\n", "more-3\n"]),
1491 
        );
1492 
        let deps = Deps(
1493 
            [(h(2), vec![h(1)]), (h(3), vec![h(1)])]
1494 
                .into_iter()
1495 
                .collect(),
1496 
        );
1497 
        let m = g.materialize(&deps);
1498 
        assert!(m.is_conflicted());
1499 
        assert_eq!(m.conflict_count(), 1);
1500 
        assert_eq!(
1501 
            m.segments,
1502 
            vec![
1503 
                Segment::Lines(vec![(h(1), 0)]),
1504 
                Segment::Conflict(vec![vec![(h(2), 0)], vec![(h(3), 0), (h(3), 1)]]),
1505 
                Segment::Lines(vec![(h(1), 1)]),
1506 
            ]
1507 
        );
1508 
        let t = text(&g, &m);
1509 
        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}");
1510 
    }
1511
1512 
    #[test]
1513 
    fn concurrent_inserts_at_different_anchors_do_not_conflict() {
1514 
        let mut g = FileGraph::new();
1515 
        g.insert(
1516 
            h(1),
1517 
            0,
1518 
            Vertex::Start,
1519 
            Vertex::End,
1520 
            &lines(&["a\n", "b\n", "c\n"]),
1521 
        );
1522 
        g.insert(
1523 
            h(2),
1524 
            0,
1525 
            Vertex::Start,
1526 
            Vertex::Atom((h(1), 0)),
1527 
            &lines(&["top\n"]),
1528 
        );
1529 
        g.insert(
1530 
            h(3),
1531 
            0,
1532 
            Vertex::Atom((h(1), 2)),
1533 
            Vertex::End,
1534 
            &lines(&["bottom\n"]),
1535 
        );
1536 
        let deps = Deps(
1537 
            [(h(2), vec![h(1)]), (h(3), vec![h(1)])]
1538 
                .into_iter()
1539 
                .collect(),
1540 
        );
1541 
        let m = g.materialize(&deps);
1542 
        assert!(!m.is_conflicted());
1543 
        assert_eq!(text(&g, &m), "top\na\nb\nc\nbottom\n");
1544 
    }
1545
1546 
    #[test]
1547 
    fn concurrent_deletes_of_the_same_line_agree() {
1548 
        let mut g = FileGraph::new();
1549 
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
1550 
        g.delete(
1551 
            h(2),
1552 
            &AtomRange {
1553 
                change: h(1),
1554 
                from: 0,
1555 
                to: 1,
1556 
            },
1557 
        );
1558 
        g.delete(
1559 
            h(3),
1560 
            &AtomRange {
1561 
                change: h(1),
1562 
                from: 0,
1563 
                to: 1,
1564 
            },
1565 
        );
1566 
        let deps = Deps(
1567 
            [(h(2), vec![h(1)]), (h(3), vec![h(1)])]
1568 
                .into_iter()
1569 
                .collect(),
1570 
        );
1571 
        let m = g.materialize(&deps);
1572 
        assert!(!m.is_conflicted());
1573 
        assert_eq!(text(&g, &m), "b\n");
1574 
    }
1575
1576 
    #[test]
1577 
    fn delete_insert_conflict_is_a_zombie() {
1578 
        let mut g = FileGraph::new();
1579 
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
1580 
        // 2 deletes a; 3 (concurrent) inserts after a.
1581 
        g.delete(
1582 
            h(2),
1583 
            &AtomRange {
1584 
                change: h(1),
1585 
                from: 0,
1586 
                to: 1,
1587 
            },
1588 
        );
1589 
        g.insert(
1590 
            h(3),
1591 
            0,
1592 
            Vertex::Atom((h(1), 0)),
1593 
            Vertex::Atom((h(1), 1)),
1594 
            &lines(&["after-a\n"]),
1595 
        );
1596 
        let deps = Deps(
1597 
            [(h(2), vec![h(1)]), (h(3), vec![h(1)])]
1598 
                .into_iter()
1599 
                .collect(),
1600 
        );
1601 
        let m = g.materialize(&deps);
1602 
        assert!(m.is_conflicted());
1603 
        assert_eq!(
1604 
            m.segments,
1605 
            vec![
1606 
                Segment::Zombie {
1607 
                    deleted: vec![(h(1), 0)],
1608 
                    inserted: vec![(h(3), 0)]
1609 
                },
1610 
                Segment::Lines(vec![(h(1), 1)]),
1611 
            ]
1612 
        );
1613 
        let t = text(&g, &m);
1614 
        assert!(t.contains("-------\na\n======="), "{t}");
1615 
        assert!(t.contains("after-a\n>>>>>>>"), "{t}");
1616
1617 
        // If the deleter saw the insert (depends on 3), there is no conflict.
1618 
        let deps = Deps(
1619 
            [(h(2), vec![h(1), h(3)]), (h(3), vec![h(1)])]
1620 
                .into_iter()
1621 
                .collect(),
1622 
        );
1623 
        let m = g.materialize(&deps);
1624 
        assert!(!m.is_conflicted());
1625 
        assert_eq!(text(&g, &m), "after-a\nb\n");
1626 
    }
1627
1628 
    #[test]
1629 
    fn insert_after_a_line_deleted_by_a_dependency_is_not_a_conflict() {
1630 
        // 1 inserts a,b; 2 deletes b (depends on 1); 3 depends on 2 yet anchors
1631 
        // after the dead b (a rewritten change may do this): no conflict.
1632 
        let mut g = FileGraph::new();
1633 
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
1634 
        g.delete(
1635 
            h(2),
1636 
            &AtomRange {
1637 
                change: h(1),
1638 
                from: 1,
1639 
                to: 2,
1640 
            },
1641 
        );
1642 
        g.insert(
1643 
            h(3),
1644 
            0,
1645 
            Vertex::Atom((h(1), 1)),
1646 
            Vertex::End,
1647 
            &lines(&["c\n"]),
1648 
        );
1649 
        let deps = Deps(
1650 
            [(h(2), vec![h(1)]), (h(3), vec![h(2)])]
1651 
                .into_iter()
1652 
                .collect(),
1653 
        );
1654 
        let m = g.materialize(&deps);
1655 
        assert!(!m.is_conflicted(), "{:?}", m.segments);
1656 
        assert_eq!(text(&g, &m), "a\nc\n");
1657 
        // A change that deletes a line it introduced itself, with a dependent
1658 
        // anchoring after it, is likewise fine.
1659 
        let mut g = FileGraph::new();
1660 
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["x\n"]));
1661 
        g.delete(
1662 
            h(1),
1663 
            &AtomRange {
1664 
                change: h(1),
1665 
                from: 0,
1666 
                to: 1,
1667 
            },
1668 
        );
1669 
        g.insert(
1670 
            h(2),
1671 
            0,
1672 
            Vertex::Atom((h(1), 0)),
1673 
            Vertex::End,
1674 
            &lines(&["y\n"]),
1675 
        );
1676 
        let deps = Deps([(h(2), vec![h(1)])].into_iter().collect());
1677 
        let m = g.materialize(&deps);
1678 
        assert!(!m.is_conflicted());
1679 
        assert_eq!(text(&g, &m), "y\n");
1680 
    }
1681
1682 
    #[test]
1683 
    fn resolution_collapses_a_conflict() {
1684 
        let mut g = FileGraph::new();
1685 
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n"]));
1686 
        g.insert(
1687 
            h(2),
1688 
            0,
1689 
            Vertex::Start,
1690 
            Vertex::Atom((h(1), 0)),
1691 
            &lines(&["x\n"]),
1692 
        );
1693 
        g.insert(
1694 
            h(3),
1695 
            0,
1696 
            Vertex::Start,
1697 
            Vertex::Atom((h(1), 0)),
1698 
            &lines(&["y\n"]),
1699 
        );
1700 
        let mut deps: HashMap<_, _> = [(h(2), vec![h(1)]), (h(3), vec![h(1)])]
1701 
            .into_iter()
1702 
            .collect();
1703 
        assert!(g.materialize(&Deps(deps.clone())).is_conflicted());
1704 
        // Resolution keeps y, drops x.
1705 
        g.delete(
1706 
            h(4),
1707 
            &AtomRange {
1708 
                change: h(2),
1709 
                from: 0,
1710 
                to: 1,
1711 
            },
1712 
        );
1713 
        deps.insert(h(4), vec![h(2), h(3)]);
1714 
        let m = g.materialize(&Deps(deps));
1715 
        assert!(!m.is_conflicted());
1716 
        assert_eq!(text(&g, &m), "y\na\n");
1717 
    }
1718
1719 
    #[test]
1720 
    fn empty_and_unterminated_files() {
1721 
        let g = FileGraph::new();
1722 
        let m = g.materialize(&NoDeps);
1723 
        assert_eq!(m.segments, vec![]);
1724 
        assert_eq!(text(&g, &m), "");
1725 
        let mut g = FileGraph::new();
1726 
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["no newline"]));
1727 
        assert_eq!(text(&g, &g.materialize(&NoDeps)), "no newline");
1728 
    }
1729
1730 
    #[test]
1731 
    fn serialization_round_trip() {
1732 
        let mut g = FileGraph::new();
1733 
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
1734 
        g.insert(
1735 
            h(2),
1736 
            0,
1737 
            Vertex::Atom((h(1), 0)),
1738 
            Vertex::Atom((h(1), 1)),
1739 
            &lines(&["x\n"]),
1740 
        );
1741 
        g.delete(
1742 
            h(3),
1743 
            &AtomRange {
1744 
                change: h(1),
1745 
                from: 1,
1746 
                to: 2,
1747 
            },
1748 
        );
1749 
        let v = g.to_value();
1750 
        let bytes = crate::cbor::encode(&v);
1751 
        let back = FileGraph::from_value(&crate::cbor::decode(&bytes).unwrap()).unwrap();
1752 
        let deps = Deps(
1753 
            [(h(2), vec![h(1)]), (h(3), vec![h(1)])]
1754 
                .into_iter()
1755 
                .collect(),
1756 
        );
1757 
        assert_eq!(back.materialize(&deps), g.materialize(&deps));
1758 
        assert_eq!(text(&back, &back.materialize(&deps)), "a\nx\n");
1759 
        assert_eq!(
1760 
            crate::cbor::encode(&back.to_value()),
1761 
            bytes,
1762 
            "deterministic"
1763 
        );
1764 
    }
1765
1766 
    /// Spec §7.3: the graph is a function of the set of changes, not their order.
1767 
    #[test]
1768 
    fn application_order_is_irrelevant() {
1769 
        use rand::seq::SliceRandom;
1770 
        type Op = (
1771 
            ChangeHash,
1772 
            Vec<(u32, Vertex, Vertex, Lines)>,
1773 
            Vec<AtomRange>,
1774 
        );
1775 
        let ops: Vec<Op> = vec![
1776 
            (
1777 
                h(1),
1778 
                vec![(0, Vertex::Start, Vertex::End, lines(&["a\n", "b\n", "c\n"]))],
1779 
                vec![],
1780 
            ),
1781 
            (
1782 
                h(2),
1783 
                vec![(
1784 
                    0,
1785 
                    Vertex::Atom((h(1), 0)),
1786 
                    Vertex::Atom((h(1), 1)),
1787 
                    lines(&["p\n"]),
1788 
                )],
1789 
                vec![],
1790 
            ),
1791 
            (
1792 
                h(3),
1793 
                vec![(
1794 
                    0,
1795 
                    Vertex::Atom((h(1), 0)),
1796 
                    Vertex::Atom((h(1), 1)),
1797 
                    lines(&["q\n", "r\n"]),
1798 
                )],
1799 
                vec![AtomRange {
1800 
                    change: h(1),
1801 
                    from: 2,
1802 
                    to: 3,
1803 
                }],
1804 
            ),
1805 
            (
1806 
                h(4),
1807 
                vec![(
1808 
                    0,
1809 
                    Vertex::Atom((h(3), 1)),
1810 
                    Vertex::Atom((h(1), 1)),
1811 
                    lines(&["s\n"]),
1812 
                )],
1813 
                vec![AtomRange {
1814 
                    change: h(1),
1815 
                    from: 1,
1816 
                    to: 2,
1817 
                }],
1818 
            ),
1819 
            (
1820 
                h(5),
1821 
                vec![(0, Vertex::Atom((h(1), 2)), Vertex::End, lines(&["z\n"]))],
1822 
                vec![],
1823 
            ),
1824 
        ];
1825 
        let deps = Deps(
1826 
            [
1827 
                (h(2), vec![h(1)]),
1828 
                (h(3), vec![h(1)]),
1829 
                (h(4), vec![h(3), h(1)]),
1830 
                (h(5), vec![h(1)]),
1831 
            ]
1832 
            .into_iter()
1833 
            .collect(),
1834 
        );
1835 
        let build = |order: &[usize]| {
1836 
            let mut g = FileGraph::new();
1837 
            for &i in order {
1838 
                let (c, ins, dels) = &ops[i];
1839 
                for (idx, a, b, l) in ins {
1840 
                    g.insert(*c, *idx, *a, *b, l);
1841 
                }
1842 
                for d in dels {
1843 
                    g.delete(*c, d);
1844 
                }
1845 
            }
1846 
            let m = g.materialize(&deps);
1847 
            (m.clone(), text(&g, &m))
1848 
        };
1849 
        let reference = build(&[0, 1, 2, 3, 4]);
1850 
        assert!(reference.0.is_conflicted());
1851 
        let mut rng = rand::thread_rng();
1852 
        let mut order: Vec<usize> = (0..ops.len()).collect();
1853 
        for _ in 0..50 {
1854 
            order.shuffle(&mut rng);
1855 
            assert_eq!(build(&order), reference, "order {order:?}");
1856 
        }
1857 
    }
1858 
}