git_export_graph: a deterministic Git export from the change graph, for the hub's Git view (refs andymccall/oxygenhub#355) 6f4226bfb87f

- **Added: a Git export from the change graph (oxygenhub#355).** oxy-core's `git_export_graph` writes every bookmark and tag to a bare Git repository so that the same changes give the same commits wherever it runs: each change a commit whose parents are its dependencies, each bookmark a branch (a merge of its heads when it has several), tags as tags, incrementally. It is what OxygenHub serves to `git clone`. (`oxy git export` still follows the checkout's own history.)

        self.git_author_key(&c.author)

}

/// What `git_export_graph` wrote.

#[derive(Debug, Clone, Default, PartialEq, Eq)]

pub struct GitGraphReport {

    /// Changes written as commits this time (the rest were exported before).

    pub commits: usize,

    /// Branches and tags pointed at their commits.

    pub branches: usize,

    pub tags: usize,

    /// Bookmarks or tags whose names Git does not take as refs.

    pub skipped_refs: Vec<String>,

    /// Subrepo nodes with Oxygen pins, which Git cannot represent.

    pub skipped_subrepos: usize,

}

/// A bookmark or tag name Git takes as a ref without escaping.

fn git_ref_ok(name: &str) -> bool {

    !name.is_empty()

        && !name.starts_with(['-', '/', '.'])

        && !name.ends_with(['/', '.'])

        && !name.contains("..")

        && !name.contains("//")

        && !name.ends_with(".lock")

        && name

            .bytes()

            .all(|b| b.is_ascii_alphanumeric() || b"-_./+".contains(&b))

}

impl Repo {

    /// Export every bookmark and tag to the bare Git repository at

    /// `git_dir` from the change graph (spec §23, oxygenhub D1), for a hub

    /// to serve to Git clients. Unlike `git_export`, which follows one

    /// checkout's operation log, this depends only on the changes, so the

    /// same changes give the same Git commits wherever it runs:

    ///

    /// - each change is a commit whose tree is the state of the change and

    ///   everything it depends on, whose parents are its dependencies'

    ///   commits, with the change's author, time and message and its

    ///   `Change-Id:` and `Oxy-Hash:` trailers (a change that depends on

    ///   nothing is a root, so Git sees Oxygen's dependencies, not the order

    ///   changes were made in);

    /// - a bookmark with one head is a branch at that head's commit; with

    ///   several, a merge of their commits whose tree is the bookmark's

    ///   state, at the newest head's time;

    /// - a tag points at its heads' commit, or such a merge.

    ///

    /// Commits already exported are remembered (marks), so a later run

    /// writes only new changes. Branches for bookmarks that are gone are

    /// deleted.

