author | Anton Shestakov <av6@dwimlabs.net> |
Thu, 03 Sep 2015 22:25:16 +0800 | |
branch | stable |
changeset 26151 | 0dda3692ec9b |
parent 24306 | 6ddc86eedc3b |
child 25942 | 015ded095933 |
permissions | -rw-r--r-- |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
1 |
# dagutil.py - dag utilities for mercurial |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
2 |
# |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
3 |
# Copyright 2010 Benoit Boissinot <bboissin@gmail.com> |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
4 |
# and Peter Arrenbrecht <peter@arrenbrecht.ch> |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
5 |
# |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
6 |
# This software may be used and distributed according to the terms of the |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
7 |
# GNU General Public License version 2 or any later version. |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
8 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
9 |
from node import nullrev |
14634
1679d73c9464
dagutil: fix missing import of i18n._
Wagner Bruna <wbruna@softwareexpress.com.br>
parents:
14364
diff
changeset
|
10 |
from i18n import _ |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
11 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
12 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
13 |
class basedag(object): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
14 |
'''generic interface for DAGs |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
15 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
16 |
terms: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
17 |
"ix" (short for index) identifies a nodes internally, |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
18 |
"id" identifies one externally. |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
19 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
20 |
All params are ixs unless explicitly suffixed otherwise. |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
21 |
Pluralized params are lists or sets. |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
22 |
''' |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
23 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
24 |
def __init__(self): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
25 |
self._inverse = None |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
26 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
27 |
def nodeset(self): |
23216
4e5ac4a3a29b
dagutil: fix id/ix typos in docstrings
Mike Edgar <adgar@google.com>
parents:
22387
diff
changeset
|
28 |
'''set of all node ixs''' |
16687
e34106fa0dc3
cleanup: "raise SomeException()" -> "raise SomeException"
Brodie Rao <brodie@sf.io>
parents:
15052
diff
changeset
|
29 |
raise NotImplementedError |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
30 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
31 |
def heads(self): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
32 |
'''list of head ixs''' |
16687
e34106fa0dc3
cleanup: "raise SomeException()" -> "raise SomeException"
Brodie Rao <brodie@sf.io>
parents:
15052
diff
changeset
|
33 |
raise NotImplementedError |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
34 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
35 |
def parents(self, ix): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
36 |
'''list of parents ixs of ix''' |
16687
e34106fa0dc3
cleanup: "raise SomeException()" -> "raise SomeException"
Brodie Rao <brodie@sf.io>
parents:
15052
diff
changeset
|
37 |
raise NotImplementedError |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
38 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
39 |
def inverse(self): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
40 |
'''inverse DAG, where parents becomes children, etc.''' |
16687
e34106fa0dc3
cleanup: "raise SomeException()" -> "raise SomeException"
Brodie Rao <brodie@sf.io>
parents:
15052
diff
changeset
|
41 |
raise NotImplementedError |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
42 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
43 |
def ancestorset(self, starts, stops=None): |
14206
2bf60f158ecb
setdiscovery: limit lines to 80 characters
Steven Brown <StevenGBrown@gmail.com>
parents:
14164
diff
changeset
|
44 |
''' |
2bf60f158ecb
setdiscovery: limit lines to 80 characters
Steven Brown <StevenGBrown@gmail.com>
parents:
14164
diff
changeset
|
45 |
set of all ancestors of starts (incl), but stop walk at stops (excl) |
2bf60f158ecb
setdiscovery: limit lines to 80 characters
Steven Brown <StevenGBrown@gmail.com>
parents:
14164
diff
changeset
|
46 |
''' |
16687
e34106fa0dc3
cleanup: "raise SomeException()" -> "raise SomeException"
Brodie Rao <brodie@sf.io>
parents:
15052
diff
changeset
|
47 |
raise NotImplementedError |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
48 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
49 |
def descendantset(self, starts, stops=None): |
14206
2bf60f158ecb
setdiscovery: limit lines to 80 characters
Steven Brown <StevenGBrown@gmail.com>
parents:
14164
diff
changeset
|
50 |
''' |
2bf60f158ecb
setdiscovery: limit lines to 80 characters
Steven Brown <StevenGBrown@gmail.com>
parents:
14164
diff
changeset
|
51 |
set of all descendants of starts (incl), but stop walk at stops (excl) |
2bf60f158ecb
setdiscovery: limit lines to 80 characters
Steven Brown <StevenGBrown@gmail.com>
parents:
14164
diff
changeset
|
52 |
''' |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
53 |
return self.inverse().ancestorset(starts, stops) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
54 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
55 |
def headsetofconnecteds(self, ixs): |
14206
2bf60f158ecb
setdiscovery: limit lines to 80 characters
Steven Brown <StevenGBrown@gmail.com>
parents:
14164
diff
changeset
|
56 |
''' |
2bf60f158ecb
setdiscovery: limit lines to 80 characters
Steven Brown <StevenGBrown@gmail.com>
parents:
14164
diff
changeset
|
57 |
subset of connected list of ixs so that no node has a descendant in it |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
58 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
59 |
By "connected list" we mean that if an ancestor and a descendant are in |
14206
2bf60f158ecb
setdiscovery: limit lines to 80 characters
Steven Brown <StevenGBrown@gmail.com>
parents:
14164
diff
changeset
|
60 |
the list, then so is at least one path connecting them. |
2bf60f158ecb
setdiscovery: limit lines to 80 characters
Steven Brown <StevenGBrown@gmail.com>
parents:
14164
diff
changeset
|
61 |
''' |
16687
e34106fa0dc3
cleanup: "raise SomeException()" -> "raise SomeException"
Brodie Rao <brodie@sf.io>
parents:
15052
diff
changeset
|
62 |
raise NotImplementedError |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
63 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
64 |
def externalize(self, ix): |
22387
ce8cea923a6c
dagutils: fix docstrings for singleton internalize/externalize
Mads Kiilerich <madski@unity3d.com>
parents:
20224
diff
changeset
|
65 |
'''return a node id''' |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
66 |
return self._externalize(ix) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
67 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
68 |
def externalizeall(self, ixs): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
69 |
'''return a list of (or set if given a set) of node ids''' |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
70 |
ids = self._externalizeall(ixs) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
71 |
if isinstance(ixs, set): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
72 |
return set(ids) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
73 |
return list(ids) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
74 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
75 |
def internalize(self, id): |
22387
ce8cea923a6c
dagutils: fix docstrings for singleton internalize/externalize
Mads Kiilerich <madski@unity3d.com>
parents:
20224
diff
changeset
|
76 |
'''return a node ix''' |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
77 |
return self._internalize(id) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
78 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
79 |
def internalizeall(self, ids, filterunknown=False): |
23216
4e5ac4a3a29b
dagutil: fix id/ix typos in docstrings
Mike Edgar <adgar@google.com>
parents:
22387
diff
changeset
|
80 |
'''return a list of (or set if given a set) of node ixs''' |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
81 |
ixs = self._internalizeall(ids, filterunknown) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
82 |
if isinstance(ids, set): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
83 |
return set(ixs) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
84 |
return list(ixs) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
85 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
86 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
87 |
class genericdag(basedag): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
88 |
'''generic implementations for DAGs''' |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
89 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
90 |
def ancestorset(self, starts, stops=None): |
24306
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
23216
diff
changeset
|
91 |
if stops: |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
23216
diff
changeset
|
92 |
stops = set(stops) |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
23216
diff
changeset
|
93 |
else: |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
23216
diff
changeset
|
94 |
stops = set() |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
95 |
seen = set() |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
96 |
pending = list(starts) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
97 |
while pending: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
98 |
n = pending.pop() |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
99 |
if n not in seen and n not in stops: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
100 |
seen.add(n) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
101 |
pending.extend(self.parents(n)) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
102 |
return seen |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
103 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
104 |
def headsetofconnecteds(self, ixs): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
105 |
hds = set(ixs) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
106 |
if not hds: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
107 |
return hds |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
108 |
for n in ixs: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
109 |
for p in self.parents(n): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
110 |
hds.discard(p) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
111 |
assert hds |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
112 |
return hds |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
113 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
114 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
115 |
class revlogbaseddag(basedag): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
116 |
'''generic dag interface to a revlog''' |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
117 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
118 |
def __init__(self, revlog, nodeset): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
119 |
basedag.__init__(self) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
120 |
self._revlog = revlog |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
121 |
self._heads = None |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
122 |
self._nodeset = nodeset |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
123 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
124 |
def nodeset(self): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
125 |
return self._nodeset |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
126 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
127 |
def heads(self): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
128 |
if self._heads is None: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
129 |
self._heads = self._getheads() |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
130 |
return self._heads |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
131 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
132 |
def _externalize(self, ix): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
133 |
return self._revlog.index[ix][7] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
134 |
def _externalizeall(self, ixs): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
135 |
idx = self._revlog.index |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
136 |
return [idx[i][7] for i in ixs] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
137 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
138 |
def _internalize(self, id): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
139 |
ix = self._revlog.rev(id) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
140 |
if ix == nullrev: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
141 |
raise LookupError(id, self._revlog.indexfile, _('nullid')) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
142 |
return ix |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
143 |
def _internalizeall(self, ids, filterunknown): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
144 |
rl = self._revlog |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
145 |
if filterunknown: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
146 |
return [r for r in map(rl.nodemap.get, ids) |
20224
34d4a037dced
discovery: enforce filtering into revlogbaseddag._internalizeall
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
20223
diff
changeset
|
147 |
if (r is not None |
34d4a037dced
discovery: enforce filtering into revlogbaseddag._internalizeall
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
20223
diff
changeset
|
148 |
and r != nullrev |
34d4a037dced
discovery: enforce filtering into revlogbaseddag._internalizeall
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
20223
diff
changeset
|
149 |
and r not in rl.filteredrevs)] |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
150 |
return map(self._internalize, ids) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
151 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
152 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
153 |
class revlogdag(revlogbaseddag): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
154 |
'''dag interface to a revlog''' |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
155 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
156 |
def __init__(self, revlog): |
20223
37e2bd560805
discovery: make revlogdag work on filtered repo
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
16687
diff
changeset
|
157 |
revlogbaseddag.__init__(self, revlog, set(revlog)) |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
158 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
159 |
def _getheads(self): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
160 |
return [r for r in self._revlog.headrevs() if r != nullrev] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
161 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
162 |
def parents(self, ix): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
163 |
rlog = self._revlog |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
164 |
idx = rlog.index |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
165 |
revdata = idx[ix] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
166 |
prev = revdata[5] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
167 |
if prev != nullrev: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
168 |
prev2 = revdata[6] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
169 |
if prev2 == nullrev: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
170 |
return [prev] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
171 |
return [prev, prev2] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
172 |
prev2 = revdata[6] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
173 |
if prev2 != nullrev: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
174 |
return [prev2] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
175 |
return [] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
176 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
177 |
def inverse(self): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
178 |
if self._inverse is None: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
179 |
self._inverse = inverserevlogdag(self) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
180 |
return self._inverse |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
181 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
182 |
def ancestorset(self, starts, stops=None): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
183 |
rlog = self._revlog |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
184 |
idx = rlog.index |
24306
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
23216
diff
changeset
|
185 |
if stops: |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
23216
diff
changeset
|
186 |
stops = set(stops) |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
23216
diff
changeset
|
187 |
else: |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
23216
diff
changeset
|
188 |
stops = set() |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
189 |
seen = set() |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
190 |
pending = list(starts) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
191 |
while pending: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
192 |
rev = pending.pop() |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
193 |
if rev not in seen and rev not in stops: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
194 |
seen.add(rev) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
195 |
revdata = idx[rev] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
196 |
for i in [5, 6]: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
197 |
prev = revdata[i] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
198 |
if prev != nullrev: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
199 |
pending.append(prev) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
200 |
return seen |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
201 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
202 |
def headsetofconnecteds(self, ixs): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
203 |
if not ixs: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
204 |
return set() |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
205 |
rlog = self._revlog |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
206 |
idx = rlog.index |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
207 |
headrevs = set(ixs) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
208 |
for rev in ixs: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
209 |
revdata = idx[rev] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
210 |
for i in [5, 6]: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
211 |
prev = revdata[i] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
212 |
if prev != nullrev: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
213 |
headrevs.discard(prev) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
214 |
assert headrevs |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
215 |
return headrevs |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
216 |
|
14364
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
217 |
def linearize(self, ixs): |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
218 |
'''linearize and topologically sort a list of revisions |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
219 |
|
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
220 |
The linearization process tries to create long runs of revs where |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
221 |
a child rev comes immediately after its first parent. This is done by |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
222 |
visiting the heads of the given revs in inverse topological order, |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
223 |
and for each visited rev, visiting its second parent, then its first |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
224 |
parent, then adding the rev itself to the output list. |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
225 |
''' |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
226 |
sorted = [] |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
227 |
visit = list(self.headsetofconnecteds(ixs)) |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
228 |
visit.sort(reverse=True) |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
229 |
finished = set() |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
230 |
|
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
231 |
while visit: |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
232 |
cur = visit.pop() |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
233 |
if cur < 0: |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
234 |
cur = -cur - 1 |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
235 |
if cur not in finished: |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
236 |
sorted.append(cur) |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
237 |
finished.add(cur) |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
238 |
else: |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
239 |
visit.append(-cur - 1) |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
240 |
visit += [p for p in self.parents(cur) |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
241 |
if p in ixs and p not in finished] |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
242 |
assert len(sorted) == len(ixs) |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
243 |
return sorted |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
244 |
|
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
245 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
246 |
class inverserevlogdag(revlogbaseddag, genericdag): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
247 |
'''inverse of an existing revlog dag; see revlogdag.inverse()''' |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
248 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
249 |
def __init__(self, orig): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
250 |
revlogbaseddag.__init__(self, orig._revlog, orig._nodeset) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
251 |
self._orig = orig |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
252 |
self._children = {} |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
253 |
self._roots = [] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
254 |
self._walkfrom = len(self._revlog) - 1 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
255 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
256 |
def _walkto(self, walkto): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
257 |
rev = self._walkfrom |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
258 |
cs = self._children |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
259 |
roots = self._roots |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
260 |
idx = self._revlog.index |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
261 |
while rev >= walkto: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
262 |
data = idx[rev] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
263 |
isroot = True |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
264 |
for prev in [data[5], data[6]]: # parent revs |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
265 |
if prev != nullrev: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
266 |
cs.setdefault(prev, []).append(rev) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
267 |
isroot = False |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
268 |
if isroot: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
269 |
roots.append(rev) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
270 |
rev -= 1 |
15052
06c3667c259c
dagutil: fix off-by-one in inverserevlogdag buildup
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
14634
diff
changeset
|
271 |
self._walkfrom = rev |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
272 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
273 |
def _getheads(self): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
274 |
self._walkto(nullrev) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
275 |
return self._roots |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
276 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
277 |
def parents(self, ix): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
278 |
if ix is None: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
279 |
return [] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
280 |
if ix <= self._walkfrom: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
281 |
self._walkto(ix) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
282 |
return self._children.get(ix, []) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
283 |
|
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
284 |
def inverse(self): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
285 |
return self._orig |