Re: [BUG] git-rev-list: --topo-order --boundary and --max-count

"Santi Béjar" [off-list ref] writes:

 the --topo-order does not play well with --boundary and --max-count.

$ git-rev-list --boundary --max-count=50 5ced0 | wc -l
56
$ git-rev-list --topo-order --boundary --max-count=50 5ced0 | wc -l
8846

(5ced0 is git.git's master). I think it should be 56 for both. It
presents this behaviour since c4025103fa, when was added --boundary
support for git-rev-list --max-count and --max-age.

I think the code that does --boundary when the list is limited
with --max-count is not quite right, even without topo-order.
Only when the traversal is not limited, the code happens to work
correctly because in that case alone we pick up positive commits
one by one up to the specified count, and do not place anything
other than their immediate parents in the list.

It needs to find out commits (be they marked as UNINTERESTING or
not) still in the revs->commits that are _not_ reachable by any
other commits in the list, or something like that.

I suspect that would unfortunately be very expensive.  Dscho,
have better ideas?

On Mon, 5 Mar 2007, Junio C Hamano wrote:

I think the code that does --boundary when the list is limited
with --max-count is not quite right, even without topo-order.

Yeah. Sadly, this is a really irritating bug, becuase it means that you 
cannot do

	gitk -50

to see some random collection of 50 recent commits.

(And yes, I've wanted to do that - I know the commit is fairly recent, so 
rather than write "gitk @{1.hour.ag}..", I'd rather just be lazy and say 
"gitk -100" to get a smaller slider bar and easier to find the recent 
ones).

I never cared enough to fix it, but it's a mis-feature. I agree that it's 
probably not entirely trivial to fix.

		Linus

In case revs->limited == 1, the revision walker really reads
everything into revs->commits. The behaviour introduced in
c4025103fa does not behave correctly in that case.

It used to say: everything which is _still_ in the pipeline
must be a boundary commit.

So, in the case that revs->limited == 1, filter out all commits
which are not dangling, in effect marking only the dangling
ones as boundary commits.

This bug was noticed by Santi Béjar.

Signed-off-by: Johannes Schindelin <redacted>
---

	On Mon, 5 Mar 2007, Junio C Hamano wrote:

	> "Santi Béjar" [off-list ref] writes:
	> 
	> > the --topo-order does not play well with --boundary and 
	> > --max-count.
	> >
	> > $ git-rev-list --boundary --max-count=50 5ced0 | wc -l
	> > 56
	> > $ git-rev-list --topo-order --boundary --max-count=50 5ced0 \
	> >   | wc -l
	> > 8846
	> >
	> > (5ced0 is git.git's master). I think it should be 56 for both. 
	> > It presents this behaviour since c4025103fa, when was added 
	> > --boundary support for git-rev-list --max-count and --max-age.
	> 
	> I think the code that does --boundary when the list is limited
	> with --max-count is not quite right, even without topo-order.

	Right.

	> It needs to find out commits (be they marked as UNINTERESTING or
	> not) still in the revs->commits that are _not_ reachable by any
	> other commits in the list, or something like that.
	> 
	> I suspect that would unfortunately be very expensive.  Dscho,
	> have better ideas?

	Unfortunately not. Fortunately, it is nowhere near as expensive as 
	I originally thought. It just has to iterate through revs->commits 
	three times, which is way cheaper than sorting the commits in the 
	first place.

	Junio, if you apply this, could you make extra sure that I did not 
	fsck up Santi's family name (I am running on a peculiar mixture of 
	UTF-8 and ISO-8859-1 terminals...).

 revision.c |   31 +++++++++++++++++++++++++++----
 1 files changed, 27 insertions(+), 4 deletions(-)

diff --git a/revision.c b/revision.c
index f5b8ae4..8d47fac 100644
--- a/revision.c
+++ b/revision.c

@@ -1294,6 +1294,26 @@ static struct commit *get_revision_1(struct rev_info *revs)
 	return NULL;
 }
 
