OXYGENHUB
# d14d78326300 oxygen / crates / oxy-core / src / graph.rs
33.2 KiB · Rust · last changed Unbound hosted repositories adopt the first pusher's id 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::hash::ChangeHash;
8 
use crate::objects::AtomRange;
9 
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
10
11 
/// `(introducing change, index within that change for this node)`.
12 
pub type AtomKey = (ChangeHash, u32);
13
14 
#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
15 
pub enum Vertex {
16 
    Start,
17 
    Atom(AtomKey),
18 
    End,
19 
}
20
21 
/// Transitive dependency test between changes; `depends_on(a, a)` is true.
22 
pub trait DepOracle {
23 
    fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool;
24 
}
25
26 
/// No change depends on any other: every pair commutes.
27 
pub struct NoDeps;
28 
impl DepOracle for NoDeps {
29 
    fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool {
30 
        a == b
31 
    }
32 
}
33
34 
#[derive(Default, Clone, Debug)]
35 
struct AtomInfo {
36 
    /// `None` until the introducing change has been applied.
37 
    content: Option<Vec<u8>>,
38 
    deleted_by: BTreeSet<ChangeHash>,
39 
}
40
41 
#[derive(Clone, Debug)]
42 
pub struct FileGraph {
43 
    atoms: HashMap<AtomKey, AtomInfo>,
44 
    succ: HashMap<Vertex, BTreeSet<Vertex>>,
45 
    pred: HashMap<Vertex, BTreeSet<Vertex>>,
46 
}
47
48 
impl Default for FileGraph {
49 
    fn default() -> Self {
50 
        Self::new()
51 
    }
52 
}
53
54 
/// One piece of a materialized file.
55 
#[derive(Clone, Debug, PartialEq, Eq)]
56 
pub enum Segment {
57 
    Lines(Vec<AtomKey>),
58 
    /// Order conflict: alternatives that cannot be ordered against each other.
59 
    Conflict(Vec<Vec<AtomKey>>),
60 
    /// Delete/insert conflict: `inserted` was anchored to `deleted` by a change
61 
    /// that commutes with the deletion.
62 
    Zombie {
63 
        deleted: Vec<AtomKey>,
64 
        inserted: Vec<AtomKey>,
65 
    },
66 
}
67
68 
#[derive(Clone, Debug, PartialEq, Eq, Default)]
69 
pub struct Materialized {
70 
    pub segments: Vec<Segment>,
71 
}
72
73 
impl Materialized {
74 
    pub fn is_conflicted(&self) -> bool {
75 
        self.segments
76 
            .iter()
77 
            .any(|s| !matches!(s, Segment::Lines(_)))
78 
    }
79 
    pub fn conflict_count(&self) -> usize {
80 
        self.segments
81 
            .iter()
82 
            .filter(|s| !matches!(s, Segment::Lines(_)))
83 
            .count()
84 
    }
85 
    /// Every live atom in materialized order, conflict sides concatenated.
86 
    pub fn live_atoms(&self) -> Vec<AtomKey> {
87 
        let mut out = Vec::new();
88 
        for s in &self.segments {
89 
            match s {
90 
                Segment::Lines(a) => out.extend(a),
91 
                Segment::Conflict(sides) => sides.iter().for_each(|x| out.extend(x)),
92 
                Segment::Zombie { inserted, .. } => out.extend(inserted),
93 
            }
94 
        }
95 
        out
96 
    }
97 
}
98
99 
impl FileGraph {
100 
    pub fn new() -> Self {
101 
        let mut g = FileGraph {
102 
            atoms: HashMap::new(),
103 
            succ: HashMap::new(),
104 
            pred: HashMap::new(),
105 
        };
106 
        g.edge(Vertex::Start, Vertex::End);
107 
        g
108 
    }
109
110 
    fn edge(&mut self, a: Vertex, b: Vertex) {
111 
        self.succ.entry(a).or_default().insert(b);
112 
        self.pred.entry(b).or_default().insert(a);
113 
        self.succ.entry(b).or_default();
114 
        self.pred.entry(a).or_default();
115 
    }
116
117 
    /// Apply an `Insert` by `change` whose first new atom has index `first_index`.
118 
    pub fn insert(
119 
        &mut self,
120 
        change: ChangeHash,
121 
        first_index: u32,
122 
        after: Vertex,
123 
        before: Vertex,
124 
        lines: &[Vec<u8>],
125 
    ) {
126 
        let mut prev = after;
127 
        for (i, line) in lines.iter().enumerate() {
128 
            let key = (change, first_index + i as u32);
129 
            self.atoms.entry(key).or_default().content = Some(line.clone());
130 
            let v = Vertex::Atom(key);
131 
            self.edge(prev, v);
132 
            prev = v;
133 
        }
134 
        self.edge(prev, before);
135 
    }
136
137 
    /// Apply a `Delete` of `range` by change `by`.
138 
    pub fn delete(&mut self, by: ChangeHash, range: &AtomRange) {
139 
        for i in range.from..range.to {
140 
            self.atoms
141 
                .entry((range.change, i))
142 
                .or_default()
143 
                .deleted_by
144 
                .insert(by);
145 
        }
146 
    }
147
148 
    pub fn is_live(&self, k: &AtomKey) -> bool {
149 
        self.atoms
150 
            .get(k)
151 
            .is_some_and(|a| a.content.is_some() && a.deleted_by.is_empty())
152 
    }
153
154 
    pub fn content(&self, k: &AtomKey) -> Option<&[u8]> {
155 
        self.atoms.get(k).and_then(|a| a.content.as_deref())
156 
    }
157
158 
    pub fn deleters(&self, k: &AtomKey) -> impl Iterator<Item = &ChangeHash> {
159 
        self.atoms
160 
            .get(k)
161 
            .into_iter()
162 
            .flat_map(|a| a.deleted_by.iter())
163 
    }
164
165 
    /// Number of atoms introduced by `change` in this graph (for index bookkeeping).
166 
    pub fn atom_count(&self) -> usize {
167 
        self.atoms.len()
168 
    }
169
170 
    fn is_ghost(&self, k: &AtomKey, info: &AtomInfo, deps: &dyn DepOracle) -> bool {
171 
        // A deleted atom is a ghost when a live direct successor was inserted
172 
        // by a change that commutes with every deleter: neither depends on
173 
        // the other (spec §9.1, delete/insert). If the inserter came after the
174 
        // deletion, or the deleter saw the insertion, there is no conflict.
175 
        self.succ.get(&Vertex::Atom(*k)).is_some_and(|ss| {
176 
            ss.iter().any(|s| match s {
177 
                Vertex::Atom(y) if self.is_live(y) => !info
178 
                    .deleted_by
179 
                    .iter()
180 
                    .any(|d| deps.depends_on(d, &y.0) || deps.depends_on(&y.0, d)),
181 
                _ => false,
182 
            })
183 
        })
184 
    }
185
186 
    /// Successors of `v` in the graph with non-kept vertices contracted away.
187 
    fn reduced_succ(
188 
        &self,
189 
        v: Vertex,
190 
        kept: &HashSet<Vertex>,
191 
        memo: &mut HashMap<Vertex, BTreeSet<Vertex>>,
192 
    ) -> BTreeSet<Vertex> {
193 
        let mut out = BTreeSet::new();
194 
        let mut stack: Vec<Vertex> = self
195 
            .succ
196 
            .get(&v)
197 
            .map(|s| s.iter().copied().collect())
198 
            .unwrap_or_default();
199 
        let mut seen = HashSet::new();
200 
        while let Some(s) = stack.pop() {
201 
            if kept.contains(&s) {
202 
                out.insert(s);
203 
            } else if seen.insert(s) {
204 
                if let Some(m) = memo.get(&s) {
205 
                    out.extend(m.iter().copied());
206 
                } else if let Some(next) = self.succ.get(&s) {
207 
                    stack.extend(next.iter().copied());
208 
                }
209 
            }
210 
        }
211 
        out
212 
    }
213
214 
    /// Order the live atoms and locate conflicts.
215 
    pub fn materialize(&self, deps: &dyn DepOracle) -> Materialized {
216 
        // 1. Vertices that survive contraction: live atoms, ghosts, Start, End.
217 
        let mut kept: HashSet<Vertex> = HashSet::new();
218 
        let mut ghosts: HashSet<AtomKey> = HashSet::new();
219 
        kept.insert(Vertex::Start);
220 
        kept.insert(Vertex::End);
221 
        for (k, info) in &self.atoms {
222 
            if info.content.is_none() {
223 
                continue;
224 
            }
225 
            if info.deleted_by.is_empty() {
226 
                kept.insert(Vertex::Atom(*k));
227 
            } else if self.is_ghost(k, info, deps) {
228 
                kept.insert(Vertex::Atom(*k));
229 
                ghosts.insert(*k);
230 
            }
231 
        }
232
233 
        // 2. Reduced graph over kept vertices.
234 
        let mut memo = HashMap::new();
235 
        let mut rsucc: HashMap<Vertex, BTreeSet<Vertex>> = HashMap::new();
236 
        let mut indeg: HashMap<Vertex, usize> = HashMap::new();
237 
        for &u in &kept {
238 
            indeg.entry(u).or_insert(0);
239 
            let rs = self.reduced_succ(u, &kept, &mut memo);
240 
            for &w in &rs {
241 
                *indeg.entry(w).or_insert(0) += 1;
242 
            }
243 
            rsucc.insert(u, rs);
244 
        }
245
246 
        // 3. Kahn's algorithm with side labelling for conflict regions.
247 
        let mut ready: BTreeSet<Vertex> = indeg
248 
            .iter()
249 
            .filter(|(_, &d)| d == 0)
250 
            .map(|(v, _)| *v)
251 
            .collect();
252 
        let mut side: HashMap<Vertex, u32> = HashMap::new();
253 
        let mut joins: HashSet<Vertex> = HashSet::new();
254 
        let mut next_side = 0u32;
255 
        let mut plain: Vec<Vertex> = Vec::new();
256 
        let mut conflict: Option<BTreeMap<u32, Vec<Vertex>>> = None;
257 
        let mut segments: Vec<Segment> = Vec::new();
258
259 
        let flush_plain = |plain: &mut Vec<Vertex>, segments: &mut Vec<Segment>| {
260 
            let atoms: Vec<AtomKey> = plain
261 
                .iter()
262 
                .filter_map(|v| {
263 
                    if let Vertex::Atom(k) = v {
264 
                        Some(*k)
265 
                    } else {
266 
                        None
267 
                    }
268 
                })
269 
                .collect();
270 
            plain.clear();
271 
            if !atoms.is_empty() {
272 
                segments.extend(split_zombies(atoms, &ghosts));
273 
            }
274 
        };
275 
        let finish_conflict = |c: BTreeMap<u32, Vec<Vertex>>, segments: &mut Vec<Segment>| {
276 
            let sides: Vec<Vec<AtomKey>> = c
277 
                .into_values()
278 
                .map(|vs| {
279 
                    vs.into_iter()
280 
                        .filter_map(|v| match v {
281 
                            Vertex::Atom(k) if !ghosts.contains(&k) => Some(k),
282 
                            _ => None,
283 
                        })
284 
                        .collect::<Vec<_>>()
285 
                })
286 
                .filter(|s| !s.is_empty())
287 
                .collect();
288 
            match sides.len() {
289 
                0 => {}
290 
                1 => segments.push(Segment::Lines(sides.into_iter().next().unwrap())),
291 
                _ => segments.push(Segment::Conflict(sides)),
292 
            }
293 
        };
294
295 
        while !ready.is_empty() {
296 
            if ready.len() >= 2 {
297 
                if conflict.is_none() {
298 
                    flush_plain(&mut plain, &mut segments);
299 
                    conflict = Some(BTreeMap::new());
300 
                }
301 
                for r in &ready {
302 
                    if !side.contains_key(r) {
303 
                        side.insert(*r, next_side);
304 
                        next_side += 1;
305 
                    }
306 
                }
307 
            }
308 
            let v = ready.pop_first().unwrap();
309 
            let my_side = side.get(&v).copied();
310 
            match (&mut conflict, my_side) {
311 
                (Some(c), Some(s)) => c.entry(s).or_default().push(v),
312 
                (Some(_), None) => {
313 
                    let c = conflict.take().unwrap();
314 
                    finish_conflict(c, &mut segments);
315 
                    plain.push(v);
316 
                }
317 
                (None, _) => plain.push(v),
318 
            }
319 
            for &w in &rsucc[&v] {
320 
                let d = indeg.get_mut(&w).unwrap();
321 
                *d -= 1;
322 
                if conflict.is_some() && !joins.contains(&w) {
323 
                    match (my_side, side.get(&w).copied()) {
324 
                        (Some(s), None) => {
325 
                            side.insert(w, s);
326 
                        }
327 
                        (Some(s), Some(t)) if s != t => {
328 
                            side.remove(&w);
329 
                            joins.insert(w);
330 
                        }
331 
                        (None, Some(_)) => {
332 
                            side.remove(&w);
333 
                            joins.insert(w);
334 
                        }
335 
                        _ => {}
336 
                    }
337 
                }
338 
                if *d == 0 {
339 
                    ready.insert(w);
340 
                }
341 
            }
342 
        }
343 
        if let Some(c) = conflict.take() {
344 
            finish_conflict(c, &mut segments);
345 
        }
346 
        flush_plain(&mut plain, &mut segments);
347 
        Materialized { segments }
348 
    }
349
350 
    /// Render a materialization to bytes with conflict markers (spec §9.5).
351 
    /// `label` gives the short description of a change for marker headers.
352 
    pub fn render(&self, m: &Materialized, label: &dyn Fn(&ChangeHash) -> String) -> Vec<u8> {
353 
        let total = m.conflict_count();
354 
        let mut n = 0;
355 
        let mut out: Vec<u8> = Vec::new();
356 
        let push_atoms = |out: &mut Vec<u8>, atoms: &[AtomKey]| {
357 
            for a in atoms {
358 
                if let Some(c) = self.content(a) {
359 
                    out.extend_from_slice(c);
360 
                }
361 
            }
362 
        };
363 
        let newline_if_needed = |out: &mut Vec<u8>| {
364 
            if !out.is_empty() && *out.last().unwrap() != b'\n' {
365 
                out.push(b'\n');
366 
            }
367 
        };
368 
        for seg in &m.segments {
369 
            match seg {
370 
                Segment::Lines(a) => push_atoms(&mut out, a),
371 
                Segment::Conflict(sides) => {
372 
                    n += 1;
373 
                    let k = sides.len();
374 
                    for (i, s) in sides.iter().enumerate() {
375 
                        newline_if_needed(&mut out);
376 
                        let who = s.first().map(|a| label(&a.0)).unwrap_or_default();
377 
                        let marker = if i == 0 { "<<<<<<<" } else { "=======" };
378 
                        out.extend_from_slice(
379 
                            format!("{marker} oxy conflict {n} of {total}, side {} of {k}: change {who}\n", i + 1).as_bytes(),
380 
                        );
381 
                        push_atoms(&mut out, s);
382 
                    }
383 
                    newline_if_needed(&mut out);
384 
                    out.extend_from_slice(
385 
                        format!(">>>>>>> oxy conflict {n} of {total} end\n").as_bytes(),
386 
                    );
387 
                }
388 
                Segment::Zombie { deleted, inserted } => {
389 
                    n += 1;
390 
                    newline_if_needed(&mut out);
391 
                    let deleter = deleted
392 
                        .first()
393 
                        .and_then(|a| self.deleters(a).next().copied())
394 
                        .map(|d| label(&d))
395 
                        .unwrap_or_default();
396 
                    let inserter = inserted.first().map(|a| label(&a.0)).unwrap_or_default();
397 
                    out.extend_from_slice(
398 
                        format!("<<<<<<< oxy conflict {n} of {total}, side 1 of 2: deleted by change {deleter}\n-------\n").as_bytes(),
399 
                    );
400 
                    push_atoms(&mut out, deleted);
401 
                    newline_if_needed(&mut out);
402 
                    out.extend_from_slice(
403 
                        format!(
404 
                            "======= oxy conflict {n} of {total}, side 2 of 2: change {inserter}\n"
405 
                        )
406 
                        .as_bytes(),
407 
                    );
408 
                    push_atoms(&mut out, inserted);
409 
                    newline_if_needed(&mut out);
410 
                    out.extend_from_slice(
411 
                        format!(">>>>>>> oxy conflict {n} of {total} end\n").as_bytes(),
412 
                    );
413 
                }
414 
            }
415 
        }
416 
        out
417 
    }
418 
}
419
420 
fn vertex_value(v: &Vertex) -> crate::cbor::Value {
421 
    use crate::cbor::Value;
422 
    match v {
423 
        Vertex::Start => Value::Uint(0),
424 
        Vertex::End => Value::Uint(1),
425 
        Vertex::Atom((c, i)) => {
426 
            Value::Array(vec![Value::Bytes(c.0.to_vec()), Value::Uint(*i as u64)])
427 
        }
428 
    }
429 
}
430
431 
fn vertex_from(v: &crate::cbor::Value) -> Result<Vertex, crate::objects::ObjectError> {
432 
    use crate::cbor::Value;
433 
    use crate::objects::ObjectError;
434 
    match v {
435 
        Value::Uint(0) => Ok(Vertex::Start),
436 
        Value::Uint(1) => Ok(Vertex::End),
437 
        Value::Array(a) if a.len() == 2 => Ok(Vertex::Atom((
438 
            crate::objects::oref(&a[0], "vertex")?,
439 
            crate::objects::u32_(&a[1], "vertex")?,
440 
        ))),
441 
        _ => Err(ObjectError::Schema(
442 
            "vertex: expected 0, 1, or [hash, index]".into(),
443 
        )),
444 
    }
445 
}
446
447 
impl FileGraph {
448 
    /// Serialize for a checkpoint: `{0: atoms [[hash, index, content|null, [deleters]]], 1: edges [[from, to]]}`.
449 
    pub fn to_value(&self) -> crate::cbor::Value {
450 
        use crate::cbor::Value;
451 
        let mut atoms: Vec<(&AtomKey, &AtomInfo)> = self.atoms.iter().collect();
452 
        atoms.sort_by_key(|(k, _)| **k);
453 
        let mut edges: Vec<(Vertex, Vertex)> = self
454 
            .succ
455 
            .iter()
456 
            .flat_map(|(a, bs)| bs.iter().map(move |b| (*a, *b)))
457 
            .collect();
458 
        edges.sort();
459 
        Value::map([
460 
            (
461 
                0,
462 
                Value::Array(
463 
                    atoms
464 
                        .into_iter()
465 
                        .map(|((c, i), info)| {
466 
                            Value::Array(vec![
467 
                                Value::Bytes(c.0.to_vec()),
468 
                                Value::Uint(*i as u64),
469 
                                info.content
470 
                                    .as_ref()
471 
                                    .map(|b| Value::Bytes(b.clone()))
472 
                                    .unwrap_or(Value::Null),
473 
                                Value::Array(
474 
                                    info.deleted_by
475 
                                        .iter()
476 
                                        .map(|d| Value::Bytes(d.0.to_vec()))
477 
                                        .collect(),
478 
                                ),
479 
                            ])
480 
                        })
481 
                        .collect(),
482 
                ),
483 
            ),
484 
            (
485 
                1,
486 
                Value::Array(
487 
                    edges
488 
                        .iter()
489 
                        .map(|(a, b)| Value::Array(vec![vertex_value(a), vertex_value(b)]))
490 
                        .collect(),
491 
                ),
492 
            ),
493 
        ])
494 
    }
495
496 
    pub fn from_value(v: &crate::cbor::Value) -> Result<FileGraph, crate::objects::ObjectError> {
497 
        use crate::objects::{array, bytes, field, map, oref, u32_, ObjectError};
498 
        let m = map(v, "file graph")?;
499 
        let mut g = FileGraph {
500 
            atoms: HashMap::new(),
501 
            succ: HashMap::new(),
502 
            pred: HashMap::new(),
503 
        };
504 
        for a in array(field(m, 0, "atoms")?, "atoms")? {
505 
            let e = array(a, "atom")?;
506 
            if e.len() != 4 {
507 
                return Err(ObjectError::Schema("atom: expected 4 fields".into()));
508 
            }
509 
            let key = (oref(&e[0], "atom change")?, u32_(&e[1], "atom index")?);
510 
            let content = if e[2].is_null() {
511 
                None
512 
            } else {
513 
                Some(bytes(&e[2], "atom content")?.to_vec())
514 
            };
515 
            let deleted_by = array(&e[3], "deleters")?
516 
                .iter()
517 
                .map(|d| oref(d, "deleter"))
518 
                .collect::<Result<BTreeSet<_>, _>>()?;
519 
            g.atoms.insert(
520 
                key,
521 
                AtomInfo {
522 
                    content,
523 
                    deleted_by,
524 
                },
525 
            );
526 
        }
527 
        for e in array(field(m, 1, "edges")?, "edges")? {
528 
            let pair = array(e, "edge")?;
529 
            if pair.len() != 2 {
530 
                return Err(ObjectError::Schema("edge: expected [from, to]".into()));
531 
            }
532 
            g.edge(vertex_from(&pair[0])?, vertex_from(&pair[1])?);
533 
        }
534 
        Ok(g)
535 
    }
536 
}
537
538 
/// Split a plain run into `Lines` and `Zombie` segments around ghost atoms.
539 
fn split_zombies(atoms: Vec<AtomKey>, ghosts: &HashSet<AtomKey>) -> Vec<Segment> {
540 
    let mut out = Vec::new();
541 
    let mut lines: Vec<AtomKey> = Vec::new();
542 
    let mut i = 0;
543 
    while i < atoms.len() {
544 
        if !ghosts.contains(&atoms[i]) {
545 
            lines.push(atoms[i]);
546 
            i += 1;
547 
            continue;
548 
        }
549 
        if !lines.is_empty() {
550 
            out.push(Segment::Lines(std::mem::take(&mut lines)));
551 
        }
552 
        let mut deleted = Vec::new();
553 
        while i < atoms.len() && ghosts.contains(&atoms[i]) {
554 
            deleted.push(atoms[i]);
555 
            i += 1;
556 
        }
557 
        let mut inserted = Vec::new();
558 
        if i < atoms.len() {
559 
            let ch = atoms[i].0;
560 
            while i < atoms.len() && atoms[i].0 == ch && !ghosts.contains(&atoms[i]) {
561 
                inserted.push(atoms[i]);
562 
                i += 1;
563 
            }
564 
        }
565 
        out.push(Segment::Zombie { deleted, inserted });
566 
    }
567 
    if !lines.is_empty() {
568 
        out.push(Segment::Lines(lines));
569 
    }
570 
    out
571 
}
572
573 
#[cfg(test)]
574 
mod tests {
575 
    use super::*;
576 
    use crate::hash::ObjectRef;
577
578 
    fn h(n: u8) -> ChangeHash {
579 
        ObjectRef([n; 32])
580 
    }
581 
    fn lines(v: &[&str]) -> Vec<Vec<u8>> {
582 
        v.iter().map(|s| s.as_bytes().to_vec()).collect()
583 
    }
584 
    fn text(g: &FileGraph, m: &Materialized) -> String {
585 
        String::from_utf8(g.render(m, &|c| c.short(4))).unwrap()
586 
    }
587
588 
    struct Deps(HashMap<ChangeHash, Vec<ChangeHash>>);
589 
    impl DepOracle for Deps {
590 
        fn depends_on(&self, a: &ChangeHash, b: &ChangeHash) -> bool {
591 
            if a == b {
592 
                return true;
593 
            }
594 
            let mut stack = vec![*a];
595 
            let mut seen = HashSet::new();
596 
            while let Some(x) = stack.pop() {
597 
                if let Some(ds) = self.0.get(&x) {
598 
                    for d in ds {
599 
                        if d == b {
600 
                            return true;
601 
                        }
602 
                        if seen.insert(*d) {
603 
                            stack.push(*d);
604 
                        }
605 
                    }
606 
                }
607 
            }
608 
            false
609 
        }
610 
    }
611
612 
    #[test]
613 
    fn sequential_inserts_and_deletes() {
614 
        let mut g = FileGraph::new();
615 
        g.insert(
616 
            h(1),
617 
            0,
618 
            Vertex::Start,
619 
            Vertex::End,
620 
            &lines(&["a\n", "b\n", "c\n"]),
621 
        );
622 
        let m = g.materialize(&NoDeps);
623 
        assert!(!m.is_conflicted());
624 
        assert_eq!(text(&g, &m), "a\nb\nc\n");
625
626 
        // Change 2 depends on 1, inserts between b and c and deletes a.
627 
        g.insert(
628 
            h(2),
629 
            0,
630 
            Vertex::Atom((h(1), 1)),
631 
            Vertex::Atom((h(1), 2)),
632 
            &lines(&["x\n"]),
633 
        );
634 
        g.delete(
635 
            h(2),
636 
            &AtomRange {
637 
                change: h(1),
638 
                from: 0,
639 
                to: 1,
640 
            },
641 
        );
642 
        let deps = Deps([(h(2), vec![h(1)])].into_iter().collect());
643 
        let m = g.materialize(&deps);
644 
        assert!(!m.is_conflicted());
645 
        assert_eq!(text(&g, &m), "b\nx\nc\n");
646 
        assert_eq!(m.live_atoms(), vec![(h(1), 1), (h(2), 0), (h(1), 2)]);
647 
    }
648
649 
    #[test]
650 
    fn concurrent_inserts_at_same_anchor_conflict() {
651 
        let mut g = FileGraph::new();
652 
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
653 
        g.insert(
654 
            h(2),
655 
            0,
656 
            Vertex::Atom((h(1), 0)),
657 
            Vertex::Atom((h(1), 1)),
658 
            &lines(&["from-2\n"]),
659 
        );
660 
        g.insert(
661 
            h(3),
662 
            0,
663 
            Vertex::Atom((h(1), 0)),
664 
            Vertex::Atom((h(1), 1)),
665 
            &lines(&["from-3\n", "more-3\n"]),
666 
        );
667 
        let deps = Deps(
668 
            [(h(2), vec![h(1)]), (h(3), vec![h(1)])]
669 
                .into_iter()
670 
                .collect(),
671 
        );
672 
        let m = g.materialize(&deps);
673 
        assert!(m.is_conflicted());
674 
        assert_eq!(m.conflict_count(), 1);
675 
        assert_eq!(
676 
            m.segments,
677 
            vec![
678 
                Segment::Lines(vec![(h(1), 0)]),
679 
                Segment::Conflict(vec![vec![(h(2), 0)], vec![(h(3), 0), (h(3), 1)]]),
680 
                Segment::Lines(vec![(h(1), 1)]),
681 
            ]
682 
        );
683 
        let t = text(&g, &m);
684 
        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}");
685 
    }
