{"thread":{"id":"35731","subject":"How to substructure rewrites?","startedAt":"2014-01-25T12:44:59Z","lastAt":"2014-01-27T21:21:16Z","messageCount":11,"participants":["David Kastrup","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"233748","messageId":"877g9ocjsk.fsf@fencepost.gnu.org","threadId":"35731","inReplyTo":null,"subject":"How to substructure rewrites?","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-01-25T12:44:59Z","receivedAt":"2014-01-25T12:44:59Z","isPatch":false,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"\nHi,\n\nI'm currently rewriting the internals of git-blame. For the somewhat\nacademic example\n\n\n\n#/bin/sh\n\ncd /tmp\nrm -rf testit\nmkdir testit\ncd testit\ngit init\nfor inc in 8 4 3 7 2 9 5 6 1\ndo\n seq 252000 -$inc 0 > testfile\n git add testfile\n git commit -m \"Run with increment $inc\"\ndone\ntime git blame testfile >/dev/null\n\n\n\nthe performance of git-blame increases by 4000%. It turns out that in\n\"real-world\" bad cases, particularly after aggressively repacking\nrepositories, the gains are quite more modest. I've seen a factor of 2\nwith source code and a factor of 3 with a large word list. The bulk of\nthe remaining time is spent in system time (which has basically not\nchanged by my work), so it is likely that the repository gets read over\nand over, calling for some better caching strategies.\n\nSo the question is how to restructure the work. I want to put out a\n\"teaser\" soonish but I think that there is little point in\nsubstructuring the commits I have so far. They start with a few\njanitorial patches already in pu, but after that there is\n\ncommit 7c610731e9452f3e8c175ab7e7542eafed1c5b93\nAuthor: David Kastrup \nDate: Sat Jan 25 13:19:17 2014 +0100\n\n wip\n\ncommit dca4c8c447b94e1a3f8f45874d5415665d503189\nAuthor: David Kastrup \nDate: Wed Jan 22 01:16:06 2014 +0100\n\n wip\n\ncommit f64b41c472442ae9971321fe8f62c3885ba4d8b7\nAuthor: David Kastrup \nDate: Sun Jan 19 02:16:21 2014 +0100\n\n blame.c: Let output determine MORE_THAN_ONE_PATH more efficiently\n\ncommit 607b094537d6fe4a75cf9a297470966bda934c73\nAuthor: David Kastrup \nDate: Mon Jan 13 18:06:06 2014 +0100\n\n wip\n\ncommit 1cd4e172533fb55793d02147c9596c59f7b05343\nAuthor: David Kastrup \nDate: Sun Jan 19 01:30:02 2014 +0100\n\n Reorganize blame data structures\n\ncommit 5ab2add67d5fcf3837623a7bc028bcaec1006cc4\nAuthor: David Kastrup \nDate: Sun Jan 19 01:29:28 2014 +0100\n\n Add blame_sort function for sorting a blame list\n\ncommit d3745752968617979878962ead957a6b5f829f0b\nAuthor: David Kastrup \nDate: Sun Jan 19 01:28:22 2014 +0100\n\n Add merge_blame function for merging two sorted blame lists.\n\n\nAs it can easily be guessed, the \"add xxx function\" commits are\nbasically adding not-yet-used code (and so will not disrupt\ncompilation), but everything starting with \"Reorganize blame data\nstructures\" up until the final commit will not work or compile since the\ncode does not match the data structures.\n\nSo there is little point in substructing all that, right? Even\nsomething seemingly isolated like\n\ncommit f64b41c472442ae9971321fe8f62c3885ba4d8b7\nAuthor: David Kastrup \nDate: Sun Jan 19 02:16:21 2014 +0100\n\n blame.c: Let output determine MORE_THAN_ONE_PATH more efficiently\n\nis not really useful as a separate commit since while it does implement\na particular task, this is done starting with non-working code relying\non no-longer existent data structures.\n\nI'm seriously considering squashing all that in a single commit. It\nseems like it would be utterly pointless to introduce artificially\nworking in-between states that simulate a partial \"migration\" to new\ndata structures that never happened. Where the algorithmic setup\nhappened, I rewrite from scratch, and it's pretty absurd to match and\nmarry efficient and inefficient half-algorithms.\n\nWhich brings us to point two: the \"teaser\" part. The current stuff has\n#if 0/#endif around the old implementation of the expensive -M and -C\noptions. They are currently not operative due to the mismatch to data\nstructures. Obviously, that makes the change unsuitable for putting\ninto master or anywhere close.\n\nI'd still want to solicit feedback: when not using those options (which\nwill likely cause me another week of headaches), the code is working\nwell and delivering identical information. So should I just squash the\nstuff and leave just the commits that made it into pu separate (so that\npeople may git-am whether or not they already have those commits)?\n\nIn general, the rule is likely \"any commit should not create a\nnon-working state\" right?\n\n-- \nDavid Kastrup\n"},{"id":"233755","messageId":"1390674221-25767-1-git-send-email-dak@gnu.org","threadId":"35731","inReplyTo":"877g9ocjsk.fsf@fencepost.gnu.org","subject":"[PATCH 0/3] \"Teaser\" patch for rewriting blame for efficiency","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-01-25T18:23:38Z","receivedAt":"2014-01-25T18:23:38Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Ok, here is the \"teaser\" for the git-blame rewrite. The first two\npatches are already in pu and only contained for simplicity. The\nthird patch gives a pretty good idea about the work that's up. It is\nmissing support for the -M and -C options (I think, if that's what the\n\"move\" and \"copy\" detection are supposed to be about). Part of\npreexisting code is #if 0/#endif removed since I don't know yet\nwhether the implementation of copy/move will need some of that.\n\nApart from these rather obvious problems, the question is whether it\nis ok to do the finished rewrite as a single commit since I cannot\nreally envision useful intermediate stages.\n\nWhile there is not much of a point on commenting on the code (and its\ntentative changes) within #if 0/#endif, the code that is actually\ncompiled is of course open to preliminary criticism.\n\nFor obvious reasons, patch #3 is not signed off: it should never be\ncommitted in its current form.\n\nDavid Kastrup (3):\n builtin/blame.c: struct blame_entry does not need a prev link\n Eliminate same_suspect function in builtin/blame.c\n builtin/blame.c: large-scale rewrite\n\n builtin/blame.c | 595 +++++++++++++++++++++++++++++++++++---------------------\n 1 file changed, 371 insertions(+), 224 deletions(-)\n\n-- \n1.8.3.2\n"},{"id":"233754","messageId":"1390674221-25767-2-git-send-email-dak@gnu.org","threadId":"35731","inReplyTo":"1390674221-25767-1-git-send-email-dak@gnu.org","subject":"[PATCH 1/3] builtin/blame.c: struct blame_entry does not need a prev link","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-01-25T18:23:39Z","receivedAt":"2014-01-25T18:23:39Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Signed-off-by: David Kastrup \n---\n builtin/blame.c | 13 ++-----------\n 1 file changed, 2 insertions(+), 11 deletions(-)\n\ndiff --git a/builtin/blame.c b/builtin/blame.c\nindex e44a6bb..2195595 100644\n--- a/builtin/blame.c\n+++ b/builtin/blame.c\n@@ -197,7 +197,6 @@ static void drop_origin_blob(struct origin *o)\n * scoreboard structure, sorted by the target line number.\n */\n struct blame_entry {\n-\tstruct blame_entry *prev;\n \tstruct blame_entry *next;\n \n \t/* the first line of this group in the final image;\n@@ -282,8 +281,6 @@ static void coalesce(struct scoreboard *sb)\n \t\t ent->s_lno + ent->num_lines == next->s_lno) {\n \t\t\tent->num_lines += next->num_lines;\n \t\t\tent->next = next->next;\n-\t\t\tif (ent->next)\n-\t\t\t\tent->next->prev = ent;\n \t\t\torigin_decref(next->suspect);\n \t\t\tfree(next);\n \t\t\tent->score = 0;\n@@ -534,7 +531,7 @@ static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)\n \t\tprev = ent;\n \n \t/* prev, if not NULL, is the last one that is below e */\n-\te->prev = prev;\n+\n \tif (prev) {\n \t\te->next = prev->next;\n \t\tprev->next = e;\n@@ -543,8 +540,6 @@ static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)\n \t\te->next = sb->ent;\n \t\tsb->ent = e;\n \t}\n-\tif (e->next)\n-\t\te->next->prev = e;\n }\n \n /*\n@@ -555,14 +550,12 @@ static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)\n */\n static void dup_entry(struct blame_entry *dst, struct blame_entry *src)\n {\n-\tstruct blame_entry *p, *n;\n+\tstruct blame_entry *n;\n \n-\tp = dst->prev;\n \tn = dst->next;\n \torigin_incref(src->suspect);\n \torigin_decref(dst->suspect);\n \tmemcpy(dst, src, sizeof(*src));\n-\tdst->prev = p;\n \tdst->next = n;\n \tdst->score = 0;\n }\n@@ -2502,8 +2495,6 @@ parse_done:\n \t\tent->suspect = o;\n \t\tent->s_lno = bottom;\n \t\tent->next = next;\n-\t\tif (next)\n-\t\t\tnext->prev = ent;\n \t\torigin_incref(o);\n \t}\n \torigin_decref(o);\n-- \n1.8.3.2\n"},{"id":"233753","messageId":"1390674221-25767-3-git-send-email-dak@gnu.org","threadId":"35731","inReplyTo":"1390674221-25767-1-git-send-email-dak@gnu.org","subject":"[PATCH 2/3] Eliminate same_suspect function in builtin/blame.c","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-01-25T18:23:40Z","receivedAt":"2014-01-25T18:23:40Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Since the origin pointers are \"interned\" and reference-counted, comparing\nthe pointers rather than the content is enough. The only uninterned\norigins are cached values kept in commit->util, but same_suspect is not\ncalled on them.\n\nSigned-off-by: David Kastrup \n---\n builtin/blame.c | 25 ++++++++-----------------\n 1 file changed, 8 insertions(+), 17 deletions(-)\n\ndiff --git a/builtin/blame.c b/builtin/blame.c\nindex 2195595..ead6148 100644\n--- a/builtin/blame.c\n+++ b/builtin/blame.c\n@@ -255,15 +255,6 @@ struct scoreboard {\n \tint *lineno;\n };\n \n-static inline int same_suspect(struct origin *a, struct origin *b)\n-{\n-\tif (a == b)\n-\t\treturn 1;\n-\tif (a->commit != b->commit)\n-\t\treturn 0;\n-\treturn !strcmp(a->path, b->path);\n-}\n-\n static void sanity_check_refcnt(struct scoreboard *);\n \n /*\n@@ -276,7 +267,7 @@ static void coalesce(struct scoreboard *sb)\n \tstruct blame_entry *ent, *next;\n \n \tfor (ent = sb->ent; ent && (next = ent->next); ent = next) {\n-\t\tif (same_suspect(ent->suspect, next->suspect) &&\n+\t\tif (ent->suspect == next->suspect &&\n \t\t ent->guilty == next->guilty &&\n \t\t ent->s_lno + ent->num_lines == next->s_lno) {\n \t\t\tent->num_lines += next->num_lines;\n@@ -735,7 +726,7 @@ static int find_last_in_target(struct scoreboard *sb, struct origin *target)\n \tint last_in_target = -1;\n \n \tfor (e = sb->ent; e; e = e->next) {\n-\t\tif (e->guilty || !same_suspect(e->suspect, target))\n+\t\tif (e->guilty || e->suspect != target)\n \t\t\tcontinue;\n \t\tif (last_in_target < e->s_lno + e->num_lines)\n \t\t\tlast_in_target = e->s_lno + e->num_lines;\n@@ -755,7 +746,7 @@ static void blame_chunk(struct scoreboard *sb,\n \tstruct blame_entry *e;\n \n \tfor (e = sb->ent; e; e = e->next) {\n-\t\tif (e->guilty || !same_suspect(e->suspect, target))\n+\t\tif (e->guilty || e->suspect != target)\n \t\t\tcontinue;\n \t\tif (same <= e->s_lno)\n \t\t\tcontinue;\n@@ -985,7 +976,7 @@ static int find_move_in_parent(struct scoreboard *sb,\n \twhile (made_progress) {\n \t\tmade_progress = 0;\n \t\tfor (e = sb->ent; e; e = e->next) {\n-\t\t\tif (e->guilty || !same_suspect(e->suspect, target) ||\n+\t\t\tif (e->guilty || e->suspect != target ||\n \t\t\t ent_score(sb, e) < blame_move_score)\n \t\t\t\tcontinue;\n \t\t\tfind_copy_in_blob(sb, e, parent, split, &file_p);\n@@ -1020,14 +1011,14 @@ static struct blame_list *setup_blame_list(struct scoreboard *sb,\n \n \tfor (e = sb->ent, num_ents = 0; e; e = e->next)\n \t\tif (!e->scanned && !e->guilty &&\n-\t\t same_suspect(e->suspect, target) &&\n+\t\t e->suspect == target &&\n \t\t min_score < ent_score(sb, e))\n \t\t\tnum_ents++;\n \tif (num_ents) {\n \t\tblame_list = xcalloc(num_ents, sizeof(struct blame_list));\n \t\tfor (e = sb->ent, i = 0; e; e = e->next)\n \t\t\tif (!e->scanned && !e->guilty &&\n-\t\t\t same_suspect(e->suspect, target) &&\n+\t\t\t e->suspect == target &&\n \t\t\t min_score < ent_score(sb, e))\n \t\t\t\tblame_list[i++].ent = e;\n \t}\n@@ -1171,7 +1162,7 @@ static void pass_whole_blame(struct scoreboard *sb,\n \t\torigin->file.ptr = NULL;\n \t}\n \tfor (e = sb->ent; e; e = e->next) {\n-\t\tif (!same_suspect(e->suspect, origin))\n+\t\tif (e->suspect != origin)\n \t\t\tcontinue;\n \t\torigin_incref(porigin);\n \t\torigin_decref(e->suspect);\n@@ -1560,7 +1551,7 @@ static void assign_blame(struct scoreboard *sb, int opt)\n \n \t\t/* Take responsibility for the remaining entries */\n \t\tfor (ent = sb->ent; ent; ent = ent->next)\n-\t\t\tif (same_suspect(ent->suspect, suspect))\n+\t\t\tif (ent->suspect == suspect)\n \t\t\t\tfound_guilty_entry(ent);\n \t\torigin_decref(suspect);\n \n-- \n1.8.3.2\n"},{"id":"233752","messageId":"1390674221-25767-4-git-send-email-dak@gnu.org","threadId":"35731","inReplyTo":"1390674221-25767-1-git-send-email-dak@gnu.org","subject":"[PATCH 3/3] builtin/blame.c: large-scale rewrite","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-01-25T18:23:41Z","receivedAt":"2014-01-25T18:23:41Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"The previous implementation uses a sorted linear list of struct\nblame_entry in a struct scoreboard for organizing all partial or\ncompleted work. Every task that is done requires going through the\nwhole list where most entries are not relevant to the task at hand.\n\nThis commit reorganizes the data structures in order to have each\nremaining subtask work with its own sorted linear list it can work off\nfront to back. Subtasks are organized into \"struct origin\" chains\nhanging off particular commits. Commits are organized into a priority\nqueue, processing them in commit date order in order to keep most of\nthe work affecting a particular blob collated even in the presence of\nan extensive merge history. In that manner, linear searches can be\nbasically avoided anywhere. They still are done for identifying one\nof multiple analyzed files in a given commit, but the degenerate case\nof a single large file being assembled from a multitude of smaller\nfiles in the past is not likely to occur often enough to warrant\nspecial treatment.\n---\n builtin/blame.c | 569 ++++++++++++++++++++++++++++++++++++--------------------\n 1 file changed, 367 insertions(+), 202 deletions(-)\n\ndiff --git a/builtin/blame.c b/builtin/blame.c\nindex ead6148..994a9e8 100644\n--- a/builtin/blame.c\n+++ b/builtin/blame.c\n@@ -18,7 +18,9 @@\n #include \"cache-tree.h\"\n #include \"string-list.h\"\n #include \"mailmap.h\"\n+#include \"mergesort.h\"\n #include \"parse-options.h\"\n+#include \"prio-queue.h\"\n #include \"utf8.h\"\n #include \"userdiff.h\"\n #include \"line-range.h\"\n@@ -83,11 +85,43 @@ static unsigned blame_copy_score;\n */\n struct origin {\n \tint refcnt;\n+\t/* Record preceding blame record for this blob */\n \tstruct origin *previous;\n+\t/* origins are put in a list linked via `next' hanging off the\n+\t * corresponding commit's util field in order to make finding\n+\t * them fast. The presence in this chain does not count\n+\t * towards the origin's reference count. It is tempting to\n+\t * let it count as long as the commit is pending examination,\n+\t * but even under circumstances where the commit will be\n+\t * present multiple times in the priority queue of unexamined\n+\t * commits, processing the first instance will not leave any\n+\t * work requiring the origin data for the second instance. An\n+\t * interspersed commit changing that would have to be\n+\t * preexisting with a different ancestry and with the same\n+\t * commit date in order to wedge itself between two instances\n+\t * of the same commit in the priority queue _and_ produce\n+\t * blame entries relevant for it. While we don't want to let\n+\t * us get tripped up by this case, it certainly does not seem\n+\t * worth optimizing for.\n+\t */\n+\tstruct origin *next;\n \tstruct commit *commit;\n+\t/* `suspects' contains blame entries that may be attributed to\n+\t * this origin's commit or to parent commits. When a commit\n+\t * is being processed, all suspects will be moved, either by\n+\t * assigning them to an origin in a different commit, or by\n+\t * shipping them to the scoreboard's ent list because they\n+\t * cannot be attributed to a different commit.\n+\t */\n+\tstruct blame_entry *suspects;\n \tmmfile_t file;\n \tunsigned char blob_sha1[20];\n \tunsigned mode;\n+\t/* shipped gets set when shipping any suspects to the final\n+\t * blame list instead of other commits\n+\t */\n+\tchar shipped;\n+\tchar guilty;\n \tchar path[FLEX_ARRAY];\n };\n \n@@ -176,10 +210,23 @@ static inline struct origin *origin_incref(struct origin *o)\n static void origin_decref(struct origin *o)\n {\n \tif (o && --o->refcnt <= 0) {\n+\t\tstruct origin *p, *l = NULL;\n \t\tif (o->previous)\n \t\t\torigin_decref(o->previous);\n \t\tfree(o->file.ptr);\n-\t\tfree(o);\n+\t\t/* Should be present exactly once in commit chain */\n+\t\tfor (p = o->commit->util; p; l = p, p = p->next) {\n+\t\t\tif (p == o)\n+\t\t\t{\n+\t\t\t\tif (l)\n+\t\t\t\t\tl->next = p->next;\n+\t\t\t\telse\n+\t\t\t\t\to->commit->util = p->next;\n+\t\t\t\tfree(o);\n+\t\t\t\treturn;\n+\t\t\t}\n+\t\t}\n+\t\tdie(\"internal error in blame::origin_decref\");\n \t}\n }\n \n@@ -193,8 +240,12 @@ static void drop_origin_blob(struct origin *o)\n \n /*\n * Each group of lines is described by a blame_entry; it can be split\n- * as we pass blame to the parents. They form a linked list in the\n- * scoreboard structure, sorted by the target line number.\n+ * as we pass blame to the parents. They are arranged in linked lists\n+ * kept as `suspects' of some unprocessed origin, or entered (when the\n+ * blame origin has been finalized) into the scoreboard structure.\n+ * While the scoreboard structure is only sorted at the end of\n+ * processing (according to final image line number), the lists\n+ * attached to an origin are sorted by the target line number.\n */\n struct blame_entry {\n \tstruct blame_entry *next;\n@@ -210,11 +261,6 @@ struct blame_entry {\n \t/* the commit that introduced this group into the final image */\n \tstruct origin *suspect;\n \n-\t/* true if the suspect is truly guilty; false while we have not\n-\t * checked if the group came from one of its parents.\n-\t */\n-\tchar guilty;\n-\n \t/* true if the entry has been scanned for copies in the current parent\n \t */\n \tchar scanned;\n@@ -230,12 +276,94 @@ struct blame_entry {\n \tunsigned score;\n };\n \n+/* This is subtle. Any _merge_ of blames happens on lists of blames\n+ * that arrived via different parents in a single suspect. In this\n+ * case, we want to sort according to the _suspect_ line numbers. In\n+ * contrast to that, blame_sort is used for the final sorting of blame\n+ * data and consequently works with final image line numbers.\n+ */\n+\n+static struct blame_entry *\n+blame_merge(struct blame_entry *list1,\n+\t struct blame_entry *list2)\n+{\n+\tstruct blame_entry *p1 = list1, *p2 = list2,\n+\t\t**tail = &list1;\n+\t\n+\tif (!p1)\n+\t\treturn p2;\n+\tif (!p2)\n+\t\treturn p1;\n+\n+\tif (p1->s_lno <= p2->s_lno)\n+\t{\n+\t\tdo {\n+\t\t\ttail = &p1->next;\n+\t\t\tif ((p1 = *tail) == NULL)\n+\t\t\t{\n+\t\t\t\t*tail = p2;\n+\t\t\t\treturn list1;\n+\t\t\t}\n+\t\t} while (p1->s_lno <= p2->s_lno);\n+\t}\n+\tfor (;;)\n+\t{\n+\t\t*tail = p2;\n+\t\tdo {\n+\t\t\ttail = &p2->next;\n+\t\t\tif ((p2 = *tail) == NULL) {\n+\t\t\t\t*tail = p1;\n+\t\t\t\treturn list1;\n+\t\t\t}\n+\t\t} while (p1->s_lno > p2->s_lno);\n+\t\t*tail = p1;\n+\t\tdo {\n+\t\t\ttail = &p1->next;\n+\t\t\tif ((p1 = *tail) == NULL) {\n+\t\t\t\t*tail = p2;\n+\t\t\t\treturn list1;\n+\t\t\t}\n+\t\t} while (p1->s_lno <= p2->s_lno);\n+\t}\n+}\n+\n+static void *\n+get_next_blame (const void *p)\n+{\n+\treturn ((struct blame_entry *)p)->next;\n+}\n+\n+static void\n+set_next_blame (void *p1, void *p2)\n+{\n+\t((struct blame_entry *)p1)->next = p2;\n+}\n+\n+static int\n+compare_blame (const void *p1, const void *p2)\n+{\n+\treturn ((struct blame_entry *)p1)->lno - ((struct blame_entry *)p2)->lno;\n+}\n+\n+static struct blame_entry *\n+blame_sort (struct blame_entry *head)\n+{\n+\treturn llist_mergesort (head, get_next_blame, set_next_blame, compare_blame);\n+}\n+\n+int compare_commits_by_reverse_commit_date(const void *a, const void *b, void *c)\n+{\n+\treturn -compare_commits_by_commit_date(a, b, c);\n+}\n+\n /*\n * The current state of the blame assignment.\n */\n struct scoreboard {\n \t/* the final commit (i.e. where we started digging from) */\n \tstruct commit *final;\n+\t/* Priority queue for commits with unassigned blame records */\n+\tstruct prio_queue commits;\n \tstruct rev_info *revs;\n \tconst char *path;\n \n@@ -268,7 +396,6 @@ static void coalesce(struct scoreboard *sb)\n \n \tfor (ent = sb->ent; ent && (next = ent->next); ent = next) {\n \t\tif (ent->suspect == next->suspect &&\n-\t\t ent->guilty == next->guilty &&\n \t\t ent->s_lno + ent->num_lines == next->s_lno) {\n \t\t\tent->num_lines += next->num_lines;\n \t\t\tent->next = next->next;\n@@ -295,23 +422,33 @@ static struct origin *make_origin(struct commit *commit, const char *path)\n \to = xcalloc(1, sizeof(*o) + strlen(path) + 1);\n \to->commit = commit;\n \to->refcnt = 1;\n+\to->next = commit->util;\n+\tcommit->util = o;\n \tstrcpy(o->path, path);\n \treturn o;\n }\n \n /*\n * Locate an existing origin or create a new one.\n+ * This moves the origin to front position in the commit util list.\n */\n static struct origin *get_origin(struct scoreboard *sb,\n \t\t\t\t struct commit *commit,\n \t\t\t\t const char *path)\n {\n-\tstruct blame_entry *e;\n+\tstruct origin *o, *l;\n \n-\tfor (e = sb->ent; e; e = e->next) {\n-\t\tif (e->suspect->commit == commit &&\n-\t\t !strcmp(e->suspect->path, path))\n-\t\t\treturn origin_incref(e->suspect);\n+\tfor (o = commit->util, l = NULL; o; l = o, o = o->next) {\n+\t\tif (!strcmp(o->path, path))\n+\t\t{\n+\t\t\t/* bump to front */\n+\t\t\tif (l) {\n+\t\t\t\tl->next = o->next;\n+\t\t\t\to->next = commit->util;\n+\t\t\t\tcommit->util = o;\n+\t\t\t}\n+\t\t\treturn origin_incref(o);\n+\t\t}\n \t}\n \treturn make_origin(commit, path);\n }\n@@ -350,41 +487,19 @@ static struct origin *find_origin(struct scoreboard *sb,\n \t\t\t\t struct commit *parent,\n \t\t\t\t struct origin *origin)\n {\n-\tstruct origin *porigin = NULL;\n+\tstruct origin *porigin;\n \tstruct diff_options diff_opts;\n \tconst char *paths[2];\n \n-\tif (parent->util) {\n-\t\t/*\n-\t\t * Each commit object can cache one origin in that\n-\t\t * commit. This is a freestanding copy of origin and\n-\t\t * not refcounted.\n-\t\t */\n-\t\tstruct origin *cached = parent->util;\n-\t\tif (!strcmp(cached->path, origin->path)) {\n+\t/* First check any existing origins */\n+\tfor (porigin = parent->util; porigin; porigin = porigin->next)\n+\t\tif (!strcmp(porigin->path, origin->path)) {\n \t\t\t/*\n \t\t\t * The same path between origin and its parent\n \t\t\t * without renaming -- the most common case.\n \t\t\t */\n-\t\t\tporigin = get_origin(sb, parent, cached->path);\n-\n-\t\t\t/*\n-\t\t\t * If the origin was newly created (i.e. get_origin\n-\t\t\t * would call make_origin if none is found in the\n-\t\t\t * scoreboard), it does not know the blob_sha1/mode,\n-\t\t\t * so copy it. Otherwise porigin was in the\n-\t\t\t * scoreboard and already knows blob_sha1/mode.\n-\t\t\t */\n-\t\t\tif (porigin->refcnt == 1) {\n-\t\t\t\thashcpy(porigin->blob_sha1, cached->blob_sha1);\n-\t\t\t\tporigin->mode = cached->mode;\n-\t\t\t}\n-\t\t\treturn porigin;\n+\t\t\treturn origin_incref (porigin);\n \t\t}\n-\t\t/* otherwise it was not very useful; free it */\n-\t\tfree(parent->util);\n-\t\tparent->util = NULL;\n-\t}\n \n \t/* See if the origin->path is different between parent\n \t * and origin first. Most of the time they are the\n@@ -450,19 +565,6 @@ static struct origin *find_origin(struct scoreboard *sb,\n \t}\n \tdiff_flush(&diff_opts);\n \tfree_pathspec(&diff_opts.pathspec);\n-\tif (porigin) {\n-\t\t/*\n-\t\t * Create a freestanding copy that is not part of\n-\t\t * the refcounted origin found in the scoreboard, and\n-\t\t * cache it in the commit.\n-\t\t */\n-\t\tstruct origin *cached;\n-\n-\t\tcached = make_origin(porigin->commit, porigin->path);\n-\t\thashcpy(cached->blob_sha1, porigin->blob_sha1);\n-\t\tcached->mode = porigin->mode;\n-\t\tparent->util = cached;\n-\t}\n \treturn porigin;\n }\n \n@@ -508,49 +610,53 @@ static struct origin *find_rename(struct scoreboard *sb,\n \treturn porigin;\n }\n \n+#if 0\n /*\n- * Link in a new blame entry to the scoreboard. Entries that cover the\n- * same line range have been removed from the scoreboard previously.\n+ * Add a new blame entry to a given output queue.\n */\n-static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)\n+static void add_blame_entry(struct blame_entry ***queue, struct blame_entry *e)\n {\n-\tstruct blame_entry *ent, *prev = NULL;\n-\n \torigin_incref(e->suspect);\n \n-\tfor (ent = sb->ent; ent && ent->lno < e->lno; ent = ent->next)\n-\t\tprev = ent;\n-\n-\t/* prev, if not NULL, is the last one that is below e */\n-\n-\tif (prev) {\n-\t\te->next = prev->next;\n-\t\tprev->next = e;\n-\t}\n-\telse {\n-\t\te->next = sb->ent;\n-\t\tsb->ent = e;\n-\t}\n+\te->next = **queue;\n+\t**queue = e;\n+\t*queue = &e->next;\n }\n \n /*\n * src typically is on-stack; we want to copy the information in it to\n- * a malloced blame_entry that is already on the linked list of the\n- * scoreboard. The origin of dst loses a refcnt while the origin of src\n- * gains one.\n+ * a blame_entry that is allocated in one queue and will be relocated\n+ * to another.\n */\n-static void dup_entry(struct blame_entry *dst, struct blame_entry *src)\n+static void dup_entry(struct blame_entry ***dstq, struct blame_entry ***srcq,\n+\t\t struct blame_entry *src)\n {\n-\tstruct blame_entry *n;\n-\n-\tn = dst->next;\n+\tstruct blame_entry *dst = **srcq;\n \torigin_incref(src->suspect);\n \torigin_decref(dst->suspect);\n+\t**srcq = dst->next;\t/* unlinked from source queue */\n \tmemcpy(dst, src, sizeof(*src));\n-\tdst->next = n;\n \tdst->score = 0;\n+\tdst->next = **dstq;\n+\t*dstq = &dst->next;\t/* linked into destination queue */\n }\n \n+/* This copies a changed entry over the existing entry in the queue */\n+static void trim_entry(struct blame_entry ***queue, struct blame_entry *src)\n+{\n+\tstruct blame_entry *dst = **queue;\n+\tstruct blame_entry *n = dst->next;\n+\t/* No need to mess with reference counts as we stay with the\n+\t * same suspect\n+\t */\n+\tmemcpy(dst, src, sizeof(*src));\n+\tdst->score = 0;\n+\tdst->next = n;\n+\t*queue = &dst->next;\t/* move after entry */\n+}\n+\n+#endif\n+\n static const char *nth_line(struct scoreboard *sb, long lno)\n {\n \treturn sb->final_buf + sb->lineno[lno];\n@@ -561,6 +667,7 @@ static const char *nth_line_cb(void *data, long lno)\n \treturn nth_line((struct scoreboard *)data, lno);\n }\n \n+#if 0\n /*\n * It is known that lines between tlno to same came from parent, and e\n * has an overlap with that range. it also is known that parent's\n@@ -573,7 +680,10 @@ static const char *nth_line_cb(void *data, long lno)\n * <------------------>\n *\n * Split e into potentially three parts; before this chunk, the chunk\n- * to be blamed for the parent, and after that portion.\n+ * to be blamed for the parent, and after that portion. As the chunks\n+ * are processed in sequence, any part before the overlap can be\n+ * terminally blamed on the target while parts after the overlap can\n+ * only be properly evaluated after examining future diffs.\n */\n static void split_overlap(struct blame_entry *split,\n \t\t\t struct blame_entry *e,\n@@ -620,72 +730,55 @@ static void split_overlap(struct blame_entry *split,\n \n /*\n * split_overlap() divided an existing blame e into up to three parts\n- * in split. Adjust the linked list of blames in the scoreboard to\n- * reflect the split.\n+ * in split. Adjust the linked list of blames to reflect the split,\n+ * the first part being common to target and parent and consequently\n+ * being blamed on the parent, the second part being different and\n+ * consequently blamed on the target, and the third part starting out\n+ * as being the same but without conclusive information where to place\n+ * the blame, so leaving it in the target subject to further\n+ * processing.\n */\n-static void split_blame(struct scoreboard *sb,\n-\t\t\tstruct blame_entry *split,\n-\t\t\tstruct blame_entry *e)\n+static void split_blame(struct blame_entry *split,\n+\t\t\tstruct blame_entry ***dstq,\n+\t\t\tstruct blame_entry ***srcq)\n {\n \tstruct blame_entry *new_entry;\n \n \tif (split[0].suspect && split[2].suspect) {\n \t\t/* The first part (reuse storage for the existing entry e) */\n-\t\tdup_entry(e, &split[0]);\n+\t\ttrim_entry(srcq, &split[0]);\n \n \t\t/* The last part -- me */\n \t\tnew_entry = xmalloc(sizeof(*new_entry));\n \t\tmemcpy(new_entry, &(split[2]), sizeof(struct blame_entry));\n-\t\tadd_blame_entry(sb, new_entry);\n+\t\tadd_blame_entry(srcq, new_entry);\n \n \t\t/* ... and the middle part -- parent */\n \t\tnew_entry = xmalloc(sizeof(*new_entry));\n \t\tmemcpy(new_entry, &(split[1]), sizeof(struct blame_entry));\n-\t\tadd_blame_entry(sb, new_entry);\n+\t\tadd_blame_entry(dstq, new_entry);\n \t}\n \telse if (!split[0].suspect && !split[2].suspect)\n \t\t/*\n \t\t * The parent covers the entire area; reuse storage for\n \t\t * e and replace it with the parent.\n \t\t */\n-\t\tdup_entry(e, &split[1]);\n+\t\tdup_entry(dstq, srcq, &split[1]);\n \telse if (split[0].suspect) {\n \t\t/* me and then parent */\n-\t\tdup_entry(e, &split[0]);\n+\t\ttrim_entry(srcq, &split[0]);\n \n \t\tnew_entry = xmalloc(sizeof(*new_entry));\n \t\tmemcpy(new_entry, &(split[1]), sizeof(struct blame_entry));\n-\t\tadd_blame_entry(sb, new_entry);\n+\t\tadd_blame_entry(dstq, new_entry);\n \t}\n \telse {\n \t\t/* parent and then me */\n-\t\tdup_entry(e, &split[1]);\n-\n \t\tnew_entry = xmalloc(sizeof(*new_entry));\n-\t\tmemcpy(new_entry, &(split[2]), sizeof(struct blame_entry));\n-\t\tadd_blame_entry(sb, new_entry);\n-\t}\n-\n-\tif (DEBUG) { /* sanity */\n-\t\tstruct blame_entry *ent;\n-\t\tint lno = sb->ent->lno, corrupt = 0;\n+\t\tmemcpy(new_entry, &(split[1]), sizeof(struct blame_entry));\n+\t\tadd_blame_entry(dstq, new_entry);\n \n-\t\tfor (ent = sb->ent; ent; ent = ent->next) {\n-\t\t\tif (lno != ent->lno)\n-\t\t\t\tcorrupt = 1;\n-\t\t\tif (ent->s_lno < 0)\n-\t\t\t\tcorrupt = 1;\n-\t\t\tlno += ent->num_lines;\n-\t\t}\n-\t\tif (corrupt) {\n-\t\t\tlno = sb->ent->lno;\n-\t\t\tfor (ent = sb->ent; ent; ent = ent->next) {\n-\t\t\t\tprintf(\"L %8d l %8d n %8d\\n\",\n-\t\t\t\t lno, ent->lno, ent->num_lines);\n-\t\t\t\tlno = ent->lno + ent->num_lines;\n-\t\t\t}\n-\t\t\tdie(\"oops\");\n-\t\t}\n+\t\ttrim_entry(srcq, &split[2]);\n \t}\n }\n \n@@ -702,74 +795,116 @@ static void decref_split(struct blame_entry *split)\n }\n \n /*\n- * Helper for blame_chunk(). blame_entry e is known to overlap with\n+ * Helper for blame_chunk(). blame_entry in srcq is known to overlap with\n * the patch hunk; split it and pass blame to the parent.\n */\n-static void blame_overlap(struct scoreboard *sb, struct blame_entry *e,\n+static void blame_overlap(struct blame entry ***dstq, struct blame_entry ***srcq,\n \t\t\t int tlno, int plno, int same,\n \t\t\t struct origin *parent)\n {\n \tstruct blame_entry split[3];\n \n-\tsplit_overlap(split, e, tlno, plno, same, parent);\n+\tsplit_overlap(split, **srcq, tlno, plno, same, parent);\n \tif (split[1].suspect)\n-\t\tsplit_blame(sb, split, e);\n+\t split_blame(split, dstq, srcq);\n \tdecref_split(split);\n }\n+#endif\n \n /*\n- * Find the line number of the last line the target is suspected for.\n+ * Process one hunk from the patch between the current suspect for\n+ * blame_entry e and its parent. This first blames any unfinished\n+ * entries before the chunk (which is where target and parent start\n+ * differing) on the parent, and then splits blame entries at the\n+ * start and at the end of the difference region.\n */\n-static int find_last_in_target(struct scoreboard *sb, struct origin *target)\n+static void blame_chunk(struct blame_entry ***dstq, struct blame_entry ***srcq,\n+\t\t\tint tlno, int offset, int same,\n+\t\t\tstruct origin *target, struct origin *parent)\n {\n-\tstruct blame_entry *e;\n-\tint last_in_target = -1;\n-\n-\tfor (e = sb->ent; e; e = e->next) {\n-\t\tif (e->guilty || e->suspect != target)\n-\t\t\tcontinue;\n-\t\tif (last_in_target < e->s_lno + e->num_lines)\n-\t\t\tlast_in_target = e->s_lno + e->num_lines;\n+\tstruct blame_entry *e = **srcq;\n+\t\n+/* Pass blame for everything before the differing chunk to the parent */\n+\twhile (e && e->s_lno + e->num_lines <= tlno) {\n+\t\t**dstq = e;\n+\t\torigin_decref(e->suspect);\n+\t\te->suspect = origin_incref(parent);\n+\t\te->s_lno += offset;\n+\t\te = *(*dstq = &e->next);\n \t}\n-\treturn last_in_target;\n-}\n-\n+\t**srcq = e;\n+\tif (!e)\n+\t\treturn;\n /*\n- * Process one hunk from the patch between the current suspect for\n- * blame_entry e and its parent. Find and split the overlap, and\n- * pass blame to the overlapping part to the parent.\n+ * current record _ends_ after the start of the difference region. If\n+ * it starts before it, we need to split it up and pass blame for its\n+ * first part to the parent.\n */\n-static void blame_chunk(struct scoreboard *sb,\n-\t\t\tint tlno, int plno, int same,\n-\t\t\tstruct origin *target, struct origin *parent)\n-{\n-\tstruct blame_entry *e;\n-\n-\tfor (e = sb->ent; e; e = e->next) {\n-\t\tif (e->guilty || e->suspect != target)\n-\t\t\tcontinue;\n-\t\tif (same <= e->s_lno)\n-\t\t\tcontinue;\n-\t\tif (tlno < e->s_lno + e->num_lines)\n-\t\t\tblame_overlap(sb, e, tlno, plno, same, parent);\n+\tif (e->s_lno < tlno) {\n+\t\t/* we move the first half to a new record */\n+\t\tint len = tlno - e->s_lno;\n+\t\tstruct blame_entry *n = xcalloc(1, sizeof (struct blame_entry));\n+\t\tn->suspect = origin_incref(parent);\n+\t\tn->lno = e->lno;\n+\t\tn->s_lno = e->s_lno + offset;\n+\t\tn->num_lines = len;\n+\t\tn->score = 0;\n+\t\t**dstq = n;\n+\t\t*dstq = &n->next;\n+\n+\t\te->lno += len;\n+\t\te->s_lno = tlno;\n+\t\te->num_lines -= len;\n+\t\te->score = 0;\n \t}\n+/*\n+ * Now retain records on the target while it is different from the parent.\n+ */\n+\twhile (e->s_lno + e->num_lines <= same) {\n+\t\te = *(*srcq = &e->next);\n+\t\tif (!e)\n+\t\t\treturn;\n+\t}\n+/*\n+ * If current record starts before sameness, need to split.\n+ */\n+\tif (e->s_lno < same) {\n+\t\tint len = same - e->s_lno;\n+\t\tstruct blame_entry *n = xcalloc(1, sizeof (struct blame_entry));\n+\t\tn->suspect = origin_incref(target);\n+\t\tn->lno = e->lno;\n+\t\tn->s_lno = e->s_lno;\n+\t\tn->num_lines = len;\n+\t\tn->score = 0;\n+\t\t**srcq = n;\n+\t\t*(*srcq = &n->next) = e;\n+\t\t/* keep second half in target queue */\n+\t\te->lno += len;\n+\t\te->s_lno = same;\n+\t\te->num_lines -= len;\n+\t\te->score = 0;\n+\t}\n+\treturn;\n }\n \n struct blame_chunk_cb_data {\n-\tstruct scoreboard *sb;\n \tstruct origin *target;\n \tstruct origin *parent;\n-\tlong plno;\n-\tlong tlno;\n+\tlong offset;\n+\tstruct blame_entry **dstq;\n+\tstruct blame_entry **srcq;\n };\n \n+/* diff chunks are from parent to target */\n static int blame_chunk_cb(long start_a, long count_a,\n \t\t\t long start_b, long count_b, void *data)\n {\n \tstruct blame_chunk_cb_data *d = data;\n-\tblame_chunk(d->sb, d->tlno, d->plno, start_b, d->target, d->parent);\n-\td->plno = start_a + count_a;\n-\td->tlno = start_b + count_b;\n+\tif (start_a - start_b != d->offset)\n+\t\tdie(\"internal error in blame::blame_chunk_cb\");\n+\tblame_chunk(&d->dstq, &d->srcq, start_b, start_a - start_b,\n+\t\t start_b + count_b, d->target, d->parent);\n+\td->offset = start_a + count_a - (start_b + count_b);\n \treturn 0;\n }\n \n@@ -782,23 +917,28 @@ static int pass_blame_to_parent(struct scoreboard *sb,\n \t\t\t\tstruct origin *target,\n \t\t\t\tstruct origin *parent)\n {\n-\tint last_in_target;\n \tmmfile_t file_p, file_o;\n \tstruct blame_chunk_cb_data d;\n+\tstruct blame_entry *newdest = NULL;\n \n-\tmemset(&d, 0, sizeof(d));\n-\td.sb = sb; d.target = target; d.parent = parent;\n-\tlast_in_target = find_last_in_target(sb, target);\n-\tif (last_in_target < 0)\n+\tif (!target->suspects)\n \t\treturn 1; /* nothing remains for this target */\n \n+\td.target = target; d.parent = parent;\n+\td.offset = 0;\n+\td.dstq = &newdest; d.srcq = &target->suspects;\n+\n \tfill_origin_blob(&sb->revs->diffopt, parent, &file_p);\n \tfill_origin_blob(&sb->revs->diffopt, target, &file_o);\n \tnum_get_patch++;\n \n \tdiff_hunks(&file_p, &file_o, 0, blame_chunk_cb, &d);\n-\t/* The rest (i.e. anything after tlno) are the same as the parent */\n-\tblame_chunk(sb, d.tlno, d.plno, last_in_target, target, parent);\n+\t/* The rest are the same as the parent */\n+\tblame_chunk(&d.dstq, &d.srcq, INT_MAX, d.offset, INT_MAX, target, parent);\n+\t*d.dstq = NULL;\n+\tparent->suspects = blame_merge (parent->suspects, newdest);\n+\tif (parent->suspects)\n+\t\tprio_queue_put(&sb->commits, parent->commit);\n \n \treturn 0;\n }\n@@ -833,6 +973,7 @@ static unsigned ent_score(struct scoreboard *sb, struct blame_entry *e)\n \treturn score;\n }\n \n+#if 0\n /*\n * best_so_far[] and this[] are both a split of an existing blame_entry\n * that passes blame to the parent. Maintain best_so_far the best split\n@@ -1147,6 +1288,8 @@ static int find_copy_in_parent(struct scoreboard *sb,\n \treturn retval;\n }\n \n+#endif\n+\n /*\n * The blobs of origin and porigin exactly match, so everything\n * origin is suspected for can be blamed on the parent.\n@@ -1154,20 +1297,22 @@ static int find_copy_in_parent(struct scoreboard *sb,\n static void pass_whole_blame(struct scoreboard *sb,\n \t\t\t struct origin *origin, struct origin *porigin)\n {\n-\tstruct blame_entry *e;\n+\tstruct blame_entry *e, *suspects;\n \n \tif (!porigin->file.ptr && origin->file.ptr) {\n \t\t/* Steal its file */\n \t\tporigin->file = origin->file;\n \t\torigin->file.ptr = NULL;\n \t}\n-\tfor (e = sb->ent; e; e = e->next) {\n-\t\tif (e->suspect != origin)\n-\t\t\tcontinue;\n+\tsuspects = origin->suspects;\n+\torigin->suspects = NULL;\n+\tfor (e = suspects; e; e = e->next) {\n \t\torigin_incref(porigin);\n \t\torigin_decref(e->suspect);\n \t\te->suspect = porigin;\n \t}\n+\tporigin->suspects = blame_merge(porigin->suspects, suspects);\n+\tprio_queue_put(&sb->commits, porigin->commit);\n }\n \n /*\n@@ -1266,6 +1411,7 @@ static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt)\n \t\t\tgoto finish;\n \t}\n \n+#if 0\n \t/*\n \t * Optionally find moves in parents' files.\n \t */\n@@ -1292,6 +1438,7 @@ static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt)\n \t\t\t\t\t\tporigin, opt))\n \t\t\t\tgoto finish;\n \t\t}\n+#endif\n \n finish:\n \tfor (i = 0; i < num_sg; i++) {\n@@ -1488,14 +1635,11 @@ static int emit_one_suspect_detail(struct origin *suspect, int repeat)\n }\n \n /*\n- * The blame_entry is found to be guilty for the range. Mark it\n- * as such, and show it in incremental output.\n+ * The blame_entry is found to be guilty for the range.\n+ * Show it in incremental output.\n */\n static void found_guilty_entry(struct blame_entry *ent)\n {\n-\tif (ent->guilty)\n-\t\treturn;\n-\tent->guilty = 1;\n \tif (incremental) {\n \t\tstruct origin *suspect = ent->suspect;\n \n@@ -1509,32 +1653,34 @@ static void found_guilty_entry(struct blame_entry *ent)\n }\n \n /*\n- * The main loop -- while the scoreboard has lines whose true origin\n- * is still unknown, pick one blame_entry, and allow its current\n- * suspect to pass blames to its parents.\n- */\n+ * The main loop -- while we have blobs with lines whose true origin\n+ * is still unknown, pick one blob, and allow its lines to pass blames\n+ * to its parents. */\n static void assign_blame(struct scoreboard *sb, int opt)\n {\n \tstruct rev_info *revs = sb->revs;\n+\tstruct commit *commit = prio_queue_get (&sb->commits);\n \n-\twhile (1) {\n+\twhile (commit) {\n \t\tstruct blame_entry *ent;\n-\t\tstruct commit *commit;\n-\t\tstruct origin *suspect = NULL;\n+\t\tstruct origin *suspect = commit->util;\n \n \t\t/* find one suspect to break down */\n-\t\tfor (ent = sb->ent; !suspect && ent; ent = ent->next)\n-\t\t\tif (!ent->guilty)\n-\t\t\t\tsuspect = ent->suspect;\n-\t\tif (!suspect)\n-\t\t\treturn; /* all done */\n+\t\twhile (suspect && !suspect->suspects)\n+\t\t\tsuspect = suspect->next;\n+\t\t\n+\t\tif (!suspect) {\n+\t\t\tcommit = prio_queue_get(&sb->commits);\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tassert(commit == suspect->commit);\n \n \t\t/*\n \t\t * We will use this suspect later in the loop,\n \t\t * so hold onto it in the meantime.\n \t\t */\n \t\torigin_incref(suspect);\n-\t\tcommit = suspect->commit;\n \t\tparse_commit(commit);\n \t\tif (reverse ||\n \t\t (!(commit->object.flags & UNINTERESTING) &&\n@@ -1550,9 +1696,22 @@ static void assign_blame(struct scoreboard *sb, int opt)\n \t\t\tcommit->object.flags |= UNINTERESTING;\n \n \t\t/* Take responsibility for the remaining entries */\n-\t\tfor (ent = sb->ent; ent; ent = ent->next)\n-\t\t\tif (ent->suspect == suspect)\n+\t\tent = suspect->suspects;\n+\t\tif (ent) {\n+\t\t\tfor (;;) {\n+\t\t\t\tstruct blame_entry *next = ent->next;\n \t\t\t\tfound_guilty_entry(ent);\n+\t\t\t\tif (next)\n+\t\t\t\t{\n+\t\t\t\t\tent = next;\n+\t\t\t\t\tcontinue;\n+\t\t\t\t}\n+\t\t\t\tent->next = sb->ent;\n+\t\t\t\tsb->ent = suspect->suspects;\n+\t\t\t\tsuspect->suspects = NULL;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n \t\torigin_decref(suspect);\n \n \t\tif (DEBUG) /* sanity */\n@@ -1609,9 +1768,8 @@ static void emit_porcelain(struct scoreboard *sb, struct blame_entry *ent,\n \tchar hex[41];\n \n \tstrcpy(hex, sha1_to_hex(suspect->commit->object.sha1));\n-\tprintf(\"%s%c%d %d %d\\n\",\n+\tprintf(\"%s %d %d %d\\n\",\n \t hex,\n-\t ent->guilty ? ' ' : '*', /* purely for debugging */\n \t ent->s_lno + 1,\n \t ent->lno + 1,\n \t ent->num_lines);\n@@ -1724,17 +1882,16 @@ static void output(struct scoreboard *sb, int option)\n \n \tif (option & OUTPUT_PORCELAIN) {\n \t\tfor (ent = sb->ent; ent; ent = ent->next) {\n-\t\t\tstruct blame_entry *oth;\n-\t\t\tstruct origin *suspect = ent->suspect;\n-\t\t\tstruct commit *commit = suspect->commit;\n+\t\t\tint count = 0;\n+\t\t\tstruct origin *suspect;\n+\t\t\tstruct commit *commit = ent->suspect->commit;\n \t\t\tif (commit->object.flags & MORE_THAN_ONE_PATH)\n \t\t\t\tcontinue;\n-\t\t\tfor (oth = ent->next; oth; oth = oth->next) {\n-\t\t\t\tif ((oth->suspect->commit != commit) ||\n-\t\t\t\t !strcmp(oth->suspect->path, suspect->path))\n-\t\t\t\t\tcontinue;\n-\t\t\t\tcommit->object.flags |= MORE_THAN_ONE_PATH;\n-\t\t\t\tbreak;\n+\t\t\tfor (suspect = commit->util; suspect; suspect = suspect->next) {\n+\t\t\t\tif (suspect->guilty && count++) {\n+\t\t\t\t\tcommit->object.flags |= MORE_THAN_ONE_PATH;\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n \t\t\t}\n \t\t}\n \t}\n@@ -2083,7 +2240,6 @@ static struct commit *fake_working_tree_commit(struct diff_options *opt,\n \torigin->file.ptr = buf.buf;\n \torigin->file.size = buf.len;\n \tpretend_sha1_file(buf.buf, buf.len, OBJ_BLOB, origin->blob_sha1);\n-\tcommit->util = origin;\n \n \t/*\n \t * Read the current index, replace the path entry with\n@@ -2394,12 +2550,16 @@ parse_done:\n \tmemset(&sb, 0, sizeof(sb));\n \n \tsb.revs = &revs;\n-\tif (!reverse)\n+\tif (!reverse) {\n \t\tfinal_commit_name = prepare_final(&sb);\n+\t\tsb.commits.compare = compare_commits_by_commit_date;\n+\t}\n \telse if (contents_from)\n \t\tdie(\"--contents and --children do not blend well.\");\n-\telse\n+\telse {\n \t\tfinal_commit_name = prepare_initial(&sb);\n+\t\tsb.commits.compare = compare_commits_by_reverse_commit_date;\n+\t}\n \n \tif (!sb.final) {\n \t\t/*\n@@ -2493,7 +2653,7 @@ parse_done:\n \trange_set_release(&ranges);\n \tstring_list_clear(&range_list, 0);\n \n-\tsb.ent = ent;\n+\tsb.ent = NULL;\n \tsb.path = path;\n \n \tread_mailmap(&mailmap, NULL);\n@@ -2501,11 +2661,16 @@ parse_done:\n \tif (!incremental)\n \t\tsetup_pager();\n \n+\tprio_queue_put(&sb.commits, o->commit);\n+\to->suspects = ent;\n+\t\n \tassign_blame(&sb, opt);\n \n \tif (incremental)\n \t\treturn 0;\n \n+\tsb.ent = blame_sort(sb.ent);\n+\n \tcoalesce(&sb);\n \n \tif (!(output_option & OUTPUT_PORCELAIN))\n-- \n1.8.3.2\n"},{"id":"233824","messageId":"xmqqppndpgbg.fsf@gitster.dls.corp.google.com","threadId":"35731","inReplyTo":"877g9ocjsk.fsf@fencepost.gnu.org","subject":"Re: How to substructure rewrites?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-01-27T15:58:27Z","receivedAt":"2014-01-27T15:58:27Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Kastrup writes:\n\n> As it can easily be guessed, the \"add xxx function\" commits are\n> basically adding not-yet-used code (and so will not disrupt\n> compilation), but everything starting with \"Reorganize blame data\n> structures\" up until the final commit will not work or compile since the\n> code does not match the data structures.\n>\n> So there is little point in substructing all that, right? Even\n> something seemingly isolated like\n>\n> commit f64b41c472442ae9971321fe8f62c3885ba4d8b7\n> Author: David Kastrup \n> Date: Sun Jan 19 02:16:21 2014 +0100\n>\n> blame.c: Let output determine MORE_THAN_ONE_PATH more efficiently\n>\n> is not really useful as a separate commit since while it does implement\n> a particular task, this is done starting with non-working code relying\n> on no-longer existent data structures.\n\nSmall pieces that are incrementally added with their own\ndocumentation would certainly be a lot easier to read than one big\nball of wax. I am wondering if it would make it easier for\neverybody to tentatively do \"git-blame vs git-blame2\" dance here,\njust like we did \"git-blame vs git-annotate\" dance some years ago.\nThat is, to add a completely new command and have them in parallel\nwhile cooking in 'next' (or we could even keep them in a few\nreleases if we are not absolutely certain about the correctness of\nthe result of the new code), aiming to eventually retire the current\nimplementation and replace it with the new one. We have already\nhave test infrastructure to allow us to run variants of blames, too,\nto help that kind of transition.\n\n> In general, the rule is likely \"any commit should not create a\n> non-working state\" right?\n\nYes.\n"},{"id":"233827","messageId":"87eh3t8k5h.fsf@fencepost.gnu.org","threadId":"35731","inReplyTo":"xmqqppndpgbg.fsf@gitster.dls.corp.google.com","subject":"Re: How to substructure rewrites?","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-01-27T16:27:38Z","receivedAt":"2014-01-27T16:27:38Z","isPatch":false,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> David Kastrup writes:\n>\n>> As it can easily be guessed, the \"add xxx function\" commits are\n>> basically adding not-yet-used code (and so will not disrupt\n>> compilation), but everything starting with \"Reorganize blame data\n>> structures\" up until the final commit will not work or compile since the\n>> code does not match the data structures.\n>>\n>> So there is little point in substructing all that, right? Even\n>> something seemingly isolated like\n>>\n>> commit f64b41c472442ae9971321fe8f62c3885ba4d8b7\n>> Author: David Kastrup \n>> Date: Sun Jan 19 02:16:21 2014 +0100\n>>\n>> blame.c: Let output determine MORE_THAN_ONE_PATH more efficiently\n>>\n>> is not really useful as a separate commit since while it does implement\n>> a particular task, this is done starting with non-working code relying\n>> on no-longer existent data structures.\n>\n> Small pieces that are incrementally added with their own\n> documentation would certainly be a lot easier to read than one big\n> ball of wax.\n\nSure. The problem is that my rewrite is characterized by doing as\nlittle as possible in order to achieve identical results (with the\nconceivable exception of picking a different, equally scored variant in\nthose parts of the algorithm choosing a maximum). That also means that\nthe basic logic and layout of the program stays the same while the data\nflow and parts of the data structures are replaced.\n\n> I am wondering if it would make it easier for everybody to tentatively\n> do \"git-blame vs git-blame2\" dance here, just like we did \"git-blame\n> vs git-annotate\" dance some years ago. That is, to add a completely\n> new command and have them in parallel while cooking in 'next' (or we\n> could even keep them in a few releases if we are not absolutely\n> certain about the correctness of the result of the new code), aiming\n> to eventually retire the current implementation and replace it with\n> the new one. We have already have test infrastructure to allow us to\n> run variants of blames, too, to help that kind of transition.\n\nWell, the point is that the implementation is supposed to\na) deliver identical results\nb) reuse as much code as possible\nso there is no real point in working with a separate source file.\n\nFor the \"if we are not absolutely certain about the correctness of the\nresult of the new code\" angle, this should be covered with the usual\nstable/unstable/proposed division most projects have in some way or\nanother for quality assurance. I have absolutely no clue how Git\norganizes that, but it would usually mean that the new code is not\nplaced in a different _file_ (or a differently named command) but rather\nin a different _branch_ as compared with the current implementation.\n\n>> In general, the rule is likely \"any commit should not create a\n>> non-working state\" right?\n>\n> Yes.\n\nMy current aim is to complete the code to the point where it is\na) fully operative and delivering equivalent results to the current\nimplementation\nb) in every aspect at least as efficient as the current implementation\nand in a state that is not basically less comprehensible than what I\nstarted with\n\nSince the change of the data structures and data flow requires changing\nall affected program parts to get to a working state, and since I don't\nhave ambitions to do more than that which is required to get there,\nI don't see how the bulk of the work can sensibly avoid coming as one\n\"omnibus\" patch. Most changes, however, will be understandable quite\nwell locally.\n\nFor example, currently the code has a number of loops traversing one\nglobal linked list, ignoring all entries not relevant to a particular\ntarget, and doing something with the rest. Those loops generally are\nreplaced with a simpler loop just running through a single _completely_\nrelevant linked list. Even while those replacements are scattered\nthroughout the patch, they make sense without having to look at the rest\nof the patch.\n\n-- \nDavid Kastrup\n"},{"id":"233830","messageId":"xmqq8uu1pdqq.fsf@gitster.dls.corp.google.com","threadId":"35731","inReplyTo":"1390674221-25767-4-git-send-email-dak@gnu.org","subject":"Re: [PATCH 3/3] builtin/blame.c: large-scale rewrite","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-01-27T16:54:05Z","receivedAt":"2014-01-27T16:54:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Kastrup writes:\n\n> The previous implementation uses a sorted linear list of struct\n> blame_entry in a struct scoreboard for organizing all partial or\n> completed work. Every task that is done requires going through the\n> whole list where most entries are not relevant to the task at hand.\n>\n> This commit reorganizes the data structures in order to have each\n> remaining subtask work with its own sorted linear list it can work off\n> front to back. Subtasks are organized into \"struct origin\" chains\n> hanging off particular commits. Commits are organized into a priority\n> queue, processing them in commit date order in order to keep most of\n> the work affecting a particular blob collated even in the presence of\n> an extensive merge history. In that manner, linear searches can be\n> basically avoided anywhere. They still are done for identifying one\n> of multiple analyzed files in a given commit, but the degenerate case\n> of a single large file being assembled from a multitude of smaller\n> files in the past is not likely to occur often enough to warrant\n> special treatment.\n> ---\n\nSign-off?\n\nActually, I'd like to take my previous suggestion to add this as\nblame2 (to replace blame in the future) back. That was based on my\nfear/hope to see an implementation based on a completely different\napproach, but the basic premise of having one blame_entry record per\nthe lines of the final image in the scoreboard, using diff between\nparents to the child to find common lines for passing the blame up,\netc. have not changed at all and the change is all about organizing\nthe pieces of data in a *much* *better* way to avoid needlessly\nfinding what we already have computed. It does look big (and if you\nremoved those \"#if 0/#endif\", the final patch would be a lot bigger\nbecause we will see a lot of deleted lines), but I do not think the\ncode conceptually is a different implementation to warrant \"create a\ntotally new blame2 and let it sit next to the original\".\n\nLooks nice overall.\n\n> diff --git a/builtin/blame.c b/builtin/blame.c\n> index ead6148..994a9e8 100644\n> --- a/builtin/blame.c\n> +++ b/builtin/blame.c\n> @@ -18,7 +18,9 @@\n> #include \"cache-tree.h\"\n> #include \"string-list.h\"\n> #include \"mailmap.h\"\n> +#include \"mergesort.h\"\n> #include \"parse-options.h\"\n> +#include \"prio-queue.h\"\n> #include \"utf8.h\"\n> #include \"userdiff.h\"\n> #include \"line-range.h\"\n> @@ -83,11 +85,43 @@ static unsigned blame_copy_score;\n> */\n> struct origin {\n> \tint refcnt;\n> +\t/* Record preceding blame record for this blob */\n> \tstruct origin *previous;\n> +\t/* origins are put in a list linked via `next' hanging off the\n> +\t * corresponding commit's util field in order to make finding\n> +\t * them fast. The presence in this chain does not count\n> +\t * towards the origin's reference count. It is tempting to\n> +\t * let it count as long as the commit is pending examination,\n> +\t * but even under circumstances where the commit will be\n> +\t * present multiple times in the priority queue of unexamined\n> +\t * commits, processing the first instance will not leave any\n> +\t * work requiring the origin data for the second instance. An\n> +\t * interspersed commit changing that would have to be\n> +\t * preexisting with a different ancestry and with the same\n> +\t * commit date in order to wedge itself between two instances\n> +\t * of the same commit in the priority queue _and_ produce\n> +\t * blame entries relevant for it. While we don't want to let\n> +\t * us get tripped up by this case, it certainly does not seem\n> +\t * worth optimizing for.\n> +\t */\n\nStyle; please make /* and */ sit on their own line without anything\nelse in multi-line comments.\n\n> +\tstruct origin *next;\n> \tstruct commit *commit;\n> +\t/* `suspects' contains blame entries that may be attributed to\n> +\t * this origin's commit or to parent commits. When a commit\n> +\t * is being processed, all suspects will be moved, either by\n> +\t * assigning them to an origin in a different commit, or by\n> +\t * shipping them to the scoreboard's ent list because they\n> +\t * cannot be attributed to a different commit.\n> +\t */\n> +\tstruct blame_entry *suspects;\n> \tmmfile_t file;\n> \tunsigned char blob_sha1[20];\n> \tunsigned mode;\n> +\t/* shipped gets set when shipping any suspects to the final\n> +\t * blame list instead of other commits\n> +\t */\n> +\tchar shipped;\n\nUnused?\n\n> +\tchar guilty;\n> \tchar path[FLEX_ARRAY];\n> };\n> \n> @@ -176,10 +210,23 @@ static inline struct origin *origin_incref(struct origin *o)\n> static void origin_decref(struct origin *o)\n> {\n> \tif (o && --o->refcnt <= 0) {\n> +\t\tstruct origin *p, *l = NULL;\n> \t\tif (o->previous)\n> \t\t\torigin_decref(o->previous);\n> \t\tfree(o->file.ptr);\n> -\t\tfree(o);\n> +\t\t/* Should be present exactly once in commit chain */\n> +\t\tfor (p = o->commit->util; p; l = p, p = p->next) {\n> +\t\t\tif (p == o)\n> +\t\t\t{\n\nStyle; please have { sit with the control structure that opens the\nblock, unless it is the opening brace of the function body or\nstruct/union definition.\n\n> +\t\t\t\tif (l)\n> +\t\t\t\t\tl->next = p->next;\n> +\t\t\t\telse\n> +\t\t\t\t\to->commit->util = p->next;\n> +\t\t\t\tfree(o);\n> +\t\t\t\treturn;\n> +\t\t\t}\n> +\t\t}\n> +\t\tdie(\"internal error in blame::origin_decref\");\n> \t}\n> }\n> \n> @@ -193,8 +240,12 @@ static void drop_origin_blob(struct origin *o)\n> \n> /*\n> * Each group of lines is described by a blame_entry; it can be split\n> - * as we pass blame to the parents. They form a linked list in the\n> - * scoreboard structure, sorted by the target line number.\n> + * as we pass blame to the parents. They are arranged in linked lists\n> + * kept as `suspects' of some unprocessed origin, or entered (when the\n> + * blame origin has been finalized) into the scoreboard structure.\n> + * While the scoreboard structure is only sorted at the end of\n> + * processing (according to final image line number), the lists\n> + * attached to an origin are sorted by the target line number.\n> */\n> struct blame_entry {\n> \tstruct blame_entry *next;\n> @@ -210,11 +261,6 @@ struct blame_entry {\n> \t/* the commit that introduced this group into the final image */\n> \tstruct origin *suspect;\n> \n> -\t/* true if the suspect is truly guilty; false while we have not\n> -\t * checked if the group came from one of its parents.\n> -\t */\n> -\tchar guilty;\n> -\n> \t/* true if the entry has been scanned for copies in the current parent\n> \t */\n> \tchar scanned;\n> @@ -230,12 +276,94 @@ struct blame_entry {\n> \tunsigned score;\n> };\n> \n> +/* This is subtle. Any _merge_ of blames happens on lists of blames\n> + * that arrived via different parents in a single suspect. In this\n> + * case, we want to sort according to the _suspect_ line numbers. In\n> + * contrast to that, blame_sort is used for the final sorting of blame\n> + * data and consequently works with final image line numbers.\n> + */\n> +\n> +static struct blame_entry *\n> +blame_merge(struct blame_entry *list1,\n> +\t struct blame_entry *list2)\n\nStyle; we do not do GNU-ish \"function name begins a line\". Even\nthough I personally find it easier to use for things like 'grep',\nthat is not the style we use around here.\n\n> +{\n> +\tstruct blame_entry *p1 = list1, *p2 = list2,\n> +\t\t**tail = &list1;\n> +\t\n> +\tif (!p1)\n> +\t\treturn p2;\n> +\tif (!p2)\n> +\t\treturn p1;\n> +\n> +\tif (p1->s_lno <= p2->s_lno)\n> +\t{\n> +\t\tdo {\n> +\t\t\ttail = &p1->next;\n> +\t\t\tif ((p1 = *tail) == NULL)\n> +\t\t\t{\n> +\t\t\t\t*tail = p2;\n> +\t\t\t\treturn list1;\n> +\t\t\t}\n> +\t\t} while (p1->s_lno <= p2->s_lno);\n> +\t}\n> +\tfor (;;)\n> +\t{\n> +\t\t*tail = p2;\n> +\t\tdo {\n> +\t\t\ttail = &p2->next;\n> +\t\t\tif ((p2 = *tail) == NULL) {\n> +\t\t\t\t*tail = p1;\n> +\t\t\t\treturn list1;\n> +\t\t\t}\n> +\t\t} while (p1->s_lno > p2->s_lno);\n> +\t\t*tail = p1;\n> +\t\tdo {\n> +\t\t\ttail = &p1->next;\n> +\t\t\tif ((p1 = *tail) == NULL) {\n> +\t\t\t\t*tail = p2;\n> +\t\t\t\treturn list1;\n> +\t\t\t}\n> +\t\t} while (p1->s_lno <= p2->s_lno);\n> +\t}\n> +}\n> +\n> +static void *\n> +get_next_blame (const void *p)\n> +{\n> +\treturn ((struct blame_entry *)p)->next;\n> +}\n> +\n> +static void\n> +set_next_blame (void *p1, void *p2)\n> +{\n> +\t((struct blame_entry *)p1)->next = p2;\n> +}\n> +\n> +static int\n> +compare_blame (const void *p1, const void *p2)\n> +{\n> +\treturn ((struct blame_entry *)p1)->lno - ((struct blame_entry *)p2)->lno;\n> +}\n> +\n> +static struct blame_entry *\n> +blame_sort (struct blame_entry *head)\n> +{\n> +\treturn llist_mergesort (head, get_next_blame, set_next_blame, compare_blame);\n> +}\n> +\n> +int compare_commits_by_reverse_commit_date(const void *a, const void *b, void *c)\n> +{\n> +\treturn -compare_commits_by_commit_date(a, b, c);\n> +}\n> +\n> /*\n> * The current state of the blame assignment.\n> */\n> struct scoreboard {\n> \t/* the final commit (i.e. where we started digging from) */\n> \tstruct commit *final;\n> +\t/* Priority queue for commits with unassigned blame records */\n> +\tstruct prio_queue commits;\n> \tstruct rev_info *revs;\n> \tconst char *path;\n> \n> @@ -268,7 +396,6 @@ static void coalesce(struct scoreboard *sb)\n> \n> \tfor (ent = sb->ent; ent && (next = ent->next); ent = next) {\n> \t\tif (ent->suspect == next->suspect &&\n> -\t\t ent->guilty == next->guilty &&\n> \t\t ent->s_lno + ent->num_lines == next->s_lno) {\n> \t\t\tent->num_lines += next->num_lines;\n> \t\t\tent->next = next->next;\n> @@ -295,23 +422,33 @@ static struct origin *make_origin(struct commit *commit, const char *path)\n> \to = xcalloc(1, sizeof(*o) + strlen(path) + 1);\n> \to->commit = commit;\n> \to->refcnt = 1;\n> +\to->next = commit->util;\n> +\tcommit->util = o;\n> \tstrcpy(o->path, path);\n> \treturn o;\n> }\n> \n> /*\n> * Locate an existing origin or create a new one.\n> + * This moves the origin to front position in the commit util list.\n> */\n> static struct origin *get_origin(struct scoreboard *sb,\n> \t\t\t\t struct commit *commit,\n> \t\t\t\t const char *path)\n> {\n> -\tstruct blame_entry *e;\n> +\tstruct origin *o, *l;\n> \n> -\tfor (e = sb->ent; e; e = e->next) {\n> -\t\tif (e->suspect->commit == commit &&\n> -\t\t !strcmp(e->suspect->path, path))\n> -\t\t\treturn origin_incref(e->suspect);\n> +\tfor (o = commit->util, l = NULL; o; l = o, o = o->next) {\n> +\t\tif (!strcmp(o->path, path))\n> +\t\t{\n> +\t\t\t/* bump to front */\n> +\t\t\tif (l) {\n> +\t\t\t\tl->next = o->next;\n> +\t\t\t\to->next = commit->util;\n> +\t\t\t\tcommit->util = o;\n> +\t\t\t}\n> +\t\t\treturn origin_incref(o);\n> +\t\t}\n> \t}\n> \treturn make_origin(commit, path);\n> }\n> @@ -350,41 +487,19 @@ static struct origin *find_origin(struct scoreboard *sb,\n> \t\t\t\t struct commit *parent,\n> \t\t\t\t struct origin *origin)\n> {\n> -\tstruct origin *porigin = NULL;\n> +\tstruct origin *porigin;\n> \tstruct diff_options diff_opts;\n> \tconst char *paths[2];\n> \n> -\tif (parent->util) {\n> -\t\t/*\n> -\t\t * Each commit object can cache one origin in that\n> -\t\t * commit. This is a freestanding copy of origin and\n> -\t\t * not refcounted.\n> -\t\t */\n> -\t\tstruct origin *cached = parent->util;\n> -\t\tif (!strcmp(cached->path, origin->path)) {\n> +\t/* First check any existing origins */\n> +\tfor (porigin = parent->util; porigin; porigin = porigin->next)\n> +\t\tif (!strcmp(porigin->path, origin->path)) {\n> \t\t\t/*\n> \t\t\t * The same path between origin and its parent\n> \t\t\t * without renaming -- the most common case.\n> \t\t\t */\n> -\t\t\tporigin = get_origin(sb, parent, cached->path);\n> -\n> -\t\t\t/*\n> -\t\t\t * If the origin was newly created (i.e. get_origin\n> -\t\t\t * would call make_origin if none is found in the\n> -\t\t\t * scoreboard), it does not know the blob_sha1/mode,\n> -\t\t\t * so copy it. Otherwise porigin was in the\n> -\t\t\t * scoreboard and already knows blob_sha1/mode.\n> -\t\t\t */\n> -\t\t\tif (porigin->refcnt == 1) {\n> -\t\t\t\thashcpy(porigin->blob_sha1, cached->blob_sha1);\n> -\t\t\t\tporigin->mode = cached->mode;\n> -\t\t\t}\n> -\t\t\treturn porigin;\n> +\t\t\treturn origin_incref (porigin);\n> \t\t}\n> -\t\t/* otherwise it was not very useful; free it */\n> -\t\tfree(parent->util);\n> -\t\tparent->util = NULL;\n> -\t}\n> \n> \t/* See if the origin->path is different between parent\n> \t * and origin first. Most of the time they are the\n> @@ -450,19 +565,6 @@ static struct origin *find_origin(struct scoreboard *sb,\n> \t}\n> \tdiff_flush(&diff_opts);\n> \tfree_pathspec(&diff_opts.pathspec);\n> -\tif (porigin) {\n> -\t\t/*\n> -\t\t * Create a freestanding copy that is not part of\n> -\t\t * the refcounted origin found in the scoreboard, and\n> -\t\t * cache it in the commit.\n> -\t\t */\n> -\t\tstruct origin *cached;\n> -\n> -\t\tcached = make_origin(porigin->commit, porigin->path);\n> -\t\thashcpy(cached->blob_sha1, porigin->blob_sha1);\n> -\t\tcached->mode = porigin->mode;\n> -\t\tparent->util = cached;\n> -\t}\n> \treturn porigin;\n> }\n> \n> @@ -508,49 +610,53 @@ static struct origin *find_rename(struct scoreboard *sb,\n> \treturn porigin;\n> }\n> \n> +#if 0\n> /*\n> - * Link in a new blame entry to the scoreboard. Entries that cover the\n> - * same line range have been removed from the scoreboard previously.\n> + * Add a new blame entry to a given output queue.\n> */\n> -static void add_blame_entry(struct scoreboard *sb, struct blame_entry *e)\n> +static void add_blame_entry(struct blame_entry ***queue, struct blame_entry *e)\n> {\n> -\tstruct blame_entry *ent, *prev = NULL;\n> -\n> \torigin_incref(e->suspect);\n> \n> -\tfor (ent = sb->ent; ent && ent->lno < e->lno; ent = ent->next)\n> -\t\tprev = ent;\n> -\n> -\t/* prev, if not NULL, is the last one that is below e */\n> -\n> -\tif (prev) {\n> -\t\te->next = prev->next;\n> -\t\tprev->next = e;\n> -\t}\n> -\telse {\n> -\t\te->next = sb->ent;\n> -\t\tsb->ent = e;\n> -\t}\n> +\te->next = **queue;\n> +\t**queue = e;\n> +\t*queue = &e->next;\n> }\n> \n> /*\n> * src typically is on-stack; we want to copy the information in it to\n> - * a malloced blame_entry that is already on the linked list of the\n> - * scoreboard. The origin of dst loses a refcnt while the origin of src\n> - * gains one.\n> + * a blame_entry that is allocated in one queue and will be relocated\n> + * to another.\n> */\n> -static void dup_entry(struct blame_entry *dst, struct blame_entry *src)\n> +static void dup_entry(struct blame_entry ***dstq, struct blame_entry ***srcq,\n> +\t\t struct blame_entry *src)\n> {\n> -\tstruct blame_entry *n;\n> -\n> -\tn = dst->next;\n> +\tstruct blame_entry *dst = **srcq;\n> \torigin_incref(src->suspect);\n> \torigin_decref(dst->suspect);\n> +\t**srcq = dst->next;\t/* unlinked from source queue */\n> \tmemcpy(dst, src, sizeof(*src));\n> -\tdst->next = n;\n> \tdst->score = 0;\n> +\tdst->next = **dstq;\n> +\t*dstq = &dst->next;\t/* linked into destination queue */\n> }\n> \n> +/* This copies a changed entry over the existing entry in the queue */\n> +static void trim_entry(struct blame_entry ***queue, struct blame_entry *src)\n> +{\n> +\tstruct blame_entry *dst = **queue;\n> +\tstruct blame_entry *n = dst->next;\n> +\t/* No need to mess with reference counts as we stay with the\n> +\t * same suspect\n> +\t */\n> +\tmemcpy(dst, src, sizeof(*src));\n> +\tdst->score = 0;\n> +\tdst->next = n;\n> +\t*queue = &dst->next;\t/* move after entry */\n> +}\n> +\n> +#endif\n> +\n> static const char *nth_line(struct scoreboard *sb, long lno)\n> {\n> \treturn sb->final_buf + sb->lineno[lno];\n> @@ -561,6 +667,7 @@ static const char *nth_line_cb(void *data, long lno)\n> \treturn nth_line((struct scoreboard *)data, lno);\n> }\n> \n> +#if 0\n> /*\n> * It is known that lines between tlno to same came from parent, and e\n> * has an overlap with that range. it also is known that parent's\n> @@ -573,7 +680,10 @@ static const char *nth_line_cb(void *data, long lno)\n> * <------------------>\n> *\n> * Split e into potentially three parts; before this chunk, the chunk\n> - * to be blamed for the parent, and after that portion.\n> + * to be blamed for the parent, and after that portion. As the chunks\n> + * are processed in sequence, any part before the overlap can be\n> + * terminally blamed on the target while parts after the overlap can\n> + * only be properly evaluated after examining future diffs.\n> */\n> static void split_overlap(struct blame_entry *split,\n> \t\t\t struct blame_entry *e,\n> @@ -620,72 +730,55 @@ static void split_overlap(struct blame_entry *split,\n> \n> /*\n> * split_overlap() divided an existing blame e into up to three parts\n> - * in split. Adjust the linked list of blames in the scoreboard to\n> - * reflect the split.\n> + * in split. Adjust the linked list of blames to reflect the split,\n> + * the first part being common to target and parent and consequently\n> + * being blamed on the parent, the second part being different and\n> + * consequently blamed on the target, and the third part starting out\n> + * as being the same but without conclusive information where to place\n> + * the blame, so leaving it in the target subject to further\n> + * processing.\n> */\n> -static void split_blame(struct scoreboard *sb,\n> -\t\t\tstruct blame_entry *split,\n> -\t\t\tstruct blame_entry *e)\n> +static void split_blame(struct blame_entry *split,\n> +\t\t\tstruct blame_entry ***dstq,\n> +\t\t\tstruct blame_entry ***srcq)\n> {\n> \tstruct blame_entry *new_entry;\n> \n> \tif (split[0].suspect && split[2].suspect) {\n> \t\t/* The first part (reuse storage for the existing entry e) */\n> -\t\tdup_entry(e, &split[0]);\n> +\t\ttrim_entry(srcq, &split[0]);\n> \n> \t\t/* The last part -- me */\n> \t\tnew_entry = xmalloc(sizeof(*new_entry));\n> \t\tmemcpy(new_entry, &(split[2]), sizeof(struct blame_entry));\n> -\t\tadd_blame_entry(sb, new_entry);\n> +\t\tadd_blame_entry(srcq, new_entry);\n> \n> \t\t/* ... and the middle part -- parent */\n> \t\tnew_entry = xmalloc(sizeof(*new_entry));\n> \t\tmemcpy(new_entry, &(split[1]), sizeof(struct blame_entry));\n> -\t\tadd_blame_entry(sb, new_entry);\n> +\t\tadd_blame_entry(dstq, new_entry);\n> \t}\n> \telse if (!split[0].suspect && !split[2].suspect)\n> \t\t/*\n> \t\t * The parent covers the entire area; reuse storage for\n> \t\t * e and replace it with the parent.\n> \t\t */\n> -\t\tdup_entry(e, &split[1]);\n> +\t\tdup_entry(dstq, srcq, &split[1]);\n> \telse if (split[0].suspect) {\n> \t\t/* me and then parent */\n> -\t\tdup_entry(e, &split[0]);\n> +\t\ttrim_entry(srcq, &split[0]);\n> \n> \t\tnew_entry = xmalloc(sizeof(*new_entry));\n> \t\tmemcpy(new_entry, &(split[1]), sizeof(struct blame_entry));\n> -\t\tadd_blame_entry(sb, new_entry);\n> +\t\tadd_blame_entry(dstq, new_entry);\n> \t}\n> \telse {\n> \t\t/* parent and then me */\n> -\t\tdup_entry(e, &split[1]);\n> -\n> \t\tnew_entry = xmalloc(sizeof(*new_entry));\n> -\t\tmemcpy(new_entry, &(split[2]), sizeof(struct blame_entry));\n> -\t\tadd_blame_entry(sb, new_entry);\n> -\t}\n> -\n> -\tif (DEBUG) { /* sanity */\n> -\t\tstruct blame_entry *ent;\n> -\t\tint lno = sb->ent->lno, corrupt = 0;\n> +\t\tmemcpy(new_entry, &(split[1]), sizeof(struct blame_entry));\n> +\t\tadd_blame_entry(dstq, new_entry);\n> \n> -\t\tfor (ent = sb->ent; ent; ent = ent->next) {\n> -\t\t\tif (lno != ent->lno)\n> -\t\t\t\tcorrupt = 1;\n> -\t\t\tif (ent->s_lno < 0)\n> -\t\t\t\tcorrupt = 1;\n> -\t\t\tlno += ent->num_lines;\n> -\t\t}\n> -\t\tif (corrupt) {\n> -\t\t\tlno = sb->ent->lno;\n> -\t\t\tfor (ent = sb->ent; ent; ent = ent->next) {\n> -\t\t\t\tprintf(\"L %8d l %8d n %8d\\n\",\n> -\t\t\t\t lno, ent->lno, ent->num_lines);\n> -\t\t\t\tlno = ent->lno + ent->num_lines;\n> -\t\t\t}\n> -\t\t\tdie(\"oops\");\n> -\t\t}\n> +\t\ttrim_entry(srcq, &split[2]);\n> \t}\n> }\n> \n> @@ -702,74 +795,116 @@ static void decref_split(struct blame_entry *split)\n> }\n> \n> /*\n> - * Helper for blame_chunk(). blame_entry e is known to overlap with\n> + * Helper for blame_chunk(). blame_entry in srcq is known to overlap with\n> * the patch hunk; split it and pass blame to the parent.\n> */\n> -static void blame_overlap(struct scoreboard *sb, struct blame_entry *e,\n> +static void blame_overlap(struct blame entry ***dstq, struct blame_entry ***srcq,\n> \t\t\t int tlno, int plno, int same,\n> \t\t\t struct origin *parent)\n> {\n> \tstruct blame_entry split[3];\n> \n> -\tsplit_overlap(split, e, tlno, plno, same, parent);\n> +\tsplit_overlap(split, **srcq, tlno, plno, same, parent);\n> \tif (split[1].suspect)\n> -\t\tsplit_blame(sb, split, e);\n> +\t split_blame(split, dstq, srcq);\n> \tdecref_split(split);\n> }\n> +#endif\n> \n> /*\n> - * Find the line number of the last line the target is suspected for.\n> + * Process one hunk from the patch between the current suspect for\n> + * blame_entry e and its parent. This first blames any unfinished\n> + * entries before the chunk (which is where target and parent start\n> + * differing) on the parent, and then splits blame entries at the\n> + * start and at the end of the difference region.\n> */\n> -static int find_last_in_target(struct scoreboard *sb, struct origin *target)\n> +static void blame_chunk(struct blame_entry ***dstq, struct blame_entry ***srcq,\n> +\t\t\tint tlno, int offset, int same,\n> +\t\t\tstruct origin *target, struct origin *parent)\n> {\n> -\tstruct blame_entry *e;\n> -\tint last_in_target = -1;\n> -\n> -\tfor (e = sb->ent; e; e = e->next) {\n> -\t\tif (e->guilty || e->suspect != target)\n> -\t\t\tcontinue;\n> -\t\tif (last_in_target < e->s_lno + e->num_lines)\n> -\t\t\tlast_in_target = e->s_lno + e->num_lines;\n> +\tstruct blame_entry *e = **srcq;\n> +\t\n> +/* Pass blame for everything before the differing chunk to the parent */\n> +\twhile (e && e->s_lno + e->num_lines <= tlno) {\n> +\t\t**dstq = e;\n> +\t\torigin_decref(e->suspect);\n> +\t\te->suspect = origin_incref(parent);\n> +\t\te->s_lno += offset;\n> +\t\te = *(*dstq = &e->next);\n> \t}\n> -\treturn last_in_target;\n> -}\n> -\n> +\t**srcq = e;\n> +\tif (!e)\n> +\t\treturn;\n> /*\n> - * Process one hunk from the patch between the current suspect for\n> - * blame_entry e and its parent. Find and split the overlap, and\n> - * pass blame to the overlapping part to the parent.\n> + * current record _ends_ after the start of the difference region. If\n> + * it starts before it, we need to split it up and pass blame for its\n> + * first part to the parent.\n> */\n> -static void blame_chunk(struct scoreboard *sb,\n> -\t\t\tint tlno, int plno, int same,\n> -\t\t\tstruct origin *target, struct origin *parent)\n> -{\n> -\tstruct blame_entry *e;\n> -\n> -\tfor (e = sb->ent; e; e = e->next) {\n> -\t\tif (e->guilty || e->suspect != target)\n> -\t\t\tcontinue;\n> -\t\tif (same <= e->s_lno)\n> -\t\t\tcontinue;\n> -\t\tif (tlno < e->s_lno + e->num_lines)\n> -\t\t\tblame_overlap(sb, e, tlno, plno, same, parent);\n> +\tif (e->s_lno < tlno) {\n> +\t\t/* we move the first half to a new record */\n> +\t\tint len = tlno - e->s_lno;\n> +\t\tstruct blame_entry *n = xcalloc(1, sizeof (struct blame_entry));\n> +\t\tn->suspect = origin_incref(parent);\n> +\t\tn->lno = e->lno;\n> +\t\tn->s_lno = e->s_lno + offset;\n> +\t\tn->num_lines = len;\n> +\t\tn->score = 0;\n> +\t\t**dstq = n;\n> +\t\t*dstq = &n->next;\n> +\n> +\t\te->lno += len;\n> +\t\te->s_lno = tlno;\n> +\t\te->num_lines -= len;\n> +\t\te->score = 0;\n> \t}\n> +/*\n> + * Now retain records on the target while it is different from the parent.\n> + */\n> +\twhile (e->s_lno + e->num_lines <= same) {\n> +\t\te = *(*srcq = &e->next);\n> +\t\tif (!e)\n> +\t\t\treturn;\n> +\t}\n> +/*\n> + * If current record starts before sameness, need to split.\n> + */\n> +\tif (e->s_lno < same) {\n> +\t\tint len = same - e->s_lno;\n> +\t\tstruct blame_entry *n = xcalloc(1, sizeof (struct blame_entry));\n> +\t\tn->suspect = origin_incref(target);\n> +\t\tn->lno = e->lno;\n> +\t\tn->s_lno = e->s_lno;\n> +\t\tn->num_lines = len;\n> +\t\tn->score = 0;\n> +\t\t**srcq = n;\n> +\t\t*(*srcq = &n->next) = e;\n> +\t\t/* keep second half in target queue */\n> +\t\te->lno += len;\n> +\t\te->s_lno = same;\n> +\t\te->num_lines -= len;\n> +\t\te->score = 0;\n> +\t}\n> +\treturn;\n> }\n> \n> struct blame_chunk_cb_data {\n> -\tstruct scoreboard *sb;\n> \tstruct origin *target;\n> \tstruct origin *parent;\n> -\tlong plno;\n> -\tlong tlno;\n> +\tlong offset;\n> +\tstruct blame_entry **dstq;\n> +\tstruct blame_entry **srcq;\n> };\n> \n> +/* diff chunks are from parent to target */\n> static int blame_chunk_cb(long start_a, long count_a,\n> \t\t\t long start_b, long count_b, void *data)\n> {\n> \tstruct blame_chunk_cb_data *d = data;\n> -\tblame_chunk(d->sb, d->tlno, d->plno, start_b, d->target, d->parent);\n> -\td->plno = start_a + count_a;\n> -\td->tlno = start_b + count_b;\n> +\tif (start_a - start_b != d->offset)\n> +\t\tdie(\"internal error in blame::blame_chunk_cb\");\n> +\tblame_chunk(&d->dstq, &d->srcq, start_b, start_a - start_b,\n> +\t\t start_b + count_b, d->target, d->parent);\n> +\td->offset = start_a + count_a - (start_b + count_b);\n> \treturn 0;\n> }\n> \n> @@ -782,23 +917,28 @@ static int pass_blame_to_parent(struct scoreboard *sb,\n> \t\t\t\tstruct origin *target,\n> \t\t\t\tstruct origin *parent)\n> {\n> -\tint last_in_target;\n> \tmmfile_t file_p, file_o;\n> \tstruct blame_chunk_cb_data d;\n> +\tstruct blame_entry *newdest = NULL;\n> \n> -\tmemset(&d, 0, sizeof(d));\n> -\td.sb = sb; d.target = target; d.parent = parent;\n> -\tlast_in_target = find_last_in_target(sb, target);\n> -\tif (last_in_target < 0)\n> +\tif (!target->suspects)\n> \t\treturn 1; /* nothing remains for this target */\n> \n> +\td.target = target; d.parent = parent;\n> +\td.offset = 0;\n> +\td.dstq = &newdest; d.srcq = &target->suspects;\n> +\n> \tfill_origin_blob(&sb->revs->diffopt, parent, &file_p);\n> \tfill_origin_blob(&sb->revs->diffopt, target, &file_o);\n> \tnum_get_patch++;\n> \n> \tdiff_hunks(&file_p, &file_o, 0, blame_chunk_cb, &d);\n> -\t/* The rest (i.e. anything after tlno) are the same as the parent */\n> -\tblame_chunk(sb, d.tlno, d.plno, last_in_target, target, parent);\n> +\t/* The rest are the same as the parent */\n> +\tblame_chunk(&d.dstq, &d.srcq, INT_MAX, d.offset, INT_MAX, target, parent);\n> +\t*d.dstq = NULL;\n> +\tparent->suspects = blame_merge (parent->suspects, newdest);\n> +\tif (parent->suspects)\n> +\t\tprio_queue_put(&sb->commits, parent->commit);\n> \n> \treturn 0;\n> }\n> @@ -833,6 +973,7 @@ static unsigned ent_score(struct scoreboard *sb, struct blame_entry *e)\n> \treturn score;\n> }\n> \n> +#if 0\n> /*\n> * best_so_far[] and this[] are both a split of an existing blame_entry\n> * that passes blame to the parent. Maintain best_so_far the best split\n> @@ -1147,6 +1288,8 @@ static int find_copy_in_parent(struct scoreboard *sb,\n> \treturn retval;\n> }\n> \n> +#endif\n> +\n> /*\n> * The blobs of origin and porigin exactly match, so everything\n> * origin is suspected for can be blamed on the parent.\n> @@ -1154,20 +1297,22 @@ static int find_copy_in_parent(struct scoreboard *sb,\n> static void pass_whole_blame(struct scoreboard *sb,\n> \t\t\t struct origin *origin, struct origin *porigin)\n> {\n> -\tstruct blame_entry *e;\n> +\tstruct blame_entry *e, *suspects;\n> \n> \tif (!porigin->file.ptr && origin->file.ptr) {\n> \t\t/* Steal its file */\n> \t\tporigin->file = origin->file;\n> \t\torigin->file.ptr = NULL;\n> \t}\n> -\tfor (e = sb->ent; e; e = e->next) {\n> -\t\tif (e->suspect != origin)\n> -\t\t\tcontinue;\n> +\tsuspects = origin->suspects;\n> +\torigin->suspects = NULL;\n> +\tfor (e = suspects; e; e = e->next) {\n> \t\torigin_incref(porigin);\n> \t\torigin_decref(e->suspect);\n> \t\te->suspect = porigin;\n> \t}\n> +\tporigin->suspects = blame_merge(porigin->suspects, suspects);\n> +\tprio_queue_put(&sb->commits, porigin->commit);\n> }\n> \n> /*\n> @@ -1266,6 +1411,7 @@ static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt)\n> \t\t\tgoto finish;\n> \t}\n> \n> +#if 0\n> \t/*\n> \t * Optionally find moves in parents' files.\n> \t */\n> @@ -1292,6 +1438,7 @@ static void pass_blame(struct scoreboard *sb, struct origin *origin, int opt)\n> \t\t\t\t\t\tporigin, opt))\n> \t\t\t\tgoto finish;\n> \t\t}\n> +#endif\n> \n> finish:\n> \tfor (i = 0; i < num_sg; i++) {\n> @@ -1488,14 +1635,11 @@ static int emit_one_suspect_detail(struct origin *suspect, int repeat)\n> }\n> \n> /*\n> - * The blame_entry is found to be guilty for the range. Mark it\n> - * as such, and show it in incremental output.\n> + * The blame_entry is found to be guilty for the range.\n> + * Show it in incremental output.\n> */\n> static void found_guilty_entry(struct blame_entry *ent)\n> {\n> -\tif (ent->guilty)\n> -\t\treturn;\n> -\tent->guilty = 1;\n> \tif (incremental) {\n> \t\tstruct origin *suspect = ent->suspect;\n> \n> @@ -1509,32 +1653,34 @@ static void found_guilty_entry(struct blame_entry *ent)\n> }\n> \n> /*\n> - * The main loop -- while the scoreboard has lines whose true origin\n> - * is still unknown, pick one blame_entry, and allow its current\n> - * suspect to pass blames to its parents.\n> - */\n> + * The main loop -- while we have blobs with lines whose true origin\n> + * is still unknown, pick one blob, and allow its lines to pass blames\n> + * to its parents. */\n> static void assign_blame(struct scoreboard *sb, int opt)\n> {\n> \tstruct rev_info *revs = sb->revs;\n> +\tstruct commit *commit = prio_queue_get (&sb->commits);\n> \n> -\twhile (1) {\n> +\twhile (commit) {\n> \t\tstruct blame_entry *ent;\n> -\t\tstruct commit *commit;\n> -\t\tstruct origin *suspect = NULL;\n> +\t\tstruct origin *suspect = commit->util;\n> \n> \t\t/* find one suspect to break down */\n> -\t\tfor (ent = sb->ent; !suspect && ent; ent = ent->next)\n> -\t\t\tif (!ent->guilty)\n> -\t\t\t\tsuspect = ent->suspect;\n> -\t\tif (!suspect)\n> -\t\t\treturn; /* all done */\n> +\t\twhile (suspect && !suspect->suspects)\n> +\t\t\tsuspect = suspect->next;\n> +\t\t\n> +\t\tif (!suspect) {\n> +\t\t\tcommit = prio_queue_get(&sb->commits);\n> +\t\t\tcontinue;\n> +\t\t}\n> +\n> +\t\tassert(commit == suspect->commit);\n> \n> \t\t/*\n> \t\t * We will use this suspect later in the loop,\n> \t\t * so hold onto it in the meantime.\n> \t\t */\n> \t\torigin_incref(suspect);\n> -\t\tcommit = suspect->commit;\n> \t\tparse_commit(commit);\n> \t\tif (reverse ||\n> \t\t (!(commit->object.flags & UNINTERESTING) &&\n> @@ -1550,9 +1696,22 @@ static void assign_blame(struct scoreboard *sb, int opt)\n> \t\t\tcommit->object.flags |= UNINTERESTING;\n> \n> \t\t/* Take responsibility for the remaining entries */\n> -\t\tfor (ent = sb->ent; ent; ent = ent->next)\n> -\t\t\tif (ent->suspect == suspect)\n> +\t\tent = suspect->suspects;\n> +\t\tif (ent) {\n> +\t\t\tfor (;;) {\n> +\t\t\t\tstruct blame_entry *next = ent->next;\n> \t\t\t\tfound_guilty_entry(ent);\n> +\t\t\t\tif (next)\n> +\t\t\t\t{\n> +\t\t\t\t\tent = next;\n> +\t\t\t\t\tcontinue;\n> +\t\t\t\t}\n> +\t\t\t\tent->next = sb->ent;\n> +\t\t\t\tsb->ent = suspect->suspects;\n> +\t\t\t\tsuspect->suspects = NULL;\n> +\t\t\t\tbreak;\n> +\t\t\t}\n> +\t\t}\n> \t\torigin_decref(suspect);\n> \n> \t\tif (DEBUG) /* sanity */\n> @@ -1609,9 +1768,8 @@ static void emit_porcelain(struct scoreboard *sb, struct blame_entry *ent,\n> \tchar hex[41];\n> \n> \tstrcpy(hex, sha1_to_hex(suspect->commit->object.sha1));\n> -\tprintf(\"%s%c%d %d %d\\n\",\n> +\tprintf(\"%s %d %d %d\\n\",\n> \t hex,\n> -\t ent->guilty ? ' ' : '*', /* purely for debugging */\n> \t ent->s_lno + 1,\n> \t ent->lno + 1,\n> \t ent->num_lines);\n> @@ -1724,17 +1882,16 @@ static void output(struct scoreboard *sb, int option)\n> \n> \tif (option & OUTPUT_PORCELAIN) {\n> \t\tfor (ent = sb->ent; ent; ent = ent->next) {\n> -\t\t\tstruct blame_entry *oth;\n> -\t\t\tstruct origin *suspect = ent->suspect;\n> -\t\t\tstruct commit *commit = suspect->commit;\n> +\t\t\tint count = 0;\n> +\t\t\tstruct origin *suspect;\n> +\t\t\tstruct commit *commit = ent->suspect->commit;\n> \t\t\tif (commit->object.flags & MORE_THAN_ONE_PATH)\n> \t\t\t\tcontinue;\n> -\t\t\tfor (oth = ent->next; oth; oth = oth->next) {\n> -\t\t\t\tif ((oth->suspect->commit != commit) ||\n> -\t\t\t\t !strcmp(oth->suspect->path, suspect->path))\n> -\t\t\t\t\tcontinue;\n> -\t\t\t\tcommit->object.flags |= MORE_THAN_ONE_PATH;\n> -\t\t\t\tbreak;\n> +\t\t\tfor (suspect = commit->util; suspect; suspect = suspect->next) {\n> +\t\t\t\tif (suspect->guilty && count++) {\n> +\t\t\t\t\tcommit->object.flags |= MORE_THAN_ONE_PATH;\n> +\t\t\t\t\tbreak;\n> +\t\t\t\t}\n> \t\t\t}\n> \t\t}\n> \t}\n> @@ -2083,7 +2240,6 @@ static struct commit *fake_working_tree_commit(struct diff_options *opt,\n> \torigin->file.ptr = buf.buf;\n> \torigin->file.size = buf.len;\n> \tpretend_sha1_file(buf.buf, buf.len, OBJ_BLOB, origin->blob_sha1);\n> -\tcommit->util = origin;\n> \n> \t/*\n> \t * Read the current index, replace the path entry with\n> @@ -2394,12 +2550,16 @@ parse_done:\n> \tmemset(&sb, 0, sizeof(sb));\n> \n> \tsb.revs = &revs;\n> -\tif (!reverse)\n> +\tif (!reverse) {\n> \t\tfinal_commit_name = prepare_final(&sb);\n> +\t\tsb.commits.compare = compare_commits_by_commit_date;\n> +\t}\n> \telse if (contents_from)\n> \t\tdie(\"--contents and --children do not blend well.\");\n> -\telse\n> +\telse {\n> \t\tfinal_commit_name = prepare_initial(&sb);\n> +\t\tsb.commits.compare = compare_commits_by_reverse_commit_date;\n> +\t}\n> \n> \tif (!sb.final) {\n> \t\t/*\n> @@ -2493,7 +2653,7 @@ parse_done:\n> \trange_set_release(&ranges);\n> \tstring_list_clear(&range_list, 0);\n> \n> -\tsb.ent = ent;\n> +\tsb.ent = NULL;\n> \tsb.path = path;\n> \n> \tread_mailmap(&mailmap, NULL);\n> @@ -2501,11 +2661,16 @@ parse_done:\n> \tif (!incremental)\n> \t\tsetup_pager();\n> \n> +\tprio_queue_put(&sb.commits, o->commit);\n> +\to->suspects = ent;\n> +\t\n> \tassign_blame(&sb, opt);\n> \n> \tif (incremental)\n> \t\treturn 0;\n> \n> +\tsb.ent = blame_sort(sb.ent);\n> +\n> \tcoalesce(&sb);\n> \n> \tif (!(output_option & OUTPUT_PORCELAIN))\n"},{"id":"233835","messageId":"87a9eh8b0d.fsf@fencepost.gnu.org","threadId":"35731","inReplyTo":"xmqq8uu1pdqq.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 3/3] builtin/blame.c: large-scale rewrite","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-01-27T19:45:06Z","receivedAt":"2014-01-27T19:45:06Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> David Kastrup writes:\n>\n>> The previous implementation uses a sorted linear list of struct\n>> blame_entry in a struct scoreboard for organizing all partial or\n>> completed work. Every task that is done requires going through the\n>> whole list where most entries are not relevant to the task at hand.\n>>\n>> This commit reorganizes the data structures in order to have each\n>> remaining subtask work with its own sorted linear list it can work off\n>> front to back. Subtasks are organized into \"struct origin\" chains\n>> hanging off particular commits. Commits are organized into a priority\n>> queue, processing them in commit date order in order to keep most of\n>> the work affecting a particular blob collated even in the presence of\n>> an extensive merge history. In that manner, linear searches can be\n>> basically avoided anywhere. They still are done for identifying one\n>> of multiple analyzed files in a given commit, but the degenerate case\n>> of a single large file being assembled from a multitude of smaller\n>> files in the past is not likely to occur often enough to warrant\n>> special treatment.\n>> ---\n>\n> Sign-off?\n\nNot while this is not fit for merging because of #if 0 etc and missing\nfunctionality. This is just for review.\n\n> Actually, I'd like to take my previous suggestion to add this as\n> blame2 (to replace blame in the future) back. That was based on my\n> fear/hope to see an implementation based on a completely different\n> approach, but the basic premise of having one blame_entry record per\n> the lines of the final image in the scoreboard, using diff between\n> parents to the child to find common lines for passing the blame up,\n> etc. have not changed at all and the change is all about organizing\n> the pieces of data in a *much* *better* way to avoid needlessly\n> finding what we already have computed.\n\nYes. Basically, the call graph outside of blame.c itself should be\npretty much the same.\n\n> Style; please make /* and */ sit on their own line without anything\n> else in multi-line comments.\n\nWill do.\n\n>> +\tstruct origin *next;\n>> \tstruct commit *commit;\n>> +\t/* `suspects' contains blame entries that may be attributed to\n>> +\t * this origin's commit or to parent commits. When a commit\n>> +\t * is being processed, all suspects will be moved, either by\n>> +\t * assigning them to an origin in a different commit, or by\n>> +\t * shipping them to the scoreboard's ent list because they\n>> +\t * cannot be attributed to a different commit.\n>> +\t */\n>> +\tstruct blame_entry *suspects;\n>> \tmmfile_t file;\n>> \tunsigned char blob_sha1[20];\n>> \tunsigned mode;\n>> +\t/* shipped gets set when shipping any suspects to the final\n>> +\t * blame list instead of other commits\n>> +\t */\n>> +\tchar shipped;\n>\n> Unused?\n\nMore like \"added, forgotten, added under yet another name\":\n\n>> +\tchar guilty;\n\nI'll have to decide which one to keep.\n\n>> +\t\t/* Should be present exactly once in commit chain */\n>> +\t\tfor (p = o->commit->util; p; l = p, p = p->next) {\n>> +\t\t\tif (p == o)\n>> +\t\t\t{\n>\n> Style; please have { sit with the control structure that opens the\n> block, unless it is the opening brace of the function body or\n> struct/union definition.\n\nOk.\n\n>> +static struct blame_entry *\n>> +blame_merge(struct blame_entry *list1,\n>> +\t struct blame_entry *list2)\n>\n> Style; we do not do GNU-ish \"function name begins a line\". Even\n> though I personally find it easier to use for things like 'grep',\n> that is not the style we use around here.\n\nOk. I'm also certain to have a few \"space between function name and\narguments\" left and will grep for those before submitting the next\nversion.\n\nNext version will at least include -M option, possibly leaving -C for\nlater.\n\n-- \nDavid Kastrup\n"},{"id":"233838","messageId":"xmqqtxcpno6i.fsf@gitster.dls.corp.google.com","threadId":"35731","inReplyTo":"87a9eh8b0d.fsf@fencepost.gnu.org","subject":"Re: [PATCH 3/3] builtin/blame.c: large-scale rewrite","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-01-27T20:51:33Z","receivedAt":"2014-01-27T20:51:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Kastrup writes:\n\n> Junio C Hamano writes:\n>\n>> David Kastrup writes:\n>>\n>>> The previous implementation uses a sorted linear list of struct\n>>> blame_entry in a struct scoreboard for organizing all partial or\n>>> completed work. Every task that is done requires going through the\n>>> whole list where most entries are not relevant to the task at hand.\n>>>\n>>> This commit reorganizes the data structures in order to have each\n>>> remaining subtask work with its own sorted linear list it can work off\n>>> front to back. Subtasks are organized into \"struct origin\" chains\n>>> hanging off particular commits. Commits are organized into a priority\n>>> queue, processing them in commit date order in order to keep most of\n>>> the work affecting a particular blob collated even in the presence of\n>>> an extensive merge history. In that manner, linear searches can be\n>>> basically avoided anywhere. They still are done for identifying one\n>>> of multiple analyzed files in a given commit, but the degenerate case\n>>> of a single large file being assembled from a multitude of smaller\n>>> files in the past is not likely to occur often enough to warrant\n>>> special treatment.\n>>> ---\n>>\n>> Sign-off?\n>\n> Not while this is not fit for merging because of #if 0 etc and missing\n> functionality. This is just for review.\n\nThat is not what Signing off a patch means, though ;-)\n\n>> Actually, I'd like to take my previous suggestion to add this as\n>> blame2 (to replace blame in the future) back. That was based on my\n>> fear/hope to see an implementation based on a completely different\n>> approach, but the basic premise of having one blame_entry record per\n>> the lines of the final image in the scoreboard, using diff between\n>> parents to the child to find common lines for passing the blame up,\n>> etc. have not changed at all and the change is all about organizing\n>> the pieces of data in a *much* *better* way to avoid needlessly\n>> finding what we already have computed.\n>\n> Yes. Basically, the call graph outside of blame.c itself should be\n> pretty much the same.\n> ...\n> Ok. I'm also certain to have a few \"space between function name and\n> arguments\" left and will grep for those before submitting the next\n> version.\n>\n> Next version will at least include -M option, possibly leaving -C for\n> later.\n\nOK. As we do not want to break the build in the middle of the\nseries, but we still want to keep the individual steps reviewable\nincrementally, I would think the best structure would be have the\nseries that consists of multiple steps \"the basic infrastructure is\nthere, but no rename following, and neither -M or -C works\", \"now\nrenames are followed\", \"now -M works\", etc., with tests that are not\nyet working (in the beginning, most of \"git blame\" test may no\nlonger work until the series is finished) marked with\n\n s/test_expect_success/test_expect_failure/\n\nand turn expect_failure into expect_success as the series advances.\nThat way, we may get a better picture of what each step achieves. I\ndunno.\n"},{"id":"233841","messageId":"87sis96rzn.fsf@fencepost.gnu.org","threadId":"35731","inReplyTo":"xmqqtxcpno6i.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH 3/3] builtin/blame.c: large-scale rewrite","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-01-27T21:21:16Z","receivedAt":"2014-01-27T21:21:16Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> David Kastrup writes:\n>\n>> Junio C Hamano writes:\n>>\n>>> David Kastrup writes:\n>>>\n>>>> The previous implementation uses a sorted linear list of struct\n>>>> blame_entry in a struct scoreboard for organizing all partial or\n>>>> completed work. Every task that is done requires going through the\n>>>> whole list where most entries are not relevant to the task at hand.\n>>>>\n>>>> This commit reorganizes the data structures in order to have each\n>>>> remaining subtask work with its own sorted linear list it can work off\n>>>> front to back. Subtasks are organized into \"struct origin\" chains\n>>>> hanging off particular commits. Commits are organized into a priority\n>>>> queue, processing them in commit date order in order to keep most of\n>>>> the work affecting a particular blob collated even in the presence of\n>>>> an extensive merge history. In that manner, linear searches can be\n>>>> basically avoided anywhere. They still are done for identifying one\n>>>> of multiple analyzed files in a given commit, but the degenerate case\n>>>> of a single large file being assembled from a multitude of smaller\n>>>> files in the past is not likely to occur often enough to warrant\n>>>> special treatment.\n>>>> ---\n>>>\n>>> Sign-off?\n>>\n>> Not while this is not fit for merging because of #if 0 etc and missing\n>> functionality. This is just for review.\n>\n> That is not what Signing off a patch means, though ;-)\n\nFrom Documentation/SubmittingPatches:\n\n The sign-off is a simple line at the end of the explanation for\n the patch, which certifies that you wrote it or otherwise have\n the right to pass it on as a open-source patch. The rules are\n pretty simple: if you can certify the below:\n\n Developer's Certificate of Origin 1.1\n\n By making a contribution to this project, I certify that:\n\nWell, and the patch is not in a state where I want to contribute it to\nthis project. Basically I first want to bring it into a state where\nI am not embarrassed by having my name attached to it.\n\nYes, that's probably not quite the idea of signing off...\n\n> OK. As we do not want to break the build in the middle of the\n> series, but we still want to keep the individual steps reviewable\n> incrementally, I would think the best structure would be have the\n> series that consists of multiple steps \"the basic infrastructure is\n> there, but no rename following, and neither -M or -C works\", \"now\n> renames are followed\", \"now -M works\", etc., with tests that are not\n> yet working (in the beginning, most of \"git blame\" test may no\n> longer work until the series is finished) marked with\n>\n> s/test_expect_success/test_expect_failure/\n>\n> and turn expect_failure into expect_success as the series advances.\n> That way, we may get a better picture of what each step achieves. I\n> dunno.\n\nSeems a bit pointless as the various functionalities are implemented in\nseparate code passages. Basically the only \"common\" code is\n\nstatic void pass_blame(struct scoreboard *sb, struct origin *origin, int opt)\n{\n\tstruct rev_info *revs = sb->revs;\n\tint i, pass, num_sg;\n\tstruct commit *commit = origin->commit;\n[...]\n\n#if 0\n\t/*\n\t * Optionally find moves in parents' files.\n\t */\n\tif (opt & PICKAXE_BLAME_MOVE)\n\t\tfor (i = 0, sg = first_scapegoat(revs, commit);\n\t\t i < num_sg && sg;\n\t\t sg = sg->next, i++) {\n\t\t\tstruct origin *porigin = sg_origin[i];\n\t\t\tif (!porigin)\n\t\t\t\tcontinue;\n\t\t\tif (find_move_in_parent(sb, origin, porigin))\n\t\t\t\tgoto finish;\n\t\t}\n\n\t/*\n\t * Optionally find copies from parents' files.\n\t */\n\tif (opt & PICKAXE_BLAME_COPY)\n\t\tfor (i = 0, sg = first_scapegoat(revs, commit);\n\t\t i < num_sg && sg;\n\t\t sg = sg->next, i++) {\n\t\t\tstruct origin *porigin = sg_origin[i];\n\t\t\tif (find_copy_in_parent(sb, origin, sg->item,\n\t\t\t\t\t\tporigin, opt))\n\t\t\t\tgoto finish;\n\t\t}\n#endif\n\n finish:\n\tfor (i = 0; i < num_sg; i++) {\n\t\tif (sg_origin[i]) {\n\t\t\tdrop_origin_blob(sg_origin[i]);\n\t\t\torigin_decref(sg_origin[i]);\n\t\t}\n\t}\n\tdrop_origin_blob(origin);\n\tif (sg_buf != sg_origin)\n\t\tfree(sg_origin);\n}\n\n\nSo what will happen here is that the #if 0 will get removed again, and\nthere will be somewhat different code for\n\n /*\n\t * Optionally find moves in parents' files.\n\t */\n\nand then somewhat different code for\n\n\t/*\n\t * Optionally find copies from parents' files.\n\t */\n\nand some section elsewhere with the functions being called here. It's\nnot like there will be significant intersection between the\n\"same-file-and-rename\" code and the \"move-in-file or\ncopy-from-some-other-file\" code. It's just a separate piece of code,\nmarked with a separate comment. Not an \"evolution\" of code, but rather\na simple addition. Basically each of those additions does \"try blaming\nsome more entries to some source different from the currently considered\ntarget\" and whatever remains at the end is blamed on the current target.\nAnd every such addition has its own algorithm and functions.\n\nAt any rate: I'll just propose the thing as one piece first and then we\ncan still discuss what kind of subdivision and/or\ncommenting/restructuring might be warranted and would simplify\nreviewing.\n\n-- \nDavid Kastrup\n"}]}