{"thread":{"id":"7373","subject":"[PATCH] Fix path-limited \"rev-list --bisect\" termination condition.","startedAt":"2007-03-23T21:57:28Z","lastAt":"2007-03-23T22:39:36Z","messageCount":4,"participants":["Junio C Hamano","Linus Torvalds"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"37842","messageId":"7vtzwboc6v.fsf@assigned-by-dhcp.cox.net","threadId":"7373","inReplyTo":null,"subject":"[PATCH] Fix path-limited \"rev-list --bisect\" termination condition.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-23T21:57:28Z","receivedAt":"2007-03-23T21:57:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"In a path-limited bisection, when the $bad commit is not\nchanging the limited path, and the number of suspects is 1, the\ncode miscounted and returned $bad from find_bisection(), which\nis not marked with TREECHANGE.  This is of course filtered by\nthe output routine, resulting in an empty output, in turn\ncausing git-bisect driver to say \"$bad was both good and bad\".\n\nIllustration.  Suppose you have these four commits, and only C\nchanges path P.  You know D is bad and A is good.\n\n\tA---B---C*--D\n\ngit-bisect driver runs this to find a bisection point:\n\n\t$ git rev-list --bisect A..D -- P\n\nwhich calls find_bisection() with B, C and D.  The set of\ncommits that is given to this function is the same set of\ncommits as rev-list without --bisect option and pathspec\nreturns.  Among them, only C is marked with TREECHANGE.  Let's\ncall the set of commits given to find_bisection() that are\nmarked with TREECHANGE (or all of them if no path limiter is in\neffect) \"the bisect set\".  In the above example, the size of the\nbisect set is 1 (contains only \"C\").\n\nFor each commit in its input, find_bisection() computes the\nnumber of commits it can reach in the bisect set.  For a commit\nin the bisect set, this number includes itself, so the number is\n1 or more.  This number is called \"depth\", and computed by\ncount_distance() function.\n\nWhen you have a bisect set of N commits, and a commit has depth\nD, how good is your bisection if you returned that commit?  How\ngood this bisection is can be measured by how many commits are\neffectively tested \"together\" by testing one commit.\n\nCurrently you have (N-1) untested commits (the tip of the bisect\nset, although it is included in the bisect set, is already known\nto be bad).  If the commit with depth D turns out to be bad,\nthen your next bisect set will have D commits and you will have\n(D-1) untested commits left, which means you tested (N-1)-(D-1)\n= (N-D) commits with this bisection.  If it turns out to be good, then\nyour next bisect set will have (N-D) commits, and you will have\n(N-D-1) untested commits left, which means you tested\n(N-1)-(N-D-1) = D commits with this bisection.\n\nTherefore, the goodness of this bisection is is min(N-D, D), and\nfind_bisection() function tries to find a commit that maximizes\nthis, by initializing \"closest\" variable to 0 and whenever a\ncommit with the goodness that is larger than the current\n\"closest\" is found, that commit and its goodness are remembered\nby updating \"closest\" variable.  The \"the commit with the best\ngoodness so far\" is kept in \"best\" variable, and is initialized\nto a commit that happens to be at the beginning of the list of\ncommits given to this function (which may or may not be in the\nbisect set when path-limit is in use).\n\nHowever, when N is 1, then the sole tree-changing commit has\ndepth of 1, and min(N-D, D) computes to 0.  This is not larger\nthan the initial value of \"closest\", and the \"so far the best\none\" commit is never replaced in the loop.\n\nWhen path-limit is not in use, this is not a problem, as any\ncommit in the input set is tree-changing.  But when path-limit\nis in use, and when the starting \"bad\" commit does not change\nthe specified path, it is not correct.  This is the first\nbug the patch fixes with a one-liner.\n\nHow many lines did I spend to describe this one-liner?\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n builtin-rev-list.c |    3 ++-\n 1 files changed, 2 insertions(+), 1 deletions(-)\n\ndiff --git a/builtin-rev-list.c b/builtin-rev-list.c\nindex c2db5a5..4f4b1d2 100644\n--- a/builtin-rev-list.c\n+++ b/builtin-rev-list.c\n@@ -180,7 +180,8 @@ static struct commit_list *find_bisection(struct commit_list *list)\n \t\t\tnr++;\n \t\tp = p->next;\n \t}\n-\tclosest = 0;\n+\n+\tclosest = -1;\n \tbest = list;\n \n \tfor (p = list; p; p = p->next) {\n-- \n1.5.1.rc1.651.g2ca06\n"},{"id":"37846","messageId":"Pine.LNX.4.64.0703231524520.6730@woody.linux-foundation.org","threadId":"7373","inReplyTo":"7vtzwboc6v.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Fix path-limited \"rev-list --bisect\" termination condition.","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-23T22:25:08Z","receivedAt":"2007-03-23T22:25:08Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 23 Mar 2007, Junio C Hamano wrote:\n> \n> How many lines did I spend to describe this one-liner?\n\nHeh. Looks good to me.\n\n\t\tLinus\n"},{"id":"37847","messageId":"7vps6zoal0.fsf@assigned-by-dhcp.cox.net","threadId":"7373","inReplyTo":"Pine.LNX.4.64.0703231524520.6730@woody.linux-foundation.org","subject":"Re: [PATCH] Fix path-limited \"rev-list --bisect\" termination condition.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-23T22:32:11Z","receivedAt":"2007-03-23T22:32:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Is this the only issue you know about with respect to the\nBISECT_NAMES?  You earlier said it was broken and suggested to\nremove it,...\n"},{"id":"37849","messageId":"Pine.LNX.4.64.0703231538270.6730@woody.linux-foundation.org","threadId":"7373","inReplyTo":"7vps6zoal0.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Fix path-limited \"rev-list --bisect\" termination condition.","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-23T22:39:36Z","receivedAt":"2007-03-23T22:39:36Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 23 Mar 2007, Junio C Hamano wrote:\n>\n> Is this the only issue you know about with respect to the\n> BISECT_NAMES?  You earlier said it was broken and suggested to\n> remove it,...\n\nThat ending condition was the only one I knew about. If you have checked \nthat it works now, I say \"keep it\". At worst, it just points to the wrong \ncommit because people gave the wrong list of filenames, but hey, let's \nburn that bridge when we get to it.\n\n\t\tLinus\n"}]}