RevWalk: integrate commit-graph with commit parsing

RevWalk#createCommit() will inspect the commit-graph file to find the
specified object's graph position and then return a new RevCommitCG
instance.

RevCommitGC is a RevCommit with an additional "pointer" (the position)
to the commit-graph, so it can load the headers and metadata from there
instead of the pack. This saves IO access in walks where the body is not
needed (i.e. #isRetainBody is false and #parseBody is not invoked).

RevWalk uses automatically the commit-graph if available, no action
needed from callers. The commit-graph is fetched on first access from
the reader (that internally can keep it loaded and reuse it between
walks).

The startup cost of reading the entire commit graph is small. After
testing, reading a commit-graph with 1 million commits takes less than
50ms. If we use RepositoryCache, it will not be initialized util the
commit-graph is rewritten.

Bug: 574368
Change-Id: I90d0f64af24f3acc3eae6da984eae302d338f5ee
Signed-off-by: kylezhao <kylezhao@tencent.com>

4 files changed, 195 insertions, 1 deletions

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
index 162e0e2cb2..0796293f52 100644
--- 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
@@ -30,6 +30,33 @@ import org.eclipse.jgit.lib.ObjectId;
  */
 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>
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..e155a25638 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
@@ -657,6 +662,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..b68f65b68c
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevCommitCG.java
@@ -0,0 +1,93 @@
+/*
+ * 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 parseHeaders(RevWalk walk) throws MissingObjectException,
+			IncorrectObjectTypeException, 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;
+		if (walk.isRetainBody()) {
+			super.parseBody(walk);
+		}
+	}
+
+	/** {@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..a66e7c86bd 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,21 @@ 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) {
+			commitGraph = reader != null ? reader.getCommitGraph().orElse(EMPTY)
+					: EMPTY;
+		}
+		return commitGraph;
+	}
+
+	/**
 	 * Asynchronous object parsing.
 	 *
 	 * @param objectIds
@@ -1650,6 +1694,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);
 	}