crates/oxy-core/src/repo/git.rs at ce118287d9da · andymccall/oxygen

# ce118287d9da oxygen / crates / oxy-core / src / repo / git.rs
82.7 KiB · Rust · last changed git import: build a merge from the paths it can change 1 month ago source blame history raw
//! Git bridge (spec §23), export side: each state the current bookmark
//! passed through becomes a Git commit through `git fast-import`, with the
//! state's full tree and the previous state's commit as parent. A state
//! that added exactly one change carries that change's message, author,
//! and `Change-Id`/`Oxy-Hash` trailers; every commit carries `Oxy-State`.
//!
//! Marks make re-exports incremental: `.oxy/git/<target>/git-marks` is
//! git's own marks file and `oxy-marks` maps state refs to marks.

use super::*;
use std::process::{Command, Stdio};
use std::sync::Arc;

#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct GitImportReport {
    pub commits: usize,
    pub merges: usize,
    /// Gitlink entries imported as subrepo nodes with Git pins.
    pub submodules: usize,
    pub heads: usize,
}

/// A running `git cat-file --batch`, for reading many blobs cheaply.
struct CatFile {
    child: std::process::Child,
    stdin: std::process::ChildStdin,
    stdout: std::io::BufReader<std::process::ChildStdout>,
}

impl CatFile {
    fn start(git_dir: &Path) -> Result<CatFile> {
        let mut child = Command::new("git")
            .arg("-C")
            .arg(git_dir)
            .args(["cat-file", "--batch"])
            .stdin(Stdio::piped())
            .stdout(Stdio::piped())
            .stderr(Stdio::null())
            .spawn()
            .map_err(|e| RepoError::Msg(format!("running git cat-file: {e}")))?;
        let stdin = child.stdin.take().unwrap();
        let stdout = std::io::BufReader::new(child.stdout.take().unwrap());
        Ok(CatFile {
            child,
            stdin,
            stdout,
        })
    }

    fn read(&mut self, sha: &str) -> Result<Vec<u8>> {
        use std::io::{BufRead, Read};
        writeln!(self.stdin, "{sha}")?;
        self.stdin.flush()?;
        let mut header = String::new();
        self.stdout.read_line(&mut header)?;
        let parts: Vec<&str> = header.trim_end().split(' ').collect();
        if parts.len() != 3 {
            return fail(format!("git cat-file: object {sha} not found"));
        }
        let size: usize = parts[2]
            .parse()
            .map_err(|_| RepoError::Msg("git cat-file: bad size".into()))?;
        let mut body = vec![0u8; size];
        self.stdout.read_exact(&mut body)?;
        let mut nl = [0u8; 1];
        self.stdout.read_exact(&mut nl)?;
        Ok(body)
    }
}

impl Drop for CatFile {
    fn drop(&mut self) {
        let _ = self.child.kill();
        let _ = self.child.wait();
    }
}

/// One path a commit changes against its first parent: its new mode and
/// blob, or `None` when the commit deletes it.
type TreeDiff = Vec<(String, Option<(String, String)>)>;

/// A running `git diff-tree --stdin`, fed every `commit parent` pair up
/// front, whose diffs are read in the same order as they are needed: a
/// commit's tree is its first parent's plus its diff, at a cost that
/// follows what it changes rather than the whole tree (oxygen#25).
struct DiffTree {
    child: std::process::Child,
    stdout: std::io::BufReader<std::process::ChildStdout>,
    feeder: Option<std::thread::JoinHandle<()>>,
    /// The header read at the end of the previous diff.
    next: Option<String>,
}

impl DiffTree {
    fn start(git_dir: &Path, pairs: Vec<(String, String)>) -> Result<DiffTree> {
        let mut child = Command::new("git")
            .arg("-C")
            .arg(git_dir)
            .args([
                "diff-tree",
                "--stdin",
                "--always",
                "-r",
                "-z",
                "--no-renames",
            ])
            .stdin(Stdio::piped())
            .stdout(Stdio::piped())
            .stderr(Stdio::null())
            .spawn()
            .map_err(|e| RepoError::Msg(format!("running git diff-tree: {e}")))?;
        let mut stdin = child.stdin.take().unwrap();
        let stdout = std::io::BufReader::new(child.stdout.take().unwrap());
        // A thread writes, so git never waits on a full pipe for us to read.
        let feeder = std::thread::spawn(move || {
            let mut w = std::io::BufWriter::new(&mut stdin);
            for (c, p) in pairs {
                if writeln!(w, "{c} {p}").is_err() {
                    return;
                }
            }
            let _ = w.flush();
        });
        Ok(DiffTree {
            child,
            stdout,
            feeder: Some(feeder),
            next: None,
        })
    }

    fn field(&mut self) -> Result<Option<String>> {
        use std::io::BufRead;
        let mut buf = Vec::new();
        if self.stdout.read_until(0, &mut buf)? == 0 {
            return Ok(None);
        }
        if buf.last() == Some(&0) {
            buf.pop();
        }
        Ok(Some(String::from_utf8_lossy(&buf).into_owned()))
    }

    /// The diff of `sha` against the parent it was fed with.
    fn diff(&mut self, sha: &str) -> Result<TreeDiff> {
        let header = match self.next.take() {
            Some(h) => Some(h),
            None => self.field()?,
        };
        if header.as_deref() != Some(sha) {
            return fail(format!("git diff-tree: expected {sha}, got {header:?}"));
        }
        let mut out = Vec::new();
        while let Some(f) = self.field()? {
            let Some(meta) = f.strip_prefix(':') else {
                self.next = Some(f);
                break;
            };
            let Some(path) = self.field()? else {
                return fail("git diff-tree: record without a path");
            };
            // `oldmode newmode oldsha newsha status`
            let m: Vec<&str> = meta.split(' ').collect();
            if m.len() != 5 {
                return fail(format!("git diff-tree: bad record {f:?}"));
            }
            let entry = if m[4].starts_with('D') {
                None
            } else {
                Some((m[1].to_string(), m[3].to_string()))
            };
            out.push((path, entry));
        }
        Ok(out)
    }
}

impl Drop for DiffTree {
    fn drop(&mut self) {
        let _ = self.child.kill();
        let _ = self.child.wait();
        if let Some(f) = self.feeder.take() {
            let _ = f.join();
        }
    }
}

/// One commit as `git log` describes it.
struct GitCommit {
    sha: String,
    parents: Vec<String>,
    author_secs: u64,
    author: String,
    message: String,
}

fn list_commits(git_dir: &Path, branch: &str) -> Result<Vec<GitCommit>> {
    let out = Command::new("git")
        .arg("-C")
        .arg(git_dir)
        .args([
            "log",
            "--reverse",
            "--topo-order",
            "--format=%H%x00%P%x00%at%x00%an <%ae>%x00%B%x1e",
            branch,
        ])
        .output()
        .map_err(|e| RepoError::Msg(format!("running git log: {e}")))?;
    if !out.status.success() {
        return fail(format!(
            "git log {branch} failed: {}",
            String::from_utf8_lossy(&out.stderr).trim()
        ));
    }
    let text = String::from_utf8_lossy(&out.stdout);
    let mut commits = Vec::new();
    for record in text.split('\x1e') {
        let record = record.trim_start_matches('\n');
        if record.trim().is_empty() {
            continue;
        }
        let f: Vec<&str> = record.splitn(5, '\0').collect();
        if f.len() != 5 {
            return fail("unexpected git log record");
        }
        commits.push(GitCommit {
            sha: f[0].to_string(),
            parents: f[1].split_whitespace().map(str::to_string).collect(),
            author_secs: f[2].parse().unwrap_or(0),
            author: f[3].to_string(),
            message: f[4].trim_end().to_string(),
        });
    }
    Ok(commits)
}

/// `path → (mode, blob sha)` for a commit's tree.
fn list_tree(git_dir: &Path, sha: &str) -> Result<BTreeMap<String, (String, String)>> {
    let text = git(git_dir, &["ls-tree", "-r", "-z", sha])?;
    let mut out = BTreeMap::new();
    for entry in text.split('\0') {
        if entry.is_empty() {
            continue;
        }
        let Some((meta, path)) = entry.split_once('\t') else {
            continue;
        };
        let m: Vec<&str> = meta.split(' ').collect();
        if m.len() == 3 {
            out.insert(path.to_string(), (m[0].to_string(), m[2].to_string()));
        }
    }
    Ok(out)
}

/// The ChangeId for a Git commit: its `Change-Id` trailer if it has a
/// 32-hex one, else BLAKE3-128 of the commit hash (spec §23).
fn change_id_for(sha: &str, message: &str) -> ChangeId {
    for line in message.lines().rev() {
        if let Some(v) = line.strip_prefix("Change-Id:") {
            if let Some(id) = ChangeId::from_hex(v.trim()) {
                return id;
            }
        }
    }
    let h = blake3::hash(sha.as_bytes());
    ChangeId(h.as_bytes()[..16].try_into().unwrap())
}

