comparison hgext/hbisect.py @ 5736:6e79d5e0e541

bisect: keep history of all bad revisions

- use a single state dict
- find the minimum bad revision

5735:9079081b8982

class bisect(object):
    """dichotomic search in the DAG of changesets"""
    def __init__(self, ui, repo):
        self.repo = repo
        self.ui = ui
        self.goodnodes = []
        self.skipnodes = []
        self.badnode = None

        p = self.repo.join("bisect.state")
        if os.path.exists(p):
            for l in self.repo.opener("bisect.state"):
                type, node = l[:-1].split()
                node = self.repo.lookup(node)
                if type == "good":
                    self.goodnodes.append(node)
                elif type == "skip":
                    self.skipnodes.append(node)
                elif type == "bad":
                    self.badnode = node

    def write(self):
        f = self.repo.opener("bisect.state", "w")
        for n in self.goodnodes:
            f.write("good %s\n" % hg.hex(n))
        for n in self.skipnodes:
            f.write("skip %s\n" % hg.hex(n))
        if self.badnode:
            f.write("bad %s\n" % hg.hex(self.badnode))

    def init(self):
        """start a new bisection"""
        p = self.repo.join("bisect.state")
        if os.path.exists(p):
            os.unlink(p)

    def bisect(self):
        cl = self.repo.changelog
        clparents = cl.parentrevs
        bad = self.badnode
        badrev = cl.rev(bad)

        # build ancestors array
        ancestors = [[]] * (cl.count() + 1) # an extra for [-1]

        # clear goodnodes from array
        for good in self.goodnodes:
            ancestors[cl.rev(good)] = None
        for rev in xrange(cl.count(), -1, -1):
            if ancestors[rev] is None:
                for prev in clparents(rev):
                    ancestors[prev] = None

            raise util.Abort(_("Could not find the first bad revision"))

        # have we narrowed it down to one entry?
        tot = len(ancestors[badrev])
        if tot == 1:
            return (self.badnode, 0)

        # find the best node to test
        best_rev = None
        best_len = -1
        skip = dict.fromkeys([cl.rev(s) for s in self.skipnodes])
        for n in ancestors[badrev]:
            if n in skip:
                continue
            a = len(ancestors[n]) # number of ancestors
            b = tot - a # number of non-ancestors

        return (best_node, tot)

    def next(self):
        """find and update to the next revision to test"""
        if self.goodnodes and self.badnode:
            node, changesets = self.bisect()

            if changesets == 0:
                self.ui.write(_("The first bad revision is:\n"))
                displayer = cmdutil.show_changeset(self.ui, self.repo, {})

                cmdutil.bail_if_changed(self.repo)
                return hg.clean(self.repo, node)

    def good(self, rev=None):
        """mark revision as good and update to the next revision to test"""
        self.goodnodes.append(self.repo.lookup(rev or '.'))
        self.write()
        return self.next()

    def skip(self, rev=None):
        """mark revision as skipped and update to the next revision to test"""
        self.skipnodes.append(self.repo.lookup(rev or '.'))
        self.write()
        return self.next()

    def bad(self, rev=None):
        """mark revision as bad and update to the next revision to test"""
        self.badnode = self.repo.lookup(rev or '.')
        self.write()
        return self.next()

def bisect_run(ui, repo, node=None, extra=None,
               reset=None, good=None, bad=None, skip=None):

5736:6e79d5e0e541

class bisect(object):
    """dichotomic search in the DAG of changesets"""
    def __init__(self, ui, repo):
        self.repo = repo
        self.ui = ui
        self.state = {'good': [], 'bad': [], 'skip': []}

        p = self.repo.join("bisect.state")
        if os.path.exists(p):
            for l in self.repo.opener("bisect.state"):
                kind, node = l[:-1].split()
                node = self.repo.lookup(node)
                if kind not in self.state:
                    raise util.Abort(_("unknown bisect kind %s") % kind)
                self.state[kind].append(node)

    def write(self):
        f = self.repo.opener("bisect.state", "w")
        for kind in self.state:
            for node in self.state[kind]:
                f.write("%s %s\n" % (kind, hg.hex(node)))

    def init(self):
        """start a new bisection"""
        p = self.repo.join("bisect.state")
        if os.path.exists(p):
            os.unlink(p)

    def bisect(self):
        cl = self.repo.changelog
        clparents = cl.parentrevs
        # only the earliest bad revision matters
        badrev = min([cl.rev(n) for n in self.state['bad']])
        bad = cl.node(badrev)

        # build ancestors array
        ancestors = [[]] * (cl.count() + 1) # an extra for [-1]

        # clear good revs from array
        for node in self.state['good']:
            ancestors[cl.rev(node)] = None
        for rev in xrange(cl.count(), -1, -1):
            if ancestors[rev] is None:
                for prev in clparents(rev):
                    ancestors[prev] = None

            raise util.Abort(_("Could not find the first bad revision"))

        # have we narrowed it down to one entry?
        tot = len(ancestors[badrev])
        if tot == 1:
            return (bad, 0)

        # find the best node to test
        best_rev = None
        best_len = -1
        skip = dict.fromkeys([cl.rev(n) for n in self.state['skip']])
        for n in ancestors[badrev]:
            if n in skip:
                continue
            a = len(ancestors[n]) # number of ancestors
            b = tot - a # number of non-ancestors

        return (best_node, tot)

    def next(self):
        """find and update to the next revision to test"""
        if self.state['good'] and self.state['bad']:
            node, changesets = self.bisect()

            if changesets == 0:
                self.ui.write(_("The first bad revision is:\n"))
                displayer = cmdutil.show_changeset(self.ui, self.repo, {})

                cmdutil.bail_if_changed(self.repo)
                return hg.clean(self.repo, node)

    def good(self, rev=None):
        """mark revision as good and update to the next revision to test"""
        self.state['good'].append(self.repo.lookup(rev or '.'))
        self.write()
        return self.next()

    def skip(self, rev=None):
        """mark revision as skipped and update to the next revision to test"""
        self.state['skip'].append(self.repo.lookup(rev or '.'))
        self.write()
        return self.next()

    def bad(self, rev=None):
        """mark revision as bad and update to the next revision to test"""
        self.state['bad'].append(self.repo.lookup(rev or '.'))
        self.write()
        return self.next()

def bisect_run(ui, repo, node=None, extra=None,
               reset=None, good=None, bad=None, skip=None):