Mercurial > hg
annotate mercurial/dagop.py @ 39583:ee1e74ee037c
formatter: fill missing resources by formatter, not by resource mapper
While working on demand loading of ctx/fctx objects, I found it's weird
to support lookup in both directions. For instance, fctx can be loaded
from (ctx, path) pair, but ctx may also be derived from fctx.changectx()
in the original mapping. If the original mapping has had fctx but no ctx,
and if the new mapping provides {path}, we can't be sure if fctx should be
updated by fctx'.changectx()[path] or not.
This patch simply drops the support for the resolution in fctx -> ctx -> repo
direction.
author | Yuya Nishihara <yuya@tcha.org> |
---|---|
date | Sat, 01 Sep 2018 13:21:45 +0900 |
parents | 0a934ee94f09 |
children | 5362c96f2feb |
rev | line source |
---|---|
32903
27932a76a88d
dagop: split module hosting DAG-related algorithms from revset
Yuya Nishihara <yuya@tcha.org>
parents:
32885
diff
changeset
|
1 # dagop.py - graph ancestry and topology algorithm for revset |
11275 | 2 # |
3 # Copyright 2010 Matt Mackall <mpm@selenic.com> | |
4 # | |
5 # This software may be used and distributed according to the terms of the | |
6 # GNU General Public License version 2 or any later version. | |
7 | |
25971
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
8 from __future__ import absolute_import |
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
9 |
20690
13c0327eeb6f
revset: changed ancestors revset to return lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents:
20659
diff
changeset
|
10 import heapq |
25971
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
11 |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
12 from .thirdparty import ( |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
13 attr, |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
14 ) |
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, |
25971
e9cd028f2dff
revset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
25929
diff
changeset
|
18 node, |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
19 patch, |
36918
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
20 pycompat, |
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 | 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() |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
28 _maxlogdepth = 0x80000000 |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
29 |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
30 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
|
31 """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
|
32 |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
33 '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
|
34 if 'reverse' is True/False respectively. |
33078
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
35 |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
36 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
|
37 earlier than the startdepth are omitted. |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
38 """ |
33003
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
39 if startdepth is None: |
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
40 startdepth = 0 |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
41 if stopdepth is None: |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
42 stopdepth = _maxlogdepth |
33027
a10f5f6771f6
dagop: raise ProgrammingError if stopdepth < 0
Martin von Zweigbergk <martinvonz@google.com>
parents:
33003
diff
changeset
|
43 if stopdepth == 0: |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
44 return |
33027
a10f5f6771f6
dagop: raise ProgrammingError if stopdepth < 0
Martin von Zweigbergk <martinvonz@google.com>
parents:
33003
diff
changeset
|
45 if stopdepth < 0: |
a10f5f6771f6
dagop: raise ProgrammingError if stopdepth < 0
Martin von Zweigbergk <martinvonz@google.com>
parents:
33003
diff
changeset
|
46 raise error.ProgrammingError('negative stopdepth') |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
47 if reverse: |
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
48 heapsign = -1 # max heap |
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
49 else: |
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
50 heapsign = +1 # min heap |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
51 |
32998
c7da57bbae96
dagop: comment why revancestors() doesn't heapify input revs at once
Yuya Nishihara <yuya@tcha.org>
parents:
32997
diff
changeset
|
52 # 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
|
53 # 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
|
54 revs.sort(reverse) |
32997
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
55 irevs = iter(revs) |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
56 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
|
57 |
32997
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
58 inputrev = next(irevs, None) |
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
59 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
|
60 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
|
61 |
33000
d3d36bcdf036
dagop: just compare with the last value to deduplicate input of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32999
diff
changeset
|
62 lastrev = None |
32999
08e2793d9f65
dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
32998
diff
changeset
|
63 while pendingheap: |
33001
92d0945a15e0
dagop: compute depth in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33000
diff
changeset
|
64 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
|
65 currev = heapsign * currev |
32999
08e2793d9f65
dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
32998
diff
changeset
|
66 if currev == inputrev: |
32997
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
67 inputrev = next(irevs, None) |
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
68 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
|
69 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
|
70 # 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
|
71 # of the same revision are iterated from the lowest depth |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
72 foundnew = (currev != lastrev) |
33003
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
73 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
|
74 lastrev = currev |
32999
08e2793d9f65
dagop: bulk rename variables in revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
32998
diff
changeset
|
75 yield currev |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
76 pdepth = curdepth + 1 |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
77 if foundnew and pdepth < stopdepth: |
33077
58ebb38456e0
dagop: factor out pfunc from revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33076
diff
changeset
|
78 for prev in pfunc(currev): |
58ebb38456e0
dagop: factor out pfunc from revancestors() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33076
diff
changeset
|
79 if prev != node.nullrev: |
33079
550c390cd9b2
dagop: make walk direction switchable so it can track descendants
Yuya Nishihara <yuya@tcha.org>
parents:
33078
diff
changeset
|
80 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
|
81 |
35276
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35275
diff
changeset
|
82 def filectxancestors(fctxs, followfirst=False): |
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35275
diff
changeset
|
83 """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
|
84 and includes the given fctxs themselves |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
85 |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
86 Yields (rev, {fctx, ...}) pairs in descending order. |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
87 """ |
35270
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
88 visit = {} |
35297
c9144396099b
dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35296
diff
changeset
|
89 visitheap = [] |
35274
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35273
diff
changeset
|
90 def addvisit(fctx): |
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35273
diff
changeset
|
91 rev = fctx.rev() |
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35273
diff
changeset
|
92 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
|
93 visit[rev] = set() |
35297
c9144396099b
dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35296
diff
changeset
|
94 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
|
95 visit[rev].add(fctx) |
2b348dc3239a
dagop: change visit dict of filectxancestors() indexed solely by rev
Yuya Nishihara <yuya@tcha.org>
parents:
35273
diff
changeset
|
96 |
35270
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
97 if followfirst: |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
98 cut = 1 |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
99 else: |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
100 cut = None |
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
101 |
35276
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35275
diff
changeset
|
102 for c in fctxs: |
205c3c6c1a51
dagop: extend filectxancestors() to walk multiple files
Yuya Nishihara <yuya@tcha.org>
parents:
35275
diff
changeset
|
103 addvisit(c) |
35275
b4b328ea6175
dagop: put start fctx into visit dict of filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35274
diff
changeset
|
104 while visit: |
35297
c9144396099b
dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35296
diff
changeset
|
105 currev = -heapq.heappop(visitheap) |
35296
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
106 curfctxs = visit.pop(currev) |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
107 yield currev, curfctxs |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
108 for c in curfctxs: |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
109 for parent in c.parents()[:cut]: |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
110 addvisit(parent) |
35297
c9144396099b
dagop: use heap to compute max rev in filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35296
diff
changeset
|
111 assert not visitheap |
35296
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
112 |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
113 def filerevancestors(fctxs, followfirst=False): |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
114 """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
|
115 and includes the given fctxs themselves |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
116 |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
117 Returns a smartset. |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
118 """ |
2cb05e6043be
dagop: add smartset interface to filectxancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
35276
diff
changeset
|
119 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
|
120 return generatorset(gen, iterasc=False) |
35270
0d27685b4a2f
dagop: copy basefilectx.ancestors() to free function
Yuya Nishihara <yuya@tcha.org>
parents:
34065
diff
changeset
|
121 |
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
122 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
|
123 if followfirst: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
124 cut = 1 |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
125 else: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
126 cut = None |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
127 cl = repo.changelog |
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
128 def plainpfunc(rev): |
33078
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
129 try: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
130 return cl.parentrevs(rev)[:cut] |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
131 except error.WdirUnsupported: |
fb663bd0243f
dagop: factor out generator of ancestor nodes
Yuya Nishihara <yuya@tcha.org>
parents:
33077
diff
changeset
|
132 return (pctx.rev() for pctx in repo[rev].parents()[:cut]) |
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
133 if cutfunc is None: |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
134 pfunc = plainpfunc |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
135 else: |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
136 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
|
137 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
|
138 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
|
139 |
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
140 def revancestors(repo, revs, followfirst=False, startdepth=None, |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
141 stopdepth=None, cutfunc=None): |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
142 """Like revlog.ancestors(), but supports additional options, includes |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
143 the given revs themselves, and returns a smartset |
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
144 |
33003
f63d111258da
revset: add startdepth limit to ancestors() as internal option
Yuya Nishihara <yuya@tcha.org>
parents:
33002
diff
changeset
|
145 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
|
146 earlier than the startdepth are omitted. |
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
147 |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
148 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
|
149 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
|
150 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
|
151 optimization sometimes. |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
152 |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
153 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
|
154 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
|
155 return True in this case. For example, |
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 D # revancestors(repo, D, cutfunc=lambda rev: rev == B) |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
158 |\ # 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
|
159 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
|
160 |/ |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
161 A |
33002
272a44cac57e
revset: add depth limit to ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
33001
diff
changeset
|
162 """ |
34065
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
163 gen = _genrevancestors(repo, revs, followfirst, startdepth, stopdepth, |
c6c8a52e28c9
revset: optimize "draft() & ::x" pattern
Jun Wu <quark@fb.com>
parents:
33284
diff
changeset
|
164 cutfunc) |
32997
b9e2269aeff8
dagop: unnest inner generator of revancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
32904
diff
changeset
|
165 return generatorset(gen, iterasc=False) |
16409
2cbd7dd0cc1f
graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents:
16402
diff
changeset
|
166 |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
167 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
|
168 if followfirst: |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
24219
diff
changeset
|
169 cut = 1 |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
24219
diff
changeset
|
170 else: |
6ddc86eedc3b
style: kill ersatz if-else ternary operators
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
24219
diff
changeset
|
171 cut = None |
16409
2cbd7dd0cc1f
graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents:
16402
diff
changeset
|
172 |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
173 cl = repo.changelog |
33076
a76a64c78807
dagop: use smartset.min() in revdescendants() generator
Yuya Nishihara <yuya@tcha.org>
parents:
33075
diff
changeset
|
174 first = revs.min() |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
175 nullrev = node.nullrev |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
176 if first == nullrev: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
177 # 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
|
178 # 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
|
179 yield first |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
180 for i in cl: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
181 yield i |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
182 else: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
183 seen = set(revs) |
33075
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
184 for i in cl.revs(first): |
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
185 if i in seen: |
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
186 yield i |
d83b189aef83
dagop: change revdescendants() to include all root revisions
Yuya Nishihara <yuya@tcha.org>
parents:
33073
diff
changeset
|
187 continue |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
188 for x in cl.parentrevs(i)[:cut]: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
189 if x != nullrev and x in seen: |
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
190 seen.add(i) |
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 break |
20692
7af341082b76
revset: changed descendants revset to use lazy generators
Lucas Moscovicz <lmoscovicz@fb.com>
parents:
20691
diff
changeset
|
193 |
33080
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
194 def _builddescendantsmap(repo, startrev, followfirst): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
195 """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
|
196 cl = repo.changelog |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
197 nullrev = node.nullrev |
38783
e7aa113b14f7
global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents:
37066
diff
changeset
|
198 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
|
199 for currev in cl.revs(startrev + 1): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
200 p1rev, p2rev = cl.parentrevs(currev) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
201 if p1rev >= startrev: |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
202 descmap[p1rev - startrev].append(currev) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
203 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
|
204 descmap[p2rev - startrev].append(currev) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
205 return descmap |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
206 |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
207 def _genrevdescendantsofdepth(repo, revs, followfirst, startdepth, stopdepth): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
208 startrev = revs.min() |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
209 descmap = _builddescendantsmap(repo, startrev, followfirst) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
210 def pfunc(rev): |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
211 return descmap[rev - startrev] |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
212 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
|
213 |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
214 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
|
215 """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
|
216 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
|
217 |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
218 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
|
219 earlier than the startdepth are omitted. |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
220 """ |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
221 if startdepth is None and stopdepth is None: |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
222 gen = _genrevdescendants(repo, revs, followfirst) |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
223 else: |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
224 gen = _genrevdescendantsofdepth(repo, revs, followfirst, |
a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
Yuya Nishihara <yuya@tcha.org>
parents:
33079
diff
changeset
|
225 startdepth, stopdepth) |
33073
b04cf7a6e0f3
dagop: unnest inner generator of revdescendants()
Yuya Nishihara <yuya@tcha.org>
parents:
33027
diff
changeset
|
226 return generatorset(gen, iterasc=True) |
16409
2cbd7dd0cc1f
graphlog: fix --follow-first --rev combinations
Patrick Mezard <patrick@mezard.eu>
parents:
16402
diff
changeset
|
227 |
26095
6eed95ca4c03
revset: mark reachablerootspure as private
Yuya Nishihara <yuya@tcha.org>
parents:
26094
diff
changeset
|
228 def _reachablerootspure(repo, minroot, roots, heads, includepath): |
26002
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
229 """return (heads(::<roots> and ::<heads>)) |
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
230 |
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
231 If includepath is True, return (<roots>::<heads>).""" |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
232 if not roots: |
26094
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
233 return [] |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
234 parentrevs = repo.changelog.parentrevs |
26053
b68c9d232db6
reachableroots: use internal "revstates" array to test if rev is a root
Yuya Nishihara <yuya@tcha.org>
parents:
26006
diff
changeset
|
235 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
|
236 visit = list(heads) |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
237 reachable = set() |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
238 seen = {} |
25566
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
239 # 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
|
240 reached = reachable.add |
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
241 dovisit = visit.append |
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
242 nextvisit = visit.pop |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
243 # 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
|
244 # sys.getrecursionlimit() |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
245 while visit: |
25566
15412bba5a68
revset: prefetch all attributes before loop in _revsbetween
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
25554
diff
changeset
|
246 rev = nextvisit() |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
247 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
|
248 reached(rev) |
26002
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
249 if not includepath: |
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
250 continue |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
251 parents = parentrevs(rev) |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
252 seen[rev] = parents |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
253 for parent in parents: |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
254 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
|
255 dovisit(parent) |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
256 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
|
257 return baseset() |
26002
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
258 if not includepath: |
fd92bfbbe02d
revset: rename revsbetween to reachableroots and add an argument
Laurent Charignon <lcharignon@fb.com>
parents:
26001
diff
changeset
|
259 return reachable |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
260 for rev in sorted(seen): |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
261 for parent in seen[rev]: |
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
262 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
|
263 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
|
264 return reachable |
16862
b6efeb27e733
revset: introduce and use _revsbetween
Bryan O'Sullivan <bryano@fb.com>
parents:
16861
diff
changeset
|
265 |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
266 def reachableroots(repo, roots, heads, includepath=False): |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
267 """return (heads(::<roots> and ::<heads>)) |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
268 |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
269 If includepath is True, return (<roots>::<heads>).""" |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
270 if not roots: |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
271 return baseset() |
26093
204131131766
reachableroots: use smartset min
Pierre-Yves David <pierre-yves.david@fb.com>
parents:
26091
diff
changeset
|
272 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
|
273 roots = list(roots) |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
274 heads = list(heads) |
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
275 try: |
26094
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
276 revs = repo.changelog.reachableroots(minroot, heads, roots, includepath) |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
277 except AttributeError: |
26095
6eed95ca4c03
revset: mark reachablerootspure as private
Yuya Nishihara <yuya@tcha.org>
parents:
26094
diff
changeset
|
278 revs = _reachablerootspure(repo, minroot, roots, heads, includepath) |
26094
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
279 revs = baseset(revs) |
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
280 revs.sort() |
df41c7be16d6
reachableroots: construct and sort baseset in revset module
Yuya Nishihara <yuya@tcha.org>
parents:
26093
diff
changeset
|
281 return revs |
26006
1ffd97cbf9a2
reachableroots: default to the C implementation
Laurent Charignon <lcharignon@fb.com>
parents:
26002
diff
changeset
|
282 |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
283 def _changesrange(fctx1, fctx2, linerange2, diffopts): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
284 """Return `(diffinrange, linerange1)` where `diffinrange` is True |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
285 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
|
286 `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
|
287 """ |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
288 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
|
289 filteredblocks, linerange1 = mdiff.blocksinrange(blocks, linerange2) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
290 diffinrange = any(stype == '!' for _, stype in filteredblocks) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
291 return diffinrange, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
292 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
293 def blockancestors(fctx, fromline, toline, followfirst=False): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
294 """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
|
295 `fromline`-`toline` range. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
296 """ |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
297 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
|
298 fctx = fctx.introfilectx() |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
299 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
|
300 while visit: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
301 c, linerange2 = visit.pop(max(visit)) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
302 pl = c.parents() |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
303 if followfirst: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
304 pl = pl[:1] |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
305 if not pl: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
306 # The block originates from the initial revision. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
307 yield c, linerange2 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
308 continue |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
309 inrange = False |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
310 for p in pl: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
311 inrangep, linerange1 = _changesrange(p, c, linerange2, diffopts) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
312 inrange = inrange or inrangep |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
313 if linerange1[0] == linerange1[1]: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
314 # 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
|
315 # 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
|
316 # branch. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
317 continue |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
318 # 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
|
319 # _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
|
320 # (as srcrev) instead possibly topmost introrev. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
321 p._descendantrev = c.rev() |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
322 visit[p.linkrev(), p.filenode()] = p, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
323 if inrange: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
324 yield c, linerange2 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
325 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
326 def blockdescendants(fctx, fromline, toline): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
327 """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
|
328 `fromline`-`toline` range. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
329 """ |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
330 # 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
|
331 # its parents. |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
332 try: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
333 c, linerange1 = next(blockancestors(fctx, fromline, toline)) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
334 except StopIteration: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
335 pass |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
336 else: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
337 if c == fctx: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
338 yield c, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
339 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
340 diffopts = patch.diffopts(fctx._repo.ui) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
341 fl = fctx.filelog() |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
342 seen = {fctx.filerev(): (fctx, (fromline, toline))} |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
343 for i in fl.descendants([fctx.filerev()]): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
344 c = fctx.filectx(i) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
345 inrange = False |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
346 for x in fl.parentrevs(i): |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
347 try: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
348 p, linerange2 = seen[x] |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
349 except KeyError: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
350 # nullrev or other branch |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
351 continue |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
352 inrangep, linerange1 = _changesrange(c, p, linerange2, diffopts) |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
353 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
|
354 # 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
|
355 # 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
|
356 # 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
|
357 # information. |
b2670290eab4
followlines: join merge parents line ranges in blockdescendants() (issue5595)
Denis Laxalde <denis.laxalde@logilab.fr>
parents:
33080
diff
changeset
|
358 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
|
359 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
|
360 linerange1 = min(lbs), max(ubs) |
32904
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
361 seen[i] = c, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
362 if inrange: |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
363 yield c, linerange1 |
582080a4a812
dagop: move blockancestors() and blockdescendants() from context
Yuya Nishihara <yuya@tcha.org>
parents:
32903
diff
changeset
|
364 |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
365 @attr.s(slots=True, frozen=True) |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
366 class annotateline(object): |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
367 fctx = attr.ib() |
37065
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
368 lineno = attr.ib() |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
369 # 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
|
370 skip = attr.ib(default=False) |
37066
b33b91ca2ec2
annotate: pack line content into annotateline object (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37065
diff
changeset
|
371 text = attr.ib(default=None) |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
372 |
37064
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
373 @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
|
374 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
|
375 # 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
|
376 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
|
377 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
|
378 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
|
379 # 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
|
380 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
|
381 |
36919
8fba319750c2
dagop: move lines() out of annotate()
Yuya Nishihara <yuya@tcha.org>
parents:
36918
diff
changeset
|
382 def _countlines(text): |
8fba319750c2
dagop: move lines() out of annotate()
Yuya Nishihara <yuya@tcha.org>
parents:
36918
diff
changeset
|
383 if text.endswith("\n"): |
8fba319750c2
dagop: move lines() out of annotate()
Yuya Nishihara <yuya@tcha.org>
parents:
36918
diff
changeset
|
384 return text.count("\n") |
8fba319750c2
dagop: move lines() out of annotate()
Yuya Nishihara <yuya@tcha.org>
parents:
36918
diff
changeset
|
385 return text.count("\n") + int(bool(text)) |
8fba319750c2
dagop: move lines() out of annotate()
Yuya Nishihara <yuya@tcha.org>
parents:
36918
diff
changeset
|
386 |
37065
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
387 def _decoratelines(text, fctx): |
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
388 n = _countlines(text) |
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
389 linenos = pycompat.rangelist(1, n + 1) |
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
390 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
|
391 |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
392 def _annotatepair(parents, childfctx, child, skipchild, diffopts): |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
393 r''' |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
394 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
|
395 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
|
396 data. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
397 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
398 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
|
399 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
|
400 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
401 See test-annotate.py for unit tests. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
402 ''' |
37064
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
403 pblocks = [(parent, mdiff.allblocks(parent.text, child.text, opts=diffopts)) |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
404 for parent in parents] |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
405 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
406 if skipchild: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
407 # 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
|
408 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
|
409 # 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
|
410 # TODO: change this? |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
411 for parent, blocks in pblocks: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
412 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
|
413 # 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
|
414 # belong to the child. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
415 if t == '=': |
37064
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
416 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
|
417 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
|
418 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
|
419 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
420 if skipchild: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
421 # 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
|
422 # 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
|
423 # behavior. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
424 pblocks.reverse() |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
425 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
426 # The heuristics are: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
427 # * 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
|
428 # 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
|
429 # * 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
|
430 # 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
|
431 # * 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
|
432 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
433 # 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
|
434 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
|
435 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
|
436 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
|
437 if a2 - a1 >= b2 - b1: |
38783
e7aa113b14f7
global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents:
37066
diff
changeset
|
438 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
|
439 if child.fctxs[bk] == childfctx: |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
440 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
|
441 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
|
442 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
|
443 child.skips[bk] = True |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
444 else: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
445 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
|
446 |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
447 # 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
|
448 # line. |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
449 for parent, blocks in remaining: |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
450 for a1, a2, b1, b2 in blocks: |
38783
e7aa113b14f7
global: use pycompat.xrange()
Gregory Szorc <gregory.szorc@gmail.com>
parents:
37066
diff
changeset
|
451 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
|
452 if child.fctxs[bk] == childfctx: |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
453 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
|
454 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
|
455 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
|
456 child.skips[bk] = True |
36917
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
457 return child |
7affcabf561e
dagop: move annotateline and _annotatepair from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
35297
diff
changeset
|
458 |
37065
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
459 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
|
460 """Core algorithm for filectx.annotate() |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
461 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
462 `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
|
463 """ |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
464 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
465 # 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
|
466 # 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
|
467 # depth-first search. |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
468 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
469 # 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
|
470 visit = [base] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
471 pcache = {} |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
472 needed = {base: 1} |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
473 while visit: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
474 f = visit.pop() |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
475 if f in pcache: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
476 continue |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
477 pl = parents(f) |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
478 pcache[f] = pl |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
479 for p in pl: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
480 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
|
481 if p not in pcache: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
482 visit.append(p) |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
483 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
484 # 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
|
485 visit[:] = [base] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
486 hist = {} |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
487 while visit: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
488 f = visit[-1] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
489 if f in hist: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
490 visit.pop() |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
491 continue |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
492 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
493 ready = True |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
494 pl = pcache[f] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
495 for p in pl: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
496 if p not in hist: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
497 ready = False |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
498 visit.append(p) |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
499 if ready: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
500 visit.pop() |
37065
b235bde38a83
annotate: drop linenumber flag from fctx.annotate() (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37064
diff
changeset
|
501 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
|
502 skipchild = False |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
503 if skiprevs is not None: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
504 skipchild = f._changeid in skiprevs |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
505 curr = _annotatepair([hist[p] for p in pl], f, curr, skipchild, |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
506 diffopts) |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
507 for p in pl: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
508 if needed[p] == 1: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
509 del hist[p] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
510 del needed[p] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
511 else: |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
512 needed[p] -= 1 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
513 |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
514 hist[f] = curr |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
515 del pcache[f] |
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
516 |
37064
434e520adb8c
annotate: do not construct attr.s object per line while computing history
Yuya Nishihara <yuya@tcha.org>
parents:
36935
diff
changeset
|
517 a = hist[base] |
37066
b33b91ca2ec2
annotate: pack line content into annotateline object (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37065
diff
changeset
|
518 return [annotateline(*r) for r in zip(a.fctxs, a.linenos, a.skips, |
b33b91ca2ec2
annotate: pack line content into annotateline object (API)
Yuya Nishihara <yuya@tcha.org>
parents:
37065
diff
changeset
|
519 mdiff.splitnewlines(a.text))] |
36918
5d3abd6a5b25
dagop: extract core algorithm of annotate() from context.py
Yuya Nishihara <yuya@tcha.org>
parents:
36917
diff
changeset
|
520 |
32903
27932a76a88d
dagop: split module hosting DAG-related algorithms from revset
Yuya Nishihara <yuya@tcha.org>
parents:
32885
diff
changeset
|
521 def toposort(revs, parentsfunc, firstbranch=()): |
29347
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
522 """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
|
523 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
524 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
|
525 the number of parallel branches and their interleaving. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
526 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
527 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
|
528 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
529 o 4 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
530 | |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
531 o 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
532 | |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
533 | o 3 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
534 | | |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
535 | o 2 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
536 |/ |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
537 o 0 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
538 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
539 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
|
540 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
|
541 occur behind a merge. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
542 """ |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
543 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
544 ### Quick summary of the algorithm |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
545 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
546 # 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
|
547 # 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
|
548 # "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
|
549 # branches with interleaved revisions. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
550 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
551 # During iteration revs are split into two groups: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
552 # A) revision already emitted |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
553 # 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
|
554 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
555 # for each REV, we do the following logic: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
556 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
557 # 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
|
558 # 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
|
559 # 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
|
560 # group first. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
561 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
562 # 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
|
563 # 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
|
564 # now awaiting for REV.parents() to be available. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
565 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
566 # 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
|
567 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
568 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
569 # 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
|
570 # puts it in group (A) from above). |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
571 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
572 revs.sort(reverse=True) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
573 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
574 # 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
|
575 # 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
|
576 # need to delay the revisions that reference them. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
577 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
578 # 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
|
579 # 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
|
580 # emitted. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
581 unblocked = set(firstbranch) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
582 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
583 # 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
|
584 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
585 # (revs: lists of revs waiting to be displayed, |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
586 # 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
|
587 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
588 # 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
|
589 # 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
|
590 # 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
|
591 # 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
|
592 # 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
|
593 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
594 # 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
|
595 # 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
|
596 # 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
|
597 # 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
|
598 # 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
|
599 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
600 # 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
|
601 # 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
|
602 # '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
|
603 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
604 # 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
|
605 # 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
|
606 groups = [([], unblocked)] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
607 pendingheap = [] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
608 pendingset = set() |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
609 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
610 heapq.heapify(pendingheap) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
611 heappop = heapq.heappop |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
612 heappush = heapq.heappush |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
613 for currentrev in revs: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
614 # 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
|
615 if currentrev not in pendingset: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
616 heappush(pendingheap, -currentrev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
617 pendingset.add(currentrev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
618 # 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
|
619 # processed. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
620 rev = None |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
621 while rev != currentrev: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
622 rev = -heappop(pendingheap) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
623 pendingset.remove(rev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
624 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
625 # 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
|
626 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
|
627 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
628 if matching: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
629 # 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
|
630 # on the same revision. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
631 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
632 # 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
|
633 # observed. For example, given two groups: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
634 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
635 # revs [5, 4] waiting for 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
636 # revs [3, 2] waiting for 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
637 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
638 # 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
|
639 # 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
|
640 # 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
|
641 # 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
|
642 # 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
|
643 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
644 # 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
|
645 # 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
|
646 # 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
|
647 # 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
|
648 targetidx = matching.pop(0) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
649 trevs, tparents = groups[targetidx] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
650 for i in matching: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
651 gr = groups[i] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
652 trevs.extend(gr[0]) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
653 tparents |= gr[1] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
654 # 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
|
655 # (starting from the last subgroup for performance and |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
656 # sanity reasons) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
657 for i in reversed(matching): |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
658 del groups[i] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
659 else: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
660 # 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
|
661 targetidx = len(groups) |
32291
bd872f64a8ba
cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents:
32085
diff
changeset
|
662 groups.append(([], {rev})) |
29347
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
663 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
664 gr = groups[targetidx] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
665 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
666 # 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
|
667 # 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
|
668 # that relied on this rev must precede it. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
669 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
670 # 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
|
671 # new nodes. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
672 if rev == currentrev: # only display stuff in rev |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
673 gr[0].append(rev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
674 gr[1].remove(rev) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
675 parents = [p for p in parentsfunc(rev) if p > node.nullrev] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
676 gr[1].update(parents) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
677 for p in parents: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
678 if p not in pendingset: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
679 pendingset.add(p) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
680 heappush(pendingheap, -p) |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
681 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
682 # Look for a subgroup to display |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
683 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
684 # 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
|
685 # 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
|
686 # 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
|
687 # 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
|
688 # subgroup. The heuristic could probably be better. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
689 # |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
690 # 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
|
691 # 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
|
692 # well. |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
693 if not unblocked: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
694 if len(groups) > 1: # display other subset |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
695 targetidx = 1 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
696 gr = groups[1] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
697 elif not gr[1] & unblocked: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
698 gr = None |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
699 |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
700 if gr is not None: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
701 # 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
|
702 # subgroup |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
703 unblocked |= gr[1] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
704 # output all revisions in the subgroup |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
705 for r in gr[0]: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
706 yield r |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
707 # delete the subgroup that you just output |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
708 # 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
|
709 if targetidx: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
710 del groups[targetidx] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
711 else: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
712 gr[0][:] = [] |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
713 # 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
|
714 # iterate over |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
715 for g in groups: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
716 for r in g[0]: |
98535ad46fc0
revset: move groupbranchiter over from graphmod
Martijn Pieters <mjpieters@fb.com>
parents:
29346
diff
changeset
|
717 yield r |
39179
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
718 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
719 def headrevs(revs, parentsfn): |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
720 """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
|
721 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
722 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
|
723 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
|
724 including nullrev. |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
725 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
726 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
|
727 subset. |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
728 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
729 ``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
|
730 the input set. |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
731 """ |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
732 headrevs = set(revs) |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
733 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
734 for rev in revs: |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
735 for prev in parentsfn(rev): |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
736 headrevs.discard(prev) |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
737 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
738 headrevs.discard(node.nullrev) |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
739 |
1c3184d7e882
dagop: extract headsetofconnecteds() from dagutil
Gregory Szorc <gregory.szorc@gmail.com>
parents:
38783
diff
changeset
|
740 return headrevs |
39181
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
741 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
742 def linearize(revs, parentsfn): |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
743 """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
|
744 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
745 The linearization process tires to create long runs of revs where a child |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
746 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
|
747 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
|
748 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
|
749 itself to the output list. |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
750 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
751 Returns a list of revision numbers. |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
752 """ |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
753 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
|
754 finished = set() |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
755 result = [] |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
756 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
757 while visit: |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
758 rev = visit.pop() |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
759 if rev < 0: |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
760 rev = -rev - 1 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
761 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
762 if rev not in finished: |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
763 result.append(rev) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
764 finished.add(rev) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
765 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
766 else: |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
767 visit.append(-rev - 1) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
768 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
769 for prev in parentsfn(rev): |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
770 if prev == node.nullrev or prev not in revs or prev in finished: |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
771 continue |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
772 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
773 visit.append(prev) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
774 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
775 assert len(result) == len(revs) |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
776 |
0a934ee94f09
dagop: port revlogdag.linearize() to standalone function
Gregory Szorc <gregory.szorc@gmail.com>
parents:
39179
diff
changeset
|
777 return result |