git-annotate bug report

git-annotate bug report

[Jeff King]

git-annotate on the tip of master seems to be broken for some files (but
not for others):

$ git-describe
v1.4.2-rc2-gfba0cbd
$ make && ./git-annotate builtin-read-tree.c
parent eff97e3faeb28f6521851c1b3be1a54a2138f12a is on line 852
Line 852, does not match:
||
|                       cnt++;|
021b6e454944a4fba878651ebf9bfe0a3f6c3077

-Peff

Re: git-annotate bug report

[Ryan Anderson]

On Thu, Aug 03, 2006 at 04:38:48PM -0400, Jeff King wrote:
> git-annotate on the tip of master seems to be broken for some files (but
> not for others):
> 
> $ git-describe
> v1.4.2-rc2-gfba0cbd
> $ make && ./git-annotate builtin-read-tree.c
> parent eff97e3faeb28f6521851c1b3be1a54a2138f12a is on line 852
> Line 852, does not match:
> ||
> |                       cnt++;|
> 021b6e454944a4fba878651ebf9bfe0a3f6c3077


Sweet, that might be exactly the test case I need to figure out where it
loses track of some lines during merges.

I'll see about looking at this over the weekend.

-- 

Ryan Anderson
  sometimes Pug Majere

Re: git-annotate bug report

[Ryan Anderson]

On Thu, Aug 03, 2006 at 04:38:48PM -0400, Jeff King wrote:
> git-annotate on the tip of master seems to be broken for some files (but
> not for others):

Well, I think I've found a few bugs here tonight, basically all are
related to handling merges correctly.

First, a trivial one:

git diff-tree -M --name-status -z outputs the sha1 without honoring the
-z.  Patch following this email.

Second, one I don't know how to fix, at the moment:

git annotate uses the automatic tree simplification that git rev-list
does.  So, when it sees a commit with 1 parent, it assumes that it
really only has one parent.  git diff-tree -c doesn't know about this
same tree simplification, and, in the case of a merge commit, will still
output the -c format patch.

That particular case is trivial, simply remove the -c from commits where
I *know* there is only parent, and ask for the exact diff I need, from
the parent to the current rev.

There is, unfortunately, another situation, that of an octopus merge.
In the case of read-tree.c (after the rename is followed), the commit
7bd1527d2d8c80a6e9a0f8583082a5aee5428c68 is problematic.  In it we have
a 4-way merge, yet only 3 paths affected read-tree.c.  The diff-parsing
in annotate constructs a regular expression to find the diff header and
read out the line number to work on, and also to construct some regular
expressions from which to tell which lines affect which parents.

For example, it looks for a line like:
+ ++Line added in 3 parents
with dynamically generated regular expressions.  These, of course, need
to know how many parents there are.  The fact that diff-tree uses a
different number of parents makes the parsing fail, and then, the fact
that there isn't a great way to figure out which of the real parents
corresponds to the pseudo parents, makes this whole thing very
messy to fix.

So, the solution I've settled on is to use git merge-base to perform
some analysis and create a pseudo-parent list that is the same size as
the actual parent list, but consisting mostly of the fake parents
git-rev-list gives me.

If anyone else is confused by this email, it's probably because I
stopped and fixed a bug in the middle of writing it.

Patches as followups to this.


-- 

Ryan Anderson
  sometimes Pug Majere

[PATCH 1/2] log-tree: show_log() should respect the setting of diffopt->line_termination

[Ryan Anderson]

Signed-off-by: Ryan Anderson <ryan@michonline.com>
---
 log-tree.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/log-tree.c b/log-tree.c
index b67b8dd..05ede0c 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -59,7 +59,7 @@ void show_log(struct rev_info *opt, cons
 		fputs(diff_unique_abbrev(commit->object.sha1, abbrev_commit), stdout);
 		if (opt->parents)
 			show_parents(commit, abbrev_commit);
-		putchar('\n');
+		putchar(opt->diffopt.line_termination);
 		return;
 	}
 
-- 
1.4.2.rc3.g6487-dirty

[PATCH 2/2] annotate: Fix bug when parsing merges with differing real and logical parents.

[Ryan Anderson]

