rev-list --reverse --full-history --parents with path limiter disconnects history

Attached is a repository (to be imported via git fast-import) that has such a history:

o--o--A--B--o
\ \
o--o--C-----M--o--X <- master

where the A,B,C touch path P2 such that P2 is the same after B and C. Commit X touches P2 as well.

This command does not give the expected result: It reports *two* initial commits and one merge; in particular, commit X is reported as initial commit.

$ git rev-list --parents --reverse --full-history master -- P2

This command gives the expected result, i.e. there is one initial commit, one merge, and some more regular commits:

$ git rev-list --parents --full-history master -- P2

And this works as well, i.e there is a linear history that omits the branch via C:

$ git rev-list --parents --reverse master -- P2

Please help!

BTW, I've observed this behavior earlier when I debugged David Tweed's repository, after which we removed --full-history from git-filter-branch. But I could not easily find a simple history that exposes the problem. Now I have such a history.

BTW2, using --simplify-merges instead of --full-history has the same problem (but I don't think that comes as a surprise).

-- Hannes

--reverse did not interact well with --parents, as the included test case shows: in a history like

  A--B.
   \   \
    `C--M--D

the command

  git rev-list --reverse --parents --full-history HEAD

erroneously lists D as having no parents at all. (Without --reverse, it correctly lists M.)

This is caused by the machinery driving --reverse: it first grabs all commits through the normal routines, then runs them through the same routines again, effectively simplifying them twice.

Fix this by moving the --reverse one level up, into get_revision(). This way we can cleanly grab all commits via the normal calls, then just pop them off the list one by one without interfering with get_revision_internal().

---

The good news is: the patch really does fix your issue. It also fixes the test case (which uses the history from the diagram above). And it passes the test suite.

The bad news: I got as far as understanding that the repeated simplification must be at fault, but gave up on trying to see exactly _which step_ breaks the output. Obviously parent rewriting is the prime suspect.

And while I'm quite convinced that this is the "right" fix in the sense that the new implementation captures how --reverse would be described by someone not knowing the code, it does change behaviour in some cases. For example, with --boundary we always output boundaries last, regardless of --reverse. With this patch, --reverse is essentially just |tac, so they move to the top.

- Thomas

PS: Apologies for the subject braino earlier today. As advised on IRC, I have labeled the resulting hole in my foot ***FIXME***.

 revision.c                          |   38 ++++++++++++++-----------------
 revision.h                          |    1 +
 t/t6013-rev-list-reverse-parents.sh |   42 +++++++++++++++++++++++++++++++++++
 3 files changed, 60 insertions(+), 21 deletions(-)
 create mode 100755 t/t6013-rev-list-reverse-parents.sh

index 36291b6..ae4062c 100644
@@ -1646,26 +1646,6 @@ static struct commit *get_revision_internal(struct rev_info *revs)
 		return c;
 	}
 
-	if (revs->reverse) {
-		int limit = -1;
-
-		if (0 <= revs->max_count) {
-			limit = revs->max_count;
-			if (0 < revs->skip_count)
-				limit += revs->skip_count;
-		}
-		l = NULL;
-		while ((c = get_revision_1(revs))) {
-			commit_list_insert(c, &l);
-			if ((0 < limit) && !--limit)
-				break;
-		}
-		revs->commits = l;
-		revs->reverse = 0;
-		revs->max_count = -1;
-		c = NULL;
-	}
-
 	/*
 	 * Now pick up what they want to give us
 	 */

@@ -1738,7 +1718,23 @@ static struct commit *get_revision_internal(struct rev_info *revs)
 
 struct commit *get_revision(struct rev_info *revs)
 {
-	struct commit *c = get_revision_internal(revs);
+	struct commit *c;
+	struct commit_list *reversed;
+
+	if (revs->reverse) {
+		reversed = NULL;
+		while ((c = get_revision_internal(revs))) {
+			commit_list_insert(c, &reversed);
+		}
+		revs->commits = reversed;
+		revs->reverse = 0;
+		revs->reverse_output_stage = 1;
+	}
+
+	if (revs->reverse_output_stage)
+		return pop_commit(&revs->commits);
+
+	c = get_revision_internal(revs);
 	if (c && revs->graph)
 		graph_update(revs->graph, c);
 	return c;

index 91f1944..a636247 100644
@@ -53,6 +53,7 @@ struct rev_info {
 			rewrite_parents:1,
 			print_parents:1,
 			reverse:1,
+			reverse_output_stage:1,
 			cherry_pick:1,
 			first_parent_only:1;
 

1.6.0.1.24.g4c7bd

Thanks for picking up the topic and helping out. It does indeed work with my example.

I let others comment whether this patch is good. I've no clue how the revision walker machinery works.

-- Hannes

Yeah, I noticed that running simplify_commit() (hence rewrite_parents()) more than once on the same commit seems to do "unexpected" things, during my (hitherto unsuccessful) attempt to to make the --simplify-merges machinery incremental.