annotate mercurial/dagop.py @ 46414:16c18d5e5dc8

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