[PATCH 0/2] Two janitorial patches for builtin/blame.c

[PATCH 0/2] Two janitorial patches for builtin/blame.c

[David Kastrup]

This is more a warmup than anything else: I'm actually doing a quite
more involved rewrite of git-blame right now.  But it's been a long
time since I sent patches for Git, so I'm starting out with something
reasonably uncontroversial.  Patch 1 is a no-brainer: maintaining
reverse links is not worth the trouble if you are not going to use
them.  Now one can be "conservative" and say "but git-blame is awfully
inefficient and maybe we'll need them in a more efficient version".
I can answer this with "no": the kind of stuff that would make things
more efficient does not require backlinks.

Patch 2 is a bit more tricky: basically its contention is that
I understand some implications of the code better than its author
appeared to do.  Which is somewhat optimistic.  Since my followup work
depends on my understanding this correctly, it's better to make sure
of that by handing in a nicely isolated patch for review.  It's
conceivable that my understanding of the commit->util cache is not
fully satisfactory.  I don't use it in my followup work anyway, but it
still would be nice to get this code path cleaned out in advance.

I don't expect measurable performance improvements from these two
patches: their main purpose is to get some cruft out of the way so
that the heavy-duty patches actually dealing with the performance
sinks will be a bit more focused.

And of course, getting the ball rolling again.

David Kastrup (2):
  builtin/blame.c: struct blame_entry does not need a prev link
  Eliminate same_suspect function in builtin/blame.c

 builtin/blame.c | 38 ++++++++++----------------------------
 1 file changed, 10 insertions(+), 28 deletions(-)

-- 
1.8.3.2

[PATCH 1/2] builtin/blame.c: struct blame_entry does not need a prev link

[David Kastrup]

---
 builtin/blame.c | 13 ++-----------
 1 file changed, 2 insertions(+), 11 deletions(-)

diff --git a/builtin/blame.c b/builtin/blame.c
index e44a6bb..2195595 100644
--- a/builtin/blame.c
+++ b/builtin/blame.c
@@ -197,7 +197,6 @@ static void drop_origin_blob(struct origin *o)
  * scoreboard structure, sorted by the target line number.
  */
 struct blame_entry {
-	struct blame_entry *prev;
 	struct blame_entry *next;
 
 	/* the first line of this group in the final image;
@@ -282,8 +281,6 @@ static void coalesce(struct scoreboard *sb)
 		    ent->s_lno + ent->num_lines == next->s_lno) {
 			ent->num_lines += next->num_lines;
 			ent->next = next->next;
-			if (ent->next)
-				ent->next->prev = ent;
 			origin_decref(next->suspect);
 			free(next);
 			ent->score = 0;
@@ -534,7 +531,7 @@ static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)
 		prev = ent;
 
 	/* prev, if not NULL, is the last one that is below e */
-	e->prev = prev;
+
 	if (prev) {
 		e->next = prev->next;
 		prev->next = e;
@@ -543,8 +540,6 @@ static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)
 		e->next = sb->ent;
 		sb->ent = e;
 	}
-	if (e->next)
-		e->next->prev = e;
 }
 
 /*
@@ -555,14 +550,12 @@ static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)
  */
 static void dup_entry(struct blame_entry *dst, struct blame_entry *src)
 {
-	struct blame_entry *p, *n;
+	struct blame_entry *n;
 
-	p = dst->prev;
 	n = dst->next;
 	origin_incref(src->suspect);
 	origin_decref(dst->suspect);
 	memcpy(dst, src, sizeof(*src));
-	dst->prev = p;
 	dst->next = n;
 	dst->score = 0;
 }
@@ -2502,8 +2495,6 @@ parse_done:
 		ent->suspect = o;
 		ent->s_lno = bottom;
 		ent->next = next;
-		if (next)
-			next->prev = ent;
 		origin_incref(o);
 	}
 	origin_decref(o);
