mercurial/ancestor.py
author Pierre-Yves David <pierre-yves.david@ens-lyon.org>
Thu, 05 May 2016 19:32:51 +0200
changeset 29150 0e9ed09f5fe9
parent 25915 7ef98b38163f
child 29216 ead25aa27a43
permissions -rw-r--r--
cleanup: replace False identity testing with an explicit token object The recommended way to check default value (when None is not as option) is a token object. Identity testing to integer is less explicit and not guaranteed to work in all implementations.
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
25915
7ef98b38163f ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25639
diff changeset
     8
from __future__ import absolute_import
7ef98b38163f ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25639
diff changeset
     9
25113
0ca8410ea345 util: drop alias for collections.deque
Martin von Zweigbergk <martinvonz@google.com>
parents: 23342
diff changeset
    10
import collections
20034
1e5b38a919dd cleanup: move stdlib imports to their own import statement
Augie Fackler <raf@durin42.com>
parents: 18987
diff changeset
    11
import heapq
25915
7ef98b38163f ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25639
diff changeset
    12
7ef98b38163f ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25639
diff changeset
    13
from .node import nullrev
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    14
21101
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    15
def commonancestorsheads(pfunc, *nodes):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    16
    """Returns a set with the heads of all common ancestors of all nodes,
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    17
    heads(::nodes[0] and ::nodes[1] and ...) .
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    18
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    19
    pfunc must return a list of parent vertices for a given vertex.
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    20
    """
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    21
    if not isinstance(nodes, set):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    22
        nodes = set(nodes)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    23
    if nullrev in nodes:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    24
        return set()
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    25
    if len(nodes) <= 1:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    26
        return nodes
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    27
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    28
    allseen = (1 << len(nodes)) - 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    29
    seen = [0] * (max(nodes) + 1)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    30
    for i, n in enumerate(nodes):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    31
        seen[n] = 1 << i
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    32
    poison = 1 << (i + 1)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    33
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    34
    gca = set()
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    35
    interesting = len(nodes)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    36
    nv = len(seen) - 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    37
    while nv >= 0 and interesting:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    38
        v = nv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    39
        nv -= 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    40
        if not seen[v]:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    41
            continue
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    42
        sv = seen[v]
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    43
        if sv < poison:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    44
            interesting -= 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    45
            if sv == allseen:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    46
                gca.add(v)
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    47
                sv |= poison
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    48
                if v in nodes:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    49
                    # history is linear
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    50
                    return set([v])
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    51
        if sv < poison:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    52
            for p in pfunc(v):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    53
                sp = seen[p]
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    54
                if p == nullrev:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    55
                    continue
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    56
                if sp == 0:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    57
                    seen[p] = sv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    58
                    interesting += 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    59
                elif sp != sv:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    60
                    seen[p] |= sv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    61
        else:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    62
            for p in pfunc(v):
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    63
                if p == nullrev:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    64
                    continue
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    65
                sp = seen[p]
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    66
                if sp and sp < poison:
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    67
                    interesting -= 1
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    68
                seen[p] = sv
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    69
    return gca
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
    70
18986
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    71
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
    72
    """
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    73
    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
    74
    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
    75
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    76
    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
    77
    """
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    78
    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
    79
        interesting = {}
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    80
        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
    81
        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
    82
        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
    83
        mapping = []
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    84
        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
    85
            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
    86
            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
    87
            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
    88
            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
    89
            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
    90
        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
    91
        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
    92
            v = nv
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    93
            nv -= 1
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    94
            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
    95
            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
    96
                continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
    97
            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
    98
            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
    99
                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
   100
                    continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   101
                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
   102
                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
   103
                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
   104
                    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
   105
                    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
   106
                        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
   107
                        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
   108
                        if sp:
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   109
                            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
   110
                            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
   111
                                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
   112
                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
   113
                    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
   114
                    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
   115
                        continue
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   116
                    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
   117
                    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
   118
                    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
   119
                    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
   120
                    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
   121
                        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
   122
            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
   123
            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
   124
                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
   125
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   126
        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
   127
            return []
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   128
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   129
        k = 0
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   130
        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
   131
            k |= i
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   132
        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
   133
21101
64911a12dc28 ancestors: extract candidates function as commonancestorsheads
Mads Kiilerich <madski@unity3d.com>
parents: 20985
diff changeset
   134
    gca = commonancestorsheads(pfunc, *orignodes)
18986
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   135
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   136
    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
   137
        return gca
