Mercurial > hg
annotate mercurial/dagop.py @ 51630:513597087b89
branching: merge stable into default
author | Pierre-Yves David <pierre-yves.david@octobus.net> |
---|---|
date | Mon, 10 Jun 2024 12:12:56 +0200 |
parents | a0d88b021a98 |
children | 278af66e6595 |
rev | line source |
---|---|
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
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
462 for r in unresolved: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
463 pendingcnt[r] += 1 |
44659
67f757ed86e0
dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents:
44658
diff
changeset
|
464 parentpointers[0][0][r] += b'1' |
67f757ed86e0
dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents:
44658
diff
changeset
|
465 parentpointers[1][0][r] += b'2' |
44592
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
466 for i, p in enumerate(parentrevs): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
467 assert p < rev |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
468 heapq.heappush(tovisit, -p) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
469 if p in pointers: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
470 # 'p' is a fork revision. concatenate tracking pointers |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
471 # and decrement the pending count accordingly. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
472 knownunresolved, knownresolved = pointers[p] |
44658
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
473 unresolved, resolved = parentpointers[i] |
44592
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
474 for r, c in unresolved.items(): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
475 if r in knownunresolved: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
476 # unresolved at both paths |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
477 pendingcnt[r] -= 1 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
478 assert pendingcnt[r] > 0 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
479 # take shorter chain |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
480 knownunresolved[r] = min(c, knownunresolved[r]) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
481 else: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
482 knownunresolved[r] = c |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
483 # simply propagate the 'resolved' set as deduplicating |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
484 # 'unresolved' here would be slightly complicated. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
485 knownresolved.update(resolved) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
486 else: |
44658
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
487 pointers[p] = parentpointers[i] |
44592
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
488 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
489 # then, populate the active parents directly and add the current |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
490 # 'rev' to the tracking pointers of the inactive parents. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
491 # 'pointers[p]' may be optimized out if both parents are active. |
44659
67f757ed86e0
dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents:
44658
diff
changeset
|
492 chaincodes = [b''] if len(parentrevs) <= 1 else [b'1', b'2'] |
44592
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
493 if curactive and bothparentsactive: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
494 for i, p in enumerate(parentrevs): |
44659
67f757ed86e0
dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents:
44658
diff
changeset
|
495 c = chaincodes[i] |
44592
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
496 parents[rev].append((c, p)) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
497 # no need to mark 'rev' as resolved since the 'rev' should |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
498 # be fully resolved (i.e. pendingcnt[rev] == 0) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
499 assert pendingcnt[rev] == 0 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
500 elif curactive: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
501 for i, p in enumerate(parentrevs): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
502 unresolved, resolved = pointers[p] |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
503 assert rev not in unresolved |
44659
67f757ed86e0
dagop: fix subsetparentswalker to set p1/p2 chains at merge revision
Yuya Nishihara <yuya@tcha.org>
parents:
44658
diff
changeset
|
504 c = chaincodes[i] |
44592
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
505 if p in subset: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
506 parents[rev].append((c, p)) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
507 # mark 'rev' as resolved through this path |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
508 resolved.add(rev) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
509 else: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
510 pendingcnt[rev] += 1 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
511 unresolved[rev] = c |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
512 assert 0 < pendingcnt[rev] <= 2 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
513 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
514 |
42446
055c3e2c44f0
revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents:
42445
diff
changeset
|
515 def _reachablerootspure(pfunc, minroot, roots, heads, includepath): |
055c3e2c44f0
revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents:
42445
diff
changeset
|
516 """See revlog.reachableroots""" |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
517 if not roots: |
26094
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
518 return [] |
26053
b68c9d232db6
reachableroots: use internal "revstates" array to test if rev is a root
Yuya Nishihara <yuya@tcha.org>
parents:
26006
diff
changeset
|
519 roots = set(roots) |
22487
e40bb83d0989
revset: stop using a baseset instead of a plain list in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
22483
diff
changeset
|
520 visit = list(heads) |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
521 reachable = set() |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
522 seen = {} |
25566
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
523 # prefetch all the things! (because python is slow) |
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
524 reached = reachable.add |
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
525 dovisit = visit.append |
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
526 nextvisit = visit.pop |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
527 # open-code the post-order traversal due to the tiny size of |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
528 # sys.getrecursionlimit() |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
529 while visit: |
25566
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
530 rev = nextvisit() |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
531 if rev in roots: |
25566
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
532 reached(rev) |
26002
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
533 if not includepath: |
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
534 continue |
42446
055c3e2c44f0
revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents:
42445
diff
changeset
|
535 parents = pfunc(rev) |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
536 seen[rev] = parents |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
537 for parent in parents: |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
538 if parent >= minroot and parent not in seen: |
25566
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
539 dovisit(parent) |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
540 if not reachable: |
22802
1fcd361efaf4
baseset: use default value instead of [] when possible
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
22801
diff
changeset
|
541 return baseset() |
26002
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
542 if not includepath: |
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
543 return reachable |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
544 for rev in sorted(seen): |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
545 for parent in seen[rev]: |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
546 if parent in reachable: |
25566
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
547 reached(rev) |
26091
60bbd4f9abd1
reachableroots: sort the smartset in the pure version too
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
26060
diff
changeset
|
548 return reachable |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
549 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
550 |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
551 def reachableroots(repo, roots, heads, includepath=False): |
42446
055c3e2c44f0
revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents:
42445
diff
changeset
|
552 """See revlog.reachableroots""" |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
553 if not roots: |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
554 return baseset() |
26093
204131131766
reachableroots: use smartset min
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
26091
diff
changeset
|
555 minroot = roots.min() |
26053
b68c9d232db6
reachableroots: use internal "revstates" array to test if rev is a root
Yuya Nishihara <yuya@tcha.org>
parents:
26006
diff
changeset
|
556 roots = list(roots) |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
557 heads = list(heads) |
42446
055c3e2c44f0
revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents:
42445
diff
changeset
|
558 revs = repo.changelog.reachableroots(minroot, heads, roots, includepath) |
26094
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
559 revs = baseset(revs) |
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
560 revs.sort() |
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
561 return revs |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
562 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
563 |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
564 def _changesrange(fctx1, fctx2, linerange2, diffopts): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
565 """Return `(diffinrange, linerange1)` where `diffinrange` is True |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
566 if diff from fctx2 to fctx1 has changes in linerange2 and |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
567 `linerange1` is the new line range for fctx1. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
568 """ |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
569 blocks = mdiff.allblocks(fctx1.data(), fctx2.data(), diffopts) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
570 filteredblocks, linerange1 = mdiff.blocksinrange(blocks, linerange2) |
43077
687b865b95ad
formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents:
43076
diff
changeset
|
571 diffinrange = any(stype == b'!' for _, stype in filteredblocks) |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
572 return diffinrange, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
573 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
574 |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
575 def blockancestors(fctx, fromline, toline, followfirst=False): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
576 """Yield ancestors of `fctx` with respect to the block of lines within |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
577 `fromline`-`toline` range. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
578 """ |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
579 diffopts = patch.diffopts(fctx._repo.ui) |
35271
d90c534099b1
filectx: extract helper method to obtain filectx pointing to its introrev
Yuya Nishihara <yuya@tcha.org>
parents:
35270
diff
changeset
|
580 fctx = fctx.introfilectx() |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
581 visit = {(fctx.linkrev(), fctx.filenode()): (fctx, (fromline, toline))} |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
582 while visit: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
583 c, linerange2 = visit.pop(max(visit)) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
584 pl = c.parents() |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
585 if followfirst: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
586 pl = pl[:1] |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
587 if not pl: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
588 # The block originates from the initial revision. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
589 yield c, linerange2 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
590 continue |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
591 inrange = False |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
592 for p in pl: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
593 inrangep, linerange1 = _changesrange(p, c, linerange2, diffopts) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
594 inrange = inrange or inrangep |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
595 if linerange1[0] == linerange1[1]: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
596 # Parent's linerange is empty, meaning that the block got |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
597 # introduced in this revision; no need to go futher in this |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
598 # branch. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
599 continue |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
600 # Set _descendantrev with 'c' (a known descendant) so that, when |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
601 # _adjustlinkrev is called for 'p', it receives this descendant |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
602 # (as srcrev) instead possibly topmost introrev. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
603 p._descendantrev = c.rev() |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
604 visit[p.linkrev(), p.filenode()] = p, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
605 if inrange: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
606 yield c, linerange2 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
607 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
608 |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
609 def blockdescendants(fctx, fromline, toline): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
610 """Yield descendants of `fctx` with respect to the block of lines within |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
611 `fromline`-`toline` range. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
612 """ |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
613 # First possibly yield 'fctx' if it has changes in range with respect to |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
614 # its parents. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
615 try: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
616 c, linerange1 = next(blockancestors(fctx, fromline, toline)) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
617 except StopIteration: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
618 pass |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
619 else: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
620 if c == fctx: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
621 yield c, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
622 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
623 diffopts = patch.diffopts(fctx._repo.ui) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
624 fl = fctx.filelog() |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
625 seen = {fctx.filerev(): (fctx, (fromline, toline))} |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
626 for i in fl.descendants([fctx.filerev()]): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
627 c = fctx.filectx(i) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
628 inrange = False |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
629 for x in fl.parentrevs(i): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
630 try: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
631 p, linerange2 = seen[x] |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
632 except KeyError: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
633 # nullrev or other branch |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
634 continue |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
635 inrangep, linerange1 = _changesrange(c, p, linerange2, diffopts) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
636 inrange = inrange or inrangep |
33284
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33080
diff
changeset
|
637 # If revision 'i' has been seen (it's a merge) and the line range |
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33080
diff
changeset
|
638 # previously computed differs from the one we just got, we take the |
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33080
diff
changeset
|
639 # surrounding interval. This is conservative but avoids loosing |
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33080
diff
changeset
|
640 # information. |
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33080
diff
changeset
|
641 if i in seen and seen[i][1] != linerange1: |
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33080
diff
changeset
|
642 lbs, ubs = zip(linerange1, seen[i][1]) |
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33080
diff
changeset
|
643 linerange1 = min(lbs), max(ubs) |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
644 seen[i] = c, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
645 if inrange: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
646 yield c, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
647 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
648 |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
649 @attr.s(slots=True, frozen=True) |
48946
642e31cb55f0
py3: use class X: instead of class X(object):
Gregory Szorc <gregory.szorc@gmail.com>
parents:
48875
diff
changeset
|
650 class annotateline: |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
651 fctx = attr.ib() |
37065
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
652 lineno = attr.ib() |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
653 # Whether this annotation was the result of a skip-annotate. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
654 skip = attr.ib(default=False) |
37066
b33b91ca2ec2
annotate: pack line content into annotateline object (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37065
diff
changeset
|
655 text = attr.ib(default=None) |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
656 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
657 |
37064
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
658 @attr.s(slots=True, frozen=True) |
48946
642e31cb55f0
py3: use class X: instead of class X(object):
Gregory Szorc <gregory.szorc@gmail.com>
parents:
48875
diff
changeset
|
659 class _annotatedfile: |
37064
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
660 # list indexed by lineno - 1 |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
661 fctxs = attr.ib() |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
662 linenos = attr.ib() |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
663 skips = attr.ib() |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
664 # full file content |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
665 text = attr.ib() |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
666 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
667 |
36919
8fba319750c2
dagop: move lines() out of annotate()
Yuya Nishihara <yuya@tcha.org>
parents:
36918
diff
changeset
|
668 def _countlines(text): |
43077
687b865b95ad
formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents:
43076
diff
changeset
|
669 if text.endswith(b"\n"): |
687b865b95ad
formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents:
43076
diff
changeset
|
670 return text.count(b"\n") |
687b865b95ad
formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents:
43076
diff
changeset
|
671 return text.count(b"\n") + int(bool(text)) |
36919
8fba319750c2
dagop: move lines() out of annotate()
Yuya Nishihara <yuya@tcha.org>
parents:
36918
diff
changeset
|
672 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
673 |
37065
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
674 def _decoratelines(text, fctx): |
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
675 n = _countlines(text) |
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
676 linenos = pycompat.rangelist(1, n + 1) |
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
677 return _annotatedfile([fctx] * n, linenos, [False] * n, text) |
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
678 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
679 |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
680 def _annotatepair(parents, childfctx, child, skipchild, diffopts): |
45942
89a2afe31e82
formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents:
45416
diff
changeset
|
681 r""" |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
682 Given parent and child fctxes and annotate data for parents, for all lines |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
683 in either parent that match the child, annotate the child with the parent's |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
684 data. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
685 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
686 Additionally, if `skipchild` is True, replace all other lines with parent |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
687 annotate data as well such that child is never blamed for any lines. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
688 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
689 See test-annotate.py for unit tests. |
45942
89a2afe31e82
formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents:
45416
diff
changeset
|
690 """ |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
691 pblocks = [ |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
692 (parent, mdiff.allblocks(parent.text, child.text, opts=diffopts)) |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
693 for parent in parents |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
694 ] |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
695 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
696 if skipchild: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
697 # Need to iterate over the blocks twice -- make it a list |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
698 pblocks = [(p, list(blocks)) for (p, blocks) in pblocks] |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
699 # Mercurial currently prefers p2 over p1 for annotate. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
700 # TODO: change this? |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
701 for parent, blocks in pblocks: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
702 for (a1, a2, b1, b2), t in blocks: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
703 # Changed blocks ('!') or blocks made only of blank lines ('~') |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
704 # belong to the child. |
43077
687b865b95ad
formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents:
43076
diff
changeset
|
705 if t == b'=': |
37064
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
706 child.fctxs[b1:b2] = parent.fctxs[a1:a2] |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
707 child.linenos[b1:b2] = parent.linenos[a1:a2] |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
708 child.skips[b1:b2] = parent.skips[a1:a2] |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
709 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
710 if skipchild: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
711 # Now try and match up anything that couldn't be matched, |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
712 # Reversing pblocks maintains bias towards p2, matching above |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
713 # behavior. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
714 pblocks.reverse() |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
715 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
716 # The heuristics are: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
717 # * Work on blocks of changed lines (effectively diff hunks with -U0). |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
718 # This could potentially be smarter but works well enough. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
719 # * For a non-matching section, do a best-effort fit. Match lines in |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
720 # diff hunks 1:1, dropping lines as necessary. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
721 # * Repeat the last line as a last resort. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
722 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
723 # First, replace as much as possible without repeating the last line. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
724 remaining = [(parent, []) for parent, _blocks in pblocks] |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
725 for idx, (parent, blocks) in enumerate(pblocks): |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
726 for (a1, a2, b1, b2), _t in blocks: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
727 if a2 - a1 >= b2 - b1: |
49284
d44e3c45f0e4
py3: replace `pycompat.xrange` by `range`
Manuel Jacob <me@manueljacob.de>
parents:
48946
diff
changeset
|
728 for bk in range(b1, b2): |
37064
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
729 if child.fctxs[bk] == childfctx: |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
730 ak = min(a1 + (bk - b1), a2 - 1) |
37064
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
731 child.fctxs[bk] = parent.fctxs[ak] |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
732 child.linenos[bk] = parent.linenos[ak] |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
733 child.skips[bk] = True |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
734 else: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
735 remaining[idx][1].append((a1, a2, b1, b2)) |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
736 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
737 # Then, look at anything left, which might involve repeating the last |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
738 # line. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
739 for parent, blocks in remaining: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
740 for a1, a2, b1, b2 in blocks: |
49284
d44e3c45f0e4
py3: replace `pycompat.xrange` by `range`
Manuel Jacob <me@manueljacob.de>
parents:
48946
diff
changeset
|
741 for bk in range(b1, b2): |
37064
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
742 if child.fctxs[bk] == childfctx: |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
743 ak = min(a1 + (bk - b1), a2 - 1) |
37064
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
744 child.fctxs[bk] = parent.fctxs[ak] |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
745 child.linenos[bk] = parent.linenos[ak] |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
746 child.skips[bk] = True |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
747 return child |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
748 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
749 |
37065
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
750 def annotate(base, parents, skiprevs=None, diffopts=None): |
36918
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
751 """Core algorithm for filectx.annotate() |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
752 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
753 `parents(fctx)` is a function returning a list of parent filectxs. |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
754 """ |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
755 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
756 # This algorithm would prefer to be recursive, but Python is a |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
757 # bit recursion-hostile. Instead we do an iterative |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
758 # depth-first search. |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
759 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
760 # 1st DFS pre-calculates pcache and needed |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
761 visit = [base] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
762 pcache = {} |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
763 needed = {base: 1} |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
764 while visit: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
765 f = visit.pop() |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
766 if f in pcache: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
767 continue |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
768 pl = parents(f) |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
769 pcache[f] = pl |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
770 for p in pl: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
771 needed[p] = needed.get(p, 0) + 1 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
772 if p not in pcache: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
773 visit.append(p) |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
774 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
775 # 2nd DFS does the actual annotate |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
776 visit[:] = [base] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
777 hist = {} |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
778 while visit: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
779 f = visit[-1] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
780 if f in hist: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
781 visit.pop() |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
782 continue |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
783 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
784 ready = True |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
785 pl = pcache[f] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
786 for p in pl: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
787 if p not in hist: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
788 ready = False |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
789 visit.append(p) |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
790 if ready: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
791 visit.pop() |
37065
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
792 curr = _decoratelines(f.data(), f) |
36918
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
793 skipchild = False |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
794 if skiprevs is not None: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
795 skipchild = f._changeid in skiprevs |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
796 curr = _annotatepair( |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
797 [hist[p] for p in pl], f, curr, skipchild, diffopts |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
798 ) |
36918
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
799 for p in pl: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
800 if needed[p] == 1: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
801 del hist[p] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
802 del needed[p] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
803 else: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
804 needed[p] -= 1 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
805 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
806 hist[f] = curr |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
807 del pcache[f] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
808 |
37064
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
809 a = hist[base] |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
810 return [ |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
811 annotateline(*r) |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
812 for r in zip(a.fctxs, a.linenos, a.skips, mdiff.splitnewlines(a.text)) |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
813 ] |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
814 |
36918
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
815 |
32903
27932a76a88d
dagop: split module hosting DAG-related algorithms from revset
Yuya Nishihara <yuya@tcha.org>
parents:
32885
diff
changeset
|
816 def toposort(revs, parentsfunc, firstbranch=()): |
29347
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
817 """Yield revisions from heads to roots one (topo) branch at a time. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
818 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
819 This function aims to be used by a graph generator that wishes to minimize |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
820 the number of parallel branches and their interleaving. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
821 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
822 Example iteration order (numbers show the "true" order in a changelog): |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
823 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
824 o 4 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
825 | |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
826 o 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
827 | |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
828 | o 3 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
829 | | |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
830 | o 2 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
831 |/ |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
832 o 0 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
833 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
834 Note that the ancestors of merges are understood by the current |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
835 algorithm to be on the same branch. This means no reordering will |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
836 occur behind a merge. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
837 """ |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
838 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
839 ### Quick summary of the algorithm |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
840 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
841 # This function is based around a "retention" principle. We keep revisions |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
842 # in memory until we are ready to emit a whole branch that immediately |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
843 # "merges" into an existing one. This reduces the number of parallel |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
844 # branches with interleaved revisions. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
845 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
846 # During iteration revs are split into two groups: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
847 # A) revision already emitted |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
848 # B) revision in "retention". They are stored as different subgroups. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
849 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
850 # for each REV, we do the following logic: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
851 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
852 # 1) if REV is a parent of (A), we will emit it. If there is a |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
853 # retention group ((B) above) that is blocked on REV being |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
854 # available, we emit all the revisions out of that retention |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
855 # group first. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
856 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
857 # 2) else, we'll search for a subgroup in (B) awaiting for REV to be |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
858 # available, if such subgroup exist, we add REV to it and the subgroup is |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
859 # now awaiting for REV.parents() to be available. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
860 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
861 # 3) finally if no such group existed in (B), we create a new subgroup. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
862 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
863 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
864 # To bootstrap the algorithm, we emit the tipmost revision (which |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
865 # puts it in group (A) from above). |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
866 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
867 revs.sort(reverse=True) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
868 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
869 # Set of parents of revision that have been emitted. They can be considered |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
870 # unblocked as the graph generator is already aware of them so there is no |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
871 # need to delay the revisions that reference them. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
872 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
873 # If someone wants to prioritize a branch over the others, pre-filling this |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
874 # set will force all other branches to wait until this branch is ready to be |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
875 # emitted. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
876 unblocked = set(firstbranch) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
877 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
878 # list of groups waiting to be displayed, each group is defined by: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
879 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
880 # (revs: lists of revs waiting to be displayed, |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
881 # blocked: set of that cannot be displayed before those in 'revs') |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
882 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
883 # The second value ('blocked') correspond to parents of any revision in the |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
884 # group ('revs') that is not itself contained in the group. The main idea |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
885 # of this algorithm is to delay as much as possible the emission of any |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
886 # revision. This means waiting for the moment we are about to display |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
887 # these parents to display the revs in a group. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
888 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
889 # This first implementation is smart until it encounters a merge: it will |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
890 # emit revs as soon as any parent is about to be emitted and can grow an |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
891 # arbitrary number of revs in 'blocked'. In practice this mean we properly |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
892 # retains new branches but gives up on any special ordering for ancestors |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
893 # of merges. The implementation can be improved to handle this better. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
894 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
895 # The first subgroup is special. It corresponds to all the revision that |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
896 # were already emitted. The 'revs' lists is expected to be empty and the |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
897 # 'blocked' set contains the parents revisions of already emitted revision. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
898 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
899 # You could pre-seed the <parents> set of groups[0] to a specific |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
900 # changesets to select what the first emitted branch should be. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
901 groups = [([], unblocked)] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
902 pendingheap = [] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
903 pendingset = set() |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
904 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
905 heapq.heapify(pendingheap) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
906 heappop = heapq.heappop |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
907 heappush = heapq.heappush |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
908 for currentrev in revs: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
909 # Heap works with smallest element, we want highest so we invert |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
910 if currentrev not in pendingset: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
911 heappush(pendingheap, -currentrev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
912 pendingset.add(currentrev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
913 # iterates on pending rev until after the current rev have been |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
914 # processed. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
915 rev = None |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
916 while rev != currentrev: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
917 rev = -heappop(pendingheap) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
918 pendingset.remove(rev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
919 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
920 # Seek for a subgroup blocked, waiting for the current revision. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
921 matching = [i for i, g in enumerate(groups) if rev in g[1]] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
922 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
923 if matching: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
924 # The main idea is to gather together all sets that are blocked |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
925 # on the same revision. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
926 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
927 # Groups are merged when a common blocking ancestor is |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
928 # observed. For example, given two groups: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
929 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
930 # revs [5, 4] waiting for 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
931 # revs [3, 2] waiting for 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
932 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
933 # These two groups will be merged when we process |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
934 # 1. In theory, we could have merged the groups when |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
935 # we added 2 to the group it is now in (we could have |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
936 # noticed the groups were both blocked on 1 then), but |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
937 # the way it works now makes the algorithm simpler. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
938 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
939 # We also always keep the oldest subgroup first. We can |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
940 # probably improve the behavior by having the longest set |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
941 # first. That way, graph algorithms could minimise the length |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
942 # of parallel lines their drawing. This is currently not done. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
943 targetidx = matching.pop(0) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
944 trevs, tparents = groups[targetidx] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
945 for i in matching: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
946 gr = groups[i] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
947 trevs.extend(gr[0]) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
948 tparents |= gr[1] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
949 # delete all merged subgroups (except the one we kept) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
950 # (starting from the last subgroup for performance and |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
951 # sanity reasons) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
952 for i in reversed(matching): |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
953 del groups[i] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
954 else: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
955 # This is a new head. We create a new subgroup for it. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
956 targetidx = len(groups) |
32291
bd872f64a8ba
cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents:
32085
diff
changeset
|
957 groups.append(([], {rev})) |
29347
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
958 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
959 gr = groups[targetidx] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
960 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
961 # We now add the current nodes to this subgroups. This is done |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
962 # after the subgroup merging because all elements from a subgroup |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
963 # that relied on this rev must precede it. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
964 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
965 # we also update the <parents> set to include the parents of the |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
966 # new nodes. |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
967 if rev == currentrev: # only display stuff in rev |
29347
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
968 gr[0].append(rev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
969 gr[1].remove(rev) |
46113
59fa3890d40a
node: import symbols explicitly
Joerg Sonnenberger <joerg@bec.de>
parents:
45942
diff
changeset
|
970 parents = [p for p in parentsfunc(rev) if p > nullrev] |
29347
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
971 gr[1].update(parents) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
972 for p in parents: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
973 if p not in pendingset: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
974 pendingset.add(p) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
975 heappush(pendingheap, -p) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
976 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
977 # Look for a subgroup to display |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
978 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
979 # When unblocked is empty (if clause), we were not waiting for any |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
980 # revisions during the first iteration (if no priority was given) or |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
981 # if we emitted a whole disconnected set of the graph (reached a |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
982 # root). In that case we arbitrarily take the oldest known |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
983 # subgroup. The heuristic could probably be better. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
984 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
985 # Otherwise (elif clause) if the subgroup is blocked on |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
986 # a revision we just emitted, we can safely emit it as |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
987 # well. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
988 if not unblocked: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
989 if len(groups) > 1: # display other subset |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
990 targetidx = 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
991 gr = groups[1] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
992 elif not gr[1] & unblocked: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
993 gr = None |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
994 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
995 if gr is not None: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
996 # update the set of awaited revisions with the one from the |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
997 # subgroup |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
998 unblocked |= gr[1] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
999 # output all revisions in the subgroup |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1000 for r in gr[0]: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1001 yield r |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1002 # delete the subgroup that you just output |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1003 # unless it is groups[0] in which case you just empty it. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1004 if targetidx: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1005 del groups[targetidx] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1006 else: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1007 gr[0][:] = [] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1008 # Check if we have some subgroup waiting for revisions we are not going to |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1009 # iterate over |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1010 for g in groups: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1011 for r in g[0]: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1012 yield r |
39179
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1013 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
1014 |
39179
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1015 def headrevs(revs, parentsfn): |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1016 """Resolve the set of heads from a set of revisions. |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1017 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1018 Receives an iterable of revision numbers and a callbable that receives a |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1019 revision number and returns an iterable of parent revision numbers, possibly |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1020 including nullrev. |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1021 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1022 Returns a set of revision numbers that are DAG heads within the passed |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1023 subset. |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1024 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1025 ``nullrev`` is never included in the returned set, even if it is provided in |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1026 the input set. |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1027 """ |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1028 headrevs = set(revs) |
46113
59fa3890d40a
node: import symbols explicitly
Joerg Sonnenberger <joerg@bec.de>
parents:
45942
diff
changeset
|
1029 parents = {nullrev} |
41277
61f9ef23a12f
dagop: minor python optimization to `headrevs`
Boris Feld <boris.feld@octobus.net>
parents:
40000
diff
changeset
|
1030 up = parents.update |
39179
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1031 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1032 for rev in revs: |
41277
61f9ef23a12f
dagop: minor python optimization to `headrevs`
Boris Feld <boris.feld@octobus.net>
parents:
40000
diff
changeset
|
1033 up(parentsfn(rev)) |
61f9ef23a12f
dagop: minor python optimization to `headrevs`
Boris Feld <boris.feld@octobus.net>
parents:
40000
diff
changeset
|
1034 headrevs.difference_update(parents) |
39179
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1035 return headrevs |
39181
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1036 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
1037 |
51395
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1038 def headrevsdiff(parentsfn, start, stop): |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1039 """Compute how the set of heads changed between |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1040 revisions `start-1` and `stop-1`. |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1041 """ |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1042 parents = set() |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1043 |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1044 heads_added = set() |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1045 heads_removed = set() |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1046 |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1047 for rev in range(stop - 1, start - 1, -1): |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1048 if rev in parents: |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1049 parents.remove(rev) |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1050 else: |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1051 heads_added.add(rev) |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1052 for p in parentsfn(rev): |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1053 parents.add(p) |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1054 |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1055 # now `parents` is the collection of candidate removed heads |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1056 rev = start - 1 |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1057 while parents: |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1058 if rev in parents: |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1059 heads_removed.add(rev) |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1060 parents.remove(rev) |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1061 |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1062 for p in parentsfn(rev): |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1063 parents.discard(p) |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1064 rev = rev - 1 |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1065 |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1066 return (heads_removed, heads_added) |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1067 |
a0d88b021a98
unbundle: faster computation of changed heads
Arseniy Alekseyev <aalekseyev@janestreet.com>
parents:
49284
diff
changeset
|
1068 |
40000
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1069 def headrevssubset(revsfn, parentrevsfn, startrev=None, stoprevs=None): |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1070 """Returns the set of all revs that have no children with control. |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1071 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1072 ``revsfn`` is a callable that with no arguments returns an iterator over |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1073 all revision numbers in topological order. With a ``start`` argument, it |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1074 returns revision numbers starting at that number. |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1075 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1076 ``parentrevsfn`` is a callable receiving a revision number and returns an |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1077 iterable of parent revision numbers, where values can include nullrev. |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1078 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1079 ``startrev`` is a revision number at which to start the search. |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1080 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1081 ``stoprevs`` is an iterable of revision numbers that, when encountered, |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1082 will stop DAG traversal beyond them. Parents of revisions in this |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1083 collection will be heads. |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1084 """ |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1085 if startrev is None: |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1086 startrev = nullrev |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1087 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1088 stoprevs = set(stoprevs or []) |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1089 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1090 reachable = {startrev} |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1091 heads = {startrev} |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1092 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1093 for rev in revsfn(start=startrev + 1): |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1094 for prev in parentrevsfn(rev): |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1095 if prev in reachable: |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1096 if rev not in stoprevs: |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1097 reachable.add(rev) |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1098 heads.add(rev) |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1099 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1100 if prev in heads and prev not in stoprevs: |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1101 heads.remove(prev) |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1102 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1103 return heads |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1104 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
1105 |
39181
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1106 def linearize(revs, parentsfn): |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1107 """Linearize and topologically sort a list of revisions. |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1108 |
39607
5362c96f2feb
dagop: fix typo spotted while doing unrelated investigation
Augie Fackler <augie@google.com>
parents:
39181
diff
changeset
|
1109 The linearization process tries to create long runs of revs where a child |
39181
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1110 rev comes immediately after its first parent. This is done by visiting the |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1111 heads of the revs in inverse topological order, and for each visited rev, |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1112 visiting its second parent, then its first parent, then adding the rev |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1113 itself to the output list. |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1114 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1115 Returns a list of revision numbers. |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1116 """ |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1117 visit = list(sorted(headrevs(revs, parentsfn), reverse=True)) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1118 finished = set() |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1119 result = [] |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1120 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1121 while visit: |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1122 rev = visit.pop() |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1123 if rev < 0: |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1124 rev = -rev - 1 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1125 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1126 if rev not in finished: |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1127 result.append(rev) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1128 finished.add(rev) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1129 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1130 else: |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1131 visit.append(-rev - 1) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1132 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1133 for prev in parentsfn(rev): |
46113
59fa3890d40a
node: import symbols explicitly
Joerg Sonnenberger <joerg@bec.de>
parents:
45942
diff
changeset
|
1134 if prev == nullrev or prev not in revs or prev in finished: |
39181
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1135 continue |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1136 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1137 visit.append(prev) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1138 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1139 assert len(result) == len(revs) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1140 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1141 return result |