-- 
1.8.3.2

[PATCH 2/2] Eliminate same_suspect function in builtin/blame.c

[David Kastrup]

Since the origin pointers are "interned" and reference-counted, comparing
the pointers rather than the content is enough.  The only uninterned
origins are cached values kept in commit->util, but same_suspect is not
called on them.
---
 builtin/blame.c | 25 ++++++++-----------------
 1 file changed, 8 insertions(+), 17 deletions(-)

diff --git a/builtin/blame.c b/builtin/blame.c
index 2195595..ead6148 100644
--- a/builtin/blame.c
+++ b/builtin/blame.c
@@ -255,15 +255,6 @@ struct scoreboard {
 	int *lineno;
 };
 
-static inline int same_suspect(struct origin *a, struct origin *b)
-{
-	if (a == b)
-		return 1;
-	if (a->commit != b->commit)
-		return 0;
-	return !strcmp(a->path, b->path);
-}
-
 static void sanity_check_refcnt(struct scoreboard *);
 
 /*
@@ -276,7 +267,7 @@ static void coalesce(struct scoreboard *sb)
 	struct blame_entry *ent, *next;
 
 	for (ent = sb->ent; ent && (next = ent->next); ent = next) {
-		if (same_suspect(ent->suspect, next->suspect) &&
+		if (ent->suspect == next->suspect &&
 		    ent->guilty == next->guilty &&
 		    ent->s_lno + ent->num_lines == next->s_lno) {
 			ent->num_lines += next->num_lines;
@@ -735,7 +726,7 @@ static int find_last_in_target(struct scoreboard *sb, struct origin *target)
 	int last_in_target = -1;
 
 	for (e = sb->ent; e; e = e->next) {
-		if (e->guilty || !same_suspect(e->suspect, target))
+		if (e->guilty || e->suspect != target)
 			continue;
 		if (last_in_target < e->s_lno + e->num_lines)
 			last_in_target = e->s_lno + e->num_lines;
@@ -755,7 +746,7 @@ static void blame_chunk(struct scoreboard *sb,
 	struct blame_entry *e;
 
 	for (e = sb->ent; e; e = e->next) {
-		if (e->guilty || !same_suspect(e->suspect, target))
+		if (e->guilty || e->suspect != target)
 			continue;
 		if (same <= e->s_lno)
 			continue;
@@ -985,7 +976,7 @@ static int find_move_in_parent(struct scoreboard *sb,
 	while (made_progress) {
 		made_progress = 0;
 		for (e = sb->ent; e; e = e->next) {
-			if (e->guilty || !same_suspect(e->suspect, target) ||
+			if (e->guilty || e->suspect != target ||
 			    ent_score(sb, e) < blame_move_score)
 				continue;
 			find_copy_in_blob(sb, e, parent, split, &file_p);
@@ -1020,14 +1011,14 @@ static struct blame_list *setup_blame_list(struct scoreboard *sb,
 
 	for (e = sb->ent, num_ents = 0; e; e = e->next)
 		if (!e->scanned && !e->guilty &&
-		    same_suspect(e->suspect, target) &&
+		    e->suspect == target &&
 		    min_score < ent_score(sb, e))
 			num_ents++;
 	if (num_ents) {
 		blame_list = xcalloc(num_ents, sizeof(struct blame_list));
 		for (e = sb->ent, i = 0; e; e = e->next)
 			if (!e->scanned && !e->guilty &&
-			    same_suspect(e->suspect, target) &&
+			    e->suspect == target &&
 			    min_score < ent_score(sb, e))
 				blame_list[i++].ent = e;
 	}
@@ -1171,7 +1162,7 @@ static void pass_whole_blame(struct scoreboard *sb,
 		origin->file.ptr = NULL;
 	}
 	for (e = sb->ent; e; e = e->next) {
-		if (!same_suspect(e->suspect, origin))
+		if (e->suspect != origin)
 			continue;
 		origin_incref(porigin);
 		origin_decref(e->suspect);
@@ -1560,7 +1551,7 @@ static void assign_blame(struct scoreboard *sb, int opt)
 
 		/* Take responsibility for the remaining entries */
 		for (ent = sb->ent; ent; ent = ent->next)