2f7186400a07 ancestor: a new algorithm that is faster for nodes near tip
Bryan O'Sullivan <bryano@fb.com>
parents: 18091
diff changeset
   138
    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
   139
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   140
class incrementalmissingancestors(object):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   141
    '''persistent state used to calculate missing ancestors incrementally
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   142
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   143
    Although similar in spirit to lazyancestors below, this is a separate class
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   144
    because trying to support contains and missingancestors operations with the
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   145
    same internal data structures adds needless complexity.'''
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   146
    def __init__(self, pfunc, bases):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   147
        self.bases = set(bases)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   148
        if not self.bases:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   149
            self.bases.add(nullrev)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   150
        self.pfunc = pfunc
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   151
23340
83225aff0265 ancestor: add a way to test whether a missing ancestor object has bases
Siddharth Agarwal <sid0@fb.com>
parents: 23339
diff changeset
   152
    def hasbases(self):
83225aff0265 ancestor: add a way to test whether a missing ancestor object has bases
Siddharth Agarwal <sid0@fb.com>
parents: 23339
diff changeset
   153
        '''whether the common set has any non-trivial bases'''
83225aff0265 ancestor: add a way to test whether a missing ancestor object has bases
Siddharth Agarwal <sid0@fb.com>
parents: 23339
diff changeset
   154
        return self.bases and self.bases != set([nullrev])
83225aff0265 ancestor: add a way to test whether a missing ancestor object has bases
Siddharth Agarwal <sid0@fb.com>
parents: 23339
diff changeset
   155
23341
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents: 23340
diff changeset
   156
    def addbases(self, newbases):
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents: 23340
diff changeset
   157
        '''grow the ancestor set by adding new bases'''
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents: 23340
diff changeset
   158
        self.bases.update(newbases)
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents: 23340
diff changeset
   159
