~bzr/bzr-bisect/trunk

« back to all changes in this revision

Viewing changes to cmds.py

  • Committer: Jelmer Vernooij
  • Date: 2011-11-25 13:21:00 UTC
  • mfrom: (82.1.1 lazy)
  • Revision ID: jelmer@samba.org-20111125132100-6rr5ftv20h1w3tds
Merge support for lazy loading.

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
1
# Copyright (C) 2006-2011 Canonical Ltd
 
2
#
 
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.
 
7
#
 
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.
 
12
#
 
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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
16
 
 
17
"""bisect command implementations."""
 
18
 
 
19
import sys
 
20
import os
 
21
import bzrlib.bzrdir
 
22
from bzrlib.commands import Command
 
23
from bzrlib.errors import BzrCommandError
 
24
from bzrlib.option import Option
 
25
from bzrlib.trace import note
 
26
 
 
27
bisect_info_path = ".bzr/bisect"
 
28
bisect_rev_path = ".bzr/bisect_revid"
 
29
 
 
30
 
 
31
class BisectCurrent(object):
 
32
    """Bisect class for managing the current revision."""
 
33
 
 
34
    def __init__(self, filename = bisect_rev_path):
 
35
        self._filename = filename
 
36
        self._bzrdir = bzrlib.bzrdir.BzrDir.open_containing(".")[0]
 
37
        self._bzrbranch = self._bzrdir.open_branch()
 
38
        if os.path.exists(filename):
 
39
            revid_file = open(filename)
 
40
            self._revid = revid_file.read().strip()
 
41
            revid_file.close()
 
42
        else:
 
43
            self._revid = self._bzrbranch.last_revision()
 
44
 
 
45
    def _save(self):
 
46
        """Save the current revision."""
 
47
 
 
48
        revid_file = open(self._filename, "w")
 
49
        revid_file.write(self._revid + "\n")
 
50
        revid_file.close()
 
51
 
 
52
    def get_current_revid(self):
 
53
        """Return the current revision id."""
 
54
        return self._revid
 
55
 
 
56
    def get_current_revno(self):
 
57
        """Return the current revision number as a tuple."""
 
58
        revdict = self._bzrbranch.get_revision_id_to_revno_map()
 
59
        return revdict[self.get_current_revid()]
 
60
 
 
61
    def get_parent_revids(self):
 
62
        """Return the IDs of the current revision's predecessors."""
 
63
        repo = self._bzrbranch.repository
 
64
        repo.lock_read()
 
65
        retval = repo.get_parent_map([self._revid]).get(self._revid, None)
 
66
        repo.unlock()
 
67
        return retval
 
68
 
 
69
    def is_merge_point(self):
 
70
        """Is the current revision a merge point?"""
 
71
        return len(self.get_parent_revids()) > 1
 
72
 
 
73
    def show_rev_log(self, out = sys.stdout):
 
74
        """Write the current revision's log entry to a file."""
 
75
        rev = self._bzrbranch.repository.get_revision(self._revid)
 
76
        revno = ".".join([str(x) for x in self.get_current_revno()])
 
77
        out.write("On revision %s (%s):\n%s\n" % (revno, rev.revision_id,
 
78
                                                  rev.message))
 
79
 
 
80
    def switch(self, revid):
 
81
        """Switch the current revision to the given revid."""
 
82
        working = self._bzrdir.open_workingtree()
 
83
        if isinstance(revid, int):
 
84
            revid = self._bzrbranch.get_rev_id(revid)
 
85
        elif isinstance(revid, list):
 
86
            revid = revid[0].in_history(working.branch).rev_id
 
87
        working.revert(None, working.branch.repository.revision_tree(revid),
 
88
                       False)
 
89
        self._revid = revid
 
90
        self._save()
 
91
 
 
92
    def reset(self):
 
93
        """Revert bisection, setting the working tree to normal."""
 
94
        working = self._bzrdir.open_workingtree()
 
95
        last_rev = working.branch.last_revision()
 
96
        rev_tree = working.branch.repository.revision_tree(last_rev)
 
97
        working.revert(None, rev_tree, False)
 
98
        if os.path.exists(bisect_rev_path):
 
99
            os.unlink(bisect_rev_path)
 
100
 
 
101
 
 
102
class BisectLog(object):
 
103
    """Bisect log file handler."""
 
104
 
 
105
    def __init__(self, filename = bisect_info_path):
 
106
        self._items = []
 
107
        self._current = BisectCurrent()
 
108
        self._bzrdir = None
 
109
        self._high_revid = None
 
110
        self._low_revid = None
 