-			if (same_suspect(ent->suspect, suspect))
+			if (ent->suspect == suspect)
 				found_guilty_entry(ent);
 		origin_decref(suspect);
 
-- 
1.8.3.2

Re: [PATCH 0/2] Two janitorial patches for builtin/blame.c

[David Kastrup]

David Kastrup <dak@gnu.org> writes:

> This is more a warmup than anything else: I'm actually doing a quite
> more involved rewrite of git-blame right now.  But it's been a long
> time since I sent patches for Git, so I'm starting out with something
> reasonably uncontroversial.

Ping?

Now I might have sent at an unopportune time: blame.c is mostly
attributed to Junio who seems to have been a few days absent now.

I also have seen quite a few mails and patch submissions on the list go
basically unanswered in the last few days.

So it might just be that this is business as usual.  However, since
I have not been on this list for quite a while, I would want to avoid
causing large delays by some oversight.

I have not so far signed off on the patches: it would appear that this
is required.  The submission guidelines in
Documentation/SubmittingPatches state for signing off:

        (a) The contribution was created in whole or in part by me and I
            have the right to submit it under the open source license
            indicated in the file; or

[...]

        (d) I understand and agree that this project and the contribution
            are public and that a record of the contribution (including all
            personal information I submit with it, including my sign-off) is
            maintained indefinitely and may be redistributed consistent with
            this project or the open source license(s) involved.

Now the file involved (builtin/blame.c) itself does not state _any_
license.  Instead it states

    /*
     * Blame
     *
     * Copyright (c) 2006, Junio C Hamano
     */

I do not intend my contribution to constitute a copyright assignment
(and it hardly could be one).  The top file COPYING in Git states

     Note that the only valid version of the GPL as far as this project
     is concerned is _this_ particular version of the license (ie v2, not
     v2.2 or v3.x or whatever), unless explicitly otherwise stated.

     HOWEVER, in order to allow a migration to GPLv3 if that seems like
     a good idea, I also ask that people involved with the project make
     their preferences known. In particular, if you trust me to make that
     decision, you might note so in your copyright message, ie something
     like

            This file is licensed under the GPL v2, or a later version
            at the discretion of Linus.

      might avoid issues. But we can also just decide to synchronize and
      contact all copyright holders on record if/when the occasion arises.

As far as I am concerned, I am willing to license my work under the
GPLv2 or any later version at the discretion of whoever wants to work
with it.  I think that should be compatible with the project goals.

Now the above passage states "you might note so in your copyright
message", but my patches do not even contain a copyright message and it
is not clear to me that they should, or that there is a sensible place
to place such "copyright messages".

So any guidance about that?

-- 
David Kastrup

Re: [PATCH 0/2] Two janitorial patches for builtin/blame.c

[Jonathan Nieder]

David Kastrup wrote:

> Now I might have sent at an unopportune time: blame.c is mostly
> attributed to Junio who seems to have been a few days absent now.
>
> I also have seen quite a few mails and patch submissions on the list go
> basically unanswered in the last few days.

In the U.S., yesterday was a federal holiday (Martin Luther King, Jr.
day) and the two days before were the weekend.

[...]
>             maintained indefinitely and may be redistributed consistent with
>             this project or the open source license(s) involved.
>
> Now the file involved (builtin/blame.c) itself does not state _any_
> license.

Most of git is GPLv2-only.  (As an aside, if there's interest then I'd
be happy to see most of it change to GPLv2-or-later since that makes
it possible to link to code under the Apache License.  But I'm also
happy with the status quo.)

