mercurial/ancestor.py
author Mads Kiilerich <madski@unity3d.com>
Mon, 24 Feb 2014 22:42:13 +0100
changeset 20555 4add43865a9b
parent 20034 1e5b38a919dd
child 20985 231ccc08670c
permissions -rw-r--r--
ancestors: remove unnecessary handling of 'left' If one of the initial nodes also is an ancestor then that most be the only ancestor. There is no need for additional bookkeeping.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     1
# ancestor.py - generic DAG ancestor algorithm for mercurial
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     2
#
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     3
# Copyright 2006 Matt Mackall <mpm@selenic.com>
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     4
#
8225
46293a0c7e9f updated license to be explicit about GPL version 2
Martin Geisler <mg@lazybytes.net>
parents: 7882
diff changeset
     5
# This software may be used and distributed according to the terms of the
10263
25e572394f5c Update license to GPLv2+
Matt Mackall <mpm@selenic.com>
parents: 8465
diff changeset
     6
# GNU General Public License version 2 or any later version.
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     7
20034
1e5b38a919dd cleanup: move stdlib imports to their own import statement
Augie Fackler <raf@durin42.com>
parents: 18987
diff changeset
     8
import heapq
1e5b38a919dd cleanup: move stdlib imports to their own import statement
Augie Fackler <raf@durin42.com>
parents: 18987
diff changeset
     9
import util
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
    10
from node import nullrev
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    11
18986
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    12
def ancestors(pfunc, *orignodes):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    13
    """
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    14
    Returns the common ancestors of a and b that are furthest from a
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    15
    root (as measured by longest path).
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    16
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    17
    pfunc must return a list of parent vertices for a given vertex.
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    18
    """
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    19
    if not isinstance(orignodes, set):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    20
        orignodes = set(orignodes)
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    21
    if nullrev in orignodes:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    22
        return set()
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    23
    if len(orignodes) <= 1:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    24
        return orignodes
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    25
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    26
    def candidates(nodes):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    27
        allseen = (1 << len(nodes)) - 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    28
        seen = [0] * (max(nodes) + 1)
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    29
        for i, n in enumerate(nodes):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    30
            seen[n] = 1 << i
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    31
        poison = 1 << (i + 1)
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    32
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    33
        gca = set()
20555
4add43865a9b ancestors: remove unnecessary handling of 'left'
Mads Kiilerich <madski@unity3d.com>
parents: 20034
diff changeset
    34
        interesting = len(nodes)
18986
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    35
        nv = len(seen) - 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    36
        while nv >= 0 and interesting:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    37
            v = nv
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    38
            nv -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    39
            if not seen[v]:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    40
                continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    41
            sv = seen[v]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    42
            if sv < poison:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    43
                interesting -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    44
                if sv == allseen:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    45
                    gca.add(v)
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    46
                    sv |= poison
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    47
                    if v in nodes:
20555
4add43865a9b ancestors: remove unnecessary handling of 'left'
Mads Kiilerich <madski@unity3d.com>
parents: 20034
diff changeset
    48
                        # history is linear
4add43865a9b ancestors: remove unnecessary handling of 'left'
Mads Kiilerich <madski@unity3d.com>
parents: 20034
diff changeset
    49
                        return set([v])
