{"thread":{"id":"875","subject":"[PATCH] Add support for author-oriented git-rev-list switches [rev 6]","startedAt":"2005-06-09T09:01:41Z","lastAt":"2005-06-09T23:10:42Z","messageCount":5,"participants":["Jon Seymour","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"4765","messageId":"20050609090141.21555.qmail@blackcubes.dyndns.org","threadId":"875","inReplyTo":null,"subject":"[PATCH] Add support for author-oriented git-rev-list switches [rev 6]","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-09T09:01:41Z","receivedAt":"2005-06-09T09:01:41Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"\nThis patch is a complete replacement for the previous --wrt \nand --wrt-author patches; it adds support for --wrt-author, \n--prune-at-author and --author switches to git-rev-list.\n\nThese switches perform various sorting and filtering operations that\nhelp any git user reconstruct a linear view of merge history from \nthe point of any given change author.\n\nWhen --wrt-author is specified, --merge-order is implied but \nthe linearisation of non-linear epochs is adjusted so that branches\ncontributed to by the author sort after branches contributed to by\nothers. This has the effect of presenting a linear history of changes as seen\nby the author's own 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 --author=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\nThis has the effect of showing the first 3 of author@domain's changes \noccuring before any of the changes in other branches. This is the \norder in which author@domain perceived change occurring - changes \na0->a3 weren't visible in author@domain's workspace until the merge at b4.\n\nIf --prune-at-author is specified, then git-rev-list behaves as if a \n^argument had been added for each commit authored by the author.\n\nThe --prune-at-author option allows an author to see a brief summary of \nchanges since they last made a contribution to the commit graph. For example:\n\n      git-rev-list --prune-at-author --pretty HEAD \n\nTo configure which author git-rev-list uses when processing the --wrt-author \nand --prune-at-author switches, use the --author=author@domain option. If this \noption is not specified, git-rev-list uses GIT_AUTHOR_EMAIL or a value\nderived from the local user, host and domain names \n(per git-commit-tree's algorithm)\n\nTo support this change, some additional functions were added to commit.c to \nallow the extraction of author from the commit header.\n\nAlso, --show-breaks, like --wrt-author now implies --merge-order rather than \nrequires it.\n\nThis change also updates Documentation/git-rev-list.txt to include \ndocumentation for --wrt-author and other git-rev-list options not currently \ndocumented.\n\nA test case has been included in t/t6001-rev-list-merge-order.sh to \nverify this change works as expected.\n\nUse of --wrt-author implies a small overhead (linear with respect to nodes \nprinted) compared with --merge-order.\n\nThis change extracts real email id formatting functions from commit-tree.c \ninto user.c and user.h.\n\nSigned-off-by: Jon Seymour <jon.seymour@gmail.com>\n\n---\n\nNOTE TO REVIEWERS: please pay special attention to get_real_identity() \nwhich was extracted from commit-tree.c and placed into user.c. It was \nessentially a cut and paste, but since this has the potential to affect the \noperation of git-commit-tree, it would be worth being very careful about \nchecking this change.\n\nAnother thing to review is my use of /dev/urandom and dd in my \nt/t6001-rev-list-merge-order.sh. I am using it so that two \nclosely timed commits look diffrent to git. If /dev/urandom doesn't\nexist I fall back to a slower, but safer technique using only \ndate.\n\n[rev 1]   * original patch\n[rev 2-4] * various cleanups\n[rev 5]   * --merge-order bug fixes already merged with Linus.\n[rev 6]   * remerged with Linus' head (98a96b00b88ee35866cd0b1e94697db76bd5ddf9)\n          * changed name of --exclude-author switch to --prune-at-author\n\t  * reformatted to be more consistent with preferred coding style, namely:\n\t        * aggressive elimination of intra-block blank lines\n                  except immediately after declarations\n                * declarations at top of block\n                * one statement blocks without braces\n                * everything except first line of function declaration \n                  wrapped at <= 80 columns\n          * modified test cases to use /dev/urandom to get some entropy for\n            commit text so that closely spaced commits aren't identical\n          * added struct epoch_methods to gather 3 function pointers now used\n            by merge order logic\n          * added a comment to commit.c to indicate that epoch.c is assuming\n            that parse_commit stacks parents read from the commit header\n            rather than queues them\n\nCould someone else review this patch please and if it, does, please your ok\nto the list? I am more than happy to make any coding style adjustments required.\n\nDiverged from 98a96b00b88ee35866cd0b1e94697db76bd5ddf9 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,65 +9,113 @@ 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 ] \n+[ *--min-age*=timestamp ] [ *--pretty* ] [ *--parents* ] [ *--header* ] \n+[ *--merge-order* ] [ *--show-breaks* ] [ *--wrt-author* ] \n+[ *--prune-at-author* ] [ *--author=author@domain* ]  \n+<head-to-include> <head-to-include> ... \n+^<base-to-prune> \n+^<base-to-prune> ...\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-If *--merge-order* is specified, the commit history is decomposed into a\n-unique sequence of minimal, non-linear epochs and maximal, linear epochs.\n-Non-linear epochs are then linearised by sorting them into merge order, which\n+\n+Lists commit objects in reverse chronological order starting at the commits \n+specified by head-to-include values, taking ancestry relationship into account.  \n+git-rev-list will not print any commits that are reachable by any of the \n+base-to-prune values. \n+\n+If *--max-count* is specified, the number of commits output is \n+limited to the number specified.\n+\n+If *--max-age* is specified, commits older than the date specified \n+(in seconds since Jan 1, 1970) are excluded from the output.\n+\n+If *--min-age* is specified, commits younger than the date specified \n+(in seconds since Jan 1, 1970) are excluded from the output.\n+\n+If *--pretty* is specified, git-rev-list prints a short summary of each \n+commit on stdout. This can be usefully parsed by git-shortlog to produce a \n+short log of changes.\n+\n+If *--parents* is specified, git-rev-list prints a space separated list \n+of parents on the same line as the commit identifier.\n+\n+If *--header* is specified, git-rev-list prints to stdout, on lines after \n+the identifier of each commit, the contents of the commit's header followed by \n+a trailing NUL.\n+\n+If *--merge-order* is specified, the commit history is decomposed into a \n+unique sequence of minimal, non-linear epochs and maximal, linear epochs. \n+Non-linear epochs are then linearised by sorting them into merge order, which \n is described below.\n \n-Maximal, linear epochs correspond to periods of sequential development.\n-Minimal, non-linear epochs correspond to periods of divergent development\n-followed by a converging merge. The theory of epochs is described in more\n-detail at\n+Maximal, linear epochs correspond to periods of sequential development. \n+Minimal, non-linear epochs correspond to periods of divergent development \n+followed by a converging merge. The theory of epochs is described in more \n+detail at \n link:http://blackcubes.dyndns.org/epoch/[http://blackcubes.dyndns.org/epoch/].\n \n-The merge order for a non-linear epoch is defined as a linearisation for which\n-the following invariants are true:\n-\n-    1. if a commit P is reachable from commit N, commit P sorts after commit N\n-       in the linearised list.\n-    2. if Pi and Pj are any two parents of a merge M (with i < j), then any\n-       commit N, such that N is reachable from Pj but not reachable from Pi,\n-       sorts before all commits reachable from Pi.\n-\n-Invariant 1 states that later commits appear before earlier commits they are\n-derived from.\n+The merge order for a non-linear epoch is defined as a linearisation for \n+which the following invariants are true:\n \n-Invariant 2 states that commits unique to \"later\" parents in a merge, appear\n-before all commits from \"earlier\" parents of a merge.\n+    1. if a commit P is reachable from commit N, commit P sorts after \n+       commit N in the linearised list.\n+    2. if Pi and Pj are any two parents of a merge M (with i < j), then \n+       any commit N, such that N is reachable from Pj but not reachable from \n+       Pi, sorts before all commits reachable from Pi.\n+   \n+Invariant 1 states that later commits appear before earlier commits \n+they are derived from.\n+\n+Invariant 2 states that commits unique to \"later\" parents in a merge, \n+appear before all commits from \"earlier\" parents of a merge.\n+\n+If *--show-breaks* is specified, each item of the list is output with a \n+2-character prefix consisting of one of:  (|), (^), (=) followed by a space. \n+ \n+Commits marked with (=) represent the boundaries of minimal, non-linear \n+epochs and correspond either to the start of a period of divergent development \n+or to the end of such a period. \n \n-If *--show-breaks* is specified, each item of the list is output with a\n-2-character prefix consisting of one of: (|), (^), (=) followed by a space.\n-\n-Commits marked with (=) represent the boundaries of minimal, non-linear epochs\n-and correspond either to the start of a period of divergent development or to\n-the end of such a period.\n-\n-Commits marked with (|) are direct parents of commits immediately preceding\n+Commits marked with (|) are direct parents of commits immediately preceding \n the marked commit in the list.\n \n-Commits marked with (^) are not parents of the immediately preceding commit.\n-These \"breaks\" represent necessary discontinuities implied by trying to\n+Commits marked with (^) are not parents of the immediately preceding commit. \n+These \"breaks\" represent necessary discontinuities implied by trying to \n represent an arbtirary DAG in a linear form.\n \n-*--show-breaks* is only valid if *--merge-order* is also specified.\n+If *--wrt-author* is specified, then git-rev-list sorts commits so that \n+contemporaneously developed commits appear to occur after (that is, sort before) \n+any commits authored by the author specified by *--author*. This reflects the \n+order in which that author sees contemporaneously developed commits appear \n+in her own workspace.\n+\n+If *--prune-at-author* is specified, then any commit authored by the \n+author is marked as uninteresting as if it had been specified with ^ on \n+the command line. This option restricts git-rev-list's output to just \n+the changes following any changes contributed by the author.\n+\n+The *--author* option is used to specify the author used by the \n+*--wrt-author* and *--prune-at-author* switches. If an *--author* option is \n+not specified, the author used is derived from GIT_AUTHOR_EMAIL or, ultimately, \n+from the local user, host and domain names as per the logic used by \n+git-commit-tree.\n+\n+Use of *--show-breaks*, *--prune-at-author* or *--wrt-author* \n+implies *--merge-order*.\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*, *--wrt-author* and *--prune-at-author* logic \n+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 \n+the git-list <git@vger.kernel.org>.\n \n GIT\n ---\ndiff --git a/Makefile b/Makefile\n--- a/Makefile\n+++ b/Makefile\n@@ -42,9 +42,9 @@ install: $(PROG) $(SCRIPTS)\n \n LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o \\\n \t tag.o delta.o date.o index.o diff-delta.o patch-delta.o entry.o \\\n-\t epoch.o refs.o\n+\t epoch.o refs.o user.o\n LIB_FILE=libgit.a\n-LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h epoch.h\n+LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h epoch.h user.h\n \n LIB_H += strbuf.h\n LIB_OBJS += strbuf.o\n@@ -140,6 +140,7 @@ diffcore-pickaxe.o : $(LIB_H) diffcore.h\n diffcore-break.o : $(LIB_H) diffcore.h\n diffcore-order.o : $(LIB_H) diffcore.h\n epoch.o: $(LIB_H)\n+user.o: $(LIB_H)\n \n test: all\n \t$(MAKE) -C t/ all\ndiff --git a/commit-tree.c b/commit-tree.c\n--- a/commit-tree.c\n+++ b/commit-tree.c\n@@ -4,8 +4,8 @@\n  * Copyright (C) Linus Torvalds, 2005\n  */\n #include \"cache.h\"\n+#include \"user.h\"\n \n-#include <pwd.h>\n #include <time.h>\n #include <ctype.h>\n \n@@ -100,17 +100,16 @@ static char *commit_tree_usage = \"git-co\n \n int main(int argc, char **argv)\n {\n-\tint i, len;\n+\tint i;\n \tint parents = 0;\n \tunsigned char tree_sha1[20];\n \tunsigned char parent_sha1[MAXPARENT][20];\n \tunsigned char commit_sha1[20];\n \tchar *gecos, *realgecos, *commitgecos;\n-\tchar *email, *commitemail, realemail[1000];\n+\tchar *email, *commitemail, *realemail;\n \tchar date[50], realdate[50];\n \tchar *audate, *cmdate;\n \tchar comment[1000];\n-\tstruct passwd *pw;\n \tchar *buffer;\n \tunsigned int size;\n \n@@ -128,19 +127,7 @@ int main(int argc, char **argv)\n \t}\n \tif (!parents)\n \t\tfprintf(stderr, \"Committing initial tree %s\\n\", argv[1]);\n-\tpw = getpwuid(getuid());\n-\tif (!pw)\n-\t\tdie(\"You don't exist. Go away!\");\n-\trealgecos = pw->pw_gecos;\n-\tlen = strlen(pw->pw_name);\n-\tmemcpy(realemail, pw->pw_name, len);\n-\trealemail[len] = '@';\n-\tgethostname(realemail+len+1, sizeof(realemail)-len-1);\n-\tif (!strchr(realemail+len+1, '.')) {\n-\t\tstrcat(realemail, \".\");\n-\t\tgetdomainname(realemail+strlen(realemail), sizeof(realemail)-strlen(realemail)-1);\n-\t}\n-\n+\tget_real_identity(&realemail, &realgecos);\n \tdatestamp(realdate, sizeof(realdate));\n \tstrcpy(date, realdate);\n \ndiff --git a/commit.c b/commit.c\n--- a/commit.c\n+++ b/commit.c\n@@ -76,6 +76,15 @@ int parse_commit_buffer(struct commit *i\n \t       !get_sha1_hex(bufptr + 7, parent)) {\n \t\tstruct commit *new_parent = lookup_commit(parent);\n \t\tif (new_parent) {\n+\t\t\t/** \n+\t\t\t * The current stacking (as opposed to queueing) \n+\t\t\t * behaviour implied by use of commit_list_insert\n+\t\t\t * is assumed in several places elsewhere in git \n+\t\t\t * - particularly epoch.c. If this ever changes\n+\t\t\t * it will be necessary to carefully re-evaluate\n+\t\t\t * order-sensitive commit list processing loops to \n+\t\t\t * ensure they are still doing the right thing.\n+\t\t\t */\n \t\t\tcommit_list_insert(new_parent, &item->parents);\n \t\t\tadd_ref(&item->object, &new_parent->object);\n \t\t}\n@@ -302,3 +311,56 @@ 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+\twhile (*p != '\\n') {\t\t\n+\t\tchar * q = header;\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/*\n+\t\t\t * if we matched but we haven't seen the \n+\t\t\t * index'th element yet, just decrement \n+\t\t\t * the index then pretend we didn't match\n+\t\t\t */\n+\t\t\tindex--;\n+\t\t\tmatched = 0;\n+\t\t}\n+\t\t\n+\t\tif (!matched) {\t\t\t\n+\t\t\t/* skip to start of next header line */\t\t\t\n+\t\t\tfor (;*p!='\\n';p++)\n+\t\t\t\t;\n+\t\t\tp++;\n+\t\t} else {\t\t\t\n+\t\t\tint count = 0; /* number of characters in value */\n+\t\t\tif (*p == ' ') {\t\t\t\t\n+\t\t\t\tp++;\n+\t\t\t\tcount = 0;\n+\t\t\t\twhile(*p != '\\n') {\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\tp++;\n+\t\t\t\t\tcount++;\n+\t\t\t\t\tlen--;\n+\t\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\treturn (len > 0) ? count+1 : -(count+1);\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,23 @@ 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 \n+ * specified into the buffer supplied and append a trailing NUL.\n+ *\n+ * Returns n<0 if the buffer was too short, where -n is the required length.\n+ * \n+ * Returns 0 if the header doesn't exist.\n+ * \n+ * Returns n>0 where n is the length of the copied zero-terminated value, \n+ * including the terminating zero.\n+ */\n+int copy_commit_header(struct commit * commit, char * header, int index, char * buffer, int len);\n+\n+/*\n+ * Copies the commit's author value into the buffer supplied. \n+ * Return values as per copy_commit_header.\n+ */\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@@ -8,7 +8,6 @@\n  *\n  */\n #include <stdlib.h>\n-\n /* Provides arbitrary precision integers required to accurately represent\n  * fractional mass: */\n #include <openssl/bn.h>\n@@ -23,7 +22,19 @@ struct fraction {\n };\n \n #define HAS_EXACTLY_ONE_PARENT(n) ((n)->parents && !(n)->parents->next)\n+#define ASSERT(x,m,c) if (!(x)) { assertion_failed(__LINE__, __FUNCTION__, m, c); }\n \n+static void assertion_failed(int line, char * function, char * message, struct commit * item)\n+{\n+\tdie(\t\"%s:%d:%s: assertion_failed: %s: commit %s, flags %x\",\n+\t\t__FILE__, \n+\t\tline, \n+\t\tfunction,\n+\t\tmessage,\n+\t    \titem ? sha1_to_hex(item->object.sha1) : \"[]\",\n+\t    \titem ? item->object.flags : 0xFFFFFFFF);\n+}\n+\t\t\t\n static BN_CTX *context = NULL;\n static struct fraction *one = NULL;\n static struct fraction *zero = NULL;\n@@ -58,10 +69,10 @@ static struct fraction *divide(struct fr\n \n \tBN_init(&bn_divisor);\n \tBN_set_word(&bn_divisor, divisor);\n-\n \tBN_copy(&result->numerator, &fraction->numerator);\n-\tBN_mul(&result->denominator, &fraction->denominator, &bn_divisor, get_BN_CTX());\n-\n+\tBN_mul(\t&result->denominator, \n+\t\t&fraction->denominator, \n+\t\t&bn_divisor, get_BN_CTX());\n \tBN_clear(&bn_divisor);\n \treturn result;\n }\n@@ -99,28 +110,44 @@ static struct fraction *copy(struct frac\n \treturn to;\n }\n \n-static struct fraction *add(struct fraction *result, struct fraction *left, struct fraction *right)\n+static struct fraction *inc(struct fraction *left, struct fraction *right)\n {\n \tBIGNUM a, b, gcd;\n \n \tBN_init(&a);\n \tBN_init(&b);\n \tBN_init(&gcd);\n-\n-\tBN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());\n-\tBN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());\n-\tBN_mul(&result->denominator, &left->denominator, &right->denominator, get_BN_CTX());\n-\tBN_add(&result->numerator, &a, &b);\n-\n-\tBN_gcd(&gcd, &result->denominator, &result->numerator, get_BN_CTX());\n-\tBN_div(&result->denominator, NULL, &result->denominator, &gcd, get_BN_CTX());\n-\tBN_div(&result->numerator, NULL, &result->numerator, &gcd, get_BN_CTX());\n-\n+\tBN_mul(\t&a, \n+\t\t&left->numerator, \n+\t\t&right->denominator, \n+\t\tget_BN_CTX());\n+\tBN_mul(\t&b, \n+\t\t&left->denominator, \n+\t\t&right->numerator, \n+\t\tget_BN_CTX());\n+\tBN_mul( &left->denominator, \n+\t\t&left->denominator, \n+\t\t&right->denominator, \n+\t\tget_BN_CTX());\n+\tBN_add(\t&left->numerator, \n+\t\t&a, \n+\t\t&b);\n+\tBN_gcd(\t&gcd, \n+\t\t&left->denominator, \n+\t\t&left->numerator, \n+\t\tget_BN_CTX());\n+\tBN_div(\t&left->denominator, \n+\t\tNULL, &left->denominator, \n+\t\t&gcd, \n+\t\tget_BN_CTX());\n+\tBN_div(\t&left->numerator, \n+\t\tNULL, &left->numerator, \n+\t\t&gcd, \n+\t\tget_BN_CTX());\n \tBN_clear(&a);\n \tBN_clear(&b);\n \tBN_clear(&gcd);\n-\n-\treturn result;\n+\treturn left;\n }\n \n static int compare(struct fraction *left, struct fraction *right)\n@@ -130,15 +157,11 @@ static int compare(struct fraction *left\n \n \tBN_init(&a);\n \tBN_init(&b);\n-\n \tBN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());\n \tBN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());\n-\n \tresult = BN_cmp(&a, &b);\n-\n \tBN_clear(&a);\n \tBN_clear(&b);\n-\n \treturn result;\n }\n \n@@ -150,21 +173,15 @@ struct mass_counter {\n static struct mass_counter *new_mass_counter(struct commit *commit, struct fraction *pending)\n {\n \tstruct mass_counter *mass_counter = xmalloc(sizeof(*mass_counter));\n-\tmemset(mass_counter, 0, sizeof(*mass_counter));\n \n+\tASSERT(!commit->object.util, \"not already initialized\", commit);\n+\n+\tmemset(mass_counter, 0, sizeof(*mass_counter));\n \tinit_fraction(&mass_counter->seen);\n \tinit_fraction(&mass_counter->pending);\n-\n \tcopy(&mass_counter->pending, pending);\n \tcopy(&mass_counter->seen, get_zero());\n-\n-\tif (commit->object.util) {\n-\t\tdie(\"multiple attempts to initialize mass counter for %s\",\n-\t\t    sha1_to_hex(commit->object.sha1));\n-\t}\n-\n \tcommit->object.util = mass_counter;\n-\n \treturn mass_counter;\n }\n \n@@ -218,73 +235,63 @@ static int find_base_for_list(struct com\n \tstruct commit_list *cleaner = NULL;\n \tstruct commit_list *pending = NULL;\n \tstruct fraction injected;\n+\n \tinit_fraction(&injected);\n \t*boundary = NULL;\n-\n-\tfor (; list; list = list->next) {\n+\tfor (; list && !ret; list = list->next) {\n \t\tstruct commit *item = list->item;\n \n-\t\tif (item->object.util) {\n-\t\t\tdie(\"%s:%d:%s: logic error: this should not have happened - commit %s\",\n-\t\t\t    __FILE__, __LINE__, __FUNCTION__,\n-\t\t\t    sha1_to_hex(item->object.sha1));\n-\t\t}\n-\n+\t\tASSERT(!item->object.util, \"no duplicates in list\", item);\n \t\tnew_mass_counter(list->item, get_one());\n-\t\tadd(&injected, &injected, get_one());\n-\n+\t\tinc(&injected, get_one());\n \t\tcommit_list_insert(list->item, &cleaner);\n \t\tcommit_list_insert(list->item, &pending);\n \t}\n-\n \twhile (!*boundary && pending && !ret) {\n \t\tstruct commit *latest = pop_commit(&pending);\n \t\tstruct mass_counter *latest_node = (struct mass_counter *) latest->object.util;\n \t\tint num_parents;\n \n-\t\tif ((ret = parse_commit(latest)))\n+\t\tret = parse_commit(latest);\n+\t\tif (ret)\n \t\t\tcontinue;\n-\t\tadd(&latest_node->seen, &latest_node->seen, &latest_node->pending);\n-\n+\t\tinc(&latest_node->seen, &latest_node->pending);\n \t\tnum_parents = count_parents(latest);\n \t\tif (num_parents) {\n-\t\t\tstruct fraction distribution;\n-\t\t\tstruct commit_list *parents;\n+\t\t\tstruct fraction div;\n+\t\t\tstruct commit_list *parents = latest->parents;\n \n-\t\t\tdivide(init_fraction(&distribution), &latest_node->pending, num_parents);\n-\n-\t\t\tfor (parents = latest->parents; parents; parents = parents->next) {\n-\t\t\t\tstruct commit *parent = parents->item;\n-\t\t\t\tstruct mass_counter *parent_node = (struct mass_counter *) parent->object.util;\n-\n-\t\t\t\tif (!parent_node) {\n-\t\t\t\t\tparent_node = new_mass_counter(parent, &distribution);\n-\t\t\t\t\tinsert_by_date(&pending, parent);\n-\t\t\t\t\tcommit_list_insert(parent, &cleaner);\n-\t\t\t\t} else {\n-\t\t\t\t\tif (!compare(&parent_node->pending, get_zero()))\n-\t\t\t\t\t\tinsert_by_date(&pending, parent);\n-\t\t\t\t\tadd(&parent_node->pending, &parent_node->pending, &distribution);\n-\t\t\t\t}\n+\t\t\tdivide(\tinit_fraction(&div), \n+\t\t\t\t&latest_node->pending, \n+\t\t\t\tnum_parents);\n+\t\t\twhile (parents) {\n+\t\t\t\tstruct mass_counter * pmc;\n+\t\t\t\tstruct commit *pc = parents->item;\n+\t\t\t\t\n+\t\t\t\tpmc = (struct mass_counter *) pc->object.util;\n+\t\t\t\tif (!pmc) {\n+\t\t\t\t\tpmc = new_mass_counter(pc, get_zero());\n+\t\t\t\t\tcommit_list_insert(pc, &cleaner);\n+\t\t\t\t}\t\t\t\t\n+\t\t\t\tif (!compare(&pmc->pending, get_zero()))\n+\t\t\t\t\tinsert_by_date(&pending, pc);\t\t\t\t\t\n+\t\t\t\tinc(&pmc->pending, &div);\n+\t\t\t\tparents = parents->next;\n \t\t\t}\n-\n-\t\t\tclear_fraction(&distribution);\n+\t\t\tclear_fraction(&div);\n \t\t}\n-\n-\t\tif (!compare(&latest_node->seen, &injected))\n+\t\tif (!compare(&latest_node->seen, &injected)) {\n \t\t\t*boundary = latest;\n+\t\t}\t\t\n \t\tcopy(&latest_node->pending, get_zero());\n \t}\n-\n \twhile (cleaner) {\n \t\tstruct commit *next = pop_commit(&cleaner);\n \t\tfree_mass_counter((struct mass_counter *) next->object.util);\n \t\tnext->object.util = NULL;\n \t}\n-\n \tif (pending)\n \t\tfree_commit_list(pending);\n-\n \tclear_fraction(&injected);\n \treturn ret;\n }\n@@ -305,7 +312,6 @@ static int find_base(struct commit *head\n \t}\n \tret = find_base_for_list(pending, boundary);\n \tfree_commit_list(pending);\n-\n \treturn ret;\n }\n \n@@ -319,13 +325,12 @@ static int find_base(struct commit *head\n  */\n static int find_next_epoch_boundary(struct commit *head_of_epoch, struct commit **boundary)\n {\n-\tint ret;\n \tstruct commit *item = head_of_epoch;\n+\tint ret;\n \n \tret = parse_commit(item);\n \tif (ret)\n \t\treturn ret;\n-\n \tif (HAS_EXACTLY_ONE_PARENT(item)) {\n \t\t/*\n \t\t * We are at the start of a maximimal linear epoch.\n@@ -336,7 +341,6 @@ static int find_next_epoch_boundary(stru\n \t\t\tret = parse_commit(item);\n \t\t}\n \t\t*boundary = item;\n-\n \t} else {\n \t\t/*\n \t\t * Otherwise, we are at the start of a minimal, non-linear\n@@ -344,7 +348,6 @@ static int find_next_epoch_boundary(stru\n \t\t */\n \t\tret = find_base(item, boundary);\n \t}\n-\n \treturn ret;\n }\n \n@@ -354,8 +357,10 @@ static int find_next_epoch_boundary(stru\n static int is_parent_of(struct commit *parent, struct commit *child)\n {\n \tstruct commit_list *parents;\n+\n \tfor (parents = child->parents; parents; parents = parents->next) {\n-\t\tif (!memcmp(parent->object.sha1, parents->item->object.sha1,\n+\t\tif (!memcmp(parent->object.sha1, \n+\t\t\t    parents->item->object.sha1,\n \t\t            sizeof(parents->item->object.sha1)))\n \t\t\treturn 1;\n \t}\n@@ -369,11 +374,12 @@ static int is_parent_of(struct commit *p\n  */\n static void push_onto_merge_order_stack(struct commit_list **stack, struct commit *item)\n {\n-\tstruct commit_list *top = *stack;\n-\tif (top && (top->item->object.flags & DISCONTINUITY)) {\n-\t\tif (is_parent_of(top->item, item)) {\n-\t\t\ttop->item->object.flags &= ~DISCONTINUITY;\n-\t\t}\n+        struct commit * top_item = *stack ? (*stack)->item : NULL;\n+\n+\tif (\ttop_item\n+\t\t&& (top_item->object.flags & DISCONTINUITY)\n+\t\t&& is_parent_of(top_item, item)) {\n+\t\ttop_item->object.flags &= ~DISCONTINUITY;\n \t}\n \tcommit_list_insert(item, stack);\n }\n@@ -381,7 +387,7 @@ static void push_onto_merge_order_stack(\n /*\n  * Marks all interesting, visited commits reachable from this commit\n  * as uninteresting. We stop recursing when we reach the epoch boundary,\n- * an unvisited node or a node that has already been marking uninteresting.\n+ * an unvisited node or a node that has already been marked uninteresting.\n  *\n  * This doesn't actually mark all ancestors between the start node and the\n  * epoch boundary uninteresting, but does ensure that they will eventually\n@@ -397,7 +403,6 @@ static void mark_ancestors_uninteresting\n \tstruct commit_list *next;\n \n \tcommit->object.flags |= UNINTERESTING;\n-\n \t/*\n \t * We only need to recurse if\n \t *      we are not on the boundary and\n@@ -416,65 +421,77 @@ static void mark_ancestors_uninteresting\n \n \tif (uninteresting || boundary || !visited)\n \t\treturn;\n-\n \tfor (next = commit->parents; next; next = next->next)\n \t\tmark_ancestors_uninteresting(next->item);\n }\n \n /*\n- * Sorts the nodes of the first epoch of the epoch sequence of the epoch headed at head\n- * into merge order.\n+ * Sorts the nodes of the first epoch of the epoch sequence of the epoch \n+ * headed at head into merge order.\n  */\n-static void sort_first_epoch(struct commit *head, struct commit_list **stack)\n+static void sort_first_epoch(struct commit *head, struct commit_list **stack, struct epoch_methods * methods)\n {\n-\tstruct commit_list *parents;\n-\tstruct commit_list *reversed_parents = NULL;\n+\tstruct commit_list *reversed = NULL;\n \n+\tif (methods->marker) {\n+\t\t(*(methods->marker)) (head);\n+\t}\n \thead->object.flags |= VISITED;\n-\n \t/*\n-\t * parse_commit() builds the parent list in reverse order with respect\n-\t * to the order of the git-commit-tree arguments. So we need to reverse\n-\t * this list to output the oldest (or most \"local\") commits last.\n+\t * reverse them so that \"local\" parents are pushed first\n+\t * and hence print last. Note: this is relying \n+\t * on parse_commit always stacking rather than queueing\n+\t * parents it reads from the commit header. If this\n+\t * assumption ever changes, then this code and\n+\t * also that in sort_list_merge_order.\n \t */\n-\tfor (parents = head->parents; parents; parents = parents->next)\n-\t\tcommit_list_insert(parents->item, &reversed_parents);\n+\tif (!head->object.util) {\n+\t\tstruct commit_list *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+\t\t/*\n+\t\t * make a copy of the parents, but don't destroy them\n+\t\t */\n+\t\tparents = head->parents;\n+\t\twhile (parents) {\n+\t\t\tcommit_list_insert(parents->item, &reversed);\n+\t\t\tparents = parents->next;\n+\t\t}\n+\t} else {\n+\t\tstruct commit_list **p;\n \n-\twhile (reversed_parents) {\n-\t\tstruct commit *parent = pop_commit(&reversed_parents);\n+\t\t/*\n+\t\t * reverse the temporary list, destroying it\n+\t\t * in the process list. \n+\t\t */\n+\t\tp = (struct commit_list **)&head->object.util;\n+\t\twhile (*p)\n+\t\t\tcommit_list_insert(pop_commit(p), &reversed);\n+\t\tASSERT(!head->object.util, \"temporary list cleared\", head);\n+\t}\n+\twhile (reversed) {\n+\t\tstruct commit *parent = pop_commit(&reversed);\n \n \t\tif (head->object.flags & UNINTERESTING) {\n \t\t\t/*\n \t\t\t * Propagates the uninteresting bit to all parents.\n-\t\t\t * if we have already visited this parent, then\n+\t\t\t * If we have already visited this parent, then\n \t\t\t * the uninteresting bit will be propagated to each\n \t\t\t * reachable commit that is still not marked\n-\t\t\t * uninteresting and won't otherwise be reached.\n+\t\t\t * uninteresting and won't otherwise be reached by\n+\t\t\t * this traversal.\n \t\t\t */\n \t\t\tmark_ancestors_uninteresting(parent);\n \t\t}\n-\n \t\tif (!(parent->object.flags & VISITED)) {\n \t\t\tif (parent->object.flags & BOUNDARY) {\n-\t\t\t\tif (*stack) {\n-\t\t\t\t\tdie(\"something else is on the stack - %s\",\n-\t\t\t\t\t    sha1_to_hex((*stack)->item->object.sha1));\n-\t\t\t\t}\n+\t\t\t\tASSERT(!(*stack), \n+\t\t\t\t\t\"empty stack at boundary\", \n+\t\t\t\t\t(*stack)->item);\n \t\t\t\tpush_onto_merge_order_stack(stack, parent);\n \t\t\t\tparent->object.flags |= VISITED;\n-\n \t\t\t} else {\n-\t\t\t\tsort_first_epoch(parent, stack);\n-\t\t\t\tif (reversed_parents) {\n+\t\t\t\tsort_first_epoch(parent, stack, methods);\n+\t\t\t\tif (reversed) {\n \t\t\t\t\t/*\n \t\t\t\t\t * This indicates a possible\n \t\t\t\t\t * discontinuity it may not be be\n@@ -485,23 +502,21 @@ static void sort_first_epoch(struct comm\n \t\t\t\t\t * The next push onto the stack will\n \t\t\t\t\t * resolve the question.\n \t\t\t\t\t */\n-\t\t\t\t\t(*stack)->item->object.flags |= DISCONTINUITY;\n+\t\t\t\t\t(*stack)->item\n+\t\t\t\t\t\t->object.flags |= DISCONTINUITY;\n \t\t\t\t}\n \t\t\t}\n \t\t}\n \t}\n-\n \tpush_onto_merge_order_stack(stack, head);\n }\n \n /*\n  * Emit the contents of the stack.\n- *\n  * The stack is freed and replaced by NULL.\n- *\n  * Sets the return value to STOP if no further output should be generated.\n  */\n-static int emit_stack(struct commit_list **stack, emitter_func emitter)\n+static int emit_stack(struct commit_list **stack, struct epoch_methods * methods)\n {\n \tunsigned int seen = 0;\n \tint action = CONTINUE;\n@@ -510,15 +525,93 @@ static int emit_stack(struct commit_list\n \t\tstruct commit *next = pop_commit(stack);\n \t\tseen |= next->object.flags;\n \t\tif (*stack)\n-\t\t\taction = (*emitter) (next);\n+\t\t\taction = (*(methods->emitter)) (next);\n \t}\n-\n \tif (*stack) {\n \t\tfree_commit_list(*stack);\n \t\t*stack = NULL;\n-\t}\n+\t}\t\n+\tif (seen & UNINTERESTING)\n+\t\t/**\n+\t\t * We stop at the base of the stack, rather than\n+\t\t * when we encounter the first UNINTERESTING flag.\n+\t\t * \n+\t\t * The reason is that there may still be interesting\n+\t\t * stuff on the stack but once we reach the base\n+\t\t * there can be no more interesting stuff by definition\n+\t\t * of what the base of an epoch is - everything reachable\n+\t\t * from the base is also reachable from the UNINTERESTING\n+\t\t * node and hence is uninteresting.\n+\t\t */\t\t \n+\t\taction = STOP;\n+\treturn action;\n+}\n \n-\treturn (action == STOP || (seen & UNINTERESTING)) ? STOP : CONTINUE;\n+/*\n+ * Sort a list of commits in local last order. A commit is \"local\" \n+ * if any of its ancestors (except the base) causes (*local_test)() to \n+ * return a non-zero value.\n+ *\n+ * The sorted list is returned in *sorted. A side effect of this function \n+ * is to set each object.util pointer in each ancestor up until the base \n+ * 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 \n+ * NULL.\n+ * \n+ * The return value contains LOCAL if any of the list is local or had a \n+ * local ancestor.\n+ */\n+static unsigned int sort_list_in_local_last_order(struct commit_list *list, struct commit_list **sorted, struct epoch_methods * methods)\n+{\n+\tstruct commit_list *next;\n+\tstruct commit_list *non_local = NULL;\n+\tstruct commit_list *local = NULL;\n+\tstruct commit_list **p = &local;\n+\tstruct commit_list **q = &non_local;\n+\n+\tif (!list || !methods->local_test) {\n+\t\t*sorted = NULL;\n+\t\treturn 0;\n+\t}\n+\tfor (next = list; next; next = next->next) {\n+\t\tstruct commit *item = next->item;\n+\n+\t\tif (item->object.flags & BOUNDARY || item->object.util) \n+\t\t\t/* \n+\t\t \t * we have already visited this item or we have\n+\t\t\t * reached the boundary.\n+                         */\n+\t\t\tcontinue;\n+\t\tif ((*(methods->local_test)) (item))\n+\t\t\titem->object.flags |= LOCAL;\n+\t\titem->object.flags |=\n+\t\t    sort_list_in_local_last_order(\n+\t\t    \titem->parents, \n+\t\t    \t(struct commit_list **) &item->object.util,\n+\t\t    \tmethods);\n+\t}\n+\t/*\n+         * Create a re-ordered list by copying the locally marked\n+         * items to the end of the new list, but otherwise preserving the\n+         * order.\n+         */\n+\tfor (next = list; next; next = next->next) {\n+\t\tif (next->item->object.flags & LOCAL) \n+\t\t\tp = &commit_list_insert(next->item, p)->next;\n+\t\telse\n+\t\t\tq = &commit_list_insert(next->item, q)->next;\n+\t}\n+\t/*\n+\t * if parse_commit in commit.c ever changes stack behaviour\n+         * to queueing behaviour this needs to change to:\n+         *\n+         *      *p = non_local;\n+         *      *sorted = local;\n+\t */\n+\t*q = local;\n+\t*sorted = non_local;\n+\treturn (local ? LOCAL : 0);\n }\n \n /*\n@@ -528,14 +621,13 @@ static int emit_stack(struct commit_list\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, struct epoch_methods * methods)\n {\n \tstruct commit *next = head_of_epoch;\n \tint ret = 0;\n \tint action = CONTINUE;\n \n \tret = parse_commit(head_of_epoch);\n-\n \twhile (next && next->parents && !ret && (action != STOP)) {\n \t\tstruct commit *base = NULL;\n \n@@ -545,34 +637,36 @@ static int sort_in_merge_order(struct co\n \t\tnext->object.flags |= BOUNDARY;\n \t\tif (base)\n \t\t\tbase->object.flags |= BOUNDARY;\n-\n \t\tif (HAS_EXACTLY_ONE_PARENT(next)) {\n \t\t\twhile (HAS_EXACTLY_ONE_PARENT(next)\n \t\t\t       && (action != STOP)\n \t\t\t       && !ret) {\n-\t\t\t\tif (next->object.flags & UNINTERESTING) {\n+\t\t\t\tif (methods->marker)\n+\t\t\t\t\t(*(methods->marker)) (next);\n+\t\t\t\tif (next->object.flags & UNINTERESTING)\n \t\t\t\t\taction = STOP;\n-\t\t\t\t} else {\n-\t\t\t\t\taction = (*emitter) (next);\n-\t\t\t\t}\n+\t\t\t\telse\n+\t\t\t\t\taction = (*(methods->emitter)) (next);\n \t\t\t\tif (action != STOP) {\n \t\t\t\t\tnext = next->parents->item;\n \t\t\t\t\tret = parse_commit(next);\n \t\t\t\t}\n \t\t\t}\n-\n \t\t} else {\n \t\t\tstruct commit_list *stack = NULL;\n-\t\t\tsort_first_epoch(next, &stack);\n-\t\t\taction = emit_stack(&stack, emitter);\n+\n+\t\t\tsort_list_in_local_last_order(\n+\t\t\t\tnext->parents, \n+\t\t\t\t(struct commit_list **) &next->object.util,\n+\t\t\t\tmethods);\n+\t\t\tsort_first_epoch(next, &stack, methods);\n+\t\t\taction = emit_stack(&stack, methods);\n \t\t\tnext = base;\n \t\t}\n \t}\n-\n \tif (next && (action != STOP) && !ret) {\n-\t\t(*emitter) (next);\n+\t\t(*(methods->emitter))(next);\n \t}\n-\n \treturn ret;\n }\n \n@@ -582,52 +676,65 @@ static int sort_in_merge_order(struct co\n  * in this subgraph using the sort_first_epoch algorithm. Once we have\n  * reached the base 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, struct epoch_methods * methods)\n {\n \tstruct commit_list *stack = NULL;\n+\tstruct commit_list *filtered = NULL;\n+\tstruct commit_list **p = &filtered;\n \tstruct commit *base;\n \tint ret = 0;\n \tint action = CONTINUE;\n-\tstruct commit_list *reversed = NULL;\n \n+        if (!methods) \n+\t\tdie(\"methods argument must not be null\");\n+\tif (!methods->emitter)\n+\t\tdie(\"an emitter methods must be supplied\");\n \tfor (; list; list = list->next) {\n \t\tstruct commit *next = list->item;\n \n \t\tif (!(next->object.flags & UNINTERESTING)) {\n-\t\t\tif (next->object.flags & DUPCHECK) {\n-\t\t\t\tfprintf(stderr, \"%s: duplicate commit %s ignored\\n\",\n-\t\t\t\t\t__FUNCTION__, sha1_to_hex(next->object.sha1));\n-\t\t\t} else {\n+\t\t\tif (!(next->object.flags & DUPCHECK)) {\n+\t\t\t\t/**\n+\t\t\t\t * Duplicates will cause find_base_for_list\n+\t\t\t\t * to die, so we silently remove them \n+\t\t\t\t * here - it isn't actually an error.\n+\t\t\t\t */\n \t\t\t\tnext->object.flags |= DUPCHECK;\n-\t\t\t\tcommit_list_insert(list->item, &reversed);\n+\t\t\t\tp = &commit_list_insert(list->item, p)->next;\n \t\t\t}\n \t\t}\n \t}\n-\n-\tif (!reversed->next) {\n+\tif (!filtered->next) {\n \t\t/*\n \t\t * If there is only one element in the list, we can sort it\n \t\t * using sort_in_merge_order.\n \t\t */\n-\t\tbase = reversed->item;\n+\t\tbase = filtered->item;\n \t} else {\n \t\t/*\n \t\t * Otherwise, we search for the base of the list.\n-\t\t */\n-\t\tret = find_base_for_list(reversed, &base);\n+\t\t */\t\t \n+\t\tstruct commit_list *sorted;\n+\t\tstruct commit_list *reversed = NULL;\n+\n+\t\tret = find_base_for_list(filtered, &base);\n \t\tif (ret)\n \t\t\treturn ret;\n \t\tif (base)\n \t\t\tbase->object.flags |= BOUNDARY;\n-\n+\t\tsort_list_in_local_last_order(filtered, &sorted, methods);\n+\t\tif (!sorted) \n+\t\t\tsorted = filtered;\n+\t\twhile (sorted)\n+\t\t\tcommit_list_insert(pop_commit(&sorted), &reversed);\n \t\twhile (reversed) {\n-\t\t\tsort_first_epoch(pop_commit(&reversed), &stack);\n+\t\t\tsort_first_epoch(pop_commit(&reversed), &stack, methods);\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\n+\t\t\t\t * first push for the next commit may (or may\n \t\t\t\t * not) represent a discontinuity with respect\n-\t\t\t\t * to the parent currently on the top of\n+\t\t\t\t * to the commit currently on the top of\n \t\t\t\t * the stack.\n \t\t\t\t *\n \t\t\t\t * Mark it for checking here, and check it\n@@ -637,13 +744,15 @@ int sort_list_in_merge_order(struct comm\n \t\t\t\tstack->item->object.flags |= DISCONTINUITY;\n \t\t\t}\n \t\t}\n-\n-\t\taction = emit_stack(&stack, emitter);\n+\t\taction = emit_stack(&stack, methods);\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, methods);\n \t}\n-\n \treturn ret;\n }\n+\n+void init_epoch_methods(struct epoch_methods * methods)\n+{\n+\tmemset(methods, 0, sizeof(*methods));\n+}\ndiff --git a/epoch.h b/epoch.h\n--- a/epoch.h\n+++ b/epoch.h\n@@ -1,20 +1,55 @@\n #ifndef EPOCH_H\n #define EPOCH_H\n \n-\n-// return codes for emitter_func\n-#define STOP     0\n-#define CONTINUE 1\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-\n+/**\n+ * Flags used by merge order logic and also by rev-list.c\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+ * Return codes for emitter method. Also used by rev-list.c\n+ */\n+#define STOP     0\n+#define CONTINUE 1\n+#define DO       2\n \n-#endif\t\t\t\t/* EPOCH_H */\n+struct epoch_methods {\n+\t/*\n+\t * Returns 0 if traversal should stop, non-zero if it should continue.\n+\t */\n+\tint (*emitter)(struct commit *);\n+\t/* \n+\t * Returns non-zero if the commit is regarded \"local\", 0 otherwise.\n+\t */\n+\tint (*local_test)(struct commit *);\n+\t/* \n+\t * Implementers may use this method to mark commits uninteresting\n+\t * according to some locally determined criteria. The tree\n+\t * will be pruned at any commit so marked.\n+\t */\n+\tvoid (*marker)(struct commit *);\n+};\n+\n+/**\n+ * Initializes an epoch_methods structure which\n+ * may be customized by the caller by overriding any of the method pointers.\n+ */\n+extern void init_epoch_methods(struct epoch_methods *);\n+\n+/**\n+ * Sorts the list of commits in merge order, using the methods specified\n+ * to customize the tactics of the search.\n+ * \n+ * The prune points should be marked with the UNINTERESTING flags. \n+ * \n+ * Note: this algorithm is dirty in the sense that it leaves traces\n+ * of its execution in the object.flags word of some or all of the commits\n+ * visited.\n+ */\n+extern int sort_list_in_merge_order(struct commit_list *list, struct epoch_methods * methods);\n+#endif\t/* EPOCH_H */\ndiff --git a/rev-list.c b/rev-list.c\n--- a/rev-list.c\n+++ b/rev-list.c\n@@ -1,18 +1,24 @@\n #include \"cache.h\"\n #include \"commit.h\"\n #include \"epoch.h\"\n+#include \"user.h\"\n \n #define SEEN\t\t(1u << 0)\n #define INTERESTING\t(1u << 1)\n \n static const char rev_list_usage[] =\n \t\"usage: git-rev-list [OPTION] commit-id <commit-id>\\n\"\n-\t\t      \"  --max-count=nr\\n\"\n-\t\t      \"  --max-age=epoch\\n\"\n-\t\t      \"  --min-age=epoch\\n\"\n-\t\t      \"  --header\\n\"\n-\t\t      \"  --pretty\\n\"\n-\t\t      \"  --merge-order [ --show-breaks ]\";\n+\t\t\t\"  --max-count=nr\\n\"\n+\t\t\t\"  --max-age=epoch\\n\"\n+\t\t\t\"  --min-age=epoch\\n\"\n+\t\t\t\"  --header\\n\"\n+\t\t\t\"  --parents\\n\"\n+\t\t\t\"  --pretty\\n\"\n+\t\t\t\"  --merge-order\\n\"\n+\t\t\t\"  --wrt-author\\n\"\n+\t\t\t\"  --prune-at-author\\n\"\n+\t\t\t\"  --author=author@domain\\n\"\n+\t\t\t\"  --show-breaks ]\";\n \n static int verbose_header = 0;\n static int show_parents = 0;\n@@ -24,6 +30,9 @@ 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+static int prune_at_author = 0;\n+static int wrt_author = 0;\n \n static void show_commit(struct commit *commit)\n {\n@@ -147,6 +156,23 @@ 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+static void mark_authors_own_uninteresting(struct commit * commit)\n+{\n+        if (is_local_author(commit)) {\n+\t\tcommit->object.flags |= UNINTERESTING;\n+        }\n+}\n \n int main(int argc, char **argv)\n {\n@@ -186,14 +212,26 @@ int main(int argc, char **argv)\n \t\t\tshow_parents = 1;\n \t\t\tcontinue;\n \t\t}\n-\t\tif (!strncmp(arg, \"--merge-order\", 13)) {\n+\t\tif (!strcmp(arg, \"--merge-order\")) {\n \t\t        merge_order = 1;\n \t\t\tcontinue;\n \t\t}\n-\t\tif (!strncmp(arg, \"--show-breaks\", 13)) {\n+\t\tif (!strcmp(arg, \"--show-breaks\")) {\n \t\t\tshow_breaks = 1;\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strncmp(arg, \"--author=\", 9)) {\n+                        local_author=strdup(&arg[9]);\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strcmp(arg, \"--wrt-author\")) {\n+\t\t        wrt_author = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strcmp(arg, \"--prune-at-author\")) {\n+\t\t        prune_at_author = 1;\n+\t\t\tcontinue;\n+\t\t}\n \n \t\tflags = 0;\n \t\tif (*arg == '^') {\n@@ -201,7 +239,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@@ -213,14 +251,38 @@ int main(int argc, char **argv)\n \tif (!list)\n \t\tusage(rev_list_usage);\n \n+        if (!merge_order) \n+        \tmerge_order = wrt_author || prune_at_author || show_breaks;        \t\n+\n \tif (!merge_order) {\t\t\n \t        if (limited)\n \t\t\tlist = limit_list(list);\n \t\tshow_commit_list(list);\n-\t} else {\n-\t\tif (sort_list_in_merge_order(list, &process_commit)) {\n-\t\t\t  die(\"merge order sort failed\\n\");\n-\t\t}\n+\t} else {\t\t\n+\t\tstruct epoch_methods methods;\n+\t\t\n+\t\tinit_epoch_methods(&methods);\n+\t        if ((prune_at_author|wrt_author) && !local_author) {\n+\t\t        local_author = gitenv(\"GIT_AUTHOR_EMAIL\") ? : NULL;                         \n+                        if (!local_author)\n+\t\t\t         get_real_identity(&local_author, NULL);\n+\t\t\telse\n+\t\t\t         local_author = strdup(local_author);\n+\t        }\t\t\n+\t\tif (local_author) {\n+\t\t        /* add delimiters to improve accuracy of match */\n+\t\t        char * tmp=xmalloc(strlen(local_author)+3);\n+\t\t        sprintf(tmp, \"<%s>\", local_author);\n+                        free(local_author);\n+                        local_author = tmp;\n+                }                \n+                methods.emitter = &process_commit;                \n+                if (wrt_author)\n+                \tmethods.local_test = &is_local_author;\n+                if (prune_at_author)\n+                \tmethods.marker = &mark_authors_own_uninteresting;\n+\t\tif (sort_list_in_merge_order(list, &methods))\n+\t      \t\tdie(\"merge order sort failed\\n\");\n \t}\n \n \treturn 0;\ndiff --git a/t/t6001-rev-list-merge-order.sh b/t/t6001-rev-list-merge-order.sh\n--- a/t/t6001-rev-list-merge-order.sh\n+++ b/t/t6001-rev-list-merge-order.sh\n@@ -9,7 +9,33 @@ test_description='Test rev-list --merge-\n \n function do_commit\n {\n-    git-commit-tree \"$@\" </dev/null\n+    (    \t\n+    \t# add some entropy to commits so that the so that\n+    \t# two closely timed commits have different sha1 hashes\n+    \t# fall back to a slower technique if urandom, md5sum or\n+    \t# dd don't exist\n+    \tif [ -c /dev/urandom -a -x \"$(which md5sum)\" -a -x \"$(which dd)\" ] \n+    \tthen\n+    \t\tdd if=/dev/urandom bs=1024 count=1 2>/dev/null | md5sum \n+    \telse\n+    \t\tsleep 1;\n+    \t\tdate\n+    \tfi\n+    ) | git-commit-tree \"$@\" 2>/dev/null\n+}\n+\n+function e_commit\n+{\n+    export GIT_AUTHOR_EMAIL=\"author-e@example.com\"\n+    do_commit \"$@\"\n+    export GIT_AUTHOR_EMAIL=\n+}\n+\n+function f_commit\n+{\n+    export GIT_AUTHOR_EMAIL=\"author-f@example.com\"\n+    do_commit \"$@\"\n+    export GIT_AUTHOR_EMAIL=\n }\n \n function check_adjacency\n@@ -30,9 +56,10 @@ function check_adjacency\n \n function sed_script\n {\n-   for c in root a0 a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 l0 l1 l2 l3 l4 l5\n+   for c in root a0 a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 l0 l1 l2 l3 l4 l5 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10\n+\n    do\n-       echo -n \"s/${!c}/$c/;\"\n+       echo -n \"s/${!c}/$c/g;\"\n    done\n }\n \n@@ -40,17 +67,16 @@ date >path0\n git-update-cache --add path0\n tree=$(git-write-tree)\n root=$(do_commit $tree 2>/dev/null)\n-export GIT_COMMITTER_NAME=foobar  # to guarantee that the commit is different\n l0=$(do_commit $tree -p $root)\n l1=$(do_commit $tree -p $l0)\n l2=$(do_commit $tree -p $l1)\n a0=$(do_commit $tree -p $l2)\n a1=$(do_commit $tree -p $a0)\n-export GIT_COMMITTER_NAME=foobar2 # to guarantee that the commit is different\n b1=$(do_commit $tree -p $a0)\n c1=$(do_commit $tree -p $b1)\n-export GIT_COMMITTER_NAME=foobar3 # to guarantee that the commit is different\n+export GIT_AUTHOR_EMAIL=foobar@example.com\n b2=$(do_commit $tree -p $b1)\n+export GIT_AUTHOR_EMAIL=\n b3=$(do_commit $tree -p $b2)\n c2=$(do_commit $tree -p $c1 -p $b2)\n c3=$(do_commit $tree -p $c2)\n@@ -63,6 +89,32 @@ l4=$(do_commit $tree -p $l3)\n l5=$(do_commit $tree -p $l4)\n echo $l5 > .git/HEAD\n \n+e1=$(e_commit $tree 2>/dev/null)\n+e2=$(e_commit $tree -p $e1)\n+f1=$(f_commit $tree -p $e1)\n+e3=$(e_commit $tree -p $e2)\n+f2=$(f_commit $tree -p $f1)\n+e4=$(e_commit $tree -p $e3 -p $f2)\n+e5=$(e_commit $tree -p $e4)\n+f3=$(f_commit $tree -p $f2)\n+f4=$(f_commit $tree -p $f3)\n+e6=$(e_commit $tree -p $e5 -p $f4)\n+f5=$(f_commit $tree -p $f4)\n+f6=$(f_commit $tree -p $f5 -p $e6)\n+e7=$(e_commit $tree -p $e6)\n+e8=$(e_commit $tree -p $e7)\n+e9=$(e_commit $tree -p $e8)\n+f7=$(f_commit $tree -p $f6)\n+f8=$(f_commit $tree -p $f7)\n+f9=$(f_commit $tree -p $f8)\n+e10=$(e_commit $tree -p $e9 -p $f8)\n+\n+\n+#>   e1 -- e2 -- e3 -- e4 -- e5 -- e6 -- e7 -- e8 -- e9 -- e10\n+#>      \\           /           /     \\                 /\n+#>       - f1 -- f2 -- f3 -- f4 -- f5 -- f6 -- f7 -- f8 -- f9\n+\n+\n git-rev-list --merge-order --show-breaks HEAD | sed \"$(sed_script)\" > actual-merge-order\n cat > expected-merge-order <<EOF\n = l5\n@@ -86,6 +138,15 @@ cat > expected-merge-order <<EOF\n = root\n EOF\n \n+\n+#\n+# cd to t/trash and use \n+#\n+#    git-rev-list ... 2>&1 | sed \"$(cat sed.script)\" \n+#\n+# if you ever want to manually debug the operation of git-rev-list\n+#\n+sed_script > sed.script\n git-rev-list HEAD | check_adjacency | sed \"$(sed_script)\" > actual-default-order\n normal_adjacency_count=$(git-rev-list HEAD | check_adjacency | grep -c \"\\^\" | tr -d ' ')\n merge_order_adjacency_count=$(git-rev-list --merge-order HEAD | check_adjacency | grep -c \"\\^\" | tr -d ' ')\n@@ -172,4 +233,125 @@ test_expect_success 'Testing duplicated \n \n test_expect_success 'Testing exclusion near merge' 'git-rev-list --merge-order $a4 ^$c3 2>/dev/null'\n \n+cat > expected-merge-order-6 <<EOF\n+= l5\n+| l4\n+| l3\n+= a4\n+| c3\n+| c2\n+| c1\n+^ b4\n+| a3\n+| a2\n+| a1\n+^ b3\n+| b2\n+| b1\n+= a0\n+| l2\n+| l1\n+| l0\n+= root\n+EOF\n+\n+git-rev-list --merge-order --show-breaks --wrt-author --author=foobar@example.com HEAD 2>/dev/null | sed \"$(sed_script)\" > actual-merge-order-6\n+test_expect_success 'Testing --wrt-author --author=foobar@example.com' 'diff expected-merge-order-6 actual-merge-order-6'\n+\n+cat > expected-merge-order-7 <<EOF\n+= l5\n+| l4\n+| l3\n+= a4\n+| c3\n+| c2\n+| c1\n+^ b4\n+| a3\n+| a2\n+| a1\n+^ b3\n+EOF\n+\n+git-rev-list --show-breaks --wrt-author --author=foobar@example.com --prune-at-author HEAD | sed \"$(sed_script)\" > actual-merge-order-7\n+test_expect_success 'Testing --prune-at-author' 'diff expected-merge-order-7 actual-merge-order-7'\n+\n+cat > expected-wrt-e <<EOF\n+| f9\n+^ e10\n+| f8\n+| f7\n+| f6\n+| f5\n+^ e9\n+| e8\n+| e7\n+| e6\n+| f4\n+| f3\n+^ e5\n+| e4\n+| f2\n+| f1\n+^ e3\n+| e2\n+= e1\n+EOF\n+\n+git-rev-list --show-breaks --wrt-author --author=author-e@example.com $e10 $f9 | sed \"$(sed_script)\" > actual-wrt-e\n+test_expect_success 'Testing --wrt-author --author=author-e' 'diff expected-wrt-e actual-wrt-e'\n+\n+cat > expected-wrt-f <<EOF\n+| f9\n+^ e10\n+| f8\n+| f7\n+| f6\n+| f5\n+^ e9\n+| e8\n+| e7\n+| e6\n+| f4\n+| f3\n+^ e5\n+| e4\n+| e3\n+| e2\n+^ f2\n+| f1\n+= e1\n+EOF\n+\n+cat > expected-wrt-nobody <<EOF\n+| e10\n+| e9\n+| e8\n+| e7\n+^ f9\n+| f8\n+| f7\n+| f6\n+| e6\n+| e5\n+| e4\n+| e3\n+| e2\n+^ f5\n+| f4\n+| f3\n+| f2\n+| f1\n+= e1\n+EOF\n+\n+git-rev-list --show-breaks --wrt-author --author=author-f@example.com $e10 $f9 | sed \"$(sed_script)\" > actual-wrt-f\n+test_expect_success 'Testing --wrt-author --author=author-f' 'diff expected-wrt-f actual-wrt-f'\n+\n+git-rev-list --show-breaks $f9 $e10 | sed \"$(sed_script)\" > actual-wrt-nobody\n+test_expect_success 'Testing --wrt-author' 'diff expected-wrt-nobody actual-wrt-nobody'\n+\n+#\n+#\n+#\n test_done\ndiff --git a/user.c b/user.c\nnew file mode 100644\n--- /dev/null\n+++ b/user.c\n@@ -0,0 +1,33 @@\n+#include \"cache.h\"\n+#include \"user.h\"\n+#include <string.h>\n+#include <pwd.h>\n+\n+void get_real_identity(char **email, char **gecos)\n+{\n+\tstatic char buffer[1000];\n+\tstruct passwd *pw;\n+\tint len;\n+\n+\tpw = getpwuid(getuid());\n+\tif (!pw)\n+\t\tdie(\"You don't exist. Go away!\");\n+\n+\tlen = strlen(pw->pw_name);\n+\tmemcpy(buffer, pw->pw_name, len);\n+\tbuffer[len] = '@';\n+\tgethostname(buffer + len + 1, sizeof(buffer) - len - 1);\n+\tif (!strchr(buffer + len + 1, '.')) {\n+\t\tstrcat(buffer, \".\");\n+\t\tgetdomainname(buffer + strlen(buffer), \n+\t\t\t\tsizeof(buffer) - strlen(buffer) - 1);\n+\t}\n+\n+\tif (gecos) {\n+\t\t*gecos = strdup(pw->pw_gecos);\n+\t}\n+\n+\tif (email) {\n+\t\t*email = strdup(buffer);\n+\t}\n+}\ndiff --git a/user.h b/user.h\nnew file mode 100644\n--- /dev/null\n+++ b/user.h\n@@ -0,0 +1,8 @@\n+#ifndef USER_H\n+#define USER_H\n+/*\n+ * Allocates two new strings to contain the real email and\n+ * name of the current user.\n+ */\n+extern void get_real_identity(char **email, char **gecos);\n+#endif\n"},{"id":"4770","messageId":"2cfc403205060902373e5c284f@mail.gmail.com","threadId":"875","inReplyTo":"20050609090141.21555.qmail@blackcubes.dyndns.org","subject":"Re: [PATCH] Add support for author-oriented git-rev-list switches [rev 6]","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-09T09:37:01Z","receivedAt":"2005-06-09T09:37:01Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"A minor edit with some more whitespace and brace cleanups is available here.\n\nhttp://blackcubes.dyndns.org/epoch/wrt-patch-rev-7.patch\n\nLinus: once your or someone else ok's the patch, you may pull the\nrevised patch from there.\n\njon.\n"},{"id":"4794","messageId":"2cfc4032050609085341e46242@mail.gmail.com","threadId":"875","inReplyTo":"2cfc403205060902373e5c284f@mail.gmail.com","subject":"Re: [PATCH] Add support for author-oriented git-rev-list switches [rev 8]","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-09T15:53:45Z","receivedAt":"2005-06-09T15:53:45Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"Since no-one had pulled the rev-7 patch to review, I have tweaked and\nsimplified the test cases some more. In particular, I removed the need\nfor /dev/urandom.\n\nhttp://blackcubes.dyndns.org/epoch/wrt-patch-latest.patch\n\nJunio: you might be interested in a new bash function I wrote in\n\n           t/t6001-rev-list-merge-order.sh\n\ncalled: test_output_expect_success\n\nIf you like, I'll generalize it and move it into testlib.sh\n\nLinus: when you are ready, the URI above contains the latest patch.\n\njon.\n"},{"id":"4802","messageId":"7vy89jb74x.fsf@assigned-by-dhcp.cox.net","threadId":"875","inReplyTo":"2cfc4032050609085341e46242@mail.gmail.com","subject":"Re: [PATCH] Add support for author-oriented git-rev-list switches [rev 8]","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-06-09T20:35:42Z","receivedAt":"2005-06-09T20:35:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"JS\" == Jon Seymour <jon.seymour@gmail.com> writes:\n\nJS> test_output_expect_success\nJS> If you like, I'll generalize it and move it into testlib.sh\n\nSounds sensible, and yes please I prefer to have it in\ntestlib.sh, and you would get bonus points if you converted some\n(I do not demand you do all of them ;-)) existing cat/echo users\nwhile you are at it.\n\nExcept for some minor points.\n\nI do not think use of \"local\" to help readability is absolutely\nnecessary in this small function, and if it is a bashism, I\nprefer to see it written in a more portable form.  I was\nthinking about removing bashism from the test scripts, although\nI have not gotten around to actually doing it [*1*, *2*].\n\n[Footnotes]\n\n*1* Auditing all the shell scripts to look for quoting bugs\nwhile eradicating bashism would be another good \"Janitor\"\nsub-project if somebody is interested on the list.\n\nI do not know what happend to other items on the Janitor project\nlist.  Personally I liked the one Sean did to redo the command\nline parameters using argp.\n\n*2* Not that I claim what I have already written is bash free.\nI do not have a handy reference that lists which is bashism and\nwhich is in POSIX.  To stay away from bashism, I just try not to\nuse certain things that I did not use when I was introduced to\nshell programming.  That list includes \"${parameter#word}\",\n\"${!parameter}\", \"function\" and \"local\".\n\n"},{"id":"4812","messageId":"2cfc4032050609161059a0f0c@mail.gmail.com","threadId":"875","inReplyTo":"2cfc4032050609085341e46242@mail.gmail.com","subject":"Re: [PATCH] Add support for author-oriented git-rev-list switches [rev 9]","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-09T23:10:42Z","receivedAt":"2005-06-09T23:10:42Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"[rev 9]   \n\n* oops, missed some whitespace in my commit.c edits - begone,\nwhitespace, begone!\n* slight change to semantics of --prune-at-author - now includes the\nauthor's own commits\nbut prunes the parents of the author's own changes. This helps put the\ncut points into some kind of context when the author has contributions\nin multiple branches.\n\nAs before available from:\nhttp://blackcubes.dyndns.org/epoch/wrt-patch-latest.patch\n\nIf anyone has objections to the changed semantics, let's discuss.\n\njon.\n"}]}