git-rev-list bug?

git-rev-list bug?

[Catalin Marinas]

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

Re: git-rev-list bug?

[Junio C Hamano]

"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.

Re: git-rev-list bug?

[Junio C Hamano]

Junio C Hamano <junkio@cox.net> writes:

> "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...

Re: git-rev-list bug?

[Junio C Hamano]

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)

Re: git-rev-list bug?

[Junio C Hamano]

Junio C Hamano <junkio@cox.net> writes:

> 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:

Re: git-rev-list bug?

[Junio C Hamano]

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)

Re: git-rev-list bug?

[Catalin Marinas]

Junio C Hamano <junkio@cox.net> wrote:
> 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

Re: git-rev-list bug?

[Linus Torvalds]

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

Re: git-rev-list bug?

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> 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.