Git import costs what each commit changes, not the whole tree 958fb27dda7c

        // 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).

        const MAX_KEPT: usize = 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();

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

        let mut last: Option<String> = None;

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

        let mut lap = |i: usize, clock: &mut std::time::Instant| {

            let now = std::time::Instant::now();

            spent[i] += now - *clock;

            *clock = now;

        };

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

                    };

                    match found {

                        Some((st, tree)) => (st, Some(tree)),

                        None => {

                            let mut st = State::new();

                            self.add_git_ancestors(&mut st, git_dir, &[p1.as_str()], &known)?;

                            (st, None)

                        }

                    }

                None => (State::new(), None),

            // Nodes the other parents' changes touch: the first parent's

            // tree cannot vouch for them.

            let mut touched: HashSet<NodeId> = HashSet::new();

                self.add_git_ancestors_touching(&mut base, git_dir, &refs, &known, &mut touched)?;

            lap(0, &mut clock);

            lap(1, &mut clock);

                        if e.kind == NodeKind::File && !e.mode.opaque && !touched.contains(&e.node)

                        {

            lap(2, &mut clock);

            lap(3, &mut clock);

            lap(4, &mut clock);

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

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

            lap(5, &mut clock);

        }

        for (name, d) in [

            "git import: bases",

            "git import: ls-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);

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

        touched: &mut HashSet<NodeId>,

        let mut add = |st: &mut State, h: &ChangeHash| -> Result<()> {

            if st.contains(h) {

                return Ok(());

            }

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

            Ok(())

        };

                add(st, h)?;

                    add(st, &h)?;

        // A directory stays while anything under it exists or is out of

        // scope: the directories above each such path, gathered once.

        let mut needed_dirs: HashSet<&str> = HashSet::new();

        fn parents_of<'a>(p: &'a str, set: &mut HashSet<&'a str>) {

            let mut end = p.len();

            while let Some(i) = p[..end].rfind('/') {

                if !set.insert(&p[..i]) {

                    break;

                }

                end = i;

            }

        }

        for p in fs_entries.keys() {

            parents_of(p, &mut needed_dirs);

        }

        for p in base_snapshot.files.keys() {

            if !self.in_scope(p) {

                parents_of(p, &mut needed_dirs);

            }

        }

            let still_needed =

                expected.kind == NodeKind::Dir && needed_dirs.contains(path.as_str());

    // A branch that edits run.sh, merged keeping main's tree (`-s ours`):

    // run.sh is the same as in the first parent's tree, but the merged

    // change touched it, so the importer must compare it, not skip it.

    git(&["checkout", "-q", "-b", "discarded"]);

    write(&g, "run.sh", b"#!/bin/sh\necho discarded\n");

    git(&["commit", "-q", "-am", "discarded edit"]);

    git(&["checkout", "-q", "main"]);

    git(&["merge", "-q", "-s", "ours", "-m", "merge discarded, keeping ours", "discarded"]);

    assert_eq!(rep.merges, 3);

    assert_eq!(fs::read(dest.join("run.sh")).unwrap(), b"#!/bin/sh\n", "the ours merge kept main's run.sh");

    let v = repo.verify_git_import(&g, "main").unwrap();

    assert_eq!(v.commits, expected_count, "every commit's tree reproduced");

    assert!(v.mismatches.is_empty(), "{:?}", v.mismatches);

## 2026-09-29: P5c, importing microsoft/vscode, first part

`oxy git import` on slices of microsoft/vscode's `main` (166 412 commits in

total), taken in the importer's own order (`git log --reverse

--topo-order`). The first 5 000 commits reach May 2016 with about 4 700

files.

The importer did work proportional to the whole tree for every commit:

- It cloned the previous state.

- It rebuilt a merge's first parent from history.

- It rendered, read and compared every file.

- It scanned every entry, with an allocation each, to decide whether each

  directory was still needed.

Now:

- Files with the same Git blob and mode as in the first parent's tree are

  marked unchanged and skipped, as a clean working copy's are. Paths that a

  merge's other parents touched are excluded.

- A commit's state is kept while first-parent children remain, up to 8,

  and the last child takes it without a clone.

- Needed directories come from one set of ancestors. That code is shared

  by snapshot and commit.

| Slice | Before | After |

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

| 300 commits (35 merges) | 65.1 s | 13.6 s |

| 1 000 commits (95 merges) | 271 s | 120 s, 3.3 GB |

| 5 000 commits (360 merges) | not finished after 80 min | 412 s, 6.3 GB, 17 MB store |

Where the 5 000-commit import spends its time (summed per phase): render

base 172 s, build change 99 s, bases 65 s, `git ls-tree` 56 s, read blobs

10 s, store 5 s.

Correctness: `oxy git verify` reproduces every commit of the 300 and

1 000-commit imports (1.9 million file comparisons for 1 000). A test

covers the case that must not be skipped: a `-s ours` merge whose other

side edited a file.

Next: rendering the base is still O(files) per commit, and memory grows

with the kept states. The full import follows.