{"thread":{"id":"839","subject":"[PATCH] Modify git-rev-list ... in merge order [ repost with bug fixes ]","startedAt":"2005-06-05T13:25:16Z","lastAt":"2005-06-06T01:43:44Z","messageCount":4,"participants":["jon@blackcubes.dyndns.org","Linus Torvalds","Jon Seymour"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"4572","messageId":"20050605134733.3123.qmail@blackcubes.dyndns.org","threadId":"839","inReplyTo":null,"subject":"[PATCH] Modify git-rev-list ... in merge order [ repost with bug fixes ]","fromName":"","fromEmail":"jon@blackcubes.dyndns.org","sentAt":null,"receivedAt":"2005-06-05T13:25:16Z","isPatch":true,"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 [ note: some bugs in my patch's \nsupport of this functionality have now been fixed ]\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 337cb3fb8da45f10fe9a0c3cf571600f55ead2ce 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\n+\t tag.o delta.o date.o index.o diff-delta.o patch-delta.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@@ -134,6 +134,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@@ -129,7 +129,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@@ -254,3 +254,25 @@ unsigned long pretty_print_commit(const \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@@ -32,6 +32,8 @@ void free_commit_list(struct commit_list\n \n void sort_by_date(struct commit_list **list);\n \n+void insert_by_date(struct commit_list **list, struct commit *item);\n+\n extern unsigned long pretty_print_commit(const char *msg, unsigned long len, char *buf, unsigned long space);\n \n \n@@ -41,4 +43,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,640 @@\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 required to accurately represent fractional mass\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 from the base commit is reachable\n+// from the commits in the starting list only 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 commit date\n+// 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 commit and\n+// then divided into N equal portions, where N is the number of parents\n+// of the commit being visited. The divided portions are then injected into each of\n+// 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 to prevent an exponential\n+// performance characteristic. The occasional timestamp inaccuracy will not dramatically\n+// affect performance but may result in more nodes being processed than strictly necessary.\n+//\n+// This procedure sets *boundary to the address of the base commit. It returns non-zero if, and only if,\n+// there was a problem parsing one of the 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+\t\n+\t\tif (list->item->object.util) {\n+\t\t\tfprintf(stderr, \n+\t\t\t\t\"%s:%d:duplicate commit %s discarded.\\n\", \n+\t\t\t\t__FILE__, \n+\t\t\t\t__LINE__, \n+\t\t\t\tsha1_to_hex(list->item->object.sha1));\n+\t\t\tcontinue;\n+\t\t}\n+\t\n+\t\tif (!(list->item->object.flags & UNINTERESTING)) {\n+\t\t\n+\t\t\tnew_mass_counter(list->item, get_one());\t\t\t\n+\t\t\tadd(&injected, &injected, get_one());\n+\t\t\t\n+\t\t\tcommit_list_insert(list->item, &cleaner);\n+\t\t\tcommit_list_insert(list->item, &pending);\n+\t\t}\n+\t\t\n+\t}\n+\n+\twhile (!*boundary && pending && !ret) {\n+\n+\t\tstruct commit *latest = pop_commit(&pending);\n+\t\t\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+\t\t\t\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+\t\t\t\t\n+\t\t\t\tif (!parent_node) {\n+\t\t\t\t\n+\t\t\t\t\tparent_node = new_mass_counter(parent, &distribution);\n+\t\t\t\t\t\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\t\n+\t\t\t\t} else {\n+\t\t\t\t\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+\t\t\t\t\t\n+\t\t\t\t}\n+\t\t\t}\n+\t\t\t\n+\t\t\tclear_fraction(&distribution);\n+\t\t\t\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+\t\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\t\n+\t}\n+\n+\tif (pending)\n+\t\tfree_commit_list(pending);\n+\t\t\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 head.\n+//\n+static int find_base(struct commit *head, struct commit **boundary)\n+{\n+\tint ret = 0;\n+\tstruct commit_list *pending = NULL;\n+        struct commit_list *next;\n+\n+\tcommit_list_insert(head, &pending);\n+\tfor (next = head->parents; next; next = next->next) {\n+\t          commit_list_insert(next->item, &pending);\n+        }\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+// 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\tparent->object.flags |= UNINTERESTING;\n+\t\t}\n+\n+\t\tif (!(parent->object.flags & VISITED)) {\n+\t\t\tif (parent->object.flags & BOUNDARY) {\n+\t\t\t\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+\t\t\t\t\n+\t\t\t\tpush_onto_merge_order_stack(stack, parent);\n+\t\t\t\tparent->object.flags |= VISITED;\n+\t\t\t\t\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 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+// Set a non-zero value if we have seen an uninteresting element while\n+// writing out the stack.\n+//\n+static int emit_stack(struct commit_list ** stack, emitter_func emitter)\n+{\n+\tunsigned int uninteresting = 0;\n+\tunsigned int seen = 0;\n+\tint stop = 0;\n+\n+\twhile (*stack && !stop) {\n+\n+ \t        struct commit * next = pop_commit(stack);\n+\n+\t\tif (next->object.flags & DISCONTINUITY) {\n+\t\t\t// reset the uninteresting flag\n+\t\t\tuninteresting = (next->object.flags & UNINTERESTING);\n+\t\t} else {\n+\t\t\t// inherit the uninteresting flag from parent that was on the stack\n+\t\t\tuninteresting |= (next->object.flags & UNINTERESTING);\n+\t\t}\n+\t\t\n+\t\tnext->object.flags |= uninteresting;\t\t\n+\t\tseen |= next->object.flags;\n+\n+\t\tif (*stack) {\n+\t\t\tstop = (*emitter) (next);\n+\t\t}\n+\t}\n+\t\n+\tif (*stack) {\n+\t\tfree_commit_list(*stack);\n+\t\t*stack = NULL;\n+\t}\n+\t\n+\treturn stop || (seen & UNINTERESTING);\n+}\t\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 stop = 0;\n+\n+\tret = parse_commit(head_of_epoch);\n+\n+\twhile (next && next->parents && !ret && !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        base->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) && !stop && !ret) {\n+\t\t\t\n+\t\t\t\tstop = (next->object.flags & UNINTERESTING) || (*emitter) (next);\n+\t\t\t\tnext = next->parents->item;\n+\t\t\t\tret = parse_commit(next);\t\t\t\t\n+\t\t\t\t\n+\t\t\t}\n+\t\t\t\n+\t\t} else {\n+\n+\t\t\tstruct commit_list *stack = NULL;\t\t\t\t\t\t\n+\t\t\tsort_first_epoch(next, &stack);\t\t\t\t\t\t\n+\t\t\tstop = emit_stack(&stack, emitter);\n+                        next = base;\n+\t\t}\n+\n+\t}\n+\n+\tif (next && !stop) {\n+\t\tstop = (*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 subgraph\n+// 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 stop = 0;\n+\n+\tstruct commit_list *reversed = NULL;\n+\n+\tfor (; list; list = list->next) {\n+\t        struct commit * next = list->item;\n+ \t        if (!(next->object.flags & UNINTERESTING)) {\n+\t\t        if (next->object.flags & DUPCHECK) { \n+\t\t\t        fprintf(stderr, \"%s: duplicate commit %s ignored\\n\", __FUNCTION__, sha1_to_hex(next->object.sha1));\n+                        } else {\n+\t\t\t        next->object.flags |= DUPCHECK;\n+\t\t                commit_list_insert(list->item, &reversed);\n+                        }\n+                }\n+        }\n+\n+\tif (!reversed->next) {\n+\t\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+\t\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        base->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 parents 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        stack->item->object.flags |= DISCONTINUITY;\n+\t\t\t}\n+\t\t}\n+\t\t\n+\t\tstop = emit_stack(&stack, emitter);\n+\t}\n+\n+\tif (!stop && base) {\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,14 @@\n+#ifndef EPOCH_H\n+#define EPOCH_H\n+\n+\n+typedef int (*emitter_func) (struct commit *); \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+#endif\t\t\t\t/* EPOCH_H */\ndiff --git a/git-resolve-script b/git-resolve-script\nold mode 100644\nnew mode 100755\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,27 +22,49 @@ static const char *prefix = \"\";\n static unsigned long max_age = -1;\n static unsigned long min_age = -1;\n static int max_count = -1;\n+static int merge_order = 0;\n+static int show_breaks = 0;\n \n-static void show_commit(struct commit *commit)\n+static int show_commit(struct commit *commit)\n {\n-\tprintf(\"%s%s\", prefix, sha1_to_hex(commit->object.sha1));\n-\tif (show_parents) {\n-\t\tstruct commit_list *parents = commit->parents;\n-\t\twhile (parents) {\n-\t\t\tprintf(\" %s\", sha1_to_hex(parents->item->object.sha1));\n-\t\t\tparents = parents->next;\n-\t\t}\n-\t}\n-\tputchar('\\n');\n-\tif (verbose_header) {\n-\t\tconst char *buf = commit->buffer;\n-\t\tif (pretty_print) {\n-\t\t\tstatic char pretty_header[16384];\n-\t\t\tpretty_print_commit(commit->buffer, ~0, pretty_header, sizeof(pretty_header));\n-\t\t\tbuf = pretty_header;\n-\t\t}\n-\t\tprintf(\"%s%c\", buf, hdr_termination);\n+\tif (commit->object.flags & UNINTERESTING)\n+\t\treturn 0;\n+\tif (min_age != -1 && (commit->date > min_age))\n+\t\treturn 0;\n+\tif (max_age != -1 && (commit->date < max_age))\n+\t\treturn 1;\n+\tif (max_count != -1 && !max_count--)\n+\t\treturn 1;\n+\n+\tif (!show_breaks) {\n+\t\tprintf(\"%s%s\", prefix, sha1_to_hex(commit->object.sha1));\t\n+\t\tif (show_parents) {\n+\t\t\tstruct commit_list *parents = commit->parents;\n+\t\t\twhile (parents) {\n+\t\t\t\tprintf(\" %s\", sha1_to_hex(parents->item->object.sha1));\n+\t\t\t\tparents = parents->next;\n+\t\t\t}\n+\t\t}\n+\t\tputchar('\\n');\n+\t\tif (verbose_header) {\n+\t\t\tconst char *buf = commit->buffer;\n+\t\t\tif (pretty_print) {\n+\t\t\t\tstatic char pretty_header[16384];\n+\t\t\t\tpretty_print_commit(commit->buffer, ~0, pretty_header, sizeof(pretty_header));\n+\t\t\t\tbuf = pretty_header;\n+\t\t\t}\n+\t\t\tprintf(\"%s%c\", buf, hdr_termination);\n+\t\t}\n+\t} else {\n+\t\tchar c='|';\n+\t\tif (commit->object.flags &DISCONTINUITY) {\n+\t\t\tc = '^';     \n+\t\t} else if (commit->object.flags & BOUNDARY) {\n+\t\t\tc = '=';\n+\t\t} \n+\t\tprintf(\"%c %s\\n\", c, sha1_to_hex(commit->object.sha1));\n \t}\n+        return 0;\n }\n \n static void show_commit_list(struct commit_list *list)\n@@ -49,15 +72,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\t\tbreak;\n-\t\tif (max_count != -1 && !max_count--)\n-\t\t\tbreak;\n-\t\tshow_commit(commit);\n+\t\tif (show_commit(commit)) \n+\t\t\tbreak;         \n \t}\n }\n \n@@ -141,6 +157,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@@ -148,7 +172,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@@ -160,9 +184,18 @@ 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 \n-\tshow_commit_list(list);\n+\t\n+\tif (!merge_order) {\n+\t        if (limited)\n+\t\t          list = limit_list(list);\n+\n+\t\tshow_commit_list(list);\n+        } else {\n+                if (sort_list_in_merge_order(list, &show_commit)) {\n+                        die(\"merge order sort failed\\n\");\n+                }\n+        }\n+\n \treturn 0;\n }\ndiff --git a/t/t6000-rev-list.sh b/t/t6000-rev-list.sh\nnew file mode 100755\n--- /dev/null\n+++ b/t/t6000-rev-list.sh\n@@ -0,0 +1,173 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2005 Jon Seymour\n+#\n+\n+test_description='Test rev-list --merge-order\n+'\n+. ./test-lib.sh\n+\n+function do_commit\n+{\n+    git-commit-tree \"$@\" </dev/null\n+}\n+\n+function check_adjacency\n+{\n+    read previous\n+    echo \"= $previous\"\n+    while read next\n+    do\n+        if ! (git-cat-file commit $previous | grep \"^parent $next\" >/dev/null)\n+        then\n+            echo \"^ $next\"\n+        else\n+            echo \"| $next\"\n+        fi\n+        previous=$next\n+    done\n+}\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+   do\n+       echo -n \"s/${!c}/$c/;\"\n+   done\n+}\n+\n+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 $root)\n+c1=$(do_commit $tree -p $b1)\n+export GIT_COMMITTER_NAME=foobar3 # to guarantee that the commit is different\n+b2=$(do_commit $tree -p $b1)\n+b3=$(do_commit $tree -p $b2)\n+c2=$(do_commit $tree -p $c1 -p $b2)\n+c3=$(do_commit $tree -p $c2)\n+a2=$(do_commit $tree -p $a1)\n+a3=$(do_commit $tree -p $a2)\n+b4=$(do_commit $tree -p $b3 -p $a3)\n+a4=$(do_commit $tree -p $a3 -p $b4 -p $c3)\n+l3=$(do_commit $tree -p $a4)\n+l4=$(do_commit $tree -p $l3)\n+l5=$(do_commit $tree -p $l4)\n+echo $l5 > .git/HEAD\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+| l4\n+| l3\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+| l2\n+| l1\n+| l0\n+= root\n+EOF\n+\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+\n+test_expect_success 'Testing that the rev-list has correct number of entries' '[ $(git-rev-list HEAD | wc -l) -eq 19 ]'\n+test_expect_success 'Testing that --merge-order produces the correct result' 'diff expected-merge-order actual-merge-order'\n+test_expect_success 'Testing that --merge-order produces as many or fewer discontinuities' '[ $merge_order_adjacency_count -le $normal_adjacency_count ]'\n+\n+cat > expected-merge-order-1 <<EOF\n+c3\n+c2\n+c1\n+b3\n+b2\n+b1\n+a3\n+a2\n+a1\n+a0\n+l2\n+l1\n+l0\n+root\n+EOF\n+\n+git-rev-list --merge-order $a3 $b3 $c3 | sed \"$(sed_script)\" > actual-merge-order-1\n+test_expect_success 'Testing multiple heads' 'diff expected-merge-order-1 actual-merge-order-1'\n+\n+cat > expected-merge-order-2 <<EOF\n+c3\n+c2\n+c1\n+b3\n+b2\n+b1\n+a3\n+a2\n+EOF\n+\n+git-rev-list --merge-order $a3 $b3 $c3 ^$a1 | sed \"$(sed_script)\" > actual-merge-order-2\n+test_expect_success 'Testing stop' 'diff expected-merge-order-2 actual-merge-order-2'\n+\n+cat > expected-merge-order-3 <<EOF\n+c3\n+c2\n+c1\n+b3\n+b2\n+b1\n+a3\n+a2\n+a1\n+a0\n+l2\n+EOF\n+\n+git-rev-list --merge-order $a3 $b3 $c3 ^$l1 | sed \"$(sed_script)\" > actual-merge-order-3\n+test_expect_success 'Testing stop in linear epoch' 'diff expected-merge-order-3 actual-merge-order-3'\n+\n+cat > expected-merge-order-4 <<EOF\n+l5\n+l4\n+l3\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+l2\n+EOF\n+\n+git-rev-list --merge-order $l5 ^$l1 | sed \"$(sed_script)\" > actual-merge-order-4\n+test_expect_success 'Testing start in linear epoch, stop after non-linear epoch' 'diff expected-merge-order-4 actual-merge-order-4'\n+\n+git-rev-list --merge-order $l5 $l5 ^$l1 2>/dev/null | sed \"$(sed_script)\" > actual-merge-order-5\n+test_expect_success 'Testing duplicated start arguments' 'diff expected-merge-order-4 actual-merge-order-5'\n+\n+test_done\n"},{"id":"4623","messageId":"Pine.LNX.4.58.0506051741190.1876@ppc970.osdl.org","threadId":"839","inReplyTo":"20050605134733.3123.qmail@blackcubes.dyndns.org","subject":"Re: [PATCH] Modify git-rev-list ... in merge order [ repost with bug fixes ]","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-06T00:44:56Z","receivedAt":"2005-06-06T00:44:56Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 5 Jun 2005 jon@blackcubes.dyndns.org wrote:\n>  \n> -static void show_commit(struct commit *commit)\n> +static int show_commit(struct commit *commit)\n\nIck. You've mixed \"show_commit()\" to be three totally independent things\n - deciding whether to show at all\n - showing the commit in traditional format\n - showing the commit tree in the new \"break\" format\n\nI really hate functions that do totally unrelated things, and I'm so much \nhappier with the new show_commit() than the old \"everything in one big \nfunction\" thing, that I'm unhappy about mixing the thing up again.\n\nPlease leave show_commit() to just show the commit, and make the other \ndecisions be independent of that.\n\n\t\tLinus\n"},{"id":"4626","messageId":"2cfc4032050605180958fcf395@mail.gmail.com","threadId":"839","inReplyTo":"Pine.LNX.4.58.0506051741190.1876@ppc970.osdl.org","subject":"Re: [PATCH] Modify git-rev-list ... in merge order [ repost with bug fixes ]","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-06T01:09:42Z","receivedAt":"2005-06-06T01:09:42Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"On 6/6/05, Linus Torvalds <torvalds@osdl.org> wrote:\n> \n> \n> On Sun, 5 Jun 2005 jon@blackcubes.dyndns.org wrote:\n> >\n> > -static void show_commit(struct commit *commit)\n> > +static int show_commit(struct commit *commit)\n> \n> Ick. You've mixed \"show_commit()\" to be three totally independent things\n>  - deciding whether to show at all\n>  - showing the commit in traditional format\n>  - showing the commit tree in the new \"break\" format\n> \n> I really hate functions that do totally unrelated things, and I'm so much\n> happier with the new show_commit() than the old \"everything in one big\n> function\" thing, that I'm unhappy about mixing the thing up again.\n> \n> Please leave show_commit() to just show the commit, and make the other\n> decisions be independent of that.\n\nMy rationale was to re-use both the filtering logic currently in the\nshow_commit_list while loop and the display logic, since I need both\nin order to maximise compatibility with the standard algorithm.\n\nHowever, I understand your concerns.\n\nMy plan, therefore, is to split the filtering logic from\nshow_commit_list's while loop into a separate function and create a\nthird function which calls the filtering logic, then show_commit. I'll\npass a pointer to the third function to sort_list_in_merge_order. I\ncan leave the show_breaks functionality in show_commit (it is, after\nall, display functionality) or I can move it into the third function.\n\nIs that ok by you?\n\njon.\n"},{"id":"4627","messageId":"Pine.LNX.4.58.0506051842310.1876@ppc970.osdl.org","threadId":"839","inReplyTo":"2cfc4032050605180958fcf395@mail.gmail.com","subject":"Re: [PATCH] Modify git-rev-list ... in merge order [ repost with bug fixes ]","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-06T01:43:44Z","receivedAt":"2005-06-06T01:43:44Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 6 Jun 2005, Jon Seymour wrote:\n> \n> My rationale was to re-use both the filtering logic currently in the\n> show_commit_list while loop and the display logic, since I need both\n> in order to maximise compatibility with the standard algorithm.\n\nIt's obviously ok to re-use the filtering, I'm just objecting to putting\nit into a function that is really unrelated to filtering..\n\n> My plan, therefore, is to split the filtering logic from\n> show_commit_list's while loop into a separate function and create a\n> third function which calls the filtering logic, then show_commit.\n\nYes.\n\n\t\tLinus\n"}]}