/// Git commits with a known Oxygen counterpart.
struct GitKnown {
    /// Imported commit → its change.
    imported: HashMap<String, ChangeHash>,
    /// Exported commit (or a fetched tip) → the bookmark state it equals.
    exported: HashMap<String, ObjectRef>,
}

#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct GitExportReport {
    pub exported: usize,
    pub skipped: usize,
    /// Subrepo nodes with Oxygen pins, which Git cannot represent.
    pub skipped_subrepos: usize,
    pub branch: String,
    pub heads: usize,
}

/// A merge bringing more commits than this sheds its base's graphs first.
const MERGE_SHED_COMMITS: usize = 100;

/// The atoms a kept state's built graphs may hold before they go back into
/// its history (#25): about a few hundred megabytes.
const KEPT_ATOMS: usize = 1_500_000;
/// A kept state with more built graphs than this sheds them.
const KEPT_GRAPHS: usize = 2000;
/// An import moves its bookmark to the commits done so far every this
/// many commits, so one that stops part way resumes from there: imported
/// commits are found from the bookmark's history (`imported_commits`).
const CHECKPOINT_COMMITS: usize = 2000;

/// Text files of a merge rendered this many at a time (oxygen#25): a
/// batch's graphs are built beside the state and dropped once rendered,
/// so what is held for the whole tree is the renderings, not the graphs
/// with every deleted line of their history.
const MERGE_BATCH: usize = 500;

thread_local! {
    /// A smaller batch for this thread's imports: tests set 1, so a small
    /// merge takes the batched path.
    static MERGE_BATCH_OVERRIDE: std::cell::Cell<Option<usize>> = const { std::cell::Cell::new(None) };
}

#[cfg(test)]
pub(crate) fn set_merge_batch_for_tests(n: Option<usize>) {
    MERGE_BATCH_OVERRIDE.with(|c| c.set(n));
}

fn merge_batch() -> usize {
    MERGE_BATCH_OVERRIDE
        .with(|c| c.get())
        .filter(|n| *n > 0)
        .unwrap_or(MERGE_BATCH)
}

impl Repo {
    /// As `State::materialize_except`, for a tree whose graphs would not
    /// fit in memory at once. The few files the change builder reads
    /// graphs for (conflicted ones, and renderings whose lines are not
    /// one per live atom) are built in the state afterwards.
    fn materialize_batched(
        &self,
        base: &mut State,
        need: &[crate::ids::NodeId],
        skip: &HashSet<crate::ids::NodeId>,
    ) -> Result<crate::state::Snapshot> {
        use crate::graph::Materialized;
        use crate::state::{FileContent, FileState};
        use rayon::prelude::*;
        let view = base.tree().view();
        let mut rendered: HashMap<crate::ids::NodeId, (Vec<u8>, Materialized)> =
            HashMap::with_capacity(need.len());
        let mut keep_built: Vec<crate::ids::NodeId> = Vec::new();
        for batch in need.chunks(merge_batch()) {
            let t = std::time::Instant::now();
            let graphs = self.build_graphs_detached(base, batch)?;
            crate::timing::add("render: build graphs, batch", t.elapsed());
            let t = std::time::Instant::now();
            let batch_rendered: Vec<(crate::ids::NodeId, Vec<u8>, Materialized)> = graphs
                .par_iter()
                .map(|(node, g)| {
                    let (bytes, m) = base.render_graph(g);
                    (*node, bytes, m)
                })
                .collect();
            drop(graphs);
            crate::timing::add("render: render, batch", t.elapsed());
            for (node, bytes, m) in batch_rendered {
                if m.is_conflicted()
                    || m.live_atoms().len() != crate::diff::split_lines(&bytes).len()
                {
                    keep_built.push(node);
                }
                rendered.insert(node, (bytes, m));
            }
        }
        if !keep_built.is_empty() {
            self.load_graphs_of(base, &keep_built)?;
        }
        let mut files = BTreeMap::new();
        let mut unrendered = BTreeSet::new();
        for (path, e) in view.entries.iter() {
            let f = if e.kind == NodeKind::File && !e.mode.opaque {
                match rendered.remove(&e.node) {
                    Some((bytes, materialized)) => FileState {
                        node: e.node,
                        kind: e.kind,
                        mode: e.mode,
                        content: FileContent::Text {
                            bytes,
                            materialized,
                        },
                    },
                    None if skip.contains(&e.node) => {
                        unrendered.insert(path.clone());
                        FileState {
                            node: e.node,
                            kind: e.kind,
                            mode: e.mode,
                            content: FileContent::Text {
                                bytes: Vec::new(),
                                materialized: Materialized::default(),
                            },
                        }
                    }
                    None => {
                        // Neither asked for nor known unchanged: render it
                        // from a built graph, as the whole-tree path does.
                        self.load_graphs_of(base, &[e.node])?;
                        base.entry_state(e)
                    }
                }
            } else {
                base.entry_state(e)
            };
            files.insert(path.clone(), f);
        }
        Ok(crate::state::Snapshot {
            tree: view,
            files,
            unrendered,
        })
    }
}

fn git(dir: &Path, args: &[&str]) -> Result<String> {
    let out = Command::new("git")
        .arg("-C")
        .arg(dir)
        .args(args)
        .output()
        .map_err(|e| RepoError::Msg(format!("running git: {e}")))?;
    if !out.status.success() {
        return fail(format!(
            "git {} failed: {}",
            args.join(" "),
            String::from_utf8_lossy(&out.stderr).trim()
        ));
    }
    Ok(String::from_utf8_lossy(&out.stdout).trim().to_string())
}

impl Repo {
    fn git_marks_dir(&self, git_dir: &Path) -> Result<PathBuf> {
        let canonical = git_dir
            .canonicalize()
            .unwrap_or_else(|_| git_dir.to_path_buf());
        let key = hash_object(ObjectType::Chunk, canonical.to_string_lossy().as_bytes()).short(16);
        let dir = self.oxy.join("git").join(key);
        fs::create_dir_all(&dir)?;
        Ok(dir)
    }

    /// `state ref → Git commit sha` for bookmark states that equal a Git
    /// commit's tree (recorded by import and fetch).
    fn read_git_states(path: &Path) -> Result<BTreeMap<ObjectRef, String>> {
        let mut out = BTreeMap::new();
        if let Ok(text) = fs::read_to_string(path) {
            for line in text.lines() {
                if let Some((h, sha)) = line.split_once(' ') {
                    if let Some(h) = ObjectRef::from_hex(h) {
                        out.insert(h, sha.trim().to_string());
                    }
                }
            }
        }
        Ok(out)
    }

    fn record_git_state(&self, git_dir: &Path, state: &ObjectRef, sha: &str) -> Result<()> {
        let path = self.git_marks_dir(git_dir)?.join("git-states");
        let mut states = Self::read_git_states(&path)?;
        states.insert(*state, sha.to_string());
        let text: String = states
            .iter()
            .map(|(h, s)| format!("{} {s}\n", h.to_hex()))
            .collect();
        write_atomic(&path, text.as_bytes())
    }

    /// The bare mirror this repository keeps for the Git remote `url`.
    fn git_mirror(&self, url: &str) -> Result<PathBuf> {
        let key = hash_object(ObjectType::Chunk, url.as_bytes()).short(16);
        let dir = self.oxy.join("git").join(key).join("mirror.git");
        if !dir.join("HEAD").exists() {
            fs::create_dir_all(&dir)?;
            git(&dir, &["init", "--bare", "-q"])?;
        }
        Ok(dir)
    }

    /// Git commits already imported into the bookmark, by sha.
    pub(crate) fn imported_commits(&self) -> Result<HashMap<String, ChangeHash>> {
        let mut map = HashMap::new();
        for e in self.log()? {
            if e.is_working_copy {
                continue;
            }
            if let Some(sha) = e
                .change
                .message
                .lines()
                .rev()
                .find_map(|l| l.strip_prefix("Git-Commit: "))
            {
                map.insert(sha.trim().to_string(), e.hash);
            }
        }
        Ok(map)
    }

    /// Bring the mirror's `branch` up to date with the Git remote `url`.
    /// A remote without that branch yet leaves the mirror as it is.
    fn git_mirror_fetch(&self, mirror: &Path, url: &str, branch: &str) -> Result<()> {
        let spec = format!("+refs/heads/{branch}:refs/heads/{branch}");
        match git(mirror, &["fetch", "-q", url, &spec]) {
            Ok(_) => Ok(()),
            Err(e) => {
                let ls = git(mirror, &["ls-remote", "--heads", url, branch]).unwrap_or_default();
                if ls.trim().is_empty() {
                    Ok(())
                } else {
                    Err(e)
                }
            }
        }
    }

