MidxPackList: Add a builder to edit the pack list In the compactor we have the existing list of packs, plus the new packs to add/remove. We need to combine all three to preview the new pack list and calculate what to put in the midx. Create a builder to add/remove packs. It takes care to take away from the list invalid midxs, to keep the updated list valid. Change-Id: Ied89ecceca4b2921d4bef39516af0e7d6a6a6964
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/MidxPackListTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/MidxPackListTest.java index 217f587..beaef58 100644 --- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/MidxPackListTest.java +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/MidxPackListTest.java
@@ -311,6 +311,168 @@ public void getPlainPacksNotCoveredBy_midxChain() { assertEquals(List.of(), packList.getPlainPacksNotCoveredBy(midxTip)); } + @Test + public void builder_delete_onlyPlain() { + DfsPackFile a = packPool.pack("a"); + DfsPackFile b = packPool.pack("b"); + DfsPackFile c = packPool.pack("c"); + + MidxPackList packList = MidxPackList.create(a, b, c).edit().delete(b) + .build(); + assertEquals(List.of(a, c), packList.getAllPlainPacks()); + } + + @Test + public void builder_delete_oneMidxCovering() { + DfsPackFile a = packPool.pack("a"); + DfsPackFile b = packPool.pack("b"); + DfsPackFile c = packPool.pack("c"); + DfsPackFileMidx midx = packPool.midx("midx", null, "a", "b", "c"); + + MidxPackList packList = MidxPackList.create(midx).edit().delete(b) + .build(); + assertEquals(List.of(c, a), packList.getAllPlainPacks()); + assertEquals(0, packList.getAllMidxPacks().size()); + } + + @Test + public void builder_delete_singlePackMidx() { + DfsPackFile a = packPool.pack("a"); + DfsPackFileMidx midx = packPool.midx("midx", null, "a"); + + MidxPackList packList = MidxPackList.create(midx).edit().delete(a) + .build(); + assertEquals(List.of(), packList.getAllPlainPacks()); + assertEquals(0, packList.getAllMidxPacks().size()); + } + + @Test + public void builder_delete_midxPlusOne_deleteUncovered() { + DfsPackFile a = packPool.pack("a"); + DfsPackFile b = packPool.pack("b"); + DfsPackFile c = packPool.pack("c"); + DfsPackFileMidx midx = packPool.midx("midx", null, "a", "b", "c"); + DfsPackFile d = packPool.pack("d"); + + MidxPackList deleteD = MidxPackList.create(d, midx).edit().delete(d) + .build(); + assertEquals(List.of(c, b, a), deleteD.getAllPlainPacks()); + assertEquals(midx, deleteD.getTopMidxPack()); + } + + @Test + public void builder_delete_midxPlusOne_deleteCovered() { + DfsPackFile a = packPool.pack("a"); + DfsPackFile b = packPool.pack("b"); + DfsPackFile c = packPool.pack("c"); + DfsPackFileMidx midx = packPool.midx("midx", null, "a", "b", "c"); + DfsPackFile d = packPool.pack("d"); + + MidxPackList deleteB = MidxPackList.create(d, midx).edit().delete(b) + .build(); + assertEquals(List.of(d, c, a), deleteB.getAllPlainPacks()); + assertEquals(0, deleteB.getAllMidxPacks().size()); + } + + @Test + public void builder_delete_nestedMidx() { + DfsPackFile a = packPool.pack("a"); + DfsPackFile b = packPool.pack("b"); + DfsPackFileMidx midxBase = packPool.midx("midxBase", null, "a", "b"); + DfsPackFile c = packPool.pack("c"); + DfsPackFile d = packPool.pack("d"); + DfsPackFileMidx midxMiddle = packPool.midx("midxMiddle", midxBase, "c", + "d"); + DfsPackFile e = packPool.pack("e"); + DfsPackFile f = packPool.pack("f"); + DfsPackFileMidx midxTip = packPool.midx("midxTip", midxMiddle, "e", + "f"); + + MidxPackList withoutF = MidxPackList.create(midxTip).edit().delete(f) + .build(); + assertEquals(List.of(e, d, c, b, a), withoutF.getAllPlainPacks()); + assertEquals(List.of(midxMiddle, midxBase), withoutF.getAllMidxPacks()); + assertEquals(midxMiddle, withoutF.getTopMidxPack()); + + MidxPackList withoutE = MidxPackList.create(midxTip).edit().delete(e) + .build(); + assertEquals(List.of(f, d, c, b, a), withoutE.getAllPlainPacks()); + assertEquals(List.of(midxMiddle, midxBase), withoutE.getAllMidxPacks()); + assertEquals(midxMiddle, withoutE.getTopMidxPack()); + assertEquals(Set.of(), withoutE.findAllCoveringMidxs(f)); + assertEquals(Set.of(midxMiddle, midxBase), + withoutE.findAllCoveringMidxs(a)); + + MidxPackList withoutD = MidxPackList.create(midxTip).edit().delete(d) + .build(); + assertEquals(List.of(f, e, c, b, a), withoutD.getAllPlainPacks()); + assertEquals(List.of(midxBase), withoutD.getAllMidxPacks()); + assertEquals(midxBase, withoutD.getTopMidxPack()); + + MidxPackList withoutC = MidxPackList.create(midxTip).edit().delete(c) + .build(); + assertEquals(List.of(f, e, d, b, a), withoutC.getAllPlainPacks()); + assertEquals(List.of(midxBase), withoutC.getAllMidxPacks()); + assertEquals(midxBase, withoutC.getTopMidxPack()); + assertEquals(Set.of(), withoutC.findAllCoveringMidxs(f, e, d, c)); + assertEquals(Set.of(midxBase), withoutC.findAllCoveringMidxs(a)); + + MidxPackList withoutB = MidxPackList.create(midxTip).edit().delete(b) + .build(); + assertEquals(List.of(f, e, d, c, a), withoutB.getAllPlainPacks()); + assertEquals(List.of(), withoutB.getAllMidxPacks()); + assertEquals(null, withoutB.getTopMidxPack()); + + MidxPackList withoutA = MidxPackList.create(midxTip).edit().delete(a) + .build(); + assertEquals(List.of(f, e, d, c, b), withoutA.getAllPlainPacks()); + assertEquals(List.of(), withoutA.getAllMidxPacks()); + assertEquals(null, withoutA.getTopMidxPack()); + assertEquals(Set.of(), withoutA.findAllCoveringMidxs(f, e, d, c, b)); + } + + @Test + public void builder_delete_nestedMidx_multipleDeletes() throws Exception { + DfsPackFile a = packPool.pack("a"); + DfsPackFile b = packPool.pack("b"); + DfsPackFileMidx midxBase = packPool.midx("midxBase", null, "a", "b"); + DfsPackFile c = packPool.pack("c"); + DfsPackFile d = packPool.pack("d"); + DfsPackFileMidx midxMiddle = packPool.midx("midxMiddle", midxBase, "c", + "d"); + DfsPackFile e = packPool.pack("e"); + DfsPackFile f = packPool.pack("f"); + DfsPackFileMidx midxTip = packPool.midx("midxTip", midxMiddle, "e", + "f"); + + { + MidxPackList deleteFromTopAndMiddle = MidxPackList.create(midxTip) + .edit().delete(e).delete(d).build(); + assertEquals(List.of(f, c, b, a), + deleteFromTopAndMiddle.getAllPlainPacks()); + assertEquals(List.of(midxBase), + deleteFromTopAndMiddle.getAllMidxPacks()); + assertEquals(midxBase, deleteFromTopAndMiddle.getTopMidxPack()); + } + { + MidxPackList deleteFromMiddleAndTop = MidxPackList.create(midxTip) + .edit().delete(d).delete(e).build(); + assertEquals(List.of(f, c, b, a), + deleteFromMiddleAndTop.getAllPlainPacks()); + assertEquals(List.of(midxBase), + deleteFromMiddleAndTop.getAllMidxPacks()); + assertEquals(midxBase, deleteFromMiddleAndTop.getTopMidxPack()); + } + { + MidxPackList deleteAllFromMidx = MidxPackList.create(midxTip).edit() + .delete(d).delete(c).build(); + assertEquals(List.of(f, e, b, a), + deleteAllFromMidx.getAllPlainPacks()); + assertEquals(List.of(midxBase), + deleteAllFromMidx.getAllMidxPacks()); + assertEquals(midxBase, deleteAllFromMidx.getTopMidxPack()); + } + } private static final class PackPool { private static final DfsRepositoryDescription repoDesc = new DfsRepositoryDescription(
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/MidxPackList.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/MidxPackList.java index 70c9b85..d60ca1e 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/MidxPackList.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/MidxPackList.java
@@ -21,6 +21,7 @@ import java.util.Queue; import java.util.Set; import java.util.TreeSet; +import java.util.stream.Collectors; import org.eclipse.jgit.annotations.Nullable; @@ -209,6 +210,151 @@ public List<DfsPackFile> getPlainPacksNotCoveredBy( .toList(); } + /** + * Get a builder to add/remove packs from the list + * + * @return the builder + */ + public Builder edit() { + return new Builder(packs); + } + + /** + * Builder to mutate the list of packs. + * + * It removes midxs from the list as packs are removed, to maintain a valid + * view of the packlist + */ + public final static class Builder { + + private final List<DfsPackFile> packList; + + private Builder(List<DfsPackFile> packs) { + this.packList = new ArrayList<>(packs); + } + + /** + * Add pack to the packlist + * + * @param toAdd + * pack to add + * @return this builder + */ + public Builder add(DfsPackFile toAdd) { + packList.add(toAdd); + return this; + } + + /** + * Delete the pack from the pack list + * + * Including any midx covering it directly or indirectly + * + * @param toDelete + * a pack to remove from the list + * @return this builder + */ + public Builder delete(DfsPackFile toDelete) { + // Check first top-level packs. In compact these are the most + // common packages being replaced. + DfsPackDescription toDeleteDesc = toDelete.getPackDescription(); + for (int i = 0; i < packList.size(); i++) { + if (packList.get(i).getPackDescription().equals(toDeleteDesc)) { + packList.remove(i); + return this; + } + } + + // If the pack is not "top-level", it may be covered by midx. + // We need to remove the pack, its covering midxs, but keep the + // other covered packs in their place. + // e.g. in the chain midx3(E, F) -> midx2 (C, D), -> midx(A, B), + // deleting C from midx3 produces: [F, E, D, midx(A, B)] + for (int i = packList.size() - 1; i >= 0; i--) { + if (!packList.get(i).getPackDescription() + .hasFileExt(MULTI_PACK_INDEX)) { + continue; + } + + DfsPackFileMidx midx = (DfsPackFileMidx) packList.get(i); + if (!containsAny(midx.getAllCoveredPacks(), + List.of(toDelete))) { + continue; + } + + List<DfsPackFile> replacement = getPacksToReplaceMidx(midx, + toDelete); + if (replacement != null) { + packList.remove(i); + if (!replacement.isEmpty()) { + packList.addAll(i, replacement); + } + } + } + + return this; + } + + /** + * Return the list of packs that replace a midx if we remove a pack + * + * When the pack is removed, any midx covering it (and above in the + * chain) is invalid. Each invalid midx is replaced with its covered + * packs (excluding the deleted pack) + * + * @param midx + * the midx + * @param toDelete + * the pack to remove + * @return the resulting list of packs after removing the pack. It can + * be null (nothing to change), empty (replace with nothing, + * i.e. delete the midx) or a list of packs + */ + @Nullable + private List<DfsPackFile> getPacksToReplaceMidx(DfsPackFileMidx midx, + DfsPackFile toDelete) { + List<DfsPackFile> result = new ArrayList<>(); + DfsPackFileMidx current = midx; + while (current != null) { + if (containsAny(current.getCoveredPacks(), List.of(toDelete))) { + List<DfsPackFile> otherCovered = current.getCoveredPacks() + .stream() + .filter(coveredPack -> !coveredPack + .getPackDescription() + .equals(toDelete.getPackDescription())) + .collect(Collectors.toCollection(ArrayList::new)); + Collections.reverse(otherCovered); + result.addAll(otherCovered); + if (current.getMultipackIndexBase() != null) { + result.add(current.getMultipackIndexBase()); + } + return result; + } + + // The deleted pack must be in the base of this midx, and it + // wil invalidate this one. Add all its covered packs to the + // result. + List<DfsPackFile> tmp = new ArrayList<>( + current.getCoveredPacks()); + Collections.reverse(tmp); + result.addAll(tmp); + current = current.getMultipackIndexBase(); + } + + // We didn't find the pack to delete in this midx chain + return null; + } + + /** + * Create a new pack list with the modifications + * + * @return a new packlist with the changes applied + */ + public MidxPackList build() { + return new MidxPackList(packList); + } + } + private static boolean containsAny(List<DfsPackFile> inMidx, List<DfsPackFile> queryPacks) { Set<DfsPackFile> inMidxSet = asSet(inMidx);