686
687 
    #[test]
688 
    fn concurrent_inserts_at_different_anchors_do_not_conflict() {
689 
        let mut g = FileGraph::new();
690 
        g.insert(
691 
            h(1),
692 
            0,
693 
            Vertex::Start,
694 
            Vertex::End,
695 
            &lines(&["a\n", "b\n", "c\n"]),
696 
        );
697 
        g.insert(
698 
            h(2),
699 
            0,
700 
            Vertex::Start,
701 
            Vertex::Atom((h(1), 0)),
702 
            &lines(&["top\n"]),
703 
        );
704 
        g.insert(
705 
            h(3),
706 
            0,
707 
            Vertex::Atom((h(1), 2)),
708 
            Vertex::End,
709 
            &lines(&["bottom\n"]),
710 
        );
711 
        let deps = Deps(
712 
            [(h(2), vec![h(1)]), (h(3), vec![h(1)])]
713 
                .into_iter()
714 
                .collect(),
715 
        );
716 
        let m = g.materialize(&deps);
717 
        assert!(!m.is_conflicted());
718 
        assert_eq!(text(&g, &m), "top\na\nb\nc\nbottom\n");
719 
    }
720
721 
    #[test]
722 
    fn concurrent_deletes_of_the_same_line_agree() {
723 
        let mut g = FileGraph::new();
724 
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
725 
        g.delete(
726 
            h(2),
727 
            &AtomRange {
728 
                change: h(1),
729 
                from: 0,
730 
                to: 1,
731 
            },
732 
        );
733 
        g.delete(
734 
            h(3),
735 
            &AtomRange {
736 
                change: h(1),
737 
                from: 0,
738 
                to: 1,
739 
            },
740 
        );
741 
        let deps = Deps(
742 
            [(h(2), vec![h(1)]), (h(3), vec![h(1)])]
743 
                .into_iter()
744 
                .collect(),
745 
        );
746 
        let m = g.materialize(&deps);
747 
        assert!(!m.is_conflicted());
748 
        assert_eq!(text(&g, &m), "b\n");
749 
    }
