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