{"thread":{"id":"810","subject":"[PATCH] Modify git-rev-list to linearise the commit history in merge order.","startedAt":"2005-06-02T15:16:38Z","lastAt":"2005-06-02T15:31:03Z","messageCount":2,"participants":["Jon Seymour"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"4421","messageId":"2cfc403205060208161bb06662@mail.gmail.com","threadId":"810","inReplyTo":"20050602151332.29183.qmail@blackcubes.dyndns.org","subject":"[PATCH] Modify git-rev-list to linearise the commit history in merge order.","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-02T15:16:38Z","receivedAt":"2005-06-02T15:16:38Z","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\nA test script, t/t5000-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        cd t\n        ./t5000-rev-list.sh\n        cd trash\n        cat actual-default-order\n        cat actual-merge-order\n\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\nalso on the linux-2.6\nrepository and has reasonable performance on both.\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---\ndiff --git a/Makefile b/Makefile\n--- a/Makefile\n+++ b/Makefile\n@@ -40,9 +40,9 @@ install: $(PROG) $(SCRIPTS)\n        $(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-        tag.o delta.o date.o index.o diff-delta.o patch-delta.o\n+        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        $(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        }\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        struct commit_list **pp = list;\n        struct commit_list *p;\n@@ -254,3 +254,25 @@ unsigned long pretty_print_commit(const\n        buf[offset] = '\\0';\n        return offset;\n }\n+\n+struct commit *pop_commit(struct commit_list **stack)\n+{\n+       struct commit_list *top = *stack;\n+       struct commit *item = top ? top->item : NULL;\n+\n+       if (top) {\n+               *stack = top->next;\n+               free(top);\n+       }\n+       return 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\nlong 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                                      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,454 @@\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\nrationales\n+ * for some of the algorithms used here.\n+ *\n+ */\n+#include <stdlib.h>\n+#include <openssl/bn.h>                // provides arbitrary\nprecision integers required to accurately represent fractional mass\n+#include \"cache.h\"\n+#include \"commit.h\"\n+#include \"epoch.h\"\n+\n+struct fraction {\n+       BIGNUM numerator;\n+       BIGNUM 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+       if (!context) {\n+               context = BN_CTX_new();\n+       }\n+       return context;\n+}\n+\n+static struct fraction *new_zero()\n+{\n+       struct fraction *result = xmalloc(sizeof(*result));\n+       BN_init(&result->numerator);\n+       BN_init(&result->denominator);\n+       BN_zero(&result->numerator);\n+       BN_one(&result->denominator);\n+       return result;\n+}\n+\n+static void clear_fraction(struct fraction *fraction)\n+{\n+       BN_clear(&fraction->numerator);\n+       BN_clear(&fraction->denominator);\n+}\n+\n+static struct fraction *divide(struct fraction *result, struct\nfraction *fraction, int divisor)\n+{\n+       BIGNUM bn_divisor;\n+\n+       BN_init(&bn_divisor);\n+       BN_set_word(&bn_divisor, divisor);\n+\n+       BN_copy(&result->numerator, &fraction->numerator);\n+       BN_mul(&result->denominator, &fraction->denominator,\n&bn_divisor, get_BN_CTX());\n+\n+       BN_clear(&bn_divisor);\n+       return result;\n+}\n+\n+static struct fraction *init_fraction(struct fraction *fraction)\n+{\n+       BN_init(&fraction->numerator);\n+       BN_init(&fraction->denominator);\n+       BN_zero(&fraction->numerator);\n+       BN_one(&fraction->denominator);\n+       return fraction;\n+}\n+\n+static struct fraction *get_one()\n+{\n+       if (!one) {\n+               one = new_zero();\n+               BN_one(&one->numerator);\n+       }\n+       return one;\n+}\n+\n+static struct fraction *get_zero()\n+{\n+       if (!zero) {\n+               zero = new_zero();\n+       }\n+       return zero;\n+}\n+\n+static struct fraction *copy(struct fraction *to, struct fraction *from)\n+{\n+       BN_copy(&to->numerator, &from->numerator);\n+       BN_copy(&to->denominator, &from->denominator);\n+       return to;\n+}\n+\n+static struct fraction *add(struct fraction *result, struct fraction\n*left, struct fraction *right)\n+{\n+       BIGNUM a, b, gcd;\n+\n+       BN_init(&a);\n+       BN_init(&b);\n+       BN_init(&gcd);\n+\n+       BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());\n+       BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());\n+       BN_mul(&result->denominator, &left->denominator,\n&right->denominator, get_BN_CTX());\n+       BN_add(&result->numerator, &a, &b);\n+\n+       BN_gcd(&gcd, &result->denominator, &result->numerator, get_BN_CTX());\n+       BN_div(&result->denominator, NULL, &result->denominator, &gcd,\nget_BN_CTX());\n+       BN_div(&result->numerator, NULL, &result->numerator, &gcd,\nget_BN_CTX());\n+\n+       BN_clear(&a);\n+       BN_clear(&b);\n+       BN_clear(&gcd);\n+\n+       return result;\n+}\n+\n+static int compare(struct fraction *left, struct fraction *right)\n+{\n+       BIGNUM a, b;\n+\n+       int result;\n+\n+       BN_init(&a);\n+       BN_init(&b);\n+\n+       BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());\n+       BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());\n+\n+       result = BN_cmp(&a, &b);\n+\n+       BN_clear(&a);\n+       BN_clear(&b);\n+\n+       return result;\n+}\n+\n+struct mass_counter {\n+       struct fraction seen;\n+       struct fraction pending;\n+};\n+\n+static struct mass_counter *new_mass_counter(struct commit *commit,\nstruct fraction *pending)\n+{\n+       struct mass_counter *mass_counter = xmalloc(sizeof(*mass_counter));\n+       memset(mass_counter, 0, sizeof(*mass_counter));\n+\n+       init_fraction(&mass_counter->seen);\n+       init_fraction(&mass_counter->pending);\n+\n+       copy(&mass_counter->pending, pending);\n+       copy(&mass_counter->seen, get_zero());\n+\n+       commit->object.util = mass_counter;\n+\n+       return mass_counter;\n+}\n+\n+static void free_mass_counter(struct mass_counter *counter)\n+{\n+       clear_fraction(&counter->seen);\n+       clear_fraction(&counter->pending);\n+       free(counter);\n+}\n+\n+//\n+// Finds the base node of an epoch.\n+//\n+// This algorithm uses a conservation of mass approach.\n+//\n+// The head starts with a weight of 1 and distributes equal portions\n+// along each edge to each of its parents. The process continues until\n+// one node discovers that it has acquired a total mass of 1 from its\n+// descendents. This node is the base node.\n+//\n+// Importantly the queue of nodes to be processed is sorted in\n+// reverse date order and each node occupies at most one\n+// position in the queue simultaneously. These two properties\n+// do not effect the algorithm's correctness. However assuming most, but\n+// not all, timestamps are sane they do prevent the algorithm becoming\n+// exponential by ensuring that most nodes are only visited once.\n+// This is true because mass is only propagated through the network\n+// when we are pretty sure we are not going to see any more coming\n+// our way. The occasional bad timestamp will mean that we are\n+// wrong, occasionally, but this does not matter too much.\n+//\n+static int find_base(struct commit *head, struct commit **boundary)\n+{\n+       int ret = 0;\n+\n+       struct commit_list *cleaner = NULL;\n+       struct commit_list *pending = NULL;\n+\n+       *boundary = NULL;\n+\n+       // we inject a mass of 1 unit here\n+\n+       new_mass_counter(head, get_one());\n+\n+       commit_list_insert(head, &pending);\n+       commit_list_insert(head, &cleaner);\n+\n+       while (!*boundary && pending && !ret) {\n+\n+               struct commit *latest = pop_commit(&pending);\n+               struct mass_counter *latest_node = (struct\nmass_counter *) latest->object.util;\n+\n+               if ((ret = parse_commit(latest)))\n+                       continue;\n+\n+               add(&latest_node->seen, &latest_node->seen,\n&latest_node->pending);\n+\n+               int num_parents = count_parents(latest);\n+\n+               if (num_parents) {\n+\n+                       struct fraction distribution;\n+\n+                       divide(init_fraction(&distribution),\n&latest_node->pending, num_parents);\n+\n+                       struct commit_list *parents;\n+\n+                       for (parents = latest->parents; parents;\nparents = parents->next) {\n+                               struct commit *parent = parents->item;\n+                               struct mass_counter *parent_node =\n(struct mass_counter *) parent->object.util;\n+                               if (!parent_node) {\n+                                       parent_node =\nnew_mass_counter(parent, &distribution);\n+                                       commit_list_insert(parent, &cleaner);\n+                                       insert_by_date(&pending, parent);\n+                               } else {\n+                                       if\n(!compare(&parent_node->pending, get_zero())) {\n+                                              \ncopy(&parent_node->pending, &distribution);\n+                                              \ninsert_by_date(&pending, parent);\n+                                       } else {\n+                                              \nadd(&parent_node->pending, &parent_node->pending, &distribution);\n+                                       }\n+                               }\n+                       }\n+               }\n+\n+               if (!compare(&latest_node->seen, get_one()) && (latest\n!= head)) {\n+                       // if this node has seen one unit of mass, it\nmust be the base, so mark\n+                       // the boundary which will cause the loop to stop.\n+                       *boundary = latest;\n+               }\n+\n+               copy(&latest_node->pending, get_zero());\n+\n+       }\n+\n+       for (; cleaner;) {\n+               struct commit *next = pop_commit(&cleaner);\n+               free_mass_counter((struct mass_counter *) next->object.util);\n+               next->object.util = NULL;\n+       }\n+\n+       if (pending)\n+               free_commit_list(pending);\n+\n+       return ret;\n+\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,\nstruct commit **boundary)\n+{\n+       int ret;\n+       struct commit *item = head_of_epoch;\n+\n+       ret = parse_commit(item);\n+       if (ret)\n+               return ret;\n+\n+       if (HAS_EXACTLY_ONE_PARENT(item)) {\n+\n+               // we are at the start of a maximimal linear epoch ..\ntraverse to the end\n+\n+               // traverse to the end of a maximal linear epoch\n+               while (HAS_EXACTLY_ONE_PARENT(item) && !ret) {\n+                       item = item->parents->item;\n+                       ret = parse_commit(item);\n+               }\n+               *boundary = item;\n+\n+       } else {\n+\n+               // otherwise, we are at the start of a minimal, non-linear\n+               // epoch - find the common base of all parents.\n+\n+               ret = find_base(item, boundary);\n+\n+       }\n+\n+       return 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+       struct commit_list *parents;\n+       for (parents = child->parents; parents; parents = parents->next) {\n+               if (!memcmp(parent->object.sha1,\nparents->item->object.sha1, sizeof(parents->item->object.sha1)))\n+                       return 1;\n+       }\n+       return 0;\n+}\n+\n+static void push_onto_merge_order_stack(struct commit_list **stack,\nstruct commit *item)\n+{\n+       struct commit_list *top = *stack;\n+       if (top && (top->item->object.flags & MERGE_ORDER_BREAK_FLAG)) {\n+               if (is_parent_of(top->item, item)) {\n+                       top->item->object.flags &= ~MERGE_ORDER_BREAK_FLAG;\n+               }\n+       }\n+       commit_list_insert(item, stack);\n+}\n+\n+//\n+// Sorts the nodes of the first epoch of the epoch sequence of the\nepoch headed at head\n+// into merge order.\n+//\n+static void sort_first_epoch(struct commit *head, struct commit_list **stack)\n+{\n+       parse_commit(head);\n+\n+       head->object.flags |= MERGE_ORDER_VISIT_FLAG;\n+\n+       struct commit_list *parents;\n+\n+       struct commit_list *reversed_parents = NULL;\n+\n+       //\n+       // parse_commit builds the parent list in reverse order with\nrespect to the order of\n+       // the git-commit-tree arguments.\n+       //\n+       // so we need to reverse this list to output the oldest (or\nmost \"local\") commits last.\n+       //\n+\n+       for (parents = head->parents; parents; parents = parents->next) {\n+               commit_list_insert(parents->item, &reversed_parents);\n+       }\n+\n+       //\n+       // todo: by sorting the parents in a different order, we can alter the\n+       // merge order to show contemporaneous changes in parallel branches\n+       // occurring after \"local\" changes. This is useful for a developer\n+       // when a developer wants to see all changes that were incorporated\n+       // into the same merge as her own changes occur after her own\n+       // changes.\n+       //\n+\n+       for (; reversed_parents;) {\n+               struct commit *parent = pop_commit(&reversed_parents);\n+               parse_commit(parent);\n+               if (!(parent->object.flags & MERGE_ORDER_VISIT_FLAG)) {\n+                       if (parent->object.flags & MERGE_ORDER_EPOCH_FLAG) {\n+                               if (*stack) {\n+                                       die(\"something else is on the\nstack - %s\\n\", sha1_to_hex((*stack)->item->object.sha1));\n+                               }\n+                               push_onto_merge_order_stack(stack, parent);\n+                               parent->object.flags |= MERGE_ORDER_VISIT_FLAG;\n+                       } else {\n+                               sort_first_epoch(parent, stack);\n+                               if (reversed_parents) {\n+                                       //\n+                                       // this indicates a possible\ndiscontinuity\n+                                       // it may not be be actual\ndiscontinuity if\n+                                       // the head of parent N\nhappens to be the tail\n+                                       // of parent N+1\n+                                       //\n+                                       // the next push onto the\nstack will resolve the question\n+                                       //\n+                                       (*stack)->item->object.flags\n|= MERGE_ORDER_BREAK_FLAG;\n+                               }\n+                       }\n+               }\n+       }\n+\n+       push_onto_merge_order_stack(stack, head);\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+int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter)\n+{\n+       struct commit *next;\n+       int ret = 0;\n+       int stop = 0;\n+\n+       parse_commit(head_of_epoch);\n+\n+       for (next = head_of_epoch; next && next->parents && !ret && !stop;) {\n+\n+               struct commit *base = NULL;\n+\n+               ret = find_next_epoch_boundary(next, &base);\n+               if (ret)\n+                       return ret;\n+\n+               next->object.flags |= MERGE_ORDER_EPOCH_FLAG;\n+               if (base) {\n+                       base->object.flags |= MERGE_ORDER_EPOCH_FLAG;\n+               }\n+\n+               if (HAS_EXACTLY_ONE_PARENT(next)) {\n+\n+                       while (HAS_EXACTLY_ONE_PARENT(next) && !stop && !ret) {\n+                               stop = (*emitter) (next);\n+                               next = next->parents->item;\n+                               ret = parse_commit(next);\n+                       }\n+\n+               } else {\n+\n+                       struct commit_list *stack = NULL;\n+                       sort_first_epoch(next, &stack);\n+                       for (; stack && !stop;) {\n+                               next = pop_commit(&stack);\n+                               if (stack) {\n+                                       stop = (*emitter) (next);\n+                               }\n+                       }\n+                       if (stack) {\n+                               free_commit_list(stack);\n+                       }\n+               }\n+\n+       }\n+\n+       if (next && !stop) {\n+               stop = (*emitter) (next);\n+       }\n+\n+       return 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,12 @@\n+#ifndef EPOCH_H\n+#define EPOCH_H\n+\n+typedef int (*emitter_func) (struct commit *);\n+\n+int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter);\n+\n+#define MERGE_ORDER_EPOCH_FLAG (1u<<3)\n+#define MERGE_ORDER_VISIT_FLAG (1u<<4)\n+#define MERGE_ORDER_BREAK_FLAG (1u<<5)\n+\n+#endif                         /* 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        const char *type;\n        struct object_list *refs;\n        struct object_list *attached_deltas;\n+       void *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,5 +1,6 @@\n #include \"cache.h\"\n #include \"commit.h\"\n+#include \"epoch.h\"\n\n #define SEEN           (1u << 0)\n #define INTERESTING    (1u << 1)\n@@ -11,7 +12,8 @@ static const char rev_list_usage[] =\n                      \"  --max-age=epoch\\n\"\n                      \"  --min-age=epoch\\n\"\n                      \"  --header\\n\"\n-                     \"  --pretty\";\n+                     \"  --pretty\\n\"\n+                     \"  --merge-order [ --show-breaks ]\";\n\n static void mark_parents_uninteresting(struct commit *commit)\n {\n@@ -36,18 +38,63 @@ static int everybody_uninteresting(struc\n        return 1;\n }\n\n+static unsigned long max_age = -1;\n+static unsigned long min_age = -1;\n+static int max_count = -1;\n+static int verbose_header = 0, show_parents = 0, pretty_print = 0,\nmerge_order = 0, show_breaks = 0;\n+static const char *prefix = \"\";\n+static int hdr_termination = 0;\n+\n+static int process_commit(struct commit * commit)\n+{\n+       if (commit->object.flags & UNINTERESTING)\n+               return 0;\n+       if (min_age != -1 && (commit->date > min_age))\n+               return 0;\n+       if (max_age != -1 && (commit->date < max_age))\n+               return 1;\n+       if (max_count != -1 && !max_count--)\n+               return 1;\n+\n+        if (!show_breaks) {\n+               printf(\"%s%s\", prefix, sha1_to_hex(commit->object.sha1));\n+               if (show_parents) {\n+                       struct commit_list *parents = commit->parents;\n+                       while (parents) {\n+                               printf(\" %s\",\nsha1_to_hex(parents->item->object.sha1));\n+                               parents = parents->next;\n+                       }\n+               }\n+               putchar('\\n');\n+               if (verbose_header) {\n+                       const char *buf = commit->buffer;\n+                       if (pretty_print) {\n+                               static char pretty_header[16384];\n+                               pretty_print_commit(commit->buffer,\n~0, pretty_header, sizeof(pretty_header));\n+                               buf = pretty_header;\n+                       }\n+                       printf(\"%s%c\", buf, hdr_termination);\n+               }\n+        } else {\n+                char c='|';\n+                if (commit->object.flags & MERGE_ORDER_BREAK_FLAG) {\n+                  c = '^';\n+                } else if (commit->object.flags & MERGE_ORDER_EPOCH_FLAG) {\n+                  c = '=';\n+                }\n+                printf(\"%c %s\\n\", c, sha1_to_hex(commit->object.sha1));\n+        }\n+\n+        return 0;\n+}\n+\n int main(int argc, char **argv)\n {\n        int nr_sha;\n        unsigned char sha1[2][20];\n        struct commit_list *list = NULL;\n        struct commit *commit, *end;\n-       int i, verbose_header = 0, show_parents = 0, pretty_print = 0;\n-       int hdr_termination = 0;\n-       const char *prefix = \"\";\n-       unsigned long max_age = -1;\n-       unsigned long min_age = -1;\n-       int max_count = -1;\n+       int i;\n\n        nr_sha = 0;\n        for (i = 1 ; i < argc; i++) {\n@@ -80,8 +127,16 @@ int main(int argc, char **argv)\n                        show_parents = 1;\n                        continue;\n                }\n+               if (!strncmp(arg, \"--merge-order\", 13)) {\n+                       merge_order = 1;\n+                       continue;\n+               }\n+               if (!strncmp(arg, \"--show-breaks\", 13)) {\n+                       show_breaks = 1;\n+                       continue;\n+               }\n\n-               if (nr_sha > 2 || get_sha1(arg, sha1[nr_sha]))\n+               if (nr_sha > 2 || get_sha1(arg, sha1[nr_sha])||\n(show_breaks && !merge_order))\n                        usage(rev_list_usage);\n                nr_sha++;\n        }\n@@ -118,36 +173,19 @@ int main(int argc, char **argv)\n                } while (list);\n                list = newlist;\n        }\n+\n+       if (!merge_order) {\n+               while (list) {\n+                       struct commit *commit =\npop_most_recent_commit(&list, SEEN);\n+                       if (process_commit(commit)) {\n+                              break;\n+                        }\n+               }\n+        } else {\n+                if (sort_in_merge_order(commit, &process_commit)) {\n+                        die(\"merge order sort failed\\n\");\n+                }\n+        }\n\n-       while (list) {\n-               struct commit *commit = pop_most_recent_commit(&list, SEEN);\n-\n-               if (commit->object.flags & UNINTERESTING)\n-                       continue;\n-               if (min_age != -1 && (commit->date > min_age))\n-                       continue;\n-               if (max_age != -1 && (commit->date < max_age))\n-                       break;\n-               if (max_count != -1 && !max_count--)\n-                       break;\n-               printf(\"%s%s\", prefix, sha1_to_hex(commit->object.sha1));\n-               if (show_parents) {\n-                       struct commit_list *parents = commit->parents;\n-                       while (parents) {\n-                               printf(\" %s\",\nsha1_to_hex(parents->item->object.sha1));\n-                               parents = parents->next;\n-                       }\n-               }\n-               putchar('\\n');\n-               if (verbose_header) {\n-                       const char *buf = commit->buffer;\n-                       if (pretty_print) {\n-                               static char pretty_header[16384];\n-                               pretty_print_commit(commit->buffer,\n~0, pretty_header, sizeof(pretty_header));\n-                               buf = pretty_header;\n-                       }\n-                       printf(\"%s%c\", buf, hdr_termination);\n-               }\n-       }\n        return 0;\n }\ndiff --git a/t/t5000-rev-list.sh b/t/t5000-rev-list.sh\nnew file mode 100755\n--- /dev/null\n+++ b/t/t5000-rev-list.sh\n@@ -0,0 +1,85 @@\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\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)\n+export GIT_COMMITTER_NAME=foobar  # to guarantee that the commit is different\n+a0=$(do_commit $tree -p $root)\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+echo $a4 > .git/HEAD\n+\n+git-rev-list --merge-order --show-breaks HEAD | sed \"$(sed_script)\" >\nactual-merge-order\n+cat > expected-merge-order <<EOF\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+EOF\n+\n+git-rev-list HEAD | check_adjacency | sed \"$(sed_script)\" >\nactual-default-order\n+normal_adjacency_count=$(git-rev-list HEAD | check_adjacency | grep\n-c \"\\^\" | tr -d ' ')\n+merge_order_adjacency_count=$(git-rev-list --merge-order HEAD |\ncheck_adjacency | grep -c \"\\^\" | tr -d ' ')\n+\n+test_expect_success 'Testing that the rev-list has correct number of\nentries' '[ $(git-rev-list HEAD | wc -l) -eq 13 ]'\n+test_expect_success 'Testing that --merge-order produces the correct\nresult' 'diff expected-merge-order actual-merge-order'\n+test_expect_success 'Testing that --merge-order produces as many or\nfewer discontinuities' '[ $merge_order_adjacency_count -le\n$normal_adjacency_count ]'\n+\n+test_done\n\n\n-- \nhomepage: http://www.zeta.org.au/~jon/\nblog: http://orwelliantremors.blogspot.com/\n"},{"id":"4422","messageId":"2cfc4032050602083131c990a6@mail.gmail.com","threadId":"810","inReplyTo":"2cfc403205060208161bb06662@mail.gmail.com","subject":"[PATCH] Modify git-rev-list to linearise the commit history in merge order. [ pox on the house of gmail ]","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-02T15:31:03Z","receivedAt":"2005-06-02T15:31:03Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"Pox on the house of gmail!\n\nA non-wrapped version of the patch can be downloaded from:\n\n        http://blackcubes.dyndns.org/epoch/epoch.patch\n\nMore info about the patch can be read here:\n\n        http://blackcubes.dyndns.org/epoch/\n\nDiscussion to the list please.\n\njon.\n---------- Forwarded message ----------\nFrom: Jon Seymour <jon.seymour@gmail.com>\nDate: Jun 3, 2005 1:16 AM\nSubject: [PATCH] Modify git-rev-list to linearise the commit history\nin merge order.\nTo: Git Mailing List <git@vger.kernel.org>\nCc: Linus Torvalds <torvalds@osdl.org>, Paul Mackerras <paulus@samba.org>\n\n\n[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\nA test script, t/t5000-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        cd t\n        ./t5000-rev-list.sh\n        cd trash\n        cat actual-default-order\n        cat actual-merge-order\n\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\nalso on the linux-2.6\nrepository and has reasonable performance on both.\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---\ndiff --git a/Makefile b/Makefile\n--- a/Makefile\n+++ b/Makefile\n@@ -40,9 +40,9 @@ install: $(PROG) $(SCRIPTS)\n        $(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-        tag.o delta.o date.o index.o diff-delta.o patch-delta.o\n+        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        $(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        }\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        struct commit_list **pp = list;\n        struct commit_list *p;\n@@ -254,3 +254,25 @@ unsigned long pretty_print_commit(const\n        buf[offset] = '\\0';\n        return offset;\n }\n+\n+struct commit *pop_commit(struct commit_list **stack)\n+{\n+       struct commit_list *top = *stack;\n+       struct commit *item = top ? top->item : NULL;\n+\n+       if (top) {\n+               *stack = top->next;\n+               free(top);\n+       }\n+       return 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\nlong 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                                      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,454 @@\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\nrationales\n+ * for some of the algorithms used here.\n+ *\n+ */\n+#include <stdlib.h>\n+#include <openssl/bn.h>                // provides arbitrary\nprecision integers required to accurately represent fractional mass\n+#include \"cache.h\"\n+#include \"commit.h\"\n+#include \"epoch.h\"\n+\n+struct fraction {\n+       BIGNUM numerator;\n+       BIGNUM 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+       if (!context) {\n+               context = BN_CTX_new();\n+       }\n+       return context;\n+}\n+\n+static struct fraction *new_zero()\n+{\n+       struct fraction *result = xmalloc(sizeof(*result));\n+       BN_init(&result->numerator);\n+       BN_init(&result->denominator);\n+       BN_zero(&result->numerator);\n+       BN_one(&result->denominator);\n+       return result;\n+}\n+\n+static void clear_fraction(struct fraction *fraction)\n+{\n+       BN_clear(&fraction->numerator);\n+       BN_clear(&fraction->denominator);\n+}\n+\n+static struct fraction *divide(struct fraction *result, struct\nfraction *fraction, int divisor)\n+{\n+       BIGNUM bn_divisor;\n+\n+       BN_init(&bn_divisor);\n+       BN_set_word(&bn_divisor, divisor);\n+\n+       BN_copy(&result->numerator, &fraction->numerator);\n+       BN_mul(&result->denominator, &fraction->denominator,\n&bn_divisor, get_BN_CTX());\n+\n+       BN_clear(&bn_divisor);\n+       return result;\n+}\n+\n+static struct fraction *init_fraction(struct fraction *fraction)\n+{\n+       BN_init(&fraction->numerator);\n+       BN_init(&fraction->denominator);\n+       BN_zero(&fraction->numerator);\n+       BN_one(&fraction->denominator);\n+       return fraction;\n+}\n+\n+static struct fraction *get_one()\n+{\n+       if (!one) {\n+               one = new_zero();\n+               BN_one(&one->numerator);\n+       }\n+       return one;\n+}\n+\n+static struct fraction *get_zero()\n+{\n+       if (!zero) {\n+               zero = new_zero();\n+       }\n+       return zero;\n+}\n+\n+static struct fraction *copy(struct fraction *to, struct fraction *from)\n+{\n+       BN_copy(&to->numerator, &from->numerator);\n+       BN_copy(&to->denominator, &from->denominator);\n+       return to;\n+}\n+\n+static struct fraction *add(struct fraction *result, struct fraction\n*left, struct fraction *right)\n+{\n+       BIGNUM a, b, gcd;\n+\n+       BN_init(&a);\n+       BN_init(&b);\n+       BN_init(&gcd);\n+\n+       BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());\n+       BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());\n+       BN_mul(&result->denominator, &left->denominator,\n&right->denominator, get_BN_CTX());\n+       BN_add(&result->numerator, &a, &b);\n+\n+       BN_gcd(&gcd, &result->denominator, &result->numerator, get_BN_CTX());\n+       BN_div(&result->denominator, NULL, &result->denominator, &gcd,\nget_BN_CTX());\n+       BN_div(&result->numerator, NULL, &result->numerator, &gcd,\nget_BN_CTX());\n+\n+       BN_clear(&a);\n+       BN_clear(&b);\n+       BN_clear(&gcd);\n+\n+       return result;\n+}\n+\n+static int compare(struct fraction *left, struct fraction *right)\n+{\n+       BIGNUM a, b;\n+\n+       int result;\n+\n+       BN_init(&a);\n+       BN_init(&b);\n+\n+       BN_mul(&a, &left->numerator, &right->denominator, get_BN_CTX());\n+       BN_mul(&b, &left->denominator, &right->numerator, get_BN_CTX());\n+\n+       result = BN_cmp(&a, &b);\n+\n+       BN_clear(&a);\n+       BN_clear(&b);\n+\n+       return result;\n+}\n+\n+struct mass_counter {\n+       struct fraction seen;\n+       struct fraction pending;\n+};\n+\n+static struct mass_counter *new_mass_counter(struct commit *commit,\nstruct fraction *pending)\n+{\n+       struct mass_counter *mass_counter = xmalloc(sizeof(*mass_counter));\n+       memset(mass_counter, 0, sizeof(*mass_counter));\n+\n+       init_fraction(&mass_counter->seen);\n+       init_fraction(&mass_counter->pending);\n+\n+       copy(&mass_counter->pending, pending);\n+       copy(&mass_counter->seen, get_zero());\n+\n+       commit->object.util = mass_counter;\n+\n+       return mass_counter;\n+}\n+\n+static void free_mass_counter(struct mass_counter *counter)\n+{\n+       clear_fraction(&counter->seen);\n+       clear_fraction(&counter->pending);\n+       free(counter);\n+}\n+\n+//\n+// Finds the base node of an epoch.\n+//\n+// This algorithm uses a conservation of mass approach.\n+//\n+// The head starts with a weight of 1 and distributes equal portions\n+// along each edge to each of its parents. The process continues until\n+// one node discovers that it has acquired a total mass of 1 from its\n+// descendents. This node is the base node.\n+//\n+// Importantly the queue of nodes to be processed is sorted in\n+// reverse date order and each node occupies at most one\n+// position in the queue simultaneously. These two properties\n+// do not effect the algorithm's correctness. However assuming most, but\n+// not all, timestamps are sane they do prevent the algorithm becoming\n+// exponential by ensuring that most nodes are only visited once.\n+// This is true because mass is only propagated through the network\n+// when we are pretty sure we are not going to see any more coming\n+// our way. The occasional bad timestamp will mean that we are\n+// wrong, occasionally, but this does not matter too much.\n+//\n+static int find_base(struct commit *head, struct commit **boundary)\n+{\n+       int ret = 0;\n+\n+       struct commit_list *cleaner = NULL;\n+       struct commit_list *pending = NULL;\n+\n+       *boundary = NULL;\n+\n+       // we inject a mass of 1 unit here\n+\n+       new_mass_counter(head, get_one());\n+\n+       commit_list_insert(head, &pending);\n+       commit_list_insert(head, &cleaner);\n+\n+       while (!*boundary && pending && !ret) {\n+\n+               struct commit *latest = pop_commit(&pending);\n+               struct mass_counter *latest_node = (struct\nmass_counter *) latest->object.util;\n+\n+               if ((ret = parse_commit(latest)))\n+                       continue;\n+\n+               add(&latest_node->seen, &latest_node->seen,\n&latest_node->pending);\n+\n+               int num_parents = count_parents(latest);\n+\n+               if (num_parents) {\n+\n+                       struct fraction distribution;\n+\n+                       divide(init_fraction(&distribution),\n&latest_node->pending, num_parents);\n+\n+                       struct commit_list *parents;\n+\n+                       for (parents = latest->parents; parents;\nparents = parents->next) {\n+                               struct commit *parent = parents->item;\n+                               struct mass_counter *parent_node =\n(struct mass_counter *) parent->object.util;\n+                               if (!parent_node) {\n+                                       parent_node =\nnew_mass_counter(parent, &distribution);\n+                                       commit_list_insert(parent, &cleaner);\n+                                       insert_by_date(&pending, parent);\n+                               } else {\n+                                       if\n(!compare(&parent_node->pending, get_zero())) {\n+\ncopy(&parent_node->pending, &distribution);\n+\ninsert_by_date(&pending, parent);\n+                                       } else {\n+\nadd(&parent_node->pending, &parent_node->pending, &distribution);\n+                                       }\n+                               }\n+                       }\n+               }\n+\n+               if (!compare(&latest_node->seen, get_one()) && (latest\n!= head)) {\n+                       // if this node has seen one unit of mass, it\nmust be the base, so mark\n+                       // the boundary which will cause the loop to stop.\n+                       *boundary = latest;\n+               }\n+\n+               copy(&latest_node->pending, get_zero());\n+\n+       }\n+\n+       for (; cleaner;) {\n+               struct commit *next = pop_commit(&cleaner);\n+               free_mass_counter((struct mass_counter *) next->object.util);\n+               next->object.util = NULL;\n+       }\n+\n+       if (pending)\n+               free_commit_list(pending);\n+\n+       return ret;\n+\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,\nstruct commit **boundary)\n+{\n+       int ret;\n+       struct commit *item = head_of_epoch;\n+\n+       ret = parse_commit(item);\n+       if (ret)\n+               return ret;\n+\n+       if (HAS_EXACTLY_ONE_PARENT(item)) {\n+\n+               // we are at the start of a maximimal linear epoch ..\ntraverse to the end\n+\n+               // traverse to the end of a maximal linear epoch\n+               while (HAS_EXACTLY_ONE_PARENT(item) && !ret) {\n+                       item = item->parents->item;\n+                       ret = parse_commit(item);\n+               }\n+               *boundary = item;\n+\n+       } else {\n+\n+               // otherwise, we are at the start of a minimal, non-linear\n+               // epoch - find the common base of all parents.\n+\n+               ret = find_base(item, boundary);\n+\n+       }\n+\n+       return 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+       struct commit_list *parents;\n+       for (parents = child->parents; parents; parents = parents->next) {\n+               if (!memcmp(parent->object.sha1,\nparents->item->object.sha1, sizeof(parents->item->object.sha1)))\n+                       return 1;\n+       }\n+       return 0;\n+}\n+\n+static void push_onto_merge_order_stack(struct commit_list **stack,\nstruct commit *item)\n+{\n+       struct commit_list *top = *stack;\n+       if (top && (top->item->object.flags & MERGE_ORDER_BREAK_FLAG)) {\n+               if (is_parent_of(top->item, item)) {\n+                       top->item->object.flags &= ~MERGE_ORDER_BREAK_FLAG;\n+               }\n+       }\n+       commit_list_insert(item, stack);\n+}\n+\n+//\n+// Sorts the nodes of the first epoch of the epoch sequence of the\nepoch headed at head\n+// into merge order.\n+//\n+static void sort_first_epoch(struct commit *head, struct commit_list **stack)\n+{\n+       parse_commit(head);\n+\n+       head->object.flags |= MERGE_ORDER_VISIT_FLAG;\n+\n+       struct commit_list *parents;\n+\n+       struct commit_list *reversed_parents = NULL;\n+\n+       //\n+       // parse_commit builds the parent list in reverse order with\nrespect to the order of\n+       // the git-commit-tree arguments.\n+       //\n+       // so we need to reverse this list to output the oldest (or\nmost \"local\") commits last.\n+       //\n+\n+       for (parents = head->parents; parents; parents = parents->next) {\n+               commit_list_insert(parents->item, &reversed_parents);\n+       }\n+\n+       //\n+       // todo: by sorting the parents in a different order, we can alter the\n+       // merge order to show contemporaneous changes in parallel branches\n+       // occurring after \"local\" changes. This is useful for a developer\n+       // when a developer wants to see all changes that were incorporated\n+       // into the same merge as her own changes occur after her own\n+       // changes.\n+       //\n+\n+       for (; reversed_parents;) {\n+               struct commit *parent = pop_commit(&reversed_parents);\n+               parse_commit(parent);\n+               if (!(parent->object.flags & MERGE_ORDER_VISIT_FLAG)) {\n+                       if (parent->object.flags & MERGE_ORDER_EPOCH_FLAG) {\n+                               if (*stack) {\n+                                       die(\"something else is on the\nstack - %s\\n\", sha1_to_hex((*stack)->item->object.sha1));\n+                               }\n+                               push_onto_merge_order_stack(stack, parent);\n+                               parent->object.flags |= MERGE_ORDER_VISIT_FLAG;\n+                       } else {\n+                               sort_first_epoch(parent, stack);\n+                               if (reversed_parents) {\n+                                       //\n+                                       // this indicates a possible\ndiscontinuity\n+                                       // it may not be be actual\ndiscontinuity if\n+                                       // the head of parent N\nhappens to be the tail\n+                                       // of parent N+1\n+                                       //\n+                                       // the next push onto the\nstack will resolve the question\n+                                       //\n+                                       (*stack)->item->object.flags\n|= MERGE_ORDER_BREAK_FLAG;\n+                               }\n+                       }\n+               }\n+       }\n+\n+       push_onto_merge_order_stack(stack, head);\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+int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter)\n+{\n+       struct commit *next;\n+       int ret = 0;\n+       int stop = 0;\n+\n+       parse_commit(head_of_epoch);\n+\n+       for (next = head_of_epoch; next && next->parents && !ret && !stop;) {\n+\n+               struct commit *base = NULL;\n+\n+               ret = find_next_epoch_boundary(next, &base);\n+               if (ret)\n+                       return ret;\n+\n+               next->object.flags |= MERGE_ORDER_EPOCH_FLAG;\n+               if (base) {\n+                       base->object.flags |= MERGE_ORDER_EPOCH_FLAG;\n+               }\n+\n+               if (HAS_EXACTLY_ONE_PARENT(next)) {\n+\n+                       while (HAS_EXACTLY_ONE_PARENT(next) && !stop && !ret) {\n+                               stop = (*emitter) (next);\n+                               next = next->parents->item;\n+                               ret = parse_commit(next);\n+                       }\n+\n+               } else {\n+\n+                       struct commit_list *stack = NULL;\n+                       sort_first_epoch(next, &stack);\n+                       for (; stack && !stop;) {\n+                               next = pop_commit(&stack);\n+                               if (stack) {\n+                                       stop = (*emitter) (next);\n+                               }\n+                       }\n+                       if (stack) {\n+                               free_commit_list(stack);\n+                       }\n+               }\n+\n+       }\n+\n+       if (next && !stop) {\n+               stop = (*emitter) (next);\n+       }\n+\n+       return 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,12 @@\n+#ifndef EPOCH_H\n+#define EPOCH_H\n+\n+typedef int (*emitter_func) (struct commit *);\n+\n+int sort_in_merge_order(struct commit *head_of_epoch, emitter_func emitter);\n+\n+#define MERGE_ORDER_EPOCH_FLAG (1u<<3)\n+#define MERGE_ORDER_VISIT_FLAG (1u<<4)\n+#define MERGE_ORDER_BREAK_FLAG (1u<<5)\n+\n+#endif                         /* 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        const char *type;\n        struct object_list *refs;\n        struct object_list *attached_deltas;\n+       void *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,5 +1,6 @@\n #include \"cache.h\"\n #include \"commit.h\"\n+#include \"epoch.h\"\n\n #define SEEN           (1u << 0)\n #define INTERESTING    (1u << 1)\n@@ -11,7 +12,8 @@ static const char rev_list_usage[] =\n                      \"  --max-age=epoch\\n\"\n                      \"  --min-age=epoch\\n\"\n                      \"  --header\\n\"\n-                     \"  --pretty\";\n+                     \"  --pretty\\n\"\n+                     \"  --merge-order [ --show-breaks ]\";\n\n static void mark_parents_uninteresting(struct commit *commit)\n {\n@@ -36,18 +38,63 @@ static int everybody_uninteresting(struc\n        return 1;\n }\n\n+static unsigned long max_age = -1;\n+static unsigned long min_age = -1;\n+static int max_count = -1;\n+static int verbose_header = 0, show_parents = 0, pretty_print = 0,\nmerge_order = 0, show_breaks = 0;\n+static const char *prefix = \"\";\n+static int hdr_termination = 0;\n+\n+static int process_commit(struct commit * commit)\n+{\n+       if (commit->object.flags & UNINTERESTING)\n+               return 0;\n+       if (min_age != -1 && (commit->date > min_age))\n+               return 0;\n+       if (max_age != -1 && (commit->date < max_age))\n+               return 1;\n+       if (max_count != -1 && !max_count--)\n+               return 1;\n+\n+        if (!show_breaks) {\n+               printf(\"%s%s\", prefix, sha1_to_hex(commit->object.sha1));\n+               if (show_parents) {\n+                       struct commit_list *parents = commit->parents;\n+                       while (parents) {\n+                               printf(\" %s\",\nsha1_to_hex(parents->item->object.sha1));\n+                               parents = parents->next;\n+                       }\n+               }\n+               putchar('\\n');\n+               if (verbose_header) {\n+                       const char *buf = commit->buffer;\n+                       if (pretty_print) {\n+                               static char pretty_header[16384];\n+                               pretty_print_commit(commit->buffer,\n~0, pretty_header, sizeof(pretty_header));\n+                               buf = pretty_header;\n+                       }\n+                       printf(\"%s%c\", buf, hdr_termination);\n+               }\n+        } else {\n+                char c='|';\n+                if (commit->object.flags & MERGE_ORDER_BREAK_FLAG) {\n+                  c = '^';\n+                } else if (commit->object.flags & MERGE_ORDER_EPOCH_FLAG) {\n+                  c = '=';\n+                }\n+                printf(\"%c %s\\n\", c, sha1_to_hex(commit->object.sha1));\n+        }\n+\n+        return 0;\n+}\n+\n int main(int argc, char **argv)\n {\n        int nr_sha;\n        unsigned char sha1[2][20];\n        struct commit_list *list = NULL;\n        struct commit *commit, *end;\n-       int i, verbose_header = 0, show_parents = 0, pretty_print = 0;\n-       int hdr_termination = 0;\n-       const char *prefix = \"\";\n-       unsigned long max_age = -1;\n-       unsigned long min_age = -1;\n-       int max_count = -1;\n+       int i;\n\n        nr_sha = 0;\n        for (i = 1 ; i < argc; i++) {\n@@ -80,8 +127,16 @@ int main(int argc, char **argv)\n                        show_parents = 1;\n                        continue;\n                }\n+               if (!strncmp(arg, \"--merge-order\", 13)) {\n+                       merge_order = 1;\n+                       continue;\n+               }\n+               if (!strncmp(arg, \"--show-breaks\", 13)) {\n+                       show_breaks = 1;\n+                       continue;\n+               }\n\n-               if (nr_sha > 2 || get_sha1(arg, sha1[nr_sha]))\n+               if (nr_sha > 2 || get_sha1(arg, sha1[nr_sha])||\n(show_breaks && !merge_order))\n                        usage(rev_list_usage);\n                nr_sha++;\n        }\n@@ -118,36 +173,19 @@ int main(int argc, char **argv)\n                } while (list);\n                list = newlist;\n        }\n+\n+       if (!merge_order) {\n+               while (list) {\n+                       struct commit *commit =\npop_most_recent_commit(&list, SEEN);\n+                       if (process_commit(commit)) {\n+                              break;\n+                        }\n+               }\n+        } else {\n+                if (sort_in_merge_order(commit, &process_commit)) {\n+                        die(\"merge order sort failed\\n\");\n+                }\n+        }\n\n-       while (list) {\n-               struct commit *commit = pop_most_recent_commit(&list, SEEN);\n-\n-               if (commit->object.flags & UNINTERESTING)\n-                       continue;\n-               if (min_age != -1 && (commit->date > min_age))\n-                       continue;\n-               if (max_age != -1 && (commit->date < max_age))\n-                       break;\n-               if (max_count != -1 && !max_count--)\n-                       break;\n-               printf(\"%s%s\", prefix, sha1_to_hex(commit->object.sha1));\n-               if (show_parents) {\n-                       struct commit_list *parents = commit->parents;\n-                       while (parents) {\n-                               printf(\" %s\",\nsha1_to_hex(parents->item->object.sha1));\n-                               parents = parents->next;\n-                       }\n-               }\n-               putchar('\\n');\n-               if (verbose_header) {\n-                       const char *buf = commit->buffer;\n-                       if (pretty_print) {\n-                               static char pretty_header[16384];\n-                               pretty_print_commit(commit->buffer,\n~0, pretty_header, sizeof(pretty_header));\n-                               buf = pretty_header;\n-                       }\n-                       printf(\"%s%c\", buf, hdr_termination);\n-               }\n-       }\n        return 0;\n }\ndiff --git a/t/t5000-rev-list.sh b/t/t5000-rev-list.sh\nnew file mode 100755\n--- /dev/null\n+++ b/t/t5000-rev-list.sh\n@@ -0,0 +1,85 @@\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\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)\n+export GIT_COMMITTER_NAME=foobar  # to guarantee that the commit is different\n+a0=$(do_commit $tree -p $root)\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+echo $a4 > .git/HEAD\n+\n+git-rev-list --merge-order --show-breaks HEAD | sed \"$(sed_script)\" >\nactual-merge-order\n+cat > expected-merge-order <<EOF\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+EOF\n+\n+git-rev-list HEAD | check_adjacency | sed \"$(sed_script)\" >\nactual-default-order\n+normal_adjacency_count=$(git-rev-list HEAD | check_adjacency | grep\n-c \"\\^\" | tr -d ' ')\n+merge_order_adjacency_count=$(git-rev-list --merge-order HEAD |\ncheck_adjacency | grep -c \"\\^\" | tr -d ' ')\n+\n+test_expect_success 'Testing that the rev-list has correct number of\nentries' '[ $(git-rev-list HEAD | wc -l) -eq 13 ]'\n+test_expect_success 'Testing that --merge-order produces the correct\nresult' 'diff expected-merge-order actual-merge-order'\n+test_expect_success 'Testing that --merge-order produces as many or\nfewer discontinuities' '[ $merge_order_adjacency_count -le\n$normal_adjacency_count ]'\n+\n+test_done\n\n\n--\nhomepage: http://www.zeta.org.au/~jon/\nblog: http://orwelliantremors.blogspot.com/\n\n\n-- \nhomepage: http://www.zeta.org.au/~jon/\nblog: http://orwelliantremors.blogspot.com/\n"}]}