750
751 
    #[test]
752 
    fn delete_insert_conflict_is_a_zombie() {
753 
        let mut g = FileGraph::new();
754 
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
755 
        // 2 deletes a; 3 (concurrent) inserts after a.
756 
        g.delete(
757 
            h(2),
758 
            &AtomRange {
759 
                change: h(1),
760 
                from: 0,
761 
                to: 1,
762 
            },
763 
        );
764 
        g.insert(
765 
            h(3),
766 
            0,
767 
            Vertex::Atom((h(1), 0)),
768 
            Vertex::Atom((h(1), 1)),
769 
            &lines(&["after-a\n"]),
770 
        );
771 
        let deps = Deps(
772 
            [(h(2), vec![h(1)]), (h(3), vec![h(1)])]
773 
                .into_iter()
774 
                .collect(),
775 
        );
776 
        let m = g.materialize(&deps);
777 
        assert!(m.is_conflicted());
778 
        assert_eq!(
779 
            m.segments,
780 
            vec![
781 
                Segment::Zombie {
782 
                    deleted: vec![(h(1), 0)],
783 
                    inserted: vec![(h(3), 0)]
784 
                },
785 
                Segment::Lines(vec![(h(1), 1)]),
786 
            ]
787 
        );
788 
        let t = text(&g, &m);
789 
        assert!(t.contains("-------\na\n======="), "{t}");
790 
        assert!(t.contains("after-a\n>>>>>>>"), "{t}");
791
792 
        // If the deleter saw the insert (depends on 3), there is no conflict.
793 
        let deps = Deps(
794 
            [(h(2), vec![h(1), h(3)]), (h(3), vec![h(1)])]
795 
                .into_iter()
796 
                .collect(),
797 
        );
798 
        let m = g.materialize(&deps);
799 
        assert!(!m.is_conflicted());
800 
        assert_eq!(text(&g, &m), "after-a\nb\n");
801 
    }
