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

annotate mercurial/dagop.py @ 52669:e627cc25b6f3

pyupgrade: rewrite `yield` statements in a loop to `yield from` This is the `legacy` fixer in `pyupgrade`, with the `yield` statement yielding loop commented back in. This seems to help pytype in some cases, and hurt it in others. But that can be manually fixed later. Note that it's possibly buggy in that it aggressively changed `import-checker.py` to `yield from 'fcntl', 'grp', 'pwd', 'select', 'termios': # Unix only`, which is invalid syntax. Possibly it needed help from the token fixer that I've disabled locally (because that wants to make a bunch of unrelated changes). Just change those few places to yield from a list, to avoid having to constantly revert that.

author	Matt Harbison <matt_harbison@yahoo.com>
date	Sun, 05 Jan 2025 22:26:16 -0500
parents	f4733654f144
children

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

Mercurial > public > mercurial-scm > hg-stable

annotate mercurial/dagop.py @ 52669:e627cc25b6f3