[PATCH 0/3] gitweb: Improve git_blame in preparation for incremental blame

[PATCH 0/3] gitweb: Improve git_blame in preparation for incremental blame

[Jakub Narebski]

The following series implements a few improvements to git_blame code
and 'blame' view output to prepare for WIP/RFC patch adding incremental
blame output to gitweb using AJAX (JavaScript and XMLHttpRequest); the
code in question is based on code by Petr Baudis from 26 Aug 2007
  http://permalink.gmane.org/gmane.comp.version-control.git/56657
which in turn was based on Fredrik Kuivinen proof of concept patch.


The first patch in series (moving id to tr element) is needed in
blame_incremental, and it makes it easier to use DOM to manipulate
gitweb blame output.

Second patch is about what I have noticed when examining git_blame
code.

The last patch is not necessarily required; but please tell me if it
is to be accepted or to be dropped, to know whether to base
incremental blame on it.

---
Jakub Narebski (3):
      gitweb: A bit of code cleanup in git_blame()
      gitweb: Cache $parent_commit info in git_blame()
      gitweb: Move 'lineno' id from link to row element in git_blame

 gitweb/gitweb.perl |   84 ++++++++++++++++++++++++++++++----------------------
 1 files changed, 49 insertions(+), 35 deletions(-)

-- 
Jakub Narebski
ShadeHawk on #git
Poland

[PATCH 1/3] gitweb: Move 'lineno' id from link to row element in git_blame

[Jakub Narebski]

Move l<line number> ID from <a> link element inside table row (inside
cell element for column with line numbers), to encompassing <tr> table
row element.  It was done to make it easier to manipulate result HTML
with DOM, and to be able write 'blame_incremental' view with the same,
or nearly the same result.

Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
For blame_incremental I need easy way to manipulate rows of blame
table, to add information about blamed commits as it arrives.

So there it is.

 gitweb/gitweb.perl |    3 +--
 1 files changed, 1 insertions(+), 2 deletions(-)

diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
index 6eb370d..1b800f4 100755
--- a/gitweb/gitweb.perl
+++ b/gitweb/gitweb.perl
@@ -4645,7 +4645,7 @@ HTML
 		if ($group_size) {
 			$current_color = ++$current_color % $num_colors;
 		}
-		print "<tr class=\"$rev_color[$current_color]\">\n";
+		print "<tr id=\"l$lineno\" class=\"$rev_color[$current_color]\">\n";
 		if ($group_size) {
 			print "<td class=\"sha1\"";
 			print " title=\"". esc_html($author) . ", $date\"";
@@ -4667,7 +4667,6 @@ HTML
 		                  hash_base => $parent_commit);
 		print "<td class=\"linenr\">";
 		print $cgi->a({ -href => "$blamed#l$orig_lineno",
-		                -id => "l$lineno",
 		                -class => "linenr" },
 		              esc_html($lineno));
 		print "</td>";

Re: [PATCH 1/3] gitweb: Move 'lineno' id from link to row element in git_blame

[Luben Tuikov]

--- On Tue, 12/9/08, Jakub Narebski <jnareb@gmail.com> wrote:
> From: Jakub Narebski <jnareb@gmail.com>
> Subject: [PATCH 1/3] gitweb: Move 'lineno' id from link to row element in git_blame
> To: git@vger.kernel.org
> Cc: "Luben Tuikov" <ltuikov@yahoo.com>, "Jakub Narebski" <jnareb@gmail.com>
> Date: Tuesday, December 9, 2008, 2:46 PM
> Move l<line number> ID from <a> link element
> inside table row (inside
> cell element for column with line numbers), to encompassing
> <tr> table
> row element.  It was done to make it easier to manipulate
> result HTML
> with DOM, and to be able write 'blame_incremental'
> view with the same,
> or nearly the same result.
> 
> Signed-off-by: Jakub Narebski <jnareb@gmail.com>
Acked-by: Luben Tuikov <ltuikov@yahoo.com>

   Luben

> ---
> For blame_incremental I need easy way to manipulate rows of
> blame
> table, to add information about blamed commits as it
> arrives.
> 
> So there it is.
> 
>  gitweb/gitweb.perl |    3 +--
>  1 files changed, 1 insertions(+), 2 deletions(-)
> 
> diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
> index 6eb370d..1b800f4 100755
> --- a/gitweb/gitweb.perl
> +++ b/gitweb/gitweb.perl
> @@ -4645,7 +4645,7 @@ HTML
>  		if ($group_size) {
>  			$current_color = ++$current_color % $num_colors;
>  		}
> -		print "<tr
> class=\"$rev_color[$current_color]\">\n";
> +		print "<tr id=\"l$lineno\"
> class=\"$rev_color[$current_color]\">\n";
>  		if ($group_size) {
>  			print "<td
> class=\"sha1\"";
>  			print " title=\"". esc_html($author)
> . ", $date\"";
> @@ -4667,7 +4667,6 @@ HTML
>  		                  hash_base => $parent_commit);
>  		print "<td
> class=\"linenr\">";
>  		print $cgi->a({ -href =>
> "$blamed#l$orig_lineno",
> -		                -id => "l$lineno",
>  		                -class => "linenr" },
>  		              esc_html($lineno));
>  		print "</td>";

Re: [PATCH 1/3] gitweb: Move 'lineno' id from link to row element in git_blame

[Petr Baudis]

On Tue, Dec 09, 2008 at 11:46:16PM +0100, Jakub Narebski wrote:
> Move l<line number> ID from <a> link element inside table row (inside
> cell element for column with line numbers), to encompassing <tr> table
> row element.  It was done to make it easier to manipulate result HTML
> with DOM, and to be able write 'blame_incremental' view with the same,
> or nearly the same result.
> 
> Signed-off-by: Jakub Narebski <jnareb@gmail.com>

Acked-by: Petr Baudis <pasky@suse.cz>

[PATCH 2/3] gitweb: Cache $parent_commit info in git_blame()

[Jakub Narebski]

Luben Tuikov changed 'lineno' link from leading to commit which lead
to current version of given block of lines, to leading to parent of
this commit in 244a70e (Blame "linenr" link jumps to previous state at
"orig_lineno").  This supposedly made data mining possible (or just
better).

Unfortunately the implementation in 244a70e used one call for
git-rev-parse to find parent revision per line in file, instead of
using long lived "git cat-file --batch-check" (which might not existed
then), or changing validate_refname to validate_revision and made it
accept <rev>^, <rev>^^, <rev>^^^ etc. syntax.

This patch attempts to migitate issue a bit by caching $parent_commit
info in %metainfo, which makes gitweb to call git-rev-parse only once
per unique commit in blame output.

Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
That is what I have noticed during browsing git_blame() code.

We can change it to even more effective implementation (like the ones
proposed above in the commit message) later.

Indenting is cause for artifically large diff

 gitweb/gitweb.perl |   16 +++++++++++-----
 1 files changed, 11 insertions(+), 5 deletions(-)

diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
index 1b800f4..916396a 100755
--- a/gitweb/gitweb.perl
+++ b/gitweb/gitweb.perl
@@ -4657,11 +4657,17 @@ HTML
 			              esc_html($rev));
 			print "</td>\n";
 		}
-		open (my $dd, "-|", git_cmd(), "rev-parse", "$full_rev^")
-			or die_error(500, "Open git-rev-parse failed");
-		my $parent_commit = <$dd>;
-		close $dd;
-		chomp($parent_commit);
+		my $parent_commit;
+		if (!exists $meta->{'parent'}) {
+			open (my $dd, "-|", git_cmd(), "rev-parse", "$full_rev^")
+				or die_error(500, "Open git-rev-parse failed");
+			$parent_commit = <$dd>;
+			close $dd;
+			chomp($parent_commit);
+			$meta->{'parent'} = $parent_commit;
+		} else {
+			$parent_commit = $meta->{'parent'};
+		}
 		my $blamed = href(action => 'blame',
 		                  file_name => $meta->{'filename'},
 		                  hash_base => $parent_commit);

Re: [PATCH 2/3] gitweb: Cache $parent_commit info in git_blame()

[Nanako Shiraishi]

Quoting Jakub Narebski <jnareb@gmail.com>:

> Unfortunately the implementation in 244a70e used one call for
> git-rev-parse to find parent revision per line in file, instead of
> using long lived "git cat-file --batch-check" (which might not existed
> then), or changing validate_refname to validate_revision and made it
> accept <rev>^, <rev>^^, <rev>^^^ etc. syntax.

Could you substantiate why this is "Unfortunate"?  Is the new implementation faster?  By how much?

When "previous" commit information is available in the output from "git blame", can you make use of it?

-- 
Nanako Shiraishi
http://ivory.ap.teacup.com/nanako3/

Re: [PATCH 2/3] gitweb: Cache $parent_commit info in git_blame()

[Jakub Narebski]

On Wed, 10 Dec 2008, Nanako Shiraishi wrote:
> Quoting Jakub Narebski <jnareb@gmail.com>:
> 
> > Unfortunately the implementation in 244a70e used one call for
> > git-rev-parse to find parent revision per line in file, instead of
> > using long lived "git cat-file --batch-check" (which might not existed
> > then), or changing validate_refname to validate_revision and made it
> > accept <rev>^, <rev>^^, <rev>^^^ etc. syntax.
> 
> Could you substantiate why this is "Unfortunate"?

Because it calls git-rev-parse once for _each line_, even if for lines
in the group of neighbour lines blamed by same commit $parent_commit
is the same, and even if you need to calculate $parent_commit only once
per unique individual commit present in blame output.
 
> Is the new implementation faster?  By how much?

File               | L[1] | C[2] || Time0[3] | Before[4] | After[4]
====================================================================
blob.h             |   18 |    4 || 0m1.727s |  0m2.545s |  0m2.474s
GIT-VERSION-GEN    |   42 |   13 || 0m2.165s |  0m2.448s |  0m2.071s
README             |   46 |    6 || 0m1.593s |  0m2.727s |  0m2.242s
revision.c         | 1923 |  121 || 0m2.357s | 0m30.365s |  0m7.028s
gitweb/gitweb.perl | 6291 |  428 || 0m8.080s | 1m37.244s | 0m20.627s

File               | L/C  | Before/After
=========================================
blob.h             |  4.5 |         1.03
GIT-VERSION-GEN    |  3.2 |         1.18
README             |  7.7 |         1.22
revision.c         | 15.9 |         4.32
gitweb/gitweb.perl | 14.7 |         4.71

As you can see the greater ratio of lines in file to unique commits
in blame output, the greater gain from the new implementation.

Footnotes:
~~~~~~~~~~
[1] Lines: 
    $ wc -l <file>
[2] Individual commits in blame output:
    $ git blame -p <file> | grep author-time | wc -l
[3] Time for running "git blame -p" (user time, single run):
    $ time git blame -p <file> >/dev/null
[4] Time to run gitweb as Perl script from command line:
    $ gitweb-run.sh "p=git.git;a=blame;f=<file>" > /dev/null 2>&1

Appendix A:
~~~~~~~~~~~
#!/bin/bash

export GATEWAY_INTERFACE="CGI/1.1"
export HTTP_ACCEPT="*/*"
export REQUEST_METHOD="GET"
export QUERY_STRING=""$1""
export PATH_INFO=""$2""

export GITWEB_CONFIG="/home/jnareb/git/gitweb/gitweb_config.perl"

perl -- /home/jnareb/git/gitweb/gitweb.perl

# end of gitweb-run.sh


> When "previous" commit information is available in the output from
> "git blame", can you make use of it? 

Yes, I could; but I don't think it got implemented.
-- 
Jakub Narebski
Poland

Re: [PATCH 2/3] gitweb: Cache $parent_commit info in git_blame()

[Junio C Hamano]

Jakub Narebski <jnareb@gmail.com> writes:

> On Wed, 10 Dec 2008, Nanako Shiraishi wrote:
>> Quoting Jakub Narebski <jnareb@gmail.com>:
>> 
>> > Unfortunately the implementation in 244a70e used one call for
>> > git-rev-parse to find parent revision per line in file, instead of
>> > using long lived "git cat-file --batch-check" (which might not existed
>> > then), or changing validate_refname to validate_revision and made it
>> > accept <rev>^, <rev>^^, <rev>^^^ etc. syntax.
>> 
>> Could you substantiate why this is "Unfortunate"?
>
> Because it calls git-rev-parse once for _each line_, even if for lines
> in the group of neighbour lines blamed by same commit $parent_commit
> is the same, and even if you need to calculate $parent_commit only once
> per unique individual commit present in blame output.

It probably was obvious that this was meant as a patch for better
performance without changing the functionality.  I tend to think the
presentation wasn't so great, though.

    Luben Tuikov changed 'lineno' link from leading to commit which lead
    to current version of given block of lines, to leading to parent of
    this commit in 244a70e (Blame "linenr" link jumps to previous state at
    "orig_lineno").  This supposedly made data mining possible (or just
    better).

Other than "supposedly" which I do not think should be there, I think this
is a great opening paragraph to establish the context.

    Unfortunately the implementation in 244a70e used one call for
    git-rev-parse to find parent revision per line in file, instead of
    using long lived "git cat-file --batch-check" (which might not existed
    then), or changing validate_refname to validate_revision and made it
    accept <rev>^, <rev>^^, <rev>^^^ etc. syntax.

But I do not think this is such a great second paragraph that states what
problem it tries to solve.  I'd say something like this instead:

        The current implementation calls rev-parse once per line to find
        parent revision of blamed commit, even when the same commit
        appears more than once, which is inefficient.

And then the outline of the solution:

    This patch attempts to migitate issue a bit by caching $parent_commit
    info in %metainfo, which makes gitweb to call git-rev-parse only once
    per unique commit in blame output.

which is very good, except that I do not think you need to say "a bit".
And have your benchmark (two tables and footnotes) after this outline of
the solution.

I think the first part of "Unfortunately" paragraph can be dropped
(because that is already in the first half of problem description) and the
rest can come as the last paragraph as "Possible future enhancements".

> Appendix A:
> ~~~~~~~~~~~
> #!/bin/bash
>
> export GATEWAY_INTERFACE="CGI/1.1"
> export HTTP_ACCEPT="*/*"
> export REQUEST_METHOD="GET"
> export QUERY_STRING=""$1""
> export PATH_INFO=""$2""
>
> export GITWEB_CONFIG="/home/jnareb/git/gitweb/gitweb_config.perl"
>
> perl -- /home/jnareb/git/gitweb/gitweb.perl
>
> # end of gitweb-run.sh

I'd suggest making a separate patch to add "gitweb-run.sh" in contrib/ so
that other people can use it when checking their changes to gitweb.  The
script might need some more polishing, though.  For example, it is not
very obvious if you have *_config.perl only to customize for your
environment (e.g. where the test repositories are) or you need to have
some overrides in there when you are running gitweb as a standalone script.

To recap, I think the commit log for this patch would have been much
easier to read if it were presented in this order:

	a paragraph to establish the context;

	a paragraph to state what problem it tries to solve;

        a paragraph (or more) to explain the solution; and finally

	a paragraph to discuss possible future enhancements.

[PATCH 2/3 (edit v2)] gitweb: Cache $parent_commit info in git_blame()

[Jakub Narebski]

Luben Tuikov changed 'lineno' link from leading to commit which gave
current version of given block of lines, to leading to parent of this
commit in 244a70e (Blame "linenr" link jumps to previous state at
"orig_lineno").  This made possible data mining using 'blame' view.

The current implementation calls rev-parse once per each blamed line
to find parent revision of blamed commit, even when the same commit
appears more than once, which is inefficient.

This patch attempts to mitigate this issue by storing (caching)
$parent_commit info in %metainfo, which makes gitweb call
git-rev-parse only once per each unique commit in blame output.


In the tables below you can see simple benchmark comparing gitweb
performance before and after this patch

File               | L[1] | C[2] || Time0[3] | Before[4] | After[4]
====================================================================
blob.h             |   18 |    4 || 0m1.727s |  0m2.545s |  0m2.474s
GIT-VERSION-GEN    |   42 |   13 || 0m2.165s |  0m2.448s |  0m2.071s
README             |   46 |    6 || 0m1.593s |  0m2.727s |  0m2.242s
revision.c         | 1923 |  121 || 0m2.357s | 0m30.365s |  0m7.028s
gitweb/gitweb.perl | 6291 |  428 || 0m8.080s | 1m37.244s | 0m20.627s

File               | L/C  | Before/After
=========================================
blob.h             |  4.5 |         1.03
GIT-VERSION-GEN    |  3.2 |         1.18
README             |  7.7 |         1.22
revision.c         | 15.9 |         4.32
gitweb/gitweb.perl | 14.7 |         4.71

As you can see the greater ratio of lines in file to unique commits
in blame output, the greater gain from the new implementation.

Footnotes:
~~~~~~~~~~
[1] Lines:
    $ wc -l <file>
[2] Individual commits in blame output:
    $ git blame -p <file> | grep author-time | wc -l
[3] Time for running "git blame -p" (user time, single run):
    $ time git blame -p <file> >/dev/null
[4] Time to run gitweb as Perl script from command line:
    $ gitweb-run.sh "p=.git;a=blame;f=<file>" > /dev/null 2>&1

The gitweb-run.sh script includes slightly modified (with adjusted
pathnames) code from gitweb_run() function from the test script
t/t9500-gitweb-standalone-no-errors.sh; gitweb config file
gitweb_config.perl contents (again up to adjusting pathnames; in
particular $projectroot variable should point to top directory of git
repository) can be found in the same place.


Alternate solutions:
~~~~~~~~~~~~~~~~~~~~
Alternate solution would be to open bidi pipe to "git cat-file
--batch-check", (like in Git::Repo in gitweb caching by Lea Wiemann),
feed $long_rev^ to it, and parse its output which has the following
form:

  926b07e694599d86cec668475071b32147c95034 commit 637

This would mean one call to git-cat-file for the whole 'blame' view,
instead of one call to git-rev-parse per each unique commit in blame
output.


Yet another solution would be to change use of validate_refname() to
validate_revision() when checking script parameters (CGI query or
path_info), with validate_revision being something like the following:

  sub validate_revision {
        my $rev = shift;
        return validate_refname(strip_rev_suffixes($rev));
  }

so we don't need to calculate $long_rev^, but can pass "$long_rev^" as
'hb' parameter.

