From 4973f05252b2159d9ceff4f480d252a596a669a1 Mon Sep 17 00:00:00 2001 From: Dave Borowitz Date: Mon, 3 Jun 2019 14:03:49 -0700 Subject: RevWalk: Add a setFirstParent that mimics C git's --first-parent RevWalk does not currently provide a --first-parent equivalent and the feature has been requested. Add a field to the RevWalk class to specify whether walks should traverse first parents only. Modify Generator implementations to support the feature. Change-Id: I4a9a0d5767f82141dcf6d08659d7cb77c585fae4 Signed-off-by: Dave Borowitz Signed-off-by: Alex Spradlin --- .../org/eclipse/jgit/revwalk/AbstractRevQueue.java | 19 ++++++-- .../org/eclipse/jgit/revwalk/BlockRevQueue.java | 8 +++- .../eclipse/jgit/revwalk/BoundaryGenerator.java | 16 +++++-- .../src/org/eclipse/jgit/revwalk/DateRevQueue.java | 11 +++-- .../org/eclipse/jgit/revwalk/DelayRevQueue.java | 1 + .../org/eclipse/jgit/revwalk/DepthGenerator.java | 9 +++- .../src/org/eclipse/jgit/revwalk/EndGenerator.java | 2 +- .../src/org/eclipse/jgit/revwalk/FIFORevQueue.java | 10 +++-- .../jgit/revwalk/FixUninterestingGenerator.java | 1 + .../src/org/eclipse/jgit/revwalk/Generator.java | 6 +++ .../src/org/eclipse/jgit/revwalk/LIFORevQueue.java | 2 +- .../eclipse/jgit/revwalk/MergeBaseGenerator.java | 3 +- .../org/eclipse/jgit/revwalk/PendingGenerator.java | 7 ++- .../src/org/eclipse/jgit/revwalk/RevWalk.java | 52 ++++++++++++++++++++-- .../org/eclipse/jgit/revwalk/RewriteGenerator.java | 5 +++ .../org/eclipse/jgit/revwalk/StartGenerator.java | 8 +++- .../eclipse/jgit/revwalk/TopoSortGenerator.java | 20 ++++++--- 17 files changed, 148 insertions(+), 32 deletions(-) (limited to 'org.eclipse.jgit/src/org/eclipse/jgit/revwalk') diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/AbstractRevQueue.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/AbstractRevQueue.java index 247a3bdb28..7b5e6fa310 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/AbstractRevQueue.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/AbstractRevQueue.java @@ -49,6 +49,10 @@ abstract class AbstractRevQueue extends Generator { /** Current output flags set for this generator instance. */ int outputType; + AbstractRevQueue(boolean firstParent) { + super(firstParent); + } + /** * Add a commit to the queue. *

