Mercurial > hg
annotate mercurial/dagop.py @ 36218:e4ccd7a69f77
httppeer: change logic around argument handling
The code to process arguments only makes sense if there are
arguments. So change an "else" to "elif args", remove an
"if" that isn't necessary, and add some docs for good measure.
Differential Revision: https://phab.mercurial-scm.org/D2214
author | Gregory Szorc <gregory.szorc@gmail.com> |
---|---|
date | Thu, 01 Feb 2018 19:32:42 -0800 |
parents | c9144396099b |
children | 7affcabf561e |
rev | line source |
---|---|
32903
27932a76a88d
dagop: split module hosting DAG-related algorithms from revset
Yuya Nishihara <yuya@tcha.org>
parents:
32885
diff
changeset
|
1 # dagop.py - graph ancestry and topology algorithm for revset |
11275 | 2 # |
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 |
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
12 from . import ( |
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
13 error, |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
14 mdiff, |
25971
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
15 node, |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
16 patch, |
30881
1be65deb3d54
smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
30850
diff
changeset
|
17 smartset, |
25971
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
18 ) |
11275 | 19 |
30881
1be65deb3d54
smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
30850
diff
changeset
|
20 baseset = smartset.baseset |
1be65deb3d54
smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
30850
diff
changeset
|
21 generatorset = smartset.generatorset |
1be65deb3d54
smartset: move set classes and related functions from revset module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
30850
diff
changeset
|
22 |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
23 # possible maximum depth between null and wdir() |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
24 _maxlogdepth = 0x80000000 |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
25 |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
26 def _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse): |
33078
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
27 """Walk DAG using 'pfunc' from the given 'revs' nodes |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
28 |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
29 'pfunc(rev)' should return the parent/child revisions of the given 'rev' |
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
30 if 'reverse' is True/False respectively. |
33078
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
31 |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
32 Scan ends at the stopdepth (exlusive) if specified. Revisions found |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
33 earlier than the startdepth are omitted. |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
34 """ |
33003
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
35 if startdepth is None: |
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
36 startdepth = 0 |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
37 if stopdepth is None: |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
38 stopdepth = _maxlogdepth |
33027
a10f5f6771f6
dagop: raise ProgrammingError if stopdepth < 0
Martin von Zweigbergk <martinvonz@google.com>
parents:
33003
diff
changeset
|
39 if stopdepth == 0: |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
40 return |
33027
a10f5f6771f6
dagop: raise ProgrammingError if stopdepth < 0
Martin von Zweigbergk <martinvonz@google.com>
parents:
33003
diff
changeset
|
41 if stopdepth < 0: |
a10f5f6771f6
dagop: raise ProgrammingError if stopdepth < 0
Martin von Zweigbergk <martinvonz@google.com>
parents:
33003
diff
changeset
|
42 raise error.ProgrammingError('negative stopdepth') |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
43 if reverse: |
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
44 heapsign = -1 # max heap |
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
45 else: |
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
46 heapsign = +1 # min heap |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
47 |
32998
c7da57bbae96
dagop: comment why revancestors() doesn't heapify input revs at once
Yuya Nishihara <yuya@tcha.org>
parents:
32997
diff
changeset
|
48 # load input revs lazily to heap so earlier revisions can be yielded |
c7da57bbae96
dagop: comment why revancestors() doesn't heapify input revs at once
Yuya Nishihara <yuya@tcha.org>
parents:
32997
diff
changeset
|
49 # without fully computing the input revs |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
50 revs.sort(reverse) |
32997
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
51 irevs = iter(revs) |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
52 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
|
53 |
32997
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
54 inputrev = next(irevs, None) |
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
55 if inputrev is not None: |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
56 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
|
57 |
33000
d3d36bcdf036
dagop: just compare with the last value to deduplicate input of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32999
diff
changeset
|
58 lastrev = None |
32999
08e2793d9f65
dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
32998
diff
changeset
|
59 while pendingheap: |
33001
92d0945a15e0
dagop: compute depth in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33000
diff
changeset
|
60 currev, curdepth = heapq.heappop(pendingheap) |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
61 currev = heapsign * currev |
32999
08e2793d9f65
dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
32998
diff
changeset
|
62 if currev == inputrev: |
32997
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
63 inputrev = next(irevs, None) |
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
64 if inputrev is not None: |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
65 heapq.heappush(pendingheap, (heapsign * inputrev, 0)) |
33003
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
66 # rescan parents until curdepth >= startdepth because queued entries |
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
67 # of the same revision are iterated from the lowest depth |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
68 foundnew = (currev != lastrev) |
33003
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
69 if foundnew and curdepth >= startdepth: |
33000
d3d36bcdf036
dagop: just compare with the last value to deduplicate input of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32999
diff
changeset
|
70 lastrev = currev |
32999
08e2793d9f65
dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
32998
diff
changeset
|
71 yield currev |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
72 pdepth = curdepth + 1 |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
73 if foundnew and pdepth < stopdepth: |
33077
58ebb38456e0
dagop: factor out pfunc from revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33076
diff
changeset
|
74 for prev in pfunc(currev): |
58ebb38456e0
dagop: factor out pfunc from revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33076
diff
changeset
|
75 if prev != node.nullrev: |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
76 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
|
77 |
35276
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35275
diff
changeset
|
78 def filectxancestors(fctxs, followfirst=False): |
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35275
diff
changeset
|
79 """Like filectx.ancestors(), but can walk from multiple files/revisions, |
35296
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
80 and includes the given fctxs themselves |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
81 |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
82 Yields (rev, {fctx, ...}) pairs in descending order. |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
83 """ |
35270
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
84 visit = {} |
35297
c9144396099b
dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35296
diff
changeset
|
85 visitheap = [] |
35274
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35273
diff
changeset
|
86 def addvisit(fctx): |
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35273
diff
changeset
|
87 rev = fctx.rev() |
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35273
diff
changeset
|
88 if rev not in visit: |
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35273
diff
changeset
|
89 visit[rev] = set() |
35297
c9144396099b
dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35296
diff
changeset
|
90 heapq.heappush(visitheap, -rev) # max heap |
35274
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35273
diff
changeset
|
91 visit[rev].add(fctx) |
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35273
diff
changeset
|
92 |
35270
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
93 if followfirst: |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
94 cut = 1 |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
95 else: |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
96 cut = None |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
97 |
35276
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35275
diff
changeset
|
98 for c in fctxs: |
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35275
diff
changeset
|
99 addvisit(c) |
35275
b4b328ea6175
dagop: put start fctx into visit dict of filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35274
diff
changeset
|
100 while visit: |
35297
c9144396099b
dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35296
diff
changeset
|
101 currev = -heapq.heappop(visitheap) |
35296
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
102 curfctxs = visit.pop(currev) |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
103 yield currev, curfctxs |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
104 for c in curfctxs: |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
105 for parent in c.parents()[:cut]: |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
106 addvisit(parent) |
35297
c9144396099b
dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35296
diff
changeset
|
107 assert not visitheap |
35296
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
108 |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
109 def filerevancestors(fctxs, followfirst=False): |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
110 """Like filectx.ancestors(), but can walk from multiple files/revisions, |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
111 and includes the given fctxs themselves |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
112 |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
113 Returns a smartset. |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
114 """ |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
115 gen = (rev for rev, _cs in filectxancestors(fctxs, followfirst)) |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
116 return generatorset(gen, iterasc=False) |
35270
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
117 |
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
118 def _genrevancestors(repo, revs, followfirst, startdepth, stopdepth, cutfunc): |
33078
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
119 if followfirst: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
120 cut = 1 |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
121 else: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
122 cut = None |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
123 cl = repo.changelog |
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
124 def plainpfunc(rev): |
33078
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
125 try: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
126 return cl.parentrevs(rev)[:cut] |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
127 except error.WdirUnsupported: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
128 return (pctx.rev() for pctx in repo[rev].parents()[:cut]) |
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
129 if cutfunc is None: |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
130 pfunc = plainpfunc |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
131 else: |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
132 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
|
133 revs = revs.filter(lambda rev: not cutfunc(rev)) |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
134 return _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse=True) |
33078
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
135 |
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
136 def revancestors(repo, revs, followfirst=False, startdepth=None, |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
137 stopdepth=None, cutfunc=None): |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
138 """Like revlog.ancestors(), but supports additional options, includes |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
139 the given revs themselves, and returns a smartset |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
140 |
33003
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
141 Scan ends at the stopdepth (exlusive) if specified. Revisions found |
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
142 earlier than the startdepth are omitted. |
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
143 |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
144 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
|
145 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
|
146 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
|
147 optimization sometimes. |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
148 |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
149 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
|
150 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
|
151 return True in this case. For example, |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
152 |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
153 D # revancestors(repo, D, cutfunc=lambda rev: rev == B) |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
154 |\ # 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
|
155 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
|
156 |/ |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
157 A |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
158 """ |
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
159 gen = _genrevancestors(repo, revs, followfirst, startdepth, stopdepth, |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
160 cutfunc) |
32997
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
161 return generatorset(gen, iterasc=False) |
16409
2cbd7dd0cc1f
graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents:
16402
diff
changeset
|
162 |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
163 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
|
164 if followfirst: |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
24219
diff
changeset
|
165 cut = 1 |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
24219
diff
changeset
|
166 else: |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
24219
diff
changeset
|
167 cut = None |
16409
2cbd7dd0cc1f
graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents:
16402
diff
changeset
|
168 |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
169 cl = repo.changelog |
33076
a76a64c78807
dagop: use smartset.min() in revdescendants() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33075
diff
changeset
|
170 first = revs.min() |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
171 nullrev = node.nullrev |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
172 if first == nullrev: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
173 # Are there nodes with a null first parent and a non-null |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
174 # second one? Maybe. Do we care? Probably not. |
33075
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
175 yield first |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
176 for i in cl: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
177 yield i |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
178 else: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
179 seen = set(revs) |
33075
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
180 for i in cl.revs(first): |
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
181 if i in seen: |
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
182 yield i |
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
183 continue |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
184 for x in cl.parentrevs(i)[:cut]: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
185 if x != nullrev and x in seen: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
186 seen.add(i) |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
187 yield i |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
188 break |
20692
7af341082b76
revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents:
20691
diff
changeset
|
189 |
33080
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
190 def _builddescendantsmap(repo, startrev, followfirst): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
191 """Build map of 'rev -> child revs', offset from startrev""" |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
192 cl = repo.changelog |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
193 nullrev = node.nullrev |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
194 descmap = [[] for _rev in xrange(startrev, len(cl))] |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
195 for currev in cl.revs(startrev + 1): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
196 p1rev, p2rev = cl.parentrevs(currev) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
197 if p1rev >= startrev: |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
198 descmap[p1rev - startrev].append(currev) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
199 if not followfirst and p2rev != nullrev and p2rev >= startrev: |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
200 descmap[p2rev - startrev].append(currev) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
201 return descmap |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
202 |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
203 def _genrevdescendantsofdepth(repo, revs, followfirst, startdepth, stopdepth): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
204 startrev = revs.min() |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
205 descmap = _builddescendantsmap(repo, startrev, followfirst) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
206 def pfunc(rev): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
207 return descmap[rev - startrev] |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
208 return _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse=False) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
209 |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
210 def revdescendants(repo, revs, followfirst, startdepth=None, stopdepth=None): |
33075
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
211 """Like revlog.descendants() but supports additional options, includes |
33080
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
212 the given revs themselves, and returns a smartset |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
213 |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
214 Scan ends at the stopdepth (exlusive) if specified. Revisions found |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
215 earlier than the startdepth are omitted. |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
216 """ |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
217 if startdepth is None and stopdepth is None: |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
218 gen = _genrevdescendants(repo, revs, followfirst) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
219 else: |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
220 gen = _genrevdescendantsofdepth(repo, revs, followfirst, |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
221 startdepth, stopdepth) |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
222 return generatorset(gen, iterasc=True) |
16409
2cbd7dd0cc1f
graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents:
16402
diff
changeset
|
223 |
26095
6eed95ca4c03
revset: mark reachablerootspure as private
Yuya Nishihara <yuya@tcha.org>
parents:
26094
diff
changeset
|
224 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
|
225 """return (heads(::<roots> and ::<heads>)) |
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
226 |
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
227 If includepath is True, return (<roots>::<heads>).""" |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
228 if not roots: |
26094
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
229 return [] |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
230 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
|
231 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
|
232 visit = list(heads) |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
233 reachable = set() |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
234 seen = {} |
25566
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
235 # 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
|
236 reached = reachable.add |
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
237 dovisit = visit.append |
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
238 nextvisit = visit.pop |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
239 # 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
|
240 # sys.getrecursionlimit() |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
241 while visit: |
25566
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
242 rev = nextvisit() |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
243 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
|
244 reached(rev) |
26002
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
245 if not includepath: |
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
246 continue |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
247 parents = parentrevs(rev) |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
248 seen[rev] = parents |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
249 for parent in parents: |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
250 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
|
251 dovisit(parent) |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
252 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
|
253 return baseset() |
26002
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
254 if not includepath: |
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
255 return reachable |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
256 for rev in sorted(seen): |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
257 for parent in seen[rev]: |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
258 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
|
259 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
|
260 return reachable |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
261 |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
262 def reachableroots(repo, roots, heads, includepath=False): |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
263 """return (heads(::<roots> and ::<heads>)) |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
264 |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
265 If includepath is True, return (<roots>::<heads>).""" |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
266 if not roots: |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
267 return baseset() |
26093
204131131766
reachableroots: use smartset min
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
26091
diff
changeset
|
268 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
|
269 roots = list(roots) |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
270 heads = list(heads) |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
271 try: |
26094
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
272 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
|
273 except AttributeError: |
26095
6eed95ca4c03
revset: mark reachablerootspure as private
Yuya Nishihara <yuya@tcha.org>
parents:
26094
diff
changeset
|
274 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
|
275 revs = baseset(revs) |
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
276 revs.sort() |
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
277 return revs |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
278 |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
279 def _changesrange(fctx1, fctx2, linerange2, diffopts): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
280 """Return `(diffinrange, linerange1)` where `diffinrange` is True |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
281 if diff from fctx2 to fctx1 has changes in linerange2 and |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
282 `linerange1` is the new line range for fctx1. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
283 """ |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
284 blocks = mdiff.allblocks(fctx1.data(), fctx2.data(), diffopts) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
285 filteredblocks, linerange1 = mdiff.blocksinrange(blocks, linerange2) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
286 diffinrange = any(stype == '!' for _, stype in filteredblocks) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
287 return diffinrange, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
288 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
289 def blockancestors(fctx, fromline, toline, followfirst=False): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
290 """Yield ancestors of `fctx` with respect to the block of lines within |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
291 `fromline`-`toline` range. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
292 """ |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
293 diffopts = patch.diffopts(fctx._repo.ui) |
35271
d90c534099b1
filectx: extract helper method to obtain filectx pointing to its introrev
Yuya Nishihara <yuya@tcha.org>
parents:
35270
diff
changeset
|
294 fctx = fctx.introfilectx() |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
295 visit = {(fctx.linkrev(), fctx.filenode()): (fctx, (fromline, toline))} |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
296 while visit: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
297 c, linerange2 = visit.pop(max(visit)) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
298 pl = c.parents() |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
299 if followfirst: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
300 pl = pl[:1] |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
301 if not pl: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
302 # The block originates from the initial revision. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
303 yield c, linerange2 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
304 continue |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
305 inrange = False |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
306 for p in pl: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
307 inrangep, linerange1 = _changesrange(p, c, linerange2, diffopts) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
308 inrange = inrange or inrangep |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
309 if linerange1[0] == linerange1[1]: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
310 # Parent's linerange is empty, meaning that the block got |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
311 # introduced in this revision; no need to go futher in this |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
312 # branch. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
313 continue |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
314 # Set _descendantrev with 'c' (a known descendant) so that, when |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
315 # _adjustlinkrev is called for 'p', it receives this descendant |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
316 # (as srcrev) instead possibly topmost introrev. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
317 p._descendantrev = c.rev() |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
318 visit[p.linkrev(), p.filenode()] = p, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
319 if inrange: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
320 yield c, linerange2 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
321 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
322 def blockdescendants(fctx, fromline, toline): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
323 """Yield descendants of `fctx` with respect to the block of lines within |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
324 `fromline`-`toline` range. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
325 """ |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
326 # First possibly yield 'fctx' if it has changes in range with respect to |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
327 # its parents. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
328 try: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
329 c, linerange1 = next(blockancestors(fctx, fromline, toline)) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
330 except StopIteration: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
331 pass |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
332 else: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
333 if c == fctx: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
334 yield c, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
335 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
336 diffopts = patch.diffopts(fctx._repo.ui) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
337 fl = fctx.filelog() |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
338 seen = {fctx.filerev(): (fctx, (fromline, toline))} |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
339 for i in fl.descendants([fctx.filerev()]): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
340 c = fctx.filectx(i) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
341 inrange = False |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
342 for x in fl.parentrevs(i): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
343 try: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
344 p, linerange2 = seen[x] |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
345 except KeyError: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
346 # nullrev or other branch |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
347 continue |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
348 inrangep, linerange1 = _changesrange(c, p, linerange2, diffopts) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
349 inrange = inrange or inrangep |
33284
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33080
diff
changeset
|
350 # If revision 'i' has been seen (it's a merge) and the line range |
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33080
diff
changeset
|
351 # previously computed differs from the one we just got, we take the |
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33080
diff
changeset
|
352 # surrounding interval. This is conservative but avoids loosing |
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33080
diff
changeset
|
353 # information. |
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33080
diff
changeset
|
354 if i in seen and seen[i][1] != linerange1: |
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33080
diff
changeset
|
355 lbs, ubs = zip(linerange1, seen[i][1]) |
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33080
diff
changeset
|
356 linerange1 = min(lbs), max(ubs) |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
357 seen[i] = c, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
358 if inrange: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
359 yield c, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
360 |
32903
27932a76a88d
dagop: split module hosting DAG-related algorithms from revset
Yuya Nishihara <yuya@tcha.org>
parents:
32885
diff
changeset
|
361 def toposort(revs, parentsfunc, firstbranch=()): |
29347
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
362 """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
|
363 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
364 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
|
365 the number of parallel branches and their interleaving. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
366 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
367 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
|
368 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
369 o 4 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
370 | |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
371 o 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
372 | |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
373 | o 3 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
374 | | |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
375 | o 2 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
376 |/ |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
377 o 0 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
378 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
379 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
|
380 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
|
381 occur behind a merge. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
382 """ |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
383 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
384 ### Quick summary of the algorithm |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
385 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
386 # 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
|
387 # 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
|
388 # "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
|
389 # branches with interleaved revisions. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
390 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
391 # During iteration revs are split into two groups: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
392 # A) revision already emitted |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
393 # 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
|
394 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
395 # for each REV, we do the following logic: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
396 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
397 # 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
|
398 # 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
|
399 # 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
|
400 # group first. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
401 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
402 # 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
|
403 # 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
|
404 # now awaiting for REV.parents() to be available. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
405 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
406 # 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
|
407 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
408 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
409 # 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
|
410 # puts it in group (A) from above). |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
411 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
412 revs.sort(reverse=True) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
413 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
414 # 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
|
415 # 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
|
416 # need to delay the revisions that reference them. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
417 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
418 # 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
|
419 # 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
|
420 # emitted. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
421 unblocked = set(firstbranch) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
422 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
423 # 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
|
424 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
425 # (revs: lists of revs waiting to be displayed, |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
426 # 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
|
427 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
428 # 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
|
429 # 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
|
430 # 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
|
431 # 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
|
432 # 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
|
433 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
434 # 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
|
435 # 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
|
436 # 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
|
437 # 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
|
438 # 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
|
439 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
440 # 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
|
441 # 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
|
442 # '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
|
443 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
444 # 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
|
445 # 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
|
446 groups = [([], unblocked)] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
447 pendingheap = [] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
448 pendingset = set() |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
449 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
450 heapq.heapify(pendingheap) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
451 heappop = heapq.heappop |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
452 heappush = heapq.heappush |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
453 for currentrev in revs: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
454 # 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
|
455 if currentrev not in pendingset: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
456 heappush(pendingheap, -currentrev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
457 pendingset.add(currentrev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
458 # 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
|
459 # processed. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
460 rev = None |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
461 while rev != currentrev: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
462 rev = -heappop(pendingheap) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
463 pendingset.remove(rev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
464 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
465 # 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
|
466 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
|
467 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
468 if matching: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
469 # 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
|
470 # on the same revision. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
471 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
472 # 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
|
473 # observed. For example, given two groups: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
474 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
475 # revs [5, 4] waiting for 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
476 # revs [3, 2] waiting for 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
477 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
478 # 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
|
479 # 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
|
480 # 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
|
481 # 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
|
482 # 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
|
483 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
484 # 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
|
485 # 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
|
486 # 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
|
487 # 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
|
488 targetidx = matching.pop(0) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
489 trevs, tparents = groups[targetidx] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
490 for i in matching: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
491 gr = groups[i] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
492 trevs.extend(gr[0]) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
493 tparents |= gr[1] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
494 # 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
|
495 # (starting from the last subgroup for performance and |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
496 # sanity reasons) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
497 for i in reversed(matching): |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
498 del groups[i] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
499 else: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
500 # 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
|
501 targetidx = len(groups) |
32291
bd872f64a8ba
cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents:
32085
diff
changeset
|
502 groups.append(([], {rev})) |
29347
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
503 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
504 gr = groups[targetidx] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
505 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
506 # 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
|
507 # 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
|
508 # that relied on this rev must precede it. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
509 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
510 # 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
|
511 # new nodes. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
512 if rev == currentrev: # only display stuff in rev |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
513 gr[0].append(rev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
514 gr[1].remove(rev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
515 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
|
516 gr[1].update(parents) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
517 for p in parents: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
518 if p not in pendingset: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
519 pendingset.add(p) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
520 heappush(pendingheap, -p) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
521 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
522 # Look for a subgroup to display |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
523 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
524 # 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
|
525 # 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
|
526 # 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
|
527 # 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
|
528 # subgroup. The heuristic could probably be better. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
529 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
530 # 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
|
531 # 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
|
532 # well. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
533 if not unblocked: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
534 if len(groups) > 1: # display other subset |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
535 targetidx = 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
536 gr = groups[1] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
537 elif not gr[1] & unblocked: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
538 gr = None |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
539 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
540 if gr is not None: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
541 # 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
|
542 # subgroup |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
543 unblocked |= gr[1] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
544 # output all revisions in the subgroup |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
545 for r in gr[0]: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
546 yield r |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
547 # delete the subgroup that you just output |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
548 # 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
|
549 if targetidx: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
550 del groups[targetidx] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
551 else: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
552 gr[0][:] = [] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
553 # 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
|
554 # iterate over |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
555 for g in groups: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
556 for r in g[0]: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
557 yield r |