{"thread":{"id":"931","subject":"[PATCH 5/7] Move knowledge of UNINTERESTING flag into rev-list.c","startedAt":"2005-06-14T02:04:43Z","lastAt":"2005-06-14T02:04:43Z","messageCount":1,"participants":["Jon Seymour"],"isPatch":true,"patchVersion":1,"patchTotal":7},"messages":[{"id":"4934","messageId":"20050614020443.23330.qmail@blackcubes.dyndns.org","threadId":"931","inReplyTo":null,"subject":"[PATCH 5/7] Move knowledge of UNINTERESTING flag into rev-list.c","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-14T02:04:43Z","receivedAt":"2005-06-14T02:04:43Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"\nThis patch moves all knowledge of output limiting into rev-list.c\neven for merge order traversals.\n\nA new method, continue_traversal, is added to the traversal\nstructure to permit tools to control how far into the graph\nthe traversal proceeds.\n\nA future modification will do the same for the DISCONTINUITY\nand DUPCHECK flags and then remove all these flags from the\nepoch.h header.\n\nSigned-off-by: Jon Seymour <jon.seymour@gmail.com>\n---\n\n epoch.c    |  112 ++++++++++++++++++------------------------------------------\n epoch.h    |   14 +++++---\n rev-list.c |   91 +++++++++++++++++++++++++++++++++++++++++++++++--\n 3 files changed, 131 insertions(+), 86 deletions(-)\n\ndiff --git a/epoch.c b/epoch.c\n--- a/epoch.c\n+++ b/epoch.c\n@@ -256,6 +256,17 @@ static void clean_commit(struct traversa\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@@ -417,46 +428,6 @@ static int find_next_epoch_boundary(stru\n }\n \n /*\n- * Marks all interesting, visited commits reachable from this commit\n- * as uninteresting. We stop recursing when we reach the epoch boundary,\n- * an unvisited node or a node that has already been marked uninteresting.\n- *\n- * This doesn't actually mark all ancestors between the start node and the\n- * epoch boundary uninteresting, but does ensure that they will eventually\n- * be marked uninteresting when the main sort_unvisited() traversal\n- * eventually reaches them.\n- */\n-static void mark_ancestors_uninteresting(struct commit *commit)\n-{\n-\tunsigned int flags = commit->object.flags;\n-\tint visited = flags & VISITED;\n-\tint boundary = flags & BOUNDARY;\n-\tint uninteresting = flags & UNINTERESTING;\n-\tstruct commit_list *next;\n-\n-\tcommit->object.flags |= UNINTERESTING;\n-\t/*\n-\t * We only need to recurse if\n-\t *      we are not on the boundary and\n-\t *      we have not already been marked uninteresting and\n-\t *      we have already been visited.\n-\t *\n-\t * The main sort_unvisited traverse will mark unreachable\n-\t * all uninteresting, unvisited parents as they are visited\n-\t * so there is no need to duplicate that traversal here.\n-\t *\n-\t * Similarly, if the commit is already marked uninteresting\n-\t * then either all ancestors have already been marked\n-\t * uninteresting or will be once the sort_unvisited\n-\t * traverse reaches them.\n-\t */\n-\tif (uninteresting || boundary || !visited)\n-\t\treturn;\n-\tfor (next = commit->parents; next; next = next->next)\n-\t\tmark_ancestors_uninteresting(next->item);\n-}\n-\n-/*\n  * Sort the epoch in (adjusted) merge order.\n  */\n static void sort_unvisited(\n@@ -487,9 +458,6 @@ static void sort_unvisited(\n \t\twhile (parents) {\n \t\t\tstruct commit *parent = pop_commit(&parents);\n \n-\t\t\tif (IS_UNINTERESTING(head)) {\n-\t\t\t\tmark_ancestors_uninteresting(parent);\n-\t\t\t}\n \t\t\tvisit_edge(traversal, head, parent);\n \t\t\tsort_unvisited(parent, stack, traversal);\n \t\t}\t\t\n@@ -513,7 +481,7 @@ static int emit_stack(struct commit_list\n \twhile (*stack) {\n \t\tstruct commit *next = pop_commit(stack);\n \t\t\n-\t\tstop = (emit_commit(traversal, next)==STOP) || (next->object.flags & UNINTERESTING) || stop ;\n+\t\tstop = stop || (emit_commit(traversal, next)==STOP);\n \t\tclean_commit(traversal, next);\n \t}\n \treturn stop ? STOP : CONTINUE;\n@@ -597,7 +565,6 @@ static unsigned int sort_local_branches_\n static int sort_maximal_linear_epoch(struct commit *head, struct traversal * traversal)\n {\n \tstruct commit * next;\n-\tstruct commit * base;\n \tint stop = 0;\n \t\n \t/* invoke the visitors, if any */\n@@ -609,17 +576,9 @@ static int sort_maximal_linear_epoch(str\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 = (emit_commit(traversal, next)==STOP) || stop;\n-\t\tif (IS_UNINTERESTING(next)) {\n-\t\t\tnext->parents->item->object.flags |= UNINTERESTING;\n-\t\t\tstop = 1;\n-\t\t}\n-\t}\n-\tbase = next;\t\t\n-\t/* then clean the nodes */\n-\tfor (next = head; next != base; next = next->parents->item) \n+\t\tstop = stop || (emit_commit(traversal, next)==STOP);\n \t\tclean_commit(traversal, next);\n-\t\t\n+\t}\n \treturn stop ? STOP : CONTINUE;\n }\n \n@@ -651,7 +610,7 @@ int traverse_from_head(struct commit *he\n \tif (ret) \n \t\treturn ret; \n         next->object.flags |= BOUNDARY;\n-\twhile (next && next->parents) {\n+\twhile (next && next->parents && continue_traversal(traversal, next)) { \n \t\tstruct commit *base = NULL;\n \t\tint next_action = CONTINUE;\n \n@@ -681,8 +640,10 @@ int traverse_from_head(struct commit *he\n \t\telse\t\t\t\t\t\n \t\t\tnext = base;\n \t}\n-\tif (next)\n+\tif (next) {\n \t\temit_commit(traversal, next);\n+\t\tclean_commit(traversal, next);\n+\t}\n \treturn 0;\n }\n \n@@ -696,7 +657,6 @@ int traverse_from_head(struct commit *he\n int traverse_from_list(struct commit_list *list, struct traversal * traversal)\n {\n \tstruct commit_list *stack = NULL;\n-\tstruct commit_list *filtered = NULL;\n \tstruct commit *base;\n \tint ret = 0;\n \n@@ -704,32 +664,26 @@ int traverse_from_list(struct commit_lis\n \t\tdie(\"traversal argument must not be null\");\n \tif (!traversal->emitter)\n \t\tdie(\"an emitter method must be supplied\");\n-\t/**\n-\t * Remove duplicates and uninteresting items.\n-\t * Duplicates are not allowed by find_base_for_list and \n-\t * uninteresting items may prevent us identifying the\n-\t * right type of traversal to do. \n-\t */\n-\tfor (; list; list = list->next) {\n-\t\tstruct commit *next = list->item;\n+\tif (list->next) {\n+\t\tstruct commit_list * copy=NULL;\n \n-\t\tif (!(next->object.flags & (UNINTERESTING|DUPCHECK))) {\n-\t\t\tnext->object.flags |= DUPCHECK;\n-\t\t\tcommit_list_insert(list->item, &filtered);\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}\t\n-\tif (!filtered)\n-\t\tdie(\"no uninteresting heads were specified\\n\");\n-\tif (filtered->next) {\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 filtered list as parents. This\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(filtered, &base);\n+\t\tret = find_base_for_list(list, &base);\n \t\tif (ret)\n \t\t\treturn ret; /* parsing failure */\n \n@@ -739,11 +693,11 @@ int traverse_from_list(struct commit_lis\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(&filtered, traversal);\t\t\t\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 (filtered)\n-\t\t\tsort_unvisited(pop_commit(&filtered), &stack, traversal);\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@@ -754,7 +708,7 @@ int traverse_from_list(struct commit_lis\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 = filtered->item;\n+\t\tbase = list->item;\n \t} \n \n         /* sort the rest with the sort_in_merge_order algorithm. */\ndiff --git a/epoch.h b/epoch.h\n--- a/epoch.h\n+++ b/epoch.h\n@@ -11,16 +11,15 @@\n #define DUPCHECK       (1u<<6)\n #define LOCAL          (1u<<7)\n #define BASE           (1u<<8)\n-#define FORK           (1u<<9)\n \n #define EPOCH_FLAGS (UNINTERESTING|BOUNDARY|VISITED|DISCONTINUITY|DUPCHECK|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+#define STOP           0\n+#define CONTINUE       1\n+#define DO             2\n \n struct traversal {\n \t/*\n@@ -57,6 +56,13 @@ struct traversal {\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 \ndiff --git a/rev-list.c b/rev-list.c\n--- a/rev-list.c\n+++ b/rev-list.c\n@@ -33,6 +33,7 @@ static int show_breaks = 0;\n static char * local_author = NULL;\n static int prune_at_author = 0;\n static int wrt_author = 0;\n+static int stop_traversal = 0;\n \n static void show_commit(struct commit *commit)\n {\n@@ -74,11 +75,19 @@ static int filter_commit(struct commit *\n \treturn DO;\n }\n \n+static int continue_traversal(struct commit * commit)\n+{\n+\treturn !stop_traversal;\n+}\n+\n static int process_commit(struct commit * commit)\n {\n \tint action=filter_commit(commit);\n \n-\tif (action == STOP) {\n+\tif (commit->object.flags & UNINTERESTING)\n+\t\tstop_traversal = 1;\n+\n+\tif (action & STOP) {\n \t\treturn STOP;\n \t}\n \n@@ -177,10 +186,79 @@ static void mark_authors_own_uninteresti\n         }\n }\n \n-static void merge_order_traversal(struct commit_list * list)\n+/*\n+ * Marks all interesting, visited commits reachable from this commit\n+ * as uninteresting. We stop recursing when we reach the epoch boundary,\n+ * an unvisited node or a node that has already been marked uninteresting.\n+ *\n+ * This doesn't actually mark all ancestors between the start node and the\n+ * epoch boundary uninteresting, but does ensure that they will eventually\n+ * be marked uninteresting when the main sort_unvisited() traversal\n+ * eventually reaches them.\n+ */\n+static void mark_ancestors_uninteresting(struct commit * head, struct commit *parent)\n+{\n+\tunsigned int flags, visited, boundary, uninteresting;\n+\tstruct commit_list *next;\n+\n+\tif (!(head->object.flags & UNINTERESTING)) {\n+\t\treturn;\n+\t}\n+\n+\tflags = parent->object.flags;\n+\tvisited = flags & VISITED;\n+\tboundary = flags & BOUNDARY;\n+\tuninteresting = flags & UNINTERESTING;\n+\n+\tparent->object.flags |= UNINTERESTING;\n+\t/*\n+\t * We only need to recurse if\n+\t *      we are not on the boundary and\n+\t *      we have not already been marked uninteresting and\n+\t *      we have already been visited.\n+\t *\n+\t * The main sort_unvisited traverse will mark unreachable\n+\t * all uninteresting, unvisited parents as they are visited\n+\t * so there is no need to duplicate that traversal here.\n+\t *\n+\t * Similarly, if the parent is already marked uninteresting\n+\t * then either all ancestors have already been marked\n+\t * uninteresting or will be once the sort_unvisited\n+\t * traverse reaches them.\n+\t */\n+\tif (uninteresting || boundary || !visited)\n+\t\treturn;\n+\tfor (next = parent->parents; next; next = next->next)\n+\t\tmark_ancestors_uninteresting(parent, next->item);\n+}\n+\n+static void merge_order_traversal(struct commit_list * list, int limited)\n {\n \tstruct traversal traversal;\n+\tstruct commit_list * elided = NULL;\n+\tstruct commit_list ** elided_tail = &elided;\n+        struct commit_list ** ptr=&list;\n+\n+\t/**\n+\t * Remove duplicates and uninteresting items.\n+\t */\n+\tfor (; *ptr; ) {\n+\t\tif ((*ptr)->item->object.flags & (UNINTERESTING|DUPCHECK))\n+\t\t\telided_tail = move_commit(elided_tail, ptr);\n+\t\telse {\n+\t\t\t(*ptr)->item->object.flags |= DUPCHECK;\n+\t\t\tptr = &(*ptr)->next;\n+\t\t}\n+\t}\t\n+\tif (elided) \n+\t\tfree_commit_list(elided);\n+\tif (!list) {\n+\t\tdie(\"all of the specified heads are interesting - nothing to do\");\n+\t}\n \n+\t/*\n+         * Setup the traversal\n+\t */\n \tinit_traversal(&traversal);\n \tif ((prune_at_author|wrt_author) && !local_author) {\n \t\tlocal_author = gitenv(\"GIT_AUTHOR_EMAIL\") ? : NULL;\t\t\t    \n@@ -197,10 +275,17 @@ static void merge_order_traversal(struct\n \t\t    local_author = tmp;\n \t}\t\t \n \ttraversal.emitter = &process_commit;\t\t  \n+\ttraversal.continue_traversal = &continue_traversal;\n+\tif (limited || prune_at_author)\n+\t\ttraversal.edge_visitor = &mark_ancestors_uninteresting;\n \tif (wrt_author)\n \t\ttraversal.local_test = &is_local_author;\n \tif (prune_at_author)\n \t\ttraversal.commit_visitor = &mark_authors_own_uninteresting;\n+\n+\t/*\n+         * Do it.\n+         */\n \tif (traverse_from_list(list, &traversal))\n \t\tdie(\"merge order sort failed\\n\");\n }\n@@ -293,7 +378,7 @@ int main(int argc, char **argv)\n \t\t\tlist = limit_list(list);\n \t\tshow_commit_list(list);\n \t} else {\t\t\n-\t\tmerge_order_traversal(list);\n+\t\tmerge_order_traversal(list, limited);\n \t}\n \n \treturn 0;\n------------\n"}]}