Merge branch 'stable-6.7' into stable-6.8

* stable-6.7:
  Introduce a PriorityQueue sorting RevCommits by commit timestamp
  Remove org.eclipse.jgit.benchmark/.factorypath
  Update jmh to 1.37 for org.eclipse.jgit.benchmark

Change-Id: I5d49a9dc7da17b83243229d4d8d3b9ee0a063e65

6 files changed, 195 insertions, 11 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 3798e3f5f8..c54c811b57 100644
--- a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
+++ b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
@@ -557,6 +557,7 @@ nothingToPush=Nothing to push.
 notMergedExceptionMessage=Branch was not deleted as it has not been merged yet; use the force option to delete it anyway
 notShallowedUnshallow=The server sent a unshallow for a commit that wasn''t marked as shallow: {0}
 noXMLParserAvailable=No XML parser available.
+nullRevCommit=RevCommit is null
 numberDoesntFit=Number doesn't fit in a single byte
 objectAtHasBadZlibStream=Object at {0} in {1} has bad zlib stream
 objectIsCorrupt=Object {0} is corrupt: {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 c8509121b4..b7175508ee 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
@@ -587,6 +587,7 @@ public class JGitText extends TranslationBundle {
 	/***/ public String notMergedExceptionMessage;
 	/***/ public String notShallowedUnshallow;
 	/***/ public String noXMLParserAvailable;
+	/***/ public String nullRevCommit;
 	/***/ public String numberDoesntFit;
 	/***/ public String objectAtHasBadZlibStream;
 	/***/ public String objectIsCorrupt;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DateRevPriorityQueue.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DateRevPriorityQueue.java
new file mode 100644
index 0000000000..233dd64a3c
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DateRevPriorityQueue.java
@@ -0,0 +1,150 @@
+/*
+ * Copyright (C) 2023, GerritForge Ltd
+ *
+ * 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.util.concurrent.atomic.AtomicInteger;
+
+import org.eclipse.jgit.annotations.Nullable;
+import org.eclipse.jgit.errors.IncorrectObjectTypeException;
+import org.eclipse.jgit.errors.MissingObjectException;
+import org.eclipse.jgit.internal.JGitText;
+
+import java.io.IOException;
+import java.util.Comparator;
+import java.util.PriorityQueue;
+
+/**
+ * A queue of commits sorted by commit time order using a Java PriorityQueue.
+ * For the commits with the same commit time insertion order will be preserved.
+ */
+class DateRevPriorityQueue extends DateRevQueue {
+	private PriorityQueue<RevCommitEntry> queue;
+
+	private final AtomicInteger sequence = new AtomicInteger(1);
+
+	/**
+	 * Create an empty queue of commits sorted by commit time order.
+	 */
+	public DateRevPriorityQueue() {
+		this(false);
+	}
+
+	/**
+	 * Create an empty queue of commits sorted by commit time order.
+	 *
+	 * @param firstParent
+	 *            treat first element as a parent
+	 */
+	DateRevPriorityQueue(boolean firstParent) {
+		super(firstParent);
+		initPriorityQueue();
+	}
+
+	private void initPriorityQueue() {
+		sequence.set(1);
+		queue = new PriorityQueue<>(Comparator.comparingInt(
+						(RevCommitEntry ent) -> ent.getEntry().getCommitTime())
+				.reversed()
+				.thenComparingInt(RevCommitEntry::getInsertSequenceNumber));
+	}
+
+    DateRevPriorityQueue(Generator s) throws MissingObjectException,
+			IncorrectObjectTypeException, IOException {
+		this(s.firstParent);
+		for (;;) {
+			final RevCommit c = s.next();
+			if (c == null) {
+				break;
+			}
+			add(c);
+		}
+	}
+
+	@Override
+	public void add(RevCommit c) {
+		// PriorityQueue does not accept null values. To keep the same behaviour
+		// do the same check and throw the same exception before creating entry
+		if (c == null) {
+			throw new NullPointerException(JGitText.get().nullRevCommit);
+		}
+		queue.add(new RevCommitEntry(sequence.getAndIncrement(), c));
+	}
+
+	@Override
+	public RevCommit next() {
+		RevCommitEntry entry = queue.poll();
+		return entry == null ? null : entry.getEntry();
+	}
+
+	/**
+	 * Peek at the next commit, without removing it.
+	 *
+	 * @return the next available commit; null if there are no commits left.
+	 */
+	@Override
+	public @Nullable RevCommit peek() {
+		RevCommitEntry entry = queue.peek();
+		return entry == null ? null : entry.getEntry();
+	}
+
+	/**
+	 * {@inheritDoc}
+	 */
+	@Override
+	public void clear() {
+		sequence.set(1);
+		queue.clear();
+	}
+
+	@Override
+	boolean everbodyHasFlag(int f) {
+		return queue.stream().map(RevCommitEntry::getEntry)
+				.noneMatch(c -> (c.flags & f) == 0);
+	}
+
+	@Override
+	boolean anybodyHasFlag(int f) {
+		return queue.stream().map(RevCommitEntry::getEntry)
+				.anyMatch(c -> (c.flags & f) != 0);
+	}
+
+	@Override
+	int outputType() {
+		return outputType | SORT_COMMIT_TIME_DESC;
+	}
+
+	@Override
+	public String toString() {
+		final StringBuilder s = new StringBuilder();
+		for (RevCommitEntry e : queue) {
+			describe(s, e.getEntry());
+		}
+		return s.toString();
+	}
+
+	private static class RevCommitEntry {
+		private final int insertSequenceNumber;
+
+		private final RevCommit entry;
+
+		public RevCommitEntry(int insertSequenceNumber, RevCommit entry) {
+			this.insertSequenceNumber = insertSequenceNumber;
+			this.entry = entry;
+		}
+
+		public int getInsertSequenceNumber() {
+			return insertSequenceNumber;
+		}
+
+		public RevCommit getEntry() {
+			return entry;
+		}
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DateRevQueue.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DateRevQueue.java
index 4ec9afc718..905dcb62ad 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DateRevQueue.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DateRevQueue.java
@@ -8,11 +8,11 @@
  *
  * SPDX-License-Identifier: BSD-3-Clause
  */
-
 package org.eclipse.jgit.revwalk;
 
 import java.io.IOException;
 
+import org.eclipse.jgit.annotations.Nullable;
 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
 import org.eclipse.jgit.errors.MissingObjectException;
 
@@ -36,11 +36,17 @@ public class DateRevQueue extends AbstractRevQueue {
 
 	private int last = -1;
 
-	/** Create an empty date queue. */
+	/** Create an empty DateRevQueue. */
 	public DateRevQueue() {
 		super(false);
 	}
 
+	/**
+	 * Create an empty DateRevQueue.
+	 *
+	 * @param firstParent
+	 *            treat first element as a parent
+	 */
 	DateRevQueue(boolean firstParent) {
 		super(firstParent);
 	}
@@ -133,7 +139,7 @@ public class DateRevQueue extends AbstractRevQueue {
 	 *
 	 * @return the next available commit; null if there are no commits left.
 	 */
-	public RevCommit peek() {
+	public @Nullable RevCommit peek() {
 		return head != null ? head.commit : null;
 	}
 
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 0d9ccdbc1b..76c14e9c26 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
@@ -21,6 +21,7 @@ import java.util.Collection;
 import java.util.EnumSet;
 import java.util.Iterator;
 import java.util.List;
+import java.util.Optional;
 
 import org.eclipse.jgit.annotations.NonNull;
 import org.eclipse.jgit.annotations.Nullable;
@@ -235,7 +236,7 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 		idBuffer = new MutableObjectId();
 		objects = new ObjectIdOwnerMap<>();
 		roots = new ArrayList<>();
-		queue = new DateRevQueue(false);
+		queue = newDateRevQueue(false);
 		pending = new StartGenerator(this);
 		sorting = EnumSet.of(RevSort.NONE);
 		filter = RevFilter.ALL;
@@ -244,6 +245,30 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 		commitGraph = null;
 	}
 
+	static AbstractRevQueue newDateRevQueue(boolean firstParent) {
+		if(usePriorityQueue()) {
+			return new DateRevPriorityQueue(firstParent);
+		}
+
+		return new DateRevQueue(firstParent);
+	}
+
+	static DateRevQueue newDateRevQueue(Generator g) throws IOException {
+		if(usePriorityQueue()) {
+			return new DateRevPriorityQueue(g);
+		}
+
+		return new DateRevQueue(g);
+	}
+
+	@SuppressWarnings("boxing")
+	private static boolean usePriorityQueue() {
+		return Optional
+				.ofNullable(System.getProperty("REVWALK_USE_PRIORITY_QUEUE")) //$NON-NLS-1$
+							.map(Boolean::parseBoolean)
+							.orElse(false);
+	}
+
 	/**
 	 * Get the reader this walker is using to load objects.
 	 *
@@ -847,7 +872,7 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 		assertNotStarted();
 		assertNoCommitsMarkedStart();
 		firstParent = enable;
-		queue = new DateRevQueue(firstParent);
+		queue = newDateRevQueue(firstParent);
 		pending = new StartGenerator(this);
 	}
 
@@ -1567,7 +1592,7 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 		}
 
 		roots.clear();
-		queue = new DateRevQueue(firstParent);
+		queue = newDateRevQueue(firstParent);
 		pending = new StartGenerator(this);
 	}
 
@@ -1588,7 +1613,7 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 		firstParent = false;
 		objects.clear();
 		roots.clear();
-		queue = new DateRevQueue(firstParent);
+		queue = newDateRevQueue(firstParent);
 		pending = new StartGenerator(this);
 		shallowCommitsInitialized = false;
 	}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java
index a79901ca10..414af30486 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java
@@ -93,10 +93,11 @@ class StartGenerator extends Generator {
 
 		final DateRevQueue pending;
 		int pendingOutputType = 0;
-		if (q instanceof DateRevQueue)
-			pending = (DateRevQueue)q;
-		else
-			pending = new DateRevQueue(q);
+		if (q instanceof DateRevQueue) {
+			pending = (DateRevQueue) q;
+		} else {
+			pending = RevWalk.newDateRevQueue(q);
+		}
 		if (tf != TreeFilter.ALL) {
 			int rewriteFlag;
 			if (w.getRewriteParents()) {