comparison hgext/hbisect.py @ 5721:8d63fa48d44a

bisect: clarify some bisection code

- rename __ancestors... to candidates
- remove head parameter (it's always badrev)
- eliminate comprehensions to shrink parents
- num_ancestors -> n_child name fix
- clarify node selection

5720:bd86c9f2f697

        #self.ui.write("Going back to tip\n")
        #self.repo.update(self.repo.changelog.tip())
        self.is_reset = True
        return 0

    def __ancestors_and_nb_ancestors(self, head):
        """
        returns (anc, n_child) where anc is the set of the ancestors of head
        and n_child is a dictionary with the following mapping:
        node -> number of ancestors (self included)

        ancestors of goodrevs are used as lower limit.
        """
        cl = self.repo.changelog
        stop = {}
        for i in xrange(len(self.goodrevs)-1, -1, -1):
            g = self.goodrevs[i]
            if g in stop:
                continue
            stop.update(cl.reachable(g))

        if head in stop:
            raise util.Abort(_("Inconsistent state, %s:%s is good and bad")
                             % (cl.rev(head), hg.short(head)))

        # build a dict of node -> [number of children, {}]
        n_child = {head: [0, {}]}
        for i in xrange(cl.rev(head)+1):
            n = cl.node(i)
            if n not in d:
                n_child[n] = [0, {}]
            parents = [p for p in cl.parents(n) if p != hg.nullid]
            for p in parents:
                n_child[p][0] += 1

        for i in xrange(cl.rev(head)+1):
            n = cl.node(i)
            parents = [p for p in cl.parents(n) if p != hg.nullid]
            for p in parents:
                n_child[p][0] -= 1
                if not n in stop:
                    n_child[n][1].update(n_child[p][1])
                if n_child[p][0] == 0:
                    n_child[p] = len(n_child[p][1])
            if not n in stop:
                n_child[n][1][n] = 1
            if n_child[n][0] == 0:
                if n == head:
                    anc = n_child[n][1]
                n_child[n] = len(n_child[n][1])
        return anc, n_child

    def next(self):
        if not self.badrev:
            raise util.Abort(_("You should give at least one bad revision"))
        if not self.goodrevs:
            self.ui.warn(_("No good revision given\n"))
            self.ui.warn(_("Marking the first revision as good\n"))
        ancestors, num_ancestors = self.__ancestors_and_nb_ancestors(
                                    self.badrev)
        tot = len(ancestors)
        if tot == 1:
            if self.badrev not in ancestors:
                raise util.Abort(_("Could not find the first bad revision"))
            self.ui.write(_("The first bad revision is:\n"))
            displayer = cmdutil.show_changeset(self.ui, self.repo, {})
            displayer.show(changenode=self.badrev)
            return None
        best_rev = None
        best_len = -1
        for n in ancestors:
            l = num_ancestors[n]
            l = min(l, tot - l)
            if l > best_len:
                best_len = l
                best_rev = n
        assert best_rev is not None
        nb_tests = 0
        q, r = divmod(tot, 2)
        while q:
            nb_tests += 1
            q, r = divmod(q, 2)
        msg = _("Testing changeset %s:%s (%s changesets remaining, "
                "~%s tests)\n") % (self.repo.changelog.rev(best_rev),
                                   hg.short(best_rev), tot, nb_tests)
        self.ui.write(msg)
        return best_rev

5721:8d63fa48d44a

        #self.ui.write("Going back to tip\n")
        #self.repo.update(self.repo.changelog.tip())
        self.is_reset = True
        return 0

    def candidates(self):
        """
        returns (anc, n_child) where anc is the set of the ancestors of head
        and n_child is a dictionary with the following mapping:
        node -> number of ancestors (self included)

        ancestors of goodrevs are used as lower limit.
        """
        cl = self.repo.changelog
        stop = {}
        bad = self.badrev
        for i in xrange(len(self.goodrevs)-1, -1, -1):
            g = self.goodrevs[i]
            if g in stop:
                continue
            stop.update(cl.reachable(g))

        if bad in stop:
            raise util.Abort(_("Inconsistent state, %s:%s is good and bad")
                             % (cl.rev(bad), hg.short(bad)))

        # build a dict of node -> [number of children, {}]
        n_child = {bad: [0, {}]}
        for i in xrange(cl.rev(bad)+1):
            n = cl.node(i)
            if n not in n_child:
                n_child[n] = [0, {}]
            # increment count of each parent
            for p in cl.parents(n):
                if p != hg.nullid:
                    n_child[p][0] += 1

        for i in xrange(cl.rev(bad)+1):
            n = cl.node(i)
            for p in cl.parents(n):
                if p != hg.nullid:
                    n_child[p][0] -= 1
                    if not n in stop:
                        n_child[n][1].update(n_child[p][1])
                    if n_child[p][0] == 0:
                        n_child[p] = len(n_child[p][1])
            if not n in stop:
                n_child[n][1][n] = 1
            if n_child[n][0] == 0:
                if n == bad:
                    anc = n_child[n][1]
                n_child[n] = len(n_child[n][1])
        return anc, n_child

    def next(self):
        if not self.badrev:
            raise util.Abort(_("You should give at least one bad revision"))
        if not self.goodrevs:
            self.ui.warn(_("No good revision given\n"))
            self.ui.warn(_("Marking the first revision as good\n"))
        ancestors, n_child = self.candidates()

        # have we narrowed it down to one entry?
        tot = len(ancestors)
        if tot == 1:
            if self.badrev not in ancestors:
                raise util.Abort(_("Could not find the first bad revision"))
            self.ui.write(_("The first bad revision is:\n"))
            displayer = cmdutil.show_changeset(self.ui, self.repo, {})
            displayer.show(changenode=self.badrev)
            return None

        # find the best node to test
        best_rev = None
        best_len = -1
        for n in ancestors:
            a = n_child[n] # number of children
            b = tot - a # number of ancestors
            value = min(a, b) # how good is this test?
            if value > best_len:
                best_len = value
                best_rev = n
        assert best_rev is not None

        # compute the approximate number of remaining tests
        nb_tests = 0
        q, r = divmod(tot, 2)
        while q:
            nb_tests += 1
            q, r = divmod(q, 2)

        msg = _("Testing changeset %s:%s (%s changesets remaining, "
                "~%s tests)\n") % (self.repo.changelog.rev(best_rev),
                                   hg.short(best_rev), tot, nb_tests)
        self.ui.write(msg)
        return best_rev