111
        self._middle_revid = None
 
112
        self._filename = filename
 
113
        self.load()
 
114
 
 
115
    def _open_for_read(self):
 
116
        """Open log file for reading."""
 
117
        if self._filename:
 
118
            return open(self._filename)
 
119
        else:
 
120
            return sys.stdin
 
121
 
 
122
    def _open_for_write(self):
 
123
        """Open log file for writing."""
 
124
        if self._filename:
 
125
            return open(self._filename, "w")
 
126
        else:
 
127
            return sys.stdout
 
128
 
 
129
    def _load_bzr_tree(self):
 
130
        """Load bzr information."""
 
131
        if not self._bzrdir:
 
132
            self._bzrdir = bzrlib.bzrdir.BzrDir.open_containing('.')[0]
 
133
            self._bzrbranch = self._bzrdir.open_branch()
 
134
 
 
135
    def _find_range_and_middle(self, branch_last_rev = None):
 
136
        """Find the current revision range, and the midpoint."""
 
137
        self._load_bzr_tree()
 
138
        self._middle_revid = None
 
139
 
 
140
        if not branch_last_rev:
 
141
            last_revid = self._bzrbranch.last_revision()
 
142
        else:
 
143
            last_revid = branch_last_rev
 
144
 
 
145
        repo = self._bzrbranch.repository
 
146
        repo.lock_read()
 
147
        try:
 
148
            rev_sequence = repo.iter_reverse_revision_history(last_revid)
 
149
            high_revid = None
 
150
            low_revid = None
 
151
            between_revs = []
 
152
            for revision in rev_sequence:
 
153
                between_revs.insert(0, revision)
 
154
                matches = [x[1] for x in self._items
 
155
                           if x[0] == revision and x[1] in ('yes', 'no')]
 
156
                if not matches:
 
157
                    continue
 
158
                if len(matches) > 1:
 
159
                    raise RuntimeError("revision %s duplicated" % revision)
 
160
                if matches[0] == "yes":
 
161
                    high_revid = revision
 
162
                    between_revs = []
 
163
                elif matches[0] == "no":
 
164
                    low_revid = revision
 
165
                    del between_revs[0]
 
166
                    break
 
167
 
 
168
            if not high_revid:
 
169
                high_revid = last_revid
 
170
            if not low_revid:
 
171
                low_revid = self._bzrbranch.get_rev_id(1)
 
172
        finally:
 
173
            repo.unlock()
 
174
 
 
175
        # The spread must include the high revision, to bias
 
176
        # odd numbers of intervening revisions towards the high
 
177
        # side.
 
178
 
 
179
        spread = len(between_revs) + 1
 
180
        if spread < 2:
 
181
            middle_index = 0
 
182
        else:
 
183
            middle_index = (spread / 2) - 1
 
184
 
 
185
        if len(between_revs) > 0:
 
186
            self._middle_revid = between_revs[middle_index]
 
187
        else:
 
188
            self._middle_revid = high_revid
 
189
 
 
190
        self._high_revid = high_revid
 
191
        self._low_revid = low_revid
 
192
 
 
193
    def _switch_wc_to_revno(self, revno, outf):
 
194
        """Move the working tree to the given revno."""
 
195
        self._current.switch(revno)
 
196
        self._current.show_rev_log(out=outf)
 
197
 
 
198
    def _set_status(self, revid, status):
 
199
        """Set the bisect status for the given revid."""
 
200
        if not self.is_done():
 
201
            if status != "done" and revid in [x[0] for x in self._items 
 
202
                                              if x[1] in ['yes', 'no']]:
 
203
                raise RuntimeError("attempting to add revid %s twice" % revid)
 
204
            self._items.append((revid, status))
 
205
 
 
206
    def change_file_name(self, filename):
 
207
        """Switch log files."""
 
208
        self._filename = filename
 
209
 
 
210
    def load(self):
 
211
        """Load the bisection log."""
 
212
        self._items = []
 
213
        if os.path.exists(self._filename):
 
214
            revlog = self._open_for_read()
 
215
            for line in revlog:
 
216
                (revid, status) = line.split()
 
217
                self._items.append((revid, status))
 
218
 
 
219
    def save(self):
 
220
        """Save the bisection log."""
 
221
        revlog = self._open_for_write()
 
222
        for (revid, status) in self._items:
 
223
            revlog.write("%s %s\n" % (revid, status))
 
224
 
 
225
    def is_done(self):
 
226
        """Report whether we've found the right revision."""
 
227
        return len(self._items) > 0 and self._items[-1][1] == "done"
 
