Mercurial > public > mercurial-scm > hg-stable
annotate mercurial/dagop.py @ 41277:61f9ef23a12f
dagop: minor python optimization to `headrevs`
Less lookup and less function call never hurt. This provides a small speedup
on various run of the 'heads()' revset. This also buys back some of the slow
down we observed in the previous changesets for single value lookup.
Performance number:
0) before dagop.headrevs usage
1) after dagop.headrevs usage
2) after this change
revset: heads(all())
plain min max first last reverse rev..rst rev..ast sort sor..rst sor..ast
0) 0.036503 0.032564 0.030024 0.032378 0.030887 0.036367 0.031713 0.032205 0.036467 0.032286 0.030300
1) 0.036668 0.035347 108% 0.035611 118% 0.035358 109% 0.035726 115% 0.036411 0.035261 111% 0.036096 112% 0.036052 0.035095 108% 0.035792 118%
2) 0.034254 93% 0.034482 0.035003 0.034353 0.033754 94% 0.034689 0.034361 0.035059 0.034636 0.034662 0.035465
revset: heads(-10000:-1)
plain min max first last reverse rev..rst rev..ast sort sor..rst sor..ast
0) 0.003936 0.003218 0.003227 0.003302 0.003328 0.003848 0.003305 0.003252 0.003839 0.003306 0.003279
1) 0.003870 0.003785 117% 0.003821 118% 0.003780 114% 0.003769 113% 0.003776 0.003792 114% 0.003805 117% 0.003810 0.003798 114% 0.003840 117%
2) 0.003666 94% 0.003577 94% 0.003632 0.003644 0.003614 0.003638 0.003652 0.003632 0.003661 0.003660 0.003658
revset: (-5000:-1000) and heads(-10000:-1)
plain min max first last reverse rev..rst rev..ast sort sor..rst sor..ast
0) 0.004244 0.003368 0.003313 0.003367 0.003327 0.004325 0.003401 0.003379 0.004310 0.003359 0.003396
1) 0.003969 93% 0.003862 114% 0.003834 115% 0.003810 113% 0.003822 114% 0.003940 91% 0.003908 114% 0.003814 112% 0.003986 92% 0.003954 117% 0.003816 112%
2) 0.003728 93% 0.003638 94% 0.003659 0.003685 0.003628 94% 0.003716 94% 0.003653 93% 0.003655 0.003748 94% 0.003740 94% 0.003686
revset: heads(matching(tip, "author"))
plain min max first last reverse rev..rst rev..ast sort sor..rst sor..ast
0) 7.574666 7.545950 7.570743 7.578697 7.525725 7.509929 7.443854 7.488442 7.452880 7.445411 7.689107
1) 7.549390 7.389162 7.529790 7.536297 7.450467 7.555347 7.404586 7.514948 7.542794 7.524787 7.536918
2) 7.568294 7.479326 7.578624 7.380375 7.440102 7.454218 7.515189 7.556511 7.524585 7.537566 7.507418
revset: heads(matching(tip, "author")) and -10000:-1
plain min max first last reverse rev..rst rev..ast sort sor..rst sor..ast
0) 7.512533 7.605877 7.382894 7.462109 7.420086 7.575034 7.448452 7.549374 7.457880 7.450308 7.515019
1) 7.548677 7.551832 7.629598 7.494857 7.550554 7.521838 7.451794 error 7.321781 7.546885 7.557523
2) 7.451985 7.541044 7.506563 7.470928 7.512618 7.474988 7.498887 7.547930 7.560276 7.618599 7.465442
revset: (-10000:-1) and heads(matching(tip, "author"))
plain min max first last reverse rev..rst rev..ast sort sor..rst sor..ast
0) 7.465419 7.570089 7.439594 7.521221 7.498716 7.492922 7.479108 7.552397 7.407888 error 7.468264
1) 7.539866 7.548045 7.491761 7.517170 7.469824 7.501990 7.579102 7.502568 7.578102 7.555754 7.567622
2) 7.370463 7.514712 7.497024 7.679428 7.638138 7.490775 7.472273 7.652587 7.584139 7.511893 7.466384
author | Boris Feld <boris.feld@octobus.net> |
---|---|
date | Mon, 14 Jan 2019 17:15:21 +0100 |
parents | 8af835af0a85 |
children | 431cf2c8c839 |
rev | line source |
---|---|
32921
27932a76a88d
dagop: split module hosting DAG-related algorithms from revset
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
1 # dagop.py - graph ancestry and topology algorithm for revset |
11275 | 2 # |
3 # Copyright 2010 Matt Mackall <mpm@selenic.com> | |
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 |
40000
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
12 from .node import ( |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
13 nullrev, |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
14 ) |
36923
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
15 from .thirdparty import ( |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
16 attr, |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
17 ) |
25971
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
18 from . import ( |
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
19 error, |
32922
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
20 mdiff, |
25971
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
21 node, |
32922
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
22 patch, |
36924
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
23 pycompat, |
30913
1be65deb3d54
smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
30850
diff
changeset
|
24 smartset, |
25971
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
25 ) |
11275 | 26 |
30913
1be65deb3d54
smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
30850
diff
changeset
|
27 baseset = smartset.baseset |
1be65deb3d54
smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
30850
diff
changeset
|
28 generatorset = smartset.generatorset |
1be65deb3d54
smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
30850
diff
changeset
|
29 |
33018
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33017
diff
changeset
|
30 # possible maximum depth between null and wdir() |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33017
diff
changeset
|
31 _maxlogdepth = 0x80000000 |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33017
diff
changeset
|
32 |
33091
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33090
diff
changeset
|
33 def _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse): |
33090
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33089
diff
changeset
|
34 """Walk DAG using 'pfunc' from the given 'revs' nodes |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33089
diff
changeset
|
35 |
33091
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33090
diff
changeset
|
36 '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:
33090
diff
changeset
|
37 if 'reverse' is True/False respectively. |
33090
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33089
diff
changeset
|
38 |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33089
diff
changeset
|
39 Scan ends at the stopdepth (exlusive) if specified. Revisions found |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33089
diff
changeset
|
40 earlier than the startdepth are omitted. |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33089
diff
changeset
|
41 """ |
33019
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33018
diff
changeset
|
42 if startdepth is None: |
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33018
diff
changeset
|
43 startdepth = 0 |
33018
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33017
diff
changeset
|
44 if stopdepth is None: |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33017
diff
changeset
|
45 stopdepth = _maxlogdepth |
33039
a10f5f6771f6
dagop: raise ProgrammingError if stopdepth < 0
Martin von Zweigbergk <martinvonz@google.com>
parents:
33019
diff
changeset
|
46 if stopdepth == 0: |
33018
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33017
diff
changeset
|
47 return |
33039
a10f5f6771f6
dagop: raise ProgrammingError if stopdepth < 0
Martin von Zweigbergk <martinvonz@google.com>
parents:
33019
diff
changeset
|
48 if stopdepth < 0: |
a10f5f6771f6
dagop: raise ProgrammingError if stopdepth < 0
Martin von Zweigbergk <martinvonz@google.com>
parents:
33019
diff
changeset
|
49 raise error.ProgrammingError('negative stopdepth') |
33091
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33090
diff
changeset
|
50 if reverse: |
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33090
diff
changeset
|
51 heapsign = -1 # max heap |
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33090
diff
changeset
|
52 else: |
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33090
diff
changeset
|
53 heapsign = +1 # min heap |
33018
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33017
diff
changeset
|
54 |
33014
c7da57bbae96
dagop: comment why revancestors() doesn't heapify input revs at once
Yuya Nishihara <yuya@tcha.org>
parents:
33013
diff
changeset
|
55 # 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:
33013
diff
changeset
|
56 # without fully computing the input revs |
33091
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33090
diff
changeset
|
57 revs.sort(reverse) |
33013
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32922
diff
changeset
|
58 irevs = iter(revs) |
33091
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33090
diff
changeset
|
59 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
|
60 |
33013
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32922
diff
changeset
|
61 inputrev = next(irevs, None) |
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32922
diff
changeset
|
62 if inputrev is not None: |
33091
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33090
diff
changeset
|
63 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
|
64 |
33016
d3d36bcdf036
dagop: just compare with the last value to deduplicate input of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33015
diff
changeset
|
65 lastrev = None |
33015
08e2793d9f65
dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33014
diff
changeset
|
66 while pendingheap: |
33017
92d0945a15e0
dagop: compute depth in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33016
diff
changeset
|
67 currev, curdepth = heapq.heappop(pendingheap) |
33091
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33090
diff
changeset
|
68 currev = heapsign * currev |
33015
08e2793d9f65
dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33014
diff
changeset
|
69 if currev == inputrev: |
33013
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32922
diff
changeset
|
70 inputrev = next(irevs, None) |
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32922
diff
changeset
|
71 if inputrev is not None: |
33091
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33090
diff
changeset
|
72 heapq.heappush(pendingheap, (heapsign * inputrev, 0)) |
33019
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33018
diff
changeset
|
73 # rescan parents until curdepth >= startdepth because queued entries |
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33018
diff
changeset
|
74 # of the same revision are iterated from the lowest depth |
33018
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33017
diff
changeset
|
75 foundnew = (currev != lastrev) |
33019
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33018
diff
changeset
|
76 if foundnew and curdepth >= startdepth: |
33016
d3d36bcdf036
dagop: just compare with the last value to deduplicate input of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33015
diff
changeset
|
77 lastrev = currev |
33015
08e2793d9f65
dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33014
diff
changeset
|
78 yield currev |
33018
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33017
diff
changeset
|
79 pdepth = curdepth + 1 |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33017
diff
changeset
|
80 if foundnew and pdepth < stopdepth: |
33089
58ebb38456e0
dagop: factor out pfunc from revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33088
diff
changeset
|
81 for prev in pfunc(currev): |
58ebb38456e0
dagop: factor out pfunc from revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33088
diff
changeset
|
82 if prev != node.nullrev: |
33091
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33090
diff
changeset
|
83 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
|
84 |
35285
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35284
diff
changeset
|
85 def filectxancestors(fctxs, followfirst=False): |
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35284
diff
changeset
|
86 """Like filectx.ancestors(), but can walk from multiple files/revisions, |
35305
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35285
diff
changeset
|
87 and includes the given fctxs themselves |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35285
diff
changeset
|
88 |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35285
diff
changeset
|
89 Yields (rev, {fctx, ...}) pairs in descending order. |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35285
diff
changeset
|
90 """ |
35279
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34082
diff
changeset
|
91 visit = {} |
35306
c9144396099b
dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35305
diff
changeset
|
92 visitheap = [] |
35283
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35282
diff
changeset
|
93 def addvisit(fctx): |
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35282
diff
changeset
|
94 rev = fctx.rev() |
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35282
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:
35282
diff
changeset
|
96 visit[rev] = set() |
35306
c9144396099b
dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35305
diff
changeset
|
97 heapq.heappush(visitheap, -rev) # max heap |
35283
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35282
diff
changeset
|
98 visit[rev].add(fctx) |
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35282
diff
changeset
|
99 |
35279
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34082
diff
changeset
|
100 if followfirst: |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34082
diff
changeset
|
101 cut = 1 |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34082
diff
changeset
|
102 else: |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34082
diff
changeset
|
103 cut = None |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34082
diff
changeset
|
104 |
35285
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35284
diff
changeset
|
105 for c in fctxs: |
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35284
diff
changeset
|
106 addvisit(c) |
35284
b4b328ea6175
dagop: put start fctx into visit dict of filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35283
diff
changeset
|
107 while visit: |
35306
c9144396099b
dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35305
diff
changeset
|
108 currev = -heapq.heappop(visitheap) |
35305
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35285
diff
changeset
|
109 curfctxs = visit.pop(currev) |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35285
diff
changeset
|
110 yield currev, curfctxs |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35285
diff
changeset
|
111 for c in curfctxs: |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35285
diff
changeset
|
112 for parent in c.parents()[:cut]: |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35285
diff
changeset
|
113 addvisit(parent) |
35306
c9144396099b
dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35305
diff
changeset
|
114 assert not visitheap |
35305
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35285
diff
changeset
|
115 |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35285
diff
changeset
|
116 def filerevancestors(fctxs, followfirst=False): |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35285
diff
changeset
|
117 """Like filectx.ancestors(), but can walk from multiple files/revisions, |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35285
diff
changeset
|
118 and includes the given fctxs themselves |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35285
diff
changeset
|
119 |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35285
diff
changeset
|
120 Returns a smartset. |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35285
diff
changeset
|
121 """ |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35285
diff
changeset
|
122 gen = (rev for rev, _cs in filectxancestors(fctxs, followfirst)) |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35285
diff
changeset
|
123 return generatorset(gen, iterasc=False) |
35279
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34082
diff
changeset
|
124 |
34082
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
125 def _genrevancestors(repo, revs, followfirst, startdepth, stopdepth, cutfunc): |
33090
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33089
diff
changeset
|
126 if followfirst: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33089
diff
changeset
|
127 cut = 1 |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33089
diff
changeset
|
128 else: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33089
diff
changeset
|
129 cut = None |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33089
diff
changeset
|
130 cl = repo.changelog |
34082
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
131 def plainpfunc(rev): |
33090
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33089
diff
changeset
|
132 try: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33089
diff
changeset
|
133 return cl.parentrevs(rev)[:cut] |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33089
diff
changeset
|
134 except error.WdirUnsupported: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33089
diff
changeset
|
135 return (pctx.rev() for pctx in repo[rev].parents()[:cut]) |
34082
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
136 if cutfunc is None: |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
137 pfunc = plainpfunc |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
138 else: |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
139 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
|
140 revs = revs.filter(lambda rev: not cutfunc(rev)) |
33091
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33090
diff
changeset
|
141 return _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse=True) |
33090
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33089
diff
changeset
|
142 |
34082
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
143 def revancestors(repo, revs, followfirst=False, startdepth=None, |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
144 stopdepth=None, cutfunc=None): |
33018
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33017
diff
changeset
|
145 """Like revlog.ancestors(), but supports additional options, includes |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33017
diff
changeset
|
146 the given revs themselves, and returns a smartset |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33017
diff
changeset
|
147 |
33019
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33018
diff
changeset
|
148 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:
33018
diff
changeset
|
149 earlier than the startdepth are omitted. |
34082
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
150 |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
151 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
|
152 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
|
153 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
|
154 optimization sometimes. |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
155 |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
156 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
|
157 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
|
158 return True in this case. For example, |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
159 |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
160 D # revancestors(repo, D, cutfunc=lambda rev: rev == B) |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
161 |\ # 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
|
162 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
|
163 |/ |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
164 A |
33018
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33017
diff
changeset
|
165 """ |
34082
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
166 gen = _genrevancestors(repo, revs, followfirst, startdepth, stopdepth, |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
167 cutfunc) |
33013
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32922
diff
changeset
|
168 return generatorset(gen, iterasc=False) |
16409
2cbd7dd0cc1f
graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents:
16402
diff
changeset
|
169 |
33085
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33039
diff
changeset
|
170 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
|
171 if followfirst: |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Guti?rrez Hermoso <jordigh@octave.org>
parents:
24219
diff
changeset
|
172 cut = 1 |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Guti?rrez Hermoso <jordigh@octave.org>
parents:
24219
diff
changeset
|
173 else: |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Guti?rrez Hermoso <jordigh@octave.org>
parents:
24219
diff
changeset
|
174 cut = None |
16409
2cbd7dd0cc1f
graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents:
16402
diff
changeset
|
175 |
33085
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33039
diff
changeset
|
176 cl = repo.changelog |
33088
a76a64c78807
dagop: use smartset.min() in revdescendants() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33087
diff
changeset
|
177 first = revs.min() |
33085
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33039
diff
changeset
|
178 nullrev = node.nullrev |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33039
diff
changeset
|
179 if first == nullrev: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33039
diff
changeset
|
180 # 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:
33039
diff
changeset
|
181 # second one? Maybe. Do we care? Probably not. |
33087
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33085
diff
changeset
|
182 yield first |
33085
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33039
diff
changeset
|
183 for i in cl: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33039
diff
changeset
|
184 yield i |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33039
diff
changeset
|
185 else: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33039
diff
changeset
|
186 seen = set(revs) |
33087
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33085
diff
changeset
|
187 for i in cl.revs(first): |
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33085
diff
changeset
|
188 if i in seen: |
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33085
diff
changeset
|
189 yield i |
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33085
diff
changeset
|
190 continue |
33085
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33039
diff
changeset
|
191 for x in cl.parentrevs(i)[:cut]: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33039
diff
changeset
|
192 if x != nullrev and x in seen: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33039
diff
changeset
|
193 seen.add(i) |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33039
diff
changeset
|
194 yield i |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33039
diff
changeset
|
195 break |
20692
7af341082b76
revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents:
20691
diff
changeset
|
196 |
33092
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
197 def _builddescendantsmap(repo, startrev, followfirst): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
198 """Build map of 'rev -> child revs', offset from startrev""" |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
199 cl = repo.changelog |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
200 nullrev = node.nullrev |
38823
e7aa113b14f7
global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents:
37069
diff
changeset
|
201 descmap = [[] for _rev in pycompat.xrange(startrev, len(cl))] |
33092
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
202 for currev in cl.revs(startrev + 1): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
203 p1rev, p2rev = cl.parentrevs(currev) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
204 if p1rev >= startrev: |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
205 descmap[p1rev - startrev].append(currev) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
206 if not followfirst and p2rev != nullrev and p2rev >= startrev: |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
207 descmap[p2rev - startrev].append(currev) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
208 return descmap |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
209 |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
210 def _genrevdescendantsofdepth(repo, revs, followfirst, startdepth, stopdepth): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
211 startrev = revs.min() |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
212 descmap = _builddescendantsmap(repo, startrev, followfirst) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
213 def pfunc(rev): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
214 return descmap[rev - startrev] |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
215 return _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse=False) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
216 |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
217 def revdescendants(repo, revs, followfirst, startdepth=None, stopdepth=None): |
33087
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33085
diff
changeset
|
218 """Like revlog.descendants() but supports additional options, includes |
33092
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
219 the given revs themselves, and returns a smartset |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
220 |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
221 Scan ends at the stopdepth (exlusive) if specified. Revisions found |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
222 earlier than the startdepth are omitted. |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
223 """ |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
224 if startdepth is None and stopdepth is None: |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
225 gen = _genrevdescendants(repo, revs, followfirst) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
226 else: |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
227 gen = _genrevdescendantsofdepth(repo, revs, followfirst, |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33091
diff
changeset
|
228 startdepth, stopdepth) |
33085
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33039
diff
changeset
|
229 return generatorset(gen, iterasc=True) |
16409
2cbd7dd0cc1f
graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents:
16402
diff
changeset
|
230 |
40000
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
231 def descendantrevs(revs, revsfn, parentrevsfn): |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
232 """Generate revision number descendants in revision order. |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
233 |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
234 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:
39623
diff
changeset
|
235 ``revs``. Results are ordered by revision number and are |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
236 therefore topological. Each revision is not considered a descendant |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
237 of itself. |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
238 |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
239 ``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:
39623
diff
changeset
|
240 revision numbers and with a ``start`` argument iterates over revision |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
241 numbers beginning with that value. |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
242 |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
243 ``parentrevsfn`` is a callable that receives a revision number and |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
244 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:
39623
diff
changeset
|
245 nullrev. |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
246 """ |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
247 first = min(revs) |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
248 |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
249 if first == nullrev: |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
250 for rev in revsfn(): |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
251 yield rev |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
252 return |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
253 |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
254 seen = set(revs) |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
255 for rev in revsfn(start=first + 1): |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
256 for prev in parentrevsfn(rev): |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
257 if prev != nullrev and prev in seen: |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
258 seen.add(rev) |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
259 yield rev |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
260 break |
0b24fcd88066
dagop: extract descendants() from revlog module
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39623
diff
changeset
|
261 |
26095
6eed95ca4c03
revset: mark reachablerootspure as private
Yuya Nishihara <yuya@tcha.org>
parents:
26094
diff
changeset
|
262 def _reachablerootspure(repo, minroot, roots, heads, includepath): |
26002
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
263 """return (heads(::<roots> and ::<heads>)) |
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
264 |
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
265 If includepath is True, return (<roots>::<heads>).""" |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
266 if not roots: |
26094
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
267 return [] |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
268 parentrevs = repo.changelog.parentrevs |
26053
b68c9d232db6
reachableroots: use internal "revstates" array to test if rev is a root
Yuya Nishihara <yuya@tcha.org>
parents:
26006
diff
changeset
|
269 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
|
270 visit = list(heads) |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
271 reachable = set() |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
272 seen = {} |
25566
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
273 # 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
|
274 reached = reachable.add |
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
275 dovisit = visit.append |
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
276 nextvisit = visit.pop |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
277 # 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
|
278 # sys.getrecursionlimit() |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
279 while visit: |
25566
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
280 rev = nextvisit() |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
281 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
|
282 reached(rev) |
26002
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
283 if not includepath: |
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
284 continue |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
285 parents = parentrevs(rev) |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
286 seen[rev] = parents |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
287 for parent in parents: |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
288 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
|
289 dovisit(parent) |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
290 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
|
291 return baseset() |
26002
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
292 if not includepath: |
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
293 return reachable |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
294 for rev in sorted(seen): |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
295 for parent in seen[rev]: |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
296 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
|
297 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
|
298 return reachable |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
299 |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
300 def reachableroots(repo, roots, heads, includepath=False): |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
301 """return (heads(::<roots> and ::<heads>)) |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
302 |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
303 If includepath is True, return (<roots>::<heads>).""" |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
304 if not roots: |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
305 return baseset() |
26093
204131131766
reachableroots: use smartset min
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
26091
diff
changeset
|
306 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
|
307 roots = list(roots) |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
308 heads = list(heads) |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
309 try: |
26094
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
310 revs = repo.changelog.reachableroots(minroot, heads, roots, includepath) |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
311 except AttributeError: |
26095
6eed95ca4c03
revset: mark reachablerootspure as private
Yuya Nishihara <yuya@tcha.org>
parents:
26094
diff
changeset
|
312 revs = _reachablerootspure(repo, minroot, roots, heads, includepath) |
26094
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
313 revs = baseset(revs) |
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
314 revs.sort() |
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
315 return revs |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
316 |
32922
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
317 def _changesrange(fctx1, fctx2, linerange2, diffopts): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
318 """Return `(diffinrange, linerange1)` where `diffinrange` is True |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
319 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:
32921
diff
changeset
|
320 `linerange1` is the new line range for fctx1. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
321 """ |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
322 blocks = mdiff.allblocks(fctx1.data(), fctx2.data(), diffopts) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
323 filteredblocks, linerange1 = mdiff.blocksinrange(blocks, linerange2) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
324 diffinrange = any(stype == '!' for _, stype in filteredblocks) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
325 return diffinrange, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
326 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
327 def blockancestors(fctx, fromline, toline, followfirst=False): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
328 """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:
32921
diff
changeset
|
329 `fromline`-`toline` range. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
330 """ |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
331 diffopts = patch.diffopts(fctx._repo.ui) |
35280
d90c534099b1
filectx: extract helper method to obtain filectx pointing to its introrev
Yuya Nishihara <yuya@tcha.org>
parents:
35279
diff
changeset
|
332 fctx = fctx.introfilectx() |
32922
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
333 visit = {(fctx.linkrev(), fctx.filenode()): (fctx, (fromline, toline))} |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
334 while visit: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
335 c, linerange2 = visit.pop(max(visit)) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
336 pl = c.parents() |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
337 if followfirst: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
338 pl = pl[:1] |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
339 if not pl: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
340 # The block originates from the initial revision. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
341 yield c, linerange2 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
342 continue |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
343 inrange = False |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
344 for p in pl: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
345 inrangep, linerange1 = _changesrange(p, c, linerange2, diffopts) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
346 inrange = inrange or inrangep |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
347 if linerange1[0] == linerange1[1]: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
348 # Parent's linerange is empty, meaning that the block got |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
349 # 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:
32921
diff
changeset
|
350 # branch. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
351 continue |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
352 # Set _descendantrev with 'c' (a known descendant) so that, when |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
353 # _adjustlinkrev is called for 'p', it receives this descendant |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
354 # (as srcrev) instead possibly topmost introrev. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
355 p._descendantrev = c.rev() |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
356 visit[p.linkrev(), p.filenode()] = p, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
357 if inrange: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
358 yield c, linerange2 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
359 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
360 def blockdescendants(fctx, fromline, toline): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
361 """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:
32921
diff
changeset
|
362 `fromline`-`toline` range. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
363 """ |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
364 # 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:
32921
diff
changeset
|
365 # its parents. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
366 try: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
367 c, linerange1 = next(blockancestors(fctx, fromline, toline)) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
368 except StopIteration: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
369 pass |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
370 else: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
371 if c == fctx: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
372 yield c, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
373 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
374 diffopts = patch.diffopts(fctx._repo.ui) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
375 fl = fctx.filelog() |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
376 seen = {fctx.filerev(): (fctx, (fromline, toline))} |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
377 for i in fl.descendants([fctx.filerev()]): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
378 c = fctx.filectx(i) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
379 inrange = False |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
380 for x in fl.parentrevs(i): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
381 try: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
382 p, linerange2 = seen[x] |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
383 except KeyError: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
384 # nullrev or other branch |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
385 continue |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
386 inrangep, linerange1 = _changesrange(c, p, linerange2, diffopts) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
387 inrange = inrange or inrangep |
33284
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33092
diff
changeset
|
388 # 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:
33092
diff
changeset
|
389 # 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:
33092
diff
changeset
|
390 # 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:
33092
diff
changeset
|
391 # information. |
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33092
diff
changeset
|
392 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:
33092
diff
changeset
|
393 lbs, ubs = zip(linerange1, seen[i][1]) |
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33092
diff
changeset
|
394 linerange1 = min(lbs), max(ubs) |
32922
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
395 seen[i] = c, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
396 if inrange: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
397 yield c, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32921
diff
changeset
|
398 |
36923
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
399 @attr.s(slots=True, frozen=True) |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
400 class annotateline(object): |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
401 fctx = attr.ib() |
37068
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37067
diff
changeset
|
402 lineno = attr.ib() |
36923
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
403 # 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:
35306
diff
changeset
|
404 skip = attr.ib(default=False) |
37069
b33b91ca2ec2
annotate: pack line content into annotateline object (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37068
diff
changeset
|
405 text = attr.ib(default=None) |
36923
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
406 |
37067
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36941
diff
changeset
|
407 @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:
36941
diff
changeset
|
408 class _annotatedfile(object): |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36941
diff
changeset
|
409 # list indexed by lineno - 1 |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36941
diff
changeset
|
410 fctxs = attr.ib() |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36941
diff
changeset
|
411 linenos = attr.ib() |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36941
diff
changeset
|
412 skips = attr.ib() |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36941
diff
changeset
|
413 # full file content |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36941
diff
changeset
|
414 text = attr.ib() |
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36941
diff
changeset
|
415 |
36925
8fba319750c2
dagop: move lines() out of annotate()
Yuya Nishihara <yuya@tcha.org>
parents:
36924
diff
changeset
|
416 def _countlines(text): |
8fba319750c2
dagop: move lines() out of annotate()
Yuya Nishihara <yuya@tcha.org>
parents:
36924
diff
changeset
|
417 if text.endswith("\n"): |
8fba319750c2
dagop: move lines() out of annotate()
Yuya Nishihara <yuya@tcha.org>
parents:
36924
diff
changeset
|
418 return text.count("\n") |
8fba319750c2
dagop: move lines() out of annotate()
Yuya Nishihara <yuya@tcha.org>
parents:
36924
diff
changeset
|
419 return text.count("\n") + int(bool(text)) |
8fba319750c2
dagop: move lines() out of annotate()
Yuya Nishihara <yuya@tcha.org>
parents:
36924
diff
changeset
|
420 |
37068
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37067
diff
changeset
|
421 def _decoratelines(text, fctx): |
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37067
diff
changeset
|
422 n = _countlines(text) |
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37067
diff
changeset
|
423 linenos = pycompat.rangelist(1, n + 1) |
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37067
diff
changeset
|
424 return _annotatedfile([fctx] * n, linenos, [False] * n, text) |
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37067
diff
changeset
|
425 |
36923
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
426 def _annotatepair(parents, childfctx, child, skipchild, diffopts): |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
427 r''' |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
428 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:
35306
diff
changeset
|
429 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:
35306
diff
changeset
|
430 data. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
431 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
432 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:
35306
diff
changeset
|
433 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:
35306
diff
changeset
|
434 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
435 See test-annotate.py for unit tests. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
436 ''' |
37067
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36941
diff
changeset
|
437 pblocks = [(parent, mdiff.allblocks(parent.text, child.text, opts=diffopts)) |
36923
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
438 for parent in parents] |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
439 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
440 if skipchild: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
441 # 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:
35306
diff
changeset
|
442 pblocks = [(p, list(blocks)) for (p, blocks) in pblocks] |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
443 # Mercurial currently prefers p2 over p1 for annotate. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
444 # TODO: change this? |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
445 for parent, blocks in pblocks: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
446 for (a1, a2, b1, b2), t in blocks: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
447 # Changed blocks ('!') or blocks made only of blank lines ('~') |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
448 # belong to the child. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
449 if t == '=': |
37067
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36941
diff
changeset
|
450 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:
36941
diff
changeset
|
451 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:
36941
diff
changeset
|
452 child.skips[b1:b2] = parent.skips[a1:a2] |
36923
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
453 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
454 if skipchild: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
455 # 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:
35306
diff
changeset
|
456 # Reversing pblocks maintains bias towards p2, matching above |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
457 # behavior. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
458 pblocks.reverse() |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
459 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
460 # The heuristics are: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
461 # * 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:
35306
diff
changeset
|
462 # This could potentially be smarter but works well enough. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
463 # * 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:
35306
diff
changeset
|
464 # diff hunks 1:1, dropping lines as necessary. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
465 # * Repeat the last line as a last resort. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
466 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
467 # 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:
35306
diff
changeset
|
468 remaining = [(parent, []) for parent, _blocks in pblocks] |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
469 for idx, (parent, blocks) in enumerate(pblocks): |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
470 for (a1, a2, b1, b2), _t in blocks: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
471 if a2 - a1 >= b2 - b1: |
38823
e7aa113b14f7
global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents:
37069
diff
changeset
|
472 for bk in pycompat.xrange(b1, b2): |
37067
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36941
diff
changeset
|
473 if child.fctxs[bk] == childfctx: |
36923
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
474 ak = min(a1 + (bk - b1), a2 - 1) |
37067
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36941
diff
changeset
|
475 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:
36941
diff
changeset
|
476 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:
36941
diff
changeset
|
477 child.skips[bk] = True |
36923
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
478 else: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
479 remaining[idx][1].append((a1, a2, b1, b2)) |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
480 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
481 # 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:
35306
diff
changeset
|
482 # line. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
483 for parent, blocks in remaining: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
484 for a1, a2, b1, b2 in blocks: |
38823
e7aa113b14f7
global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents:
37069
diff
changeset
|
485 for bk in pycompat.xrange(b1, b2): |
37067
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36941
diff
changeset
|
486 if child.fctxs[bk] == childfctx: |
36923
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
487 ak = min(a1 + (bk - b1), a2 - 1) |
37067
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36941
diff
changeset
|
488 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:
36941
diff
changeset
|
489 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:
36941
diff
changeset
|
490 child.skips[bk] = True |
36923
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
491 return child |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35306
diff
changeset
|
492 |
37068
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37067
diff
changeset
|
493 def annotate(base, parents, skiprevs=None, diffopts=None): |
36924
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
494 """Core algorithm for filectx.annotate() |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
495 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
496 `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:
36923
diff
changeset
|
497 """ |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
498 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
499 # 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:
36923
diff
changeset
|
500 # bit recursion-hostile. Instead we do an iterative |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
501 # depth-first search. |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
502 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
503 # 1st DFS pre-calculates pcache and needed |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
504 visit = [base] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
505 pcache = {} |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
506 needed = {base: 1} |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
507 while visit: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
508 f = visit.pop() |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
509 if f in pcache: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
510 continue |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
511 pl = parents(f) |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
512 pcache[f] = pl |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
513 for p in pl: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
514 needed[p] = needed.get(p, 0) + 1 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
515 if p not in pcache: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
516 visit.append(p) |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
517 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
518 # 2nd DFS does the actual annotate |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
519 visit[:] = [base] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
520 hist = {} |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
521 while visit: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
522 f = visit[-1] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
523 if f in hist: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
524 visit.pop() |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
525 continue |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
526 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
527 ready = True |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
528 pl = pcache[f] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
529 for p in pl: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
530 if p not in hist: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
531 ready = False |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
532 visit.append(p) |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
533 if ready: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
534 visit.pop() |
37068
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37067
diff
changeset
|
535 curr = _decoratelines(f.data(), f) |
36924
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
536 skipchild = False |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
537 if skiprevs is not None: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
538 skipchild = f._changeid in skiprevs |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
539 curr = _annotatepair([hist[p] for p in pl], f, curr, skipchild, |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
540 diffopts) |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
541 for p in pl: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
542 if needed[p] == 1: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
543 del hist[p] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
544 del needed[p] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
545 else: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
546 needed[p] -= 1 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
547 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
548 hist[f] = curr |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
549 del pcache[f] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
550 |
37067
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36941
diff
changeset
|
551 a = hist[base] |
37069
b33b91ca2ec2
annotate: pack line content into annotateline object (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37068
diff
changeset
|
552 return [annotateline(*r) for r in zip(a.fctxs, a.linenos, a.skips, |
b33b91ca2ec2
annotate: pack line content into annotateline object (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37068
diff
changeset
|
553 mdiff.splitnewlines(a.text))] |
36924
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36923
diff
changeset
|
554 |
32921
27932a76a88d
dagop: split module hosting DAG-related algorithms from revset
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
555 def toposort(revs, parentsfunc, firstbranch=()): |
29347
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
556 """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
|
557 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
558 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
|
559 the number of parallel branches and their interleaving. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
560 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
561 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
|
562 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
563 o 4 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
564 | |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
565 o 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
566 | |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
567 | o 3 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
568 | | |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
569 | o 2 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
570 |/ |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
571 o 0 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
572 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
573 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
|
574 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
|
575 occur behind a merge. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
576 """ |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
577 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
578 ### Quick summary of the algorithm |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
579 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
580 # 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
|
581 # 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
|
582 # "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
|
583 # branches with interleaved revisions. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
584 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
585 # During iteration revs are split into two groups: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
586 # A) revision already emitted |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
587 # 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
|
588 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
589 # for each REV, we do the following logic: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
590 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
591 # 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
|
592 # 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
|
593 # 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
|
594 # group first. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
595 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
596 # 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
|
597 # 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
|
598 # now awaiting for REV.parents() to be available. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
599 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
600 # 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
|
601 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
602 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
603 # 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
|
604 # puts it in group (A) from above). |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
605 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
606 revs.sort(reverse=True) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
607 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
608 # 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
|
609 # 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
|
610 # need to delay the revisions that reference them. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
611 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
612 # 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
|
613 # 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
|
614 # emitted. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
615 unblocked = set(firstbranch) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
616 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
617 # 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
|
618 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
619 # (revs: lists of revs waiting to be displayed, |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
620 # 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
|
621 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
622 # 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
|
623 # 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
|
624 # 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
|
625 # 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
|
626 # 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
|
627 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
628 # 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
|
629 # 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
|
630 # 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
|
631 # 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
|
632 # 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
|
633 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
634 # 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
|
635 # 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
|
636 # '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
|
637 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
638 # 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
|
639 # 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
|
640 groups = [([], unblocked)] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
641 pendingheap = [] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
642 pendingset = set() |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
643 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
644 heapq.heapify(pendingheap) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
645 heappop = heapq.heappop |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
646 heappush = heapq.heappush |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
647 for currentrev in revs: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
648 # 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
|
649 if currentrev not in pendingset: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
650 heappush(pendingheap, -currentrev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
651 pendingset.add(currentrev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
652 # 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
|
653 # processed. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
654 rev = None |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
655 while rev != currentrev: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
656 rev = -heappop(pendingheap) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
657 pendingset.remove(rev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
658 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
659 # 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
|
660 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
|
661 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
662 if matching: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
663 # 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
|
664 # on the same revision. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
665 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
666 # 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
|
667 # observed. For example, given two groups: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
668 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
669 # revs [5, 4] waiting for 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
670 # revs [3, 2] waiting for 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
671 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
672 # 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
|
673 # 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
|
674 # 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
|
675 # 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
|
676 # 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
|
677 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
678 # 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
|
679 # 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
|
680 # 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
|
681 # 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
|
682 targetidx = matching.pop(0) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
683 trevs, tparents = groups[targetidx] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
684 for i in matching: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
685 gr = groups[i] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
686 trevs.extend(gr[0]) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
687 tparents |= gr[1] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
688 # 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
|
689 # (starting from the last subgroup for performance and |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
690 # sanity reasons) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
691 for i in reversed(matching): |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
692 del groups[i] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
693 else: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
694 # 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
|
695 targetidx = len(groups) |
32331
bd872f64a8ba
cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents:
32085
diff
changeset
|
696 groups.append(([], {rev})) |
29347
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
697 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
698 gr = groups[targetidx] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
699 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
700 # 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
|
701 # 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
|
702 # that relied on this rev must precede it. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
703 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
704 # 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
|
705 # new nodes. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
706 if rev == currentrev: # only display stuff in rev |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
707 gr[0].append(rev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
708 gr[1].remove(rev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
709 parents = [p for p in parentsfunc(rev) if p > node.nullrev] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
710 gr[1].update(parents) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
711 for p in parents: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
712 if p not in pendingset: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
713 pendingset.add(p) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
714 heappush(pendingheap, -p) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
715 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
716 # Look for a subgroup to display |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
717 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
718 # 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
|
719 # 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
|
720 # 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
|
721 # 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
|
722 # subgroup. The heuristic could probably be better. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
723 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
724 # 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
|
725 # 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
|
726 # well. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
727 if not unblocked: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
728 if len(groups) > 1: # display other subset |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
729 targetidx = 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
730 gr = groups[1] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
731 elif not gr[1] & unblocked: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
732 gr = None |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
733 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
734 if gr is not None: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
735 # 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
|
736 # subgroup |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
737 unblocked |= gr[1] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
738 # output all revisions in the subgroup |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
739 for r in gr[0]: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
740 yield r |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
741 # delete the subgroup that you just output |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
742 # 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
|
743 if targetidx: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
744 del groups[targetidx] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
745 else: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
746 gr[0][:] = [] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
747 # 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
|
748 # iterate over |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
749 for g in groups: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
750 for r in g[0]: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
751 yield r |
39212
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38823
diff
changeset
|
752 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38823
diff
changeset
|
753 def headrevs(revs, parentsfn): |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38823
diff
changeset
|
754 """Resolve the set of heads from a set of revisions. |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38823
diff
changeset
|
755 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38823
diff
changeset
|
756 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:
38823
diff
changeset
|
757 revision number and returns an iterable of parent revision numbers, possibly |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38823
diff
changeset
|
758 including nullrev. |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38823
diff
changeset
|
759 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38823
diff
changeset
|
760 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:
38823
diff
changeset
|
761 subset. |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38823
diff
changeset
|
762 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38823
diff
changeset
|
763 ``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:
38823
diff
changeset
|
764 the input set. |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38823
diff
changeset
|
765 """ |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38823
diff
changeset
|
766 headrevs = set(revs) |
41277
61f9ef23a12f
dagop: minor python optimization to `headrevs`
Boris Feld <boris.feld@octobus.net>
parents:
40001
diff
changeset
|
767 parents = set([node.nullrev]) |
61f9ef23a12f
dagop: minor python optimization to `headrevs`
Boris Feld <boris.feld@octobus.net>
parents:
40001
diff
changeset
|
768 up = parents.update |
39212
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38823
diff
changeset
|
769 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38823
diff
changeset
|
770 for rev in revs: |
41277
61f9ef23a12f
dagop: minor python optimization to `headrevs`
Boris Feld <boris.feld@octobus.net>
parents:
40001
diff
changeset
|
771 up(parentsfn(rev)) |
61f9ef23a12f
dagop: minor python optimization to `headrevs`
Boris Feld <boris.feld@octobus.net>
parents:
40001
diff
changeset
|
772 headrevs.difference_update(parents) |
39212
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38823
diff
changeset
|
773 return headrevs |
39214
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
774 |
40001
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
775 def headrevssubset(revsfn, parentrevsfn, startrev=None, stoprevs=None): |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
776 """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:
40000
diff
changeset
|
777 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
778 ``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:
40000
diff
changeset
|
779 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:
40000
diff
changeset
|
780 returns revision numbers starting at that number. |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
781 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
782 ``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:
40000
diff
changeset
|
783 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:
40000
diff
changeset
|
784 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
785 ``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:
40000
diff
changeset
|
786 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
787 ``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:
40000
diff
changeset
|
788 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:
40000
diff
changeset
|
789 collection will be heads. |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
790 """ |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
791 if startrev is None: |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
792 startrev = nullrev |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
793 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
794 stoprevs = set(stoprevs or []) |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
795 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
796 reachable = {startrev} |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
797 heads = {startrev} |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
798 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
799 for rev in revsfn(start=startrev + 1): |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
800 for prev in parentrevsfn(rev): |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
801 if prev in reachable: |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
802 if rev not in stoprevs: |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
803 reachable.add(rev) |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
804 heads.add(rev) |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
805 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
806 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:
40000
diff
changeset
|
807 heads.remove(prev) |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
808 |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
809 return heads |
8af835af0a85
dagop: extract DAG local heads functionality from revlog
Gregory Szorc <gregory.szorc@gmail.com>
parents:
40000
diff
changeset
|
810 |
39214
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
811 def linearize(revs, parentsfn): |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
812 """Linearize and topologically sort a list of revisions. |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
813 |
39623
5362c96f2feb
dagop: fix typo spotted while doing unrelated investigation
Augie Fackler <augie@google.com>
parents:
39214
diff
changeset
|
814 The linearization process tries to create long runs of revs where a child |
39214
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
815 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:
39212
diff
changeset
|
816 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:
39212
diff
changeset
|
817 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:
39212
diff
changeset
|
818 itself to the output list. |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
819 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
820 Returns a list of revision numbers. |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
821 """ |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
822 visit = list(sorted(headrevs(revs, parentsfn), reverse=True)) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
823 finished = set() |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
824 result = [] |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
825 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
826 while visit: |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
827 rev = visit.pop() |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
828 if rev < 0: |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
829 rev = -rev - 1 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
830 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
831 if rev not in finished: |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
832 result.append(rev) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
833 finished.add(rev) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
834 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
835 else: |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
836 visit.append(-rev - 1) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
837 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
838 for prev in parentsfn(rev): |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
839 if prev == node.nullrev or prev not in revs or prev in finished: |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
840 continue |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
841 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
842 visit.append(prev) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
843 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
844 assert len(result) == len(revs) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
845 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39212
diff
changeset
|
846 return result |