* [JGIT PATCH 0/5] RevWalk fixes for UNINTERESTING
@ 2009-03-13 2:07 Shawn O. Pearce
2009-03-13 2:07 ` [JGIT PATCH 1/5] Show critical flags in debug toString() descriptions of rev queues Shawn O. Pearce
2009-03-13 20:00 ` [JGIT PATCH 0/5] RevWalk fixes for UNINTERESTING Robin Rosenberg
0 siblings, 2 replies; 13+ messages in thread
From: Shawn O. Pearce @ 2009-03-13 2:07 UTC (permalink / raw)
To: Robin Rosenberg; +Cc: git
Today I uncovered some ugly cases with "jgit rev-list B ^A", where
some commits reachable from A were still being output, even though
we asked that they be excluded.
This series attempts to fix it by forcing date ordering, and delaying
output a little to try and work over any clock skew discovered near
the end of the traversal, just before we give up.
Shawn O. Pearce (5):
Show critical flags in debug toString() descriptions of rev queues
Make RevObject.getType implementations final
Remove the horribly stupid RevSort.START_ORDER
Fix RevWalk with Linus Torvald's occasional bad commit date hack
Avoid incorrect output of UNINTERESTING commits when clock skew
occurs
.../org/spearce/jgit/revwalk/AbstractRevQueue.java | 5 +
.../src/org/spearce/jgit/revwalk/DateRevQueue.java | 10 +--
.../org/spearce/jgit/revwalk/DelayRevQueue.java | 92 ++++++++++++++++++++
.../src/org/spearce/jgit/revwalk/FIFORevQueue.java | 10 +--
.../jgit/revwalk/FixUninterestingGenerator.java | 77 ++++++++++++++++
.../src/org/spearce/jgit/revwalk/LIFORevQueue.java | 10 +--
.../org/spearce/jgit/revwalk/PendingGenerator.java | 59 +++++++++++--
.../src/org/spearce/jgit/revwalk/RevBlob.java | 2 +-
.../src/org/spearce/jgit/revwalk/RevCommit.java | 15 +++-
.../src/org/spearce/jgit/revwalk/RevObject.java | 24 +++++
.../src/org/spearce/jgit/revwalk/RevSort.java | 11 ---
.../src/org/spearce/jgit/revwalk/RevTag.java | 2 +-
.../src/org/spearce/jgit/revwalk/RevTree.java | 2 +-
.../src/org/spearce/jgit/revwalk/RevWalk.java | 6 +-
.../org/spearce/jgit/revwalk/StartGenerator.java | 27 ++++--
15 files changed, 296 insertions(+), 56 deletions(-)
create mode 100644 org.spearce.jgit/src/org/spearce/jgit/revwalk/DelayRevQueue.java
create mode 100644 org.spearce.jgit/src/org/spearce/jgit/revwalk/FixUninterestingGenerator.java
^ permalink raw reply [flat|nested] 13+ messages in thread* [JGIT PATCH 1/5] Show critical flags in debug toString() descriptions of rev queues 2009-03-13 2:07 [JGIT PATCH 0/5] RevWalk fixes for UNINTERESTING Shawn O. Pearce @ 2009-03-13 2:07 ` Shawn O. Pearce 2009-03-13 2:07 ` [JGIT PATCH 2/5] Make RevObject.getType implementations final Shawn O. Pearce 2009-03-13 20:00 ` [JGIT PATCH 0/5] RevWalk fixes for UNINTERESTING Robin Rosenberg 1 sibling, 1 reply; 13+ messages in thread From: Shawn O. Pearce @ 2009-03-13 2:07 UTC (permalink / raw) To: Robin Rosenberg; +Cc: git These can help identify the state of each object, especially the important UNINTERESTING flag being present (or not). Signed-off-by: Shawn O. Pearce <spearce@spearce.org> --- .../org/spearce/jgit/revwalk/AbstractRevQueue.java | 5 ++++ .../src/org/spearce/jgit/revwalk/DateRevQueue.java | 10 ++------ .../src/org/spearce/jgit/revwalk/FIFORevQueue.java | 10 ++------ .../src/org/spearce/jgit/revwalk/LIFORevQueue.java | 10 ++------ .../src/org/spearce/jgit/revwalk/RevCommit.java | 12 ++++++++++ .../src/org/spearce/jgit/revwalk/RevObject.java | 23 ++++++++++++++++++++ 6 files changed, 49 insertions(+), 21 deletions(-) diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/AbstractRevQueue.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/AbstractRevQueue.java index 4cf7dae..5bb969d 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/AbstractRevQueue.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/AbstractRevQueue.java @@ -115,6 +115,11 @@ int outputType() { return outputType; } + protected static void describe(final StringBuilder s, final RevCommit c) { + s.append(c.toString()); + s.append('\n'); + } + private static class AlwaysEmptyQueue extends AbstractRevQueue { @Override public void add(RevCommit c) { diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/DateRevQueue.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/DateRevQueue.java index f797477..210f985 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/DateRevQueue.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/DateRevQueue.java @@ -126,13 +126,9 @@ int outputType() { } public String toString() { - final StringBuffer s = new StringBuffer(); - for (Entry q = head; q != null; q = q.next) { - s.append(q.commit.name()); - s.append(' '); - s.append(q.commit.commitTime); - s.append('\n'); - } + final StringBuilder s = new StringBuilder(); + for (Entry q = head; q != null; q = q.next) + describe(s, q.commit); return s.toString(); } diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/FIFORevQueue.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/FIFORevQueue.java index 2c4c003..f086928 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/FIFORevQueue.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/FIFORevQueue.java @@ -149,14 +149,10 @@ void removeFlag(final int f) { } public String toString() { - final StringBuffer s = new StringBuffer(); + final StringBuilder s = new StringBuilder(); for (Block q = head; q != null; q = q.next) { - for (int i = q.headIndex; i < q.tailIndex; i++) { - s.append(q.commits[i].name()); - s.append(' '); - s.append(q.commits[i].commitTime); - s.append('\n'); - } + for (int i = q.headIndex; i < q.tailIndex; i++) + describe(s, q.commits[i]); } return s.toString(); } diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/LIFORevQueue.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/LIFORevQueue.java index 5e885c0..045f7f1 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/LIFORevQueue.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/LIFORevQueue.java @@ -104,14 +104,10 @@ boolean anybodyHasFlag(final int f) { } public String toString() { - final StringBuffer s = new StringBuffer(); + final StringBuilder s = new StringBuilder(); for (Block q = head; q != null; q = q.next) { - for (int i = q.headIndex; i < q.tailIndex; i++) { - s.append(q.commits[i].name()); - s.append(' '); - s.append(q.commits[i].commitTime); - s.append('\n'); - } + for (int i = q.headIndex; i < q.tailIndex; i++) + describe(s, q.commits[i]); } return s.toString(); } diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevCommit.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevCommit.java index de11c39..1b25fce 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevCommit.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevCommit.java @@ -388,4 +388,16 @@ public void dispose() { flags &= ~PARSED; buffer = null; } + + @Override + public String toString() { + final StringBuilder s = new StringBuilder(); + s.append(Constants.typeString(getType())); + s.append(name()); + s.append(' '); + s.append(commitTime); + s.append(' '); + appendCoreFlags(s); + return s.toString(); + } } diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevObject.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevObject.java index 451205c..7dadb7b 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevObject.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevObject.java @@ -167,4 +167,27 @@ public void remove(final RevFlagSet set) { public void dispose() { // Nothing needs to be done for most objects. } + + @Override + public String toString() { + final StringBuilder s = new StringBuilder(); + s.append(Constants.typeString(getType())); + s.append(name()); + s.append(' '); + appendCoreFlags(s); + return s.toString(); + } + + /** + * @param s + * buffer to append a debug description of core RevFlags onto. + */ + protected void appendCoreFlags(final StringBuilder s) { + s.append((flags & RevWalk.TOPO_DELAY) != 0 ? 'o' : '-'); + s.append((flags & RevWalk.TEMP_MARK) != 0 ? 't' : '-'); + s.append((flags & RevWalk.REWRITE) != 0 ? 'r' : '-'); + s.append((flags & RevWalk.UNINTERESTING) != 0 ? 'u' : '-'); + s.append((flags & RevWalk.SEEN) != 0 ? 's' : '-'); + s.append((flags & RevWalk.PARSED) != 0 ? 'p' : '-'); + } } -- 1.6.2.288.gc3f22 ^ permalink raw reply related [flat|nested] 13+ messages in thread
* [JGIT PATCH 2/5] Make RevObject.getType implementations final 2009-03-13 2:07 ` [JGIT PATCH 1/5] Show critical flags in debug toString() descriptions of rev queues Shawn O. Pearce @ 2009-03-13 2:07 ` Shawn O. Pearce 2009-03-13 2:07 ` [JGIT PATCH 3/5] Remove the horribly stupid RevSort.START_ORDER Shawn O. Pearce 0 siblings, 1 reply; 13+ messages in thread From: Shawn O. Pearce @ 2009-03-13 2:07 UTC (permalink / raw) To: Robin Rosenberg; +Cc: git These methods should never be overridden once defined by the base class of RevCommit, RevTree, RevBlob or RevTag. An override is only going to provide confusion to calls who rely upon the return value to know if a downcast is safe. Signed-off-by: Shawn O. Pearce <spearce@spearce.org> --- .../src/org/spearce/jgit/revwalk/RevBlob.java | 2 +- .../src/org/spearce/jgit/revwalk/RevCommit.java | 3 ++- .../src/org/spearce/jgit/revwalk/RevObject.java | 1 + .../src/org/spearce/jgit/revwalk/RevTag.java | 2 +- .../src/org/spearce/jgit/revwalk/RevTree.java | 2 +- 5 files changed, 6 insertions(+), 4 deletions(-) diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevBlob.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevBlob.java index 66cdc02..cf241cf 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevBlob.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevBlob.java @@ -58,7 +58,7 @@ void parse(final RevWalk walk) { } @Override - public int getType() { + public final int getType() { return Constants.OBJ_BLOB; } } diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevCommit.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevCommit.java index 1b25fce..2a59ec4 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevCommit.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevCommit.java @@ -139,7 +139,7 @@ else if (nParents == 1) { } @Override - public int getType() { + public final int getType() { return Constants.OBJ_COMMIT; } @@ -393,6 +393,7 @@ public void dispose() { public String toString() { final StringBuilder s = new StringBuilder(); s.append(Constants.typeString(getType())); + s.append(' '); s.append(name()); s.append(' '); s.append(commitTime); diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevObject.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevObject.java index 7dadb7b..8c7cc23 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevObject.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevObject.java @@ -172,6 +172,7 @@ public void dispose() { public String toString() { final StringBuilder s = new StringBuilder(); s.append(Constants.typeString(getType())); + s.append(' '); s.append(name()); s.append(' '); appendCoreFlags(s); diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevTag.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevTag.java index aba8744..cace82d 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevTag.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevTag.java @@ -99,7 +99,7 @@ void parseCanonical(final RevWalk walk, final byte[] rawTag) } @Override - public int getType() { + public final int getType() { return Constants.OBJ_TAG; } diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevTree.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevTree.java index e1cd4b5..4d767e4 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevTree.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevTree.java @@ -58,7 +58,7 @@ void parse(final RevWalk walk) { } @Override - public int getType() { + public final int getType() { return Constants.OBJ_TREE; } } -- 1.6.2.288.gc3f22 ^ permalink raw reply related [flat|nested] 13+ messages in thread
* [JGIT PATCH 3/5] Remove the horribly stupid RevSort.START_ORDER 2009-03-13 2:07 ` [JGIT PATCH 2/5] Make RevObject.getType implementations final Shawn O. Pearce @ 2009-03-13 2:07 ` Shawn O. Pearce 2009-03-13 2:07 ` [JGIT PATCH 4/5] Fix RevWalk with Linus Torvald's occasional bad commit date hack Shawn O. Pearce 0 siblings, 1 reply; 13+ messages in thread From: Shawn O. Pearce @ 2009-03-13 2:07 UTC (permalink / raw) To: Robin Rosenberg; +Cc: git I must have been on crack the day I wrote 3b27268f49 ("Allow RevWalk users to ask for FIFO style ordering"). Its a really bad idea. Applications can get themselves into a situation where they process one branch long before another, and then abort too early, before all commits have been correctly flagged UNINTERESTING. For example, given the graph: Z-A------------B | / | --------- \ / Q-R-S-T-U-V If B is "interesting" and A,V are UNINTERESTING, without forcing the commit timestamp ordering in the pending queue we wind up processing all of B-Z, producing R,Q as "interesting" output in the process, and terminate before S can even be parsed. Consequently we never push the UNINTERESTING flag down onto R, and R,Q produced when they shouldn't. We now require that the pending queue use a DateRevQueue instead of the FIFORevQueue, so that in the above graph S must be parsed before we can even consider R or A, even though R,A were reached earlier. This of course still assumes there is no clock skew between S and R. The next commit will address some limited clock skew issues. Signed-off-by: Shawn O. Pearce <spearce@spearce.org> --- .../org/spearce/jgit/revwalk/PendingGenerator.java | 8 +++----- .../src/org/spearce/jgit/revwalk/RevSort.java | 11 ----------- .../src/org/spearce/jgit/revwalk/RevWalk.java | 6 +++--- .../org/spearce/jgit/revwalk/StartGenerator.java | 8 ++------ 4 files changed, 8 insertions(+), 25 deletions(-) diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java index 25b2966..144e909 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java @@ -62,7 +62,7 @@ private final RevWalk walker; - private final AbstractRevQueue pending; + private final DateRevQueue pending; private final RevFilter filter; @@ -70,7 +70,7 @@ boolean canDispose; - PendingGenerator(final RevWalk w, final AbstractRevQueue p, + PendingGenerator(final RevWalk w, final DateRevQueue p, final RevFilter f, final int out) { walker = w; pending = p; @@ -81,9 +81,7 @@ PendingGenerator(final RevWalk w, final AbstractRevQueue p, @Override int outputType() { - if (pending instanceof DateRevQueue) - return output | SORT_COMMIT_TIME_DESC; - return output; + return output | SORT_COMMIT_TIME_DESC; } @Override diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevSort.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevSort.java index b0a03ad..8c3eaed 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevSort.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevSort.java @@ -49,17 +49,6 @@ NONE, /** - * Maintain the order commits were marked as starting points. - * <p> - * This strategy is largely a FIFO strategy; commits are enumerated in the - * order they were added to the RevWalk by the application. Parents not yet - * visited are added behind all commits already enqueued for visiting. - * <p> - * This strategy should not be combined with {@link #COMMIT_TIME_DESC}. - */ - START_ORDER, - - /** * Sort by commit time, descending (newest first, oldest last). * <p> * This strategy can be combined with {@link #TOPO}. diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java index c8ec458..316f722 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java @@ -187,7 +187,7 @@ public RevWalk(final Repository repo) { idBuffer = new MutableObjectId(); objects = new ObjectIdSubclassMap<RevObject>(); roots = new ArrayList<RevCommit>(); - queue = new FIFORevQueue(); + queue = new DateRevQueue(); pending = new StartGenerator(this); sorting = EnumSet.of(RevSort.NONE); filter = RevFilter.ALL; @@ -915,7 +915,7 @@ protected void reset(int retainFlags) { curs.release(); roots.clear(); - queue = new FIFORevQueue(); + queue = new DateRevQueue(); pending = new StartGenerator(this); } @@ -934,7 +934,7 @@ public void dispose() { objects.clear(); curs.release(); roots.clear(); - queue = new FIFORevQueue(); + queue = new DateRevQueue(); pending = new StartGenerator(this); } diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java index 1b7947f..bf7067a 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java @@ -108,11 +108,7 @@ RevCommit next() throws MissingObjectException, } int pendingOutputType = 0; - if (walker.hasRevSort(RevSort.START_ORDER) - && !(q instanceof FIFORevQueue)) - q = new FIFORevQueue(q); - if (walker.hasRevSort(RevSort.COMMIT_TIME_DESC) - && !(q instanceof DateRevQueue)) + if (!(q instanceof DateRevQueue)) q = new DateRevQueue(q); if (tf != TreeFilter.ALL) { rf = AndRevFilter.create(rf, new RewriteTreeFilter(w, tf)); @@ -120,7 +116,7 @@ RevCommit next() throws MissingObjectException, } walker.queue = q; - g = new PendingGenerator(w, q, rf, pendingOutputType); + g = new PendingGenerator(w, (DateRevQueue) q, rf, pendingOutputType); if (boundary) { // Because the boundary generator may produce uninteresting -- 1.6.2.288.gc3f22 ^ permalink raw reply related [flat|nested] 13+ messages in thread
* [JGIT PATCH 4/5] Fix RevWalk with Linus Torvald's occasional bad commit date hack 2009-03-13 2:07 ` [JGIT PATCH 3/5] Remove the horribly stupid RevSort.START_ORDER Shawn O. Pearce @ 2009-03-13 2:07 ` Shawn O. Pearce 2009-03-13 2:07 ` [JGIT PATCH 5/5] Avoid incorrect output of UNINTERESTING commits when clock skew occurs Shawn O. Pearce 2009-03-14 0:54 ` [JGIT PATCH 4/5 v2] Fix RevWalk with Linus Torvald's occasional bad commit date hack Shawn O. Pearce 0 siblings, 2 replies; 13+ messages in thread From: Shawn O. Pearce @ 2009-03-13 2:07 UTC (permalink / raw) To: Robin Rosenberg; +Cc: git In git-core commit 7d004199d134c9d465e013064f72dbc04507f6c0 Linus describes a hack he created to improve the handling of cases where commit dates are out of order, such as a child commit having a date older than its parent. These cases can show up when there is bad imported data, or significant clock skew between distributed peers. The original git-core bug report identified a failure in: git rev-list A..B C where commits contained in both A and B were reported, due to out of order commit dates. We keep running until the most recent commit in the pending queue is more recent than the last commit sent to the caller. If the pending queue suddenly goes "backwards" due to one of our parent's having a more recent commit date, this new check ensures we will keep processing the graph until we see a more consistent cut. We process an extra OVER_SCAN commits after we decide that all remaining commits are UNINTERESTING. Processing these extra commits ensures flags are carried back further in the graph, increasing the chances that we correctly mark relevant nodes. As a result of this hack, we may produce a commit to our caller, but then later mark it UNINTERESTING if we discover date skew. To handle such cases, callers could buffer produced commits and filter out those that are UNINTERESTING, but this somewhat costly and may not always be necessary. Signed-off-by: Shawn O. Pearce <spearce@spearce.org> --- .../org/spearce/jgit/revwalk/PendingGenerator.java | 51 ++++++++++++++++++-- 1 files changed, 47 insertions(+), 4 deletions(-) diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java index 144e909..cd24e8f 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java @@ -42,6 +42,7 @@ import org.spearce.jgit.errors.IncorrectObjectTypeException; import org.spearce.jgit.errors.MissingObjectException; import org.spearce.jgit.errors.StopWalkException; +import org.spearce.jgit.lib.ObjectId; import org.spearce.jgit.revwalk.filter.RevFilter; /** @@ -60,6 +61,24 @@ private static final int UNINTERESTING = RevWalk.UNINTERESTING; + /** + * Number of additional commits to scan after we think we are done. + * <p> + * This small buffer of commits is scanned to ensure we didn't miss anything + * as a result of clock skew when the commits were made. We need to set our + * constant to 1 additional commit due to the use of a pre-increment + * operator when accessing the value. + */ + private static final int OVER_SCAN = 5 + 1; + + /** A commit near the end of time, to initialize {@link #last} with. */ + private static final RevCommit INIT_LAST; + + static { + INIT_LAST = new RevCommit(ObjectId.zeroId()); + INIT_LAST.commitTime = Integer.MAX_VALUE; + } + private final RevWalk walker; private final DateRevQueue pending; @@ -68,6 +87,17 @@ private final int output; + /** Last commit produced to the caller from {@link #next()}. */ + private RevCommit last = INIT_LAST; + + /** + * Number of commits we have remaining in our over-scan allotment. + * <p> + * Only relevant if there are {@link #UNINTERESTING} commits in the + * {@link #pending} queue. + */ + private int overScan = OVER_SCAN; + boolean canDispose; PendingGenerator(final RevWalk w, final DateRevQueue p, @@ -112,14 +142,27 @@ RevCommit next() throws MissingObjectException, walker.carryFlagsImpl(c); if ((c.flags & UNINTERESTING) != 0) { - if (pending.everbodyHasFlag(UNINTERESTING)) - throw StopWalkException.INSTANCE; - c.dispose(); + if (pending.everbodyHasFlag(UNINTERESTING)) { + final RevCommit n = pending.peek(); + if (n != null && n.commitTime <= last.commitTime) { + // This is too close to call. The next commit we + // would pop is before the last one we produced. + // We have to keep going to ensure that we carry + // flags as much as necessary. + // + overScan = OVER_SCAN; + } else if (--overScan == 0) + throw StopWalkException.INSTANCE; + } else { + overScan = OVER_SCAN; + } + if (canDispose) + c.dispose(); continue; } if (produce) - return c; + return last = c; else if (canDispose) c.dispose(); } -- 1.6.2.288.gc3f22 ^ permalink raw reply related [flat|nested] 13+ messages in thread
* [JGIT PATCH 5/5] Avoid incorrect output of UNINTERESTING commits when clock skew occurs 2009-03-13 2:07 ` [JGIT PATCH 4/5] Fix RevWalk with Linus Torvald's occasional bad commit date hack Shawn O. Pearce @ 2009-03-13 2:07 ` Shawn O. Pearce 2009-03-14 0:54 ` [JGIT PATCH 4/5 v2] Fix RevWalk with Linus Torvald's occasional bad commit date hack Shawn O. Pearce 1 sibling, 0 replies; 13+ messages in thread From: Shawn O. Pearce @ 2009-03-13 2:07 UTC (permalink / raw) To: Robin Rosenberg; +Cc: git The prior commit added functionality to scan a few extra commits when we otherwise would have aborted due to everything left being colored UNINTERESTING. When that happens we may wind up coloring a commit that we already produced to the caller, giving the caller an incorrect result set. If we insert a fully buffered generator in the pipeline, such as that used for RevSort.TOPO or RevSort.REVERSE, we can easily filter these late-colored commits out before we show them to the application. But otherwise we delay the output by 6 commits, just long enough to give PendingGenerator a reasonable chance at getting the coloring right. This is only an approximation. It is still possible for commits to produce when they should be UNINTERESTING, such as if more than the OVER_SCAN limit had clock skew between two branches and the common merge base, even if we are fully buffering our output. Signed-off-by: Shawn O. Pearce <spearce@spearce.org> --- .../org/spearce/jgit/revwalk/DelayRevQueue.java | 92 ++++++++++++++++++++ .../jgit/revwalk/FixUninterestingGenerator.java | 77 ++++++++++++++++ .../org/spearce/jgit/revwalk/PendingGenerator.java | 2 +- .../org/spearce/jgit/revwalk/StartGenerator.java | 23 ++++- 4 files changed, 189 insertions(+), 5 deletions(-) create mode 100644 org.spearce.jgit/src/org/spearce/jgit/revwalk/DelayRevQueue.java create mode 100644 org.spearce.jgit/src/org/spearce/jgit/revwalk/FixUninterestingGenerator.java diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/DelayRevQueue.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/DelayRevQueue.java new file mode 100644 index 0000000..1eb7064 --- /dev/null +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/DelayRevQueue.java @@ -0,0 +1,92 @@ +/* + * Copyright (C) 2009, Google Inc. + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Git Development Community nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.spearce.jgit.revwalk; + +import java.io.IOException; + +import org.spearce.jgit.errors.IncorrectObjectTypeException; +import org.spearce.jgit.errors.MissingObjectException; + +/** + * Delays commits to be at least {@link PendingGenerator#OVER_SCAN} late. + * <p> + * This helps to "fix up" weird corner cases resulting from clock skew, by + * slowing down what we produce to the caller we get a better chance to ensure + * PendingGenerator reached back far enough in the graph to correctly mark + * commits {@link RevWalk#UNINTERESTING} if necessary. + * <p> + * This generator should appear before {@link FixUninterestingGenerator} if the + * lower level {@link #pending} isn't already fully buffered. + */ +final class DelayRevQueue extends Generator { + private static final int OVER_SCAN = PendingGenerator.OVER_SCAN; + + private final Generator pending; + + private final FIFORevQueue delay; + + private int size; + + DelayRevQueue(final Generator g) { + pending = g; + delay = new FIFORevQueue(); + } + + @Override + int outputType() { + return pending.outputType(); + } + + @Override + RevCommit next() throws MissingObjectException, + IncorrectObjectTypeException, IOException { + while (size < OVER_SCAN) { + final RevCommit c = pending.next(); + if (c == null) + break; + delay.add(c); + size++; + } + + final RevCommit c = delay.next(); + if (c == null) + return null; + size--; + return c; + } +} diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/FixUninterestingGenerator.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/FixUninterestingGenerator.java new file mode 100644 index 0000000..6a9ba61 --- /dev/null +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/FixUninterestingGenerator.java @@ -0,0 +1,77 @@ +/* + * Copyright (C) 2009, Google Inc. + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Git Development Community nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.spearce.jgit.revwalk; + +import java.io.IOException; + +import org.spearce.jgit.errors.IncorrectObjectTypeException; +import org.spearce.jgit.errors.MissingObjectException; + +/** + * Filters out commits marked {@link RevWalk#UNINTERESTING}. + * <p> + * This generator is only in front of another generator that has fully buffered + * commits, such that we are called only after the {@link PendingGenerator} has + * exhausted its input queue and given up. It skips over any uninteresting + * commits that may have leaked out of the PendingGenerator due to clock skew + * being detected in the commit objects. + */ +final class FixUninterestingGenerator extends Generator { + private final Generator pending; + + FixUninterestingGenerator(final Generator g) { + pending = g; + } + + @Override + int outputType() { + return pending.outputType(); + } + + @Override + RevCommit next() throws MissingObjectException, + IncorrectObjectTypeException, IOException { + for (;;) { + final RevCommit c = pending.next(); + if (c == null) + return null; + if ((c.flags & RevWalk.UNINTERESTING) == 0) + return c; + } + } +} diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java index cd24e8f..ebbb39f 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java @@ -69,7 +69,7 @@ * constant to 1 additional commit due to the use of a pre-increment * operator when accessing the value. */ - private static final int OVER_SCAN = 5 + 1; + static final int OVER_SCAN = 5 + 1; /** A commit near the end of time, to initialize {@link #last} with. */ private static final RevCommit INIT_LAST; diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java index bf7067a..3535250 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java @@ -90,6 +90,7 @@ RevCommit next() throws MissingObjectException, return mbg.next(); } + final boolean uninteresting = q.anybodyHasFlag(RevWalk.UNINTERESTING); boolean boundary = walker.hasRevSort(RevSort.BOUNDARY); if (!boundary && walker instanceof ObjectWalk) { @@ -99,7 +100,7 @@ RevCommit next() throws MissingObjectException, // boundary = true; } - if (boundary && !q.anybodyHasFlag(RevWalk.UNINTERESTING)) { + if (boundary && !uninteresting) { // If we were not fed uninteresting commits we will never // construct a boundary. There is no reason to include the // extra overhead associated with that in our pipeline. @@ -107,16 +108,19 @@ RevCommit next() throws MissingObjectException, boundary = false; } + final DateRevQueue pending; int pendingOutputType = 0; - if (!(q instanceof DateRevQueue)) - q = new DateRevQueue(q); + if (q instanceof DateRevQueue) + pending = (DateRevQueue)q; + else + pending = new DateRevQueue(q); if (tf != TreeFilter.ALL) { rf = AndRevFilter.create(rf, new RewriteTreeFilter(w, tf)); pendingOutputType |= HAS_REWRITE | NEEDS_REWRITE; } walker.queue = q; - g = new PendingGenerator(w, (DateRevQueue) q, rf, pendingOutputType); + g = new PendingGenerator(w, pending, rf, pendingOutputType); if (boundary) { // Because the boundary generator may produce uninteresting @@ -143,6 +147,17 @@ RevCommit next() throws MissingObjectException, g = new LIFORevQueue(g); if (boundary) g = new BoundaryGenerator(w, g); + else if (uninteresting) { + // Try to protect ourselves from uninteresting commits producing + // due to clock skew in the commit time stamps. Delay such that + // we have a chance at coloring enough of the graph correctly, + // and then strip any UNINTERESTING nodes that may have leaked + // through early. + // + if (pending.peek() != null) + g = new DelayRevQueue(g); + g = new FixUninterestingGenerator(g); + } w.pending = g; return g.next(); -- 1.6.2.288.gc3f22 ^ permalink raw reply related [flat|nested] 13+ messages in thread
* [JGIT PATCH 4/5 v2] Fix RevWalk with Linus Torvald's occasional bad commit date hack 2009-03-13 2:07 ` [JGIT PATCH 4/5] Fix RevWalk with Linus Torvald's occasional bad commit date hack Shawn O. Pearce 2009-03-13 2:07 ` [JGIT PATCH 5/5] Avoid incorrect output of UNINTERESTING commits when clock skew occurs Shawn O. Pearce @ 2009-03-14 0:54 ` Shawn O. Pearce 1 sibling, 0 replies; 13+ messages in thread From: Shawn O. Pearce @ 2009-03-14 0:54 UTC (permalink / raw) To: Robin Rosenberg; +Cc: git In git-core commit 7d004199d134c9d465e013064f72dbc04507f6c0 Linus describes a hack he created to improve the handling of cases where commit dates are out of order, such as a child commit having a date older than its parent. These cases can show up when there is bad imported data, or significant clock skew between distributed peers. The original git-core bug report identified a failure in: git rev-list A..B C where commits contained in both A and B were reported, due to out of order commit dates. We keep running until the most recent commit in the pending queue is more recent than the last commit sent to the caller. If the pending queue suddenly goes "backwards" due to one of our parent's having a more recent commit date, this new check ensures we will keep processing the graph until we see a more consistent cut. We process an extra OVER_SCAN commits after we decide that all remaining commits are UNINTERESTING. Processing these extra commits ensures flags are carried back further in the graph, increasing the chances that we correctly mark relevant nodes. As a result of this hack, we may produce a commit to our caller, but then later mark it UNINTERESTING if we discover date skew. To handle such cases, callers could buffer produced commits and filter out those that are UNINTERESTING, but this somewhat costly and may not always be necessary. Signed-off-by: Shawn O. Pearce <spearce@spearce.org> --- This version inverts the "n.commitTime <= last.commitTime", I confused myself and wrote it backwards. The next patch I'm going to send with the tests has a test for this condition, to verify its correct. .../org/spearce/jgit/revwalk/PendingGenerator.java | 51 ++++++++++++++++++-- 1 files changed, 47 insertions(+), 4 deletions(-) diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java index 144e909..4e24431 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java @@ -42,6 +42,7 @@ import org.spearce.jgit.errors.IncorrectObjectTypeException; import org.spearce.jgit.errors.MissingObjectException; import org.spearce.jgit.errors.StopWalkException; +import org.spearce.jgit.lib.ObjectId; import org.spearce.jgit.revwalk.filter.RevFilter; /** @@ -60,6 +61,24 @@ private static final int UNINTERESTING = RevWalk.UNINTERESTING; + /** + * Number of additional commits to scan after we think we are done. + * <p> + * This small buffer of commits is scanned to ensure we didn't miss anything + * as a result of clock skew when the commits were made. We need to set our + * constant to 1 additional commit due to the use of a pre-increment + * operator when accessing the value. + */ + private static final int OVER_SCAN = 5 + 1; + + /** A commit near the end of time, to initialize {@link #last} with. */ + private static final RevCommit INIT_LAST; + + static { + INIT_LAST = new RevCommit(ObjectId.zeroId()); + INIT_LAST.commitTime = Integer.MAX_VALUE; + } + private final RevWalk walker; private final DateRevQueue pending; @@ -68,6 +87,17 @@ private final int output; + /** Last commit produced to the caller from {@link #next()}. */ + private RevCommit last = INIT_LAST; + + /** + * Number of commits we have remaining in our over-scan allotment. + * <p> + * Only relevant if there are {@link #UNINTERESTING} commits in the + * {@link #pending} queue. + */ + private int overScan = OVER_SCAN; + boolean canDispose; PendingGenerator(final RevWalk w, final DateRevQueue p, @@ -112,14 +142,27 @@ RevCommit next() throws MissingObjectException, walker.carryFlagsImpl(c); if ((c.flags & UNINTERESTING) != 0) { - if (pending.everbodyHasFlag(UNINTERESTING)) - throw StopWalkException.INSTANCE; - c.dispose(); + if (pending.everbodyHasFlag(UNINTERESTING)) { + final RevCommit n = pending.peek(); + if (n != null && n.commitTime >= last.commitTime) { + // This is too close to call. The next commit we + // would pop is dated after the last one produced. + // We have to keep going to ensure that we carry + // flags as much as necessary. + // + overScan = OVER_SCAN; + } else if (--overScan == 0) + throw StopWalkException.INSTANCE; + } else { + overScan = OVER_SCAN; + } + if (canDispose) + c.dispose(); continue; } if (produce) - return c; + return last = c; else if (canDispose) c.dispose(); } -- 1.6.2.288.gc3f22 ^ permalink raw reply related [flat|nested] 13+ messages in thread
* Re: [JGIT PATCH 0/5] RevWalk fixes for UNINTERESTING 2009-03-13 2:07 [JGIT PATCH 0/5] RevWalk fixes for UNINTERESTING Shawn O. Pearce 2009-03-13 2:07 ` [JGIT PATCH 1/5] Show critical flags in debug toString() descriptions of rev queues Shawn O. Pearce @ 2009-03-13 20:00 ` Robin Rosenberg 2009-03-13 22:39 ` [JGIT PATCH 0/6] Add tests for RevWalk and its supporting code Shawn O. Pearce 1 sibling, 1 reply; 13+ messages in thread From: Robin Rosenberg @ 2009-03-13 20:00 UTC (permalink / raw) To: Shawn O. Pearce; +Cc: git fredag 13 mars 2009 03:07:37 skrev "Shawn O. Pearce" <spearce@spearce.org>: > Today I uncovered some ugly cases with "jgit rev-list B ^A", where > some commits reachable from A were still being output, even though > we asked that they be excluded. How about a test suite to prove this is better than before? -- robin ^ permalink raw reply [flat|nested] 13+ messages in thread
* [JGIT PATCH 0/6] Add tests for RevWalk and its supporting code 2009-03-13 20:00 ` [JGIT PATCH 0/5] RevWalk fixes for UNINTERESTING Robin Rosenberg @ 2009-03-13 22:39 ` Shawn O. Pearce 2009-03-14 0:13 ` Shawn O. Pearce 0 siblings, 1 reply; 13+ messages in thread From: Shawn O. Pearce @ 2009-03-13 22:39 UTC (permalink / raw) To: Robin Rosenberg; +Cc: git These new tests cover some of the common cases we see with using a RevWalk, and increase our code coverage in this critical area of the JGit library. Signed-off-by: Shawn O. Pearce <spearce@spearce.org> --- Robin Rosenberg <robin.rosenberg.lists@dewire.com> wrote: > fredag 13 mars 2009 03:07:37 skrev "Shawn O. Pearce" <spearce@spearce.org>: > > Today I uncovered some ugly cases with "jgit rev-list B ^A", where > > some commits reachable from A were still being output, even though > > we asked that they be excluded. > > How about a test suite to prove this is better than before? Its better. :-) These tests don't pass before the series. They pass after. .../org/spearce/jgit/revwalk/RevFlagSetTest.java | 131 +++++++++++ .../org/spearce/jgit/revwalk/RevWalkCullTest.java | 75 +++++++ .../spearce/jgit/revwalk/RevWalkFilterTest.java | 233 ++++++++++++++++++++ .../spearce/jgit/revwalk/RevWalkMergeBaseTest.java | 117 ++++++++++ .../org/spearce/jgit/revwalk/RevWalkSortTest.java | 164 ++++++++++++++ .../org/spearce/jgit/revwalk/RevWalkTestCase.java | 102 +++++++++ 6 files changed, 822 insertions(+), 0 deletions(-) create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevFlagSetTest.java create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkCullTest.java create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkFilterTest.java create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkMergeBaseTest.java create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkSortTest.java create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkTestCase.java diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevFlagSetTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevFlagSetTest.java new file mode 100644 index 0000000..76f3cbb --- /dev/null +++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevFlagSetTest.java @@ -0,0 +1,131 @@ +/* + * Copyright (C) 2008, Google Inc. + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Git Development Community nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.spearce.jgit.revwalk; + +import java.util.Arrays; +import java.util.Iterator; + +public class RevFlagSetTest extends RevWalkTestCase { + public void testEmpty() { + final RevFlagSet set = new RevFlagSet(); + assertEquals(0, set.mask); + assertEquals(0, set.size()); + assertNotNull(set.iterator()); + assertFalse(set.iterator().hasNext()); + } + + public void testAddOne() { + final String flagName = "flag"; + final RevFlag flag = rw.newFlag(flagName); + assertTrue(0 != flag.mask); + assertSame(flagName, flag.name); + + final RevFlagSet set = new RevFlagSet(); + assertTrue(set.add(flag)); + assertFalse(set.add(flag)); + assertEquals(flag.mask, set.mask); + assertEquals(1, set.size()); + final Iterator<RevFlag> i = set.iterator(); + assertTrue(i.hasNext()); + assertSame(flag, i.next()); + assertFalse(i.hasNext()); + } + + public void testAddTwo() { + final RevFlag flag1 = rw.newFlag("flag_1"); + final RevFlag flag2 = rw.newFlag("flag_2"); + assertTrue((flag1.mask & flag2.mask) == 0); + + final RevFlagSet set = new RevFlagSet(); + assertTrue(set.add(flag1)); + assertTrue(set.add(flag2)); + assertEquals(flag1.mask | flag2.mask, set.mask); + assertEquals(2, set.size()); + } + + public void testContainsAll() { + final RevFlag flag1 = rw.newFlag("flag_1"); + final RevFlag flag2 = rw.newFlag("flag_2"); + final RevFlagSet set1 = new RevFlagSet(); + assertTrue(set1.add(flag1)); + assertTrue(set1.add(flag2)); + + assertTrue(set1.containsAll(set1)); + assertTrue(set1.containsAll(Arrays + .asList(new RevFlag[] { flag1, flag2 }))); + + final RevFlagSet set2 = new RevFlagSet(); + set2.add(rw.newFlag("flag_3")); + assertFalse(set1.containsAll(set2)); + } + + public void testEquals() { + final RevFlag flag1 = rw.newFlag("flag_1"); + final RevFlag flag2 = rw.newFlag("flag_2"); + final RevFlagSet set = new RevFlagSet(); + assertTrue(set.add(flag1)); + assertTrue(set.add(flag2)); + + assertTrue(new RevFlagSet(set).equals(set)); + assertTrue(new RevFlagSet(Arrays.asList(new RevFlag[] { flag1, flag2 })) + .equals(set)); + } + + public void testRemove() { + final RevFlag flag1 = rw.newFlag("flag_1"); + final RevFlag flag2 = rw.newFlag("flag_2"); + final RevFlagSet set = new RevFlagSet(); + assertTrue(set.add(flag1)); + assertTrue(set.add(flag2)); + + assertTrue(set.remove(flag1)); + assertFalse(set.remove(flag1)); + assertEquals(flag2.mask, set.mask); + assertFalse(set.contains(flag1)); + } + + public void testContains() { + final RevFlag flag1 = rw.newFlag("flag_1"); + final RevFlag flag2 = rw.newFlag("flag_2"); + final RevFlagSet set = new RevFlagSet(); + set.add(flag1); + assertTrue(set.contains(flag1)); + assertFalse(set.contains(flag2)); + assertFalse(set.contains("bob")); + } +} diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkCullTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkCullTest.java new file mode 100644 index 0000000..ad78b16 --- /dev/null +++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkCullTest.java @@ -0,0 +1,75 @@ +/* + * Copyright (C) 2008, Google Inc. + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Git Development Community nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.spearce.jgit.revwalk; + +import org.spearce.jgit.lib.ObjectId; + +public class RevWalkCullTest extends RevWalkTestCase { + public void testProperlyCullAllAncestors1() throws Exception { + // Credit goes to Junio C Hamano <gitster@pobox.com> for this + // test case in git-core (t/t6009-rev-list-parent.sh) + // + // We induce a clock skew so two is dated before one. + // + final ObjectId a = commit(); + final ObjectId b = commit(-2400, a); + final ObjectId c = commit(b); + final ObjectId d = commit(c); + + markStart(a); + markUninteresting(d); + assertNull(rw.next()); + } + + public void testProperlyCullAllAncestors2() throws Exception { + // Despite clock skew on c1 being very old it should not + // produce, neither should a or b, or any part of that chain. + // + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c1 = commit(-5, b); + final ObjectId c2 = commit(10, b); + final ObjectId d = commit(c1, c2); + + markStart(d); + markUninteresting(c1); + assertCommit(d, rw.next()); + assertCommit(c2, rw.next()); + assertNull(rw.next()); + } +} diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkFilterTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkFilterTest.java new file mode 100644 index 0000000..cf2975d --- /dev/null +++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkFilterTest.java @@ -0,0 +1,233 @@ +/* + * Copyright (C) 2008, Google Inc. + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Git Development Community nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.spearce.jgit.revwalk; + +import java.io.IOException; + +import org.spearce.jgit.errors.IncorrectObjectTypeException; +import org.spearce.jgit.errors.MissingObjectException; +import org.spearce.jgit.errors.StopWalkException; +import org.spearce.jgit.lib.ObjectId; +import org.spearce.jgit.revwalk.filter.AndRevFilter; +import org.spearce.jgit.revwalk.filter.NotRevFilter; +import org.spearce.jgit.revwalk.filter.OrRevFilter; +import org.spearce.jgit.revwalk.filter.RevFilter; + +public class RevWalkFilterTest extends RevWalkTestCase { + private static final MyAll MY_ALL = new MyAll(); + + public void testFilter_ALL() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(RevFilter.ALL); + markStart(c); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testFilter_Negate_ALL() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(RevFilter.ALL.negate()); + markStart(c); + assertNull(rw.next()); + } + + public void testFilter_NOT_ALL() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(NotRevFilter.create(RevFilter.ALL)); + markStart(c); + assertNull(rw.next()); + } + + public void testFilter_NONE() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(RevFilter.NONE); + markStart(c); + assertNull(rw.next()); + } + + public void testFilter_NOT_NONE() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(NotRevFilter.create(RevFilter.NONE)); + markStart(c); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testFilter_ALL_And_NONE() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(AndRevFilter.create(RevFilter.ALL, RevFilter.NONE)); + markStart(c); + assertNull(rw.next()); + } + + public void testFilter_NONE_And_ALL() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(AndRevFilter.create(RevFilter.NONE, RevFilter.ALL)); + markStart(c); + assertNull(rw.next()); + } + + public void testFilter_ALL_Or_NONE() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(OrRevFilter.create(RevFilter.ALL, RevFilter.NONE)); + markStart(c); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testFilter_NONE_Or_ALL() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(OrRevFilter.create(RevFilter.NONE, RevFilter.ALL)); + markStart(c); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testFilter_MY_ALL_And_NONE() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(AndRevFilter.create(MY_ALL, RevFilter.NONE)); + markStart(c); + assertNull(rw.next()); + } + + public void testFilter_NONE_And_MY_ALL() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(AndRevFilter.create(RevFilter.NONE, MY_ALL)); + markStart(c); + assertNull(rw.next()); + } + + public void testFilter_MY_ALL_Or_NONE() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(OrRevFilter.create(MY_ALL, RevFilter.NONE)); + markStart(c); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testFilter_NONE_Or_MY_ALL() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(OrRevFilter.create(RevFilter.NONE, MY_ALL)); + markStart(c); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testFilter_NO_MERGES() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c1 = commit(b); + final ObjectId c2 = commit(b); + final ObjectId d = commit(c1, c2); + final ObjectId e = commit(d); + + rw.setRevFilter(RevFilter.NO_MERGES); + markStart(e); + assertCommit(e, rw.next()); + assertCommit(c2, rw.next()); + assertCommit(c1, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + private static class MyAll extends RevFilter { + @Override + public RevFilter clone() { + return this; + } + + @Override + public boolean include(RevWalk walker, RevCommit cmit) + throws StopWalkException, MissingObjectException, + IncorrectObjectTypeException, IOException { + return true; + } + } +} diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkMergeBaseTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkMergeBaseTest.java new file mode 100644 index 0000000..b05e774 --- /dev/null +++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkMergeBaseTest.java @@ -0,0 +1,117 @@ +/* + * Copyright (C) 2008, Google Inc. + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Git Development Community nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.spearce.jgit.revwalk; + +import org.spearce.jgit.lib.ObjectId; +import org.spearce.jgit.revwalk.filter.RevFilter; + +public class RevWalkMergeBaseTest extends RevWalkTestCase { + public void testNone() throws Exception { + final ObjectId c1 = commit(commit(commit())); + final ObjectId c2 = commit(commit(commit())); + + rw.setRevFilter(RevFilter.MERGE_BASE); + markStart(c1); + markStart(c2); + assertNull(rw.next()); + } + + public void testSimple() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c1 = commit(commit(commit(commit(commit(b))))); + final ObjectId c2 = commit(commit(commit(commit(commit(b))))); + + rw.setRevFilter(RevFilter.MERGE_BASE); + markStart(c1); + markStart(c2); + assertCommit(b, rw.next()); + assertNull(rw.next()); + } + + public void testMultipleHeads_SameBase1() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c1 = commit(commit(commit(commit(commit(b))))); + final ObjectId c2 = commit(commit(commit(commit(commit(b))))); + final ObjectId c3 = commit(commit(commit(b))); + + rw.setRevFilter(RevFilter.MERGE_BASE); + markStart(c1); + markStart(c2); + markStart(c3); + assertCommit(b, rw.next()); + assertNull(rw.next()); + } + + public void testMultipleHeads_SameBase2() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + final ObjectId d1 = commit(commit(commit(commit(commit(b))))); + final ObjectId d2 = commit(commit(commit(commit(commit(c))))); + final ObjectId d3 = commit(commit(commit(c))); + + rw.setRevFilter(RevFilter.MERGE_BASE); + markStart(d1); + markStart(d2); + markStart(d3); + assertCommit(b, rw.next()); + assertNull(rw.next()); + } + + public void testCrissCross() throws Exception { + // See http://marc.info/?l=git&m=111463358500362&w=2 for a nice + // description of what this test is creating. We don't have a + // clean merge base for d,e as they each merged the parents b,c + // in different orders. + // + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(a); + final ObjectId d = commit(b, c); + final ObjectId e = commit(c, b); + + rw.setRevFilter(RevFilter.MERGE_BASE); + markStart(d); + markStart(e); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertNull(rw.next()); + } +} diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkSortTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkSortTest.java new file mode 100644 index 0000000..6f2eedc --- /dev/null +++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkSortTest.java @@ -0,0 +1,164 @@ +/* + * Copyright (C) 2008, Google Inc. + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Git Development Community nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.spearce.jgit.revwalk; + +import org.spearce.jgit.lib.ObjectId; + +public class RevWalkSortTest extends RevWalkTestCase { + public void testSort_Default() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(1, a); + final ObjectId c = commit(1, b); + final ObjectId d = commit(1, c); + + markStart(d); + assertCommit(d, rw.next()); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testSort_COMMIT_TIME_DESC() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + final ObjectId d = commit(c); + + rw.sort(RevSort.COMMIT_TIME_DESC); + markStart(d); + assertCommit(d, rw.next()); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testSort_REVERSE() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + final ObjectId d = commit(c); + + rw.sort(RevSort.REVERSE); + markStart(d); + assertCommit(a, rw.next()); + assertCommit(b, rw.next()); + assertCommit(c, rw.next()); + assertCommit(d, rw.next()); + assertNull(rw.next()); + } + + public void testSort_COMMIT_TIME_DESC_OutOfOrder1() throws Exception { + // Despite being out of order time-wise, a strand-of-pearls must + // still maintain topological order. + // + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(-5, b); + final ObjectId d = commit(10, c); + assertTrue(parse(a).getCommitTime() < parse(d).getCommitTime()); + assertTrue(parse(c).getCommitTime() < parse(b).getCommitTime()); + + rw.sort(RevSort.COMMIT_TIME_DESC); + markStart(d); + assertCommit(d, rw.next()); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testSort_COMMIT_TIME_DESC_OutOfOrder2() throws Exception { + // c1 is back dated before its parent. + // + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c1 = commit(-5, b); + final ObjectId c2 = commit(10, b); + final ObjectId d = commit(c1, c2); + + rw.sort(RevSort.COMMIT_TIME_DESC); + markStart(d); + assertCommit(d, rw.next()); + assertCommit(c2, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertCommit(c1, rw.next()); + assertNull(rw.next()); + } + + public void testSort_TOPO() throws Exception { + // c1 is back dated before its parent. + // + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c1 = commit(-5, b); + final ObjectId c2 = commit(10, b); + final ObjectId d = commit(c1, c2); + + rw.sort(RevSort.TOPO); + markStart(d); + assertCommit(d, rw.next()); + assertCommit(c2, rw.next()); + assertCommit(c1, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testSort_TOPO_REVERSE() throws Exception { + // c1 is back dated before its parent. + // + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c1 = commit(-5, b); + final ObjectId c2 = commit(10, b); + final ObjectId d = commit(c1, c2); + + rw.sort(RevSort.TOPO); + rw.sort(RevSort.REVERSE, true); + markStart(d); + assertCommit(a, rw.next()); + assertCommit(b, rw.next()); + assertCommit(c1, rw.next()); + assertCommit(c2, rw.next()); + assertCommit(d, rw.next()); + assertNull(rw.next()); + } +} diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkTestCase.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkTestCase.java new file mode 100644 index 0000000..bd696dd --- /dev/null +++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkTestCase.java @@ -0,0 +1,102 @@ +/* + * Copyright (C) 2008, Google Inc. + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Git Development Community nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.spearce.jgit.revwalk; + +import java.util.Date; + +import org.spearce.jgit.lib.Commit; +import org.spearce.jgit.lib.ObjectId; +import org.spearce.jgit.lib.ObjectWriter; +import org.spearce.jgit.lib.PersonIdent; +import org.spearce.jgit.lib.RepositoryTestCase; +import org.spearce.jgit.lib.Tree; + +/** Support for tests of the {@link RevWalk} class. */ +public abstract class RevWalkTestCase extends RepositoryTestCase { + protected ObjectWriter ow; + + protected ObjectId emptyTree; + + protected long nowTick; + + protected RevWalk rw; + + public void setUp() throws Exception { + super.setUp(); + ow = new ObjectWriter(db); + emptyTree = ow.writeTree(new Tree(db)); + nowTick = 1236977987000L; + rw = new RevWalk(db); + } + + protected void tick(final int secDelta) { + nowTick += secDelta * 1000L; + } + + protected ObjectId commit(final ObjectId... parents) throws Exception { + return commit(1, parents); + } + + protected ObjectId commit(final int secDelta, final ObjectId... parents) + throws Exception { + tick(secDelta); + final Commit c = new Commit(db); + c.setTreeId(emptyTree); + c.setParentIds(parents); + c.setAuthor(new PersonIdent(jauthor, new Date(nowTick))); + c.setCommitter(new PersonIdent(jcommitter, new Date(nowTick))); + c.setMessage(""); + return ow.writeCommit(c); + } + + protected RevCommit parse(final ObjectId commitId) throws Exception { + return rw.parseCommit(commitId); + } + + protected void markStart(final ObjectId commitId) throws Exception { + rw.markStart(parse(commitId)); + } + + protected void markUninteresting(final ObjectId commitId) throws Exception { + rw.markUninteresting(parse(commitId)); + } + + protected void assertCommit(final ObjectId commitId, final RevCommit commit) { + assertEquals(commitId.name(), commit != null ? commit.name() : null); + } +} -- 1.6.2.288.gc3f22 ^ permalink raw reply related [flat|nested] 13+ messages in thread
* Re: [JGIT PATCH 0/6] Add tests for RevWalk and its supporting code 2009-03-13 22:39 ` [JGIT PATCH 0/6] Add tests for RevWalk and its supporting code Shawn O. Pearce @ 2009-03-14 0:13 ` Shawn O. Pearce 2009-03-14 0:56 ` [JGIT PATCH 6/5 v2] " Shawn O. Pearce 0 siblings, 1 reply; 13+ messages in thread From: Shawn O. Pearce @ 2009-03-14 0:13 UTC (permalink / raw) To: Robin Rosenberg; +Cc: git "Shawn O. Pearce" <spearce@spearce.org> wrote: > These new tests cover some of the common cases we see with using a > RevWalk, and increase our code coverage in this critical area of > the JGit library. > > Signed-off-by: Shawn O. Pearce <spearce@spearce.org> > --- > Robin Rosenberg <robin.rosenberg.lists@dewire.com> wrote: > > fredag 13 mars 2009 03:07:37 skrev "Shawn O. Pearce" <spearce@spearce.org>: > > > Today I uncovered some ugly cases with "jgit rev-list B ^A", where > > > some commits reachable from A were still being output, even though > > > we asked that they be excluded. > > > > How about a test suite to prove this is better than before? > > Its better. :-) Its actually not better. Although the tests I'm replying to are right, there's another bug introduced by this series that they don't detect, but that shows up on the Linux kernel repository. I have yet to track down the full thing... but I know its busted. -- Shawn. ^ permalink raw reply [flat|nested] 13+ messages in thread
* [JGIT PATCH 6/5 v2] Add tests for RevWalk and its supporting code 2009-03-14 0:13 ` Shawn O. Pearce @ 2009-03-14 0:56 ` Shawn O. Pearce 2009-03-15 11:34 ` Robin Rosenberg 0 siblings, 1 reply; 13+ messages in thread From: Shawn O. Pearce @ 2009-03-14 0:56 UTC (permalink / raw) To: Robin Rosenberg; +Cc: git These new tests cover some of the common cases we see with using a RevWalk, and increase our code coverage in this critical area of the JGit library. Signed-off-by: Shawn O. Pearce <spearce@spearce.org> --- "Shawn O. Pearce" <spearce@spearce.org> wrote: > I have yet to track down the full thing... but I know its busted. This updated test patch includes a test for the bug I was talking about, and fixed with 4/5 v2. .../org/spearce/jgit/revwalk/RevFlagSetTest.java | 131 +++++++++++ .../org/spearce/jgit/revwalk/RevWalkCullTest.java | 96 ++++++++ .../spearce/jgit/revwalk/RevWalkFilterTest.java | 233 ++++++++++++++++++++ .../spearce/jgit/revwalk/RevWalkMergeBaseTest.java | 117 ++++++++++ .../org/spearce/jgit/revwalk/RevWalkSortTest.java | 164 ++++++++++++++ .../org/spearce/jgit/revwalk/RevWalkTestCase.java | 102 +++++++++ 6 files changed, 843 insertions(+), 0 deletions(-) create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevFlagSetTest.java create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkCullTest.java create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkFilterTest.java create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkMergeBaseTest.java create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkSortTest.java create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkTestCase.java diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevFlagSetTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevFlagSetTest.java new file mode 100644 index 0000000..76f3cbb --- /dev/null +++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevFlagSetTest.java @@ -0,0 +1,131 @@ +/* + * Copyright (C) 2008, Google Inc. + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Git Development Community nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.spearce.jgit.revwalk; + +import java.util.Arrays; +import java.util.Iterator; + +public class RevFlagSetTest extends RevWalkTestCase { + public void testEmpty() { + final RevFlagSet set = new RevFlagSet(); + assertEquals(0, set.mask); + assertEquals(0, set.size()); + assertNotNull(set.iterator()); + assertFalse(set.iterator().hasNext()); + } + + public void testAddOne() { + final String flagName = "flag"; + final RevFlag flag = rw.newFlag(flagName); + assertTrue(0 != flag.mask); + assertSame(flagName, flag.name); + + final RevFlagSet set = new RevFlagSet(); + assertTrue(set.add(flag)); + assertFalse(set.add(flag)); + assertEquals(flag.mask, set.mask); + assertEquals(1, set.size()); + final Iterator<RevFlag> i = set.iterator(); + assertTrue(i.hasNext()); + assertSame(flag, i.next()); + assertFalse(i.hasNext()); + } + + public void testAddTwo() { + final RevFlag flag1 = rw.newFlag("flag_1"); + final RevFlag flag2 = rw.newFlag("flag_2"); + assertTrue((flag1.mask & flag2.mask) == 0); + + final RevFlagSet set = new RevFlagSet(); + assertTrue(set.add(flag1)); + assertTrue(set.add(flag2)); + assertEquals(flag1.mask | flag2.mask, set.mask); + assertEquals(2, set.size()); + } + + public void testContainsAll() { + final RevFlag flag1 = rw.newFlag("flag_1"); + final RevFlag flag2 = rw.newFlag("flag_2"); + final RevFlagSet set1 = new RevFlagSet(); + assertTrue(set1.add(flag1)); + assertTrue(set1.add(flag2)); + + assertTrue(set1.containsAll(set1)); + assertTrue(set1.containsAll(Arrays + .asList(new RevFlag[] { flag1, flag2 }))); + + final RevFlagSet set2 = new RevFlagSet(); + set2.add(rw.newFlag("flag_3")); + assertFalse(set1.containsAll(set2)); + } + + public void testEquals() { + final RevFlag flag1 = rw.newFlag("flag_1"); + final RevFlag flag2 = rw.newFlag("flag_2"); + final RevFlagSet set = new RevFlagSet(); + assertTrue(set.add(flag1)); + assertTrue(set.add(flag2)); + + assertTrue(new RevFlagSet(set).equals(set)); + assertTrue(new RevFlagSet(Arrays.asList(new RevFlag[] { flag1, flag2 })) + .equals(set)); + } + + public void testRemove() { + final RevFlag flag1 = rw.newFlag("flag_1"); + final RevFlag flag2 = rw.newFlag("flag_2"); + final RevFlagSet set = new RevFlagSet(); + assertTrue(set.add(flag1)); + assertTrue(set.add(flag2)); + + assertTrue(set.remove(flag1)); + assertFalse(set.remove(flag1)); + assertEquals(flag2.mask, set.mask); + assertFalse(set.contains(flag1)); + } + + public void testContains() { + final RevFlag flag1 = rw.newFlag("flag_1"); + final RevFlag flag2 = rw.newFlag("flag_2"); + final RevFlagSet set = new RevFlagSet(); + set.add(flag1); + assertTrue(set.contains(flag1)); + assertFalse(set.contains(flag2)); + assertFalse(set.contains("bob")); + } +} diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkCullTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkCullTest.java new file mode 100644 index 0000000..93bd645 --- /dev/null +++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkCullTest.java @@ -0,0 +1,96 @@ +/* + * Copyright (C) 2008, Google Inc. + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Git Development Community nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.spearce.jgit.revwalk; + +import org.spearce.jgit.lib.ObjectId; + +public class RevWalkCullTest extends RevWalkTestCase { + public void testProperlyCullAllAncestors1() throws Exception { + // Credit goes to Junio C Hamano <gitster@pobox.com> for this + // test case in git-core (t/t6009-rev-list-parent.sh) + // + // We induce a clock skew so two is dated before one. + // + final ObjectId a = commit(); + final ObjectId b = commit(-2400, a); + final ObjectId c = commit(b); + final ObjectId d = commit(c); + + markStart(a); + markUninteresting(d); + assertNull(rw.next()); + } + + public void testProperlyCullAllAncestors2() throws Exception { + // Despite clock skew on c1 being very old it should not + // produce, neither should a or b, or any part of that chain. + // + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c1 = commit(-5, b); + final ObjectId c2 = commit(10, b); + final ObjectId d = commit(c1, c2); + + markStart(d); + markUninteresting(c1); + assertCommit(d, rw.next()); + assertCommit(c2, rw.next()); + assertNull(rw.next()); + } + + public void testProperlyCullAllAncestors_LongHistory() throws Exception { + final ObjectId a = commit(); + ObjectId b = commit(a); + for (int i = 0; i < 24; i++) { + b = commit(b); + if ((i & 2) == 0) + markUninteresting(b); + } + final ObjectId c = commit(b); + + markStart(c); + markUninteresting(b); + assertCommit(c, rw.next()); + assertNull(rw.next()); + + // We should have aborted before we got back so far that "a" + // would be parsed. Thus, its parents shouldn't be allocated. + // + assertNull(rw.lookupCommit(a).parents); + } +} diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkFilterTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkFilterTest.java new file mode 100644 index 0000000..cf2975d --- /dev/null +++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkFilterTest.java @@ -0,0 +1,233 @@ +/* + * Copyright (C) 2008, Google Inc. + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Git Development Community nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.spearce.jgit.revwalk; + +import java.io.IOException; + +import org.spearce.jgit.errors.IncorrectObjectTypeException; +import org.spearce.jgit.errors.MissingObjectException; +import org.spearce.jgit.errors.StopWalkException; +import org.spearce.jgit.lib.ObjectId; +import org.spearce.jgit.revwalk.filter.AndRevFilter; +import org.spearce.jgit.revwalk.filter.NotRevFilter; +import org.spearce.jgit.revwalk.filter.OrRevFilter; +import org.spearce.jgit.revwalk.filter.RevFilter; + +public class RevWalkFilterTest extends RevWalkTestCase { + private static final MyAll MY_ALL = new MyAll(); + + public void testFilter_ALL() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(RevFilter.ALL); + markStart(c); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testFilter_Negate_ALL() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(RevFilter.ALL.negate()); + markStart(c); + assertNull(rw.next()); + } + + public void testFilter_NOT_ALL() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(NotRevFilter.create(RevFilter.ALL)); + markStart(c); + assertNull(rw.next()); + } + + public void testFilter_NONE() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(RevFilter.NONE); + markStart(c); + assertNull(rw.next()); + } + + public void testFilter_NOT_NONE() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(NotRevFilter.create(RevFilter.NONE)); + markStart(c); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testFilter_ALL_And_NONE() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(AndRevFilter.create(RevFilter.ALL, RevFilter.NONE)); + markStart(c); + assertNull(rw.next()); + } + + public void testFilter_NONE_And_ALL() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(AndRevFilter.create(RevFilter.NONE, RevFilter.ALL)); + markStart(c); + assertNull(rw.next()); + } + + public void testFilter_ALL_Or_NONE() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(OrRevFilter.create(RevFilter.ALL, RevFilter.NONE)); + markStart(c); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testFilter_NONE_Or_ALL() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(OrRevFilter.create(RevFilter.NONE, RevFilter.ALL)); + markStart(c); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testFilter_MY_ALL_And_NONE() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(AndRevFilter.create(MY_ALL, RevFilter.NONE)); + markStart(c); + assertNull(rw.next()); + } + + public void testFilter_NONE_And_MY_ALL() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(AndRevFilter.create(RevFilter.NONE, MY_ALL)); + markStart(c); + assertNull(rw.next()); + } + + public void testFilter_MY_ALL_Or_NONE() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(OrRevFilter.create(MY_ALL, RevFilter.NONE)); + markStart(c); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testFilter_NONE_Or_MY_ALL() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + + rw.setRevFilter(OrRevFilter.create(RevFilter.NONE, MY_ALL)); + markStart(c); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testFilter_NO_MERGES() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c1 = commit(b); + final ObjectId c2 = commit(b); + final ObjectId d = commit(c1, c2); + final ObjectId e = commit(d); + + rw.setRevFilter(RevFilter.NO_MERGES); + markStart(e); + assertCommit(e, rw.next()); + assertCommit(c2, rw.next()); + assertCommit(c1, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + private static class MyAll extends RevFilter { + @Override + public RevFilter clone() { + return this; + } + + @Override + public boolean include(RevWalk walker, RevCommit cmit) + throws StopWalkException, MissingObjectException, + IncorrectObjectTypeException, IOException { + return true; + } + } +} diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkMergeBaseTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkMergeBaseTest.java new file mode 100644 index 0000000..b05e774 --- /dev/null +++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkMergeBaseTest.java @@ -0,0 +1,117 @@ +/* + * Copyright (C) 2008, Google Inc. + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Git Development Community nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.spearce.jgit.revwalk; + +import org.spearce.jgit.lib.ObjectId; +import org.spearce.jgit.revwalk.filter.RevFilter; + +public class RevWalkMergeBaseTest extends RevWalkTestCase { + public void testNone() throws Exception { + final ObjectId c1 = commit(commit(commit())); + final ObjectId c2 = commit(commit(commit())); + + rw.setRevFilter(RevFilter.MERGE_BASE); + markStart(c1); + markStart(c2); + assertNull(rw.next()); + } + + public void testSimple() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c1 = commit(commit(commit(commit(commit(b))))); + final ObjectId c2 = commit(commit(commit(commit(commit(b))))); + + rw.setRevFilter(RevFilter.MERGE_BASE); + markStart(c1); + markStart(c2); + assertCommit(b, rw.next()); + assertNull(rw.next()); + } + + public void testMultipleHeads_SameBase1() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c1 = commit(commit(commit(commit(commit(b))))); + final ObjectId c2 = commit(commit(commit(commit(commit(b))))); + final ObjectId c3 = commit(commit(commit(b))); + + rw.setRevFilter(RevFilter.MERGE_BASE); + markStart(c1); + markStart(c2); + markStart(c3); + assertCommit(b, rw.next()); + assertNull(rw.next()); + } + + public void testMultipleHeads_SameBase2() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + final ObjectId d1 = commit(commit(commit(commit(commit(b))))); + final ObjectId d2 = commit(commit(commit(commit(commit(c))))); + final ObjectId d3 = commit(commit(commit(c))); + + rw.setRevFilter(RevFilter.MERGE_BASE); + markStart(d1); + markStart(d2); + markStart(d3); + assertCommit(b, rw.next()); + assertNull(rw.next()); + } + + public void testCrissCross() throws Exception { + // See http://marc.info/?l=git&m=111463358500362&w=2 for a nice + // description of what this test is creating. We don't have a + // clean merge base for d,e as they each merged the parents b,c + // in different orders. + // + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(a); + final ObjectId d = commit(b, c); + final ObjectId e = commit(c, b); + + rw.setRevFilter(RevFilter.MERGE_BASE); + markStart(d); + markStart(e); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertNull(rw.next()); + } +} diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkSortTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkSortTest.java new file mode 100644 index 0000000..6f2eedc --- /dev/null +++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkSortTest.java @@ -0,0 +1,164 @@ +/* + * Copyright (C) 2008, Google Inc. + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Git Development Community nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.spearce.jgit.revwalk; + +import org.spearce.jgit.lib.ObjectId; + +public class RevWalkSortTest extends RevWalkTestCase { + public void testSort_Default() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(1, a); + final ObjectId c = commit(1, b); + final ObjectId d = commit(1, c); + + markStart(d); + assertCommit(d, rw.next()); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testSort_COMMIT_TIME_DESC() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + final ObjectId d = commit(c); + + rw.sort(RevSort.COMMIT_TIME_DESC); + markStart(d); + assertCommit(d, rw.next()); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testSort_REVERSE() throws Exception { + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(b); + final ObjectId d = commit(c); + + rw.sort(RevSort.REVERSE); + markStart(d); + assertCommit(a, rw.next()); + assertCommit(b, rw.next()); + assertCommit(c, rw.next()); + assertCommit(d, rw.next()); + assertNull(rw.next()); + } + + public void testSort_COMMIT_TIME_DESC_OutOfOrder1() throws Exception { + // Despite being out of order time-wise, a strand-of-pearls must + // still maintain topological order. + // + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c = commit(-5, b); + final ObjectId d = commit(10, c); + assertTrue(parse(a).getCommitTime() < parse(d).getCommitTime()); + assertTrue(parse(c).getCommitTime() < parse(b).getCommitTime()); + + rw.sort(RevSort.COMMIT_TIME_DESC); + markStart(d); + assertCommit(d, rw.next()); + assertCommit(c, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testSort_COMMIT_TIME_DESC_OutOfOrder2() throws Exception { + // c1 is back dated before its parent. + // + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c1 = commit(-5, b); + final ObjectId c2 = commit(10, b); + final ObjectId d = commit(c1, c2); + + rw.sort(RevSort.COMMIT_TIME_DESC); + markStart(d); + assertCommit(d, rw.next()); + assertCommit(c2, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertCommit(c1, rw.next()); + assertNull(rw.next()); + } + + public void testSort_TOPO() throws Exception { + // c1 is back dated before its parent. + // + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c1 = commit(-5, b); + final ObjectId c2 = commit(10, b); + final ObjectId d = commit(c1, c2); + + rw.sort(RevSort.TOPO); + markStart(d); + assertCommit(d, rw.next()); + assertCommit(c2, rw.next()); + assertCommit(c1, rw.next()); + assertCommit(b, rw.next()); + assertCommit(a, rw.next()); + assertNull(rw.next()); + } + + public void testSort_TOPO_REVERSE() throws Exception { + // c1 is back dated before its parent. + // + final ObjectId a = commit(); + final ObjectId b = commit(a); + final ObjectId c1 = commit(-5, b); + final ObjectId c2 = commit(10, b); + final ObjectId d = commit(c1, c2); + + rw.sort(RevSort.TOPO); + rw.sort(RevSort.REVERSE, true); + markStart(d); + assertCommit(a, rw.next()); + assertCommit(b, rw.next()); + assertCommit(c1, rw.next()); + assertCommit(c2, rw.next()); + assertCommit(d, rw.next()); + assertNull(rw.next()); + } +} diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkTestCase.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkTestCase.java new file mode 100644 index 0000000..bd696dd --- /dev/null +++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkTestCase.java @@ -0,0 +1,102 @@ +/* + * Copyright (C) 2008, Google Inc. + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Git Development Community nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.spearce.jgit.revwalk; + +import java.util.Date; + +import org.spearce.jgit.lib.Commit; +import org.spearce.jgit.lib.ObjectId; +import org.spearce.jgit.lib.ObjectWriter; +import org.spearce.jgit.lib.PersonIdent; +import org.spearce.jgit.lib.RepositoryTestCase; +import org.spearce.jgit.lib.Tree; + +/** Support for tests of the {@link RevWalk} class. */ +public abstract class RevWalkTestCase extends RepositoryTestCase { + protected ObjectWriter ow; + + protected ObjectId emptyTree; + + protected long nowTick; + + protected RevWalk rw; + + public void setUp() throws Exception { + super.setUp(); + ow = new ObjectWriter(db); + emptyTree = ow.writeTree(new Tree(db)); + nowTick = 1236977987000L; + rw = new RevWalk(db); + } + + protected void tick(final int secDelta) { + nowTick += secDelta * 1000L; + } + + protected ObjectId commit(final ObjectId... parents) throws Exception { + return commit(1, parents); + } + + protected ObjectId commit(final int secDelta, final ObjectId... parents) + throws Exception { + tick(secDelta); + final Commit c = new Commit(db); + c.setTreeId(emptyTree); + c.setParentIds(parents); + c.setAuthor(new PersonIdent(jauthor, new Date(nowTick))); + c.setCommitter(new PersonIdent(jcommitter, new Date(nowTick))); + c.setMessage(""); + return ow.writeCommit(c); + } + + protected RevCommit parse(final ObjectId commitId) throws Exception { + return rw.parseCommit(commitId); + } + + protected void markStart(final ObjectId commitId) throws Exception { + rw.markStart(parse(commitId)); + } + + protected void markUninteresting(final ObjectId commitId) throws Exception { + rw.markUninteresting(parse(commitId)); + } + + protected void assertCommit(final ObjectId commitId, final RevCommit commit) { + assertEquals(commitId.name(), commit != null ? commit.name() : null); + } +} -- 1.6.2.288.gc3f22 ^ permalink raw reply related [flat|nested] 13+ messages in thread
* Re: [JGIT PATCH 6/5 v2] Add tests for RevWalk and its supporting code 2009-03-14 0:56 ` [JGIT PATCH 6/5 v2] " Shawn O. Pearce @ 2009-03-15 11:34 ` Robin Rosenberg 2009-03-16 14:33 ` Shawn O. Pearce 0 siblings, 1 reply; 13+ messages in thread From: Robin Rosenberg @ 2009-03-15 11:34 UTC (permalink / raw) To: Shawn O. Pearce; +Cc: git A few /09 interesting/ places in StartGenerator are not covered by the tests. if (q instanceof DateRevQueue) pending = (DateRevQueue)q; else --> pending = new DateRevQueue(q); and if (tf != TreeFilter.ALL) { --> rf = AndRevFilter.create(rf, new RewriteTreeFilter(w, tf)); --> pendingOutputType |= HAS_REWRITE | NEEDS_REWRITE; } PendingGenerator if (n != null && n.commitTime >= last.commitTime) { // This is too close to call. The next commit we // would pop is dated after the last one produced. // We have to keep going to ensure that we carry // flags as much as necessary. // --> overScan = OVER_SCAN; I'll merge it anyway since this is still a huge improvement compared to the previous state. -- robin ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [JGIT PATCH 6/5 v2] Add tests for RevWalk and its supporting code 2009-03-15 11:34 ` Robin Rosenberg @ 2009-03-16 14:33 ` Shawn O. Pearce 0 siblings, 0 replies; 13+ messages in thread From: Shawn O. Pearce @ 2009-03-16 14:33 UTC (permalink / raw) To: Robin Rosenberg; +Cc: git Robin Rosenberg <robin.rosenberg.lists@dewire.com> wrote: > > A few /09 interesting/ places in StartGenerator are not covered by the tests. > > if (q instanceof DateRevQueue) > pending = (DateRevQueue)q; > else > --> pending = new DateRevQueue(q); This one is difficult to test. Near as I can tell from the code in the revwalk package, it never happens. But if we did get here with a non date rev queue, DateRevQueue()'s constructor can copy the data from q over to one with no risk. Perhaps just test this constructor in isolation? > and > > if (tf != TreeFilter.ALL) { > --> rf = AndRevFilter.create(rf, new RewriteTreeFilter(w, tf)); > --> pendingOutputType |= HAS_REWRITE | NEEDS_REWRITE; > } That says we have no tests on the path filter code. Adding one is likely to identify at least one bug. Clearly we need additional tests on the path filter sections. And it isn't just for this one little conditional; the entire RewriteTreeFilter and RewriteGenerator are untested right now. I can work on adding more test coverage here, but its not in the critical path for me at day-job right now. The other problems I tried to address in this series were. So its lower in my queue so-to-speak. But I'll see what I can do in the near future to write additional tests for this area of the revwalk package. > PendingGenerator > if (n != null && n.commitTime >= last.commitTime) { > // This is too close to call. The next commit we > // would pop is dated after the last one produced. > // We have to keep going to ensure that we carry > // flags as much as necessary. > // > --> overScan = OVER_SCAN; *sigh* We never get here in the test suite? I missed that. I'll try to work out a test case today and send an additional patch to get coverage here. I thought RevWalkCullTest testProperlyCullAllAncestors1() would be hitting here. It doesn't. > I'll merge it anyway since this is still a huge improvement compared to the previous > state. Thanks. A co-worker and I are also currently trying to track down a deadlock between C git-fetch and JGit upload-pack. Both get stuck waiting for the other to answer. Clearly its JGit's fault. -- Shawn. ^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2009-03-16 14:35 UTC | newest] Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2009-03-13 2:07 [JGIT PATCH 0/5] RevWalk fixes for UNINTERESTING Shawn O. Pearce 2009-03-13 2:07 ` [JGIT PATCH 1/5] Show critical flags in debug toString() descriptions of rev queues Shawn O. Pearce 2009-03-13 2:07 ` [JGIT PATCH 2/5] Make RevObject.getType implementations final Shawn O. Pearce 2009-03-13 2:07 ` [JGIT PATCH 3/5] Remove the horribly stupid RevSort.START_ORDER Shawn O. Pearce 2009-03-13 2:07 ` [JGIT PATCH 4/5] Fix RevWalk with Linus Torvald's occasional bad commit date hack Shawn O. Pearce 2009-03-13 2:07 ` [JGIT PATCH 5/5] Avoid incorrect output of UNINTERESTING commits when clock skew occurs Shawn O. Pearce 2009-03-14 0:54 ` [JGIT PATCH 4/5 v2] Fix RevWalk with Linus Torvald's occasional bad commit date hack Shawn O. Pearce 2009-03-13 20:00 ` [JGIT PATCH 0/5] RevWalk fixes for UNINTERESTING Robin Rosenberg 2009-03-13 22:39 ` [JGIT PATCH 0/6] Add tests for RevWalk and its supporting code Shawn O. Pearce 2009-03-14 0:13 ` Shawn O. Pearce 2009-03-14 0:56 ` [JGIT PATCH 6/5 v2] " Shawn O. Pearce 2009-03-15 11:34 ` Robin Rosenberg 2009-03-16 14:33 ` Shawn O. Pearce
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.