228
 
 
229
    def set_status_from_revspec(self, revspec, status):
 
230
        """Set the bisection status for the revision in revspec."""
 
231
        self._load_bzr_tree()
 
232
        revid = revspec[0].in_history(self._bzrbranch).rev_id
 
233
        self._set_status(revid, status)
 
234
 
 
235
    def set_current(self, status):
 
236
        """Set the current revision to the given bisection status."""
 
237
        self._set_status(self._current.get_current_revid(), status)
 
238
 
 
239
    def is_merge_point(self, revid):
 
240
        return len(self.get_parent_revids(revid)) > 1
 
241
 
 
242
    def get_parent_revids(self, revid):
 
243
        repo = self._bzrbranch.repository
 
244
        repo.lock_read()
 
245
        try:
 
246
            retval = repo.get_parent_map([revid]).get(revid, None)
 
247
        finally:
 
248
            repo.unlock()
 
249
        return retval
 
250
 
 
251
    def bisect(self, outf):
 
252
        """Using the current revision's status, do a bisection."""
 
253
        self._find_range_and_middle()
 
254
        # If we've found the "final" revision, check for a
 
255
        # merge point.
 
256
        while ((self._middle_revid == self._high_revid
 
257
                or self._middle_revid == self._low_revid)
 
258
                and self.is_merge_point(self._middle_revid)):
 
259
            for parent in self.get_parent_revids(self._middle_revid):
 
260
                if parent == self._low_revid:
 
261
                    continue
 
262
                else:
 
263
                    self._find_range_and_middle(parent)
 
264
                    break
 
265
        self._switch_wc_to_revno(self._middle_revid, outf)
 
266
        if self._middle_revid == self._high_revid or \
 
267
           self._middle_revid == self._low_revid:
 
268
            self.set_current("done")
 
269
 
 
270
 
 
271
class cmd_bisect(Command):
 
272
    """Find an interesting commit using a binary search.
 
273
 
 
274
    Bisecting, in a nutshell, is a way to find the commit at which
 
275
    some testable change was made, such as the introduction of a bug
 
276
    or feature.  By identifying a version which did not have the
 
277
    interesting change and a later version which did, a developer
 
278
    can test for the presence of the change at various points in
 
279
    the history, eventually ending up at the precise commit when
 
280
    the change was first introduced.
 
281
 
 
282
    This command uses subcommands to implement the search, each
 
283
    of which changes the state of the bisection.  The
 
284
    subcommands are:
 
285
 
 
286
    bzr bisect start
 
287
        Start a bisect, possibly clearing out a previous bisect.
 
288
 
 
289
    bzr bisect yes [-r rev]
 
290
        The specified revision (or the current revision, if not given)
 
291
        has the characteristic we're looking for,
 
292
 
 
293
    bzr bisect no [-r rev]
 
294
        The specified revision (or the current revision, if not given)
 
295
        does not have the characteristic we're looking for,
 
296
 
 
297
    bzr bisect move -r rev
 
298
        Switch to a different revision manually.  Use if the bisect
 
299
        algorithm chooses a revision that is not suitable.  Try to
 
300
        move as little as possible.
 
301
 
 
302
    bzr bisect reset
 
303
        Clear out a bisection in progress.
 
304
 
 
305
    bzr bisect log [-o file]
 
306
        Output a log of the current bisection to standard output, or
 
307
        to the specified file.
 
308
 
 
309
    bzr bisect replay <logfile>
 
310
        Replay a previously-saved bisect log, forgetting any bisection
 
311
        that might be in progress.
 
312
 
 
313
    bzr bisect run <script>
 
314
        Bisect automatically using <script> to determine 'yes' or 'no'.
 
315
        <script> should exit with:
 
316
           0 for yes
 
317
           125 for unknown (like build failed so we could not test)
 
318
           anything else for no
 
319
    """
 
320
 
 
321
    takes_args = ['subcommand', 'args*']
 
322
    takes_options = [Option('output', short_name='o',
 
323
                            help='Write log to this file.', type=unicode),
 
324
                     'revision']
 
325
 
 
326
    def _check(self):
 
327
        """Check preconditions for most operations to work."""
 
328
        if not os.path.exists(bisect_info_path):
 
329
            raise BzrCommandError("No bisection in progress.")
 
330
 
 
331
    def _set_state(self, revspec, state):
 
332
        """Set the state of the given revspec and bisecting.
 
333
 
 
334
        Returns boolean indicating if bisection is done."""
 
335
        bisect_log = BisectLog()
 
336
        if bisect_log.is_done():
 