[...]
> As far as I am concerned, I am willing to license my work under the
> GPLv2 or any later version at the discretion of whoever wants to work
> with it.  I think that should be compatible with the project goals.
>
> Now the above passage states "you might note so in your copyright
> message", but my patches do not even contain a copyright message and it
> is not clear to me that they should, or that there is a sensible place
> to place such "copyright messages".

Yeah, since these patches aren't adding a large new chunk of code
there's no need for a new copyright notice and so no place to put that
kind of thing unless Junio wants to relicense blame (which would be
orthogonal to these patches).

Thanks and hope that helps,
Jonathan

Re: [PATCH 0/2] Two janitorial patches for builtin/blame.c

[David Kastrup]

Jonathan Nieder <jrnieder@gmail.com> writes:

> David Kastrup wrote:
>
>> Now I might have sent at an unopportune time: blame.c is mostly
>> attributed to Junio who seems to have been a few days absent now.
>>
>> I also have seen quite a few mails and patch submissions on the list go
>> basically unanswered in the last few days.
>
> In the U.S., yesterday was a federal holiday (Martin Luther King, Jr.
> day) and the two days before were the weekend.

I see.

>> Now the file involved (builtin/blame.c) itself does not state _any_
>> license.
>
> Most of git is GPLv2-only.

Does that include builtin/blame.c?

> Yeah, since these patches aren't adding a large new chunk of code

Well, _significant_ chunks of code are in the works already (and my
question was really more about them).

> there's no need for a new copyright notice and so no place to put that
> kind of thing unless Junio wants to relicense blame (which would be
> orthogonal to these patches).

So my understanding is that when we are talking about _significant_
additions to builtin/blame.c (the current patches don't qualify as such
really) that

a) builtin/blame.c is licensed under GPLv2
b) significant contributions to it will not be relicensed under
different licenses without the respective contributors' explicit
consent.

This question is not academical to me.  I don't have any source of
income apart from people paying me to write free software (mainly
LilyPond users), so if I'm writing significant pieces of code, I don't
want to see them distributed as proprietary software (for example, by
traveling through the very unrestrictively licensed libgit2) without
being in the situation of negotiating recompensation for that.

The combination of the SubmittingPatches text with the file notices in
builtin/blame.c is not really painting a full picture of the situation.

-- 
David Kastrup

Re: [PATCH 0/2] Two janitorial patches for builtin/blame.c

[Jonathan Nieder]

David Kastrup wrote:

> So my understanding is that when we are talking about _significant_
> additions to builtin/blame.c (the current patches don't qualify as such
> really) that
>
> a) builtin/blame.c is licensed under GPLv2
> b) significant contributions to it will not be relicensed under
> different licenses without the respective contributors' explicit
> consent.

Yep, that's how it works.

[...]
> The combination of the SubmittingPatches text with the file notices in
> builtin/blame.c is not really painting a full picture of the situation.

Any idea how this could be made more clear?  E.g., maybe we should
bite the bullet and add a line to all source files that don't already
state a license:

	/*
	 * License: GPLv2.  See COPYING for details.
	 */

Re: [PATCH 0/2] Two janitorial patches for builtin/blame.c

[David Kastrup]

Jonathan Nieder <jrnieder@gmail.com> writes:

> David Kastrup wrote:
>
>> So my understanding is that when we are talking about _significant_
>> additions to builtin/blame.c (the current patches don't qualify as such
>> really) that
>>
>> a) builtin/blame.c is licensed under GPLv2
>> b) significant contributions to it will not be relicensed under
>> different licenses without the respective contributors' explicit
>> consent.
>
> Yep, that's how it works.
>
> [...]
>> The combination of the SubmittingPatches text with the file notices in
>> builtin/blame.c is not really painting a full picture of the situation.
>
> Any idea how this could be made more clear?  E.g., maybe we should
> bite the bullet and add a line to all source files that don't already
> state a license:
>
> 	/*
> 	 * License: GPLv2.  See COPYING for details.
> 	 */