    /// Fetch `branch` of the Git repository at `url` (a path or a Git URL)
    /// through a mirror and import the commits not yet in the bookmark
    /// (spec §23). Works on a repository that already has history: the
    /// new changes join the bookmark like a pull.
    pub fn git_fetch(&self, url: &str, branch: &str) -> Result<GitImportReport> {
        // A local path, made absolute: git runs it from inside the mirror.
        let local = Path::new(url)
            .canonicalize()
            .ok()
            .filter(|_| !url.contains("://"));
        let absolute = local.as_ref().map(|p| p.to_string_lossy().into_owned());
        let url = absolute.as_deref().unwrap_or(url);
        let mirror = self.git_mirror(url)?;
        self.git_mirror_fetch(&mirror, url, branch)?;
        if git(
            &mirror,
            &[
                "rev-parse",
                "--verify",
                "-q",
                &format!("refs/heads/{branch}"),
            ],
        )
        .is_err()
        {
            return fail(format!("{url} has no branch {branch:?}"));
        }
        self.import_git_commits(
            &mirror,
            branch,
            &format!("oxy git fetch {url} {branch}"),
            &mut |_| {},
        )
    }

    /// Export the bookmark to `branch` of the Git repository at `url`
    /// through the mirror and push it. The remote's tip must already have
    /// been fetched (`git_fetch`), so the push fast-forwards.
    pub fn git_push(&self, url: &str, branch: &str) -> Result<GitExportReport> {
        let mirror = self.git_mirror(url)?;
        self.git_mirror_fetch(&mirror, url, branch)?;
        if let Ok(tip) = git(
            &mirror,
            &[
                "rev-parse",
                "--verify",
                "-q",
                &format!("refs/heads/{branch}"),
            ],
        ) {
            let known = self.git_known(&mirror)?;
            if !known.imported.contains_key(&tip) && !known.exported.contains_key(&tip) {
                return fail(format!(
                    "{url} {branch} has commits not yet fetched; run `oxy git fetch {url}` first"
                ));
            }
        }
        let report = self.git_export_as(&mirror, branch)?;
        let spec = format!("refs/heads/{branch}:refs/heads/{branch}");
        git(&mirror, &["push", "-q", url, &spec])?;
        Ok(report)
    }

    fn read_oxy_marks(path: &Path) -> Result<BTreeMap<ObjectRef, u64>> {
        let mut out = BTreeMap::new();
        if let Ok(text) = fs::read_to_string(path) {
            for line in text.lines() {
                if let Some((h, m)) = line.split_once(' ') {
                    if let (Some(h), Ok(m)) = (ObjectRef::from_hex(h), m.parse()) {
                        out.insert(h, m);
                    }
                }
            }
        }
        Ok(out)
    }

    /// Export the current bookmark to the Git repository at `git_dir`,
    /// creating a bare one if nothing is there. Each state the bookmark
    /// passed through (per the operation log) becomes one commit whose tree
    /// is that state, so the Git branch is a linear history of full trees.
    pub fn git_export(&self, git_dir: &Path) -> Result<GitExportReport> {
        let bookmark = self.config.bookmark.clone();
        self.git_export_as(git_dir, &bookmark)
    }

    /// `git_export` to the Git branch `branch`. A state that came from a
    /// Git commit (`oxy git fetch`) is not re-exported: later states chain
    /// onto that commit, so a push back to the Git remote fast-forwards.
    pub fn git_export_as(&self, git_dir: &Path, branch: &str) -> Result<GitExportReport> {
        if !git_dir.join("HEAD").exists() && !git_dir.join(".git").exists() {
            fs::create_dir_all(git_dir)?;
            git(git_dir, &["init", "--bare", "-q"])?;
        }
        let marks_dir = self.git_marks_dir(git_dir)?;
        let git_marks = marks_dir.join("git-marks");
        let oxy_marks_path = marks_dir.join("oxy-marks");
        let mut marks = Self::read_oxy_marks(&oxy_marks_path)?;
        let git_states = Self::read_git_states(&marks_dir.join("git-states"))?;
        let mut next_mark = marks.values().copied().max().unwrap_or(0) + 1;

        let bookmark = self.config.bookmark.clone();
        let mut stream: Vec<u8> = Vec::new();
        let mut report = GitExportReport {
            branch: branch.to_string(),
            heads: self.bookmark_heads()?.len(),
            ..Default::default()
        };

        // States along the bookmark, oldest first, skipping unchanged and pruned ones.
        let mut ops = self.op_log()?;
        ops.reverse();
        let mut prev: Option<(ObjectRef, Vec<ChangeHash>)> = None;
        // The fast-import parent of the next commit: `:mark` or a commit sha.
        let mut last_parent: Option<String> = None;
        for (_, op) in &ops {
            let Some(state_ref) = op.view.bookmarks.get(&bookmark).copied() else {
                continue;
            };
            if prev.as_ref().is_some_and(|(p, _)| *p == state_ref) {
                continue;
            }
            let Ok(state) = self.store.get_state(&state_ref) else {
                continue;
            };
            if state.heads.is_empty() {
                prev = Some((state_ref, vec![]));
                continue;
            }
            if let Some(sha) = git_states.get(&state_ref) {
                report.skipped += 1;
                last_parent = Some(sha.clone());
                prev = Some((state_ref, state.heads.clone()));
                continue;
            }
            if let Some(m) = marks.get(&state_ref) {
                report.skipped += 1;
                last_parent = Some(format!(":{m}"));
                prev = Some((state_ref, state.heads.clone()));
                continue;
            }
            let prev_heads = prev.as_ref().map(|(_, h)| h.clone()).unwrap_or_default();
            let added = self
                .negotiate(&prev_heads, &state.heads)
                .unwrap_or_default();
            let loaded = self.load_state(&state.heads)?;
            let snapshot = loaded.materialize();
            let (author, secs, mut message) = match added.as_slice() {
                [h] => {
                    let c = self.store.get_change(h)?;
                    let mut m = c.message.clone();
                    if !m.ends_with('\n') {
                        m.push('\n');
                    }
                    m.push_str(&format!(
                        "\nChange-Id: {}\nOxy-Hash: {}\n",
                        c.change_id.to_hex(),
                        h.to_hex()
                    ));
                    (self.git_author(&c), c.hlc.wall_ms / 1000, m)
                }
                [] => (
                    "oxy <oxy@localhost>".to_string(),
                    op.hlc.wall_ms / 1000,
                    format!("oxy: {}\n\n", op.command),
                ),
                many => {
                    let mut m = format!("oxy: {} ({} changes)\n\n", op.command, many.len());
                    for h in many {
                        let c = self.store.get_change(h)?;
                        m.push_str(&format!(
                            "- {} {}\n",
                            c.change_id.short(8),
                            c.message.lines().next().unwrap_or("")
                        ));
                    }
                    m.push_str(&format!(
                        "\nOxy-Changes: {}\n",
                        many.iter()
                            .map(|h| h.to_hex())
                            .collect::<Vec<_>>()
                            .join(" ")
                    ));
                    ("oxy <oxy@localhost>".to_string(), op.hlc.wall_ms / 1000, m)
                }
            };
            message.push_str(&format!("Oxy-State: {}\n", state_ref.to_hex()));
            if snapshot.is_conflicted() {
                message.push_str("Oxy-Conflicted: true\n");
            }
            let mark = next_mark;
            next_mark += 1;
            let parents: Vec<String> = last_parent.clone().into_iter().collect();
            self.write_commit(
                &mut stream,
                "refs/oxy/export",
                mark,
                &author,
                secs,
                &message,
                &parents,
                &snapshot,
            )?;
            marks.insert(state_ref, mark);
            last_parent = Some(format!(":{mark}"));
            prev = Some((state_ref, state.heads.clone()));
            report.exported += 1;
        }
        if let Some(p) = &last_parent {
            stream.extend_from_slice(format!("reset refs/heads/{branch}\nfrom {p}\n\n").as_bytes());
        }
        // Tags: a tag whose state was exported as a bookmark state points at
        // that commit; otherwise its state gets a commit of its own.
        for t in self.tags()? {
            let target = match (git_states.get(&t.state), marks.get(&t.state)) {
                (Some(sha), _) => sha.clone(),
                (None, Some(m)) => format!(":{m}"),
                (None, None) => {
                    let loaded = self.load_state(&t.heads)?;
                    let snapshot = loaded.materialize();
                    let mark = next_mark;
                    next_mark += 1;
                    let message = format!(
                        "oxy: tag {}\n\n{}Oxy-State: {}\n",
                        t.name,
                        if t.message.is_empty() {
                            String::new()
                        } else {
                            format!("{}\n\n", t.message)
                        },
                        t.state.to_hex()
                    );
                    self.write_commit(
                        &mut stream,
                        "refs/oxy/export",
                        mark,
                        "oxy <oxy@localhost>",
                        Hlc::now().wall_ms / 1000,
                        &message,
                        &[],
                        &snapshot,
                    )?;
                    marks.insert(t.state, mark);
                    report.exported += 1;
                    format!(":{mark}")
                }
            };
            stream.extend_from_slice(
                format!("reset refs/tags/{}\nfrom {target}\n\n", t.name).as_bytes(),
            );
        }
        stream.extend_from_slice(b"done\n");

        let mut cmd = Command::new("git");
        // `--force`: the scratch ref may jump between unrelated states.
        cmd.arg("-C")
            .arg(git_dir)
            .args(["fast-import", "--quiet", "--done", "--force"])
            .arg(format!("--export-marks={}", git_marks.display()));
        if git_marks.exists() {
            cmd.arg(format!("--import-marks={}", git_marks.display()));
        }
        let mut child = cmd
            .stdin(Stdio::piped())
            .stdout(Stdio::null())
            .stderr(Stdio::piped())
            .spawn()
            .map_err(|e| RepoError::Msg(format!("running git fast-import: {e}")))?;
        child.stdin.take().unwrap().write_all(&stream)?;
        let out = child.wait_with_output()?;
        if !out.status.success() {
            return fail(format!(
                "git fast-import failed: {}",
                String::from_utf8_lossy(&out.stderr).trim()
            ));
        }
        let text: String = marks
            .iter()
            .map(|(h, m)| format!("{} {m}\n", h.to_hex()))
            .collect();
        write_atomic(&oxy_marks_path, text.as_bytes())?;
        let _ = git(git_dir, &["update-ref", "-d", "refs/oxy/export"]);
        report.skipped_subrepos = self.git_export_skipped.replace(0);
        Ok(report)
    }

