Render a file that is one chain of lines without contracting it 598009a75f6c

        let direct = self.succ.get(&v).map(Edges::as_slice).unwrap_or_default();

        // The common case, a successor that is itself kept: nothing to

        // contract.

        if direct.iter().all(|s| kept.contains(s)) {

            return direct.iter().copied().collect();

        }

        let mut stack: Vec<Vertex> = direct.to_vec();

    }

    /// The atoms in order when the graph is one chain from Start to End with

    /// nothing deleted: a file only ever inserted into in sequence, as every

    /// file of a fresh commit or a clone is. Such a graph has no conflict.

    /// An edge to End besides the chain's next atom (Start's own, or an

    /// append's anchor) orders nothing, since End is last anyway.

    fn as_chain(&self) -> Option<Vec<AtomKey>> {

        if self

            .atoms

            .values()

            .any(|a| a.content.is_none() || !a.deleted_by.is_empty())

        {

            return None;

        }

        let mut order = Vec::with_capacity(self.atoms.len());

        let mut v = Vertex::Start;

        loop {

            let succ = self.succ.get(&v)?.as_slice();

            let mut atoms = succ.iter().filter(|s| **s != Vertex::End);

            match (atoms.next(), atoms.next()) {

                (None, _) if succ.contains(&Vertex::End) => break,

                (Some(Vertex::Atom(k)), None) if order.len() < self.atoms.len() => {

                    order.push(*k);

                    v = Vertex::Atom(*k);

                }

                _ => return None,

            }

        }

        (order.len() == self.atoms.len()).then_some(order)

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

            return Materialized {

                segments: if order.is_empty() {

                    vec![]

                } else {

                    vec![Segment::Lines(order)]

                },

            };

        }

        self.materialize_general(deps)

    }

    /// [`FileGraph::materialize`] for any graph: contraction, then a

    /// topological order with conflict regions.

    fn materialize_general(&self, deps: &dyn DepOracle) -> Materialized {

    }

    /// The chain shortcut agrees with the general algorithm wherever it

    /// applies, and stands aside wherever it does not.

    #[test]

    fn the_chain_shortcut_agrees_with_the_general_order() {

        let mut g = FileGraph::new();

        g.insert(

            h(1),

            0,

            Vertex::Start,

            Vertex::End,

            &lines(&["a\n", "b\n", "c\n"]),

        );

        assert!(g.as_chain().is_some());

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

        // Appended after the last line: still a chain.

        g.insert(

            h(2),

            0,

            Vertex::Atom((h(1), 2)),

            Vertex::End,

            &lines(&["d\n"]),

        );

        assert!(g.as_chain().is_some());

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

        // Inserted between two lines: not a chain (a has two successors).

        g.insert(

            h(4),

            0,

            Vertex::Atom((h(1), 0)),

            Vertex::Atom((h(1), 1)),

            &lines(&["x\n"]),

        );

        assert!(g.as_chain().is_none());

        assert_eq!(text(&g, &g.materialize(&NoDeps)), "a\nx\nb\nc\nd\n");

        // Two inserts at one anchor: a conflict, never a chain.

        let mut c = FileGraph::new();

        c.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n"]));

        c.insert(h(2), 0, Vertex::Start, Vertex::End, &lines(&["b\n"]));

        assert!(c.as_chain().is_none());

        assert!(c.materialize(&NoDeps).is_conflicted());

        // A deletion: not a chain.

        let mut d = FileGraph::new();

        d.insert(h(1), 0, Vertex::Start, Vertex::End, &lines(&["a\n", "b\n"]));

        d.delete(

            h(3),

            &AtomRange {

                change: h(1),

                from: 0,

                to: 1,

            },

        );

        assert!(d.as_chain().is_none());

        assert_eq!(d.materialize(&NoDeps), d.materialize_general(&NoDeps));

        // Empty.

        let e = FileGraph::new();

        assert_eq!(e.materialize(&NoDeps), e.materialize_general(&NoDeps));

    /// Each change's hash, in the order of `changes`, when whoever made

    /// the bundle knows it: the store it came from, or the bytes it was

    /// decoded from. Never read from the wire. Empty when unknown.

    pub hashes: Vec<ChangeHash>,

            let encoded = o::bytes(&pair[0], "change")?;

            b.hashes

                .push(crate::hash::hash_object(ObjectType::Change, encoded));

            let change = Change::decode_with(encoded, &mut |text, count| {

            hashes: vec![],

        assert_eq!(

            d.hashes,

            vec![c.hash()],

            "the receiver hashes what it was sent"

        );

            {

                let _t = crate::timing::phase("checkout: build graphs");

                self.load_graphs_of(&mut target, &nodes)?;

            }

            let rendered: Vec<(Vec<u8>, bool)> = {

                let _t = crate::timing::phase("checkout: render");

                nodes

                    .par_iter()

                    .map(|n| {

                        let (bytes, m) = target.render_file(n);

                        (bytes, m.is_conflicted())

                    })

                    .collect()

            };

            let _t = crate::timing::phase("checkout: write");

            bundle.hashes.push(*h);

        // Each change's hash: from the bundle when its maker knew it, else

        // worked out once (for a change adding a whole tree, hashing is

        // chunking all its text).

        let hashes: Vec<ChangeHash> = if bundle.hashes.len() == bundle.changes.len() {

            bundle.hashes.clone()

        } else {

            bundle.changes.iter().map(|(c, _)| c.hash()).collect()

        };

        let incoming: BTreeSet<ChangeHash> = hashes.iter().copied().collect();

        for ((c, sigs), h) in bundle.changes.iter().zip(hashes) {

            let stored = self.store.put_change(c)?;

            if stored != h {

                return fail(format!(

                    "change {} is not the change the bundle names",

                    h.short(12)

                ));

            }

### Clone (2026-09-30, oxygen#35)

A local clone of the Linux tip took 96 s and 5.2 GB RSS. Its checkout

spent most of its time rendering: working out each file's line order

allocated three sets per line (the contraction of the graph), 93 GB in

all, although every file of a fresh tree is one chain of lines. And the

import hashed each change three times, for the huge first change

chunking its 1.8 GB of text each time.

- A graph that is one chain from start to end with nothing deleted (an

  edge to End besides the next line orders nothing) is read off in

  order; any other graph takes the general algorithm, which also skips

  its contraction where a line's successors are all kept. A test checks

  the two agree.

- A bundle carries each change's hash when its maker knows it (the store

  it came from, or the received bytes); never from the wire. An import

  hashes each change once, by storing it, and checks it is the named one.

| Local clone, Linux tip | Time | RSS |

|---|---:|---:|

| Before | 96 s (81.6 s in a quieter run) | 5.2 to 5.4 GB |

| After | 61.0 s | 4.1 GB |

| Git | 9.6 s | 469 MB |

The checkout (31 s) now spends most of its time building graphs: each

batch of 2 048 files reads the 81 MiB first change again for its inline

inserts.