{"thread":{"id":"48553","subject":"[RFC PATCH v3 1/2] Implement --first-parent for git rev-list --bisect","startedAt":"2018-05-23T12:00:56Z","lastAt":"2018-05-24T04:31:08Z","messageCount":2,"participants":["Tiago Botelho","Junio C Hamano"],"isPatch":true,"patchVersion":3,"patchTotal":2},"messages":[{"id":"348367","messageId":"20180523120028.36427-1-tiagonbotelho@hotmail.com","threadId":"48553","inReplyTo":null,"subject":"[RFC PATCH v3 1/2] Implement --first-parent for git rev-list --bisect","fromName":"Tiago Botelho","fromEmail":"tiagonbotelho@gmail.com","sentAt":"2018-05-23T12:00:28Z","receivedAt":"2018-05-23T12:00:56Z","isPatch":true,"sender":{"key":"tiagonbotelho@gmail.com","avatar":"https://gravatar.com/avatar/263ea75fe0d4aa4ac14fa9dd08b82955689b6769cf5d33599914ca4321a4597b?d=mp&s=160"},"body":"This will enable users to implement bisecting on first parents\nwhich can be useful for when the commits from a feature branch\nthat we want to merge are not always tested.\n\nSigned-off-by: Tiago Botelho <tiagonbotelho@hotmail.com>\n---\n bisect.c           | 53 +++++++++++++++++++++++++++++++----------------------\n bisect.h           |  3 ++-\n builtin/rev-list.c |  3 +++\n revision.c         |  3 ---\n 4 files changed, 36 insertions(+), 26 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 4eafc8262..f43713574 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -34,7 +34,7 @@ static const char *term_good;\n  * We care just barely enough to avoid recursing for\n  * non-merge entries.\n  */\n-static int count_distance(struct commit_list *entry)\n+static int count_distance(struct commit_list *entry, unsigned bisect_flags)\n {\n \tint nr = 0;\n \n@@ -49,10 +49,10 @@ static int count_distance(struct commit_list *entry)\n \t\tcommit->object.flags |= COUNTED;\n \t\tp = commit->parents;\n \t\tentry = p;\n-\t\tif (p) {\n+\t\tif (p && !(bisect_flags & BISECT_FIRST_PARENT)) {\n \t\t\tp = p->next;\n \t\t\twhile (p) {\n-\t\t\t\tnr += count_distance(p);\n+\t\t\t\tnr += count_distance(p, bisect_flags);\n \t\t\t\tp = p->next;\n \t\t\t}\n \t\t}\n@@ -82,15 +82,16 @@ static inline void weight_set(struct commit_list *elem, int weight)\n \t*((int*)(elem->item->util)) = weight;\n }\n \n-static int count_interesting_parents(struct commit *commit)\n+static int count_interesting_parents(struct commit *commit, unsigned bisect_flags)\n {\n \tstruct commit_list *p;\n \tint count;\n \n \tfor (count = 0, p = commit->parents; p; p = p->next) {\n-\t\tif (p->item->object.flags & UNINTERESTING)\n-\t\t\tcontinue;\n-\t\tcount++;\n+\t\tif (!(p->item->object.flags & UNINTERESTING))\n+\t\t    count++;\n+\t\tif (bisect_flags & BISECT_FIRST_PARENT)\n+\t\t\tbreak;\n \t}\n \treturn count;\n }\n@@ -117,10 +118,10 @@ static inline int halfway(struct commit_list *p, int nr)\n }\n \n #if !DEBUG_BISECT\n-#define show_list(a,b,c,d) do { ; } while (0)\n+#define show_list(a,b,c,d,e) do { ; } while (0)\n #else\n static void show_list(const char *debug, int counted, int nr,\n-\t\t      struct commit_list *list)\n+\t\t      struct commit_list *list, unsigned bisect_flags)\n {\n \tstruct commit_list *p;\n \n@@ -146,10 +147,14 @@ static void show_list(const char *debug, int counted, int nr,\n \t\telse\n \t\t\tfprintf(stderr, \"---\");\n \t\tfprintf(stderr, \" %.*s\", 8, oid_to_hex(&commit->object.oid));\n-\t\tfor (pp = commit->parents; pp; pp = pp->next)\n+\t\tfor (pp = commit->parents; pp; pp = pp->next) {\n \t\t\tfprintf(stderr, \" %.*s\", 8,\n \t\t\t\toid_to_hex(&pp->item->object.oid));\n \n+\t\t\tif (bisect_flags & BISECT_FIRST_PARENT)\n+\t\t\t\tbreak;\n+\t\t}\n+\n \t\tsubject_len = find_commit_subject(buf, &subject_start);\n \t\tif (subject_len)\n \t\t\tfprintf(stderr, \" %.*s\", subject_len, subject_start);\n@@ -267,13 +272,13 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\tunsigned flags = commit->object.flags;\n \n \t\tp->item->util = &weights[n++];\n-\t\tswitch (count_interesting_parents(commit)) {\n+\t\tswitch (count_interesting_parents(commit, bisect_flags)) {\n \t\tcase 0:\n \t\t\tif (!(flags & TREESAME)) {\n \t\t\t\tweight_set(p, 1);\n \t\t\t\tcounted++;\n \t\t\t\tshow_list(\"bisection 2 count one\",\n-\t\t\t\t\t  counted, nr, list);\n+\t\t\t\t\t  counted, nr, list, bisect_flags);\n \t\t\t}\n \t\t\t/*\n \t\t\t * otherwise, it is known not to reach any\n@@ -289,7 +294,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t}\n \t}\n \n-\tshow_list(\"bisection 2 initialize\", counted, nr, list);\n+\tshow_list(\"bisection 2 initialize\", counted, nr, list, bisect_flags);\n \n \t/*\n \t * If you have only one parent in the resulting set\n@@ -310,7 +315,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\tcontinue;\n \t\tif (weight(p) != -2)\n \t\t\tcontinue;\n-\t\tweight_set(p, count_distance(p));\n+\t\tweight_set(p, count_distance(p, bisect_flags));\n \t\tclear_distance(list);\n \n \t\t/* Does it happen to be at exactly half-way? */\n@@ -319,7 +324,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\tcounted++;\n \t}\n \n-\tshow_list(\"bisection 2 count_distance\", counted, nr, list);\n+\tshow_list(\"bisection 2 count_distance\", counted, nr, list, bisect_flags);\n \n \twhile (counted < nr) {\n \t\tfor (p = list; p; p = p->next) {\n@@ -329,9 +334,10 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\tif (0 <= weight(p))\n \t\t\t\tcontinue;\n \t\t\tfor (q = p->item->parents; q; q = q->next) {\n-\t\t\t\tif (q->item->object.flags & UNINTERESTING)\n-\t\t\t\t\tcontinue;\n-\t\t\t\tif (0 <= weight(q))\n+\t\t\t\tif (!(q->item->object.flags & UNINTERESTING))\n+\t\t\t\t\tif (0 <= weight(q))\n+\t\t\t\t\t\tbreak;\n+\t\t\t\tif (bisect_flags & BISECT_FIRST_PARENT)\n \t\t\t\t\tbreak;\n \t\t\t}\n \t\t\tif (!q)\n@@ -346,7 +352,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t\tweight_set(p, weight(q)+1);\n \t\t\t\tcounted++;\n \t\t\t\tshow_list(\"bisection 2 count one\",\n-\t\t\t\t\t  counted, nr, list);\n+\t\t\t\t\t  counted, nr, list, bisect_flags);\n \t\t\t}\n \t\t\telse\n \t\t\t\tweight_set(p, weight(q));\n@@ -357,7 +363,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t}\n \t}\n \n-\tshow_list(\"bisection 2 counted all\", counted, nr, list);\n+\tshow_list(\"bisection 2 counted all\", counted, nr, list, bisect_flags);\n \n \tif (!find_all)\n \t\treturn best_bisection(list, nr);\n@@ -372,7 +378,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches,\n \tstruct commit_list *list, *p, *best, *next, *last;\n \tint *weights;\n \n-\tshow_list(\"bisection 2 entry\", 0, 0, *commit_list);\n+\tshow_list(\"bisection 2 entry\", 0, 0, *commit_list, bisect_flags);\n \n \t/*\n \t * Count the number of total and tree-changing items on the\n@@ -395,7 +401,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches,\n \t\ton_list++;\n \t}\n \tlist = last;\n-\tshow_list(\"bisection 2 sorted\", 0, nr, list);\n+\tshow_list(\"bisection 2 sorted\", 0, nr, list, bisect_flags);\n \n \t*all = nr;\n \tweights = xcalloc(on_list, sizeof(*weights));\n@@ -962,6 +968,9 @@ int bisect_next_all(const char *prefix, int no_checkout)\n \tif (skipped_revs.nr)\n \t\tbisect_flags |= BISECT_FIND_ALL;\n \n+\tif (revs.first_parent_only)\n+\t\tbisect_flags |= BISECT_FIRST_PARENT;\n+\n \tfind_bisection(&revs.commits, &reaches, &all, bisect_flags);\n \trevs.commits = managed_skipped(revs.commits, &tried);\n \ndiff --git a/bisect.h b/bisect.h\nindex 1d40a33ad..5b7358fc9 100644\n--- a/bisect.h\n+++ b/bisect.h\n@@ -1,7 +1,8 @@\n #ifndef BISECT_H\n #define BISECT_H\n \n-#define BISECT_FIND_ALL\t\t(1u<<0)\n+#define BISECT_FIND_ALL\t\t  (1u<<0)\n+#define BISECT_FIRST_PARENT (1u<<1)\n \n /*\n  * Find bisection. If something is found, `reaches` will be the number of\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex 8752f5bbe..66439e1b3 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -538,6 +538,9 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \tif (bisect_list) {\n \t\tint reaches, all;\n \n+\t\tif (revs.first_parent_only)\n+\t\t\tbisect_flags |= BISECT_FIRST_PARENT;\n+\n \t\tfind_bisection(&revs.commits, &reaches, &all, bisect_flags);\n \n \t\tif (bisect_show_vars)\ndiff --git a/revision.c b/revision.c\nindex 4e0e193e5..b9d063805 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2474,9 +2474,6 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s\n \tif (!revs->reflog_info && revs->grep_filter.use_reflog_filter)\n \t\tdie(\"cannot use --grep-reflog without --walk-reflogs\");\n \n-\tif (revs->first_parent_only && revs->bisect)\n-\t\tdie(_(\"--first-parent is incompatible with --bisect\"));\n-\n \tif (revs->expand_tabs_in_log < 0)\n \t\trevs->expand_tabs_in_log = revs->expand_tabs_in_log_default;\n \n-- \n2.16.3\n\n"},{"id":"348402","messageId":"xmqqtvqxsmii.fsf@gitster-ct.c.googlers.com","threadId":"48553","inReplyTo":"20180523120028.36427-1-tiagonbotelho@hotmail.com","subject":"Re: [RFC PATCH v3 1/2] Implement --first-parent for git rev-list --bisect","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-05-24T04:31:01Z","receivedAt":"2018-05-24T04:31:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Tiago Botelho <tiagonbotelho@gmail.com> writes:\n\n> -static int count_interesting_parents(struct commit *commit)\n> +static int count_interesting_parents(struct commit *commit, unsigned bisect_flags)\n>  {\n>  \tstruct commit_list *p;\n>  \tint count;\n>  \n>  \tfor (count = 0, p = commit->parents; p; p = p->next) {\n> -\t\tif (p->item->object.flags & UNINTERESTING)\n> -\t\t\tcontinue;\n> -\t\tcount++;\n> +\t\tif (!(p->item->object.flags & UNINTERESTING))\n> +\t\t    count++;\n> +\t\tif (bisect_flags & BISECT_FIRST_PARENT)\n> +\t\t\tbreak;\n>  \t}\n>  \treturn count;\n>  }\n\nSince this change makes the function never return anything more than 1,...\n\n> @@ -310,7 +315,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n>  \t\t\tcontinue;\n>  \t\tif (weight(p) != -2)\n>  \t\t\tcontinue;\n> -\t\tweight_set(p, count_distance(p));\n> +\t\tweight_set(p, count_distance(p, bisect_flags));\n>  \t\tclear_distance(list);\n\n... this code will not be reached when in the first-parent mode,\nwhere we count the weight for merge commits the hard way.\n\nAm I reading the code correctly?  Not pointing out a problem; just\ndouble checking how the code works.\n\n> @@ -329,9 +334,10 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n>  \t\t\tif (0 <= weight(p))\n>  \t\t\t\tcontinue;\n>  \t\t\tfor (q = p->item->parents; q; q = q->next) {\n> -\t\t\t\tif (q->item->object.flags & UNINTERESTING)\n> -\t\t\t\t\tcontinue;\n> -\t\t\t\tif (0 <= weight(q))\n> +\t\t\t\tif (!(q->item->object.flags & UNINTERESTING))\n> +\t\t\t\t\tif (0 <= weight(q))\n> +\t\t\t\t\t\tbreak;\n> +\t\t\t\tif (bisect_flags & BISECT_FIRST_PARENT)\n>  \t\t\t\t\tbreak;\n>  \t\t\t}\n>  \t\t\tif (!q)\n>  \t\t\t\tcontinue;\n\nThis loop propagates the known weight of an ancestor through a\nsingle strand of pearls.\n\nWhen this loop is entered, any commit that has non-negative weight\nhas only one parent of interest, as we counted weight for all merges\nthe hard way and also weight for root and boundary commits, in the\nprevious loop.  The original goes through p's parents and see if an\ninteresting parent has non-negative weight (i.e. weight is known for\nthat parent), at which point break out of the loop, with q that is\nnon-NULL.  Immediately after the loop, q != NULL means we can now\ncompute weight for p based on q's weight.\n\nI think this patch breaks the logic.  When we are looking at a\ncommit 'p' whose weight is not known yet, we grab its first parent\nin 'q'.  Imagine that it is not an UNINTERESTING commit (i.e. a\ncommit whose weight matters when deciding the bisection) whose\nweight is not yet known.  With the updated code under the\nfirst-parent mode, we break out of the loop, 'q' pointing at the\ncommit whose weight is not yet known.  The computation done by the\ncode that immediately follows the above part is now broken, as it\nwill call weight(q) to get -1 and propagate it to p (or add 1 and\nset 0 to p), no?\n\nPerhaps something along this line may be closer to what we want:\n\n\tif (0 <= weight(p))\n\t\tcontinue; /* already known */\n\tfor (q = p->item->parents; q; q = q->next) {\n        \tif ((bisect_flags & BISECT_FIRST_PARENT)) {\n\t\t\tif (weight(q) < 0)\n\t\t\t\tq = NULL;\n\t\t\tbreak;\n\t\t}\n\t\tif (q->item->object.flags & UNINTERESTING)\n\t\t\tcontinue;\n\t\tif (0 <= weight(q))\n\t\t\tbreak;\n\t}\n\tif (!q)\n\t\tcontinue; /* parent's weight not yet usable */\n\nThat is, under the first-parent mode, we would pay attention only to\nthe first parent of 'p' and break out of this loop without even\nlooking at q->next.  If the weight of that parent is not known yet,\nwe mark that fact by clearing q to NULL and break out of the loop.\nIf the weight is known, we do not clear q, so we compute weight of p\nbased on weight(q).\n\nI am not offhand certain what should happen when p's first parent is\nuninteresting.  The updated count_interesting_parents() would have\nreturned 0 for p in such a case, so at this point of the code where\np's weight is unknown, its first parent can never be UNINTERESTING,\nI would think.\n"}]}