# 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
    # only the earliest bad revision matters
    badrev = min([changelog.rev(n) for n in state['bad']])
    bad = changelog.node(badrev)
    skip = dict.fromkeys([changelog.rev(n) for n in state['skip']])

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

    # clear good revs from array
    for node in state['good']:
        ancestors[changelog.rev(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:
        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)
    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)