802
803 
    #[test]
804 
    fn insert_after_a_line_deleted_by_a_dependency_is_not_a_conflict() {
805 
        // 1 inserts a,b; 2 deletes b (depends on 1); 3 depends on 2 yet anchors
806 
        // after the dead b (a rewritten change may do this): no conflict.
807 
        let mut g = FileGraph::new();
808 
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
809 
        g.delete(
810 
            h(2),
811 
            &AtomRange {
812 
                change: h(1),
813 
                from: 1,
814 
                to: 2,
815 
            },
816 
        );
817 
        g.insert(
818 
            h(3),
819 
            0,
820 
            Vertex::Atom((h(1), 1)),
821 
            Vertex::End,
822 
            &lines(&["c\n"]),
823 
        );
824 
        let deps = Deps(
825 
            [(h(2), vec![h(1)]), (h(3), vec![h(2)])]
826 
                .into_iter()
827 
                .collect(),
828 
        );
829 
        let m = g.materialize(&deps);
830 
        assert!(!m.is_conflicted(), "{:?}", m.segments);
831 
        assert_eq!(text(&g, &m), "a\nc\n");
832 
        // A change that deletes a line it introduced itself, with a dependent
833 
        // anchoring after it, is likewise fine.
834 
        let mut g = FileGraph::new();
835 
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["x\n"]));
836 
        g.delete(
837 
            h(1),
838 
            &AtomRange {
839 
                change: h(1),
840 
                from: 0,
841 
                to: 1,
842 
            },
843 
        );
