File graphs keep their order as edits apply dbf06d342e1d

    /// The live atoms' order, once known to be the graph's only one.

    order: OrderSlot,

/// A file graph's live atoms in order, when the graph orders them one way

/// only: found by [`FileGraph::materialize`] and brought up to date by

/// [`Order::splice`] as a change's edits apply, so a long-lived file

/// renders in time that follows its live lines rather than every line it

/// ever had. Any other change to the graph drops it.

#[derive(Debug)]

pub struct Order {

    atoms: Vec<AtomKey>,

    /// Atoms deleted since the order was last confirmed: it holds while

    /// none of them is a ghost (spec §9.1), which only a render can ask,

    /// since it needs to know how the changes depend on each other.

    unchecked: Vec<AtomKey>,

    confirmed: std::sync::atomic::AtomicBool,

}

/// Holds a graph's [`Order`]; filled in by a render, which only reads the

/// graph.

#[derive(Debug, Default)]

struct OrderSlot(std::sync::Mutex<Option<std::sync::Arc<Order>>>);

impl OrderSlot {

    fn get(&self) -> Option<std::sync::Arc<Order>> {

        self.0.lock().unwrap_or_else(|e| e.into_inner()).clone()

    }

    fn set(&self, o: Option<std::sync::Arc<Order>>) {

        *self.0.lock().unwrap_or_else(|e| e.into_inner()) = o;

    }

    fn take(&mut self) -> Option<std::sync::Arc<Order>> {

        self.0.get_mut().unwrap_or_else(|e| e.into_inner()).take()

    }

}

impl Clone for OrderSlot {

    fn clone(&self) -> Self {

        OrderSlot(std::sync::Mutex::new(self.get()))

    }

}

impl Order {

    fn known(atoms: Vec<AtomKey>) -> Order {

        Order {

            atoms,

            unchecked: Vec::new(),

            confirmed: std::sync::atomic::AtomicBool::new(true),

        }

    }

    /// The order after change `h` inserts the runs `inserts` (after,

    /// before, first index, count) and deletes `deleted`, as its edits

    /// apply; `None` where that is not certain to be the graph's only

    /// order: an anchor not in the order, live lines between an insert's

    /// anchors, or two inserts with nothing kept between them.

