Mercurial > public > mercurial-scm > hg-stable

annotate mercurial/dagop.py @ 33014:c7da57bbae96

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
dagop: comment why revancestors() doesn't heapify input revs at once I wondered why we're doing this complicated stuff without noticing the input revs may be iterated lazily in descending order. c1f666e27345 showed why.
author Yuya Nishihara <yuya@tcha.org>
date Sun, 18 Jun 2017 17:16:02 +0900
parents b9e2269aeff8
children 08e2793d9f65
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
32921
27932a76a88d dagop: split module hosting DAG-related algorithms from revset
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
1 # dagop.py - graph ancestry and topology algorithm for revset
11275
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,
32922
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
14 mdiff,
25971
e9cd028f2dff revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25929
diff changeset
15 node,
32922
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
16 patch,
30913
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
30913
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
33013
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
23 def _genrevancestors(repo, revs, followfirst):
24306
6ddc86eedc3b style: kill ersatz if-else ternary operators
Jordi Guti?rrez Hermoso <jordigh@octave.org>
parents: 24219
diff changeset
24 if followfirst:
6ddc86eedc3b style: kill ersatz if-else ternary operators
Jordi Guti?rrez Hermoso <jordigh@octave.org>
parents: 24219
diff changeset
25 cut = 1
6ddc86eedc3b style: kill ersatz if-else ternary operators
Jordi Guti?rrez Hermoso <jordigh@octave.org>
parents: 24219
diff changeset
26 else:
6ddc86eedc3b style: kill ersatz if-else ternary operators
Jordi Guti?rrez Hermoso <jordigh@octave.org>
parents: 24219
diff changeset
27 cut = None
16409
2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents: 16402
diff changeset
28 cl = repo.changelog
33014
c7da57bbae96 dagop: comment why revancestors() doesn't heapify input revs at once
Yuya Nishihara <yuya@tcha.org>
parents: 33013
diff changeset
29
c7da57bbae96 dagop: comment why revancestors() doesn't heapify input revs at once
Yuya Nishihara <yuya@tcha.org>
parents: 33013
diff changeset
30 # load input revs lazily to heap so earlier revisions can be yielded
c7da57bbae96 dagop: comment why revancestors() doesn't heapify input revs at once
Yuya Nishihara <yuya@tcha.org>
parents: 33013
diff changeset
31 # without fully computing the input revs
33013
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
32 revs.sort(reverse=True)
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
33 irevs = iter(revs)
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
34 h = []
20690
13c0327eeb6f revset: changed ancestors revset to return lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20659
diff changeset
35
33013
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
36 inputrev = next(irevs, None)
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
37 if inputrev is not None:
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
38 heapq.heappush(h, -inputrev)
20691
c1f666e27345 revset: optimized _revancestors method based on order of revisions
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20690
diff changeset
39
33013
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
40 seen = set()
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
41 while h:
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
42 current = -heapq.heappop(h)
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
43 if current == inputrev:
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
44 inputrev = next(irevs, None)
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
45 if inputrev is not None:
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
46 heapq.heappush(h, -inputrev)
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
47 if current not in seen:
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
48 seen.add(current)
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
49 yield current
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
50 try:
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
51 for parent in cl.parentrevs(current)[:cut]:
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
52 if parent != node.nullrev:
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
53 heapq.heappush(h, -parent)
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
54 except error.WdirUnsupported:
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
55 for parent in repo[current].parents()[:cut]:
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
56 if parent.rev() != node.nullrev:
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
57 heapq.heappush(h, -parent.rev())
20690
13c0327eeb6f revset: changed ancestors revset to return lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20659
diff changeset
58
33013
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
59 def revancestors(repo, revs, followfirst):
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
60 """Like revlog.ancestors(), but supports followfirst."""
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
61 gen = _genrevancestors(repo, revs, followfirst)
b9e2269aeff8 dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents: 32922
diff changeset
62 return generatorset(gen, iterasc=False)
16409
2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents: 16402
diff changeset
63
32921
27932a76a88d dagop: split module hosting DAG-related algorithms from revset
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
64 def revdescendants(repo, revs, followfirst):
16409
2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents: 16402
diff changeset
65 """Like revlog.descendants() but supports followfirst."""
24306
6ddc86eedc3b style: kill ersatz if-else ternary operators
Jordi Guti?rrez Hermoso <jordigh@octave.org>
parents: 24219
diff changeset
66 if followfirst:
6ddc86eedc3b style: kill ersatz if-else ternary operators
Jordi Guti?rrez Hermoso <jordigh@octave.org>
parents: 24219
diff changeset
67 cut = 1
6ddc86eedc3b style: kill ersatz if-else ternary operators
Jordi Guti?rrez Hermoso <jordigh@octave.org>
parents: 24219
diff changeset
68 else:
6ddc86eedc3b style: kill ersatz if-else ternary operators
Jordi Guti?rrez Hermoso <jordigh@octave.org>
parents: 24219
diff changeset
69 cut = None
16409
2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents: 16402
diff changeset
70
20692
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
71 def iterate():
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
72 cl = repo.changelog
25549
f93ff3ab8d14 revset: mark spots that should use 'smartset.min()'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25548
diff changeset
73 # XXX this should be 'parentset.min()' assuming 'parentset' is a
f93ff3ab8d14 revset: mark spots that should use 'smartset.min()'
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25548
diff changeset
74 # smartset (and if it is not, it should.)
20692
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
75 first = min(revs)
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
76 nullrev = node.nullrev
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
77 if first == nullrev:
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
78 # Are there nodes with a null first parent and a non-null
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
79 # second one? Maybe. Do we care? Probably not.
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
80 for i in cl:
16409
2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents: 16402
diff changeset
81 yield i
20692
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
82 else:
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
83 seen = set(revs)
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
84 for i in cl.revs(first + 1):
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
85 for x in cl.parentrevs(i)[:cut]:
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
86 if x != nullrev and x in seen:
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
87 seen.add(i)
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
88 yield i
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
89 break
7af341082b76 revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents: 20691
diff changeset
90
22795
c21342159fad generatorset: drop the leading underscore in the class name
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 22794
diff changeset
91 return generatorset(iterate(), iterasc=True)
16409
2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents: 16402
diff changeset
92
26095
6eed95ca4c03 revset: mark reachablerootspure as private
Yuya Nishihara <yuya@tcha.org>
parents: 26094
diff changeset
93 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
94 """return (heads(::<roots> and ::<heads>))
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
95
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
96 If includepath is True, return (<roots>::<heads>)."""
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
97 if not roots:
26094
df41c7be16d6 reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents: 26093
diff changeset
98 return []
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
99 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
100 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
101 visit = list(heads)
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
102 reachable = set()
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
103 seen = {}
25566
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
104 # 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
105 reached = reachable.add
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
106 dovisit = visit.append
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
107 nextvisit = visit.pop
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
108 # 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
109 # sys.getrecursionlimit()
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
110 while visit:
25566
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 25554
diff changeset
111 rev = nextvisit()
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
112 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
113 reached(rev)
26002
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
114 if not includepath:
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
115 continue
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
116 parents = parentrevs(rev)
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
117 seen[rev] = parents
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
118 for parent in parents:
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
119 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
120 dovisit(parent)
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
121 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
122 return baseset()
26002
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
123 if not includepath:
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents: 26001
diff changeset
124 return reachable
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
125 for rev in sorted(seen):
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
126 for parent in seen[rev]:
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
127 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
128 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
129 return reachable
16862
b6efeb27e733 revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents: 16861
diff changeset
130
26006
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
131 def reachableroots(repo, roots, heads, includepath=False):
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
132 """return (heads(::<roots> and ::<heads>))
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
133
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
134 If includepath is True, return (<roots>::<heads>)."""
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
135 if not roots:
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
136 return baseset()
26093
204131131766 reachableroots: use smartset min
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 26091
diff changeset
137 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
138 roots = list(roots)
26006
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
139 heads = list(heads)
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
140 try:
26094
df41c7be16d6 reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents: 26093
diff changeset
141 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
142 except AttributeError:
26095
6eed95ca4c03 revset: mark reachablerootspure as private
Yuya Nishihara <yuya@tcha.org>
parents: 26094
diff changeset
143 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
144 revs = baseset(revs)
df41c7be16d6 reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents: 26093
diff changeset
145 revs.sort()
df41c7be16d6 reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents: 26093
diff changeset
146 return revs
26006
1ffd97cbf9a2 reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents: 26002
diff changeset
147
32922
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
148 def _changesrange(fctx1, fctx2, linerange2, diffopts):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
149 """Return `(diffinrange, linerange1)` where `diffinrange` is True
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
150 if diff from fctx2 to fctx1 has changes in linerange2 and
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
151 `linerange1` is the new line range for fctx1.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
152 """
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
153 blocks = mdiff.allblocks(fctx1.data(), fctx2.data(), diffopts)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
154 filteredblocks, linerange1 = mdiff.blocksinrange(blocks, linerange2)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
155 diffinrange = any(stype == '!' for _, stype in filteredblocks)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
156 return diffinrange, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
157
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
158 def blockancestors(fctx, fromline, toline, followfirst=False):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
159 """Yield ancestors of `fctx` with respect to the block of lines within
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
160 `fromline`-`toline` range.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
161 """
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
162 diffopts = patch.diffopts(fctx._repo.ui)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
163 introrev = fctx.introrev()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
164 if fctx.rev() != introrev:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
165 fctx = fctx.filectx(fctx.filenode(), changeid=introrev)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
166 visit = {(fctx.linkrev(), fctx.filenode()): (fctx, (fromline, toline))}
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
167 while visit:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
168 c, linerange2 = visit.pop(max(visit))
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
169 pl = c.parents()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
170 if followfirst:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
171 pl = pl[:1]
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
172 if not pl:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
173 # The block originates from the initial revision.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
174 yield c, linerange2
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
175 continue
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
176 inrange = False
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
177 for p in pl:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
178 inrangep, linerange1 = _changesrange(p, c, linerange2, diffopts)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
179 inrange = inrange or inrangep
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
180 if linerange1[0] == linerange1[1]:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
181 # Parent's linerange is empty, meaning that the block got
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
182 # introduced in this revision; no need to go futher in this
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
183 # branch.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
184 continue
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
185 # Set _descendantrev with 'c' (a known descendant) so that, when
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
186 # _adjustlinkrev is called for 'p', it receives this descendant
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
187 # (as srcrev) instead possibly topmost introrev.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
188 p._descendantrev = c.rev()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
189 visit[p.linkrev(), p.filenode()] = p, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
190 if inrange:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
191 yield c, linerange2
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
192
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
193 def blockdescendants(fctx, fromline, toline):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
194 """Yield descendants of `fctx` with respect to the block of lines within
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
195 `fromline`-`toline` range.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
196 """
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
197 # First possibly yield 'fctx' if it has changes in range with respect to
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
198 # its parents.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
199 try:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
200 c, linerange1 = next(blockancestors(fctx, fromline, toline))
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
201 except StopIteration:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
202 pass
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
203 else:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
204 if c == fctx:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
205 yield c, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
206
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
207 diffopts = patch.diffopts(fctx._repo.ui)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
208 fl = fctx.filelog()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
209 seen = {fctx.filerev(): (fctx, (fromline, toline))}
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
210 for i in fl.descendants([fctx.filerev()]):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
211 c = fctx.filectx(i)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
212 inrange = False
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
213 for x in fl.parentrevs(i):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
214 try:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
215 p, linerange2 = seen[x]
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
216 except KeyError:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
217 # nullrev or other branch
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
218 continue
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
219 inrangep, linerange1 = _changesrange(c, p, linerange2, diffopts)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
220 inrange = inrange or inrangep
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
221 # If revision 'i' has been seen (it's a merge), we assume that its
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
222 # line range is the same independently of which parents was used
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
223 # to compute it.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
224 assert i not in seen or seen[i][1] == linerange1, (
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
225 'computed line range for %s is not consistent between '
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
226 'ancestor branches' % c)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
227 seen[i] = c, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
228 if inrange:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
229 yield c, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents: 32921
diff changeset
230
32921
27932a76a88d dagop: split module hosting DAG-related algorithms from revset
Yuya Nishihara <yuya@tcha.org>
parents: 32903
diff changeset
231 def toposort(revs, parentsfunc, firstbranch=()):
29347
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
232 """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
233
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
234 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
235 the number of parallel branches and their interleaving.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
236
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
237 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
238
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
239 o 4
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
240 |
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
241 o 1
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
242 |
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
243 | o 3
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
244 | |
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
245 | o 2
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
246 |/
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
247 o 0
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
248
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
249 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
250 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
251 occur behind a merge.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
252 """
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
253
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
254 ### Quick summary of the algorithm
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
255 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
256 # 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
257 # 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
258 # "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
259 # branches with interleaved revisions.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
260 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
261 # During iteration revs are split into two groups:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
262 # A) revision already emitted
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
263 # 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
264 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
265 # for each REV, we do the following logic:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
266 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
267 # 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
268 # 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
269 # 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
270 # group first.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
271 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
272 # 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
273 # 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
274 # now awaiting for REV.parents() to be available.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
275 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
276 # 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
277 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
278 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
279 # 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
280 # puts it in group (A) from above).
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
281
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
282 revs.sort(reverse=True)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
283
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
284 # 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
285 # 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
286 # need to delay the revisions that reference them.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
287 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
288 # 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
289 # 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
290 # emitted.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
291 unblocked = set(firstbranch)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
292
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
293 # 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
294 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
295 # (revs: lists of revs waiting to be displayed,
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
296 # 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
297 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
298 # 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
299 # 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
300 # 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
301 # 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
302 # 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
303 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
304 # 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
305 # 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
306 # 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
307 # 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
308 # 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
309 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
310 # 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
311 # 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
312 # '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
313 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
314 # 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
315 # 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
316 groups = [([], unblocked)]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
317 pendingheap = []
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
318 pendingset = set()
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
319
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
320 heapq.heapify(pendingheap)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
321 heappop = heapq.heappop
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
322 heappush = heapq.heappush
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
323 for currentrev in revs:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
324 # 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
325 if currentrev not in pendingset:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
326 heappush(pendingheap, -currentrev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
327 pendingset.add(currentrev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
328 # 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
329 # processed.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
330 rev = None
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
331 while rev != currentrev:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
332 rev = -heappop(pendingheap)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
333 pendingset.remove(rev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
334
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
335 # 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
336 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
337
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
338 if matching:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
339 # 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
340 # on the same revision.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
341 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
342 # 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
343 # observed. For example, given two groups:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
344 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
345 # revs [5, 4] waiting for 1
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
346 # revs [3, 2] waiting for 1
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
347 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
348 # 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
349 # 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
350 # 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
351 # 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
352 # 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
353 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
354 # 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
355 # 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
356 # 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
357 # 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
358 targetidx = matching.pop(0)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
359 trevs, tparents = groups[targetidx]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
360 for i in matching:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
361 gr = groups[i]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
362 trevs.extend(gr[0])
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
363 tparents |= gr[1]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
364 # 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
365 # (starting from the last subgroup for performance and
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
366 # sanity reasons)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
367 for i in reversed(matching):
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
368 del groups[i]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
369 else:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
370 # 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
371 targetidx = len(groups)
32331
bd872f64a8ba cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents: 32085
diff changeset
372 groups.append(([], {rev}))
29347
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
373
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
374 gr = groups[targetidx]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
375
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
376 # 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
377 # 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
378 # that relied on this rev must precede it.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
379 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
380 # 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
381 # new nodes.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
382 if rev == currentrev: # only display stuff in rev
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
383 gr[0].append(rev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
384 gr[1].remove(rev)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
385 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
386 gr[1].update(parents)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
387 for p in parents:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
388 if p not in pendingset:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
389 pendingset.add(p)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
390 heappush(pendingheap, -p)
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
391
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
392 # Look for a subgroup to display
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
393 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
394 # 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
395 # 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
396 # 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
397 # 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
398 # subgroup. The heuristic could probably be better.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
399 #
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
400 # 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
401 # 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
402 # well.
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
403 if not unblocked:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
404 if len(groups) > 1: # display other subset
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
405 targetidx = 1
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
406 gr = groups[1]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
407 elif not gr[1] & unblocked:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
408 gr = None
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 if gr is not None:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
411 # 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
412 # subgroup
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
413 unblocked |= gr[1]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
414 # output all revisions in the subgroup
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
415 for r in gr[0]:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
416 yield r
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
417 # delete the subgroup that you just output
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
418 # 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
419 if targetidx:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
420 del groups[targetidx]
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
421 else:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
422 gr[0][:] = []
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
423 # 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
424 # iterate over
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
425 for g in groups:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
426 for r in g[0]:
98535ad46fc0 revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents: 29346
diff changeset
427 yield r