    pub fn git_export_graph(&self, git_dir: &Path) -> Result<GitGraphReport> {

        if !git_dir.join("HEAD").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 graph_marks = marks_dir.join("graph-marks");

        let mut marks = Self::read_oxy_marks(&graph_marks)?;

        let mut next = marks.values().copied().max().unwrap_or(0) + 1;

        let mut report = GitGraphReport::default();

        let mut stream: Vec<u8> = Vec::new();

        let mut refs: Vec<(String, Vec<ChangeHash>)> = Vec::new();

        for b in self.bookmarks()? {

            if git_ref_ok(&b.name) {

                refs.push((format!("refs/heads/{}", b.name), b.heads));

            } else {

                report.skipped_refs.push(b.name);

            }

        }

        let tags = self.tags()?;

        for t in &tags {

            if git_ref_ok(&t.name) {

                refs.push((format!("refs/tags/{}", t.name), t.heads.clone()));

            } else {

                report.skipped_refs.push(t.name.clone());

            }

        }

        // Every change the refs reach, dependencies before dependents: a

        // depth-first walk in hash order, so the order is the same everywhere.

        let mut order: Vec<ChangeHash> = Vec::new();

        let mut seen: HashSet<ChangeHash> = HashSet::new();

        let mut metas: HashMap<ChangeHash, crate::state::ChangeMeta> = HashMap::new();

        let mut roots: Vec<ChangeHash> = refs.iter().flat_map(|(_, h)| h.iter().copied()).collect();

        roots.sort();

        roots.dedup();

        for root in roots {

            if !seen.insert(root) {

                continue;

            }

            let mut stack: Vec<(ChangeHash, bool)> = vec![(root, false)];

            while let Some((h, done)) = stack.pop() {

                if done {

                    order.push(h);

                    continue;

                }

                stack.push((h, true));

                let meta = self.store.get_change_meta(&h)?;

                let mut deps = meta.deps.clone();

                deps.sort();

                for d in deps.into_iter().rev() {

                    if seen.insert(d) {

                        stack.push((d, false));

                    }

                }

                metas.insert(h, meta);

            }

        }

        for h in &order {

            if marks.contains_key(h) {

                continue;

            }

            let meta = &metas[h];

            let snapshot = self.load_state(&[*h])?.materialize();

            let mut message = meta.message.clone();

            if !message.ends_with('\n') {

                message.push('\n');

            }

            message.push_str(&format!(

                "\nChange-Id: {}\nOxy-Hash: {}\n",

                meta.change_id.to_hex(),

                h.to_hex()

            ));

            if snapshot.is_conflicted() {

                message.push_str("Oxy-Conflicted: true\n");

            }

            let mut deps = meta.deps.clone();

            deps.sort();

            let parents: Vec<String> = deps

                .iter()

                .filter_map(|d| marks.get(d))

                .map(|m| format!(":{m}"))

                .collect();

            let mark = next;

            next += 1;

            if parents.is_empty() {

                // Without `from`, fast-import would make the scratch ref's

                // tip its parent; a change that depends on nothing is a root.

                stream.extend_from_slice(b"reset refs/oxy/export\n\n");

            }

            self.write_commit(

                &mut stream,

                "refs/oxy/export",

                mark,

                &self.git_author_key(&meta.author),

                meta.hlc.wall_ms / 1000,

                &message,

                &parents,

                &snapshot,

            )?;

            marks.insert(*h, mark);

            report.commits += 1;

        }

        let mut wanted: HashSet<String> = HashSet::new();

        for (name, heads) in &refs {

            let mut heads = heads.clone();

            heads.sort();

            heads.dedup();

            let target = match heads.as_slice() {

                [] => continue,

                [one] => format!(":{}", marks[one]),

                many => {

                    // A merge of the heads, named by them so it is made once.

                    let key = hash_object(

                        ObjectType::Chunk,

                        many.iter()

                            .map(|h| h.to_hex())

                            .collect::<Vec<_>>()

                            .join(" ")

                            .as_bytes(),

                    );

                    if let Some(m) = marks.get(&key) {

                        format!(":{m}")

                    } else {

                        let snapshot = self.load_state(many)?.materialize();

                        let newest = many.iter().map(|h| metas[h].hlc.wall_ms).max().unwrap_or(0);

                        let mut message = format!(

                            "Merge of {} heads\n\nOxy-Heads: {}\n",

                            many.len(),

                            many.iter()

                                .map(|h| h.to_hex())

                                .collect::<Vec<_>>()

                                .join(" ")

                        );

                        if snapshot.is_conflicted() {

                            message.push_str("Oxy-Conflicted: true\n");

                        }

                        let parents: Vec<String> =

                            many.iter().map(|h| format!(":{}", marks[h])).collect();

                        let mark = next;

                        next += 1;

                        self.write_commit(

                            &mut stream,

                            "refs/oxy/export",

                            mark,

                            "oxy <oxy@localhost>",

                            newest / 1000,

                            &message,

                            &parents,

                            &snapshot,

                        )?;

                        marks.insert(key, mark);

                        format!(":{mark}")

                    }

                }

            };

            stream.extend_from_slice(format!("reset {name}\nfrom {target}\n\n").as_bytes());

            wanted.insert(name.clone());

            if name.starts_with("refs/tags/") {

                report.tags += 1;

            } else {

                report.branches += 1;

            }

        }

        stream.extend_from_slice(b"done\n");

        run_fast_import(git_dir, &stream, &git_marks)?;

        let text: String = marks

            .iter()

            .map(|(h, m)| format!("{} {m}\n", h.to_hex()))

            .collect();

        write_atomic(&graph_marks, text.as_bytes())?;

        let _ = git(git_dir, &["update-ref", "-d", "refs/oxy/export"]);

        // Branches and tags of bookmarks and tags that are gone.

        let listed = git(

            git_dir,

            &[

                "for-each-ref",

                "--format=%(refname)",

                "refs/heads",

                "refs/tags",

            ],

        )?;

        for r in listed

            .lines()

            .map(str::trim)

            .filter(|r| !r.is_empty() && !wanted.contains(*r))

        {

            git(git_dir, &["update-ref", "-d", r])?;

        }

        // HEAD names the main bookmark when there is one, so a clone checks it out.

        let main = ["main", "master", "trunk", "develop"]

            .into_iter()

            .find(|b| wanted.contains(&format!("refs/heads/{b}")));

        if let Some(b) = main {

            git(

                git_dir,

                &["symbolic-ref", "HEAD", &format!("refs/heads/{b}")],

            )?;

        }

        report.skipped_subrepos = self.git_export_skipped.replace(0);

        Ok(report)

    }

