diff options
Diffstat (limited to 'org.eclipse.jgit/src')
6 files changed, 152 insertions, 2 deletions
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 6235dd83d9..9d8acad7a8 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java @@ -82,6 +82,7 @@ public class JGitText extends TranslationBundle { /***/ public String cannotCheckoutFromUnbornBranch; /***/ public String cannotCheckoutOursSwitchBranch; /***/ public String cannotCombineSquashWithNoff; + /***/ public String cannotCombineTopoSortWithTopoNonIntermixSort; /***/ public String cannotCombineTreeFilterWithRevFilter; /***/ public String cannotCommitOnARepoWithState; /***/ public String cannotCommitWriteTo; diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevObject.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevObject.java index 5ce4bc33b5..4d2684a0f0 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevObject.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevObject.java @@ -152,6 +152,7 @@ public abstract class RevObject extends ObjectIdOwnerMap.Entry { */ protected void appendCoreFlags(StringBuilder s) { s.append((flags & RevWalk.TOPO_DELAY) != 0 ? 'o' : '-'); + s.append((flags & RevWalk.TOPO_QUEUED) != 0 ? 'q' : '-'); s.append((flags & RevWalk.TEMP_MARK) != 0 ? 't' : '-'); s.append((flags & RevWalk.REWRITE) != 0 ? 'r' : '-'); s.append((flags & RevWalk.UNINTERESTING) != 0 ? 'u' : '-'); diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevSort.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevSort.java index fc6ae28dc9..08396a8061 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevSort.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevSort.java @@ -40,6 +40,18 @@ public enum RevSort { TOPO, /** + * Topological sorting (all children before parents) without intermixing + * lines of history. + * <p> + * This behavior more closely resembles C Git's git-log --topo-order than + * {@link #TOPO}. See C Git's topo-order <a href= + * "https://git-scm.com/docs/git-log#Documentation/git-log.txt---topo-order">description</a>. + * + * @since 5.8 + */ + TOPO_KEEP_BRANCH_TOGETHER, + + /** * Flip the output into the reverse ordering. * <p> * This strategy can be combined with the others described by this type as 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 f425e87618..6b62fcdf6d 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java @@ -131,8 +131,17 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable { */ static final int TOPO_DELAY = 1 << 5; + /** + * Temporary mark for use within {@link TopoNonIntermixSortGenerator}. + * <p> + * This mark indicates the commit has been queued for emission in + * {@link TopoSortGenerator} and can be produced. This mark is removed when + * the commit has been produced. + */ + static final int TOPO_QUEUED = 1 << 6; + /** Number of flag bits we keep internal for our own use. See above flags. */ - static final int RESERVED_FLAGS = 6; + static final int RESERVED_FLAGS = 7; private static final int APP_FLAGS = -1 & ~((1 << RESERVED_FLAGS) - 1); 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 2c1b0a59ee..18af012afd 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java @@ -135,8 +135,18 @@ class StartGenerator extends Generator { } if (walker.hasRevSort(RevSort.TOPO) - && (g.outputType() & SORT_TOPO) == 0) + && walker.hasRevSort(RevSort.TOPO_KEEP_BRANCH_TOGETHER)) { + throw new IllegalStateException(JGitText + .get().cannotCombineTopoSortWithTopoNonIntermixSort); + } + + if (walker.hasRevSort(RevSort.TOPO) + && (g.outputType() & SORT_TOPO) == 0) { g = new TopoSortGenerator(g); + } else if (walker.hasRevSort(RevSort.TOPO_KEEP_BRANCH_TOGETHER) + && (g.outputType() & SORT_TOPO) == 0) { + g = new TopoNonIntermixSortGenerator(g); + } if (walker.hasRevSort(RevSort.REVERSE)) g = new LIFORevQueue(g); if (boundary) diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/TopoNonIntermixSortGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/TopoNonIntermixSortGenerator.java new file mode 100644 index 0000000000..4f6d417ed1 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/TopoNonIntermixSortGenerator.java @@ -0,0 +1,117 @@ +/* + * Copyright (C) 2020, 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.revwalk; + +import java.io.IOException; + +import org.eclipse.jgit.errors.IncorrectObjectTypeException; +import org.eclipse.jgit.errors.MissingObjectException; + +/** Sorts commits in topological order without intermixing lines of history. */ +class TopoNonIntermixSortGenerator extends Generator { + private static final int TOPO_QUEUED = RevWalk.TOPO_QUEUED; + + private final FIFORevQueue pending; + + private final int outputType; + + /** + * Create a new sorter and completely spin the generator. + * <p> + * When the constructor completes the supplied generator will have no + * commits remaining, as all of the commits will be held inside of this + * generator's internal buffer. + * + * @param s + * generator to pull all commits out of, and into this buffer. + * @throws MissingObjectException + * @throws IncorrectObjectTypeException + * @throws IOException + */ + TopoNonIntermixSortGenerator(Generator s) throws MissingObjectException, + IncorrectObjectTypeException, IOException { + super(s.firstParent); + pending = new FIFORevQueue(firstParent); + outputType = s.outputType() | SORT_TOPO; + s.shareFreeList(pending); + for (;;) { + final RevCommit c = s.next(); + if (c == null) { + break; + } + if ((c.flags & TOPO_QUEUED) == 0) { + for (RevCommit p : c.parents) { + p.inDegree++; + + if (firstParent) { + break; + } + } + } + c.flags |= TOPO_QUEUED; + pending.add(c); + } + } + + @Override + int outputType() { + return outputType; + } + + @Override + void shareFreeList(BlockRevQueue q) { + q.shareFreeList(pending); + } + + @Override + RevCommit next() throws MissingObjectException, + IncorrectObjectTypeException, IOException { + for (;;) { + final RevCommit c = pending.next(); + if (c == null) { + return null; + } + + if (c.inDegree > 0) { + // At least one of our children is missing. We delay + // production until all of our children are output. + // + continue; + } + + if ((c.flags & TOPO_QUEUED) == 0) { + // c is a parent that already produced or a parent that + // was never in the priority queue and should never produce. + // + continue; + } + + for (RevCommit p : c.parents) { + if (--p.inDegree == 0 && (p.flags & TOPO_QUEUED) != 0) { + // The parent has no unproduced interesting children. unpop + // the parent so it goes right behind this child. This means + // that this parent commit may appear in "pending" more than + // once, but this is safe since upon the second and + // subsequent iterations with this commit, it will no longer + // have TOPO_QUEUED set, and thus will be skipped. + // + pending.unpop(p); + } + if (firstParent) { + break; + } + } + + c.flags &= ~TOPO_QUEUED; + return c; + } + } +} |