844 
        g.insert(
845 
            h(2),
846 
            0,
847 
            Vertex::Atom((h(1), 0)),
848 
            Vertex::End,
849 
            &lines(&["y\n"]),
850 
        );
851 
        let deps = Deps([(h(2), vec![h(1)])].into_iter().collect());
852 
        let m = g.materialize(&deps);
853 
        assert!(!m.is_conflicted());
854 
        assert_eq!(text(&g, &m), "y\n");
855 
    }
856
857 
    #[test]
858 
    fn resolution_collapses_a_conflict() {
859 
        let mut g = FileGraph::new();
860 
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n"]));
861 
        g.insert(
862 
            h(2),
863 
            0,
864 
            Vertex::Start,
865 
            Vertex::Atom((h(1), 0)),
866 
            &lines(&["x\n"]),
867 
        );
868 
        g.insert(
869 
            h(3),
870 
            0,
871 
            Vertex::Start,
872 
            Vertex::Atom((h(1), 0)),
873 
            &lines(&["y\n"]),
874 
        );
875 
        let mut deps: HashMap<_, _> = [(h(2), vec![h(1)]), (h(3), vec![h(1)])]
876 
            .into_iter()
877 
            .collect();
878 
        assert!(g.materialize(&Deps(deps.clone())).is_conflicted());
879 
        // Resolution keeps y, drops x.
880 
        g.delete(
881 
            h(4),
882 
            &AtomRange {
883 
                change: h(2),
884 
                from: 0,
885 
                to: 1,
886 
            },
887 
        );
888 
        deps.insert(h(4), vec![h(2), h(3)]);
889 
        let m = g.materialize(&Deps(deps));
890 
        assert!(!m.is_conflicted());
891 
        assert_eq!(text(&g, &m), "y\na\n");
892 
    }