337
            note("No further bisection is possible.\n")
 
338
            bisect_log._current.show_rev_log(self.outf)
 
339
            return True
 
340
 
 
341
        if revspec:
 
342
            bisect_log.set_status_from_revspec(revspec, state)
 
343
        else:
 
344
            bisect_log.set_current(state)
 
345
        bisect_log.bisect(self.outf)
 
346
        bisect_log.save()
 
347
        return False
 
348
 
 
349
    def run(self, subcommand, args_list, revision=None, output=None):
 
350
        """Handle the bisect command."""
 
351
 
 
352
        log_fn = None
 
353
        if subcommand in ('yes', 'no', 'move') and revision:
 
354
            pass
 
355
        elif subcommand in ('replay', ) and args_list and len(args_list) == 1:
 
356
            log_fn = args_list[0]
 
357
        elif subcommand in ('move', ) and not revision:
 
358
            raise BzrCommandError(
 
359
                "The 'bisect move' command requires a revision.")
 
360
        elif subcommand in ('run', ):
 
361
            run_script = args_list[0]
 
362
        elif args_list or revision:
 
363
            raise BzrCommandError(
 
364
                "Improper arguments to bisect " + subcommand)
 
365
 
 
366
        # Dispatch.
 
367
 
 
368
        if subcommand == "start":
 
369
            self.start()
 
370
        elif subcommand == "yes":
 
371
            self.yes(revision)
 
372
        elif subcommand == "no":
 
373
            self.no(revision)
 
374
        elif subcommand == "move":
 
375
            self.move(revision)
 
376
        elif subcommand == "reset":
 
377
            self.reset()
 
378
        elif subcommand == "log":
 
379
            self.log(output)
 
380
        elif subcommand == "replay":
 
381
            self.replay(log_fn)
 
382
        elif subcommand == "run":
 
383
            self.run_bisect(run_script)
 
384
        else:
 
385
            raise BzrCommandError(
 
386
                "Unknown bisect command: " + subcommand)
 
387
 
 
388
    def reset(self):
 
389
        """Reset the bisect state to no state."""
 
390
        self._check()
 
391
        BisectCurrent().reset()
 
392
        os.unlink(bisect_info_path)
 
393
 
 
394
    def start(self):
 
395
        """Reset the bisect state, then prepare for a new bisection."""
 
396
        if os.path.exists(bisect_info_path):
 
397
            BisectCurrent().reset()
 
398
            os.unlink(bisect_info_path)
 
399
 
 
400
        bisect_log = BisectLog()
 
401
        bisect_log.set_current("start")
 
402
        bisect_log.save()
 
403
 
 
404
    def yes(self, revspec):
 
405
        """Mark that a given revision has the state we're looking for."""
 
406
        self._set_state(revspec, "yes")
 
407
 
 
408
    def no(self, revspec):
 
409
        """Mark that a given revision does not have the state we're looking for."""
 
410
        self._set_state(revspec, "no")
 
411
 
 
412
    def move(self, revspec):
 
413
        """Move to a different revision manually."""
 
414
        current = BisectCurrent()
 
415
        current.switch(revspec)
 
416
        current.show_rev_log(out=self.outf)
 
417
 
 
418
    def log(self, filename):
 
419
        """Write the current bisect log to a file."""
 
420
        self._check()
 
421
        bisect_log = BisectLog()
 
422
        bisect_log.change_file_name(filename)
 
423
        bisect_log.save()
 
424
 
 
425
    def replay(self, filename):
 
426
        """Apply the given log file to a clean state, so the state is
 
427
        exactly as it was when the log was saved."""
 
428
        if os.path.exists(bisect_info_path):
 
429
            BisectCurrent().reset()
 
430
            os.unlink(bisect_info_path)
 
431
        bisect_log = BisectLog(filename)
 
432
        bisect_log.change_file_name(bisect_info_path)
 
433
        bisect_log.save()
 
434
 
 
435
        bisect_log.bisect(self.outf)
 
436
 
 
437
    def run_bisect(self, script):
 
438
        import subprocess
 
439
        note("Starting bisect.")
 
440
        self.start()
 
441
        while True:
 
442
            try:
 
443
                process = subprocess.Popen(script, shell=True)
 
444
                process.wait()
 
445
                retcode = process.returncode
 
446
                if retcode == 0:
 
447
                    done = self._set_state(None, 'yes')
 
448
                elif retcode == 125:
 
449
                    break
 
450
                else:
 
451
                    done = self._set_state(None, 'no')
 
452
                if done:
 
453
                    break
 
454
            except RuntimeError:
 
455
                break