This solution has the advantage that it can be easily adapted to
future incremental blame output.

Acked-by: Luben Tuikov <ltuikov@yahoo.com>
Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
On Wed, 10 Dec 2008, Junio C Hamano wrote:

> To recap, I think the commit log for this patch would have been much
> easier to read if it were presented in this order:
> 
>         a paragraph to establish the context;
> 
>         a paragraph to state what problem it tries to solve;
> 
>         a paragraph (or more) to explain the solution; and finally
> 
>         a paragraph to discuss possible future enhancements.

Like this?

Only commit message has changed.

 gitweb/gitweb.perl |   16 +++++++++++-----
 1 files changed, 11 insertions(+), 5 deletions(-)

diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
index 1b800f4..916396a 100755
--- a/gitweb/gitweb.perl
+++ b/gitweb/gitweb.perl
@@ -4657,11 +4657,17 @@ HTML
 			              esc_html($rev));
 			print "</td>\n";
 		}
-		open (my $dd, "-|", git_cmd(), "rev-parse", "$full_rev^")
-			or die_error(500, "Open git-rev-parse failed");
-		my $parent_commit = <$dd>;
-		close $dd;
-		chomp($parent_commit);
+		my $parent_commit;
+		if (!exists $meta->{'parent'}) {
+			open (my $dd, "-|", git_cmd(), "rev-parse", "$full_rev^")
+				or die_error(500, "Open git-rev-parse failed");
+			$parent_commit = <$dd>;
+			close $dd;
+			chomp($parent_commit);
+			$meta->{'parent'} = $parent_commit;
+		} else {
+			$parent_commit = $meta->{'parent'};
+		}
 		my $blamed = href(action => 'blame',
 		                  file_name => $meta->{'filename'},
 		                  hash_base => $parent_commit);
-- 
1.6.0.4

Re: [PATCH 2/3 (edit v2)] gitweb: Cache $parent_commit info in git_blame()

[Luben Tuikov]

--- On Wed, 12/10/08, Jakub Narebski <jnareb@gmail.com> wrote:
> Acked-by: Luben Tuikov <ltuikov@yahoo.com>
> Signed-off-by: Jakub Narebski <jnareb@gmail.com>

I've always seen "Acked-by:" follows "Signed-off-by:".  Junio, has this
changed?

   Luben

Re: [PATCH 2/3 (edit v2)] gitweb: Cache $parent_commit info in git_blame()

[Junio C Hamano]

Luben Tuikov <ltuikov@yahoo.com> writes:

> --- On Wed, 12/10/08, Jakub Narebski <jnareb@gmail.com> wrote:
>> Acked-by: Luben Tuikov <ltuikov@yahoo.com>
>> Signed-off-by: Jakub Narebski <jnareb@gmail.com>
>
> I've always seen "Acked-by:" follows "Signed-off-by:".  Junio, has this
> changed?

I think the order is supposed to show the order of things happened.  Jakub
signs off the patch, you Ack, and I see the patch and append my sign-off.

You saw the exact same patch text, said that looked Ok to you, and Jakub
updated the log message to present the change better and signed off the
whole thing again.  You could say that there should be another, original,
sign off by Jakub before your Ack, but I do not think it adds anything of
value.

In any case, the change will be queued to 'pu'.  It is great that it is a
trivial change that gives us great performance boost, and I wish all our
patches are like that ;-).

Re: [PATCH 2/3 (edit v2)] gitweb: Cache $parent_commit info in git_blame()

[Junio C Hamano]

Jakub Narebski <jnareb@gmail.com> writes:

> ...
> Alternate solutions:
> ~~~~~~~~~~~~~~~~~~~~
> ...
> Acked-by: Luben Tuikov <ltuikov@yahoo.com>
> Signed-off-by: Jakub Narebski <jnareb@gmail.com>
> ---
> On Wed, 10 Dec 2008, Junio C Hamano wrote:
>
>> To recap, I think the commit log for this patch would have been much
>> easier to read if it were presented in this order:
>> 
>>         a paragraph to establish the context;
>> 
>>         a paragraph to state what problem it tries to solve;
>> 
>>         a paragraph (or more) to explain the solution; and finally
>> 
>>         a paragraph to discuss possible future enhancements.
>
> Like this?

Yes, basically.

The "future possibilities" section might be a bit too heavy, and also
calling it "Alternate solutions" makes it slightly unclear if it is
talking about what is implemented, or only talking about idle speculation
without an actual code (in this case, it is the latter), though.

> Only commit message has changed.

Which is a bit unnice, because it will conflict with the original [3/3]
that I queued already (with a pair of fixes, including but not limited to
the one you sent "Oops, it should have been like this" for).

I can hand wiggle the patch to make it apply, but I'd prefer if I did not
have to do this every time I receive a patch.

I think the conflict was trivial (just a single s/rev/short_rev/) and I
did not make a silly mistake when I fixed it up, but please check the
result on 'pu' after I push the results out.

Thanks.

Re: [PATCH 2/3 (edit v2)] gitweb: Cache $parent_commit info in git_blame()

[Jakub Narebski]

On Fri, 12 Dec 2008, Junio C Hamano wrote:
> Jakub Narebski <jnareb@gmail.com> writes:

> > Only commit message has changed.
> 
> Which is a bit unnice, because it will conflict with the original [3/3]
> that I queued already (with a pair of fixes, including but not limited to
> the one you sent "Oops, it should have been like this" for).
> 
> I can hand wiggle the patch to make it apply, but I'd prefer if I did not
> have to do this every time I receive a patch.

I'm sorry about that; I have forgot to change order of patches to have
original 1/3, 3/3, 2/3 (I should have used 'stg float' for that).

> I think the conflict was trivial (just a single s/rev/short_rev/) and I
> did not make a silly mistake when I fixed it up, but please check the
> result on 'pu' after I push the results out.

I did the reordering, and gitweb on compared top of reordered stack
of patches with gitweb from top of 'pu' branch, and the only
difference in the area touched by git_blame improvements series is
one comment I have added in v2 of 3/3.

Thank you for your work.
-- 
Jakub Narebski
Poland

Re: [PATCH 2/3 (edit v2)] gitweb: Cache $parent_commit info in git_blame()

[Petr Baudis]

On Thu, Dec 11, 2008 at 01:33:29AM +0100, Jakub Narebski wrote:
> Luben Tuikov changed 'lineno' link from leading to commit which gave
> current version of given block of lines, to leading to parent of this
> commit in 244a70e (Blame "linenr" link jumps to previous state at
> "orig_lineno").  This made possible data mining using 'blame' view.
> 
> The current implementation calls rev-parse once per each blamed line
> to find parent revision of blamed commit, even when the same commit
> appears more than once, which is inefficient.
> 
> This patch attempts to mitigate this issue by storing (caching)
> $parent_commit info in %metainfo, which makes gitweb call
> git-rev-parse only once per each unique commit in blame output.
> 
> 
> In the tables below you can see simple benchmark comparing gitweb
> performance before and after this patch
> 
> File               | L[1] | C[2] || Time0[3] | Before[4] | After[4]
> ====================================================================
> blob.h             |   18 |    4 || 0m1.727s |  0m2.545s |  0m2.474s
> GIT-VERSION-GEN    |   42 |   13 || 0m2.165s |  0m2.448s |  0m2.071s
> README             |   46 |    6 || 0m1.593s |  0m2.727s |  0m2.242s
> revision.c         | 1923 |  121 || 0m2.357s | 0m30.365s |  0m7.028s
> gitweb/gitweb.perl | 6291 |  428 || 0m8.080s | 1m37.244s | 0m20.627s
> 
> File               | L/C  | Before/After
> =========================================
> blob.h             |  4.5 |         1.03
> GIT-VERSION-GEN    |  3.2 |         1.18
> README             |  7.7 |         1.22
> revision.c         | 15.9 |         4.32
> gitweb/gitweb.perl | 14.7 |         4.71
> 
> As you can see the greater ratio of lines in file to unique commits
> in blame output, the greater gain from the new implementation.
> 
> Footnotes:
> ~~~~~~~~~~
> [1] Lines:
>     $ wc -l <file>
> [2] Individual commits in blame output:
>     $ git blame -p <file> | grep author-time | wc -l
> [3] Time for running "git blame -p" (user time, single run):
>     $ time git blame -p <file> >/dev/null
> [4] Time to run gitweb as Perl script from command line:
>     $ gitweb-run.sh "p=.git;a=blame;f=<file>" > /dev/null 2>&1
> 
> The gitweb-run.sh script includes slightly modified (with adjusted
> pathnames) code from gitweb_run() function from the test script
> t/t9500-gitweb-standalone-no-errors.sh; gitweb config file
> gitweb_config.perl contents (again up to adjusting pathnames; in
> particular $projectroot variable should point to top directory of git
> repository) can be found in the same place.
> 
> 
> Alternate solutions:
> ~~~~~~~~~~~~~~~~~~~~
> Alternate solution would be to open bidi pipe to "git cat-file
> --batch-check", (like in Git::Repo in gitweb caching by Lea Wiemann),
> feed $long_rev^ to it, and parse its output which has the following
> form:
> 
>   926b07e694599d86cec668475071b32147c95034 commit 637
> 
> This would mean one call to git-cat-file for the whole 'blame' view,
> instead of one call to git-rev-parse per each unique commit in blame
> output.
> 
> 
> Yet another solution would be to change use of validate_refname() to
> validate_revision() when checking script parameters (CGI query or
> path_info), with validate_revision being something like the following:
> 
>   sub validate_revision {
>         my $rev = shift;
>         return validate_refname(strip_rev_suffixes($rev));
>   }
> 
> so we don't need to calculate $long_rev^, but can pass "$long_rev^" as
> 'hb' parameter.
> 
> This solution has the advantage that it can be easily adapted to
> future incremental blame output.
> 
> Acked-by: Luben Tuikov <ltuikov@yahoo.com>
> Signed-off-by: Jakub Narebski <jnareb@gmail.com>

Acked-by: Petr Baudis <pasky@suse.cz>

(though I think the commit message is total overkill for such an obvious
change ;-)

Re: [PATCH 2/3 (edit v2)] gitweb: Cache $parent_commit info in git_blame()

[Junio C Hamano]

Petr Baudis <pasky@suse.cz> writes:

> (though I think the commit message is total overkill for such an obvious
> change ;-)

I think so too; the performance figures are nice but there is no need to
talk about what is not implemented.

Re: [PATCH 2/3] gitweb: Cache $parent_commit info in git_blame()

[Luben Tuikov]

--- On Tue, 12/9/08, Jakub Narebski <jnareb@gmail.com> wrote:
> From: Jakub Narebski <jnareb@gmail.com>
> Subject: [PATCH 2/3] gitweb: Cache $parent_commit info in git_blame()
> To: git@vger.kernel.org
> Cc: "Luben Tuikov" <ltuikov@yahoo.com>, "Jakub Narebski" <jnareb@gmail.com>
> Date: Tuesday, December 9, 2008, 2:48 PM
> Luben Tuikov changed 'lineno' link from leading to
> commit which lead
> to current version of given block of lines, to leading to
> parent of
> this commit in 244a70e (Blame "linenr" link jumps
> to previous state at
> "orig_lineno").  This supposedly made data mining
> possible (or just
> better).

Before 244a70e, clicking on linenr links would display
the same commit id as displayed to the left, which is no
different than the block of lines displayed, thus data
mining was impossible, i.e. I had to manually (commands)
go back in history to see how this line or block of lines
developed and/or changed.

244a70e didn't make data mining perfect, just possible.

> This patch attempts to migitate issue a bit by caching
> $parent_commit
> info in %metainfo, which makes gitweb to call git-rev-parse
> only once
> per unique commit in blame output.

Have you tested this patch that it gives the same commit chain
as before it?

   Luben


> 
> Signed-off-by: Jakub Narebski <jnareb@gmail.com>
> ---
> That is what I have noticed during browsing git_blame()
> code.

What?

> We can change it to even more effective implementation
> (like the ones
> proposed above in the commit message) later.

Where?

