Verify a Git import from each parent's state 57d8dc05c9d4

        // The state of a commit whose first-parent children are still to

        // come, so a child adds its own changes instead of loading all its

        // history again (as the import does).

        let mut waiting: HashMap<&str, usize> = HashMap::new();

            if let Some(p1) = c.parents.first() {

                *waiting.entry(p1.as_str()).or_default() += 1;

            }

        }

        let mut kept: HashMap<String, State> = HashMap::new();

        let mut kept_order: std::collections::VecDeque<String> = std::collections::VecDeque::new();

        for c in &commits {

            let from_parent = c.parents.first().and_then(|p1| {

                let left = waiting.get_mut(p1.as_str()).map(|n| {

                    *n -= 1;

                    *n

                });

                if left == Some(0) {

                    kept_order.retain(|k| k != p1);

                    kept.remove(p1.as_str())

                } else {

                    kept.get(p1.as_str()).cloned()

                }

            });

            let state = match from_parent {

                Some(mut st) => {

                    // The changes the parent's state lacks. The state never

                    // builds a graph (they are built beside it), so they

                    // are read without their text.

                    for h in set.iter() {

                        if !st.contains(h) {

                            let (change, texts) = self.store.get_change_lazy(h)?;

                            st.add_known(*h, change, texts);

                        }

                    }

                    st

                }

                None => self.load_state_history(&heads)?,

            };

            let graphs = self.build_graphs_detached(&state, &need)?;

                            let (have, m) = match graphs.get(&e.node) {

                                Some(g) => state.render_graph(g),

                                None => (Vec::new(), Default::default()),

                            };

                                // Who conflicts: a copy of the state with this graph built.

                                let mut detail = state.clone();

                                self.load_graphs_of(&mut detail, &[e.node])?;

                                let who: Vec<String> = detail

                }

            }

            if waiting.get(c.sha.as_str()).is_some_and(|n| *n > 0) {

                kept.insert(c.sha.clone(), state);

                kept_order.push_back(c.sha.clone());

                if kept_order.len() > 8 {

                    if let Some(old) = kept_order.pop_front() {

                        kept.remove(&old);

                    }

    /// The graphs of `nodes` of a history-only state, built beside it (see

    /// [`State::build_graphs_detached`]).

    pub fn build_graphs_detached(

        &self,

        state: &State,

        nodes: &[crate::ids::NodeId],

    ) -> Result<HashMap<crate::ids::NodeId, crate::graph::FileGraph>> {

        Ok(state

            .build_graphs_detached(

                nodes,

                |refs| {

                    self.read_blobs(refs).map_err(|e| {

                        crate::objects::ObjectError::Schema(format!("graph and text blobs: {e}"))

                    })

                },

                |h| self.change_bytes(h),

            )?

            .into_iter()

            .collect())

    }

/// Build the graphs of deferred entries: their checkpoint bases and the

/// texts of inserts read without their lines are loaded in one call, then

/// the graphs are built in parallel (they are independent).

fn build_deferred(

    mut taken: Vec<(NodeId, Deferred)>,

    load: impl FnOnce(&[ObjectRef]) -> Result<Vec<Vec<u8>>, ObjectError>,

    read_change: impl Fn(&ChangeHash) -> Result<Arc<Vec<u8>>, ObjectError>,

) -> Result<Vec<(NodeId, FileGraph)>, ObjectError> {

    let mut refs: Vec<ObjectRef> = taken

        .iter()

        .filter_map(|(_, d)| match &d.base {

            Some(DeferredBase::Blob(r)) => Some(*r),

            _ => None,

        })

        .collect();

    // Text blobs of inserts read without their lines, after the bases.

    let bases = refs.len();

    refs.extend(taken.iter().flat_map(|(_, d)| {

        d.texts.iter().filter_map(|t| match t {

            TextRef::Blob(r, _) => Some(*r),

            TextRef::Inline { .. } => None,

        })

    }));

    // And the encodings of changes whose inline inserts are needed,

    // each read once.

    let mut changes: HashMap<ChangeHash, Arc<Vec<u8>>> = HashMap::new();

    for t in taken.iter().flat_map(|(_, d)| d.texts.iter()) {

        if let TextRef::Inline { change, .. } = t {

            if !changes.contains_key(change) {

                changes.insert(*change, read_change(change)?);

            }

        }

    }

    let mut blobs = if refs.is_empty() {

        Vec::new()

    } else {

        load(&refs)?

    };

    if blobs.len() != refs.len() {

        return Err(ObjectError::Schema("graph blobs: wrong count".into()));

    }

    let mut texts = blobs.split_off(bases).into_iter();

    let mut blobs = blobs.into_iter();

    // Pair each graph with its blob, then build them all in parallel:

    // graphs are independent.

    let mut work: Vec<(NodeId, Deferred, Option<Vec<u8>>)> = Vec::with_capacity(taken.len());

    for (node, mut d) in taken.drain(..) {

        // Fill in the lines of inserts read without them, in order.

        let mut want = std::mem::take(&mut d.texts).into_iter();

        for (_, edits) in d.edits.iter_mut() {

            for e in edits.iter_mut() {

                if let Edit::Insert { lines, .. } = e {

                    if lines.is_empty() {

                        *lines = match want.next() {

                            Some(TextRef::Blob(_, count)) => {

                                let content = texts.next().ok_or_else(|| {

                                    ObjectError::Schema("text blobs: wrong count".into())

                                })?;

                                crate::objects::text_lines(&content, count)?

                            }

                            Some(TextRef::Inline { change, start, end }) => {

                                let bytes = &changes[&change];

                                let range =

                                    bytes.get(start as usize..end as usize).ok_or_else(|| {

                                        ObjectError::Schema(

                                            "an inline insert lies outside its change".into(),

                                        )

                                    })?;

                                crate::objects::inline_lines(range)?

                            }

                            None => {

                                return Err(ObjectError::Schema(

                                    "an insert's text is missing".into(),

                                ))

                            }

                        };

                    }

                }

            }

        }

        let bytes = match &d.base {

            Some(DeferredBase::Blob(_)) => Some(

                blobs

                    .next()

                    .ok_or_else(|| ObjectError::Schema("graph blobs: wrong count".into()))?,

            ),

            _ => None,

        };

        work.push((node, d, bytes));

    }

    use rayon::prelude::*;

    let built: Vec<(NodeId, FileGraph)> = work

        .into_par_iter()

        .map(|(node, mut d, bytes)| {

            let mut graph = match (d.base.take(), bytes) {

                (Some(DeferredBase::Inline(v)), _) => FileGraph::from_value(&v)?,

                (Some(DeferredBase::Blob(_)), Some(bytes)) => {

                    FileGraph::from_value(&cbor::decode(&bytes)?)?

                }

                _ => FileGraph::default(),

            };

            for (h, edits) in std::mem::take(&mut d.edits) {

                apply_file_edits(&mut graph, h, edits);

            }

            Ok((node, graph))

        })

        .collect::<Result<_, ObjectError>>()?;

    Ok(built)

}

        let taken: Vec<(NodeId, Deferred)> = nodes

        let built = build_deferred(taken, load, read_change)?;

    }

    /// The graphs of `nodes`, built from this history-only state's deferred

    /// edits without building them in it: the state stays history only, so

    /// changes read without their lines can still be added to it and every

    /// graph keeps its key. For a caller that renders a few files of many

    /// states in turn (verifying an import).

    pub fn build_graphs_detached(

        &self,

        nodes: &[NodeId],

        load: impl FnOnce(&[ObjectRef]) -> Result<Vec<Vec<u8>>, ObjectError>,

        read_change: impl Fn(&ChangeHash) -> Result<Arc<Vec<u8>>, ObjectError>,

    ) -> Result<Vec<(NodeId, FileGraph)>, ObjectError> {

        let Some(deferred) = self.deferred.as_ref() else {

            return Ok(Vec::new());

        };

        let copies: Vec<(NodeId, Deferred)> = nodes

            .iter()

            .map(|n| (*n, deferred.get(n).cloned().unwrap_or_default()))

            .collect();

        build_deferred(copies, load, read_change)

    }

    /// Render a graph built for this state (see

    /// [`State::build_graphs_detached`]), as [`State::render_file`] does.

    pub fn render_graph(&self, g: &FileGraph) -> (Vec<u8>, Materialized) {

        let m = g.materialize(self);

        let bytes = g.render(&m, &|h| self.label(h));

        (bytes, m)

Verify loaded each commit's history from scratch. It now keeps the

state of a commit whose children are still to come, as the import does,

and a child adds only the changes its parent lacks. Those states stay

history only: graphs are built beside them (`State::build_graphs_detached`)

and dropped after rendering, so changes are added without their text and

every file keeps its graph key, which the cache of verified files needs.

The same 5 000 commits verify in 166.5 s (from 978 s), 1.3 GB.