mercurial-scm/hg: mercurial/dagop.py annotate

annotate mercurial/dagop.py @ 51725:278af66e6595

typing: induce pytype to use the standard `attr` instead of the vendored copy What was previously happening with the vendored copy was that pytype would stub out all(?) classes that were decorated with `@attr.s` as `Any`. After this, we get a ton of classes defined, and numerous fields and methods now have proper types.

author	Matt Harbison <matt_harbison@yahoo.com>
date	Tue, 23 Jul 2024 19:20:22 -0400
parents	a0d88b021a98
children	460e80488cf0

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

Mercurial > public > mercurial-scm > hg

annotate mercurial/dagop.py @ 51725:278af66e6595