# bisect extension for mercurial

#

# Copyright 2005, 2006 Benoit Boissinot <benoit.boissinot@ens-lyon.org>

# Inspired by git bisect, extension skeleton taken from mq.py.

#

# This software may be used and distributed according to the terms

# of the GNU General Public License, incorporated herein by reference.

from mercurial.demandload import demandload

demandload(globals(), "os sys sets mercurial:hg,util")

versionstr = "0.0.3"

def lookup_rev(ui, repo, rev=None):

    """returns rev or the checked-out revision if rev is None"""

    if not rev is None:

        return repo.lookup(rev)

    parents = [p for p in repo.dirstate.parents() if p != hg.nullid]

    if len(parents) != 1:

        ui.warn("unexpected number of parents\n")

        ui.warn("please commit or revert\n")

        sys.exit(1)

    return parents.pop()

def check_clean(ui, repo):

        modified, added, removed, deleted, unknown = repo.changes()

        if modified or added or removed:

            ui.warn("Repository is not clean, please commit or revert\n")

            sys.exit(1)

class bisect(object):

    """dichotomic search in the DAG of changesets"""

    def __init__(self, ui, repo):

        self.repo = repo

        self.path = repo.join("bisect")

        self.opener = util.opener(self.path)

        self.ui = ui

        self.goodrevs = []

        self.badrev = None

        self.good_dirty = 0

        self.bad_dirty = 0

        self.good_path = "good"

        self.bad_path = "bad"

        if os.path.exists(os.path.join(self.path, self.good_path)):

            self.goodrevs = self.opener(self.good_path).read().splitlines()

            self.goodrevs = [hg.bin(x) for x in self.goodrevs]

        if os.path.exists(os.path.join(self.path, self.bad_path)):

            r = self.opener(self.bad_path).read().splitlines()

            if r:

                self.badrev = hg.bin(r.pop(0))

    def __del__(self):

        if not os.path.isdir(self.path):

            return

        f = self.opener(self.good_path, "w")

        f.write("\n".join([hg.hex(r) for r in  self.goodrevs]))

        if len(self.goodrevs) > 0:

            f.write("\n")

        f = self.opener(self.bad_path, "w")

        if self.badrev:

            f.write(hg.hex(self.badrev) + "\n")

    def init(self):

        """start a new bisection"""

        if os.path.isdir(self.path):

            self.ui.warn("bisect directory already exists\n")

            return 1

        os.mkdir(self.path)

        check_clean(self.ui, self.repo)

        return 0

    def reset(self):

        """finish a bisection"""

        if os.path.isdir(self.path):

            sl = [os.path.join(self.path, p)

                  for p in [self.bad_path, self.good_path]]

            for s in sl:

                if os.path.exists(s):

                    os.unlink(s)

            os.rmdir(self.path)

        # Not sure about this

        #self.ui.write("Going back to tip\n")

        #self.repo.update(self.repo.changelog.tip())

        return 1

    def num_ancestors(self, head=None, stop=None):

        """

        returns a dict with the mapping:

        node -> number of ancestors (self included)

        for all nodes who are ancestor of head and

        not in stop.

        """

        if head is None:

            head = self.badrev

        return self.__ancestors_and_nb_ancestors(head, stop)[1]

    def ancestors(self, head=None, stop=None):

        """

        returns the set of the ancestors of head (self included)

        who are not in stop.

        """

        if head is None:

            head = self.badrev

        return self.__ancestors_and_nb_ancestors(head, stop)[0]

    def __ancestors_and_nb_ancestors(self, head, stop=None):

        """

        if stop is None then ancestors of goodrevs are used as

        lower limit.

        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)

        """

        cl = self.repo.changelog

        if not stop:

            stop = sets.Set([])

            for i in xrange(len(self.goodrevs)-1, -1, -1):

                g = self.goodrevs[i]

                if g in stop:

                    continue

                stop.update(cl.reachable(g))

        def num_children(a):

            """

            returns a dictionnary with the following mapping

            node -> [number of children, empty set]

            """

            d = {a: [0, sets.Set([])]}

            for i in xrange(cl.rev(a)+1):

                n = cl.node(i)

                if not d.has_key(n):

                    d[n] = [0, sets.Set([])]

                parents = [p for p in cl.parents(n) if p != hg.nullid]

                for p in parents:

                    d[p][0] += 1

            return d

        if head in stop:

            self.ui.warn("Unconsistent state, %s is good and bad\n"

                          % hg.hex(head))

            sys.exit(1)

        n_child = num_children(head)

        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].union_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].add(n)

            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:

            self.ui.warn("You should give at least one bad\n")

            sys.exit(1)

        if not self.goodrevs:

            self.ui.warn("No good revision given\n")

            self.ui.warn("Assuming the first revision is good\n")

        ancestors, num_ancestors = self.__ancestors_and_nb_ancestors(

                                    self.badrev)

        tot = len(ancestors)

        if tot == 1:

            if ancestors.pop() != self.badrev:

                self.ui.warn("Could not find the first bad revision\n")

                sys.exit(1)

            self.ui.write(

                "The first bad revision is : %s\n" % hg.hex(self.badrev))

            sys.exit(0)

        self.ui.write("%d revisions left\n" % tot)

        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

        return best_rev

    def autonext(self):

        """find and update to the next revision to test"""

        check_clean(self.ui, self.repo)

        rev = self.next()

        self.ui.write("Now testing %s\n" % hg.hex(rev))

        return self.repo.update(rev, force=True)

    def good(self, rev):

        self.goodrevs.append(rev)

    def autogood(self, rev=None):

        """mark revision as good and update to the next revision to test"""

        check_clean(self.ui, self.repo)

        rev = lookup_rev(self.ui, self.repo, rev)

        self.good(rev)

        if self.badrev:

            self.autonext()

    def bad(self, rev):

        self.badrev = rev

    def autobad(self, rev=None):

        """mark revision as bad and update to the next revision to test"""

        check_clean(self.ui, self.repo)

        rev = lookup_rev(self.ui, self.repo, rev)

        self.bad(rev)

        if self.goodrevs:

            self.autonext()