Probably somewhat more verbose like "This file may be distributed under
the conditions of the GPLv2.  See the file COPYING for details".
I think there are boilerplate texts for that.

Whatever the exact wording, that would be the cleanest way I think.  The
respective Documentation/SubmittingPatches text looks like it is quoted
from somewhere else, so adapting it to the realities of files without
clear copyright statement seems less straightforward.

-- 
David Kastrup

Re: [PATCH 0/2] Two janitorial patches for builtin/blame.c

[Jonathan Nieder]

David Kastrup wrote:
> Jonathan Nieder <jrnieder@gmail.com> writes:

>> Any idea how this could be made more clear?  E.g., maybe we should
>> bite the bullet and add a line to all source files that don't already
>> state a license:
>>
>> 	/*
>> 	 * License: GPLv2.  See COPYING for details.
>> 	 */
>
> Probably somewhat more verbose like "This file may be distributed under
> the conditions of the GPLv2.  See the file COPYING for details".
> I think there are boilerplate texts for that.

All else being equal, longer is worse.

> Whatever the exact wording, that would be the cleanest way I think.  The
> respective Documentation/SubmittingPatches text looks like it is quoted
> from somewhere else, so adapting it to the realities of files without
> clear copyright statement seems less straightforward.

Hm, the wording comes from the Linux kernel project, where it's also
pretty normal not to have a license notice in every file (and where
the default license is also GPLv2).

Is the problem the phrase "indicated in the file", or is the problem
e.g. the lack of a pointer to
https://github.com/libgit2/libgit2/blob/development/git.git-authors?

Jonathan

Re: [PATCH 0/2] Two janitorial patches for builtin/blame.c

[Jonathan Nieder]

David Kastrup wrote:

> The combination of the SubmittingPatches text with the file notices in
> builtin/blame.c is not really painting a full picture of the situation.

BTW, thanks for bringing this up.  It last came up at [1].  Perhaps we
can do better by adding a note to README or some similar file
explaining that git is under the GPLv2 and files use that license when
not otherwise specified.

[1] http://thread.gmane.org/gmane.comp.version-control.git/234705/focus=234709

Re: [PATCH 0/2] Two janitorial patches for builtin/blame.c

[David Kastrup]

Jonathan Nieder <jrnieder@gmail.com> writes:

> David Kastrup wrote:
>> Jonathan Nieder <jrnieder@gmail.com> writes:
>
>>> Any idea how this could be made more clear?  E.g., maybe we should
>>> bite the bullet and add a line to all source files that don't already
>>> state a license:
>>>
>>> 	/*
>>> 	 * License: GPLv2.  See COPYING for details.
>>> 	 */
>>
>> Probably somewhat more verbose like "This file may be distributed under
>> the conditions of the GPLv2.  See the file COPYING for details".
>> I think there are boilerplate texts for that.
>
> All else being equal, longer is worse.

I am not sure that all else is equal.

>> Whatever the exact wording, that would be the cleanest way I think.  The
>> respective Documentation/SubmittingPatches text looks like it is quoted
>> from somewhere else, so adapting it to the realities of files without
>> clear copyright statement seems less straightforward.
>
> Hm, the wording comes from the Linux kernel project, where it's also
> pretty normal not to have a license notice in every file (and where
> the default license is also GPLv2).
>
> Is the problem the phrase "indicated in the file",

At least that's what I perceive as a problem in combination with the
complete absence of any such notice in the file I am contributing to.

git grep -i license

actually shows a dearth of licensing information outside of subprojects
and contrib.  The README file states

    Git is an Open Source project covered by the GNU General Public
    License version 2 (some parts of it are under different licenses,
    compatible with the GPLv2). It was originally written by Linus
    Torvalds with help of a group of hackers around the net.

