Timeline for What is the maximum number of steps to find a bug using bisecting?
Current License: CC BY-SA 3.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 22, 2018 at 7:58 | vote | accept | Michaël Le Barbier | ||
| Jun 1, 2015 at 0:07 | audit | Close votes | |||
| Jun 2, 2015 at 0:32 | |||||
| May 21, 2015 at 15:48 | comment | added | Ordous |
As a quick guess - if you assume you can only merge 1 branch into another (no merging of 3+ branches together), then you can easily check in at most O(h + log(n)) where n is the longest no-merges spree in the commit tree, and h is the largest number of merges that a commit may have needed to go through from start to your known buggy build. This would be achievable by dividing your commit tree into a proper binary tree, and then pruning one branch at a time. (Note - this means that in your second case the time is from log(n) to n depending on the order of merges)
|
|
| May 21, 2015 at 7:54 | answer | added | phyrfox | timeline score: 3 | |
| May 20, 2015 at 17:59 | audit | Suggested edits | |||
| May 20, 2015 at 18:00 | |||||
| Apr 28, 2015 at 6:13 | history | tweeted | twitter.com/#!/StackProgrammer/status/592934692212576256 | ||
| Apr 28, 2015 at 5:37 | comment | added | Doc Brown | @BartvanIngenSchenau: you got my point, though I think it does not depend on how the SCM stores something internally. The important part is the SCM model, as it is seen from a user of the SCM. I assume we are talking of changesets here. Each commit is a changeset, and to validate the presence of a bug one has to apply the changesets to a base revision first, then run a build step and a test which shows up a bug. And we are assuming once a bug is introduced by a specific changeset, it stays in the resulting code. | |
| Apr 28, 2015 at 5:32 | comment | added | Doc Brown | @Izkata: why not? If the bug is introduce in "commit B", it is in the codebase after you merged B into the trunk, and it stays in there if you merge C afterwards, if you only merge D afterwards, or both. Note that the test for the presence of a bug cannot not done by looking at a specific commit (the differences applied), but by testing the resulting code base after merging the commit to it. | |
| Apr 28, 2015 at 5:30 | comment | added | Bart van Ingen Schenau |
@Izkata: That depends on how commits are stored in the SCM system. If they are stored as snapshots, then your objections are valid. But if they are stored as differences, then the linearisation A, B, C, D would have the bug also show up in C' (the snapshot created by applying differences B and C to the snapshot at A).
|
|
| Apr 27, 2015 at 23:21 | comment | added | Izkata |
@DocBrown This is awkward to do in comments, but if the commit tree is A -> B -> D and A -> C -> D (a diamond), and the bug is in B and D, then your arbitrary linearization cannot choose A, B, C, D and still work - even though B and C are still independent
|
|
| Apr 27, 2015 at 6:55 | comment | added | Doc Brown | @Izkata: the whole question makes only sense under the assumption that the bug does not disappear by a later commit. Without that assumption, bisection would not work for an already linear history tree. Furthermore, the definition of commits beeing independent is "the order in which they are applied is irrelevant", so the outcome of the commits cannot depend on the order, otherwise the commits were not indepedent in first place. | |
| Apr 27, 2015 at 0:16 | comment | added | Izkata | @DocBrown If you choose the wrong order, the bug can disappear and then reappear in the linear ordering. Bisect at its most basic works as a binary search; those intermediate "fixed" commits would make it go in the wrong direction if it landed on one of them, so I don't think the simplification works here | |
| Apr 26, 2015 at 23:45 | comment | added | Winston Ewert | Related: cstheory.stackexchange.com/questions/8923/… cs.stackexchange.com/questions/22451/… | |
| Apr 26, 2015 at 18:29 | comment | added | Doc Brown | "We want to find the first bug where the bug appears" - (you surely meant "the first commit"). Excactly. Pick an arbitrary order, apply the bisection, it will tell you which of the M_i is the cause. What am I missing? | |
| Apr 26, 2015 at 18:27 | comment | added | Michaël Le Barbier | And linearization is always possible for a directed, acyclic graph. Do you refer to topological sort? This is not an option here because if I introduce an arrow in the graph, I break the implicit assumption that once the bug went in, it stays there. | |
| Apr 26, 2015 at 18:25 | comment | added | Michaël Le Barbier | We want to find the first bug where the bug appears. In the case of parallel commits, we may need to examine each commit to conclude that the bug appeared in one Mᵢ or in A. In the case of a linear history, one can skip some commits. | |
| Apr 26, 2015 at 18:21 | comment | added | Doc Brown |
Still having trouble to understand what happens with parallel commits. If we assume the bug was introduced in exactly one of the M_i, then you can just pick an arbitrary order for them, and deal with them like in case 1. And linearization is always possible for a directed, acyclic graph.
|
|
| Apr 26, 2015 at 16:50 | comment | added | Michaël Le Barbier | @DocBrown – This is definitely true! But let us assume that this is not the case, i.e. we consider the optimistic case where bisecting will actually find the bug! EDIT Well actually, this just means that the commit look for is A itself! :) | |
| Apr 26, 2015 at 16:47 | comment | added | Doc Brown | If I got this right, if you have 2 parallel commits, you may not be able to assign the bug to one of the commits - it is totally possible that the bug only results from the combination of the two. | |
| Apr 26, 2015 at 16:38 | comment | added | Michaël Le Barbier | The mathy way to ask the question would go as “Given a finite ordered lattice which is an interval, we consider sets of intervals on this lattice, such that each point in the lattice can be described as an intersection of some of these intervals. Which is the smallest cardinal such a set can have?” | |
| Apr 26, 2015 at 16:26 | history | asked | Michaël Le Barbier | CC BY-SA 3.0 |