    /// Import branch `branch` of the Git repository at `git_dir` into this
    /// (empty) repository's bookmark (spec §23): one change per commit, its
    /// edits the difference between the union of its parents' states and its
    /// tree, so merge commits become resolutions. Submodules are skipped.
    pub fn import_git(&self, git_dir: &Path, branch: &str) -> Result<GitImportReport> {
        self.import_git_with(git_dir, branch, &mut |_| {})
    }

    /// `import_git`, telling `progress` where it is every few hundred
    /// commits: the count so far, the merges, and the commit in hand, so a
    /// long import is never silent and a run that dies says where.
    pub fn import_git_with(
        &self,
        git_dir: &Path,
        branch: &str,
        progress: crate::store::Progress<'_>,
    ) -> Result<GitImportReport> {
        if !self.bookmark_heads()?.is_empty() {
            return fail("git import needs an empty bookmark; import into a fresh repository");
        }
        self.import_git_commits(
            git_dir,
            branch,
            &format!("oxy git import {} {branch}", git_dir.display()),
            progress,
        )
    }

    /// Import the commits of `branch` that the bookmark does not have yet,
    /// then move the bookmark to the union of its heads and theirs.
    fn import_git_commits(
        &self,
        git_dir: &Path,
        branch: &str,
        command: &str,
        progress: crate::store::Progress<'_>,
    ) -> Result<GitImportReport> {
        let batch = self.store.begin_batch()?;
        let result = self.import_git_commits_batched(git_dir, branch, command, progress);
        batch.finish()?;
        result
    }