    /// `Name <email>` for a Git commit, from the author's identity.

    fn git_author_key(&self, key: &KeyId) -> String {

        match self.store.get_identity(key) {

            Ok(id) if !id.name.is_empty() => format!(

                "{} <{}>",

                id.name.replace(['<', '>', '\n'], " "),

                id.email.replace(['<', '>', '\n', ' '], "")

            ),

            _ => "oxy <oxy@localhost>".to_string(),

        }

    }

}

/// Feed a fast-import stream to `git fast-import` in `git_dir`, keeping its

/// marks in `git_marks` so a later run can refer to commits it wrote.

fn run_fast_import(git_dir: &Path, stream: &[u8], git_marks: &Path) -> Result<()> {

    let mut cmd = Command::new("git");

    // `--force`: a ref may move to an unrelated commit (a bookmark rewritten).

    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()

        ));

    }

    Ok(())

#[test]

fn git_export_graph_is_deterministic_and_merges_heads() {

    hermetic();

    if std::process::Command::new("git")

        .arg("--version")

        .output()

        .is_err()

    {

        eprintln!("git not installed; skipping");

        return;

    }

    let dir = tempfile::tempdir().unwrap();

    let root = dir.path();

    let mut repo = Repo::init(&root.join("r"))

        .unwrap()

        .with_home(root.join("home"));

    repo.create_identity("Ada Lovelace", "[email protected]", IdentityScope::User)

        .unwrap();

    let r = root.join("r");

    write(&r, "README.md", b"hello\n");

    let h1 = repo.commit("first", &[]).unwrap();

    write(&r, "README.md", b"hello\nworld\n");

    write(&r, "src/main.rs", b"fn main() {}\n");

    let h2 = repo.commit("second", &[]).unwrap();

    repo.tag_create("v1", &[h2], "the first release").unwrap();

    // An independent change: main gets two heads.

    repo.checkout(&[h1], false, "checkout").unwrap();

    write(&r, "other.txt", b"o\n");

    let h3 = repo.commit("third", &[]).unwrap();

    repo.bookmark_create("gone", Some(&[h1])).unwrap();

    let git = |git_dir: &Path, args: &[&str]| -> String {

        let out = std::process::Command::new("git")

            .arg("-C")

            .arg(git_dir)

            .args(args)

            .output()

            .unwrap();

        assert!(

            out.status.success(),

            "git {args:?}: {}",

            String::from_utf8_lossy(&out.stderr)

        );

        String::from_utf8_lossy(&out.stdout).trim().to_string()

    };

    let a = root.join("a.git");

    let rep = repo.git_export_graph(&a).unwrap();

    assert_eq!((rep.commits, rep.tags), (3, 1), "{rep:?}");

    assert_eq!(rep.branches, 2, "main and gone: {rep:?}");

    // Each change is a commit whose parents are exactly its dependencies'

    // commits (Oxygen's dependencies, not the order changes were made in).

    let by_hash = |hash: ChangeHash| {

        git(

            &a,

            &[

                "log",

                "--all",

                "--format=%H",

                &format!("--grep=Oxy-Hash: {}", hash.to_hex()),

            ],

        )

    };

    let (c1, c2, c3) = (by_hash(h1), by_hash(h2), by_hash(h3));

    for (h, c) in [(h1, &c1), (h2, &c2), (h3, &c3)] {

        let mut want: Vec<String> = repo

            .store()

            .get_change_meta(&h)

            .unwrap()

            .deps

            .iter()

            .map(|d| by_hash(*d))

            .collect();

        want.sort();

        let mut have: Vec<String> = git(&a, &["rev-list", "--parents", "-1", c])

            .split(' ')

            .skip(1)

            .map(String::from)

            .collect();

        have.sort();

        assert_eq!(have, want, "{h:?}'s commit's parents");

    }

    assert!(

        !repo.store().get_change_meta(&h2).unwrap().deps.is_empty(),

        "second edits first's README"

    );

    assert_eq!(

        git(&a, &["show", &format!("{c2}:src/main.rs")]),

        "fn main() {}"

    );

    assert!(

        git(&a, &["ls-tree", "--name-only", &c3])

            .lines()

            .all(|l| l != "src"),

        "a change's tree is its own closure, not the bookmark's"

    );

    assert_eq!(

        git(&a, &["log", "-1", "--format=%an <%ae>", &c1]),

        "Ada Lovelace <[email protected]>"

    );

    // main has two heads: a merge of both, whose tree is the union.

    let main = git(&a, &["rev-parse", "main"]);

    let mut parents: Vec<String> = git(&a, &["rev-list", "--parents", "-1", "main"])

        .split(' ')

        .skip(1)

        .map(String::from)

        .collect();

    parents.sort();

    let mut want = vec![c2.clone(), c3.clone()];

    want.sort();

    assert_eq!(parents, want, "the merge's parents are the heads");

    assert_eq!(

        git(&a, &["ls-tree", "--name-only", "main"]),

        "README.md\nother.txt\nsrc"

    );

    assert!(git(&a, &["log", "-1", "--format=%B", "main"]).contains("Merge of 2 heads"));

    assert_eq!(

        git(&a, &["rev-parse", "v1^{commit}"]),

        c2,

        "the tag is its head's commit"

    );

    assert_eq!(git(&a, &["symbolic-ref", "HEAD"]), "refs/heads/main");

    // Again: nothing new. A bookmark deleted takes its branch with it.

    repo.bookmark_delete("gone").unwrap();

    let rep = repo.git_export_graph(&a).unwrap();

    assert_eq!(rep.commits, 0, "{rep:?}");

    assert!(

        git(&a, &["for-each-ref", "--format=%(refname)", "refs/heads"])

            .lines()

            .all(|r| r != "refs/heads/gone")

    );

    assert_eq!(

        git(&a, &["rev-parse", "main"]),

        main,

        "the merge is made once"

    );

    // The same changes elsewhere give the same commits.

    let other = Repo::clone(r.to_str().unwrap(), &root.join("clone"))

        .unwrap()

        .with_home(root.join("home"));

    let b = root.join("b.git");

    other.git_export_graph(&b).unwrap();

    assert_eq!(

        git(&b, &["rev-parse", "main"]),

        main,

        "deterministic across repositories"

    );

    assert_eq!(git(&b, &["rev-parse", "v1^{commit}"]), c2);

}

- **Export by change graph.** For a server serving Git clients (a hub's Git view), `git_export_graph` exports every bookmark and tag from the changes alone, so the same changes give the same commits wherever it runs: each change is a commit whose tree is the state of the change and its dependency closure and whose parents are its dependencies' commits (a change that depends on nothing is a root), with the change's author, time, message and `Change-Id:`/`Oxy-Hash:` trailers; a bookmark with one head is a branch at its commit, with several a merge of their commits (the bookmark's state, at the newest head's time, `Oxy-Heads:`); tags likewise. Marks make it incremental; branches of deleted bookmarks are removed.