Mercurial > public > mercurial-scm > hg

annotate mercurial/dagop.py @ 35274:2b348dc3239a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
dagop: change visit dict of filectxancestors() indexed solely by rev In future patches, a max heap will be used to compute the next revision to visit.
author Yuya Nishihara <yuya@tcha.org>
date Thu, 22 Sep 2016 18:11:37 +0900
parents 8dee2080f35c
children b4b328ea6175
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
2 #
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
3 # Copyright 2010 Matt Mackall <mpm@selenic.com>
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
4 #
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
5 # This software may be used and distributed according to the terms of the
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
6 # GNU General Public License version 2 or any later version.
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
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
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
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
35270
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
78 def filectxancestors(fctx, followfirst=False):
35272
70e86db6a913 dagop: yield intro filectx by filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35271
diff changeset
79 """Like filectx.ancestors(), but includes the given fctx itself"""
35270
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
80 visit = {}
35274
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents: 35273
diff changeset
81 def addvisit(fctx):
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents: 35273
diff changeset
82 rev = fctx.rev()
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents: 35273
diff changeset
83 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
84 visit[rev] = set()
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents: 35273
diff changeset
85 visit[rev].add(fctx)
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents: 35273
diff changeset
86
35270
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
87 c = fctx
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
88 if followfirst:
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
89 cut = 1
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
90 else:
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
91 cut = None
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
92
35272
70e86db6a913 dagop: yield intro filectx by filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 35271
diff changeset
93 yield c
35270
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
94 while True:
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
95 for parent in c.parents()[:cut]:
35274
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents: 35273
diff changeset
96 addvisit(parent)
35270
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
97 if not visit:
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
98 break
35274
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents: 35273
diff changeset
99 rev = max(visit)
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents: 35273
diff changeset
100 c = visit[rev].pop()
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents: 35273
diff changeset
101 if not visit[rev]:
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents: 35273
diff changeset
102 del visit[rev]
35270
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
103 yield c
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents: 34065
diff changeset
104
34065
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
105 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
106 if followfirst:
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
107 cut = 1
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
108 else:
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
109 cut = None
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
110 cl = repo.changelog
34065
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
111 def plainpfunc(rev):
33078
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
112 try:
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
113 return cl.parentrevs(rev)[:cut]
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
114 except error.WdirUnsupported:
fb663bd0243f dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents: 33077
diff changeset
115 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
116 if cutfunc is None:
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
117 pfunc = plainpfunc
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
118 else:
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
119 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
120 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
121 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
122
34065
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
123 def revancestors(repo, revs, followfirst=False, startdepth=None,
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
124 stopdepth=None, cutfunc=None):
33002
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
125 """Like revlog.ancestors(), but supports additional options, includes
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
126 the given revs themselves, and returns a smartset
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
127
33003
f63d111258da revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents: 33002
diff changeset
128 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
129 earlier than the startdepth are omitted.
34065
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
130
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
131 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
132 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
133 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
134 optimization sometimes.
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
135
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
136 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
137 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
138 return True in this case. For example,
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
139
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
140 D # revancestors(repo, D, cutfunc=lambda rev: rev == B)
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
141 |\ # 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
142 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
143 |/
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
144 A
33002
272a44cac57e revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 33001
diff changeset
145 """
34065
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
146 gen = _genrevancestors(repo, revs, followfirst, startdepth, stopdepth,
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents: 33284
diff changeset
147 cutfunc)
32997
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32904
diff changeset
148 return generatorset(gen, iterasc=False)
16409
2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents: 16402
diff changeset
149
33073
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
150 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
151 if followfirst:
6ddc86eedc3b style: kill ersatz if-else ternary operators
Jordi Guti?rrez Hermoso <jordigh@octave.org>
parents: 24219
diff changeset
152 cut = 1
6ddc86eedc3b style: kill ersatz if-else ternary operators
Jordi Guti?rrez Hermoso <jordigh@octave.org>
parents: 24219
diff changeset
153 else:
6ddc86eedc3b style: kill ersatz if-else ternary operators
Jordi Guti?rrez Hermoso <jordigh@octave.org>
parents: 24219
diff changeset
154 cut = None
16409
2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents: 16402
diff changeset
155
33073
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
156 cl = repo.changelog
33076
a76a64c78807 dagop: use smartset.min() in revdescendants() generator
Yuya Nishihara <yuya@tcha.org>
parents: 33075
diff changeset
157 first = revs.min()
33073
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
158 nullrev = node.nullrev
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
159 if first == nullrev:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
160 # 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
161 # 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
162 yield first
33073
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
163 for i in cl:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
164 yield i
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
165 else:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
166 seen = set(revs)
33075
d83b189aef83 dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents: 33073
diff changeset
167 for i in cl.revs(first):
d83b189aef83 dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents: 33073
diff changeset
168 if i in seen:
d83b189aef83 dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents: 33073
diff changeset
169 yield i
d83b189aef83 dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents: 33073
diff changeset
170 continue
33073
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
171 for x in cl.parentrevs(i)[:cut]:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
172 if x != nullrev and x in seen:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
173 seen.add(i)
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
174 yield i
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
175 break
20692
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
176
33080
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
177 def _builddescendantsmap(repo, startrev, followfirst):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
178 """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
179 cl = repo.changelog
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
180 nullrev = node.nullrev
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
181 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
182 for currev in cl.revs(startrev + 1):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
183 p1rev, p2rev = cl.parentrevs(currev)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
184 if p1rev >= startrev:
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
185 descmap[p1rev - startrev].append(currev)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
186 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
187 descmap[p2rev - startrev].append(currev)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
188 return descmap
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
189
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
190 def _genrevdescendantsofdepth(repo, revs, followfirst, startdepth, stopdepth):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
191 startrev = revs.min()
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
192 descmap = _builddescendantsmap(repo, startrev, followfirst)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
193 def pfunc(rev):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
194 return descmap[rev - startrev]
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
195 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
196
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
197 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
198 """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
199 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
200
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
201 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
202 earlier than the startdepth are omitted.
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
203 """
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
204 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
205 gen = _genrevdescendants(repo, revs, followfirst)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
206 else:
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
207 gen = _genrevdescendantsofdepth(repo, revs, followfirst,
a53bfc2845f2 revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents: 33079
diff changeset
208 startdepth, stopdepth)
33073
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents: 33027
diff changeset
209 return generatorset(gen, iterasc=True)
16409
2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents: 16402
diff changeset
210
26095
6eed95ca4c03 revset: mark reachablerootspure as private
Yuya Nishihara <yuya@tcha.org>
parents: 26094
diff changeset
211 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
212 """return (heads(::<roots> and ::<heads>))
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
213
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
214 If includepath is True, return (<roots>::<heads>)."""
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
215 if not roots:
26094
df41c7be16d6 reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents: 26093
diff changeset
216 return []
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
217 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
218 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
219 visit = list(heads)
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
220 reachable = set()
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
221 seen = {}
25566
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
222 # 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
223 reached = reachable.add
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
224 dovisit = visit.append
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
225 nextvisit = visit.pop
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
226 # 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
227 # sys.getrecursionlimit()
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
228 while visit:
25566
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
229 rev = nextvisit()
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
230 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
231 reached(rev)
26002
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
232 if not includepath:
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
233 continue
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
234 parents = parentrevs(rev)
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
235 seen[rev] = parents
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
236 for parent in parents:
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
237 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
238 dovisit(parent)
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
239 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
240 return baseset()
26002
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
241 if not includepath:
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
242 return reachable
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
243 for rev in sorted(seen):
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
244 for parent in seen[rev]:
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
245 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
246 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
247 return reachable
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
248
26006
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
249 def reachableroots(repo, roots, heads, includepath=False):
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
250 """return (heads(::<roots> and ::<heads>))
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
251
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
252 If includepath is True, return (<roots>::<heads>)."""
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
253 if not roots:
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
254 return baseset()
26093
204131131766 reachableroots: use smartset min
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 26091
diff changeset
255 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
256 roots = list(roots)
26006
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
257 heads = list(heads)
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
258 try:
26094
df41c7be16d6 reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents: 26093
diff changeset
259 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
260 except AttributeError:
26095
6eed95ca4c03 revset: mark reachablerootspure as private
Yuya Nishihara <yuya@tcha.org>
parents: 26094
diff changeset
261 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
262 revs = baseset(revs)
df41c7be16d6 reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents: 26093
diff changeset
263 revs.sort()
df41c7be16d6 reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents: 26093
diff changeset
264 return revs
26006
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
265
32904
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
266 def _changesrange(fctx1, fctx2, linerange2, diffopts):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
267 """Return `(diffinrange, linerange1)` where `diffinrange` is True
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
268 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
269 `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
270 """
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
271 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
272 filteredblocks, linerange1 = mdiff.blocksinrange(blocks, linerange2)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
273 diffinrange = any(stype == '!' for _, stype in filteredblocks)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
274 return diffinrange, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
275
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
276 def blockancestors(fctx, fromline, toline, followfirst=False):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
277 """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
278 `fromline`-`toline` range.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
279 """
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
280 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
281 fctx = fctx.introfilectx()
32904
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
282 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
283 while visit:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
284 c, linerange2 = visit.pop(max(visit))
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
285 pl = c.parents()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
286 if followfirst:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
287 pl = pl[:1]
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
288 if not pl:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
289 # The block originates from the initial revision.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
290 yield c, linerange2
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
291 continue
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
292 inrange = False
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
293 for p in pl:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
294 inrangep, linerange1 = _changesrange(p, c, linerange2, diffopts)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
295 inrange = inrange or inrangep
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
296 if linerange1[0] == linerange1[1]:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
297 # 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
298 # 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
299 # branch.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
300 continue
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
301 # 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
302 # _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
303 # (as srcrev) instead possibly topmost introrev.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
304 p._descendantrev = c.rev()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
305 visit[p.linkrev(), p.filenode()] = p, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
306 if inrange:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
307 yield c, linerange2
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
308
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
309 def blockdescendants(fctx, fromline, toline):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
310 """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
311 `fromline`-`toline` range.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
312 """
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
313 # 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
314 # its parents.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
315 try:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
316 c, linerange1 = next(blockancestors(fctx, fromline, toline))
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
317 except StopIteration:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
318 pass
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
319 else:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
320 if c == fctx:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
321 yield c, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
322
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
323 diffopts = patch.diffopts(fctx._repo.ui)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
324 fl = fctx.filelog()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
325 seen = {fctx.filerev(): (fctx, (fromline, toline))}
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
326 for i in fl.descendants([fctx.filerev()]):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
327 c = fctx.filectx(i)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
328 inrange = False
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
329 for x in fl.parentrevs(i):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
330 try:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
331 p, linerange2 = seen[x]
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
332 except KeyError:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
333 # nullrev or other branch
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
334 continue
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
335 inrangep, linerange1 = _changesrange(c, p, linerange2, diffopts)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
336 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
337 # 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
338 # 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
339 # 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
340 # information.
b2670290eab4 followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents: 33080
diff changeset
341 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
342 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
343 linerange1 = min(lbs), max(ubs)
32904
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
344 seen[i] = c, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
345 if inrange:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
346 yield c, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
347
32903
27932a76a88d dagop: split module hosting DAG-related algorithms from revset
Yuya Nishihara <yuya@tcha.org>
parents: 32885
diff changeset
348 def toposort(revs, parentsfunc, firstbranch=()):
29347
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
349 """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
350
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
351 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
352 the number of parallel branches and their interleaving.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
353
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
354 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
355
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
356 o 4
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
357 |
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
358 o 1
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
359 |
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
360 | o 3
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
361 | |
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
362 | o 2
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 o 0
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
365
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
366 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
367 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
368 occur behind a merge.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
369 """
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 ### Quick summary of the algorithm
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 # 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
374 # 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
375 # "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
376 # branches with interleaved revisions.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
377 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
378 # During iteration revs are split into two groups:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
379 # A) revision already emitted
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
380 # 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
381 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
382 # for each REV, we do the following logic:
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 # 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
385 # 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
386 # 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
387 # group first.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
388 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
389 # 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
390 # 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
391 # now awaiting for REV.parents() to be available.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
392 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
393 # 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
394 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
395 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
396 # 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
397 # puts it in group (A) from above).
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
398
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
399 revs.sort(reverse=True)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
400
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
401 # 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
402 # 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
403 # need to delay the revisions that reference them.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
404 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
405 # 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
406 # 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
407 # emitted.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
408 unblocked = set(firstbranch)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
409
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
410 # 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
411 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
412 # (revs: lists of revs waiting to be displayed,
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
413 # 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
414 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
415 # 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
416 # 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
417 # 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
418 # 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
419 # 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
420 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
421 # 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
422 # 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
423 # 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
424 # 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
425 # 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
426 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
427 # 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
428 # 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
429 # '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
430 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
431 # 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
432 # 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
433 groups = [([], unblocked)]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
434 pendingheap = []
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
435 pendingset = set()
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
436
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
437 heapq.heapify(pendingheap)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
438 heappop = heapq.heappop
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
439 heappush = heapq.heappush
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
440 for currentrev in revs:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
441 # 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
442 if currentrev not in pendingset:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
443 heappush(pendingheap, -currentrev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
444 pendingset.add(currentrev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
445 # 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
446 # processed.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
447 rev = None
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
448 while rev != currentrev:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
449 rev = -heappop(pendingheap)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
450 pendingset.remove(rev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
451
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
452 # 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
453 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
454
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
455 if matching:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
456 # 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
457 # on the same revision.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
458 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
459 # 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
460 # observed. For example, given two groups:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
461 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
462 # revs [5, 4] waiting for 1
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
463 # revs [3, 2] waiting for 1
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 # 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
466 # 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
467 # 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
468 # 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
469 # 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
470 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
471 # 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
472 # 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
473 # 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
474 # 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
475 targetidx = matching.pop(0)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
476 trevs, tparents = groups[targetidx]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
477 for i in matching:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
478 gr = groups[i]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
479 trevs.extend(gr[0])
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
480 tparents |= gr[1]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
481 # 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
482 # (starting from the last subgroup for performance and
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
483 # sanity reasons)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
484 for i in reversed(matching):
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
485 del groups[i]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
486 else:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
487 # 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
488 targetidx = len(groups)
32291
bd872f64a8ba cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents: 32085
diff changeset
489 groups.append(([], {rev}))
29347
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
490
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
491 gr = groups[targetidx]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
492
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
493 # 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
494 # 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
495 # that relied on this rev must precede it.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
496 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
497 # 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
498 # new nodes.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
499 if rev == currentrev: # only display stuff in rev
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
500 gr[0].append(rev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
501 gr[1].remove(rev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
502 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
503 gr[1].update(parents)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
504 for p in parents:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
505 if p not in pendingset:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
506 pendingset.add(p)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
507 heappush(pendingheap, -p)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
508
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
509 # Look for a subgroup to display
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
510 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
511 # 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
512 # 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
513 # 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
514 # 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
515 # subgroup. The heuristic could probably be better.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
516 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
517 # 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
518 # 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
519 # well.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
520 if not unblocked:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
521 if len(groups) > 1: # display other subset
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
522 targetidx = 1
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
523 gr = groups[1]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
524 elif not gr[1] & unblocked:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
525 gr = None
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
526
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
527 if gr is not None:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
528 # 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
529 # subgroup
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
530 unblocked |= gr[1]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
531 # output all revisions in the subgroup
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
532 for r in gr[0]:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
533 yield r
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
534 # delete the subgroup that you just output
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
535 # 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
536 if targetidx:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
537 del groups[targetidx]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
538 else:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
539 gr[0][:] = []
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
540 # 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
541 # iterate over
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
542 for g in groups:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
543 for r in g[0]:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
544 yield r