    fn import_git_commits_batched(
        &self,
        git_dir: &Path,
        branch: &str,
        command: &str,
        progress: crate::store::Progress<'_>,
    ) -> Result<GitImportReport> {
        let commits = list_commits(git_dir, branch)?;
        let mut cat = CatFile::start(git_dir)?;
        let mut report = GitImportReport::default();
        let mut known = self.git_known(git_dir)?;
        let old_heads = self.bookmark_heads()?;
        // The bookmark's heads as changes arrive: a change stops being a
        // head when another depends on it, so no full state of every
        // imported change is needed at the end.
        let mut heads_now: BTreeSet<ChangeHash> = old_heads.iter().copied().collect();
        // The state and Git tree of imported commits whose first-parent
        // children are still to come, so a child starts from its parent's
        // state instead of rebuilding it from history. The last child takes
        // it; earlier ones clone it. At most `max_kept` are kept (a later
        // child of an evicted one rebuilds).
        // OXY_IMPORT_KEEP overrides it, for measuring.
        let max_kept: usize = std::env::var("OXY_IMPORT_KEEP")
            .ok()
            .and_then(|v| v.parse().ok())
            .unwrap_or(8);
        let mut waiting: HashMap<&str, usize> = HashMap::new();
        for gc in &commits {
            if let Some(p1) = gc.parents.first() {
                *waiting.entry(p1.as_str()).or_default() += 1;
            }
        }
        type Kept = (State, BTreeMap<String, (String, String)>);
        let mut kept: HashMap<String, Kept> = HashMap::new();
        // Every commit to import that has a parent, diffed against its first.
        let pairs: Vec<(String, String)> = commits
            .iter()
            .filter(|gc| {
                !known.imported.contains_key(&gc.sha) && !known.exported.contains_key(&gc.sha)
            })
            .filter_map(|gc| Some((gc.sha.clone(), gc.parents.first()?.clone())))
            .collect();
        let mut diffs = DiffTree::start(git_dir, pairs)?;
        let mut rebuilt = 0usize;
        let mut kept_order: std::collections::VecDeque<String> = std::collections::VecDeque::new();
        let mut last: Option<String> = None;
        let mut blob_cache: HashMap<String, Vec<u8>> = HashMap::new();
        let mut cache_bytes: usize = 0;
        // Time spent per phase over all commits (`OXY_TIMINGS=1`).
        let mut spent = [std::time::Duration::ZERO; 6];
        let mut clock = std::time::Instant::now();
        // One line per commit on stderr with OXY_IMPORT_TRACE=1: where its
        // base came from, what a merge added, the graphs its state holds,
        // the kept states and the process's resident memory.
        let trace = std::env::var_os("OXY_IMPORT_TRACE").is_some();
        let rss_mb = || -> u64 {
            std::fs::read_to_string("/proc/self/statm")
                .ok()
                .and_then(|s| s.split_whitespace().nth(1)?.parse::<u64>().ok())
                .map(|pages| pages * 4096 >> 20)
                .unwrap_or(0)
        };
        let mut done = 0usize;
        // Atoms a kept state's graphs may hold before they are shed;
        // OXY_IMPORT_KEPT_ATOMS overrides it, for measuring.
        let kept_atoms: usize = std::env::var("OXY_IMPORT_KEPT_ATOMS")
            .ok()
            .and_then(|v| v.parse().ok())
            .unwrap_or(KEPT_ATOMS);
        // Graphs turned back into history (see `State::shed_graphs`).
        let mut shed = 0usize;
        let mut lap = |i: usize, clock: &mut std::time::Instant| {
            let now = std::time::Instant::now();
            spent[i] += now - *clock;
            *clock = now;
        };

        // OXY_IMPORT_CHECKPOINT overrides it, for testing.
        let checkpoint_every: usize = std::env::var("OXY_IMPORT_CHECKPOINT")
            .ok()
            .and_then(|v| v.parse().ok())
            .filter(|n| *n > 0)
            .unwrap_or(CHECKPOINT_COMMITS);
        // OXY_IMPORT_STOP_AFTER ends the import cleanly after that many
        // commits, its timings reported, for measuring at depth.
        let stop_after: Option<usize> = std::env::var("OXY_IMPORT_STOP_AFTER")
            .ok()
            .and_then(|v| v.parse().ok());
        let whole_merges = std::env::var_os("OXY_IMPORT_WHOLE_MERGES").filter(|v| v != "0");
        let total = commits.len();
        for (index, gc) in commits.iter().enumerate() {
            if known.imported.contains_key(&gc.sha) || known.exported.contains_key(&gc.sha) {
                continue;
            }
            if stop_after.is_some_and(|n| done >= n) {
                break;
            }
            let commit_started = std::time::Instant::now();
            if index % 500 == 0 {
                progress(&format!(
                    "{index} of {total} commits, {} merges; at {} {}",
                    report.merges,
                    &gc.sha[..12.min(gc.sha.len())],
                    gc.message
                        .lines()
                        .next()
                        .unwrap_or("")
                        .chars()
                        .take(60)
                        .collect::<String>()
                ));
            }
            let mut base_how = "root";
            // Base: union of every parent's state, starting from the first
            // parent's kept state when there is one; its tree tells which
            // paths this commit leaves alone.
            let (mut base, prev_tree) = match gc.parents.first() {
                Some(p1) => {
                    let left = waiting.get_mut(p1.as_str()).map(|n| {
                        *n -= 1;
                        *n
                    });
                    let found = if left == Some(0) {
                        kept_order.retain(|k| k != p1);
                        kept.remove(p1.as_str())
                    } else {
                        kept.get(p1.as_str()).cloned()
                    };
                    let how = match (&found, left) {
                        (Some(_), Some(0)) => "kept",
                        (Some(_), _) => "cloned",
                        (None, _) => "rebuilt",
                    };
                    if trace {
                        base_how = how;
                    }
                    match found {
                        Some((st, tree)) => (st, Some(tree)),
                        None => {
                            // History only: graphs are built for the files a
                            // commit changes, so memory follows what changes,
                            // not the whole tree.
                            let mut st = State::new_history_only();
                            self.add_git_ancestors(&mut st, git_dir, &[p1.as_str()], &known)?;
                            // The parent's tree, so this commit still
                            // renders only what it changes.
                            rebuilt += 1;
                            (st, Some(list_tree(git_dir, p1)?))
                        }
                    }
                }
                None => (State::new_history_only(), None),
            };
            // Nodes the other parents' changes touch: the first parent's
            // tree cannot vouch for them.
            let mut touched: HashSet<NodeId> = HashSet::new();
            let mut merged = 0usize;
            // Where the first parent has each node, read before the merged
            // changes move anything: a merge's partial build names the paths
            // they touch in the first parent's tree as well as in the merged
            // state (oxygen#80).
            let mut first_parent_view: Option<crate::tree::TreeView> = None;
            if gc.parents.len() > 1 {
                report.merges += 1;
                if prev_tree.is_some() && whole_merges.is_none() {
                    first_parent_view = Some(base.tree().view());
                }
                let mut args: Vec<String> = gc.parents[1..].to_vec();
                args.push(format!("^{}", gc.parents[0]));
                let refs: Vec<&str> = args.iter().map(String::as_str).collect();
                // A merge of a long-lived branch brings thousands of
                // changes: added to built graphs, which kept states share,
                // they were copied and applied whole (vscode's import passed
                // 14 GB on such merges). Shed the graphs first, so the
                // changes go in as skeletons and only what this commit
                // touches is built again.
                if base.built_count() > 0 {
                    let mut count_args = vec!["rev-list", "--count"];
                    count_args.extend(refs.iter().copied());
                    let others: usize = git(git_dir, &count_args)?.trim().parse().unwrap_or(0);
                    if others > MERGE_SHED_COMMITS {
                        shed += base.shed_graphs(|b| self.store_blob(b))?;
                    }
                }
                let before = base.len();
                self.add_git_ancestors_touching(&mut base, git_dir, &refs, &known, &mut touched)?;
                merged = base.len() - before;
            }
            lap(0, &mut clock);
            // The commit's tree: its first parent's with the diff applied,
            // or listed whole when that tree is not kept.
            let diff = match gc.parents.first() {
                Some(_) => Some(diffs.diff(&gc.sha)?),
                None => None,
            };
            let (tree, changed) = match (prev_tree, diff) {
                (Some(mut t), Some(diff)) => {
                    let mut changed: HashSet<String> = HashSet::new();
                    for (path, entry) in diff {
                        match entry {
                            Some(v) => {
                                t.insert(path.clone(), v);
                            }
                            None => {
                                t.remove(&path);
                            }
                        }
                        changed.insert(path);
                    }
                    (t, Some(changed))
                }
                _ => (list_tree(git_dir, &gc.sha)?, None),
            };
            lap(1, &mut clock);
            // Text files with the same blob and mode as in the first
            // parent's tree equal the base's rendering: they are neither
            // rendered nor read nor compared (spec §12.3, as for a clean
            // working copy), so a commit costs what it changes.
            let mut same: HashMap<&str, NodeId> = HashMap::new();
            // Opaque files and symlinks likewise, when the base has one
            // blob for them: they are neither read nor stored again.
            let mut same_opaque: HashSet<&str> = HashSet::new();
            // An ordinary commit in a tree without submodules is built from
            // the paths it changes alone (oxygen#25): with the `.oxyattributes`
            // files that decide how they are stored, and the directories its
            // removals may leave empty. A merge, or a commit whose parent's
            // tree is not at hand, is built from its whole tree.
            // A merge can differ from its first parent only at the paths
            // Git's diff names and where the merged changes touched: those
            // paths in the first parent's tree and in the merged state. With
            // them added it is built like an ordinary commit, instead of
            // from its whole tree (18 s for any merge at 118k commits of
            // VS Code, oxygen#80). OXY_IMPORT_WHOLE_MERGES=1 restores the
            // whole-tree path, for comparing.
            let mut changed = changed;
            // A tree conflict in the merged state (both sides placed a file
            // at one path) is resolved by the whole-tree path.
            let mut merge_how = if gc.parents.len() > 1 {
                if first_parent_view.is_some() {
                    "partial"
                } else {
                    "whole"
                }
            } else {
                "-"
            };
            // Only a conflict among what the merged changes touched; one
            // elsewhere stays as it was in the first parent either way.
            if first_parent_view.is_some()
                && base.tree().view().conflicts.iter().any(|c| {
                    use crate::tree::TreeConflict::*;
                    match c {
                        Name { nodes, .. } => nodes.iter().any(|n| touched.contains(n)),
                        MultiPlacement { node, .. } | Cycle { node } | Mode { node, .. } => {
                            touched.contains(node)
                        }
                        Orphan { node, parent } => {
                            touched.contains(node) || touched.contains(parent)
                        }
                    }
                })
            {
                first_parent_view = None;
                merge_how = "conflicted";
            }
            if let (Some(ch), Some(fp)) = (changed.as_mut(), &first_parent_view) {
                let union = base.tree().view();
                for v in [fp, &union] {
                    for (path, e) in v.entries.iter() {
                        if touched.contains(&e.node) {
                            ch.insert(path.clone());
                        }
                    }
                }
            }
            let partial = changed.is_some()
                && (gc.parents.len() == 1 || first_parent_view.is_some())
                && !tree.values().any(|(mode, _)| mode == "160000");
            let mut rel: BTreeSet<&str> = BTreeSet::new();
            // Text files whose graphs this commit builds, for the trace.
            let need_n: usize;
            let base_snapshot = if let (true, Some(changed)) = (partial, &changed) {
                let view = base.tree().view();
                rel.extend(changed.iter().map(String::as_str));
                rel.extend(
                    tree.keys()
                        .map(String::as_str)
                        .filter(|p| *p == ".oxyattributes" || p.ends_with("/.oxyattributes")),
                );
                let mut dirs: BTreeSet<&str> = BTreeSet::new();
                for p in changed.iter().filter(|p| !tree.contains_key(*p)) {
                    let mut end = p.len();
                    while let Some(i) = p[..end].rfind('/') {
                        if !dirs.insert(&p[..i]) {
                            break;
                        }
                        end = i;
                    }
                }
                let need: Vec<NodeId> = rel
                    .iter()
                    .filter_map(|p| view.entries.get(*p))
                    .filter(|e| e.kind == NodeKind::File && !e.mode.opaque)
                    .map(|e| e.node)
                    .collect();
                crate::timing::add("render: same and need", clock.elapsed());
                need_n = need.len();
                let t = std::time::Instant::now();
                self.load_graphs_of(&mut base, &need)?;
                crate::timing::add("render: load graphs", t.elapsed());
                let t = std::time::Instant::now();
                let snap = base.materialize_paths(view, rel.iter().chain(dirs.iter()).copied());
                crate::timing::add("render: materialize", t.elapsed());
                snap
            } else {
                if let Some(changed) = &changed {
                    let view = base.tree().view();
                    for path in tree.keys() {
                        // Submodule handling reads these two whatever changed.
                        if changed.contains(path) || path == ".gitmodules" || path == ".oxymodules"
                        {
                            continue;
                        }
                        if let Some(e) = view.entries.get(path) {
                            if touched.contains(&e.node) {
                                continue;
                            }
                            let opaque = e.kind == NodeKind::Symlink
                                || (e.kind == NodeKind::File && e.mode.opaque);
                            if e.kind == NodeKind::File && !e.mode.opaque {
                                same.insert(path.as_str(), e.node);
                            } else if opaque && base.live_blobs(&e.node).len() == 1 {
                                same_opaque.insert(path.as_str());
                            }
                        }
                    }
                }
                // Build the graphs of every text file the commit may change.
                let skip: HashSet<NodeId> = same.values().copied().collect();
                let need: Vec<NodeId> = base
                    .tree()
                    .view()
                    .entries
                    .values()
                    .filter(|e| {
                        e.kind == NodeKind::File && !e.mode.opaque && !skip.contains(&e.node)
                    })
                    .map(|e| e.node)
                    .collect();
                crate::timing::add("render: same and need", clock.elapsed());
                need_n = need.len();
                let t = std::time::Instant::now();
                let snap = if need.len() > merge_batch() {
                    // A merge onto a base with no built graphs: thousands
                    // of files, whose graphs would not fit at once.
                    self.materialize_batched(&mut base, &need, &skip)?
                } else {
                    let g = std::time::Instant::now();
                    self.load_graphs_of(&mut base, &need)?;
                    crate::timing::add("render: whole, load graphs", g.elapsed());
                    let m = std::time::Instant::now();
                    let snap = base.materialize_except(&skip);
                    crate::timing::add("render: whole, materialize", m.elapsed());
                    snap
                };
                crate::timing::add("render: whole tree", t.elapsed());
                snap
            };

            lap(2, &mut clock);
            // The commit's tree as in-memory entries.
            let mut entries: BTreeMap<String, FsEntry> = BTreeMap::new();
            let mut gitlinks: Vec<(String, String)> = Vec::new();
            let listed: Box<dyn Iterator<Item = (&String, &(String, String))>> = if partial {
                Box::new(rel.iter().filter_map(|p| tree.get_key_value(*p)))
            } else {
                Box::new(tree.iter())
            };
            for (path, (mode, sha)) in listed {
                let (path, sha) = (path.clone(), sha.clone());
                let (kind, exec) = match mode.as_str() {
                    "100644" | "100664" => (NodeKind::File, false),
                    "100755" => (NodeKind::File, true),
                    "120000" => (NodeKind::Symlink, false),
                    "160000" => {
                        gitlinks.push((path, sha));
                        continue;
                    }
                    _ => continue,
                };
                if same.contains_key(path.as_str()) || same_opaque.contains(path.as_str()) {
                    let mut e = FsEntry::new(kind, exec, Vec::new());
                    e.unchanged = true;
                    entries.insert(path, e);
                    continue;
                }
                let content = match blob_cache.get(&sha) {
                    Some(c) => c.clone(),
                    None => {
                        let c = cat.read(&sha)?;
                        if cache_bytes + c.len() > 64 * 1024 * 1024 {
                            blob_cache.clear();
                            cache_bytes = 0;
                        }
                        cache_bytes += c.len();
                        blob_cache.insert(sha.clone(), c.clone());
                        c
                    }
                };
                entries.insert(path, FsEntry::new(kind, exec, content));
            }

            // Submodules (spec §23): gitlinks become subrepo nodes with Git
            // pins, and `.gitmodules` also yields `.oxymodules`.
            if !gitlinks.is_empty() {
                report.submodules += gitlinks.len();
                let gm = entries
                    .get(".gitmodules")
                    .map(|e| {
                        crate::subrepo::Modules::from_gitmodules(&String::from_utf8_lossy(
                            &e.content,
                        ))
                    })
                    .unwrap_or_default();
                let mut modules = entries
                    .get(".oxymodules")
                    .map(|e| crate::subrepo::Modules::parse(&String::from_utf8_lossy(&e.content)))
                    .unwrap_or_default();
                for (path, sha) in &gitlinks {
                    let m = gm.entries.get(path);
                    let branch = m
                        .and_then(|m| m.bookmark.clone())
                        .unwrap_or_else(|| "HEAD".into());
                    entries.insert(
                        path.clone(),
                        FsEntry::new(
                            NodeKind::Subrepo,
                            false,
                            crate::subrepo::Pin::Git {
                                sha: sha.clone(),
                                branch,
                            }
                            .encode(),
                        ),
                    );
                    if let Some(m) = m {
                        modules.entries.insert(path.clone(), m.clone());
                    }
                }
                if !modules.entries.is_empty() {
                    entries.insert(
                        ".oxymodules".into(),
                        FsEntry::new(NodeKind::File, false, modules.to_text().into_bytes()),
                    );
                }
            }
            lap(3, &mut clock);
            // New nodes' identifiers derive from the commit, so importing the
            // same Git history twice gives the same changes (spec §23).
            let seed = *blake3::hash(format!("oxy git import\0{}", gc.sha).as_bytes()).as_bytes();
            let mut built = if partial {
                // Whether the new tree has anything under `dir`.
                let dir_needed = |dir: &str| {
                    let prefix = format!("{dir}/");
                    tree.range(prefix.clone()..)
                        .next()
                        .is_some_and(|(k, _)| k.starts_with(&prefix))
                };
                self.build_from_entries_seeded(
                    &base,
                    &base_snapshot,
                    &entries,
                    seed,
                    Some(&dir_needed),
                )?
            } else {
                self.build_from_entries_seeded(&base, &base_snapshot, &entries, seed, None)?
            };
            lap(4, &mut clock);
            // A file or submodule with several live blobs (branches that
            // replaced it independently) is resolved to the commit's blob:
            // Git's merge is the authority here, unlike a working copy,
            // where a candidate on disk is not yet a decision (spec §23).
            for (path, f) in &base_snapshot.files {
                let (FileContent::Opaque { blobs }, Some(e)) = (&f.content, entries.get(path))
                else {
                    continue;
                };
                if blobs.len() < 2 || f.kind != e.kind {
                    continue;
                }
                let chosen = self.store_blob(&e.content)?;
                for b in blobs {
                    built.edits.push(Edit::Replace {
                        node: f.node,
                        old: Some(*b),
                        new: Some(chosen),
                    });
                }
                built.resolves = true;
                built
                    .contributors
                    .extend(base.live_replaces(&f.node).into_iter().map(|(c, _)| c));
            }
            // It shares the base's tree view, which applying the change
            // then updates in place rather than copying.
            drop(base_snapshot);
            drop(entries);
            let mut deps: BTreeSet<ChangeHash> = built.contributors.iter().copied().collect();
            let mut message = gc.message.clone();
            if !message.ends_with('\n') {
                message.push('\n');
            }
            message.push_str(&format!(
                "\nGit-Commit: {}\nGit-Author: {}\n",
                gc.sha, gc.author
            ));
            let mut change = Change {
                version: crate::objects::CHANGE_VERSION,
                change_id: change_id_for(&gc.sha, &gc.message),
                deps: vec![],
                author: ObjectRef::ZERO,
                hlc: Hlc {
                    wall_ms: gc.author_secs * 1000,
                    logical: 0,
                },
                message,
                tree_ops: built.tree_ops,
                edits: built.edits,
                kind: if built.resolves {
                    ChangeKind::Resolution
                } else {
                    ChangeKind::Normal
                },
            };
            let t = std::time::Instant::now();
            deps.extend(referenced_changes(&change, &base));
            crate::timing::add("store: referenced", t.elapsed());
            change.deps = deps.into_iter().collect();
            change.normalize();
            let hash = self.store.put_change(&change)?;
            for d in &change.deps {
                heads_now.remove(d);
            }
            heads_now.insert(hash);
            // Built graphs take its edits whole; files not built keep only
            // where its text is, read back from the store.
            let t = std::time::Instant::now();
            let (skeleton, texts) = self.store.get_change_lazy(&hash)?;
            base.add_known_mixed(hash, change, skeleton, texts);
            crate::timing::add("store: add to state", t.elapsed());
            known.imported.insert(gc.sha.clone(), hash);
            if waiting.get(gc.sha.as_str()).is_some_and(|n| *n > 0) {
                // A kept state holds its graphs until its children come:
                // past a few thousand, they go back into its history.
                // Past a few thousand graphs, or past a budget of atoms: a
                // long-lived file's graph keeps every line it ever had, so a
                // handful of them can hold gigabytes (#25).
                if base.built_count() > KEPT_GRAPHS || base.built_atoms() > kept_atoms {
                    shed += base.shed_graphs(|b| self.store_blob(b))?;
                }
                kept.insert(gc.sha.clone(), (base, tree));
                kept_order.push_back(gc.sha.clone());
                if kept_order.len() > max_kept {
                    if let Some(old) = kept_order.pop_front() {
                        kept.remove(&old);
                    }
                }
            }
            last = Some(gc.sha.clone());
            report.commits += 1;
            lap(5, &mut clock);
            done += 1;
            if done.is_multiple_of(checkpoint_every) {
                self.checkpoint_import(&heads_now, done)?;
            }
            // A merge renders thousands of files on many threads and frees
            // it all; the allocator keeps those pages unless asked to give
            // them back, and the next merge piles on top (#25).
            let before_trim = if trace { rss_mb() } else { 0 };
            if gc.parents.len() > 1 {
                crate::alloc_stats::release_freed_memory();
            }
            if trace {
                let built = kept
                    .get(gc.sha.as_str())
                    .map(|(st, _)| st.built_count())
                    .unwrap_or(0);
                let (edits, most) = kept
                    .get(gc.sha.as_str())
                    .map(|(st, _)| st.deferred_edit_count())
                    .unwrap_or((0, 0));
                let atoms = kept
                    .get(gc.sha.as_str())
                    .map(|(st, _)| st.built_atoms())
                    .unwrap_or(0);
                eprintln!(
                    "trace {done} {} parents={} base={base_how} merged={merged} built={built} atoms={atoms} kept={} shed={shed} rss_mb={} before_trim_mb={before_trim} deferred_edits={edits} most={most} need={need_n} merge={merge_how} ms={}",
                    &gc.sha[..12.min(gc.sha.len())],
                    gc.parents.len(),
                    kept.len(),
                    rss_mb(),
                    commit_started.elapsed().as_millis()
                );
            }
        }
        for (name, d) in [
            "git import: bases",
            "git import: tree",
            "git import: render base",
            "git import: read blobs",
            "git import: build change",
            "git import: store change",
        ]
        .iter()
        .zip(spent)
        {
            crate::timing::record(name, d);
        }
        crate::timing::report_totals();
        if crate::timing::enabled() {
            eprintln!(
                "timing git import: {rebuilt} bases rebuilt from history, {shed} graphs shed"
            );
        }

        // The bookmark: heads of the old state plus every new change.
        report.heads = old_heads.len();
        if last.is_none() {
            return Ok(report);
        }
        let heads: Vec<ChangeHash> = heads_now.into_iter().collect();
        report.heads = heads.len();
        let (op_ref, op) = self.head_op()?;
        let mut view = op.view.clone();
        let old_state_ref = view.bookmarks.get(&self.config.bookmark).copied();
        let state_ref = self.store.put_state(&StateObject::new(heads.clone()))?;
        view.bookmarks
            .insert(self.config.bookmark.clone(), state_ref);
        self.record_op(&[op_ref], command, view)?;
        // The new state equals the tip's tree when the old one was itself a
        // Git commit's tree (fetched or exported), or there was none.
        let old_known = old_heads.is_empty()
            || old_state_ref.is_some_and(|s| known.exported.values().any(|e| *e == s));
        if let (Some(tip), true) = (commits.last(), old_known) {
            self.record_git_state(git_dir, &state_ref, &tip.sha)?;
        }
        // The working copy follows when it was clean on the old heads.
        if old_heads.is_empty() {
            self.checkout(&heads, true, &format!("{command} (checkout)"))?;
        } else {
            let snap = self.snapshot(command)?;
            let clean = snap.wc.tree_ops.is_empty() && snap.wc.edits.is_empty();
            let mut base = snap.base.maximal(&snap.wc.deps);
            base.sort();
            let mut sorted_old = old_heads.clone();
            sorted_old.sort();
            // An empty base too: an import that stopped after a checkpoint
            // never checked anything out, and resuming it should.
            if clean && (base == sorted_old || base.is_empty()) {
                self.checkout(&heads, false, &format!("{command} (checkout)"))?;
            }
        }
        Ok(report)
    }

