mercurial/hbisect.py
author Matt Mackall <mpm@selenic.com>
Mon, 31 Dec 2007 18:20:34 -0600
changeset 5776 35ec669cdd43
parent 5775 2dd202a6e15b
child 5777 51776e50bc8c
permissions -rw-r--r--
bisect: handle search for bad to good transitions Automatically detect whether we're looking for a bad to good transition rather than the usual good to bad transition by detecting when badrev is inside the good set and flipping good/bad.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
5775
2dd202a6e15b bisect: make bisect a built-in command
Matt Mackall <mpm@selenic.com>
parents: 5774
diff changeset
     1
# changelog bisection for mercurial
1367
a7678cbd7c28 bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff changeset
     2
#
5775
2dd202a6e15b bisect: make bisect a built-in command
Matt Mackall <mpm@selenic.com>
parents: 5774
diff changeset
     3
# Copyright 2007 Matt Mackall
1861
65949d1c9bf7 Added copyright information to hbisect.py
Thomas Arendsen Hein <thomas@intevation.de>
parents: 1856
diff changeset
     4
# Copyright 2005, 2006 Benoit Boissinot <benoit.boissinot@ens-lyon.org>
65949d1c9bf7 Added copyright information to hbisect.py
Thomas Arendsen Hein <thomas@intevation.de>
parents: 1856
diff changeset
     5
# Inspired by git bisect, extension skeleton taken from mq.py.
65949d1c9bf7 Added copyright information to hbisect.py
Thomas Arendsen Hein <thomas@intevation.de>
parents: 1856
diff changeset
     6
#
1367
a7678cbd7c28 bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff changeset
     7
# This software may be used and distributed according to the terms
a7678cbd7c28 bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff changeset
     8
# of the GNU General Public License, incorporated herein by reference.
a7678cbd7c28 bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff changeset
     9
5775
2dd202a6e15b bisect: make bisect a built-in command
Matt Mackall <mpm@selenic.com>
parents: 5774
diff changeset
    10
from i18n import _
2dd202a6e15b bisect: make bisect a built-in command
Matt Mackall <mpm@selenic.com>
parents: 5774
diff changeset
    11
import hg, util
1367
a7678cbd7c28 bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff changeset
    12
5775
2dd202a6e15b bisect: make bisect a built-in command
Matt Mackall <mpm@selenic.com>
parents: 5774
diff changeset
    13
def bisect(changelog, state):
5737
6c8df073c3ee bisect: remove class
Matt Mackall <mpm@selenic.com>
parents: 5736
diff changeset
    14
    clparents = changelog.parentrevs
5770
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
    15
    skip = dict.fromkeys([changelog.rev(n) for n in state['skip']])
1367
a7678cbd7c28 bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff changeset
    16
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    17
    def buildancestors(bad, good):
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    18
        # only the earliest bad revision matters
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    19
        badrev = min([changelog.rev(n) for n in bad])
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    20
        goodrevs = [changelog.rev(n) for n in good]
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    21
        # build ancestors array
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    22
        ancestors = [[]] * (changelog.count() + 1) # an extra for [-1]
1367
a7678cbd7c28 bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff changeset
    23
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    24
        # clear good revs from array
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    25
        for node in goodrevs:
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    26
            ancestors[node] = None
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    27
        for rev in xrange(changelog.count(), -1, -1):
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    28
            if ancestors[rev] is None:
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    29
                for prev in clparents(rev):
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    30
                    ancestors[prev] = None
1367
a7678cbd7c28 bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff changeset
    31
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    32
        if ancestors[badrev] is None:
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    33
            return None, None
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    34
        return badrev, ancestors
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    35
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    36
    good = 0
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    37
    badrev, ancestors = buildancestors(state['bad'], state['good'])
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    38
    if not ancestors: # looking for bad to good transition?
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    39
        good = 1
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    40
        badrev, ancestors = buildancestors(state['good'], state['bad'])
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    41
    if not ancestors: # now we're confused
