threads / bug / 3599

git-rev-list bug?

Subject: git-rev-list bug?

## tl;dr

9 messages between Mar 8, 2006 and Mar 10, 2006.

replies: 8people: 4as markdown or json

Catalin Marinas· Mar 8, 2006, 16:19 UTC · lore

Sorry if this was previously discussed. I ran git-rev-list on a linear graph and tried to filter the results by a file name:

  git rev-list since.. path/to/file

but it always shows the child commit of "since" even if it didn't touch the file. The same behaviour is for git-log (since it uses git-rev-list) but git-whatchanged seems to be fine.

Is this the intended behaviour? The "stg patches" command based on git-rev-list used to work fine a few weeks ago but now it is always reporting the bottom patch in the stack as modifying a given file.

Thanks.

-- Catalin

Junio C Hamano· Mar 8, 2006, 20:16 UTC · re: Catalin Marinas · lore

Re: git-rev-list bug?

"Catalin Marinas" <catalin.marinas@gmail.com> writes:
Show 12 quoted lines
> Sorry if this was previously discussed. I ran git-rev-list on a linear
> graph and tried to filter the results by a file name:
>
>   git rev-list since.. path/to/file
>
> but it always shows the child commit of "since" even if it didn't
> touch the file. The same behaviour is for git-log (since it uses
> git-rev-list) but git-whatchanged seems to be fine.
>
> Is this the intended behaviour? The "stg patches" command based on
> git-rev-list used to work fine a few weeks ago but now it is always
> reporting the bottom patch in the stack as modifying a given file.

I can confirm that this is a recent breakage, but since it is unfortunately my day-job day the more detailed analysis and fix needs to wait. Sorry.

Junio C Hamano· Mar 10, 2006, 08:20 UTC · re: Junio C Hamano · lore

Re: git-rev-list bug?

Junio C Hamano <junkio@cox.net> writes:
Show 18 quoted lines
> "Catalin Marinas" <catalin.marinas@gmail.com> writes:
>
>> Sorry if this was previously discussed. I ran git-rev-list on a linear
>> graph and tried to filter the results by a file name:
>>
>>   git rev-list since.. path/to/file
>>
>> but it always shows the child commit of "since" even if it didn't
>> touch the file. The same behaviour is for git-log (since it uses
>> git-rev-list) but git-whatchanged seems to be fine.
>>
>> Is this the intended behaviour? The "stg patches" command based on
>> git-rev-list used to work fine a few weeks ago but now it is always
>> reporting the bottom patch in the stack as modifying a given file.
>
> I can confirm that this is a recent breakage, but since it is
> unfortunately my day-job day the more detailed analysis and fix
> needs to wait.  Sorry.

To my surprise, it turns out that this regression was not very recent. Bisecting points at this commite:

diff-tree 461cf59... (from 6b94f1e...)
Author: Linus Torvalds <torvalds@osdl.org>
Date:   Wed Jan 18 14:47:30 2006 -0800
    rev-list: stop when the file disappears
    
    The one thing I've considered doing (I really should) is to add a "stop
    when you don't find the file" option to "git-rev-list". This patch does
    some of the work towards that: it removes the "parent" thing when the
    file disappears, so a "git annotate" could do do something like
    
    	git-rev-list --remove-empty --parents HEAD -- "$filename"
    
    and it would get a good graph that stops when the filename disappears
    (it's not perfect though: it won't remove all the unintersting commits).
    
    It also simplifies the logic of finding tree differences a bit, at the
    cost of making it a tad less efficient.
    
    The old logic was two-phase: it would first simplify _only_ merges tree as
    it traversed the tree, and then simplify the linear parts of the remainder
    independently. That was pretty optimal from an efficiency standpoint
    because it avoids doing any comparisons that we can see are unnecessary,
    but it made it much harder to understand than it really needed to be.
    
    The new logic is a lot more straightforward, and compares the trees as it
    traverses the graph (ie everything is a single phase). That makes it much
    easier to stop graph traversal at any point where a file disappears.
    