    /// Add to `st` the changes of every Git commit `rev-list args` lists:
    /// an imported commit's change, or the whole state an exported commit
    /// was made from (which may hold changes Git never saw).
    fn add_git_ancestors(
        &self,
        st: &mut State,
        git_dir: &Path,
        args: &[&str],
        known: &GitKnown,
    ) -> Result<()> {
        self.add_git_ancestors_touching(st, git_dir, args, known, &mut HashSet::new())
    }

    /// `add_git_ancestors`, also collecting in `touched` every node the
    /// changes it adds edit, place or remove.
    fn add_git_ancestors_touching(
        &self,
        st: &mut State,
        git_dir: &Path,
        args: &[&str],
        known: &GitKnown,
        touched: &mut HashSet<NodeId>,
    ) -> Result<()> {
        let mut full = vec!["rev-list"];
        full.extend(args);
        let out = git(git_dir, &full)?;
        let mut add = |st: &mut State, h: &ChangeHash| -> Result<()> {
            if st.contains(h) {
                return Ok(());
            }
            if !st.is_history_only() {
                let c = self.store.get_change(h)?;
                touched.extend(c.edits.iter().map(|e| e.node()));
                touched.extend(c.tree_ops.iter().map(|o| o.node()));
                st.add_unchecked(c);
                return Ok(());
            }
            // History only: the text of an edit waits unread unless its
            // file's graph is built.
            let (skeleton, texts) = self.store.get_change_lazy(h)?;
            touched.extend(skeleton.edits.iter().map(|e| e.node()));
            touched.extend(skeleton.tree_ops.iter().map(|o| o.node()));
            let built = skeleton
                .edits
                .iter()
                .any(|e| !matches!(e, Edit::Replace { .. }) && st.is_built(&e.node()));
            if built {
                let full = self.store.get_change(h)?;
                st.add_known_mixed(*h, full, skeleton, texts);
            } else {
                st.add_known(*h, skeleton, texts);
            }
            Ok(())
        };
        for sha in out.lines() {
            if let Some(h) = known.imported.get(sha) {
                add(st, h)?;
            } else if let Some(state_ref) = known.exported.get(sha) {
                let heads = self.store.get_state(state_ref)?.heads;
                for h in self.negotiate(&[], &heads)? {
                    add(st, &h)?;
                }
            }
        }
        Ok(())
    }

