author | Martin von Zweigbergk <martinvonz@google.com> |
Fri, 09 Sep 2022 12:45:26 -0700 | |
changeset 49495 | 59a72267f5ce |
parent 49284 | d44e3c45f0e4 |
child 51395 | a0d88b021a98 |
permissions | -rw-r--r-- |
32903
27932a76a88d
dagop: split module hosting DAG-related algorithms from revset
Yuya Nishihara <yuya@tcha.org>
parents:
32885
diff
changeset
|
1 |
# dagop.py - graph ancestry and topology algorithm for revset |
11275 | 2 |
# |
46819
d4ba4d51f85f
contributor: change mentions of mpm to olivia
Raphaël Gomès <rgomes@octobus.net>
parents:
46113
diff
changeset
|
3 |
# Copyright 2010 Olivia Mackall <olivia@selenic.com> |
11275 | 4 |
# |
5 |
# This software may be used and distributed according to the terms of the |
|
6 |
# GNU General Public License version 2 or any later version. |
|
7 |
||
25971
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
8 |
|
20690
13c0327eeb6f
revset: changed ancestors revset to return lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents:
20659
diff
changeset
|
9 |
import heapq |
25971
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
10 |
|
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
11 |
from .thirdparty import attr |
46113
59fa3890d40a
node: import symbols explicitly
Joerg Sonnenberger <joerg@bec.de>
parents:
45942
diff
changeset
|
12 |
from .node import nullrev |
25971
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
13 |
from . import ( |
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
14 |
error, |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
15 |
mdiff, |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
16 |
patch, |
36918
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
17 |
pycompat, |
45416
4ebc5f325bed
log: fix crash and bad filematcher lookup by -fr'wdir()' PATH
Yuya Nishihara <yuya@tcha.org>
parents:
44659
diff
changeset
|
18 |
scmutil, |
30881
1be65deb3d54
smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
30850
diff
changeset
|
19 |
smartset, |
25971
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
20 |
) |
11275 | 21 |
|
30881
1be65deb3d54
smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
30850
diff
changeset
|
22 |
baseset = smartset.baseset |
1be65deb3d54
smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
30850
diff
changeset
|
23 |
generatorset = smartset.generatorset |
1be65deb3d54
smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
30850
diff
changeset
|
24 |
|
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
25 |
# possible maximum depth between null and wdir() |
41359
431cf2c8c839
revset: support ranges in #generations relation
Anton Shestakov <av6@dwimlabs.net>
parents:
41277
diff
changeset
|
26 |
maxlogdepth = 0x80000000 |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
27 |
|
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
28 |
|
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
29 |
def _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse): |
33078
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
30 |
"""Walk DAG using 'pfunc' from the given 'revs' nodes |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
31 |
|
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
32 |
'pfunc(rev)' should return the parent/child revisions of the given 'rev' |
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
33 |
if 'reverse' is True/False respectively. |
33078
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
34 |
|
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
35 |
Scan ends at the stopdepth (exlusive) if specified. Revisions found |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
36 |
earlier than the startdepth are omitted. |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
37 |
""" |
33003
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
38 |
if startdepth is None: |
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
39 |
startdepth = 0 |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
40 |
if stopdepth is None: |
41359
431cf2c8c839
revset: support ranges in #generations relation
Anton Shestakov <av6@dwimlabs.net>
parents:
41277
diff
changeset
|
41 |
stopdepth = maxlogdepth |
33027
a10f5f6771f6
dagop: raise ProgrammingError if stopdepth < 0
Martin von Zweigbergk <martinvonz@google.com>
parents:
33003
diff
changeset
|
42 |
if stopdepth == 0: |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
43 |
return |
33027
a10f5f6771f6
dagop: raise ProgrammingError if stopdepth < 0
Martin von Zweigbergk <martinvonz@google.com>
parents:
33003
diff
changeset
|
44 |
if stopdepth < 0: |
43077
687b865b95ad
formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents:
43076
diff
changeset
|
45 |
raise error.ProgrammingError(b'negative stopdepth') |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
46 |
if reverse: |
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
47 |
heapsign = -1 # max heap |
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
48 |
else: |
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
49 |
heapsign = +1 # min heap |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
50 |
|
32998
c7da57bbae96
dagop: comment why revancestors() doesn't heapify input revs at once
Yuya Nishihara <yuya@tcha.org>
parents:
32997
diff
changeset
|
51 |
# load input revs lazily to heap so earlier revisions can be yielded |
c7da57bbae96
dagop: comment why revancestors() doesn't heapify input revs at once
Yuya Nishihara <yuya@tcha.org>
parents:
32997
diff
changeset
|
52 |
# without fully computing the input revs |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
53 |
revs.sort(reverse) |
32997
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
54 |
irevs = iter(revs) |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
55 |
pendingheap = [] # [(heapsign * rev, depth), ...] (i.e. lower depth first) |
20690
13c0327eeb6f
revset: changed ancestors revset to return lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents:
20659
diff
changeset
|
56 |
|
32997
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
57 |
inputrev = next(irevs, None) |
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
58 |
if inputrev is not None: |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
59 |
heapq.heappush(pendingheap, (heapsign * inputrev, 0)) |
20691
c1f666e27345
revset: optimized _revancestors method based on order of revisions
Lucas Moscovicz <lmoscovicz@fb.com>
parents:
20690
diff
changeset
|
60 |
|
33000
d3d36bcdf036
dagop: just compare with the last value to deduplicate input of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32999
diff
changeset
|
61 |
lastrev = None |
32999
08e2793d9f65
dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
32998
diff
changeset
|
62 |
while pendingheap: |
33001
92d0945a15e0
dagop: compute depth in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33000
diff
changeset
|
63 |
currev, curdepth = heapq.heappop(pendingheap) |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
64 |
currev = heapsign * currev |
32999
08e2793d9f65
dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
32998
diff
changeset
|
65 |
if currev == inputrev: |
32997
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
66 |
inputrev = next(irevs, None) |
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
67 |
if inputrev is not None: |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
68 |
heapq.heappush(pendingheap, (heapsign * inputrev, 0)) |
33003
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
69 |
# rescan parents until curdepth >= startdepth because queued entries |
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
70 |
# of the same revision are iterated from the lowest depth |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
71 |
foundnew = currev != lastrev |
33003
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
72 |
if foundnew and curdepth >= startdepth: |
33000
d3d36bcdf036
dagop: just compare with the last value to deduplicate input of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32999
diff
changeset
|
73 |
lastrev = currev |
32999
08e2793d9f65
dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
32998
diff
changeset
|
74 |
yield currev |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
75 |
pdepth = curdepth + 1 |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
76 |
if foundnew and pdepth < stopdepth: |
33077
58ebb38456e0
dagop: factor out pfunc from revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33076
diff
changeset
|
77 |
for prev in pfunc(currev): |
46113
59fa3890d40a
node: import symbols explicitly
Joerg Sonnenberger <joerg@bec.de>
parents:
45942
diff
changeset
|
78 |
if prev != nullrev: |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
79 |
heapq.heappush(pendingheap, (heapsign * prev, pdepth)) |
20690
13c0327eeb6f
revset: changed ancestors revset to return lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents:
20659
diff
changeset
|
80 |
|
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
81 |
|
35276
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35275
diff
changeset
|
82 |
def filectxancestors(fctxs, followfirst=False): |
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35275
diff
changeset
|
83 |
"""Like filectx.ancestors(), but can walk from multiple files/revisions, |
35296
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
84 |
and includes the given fctxs themselves |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
85 |
|
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
86 |
Yields (rev, {fctx, ...}) pairs in descending order. |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
87 |
""" |
35270
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
88 |
visit = {} |
35297
c9144396099b
dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35296
diff
changeset
|
89 |
visitheap = [] |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
90 |
|
35274
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35273
diff
changeset
|
91 |
def addvisit(fctx): |
45416
4ebc5f325bed
log: fix crash and bad filematcher lookup by -fr'wdir()' PATH
Yuya Nishihara <yuya@tcha.org>
parents:
44659
diff
changeset
|
92 |
rev = scmutil.intrev(fctx) |
35274
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35273
diff
changeset
|
93 |
if rev not in visit: |
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35273
diff
changeset
|
94 |
visit[rev] = set() |
35297
c9144396099b
dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35296
diff
changeset
|
95 |
heapq.heappush(visitheap, -rev) # max heap |
35274
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35273
diff
changeset
|
96 |
visit[rev].add(fctx) |
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35273
diff
changeset
|
97 |
|
35270
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
98 |
if followfirst: |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
99 |
cut = 1 |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
100 |
else: |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
101 |
cut = None |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
102 |
|
35276
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35275
diff
changeset
|
103 |
for c in fctxs: |
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35275
diff
changeset
|
104 |
addvisit(c) |
35275
b4b328ea6175
dagop: put start fctx into visit dict of filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35274
diff
changeset
|
105 |
while visit: |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
106 |
currev = -(heapq.heappop(visitheap)) |
35296
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
107 |
curfctxs = visit.pop(currev) |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
108 |
yield currev, curfctxs |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
109 |
for c in curfctxs: |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
110 |
for parent in c.parents()[:cut]: |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
111 |
addvisit(parent) |
35297
c9144396099b
dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35296
diff
changeset
|
112 |
assert not visitheap |
35296
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
113 |
|
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
114 |
|
35296
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
115 |
def filerevancestors(fctxs, followfirst=False): |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
116 |
"""Like filectx.ancestors(), but can walk from multiple files/revisions, |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
117 |
and includes the given fctxs themselves |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
118 |
|
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
119 |
Returns a smartset. |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
120 |
""" |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
121 |
gen = (rev for rev, _cs in filectxancestors(fctxs, followfirst)) |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
122 |
return generatorset(gen, iterasc=False) |
35270
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
123 |
|
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
124 |
|
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
125 |
def _genrevancestors(repo, revs, followfirst, startdepth, stopdepth, cutfunc): |
33078
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
126 |
if followfirst: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
127 |
cut = 1 |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
128 |
else: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
129 |
cut = None |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
130 |
cl = repo.changelog |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
131 |
|
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
132 |
def plainpfunc(rev): |
33078
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
133 |
try: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
134 |
return cl.parentrevs(rev)[:cut] |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
135 |
except error.WdirUnsupported: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
136 |
return (pctx.rev() for pctx in repo[rev].parents()[:cut]) |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
137 |
|
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
138 |
if cutfunc is None: |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
139 |
pfunc = plainpfunc |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
140 |
else: |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
141 |
pfunc = lambda rev: [r for r in plainpfunc(rev) if not cutfunc(r)] |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
142 |
revs = revs.filter(lambda rev: not cutfunc(rev)) |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
143 |
return _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse=True) |
33078
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
144 |
|
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
145 |
|
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
146 |
def revancestors( |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
147 |
repo, revs, followfirst=False, startdepth=None, stopdepth=None, cutfunc=None |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
148 |
): |
41533
0f64091cc851
global: make some docstrings raw strings
Gregory Szorc <gregory.szorc@gmail.com>
parents:
41389
diff
changeset
|
149 |
r"""Like revlog.ancestors(), but supports additional options, includes |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
150 |
the given revs themselves, and returns a smartset |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
151 |
|
33003
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
152 |
Scan ends at the stopdepth (exlusive) if specified. Revisions found |
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
153 |
earlier than the startdepth are omitted. |
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
154 |
|
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
155 |
If cutfunc is provided, it will be used to cut the traversal of the DAG. |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
156 |
When cutfunc(X) returns True, the DAG traversal stops - revision X and |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
157 |
X's ancestors in the traversal path will be skipped. This could be an |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
158 |
optimization sometimes. |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
159 |
|
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
160 |
Note: if Y is an ancestor of X, cutfunc(X) returning True does not |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
161 |
necessarily mean Y will also be cut. Usually cutfunc(Y) also wants to |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
162 |
return True in this case. For example, |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
163 |
|
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
164 |
D # revancestors(repo, D, cutfunc=lambda rev: rev == B) |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
165 |
|\ # will include "A", because the path D -> C -> A was not cut. |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
166 |
B C # If "B" gets cut, "A" might want to be cut too. |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
167 |
|/ |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
168 |
A |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
169 |
""" |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
170 |
gen = _genrevancestors( |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
171 |
repo, revs, followfirst, startdepth, stopdepth, cutfunc |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
172 |
) |
32997
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
173 |
return generatorset(gen, iterasc=False) |
16409
2cbd7dd0cc1f
graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents:
16402
diff
changeset
|
174 |
|
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
175 |
|
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
176 |
def _genrevdescendants(repo, revs, followfirst): |
24306
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
24219
diff
changeset
|
177 |
if followfirst: |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
24219
diff
changeset
|
178 |
cut = 1 |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
24219
diff
changeset
|
179 |
else: |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
24219
diff
changeset
|
180 |
cut = None |
16409
2cbd7dd0cc1f
graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents:
16402
diff
changeset
|
181 |
|
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
182 |
cl = repo.changelog |
33076
a76a64c78807
dagop: use smartset.min() in revdescendants() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33075
diff
changeset
|
183 |
first = revs.min() |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
184 |
if first == nullrev: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
185 |
# Are there nodes with a null first parent and a non-null |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
186 |
# second one? Maybe. Do we care? Probably not. |
33075
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
187 |
yield first |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
188 |
for i in cl: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
189 |
yield i |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
190 |
else: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
191 |
seen = set(revs) |
33075
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
192 |
for i in cl.revs(first): |
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
193 |
if i in seen: |
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
194 |
yield i |
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
195 |
continue |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
196 |
for x in cl.parentrevs(i)[:cut]: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
197 |
if x != nullrev and x in seen: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
198 |
seen.add(i) |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
199 |
yield i |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
200 |
break |
20692
7af341082b76
revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents:
20691
diff
changeset
|
201 |
|
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
202 |
|
33080
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
203 |
def _builddescendantsmap(repo, startrev, followfirst): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
204 |
"""Build map of 'rev -> child revs', offset from startrev""" |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
205 |
cl = repo.changelog |
49284
d44e3c45f0e4
py3: replace `pycompat.xrange` by `range`
Manuel Jacob <me@manueljacob.de>
parents:
48946
diff
changeset
|
206 |
descmap = [[] for _rev in range(startrev, len(cl))] |
33080
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
207 |
for currev in cl.revs(startrev + 1): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
208 |
p1rev, p2rev = cl.parentrevs(currev) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
209 |
if p1rev >= startrev: |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
210 |
descmap[p1rev - startrev].append(currev) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
211 |
if not followfirst and p2rev != nullrev and p2rev >= startrev: |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
212 |
descmap[p2rev - startrev].append(currev) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
213 |
return descmap |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
214 |
|
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
215 |
|
33080
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
216 |
def _genrevdescendantsofdepth(repo, revs, followfirst, startdepth, stopdepth): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
217 |
startrev = revs.min() |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
218 |
descmap = _builddescendantsmap(repo, startrev, followfirst) |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
219 |
|
33080
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
220 |
def pfunc(rev): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
221 |
return descmap[rev - startrev] |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
222 |
|
33080
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
223 |
return _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse=False) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
224 |
|
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
225 |
|
33080
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
226 |
def revdescendants(repo, revs, followfirst, startdepth=None, stopdepth=None): |
33075
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
227 |
"""Like revlog.descendants() but supports additional options, includes |
33080
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
228 |
the given revs themselves, and returns a smartset |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
229 |
|
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
230 |
Scan ends at the stopdepth (exlusive) if specified. Revisions found |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
231 |
earlier than the startdepth are omitted. |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
232 |
""" |
41389
7e55ca658e4b
dagop: check if stopdepth is greater than or equal to maxlogdepth
Anton Shestakov <av6@dwimlabs.net>
parents:
41359
diff
changeset
|
233 |
if startdepth is None and (stopdepth is None or stopdepth >= maxlogdepth): |
33080
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
234 |
gen = _genrevdescendants(repo, revs, followfirst) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
235 |
else: |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
236 |
gen = _genrevdescendantsofdepth( |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
237 |
repo, revs, followfirst, startdepth, stopdepth |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
238 |
) |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
239 |
return generatorset(gen, iterasc=True) |
16409
2cbd7dd0cc1f
graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents:
16402
diff
changeset
|
240 |
|
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
241 |
|
39999
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
242 |
def descendantrevs(revs, revsfn, parentrevsfn): |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
243 |
"""Generate revision number descendants in revision order. |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
244 |
|
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
245 |
Yields revision numbers starting with a child of some rev in |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
246 |
``revs``. Results are ordered by revision number and are |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
247 |
therefore topological. Each revision is not considered a descendant |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
248 |
of itself. |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
249 |
|
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
250 |
``revsfn`` is a callable that with no argument iterates over all |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
251 |
revision numbers and with a ``start`` argument iterates over revision |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
252 |
numbers beginning with that value. |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
253 |
|
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
254 |
``parentrevsfn`` is a callable that receives a revision number and |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
255 |
returns an iterable of parent revision numbers, whose values may include |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
256 |
nullrev. |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
257 |
""" |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
258 |
first = min(revs) |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
259 |
|
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
260 |
if first == nullrev: |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
261 |
for rev in revsfn(): |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
262 |
yield rev |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
263 |
return |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
264 |
|
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
265 |
seen = set(revs) |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
266 |
for rev in revsfn(start=first + 1): |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
267 |
for prev in parentrevsfn(rev): |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
268 |
if prev != nullrev and prev in seen: |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
269 |
seen.add(rev) |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
270 |
yield rev |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
271 |
break |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
272 |
|
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
273 |
|
48946
642e31cb55f0
py3: use class X: instead of class X(object):
Gregory Szorc <gregory.szorc@gmail.com>
parents:
48875
diff
changeset
|
274 |
class subsetparentswalker: |
44592
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
275 |
r"""Scan adjacent ancestors in the graph given by the subset |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
276 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
277 |
This computes parent-child relations in the sub graph filtered by |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
278 |
a revset. Primary use case is to draw a revisions graph. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
279 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
280 |
In the following example, we consider that the node 'f' has edges to all |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
281 |
ancestor nodes, but redundant paths are eliminated. The edge 'f'->'b' |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
282 |
is eliminated because there is a path 'f'->'c'->'b' for example. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
283 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
284 |
- d - e - |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
285 |
/ \ |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
286 |
a - b - c - f |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
287 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
288 |
If the node 'c' is filtered out, the edge 'f'->'b' is activated. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
289 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
290 |
- d - e - |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
291 |
/ \ |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
292 |
a - b -(c)- f |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
293 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
294 |
Likewise, if 'd' and 'e' are filtered out, this edge is fully eliminated |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
295 |
since there is a path 'f'->'c'->'b'->'a' for 'f'->'a'. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
296 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
297 |
(d) (e) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
298 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
299 |
a - b - c - f |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
300 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
301 |
Implementation-wise, 'f' is passed down to 'a' as unresolved through the |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
302 |
'f'->'e'->'d'->'a' path, whereas we do also remember that 'f' has already |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
303 |
been resolved while walking down the 'f'->'c'->'b'->'a' path. When |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
304 |
processing the node 'a', the unresolved 'f'->'a' path is eliminated as |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
305 |
the 'f' end is marked as resolved. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
306 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
307 |
Ancestors are searched from the tipmost revision in the subset so the |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
308 |
results can be cached. You should specify startrev to narrow the search |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
309 |
space to ':startrev'. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
310 |
""" |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
311 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
312 |
def __init__(self, repo, subset, startrev=None): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
313 |
if startrev is not None: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
314 |
subset = repo.revs(b'%d:null', startrev) & subset |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
315 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
316 |
# equivalent to 'subset = subset.sorted(reverse=True)', but there's |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
317 |
# no such function. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
318 |
fastdesc = subset.fastdesc |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
319 |
if fastdesc: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
320 |
desciter = fastdesc() |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
321 |
else: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
322 |
if not subset.isdescending() and not subset.istopo(): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
323 |
subset = smartset.baseset(subset) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
324 |
subset.sort(reverse=True) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
325 |
desciter = iter(subset) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
326 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
327 |
self._repo = repo |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
328 |
self._changelog = repo.changelog |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
329 |
self._subset = subset |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
330 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
331 |
# scanning state (see _scanparents): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
332 |
self._tovisit = [] |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
333 |
self._pendingcnt = {} |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
334 |
self._pointers = {} |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
335 |
self._parents = {} |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
336 |
self._inputhead = nullrev # reassigned by self._advanceinput() |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
337 |
self._inputtail = desciter |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
338 |
self._bottomrev = nullrev |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
339 |
self._advanceinput() |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
340 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
341 |
def parentsset(self, rev): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
342 |
"""Look up parents of the given revision in the subset, and returns |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
343 |
as a smartset""" |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
344 |
return smartset.baseset(self.parents(rev)) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
345 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
346 |
def parents(self, rev): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
347 |
"""Look up parents of the given revision in the subset |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
348 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
349 |
The returned revisions are sorted by parent index (p1/p2). |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
350 |
""" |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
351 |
self._scanparents(rev) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
352 |
return [r for _c, r in sorted(self._parents.get(rev, []))] |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
353 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
354 |
def _parentrevs(self, rev): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
355 |
try: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
356 |
revs = self._changelog.parentrevs(rev) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
357 |
if revs[-1] == nullrev: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
358 |
return revs[:-1] |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
359 |
return revs |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
360 |
except error.WdirUnsupported: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
361 |
return tuple(pctx.rev() for pctx in self._repo[None].parents()) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
362 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
363 |
def _advanceinput(self): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
364 |
"""Advance the input iterator and set the next revision to _inputhead""" |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
365 |
if self._inputhead < nullrev: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
366 |
return |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
367 |
try: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
368 |
self._inputhead = next(self._inputtail) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
369 |
except StopIteration: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
370 |
self._bottomrev = self._inputhead |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
371 |
self._inputhead = nullrev - 1 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
372 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
373 |
def _scanparents(self, stoprev): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
374 |
"""Scan ancestors until the parents of the specified stoprev are |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
375 |
resolved""" |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
376 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
377 |
# 'tovisit' is the queue of the input revisions and their ancestors. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
378 |
# It will be populated incrementally to minimize the initial cost |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
379 |
# of computing the given subset. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
380 |
# |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
381 |
# For to-visit revisions, we keep track of |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
382 |
# - the number of the unresolved paths: pendingcnt[rev], |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
383 |
# - dict of the unresolved descendants and chains: pointers[rev][0], |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
384 |
# - set of the already resolved descendants: pointers[rev][1]. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
385 |
# |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
386 |
# When a revision is visited, 'pointers[rev]' should be popped and |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
387 |
# propagated to its parents accordingly. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
388 |
# |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
389 |
# Once all pending paths have been resolved, 'pendingcnt[rev]' becomes |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
390 |
# 0 and 'parents[rev]' contains the unsorted list of parent revisions |
44659
67f757ed86e0
dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents:
44658
diff
changeset
|
391 |
# and p1/p2 chains (excluding linear paths.) The p1/p2 chains will be |
67f757ed86e0
dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents:
44658
diff
changeset
|
392 |
# used as a sort key preferring p1. 'len(chain)' should be the number |
67f757ed86e0
dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents:
44658
diff
changeset
|
393 |
# of merges between two revisions. |
44592
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
394 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
395 |
subset = self._subset |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
396 |
tovisit = self._tovisit # heap queue of [-rev] |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
397 |
pendingcnt = self._pendingcnt # {rev: count} for visited revisions |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
398 |
pointers = self._pointers # {rev: [{unresolved_rev: chain}, resolved]} |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
399 |
parents = self._parents # {rev: [(chain, rev)]} |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
400 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
401 |
while tovisit or self._inputhead >= nullrev: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
402 |
if pendingcnt.get(stoprev) == 0: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
403 |
return |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
404 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
405 |
# feed greater revisions from input set to queue |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
406 |
if not tovisit: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
407 |
heapq.heappush(tovisit, -self._inputhead) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
408 |
self._advanceinput() |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
409 |
while self._inputhead >= -tovisit[0]: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
410 |
heapq.heappush(tovisit, -self._inputhead) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
411 |
self._advanceinput() |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
412 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
413 |
rev = -heapq.heappop(tovisit) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
414 |
if rev < self._bottomrev: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
415 |
return |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
416 |
if rev in pendingcnt and rev not in pointers: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
417 |
continue # already visited |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
418 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
419 |
curactive = rev in subset |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
420 |
pendingcnt.setdefault(rev, 0) # mark as visited |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
421 |
if curactive: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
422 |
assert rev not in parents |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
423 |
parents[rev] = [] |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
424 |
unresolved, resolved = pointers.pop(rev, ({}, set())) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
425 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
426 |
if curactive: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
427 |
# reached to active rev, resolve pending descendants' parents |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
428 |
for r, c in unresolved.items(): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
429 |
pendingcnt[r] -= 1 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
430 |
assert pendingcnt[r] >= 0 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
431 |
if r in resolved: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
432 |
continue # eliminate redundant path |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
433 |
parents[r].append((c, rev)) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
434 |
# mark the descendant 'r' as resolved through this path if |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
435 |
# there are still pending pointers. the 'resolved' set may |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
436 |
# be concatenated later at a fork revision. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
437 |
if pendingcnt[r] > 0: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
438 |
resolved.add(r) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
439 |
unresolved.clear() |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
440 |
# occasionally clean resolved markers. otherwise the set |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
441 |
# would grow indefinitely. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
442 |
resolved = {r for r in resolved if pendingcnt[r] > 0} |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
443 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
444 |
parentrevs = self._parentrevs(rev) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
445 |
bothparentsactive = all(p in subset for p in parentrevs) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
446 |
|
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
447 |
# set up or propagate tracking pointers if |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
448 |
# - one of the parents is not active, |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
449 |
# - or descendants' parents are unresolved. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
450 |
if not bothparentsactive or unresolved or resolved: |
44658
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
451 |
if len(parentrevs) <= 1: |
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
452 |
# can avoid copying the tracking pointer |
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
453 |
parentpointers = [(unresolved, resolved)] |
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
454 |
else: |
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
455 |
parentpointers = [ |
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
456 |
(unresolved, resolved), |
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
457 |
(unresolved.copy(), resolved.copy()), |
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
458 |
] |
44592
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
459 |
# 'rev' is a merge revision. increment the pending count |
44659
67f757ed86e0
dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents:
44658
diff
changeset
|
460 |
# as the 'unresolved' dict will be duplicated, and append |
67f757ed86e0
dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents:
44658
diff
changeset
|
461 |
# p1/p2 code to the existing chains. |
44592 |