* Git bisect does not find commit introducing the bug @ 2017-02-17 22:29 Alex Hoffman 2017-02-17 23:21 ` Stephan Beyer 0 siblings, 1 reply; 26+ messages in thread From: Alex Hoffman @ 2017-02-17 22:29 UTC (permalink / raw) To: git Hi there, According to the documentation "git bisect" is designed "to find the commit that introduced a bug" . I have found a situation in which it does not returns the commit I expected. In order to reproduce the problem: 1. mkdir test; cd test; git clone https://github.com/entbugger/git-bisect-issue.git cd git-bisect-issue The tag "v.bad" is one bad version and tag "v.good" is the first good version. A good version is one having the line "FEATURE2" in file1.txt, which was introduced in "v.good". 2. Copy test scripts to another folder to make sure they are not overridden by 'git bisect' cp *.sh ../ cd .. ./search-bug-git.sh 3. Run ./search-bug-git.sh to search for the commit introducing the bug. It finds that the commit 04c6f4b9ed with the message "Feature 1" is the first one introducing the bug. First of all this is confusing, as this commit cannot be reached starting from "v.good". Then I expected the commit with the message "Introduce bug" to be returned by 'git bisect', as it is the first commit between "v.good" and "v.bad" that does not contain the line "FEATURE2" in file1.txt, which is what I understand by the commit "that introduced a bug" (cited from the manpage of git bisect). Thanks for looking to this, Best regards, VG ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-17 22:29 Git bisect does not find commit introducing the bug Alex Hoffman @ 2017-02-17 23:21 ` Stephan Beyer 2017-02-18 9:12 ` Johannes Sixt 0 siblings, 1 reply; 26+ messages in thread From: Stephan Beyer @ 2017-02-17 23:21 UTC (permalink / raw) To: Alex Hoffman, git Hi, On 02/17/2017 11:29 PM, Alex Hoffman wrote: > According to the documentation "git bisect" is designed "to find the > commit that introduced a bug" . > I have found a situation in which it does not returns the commit I expected. > In order to reproduce the problem: For the others who are too lazy to clone your repo and run the scripts, the history is like that (read from bottom to top) and I marked the commit found by git bisect and the on you expected: * 7a9e952 (bisect bad) <BAD> |\ | * 671cec2 <BAD> <--- expected | |\ | * | 04c6f4b <BAD> <--- found * | | 3915157 <GOOD> |\ \ \ | | |/ | |/| | * | f4154e9 (bisect good) <GOOD> | * | 85855bf <BAD> | |/ * | f1a36f5 <BAD> |/ * 1b7fb88 <BAD> The <BAD> and <GOOD> markers are set by your definition of what good and what bad commits are. > First of all this is confusing, as this commit cannot be reached > starting from "v.good". Hm, IMHO it shows that your example is pretty artificial (although you might have come across it in a real-world scenario): you introduced a new feature in f4154e9 (and it worked) and you broke that feature by making the merge 671cec2. However, the feature (that broke in 671cec2) did not even exist in 04c6f4b; so a test on the feature would not fail (leading to "bisect bad" as in the example), it would not exist (leading to "bisect skip"). And if we are not talking about passing or failing tests but about crashing, bisect finds the right thing: f4154e9 was not crashing, but 04c6f4b is crashing. Yes, it's not the commit that introduced the crash (which would be the first commit in the repo) but it's the first crashing commit after the one marked as good. So I'd consider this a feature or rather correct behavior, not a bug. In other words: bisect assumes that your repo is usually in a good state and you have a commit that changes it to a bad state. In your case you have a repo that is in a bad state and you have a commit that switches it to a good state and later you merge a bad-state branch and you have a bad state again. It is not made for that use-case, I think. Cheers Stephan ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-17 23:21 ` Stephan Beyer @ 2017-02-18 9:12 ` Johannes Sixt 2017-02-18 11:15 ` Alex Hoffman 0 siblings, 1 reply; 26+ messages in thread From: Johannes Sixt @ 2017-02-18 9:12 UTC (permalink / raw) To: Alex Hoffman; +Cc: Stephan Beyer, git Am 18.02.2017 um 00:21 schrieb Stephan Beyer: > On 02/17/2017 11:29 PM, Alex Hoffman wrote: > * 7a9e952 (bisect bad) <BAD> > |\ > | * 671cec2 <BAD> <--- expected > | |\ > | * | 04c6f4b <BAD> <--- found > * | | 3915157 <GOOD> > |\ \ \ > | | |/ > | |/| > | * | f4154e9 (bisect good) <GOOD> > | * | 85855bf <BAD> > | |/ > * | f1a36f5 <BAD> > |/ > * 1b7fb88 <BAD> > > The <BAD> and <GOOD> markers are set by your definition of what good and > what bad commits are. > > [...] > In other words: bisect assumes that your repo is usually in a good state > and you have a commit that changes it to a bad state. In your case you > have a repo that is in a bad state and you have a commit that switches > it to a good state and later you merge a bad-state branch and you have a > bad state again. It is not made for that use-case, I think. Correct. The assumption of bisection is that there is only one transition between GOOD and BAD. By violating that assumption, anything can happen. -- Hannes ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-18 9:12 ` Johannes Sixt @ 2017-02-18 11:15 ` Alex Hoffman 2017-02-18 14:18 ` Johannes Sixt 0 siblings, 1 reply; 26+ messages in thread From: Alex Hoffman @ 2017-02-18 11:15 UTC (permalink / raw) To: Johannes Sixt; +Cc: Stephan Beyer, git >> First of all this is confusing, as this commit cannot be reached >> starting from "v.good". > Hm, IMHO it shows that your example is pretty artificial (although you > might have come across it in a real-world scenario): you introduced a > new feature in f4154e9 (and it worked) and you broke that feature by > making the merge 671cec2. However, the feature (that broke in 671cec2) > did not even exist in 04c6f4b; so a test on the feature would not fail > (leading to "bisect bad" as in the example), it would not exist (leading > to "bisect skip"). No one commented the fact, that I find this very confusing. Don't you find this confusing? I will underline, that 'git bisect good v.good' will fail if the commit 'v.good' is not a parent of the bad commit, meaning there MUST be at least a path between 'v.good' and 'v.bad', thus I would expect it looks on this path ONLY. Beside that, this is what I understand by 'binary search' (to search on this commit path). You might find this example artificial, but I doubt git is/was intentionally designed to work with 'natural' examples only (no matter how you define 'natural' and 'artificial'). >> In other words: bisect assumes that your repo is usually in a good state >> and you have a commit that changes it to a bad state. In your case you >> have a repo that is in a bad state and you have a commit that switches >> it to a good state and later you merge a bad-state branch and you have a >> bad state again. It is not made for that use-case, I think. > Correct. The assumption of bisection is that there is only one transition between GOOD and BAD. By violating that assumption, anything can happen. I did not find that in the manpage or did I miss it? Why would someone assume that the commit graph looks in a certain way? I assume, that 'git bisect' was not thought through and that it considers the first directed path between v.good and v.bad, instead of all paths (in my example graph there are two such paths). I will also underline that git bisect was designed to work with multiple good commits and one bad commit (also multiple paths), but probably NOT with multiple paths between the same pair of good and bad commits. VG 2017-02-18 10:12 GMT+01:00 Johannes Sixt <j6t@kdbg.org>: > Am 18.02.2017 um 00:21 schrieb Stephan Beyer: >> >> On 02/17/2017 11:29 PM, Alex Hoffman wrote: >> * 7a9e952 (bisect bad) <BAD> >> |\ >> | * 671cec2 <BAD> <--- expected >> | |\ >> | * | 04c6f4b <BAD> <--- found >> * | | 3915157 <GOOD> >> |\ \ \ >> | | |/ >> | |/| >> | * | f4154e9 (bisect good) <GOOD> >> | * | 85855bf <BAD> >> | |/ >> * | f1a36f5 <BAD> >> |/ >> * 1b7fb88 <BAD> >> >> The <BAD> and <GOOD> markers are set by your definition of what good and >> what bad commits are. >> >> [...] >> In other words: bisect assumes that your repo is usually in a good state >> and you have a commit that changes it to a bad state. In your case you >> have a repo that is in a bad state and you have a commit that switches >> it to a good state and later you merge a bad-state branch and you have a >> bad state again. It is not made for that use-case, I think. > > > Correct. The assumption of bisection is that there is only one transition > between GOOD and BAD. By violating that assumption, anything can happen. > > -- Hannes > ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-18 11:15 ` Alex Hoffman @ 2017-02-18 14:18 ` Johannes Sixt 2017-02-18 18:36 ` Alex Hoffman 0 siblings, 1 reply; 26+ messages in thread From: Johannes Sixt @ 2017-02-18 14:18 UTC (permalink / raw) To: Alex Hoffman; +Cc: Stephan Beyer, git Am 18.02.2017 um 12:15 schrieb Alex Hoffman: > No one commented the fact, that I find this very confusing. Don't you > find this confusing? I will underline, that 'git bisect good v.good' > will fail if the commit 'v.good' is not a parent of the bad commit, > meaning there MUST be at least a path between 'v.good' and 'v.bad', > thus I would expect it looks on this path ONLY. Beside that, this is > what I understand by 'binary search' (to search on this commit path). But this is not how Git works. Git computes graph differences, i.e., it subtracts from the commits reachable from v.bad those that are reachable from v.good. This leaves more than just those on some path from v.good to v.bad. And it should work this way. Consider this history: --o--o--o--G--X \ \ x--x--x--x--X--B-- When you find B bad and G good, than any one of the x or X may have introduced the breakage, not just one of the X. >> Correct. The assumption of bisection is that there is only one >> transition between GOOD and BAD. By violating that assumption, >> anything can happen. > > I did not find that in the manpage or did I miss it? Why would someone > assume that the commit graph looks in a certain way? There is no restriction in the commit graph. The only restriction, actually assumption, is that there is *one* transition from good to bad and no transition from bad to good. Otherwise, bisection cannot work. > I assume, that > 'git bisect' was not thought through and that it considers the first > directed path between v.good and v.bad, instead of all paths (in my > example graph there are two such paths). I will also underline that > git bisect was designed to work with multiple good commits and one bad > commit (also multiple paths), but probably NOT with multiple paths > between the same pair of good and bad commits. Oh, IMO git bisect was well thought through. If it considered just paths from good to bad, it would not given the correct answer. See the example history above. Bisect authors would not have deemed that sufficiently good ;) -- Hannes ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-18 14:18 ` Johannes Sixt @ 2017-02-18 18:36 ` Alex Hoffman 2017-02-18 19:58 ` Christian Couder ` (3 more replies) 0 siblings, 4 replies; 26+ messages in thread From: Alex Hoffman @ 2017-02-18 18:36 UTC (permalink / raw) To: Johannes Sixt; +Cc: Stephan Beyer, git > But this is not how Git works. Git computes graph differences, i.e., it > subtracts from the commits reachable from v.bad those that are reachable > from v.good. This leaves more than just those on some path from v.good to > v.bad. And it should work this way. Consider this history: > > --o--o--o--G--X > \ \ > x--x--x--x--X--B-- > > When you find B bad and G good, than any one of the x or X may have > introduced the breakage, not just one of the X. > Thank you for clarifying how git bisect works. How did you find that out? Did you check the source code? If that is not documented in the man page may be it worth documenting it in order to avoid future confusion for other users. Let's consider your example with distinct names for nodes: --o1--o2--o3--G--X1 \ \ x1--x2--x3--x4--X1--B-- It makes sense that git bisect is expecting a single transition, as this is a precondition for a binary search to work. My definition of "the transition" is a commit with at least one of its parents as a good version, but the commit itself a bad version. I hope we agree that git bisect's mission is to search for this transition (as I suppose that most of people need such a functionality from git, if not exactly from git bisect). How could be x1 or x3 be the transition, if chances are that o1 is not a good version? Of course it would make sense to me if bisect would check o1 whether good and only then to check also x1-x3, but this is not what git makes (at least not in my initial example). If you consider that git bisect's mission is different from finding the transition, could you please explain what exact commit git bisect is supposed to return (ideally with terms from the graph theory) and when it makes sense to return that? Because I do not see any sense in looking in the path x1-x3 without knowing that those commits may be a transition. > Oh, IMO git bisect was well thought through. If it considered just paths > from good to bad, it would not given the correct answer. See the example > history above. Bisect authors would not have deemed that sufficiently good You definitely convinced me that git MUST search more than only in the paths between good and bad commits, as the good commit G does not have to be the first good commit (thank you for that). My problem/confusion is that it returns something that does not make sense to me, because it does not make sure it returns a transition. VG PS: thank you for continuing this discussion. ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-18 18:36 ` Alex Hoffman @ 2017-02-18 19:58 ` Christian Couder 2017-02-19 11:32 ` Alex Hoffman 2017-02-20 9:02 ` Junio C Hamano 2017-02-18 22:10 ` Philip Oakley ` (2 subsequent siblings) 3 siblings, 2 replies; 26+ messages in thread From: Christian Couder @ 2017-02-18 19:58 UTC (permalink / raw) To: Alex Hoffman; +Cc: Johannes Sixt, Stephan Beyer, git On Sat, Feb 18, 2017 at 7:36 PM, Alex Hoffman <spec@gal.ro> wrote: >> But this is not how Git works. Git computes graph differences, i.e., it >> subtracts from the commits reachable from v.bad those that are reachable >> from v.good. This leaves more than just those on some path from v.good to >> v.bad. And it should work this way. Consider this history: >> >> --o--o--o--G--X >> \ \ >> x--x--x--x--X--B-- >> >> When you find B bad and G good, than any one of the x or X may have >> introduced the breakage, not just one of the X. >> > > Thank you for clarifying how git bisect works. How did you find that > out? Did you check the source code? If that is not documented in the > man page may be it worth documenting it in order to avoid future > confusion for other users. At the end of the git-bisect man page (in the SEE ALSO section) there is a link to https://github.com/git/git/blob/master/Documentation/git-bisect-lk2009.txt which has a lot of details about how bisect works. > Let's consider your example with distinct names for nodes: > > --o1--o2--o3--G--X1 > \ \ > x1--x2--x3--x4--X1--B-- > > It makes sense that git bisect is expecting a single transition, as > this is a precondition for a binary search to work. My definition of > "the transition" is a commit with at least one of its parents as a > good version, but the commit itself a bad version. What if a commit C has one good parent A and one bad parent B? Isn't it more likely that the first bad commit is B instead of C? > I hope we agree > that git bisect's mission is to search for this transition (as I > suppose that most of people need such a functionality from git, if not > exactly from git bisect). The goal is to find the first bad commit, which is a commit that has only good parents. > How could be x1 or x3 be the transition, if > chances are that o1 is not a good version? As o1 is an ancestor of G, then o1 is considered good by the bisect algorithm. If it was bad, it would means that there is a transition from bad to good between o1 and G. But when a good commit is an ancestor of the bad commit, git bisect makes the assumption that there is no transition from bad to good in the graph. > Of course it would make > sense to me if bisect would check o1 whether good and only then to > check also x1-x3, but this is not what git makes (at least not in my > initial example). > > If you consider that git bisect's mission is different from finding > the transition, could you please explain what exact commit git bisect > is supposed to return (ideally with terms from the graph theory) and > when it makes sense to return that? Because I do not see any sense in > looking in the path x1-x3 without knowing that those commits may be a > transition. I hope it makes sense with the above explanations. >> Oh, IMO git bisect was well thought through. If it considered just paths >> from good to bad, it would not given the correct answer. See the example >> history above. Bisect authors would not have deemed that sufficiently good > > You definitely convinced me that git MUST search more than only in the > paths between good and bad commits, as the good commit G does not have > to be the first good commit (thank you for that). My problem/confusion > is that it returns something that does not make sense to me, because > it does not make sure it returns a transition. git bisect makes some assumptions that are true most of the time, so in practice it works well most of the time. ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-18 19:58 ` Christian Couder @ 2017-02-19 11:32 ` Alex Hoffman 2017-02-19 12:43 ` Alex Hoffman ` (2 more replies) 2017-02-20 9:02 ` Junio C Hamano 1 sibling, 3 replies; 26+ messages in thread From: Alex Hoffman @ 2017-02-19 11:32 UTC (permalink / raw) To: Christian Couder; +Cc: Johannes Sixt, Stephan Beyer, git > At the end of the git-bisect man page (in the SEE ALSO section) there > is a link to https://github.com/git/git/blob/master/Documentation/git-bisect-lk2009.txt > which has a lot of details about how bisect works. > Thanks for pointing out the SEE ALSO section. I think it makes sense to include/describe the entire algorithm in the man page itself, although I am not sure whether the graphs would be always correctly visually represented in the man page format. > The goal is to find the first bad commit, which is a commit that has > only good parents. OK, bisect's mission is more exact than I thought, which is good. M > As o1 is an ancestor of G, then o1 is considered good by the bisect algorithm. > If it was bad, it would means that there is a transition from bad to > good between o1 and G. > But when a good commit is an ancestor of the bad commit, git bisect > makes the assumption that there is no transition from bad to good in > the graph. The assumption that there is no transition from bad to good in the graph did not hold in my example and it does not hold when a feature was recently introduced and gets broken relative shortly afterwards. But I consider it is easy to change the algorithm not to assume, but rather to check it. > git bisect makes some assumptions that are true most of the time, so > in practice it works well most of the time. Whatever the definition of "most of the time" everyone might have, I think there is room for improvement. Below I am trying to make a small change to the current algorithm in order to deal with the assumption that sometimes does not hold (e.g in my example), by explicitly validating the check. > --o1--o2--o3--G--X1 > \ \ > x1--x2--x3--x4--X2--B-- > \ / > y1--y2--y3 Step 1a. (Unchanged) keep only the commits that: a) are ancestor of the "bad" commit (including the "bad" commit itself), b) are not ancestor of a "good" commit (excluding the "good" commits). The following graph results: x1--x2--x3--x4--X2--B-- \ / y1--y2--y3 Step 1b. (New) Mark all root commits of the resulting graph (i.e commits without parents) as unconfirmed (unconfirmed=node that has only bad parents). Remove all root commits that user already confirmed (e.g if user already marked its parent as good right before starting bisect run). For every unconfirmed root commit check if it has any good parents. In the example above check whether x1 has good parents. If the current root element has any parents and none of them is good, we can delete all paths from it until to the next commit that has a parent in the ancestors of GOOD. In the example above to delete the path x1-x3 and x1-y3. Also add new resulting root commits to the list of unconfirmed commits (commit x4). Otherwise mark it as confirmed. Step2. Continue the existing algorithm. If this improvement works (i.e you do not find any bugs in it and it is feasible to implement, which seems to me) the following would be its advantages: 1. An assumption less, as we explicitly check the assumption. 2. It might be quicker, because we delete parts of graph that cannot contain transitions. 3. It returns more exact results. VG ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-19 11:32 ` Alex Hoffman @ 2017-02-19 12:43 ` Alex Hoffman 2017-02-19 13:07 ` Christian Couder 2017-02-19 14:13 ` Johannes Sixt 2 siblings, 0 replies; 26+ messages in thread From: Alex Hoffman @ 2017-02-19 12:43 UTC (permalink / raw) To: Christian Couder; +Cc: Johannes Sixt, Stephan Beyer, git Below is a correction of the first proposed algorithm: >--o1--o2--o3--G --X1 > \ \ > x1--x2--x3--x4--X2--B-- > \ / > y1--y2--y3 > Step 1a. (Unchanged) keep only the commits that: a) are ancestor of the "bad" commit (including the "bad" commit itself), b) are not ancestor of a "good" commit (excluding the "good" commits). The following graph results: x1--x2--x3--x4--X2--B-- \ / y1--y2--y3 Step 1b. (New) Mark all commits of the resulting graph as unconfirmed (unconfirmed=node without good ancestors). Mark as confirmed all descendants of commits that user marked explicitly as good (e.g if user already marked its parent/grand parent/... as good right before starting bisect run). Step 1c. From all unconfirmed root commits build a set SET_GOOD of those with any good parents in the original graph (root commit = commit without parents in the resulting graph) and one SET_BAD for commits with only BAD parents. To build a set means to ask explicitly the user (or the command passed in git bisect run) whether any of its parents is good. In the example above find out whether x1 has any good parents or no parent at all and if so add it to SET_GOOD, otherwise to SET_BAD. Mark as confirmed each commit in SET_GOOD and all its descendants. For every commit in SET_BAD delete all paths from it until to the next confirmed commit. In the example above if x1 is in SET_BAD delete the path x1-x3 and x1-y3. If any new root commits result (commit x4), redo step 1c with them. Step2. Continue the existing algorithm. If this improvement works (i.e you do not find any bugs in it and it is feasible to implement, which seems to me) the following would be its advantages: 1. An assumption less, as we explicitly check the assumption. 2. It might be quicker, because we delete parts of graph that cannot contain transitions. 3. It returns more exact results. VG ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-19 11:32 ` Alex Hoffman 2017-02-19 12:43 ` Alex Hoffman @ 2017-02-19 13:07 ` Christian Couder 2017-02-19 14:13 ` Johannes Sixt 2 siblings, 0 replies; 26+ messages in thread From: Christian Couder @ 2017-02-19 13:07 UTC (permalink / raw) To: Alex Hoffman; +Cc: Johannes Sixt, Stephan Beyer, git On Sun, Feb 19, 2017 at 12:32 PM, Alex Hoffman <spec@gal.ro> wrote: >> At the end of the git-bisect man page (in the SEE ALSO section) there >> is a link to https://github.com/git/git/blob/master/Documentation/git-bisect-lk2009.txt >> which has a lot of details about how bisect works. > > Thanks for pointing out the SEE ALSO section. I think it makes sense > to include/describe the entire algorithm in the man page itself, > although I am not sure whether the graphs would be always correctly > visually represented in the man page format. It would possibly be very long to describe the entire algorithm, as it can be quite complex in some cases and it is difficult to understand without graphs. Maybe we could describe it, or some parts of it, in a separate document and provide links at different places in the man page. Anyway feel free to send patches. >> The goal is to find the first bad commit, which is a commit that has >> only good parents. > > OK, bisect's mission is more exact than I thought, which is good. M Good that you seem to agree with this goal. >> As o1 is an ancestor of G, then o1 is considered good by the bisect algorithm. >> If it was bad, it would means that there is a transition from bad to >> good between o1 and G. >> But when a good commit is an ancestor of the bad commit, git bisect >> makes the assumption that there is no transition from bad to good in >> the graph. > > The assumption that there is no transition from bad to good in the > graph did not hold in my example and it does not hold when a feature > was recently introduced and gets broken relative shortly afterwards. > But I consider it is easy to change the algorithm not to assume, but > rather to check it. I don't think the default algorithm will change soon, but there have been discussions for a long time about adding options to use different algorithms. For example people have been discussing a "--first-parent" option for many years as well as recently. It would bisect only along the first parents of the involved commits, and it could help find the merge commit that introduced a bug in the mainline. >> git bisect makes some assumptions that are true most of the time, so >> in practice it works well most of the time. > > Whatever the definition of "most of the time" everyone might have, I > think there is room for improvement. So feel free to send patches that would implement an option with the improvements you want. > Below I am trying to make a small > change to the current algorithm in order to deal with the assumption > that sometimes does not hold (e.g in my example), by explicitly > validating the check. > >> --o1--o2--o3--G--X1 >> \ \ >> x1--x2--x3--x4--X2--B-- >> \ / >> y1--y2--y3 > > Step 1a. (Unchanged) keep only the commits that: > > a) are ancestor of the "bad" commit (including the "bad" commit itself), > b) are not ancestor of a "good" commit (excluding the "good" commits). > > The following graph results: > x1--x2--x3--x4--X2--B-- > \ / > y1--y2--y3 I would say that the above graph is missing X1. > Step 1b. (New) Mark all root commits of the resulting graph (i.e > commits without parents) as unconfirmed (unconfirmed=node that has > only bad parents). Remove all root commits that user already confirmed > (e.g if user already marked its parent as good right before starting > bisect run). For every unconfirmed root commit check if it has any > good parents. In the example above check whether x1 has good parents. I think I understand the above... > If the current root element has any parents and none of them is > good, we can delete all paths from it until to the next commit that > has a parent in the ancestors of GOOD. In the example above to delete > the path x1-x3 and x1-y3. Also add new resulting root commits to the > list of unconfirmed commits (commit x4). > Otherwise mark it as confirmed. ... but I don't understand the logic of the above. If the root element has a bad parent, then it means that the "first bad commit" is either the bad parent or one of its ancestors, so it is not logical to delete it. In your example if x1 has one bad parent, this bad parent and its ancestors should be included in the search of the first bad commit. Otherwise the goal is not any more to find the first bad commit. PS: I saw that you have just sent another version of the algorithm, but I don't want to take a look at it right now. Anyway I am keeping my above comments as they might still be useful. > Step2. Continue the existing algorithm. > > > If this improvement works (i.e you do not find any bugs in it and it > is feasible to implement, which seems to me) As you describe it, I don't think it is compatible with the goal of finding the first bad commit. Also there are many things that are feasible to implement, but it doesn't mean that someone will soon make the effort to implement them in a way that looks good enough to be deemed worth merging into the current code base. > the following would be > its advantages: > 1. An assumption less, as we explicitly check the assumption. Checking can be costly. If the probability that the check will fail is very low, while the cost of checking is high, it is less costly on average to not check. > 2. It might be quicker, because we delete parts of graph that cannot > contain transitions. I don't agree that it's a good idea to delete what you suggest above. Or if you think that the goal should not be to find the "first bad commit" in the above case, then you should explain what the goal should be. > 3. It returns more exact results. Yeah, but checking every commit related to the good and bad commits would also return more exact results. (This can probably be done using `git rebase --exec ...` by the way.) One could even print a nice graph with all the good and bad commits. The problem is that it would not be efficient. If git bisect makes some assumptions, it is because they have been deemed reasonable and they have worked well in practice. It's also because the goal of git bisect is to be efficient, otherwise there would be no point in using a binary search algorithm in the first place. ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-19 11:32 ` Alex Hoffman 2017-02-19 12:43 ` Alex Hoffman 2017-02-19 13:07 ` Christian Couder @ 2017-02-19 14:13 ` Johannes Sixt 2017-02-19 19:05 ` Alex Hoffman 2 siblings, 1 reply; 26+ messages in thread From: Johannes Sixt @ 2017-02-19 14:13 UTC (permalink / raw) To: Alex Hoffman; +Cc: Christian Couder, Stephan Beyer, git Am 19.02.2017 um 12:32 schrieb Alex Hoffman: > The assumption that there is no transition from bad to good in the > graph did not hold in my example and it does not hold when a feature > was recently introduced and gets broken relative shortly afterwards. Then you must adjust your definition of "good": All commits that do not have the feature, yet, are "good": since they do not have the feature in the first place, they cannot have the breakage that you found in the feature. That is exactly the situation in your original example! But you constructed the condition of goodness in such a simplistic way (depending on the presence of a string), that it was impossible to distinguish between "does not have the feature at all" and "has the feature, but it is broken". -- Hannes ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-19 14:13 ` Johannes Sixt @ 2017-02-19 19:05 ` Alex Hoffman 2017-02-19 19:25 ` Jacob Keller 0 siblings, 1 reply; 26+ messages in thread From: Alex Hoffman @ 2017-02-19 19:05 UTC (permalink / raw) To: Johannes Sixt; +Cc: Christian Couder, Stephan Beyer, git > Then you must adjust your definition of "good": All commits that do not have > the feature, yet, are "good": since they do not have the feature in the > first place, they cannot have the breakage that you found in the feature. > > That is exactly the situation in your original example! But you constructed > the condition of goodness in such a simplistic way (depending on the > presence of a string), that it was impossible to distinguish between "does > not have the feature at all" and "has the feature, but it is broken". Johannes, thank you for correctly identifying the error in my logic. Indeed I was using the term 'bad' also for the commit without the feature. In order to find the commit introducing the bug in my example a new state is needed, which would make 'git bisect' a bit more complicated than the user 'most of the time' probably needs. Or do you think, it would make sense to ask the user for this state (if e.g 'git bisect' would be started with a new parameter)? ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-19 19:05 ` Alex Hoffman @ 2017-02-19 19:25 ` Jacob Keller 2017-02-20 7:38 ` Oleg Taranenko 0 siblings, 1 reply; 26+ messages in thread From: Jacob Keller @ 2017-02-19 19:25 UTC (permalink / raw) To: Alex Hoffman; +Cc: Johannes Sixt, Christian Couder, Stephan Beyer, git On Sun, Feb 19, 2017 at 11:05 AM, Alex Hoffman <spec@gal.ro> wrote: >> Then you must adjust your definition of "good": All commits that do not have >> the feature, yet, are "good": since they do not have the feature in the >> first place, they cannot have the breakage that you found in the feature. >> >> That is exactly the situation in your original example! But you constructed >> the condition of goodness in such a simplistic way (depending on the >> presence of a string), that it was impossible to distinguish between "does >> not have the feature at all" and "has the feature, but it is broken". > > Johannes, thank you for correctly identifying the error in my logic. > Indeed I was using the term 'bad' also for the commit without the > feature. In order to find the commit introducing the bug in my example > a new state is needed, which would make 'git bisect' a bit more > complicated than the user 'most of the time' probably needs. Or do you > think, it would make sense to ask the user for this state (if e.g 'git > bisect' would be started with a new parameter)? If a commit doesn't have the feature, then it is by definition, not containing a broken feature, and you can simply use the "good" state. There is no need for a different state. If you can't test the commit because it's broken in some other way, you can use "git bisect skip" but that isn't what you want in this case. Thanks, Jake ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-19 19:25 ` Jacob Keller @ 2017-02-20 7:38 ` Oleg Taranenko 2017-02-20 12:27 ` Jakub Narębski 0 siblings, 1 reply; 26+ messages in thread From: Oleg Taranenko @ 2017-02-20 7:38 UTC (permalink / raw) To: Jacob Keller Cc: Alex Hoffman, Johannes Sixt, Christian Couder, Stephan Beyer, git >>> Then you must adjust your definition of "good": All commits that do not have >>> the feature, yet, are "good": since they do not have the feature in the >>> first place, they cannot have the breakage that you found in the feature. >>> >>> That is exactly the situation in your original example! But you constructed >>> the condition of goodness in such a simplistic way (depending on the >>> presence of a string), that it was impossible to distinguish between "does >>> not have the feature at all" and "has the feature, but it is broken". >> >> Johannes, thank you for correctly identifying the error in my logic. >> Indeed I was using the term 'bad' also for the commit without the >> feature. In order to find the commit introducing the bug in my example >> a new state is needed, which would make 'git bisect' a bit more >> complicated than the user 'most of the time' probably needs. Or do you >> think, it would make sense to ask the user for this state (if e.g 'git >> bisect' would be started with a new parameter)? > If a commit doesn't have the feature, then it is by definition, not > containing a broken feature, and you can simply use the "good" state. > There is no need for a different state. If you can't test the commit > because it's broken in some other way, you can use "git bisect skip" > but that isn't what you want in this case. Commits missing feature == 'good' commit is a very confusing one. Looks like in real life it happens much often, then git developers can imagine. For multi-branch/multi-feature workflow it's pretty easy not to recognize whether it is missing or not developed yet, especially on retrospective view where cherry-picking/squashing/merging is being used. My experience shows most annoying bugs are generating after a heavy merge (evil merge) with conflicts resolutions, where developer is not involved in the knowing what happens on counterpart changes. Then feature can be disappeared after it was worked & tested in its own branches. @Alex, I'm pretty interesting in fixing this weird bisect behaviour as well, as far as I struggled on it last summer and continue struggling so far :) If you want we can join to your efforts on fixing. Cheers, Oleg ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-20 7:38 ` Oleg Taranenko @ 2017-02-20 12:27 ` Jakub Narębski 2017-02-20 13:50 ` Oleg Taranenko 0 siblings, 1 reply; 26+ messages in thread From: Jakub Narębski @ 2017-02-20 12:27 UTC (permalink / raw) To: Oleg Taranenko, Jacob Keller Cc: Alex Hoffman, Johannes Sixt, Christian Couder, Stephan Beyer, git W dniu 20.02.2017 o 08:38, Oleg Taranenko pisze: >>>> Then you must adjust your definition of "good": All commits that do not have >>>> the feature, yet, are "good": since they do not have the feature in the >>>> first place, they cannot have the breakage that you found in the feature. >>>> >>>> That is exactly the situation in your original example! But you constructed >>>> the condition of goodness in such a simplistic way (depending on the >>>> presence of a string), that it was impossible to distinguish between "does >>>> not have the feature at all" and "has the feature, but it is broken". >>> >>> Johannes, thank you for correctly identifying the error in my logic. >>> Indeed I was using the term 'bad' also for the commit without the >>> feature. In order to find the commit introducing the bug in my example >>> a new state is needed, which would make 'git bisect' a bit more >>> complicated than the user 'most of the time' probably needs. Or do you >>> think, it would make sense to ask the user for this state (if e.g 'git >>> bisect' would be started with a new parameter)? > >> If a commit doesn't have the feature, then it is by definition, not >> containing a broken feature, and you can simply use the "good" state. >> There is no need for a different state. If you can't test the commit >> because it's broken in some other way, you can use "git bisect skip" >> but that isn't what you want in this case. > > Commits missing feature == 'good' commit is a very confusing one. Nowadays you can change the names for 'old' and 'new' with `git bisect terms`. HTH. > Looks like in real life it happens much often, then git developers can > imagine. For multi-branch/multi-feature workflow it's pretty easy not > to recognize whether it is missing or not developed yet, especially on > retrospective view where cherry-picking/squashing/merging is being > used. My experience shows most annoying bugs are generating after a > heavy merge (evil merge) with conflicts resolutions, where developer > is not involved in the knowing what happens on counterpart changes. > Then feature can be disappeared after it was worked & tested in its > own branches. Good to know about this problem. > @Alex, I'm pretty interesting in fixing this weird bisect behaviour as > well, as far as I struggled on it last summer and continue struggling > so far :) If you want we can join to your efforts on fixing. Anyway, I don't think it is feasible to weaken the assumption that there is only one transition from 'old' ('good') to 'new' ('bad'); this is what allows O(log(N)) operations. See bisection method of root finding, that is finding zeros of a continuous function. Best, -- Jakub Narębski ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-20 12:27 ` Jakub Narębski @ 2017-02-20 13:50 ` Oleg Taranenko 2017-02-20 20:31 ` Alex Hoffman 0 siblings, 1 reply; 26+ messages in thread From: Oleg Taranenko @ 2017-02-20 13:50 UTC (permalink / raw) To: Jakub Narębski Cc: Jacob Keller, Alex Hoffman, Johannes Sixt, Christian Couder, Stephan Beyer, git > Anyway, I don't think it is feasible to weaken the assumption that there > is only one transition from 'old' ('good') to 'new' ('bad'); this is > what allows O(log(N)) operations. See bisection method of root finding, > that is finding zeros of a continuous function. I don't intended to change default behaviour of git bisect, I can estimate what drawback it could bring. I'd rather implement something like git bisect start --bisect-strategy=missing-feature by default current state is being used. git config value would be also useful. Oleg ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-20 13:50 ` Oleg Taranenko @ 2017-02-20 20:31 ` Alex Hoffman 2017-02-20 20:35 ` Jakub Narębski 0 siblings, 1 reply; 26+ messages in thread From: Alex Hoffman @ 2017-02-20 20:31 UTC (permalink / raw) To: Oleg Taranenko Cc: Jakub Narębski, Jacob Keller, Johannes Sixt, Christian Couder, Stephan Beyer, git I see two different problems each with a different assumption (see the definition of "bisectable" in the email of Junio C Hamano): 1. (Current) Assume the entire history graph is bisectable. DO: Search where in the entire graph the first 'trait'/transition occurs. 2. (New) Assume only the graph between one good commit and one bad commit is bisectable. DO: Search where the first transition occurs in the graph between these two commits. It seems that the real world needs a solution also for the second problem (example if the good commit is the FIRST good commit of a feature or if the good commit is not the first good commit, but you definitely know, that it broke first somewhere in between the good and bad commit). I find the way to go as Oleg proposed is gittish enough (with a new parameter --strategy). Beside I would underline that also the second problem is a bisect problem, just for another graph, thus it makes perfect sense to extend 'git bisect' for this. Does that look reasonably? ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-20 20:31 ` Alex Hoffman @ 2017-02-20 20:35 ` Jakub Narębski 2017-02-20 20:39 ` Alex Hoffman 2017-02-20 22:24 ` Philip Oakley 0 siblings, 2 replies; 26+ messages in thread From: Jakub Narębski @ 2017-02-20 20:35 UTC (permalink / raw) To: Alex Hoffman, Oleg Taranenko Cc: Jacob Keller, Johannes Sixt, Christian Couder, Stephan Beyer, git W dniu 20.02.2017 o 21:31, Alex Hoffman pisze: > I see two different problems each with a different assumption (see the > definition of "bisectable" in the email of Junio C Hamano): > > 1. (Current) Assume the entire history graph is bisectable. DO: Search > where in the entire graph the first 'trait'/transition occurs. > > 2. (New) Assume only the graph between one good commit and one bad > commit is bisectable. DO: Search where the first transition occurs in > the graph between these two commits. If `git bisect` is/would be affected by `git log` history-related options then this is what `--strict-ancestor` option gives/would give. -- Jakub Narębski ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-20 20:35 ` Jakub Narębski @ 2017-02-20 20:39 ` Alex Hoffman 2017-02-20 22:24 ` Philip Oakley 1 sibling, 0 replies; 26+ messages in thread From: Alex Hoffman @ 2017-02-20 20:39 UTC (permalink / raw) To: Jakub Narębski Cc: Oleg Taranenko, Jacob Keller, Johannes Sixt, Christian Couder, Stephan Beyer, git > If `git bisect` is/would be affected by `git log` history-related options > then this is what `--strict-ancestor` option gives/would give. Exactly my thoughts. All that needs to be changed in the 2nd problem is the graph where to search. But first we must agree about the usefulness of the 2nd problem. Any thoughts/comments/votes for/against? ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-20 20:35 ` Jakub Narębski 2017-02-20 20:39 ` Alex Hoffman @ 2017-02-20 22:24 ` Philip Oakley 2017-02-21 19:40 ` Alex Hoffman 1 sibling, 1 reply; 26+ messages in thread From: Philip Oakley @ 2017-02-20 22:24 UTC (permalink / raw) To: Alex Hoffman, Oleg Taranenko, Jakub Narębski Cc: Jacob Keller, Johannes Sixt, Christian Couder, Stephan Beyer, git From: "Jakub Narębski" <jnareb@gmail.com> >W dniu 20.02.2017 o 21:31, Alex Hoffman pisze: >> I see two different problems each with a different assumption (see the >> definition of "bisectable" in the email of Junio C Hamano): >> >> 1. (Current) Assume the entire history graph is bisectable. DO: Search >> where in the entire graph the first 'trait'/transition occurs. >> >> 2. (New) Assume only the graph between one good commit and one bad >> commit is bisectable. DO: Search where the first transition occurs in >> the graph between these two commits. > > If `git bisect` is/would be affected by `git log` history-related options > then this is what `--strict-ancestor` option gives/would give. > isn't that spelt `--ancestry-path` ? (--ancestry-path has it's own issues such as needing an --first-parent-show option, but that's possibly a by the by) -- Philip ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-20 22:24 ` Philip Oakley @ 2017-02-21 19:40 ` Alex Hoffman 2017-02-21 22:39 ` Philip Oakley 0 siblings, 1 reply; 26+ messages in thread From: Alex Hoffman @ 2017-02-21 19:40 UTC (permalink / raw) To: Philip Oakley Cc: Oleg Taranenko, Jakub Narębski, Jacob Keller, Johannes Sixt, Christian Couder, Stephan Beyer, git > isn't that spelt `--ancestry-path` ? > (--ancestry-path has it's own issues such as needing an --first-parent-show > option, but that's possibly a by the by) Indeed it is spelled `--ancestry-path`. And interestingly enough you may use it multiple times with the wanted effect in our case (e.g when the user has multiple good commit and a single bad commit before running the bisect itself). Also it is `--first-parent` (not `--first-parent-show`), but I do not understand why do we need this option? What kind of issues does `--ancestry-path` have? Best regards, VG ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-21 19:40 ` Alex Hoffman @ 2017-02-21 22:39 ` Philip Oakley 0 siblings, 0 replies; 26+ messages in thread From: Philip Oakley @ 2017-02-21 22:39 UTC (permalink / raw) To: Alex Hoffman Cc: Oleg Taranenko, Jakub Narębski, Jacob Keller, Johannes Sixt, Christian Couder, Stephan Beyer, git From: "Alex Hoffman" <spec@gal.ro> >> isn't that spelt `--ancestry-path` ? >> (--ancestry-path has it's own issues such as needing >> an --first-parent-show >> option, but that's possibly a by the by) > > Indeed it is spelled `--ancestry-path`. And interestingly enough you > may use it multiple times with the wanted effect in our case (e.g when > the user has multiple good commit and a single bad commit before > running the bisect itself). > Also it is `--first-parent` (not `--first-parent-show`), My spelling was deliberate ;-) If you use the currently coded --first-parent with a properly relevant commit for --ancestry-path then you get nothing. The purpose of ancestry-path is to find the ancestry chain that deviates from being a first-parent traversal [1], but the first-parent want to hold the walk to just the first parent chain - a contradiction. Adding the -show at the end is my attempt to indicate that it is for the second aspect, that of selecting which commits to show/use. I had an initial discussion back at [2], but failed then too. > but I do not understand why do we need this > option? What kind of issues does `--ancestry-path` have? > > Best regards, > VG > -- Philip [1] \git\Documentation\technical\api-revision-walking.txt ["two diff_options, one for path limiting, another for output"] [2] https://public-inbox.org/git/2FA1998250474E76A386B82AD635E56A@PhilipOakley/ ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-18 19:58 ` Christian Couder 2017-02-19 11:32 ` Alex Hoffman @ 2017-02-20 9:02 ` Junio C Hamano 1 sibling, 0 replies; 26+ messages in thread From: Junio C Hamano @ 2017-02-20 9:02 UTC (permalink / raw) To: Christian Couder; +Cc: Alex Hoffman, Johannes Sixt, Stephan Beyer, git Christian Couder <christian.couder@gmail.com> writes: > git bisect makes some assumptions that are true most of the time, so > in practice it works well most of the time. I think we need to clarify the documentation and ask you to stop using such fuzzy phrases like "assumptions" and "most of the time" ;-). For bisection to work, "git bisect" requires a very simple thing, which is that your history is bisectable wrt one particular "trait", i.e. what you are interested in (e.g. the trait may be "the commit has this feature in a broken form"). What does it mean for a history to be "bisectable", then? A bisectable history has commits with the "trait" and commits without the "trait". Given any commit with the "trait", all commits that are decendant of such commit must have the "trait". Also given any commit without the "trait", all commits that are ancestor of such a commit must not have the "trait". And your goal is to find one commit with the "trait" whose direct parent commits all lack the "trait". If and only if you can formulate your problem into the above form, "git bisect" can help you by not requiring you to check each and every commit in the history. Depending on the way you define the "trait", your history may not be bisectable, but by formulating the "trait" carefully, many such history can be made bisectable. In the "Recently some commit broke feature X. Before then the feature used to work. In an ancient past, the feature did not even exist" example, if you set "trying to use feature X breaks" as the "trait", your history is not bisectable unless you ignore the ancient part that did not even have the feature. If you restate your "trait" to "feature X does not exist in a broken form", however, the history becomes bisectable. Historically, we called commits with "trait" BAD and others GOOD, because bisection was used primarily to hunt for bugs. It may be easier to understand if the user thinks of commits without "trait" as OLD (i.e. commits in the older part of the history are not yet contaminated), and commits with "trait" as NEW (i.e. at some point, there is an event to introduce the "trait" and newer part of the history is contaminated by that event ever since). ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-18 18:36 ` Alex Hoffman 2017-02-18 19:58 ` Christian Couder @ 2017-02-18 22:10 ` Philip Oakley 2017-02-18 22:36 ` Hilco Wijbenga 2017-02-18 22:37 ` Johannes Sixt 3 siblings, 0 replies; 26+ messages in thread From: Philip Oakley @ 2017-02-18 22:10 UTC (permalink / raw) To: Alex Hoffman, Johannes Sixt; +Cc: Stephan Beyer, git From: "Alex Hoffman" <spec@gal.ro> >> But this is not how Git works. Git computes graph differences, i.e., it >> subtracts from the commits reachable from v.bad those that are reachable >> from v.good. This leaves more than just those on some path from v.good to >> v.bad. And it should work this way. Consider this history: >> >> --o--o--o--G--X >> \ \ >> x--x--x--x--X--B-- >> >> When you find B bad and G good, than any one of the x or X may have >> introduced the breakage, not just one of the X. >> > > Thank you for clarifying how git bisect works. How did you find that > out? Did you check the source code? If that is not documented in the > man page may be it worth documenting it in order to avoid future > confusion for other users. Any suggestions for improving the documentation are always worthwhile. As someone who asked, what extra info would have helped? Even beetter if it looks like a patch ;-) > > Let's consider your example with distinct names for nodes: > > --o1--o2--o3--G--X1 > \ \ > x1--x2--x3--x4--X1--B-- > > It makes sense that git bisect is expecting a single transition, as > this is a precondition for a binary search to work. My definition of > "the transition" is a commit with at least one of its parents as a > good version, but the commit itself a bad version. I hope we agree > that git bisect's mission is to search for this transition (as I > suppose that most of people need such a functionality from git, if not > exactly from git bisect). How could be x1 or x3 be the transition, if > chances are that o1 is not a good version? Of course it would make > sense to me if bisect would check o1 whether good and only then to > check also x1-x3, but this is not what git makes (at least not in my > initial example). > > If you consider that git bisect's mission is different from finding > the transition, could you please explain what exact commit git bisect > is supposed to return (ideally with terms from the graph theory) and > when it makes sense to return that? Because I do not see any sense in > looking in the path x1-x3 without knowing that those commits may be a > transition. > > >> Oh, IMO git bisect was well thought through. If it considered just paths >> from good to bad, it would not given the correct answer. See the example >> history above. Bisect authors would not have deemed that sufficiently >> good > > You definitely convinced me that git MUST search more than only in the > paths between good and bad commits, as the good commit G does not have > to be the first good commit (thank you for that). My problem/confusion > is that it returns something that does not make sense to me, because > it does not make sure it returns a transition. > > VG > > PS: thank you for continuing this discussion. > -- Philip ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-18 18:36 ` Alex Hoffman 2017-02-18 19:58 ` Christian Couder 2017-02-18 22:10 ` Philip Oakley @ 2017-02-18 22:36 ` Hilco Wijbenga 2017-02-18 22:37 ` Johannes Sixt 3 siblings, 0 replies; 26+ messages in thread From: Hilco Wijbenga @ 2017-02-18 22:36 UTC (permalink / raw) To: Alex Hoffman; +Cc: Johannes Sixt, Stephan Beyer, Git Users On 18 February 2017 at 10:36, Alex Hoffman <spec@gal.ro> wrote: > You definitely convinced me that git MUST search more than only in the > paths between good and bad commits, as the good commit G does not have > to be the first good commit (thank you for that). My problem/confusion > is that it returns something that does not make sense to me, because > it does not make sure it returns a transition. If multiple transitions from GOOD to BAD happen, then I don't see how binary search is useful/possible. The same is true for a simple list of numbers, say, 1 5 6 2 3 4. You can't use binary search here because you can't "throw away" all numbers to the left (or right) of your pivot. Or am I missing your point? ^ permalink raw reply [flat|nested] 26+ messages in thread
* Re: Git bisect does not find commit introducing the bug 2017-02-18 18:36 ` Alex Hoffman ` (2 preceding siblings ...) 2017-02-18 22:36 ` Hilco Wijbenga @ 2017-02-18 22:37 ` Johannes Sixt 3 siblings, 0 replies; 26+ messages in thread From: Johannes Sixt @ 2017-02-18 22:37 UTC (permalink / raw) To: Alex Hoffman; +Cc: Stephan Beyer, git Am 18.02.2017 um 19:36 schrieb Alex Hoffman: > Let's consider your example with distinct names for nodes: > > --o1--o2--o3--G--X1 > \ \ > x1--x2--x3--x4--X2--B-- > > It makes sense that git bisect is expecting a single transition, as > this is a precondition for a binary search to work. My definition of > "the transition" is a commit with at least one of its parents as a > good version, but the commit itself a bad version. But that is not the definition of transition that lets you pin-point the breaking commit precisly. Assume x3 is the commit introducing the breakage in the graph above. Even though you only know initially that G is good and B is bad, would you not prefer to find x3 instead of X2? As Christian said, a transition is when a commit is bad and all its parents are good, and this definition lets you find x3. > I hope we agree > that git bisect's mission is to search for this transition (as I > suppose that most of people need such a functionality from git, if not > exactly from git bisect). How could be x1 or x3 be the transition, if > chances are that o1 is not a good version? By declaring G as good, it is implied that o1 is also good. If it is in fact bad, the assumptions of git bisect are violated (because there would be a transition from bad to good at o2, o3, or G), and anything can happen. > If you consider that git bisect's mission is different from finding > the transition, could you please explain what exact commit git bisect > is supposed to return (ideally with terms from the graph theory) and > when it makes sense to return that? Because I do not see any sense in > looking in the path x1-x3 without knowing that those commits may be a > transition. And I do not see a reason why git bisect should not look at those commits. If x3 is the commit that broke my program, I do prefer to be pointed at x3 rather than X2. -- Hannes ^ permalink raw reply [flat|nested] 26+ messages in thread
end of thread, other threads:[~2017-02-21 22:40 UTC | newest] Thread overview: 26+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2017-02-17 22:29 Git bisect does not find commit introducing the bug Alex Hoffman 2017-02-17 23:21 ` Stephan Beyer 2017-02-18 9:12 ` Johannes Sixt 2017-02-18 11:15 ` Alex Hoffman 2017-02-18 14:18 ` Johannes Sixt 2017-02-18 18:36 ` Alex Hoffman 2017-02-18 19:58 ` Christian Couder 2017-02-19 11:32 ` Alex Hoffman 2017-02-19 12:43 ` Alex Hoffman 2017-02-19 13:07 ` Christian Couder 2017-02-19 14:13 ` Johannes Sixt 2017-02-19 19:05 ` Alex Hoffman 2017-02-19 19:25 ` Jacob Keller 2017-02-20 7:38 ` Oleg Taranenko 2017-02-20 12:27 ` Jakub Narębski 2017-02-20 13:50 ` Oleg Taranenko 2017-02-20 20:31 ` Alex Hoffman 2017-02-20 20:35 ` Jakub Narębski 2017-02-20 20:39 ` Alex Hoffman 2017-02-20 22:24 ` Philip Oakley 2017-02-21 19:40 ` Alex Hoffman 2017-02-21 22:39 ` Philip Oakley 2017-02-20 9:02 ` Junio C Hamano 2017-02-18 22:10 ` Philip Oakley 2017-02-18 22:36 ` Hilco Wijbenga 2017-02-18 22:37 ` Johannes Sixt
Code repositories for project(s) associated with this public inbox https://80x24.org/mirrors/git.git This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).