18986
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    50
            if sv < poison:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    51
                for p in pfunc(v):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    52
                    sp = seen[p]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    53
                    if p == nullrev:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    54
                        continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    55
                    if sp == 0:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    56
                        seen[p] = sv
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    57
                        interesting += 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    58
                    elif sp != sv:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    59
                        seen[p] |= sv
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    60
            else:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    61
                for p in pfunc(v):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    62
                    if p == nullrev:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    63
                        continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    64
                    sp = seen[p]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    65
                    if sp and sp < poison:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    66
                        interesting -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    67
                    seen[p] = sv
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    68
        return gca
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    69
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    70
    def deepest(nodes):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    71
        interesting = {}
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    72
        count = max(nodes) + 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    73
        depth = [0] * count
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    74
        seen = [0] * count
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    75
        mapping = []
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    76
        for (i, n) in enumerate(sorted(nodes)):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    77
            depth[n] = 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    78
            b = 1 << i
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    79
            seen[n] = b
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    80
            interesting[b] = 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    81
            mapping.append((b, n))
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    82
        nv = count - 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    83
        while nv >= 0 and len(interesting) > 1:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    84
            v = nv
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    85
            nv -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    86
            dv = depth[v]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    87
            if dv == 0:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    88
                continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    89
            sv = seen[v]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    90
            for p in pfunc(v):
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    91
                if p == nullrev:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    92
                    continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    93
                dp = depth[p]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    94
                nsp = sp = seen[p]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    95
                if dp <= dv:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    96
                    depth[p] = dv + 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    97
                    if sp != sv:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    98
                        interesting[sv] += 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    99
                        nsp = seen[p] = sv
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   100
                        if sp:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   101
                            interesting[sp] -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   102
                            if interesting[sp] == 0:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   103
                                del interesting[sp]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   104
                elif dv == dp - 1:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   105
                    nsp = sp | sv
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   106
                    if nsp == sp:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   107
                        continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   108
                    seen[p] = nsp
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   109
                    interesting.setdefault(nsp, 0)
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   110
                    interesting[nsp] += 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   111
                    interesting[sp] -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   112
                    if interesting[sp] == 0:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   113
                        del interesting[sp]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   114
            interesting[sv] -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   115
            if interesting[sv] == 0:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   116
                del interesting[sv]
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   117
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   118
        if len(interesting) != 1:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   119
            return []
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   120
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   121
        k = 0
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   122
        for i in interesting:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   123
            k |= i
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   124
        return set(n for (i, n) in mapping if k & i)
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   125
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   126
    gca = candidates(orignodes)
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   127
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   128
    if len(gca) <= 1:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   129
        return gca
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   130
    return deepest(gca)
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   131
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   132
def genericancestor(a, b, pfunc):
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   133
    """
13554
22565ddb28e7 ancestor: improve description
Matt Mackall <mpm@selenic.com>
parents: 12401
diff changeset
   134
    Returns the common ancestor of a and b that is furthest from a
22565ddb28e7 ancestor: improve description
Matt Mackall <mpm@selenic.com>
parents: 12401
diff changeset
   135
    root (as measured by longest path) or None if no ancestor is
22565ddb28e7 ancestor: improve description
Matt Mackall <mpm@selenic.com>
parents: 12401
diff changeset
   136
    found. If there are multiple common ancestors at the same
22565ddb28e7 ancestor: improve description
Matt Mackall <mpm@selenic.com>
parents: 12401
diff changeset
   137
    distance, the first one found is returned.
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   138
9915
806e6b6cb8d8 ancestor: improve docstring
Sune Foldager <cryo@cyanite.org>
parents: 8465
diff changeset
   139
    pfunc must return a list of parent vertices for a given vertex
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   140
    """
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   141
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   142
    if a == b:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   143
        return a
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   144
11418
67bb9d78f05e merge: sort arguments to stabilize the ancestor search
Matt Mackall <mpm@selenic.com>
parents: 10264
diff changeset
   145
    a, b = sorted([a, b])
67bb9d78f05e merge: sort arguments to stabilize the ancestor search
Matt Mackall <mpm@selenic.com>
parents: 10264
diff changeset
   146
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   147
    # find depth from root of all ancestors
13554
22565ddb28e7 ancestor: improve description
Matt Mackall <mpm@selenic.com>
parents: 12401
diff changeset
   148
    # depth is stored as a negative for heapq
7882
8d78fc991b71 ancestor: caching the parent list to improve performance
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 6429
diff changeset
   149
    parentcache = {}
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   150
    visit = [a, b]
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   151
    depth = {}
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   152
    while visit:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   153
        vertex = visit[-1]
18986
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   154
        pl = [p for p in pfunc(vertex) if p != nullrev]
7882
8d78fc991b71 ancestor: caching the parent list to improve performance
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 6429
diff changeset
   155
        parentcache[vertex] = pl
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   156
        if not pl:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   157
            depth[vertex] = 0
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   158
            visit.pop()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   159
        else:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   160
            for p in pl:
12401
4cdaf1adafc8 backout most of 4f8067c94729
Matt Mackall <mpm@selenic.com>
parents: 12387
diff changeset
   161
                if p == a or p == b: # did we find a or b as a parent?
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   162
                    return p # we're done
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   163
                if p not in depth:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   164
                    visit.append(p)
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   165
            if visit[-1] == vertex:
13554
22565ddb28e7 ancestor: improve description
Matt Mackall <mpm@selenic.com>
parents: 12401
diff changeset
   166
                # -(maximum distance of parents + 1)
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   167
                depth[vertex] = min([depth[p] for p in pl]) - 1
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   168
                visit.pop()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   169
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   170
    # traverse ancestors in order of decreasing distance from root
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   171
    def ancestors(vertex):
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   172
        h = [(depth[vertex], vertex)]
8465
23429ebd3f9d ancestor: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8225
diff changeset
   173
        seen = set()
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   174
        while h:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   175
            d, n = heapq.heappop(h)
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   176
            if n not in seen:
8465
23429ebd3f9d ancestor: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8225
diff changeset
   177
                seen.add(n)
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   178
                yield (d, n)
7882
8d78fc991b71 ancestor: caching the parent list to improve performance
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 6429
diff changeset
   179
                for p in parentcache[n]:
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   180
                    heapq.heappush(h, (depth[p], p))
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   181
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   182
    def generations(vertex):
8465
23429ebd3f9d ancestor: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8225
diff changeset
   183
        sg, s = None, set()
3673
eb0b4a2d70a9 white space and line break cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents: 3135
diff changeset
   184
        for g, v in ancestors(vertex):
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   185
            if g != sg:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   186
                if sg:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   187
                    yield sg, s
8465
23429ebd3f9d ancestor: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8225
diff changeset
   188
                sg, s = g, set((v,))
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   189
            else:
8465
23429ebd3f9d ancestor: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8225
diff changeset
   190
                s.add(v)
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   191
        yield sg, s
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   192
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   193
    x = generations(a)
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   194
    y = generations(b)
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   195
    gx = x.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   196
    gy = y.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   197
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   198
    # increment each ancestor list until it is closer to root than
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   199
    # the other, or they match
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   200
    try:
14494
1ffeeb91c55d check-code: flag 0/1 used as constant Boolean expression
Martin Geisler <mg@lazybytes.net>
parents: 13554
diff changeset
   201
        while True:
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   202
            if gx[0] == gy[0]:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   203
                for v in gx[1]:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   204
                    if v in gy[1]:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   205
                        return v
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   206
                gy = y.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   207
                gx = x.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   208
            elif gx[0] > gy[0]:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   209
                gy = y.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   210
            else:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   211
                gx = x.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   212
    except StopIteration:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   213
        return None
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   214
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   215
def missingancestors(revs, bases, pfunc):
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   216
    """Return all the ancestors of revs that are not ancestors of bases.
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   217
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   218
    This may include elements from revs.
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   219
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   220
    Equivalent to the revset (::revs - ::bases). Revs are returned in
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   221
    revision number order, which is a topological order.
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   222
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   223
    revs and bases should both be iterables. pfunc must return a list of
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   224
    parent revs for a given revs.
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   225
    """
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   226
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   227
    revsvisit = set(revs)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   228
    basesvisit = set(bases)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   229
    if not revsvisit:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   230
        return []
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   231
    if not basesvisit:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   232
        basesvisit.add(nullrev)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   233
    start = max(max(revsvisit), max(basesvisit))
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   234
    bothvisit = revsvisit.intersection(basesvisit)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   235
    revsvisit.difference_update(bothvisit)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   236
    basesvisit.difference_update(bothvisit)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   237
    # At this point, we hold the invariants that:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   238
    # - revsvisit is the set of nodes we know are an ancestor of at least one
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   239
    #   of the nodes in revs
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   240
    # - basesvisit is the same for bases
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   241
    # - bothvisit is the set of nodes we know are ancestors of at least one of
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   242
    #   the nodes in revs and one of the nodes in bases
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   243
    # - a node may be in none or one, but not more, of revsvisit, basesvisit
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   244
    #   and bothvisit at any given time
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   245
    # Now we walk down in reverse topo order, adding parents of nodes already
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   246
    # visited to the sets while maintaining the invariants. When a node is
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   247
    # found in both revsvisit and basesvisit, it is removed from them and
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   248
    # added to bothvisit instead. When revsvisit becomes empty, there are no
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   249
    # more ancestors of revs that aren't also ancestors of bases, so exit.
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   250
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   251
    missing = []
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   252
    for curr in xrange(start, nullrev, -1):
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   253
        if not revsvisit:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   254
            break
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   255
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   256
        if curr in bothvisit:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   257
            bothvisit.remove(curr)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   258
            # curr's parents might have made it into revsvisit or basesvisit
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   259
            # through another path
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   260
            for p in pfunc(curr):
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   261
                revsvisit.discard(p)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   262
                basesvisit.discard(p)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   263
                bothvisit.add(p)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   264
            continue
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   265
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   266
        # curr will never be in both revsvisit and basesvisit, since if it
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   267
        # were it'd have been pushed to bothvisit
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   268
        if curr in revsvisit:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   269
            missing.append(curr)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   270
            thisvisit = revsvisit
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   271
            othervisit = basesvisit
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   272
        elif curr in basesvisit:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   273
            thisvisit = basesvisit
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   274
            othervisit = revsvisit
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   275
        else:
17976
09d5681d5b72 ancestor: fix a comment (followup to 0b03454abae7)
Siddharth Agarwal <sid0@fb.com>
parents: 17970
diff changeset
   276
            # not an ancestor of revs or bases: ignore
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   277
            continue
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   278
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   279
        thisvisit.remove(curr)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   280
        for p in pfunc(curr):
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   281
            if p == nullrev:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   282
                pass
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   283
            elif p in othervisit or p in bothvisit:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   284
                # p is implicitly in thisvisit. This means p is or should be
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   285
                # in bothvisit
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   286
                revsvisit.discard(p)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   287
                basesvisit.discard(p)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   288
                bothvisit.add(p)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   289
            else:
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   290
                # visit later
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   291
                thisvisit.add(p)
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   292
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   293
    missing.reverse()
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   294
    return missing
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   295
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   296
class lazyancestors(object):
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   297
    def __init__(self, cl, revs, stoprev=0, inclusive=False):
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   298
        """Create a new object generating ancestors for the given revs. Does
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   299
        not generate revs lower than stoprev.
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   300
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   301
        This is computed lazily starting from revs. The object supports
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   302
        iteration and membership.
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   303
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   304
        cl should be a changelog and revs should be an iterable. inclusive is
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   305
        a boolean that indicates whether revs should be included. Revs lower
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   306
        than stoprev will not be generated.
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   307
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   308
        Result does not include the null revision."""
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   309
        self._parentrevs = cl.parentrevs
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   310
        self._initrevs = revs
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   311
        self._stoprev = stoprev
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   312
        self._inclusive = inclusive
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   313
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   314
        # Initialize data structures for __contains__.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   315
        # For __contains__, we use a heap rather than a deque because
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   316
        # (a) it minimizes the number of parentrevs calls made
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   317
        # (b) it makes the loop termination condition obvious
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   318
        # Python's heap is a min-heap. Multiply all values by -1 to convert it
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   319
        # into a max-heap.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   320
        self._containsvisit = [-rev for rev in revs]
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   321
        heapq.heapify(self._containsvisit)
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   322
        if inclusive:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   323
            self._containsseen = set(revs)
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   324
        else:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   325
            self._containsseen = set()
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   326
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   327
    def __iter__(self):
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   328
        """Generate the ancestors of _initrevs in reverse topological order.
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   329
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   330
        If inclusive is False, yield a sequence of revision numbers starting
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   331
        with the parents of each revision in revs, i.e., each revision is *not*
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   332
        considered an ancestor of itself.  Results are in breadth-first order:
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   333
        parents of each rev in revs, then parents of those, etc.
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   334
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   335
        If inclusive is True, yield all the revs first (ignoring stoprev),
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   336
        then yield all the ancestors of revs as when inclusive is False.
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   337
        If an element in revs is an ancestor of a different rev it is not
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   338
        yielded again."""
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   339
        seen = set()
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   340
        revs = self._initrevs
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   341
        if self._inclusive:
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   342
            for rev in revs:
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   343
                yield rev
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   344
            seen.update(revs)
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   345
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   346
        parentrevs = self._parentrevs
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   347
        stoprev = self._stoprev
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   348
        visit = util.deque(revs)
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   349
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   350
        while visit:
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   351
            for parent in parentrevs(visit.popleft()):
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   352
                if parent >= stoprev and parent not in seen:
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   353
                    visit.append(parent)
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   354
                    seen.add(parent)
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   355
                    yield parent
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   356
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   357
    def __contains__(self, target):
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   358
        """Test whether target is an ancestor of self._initrevs."""
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   359
        # Trying to do both __iter__ and __contains__ using the same visit
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   360
        # heap and seen set is complex enough that it slows down both. Keep
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   361
        # them separate.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   362
        seen = self._containsseen
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   363
        if target in seen:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   364
            return True
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   365
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   366
        parentrevs = self._parentrevs
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   367
        visit = self._containsvisit
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   368
        stoprev = self._stoprev
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   369
        heappop = heapq.heappop
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   370
        heappush = heapq.heappush
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   371
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   372
        targetseen = False
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   373
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   374
        while visit and -visit[0] > target and not targetseen:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   375
            for parent in parentrevs(-heappop(visit)):
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   376
                if parent < stoprev or parent in seen:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   377
                    continue
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   378
                # We need to make sure we push all parents into the heap so
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   379
                # that we leave it in a consistent state for future calls.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   380
                heappush(visit, -parent)
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   381
                seen.add(parent)
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   382
                if parent == target:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   383
                    targetseen = True
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   384
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   385
        return targetseen