5737
6c8df073c3ee bisect: remove class
Matt Mackall <mpm@selenic.com>
parents: 5736
diff changeset
    42
        raise util.Abort(_("Inconsistent state, %s:%s is good and bad")
6c8df073c3ee bisect: remove class
Matt Mackall <mpm@selenic.com>
parents: 5736
diff changeset
    43
                         % (badrev, hg.short(bad)))
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    44
    bad = changelog.node(badrev)
5723
e3b09819496b bisect: switch to rev-based calculation
Matt Mackall <mpm@selenic.com>
parents: 5722
diff changeset
    45
5768
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    46
    # build children dict
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    47
    children = {}
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    48
    visit = [badrev]
5769
49809f4a38d8 bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents: 5768
diff changeset
    49
    candidates = []
5768
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    50
    while visit:
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    51
        rev = visit.pop(0)
5767
dd5f8ed31057 bisect: propagate ancestor lists directly to children
Matt Mackall <mpm@selenic.com>
parents: 5766
diff changeset
    52
        if ancestors[rev] == []:
5769
49809f4a38d8 bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents: 5768
diff changeset
    53
            candidates.append(rev)
5767
dd5f8ed31057 bisect: propagate ancestor lists directly to children
Matt Mackall <mpm@selenic.com>
parents: 5766
diff changeset
    54
            for prev in clparents(rev):
5768
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    55
                if prev != -1:
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    56
                    if prev in children:
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    57
                        children[prev].append(rev)
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    58
                    else:
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    59
                        children[prev] = [rev]
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    60
                        visit.append(prev)
5767
dd5f8ed31057 bisect: propagate ancestor lists directly to children
Matt Mackall <mpm@selenic.com>
parents: 5766
diff changeset
    61
5769
49809f4a38d8 bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents: 5768
diff changeset
    62
    candidates.sort()
5770
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
    63
    # have we narrowed it down to one entry?
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
    64
    tot = len(candidates)
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
    65
    if tot == 1:
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    66
        return (bad, 0, good)
5771
9d3f49f52a4a bisect: stop early if we find a perfect candidate
Matt Mackall <mpm@selenic.com>
parents: 5770
diff changeset
    67
    perfect = tot / 2
5769
49809f4a38d8 bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents: 5768
diff changeset
    68
5770
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
    69
    # find the best node to test
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
    70
    best_rev = None
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
    71
    best_len = -1
5772
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
    72
    poison = {}
5769
49809f4a38d8 bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents: 5768
diff changeset
    73
    for rev in candidates:
5772
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
    74
        if rev in poison:
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
    75
            for c in children.get(rev, []):
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
    76
                poison[c] = True # poison children
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
    77
            continue
5773
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    78
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    79
        a = ancestors[rev] or [rev]
5770
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
    80
        ancestors[rev] = None
5773
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    81
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    82
        x = len(a) # number of ancestors
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    83
        y = tot - x # number of non-ancestors
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    84
        value = min(x, y) # how good is this test?
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    85
        if value > best_len and rev not in skip:
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    86
            best_len = value
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    87
            best_rev = rev
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    88
            if value == perfect: # found a perfect candidate? quit early
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    89
                break
5772
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
    90
5773
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    91
        if y < perfect: # all downhill from here?
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    92
            for c in children.get(rev, []):
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    93
                poison[c] = True # poison children
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    94
            continue
5772
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
    95
5773
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    96
        for c in children.get(rev, []):
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    97
            if ancestors[c]:
5774
c850a8640981 bisect: faster merging
Matt Mackall <mpm@selenic.com>
parents: 5773
diff changeset
    98
                ancestors[c] = dict.fromkeys(ancestors[c] + a).keys()
5773
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    99
            else:
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
   100
                ancestors[c] = a + [c]
5734
944b231fa0e7 bisect: move reporting out of core bisect function
Matt Mackall <mpm@selenic.com>
parents: 5733
diff changeset
   101
5737
6c8df073c3ee bisect: remove class
Matt Mackall <mpm@selenic.com>
parents: 5736
diff changeset
   102
    assert best_rev is not None
6c8df073c3ee bisect: remove class
Matt Mackall <mpm@selenic.com>
parents: 5736
diff changeset
   103
    best_node = changelog.node(best_rev)
1367
a7678cbd7c28 bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff changeset
   104
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
   105
    return (best_node, tot, good)