{"thread":{"id":"48802","subject":"[RFC PATCH 00/13] Consolidate reachability logic","startedAt":"2018-06-29T16:12:40Z","lastAt":"2018-06-30T01:40:27Z","messageCount":29,"participants":["Derrick Stolee","Stefan Beller","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":13},"messages":[{"id":"351344","messageId":"20180629161223.229661-1-dstolee@microsoft.com","threadId":"48802","inReplyTo":null,"subject":"[RFC PATCH 00/13] Consolidate reachability logic","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-29T16:12:35Z","receivedAt":"2018-06-29T16:12:40Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"This RFC is a bit unpolished because I was mostly seeing where the idea\ncould go. I wanted to achieve the following:\n\n1. Consolidate several different commit walks into one file\n2. Reduce duplicate reachability logic\n3. Increase testability (correctness and performance)\n4. Improve performance of reachability queries\n\nMy approach is mostly in three parts:\n\n I. Move code to a new commit-reach.c file.\n II. Add a 'test-tool reach' command to test these methods directly.\nIII. Modify the logic by improving performance and calling methods with\n similar logic but different prototypes.\n\nThe 'test-tool reach' command is helpful to make sure I don't break\nanything as I change the logic, but also so I can test methods that are\nnormally only exposed by other more complicated commands. For instance,\nref_newer() is part of 'git push -f' and ok_to_give_up() is buried deep\nwithin fetch negotiation. Both of these methods have some problematic\nperformacne issues that are corrected by this series. As I discovered\nthem, it was clear that it would be better to consolidate walk logic\ninstead of discovering a new walk in another file hidden somewhere.\n\nFor the ok_to_give_up() method, I refactored the method so I could pull\nthe logic out of the depths of fetch negotiation. In the commit\n\"commit-reach: make can_all_from_reach... linear\" I discuss how the\nexisting algorithm is quadratic and how we can make it linear. Also, we\ncan use heuristic knowledge about the shape of the commit graph and the\nusual haves/wants to get some extra performance bonus. (The heuristic is\nto do a DFS with first-parents first, and stop on first found result. We\nexpect haves/wants to include ref tips, which typically have their\nprevious values in their first-parent history.)\n\nThe \"test-reach\" commit in particular is not split well or described\nwell for mailing-list review. I figured I would send the RFC instead of\ntweaking it carefully, because I will need to re-do most of these\nchanges after more of the object-store series is merged. I don't plan to\nsend a v1 patch until the lookup_commit() and parse_commit() code is\nstable again.\n\nThanks,\n-Stolee\n\nDerrick Stolee (13):\n commit-reach: move walk methods from commit.c\n commit-reach: move ref_newer from remote.c\n commit-reach: move commit_contains from ref-filter\n upload-pack: make reachable() more generic\n upload-pack: refactor ok_to_give_up()\n commit-reach: move can_all_from_reach_with_flag()\n test-reach\n test-reach: test reduce_heads()\n commit-reach: test can_all_from_reach\n commit-reach: test is_descendant_of\n commit-reach: make can_all_from_reach... linear\n commit-reach: use is_descendant_of for ref_newer\n commit-reach: use can_all_from_reach\n\n Makefile | 2 +\n builtin/remote.c | 1 +\n commit-reach.c | 656 ++++++++++++++++++++++++++++++++++++++++++\n commit-reach.h | 37 +++\n commit.c | 365 +----------------------\n commit.h | 6 +-\n fast-import.c | 1 +\n fetch-pack.c | 3 +-\n http-push.c | 1 +\n ref-filter.c | 147 +---------\n remote.c | 48 +---\n remote.h | 1 -\n sha1-name.c | 3 +-\n t/helper/test-reach.c | 128 +++++++++\n t/helper/test-tool.c | 1 +\n t/helper/test-tool.h | 1 +\n t/t6600-test-reach.sh | 177 ++++++++++++\n upload-pack.c | 58 +---\n walker.c | 3 +-\n 19 files changed, 1035 insertions(+), 604 deletions(-)\n create mode 100644 commit-reach.c\n create mode 100644 commit-reach.h\n create mode 100644 t/helper/test-reach.c\n create mode 100755 t/t6600-test-reach.sh\n\n\nbase-commit: d4f65b8d141e041eb5e558cd9e763873e29863b9\n-- \n2.18.0.118.gd4f65b8d14\n\n"},{"id":"351345","messageId":"20180629161223.229661-2-dstolee@microsoft.com","threadId":"48802","inReplyTo":"20180629161223.229661-1-dstolee@microsoft.com","subject":"[RFC PATCH 01/13] commit-reach: move walk methods from commit.c","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-29T16:12:37Z","receivedAt":"2018-06-29T16:12:45Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Signed-off-by: Derrick Stolee \n---\n Makefile | 1 +\n commit-reach.c | 359 +++++++++++++++++++++++++++++++++++++++++++++++++\n commit-reach.h | 41 ++++++\n commit.c | 358 ------------------------------------------------\n 4 files changed, 401 insertions(+), 358 deletions(-)\n create mode 100644 commit-reach.c\n create mode 100644 commit-reach.h\n\ndiff --git a/Makefile b/Makefile\nindex 0cb6590f24..89ad873ce0 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -828,6 +828,7 @@ LIB_OBJS += column.o\n LIB_OBJS += combine-diff.o\n LIB_OBJS += commit.o\n LIB_OBJS += commit-graph.o\n+LIB_OBJS += commit-reach.o\n LIB_OBJS += compat/obstack.o\n LIB_OBJS += compat/terminal.o\n LIB_OBJS += config.o\ndiff --git a/commit-reach.c b/commit-reach.c\nnew file mode 100644\nindex 0000000000..1438393165\n--- /dev/null\n+++ b/commit-reach.c\n@@ -0,0 +1,359 @@\n+#include \"cache.h\"\n+#include \"prio-queue.h\"\n+#include \"commit-reach.h\"\n+\n+/* Remember to update object flag allocation in object.h */\n+#define PARENT1 (1u<<16)\n+#define PARENT2 (1u<<17)\n+#define STALE (1u<<18)\n+#define RESULT (1u<<19)\n+\n+static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);\n+\n+static int queue_has_nonstale(struct prio_queue *queue)\n+{\n+\tint i;\n+\tfor (i = 0; i < queue->nr; i++) {\n+\t\tstruct commit *commit = queue->array[i].data;\n+\t\tif (!(commit->object.flags & STALE))\n+\t\t\treturn 1;\n+\t}\n+\treturn 0;\n+}\n+\n+/* all input commits in one and twos[] must have been parsed! */\n+static struct commit_list *paint_down_to_common(struct commit *one, int n,\n+\t\t\t\t\t\tstruct commit **twos,\n+\t\t\t\t\t\tint min_generation)\n+{\n+\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n+\tstruct commit_list *result = NULL;\n+\tint i;\n+\tuint32_t last_gen = GENERATION_NUMBER_INFINITY;\n+\n+\tone->object.flags |= PARENT1;\n+\tif (!n) {\n+\t\tcommit_list_append(one, &result);\n+\t\treturn result;\n+\t}\n+\tprio_queue_put(&queue, one);\n+\n+\tfor (i = 0; i < n; i++) {\n+\t\ttwos[i]->object.flags |= PARENT2;\n+\t\tprio_queue_put(&queue, twos[i]);\n+\t}\n+\n+\twhile (queue_has_nonstale(&queue)) {\n+\t\tstruct commit *commit = prio_queue_get(&queue);\n+\t\tstruct commit_list *parents;\n+\t\tint flags;\n+\n+\t\tif (commit->generation > last_gen)\n+\t\t\tBUG(\"bad generation skip %8x > %8x at %s\",\n+\t\t\t commit->generation, last_gen,\n+\t\t\t oid_to_hex(&commit->object.oid));\n+\t\tlast_gen = commit->generation;\n+\n+\t\tif (commit->generation < min_generation)\n+\t\t\tbreak;\n+\n+\t\tflags = commit->object.flags & (PARENT1 | PARENT2 | STALE);\n+\t\tif (flags == (PARENT1 | PARENT2)) {\n+\t\t\tif (!(commit->object.flags & RESULT)) {\n+\t\t\t\tcommit->object.flags |= RESULT;\n+\t\t\t\tcommit_list_insert_by_date(commit, &result);\n+\t\t\t}\n+\t\t\t/* Mark parents of a found merge stale */\n+\t\t\tflags |= STALE;\n+\t\t}\n+\t\tparents = commit->parents;\n+\t\twhile (parents) {\n+\t\t\tstruct commit *p = parents->item;\n+\t\t\tparents = parents->next;\n+\t\t\tif ((p->object.flags & flags) == flags)\n+\t\t\t\tcontinue;\n+\t\t\tif (parse_commit(p))\n+\t\t\t\treturn NULL;\n+\t\t\tp->object.flags |= flags;\n+\t\t\tprio_queue_put(&queue, p);\n+\t\t}\n+\t}\n+\n+\tclear_prio_queue(&queue);\n+\treturn result;\n+}\n+\n+static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)\n+{\n+\tstruct commit_list *list = NULL;\n+\tstruct commit_list *result = NULL;\n+\tint i;\n+\n+\tfor (i = 0; i < n; i++) {\n+\t\tif (one == twos[i])\n+\t\t\t/*\n+\t\t\t * We do not mark this even with RESULT so we do not\n+\t\t\t * have to clean it up.\n+\t\t\t */\n+\t\t\treturn commit_list_insert(one, &result);\n+\t}\n+\n+\tif (parse_commit(one))\n+\t\treturn NULL;\n+\tfor (i = 0; i < n; i++) {\n+\t\tif (parse_commit(twos[i]))\n+\t\t\treturn NULL;\n+\t}\n+\n+\tlist = paint_down_to_common(one, n, twos, 0);\n+\n+\twhile (list) {\n+\t\tstruct commit *commit = pop_commit(&list);\n+\t\tif (!(commit->object.flags & STALE))\n+\t\t\tcommit_list_insert_by_date(commit, &result);\n+\t}\n+\treturn result;\n+}\n+\n+struct commit_list *get_octopus_merge_bases(struct commit_list *in)\n+{\n+\tstruct commit_list *i, *j, *k, *ret = NULL;\n+\n+\tif (!in)\n+\t\treturn ret;\n+\n+\tcommit_list_insert(in->item, &ret);\n+\n+\tfor (i = in->next; i; i = i->next) {\n+\t\tstruct commit_list *new_commits = NULL, *end = NULL;\n+\n+\t\tfor (j = ret; j; j = j->next) {\n+\t\t\tstruct commit_list *bases;\n+\t\t\tbases = get_merge_bases(i->item, j->item);\n+\t\t\tif (!new_commits)\n+\t\t\t\tnew_commits = bases;\n+\t\t\telse\n+\t\t\t\tend->next = bases;\n+\t\t\tfor (k = bases; k; k = k->next)\n+\t\t\t\tend = k;\n+\t\t}\n+\t\tret = new_commits;\n+\t}\n+\treturn ret;\n+}\n+\n+static int remove_redundant(struct commit **array, int cnt)\n+{\n+\t/*\n+\t * Some commit in the array may be an ancestor of\n+\t * another commit. Move such commit to the end of\n+\t * the array, and return the number of commits that\n+\t * are independent from each other.\n+\t */\n+\tstruct commit **work;\n+\tunsigned char *redundant;\n+\tint *filled_index;\n+\tint i, j, filled;\n+\n+\twork = xcalloc(cnt, sizeof(*work));\n+\tredundant = xcalloc(cnt, 1);\n+\tALLOC_ARRAY(filled_index, cnt - 1);\n+\n+\tfor (i = 0; i < cnt; i++)\n+\t\tparse_commit(array[i]);\n+\tfor (i = 0; i < cnt; i++) {\n+\t\tstruct commit_list *common;\n+\t\tuint32_t min_generation = array[i]->generation;\n+\n+\t\tif (redundant[i])\n+\t\t\tcontinue;\n+\t\tfor (j = filled = 0; j < cnt; j++) {\n+\t\t\tif (i == j || redundant[j])\n+\t\t\t\tcontinue;\n+\t\t\tfilled_index[filled] = j;\n+\t\t\twork[filled++] = array[j];\n+\n+\t\t\tif (array[j]->generation < min_generation)\n+\t\t\t\tmin_generation = array[j]->generation;\n+\t\t}\n+\t\tcommon = paint_down_to_common(array[i], filled, work,\n+\t\t\t\t\t min_generation);\n+\t\tif (array[i]->object.flags & PARENT2)\n+\t\t\tredundant[i] = 1;\n+\t\tfor (j = 0; j < filled; j++)\n+\t\t\tif (work[j]->object.flags & PARENT1)\n+\t\t\t\tredundant[filled_index[j]] = 1;\n+\t\tclear_commit_marks(array[i], all_flags);\n+\t\tclear_commit_marks_many(filled, work, all_flags);\n+\t\tfree_commit_list(common);\n+\t}\n+\n+\t/* Now collect the result */\n+\tCOPY_ARRAY(work, array, cnt);\n+\tfor (i = filled = 0; i < cnt; i++)\n+\t\tif (!redundant[i])\n+\t\t\tarray[filled++] = work[i];\n+\tfor (j = filled, i = 0; i < cnt; i++)\n+\t\tif (redundant[i])\n+\t\t\tarray[j++] = work[i];\n+\tfree(work);\n+\tfree(redundant);\n+\tfree(filled_index);\n+\treturn filled;\n+}\n+\n+static struct commit_list *get_merge_bases_many_0(struct commit *one,\n+\t\t\t\t\t\t int n,\n+\t\t\t\t\t\t struct commit **twos,\n+\t\t\t\t\t\t int cleanup)\n+{\n+\tstruct commit_list *list;\n+\tstruct commit **rslt;\n+\tstruct commit_list *result;\n+\tint cnt, i;\n+\n+\tresult = merge_bases_many(one, n, twos);\n+\tfor (i = 0; i < n; i++) {\n+\t\tif (one == twos[i])\n+\t\t\treturn result;\n+\t}\n+\tif (!result || !result->next) {\n+\t\tif (cleanup) {\n+\t\t\tclear_commit_marks(one, all_flags);\n+\t\t\tclear_commit_marks_many(n, twos, all_flags);\n+\t\t}\n+\t\treturn result;\n+\t}\n+\n+\t/* There are more than one */\n+\tcnt = commit_list_count(result);\n+\trslt = xcalloc(cnt, sizeof(*rslt));\n+\tfor (list = result, i = 0; list; list = list->next)\n+\t\trslt[i++] = list->item;\n+\tfree_commit_list(result);\n+\n+\tclear_commit_marks(one, all_flags);\n+\tclear_commit_marks_many(n, twos, all_flags);\n+\n+\tcnt = remove_redundant(rslt, cnt);\n+\tresult = NULL;\n+\tfor (i = 0; i < cnt; i++)\n+\t\tcommit_list_insert_by_date(rslt[i], &result);\n+\tfree(rslt);\n+\treturn result;\n+}\n+\n+struct commit_list *get_merge_bases_many(struct commit *one,\n+\t\t\t\t\t int n,\n+\t\t\t\t\t struct commit **twos)\n+{\n+\treturn get_merge_bases_many_0(one, n, twos, 1);\n+}\n+\n+struct commit_list *get_merge_bases_many_dirty(struct commit *one,\n+\t\t\t\t\t int n,\n+\t\t\t\t\t struct commit **twos)\n+{\n+\treturn get_merge_bases_many_0(one, n, twos, 0);\n+}\n+\n+struct commit_list *get_merge_bases(struct commit *one, struct commit *two)\n+{\n+\treturn get_merge_bases_many_0(one, 1, &two, 1);\n+}\n+\n+/*\n+ * Is \"commit\" a descendant of one of the elements on the \"with_commit\" list?\n+ */\n+int is_descendant_of(struct commit *commit, struct commit_list *with_commit)\n+{\n+\tif (!with_commit)\n+\t\treturn 1;\n+\twhile (with_commit) {\n+\t\tstruct commit *other;\n+\n+\t\tother = with_commit->item;\n+\t\twith_commit = with_commit->next;\n+\t\tif (in_merge_bases(other, commit))\n+\t\t\treturn 1;\n+\t}\n+\treturn 0;\n+}\n+\n+/*\n+ * Is \"commit\" an ancestor of one of the \"references\"?\n+ */\n+int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit **reference)\n+{\n+\tstruct commit_list *bases;\n+\tint ret = 0, i;\n+\tuint32_t min_generation = GENERATION_NUMBER_INFINITY;\n+\n+\tif (parse_commit(commit))\n+\t\treturn ret;\n+\tfor (i = 0; i < nr_reference; i++) {\n+\t\tif (parse_commit(reference[i]))\n+\t\t\treturn ret;\n+\t\tif (reference[i]->generation < min_generation)\n+\t\t\tmin_generation = reference[i]->generation;\n+\t}\n+\n+\tif (commit->generation > min_generation)\n+\t\treturn ret;\n+\n+\tbases = paint_down_to_common(commit, nr_reference, reference, commit->generation);\n+\tif (commit->object.flags & PARENT2)\n+\t\tret = 1;\n+\tclear_commit_marks(commit, all_flags);\n+\tclear_commit_marks_many(nr_reference, reference, all_flags);\n+\tfree_commit_list(bases);\n+\treturn ret;\n+}\n+\n+/*\n+ * Is \"commit\" an ancestor of (i.e. reachable from) the \"reference\"?\n+ */\n+int in_merge_bases(struct commit *commit, struct commit *reference)\n+{\n+\treturn in_merge_bases_many(commit, 1, &reference);\n+}\n+\n+struct commit_list *reduce_heads(struct commit_list *heads)\n+{\n+\tstruct commit_list *p;\n+\tstruct commit_list *result = NULL, **tail = &result;\n+\tstruct commit **array;\n+\tint num_head, i;\n+\n+\tif (!heads)\n+\t\treturn NULL;\n+\n+\t/* Uniquify */\n+\tfor (p = heads; p; p = p->next)\n+\t\tp->item->object.flags &= ~STALE;\n+\tfor (p = heads, num_head = 0; p; p = p->next) {\n+\t\tif (p->item->object.flags & STALE)\n+\t\t\tcontinue;\n+\t\tp->item->object.flags |= STALE;\n+\t\tnum_head++;\n+\t}\n+\tarray = xcalloc(num_head, sizeof(*array));\n+\tfor (p = heads, i = 0; p; p = p->next) {\n+\t\tif (p->item->object.flags & STALE) {\n+\t\t\tarray[i++] = p->item;\n+\t\t\tp->item->object.flags &= ~STALE;\n+\t\t}\n+\t}\n+\tnum_head = remove_redundant(array, num_head);\n+\tfor (i = 0; i < num_head; i++)\n+\t\ttail = &commit_list_insert(array[i], tail)->next;\n+\tfree(array);\n+\treturn result;\n+}\n+\n+void reduce_heads_replace(struct commit_list **heads)\n+{\n+\tstruct commit_list *result = reduce_heads(*heads);\n+\tfree_commit_list(*heads);\n+\t*heads = result;\n+}\ndiff --git a/commit-reach.h b/commit-reach.h\nnew file mode 100644\nindex 0000000000..244f48c5f2\n--- /dev/null\n+++ b/commit-reach.h\n@@ -0,0 +1,41 @@\n+#ifndef __COMMIT_REACH_H__\n+#define __COMMIT_REACH_H__\n+\n+#include \"commit.h\"\n+\n+struct commit_list *get_merge_bases_many(struct commit *one,\n+\t\t\t\t\t int n,\n+\t\t\t\t\t struct commit **twos);\n+struct commit_list *get_merge_bases_many_dirty(struct commit *one,\n+\t\t\t\t\t int n,\n+\t\t\t\t\t struct commit **twos);\n+struct commit_list *get_merge_bases(struct commit *one, struct commit *two);\n+struct commit_list *get_octopus_merge_bases(struct commit_list *in);\n+\n+/* To be used only when object flags after this call no longer matter */\n+struct commit_list *get_merge_bases_many_dirty(struct commit *one, int n, struct commit **twos);\n+\n+int is_descendant_of(struct commit *commit, struct commit_list *with_commit);\n+int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit **reference);\n+int in_merge_bases(struct commit *commit, struct commit *reference);\n+\n+\n+/*\n+ * Takes a list of commits and returns a new list where those\n+ * have been removed that can be reached from other commits in\n+ * the list. It is useful for, e.g., reducing the commits\n+ * randomly thrown at the git-merge command and removing\n+ * redundant commits that the user shouldn't have given to it.\n+ *\n+ * This function destroys the STALE bit of the commit objects'\n+ * flags.\n+ */\n+struct commit_list *reduce_heads(struct commit_list *heads);\n+\n+/*\n+ * Like `reduce_heads()`, except it replaces the list. Use this\n+ * instead of `foo = reduce_heads(foo);` to avoid memory leaks.\n+ */\n+void reduce_heads_replace(struct commit_list **heads);\n+\n+#endif\ndiff --git a/commit.c b/commit.c\nindex 598cf21cee..d4ddaf4879 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -818,364 +818,6 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so\n \t\tclear_author_date_slab(&author_date);\n }\n \n-/* merge-base stuff */\n-\n-/* Remember to update object flag allocation in object.h */\n-#define PARENT1\t\t(1u<<16)\n-#define PARENT2\t\t(1u<<17)\n-#define STALE\t\t(1u<<18)\n-#define RESULT\t\t(1u<<19)\n-\n-static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);\n-\n-static int queue_has_nonstale(struct prio_queue *queue)\n-{\n-\tint i;\n-\tfor (i = 0; i < queue->nr; i++) {\n-\t\tstruct commit *commit = queue->array[i].data;\n-\t\tif (!(commit->object.flags & STALE))\n-\t\t\treturn 1;\n-\t}\n-\treturn 0;\n-}\n-\n-/* all input commits in one and twos[] must have been parsed! */\n-static struct commit_list *paint_down_to_common(struct commit *one, int n,\n-\t\t\t\t\t\tstruct commit **twos,\n-\t\t\t\t\t\tint min_generation)\n-{\n-\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n-\tstruct commit_list *result = NULL;\n-\tint i;\n-\tuint32_t last_gen = GENERATION_NUMBER_INFINITY;\n-\n-\tone->object.flags |= PARENT1;\n-\tif (!n) {\n-\t\tcommit_list_append(one, &result);\n-\t\treturn result;\n-\t}\n-\tprio_queue_put(&queue, one);\n-\n-\tfor (i = 0; i < n; i++) {\n-\t\ttwos[i]->object.flags |= PARENT2;\n-\t\tprio_queue_put(&queue, twos[i]);\n-\t}\n-\n-\twhile (queue_has_nonstale(&queue)) {\n-\t\tstruct commit *commit = prio_queue_get(&queue);\n-\t\tstruct commit_list *parents;\n-\t\tint flags;\n-\n-\t\tif (commit->generation > last_gen)\n-\t\t\tBUG(\"bad generation skip %8x > %8x at %s\",\n-\t\t\t commit->generation, last_gen,\n-\t\t\t oid_to_hex(&commit->object.oid));\n-\t\tlast_gen = commit->generation;\n-\n-\t\tif (commit->generation < min_generation)\n-\t\t\tbreak;\n-\n-\t\tflags = commit->object.flags & (PARENT1 | PARENT2 | STALE);\n-\t\tif (flags == (PARENT1 | PARENT2)) {\n-\t\t\tif (!(commit->object.flags & RESULT)) {\n-\t\t\t\tcommit->object.flags |= RESULT;\n-\t\t\t\tcommit_list_insert_by_date(commit, &result);\n-\t\t\t}\n-\t\t\t/* Mark parents of a found merge stale */\n-\t\t\tflags |= STALE;\n-\t\t}\n-\t\tparents = commit->parents;\n-\t\twhile (parents) {\n-\t\t\tstruct commit *p = parents->item;\n-\t\t\tparents = parents->next;\n-\t\t\tif ((p->object.flags & flags) == flags)\n-\t\t\t\tcontinue;\n-\t\t\tif (parse_commit(p))\n-\t\t\t\treturn NULL;\n-\t\t\tp->object.flags |= flags;\n-\t\t\tprio_queue_put(&queue, p);\n-\t\t}\n-\t}\n-\n-\tclear_prio_queue(&queue);\n-\treturn result;\n-}\n-\n-static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)\n-{\n-\tstruct commit_list *list = NULL;\n-\tstruct commit_list *result = NULL;\n-\tint i;\n-\n-\tfor (i = 0; i < n; i++) {\n-\t\tif (one == twos[i])\n-\t\t\t/*\n-\t\t\t * We do not mark this even with RESULT so we do not\n-\t\t\t * have to clean it up.\n-\t\t\t */\n-\t\t\treturn commit_list_insert(one, &result);\n-\t}\n-\n-\tif (parse_commit(one))\n-\t\treturn NULL;\n-\tfor (i = 0; i < n; i++) {\n-\t\tif (parse_commit(twos[i]))\n-\t\t\treturn NULL;\n-\t}\n-\n-\tlist = paint_down_to_common(one, n, twos, 0);\n-\n-\twhile (list) {\n-\t\tstruct commit *commit = pop_commit(&list);\n-\t\tif (!(commit->object.flags & STALE))\n-\t\t\tcommit_list_insert_by_date(commit, &result);\n-\t}\n-\treturn result;\n-}\n-\n-struct commit_list *get_octopus_merge_bases(struct commit_list *in)\n-{\n-\tstruct commit_list *i, *j, *k, *ret = NULL;\n-\n-\tif (!in)\n-\t\treturn ret;\n-\n-\tcommit_list_insert(in->item, &ret);\n-\n-\tfor (i = in->next; i; i = i->next) {\n-\t\tstruct commit_list *new_commits = NULL, *end = NULL;\n-\n-\t\tfor (j = ret; j; j = j->next) {\n-\t\t\tstruct commit_list *bases;\n-\t\t\tbases = get_merge_bases(i->item, j->item);\n-\t\t\tif (!new_commits)\n-\t\t\t\tnew_commits = bases;\n-\t\t\telse\n-\t\t\t\tend->next = bases;\n-\t\t\tfor (k = bases; k; k = k->next)\n-\t\t\t\tend = k;\n-\t\t}\n-\t\tret = new_commits;\n-\t}\n-\treturn ret;\n-}\n-\n-static int remove_redundant(struct commit **array, int cnt)\n-{\n-\t/*\n-\t * Some commit in the array may be an ancestor of\n-\t * another commit. Move such commit to the end of\n-\t * the array, and return the number of commits that\n-\t * are independent from each other.\n-\t */\n-\tstruct commit **work;\n-\tunsigned char *redundant;\n-\tint *filled_index;\n-\tint i, j, filled;\n-\n-\twork = xcalloc(cnt, sizeof(*work));\n-\tredundant = xcalloc(cnt, 1);\n-\tALLOC_ARRAY(filled_index, cnt - 1);\n-\n-\tfor (i = 0; i < cnt; i++)\n-\t\tparse_commit(array[i]);\n-\tfor (i = 0; i < cnt; i++) {\n-\t\tstruct commit_list *common;\n-\t\tuint32_t min_generation = array[i]->generation;\n-\n-\t\tif (redundant[i])\n-\t\t\tcontinue;\n-\t\tfor (j = filled = 0; j < cnt; j++) {\n-\t\t\tif (i == j || redundant[j])\n-\t\t\t\tcontinue;\n-\t\t\tfilled_index[filled] = j;\n-\t\t\twork[filled++] = array[j];\n-\n-\t\t\tif (array[j]->generation < min_generation)\n-\t\t\t\tmin_generation = array[j]->generation;\n-\t\t}\n-\t\tcommon = paint_down_to_common(array[i], filled, work,\n-\t\t\t\t\t min_generation);\n-\t\tif (array[i]->object.flags & PARENT2)\n-\t\t\tredundant[i] = 1;\n-\t\tfor (j = 0; j < filled; j++)\n-\t\t\tif (work[j]->object.flags & PARENT1)\n-\t\t\t\tredundant[filled_index[j]] = 1;\n-\t\tclear_commit_marks(array[i], all_flags);\n-\t\tclear_commit_marks_many(filled, work, all_flags);\n-\t\tfree_commit_list(common);\n-\t}\n-\n-\t/* Now collect the result */\n-\tCOPY_ARRAY(work, array, cnt);\n-\tfor (i = filled = 0; i < cnt; i++)\n-\t\tif (!redundant[i])\n-\t\t\tarray[filled++] = work[i];\n-\tfor (j = filled, i = 0; i < cnt; i++)\n-\t\tif (redundant[i])\n-\t\t\tarray[j++] = work[i];\n-\tfree(work);\n-\tfree(redundant);\n-\tfree(filled_index);\n-\treturn filled;\n-}\n-\n-static struct commit_list *get_merge_bases_many_0(struct commit *one,\n-\t\t\t\t\t\t int n,\n-\t\t\t\t\t\t struct commit **twos,\n-\t\t\t\t\t\t int cleanup)\n-{\n-\tstruct commit_list *list;\n-\tstruct commit **rslt;\n-\tstruct commit_list *result;\n-\tint cnt, i;\n-\n-\tresult = merge_bases_many(one, n, twos);\n-\tfor (i = 0; i < n; i++) {\n-\t\tif (one == twos[i])\n-\t\t\treturn result;\n-\t}\n-\tif (!result || !result->next) {\n-\t\tif (cleanup) {\n-\t\t\tclear_commit_marks(one, all_flags);\n-\t\t\tclear_commit_marks_many(n, twos, all_flags);\n-\t\t}\n-\t\treturn result;\n-\t}\n-\n-\t/* There are more than one */\n-\tcnt = commit_list_count(result);\n-\trslt = xcalloc(cnt, sizeof(*rslt));\n-\tfor (list = result, i = 0; list; list = list->next)\n-\t\trslt[i++] = list->item;\n-\tfree_commit_list(result);\n-\n-\tclear_commit_marks(one, all_flags);\n-\tclear_commit_marks_many(n, twos, all_flags);\n-\n-\tcnt = remove_redundant(rslt, cnt);\n-\tresult = NULL;\n-\tfor (i = 0; i < cnt; i++)\n-\t\tcommit_list_insert_by_date(rslt[i], &result);\n-\tfree(rslt);\n-\treturn result;\n-}\n-\n-struct commit_list *get_merge_bases_many(struct commit *one,\n-\t\t\t\t\t int n,\n-\t\t\t\t\t struct commit **twos)\n-{\n-\treturn get_merge_bases_many_0(one, n, twos, 1);\n-}\n-\n-struct commit_list *get_merge_bases_many_dirty(struct commit *one,\n-\t\t\t\t\t int n,\n-\t\t\t\t\t struct commit **twos)\n-{\n-\treturn get_merge_bases_many_0(one, n, twos, 0);\n-}\n-\n-struct commit_list *get_merge_bases(struct commit *one, struct commit *two)\n-{\n-\treturn get_merge_bases_many_0(one, 1, &two, 1);\n-}\n-\n-/*\n- * Is \"commit\" a descendant of one of the elements on the \"with_commit\" list?\n- */\n-int is_descendant_of(struct commit *commit, struct commit_list *with_commit)\n-{\n-\tif (!with_commit)\n-\t\treturn 1;\n-\twhile (with_commit) {\n-\t\tstruct commit *other;\n-\n-\t\tother = with_commit->item;\n-\t\twith_commit = with_commit->next;\n-\t\tif (in_merge_bases(other, commit))\n-\t\t\treturn 1;\n-\t}\n-\treturn 0;\n-}\n-\n-/*\n- * Is \"commit\" an ancestor of one of the \"references\"?\n- */\n-int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit **reference)\n-{\n-\tstruct commit_list *bases;\n-\tint ret = 0, i;\n-\tuint32_t min_generation = GENERATION_NUMBER_INFINITY;\n-\n-\tif (parse_commit(commit))\n-\t\treturn ret;\n-\tfor (i = 0; i < nr_reference; i++) {\n-\t\tif (parse_commit(reference[i]))\n-\t\t\treturn ret;\n-\t\tif (reference[i]->generation < min_generation)\n-\t\t\tmin_generation = reference[i]->generation;\n-\t}\n-\n-\tif (commit->generation > min_generation)\n-\t\treturn ret;\n-\n-\tbases = paint_down_to_common(commit, nr_reference, reference, commit->generation);\n-\tif (commit->object.flags & PARENT2)\n-\t\tret = 1;\n-\tclear_commit_marks(commit, all_flags);\n-\tclear_commit_marks_many(nr_reference, reference, all_flags);\n-\tfree_commit_list(bases);\n-\treturn ret;\n-}\n-\n-/*\n- * Is \"commit\" an ancestor of (i.e. reachable from) the \"reference\"?\n- */\n-int in_merge_bases(struct commit *commit, struct commit *reference)\n-{\n-\treturn in_merge_bases_many(commit, 1, &reference);\n-}\n-\n-struct commit_list *reduce_heads(struct commit_list *heads)\n-{\n-\tstruct commit_list *p;\n-\tstruct commit_list *result = NULL, **tail = &result;\n-\tstruct commit **array;\n-\tint num_head, i;\n-\n-\tif (!heads)\n-\t\treturn NULL;\n-\n-\t/* Uniquify */\n-\tfor (p = heads; p; p = p->next)\n-\t\tp->item->object.flags &= ~STALE;\n-\tfor (p = heads, num_head = 0; p; p = p->next) {\n-\t\tif (p->item->object.flags & STALE)\n-\t\t\tcontinue;\n-\t\tp->item->object.flags |= STALE;\n-\t\tnum_head++;\n-\t}\n-\tarray = xcalloc(num_head, sizeof(*array));\n-\tfor (p = heads, i = 0; p; p = p->next) {\n-\t\tif (p->item->object.flags & STALE) {\n-\t\t\tarray[i++] = p->item;\n-\t\t\tp->item->object.flags &= ~STALE;\n-\t\t}\n-\t}\n-\tnum_head = remove_redundant(array, num_head);\n-\tfor (i = 0; i < num_head; i++)\n-\t\ttail = &commit_list_insert(array[i], tail)->next;\n-\tfree(array);\n-\treturn result;\n-}\n-\n-void reduce_heads_replace(struct commit_list **heads)\n-{\n-\tstruct commit_list *result = reduce_heads(*heads);\n-\tfree_commit_list(*heads);\n-\t*heads = result;\n-}\n-\n static const char gpg_sig_header[] = \"gpgsig\";\n static const int gpg_sig_header_len = sizeof(gpg_sig_header) - 1;\n \n-- \n2.18.0.118.gd4f65b8d14\n\n"},{"id":"351346","messageId":"20180629161223.229661-3-dstolee@microsoft.com","threadId":"48802","inReplyTo":"20180629161223.229661-1-dstolee@microsoft.com","subject":"[RFC PATCH 02/13] commit-reach: move ref_newer from remote.c","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-29T16:12:39Z","receivedAt":"2018-06-29T16:12:48Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Signed-off-by: Derrick Stolee \n---\n builtin/remote.c | 1 +\n commit-reach.c | 52 ++++++++++++++++++++++++++++++++++++++++++++++++\n commit-reach.h | 2 ++\n http-push.c | 1 +\n remote.c | 48 +-------------------------------------------\n remote.h | 1 -\n 6 files changed, 57 insertions(+), 48 deletions(-)\n\ndiff --git a/builtin/remote.c b/builtin/remote.c\nindex 1a82d850a2..341f704ada 100644\n--- a/builtin/remote.c\n+++ b/builtin/remote.c\n@@ -9,6 +9,7 @@\n #include \"refs.h\"\n #include \"refspec.h\"\n #include \"argv-array.h\"\n+#include \"commit-reach.h\"\n \n static const char * const builtin_remote_usage[] = {\n \tN_(\"git remote [-v | --verbose]\"),\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 1438393165..80cdb738f6 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -1,5 +1,10 @@\n #include \"cache.h\"\n+#include \"commit.h\"\n+#include \"decorate.h\"\n #include \"prio-queue.h\"\n+#include \"tree.h\"\n+#include \"revision.h\"\n+#include \"tag.h\"\n #include \"commit-reach.h\"\n \n /* Remember to update object flag allocation in object.h */\n@@ -357,3 +362,50 @@ void reduce_heads_replace(struct commit_list **heads)\n \tfree_commit_list(*heads);\n \t*heads = result;\n }\n+\n+static void unmark_and_free(struct commit_list *list, unsigned int mark)\n+{\n+\twhile (list) {\n+\t\tstruct commit *commit = pop_commit(&list);\n+\t\tcommit->object.flags &= ~mark;\n+\t}\n+}\n+\n+int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)\n+{\n+\tstruct object *o;\n+\tstruct commit *old_commit, *new_commit;\n+\tstruct commit_list *list, *used;\n+\tint found = 0;\n+\n+\t/*\n+\t * Both new_commit and old_commit must be commit-ish and new_commit is descendant of\n+\t * old_commit. Otherwise we require --force.\n+\t */\n+\to = deref_tag(parse_object(old_oid), NULL, 0);\n+\tif (!o || o->type != OBJ_COMMIT)\n+\t\treturn 0;\n+\told_commit = (struct commit *) o;\n+\n+\to = deref_tag(parse_object(new_oid), NULL, 0);\n+\tif (!o || o->type != OBJ_COMMIT)\n+\t\treturn 0;\n+\tnew_commit = (struct commit *) o;\n+\n+\tif (parse_commit(new_commit) < 0)\n+\t\treturn 0;\n+\n+\tused = list = NULL;\n+\tcommit_list_insert(new_commit, &list);\n+\twhile (list) {\n+\t\tnew_commit = pop_most_recent_commit(&list, TMP_MARK);\n+\t\tcommit_list_insert(new_commit, &used);\n+\t\tif (new_commit == old_commit) {\n+\t\t\tfound = 1;\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\tunmark_and_free(list, TMP_MARK);\n+\tunmark_and_free(used, TMP_MARK);\n+\treturn found;\n+}\ndiff --git a/commit-reach.h b/commit-reach.h\nindex 244f48c5f2..35ec9f0ddb 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -38,4 +38,6 @@ struct commit_list *reduce_heads(struct commit_list *heads);\n */\n void reduce_heads_replace(struct commit_list **heads);\n \n+int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);\n+\n #endif\ndiff --git a/http-push.c b/http-push.c\nindex 7e38522098..218315b00b 100644\n--- a/http-push.c\n+++ b/http-push.c\n@@ -13,6 +13,7 @@\n #include \"argv-array.h\"\n #include \"packfile.h\"\n #include \"object-store.h\"\n+#include \"commit-reach.h\"\n \n #ifdef EXPAT_NEEDS_XMLPARSE_H\n #include \ndiff --git a/remote.c b/remote.c\nindex abe80c1397..dcb5a33fac 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -11,6 +11,7 @@\n #include \"string-list.h\"\n #include \"mergesort.h\"\n #include \"argv-array.h\"\n+#include \"commit-reach.h\"\n \n enum map_direction { FROM_SRC, FROM_DST };\n \n@@ -1781,53 +1782,6 @@ int resolve_remote_symref(struct ref *ref, struct ref *list)\n \treturn 1;\n }\n \n-static void unmark_and_free(struct commit_list *list, unsigned int mark)\n-{\n-\twhile (list) {\n-\t\tstruct commit *commit = pop_commit(&list);\n-\t\tcommit->object.flags &= ~mark;\n-\t}\n-}\n-\n-int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)\n-{\n-\tstruct object *o;\n-\tstruct commit *old_commit, *new_commit;\n-\tstruct commit_list *list, *used;\n-\tint found = 0;\n-\n-\t/*\n-\t * Both new_commit and old_commit must be commit-ish and new_commit is descendant of\n-\t * old_commit. Otherwise we require --force.\n-\t */\n-\to = deref_tag(parse_object(old_oid), NULL, 0);\n-\tif (!o || o->type != OBJ_COMMIT)\n-\t\treturn 0;\n-\told_commit = (struct commit *) o;\n-\n-\to = deref_tag(parse_object(new_oid), NULL, 0);\n-\tif (!o || o->type != OBJ_COMMIT)\n-\t\treturn 0;\n-\tnew_commit = (struct commit *) o;\n-\n-\tif (parse_commit(new_commit) < 0)\n-\t\treturn 0;\n-\n-\tused = list = NULL;\n-\tcommit_list_insert(new_commit, &list);\n-\twhile (list) {\n-\t\tnew_commit = pop_most_recent_commit(&list, TMP_MARK);\n-\t\tcommit_list_insert(new_commit, &used);\n-\t\tif (new_commit == old_commit) {\n-\t\t\tfound = 1;\n-\t\t\tbreak;\n-\t\t}\n-\t}\n-\tunmark_and_free(list, TMP_MARK);\n-\tunmark_and_free(used, TMP_MARK);\n-\treturn found;\n-}\n-\n /*\n * Lookup the upstream branch for the given branch and if present, optionally\n * compute the commit ahead/behind values for the pair.\ndiff --git a/remote.h b/remote.h\nindex 45ecc6cefa..56fb9cbb27 100644\n--- a/remote.h\n+++ b/remote.h\n@@ -149,7 +149,6 @@ extern struct ref **get_remote_refs(int fd_out, struct packet_reader *reader,\n \t\t\t\t const struct string_list *server_options);\n \n int resolve_remote_symref(struct ref *ref, struct ref *list);\n-int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);\n \n /*\n * Remove and free all but the first of any entries in the input list\n-- \n2.18.0.118.gd4f65b8d14\n\n"},{"id":"351347","messageId":"20180629161223.229661-4-dstolee@microsoft.com","threadId":"48802","inReplyTo":"20180629161223.229661-1-dstolee@microsoft.com","subject":"[RFC PATCH 03/13] commit-reach: move commit_contains from ref-filter","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-29T16:12:41Z","receivedAt":"2018-06-29T16:12:51Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Signed-off-by: Derrick Stolee \n---\n commit-reach.c | 119 +++++++++++++++++++++++++++++++++++++++\n commit-reach.h | 44 +++++----------\n fast-import.c | 1 +\n ref-filter.c | 147 +++----------------------------------------------\n 4 files changed, 141 insertions(+), 170 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 80cdb738f6..6cfd7379ce 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -409,3 +409,122 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)\n \tunmark_and_free(used, TMP_MARK);\n \treturn found;\n }\n+\n+/*\n+ * Mimicking the real stack, this stack lives on the heap, avoiding stack\n+ * overflows.\n+ *\n+ * At each recursion step, the stack items points to the commits whose\n+ * ancestors are to be inspected.\n+ */\n+struct contains_stack {\n+\tint nr, alloc;\n+\tstruct contains_stack_entry {\n+\t\tstruct commit *commit;\n+\t\tstruct commit_list *parents;\n+\t} *contains_stack;\n+};\n+\n+static int in_commit_list(const struct commit_list *want, struct commit *c)\n+{\n+\tfor (; want; want = want->next)\n+\t\tif (!oidcmp(&want->item->object.oid, &c->object.oid))\n+\t\t\treturn 1;\n+\treturn 0;\n+}\n+\n+/*\n+ * Test whether the candidate is contained in the list.\n+ * Do not recurse to find out, though, but return -1 if inconclusive.\n+ */\n+static enum contains_result contains_test(struct commit *candidate,\n+\t\t\t\t\t const struct commit_list *want,\n+\t\t\t\t\t struct contains_cache *cache,\n+\t\t\t\t\t uint32_t cutoff)\n+{\n+\tenum contains_result *cached = contains_cache_at(cache, candidate);\n+\n+\t/* If we already have the answer cached, return that. */\n+\tif (*cached)\n+\t\treturn *cached;\n+\n+\t/* or are we it? */\n+\tif (in_commit_list(want, candidate)) {\n+\t\t*cached = CONTAINS_YES;\n+\t\treturn CONTAINS_YES;\n+\t}\n+\n+\t/* Otherwise, we don't know; prepare to recurse */\n+\tparse_commit_or_die(candidate);\n+\n+\tif (candidate->generation < cutoff)\n+\t\treturn CONTAINS_NO;\n+\n+\treturn CONTAINS_UNKNOWN;\n+}\n+\n+static void push_to_contains_stack(struct commit *candidate, struct contains_stack *contains_stack)\n+{\n+\tALLOC_GROW(contains_stack->contains_stack, contains_stack->nr + 1, contains_stack->alloc);\n+\tcontains_stack->contains_stack[contains_stack->nr].commit = candidate;\n+\tcontains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents;\n+}\n+\n+static enum contains_result contains_tag_algo(struct commit *candidate,\n+\t\t\t\t\t const struct commit_list *want,\n+\t\t\t\t\t struct contains_cache *cache)\n+{\n+\tstruct contains_stack contains_stack = { 0, 0, NULL };\n+\tenum contains_result result;\n+\tuint32_t cutoff = GENERATION_NUMBER_INFINITY;\n+\tconst struct commit_list *p;\n+\n+\tfor (p = want; p; p = p->next) {\n+\t\tstruct commit *c = p->item;\n+\t\tload_commit_graph_info(c);\n+\t\tif (c->generation < cutoff)\n+\t\t\tcutoff = c->generation;\n+\t}\n+\n+\tresult = contains_test(candidate, want, cache, cutoff);\n+\tif (result != CONTAINS_UNKNOWN)\n+\t\treturn result;\n+\n+\tpush_to_contains_stack(candidate, &contains_stack);\n+\twhile (contains_stack.nr) {\n+\t\tstruct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];\n+\t\tstruct commit *commit = entry->commit;\n+\t\tstruct commit_list *parents = entry->parents;\n+\n+\t\tif (!parents) {\n+\t\t\t*contains_cache_at(cache, commit) = CONTAINS_NO;\n+\t\t\tcontains_stack.nr--;\n+\t\t}\n+\t\t/*\n+\t\t * If we just popped the stack, parents->item has been marked,\n+\t\t * therefore contains_test will return a meaningful yes/no.\n+\t\t */\n+\t\telse switch (contains_test(parents->item, want, cache, cutoff)) {\n+\t\tcase CONTAINS_YES:\n+\t\t\t*contains_cache_at(cache, commit) = CONTAINS_YES;\n+\t\t\tcontains_stack.nr--;\n+\t\t\tbreak;\n+\t\tcase CONTAINS_NO:\n+\t\t\tentry->parents = parents->next;\n+\t\t\tbreak;\n+\t\tcase CONTAINS_UNKNOWN:\n+\t\t\tpush_to_contains_stack(parents->item, &contains_stack);\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\tfree(contains_stack.contains_stack);\n+\treturn contains_test(candidate, want, cache, cutoff);\n+}\n+\n+int commit_contains(struct ref_filter *filter, struct commit *commit,\n+\t\t struct commit_list *list, struct contains_cache *cache)\n+{\n+\tif (filter->with_commit_tag_algo)\n+\t\treturn contains_tag_algo(commit, list, cache) == CONTAINS_YES;\n+\treturn is_descendant_of(commit, list);\n+}\ndiff --git a/commit-reach.h b/commit-reach.h\nindex 35ec9f0ddb..986fb388d5 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -2,42 +2,24 @@\n #define __COMMIT_REACH_H__\n \n #include \"commit.h\"\n+#include \"commit-slab.h\"\n+#include \"ref-filter.h\"\n \n-struct commit_list *get_merge_bases_many(struct commit *one,\n-\t\t\t\t\t int n,\n-\t\t\t\t\t struct commit **twos);\n-struct commit_list *get_merge_bases_many_dirty(struct commit *one,\n-\t\t\t\t\t int n,\n-\t\t\t\t\t struct commit **twos);\n-struct commit_list *get_merge_bases(struct commit *one, struct commit *two);\n-struct commit_list *get_octopus_merge_bases(struct commit_list *in);\n-\n-/* To be used only when object flags after this call no longer matter */\n-struct commit_list *get_merge_bases_many_dirty(struct commit *one, int n, struct commit **twos);\n-\n-int is_descendant_of(struct commit *commit, struct commit_list *with_commit);\n-int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit **reference);\n-int in_merge_bases(struct commit *commit, struct commit *reference);\n-\n+int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);\n \n /*\n- * Takes a list of commits and returns a new list where those\n- * have been removed that can be reached from other commits in\n- * the list. It is useful for, e.g., reducing the commits\n- * randomly thrown at the git-merge command and removing\n- * redundant commits that the user shouldn't have given to it.\n- *\n- * This function destroys the STALE bit of the commit objects'\n- * flags.\n+ * Unknown has to be \"0\" here, because that's the default value for\n+ * contains_cache slab entries that have not yet been assigned.\n */\n-struct commit_list *reduce_heads(struct commit_list *heads);\n+enum contains_result {\n+\tCONTAINS_UNKNOWN = 0,\n+\tCONTAINS_NO,\n+\tCONTAINS_YES\n+};\n \n-/*\n- * Like `reduce_heads()`, except it replaces the list. Use this\n- * instead of `foo = reduce_heads(foo);` to avoid memory leaks.\n- */\n-void reduce_heads_replace(struct commit_list **heads);\n+define_commit_slab(contains_cache, enum contains_result);\n \n-int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);\n+int commit_contains(struct ref_filter *filter, struct commit *commit,\n+\t\t struct commit_list *list, struct contains_cache *cache);\n \n #endif\ndiff --git a/fast-import.c b/fast-import.c\nindex 4d55910ab9..49ce8e8426 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -171,6 +171,7 @@ Format of STDIN stream:\n #include \"packfile.h\"\n #include \"object-store.h\"\n #include \"mem-pool.h\"\n+#include \"commit-reach.h\"\n \n #define PACK_ID_BITS 16\n #define MAX_PACK_ID ((1<next)\n-\t\tif (!oidcmp(&want->item->object.oid, &c->object.oid))\n-\t\t\treturn 1;\n-\treturn 0;\n-}\n-\n-/*\n- * Test whether the candidate is contained in the list.\n- * Do not recurse to find out, though, but return -1 if inconclusive.\n- */\n-static enum contains_result contains_test(struct commit *candidate,\n-\t\t\t\t\t const struct commit_list *want,\n-\t\t\t\t\t struct contains_cache *cache,\n-\t\t\t\t\t uint32_t cutoff)\n-{\n-\tenum contains_result *cached = contains_cache_at(cache, candidate);\n-\n-\t/* If we already have the answer cached, return that. */\n-\tif (*cached)\n-\t\treturn *cached;\n-\n-\t/* or are we it? */\n-\tif (in_commit_list(want, candidate)) {\n-\t\t*cached = CONTAINS_YES;\n-\t\treturn CONTAINS_YES;\n-\t}\n-\n-\t/* Otherwise, we don't know; prepare to recurse */\n-\tparse_commit_or_die(candidate);\n-\n-\tif (candidate->generation < cutoff)\n-\t\treturn CONTAINS_NO;\n-\n-\treturn CONTAINS_UNKNOWN;\n-}\n-\n-static void push_to_contains_stack(struct commit *candidate, struct contains_stack *contains_stack)\n-{\n-\tALLOC_GROW(contains_stack->contains_stack, contains_stack->nr + 1, contains_stack->alloc);\n-\tcontains_stack->contains_stack[contains_stack->nr].commit = candidate;\n-\tcontains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents;\n-}\n-\n-static enum contains_result contains_tag_algo(struct commit *candidate,\n-\t\t\t\t\t const struct commit_list *want,\n-\t\t\t\t\t struct contains_cache *cache)\n-{\n-\tstruct contains_stack contains_stack = { 0, 0, NULL };\n-\tenum contains_result result;\n-\tuint32_t cutoff = GENERATION_NUMBER_INFINITY;\n-\tconst struct commit_list *p;\n-\n-\tfor (p = want; p; p = p->next) {\n-\t\tstruct commit *c = p->item;\n-\t\tload_commit_graph_info(c);\n-\t\tif (c->generation < cutoff)\n-\t\t\tcutoff = c->generation;\n-\t}\n-\n-\tresult = contains_test(candidate, want, cache, cutoff);\n-\tif (result != CONTAINS_UNKNOWN)\n-\t\treturn result;\n-\n-\tpush_to_contains_stack(candidate, &contains_stack);\n-\twhile (contains_stack.nr) {\n-\t\tstruct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];\n-\t\tstruct commit *commit = entry->commit;\n-\t\tstruct commit_list *parents = entry->parents;\n-\n-\t\tif (!parents) {\n-\t\t\t*contains_cache_at(cache, commit) = CONTAINS_NO;\n-\t\t\tcontains_stack.nr--;\n-\t\t}\n-\t\t/*\n-\t\t * If we just popped the stack, parents->item has been marked,\n-\t\t * therefore contains_test will return a meaningful yes/no.\n-\t\t */\n-\t\telse switch (contains_test(parents->item, want, cache, cutoff)) {\n-\t\tcase CONTAINS_YES:\n-\t\t\t*contains_cache_at(cache, commit) = CONTAINS_YES;\n-\t\t\tcontains_stack.nr--;\n-\t\t\tbreak;\n-\t\tcase CONTAINS_NO:\n-\t\t\tentry->parents = parents->next;\n-\t\t\tbreak;\n-\t\tcase CONTAINS_UNKNOWN:\n-\t\t\tpush_to_contains_stack(parents->item, &contains_stack);\n-\t\t\tbreak;\n-\t\t}\n-\t}\n-\tfree(contains_stack.contains_stack);\n-\treturn contains_test(candidate, want, cache, cutoff);\n-}\n-\n-static int commit_contains(struct ref_filter *filter, struct commit *commit,\n-\t\t\t struct commit_list *list, struct contains_cache *cache)\n-{\n-\tif (filter->with_commit_tag_algo)\n-\t\treturn contains_tag_algo(commit, list, cache) == CONTAINS_YES;\n-\treturn is_descendant_of(commit, list);\n-}\n-\n /*\n * Return 1 if the refname matches one of the patterns, otherwise 0.\n * A pattern can be a literal prefix (e.g. a refname \"refs/heads/master\"\n@@ -1984,6 +1846,13 @@ static int filter_ref_kind(struct ref_filter *filter, const char *refname)\n \treturn ref_kind_from_refname(refname);\n }\n \n+struct ref_filter_cbdata {\n+ struct ref_array *array;\n+ struct ref_filter *filter;\n+ struct contains_cache contains_cache;\n+ struct contains_cache no_contains_cache;\n+};\n+\n /*\n * A call-back given to for_each_ref(). Filter refs and keep them for\n * later object processing.\n-- \n2.18.0.118.gd4f65b8d14\n\n"},{"id":"351348","messageId":"20180629161223.229661-5-dstolee@microsoft.com","threadId":"48802","inReplyTo":"20180629161223.229661-1-dstolee@microsoft.com","subject":"[RFC PATCH 04/13] upload-pack: make reachable() more generic","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-29T16:12:45Z","receivedAt":"2018-06-29T16:12:54Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"In anticipation of moving the reachable() method to commit-reach.c,\nmodify the prototype to be more generic to flags known outside of\nupload-pack.c. Also rename 'want' to 'from' to make the statement\nmore clear outside of the context of haves/wants negotiation.\n\nSigned-off-by: Derrick Stolee \n---\n upload-pack.c | 23 +++++++++++------------\n 1 file changed, 11 insertions(+), 12 deletions(-)\n\ndiff --git a/upload-pack.c b/upload-pack.c\nindex 87c6722ea5..95c56dc027 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -28,7 +28,6 @@\n #define OUR_REF\t\t(1u << 12)\n #define WANTED\t\t(1u << 13)\n #define COMMON_KNOWN\t(1u << 14)\n-#define REACHABLE\t(1u << 15)\n \n #define SHALLOW\t\t(1u << 16)\n #define NOT_SHALLOW\t(1u << 17)\n@@ -334,36 +333,36 @@ static int got_oid(const char *hex, struct object_id *oid)\n \treturn 0;\n }\n \n-static int reachable(struct commit *want)\n+static int reachable(struct commit *from, int with_flag, int assign_flag)\n {\n \tstruct prio_queue work = { compare_commits_by_commit_date };\n \n-\tprio_queue_put(&work, want);\n+\tprio_queue_put(&work, from);\n \twhile (work.nr) {\n \t\tstruct commit_list *list;\n \t\tstruct commit *commit = prio_queue_get(&work);\n \n-\t\tif (commit->object.flags & THEY_HAVE) {\n-\t\t\twant->object.flags |= COMMON_KNOWN;\n+\t\tif (commit->object.flags & with_flag) {\n+\t\t\tfrom->object.flags |= assign_flag;\n \t\t\tbreak;\n \t\t}\n \t\tif (!commit->object.parsed)\n \t\t\tparse_object(&commit->object.oid);\n-\t\tif (commit->object.flags & REACHABLE)\n+\t\tif (commit->object.flags & TMP_MARK)\n \t\t\tcontinue;\n-\t\tcommit->object.flags |= REACHABLE;\n+\t\tcommit->object.flags |= TMP_MARK;\n \t\tif (commit->date < oldest_have)\n \t\t\tcontinue;\n \t\tfor (list = commit->parents; list; list = list->next) {\n \t\t\tstruct commit *parent = list->item;\n-\t\t\tif (!(parent->object.flags & REACHABLE))\n+\t\t\tif (!(parent->object.flags & TMP_MARK))\n \t\t\t\tprio_queue_put(&work, parent);\n \t\t}\n \t}\n-\twant->object.flags |= REACHABLE;\n-\tclear_commit_marks(want, REACHABLE);\n+\tfrom->object.flags |= TMP_MARK;\n+\tclear_commit_marks(from, TMP_MARK);\n \tclear_prio_queue(&work);\n-\treturn (want->object.flags & COMMON_KNOWN);\n+\treturn (from->object.flags & assign_flag);\n }\n \n static int ok_to_give_up(void)\n@@ -388,7 +387,7 @@ static int ok_to_give_up(void)\n \t\t\twant_obj.objects[i].item->flags |= COMMON_KNOWN;\n \t\t\tcontinue;\n \t\t}\n-\t\tif (!reachable((struct commit *)want))\n+\t\tif (!reachable((struct commit *)want, THEY_HAVE, COMMON_KNOWN))\n \t\t\treturn 0;\n \t}\n \treturn 1;\n-- \n2.18.0.118.gd4f65b8d14\n\n"},{"id":"351349","messageId":"20180629161223.229661-7-dstolee@microsoft.com","threadId":"48802","inReplyTo":"20180629161223.229661-1-dstolee@microsoft.com","subject":"[RFC PATCH 06/13] commit-reach: move can_all_from_reach_with_flag()","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-29T16:12:53Z","receivedAt":"2018-06-29T16:13:00Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Signed-off-by: Derrick Stolee \n---\n commit-reach.c | 61 +++++++++++++++++++++++++++++++++++++++++++++++++\n commit-reach.h | 8 +++++++\n upload-pack.c | 62 +++-----------------------------------------------\n 3 files changed, 72 insertions(+), 59 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 6cfd7379ce..44c09669ec 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -1,5 +1,6 @@\n #include \"cache.h\"\n #include \"commit.h\"\n+#include \"commit-graph.h\"\n #include \"decorate.h\"\n #include \"prio-queue.h\"\n #include \"tree.h\"\n@@ -528,3 +529,63 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,\n \t\treturn contains_tag_algo(commit, list, cache) == CONTAINS_YES;\n \treturn is_descendant_of(commit, list);\n }\n+\n+static int reachable(struct commit *from, int with_flag, int assign_flag, time_t min_commit_date)\n+{\n+\tstruct prio_queue work = { compare_commits_by_commit_date };\n+\n+\tprio_queue_put(&work, from);\n+\twhile (work.nr) {\n+\t\tstruct commit_list *list;\n+\t\tstruct commit *commit = prio_queue_get(&work);\n+\n+\t\tif (commit->object.flags & with_flag) {\n+\t\t\tfrom->object.flags |= assign_flag;\n+\t\t\tbreak;\n+\t\t}\n+\t\tif (!commit->object.parsed)\n+\t\t\tparse_object(&commit->object.oid);\n+\t\tif (commit->object.flags & TMP_MARK)\n+\t\t\tcontinue;\n+\t\tcommit->object.flags |= TMP_MARK;\n+\t\tif (commit->date < min_commit_date)\n+\t\t\tcontinue;\n+\t\tfor (list = commit->parents; list; list = list->next) {\n+\t\t\tstruct commit *parent = list->item;\n+\t\t\tif (!(parent->object.flags & TMP_MARK))\n+\t\t\t\tprio_queue_put(&work, parent);\n+\t\t}\n+\t}\n+\tfrom->object.flags |= TMP_MARK;\n+\tclear_commit_marks(from, TMP_MARK);\n+\tclear_prio_queue(&work);\n+\treturn (from->object.flags & assign_flag);\n+}\n+\n+int can_all_from_reach_with_flag(struct object_array from,\n+\t\t\t\t int with_flag, int assign_flag,\n+\t\t\t\t time_t min_commit_date)\n+{\n+\tint i;\n+\n+\tfor (i = 0; i < from.nr; i++) {\n+\t\tstruct object *from_one = from.objects[i].item;\n+\n+\t\tif (from_one->flags & assign_flag)\n+\t\t\tcontinue;\n+\t\tfrom_one = deref_tag(from_one, \"a from object\", 0);\n+\t\tif (!from_one || from_one->type != OBJ_COMMIT) {\n+\t\t\t/* no way to tell if this is reachable by\n+\t\t\t * looking at the ancestry chain alone, so\n+\t\t\t * leave a note to ourselves not to worry about\n+\t\t\t * this object anymore.\n+\t\t\t */\n+\t\t\tfrom.objects[i].item->flags |= assign_flag;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!reachable((struct commit *)from_one, with_flag,\n+\t\t\t assign_flag, min_commit_date))\n+\t\t\treturn 0;\n+\t}\n+\treturn 1;\n+}\ndiff --git a/commit-reach.h b/commit-reach.h\nindex 986fb388d5..c3da8488eb 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -22,4 +22,12 @@ define_commit_slab(contains_cache, enum contains_result);\n int commit_contains(struct ref_filter *filter, struct commit *commit,\n \t\t struct commit_list *list, struct contains_cache *cache);\n \n+/*\n+ * Can every commit or tag in the 'from' array reach a commit that has\n+ * the 'with_flag' bit on? Mark the commits in 'from' that can reach\n+ * such commits with 'assign_flag'.\n+ */\n+int can_all_from_reach_with_flag(struct object_array from, int with_flag,\n+\t\t\t\t int assign_flag, time_t min_commit_date);\n+\n #endif\ndiff --git a/upload-pack.c b/upload-pack.c\nindex 2f09cadbc0..7c58cb8f5e 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -22,6 +22,7 @@\n #include \"quote.h\"\n #include \"upload-pack.h\"\n #include \"serve.h\"\n+#include \"commit-reach.h\"\n \n /* Remember to update object flag allocation in object.h */\n #define THEY_HAVE\t(1u << 11)\n@@ -333,70 +334,13 @@ static int got_oid(const char *hex, struct object_id *oid)\n \treturn 0;\n }\n \n-static int reachable(struct commit *from, int with_flag, int assign_flag)\n-{\n-\tstruct prio_queue work = { compare_commits_by_commit_date };\n-\n-\tprio_queue_put(&work, from);\n-\twhile (work.nr) {\n-\t\tstruct commit_list *list;\n-\t\tstruct commit *commit = prio_queue_get(&work);\n-\n-\t\tif (commit->object.flags & with_flag) {\n-\t\t\tfrom->object.flags |= assign_flag;\n-\t\t\tbreak;\n-\t\t}\n-\t\tif (!commit->object.parsed)\n-\t\t\tparse_object(&commit->object.oid);\n-\t\tif (commit->object.flags & TMP_MARK)\n-\t\t\tcontinue;\n-\t\tcommit->object.flags |= TMP_MARK;\n-\t\tif (commit->date < oldest_have)\n-\t\t\tcontinue;\n-\t\tfor (list = commit->parents; list; list = list->next) {\n-\t\t\tstruct commit *parent = list->item;\n-\t\t\tif (!(parent->object.flags & TMP_MARK))\n-\t\t\t\tprio_queue_put(&work, parent);\n-\t\t}\n-\t}\n-\tfrom->object.flags |= TMP_MARK;\n-\tclear_commit_marks(from, TMP_MARK);\n-\tclear_prio_queue(&work);\n-\treturn (from->object.flags & assign_flag);\n-}\n-\n-static int can_all_from_reach_with_flag(struct object_array from,\n-\t\t\t\t\tint with_flag, int assign_flag)\n-{\n-\tint i;\n-\n-\tfor (i = 0; i < from.nr; i++) {\n-\t\tstruct object *from_one = from.objects[i].item;\n-\n-\t\tif (from_one->flags & assign_flag)\n-\t\t\tcontinue;\n-\t\tfrom_one = deref_tag(from_one, \"a from object\", 0);\n-\t\tif (!from_one || from_one->type != OBJ_COMMIT) {\n-\t\t\t/* no way to tell if this is reachable by\n-\t\t\t * looking at the ancestry chain alone, so\n-\t\t\t * leave a note to ourselves not to worry about\n-\t\t\t * this object anymore.\n-\t\t\t */\n-\t\t\tfrom.objects[i].item->flags |= assign_flag;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tif (!reachable((struct commit *)from_one, with_flag, assign_flag))\n-\t\t\treturn 0;\n-\t}\n-\treturn 1;\n-}\n-\n static int ok_to_give_up(void)\n {\n \tif (!have_obj.nr)\n \t\treturn 0;\n \n-\treturn can_all_from_reach_with_flag(want_obj, THEY_HAVE, COMMON_KNOWN);\n+\treturn can_all_from_reach_with_flag(want_obj, THEY_HAVE,\n+\t\t\t\t\t COMMON_KNOWN, oldest_have);\n }\n \n static int get_common_commits(void)\n-- \n2.18.0.118.gd4f65b8d14\n\n"},{"id":"351350","messageId":"20180629161223.229661-11-dstolee@microsoft.com","threadId":"48802","inReplyTo":"20180629161223.229661-1-dstolee@microsoft.com","subject":"[RFC PATCH 10/13] commit-reach: test is_descendant_of","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-29T16:12:58Z","receivedAt":"2018-06-29T16:13:06Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Signed-off-by: Derrick Stolee \n---\n t/helper/test-reach.c | 2 ++\n t/t6600-test-reach.sh | 25 +++++++++++++++++++++++++\n 2 files changed, 27 insertions(+)\n\ndiff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\nindex 88639a2945..14aaef5bff 100644\n--- a/t/helper/test-reach.c\n+++ b/t/helper/test-reach.c\n@@ -89,6 +89,8 @@ int cmd__reach(int ac, const char **av)\n \t\tprintf(\"%s:%d\\n\", av[1], ref_newer(&oid_A, &oid_B));\n \telse if (!strcmp(av[1], \"in_merge_base\"))\n \t\tprintf(\"%s:%d\\n\", av[1], in_merge_bases(A, B));\n+\telse if (!strcmp(av[1], \"is_descendant_of\"))\n+\t\tprintf(\"%s(A,X):%d\\n\", av[1], is_descendant_of(A, list_X));\n \telse if (!strcmp(av[1], \"get_merge_bases_many\")) {\n \t\tstruct commit_list *list = get_merge_bases_many(A, nr_X, X);\n \t\tprintf(\"%s(A,X):\\n\", av[1]);\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex ef25e70174..62655ae650 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -78,6 +78,31 @@ test_expect_success 'ref_newer:miss' '\n \ttest_reach_two_modes ref_newer\n '\n \n+test_expect_success 'is_descendant_of:hit' '\n+\tcat >input <<- EOF &&\n+\tA:commit-5-7\n+\tX:commit-4-8\n+\tX:commit-6-6\n+\tX:commit-1-1\n+\tEOF\n+\tcat >expect <<- EOF &&\n+\tis_descendant_of(A,X):1\n+\tEOF\n+\ttest_reach_two_modes is_descendant_of\n+'\n+\n+test_expect_success 'is_descendant_of:miss' '\n+\tcat >input <<- EOF &&\n+\tA:commit-5-7\n+\tX:commit-4-8\n+\tX:commit-6-6\n+\tEOF\n+\tcat >expect <<- EOF &&\n+\tis_descendant_of(A,X):0\n+\tEOF\n+\ttest_reach_two_modes is_descendant_of\n+'\n+\n test_expect_success 'reduce_heads' '\n \tcat >input <<- EOF &&\n \tX:commit-1-10\n-- \n2.18.0.118.gd4f65b8d14\n\n"},{"id":"351351","messageId":"20180629161223.229661-10-dstolee@microsoft.com","threadId":"48802","inReplyTo":"20180629161223.229661-1-dstolee@microsoft.com","subject":"[RFC PATCH 09/13] commit-reach: test can_all_from_reach","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-29T16:12:57Z","receivedAt":"2018-06-29T16:13:08Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Signed-off-by: Derrick Stolee \n---\n commit-reach.c | 52 +++++++++++++++++++++++++++++++++++++++----\n commit-reach.h | 4 +++-\n t/helper/test-reach.c | 7 ++++--\n t/t6600-test-reach.sh | 51 +++++++++++++++++++++++++++++++++++++++---\n upload-pack.c | 2 +-\n 5 files changed, 105 insertions(+), 11 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 44c09669ec..992ad5cdc7 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -562,14 +562,14 @@ static int reachable(struct commit *from, int with_flag, int assign_flag, time_t\n \treturn (from->object.flags & assign_flag);\n }\n \n-int can_all_from_reach_with_flag(struct object_array from,\n+int can_all_from_reach_with_flag(struct object_array *from,\n \t\t\t\t int with_flag, int assign_flag,\n \t\t\t\t time_t min_commit_date)\n {\n \tint i;\n \n-\tfor (i = 0; i < from.nr; i++) {\n-\t\tstruct object *from_one = from.objects[i].item;\n+\tfor (i = 0; i < from->nr; i++) {\n+\t\tstruct object *from_one = from->objects[i].item;\n \n \t\tif (from_one->flags & assign_flag)\n \t\t\tcontinue;\n@@ -580,7 +580,7 @@ int can_all_from_reach_with_flag(struct object_array from,\n \t\t\t * leave a note to ourselves not to worry about\n \t\t\t * this object anymore.\n \t\t\t */\n-\t\t\tfrom.objects[i].item->flags |= assign_flag;\n+\t\t\tfrom->objects[i].item->flags |= assign_flag;\n \t\t\tcontinue;\n \t\t}\n \t\tif (!reachable((struct commit *)from_one, with_flag,\n@@ -589,3 +589,47 @@ int can_all_from_reach_with_flag(struct object_array from,\n \t}\n \treturn 1;\n }\n+\n+int can_all_from_reach(struct commit_list *from, struct commit_list *to)\n+{\n+\tstruct object_array from_objs = OBJECT_ARRAY_INIT;\n+\ttime_t min_commit_date = from->item->date;\n+\tstruct commit_list *from_iter = from;\n+\tstruct commit_list *to_iter = to;\n+\tint result;\n+\n+\twhile (from_iter) {\n+\t\tadd_object_array(&from_iter->item->object, NULL, &from_objs);\n+\n+\t\tif (from_iter->item->date < min_commit_date)\n+\t\t\tmin_commit_date = from_iter->item->date;\n+\n+\t\tfrom_iter = from_iter->next;\n+\t}\n+\n+\twhile (to_iter) {\n+\t\tif (to_iter->item->date < min_commit_date)\n+\t\t\tmin_commit_date = to_iter->item->date;\n+\n+\t\tto_iter->item->object.flags |= PARENT2;\n+\n+\t\tto_iter = to_iter->next;\n+\t}\n+\n+\tresult = can_all_from_reach_with_flag(&from_objs, PARENT2, PARENT1,\n+\t\t\t\t\t min_commit_date);\n+\n+\twhile (from) {\n+\t\tclear_commit_marks(from->item, PARENT1);\n+\t\tfrom = from->next;\n+\t}\n+\n+\twhile (to) {\n+\t\tclear_commit_marks(to->item, PARENT2);\n+\t\tto = to->next;\n+\t}\n+\n+\tobject_array_clear(&from_objs);\n+\n+\treturn result;\n+}\ndiff --git a/commit-reach.h b/commit-reach.h\nindex c3da8488eb..8ab06af2eb 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -27,7 +27,9 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,\n * the 'with_flag' bit on? Mark the commits in 'from' that can reach\n * such commits with 'assign_flag'.\n */\n-int can_all_from_reach_with_flag(struct object_array from, int with_flag,\n+int can_all_from_reach_with_flag(struct object_array *from, int with_flag,\n \t\t\t\t int assign_flag, time_t min_commit_date);\n \n+int can_all_from_reach(struct commit_list *from, struct commit_list *to);\n+\n #endif\ndiff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\nindex d57660af45..88639a2945 100644\n--- a/t/helper/test-reach.c\n+++ b/t/helper/test-reach.c\n@@ -15,9 +15,9 @@ int cmd__reach(int ac, const char **av)\n \tstruct strbuf buf = STRBUF_INIT;\n \n \tsetup_git_directory();\n-\tget_git_config(default_git_config, 0);\n+\tgit_config(git_default_config, NULL);\n \n-\tif (argc < 2)\n+\tif (ac < 2)\n \t\texit(1);\n \n \t/* load input data */\n@@ -117,6 +117,9 @@ int cmd__reach(int ac, const char **av)\n \t\t\tprintf(\"%s\\n\", oid_to_hex(&list->item->object.oid));\n \t\t\tlist = list->next;\n \t\t}\n+\t} else if (!strcmp(av[1], \"can_all_from_reach\")) {\n+\t\tint result = can_all_from_reach(list_X, list_Y);\n+\t\tprintf(\"%s(X,Y):%d\\n\", av[1], result);\n \t}\n \n \texit(0);\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex 0f60db9c60..ef25e70174 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -64,7 +64,7 @@ test_expect_success 'ref_newer:miss' '\n \tcat >expect <<- EOF &&\n \tref_newer:0\n \tEOF\n-\ttest_reach_two_modes \"ref_newer\"\n+\ttest_reach_two_modes ref_newer\n '\n \n test_expect_success 'ref_newer:miss' '\n@@ -75,7 +75,7 @@ test_expect_success 'ref_newer:miss' '\n \tcat >expect <<- EOF &&\n \tref_newer:1\n \tEOF\n-\ttest_reach_two_modes \"ref_newer\"\n+\ttest_reach_two_modes ref_newer\n '\n \n test_expect_success 'reduce_heads' '\n@@ -101,7 +101,52 @@ test_expect_success 'reduce_heads' '\n \tgit rev-parse commit-1-10 >>expect &&\n \tprintf \"reduce_heads(Y):\\n\" >>expect &&\n \tgit rev-parse commit-10-10 >>expect &&\n-\ttest_reach_two_modes \"reduce_heads\"\n+\ttest_reach_two_modes reduce_heads\n+'\n+\n+test_expect_success 'can_all_from_reach:hit' '\n+\tcat >input <<- EOF &&\n+\tX:commit-2-10\n+\tX:commit-3-9\n+\tX:commit-4-8\n+\tX:commit-5-7\n+\tX:commit-6-6\n+\tX:commit-7-5\n+\tX:commit-8-4\n+\tX:commit-9-3\n+\tY:commit-1-9\n+\tY:commit-2-8\n+\tY:commit-3-7\n+\tY:commit-4-6\n+\tY:commit-5-5\n+\tY:commit-6-4\n+\tY:commit-7-3\n+\tY:commit-8-1\n+\tEOF\n+\tprintf \"can_all_from_reach(X,Y):1\\n\" >expect &&\n+\ttest_reach_two_modes can_all_from_reach\n+'\n+\n+test_expect_success 'can_all_from_reach:miss' '\n+\tcat >input <<- EOF &&\n+\tX:commit-2-10\n+\tX:commit-3-9\n+\tX:commit-4-8\n+\tX:commit-5-7\n+\tX:commit-6-6\n+\tX:commit-7-5\n+\tX:commit-8-4\n+\tX:commit-9-3\n+\tY:commit-1-9\n+\tY:commit-2-8\n+\tY:commit-3-7\n+\tY:commit-4-6\n+\tY:commit-5-5\n+\tY:commit-6-4\n+\tY:commit-8-5\n+\tEOF\n+\tprintf \"can_all_from_reach(X,Y):0\\n\" >expect &&\n+\ttest_reach_two_modes can_all_from_reach\n '\n \n test_done\ndiff --git a/upload-pack.c b/upload-pack.c\nindex 7c58cb8f5e..e59fbca257 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -339,7 +339,7 @@ static int ok_to_give_up(void)\n \tif (!have_obj.nr)\n \t\treturn 0;\n \n-\treturn can_all_from_reach_with_flag(want_obj, THEY_HAVE,\n+\treturn can_all_from_reach_with_flag(&want_obj, THEY_HAVE,\n \t\t\t\t\t COMMON_KNOWN, oldest_have);\n }\n \n-- \n2.18.0.118.gd4f65b8d14\n\n"},{"id":"351352","messageId":"20180629161223.229661-13-dstolee@microsoft.com","threadId":"48802","inReplyTo":"20180629161223.229661-1-dstolee@microsoft.com","subject":"[RFC PATCH 12/13] commit-reach: use is_descendant_of for ref_newer","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-29T16:13:01Z","receivedAt":"2018-06-29T16:13:11Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"The ref_newer method is used by 'git push' to detect if a force-push is\nrequried. This method does not use any kind of cutoff when walking, so\nin the case of a force-push will walk all reachable commits.\n\nThe is_descendant_of method already uses paint_down_to_common along with\ncutoffs. By translating the ref_newer arguments into the commit and\ncommit_list required by is_descendant_of, we can have one fewer commit\nwalk and also improve our performance!\n\nFor a copy of the Linux repository, 'test-tool reach ref_newer' presents\nthe following improvements with the specified input.\n\nInput\n-----\nA:v4.9\nB:v3.19\n\nBefore: 0.11 s\n After: 0.10 s\n\nTo test the negative case, add a new commit with parent v3.19,\nregenerate the commit-graph, and then run with B pointing at that\ncommit.\n\nBefore: 0.52 s\n After: 0.12 s\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 17 ++++-------------\n commit.c | 7 +++++--\n commit.h | 6 +++++-\n fetch-pack.c | 3 ++-\n sha1-name.c | 3 ++-\n walker.c | 3 ++-\n 6 files changed, 20 insertions(+), 19 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 8e24455d9f..249e9a4fac 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -376,7 +376,7 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)\n {\n \tstruct object *o;\n \tstruct commit *old_commit, *new_commit;\n-\tstruct commit_list *list, *used;\n+\tstruct commit_list *list = NULL;\n \tint found = 0;\n \n \t/*\n@@ -396,18 +396,9 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)\n \tif (parse_commit(new_commit) < 0)\n \t\treturn 0;\n \n-\tused = list = NULL;\n-\tcommit_list_insert(new_commit, &list);\n-\twhile (list) {\n-\t\tnew_commit = pop_most_recent_commit(&list, TMP_MARK);\n-\t\tcommit_list_insert(new_commit, &used);\n-\t\tif (new_commit == old_commit) {\n-\t\t\tfound = 1;\n-\t\t\tbreak;\n-\t\t}\n-\t}\n-\tunmark_and_free(list, TMP_MARK);\n-\tunmark_and_free(used, TMP_MARK);\n+\tcommit_list_insert(old_commit, &list);\n+\tfound = is_descendant_of(new_commit, list);\n+\tfree_commit_list(list);\n \treturn found;\n }\n \ndiff --git a/commit.c b/commit.c\nindex d4ddaf4879..9870682673 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -556,7 +556,8 @@ void commit_list_sort_by_date(struct commit_list **list)\n }\n \n struct commit *pop_most_recent_commit(struct commit_list **list,\n-\t\t\t\t unsigned int mark)\n+\t\t\t\t unsigned int mark,\n+\t\t\t\t uint32_t min_generation)\n {\n \tstruct commit *ret = pop_commit(list);\n \tstruct commit_list *parents = ret->parents;\n@@ -565,7 +566,9 @@ struct commit *pop_most_recent_commit(struct commit_list **list,\n \t\tstruct commit *commit = parents->item;\n \t\tif (!parse_commit(commit) && !(commit->object.flags & mark)) {\n \t\t\tcommit->object.flags |= mark;\n-\t\t\tcommit_list_insert_by_date(commit, list);\n+\n+\t\t\tif (commit->generation >= min_generation)\n+\t\t\t\tcommit_list_insert_by_date(commit, list);\n \t\t}\n \t\tparents = parents->next;\n \t}\ndiff --git a/commit.h b/commit.h\nindex 7e0f273720..5eaeded5e2 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -159,9 +159,13 @@ extern const char *skip_blank_lines(const char *msg);\n \n /** Removes the first commit from a list sorted by date, and adds all\n * of its parents.\n+ *\n+ * The parents are not added if their generation number is strictly\n+ * lower than min_generation.\n **/\n struct commit *pop_most_recent_commit(struct commit_list **list,\n-\t\t\t\t unsigned int mark);\n+\t\t\t\t unsigned int mark,\n+\t\t\t\t uint32_t min_generation);\n \n struct commit *pop_commit(struct commit_list **stack);\n \ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex a320ce9872..351e3d4bcd 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -600,7 +600,8 @@ static void mark_recent_complete_commits(struct fetch_pack_args *args,\n \twhile (complete && cutoff <= complete->item->date) {\n \t\tprint_verbose(args, _(\"Marking %s as complete\"),\n \t\t\t oid_to_hex(&complete->item->object.oid));\n-\t\tpop_most_recent_commit(&complete, COMPLETE);\n+\t\tpop_most_recent_commit(&complete, COMPLETE,\n+\t\t\t\t GENERATION_NUMBER_ZERO);\n \t}\n }\n \ndiff --git a/sha1-name.c b/sha1-name.c\nindex 60d9ef3c7e..471a54464d 100644\n--- a/sha1-name.c\n+++ b/sha1-name.c\n@@ -1141,7 +1141,8 @@ static int get_oid_oneline(const char *prefix, struct object_id *oid,\n \t\tstruct commit *commit;\n \t\tint matches;\n \n-\t\tcommit = pop_most_recent_commit(&list, ONELINE_SEEN);\n+\t\tcommit = pop_most_recent_commit(&list, ONELINE_SEEN,\n+\t\t\t\t\t\tGENERATION_NUMBER_ZERO);\n \t\tif (!parse_object(&commit->object.oid))\n \t\t\tcontinue;\n \t\tbuf = get_commit_buffer(commit, NULL);\ndiff --git a/walker.c b/walker.c\nindex 0b162a09b9..e243fc8768 100644\n--- a/walker.c\n+++ b/walker.c\n@@ -78,7 +78,8 @@ static int process_commit(struct walker *walker, struct commit *commit)\n \t\treturn -1;\n \n \twhile (complete && complete->item->date >= commit->date) {\n-\t\tpop_most_recent_commit(&complete, COMPLETE);\n+\t\tpop_most_recent_commit(&complete, COMPLETE,\n+\t\t\t\t GENERATION_NUMBER_ZERO);\n \t}\n \n \tif (commit->object.flags & COMPLETE)\n-- \n2.18.0.118.gd4f65b8d14\n\n"},{"id":"351353","messageId":"20180629161223.229661-14-dstolee@microsoft.com","threadId":"48802","inReplyTo":"20180629161223.229661-1-dstolee@microsoft.com","subject":"[RFC PATCH 13/13] commit-reach: use can_all_from_reach","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-29T16:13:03Z","receivedAt":"2018-06-29T16:13:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"The is_descendant_of method previously used in_merge_bases() to check if\nthe commit can reach any of the commits in the provided list. This had\ntwo performance problems:\n\n1. The performance is quadratic in worst-case.\n\n2. A single in_merge_bases() call requires walking beyond the target\n commit in order to find the full set of boundary commits that may be\n merge-bases.\n\nThe can_all_from_reach method avoids this quadratic behavior and can\nlimit the search beyond the target commits using generation numbers. It\nrequires a small prototype adjustment to stop using commit-date as a\ncutoff, as that optimization is no longer appropriate here.\n\nPerformance was meausured on a copy of the Linux repository using the\n'test-tool reach is_descendant_of' command using this input:\n\nA:v4.9\nX:v4.10\nX:v4.11\nX:v4.12\nX:v4.13\nX:v4.14\nX:v4.15\nX:v4.16\nX:v4.17\nX.v3.0\n\nNote that this input is tailored to demonstrate the quadratic nature of\nthe previous method, as it will compute merge-bases for v4.9 versus all\nof the later versions before checking against v4.1.\n\nBefore: 0.31 s\n After: 0.27 s\n\nSince we previously used the is_descendant_of method in the ref_newer\nmethod, we also measured performance there using\n'test-tool reach ref_newer':\n\nBefore: 0.12 s\n After: 0.11 s\n\nSigned-off-by: Derrick Stolee \n---\n\nOne thing I know is missing from this commit is a special-case to use\nthe old logic when there is no commit-graph present. The\ncan_all_from_reach() algorithm can be worse when we do not have good\ngeneration number cutoffs. In the previous case of\ncan_all_from_reach_with_flags(), we already had an established pattern\nof using commit date as a cutoff, so the generation number is only a\nsecond cutoff and the algorithm cannot walk more commits than before.\n\n commit-reach.c | 34 +++++++++++++++++-----------------\n commit-reach.h | 3 ++-\n t/helper/test-reach.c | 2 +-\n 3 files changed, 20 insertions(+), 19 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 249e9a4fac..a823d6965c 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -273,17 +273,15 @@ struct commit_list *get_merge_bases(struct commit *one, struct commit *two)\n */\n int is_descendant_of(struct commit *commit, struct commit_list *with_commit)\n {\n+\tstruct commit_list *from_list = NULL;\n+\tint result;\n \tif (!with_commit)\n \t\treturn 1;\n-\twhile (with_commit) {\n-\t\tstruct commit *other;\n \n-\t\tother = with_commit->item;\n-\t\twith_commit = with_commit->next;\n-\t\tif (in_merge_bases(other, commit))\n-\t\t\treturn 1;\n-\t}\n-\treturn 0;\n+\tcommit_list_insert(commit, &from_list);\n+\tresult = can_all_from_reach(from_list, with_commit, 0);\n+\tfree_commit_list(from_list);\n+\treturn result;\n }\n \n /*\n@@ -605,10 +603,11 @@ int can_all_from_reach_with_flag(struct object_array *from,\n \treturn result;\n }\n \n-int can_all_from_reach(struct commit_list *from, struct commit_list *to)\n+int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n+\t\t int cutoff_by_min_date)\n {\n \tstruct object_array from_objs = OBJECT_ARRAY_INIT;\n-\ttime_t min_commit_date = from->item->date;\n+\ttime_t min_commit_date = cutoff_by_min_date ? from->item->date : 0;\n \tstruct commit_list *from_iter = from;\n \tstruct commit_list *to_iter = to;\n \tint result;\n@@ -617,20 +616,21 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to)\n \twhile (from_iter) {\n \t\tadd_object_array(&from_iter->item->object, NULL, &from_objs);\n \n-\t\tif (from_iter->item->date < min_commit_date)\n+\t\tif (!parse_commit(from_iter->item) &&\n+\t\t from_iter->item->date < min_commit_date)\n \t\t\tmin_commit_date = from_iter->item->date;\n \n \t\tfrom_iter = from_iter->next;\n \t}\n \n \twhile (to_iter) {\n-\t\tparse_commit(to_iter->item);\n-\n-\t\tif (to_iter->item->date < min_commit_date)\n-\t\t\tmin_commit_date = to_iter->item->date;\n+\t\tif (!parse_commit(to_iter->item)) {\n+\t\t\tif (to_iter->item->date < min_commit_date)\n+\t\t\t\tmin_commit_date = to_iter->item->date;\n \n-\t\tif (to_iter->item->generation < min_generation)\n-\t\t\tmin_generation = to_iter->item->generation;\n+\t\t\tif (to_iter->item->generation < min_generation)\n+\t\t\t\tmin_generation = to_iter->item->generation;\n+\t\t}\n \n \t\tto_iter->item->object.flags |= PARENT2;\n \ndiff --git a/commit-reach.h b/commit-reach.h\nindex 3eb4c057e6..180f865d7d 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -31,6 +31,7 @@ int can_all_from_reach_with_flag(struct object_array *from, int with_flag,\n \t\t\t\t int assign_flag, time_t min_commit_date,\n \t\t\t\t uint32_t min_generation);\n \n-int can_all_from_reach(struct commit_list *from, struct commit_list *to);\n+int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n+\t\t int cutoff_by_min_date);\n \n #endif\ndiff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\nindex 14aaef5bff..c05137c9f3 100644\n--- a/t/helper/test-reach.c\n+++ b/t/helper/test-reach.c\n@@ -120,7 +120,7 @@ int cmd__reach(int ac, const char **av)\n \t\t\tlist = list->next;\n \t\t}\n \t} else if (!strcmp(av[1], \"can_all_from_reach\")) {\n-\t\tint result = can_all_from_reach(list_X, list_Y);\n+\t\tint result = can_all_from_reach(list_X, list_Y, 1);\n \t\tprintf(\"%s(X,Y):%d\\n\", av[1], result);\n \t}\n \n-- \n2.18.0.118.gd4f65b8d14\n\n"},{"id":"351354","messageId":"20180629161223.229661-9-dstolee@microsoft.com","threadId":"48802","inReplyTo":"20180629161223.229661-1-dstolee@microsoft.com","subject":"[RFC PATCH 08/13] test-reach: test reduce_heads()","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-29T16:12:56Z","receivedAt":"2018-06-29T16:13:17Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Signed-off-by: Derrick Stolee \n---\n t/t6600-test-reach.sh | 26 ++++++++++++++++++++++++++\n 1 file changed, 26 insertions(+)\n\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex c9337b6b46..0f60db9c60 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -78,4 +78,30 @@ test_expect_success 'ref_newer:miss' '\n \ttest_reach_two_modes \"ref_newer\"\n '\n \n+test_expect_success 'reduce_heads' '\n+\tcat >input <<- EOF &&\n+\tX:commit-1-10\n+\tX:commit-2-8\n+\tX:commit-3-6\n+\tX:commit-4-4\n+\tX:commit-1-7\n+\tX:commit-2-5\n+\tX:commit-3-3\n+\tX:commit-5-1\n+\tY:commit-10-10\n+\tY:commit-3-10\n+\tY:commit-9-9\n+\tY:commit-8-1\n+\tEOF\n+\tprintf \"reduce_heads(X):\\n\" >expect &&\n+\tgit rev-parse commit-5-1 >>expect &&\n+\tgit rev-parse commit-4-4 >>expect &&\n+\tgit rev-parse commit-3-6 >>expect &&\n+\tgit rev-parse commit-2-8 >>expect &&\n+\tgit rev-parse commit-1-10 >>expect &&\n+\tprintf \"reduce_heads(Y):\\n\" >>expect &&\n+\tgit rev-parse commit-10-10 >>expect &&\n+\ttest_reach_two_modes \"reduce_heads\"\n+'\n+\n test_done\n-- \n2.18.0.118.gd4f65b8d14\n\n"},{"id":"351355","messageId":"20180629161223.229661-12-dstolee@microsoft.com","threadId":"48802","inReplyTo":"20180629161223.229661-1-dstolee@microsoft.com","subject":"[RFC PATCH 11/13] commit-reach: make can_all_from_reach... linear","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-29T16:13:00Z","receivedAt":"2018-06-29T16:13:19Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"The can_all_from_reach_with_flags() algorithm is currently quadratic in\nthe worst case, because it calls the reachable() method for every 'from'\nwithout tracking which commits have already been walked or which can\nalready reach a commit in 'to'.\n\nRewrite the algorithm to walk each commit a constant number of times.\n\nWe also add some optimizations that should work for the main consumer of\nthis method: fetch negotitation (haves/wants).\n\nThe first step includes using a depth-first-search (DFS) from each from\ncommit, sorted by ascending generation number. We do not walk beyond the\nminimum generation number or the minimum commit date. This DFS is likely\nto be faster than the existing reachable() method because we expect\nprevious ref values to be along the first-parent history.\n\nIf we find a target commit, then we mark everything in the DFS stack as\na RESULT. This expands the set of targets for the other from commits. We\nalso mark the visited commits using 'assign_flag' to prevent re-walking\nthe same code.\n\nWe still need to clear our flags at the end, which is why we will have a\ntotal of three visits to each commit.\n\nPerformance was measured on the Linux repository using\n'test-tool reach can_all_from_reach'. The input included rows seeded by\ntag values. The \"small\" case included X-rows as v4.[0-9]* and Y-rows as\nv3.[0-9]*. This mimics a (very large) fetch that says \"I have all major\nv3 releases and want all major v4 releases.\" The \"large\" case included\nX-rows as \"v4.*\" and Y-rows as \"v3.*\". This adds all release-candidate\ntags to the set, which does not greatly increase the number of objects\nthat are considered, but does increase the number of 'from' commits,\ndemonstrating the quadratic nature of the previous code.\n\nSmall Case\n----------\n\nBefore: 1.45 s\n After: 0.34 s\n\nLarge Case\n----------\n\nBefore: 5.83 s\n After: 0.37 s\n\nNote how the time increases between the two cases in the two versions.\nThe new code increases relative to the number of commits that need to be\nwalked, but not directly relative to the number of 'from' commits.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 122 ++++++++++++++++++++++++++++++-------------------\n commit-reach.h | 3 +-\n upload-pack.c | 5 +-\n 3 files changed, 82 insertions(+), 48 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 992ad5cdc7..8e24455d9f 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -530,64 +530,88 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,\n \treturn is_descendant_of(commit, list);\n }\n \n-static int reachable(struct commit *from, int with_flag, int assign_flag, time_t min_commit_date)\n+static int compare_commits_by_gen(const void *_a, const void *_b)\n {\n-\tstruct prio_queue work = { compare_commits_by_commit_date };\n+\tconst struct commit *a = (const struct commit *)_a;\n+\tconst struct commit *b = (const struct commit *)_b;\n \n-\tprio_queue_put(&work, from);\n-\twhile (work.nr) {\n-\t\tstruct commit_list *list;\n-\t\tstruct commit *commit = prio_queue_get(&work);\n-\n-\t\tif (commit->object.flags & with_flag) {\n-\t\t\tfrom->object.flags |= assign_flag;\n-\t\t\tbreak;\n-\t\t}\n-\t\tif (!commit->object.parsed)\n-\t\t\tparse_object(&commit->object.oid);\n-\t\tif (commit->object.flags & TMP_MARK)\n-\t\t\tcontinue;\n-\t\tcommit->object.flags |= TMP_MARK;\n-\t\tif (commit->date < min_commit_date)\n-\t\t\tcontinue;\n-\t\tfor (list = commit->parents; list; list = list->next) {\n-\t\t\tstruct commit *parent = list->item;\n-\t\t\tif (!(parent->object.flags & TMP_MARK))\n-\t\t\t\tprio_queue_put(&work, parent);\n-\t\t}\n-\t}\n-\tfrom->object.flags |= TMP_MARK;\n-\tclear_commit_marks(from, TMP_MARK);\n-\tclear_prio_queue(&work);\n-\treturn (from->object.flags & assign_flag);\n+\tif (a->generation < b->generation)\n+\t\treturn -1;\n+\tif (a->generation > b->generation)\n+\t\treturn 1;\n+\treturn 0;\n }\n \n int can_all_from_reach_with_flag(struct object_array *from,\n \t\t\t\t int with_flag, int assign_flag,\n-\t\t\t\t time_t min_commit_date)\n+\t\t\t\t time_t min_commit_date,\n+\t\t\t\t uint32_t min_generation)\n {\n+\tstruct commit **list = NULL;\n \tint i;\n+\tint result = 1;\n \n+\tALLOC_ARRAY(list, from->nr);\n \tfor (i = 0; i < from->nr; i++) {\n-\t\tstruct object *from_one = from->objects[i].item;\n+\t\tlist[i] = (struct commit *)from->objects[i].item;\n \n-\t\tif (from_one->flags & assign_flag)\n-\t\t\tcontinue;\n-\t\tfrom_one = deref_tag(from_one, \"a from object\", 0);\n-\t\tif (!from_one || from_one->type != OBJ_COMMIT) {\n-\t\t\t/* no way to tell if this is reachable by\n-\t\t\t * looking at the ancestry chain alone, so\n-\t\t\t * leave a note to ourselves not to worry about\n-\t\t\t * this object anymore.\n-\t\t\t */\n-\t\t\tfrom->objects[i].item->flags |= assign_flag;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tif (!reachable((struct commit *)from_one, with_flag,\n-\t\t\t assign_flag, min_commit_date))\n+\t\tparse_commit(list[i]);\n+\n+\t\tif (list[i]->generation < min_generation)\n \t\t\treturn 0;\n \t}\n-\treturn 1;\n+\n+\tQSORT(list, from->nr, compare_commits_by_gen);\n+\n+\tfor (i = 0; i < from->nr; i++) {\n+\t\t/* DFS from list[i] */\n+\t\tstruct commit_list *stack = NULL;\n+\n+\t\tlist[i]->object.flags |= assign_flag;\n+\t\tcommit_list_insert(list[i], &stack);\n+\n+\t\twhile (stack) {\n+\t\t\tstruct commit_list *parent;\n+\n+\t\t\tif (stack->item->object.flags & with_flag) {\n+\t\t\t\tpop_commit(&stack);\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\n+\t\t\tfor (parent = stack->item->parents; parent; parent = parent->next) {\n+\t\t\t\tif (parent->item->object.flags & (with_flag | RESULT))\n+\t\t\t\t\tstack->item->object.flags |= RESULT;\n+\n+\t\t\t\tif (!(parent->item->object.flags & assign_flag)) {\n+\t\t\t\t\tparent->item->object.flags |= assign_flag;\n+\n+\t\t\t\t\tparse_commit(parent->item);\n+\n+\t\t\t\t\tif (parent->item->date < min_commit_date ||\n+\t\t\t\t\t parent->item->generation < min_generation)\n+\t\t\t\t\t\tcontinue;\n+\n+\t\t\t\t\tcommit_list_insert(parent->item, &stack);\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t\tif (!parent)\n+\t\t\t\tpop_commit(&stack);\n+\t\t}\n+\n+\t\tif (!(list[i]->object.flags & (with_flag | RESULT))) {\n+\t\t\tresult = 0;\n+\t\t\tgoto cleanup;\n+\t\t}\n+\t}\n+\n+cleanup:\n+\tfor (i = 0; i < from->nr; i++) {\n+\t\tclear_commit_marks(list[i], RESULT);\n+\t\tclear_commit_marks(list[i], assign_flag);\n+\t}\n+\treturn result;\n }\n \n int can_all_from_reach(struct commit_list *from, struct commit_list *to)\n@@ -597,6 +621,7 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to)\n \tstruct commit_list *from_iter = from;\n \tstruct commit_list *to_iter = to;\n \tint result;\n+\tuint32_t min_generation = GENERATION_NUMBER_INFINITY;\n \n \twhile (from_iter) {\n \t\tadd_object_array(&from_iter->item->object, NULL, &from_objs);\n@@ -608,16 +633,21 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to)\n \t}\n \n \twhile (to_iter) {\n+\t\tparse_commit(to_iter->item);\n+\n \t\tif (to_iter->item->date < min_commit_date)\n \t\t\tmin_commit_date = to_iter->item->date;\n \n+\t\tif (to_iter->item->generation < min_generation)\n+\t\t\tmin_generation = to_iter->item->generation;\n+\n \t\tto_iter->item->object.flags |= PARENT2;\n \n \t\tto_iter = to_iter->next;\n \t}\n \n \tresult = can_all_from_reach_with_flag(&from_objs, PARENT2, PARENT1,\n-\t\t\t\t\t min_commit_date);\n+\t\t\t\t\t min_commit_date, min_generation);\n \n \twhile (from) {\n \t\tclear_commit_marks(from->item, PARENT1);\ndiff --git a/commit-reach.h b/commit-reach.h\nindex 8ab06af2eb..3eb4c057e6 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -28,7 +28,8 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,\n * such commits with 'assign_flag'.\n */\n int can_all_from_reach_with_flag(struct object_array *from, int with_flag,\n-\t\t\t\t int assign_flag, time_t min_commit_date);\n+\t\t\t\t int assign_flag, time_t min_commit_date,\n+\t\t\t\t uint32_t min_generation);\n \n int can_all_from_reach(struct commit_list *from, struct commit_list *to);\n \ndiff --git a/upload-pack.c b/upload-pack.c\nindex e59fbca257..95ba077e2b 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -336,11 +336,14 @@ static int got_oid(const char *hex, struct object_id *oid)\n \n static int ok_to_give_up(void)\n {\n+\tuint32_t min_generation = GENERATION_NUMBER_ZERO;\n+\n \tif (!have_obj.nr)\n \t\treturn 0;\n \n \treturn can_all_from_reach_with_flag(&want_obj, THEY_HAVE,\n-\t\t\t\t\t COMMON_KNOWN, oldest_have);\n+\t\t\t\t\t COMMON_KNOWN, oldest_have,\n+\t\t\t\t\t min_generation);\n }\n \n static int get_common_commits(void)\n-- \n2.18.0.118.gd4f65b8d14\n\n"},{"id":"351356","messageId":"20180629161223.229661-6-dstolee@microsoft.com","threadId":"48802","inReplyTo":"20180629161223.229661-1-dstolee@microsoft.com","subject":"[RFC PATCH 05/13] upload-pack: refactor ok_to_give_up()","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-29T16:12:52Z","receivedAt":"2018-06-29T16:13:22Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"In anticipation of consolidating all commit reachability algorithms,\nrefactor ok_to_give_up() in order to allow splitting its logic into\nan external method.\n\nSigned-off-by: Derrick Stolee \n---\n upload-pack.c | 28 +++++++++++++++++-----------\n 1 file changed, 17 insertions(+), 11 deletions(-)\n\ndiff --git a/upload-pack.c b/upload-pack.c\nindex 95c56dc027..2f09cadbc0 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -365,34 +365,40 @@ static int reachable(struct commit *from, int with_flag, int assign_flag)\n \treturn (from->object.flags & assign_flag);\n }\n \n-static int ok_to_give_up(void)\n+static int can_all_from_reach_with_flag(struct object_array from,\n+\t\t\t\t\tint with_flag, int assign_flag)\n {\n \tint i;\n \n-\tif (!have_obj.nr)\n-\t\treturn 0;\n-\n-\tfor (i = 0; i < want_obj.nr; i++) {\n-\t\tstruct object *want = want_obj.objects[i].item;\n+\tfor (i = 0; i < from.nr; i++) {\n+\t\tstruct object *from_one = from.objects[i].item;\n \n-\t\tif (want->flags & COMMON_KNOWN)\n+\t\tif (from_one->flags & assign_flag)\n \t\t\tcontinue;\n-\t\twant = deref_tag(want, \"a want line\", 0);\n-\t\tif (!want || want->type != OBJ_COMMIT) {\n+\t\tfrom_one = deref_tag(from_one, \"a from object\", 0);\n+\t\tif (!from_one || from_one->type != OBJ_COMMIT) {\n \t\t\t/* no way to tell if this is reachable by\n \t\t\t * looking at the ancestry chain alone, so\n \t\t\t * leave a note to ourselves not to worry about\n \t\t\t * this object anymore.\n \t\t\t */\n-\t\t\twant_obj.objects[i].item->flags |= COMMON_KNOWN;\n+\t\t\tfrom.objects[i].item->flags |= assign_flag;\n \t\t\tcontinue;\n \t\t}\n-\t\tif (!reachable((struct commit *)want, THEY_HAVE, COMMON_KNOWN))\n+\t\tif (!reachable((struct commit *)from_one, with_flag, assign_flag))\n \t\t\treturn 0;\n \t}\n \treturn 1;\n }\n \n+static int ok_to_give_up(void)\n+{\n+\tif (!have_obj.nr)\n+\t\treturn 0;\n+\n+\treturn can_all_from_reach_with_flag(want_obj, THEY_HAVE, COMMON_KNOWN);\n+}\n+\n static int get_common_commits(void)\n {\n \tstruct object_id oid;\n-- \n2.18.0.118.gd4f65b8d14\n\n"},{"id":"351357","messageId":"20180629161223.229661-8-dstolee@microsoft.com","threadId":"48802","inReplyTo":"20180629161223.229661-1-dstolee@microsoft.com","subject":"[RFC PATCH 07/13] test-reach","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-06-29T16:12:54Z","receivedAt":"2018-06-29T16:13:27Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"---\n Makefile | 1 +\n t/helper/test-reach.c | 123 ++++++++++++++++++++++++++++++++++++++++++\n t/helper/test-tool.c | 1 +\n t/helper/test-tool.h | 1 +\n t/t6600-test-reach.sh | 81 ++++++++++++++++++++++++++++\n 5 files changed, 207 insertions(+)\n create mode 100644 t/helper/test-reach.c\n create mode 100755 t/t6600-test-reach.sh\n\ndiff --git a/Makefile b/Makefile\nindex 89ad873ce0..c2a2c6457e 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -716,6 +716,7 @@ TEST_BUILTINS_OBJS += test-mktemp.o\n TEST_BUILTINS_OBJS += test-online-cpus.o\n TEST_BUILTINS_OBJS += test-path-utils.o\n TEST_BUILTINS_OBJS += test-prio-queue.o\n+TEST_BUILTINS_OBJS += test-reach.o\n TEST_BUILTINS_OBJS += test-read-cache.o\n TEST_BUILTINS_OBJS += test-ref-store.o\n TEST_BUILTINS_OBJS += test-regex.o\ndiff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\nnew file mode 100644\nindex 0000000000..d57660af45\n--- /dev/null\n+++ b/t/helper/test-reach.c\n@@ -0,0 +1,123 @@\n+#include \"test-tool.h\"\n+#include \"cache.h\"\n+#include \"commit-reach.h\"\n+#include \"config.h\"\n+#include \"parse-options.h\"\n+#include \"tag.h\"\n+\n+int cmd__reach(int ac, const char **av)\n+{\n+\tstruct object_id oid_A, oid_B;\n+\tstruct commit *A, *B;\n+\tstruct commit **X, **Y;\n+\tint nr_X, alloc_X, nr_Y, alloc_Y;\n+\tstruct commit_list *list_X, *list_Y;\n+\tstruct strbuf buf = STRBUF_INIT;\n+\n+\tsetup_git_directory();\n+\tget_git_config(default_git_config, 0);\n+\n+\tif (argc < 2)\n+\t\texit(1);\n+\n+\t/* load input data */\n+\tA = B = NULL;\n+\tlist_X = list_Y = NULL;\n+\tnr_X = nr_Y = 0;\n+\talloc_X = alloc_Y = 16;\n+\tALLOC_ARRAY(X, alloc_X);\n+\tALLOC_ARRAY(Y, alloc_Y);\n+\n+\twhile (strbuf_getline(&buf, stdin) != EOF) {\n+\t\tstruct object_id oid;\n+\t\tstruct object *o;\n+\t\tstruct commit *c;\n+\t\tif (buf.len < 3)\n+\t\t\tcontinue;\n+\n+\t\tif (get_oid_committish(buf.buf + 2, &oid))\n+\t\t\tdie(\"failed to resolve %s\", buf.buf + 2);\n+\n+\t\to = parse_object(&oid);\n+\t\to = deref_tag_noverify(o);\n+\n+\t\tif (!o)\n+\t\t\tdie(\"failed to load commit for input %s resulting in oid %s\\n\",\n+\t\t\t buf.buf, oid_to_hex(&oid));\n+\n+\t\tc = object_as_type(o, OBJ_COMMIT, 0);\n+\n+\t\tif (!c)\n+\t\t\tdie(\"failed to load commit for input %s resulting in oid %s\\n\",\n+\t\t\t buf.buf, oid_to_hex(&oid));\n+\n+\t\tswitch (buf.buf[0]) {\n+\t\t\tcase 'A':\n+\t\t\t\toidcpy(&oid_A, &oid);\n+\t\t\t\tA = c;\n+\t\t\t\tbreak;\n+\n+\t\t\tcase 'B':\n+\t\t\t\toidcpy(&oid_B, &oid);\n+\t\t\t\tB = c;\n+\t\t\t\tbreak;\n+\n+\t\t\tcase 'X':\n+\t\t\t\tALLOC_GROW(X, nr_X + 1, alloc_X);\n+\t\t\t\tX[nr_X++] = c;\n+\t\t\t\tcommit_list_insert(c, &list_X);\n+\t\t\t\tbreak;\n+\n+\t\t\tcase 'Y':\n+\t\t\t\tALLOC_GROW(Y, nr_Y + 1, alloc_Y);\n+\t\t\t\tY[nr_Y++] = c;\n+\t\t\t\tcommit_list_insert(c, &list_Y);\n+\t\t\t\tbreak;\n+\n+\t\t\tdefault:\n+\t\t\t\tdie(\"unexpected start of line: %c\", buf.buf[0]);\n+\t\t}\n+\t}\n+\tstrbuf_release(&buf);\n+\n+\tif (ac > 2 && !strcmp(av[2], \"graph:off\"))\n+\t\tcore_commit_graph = 0;\n+\tif (ac > 2 && !strcmp(av[2], \"graph:on\"))\n+\t\tcore_commit_graph = 1;\n+\n+\tif (!strcmp(av[1], \"ref_newer\"))\n+\t\tprintf(\"%s:%d\\n\", av[1], ref_newer(&oid_A, &oid_B));\n+\telse if (!strcmp(av[1], \"in_merge_base\"))\n+\t\tprintf(\"%s:%d\\n\", av[1], in_merge_bases(A, B));\n+\telse if (!strcmp(av[1], \"get_merge_bases_many\")) {\n+\t\tstruct commit_list *list = get_merge_bases_many(A, nr_X, X);\n+\t\tprintf(\"%s(A,X):\\n\", av[1]);\n+\t\twhile (list) {\n+\t\t\tprintf(\"%s\\n\", oid_to_hex(&list->item->object.oid));\n+\t\t\tlist = list->next;\n+\t\t}\n+\n+\t\tlist = get_merge_bases_many(B, nr_Y, Y);\n+\t\tprintf(\"%s(B,Y):\\n\", av[1]);\n+\t\twhile (list) {\n+\t\t\tprintf(\"%s\\n\", oid_to_hex(&list->item->object.oid));\n+\t\t\tlist = list->next;\n+\t\t}\n+\t} else if (!strcmp(av[1], \"reduce_heads\")) {\n+\t\tstruct commit_list *list = reduce_heads(list_X);\n+\t\tprintf(\"%s(X):\\n\", av[1]);\n+\t\twhile (list) {\n+\t\t\tprintf(\"%s\\n\", oid_to_hex(&list->item->object.oid));\n+\t\t\tlist = list->next;\n+\t\t}\n+\n+\t\tlist = reduce_heads(list_Y);\n+\t\tprintf(\"%s(Y):\\n\", av[1]);\n+\t\twhile (list) {\n+\t\t\tprintf(\"%s\\n\", oid_to_hex(&list->item->object.oid));\n+\t\t\tlist = list->next;\n+\t\t}\n+\t}\n+\n+\texit(0);\n+}\ndiff --git a/t/helper/test-tool.c b/t/helper/test-tool.c\nindex 805a45de9c..64d250b602 100644\n--- a/t/helper/test-tool.c\n+++ b/t/helper/test-tool.c\n@@ -26,6 +26,7 @@ static struct test_cmd cmds[] = {\n \t{ \"online-cpus\", cmd__online_cpus },\n \t{ \"path-utils\", cmd__path_utils },\n \t{ \"prio-queue\", cmd__prio_queue },\n+\t{ \"reach\", cmd__reach },\n \t{ \"read-cache\", cmd__read_cache },\n \t{ \"ref-store\", cmd__ref_store },\n \t{ \"regex\", cmd__regex },\ndiff --git a/t/helper/test-tool.h b/t/helper/test-tool.h\nindex 7116ddfb94..0b1d3534b5 100644\n--- a/t/helper/test-tool.h\n+++ b/t/helper/test-tool.h\n@@ -20,6 +20,7 @@ int cmd__mktemp(int argc, const char **argv);\n int cmd__online_cpus(int argc, const char **argv);\n int cmd__path_utils(int argc, const char **argv);\n int cmd__prio_queue(int argc, const char **argv);\n+int cmd__reach(int argc, const char **argv);\n int cmd__read_cache(int argc, const char **argv);\n int cmd__ref_store(int argc, const char **argv);\n int cmd__regex(int argc, const char **argv);\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nnew file mode 100755\nindex 0000000000..c9337b6b46\n--- /dev/null\n+++ b/t/t6600-test-reach.sh\n@@ -0,0 +1,81 @@\n+#!/bin/sh\n+\n+test_description='basic commit reachability tests'\n+\n+. ./test-lib.sh\n+\n+# Construct a grid-like commit graph with points (x,y)\n+# with 1 <= x <= 10, 1 <= y <= 10, where (x,y) has\n+# parents (x-1, y) and (x, y-1), keeping in mind that\n+# we drop a parent if a coordinate is nonpositive.\n+#\n+# (10,10)\n+# / \\\n+# (10,9) (9,10)\n+# / \\ / \\\n+# (10,8) (9,9) (8,10)\n+# / \\ / \\ / \\\n+# ( continued...)\n+# \\ / \\ / \\ /\n+# (3,1) (2,2) (1,3)\n+# \\ / \\ /\n+# (2,1) (2,1)\n+# \\ /\n+# (1,1)\n+#\n+# We use branch 'comit-x-y' to refer to (x,y).\n+# This grid allows interesting reachability and\n+# non-reachability queries: (x,y) can reach (x',y')\n+# if and only if x' <= x and y' <= y.\n+test_expect_success 'setup' '\n+\tfor i in $(test_seq 1 10)\n+\tdo\n+\t\ttest_commit \"1-$i\" &&\n+\t\tgit branch -f commit-1-$i\n+\tdone &&\n+\tfor j in $(test_seq 1 9)\n+\tdo\n+\t\tgit reset --hard commit-$j-1 &&\n+\t\tx=$(($j + 1)) &&\n+\t\ttest_commit \"$x-1\" &&\n+\t\tgit branch -f commit-$x-1 &&\n+\n+\t\tfor i in $(test_seq 2 10)\n+\t\tdo\n+\t\t\tgit merge commit-$j-$i -m \"$x-$i\" &&\n+\t\t\tgit branch -f commit-$x-$i\n+\t\tdone\n+\tdone &&\n+\tgit commit-graph write --reachable\n+'\n+\n+test_reach_two_modes() {\n+\ttest-tool reach $1 graph:off output &&\n+\ttest_cmp output expect &&\n+\ttest-tool reach $1 graph:on output &&\n+\ttest_cmp output expect\n+}\n+\n+test_expect_success 'ref_newer:miss' '\n+\tcat >input <<- EOF &&\n+\tA:commit-5-7\n+\tB:commit-4-9\n+\tEOF\n+\tcat >expect <<- EOF &&\n+\tref_newer:0\n+\tEOF\n+\ttest_reach_two_modes \"ref_newer\"\n+'\n+\n+test_expect_success 'ref_newer:miss' '\n+\tcat >input <<- EOF &&\n+\tA:commit-5-7\n+\tB:commit-2-3\n+\tEOF\n+\tcat >expect <<- EOF &&\n+\tref_newer:1\n+\tEOF\n+\ttest_reach_two_modes \"ref_newer\"\n+'\n+\n+test_done\n-- \n2.18.0.118.gd4f65b8d14\n\n"},{"id":"351362","messageId":"0107a143-a90a-0b37-f5c9-2e93ff6fa593@gmail.com","threadId":"48802","inReplyTo":"20180629161223.229661-1-dstolee@microsoft.com","subject":"Re: [RFC PATCH 00/13] Consolidate reachability logic","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-06-29T17:33:09Z","receivedAt":"2018-06-29T17:33:17Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"This RFC is available as a GitHub pull request [1].\n\nThanks,\n-Stolee\n\n[1] https://github.com/derrickstolee/git/pull/8\n"},{"id":"351380","messageId":"CAGZ79kZUYMob2G=RD6UXw3-=PgeP7s=e5XhpzPh9fcZjxh6t7g@mail.gmail.com","threadId":"48802","inReplyTo":"20180629161223.229661-2-dstolee@microsoft.com","subject":"Re: [RFC PATCH 01/13] commit-reach: move walk methods from commit.c","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-06-29T21:35:48Z","receivedAt":"2018-06-29T21:36:03Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"Hi Derrick,\n\n> +/* Remember to update object flag allocation in object.h */\n> +#define PARENT1 (1u<<16)\n> +#define PARENT2 (1u<<17)\n> +#define STALE (1u<<18)\n> +#define RESULT (1u<<19)\n\nSomething is up with whitespaces here, apart from that this patch\nlooks good.\n"},{"id":"351381","messageId":"CAGZ79kbMks+U94-==SB48DoSpYQOpa-bn_yJBjW7zH3cCCotng@mail.gmail.com","threadId":"48802","inReplyTo":"20180629161223.229661-4-dstolee@microsoft.com","subject":"Re: [RFC PATCH 03/13] commit-reach: move commit_contains from ref-filter","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-06-29T21:38:50Z","receivedAt":"2018-06-29T21:39:06Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"Hi Derrick,\n\n> +struct ref_filter_cbdata {\n> + struct ref_array *array;\n> + struct ref_filter *filter;\n> + struct contains_cache contains_cache;\n> + struct contains_cache no_contains_cache;\n\nThese members also seem to be moved whitespace-inconsistently.\nCould you clarify in the commit message that you re-indent them or\nwhat happened?\n"},{"id":"351382","messageId":"CAGZ79kbMSnTqyJY8Ds6gsyy9saCmWW3jdELsS9RkO2a3isP5zA@mail.gmail.com","threadId":"48802","inReplyTo":"20180629161223.229661-6-dstolee@microsoft.com","subject":"Re: [RFC PATCH 05/13] upload-pack: refactor ok_to_give_up()","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-06-29T21:44:23Z","receivedAt":"2018-06-29T21:44:39Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"Hi Derrick,\n\n> -static int ok_to_give_up(void)\n> +static int can_all_from_reach_with_flag(struct object_array from,\n\nThis method is hard to read; at first I thought you missed a word,\nbut then I realized that it asks \"can all 'from' members reach\n['something'] and we pass in the 'flag', so maybe\n\n all_reachable_flags\n\nor something?\n\n\n\n> /* no way to tell if this is reachable by\n\nWhile at it, you may want to fix the comment here.\n"},{"id":"351383","messageId":"CAGZ79kYR1yHxkcDTJh7YoNJydkE_WhdL1mdMKL3hDXgEk+gLxw@mail.gmail.com","threadId":"48802","inReplyTo":"20180629161223.229661-7-dstolee@microsoft.com","subject":"Re: [RFC PATCH 06/13] commit-reach: move can_all_from_reach_with_flag()","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-06-29T21:47:57Z","receivedAt":"2018-06-29T21:48:12Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"Hi Derrick,\n\n> +static int reachable(struct commit *from, int with_flag, int assign_flag, time_t min_commit_date)\n[...]\n> + if (commit->date < min_commit_date)\n> + continue;\n[...]\n\n> +int can_all_from_reach_with_flag(struct object_array from,\n> + int with_flag, int assign_flag,\n> + time_t min_commit_date)\n\nCan you expand on why we introduce the min_commit_date in the commit message?\n(It looks like a rebase error as I would have expected a move only,\ngiven the subject)\n\nThanks,\nStefan\n"},{"id":"351384","messageId":"xmqqbmbttg4i.fsf@gitster-ct.c.googlers.com","threadId":"48802","inReplyTo":"20180629161223.229661-2-dstolee@microsoft.com","subject":"Re: [RFC PATCH 01/13] commit-reach: move walk methods from commit.c","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-06-29T21:52:29Z","receivedAt":"2018-06-29T21:52:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> Signed-off-by: Derrick Stolee \n> ---\n> Makefile | 1 +\n> commit-reach.c | 359 +++++++++++++++++++++++++++++++++++++++++++++++++\n> commit-reach.h | 41 ++++++\n> commit.c | 358 ------------------------------------------------\n> 4 files changed, 401 insertions(+), 358 deletions(-)\n> create mode 100644 commit-reach.c\n\n\"blame -bs -C HEAD^..\" tells us that all lines except for the\ninitial #include of this file came from commit.c verbatim, which is\ngood for a \"move lines\" patch like this one.\n\n> create mode 100644 commit-reach.h\n\n\"blame -bs -C -C HEAD^..\" tells us, but \"blame -bs -C HEAD^..\" does\nnot tell us, that most of the lines are from commit.h, which is a\nvery bad sign. reduce_heads(), for example, have two duplicated\ndecl and depending on which header file is included, the source\nfiles will risk getting inconsistent definition once the headers\nstart to deviate from each other.\n\n"},{"id":"351385","messageId":"CAGZ79kZpZvaX7Jh7hXPWV+KPffx4m+5W-3Baqd6ggoNnq2Y9hw@mail.gmail.com","threadId":"48802","inReplyTo":"20180629161223.229661-8-dstolee@microsoft.com","subject":"Re: [RFC PATCH 07/13] test-reach","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-06-29T21:54:46Z","receivedAt":"2018-06-29T21:55:01Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, Jun 29, 2018 at 9:13 AM Derrick Stolee wrote:\n\n> +# Construct a grid-like commit graph with points (x,y)\n> +# with 1 <= x <= 10, 1 <= y <= 10, where (x,y) has\n> +# parents (x-1, y) and (x, y-1), keeping in mind that\n> +# we drop a parent if a coordinate is nonpositive.\n> +#\n> +# (10,10)\n> +# / \\\n> +# (10,9) (9,10)\n> +# / \\ / \\\n> +# (10,8) (9,9) (8,10)\n> +# / \\ / \\ / \\\n> +# ( continued...)\n> +# \\ / \\ / \\ /\n> +# (3,1) (2,2) (1,3)\n> +# \\ / \\ /\n> +# (2,1) (2,1)\n> +# \\ /\n> +# (1,1)\n> +#\n> +# We use branch 'comit-x-y' to refer to (x,y).\n> +# This grid allows interesting reachability and\n> +# non-reachability queries: (x,y) can reach (x',y')\n> +# if and only if x' <= x and y' <= y.\n\nThis is an interesting DAG, though not very common\nin reality (81 merges, 18 single parent commits,\none root with a depth of at most 10).\n\nIt reminds me of FELINE as that also has 2 independent numbers :)\n\nI guess it is easy to make up artificial test cases for that,\nbut I wonder if we want more variety for a generic reachability\ntest tool (e.g. long chains of parallel histories, octopus,\ndisconnected parts of the graph)\n\n> +test_expect_success 'setup' '\n[...]\n> + git commit-graph write --reachable\n\nIs this only to test the full commit-graph?, maybe we'd\nwant to write out the commit graph at (5,10) or so, such\nthat half the walking is tested without graph.\nWhat about author/commit dates?\n"},{"id":"351386","messageId":"xmqq36x5tfqu.fsf@gitster-ct.c.googlers.com","threadId":"48802","inReplyTo":"20180629161223.229661-4-dstolee@microsoft.com","subject":"Re: [RFC PATCH 03/13] commit-reach: move commit_contains from ref-filter","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-06-29T22:00:41Z","receivedAt":"2018-06-29T22:00:47Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> +int commit_contains(struct ref_filter *filter, struct commit *commit,\n> +\t\t struct commit_list *list, struct contains_cache *cache)\n\nThis is a symbol that is used to be file-local private. Is it named\nappropriately in the new context, which is \"globally visible\nthroughout the system\"? The convention to call into it now must be\ndocumented a lot better (e.g. how should list/cache etc are to be\nprepared?).\n\n> +{\n> +\tif (filter->with_commit_tag_algo)\n> +\t\treturn contains_tag_algo(commit, list, cache) == CONTAINS_YES;\n> +\treturn is_descendant_of(commit, list);\n> +}\n> diff --git a/commit-reach.h b/commit-reach.h\n> index 35ec9f0ddb..986fb388d5 100644\n> --- a/commit-reach.h\n> +++ b/commit-reach.h\n> @@ -2,42 +2,24 @@\n> #define __COMMIT_REACH_H__\n> \n> #include \"commit.h\"\n> +#include \"commit-slab.h\"\n> +#include \"ref-filter.h\"\n> \n> -struct commit_list *get_merge_bases_many(struct commit *one,\n> -\t\t\t\t\t int n,\n> -\t\t\t\t\t struct commit **twos);\n> -struct commit_list *get_merge_bases_many_dirty(struct commit *one,\n> -\t\t\t\t\t int n,\n> -\t\t\t\t\t struct commit **twos);\n> -struct commit_list *get_merge_bases(struct commit *one, struct commit *two);\n> -struct commit_list *get_octopus_merge_bases(struct commit_list *in);\n> -\n> -/* To be used only when object flags after this call no longer matter */\n> -struct commit_list *get_merge_bases_many_dirty(struct commit *one, int n, struct commit **twos);\n> -\n> -int is_descendant_of(struct commit *commit, struct commit_list *with_commit);\n> -int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit **reference);\n> -int in_merge_bases(struct commit *commit, struct commit *reference);\n> -\n> +int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);\n> \n> /*\n> - * Takes a list of commits and returns a new list where those\n> - * have been removed that can be reached from other commits in\n> - * the list. It is useful for, e.g., reducing the commits\n> - * randomly thrown at the git-merge command and removing\n> - * redundant commits that the user shouldn't have given to it.\n> - *\n> - * This function destroys the STALE bit of the commit objects'\n> - * flags.\n\nThe above removal of lines is sloppy; they are mostly duplicates in\ncommit.h that should never have been moved here in the first place,\nno?\n\n> + * Unknown has to be \"0\" here, because that's the default value for\n> + * contains_cache slab entries that have not yet been assigned.\n> */\n> -struct commit_list *reduce_heads(struct commit_list *heads);\n> +enum contains_result {\n> +\tCONTAINS_UNKNOWN = 0,\n> +\tCONTAINS_NO,\n> +\tCONTAINS_YES\n> +};\n\nAre these names specific enough, or were they OK in the limited\ncontext inside ref-filter but now are overly broad as globally\nvisible names? I suspect it might be the latter.\n"},{"id":"351387","messageId":"xmqqwouhs0xs.fsf@gitster-ct.c.googlers.com","threadId":"48802","inReplyTo":"20180629161223.229661-5-dstolee@microsoft.com","subject":"Re: [RFC PATCH 04/13] upload-pack: make reachable() more generic","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-06-29T22:05:51Z","receivedAt":"2018-06-29T22:05:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> In anticipation of moving the reachable() method to commit-reach.c,\n> modify the prototype to be more generic to flags known outside of\n> upload-pack.c. Also rename 'want' to 'from' to make the statement\n> more clear outside of the context of haves/wants negotiation.\n\nFWIW, I find the order of things done quite sensible. Rename,\nextend, etc., to prepare before moving and then move, not the other\nway around. You would want to do the same for some symbols named\noverly broadly you moved in earlier steps, too.\n\nAlso, if you will be making this function a global one in a later\nstep, now is the time to give it a good name suitable in the new\nglobal context before moving in this preparatory step. If it will\nbe file-scope static in its new home, then reachable() may still be\na good enough name. Let's keep reading...\n"},{"id":"351388","messageId":"CAGZ79kafYmpzYws7WQJO4-zmWwTBo9Pwo-PpkbmJF+Z9GzsvZA@mail.gmail.com","threadId":"48802","inReplyTo":"20180629161223.229661-9-dstolee@microsoft.com","subject":"Re: [RFC PATCH 08/13] test-reach: test reduce_heads()","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-06-29T22:06:52Z","receivedAt":"2018-06-29T22:07:07Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, Jun 29, 2018 at 9:13 AM Derrick Stolee wrote:\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> t/t6600-test-reach.sh | 26 ++++++++++++++++++++++++++\n> 1 file changed, 26 insertions(+)\n>\n> diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\n> index c9337b6b46..0f60db9c60 100755\n> --- a/t/t6600-test-reach.sh\n> +++ b/t/t6600-test-reach.sh\n> @@ -78,4 +78,30 @@ test_expect_success 'ref_newer:miss' '\n> test_reach_two_modes \"ref_newer\"\n> '\n>\n> +test_expect_success 'reduce_heads' '\n> + cat >input <<- EOF &&\n> + X:commit-1-10\n> + X:commit-2-8\n> + X:commit-3-6\n> + X:commit-4-4\n> + X:commit-1-7\n> + X:commit-2-5\n> + X:commit-3-3\n> + X:commit-5-1\n> + Y:commit-10-10\n> + Y:commit-3-10\n> + Y:commit-9-9\n> + Y:commit-8-1\n> + EOF\n> + printf \"reduce_heads(X):\\n\" >expect &&\n> + git rev-parse commit-5-1 >>expect &&\n\nSee 6ac767e5c00 (t6036, t6042: prefer test_cmp to sequences of test, 2018-05-24)\non how to avoid some forks here:\n\n git rev-parse >expect \\\n many HEADs or Tips &&\n"},{"id":"351392","messageId":"CAGZ79kYM2KF3sKbxWCJQd4mbXNs=0RJiT8x=GP2tAUg4969q4w@mail.gmail.com","threadId":"48802","inReplyTo":"20180629161223.229661-12-dstolee@microsoft.com","subject":"Re: [RFC PATCH 11/13] commit-reach: make can_all_from_reach... linear","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-06-29T23:18:31Z","receivedAt":"2018-06-29T23:20:17Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, Jun 29, 2018 at 9:13 AM Derrick Stolee wrote:\n>\n> The can_all_from_reach_with_flags() algorithm is currently quadratic in\n> the worst case, because it calls the reachable() method for every 'from'\n> without tracking which commits have already been walked or which can\n> already reach a commit in 'to'.\n>\n> Rewrite the algorithm to walk each commit a constant number of times.\n>\n> We also add some optimizations that should work for the main consumer of\n> this method: fetch negotitation (haves/wants).\n>\n> The first step includes using a depth-first-search (DFS) from each from\n> commit, sorted by ascending generation number. We do not walk beyond the\n> minimum generation number or the minimum commit date. This DFS is likely\n> to be faster than the existing reachable() method because we expect\n> previous ref values to be along the first-parent history.\n>\n> If we find a target commit, then we mark everything in the DFS stack as\n> a RESULT. This expands the set of targets for the other from commits. We\n> also mark the visited commits using 'assign_flag' to prevent re-walking\n> the same code.\n>\n> We still need to clear our flags at the end, which is why we will have a\n> total of three visits to each commit.\n>\n> Performance was measured on the Linux repository using\n> 'test-tool reach can_all_from_reach'. The input included rows seeded by\n> tag values. The \"small\" case included X-rows as v4.[0-9]* and Y-rows as\n> v3.[0-9]*. This mimics a (very large) fetch that says \"I have all major\n> v3 releases and want all major v4 releases.\" The \"large\" case included\n> X-rows as \"v4.*\" and Y-rows as \"v3.*\". This adds all release-candidate\n> tags to the set, which does not greatly increase the number of objects\n> that are considered, but does increase the number of 'from' commits,\n> demonstrating the quadratic nature of the previous code.\n>\n> Small Case\n> ----------\n>\n> Before: 1.45 s\n> After: 0.34 s\n>\n> Large Case\n> ----------\n>\n> Before: 5.83 s\n> After: 0.37 s\n>\n> Note how the time increases between the two cases in the two versions.\n> The new code increases relative to the number of commits that need to be\n> walked, but not directly relative to the number of 'from' commits.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> commit-reach.c | 122 ++++++++++++++++++++++++++++++-------------------\n> commit-reach.h | 3 +-\n> upload-pack.c | 5 +-\n> 3 files changed, 82 insertions(+), 48 deletions(-)\n>\n> diff --git a/commit-reach.c b/commit-reach.c\n> index 992ad5cdc7..8e24455d9f 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -530,64 +530,88 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,\n> return is_descendant_of(commit, list);\n> }\n>\n> -static int reachable(struct commit *from, int with_flag, int assign_flag, time_t min_commit_date)\n> +static int compare_commits_by_gen(const void *_a, const void *_b)\n> {\n> - struct prio_queue work = { compare_commits_by_commit_date };\n> + const struct commit *a = (const struct commit *)_a;\n> + const struct commit *b = (const struct commit *)_b;\n>\n> - prio_queue_put(&work, from);\n> - while (work.nr) {\n> - struct commit_list *list;\n> - struct commit *commit = prio_queue_get(&work);\n> -\n> - if (commit->object.flags & with_flag) {\n> - from->object.flags |= assign_flag;\n> - break;\n> - }\n> - if (!commit->object.parsed)\n> - parse_object(&commit->object.oid);\n> - if (commit->object.flags & TMP_MARK)\n> - continue;\n> - commit->object.flags |= TMP_MARK;\n> - if (commit->date < min_commit_date)\n> - continue;\n> - for (list = commit->parents; list; list = list->next) {\n> - struct commit *parent = list->item;\n> - if (!(parent->object.flags & TMP_MARK))\n> - prio_queue_put(&work, parent);\n> - }\n> - }\n> - from->object.flags |= TMP_MARK;\n> - clear_commit_marks(from, TMP_MARK);\n> - clear_prio_queue(&work);\n> - return (from->object.flags & assign_flag);\n> + if (a->generation < b->generation)\n> + return -1;\n> + if (a->generation > b->generation)\n> + return 1;\n> + return 0;\n> }\n>\n> int can_all_from_reach_with_flag(struct object_array *from,\n> int with_flag, int assign_flag,\n> - time_t min_commit_date)\n> + time_t min_commit_date,\n> + uint32_t min_generation)\n> {\n> + struct commit **list = NULL;\n> int i;\n> + int result = 1;\n>\n> + ALLOC_ARRAY(list, from->nr);\n> for (i = 0; i < from->nr; i++) {\n> - struct object *from_one = from->objects[i].item;\n> + list[i] = (struct commit *)from->objects[i].item;\n>\n> - if (from_one->flags & assign_flag)\n> - continue;\n> - from_one = deref_tag(from_one, \"a from object\", 0);\n> - if (!from_one || from_one->type != OBJ_COMMIT) {\n> - /* no way to tell if this is reachable by\n> - * looking at the ancestry chain alone, so\n> - * leave a note to ourselves not to worry about\n> - * this object anymore.\n> - */\n> - from->objects[i].item->flags |= assign_flag;\n> - continue;\n> - }\n> - if (!reachable((struct commit *)from_one, with_flag,\n> - assign_flag, min_commit_date))\n> + parse_commit(list[i]);\n> +\n> + if (list[i]->generation < min_generation)\n> return 0;\n> }\n> - return 1;\n> +\n> + QSORT(list, from->nr, compare_commits_by_gen);\n> +\n> + for (i = 0; i < from->nr; i++) {\n> + /* DFS from list[i] */\n> + struct commit_list *stack = NULL;\n> +\n> + list[i]->object.flags |= assign_flag;\n> + commit_list_insert(list[i], &stack);\n> +\n> + while (stack) {\n> + struct commit_list *parent;\n> +\n> + if (stack->item->object.flags & with_flag) {\n> + pop_commit(&stack);\n> + continue;\n> + }\n> +\n> + for (parent = stack->item->parents; parent; parent = parent->next) {\n> + if (parent->item->object.flags & (with_flag | RESULT))\n> + stack->item->object.flags |= RESULT;\n> +\n> + if (!(parent->item->object.flags & assign_flag)) {\n> + parent->item->object.flags |= assign_flag;\n> +\n> + parse_commit(parent->item);\n\nWe can use parse_commit here as it would print a warning and keep going?\n"},{"id":"351393","messageId":"CAGZ79kbVvto1uV0Rk2UbqLTeL2s21efdcwkEfEPZG+3pD5gwXg@mail.gmail.com","threadId":"48802","inReplyTo":"20180629161223.229661-14-dstolee@microsoft.com","subject":"Re: [RFC PATCH 13/13] commit-reach: use can_all_from_reach","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-06-29T23:21:06Z","receivedAt":"2018-06-29T23:21:21Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"Hi Derrick,\nOn Fri, Jun 29, 2018 at 9:13 AM Derrick Stolee wrote:\n>\n> The is_descendant_of method previously used in_merge_bases() to check if\n> the commit can reach any of the commits in the provided list. This had\n> two performance problems:\n>\n> 1. The performance is quadratic in worst-case.\n>\n> 2. A single in_merge_bases() call requires walking beyond the target\n> commit in order to find the full set of boundary commits that may be\n> merge-bases.\n>\n> The can_all_from_reach method avoids this quadratic behavior and can\n> limit the search beyond the target commits using generation numbers. It\n> requires a small prototype adjustment to stop using commit-date as a\n> cutoff, as that optimization is no longer appropriate here.\n>\n> Performance was meausured on a copy of the Linux repository using the\n> 'test-tool reach is_descendant_of' command using this input:\n>\n> A:v4.9\n> X:v4.10\n> X:v4.11\n> X:v4.12\n> X:v4.13\n> X:v4.14\n> X:v4.15\n> X:v4.16\n> X:v4.17\n> X.v3.0\n>\n> Note that this input is tailored to demonstrate the quadratic nature of\n> the previous method, as it will compute merge-bases for v4.9 versus all\n> of the later versions before checking against v4.1.\n>\n> Before: 0.31 s\n> After: 0.27 s\n>\n> Since we previously used the is_descendant_of method in the ref_newer\n> method, we also measured performance there using\n> 'test-tool reach ref_newer':\n>\n> Before: 0.12 s\n> After: 0.11 s\n>\n> Signed-off-by: Derrick Stolee \n> ---\n>\n> One thing I know is missing from this commit is a special-case to use\n> the old logic when there is no commit-graph present. The\n> can_all_from_reach() algorithm can be worse when we do not have good\n> generation number cutoffs. In the previous case of\n> can_all_from_reach_with_flags(), we already had an established pattern\n> of using commit date as a cutoff, so the generation number is only a\n> second cutoff and the algorithm cannot walk more commits than before.\n\nI like this series,\nThanks for writing it!\nStefan\n"},{"id":"351397","messageId":"74071f5d-af5c-a125-3125-f52dd0977cb4@gmail.com","threadId":"48802","inReplyTo":"CAGZ79kbMks+U94-==SB48DoSpYQOpa-bn_yJBjW7zH3cCCotng@mail.gmail.com","subject":"Re: [RFC PATCH 03/13] commit-reach: move commit_contains from ref-filter","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-06-30T01:32:22Z","receivedAt":"2018-06-30T01:32:28Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/29/2018 5:38 PM, Stefan Beller wrote:\n> Hi Derrick,\n>\n>> +struct ref_filter_cbdata {\n>> + struct ref_array *array;\n>> + struct ref_filter *filter;\n>> + struct contains_cache contains_cache;\n>> + struct contains_cache no_contains_cache;\n> These members also seem to be moved whitespace-inconsistently.\n> Could you clarify in the commit message that you re-indent them or\n> what happened?\n\nSorry, there appears to be something strange that happens when I paste \ninto vim that causes my whitespace to mess up, especially leading \nwhitespace. Usually `git rebase --whitespace=fix` fixes it.\n\nI'll be more careful in my next replay of the series.\n"},{"id":"351398","messageId":"bc1572df-8b56-9010-000f-d1c14a68c016@gmail.com","threadId":"48802","inReplyTo":"CAGZ79kYR1yHxkcDTJh7YoNJydkE_WhdL1mdMKL3hDXgEk+gLxw@mail.gmail.com","subject":"Re: [RFC PATCH 06/13] commit-reach: move can_all_from_reach_with_flag()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-06-30T01:35:18Z","receivedAt":"2018-06-30T01:35:25Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/29/2018 5:47 PM, Stefan Beller wrote:\n> Hi Derrick,\n>\n>> +static int reachable(struct commit *from, int with_flag, int assign_flag, time_t min_commit_date)\n> [...]\n>> + if (commit->date < min_commit_date)\n>> + continue;\n> [...]\n>\n>> +int can_all_from_reach_with_flag(struct object_array from,\n>> + int with_flag, int assign_flag,\n>> + time_t min_commit_date)\n> Can you expand on why we introduce the min_commit_date in the commit message?\n> (It looks like a rebase error as I would have expected a move only,\n> given the subject)\n\nThis is a case where this should have been two steps:\n\n1. Remove dependence on the global 'oldest_have' in upload-pack.c by \ncreating the min_commit_date parameter.\n\n2. Move the code from upload-pack.c to commit-reach.c.\n\nThanks,\n-Stolee\n"},{"id":"351399","messageId":"3fe0c247-3680-946d-b1d4-f30f85eb78a8@gmail.com","threadId":"48802","inReplyTo":"CAGZ79kZpZvaX7Jh7hXPWV+KPffx4m+5W-3Baqd6ggoNnq2Y9hw@mail.gmail.com","subject":"Re: [RFC PATCH 07/13] test-reach","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-06-30T01:40:22Z","receivedAt":"2018-06-30T01:40:27Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/29/2018 5:54 PM, Stefan Beller wrote:\n> On Fri, Jun 29, 2018 at 9:13 AM Derrick Stolee wrote:\n>\n>> +# Construct a grid-like commit graph with points (x,y)\n>> +# with 1 <= x <= 10, 1 <= y <= 10, where (x,y) has\n>> +# parents (x-1, y) and (x, y-1), keeping in mind that\n>> +# we drop a parent if a coordinate is nonpositive.\n>> +#\n>> +# (10,10)\n>> +# / \\\n>> +# (10,9) (9,10)\n>> +# / \\ / \\\n>> +# (10,8) (9,9) (8,10)\n>> +# / \\ / \\ / \\\n>> +# ( continued...)\n>> +# \\ / \\ / \\ /\n>> +# (3,1) (2,2) (1,3)\n>> +# \\ / \\ /\n>> +# (2,1) (2,1)\n>> +# \\ /\n>> +# (1,1)\n>> +#\n>> +# We use branch 'comit-x-y' to refer to (x,y).\n>> +# This grid allows interesting reachability and\n>> +# non-reachability queries: (x,y) can reach (x',y')\n>> +# if and only if x' <= x and y' <= y.\n> This is an interesting DAG, though not very common\n> in reality (81 merges, 18 single parent commits,\n> one root with a depth of at most 10).\n>\n> It reminds me of FELINE as that also has 2 independent numbers :)\n\nThe design of this graph is exactly so you (the test writer) can know if \ntwo commits can reach exactly by whether the two-dimensional keys are \ncomparable. It's wide enough that we can come up with interesting test \ncases for some of these walks, especially the have/wants negotiation.\n\n>\n> I guess it is easy to make up artificial test cases for that,\n> but I wonder if we want more variety for a generic reachability\n> test tool (e.g. long chains of parallel histories, octopus,\n> disconnected parts of the graph)\n>\n>> +test_expect_success 'setup' '\n> [...]\n>> + git commit-graph write --reachable\n> Is this only to test the full commit-graph?, maybe we'd\n> want to write out the commit graph at (5,10) or so, such\n> that half the walking is tested without graph.\n> What about author/commit dates?\n\nThere are a lot of ways we can get strange edge cases for commit-graph \nwalks, especially when we start being clever. This test case is only a \nstart to feeling like we have good coverage, but having a non-trivial \nwalk include both outputs (yes/no) for each method is a good start.\n\nI think after we get a basic coverage for these methods on this example, \nwe can add examples as necessary when we find tricky code paths that \nneed coverage.\n\nThanks,\n-Stolee\n"}]}