diff options
Diffstat (limited to 'org.eclipse.jgit/src/org/eclipse/jgit')
68 files changed, 3991 insertions, 178 deletions
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/api/PullCommand.java b/org.eclipse.jgit/src/org/eclipse/jgit/api/PullCommand.java index 281ecfd011..83ae0fc9d4 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/api/PullCommand.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/api/PullCommand.java @@ -137,8 +137,8 @@ public class PullCommand extends TransportCommand<PullCommand, PullResult> { * <dt>BranchRebaseMode.REBASE</dt> * <dd>Equivalent to {@code --rebase} on the command line: use rebase * instead of merge after fetching.</dd> - * <dt>BranchRebaseMode.PRESERVE</dt> - * <dd>Equivalent to {@code --preserve-merges} on the command line: rebase + * <dt>BranchRebaseMode.MERGES</dt> + * <dd>Equivalent to {@code --rebase-merges} on the command line: rebase * preserving local merge commits.</dd> * <dt>BranchRebaseMode.INTERACTIVE</dt> * <dd>Equivalent to {@code --interactive} on the command line: use @@ -362,7 +362,7 @@ public class PullCommand extends TransportCommand<PullCommand, PullResult> { .setStrategy(strategy) .setContentMergeStrategy(contentStrategy) .setPreserveMerges( - pullRebaseMode == BranchRebaseMode.PRESERVE) + pullRebaseMode == BranchRebaseMode.MERGES) .call(); result = new PullResult(fetchRes, remote, rebaseRes); } else { diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/api/RebaseCommand.java b/org.eclipse.jgit/src/org/eclipse/jgit/api/RebaseCommand.java index 4e0d9d78c3..1e5523f275 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/api/RebaseCommand.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/api/RebaseCommand.java @@ -151,7 +151,7 @@ public class RebaseCommand extends GitCommand<RebaseResult> { /** * The folder containing the hashes of (potentially) rewritten commits when - * --preserve-merges is used. + * --rebase-merges is used. * <p> * Native git rebase --merge uses a <em>file</em> of that name to record * commits to copy notes at the end of the whole rebase. @@ -160,7 +160,7 @@ public class RebaseCommand extends GitCommand<RebaseResult> { private static final String REWRITTEN = "rewritten"; //$NON-NLS-1$ /** - * File containing the current commit(s) to cherry pick when --preserve-merges + * File containing the current commit(s) to cherry pick when --rebase-merges * is used. */ private static final String CURRENT_COMMIT = "current-commit"; //$NON-NLS-1$ diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java index 7fc48d45fa..39cc749cc4 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java @@ -139,6 +139,7 @@ public class JGitText extends TranslationBundle { /***/ public String cannotRead; /***/ public String cannotReadBackDelta; /***/ public String cannotReadBlob; + /***/ public String cannotReadByte; /***/ public String cannotReadCommit; /***/ public String cannotReadFile; /***/ public String cannotReadHEAD; @@ -172,11 +173,17 @@ public class JGitText extends TranslationBundle { /***/ public String commandClosedStderrButDidntExit; /***/ public String commandRejectedByHook; /***/ public String commandWasCalledInTheWrongState; + /***/ public String commitGraphChunkNeeded; + /***/ public String commitGraphChunkRepeated; + /***/ public String commitGraphChunkUnknown; + /***/ public String commitGraphFileIsTooLargeForJgit; + /***/ public String commitGraphWritingCancelled; /***/ public String commitMessageNotSpecified; /***/ public String commitOnRepoWithoutHEADCurrentlyNotSupported; /***/ public String commitAmendOnInitialNotPossible; /***/ public String commitsHaveAlreadyBeenMarkedAsStart; /***/ public String compressingObjects; + /***/ public String computingCommitGeneration; /***/ public String configSubsectionContainsNewline; /***/ public String configSubsectionContainsNullByte; /***/ public String configValueContainsNullByte; @@ -187,6 +194,7 @@ public class JGitText extends TranslationBundle { /***/ public String contextMustBeNonNegative; /***/ public String cookieFilePathRelative; /***/ public String copyFileFailedNullFiles; + /***/ public String corruptCommitGraph; /***/ public String corruptionDetectedReReadingAt; /***/ public String corruptObjectBadDate; /***/ public String corruptObjectBadEmail; @@ -329,6 +337,7 @@ public class JGitText extends TranslationBundle { /***/ public String exceptionOccurredDuringAddingOfOptionToALogCommand; /***/ public String exceptionOccurredDuringReadingOfGIT_DIR; /***/ public String exceptionWhileFindingUserHome; + /***/ public String exceptionWhileLoadingCommitGraph; /***/ public String exceptionWhileReadingPack; /***/ public String expectedACKNAKFoundEOF; /***/ public String expectedACKNAKGot; @@ -358,6 +367,7 @@ public class JGitText extends TranslationBundle { /***/ public String filterExecutionFailed; /***/ public String filterExecutionFailedRc; /***/ public String filterRequiresCapability; + /***/ public String findingCommitsForCommitGraph; /***/ public String findingGarbage; /***/ public String flagIsDisposed; /***/ public String flagNotFromThis; @@ -382,6 +392,8 @@ public class JGitText extends TranslationBundle { /***/ public String illegalCombinationOfArguments; /***/ public String illegalHookName; /***/ public String illegalPackingPhase; + /***/ public String illegalTernarySearchTreeKey; + /***/ public String illegalTernarySearchTreeValue; /***/ public String incorrectHashFor; /***/ public String incorrectOBJECT_ID_LENGTH; /***/ public String indexFileCorruptedNegativeBucketCount; @@ -413,6 +425,7 @@ public class JGitText extends TranslationBundle { /***/ public String invalidEncoding; /***/ public String invalidEncryption; /***/ public String invalidExpandWildcard; + /***/ public String invalidExtraEdgeListPosition; /***/ public String invalidFilter; /***/ public String invalidGitdirRef; /***/ public String invalidGitModules; @@ -543,6 +556,7 @@ public class JGitText extends TranslationBundle { /***/ public String noSuchSubmodule; /***/ public String notABoolean; /***/ public String notABundle; + /***/ public String notACommitGraph; /***/ public String notADIRCFile; /***/ public String notAGitDirectory; /***/ public String notAPACKFile; @@ -556,6 +570,7 @@ public class JGitText extends TranslationBundle { /***/ public String notMergedExceptionMessage; /***/ public String notShallowedUnshallow; /***/ public String noXMLParserAvailable; + /***/ public String numberDoesntFit; /***/ public String objectAtHasBadZlibStream; /***/ public String objectIsCorrupt; /***/ public String objectIsCorrupt3; @@ -792,6 +807,7 @@ public class JGitText extends TranslationBundle { /***/ public String tSizeMustBeGreaterOrEqual1; /***/ public String unableToCheckConnectivity; /***/ public String unableToCreateNewObject; + /***/ public String unableToReadFullInt; /***/ public String unableToReadPackfile; /***/ public String unableToRemovePath; /***/ public String unableToWrite; @@ -817,6 +833,7 @@ public class JGitText extends TranslationBundle { /***/ public String unknownObjectInIndex; /***/ public String unknownObjectType; /***/ public String unknownObjectType2; + /***/ public String unknownPositionEncoding; /***/ public String unknownRefStorageFormat; /***/ public String unknownRepositoryFormat; /***/ public String unknownRepositoryFormat2; @@ -826,6 +843,7 @@ public class JGitText extends TranslationBundle { /***/ public String unmergedPath; /***/ public String unmergedPaths; /***/ public String unpackException; + /***/ public String unreadableCommitGraph; /***/ public String unreadablePackIndex; /***/ public String unrecognizedPackExtension; /***/ public String unrecognizedRef; @@ -833,6 +851,7 @@ public class JGitText extends TranslationBundle { /***/ public String unsupportedAlternates; /***/ public String unsupportedArchiveFormat; /***/ public String unsupportedCommand0; + /***/ public String unsupportedCommitGraphVersion; /***/ public String unsupportedEncryptionAlgorithm; /***/ public String unsupportedEncryptionVersion; /***/ public String unsupportedGC; @@ -842,6 +861,7 @@ public class JGitText extends TranslationBundle { /***/ public String unsupportedPackVersion; /***/ public String unsupportedReftableVersion; /***/ public String unsupportedRepositoryDescription; + /***/ public String unsupportedSizesObjSizeIndex; /***/ public String updateRequiresOldIdAndNewId; /***/ public String updatingHeadFailed; /***/ public String updatingReferences; @@ -871,6 +891,7 @@ public class JGitText extends TranslationBundle { /***/ public String writeTimedOut; /***/ public String writingNotPermitted; /***/ public String writingNotSupported; + /***/ public String writingOutCommitGraph; /***/ public String writingObjects; /***/ public String wrongDecompressedLength; /***/ public String wrongRepositoryState; diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraph.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraph.java new file mode 100644 index 0000000000..0796293f52 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraph.java @@ -0,0 +1,145 @@ +/* + * Copyright (C) 2022, Tencent. + * + * 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.commitgraph; + +import org.eclipse.jgit.lib.AnyObjectId; +import org.eclipse.jgit.lib.ObjectId; + +/** + * The CommitGraph is a supplemental data structure that accelerates commit + * graph walks. + * <p> + * If a user downgrades or disables the <code>core.commitGraph</code> config + * setting, then the existing object database is sufficient. + * </p> + * <p> + * It stores the commit graph structure along with some extra metadata to speed + * up graph walks. By listing commit OIDs in lexicographic order, we can + * identify an integer position for each commit and refer to the parents of a + * commit using those integer positions. We use binary search to find initial + * commits and then use the integer positions for fast lookups during the walk. + * </p> + */ +public interface CommitGraph { + + /** Empty {@link CommitGraph} with no results. */ + CommitGraph EMPTY = new CommitGraph() { + /** {@inheritDoc} */ + @Override + public int findGraphPosition(AnyObjectId commit) { + return -1; + } + + /** {@inheritDoc} */ + @Override + public CommitData getCommitData(int graphPos) { + return null; + } + + /** {@inheritDoc} */ + @Override + public ObjectId getObjectId(int graphPos) { + return null; + } + + /** {@inheritDoc} */ + @Override + public long getCommitCnt() { + return 0; + } + }; + + /** + * Find the position in the commit-graph of the commit. + * <p> + * The position can only be used within the CommitGraph Instance you got it + * from. That's because the graph position of the same commit may be + * different in CommitGraph obtained at different times (eg., regenerated + * new commit-graph). + * + * @param commit + * the commit for which the commit-graph position will be found. + * @return the commit-graph position or -1 if the object was not found. + */ + int findGraphPosition(AnyObjectId commit); + + /** + * Get the metadata of a commit。 + * <p> + * This function runs in time O(1). + * <p> + * In the process of commit history traversal, + * {@link CommitData#getParents()} makes us get the graphPos of the commit's + * parents in advance, so that we can avoid O(logN) lookup and use O(1) + * lookup instead. + * + * @param graphPos + * the position in the commit-graph of the object. + * @return the metadata of a commit or null if it's not found. + */ + CommitData getCommitData(int graphPos); + + /** + * Get the object at the commit-graph position. + * + * @param graphPos + * the position in the commit-graph of the object. + * @return the ObjectId or null if it's not found. + */ + ObjectId getObjectId(int graphPos); + + /** + * Obtain the total number of commits described by this commit-graph. + * + * @return number of commits in this commit-graph. + */ + long getCommitCnt(); + + /** + * Metadata of a commit in commit data chunk. + */ + interface CommitData { + + /** + * Get a reference to this commit's tree. + * + * @return tree of this commit. + */ + ObjectId getTree(); + + /** + * Obtain an array of all parents. + * <p> + * The method only provides the graph positions of parents in + * commit-graph, call {@link CommitGraph#getObjectId(int)} to get the + * real objectId. + * + * @return the array of parents. + */ + int[] getParents(); + + /** + * Time from the "committer" line. + * + * @return the commit time in seconds since EPOCH. + */ + long getCommitTime(); + + /** + * Get the generation number (the distance from the root) of the commit. + * + * @return the generation number or + * {@link org.eclipse.jgit.lib.Constants#COMMIT_GENERATION_NOT_COMPUTED} + * if the writer didn't calculate it. + */ + int getGeneration(); + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphBuilder.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphBuilder.java new file mode 100644 index 0000000000..a6af3bc592 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphBuilder.java @@ -0,0 +1,104 @@ +/* + * Copyright (C) 2022, Tencent. + * + * 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.commitgraph; + +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_ID_COMMIT_DATA; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_ID_EXTRA_EDGE_LIST; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_ID_OID_FANOUT; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_ID_OID_LOOKUP; +import static org.eclipse.jgit.lib.Constants.OBJECT_ID_LENGTH; + +import java.text.MessageFormat; + +import org.eclipse.jgit.internal.JGitText; + +/** + * Builder for {@link CommitGraph}. + */ +class CommitGraphBuilder { + + private final int hashLength; + + private byte[] oidFanout; + + private byte[] oidLookup; + + private byte[] commitData; + + private byte[] extraList; + + /** @return A builder of {@link CommitGraph}. */ + static CommitGraphBuilder builder() { + return new CommitGraphBuilder(OBJECT_ID_LENGTH); + } + + private CommitGraphBuilder(int hashLength) { + this.hashLength = hashLength; + } + + CommitGraphBuilder addOidFanout(byte[] buffer) + throws CommitGraphFormatException { + assertChunkNotSeenYet(oidFanout, CHUNK_ID_OID_FANOUT); + oidFanout = buffer; + return this; + } + + CommitGraphBuilder addOidLookUp(byte[] buffer) + throws CommitGraphFormatException { + assertChunkNotSeenYet(oidLookup, CHUNK_ID_OID_LOOKUP); + oidLookup = buffer; + return this; + } + + CommitGraphBuilder addCommitData(byte[] buffer) + throws CommitGraphFormatException { + assertChunkNotSeenYet(commitData, CHUNK_ID_COMMIT_DATA); + commitData = buffer; + return this; + } + + CommitGraphBuilder addExtraList(byte[] buffer) + throws CommitGraphFormatException { + assertChunkNotSeenYet(extraList, CHUNK_ID_EXTRA_EDGE_LIST); + extraList = buffer; + return this; + } + + CommitGraph build() throws CommitGraphFormatException { + assertChunkNotNull(oidFanout, CHUNK_ID_OID_FANOUT); + assertChunkNotNull(oidLookup, CHUNK_ID_OID_LOOKUP); + assertChunkNotNull(commitData, CHUNK_ID_COMMIT_DATA); + + GraphObjectIndex index = new GraphObjectIndex(hashLength, oidFanout, + oidLookup); + GraphCommitData commitDataChunk = new GraphCommitData(hashLength, + commitData, extraList); + return new CommitGraphV1(index, commitDataChunk); + } + + private void assertChunkNotNull(Object object, int chunkId) + throws CommitGraphFormatException { + if (object == null) { + throw new CommitGraphFormatException( + MessageFormat.format(JGitText.get().commitGraphChunkNeeded, + Integer.toHexString(chunkId))); + } + } + + private void assertChunkNotSeenYet(Object object, int chunkId) + throws CommitGraphFormatException { + if (object != null) { + throw new CommitGraphFormatException(MessageFormat.format( + JGitText.get().commitGraphChunkRepeated, + Integer.toHexString(chunkId))); + } + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphConstants.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphConstants.java new file mode 100644 index 0000000000..a074833fa5 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphConstants.java @@ -0,0 +1,55 @@ +/* + * Copyright (C) 2021, Tencent. + * + * 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.commitgraph; + +/** + * Constants relating to commit-graph. + */ +class CommitGraphConstants { + + static final int COMMIT_GRAPH_MAGIC = 0x43475048; /* "CGPH" */ + + static final int CHUNK_ID_OID_FANOUT = 0x4f494446; /* "OIDF" */ + + static final int CHUNK_ID_OID_LOOKUP = 0x4f49444c; /* "OIDL" */ + + static final int CHUNK_ID_COMMIT_DATA = 0x43444154; /* "CDAT" */ + + static final int CHUNK_ID_EXTRA_EDGE_LIST = 0x45444745; /* "EDGE" */ + + /** + * First 4 bytes describe the chunk id. Value 0 is a terminating label. + * Other 8 bytes provide the byte-offset in current file for chunk to start. + */ + static final int CHUNK_LOOKUP_WIDTH = 12; + + /** + * First 8 bytes are for the positions of the first two parents of the ith + * commit. The next 8 bytes store the generation number of the commit and + * the commit time in seconds since EPOCH. + */ + static final int COMMIT_DATA_WIDTH = 16; + + /** Mask to make the last edgeValue into position */ + static final int GRAPH_EDGE_LAST_MASK = 0x7fffffff; + + /** EdgeValue & GRAPH_LAST_EDGE != 0 means it is the last edgeValue */ + static final int GRAPH_LAST_EDGE = 0x80000000; + + /** EdgeValue == GRAPH_NO_PARENT means it has no parents */ + static final int GRAPH_NO_PARENT = 0x70000000; + + /** + * EdgeValue & GRAPH_EXTRA_EDGES_NEEDED != 0 means its other parents are in + * Chunk Extra Edge List + */ + static final int GRAPH_EXTRA_EDGES_NEEDED = 0x80000000; +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphFormatException.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphFormatException.java new file mode 100644 index 0000000000..352bf4b9ef --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphFormatException.java @@ -0,0 +1,31 @@ +/* + * Copyright (C) 2022, Tencent. + * + * 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.commitgraph; + +import java.io.IOException; + +/** + * Thrown when a commit-graph file's format is different from we expected + */ +public class CommitGraphFormatException extends IOException { + + private static final long serialVersionUID = 1L; + + /** + * Construct an exception. + * + * @param why + * description of the type of error. + */ + CommitGraphFormatException(String why) { + super(why); + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphLoader.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphLoader.java new file mode 100644 index 0000000000..571f5f4ebe --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphLoader.java @@ -0,0 +1,186 @@ +/* + * Copyright (C) 2022, Tencent. + * + * 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.commitgraph; + +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_ID_COMMIT_DATA; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_ID_EXTRA_EDGE_LIST; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_ID_OID_FANOUT; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_ID_OID_LOOKUP; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_LOOKUP_WIDTH; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.COMMIT_GRAPH_MAGIC; + +import java.io.File; +import java.io.FileNotFoundException; +import java.io.IOException; +import java.io.InputStream; +import java.text.MessageFormat; +import java.util.ArrayList; +import java.util.List; + +import org.eclipse.jgit.internal.JGitText; +import org.eclipse.jgit.util.IO; +import org.eclipse.jgit.util.NB; +import org.eclipse.jgit.util.io.SilentFileInputStream; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +/** + * The loader returns the representation of the commit-graph file content. + */ +public class CommitGraphLoader { + + private final static Logger LOG = LoggerFactory + .getLogger(CommitGraphLoader.class); + + /** + * Open an existing commit-graph file for reading. + * <p> + * The format of the file will be automatically detected and a proper access + * implementation for that format will be constructed and returned to the + * caller. The file may or may not be held open by the returned instance. + * + * @param graphFile + * existing commit-graph to read. + * @return a copy of the commit-graph file in memory + * @throws FileNotFoundException + * the file does not exist. + * @throws CommitGraphFormatException + * commit-graph file's format is different from we expected. + * @throws java.io.IOException + * the file exists but could not be read due to security errors + * or unexpected data corruption. + */ + public static CommitGraph open(File graphFile) throws FileNotFoundException, + CommitGraphFormatException, IOException { + try (SilentFileInputStream fd = new SilentFileInputStream(graphFile)) { + try { + return read(fd); + } catch (CommitGraphFormatException fe) { + throw fe; + } catch (IOException ioe) { + throw new IOException(MessageFormat.format( + JGitText.get().unreadableCommitGraph, + graphFile.getAbsolutePath()), ioe); + } + } + } + + /** + * Read an existing commit-graph file from a buffered stream. + * <p> + * The format of the file will be automatically detected and a proper access + * implementation for that format will be constructed and returned to the + * caller. The file may or may not be held open by the returned instance. + * + * @param fd + * stream to read the commit-graph file from. The stream must be + * buffered as some small IOs are performed against the stream. + * The caller is responsible for closing the stream. + * + * @return a copy of the commit-graph file in memory + * @throws CommitGraphFormatException + * the commit-graph file's format is different from we expected. + * @throws java.io.IOException + * the stream cannot be read. + */ + public static CommitGraph read(InputStream fd) + throws CommitGraphFormatException, IOException { + byte[] hdr = new byte[8]; + IO.readFully(fd, hdr, 0, hdr.length); + + int magic = NB.decodeInt32(hdr, 0); + if (magic != COMMIT_GRAPH_MAGIC) { + throw new CommitGraphFormatException( + JGitText.get().notACommitGraph); + } + + // Read the hash version (1 byte) + // 1 => SHA-1 + // 2 => SHA-256 nonsupport now + int hashVersion = hdr[5]; + if (hashVersion != 1) { + throw new CommitGraphFormatException( + JGitText.get().incorrectOBJECT_ID_LENGTH); + } + + // Check commit-graph version + int v = hdr[4]; + if (v != 1) { + throw new CommitGraphFormatException(MessageFormat.format( + JGitText.get().unsupportedCommitGraphVersion, + Integer.valueOf(v))); + } + + // Read the number of "chunkOffsets" (1 byte) + int numberOfChunks = hdr[6]; + + // hdr[7] is the number of base commit-graphs, which is not supported in + // current version + + byte[] lookupBuffer = new byte[CHUNK_LOOKUP_WIDTH + * (numberOfChunks + 1)]; + IO.readFully(fd, lookupBuffer, 0, lookupBuffer.length); + List<ChunkSegment> chunks = new ArrayList<>(numberOfChunks + 1); + for (int i = 0; i <= numberOfChunks; i++) { + // chunks[numberOfChunks] is just a marker, in order to record the + // length of the last chunk. + int id = NB.decodeInt32(lookupBuffer, i * 12); + long offset = NB.decodeInt64(lookupBuffer, i * 12 + 4); + chunks.add(new ChunkSegment(id, offset)); + } + + CommitGraphBuilder builder = CommitGraphBuilder.builder(); + for (int i = 0; i < numberOfChunks; i++) { + long chunkOffset = chunks.get(i).offset; + int chunkId = chunks.get(i).id; + long len = chunks.get(i + 1).offset - chunkOffset; + + if (len > Integer.MAX_VALUE - 8) { // http://stackoverflow.com/a/8381338 + throw new CommitGraphFormatException( + JGitText.get().commitGraphFileIsTooLargeForJgit); + } + + byte buffer[] = new byte[(int) len]; + IO.readFully(fd, buffer, 0, buffer.length); + + switch (chunkId) { + case CHUNK_ID_OID_FANOUT: + builder.addOidFanout(buffer); + break; + case CHUNK_ID_OID_LOOKUP: + builder.addOidLookUp(buffer); + break; + case CHUNK_ID_COMMIT_DATA: + builder.addCommitData(buffer); + break; + case CHUNK_ID_EXTRA_EDGE_LIST: + builder.addExtraList(buffer); + break; + default: + LOG.warn(MessageFormat.format( + JGitText.get().commitGraphChunkUnknown, + Integer.toHexString(chunkId))); + } + } + return builder.build(); + } + + private static class ChunkSegment { + final int id; + + final long offset; + + private ChunkSegment(int id, long offset) { + this.id = id; + this.offset = offset; + } + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphV1.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphV1.java new file mode 100644 index 0000000000..da172192e4 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphV1.java @@ -0,0 +1,58 @@ +/* + * Copyright (C) 2022, Tencent. + * + * 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.commitgraph; + +import org.eclipse.jgit.lib.AnyObjectId; +import org.eclipse.jgit.lib.ObjectId; + +/** + * Support for the commit-graph v1 format. + * + * @see CommitGraph + */ +class CommitGraphV1 implements CommitGraph { + + private final GraphObjectIndex idx; + + private final GraphCommitData commitData; + + CommitGraphV1(GraphObjectIndex index, GraphCommitData commitData) { + this.idx = index; + this.commitData = commitData; + } + + /** {@inheritDoc} */ + @Override + public int findGraphPosition(AnyObjectId commit) { + return idx.findGraphPosition(commit); + } + + /** {@inheritDoc} */ + @Override + public CommitData getCommitData(int graphPos) { + if (graphPos < 0 || graphPos >= getCommitCnt()) { + return null; + } + return commitData.getCommitData(graphPos); + } + + /** {@inheritDoc} */ + @Override + public ObjectId getObjectId(int graphPos) { + return idx.getObjectId(graphPos); + } + + /** {@inheritDoc} */ + @Override + public long getCommitCnt() { + return idx.getCommitCnt(); + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphWriter.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphWriter.java new file mode 100644 index 0000000000..a58a9eb632 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphWriter.java @@ -0,0 +1,338 @@ +/* + * Copyright (C) 2021, Tencent. + * + * 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.commitgraph; + +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_ID_COMMIT_DATA; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_ID_EXTRA_EDGE_LIST; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_ID_OID_FANOUT; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_ID_OID_LOOKUP; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.CHUNK_LOOKUP_WIDTH; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.COMMIT_DATA_WIDTH; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.COMMIT_GRAPH_MAGIC; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.GRAPH_EXTRA_EDGES_NEEDED; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.GRAPH_LAST_EDGE; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.GRAPH_NO_PARENT; +import static org.eclipse.jgit.lib.Constants.COMMIT_GENERATION_NOT_COMPUTED; +import static org.eclipse.jgit.lib.Constants.COMMIT_GENERATION_UNKNOWN; +import static org.eclipse.jgit.lib.Constants.OBJECT_ID_LENGTH; + +import java.io.IOException; +import java.io.InterruptedIOException; +import java.io.OutputStream; +import java.text.MessageFormat; +import java.util.ArrayList; +import java.util.List; +import java.util.Stack; + +import org.eclipse.jgit.annotations.NonNull; +import org.eclipse.jgit.errors.MissingObjectException; +import org.eclipse.jgit.internal.JGitText; +import org.eclipse.jgit.internal.storage.io.CancellableDigestOutputStream; +import org.eclipse.jgit.lib.ObjectId; +import org.eclipse.jgit.lib.ProgressMonitor; +import org.eclipse.jgit.revwalk.RevCommit; +import org.eclipse.jgit.util.NB; + +/** + * Writes a commit-graph formatted file. + * + * @since 6.5 + */ +public class CommitGraphWriter { + + private static final int COMMIT_GRAPH_VERSION_GENERATED = 1; + + private static final int OID_HASH_VERSION = 1; + + private static final int GRAPH_FANOUT_SIZE = 4 * 256; + + private static final int GENERATION_NUMBER_MAX = 0x3FFFFFFF; + + private final int hashsz; + + private final GraphCommits graphCommits; + + /** + * Create commit-graph writer for these commits. + * + * @param graphCommits + * the commits which will be writen to the commit-graph. + */ + public CommitGraphWriter(@NonNull GraphCommits graphCommits) { + this.graphCommits = graphCommits; + this.hashsz = OBJECT_ID_LENGTH; + } + + /** + * Write commit-graph to the supplied stream. + * + * @param monitor + * progress monitor to report the number of items written. + * @param commitGraphStream + * output stream of commit-graph data. The stream should be + * buffered by the caller. The caller is responsible for closing + * the stream. + * @throws IOException + */ + public void write(@NonNull ProgressMonitor monitor, + @NonNull OutputStream commitGraphStream) throws IOException { + if (graphCommits.size() == 0) { + return; + } + + List<ChunkHeader> chunks = createChunks(); + long writeCount = 256 + 2 * graphCommits.size() + + graphCommits.getExtraEdgeCnt(); + monitor.beginTask( + MessageFormat.format(JGitText.get().writingOutCommitGraph, + Integer.valueOf(chunks.size())), + (int) writeCount); + + try (CancellableDigestOutputStream out = new CancellableDigestOutputStream( + monitor, commitGraphStream)) { + writeHeader(out, chunks.size()); + writeChunkLookup(out, chunks); + writeChunks(monitor, out, chunks); + writeCheckSum(out); + } catch (InterruptedIOException e) { + throw new IOException(JGitText.get().commitGraphWritingCancelled, + e); + } finally { + monitor.endTask(); + } + } + + private List<ChunkHeader> createChunks() { + List<ChunkHeader> chunks = new ArrayList<>(); + chunks.add(new ChunkHeader(CHUNK_ID_OID_FANOUT, GRAPH_FANOUT_SIZE)); + chunks.add(new ChunkHeader(CHUNK_ID_OID_LOOKUP, + hashsz * graphCommits.size())); + chunks.add(new ChunkHeader(CHUNK_ID_COMMIT_DATA, + (hashsz + 16) * graphCommits.size())); + if (graphCommits.getExtraEdgeCnt() > 0) { + chunks.add(new ChunkHeader(CHUNK_ID_EXTRA_EDGE_LIST, + graphCommits.getExtraEdgeCnt() * 4)); + } + return chunks; + } + + private void writeHeader(CancellableDigestOutputStream out, int numChunks) + throws IOException { + byte[] headerBuffer = new byte[8]; + NB.encodeInt32(headerBuffer, 0, COMMIT_GRAPH_MAGIC); + byte[] buff = { (byte) COMMIT_GRAPH_VERSION_GENERATED, + (byte) OID_HASH_VERSION, (byte) numChunks, (byte) 0 }; + System.arraycopy(buff, 0, headerBuffer, 4, 4); + out.write(headerBuffer, 0, 8); + out.flush(); + } + + private void writeChunkLookup(CancellableDigestOutputStream out, + List<ChunkHeader> chunks) throws IOException { + int numChunks = chunks.size(); + long chunkOffset = 8 + (numChunks + 1) * CHUNK_LOOKUP_WIDTH; + byte[] buffer = new byte[CHUNK_LOOKUP_WIDTH]; + for (ChunkHeader chunk : chunks) { + NB.encodeInt32(buffer, 0, chunk.id); + NB.encodeInt64(buffer, 4, chunkOffset); + out.write(buffer); + chunkOffset += chunk.size; + } + NB.encodeInt32(buffer, 0, 0); + NB.encodeInt64(buffer, 4, chunkOffset); + out.write(buffer); + } + + private void writeChunks(ProgressMonitor monitor, + CancellableDigestOutputStream out, List<ChunkHeader> chunks) + throws IOException { + for (ChunkHeader chunk : chunks) { + int chunkId = chunk.id; + + switch (chunkId) { + case CHUNK_ID_OID_FANOUT: + writeFanoutTable(out); + break; + case CHUNK_ID_OID_LOOKUP: + writeOidLookUp(out); + break; + case CHUNK_ID_COMMIT_DATA: + writeCommitData(monitor, out); + break; + case CHUNK_ID_EXTRA_EDGE_LIST: + writeExtraEdges(out); + break; + } + } + } + + private void writeCheckSum(CancellableDigestOutputStream out) + throws IOException { + out.write(out.getDigest()); + out.flush(); + } + + private void writeFanoutTable(CancellableDigestOutputStream out) + throws IOException { + byte[] tmp = new byte[4]; + int[] fanout = new int[256]; + for (RevCommit c : graphCommits) { + fanout[c.getFirstByte() & 0xff]++; + } + for (int i = 1; i < fanout.length; i++) { + fanout[i] += fanout[i - 1]; + } + for (int n : fanout) { + NB.encodeInt32(tmp, 0, n); + out.write(tmp, 0, 4); + out.getWriteMonitor().update(1); + } + } + + private void writeOidLookUp(CancellableDigestOutputStream out) + throws IOException { + byte[] tmp = new byte[4 + hashsz]; + + for (RevCommit c : graphCommits) { + c.copyRawTo(tmp, 0); + out.write(tmp, 0, hashsz); + out.getWriteMonitor().update(1); + } + } + + private void writeCommitData(ProgressMonitor monitor, + CancellableDigestOutputStream out) throws IOException { + int[] generations = computeGenerationNumbers(monitor); + int num = 0; + byte[] tmp = new byte[hashsz + COMMIT_DATA_WIDTH]; + int i = 0; + for (RevCommit commit : graphCommits) { + int edgeValue; + int[] packedDate = new int[2]; + + ObjectId treeId = commit.getTree(); + treeId.copyRawTo(tmp, 0); + + RevCommit[] parents = commit.getParents(); + if (parents.length == 0) { + edgeValue = GRAPH_NO_PARENT; + } else { + RevCommit parent = parents[0]; + edgeValue = graphCommits.getOidPosition(parent); + } + NB.encodeInt32(tmp, hashsz, edgeValue); + if (parents.length == 1) { + edgeValue = GRAPH_NO_PARENT; + } else if (parents.length == 2) { + RevCommit parent = parents[1]; + edgeValue = graphCommits.getOidPosition(parent); + } else if (parents.length > 2) { + edgeValue = GRAPH_EXTRA_EDGES_NEEDED | num; + num += parents.length - 1; + } + + NB.encodeInt32(tmp, hashsz + 4, edgeValue); + + packedDate[0] = 0; // commitTime is an int in JGit now + packedDate[0] |= generations[i] << 2; + packedDate[1] = commit.getCommitTime(); + NB.encodeInt32(tmp, hashsz + 8, packedDate[0]); + NB.encodeInt32(tmp, hashsz + 12, packedDate[1]); + + out.write(tmp); + out.getWriteMonitor().update(1); + i++; + } + } + + private int[] computeGenerationNumbers(ProgressMonitor monitor) + throws MissingObjectException { + int[] generations = new int[graphCommits.size()]; + monitor.beginTask(JGitText.get().computingCommitGeneration, + graphCommits.size()); + for (RevCommit cmit : graphCommits) { + monitor.update(1); + int generation = generations[graphCommits.getOidPosition(cmit)]; + if (generation != COMMIT_GENERATION_NOT_COMPUTED + && generation != COMMIT_GENERATION_UNKNOWN) { + continue; + } + + Stack<RevCommit> commitStack = new Stack<>(); + commitStack.push(cmit); + + while (!commitStack.empty()) { + int maxGeneration = 0; + boolean allParentComputed = true; + RevCommit current = commitStack.peek(); + RevCommit parent; + + for (int i = 0; i < current.getParentCount(); i++) { + parent = current.getParent(i); + generation = generations[graphCommits + .getOidPosition(parent)]; + if (generation == COMMIT_GENERATION_NOT_COMPUTED + || generation == COMMIT_GENERATION_UNKNOWN) { + allParentComputed = false; + commitStack.push(parent); + break; + } else if (generation > maxGeneration) { + maxGeneration = generation; + } + } + + if (allParentComputed) { + RevCommit commit = commitStack.pop(); + generation = maxGeneration + 1; + if (generation > GENERATION_NUMBER_MAX) { + generation = GENERATION_NUMBER_MAX; + } + generations[graphCommits + .getOidPosition(commit)] = generation; + } + } + } + monitor.endTask(); + return generations; + } + + private void writeExtraEdges(CancellableDigestOutputStream out) + throws IOException { + byte[] tmp = new byte[4]; + for (RevCommit commit : graphCommits) { + RevCommit[] parents = commit.getParents(); + if (parents.length > 2) { + int edgeValue; + for (int n = 1; n < parents.length; n++) { + RevCommit parent = parents[n]; + edgeValue = graphCommits.getOidPosition(parent); + if (n == parents.length - 1) { + edgeValue |= GRAPH_LAST_EDGE; + } + NB.encodeInt32(tmp, 0, edgeValue); + out.write(tmp); + out.getWriteMonitor().update(1); + } + } + } + } + + private static class ChunkHeader { + final int id; + + final long size; + + public ChunkHeader(int id, long size) { + this.id = id; + this.size = size; + } + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/GraphCommitData.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/GraphCommitData.java new file mode 100644 index 0000000000..6ae40ff552 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/GraphCommitData.java @@ -0,0 +1,172 @@ +/* + * Copyright (C) 2022, Tencent. + * + * 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.commitgraph; + +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.COMMIT_DATA_WIDTH; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.GRAPH_EDGE_LAST_MASK; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.GRAPH_EXTRA_EDGES_NEEDED; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.GRAPH_LAST_EDGE; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraphConstants.GRAPH_NO_PARENT; + +import java.text.MessageFormat; +import java.util.Arrays; + +import org.eclipse.jgit.annotations.NonNull; +import org.eclipse.jgit.internal.JGitText; +import org.eclipse.jgit.internal.storage.commitgraph.CommitGraph.CommitData; +import org.eclipse.jgit.lib.ObjectId; +import org.eclipse.jgit.util.NB; + +/** + * Represent the collection of {@link CommitData}. + */ +class GraphCommitData { + + private static final int[] NO_PARENTS = {}; + + private final byte[] data; + + private final byte[] extraList; + + private final int hashLength; + + private final int commitDataLength; + + /** + * Initialize the GraphCommitData. + * + * @param hashLength + * length of object hash. + * @param commitData + * content of CommitData Chunk. + * @param extraList + * content of Extra Edge List Chunk. + */ + GraphCommitData(int hashLength, @NonNull byte[] commitData, + byte[] extraList) { + this.data = commitData; + this.extraList = extraList; + this.hashLength = hashLength; + this.commitDataLength = hashLength + COMMIT_DATA_WIDTH; + } + + /** + * Get the metadata of a commit。 + * + * @param graphPos + * the position in the commit-graph of the object. + * @return the metadata of a commit or null if not found. + */ + CommitData getCommitData(int graphPos) { + int dataIdx = commitDataLength * graphPos; + + // parse tree + ObjectId tree = ObjectId.fromRaw(data, dataIdx); + + // parse date + long dateHigh = NB.decodeUInt32(data, dataIdx + hashLength + 8) & 0x3; + long dateLow = NB.decodeUInt32(data, dataIdx + hashLength + 12); + long commitTime = dateHigh << 32 | dateLow; + + // parse generation + int generation = NB.decodeInt32(data, dataIdx + hashLength + 8) >> 2; + + // parse first parent + int parent1 = NB.decodeInt32(data, dataIdx + hashLength); + if (parent1 == GRAPH_NO_PARENT) { + return new CommitDataImpl(tree, NO_PARENTS, commitTime, generation); + } + + // parse second parent + int parent2 = NB.decodeInt32(data, dataIdx + hashLength + 4); + if (parent2 == GRAPH_NO_PARENT) { + return new CommitDataImpl(tree, new int[] { parent1 }, commitTime, + generation); + } + + if ((parent2 & GRAPH_EXTRA_EDGES_NEEDED) == 0) { + return new CommitDataImpl(tree, new int[] { parent1, parent2 }, + commitTime, generation); + } + + // parse parents for octopus merge + return new CommitDataImpl(tree, + findParentsForOctopusMerge(parent1, + parent2 & GRAPH_EDGE_LAST_MASK), + commitTime, generation); + } + + private int[] findParentsForOctopusMerge(int parent1, int extraEdgePos) { + int maxOffset = extraList.length - 4; + int offset = extraEdgePos * 4; + if (offset < 0 || offset > maxOffset) { + throw new IllegalArgumentException(MessageFormat.format( + JGitText.get().invalidExtraEdgeListPosition, + Integer.valueOf(extraEdgePos))); + } + int[] pList = new int[32]; + pList[0] = parent1; + int count = 1; + int parentPosition; + for (; offset <= maxOffset; offset += 4) { + if (count >= pList.length) { + // expand the pList + pList = Arrays.copyOf(pList, pList.length + 32); + } + parentPosition = NB.decodeInt32(extraList, offset); + if ((parentPosition & GRAPH_LAST_EDGE) != 0) { + pList[count++] = parentPosition & GRAPH_EDGE_LAST_MASK; + break; + } + pList[count++] = parentPosition; + } + return Arrays.copyOf(pList, count); + } + + private static class CommitDataImpl implements CommitData { + + private final ObjectId tree; + + private final int[] parents; + + private final long commitTime; + + private final int generation; + + public CommitDataImpl(ObjectId tree, int[] parents, long commitTime, + int generation) { + this.tree = tree; + this.parents = parents; + this.commitTime = commitTime; + this.generation = generation; + } + + @Override + public ObjectId getTree() { + return tree; + } + + @Override + public int[] getParents() { + return parents; + } + + @Override + public long getCommitTime() { + return commitTime; + } + + @Override + public int getGeneration() { + return generation; + } + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/GraphCommits.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/GraphCommits.java new file mode 100644 index 0000000000..ccf6d0e66a --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/GraphCommits.java @@ -0,0 +1,142 @@ +/* + * Copyright (C) 2021, Tencent. + * + * 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.commitgraph; + +import java.io.IOException; +import java.util.Collections; +import java.util.Iterator; +import java.util.List; +import java.util.Set; + +import org.eclipse.jgit.annotations.NonNull; +import org.eclipse.jgit.errors.MissingObjectException; +import org.eclipse.jgit.internal.JGitText; +import org.eclipse.jgit.lib.AnyObjectId; +import org.eclipse.jgit.lib.Constants; +import org.eclipse.jgit.lib.ObjectId; +import org.eclipse.jgit.lib.ObjectIdOwnerMap; +import org.eclipse.jgit.lib.ProgressMonitor; +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.util.BlockList; + +/** + * The commits which are used by the commit-graph writer to: + * <ul> + * <li>List commits in SHA1 order.</li> + * <li>Get the position of a specific SHA1 in the list.</li> + * </ul> + * + * @since 6.5 + */ +public class GraphCommits implements Iterable<RevCommit> { + + /** + * Prepare and create the commits for + * {@link org.eclipse.jgit.internal.storage.commitgraph.CommitGraphWriter} + * from the RevWalk. + * + * @param pm + * progress monitor. + * @param wants + * the list of wanted objects, writer walks commits starting at + * these. Must not be {@code null}. + * @param walk + * the RevWalk to use. Must not be {@code null}. + * @return the commits' collection which are used by the commit-graph + * writer. Never null. + * @throws IOException + */ + public static GraphCommits fromWalk(ProgressMonitor pm, + @NonNull Set<? extends ObjectId> wants, @NonNull RevWalk walk) + throws IOException { + walk.reset(); + walk.sort(RevSort.NONE); + walk.setRetainBody(false); + for (ObjectId id : wants) { + RevObject o = walk.parseAny(id); + if (o instanceof RevCommit) { + walk.markStart((RevCommit) o); + } + } + List<RevCommit> commits = new BlockList<>(); + RevCommit c; + pm.beginTask(JGitText.get().findingCommitsForCommitGraph, + ProgressMonitor.UNKNOWN); + while ((c = walk.next()) != null) { + pm.update(1); + commits.add(c); + } + pm.endTask(); + return new GraphCommits(commits); + } + + private final List<RevCommit> sortedCommits; + + private final ObjectIdOwnerMap<CommitWithPosition> commitPosMap; + + private final int extraEdgeCnt; + + /** + * Initialize the GraphCommits. + * + * @param commits + * list of commits with their headers already parsed. + */ + private GraphCommits(List<RevCommit> commits) { + Collections.sort(commits); // sorted by name + sortedCommits = commits; + commitPosMap = new ObjectIdOwnerMap<>(); + int cnt = 0; + for (int i = 0; i < commits.size(); i++) { + RevCommit c = sortedCommits.get(i); + if (c.getParentCount() > 2) { + cnt += c.getParentCount() - 1; + } + commitPosMap.add(new CommitWithPosition(c, i)); + } + this.extraEdgeCnt = cnt; + } + + int getOidPosition(RevCommit c) throws MissingObjectException { + CommitWithPosition commitWithPosition = commitPosMap.get(c); + if (commitWithPosition == null) { + throw new MissingObjectException(c, Constants.OBJ_COMMIT); + } + return commitWithPosition.position; + } + + int getExtraEdgeCnt() { + return extraEdgeCnt; + } + + int size() { + return sortedCommits.size(); + } + + /** {@inheritDoc} */ + @Override + public Iterator<RevCommit> iterator() { + return sortedCommits.iterator(); + } + + private static class CommitWithPosition extends ObjectIdOwnerMap.Entry { + + final int position; + + CommitWithPosition(AnyObjectId id, int position) { + super(id); + this.position = position; + } + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/GraphObjectIndex.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/GraphObjectIndex.java new file mode 100644 index 0000000000..b0df46732e --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/GraphObjectIndex.java @@ -0,0 +1,119 @@ +/* + * Copyright (C) 2022, Tencent. + * + * 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.commitgraph; + +import org.eclipse.jgit.annotations.NonNull; +import org.eclipse.jgit.internal.JGitText; +import org.eclipse.jgit.lib.AnyObjectId; +import org.eclipse.jgit.lib.ObjectId; +import org.eclipse.jgit.util.NB; + +/** + * The index which are used by the commit-graph to: + * <ul> + * <li>Get the object in commit-graph by using a specific position.</li> + * <li>Get the position of a specific object in commit-graph.</li> + * </ul> + */ +class GraphObjectIndex { + + private static final int FANOUT = 256; + + private final int hashLength; + + private final int[] fanoutTable; + + private final byte[] oidLookup; + + private final long commitCnt; + + /** + * Initialize the GraphObjectIndex. + * + * @param hashLength + * length of object hash. + * @param oidFanout + * content of OID Fanout Chunk. + * @param oidLookup + * content of OID Lookup Chunk. + * @throws CommitGraphFormatException + * commit-graph file's format is different from we expected. + */ + GraphObjectIndex(int hashLength, @NonNull byte[] oidFanout, + @NonNull byte[] oidLookup) throws CommitGraphFormatException { + this.hashLength = hashLength; + this.oidLookup = oidLookup; + + int[] table = new int[FANOUT]; + long uint32; + for (int k = 0; k < table.length; k++) { + uint32 = NB.decodeUInt32(oidFanout, k * 4); + if (table[k] > Integer.MAX_VALUE) { + throw new CommitGraphFormatException( + JGitText.get().commitGraphFileIsTooLargeForJgit); + } + table[k] = (int) uint32; + } + this.fanoutTable = table; + this.commitCnt = table[FANOUT - 1]; + } + + /** + * Find the position in the commit-graph of the specified id. + * + * @param id + * the id for which the commit-graph position will be found. + * @return the commit-graph position or -1 if the object was not found. + */ + int findGraphPosition(AnyObjectId id) { + int levelOne = id.getFirstByte(); + int high = fanoutTable[levelOne]; + int low = 0; + if (levelOne > 0) { + low = fanoutTable[levelOne - 1]; + } + do { + int mid = (low + high) >>> 1; + int pos = objIdOffset(mid); + int cmp = id.compareTo(oidLookup, pos); + if (cmp < 0) { + high = mid; + } else if (cmp == 0) { + return mid; + } else { + low = mid + 1; + } + } while (low < high); + return -1; + } + + /** + * Get the object at the commit-graph position. + * + * @param graphPos + * the position in the commit-graph of the object. + * @return the ObjectId or null if it's not found. + */ + ObjectId getObjectId(int graphPos) { + if (graphPos < 0 || graphPos >= commitCnt) { + return null; + } + return ObjectId.fromRaw(oidLookup, objIdOffset(graphPos)); + } + + long getCommitCnt() { + return commitCnt; + } + + private int objIdOffset(int pos) { + return hashLength * pos; + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsGarbageCollector.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsGarbageCollector.java index 26d5b5b176..66bcf73987 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsGarbageCollector.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsGarbageCollector.java @@ -18,6 +18,7 @@ import static org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource.RE import static org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource.UNREACHABLE_GARBAGE; import static org.eclipse.jgit.internal.storage.dfs.DfsPackCompactor.configureReftable; import static org.eclipse.jgit.internal.storage.pack.PackExt.BITMAP_INDEX; +import static org.eclipse.jgit.internal.storage.pack.PackExt.COMMIT_GRAPH; import static org.eclipse.jgit.internal.storage.pack.PackExt.INDEX; import static org.eclipse.jgit.internal.storage.pack.PackExt.PACK; import static org.eclipse.jgit.internal.storage.pack.PackExt.REFTABLE; @@ -34,8 +35,11 @@ import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.concurrent.TimeUnit; +import java.util.stream.Collectors; import org.eclipse.jgit.internal.JGitText; +import org.eclipse.jgit.internal.storage.commitgraph.CommitGraphWriter; +import org.eclipse.jgit.internal.storage.commitgraph.GraphCommits; import org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource; import org.eclipse.jgit.internal.storage.file.PackIndex; import org.eclipse.jgit.internal.storage.file.PackReverseIndex; @@ -75,6 +79,7 @@ public class DfsGarbageCollector { private PackConfig packConfig; private ReftableConfig reftableConfig; private boolean convertToReftable = true; + private boolean writeCommitGraph; private boolean includeDeletes; private long reftableInitialMinUpdateIndex = 1; private long reftableInitialMaxUpdateIndex = 1; @@ -279,6 +284,20 @@ public class DfsGarbageCollector { } /** + * Toggle commit graph generation. + * <p> + * False by default. + * + * @param enable + * Allow/Disallow commit graph generation. + * @return {@code this} + */ + public DfsGarbageCollector setWriteCommitGraph(boolean enable) { + writeCommitGraph = enable; + return this; + } + + /** * Create a single new pack file containing all of the live objects. * <p> * This method safely decides which packs can be expired after the new pack @@ -642,6 +661,10 @@ public class DfsGarbageCollector { writeReftable(pack); } + if (source == GC) { + writeCommitGraph(pack, pm); + } + try (DfsOutputStream out = objdb.writeFile(pack, PACK)) { pw.writePack(pm, pm, out); pack.addFileExt(PACK); @@ -724,4 +747,25 @@ public class DfsGarbageCollector { pack.setReftableStats(writer.getStats()); } } + + private void writeCommitGraph(DfsPackDescription pack, ProgressMonitor pm) + throws IOException { + if (!writeCommitGraph || !objdb.getShallowCommits().isEmpty()) { + return; + } + + Set<ObjectId> allTips = refsBefore.stream().map(Ref::getObjectId) + .collect(Collectors.toUnmodifiableSet()); + + try (DfsOutputStream out = objdb.writeFile(pack, COMMIT_GRAPH); + RevWalk pool = new RevWalk(ctx)) { + GraphCommits gcs = GraphCommits.fromWalk(pm, allTips, pool); + CountingOutputStream cnt = new CountingOutputStream(out); + CommitGraphWriter writer = new CommitGraphWriter(gcs); + writer.write(pm, cnt); + pack.addFileExt(COMMIT_GRAPH); + pack.setFileSize(COMMIT_GRAPH, cnt.getCount()); + pack.setBlockSize(COMMIT_GRAPH, out.blockSize()); + } + } } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsPackFile.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsPackFile.java index 15511fed30..411777c7ad 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsPackFile.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsPackFile.java @@ -14,6 +14,7 @@ package org.eclipse.jgit.internal.storage.dfs; import static org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource.UNREACHABLE_GARBAGE; import static org.eclipse.jgit.internal.storage.pack.PackExt.BITMAP_INDEX; +import static org.eclipse.jgit.internal.storage.pack.PackExt.COMMIT_GRAPH; import static org.eclipse.jgit.internal.storage.pack.PackExt.INDEX; import static org.eclipse.jgit.internal.storage.pack.PackExt.PACK; import static org.eclipse.jgit.internal.storage.pack.PackExt.REVERSE_INDEX; @@ -37,6 +38,8 @@ import org.eclipse.jgit.errors.MissingObjectException; import org.eclipse.jgit.errors.PackInvalidException; import org.eclipse.jgit.errors.StoredObjectRepresentationNotAvailableException; import org.eclipse.jgit.internal.JGitText; +import org.eclipse.jgit.internal.storage.commitgraph.CommitGraph; +import org.eclipse.jgit.internal.storage.commitgraph.CommitGraphLoader; import org.eclipse.jgit.internal.storage.file.PackBitmapIndex; import org.eclipse.jgit.internal.storage.file.PackIndex; import org.eclipse.jgit.internal.storage.file.PackReverseIndex; @@ -69,6 +72,9 @@ public final class DfsPackFile extends BlockBasedFile { /** Index of compressed bitmap mapping entire object graph. */ private volatile PackBitmapIndex bitmapIndex; + /** Index of compressed commit graph mapping entire object graph. */ + private volatile CommitGraph commitGraph; + /** * Objects we have tried to read, and discovered to be corrupt. * <p> @@ -215,6 +221,43 @@ public final class DfsPackFile extends BlockBasedFile { return bitmapIndex; } + /** + * Get the Commit Graph for this PackFile. + * + * @param ctx + * reader context to support reading from the backing store if + * the index is not already loaded in memory. + * @return {@link org.eclipse.jgit.internal.storage.commitgraph.CommitGraph}, + * null if pack doesn't have it. + * @throws java.io.IOException + * the Commit Graph is not available, or is corrupt. + */ + public CommitGraph getCommitGraph(DfsReader ctx) throws IOException { + if (invalid || isGarbage() || !desc.hasFileExt(COMMIT_GRAPH)) { + return null; + } + + if (commitGraph != null) { + return commitGraph; + } + + DfsStreamKey commitGraphKey = desc.getStreamKey(COMMIT_GRAPH); + AtomicBoolean cacheHit = new AtomicBoolean(true); + DfsBlockCache.Ref<CommitGraph> cgref = cache + .getOrLoadRef(commitGraphKey, REF_POSITION, () -> { + cacheHit.set(false); + return loadCommitGraph(ctx, commitGraphKey); + }); + if (cacheHit.get()) { + ctx.stats.commitGraphCacheHit++; + } + CommitGraph cg = cgref.get(); + if (commitGraph == null && cg != null) { + commitGraph = cg; + } + return commitGraph; + } + PackReverseIndex getReverseIdx(DfsReader ctx) throws IOException { if (reverseIndex != null) { return reverseIndex; @@ -1081,4 +1124,37 @@ public final class DfsPackFile extends BlockBasedFile { desc.getFileName(BITMAP_INDEX)), e); } } + + private DfsBlockCache.Ref<CommitGraph> loadCommitGraph(DfsReader ctx, + DfsStreamKey cgkey) throws IOException { + ctx.stats.readCommitGraph++; + long start = System.nanoTime(); + try (ReadableChannel rc = ctx.db.openFile(desc, COMMIT_GRAPH)) { + long size; + CommitGraph cg; + try { + InputStream in = Channels.newInputStream(rc); + int wantSize = 8192; + int bs = rc.blockSize(); + if (0 < bs && bs < wantSize) { + bs = (wantSize / bs) * bs; + } else if (bs <= 0) { + bs = wantSize; + } + in = new BufferedInputStream(in, bs); + cg = CommitGraphLoader.read(in); + } finally { + size = rc.position(); + ctx.stats.readCommitGraphBytes += size; + ctx.stats.readCommitGraphMicros += elapsedMicros(start); + } + commitGraph = cg; + return new DfsBlockCache.Ref<>(cgkey, REF_POSITION, size, cg); + } catch (IOException e) { + throw new IOException( + MessageFormat.format(DfsText.get().cannotReadCommitGraph, + desc.getFileName(COMMIT_GRAPH)), + e); + } + } } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReader.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReader.java index d043b05fb9..8d8a766b0f 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReader.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReader.java @@ -23,6 +23,7 @@ import java.util.HashSet; import java.util.Iterator; import java.util.LinkedList; import java.util.List; +import java.util.Optional; import java.util.Set; import java.util.zip.DataFormatException; import java.util.zip.Inflater; @@ -31,6 +32,7 @@ import org.eclipse.jgit.errors.IncorrectObjectTypeException; import org.eclipse.jgit.errors.MissingObjectException; import org.eclipse.jgit.errors.StoredObjectRepresentationNotAvailableException; import org.eclipse.jgit.internal.JGitText; +import org.eclipse.jgit.internal.storage.commitgraph.CommitGraph; import org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackList; import org.eclipse.jgit.internal.storage.file.BitmapIndexImpl; import org.eclipse.jgit.internal.storage.file.PackBitmapIndex; @@ -123,6 +125,18 @@ public class DfsReader extends ObjectReader implements ObjectReuseAsIs { /** {@inheritDoc} */ @Override + public Optional<CommitGraph> getCommitGraph() throws IOException { + for (DfsPackFile pack : db.getPacks()) { + CommitGraph cg = pack.getCommitGraph(this); + if (cg != null) { + return Optional.of(cg); + } + } + return Optional.empty(); + } + + /** {@inheritDoc} */ + @Override public Collection<CachedPack> getCachedPacksAndUpdate( BitmapBuilder needBitmap) throws IOException { for (DfsPackFile pack : db.getPacks()) { diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReaderIoStats.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReaderIoStats.java index 5c47425013..5ac7985e97 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReaderIoStats.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReaderIoStats.java @@ -28,6 +28,9 @@ public class DfsReaderIoStats { /** Total number of cache hits for bitmap indexes. */ long bitmapCacheHit; + /** Total number of cache hits for commit graphs. */ + long commitGraphCacheHit; + /** Total number of complete pack indexes read into memory. */ long readIdx; @@ -37,15 +40,24 @@ public class DfsReaderIoStats { /** Total number of reverse indexes added into memory. */ long readReverseIdx; + /** Total number of complete commit graphs read into memory. */ + long readCommitGraph; + /** Total number of bytes read from pack indexes. */ long readIdxBytes; + /** Total number of bytes read from commit graphs. */ + long readCommitGraphBytes; + /** Total microseconds spent reading pack indexes. */ long readIdxMicros; /** Total microseconds spent creating reverse indexes. */ long readReverseIdxMicros; + /** Total microseconds spent creating commit graphs. */ + long readCommitGraphMicros; + /** Total number of bytes read from bitmap indexes. */ long readBitmapIdxBytes; @@ -123,6 +135,15 @@ public class DfsReaderIoStats { } /** + * Get total number of commit graph cache hits. + * + * @return total number of commit graph cache hits. + */ + public long getCommitGraphCacheHits() { + return stats.commitGraphCacheHit; + } + + /** * Get total number of complete pack indexes read into memory. * * @return total number of complete pack indexes read into memory. @@ -141,6 +162,15 @@ public class DfsReaderIoStats { } /** + * Get total number of times the commit graph read into memory. + * + * @return total number of commit graph read into memory. + */ + public long getReadCommitGraphCount() { + return stats.readCommitGraph; + } + + /** * Get total number of complete bitmap indexes read into memory. * * @return total number of complete bitmap indexes read into memory. @@ -159,6 +189,15 @@ public class DfsReaderIoStats { } /** + * Get total number of bytes read from commit graphs. + * + * @return total number of bytes read from commit graphs. + */ + public long getCommitGraphBytes() { + return stats.readCommitGraphBytes; + } + + /** * Get total microseconds spent reading pack indexes. * * @return total microseconds spent reading pack indexes. @@ -177,6 +216,15 @@ public class DfsReaderIoStats { } /** + * Get total microseconds spent reading commit graphs. + * + * @return total microseconds spent reading commit graphs. + */ + public long getReadCommitGraphMicros() { + return stats.readCommitGraphMicros; + } + + /** * Get total number of bytes read from bitmap indexes. * * @return total number of bytes read from bitmap indexes. diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsText.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsText.java index df565e568d..f36ec06d3f 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsText.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsText.java @@ -28,6 +28,7 @@ public class DfsText extends TranslationBundle { // @formatter:off /***/ public String cannotReadIndex; + /***/ public String cannotReadCommitGraph; /***/ public String shortReadOfBlock; /***/ public String shortReadOfIndex; /***/ public String willNotStoreEmptyPack; diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/InMemoryRepository.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/InMemoryRepository.java index 5a8207ed01..583b8b3f6b 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/InMemoryRepository.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/InMemoryRepository.java @@ -66,7 +66,16 @@ public class InMemoryRepository extends DfsRepository { InMemoryRepository(Builder builder) { super(builder); objdb = new MemObjDatabase(this); - refdb = new MemRefDatabase(); + refdb = createRefDatabase(); + } + + /** + * Creates a new in-memory ref database. + * + * @return a new in-memory reference database. + */ + protected MemRefDatabase createRefDatabase() { + return new MemRefDatabase(); } /** {@inheritDoc} */ diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/CachedObjectDirectory.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/CachedObjectDirectory.java index 9272bf3f59..2e19580f5f 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/CachedObjectDirectory.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/CachedObjectDirectory.java @@ -15,6 +15,7 @@ import java.io.File; import java.io.IOException; import java.util.Collection; import java.util.HashSet; +import java.util.Optional; import java.util.Set; import org.eclipse.jgit.internal.storage.file.ObjectDirectory.AlternateHandle; @@ -22,6 +23,7 @@ import org.eclipse.jgit.internal.storage.pack.ObjectToPack; import org.eclipse.jgit.internal.storage.pack.PackWriter; import org.eclipse.jgit.lib.AbbreviatedObjectId; import org.eclipse.jgit.lib.AnyObjectId; +import org.eclipse.jgit.internal.storage.commitgraph.CommitGraph; import org.eclipse.jgit.lib.Config; import org.eclipse.jgit.lib.Constants; import org.eclipse.jgit.lib.ObjectDatabase; @@ -259,6 +261,12 @@ class CachedObjectDirectory extends FileObjectDatabase { return wrapped.getPacks(); } + /** {@inheritDoc} */ + @Override + public Optional<CommitGraph> getCommitGraph() { + return wrapped.getCommitGraph(); + } + private static class UnpackedObjectId extends ObjectIdOwnerMap.Entry { UnpackedObjectId(AnyObjectId id) { super(id); diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/FileCommitGraph.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/FileCommitGraph.java new file mode 100644 index 0000000000..44429a7786 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/FileCommitGraph.java @@ -0,0 +1,135 @@ +/* + * Copyright (C) 2022, Tencent. + * + * 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.file; + +import java.io.File; +import java.io.FileNotFoundException; +import java.io.IOException; +import java.text.MessageFormat; +import java.util.concurrent.atomic.AtomicReference; + +import org.eclipse.jgit.annotations.NonNull; +import org.eclipse.jgit.internal.JGitText; +import org.eclipse.jgit.internal.storage.commitgraph.CommitGraphFormatException; +import org.eclipse.jgit.internal.storage.commitgraph.CommitGraphLoader; +import org.eclipse.jgit.internal.storage.commitgraph.CommitGraph; +import org.eclipse.jgit.lib.Constants; +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +/** + * Traditional file system for commit-graph. + * <p> + * This is the commit-graph file representation for a Git object database. Each + * call to {@link FileCommitGraph#get()} will recheck for newer versions. + */ +public class FileCommitGraph { + private final static Logger LOG = LoggerFactory + .getLogger(FileCommitGraph.class); + + private final AtomicReference<GraphSnapshot> baseGraph; + + /** + * Initialize a reference to an on-disk commit-graph. + * + * @param objectsDir + * the location of the <code>objects</code> directory. + */ + FileCommitGraph(File objectsDir) { + this.baseGraph = new AtomicReference<>(new GraphSnapshot( + new File(objectsDir, Constants.INFO_COMMIT_GRAPH))); + } + + /** + * The method will first scan whether the ".git/objects/info/commit-graph" + * has been modified, if so, it will re-parse the file, otherwise it will + * return the same result as the last time. + * + * @return commit-graph or null if commit-graph file does not exist or + * corrupt. + */ + CommitGraph get() { + GraphSnapshot original = baseGraph.get(); + synchronized (baseGraph) { + GraphSnapshot o, n; + do { + o = baseGraph.get(); + if (o != original) { + // Another thread did the scan for us, while we + // were blocked on the monitor above. + // + return o.getCommitGraph(); + } + n = o.refresh(); + if (n == o) { + return n.getCommitGraph(); + } + } while (!baseGraph.compareAndSet(o, n)); + return n.getCommitGraph(); + } + } + + private static final class GraphSnapshot { + private final File file; + + private final FileSnapshot snapshot; + + private final CommitGraph graph; + + GraphSnapshot(@NonNull File file) { + this(file, null, null); + } + + GraphSnapshot(@NonNull File file, FileSnapshot snapshot, + CommitGraph graph) { + this.file = file; + this.snapshot = snapshot; + this.graph = graph; + } + + CommitGraph getCommitGraph() { + return graph; + } + + GraphSnapshot refresh() { + if (graph == null && !file.exists()) { + // commit-graph file didn't exist + return this; + } + if (snapshot != null && !snapshot.isModified(file)) { + // commit-graph file was not modified + return this; + } + return new GraphSnapshot(file, FileSnapshot.save(file), open(file)); + } + + private static CommitGraph open(File file) { + try { + return CommitGraphLoader.open(file); + } catch (FileNotFoundException noFile) { + // ignore if file do not exist + return null; + } catch (IOException e) { + if (e instanceof CommitGraphFormatException) { + LOG.warn( + MessageFormat.format( + JGitText.get().corruptCommitGraph, file), + e); + } else { + LOG.error(MessageFormat.format( + JGitText.get().exceptionWhileLoadingCommitGraph, + file), e); + } + return null; + } + } + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/FileObjectDatabase.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/FileObjectDatabase.java index e97ed393a1..aa578d31ba 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/FileObjectDatabase.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/FileObjectDatabase.java @@ -13,8 +13,10 @@ package org.eclipse.jgit.internal.storage.file; import java.io.File; import java.io.IOException; import java.util.Collection; +import java.util.Optional; import java.util.Set; +import org.eclipse.jgit.internal.storage.commitgraph.CommitGraph; import org.eclipse.jgit.internal.storage.pack.ObjectToPack; import org.eclipse.jgit.internal.storage.pack.PackWriter; import org.eclipse.jgit.lib.AbbreviatedObjectId; @@ -72,4 +74,6 @@ abstract class FileObjectDatabase extends ObjectDatabase { abstract Pack openPack(File pack) throws IOException; abstract Collection<Pack> getPacks(); + + abstract Optional<CommitGraph> getCommitGraph(); } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/GC.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/GC.java index 799d058b7d..06ec80c05f 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/GC.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/GC.java @@ -14,6 +14,7 @@ import static org.eclipse.jgit.internal.storage.pack.PackExt.BITMAP_INDEX; import static org.eclipse.jgit.internal.storage.pack.PackExt.INDEX; import static org.eclipse.jgit.internal.storage.pack.PackExt.KEEP; import static org.eclipse.jgit.internal.storage.pack.PackExt.PACK; +import static org.eclipse.jgit.internal.storage.pack.PackExt.REVERSE_INDEX; import java.io.File; import java.io.FileOutputStream; @@ -69,10 +70,13 @@ import org.eclipse.jgit.errors.IncorrectObjectTypeException; import org.eclipse.jgit.errors.MissingObjectException; import org.eclipse.jgit.errors.NoWorkTreeException; import org.eclipse.jgit.internal.JGitText; +import org.eclipse.jgit.internal.storage.commitgraph.CommitGraphWriter; +import org.eclipse.jgit.internal.storage.commitgraph.GraphCommits; import org.eclipse.jgit.internal.storage.pack.PackExt; import org.eclipse.jgit.internal.storage.pack.PackWriter; import org.eclipse.jgit.lib.ConfigConstants; import org.eclipse.jgit.lib.Constants; +import org.eclipse.jgit.lib.CoreConfig; import org.eclipse.jgit.lib.FileMode; import org.eclipse.jgit.lib.NullProgressMonitor; import org.eclipse.jgit.lib.ObjectId; @@ -121,19 +125,17 @@ public class GC { private static final Pattern PATTERN_LOOSE_OBJECT = Pattern .compile("[0-9a-fA-F]{38}"); //$NON-NLS-1$ - private static final String PACK_EXT = "." + PackExt.PACK.getExtension();//$NON-NLS-1$ + private static final Set<PackExt> PARENT_EXTS = Set.of(PACK, KEEP); - private static final String BITMAP_EXT = "." //$NON-NLS-1$ - + PackExt.BITMAP_INDEX.getExtension(); - - private static final String INDEX_EXT = "." + PackExt.INDEX.getExtension(); //$NON-NLS-1$ - - private static final String KEEP_EXT = "." + PackExt.KEEP.getExtension(); //$NON-NLS-1$ + private static final Set<PackExt> CHILD_EXTS = Set.of(BITMAP_INDEX, INDEX, + REVERSE_INDEX); private static final int DEFAULT_AUTOPACKLIMIT = 50; private static final int DEFAULT_AUTOLIMIT = 6700; + private static final boolean DEFAULT_WRITE_COMMIT_GRAPH = false; + private static volatile ExecutorService executor; /** @@ -285,6 +287,9 @@ public class GC { Collection<Pack> newPacks = repack(); prune(Collections.emptySet()); // TODO: implement rerere_gc(pm); + if (shouldWriteCommitGraphWhenGc()) { + writeCommitGraph(refsToObjectIds(getAllRefs())); + } return newPacks; } } @@ -902,6 +907,105 @@ public class GC { return ret; } + private Set<ObjectId> refsToObjectIds(Collection<Ref> refs) + throws IOException { + Set<ObjectId> objectIds = new HashSet<>(); + for (Ref ref : refs) { + checkCancelled(); + if (ref.getPeeledObjectId() != null) { + objectIds.add(ref.getPeeledObjectId()); + continue; + } + + if (ref.getObjectId() != null) { + objectIds.add(ref.getObjectId()); + } + } + return objectIds; + } + + /** + * Generate a new commit-graph file when 'core.commitGraph' is true. + * + * @param wants + * the list of wanted objects, writer walks commits starting at + * these. Must not be {@code null}. + * @throws IOException + */ + void writeCommitGraph(@NonNull Set<? extends ObjectId> wants) + throws IOException { + if (!repo.getConfig().get(CoreConfig.KEY).enableCommitGraph()) { + return; + } + if (repo.getObjectDatabase().getShallowCommits().size() > 0) { + return; + } + checkCancelled(); + if (wants.isEmpty()) { + return; + } + File tmpFile = null; + try (RevWalk walk = new RevWalk(repo)) { + CommitGraphWriter writer = new CommitGraphWriter( + GraphCommits.fromWalk(pm, wants, walk)); + tmpFile = File.createTempFile("commit_", ".graph_tmp", //$NON-NLS-1$//$NON-NLS-2$ + repo.getObjectDatabase().getInfoDirectory()); + // write the commit-graph file + try (FileOutputStream fos = new FileOutputStream(tmpFile); + FileChannel channel = fos.getChannel(); + OutputStream channelStream = Channels + .newOutputStream(channel)) { + writer.write(pm, channelStream); + channel.force(true); + } + + // rename the temporary file to real file + File realFile = new File(repo.getObjectsDirectory(), + Constants.INFO_COMMIT_GRAPH); + FileUtils.rename(tmpFile, realFile, StandardCopyOption.ATOMIC_MOVE); + } finally { + if (tmpFile != null && tmpFile.exists()) { + tmpFile.delete(); + } + } + deleteTempCommitGraph(); + } + + private void deleteTempCommitGraph() { + Path objectsDir = repo.getObjectDatabase().getInfoDirectory().toPath(); + Instant threshold = Instant.now().minus(1, ChronoUnit.DAYS); + if (!Files.exists(objectsDir)) { + return; + } + try (DirectoryStream<Path> stream = Files.newDirectoryStream(objectsDir, + "commit_*_tmp")) { //$NON-NLS-1$ + stream.forEach(t -> { + try { + Instant lastModified = Files.getLastModifiedTime(t) + .toInstant(); + if (lastModified.isBefore(threshold)) { + Files.deleteIfExists(t); + } + } catch (IOException e) { + LOG.error(e.getMessage(), e); + } + }); + } catch (IOException e) { + LOG.error(e.getMessage(), e); + } + } + + /** + * If {@code true}, will rewrite the commit-graph file when gc is run. + * + * @return true if commit-graph should be writen. Default is {@code false}. + */ + boolean shouldWriteCommitGraphWhenGc() { + return repo.getConfig().getBoolean(ConfigConstants.CONFIG_GC_SECTION, + ConfigConstants.CONFIG_KEY_WRITE_COMMIT_GRAPH, + DEFAULT_WRITE_COMMIT_GRAPH); + } + private static boolean isHead(Ref ref) { return ref.getName().startsWith(Constants.R_HEADS); } @@ -962,47 +1066,52 @@ public class GC { } } + private static Optional<PackFile> toPackFileWithValidExt( + Path packFilePath) { + try { + PackFile packFile = new PackFile(packFilePath.toFile()); + if (packFile.getPackExt() == null) { + return Optional.empty(); + } + return Optional.of(packFile); + } catch (IllegalArgumentException e) { + return Optional.empty(); + } + } + /** * Deletes orphans * <p> - * A file is considered an orphan if it is either a "bitmap" or an index - * file, and its corresponding pack file is missing in the list. + * A file is considered an orphan if it is some type of index file, but + * there is not a corresponding pack or keep file present in the directory. * </p> */ private void deleteOrphans() { Path packDir = repo.getObjectDatabase().getPackDirectory().toPath(); - List<String> fileNames = null; + List<PackFile> childFiles; + Set<String> seenParentIds = new HashSet<>(); try (Stream<Path> files = Files.list(packDir)) { - fileNames = files.map(path -> path.getFileName().toString()) - .filter(name -> (name.endsWith(PACK_EXT) - || name.endsWith(BITMAP_EXT) - || name.endsWith(INDEX_EXT) - || name.endsWith(KEEP_EXT))) - // sort files with same base name in the order: - // .pack, .keep, .index, .bitmap to avoid look ahead - .sorted(Collections.reverseOrder()) - .collect(Collectors.toList()); + childFiles = files.map(GC::toPackFileWithValidExt) + .filter(Optional::isPresent).map(Optional::get) + .filter(packFile -> { + PackExt ext = packFile.getPackExt(); + if (PARENT_EXTS.contains(ext)) { + seenParentIds.add(packFile.getId()); + return false; + } + return CHILD_EXTS.contains(ext); + }).collect(Collectors.toList()); } catch (IOException e) { LOG.error(e.getMessage(), e); return; } - if (fileNames == null) { - return; - } - String latestId = null; - for (String n : fileNames) { - PackFile pf = new PackFile(packDir.toFile(), n); - PackExt ext = pf.getPackExt(); - if (ext.equals(PACK) || ext.equals(KEEP)) { - latestId = pf.getId(); - } - if (latestId == null || !pf.getId().equals(latestId)) { - // no pack or keep for this id + for (PackFile child : childFiles) { + if (!seenParentIds.contains(child.getId())) { try { - FileUtils.delete(pf, + FileUtils.delete(child, FileUtils.RETRY | FileUtils.SKIP_MISSING); - LOG.warn(JGitText.get().deletedOrphanInPackDir, pf); + LOG.warn(JGitText.get().deletedOrphanInPackDir, child); } catch (IOException e) { LOG.error(e.getMessage(), e); } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/LooseObjects.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/LooseObjects.java index b9af83d24d..326c5f6457 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/LooseObjects.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/LooseObjects.java @@ -254,7 +254,7 @@ class LooseObjects { // refresh directory to work around NFS caching issue } return getSizeWithoutRefresh(curs, id); - } catch (FileNotFoundException e) { + } catch (FileNotFoundException unused) { if (fileFor(id).exists()) { throw noFile; } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/ObjectDirectory.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/ObjectDirectory.java index 53fdc66082..f27daad897 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/ObjectDirectory.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/ObjectDirectory.java @@ -28,6 +28,7 @@ import java.util.Collections; import java.util.HashSet; import java.util.List; import java.util.Objects; +import java.util.Optional; import java.util.Set; import java.util.concurrent.atomic.AtomicReference; @@ -38,8 +39,10 @@ import org.eclipse.jgit.internal.storage.pack.PackExt; import org.eclipse.jgit.internal.storage.pack.PackWriter; import org.eclipse.jgit.lib.AbbreviatedObjectId; import org.eclipse.jgit.lib.AnyObjectId; +import org.eclipse.jgit.internal.storage.commitgraph.CommitGraph; import org.eclipse.jgit.lib.Config; import org.eclipse.jgit.lib.Constants; +import org.eclipse.jgit.lib.CoreConfig; import org.eclipse.jgit.lib.ObjectDatabase; import org.eclipse.jgit.lib.ObjectId; import org.eclipse.jgit.lib.ObjectLoader; @@ -86,6 +89,8 @@ public class ObjectDirectory extends FileObjectDatabase { private final File alternatesFile; + private final FileCommitGraph fileCommitGraph; + private final FS fs; private final AtomicReference<AlternateHandle[]> alternates; @@ -125,6 +130,7 @@ public class ObjectDirectory extends FileObjectDatabase { loose = new LooseObjects(config, objects); packed = new PackDirectory(config, packDirectory); preserved = new PackDirectory(config, preservedDirectory); + fileCommitGraph = new FileCommitGraph(objects); this.fs = fs; this.shallowFile = shallowFile; @@ -228,6 +234,15 @@ public class ObjectDirectory extends FileObjectDatabase { return count; } + /** {@inheritDoc} */ + @Override + public Optional<CommitGraph> getCommitGraph() { + if (config.get(CoreConfig.KEY).enableCommitGraph()) { + return Optional.ofNullable(fileCommitGraph.get()); + } + return Optional.empty(); + } + /** * {@inheritDoc} * <p> @@ -809,4 +824,8 @@ public class ObjectDirectory extends FileObjectDatabase { AlternateHandle.Id getAlternateId() { return handle.getId(); } + + File getInfoDirectory() { + return infoDirectory; + } } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackBitmapIndexV1.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackBitmapIndexV1.java index 21aba3e6a3..988dc6c4ff 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackBitmapIndexV1.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackBitmapIndexV1.java @@ -220,7 +220,7 @@ class PackBitmapIndexV1 extends BasePackBitmapIndex { long offset = packIndex.findOffset(objectId); if (offset == -1) return -1; - return reverseIndex.findPostion(offset); + return reverseIndex.findPosition(offset); } /** {@inheritDoc} */ diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndex.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndex.java index 942cc96745..f4f62d4205 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndex.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndex.java @@ -241,6 +241,17 @@ public abstract class PackIndex public abstract long findOffset(AnyObjectId objId); /** + * Locate the position of this id in the list of object-ids in the index + * + * @param objId + * name of the object to locate within the index + * @return position of the object-id in the lexicographically ordered list + * of ids stored in this index; -1 if the object does not exist in + * this index and is thus not stored in the associated pack. + */ + public abstract int findPosition(AnyObjectId objId); + + /** * Retrieve stored CRC32 checksum of the requested object raw-data * (including header). * diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndexV1.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndexV1.java index eb0ac6a062..fff410b4ce 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndexV1.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndexV1.java @@ -32,6 +32,8 @@ import org.eclipse.jgit.util.NB; class PackIndexV1 extends PackIndex { private static final int IDX_HDR_LEN = 256 * 4; + private static final int RECORD_SIZE = 4 + Constants.OBJECT_ID_LENGTH; + private final long[] idxHeader; byte[][] idxdata; @@ -131,8 +133,50 @@ class PackIndexV1 extends PackIndex { public long findOffset(AnyObjectId objId) { final int levelOne = objId.getFirstByte(); byte[] data = idxdata[levelOne]; - if (data == null) + int pos = levelTwoPosition(objId, data); + if (pos < 0) { + return -1; + } + // The records are (offset, objectid), pos points to objectId + int b0 = data[pos - 4] & 0xff; + int b1 = data[pos - 3] & 0xff; + int b2 = data[pos - 2] & 0xff; + int b3 = data[pos - 1] & 0xff; + return (((long) b0) << 24) | (b1 << 16) | (b2 << 8) | (b3); + } + + /** {@inheritDoc} */ + @Override + public int findPosition(AnyObjectId objId) { + int levelOne = objId.getFirstByte(); + int levelTwo = levelTwoPosition(objId, idxdata[levelOne]); + if (levelTwo < 0) { return -1; + } + long objsBefore = levelOne == 0 ? 0 : idxHeader[levelOne - 1]; + return (int) objsBefore + ((levelTwo - 4) / RECORD_SIZE); + } + + /** + * Find position in level two data of this objectId + * + * Records are (offset, objectId), so to read the corresponding offset, + * caller must substract from this position. + * + * @param objId + * ObjectId we are looking for + * @param data + * Blob of second level data with a series of (offset, objectid) + * pairs where we should find objId + * + * @return position in the byte[] where the objectId starts. -1 if not + * found. + */ + private int levelTwoPosition(AnyObjectId objId, byte[] data) { + if (data == null || data.length == 0) { + return -1; + } + int high = data.length / (4 + Constants.OBJECT_ID_LENGTH); int low = 0; do { @@ -142,11 +186,7 @@ class PackIndexV1 extends PackIndex { if (cmp < 0) high = mid; else if (cmp == 0) { - int b0 = data[pos - 4] & 0xff; - int b1 = data[pos - 3] & 0xff; - int b2 = data[pos - 2] & 0xff; - int b3 = data[pos - 1] & 0xff; - return (((long) b0) << 24) | (b1 << 16) | (b2 << 8) | (b3); + return pos; } else low = mid + 1; } while (low < high); @@ -204,7 +244,7 @@ class PackIndexV1 extends PackIndex { } private static int idOffset(int mid) { - return ((4 + Constants.OBJECT_ID_LENGTH) * mid) + 4; + return (RECORD_SIZE * mid) + 4; } private class IndexV1Iterator extends EntriesIterator { diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndexV2.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndexV2.java index 09397e316d..7a390060c7 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndexV2.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndexV2.java @@ -192,6 +192,18 @@ class PackIndexV2 extends PackIndex { return getOffset(levelOne, levelTwo); } + /** {@inheritDoc} */ + @Override + public int findPosition(AnyObjectId objId) { + int levelOne = objId.getFirstByte(); + int levelTwo = binarySearchLevelTwo(objId, levelOne); + if (levelTwo < 0) { + return -1; + } + long objsBefore = levelOne == 0 ? 0 : fanoutTable[levelOne - 1]; + return (int) objsBefore + levelTwo; + } + private long getOffset(int levelOne, int levelTwo) { final long p = NB.decodeUInt32(offset32[levelOne], levelTwo << 2); if ((p & IS_O64) != 0) diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackObjectSizeIndex.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackObjectSizeIndex.java new file mode 100644 index 0000000000..1c3797c509 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackObjectSizeIndex.java @@ -0,0 +1,45 @@ +/* + * Copyright (C) 2022, Google LLC and others + * + * 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.file; + +/** + * Index of object sizes in a pack + * + * It is not guaranteed that the implementation contains the sizes of all + * objects (e.g. it could store only objects over certain threshold). + */ +public interface PackObjectSizeIndex { + + /** + * Returns the inflated size of the object. + * + * @param idxOffset + * position in the pack (as returned from PackIndex) + * @return size of the object, -1 if not found in the index. + */ + long getSize(int idxOffset); + + /** + * Number of objects in the index + * + * @return number of objects in the index + */ + long getObjectCount(); + + + /** + * Minimal size of an object to be included in this index + * + * Cut-off value used at generation time to decide what objects to index. + * + * @return size in bytes + */ + int getThreshold(); +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackObjectSizeIndexLoader.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackObjectSizeIndexLoader.java new file mode 100644 index 0000000000..9d6941823a --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackObjectSizeIndexLoader.java @@ -0,0 +1,43 @@ +/* + * Copyright (C) 2022, Google LLC and others + * + * 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.file; + +import java.io.IOException; +import java.io.InputStream; +import java.util.Arrays; + +/** + * Chooses the specific implementation of the object-size index based on the + * file version. + */ +public class PackObjectSizeIndexLoader { + + /** + * Read an object size index from the stream + * + * @param in + * input stream at the beginning of the object size data + * @return an implementation of the object size index + * @throws IOException + * error reading the streams + */ + public static PackObjectSizeIndex load(InputStream in) throws IOException { + byte[] header = in.readNBytes(4); + if (!Arrays.equals(header, PackObjectSizeIndexWriter.HEADER)) { + throw new IOException("Stream is not an object index"); //$NON-NLS-1$ + } + + int version = in.readNBytes(1)[0]; + if (version != 1) { + throw new IOException("Unknown object size version: " + version); //$NON-NLS-1$ + } + return PackObjectSizeIndexV1.parse(in); + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackObjectSizeIndexV1.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackObjectSizeIndexV1.java new file mode 100644 index 0000000000..be2ff67e4f --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackObjectSizeIndexV1.java @@ -0,0 +1,223 @@ +/* + * Copyright (C) 2022, Google LLC and others + * + * 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.file; + +import java.io.IOException; +import java.io.InputStream; +import java.io.UnsupportedEncodingException; +import java.util.Arrays; + +import org.eclipse.jgit.internal.JGitText; +import org.eclipse.jgit.util.NB; + +/** + * Memory representation of the object-size index + * + * The object size index is a map from position in the primary idx (i.e. + * position of the object-id in lexicographical order) to size. + * + * Most of the positions fit in unsigned 3 bytes (up to 16 million) + */ +class PackObjectSizeIndexV1 implements PackObjectSizeIndex { + + private static final byte BITS_24 = 0x18; + + private static final byte BITS_32 = 0x20; + + private final int threshold; + + private final UInt24Array positions24; + + private final int[] positions32; + + /** + * Parallel array to concat(positions24, positions32) with the size of the + * objects. + * + * A value >= 0 is the size of the object. A negative value means the size + * doesn't fit in an int and |value|-1 is the position for the size in the + * size64 array e.g. a value of -1 is sizes64[0], -2 = sizes64[1], ... + */ + private final int[] sizes32; + + private final long[] sizes64; + + static PackObjectSizeIndex parse(InputStream in) throws IOException { + /** Header and version already out of the input */ + IndexInputStreamReader stream = new IndexInputStreamReader(in); + int threshold = stream.readInt(); // minSize + int objCount = stream.readInt(); + if (objCount == 0) { + return new EmptyPackObjectSizeIndex(threshold); + } + return new PackObjectSizeIndexV1(stream, threshold, objCount); + } + + private PackObjectSizeIndexV1(IndexInputStreamReader stream, int threshold, + int objCount) throws IOException { + this.threshold = threshold; + UInt24Array pos24 = null; + int[] pos32 = null; + + byte positionEncoding; + while ((positionEncoding = stream.readByte()) != 0) { + if (Byte.compareUnsigned(positionEncoding, BITS_24) == 0) { + int sz = stream.readInt(); + pos24 = new UInt24Array(stream.readNBytes(sz * 3)); + } else if (Byte.compareUnsigned(positionEncoding, BITS_32) == 0) { + int sz = stream.readInt(); + pos32 = stream.readIntArray(sz); + } else { + throw new UnsupportedEncodingException( + String.format(JGitText.get().unknownPositionEncoding, + Integer.toHexString(positionEncoding))); + } + } + positions24 = pos24 != null ? pos24 : UInt24Array.EMPTY; + positions32 = pos32 != null ? pos32 : new int[0]; + + sizes32 = stream.readIntArray(objCount); + int c64sizes = stream.readInt(); + if (c64sizes == 0) { + sizes64 = new long[0]; + return; + } + sizes64 = stream.readLongArray(c64sizes); + int c128sizes = stream.readInt(); + if (c128sizes != 0) { + // this MUST be 0 (we don't support 128 bits sizes yet) + throw new IOException(JGitText.get().unsupportedSizesObjSizeIndex); + } + } + + @Override + public long getSize(int idxOffset) { + int pos = -1; + if (!positions24.isEmpty() && idxOffset <= positions24.getLastValue()) { + pos = positions24.binarySearch(idxOffset); + } else if (positions32.length > 0 && idxOffset >= positions32[0]) { + int pos32 = Arrays.binarySearch(positions32, idxOffset); + if (pos32 >= 0) { + pos = pos32 + positions24.size(); + } + } + if (pos < 0) { + return -1; + } + + int objSize = sizes32[pos]; + if (objSize < 0) { + int secondPos = Math.abs(objSize) - 1; + return sizes64[secondPos]; + } + return objSize; + } + + @Override + public long getObjectCount() { + return positions24.size() + positions32.length; + } + + @Override + public int getThreshold() { + return threshold; + } + + /** + * Wrapper to read parsed content from the byte stream + */ + private static class IndexInputStreamReader { + + private final byte[] buffer = new byte[8]; + + private final InputStream in; + + IndexInputStreamReader(InputStream in) { + this.in = in; + } + + int readInt() throws IOException { + int n = in.readNBytes(buffer, 0, 4); + if (n < 4) { + throw new IOException(JGitText.get().unableToReadFullInt); + } + return NB.decodeInt32(buffer, 0); + } + + int[] readIntArray(int intsCount) throws IOException { + if (intsCount == 0) { + return new int[0]; + } + + int[] dest = new int[intsCount]; + for (int i = 0; i < intsCount; i++) { + dest[i] = readInt(); + } + return dest; + } + + long readLong() throws IOException { + int n = in.readNBytes(buffer, 0, 8); + if (n < 8) { + throw new IOException(JGitText.get().unableToReadFullInt); + } + return NB.decodeInt64(buffer, 0); + } + + long[] readLongArray(int longsCount) throws IOException { + if (longsCount == 0) { + return new long[0]; + } + + long[] dest = new long[longsCount]; + for (int i = 0; i < longsCount; i++) { + dest[i] = readLong(); + } + return dest; + } + + byte readByte() throws IOException { + int n = in.readNBytes(buffer, 0, 1); + if (n != 1) { + throw new IOException(JGitText.get().cannotReadByte); + } + return buffer[0]; + } + + byte[] readNBytes(int sz) throws IOException { + return in.readNBytes(sz); + } + } + + private static class EmptyPackObjectSizeIndex + implements PackObjectSizeIndex { + + private final int threshold; + + EmptyPackObjectSizeIndex(int threshold) { + this.threshold = threshold; + } + + @Override + public long getSize(int idxOffset) { + return -1; + } + + @Override + public long getObjectCount() { + return 0; + } + + @Override + public int getThreshold() { + return threshold; + } + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackObjectSizeIndexWriter.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackObjectSizeIndexWriter.java new file mode 100644 index 0000000000..65a065dd55 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackObjectSizeIndexWriter.java @@ -0,0 +1,286 @@ +/* + * Copyright (C) 2022, Google LLC and others + * + * 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.file; + +import java.io.BufferedOutputStream; +import java.io.IOException; +import java.io.OutputStream; +import java.util.List; + +import org.eclipse.jgit.internal.JGitText; +import org.eclipse.jgit.lib.Constants; +import org.eclipse.jgit.transport.PackedObjectInfo; +import org.eclipse.jgit.util.NB; + +/** + * Write an object index in the output stream + */ +public abstract class PackObjectSizeIndexWriter { + + private static final int MAX_24BITS_UINT = 0xffffff; + + private static final PackObjectSizeIndexWriter NULL_WRITER = new PackObjectSizeIndexWriter() { + @Override + public void write(List<? extends PackedObjectInfo> objs) { + // Do nothing + } + }; + + /** Magic constant for the object size index file */ + protected static final byte[] HEADER = { -1, 's', 'i', 'z' }; + + /** + * Returns a writer for the latest index version + * + * @param os + * Output stream where to write the index + * @param minSize + * objects strictly smaller than this size won't be added to the + * index. Negative size won't write AT ALL. Other sizes could write + * an empty index. + * @return the index writer + */ + public static PackObjectSizeIndexWriter createWriter(OutputStream os, + int minSize) { + if (minSize < 0) { + return NULL_WRITER; + } + return new PackObjectSizeWriterV1(os, minSize); + } + + /** + * Add the objects to the index + * + * @param objs + * objects in the pack, in sha1 order. Their position in the list + * matches their position in the primary index. + * @throws IOException + * problem writing to the stream + */ + public abstract void write(List<? extends PackedObjectInfo> objs) + throws IOException; + + /** + * Object size index v1. + * + * Store position (in the main index) to size as parallel arrays. + * + * <p>Positions in the main index fit well in unsigned 24 bits (16M) for most + * repositories, but some outliers have even more objects, so we need to + * store also 32 bits positions. + * + * <p>Sizes are stored as a first array parallel to positions. If a size + * doesn't fit in an element of that array, then we encode there a position + * on the next-size array. This "overflow" array doesn't have entries for + * all positions. + * + * <pre> + * + * positions [10, 500, 1000, 1001] + * sizes (32bits) [15MB, -1, 6MB, -2] + * ___/ ______/ + * / / + * sizes (64 bits) [3GB, 6GB] + * </pre> + * + * <p>For sizes we use 32 bits as the first level and 64 for the rare objects + * over 2GB. + * + * <p>A 24/32/64 bits hierarchy of arrays saves space if we have a lot of small + * objects, but wastes space if we have only big ones. The min size to index is + * controlled by conf and in principle we want to index only rather + * big objects (e.g. > 10MB). We could support more dynamics read/write of sizes + * (e.g. 24 only if the threshold will include many of those objects) but it + * complicates a lot code and spec. If needed it could go for a v2 of the protocol. + * + * <p>Format: + * + * <li>A header with the magic number (4 bytes) + * <li>The index version (1 byte) + * <li>The minimum object size (4 bytes) + * <li>Total count of objects indexed (C, 4 bytes) + * (if count == 0, stop here) + * + * Blocks of + * <li>Size per entry in bits (1 byte, either 24 (0x18) or 32 (0x20)) + * <li>Count of entries (4 bytes) (c, as a signed int) + * <li>positions encoded in s bytes each (i.e s*c bytes) + * + * <li>0 (as a "size-per-entry = 0", marking end of the section) + * + * <li>32 bit sizes (C * 4 bytes). Negative size means + * nextLevel[abs(size)-1] + * <li>Count of 64 bit sizes (s64) (or 0 if no more indirections) + * <li>64 bit sizes (s64 * 8 bytes) + * <li>0 (end) + */ + static class PackObjectSizeWriterV1 extends PackObjectSizeIndexWriter { + + private final OutputStream os; + + private final int minObjSize; + + private final byte[] intBuffer = new byte[4]; + + PackObjectSizeWriterV1(OutputStream os, int minSize) { + this.os = new BufferedOutputStream(os); + this.minObjSize = minSize; + } + + @Override + public void write(List<? extends PackedObjectInfo> allObjects) + throws IOException { + os.write(HEADER); + writeUInt8(1); // Version + writeInt32(minObjSize); + + PackedObjectStats stats = countIndexableObjects(allObjects); + int[] indexablePositions = findIndexablePositions(allObjects, + stats.indexableObjs); + writeInt32(indexablePositions.length); // Total # of objects + if (indexablePositions.length == 0) { + os.flush(); + return; + } + + // Positions that fit in 3 bytes + if (stats.pos24Bits > 0) { + writeUInt8(24); + writeInt32(stats.pos24Bits); + applyToRange(indexablePositions, 0, stats.pos24Bits, + this::writeInt24); + } + // Positions that fit in 4 bytes + // We only use 31 bits due to sign, + // but that covers 2 billion objs + if (stats.pos31Bits > 0) { + writeUInt8(32); + writeInt32(stats.pos31Bits); + applyToRange(indexablePositions, stats.pos24Bits, + stats.pos24Bits + stats.pos31Bits, this::writeInt32); + } + writeUInt8(0); + writeSizes(allObjects, indexablePositions, stats.sizeOver2GB); + os.flush(); + } + + private void writeUInt8(int i) throws IOException { + if (i > 255) { + throw new IllegalStateException( + JGitText.get().numberDoesntFit); + } + NB.encodeInt32(intBuffer, 0, i); + os.write(intBuffer, 3, 1); + } + + private void writeInt24(int i) throws IOException { + NB.encodeInt24(intBuffer, 1, i); + os.write(intBuffer, 1, 3); + } + + private void writeInt32(int i) throws IOException { + NB.encodeInt32(intBuffer, 0, i); + os.write(intBuffer); + } + + private void writeSizes(List<? extends PackedObjectInfo> allObjects, + int[] indexablePositions, int objsBiggerThan2Gb) + throws IOException { + if (indexablePositions.length == 0) { + writeInt32(0); + return; + } + + byte[] sizes64bits = new byte[8 * objsBiggerThan2Gb]; + int s64 = 0; + for (int i = 0; i < indexablePositions.length; i++) { + PackedObjectInfo info = allObjects.get(indexablePositions[i]); + if (info.getFullSize() < Integer.MAX_VALUE) { + writeInt32((int) info.getFullSize()); + } else { + // Size needs more than 32 bits. Store -1 * offset in the + // next table as size. + writeInt32(-1 * (s64 + 1)); + NB.encodeInt64(sizes64bits, s64 * 8, info.getFullSize()); + s64++; + } + } + if (objsBiggerThan2Gb > 0) { + writeInt32(objsBiggerThan2Gb); + os.write(sizes64bits); + } + writeInt32(0); + } + + private int[] findIndexablePositions( + List<? extends PackedObjectInfo> allObjects, + int indexableObjs) { + int[] positions = new int[indexableObjs]; + int positionIdx = 0; + for (int i = 0; i < allObjects.size(); i++) { + PackedObjectInfo o = allObjects.get(i); + if (!shouldIndex(o)) { + continue; + } + positions[positionIdx++] = i; + } + return positions; + } + + private PackedObjectStats countIndexableObjects( + List<? extends PackedObjectInfo> objs) { + PackedObjectStats stats = new PackedObjectStats(); + for (int i = 0; i < objs.size(); i++) { + PackedObjectInfo o = objs.get(i); + if (!shouldIndex(o)) { + continue; + } + stats.indexableObjs++; + if (o.getFullSize() > Integer.MAX_VALUE) { + stats.sizeOver2GB++; + } + if (i <= MAX_24BITS_UINT) { + stats.pos24Bits++; + } else { + stats.pos31Bits++; + // i is a positive int, cannot be bigger than this + } + } + return stats; + } + + private boolean shouldIndex(PackedObjectInfo o) { + return (o.getType() == Constants.OBJ_BLOB) + && (o.getFullSize() >= minObjSize); + } + + private static class PackedObjectStats { + int indexableObjs; + + int pos24Bits; + + int pos31Bits; + + int sizeOver2GB; + } + + @FunctionalInterface + interface IntEncoder { + void encode(int i) throws IOException; + } + + private static void applyToRange(int[] allPositions, int start, int end, + IntEncoder encoder) throws IOException { + for (int i = start; i < end; i++) { + encoder.encode(allPositions[i]); + } + } + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackReverseIndex.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackReverseIndex.java index ee458e27ba..1a5adb4a16 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackReverseIndex.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackReverseIndex.java @@ -158,7 +158,7 @@ public class PackReverseIndex { return index.getOffset(nth[ith + 1]); } - int findPostion(long offset) { + int findPosition(long offset) { return binarySearch(offset); } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/RefDirectory.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/RefDirectory.java index d72f935555..e9abb02379 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/RefDirectory.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/RefDirectory.java @@ -112,11 +112,6 @@ public class RefDirectory extends RefDatabase { /** If in the header, denotes the file has peeled data. */ public static final String PACKED_REFS_PEELED = " peeled"; //$NON-NLS-1$ - /** The names of the additional refs supported by this class */ - private static final String[] additionalRefsNames = new String[] { - Constants.MERGE_HEAD, Constants.FETCH_HEAD, Constants.ORIG_HEAD, - Constants.CHERRY_PICK_HEAD }; - @SuppressWarnings("boxing") private static final List<Integer> RETRY_SLEEP_MS = Collections.unmodifiableList(Arrays.asList(0, 100, 200, 400, 800, 1600)); diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/UInt24Array.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/UInt24Array.java new file mode 100644 index 0000000000..3a0a18bdb3 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/UInt24Array.java @@ -0,0 +1,93 @@ +/* + * Copyright (C) 2023, 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.file; + +/** + * A view of a byte[] as a list of integers stored in 3 bytes. + * + * The ints are stored in big-endian ("network order"), so + * byte[]{aa,bb,cc} becomes the int 0x00aabbcc + */ +final class UInt24Array { + + public static final UInt24Array EMPTY = new UInt24Array( + new byte[0]); + + private static final int ENTRY_SZ = 3; + + private final byte[] data; + + private final int size; + + UInt24Array(byte[] data) { + this.data = data; + this.size = data.length / ENTRY_SZ; + } + + boolean isEmpty() { + return size == 0; + } + + int size() { + return size; + } + + int get(int index) { + if (index < 0 || index >= size) { + throw new IndexOutOfBoundsException(index); + } + int offset = index * ENTRY_SZ; + int e = data[offset] & 0xff; + e <<= 8; + e |= data[offset + 1] & 0xff; + e <<= 8; + e |= data[offset + 2] & 0xff; + return e; + } + + /** + * Search needle in the array. + * + * This assumes a sorted array. + * + * @param needle + * It cannot be bigger than 0xffffff (max unsigned three bytes). + * @return position of the needle in the array, -1 if not found. Runtime + * exception if the value is too big for 3 bytes. + */ + int binarySearch(int needle) { + if ((needle & 0xff000000) != 0) { + throw new IllegalArgumentException("Too big value for 3 bytes"); //$NON-NLS-1$ + } + if (size == 0) { + return -1; + } + int high = size; + if (high == 0) + return -1; + int low = 0; + do { + int mid = (low + high) >>> 1; + int cmp; + cmp = Integer.compare(needle, get(mid)); + if (cmp < 0) + high = mid; + else if (cmp == 0) { + return mid; + } else + low = mid + 1; + } while (low < high); + return -1; + } + + int getLastValue() { + return get(size - 1); + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/WindowCursor.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/WindowCursor.java index e7fd7b9e76..fa743babe7 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/WindowCursor.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/WindowCursor.java @@ -16,6 +16,7 @@ import java.util.Collection; import java.util.Collections; import java.util.HashSet; import java.util.List; +import java.util.Optional; import java.util.Set; import java.util.zip.DataFormatException; import java.util.zip.Inflater; @@ -34,6 +35,7 @@ import org.eclipse.jgit.lib.AbbreviatedObjectId; import org.eclipse.jgit.lib.AnyObjectId; import org.eclipse.jgit.lib.BitmapIndex; import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder; +import org.eclipse.jgit.internal.storage.commitgraph.CommitGraph; import org.eclipse.jgit.lib.Constants; import org.eclipse.jgit.lib.InflaterCache; import org.eclipse.jgit.lib.ObjectId; @@ -96,6 +98,12 @@ final class WindowCursor extends ObjectReader implements ObjectReuseAsIs { /** {@inheritDoc} */ @Override + public Optional<CommitGraph> getCommitGraph() { + return db.getCommitGraph(); + } + + /** {@inheritDoc} */ + @Override public Collection<CachedPack> getCachedPacksAndUpdate( BitmapBuilder needBitmap) throws IOException { for (Pack pack : db.getPacks()) { diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/memory/TernarySearchTree.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/memory/TernarySearchTree.java new file mode 100644 index 0000000000..1ac6627360 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/memory/TernarySearchTree.java @@ -0,0 +1,597 @@ +/* + * Copyright (C) 2021, Matthias Sohn <matthias.sohn@sap.com> and others + * + * 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.memory; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.LinkedList; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; +import java.util.Queue; +import java.util.concurrent.atomic.AtomicInteger; +import java.util.concurrent.locks.ReadWriteLock; +import java.util.concurrent.locks.ReentrantReadWriteLock; + +import org.eclipse.jgit.annotations.Nullable; +import org.eclipse.jgit.internal.JGitText; +import org.eclipse.jgit.util.StringUtils; + +/** + * A ternary search tree with String keys and generic values. + * + * TernarySearchTree is a type of trie (sometimes called a prefix tree) where + * nodes are arranged in a manner similar to a binary search tree, but with up + * to three children rather than the binary tree's limit of two. Like other + * prefix trees, a ternary search tree can be used as an associative map + * structure with the ability for incremental string search. However, ternary + * search trees are more space efficient compared to standard prefix trees, at + * the cost of speed. + * + * Keys must not be null or empty. Values cannot be null. + * + * This class is thread safe. + * + * @param <Value> + * type of values in this tree + * @since 6.5 + */ +public final class TernarySearchTree<Value> { + + private static final char WILDCARD = '?'; + + private static class Node<Value> { + final char c; + + Node<Value> lo, eq, hi; + + Value val; + + Node(char c) { + this.c = c; + } + + boolean hasValue() { + return val != null; + } + } + + /** + * Loader to load key-value pairs to be cached in the tree + * + * @param <Value> + * type of values + */ + public static interface Loader<Value> { + /** + * Load map of all key value pairs + * + * @return map of all key value pairs to cache in the tree + */ + Map<String, Value> loadAll(); + } + + private static void validateKey(String key) { + if (StringUtils.isEmptyOrNull(key)) { + throw new IllegalArgumentException( + JGitText.get().illegalTernarySearchTreeKey); + } + } + + private static <V> void validateValue(V value) { + if (value == null) { + throw new IllegalArgumentException( + JGitText.get().illegalTernarySearchTreeValue); + } + } + + private final ReadWriteLock lock; + + private final AtomicInteger size = new AtomicInteger(0); + + private Node<Value> root; + + /** + * Construct a new ternary search tree + */ + public TernarySearchTree() { + lock = new ReentrantReadWriteLock(); + } + + /** + * Get the lock guarding read and write access to the cache. + * + * @return lock guarding read and write access to the cache + */ + public ReadWriteLock getLock() { + return lock; + } + + /** + * Replace the tree with a new tree containing all entries provided by an + * iterable + * + * @param loader + * iterable providing key-value pairs to load + * @return number of key-value pairs after replacing finished + */ + public int replace(Iterable<Entry<String, Value>> loader) { + lock.writeLock().lock(); + try { + clear(); + for (Entry<String, Value> e : loader) { + insertImpl(e.getKey(), e.getValue()); + } + } finally { + lock.writeLock().unlock(); + } + return size.get(); + } + + /** + * Reload the tree entries provided by loader + * + * @param loader + * iterable providing key-value pairs to load + * @return number of key-value pairs + */ + public int reload(Iterable<Entry<String, Value>> loader) { + lock.writeLock().lock(); + try { + for (Entry<String, Value> e : loader) { + insertImpl(e.getKey(), e.getValue()); + } + } finally { + lock.writeLock().unlock(); + } + return size.get(); + } + + /** + * Delete entries + * + * @param delete + * iterable providing keys of entries to be deleted + * @return number of key-value pairs + */ + public int delete(Iterable<String> delete) { + lock.writeLock().lock(); + try { + for (String s : delete) { + delete(s); + } + } finally { + lock.writeLock().unlock(); + } + return size.get(); + } + + /** + * Get the number of key value pairs in this trie + * + * @return number of key value pairs in this trie + */ + public int size() { + return size.get(); + } + + /** + * Get the value associated to a key or {@code null}. + * + * @param key + * the key + * @return the value associated to this key + */ + @Nullable + public Value get(String key) { + validateKey(key); + lock.readLock().lock(); + try { + Node<Value> node = get(root, key, 0); + if (node == null) { + return null; + } + return node.val; + } finally { + lock.readLock().unlock(); + } + } + + /** + * Check whether this tree contains the given key. + * + * @param key + * a key + * @return whether this tree contains this key + */ + public boolean contains(String key) { + return get(key) != null; + } + + /** + * Insert a key-value pair. If the key already exists the old value is + * overwritten. + * + * @param key + * the key + * @param value + * the value + * @return number of key-value pairs after adding the entry + */ + public int insert(String key, Value value) { + lock.writeLock().lock(); + try { + insertImpl(key, value); + return size.get(); + } finally { + lock.writeLock().unlock(); + } + } + + /** + * Insert map of key-value pairs. Values of existing keys are overwritten. + * Use this method to insert multiple key-value pairs. + * + * @param map + * map of key-value pairs to insert + * @return number of key-value pairs after adding entries + */ + public int insert(Map<String, Value> map) { + lock.writeLock().lock(); + try { + for (Entry<String, Value> e : map.entrySet()) { + insertImpl(e.getKey(), e.getValue()); + } + return size.get(); + } finally { + lock.writeLock().unlock(); + } + } + + private void insertImpl(String key, Value value) { + validateValue(value); + if (!contains(key)) { + size.addAndGet(1); + } + root = insert(root, key, value, 0); + } + + /** + * Delete a key-value pair. Does nothing if the key doesn't exist. + * + * @param key + * the key + * @return number of key-value pairs after the deletion + */ + public int delete(String key) { + lock.writeLock().lock(); + try { + if (contains(key)) { + size.addAndGet(-1); + root = insert(root, key, null, 0); + } + return size.get(); + } finally { + lock.writeLock().unlock(); + } + } + + /** + * Remove all key value pairs from this tree + */ + public void clear() { + lock.writeLock().lock(); + try { + size.set(0); + root = null; + } finally { + lock.writeLock().unlock(); + } + } + + /** + * Find the key which is the longest prefix of the given query string. + * + * @param query + * @return the key which is the longest prefix of the given query string or + * {@code null} if none exists. + */ + @Nullable + public String keyLongestPrefixOf(String query) { + if (StringUtils.isEmptyOrNull(query)) { + return null; + } + lock.readLock().lock(); + try { + int length = 0; + Node<Value> node = root; + int i = 0; + while (node != null && i < query.length()) { + char c = query.charAt(i); + if (node.c > c) { + node = node.lo; + } else if (node.c < c) { + node = node.hi; + } else { + i++; + if (node.hasValue()) { + length = i; + } + node = node.eq; + } + } + return query.substring(0, length); + } finally { + lock.readLock().unlock(); + } + } + + /** + * Get all keys. + * + * @return all keys + */ + public Iterable<String> getKeys() { + Queue<String> queue = new LinkedList<>(); + lock.readLock().lock(); + try { + findKeysWithPrefix(root, new StringBuilder(), queue); + return queue; + } finally { + lock.readLock().unlock(); + } + } + + /** + * Get keys starting with given prefix + * + * @param prefix + * key prefix + * @return keys starting with given prefix + */ + public Iterable<String> getKeysWithPrefix(String prefix) { + Queue<String> keys = new LinkedList<>(); + if (prefix == null) { + return keys; + } + if (prefix.isEmpty()) { + return getKeys(); + } + lock.readLock().lock(); + try { + validateKey(prefix); + Node<Value> node = get(root, prefix, 0); + if (node == null) { + return keys; + } + if (node.hasValue()) { + keys.add(prefix); + } + findKeysWithPrefix(node.eq, new StringBuilder(prefix), keys); + return keys; + } finally { + lock.readLock().unlock(); + } + } + + /** + * Get all entries. + * + * @return all entries + */ + public Map<String, Value> getAll() { + Map<String, Value> entries = new HashMap<>(); + lock.readLock().lock(); + try { + findWithPrefix(root, new StringBuilder(), entries); + return entries; + } finally { + lock.readLock().unlock(); + } + } + + /** + * Get all values. + * + * @return all values + */ + public List<Value> getAllValues() { + List<Value> values = new ArrayList<>(); + lock.readLock().lock(); + try { + findValuesWithPrefix(root, new StringBuilder(), values); + return values; + } finally { + lock.readLock().unlock(); + } + } + + /** + * Get all entries with given prefix + * + * @param prefix + * key prefix + * @return entries with given prefix + */ + public Map<String, Value> getWithPrefix(String prefix) { + Map<String, Value> entries = new HashMap<>(); + if (prefix == null) { + return entries; + } + if (prefix.isEmpty()) { + return getAll(); + } + lock.readLock().lock(); + try { + validateKey(prefix); + Node<Value> node = get(root, prefix, 0); + if (node == null) { + return entries; + } + if (node.hasValue()) { + entries.put(prefix, node.val); + } + findWithPrefix(node.eq, new StringBuilder(prefix), entries); + return entries; + } finally { + lock.readLock().unlock(); + } + } + + /** + * Get all values with given key prefix + * + * @param prefix + * key prefix + * @return entries with given prefix + */ + public List<Value> getValuesWithPrefix(String prefix) { + List<Value> values = new ArrayList<>(); + if (prefix == null) { + return values; + } + if (prefix.isEmpty()) { + return getAllValues(); + } + lock.readLock().lock(); + try { + validateKey(prefix); + Node<Value> node = get(root, prefix, 0); + if (node == null) { + return values; + } + if (node.hasValue()) { + values.add(node.val); + } + findValuesWithPrefix(node.eq, new StringBuilder(prefix), values); + return values; + } finally { + lock.readLock().unlock(); + } + } + + /** + * Get keys matching given pattern using '?' as wildcard character. + * + * @param pattern + * search pattern + * @return keys matching given pattern. + */ + public Iterable<String> getKeysMatching(String pattern) { + Queue<String> keys = new LinkedList<>(); + lock.readLock().lock(); + try { + findKeysWithPrefix(root, new StringBuilder(), 0, pattern, keys); + return keys; + } finally { + lock.readLock().unlock(); + } + } + + private Node<Value> get(Node<Value> node, String key, int depth) { + if (node == null) { + return null; + } + char c = key.charAt(depth); + if (node.c > c) { + return get(node.lo, key, depth); + } else if (node.c < c) { + return get(node.hi, key, depth); + } else if (depth < key.length() - 1) { + return get(node.eq, key, depth + 1); + } else { + return node; + } + } + + private Node<Value> insert(Node<Value> node, String key, Value val, + int depth) { + char c = key.charAt(depth); + if (node == null) { + node = new Node<>(c); + } + if (node.c > c) { + node.lo = insert(node.lo, key, val, depth); + } else if (node.c < c) { + node.hi = insert(node.hi, key, val, depth); + } else if (depth < key.length() - 1) { + node.eq = insert(node.eq, key, val, depth + 1); + } else { + node.val = val; + } + return node; + } + + private void findKeysWithPrefix(Node<Value> node, StringBuilder prefix, + Queue<String> keys) { + if (node == null) { + return; + } + findKeysWithPrefix(node.lo, prefix, keys); + if (node.hasValue()) { + keys.add(prefix.toString() + node.c); + } + findKeysWithPrefix(node.eq, prefix.append(node.c), keys); + prefix.deleteCharAt(prefix.length() - 1); + findKeysWithPrefix(node.hi, prefix, keys); + } + + private void findWithPrefix(Node<Value> node, StringBuilder prefix, + Map<String, Value> entries) { + if (node == null) { + return; + } + findWithPrefix(node.lo, prefix, entries); + if (node.hasValue()) { + entries.put(prefix.toString() + node.c, node.val); + } + findWithPrefix(node.eq, prefix.append(node.c), entries); + prefix.deleteCharAt(prefix.length() - 1); + findWithPrefix(node.hi, prefix, entries); + } + + private void findValuesWithPrefix(Node<Value> node, StringBuilder prefix, + List<Value> values) { + if (node == null) { + return; + } + findValuesWithPrefix(node.lo, prefix, values); + if (node.hasValue()) { + values.add(node.val); + } + findValuesWithPrefix(node.eq, prefix.append(node.c), values); + prefix.deleteCharAt(prefix.length() - 1); + findValuesWithPrefix(node.hi, prefix, values); + } + + private void findKeysWithPrefix(Node<Value> node, StringBuilder prefix, + int i, String pattern, Queue<String> keys) { + if (node == null || StringUtils.isEmptyOrNull(pattern)) { + return; + } + char c = pattern.charAt(i); + if (c == WILDCARD || node.c > c) { + findKeysWithPrefix(node.lo, prefix, i, pattern, keys); + } + if (c == WILDCARD || node.c == c) { + if (i == pattern.length() - 1 && node.hasValue()) { + keys.add(prefix.toString() + node.c); + } + if (i < pattern.length() - 1) { + findKeysWithPrefix(node.eq, prefix.append(node.c), i + 1, + pattern, keys); + prefix.deleteCharAt(prefix.length() - 1); + } + } + if (c == WILDCARD || node.c < c) { + findKeysWithPrefix(node.hi, prefix, i, pattern, keys); + } + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackExt.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackExt.java index c006995c5e..adad411c6f 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackExt.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackExt.java @@ -30,7 +30,13 @@ public enum PackExt { REFTABLE("ref"), //$NON-NLS-1$ /** A pack reverse index file extension. */ - REVERSE_INDEX("rev"); //$NON-NLS-1$ + REVERSE_INDEX("rev"), //$NON-NLS-1$ + + /** A commit graph file extension. */ + COMMIT_GRAPH("graph"), //$NON-NLS-1$ + + /** An object size index. */ + OBJECT_SIZE_INDEX("objsize"); //$NON-NLS-1$ private final String ext; diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriter.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriter.java index d43d8bba8b..60edc76997 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriter.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriter.java @@ -61,6 +61,7 @@ import org.eclipse.jgit.internal.JGitText; import org.eclipse.jgit.internal.storage.file.PackBitmapIndexBuilder; import org.eclipse.jgit.internal.storage.file.PackBitmapIndexWriterV1; import org.eclipse.jgit.internal.storage.file.PackIndexWriter; +import org.eclipse.jgit.internal.storage.file.PackObjectSizeIndexWriter; import org.eclipse.jgit.lib.AnyObjectId; import org.eclipse.jgit.lib.AsyncObjectSizeQueue; import org.eclipse.jgit.lib.BatchingProgressMonitor; @@ -1114,6 +1115,50 @@ public class PackWriter implements AutoCloseable { } /** + * Create an object size index file for the contents of the pack file just + * written. + * <p> + * Called after + * {@link #writePack(ProgressMonitor, ProgressMonitor, OutputStream)} that + * populates the list of objects to pack and before + * {@link #writeBitmapIndex(OutputStream)} that destroys it. + * <p> + * Writing this index is only required for local pack storage. Packs sent on + * the network do not need to create an object size index. + * + * @param objIdxStream + * output for the object size index data. Caller is responsible + * for closing this stream. + * @throws IOException + * errors while writing + */ + public void writeObjectSizeIndex(OutputStream objIdxStream) + throws IOException { + if (config.getMinBytesForObjSizeIndex() < 0) { + return; + } + + long writeStart = System.currentTimeMillis(); + // We only need to populate the size of blobs + AsyncObjectSizeQueue<ObjectToPack> sizeQueue = reader + .getObjectSize(objectsLists[OBJ_BLOB], /* reportMissing= */false); + try { + while (sizeQueue.next()) { + ObjectToPack otp = sizeQueue.getCurrent(); + long sz = sizeQueue.getSize(); + otp.setFullSize(sz); + } + } finally { + sizeQueue.release(); + } + PackObjectSizeIndexWriter iw = PackObjectSizeIndexWriter.createWriter( + objIdxStream, config.getMinBytesForObjSizeIndex()); + // All indexed objects because their positions must match primary index order + iw.write(sortByName()); + stats.timeWriting += System.currentTimeMillis() - writeStart; + } + + /** * Create a bitmap index file to match the pack file just written. * <p> * Called after {@link #prepareBitmapIndex(ProgressMonitor)}. @@ -2393,10 +2438,14 @@ public class PackWriter implements AutoCloseable { int numCommits = objectsLists[OBJ_COMMIT].size(); List<ObjectToPack> byName = sortByName(); + // Reset sortedByName before the array that it points to is mutated by + // PackBitmapIndexBuilder, to prevent other methods referencing the + // mutated array afterwards. sortedByName = null; objectsLists = null; objectsMap = null; writeBitmaps = new PackBitmapIndexBuilder(byName); + // Allow byName to be GC'd if JVM GC runs before the end of the method. byName = null; PackWriterBitmapPreparer bitmapPreparer = new PackWriterBitmapPreparer( diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/BatchRefUpdate.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/BatchRefUpdate.java index ef1379a238..e2bebfefdb 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/BatchRefUpdate.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/BatchRefUpdate.java @@ -498,17 +498,14 @@ public class BatchRefUpdate { try { if (cmd.getResult() == NOT_ATTEMPTED) { cmd.updateType(walk); - RefUpdate ru = newUpdate(cmd); switch (cmd.getType()) { case DELETE: // Performed in the first phase break; case UPDATE: case UPDATE_NONFASTFORWARD: - RefUpdate ruu = newUpdate(cmd); - cmd.setResult(ruu.update(walk)); - break; case CREATE: + RefUpdate ru = newUpdate(cmd); cmd.setResult(ru.update(walk)); break; } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/BatchingProgressMonitor.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/BatchingProgressMonitor.java index 49e295aed8..f826057370 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/BatchingProgressMonitor.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/BatchingProgressMonitor.java @@ -10,21 +10,29 @@ package org.eclipse.jgit.lib; +import java.time.Duration; +import java.time.Instant; import java.util.concurrent.Future; import java.util.concurrent.TimeUnit; import org.eclipse.jgit.lib.internal.WorkQueue; +import org.eclipse.jgit.util.SystemReader; /** * ProgressMonitor that batches update events. */ public abstract class BatchingProgressMonitor implements ProgressMonitor { + private static boolean performanceTrace = SystemReader.getInstance() + .isPerformanceTraceEnabled(); + private long delayStartTime; private TimeUnit delayStartUnit = TimeUnit.MILLISECONDS; private Task task; + private Boolean showDuration; + /** * Set an optional delay before the first output. * @@ -76,6 +84,11 @@ public abstract class BatchingProgressMonitor implements ProgressMonitor { return false; } + @Override + public void showDuration(boolean enabled) { + showDuration = Boolean.valueOf(enabled); + } + /** * Update the progress monitor if the total work isn't known, * @@ -83,8 +96,12 @@ public abstract class BatchingProgressMonitor implements ProgressMonitor { * name of the task. * @param workCurr * number of units already completed. + * @param duration + * how long this task runs + * @since 6.5 */ - protected abstract void onUpdate(String taskName, int workCurr); + protected abstract void onUpdate(String taskName, int workCurr, + Duration duration); /** * Finish the progress monitor when the total wasn't known in advance. @@ -93,8 +110,12 @@ public abstract class BatchingProgressMonitor implements ProgressMonitor { * name of the task. * @param workCurr * total number of units processed. + * @param duration + * how long this task runs + * @since 6.5 */ - protected abstract void onEndTask(String taskName, int workCurr); + protected abstract void onEndTask(String taskName, int workCurr, + Duration duration); /** * Update the progress monitor when the total is known in advance. @@ -107,9 +128,12 @@ public abstract class BatchingProgressMonitor implements ProgressMonitor { * estimated number of units to process. * @param percentDone * {@code workCurr * 100 / workTotal}. + * @param duration + * how long this task runs + * @since 6.5 */ protected abstract void onUpdate(String taskName, int workCurr, - int workTotal, int percentDone); + int workTotal, int percentDone, Duration duration); /** * Finish the progress monitor when the total is known in advance. @@ -122,9 +146,58 @@ public abstract class BatchingProgressMonitor implements ProgressMonitor { * estimated number of units to process. * @param percentDone * {@code workCurr * 100 / workTotal}. + * @param duration + * duration of the task + * @since 6.5 */ protected abstract void onEndTask(String taskName, int workCurr, - int workTotal, int percentDone); + int workTotal, int percentDone, Duration duration); + + private boolean showDuration() { + return showDuration != null ? showDuration.booleanValue() + : performanceTrace; + } + + /** + * Append formatted duration if system property or environment variable + * GIT_TRACE_PERFORMANCE is set to "true". If both are defined the system + * property takes precedence. + * + * @param s + * StringBuilder to append the formatted duration to + * @param duration + * duration to format + * @since 6.5 + */ + @SuppressWarnings({ "boxing", "nls" }) + protected void appendDuration(StringBuilder s, Duration duration) { + if (!showDuration()) { + return; + } + long hours = duration.toHours(); + int minutes = duration.toMinutesPart(); + int seconds = duration.toSecondsPart(); + s.append(" ["); + if (hours > 0) { + s.append(hours).append(':'); + s.append(String.format("%02d", minutes)).append(':'); + s.append(String.format("%02d", seconds)); + } else if (minutes > 0) { + s.append(minutes).append(':'); + s.append(String.format("%02d", seconds)); + } else { + s.append(seconds); + } + s.append('.').append(String.format("%03d", duration.toMillisPart())); + if (hours > 0) { + s.append('h'); + } else if (minutes > 0) { + s.append('m'); + } else { + s.append('s'); + } + s.append(']'); + } private static class Task implements Runnable { /** Title of the current task. */ @@ -148,10 +221,13 @@ public abstract class BatchingProgressMonitor implements ProgressMonitor { /** Percentage of {@link #totalWork} that is done. */ private int lastPercent; + private final Instant startTime; + Task(String taskName, int totalWork) { this.taskName = taskName; this.totalWork = totalWork; this.display = true; + this.startTime = Instant.now(); } void delay(long time, TimeUnit unit) { @@ -170,7 +246,7 @@ public abstract class BatchingProgressMonitor implements ProgressMonitor { if (totalWork == UNKNOWN) { // Only display once per second, as the alarm fires. if (display) { - pm.onUpdate(taskName, lastWork); + pm.onUpdate(taskName, lastWork, elapsedTime()); output = true; restartTimer(); } @@ -178,12 +254,14 @@ public abstract class BatchingProgressMonitor implements ProgressMonitor { // Display once per second or when 1% is done. int currPercent = Math.round(lastWork * 100F / totalWork); if (display) { - pm.onUpdate(taskName, lastWork, totalWork, currPercent); + pm.onUpdate(taskName, lastWork, totalWork, currPercent, + elapsedTime()); output = true; restartTimer(); lastPercent = currPercent; } else if (currPercent != lastPercent) { - pm.onUpdate(taskName, lastWork, totalWork, currPercent); + pm.onUpdate(taskName, lastWork, totalWork, currPercent, + elapsedTime()); output = true; lastPercent = currPercent; } @@ -199,14 +277,18 @@ public abstract class BatchingProgressMonitor implements ProgressMonitor { void end(BatchingProgressMonitor pm) { if (output) { if (totalWork == UNKNOWN) { - pm.onEndTask(taskName, lastWork); + pm.onEndTask(taskName, lastWork, elapsedTime()); } else { int currPercent = Math.round(lastWork * 100F / totalWork); - pm.onEndTask(taskName, lastWork, totalWork, currPercent); + pm.onEndTask(taskName, lastWork, totalWork, currPercent, elapsedTime()); } } if (timerFuture != null) timerFuture.cancel(false /* no interrupt */); } + + private Duration elapsedTime() { + return Duration.between(startTime, Instant.now()); + } } } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/BranchConfig.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/BranchConfig.java index aa613d07eb..e15c7af932 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/BranchConfig.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/BranchConfig.java @@ -30,8 +30,17 @@ public class BranchConfig { /** Value for rebasing */ REBASE("true"), //$NON-NLS-1$ - /** Value for rebasing preserving local merge commits */ - PRESERVE("preserve"), //$NON-NLS-1$ + /** + * Value for rebasing preserving local merge commits + * + * @since 6.5 used instead of deprecated "preserve" option + */ + MERGES("merges"){ //$NON-NLS-1$ + @Override + public boolean matchConfigValue(String s) { + return super.matchConfigValue(s) || "preserve".equals(s); //$NON-NLS-1$ + } + }, /** Value for rebasing interactively */ INTERACTIVE("interactive"), //$NON-NLS-1$ /** Value for not rebasing at all but merging */ diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigConstants.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigConstants.java index 2b49f956ff..7d6f40a51b 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigConstants.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ConfigConstants.java @@ -835,6 +835,13 @@ public final class ConfigConstants { public static final String CONFIG_KEY_WINDOW_MEMORY = "windowmemory"; /** + * the "pack.minBytesForObjSizeIndex" key + * + * @since 6.5 + */ + public static final String CONFIG_KEY_MIN_BYTES_OBJ_SIZE_INDEX = "minBytesForObjSizeIndex"; + + /** * The "repack.packKeptObjects" key * * @since 5.13.3 @@ -912,6 +919,20 @@ public final class ConfigConstants { public static final String CONFIG_KEY_ABBREV = "abbrev"; /** + * The "writeCommitGraph" key + * + * @since 6.5 + */ + public static final String CONFIG_KEY_WRITE_COMMIT_GRAPH = "writeCommitGraph"; + + /** + * The "commitGraph" used by commit-graph feature + * + * @since 6.5 + */ + public static final String CONFIG_COMMIT_GRAPH = "commitGraph"; + + /** * The "trustPackedRefsStat" key * * @since 6.1.1 diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/Constants.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/Constants.java index 30a0074195..0b8bf8c6c5 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/Constants.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/Constants.java @@ -284,6 +284,12 @@ public final class Constants { */ public static final String INFO_HTTP_ALTERNATES = "info/http-alternates"; + /** + * info commit-graph file (goes under OBJECTS) + * @since 6.5 + */ + public static final String INFO_COMMIT_GRAPH = "info/commit-graph"; + /** Packed refs file */ public static final String PACKED_REFS = "packed-refs"; @@ -754,6 +760,23 @@ public final class Constants { */ public static final int INFINITE_DEPTH = 0x7fffffff; + /** + * We use ({@value}) as generation number for commits not in the + * commit-graph file. + * + * @since 6.5 + */ + public static int COMMIT_GENERATION_UNKNOWN = Integer.MAX_VALUE; + + /** + * If a commit-graph file was written by a version of Git that did not + * compute generation numbers, then those commits will have generation + * number represented by ({@value}). + * + * @since 6.5 + */ + public static int COMMIT_GENERATION_NOT_COMPUTED = 0; + private Constants() { // Hide the default constructor } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/CoreConfig.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/CoreConfig.java index fc82a5fead..4de1801d04 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/CoreConfig.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/CoreConfig.java @@ -117,6 +117,13 @@ public class CoreConfig { } /** + * Default value of commit graph enable option: {@value} + * + * @since 6.5 + */ + public static final boolean DEFAULT_COMMIT_GRAPH_ENABLE = false; + + /** * Permissible values for {@code core.trustPackedRefsStat}. * * @since 6.1.1 @@ -147,6 +154,8 @@ public class CoreConfig { private final String attributesfile; + private final boolean commitGraph; + /** * Options for symlink handling * @@ -188,6 +197,9 @@ public class CoreConfig { ConfigConstants.CONFIG_KEY_EXCLUDESFILE); attributesfile = rc.getString(ConfigConstants.CONFIG_CORE_SECTION, null, ConfigConstants.CONFIG_KEY_ATTRIBUTESFILE); + commitGraph = rc.getBoolean(ConfigConstants.CONFIG_CORE_SECTION, + ConfigConstants.CONFIG_COMMIT_GRAPH, + DEFAULT_COMMIT_GRAPH_ENABLE); } /** @@ -240,4 +252,16 @@ public class CoreConfig { public String getAttributesFile() { return attributesfile; } + + /** + * Whether to read the commit-graph file (if it exists) to parse the graph + * structure of commits. Default to + * {@value org.eclipse.jgit.lib.CoreConfig#DEFAULT_COMMIT_GRAPH_ENABLE}. + * + * @return whether to read the commit-graph file + * @since 6.5 + */ + public boolean enableCommitGraph() { + return commitGraph; + } } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/EmptyProgressMonitor.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/EmptyProgressMonitor.java index 6b201e6bcf..94d28eb345 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/EmptyProgressMonitor.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/EmptyProgressMonitor.java @@ -48,4 +48,8 @@ public abstract class EmptyProgressMonitor implements ProgressMonitor { return false; } + @Override + public void showDuration(boolean enabled) { + // not implemented + } } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/NullProgressMonitor.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/NullProgressMonitor.java index 10904b6955..127cca9d1b 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/NullProgressMonitor.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/NullProgressMonitor.java @@ -52,4 +52,9 @@ public class NullProgressMonitor implements ProgressMonitor { public void endTask() { // Do not report. } + + @Override + public void showDuration(boolean enabled) { + // don't show + } } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectReader.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectReader.java index 081f40e9db..69b2b5104e 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectReader.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectReader.java @@ -17,6 +17,7 @@ import java.util.ArrayList; import java.util.Collection; import java.util.Iterator; import java.util.List; +import java.util.Optional; import java.util.Set; import org.eclipse.jgit.annotations.NonNull; @@ -27,6 +28,7 @@ import org.eclipse.jgit.internal.revwalk.BitmappedObjectReachabilityChecker; import org.eclipse.jgit.internal.revwalk.BitmappedReachabilityChecker; import org.eclipse.jgit.internal.revwalk.PedestrianObjectReachabilityChecker; import org.eclipse.jgit.internal.revwalk.PedestrianReachabilityChecker; +import org.eclipse.jgit.internal.storage.commitgraph.CommitGraph; import org.eclipse.jgit.revwalk.ObjectReachabilityChecker; import org.eclipse.jgit.revwalk.ObjectWalk; import org.eclipse.jgit.revwalk.ReachabilityChecker; @@ -500,6 +502,26 @@ public abstract class ObjectReader implements AutoCloseable { } /** + * Get the commit-graph for this repository if available. + * <p> + * The commit graph can be created/modified/deleted while the repository is + * open and specific implementations decide when to refresh it. + * + * @return the commit-graph or empty if the commit-graph does not exist or + * is invalid; always returns empty when core.commitGraph is false + * (default is + * {@value org.eclipse.jgit.lib.CoreConfig#DEFAULT_COMMIT_GRAPH_ENABLE}). + * + * @throws IOException + * if it cannot open any of the underlying commit graph. + * + * @since 6.5 + */ + public Optional<CommitGraph> getCommitGraph() throws IOException { + return Optional.empty(); + } + + /** * Get the {@link org.eclipse.jgit.lib.ObjectInserter} from which this * reader was created using {@code inserter.newReader()} * @@ -642,6 +664,11 @@ public abstract class ObjectReader implements AutoCloseable { } @Override + public Optional<CommitGraph> getCommitGraph() throws IOException{ + return delegate().getCommitGraph(); + } + + @Override @Nullable public ObjectInserter getCreatedFromInserter() { return delegate().getCreatedFromInserter(); diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ProgressMonitor.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ProgressMonitor.java index 9ebb0a46b9..2ce73ace86 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ProgressMonitor.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ProgressMonitor.java @@ -65,4 +65,13 @@ public interface ProgressMonitor { * @return true if the user asked the process to stop working. */ boolean isCancelled(); + + /** + * Set whether the monitor should show elapsed time per task + * + * @param enabled + * whether to show elapsed time per task + * @since 6.5 + */ + void showDuration(boolean enabled); } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefDatabase.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefDatabase.java index 7b7bdebac8..98089fb8fd 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefDatabase.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefDatabase.java @@ -40,10 +40,10 @@ public abstract class RefDatabase { /** * Order of prefixes to search when using non-absolute references. * <p> - * {@link #findRef(String)} takes this search space into consideration - * when locating a reference by name. The first entry in the path is - * always {@code ""}, ensuring that absolute references are resolved - * without further mangling. + * {@link #findRef(String)} takes this search space into consideration when + * locating a reference by name. The first entry in the path is always + * {@code ""}, ensuring that absolute references are resolved without + * further mangling. */ protected static final String[] SEARCH_PATH = { "", //$NON-NLS-1$ Constants.R_REFS, // @@ -69,6 +69,15 @@ public abstract class RefDatabase { public static final String ALL = "";//$NON-NLS-1$ /** + * The names of additional refs + * + * @since 6.5 + */ + protected static final String[] additionalRefsNames = new String[] { + Constants.MERGE_HEAD, Constants.FETCH_HEAD, Constants.ORIG_HEAD, + Constants.CHERRY_PICK_HEAD, Constants.REVERT_HEAD }; + + /** * Initialize a new reference database at this location. * * @throws java.io.IOException @@ -341,12 +350,12 @@ public abstract class RefDatabase { /** * Returns all refs. * <p> - * This includes {@code HEAD}, branches under {@code ref/heads/}, tags - * under {@code refs/tags/}, etc. It does not include pseudo-refs like + * This includes {@code HEAD}, branches under {@code ref/heads/}, tags under + * {@code refs/tags/}, etc. It does not include pseudo-refs like * {@code FETCH_HEAD}; for those, see {@link #getAdditionalRefs}. * <p> - * Symbolic references to a non-existent ref (for example, - * {@code HEAD} pointing to a branch yet to be born) are not included. + * Symbolic references to a non-existent ref (for example, {@code HEAD} + * pointing to a branch yet to be born) are not included. * <p> * Callers interested in only a portion of the ref hierarchy can call * {@link #getRefsByPrefix} instead. @@ -386,8 +395,9 @@ public abstract class RefDatabase { * {@link RefDatabase} should override this method directly if a better * implementation is possible. * - * @param prefix string that names of refs should start with; may be - * empty (to return all refs). + * @param prefix + * string that names of refs should start with; may be empty (to + * return all refs). * @return immutable list of refs whose names start with {@code prefix}. * @throws java.io.IOException * the reference space cannot be accessed. @@ -417,18 +427,22 @@ public abstract class RefDatabase { } /** - * Returns refs whose names start with a given prefix excluding all refs that - * start with one of the given prefixes. + * Returns refs whose names start with a given prefix excluding all refs + * that start with one of the given prefixes. * * <p> - * The default implementation is not efficient. Implementors of {@link RefDatabase} - * should override this method directly if a better implementation is possible. - * - * @param include string that names of refs should start with; may be empty. - * @param excludes strings that names of refs can't start with; may be empty. - * @return immutable list of refs whose names start with {@code prefix} and none - * of the strings in {@code exclude}. - * @throws java.io.IOException the reference space cannot be accessed. + * The default implementation is not efficient. Implementors of + * {@link RefDatabase} should override this method directly if a better + * implementation is possible. + * + * @param include + * string that names of refs should start with; may be empty. + * @param excludes + * strings that names of refs can't start with; may be empty. + * @return immutable list of refs whose names start with {@code prefix} and + * none of the strings in {@code exclude}. + * @throws java.io.IOException + * the reference space cannot be accessed. * @since 5.11 */ @NonNull @@ -492,13 +506,14 @@ public abstract class RefDatabase { } /** - * If the ref database does not support fast inverse queries, it may - * be advantageous to build a complete SHA1 to ref map in advance for - * multiple uses. To let applications decide on this decision, - * this function indicates whether the inverse map is available. + * If the ref database does not support fast inverse queries, it may be + * advantageous to build a complete SHA1 to ref map in advance for multiple + * uses. To let applications decide on this decision, this function + * indicates whether the inverse map is available. * * @return whether this RefDatabase supports fast inverse ref queries. - * @throws IOException on I/O problems. + * @throws IOException + * on I/O problems. * @since 5.6 */ public boolean hasFastTipsWithSha1() throws IOException { @@ -509,10 +524,10 @@ public abstract class RefDatabase { * Check if any refs exist in the ref database. * <p> * This uses the same definition of refs as {@link #getRefs()}. In - * particular, returns {@code false} in a new repository with no refs - * under {@code refs/} and {@code HEAD} pointing to a branch yet to be - * born, and returns {@code true} in a repository with no refs under - * {@code refs/} and a detached {@code HEAD} pointing to history. + * particular, returns {@code false} in a new repository with no refs under + * {@code refs/} and {@code HEAD} pointing to a branch yet to be born, and + * returns {@code true} in a repository with no refs under {@code refs/} and + * a detached {@code HEAD} pointing to history. * * @return true if the database has refs. * @throws java.io.IOException diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefWriter.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefWriter.java index c80d80f607..d2c3f9de68 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefWriter.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefWriter.java @@ -138,8 +138,7 @@ public abstract class RefWriter { final StringWriter w = new StringWriter(); if (peeled) { w.write(RefDirectory.PACKED_REFS_HEADER); - if (peeled) - w.write(RefDirectory.PACKED_REFS_PEELED); + w.write(RefDirectory.PACKED_REFS_PEELED); w.write('\n'); } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/TextProgressMonitor.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/TextProgressMonitor.java index 03a78eb8ac..85aa0b6639 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/TextProgressMonitor.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/TextProgressMonitor.java @@ -17,6 +17,7 @@ import java.io.IOException; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.Writer; +import java.time.Duration; /** * A simple progress reporter printing on a stream. @@ -46,49 +47,53 @@ public class TextProgressMonitor extends BatchingProgressMonitor { /** {@inheritDoc} */ @Override - protected void onUpdate(String taskName, int workCurr) { + protected void onUpdate(String taskName, int workCurr, Duration duration) { StringBuilder s = new StringBuilder(); - format(s, taskName, workCurr); + format(s, taskName, workCurr, duration); send(s); } /** {@inheritDoc} */ @Override - protected void onEndTask(String taskName, int workCurr) { + protected void onEndTask(String taskName, int workCurr, Duration duration) { StringBuilder s = new StringBuilder(); - format(s, taskName, workCurr); + format(s, taskName, workCurr, duration); s.append("\n"); //$NON-NLS-1$ send(s); } - private void format(StringBuilder s, String taskName, int workCurr) { + private void format(StringBuilder s, String taskName, int workCurr, + Duration duration) { s.append("\r"); //$NON-NLS-1$ s.append(taskName); s.append(": "); //$NON-NLS-1$ while (s.length() < 25) s.append(' '); s.append(workCurr); + appendDuration(s, duration); } /** {@inheritDoc} */ @Override - protected void onUpdate(String taskName, int cmp, int totalWork, int pcnt) { + protected void onUpdate(String taskName, int cmp, int totalWork, int pcnt, + Duration duration) { StringBuilder s = new StringBuilder(); - format(s, taskName, cmp, totalWork, pcnt); + format(s, taskName, cmp, totalWork, pcnt, duration); send(s); } /** {@inheritDoc} */ @Override - protected void onEndTask(String taskName, int cmp, int totalWork, int pcnt) { + protected void onEndTask(String taskName, int cmp, int totalWork, int pcnt, + Duration duration) { StringBuilder s = new StringBuilder(); - format(s, taskName, cmp, totalWork, pcnt); + format(s, taskName, cmp, totalWork, pcnt, duration); s.append("\n"); //$NON-NLS-1$ send(s); } private void format(StringBuilder s, String taskName, int cmp, - int totalWork, int pcnt) { + int totalWork, int pcnt, Duration duration) { s.append("\r"); //$NON-NLS-1$ s.append(taskName); s.append(": "); //$NON-NLS-1$ @@ -106,9 +111,10 @@ public class TextProgressMonitor extends BatchingProgressMonitor { s.append(pcnt); s.append("% ("); //$NON-NLS-1$ s.append(curStr); - s.append("/"); //$NON-NLS-1$ + s.append('/'); s.append(endStr); - s.append(")"); //$NON-NLS-1$ + s.append(')'); + appendDuration(s, duration); } private void send(StringBuilder s) { diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ThreadSafeProgressMonitor.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ThreadSafeProgressMonitor.java index 180fbdc461..e553955560 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ThreadSafeProgressMonitor.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ThreadSafeProgressMonitor.java @@ -158,6 +158,11 @@ public class ThreadSafeProgressMonitor implements ProgressMonitor { pm.endTask(); } + @Override + public void showDuration(boolean enabled) { + pm.showDuration(enabled); + } + private boolean isMainThread() { return Thread.currentThread() == mainThread; } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/patch/PatchApplier.java b/org.eclipse.jgit/src/org/eclipse/jgit/patch/PatchApplier.java index ca8ea5d170..98a2804ee4 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/patch/PatchApplier.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/patch/PatchApplier.java @@ -24,6 +24,7 @@ import java.nio.file.StandardCopyOption; import java.text.MessageFormat; import java.time.Instant; import java.util.ArrayList; +import java.util.Arrays; import java.util.HashSet; import java.util.Iterator; import java.util.List; @@ -68,12 +69,14 @@ import org.eclipse.jgit.treewalk.WorkingTreeOptions; import org.eclipse.jgit.treewalk.filter.AndTreeFilter; import org.eclipse.jgit.treewalk.filter.NotIgnoredFilter; import org.eclipse.jgit.treewalk.filter.PathFilterGroup; +import org.eclipse.jgit.util.FS; import org.eclipse.jgit.util.FS.ExecutionResult; import org.eclipse.jgit.util.FileUtils; import org.eclipse.jgit.util.IO; import org.eclipse.jgit.util.LfsFactory; import org.eclipse.jgit.util.LfsFactory.LfsInputStream; import org.eclipse.jgit.util.RawParseUtils; +import org.eclipse.jgit.util.StringUtils; import org.eclipse.jgit.util.TemporaryBuffer; import org.eclipse.jgit.util.TemporaryBuffer.LocalFile; import org.eclipse.jgit.util.io.BinaryDeltaInputStream; @@ -91,6 +94,9 @@ import org.eclipse.jgit.util.sha1.SHA1; */ public class PatchApplier { + private static final byte[] NO_EOL = "\\ No newline at end of file" //$NON-NLS-1$ + .getBytes(StandardCharsets.US_ASCII); + /** The tree before applying the patch. Only non-null for inCore operation. */ @Nullable private final RevTree beforeTree; @@ -180,7 +186,7 @@ public class PatchApplier { public Result applyPatch(InputStream patchInput) throws PatchFormatException, PatchApplyException { Result result = new Result(); - org.eclipse.jgit.patch.Patch p = new org.eclipse.jgit.patch.Patch(); + Patch p = new Patch(); try (InputStream inStream = patchInput) { p.parse(inStream); @@ -188,12 +194,12 @@ public class PatchApplier { throw new PatchFormatException(p.getErrors()); } - DirCache dirCache = (inCore()) ? DirCache.newInCore() + DirCache dirCache = inCore() ? DirCache.read(reader, beforeTree) : repo.lockDirCache(); DirCacheBuilder dirCacheBuilder = dirCache.builder(); Set<String> modifiedPaths = new HashSet<>(); - for (org.eclipse.jgit.patch.FileHeader fh : p.getFiles()) { + for (FileHeader fh : p.getFiles()) { ChangeType type = fh.getChangeType(); switch (type) { case ADD: { @@ -345,8 +351,8 @@ public class PatchApplier { * @throws PatchApplyException */ private void apply(String pathWithOriginalContent, DirCache dirCache, - DirCacheBuilder dirCacheBuilder, @Nullable File f, - org.eclipse.jgit.patch.FileHeader fh) throws PatchApplyException { + DirCacheBuilder dirCacheBuilder, @Nullable File f, FileHeader fh) + throws PatchApplyException { if (PatchType.BINARY.equals(fh.getPatchType())) { // This patch type just says "something changed". We can't do // anything with that. @@ -484,7 +490,7 @@ public class PatchApplier { } dce.setLength(length); - try (LfsInputStream is = org.eclipse.jgit.util.LfsFactory.getInstance() + try (LfsInputStream is = LfsFactory.getInstance() .applyCleanFilter(repo, input, length, lfsAttribute)) { dce.setObjectId(inserter.insert(OBJ_BLOB, is.getLength(), is)); } @@ -522,15 +528,13 @@ public class PatchApplier { // conversion. try (InputStream input = filterClean(repo, path, fileStreamSupplier.load(), convertCrLf, filterCommand)) { - return new RawText(org.eclipse.jgit.util.IO - .readWholeStream(input, 0).array()); + return new RawText(IO.readWholeStream(input, 0).array()); } } if (convertCrLf) { try (InputStream input = EolStreamTypeUtil.wrapInputStream( fileStreamSupplier.load(), EolStreamType.TEXT_LF)) { - return new RawText(org.eclipse.jgit.util.IO - .readWholeStream(input, 0).array()); + return new RawText(IO.readWholeStream(input, 0).array()); } } if (inCore() && fileId.equals(ObjectId.zeroId())) { @@ -547,12 +551,12 @@ public class PatchApplier { input = EolStreamTypeUtil.wrapInputStream(input, EolStreamType.TEXT_LF); } - if (org.eclipse.jgit.util.StringUtils.isEmptyOrNull(filterCommand)) { + if (StringUtils.isEmptyOrNull(filterCommand)) { return input; } if (FilterCommandRegistry.isRegistered(filterCommand)) { - LocalFile buffer = new org.eclipse.jgit.util.TemporaryBuffer.LocalFile( - null, inCoreSizeLimit); + LocalFile buffer = new TemporaryBuffer.LocalFile(null, + inCoreSizeLimit); FilterCommand command = FilterCommandRegistry.createFilterCommand( filterCommand, repository, input, buffer); while (command.run() != -1) { @@ -560,7 +564,7 @@ public class PatchApplier { } return buffer.openInputStreamWithAutoDestroy(); } - org.eclipse.jgit.util.FS fs = repository.getFS(); + FS fs = repository.getFS(); ProcessBuilder filterProcessBuilder = fs.runInShell(filterCommand, new String[0]); filterProcessBuilder.directory(repository.getWorkTree()); @@ -577,14 +581,14 @@ public class PatchApplier { if (rc != 0) { throw new IOException(new FilterFailedException(rc, filterCommand, path, result.getStdout().toByteArray(4096), - org.eclipse.jgit.util.RawParseUtils + RawParseUtils .decode(result.getStderr().toByteArray(4096)))); } return result.getStdout().openInputStreamWithAutoDestroy(); } - private boolean needsCrLfConversion(File f, - org.eclipse.jgit.patch.FileHeader fileHeader) throws IOException { + private boolean needsCrLfConversion(File f, FileHeader fileHeader) + throws IOException { if (PatchType.GIT_BINARY.equals(fileHeader.getPatchType())) { return false; } @@ -596,12 +600,11 @@ public class PatchApplier { return false; } - private static boolean hasCrLf( - org.eclipse.jgit.patch.FileHeader fileHeader) { + private static boolean hasCrLf(FileHeader fileHeader) { if (PatchType.GIT_BINARY.equals(fileHeader.getPatchType())) { return false; } - for (org.eclipse.jgit.patch.HunkHeader header : fileHeader.getHunks()) { + for (HunkHeader header : fileHeader.getHunks()) { byte[] buf = header.getBuffer(); int hunkEnd = header.getEndOffset(); int lineStart = header.getStartOffset(); @@ -702,15 +705,15 @@ public class PatchApplier { * @throws IOException * @throws UnsupportedOperationException */ - private ContentStreamLoader applyBinary(String path, File f, - org.eclipse.jgit.patch.FileHeader fh, StreamSupplier inputSupplier, - ObjectId id) throws PatchApplyException, IOException, + private ContentStreamLoader applyBinary(String path, File f, FileHeader fh, + StreamSupplier inputSupplier, ObjectId id) + throws PatchApplyException, IOException, UnsupportedOperationException { if (!fh.getOldId().isComplete() || !fh.getNewId().isComplete()) { throw new PatchApplyException(MessageFormat .format(JGitText.get().applyBinaryOidTooShort, path)); } - org.eclipse.jgit.patch.BinaryHunk hunk = fh.getForwardBinaryHunk(); + BinaryHunk hunk = fh.getForwardBinaryHunk(); // A BinaryHunk has the start at the "literal" or "delta" token. Data // starts on the next line. int start = RawParseUtils.nextLF(hunk.getBuffer(), @@ -753,8 +756,7 @@ public class PatchApplier { } } - private ContentStreamLoader applyText(RawText rt, - org.eclipse.jgit.patch.FileHeader fh) + private ContentStreamLoader applyText(RawText rt, FileHeader fh) throws IOException, PatchApplyException { List<ByteBuffer> oldLines = new ArrayList<>(rt.size()); for (int i = 0; i < rt.size(); i++) { @@ -764,7 +766,9 @@ public class PatchApplier { int afterLastHunk = 0; int lineNumberShift = 0; int lastHunkNewLine = -1; - for (org.eclipse.jgit.patch.HunkHeader hh : fh.getHunks()) { + boolean lastWasRemoval = false; + boolean noNewLineAtEndOfNew = false; + for (HunkHeader hh : fh.getHunks()) { // We assume hunks to be ordered if (hh.getNewStartLine() <= lastHunkNewLine) { throw new PatchApplyException(MessageFormat @@ -852,17 +856,26 @@ public class PatchApplier { if (!hunkLine.hasRemaining()) { // Completely empty line; accept as empty context line applyAt++; + lastWasRemoval = false; continue; } switch (hunkLine.array()[hunkLine.position()]) { case ' ': applyAt++; + lastWasRemoval = false; break; case '-': newLines.remove(applyAt); + lastWasRemoval = true; break; case '+': newLines.add(applyAt++, slice(hunkLine, 1)); + lastWasRemoval = false; + break; + case '\\': + if (!lastWasRemoval && isNoNewlineAtEnd(hunkLine)) { + noNewLineAtEndOfNew = true; + } break; default: break; @@ -870,12 +883,15 @@ public class PatchApplier { } afterLastHunk = applyAt; } - if (!isNoNewlineAtEndOfFile(fh)) { + // If the last line should have a newline, add a null sentinel + if (lastHunkNewLine >= 0 && afterLastHunk == newLines.size()) { + // Last line came from the patch + if (!noNewLineAtEndOfNew) { + newLines.add(null); + } + } else if (!rt.isMissingNewlineAtEnd()) { newLines.add(null); } - if (!rt.isMissingNewlineAtEnd()) { - oldLines.add(null); - } // We could check if old == new, but the short-circuiting complicates // logic for inCore patching, so just write the new thing regardless. @@ -933,21 +949,9 @@ public class PatchApplier { return ByteBuffer.wrap(b.array(), newOffset, b.limit() - newOffset); } - private boolean isNoNewlineAtEndOfFile( - org.eclipse.jgit.patch.FileHeader fh) { - List<? extends org.eclipse.jgit.patch.HunkHeader> hunks = fh.getHunks(); - if (hunks == null || hunks.isEmpty()) { - return false; - } - org.eclipse.jgit.patch.HunkHeader lastHunk = hunks - .get(hunks.size() - 1); - byte[] buf = new byte[lastHunk.getEndOffset() - - lastHunk.getStartOffset()]; - System.arraycopy(lastHunk.getBuffer(), lastHunk.getStartOffset(), buf, - 0, buf.length); - RawText lhrt = new RawText(buf); - return lhrt.getString(lhrt.size() - 1) - .equals("\\ No newline at end of file"); //$NON-NLS-1$ + private boolean isNoNewlineAtEnd(ByteBuffer hunkLine) { + return Arrays.equals(NO_EOL, 0, NO_EOL.length, hunkLine.array(), + hunkLine.position(), hunkLine.limit()); } /** diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevCommit.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevCommit.java index 6b644cef90..b64c9ce906 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevCommit.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevCommit.java @@ -105,7 +105,12 @@ public class RevCommit extends RevObject { static final RevCommit[] NO_PARENTS = {}; - private RevTree tree; + /** + * Tree reference of the commit. + * + * @since 6.5 + */ + protected RevTree tree; /** * Avoid accessing this field directly. Use method @@ -120,7 +125,15 @@ public class RevCommit extends RevObject { int inDegree; - private byte[] buffer; + /** + * Raw unparsed commit body of the commit. Populated only + * after {@link #parseCanonical(RevWalk, byte[])} with + * {@link RevWalk#isRetainBody()} enable or after + * {@link #parseBody(RevWalk)} and {@link #parse(RevWalk, byte[])}. + * + * @since 6.5.1 + */ + protected byte[] buffer; /** * Create a new commit reference. @@ -657,6 +670,24 @@ public class RevCommit extends RevObject { } /** + * Get the distance of the commit from the root, as defined in + * {@link org.eclipse.jgit.internal.storage.commitgraph.CommitGraph} + * <p> + * Generation number is + * {@link org.eclipse.jgit.lib.Constants#COMMIT_GENERATION_UNKNOWN} when the + * commit is not in the commit-graph. If a commit-graph file was written by + * a version of Git that did not compute generation numbers, then those + * commits in commit-graph will have generation number represented by + * {@link org.eclipse.jgit.lib.Constants#COMMIT_GENERATION_NOT_COMPUTED}. + * + * @return the generation number + * @since 6.5 + */ + int getGeneration() { + return Constants.COMMIT_GENERATION_UNKNOWN; + } + + /** * Reset this commit to allow another RevWalk with the same instances. * <p> * Subclasses <b>must</b> call <code>super.reset()</code> to ensure the diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevCommitCG.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevCommitCG.java new file mode 100644 index 0000000000..4d3664da11 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevCommitCG.java @@ -0,0 +1,106 @@ +/* + * Copyright (C) 2023, Tencent. + * + * 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.revwalk; + +import java.io.IOException; + +import org.eclipse.jgit.errors.IncorrectObjectTypeException; +import org.eclipse.jgit.errors.MissingObjectException; +import org.eclipse.jgit.internal.storage.commitgraph.CommitGraph; +import org.eclipse.jgit.lib.AnyObjectId; +import org.eclipse.jgit.lib.Constants; +import org.eclipse.jgit.lib.ObjectId; + +/** + * RevCommit parsed from + * {@link org.eclipse.jgit.internal.storage.commitgraph.CommitGraph}. + * + * @since 6.5 + */ +class RevCommitCG extends RevCommit { + + private final int graphPosition; + + private int generation = Constants.COMMIT_GENERATION_UNKNOWN; + + /** + * Create a new commit reference. + * + * @param id + * object name for the commit. + * @param graphPosition + * the position in the commit-graph of the object. + */ + protected RevCommitCG(AnyObjectId id, int graphPosition) { + super(id); + this.graphPosition = graphPosition; + } + + /** {@inheritDoc} */ + @Override + void parseCanonical(RevWalk walk, byte[] raw) throws IOException { + if (walk.isRetainBody()) { + buffer = raw; + } + parseInGraph(walk); + } + + /** {@inheritDoc} */ + @Override + void parseHeaders(RevWalk walk) throws MissingObjectException, + IncorrectObjectTypeException, IOException { + if (walk.isRetainBody()) { + super.parseBody(walk); // This parses header and body + return; + } + parseInGraph(walk); + } + + private void parseInGraph(RevWalk walk) throws IOException { + CommitGraph graph = walk.commitGraph(); + CommitGraph.CommitData data = graph.getCommitData(graphPosition); + if (data == null) { + // RevCommitCG was created because we got its graphPosition from + // commit-graph. If now the commit-graph doesn't know about it, + // something went wrong. + throw new IllegalStateException(); + } + if (!walk.shallowCommitsInitialized) { + walk.initializeShallowCommits(this); + } + + this.tree = walk.lookupTree(data.getTree()); + this.commitTime = (int) data.getCommitTime(); + this.generation = data.getGeneration(); + + if (getParents() == null) { + int[] pGraphList = data.getParents(); + if (pGraphList.length == 0) { + this.parents = RevCommit.NO_PARENTS; + } else { + RevCommit[] pList = new RevCommit[pGraphList.length]; + for (int i = 0; i < pList.length; i++) { + int graphPos = pGraphList[i]; + ObjectId objId = graph.getObjectId(graphPos); + pList[i] = walk.lookupCommit(objId, graphPos); + } + this.parents = pList; + } + } + flags |= PARSED; + } + + /** {@inheritDoc} */ + @Override + int getGeneration() { + return generation; + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java index 8da36c5243..9da7105566 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java @@ -12,6 +12,8 @@ package org.eclipse.jgit.revwalk; +import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraph.EMPTY; + import java.io.IOException; import java.text.MessageFormat; import java.util.ArrayList; @@ -30,6 +32,7 @@ import org.eclipse.jgit.errors.RevWalkException; import org.eclipse.jgit.internal.JGitText; import org.eclipse.jgit.lib.AnyObjectId; import org.eclipse.jgit.lib.AsyncObjectLoaderQueue; +import org.eclipse.jgit.internal.storage.commitgraph.CommitGraph; import org.eclipse.jgit.lib.Constants; import org.eclipse.jgit.lib.MutableObjectId; import org.eclipse.jgit.lib.NullProgressMonitor; @@ -189,6 +192,8 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable { private TreeFilter treeFilter; + private CommitGraph commitGraph; + private boolean retainBody = true; private boolean rewriteParents = true; @@ -237,6 +242,7 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable { filter = RevFilter.ALL; treeFilter = TreeFilter.ALL; this.closeReader = closeReader; + commitGraph = null; } /** @@ -900,6 +906,29 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable { } /** + * This method is intended to be invoked only by {@link RevCommitCG}, in + * order to give commit the correct graphPosition before accessing the + * commit-graph. In this way, the headers of the commit can be obtained in + * constant time. + * + * @param id + * name of the commit object. + * @param graphPos + * the position in the commit-graph of the object. + * @return reference to the commit object. Never null. + * @since 6.5 + */ + @NonNull + protected RevCommit lookupCommit(AnyObjectId id, int graphPos) { + RevCommit c = (RevCommit) objects.get(id); + if (c == null) { + c = createCommit(id, graphPos); + objects.add(c); + } + return c; + } + + /** * Locate a reference to a tag without loading it. * <p> * The tag may or may not exist in the repository. It is impossible to tell @@ -1136,6 +1165,26 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable { } /** + * Get the commit-graph. + * + * @return the commit-graph. Never null. + * @since 6.5 + */ + @NonNull + CommitGraph commitGraph() { + if (commitGraph == null) { + try { + commitGraph = reader != null + ? reader.getCommitGraph().orElse(EMPTY) + : EMPTY; + } catch (IOException e) { + commitGraph = EMPTY; + } + } + return commitGraph; + } + + /** * Asynchronous object parsing. * * @param objectIds @@ -1650,6 +1699,13 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable { * @return a new unparsed reference for the object. */ protected RevCommit createCommit(AnyObjectId id) { + return createCommit(id, commitGraph().findGraphPosition(id)); + } + + private RevCommit createCommit(AnyObjectId id, int graphPos) { + if (graphPos >= 0) { + return new RevCommitCG(id, graphPos); + } return new RevCommit(id); } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackConfig.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackConfig.java index ff925dbe8d..a8180d1d8d 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackConfig.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackConfig.java @@ -36,6 +36,7 @@ import static org.eclipse.jgit.lib.ConfigConstants.CONFIG_KEY_THREADS; import static org.eclipse.jgit.lib.ConfigConstants.CONFIG_KEY_WAIT_PREVENT_RACYPACK; import static org.eclipse.jgit.lib.ConfigConstants.CONFIG_KEY_WINDOW; import static org.eclipse.jgit.lib.ConfigConstants.CONFIG_KEY_WINDOW_MEMORY; +import static org.eclipse.jgit.lib.ConfigConstants.CONFIG_KEY_MIN_BYTES_OBJ_SIZE_INDEX; import static org.eclipse.jgit.lib.ConfigConstants.CONFIG_PACK_SECTION; import static org.eclipse.jgit.lib.ConfigConstants.CONFIG_KEY_PACK_KEPT_OBJECTS; import static org.eclipse.jgit.lib.ConfigConstants.CONFIG_KEY_PRESERVE_OLD_PACKS; @@ -249,6 +250,15 @@ public class PackConfig { public static final String[] DEFAULT_BITMAP_EXCLUDED_REFS_PREFIXES = new String[0]; /** + * Default minimum size for an object to be included in the size index: + * {@value} + * + * @see #setMinBytesForObjSizeIndex(int) + * @since 6.5 + */ + public static final int DEFAULT_MIN_BYTES_FOR_OBJ_SIZE_INDEX = -1; + + /** * Default max time to spend during the search for reuse phase. This * optimization is disabled by default: {@value} * @@ -318,6 +328,8 @@ public class PackConfig { private boolean singlePack; + private int minBytesForObjSizeIndex = DEFAULT_MIN_BYTES_FOR_OBJ_SIZE_INDEX; + /** * Create a default configuration. */ @@ -386,6 +398,7 @@ public class PackConfig { this.cutDeltaChains = cfg.cutDeltaChains; this.singlePack = cfg.singlePack; this.searchForReuseTimeout = cfg.searchForReuseTimeout; + this.minBytesForObjSizeIndex = cfg.minBytesForObjSizeIndex; } /** @@ -1235,6 +1248,45 @@ public class PackConfig { } /** + * Minimum size of an object (inclusive) to be added in the object size + * index. + * + * A negative value disables the writing of the object size index. + * + * @return minimum size an object must have to be included in the object + * index. + * @since 6.5 + */ + public int getMinBytesForObjSizeIndex() { + return minBytesForObjSizeIndex; + } + + /** + * Set minimum size an object must have to be included in the object size + * index. + * + * A negative value disables the object index. + * + * @param minBytesForObjSizeIndex + * minimum size (inclusive) of an object to be included in the + * object size index. -1 disables the index. + * @since 6.5 + */ + public void setMinBytesForObjSizeIndex(int minBytesForObjSizeIndex) { + this.minBytesForObjSizeIndex = minBytesForObjSizeIndex; + } + + /** + * Should writers add an object size index when writing a pack. + * + * @return true to write an object-size index with the pack + * @since 6.5 + */ + public boolean isWriteObjSizeIndex() { + return this.minBytesForObjSizeIndex >= 0; + } + + /** * Update properties by setting fields from the configuration. * * If a property's corresponding variable is not defined in the supplied @@ -1316,6 +1368,9 @@ public class PackConfig { setMinSizePreventRacyPack(rc.getLong(CONFIG_PACK_SECTION, CONFIG_KEY_MIN_SIZE_PREVENT_RACYPACK, getMinSizePreventRacyPack())); + setMinBytesForObjSizeIndex(rc.getInt(CONFIG_PACK_SECTION, + CONFIG_KEY_MIN_BYTES_OBJ_SIZE_INDEX, + DEFAULT_MIN_BYTES_FOR_OBJ_SIZE_INDEX)); setPreserveOldPacks(rc.getBoolean(CONFIG_PACK_SECTION, CONFIG_KEY_PRESERVE_OLD_PACKS, DEFAULT_PRESERVE_OLD_PACKS)); setPrunePreserved(rc.getBoolean(CONFIG_PACK_SECTION, @@ -1355,6 +1410,8 @@ public class PackConfig { b.append(", searchForReuseTimeout") //$NON-NLS-1$ .append(getSearchForReuseTimeout()); b.append(", singlePack=").append(getSinglePack()); //$NON-NLS-1$ + b.append(", minBytesForObjSizeIndex=") //$NON-NLS-1$ + .append(getMinBytesForObjSizeIndex()); return b.toString(); } } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/FetchProcess.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/FetchProcess.java index e0eb126440..f02160e457 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/FetchProcess.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/FetchProcess.java @@ -90,6 +90,7 @@ class FetchProcess { .collect(Collectors.toList()); } + @SuppressWarnings("Finally") void execute(ProgressMonitor monitor, FetchResult result, String initialBranch) throws NotSupportedException, TransportException { diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/ProtocolV2Parser.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/ProtocolV2Parser.java index c4129ff4d0..e437f22d02 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/ProtocolV2Parser.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/ProtocolV2Parser.java @@ -281,6 +281,12 @@ final class ProtocolV2Parser { return builder.build(); } + if (!PacketLineIn.isDelimiter(line)) { + throw new PackProtocolException(MessageFormat + .format(JGitText.get().unexpectedPacketLine, line)); + } + + line = pckIn.readString(); if (!line.equals("size")) { //$NON-NLS-1$ throw new PackProtocolException(MessageFormat .format(JGitText.get().unexpectedPacketLine, line)); diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/SideBandProgressMonitor.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/SideBandProgressMonitor.java index 83e8bc291f..33308600d9 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/SideBandProgressMonitor.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/SideBandProgressMonitor.java @@ -12,6 +12,7 @@ package org.eclipse.jgit.transport; import java.io.IOException; import java.io.OutputStream; +import java.time.Duration; import org.eclipse.jgit.lib.BatchingProgressMonitor; import org.eclipse.jgit.lib.Constants; @@ -29,48 +30,52 @@ class SideBandProgressMonitor extends BatchingProgressMonitor { /** {@inheritDoc} */ @Override - protected void onUpdate(String taskName, int workCurr) { + protected void onUpdate(String taskName, int workCurr, Duration duration) { StringBuilder s = new StringBuilder(); - format(s, taskName, workCurr); + format(s, taskName, workCurr, duration); s.append(" \r"); //$NON-NLS-1$ send(s); } /** {@inheritDoc} */ @Override - protected void onEndTask(String taskName, int workCurr) { + protected void onEndTask(String taskName, int workCurr, Duration duration) { StringBuilder s = new StringBuilder(); - format(s, taskName, workCurr); + format(s, taskName, workCurr, duration); s.append(", done\n"); //$NON-NLS-1$ send(s); } - private void format(StringBuilder s, String taskName, int workCurr) { + private void format(StringBuilder s, String taskName, int workCurr, + Duration duration) { s.append(taskName); s.append(": "); //$NON-NLS-1$ s.append(workCurr); + appendDuration(s, duration); } /** {@inheritDoc} */ @Override - protected void onUpdate(String taskName, int cmp, int totalWork, int pcnt) { + protected void onUpdate(String taskName, int cmp, int totalWork, int pcnt, + Duration duration) { StringBuilder s = new StringBuilder(); - format(s, taskName, cmp, totalWork, pcnt); + format(s, taskName, cmp, totalWork, pcnt, duration); s.append(" \r"); //$NON-NLS-1$ send(s); } /** {@inheritDoc} */ @Override - protected void onEndTask(String taskName, int cmp, int totalWork, int pcnt) { + protected void onEndTask(String taskName, int cmp, int totalWork, int pcnt, + Duration duration) { StringBuilder s = new StringBuilder(); - format(s, taskName, cmp, totalWork, pcnt); + format(s, taskName, cmp, totalWork, pcnt, duration); s.append("\n"); //$NON-NLS-1$ send(s); } private void format(StringBuilder s, String taskName, int cmp, - int totalWork, int pcnt) { + int totalWork, int pcnt, Duration duration) { s.append(taskName); s.append(": "); //$NON-NLS-1$ if (pcnt < 100) @@ -80,9 +85,10 @@ class SideBandProgressMonitor extends BatchingProgressMonitor { s.append(pcnt); s.append("% ("); //$NON-NLS-1$ s.append(cmp); - s.append("/"); //$NON-NLS-1$ + s.append('/'); s.append(totalWork); - s.append(")"); //$NON-NLS-1$ + s.append(')'); + appendDuration(s, duration); } private void send(StringBuilder s) { diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/TransferConfig.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/TransferConfig.java index 805166a405..064201a629 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/TransferConfig.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/TransferConfig.java @@ -1,5 +1,5 @@ /* - * Copyright (C) 2008, 2020 Google Inc. and others + * Copyright (C) 2008, 2023 Google Inc. and others * * This program and the accompanying materials are made available under the * terms of the Eclipse Distribution License v. 1.0 which is available at @@ -118,6 +118,7 @@ public class TransferConfig { private final boolean allowRefInWant; private final boolean allowTipSha1InWant; private final boolean allowReachableSha1InWant; + private final boolean allowAnySha1InWant; private final boolean allowFilter; private final boolean allowSidebandAll; @@ -202,6 +203,8 @@ public class TransferConfig { "uploadpack", "allowtipsha1inwant", false); allowReachableSha1InWant = rc.getBoolean( "uploadpack", "allowreachablesha1inwant", false); + allowAnySha1InWant = rc.getBoolean("uploadpack", "allowanysha1inwant", + false); allowFilter = rc.getBoolean( "uploadpack", "allowfilter", false); protocolVersion = ProtocolVersion.parse(rc @@ -284,6 +287,16 @@ public class TransferConfig { } /** + * Whether to allow clients to request any SHA-1s + * + * @return allow clients to request any SHA-1s? + * @since 6.5 + */ + public boolean isAllowAnySha1InWant() { + return allowAnySha1InWant; + } + + /** * @return true if clients are allowed to specify a "filter" line * @since 5.0 */ diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java index 9b40dfea19..f245eae39f 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java @@ -681,6 +681,10 @@ public class UploadPack implements Closeable { */ public void setTransferConfig(@Nullable TransferConfig tc) { this.transferConfig = tc != null ? tc : new TransferConfig(db); + if (transferConfig.isAllowAnySha1InWant()) { + setRequestPolicy(RequestPolicy.ANY); + return; + } if (transferConfig.isAllowTipSha1InWant()) { setRequestPolicy(transferConfig.isAllowReachableSha1InWant() ? RequestPolicy.REACHABLE_COMMIT_TIP : RequestPolicy.TIP); @@ -1386,6 +1390,9 @@ public class UploadPack implements Closeable { if (transferConfig.isAllowReceiveClientSID()) { caps.add(OPTION_SESSION_ID); } + if (transferConfig.isAdvertiseObjectInfo()) { + caps.add(COMMAND_OBJECT_INFO); + } return caps; } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/WalkFetchConnection.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/WalkFetchConnection.java index d67fe074e4..ed8f450c53 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/WalkFetchConnection.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/WalkFetchConnection.java @@ -470,6 +470,7 @@ class WalkFetchConnection extends BaseFetchConnection { } } + @SuppressWarnings("Finally") private boolean downloadPackedObject(final ProgressMonitor monitor, final AnyObjectId id) throws TransportException { // Search for the object in a remote pack whose index we have, diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/WalkPushConnection.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/WalkPushConnection.java index 03ef852c7f..a54fd8e14d 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/WalkPushConnection.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/WalkPushConnection.java @@ -230,7 +230,7 @@ class WalkPushConnection extends BaseConnection implements PushConnection { // offsets from appearing to clients. // dest.writeInfoPacks(packNames.keySet()); - dest.deleteFile(idx.getPath()); + dest.deleteFile(sanitizedPath(idx)); } // Write the pack file, then the index, as readers look the @@ -238,13 +238,13 @@ class WalkPushConnection extends BaseConnection implements PushConnection { // String wt = "Put " + pack.getName().substring(0, 12); //$NON-NLS-1$ try (OutputStream os = new BufferedOutputStream( - dest.writeFile(pack.getPath(), monitor, + dest.writeFile(sanitizedPath(pack), monitor, wt + "." + pack.getPackExt().getExtension()))) { //$NON-NLS-1$ writer.writePack(monitor, monitor, os); } try (OutputStream os = new BufferedOutputStream( - dest.writeFile(idx.getPath(), monitor, + dest.writeFile(sanitizedPath(idx), monitor, wt + "." + idx.getPackExt().getExtension()))) { //$NON-NLS-1$ writer.writeIndex(os); } @@ -269,7 +269,7 @@ class WalkPushConnection extends BaseConnection implements PushConnection { private void safeDelete(File path) { if (path != null) { try { - dest.deleteFile(path.getPath()); + dest.deleteFile(sanitizedPath(path)); } catch (IOException cleanupFailure) { // Ignore the deletion failure. We probably are // already failing and were just trying to pick @@ -366,4 +366,13 @@ class WalkPushConnection extends BaseConnection implements PushConnection { } return updates.get(0).getRemoteName(); } + + private static String sanitizedPath(File file) { + String path = file.getPath(); + if (File.separatorChar != '/') { + path = path.replace(File.separatorChar, '/'); + } + return path; + } + } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/util/IO.java b/org.eclipse.jgit/src/org/eclipse/jgit/util/IO.java index 6d5694e435..80877bbdc6 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/util/IO.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/util/IO.java @@ -207,6 +207,25 @@ public class IO { } /** + * Read from input until the entire byte array filled, or throw an exception + * if stream ends first. + * + * @param fd + * input stream to read the data from. + * @param dst + * buffer that must be fully populated + * @throws EOFException + * the stream ended before dst was fully populated. + * @throws java.io.IOException + * there was an error reading from the stream. + * @since 6.5 + */ + public static void readFully(InputStream fd, byte[] dst) + throws IOException { + readFully(fd, dst, 0, dst.length); + } + + /** * Read as much of the array as possible from a channel. * * @param channel diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/util/SystemReader.java b/org.eclipse.jgit/src/org/eclipse/jgit/util/SystemReader.java index 5ced0713e0..a8a77904a2 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/util/SystemReader.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/util/SystemReader.java @@ -65,6 +65,21 @@ public abstract class SystemReader { private static volatile Boolean isLinux; + private static final String GIT_TRACE_PERFORMANCE = "GIT_TRACE_PERFORMANCE"; //$NON-NLS-1$ + + private static final boolean performanceTrace = initPerformanceTrace(); + + private static boolean initPerformanceTrace() { + String val = System.getenv(GIT_TRACE_PERFORMANCE); + if (val == null) { + val = System.getenv(GIT_TRACE_PERFORMANCE); + } + if (val != null) { + return Boolean.valueOf(val).booleanValue(); + } + return false; + } + static { SystemReader r = new Default(); r.init(); @@ -560,6 +575,16 @@ public abstract class SystemReader { return isLinux.booleanValue(); } + /** + * Whether performance trace is enabled + * + * @return whether performance trace is enabled + * @since 6.5 + */ + public boolean isPerformanceTraceEnabled() { + return performanceTrace; + } + private String getOsName() { return AccessController.doPrivileged( (PrivilegedAction<String>) () -> getProperty("os.name") //$NON-NLS-1$ |