> 
> Indenting is cause for artifically large diff
> 
>  gitweb/gitweb.perl |   16 +++++++++++-----
>  1 files changed, 11 insertions(+), 5 deletions(-)
> 
> diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
> index 1b800f4..916396a 100755
> --- a/gitweb/gitweb.perl
> +++ b/gitweb/gitweb.perl
> @@ -4657,11 +4657,17 @@ HTML
>  			              esc_html($rev));
>  			print "</td>\n";
>  		}
> -		open (my $dd, "-|", git_cmd(),
> "rev-parse", "$full_rev^")
> -			or die_error(500, "Open git-rev-parse
> failed");
> -		my $parent_commit = <$dd>;
> -		close $dd;
> -		chomp($parent_commit);
> +		my $parent_commit;
> +		if (!exists $meta->{'parent'}) {
> +			open (my $dd, "-|", git_cmd(),
> "rev-parse", "$full_rev^")
> +				or die_error(500, "Open git-rev-parse
> failed");
> +			$parent_commit = <$dd>;
> +			close $dd;
> +			chomp($parent_commit);
> +			$meta->{'parent'} = $parent_commit;
> +		} else {
> +			$parent_commit = $meta->{'parent'};
> +		}
>  		my $blamed = href(action => 'blame',
>  		                  file_name =>
> $meta->{'filename'},
>  		                  hash_base => $parent_commit);

Re: [PATCH 2/3] gitweb: Cache $parent_commit info in git_blame()

[Jakub Narebski]

On Wed, 10 Dec 2008, Luben Tuikov wrote:
> --- On Tue, 12/9/08, Jakub Narebski <jnareb@gmail.com> wrote:

> > This patch attempts to migitate issue [of performance] a bit by
> > caching $parent_commit info in %metainfo, which makes gitweb to
> > call git-rev-parse only once per unique commit in blame output.
> 
> Have you tested this patch that it gives the same commit chain
> as before it?

The only difference between precious version and this patch is that
now, if you calculate sha-1 of $long_rev^, it is stored in 
$metainfo{$long_rev}{'parent'} and not calculated second time.

But I have checked that (at least for single example file) the blame
output is identical for before and after this patch.


> > That is what I have noticed during browsing git_blame()
> > code.
> 
> What?

What I have noticed? I have noticed this inefficiency.
Why I was browsing git_blame? To write git_blame_incremental...

See also my reply to Nanako Shiraishi with simple benchmark.

> > We can change it to even more effective implementation
> > (like the ones proposed above in the commit message) later.
> 
> Where?

jn> Unfortunately the implementation in 244a70e used one call for
jn> git-rev-parse to find parent revision per line in file, instead of
jn> using long lived "git cat-file --batch-check" (which might not existed
jn> then), or changing validate_refname to validate_revision and made it
jn> accept <rev>^, <rev>^^, <rev>^^^ etc. syntax.

One solution mentioned there is to open bidi pipe (like in Git::Repo
in gitweb caching by Lea Wiemann) to "git cat-file --batch-check"
(the '--batch-check' option was added to git-cat-file by Adam Roben
on Apr 23, 2008 in v1.5.6-rc0~8^2~9), feed it $long_rev^, and parse
its output of the form:

  926b07e694599d86cec668475071b32147c95034 commit 637

see manpage for git-cat-file(1). Unfortunately it seems like 
command_bidi_pipe doesn't work as _I_ expected...


Another solution mentioned there is to change validate_refname to
validate_revision when checking script parameters (CGI query or
path_info), with validate_revision being something like:

  sub validate_revision {
  	my $rev = shift;
	return validate_refname(strip_rev_suffixes($rev));
  }

or something like that, so we don't need to calculate $long_rev^,
but can pass "$long_rev^" as 'hb' parameter ($long_rev can in turn
also end in '^').

-- 
Jakub Narebski
Poland

Re: [PATCH 2/3] gitweb: Cache $parent_commit info in git_blame()

[Luben Tuikov]

--- On Wed, 12/10/08, Jakub Narebski <jnareb@gmail.com> wrote:
> > Have you tested this patch that it gives the same
> commit chain
> > as before it?
> 
> The only difference between precious version and this patch
> is that
> now, if you calculate sha-1 of $long_rev^, it is stored in 
> $metainfo{$long_rev}{'parent'} and not calculated
> second time.

Yes, I agree a patch to this effect would improve performance
proportionally to the history of the lines of a file.  So it's a
good thing, as most commits change a contiguous block of size more
than one line of a file.

"$parent_commit" depends on "$full_rev^" which depends on "$full_rev".
So as soon as "$full_rev" != "$old_full_rev", you'd know that you need
to update "$parent_commit".  "$old_full_rev" needs to exist outside the
scope of "while (1)".  I didn't see this in the code or in the patch.

> But I have checked that (at least for single example file)
> the blame output is identical for before and after this patch.

I've always tested it on something like "gitweb.perl", etc.

    Luben

Re: [PATCH 2/3] gitweb: Cache $parent_commit info in git_blame()

[Jakub Narebski]

On Wed, 10 Dec 2008, Luben Tuikov wrote:
> --- On Wed, 12/10/08, Jakub Narebski <jnareb@gmail.com> wrote:

Side note: is it Yahoo web mail interface that removes attributions?

> > > Have you tested this patch that it gives the same commit chain
> > > as before it?
> > 
> > The only difference between precious version and this patch
> > is that now, if you calculate sha-1 of $long_rev^, it is stored in 
> > $metainfo{$long_rev}{'parent'} and not calculated second time.
> 
> Yes, I agree a patch to this effect would improve performance
> proportionally to the history of the lines of a file.

Or rather proportionally to the ratio of number of lines of a file
to number of unique commits (not groups of lines) which are blamed
for given contents of a file.

> So it's a good thing, as most commits change a contiguous block
> of size more than one line of a file.
> 
> "$parent_commit" depends on "$full_rev^" which depends on "$full_rev".
> So as soon as "$full_rev" != "$old_full_rev", you'd know that you need
> to update "$parent_commit".  "$old_full_rev" needs to exist outside
> the  scope of "while (1)".  I didn't see this in the code or in the
> patch. 

You don't need $old_full_rev. We have to save data about commit in
%metainfo hash because information about commit appears in 
"git blame --porcelain" output _once_ per commit. So we use the same
cache to store $full_rev^ in $meta{'parent'}, which means storing
it in $metainfo{$full_rev}{'parent'}.

Now if the commit we saved this info about appears again in git-blame
output, be it in group of lines for which the same commit is blamed,
or later in unrelated chunk, we use saved info.

Let me try to explain it using the following diagram:

  Commit N Line Original code      This patch
  ------------------------------------------------------
  3a4046 1 xxx  rev-parse 3a4046^  rev-parse 3a4046^
         2 xxx  rev-parse 3a4046^  $mi{3a4046}{'parent'}
         3 xxx  rev-parse 3a4046^  $mi{3a4046}{'parent'}
  f47c19 5 xxx  rev-parse f47c19^  rev-parse f47c19^
         6 xxx  rev-parse f47c19^  $mi{f47c19}{'parent'}
  3a4046 7 xxx  rev-parse 3a4046^  $mi{3a4046}{'parent'}  <--
         8 xxx  rev-parse 3a4046^  $mi{3a4046}{'parent'}

where "rev-parse 3a4046^" means call to git-rev-parse, and $mi{<rev>}
accessing $metainfo{$full_rev} (via $meta).
 
In place marked by arrow '<--' you don't need to calculate 3a4046^
again...

> > But I have checked that (at least for single example file)
> > the blame output is identical for before and after this patch.
> 
> I've always tested it on something like "gitweb.perl", etc.

I've checked it on blob.h.  Other good example is README (with boundary
commits) and GIT-VERSION-GEN (with different output between git-blame
--porcelain and --incremental), both of which take much less time than
gitweb/gitweb.perl (see benchmarks in other post).

-- 
Jakub Narebski
Poland

Re: [PATCH 2/3] gitweb: Cache $parent_commit info in git_blame()

[Luben Tuikov]

--- On Wed, 12/10/08, Jakub Narebski <jnareb@gmail.com> wrote:

> You don't need $old_full_rev. We have to save data
> about commit in
> %metainfo hash because information about commit appears in 

Oh, yeah, the hash... Then, it looks correct.

Acked-by: Luben Tuikov <ltuikov@yahoo.com>

[PATCH 3/3] gitweb: A bit of code cleanup in git_blame()

[Jakub Narebski]

Among others: 
 * move variable declaration closer to the place it is set and used,
   if possible,
 * uniquify and simplify coding style a bit, which includes removing
   unnecessary '()'.
 * check type only if $hash was defined, as otherwise from the way
   git_get_hash_by_path() is called (and works), we know that it is
   a blob,
 * use modern calling convention for git-blame,
 * remove unused variable,
 * don't use implicit variables ($_),
 * add some comments

Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
Not stricly necessary... but the code looked not very nice

 gitweb/gitweb.perl |   65 ++++++++++++++++++++++++++++++----------------------
 1 files changed, 37 insertions(+), 28 deletions(-)

diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
index 916396a..68aa3f8 100755
--- a/gitweb/gitweb.perl
+++ b/gitweb/gitweb.perl
@@ -4575,28 +4575,32 @@ sub git_tag {
 }
 
 sub git_blame {
-	my $fd;
-	my $ftype;
-
+	# permissions
 	gitweb_check_feature('blame')
-	    or die_error(403, "Blame view not allowed");
+		or die_error(403, "Blame view not allowed");
 
+	# error checking
 	die_error(400, "No file name given") unless $file_name;
 	$hash_base ||= git_get_head_hash($project);
-	die_error(404, "Couldn't find base commit") unless ($hash_base);
+	die_error(404, "Couldn't find base commit") unless $hash_base;
 	my %co = parse_commit($hash_base)
 		or die_error(404, "Commit not found");
 	if (!defined $hash) {
 		$hash = git_get_hash_by_path($hash_base, $file_name, "blob")
 			or die_error(404, "Error looking up file");
+	} else {
+		my $ftype = git_get_type($hash);
+		if ($ftype !~ "blob") {
+			die_error(400, "Object is not a blob");
+		}
 	}
-	$ftype = git_get_type($hash);
-	if ($ftype !~ "blob") {
-		die_error(400, "Object is not a blob");
-	}
-	open ($fd, "-|", git_cmd(), "blame", '-p', '--',
-	      $file_name, $hash_base)
+
+	# run git-blame --porcelain
+	open my $fd, "-|", git_cmd(), "blame", '-p',
+		$hash_base, '--', $file_name
 		or die_error(500, "Open git-blame failed");
+
+	# page header
 	git_header_html();
 	my $formats_nav =
 		$cgi->a({-href => href(action=>"blob", -replay=>1)},
@@ -4610,40 +4614,43 @@ sub git_blame {
 	git_print_page_nav('','', $hash_base,$co{'tree'},$hash_base, $formats_nav);
 	git_print_header_div('commit', esc_html($co{'title'}), $hash_base);
 	git_print_page_path($file_name, $ftype, $hash_base);
-	my @rev_color = (qw(light2 dark2));
+
+	# page body
+	my @rev_color = qw(light2 dark2);
 	my $num_colors = scalar(@rev_color);
 	my $current_color = 0;
-	my $last_rev;
+	my %metainfo = ();
+
 	print <<HTML;
 <div class="page_body">
 <table class="blame">
 <tr><th>Commit</th><th>Line</th><th>Data</th></tr>
 HTML
-	my %metainfo = ();
-	while (1) {
-		$_ = <$fd>;
-		last unless defined $_;
+ LINE:
+	while (my $line = <$fd>) {
+		chomp $line;
+		# the header: <SHA-1> <src lineno> <dst lineno> [<lines in group>]
+		# no <lines in group> for subsequent lines in group of lines
 		my ($full_rev, $orig_lineno, $lineno, $group_size) =
-		    /^([0-9a-f]{40}) (\d+) (\d+)(?: (\d+))?$/;
+		   ($line =~ /^([0-9a-f]{40}) (\d+) (\d+)(?: (\d+))?$/);
 		if (!exists $metainfo{$full_rev}) {
 			$metainfo{$full_rev} = {};
 		}
 		my $meta = $metainfo{$full_rev};
-		while (<$fd>) {
-			last if (s/^\t//);
-			if (/^(\S+) (.*)$/) {
+		while (my $data = <$fd>) {
+			chomp $data;
+			last if ($data =~ s/^\t//); # contents of line
+			if ($data =~ /^(\S+) (.*)$/) {
 				$meta->{$1} = $2;
 			}
 		}
-		my $data = $_;
-		chomp $data;
-		my $rev = substr($full_rev, 0, 8);
+		my $short_rev = substr($full_rev, 0, 8);
 		my $author = $meta->{'author'};
-		my %date = parse_date($meta->{'author-time'},
-		                      $meta->{'author-tz'});
+		my %date =
+			parse_date($meta->{'author-time'}, $meta->{'author-tz'});
 		my $date = $date{'iso-tz'};
 		if ($group_size) {
-			$current_color = ++$current_color % $num_colors;
+			$current_color = ($current_color + 1) % $num_colors;
 		}
 		print "<tr id=\"l$lineno\" class=\"$rev_color[$current_color]\">\n";
 		if ($group_size) {
@@ -4654,7 +4661,7 @@ HTML
 			print $cgi->a({-href => href(action=>"commit",
 			                             hash=>$full_rev,
 			                             file_name=>$file_name)},
-			              esc_html($rev));
+			              esc_html($short_rev));
 			print "</td>\n";
 		}
 		my $parent_commit;
@@ -4683,6 +4690,8 @@ HTML
 	print "</div>";
 	close $fd
 		or print "Reading blob failed\n";
+
+	# page footer
 	git_footer_html();
 }
 

Re: [PATCH 3/3] gitweb: A bit of code cleanup in git_blame()

[Jakub Narebski]

Jakub Narebski wrote:

I'm sorry, there should be

  +       my $ftype = "blob";
>         if (!defined $hash) {
>                 $hash = git_get_hash_by_path($hash_base, $file_name, "blob")
>                         or die_error(404, "Error looking up file");
> +       } else {
> +               $ftype = git_get_type($hash);
> +               if ($ftype !~ "blob") {
> +                       die_error(400, "Object is not a blob");
> +               }

-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

Re: [PATCH 3/3] gitweb: A bit of code cleanup in git_blame()

[Junio C Hamano]

Jakub Narebski <jnareb@gmail.com> writes:

> Jakub Narebski wrote:
>
> I'm sorry, there should be
>
>   +       my $ftype = "blob";
>>         if (!defined $hash) {
>>                 $hash = git_get_hash_by_path($hash_base, $file_name, "blob")
>>                         or die_error(404, "Error looking up file");
>> +       } else {
>> +               $ftype = git_get_type($hash);
>> +               if ($ftype !~ "blob") {
>> +                       die_error(400, "Object is not a blob");
>> +               }

I will squash in the following and queue [1/3] and [3/3] to 'pu', as there
seem to be a few comments on [2/3] that look worth addressing.

 gitweb/gitweb.perl |    6 ++++--
 1 files changed, 4 insertions(+), 2 deletions(-)

diff --git c/gitweb/gitweb.perl w/gitweb/gitweb.perl
index d491a1d..ccbf5d4 100755
--- c/gitweb/gitweb.perl
+++ w/gitweb/gitweb.perl
@@ -4585,11 +4585,12 @@ sub git_blame {
 	die_error(404, "Couldn't find base commit") unless $hash_base;
 	my %co = parse_commit($hash_base)
 		or die_error(404, "Commit not found");
+	my $ftype = "blob";
 	if (!defined $hash) {
 		$hash = git_get_hash_by_path($hash_base, $file_name, "blob")
 			or die_error(404, "Error looking up file");
 	} else {
-		my $ftype = git_get_type($hash);
+		$ftype = git_get_type($hash);
 		if ($ftype !~ "blob") {
 			die_error(400, "Object is not a blob");
 		}
@@ -4637,7 +4638,8 @@ HTML
 			$metainfo{$full_rev} = {};
 		}
 		my $meta = $metainfo{$full_rev};
-		while (my $data = <$fd>) {
+		my $data;
+		while ($data = <$fd>) {
 			chomp $data;
 			last if ($data =~ s/^\t//); # contents of line
 			if ($data =~ /^(\S+) (.*)$/) {

Re: [PATCH 3/3] gitweb: A bit of code cleanup in git_blame()

[Luben Tuikov]

--- On Tue, 12/9/08, Jakub Narebski <jnareb@gmail.com> wrote:
> From: Jakub Narebski <jnareb@gmail.com>
> Subject: [PATCH 3/3] gitweb: A bit of code cleanup in git_blame()
> To: git@vger.kernel.org
> Cc: "Luben Tuikov" <ltuikov@yahoo.com>, "Jakub Narebski" <jnareb@gmail.com>
> Date: Tuesday, December 9, 2008, 2:48 PM
> Among others: 
>  * move variable declaration closer to the place it is set
> and used,
>    if possible,
>  * uniquify and simplify coding style a bit, which includes
> removing
>    unnecessary '()'.
>  * check type only if $hash was defined, as otherwise from
> the way
>    git_get_hash_by_path() is called (and works), we know
> that it is
>    a blob,
>  * use modern calling convention for git-blame,
>  * remove unused variable,
>  * don't use implicit variables ($_),
>  * add some comments
> 
> Signed-off-by: Jakub Narebski <jnareb@gmail.com>
Acked-by: Luben Tuikov <ltuikov@yahoo.com>

Looks good.

> ---
> Not stricly necessary... but the code looked not very nice
> 
>  gitweb/gitweb.perl |   65
> ++++++++++++++++++++++++++++++----------------------
>  1 files changed, 37 insertions(+), 28 deletions(-)
> 
> diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
> index 916396a..68aa3f8 100755
> --- a/gitweb/gitweb.perl
> +++ b/gitweb/gitweb.perl
> @@ -4575,28 +4575,32 @@ sub git_tag {
>  }
>  
>  sub git_blame {
> -	my $fd;
> -	my $ftype;
> -
> +	# permissions
>  	gitweb_check_feature('blame')
> -	    or die_error(403, "Blame view not
> allowed");
> +		or die_error(403, "Blame view not allowed");
>  
> +	# error checking
>  	die_error(400, "No file name given") unless
> $file_name;
>  	$hash_base ||= git_get_head_hash($project);
> -	die_error(404, "Couldn't find base commit")
> unless ($hash_base);
> +	die_error(404, "Couldn't find base commit")
> unless $hash_base;
>  	my %co = parse_commit($hash_base)
>  		or die_error(404, "Commit not found");
>  	if (!defined $hash) {
>  		$hash = git_get_hash_by_path($hash_base, $file_name,
> "blob")
>  			or die_error(404, "Error looking up file");
> +	} else {
> +		my $ftype = git_get_type($hash);
> +		if ($ftype !~ "blob") {
> +			die_error(400, "Object is not a blob");
> +		}
>  	}
> -	$ftype = git_get_type($hash);
> -	if ($ftype !~ "blob") {
> -		die_error(400, "Object is not a blob");
> -	}
> -	open ($fd, "-|", git_cmd(), "blame",
> '-p', '--',
> -	      $file_name, $hash_base)
> +
> +	# run git-blame --porcelain
> +	open my $fd, "-|", git_cmd(),
> "blame", '-p',
> +		$hash_base, '--', $file_name
>  		or die_error(500, "Open git-blame failed");
> +
> +	# page header
>  	git_header_html();
>  	my $formats_nav =
>  		$cgi->a({-href =>
> href(action=>"blob", -replay=>1)},
> @@ -4610,40 +4614,43 @@ sub git_blame {
>  	git_print_page_nav('','',
> $hash_base,$co{'tree'},$hash_base, $formats_nav);
>  	git_print_header_div('commit',
> esc_html($co{'title'}), $hash_base);
>  	git_print_page_path($file_name, $ftype, $hash_base);
> -	my @rev_color = (qw(light2 dark2));
> +
> +	# page body
> +	my @rev_color = qw(light2 dark2);
>  	my $num_colors = scalar(@rev_color);
>  	my $current_color = 0;
> -	my $last_rev;
> +	my %metainfo = ();
> +
>  	print <<HTML;
>  <div class="page_body">
>  <table class="blame">
> 
> <tr><th>Commit</th><th>Line</th><th>Data</th></tr>
>  HTML
> -	my %metainfo = ();
> -	while (1) {
> -		$_ = <$fd>;
> -		last unless defined $_;
> + LINE:
> +	while (my $line = <$fd>) {
> +		chomp $line;
> +		# the header: <SHA-1> <src lineno> <dst
> lineno> [<lines in group>]
> +		# no <lines in group> for subsequent lines in
> group of lines
>  		my ($full_rev, $orig_lineno, $lineno, $group_size) =
> -		    /^([0-9a-f]{40}) (\d+) (\d+)(?:
> (\d+))?$/;
> +		   ($line =~ /^([0-9a-f]{40}) (\d+) (\d+)(?:
> (\d+))?$/);
>  		if (!exists $metainfo{$full_rev}) {
>  			$metainfo{$full_rev} = {};
>  		}
>  		my $meta = $metainfo{$full_rev};
> -		while (<$fd>) {
> -			last if (s/^\t//);
> -			if (/^(\S+) (.*)$/) {
> +		while (my $data = <$fd>) {
> +			chomp $data;
> +			last if ($data =~ s/^\t//); # contents of line
> +			if ($data =~ /^(\S+) (.*)$/) {
>  				$meta->{$1} = $2;
>  			}
>  		}
> -		my $data = $_;
> -		chomp $data;
> -		my $rev = substr($full_rev, 0, 8);
> +		my $short_rev = substr($full_rev, 0, 8);
>  		my $author = $meta->{'author'};
> -		my %date = parse_date($meta->{'author-time'},
> -		                      $meta->{'author-tz'});
> +		my %date =
> +			parse_date($meta->{'author-time'},
> $meta->{'author-tz'});
>  		my $date = $date{'iso-tz'};
>  		if ($group_size) {
> -			$current_color = ++$current_color % $num_colors;
> +			$current_color = ($current_color + 1) % $num_colors;
>  		}
>  		print "<tr id=\"l$lineno\"
> class=\"$rev_color[$current_color]\">\n";
>  		if ($group_size) {
> @@ -4654,7 +4661,7 @@ HTML
>  			print $cgi->a({-href =>
> href(action=>"commit",
>  			                             hash=>$full_rev,
>  			                            
> file_name=>$file_name)},
> -			              esc_html($rev));
> +			              esc_html($short_rev));
>  			print "</td>\n";
>  		}
>  		my $parent_commit;
> @@ -4683,6 +4690,8 @@ HTML
>  	print "</div>";
>  	close $fd
>  		or print "Reading blob failed\n";
> +
> +	# page footer
>  	git_footer_html();
>  }

[RFC/PATCH 4/3] gitweb: Incremental blame (proof of concept)

[Jakub Narebski]

This is tweaked up version of Petr Baudis <pasky@suse.cz> patch, which
in turn was tweaked up version of Fredrik Kuivinen <frekui@gmail.com>'s
proof of concept patch.  It adds 'blame_incremental' view, which
incrementally displays line data in blame view using JavaScript (AJAX).

The original patch by Fredrik Kuivinen has been lightly tested in a
couple of browsers (Firefox, Mozilla, Konqueror, Galeon, Opera and IE6).
The next patch by Petr Baudis has been tested in Firefox and Epiphany.
This patch has been lightly tested in Mozilla 1.17.2 and Konqueror
3.5.3.

This patch does not (contrary to the one by Petr Baudis) enable this
view in gitweb: there are no links leading to 'blame_incremental'
action.  You would have to generate URL 'by hand' (e.g. changing 'blame'
or 'blob' in gitweb URL to 'blame_incremental').  Having links in gitweb
lead to this new action (e.g. by rewriting them like in previous patch),
if JavaScript is enabled in browser, is left for later.

Like earlier patch by Per Baudis it avoids code duplication, but it goes
one step further and use git_blame_common for ordinary blame view, for
incremental blame, and for incremental blame data.

How the 'blame_incremental' view works:
* gitweb generates initial info by putting file contents (from
  git-cat-file) together with line numbers in blame table
* then gitweb makes web browser JavaScript engine call startBlame()
  function from blame.js
* startBlame() opens connection to 'blame_data' view, which in turn
  calls "git blame --incremental" for a file, and streams output of
  git-blame to JavaScript (blame.js)
* blame.js updates line info in blame view, coloring it, and updating
  progress info; note that it has to use 3 colors to ensure that
  different neighbour groups have different styles
* when 'blame_data' ends, and blame.js finishes updating line info,
  it fixes colors to match (as far as possible) ordinary 'blame' view,
  and updates generating time info.

This code uses http://ajaxpatterns.org/HTTP_Streaming pattern.

It deals with streamed 'blame_data' server error by notifying about them
in the progress info area (just in case).

This patch adds GITWEB_BLAMEJS compile configuration option, and
modifies git-instaweb.sh to take blame.js into account, but it does not
update gitweb/README file (as it is only proof of concept patch).  The
code for git-instaweb.sh was taken from Pasky's patch.

While at it, this patch uniquifies td.dark and td.dark2 style: they
differ only in that td.dark2 doesn't have style for :hover.


This patch also adds showing time (in seconds) it took to generate
a page in page footer (based on example code by Pasky), even though
it is independent change, to be able to evaluate incremental blame in
gitweb better.  In proper patch series it would be independent commit;
and it probably would provide fallback if Time::HiRes is not available
(by e.g. not showing generating time info), even though this is
unlikely.

Cc: Fredrik Kuivinen <frekui@gmail.com>
Signed-off-by: Petr Baudis <pasky@suse.cz>
Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
I'm sorry if you have received duplicate copy of this message...

NOTE: This patch is RFC proof of concept patch!: it should be split
onto many smaller patches for easy review (and bug finding) in version
meant to be applied.

[Please tell me if some of info below should be put in the commit
 message instead of here]

Patch by Petr Baudis this one is based on:
  http://permalink.gmane.org/gmane.comp.version-control.git/56657

Original patch by Fredrik Kuivinen:
  http://article.gmane.org/gmane.comp.version-control.git/41361

Snippet adding 'generated in' to gitweb, by Petr Baudis:
  http://article.gmane.org/gmane.comp.version-control.git/83306

Should I post interdiff to Petr Baudis patch, and comments about
difference between them? This post is quite long as it is now...


Differences between 'blame' and 'blame_incremental' output:
* Line number links in 'blame' lead to parent of blamed commit, i.e. to
  the view where given line _changed_; this behavior was introduced in
  244a70e (Blame "linenr" link jumps to previous state at "orig_lineno")
  by Luben Tuikov on Jan 2008 to make data mining possible.

  Currently 'blame_incremental' lead to version at blamed commit; this
  would be hard to change without opening another stream, or without
  having gitweb accept <sha1>^ for 'hb' (hash_base) parameter.

* The title attribute (shown in popup on mouseover) for "sha1" cell
  for 'blame_incremental' view looks like the following:
    'Kay Sievers, 2005-08-07 19:49:46 +0000 (21:49:46 +0200)'
  more like the date format used in 'commit' view, rather than shorter
    'Kay Sievers, 2005-08-07 21:49:46 +0200'

  This is a bit of accident, as in originla patch(es) there was error
  where the time and date shown were for UTC (GMT), and not for shown
  together timezone, i.e.
    'Kay Sievers, 2005-08-07 19:49:46 +0200'
  and I have added local time instead of replacing it. But perhaps it
  is 'blame' view that should change format? 

* In 'blame_incremental' the cell (<td>) with sha1 has rowspan
  attribute set even if it is at its default value rowspan="1".
  This should be very easy to fix.

* The 'blame_incremental' view has new feature inspired by output of
  "git gui blame <file>", that if group of lines blamed to the same
  commit has more than two lines, then below shortened sha-1 of a
  commit it is shown shortened author (initials, in uppercase).

  If you think it is worth it, this feature should be fairly easy to
  port to ordinary non-incremental 'blame' view.

* Sometimes "git blame --porcelain" and "git blame --incremental" can
  give different output.  Compare for example 'blame' and
  'blame_incremental' view for GIT-VERSION-GEN in git.git repository,
  and note that in 'blame_incremental' the last two groups are for the
  same commit (compare bottom parts of pages).  'blame_incremental'
  currently does not consolidate groups; if it did that, it should do
  it before fixColors()

* During filling blame info 'blame_incremental' view uses three colors
  (three styles: color1, color2, color3) instead of two color zebra
  coloring (two styles: light2, dark2) to ensure that the color of
  current group is different from both of its neighbours.

  This is non-issue: this is fixed at the end (although intermediate
  versions of blame.js script didn't fo fixColors() to make it easier
  to check if the 3-coloring is correct).

* The 'blame_incremental' view contains unique progress bar and
  progress report; perhaps they should vanish after succesfull loading
  of all data?


Bugs and suspected bugs in Mozilla 1.17.2 (my main browser); perhaps
those got corrected, as 1.17.2 is ancient (Gecko/20050923) version:
* HTML 4.01 Transitional specification at W3C states only ID and NAME
  tokens must begin with a letter ([A-Za-z]); it looks like class
  named "1" or "2" or "3" has style specified by CSS ignored.

* With XHTML 1.0 DTD and application/xhtml+xml content type, if there
  were <col /> elements in blame table (currently commented out in the
  source), then row with column headings (with <td> elements) was not
  visible.

* With XHTML 1.0 DTD and application/xhtml+xml content type, if there
  was an error in JavaScript, instead of having it visible as error
  message in JavaScript Console, Mozilla behaved as if the script
  wasn't there at all.

* With XHTML 1.0 DTD and application/xhtml+xml content type, setting
  innerHTML doesn't work: it raises cryptic JavaScript exception:

    Component returned failure code: 0x80004005 (NS_ERROR_FAILURE)
    [nsIDOMNSHTMLElement.innerHTML]	

  Correct solution would be to use only DOM, or rather depending on
  what web browser supports, use either .innerHTML (which is
  proprietary Microsoft extension) or DOM (which is standard but not
  all browser use it).  Current *workaround* is to simply always use
  'text/html' content type, and HTML 4.01 DTD.

  I wonder whether innerHTML or DOM is faster; and how many of web
  browser implements other similar properties like innerText,
  outerHTML and insertAdjacentHTML.

* XHTML 1.0 doesn't allow for trick with using HTML comments to hide
  contents of <script> element from old browsers, as XML compliant
  browser can remove XML comments before seeing JavaScript, so we
  don't use it.  Besides I think this issue is irrelevant now.


P.S. I have removed a few spurious one line change chunks from
gitweb/gitweb.perl, which were done to not confuse Perl syntax
highlighting (lazy-lock-mode) from cperl-mode in GNU Emacs 21.4.1,
and to not confuse imenu parser in GNU Emacs (which allow to go to
specified subroutine, and to display which-function-info in
modeline), so diffstat is slightly out of sync.

Those were #" or #' after regexp with single unescaped " or ',
and ($) in definition of "sub S_ISGITLINK($)".

P.P.S. What is the stance for copyrigth assesments in the files
for git code, like the ones in gitweb/gitweb.perl and gitweb/blame.js?

P.P.P.S. Should I use Signed-off-by from Pasky and Fredrik if I based
my code on theirs, and if they all signed their patches?

 Makefile           |    4 +
 git-instaweb.sh    |    6 +
 gitweb/blame.js    |  398 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 gitweb/gitweb.css  |   27 +++-
 gitweb/gitweb.perl |  252 ++++++++++++++++++++++-----------
 5 files changed, 597 insertions(+), 90 deletions(-)
 create mode 100644 gitweb/blame.js

diff --git a/Makefile b/Makefile
index 5158197..05ac246 100644
--- a/Makefile
+++ b/Makefile
@@ -218,6 +218,7 @@ GITWEB_HOMETEXT = indextext.html
 GITWEB_CSS = gitweb.css
 GITWEB_LOGO = git-logo.png
 GITWEB_FAVICON = git-favicon.png
+GITWEB_BLAMEJS = blame.js
 GITWEB_SITE_HEADER =
 GITWEB_SITE_FOOTER =
 
@@ -1209,6 +1210,7 @@ gitweb/gitweb.cgi: gitweb/gitweb.perl
 	    -e 's|++GITWEB_CSS++|$(GITWEB_CSS)|g' \
 	    -e 's|++GITWEB_LOGO++|$(GITWEB_LOGO)|g' \
 	    -e 's|++GITWEB_FAVICON++|$(GITWEB_FAVICON)|g' \
+	    -e 's|++GITWEB_BLAMEJS++|$(GITWEB_BLAMEJS)|g' \
 	    -e 's|++GITWEB_SITE_HEADER++|$(GITWEB_SITE_HEADER)|g' \
 	    -e 's|++GITWEB_SITE_FOOTER++|$(GITWEB_SITE_FOOTER)|g' \
 	    $< >$@+ && \
@@ -1224,6 +1226,8 @@ git-instaweb: git-instaweb.sh gitweb/gitweb.cgi gitweb/gitweb.css
 	    -e '/@@GITWEB_CGI@@/d' \
 	    -e '/@@GITWEB_CSS@@/r gitweb/gitweb.css' \
 	    -e '/@@GITWEB_CSS@@/d' \
+	    -e '/@@GITWEB_BLAMEJS@@/r gitweb/blame.js' \
+	    -e '/@@GITWEB_BLAMEJS@@/d' \
 	    -e 's|@@PERL@@|$(PERL_PATH_SQ)|g' \
 	    $@.sh > $@+ && \
 	chmod +x $@+ && \
diff --git a/git-instaweb.sh b/git-instaweb.sh
index 0843372..f41354c 100755
--- a/git-instaweb.sh
+++ b/git-instaweb.sh
@@ -268,6 +268,12 @@ gitweb_css () {
 EOFGITWEB
 }
 
+gitweb_blamejs () {
+	cat > "$1" <<\EOFGITWEB
+@@GITWEB_BLAMEJS@@
+EOFGITWEB
+}
+
 gitweb_cgi "$GIT_DIR/gitweb/gitweb.cgi"
 gitweb_css "$GIT_DIR/gitweb/gitweb.css"
 
diff --git a/gitweb/blame.js b/gitweb/blame.js
new file mode 100644
index 0000000..197d615
--- /dev/null
+++ b/gitweb/blame.js
@@ -0,0 +1,398 @@
+// Copyright (C) 2007, Fredrik Kuivinen <frekui@gmail.com>
+
+var DEBUG = 0;
+function debug(str) {
+	if (DEBUG)
+		alert(str);
+}
+
+function createRequestObject() {
+	var ro;
+	if (window.XMLHttpRequest) {
+		ro = new XMLHttpRequest();
+	} else {
+		ro = new ActiveXObject("Microsoft.XMLHTTP");
+	}
+	if (!ro)
+		debug("Couldn't start XMLHttpRequest object");
+	return ro;
+}
+
+var http;
+var baseUrl;
+
+// 'commits' is an associative map. It maps SHA1s to Commit objects.
+var commits = new Object();
+
+function Commit(sha1) {
+	this.sha1 = sha1;
+}
+
+// convert month or day of the month to string, padding it with
+// '0' (zero) to two characters width if necessary
+function zeroPad(n) {
+	if (n < 10)
+		return '0' + n;
+	else
+		return n.toString();
+}
+
+function spacePad(n,width) {
+	var scale = 1;
+	var str = '';
+
+	while (width > 1) {
+		scale *= 10;
+		if (n < scale)
+			str += '&nbsp;';
+		width--;
+	}
+	return str + n.toString();
+}
+
+
+var blamedLines = 0;
+var totalLines  = '???';
+var div_progress_bar;
+var div_progress_info;
+
+function countLines() {
+	var table = document.getElementById('blame_table');
+	if (!table)
+		table = document.getElementsByTagName('table').item(0);
+
+	if (table)
+		return table.getElementsByTagName('tr').length - 1; // for header
+	else
+		return '...';
+}
+
+function updateProgressInfo() {
+	if (!div_progress_info)
+		div_progress_info = document.getElementById('progress_info');
+	if (!div_progress_bar)
+		div_progress_bar = document.getElementById('progress_bar');
+	if (!div_progress_info && !div_progress_bar)
+		return;
+
+	var percentage = Math.floor(100.0*blamedLines/totalLines);
+
+	if (div_progress_info) {
+		div_progress_info.innerHTML  = blamedLines + ' / ' + totalLines
+			+ ' ('+spacePad(percentage,3)+'%)';
+	}
+
+	if (div_progress_bar) {
+		div_progress_bar.setAttribute('style', 'width: '+percentage+'%;');
+	}
+}
+
+var colorRe = new RegExp('color([0-9]*)');
+/* return N if <tr class="colorN">, otherwise return null */
+function getColorNo(tr) {
+	var className = tr.getAttribute('class');
+	if (className) {
+		match = colorRe.exec(className);
+		if (match)
+			return parseInt(match[1]);
+	}
+	return null;
+}
+
+function findColorNo(tr_prev, tr_next) {
+	var color_prev;
+	var color_next;
+
+	if (tr_prev)
+		color_prev = getColorNo(tr_prev);
+	if (tr_next)
+		color_next = getColorNo(tr_next);
+
+	if (!color_prev && !color_next)
+		return 1;
+	if (color_prev == color_next)
+		return ((color_prev % 3) + 1);
+	if (!color_prev)
+		return ((color_next % 3) + 1);
+	if (!color_next)
+		return ((color_prev % 3) + 1);
+	return (3 - ((color_prev + color_next) % 3));
+}
+
+var tzRe = new RegExp('^([+-][0-9][0-9])([0-9][0-9])$');
+// called for each blame entry, as soon as it finishes
+function handleLine(commit) {
+	/* This is the structure of the HTML fragment we are working
+	   with:
+	   
+	   <tr id="l123" class="">
+	     <td class="sha1" title=""><a href=""></a></td>
+	     <td class="linenr"><a class="linenr" href="">123</a></td>
+	     <td class="pre"># times (my ext3 doesn&#39;t).</td>
+	   </tr>
+	*/
+
+	var resline = commit.resline;
+
+	if (!commit.info) {
+		var date = new Date();
+		date.setTime(commit.authorTime * 1000); // milliseconds
+		var dateStr =
+			date.getUTCFullYear() + '-'
+			+ zeroPad(date.getUTCMonth()+1) + '-'
+			+ zeroPad(date.getUTCDate());
+		var timeStr =
+			zeroPad(date.getUTCHours()) + ':'
+			+ zeroPad(date.getUTCMinutes()) + ':'
+			+ zeroPad(date.getUTCSeconds());
+
+		var localDate = new Date();
+		var match = tzRe.exec(commit.authorTimezone);
+		localDate.setTime(1000 * (commit.authorTime
+			+ (parseInt(match[1],10)*3600 + parseInt(match[2],10)*60)));
+		var localTimeStr =
+			zeroPad(localDate.getUTCHours()) + ':'
+			+ zeroPad(localDate.getUTCMinutes()) + ':'
+			+ zeroPad(localDate.getUTCSeconds());
+
+		/* e.g. 'Kay Sievers, 2005-08-07 19:49:46 +0000 (21:49:46 +0200)' */
+		commit.info = commit.author + ', ' + dateStr + ' '
+			+ timeStr + ' +0000'
+			+ ' (' + localTimeStr + ' ' + commit.authorTimezone + ')';
+	}
+
+	var color = findColorNo(
+		document.getElementById('l'+(resline-1)),
+		document.getElementById('l'+(resline+commit.numlines))
+	);
+
+
+	for (var i = 0; i < commit.numlines; i++) {
+		var tr = document.getElementById('l'+resline);
+		if (!tr) {
+			debug('tr is null! resline: ' + resline);
+			break;
+		}
+		/*
+			<tr id="l123" class="">
+			  <td class="sha1" title=""><a href=""></a></td>
+			  <td class="linenr"><a class="linenr" href="">123</a></td>
+			  <td class="pre"># times (my ext3 doesn&#39;t).</td>
+			</tr>
+		*/
+		var td_sha1  = tr.firstChild;
+		var a_sha1   = td_sha1.firstChild;
+		var a_linenr = td_sha1.nextSibling.firstChild;
+
+		/* <tr id="l123" class=""> */
+		if (color) {
+			tr.setAttribute('class', 'color'+color.toString());
+			// Internet Explorer needs this
+			//tr.setAttribute('className', color.toString);
+		}
+		/* <td class="sha1" title="?" rowspan="?"><a href="?">?</a></td> */
+		if (i == 0) {
+			td_sha1.title = commit.info;
+			td_sha1.setAttribute('rowspan', commit.numlines);
+
+			a_sha1.href = baseUrl + '?a=commit;h=' + commit.sha1;
+			a_sha1.innerHTML = commit.sha1.substr(0, 8);
+			if (commit.numlines >= 2) {
+				var br   = document.createElement("br");
+				var text = document.createTextNode(commit.author.match(/\b([A-Z])\B/g).join(''));
+				if (br && text) {
+					td_sha1.appendChild(br);
+					td_sha1.appendChild(text);
+				}
+			}
+		} else {
+			tr.removeChild(td_sha1);
+		}
+
+		/* <td class="linenr"><a class="linenr" href="?">123</a></td> */
+		a_linenr.href = baseUrl + '?a=blame;hb=' + commit.sha1
+			+ ';f=' + commit.filename + '#l' + (commit.srcline + i);
+
+		resline++;
+		blamedLines++;
+
+		//updateProgressInfo();
+	}
+}
+
+function startOfGroup(tr) {
+	return tr.firstChild.getAttribute('class') == 'sha1';
+}
+
+function fixColors() {
+	var colorClasses = ['light2', 'dark2'];
+	var linenum = 1;
+	var tr;
+	var colorClass = 0;
+
+	while ((tr = document.getElementById('l'+linenum))) {
+		if (startOfGroup(tr, linenum, document)) {
+			colorClass = (colorClass + 1) % 2;
+		}
+		tr.setAttribute('class', colorClasses[colorClass]);
+		// Internet Explorer needs this
+		tr.setAttribute('className', colorClasses[colorClass]);
+		linenum++;
+	}
+}
+
+var t_interval_server = '';
+var t0 = new Date();
+
+function writeTimeInterval() {
+	var info = document.getElementById('generate_time');
+	if (!info)
+		return;
+	var t1 = new Date();
+
+	info.innerHTML += ' + '
+		+ t_interval_server+'s server (blame_data) / '
+		+ (t1.getTime() - t0.getTime())/1000 + 's client (JavaScript)';
+}
+
+// ----------------------------------------------------------------------
+
+var prevDataLength = -1;
+var nextLine = 0;
+var inProgress = false;
+
+var sha1Re = new RegExp('([0-9a-f]{40}) ([0-9]+) ([0-9]+) ([0-9]+)');
+var infoRe = new RegExp('([a-z-]+) ?(.*)');
+var endRe = new RegExp('END ?(.*)');
+var curCommit = new Commit();
+
+var pollTimer = null;
+
+function handleResponse() {
+	debug('handleResp ready: ' + http.readyState
+	      + ' respText null?: ' + (http.responseText === null)
+	      + ' progress: ' + inProgress);
+
+	if (http.readyState != 4 && http.readyState != 3)
+		return;
+
+	// the server stream is incorrect
+	if (http.readyState == 3 && http.status != 200)
+		return;
+	if (http.readyState == 4 && http.status != 200) {
+		if (!div_progress_info)
+			div_progress_info = document.getElementById('progress_info');
+
+		if (div_progress_info) {
+			div_progress_info.setAttribute('class', 'error');
+			div_progress_info.innerHTML =
+				http.status+' - Error contacting server\n';
+		} else {
+			document.write("<b>ERROR:</b> HTTP status is "+http.status+"<br />\n");
+		}
+
+		clearInterval(pollTimer);
+		inProgress = false;
+	}
+
+	// In konqueror http.responseText is sometimes null here...
+	if (http.responseText === null)
+		return;
+
+	/*
+	var resp = document.getElementById('state');
+	if (resp) {
+		resp.innerHTML = http.readyState + ' : ' + http.status
+			+ '<br />len = ' + http.responseText.length
+			+ '; inProgress='+inProgress;
+		//inProgress = true;
+	}
+	*/
+
+	if (inProgress)
+		return;
+	else
+		inProgress = true;
+
+	while (prevDataLength != http.responseText.length) {
+		if (http.readyState == 4
+		    && prevDataLength == http.responseText.length) {
+			break;
+		}
+
+		prevDataLength = http.responseText.length;
+		var response = http.responseText.substring(nextLine);
+		var lines = response.split('\n');
+		nextLine = nextLine + response.lastIndexOf('\n') + 1;
+		if (response[response.length-1] != '\n') {
+			lines.pop();
+		}
+
+		for (var i = 0; i < lines.length; i++) {
+			var match = sha1Re.exec(lines[i]);
+			if (match) {
+				var sha1 = match[1];
+				var srcline = parseInt(match[2]);
+				var resline = parseInt(match[3]);
+				var numlines = parseInt(match[4]);
+				var c = commits[sha1];
+				if (!c) {
+					c = new Commit(sha1);
+					commits[sha1] = c;
+				}
+
+				c.srcline = srcline;
+				c.resline = resline;
+				c.numlines = numlines;
+				curCommit = c;
+			} else if ((match = infoRe.exec(lines[i]))) {
+				var info = match[1];
+				var data = match[2];
+				if (info == 'filename') {
+					curCommit.filename = data;
+					handleLine(curCommit);
+					updateProgressInfo();
+				} else if (info == 'author') {
+					curCommit.author = data;
+				} else if (info == 'author-time') {
+					curCommit.authorTime = parseInt(data);
+				} else if (info == 'author-tz') {
+					curCommit.authorTimezone = data;
+				}
+			} else if ((match = endRe.exec(lines[i]))) {
+				t_interval_server = match[1];
+				debug('END: '+lines[i]);
+			} else if (lines[i] != '') {
+				debug('malformed line: ' + lines[i]);
+			}
+		}
+	}
+
+	if (http.readyState == 4 &&
+	    prevDataLength == http.responseText.length) {
+		clearInterval(pollTimer);
+
+		fixColors();
+		writeTimeInterval();
+	}
+
+	inProgress = false;
+}
+
+function startBlame(blamedataUrl, bUrl) {
+	debug('startBlame('+blamedataUrl+', '+bUrl+')');
+
+	t0 = new Date();
+	baseUrl = bUrl;
+	totalLines = countLines();
+	updateProgressInfo();
+
+	http = createRequestObject();
+	http.open('get', blamedataUrl);
+	http.onreadystatechange = handleResponse;
+	http.send(null);
+
+	pollTimer = setInterval(handleResponse, 1000);
+}
+
+// end of blame.js
diff --git a/gitweb/gitweb.css b/gitweb/gitweb.css
index a01eac8..e359618 100644
--- a/gitweb/gitweb.css
+++ b/gitweb/gitweb.css
@@ -223,11 +223,7 @@ tr.light:hover {
 	background-color: #edece6;
 }
 
-tr.dark {
-	background-color: #f6f6f0;
-}
-
-tr.dark2 {
+tr.dark, tr.dark2 {
 	background-color: #f6f6f0;
 }
 
@@ -235,6 +231,14 @@ tr.dark:hover {
 	background-color: #edece6;
 }
 
+tr.color1:hover { background-color: #e6ede6; }
+tr.color2:hover { background-color: #e6e6ed; }
+tr.color3:hover { background-color: #ede6e6; }
+
+tr.color1 { background-color: #f6fff6; }
+tr.color2 { background-color: #f6f6ff; }
+tr.color3 { background-color: #fff6f6; }
+
 td {
 	padding: 2px 5px;
 	font-size: 100%;
@@ -255,7 +259,7 @@ td.sha1 {
 	font-family: monospace;
 }
 
-td.error {
+.error {
 	color: red;
 	background-color: yellow;
 }
@@ -326,6 +330,17 @@ td.mode {
 	font-family: monospace;
 }
 
+/* progress of blame_interactive */
+div#progress_bar {
+	height: 2px;
+	margin-bottom: -2px;
+	background-color: #d8d9d0;
+}
+div#progress_info {
+	float: right;
+	text-align: right;
+}
+
 /* styling of diffs (patchsets): commitdiff and blobdiff views */
 div.diff.header,
 div.diff.extended_header {
diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
index 4987fdc..774bcc6 100755
--- a/gitweb/gitweb.perl
+++ b/gitweb/gitweb.perl
@@ -18,6 +18,9 @@ use File::Find qw();
 use File::Basename qw(basename);
 binmode STDOUT, ':utf8';
 
+use Time::HiRes qw(gettimeofday tv_interval);
+our $t0 = [gettimeofday];
+
 BEGIN {
 	CGI->compile() if $ENV{'MOD_PERL'};
 }
@@ -74,6 +77,8 @@ our $stylesheet = undef;
 our $logo = "++GITWEB_LOGO++";
 # URI of GIT favicon, assumed to be image/png type
 our $favicon = "++GITWEB_FAVICON++";
+# URI of blame.js
+our $blamejs = "++GITWEB_BLAMEJS++";
 
 # URI and label (title) of GIT logo link
 #our $logo_url = "http://www.kernel.org/pub/software/scm/git/docs/";
@@ -493,6 +498,8 @@ our %cgi_param_mapping = @cgi_param_mapping;
 # we will also need to know the possible actions, for validation
 our %actions = (
 	"blame" => \&git_blame,
+	"blame_incremental" => \&git_blame_incremental,
+	"blame_data" => \&git_blame_data,
 	"blobdiff" => \&git_blobdiff,
 	"blobdiff_plain" => \&git_blobdiff_plain,
 	"blob" => \&git_blob,
@@ -2874,13 +2881,13 @@ sub git_header_html {
 	# 'application/xhtml+xml', otherwise send it as plain old 'text/html'.
 	# we have to do this because MSIE sometimes globs '*/*', pretending to
 	# support xhtml+xml but choking when it gets what it asked for.
-	if (defined $cgi->http('HTTP_ACCEPT') &&
-	    $cgi->http('HTTP_ACCEPT') =~ m/(,|;|\s|^)application\/xhtml\+xml(,|;|\s|$)/ &&
-	    $cgi->Accept('application/xhtml+xml') != 0) {
-		$content_type = 'application/xhtml+xml';
-	} else {
+	#if (defined $cgi->http('HTTP_ACCEPT') &&
+	#    $cgi->http('HTTP_ACCEPT') =~ m/(,|;|\s|^)application\/xhtml\+xml(,|;|\s|$)/ &&
+	#    $cgi->Accept('application/xhtml+xml') != 0) {
+	#	$content_type = 'application/xhtml+xml';
+	#} else {
 		$content_type = 'text/html';
-	}
+	#}
 	print $cgi->header(-type=>$content_type, -charset => 'utf-8',
 	                   -status=> $status, -expires => $expires);
 	my $mod_perl_version = $ENV{'MOD_PERL'} ? " $ENV{'MOD_PERL'}" : '';
@@ -3042,6 +3049,14 @@ sub git_footer_html {
 	}
 	print "</div>\n"; # class="page_footer"
 
+	print "<div class=\"page_footer\">\n";
+	print 'This page took '.
+	      '<span id="generate_time" class="time_span">'.
+	      tv_interval($t0, [gettimeofday]).'s'.
+	      '</span>'.
+	      " to generate.\n";
+	print "</div>\n"; # class="page_footer"
+
 	if (-f $site_footer) {
 		insert_file($site_footer);
 	}
@@ -4574,7 +4589,9 @@ sub git_tag {
 	git_footer_html();
 }
 
-sub git_blame {
+sub git_blame_common {
+	my $format = shift || 'porcelain';
+
 	# permissions
 	gitweb_check_feature('blame')
 		or die_error(403, "Blame view not allowed");
@@ -4596,10 +4613,36 @@ sub git_blame {
 		}
 	}
 
-	# run git-blame --porcelain
-	open my $fd, "-|", git_cmd(), "blame", '-p',
-		$hash_base, '--', $file_name
-		or die_error(500, "Open git-blame failed");
+	my $fd;
+	if ($format eq 'incremental') {
+		# get file contents (as base)
+		open $fd, "-|", git_cmd(), 'cat-file', 'blob', $hash
+			or die_error(500, "Open git-cat-file failed");
+	} elsif ($format eq 'data') {
+		# run git-blame --incremental
+		open $fd, "-|", git_cmd(), "blame", "--incremental",
+			$hash_base, "--", $file_name
+			or die_error(500, "Open git-blame --incremental failed");
+	} else {
+		# run git-blame --porcelain
+		open $fd, "-|", git_cmd(), "blame", '-p',
+			$hash_base, '--', $file_name
+			or die_error(500, "Open git-blame --porcelain failed");
+	}
+
+	# incremental blame data returns early
+	if ($format eq 'data') {
+		print $cgi->header(
+			-type=>"text/plain", -charset => "utf-8",
+			-status=> "200 OK");
+		local $| = 1; # output autoflush
+		print while <$fd>;
+		close $fd
+			or print "ERROR $!\n";
+		print "END ".tv_interval($t0, [gettimeofday])."\n";
+
+		return;
+	}
 
 	# page header
 	git_header_html();
@@ -4610,93 +4653,134 @@ sub git_blame {
 		$cgi->a({-href => href(action=>"history", -replay=>1)},
 		        "history") .
 		" | " .
-		$cgi->a({-href => href(action=>"blame", file_name=>$file_name)},
+		$cgi->a({-href => href(action=>$action, file_name=>$file_name)},
 		        "HEAD");
 	git_print_page_nav('','', $hash_base,$co{'tree'},$hash_base, $formats_nav);
 	git_print_header_div('commit', esc_html($co{'title'}), $hash_base);
 	git_print_page_path($file_name, $ftype, $hash_base);
 
 	# page body
+	print qq!<div id="progress_bar" style="width: 100%; background-color: yellow"></div>\n!
+		if ($format eq 'incremental');
+	print qq!<div class="page_body">\n!;
+	print qq!<div id="progress_info">... / ...</div>\n!
+		if ($format eq 'incremental');
+	print qq!<table id="blame_table" class="blame" width="100%">\n!.
+	      #qq!<col width="5.5em" /><col width="2.5em" /><col width="*" />\n!.
+	      qq!<tr><th>Commit</th><th>Line</th><th>Data</th></tr>\n!;
+
 	my @rev_color = qw(light2 dark2);
 	my $num_colors = scalar(@rev_color);
 	my $current_color = 0;
-	my %metainfo = ();
 
-	print <<HTML;
-<div class="page_body">
-<table class="blame">
-<tr><th>Commit</th><th>Line</th><th>Data</th></tr>
-HTML
- LINE:
-	while (my $line = <$fd>) {
-		chomp $line;
-		# the header: <SHA-1> <src lineno> <dst lineno> [<lines in group>]
-		# no <lines in group> for subsequent lines in group of lines
-		my ($full_rev, $orig_lineno, $lineno, $group_size) =
-		   ($line =~ /^([0-9a-f]{40}) (\d+) (\d+)(?: (\d+))?$/);
-		if (!exists $metainfo{$full_rev}) {
-			$metainfo{$full_rev} = {};
-		}
-		my $meta = $metainfo{$full_rev};
-		my $data; # last line is used later
-		while ($data = <$fd>) {
-			chomp $data;
-			last if ($data =~ s/^\t//); # contents of line
-			if ($data =~ /^(\S+) (.*)$/) {
-				$meta->{$1} = $2;
-			}
-		}
-		my $short_rev = substr($full_rev, 0, 8);
-		my $author = $meta->{'author'};
-		my %date =
-			parse_date($meta->{'author-time'}, $meta->{'author-tz'});
-		my $date = $date{'iso-tz'};
-		if ($group_size) {
-			$current_color = ($current_color + 1) % $num_colors;
-		}
-		print "<tr id=\"l$lineno\" class=\"$rev_color[$current_color]\">\n";
-		if ($group_size) {
-			print "<td class=\"sha1\"";
-			print " title=\"". esc_html($author) . ", $date\"";
-			print " rowspan=\"$group_size\"" if ($group_size > 1);
-			print ">";
-			print $cgi->a({-href => href(action=>"commit",
-			                             hash=>$full_rev,
-			                             file_name=>$file_name)},
-			              esc_html($short_rev));
-			print "</td>\n";
+	if ($format eq 'incremental') {
+		my $color_class = $rev_color[$current_color];
+
+		#contents of a file
+		my $linenr = 0;
+	LINE:
+		while (my $line = <$fd>) {
+			chomp $line;
+			$linenr++;
+
+			print qq!<tr id="l$linenr" class="$color_class">!.
+			      qq!<td class="sha1"><a href=""></a></td>!.
+			      qq!<td class="linenr">!.
+			      qq!<a class="linenr" href="">$linenr</a></td>!;
+			print qq!<td class="pre">! . esc_html($line) . "</td>\n";
+			print qq!</tr>\n!;
 		}
-		my $parent_commit;
-		if (!exists $meta->{'parent'}) {
-			open (my $dd, "-|", git_cmd(), "rev-parse", "$full_rev^")
-				or die_error(500, "Open git-rev-parse failed");
-			$parent_commit = <$dd>;
-			close $dd;
-			chomp($parent_commit);
-			$meta->{'parent'} = $parent_commit;
-		} else {
-			$parent_commit = $meta->{'parent'};
-		}
-		my $blamed = href(action => 'blame',
-		                  file_name => $meta->{'filename'},
-		                  hash_base => $parent_commit);
-		print "<td class=\"linenr\">";
-		print $cgi->a({ -href => "$blamed#l$orig_lineno",
-		                -class => "linenr" },
-		              esc_html($lineno));
-		print "</td>";
-		print "<td class=\"pre\">" . esc_html($data) . "</td>\n";
-		print "</tr>\n";
-	}
-	print "</table>\n";
-	print "</div>";
+
+	} else { # porcelain, i.e. ordinary blame
+		my %metainfo = (); # saves information about commits
+
+		# blame data
+	LINE:
+		while (my $line = <$fd>) {
+			chomp $line;
+			# the header: <SHA-1> <src lineno> <dst lineno> [<lines in group>]
+			# no <lines in group> for subsequent lines in group of lines
+			my ($full_rev, $orig_lineno, $lineno, $group_size) =
+				($line =~ /^([0-9a-f]{40}) (\d+) (\d+)(?: (\d+))?$/);
+			$metainfo{$full_rev} ||= {};
+			my $meta = $metainfo{$full_rev};
+			my $data; # last line is used later
+			while ($data = <$fd>) {
+				chomp $data;
+				last if ($data =~ s/^\t//); # contents of line
+				if ($data =~ /^(\S+) (.*)$/) {
+					$meta->{$1} = $2;
+				}
+			}
+			my $short_rev = substr($full_rev, 0, 8);
+			my $author = $meta->{'author'};
+			my %date =
+				parse_date($meta->{'author-time'}, $meta->{'author-tz'});
+			my $date = $date{'iso-tz'};
+			if ($group_size) {
+				$current_color = ($current_color + 1) % $num_colors;
+			}
+			print qq!<tr id="l$lineno" class="$rev_color[$current_color]">\n!;
+			if ($group_size) {
+				print qq!<td class="sha1"!.
+				      qq! title="!. esc_html($author) . qq!, $date"!;
+				print qq! rowspan="$group_size"! if ($group_size > 1);
+				print qq!>!;
+				print $cgi->a({-href => href(action=>"commit",
+				                             hash=>$full_rev,
+				                             file_name=>$file_name)},
+				              esc_html($short_rev));
+				print qq!</td>\n!;
+			}
+			if (!exists $meta->{'parent'}) {
+				open my $dd, "-|", git_cmd(), "rev-parse", "$full_rev^"
+					or die_error(500, "Open git-rev-parse failed");
+				$meta->{'parent'} = <$dd>;
+				close $dd;
+				chomp $meta->{'parent'};
+			}
+			my $blamed = href(action => 'blame',
+			                  file_name => $meta->{'filename'},
+			                  hash_base => $meta->{'parent'});
+			print qq!<td class="linenr">!.
+			       $cgi->a({ -href => "$blamed#l$orig_lineno",
+			                -class => "linenr" },
+			               esc_html($lineno)).
+			      qq!</td>!;
+			print qq!<td class="pre">! . esc_html($data) . "</td>\n";
+			print qq!</tr>\n!;
+		}
+	}
+
+	# footer
+	print "</table>\n"; # class="blame"
+	print "</div>\n";   # class="blame_body"
 	close $fd
 		or print "Reading blob failed\n";
 
-	# page footer
+	if ($format eq 'incremental') {
+		print qq!<script type="text/javascript" src="$blamejs"></script>\n!.
+		      qq!<script type="text/javascript">\n!.
+		      qq!startBlame("!. href(action=>"blame_data", -replay=>1) .qq!",\n!.
+		      qq!           "$my_url");\n!.
+		      qq!</script>\n!;
+	}
+
 	git_footer_html();
 }
 
+sub git_blame {
+	git_blame_common();
+}
+
+sub git_blame_incremental {
+	git_blame_common('incremental');
+}
+
+sub git_blame_data {
+	git_blame_common('data');
+}
+
 sub git_tags {
 	my $head = git_get_head_hash($project);
 	git_header_html();

-- 
Stacked GIT 0.14.3
git version 1.6.0.4

Re: [RFC/PATCH 4/3] gitweb: Incremental blame (proof of concept)

[Junio C Hamano]

Jakub Narebski <jnareb@gmail.com> writes:

> NOTE: This patch is RFC proof of concept patch!: it should be split
> onto many smaller patches for easy review (and bug finding) in version
> meant to be applied.

Hmm, the comments an RFC requests for would certainly be based on reviews
of the patch in question, so if the patch is known to be unsuitable for
reviewing, what would that tell us, I wonder ;-)?

Among the 700 lines added/deleted, 400 lines are from a single new file,
so what may benefit from splitting would be the changes to gitweb.perl but
it does not look so bad (I haven't really read the patch, though).

> Differences between 'blame' and 'blame_incremental' output:

Hmm, are these by design in the sense that "when people are getting
incremental blame output, the normal blame output format is unsuitable for
such and such reasons and that is why there have to be these differences",
or "the code happens to produce slightly different results because it is
implemented differently; the differences are listed here as due
diligence"?

> P.P.S. What is the stance for copyrigth assesments in the files
> for git code, like the ones in gitweb/gitweb.perl and gitweb/blame.js?

There is no copyright assignment.  Everybody retains the own copyright on
their own work.

> P.P.P.S. Should I use Signed-off-by from Pasky and Fredrik if I based
> my code on theirs, and if they all signed their patches?

I think that is in line with what Certificate of Origin asks you to do.

Re: [RFC/PATCH 4/3] gitweb: Incremental blame (proof of concept)

[Jakub Narebski]

On Thu, 11 Dec 2008, Junio C Hamano wrote:
> Jakub Narebski <jnareb@gmail.com> writes:
> 
> > NOTE: This patch is RFC proof of concept patch!: it should be split
> > onto many smaller patches for easy review (and bug finding) in version
> > meant to be applied.
> 
> Hmm, the comments an RFC requests for would certainly be based on reviews
> of the patch in question, so if the patch is known to be unsuitable for
> reviewing, what would that tell us, I wonder ;-)?

Well, you can apply patch and test how it works, for example if
JavaScript code works in other browsers that have JavaScript and DOM
support (Firefox, IE, Opera, Safari, Google Chrome)... Or what
features or what interface one would like to have...

> Among the 700 lines added/deleted, 400 lines are from a single new file,
> so what may benefit from splitting would be the changes to gitweb.perl but
> it does not look so bad (I haven't really read the patch, though).

There are a few features which could be split in separate commits:
 * there are a few improvements to gitweb.css, independent of 
   incremental blame view, like td.warning -> .warning
 * adding to gitweb writing how long it took to generate page should
   be made into separate commit, probably made optional, use better
   HTML style, and have some fallback if there is no Time::HiRes

 * progress report could be made into separate commit; I needed it to
   debug code, to check if it progress nicely, but it is not strictly
   required (but it is nice to have visual indicator of progress)
 * 3-coloring of blamed lines during adding blame info was added for
   the fun of it, and should probably be in separate commit
 * adding author initials a'la "git gui blame" while nice could also
   be put in separate commit, probably adding this feature also to
   ordinary 'blame' output

[...] 
> > Differences between 'blame' and 'blame_incremental' output:
> 
> Hmm, are these by design in the sense that "when people are getting
> incremental blame output, the normal blame output format is unsuitable for
> such and such reasons and that is why there have to be these differences",
> or "the code happens to produce slightly different results because it is
> implemented differently; the differences are listed here as due
> diligence"?

Actually it is both. Some of differences are _currently_ not possible
to resolve (parent commit 'lineno' links, split group of lines blamed
by the same commit), some are coded differently (title attribute for
sha1, rowspan="1", author initials feature), and some are impossible
in incremental blame at least during generation (zebra table) or does
not make sense in 'blame' view (progress indicators).

> > P.P.S. What is the stance for copyrigth assesments in the files
> > for git code, like the ones in gitweb/gitweb.perl and gitweb/blame.js?
> 
> There is no copyright assignment.  Everybody retains the own copyright on
> their own work.

Errr... I'm sorry, I haven't made myself clear. I wanted to ask what
is the best practices about copyright statement lines like

  // Copyright (C) 2007, Fredrik Kuivinen <frekui@gmail.com>

and other results of "git grep Copyright": should it be added for
initial author, for main authors... I guess not for all authors.

> > P.P.P.S. Should I use Signed-off-by from Pasky and Fredrik if I based
> > my code on theirs, and if they all signed their patches?
> 
> I think that is in line with what Certificate of Origin asks you to do.
 
I was bit confused because Petr Baudis in his patch used Cc: and not
Signed-off-by: to Fredrik Kuivinen...
-- 
Jakub Narebski
Poland

Re: [RFC/PATCH 4/3] gitweb: Incremental blame (proof of concept)

[Jakub Narebski]

Jakub Narebski <jnareb@gmail.com> writes:

> This is tweaked up version of Petr Baudis <pasky@suse.cz> patch, which
> in turn was tweaked up version of Fredrik Kuivinen <frekui@gmail.com>'s
> proof of concept patch.  It adds 'blame_incremental' view, which
> incrementally displays line data in blame view using JavaScript (AJAX).

[...]
> Patch by Petr Baudis this one is based on:
>   http://permalink.gmane.org/gmane.comp.version-control.git/56657
> 
> Original patch by Fredrik Kuivinen:
>   http://article.gmane.org/gmane.comp.version-control.git/41361
> 
> Snippet adding 'generated in' to gitweb, by Petr Baudis:
>   http://article.gmane.org/gmane.comp.version-control.git/83306
> 
> Should I post interdiff to Petr Baudis patch, and comments about
> difference between them? [...]

Here is the list of differences between Petr Baudis patch and the one
I have just send.  No interdiff, as it is artificially large because
previous patch was based on much older version, so ranges does not
match.

Bugs I have made:
 * I forgot to make some changes for git-instaweb.sh to have support
   for incremental blame, namely dependency of 'git-instaweb' target
   in Makefile on gitweb/blame.js, and lack of the following line in
   git-instaweb.sh:
        gitweb_blamejs $GIT_DIR/gitweb/blame.js

 * Pasky's patch added support for href(...,-partial_query=>1) extra
   parameter, which ensured that gitweb link had '?' in it, and used
   it to generate 'baseUrl' parameter for startBlame.  I have
   misunderstood what baseUrl is about, and used $my_url there, while
   it is partial URL for blame links: it is projectUrl.

   Therefore links in blame table current 'blame_incremental' would
   not work. I'm sorry about that, I thought I have checked it...

Intentionally omitted features:
 * In patch this one is based on there was fixBlameLinks() JavaScript
   function (put directly in the HTML head inside <script> element),
   which was used in body.onLoad event to change 'a=blame' to
   'a=blame_incremental' in links marked with class="blamelink".

   First, this IMHO should be put as separate patch; you can test
   'blame_incremental' view by hand-crafting gitweb URL.  Second, it
   would be not enough in current gitweb, as action can be put in
   path_info. So either fixBlameLinks() should be made work in both
   cases, or it should be done in different way, for example adding
   'js=1' for all links, or doing JavaScript redirect from 'blame'
   view (although this way we won't be able to view ordinary 'blame'
   view without turning off JavaScript).

Differences in coding of the same features:
 * In Pasky's patch git_blame (then named git_blame2) and
   git_blame_incremental were just wrappers around git_blame_common;
   in this patch git_blame_data is also wrapper (to avoid duplicating
   permissions and parameter checking code).

 * Instead of calculating title string for "Commit" column cell, and
   necessary data for each row, we now calculate it once per commit
   and save (cache) in 'commits' associative array (hash).

   This is a bit of performance improvement, similar to the one in 
     "[PATCH 2/3] gitweb: Cache $parent_commit info in git_blame()"
   for 'blame' view in gitweb. It is just using Date() and string
   concatenation, and not extra fork.

 * Variables holding manipulated elements are named a bit differently,
   and calculated upfront:
      td_sha1   instead of  tr.firstChild
      a_sha1    instead of  ahsAnchor
      a_linenr  instead of  lineAnchor

 * There were a few of style changes in gitweb/blame.js; for example
   it is used the following style of function definition

      function functionName(arg1, arg2) {

   thorough the code.

Fixes for bugs in Pasky's patch, and changes related to changes in
ordinary 'blame' output: 
 * handleResponse function was called only from XMLHttpRequest
   onreadystatechange event. Not all browsers call onreadystatechange
   each time the server flushes output (Firefox does that), so we use
   a timer to check (poll) for changes.

   See http://ajaxpatterns.org/HTTP_Streaming#Refactoring_Illustration

 * The 'linenr' link was to line number commit.srcline, while it
   should be to (commit.srcline + i), as commit.srcline is _start_
   line in group, and not the line equivalent to current line in
   source.

   This might be thought a (mis)feature, and not a bug, though.

 * Currently 'blame' view uses single cell (with rowspan="N") spanning
   the whole group of lines blaming the same commit, instead of using
   empty cells for subsequent lines in group.  Therefore instead of
   setting "shaAnchor.innerHTML = '';" to make subsequent cells in
   "Commit" ('sha1') column empty (or rather to make link element <a>
   in cell empty), we use "tr.removeChild(td_sha1);"

   This change was made necessary by changes in the 'blame' view.
   This also meant that the code checking if lines are in the same
   group has to be changes; it was refactored into startOfGroup(tr)
   function.

 * The title for cells in "Commit" column used UTC (GMT) date and time
      'Kay Sievers, 2005-08-07 19:49:46'
   instead of the localtime format used currently by 'blame' view:
      'Kay Sievers, 2005-08-07 21:49:46 +0200'
   Current code uses neither, but 'commit'-like format:
      'Kay Sievers, 2005-08-07 19:49:46 +0000 (21:49:46 +0200)'

New features (in short):
 * 3-coloring of lines with blame data during incremental blaming
 * Adding author initials below shortened SHA-1 of a commit
   (if there is place for it, i.e. if group has more than 1 row)
 * progress indicator: progress info and progress bar
 * information about how long it took to run 'blame_data',
   and how long it took to run JavaScript script

-- 
Jakub Narebski
Poland
ShadeHawk on #git

Re: [RFC/PATCH 4/3] gitweb: Incremental blame (proof of concept)

[Jakub Narebski]

Jakub Narebski <jnareb@gmail.com> writes:

> New features (in short):
>  * 3-coloring of lines with blame data during incremental blaming
>  * Adding author initials below shortened SHA-1 of a commit
>    (if there is place for it, i.e. if group has more than 1 row)
>  * progress indicator: progress info and progress bar
>  * information about how long it took to run 'blame_data',
>    and how long it took to run JavaScript script

 * handling server ('blame_data') errors, i.e. status != 200.
   (I needed that to debug blame.js when I entered URL incorrectly).

-- 
Jakub Narebski
Poland
ShadeHawk on #git

[RFC/PATCH v2] gitweb: Incremental blame (proof of concept)

[Jakub Narebski]

This is tweaked up version of Petr Baudis <pasky@suse.cz> patch, which
in turn was tweaked up version of Fredrik Kuivinen <frekui@gmail.com>'s
proof of concept patch.  It adds 'blame_incremental' view, which
incrementally displays line data in blame view using JavaScript (AJAX).

The original patch by Fredrik Kuivinen has been lightly tested in a
couple of browsers (Firefox, Mozilla, Konqueror, Galeon, Opera and IE6).
The next patch by Petr Baudis has been tested in Firefox and Epiphany.
This patch has been lightly tested in Mozilla 1.17.2 and Konqueror
3.5.3.

This patch does not (contrary to the one by Petr Baudis) enable this
view in gitweb: there are no links leading to 'blame_incremental'
action.  You would have to generate URL 'by hand' (e.g. changing 'blame'
or 'blob' in gitweb URL to 'blame_incremental').  Having links in gitweb
lead to this new action (e.g. by rewriting them like in previous patch),
if JavaScript is enabled in browser, is left for later.

Like earlier patch by Per Baudis it avoids code duplication, but it goes
one step further and use git_blame_common for ordinary blame view, for
incremental blame, and (which is change from previous patch) for
incremental blame data.

How the 'blame_incremental' view works:
* gitweb generates initial info by putting file contents (from
  git-cat-file) together with line numbers in blame table
* then gitweb makes web browser JavaScript engine call startBlame()
  function from blame.js
* startBlame() opens connection to 'blame_data' view, which in turn
  calls "git blame --incremental" for a file, and streams output of
  git-blame to JavaScript (blame.js)
* blame.js updates line info in blame view, coloring it, and updating
  progress info; note that it has to use 3 colors to ensure that
  different neighbour groups have different styles
* when 'blame_data' ends, and blame.js finishes updating line info,
  it fixes colors to match (as far as possible) ordinary 'blame' view,
  and updates generating time info.

This code uses http://ajaxpatterns.org/HTTP_Streaming pattern.

It deals with streamed 'blame_data' server error by notifying about them
in the progress info area (just in case).

This patch adds GITWEB_BLAMEJS compile configuration option, and
modifies git-instaweb.sh to take blame.js into account, but it does not
update gitweb/README file (as it is only proof of concept patch).  The
code for git-instaweb.sh was taken from Pasky's patch.

While at it, this patch uniquifies td.dark and td.dark2 style: they
differ only in that td.dark2 doesn't have style for :hover.


This patch also adds showing time (in seconds) it took to generate
a page in page footer (based on example code by Pasky), even though
it is independent change, to be able to evaluate incremental blame in
gitweb better.  In proper patch series it would be independent commit;
and it probably would provide fallback if Time::HiRes is not available
(by e.g. not showing generating time info), even though this is
unlikely.

Signed-off-by: Fredrik Kuivinen <frekui@gmail.com>
Signed-off-by: Petr Baudis <pasky@suse.cz>
Signed-off-by: Jakub Narebski <jnareb@gmail.com>
---
Differences from previous version of patch:
 * Fixed copying git-instaweb related changes from Petr Baudis patch;
   git-instaweb should not work with 'blame_incremental' view
 * Fixed links in blame table in 'blame_incremental' view, and add
   support for href(..., -partial_query=>1)
 * The title attribute for "Commit" column ("sha1" cells) agrees with
   the one used for 'blame' view, meaning using localtime e.g. 
     'Kay Sievers, 2005-08-07 21:49:46 +0200'
   There was a bug in Pasky and Frederik patch here...
 * Incremental blame data generation can lead to neighbour groups
   blaming the same commit; such groups are now concatenated when
   fixing colors to zebra pattern. This mean that 'blame_incremental'
   output should match 'blame' view.
 * New feature adding author initials below shortened sha1 of commit
   was dropped; it was not present in 'blame' view, and it would make
   fixing of line grouping mentioned in previous point much more
   difficult.

 * Use more robust createRequestObject(), using try ... catch,
   taken from AJAX article at WikiPedia.
 * Better error handling: show big warning with link to 'blame'
   view if scripts are disabled, show error if XMLHttpRequest object
   cannot be started, show statusText on server returning status != 200
 * use deleteCell (DOM HTML) rather than removeChild (DOM Core)
   to delete cell(s) below cell spanning multiple rows
 * Set 'commits' to empty associative array to mark memory to be freed
 * A few improvements to findColorNo and its helper functions
 * Remember about Internet Explorer quirk when setting class attr
 * Added many comments, changed names of few variables to be more
   readable, rename few functions, split off functions, etc.
 * A bit of style cleanup: always use block with if, in continued
   (broken) lines put operator at the end of line, use literal object
   notation "{}" to initialize empty associative array rather than
   cryptic "new Object()", use === and !=== instead of == and !=,
   always use radix parameter to parseInt (i.e. parseInt(str, 10))  
   All those changes were recommended by JSLint.

 Makefile           |    6 +-
 git-instaweb.sh    |    7 +
 gitweb/blame.js    |  470 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 gitweb/gitweb.css  |   27 +++-
 gitweb/gitweb.perl |  263 ++++++++++++++++++++---------
 5 files changed, 683 insertions(+), 90 deletions(-)
 create mode 100644 gitweb/blame.js

diff --git a/Makefile b/Makefile
index 5158197..d2d3fff 100644
--- a/Makefile
+++ b/Makefile
@@ -218,6 +218,7 @@ GITWEB_HOMETEXT = indextext.html
 GITWEB_CSS = gitweb.css
 GITWEB_LOGO = git-logo.png
 GITWEB_FAVICON = git-favicon.png
+GITWEB_BLAMEJS = blame.js
 GITWEB_SITE_HEADER =
 GITWEB_SITE_FOOTER =
 
@@ -1209,13 +1210,14 @@ gitweb/gitweb.cgi: gitweb/gitweb.perl
 	    -e 's|++GITWEB_CSS++|$(GITWEB_CSS)|g' \
 	    -e 's|++GITWEB_LOGO++|$(GITWEB_LOGO)|g' \
 	    -e 's|++GITWEB_FAVICON++|$(GITWEB_FAVICON)|g' \
+	    -e 's|++GITWEB_BLAMEJS++|$(GITWEB_BLAMEJS)|g' \
 	    -e 's|++GITWEB_SITE_HEADER++|$(GITWEB_SITE_HEADER)|g' \
 	    -e 's|++GITWEB_SITE_FOOTER++|$(GITWEB_SITE_FOOTER)|g' \
 	    $< >$@+ && \
 	chmod +x $@+ && \
 	mv $@+ $@
 
-git-instaweb: git-instaweb.sh gitweb/gitweb.cgi gitweb/gitweb.css
+git-instaweb: git-instaweb.sh gitweb/gitweb.cgi gitweb/gitweb.css gitweb/blame.js
 	$(QUIET_GEN)$(RM) $@ $@+ && \
 	sed -e '1s|#!.*/sh|#!$(SHELL_PATH_SQ)|' \
 	    -e 's/@@GIT_VERSION@@/$(GIT_VERSION)/g' \
@@ -1224,6 +1226,8 @@ git-instaweb: git-instaweb.sh gitweb/gitweb.cgi gitweb/gitweb.css
 	    -e '/@@GITWEB_CGI@@/d' \
 	    -e '/@@GITWEB_CSS@@/r gitweb/gitweb.css' \
 	    -e '/@@GITWEB_CSS@@/d' \
+	    -e '/@@GITWEB_BLAMEJS@@/r gitweb/blame.js' \
+	    -e '/@@GITWEB_BLAMEJS@@/d' \
 	    -e 's|@@PERL@@|$(PERL_PATH_SQ)|g' \
 	    $@.sh > $@+ && \
 	chmod +x $@+ && \
diff --git a/git-instaweb.sh b/git-instaweb.sh
index 0843372..510789f 100755
--- a/git-instaweb.sh
+++ b/git-instaweb.sh
@@ -268,8 +268,15 @@ gitweb_css () {
 EOFGITWEB
 }
 
+gitweb_blamejs () {
+	cat > "$1" <<\EOFGITWEB
+@@GITWEB_BLAMEJS@@
+EOFGITWEB
+}
+
 gitweb_cgi "$GIT_DIR/gitweb/gitweb.cgi"
 gitweb_css "$GIT_DIR/gitweb/gitweb.css"
+gitweb_blamejs "$GIT_DIR/gitweb/blame.js"
 
 case "$httpd" in
 *lighttpd*)
diff --git a/gitweb/blame.js b/gitweb/blame.js
new file mode 100644
index 0000000..6288bd1
--- /dev/null
+++ b/gitweb/blame.js
@@ -0,0 +1,470 @@
+// Copyright (C) 2007, Fredrik Kuivinen <frekui@gmail.com>
+
+var DEBUG = 0;
+function debug(str) {
+	if (DEBUG) {
+		alert(str);
+	}
+}
+
+function createRequestObject() {
+	try {
+		return new XMLHttpRequest();
+	} catch(e) {}
+	try {
+		return new ActiveXObject("Msxml2.XMLHTTP");
+	} catch (e) {}
+	try {
+		return new ActiveXObject("Microsoft.XMLHTTP");
+	} catch (e) {}
+
+	debug("XMLHttpRequest not supported");
+	return null;
+}
+
+var http; // XMLHttpRequest object
+var projectUrl; // partial query
+
+// 'commits' is an associative map. It maps SHA1s to Commit objects.
+var commits = {};
+
+function Commit(sha1) {
+	this.sha1 = sha1;
+}
+
+// convert month or day of the month to string, padding it with
+// '0' (zero) to two characters width if necessary, e.g. 2 -> '02'
+function zeroPad(n) {
+	if (n < 10) {
+		return '0' + n;
+	} else {
+		return n.toString();
+	}
+}
+
+// pad number N with nonbreakable spaces on the right, to WIDTH characters
+// example: spacePad(12, 3) == '&nbsp;12' ('&nbsp;' is nonbreakable space)
+function spacePad(n,width) {
+	var scale = 1;
+	var str = '';
+
+	while (width > 1) {
+		scale *= 10;
+		if (n < scale) {
+			str += '&nbsp;';
+		}
+		width--;
+	}
+	return str + n;
+}
+
+var blamedLines = 0;
+var totalLines  = '???';
+var div_progress_bar;
+var div_progress_info;
+
+// how many lines does a file have, used in progress info
+function countLines() {
+	var table =
+		document.getElementById('blame_table') ||
+		document.getElementsByTagName('table')[0];
+
+	if (table) {
+		return table.getElementsByTagName('tr').length - 1; // for header
+	} else {
+		return '...';
+	}
+}
+
+// update progress info and length (width) of progress bar
+function updateProgressInfo() {
+	if (!div_progress_info) {
+		div_progress_info = document.getElementById('progress_info');
+	}
+	if (!div_progress_bar) {
+		div_progress_bar = document.getElementById('progress_bar');
+	}
+	if (!div_progress_info && !div_progress_bar) {
+		return;
+	}
+
+	var percentage = Math.floor(100.0*blamedLines/totalLines);
+
+	if (div_progress_info) {
+		div_progress_info.innerHTML  = blamedLines + ' / ' + totalLines +
+			' ('+spacePad(percentage,3)+'%)';
+	}
+
+	if (div_progress_bar) {
+		div_progress_bar.setAttribute('style', 'width: '+percentage+'%;');
+	}
+}
+
+// used to extract N from colorN, where N is a number,
+var colorRe = new RegExp('color([0-9]*)');
+
+// return N if <tr class="colorN">, otherwise return null
+// (some browsers require CSS class names to begin with letter)
+function getColorNo(tr) {
+	if (!tr) {
+		return null;
+	}
+	var className = tr.getAttribute('class');
+	if (className) {
+		match = colorRe.exec(className);
+		if (match) {
+			return parseInt(match[1],10);
+		}
+	}
+	return null;
+}
+
+// return one of given possible colors
+// example: chooseColorNoFrom(2, 3) might be 2 or 3
+function chooseColorNoFrom() {
+	// simplest version
+	return arguments[0];
+}
+
+// given two neigbour <tr> elements, find color which would be different
+// from color of both of neighbours; used to 3-color blame table
+function findColorNo(tr_prev, tr_next) {
+	var color_prev = getColorNo(tr_prev);
+	var color_next = getColorNo(tr_next);
+
+
+	// neither of neighbours has color set
+	if (!color_prev && !color_next) {
+		return chooseColorNoFrom(1,2,3);
+	}
+
+	// either both neighbours have the same color,
+	// or only one of neighbours have color set
+	var color;
+	if (color_prev == color_next) {
+		color = color_prev; // = color_next;
+	} else if (!color_prev) {
+		color = color_next;
+	} else if (!color_next) {
+		color = color_prev;
+	}
+	if (color) {
+		return chooseColorNoFrom((color % 3) + 1, ((color+1) % 3) + 1);
+	}
+
+	// neighbours have different colors
+	return (3 - ((color_prev + color_next) % 3));
+}
+
+// used to extract hours and minutes from timezone info, e.g '-0900'
+var tzRe = new RegExp('^([+-][0-9][0-9])([0-9][0-9])$');
+
+// called for each blame entry, as soon as it finishes
+function handleLine(commit) {
+	/* 
+	   This is the structure of the HTML fragment we are working
+	   with:
+	   
+	   <tr id="l123" class="">
+	     <td class="sha1" title=""><a href=""></a></td>
+	     <td class="linenr"><a class="linenr" href="">123</a></td>
+	     <td class="pre"># times (my ext3 doesn&#39;t).</td>
+	   </tr>
+	*/
+
+	var resline = commit.resline;
+
+	// format date and time string only once per commit
+	if (!commit.info) {
+		var localDate = new Date(); // date corrected by timezone
+		var match = tzRe.exec(commit.authorTimezone);
+		localDate.setTime(1000 * (commit.authorTime +
+			(parseInt(match[1],10)*3600 + parseInt(match[2],10)*60)));
+		var localDateStr = // e.g. '2005-08-07'
+			localDate.getUTCFullYear()         + '-' +
+			zeroPad(localDate.getUTCMonth()+1) + '-' +
+			zeroPad(localDate.getUTCDate());
+		var localTimeStr = // e.g. '21:49:46'
+			zeroPad(localDate.getUTCHours())   + ':' +
+			zeroPad(localDate.getUTCMinutes()) + ':' +
+			zeroPad(localDate.getUTCSeconds());
+
+		/* e.g. 'Kay Sievers, 2005-08-07 21:49:46 +0200' */
+		commit.info = commit.author + ', ' + localDateStr + ' ' +
+			localTimeStr + ' ' + commit.authorTimezone;
+	}
+
+	// color depends on group of lines, not only on blamed commit
+	var colorNo = findColorNo(
+		document.getElementById('l'+(resline-1)),
+		document.getElementById('l'+(resline+commit.numlines))
+	);
+
+
+	for (var i = 0; i < commit.numlines; i++) {
+		var tr = document.getElementById('l'+resline);
+		if (!tr) {
+			debug('tr is null! resline: ' + resline);
+			break;
+		}
+		/*
+			<tr id="l123" class="">
+			  <td class="sha1" title=""><a href=""></a></td>
+			  <td class="linenr"><a class="linenr" href="">123</a></td>
+			  <td class="pre"># times (my ext3 doesn&#39;t).</td>
+			</tr>
+		*/
+		var td_sha1  = tr.firstChild;
+		var a_sha1   = td_sha1.firstChild;
+		var a_linenr = td_sha1.nextSibling.firstChild;
+
+		/* <tr id="l123" class=""> */
+		if (colorNo !== null) {
+			tr.setAttribute('class', 'color'+colorNo);
+			// Internet Explorer needs this
+			tr.setAttribute('className', 'color'+colorNo);
+		}
+		/* <td class="sha1" title="?" rowspan="?"><a href="?">?</a></td> */
+		if (i === 0) {
+			td_sha1.title = commit.info;
+			td_sha1.setAttribute('rowspan', commit.numlines);
+
+			a_sha1.href = projectUrl + ';a=commit;h=' + commit.sha1;
+			a_sha1.innerHTML = commit.sha1.substr(0, 8);
+
+		} else {
+			//tr.removeChild(td_sha1); // DOM2 Core way
+			tr.deleteCell(0); // DOM2 HTML way
+		}
+
+		/* <td class="linenr"><a class="linenr" href="?">123</a></td> */
+		a_linenr.href = projectUrl + ';a=blame;hb=' + commit.sha1 +
+			';f=' + commit.filename + '#l' + (commit.srcline + i);
+
+		resline++;
+		blamedLines++;
+
+		//updateProgressInfo();
+	}
+}
+
+function startOfGroup(tr) {
+	return tr.firstChild.getAttribute('class') == 'sha1';
+}
+
+function fixColorsAndGroups() {
+	var colorClasses = ['light2', 'dark2'];
+	var linenum = 1;
+	var tr, prev_group;
+	var colorClass = 0;
+
+	while ((tr = document.getElementById('l'+linenum))) {
+		if (startOfGroup(tr, linenum, document)) {
+			if (prev_group &&
+			    prev_group.firstChild.firstChild.href ==
+			            tr.firstChild.firstChild.href) {
+				// we have to concatenate groups
+				var rows = prev_group.firstChild.getAttribute('rowspan');
+				// assume that we have rowspan even for rowspan="1"
+				prev_group.firstChild.setAttribute('rowspan',
+					(rows + tr.firstChild.getAttribute('rowspan')));
+				tr.removeChild(tr.firstChild);
+			} else {
+				colorClass = (colorClass + 1) % 2;
+				prev_group = tr;
+			}
+		}
+		tr.setAttribute('class', colorClasses[colorClass]);
+		// Internet Explorer needs this
+		tr.setAttribute('className', colorClasses[colorClass]);
+		linenum++;
+	}
+}
+
+var t_interval_server = '';
+var t0 = new Date();
+
+// write how much it took to generate data, and to run script
+function writeTimeInterval() {
+	var info = document.getElementById('generate_time');
+	if (!info) {
+		return;
+	}
+	var t1 = new Date();
+
+	info.innerHTML += ' + ' +
+		t_interval_server+'s server (blame_data) / ' +
+		(t1.getTime() - t0.getTime())/1000 + 's client (JavaScript)';
+}
+
+// ----------------------------------------------------------------------
+
+var prevDataLength = -1;
+var nextLine = 0;
+var inProgress = false;
+
+var sha1Re = new RegExp('([0-9a-f]{40}) ([0-9]+) ([0-9]+) ([0-9]+)');
+var infoRe = new RegExp('([a-z-]+) ?(.*)');
+var endRe = new RegExp('END ?(.*)');
+var curCommit = new Commit();
+
+var pollTimer = null;
+
+function handleResponse() {
+	debug('handleResp ready: ' + http.readyState +
+	      ' respText null?: ' + (http.responseText === null) +
+	      ' progress: ' + inProgress);
+
+	if (http.readyState != 4 && http.readyState != 3) {
+		return;
+	}
+
+	// the server returned error
+	if (http.readyState == 3 && http.status != 200) {
+		return;
+	}
+	if (http.readyState == 4 && http.status != 200) {
+		if (!div_progress_info) {
+			div_progress_info = document.getElementById('progress_info');
+		}
+
+		if (div_progress_info) {
+			div_progress_info.setAttribute('class', 'error');
+			// Internet Explorer needs this
+			div_progress_info.setAttribute('className', 'error');
+			div_progress_info.innerHTML = 'Server error: ' +
+				http.status+' - '+(http.statusText || 'Error contacting server');
+		}
+
+		clearInterval(pollTimer);
+		inProgress = false;
+	}
+
+	// In konqueror http.responseText is sometimes null here...
+	if (http.responseText === null) {
+		return;
+	}
+
+	// in case we were called before finished processing
+	if (inProgress) {
+		return;
+	} else {
+		inProgress = true;
+	}
+
+	while (prevDataLength != http.responseText.length) {
+		if (http.readyState == 4 &&
+		    prevDataLength == http.responseText.length) {
+			break;
+		}
+
+		prevDataLength = http.responseText.length;
+		var response = http.responseText.substring(nextLine);
+		var lines = response.split('\n');
+		nextLine = nextLine + response.lastIndexOf('\n') + 1;
+		if (response[response.length-1] != '\n') {
+			lines.pop();
+		}
+
+		for (var i = 0; i < lines.length; i++) {
+			var match = sha1Re.exec(lines[i]);
+			if (match) {
+				var sha1 = match[1];
+				var srcline = parseInt(match[2],10);
+				var resline = parseInt(match[3],10);
+				var numlines = parseInt(match[4],10);
+				var c = commits[sha1];
+				if (!c) {
+					c = new Commit(sha1);
+					commits[sha1] = c;
+				}
+
+				c.srcline = srcline;
+				c.resline = resline;
+				c.numlines = numlines;
+				curCommit = c;
+			} else if ((match = infoRe.exec(lines[i]))) {
+				var info = match[1];
+				var data = match[2];
+				if (info == 'filename') {
+					curCommit.filename = data;
+					handleLine(curCommit);
+					updateProgressInfo();
+				} else if (info == 'author') {
+					curCommit.author = data;
+				} else if (info == 'author-time') {
+					curCommit.authorTime = parseInt(data,10);
+				} else if (info == 'author-tz') {
+					curCommit.authorTimezone = data;
+				}
+			} else if ((match = endRe.exec(lines[i]))) {
+				t_interval_server = match[1];
+				debug('END: '+lines[i]);
+			} else if (lines[i] !== '') {
+				debug('malformed line: ' + lines[i]);
+			}
+		}
+	}
+
+	// did we finish work?
+	if (http.readyState == 4 &&
+	    prevDataLength == http.responseText.length) {
+		clearInterval(pollTimer);
+
+		fixColorsAndGroups();
+		writeTimeInterval();
+		commits = {}; // free memory
+	}
+
+	inProgress = false;
+}
+
+// ============================================================
+// ------------------------------------------------------------
+
+/*
+	Function: startBlame
+
+	Incrementally update line data in blame_incremental view in gitweb.
+
+	Parameters:
+
+		blamedataUrl - URL to server script generating blame data.
+		bUrl -partial URL to project, used to generate links in blame.
+
+	Comments:
+
+	Called from 'blame_incremental' view after loading table with
+	file contents, a base for blame view.
+*/
+function startBlame(blamedataUrl, bUrl) {
+	debug('startBlame('+blamedataUrl+', '+bUrl+')');
+
+	http = createRequestObject();
+	if (!http) {
+		div_progress_info = document.getElementById('progress_info');
+
+		if (div_progress_info) {
+			div_progress_info.setAttribute('class', 'error');
+			// Internet Explorer needs this
+			div_progress_info.setAttribute('className', 'error');
+			div_progress_info.innerHTML = 'XMLHttpRequest not supported';
+		}
+
+		return;
+	}
+
+	t0 = new Date();
+	projectUrl = bUrl;
+	totalLines = countLines();
+	updateProgressInfo();
+
+	http.open('get', blamedataUrl);
+	http.onreadystatechange = handleResponse;
+	http.send(null);
+
+	// not all browsers call onreadystatechange event on each server flush
+	pollTimer = setInterval(handleResponse, 2000);
+}
+
+// end of blame.js
diff --git a/gitweb/gitweb.css b/gitweb/gitweb.css
index a01eac8..e359618 100644
--- a/gitweb/gitweb.css
+++ b/gitweb/gitweb.css
@@ -223,11 +223,7 @@ tr.light:hover {
 	background-color: #edece6;
 }
 
-tr.dark {
-	background-color: #f6f6f0;
-}
-
-tr.dark2 {
+tr.dark, tr.dark2 {
 	background-color: #f6f6f0;
 }
 
@@ -235,6 +231,14 @@ tr.dark:hover {
 	background-color: #edece6;
 }
 
+tr.color1:hover { background-color: #e6ede6; }
+tr.color2:hover { background-color: #e6e6ed; }
+tr.color3:hover { background-color: #ede6e6; }
+
+tr.color1 { background-color: #f6fff6; }
+tr.color2 { background-color: #f6f6ff; }
+tr.color3 { background-color: #fff6f6; }
+
 td {
 	padding: 2px 5px;
 	font-size: 100%;
@@ -255,7 +259,7 @@ td.sha1 {
 	font-family: monospace;
 }
 
-td.error {
+.error {
 	color: red;
 	background-color: yellow;
 }
@@ -326,6 +330,17 @@ td.mode {
 	font-family: monospace;
 }
 
+/* progress of blame_interactive */
+div#progress_bar {
+	height: 2px;
+	margin-bottom: -2px;
+	background-color: #d8d9d0;
+}
+div#progress_info {
+	float: right;
+	text-align: right;
+}
+
 /* styling of diffs (patchsets): commitdiff and blobdiff views */
 div.diff.header,
 div.diff.extended_header {
diff --git a/gitweb/gitweb.perl b/gitweb/gitweb.perl
index 4987fdc..93a4e82 100755
--- a/gitweb/gitweb.perl
+++ b/gitweb/gitweb.perl
@@ -18,6 +18,9 @@ use File::Find qw();
 use File::Basename qw(basename);
 binmode STDOUT, ':utf8';
 
+use Time::HiRes qw(gettimeofday tv_interval);
+our $t0 = [gettimeofday];
+
 BEGIN {
 	CGI->compile() if $ENV{'MOD_PERL'};
 }
@@ -74,6 +77,8 @@ our $stylesheet = undef;
 our $logo = "++GITWEB_LOGO++";
 # URI of GIT favicon, assumed to be image/png type
 our $favicon = "++GITWEB_FAVICON++";
+# URI of blame.js
+our $blamejs = "++GITWEB_BLAMEJS++";
 
 # URI and label (title) of GIT logo link
 #our $logo_url = "http://www.kernel.org/pub/software/scm/git/docs/";
@@ -493,6 +498,8 @@ our %cgi_param_mapping = @cgi_param_mapping;
 # we will also need to know the possible actions, for validation
 our %actions = (
 	"blame" => \&git_blame,
+	"blame_incremental" => \&git_blame_incremental,
+	"blame_data" => \&git_blame_data,
 	"blobdiff" => \&git_blobdiff,
 	"blobdiff_plain" => \&git_blobdiff_plain,
 	"blob" => \&git_blob,
@@ -919,7 +926,8 @@ sub href (%) {
 			}
 		}
 	}
-	$href .= "?" . join(';', @result) if scalar @result;
+	$href .= "?" . join(';', @result)
+		if ($params{-partial_query} or scalar @result);
 
 	return $href;
 }
@@ -1272,7 +1280,7 @@ use constant {
 };
 
 # submodule/subproject, a commit object reference
-sub S_ISGITLINK($) {
+sub S_ISGITLINK {
 	my $mode = shift;
 
 	return (($mode & S_IFMT) == S_IFGITLINK)
@@ -1558,7 +1566,7 @@ sub format_diff_from_to_header {
 	# no extra formatting for "^--- /dev/null"
 	if (! $diffinfo->{'nparents'}) {
 		# ordinary (single parent) diff
-		if ($line =~ m!^--- "?a/!) {
+		if ($line =~ m!^--- "?a/!) {#"
 			if ($from->{'href'}) {
 				$line = '--- a/' .
 				        $cgi->a({-href=>$from->{'href'}, -class=>"path"},
@@ -1816,7 +1824,7 @@ sub git_cmd {
 # Try to avoid using this function wherever possible.
 sub quote_command {
 	return join(' ',
-		    map( { my $a = $_; $a =~ s/(['!])/'\\$1'/g; "'$a'" } @_ ));
+		    map( { my $a = $_; $a =~ s/(['!])/'\\$1'/g; "'$a'" } @_ ));#'
 }
 
 # get HEAD ref of given project as hash
@@ -2874,13 +2882,13 @@ sub git_header_html {
 	# 'application/xhtml+xml', otherwise send it as plain old 'text/html'.
 	# we have to do this because MSIE sometimes globs '*/*', pretending to
 	# support xhtml+xml but choking when it gets what it asked for.
-	if (defined $cgi->http('HTTP_ACCEPT') &&
-	    $cgi->http('HTTP_ACCEPT') =~ m/(,|;|\s|^)application\/xhtml\+xml(,|;|\s|$)/ &&
-	    $cgi->Accept('application/xhtml+xml') != 0) {
-		$content_type = 'application/xhtml+xml';
-	} else {
+	#if (defined $cgi->http('HTTP_ACCEPT') &&
+	#    $cgi->http('HTTP_ACCEPT') =~ m/(,|;|\s|^)application\/xhtml\+xml(,|;|\s|$)/ &&
+	#    $cgi->Accept('application/xhtml+xml') != 0) {
+	#	$content_type = 'application/xhtml+xml';
+	#} else {
 		$content_type = 'text/html';
-	}
+	#}
 	print $cgi->header(-type=>$content_type, -charset => 'utf-8',
 	                   -status=> $status, -expires => $expires);
 	my $mod_perl_version = $ENV{'MOD_PERL'} ? " $ENV{'MOD_PERL'}" : '';
@@ -3042,6 +3050,14 @@ sub git_footer_html {
 	}
 	print "</div>\n"; # class="page_footer"
 
+	print "<div class=\"page_footer\">\n";
+	print 'This page took '.
+	      '<span id="generate_time" class="time_span">'.
+	      tv_interval($t0, [gettimeofday]).'s'.
+	      '</span>'.
+	      " to generate.\n";
+	print "</div>\n"; # class="page_footer"
+
 	if (-f $site_footer) {
 		insert_file($site_footer);
 	}
@@ -3803,7 +3819,7 @@ sub git_patchset_body {
 	while ($patch_line) {
 
 		# parse "git diff" header line
-		if ($patch_line =~ m/^diff --git (\"(?:[^\\\"]*(?:\\.[^\\\"]*)*)\"|[^ "]*) (.*)$/) {
+		if ($patch_line =~ m/^diff --git (\"(?:[^\\\"]*(?:\\.[^\\\"]*)*)\"|[^ "]*) (.*)$/) {#"
 			# $1 is from_name, which we do not use
 			$to_name = unquote($2);
 			$to_name =~ s!^b/!!;
@@ -4574,7 +4590,9 @@ sub git_tag {
 	git_footer_html();
 }
 
-sub git_blame {
+sub git_blame_common {
+	my $format = shift || 'porcelain';
+
 	# permissions
 	gitweb_check_feature('blame')
 		or die_error(403, "Blame view not allowed");
@@ -4596,10 +4614,36 @@ sub git_blame {
 		}
 	}
 
-	# run git-blame --porcelain
-	open my $fd, "-|", git_cmd(), "blame", '-p',
-		$hash_base, '--', $file_name
-		or die_error(500, "Open git-blame failed");
+	my $fd;
+	if ($format eq 'incremental') {
+		# get file contents (as base)
+		open $fd, "-|", git_cmd(), 'cat-file', 'blob', $hash
+			or die_error(500, "Open git-cat-file failed");
+	} elsif ($format eq 'data') {
+		# run git-blame --incremental
+		open $fd, "-|", git_cmd(), "blame", "--incremental",
+			$hash_base, "--", $file_name
+			or die_error(500, "Open git-blame --incremental failed");
+	} else {
+		# run git-blame --porcelain
+		open $fd, "-|", git_cmd(), "blame", '-p',
+			$hash_base, '--', $file_name
+			or die_error(500, "Open git-blame --porcelain failed");
+	}
+
+	# incremental blame data returns early
+	if ($format eq 'data') {
+		print $cgi->header(
+			-type=>"text/plain", -charset => "utf-8",
+			-status=> "200 OK");
+		local $| = 1; # output autoflush
+		print while <$fd>;
+		close $fd
+			or print "ERROR $!\n";
+		print "END ".tv_interval($t0, [gettimeofday])."\n";
+
+		return;
+	}
 
 	# page header
 	git_header_html();
@@ -4610,93 +4654,146 @@ sub git_blame {
 		$cgi->a({-href => href(action=>"history", -replay=>1)},
 		        "history") .
 		" | " .
-		$cgi->a({-href => href(action=>"blame", file_name=>$file_name)},
+		$cgi->a({-href => href(action=>$action, file_name=>$file_name)},
 		        "HEAD");
 	git_print_page_nav('','', $hash_base,$co{'tree'},$hash_base, $formats_nav);
 	git_print_header_div('commit', esc_html($co{'title'}), $hash_base);
 	git_print_page_path($file_name, $ftype, $hash_base);
 
 	# page body
+	if ($format eq 'incremental') {
+		print "<noscript>\n<div class=\"error\"><center><b>\n".
+		      "This page requires JavaScript to run\nUse ".
+		      $cgi->a({-href => href(action=>'blame',-replay=>1)}, 'this page').
+		      " instead.\n".
+		      "</b></center></div>\n</noscript>\n";
+
+		print qq!<div id="progress_bar" style="width: 100%; background-color: yellow"></div>\n!;
+	}
+
+	print qq!<div class="page_body">\n!;
+	print qq!<div id="progress_info">... / ...</div>\n!
+		if ($format eq 'incremental');
+	print qq!<table id="blame_table" class="blame" width="100%">\n!.
+	      #qq!<col width="5.5em" /><col width="2.5em" /><col width="*" />\n!.
+	      qq!<thead>\n!.
+	      qq!<tr><th>Commit</th><th>Line</th><th>Data</th></tr>\n!.
+	      qq!</thead>\n!.
+	      qq!<tbody>\n!;
+
 	my @rev_color = qw(light2 dark2);
 	my $num_colors = scalar(@rev_color);
 	my $current_color = 0;
-	my %metainfo = ();
 
-	print <<HTML;
-<div class="page_body">
-<table class="blame">
-<tr><th>Commit</th><th>Line</th><th>Data</th></tr>
-HTML
- LINE:
-	while (my $line = <$fd>) {
-		chomp $line;
-		# the header: <SHA-1> <src lineno> <dst lineno> [<lines in group>]
-		# no <lines in group> for subsequent lines in group of lines
-		my ($full_rev, $orig_lineno, $lineno, $group_size) =
-		   ($line =~ /^([0-9a-f]{40}) (\d+) (\d+)(?: (\d+))?$/);
-		if (!exists $metainfo{$full_rev}) {
-			$metainfo{$full_rev} = {};
-		}
-		my $meta = $metainfo{$full_rev};
-		my $data; # last line is used later
-		while ($data = <$fd>) {
-			chomp $data;
-			last if ($data =~ s/^\t//); # contents of line
-			if ($data =~ /^(\S+) (.*)$/) {
-				$meta->{$1} = $2;
-			}
-		}
-		my $short_rev = substr($full_rev, 0, 8);
-		my $author = $meta->{'author'};
-		my %date =
-			parse_date($meta->{'author-time'}, $meta->{'author-tz'});
-		my $date = $date{'iso-tz'};
-		if ($group_size) {
-			$current_color = ($current_color + 1) % $num_colors;
-		}
-		print "<tr id=\"l$lineno\" class=\"$rev_color[$current_color]\">\n";
-		if ($group_size) {
-			print "<td class=\"sha1\"";
-			print " title=\"". esc_html($author) . ", $date\"";
-			print " rowspan=\"$group_size\"" if ($group_size > 1);
-			print ">";
-			print $cgi->a({-href => href(action=>"commit",
-			                             hash=>$full_rev,
-			                             file_name=>$file_name)},
-			              esc_html($short_rev));
-			print "</td>\n";
+	if ($format eq 'incremental') {
+		my $color_class = $rev_color[$current_color];
+
+		#contents of a file
+		my $linenr = 0;
+	LINE:
+		while (my $line = <$fd>) {
+			chomp $line;
+			$linenr++;
+
+			print qq!<tr id="l$linenr" class="$color_class">!.
+			      qq!<td class="sha1"><a href=""></a></td>!.
+			      qq!<td class="linenr">!.
+			      qq!<a class="linenr" href="">$linenr</a></td>!;
+			print qq!<td class="pre">! . esc_html($line) . "</td>\n";
+			print qq!</tr>\n!;
 		}
-		my $parent_commit;
-		if (!exists $meta->{'parent'}) {
-			open (my $dd, "-|", git_cmd(), "rev-parse", "$full_rev^")
-				or die_error(500, "Open git-rev-parse failed");
-			$parent_commit = <$dd>;
-			close $dd;
-			chomp($parent_commit);
-			$meta->{'parent'} = $parent_commit;
-		} else {
-			$parent_commit = $meta->{'parent'};
-		}
-		my $blamed = href(action => 'blame',
-		                  file_name => $meta->{'filename'},
-		                  hash_base => $parent_commit);
-		print "<td class=\"linenr\">";
-		print $cgi->a({ -href => "$blamed#l$orig_lineno",
-		                -class => "linenr" },
-		              esc_html($lineno));
-		print "</td>";
-		print "<td class=\"pre\">" . esc_html($data) . "</td>\n";
-		print "</tr>\n";
-	}
-	print "</table>\n";
-	print "</div>";
+
+	} else { # porcelain, i.e. ordinary blame
+		my %metainfo = (); # saves information about commits
+
+		# blame data
+	LINE:
+		while (my $line = <$fd>) {
+			chomp $line;
+			# the header: <SHA-1> <src lineno> <dst lineno> [<lines in group>]
+			# no <lines in group> for subsequent lines in group of lines
+			my ($full_rev, $orig_lineno, $lineno, $group_size) =
+				($line =~ /^([0-9a-f]{40}) (\d+) (\d+)(?: (\d+))?$/);
+			$metainfo{$full_rev} ||= {};
+			my $meta = $metainfo{$full_rev};
+			my $data; # last line is used later
+			while ($data = <$fd>) {
+				chomp $data;
+				last if ($data =~ s/^\t//); # contents of line
+				if ($data =~ /^(\S+) (.*)$/) {
+					$meta->{$1} = $2;
+				}
+			}
+			my $short_rev = substr($full_rev, 0, 8);
+			my $author = $meta->{'author'};
+			my %date =
+				parse_date($meta->{'author-time'}, $meta->{'author-tz'});
+			my $date = $date{'iso-tz'};
+			if ($group_size) {
+				$current_color = ($current_color + 1) % $num_colors;
+			}
+			print qq!<tr id="l$lineno" class="$rev_color[$current_color]">\n!;
+			if ($group_size) {
+				print qq!<td class="sha1"!.
+				      qq! title="!. esc_html($author) . qq!, $date"!;
+				print qq! rowspan="$group_size"! if ($group_size > 1);
+				print qq!>!;
+				print $cgi->a({-href => href(action=>"commit",
+				                             hash=>$full_rev,
+				                             file_name=>$file_name)},
+				              esc_html($short_rev));
+				print qq!</td>\n!;
+			}
+			if (!exists $meta->{'parent'}) {
+				open my $dd, "-|", git_cmd(), "rev-parse", "$full_rev^"
+					or die_error(500, "Open git-rev-parse failed");
+				$meta->{'parent'} = <$dd>;
+				close $dd;
+				chomp $meta->{'parent'};
+			}
+			my $blamed = href(action => 'blame',
+			                  file_name => $meta->{'filename'},
+			                  hash_base => $meta->{'parent'});
+			print qq!<td class="linenr">!.
+			       $cgi->a({ -href => "$blamed#l$orig_lineno",
+			                -class => "linenr" },
+			               esc_html($lineno)).
+			      qq!</td>!;
+			print qq!<td class="pre">! . esc_html($data) . "</td>\n";
+			print qq!</tr>\n!;
+		}
+	}
+
+	# footer
+	print "</tbody>\n".
+	      "</table>\n"; # class="blame"
+	print "</div>\n";   # class="blame_body"
 	close $fd
 		or print "Reading blob failed\n";
 
-	# page footer
+	if ($format eq 'incremental') {
+		print qq!<script type="text/javascript" src="$blamejs"></script>\n!.
+		      qq!<script type="text/javascript">\n!.
+		      qq!startBlame("!. href(action=>"blame_data", -replay=>1) .qq!",\n!.
+		      qq!           "!. href(-partial_query=>1) .qq!");\n!.
+		      qq!</script>\n!;
+	}
+
 	git_footer_html();
 }
 
+sub git_blame {
+	git_blame_common();
+}
+
+sub git_blame_incremental {
+	git_blame_common('incremental');
+}
+
+sub git_blame_data {
+	git_blame_common('data');
+}
+
 sub git_tags {
 	my $head = git_get_head_hash($project);
 	git_header_html();
-- 
1.6.0.4

[RFC] gitweb: Incremental blame - suggestions for improvements

[Jakub Narebski]

A few suggestions for further improvement of blame_incremental:
 * Better support for data mining in 'blame_incremental' view,
   (for "lineno" links to (approximately) lead to previous version of
   line) would probably require for gitweb to accept "<rev>^" for 'hb'
   parameter (and perhaps resolve/parse it before saving to
   $hash_base). This would also help performance of 'blame' view.

 * Move some of processing to server, to 'blame_data' action, and for
   example send whole saved and processed info for a group of lines as
   JSON or as variation of "git blame --incremental" output.

 * Better error checking: not only check if scripting is turned on,
   but also if required methods like document.getElementById are
   available. Probably would require falback to *ugh* document.write.

 * Perhaps fallback on (slower) DOM methods if innerHTML is not
   available or doesn't work, which is the case for some versions of
   some browsers in strict XHTML (application/xml+html + XHTML DTD)
   mode.

 * Fallback on DOM Core methods of deleting cell if DOM HTML
   deleteCell method is not available; check that DOM Core way does
   not lead to memory leaks (by deleting element, but not its
   children).

 * Use 'one second spotlight' or other similar user interface patter
   to signal in more visible way than reaching 100% in progress info,
   and changing colors from 3-coloring to 2-color zebra in blame table
   that all blame data was received and entered.

 * Check in handleResponse if browser calls it on [each] server flush,
   by checking if it is called more than once with http.readyState == 3
   and with different http.responseText, and disable poll timer then.

 * Mark boundary commits (this applies both to 'blame' and
   'blame_incremental' views), using UNDOCUMENTED "boundary" header.

 * A toy. Make progress bar indicator more smooth by interpolating
   changes between updates, so it moves smoothly. This would make it
   provide impression for user, not an accurate measure of blamed
   percentage.

 * A toy. Make sure that 3-coloring during updating blame table use
   all three colors with similar frequency, for example by using the
   following implementation of chooseColorNoFrom function:

    // return one of given possible colors
    // example: chooseColorNoFrom(2, 3) might be 2 or 3
    var colorsFreq = [0, 0, 0];
    // assumes that  1 <= arguments[i] <= colorsFreq.length
    function chooseColorNoFrom() {
    	// choose the color which is least used
    	var colorNo = arguments[0];
    	for (var i = 1; i < arguments.length; i++) {
    		if (colorsFreq[arguments[i]-1] < colorsFreq[colorNo-1]) {
    			colorNo = arguments[i];
    		}
    	}
    	colorsFreq[colorNo-1]++;
    	return colorNo;
    }


Do you have your own suggestions?  Comments?
Would incremental blame help git-instaweb use?
-- 
Jakub Narebski
Poland
ShadeHawk on #git