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."""
20
from .controldir import ControlDir
21
from . import revision as _mod_revision
22
from .commands import Command
23
from .errors import CommandError
24
from .option import Option
25
from .trace import note
27
BISECT_INFO_PATH = "bisect"
28
BISECT_REV_PATH = "bisect_revid"
31
class BisectCurrent(object):
32
"""Bisect class for managing the current revision."""
34
def __init__(self, controldir, filename=BISECT_REV_PATH):
35
self._filename = filename
36
self._controldir = controldir
37
self._branch = self._controldir.open_branch()
38
if self._controldir.control_transport.has(filename):
39
self._revid = self._controldir.control_transport.get_bytes(
42
self._revid = self._branch.last_revision()
45
"""Save the current revision."""
46
self._controldir.control_transport.put_bytes(
47
self._filename, self._revid + b"\n")
49
def get_current_revid(self):
50
"""Return the current revision id."""
53
def get_current_revno(self):
54
"""Return the current revision number as a tuple."""
55
return self._branch.revision_id_to_dotted_revno(self._revid)
57
def get_parent_revids(self):
58
"""Return the IDs of the current revision's predecessors."""
59
repo = self._branch.repository
60
with repo.lock_read():
61
retval = repo.get_parent_map([self._revid]).get(self._revid, None)
64
def is_merge_point(self):
65
"""Is the current revision a merge point?"""
66
return len(self.get_parent_revids()) > 1
68
def show_rev_log(self, outf):
69
"""Write the current revision's log entry to a file."""
70
rev = self._branch.repository.get_revision(self._revid)
71
revno = ".".join([str(x) for x in self.get_current_revno()])
72
outf.write("On revision %s (%s):\n%s\n" % (revno, rev.revision_id,
75
def switch(self, revid):
76
"""Switch the current revision to the given revid."""
77
working = self._controldir.open_workingtree()
78
if isinstance(revid, int):
79
revid = self._branch.get_rev_id(revid)
80
elif isinstance(revid, list):
81
revid = revid[0].in_history(working.branch).rev_id
82
working.revert(None, working.branch.repository.revision_tree(revid),
88
"""Revert bisection, setting the working tree to normal."""
89
working = self._controldir.open_workingtree()
90
last_rev = working.branch.last_revision()
91
rev_tree = working.branch.repository.revision_tree(last_rev)
92
working.revert(None, rev_tree, False)
93
if self._controldir.control_transport.has(BISECT_REV_PATH):
94
self._controldir.control_transport.delete(BISECT_REV_PATH)
97
class BisectLog(object):
98
"""Bisect log file handler."""
100
def __init__(self, controldir, filename=BISECT_INFO_PATH):
102
self._current = BisectCurrent(controldir)
103
self._controldir = controldir
105
self._high_revid = None
106
self._low_revid = None
107
self._middle_revid = None
108
self._filename = filename
111
def _open_for_read(self):
112
"""Open log file for reading."""
114
return self._controldir.control_transport.get(self._filename)
118
def _load_tree(self):
119
"""Load bzr information."""
121
self._branch = self._controldir.open_branch()
123
def _find_range_and_middle(self, branch_last_rev=None):
124
"""Find the current revision range, and the midpoint."""
126
self._middle_revid = None
128
if not branch_last_rev:
129
last_revid = self._branch.last_revision()
131
last_revid = branch_last_rev
133
repo = self._branch.repository
134
with repo.lock_read():
135
graph = repo.get_graph()
136
rev_sequence = graph.iter_lefthand_ancestry(
137
last_revid, (_mod_revision.NULL_REVISION,))
141
for revision in rev_sequence:
142
between_revs.insert(0, revision)
143
matches = [x[1] for x in self._items
144
if x[0] == revision and x[1] in ('yes', 'no')]
148
raise RuntimeError("revision %s duplicated" % revision)
149
if matches[0] == "yes":
150
high_revid = revision
152
elif matches[0] == "no":
158
high_revid = last_revid
160
low_revid = self._branch.get_rev_id(1)
162
# The spread must include the high revision, to bias
163
# odd numbers of intervening revisions towards the high
166
spread = len(between_revs) + 1
170
middle_index = (spread // 2) - 1
172
if len(between_revs) > 0:
173
self._middle_revid = between_revs[middle_index]
175
self._middle_revid = high_revid
177
self._high_revid = high_revid
178
self._low_revid = low_revid
180
def _switch_wc_to_revno(self, revno, outf):
181
"""Move the working tree to the given revno."""
182
self._current.switch(revno)
183
self._current.show_rev_log(outf=outf)
185
def _set_status(self, revid, status):
186
"""Set the bisect status for the given revid."""
187
if not self.is_done():
188
if status != "done" and revid in [x[0] for x in self._items
189
if x[1] in ['yes', 'no']]:
190
raise RuntimeError("attempting to add revid %s twice" % revid)
191
self._items.append((revid, status))
193
def change_file_name(self, filename):
194
"""Switch log files."""
195
self._filename = filename
198
"""Load the bisection log."""
200
if self._controldir.control_transport.has(self._filename):
201
revlog = self._open_for_read()
203
(revid, status) = line.split()
204
self._items.append((revid, status.decode('ascii')))
207
"""Save the bisection log."""
209
(b"%s %s\n" % (revid, status.encode('ascii')))
210
for (revid, status) in self._items)
212
self._controldir.control_transport.put_bytes(
213
self._filename, contents)
215
sys.stdout.write(contents)
218
"""Report whether we've found the right revision."""
219
return len(self._items) > 0 and self._items[-1][1] == "done"
221
def set_status_from_revspec(self, revspec, status):
222
"""Set the bisection status for the revision in revspec."""
224
revid = revspec[0].in_history(self._branch).rev_id
225
self._set_status(revid, status)
227
def set_current(self, status):
228
"""Set the current revision to the given bisection status."""
229
self._set_status(self._current.get_current_revid(), status)
231
def is_merge_point(self, revid):
232
return len(self.get_parent_revids(revid)) > 1
234
def get_parent_revids(self, revid):
235
repo = self._branch.repository
236
with repo.lock_read():
237
retval = repo.get_parent_map([revid]).get(revid, None)
240
def bisect(self, outf):
241
"""Using the current revision's status, do a bisection."""
242
self._find_range_and_middle()
243
# If we've found the "final" revision, check for a
245
while ((self._middle_revid == self._high_revid or
246
self._middle_revid == self._low_revid) and
247
self.is_merge_point(self._middle_revid)):
248
for parent in self.get_parent_revids(self._middle_revid):
249
if parent == self._low_revid:
252
self._find_range_and_middle(parent)
254
self._switch_wc_to_revno(self._middle_revid, outf)
255
if self._middle_revid == self._high_revid or \
256
self._middle_revid == self._low_revid:
257
self.set_current("done")
260
class cmd_bisect(Command):
261
"""Find an interesting commit using a binary search.
263
Bisecting, in a nutshell, is a way to find the commit at which
264
some testable change was made, such as the introduction of a bug
265
or feature. By identifying a version which did not have the
266
interesting change and a later version which did, a developer
267
can test for the presence of the change at various points in
268
the history, eventually ending up at the precise commit when
269
the change was first introduced.
271
This command uses subcommands to implement the search, each
272
of which changes the state of the bisection. The
276
Start a bisect, possibly clearing out a previous bisect.
278
brz bisect yes [-r rev]
279
The specified revision (or the current revision, if not given)
280
has the characteristic we're looking for,
282
brz bisect no [-r rev]
283
The specified revision (or the current revision, if not given)
284
does not have the characteristic we're looking for,
286
brz bisect move -r rev
287
Switch to a different revision manually. Use if the bisect
288
algorithm chooses a revision that is not suitable. Try to
289
move as little as possible.
292
Clear out a bisection in progress.
294
brz bisect log [-o file]
295
Output a log of the current bisection to standard output, or
296
to the specified file.
298
brz bisect replay <logfile>
299
Replay a previously-saved bisect log, forgetting any bisection
300
that might be in progress.
302
brz bisect run <script>
303
Bisect automatically using <script> to determine 'yes' or 'no'.
304
<script> should exit with:
306
125 for unknown (like build failed so we could not test)
310
takes_args = ['subcommand', 'args*']
311
takes_options = [Option('output', short_name='o',
312
help='Write log to this file.', type=str),
313
'revision', 'directory']
315
def _check(self, controldir):
316
"""Check preconditions for most operations to work."""
317
if not controldir.control_transport.has(BISECT_INFO_PATH):
318
raise CommandError("No bisection in progress.")
320
def _set_state(self, controldir, revspec, state):
321
"""Set the state of the given revspec and bisecting.
323
Returns boolean indicating if bisection is done."""
324
bisect_log = BisectLog(controldir)
325
if bisect_log.is_done():
326
note("No further bisection is possible.\n")
327
bisect_log._current.show_rev_log(outf=self.outf)
331
bisect_log.set_status_from_revspec(revspec, state)
333
bisect_log.set_current(state)
334
bisect_log.bisect(self.outf)
338
def run(self, subcommand, args_list, directory='.', revision=None,
340
"""Handle the bisect command."""
343
if subcommand in ('yes', 'no', 'move') and revision:
345
elif subcommand in ('replay', ) and args_list and len(args_list) == 1:
346
log_fn = args_list[0]
347
elif subcommand in ('move', ) and not revision:
349
"The 'bisect move' command requires a revision.")
350
elif subcommand in ('run', ):
351
run_script = args_list[0]
352
elif args_list or revision:
354
"Improper arguments to bisect " + subcommand)
356
controldir, _ = ControlDir.open_containing(directory)
359
if subcommand == "start":
360
self.start(controldir)
361
elif subcommand == "yes":
362
self.yes(controldir, revision)
363
elif subcommand == "no":
364
self.no(controldir, revision)
365
elif subcommand == "move":
366
self.move(controldir, revision)
367
elif subcommand == "reset":
368
self.reset(controldir)
369
elif subcommand == "log":
370
self.log(controldir, output)
371
elif subcommand == "replay":
372
self.replay(controldir, log_fn)
373
elif subcommand == "run":
374
self.run_bisect(controldir, run_script)
377
"Unknown bisect command: " + subcommand)
379
def reset(self, controldir):
380
"""Reset the bisect state to no state."""
381
self._check(controldir)
382
BisectCurrent(controldir).reset()
383
controldir.control_transport.delete(BISECT_INFO_PATH)
385
def start(self, controldir):
386
"""Reset the bisect state, then prepare for a new bisection."""
387
if controldir.control_transport.has(BISECT_INFO_PATH):
388
BisectCurrent(controldir).reset()
389
controldir.control_transport.delete(BISECT_INFO_PATH)
391
bisect_log = BisectLog(controldir)
392
bisect_log.set_current("start")
395
def yes(self, controldir, revspec):
396
"""Mark that a given revision has the state we're looking for."""
397
self._set_state(controldir, revspec, "yes")
399
def no(self, controldir, revspec):
400
"""Mark a given revision as wrong."""
401
self._set_state(controldir, revspec, "no")
403
def move(self, controldir, revspec):
404
"""Move to a different revision manually."""
405
current = BisectCurrent(controldir)
406
current.switch(revspec)
407
current.show_rev_log(outf=self.outf)
409
def log(self, controldir, filename):
410
"""Write the current bisect log to a file."""
411
self._check(controldir)
412
bisect_log = BisectLog(controldir)
413
bisect_log.change_file_name(filename)
416
def replay(self, controldir, filename):
417
"""Apply the given log file to a clean state, so the state is
418
exactly as it was when the log was saved."""
419
if controldir.control_transport.has(BISECT_INFO_PATH):
420
BisectCurrent(controldir).reset()
421
controldir.control_transport.delete(BISECT_INFO_PATH)
422
bisect_log = BisectLog(controldir, filename)
423
bisect_log.change_file_name(BISECT_INFO_PATH)
426
bisect_log.bisect(self.outf)
428
def run_bisect(self, controldir, script):
430
note("Starting bisect.")
431
self.start(controldir)
434
process = subprocess.Popen(script, shell=True)
436
retcode = process.returncode
438
done = self._set_state(controldir, None, 'yes')
442
done = self._set_state(controldir, None, 'no')
added
removed
breezy/bisect.py
