{"thread":{"id":"932","subject":"[PATCH 7/7] Move traversal parts of epoch.[ch] into traversal.[ch]","startedAt":"2005-06-14T02:04:48Z","lastAt":"2005-06-14T02:04:48Z","messageCount":1,"participants":["Jon Seymour"],"isPatch":true,"patchVersion":1,"patchTotal":7},"messages":[{"id":"4936","messageId":"20050614020448.23369.qmail@blackcubes.dyndns.org","threadId":"932","inReplyTo":null,"subject":"[PATCH 7/7] Move traversal parts of epoch.[ch] into traversal.[ch]","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-14T02:04:48Z","receivedAt":"2005-06-14T02:04:48Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"\nThis change splits the non-epoch related parts of\nthe traversal algorithm into traversal.[ch] which\nbecome the public interfaces for the traversal\nalgorithms. The strictly epoch-related code using\nfractions, bignums etc., which are implementation\ndetails of the traversal algorithms are left\nin epoch.[ch]\n\nThis reduces the size of the epoch module thereby\nenhancing the maintainability of both it and the\nnew traversal modules.\n\nSigned-off-by: Jon Seymour <jon.seymour@gmail.com>\n---\n\n Makefile    |    7 +\n epoch.c     |  411 ++---------------------------------------------------------\n epoch.h     |  107 ++++-----------\n rev-list.c  |    2 \n traversal.c |  395 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n traversal.h |   92 +++++++++++++\n 6 files changed, 533 insertions(+), 481 deletions(-)\n\ndiff --git a/Makefile b/Makefile\n--- a/Makefile\n+++ b/Makefile\n@@ -42,9 +42,9 @@ install: $(PROG) $(SCRIPTS)\n \n LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o \\\n \t tag.o delta.o date.o index.o diff-delta.o patch-delta.o entry.o \\\n-\t epoch.o refs.o user.o\n+\t traversal.o refs.o user.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 epoch.h user.h\n+LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h traversal.h user.h\n \n LIB_H += strbuf.h\n LIB_OBJS += strbuf.o\n@@ -140,8 +140,9 @@ 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+traversal.o: $(LIB_H)\n user.o: $(LIB_H)\n+epoch.o: $(LIB_H)\n \n test: all\n \t$(MAKE) -C t/ all\ndiff --git a/epoch.c b/epoch.c\n--- a/epoch.c\n+++ b/epoch.c\n@@ -7,43 +7,29 @@\n  * for some of the algorithms used here.\n  *\n  */\n-#include <stdlib.h>\n+#include \"commit.h\"\n+#include \"epoch.h\"\n /* Provides arbitrary precision integers required to accurately represent\n  * fractional mass: */\n #include <openssl/bn.h>\n \n-#include \"cache.h\"\n-#include \"commit.h\"\n-#include \"epoch.h\"\n+\n+#define ASSERT(x,m,c) /* not currently used - documentation only */\n \n struct fraction {\n \tBIGNUM numerator;\n \tBIGNUM denominator;\n };\n \n+struct mass_counter {\n+\tstruct fraction seen;\n+\tstruct fraction pending;\n+};\n+\n static BN_CTX *context = NULL;\n static struct fraction *one = NULL;\n static struct fraction *zero = NULL;\n \n-#define HAS_EXACTLY_ONE_PARENT(n) ((n)->parents && !(n)->parents->next)\n-#define IS_SEEN(c) ((c)->object.flags & SEEN)\n-#define IS_BASE(c) ((c)->object.flags & BASE)\n-#define IS_LOCAL(c) ((c)->object.flags & LOCAL)\n-\n-/* leave the assertions defined for now, maybe null def them later */\n-#define ASSERT(x,m,c) if (!(x)) { assertion_failed(__LINE__, __FUNCTION__, m, c); } else {}\n-\n-static void assertion_failed(int line, char * function, char * message, struct commit * item)\n-{\n-\tdie(\t\"%s:%d:%s: assertion_failed: %s: commit %s, flags %x\",\n-\t\t__FILE__, \n-\t\tline, \n-\t\tfunction,\n-\t\tmessage,\n-\t\titem ? sha1_to_hex(item->object.sha1) : \"[]\",\n-\t\titem ? item->object.flags : 0xFFFFFFFF);\n-}\n-\t\t\t\n static BN_CTX *get_BN_CTX()\n {\n \tif (!context)\n@@ -168,11 +154,6 @@ static int compare(struct fraction *left\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@@ -196,81 +177,6 @@ static void free_mass_counter(struct mas\n }\n \n /*\n- * This function calls the supplied commit_visitor method, if there is one.\n- */\n-static void visit_commit(struct traversal * traversal, struct commit * commit, int first_visit)\n-{\n-\t/*\n-\t * pre-condition:\n-\t * \tfirst_visit => object.util == NULL\n-\t */\n-\tif (traversal->commit_visitor)\n-\t\t(*(traversal->commit_visitor))(commit, first_visit);\n-}\n-\n-/*\n- * This function is called as each edge in the graph is identified. It \n- * will always be called after visit_commit(...,from, 1). No guarantees\n- * are offered about when this call will be made w.r.t. to the call\n- * to visit_commit(..., to, 1)\n- */\n-static void visit_edge(struct traversal * traversal, struct commit * from, struct commit * to)\n-{\n-\t/*\n-\t * pre-condition:\n-\t * \tfrom->object.flags & SEEN &&\n-\t * \tto->object.util => (to->object.flags & SEEN)\n-\t */ \n-\tif (traversal->edge_visitor)\n-\t\t(*(traversal->edge_visitor))(from, to);\n-}\n-\n-/*\n- * This function is called exactly once for each commit discovered during\n- * the merge order traversal. If it ever returns a non-zero value, the\n- * merge order traversal will not continue past the current epoch boundary.\n- * It may, however, continue to emit nodes up until the epoch boundary.\n- * It is the implementer's responsibility to perform output limiting if \n- * that is required.\n- */\n-static int emit_commit(struct traversal * traversal, struct commit * commit)\n-{\n-\treturn (*(traversal->emitter))(commit);\n-}\n-\n-/*\n- * Invoke a call back method to allow the tactics to release and storage\n- * allocated during a previous visit_commit or visit_edge call.\n- */\n-static void clean_commit(struct traversal * traversal, struct commit * commit)\n-{\n-\tif (traversal->clean)\n-\t\t(*(traversal->clean))(commit);\n-\tcommit->object.util = NULL;\n-\tcommit->object.flags &= ~(TRAVERSAL_FLAGS);\n-\t/*\n-\t * post-condition:\n-\t * \tcommit->object.util == NULL && !(commit->object.flag & TRAVERSAL_FLAGS)\n-\t */\t\t\n-}\n-\n-/**\n- * Ask the tactics if we should traverse into the epoch headed at head.\n- */\n-static int continue_traversal(struct traversal * traversal, struct commit * head)\n-{\n-\tif (traversal->continue_traversal)\n-\t\treturn (*(traversal->continue_traversal))(head);\n-\telse\n-\t\treturn 1;\n-}\n-\n-void init_traversal(struct traversal * traversal)\n-{\n-\tmemset(traversal, 0, sizeof(*traversal));\n-}\n-\n-/*\n  * Finds the base commit of a list of commits.\n  *\n  * One property of the commit being searched for is that every commit reachable\n@@ -307,7 +213,7 @@ void init_traversal(struct traversal * t\n  * non-zero if, and only if, there was a problem parsing one of the\n  * commits discovered during the traversal.\n  */\n-static int find_base_for_list(struct commit_list *list, struct commit **boundary)\n+int find_base_for_list(struct commit_list *list, struct commit **boundary)\n {\n \tint ret = 0;\n \tstruct commit_list *cleaner = NULL;\n@@ -320,10 +226,10 @@ static int find_base_for_list(struct com\n \t\tstruct commit *item = list->item;\n \n \t\tASSERT(!item->object.util, \"no duplicates in list\", item);\n-\t\tnew_mass_counter(list->item, get_one());\n+\t\tnew_mass_counter(item, get_one());\n \t\tinc(&injected, get_one());\n-\t\tcommit_list_insert(list->item, &cleaner);\n-\t\tcommit_list_insert(list->item, &pending);\n+\t\tcommit_list_insert(item, &cleaner);\n+\t\tcommit_list_insert(item, &pending);\n \t}\n \twhile (!*boundary && pending && !ret) {\n \t\tstruct commit *latest = pop_commit(&pending);\n@@ -378,7 +284,7 @@ static int find_base_for_list(struct com\n  * Finds the base of an minimal, non-linear epoch, headed at head, by\n  * applying the find_base_for_list to a list consisting of the parents\n  */\n-static int find_base(struct commit *head, struct commit **boundary)\n+int find_base(struct commit *head, struct commit **boundary)\n {\n \tint ret = 0;\n \tstruct commit_list *pending = NULL;\n@@ -397,7 +303,7 @@ static int find_base(struct commit *head\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-static int find_next_epoch_boundary(struct commit *head_of_epoch, struct commit **boundary)\n+int find_next_epoch_boundary(struct commit *head_of_epoch, struct commit **boundary)\n {\n \tstruct commit *item = head_of_epoch;\n \tint ret;\n@@ -424,290 +330,3 @@ static int find_next_epoch_boundary(stru\n \t}\n \treturn ret;\n }\n-\n-/*\n- * Sort the epoch in (adjusted) merge order.\n- */\n-static void sort_unvisited(\n-\tstruct commit *head, \n-\tstruct commit_list **stack, \n-\tstruct traversal * traversal)\n-{\n-\tstruct commit_list *parents = NULL;\n-        struct commit * top = *stack?(*stack)->item:NULL;\n-\n-\tif (IS_SEEN(head)) {\n-\t\tif (!IS_BASE(head)) {\n-\t\t\tvisit_commit(traversal, head, 0);\n-\t\t}\n-\t\treturn;\n-\t}\n-\thead->object.flags |= SEEN;\n-        if (IS_BASE(head)) {\n-\t\tASSERT(!top, \"stack empty on visit to base\", head);\n-\t} else {\n-\t\tif (!head->object.util) {\n-                        parents = copy_parents_in_header_order(head);\n-\t\t} else {\n-\t\t\tparents = (struct commit_list *)head->object.util;\n-                        head->object.util = NULL;\n-\t\t}\n-\t\tvisit_commit(traversal, head, 1);\n-\t\twhile (parents) {\n-\t\t\tstruct commit *parent = pop_commit(&parents);\n-\n-\t\t\tvisit_edge(traversal, head, parent);\n-\t\t\tsort_unvisited(parent, stack, traversal);\n-\t\t}\t\t\n-\t\tcommit_list_insert(head, stack);\t\n-        }\n-}\n-\n-/*\n- * Emit the contents of the stack.\n- * The stack is freed and replaced by NULL.\n- * Sets the return value to STOP if the traversal should stop.\n- */\n-static int emit_stack(struct commit_list **stack, struct traversal * traversal)\n-{\n-\tint stop = 0;\n-\n-\twhile (*stack) {\n-\t\tstruct commit *next = pop_commit(stack);\n-\t\t\n-\t\tstop = stop || (emit_commit(traversal, next)==STOP);\n-\t\tclean_commit(traversal, next);\n-\t}\n-\treturn stop ? STOP : CONTINUE;\n-}\n-\n-/*\n- * Copy the parents of the commit and store the head of the list\n- * in object.util. Return the address of object.util itself.\n- */\n-static struct commit_list ** copy_and_store_parents(struct commit * commit)\n-{\n-\tstruct commit_list * copied=copy_parents_in_header_order(commit);\n-\n-        commit->object.util = copied;\n-\treturn (struct commit_list **)&commit->object.util;\n-}\n-\n-/*\n- * Sort a list of commits in local first order. A commit is \"local\" \n- * if any of its ancestors (except the base) causes (*local_test)() to \n- * return a non-zero value.\n- *\n- * The sorted list is returned in *sorted. A side effect of this function \n- * is to set each object.util pointer in each ancestor up until the base \n- * to a list of parents is sorted in local first order.\n- *\n- * Does nothing if the list is empty.\n- * \n- * The return value contains LOCAL if any of the list is local or had a \n- * local ancestor.\n- */\n-static unsigned int sort_local_branches_first(struct commit_list ** list, struct traversal * traversal)\n-{\n-\tstruct commit_list *local = NULL;\n-\tstruct commit_list **local_tail = &local;\n-\tstruct commit_list **non_local_ptr;\n-\n-\tASSERT(traversal->local_test, \"local_test method is defined\", NULL);\n-\tif (!*list) {\n-\t\treturn 0;\n-\t}\n-\tfor (non_local_ptr = list; *non_local_ptr; ) {\n-\t\tstruct commit *item = (*non_local_ptr)->item;\n-\t\t\n-\t\t/*\n-\t\t * We don't descend past the base or visit\n-\t\t * a commit we have already visited.\n-                 */\n-\t\tif (!IS_BASE(item) && !item->object.util) {\n-\t\t\tstruct commit_list ** copied;\n-\t\t\t\n-\t\t\tif ((*(traversal->local_test)) (item))\n-\t\t\t\titem->object.flags |= LOCAL;\n-\t\t\tcopied=copy_and_store_parents(item);\n-\t\t\titem->object.flags \n-\t\t\t    |= sort_local_branches_first(copied, traversal);\n-\t\t}\n-\t\t/**\n-\t\t * Move local items onto their own list.\n-                 */\n-\t\tif (IS_LOCAL(item))\n-\t\t\tlocal_tail = move_commit(local_tail, non_local_ptr);\n-\t\telse\n-\t\t\tnon_local_ptr = &(*non_local_ptr)->next;\n-\t}\n-\t/*\n-         * Splice the non-local list onto the end of the local\n-         * list, set head of the list to the head of the local list\n-         * return if the LOCAL flag set if we have any local branches\n-         */\n-        *local_tail = *list;\n-        *list = local;\n-\treturn ((*list)->item->object.flags & LOCAL);\n-}\n-\n-/*\n- * Sorting a maximal linear epoch involves traversing until we\n- * reach the base and emitting as we go. We don't emit the base\n- * now.\n- */\n-static int sort_maximal_linear_epoch(struct commit *head, struct traversal * traversal)\n-{\n-\tstruct commit * next;\n-\tint stop = 0;\n-\t\n-\t/* invoke the visitors, if any */\n-\tif (traversal->commit_visitor || traversal->edge_visitor) {\n-\t\tfor (next = head; !IS_BASE(next); next = next->parents->item) {\n-\t\t\tvisit_commit(traversal, next, 1);\n-\t\t\tvisit_edge(traversal, next, next->parents->item);\n-\t\t}\n-\t}\t\t\n-\t/* now emit the nodes, and mark the base*/\n-\tfor (next = head; !IS_BASE(next); next = next->parents->item) {\n-\t\tstop = stop || (emit_commit(traversal, next)==STOP);\n-\t\tclean_commit(traversal, next);\n-\t}\n-\treturn stop ? STOP : CONTINUE;\n-}\n-\n-/*\n- * Sorting a minimal non-linear epoch involves recursively apply\n- * sort_unvisited after doing a local_branches_first sort to the\n- * parents of each commit in the epoch, if required, then emitting\n- * the stack.\n- */\n-static int sort_minimal_non_linear_epoch(struct commit *head, struct traversal * traversal)\n-{\n-\tstruct commit_list *stack = NULL;\t\n-\n-\tif (traversal->local_test) \n-\t\tsort_local_branches_first(copy_and_store_parents(head),\ttraversal);\n-\tsort_unvisited(head, &stack, traversal);\n-\treturn emit_stack(&stack, traversal);\n-}\n-\n-/*\n- * see epoch.h\n- */\n-int traverse_from_head(struct commit *head, struct traversal * traversal)\n-{\n-\tstruct commit *next = head;\n-\tint ret = 0;\n-\n-\tret = parse_commit(next);\n-\tif (ret) \n-\t\treturn ret; \n-        next->object.flags |= BOUNDARY;\n-\twhile (next && next->parents && continue_traversal(traversal, next)) { \n-\t\tstruct commit *base = NULL;\n-\t\tint next_action = CONTINUE;\n-\n-\t\t/* scan to the base of the current epoch */\n-\t\tret = find_next_epoch_boundary(next, &base);\n-\t\t\n-\t\t/* abort if we detected a parsing error */\n-\t\tif (ret)\n-\t\t\treturn ret; /* parsing failure */\n-\t\t\t\n-\t\t/* mark the new base so we know when to stop sorting */\n-\t\tif (base)\n-\t\t\tbase->object.flags |= (BOUNDARY|BASE);\n-\t\t\t\n-\t\t/* reset flags set by last iteration */\n-\t\tnext->object.flags &= ~(BASE|SEEN);\n-\t\t\n-\t\t/* sort with the optimal algorithm */\n-\t\tif (HAS_EXACTLY_ONE_PARENT(next))\n-\t\t\tnext_action = sort_maximal_linear_epoch(next, traversal);\n-\t\telse\n-\t\t\tnext_action = sort_minimal_non_linear_epoch(next, traversal);\n-\t\t\t\n-\t\t/* stop or iterate */\t\t\t\n-\t\tif (next_action == STOP)\n-\t\t\treturn 0; \n-\t\telse\t\t\t\t\t\n-\t\t\tnext = base;\n-\t}\n-\tif (next) {\n-\t\temit_commit(traversal, next);\n-\t\tclean_commit(traversal, next);\n-\t}\n-\treturn 0;\n-}\n-\n-/*\n- * see epoch.h\n- * Traverses 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\n- * in this subgraph using the sort_unvisited algorithm. Once we have\n- * reached the base we can continue sorting using traverse_from_head.\n- */\n-int traverse_from_list(struct commit_list *list, struct traversal * traversal)\n-{\n-\tstruct commit_list *stack = NULL;\n-\tstruct commit *base;\n-\tint ret = 0;\n-\n-\tif (!traversal) \n-\t\tdie(\"traversal argument must not be null\");\n-\tif (!traversal->emitter)\n-\t\tdie(\"an emitter method must be supplied\");\n-\tif (list->next) {\n-\t\tstruct commit_list * copy=NULL;\n-\n-\t\t/* \n-\t\t * Make a copy of the list we can sort.\n-\t\t */\n-\t\tfor(;list;list=list->next) {\n-\t\t\tcommit_list_insert(list->item, &copy);\n-\t\t}\n-\t\tlist=copy;\n-\n-\t\t/*\n-\t\t * With multiple items to start the search with,\n-\t\t * we first sort the list into local order (if required)\n-\t\t * \n-\t\t * This behaves as if a commit was performed which\n-\t\t * referenced the list as parents. This\n-\t\t * would create a minimal, non-linear epoch.\n-\t\t */\t\t \n-\t\tret = find_base_for_list(list, &base);\n-\t\tif (ret)\n-\t\t\treturn ret; /* parsing failure */\n-\n-\t\t/* mark the termination condition*/\n-\t\tif (base)\n-\t\t\tbase->object.flags |= (BOUNDARY|BASE);\n-\n-\t\t/* sort local branches first, so they print last */\t\t\t\n-\t\tif (traversal->local_test)\n-\t\t\tsort_local_branches_first(&list, traversal);\t\t\t\n-\n-\t\t/* sort the unvisited part of the epoch in merge order */\n-\t\twhile (list)\n-\t\t\tsort_unvisited(pop_commit(&list), &stack, traversal);\n-\t\t\n-\t\t/* output the stack */\n-\t\tif (emit_stack(&stack, traversal) == STOP) \n-\t\t\treturn STOP;\t\t\t\n-\t} else {\n-\t\t/*\n-\t\t * With only one item on the list, we just use\n-\t\t * sort in merge order which handles maximal\n-\t\t * linear epochs as well as minimal, non-linear epochs.\n-\t\t */\n-\t\tbase = list->item;\n-\t} \n-\n-        /* sort the rest with the sort_in_merge_order algorithm. */\n-\tif (base)\n-\t\tret = traverse_from_head(base, traversal);\n-\treturn ret;\n-}\n-\ndiff --git a/epoch.h b/epoch.h\n--- a/epoch.h\n+++ b/epoch.h\n@@ -1,91 +1,38 @@\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 #ifndef EPOCH_H\n #define EPOCH_H\n \n-/**\n- * Flags used by merge order logic and also by rev-list.c\n- */\n-#define SEEN                    (1u<<0)\n-#define BOUNDARY                (SEEN<<1)\n-#define LOCAL                   (BOUNDARY<<1)\n-#define BASE                    (LOCAL<<1)\n-#define LAST_TRAVERSAL_FLAG     (BASE)\n-\n-#define TRAVERSAL_FLAGS         (BOUNDARY|SEEN|LOCAL|BASE)\n-\n-/**\n- * Return codes for emitter method. Also used by rev-list.c\n- */\n-#define STOP           0\n-#define CONTINUE       1\n-#define DO             2\n-\n-struct traversal {\n-\t/*\n-\t * Returns 0 if traversal should stop, non-zero if it should continue.\n-\t */\n-\tint (*emitter)(struct commit *);\n-\n-\t/* \n-\t * Returns non-zero if the commit is regarded \"local\", 0 otherwise.\n-\t */\n-\tint (*local_test)(struct commit *);\n-\n-\t/*\n-\t * If defined, called on each visit to a vertex during the \n-         * sort phase of the traversal. first_visit will be\n-         * non-zero on the first visit, zero otherwise.\n-         *\n-         * object.util is available for use by the visitor.\n-\t */\n-\tvoid (*commit_visitor)(struct commit *, int first_visit);\n-\n-\t/*\n-         * Called at some point prior to visiting 'to' from 'from'.\n-         * commit_visitor will already have been called at least once for \n-         * from node. It may or may not have already been called for the\n-         * to node.\n-\t */\n-\tvoid (*edge_visitor)(struct commit * from, struct commit * to);\n+#include \"cache.h\"\n \n-\t/*\n-         * Called sometime after the emitter function has been called.\n-         * Once this call completes the object.util pointer will be set to NULL.\n-         * Implementers should use this call to free any data structure\n-         * allocated by the commit_visitor method.\n-\t */\n-\tvoid (*clean)(struct commit *);\n+#define HAS_EXACTLY_ONE_PARENT(n) ((n)->parents && !(n)->parents->next)\n \n-\t/*\n-\t * Called at each epoch boundary. Implementers may return\n-\t * non-zero if the traversal into the next epoch should\n-\t * be stopped.\n-\t */\n-\tint (*continue_traversal)(struct commit *);\n-}\n-;\n-\n-/**\n- * Initializes a traversal structure which\n- * may be customized by the caller by overriding any of the method pointers.\n+/*\n+ * Find the next articulation point in the graph\n  */\n-extern void init_traversal(struct traversal *);\n+int find_base_for_list(struct commit_list *list, struct commit **boundary);\n \n-/**\n- * Traverses the commit graph from the commits listed. \n- *\n- * The traversal is performed in (optionally localised) merge order \n- * which is defined by invariants specified in Documentation/git-rev-list.txt\n+/*\n+ * Find the base of the minimal, non-linear epoch headed at head.\n  *\n- * The tactics used during the traversal can be customized\n- * by configuring the traversal structure with appropriately\n- * defined method pointers.\n-\n+ * The base is the first articulation point of the graph reachable from head\n+ * such that the only paths between the head and commits reachable from the \n+ * base are paths that include the base itself.\n  */\n-extern int traverse_from_list(struct commit_list *list, struct traversal * traversal);\n+int find_base(struct commit *head, struct commit **boundary);\n \n-/**\n- * Traverses the commit graph from the head commit listed. In other\n- * respects, like traverse_from_list.\n+/*\n+ * Find the boundary of the next epoch in the unique epoch sequence\n+ * for the graph reachable from head. This is either the\n+ * end of the base of a minimal, non-linear epoch (if head has >1 parents)\n+ * or the end of a maximal, linear epoch (if head has exactly 1 parent)\n  */\n-extern int traverse_from_head(struct commit *head, struct traversal * traversal);\n-#endif\t/* EPOCH_H */\n+int find_next_epoch_boundary(struct commit *head, struct commit **boundary);\n+#endif /* EPOCH_H */\ndiff --git a/rev-list.c b/rev-list.c\n--- a/rev-list.c\n+++ b/rev-list.c\n@@ -1,6 +1,6 @@\n #include \"cache.h\"\n #include \"commit.h\"\n-#include \"epoch.h\"\n+#include \"traversal.h\"\n #include \"user.h\"\n \n #define INTERESTING\t(LAST_TRAVERSAL_FLAG << 1)\ndiff --git a/traversal.c b/traversal.c\nnew file mode 100644\n--- /dev/null\n+++ b/traversal.c\n@@ -0,0 +1,395 @@\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 \"cache.h\"\n+#include \"commit.h\"\n+#include \"traversal.h\"\n+#include \"epoch.h\"\n+\n+#define IS_SEEN(c) ((c)->object.flags & SEEN)\n+#define IS_BASE(c) ((c)->object.flags & BASE)\n+#define IS_LOCAL(c) ((c)->object.flags & LOCAL)\n+\n+/* leave the assertions defined for now, maybe null def them later */\n+#define ASSERT(x,m,c) if (!(x)) { assertion_failed(__LINE__, __FUNCTION__, m, c); } else {}\n+\n+static void assertion_failed(int line, char * function, char * message, struct commit * item)\n+{\n+\tdie(\t\"%s:%d:%s: assertion_failed: %s: commit %s, flags %x\",\n+\t\t__FILE__, \n+\t\tline, \n+\t\tfunction,\n+\t\tmessage,\n+\t\titem ? sha1_to_hex(item->object.sha1) : \"[]\",\n+\t\titem ? item->object.flags : 0xFFFFFFFF);\n+}\n+\t\t\t\n+/*\n+ * This function calls the supplied commit_visitor method, if there is one.\n+ */\n+static void visit_commit(struct traversal * traversal, struct commit * commit, int first_visit)\n+{\n+\t/*\n+\t * pre-condition:\n+\t * \tfirst_visit => object.util == NULL\n+\t */\n+\tif (traversal->commit_visitor)\n+\t\t(*(traversal->commit_visitor))(commit, first_visit);\n+}\n+\n+/*\n+ * This function is called as each edge in the graph is identified. It \n+ * will always be called after visit_commit(...,from, 1). No guarantees\n+ * are offered about when this call will be made w.r.t. to the call\n+ * to visit_commit(..., to, 1)\n+ */\n+static void visit_edge(struct traversal * traversal, struct commit * from, struct commit * to)\n+{\n+\t/*\n+\t * pre-condition:\n+\t * \tfrom->object.flags & SEEN &&\n+\t * \tto->object.util => (to->object.flags & SEEN)\n+\t */ \n+\tif (traversal->edge_visitor)\n+\t\t(*(traversal->edge_visitor))(from, to);\n+}\n+\n+/*\n+ * This function is called exactly once for each commit discovered during\n+ * the merge order traversal. If it ever returns a non-zero value, the\n+ * merge order traversal will not continue past the current epoch boundary.\n+ * It may, however, continue to emit nodes up until the epoch boundary.\n+ * It is the implementer's responsibility to perform output limiting if \n+ * that is required.\n+ */\n+static int emit_commit(struct traversal * traversal, struct commit * commit)\n+{\n+\treturn (*(traversal->emitter))(commit);\n+}\n+\n+/*\n+ * Invoke a call back method to allow the tactics to release and storage\n+ * allocated during a previous visit_commit or visit_edge call.\n+ */\n+static void clean_commit(struct traversal * traversal, struct commit * commit)\n+{\n+\tif (traversal->clean)\n+\t\t(*(traversal->clean))(commit);\n+\tcommit->object.util = NULL;\n+\tcommit->object.flags &= ~(TRAVERSAL_FLAGS);\n+\t/*\n+\t * post-condition:\n+\t * \tcommit->object.util == NULL && !(commit->object.flag & TRAVERSAL_FLAGS)\n+\t */\t\t\n+}\n+\n+/**\n+ * Ask the tactics if we should traverse into the epoch headed at head.\n+ */\n+static int continue_traversal(struct traversal * traversal, struct commit * head)\n+{\n+\tif (traversal->continue_traversal)\n+\t\treturn (*(traversal->continue_traversal))(head);\n+\telse\n+\t\treturn 1;\n+}\n+\n+void init_traversal(struct traversal * traversal)\n+{\n+\tmemset(traversal, 0, sizeof(*traversal));\n+}\n+\n+/*\n+ * Sort the epoch in (adjusted) merge order.\n+ */\n+static void sort_unvisited(\n+\tstruct commit *head, \n+\tstruct commit_list **stack, \n+\tstruct traversal * traversal)\n+{\n+\tstruct commit_list *parents = NULL;\n+        struct commit * top = *stack?(*stack)->item:NULL;\n+\n+\tif (IS_SEEN(head)) {\n+\t\tif (!IS_BASE(head)) {\n+\t\t\tvisit_commit(traversal, head, 0);\n+\t\t}\n+\t\treturn;\n+\t}\n+\thead->object.flags |= SEEN;\n+        if (IS_BASE(head)) {\n+\t\tASSERT(!top, \"stack empty on visit to base\", head);\n+\t} else {\n+\t\tif (!head->object.util) {\n+                        parents = copy_parents_in_header_order(head);\n+\t\t} else {\n+\t\t\tparents = (struct commit_list *)head->object.util;\n+                        head->object.util = NULL;\n+\t\t}\n+\t\tvisit_commit(traversal, head, 1);\n+\t\twhile (parents) {\n+\t\t\tstruct commit *parent = pop_commit(&parents);\n+\n+\t\t\tvisit_edge(traversal, head, parent);\n+\t\t\tsort_unvisited(parent, stack, traversal);\n+\t\t}\t\t\n+\t\tcommit_list_insert(head, stack);\t\n+        }\n+}\n+\n+/*\n+ * Emit the contents of the stack.\n+ * The stack is freed and replaced by NULL.\n+ * Sets the return value to STOP if the traversal should stop.\n+ */\n+static int emit_stack(struct commit_list **stack, struct traversal * traversal)\n+{\n+\tint stop = 0;\n+\n+\twhile (*stack) {\n+\t\tstruct commit *next = pop_commit(stack);\n+\t\t\n+\t\tstop = stop || (emit_commit(traversal, next)==STOP);\n+\t\tclean_commit(traversal, next);\n+\t}\n+\treturn stop ? STOP : CONTINUE;\n+}\n+\n+/*\n+ * Copy the parents of the commit and store the head of the list\n+ * in object.util. Return the address of object.util itself.\n+ */\n+static struct commit_list ** copy_and_store_parents(struct commit * commit)\n+{\n+\tstruct commit_list * copied=copy_parents_in_header_order(commit);\n+\n+        commit->object.util = copied;\n+\treturn (struct commit_list **)&commit->object.util;\n+}\n+\n+/*\n+ * Sort a list of commits in local first order. A commit is \"local\" \n+ * if any of its ancestors (except the base) causes (*local_test)() to \n+ * return a non-zero value.\n+ *\n+ * The sorted list is returned in *sorted. A side effect of this function \n+ * is to set each object.util pointer in each ancestor up until the base \n+ * to a list of parents is sorted in local first order.\n+ *\n+ * Does nothing if the list is empty.\n+ * \n+ * The return value contains LOCAL if any of the list is local or had a \n+ * local ancestor.\n+ */\n+static unsigned int sort_local_branches_first(struct commit_list ** list, struct traversal * traversal)\n+{\n+\tstruct commit_list *local = NULL;\n+\tstruct commit_list **local_tail = &local;\n+\tstruct commit_list **non_local_ptr;\n+\n+\tASSERT(traversal->local_test, \"local_test method is defined\", NULL);\n+\tif (!*list) {\n+\t\treturn 0;\n+\t}\n+\tfor (non_local_ptr = list; *non_local_ptr; ) {\n+\t\tstruct commit *item = (*non_local_ptr)->item;\n+\t\t\n+\t\t/*\n+\t\t * We don't descend past the base or visit\n+\t\t * a commit we have already visited.\n+                 */\n+\t\tif (!IS_BASE(item) && !item->object.util) {\n+\t\t\tstruct commit_list ** copied;\n+\t\t\t\n+\t\t\tif ((*(traversal->local_test)) (item))\n+\t\t\t\titem->object.flags |= LOCAL;\n+\t\t\tcopied=copy_and_store_parents(item);\n+\t\t\titem->object.flags \n+\t\t\t    |= sort_local_branches_first(copied, traversal);\n+\t\t}\n+\t\t/**\n+\t\t * Move local items onto their own list.\n+                 */\n+\t\tif (IS_LOCAL(item))\n+\t\t\tlocal_tail = move_commit(local_tail, non_local_ptr);\n+\t\telse\n+\t\t\tnon_local_ptr = &(*non_local_ptr)->next;\n+\t}\n+\t/*\n+         * Splice the non-local list onto the end of the local\n+         * list, set head of the list to the head of the local list\n+         * return if the LOCAL flag set if we have any local branches\n+         */\n+        *local_tail = *list;\n+        *list = local;\n+\treturn ((*list)->item->object.flags & LOCAL);\n+}\n+\n+/*\n+ * Sorting a maximal linear epoch involves traversing until we\n+ * reach the base and emitting as we go. We don't emit the base\n+ * now.\n+ */\n+static int sort_maximal_linear_epoch(struct commit *head, struct traversal * traversal)\n+{\n+\tstruct commit * next;\n+\tint stop = 0;\n+\t\n+\t/* invoke the visitors, if any */\n+\tif (traversal->commit_visitor || traversal->edge_visitor) {\n+\t\tfor (next = head; !IS_BASE(next); next = next->parents->item) {\n+\t\t\tvisit_commit(traversal, next, 1);\n+\t\t\tvisit_edge(traversal, next, next->parents->item);\n+\t\t}\n+\t}\t\t\n+\t/* now emit the nodes, and mark the base*/\n+\tfor (next = head; !IS_BASE(next); next = next->parents->item) {\n+\t\tstop = stop || (emit_commit(traversal, next)==STOP);\n+\t\tclean_commit(traversal, next);\n+\t}\n+\treturn stop ? STOP : CONTINUE;\n+}\n+\n+/*\n+ * Sorting a minimal non-linear epoch involves recursively apply\n+ * sort_unvisited after doing a local_branches_first sort to the\n+ * parents of each commit in the epoch, if required, then emitting\n+ * the stack.\n+ */\n+static int sort_minimal_non_linear_epoch(struct commit *head, struct traversal * traversal)\n+{\n+\tstruct commit_list *stack = NULL;\t\n+\n+\tif (traversal->local_test) \n+\t\tsort_local_branches_first(copy_and_store_parents(head),\ttraversal);\n+\tsort_unvisited(head, &stack, traversal);\n+\treturn emit_stack(&stack, traversal);\n+}\n+\n+/*\n+ * see commit-graph.h\n+ */\n+int traverse_from_head(struct commit *head, struct traversal * traversal)\n+{\n+\tstruct commit *next = head;\n+\tint ret = 0;\n+\n+\tret = parse_commit(next);\n+\tif (ret) \n+\t\treturn ret; \n+        next->object.flags |= BOUNDARY;\n+\twhile (next && next->parents && continue_traversal(traversal, next)) { \n+\t\tstruct commit *base = NULL;\n+\t\tint next_action = CONTINUE;\n+\n+\t\t/* scan to the base of the current epoch */\n+\t\tret = find_next_epoch_boundary(next, &base);\n+\t\t\n+\t\t/* abort if we detected a parsing error */\n+\t\tif (ret)\n+\t\t\treturn ret; /* parsing failure */\n+\t\t\t\n+\t\t/* mark the new base so we know when to stop sorting */\n+\t\tif (base)\n+\t\t\tbase->object.flags |= (BOUNDARY|BASE);\n+\t\t\t\n+\t\t/* reset flags set by last iteration */\n+\t\tnext->object.flags &= ~(BASE|SEEN);\n+\t\t\n+\t\t/* sort with the optimal algorithm */\n+\t\tif (HAS_EXACTLY_ONE_PARENT(next))\n+\t\t\tnext_action = sort_maximal_linear_epoch(next, traversal);\n+\t\telse\n+\t\t\tnext_action = sort_minimal_non_linear_epoch(next, traversal);\n+\t\t\t\n+\t\t/* stop or iterate */\t\t\t\n+\t\tif (next_action == STOP)\n+\t\t\treturn 0; \n+\t\telse\t\t\t\t\t\n+\t\t\tnext = base;\n+\t}\n+\tif (next) {\n+\t\temit_commit(traversal, next);\n+\t\tclean_commit(traversal, next);\n+\t}\n+\treturn 0;\n+}\n+\n+/*\n+ * see commit-graph.h\n+ *\n+ * Traverses 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\n+ * in this subgraph using the sort_unvisited algorithm. Once we have\n+ * reached the base we can continue sorting using traverse_from_head.\n+ */\n+int traverse_from_list(struct commit_list *list, struct traversal * traversal)\n+{\n+\tstruct commit_list *stack = NULL;\n+\tstruct commit *base;\n+\tint ret = 0;\n+\n+\tif (!traversal) \n+\t\tdie(\"traversal argument must not be null\");\n+\tif (!traversal->emitter)\n+\t\tdie(\"an emitter method must be supplied\");\n+\tif (list->next) {\n+\t\tstruct commit_list * copy=NULL;\n+\n+\t\t/* \n+\t\t * Make a copy of the list we can sort.\n+\t\t */\n+\t\tfor(;list;list=list->next) {\n+\t\t\tcommit_list_insert(list->item, &copy);\n+\t\t}\n+\t\tlist=copy;\n+\n+\t\t/*\n+\t\t * With multiple items to start the search with,\n+\t\t * we first sort the list into local order (if required)\n+\t\t * \n+\t\t * This behaves as if a commit was performed which\n+\t\t * referenced the list as parents. This\n+\t\t * would create a minimal, non-linear epoch.\n+\t\t */\t\t \n+\t\tret = find_base_for_list(list, &base);\n+\t\tif (ret)\n+\t\t\treturn ret; /* parsing failure */\n+\n+\t\t/* mark the termination condition*/\n+\t\tif (base)\n+\t\t\tbase->object.flags |= (BOUNDARY|BASE);\n+\n+\t\t/* sort local branches first, so they print last */\t\t\t\n+\t\tif (traversal->local_test)\n+\t\t\tsort_local_branches_first(&list, traversal);\t\t\t\n+\n+\t\t/* sort the unvisited part of the epoch in merge order */\n+\t\twhile (list)\n+\t\t\tsort_unvisited(pop_commit(&list), &stack, traversal);\n+\t\t\n+\t\t/* output the stack */\n+\t\tif (emit_stack(&stack, traversal) == STOP) \n+\t\t\treturn STOP;\t\t\t\n+\t} else {\n+\t\t/*\n+\t\t * With only one item on the list, we just use\n+\t\t * sort in merge order which handles maximal\n+\t\t * linear epochs as well as minimal, non-linear epochs.\n+\t\t */\n+\t\tbase = list->item;\n+\t} \n+\n+        /* sort the rest with the sort_in_merge_order algorithm. */\n+\tif (base)\n+\t\tret = traverse_from_head(base, traversal);\n+\treturn ret;\n+}\n+\ndiff --git a/traversal.h b/traversal.h\n--- a/traversal.h\n+++ b/traversal.h\n@@ -1 +1,91 @@\n-/* workaround for git-apply issue */\n+#ifndef TRAVERSAL_H\n+#define TRAVERSAL_H\n+\n+/**\n+ * Flags used by merge order logic and also by rev-list.c\n+ */\n+#define SEEN                    (1u<<0)\n+#define BOUNDARY                (SEEN<<1)\n+#define LOCAL                   (BOUNDARY<<1)\n+#define BASE                    (LOCAL<<1)\n+#define LAST_TRAVERSAL_FLAG     (BASE)\n+\n+#define TRAVERSAL_FLAGS         (BOUNDARY|SEEN|LOCAL|BASE)\n+\n+/**\n+ * Return codes for emitter method. Also used by rev-list.c\n+ */\n+#define STOP           0\n+#define CONTINUE       1\n+#define DO             2\n+\n+struct traversal {\n+\t/*\n+\t * Returns 0 if traversal should stop, non-zero if it should continue.\n+\t */\n+\tint (*emitter)(struct commit *);\n+\n+\t/* \n+\t * Returns non-zero if the commit is regarded \"local\", 0 otherwise.\n+\t */\n+\tint (*local_test)(struct commit *);\n+\n+\t/*\n+\t * If defined, called on each visit to a vertex during the \n+         * sort phase of the traversal. first_visit will be\n+         * non-zero on the first visit, zero otherwise.\n+         *\n+         * object.util is available for use by the visitor.\n+\t */\n+\tvoid (*commit_visitor)(struct commit *, int first_visit);\n+\n+\t/*\n+         * Called at some point prior to visiting 'to' from 'from'.\n+         * commit_visitor will already have been called at least once for \n+         * from node. It may or may not have already been called for the\n+         * to node.\n+\t */\n+\tvoid (*edge_visitor)(struct commit * from, struct commit * to);\n+\n+\t/*\n+         * Called sometime after the emitter function has been called.\n+         * Once this call completes the object.util pointer will be set to NULL.\n+         * Implementers should use this call to free any data structure\n+         * allocated by the commit_visitor method.\n+\t */\n+\tvoid (*clean)(struct commit *);\n+\n+\t/*\n+\t * Called at each epoch boundary. Implementers may return\n+\t * non-zero if the traversal into the next epoch should\n+\t * be stopped.\n+\t */\n+\tint (*continue_traversal)(struct commit *);\n+}\n+;\n+\n+/**\n+ * Initializes a traversal structure which\n+ * may be customized by the caller by overriding any of the method pointers.\n+ */\n+extern void init_traversal(struct traversal *);\n+\n+/**\n+ * Traverses the commit graph from the commits listed. \n+ *\n+ * The traversal is performed in (optionally localised) merge order \n+ * which is defined by invariants specified in Documentation/git-rev-list.txt\n+ *\n+ * The tactics used during the traversal can be customized\n+ * by configuring the traversal structure with appropriately\n+ * defined method pointers.\n+\n+ */\n+extern int traverse_from_list(struct commit_list *list, struct traversal * traversal);\n+\n+/**\n+ * Traverses the commit graph from the head commit listed. In other\n+ * respects, like traverse_from_list.\n+ */\n+extern int traverse_from_head(struct commit *head, struct traversal * traversal);\n+#endif\t/* TRAVERSAL_H */\n------------\n"}]}