# changelog bisection for mercurial

#

# Copyright 2007 Matt Mackall

# 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 i18n import _

import hg, util

def bisect(changelog, state):

    clparents = changelog.parentrevs

    skip = dict.fromkeys([changelog.rev(n) for n in state['skip']])

    def buildancestors(bad, good):

        # only the earliest bad revision matters

        badrev = min([changelog.rev(n) for n in bad])

        goodrevs = [changelog.rev(n) for n in good]

        # build ancestors array

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

        # clear good revs from array

        for node in goodrevs:

            ancestors[node] = None

        for rev in xrange(changelog.count(), -1, -1):

            if ancestors[rev] is None:

                for prev in clparents(rev):

                    ancestors[prev] = None

        if ancestors[badrev] is None:

        return badrev, ancestors

    good = 0

    badrev, ancestors = buildancestors(state['bad'], state['good'])

    if not ancestors: # looking for bad to good transition?

        good = 1

        badrev, ancestors = buildancestors(state['good'], state['bad'])

    if not ancestors: # now we're confused

        raise util.Abort(_("Inconsistent state, %s:%s is good and bad")

                         % (badrev, hg.short(bad)))

    # build children dict

    children = {}

    visit = [badrev]

    candidates = []

    while visit:

        rev = visit.pop(0)

        if ancestors[rev] == []:

            candidates.append(rev)

            for prev in clparents(rev):

                if prev != -1:

                    if prev in children:

                        children[prev].append(rev)

                    else:

                        children[prev] = [rev]

                        visit.append(prev)

    candidates.sort()

    # have we narrowed it down to one entry?

    tot = len(candidates)

    if tot == 1:

        return (bad, 0, good)

    perfect = tot / 2

    # find the best node to test

    best_rev = None

    best_len = -1

    poison = {}

    for rev in candidates:

        if rev in poison:

            for c in children.get(rev, []):

                poison[c] = True # poison children

            continue

        a = ancestors[rev] or [rev]

        ancestors[rev] = None

        x = len(a) # number of ancestors

        y = tot - x # number of non-ancestors

        value = min(x, y) # how good is this test?

        if value > best_len and rev not in skip:

            best_len = value

            best_rev = rev

            if value == perfect: # found a perfect candidate? quit early

                break

        if y < perfect: # all downhill from here?

            for c in children.get(rev, []):

                poison[c] = True # poison children

            continue

        for c in children.get(rev, []):

            if ancestors[c]:

                ancestors[c] = dict.fromkeys(ancestors[c] + a).keys()

            else:

                ancestors[c] = a + [c]

    assert best_rev is not None

    best_node = changelog.node(best_rev)

    return (best_node, tot, good)