    /// Point the bookmark at an import's heads so far (see
    /// `CHECKPOINT_COMMITS`); the working copy is left alone until the end.
    fn checkpoint_import(&self, heads: &BTreeSet<ChangeHash>, done: usize) -> Result<()> {
        let heads: Vec<ChangeHash> = heads.iter().copied().collect();
        let (op_ref, op) = self.head_op()?;
        let mut view = op.view.clone();
        let state_ref = self.store.put_state(&StateObject::new(heads))?;
        view.bookmarks
            .insert(self.config.bookmark.clone(), state_ref);
        self.record_op(
            &[op_ref],
            &format!("oxy git import (checkpoint after {done} commits)"),
            view,
        )?;
        Ok(())
    }

    /// Commits this repository can relate to Oxygen history: imported
    /// ones by change, exported ones (through `git_dir`'s marks) by state.
    fn git_known(&self, git_dir: &Path) -> Result<GitKnown> {
        let imported = self.imported_commits()?;
        let marks_dir = self.git_marks_dir(git_dir)?;
        let oxy_marks = Self::read_oxy_marks(&marks_dir.join("oxy-marks"))?;
        let mut sha_of_mark: HashMap<u64, String> = HashMap::new();
        if let Ok(text) = fs::read_to_string(marks_dir.join("git-marks")) {
            for line in text.lines() {
                if let Some((m, sha)) = line.split_once(' ') {
                    if let Ok(m) = m.trim_start_matches(':').parse::<u64>() {
                        sha_of_mark.insert(m, sha.trim().to_string());
                    }
                }
            }
        }
        let mut exported = HashMap::new();
        for (state_ref, m) in oxy_marks {
            if let Some(sha) = sha_of_mark.get(&m) {
                exported.insert(sha.clone(), state_ref);
            }
        }
        for (state_ref, sha) in Self::read_git_states(&marks_dir.join("git-states"))? {
            exported.entry(sha).or_insert(state_ref);
        }
        Ok(GitKnown { imported, exported })
    }

    fn git_author(&self, c: &Change) -> String {
        match self.store.get_identity(&c.author) {
            Ok(id) if !id.name.is_empty() => format!(
                "{} <{}>",
                id.name.replace(['<', '>', '\n'], " "),
                id.email.replace(['<', '>', '\n', ' '], "")
            ),
            _ => "oxy <oxy@localhost>".to_string(),
        }
    }

    #[allow(clippy::too_many_arguments)]
    fn write_commit(
        &self,
        out: &mut Vec<u8>,
        reference: &str,
        mark: u64,
        author: &str,
        secs: u64,
        message: &str,
        parents: &[String],
        snapshot: &Snapshot,
    ) -> Result<()> {
        out.extend_from_slice(format!("commit {reference}\nmark :{mark}\nauthor {author} {secs} +0000\ncommitter {author} {secs} +0000\ndata {}\n{message}\n", message.len()).as_bytes());
        for (i, p) in parents.iter().enumerate() {
            out.extend_from_slice(
                format!("{} {p}\n", if i == 0 { "from" } else { "merge" }).as_bytes(),
            );
        }
        out.extend_from_slice(b"deleteall\n");
        let has_gitmodules = snapshot.files.contains_key(".gitmodules");
        for (path, f) in &snapshot.files {
            if path == ".oxymodules" {
                // Git reads `.gitmodules`; derive it unless the tree has one.
                if !has_gitmodules {
                    if let FileContent::Text { bytes, .. } = &f.content {
                        let gm = crate::subrepo::Modules::parse(&String::from_utf8_lossy(bytes))
                            .to_gitmodules();
                        if !gm.is_empty() {
                            out.extend_from_slice(
                                format!("M 100644 inline .gitmodules\ndata {}\n", gm.len())
                                    .as_bytes(),
                            );
                            out.extend_from_slice(gm.as_bytes());
                            out.push(b'\n');
                        }
                    }
                }
                continue;
            }
            if f.kind == NodeKind::Subrepo {
                if let FileContent::Opaque { blobs } = &f.content {
                    if let Some(b) = blobs.first() {
                        match crate::subrepo::Pin::decode(&self.read_blob(b)?)? {
                            crate::subrepo::Pin::Git { sha, .. } => {
                                out.extend_from_slice(format!("M 160000 {sha} {path}\n").as_bytes())
                            }
                            crate::subrepo::Pin::Oxy { .. } => self
                                .git_export_skipped
                                .set(self.git_export_skipped.get() + 1),
                        }
                    }
                }
                continue;
            }
            let (mode, bytes): (&str, Vec<u8>) = match (&f.kind, &f.content) {
                (NodeKind::Dir, _) => continue,
                (NodeKind::Symlink, FileContent::Opaque { blobs }) => (
                    "120000",
                    blobs
                        .first()
                        .map(|b| self.read_blob(b))
                        .transpose()?
                        .unwrap_or_default(),
                ),
                (_, FileContent::Text { bytes, .. }) => {
                    (if f.mode.exec { "100755" } else { "100644" }, bytes.clone())
                }
                (_, FileContent::Opaque { blobs }) => (
                    if f.mode.exec { "100755" } else { "100644" },
                    blobs
                        .first()
                        .map(|b| self.read_blob(b))
                        .transpose()?
                        .unwrap_or_default(),
                ),
                (_, FileContent::Dir) => continue,
            };
            out.extend_from_slice(
                format!("M {mode} inline {path}\ndata {}\n", bytes.len()).as_bytes(),
            );
            out.extend_from_slice(&bytes);
            out.push(b'\n');
        }
        out.push(b'\n');
        Ok(())
    }
}

