1
# Copyright (C) 2006-2011 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
"""bisect command implementations."""
19
from __future__ import absolute_import
22
from .controldir import ControlDir
23
from . import revision as _mod_revision
24
from .commands import Command
25
from .errors import BzrCommandError
26
from .option import Option
30
from .trace import note
32
BISECT_INFO_PATH = "bisect"
33
BISECT_REV_PATH = "bisect_revid"
36
class BisectCurrent(object):
37
"""Bisect class for managing the current revision."""
39
def __init__(self, controldir, filename=BISECT_REV_PATH):
40
self._filename = filename
41
self._controldir = controldir
42
self._branch = self._controldir.open_branch()
43
if self._controldir.control_transport.has(filename):
44
self._revid = self._controldir.control_transport.get_bytes(
47
self._revid = self._branch.last_revision()
50
"""Save the current revision."""
51
self._controldir.control_transport.put_bytes(
52
self._filename, self._revid + "\n")
54
def get_current_revid(self):
55
"""Return the current revision id."""
58
def get_current_revno(self):
59
"""Return the current revision number as a tuple."""
60
revdict = self._branch.get_revision_id_to_revno_map()
61
return revdict[self.get_current_revid()]
63
def get_parent_revids(self):
64
"""Return the IDs of the current revision's predecessors."""
65
repo = self._branch.repository
67
retval = repo.get_parent_map([self._revid]).get(self._revid, None)
71
def is_merge_point(self):
72
"""Is the current revision a merge point?"""
73
return len(self.get_parent_revids()) > 1
75
def show_rev_log(self, out = sys.stdout):
76
"""Write the current revision's log entry to a file."""
77
rev = self._branch.repository.get_revision(self._revid)
78
revno = ".".join([str(x) for x in self.get_current_revno()])
79
out.write("On revision %s (%s):\n%s\n" % (revno, rev.revision_id,
82
def switch(self, revid):
83
"""Switch the current revision to the given revid."""
84
working = self._controldir.open_workingtree()
85
if isinstance(revid, int):
86
revid = self._branch.get_rev_id(revid)
87
elif isinstance(revid, list):
88
revid = revid[0].in_history(working.branch).rev_id
89
working.revert(None, working.branch.repository.revision_tree(revid),
95
"""Revert bisection, setting the working tree to normal."""
96
working = self._controldir.open_workingtree()
97
last_rev = working.branch.last_revision()
98
rev_tree = working.branch.repository.revision_tree(last_rev)
99
working.revert(None, rev_tree, False)
100
if self._controldir.control_transport.has(BISECT_REV_PATH):
101
self._controldir.control_transport.delete(BISECT_REV_PATH)
104
class BisectLog(object):
105
"""Bisect log file handler."""
107
def __init__(self, controldir, filename=BISECT_INFO_PATH):
109
self._current = BisectCurrent(controldir)
110
self._controldir = controldir
112
self._high_revid = None
113
self._low_revid = None
114
self._middle_revid = None
115
self._filename = filename
118
def _open_for_read(self):
119
"""Open log file for reading."""
121
return self._controldir.control_transport.get(self._filename)
125
def _load_tree(self):
126
"""Load bzr information."""
128
self._branch = self._controldir.open_branch()
130
def _find_range_and_middle(self, branch_last_rev = None):
131
"""Find the current revision range, and the midpoint."""
133
self._middle_revid = None
135
if not branch_last_rev:
136
last_revid = self._branch.last_revision()
138
last_revid = branch_last_rev
140
repo = self._branch.repository
143
graph = repo.get_graph()
144
rev_sequence = graph.iter_lefthand_ancestry(last_revid,
145
(_mod_revision.NULL_REVISION,))
149
for revision in rev_sequence:
150
between_revs.insert(0, revision)
151
matches = [x[1] for x in self._items
152
if x[0] == revision and x[1] in ('yes', 'no')]
156
raise RuntimeError("revision %s duplicated" % revision)
157
if matches[0] == "yes":
158
high_revid = revision
160
elif matches[0] == "no":
166
high_revid = last_revid
168
low_revid = self._branch.get_rev_id(1)
172
# The spread must include the high revision, to bias
173
# odd numbers of intervening revisions towards the high
176
spread = len(between_revs) + 1
180
middle_index = (spread / 2) - 1
182
if len(between_revs) > 0:
183
self._middle_revid = between_revs[middle_index]
185
self._middle_revid = high_revid
187
self._high_revid = high_revid
188
self._low_revid = low_revid
190
def _switch_wc_to_revno(self, revno, outf):
191
"""Move the working tree to the given revno."""
192
self._current.switch(revno)
193
self._current.show_rev_log(out=outf)
195
def _set_status(self, revid, status):
196
"""Set the bisect status for the given revid."""
197
if not self.is_done():
198
if status != "done" and revid in [x[0] for x in self._items
199
if x[1] in ['yes', 'no']]:
200
raise RuntimeError("attempting to add revid %s twice" % revid)
201
self._items.append((revid, status))
203
def change_file_name(self, filename):
204
"""Switch log files."""
205
self._filename = filename
208
"""Load the bisection log."""
210
if self._controldir.control_transport.has(self._filename):
211
revlog = self._open_for_read()
213
(revid, status) = line.split()
214
self._items.append((revid, status))
217
"""Save the bisection log."""
219
("%s %s\n" % (revid, status))
220
for (revid, status) in self._items)
222
self._controldir.control_transport.put_bytes(
223
self._filename, contents)
225
sys.stdout.write(contents)
228
"""Report whether we've found the right revision."""
229
return len(self._items) > 0 and self._items[-1][1] == "done"
231
def set_status_from_revspec(self, revspec, status):
232
"""Set the bisection status for the revision in revspec."""
234
revid = revspec[0].in_history(self._branch).rev_id
235
self._set_status(revid, status)
237
def set_current(self, status):
238
"""Set the current revision to the given bisection status."""
239
self._set_status(self._current.get_current_revid(), status)
241
def is_merge_point(self, revid):
242
return len(self.get_parent_revids(revid)) > 1
244
def get_parent_revids(self, revid):
245
repo = self._branch.repository
248
retval = repo.get_parent_map([revid]).get(revid, None)
253
def bisect(self, outf):
254
"""Using the current revision's status, do a bisection."""
255
self._find_range_and_middle()
256
# If we've found the "final" revision, check for a
258
while ((self._middle_revid == self._high_revid
259
or self._middle_revid == self._low_revid)
260
and self.is_merge_point(self._middle_revid)):
261
for parent in self.get_parent_revids(self._middle_revid):
262
if parent == self._low_revid:
265
self._find_range_and_middle(parent)
267
self._switch_wc_to_revno(self._middle_revid, outf)
268
if self._middle_revid == self._high_revid or \
269
self._middle_revid == self._low_revid:
270
self.set_current("done")
273
class cmd_bisect(Command):
274
"""Find an interesting commit using a binary search.
276
Bisecting, in a nutshell, is a way to find the commit at which
277
some testable change was made, such as the introduction of a bug
278
or feature. By identifying a version which did not have the
279
interesting change and a later version which did, a developer
280
can test for the presence of the change at various points in
281
the history, eventually ending up at the precise commit when
282
the change was first introduced.
284
This command uses subcommands to implement the search, each
285
of which changes the state of the bisection. The
289
Start a bisect, possibly clearing out a previous bisect.
291
brz bisect yes [-r rev]
292
The specified revision (or the current revision, if not given)
293
has the characteristic we're looking for,
295
brz bisect no [-r rev]
296
The specified revision (or the current revision, if not given)
297
does not have the characteristic we're looking for,
299
brz bisect move -r rev
300
Switch to a different revision manually. Use if the bisect
301
algorithm chooses a revision that is not suitable. Try to
302
move as little as possible.
305
Clear out a bisection in progress.
307
brz bisect log [-o file]
308
Output a log of the current bisection to standard output, or
309
to the specified file.
311
brz bisect replay <logfile>
312
Replay a previously-saved bisect log, forgetting any bisection
313
that might be in progress.
315
brz bisect run <script>
316
Bisect automatically using <script> to determine 'yes' or 'no'.
317
<script> should exit with:
319
125 for unknown (like build failed so we could not test)
323
takes_args = ['subcommand', 'args*']
324
takes_options = [Option('output', short_name='o',
325
help='Write log to this file.', type=text_type),
326
'revision', 'directory']
328
def _check(self, controldir):
329
"""Check preconditions for most operations to work."""
330
if not controldir.control_transport.has(BISECT_INFO_PATH):
331
raise BzrCommandError("No bisection in progress.")
333
def _set_state(self, controldir, revspec, state):
334
"""Set the state of the given revspec and bisecting.
336
Returns boolean indicating if bisection is done."""
337
bisect_log = BisectLog(controldir)
338
if bisect_log.is_done():
339
note("No further bisection is possible.\n")
340
bisect_log._current.show_rev_log(self.outf)
344
bisect_log.set_status_from_revspec(revspec, state)
346
bisect_log.set_current(state)
347
bisect_log.bisect(self.outf)
351
def run(self, subcommand, args_list, directory='.', revision=None, output=None):
352
"""Handle the bisect command."""
355
if subcommand in ('yes', 'no', 'move') and revision:
357
elif subcommand in ('replay', ) and args_list and len(args_list) == 1:
358
log_fn = args_list[0]
359
elif subcommand in ('move', ) and not revision:
360
raise BzrCommandError(
361
"The 'bisect move' command requires a revision.")
362
elif subcommand in ('run', ):
363
run_script = args_list[0]
364
elif args_list or revision:
365
raise BzrCommandError(
366
"Improper arguments to bisect " + subcommand)
368
controldir, _ = ControlDir.open_containing(directory)
371
if subcommand == "start":
372
self.start(controldir)
373
elif subcommand == "yes":
374
self.yes(controldir, revision)
375
elif subcommand == "no":
376
self.no(controldir, revision)
377
elif subcommand == "move":
378
self.move(controldir, revision)
379
elif subcommand == "reset":
380
self.reset(controldir)
381
elif subcommand == "log":
382
self.log(controldir, output)
383
elif subcommand == "replay":
384
self.replay(controldir, log_fn)
385
elif subcommand == "run":
386
self.run_bisect(controldir, run_script)
388
raise BzrCommandError(
389
"Unknown bisect command: " + subcommand)
391
def reset(self, controldir):
392
"""Reset the bisect state to no state."""
393
self._check(controldir)
394
BisectCurrent(controldir).reset()
395
controldir.control_transport.delete(BISECT_INFO_PATH)
397
def start(self, controldir):
398
"""Reset the bisect state, then prepare for a new bisection."""
399
if controldir.control_transport.has(BISECT_INFO_PATH):
400
BisectCurrent(controldir).reset()
401
controldir.control_transport.delete(BISECT_INFO_PATH)
403
bisect_log = BisectLog(controldir)
404
bisect_log.set_current("start")
407
def yes(self, controldir, revspec):
408
"""Mark that a given revision has the state we're looking for."""
409
self._set_state(controldir, revspec, "yes")
411
def no(self, controldir, revspec):
412
"""Mark that a given revision does not have the state we're looking for."""
413
self._set_state(controldir, revspec, "no")
415
def move(self, controldir, revspec):
416
"""Move to a different revision manually."""
417
current = BisectCurrent(controldir)
418
current.switch(revspec)
419
current.show_rev_log(out=self.outf)
421
def log(self, controldir, filename):
422
"""Write the current bisect log to a file."""
423
self._check(controldir)
424
bisect_log = BisectLog(controldir)
425
bisect_log.change_file_name(filename)
428
def replay(self, controldir, filename):
429
"""Apply the given log file to a clean state, so the state is
430
exactly as it was when the log was saved."""
431
if controldir.control_transport.has(BISECT_INFO_PATH):
432
BisectCurrent(controldir).reset()
433
controldir.control_transport.delete(BISECT_INFO_PATH)
434
bisect_log = BisectLog(controldir, filename)
435
bisect_log.change_file_name(BISECT_INFO_PATH)
438
bisect_log.bisect(self.outf)
440
def run_bisect(self, controldir, script):
442
note("Starting bisect.")
443
self.start(controldir)
446
process = subprocess.Popen(script, shell=True)
448
retcode = process.returncode
450
done = self._set_state(controldir, None, 'yes')
454
done = self._set_state(controldir, None, 'no')