without mentioning _which_ parts are under different licenses.  The
license file COPYING itself does not specify which files are covered,
and there is _also_ LGPL-2.1 which has a statement

     While most of this project is under the GPL (see COPYING), the
     xdiff/ library and some libc code from compat/ are licensed under
     the GNU LGPL, version 2.1 or (at your option) any later version and
     some other files are under other licenses.  Check the individual
     files to be sure.

Well, and when checking the individual files, there is really nothing
to be found for "being sure".

The net result is that when signing off on a patch according to the
rules in Documentation/SubmittingPatches, for most files you don't
really have a definite statement just _what_ license you are agreeing
your work to be distributed under.

> or is the problem
> e.g. the lack of a pointer to
> https://github.com/libgit2/libgit2/blob/development/git.git-authors?

No, not at all.  libgit2 is not in any way special among projects that
might want to have access to Git code under different licenses.  It
would be possible to state something like "Unless indicated otherwise,
consent will be assumed for contributions to Git as being
redistributable in the libgit2 project under its respective licenses" or
something, but I think that would be seriously surprising, and not
noticing such a clause could not be construed as implying consent.

-- 
David Kastrup

Re: [PATCH 0/2] Two janitorial patches for builtin/blame.c

[Jonathan Nieder]

David Kastrup wrote:

> and contrib.  The README file states
>
>     Git is an Open Source project covered by the GNU General Public
>     License version 2 (some parts of it are under different licenses,
>     compatible with the GPLv2). It was originally written by Linus
>     Torvalds with help of a group of hackers around the net.
>
> without mentioning _which_ parts are under different licenses.

Okay, how about this patch?

diff --git i/README w/README
index 15a8e23..6745db5 100644
--- i/README
+++ w/README
@@ -21,8 +21,9 @@ and full access to internals.
 
 Git is an Open Source project covered by the GNU General Public
 License version 2 (some parts of it are under different licenses,
-compatible with the GPLv2). It was originally written by Linus
-Torvalds with help of a group of hackers around the net.
+compatible with the GPLv2, and have notices to that effect). It was
+originally written by Linus Torvalds with help of a group of hackers
+around the net.
 
 Please read the file INSTALL for installation instructions.
 

Re: [PATCH 0/2] Two janitorial patches for builtin/blame.c

[Junio C Hamano]

Jonathan Nieder <jrnieder@gmail.com> writes:

> David Kastrup wrote:
>
>> So my understanding is that when we are talking about _significant_
>> additions to builtin/blame.c (the current patches don't qualify as such
>> really) that
>>
>> a) builtin/blame.c is licensed under GPLv2
>> b) significant contributions to it will not be relicensed under
>> different licenses without the respective contributors' explicit
>> consent.
>
> Yep, that's how it works.
>
> [...]
>> The combination of the SubmittingPatches text with the file notices in
>> builtin/blame.c is not really painting a full picture of the situation.
>
> Any idea how this could be made more clear?  E.g., maybe we should
> bite the bullet and add a line to all source files that don't already
> state a license:
>
> 	/*
> 	 * License: GPLv2.  See COPYING for details.
> 	 */

I vaguely recall that jgit folks at one point wanted to lift this
implementation and were interested in seeing it to be dual licensed
to BSD but that was a long time ago.

  http://git.661346.n2.nabble.com/JGIT-Blame-functionality-for-jgit-td2142726.html

Re: [PATCH 0/2] Two janitorial patches for builtin/blame.c

[David Kastrup]

Jonathan Nieder <jrnieder@gmail.com> writes:

