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