RefAdvancer: helper to find when a branch enters a pack For the bitmap calculation in midx, we need to follow a tip until it enters a pack. Add a helper to advance tips until they find their entry point into a pack. Change-Id: I54a7df7dd51be104a31008b3bf2949df6a6a6964
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/RefAdvancerWalkTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/RefAdvancerWalkTest.java new file mode 100644 index 0000000..321ea01 --- /dev/null +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/RefAdvancerWalkTest.java
@@ -0,0 +1,155 @@ +/* + * Copyright (C) 2026, Google LLC. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Distribution License v. 1.0 which is available at + * https://www.eclipse.org/org/documents/edl-v10.php. + * + * SPDX-License-Identifier: BSD-3-Clause + */ +package org.eclipse.jgit.internal.storage.dfs; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; + +import java.io.IOException; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Set; +import java.util.stream.Collectors; + +import org.eclipse.jgit.junit.TestRepository; +import org.eclipse.jgit.lib.ObjectId; +import org.eclipse.jgit.revwalk.RevCommit; +import org.junit.Before; +import org.junit.Test; + +public class RefAdvancerWalkTest { + private static final String MAIN = "refs/heads/main"; + + private InMemoryRepository db; + + private TestRepository<InMemoryRepository> git; + + private Set<RevCommit> commitsInMidx; + + private Map<String, RevCommit> commitByLetter; + + @Before + public void setUp() throws Exception { + db = new InMemoryRepository( + new DfsRepositoryDescription("ref advance")); + git = new TestRepository<>(db); + setupRepo(); + } + + /** + * <pre> + * tipMergeBeforeMidx -> H + * | + * | + * F G <- tipStraight + * |\ | + * | \| + * tipMergeMidxCommits -> D E + * |\ | + * +--------+ + * | B C <-- tipIn + * | | / | + * | |/ | + * | A | + * | midx| + * +--------+ + * </pre> + */ + private void setupRepo() throws Exception { + RevCommit a = commitToMain(); + RevCommit b = commitToMain(); + RevCommit c = commit(a); + RevCommit d = commitToMain(c); + RevCommit e = commit(c); + /* unused */ commitToMain(); + RevCommit g = commit(e); + RevCommit h = commitToMain(); + + commitsInMidx = new HashSet<>(); + commitsInMidx.add(a); + commitsInMidx.add(b); + commitsInMidx.add(c); + + commitByLetter = Map.of("a", a, "b", b, "c", c, "d", d, "e", e, "g", g, + "h", h); + + } + + @Test + public void singleWant_linearHistory() throws Exception { + runTest("g", Set.of("c")); + } + + @Test + public void singleWant_alreadyInMidx() throws Exception { + runTest("c", Set.of("c")); + } + + @Test + public void singleWant_mergeCommitsInMidx() throws Exception { + runTest("d", Set.of("b", "c")); + } + + @Test + public void singleWant_mergeBeforeMidx() throws Exception { + runTest("h", Set.of("b", "c")); + } + + @Test + public void manyWant_mergeBeforeMidx() throws Exception { + runTest(Set.of("h", "c", "d", "g"), Set.of("b", "c")); + } + + private void runTest(String want, Set<String> expectedTips) + throws IOException { + runTest(Set.of(want), expectedTips); + } + + private void runTest(Set<String> want, Set<String> expectedTips) + throws IOException { + RefAdvancerWalk advancer = new RefAdvancerWalk(db, + commitsInMidx::contains); + List<ObjectId> wants = want.stream().map(commitByLetter::get) + .collect(Collectors.toUnmodifiableList()); + Set<RevCommit> tipsInMidx = advancer.advance(wants); + + Set<RevCommit> expected = expectedTips.stream().map(commitByLetter::get) + .collect(Collectors.toUnmodifiableSet()); + assertEquals(expected.size(), tipsInMidx.size()); + assertTrue(tipsInMidx.containsAll(expected)); + } + + private static int commitCounter = 0; + + private RevCommit commitToMain() throws Exception { + int i = commitCounter++; + return git.branch(MAIN).commit() + .add("xx" + i, git.blob("content #" + i)).create(); + } + + private RevCommit commitToMain(RevCommit... extraParent) throws Exception { + int i = commitCounter++; + TestRepository<InMemoryRepository>.CommitBuilder commit = git + .branch(MAIN).commit(); + for (RevCommit p : extraParent) { + commit.parent(p); + } + + return commit.add("xx" + i, git.blob("content #" + i)).create(); + } + + private RevCommit commit(RevCommit parent) throws Exception { + int i = commitCounter++; + return git.commit().parent(parent) + .add("cc" + i, git.blob("out of main content #" + i)).create(); + } + +}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/RefAdvancerWalk.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/RefAdvancerWalk.java new file mode 100644 index 0000000..d0d8056 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/RefAdvancerWalk.java
@@ -0,0 +1,112 @@ +/* + * Copyright (C) 2026, Google LLC. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Distribution License v. 1.0 which is available at + * https://www.eclipse.org/org/documents/edl-v10.php. + * + * SPDX-License-Identifier: BSD-3-Clause + */ +package org.eclipse.jgit.internal.storage.dfs; + +import java.io.IOException; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +import org.eclipse.jgit.errors.StopWalkException; +import org.eclipse.jgit.lib.ObjectId; +import org.eclipse.jgit.revwalk.RevCommit; +import org.eclipse.jgit.revwalk.RevObject; +import org.eclipse.jgit.revwalk.RevSort; +import org.eclipse.jgit.revwalk.RevWalk; +import org.eclipse.jgit.revwalk.filter.RevFilter; + +/** + * Walk from some commits and find where to they enter a pack + */ +class RefAdvancerWalk { + + private final DfsRepository db; + + private final InPackPredicate includeP; + + /** + * True when the commit is in the pack + */ + @FunctionalInterface + interface InPackPredicate { + boolean test(RevCommit c) throws IOException; + } + + RefAdvancerWalk(DfsRepository db, InPackPredicate include) { + this.db = db; + this.includeP = include; + } + + private RevWalk createRevWalk() { + RevWalk rw = new RevWalk(db); + rw.sort(RevSort.COMMIT_TIME_DESC); + rw.setRevFilter(new FirstInPack(includeP)); + return rw; + } + + /** + * Advance the tips to their first commit inside the pack + * + * @param allTips + * tips of interesting refs + * @return first commit(s) where the tips enter the pack. A tips may + * translate into 0 commits (it doesn't enter the pack in its + * history), 1 commit (a linear history) or n commits (merges lead + * to multiple histories into the pack). A tip already inside the + * pack is returned as it is. + * @throws IOException + * error browsing history + */ + Set<RevCommit> advance(List<ObjectId> allTips) throws IOException { + Set<RevCommit> tipsInMidx = new HashSet<>(allTips.size()); + try (RevWalk rw = createRevWalk()) { + for (ObjectId tip : allTips) { + RevObject tipObject = rw.parseAny(tip); + if (!(tipObject instanceof RevCommit tipCommit)) { + continue; + } + + rw.markStart(tipCommit); + RevCommit inPack; + while ((inPack = rw.next()) != null) { + tipsInMidx.add(inPack); + } + } + } + return tipsInMidx; + } + + private static class FirstInPack extends RevFilter { + + private final InPackPredicate isInPack; + + FirstInPack(InPackPredicate isInPack) { + this.isInPack = isInPack; + } + + @Override + public boolean include(RevWalk walker, RevCommit cmit) + throws StopWalkException, IOException { + if (!isInPack.test(cmit)) { + return false; + } + + for (RevCommit p : cmit.getParents()) { + walker.markUninteresting(p); + } + return true; + } + + @Override + public RevFilter clone() { + return this; + } + } +}