mercurial/hbisect.py
author Dirkjan Ochtman <dirkjan@ochtman.nl>
Wed, 18 Jun 2008 10:15:59 +0200
changeset 6694 b3602c98c686
parent 6692 683428d1e639
child 6750 fb42030d79d6
permissions -rw-r--r--
merge incorporation of graph into paper style
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 _
6217
fe8dbbe9520d Avoid importing mercurial.node/mercurial.repo stuff from mercurial.hg
Joel Rosdahl <joel@rosdahl.net>
parents: 5777
diff changeset
    11
from node import short
fe8dbbe9520d Avoid importing mercurial.node/mercurial.repo stuff from mercurial.hg
Joel Rosdahl <joel@rosdahl.net>
parents: 5777
diff changeset
    12
import util
1367
a7678cbd7c28 bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff changeset
    13
5775
2dd202a6e15b bisect: make bisect a built-in command
Matt Mackall <mpm@selenic.com>
parents: 5774
diff changeset
    14
def bisect(changelog, state):
5737
6c8df073c3ee bisect: remove class
Matt Mackall <mpm@selenic.com>
parents: 5736
diff changeset
    15
    clparents = changelog.parentrevs
5770
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
    16
    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
    17
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    18
    def buildancestors(bad, good):
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    19
        # only the earliest bad revision matters
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    20
        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
    21
        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
    22
        # build ancestors array
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    23
        ancestors = [[]] * (changelog.count() + 1) # an extra for [-1]
1367
a7678cbd7c28 bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff changeset
    24
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    25
        # clear good revs from array
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    26
        for node in goodrevs:
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    27
            ancestors[node] = None
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    28
        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
    29
            if ancestors[rev] is None:
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    30
                for prev in clparents(rev):
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    31
                    ancestors[prev] = None
1367
a7678cbd7c28 bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff changeset
    32
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    33
        if ancestors[badrev] is None:
5777
51776e50bc8c bisect: improve tests
Matt Mackall <mpm@selenic.com>
parents: 5776
diff changeset
    34
            return badrev, None
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    35
        return badrev, ancestors
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    36
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    37
    good = 0
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    38
    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
    39
    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
    40
        good = 1
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    41
        badrev, ancestors = buildancestors(state['good'], state['bad'])
5777
51776e50bc8c bisect: improve tests
Matt Mackall <mpm@selenic.com>
parents: 5776
diff changeset
    42
    bad = changelog.node(badrev)
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    43
    if not ancestors: # now we're confused
5737
6c8df073c3ee bisect: remove class
Matt Mackall <mpm@selenic.com>
parents: 5736
diff changeset
    44
        raise util.Abort(_("Inconsistent state, %s:%s is good and bad")
6217
fe8dbbe9520d Avoid importing mercurial.node/mercurial.repo stuff from mercurial.hg
Joel Rosdahl <joel@rosdahl.net>
parents: 5777
diff changeset
    45
                         % (badrev, short(bad)))
5723
e3b09819496b bisect: switch to rev-based calculation
Matt Mackall <mpm@selenic.com>
parents: 5722
diff changeset
    46
5768
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    47
    # build children dict
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    48
    children = {}
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    49
    visit = [badrev]
5769
49809f4a38d8 bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents: 5768
diff changeset
    50
    candidates = []
5768
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    51
    while visit:
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    52
        rev = visit.pop(0)
5767
dd5f8ed31057 bisect: propagate ancestor lists directly to children
Matt Mackall <mpm@selenic.com>
parents: 5766
diff changeset
    53
        if ancestors[rev] == []:
5769
49809f4a38d8 bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents: 5768
diff changeset
    54
            candidates.append(rev)
5767
dd5f8ed31057 bisect: propagate ancestor lists directly to children
Matt Mackall <mpm@selenic.com>
parents: 5766
diff changeset
    55
            for prev in clparents(rev):
5768
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    56
                if prev != -1:
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    57
                    if prev in children:
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    58
                        children[prev].append(rev)
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    59
                    else:
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    60
                        children[prev] = [rev]
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
    61
                        visit.append(prev)
5767
dd5f8ed31057 bisect: propagate ancestor lists directly to children
Matt Mackall <mpm@selenic.com>
parents: 5766
diff changeset
    62
5769
49809f4a38d8 bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents: 5768
diff changeset
    63
    candidates.sort()
5770
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
    64
    # 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
    65
    tot = len(candidates)
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
    66
    if tot == 1:
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
    67
        return (bad, 0, good)
5771
9d3f49f52a4a bisect: stop early if we find a perfect candidate
Matt Mackall <mpm@selenic.com>
parents: 5770
diff changeset
    68
    perfect = tot / 2
5769
49809f4a38d8 bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents: 5768
diff changeset
    69
5770
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
    70
    # find the best node to test
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
    71
    best_rev = None
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
    72
    best_len = -1
5772
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
    73
    poison = {}
5769
49809f4a38d8 bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents: 5768
diff changeset
    74
    for rev in candidates:
5772
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
    75
        if rev in poison:
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
    76
            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
    77
                poison[c] = True # poison children
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
    78
            continue
5773
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    79
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    80
        a = ancestors[rev] or [rev]
5770
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
    81
        ancestors[rev] = None
5773
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    82
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    83
        x = len(a) # number of ancestors
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    84
        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
    85
        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
    86
        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
    87
            best_len = value
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    88
            best_rev = rev
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    89
            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
    90
                break
5772
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
    91
5773
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    92
        if y < perfect: # all downhill from here?
6694
b3602c98c686 merge incorporation of graph into paper style
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents: 6692
diff changeset
    93
            for c in children.get(rev, []):
b3602c98c686 merge incorporation of graph into paper style
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents: 6692
diff changeset
    94
                poison[c] = True # poison children
b3602c98c686 merge incorporation of graph into paper style
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents: 6692
diff changeset
    95
            continue
5772
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
    96
5773
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    97
        for c in children.get(rev, []):
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
    98
            if ancestors[c]:
5774
c850a8640981 bisect: faster merging
Matt Mackall <mpm@selenic.com>
parents: 5773
diff changeset
    99
                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
   100
            else:
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
   101
                ancestors[c] = a + [c]
5734
944b231fa0e7 bisect: move reporting out of core bisect function
Matt Mackall <mpm@selenic.com>
parents: 5733
diff changeset
   102
5737
6c8df073c3ee bisect: remove class
Matt Mackall <mpm@selenic.com>
parents: 5736
diff changeset
   103
    assert best_rev is not None
6c8df073c3ee bisect: remove class
Matt Mackall <mpm@selenic.com>
parents: 5736
diff changeset
   104
    best_node = changelog.node(best_rev)
1367
a7678cbd7c28 bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff changeset
   105
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
   106
    return (best_node, tot, good)