I haven't had time to dig into this deeper yet...
Junio C Hamano· Mar 10, 2006, 09:40 UTC · re: Junio C Hamano · lore

Re: git-rev-list bug?

Junio C Hamano <junkio@cox.net> writes:
> To my surprise, it turns out that this regression was not very
> recent.  Bisecting points at this commite:
>...
> I haven't had time to dig into this deeper yet...

I am wondering why try_to_simplify_commit() skips parents marked with UNINTERESTING. I think this is causing a problem Catalin found with rev-list.

If you have (time flows from top to bottom):
	commit#1	(it does not matter what this does)
        commit#2        change file B only
        commit#3	change file A only
        commit#4	change file B only

"git-rev-list commit#1..commit#4 -- A" shows commit#3 (correct) and commit#2 (incorrect).

It pushes commit#1 (UNINTERESTING) and commit#4 (~UNINTERESTING) and starts traversing. try-to-simplify(commit#4) says "no tree change between #3 and #4" and it returns without marking commit#4 with TREECHANGE flag. But when looking at commit#2 and trying to simplify it, it says "Ah, its parent is uninteresting, so I would not do compare_tree()". Iteration over parents of commit#2 leaves the while() loop and at the end of function the commit is marked with TREECHANGE and is shown.

The attached patch seems to fix it (without losing the logic to omit tree comparison with UNINTERESTING parent, which I do not quite understand).

---
diff --git a/revision.c b/revision.c
index 713f27e..23c9b9d 100644
--- a/revision.c
+++ b/revision.c
@@ -282,6 +282,7 @@ static int same_tree_as_empty(struct tre
 static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
 {
 	struct commit_list **pp, *parent;
+	int changed = 0;
 
 	if (!commit->tree)
 		return;
@@ -315,12 +316,14 @@ static void try_to_simplify_commit(struc
 			}
 		/* fallthrough */
 		case TREE_DIFFERENT:
+			changed = 1;
 			pp = &parent->next;
 			continue;
 		}
 		die("bad tree compare for commit %s", sha1_to_hex(commit->object.sha1));
 	}
-	commit->object.flags |= TREECHANGE;
+	if (changed)
+		commit->object.flags |= TREECHANGE;
 }
 
 static void add_parents_to_list(struct rev_info *revs, struct commit *commit, struct commit_list **list)
Junio C Hamano· Mar 10, 2006, 09:59 UTC · re: Junio C Hamano · lore

Re: git-rev-list bug?

Junio C Hamano <junkio@cox.net> writes:
Show 7 quoted lines
> I am wondering why try_to_simplify_commit() skips parents marked
> with UNINTERESTING.  I think this is causing a problem Catalin
> found with rev-list.
> ...
> The attached patch seems to fix it (without losing the logic to
> omit tree comparison with UNINTERESTING parent, which I do not
> quite understand).

Actually the previous patch is not right either. If I ask "what changes path B between commit#1..commit#4", it would still omit commit#2.

It should not matter if the parent is uninteresting while checking if a commit touches the specified path. The attached patch which replaces the previous botched one does exactly that.

It however has a side effect -- uninteresting commits were never parsed here, but now they get parsed. I am not sure if there are correctness implications...