    pub fn splice(

        &self,

        h: ChangeHash,

        inserts: &[(Vertex, Vertex, u32, u32)],

        deleted: &[AtomKey],

    ) -> Option<std::sync::Arc<Order>> {

        let mut want: HashSet<AtomKey> = deleted.iter().copied().collect();

        for (a, b, _, _) in inserts {

            for v in [a, b] {

                if let Vertex::Atom(k) = v {

                    want.insert(*k);

                }

            }

        }

        let mut pos: HashMap<AtomKey, usize> = HashMap::default();

        for (i, k) in self.atoms.iter().enumerate() {

            if want.contains(k) {

                pos.insert(*k, i);

            }

        }

        let len = self.atoms.len();

        let mut gone = vec![false; len];

        let mut unchecked = if self.confirmed.load(std::sync::atomic::Ordering::Relaxed) {

            Vec::new()

        } else {

            self.unchecked.clone()

        };

        for k in deleted {

            if k.0 == h {

                return None;

            }

            if let Some(&i) = pos.get(k) {

                if !gone[i] {

                    gone[i] = true;

                    unchecked.push(*k);

                }

            }

        }

        // Each run goes in the gap its anchors leave (slot `i`: before

        // `atoms[i]`), which must hold nothing that stays.

        let mut slots: Vec<(usize, usize, u32, u32)> = Vec::with_capacity(inserts.len());

        for &(a, b, first, count) in inserts {

            let from = match a {

                Vertex::Start => 0,

                Vertex::Atom(k) => pos.get(&k)? + 1,

                Vertex::End => return None,

            };

            let to = match b {

                Vertex::End => len,

                Vertex::Atom(k) => *pos.get(&k)?,

                Vertex::Start => return None,

            };

            if from > to || gone[from..to].iter().any(|g| !g) {

                return None;

            }

            slots.push((from, to, first, count));

        }

        // Runs one after another need a kept line between them, or the

        // graph would not say which comes first.

        slots.sort_unstable();

        for w in slots.windows(2) {

            let (end, next) = (w[0].1, w[1].0);

            if end >= next || !gone[end..next].iter().any(|g| !g) {

                return None;

            }

        }

        let added: usize = slots.iter().map(|s| s.3 as usize).sum();

        let mut atoms = Vec::with_capacity(len + added);

        let mut slots = slots.into_iter().peekable();

        let mut runs_at = |i: usize, atoms: &mut Vec<AtomKey>| {

            while let Some(&(from, _, first, count)) = slots.peek() {

                if from != i {

                    break;

                }

                atoms.extend((first..first + count).map(|j| (h, j)));

                slots.next();

            }

        };

        for (i, (k, g)) in self.atoms.iter().zip(&gone).enumerate() {

            runs_at(i, &mut atoms);

            if !g {

                atoms.push(*k);

            }

        }

        runs_at(len, &mut atoms);

        let confirmed = unchecked.is_empty();

        Some(std::sync::Arc::new(Order {

            atoms,

            unchecked,

            confirmed: std::sync::atomic::AtomicBool::new(confirmed),

        }))

    }

}

            order: OrderSlot::default(),

        self.order.take();

        self.order.take();

        let lines = |order: Vec<AtomKey>| Materialized {

            segments: if order.is_empty() {

                vec![]

            } else {

                vec![Segment::Lines(order)]

            },

        };

        use std::sync::atomic::Ordering::Relaxed;

        if let Some(o) = self.order.get() {

            let holds = o.confirmed.load(Relaxed)

                || o.unchecked.iter().all(|k| {

                    self.atoms

                        .get(k)

                        .is_none_or(|info| !self.is_ghost(k, info, deps))

                });

            if holds {

                o.confirmed.store(true, Relaxed);

                return lines(o.atoms.clone());

            }

            self.order.set(None);

        }

        // A chain (nothing ever deleted) is quick to walk, and a fresh tree

        // is all chains: no order is kept for one.

        if let Some(order) = self.as_chain() {

            return lines(order);

        if let Some(order) = self.as_order(deps) {

            self.order

                .set(Some(std::sync::Arc::new(Order::known(order.clone()))));

            return lines(order);

        }

    }

    /// Take the kept order, to [`Order::splice`] it once a change's edits

    /// have applied (they drop it).

    pub fn take_order(&mut self) -> Option<std::sync::Arc<Order>> {

        self.order.take()

    }

    /// Keep `order`, spliced by the edits just applied.

    pub fn keep_order(&mut self, order: Option<std::sync::Arc<Order>>) {

        *self.order.0.get_mut().unwrap_or_else(|e| e.into_inner()) = order;

            order: OrderSlot::default(),

    }

    /// Applied as the state applies a change's edits: the kept order is

    /// spliced by them.

    fn apply_spliced(

        g: &mut FileGraph,

        h: ChangeHash,

        inserts: &[(Vertex, Vertex, usize)],

        deleted: &[AtomKey],

    ) {

        let order = g.take_order();

        let mut runs = Vec::new();

        let mut next = 0u32;

        for (i, &(a, b, n)) in inserts.iter().enumerate() {

            let text: Vec<String> = (0..n).map(|j| format!("{i}.{j}\n")).collect();

            let text: Vec<&str> = text.iter().map(String::as_str).collect();

            g.insert(h, next, a, b, &lines(&text));

            runs.push((a, b, next, n as u32));

            next += n as u32;

        }

        for k in deleted {

            g.delete(

                h,

                &AtomRange {

                    change: k.0,

                    from: k.1,

                    to: k.1 + 1,

                },

            );

        }

        if let Some(o) = order {

            g.keep_order(o.splice(h, &runs, deleted));

        }

    }

    /// Edits as a diff makes them from the order `l`: hunks with a kept

    /// line between them, each deleting some lines and inserting some.

    fn random_edits(

        l: &[AtomKey],

        rnd: &mut impl FnMut(usize) -> usize,

    ) -> (Vec<(Vertex, Vertex, usize)>, Vec<AtomKey>) {

        let (mut inserts, mut deleted) = (Vec::new(), Vec::new());

        let mut i = rnd(3);

        while i <= l.len() {

            let del = rnd(3).min(l.len() - i);

            let add = rnd(3);

            let after = if i == 0 {

                Vertex::Start

            } else {

                Vertex::Atom(l[i - 1])

            };

            let before = l.get(i).map(|k| Vertex::Atom(*k)).unwrap_or(Vertex::End);

            deleted.extend(&l[i..i + del]);

            if add > 0 {

                inserts.push((after, before, add));

            }

            i += del + 1 + rnd(6);

        }

        (inserts, deleted)

    }

    /// The kept order, spliced change by change, is what the general

    /// algorithm finds, through sequential edits and through concurrent

    /// ones that leave conflicts and ghosts (where it must stand aside).

    #[test]

    fn the_kept_order_follows_edits() {

        let hn = |i: usize| {

            let mut b = [0u8; 32];

            b[..2].copy_from_slice(&(i as u16).to_be_bytes());

            ObjectRef(b)

        };

        let mut seed = 7u64;

        let mut rnd = move |n: usize| {

            seed = seed

                .wrapping_mul(6364136223846793005)

                .wrapping_add(1442695040888963407);

            ((seed >> 33) as usize) % n.max(1)

        };

        let mut deps = Deps(HashMap::default());

        let mut g = FileGraph::new();

        let first: Vec<String> = (0..40).map(|i| format!("{i}\n")).collect();

        let first: Vec<&str> = first.iter().map(String::as_str).collect();

        g.insert(hn(1), 0, Vertex::Start, Vertex::End, &lines(&first));

        let mut known: Vec<ChangeHash> = vec![hn(1)];

        let mut c = 2;

        let (mut spliced, mut conflicted) = (0, 0);

        for step in 0..400 {

            let l = g.materialize(&deps).live_atoms();

            // Now and then two changes from the same base, neither knowing

            // the other.

            let pair = step % 7 == 3;

            let base = known.clone();

            for _ in 0..if pair { 2 } else { 1 } {

                let h = hn(c);

                c += 1;

                let (inserts, deleted) = random_edits(&l, &mut rnd);

                deps.0.insert(h, base.clone());

                apply_spliced(&mut g, h, &inserts, &deleted);

                known.push(h);

                if g.order.get().is_some() {

                    spliced += 1;

                }

                let m = g.materialize(&deps);

                assert_eq!(m, g.materialize_general(&deps), "step {step}");

                if m.is_conflicted() {

                    conflicted += 1;

                }

            }

            // A change that knows everything settles any conflict by

            // rewriting the file.

            if g.materialize(&deps).is_conflicted() {

                let h = hn(c);

                c += 1;

                let all = g.materialize(&deps).live_atoms();

                deps.0.insert(h, known.clone());

                apply_spliced(&mut g, h, &[(Vertex::Start, Vertex::End, 5)], &all);

                known.push(h);

                assert_eq!(g.materialize(&deps), g.materialize_general(&deps));

            }

        }

        assert!(

            spliced > 100 && conflicted > 0,

            "{spliced} spliced, {conflicted} conflicted"

        );

    // The graph's kept order, if any, follows the edits (see `Order`).

    let order = g.take_order();

    let mut inserts: Vec<(Vertex, Vertex, u32, u32)> = Vec::new();

    let mut deleted: Vec<crate::graph::AtomKey> = Vec::new();

                let count = lines.len() as u32;

                next += count;

                let (after, before) = (vertex(after.resolve(h)), vertex(before.resolve(h)));

                inserts.push((after, before, first, count));

                g.insert_owned(h, first, after, before, lines);

                    let r = r.resolve(h);

                    deleted.extend((r.from..r.to).map(|i| (r.change, i)));

                    g.delete(h, &r);

    }

    if let Some(o) = order {

        g.keep_order(o.splice(h, &inserts, &deleted));