23342
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   160
    def removeancestorsfrom(self, revs):
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   161
        '''remove all ancestors of bases from the set revs (in place)'''
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   162
        bases = self.bases
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   163
        pfunc = self.pfunc
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   164
        revs.difference_update(bases)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   165
        # nullrev is always an ancestor
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   166
        revs.discard(nullrev)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   167
        if not revs:
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   168
            return
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   169
        # anything in revs > start is definitely not an ancestor of bases
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   170
        # revs <= start needs to be investigated
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   171
        start = max(bases)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   172
        keepcount = sum(1 for r in revs if r > start)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   173
        if len(revs) == keepcount:
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   174
            # no revs to consider
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   175
            return
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   176
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   177
        for curr in xrange(start, min(revs) - 1, -1):
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   178
            if curr not in bases:
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   179
                continue
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   180
            revs.discard(curr)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   181
            bases.update(pfunc(curr))
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   182
            if len(revs) == keepcount:
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   183
                # no more potential revs to discard
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   184
                break
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
   185
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   186
    def missingancestors(self, revs):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   187
        '''return all the ancestors of revs that are not ancestors of self.bases
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   188
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   189
        This may include elements from revs.
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   190
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   191
        Equivalent to the revset (::revs - ::self.bases). Revs are returned in
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   192
        revision number order, which is a topological order.'''
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   193
        revsvisit = set(revs)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   194
        basesvisit = self.bases
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   195
        pfunc = self.pfunc
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   196
        bothvisit = revsvisit.intersection(basesvisit)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   197
        revsvisit.difference_update(bothvisit)
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   198
        if not revsvisit:
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   199
            return []
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   200
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   201
        start = max(max(revsvisit), max(basesvisit))
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   202
        # At this point, we hold the invariants that:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   203
        # - revsvisit is the set of nodes we know are an ancestor of at least
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   204
        #   one of the nodes in revs
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   205
        # - basesvisit is the same for bases
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   206
        # - bothvisit is the set of nodes we know are ancestors of at least one
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   207
        #   of the nodes in revs and one of the nodes in bases. bothvisit and
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   208
        #   revsvisit are mutually exclusive, but bothvisit is a subset of
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   209
        #   basesvisit.
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   210
        # Now we walk down in reverse topo order, adding parents of nodes
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   211
        # already visited to the sets while maintaining the invariants. When a
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   212
        # node is found in both revsvisit and basesvisit, it is removed from
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   213
        # revsvisit and added to bothvisit. When revsvisit becomes empty, there
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   214
        # are no more ancestors of revs that aren't also ancestors of bases, so
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   215
        # exit.
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   216
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   217
        missing = []
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   218
        for curr in xrange(start, nullrev, -1):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   219
            if not revsvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   220
                break
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   221
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   222
            if curr in bothvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   223
                bothvisit.remove(curr)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   224
                # curr's parents might have made it into revsvisit through
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   225
                # another path
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   226
                for p in pfunc(curr):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   227
                    revsvisit.discard(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   228
                    basesvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   229
                    bothvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   230
                continue
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   231
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   232
            if curr in revsvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   233
                missing.append(curr)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   234
                revsvisit.remove(curr)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   235
                thisvisit = revsvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   236
                othervisit = basesvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   237
            elif curr in basesvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   238
                thisvisit = basesvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   239
                othervisit = revsvisit
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   240
            else:
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   241
                # not an ancestor of revs or bases: ignore
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   242
                continue
17970
0b03454abae7 ancestor: faster algorithm for difference of ancestor sets
Siddharth Agarwal <sid0@fb.com>
parents: 14494
diff changeset
   243
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   244
            for p in pfunc(curr):
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   245
                if p == nullrev:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   246
                    pass
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   247
                elif p in othervisit or p in bothvisit:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   248
                    # p is implicitly in thisvisit. This means p is or should be
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   249
                    # in bothvisit
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   250
                    revsvisit.discard(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   251
                    basesvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   252
                    bothvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   253
                else:
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   254
                    # visit later
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   255
                    thisvisit.add(p)
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   256
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   257
        missing.reverse()
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   258
        return missing
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23333
diff changeset
   259
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   260
class lazyancestors(object):
23328
3a7d9c0c57a5 ancestor.lazyancestors: take parentrevs function rather than changelog
Siddharth Agarwal <sid0@fb.com>
parents: 22225
diff changeset
   261
    def __init__(self, pfunc, revs, stoprev=0, inclusive=False):
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   262
        """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
   263
        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
   264
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   265
        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
   266
        iteration and membership.
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   267
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   268
        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
   269
        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
   270
        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
   271
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   272
        Result does not include the null revision."""
23328
3a7d9c0c57a5 ancestor.lazyancestors: take parentrevs function rather than changelog
Siddharth Agarwal <sid0@fb.com>
parents: 22225
diff changeset
   273
        self._parentrevs = pfunc
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   274
        self._initrevs = revs
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   275
        self._stoprev = stoprev
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   276
        self._inclusive = inclusive
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   277
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   278
        # Initialize data structures for __contains__.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   279
        # 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
   280
        # (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
   281
        # (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
   282
        # 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
   283
        # into a max-heap.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   284
        self._containsvisit = [-rev for rev in revs]
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   285
        heapq.heapify(self._containsvisit)
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   286
        if inclusive:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   287
            self._containsseen = set(revs)
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   288
        else:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   289
            self._containsseen = set()
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   290
22225
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
   291
    def __nonzero__(self):
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
   292
        """False if the set is empty, True otherwise."""
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
   293
        try:
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
   294
            iter(self).next()
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
   295
            return True
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
   296
        except StopIteration:
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
   297
            return False
baecf4e1b7d0 ancestors: add a __nonzero__ method
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21101
diff changeset
   298
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   299
    def __iter__(self):
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   300
        """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
   301
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   302
        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
   303
        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
   304
        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
   305
        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
   306
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   307
        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
   308
        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
   309
        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
   310
        yielded again."""
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   311
        seen = set()
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   312
        revs = self._initrevs
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   313
        if self._inclusive:
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   314
            for rev in revs:
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   315
                yield rev
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   316
            seen.update(revs)
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   317
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   318
        parentrevs = self._parentrevs
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   319
        stoprev = self._stoprev
25113
0ca8410ea345 util: drop alias for collections.deque
Martin von Zweigbergk <martinvonz@google.com>
parents: 23342
diff changeset
   320
        visit = collections.deque(revs)
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   321
25639
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
   322
        see = seen.add
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
   323
        schedule = visit.append
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
   324
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   325
        while visit:
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   326
            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
   327
                if parent >= stoprev and parent not in seen:
25639
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
   328
                    schedule(parent)
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
   329
                    see(parent)
18090
9abc55ef85b5 revlog: move ancestor generation out to a new class
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
   330
                    yield parent
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   331
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   332
    def __contains__(self, target):
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   333
        """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
   334
        # 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
   335
        # 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
   336
        # them separate.
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   337
        seen = self._containsseen
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   338
        if target in seen:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   339
            return True
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   340
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   341
        parentrevs = self._parentrevs
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   342
        visit = self._containsvisit
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   343
        stoprev = self._stoprev
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   344
        heappop = heapq.heappop
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   345
        heappush = heapq.heappush
25639
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
   346
        see = seen.add
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   347
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   348
        targetseen = False
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   349
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   350
        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
   351
            for parent in parentrevs(-heappop(visit)):
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   352
                if parent < stoprev or parent in seen:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   353
                    continue
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   354
                # 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
   355
                # 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
   356
                heappush(visit, -parent)
25639
7125225a5287 ancestors: prefetch method outside of the loop
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25113
diff changeset
   357
                see(parent)
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   358
                if parent == target:
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   359
                    targetseen = True
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   360
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18090
diff changeset
   361
        return targetseen