---
diff --git a/revision.c b/revision.c
index 713f27e..9d0934a 100644
--- a/revision.c
+++ b/revision.c
@@ -296,11 +296,6 @@ static void try_to_simplify_commit(struc
 	while ((parent = *pp) != NULL) {
 		struct commit *p = parent->item;
 
-		if (p->object.flags & UNINTERESTING) {
-			pp = &parent->next;
-			continue;
-		}
-
 		parse_commit(p);
 		switch (compare_tree(p->tree, commit->tree)) {
 		case TREE_SAME:
Junio C Hamano· Mar 10, 2006, 10:25 UTC · re: Junio C Hamano · lore

Re: git-rev-list bug?

Junio C Hamano <junkio@cox.net> writes:
> It however has a side effect -- uninteresting commits were never
> parsed here, but now they get parsed.  I am not sure if there
> are correctness implications...

Actually there is. If a merge with an uninteresting side branch was the only thing that brought changes to paths we are interested in, we do not want TREE_SAME logic to remove other parents (i.e. the branches we are interested in) from the merge commit. 

So we would need a combination of both, something like this?
---
diff --git a/revision.c b/revision.c
index 713f27e..c8d93ff 100644
--- a/revision.c
+++ b/revision.c
@@ -282,6 +282,7 @@ static int same_tree_as_empty(struct tre
 static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
 {
 	struct commit_list **pp, *parent;
+	int tree_changed = 0;
 
 	if (!commit->tree)
 		return;
@@ -296,14 +297,19 @@ static void try_to_simplify_commit(struc
 	while ((parent = *pp) != NULL) {
 		struct commit *p = parent->item;
 
-		if (p->object.flags & UNINTERESTING) {
-			pp = &parent->next;
-			continue;
-		}
-
 		parse_commit(p);
 		switch (compare_tree(p->tree, commit->tree)) {
 		case TREE_SAME:
+			if (p->object.flags & UNINTERESTING) {
+				/* Even if a merge with an uninteresting
+				 * side branch brought the entire change
+				 * we are interested in, we do not want
+				 * to lose the other branches of this
+				 * merge, so we just keep going.
+				 */
+				pp = &parent->next;
+				continue;
+			}
 			parent->next = NULL;
 			commit->parents = parent;
 			return;
@@ -315,12 +321,14 @@ static void try_to_simplify_commit(struc
 			}
 		/* fallthrough */
 		case TREE_DIFFERENT:
+			tree_changed = 1;
 			pp = &parent->next;
 			continue;
 		}
 		die("bad tree compare for commit %s", sha1_to_hex(commit->object.sha1));
 	}
-	commit->object.flags |= TREECHANGE;
+	if (tree_changed)
+		commit->object.flags |= TREECHANGE;
 }
 
 static void add_parents_to_list(struct rev_info *revs, struct commit *commit, struct commit_list **list)
Catalin Marinas· Mar 10, 2006, 11:01 UTC · re: Junio C Hamano · lore

Re: git-rev-list bug?

Junio C Hamano <junkio@cox.net> wrote:
Show 13 quoted lines
> Junio C Hamano <junkio@cox.net> writes:
>
>> It however has a side effect -- uninteresting commits were never
>> parsed here, but now they get parsed.  I am not sure if there
>> are correctness implications...
>
> Actually there is.  If a merge with an uninteresting side branch
> was the only thing that brought changes to paths we are
> interested in, we do not want TREE_SAME logic to remove other
> parents (i.e. the branches we are interested in) from the merge
> commit.  
>
> So we would need a combination of both, something like this?

I can confirm that it "stg patches" works fine with this patch for git-rev-list.

Thanks.
-- 
Catalin
Linus Torvalds· Mar 10, 2006, 18:31 UTC · re: Junio C Hamano · lore

Re: git-rev-list bug?

On Fri, 10 Mar 2006, Junio C Hamano wrote:
> 
> So we would need a combination of both, something like this?
Looks good to me.

As does the 'revs.prune_fn' abstraction by Fredrik Kuivinen, for that matter. Ack to both.

		Linus
Junio C Hamano· Mar 10, 2006, 22:42 UTC · re: Linus Torvalds · lore

Re: git-rev-list bug?

Linus Torvalds <torvalds@osdl.org> writes:
Show 8 quoted lines
> On Fri, 10 Mar 2006, Junio C Hamano wrote:
>> 
>> So we would need a combination of both, something like this?
>
> Looks good to me.
>
> As does the 'revs.prune_fn' abstraction by Fredrik Kuivinen, for that 
> matter. Ack to both.

Thanks. I'm swamped by day-job today so will apply it sometime tomorrow.

← back to recent threads