{"thread":{"id":"10186","subject":"[PATCH 1/2] rev-list: implement --bisect-all","startedAt":"2007-10-08T03:34:38Z","lastAt":"2007-10-23T21:33:15Z","messageCount":5,"participants":["Christian Couder","Johannes Schindelin","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"55150","messageId":"20071008053438.6a829b91.chriscool@tuxfamily.org","threadId":"10186","inReplyTo":null,"subject":"[PATCH 1/2] rev-list: implement --bisect-all","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2007-10-08T03:34:38Z","receivedAt":"2007-10-08T03:34:38Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"This is Junio's patch with some stuff to make --bisect-all\ncompatible with --bisect-vars.\n\nThis option makes it possible to see all the potential\nbisection points. The best ones are displayed first.\n\nSigned-off-by: Christian Couder <chriscool@tuxfamily.org>\n---\n builtin-rev-list.c |   98 +++++++++++++++++++++++++++++++++++++++++++++-------\n log-tree.c         |    2 +-\n log-tree.h         |    1 +\n 3 files changed, 87 insertions(+), 14 deletions(-)\n\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex 33726b8..0943b76 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -9,6 +9,7 @@\n #include \"revision.h\"\n #include \"list-objects.h\"\n #include \"builtin.h\"\n+#include \"log-tree.h\"\n \n /* bits #0-15 in revision.h */\n \n@@ -39,6 +40,7 @@ static const char rev_list_usage[] =\n \"  special purpose:\\n\"\n \"    --bisect\\n\"\n \"    --bisect-vars\"\n+\"    --bisect-all\"\n ;\n \n static struct rev_info revs;\n@@ -74,6 +76,7 @@ static void show_commit(struct commit *commit)\n \t\t\tparents = parents->next;\n \t\t}\n \t}\n+\tshow_decorations(commit);\n \tif (revs.commit_format == CMIT_FMT_ONELINE)\n \t\tputchar(' ');\n \telse\n@@ -278,6 +281,57 @@ static struct commit_list *best_bisection(struct commit_list *list, int nr)\n \treturn best;\n }\n \n+struct commit_dist {\n+\tstruct commit *commit;\n+\tint distance;\n+};\n+\n+static int compare_commit_dist(const void *a_, const void *b_)\n+{\n+\tstruct commit_dist *a, *b;\n+\n+\ta = (struct commit_dist *)a_;\n+\tb = (struct commit_dist *)b_;\n+\tif (a->distance != b->distance)\n+\t\treturn b->distance - a->distance; /* desc sort */\n+\treturn hashcmp(a->commit->object.sha1, b->commit->object.sha1);\n+}\n+\n+static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)\n+{\n+\tstruct commit_list *p;\n+\tstruct commit_dist *array = xcalloc(nr, sizeof(*array));\n+\tint cnt, i;\n+\n+\tfor (p = list, cnt = 0; p; p = p->next) {\n+\t\tint distance;\n+\t\tunsigned flags = p->item->object.flags;\n+\n+\t\tif (revs.prune_fn && !(flags & TREECHANGE))\n+\t\t\tcontinue;\n+\t\tdistance = weight(p);\n+\t\tif (nr - distance < distance)\n+\t\t\tdistance = nr - distance;\n+\t\tarray[cnt].commit = p->item;\n+\t\tarray[cnt].distance = distance;\n+\t\tcnt++;\n+\t}\n+\tqsort(array, cnt, sizeof(*array), compare_commit_dist);\n+\tfor (p = list, i = 0; i < cnt; i++) {\n+\t\tstruct name_decoration *r = xmalloc(sizeof(*r) + 100);\n+\t\tstruct object *obj = &(array[i].commit->object);\n+\n+\t\tsprintf(r->name, \"dist=%d\", array[i].distance);\n+\t\tr->next = add_decoration(&name_decoration, obj, r);\n+\t\tp->item = array[i].commit;\n+\t\tp = p->next;\n+\t}\n+\tif (p)\n+\t\tp->next = NULL;\n+\tfree(array);\n+\treturn list;\n+}\n+\n /*\n  * zero or positive weight is the number of interesting commits it can\n  * reach, including itself.  Especially, weight = 0 means it does not\n@@ -292,7 +346,8 @@ static struct commit_list *best_bisection(struct commit_list *list, int nr)\n  * or positive distance.\n  */\n static struct commit_list *do_find_bisection(struct commit_list *list,\n-\t\t\t\t\t     int nr, int *weights)\n+\t\t\t\t\t     int nr, int *weights,\n+\t\t\t\t\t     int find_all)\n {\n \tint n, counted;\n \tstruct commit_list *p;\n@@ -351,7 +406,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\tclear_distance(list);\n \n \t\t/* Does it happen to be at exactly half-way? */\n-\t\tif (halfway(p, nr))\n+\t\tif (!find_all && halfway(p, nr))\n \t\t\treturn p;\n \t\tcounted++;\n \t}\n@@ -389,19 +444,22 @@ static struct commit_list *do_find_bisection(struct commit_list *list,\n \t\t\t\tweight_set(p, weight(q));\n \n \t\t\t/* Does it happen to be at exactly half-way? */\n-\t\t\tif (halfway(p, nr))\n+\t\t\tif (!find_all && halfway(p, nr))\n \t\t\t\treturn p;\n \t\t}\n \t}\n \n \tshow_list(\"bisection 2 counted all\", counted, nr, list);\n \n-\t/* Then find the best one */\n-\treturn best_bisection(list, nr);\n+\tif (!find_all)\n+\t\treturn best_bisection(list, nr);\n+\telse\n+\t\treturn best_bisection_sorted(list, nr);\n }\n \n static struct commit_list *find_bisection(struct commit_list *list,\n-\t\t\t\t\t  int *reaches, int *all)\n+\t\t\t\t\t  int *reaches, int *all,\n+\t\t\t\t\t  int find_all)\n {\n \tint nr, on_list;\n \tstruct commit_list *p, *best, *next, *last;\n@@ -434,14 +492,13 @@ static struct commit_list *find_bisection(struct commit_list *list,\n \tweights = xcalloc(on_list, sizeof(*weights));\n \n \t/* Do the real work of finding bisection commit. */\n-\tbest = do_find_bisection(list, nr, weights);\n-\n+\tbest = do_find_bisection(list, nr, weights, find_all);\n \tif (best) {\n-\t\tbest->next = NULL;\n+\t\tif (!find_all)\n+\t\t\tbest->next = NULL;\n \t\t*reaches = weight(best);\n \t}\n \tfree(weights);\n-\n \treturn best;\n }\n \n@@ -468,6 +525,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \tint i;\n \tint read_from_stdin = 0;\n \tint bisect_show_vars = 0;\n+\tint bisect_find_all = 0;\n \n \tgit_config(git_default_config);\n \tinit_revisions(&revs, prefix);\n@@ -490,6 +548,11 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \t\t\tbisect_list = 1;\n \t\t\tcontinue;\n \t\t}\n+\t\tif (!strcmp(arg, \"--bisect-all\")) {\n+\t\t\tbisect_list = 1;\n+\t\t\tbisect_find_all = 1;\n+\t\t\tcontinue;\n+\t\t}\n \t\tif (!strcmp(arg, \"--bisect-vars\")) {\n \t\t\tbisect_list = 1;\n \t\t\tbisect_show_vars = 1;\n@@ -536,9 +599,11 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \tif (bisect_list) {\n \t\tint reaches = reaches, all = all;\n \n-\t\trevs.commits = find_bisection(revs.commits, &reaches, &all);\n+\t\trevs.commits = find_bisection(revs.commits, &reaches, &all,\n+\t\t\t\t\t      bisect_find_all);\n \t\tif (bisect_show_vars) {\n \t\t\tint cnt;\n+\t\t\tchar hex[41];\n \t\t\tif (!revs.commits)\n \t\t\t\treturn 1;\n \t\t\t/*\n@@ -550,15 +615,22 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \t\t\t * A bisect set of size N has (N-1) commits further\n \t\t\t * to test, as we already know one bad one.\n \t\t\t */\n-\t\t\tcnt = all-reaches;\n+\t\t\tcnt = all - reaches;\n \t\t\tif (cnt < reaches)\n \t\t\t\tcnt = reaches;\n+\t\t\tstrcpy(hex, sha1_to_hex(revs.commits->item->object.sha1));\n+\n+\t\t\tif (bisect_find_all) {\n+\t\t\t\ttraverse_commit_list(&revs, show_commit, show_object);\n+\t\t\t\tprintf(\"------\\n\");\n+\t\t\t}\n+\n \t\t\tprintf(\"bisect_rev=%s\\n\"\n \t\t\t       \"bisect_nr=%d\\n\"\n \t\t\t       \"bisect_good=%d\\n\"\n \t\t\t       \"bisect_bad=%d\\n\"\n \t\t\t       \"bisect_all=%d\\n\",\n-\t\t\t       sha1_to_hex(revs.commits->item->object.sha1),\n+\t\t\t       hex,\n \t\t\t       cnt - 1,\n \t\t\t       all - reaches - 1,\n \t\t\t       reaches - 1,\ndiff --git a/log-tree.c b/log-tree.c\nindex 2319154..f766758 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -15,7 +15,7 @@ static void show_parents(struct commit *commit, int abbrev)\n \t}\n }\n \n-static void show_decorations(struct commit *commit)\n+void show_decorations(struct commit *commit)\n {\n \tconst char *prefix;\n \tstruct name_decoration *decoration;\ndiff --git a/log-tree.h b/log-tree.h\nindex e82b56a..b33f7cd 100644\n--- a/log-tree.h\n+++ b/log-tree.h\n@@ -12,5 +12,6 @@ int log_tree_diff_flush(struct rev_info *);\n int log_tree_commit(struct rev_info *, struct commit *);\n int log_tree_opt_parse(struct rev_info *, const char **, int);\n void show_log(struct rev_info *opt, const char *sep);\n+void show_decorations(struct commit *commit);\n \n #endif\n-- \n1.5.3.4.208.g996ad\n"},{"id":"55152","messageId":"Pine.LNX.4.64.0710080442420.4174@racer.site","threadId":"10186","inReplyTo":"20071008053438.6a829b91.chriscool@tuxfamily.org","subject":"Re: [PATCH 1/2] rev-list: implement --bisect-all","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-10-08T03:44:09Z","receivedAt":"2007-10-08T03:44:09Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 8 Oct 2007, Christian Couder wrote:\n\n> This option makes it possible to see all the potential bisection points. \n> The best ones are displayed first.\n\nWould it not be better to pass --bisect-vars a list of commits that we do \nnot want to see?  It could then mark them as \"DUNNO\", and still just \noutput a single commit.\n\nIMHO such a logic does not belong into a shell script, but into the C \ncore.\n\nCiao,\nDscho\n"},{"id":"55158","messageId":"200710080708.46579.chriscool@tuxfamily.org","threadId":"10186","inReplyTo":"Pine.LNX.4.64.0710080442420.4174@racer.site","subject":"Re: [PATCH 1/2] rev-list: implement --bisect-all","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2007-10-08T05:08:45Z","receivedAt":"2007-10-08T05:08:45Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Hi Dscho,\n\nLe lundi 8 octobre 2007, Johannes Schindelin a écrit :\n> Hi,\n>\n> On Mon, 8 Oct 2007, Christian Couder wrote:\n> > This option makes it possible to see all the potential bisection\n> > points. The best ones are displayed first.\n>\n> Would it not be better to pass --bisect-vars a list of commits that we do\n> not want to see?  It could then mark them as \"DUNNO\", and still just\n> output a single commit.\n\nThe problem is that after --bisect-vars we already pass some \"good\" and then \na bad commit. So we have to use another flag like --bisect-dunno and put \nthe dunno commits after this one.\n\nThen there is the problem that revision.c reorders arguments and doesn't \nknow about \"--bisect-*\" flags. It is also used by a lot of other commands.\n\nAfter struggling with revision.c for some time, I thought it would be \nsimpler and safer to come up first with something in shell.\n\nAlso please note that in some cases we cannot just output a single commit, \nbecause we just dunno which commit is the first bad one.\n\n> IMHO such a logic does not belong into a shell script, but into the C\n> core.\n\nThere is a lot of the bisect logic implemented in git-bisect.sh already. The \nlong term plan is to rewrite it in C, but I am not sure that the \"dunno\" \nlogic should be the first part of it to be done in C.\n\nAlso I thought it was still fine to prototype new features in shell.\n\nBest regards,\nChristian.\n"},{"id":"55159","messageId":"Pine.LNX.4.64.0710080607180.4174@racer.site","threadId":"10186","inReplyTo":"200710080708.46579.chriscool@tuxfamily.org","subject":"Re: [PATCH 1/2] rev-list: implement --bisect-all","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-10-08T05:08:58Z","receivedAt":"2007-10-08T05:08:58Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 8 Oct 2007, Christian Couder wrote:\n\n> > IMHO such a logic does not belong into a shell script, but into the C \n> > core.\n> \n> There is a lot of the bisect logic implemented in git-bisect.sh already. \n> The long term plan is to rewrite it in C,\n\nOh?  Did I miss something?\n\n> but I am not sure that the \"dunno\" logic should be the first part of it \n> to be done in C.\n\nThe thing is, git-bisect is porcelain-ish.  And by having a lot of the \nfunctionality there, which is not really porcelain, but plumbing, you \nprevent other porcelains, such as git-gui or qgit, from using that \nfunction.\n\nWhich is bad.\n\nCiao,\nDscho\n"},{"id":"57028","messageId":"7vabq97bz8.fsf@gitster.siamese.dyndns.org","threadId":"10186","inReplyTo":"Pine.LNX.4.64.0710080607180.4174@racer.site","subject":"Re: [PATCH 1/2] rev-list: implement --bisect-all","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-10-23T21:33:15Z","receivedAt":"2007-10-23T21:33:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> On Mon, 8 Oct 2007, Christian Couder wrote:\n>\n>> but I am not sure that the \"dunno\" logic should be the first part of it \n>> to be done in C.\n>\n> The thing is, git-bisect is porcelain-ish.  And by having a lot of the \n> functionality there, which is not really porcelain, but plumbing, you \n> prevent other porcelains, such as git-gui or qgit, from using that \n> function.\n>\n> Which is bad.\n\nStill, it is good to prototype in the script while figuring out\nwhat the desired behaviour is, I would say.\n\nWhat I was hoping to see when I posted --bisect-all suggestion\nwas a bit different from what Christian did, by the way.\n\nIn addition to the bisect/skip-* that are filtered at the shell\nlevel, if you feed the list of commits that cannot be tested to\nthe bisection plumbing, you can affect the way the resulting\nlist from the --bisect-all is sorted.\n\nSuppose you have this (B is bad, G is good):\n\n           o---.........---o---Y---o---o---B\n          /                       /\n     G---o---.........---o---Z---X\n\nand one round of bisection picked X.  You find it untestable,\nand Y and Z both bisects the remaining set equally well.  In\nsuch a case, the current code sorts the resulting set, with Y\nand Z next to each other (because they are both closest to the\nmidway), and the Porcelain filters out X which is better than Y\nor Z.  You may end up picking Z.\n\nOften, when X is not testable, neither is Z.  We would be better\noff to avoid checking a commit close to what are known to be\nuntestable while there are other commits that are equally close\nto the midway.\n\nSo instead of sorting the list solely based on the mid-ness like\nthe current code does (i.e. compare_commit_dist()), we can tweak\ncommits' mid-ness value (i.e. best_bisection_sorted() computes\nit in distance variable) by penalizing it with the closeness of\nthe commit to known untestable commits.\n\nNaively, \"closeness\" of commit Z to commit X can be defined as\nsomething simple as \"rev-list Z...X | wc -l\".  The smaller the\nnumber, the closer the commits.\n"}]}