893
894 
    #[test]
895 
    fn empty_and_unterminated_files() {
896 
        let g = FileGraph::new();
897 
        let m = g.materialize(&NoDeps);
898 
        assert_eq!(m.segments, vec![]);
899 
        assert_eq!(text(&g, &m), "");
900 
        let mut g = FileGraph::new();
901 
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["no newline"]));
902 
        assert_eq!(text(&g, &g.materialize(&NoDeps)), "no newline");
903 
    }
904
905 
    #[test]
906 
    fn serialization_round_trip() {
907 
        let mut g = FileGraph::new();
908 
        g.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));
909 
        g.insert(
910 
            h(2),
911 
            0,
912 
            Vertex::Atom((h(1), 0)),
913 
            Vertex::Atom((h(1), 1)),
914 
            &lines(&["x\n"]),
915 
        );
916 
        g.delete(
917 
            h(3),
918 
            &AtomRange {
919 
                change: h(1),
920 
                from: 1,
921 
                to: 2,
922 
            },
923 
        );
924 
        let v = g.to_value();
925 
        let bytes = crate::cbor::encode(&v);
926 
        let back = FileGraph::from_value(&crate::cbor::decode(&bytes).unwrap()).unwrap();
927 
        let deps = Deps(
928 
            [(h(2), vec![h(1)]), (h(3), vec![h(1)])]
929 
                .into_iter()
930 
                .collect(),
931 
        );