# should we put it in the class ?

def test(ui, repo, rev):

    """test the bisection code"""

    b = bisect(ui, repo)

    rev = repo.lookup(rev)

    ui.write("testing with rev %s\n" % hg.hex(rev))

    anc = b.ancestors()

    while len(anc) > 1:

        if not rev in anc:

            ui.warn("failure while bisecting\n")

            sys.exit(1)

        ui.write("it worked :)\n")

        new_rev = b.next()

        ui.write("choosing if good or bad\n")

        if rev in b.ancestors(head=new_rev):

            b.bad(new_rev)

            ui.write("it is bad\n")

        else:

            b.good(new_rev)

            ui.write("it is good\n")

        anc = b.ancestors()

        repo.update(new_rev, force=True)

    for v in anc:

        if v != rev:

            ui.warn("fail to found cset! :(\n")

            return 1

    ui.write("Found bad cset: %s\n" % hg.hex(b.badrev))

    ui.write("Everything is ok :)\n")

    return 0

def bisect_run(ui, repo, cmd=None, *args):

    """bisect extension: dichotomic search in the DAG of changesets

for subcommands see "hg bisect help\"

    """

    def help_(cmd=None, *args):

        """show help for a given bisect subcommand or all subcommands"""

        cmdtable = bisectcmdtable

        if cmd:

            doc = cmdtable[cmd][0].__doc__

            synopsis = cmdtable[cmd][2]

            ui.write(synopsis + "\n")

            ui.write("\n" + doc + "\n")

            return

        ui.write("list of subcommands for the bisect extension\n\n")

        cmds = cmdtable.keys()

        cmds.sort()

        m = max([len(c) for c in cmds])

        for cmd in cmds:

            doc = cmdtable[cmd][0].__doc__.splitlines(0)[0].rstrip()

            ui.write(" %-*s   %s\n" % (m, cmd, doc))

    b = bisect(ui, repo)

    bisectcmdtable = {

        "init": (b.init, 0, "hg bisect init"),

        "bad": (b.autobad, 1, "hg bisect bad [<rev>]"),

        "good": (b.autogood, 1, "hg bisect good [<rev>]"),

        "next": (b.autonext, 0, "hg bisect next"),

        "reset": (b.reset, 0, "hg bisect reset"),

        "help": (help_, 1, "hg bisect help [<subcommand>]"),

    }

    if not bisectcmdtable.has_key(cmd):

        ui.warn("bisect: Unknown sub-command\n")

        return help_()

    if len(args) > bisectcmdtable[cmd][1]:

        ui.warn("bisect: Too many arguments\n")

        return help_()

    return bisectcmdtable[cmd][0](*args)

cmdtable = {

    "bisect": (bisect_run, [], "hg bisect [help|init|reset|next|good|bad]"),

    #"bisect-test": (test, [], "hg bisect-test rev"),

}