@@ -96,10 +100,15 @@ abstract class AbstractRevQueue extends Generator { */ public final void addParents(RevCommit c, RevFlag queueControl) { final RevCommit[] pList = c.parents; - if (pList == null) + if (pList == null) { return; - for (RevCommit p : pList) - add(p, queueControl); + } + for (int i = 0; i < pList.length; i++) { + if (firstParent && i > 0) { + break; + } + add(pList[i], queueControl); + } } /** @@ -138,6 +147,10 @@ abstract class AbstractRevQueue extends Generator { } private static class AlwaysEmptyQueue extends AbstractRevQueue { + private AlwaysEmptyQueue() { + super(false); + } + @Override public void add(RevCommit c) { throw new UnsupportedOperationException(); diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BlockRevQueue.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BlockRevQueue.java index 79307b5b7c..64e9e03229 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BlockRevQueue.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BlockRevQueue.java @@ -53,13 +53,19 @@ abstract class BlockRevQueue extends AbstractRevQueue { /** * Create an empty revision queue. + * + * @param firstParent + * whether only first-parent links should be followed when + * walking */ - protected BlockRevQueue() { + protected BlockRevQueue(boolean firstParent) { + super(firstParent); free = new BlockFreeList(); } BlockRevQueue(Generator s) throws MissingObjectException, IncorrectObjectTypeException, IOException { + super(s.firstParent); free = new BlockFreeList(); outputType = s.outputType(); s.shareFreeList(this); diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BoundaryGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BoundaryGenerator.java index 0fd6621e62..98c99e845d 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BoundaryGenerator.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BoundaryGenerator.java @@ -55,6 +55,7 @@ class BoundaryGenerator extends Generator { Generator g; BoundaryGenerator(RevWalk w, Generator s) { + super(s.firstParent); g = new InitialGenerator(w, s); } @@ -86,8 +87,9 @@ class BoundaryGenerator extends Generator { private final Generator source; InitialGenerator(RevWalk w, Generator s) { + super(s.firstParent); walk = w; - held = new FIFORevQueue(); + held = new FIFORevQueue(firstParent); source = s; source.shareFreeList(held); } @@ -107,13 +109,19 @@ class BoundaryGenerator extends Generator { IncorrectObjectTypeException, IOException { RevCommit c = source.next(); if (c != null) { - for (RevCommit p : c.parents) - if ((p.flags & UNINTERESTING) != 0) + for (int i = 0; i < c.parents.length; i++) { + if (firstParent && i > 0) { + break; + } + RevCommit p = c.parents[i]; + if ((p.flags & UNINTERESTING) != 0) { held.add(p); + } + } return c; } - final FIFORevQueue boundary = new FIFORevQueue(); + final FIFORevQueue boundary = new FIFORevQueue(firstParent); boundary.shareFreeList(held); for (;;) { c = held.next(); 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 b86e876201..d77b055534 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DateRevQueue.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DateRevQueue.java @@ -69,15 +69,18 @@ public class DateRevQueue extends AbstractRevQueue { private int last = -1; - /** - * Create an empty date queue. - */ + /** Create an empty date queue. */ public DateRevQueue() { - super(); + super(false); + } + + DateRevQueue(boolean firstParent) { + super(firstParent); } DateRevQueue(Generator s) throws MissingObjectException, IncorrectObjectTypeException, IOException { + super(s.firstParent); for (;;) { final RevCommit c = s.next(); if (c == null) diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DelayRevQueue.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DelayRevQueue.java index c397a01317..9134e08b28 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DelayRevQueue.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DelayRevQueue.java @@ -70,6 +70,7 @@ final class DelayRevQueue extends Generator { private int size; DelayRevQueue(Generator g) { + super(g.firstParent); pending = g; delay = new FIFORevQueue(); } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DepthGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DepthGenerator.java index 5199a2927d..0b04d5d174 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DepthGenerator.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DepthGenerator.java @@ -95,7 +95,8 @@ class DepthGenerator extends Generator { */ DepthGenerator(DepthWalk w, Generator s) throws MissingObjectException, IncorrectObjectTypeException, IOException { - pending = new FIFORevQueue(); + super(s.firstParent); + pending = new FIFORevQueue(firstParent); walk = (RevWalk)w; this.depth = w.getDepth(); @@ -196,7 +197,11 @@ class DepthGenerator extends Generator { int newDepth = c.depth + 1; - for (RevCommit p : c.parents) { + for (int i = 0; i < c.parents.length; i++) { + if (firstParent && i > 0) { + break; + } + RevCommit p = c.parents[i]; DepthWalk.Commit dp = (DepthWalk.Commit) p; // If no depth has been assigned to this commit, assign diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/EndGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/EndGenerator.java index 627e1c7a51..03916c8152 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/EndGenerator.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/EndGenerator.java @@ -47,7 +47,7 @@ class EndGenerator extends Generator { static final EndGenerator INSTANCE = new EndGenerator(); private EndGenerator() { - // We have nothing to initialize. + super(false); } @Override diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/FIFORevQueue.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/FIFORevQueue.java index cdb084c15e..40ee55c730 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/FIFORevQueue.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/FIFORevQueue.java @@ -56,11 +56,13 @@ public class FIFORevQueue extends BlockRevQueue { private Block tail; - /** - * Create an empty FIFO queue. - */ + /** Create an empty FIFO queue. */ public FIFORevQueue() { - super(); + super(false); + } + + FIFORevQueue(boolean firstParent) { + super(firstParent); } FIFORevQueue(Generator s) throws MissingObjectException, diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/FixUninterestingGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/FixUninterestingGenerator.java index 4e6d7e681d..289842a909 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/FixUninterestingGenerator.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/FixUninterestingGenerator.java @@ -62,6 +62,7 @@ final class FixUninterestingGenerator extends Generator { private final Generator pending; FixUninterestingGenerator(Generator g) { + super(g.firstParent); pending = g; } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/Generator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/Generator.java index b2c92ea249..59c5cce828 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/Generator.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/Generator.java @@ -75,6 +75,12 @@ abstract class Generator { /** Output may have {@link RevWalk#UNINTERESTING} marked on it. */ static final int HAS_UNINTERESTING = 1 << 4; + protected final boolean firstParent; + + protected Generator(boolean firstParent) { + this.firstParent = firstParent; + } + /** * Connect the supplied queue to this generator's own free list (if any). * diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/LIFORevQueue.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/LIFORevQueue.java index 846b8d92fa..5628d359bf 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/LIFORevQueue.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/LIFORevQueue.java @@ -59,7 +59,7 @@ public class LIFORevQueue extends BlockRevQueue { * Create an empty LIFO queue. */ public LIFORevQueue() { - super(); + super(false); } LIFORevQueue(Generator s) throws MissingObjectException, diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/MergeBaseGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/MergeBaseGenerator.java index 2fe95318b2..4ea57cb51b 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/MergeBaseGenerator.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/MergeBaseGenerator.java @@ -85,8 +85,9 @@ class MergeBaseGenerator extends Generator { private CarryStack stack; MergeBaseGenerator(RevWalk w) { + super(w.isFirstParent()); walker = w; - pending = new DateRevQueue(); + pending = new DateRevQueue(firstParent); } void init(AbstractRevQueue p) throws IOException { diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/PendingGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/PendingGenerator.java index e607b7daa0..52dd56d129 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/PendingGenerator.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/PendingGenerator.java @@ -109,6 +109,7 @@ class PendingGenerator extends Generator { PendingGenerator(final RevWalk w, final DateRevQueue p, final RevFilter f, final int out) { + super(w.isFirstParent()); walker = w; pending = p; filter = f; @@ -140,7 +141,11 @@ class PendingGenerator extends Generator { produce = filter.include(walker, c); } - for (RevCommit p : c.parents) { + for (int i = 0; i < c.parents.length; i++) { + RevCommit p = c.parents[i]; + if (firstParent && i > 0) { + continue; + } if ((p.flags & SEEN) != 0) continue; if ((p.flags & PARSED) == 0) 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 80fc81073c..12e9f892b3 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java @@ -200,6 +200,8 @@ public class RevWalk implements Iterable, AutoCloseable { private boolean rewriteParents = true; + private boolean firstParent; + boolean shallowCommitsInitialized; /** @@ -232,7 +234,7 @@ public class RevWalk implements Iterable, AutoCloseable { idBuffer = new MutableObjectId(); objects = new ObjectIdOwnerMap<>(); roots = new ArrayList<>(); - queue = new DateRevQueue(); + queue = new DateRevQueue(false); pending = new StartGenerator(this); sorting = EnumSet.of(RevSort.NONE); filter = RevFilter.ALL; @@ -660,6 +662,33 @@ public class RevWalk implements Iterable, AutoCloseable { retainBody = retain; } + /** + * @return whether only first-parent links should be followed when walking. + * @since 5.4 + */ + public boolean isFirstParent() { + return firstParent; + } + + /** + * Set whether or not only first parent links should be followed. + *

+ * If set, second- and higher-parent links are not traversed at all. + *

+ * This must be called prior to {@link #markStart(RevCommit)}. + * + * @param enable + * true to walk only first-parent links. + * @since 5.4 + */ + public void setFirstParent(boolean enable) { + assertNotStarted(); + assertNoCommitsMarkedStart(); + firstParent = enable; + queue = new DateRevQueue(firstParent); + pending = new StartGenerator(this); + } + /** * Locate a reference to a blob without loading it. *

@@ -1292,7 +1321,8 @@ public class RevWalk implements Iterable, AutoCloseable { *

* Unlike {@link #dispose()} previously acquired RevObject (and RevCommit) * instances are not invalidated. RevFlag instances are not invalidated, but - * are removed from all RevObjects. + * are removed from all RevObjects. The value of {@code firstParent} is + * retained. * * @param retainFlags * application flags that should not be cleared from @@ -1328,7 +1358,7 @@ public class RevWalk implements Iterable, AutoCloseable { } roots.clear(); - queue = new DateRevQueue(); + queue = new DateRevQueue(firstParent); pending = new StartGenerator(this); } @@ -1346,9 +1376,10 @@ public class RevWalk implements Iterable, AutoCloseable { delayFreeFlags = 0; retainOnReset = 0; carryFlags = UNINTERESTING; + firstParent = false; objects.clear(); roots.clear(); - queue = new DateRevQueue(); + queue = new DateRevQueue(firstParent); pending = new StartGenerator(this); shallowCommitsInitialized = false; } @@ -1420,6 +1451,19 @@ public class RevWalk implements Iterable, AutoCloseable { throw new IllegalStateException(JGitText.get().outputHasAlreadyBeenStarted); } + /** + * Throws an exception if any commits have been marked as start. + *

+ * If {@link #markStart(RevCommit)} has already been called, + * {@link #reset()} can be called to satisfy this condition. + */ + protected void assertNoCommitsMarkedStart() { + if (roots.isEmpty()) + return; + throw new IllegalStateException( + JGitText.get().commitsHaveAlreadyBeenMarkedAsStart); + } + private boolean isNotStarted() { return pending instanceof StartGenerator; } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RewriteGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RewriteGenerator.java index 1c868ffe08..2e26641ebc 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RewriteGenerator.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RewriteGenerator.java @@ -77,6 +77,7 @@ class RewriteGenerator extends Generator { private final Generator source; RewriteGenerator(Generator s) { + super(s.firstParent); source = s; } @@ -102,6 +103,10 @@ class RewriteGenerator extends Generator { final int nParents = pList.length; for (int i = 0; i < nParents; i++) { final RevCommit oldp = pList[i]; + if (firstParent && i > 0) { + c.parents = new RevCommit[] { rewrite(oldp) }; + return c; + } final RevCommit newp = rewrite(oldp); if (oldp != newp) { pList[i] = newp; 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 eb129a2631..b309d6fee2 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java @@ -67,6 +67,7 @@ class StartGenerator extends Generator { private final RevWalk walker; StartGenerator(RevWalk w) { + super(w.isFirstParent()); walker = w; } @@ -89,9 +90,14 @@ class StartGenerator extends Generator { // Computing for merge bases is a special case and does not // use the bulk of the generator pipeline. // - if (tf != TreeFilter.ALL) + if (tf != TreeFilter.ALL) { throw new IllegalStateException(MessageFormat.format( JGitText.get().cannotCombineTreeFilterWithRevFilter, tf, rf)); + } + if (w.isFirstParent()) { + throw new IllegalStateException( + JGitText.get().cannotFindMergeBaseUsingFirstParent); + } final MergeBaseGenerator mbg = new MergeBaseGenerator(w); walker.pending = mbg; diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/TopoSortGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/TopoSortGenerator.java index 645034351f..a2c9ef6da4 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/TopoSortGenerator.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/TopoSortGenerator.java @@ -71,15 +71,21 @@ class TopoSortGenerator extends Generator { */ TopoSortGenerator(Generator s) throws MissingObjectException, IncorrectObjectTypeException, IOException { - pending = new FIFORevQueue(); + super(s.firstParent); + pending = new FIFORevQueue(firstParent); outputType = s.outputType() | SORT_TOPO; s.shareFreeList(pending); for (;;) { final RevCommit c = s.next(); - if (c == null) + if (c == null) { break; - for (RevCommit p : c.parents) - p.inDegree++; + } + for (int i = 0; i < c.parents.length; i++) { + if (firstParent && i > 0) { + break; + } + c.parents[i].inDegree++; + } pending.add(c); } } @@ -113,7 +119,11 @@ class TopoSortGenerator extends Generator { // All of our children have already produced, // so it is OK for us to produce now as well. // - for (RevCommit p : c.parents) { + for (int i = 0; i < c.parents.length; i++) { + if (firstParent && i > 0) { + break; + } + RevCommit p = c.parents[i]; if (--p.inDegree == 0 && (p.flags & TOPO_DELAY) != 0) { // This parent tried to come before us, but we are // his last child. unpop the parent so it goes right -- cgit v1.2.3