69:
in editions comprising one or more changesets. Editions with known regressions could not be validated until developers addressed the problem. Source change isolation narrowed the cause to a single changeset that could then be excluded from editions, unblocking them with respect to this problem, while
271:
have built-in functionality for code bisection. The user can start a bisection session with a specified range of revisions from which the revision control system proposes a revision to test, the user tells the system whether the revision tested as "good" or "bad", and the process repeats until the
239:
of the change in behavior between the start and the end of the search space. The root cause could be a different changeset, or a combination of two or more changesets across the search space. To help deal with this problem, automated tools allow specific changesets to be ignored during a bisection
234:
If there are multiple changesets across the search space where the behavior being tested changes between false and true, then the bisection algorithm will find one of them, but it will not necessarily be the
231:
across the search space. For a
Boolean function such as a pass/fail test, this means that it only changes once across all changesets between the start and end of the search space.
185:
252:
processes: failures in exhaustive automated regression tests can trigger automated bisection to localize faults. Ness and Ngo focused on its potential in Cray's
205:
248:
Although the bisection method can be completed manually, one of its main advantages is that it can be easily automated. It can thus fit into existing
227:
For the bisection algorithm to identify a single changeset which caused the behavior being tested to change, the behavior must change
509:
119:
504:
256:-style environment in which the automatically isolated bad changeset could be automatically excluded from builds.
219:
For code bisection it is desirable that each revision in the search space can be built and tested independently.
90:
82:
37:
that result in a specific behavior change. It is mostly employed for finding the patch that introduced a
446:"bisect - Find the revision introducing a bug using a binary search — Bazaar 2.8.0dev1 documentation"
499:
81:
Code bisection has the goal of minimizing the effort to find a specific change set. It employs a
20:
445:
469:
155:
149:
107:
111:
30:
8:
514:
283:
253:
236:
54:
228:
190:
132:
62:
301:
421:
277:
273:
272:
specific "bad" revision has been identified. Other revision control systems, such as
34:
353:
330:
86:
295:
249:
57:
was described as "source change isolation" in 1997 by Brian Ness and Viet Ngo of
373:
85:
that depends on having access to the code history which is usually preserved by
334:
264:
145:
493:
208:
114:. This makes it possible to use a divide and conquer search algorithm which:
75:
71:
58:
41:. Another application area is finding the patch that indirectly fixed a bug.
38:
358:
207:
denoting the number of revisions in the search space, and is similar to a
260:
397:
131:
re-iterates the steps above until a range with at most one bisectable
268:
50:
66:
286:
can do bisection automatically to find performance regressions.
70:
the author of the change worked on a fix. Ness and Ngo outlined
352:. European Software Engineering Conference. Toulouse, France.
280:, support bisection through plugins or external scripts.
329:. Computer Software and Applications Conference. IEEE.
350:
Yesterday, my program worked. Today, it does not. Why?
327:
Regression containment through source change isolation
304:(determining changesets that edited a line in a file)
193:
158:
128:
reduces the search space depending on the test result
298:(generalization of finding a minimal cause of a bug)
214:
199:
179:
491:
101:
357:
320:
318:
139:
341:
324:
492:
347:
315:
78:methods of performing this isolation.
243:
106:Code history has the structure of a
96:
13:
125:tests for the behavior in question
14:
526:
302:Annotation § Source control
325:Ness, Brian; Ngo, Viet (1997).
222:
215:Desirable repository properties
462:
438:
414:
390:
366:
174:
162:
1:
308:
259:The revision control systems
510:Software development process
83:divide and conquer algorithm
49:The process of locating the
7:
289:
53:that introduced a specific
44:
10:
531:
335:10.1109/CMPSAC.1997.625082
18:
180:{\displaystyle O(\log N)}
450:Doc.bazaar.canonical.com
348:Zeller, Andreas (1999).
102:Code bisection algorithm
65:was performed on Cray's
505:Version control systems
374:"Fossil: Help: bisect"
201:
181:
150:algorithmic complexity
140:Algorithmic complexity
122:of candidate revisions
108:directed acyclic graph
359:10.1145/318774.318946
202:
182:
191:
156:
112:topologically sorted
31:software development
29:is a method used in
19:For other uses, see
16:Software engineering
284:Phoronix Test Suite
254:continuous delivery
378:www.fossil-scm.org
244:Automation support
197:
177:
63:Regression testing
200:{\displaystyle N}
522:
484:
483:
481:
480:
466:
460:
459:
457:
456:
442:
436:
435:
433:
432:
418:
412:
411:
409:
408:
394:
388:
387:
385:
384:
370:
364:
363:
361:
345:
339:
338:
322:
206:
204:
203:
198:
186:
184:
183:
178:
144:Bisection is in
97:Bisection method
87:revision control
530:
529:
525:
524:
523:
521:
520:
519:
500:Version control
490:
489:
488:
487:
478:
476:
468:
467:
463:
454:
452:
444:
443:
439:
430:
428:
420:
419:
415:
406:
404:
398:"git-bisect(1)"
396:
395:
391:
382:
380:
372:
371:
367:
346:
342:
323:
316:
311:
296:Delta debugging
292:
250:test automation
246:
225:
217:
192:
189:
188:
157:
154:
153:
142:
133:patch candidate
104:
99:
91:code repository
47:
24:
17:
12:
11:
5:
528:
518:
517:
512:
507:
502:
486:
485:
461:
437:
413:
389:
365:
340:
313:
312:
310:
307:
306:
305:
299:
291:
288:
245:
242:
224:
221:
216:
213:
196:
176:
173:
170:
167:
164:
161:
141:
138:
137:
136:
129:
126:
123:
118:splits up the
103:
100:
98:
95:
46:
43:
15:
9:
6:
4:
3:
2:
527:
516:
513:
511:
508:
506:
503:
501:
498:
497:
495:
475:
471:
465:
451:
447:
441:
427:
423:
417:
403:
399:
393:
379:
375:
369:
360:
355:
351:
344:
336:
332:
328:
321:
319:
314:
303:
300:
297:
294:
293:
287:
285:
281:
279:
275:
270:
266:
262:
257:
255:
251:
241:
238:
232:
230:
229:monotonically
220:
212:
210:
209:binary search
194:
171:
168:
165:
159:
151:
147:
134:
130:
127:
124:
121:
117:
116:
115:
113:
110:which can be
109:
94:
92:
88:
84:
79:
77:
76:binary search
73:
72:linear search
68:
64:
60:
59:Cray Research
56:
52:
42:
40:
36:
32:
28:
22:
477:. Retrieved
474:Metacpan.org
473:
470:"svn-bisect"
464:
453:. Retrieved
449:
440:
429:. Retrieved
425:
416:
405:. Retrieved
401:
392:
381:. Retrieved
377:
368:
349:
343:
326:
282:
258:
247:
233:
226:
223:Monotonicity
218:
143:
120:search space
105:
80:
48:
33:to identify
26:
25:
426:Selenic.com
402:git-scm.com
35:change sets
515:Algorithms
494:Categories
479:2022-08-03
455:2017-01-09
431:2017-01-09
407:2017-08-05
383:2020-09-03
309:References
278:Subversion
237:root cause
148:having an
55:regression
269:Mercurial
169:
67:compilers
51:changeset
27:Bisection
290:See also
240:search.
45:Overview
135:remains
274:Bazaar
261:Fossil
146:LSPACE
21:Bisect
187:with
89:in a
422:"hg"
267:and
74:and
354:doi
331:doi
276:or
265:Git
166:log
152:of
39:bug
496::
472:.
448:.
424:.
400:.
376:.
317:^
263:,
211:.
93:.
61:.
482:.
458:.
434:.
410:.
386:.
362:.
356::
337:.
333::
195:N
175:)
172:N
163:(
160:O
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.