> David Kastrup wrote:
>
>> and contrib.  The README file states
>>
>>     Git is an Open Source project covered by the GNU General Public
>>     License version 2 (some parts of it are under different licenses,
>>     compatible with the GPLv2). It was originally written by Linus
>>     Torvalds with help of a group of hackers around the net.
>>
>> without mentioning _which_ parts are under different licenses.
>
> Okay, how about this patch?
>
> diff --git i/README w/README
> index 15a8e23..6745db5 100644
> --- i/README
> +++ w/README
> @@ -21,8 +21,9 @@ and full access to internals.
>  
>  Git is an Open Source project covered by the GNU General Public
>  License version 2 (some parts of it are under different licenses,
> -compatible with the GPLv2). It was originally written by Linus
> -Torvalds with help of a group of hackers around the net.
> +compatible with the GPLv2, and have notices to that effect). It was
> +originally written by Linus Torvalds with help of a group of hackers
> +around the net.

Clearer.  I think it would be most accurate to state:

    Git is an Open Source project covered by the GNU General Public
    License version 2.  Those parts of it which may be also be
    distributed under other licenses contain notices to that effect.

The point is that as a whole, the software is distributed under GPLv2
(that's what "compatible" licensing actually means since the GPL demands
distribution of the software "as a whole" under the GPL) but parts of it
may optionally be distributed under other licenses.

-- 
David Kastrup

Re: [PATCH 1/2] builtin/blame.c: struct blame_entry does not need a prev link

[Junio C Hamano]

David Kastrup <dak@gnu.org> writes:

> ---

Thanks.  At some point during its development I must have thought
that having it as a dual-linked list may make it easier when we have
to split a block into pieces, but it seems that split_overlap() does
not need to look at this information.

Needs sign-off.


>  builtin/blame.c | 13 ++-----------
>  1 file changed, 2 insertions(+), 11 deletions(-)
>
> diff --git a/builtin/blame.c b/builtin/blame.c
> index e44a6bb..2195595 100644
> --- a/builtin/blame.c
> +++ b/builtin/blame.c
> @@ -197,7 +197,6 @@ static void drop_origin_blob(struct origin *o)
>   * scoreboard structure, sorted by the target line number.
>   */
>  struct blame_entry {
> -	struct blame_entry *prev;
>  	struct blame_entry *next;
>  
>  	/* the first line of this group in the final image;
> @@ -282,8 +281,6 @@ static void coalesce(struct scoreboard *sb)
>  		    ent->s_lno + ent->num_lines == next->s_lno) {
>  			ent->num_lines += next->num_lines;
>  			ent->next = next->next;
> -			if (ent->next)
> -				ent->next->prev = ent;
>  			origin_decref(next->suspect);
>  			free(next);
>  			ent->score = 0;
> @@ -534,7 +531,7 @@ static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)
>  		prev = ent;
>  
>  	/* prev, if not NULL, is the last one that is below e */
> -	e->prev = prev;
> +
>  	if (prev) {
>  		e->next = prev->next;
>  		prev->next = e;
> @@ -543,8 +540,6 @@ static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)
>  		e->next = sb->ent;
>  		sb->ent = e;
>  	}
> -	if (e->next)
> -		e->next->prev = e;
>  }
>  
>  /*
> @@ -555,14 +550,12 @@ static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)
>   */
>  static void dup_entry(struct blame_entry *dst, struct blame_entry *src)
>  {
> -	struct blame_entry *p, *n;
> +	struct blame_entry *n;
>  
> -	p = dst->prev;
>  	n = dst->next;
>  	origin_incref(src->suspect);
>  	origin_decref(dst->suspect);
>  	memcpy(dst, src, sizeof(*src));
> -	dst->prev = p;
>  	dst->next = n;
>  	dst->score = 0;
>  }
> @@ -2502,8 +2495,6 @@ parse_done:
>  		ent->suspect = o;
>  		ent->s_lno = bottom;
>  		ent->next = next;
> -		if (next)
> -			next->prev = ent;
>  		origin_incref(o);
>  	}
>  	origin_decref(o);

Re: [PATCH 0/2] Two janitorial patches for builtin/blame.c

[David Kastrup]

Junio C Hamano <gitster@pobox.com> writes:

