CommitGraph: add commit-graph for FileObjectDatabase

This change makes JGit can read .git/objects/info/commit-graph file
and then get CommitGraph.

Loading a new commit-graph into memory requires additional time. After
testing, loading a copy of the Linux's commit-graph(1039139 commits)
is under 50ms.

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

6 files changed, 162 insertions, 0 deletions

diff --git a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
index 9c918ad410..836213286d 100644
--- a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
+++ b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
@@ -164,6 +164,7 @@ connectionTimeOut=Connection time out: {0}
 contextMustBeNonNegative=context must be >= 0
 cookieFilePathRelative=git config http.cookieFile contains a relative path, should be absolute: {0}
 copyFileFailedNullFiles=Cannot copy file. Either origin or destination files are null
+corruptCommitGraph=commit-graph file {0} is corrupt
 corruptionDetectedReReadingAt=Corruption detected re-reading at {0}
 corruptObjectBadDate=bad date
 corruptObjectBadEmail=bad email
@@ -306,6 +307,7 @@ exceptionHookExecutionInterrupted=Execution of "{0}" hook interrupted.
 exceptionOccurredDuringAddingOfOptionToALogCommand=Exception occurred during adding of {0} as option to a Log command
 exceptionOccurredDuringReadingOfGIT_DIR=Exception occurred during reading of $GIT_DIR/{0}. {1}
 exceptionWhileFindingUserHome=Problem determining the user home directory, trying Java user.home
+exceptionWhileLoadingCommitGraph=Exception caught while loading commit-graph file {0}, the commit-graph file might be corrupt.
 exceptionWhileReadingPack=Exception caught while accessing pack file {0}, the pack file might be corrupt. Caught {1} consecutive errors while trying to read this pack.
 expectedACKNAKFoundEOF=Expected ACK/NAK, found EOF
 expectedACKNAKGot=Expected ACK/NAK, got: {0}
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 3300742f82..f4f91f8aab 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
@@ -192,6 +192,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;
@@ -334,6 +335,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;
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..3e411a125a
--- /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, FileSnapshot.save(file), null);
+		}
+
+		GraphSnapshot(@NonNull File file, @NonNull 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.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/ObjectDirectory.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/ObjectDirectory.java
index f7ccceca47..cb91c7931e 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;
 
@@ -37,6 +38,7 @@ 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.ObjectDatabase;
@@ -85,6 +87,8 @@ public class ObjectDirectory extends FileObjectDatabase {
 
 	private final File alternatesFile;
 
+	private final FileCommitGraph fileCommitGraph;
+
 	private final FS fs;
 
 	private final AtomicReference<AlternateHandle[]> alternates;
@@ -124,6 +128,7 @@ public class ObjectDirectory extends FileObjectDatabase {
 		loose = new LooseObjects(objects);
 		packed = new PackDirectory(config, packDirectory);
 		preserved = new PackDirectory(config, preservedDirectory);
+		fileCommitGraph = new FileCommitGraph(objects);
 		this.fs = fs;
 		this.shallowFile = shallowFile;
 
@@ -227,6 +232,12 @@ public class ObjectDirectory extends FileObjectDatabase {
 		return count;
 	}
 
+	/** {@inheritDoc} */
+	@Override
+	public Optional<CommitGraph> getCommitGraph() {
+		return Optional.ofNullable(fileCommitGraph.get());
+	}
+
 	/**
 	 * {@inheritDoc}
 	 * <p>