{"thread":{"id":"846","subject":"7fb9de4a830dd8969bc17a219c509a76dd3c9aad","startedAt":"2005-06-06T15:04:22Z","lastAt":"2005-06-06T16:05:23Z","messageCount":4,"participants":["jon@blackcubes.dyndns.org","Jon Seymour","Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"4646","messageId":"20050606153940.20039.qmail@blackcubes.dyndns.org","threadId":"846","inReplyTo":null,"subject":"7fb9de4a830dd8969bc17a219c509a76dd3c9aad","fromName":"","fromEmail":"jon@blackcubes.dyndns.org","sentAt":null,"receivedAt":"2005-06-06T15:04:22Z","isPatch":false,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"[PATCH] Modify git-rev-list to linearise the commit history in merge order.\n\nThis patch linearises the GIT commit history graph into merge order \nwhich is defined by invariants specified in Documentation/git-rev-list.txt.\n\nThe linearisation produced by this patch is superior in an objective sense \nto that produced by the existing git-rev-list implementation in that \nthe linearisation produced is guaranteed to have the minimum number of \ndiscontinuities, where a discontinuity is defined as an adjacent pair of \ncommits in the output list which are not related in a direct child-parent \nrelationship.\n\nWith this patch a graph like this:\n\na4 ---\n| \\   \\\n|  b4 |\n|/ |  |\na3 |  |\n|  |  |\na2 |  |\n|  |  c3\n|  |  |\n|  |  c2\n|  b3 |\n|  | /|\n|  b2 |\n|  |  c1\n|  | /\n|  b1\na1 |\n|  |\na0 |\n| /\nroot\n\nSorts like this:\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\nInstead of this:\n\n= a4\n| c3\n^ b4\n| a3\n^ c2\n^ b3\n^ a2\n^ b2\n^ c1\n^ a1\n^ b1\n^ a0\n= root\n\nA test script, t/t6000-rev-list.sh, includes a test which demonstrates\nthat the linearisation produced by --merge-order has less discontinuities\nthan the linearisation produced by git-rev-list without the --merge-order\nflag specified. To see this, do the following:\n\n\tcd t\n\t./t6000-rev-list.sh\n\tcd trash\n\tcat actual-default-order\n\tcat actual-merge-order\n\t\nThe existing behaviour of git-rev-list is preserved, by default. To obtain \nthe modified behaviour, specify --merge-order or --merge-order --show-breaks \non the command line.\n\nThis version of the patch has been tested on the git repository and also on the linux-2.6\nrepository and has reasonable performance on both - ~50-100% slower than the original algorithm.\n\nThis version of the patch has incorporated a functional equivalent of the Linus' output limiting\nalgorithm into the merge-order algorithm itself. This operates per the notes associated \nwith Linus' commit 337cb3fb8da45f10fe9a0c3cf571600f55ead2ce.\n\nThis version has incorporated Linus' feedback regarding proposed changes to rev-list.c.\n(see: [PATCH] Factor out filtering in rev-list.c)\n\nThis version has improved the way sort_first_epoch marks commits as uninteresting.\n\nFor more details about this change, refer to Documentation/git-rev-list.txt \nand http://blackcubes.dyndns.org/epoch/.\n\nSigned-off-by: Jon Seymour <jon.seymour@gmail.com>\n\nDiverged from d925ffbd064802bc8a6ab0bccf0c43b00a7fe710 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,7 +9,7 @@ git-rev-list - Lists commit objects in r\n \n SYNOPSIS\n --------\n-'git-rev-list' <commit>\n+'git-rev-list' [ *--max-count*=number ] [ *--max-age*=timestamp ] [ *--min-age*=timestamp ] [ *--merge-order* [ *--show-breaks* ] ] <commit>\n \n DESCRIPTION\n -----------\n@@ -17,11 +17,39 @@ Lists commit objects in reverse chronolo\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 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+is described below.\n+\n+Maximal, linear epochs correspond to periods of sequential development. Minimal, non-linear epochs \n+correspond to periods of divergent development followed by a converging merge. The theory of epochs is described\n+in more detail at 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 the following invariants are true:\n+\n+    1. if a commit P is reachable from commit N, commit P sorts after commit N in the linearised list.\n+    2. if Pi and Pj are any two parents of a merge M (with i < j), then any commit N, such that N is reachable from Pj\n+       but not reachable from Pi, sorts before all commits reachable from Pi.\n+   \n+Invariant 1 states that later commits appear before earlier commits they are derived from.\n+\n+Invariant 2 states that commits unique to \"later\" parents in a merge, appear before all commits from \"earlier\" parents of\n+a merge.\n+\n+If *--show-breaks* is specified, each item of the list is output with a 2-character prefix consisting of one of: \n+ (|), (^), (=) followed by a space. \n+Commits marked with (=) represent the boundaries of minimal, non-linear epochs and correspond either to the start of a period of divergent development or to the end of such a period. \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 \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+\n Documentation\n --------------\n Documentation by David Greaves, Junio C Hamano and the git-list <git@vger.kernel.org>.\ndiff --git a/Makefile b/Makefile\n--- a/Makefile\n+++ b/Makefile\n@@ -40,9 +40,9 @@ install: $(PROG) $(SCRIPTS)\n \t$(INSTALL) $(PROG) $(SCRIPTS) $(dest)$(bin)\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 tag.o delta.o date.o index.o diff-delta.o patch-delta.o entry.o epoch.o\n LIB_FILE=libgit.a\n-LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h\n+LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h epoch.h\n \n LIB_H += strbuf.h\n LIB_OBJS += strbuf.o\n@@ -135,6 +135,7 @@ diffcore-pathspec.o : $(LIB_H) diffcore.\n 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 \n test: all\n \t$(MAKE) -C t/ all\ndiff --git a/commit.c b/commit.c\n--- a/commit.c\n+++ b/commit.c\n@@ -130,7 +130,7 @@ void free_commit_list(struct commit_list\n \t}\n }\n \n-static void insert_by_date(struct commit_list **list, struct commit *item)\n+void insert_by_date(struct commit_list **list, struct commit *item)\n {\n \tstruct commit_list **pp = list;\n \tstruct commit_list *p;\n@@ -280,3 +280,25 @@ unsigned long pretty_print_commit(enum c\n \tbuf[offset] = '\\0';\n \treturn offset;\n }\n+\n+struct commit *pop_commit(struct commit_list **stack)\n+{\n+\tstruct commit_list *top = *stack;\n+\tstruct commit *item = top ? top->item : NULL;\n+\n+\tif (top) {\n+\t\t*stack = top->next;\n+\t\tfree(top);\n+\t}\n+\treturn item;\n+}\n+\n+int count_parents(struct commit * commit)\n+{\n+        int count = 0;\n+        struct commit_list * parents = commit->parents;\n+        for (count=0;parents; parents=parents->next,count++)\n+          ;\n+        return count;\n+}\n+\ndiff --git a/commit.h b/commit.h\n--- a/commit.h\n+++ b/commit.h\n@@ -42,6 +42,7 @@ enum cmit_fmt {\n \n extern unsigned long pretty_print_commit(enum cmit_fmt fmt, const char *msg, unsigned long len, char *buf, unsigned long space);\n \n+void insert_by_date(struct commit_list **list, struct commit *item);\n \n /** Removes the first commit from a list sorted by date, and adds all\n  * of its parents.\n@@ -49,4 +50,7 @@ extern unsigned long pretty_print_commit\n struct commit *pop_most_recent_commit(struct commit_list **list, \n \t\t\t\t      unsigned int mark);\n \n+struct commit *pop_commit(struct commit_list **stack);\n+\n+int count_parents(struct commit * commit);\n #endif /* COMMIT_H */\ndiff --git a/epoch.c b/epoch.c\nnew file mode 100644\n--- /dev/null\n+++ b/epoch.c\n@@ -0,0 +1,693 @@\n+/*\n+ * Copyright (c) 2005, Jon Seymour\n+ *\n+ * For more information about epoch theory on which this module is based,\n+ * refer to http://blackcubes.dyndns.org/epoch/. That web page defines\n+ * terms such as \"epoch\" and \"minimal, non-linear epoch\" and provides rationales\n+ * for some of the algorithms used here.\n+ *\n+ */\n+#include <stdlib.h>\n+#include <openssl/bn.h>\t\t// provides arbitrary precision integers\n+\t\t\t\t// required to accurately represent fractional \n+\t\t\t\t//mass\n+\n+#include \"cache.h\"\n+#include \"commit.h\"\n+#include \"epoch.h\"\n+\n+struct fraction {\n+\tBIGNUM numerator;\n+\tBIGNUM denominator;\n+};\n+\n+#define HAS_EXACTLY_ONE_PARENT(n) ((n)->parents && !(n)->parents->next)\n+\n+static BN_CTX *context = NULL;\n+static struct fraction *one = NULL;\n+static struct fraction *zero = NULL;\n+\n+static BN_CTX *get_BN_CTX()\n+{\n+\tif (!context) {\n+\t\tcontext = BN_CTX_new();\n+\t}\n+\treturn context;\n+}\n+\n+static struct fraction *new_zero()\n+{\n+\tstruct fraction *result = xmalloc(sizeof(*result));\n+\tBN_init(&result->numerator);\n+\tBN_init(&result->denominator);\n+\tBN_zero(&result->numerator);\n+\tBN_one(&result->denominator);\n+\treturn result;\n+}\n+\n+static void clear_fraction(struct fraction *fraction)\n+{\n+\tBN_clear(&fraction->numerator);\n+\tBN_clear(&fraction->denominator);\n+}\n+\n+static struct fraction *divide(struct fraction *result, struct fraction *fraction, int divisor)\n+{\n+\tBIGNUM bn_divisor;\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_clear(&bn_divisor);\n+\treturn result;\n+}\n+\n+static struct fraction *init_fraction(struct fraction *fraction)\n+{\n+\tBN_init(&fraction->numerator);\n+\tBN_init(&fraction->denominator);\n+\tBN_zero(&fraction->numerator);\n+\tBN_one(&fraction->denominator);\n+\treturn fraction;\n+}\n+\n+static struct fraction *get_one()\n+{\n+\tif (!one) {\n+\t\tone = new_zero();\n+\t\tBN_one(&one->numerator);\n+\t}\n+\treturn one;\n+}\n+\n+static struct fraction *get_zero()\n+{\n+\tif (!zero) {\n+\t\tzero = new_zero();\n+\t}\n+\treturn zero;\n+}\n+\n+static struct fraction *copy(struct fraction *to, struct fraction *from)\n+{\n+\tBN_copy(&to->numerator, &from->numerator);\n+\tBN_copy(&to->denominator, &from->denominator);\n+\treturn to;\n+}\n+\n+static struct fraction *add(struct fraction *result, 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_clear(&a);\n+\tBN_clear(&b);\n+\tBN_clear(&gcd);\n+\n+\treturn result;\n+}\n+\n+static int compare(struct fraction *left, struct fraction *right)\n+{\n+\tBIGNUM a, b;\n+\n+\tint result;\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+struct mass_counter {\n+\tstruct fraction seen;\n+\tstruct fraction pending;\n+};\n+\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+\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\", sha1_to_hex(commit->object.sha1));\n+\t}\n+\n+\tcommit->object.util = mass_counter;\n+\n+\treturn mass_counter;\n+}\n+\n+static void free_mass_counter(struct mass_counter *counter)\n+{\n+\tclear_fraction(&counter->seen);\n+\tclear_fraction(&counter->pending);\n+\tfree(counter);\n+}\n+\n+//\n+// Finds the base commit of a list of commits.\n+//\n+// One property of the commit being searched for is that every commit reachable \n+// from the base commit is reachable from the commits in the starting list only \n+// via paths that include the base commit.\n+//\n+// This algorithm uses a conservation of mass approach to find the base commit.\n+//\n+// We start by injecting one unit of mass into the graph at each\n+// of the commits in the starting list. Injecting mass into a commit\n+// is achieved by adding to its pending mass counter and, if it is not already\n+// enqueued, enqueuing the commit in a list of pending commits, in latest \n+// commit date first order.\n+//\n+// The algorithm then preceeds to visit each commit in the pending queue.\n+// Upon each visit, the pending mass is added to the mass already seen for that \n+// commit and then divided into N equal portions, where N is the number of \n+// parents of the commit being visited. The divided portions are then injected \n+// into each of the parents.\n+//\n+// The algorithm continues until we discover a commit which has seen all the\n+// mass originally injected or until we run out of things to do. \n+//\n+// If we find a commit that has seen all the original mass, we have found\n+// the common base of all the commits in the starting list. \n+//\n+// The algorithm does _not_ depend on accurate timestamps for correct operation.\n+// However, reasonably sane (e.g. non-random) timestamps are required in order \n+// to prevent an exponential performance characteristic. The occasional \n+// timestamp inaccuracy will not dramatically affect performance but may \n+// result in more nodes being processed than strictly necessary.\n+//\n+// This procedure sets *boundary to the address of the base commit. It returns \n+// non-zero if, and only if, there was a problem parsing one of the \n+// commits discovered during the traversal.\n+//\n+static int find_base_for_list(struct commit_list *list, struct commit **boundary)\n+{\n+\n+\tint ret = 0;\n+\n+\tstruct commit_list *cleaner = NULL;\n+\tstruct commit_list *pending = NULL;\n+\n+\t*boundary = NULL;\n+\n+\tstruct fraction injected;\n+\n+\tinit_fraction(&injected);\n+\n+\tfor (; list; list = list->next) {\n+\n+\t\tstruct commit *item = list->item;\n+\n+\t\tif (item->object.util || (item->object.flags & UNINTERESTING)) {\n+\t\t\tdie(\"%s:%d:%s: logic error: this should not have happened - commit %s\\n\",\n+\t\t\t    __FILE__, __LINE__, __FUNCTION__, sha1_to_hex(item->object.sha1));\n+\t\t}\n+\n+\t\tnew_mass_counter(list->item, get_one());\n+\t\tadd(&injected, &injected, get_one());\n+\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+\n+\t\tstruct commit *latest = pop_commit(&pending);\n+\n+\t\tstruct mass_counter *latest_node = (struct mass_counter *) latest->object.util;\n+\n+\t\tif ((ret = parse_commit(latest)))\n+\t\t\tcontinue;\n+\n+\t\tadd(&latest_node->seen, &latest_node->seen, &latest_node->pending);\n+\n+\t\tint num_parents = count_parents(latest);\n+\n+\t\tif (num_parents) {\n+\n+\t\t\tstruct fraction distribution;\n+\t\t\tstruct commit_list *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+\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+\n+\t\t\t\t\tparent_node = new_mass_counter(parent, &distribution);\n+\n+\t\t\t\t\tinsert_by_date(&pending, parent);\n+\t\t\t\t\tcommit_list_insert(parent, &cleaner);\n+\n+\t\t\t\t} else {\n+\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\t}\n+\t\t\t\t\tadd(&parent_node->pending, &parent_node->pending, &distribution);\n+\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t\tclear_fraction(&distribution);\n+\n+\t\t}\n+\n+\t\tif (!compare(&latest_node->seen, &injected)) {\n+\t\t\t*boundary = latest;\n+\t\t}\n+\n+\t\tcopy(&latest_node->pending, get_zero());\n+\n+\t}\n+\n+\twhile (cleaner) {\n+\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+\n+\t}\n+\n+\tif (pending)\n+\t\tfree_commit_list(pending);\n+\n+\tclear_fraction(&injected);\n+\n+\treturn ret;\n+\n+}\n+\n+\n+//\n+// Finds the base of an minimal, non-linear epoch, headed at head, by\n+// applying the find_base_for_list to a list consisting of the parents\n+//\n+static int find_base(struct commit *head, struct commit **boundary)\n+{\n+\tint ret = 0;\n+\tstruct commit_list *pending = NULL;\n+\tstruct commit_list *next;\n+\n+\tcommit_list_insert(head, &pending);\n+\tfor (next = head->parents; next; next = next->next) {\n+\t\tcommit_list_insert(next->item, &pending);\n+\t}\n+\tret = find_base_for_list(pending, boundary);\n+\tfree_commit_list(pending);\n+\n+\treturn ret;\n+}\n+\n+//\n+// This procedure traverses to the boundary of the first epoch in the epoch\n+// sequence of the epoch headed at head_of_epoch. This is either the end of\n+// the maximal linear epoch or the base of a minimal non-linear epoch.\n+//\n+// The queue of pending nodes is sorted in reverse date order and each node\n+// is currently in the queue at most once.\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+\n+\tret = parse_commit(item);\n+\tif (ret)\n+\t\treturn ret;\n+\n+\tif (HAS_EXACTLY_ONE_PARENT(item)) {\n+\n+\t\t// we are at the start of a maximimal linear epoch .. traverse to the end\n+\n+\t\t// traverse to the end of a maximal linear epoch\n+\t\twhile (HAS_EXACTLY_ONE_PARENT(item) && !ret) {\n+\t\t\titem = item->parents->item;\n+\t\t\tret = parse_commit(item);\n+\t\t}\n+\t\t*boundary = item;\n+\n+\t} else {\n+\n+\t\t// otherwise, we are at the start of a minimal, non-linear\n+\t\t// epoch - find the common base of all parents.\n+\n+\t\tret = find_base(item, boundary);\n+\n+\t}\n+\n+\treturn ret;\n+}\n+\n+//\n+// Returns non-zero if parent is known to be a parent of child.\n+//\n+static int is_parent_of(struct commit *parent, struct commit *child)\n+{\n+\tstruct commit_list *parents;\n+\tfor (parents = child->parents; parents; parents = parents->next) {\n+\t\tif (!memcmp(parent->object.sha1, parents->item->object.sha1, sizeof(parents->item->object.sha1)))\n+\t\t\treturn 1;\n+\t}\n+\treturn 0;\n+}\n+\n+//\n+// Pushes an item onto the merge order stack. If the top of the stack is\n+// marked as being a possible \"break\", we check to see whether it actually\n+// is a break.\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+\t}\n+\tcommit_list_insert(item, stack);\n+}\n+\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+// This doesn't actually mark all ancestors between the start node and the\n+// epoch boundary uninteresting, but does ensure that they will \n+// eventually be marked uninteresting when the main sort_first_epoch \n+// traversal eventually reaches them. \n+//\n+static void mark_ancestors_uninteresting(struct commit *commit)\n+{\n+\tunsigned int flags = commit->object.flags;\n+\tint visited = flags & VISITED;\n+\tint boundary = flags & BOUNDARY;\n+\tint uninteresting = flags & UNINTERESTING;\n+\n+\tif (uninteresting || boundary || !visited) {\n+\t\tcommit->object.flags |= UNINTERESTING;\n+\t\treturn;\n+\n+\t\t// we only need to recurse if\n+\t\t//      we are not on the boundary, and,\n+\t\t//      we have not already been marked uninteresting, and,\n+\t\t//      we have already been visited.\n+\n+\t\t//\n+\t\t// the main sort_first_epoch traverse will \n+\t\t// mark unreachable all uninteresting, unvisited parents \n+\t\t// as they are visited so there is no need to duplicate\n+\t\t// that traversal here.\n+\t\t//\n+\t\t// similarly, if we are already marked uninteresting\n+\t\t// then either all ancestors have already been marked\n+\t\t// uninteresting or will be once the sort_first_epoch\n+\t\t// traverse reaches them.\n+\t\t//\n+\t}\n+\n+\tstruct commit_list *next;\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+//\n+static void sort_first_epoch(struct commit *head, struct commit_list **stack)\n+{\n+\tstruct commit_list *parents;\n+\tstruct commit_list *reversed_parents = NULL;\n+\n+\thead->object.flags |= VISITED;\n+\n+\t//\n+\t// parse_commit builds the parent list in reverse order with respect to the order of\n+\t// the git-commit-tree arguments.\n+\t//\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+\n+\twhile (reversed_parents) {\n+\n+\t\tstruct commit *parent = pop_commit(&reversed_parents);\n+\n+\t\tif (head->object.flags & UNINTERESTING) {\n+\t\t\t// propagates the uninteresting bit to\n+\t\t\t// all parents. if we have already visited\n+\t\t\t// this parent, then the uninteresting bit\n+\t\t\t// will be propagated to each reachable \n+\t\t\t// commit that is still not marked uninteresting\n+\t\t\t// and won't otherwise be reached.\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+\n+\t\t\t\tif (*stack) {\n+\t\t\t\t\tdie(\"something else is on the stack - %s\\n\", sha1_to_hex((*stack)->item->object.sha1));\n+\t\t\t\t}\n+\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+\n+\t\t\t\tsort_first_epoch(parent, stack);\n+\n+\t\t\t\tif (reversed_parents) {\n+\t\t\t\t\t//\n+\t\t\t\t\t// this indicates a possible discontinuity\n+\t\t\t\t\t// it may not be be actual discontinuity if\n+\t\t\t\t\t// the head of parent N happens to be the tail\n+\t\t\t\t\t// of parent N+1\n+\t\t\t\t\t//\n+\t\t\t\t\t// the next push onto the stack will resolve the \n+\t\t\t\t\t// question\n+\t\t\t\t\t//\n+\t\t\t\t\t(*stack)->item->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+{\n+\tunsigned int seen = 0;\n+\tint action = CONTINUE;\n+\n+\twhile (*stack && (action != STOP)) {\n+\n+\t\tstruct commit *next = pop_commit(stack);\n+\n+\t\tseen |= next->object.flags;\n+\n+\t\tif (*stack) {\n+\t\t\taction = (*emitter) (next);\n+\t\t}\n+\t}\n+\n+\tif (*stack) {\n+\t\tfree_commit_list(*stack);\n+\t\t*stack = NULL;\n+\t}\n+\n+\treturn (action == STOP || (seen & UNINTERESTING)) ? STOP : CONTINUE;\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+{\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+\n+\t\tstruct commit *base = NULL;\n+\n+\t\tif ((ret = find_next_epoch_boundary(next, &base)))\n+\t\t\treturn ret;\n+\n+\t\tnext->object.flags |= BOUNDARY;\n+\t\tif (base) {\n+\t\t\tbase->object.flags |= BOUNDARY;\n+\t\t}\n+\n+\t\tif (HAS_EXACTLY_ONE_PARENT(next)) {\n+\n+\t\t\twhile (HAS_EXACTLY_ONE_PARENT(next)\n+\t\t\t       && (action != STOP)\n+\t\t\t       && !ret) {\n+\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+\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+\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+\t\t\tnext = base;\n+\n+\t\t}\n+\n+\t}\n+\n+\tif (next && (action != STOP) && !ret) {\n+\t\t(*emitter) (next);\n+\t}\n+\n+\treturn ret;\n+}\n+\n+//\n+// Sorts the nodes reachable from a starting list in merge order, we \n+// first find the base for the starting list and then sort all nodes in this \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+{\n+\tstruct commit_list *stack = NULL;\n+\tstruct commit *base;\n+\n+\tint ret = 0;\n+\tint action = CONTINUE;\n+\n+\tstruct commit_list *reversed = NULL;\n+\n+\tfor (; list; list = list->next) {\n+\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\", __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}\n+\t\t}\n+\t}\n+\n+\tif (!reversed->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+\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\t\treturn ret;\n+\n+\t\tif (base) {\n+\t\t\tbase->object.flags |= BOUNDARY;\n+\t\t}\n+\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// 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//\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+\t\t\t\t// more details.\n+\t\t\t\t//\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}\n+\n+\tif (base && (action != STOP)) {\n+\t\tret = sort_in_merge_order(base, emitter);\n+\t}\n+\n+\treturn ret;\n+}\ndiff --git a/epoch.h b/epoch.h\nnew file mode 100644\n--- /dev/null\n+++ b/epoch.h\n@@ -0,0 +1,20 @@\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+#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+\n+\n+#endif\t\t\t\t/* EPOCH_H */\ndiff --git a/object.h b/object.h\n--- a/object.h\n+++ b/object.h\n@@ -15,6 +15,7 @@ struct object {\n \tconst char *type;\n \tstruct object_list *refs;\n \tstruct object_list *attached_deltas;\n+\tvoid *util;\n };\n \n extern int nr_objs;\ndiff --git a/rev-list.c b/rev-list.c\n--- a/rev-list.c\n+++ b/rev-list.c\n@@ -1,9 +1,9 @@\n #include \"cache.h\"\n #include \"commit.h\"\n+#include \"epoch.h\"\n \n #define SEEN\t\t(1u << 0)\n #define INTERESTING\t(1u << 1)\n-#define UNINTERESTING\t(1u << 2)\n \n static const char rev_list_usage[] =\n \t\"usage: git-rev-list [OPTION] commit-id <commit-id>\\n\"\n@@ -11,7 +11,8 @@ 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      \"  --pretty\";\n+\t\t      \"  --pretty\\n\"\n+\t\t      \"  --merge-order [ --show-breaks ]\";\n \n static int verbose_header = 0;\n static int show_parents = 0;\n@@ -21,9 +22,19 @@ static unsigned long max_age = -1;\n static unsigned long min_age = -1;\n 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 \n static void show_commit(struct commit *commit)\n {\n+\tif (show_breaks) {\n+\t\tprefix = \"| \";\n+\t\tif (commit->object.flags & DISCONTINUITY) {\n+\t\t\tprefix = \"^ \";     \n+\t\t} else if (commit->object.flags & BOUNDARY) {\n+\t\t\tprefix = \"= \";\n+\t\t} \n+        }        \t\t\n \tprintf(\"%s%s\", prefix, sha1_to_hex(commit->object.sha1));\n \tif (show_parents) {\n \t\tstruct commit_list *parents = commit->parents;\n@@ -37,7 +48,38 @@ static void show_commit(struct commit *c\n \t\tstatic char pretty_header[16384];\n \t\tpretty_print_commit(commit_format, commit->buffer, ~0, pretty_header, sizeof(pretty_header));\n \t\tprintf(\"%s%c\", pretty_header, hdr_termination);\n+\t}\t\n+}\n+\n+static int filter_commit(struct commit * commit)\n+{\n+\tif (commit->object.flags & UNINTERESTING)\n+\t\treturn CONTINUE;\n+\tif (min_age != -1 && (commit->date > min_age))\n+\t\treturn CONTINUE;\n+\tif (max_age != -1 && (commit->date < max_age))\n+\t\treturn STOP;\n+\tif (max_count != -1 && !max_count--)\n+\t\treturn STOP;\n+\n+\treturn DO;\n+}\n+\n+static int process_commit(struct commit * commit)\n+{\n+\tint action=filter_commit(commit);\n+\n+\tif (action == STOP) {\n+\t\treturn STOP;\n+\t}\n+\n+\tif (action == CONTINUE) {\n+\t\treturn CONTINUE;\n \t}\n+\n+\tshow_commit(commit);\n+\n+\treturn CONTINUE;\n }\n \n static void show_commit_list(struct commit_list *list)\n@@ -45,15 +87,8 @@ static void show_commit_list(struct comm\n \twhile (list) {\n \t\tstruct commit *commit = pop_most_recent_commit(&list, SEEN);\n \n-\t\tif (commit->object.flags & UNINTERESTING)\n-\t\t\tcontinue;\n-\t\tif (min_age != -1 && (commit->date > min_age))\n-\t\t\tcontinue;\n-\t\tif (max_age != -1 && (commit->date < max_age))\n+\t\tif (process_commit(commit) == STOP)\n \t\t\tbreak;\n-\t\tif (max_count != -1 && !max_count--)\n-\t\t\tbreak;\n-\t\tshow_commit(commit);\n \t}\n }\n \n@@ -110,6 +145,8 @@ static enum cmit_fmt get_commit_format(c\n \tif (!strcmp(arg, \"=short\"))\n \t\treturn CMIT_FMT_SHORT;\n \tusage(rev_list_usage);\t\n+\n+\treturn CMIT_FMT_DEFAULT;\n }\t\t\t\n \n \n@@ -151,6 +188,14 @@ 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\t        merge_order = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strncmp(arg, \"--show-breaks\", 13)) {\n+\t\t\tshow_breaks = 1;\n+\t\t\tcontinue;\n+\t\t}\n \n \t\tflags = 0;\n \t\tif (*arg == '^') {\n@@ -158,7 +203,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))\n+\t\tif (get_sha1(arg, sha1) || (show_breaks && !merge_order))\n \t\t\tusage(rev_list_usage);\n \t\tcommit = lookup_commit_reference(sha1);\n \t\tif (!commit || parse_commit(commit) < 0)\n@@ -170,9 +215,19 @@ int main(int argc, char **argv)\n \tif (!list)\n \t\tusage(rev_list_usage);\n \n-\tif (limited)\n-\t\tlist = limit_list(list);\n+\tif (!merge_order) {\t\t\n+\t\n+\t        if (limited) \n+\t\t\tlist = limit_list(list);\n+\t\tshow_commit_list(list);\n+\t\t\t\n+\t} else {\n+\t\t\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\t\t\t\t\n+\t}\n \n-\tshow_commit_list(list);\n \treturn 0;\n }\n"},{"id":"4647","messageId":"2cfc4032050606084460ff5ce2@mail.gmail.com","threadId":"846","inReplyTo":"20050606153940.20039.qmail@blackcubes.dyndns.org","subject":"Re: 7fb9de4a830dd8969bc17a219c509a76dd3c9aad [ or: the --merge-order patch ]","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-06T15:44:41Z","receivedAt":"2005-06-06T15:44:41Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"Sorry about the Subject: - my patch submission script is obviously a\nlittle buggy.\n\nAnyway, the referenced e-mail contains the latest --merge-order patch\nwhich is synced with Linus' head and incorporates my earlier\nrev-list.c patch.\n\njon.\n"},{"id":"4648","messageId":"Pine.LNX.4.58.0506060858140.1876@ppc970.osdl.org","threadId":"846","inReplyTo":"20050606153940.20039.qmail@blackcubes.dyndns.org","subject":"Re: 7fb9de4a830dd8969bc17a219c509a76dd3c9aad","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-06T16:01:22Z","receivedAt":"2005-06-06T16:01:22Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 6 Jun 2005 jon@blackcubes.dyndns.org wrote:\n>\n> [PATCH] Modify git-rev-list to linearise the commit history in merge order.\n\nMuch nicer. Will apply after testing, however, not this part:\n\n> @@ -110,6 +145,8 @@ static enum cmit_fmt get_commit_format(c\n>  \tif (!strcmp(arg, \"=short\"))\n>  \t\treturn CMIT_FMT_SHORT;\n>  \tusage(rev_list_usage);\t\n> +\n> +\treturn CMIT_FMT_DEFAULT;\n>  }\t\t\t\n>  \n>  \n\nIf you're bothered by a compiler warning (that I don't see, wonder why?),\nplease mark usage() and die() with \"__attribute__ ((__noreturn__))\". Make\nit depend on GCC, ie\n\n\t#ifdef __GCC__\n\t#define NO_RETURN __attribute__((__noreturn__))\n\t#else\n\t#define NO_RETURN\n\t#endif\n\nand then do\n\n\textern void die(const char *, ...) NO_RETURN;\n\nor something like that.\n\nAnyway, that's indepdendent of this patch, but just fyi.\n\n\t\tLinus\n"},{"id":"4754","messageId":"2cfc4032050606090514981174@mail.gmail.com","threadId":"846","inReplyTo":"Pine.LNX.4.58.0506060858140.1876@ppc970.osdl.org","subject":"Re: 7fb9de4a830dd8969bc17a219c509a76dd3c9aad","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-06T16:05:23Z","receivedAt":"2005-06-06T16:05:23Z","isPatch":false,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"On 6/7/05, Linus Torvalds <torvalds@osdl.org> wrote:\n> \n> \n> On Mon, 6 Jun 2005 jon@blackcubes.dyndns.org wrote:\n> >\n> > [PATCH] Modify git-rev-list to linearise the commit history in merge order.\n> \n> Much nicer. Will apply after testing, however, not this part:\n> \n> > @@ -110,6 +145,8 @@ static enum cmit_fmt get_commit_format(c\n> >       if (!strcmp(arg, \"=short\"))\n> >               return CMIT_FMT_SHORT;\n> >       usage(rev_list_usage);\n> > +\n> > +     return CMIT_FMT_DEFAULT;\n> >  }\n> >\n> >\n> \n> If you're bothered by a compiler warning (that I don't see, wonder why?),\n> please mark usage() and die() with \"__attribute__ ((__noreturn__))\". Make\n> it depend on GCC, ie\n> \n>         #ifdef __GCC__\n>         #define NO_RETURN __attribute__((__noreturn__))\n>         #else\n>         #define NO_RETURN\n>         #endif\n> \n> and then do\n> \n>         extern void die(const char *, ...) NO_RETURN;\n> \n> or something like that.\n> \n> Anyway, that's indepdendent of this patch, but just fyi.\n> \n>                 Linus\n> \n\nHere's my gcc version string:\n\n          gcc (GCC) 3.3.3 20040412 (Red Hat Linux 3.3.3-7)\n\nShall I resend you the patch with that taken out?\n\njon.\n-- \nhomepage: http://www.zeta.org.au/~jon/\nblog: http://orwelliantremors.blogspot.com/\n"}]}