{"thread":{"id":"811","subject":"[PATCH] Modify git-rev-list ... [ resend to fix whitespace mangle ]","startedAt":"2005-06-02T15:31:03Z","lastAt":"2005-06-03T22:34:31Z","messageCount":2,"participants":["jon@blackcubes.dyndns.org","Jon Seymour"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"4423","messageId":"20050602154957.29316.qmail@blackcubes.dyndns.org","threadId":"811","inReplyTo":null,"subject":"[PATCH] Modify git-rev-list ... [ resend to fix whitespace mangle ]","fromName":"","fromEmail":"jon@blackcubes.dyndns.org","sentAt":null,"receivedAt":"2005-06-02T15:31:03Z","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\tcd t\n\t./t5000-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.\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 \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,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 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+\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 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+\tint ret = 0;\n+\n+\tstruct commit_list *cleaner = NULL;\n+\tstruct commit_list *pending = NULL;\n+\n+\t*boundary = NULL;\n+\n+\t// we inject a mass of 1 unit here\n+\n+\tnew_mass_counter(head, get_one());\n+\n+\tcommit_list_insert(head, &pending);\n+\tcommit_list_insert(head, &cleaner);\n+\n+\twhile (!*boundary && pending && !ret) {\n+\n+\t\tstruct commit *latest = pop_commit(&pending);\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+\n+\t\t\tdivide(init_fraction(&distribution), &latest_node->pending, num_parents);\n+\n+\t\t\tstruct commit_list *parents;\n+\n+\t\t\tfor (parents = latest->parents; parents; parents = parents->next) {\n+\t\t\t\tstruct commit *parent = parents->item;\n+\t\t\t\tstruct mass_counter *parent_node = (struct mass_counter *) parent->object.util;\n+\t\t\t\tif (!parent_node) {\n+\t\t\t\t\tparent_node = new_mass_counter(parent, &distribution);\n+\t\t\t\t\tcommit_list_insert(parent, &cleaner);\n+\t\t\t\t\tinsert_by_date(&pending, parent);\n+\t\t\t\t} else {\n+\t\t\t\t\tif (!compare(&parent_node->pending, get_zero())) {\n+\t\t\t\t\t\tcopy(&parent_node->pending, &distribution);\n+\t\t\t\t\t\tinsert_by_date(&pending, parent);\n+\t\t\t\t\t} else {\n+\t\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}\n+\n+\t\tif (!compare(&latest_node->seen, get_one()) && (latest != head)) {\n+\t\t\t// if this node has seen one unit of mass, it must be the base, so mark\n+\t\t\t// the boundary which will cause the loop to stop.\n+\t\t\t*boundary = latest;\n+\t\t}\n+\n+\t\tcopy(&latest_node->pending, get_zero());\n+\n+\t}\n+\n+\tfor (; cleaner;) {\n+\t\tstruct commit *next = pop_commit(&cleaner);\n+\t\tfree_mass_counter((struct mass_counter *) next->object.util);\n+\t\tnext->object.util = NULL;\n+\t}\n+\n+\tif (pending)\n+\t\tfree_commit_list(pending);\n+\n+\treturn 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, 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+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 & MERGE_ORDER_BREAK_FLAG)) {\n+\t\tif (is_parent_of(top->item, item)) {\n+\t\t\ttop->item->object.flags &= ~MERGE_ORDER_BREAK_FLAG;\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+\tparse_commit(head);\n+\n+\thead->object.flags |= MERGE_ORDER_VISIT_FLAG;\n+\n+\tstruct commit_list *parents;\n+\n+\tstruct commit_list *reversed_parents = NULL;\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+\t}\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+\tfor (; reversed_parents;) {\n+\t\tstruct commit *parent = pop_commit(&reversed_parents);\n+\t\tparse_commit(parent);\n+\t\tif (!(parent->object.flags & MERGE_ORDER_VISIT_FLAG)) {\n+\t\t\tif (parent->object.flags & MERGE_ORDER_EPOCH_FLAG) {\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\tpush_onto_merge_order_stack(stack, parent);\n+\t\t\t\tparent->object.flags |= MERGE_ORDER_VISIT_FLAG;\n+\t\t\t} else {\n+\t\t\t\tsort_first_epoch(parent, stack);\n+\t\t\t\tif (reversed_parents) {\n+\t\t\t\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 |= MERGE_ORDER_BREAK_FLAG;\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+// 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+\tstruct commit *next;\n+\tint ret = 0;\n+\tint stop = 0;\n+\n+\tparse_commit(head_of_epoch);\n+\n+\tfor (next = head_of_epoch; next && next->parents && !ret && !stop;) {\n+\n+\t\tstruct commit *base = NULL;\n+\n+\t\tret = find_next_epoch_boundary(next, &base);\n+\t\tif (ret)\n+\t\t\treturn ret;\n+\n+\t\tnext->object.flags |= MERGE_ORDER_EPOCH_FLAG;\n+\t\tif (base) {\n+\t\t\tbase->object.flags |= MERGE_ORDER_EPOCH_FLAG;\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\tstop = (*emitter) (next);\n+\t\t\t\tnext = next->parents->item;\n+\t\t\t\tret = parse_commit(next);\n+\t\t\t}\n+\n+\t\t} else {\n+\n+\t\t\tstruct commit_list *stack = NULL;\n+\t\t\tsort_first_epoch(next, &stack);\n+\t\t\tfor (; stack && !stop;) {\n+\t\t\t\tnext = pop_commit(&stack);\n+\t\t\t\tif (stack) {\n+\t\t\t\t\tstop = (*emitter) (next);\n+\t\t\t\t}\n+\t\t\t}\n+\t\t\tif (stack) {\n+\t\t\t\tfree_commit_list(stack);\n+\t\t\t}\n+\t\t}\n+\n+\t}\n+\n+\tif (next && !stop) {\n+\t\tstop = (*emitter) (next);\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,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\t\t\t\t/* EPOCH_H */\ndiff --git a/object.h b/object.h\n--- a/object.h\n+++ b/object.h\n@@ -15,6 +15,7 @@ struct object {\n \tconst char *type;\n \tstruct object_list *refs;\n \tstruct object_list *attached_deltas;\n+\tvoid *util;\n };\n \n extern int nr_objs;\ndiff --git a/rev-list.c b/rev-list.c\n--- a/rev-list.c\n+++ b/rev-list.c\n@@ -1,5 +1,6 @@\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@@ -11,7 +12,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 void mark_parents_uninteresting(struct commit *commit)\n {\n@@ -36,18 +38,63 @@ static int everybody_uninteresting(struc\n \treturn 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, merge_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+\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+\t\t\n+        if (!show_breaks) {\n+\t\tprintf(\"%s%s\", prefix, sha1_to_hex(commit->object.sha1));\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+        } 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+\t\t\n+        return 0;\n+}\n+\n int main(int argc, char **argv)\n {\n \tint nr_sha;\n \tunsigned char sha1[2][20];\n \tstruct commit_list *list = NULL;\n \tstruct commit *commit, *end;\n-\tint i, verbose_header = 0, show_parents = 0, pretty_print = 0;\n-\tint hdr_termination = 0;\n-\tconst char *prefix = \"\";\n-\tunsigned long max_age = -1;\n-\tunsigned long min_age = -1;\n-\tint max_count = -1;\n+\tint i;\n \n \tnr_sha = 0;\n \tfor (i = 1 ; i < argc; i++) {\n@@ -80,8 +127,16 @@ 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\tif (nr_sha > 2 || get_sha1(arg, sha1[nr_sha]))\n+\t\tif (nr_sha > 2 || get_sha1(arg, sha1[nr_sha])|| (show_breaks && !merge_order))\n \t\t\tusage(rev_list_usage);\n \t\tnr_sha++;\n \t}\n@@ -118,36 +173,19 @@ int main(int argc, char **argv)\n \t\t} while (list);\n \t\tlist = newlist;\n \t}\n+\t\n+\tif (!merge_order) {\n+\t\twhile (list) {\n+\t\t\tstruct commit *commit = pop_most_recent_commit(&list, SEEN);\t\t\n+\t\t\tif (process_commit(commit)) {\n+\t\t\t       break;\n+                        }\n+\t\t}\n+        } else {\n+                if (sort_in_merge_order(commit, &process_commit)) {\n+                        die(\"merge order sort failed\\n\");\n+                }\n+        }\n \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\tprintf(\"%s%s\", prefix, sha1_to_hex(commit->object.sha1));\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}\n \treturn 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)\" > actual-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)\" > 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 13 ]'\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+test_done\n"},{"id":"4514","messageId":"2cfc40320506031534456c8619@mail.gmail.com","threadId":"811","inReplyTo":"2cfc4032050603153419b72444@mail.gmail.com","subject":"[PATCH] Modify git-rev-list ... [ resend to fix whitespace mangle ]","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-03T22:34:31Z","receivedAt":"2005-06-03T22:34:31Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"On 6/4/05, Junio C Hamano <junkio@cox.net> wrote:\n> I only fast-forwarded over maths on your website about the epoch\n> ordering, but what the patch tries to do sounds right to me.\n>\n> One nitpick request I have is to name its test t6000 series, to\n> match the naming convention Pasky came up with?\n>\n>         First digit tells the family:\n>\n>                 0 - the absolute basics and global stuff\n>                 1 - the basic commands concerning database\n>                 2 - the basic commands concerning the working tree\n>                 3 - the other basic commands (e.g. ls-files)\n>                 4 - the diff commands\n>                 5 - the pull and exporting commands\n>                 6 - the revision tree commands (even e.g. merge-base)\n>\n\nSure. I'll modify the patch and repost.\n\n> Also I wonder what the performance implication of this patch is.\n>\n\nIt actually works quite well. I took some care to make sure the\nalgorithm didn't have to scan the entire tree if you only want part of\nit and is roughly linear in the number of edges it actually processes.\nIt does this by borrowing the original heuristic of a latest date\nfirst scan, and also by accumulating \"work\" to do prior to propagating\nit through the network. This means that most nodes are only visited (a\nsmall-multiple of) once.\n\nOne thing to be aware of is that it does have to scan to epoch\nboundaries which, in the Linux kernel, are spaced an average of 100\ncommits apart. The first time you run it on a cold-cache, the output\npauses for a while after the first few commits. But run it again when\nthe cache is warm and the performance is, IMO, quite ok.\n\nHere are the cold-cache stats on the Linux-2.6 tree which has 1300\ncommits and quite a lot of merges and forks\n\n$ time git-rev-list --merge-order --show-breaks HEAD > out 2>err\n\nreal    0m32.283s\nuser    0m0.135s\nsys     0m0.141s\n\nAnd the warm cache stats:\n\n$ time git-rev-list --merge-order --show-breaks HEAD > out 2>err\n\nreal    0m0.181s\nuser    0m0.119s\nsys     0m0.040s\n\nCompared with the standard algorithm:\n\n$ time git-rev-list HEAD > out 2>err\n\nreal    0m0.112s\nuser    0m0.065s\nsys     0m0.032s\n\nSo, it is perhaps 50-100% slower on a warm-cache than the standard algorithm.\n\njon.\n--\nhomepage: http://www.zeta.org.au/~jon/\nblog: http://orwelliantremors.blogspot.com/\n"}]}