Mercurial > hg
annotate mercurial/dagutil.py @ 16719:e7bf09acd410
localrepo: add branchtip() method for faster single-branch lookups
For the PyPy repo with 744 branches and 843 branch heads, this brings
hg log -r default over NFS from:
CallCount Recursive Total(ms) Inline(ms) module:lineno(function)
3249 0 1.3222 1.3222 <open>
3244 0 0.6211 0.6211 <method 'close' of 'file' objects>
3243 0 0.0800 0.0800 <method 'read' of 'file' objects>
3241 0 0.0660 0.0660 <method 'seek' of 'file' objects>
3905 0 0.0476 0.0476 <zlib.decompress>
3281 0 2.6756 0.0472 mercurial.changelog:182(read)
+3281 0 2.5256 0.0453 +mercurial.revlog:881(revision)
+3276 0 0.0389 0.0196 +mercurial.changelog:28(decodeextra)
+6562 0 0.0123 0.0123 +<method 'split' of 'str' objects>
+6562 0 0.0408 0.0073 +mercurial.encoding:61(tolocal)
+3281 0 0.0054 0.0054 +<method 'index' of 'str' objects>
3241 0 2.2464 0.0456 mercurial.revlog:818(_loadchunk)
+3241 0 0.6205 0.6205 +<method 'close' of 'file' objects>
+3241 0 0.0765 0.0765 +<method 'read' of 'file' objects>
+3241 0 0.0660 0.0660 +<method 'seek' of 'file' objects>
+3241 0 1.4209 0.0135 +mercurial.store:374(__call__)
+3241 0 0.0122 0.0107 +mercurial.revlog:810(_addchunk)
3281 0 2.5256 0.0453 mercurial.revlog:881(revision)
+3280 0 0.0175 0.0175 +mercurial.revlog:305(rev)
+3281 0 2.2819 0.0119 +mercurial.revlog:847(_chunkraw)
+3281 0 0.0603 0.0083 +mercurial.revlog:945(_checkhash)
+3281 0 0.0051 0.0051 +mercurial.revlog:349(flags)
+3281 0 0.0040 0.0040 +<mercurial.mpatch.patches>
13682 0 0.0479 0.0248 <method 'decode' of 'str' objects>
+7418 0 0.0228 0.0076 +encodings.utf_8:15(decode)
+1 0 0.0003 0.0000 +encodings:71(search_function)
3248 0 1.3995 0.0246 mercurial.scmutil:218(__call__)
+3248 0 1.3222 1.3222 +<open>
+3248 0 0.0235 0.0184 +os.path:80(split)
+3248 0 0.0084 0.0068 +mercurial.scmutil:92(__call__)
Time: real 2.750 secs (user 0.680+0.000 sys 0.360+0.000)
down to:
CallCount Recursive Total(ms) Inline(ms) module:lineno(function)
55 31 0.0197 0.0163 <__import__>
+1 0 0.0006 0.0002 +mercurial.context:8(<module>)
+1 0 0.0042 0.0001 +mercurial.revlog:12(<module>)
+1 0 0.0002 0.0001 +mercurial.match:8(<module>)
+1 0 0.0003 0.0001 +mercurial.dirstate:7(<module>)
+1 0 0.0057 0.0001 +mercurial.changelog:8(<module>)
1 0 0.0117 0.0032 mercurial.localrepo:525(_readbranchcache)
+844 0 0.0015 0.0015 +<binascii.unhexlify>
+845 0 0.0010 0.0010 +<method 'split' of 'str' objects>
+843 0 0.0045 0.0009 +mercurial.encoding:61(tolocal)
+843 0 0.0004 0.0004 +<method 'setdefault' of 'dict' objects>
+1 0 0.0003 0.0003 +<method 'close' of 'file' objects>
3 0 0.0029 0.0029 <method 'read' of 'file' objects>
9 0 0.0018 0.0018 <open>
990 0 0.0017 0.0017 <binascii.unhexlify>
53 0 0.0016 0.0016 mercurial.demandimport:43(__init__)
862 0 0.0015 0.0015 <_codecs.utf_8_decode>
862 0 0.0037 0.0014 <method 'decode' of 'str' objects>
+862 0 0.0023 0.0008 +encodings.utf_8:15(decode)
981 0 0.0011 0.0011 <method 'split' of 'str' objects>
861 0 0.0046 0.0009 mercurial.encoding:61(tolocal)
+861 0 0.0037 0.0014 +<method 'decode' of 'str' objects>
862 0 0.0023 0.0008 encodings.utf_8:15(decode)
+862 0 0.0015 0.0015 +<_codecs.utf_8_decode>
4 0 0.0008 0.0008 <method 'close' of 'file' objects>
179 154 0.0202 0.0004 mercurial.demandimport:83(__getattribute__)
+36 11 0.0199 0.0003 +mercurial.demandimport:55(_load)
+72 0 0.0001 0.0001 +mercurial.demandimport:83(__getattribute__)
+36 0 0.0000 0.0000 +<getattr>
1 0 0.0015 0.0004 mercurial.tags:148(_readtagcache)
Time: real 0.060 secs (user 0.030+0.000 sys 0.010+0.000)
author | Brodie Rao <brodie@sf.io> |
---|---|
date | Sun, 13 May 2012 14:04:04 +0200 |
parents | e34106fa0dc3 |
children | 37e2bd560805 |
rev | line source |
---|---|
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): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
28 '''set of all node idxs''' |
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): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
65 '''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
|
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): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
76 '''return a list of (or set if given a set) of node ixs''' |
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): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
80 '''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
|
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): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
91 stops = stops and set(stops) or set() |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
92 seen = set() |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
93 pending = list(starts) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
94 while pending: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
95 n = pending.pop() |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
96 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
|
97 seen.add(n) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
98 pending.extend(self.parents(n)) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
99 return seen |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
100 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
101 def headsetofconnecteds(self, ixs): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
102 hds = set(ixs) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
103 if not hds: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
104 return hds |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
105 for n in ixs: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
106 for p in self.parents(n): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
107 hds.discard(p) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
108 assert hds |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
109 return hds |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
110 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
111 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
112 class revlogbaseddag(basedag): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
113 '''generic dag interface to a revlog''' |
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 def __init__(self, revlog, nodeset): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
116 basedag.__init__(self) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
117 self._revlog = revlog |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
118 self._heads = None |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
119 self._nodeset = nodeset |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
120 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
121 def nodeset(self): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
122 return self._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 heads(self): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
125 if self._heads is None: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
126 self._heads = self._getheads() |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
127 return self._heads |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
128 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
129 def _externalize(self, ix): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
130 return self._revlog.index[ix][7] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
131 def _externalizeall(self, ixs): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
132 idx = self._revlog.index |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
133 return [idx[i][7] for i in ixs] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
134 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
135 def _internalize(self, id): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
136 ix = self._revlog.rev(id) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
137 if ix == nullrev: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
138 raise LookupError(id, self._revlog.indexfile, _('nullid')) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
139 return ix |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
140 def _internalizeall(self, ids, filterunknown): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
141 rl = self._revlog |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
142 if filterunknown: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
143 return [r for r in map(rl.nodemap.get, ids) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
144 if r is not None and r != nullrev] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
145 return map(self._internalize, ids) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
146 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
147 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
148 class revlogdag(revlogbaseddag): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
149 '''dag interface to a revlog''' |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
150 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
151 def __init__(self, revlog): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
152 revlogbaseddag.__init__(self, revlog, set(xrange(len(revlog)))) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
153 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
154 def _getheads(self): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
155 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
|
156 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
157 def parents(self, ix): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
158 rlog = self._revlog |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
159 idx = rlog.index |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
160 revdata = idx[ix] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
161 prev = revdata[5] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
162 if prev != nullrev: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
163 prev2 = revdata[6] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
164 if prev2 == nullrev: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
165 return [prev] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
166 return [prev, prev2] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
167 prev2 = revdata[6] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
168 if prev2 != nullrev: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
169 return [prev2] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
170 return [] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
171 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
172 def inverse(self): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
173 if self._inverse is None: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
174 self._inverse = inverserevlogdag(self) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
175 return self._inverse |
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 ancestorset(self, starts, stops=None): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
178 rlog = self._revlog |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
179 idx = rlog.index |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
180 stops = stops and set(stops) or set() |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
181 seen = set() |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
182 pending = list(starts) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
183 while pending: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
184 rev = pending.pop() |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
185 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
|
186 seen.add(rev) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
187 revdata = idx[rev] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
188 for i in [5, 6]: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
189 prev = revdata[i] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
190 if prev != nullrev: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
191 pending.append(prev) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
192 return seen |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
193 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
194 def headsetofconnecteds(self, ixs): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
195 if not ixs: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
196 return set() |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
197 rlog = self._revlog |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
198 idx = rlog.index |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
199 headrevs = set(ixs) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
200 for rev in ixs: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
201 revdata = idx[rev] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
202 for i in [5, 6]: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
203 prev = revdata[i] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
204 if prev != nullrev: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
205 headrevs.discard(prev) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
206 assert headrevs |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
207 return headrevs |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
208 |
14364
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
209 def linearize(self, ixs): |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
210 '''linearize and topologically sort a list of revisions |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
211 |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
212 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
|
213 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
|
214 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
|
215 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
|
216 parent, then adding the rev itself to the output list. |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
217 ''' |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
218 sorted = [] |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
219 visit = list(self.headsetofconnecteds(ixs)) |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
220 visit.sort(reverse=True) |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
221 finished = set() |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
222 |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
223 while visit: |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
224 cur = visit.pop() |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
225 if cur < 0: |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
226 cur = -cur - 1 |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
227 if cur not in finished: |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
228 sorted.append(cur) |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
229 finished.add(cur) |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
230 else: |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
231 visit.append(-cur - 1) |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
232 visit += [p for p in self.parents(cur) |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
233 if p in ixs and p not in finished] |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
234 assert len(sorted) == len(ixs) |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
235 return sorted |
a3b9f1bddab1
revlogdag: add linearize function
Sune Foldager <cryo@cyanite.org>
parents:
14206
diff
changeset
|
236 |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
237 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
238 class inverserevlogdag(revlogbaseddag, genericdag): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
239 '''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
|
240 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
241 def __init__(self, orig): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
242 revlogbaseddag.__init__(self, orig._revlog, orig._nodeset) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
243 self._orig = orig |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
244 self._children = {} |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
245 self._roots = [] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
246 self._walkfrom = len(self._revlog) - 1 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
247 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
248 def _walkto(self, walkto): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
249 rev = self._walkfrom |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
250 cs = self._children |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
251 roots = self._roots |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
252 idx = self._revlog.index |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
253 while rev >= walkto: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
254 data = idx[rev] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
255 isroot = True |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
256 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
|
257 if prev != nullrev: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
258 cs.setdefault(prev, []).append(rev) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
259 isroot = False |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
260 if isroot: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
261 roots.append(rev) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
262 rev -= 1 |
15052
06c3667c259c
dagutil: fix off-by-one in inverserevlogdag buildup
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
14634
diff
changeset
|
263 self._walkfrom = rev |
14164
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
264 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
265 def _getheads(self): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
266 self._walkto(nullrev) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
267 return self._roots |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
268 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
269 def parents(self, ix): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
270 if ix is None: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
271 return [] |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
272 if ix <= self._walkfrom: |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
273 self._walkto(ix) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
274 return self._children.get(ix, []) |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
275 |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
276 def inverse(self): |
cb98fed52495
discovery: add new set-based discovery
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents:
diff
changeset
|
277 return self._orig |