/// What `verify_git_import` found (spec §23: import must reproduce every tree).
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct GitVerifyReport {
    pub commits: usize,
    pub files_compared: usize,
    /// `(commit, what differs)`; empty when every commit's tree is reproduced.
    pub mismatches: Vec<(String, String)>,
}

impl Repo {
    /// Check an import against its Git source: for every commit of
    /// `branch`, the state formed by the changes imported for it and all
    /// its ancestors must materialize to exactly that commit's tree, byte
    /// for byte, with the same executable bits, symlink targets and
    /// submodule pins. Reads only; stops listing after 50 differences.
    pub fn verify_git_import(&self, git_dir: &Path, branch: &str) -> Result<GitVerifyReport> {
        let commits = list_commits(git_dir, branch)?;
        let imported = self.imported_commits()?;
        let mut cat = CatFile::start(git_dir)?;
        let mut rep = GitVerifyReport::default();
        // Changes of each commit and all its ancestors, built up in topological order.
        let mut closure: HashMap<String, Arc<BTreeSet<ChangeHash>>> = HashMap::new();
        // Graphs (by key) and blobs already found equal to a Git blob.
        let mut verified_graphs: HashMap<[u8; 32], String> = HashMap::new();
        let mut verified_blobs: HashMap<ObjectRef, String> = HashMap::new();
        // 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();
        for c in &commits {
            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 {
            rep.commits += 1;
            let mut set: BTreeSet<ChangeHash> = BTreeSet::new();
            for p in &c.parents {
                if let Some(ps) = closure.get(p) {
                    set.extend(ps.iter().copied());
                }
            }
            match imported.get(&c.sha) {
                Some(h) => {
                    set.insert(*h);
                }
                None => {
                    rep.mismatches.push((
                        c.sha.clone(),
                        "no imported change carries this commit".into(),
                    ));
                }
            }
            let set = Arc::new(set);
            closure.insert(c.sha.clone(), set.clone());
            if rep.mismatches.len() >= 50 {
                break;
            }
            let heads: Vec<ChangeHash> = set.iter().copied().collect();
            // History only: a file whose graph (by key) or blob was already
            // found equal to this Git blob is not built, rendered or read
            // again; the rest are.
            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 view = state.tree().view();
            let tree = list_tree(git_dir, &c.sha)?;
            let short = &c.sha[..12.min(c.sha.len())];
            let mut differ = |what: String| rep.mismatches.push((c.sha.clone(), what));
            let mut conflicted: Vec<String> =
                view.conflicts.iter().map(|c| format!("{c:?}")).collect();
            let mut need: Vec<NodeId> = Vec::new();
            for (path, (mode, sha)) in &tree {
                let Some(e) = view.entries.get(path) else {
                    continue;
                };
                if mode != "160000"
                    && mode != "120000"
                    && e.kind == NodeKind::File
                    && !e.mode.opaque
                {
                    let known = state
                        .graph_key(&e.node)
                        .is_some_and(|k| verified_graphs.get(&k) == Some(sha));
                    if !known {
                        need.push(e.node);
                    }
                }
            }
            // A graph's key is known only before it is built.
            let keys: HashMap<NodeId, [u8; 32]> = need
                .iter()
                .filter_map(|n| Some((*n, state.graph_key(n)?)))
                .collect();
            let need_set: HashSet<NodeId> = need.iter().copied().collect();
            let graphs = self.build_graphs_detached(&state, &need)?;
            for (path, (mode, sha)) in &tree {
                let Some(e) = view.entries.get(path) else {
                    differ(format!("{short}: {path} is missing"));
                    continue;
                };
                rep.files_compared += 1;
                match mode.as_str() {
                    "160000" => {
                        let blobs = state.live_blobs(&e.node);
                        match (e.kind, blobs.as_slice()) {
                            (NodeKind::Subrepo, [b]) => {
                                let pin = crate::subrepo::Pin::decode(&self.read_blob(b)?)?;
                                if !matches!(&pin, crate::subrepo::Pin::Git { sha: s, .. } if s == sha)
                                {
                                    differ(format!("{short}: {path} pins another commit"));
                                }
                            }
                            (kind, _) => differ(format!(
                                "{short}: {path} is not one submodule pin: {kind:?} with {} pins",
                                blobs.len()
                            )),
                        }
                    }
                    "120000" => {
                        let target = cat.read(sha)?;
                        let blobs = state.live_blobs(&e.node);
                        match (e.kind, blobs.as_slice()) {
                            (NodeKind::Symlink, [b]) if self.read_blob(b)? == target => {}
                            _ => differ(format!("{short}: symlink {path} differs")),
                        }
                    }
                    _ => {
                        if e.mode.exec != (mode == "100755") {
                            differ(format!("{short}: {path} executable bit differs"));
                        }
                        if e.kind == NodeKind::File && !e.mode.opaque {
                            if !need_set.contains(&e.node) {
                                // Known equal: skipped when the graphs were chosen.
                                continue;
                            }
                            let (have, m) = match graphs.get(&e.node) {
                                Some(g) => state.render_graph(g),
                                None => (Vec::new(), Default::default()),
                            };
                            if m.is_conflicted() {
                                // 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
                                    .conflict_regions(&e.node)
                                    .contributors
                                    .iter()
                                    .filter_map(|h| state.get(h))
                                    .map(|m| {
                                        let sha = m
                                            .message
                                            .lines()
                                            .rev()
                                            .find_map(|l| l.strip_prefix("Git-Commit: "))
                                            .unwrap_or("?");
                                        format!(
                                            "{} {:?}",
                                            &sha[..12.min(sha.len())],
                                            m.message.lines().next().unwrap_or("")
                                        )
                                    })
                                    .collect();
                                conflicted.push(format!("{path} between {}", who.join(" and ")));
                            }
                            let want = cat.read(sha)?;
                            if have != want {
                                differ(format!(
                                    "{short}: {path} differs: {}",
                                    first_difference(&have, &want)
                                ));
                            } else if !m.is_conflicted() {
                                if let Some(k) = keys.get(&e.node) {
                                    verified_graphs.insert(*k, sha.clone());
                                }
                            }
                            continue;
                        }
                        let blobs = state.live_blobs(&e.node);
                        let [b] = blobs.as_slice() else {
                            differ(format!("{short}: {path} is not one file"));
                            continue;
                        };
                        if verified_blobs.get(b) == Some(sha) {
                            continue;
                        }
                        if self.read_blob(b)? != cat.read(sha)? {
                            differ(format!("{short}: {path} differs"));
                        } else {
                            verified_blobs.insert(*b, sha.clone());
                        }
                    }
                }
            }
            if !conflicted.is_empty() {
                differ(format!(
                    "{short}: the state is conflicted: {}",
                    conflicted.join("; ")
                ));
            }
            // Import records submodules in `.oxymodules` as well (spec §23),
            // and export leaves it out again.
            let has_submodules = tree.values().any(|(m, _)| m == "160000");
            for (path, e) in view.entries.iter() {
                if e.kind != NodeKind::Dir
                    && !tree.contains_key(path)
                    && !(has_submodules && path == ".oxymodules")
                {
                    differ(format!("{short}: {path} is extra"));
                }
            }
            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);
                    }
                }
            }
            if rep.mismatches.len() >= 50 {
                break;
            }
        }
        Ok(rep)
    }
}

/// Where two versions of a file first part, for a verification report.
fn first_difference(have: &[u8], want: &[u8]) -> String {
    let (h, w): (Vec<&[u8]>, Vec<&[u8]>) = (
        have.split(|b| *b == b'\n').collect(),
        want.split(|b| *b == b'\n').collect(),
    );
    let i = h
        .iter()
        .zip(&w)
        .position(|(a, b)| a != b)
        .unwrap_or(h.len().min(w.len()));
    let show = |l: Option<&&[u8]>| {
        l.map(|l| String::from_utf8_lossy(&l[..l.len().min(60)]).into_owned())
            .unwrap_or_else(|| "(end)".into())
    };
    format!(
        "line {}: has {:?}, Git has {:?} ({} lines, Git has {})",
        i + 1,
        show(h.get(i)),
        show(w.get(i)),
        h.len(),
        w.len()
    )
}
`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet
Keyboard