Signed-off-by: Ryan Anderson <ryan@michonline.com>
---
 git-annotate.perl |  128 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 files changed, 122 insertions(+), 6 deletions(-)

diff --git a/git-annotate.perl b/git-annotate.perl
index 505b5cc..215ed26 100755
--- a/git-annotate.perl
+++ b/git-annotate.perl
@@ -147,7 +147,7 @@ sub init_claim {
 
 
 sub handle_rev {
-	my $i = 0;
+	my $revseen = 0;
 	my %seen;
 	while (my $rev = shift @revqueue) {
 		next if $seen{$rev}++;
@@ -247,22 +247,129 @@ sub git_find_parent {
 	return $parent;
 }
 
+sub git_find_all_parents {
+	my ($rev) = @_;
+
+	my $revparent = open_pipe("git-rev-list","--remove-empty", "--parents","--max-count=1","$rev")
+		or die "Failed to open git-rev-list to find a single parent: $!";
+
+	my $parentline = <$revparent>;
+	chomp $parentline;
+	my ($origrev, @parents) = split m/\s+/, $parentline;
+
+	close($revparent);
+
+	return @parents;
+}
+
+sub git_merge_base {
+	my ($rev1, $rev2) = @_;
+
+	my $mb = open_pipe("git-merge-base", $rev1, $rev2)
+	        or die "Failed to open git-merge-base: $!";
+
+	my $base = <$mb>;
+	chomp $base;
+
+	close($mb);
+
+	return $base;
+}
+
+# Construct a set of pseudo parents that are in the same order,
+# and the same quantity as the real parents,
+# but whose SHA1s are as similar to the logical parents
+# as possible.
+sub get_pseudo_parents {
+	my ($all, $fake) = @_;
+
+	my @all = @$all;
+	my @fake = @$fake;
+
+	my @pseudo;
+
+	my %fake = map {$_ => 1} @fake;
+	my %seenfake;
+
+	my $fakeidx = 0;
+	foreach my $p (@all) {
+		if (exists $fake{$p}) {
+			if ($fake[$fakeidx] ne $p) {
+				die sprintf("parent mismatch: %s != %s\nall:%s\nfake:%s\n",
+					    $fake[$fakeidx], $p,
+					    join(", ", @all),
+					    join(", ", @fake),
+					   );
+			}
+
+			push @pseudo, $p;
+			$fakeidx++;
+			$seenfake{$p}++;
+
+		} else {
+			my $base = git_merge_base($fake[$fakeidx], $p);
+			if ($base ne $fake[$fakeidx]) {
+				die sprintf("Result of merge-base doesn't match fake: %s,%s != %s\n",
+				       $fake[$fakeidx], $p, $base);
+			}
+
+			# The details of how we parse the diffs
+			# mean that we cannot have a duplicate
+			# revision in the list, so if we've already
+			# seen the revision we would normally add, just use
+			# the actual revision.
+			if ($seenfake{$base}) {
+				push @pseudo, $p;
+			} else {
+				push @pseudo, $base;
+				$seenfake{$base}++;
+			}
+		}
+	}
+
+	return @pseudo;
+}
+
 
 # Get a diff between the current revision and a parent.
 # Record the commit information that results.
 sub git_diff_parse {
 	my ($parents, $rev, %revinfo) = @_;
 
+	my @pseudo_parents;
+	my @command = ("git-diff-tree");
+	my $revision_spec;
+
+	if (scalar @$parents == 1) {
+
+		$revision_spec = join("..", $parents->[0], $rev);
+		@pseudo_parents = @$parents;
+	} else {
+		my @all_parents = git_find_all_parents($rev);
+
+		if (@all_parents !=  @$parents) {
+			@pseudo_parents = get_pseudo_parents(\@all_parents, $parents);
+		} else {
+			@pseudo_parents = @$parents;
+		}
+
+		$revision_spec = $rev;
+		push @command, "-c";
+	}
+
 	my @filenames = ( $revs{$rev}{'filename'} );
+
 	foreach my $parent (@$parents) {
 		push @filenames, $revs{$parent}{'filename'};
 	}
 
-	my $diff = open_pipe("git-diff-tree","-M","-p","-c",$rev,"--",
-				@filenames )
+	push @command, "-p", "-M", $revision_spec, "--", @filenames;
+
+
+	my $diff = open_pipe( @command )
 		or die "Failed to call git-diff for annotation: $!";
 
-	_git_diff_parse($diff, $parents, $rev, %revinfo);
+	_git_diff_parse($diff, \@pseudo_parents, $rev, %revinfo);
 
 	close($diff);
 }
@@ -283,6 +390,7 @@ sub _git_diff_parse {
 	$diff_header_regexp .= "@" x @$parents;
 	$diff_header_regexp .= ' -\d+,\d+' x @$parents;
 	$diff_header_regexp .= ' \+(\d+),\d+';
+	$diff_header_regexp .= " " . ("@" x @$parents);
 
 	my %claim_regexps;
 	my $allparentplus = '^' . '\\+' x @$parents . '(.*)$';
@@ -311,6 +419,7 @@ sub _git_diff_parse {
 	DIFF:
 	while(<$diff>) {
 		chomp;
+		#printf("%d:%s:\n", $gotheader, $_);
 		if (m/$diff_header_regexp/) {
 			$remstart = $1 - 1;
 			# (0-based arrays)
@@ -391,10 +500,17 @@ sub _git_diff_parse {
 						printf("parent %s is on line %d\n", $parent, $pi{$parent});
 					}
 
+					my @context;
+					for (my $i = -2; $i < 2; $i++) {
+						push @context, get_line($slines, $ri + $i);
+					}
+					my $context = join("\n", @context);
+
+					my $justline = substr($_, scalar @$parents);
 					die sprintf("Line %d, does not match:\n|%s|\n|%s|\n%s\n",
 						    $ri,
-						substr($_,scalar @$parents),
-						get_line($slines,$ri), $rev);
+						    $justline,
+						    $context);
 				}
 				foreach my $parent (@$parents) {
 					$plines{$parent}[$pi{$parent}++] = $slines->[$ri];
-- 
1.4.2.rc3.g6487-dirty

Re: [PATCH 2/2] annotate: Fix bug when parsing merges with differing real and logical parents.

[Junio C Hamano]

This does stop it from dying on Jeff King's bug report
(<20060803203848.GA15121@coredump.intra.peff.net>) to annotate
builtin-read-tree.c.  However,...

Comparing output between "annotate" and "blame -c" on the same
file shows a rather interesting differences.

(1) "annotate" blames the first line "/*" to d147e501 made on
    2006-05-23, while "blame" annotates it with 8bc9a0c7 made on
    2005-04-07.  As far as I remember this line has never been
    touched by anybody during the life of the file, so the
    latter sounds more plausible.

(2) The 13th line to #include "cache-tree.h" is blamed on
    3f69d405 by "annotate", while annotation by "blame" reads
    that it came from bad68ec9.

    3f69d405 is a merge to incorporate the line into "master"
    branch.  "git show -M 3f69d405 -- builtin-read-tree.c read-tree.c"
    starts with:

        diff --cc builtin-read-tree.c
        index ec40d01,99e7c75..716f792
        --- a/builtin-read-tree.c
        +++ b/builtin-read-tree.c
        @@@ -9,9 -9,9 +9,10 @@@

          #include "object.h"
          #include "tree.h"
        + #include "cache-tree.h"
	  #include <sys/time.h>

    Which means the line is new from the point of view of the
    "master" branch, but existed in the branch that this commit
    merges from (namely, jc/cache-tree) already.

    "git show -M bad68ec9 -- read-tree.c" shows that it is the
    one that added the #include line to the history.

(3) The 14th line to #include <sys/time.h> is blamed on d147e501
    by "annotate" but "blame" says it came from 744633cb.  It is
    obvious the latter is correct, if you look at "git show" on
    these commits.  The eye-candy was what made <sys/time.h>
    necessary (it needed to do the progress-signal stuff).

In fact, "annotate" attributes too many lines to d147e501 (839
lines).

Given that "git show -M d147e501 -- read-tree.c builtin-read-tree.c"
shows only 2 insertions and 1 deletion, it does not sound
right.  The commit adds #include "builtin.h" and changes the
function name "main" to "cmd_read_tree".

On the other hand, "blame" attributes only 1 line to this
commit; the line to #include "builtin.h".  The other change this
commit introduces (main -> cmd_read_tree) is not counted because
the third parameter to the function changes after this commit by
a91af794 (which, by the way, both "annotate" and "blame" get
right), and the line this commit introduces did not survive.

Re: [PATCH 1/2] log-tree: show_log() should respect the setting of diffopt->line_termination

[Junio C Hamano]

Thanks.  This indeed was a regression from 1.0 codebase.

Re: [PATCH 2/2] annotate: Fix bug when parsing merges with differing real and logical parents.

[Ryan Anderson]

On Mon, Aug 07, 2006 at 12:16:27PM -0700, Junio C Hamano wrote:
> This does stop it from dying on Jeff King's bug report
> (<20060803203848.GA15121@coredump.intra.peff.net>) to annotate
> builtin-read-tree.c.  However,...
> 
> Comparing output between "annotate" and "blame -c" on the same
> file shows a rather interesting differences.

Yes, annotate is still mis-attributing things to merges that it should
not.  I was kind of hoping this fix would have a side-effect of fixing
it, but I had no logical reason to think it would.   I'm going to try
again at fixing it later this week, maybe the weekend, but I'm starting
to think that maybe blame has won. :)

> 
> (1) "annotate" blames the first line "/*" to d147e501 made on
>     2006-05-23, while "blame" annotates it with 8bc9a0c7 made on
>     2005-04-07.  As far as I remember this line has never been
>     touched by anybody during the life of the file, so the
>     latter sounds more plausible.
> 
> (2) The 13th line to #include "cache-tree.h" is blamed on
>     3f69d405 by "annotate", while annotation by "blame" reads
>     that it came from bad68ec9.
> 
>     3f69d405 is a merge to incorporate the line into "master"
>     branch.  "git show -M 3f69d405 -- builtin-read-tree.c read-tree.c"
>     starts with:
> 
>         diff --cc builtin-read-tree.c
>         index ec40d01,99e7c75..716f792
>         --- a/builtin-read-tree.c
>         +++ b/builtin-read-tree.c
>         @@@ -9,9 -9,9 +9,10 @@@
> 
>           #include "object.h"
>           #include "tree.h"
>         + #include "cache-tree.h"
> 	  #include <sys/time.h>
> 
>     Which means the line is new from the point of view of the
>     "master" branch, but existed in the branch that this commit
>     merges from (namely, jc/cache-tree) already.
> 
>     "git show -M bad68ec9 -- read-tree.c" shows that it is the
>     one that added the #include line to the history.
> 
> (3) The 14th line to #include <sys/time.h> is blamed on d147e501
>     by "annotate" but "blame" says it came from 744633cb.  It is
>     obvious the latter is correct, if you look at "git show" on
>     these commits.  The eye-candy was what made <sys/time.h>
>     necessary (it needed to do the progress-signal stuff).
> 
> In fact, "annotate" attributes too many lines to d147e501 (839
> lines).
> 
> Given that "git show -M d147e501 -- read-tree.c builtin-read-tree.c"
> shows only 2 insertions and 1 deletion, it does not sound
> right.  The commit adds #include "builtin.h" and changes the
> function name "main" to "cmd_read_tree".
> 
> On the other hand, "blame" attributes only 1 line to this
> commit; the line to #include "builtin.h".  The other change this
> commit introduces (main -> cmd_read_tree) is not counted because
> the third parameter to the function changes after this commit by
> a91af794 (which, by the way, both "annotate" and "blame" get
> right), and the line this commit introduces did not survive.
> 
> 
> 

-- 

Ryan Anderson
  sometimes Pug Majere

Annotate another problem report

[Junio C Hamano]

"git annotate Makefile v1.4.0" outputs this:

...
58e60dd2	(Nick Hengeveld	2005-11-02 11:19:24 -0800	13)# git.......
58e60dd2	(Nick Hengeveld	2005-11-02 11:19:24 -0800	14)# tra.......
	(          	1970-01-01 00:00:00 	15)#
6d9bbc50	(Patrick Mauritz	2005-09-19 16:11:19 +0200	16)# ..
6d9bbc50	(Patrick Mauritz	2005-09-19 16:11:19 +0200	17)# ..
...

There are a handful lines it couldn't tell where they came from:

	(          	1970-01-01 00:00:00 	15)#
	(          	1970-01-01 00:00:00 	179)
	(          	1970-01-01 00:00:00 	182)
	(          	1970-01-01 00:00:00 	274)endif
	(          	1970-01-01 00:00:00 	323)
	(          	1970-01-01 00:00:00 	384)else
	(          	1970-01-01 00:00:00 	385)	LIB_4_ICONV =

Re: Annotate another problem report

[Ryan Anderson]

On Mon, Aug 07, 2006 at 01:00:34PM -0700, Junio C Hamano wrote:
> "git annotate Makefile v1.4.0" outputs this:

Known.  I think this is related to the merge-parsing bug.

Unfortunately, the only test cases I've found for this involve things
with both a lot of revisions and a lot of lines, so it's a bit hard to
manually see what's going wrong.

> ...
> 58e60dd2	(Nick Hengeveld	2005-11-02 11:19:24 -0800	13)# git.......
> 58e60dd2	(Nick Hengeveld	2005-11-02 11:19:24 -0800	14)# tra.......
> 	(          	1970-01-01 00:00:00 	15)#
> 6d9bbc50	(Patrick Mauritz	2005-09-19 16:11:19 +0200	16)# ..
> 6d9bbc50	(Patrick Mauritz	2005-09-19 16:11:19 +0200	17)# ..
> ...
> 
> There are a handful lines it couldn't tell where they came from:
> 
> 	(          	1970-01-01 00:00:00 	15)#
> 	(          	1970-01-01 00:00:00 	179)
> 	(          	1970-01-01 00:00:00 	182)
> 	(          	1970-01-01 00:00:00 	274)endif
> 	(          	1970-01-01 00:00:00 	323)
> 	(          	1970-01-01 00:00:00 	384)else
> 	(          	1970-01-01 00:00:00 	385)	LIB_4_ICONV =
> 
> 

-- 

Ryan Anderson
  sometimes Pug Majere

Re: git-annotate bug report

[Junio C Hamano]

Ryan Anderson <ryan@michonline.com> writes:

> Second, one I don't know how to fix, at the moment:
>
> git annotate uses the automatic tree simplification that git rev-list
> does.  So, when it sees a commit with 1 parent, it assumes that it
> really only has one parent.  git diff-tree -c doesn't know about this
> same tree simplification, and, in the case of a merge commit, will still
> output the -c format patch.

When a merge M between A and B is simplified to have only A as a
parent, that means the file in question are identical in M and
A.  So you can just pass all the remaining blame on to A without
letting M taking any blame for itself.  So you do not need to do
any diff at all for a simplified merge.

> There is, unfortunately, another situation, that of an octopus merge.
> In the case of read-tree.c (after the rename is followed), the commit
> 7bd1527d2d8c80a6e9a0f8583082a5aee5428c68 is problematic.  In it we have
> a 4-way merge, yet only 3 paths affected read-tree.c.  The diff-parsing
> in annotate constructs a regular expression to find the diff header and
> read out the line number to work on, and also to construct some regular
> expressions from which to tell which lines affect which parents.

If a merge is not simplified, and if you end up reading from
--cc or -c -p, then:

> For example, it looks for a line like:
> + ++Line added in 3 parents
> with dynamically generated regular expressions.

the merge needs to claim responsibility only for lines that have
all pluses (i.e. evil merge), which you are already doing, I
think.  Any line without a minus that has at least one space can
be blamed on the parent that corresponds to the space (and if
there are more than one space, pick the first one).

Your particular "octopus" case, I think, is the same story.

$ git diff-tree --pretty=short -p -c 7bd1527 -- read-tree.c builtin-read-tree.c

would give you a combined diff, none of which has $allparentplus
(so nothing should be attributed to this merge), and the header
would tell you which parent to pass the blame on from that
point.