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

annotate mercurial/dagop.py @ 51811:460e80488cf0

typing: lock in correct changes from pytype 2023.04.11 -> 2023.06.16 There were a handful of other changes to the pyi files generated when updating pytype locally (and jumping from python 3.8.0 to python 3.10.11), but they were not as clear (e.g. the embedded type in a list changing from `nothing` to `Any` or similar). These looked obviously correct, and agreed with PyCharm's thoughts on the signatures. Oddly, even though pytype starting inferring `obsutil._getfilteredreason()` as returning bytes, it (correctly) complained about the None path when it was typed that way. Instead, raise a ProgrammingError if an unhandled fate is calculated. (Currently, all possibilities are handled, so this isn't reachable unless another fate is added in the future.)

author	Matt Harbison <matt_harbison@yahoo.com>
date	Tue, 20 Aug 2024 18:30:47 -0400
parents	278af66e6595
children	f4733654f144

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

Mercurial > public > mercurial-scm > hg

annotate mercurial/dagop.py @ 51811:460e80488cf0