> Jonathan Nieder <jrnieder@gmail.com> writes:
>
>> David Kastrup wrote:
>>
>>> So my understanding is that when we are talking about _significant_
>>> additions to builtin/blame.c (the current patches don't qualify as such
>>> really) that
>>>
>>> a) builtin/blame.c is licensed under GPLv2
>>> b) significant contributions to it will not be relicensed under
>>> different licenses without the respective contributors' explicit
>>> consent.
>>
>> Yep, that's how it works.
>>
>> [...]
>>> The combination of the SubmittingPatches text with the file notices in
>>> builtin/blame.c is not really painting a full picture of the situation.
>>
>> Any idea how this could be made more clear?  E.g., maybe we should
>> bite the bullet and add a line to all source files that don't already
>> state a license:
>>
>> 	/*
>> 	 * License: GPLv2.  See COPYING for details.
>> 	 */
>
> I vaguely recall that jgit folks at one point wanted to lift this
> implementation and were interested in seeing it to be dual licensed
> to BSD but that was a long time ago.
>
>   http://git.661346.n2.nabble.com/JGIT-Blame-functionality-for-jgit-td2142726.html

Ok, let me state quite clearly before we waste time, energy and
goodwill:

a) I am reworking the core logic of blame.c to make it produce the same
results while being orders of magnitude faster.  Git's current
implementation is a roadblock for serious use.  Keeping its current core
algorithms and data flow, it would have been reasonably easy to speed
the current code up by a factor of 2 or more by doing local
optimizations.  But I've chosen _not_ to keep the current logic and data
flow.  That means quite a bit more work, and it means completely
understanding the existing code before being able to replace it.

The core part of blame.c spends literally billions of iterations in
real-life situations leafing through one large linear list for tiny bits
of information.  One could use a better searchable data structure and
speed up the access in that manner, but better than a fast search is no
search at all.  I am separating the data so that at any given time I am
only accessing actually relevant data.  O(n) beats O(n lg n), and the
code remains almost as readable as the current O(n^2).

b) This will require thoroughly reworking the core parts of the
algorithm which will then be about 50/50 old and new code that cannot
sensibly be separated since significant parts of the previous code will
be gone completely as the data flow is fundamentally different.

c) The "fine points" of blame.c, in particular all the various command
line options and the implementation of their exact meaning would stay
the same.  I hope I can avoid touching more than 50% of the code.

d) I am fine with distributing my work under the GPLv2 or later, but no
other license will be implied.  While this does not affect the core Git
distribution itself: for distribution under more permissive licenses for
the purpose of making inclusion in proprietary software possible, I'd
probably attach a big price tag that reflects the amount of work and
quality of code going in and the fact that I have no other source of
income.

e) No idea whether this would affect JGIT: it depends on how much JGIT
would be a literal translation of blame.c into Java (?) or a
functionally equivalent rewrite employing different and/or native data
structures to achieve the same effect.  To me it's irritating that
something like the fine but boring points of option parsing might be
more susceptible to copyright protection than doing a careful
algorithmic design, but that's the way the world is wired.

At any rate: JGIT or not, I'll be contributing work with the
understanding that it will be licensed under the _current_ licensing
scheme of Git.  And I think that's a reasonable expectation.

-- 
David Kastrup

Re: [PATCH 1/2] builtin/blame.c: struct blame_entry does not need a prev link

[David Kastrup]

Junio C Hamano <gitster@pobox.com> writes:

> David Kastrup <dak@gnu.org> writes:
>
>> ---
>
> Thanks.  At some point during its development I must have thought
> that having it as a dual-linked list may make it easier when we have
> to split a block into pieces, but it seems that split_overlap() does
> not need to look at this information.
>
> Needs sign-off.

Well, as I said: it's quite possible that the double-linking might be
useful for some particular hypothetical rewrite of the code.  It isn't
for the current code, and it's not useful for my own rewrite.

Will be posting a signed-off version presently.

-- 
David Kastrup