{"thread":{"id":"927","subject":"[PATCH 2/7] Introduce new methods into the epoch_methods structure.","startedAt":"2005-06-14T02:04:36Z","lastAt":"2005-06-14T02:04:36Z","messageCount":1,"participants":["Jon Seymour"],"isPatch":true,"patchVersion":1,"patchTotal":7},"messages":[{"id":"4930","messageId":"20050614020436.23273.qmail@blackcubes.dyndns.org","threadId":"927","inReplyTo":null,"subject":"[PATCH 2/7] Introduce new methods into the epoch_methods structure.","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-06-14T02:04:36Z","receivedAt":"2005-06-14T02:04:36Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"\nThe epoch_methods in epoch.h is modified to include several new methods:\n\nvisit_commit - This method is called during the sort phase of a merge order traversal.\nImplementors may allocate resources and reference them by object.util during this call.\n\nvisit_edge - This method is called each time an edge is visited during the sort phase\nof a merge order traversal.\n\nclean_commit - This method allows implementors to cleanup and release any resources\nallocated during visit_commit.\n\nThis change starts to move responsibility for output limiting back into rev-list.c and\nstarts to generalize epoch.c as a general purpose commit graph traversal algorithm.\n\nsort_list_in_merge_order now clears all flags it uses (masked by EPOCH_FLAGS),\nrather than leaving them in an undefined state as it did previously.\n\nSigned-off-by: Jon Seymour <jon.seymour@gmail.com>\n---\n\n epoch.c    |  145 ++++++++++++++++++++++++++++++++++++++++--------------------\n epoch.h    |   35 ++++++++++++--\n rev-list.c |   66 +++++++++++++++------------\n 3 files changed, 163 insertions(+), 83 deletions(-)\n\ndiff --git a/epoch.c b/epoch.c\n--- a/epoch.c\n+++ b/epoch.c\n@@ -197,17 +197,65 @@ static void free_mass_counter(struct mas\n \tfree(counter);\n }\n \n-static void mark_commit(struct epoch_methods * methods, struct commit * commit)\n+/*\n+ * This function calls the supplied commit_visitor method, if there is one.\n+ */\n+static void visit_commit(struct epoch_methods * methods, struct commit * commit, int first_visit)\n {\n-\tif (methods->marker)\n-\t\t(*(methods->marker))(commit);\n+\t/*\n+\t * pre-condition:\n+\t * \tfirst_visit => object.util == NULL\n+\t */\n+\tif (methods->commit_visitor)\n+\t\t(*(methods->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 epoch_methods * methods, struct commit * from, struct commit * to)\n+{\n+\t/*\n+\t * pre-condition:\n+\t * \tfrom->object.flags & VISITED &&\n+\t * \tto->object.util => (to->object.flags & VISITED)\n+\t */ \n+\tif (methods->edge_visitor)\n+\t\t(*(methods->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 epoch_methods * methods, struct commit * commit)\n {\n \treturn (*(methods->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 epoch_methods * methods, struct commit * commit)\n+{\n+\tif (methods->clean)\n+\t\t(*(methods->clean))(commit);\n+\tcommit->object.util = NULL;\n+\tcommit->object.flags &= ~(EPOCH_FLAGS);\n+\t/*\n+\t * post-condition:\n+\t * \tcommit->object.util == NULL && !(commit->object.flag & EPOCH_FLAGS)\n+\t */\t\t\n+}\n+\n void init_epoch_methods(struct epoch_methods * methods)\n {\n \tmemset(methods, 0, sizeof(*methods));\n@@ -410,7 +458,7 @@ static void mark_ancestors_uninteresting\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 we are already marked uninteresting\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@@ -432,10 +480,13 @@ static void sort_unvisited(\n \tstruct commit_list *parents = NULL;\n         struct commit * top = *stack?(*stack)->item:NULL;\n \n-\tif (IS_VISITED(head)) \n+\tif (IS_VISITED(head)) {\n+\t\tif (!IS_BASE(head)) {\n+\t\t\tvisit_commit(methods, head, 0);\n+\t\t}\n \t\treturn;\n+\t}\n \thead->object.flags |= VISITED;\n-\tmark_commit(methods, head);\n         if (IS_BASE(head)) {\n \t\tASSERT(!top, \"stack empty on visit to base\", head);\n \t} else {\n@@ -445,57 +496,40 @@ static void sort_unvisited(\n \t\t\tparents = (struct commit_list *)head->object.util;\n                         head->object.util = NULL;\n \t\t}\n+\t\tvisit_commit(methods, head, 1);\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(methods, head, parent);\n \t\t\tsort_unvisited(parent, stack, methods);\n \t\t}\t\t\n+\t\ttop=(*stack)?(*stack)->item:NULL;\n+\t\tif (top && !is_parent_of(top, head)) {\n+\t\t\ttop->object.flags |= DISCONTINUITY;\n+\t\t}\t\t\t\n+\t\tcommit_list_insert(head, stack);\t\n         }\n-\ttop=(*stack)?(*stack)->item:NULL;\n-\tif (top && !is_parent_of(top, head)) {\n-\t\ttop->object.flags |= DISCONTINUITY;\n-\t}\t\t\t\n-\tcommit_list_insert(head, stack);\t\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 no further output should be generated.\n+ * Sets the return value to STOP if the traversal should stop.\n  */\n static int emit_stack(struct commit_list **stack, struct epoch_methods * methods)\n {\n-\tunsigned int seen = 0;\n-\tint action = CONTINUE;\n+\tint stop = 0;\n \n-\twhile (*stack && (action != STOP)) {\n+\twhile (*stack) {\n \t\tstruct commit *next = pop_commit(stack);\n-\t\tseen |= next->object.flags;\n-\t\tif (*stack)\n-\t\t\taction = emit_commit(methods, next);\n-\t}\n-\tif (*stack) {\n-\t\tfree_commit_list(*stack);\n-\t\t*stack = NULL;\n-\t}\t\n-\tif (seen & UNINTERESTING) {\n-\t\t/**\n-\t\t * We stop at the base of the stack, rather than\n-\t\t * when we encounter the first UNINTERESTING flag.\n-\t\t * \n-\t\t * The reason is that there may still be interesting stuff \n-\t\t * on the stack but once we reach the base there can be no \n-\t\t * more interesting stuff by definition of what the base \n-\t\t * of an epoch is - everything reachable from the base is \n-\t\t * also reachable from the UNINTERESTING node and hence \n-\t\t * is uninteresting.\n-\t\t */\t\t \n-\t\taction = STOP;\n+\t\t\n+\t\tstop = (emit_commit(methods, next)==STOP) || (next->object.flags & UNINTERESTING) || stop ;\n+\t\tclean_commit(methods, next);\n \t}\n-\treturn action;\n+\treturn stop ? STOP : CONTINUE;\n }\n \n /*\n@@ -558,6 +592,7 @@ static unsigned int sort_local_branches_\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 ((*(methods->local_test)) (item))\n \t\t\t\titem->object.flags |= LOCAL;\n \t\t\tcopied=copy_and_store_parents(item);\n@@ -587,16 +622,33 @@ static unsigned int sort_local_branches_\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 *next, struct epoch_methods * methods)\n+static int sort_maximal_linear_epoch(struct commit *head, struct epoch_methods * methods)\n {\n-\twhile (!IS_BASE(next)) {\n-\t\tmark_commit(methods, next);\t\t\n-\t\tif (!IS_UNINTERESTING(next) && (emit_commit(methods, next) != STOP))\n-\t\t\tnext = next->parents->item;\n-\t\telse\t\t\t\n-\t\t\treturn STOP;\n+\tstruct commit * next;\n+\tstruct commit * base;\n+\tint stop = 0;\n+\t\n+\t/* invoke the visitors, if any */\n+\tif (methods->commit_visitor || methods->edge_visitor) {\n+\t\tfor (next = head; !IS_BASE(next); next = next->parents->item) {\n+\t\t\tvisit_commit(methods, next, 1);\n+\t\t\tvisit_edge(methods, 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 = (emit_commit(methods, 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-\treturn CONTINUE;\n+\tbase = next;\t\t\n+\t/* then clean the nodes */\n+\tfor (next = head; next != base; next = next->parents->item) \n+\t\tclean_commit(methods, next);\n+\t\t\n+\treturn stop ? STOP : CONTINUE;\n }\n \n /*\n@@ -617,9 +669,6 @@ static int sort_minimal_non_linear_epoch\n /*\n  * Sorts an arbitrary epoch into merge order by sorting each epoch\n  * of its epoch sequence into order.\n- *\n- * Note: this algorithm currently leaves traces of its execution in the\n- * object flags of nodes it discovers. This should probably be fixed.\n  */\n static int sort_in_merge_order(struct commit *head, struct epoch_methods * methods)\n {\ndiff --git a/epoch.h b/epoch.h\n--- a/epoch.h\n+++ b/epoch.h\n@@ -11,6 +11,9 @@\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@@ -28,13 +31,33 @@ struct epoch_methods {\n \t * Returns non-zero if the commit is regarded \"local\", 0 otherwise.\n \t */\n \tint (*local_test)(struct commit *);\n-\t/* \n-\t * Implementers may use this method to mark commits uninteresting\n-\t * according to some locally determined criteria. The tree\n-\t * will be pruned at any commit so marked.\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 (*marker)(struct commit *);\n-};\n+\tvoid (*clean)(struct commit *);\n+}\n+;\n \n /**\n  * Initializes an epoch_methods structure which\ndiff --git a/rev-list.c b/rev-list.c\n--- a/rev-list.c\n+++ b/rev-list.c\n@@ -18,7 +18,7 @@ static const char rev_list_usage[] =\n \t\t\t\"  --wrt-author\\n\"\n \t\t\t\"  --prune-at-author\\n\"\n \t\t\t\"  --author=author@domain\\n\"\n-\t\t\t\"  --show-breaks ]\";\n+\t\t\t\"  --show-breaks\";\n \n static int verbose_header = 0;\n static int show_parents = 0;\n@@ -167,9 +167,9 @@ static int is_local_author(struct commit\n \treturn 0;\n }\n \n-static void mark_authors_own_uninteresting(struct commit * commit)\n+static void mark_authors_own_uninteresting(struct commit * commit, int first_visit)\n {\n-        if (is_local_author(commit)) {\n+        if (first_visit && is_local_author(commit)) {\n \t\tstruct commit_list * parents = commit->parents;\n \t\tfor (;parents;parents=parents->next) {\n \t\t\tparents->item->object.flags |= UNINTERESTING;\n@@ -177,6 +177,34 @@ static void mark_authors_own_uninteresti\n         }\n }\n \n+static void merge_order_traversal(struct commit_list * list)\n+{\n+\tstruct epoch_methods methods;\n+\n+\tinit_epoch_methods(&methods);\n+\tif ((prune_at_author|wrt_author) && !local_author) {\n+\t\tlocal_author = gitenv(\"GIT_AUTHOR_EMAIL\") ? : NULL;\t\t\t    \n+\t\tif (!local_author)\n+\t\t\tget_real_identity(&local_author, NULL);\n+\t\telse\n+\t\t\tlocal_author = strdup(local_author);\n+\t}\n+\tif (local_author) {\n+\t\t    /* add delimiters to improve accuracy of match */\n+\t\t    char * tmp=xmalloc(strlen(local_author)+3);\n+\t\t    sprintf(tmp, \"<%s>\", local_author);\n+\t\t    free(local_author);\n+\t\t    local_author = tmp;\n+\t}\t\t \n+\tmethods.emitter = &process_commit;\t\t  \n+\tif (wrt_author)\n+\t\tmethods.local_test = &is_local_author;\n+\tif (prune_at_author)\n+\t\tmethods.commit_visitor = &mark_authors_own_uninteresting;\n+\tif (sort_list_in_merge_order(list, &methods))\n+\t\tdie(\"merge order sort failed\\n\");\n+}\n+\n int main(int argc, char **argv)\n {\n \tstruct commit_list *list = NULL;\n@@ -254,38 +282,18 @@ int main(int argc, char **argv)\n \tif (!list)\n \t\tusage(rev_list_usage);\n \n-        if (!merge_order) \n-        \tmerge_order = wrt_author || prune_at_author || show_breaks;        \t\n+       \tmerge_order = \n+\t\tmerge_order\n+\t\t|| wrt_author \n+\t\t|| prune_at_author \n+\t\t|| show_breaks;\n \n \tif (!merge_order) {\t\t\n \t        if (limited)\n \t\t\tlist = limit_list(list);\n \t\tshow_commit_list(list);\n \t} else {\t\t\n-\t\tstruct epoch_methods methods;\n-\t\n-\t\tinit_epoch_methods(&methods);\n-\t\tif ((prune_at_author|wrt_author) && !local_author) {\n-\t\t\tlocal_author = gitenv(\"GIT_AUTHOR_EMAIL\") ? : NULL;\t\t\t    \n-\t\t\tif (!local_author)\n-\t\t\t\t get_real_identity(&local_author, NULL);\n-\t\t\telse\n-\t\t\t\t local_author = strdup(local_author);\n-\t\t}\t\t\n-\t\tif (local_author) {\n-\t\t\t/* add delimiters to improve accuracy of match */\n-\t\t\tchar * tmp=xmalloc(strlen(local_author)+3);\n-\t\t\tsprintf(tmp, \"<%s>\", local_author);\n-\t\t\tfree(local_author);\n-\t\t\tlocal_author = tmp;\n-\t\t}\t\t \n-\t\tmethods.emitter = &process_commit;\t\t  \n-\t\tif (wrt_author)\n-\t\t\tmethods.local_test = &is_local_author;\n-\t\tif (prune_at_author)\n-\t\t\tmethods.marker = &mark_authors_own_uninteresting;\n-\t\tif (sort_list_in_merge_order(list, &methods))\n-\t\t\tdie(\"merge order sort failed\\n\");\n+\t\tmerge_order_traversal(list);\n \t}\n \n \treturn 0;\n------------\n"}]}