Mercurial > hg
annotate mercurial/dagop.py @ 48694:5c940f9ba3e4
dagop: don't import nullrev from .node twice
See 59fa3890d40a.
Differential Revision: https://phab.mercurial-scm.org/D12120
author | Anton Shestakov <av6@dwimlabs.net> |
---|---|
date | Mon, 31 Jan 2022 18:04:11 +0300 |
parents | d4ba4d51f85f |
children | 6000f5b25c9b |
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 from __future__ import absolute_import |
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
9 |
20690
13c0327eeb6f
revset: changed ancestors revset to return lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents:
20659
diff
changeset
|
10 import heapq |
25971
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
11 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
12 from .thirdparty import attr |
46113
59fa3890d40a
node: import symbols explicitly
Joerg Sonnenberger <joerg@bec.de>
parents:
45942
diff
changeset
|
13 from .node import nullrev |
25971
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
14 from . import ( |
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
15 error, |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
16 mdiff, |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
17 patch, |
36918
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
18 pycompat, |
45416
4ebc5f325bed
log: fix crash and bad filematcher lookup by -fr'wdir()' PATH
Yuya Nishihara <yuya@tcha.org>
parents:
44659
diff
changeset
|
19 scmutil, |
30881
1be65deb3d54
smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
30850
diff
changeset
|
20 smartset, |
25971
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
21 ) |
11275 | 22 |
30881
1be65deb3d54
smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
30850
diff
changeset
|
23 baseset = smartset.baseset |
1be65deb3d54
smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
30850
diff
changeset
|
24 generatorset = smartset.generatorset |
1be65deb3d54
smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
30850
diff
changeset
|
25 |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
26 # possible maximum depth between null and wdir() |
41359
431cf2c8c839
revset: support ranges in #generations relation
Anton Shestakov <av6@dwimlabs.net>
parents:
41277
diff
changeset
|
27 maxlogdepth = 0x80000000 |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
28 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
29 |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
30 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
|
31 """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
|
32 |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
33 '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
|
34 if 'reverse' is True/False respectively. |
33078
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
35 |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
36 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
|
37 earlier than the startdepth are omitted. |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
38 """ |
33003
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
39 if startdepth is None: |
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
40 startdepth = 0 |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
41 if stopdepth is None: |
41359
431cf2c8c839
revset: support ranges in #generations relation
Anton Shestakov <av6@dwimlabs.net>
parents:
41277
diff
changeset
|
42 stopdepth = maxlogdepth |
33027
a10f5f6771f6
dagop: raise ProgrammingError if stopdepth < 0
Martin von Zweigbergk <martinvonz@google.com>
parents:
33003
diff
changeset
|
43 if stopdepth == 0: |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
44 return |
33027
a10f5f6771f6
dagop: raise ProgrammingError if stopdepth < 0
Martin von Zweigbergk <martinvonz@google.com>
parents:
33003
diff
changeset
|
45 if stopdepth < 0: |
43077
687b865b95ad
formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents:
43076
diff
changeset
|
46 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
|
47 if reverse: |
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
48 heapsign = -1 # max heap |
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
49 else: |
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
50 heapsign = +1 # min heap |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
51 |
32998
c7da57bbae96
dagop: comment why revancestors() doesn't heapify input revs at once
Yuya Nishihara <yuya@tcha.org>
parents:
32997
diff
changeset
|
52 # 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
|
53 # 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
|
54 revs.sort(reverse) |
32997
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
55 irevs = iter(revs) |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
56 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
|
57 |
32997
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
58 inputrev = next(irevs, None) |
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
59 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
|
60 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
|
61 |
33000
d3d36bcdf036
dagop: just compare with the last value to deduplicate input of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32999
diff
changeset
|
62 lastrev = None |
32999
08e2793d9f65
dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
32998
diff
changeset
|
63 while pendingheap: |
33001
92d0945a15e0
dagop: compute depth in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33000
diff
changeset
|
64 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
|
65 currev = heapsign * currev |
32999
08e2793d9f65
dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
32998
diff
changeset
|
66 if currev == inputrev: |
32997
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
67 inputrev = next(irevs, None) |
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
68 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
|
69 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
|
70 # 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
|
71 # 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
|
72 foundnew = currev != lastrev |
33003
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
73 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
|
74 lastrev = currev |
32999
08e2793d9f65
dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
32998
diff
changeset
|
75 yield currev |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
76 pdepth = curdepth + 1 |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
77 if foundnew and pdepth < stopdepth: |
33077
58ebb38456e0
dagop: factor out pfunc from revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33076
diff
changeset
|
78 for prev in pfunc(currev): |
46113
59fa3890d40a
node: import symbols explicitly
Joerg Sonnenberger <joerg@bec.de>
parents:
45942
diff
changeset
|
79 if prev != nullrev: |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
80 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
|
81 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
82 |
35276
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35275
diff
changeset
|
83 def filectxancestors(fctxs, followfirst=False): |
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35275
diff
changeset
|
84 """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
|
85 and includes the given fctxs themselves |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
86 |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
87 Yields (rev, {fctx, ...}) pairs in descending order. |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
88 """ |
35270
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
89 visit = {} |
35297
c9144396099b
dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35296
diff
changeset
|
90 visitheap = [] |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
91 |
35274
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35273
diff
changeset
|
92 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
|
93 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
|
94 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
|
95 visit[rev] = set() |
35297
c9144396099b
dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35296
diff
changeset
|
96 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
|
97 visit[rev].add(fctx) |
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35273
diff
changeset
|
98 |
35270
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
99 if followfirst: |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
100 cut = 1 |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
101 else: |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
102 cut = None |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
103 |
35276
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35275
diff
changeset
|
104 for c in fctxs: |
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35275
diff
changeset
|
105 addvisit(c) |
35275
b4b328ea6175
dagop: put start fctx into visit dict of filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35274
diff
changeset
|
106 while visit: |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
107 currev = -(heapq.heappop(visitheap)) |
35296
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
108 curfctxs = visit.pop(currev) |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
109 yield currev, curfctxs |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
110 for c in curfctxs: |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
111 for parent in c.parents()[:cut]: |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
112 addvisit(parent) |
35297
c9144396099b
dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35296
diff
changeset
|
113 assert not visitheap |
35296
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
114 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
115 |
35296
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
116 def filerevancestors(fctxs, followfirst=False): |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
117 """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
|
118 and includes the given fctxs themselves |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
119 |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
120 Returns a smartset. |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
121 """ |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
122 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
|
123 return generatorset(gen, iterasc=False) |
35270
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
124 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
125 |
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
126 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
|
127 if followfirst: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
128 cut = 1 |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
129 else: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
130 cut = None |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
131 cl = repo.changelog |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
132 |
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
133 def plainpfunc(rev): |
33078
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
134 try: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
135 return cl.parentrevs(rev)[:cut] |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
136 except error.WdirUnsupported: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
137 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
|
138 |
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
139 if cutfunc is None: |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
140 pfunc = plainpfunc |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
141 else: |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
142 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
|
143 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
|
144 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
|
145 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
146 |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
147 def revancestors( |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
148 repo, revs, followfirst=False, startdepth=None, stopdepth=None, cutfunc=None |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
149 ): |
41533
0f64091cc851
global: make some docstrings raw strings
Gregory Szorc <gregory.szorc@gmail.com>
parents:
41389
diff
changeset
|
150 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
|
151 the given revs themselves, and returns a smartset |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
152 |
33003
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
153 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
|
154 earlier than the startdepth are omitted. |
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
155 |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
156 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
|
157 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
|
158 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
|
159 optimization sometimes. |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
160 |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
161 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
|
162 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
|
163 return True in this case. For example, |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
164 |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
165 D # revancestors(repo, D, cutfunc=lambda rev: rev == B) |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
166 |\ # 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
|
167 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
|
168 |/ |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
169 A |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
170 """ |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
171 gen = _genrevancestors( |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
172 repo, revs, followfirst, startdepth, stopdepth, cutfunc |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
173 ) |
32997
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
174 return generatorset(gen, iterasc=False) |
16409
2cbd7dd0cc1f
graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents:
16402
diff
changeset
|
175 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
176 |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
177 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
|
178 if followfirst: |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
24219
diff
changeset
|
179 cut = 1 |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
24219
diff
changeset
|
180 else: |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
24219
diff
changeset
|
181 cut = None |
16409
2cbd7dd0cc1f
graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents:
16402
diff
changeset
|
182 |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
183 cl = repo.changelog |
33076
a76a64c78807
dagop: use smartset.min() in revdescendants() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33075
diff
changeset
|
184 first = revs.min() |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
185 if first == nullrev: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
186 # 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
|
187 # 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
|
188 yield first |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
189 for i in cl: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
190 yield i |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
191 else: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
192 seen = set(revs) |
33075
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
193 for i in cl.revs(first): |
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
194 if i in seen: |
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
195 yield i |
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
196 continue |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
197 for x in cl.parentrevs(i)[:cut]: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
198 if x != nullrev and x in seen: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
199 seen.add(i) |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
200 yield i |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
201 break |
20692
7af341082b76
revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents:
20691
diff
changeset
|
202 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
203 |
33080
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
204 def _builddescendantsmap(repo, startrev, followfirst): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
205 """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
|
206 cl = repo.changelog |
38783
e7aa113b14f7
global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents:
37066
diff
changeset
|
207 descmap = [[] for _rev in pycompat.xrange(startrev, len(cl))] |
33080
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
208 for currev in cl.revs(startrev + 1): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
209 p1rev, p2rev = cl.parentrevs(currev) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
210 if p1rev >= startrev: |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
211 descmap[p1rev - startrev].append(currev) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
212 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
|
213 descmap[p2rev - startrev].append(currev) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
214 return descmap |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
215 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
216 |
33080
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
217 def _genrevdescendantsofdepth(repo, revs, followfirst, startdepth, stopdepth): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
218 startrev = revs.min() |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
219 descmap = _builddescendantsmap(repo, startrev, followfirst) |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
220 |
33080
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
221 def pfunc(rev): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
222 return descmap[rev - startrev] |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
223 |
33080
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
224 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
|
225 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
226 |
33080
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
227 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
|
228 """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
|
229 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
|
230 |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
231 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
|
232 earlier than the startdepth are omitted. |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
233 """ |
41389
7e55ca658e4b
dagop: check if stopdepth is greater than or equal to maxlogdepth
Anton Shestakov <av6@dwimlabs.net>
parents:
41359
diff
changeset
|
234 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
|
235 gen = _genrevdescendants(repo, revs, followfirst) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
236 else: |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
237 gen = _genrevdescendantsofdepth( |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
238 repo, revs, followfirst, startdepth, stopdepth |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
239 ) |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
240 return generatorset(gen, iterasc=True) |
16409
2cbd7dd0cc1f
graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents:
16402
diff
changeset
|
241 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
242 |
39999
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
243 def descendantrevs(revs, revsfn, parentrevsfn): |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
244 """Generate revision number descendants in revision order. |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
245 |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
246 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
|
247 ``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
|
248 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
|
249 of itself. |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
250 |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
251 ``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
|
252 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
|
253 numbers beginning with that value. |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
254 |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
255 ``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
|
256 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
|
257 nullrev. |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
258 """ |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
259 first = min(revs) |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
260 |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
261 if first == nullrev: |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
262 for rev in revsfn(): |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
263 yield rev |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
264 return |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
265 |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
266 seen = set(revs) |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
267 for rev in revsfn(start=first + 1): |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
268 for prev in parentrevsfn(rev): |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
269 if prev != nullrev and prev in seen: |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
270 seen.add(rev) |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
271 yield rev |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
272 break |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39607
diff
changeset
|
273 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
274 |
44592
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
275 class subsetparentswalker(object): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
276 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
|
277 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
278 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
|
279 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
|
280 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
281 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
|
282 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
|
283 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
|
284 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
285 - d - e - |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
286 / \ |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
287 a - b - c - f |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
288 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
289 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
|
290 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
291 - d - e - |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
292 / \ |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
293 a - b -(c)- f |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
294 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
295 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
|
296 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
|
297 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
298 (d) (e) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
299 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
300 a - b - c - f |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
301 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
302 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
|
303 '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
|
304 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
|
305 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
|
306 the 'f' end is marked as resolved. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
307 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
308 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
|
309 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
|
310 space to ':startrev'. |
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 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
313 def __init__(self, repo, subset, startrev=None): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
314 if startrev is not None: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
315 subset = repo.revs(b'%d:null', startrev) & subset |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
316 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
317 # 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
|
318 # no such function. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
319 fastdesc = subset.fastdesc |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
320 if fastdesc: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
321 desciter = fastdesc() |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
322 else: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
323 if not subset.isdescending() and not subset.istopo(): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
324 subset = smartset.baseset(subset) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
325 subset.sort(reverse=True) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
326 desciter = iter(subset) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
327 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
328 self._repo = repo |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
329 self._changelog = repo.changelog |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
330 self._subset = subset |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
331 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
332 # scanning state (see _scanparents): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
333 self._tovisit = [] |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
334 self._pendingcnt = {} |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
335 self._pointers = {} |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
336 self._parents = {} |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
337 self._inputhead = nullrev # reassigned by self._advanceinput() |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
338 self._inputtail = desciter |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
339 self._bottomrev = nullrev |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
340 self._advanceinput() |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
341 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
342 def parentsset(self, rev): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
343 """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
|
344 as a smartset""" |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
345 return smartset.baseset(self.parents(rev)) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
346 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
347 def parents(self, rev): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
348 """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
|
349 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
350 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
|
351 """ |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
352 self._scanparents(rev) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
353 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
|
354 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
355 def _parentrevs(self, rev): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
356 try: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
357 revs = self._changelog.parentrevs(rev) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
358 if revs[-1] == nullrev: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
359 return revs[:-1] |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
360 return revs |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
361 except error.WdirUnsupported: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
362 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
|
363 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
364 def _advanceinput(self): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
365 """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
|
366 if self._inputhead < nullrev: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
367 return |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
368 try: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
369 self._inputhead = next(self._inputtail) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
370 except StopIteration: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
371 self._bottomrev = self._inputhead |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
372 self._inputhead = nullrev - 1 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
373 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
374 def _scanparents(self, stoprev): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
375 """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
|
376 resolved""" |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
377 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
378 # '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
|
379 # 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
|
380 # of computing the given subset. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
381 # |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
382 # For to-visit revisions, we keep track of |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
383 # - the number of the unresolved paths: pendingcnt[rev], |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
384 # - 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
|
385 # - 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
|
386 # |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
387 # 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
|
388 # propagated to its parents accordingly. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
389 # |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
390 # 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
|
391 # 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
|
392 # 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
|
393 # 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
|
394 # of merges between two revisions. |
44592
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
395 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
396 subset = self._subset |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
397 tovisit = self._tovisit # heap queue of [-rev] |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
398 pendingcnt = self._pendingcnt # {rev: count} for visited revisions |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
399 pointers = self._pointers # {rev: [{unresolved_rev: chain}, resolved]} |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
400 parents = self._parents # {rev: [(chain, rev)]} |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
401 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
402 while tovisit or self._inputhead >= nullrev: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
403 if pendingcnt.get(stoprev) == 0: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
404 return |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
405 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
406 # feed greater revisions from input set to queue |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
407 if not tovisit: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
408 heapq.heappush(tovisit, -self._inputhead) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
409 self._advanceinput() |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
410 while self._inputhead >= -tovisit[0]: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
411 heapq.heappush(tovisit, -self._inputhead) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
412 self._advanceinput() |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
413 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
414 rev = -heapq.heappop(tovisit) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
415 if rev < self._bottomrev: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
416 return |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
417 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
|
418 continue # already visited |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
419 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
420 curactive = rev in subset |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
421 pendingcnt.setdefault(rev, 0) # mark as visited |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
422 if curactive: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
423 assert rev not in parents |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
424 parents[rev] = [] |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
425 unresolved, resolved = pointers.pop(rev, ({}, set())) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
426 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
427 if curactive: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
428 # reached to active rev, resolve pending descendants' parents |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
429 for r, c in unresolved.items(): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
430 pendingcnt[r] -= 1 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
431 assert pendingcnt[r] >= 0 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
432 if r in resolved: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
433 continue # eliminate redundant path |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
434 parents[r].append((c, rev)) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
435 # 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
|
436 # 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
|
437 # be concatenated later at a fork revision. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
438 if pendingcnt[r] > 0: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
439 resolved.add(r) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
440 unresolved.clear() |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
441 # occasionally clean resolved markers. otherwise the set |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
442 # would grow indefinitely. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
443 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
|
444 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
445 parentrevs = self._parentrevs(rev) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
446 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
|
447 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
448 # set up or propagate tracking pointers if |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
449 # - one of the parents is not active, |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
450 # - or descendants' parents are unresolved. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
451 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
|
452 if len(parentrevs) <= 1: |
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
453 # can avoid copying the tracking pointer |
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
454 parentpointers = [(unresolved, resolved)] |
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
455 else: |
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
456 parentpointers = [ |
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
457 (unresolved, resolved), |
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
458 (unresolved.copy(), resolved.copy()), |
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
459 ] |
44592
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
460 # '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
|
461 # 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
|
462 # p1/p2 code to the existing chains. |
44592
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
463 for r in unresolved: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
464 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
|
465 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
|
466 parentpointers[1][0][r] += b'2' |
44592
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
467 for i, p in enumerate(parentrevs): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
468 assert p < rev |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
469 heapq.heappush(tovisit, -p) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
470 if p in pointers: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
471 # 'p' is a fork revision. concatenate tracking pointers |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
472 # and decrement the pending count accordingly. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
473 knownunresolved, knownresolved = pointers[p] |
44658
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
474 unresolved, resolved = parentpointers[i] |
44592
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
475 for r, c in unresolved.items(): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
476 if r in knownunresolved: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
477 # unresolved at both paths |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
478 pendingcnt[r] -= 1 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
479 assert pendingcnt[r] > 0 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
480 # take shorter chain |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
481 knownunresolved[r] = min(c, knownunresolved[r]) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
482 else: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
483 knownunresolved[r] = c |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
484 # simply propagate the 'resolved' set as deduplicating |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
485 # 'unresolved' here would be slightly complicated. |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
486 knownresolved.update(resolved) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
487 else: |
44658
25436f83fb95
dagop: simplify dict/set reuse condition in subsetparentswalker
Yuya Nishihara <yuya@tcha.org>
parents:
44592
diff
changeset
|
488 pointers[p] = parentpointers[i] |
44592
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
489 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
490 # 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
|
491 # '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
|
492 # '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
|
493 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
|
494 if curactive and bothparentsactive: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
495 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
|
496 c = chaincodes[i] |
44592
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
497 parents[rev].append((c, p)) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
498 # 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
|
499 # be fully resolved (i.e. pendingcnt[rev] == 0) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
500 assert pendingcnt[rev] == 0 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
501 elif curactive: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
502 for i, p in enumerate(parentrevs): |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
503 unresolved, resolved = pointers[p] |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
504 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
|
505 c = chaincodes[i] |
44592
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
506 if p in subset: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
507 parents[rev].append((c, p)) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
508 # mark 'rev' as resolved through this path |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
509 resolved.add(rev) |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
510 else: |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
511 pendingcnt[rev] += 1 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
512 unresolved[rev] = c |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
513 assert 0 < pendingcnt[rev] <= 2 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
514 |
7cd5c0968139
templater: add subsetparents(rev, revset) function
Yuya Nishihara <yuya@tcha.org>
parents:
43077
diff
changeset
|
515 |
42446
055c3e2c44f0
revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents:
42445
diff
changeset
|
516 def _reachablerootspure(pfunc, minroot, roots, heads, includepath): |
055c3e2c44f0
revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents:
42445
diff
changeset
|
517 """See revlog.reachableroots""" |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
518 if not roots: |
26094
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
519 return [] |
26053
b68c9d232db6
reachableroots: use internal "revstates" array to test if rev is a root
Yuya Nishihara <yuya@tcha.org>
parents:
26006
diff
changeset
|
520 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
|
521 visit = list(heads) |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
522 reachable = set() |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
523 seen = {} |
25566
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
524 # 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
|
525 reached = reachable.add |
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
526 dovisit = visit.append |
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
527 nextvisit = visit.pop |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
528 # 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
|
529 # sys.getrecursionlimit() |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
530 while visit: |
25566
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
531 rev = nextvisit() |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
532 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
|
533 reached(rev) |
26002
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
534 if not includepath: |
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
535 continue |
42446
055c3e2c44f0
revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents:
42445
diff
changeset
|
536 parents = pfunc(rev) |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
537 seen[rev] = parents |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
538 for parent in parents: |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
539 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
|
540 dovisit(parent) |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
541 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
|
542 return baseset() |
26002
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
543 if not includepath: |
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
544 return reachable |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
545 for rev in sorted(seen): |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
546 for parent in seen[rev]: |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
547 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
|
548 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
|
549 return reachable |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
550 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
551 |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
552 def reachableroots(repo, roots, heads, includepath=False): |
42446
055c3e2c44f0
revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents:
42445
diff
changeset
|
553 """See revlog.reachableroots""" |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
554 if not roots: |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
555 return baseset() |
26093
204131131766
reachableroots: use smartset min
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
26091
diff
changeset
|
556 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
|
557 roots = list(roots) |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
558 heads = list(heads) |
42446
055c3e2c44f0
revlog: speed up isancestor
Valentin Gatien-Baron <vgatien-baron@janestreet.com>
parents:
42445
diff
changeset
|
559 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
|
560 revs = baseset(revs) |
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
561 revs.sort() |
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
562 return revs |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
563 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
564 |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
565 def _changesrange(fctx1, fctx2, linerange2, diffopts): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
566 """Return `(diffinrange, linerange1)` where `diffinrange` is True |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
567 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
|
568 `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
|
569 """ |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
570 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
|
571 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
|
572 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
|
573 return diffinrange, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
574 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
575 |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
576 def blockancestors(fctx, fromline, toline, followfirst=False): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
577 """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
|
578 `fromline`-`toline` range. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
579 """ |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
580 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
|
581 fctx = fctx.introfilectx() |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
582 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
|
583 while visit: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
584 c, linerange2 = visit.pop(max(visit)) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
585 pl = c.parents() |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
586 if followfirst: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
587 pl = pl[:1] |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
588 if not pl: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
589 # The block originates from the initial revision. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
590 yield c, linerange2 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
591 continue |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
592 inrange = False |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
593 for p in pl: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
594 inrangep, linerange1 = _changesrange(p, c, linerange2, diffopts) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
595 inrange = inrange or inrangep |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
596 if linerange1[0] == linerange1[1]: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
597 # 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
|
598 # 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
|
599 # branch. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
600 continue |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
601 # 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
|
602 # _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
|
603 # (as srcrev) instead possibly topmost introrev. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
604 p._descendantrev = c.rev() |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
605 visit[p.linkrev(), p.filenode()] = p, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
606 if inrange: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
607 yield c, linerange2 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
608 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
609 |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
610 def blockdescendants(fctx, fromline, toline): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
611 """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
|
612 `fromline`-`toline` range. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
613 """ |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
614 # 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
|
615 # its parents. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
616 try: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
617 c, linerange1 = next(blockancestors(fctx, fromline, toline)) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
618 except StopIteration: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
619 pass |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
620 else: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
621 if c == fctx: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
622 yield c, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
623 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
624 diffopts = patch.diffopts(fctx._repo.ui) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
625 fl = fctx.filelog() |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
626 seen = {fctx.filerev(): (fctx, (fromline, toline))} |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
627 for i in fl.descendants([fctx.filerev()]): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
628 c = fctx.filectx(i) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
629 inrange = False |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
630 for x in fl.parentrevs(i): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
631 try: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
632 p, linerange2 = seen[x] |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
633 except KeyError: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
634 # nullrev or other branch |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
635 continue |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
636 inrangep, linerange1 = _changesrange(c, p, linerange2, diffopts) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
637 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
|
638 # 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
|
639 # 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
|
640 # 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
|
641 # information. |
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33080
diff
changeset
|
642 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
|
643 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
|
644 linerange1 = min(lbs), max(ubs) |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
645 seen[i] = c, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
646 if inrange: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
647 yield c, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
648 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
649 |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
650 @attr.s(slots=True, frozen=True) |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
651 class annotateline(object): |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
652 fctx = attr.ib() |
37065
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
653 lineno = attr.ib() |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
654 # 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
|
655 skip = attr.ib(default=False) |
37066
b33b91ca2ec2
annotate: pack line content into annotateline object (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37065
diff
changeset
|
656 text = attr.ib(default=None) |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
657 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
658 |
37064
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
659 @attr.s(slots=True, frozen=True) |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
660 class _annotatedfile(object): |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
661 # 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
|
662 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
|
663 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
|
664 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
|
665 # 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
|
666 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
|
667 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
668 |
36919
8fba319750c2
dagop: move lines() out of annotate()
Yuya Nishihara <yuya@tcha.org>
parents:
36918
diff
changeset
|
669 def _countlines(text): |
43077
687b865b95ad
formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents:
43076
diff
changeset
|
670 if text.endswith(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") |
687b865b95ad
formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents:
43076
diff
changeset
|
672 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
|
673 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
674 |
37065
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
675 def _decoratelines(text, fctx): |
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
676 n = _countlines(text) |
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
677 linenos = pycompat.rangelist(1, n + 1) |
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
678 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
|
679 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
680 |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
681 def _annotatepair(parents, childfctx, child, skipchild, diffopts): |
45942
89a2afe31e82
formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents:
45416
diff
changeset
|
682 r""" |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
683 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
|
684 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
|
685 data. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
686 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
687 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
|
688 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
|
689 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
690 See test-annotate.py for unit tests. |
45942
89a2afe31e82
formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents:
45416
diff
changeset
|
691 """ |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
692 pblocks = [ |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
693 (parent, mdiff.allblocks(parent.text, child.text, opts=diffopts)) |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
694 for parent in parents |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
695 ] |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
696 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
697 if skipchild: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
698 # 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
|
699 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
|
700 # 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
|
701 # TODO: change this? |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
702 for parent, blocks in pblocks: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
703 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
|
704 # 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
|
705 # belong to the child. |
43077
687b865b95ad
formatting: byteify all mercurial/ and hgext/ string literals
Augie Fackler <augie@google.com>
parents:
43076
diff
changeset
|
706 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
|
707 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
|
708 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
|
709 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
|
710 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
711 if skipchild: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
712 # 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
|
713 # 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
|
714 # behavior. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
715 pblocks.reverse() |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
716 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
717 # The heuristics are: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
718 # * 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
|
719 # 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
|
720 # * 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
|
721 # 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
|
722 # * 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
|
723 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
724 # 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
|
725 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
|
726 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
|
727 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
|
728 if a2 - a1 >= b2 - b1: |
38783
e7aa113b14f7
global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents:
37066
diff
changeset
|
729 for bk in pycompat.xrange(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
|
730 if child.fctxs[bk] == childfctx: |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
731 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
|
732 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
|
733 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
|
734 child.skips[bk] = True |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
735 else: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
736 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
|
737 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
738 # 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
|
739 # line. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
740 for parent, blocks in remaining: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
741 for a1, a2, b1, b2 in blocks: |
38783
e7aa113b14f7
global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents:
37066
diff
changeset
|
742 for bk in pycompat.xrange(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
|
743 if child.fctxs[bk] == childfctx: |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
744 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
|
745 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
|
746 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
|
747 child.skips[bk] = True |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
748 return child |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
749 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
750 |
37065
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
751 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
|
752 """Core algorithm for filectx.annotate() |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
753 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
754 `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
|
755 """ |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
756 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
757 # 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
|
758 # 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
|
759 # depth-first search. |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
760 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
761 # 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
|
762 visit = [base] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
763 pcache = {} |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
764 needed = {base: 1} |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
765 while visit: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
766 f = visit.pop() |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
767 if f in pcache: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
768 continue |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
769 pl = parents(f) |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
770 pcache[f] = pl |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
771 for p in pl: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
772 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
|
773 if p not in pcache: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
774 visit.append(p) |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
775 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
776 # 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
|
777 visit[:] = [base] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
778 hist = {} |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
779 while visit: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
780 f = visit[-1] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
781 if f in hist: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
782 visit.pop() |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
783 continue |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
784 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
785 ready = True |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
786 pl = pcache[f] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
787 for p in pl: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
788 if p not in hist: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
789 ready = False |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
790 visit.append(p) |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
791 if ready: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
792 visit.pop() |
37065
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
793 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
|
794 skipchild = False |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
795 if skiprevs is not None: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
796 skipchild = f._changeid in skiprevs |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
797 curr = _annotatepair( |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
798 [hist[p] for p in pl], f, curr, skipchild, diffopts |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
799 ) |
36918
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
800 for p in pl: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
801 if needed[p] == 1: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
802 del hist[p] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
803 del needed[p] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
804 else: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
805 needed[p] -= 1 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
806 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
807 hist[f] = curr |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
808 del pcache[f] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
809 |
37064
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
810 a = hist[base] |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
811 return [ |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
812 annotateline(*r) |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
813 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
|
814 ] |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
815 |
36918
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
816 |
32903
27932a76a88d
dagop: split module hosting DAG-related algorithms from revset
Yuya Nishihara <yuya@tcha.org>
parents:
32885
diff
changeset
|
817 def toposort(revs, parentsfunc, firstbranch=()): |
29347
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
818 """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
|
819 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
820 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
|
821 the number of parallel branches and their interleaving. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
822 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
823 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
|
824 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
825 o 4 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
826 | |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
827 o 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
828 | |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
829 | o 3 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
830 | | |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
831 | o 2 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
832 |/ |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
833 o 0 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
834 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
835 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
|
836 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
|
837 occur behind a merge. |
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 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
840 ### Quick summary of the algorithm |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
841 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
842 # 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
|
843 # 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
|
844 # "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
|
845 # branches with interleaved revisions. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
846 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
847 # During iteration revs are split into two groups: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
848 # A) revision already emitted |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
849 # 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
|
850 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
851 # for each REV, we do the following logic: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
852 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
853 # 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
|
854 # 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
|
855 # 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
|
856 # group first. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
857 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
858 # 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
|
859 # 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
|
860 # now awaiting for REV.parents() to be available. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
861 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
862 # 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
|
863 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
864 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
865 # 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
|
866 # puts it in group (A) from above). |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
867 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
868 revs.sort(reverse=True) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
869 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
870 # 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
|
871 # 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
|
872 # need to delay the revisions that reference them. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
873 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
874 # 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
|
875 # 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
|
876 # emitted. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
877 unblocked = set(firstbranch) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
878 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
879 # 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
|
880 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
881 # (revs: lists of revs waiting to be displayed, |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
882 # 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
|
883 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
884 # 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
|
885 # 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
|
886 # 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
|
887 # 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
|
888 # 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
|
889 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
890 # 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
|
891 # 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
|
892 # 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
|
893 # 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
|
894 # 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
|
895 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
896 # 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
|
897 # 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
|
898 # '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
|
899 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
900 # 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
|
901 # 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
|
902 groups = [([], unblocked)] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
903 pendingheap = [] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
904 pendingset = set() |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
905 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
906 heapq.heapify(pendingheap) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
907 heappop = heapq.heappop |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
908 heappush = heapq.heappush |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
909 for currentrev in revs: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
910 # 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
|
911 if currentrev not in pendingset: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
912 heappush(pendingheap, -currentrev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
913 pendingset.add(currentrev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
914 # 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
|
915 # processed. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
916 rev = None |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
917 while rev != currentrev: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
918 rev = -heappop(pendingheap) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
919 pendingset.remove(rev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
920 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
921 # 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
|
922 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
|
923 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
924 if matching: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
925 # 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
|
926 # on the same revision. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
927 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
928 # 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
|
929 # observed. For example, given two groups: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
930 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
931 # revs [5, 4] waiting for 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
932 # revs [3, 2] waiting for 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
933 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
934 # 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
|
935 # 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
|
936 # 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
|
937 # 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
|
938 # 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
|
939 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
940 # 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
|
941 # 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
|
942 # 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
|
943 # 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
|
944 targetidx = matching.pop(0) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
945 trevs, tparents = groups[targetidx] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
946 for i in matching: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
947 gr = groups[i] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
948 trevs.extend(gr[0]) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
949 tparents |= gr[1] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
950 # 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
|
951 # (starting from the last subgroup for performance and |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
952 # sanity reasons) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
953 for i in reversed(matching): |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
954 del groups[i] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
955 else: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
956 # 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
|
957 targetidx = len(groups) |
32291
bd872f64a8ba
cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents:
32085
diff
changeset
|
958 groups.append(([], {rev})) |
29347
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
959 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
960 gr = groups[targetidx] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
961 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
962 # 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
|
963 # 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
|
964 # that relied on this rev must precede it. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
965 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
966 # 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
|
967 # new nodes. |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
968 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
|
969 gr[0].append(rev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
970 gr[1].remove(rev) |
46113
59fa3890d40a
node: import symbols explicitly
Joerg Sonnenberger <joerg@bec.de>
parents:
45942
diff
changeset
|
971 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
|
972 gr[1].update(parents) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
973 for p in parents: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
974 if p not in pendingset: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
975 pendingset.add(p) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
976 heappush(pendingheap, -p) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
977 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
978 # Look for a subgroup to display |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
979 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
980 # 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
|
981 # 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
|
982 # 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
|
983 # 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
|
984 # subgroup. The heuristic could probably be better. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
985 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
986 # 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
|
987 # 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
|
988 # well. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
989 if not unblocked: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
990 if len(groups) > 1: # display other subset |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
991 targetidx = 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
992 gr = groups[1] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
993 elif not gr[1] & unblocked: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
994 gr = None |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
995 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
996 if gr is not None: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
997 # 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
|
998 # subgroup |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
999 unblocked |= gr[1] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1000 # output all revisions in the subgroup |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1001 for r in gr[0]: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1002 yield r |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1003 # delete the subgroup that you just output |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1004 # 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
|
1005 if targetidx: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1006 del groups[targetidx] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1007 else: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1008 gr[0][:] = [] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1009 # 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
|
1010 # iterate over |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1011 for g in groups: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1012 for r in g[0]: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
1013 yield r |
39179
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1014 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
1015 |
39179
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1016 def headrevs(revs, parentsfn): |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1017 """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
|
1018 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1019 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
|
1020 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
|
1021 including nullrev. |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1022 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1023 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
|
1024 subset. |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1025 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1026 ``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
|
1027 the input set. |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1028 """ |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1029 headrevs = set(revs) |
46113
59fa3890d40a
node: import symbols explicitly
Joerg Sonnenberger <joerg@bec.de>
parents:
45942
diff
changeset
|
1030 parents = {nullrev} |
41277
61f9ef23a12f
dagop: minor python optimization to `headrevs`
Boris Feld <boris.feld@octobus.net>
parents:
40000
diff
changeset
|
1031 up = parents.update |
39179
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1032 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1033 for rev in revs: |
41277
61f9ef23a12f
dagop: minor python optimization to `headrevs`
Boris Feld <boris.feld@octobus.net>
parents:
40000
diff
changeset
|
1034 up(parentsfn(rev)) |
61f9ef23a12f
dagop: minor python optimization to `headrevs`
Boris Feld <boris.feld@octobus.net>
parents:
40000
diff
changeset
|
1035 headrevs.difference_update(parents) |
39179
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
1036 return headrevs |
39181
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1037 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
1038 |
40000
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1039 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
|
1040 """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
|
1041 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1042 ``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
|
1043 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
|
1044 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
|
1045 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1046 ``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
|
1047 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
|
1048 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1049 ``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
|
1050 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1051 ``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
|
1052 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
|
1053 collection will be heads. |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1054 """ |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1055 if startrev is None: |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1056 startrev = nullrev |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1057 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1058 stoprevs = set(stoprevs or []) |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1059 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1060 reachable = {startrev} |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1061 heads = {startrev} |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1062 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1063 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
|
1064 for prev in parentrevsfn(rev): |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1065 if prev in reachable: |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1066 if rev not in stoprevs: |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1067 reachable.add(rev) |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1068 heads.add(rev) |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1069 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1070 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
|
1071 heads.remove(prev) |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1072 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1073 return heads |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39999
diff
changeset
|
1074 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
42446
diff
changeset
|
1075 |
39181
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1076 def linearize(revs, parentsfn): |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1077 """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
|
1078 |
39607
5362c96f2feb
dagop: fix typo spotted while doing unrelated investigation
Augie Fackler <augie@google.com>
parents:
39181
diff
changeset
|
1079 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
|
1080 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
|
1081 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
|
1082 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
|
1083 itself to the output list. |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1084 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1085 Returns a list of revision numbers. |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1086 """ |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1087 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
|
1088 finished = set() |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1089 result = [] |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1090 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1091 while visit: |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1092 rev = visit.pop() |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1093 if rev < 0: |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1094 rev = -rev - 1 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1095 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1096 if rev not in finished: |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1097 result.append(rev) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1098 finished.add(rev) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1099 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1100 else: |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1101 visit.append(-rev - 1) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1102 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1103 for prev in parentsfn(rev): |
46113
59fa3890d40a
node: import symbols explicitly
Joerg Sonnenberger <joerg@bec.de>
parents:
45942
diff
changeset
|
1104 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
|
1105 continue |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1106 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1107 visit.append(prev) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1108 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1109 assert len(result) == len(revs) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1110 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
1111 return result |