{"thread":{"id":"852","subject":"[PATCH] Add support for --wrt flag to git-rev-list","startedAt":"2005-06-07T06:00:16Z","lastAt":"2005-06-07T06:00:16Z","messageCount":1,"participants":["Jon Seymour"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"4666","messageId":"20050607060016.17261.qmail@blackcubes.dyndns.org","threadId":"852","inReplyTo":null,"subject":"[PATCH] Add support for --wrt flag to git-rev-list","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-07T06:00:16Z","receivedAt":"2005-06-07T06:00:16Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"[PATCH] Add support for --wrt flag to git-rev-list\n\nThis patch adds support for a --wrt flag to git-rev-list.\n\nWhen --wrt=author@domain is specified, --merge-order is implied but \nthe linearisation of non-linear epochs is adjusted so that branches\ncontributed to by author@domain sort after branches contributed by\nothers. This has effect of presenting a linear history changes as seen\nby author@domain's workspace.\n\nFor example, given this commit history:\n\na4 ---\n| \\   \\\n|  b4 |\n|/ |  |\na3 |  |\n|  |  |\na2 |  |\n|  |  c3\n|  |  |\n|  |  c2\n|  b3 |\n|  | /|\n|  b2 |\n|  |  c1\n|  | /\n|  b1    <-- commit authored by author@domain\na1 |\n|  |\na0 |\n| /\nroot\n\n--merge-order alone would sort it as follows:\n\n= a4\n| c3\n| c2\n| c1\n^ b4\n| b3\n| b2\n| b1\n^ a3\n| a2\n| a1\n| a0\n= root\n\nhowever, with --wrt=author@domain, git-rev-list sorts as follows:\n\n= a4\n| c3\n| c2\n| c1\n^ b4\n| a3\n| a2\n| a1\n| a0\n^ b3\n| b2\n| b1\n= root\n\nTo support this change, some additional functions were added to commit.c to allow\nthe extraction of author from the commit header.\n\nAlso, --show-breaks, like --wrt now implies --merge-order rather than requires it.\n\nThis change also updates Documentation/git-rev-list.txt to include documentation for\n--wrt and other git-rev-list options not currently documented.\n\nA test case has been included in t/t6000-rev-list.sh to verify this change works as\nexpected.\n\nUse of --wrt implies a small overhead (linear with respect to nodes printed) compared with --merge-order.\n\nSigned-off-by: Jon Seymour <jon.seymour@gmail.com>\n\nDiverged from ed37b5b2b94398f3ab8312dfdf23cfd25549e3ec by Linus Torvalds <torvalds@ppc970.osdl.org>\n---\ndiff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt\n--- a/Documentation/git-rev-list.txt\n+++ b/Documentation/git-rev-list.txt\n@@ -9,13 +9,25 @@ git-rev-list - Lists commit objects in r\n \n SYNOPSIS\n --------\n-'git-rev-list' [ *--max-count*=number ] [ *--max-age*=timestamp ] [ *--min-age*=timestamp ] [ *--merge-order* [ *--show-breaks* ] ] <commit>\n+'git-rev-list' [ *--max-count*=number ] [ *--max-age*=timestamp ] [ *--min-age*=timestamp ] [ *--pretty* ] [ *--parents* ] [ *--header* ] [ *--merge-order* [ *--show-breaks* ] ] [ *--wrt=author@domain* ] <head-to-include> <head-to-include> ... \n+^<base-to-exclude> \n+^<base-to-exclude> ...\n \n DESCRIPTION\n -----------\n-Lists commit objects in reverse chronological order starting at the\n-given commit, taking ancestry relationship into account.  This is\n-useful to produce human-readable log output.\n+\n+Lists commit objects in reverse chronological order starting at the commits specified by head-to-include values, \n+taking ancestry relationship into account.  git-rev-list will not print any commits that are reachable \n+by any of the base-to-exclude values. \n+\n+If *--pretty* is specified, git-rev-list prints a short summary of each commit on stdout. This can be usefully\n+parsed by git-shortlog to produce a short log of changes.\n+\n+If *--parents* is specified, git-rev-list prints a space separated list of parents on the same line as the\n+commit identifier.\n+\n+If *--header* is specified, git-rev-list prints to stdout, on line after the identifier of each commit, \n+the contents of the commit's header followed by a trailing NUL.\n \n If *--merge-order* is specified, the commit history is decomposed into a unique sequence of minimal, non-linear\n epochs and maximal, linear epochs. Non-linear epochs are then linearised by sorting them into merge order, which \n@@ -42,17 +54,22 @@ Commits marked with (=) represent the bo\n Commits marked with (|) are direct parents of commits immediately preceding the marked commit in the list.\n Commits marked with (^) are not parents of the immediately preceding commit. These \"breaks\" represent necessary discontinuities implied by trying to represent an arbtirary DAG in a linear form.\n \n-*--show-breaks* is only valid if *--merge-order* is also specified.\n+*--show-breaks* implies *--merge-order*.\n+\n+If *--wrt=author@domain* is specified, then --merge-order is implied but git-rev-list sorts commits\n+so that contemporaneously parallel commits (w.r.t. author@domain) appear to occur after (that is, sort before) \n+any commits authored by author@domain. This reflects the order in which author@domain's workspace sees contemporaneously\n+parallel changes.\n \n Author\n ------\n Written by Linus Torvalds <torvalds@osdl.org>\n \n-Original *--merge-order* logic by Jon Seymour <jon.seymour@gmail.com>\n+Original *--merge-order* and *--wrt* logic by Jon Seymour <jon.seymour@gmail.com>\n \n Documentation\n --------------\n-Documentation by David Greaves, Junio C Hamano and the git-list <git@vger.kernel.org>.\n+Documentation by David Greaves, Junio C Hamano, Jon Seymour and the git-list <git@vger.kernel.org>.\n \n GIT\n ---\ndiff --git a/commit.c b/commit.c\n--- a/commit.c\n+++ b/commit.c\n@@ -302,3 +302,65 @@ int count_parents(struct commit * commit\n         return count;\n }\n \n+int copy_commit_header(struct commit * commit, char * header, int index, char * buffer, int len)\n+{\n+\tchar * p = commit->buffer;\n+\t\n+\twhile (*p) {\t\t\n+\n+\t\tchar * q = header;\n+\t\tif (*p == '\\n') {\n+\t\t\tbreak;\n+\t\t}\n+\n+\t\tint matched;\n+\n+\t\tfor (matched = 1; *p != ' ' && *p != '\\n'; p++, q++) {\n+\t\t\tmatched = matched & (*q==*p);\n+\t\t}\n+\t\t\n+\t\tif (matched && index) {\n+\t\t\t// if we matched but we haven't seen the index'th element yet, \n+\t\t\t// just decrement the index then pretend we didn't match\n+\t\t\tindex--;\n+\t\t\tmatched = 0;\n+\t\t}\n+\t\t\n+\t\tif (!matched) {\n+\t\t\t\n+\t\t\t// skip to start of next header line\n+\t\t\t\n+\t\t\tfor (;*p!='\\n';p++)\n+\t\t\t\t;\n+\t\t\tp++;\n+\t\t\t\n+\t\t} else {\n+\t\t\t\n+\t\t\tint count = 0; // number of characters in value\n+\t\t\t\n+\t\t\tif (*p == ' ') {\t\t\t\t\n+\t\t\t\tp++;\n+\t\t\t\t\n+\t\t\t\tfor (count = 0; *p != '\\n'; p++, count++, len--) {\n+\t\t\t\t\tif (len > 0) {\n+\t\t\t\t\t\t*buffer++=*p;\t\t\t\t\n+\t\t\t\t\t}\t\t\t\t\t\t\n+\t\t\t\t}\n+\t\t\t\t\t\t\t\t\n+\t\t\t} \n+\t\t\t\n+\t\t\tif (len > 0) {\n+\t\t\t\t*buffer = 0;\n+\t\t\t}\n+\t\t\t\n+\t\t\treturn (len > 0) ? count+1 : -(count+1);\n+\t\t\t\n+\t\t}\t\t\t\n+\t}\n+\treturn 0;\n+}\n+\n+int copy_author(struct commit * commit, char * buffer, int len)\n+{\n+\treturn copy_commit_header(commit, \"author\", 0, buffer, len);\n+}\ndiff --git a/commit.h b/commit.h\n--- a/commit.h\n+++ b/commit.h\n@@ -53,4 +53,17 @@ struct commit *pop_most_recent_commit(st\n struct commit *pop_commit(struct commit_list **stack);\n \n int count_parents(struct commit * commit);\n+\n+//\n+// Copies the value of the (index+1)'th commit header matching the name specified\n+// into the buffer supplied and append a trailing NUL.\n+//\n+// Returns n<0 if the buffer was too short (-n is the required length)\n+// Returns 0 if the header doesn't exist.\n+// Returns n>0 where n is the length of the copied zero-terminated value, including the terminating zero.\n+//\n+int copy_commit_header(struct commit * commit, char * header, int index, char * buffer, int len);\n+\n+// Copies the commit's author value into the buffer supplied. Return values as per copy_commit_header.\n+int copy_author(struct commit * commit, char * buffer, int len);\n #endif /* COMMIT_H */\ndiff --git a/epoch.c b/epoch.c\n--- a/epoch.c\n+++ b/epoch.c\n@@ -464,17 +464,21 @@ static void sort_first_epoch(struct comm\n \t// so we need to reverse this list to output the oldest (or most \"local\") commits last.\n \t//\n \n-\tfor (parents = head->parents; parents; parents = parents->next)\n-\t\tcommit_list_insert(parents->item, &reversed_parents);\n-\n-\t//\n-\t// todo: by sorting the parents in a different order, we can alter the \n-\t// merge order to show contemporaneous changes in parallel branches\n-\t// occurring after \"local\" changes. This is useful for a developer\n-\t// when a developer wants to see all changes that were incorporated\n-\t// into the same merge as her own changes occur after her own\n-\t// changes.\n-\t//\n+\tif (!head->object.util) {\t\n+\t\t\n+\t\tfor (parents = head->parents; parents; parents = parents->next)\n+\t\t\tcommit_list_insert(parents->item, &reversed_parents);\n+\t\t\t\n+\t} else {\n+\t\t\n+\t\t// reverse the locally sorted parents and reset utility pointer to NULL\n+\t\t\n+\t\tparents = (struct commit_list *)head->object.util;\n+\t\thead->object.util = NULL;\n+\t\twhile (parents) {\n+\t\t\tcommit_list_insert(pop_commit(&parents), &reversed_parents);\n+\t\t}\n+\t}\t\t\t\n \n \twhile (reversed_parents) {\n \n@@ -555,13 +559,82 @@ static int emit_stack(struct commit_list\n }\n \n //\n+// Sort a list of commits in local last order. A commit is \"local\" if any of its ancestors (except the base)\n+// causes (*local_test)() to return a non-zero value.\n+//\n+// The sorted list is returned in *sorted. A side effect of this function is to set each object.util \n+// pointer to a list of parents sorted in local_last order.\n+//\n+// Does nothing except set *sorted to NULL if either list or local_test are NULL.\n+//\n+static void sort_list_in_local_last_order(struct commit_list * list, local_test_func local_test, struct commit_list ** sorted)\n+{\n+\tif (!list || !local_test) {\n+\t\t*sorted = NULL;\n+\t\treturn;\n+\t}\n+\t\n+        struct commit_list * next;\n+        \n+\tfor ( next = list ; next; next = next->next) {\n+\t\t\n+\t\tstruct commit * item = next->item;\n+\t\t\n+\t\tif (item->object.flags & BOUNDARY || item->object.util) {\n+\t\t\t// we have already visited this item or we have\n+\t\t\t// reached the boundary.\n+\t\t\tcontinue;\n+\t\t}\n+\t\t\n+ \t\tif ((*local_test)(item)) {\n+\t\t\titem->object.flags |= LOCAL;\t\t\t\n+ \t\t}\t\t\t\n+\t\t\n+\t\tsort_list_in_local_last_order(item->parents, local_test, (struct commit_list **)&item->object.util);\t\t\n+\t\t\n+\t\tstruct commit_list * sorted_parents = (struct commit_list *)&item->object.util;\n+\t\t\n+\t\tif (sorted_parents && (sorted_parents->item->object.flags & LOCAL)) {\n+\t\t\titem->object.flags |= LOCAL;\n+\t\t}\t\t\t\t\t\n+\t}\n+\t\n+\t//\n+\t// Iterate over the original list and generate two lists - a list of the\n+\t// non-local parents and list of local parents. Then splice the list\n+\t// of local parents onto the end of the non-local parents to form\n+\t// a new list.\n+\t//\n+\t\n+        struct commit_list * non_local = NULL;\n+        struct commit_list * local = NULL;                \n+        struct commit_list **p = &local;\n+        struct commit_list **q = &non_local;\n+        \n+\tfor (next = list; next; next = next->next) {\n+\t\t\n+\t\tif (next->item->object.flags & LOCAL) { \n+\t\t\t*p = commit_list_insert(next->item, p);\n+\t\t\tp = &(*p)->next;\n+\t\t} else {\n+\t\t\t*q = commit_list_insert(next->item, q);\n+\t\t\tq = &(*q)->next;\n+\t\t}\n+\t}\n+\t\n+\t*q = local;\t\n+\t*sorted = non_local;\n+\t\n+}\n+\n+//\n // Sorts an arbitrary epoch into merge order by sorting each epoch\n // of its epoch sequence into order.\n //\n // Note: this algorithm currently leaves traces of its execution in the\n // object flags of nodes it discovers. This should probably be fixed.\n //\n-static int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter)\n+static int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter, local_test_func local_test)\n {\n \tstruct commit *next = head_of_epoch;\n \tint ret = 0;\n@@ -602,6 +675,9 @@ static int sort_in_merge_order(struct co\n \t\t} else {\n \n \t\t\tstruct commit_list *stack = NULL;\n+\n+\t\t\tsort_list_in_local_last_order(next->parents, local_test, (struct commit_list **)&next->object.util);\n+\t\t\t\n \t\t\tsort_first_epoch(next, &stack);\n \t\t\taction = emit_stack(&stack, emitter);\n \t\t\tnext = base;\n@@ -623,7 +699,7 @@ static int sort_in_merge_order(struct co\n // subgraph using the sort_first_epoch algorithm. Once we have reached the base\n // we can continue sorting using sort_in_merge_order.\n //\n-int sort_list_in_merge_order(struct commit_list *list, emitter_func emitter)\n+int sort_list_in_merge_order(struct commit_list *list, emitter_func emitter, local_test_func local_test)\n {\n \tstruct commit_list *stack = NULL;\n \tstruct commit *base;\n@@ -631,7 +707,8 @@ int sort_list_in_merge_order(struct comm\n \tint ret = 0;\n \tint action = CONTINUE;\n \n-\tstruct commit_list *reversed = NULL;\n+\tstruct commit_list *filtered = NULL;\n+\tstruct commit_list **p = &filtered;\n \n \tfor (; list; list = list->next) {\n \n@@ -642,37 +719,50 @@ int sort_list_in_merge_order(struct comm\n \t\t\t\tfprintf(stderr, \"%s: duplicate commit %s ignored\\n\", __FUNCTION__, sha1_to_hex(next->object.sha1));\n \t\t\t} else {\n \t\t\t\tnext->object.flags |= DUPCHECK;\n-\t\t\t\tcommit_list_insert(list->item, &reversed);\n+\t\t\t\t*p = commit_list_insert(list->item, p);\n+\t\t\t\tp = &(*p)->next;\n \t\t\t}\n \t\t}\n \t}\n \n-\tif (!reversed->next) {\n+\tif (!filtered->next) {\n \n \t\t// if there is only one element in the list, we can sort it using \n \t\t// sort_in_merge_order.\n \n-\t\tbase = reversed->item;\n+\t\tbase = filtered->item;\n \n \t} else {\n \n \t\t// otherwise, we search for the base of the list\n \n-\t\tif ((ret = find_base_for_list(reversed, &base)))\n+\t\tif ((ret = find_base_for_list(filtered, &base)))\n \t\t\treturn ret;\n \n \t\tif (base) {\n \t\t\tbase->object.flags |= BOUNDARY;\n \t\t}\n-\n+\t\t\n+\t\tstruct commit_list * sorted;\n+\t\t\n+\t\tsort_list_in_local_last_order(filtered, local_test, &sorted);\n+\t\t\n+\t\tif (!sorted) {\n+\t\t\tsorted = filtered;\n+\t\t}\n+\t\t\n+\t\tstruct commit_list * reversed = NULL;\n+\t\twhile (sorted) \n+\t\t\tcommit_list_insert(pop_commit(&sorted), &reversed);\n+\t\t\n \t\twhile (reversed) {\n \t\t\tsort_first_epoch(pop_commit(&reversed), &stack);\n \t\t\tif (reversed) {\n \t\t\t\t//\n \t\t\t\t// if we have more commits to push, then the\n-\t\t\t\t// first push for the next parent may (or may not)\n+\t\t\t\t// first push for the next commit may (or may not)\n \t\t\t\t// represent a discontinuity with respect to the\n-\t\t\t\t// parent currently on the top of the stack.\n+\t\t\t\t// commit currently on the top of the stack.\n \t\t\t\t//\n \t\t\t\t// mark it for checking here, and check it\n \t\t\t\t// with the next push...see sort_first_epoch for\n@@ -686,8 +776,9 @@ int sort_list_in_merge_order(struct comm\n \t}\n \n \tif (base && (action != STOP)) {\n-\t\tret = sort_in_merge_order(base, emitter);\n+\t\tret = sort_in_merge_order(base, emitter, local_test);\n \t}\n \n \treturn ret;\n }\n+\ndiff --git a/epoch.h b/epoch.h\n--- a/epoch.h\n+++ b/epoch.h\n@@ -8,13 +8,18 @@\n #define DO       2\n typedef int (*emitter_func) (struct commit *); \n \n-int sort_list_in_merge_order(struct commit_list *list, emitter_func emitter);\n+// functions of this type return non-zero if the commit is \"local\" by some private assessment of\n+// what it is for a commit to be local.\n+typedef int (*local_test_func) (struct commit *); \n+\n+int sort_list_in_merge_order(struct commit_list *list, emitter_func emitter, local_test_func local_test);\n \n #define UNINTERESTING  (1u<<2)\n #define BOUNDARY       (1u<<3)\n #define VISITED        (1u<<4)\n #define DISCONTINUITY  (1u<<5)\n #define DUPCHECK       (1u<<6)\n+#define LOCAL          (1u<<7)\n \n \n #endif\t\t\t\t/* EPOCH_H */\ndiff --git a/rev-list.c b/rev-list.c\n--- a/rev-list.c\n+++ b/rev-list.c\n@@ -11,8 +11,11 @@ static const char rev_list_usage[] =\n \t\t      \"  --max-age=epoch\\n\"\n \t\t      \"  --min-age=epoch\\n\"\n \t\t      \"  --header\\n\"\n+\t\t      \"  --parents\\n\"\n \t\t      \"  --pretty\\n\"\n-\t\t      \"  --merge-order [ --show-breaks ]\";\n+\t\t      \"  --merge-order\\n\"\n+\t\t      \"  --wrt=author@domain\\n\"\n+                      \"  --show-breaks ]\";\n \n static int verbose_header = 0;\n static int show_parents = 0;\n@@ -24,6 +27,7 @@ static int max_count = -1;\n static enum cmit_fmt commit_format = CMIT_FMT_RAW;\n static int merge_order = 0;\n static int show_breaks = 0;\n+static char * local_author = NULL;\n \n static void show_commit(struct commit *commit)\n {\n@@ -147,6 +151,16 @@ static enum cmit_fmt get_commit_format(c\n \tusage(rev_list_usage);\t\n }\t\t\t\n \n+static int is_local_author(struct commit * commit)\n+{\n+\tstatic char author[16384];\n+\tif (copy_author(commit, author, sizeof(author)) > 0) {\n+\t\tif (strstr(author, local_author)) {\n+\t\t\treturn 1;\n+\t\t}\n+\t}\n+\treturn 0;\n+}\n \n int main(int argc, char **argv)\n {\n@@ -192,6 +206,13 @@ int main(int argc, char **argv)\n \t\t}\n \t\tif (!strncmp(arg, \"--show-breaks\", 13)) {\n \t\t\tshow_breaks = 1;\n+                        merge_order = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strncmp(arg, \"--wrt=\", 6)) {\n+\t\t\tlocal_author=xmalloc(strlen(&arg[6])+3);\n+\t\t\tsprintf(local_author, \"<%s>\", &arg[6]);\n+\t\t\tmerge_order = 1;\n \t\t\tcontinue;\n \t\t}\n \n@@ -201,7 +222,7 @@ int main(int argc, char **argv)\n \t\t\targ++;\n \t\t\tlimited = 1;\n \t\t}\n-\t\tif (get_sha1(arg, sha1) || (show_breaks && !merge_order))\n+\t\tif (get_sha1(arg, sha1))\n \t\t\tusage(rev_list_usage);\n \t\tcommit = lookup_commit_reference(sha1);\n \t\tif (!commit || parse_commit(commit) < 0)\n@@ -221,7 +242,7 @@ int main(int argc, char **argv)\n \t\t\t\n \t} else {\n \t\t\n-\t\tif (sort_list_in_merge_order(list, &process_commit)) {\n+\t\tif (sort_list_in_merge_order(list, &process_commit, local_author ? &is_local_author : NULL)) {\n \t\t\t  die(\"merge order sort failed\\n\");\n \t\t}\n \t\t\t\t\t\n"}]}