+static struct commit_list *get_dangling_commits(struct commit_list *list)
+{
+	struct commit_list *result = NULL, *iter, *parent;
+
+	for (iter = list; iter; iter = iter->next)
+		for (parent = iter->item->parents;
+				parent;
+				parent = parent->next)
+			parent->item->object.flags |= TMP_MARK;
+	for (iter = list; iter; iter = iter->next)
+		if (!(iter->item->object.flags & TMP_MARK))
+			commit_list_insert(iter->item, &result);
+	for (iter = list; iter; iter = iter->next)
+		for (parent = iter->item->parents;
+				parent;
+				parent = parent->next)
+			parent->item->object.flags &= ~TMP_MARK;
+	return result;
+}
+
 struct commit *get_revision(struct rev_info *revs)
 {
 	struct commit *c = NULL;

@@ -1345,12 +1365,15 @@ struct commit *get_revision(struct rev_info *revs)
 		break;
 	case 0:
 		if (revs->boundary) {
-			struct commit_list *list = revs->commits;
-			while (list) {
+			struct commit_list *list;
+			if (revs->limited) {
+				list = get_dangling_commits(revs->commits);
+				free_commit_list(revs->commits);
+				revs->commits = list;
+			}
+			for (list = revs->commits; list; list = list->next)
 				list->item->object.flags |=
 					BOUNDARY_SHOW | BOUNDARY;
-				list = list->next;
-			}
 			/* all remaining commits are boundary commits */
 			revs->max_count = -1;
 			revs->limited = 1;

-- 
1.5.0.3.2518.g2f72-dirty

Hi,

On Mon, 5 Mar 2007, Johannes Schindelin wrote:

	On Mon, 5 Mar 2007, Junio C Hamano wrote:

	> "Santi Béjar" [off-list ref] writes:
	> 
	> > the --topo-order does not play well with --boundary and 
	> > --max-count.
	> >
	> > $ git-rev-list --boundary --max-count=50 5ced0 | wc -l
	> > 56
	> > $ git-rev-list --topo-order --boundary --max-count=50 5ced0 \
	> >   | wc -l
	> > 8846
	> >
	> > (5ced0 is git.git's master). I think it should be 56 for both. 

Side note: with the patch I am replying to, the latter command returns 51. 
This is correct, since the only boundary commit it shows (1db8b60b) has 
(all) the other 5 commits as ancestors.

The behaviour of both is correct: in the former case, there is not enough 
information to tell that one of the 6 boundary commits reaches all the 
others.

Ciao,
Dscho

On Mon, 5 Mar 2007, Johannes Schindelin wrote:

In case revs->limited == 1, the revision walker really reads
everything into revs->commits. The behaviour introduced in
c4025103fa does not behave correctly in that case.

It used to say: everything which is _still_ in the pipeline
must be a boundary commit.

I would suggest this (more invasive) patch instead.

Yours is

 revision.c |   31 +++++++++++++++++++++++++++----
 1 files changed, 27 insertions(+), 4 deletions(-)

and mine is

 revision.c |   86 ++++++++++++++++++++++++++++++-----------------------------
 1 files changed, 44 insertions(+), 42 deletions(-)

ie I have bigger changes, but on the whole this patch just adds two lines 
total, and I *think* the end result is more readable.

NOTE! Our patches aren't really mutually incompatible, and they attack the 
problem from two different directions. You do the separate phase (which is 
also correct), and my patch instead tries to clean up the commit walking 
so that the commit number limiter works more like the date limiter (which 
fundamentally has all the same issues! Including the problem with some 
commits possibly being marked as boundary commits when they aren't really, 
because the path-limiting or revision-limiting ended up cutting things off 
*differently* than the date-limiting).

So I would humbly suggest applying this one first (which makes the 
handling of the walk-time commit limiter more uniform and less hacky), and 
if we need to, we can *also* add the whole separate phase for the 
"revs->limited" case..

		Linus

---
commit d3dd7e89c123b644ef199380f4f050226e4df862
Author: Linus Torvalds [off-list ref]
Date:   Mon Mar 5 10:15:20 2007 -0800

    revision list: fix BOUNDARY handling with limiters and commit counts
    
    When we limited the number of commits using "max_count", we would not
    correctly handle the combination of various time- and reachability-based
    limiting and the use of a commit counting.  Everything that was
    reachable (but overflowed the commit count) would be marked as a
    BOUNDARY commit, resulting in things like "gitk" not being usable
    together with a numerical limit on the number of commits.
    
    This largely fixes it by being more careful about how we mark commits
    that went over the commit counts.
    
    NOTE! Because the numerical limiting happens without a separate phase as
    we traverse the commit list, we still won't do the boundary handling
    100% correct when a commit may be reachable from multiple sources, and
    under those circumstances, some commits will be marked as boundary
    commits even though they strictly aren't.
    
    To fix this, we would need to make rather more invasive changes, with
    commit counting being an integral part of the limiting (whuch is
    fundamnetally hard, since limiting itself will change the number of
    commits!).
    
    So this is the "good enough to be quite usable" approach.  The problem
    only affects boundary commits, and programs like 'gitk' that uses
    boundary commits would be better off just noticing themselves that not
    all boundary commits are necessarily useful.
    
    Signed-off-by: Linus Torvalds [off-list ref]
---
 revision.c |   86 ++++++++++++++++++++++++++++++-----------------------------
 1 files changed, 44 insertions(+), 42 deletions(-)

diff --git a/revision.c b/revision.c
index f5b8ae4..f5430d6 100644
--- a/revision.c
+++ b/revision.c

@@ -1213,6 +1213,30 @@ static int commit_match(struct commit *commit, struct rev_info *opt)
 			   commit->buffer, strlen(commit->buffer));
 }
 
+enum walk_action {
+	WALK_PARENTS,
+	WALK_STOP,
+};
+
+/*
+ * When we do the list limiting at commit-walking time, we
+ * need to make sure that we stop walking parenthood when
+ * we hit a commit that isn't interesting any more. This can
+ * be due to max_count or due to date limiters.
+ */
+static enum walk_action walk_commit(struct rev_info *revs, struct commit *commit)
+{
+	if (!revs->max_count)
+		return WALK_STOP;
+
+	if (revs->max_age != -1) {
+		if (commit->date < revs->max_age)
+			return WALK_STOP;
+	}
+
+	return WALK_PARENTS;
+}
+
 static struct commit *get_revision_1(struct rev_info *revs)
 {
 	if (!revs->commits)

@@ -1233,17 +1257,19 @@ static struct commit *get_revision_1(struct rev_info *revs)
 		 * the parents here. We also need to do the date-based limiting
 		 * that we'd otherwise have done in limit_list().
 		 */
-		if (!revs->limited) {
-			if (revs->max_age != -1 &&
-			    (commit->date < revs->max_age)) {
-				if (revs->boundary)
-					commit->object.flags |=
-						BOUNDARY_SHOW | BOUNDARY;
-				else
-					continue;
-			} else
-				add_parents_to_list(revs, commit,
-						&revs->commits);
+		switch (walk_commit(revs, commit)) {
+		case WALK_PARENTS:
+			if (revs->limited)
+				break;
+			add_parents_to_list(revs, commit, &revs->commits);
+			break;
+		case WALK_STOP:
+			if (!revs->boundary)
+				continue;
+			if (!(commit->object.flags & UNINTERESTING))
+				commit->object.flags |= BOUNDARY_SHOW | BOUNDARY | UNINTERESTING;
+			mark_parents_uninteresting(commit);
+			break;
 		}
 		if (commit->object.flags & SHOWN)
 			continue;

@@ -1289,6 +1315,12 @@ static struct commit *get_revision_1(struct rev_info *revs)
 		if (revs->boundary)
 			mark_boundary_to_show(commit);
 		commit->object.flags |= SHOWN;
+		if (revs->skip_count > 0) {
+			revs->skip_count--;
+			continue;
+		}
+		if (revs->max_count > 0)
+			revs->max_count--;
 		return commit;
 	} while (revs->commits);
 	return NULL;

@@ -1296,9 +1328,8 @@ static struct commit *get_revision_1(struct rev_info *revs)
 
 struct commit *get_revision(struct rev_info *revs)
 {
-	struct commit *c = NULL;
-
 	if (revs->reverse) {
+		struct commit *c;
 		struct commit_list *list;
 
 		/*

@@ -1332,34 +1363,5 @@ struct commit *get_revision(struct rev_info *revs)
 		return c;
 	}
 
-	if (0 < revs->skip_count) {
-		while ((c = get_revision_1(revs)) != NULL) {
-			if (revs->skip_count-- <= 0)
-				break;
-		}
-	}
-
-	/* Check the max_count ... */
-	switch (revs->max_count) {
-	case -1:
-		break;
-	case 0:
-		if (revs->boundary) {
-			struct commit_list *list = revs->commits;
-			while (list) {
-				list->item->object.flags |=
-					BOUNDARY_SHOW | BOUNDARY;
-				list = list->next;
-			}
-			/* all remaining commits are boundary commits */
-			revs->max_count = -1;
-			revs->limited = 1;
-		} else
-			return NULL;
-	default:
-		revs->max_count--;
-	}
-	if (c)
-		return c;
 	return get_revision_1(revs);
 }

On Mon, 5 Mar 2007, Linus Torvalds wrote:

NOTE! Our patches aren't really mutually incompatible, and they attack the 
problem from two different directions. You do the separate phase (which is 
also correct), and my patch instead tries to clean up the commit walking 
so that the commit number limiter works more like the date limiter (which 
fundamentally has all the same issues! Including the problem with some 
commits possibly being marked as boundary commits when they aren't really, 
because the path-limiting or revision-limiting ended up cutting things off 
*differently* than the date-limiting).

Side note: the reason you don't *notice* it with the date-limiter is 
simply that the date limiter *also* runs at limit-time, rather than just 
at the incremental "run at the end" phase. So the date-limiter is much 
simpler when done together with other limiters (like path and revision 
limiters).

HOWEVER. We can't do the same thing for the numerical one, because we need 
to run the other limiters *first*, and the numerical limiter always comes 
at the end. And the path-based "dense" limiter actually runs mostly 
incrementally, so you cannot do the numerical limiter until after it has 
run..

The way to really clean stuff up would be to:

 - first phase: limit by date and revision ranges first (both of those are 
   static and quick, and don't depend on anything else)

   We do this already (limit_list)

 - second phase: limit by pathname (we don't do this as a phase at all, we 
   do it incrementally: see "rewrite_parents()")

 -third phase: limit by number

HOWEVER. There's a damn good reason why we do things the way we do, namely 
simply the fact that we want to do pathname limiting as much at run-time 
as possible.. But we *could* do the "rewrite_parents()" thing both in the
non-incremental and in the final phase. However, doing the parent 
rewriting is quite nasty and error-prone, so I've been avoiding it.

Anyway, I *suspect* that Dscho's patch might do the wrong thing for 
something like

	gitk -20 v1.4.4.. t/

exactly because of the subtle interaction between pathname limiting, 
static commit limiting *and* commit number limiting. Dscho?

		Linus

Johannes Schindelin [off-list ref] writes:

In case revs->limited == 1, the revision walker really reads
everything into revs->commits. The behaviour introduced in
c4025103fa does not behave correctly in that case.

It used to say: everything which is _still_ in the pipeline
must be a boundary commit.

So, in the case that revs->limited == 1, filter out all commits
which are not dangling, in effect marking only the dangling
ones as boundary commits.

That's what I suggested initially but I think that is wrong.  We
should show only unshown immediate parents of shown commits at
that stage.

Hi,

On Mon, 5 Mar 2007, Linus Torvalds wrote:

Anyway, I *suspect* that Dscho's patch might do the wrong thing for 
something like

	gitk -20 v1.4.4.. t/

exactly because of the subtle interaction between pathname limiting, 
static commit limiting *and* commit number limiting. Dscho?

Correct. I'll have a look at Junio's patch shortly, which hopefully makes 
me forget my shortsighted patch.

Ciao,
Dscho