932 
        assert_eq!(back.materialize(&deps), g.materialize(&deps));
933 
        assert_eq!(text(&back, &back.materialize(&deps)), "a\nx\n");
934 
        assert_eq!(
935 
            crate::cbor::encode(&back.to_value()),
936 
            bytes,
937 
            "deterministic"
938 
        );
939 
    }
940
941 
    /// Spec §7.3: the graph is a function of the set of changes, not their order.
942 
    #[test]
943 
    fn application_order_is_irrelevant() {
944 
        use rand::seq::SliceRandom;
945 
        type Op = (
946 
            ChangeHash,
947 
            Vec<(u32, Vertex, Vertex, Vec<Vec<u8>>)>,
948 
            Vec<AtomRange>,
949 
        );
950 
        let ops: Vec<Op> = vec![
951 
            (
952 
                h(1),
953 
                vec![(0, Vertex::Start, Vertex::End, lines(&["a\n", "b\n", "c\n"]))],
954 
                vec![],
955 
            ),
956 
            (
957 
                h(2),
958 
                vec![(
959 
                    0,
960 
                    Vertex::Atom((h(1), 0)),
961 
                    Vertex::Atom((h(1), 1)),
962 
                    lines(&["p\n"]),
963 
                )],
964 
                vec![],
965 
            ),
966 
            (
967 
                h(3),
968 
                vec![(
969 
                    0,
970 
                    Vertex::Atom((h(1), 0)),
971 
                    Vertex::Atom((h(1), 1)),
972 
                    lines(&["q\n", "r\n"]),
973 
                )],
974 
                vec![AtomRange {
975 
                    change: h(1),
976 
                    from: 2,
977 
                    to: 3,
978 
                }],
979 
            ),
980 
            (
981 
                h(4),
982 
                vec![(
983 
                    0,
984 
                    Vertex::Atom((h(3), 1)),
985 
                    Vertex::Atom((h(1), 1)),
986 
                    lines(&["s\n"]),
987 
                )],
988 
                vec![AtomRange {
989 
                    change: h(1),
990 
                    from: 1,
991 
                    to: 2,
992 
                }],
993 
            ),
994 
            (
995 
                h(5),
996 
                vec![(0, Vertex::Atom((h(1), 2)), Vertex::End, lines(&["z\n"]))],
997 
                vec![],
998 
            ),
999 
        ];
1000 
        let deps = Deps(
1001 
            [
1002 
                (h(2), vec![h(1)]),
1003 
                (h(3), vec![h(1)]),
1004 
                (h(4), vec![h(3), h(1)]),
1005 
                (h(5), vec![h(1)]),
1006 
            ]
1007 
            .into_iter()
1008 
            .collect(),
1009 
        );
1010 
        let build = |order: &[usize]| {
1011 
            let mut g = FileGraph::new();
1012 
            for &i in order {
1013 
                let (c, ins, dels) = &ops[i];
1014 
                for (idx, a, b, l) in ins {
1015 
                    g.insert(*c, *idx, *a, *b, l);
1016 
                }
1017 
                for d in dels {
1018 
                    g.delete(*c, d);
1019 
                }
1020 
            }
1021 
            let m = g.materialize(&deps);
1022 
            (m.clone(), text(&g, &m))
1023 
        };
1024 
        let reference = build(&[0, 1, 2, 3, 4]);
1025 
        assert!(reference.0.is_conflicted());
1026 
        let mut rng = rand::thread_rng();
1027 
        let mut order: Vec<usize> = (0..ops.len()).collect();
1028 
        for _ in 0..50 {
1029 
            order.shuffle(&mut rng);
1030 
            assert_eq!(build(&order), reference, "order {order:?}");
1031 
        }
1032 
    }
1033 
}