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

annotate mercurial/dagop.py @ 42446:055c3e2c44f0

revlog: speed up isancestor Currently, it is implemented on top of commonancestorsheads. Implement it on top of reachableroots instead, as reachableroots could stop walking the graph much sooner than commonancestorsheads. Measuring repo.changelog.isancestorrev on two revisions in a private repository: before: ! wall 0.005175 comb 0.010000 user 0.010000 sys 0.000000 (best of 550) after : ! wall 0.000072 comb 0.000000 user 0.000000 sys 0.000000 (best of 36199) When hg does this kind of operations 1500 times in pull -> bookmarks.comparebookmarks -> bookmarks.validdest, that's 11s that drop from the --profile output. Differential Revision: https://phab.mercurial-scm.org/D6506

author	Valentin Gatien-Baron <vgatien-baron@janestreet.com>
date	Mon, 10 Jun 2019 13:23:14 -0400
parents	3e42fc243741
children	2372284d9457

rev	line source
32903 27932a76a88d dagop: split module hosting DAG-related algorithms from revset Yuya Nishihara <yuya@tcha.org> parents: 32885 diff changeset	1 # dagop.py - graph ancestry and topology algorithm for revset
11275 c9ce8ecd6ca1 revset: introduce revset core Matt Mackall <mpm@selenic.com> parents: diff changeset	2 #
c9ce8ecd6ca1 revset: introduce revset core Matt Mackall <mpm@selenic.com> parents: diff changeset	3 # Copyright 2010 Matt Mackall <mpm@selenic.com>
c9ce8ecd6ca1 revset: introduce revset core Matt Mackall <mpm@selenic.com> parents: diff changeset	4 #
c9ce8ecd6ca1 revset: introduce revset core Matt Mackall <mpm@selenic.com> parents: diff changeset	5 # This software may be used and distributed according to the terms of the
c9ce8ecd6ca1 revset: introduce revset core Matt Mackall <mpm@selenic.com> parents: diff changeset	6 # GNU General Public License version 2 or any later version.
c9ce8ecd6ca1 revset: introduce revset core Matt Mackall <mpm@selenic.com> parents: diff changeset	7
25971 e9cd028f2dff revset: use absolute_import Gregory Szorc <gregory.szorc@gmail.com> parents: 25929 diff changeset	8 from __future__ import absolute_import
e9cd028f2dff revset: use absolute_import Gregory Szorc <gregory.szorc@gmail.com> parents: 25929 diff changeset	9
20690 13c0327eeb6f revset: changed ancestors revset to return lazy generators Lucas Moscovicz <lmoscovicz@fb.com> parents: 20659 diff changeset	10 import heapq
25971 e9cd028f2dff revset: use absolute_import Gregory Szorc <gregory.szorc@gmail.com> parents: 25929 diff changeset	11
39999 0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	12 from .node import (
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	13 nullrev,
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	14 )
36917 7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	15 from .thirdparty import (
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	16 attr,
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	17 )
25971 e9cd028f2dff revset: use absolute_import Gregory Szorc <gregory.szorc@gmail.com> parents: 25929 diff changeset	18 from . import (
e9cd028f2dff revset: use absolute_import Gregory Szorc <gregory.szorc@gmail.com> parents: 25929 diff changeset	19 error,
32904 582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	20 mdiff,
25971 e9cd028f2dff revset: use absolute_import Gregory Szorc <gregory.szorc@gmail.com> parents: 25929 diff changeset	21 node,
32904 582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	22 patch,
36918 5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	23 pycompat,
30881 1be65deb3d54 smartset: move set classes and related functions from revset module (API) Yuya Nishihara <yuya@tcha.org> parents: 30850 diff changeset	24 smartset,
25971 e9cd028f2dff revset: use absolute_import Gregory Szorc <gregory.szorc@gmail.com> parents: 25929 diff changeset	25 )
11275 c9ce8ecd6ca1 revset: introduce revset core Matt Mackall <mpm@selenic.com> parents: diff changeset	26
30881 1be65deb3d54 smartset: move set classes and related functions from revset module (API) Yuya Nishihara <yuya@tcha.org> parents: 30850 diff changeset	27 baseset = smartset.baseset
1be65deb3d54 smartset: move set classes and related functions from revset module (API) Yuya Nishihara <yuya@tcha.org> parents: 30850 diff changeset	28 generatorset = smartset.generatorset
1be65deb3d54 smartset: move set classes and related functions from revset module (API) Yuya Nishihara <yuya@tcha.org> parents: 30850 diff changeset	29
33002 272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	30 # possible maximum depth between null and wdir()
41359 431cf2c8c839 revset: support ranges in #generations relation Anton Shestakov <av6@dwimlabs.net> parents: 41277 diff changeset	31 maxlogdepth = 0x80000000
33002 272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	32
33079 550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	33 def _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse):
33078 fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	34 """Walk DAG using 'pfunc' from the given 'revs' nodes
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	35
33079 550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	36 'pfunc(rev)' should return the parent/child revisions of the given 'rev'
550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	37 if 'reverse' is True/False respectively.
33078 fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	38
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	39 Scan ends at the stopdepth (exlusive) if specified. Revisions found
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	40 earlier than the startdepth are omitted.
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	41 """
33003 f63d111258da revset: add startdepth limit to ancestors() as internal option Yuya Nishihara <yuya@tcha.org> parents: 33002 diff changeset	42 if startdepth is None:
f63d111258da revset: add startdepth limit to ancestors() as internal option Yuya Nishihara <yuya@tcha.org> parents: 33002 diff changeset	43 startdepth = 0
33002 272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	44 if stopdepth is None:
41359 431cf2c8c839 revset: support ranges in #generations relation Anton Shestakov <av6@dwimlabs.net> parents: 41277 diff changeset	45 stopdepth = maxlogdepth
33027 a10f5f6771f6 dagop: raise ProgrammingError if stopdepth < 0 Martin von Zweigbergk <martinvonz@google.com> parents: 33003 diff changeset	46 if stopdepth == 0:
33002 272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	47 return
33027 a10f5f6771f6 dagop: raise ProgrammingError if stopdepth < 0 Martin von Zweigbergk <martinvonz@google.com> parents: 33003 diff changeset	48 if stopdepth < 0:
a10f5f6771f6 dagop: raise ProgrammingError if stopdepth < 0 Martin von Zweigbergk <martinvonz@google.com> parents: 33003 diff changeset	49 raise error.ProgrammingError('negative stopdepth')
33079 550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	50 if reverse:
550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	51 heapsign = -1 # max heap
550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	52 else:
550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	53 heapsign = +1 # min heap
33002 272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	54
32998 c7da57bbae96 dagop: comment why revancestors() doesn't heapify input revs at once Yuya Nishihara <yuya@tcha.org> parents: 32997 diff changeset	55 # load input revs lazily to heap so earlier revisions can be yielded
c7da57bbae96 dagop: comment why revancestors() doesn't heapify input revs at once Yuya Nishihara <yuya@tcha.org> parents: 32997 diff changeset	56 # without fully computing the input revs
33079 550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	57 revs.sort(reverse)
32997 b9e2269aeff8 dagop: unnest inner generator of revancestors() Yuya Nishihara <yuya@tcha.org> parents: 32904 diff changeset	58 irevs = iter(revs)
33079 550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	59 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	60
32997 b9e2269aeff8 dagop: unnest inner generator of revancestors() Yuya Nishihara <yuya@tcha.org> parents: 32904 diff changeset	61 inputrev = next(irevs, None)
b9e2269aeff8 dagop: unnest inner generator of revancestors() Yuya Nishihara <yuya@tcha.org> parents: 32904 diff changeset	62 if inputrev is not None:
33079 550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	63 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	64
33000 d3d36bcdf036 dagop: just compare with the last value to deduplicate input of revancestors() Yuya Nishihara <yuya@tcha.org> parents: 32999 diff changeset	65 lastrev = None
32999 08e2793d9f65 dagop: bulk rename variables in revancestors() generator Yuya Nishihara <yuya@tcha.org> parents: 32998 diff changeset	66 while pendingheap:
33001 92d0945a15e0 dagop: compute depth in revancestors() generator Yuya Nishihara <yuya@tcha.org> parents: 33000 diff changeset	67 currev, curdepth = heapq.heappop(pendingheap)
33079 550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	68 currev = heapsign * currev
32999 08e2793d9f65 dagop: bulk rename variables in revancestors() generator Yuya Nishihara <yuya@tcha.org> parents: 32998 diff changeset	69 if currev == inputrev:
32997 b9e2269aeff8 dagop: unnest inner generator of revancestors() Yuya Nishihara <yuya@tcha.org> parents: 32904 diff changeset	70 inputrev = next(irevs, None)
b9e2269aeff8 dagop: unnest inner generator of revancestors() Yuya Nishihara <yuya@tcha.org> parents: 32904 diff changeset	71 if inputrev is not None:
33079 550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	72 heapq.heappush(pendingheap, (heapsign * inputrev, 0))
33003 f63d111258da revset: add startdepth limit to ancestors() as internal option Yuya Nishihara <yuya@tcha.org> parents: 33002 diff changeset	73 # rescan parents until curdepth >= startdepth because queued entries
f63d111258da revset: add startdepth limit to ancestors() as internal option Yuya Nishihara <yuya@tcha.org> parents: 33002 diff changeset	74 # of the same revision are iterated from the lowest depth
33002 272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	75 foundnew = (currev != lastrev)
33003 f63d111258da revset: add startdepth limit to ancestors() as internal option Yuya Nishihara <yuya@tcha.org> parents: 33002 diff changeset	76 if foundnew and curdepth >= startdepth:
33000 d3d36bcdf036 dagop: just compare with the last value to deduplicate input of revancestors() Yuya Nishihara <yuya@tcha.org> parents: 32999 diff changeset	77 lastrev = currev
32999 08e2793d9f65 dagop: bulk rename variables in revancestors() generator Yuya Nishihara <yuya@tcha.org> parents: 32998 diff changeset	78 yield currev
33002 272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	79 pdepth = curdepth + 1
272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	80 if foundnew and pdepth < stopdepth:
33077 58ebb38456e0 dagop: factor out pfunc from revancestors() generator Yuya Nishihara <yuya@tcha.org> parents: 33076 diff changeset	81 for prev in pfunc(currev):
58ebb38456e0 dagop: factor out pfunc from revancestors() generator Yuya Nishihara <yuya@tcha.org> parents: 33076 diff changeset	82 if prev != node.nullrev:
33079 550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	83 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	84
35276 205c3c6c1a51 dagop: extend filectxancestors() to walk multiple files Yuya Nishihara <yuya@tcha.org> parents: 35275 diff changeset	85 def filectxancestors(fctxs, followfirst=False):
205c3c6c1a51 dagop: extend filectxancestors() to walk multiple files Yuya Nishihara <yuya@tcha.org> parents: 35275 diff changeset	86 """Like filectx.ancestors(), but can walk from multiple files/revisions,
35296 2cb05e6043be dagop: add smartset interface to filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35276 diff changeset	87 and includes the given fctxs themselves
2cb05e6043be dagop: add smartset interface to filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35276 diff changeset	88
2cb05e6043be dagop: add smartset interface to filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35276 diff changeset	89 Yields (rev, {fctx, ...}) pairs in descending order.
2cb05e6043be dagop: add smartset interface to filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35276 diff changeset	90 """
35270 0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	91 visit = {}
35297 c9144396099b dagop: use heap to compute max rev in filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35296 diff changeset	92 visitheap = []
35274 2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev Yuya Nishihara <yuya@tcha.org> parents: 35273 diff changeset	93 def addvisit(fctx):
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev Yuya Nishihara <yuya@tcha.org> parents: 35273 diff changeset	94 rev = fctx.rev()
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev Yuya Nishihara <yuya@tcha.org> parents: 35273 diff changeset	95 if rev not in visit:
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev Yuya Nishihara <yuya@tcha.org> parents: 35273 diff changeset	96 visit[rev] = set()
35297 c9144396099b dagop: use heap to compute max rev in filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35296 diff changeset	97 heapq.heappush(visitheap, -rev) # max heap
35274 2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev Yuya Nishihara <yuya@tcha.org> parents: 35273 diff changeset	98 visit[rev].add(fctx)
2b348dc3239a dagop: change visit dict of filectxancestors() indexed solely by rev Yuya Nishihara <yuya@tcha.org> parents: 35273 diff changeset	99
35270 0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	100 if followfirst:
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	101 cut = 1
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	102 else:
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	103 cut = None
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	104
35276 205c3c6c1a51 dagop: extend filectxancestors() to walk multiple files Yuya Nishihara <yuya@tcha.org> parents: 35275 diff changeset	105 for c in fctxs:
205c3c6c1a51 dagop: extend filectxancestors() to walk multiple files Yuya Nishihara <yuya@tcha.org> parents: 35275 diff changeset	106 addvisit(c)
35275 b4b328ea6175 dagop: put start fctx into visit dict of filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35274 diff changeset	107 while visit:
35297 c9144396099b dagop: use heap to compute max rev in filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35296 diff changeset	108 currev = -heapq.heappop(visitheap)
35296 2cb05e6043be dagop: add smartset interface to filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35276 diff changeset	109 curfctxs = visit.pop(currev)
2cb05e6043be dagop: add smartset interface to filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35276 diff changeset	110 yield currev, curfctxs
2cb05e6043be dagop: add smartset interface to filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35276 diff changeset	111 for c in curfctxs:
2cb05e6043be dagop: add smartset interface to filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35276 diff changeset	112 for parent in c.parents()[:cut]:
2cb05e6043be dagop: add smartset interface to filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35276 diff changeset	113 addvisit(parent)
35297 c9144396099b dagop: use heap to compute max rev in filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35296 diff changeset	114 assert not visitheap
35296 2cb05e6043be dagop: add smartset interface to filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35276 diff changeset	115
2cb05e6043be dagop: add smartset interface to filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35276 diff changeset	116 def filerevancestors(fctxs, followfirst=False):
2cb05e6043be dagop: add smartset interface to filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35276 diff changeset	117 """Like filectx.ancestors(), but can walk from multiple files/revisions,
2cb05e6043be dagop: add smartset interface to filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35276 diff changeset	118 and includes the given fctxs themselves
2cb05e6043be dagop: add smartset interface to filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35276 diff changeset	119
2cb05e6043be dagop: add smartset interface to filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35276 diff changeset	120 Returns a smartset.
2cb05e6043be dagop: add smartset interface to filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35276 diff changeset	121 """
2cb05e6043be dagop: add smartset interface to filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35276 diff changeset	122 gen = (rev for rev, _cs in filectxancestors(fctxs, followfirst))
2cb05e6043be dagop: add smartset interface to filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35276 diff changeset	123 return generatorset(gen, iterasc=False)
35270 0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	124
34065 c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	125 def _genrevancestors(repo, revs, followfirst, startdepth, stopdepth, cutfunc):
33078 fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	126 if followfirst:
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	127 cut = 1
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	128 else:
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	129 cut = None
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	130 cl = repo.changelog
34065 c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	131 def plainpfunc(rev):
33078 fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	132 try:
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	133 return cl.parentrevs(rev)[:cut]
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	134 except error.WdirUnsupported:
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	135 return (pctx.rev() for pctx in repo[rev].parents()[:cut])
34065 c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	136 if cutfunc is None:
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	137 pfunc = plainpfunc
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	138 else:
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	139 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	140 revs = revs.filter(lambda rev: not cutfunc(rev))
33079 550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	141 return _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse=True)
33078 fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	142
34065 c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	143 def revancestors(repo, revs, followfirst=False, startdepth=None,
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	144 stopdepth=None, cutfunc=None):
41533 0f64091cc851 global: make some docstrings raw strings Gregory Szorc <gregory.szorc@gmail.com> parents: 41389 diff changeset	145 r"""Like revlog.ancestors(), but supports additional options, includes
33002 272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	146 the given revs themselves, and returns a smartset
272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	147
33003 f63d111258da revset: add startdepth limit to ancestors() as internal option Yuya Nishihara <yuya@tcha.org> parents: 33002 diff changeset	148 Scan ends at the stopdepth (exlusive) if specified. Revisions found
f63d111258da revset: add startdepth limit to ancestors() as internal option Yuya Nishihara <yuya@tcha.org> parents: 33002 diff changeset	149 earlier than the startdepth are omitted.
34065 c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	150
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	151 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	152 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	153 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	154 optimization sometimes.
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	155
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	156 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	157 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	158 return True in this case. For example,
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	159
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	160 D # revancestors(repo, D, cutfunc=lambda rev: rev == B)
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	161 \|\ # 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	162 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	163 \|/
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	164 A
33002 272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	165 """
34065 c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	166 gen = _genrevancestors(repo, revs, followfirst, startdepth, stopdepth,
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	167 cutfunc)
32997 b9e2269aeff8 dagop: unnest inner generator of revancestors() Yuya Nishihara <yuya@tcha.org> parents: 32904 diff changeset	168 return generatorset(gen, iterasc=False)
16409 2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations Patrick Mezard <patrick@mezard.eu> parents: 16402 diff changeset	169
33073 b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	170 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	171 if followfirst:
6ddc86eedc3b style: kill ersatz if-else ternary operators Jordi Guti?rrez Hermoso <jordigh@octave.org> parents: 24219 diff changeset	172 cut = 1
6ddc86eedc3b style: kill ersatz if-else ternary operators Jordi Guti?rrez Hermoso <jordigh@octave.org> parents: 24219 diff changeset	173 else:
6ddc86eedc3b style: kill ersatz if-else ternary operators Jordi Guti?rrez Hermoso <jordigh@octave.org> parents: 24219 diff changeset	174 cut = None
16409 2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations Patrick Mezard <patrick@mezard.eu> parents: 16402 diff changeset	175
33073 b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	176 cl = repo.changelog
33076 a76a64c78807 dagop: use smartset.min() in revdescendants() generator Yuya Nishihara <yuya@tcha.org> parents: 33075 diff changeset	177 first = revs.min()
33073 b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	178 nullrev = node.nullrev
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	179 if first == nullrev:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	180 # Are there nodes with a null first parent and a non-null
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	181 # second one? Maybe. Do we care? Probably not.
33075 d83b189aef83 dagop: change revdescendants() to include all root revisions Yuya Nishihara <yuya@tcha.org> parents: 33073 diff changeset	182 yield first
33073 b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	183 for i in cl:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	184 yield i
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	185 else:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	186 seen = set(revs)
33075 d83b189aef83 dagop: change revdescendants() to include all root revisions Yuya Nishihara <yuya@tcha.org> parents: 33073 diff changeset	187 for i in cl.revs(first):
d83b189aef83 dagop: change revdescendants() to include all root revisions Yuya Nishihara <yuya@tcha.org> parents: 33073 diff changeset	188 if i in seen:
d83b189aef83 dagop: change revdescendants() to include all root revisions Yuya Nishihara <yuya@tcha.org> parents: 33073 diff changeset	189 yield i
d83b189aef83 dagop: change revdescendants() to include all root revisions Yuya Nishihara <yuya@tcha.org> parents: 33073 diff changeset	190 continue
33073 b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	191 for x in cl.parentrevs(i)[:cut]:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	192 if x != nullrev and x in seen:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	193 seen.add(i)
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	194 yield i
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	195 break
20692 7af341082b76 revset: changed descendants revset to use lazy generators Lucas Moscovicz <lmoscovicz@fb.com> parents: 20691 diff changeset	196
33080 a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	197 def _builddescendantsmap(repo, startrev, followfirst):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	198 """Build map of 'rev -> child revs', offset from startrev"""
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	199 cl = repo.changelog
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	200 nullrev = node.nullrev
38783 e7aa113b14f7 global: use pycompat.xrange() Gregory Szorc <gregory.szorc@gmail.com> parents: 37066 diff changeset	201 descmap = [[] for _rev in pycompat.xrange(startrev, len(cl))]
33080 a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	202 for currev in cl.revs(startrev + 1):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	203 p1rev, p2rev = cl.parentrevs(currev)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	204 if p1rev >= startrev:
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	205 descmap[p1rev - startrev].append(currev)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	206 if not followfirst and p2rev != nullrev and p2rev >= startrev:
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	207 descmap[p2rev - startrev].append(currev)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	208 return descmap
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	209
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	210 def _genrevdescendantsofdepth(repo, revs, followfirst, startdepth, stopdepth):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	211 startrev = revs.min()
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	212 descmap = _builddescendantsmap(repo, startrev, followfirst)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	213 def pfunc(rev):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	214 return descmap[rev - startrev]
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	215 return _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse=False)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	216
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	217 def revdescendants(repo, revs, followfirst, startdepth=None, stopdepth=None):
33075 d83b189aef83 dagop: change revdescendants() to include all root revisions Yuya Nishihara <yuya@tcha.org> parents: 33073 diff changeset	218 """Like revlog.descendants() but supports additional options, includes
33080 a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	219 the given revs themselves, and returns a smartset
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	220
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	221 Scan ends at the stopdepth (exlusive) if specified. Revisions found
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	222 earlier than the startdepth are omitted.
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	223 """
41389 7e55ca658e4b dagop: check if stopdepth is greater than or equal to maxlogdepth Anton Shestakov <av6@dwimlabs.net> parents: 41359 diff changeset	224 if startdepth is None and (stopdepth is None or stopdepth >= maxlogdepth):
33080 a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	225 gen = _genrevdescendants(repo, revs, followfirst)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	226 else:
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	227 gen = _genrevdescendantsofdepth(repo, revs, followfirst,
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	228 startdepth, stopdepth)
33073 b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	229 return generatorset(gen, iterasc=True)
16409 2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations Patrick Mezard <patrick@mezard.eu> parents: 16402 diff changeset	230
39999 0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	231 def descendantrevs(revs, revsfn, parentrevsfn):
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	232 """Generate revision number descendants in revision order.
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	233
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	234 Yields revision numbers starting with a child of some rev in
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	235 ``revs``. Results are ordered by revision number and are
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	236 therefore topological. Each revision is not considered a descendant
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	237 of itself.
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	238
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	239 ``revsfn`` is a callable that with no argument iterates over all
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	240 revision numbers and with a ``start`` argument iterates over revision
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	241 numbers beginning with that value.
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	242
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	243 ``parentrevsfn`` is a callable that receives a revision number and
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	244 returns an iterable of parent revision numbers, whose values may include
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	245 nullrev.
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	246 """
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	247 first = min(revs)
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	248
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	249 if first == nullrev:
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	250 for rev in revsfn():
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	251 yield rev
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	252 return
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	253
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	254 seen = set(revs)
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	255 for rev in revsfn(start=first + 1):
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	256 for prev in parentrevsfn(rev):
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	257 if prev != nullrev and prev in seen:
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	258 seen.add(rev)
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	259 yield rev
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	260 break
0b24fcd88066 dagop: extract descendants() from revlog module Gregory Szorc <gregory.szorc@gmail.com> parents: 39607 diff changeset	261
42446 055c3e2c44f0 revlog: speed up isancestor Valentin Gatien-Baron <vgatien-baron@janestreet.com> parents: 42445 diff changeset	262 def _reachablerootspure(pfunc, minroot, roots, heads, includepath):
055c3e2c44f0 revlog: speed up isancestor Valentin Gatien-Baron <vgatien-baron@janestreet.com> parents: 42445 diff changeset	263 """See revlog.reachableroots"""
16862 b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	264 if not roots:
26094 df41c7be16d6 reachableroots: construct and sort baseset in revset module Yuya Nishihara <yuya@tcha.org> parents: 26093 diff changeset	265 return []
26053 b68c9d232db6 reachableroots: use internal "revstates" array to test if rev is a root Yuya Nishihara <yuya@tcha.org> parents: 26006 diff changeset	266 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	267 visit = list(heads)
16862 b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	268 reachable = set()
b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	269 seen = {}
25566 15412bba5a68 revset: prefetch all attributes before loop in _revsbetween Pierre-Yves David <pierre-yves.david@fb.com> parents: 25554 diff changeset	270 # 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	271 reached = reachable.add
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween Pierre-Yves David <pierre-yves.david@fb.com> parents: 25554 diff changeset	272 dovisit = visit.append
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween Pierre-Yves David <pierre-yves.david@fb.com> parents: 25554 diff changeset	273 nextvisit = visit.pop
16862 b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	274 # 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	275 # sys.getrecursionlimit()
b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	276 while visit:
25566 15412bba5a68 revset: prefetch all attributes before loop in _revsbetween Pierre-Yves David <pierre-yves.david@fb.com> parents: 25554 diff changeset	277 rev = nextvisit()
16862 b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	278 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	279 reached(rev)
26002 fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument Laurent Charignon <lcharignon@fb.com> parents: 26001 diff changeset	280 if not includepath:
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument Laurent Charignon <lcharignon@fb.com> parents: 26001 diff changeset	281 continue
42446 055c3e2c44f0 revlog: speed up isancestor Valentin Gatien-Baron <vgatien-baron@janestreet.com> parents: 42445 diff changeset	282 parents = pfunc(rev)
16862 b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	283 seen[rev] = parents
b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	284 for parent in parents:
b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	285 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	286 dovisit(parent)
16862 b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	287 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	288 return baseset()
26002 fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument Laurent Charignon <lcharignon@fb.com> parents: 26001 diff changeset	289 if not includepath:
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument Laurent Charignon <lcharignon@fb.com> parents: 26001 diff changeset	290 return reachable
16862 b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	291 for rev in sorted(seen):
b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	292 for parent in seen[rev]:
b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	293 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	294 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	295 return reachable
16862 b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	296
26006 1ffd97cbf9a2 reachableroots: default to the C implementation Laurent Charignon <lcharignon@fb.com> parents: 26002 diff changeset	297 def reachableroots(repo, roots, heads, includepath=False):
42446 055c3e2c44f0 revlog: speed up isancestor Valentin Gatien-Baron <vgatien-baron@janestreet.com> parents: 42445 diff changeset	298 """See revlog.reachableroots"""
26006 1ffd97cbf9a2 reachableroots: default to the C implementation Laurent Charignon <lcharignon@fb.com> parents: 26002 diff changeset	299 if not roots:
1ffd97cbf9a2 reachableroots: default to the C implementation Laurent Charignon <lcharignon@fb.com> parents: 26002 diff changeset	300 return baseset()
26093 204131131766 reachableroots: use smartset min Pierre-Yves David <pierre-yves.david@fb.com> parents: 26091 diff changeset	301 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	302 roots = list(roots)
26006 1ffd97cbf9a2 reachableroots: default to the C implementation Laurent Charignon <lcharignon@fb.com> parents: 26002 diff changeset	303 heads = list(heads)
42446 055c3e2c44f0 revlog: speed up isancestor Valentin Gatien-Baron <vgatien-baron@janestreet.com> parents: 42445 diff changeset	304 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	305 revs = baseset(revs)
df41c7be16d6 reachableroots: construct and sort baseset in revset module Yuya Nishihara <yuya@tcha.org> parents: 26093 diff changeset	306 revs.sort()
df41c7be16d6 reachableroots: construct and sort baseset in revset module Yuya Nishihara <yuya@tcha.org> parents: 26093 diff changeset	307 return revs
26006 1ffd97cbf9a2 reachableroots: default to the C implementation Laurent Charignon <lcharignon@fb.com> parents: 26002 diff changeset	308
32904 582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	309 def _changesrange(fctx1, fctx2, linerange2, diffopts):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	310 """Return `(diffinrange, linerange1)` where `diffinrange` is True
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	311 if diff from fctx2 to fctx1 has changes in linerange2 and
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	312 `linerange1` is the new line range for fctx1.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	313 """
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	314 blocks = mdiff.allblocks(fctx1.data(), fctx2.data(), diffopts)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	315 filteredblocks, linerange1 = mdiff.blocksinrange(blocks, linerange2)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	316 diffinrange = any(stype == '!' for _, stype in filteredblocks)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	317 return diffinrange, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	318
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	319 def blockancestors(fctx, fromline, toline, followfirst=False):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	320 """Yield ancestors of `fctx` with respect to the block of lines within
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	321 `fromline`-`toline` range.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	322 """
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	323 diffopts = patch.diffopts(fctx._repo.ui)
35271 d90c534099b1 filectx: extract helper method to obtain filectx pointing to its introrev Yuya Nishihara <yuya@tcha.org> parents: 35270 diff changeset	324 fctx = fctx.introfilectx()
32904 582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	325 visit = {(fctx.linkrev(), fctx.filenode()): (fctx, (fromline, toline))}
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	326 while visit:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	327 c, linerange2 = visit.pop(max(visit))
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	328 pl = c.parents()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	329 if followfirst:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	330 pl = pl[:1]
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	331 if not pl:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	332 # The block originates from the initial revision.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	333 yield c, linerange2
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	334 continue
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	335 inrange = False
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	336 for p in pl:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	337 inrangep, linerange1 = _changesrange(p, c, linerange2, diffopts)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	338 inrange = inrange or inrangep
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	339 if linerange1[0] == linerange1[1]:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	340 # Parent's linerange is empty, meaning that the block got
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	341 # introduced in this revision; no need to go futher in this
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	342 # branch.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	343 continue
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	344 # Set _descendantrev with 'c' (a known descendant) so that, when
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	345 # _adjustlinkrev is called for 'p', it receives this descendant
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	346 # (as srcrev) instead possibly topmost introrev.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	347 p._descendantrev = c.rev()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	348 visit[p.linkrev(), p.filenode()] = p, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	349 if inrange:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	350 yield c, linerange2
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	351
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	352 def blockdescendants(fctx, fromline, toline):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	353 """Yield descendants of `fctx` with respect to the block of lines within
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	354 `fromline`-`toline` range.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	355 """
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	356 # First possibly yield 'fctx' if it has changes in range with respect to
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	357 # its parents.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	358 try:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	359 c, linerange1 = next(blockancestors(fctx, fromline, toline))
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	360 except StopIteration:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	361 pass
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	362 else:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	363 if c == fctx:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	364 yield c, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	365
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	366 diffopts = patch.diffopts(fctx._repo.ui)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	367 fl = fctx.filelog()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	368 seen = {fctx.filerev(): (fctx, (fromline, toline))}
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	369 for i in fl.descendants([fctx.filerev()]):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	370 c = fctx.filectx(i)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	371 inrange = False
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	372 for x in fl.parentrevs(i):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	373 try:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	374 p, linerange2 = seen[x]
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	375 except KeyError:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	376 # nullrev or other branch
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	377 continue
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	378 inrangep, linerange1 = _changesrange(c, p, linerange2, diffopts)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	379 inrange = inrange or inrangep
33284 b2670290eab4 followlines: join merge parents line ranges in blockdescendants() (issue5595) Denis Laxalde <denis.laxalde@logilab.fr> parents: 33080 diff changeset	380 # If revision 'i' has been seen (it's a merge) and the line range
b2670290eab4 followlines: join merge parents line ranges in blockdescendants() (issue5595) Denis Laxalde <denis.laxalde@logilab.fr> parents: 33080 diff changeset	381 # previously computed differs from the one we just got, we take the
b2670290eab4 followlines: join merge parents line ranges in blockdescendants() (issue5595) Denis Laxalde <denis.laxalde@logilab.fr> parents: 33080 diff changeset	382 # surrounding interval. This is conservative but avoids loosing
b2670290eab4 followlines: join merge parents line ranges in blockdescendants() (issue5595) Denis Laxalde <denis.laxalde@logilab.fr> parents: 33080 diff changeset	383 # information.
b2670290eab4 followlines: join merge parents line ranges in blockdescendants() (issue5595) Denis Laxalde <denis.laxalde@logilab.fr> parents: 33080 diff changeset	384 if i in seen and seen[i][1] != linerange1:
b2670290eab4 followlines: join merge parents line ranges in blockdescendants() (issue5595) Denis Laxalde <denis.laxalde@logilab.fr> parents: 33080 diff changeset	385 lbs, ubs = zip(linerange1, seen[i][1])
b2670290eab4 followlines: join merge parents line ranges in blockdescendants() (issue5595) Denis Laxalde <denis.laxalde@logilab.fr> parents: 33080 diff changeset	386 linerange1 = min(lbs), max(ubs)
32904 582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	387 seen[i] = c, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	388 if inrange:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	389 yield c, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	390
36917 7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	391 @attr.s(slots=True, frozen=True)
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	392 class annotateline(object):
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	393 fctx = attr.ib()
37065 b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API) Yuya Nishihara <yuya@tcha.org> parents: 37064 diff changeset	394 lineno = attr.ib()
36917 7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	395 # Whether this annotation was the result of a skip-annotate.
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	396 skip = attr.ib(default=False)
37066 b33b91ca2ec2 annotate: pack line content into annotateline object (API) Yuya Nishihara <yuya@tcha.org> parents: 37065 diff changeset	397 text = attr.ib(default=None)
36917 7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	398
37064 434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	399 @attr.s(slots=True, frozen=True)
434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	400 class _annotatedfile(object):
434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	401 # list indexed by lineno - 1
434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	402 fctxs = attr.ib()
434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	403 linenos = attr.ib()
434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	404 skips = attr.ib()
434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	405 # full file content
434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	406 text = attr.ib()
434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	407
36919 8fba319750c2 dagop: move lines() out of annotate() Yuya Nishihara <yuya@tcha.org> parents: 36918 diff changeset	408 def _countlines(text):
8fba319750c2 dagop: move lines() out of annotate() Yuya Nishihara <yuya@tcha.org> parents: 36918 diff changeset	409 if text.endswith("\n"):
8fba319750c2 dagop: move lines() out of annotate() Yuya Nishihara <yuya@tcha.org> parents: 36918 diff changeset	410 return text.count("\n")
8fba319750c2 dagop: move lines() out of annotate() Yuya Nishihara <yuya@tcha.org> parents: 36918 diff changeset	411 return text.count("\n") + int(bool(text))
8fba319750c2 dagop: move lines() out of annotate() Yuya Nishihara <yuya@tcha.org> parents: 36918 diff changeset	412
37065 b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API) Yuya Nishihara <yuya@tcha.org> parents: 37064 diff changeset	413 def _decoratelines(text, fctx):
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API) Yuya Nishihara <yuya@tcha.org> parents: 37064 diff changeset	414 n = _countlines(text)
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API) Yuya Nishihara <yuya@tcha.org> parents: 37064 diff changeset	415 linenos = pycompat.rangelist(1, n + 1)
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API) Yuya Nishihara <yuya@tcha.org> parents: 37064 diff changeset	416 return _annotatedfile([fctx] * n, linenos, [False] * n, text)
b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API) Yuya Nishihara <yuya@tcha.org> parents: 37064 diff changeset	417
36917 7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	418 def _annotatepair(parents, childfctx, child, skipchild, diffopts):
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	419 r'''
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	420 Given parent and child fctxes and annotate data for parents, for all lines
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	421 in either parent that match the child, annotate the child with the parent's
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	422 data.
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	423
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	424 Additionally, if `skipchild` is True, replace all other lines with parent
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	425 annotate data as well such that child is never blamed for any lines.
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	426
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	427 See test-annotate.py for unit tests.
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	428 '''
37064 434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	429 pblocks = [(parent, mdiff.allblocks(parent.text, child.text, opts=diffopts))
36917 7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	430 for parent in parents]
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	431
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	432 if skipchild:
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	433 # Need to iterate over the blocks twice -- make it a list
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	434 pblocks = [(p, list(blocks)) for (p, blocks) in pblocks]
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	435 # Mercurial currently prefers p2 over p1 for annotate.
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	436 # TODO: change this?
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	437 for parent, blocks in pblocks:
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	438 for (a1, a2, b1, b2), t in blocks:
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	439 # Changed blocks ('!') or blocks made only of blank lines ('~')
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	440 # belong to the child.
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	441 if t == '=':
37064 434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	442 child.fctxs[b1:b2] = parent.fctxs[a1:a2]
434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	443 child.linenos[b1:b2] = parent.linenos[a1:a2]
434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	444 child.skips[b1:b2] = parent.skips[a1:a2]
36917 7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	445
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	446 if skipchild:
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	447 # Now try and match up anything that couldn't be matched,
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	448 # Reversing pblocks maintains bias towards p2, matching above
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	449 # behavior.
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	450 pblocks.reverse()
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	451
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	452 # The heuristics are:
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	453 # * Work on blocks of changed lines (effectively diff hunks with -U0).
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	454 # This could potentially be smarter but works well enough.
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	455 # * For a non-matching section, do a best-effort fit. Match lines in
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	456 # diff hunks 1:1, dropping lines as necessary.
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	457 # * Repeat the last line as a last resort.
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	458
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	459 # First, replace as much as possible without repeating the last line.
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	460 remaining = [(parent, []) for parent, _blocks in pblocks]
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	461 for idx, (parent, blocks) in enumerate(pblocks):
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	462 for (a1, a2, b1, b2), _t in blocks:
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	463 if a2 - a1 >= b2 - b1:
38783 e7aa113b14f7 global: use pycompat.xrange() Gregory Szorc <gregory.szorc@gmail.com> parents: 37066 diff changeset	464 for bk in pycompat.xrange(b1, b2):
37064 434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	465 if child.fctxs[bk] == childfctx:
36917 7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	466 ak = min(a1 + (bk - b1), a2 - 1)
37064 434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	467 child.fctxs[bk] = parent.fctxs[ak]
434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	468 child.linenos[bk] = parent.linenos[ak]
434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	469 child.skips[bk] = True
36917 7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	470 else:
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	471 remaining[idx][1].append((a1, a2, b1, b2))
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	472
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	473 # Then, look at anything left, which might involve repeating the last
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	474 # line.
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	475 for parent, blocks in remaining:
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	476 for a1, a2, b1, b2 in blocks:
38783 e7aa113b14f7 global: use pycompat.xrange() Gregory Szorc <gregory.szorc@gmail.com> parents: 37066 diff changeset	477 for bk in pycompat.xrange(b1, b2):
37064 434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	478 if child.fctxs[bk] == childfctx:
36917 7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	479 ak = min(a1 + (bk - b1), a2 - 1)
37064 434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	480 child.fctxs[bk] = parent.fctxs[ak]
434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	481 child.linenos[bk] = parent.linenos[ak]
434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	482 child.skips[bk] = True
36917 7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	483 return child
7affcabf561e dagop: move annotateline and _annotatepair from context.py Yuya Nishihara <yuya@tcha.org> parents: 35297 diff changeset	484
37065 b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API) Yuya Nishihara <yuya@tcha.org> parents: 37064 diff changeset	485 def annotate(base, parents, skiprevs=None, diffopts=None):
36918 5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	486 """Core algorithm for filectx.annotate()
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	487
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	488 `parents(fctx)` is a function returning a list of parent filectxs.
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	489 """
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	490
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	491 # This algorithm would prefer to be recursive, but Python is a
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	492 # bit recursion-hostile. Instead we do an iterative
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	493 # depth-first search.
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	494
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	495 # 1st DFS pre-calculates pcache and needed
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	496 visit = [base]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	497 pcache = {}
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	498 needed = {base: 1}
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	499 while visit:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	500 f = visit.pop()
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	501 if f in pcache:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	502 continue
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	503 pl = parents(f)
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	504 pcache[f] = pl
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	505 for p in pl:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	506 needed[p] = needed.get(p, 0) + 1
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	507 if p not in pcache:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	508 visit.append(p)
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	509
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	510 # 2nd DFS does the actual annotate
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	511 visit[:] = [base]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	512 hist = {}
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	513 while visit:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	514 f = visit[-1]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	515 if f in hist:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	516 visit.pop()
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	517 continue
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	518
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	519 ready = True
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	520 pl = pcache[f]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	521 for p in pl:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	522 if p not in hist:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	523 ready = False
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	524 visit.append(p)
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	525 if ready:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	526 visit.pop()
37065 b235bde38a83 annotate: drop linenumber flag from fctx.annotate() (API) Yuya Nishihara <yuya@tcha.org> parents: 37064 diff changeset	527 curr = _decoratelines(f.data(), f)
36918 5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	528 skipchild = False
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	529 if skiprevs is not None:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	530 skipchild = f._changeid in skiprevs
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	531 curr = _annotatepair([hist[p] for p in pl], f, curr, skipchild,
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	532 diffopts)
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	533 for p in pl:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	534 if needed[p] == 1:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	535 del hist[p]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	536 del needed[p]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	537 else:
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	538 needed[p] -= 1
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	539
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	540 hist[f] = curr
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	541 del pcache[f]
5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	542
37064 434e520adb8c annotate: do not construct attr.s object per line while computing history Yuya Nishihara <yuya@tcha.org> parents: 36935 diff changeset	543 a = hist[base]
37066 b33b91ca2ec2 annotate: pack line content into annotateline object (API) Yuya Nishihara <yuya@tcha.org> parents: 37065 diff changeset	544 return [annotateline(*r) for r in zip(a.fctxs, a.linenos, a.skips,
b33b91ca2ec2 annotate: pack line content into annotateline object (API) Yuya Nishihara <yuya@tcha.org> parents: 37065 diff changeset	545 mdiff.splitnewlines(a.text))]
36918 5d3abd6a5b25 dagop: extract core algorithm of annotate() from context.py Yuya Nishihara <yuya@tcha.org> parents: 36917 diff changeset	546
32903 27932a76a88d dagop: split module hosting DAG-related algorithms from revset Yuya Nishihara <yuya@tcha.org> parents: 32885 diff changeset	547 def toposort(revs, parentsfunc, firstbranch=()):
29347 98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	548 """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	549
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	550 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	551 the number of parallel branches and their interleaving.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	552
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	553 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	554
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	555 o 4
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	556 \|
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	557 o 1
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	558 \|
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	559 \| o 3
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	560 \| \|
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	561 \| o 2
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	562 \|/
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	563 o 0
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	564
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	565 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	566 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	567 occur behind a merge.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	568 """
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	569
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	570 ### Quick summary of the algorithm
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	571 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	572 # 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	573 # 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	574 # "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	575 # branches with interleaved revisions.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	576 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	577 # During iteration revs are split into two groups:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	578 # A) revision already emitted
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	579 # 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	580 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	581 # for each REV, we do the following logic:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	582 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	583 # 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	584 # 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	585 # 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	586 # group first.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	587 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	588 # 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	589 # 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	590 # now awaiting for REV.parents() to be available.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	591 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	592 # 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	593 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	594 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	595 # 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	596 # puts it in group (A) from above).
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	597
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	598 revs.sort(reverse=True)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	599
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	600 # 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	601 # 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	602 # need to delay the revisions that reference them.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	603 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	604 # 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	605 # 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	606 # emitted.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	607 unblocked = set(firstbranch)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	608
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	609 # 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	610 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	611 # (revs: lists of revs waiting to be displayed,
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	612 # 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	613 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	614 # 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	615 # 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	616 # 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	617 # 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	618 # 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	619 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	620 # 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	621 # 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	622 # 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	623 # 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	624 # 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	625 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	626 # 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	627 # 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	628 # '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	629 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	630 # 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	631 # 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	632 groups = [([], unblocked)]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	633 pendingheap = []
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	634 pendingset = set()
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	635
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	636 heapq.heapify(pendingheap)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	637 heappop = heapq.heappop
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	638 heappush = heapq.heappush
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	639 for currentrev in revs:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	640 # 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	641 if currentrev not in pendingset:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	642 heappush(pendingheap, -currentrev)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	643 pendingset.add(currentrev)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	644 # 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	645 # processed.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	646 rev = None
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	647 while rev != currentrev:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	648 rev = -heappop(pendingheap)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	649 pendingset.remove(rev)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	650
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	651 # 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	652 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	653
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	654 if matching:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	655 # 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	656 # on the same revision.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	657 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	658 # 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	659 # observed. For example, given two groups:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	660 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	661 # revs [5, 4] waiting for 1
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	662 # revs [3, 2] waiting for 1
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	663 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	664 # 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	665 # 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	666 # 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	667 # 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	668 # 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	669 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	670 # 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	671 # 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	672 # 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	673 # 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	674 targetidx = matching.pop(0)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	675 trevs, tparents = groups[targetidx]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	676 for i in matching:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	677 gr = groups[i]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	678 trevs.extend(gr[0])
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	679 tparents \|= gr[1]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	680 # 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	681 # (starting from the last subgroup for performance and
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	682 # sanity reasons)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	683 for i in reversed(matching):
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	684 del groups[i]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	685 else:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	686 # 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	687 targetidx = len(groups)
32291 bd872f64a8ba cleanup: use set literals Martin von Zweigbergk <martinvonz@google.com> parents: 32085 diff changeset	688 groups.append(([], {rev}))
29347 98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	689
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	690 gr = groups[targetidx]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	691
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	692 # 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	693 # 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	694 # that relied on this rev must precede it.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	695 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	696 # 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	697 # new nodes.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	698 if rev == currentrev: # only display stuff in rev
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	699 gr[0].append(rev)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	700 gr[1].remove(rev)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	701 parents = [p for p in parentsfunc(rev) if p > node.nullrev]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	702 gr[1].update(parents)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	703 for p in parents:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	704 if p not in pendingset:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	705 pendingset.add(p)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	706 heappush(pendingheap, -p)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	707
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	708 # Look for a subgroup to display
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	709 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	710 # 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	711 # 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	712 # 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	713 # 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	714 # subgroup. The heuristic could probably be better.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	715 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	716 # 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	717 # 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	718 # well.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	719 if not unblocked:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	720 if len(groups) > 1: # display other subset
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	721 targetidx = 1
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	722 gr = groups[1]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	723 elif not gr[1] & unblocked:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	724 gr = None
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	725
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	726 if gr is not None:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	727 # 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	728 # subgroup
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	729 unblocked \|= gr[1]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	730 # output all revisions in the subgroup
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	731 for r in gr[0]:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	732 yield r
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	733 # delete the subgroup that you just output
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	734 # 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	735 if targetidx:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	736 del groups[targetidx]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	737 else:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	738 gr[0][:] = []
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	739 # 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	740 # iterate over
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	741 for g in groups:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	742 for r in g[0]:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	743 yield r
39179 1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil Gregory Szorc <gregory.szorc@gmail.com> parents: 38783 diff changeset	744
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil Gregory Szorc <gregory.szorc@gmail.com> parents: 38783 diff changeset	745 def headrevs(revs, parentsfn):
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil Gregory Szorc <gregory.szorc@gmail.com> parents: 38783 diff changeset	746 """Resolve the set of heads from a set of revisions.
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil Gregory Szorc <gregory.szorc@gmail.com> parents: 38783 diff changeset	747
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil Gregory Szorc <gregory.szorc@gmail.com> parents: 38783 diff changeset	748 Receives an iterable of revision numbers and a callbable that receives a
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil Gregory Szorc <gregory.szorc@gmail.com> parents: 38783 diff changeset	749 revision number and returns an iterable of parent revision numbers, possibly
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil Gregory Szorc <gregory.szorc@gmail.com> parents: 38783 diff changeset	750 including nullrev.
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil Gregory Szorc <gregory.szorc@gmail.com> parents: 38783 diff changeset	751
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil Gregory Szorc <gregory.szorc@gmail.com> parents: 38783 diff changeset	752 Returns a set of revision numbers that are DAG heads within the passed
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil Gregory Szorc <gregory.szorc@gmail.com> parents: 38783 diff changeset	753 subset.
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil Gregory Szorc <gregory.szorc@gmail.com> parents: 38783 diff changeset	754
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil Gregory Szorc <gregory.szorc@gmail.com> parents: 38783 diff changeset	755 ``nullrev`` is never included in the returned set, even if it is provided in
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil Gregory Szorc <gregory.szorc@gmail.com> parents: 38783 diff changeset	756 the input set.
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil Gregory Szorc <gregory.szorc@gmail.com> parents: 38783 diff changeset	757 """
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil Gregory Szorc <gregory.szorc@gmail.com> parents: 38783 diff changeset	758 headrevs = set(revs)
42057 566daffc607d cleanup: use set literals where possible Martin von Zweigbergk <martinvonz@google.com> parents: 41533 diff changeset	759 parents = {node.nullrev}
41277 61f9ef23a12f dagop: minor python optimization to `headrevs` Boris Feld <boris.feld@octobus.net> parents: 40000 diff changeset	760 up = parents.update
39179 1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil Gregory Szorc <gregory.szorc@gmail.com> parents: 38783 diff changeset	761
1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil Gregory Szorc <gregory.szorc@gmail.com> parents: 38783 diff changeset	762 for rev in revs:
41277 61f9ef23a12f dagop: minor python optimization to `headrevs` Boris Feld <boris.feld@octobus.net> parents: 40000 diff changeset	763 up(parentsfn(rev))
61f9ef23a12f dagop: minor python optimization to `headrevs` Boris Feld <boris.feld@octobus.net> parents: 40000 diff changeset	764 headrevs.difference_update(parents)
39179 1c3184d7e882 dagop: extract headsetofconnecteds() from dagutil Gregory Szorc <gregory.szorc@gmail.com> parents: 38783 diff changeset	765 return headrevs
39181 0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	766
40000 8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	767 def headrevssubset(revsfn, parentrevsfn, startrev=None, stoprevs=None):
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	768 """Returns the set of all revs that have no children with control.
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	769
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	770 ``revsfn`` is a callable that with no arguments returns an iterator over
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	771 all revision numbers in topological order. With a ``start`` argument, it
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	772 returns revision numbers starting at that number.
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	773
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	774 ``parentrevsfn`` is a callable receiving a revision number and returns an
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	775 iterable of parent revision numbers, where values can include nullrev.
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	776
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	777 ``startrev`` is a revision number at which to start the search.
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	778
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	779 ``stoprevs`` is an iterable of revision numbers that, when encountered,
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	780 will stop DAG traversal beyond them. Parents of revisions in this
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	781 collection will be heads.
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	782 """
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	783 if startrev is None:
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	784 startrev = nullrev
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	785
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	786 stoprevs = set(stoprevs or [])
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	787
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	788 reachable = {startrev}
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	789 heads = {startrev}
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	790
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	791 for rev in revsfn(start=startrev + 1):
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	792 for prev in parentrevsfn(rev):
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	793 if prev in reachable:
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	794 if rev not in stoprevs:
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	795 reachable.add(rev)
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	796 heads.add(rev)
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	797
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	798 if prev in heads and prev not in stoprevs:
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	799 heads.remove(prev)
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	800
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	801 return heads
8af835af0a85 dagop: extract DAG local heads functionality from revlog Gregory Szorc <gregory.szorc@gmail.com> parents: 39999 diff changeset	802
39181 0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	803 def linearize(revs, parentsfn):
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	804 """Linearize and topologically sort a list of revisions.
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	805
39607 5362c96f2feb dagop: fix typo spotted while doing unrelated investigation Augie Fackler <augie@google.com> parents: 39181 diff changeset	806 The linearization process tries to create long runs of revs where a child
39181 0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	807 rev comes immediately after its first parent. This is done by visiting the
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	808 heads of the revs in inverse topological order, and for each visited rev,
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	809 visiting its second parent, then its first parent, then adding the rev
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	810 itself to the output list.
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	811
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	812 Returns a list of revision numbers.
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	813 """
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	814 visit = list(sorted(headrevs(revs, parentsfn), reverse=True))
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	815 finished = set()
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	816 result = []
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	817
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	818 while visit:
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	819 rev = visit.pop()
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	820 if rev < 0:
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	821 rev = -rev - 1
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	822
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	823 if rev not in finished:
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	824 result.append(rev)
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	825 finished.add(rev)
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	826
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	827 else:
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	828 visit.append(-rev - 1)
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	829
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	830 for prev in parentsfn(rev):
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	831 if prev == node.nullrev or prev not in revs or prev in finished:
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	832 continue
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	833
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	834 visit.append(prev)
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	835
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	836 assert len(result) == len(revs)
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	837
0a934ee94f09 dagop: port revlogdag.linearize() to standalone function Gregory Szorc <gregory.szorc@gmail.com> parents: 39179 diff changeset	838 return result

Mercurial > public > mercurial-scm > hg

annotate mercurial/dagop.py @ 42446:055c3e2c44f0