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

annotate mercurial/dagop.py @ 35273:8dee2080f35c

dagop: use fctx.rev() consistently in filectxancestors() We can't use fctx.linkrev() to sort fctxs coming from multiple files. This was changed at 24b57c3899f8 due to performance issue, but we know we evaluate parent.rev() in revset anyway.

author	Yuya Nishihara <yuya@tcha.org>
date	Thu, 22 Sep 2016 18:01:55 +0900
parents	70e86db6a913
children	2b348dc3239a

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
e9cd028f2dff revset: use absolute_import Gregory Szorc <gregory.szorc@gmail.com> parents: 25929 diff changeset	12 from . import (
e9cd028f2dff revset: use absolute_import Gregory Szorc <gregory.szorc@gmail.com> parents: 25929 diff changeset	13 error,
32904 582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	14 mdiff,
25971 e9cd028f2dff revset: use absolute_import Gregory Szorc <gregory.szorc@gmail.com> parents: 25929 diff changeset	15 node,
32904 582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	16 patch,
30881 1be65deb3d54 smartset: move set classes and related functions from revset module (API) Yuya Nishihara <yuya@tcha.org> parents: 30850 diff changeset	17 smartset,
25971 e9cd028f2dff revset: use absolute_import Gregory Szorc <gregory.szorc@gmail.com> parents: 25929 diff changeset	18 )
11275 c9ce8ecd6ca1 revset: introduce revset core Matt Mackall <mpm@selenic.com> parents: diff changeset	19
30881 1be65deb3d54 smartset: move set classes and related functions from revset module (API) Yuya Nishihara <yuya@tcha.org> parents: 30850 diff changeset	20 baseset = smartset.baseset
1be65deb3d54 smartset: move set classes and related functions from revset module (API) Yuya Nishihara <yuya@tcha.org> parents: 30850 diff changeset	21 generatorset = smartset.generatorset
1be65deb3d54 smartset: move set classes and related functions from revset module (API) Yuya Nishihara <yuya@tcha.org> parents: 30850 diff changeset	22
33002 272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	23 # possible maximum depth between null and wdir()
272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	24 _maxlogdepth = 0x80000000
272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	25
33079 550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	26 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	27 """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	28
33079 550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	29 '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	30 if 'reverse' is True/False respectively.
33078 fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	31
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	32 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	33 earlier than the startdepth are omitted.
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	34 """
33003 f63d111258da revset: add startdepth limit to ancestors() as internal option Yuya Nishihara <yuya@tcha.org> parents: 33002 diff changeset	35 if startdepth is None:
f63d111258da revset: add startdepth limit to ancestors() as internal option Yuya Nishihara <yuya@tcha.org> parents: 33002 diff changeset	36 startdepth = 0
33002 272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	37 if stopdepth is None:
272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	38 stopdepth = _maxlogdepth
33027 a10f5f6771f6 dagop: raise ProgrammingError if stopdepth < 0 Martin von Zweigbergk <martinvonz@google.com> parents: 33003 diff changeset	39 if stopdepth == 0:
33002 272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	40 return
33027 a10f5f6771f6 dagop: raise ProgrammingError if stopdepth < 0 Martin von Zweigbergk <martinvonz@google.com> parents: 33003 diff changeset	41 if stopdepth < 0:
a10f5f6771f6 dagop: raise ProgrammingError if stopdepth < 0 Martin von Zweigbergk <martinvonz@google.com> parents: 33003 diff changeset	42 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	43 if reverse:
550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	44 heapsign = -1 # max heap
550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	45 else:
550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	46 heapsign = +1 # min heap
33002 272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	47
32998 c7da57bbae96 dagop: comment why revancestors() doesn't heapify input revs at once Yuya Nishihara <yuya@tcha.org> parents: 32997 diff changeset	48 # 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	49 # 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	50 revs.sort(reverse)
32997 b9e2269aeff8 dagop: unnest inner generator of revancestors() Yuya Nishihara <yuya@tcha.org> parents: 32904 diff changeset	51 irevs = iter(revs)
33079 550c390cd9b2 dagop: make walk direction switchable so it can track descendants Yuya Nishihara <yuya@tcha.org> parents: 33078 diff changeset	52 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	53
32997 b9e2269aeff8 dagop: unnest inner generator of revancestors() Yuya Nishihara <yuya@tcha.org> parents: 32904 diff changeset	54 inputrev = next(irevs, None)
b9e2269aeff8 dagop: unnest inner generator of revancestors() Yuya Nishihara <yuya@tcha.org> parents: 32904 diff changeset	55 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	56 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	57
33000 d3d36bcdf036 dagop: just compare with the last value to deduplicate input of revancestors() Yuya Nishihara <yuya@tcha.org> parents: 32999 diff changeset	58 lastrev = None
32999 08e2793d9f65 dagop: bulk rename variables in revancestors() generator Yuya Nishihara <yuya@tcha.org> parents: 32998 diff changeset	59 while pendingheap:
33001 92d0945a15e0 dagop: compute depth in revancestors() generator Yuya Nishihara <yuya@tcha.org> parents: 33000 diff changeset	60 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	61 currev = heapsign * currev
32999 08e2793d9f65 dagop: bulk rename variables in revancestors() generator Yuya Nishihara <yuya@tcha.org> parents: 32998 diff changeset	62 if currev == inputrev:
32997 b9e2269aeff8 dagop: unnest inner generator of revancestors() Yuya Nishihara <yuya@tcha.org> parents: 32904 diff changeset	63 inputrev = next(irevs, None)
b9e2269aeff8 dagop: unnest inner generator of revancestors() Yuya Nishihara <yuya@tcha.org> parents: 32904 diff changeset	64 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	65 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	66 # 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	67 # 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	68 foundnew = (currev != lastrev)
33003 f63d111258da revset: add startdepth limit to ancestors() as internal option Yuya Nishihara <yuya@tcha.org> parents: 33002 diff changeset	69 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	70 lastrev = currev
32999 08e2793d9f65 dagop: bulk rename variables in revancestors() generator Yuya Nishihara <yuya@tcha.org> parents: 32998 diff changeset	71 yield currev
33002 272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	72 pdepth = curdepth + 1
272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	73 if foundnew and pdepth < stopdepth:
33077 58ebb38456e0 dagop: factor out pfunc from revancestors() generator Yuya Nishihara <yuya@tcha.org> parents: 33076 diff changeset	74 for prev in pfunc(currev):
58ebb38456e0 dagop: factor out pfunc from revancestors() generator Yuya Nishihara <yuya@tcha.org> parents: 33076 diff changeset	75 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	76 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	77
35270 0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	78 def filectxancestors(fctx, followfirst=False):
35272 70e86db6a913 dagop: yield intro filectx by filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35271 diff changeset	79 """Like filectx.ancestors(), but includes the given fctx itself"""
35270 0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	80 visit = {}
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	81 c = fctx
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	82 if followfirst:
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	83 cut = 1
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	84 else:
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	85 cut = None
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	86
35272 70e86db6a913 dagop: yield intro filectx by filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35271 diff changeset	87 yield c
35270 0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	88 while True:
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	89 for parent in c.parents()[:cut]:
35273 8dee2080f35c dagop: use fctx.rev() consistently in filectxancestors() Yuya Nishihara <yuya@tcha.org> parents: 35272 diff changeset	90 visit[(parent.rev(), parent.filenode())] = parent
35270 0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	91 if not visit:
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	92 break
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	93 c = visit.pop(max(visit))
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	94 yield c
0d27685b4a2f dagop: copy basefilectx.ancestors() to free function Yuya Nishihara <yuya@tcha.org> parents: 34065 diff changeset	95
34065 c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	96 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	97 if followfirst:
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	98 cut = 1
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	99 else:
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	100 cut = None
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	101 cl = repo.changelog
34065 c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	102 def plainpfunc(rev):
33078 fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	103 try:
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	104 return cl.parentrevs(rev)[:cut]
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	105 except error.WdirUnsupported:
fb663bd0243f dagop: factor out generator of ancestor nodes Yuya Nishihara <yuya@tcha.org> parents: 33077 diff changeset	106 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	107 if cutfunc is None:
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	108 pfunc = plainpfunc
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	109 else:
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	110 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	111 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	112 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	113
34065 c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	114 def revancestors(repo, revs, followfirst=False, startdepth=None,
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	115 stopdepth=None, cutfunc=None):
33002 272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	116 """Like revlog.ancestors(), but supports additional options, includes
272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	117 the given revs themselves, and returns a smartset
272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	118
33003 f63d111258da revset: add startdepth limit to ancestors() as internal option Yuya Nishihara <yuya@tcha.org> parents: 33002 diff changeset	119 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	120 earlier than the startdepth are omitted.
34065 c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	121
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	122 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	123 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	124 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	125 optimization sometimes.
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	126
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	127 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	128 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	129 return True in this case. For example,
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	130
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	131 D # revancestors(repo, D, cutfunc=lambda rev: rev == B)
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	132 \|\ # 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	133 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	134 \|/
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	135 A
33002 272a44cac57e revset: add depth limit to ancestors() Yuya Nishihara <yuya@tcha.org> parents: 33001 diff changeset	136 """
34065 c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	137 gen = _genrevancestors(repo, revs, followfirst, startdepth, stopdepth,
c6c8a52e28c9 revset: optimize "draft() & ::x" pattern Jun Wu <quark@fb.com> parents: 33284 diff changeset	138 cutfunc)
32997 b9e2269aeff8 dagop: unnest inner generator of revancestors() Yuya Nishihara <yuya@tcha.org> parents: 32904 diff changeset	139 return generatorset(gen, iterasc=False)
16409 2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations Patrick Mezard <patrick@mezard.eu> parents: 16402 diff changeset	140
33073 b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	141 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	142 if followfirst:
6ddc86eedc3b style: kill ersatz if-else ternary operators Jordi Guti?rrez Hermoso <jordigh@octave.org> parents: 24219 diff changeset	143 cut = 1
6ddc86eedc3b style: kill ersatz if-else ternary operators Jordi Guti?rrez Hermoso <jordigh@octave.org> parents: 24219 diff changeset	144 else:
6ddc86eedc3b style: kill ersatz if-else ternary operators Jordi Guti?rrez Hermoso <jordigh@octave.org> parents: 24219 diff changeset	145 cut = None
16409 2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations Patrick Mezard <patrick@mezard.eu> parents: 16402 diff changeset	146
33073 b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	147 cl = repo.changelog
33076 a76a64c78807 dagop: use smartset.min() in revdescendants() generator Yuya Nishihara <yuya@tcha.org> parents: 33075 diff changeset	148 first = revs.min()
33073 b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	149 nullrev = node.nullrev
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	150 if first == nullrev:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	151 # 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	152 # 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	153 yield first
33073 b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	154 for i in cl:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	155 yield i
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	156 else:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	157 seen = set(revs)
33075 d83b189aef83 dagop: change revdescendants() to include all root revisions Yuya Nishihara <yuya@tcha.org> parents: 33073 diff changeset	158 for i in cl.revs(first):
d83b189aef83 dagop: change revdescendants() to include all root revisions Yuya Nishihara <yuya@tcha.org> parents: 33073 diff changeset	159 if i in seen:
d83b189aef83 dagop: change revdescendants() to include all root revisions Yuya Nishihara <yuya@tcha.org> parents: 33073 diff changeset	160 yield i
d83b189aef83 dagop: change revdescendants() to include all root revisions Yuya Nishihara <yuya@tcha.org> parents: 33073 diff changeset	161 continue
33073 b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	162 for x in cl.parentrevs(i)[:cut]:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	163 if x != nullrev and x in seen:
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	164 seen.add(i)
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	165 yield i
b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	166 break
20692 7af341082b76 revset: changed descendants revset to use lazy generators Lucas Moscovicz <lmoscovicz@fb.com> parents: 20691 diff changeset	167
33080 a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	168 def _builddescendantsmap(repo, startrev, followfirst):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	169 """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	170 cl = repo.changelog
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	171 nullrev = node.nullrev
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	172 descmap = [[] for _rev in xrange(startrev, len(cl))]
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	173 for currev in cl.revs(startrev + 1):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	174 p1rev, p2rev = cl.parentrevs(currev)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	175 if p1rev >= startrev:
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	176 descmap[p1rev - startrev].append(currev)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	177 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	178 descmap[p2rev - startrev].append(currev)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	179 return descmap
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	180
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	181 def _genrevdescendantsofdepth(repo, revs, followfirst, startdepth, stopdepth):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	182 startrev = revs.min()
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	183 descmap = _builddescendantsmap(repo, startrev, followfirst)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	184 def pfunc(rev):
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	185 return descmap[rev - startrev]
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	186 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	187
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	188 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	189 """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	190 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	191
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	192 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	193 earlier than the startdepth are omitted.
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	194 """
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	195 if startdepth is None and stopdepth is None:
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	196 gen = _genrevdescendants(repo, revs, followfirst)
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	197 else:
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	198 gen = _genrevdescendantsofdepth(repo, revs, followfirst,
a53bfc2845f2 revset: add depth limit to descendants() (issue5374) Yuya Nishihara <yuya@tcha.org> parents: 33079 diff changeset	199 startdepth, stopdepth)
33073 b04cf7a6e0f3 dagop: unnest inner generator of revdescendants() Yuya Nishihara <yuya@tcha.org> parents: 33027 diff changeset	200 return generatorset(gen, iterasc=True)
16409 2cbd7dd0cc1f graphlog: fix --follow-first --rev combinations Patrick Mezard <patrick@mezard.eu> parents: 16402 diff changeset	201
26095 6eed95ca4c03 revset: mark reachablerootspure as private Yuya Nishihara <yuya@tcha.org> parents: 26094 diff changeset	202 def _reachablerootspure(repo, minroot, roots, heads, includepath):
26002 fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument Laurent Charignon <lcharignon@fb.com> parents: 26001 diff changeset	203 """return (heads(::<roots> and ::<heads>))
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument Laurent Charignon <lcharignon@fb.com> parents: 26001 diff changeset	204
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument Laurent Charignon <lcharignon@fb.com> parents: 26001 diff changeset	205 If includepath is True, return (<roots>::<heads>)."""
16862 b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	206 if not roots:
26094 df41c7be16d6 reachableroots: construct and sort baseset in revset module Yuya Nishihara <yuya@tcha.org> parents: 26093 diff changeset	207 return []
16862 b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	208 parentrevs = repo.changelog.parentrevs
26053 b68c9d232db6 reachableroots: use internal "revstates" array to test if rev is a root Yuya Nishihara <yuya@tcha.org> parents: 26006 diff changeset	209 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	210 visit = list(heads)
16862 b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	211 reachable = set()
b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	212 seen = {}
25566 15412bba5a68 revset: prefetch all attributes before loop in _revsbetween Pierre-Yves David <pierre-yves.david@fb.com> parents: 25554 diff changeset	213 # 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	214 reached = reachable.add
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween Pierre-Yves David <pierre-yves.david@fb.com> parents: 25554 diff changeset	215 dovisit = visit.append
15412bba5a68 revset: prefetch all attributes before loop in _revsbetween Pierre-Yves David <pierre-yves.david@fb.com> parents: 25554 diff changeset	216 nextvisit = visit.pop
16862 b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	217 # 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	218 # sys.getrecursionlimit()
b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	219 while visit:
25566 15412bba5a68 revset: prefetch all attributes before loop in _revsbetween Pierre-Yves David <pierre-yves.david@fb.com> parents: 25554 diff changeset	220 rev = nextvisit()
16862 b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	221 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	222 reached(rev)
26002 fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument Laurent Charignon <lcharignon@fb.com> parents: 26001 diff changeset	223 if not includepath:
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument Laurent Charignon <lcharignon@fb.com> parents: 26001 diff changeset	224 continue
16862 b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	225 parents = parentrevs(rev)
b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	226 seen[rev] = parents
b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	227 for parent in parents:
b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	228 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	229 dovisit(parent)
16862 b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	230 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	231 return baseset()
26002 fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument Laurent Charignon <lcharignon@fb.com> parents: 26001 diff changeset	232 if not includepath:
fd92bfbbe02d revset: rename revsbetween to reachableroots and add an argument Laurent Charignon <lcharignon@fb.com> parents: 26001 diff changeset	233 return reachable
16862 b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	234 for rev in sorted(seen):
b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	235 for parent in seen[rev]:
b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	236 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	237 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	238 return reachable
16862 b6efeb27e733 revset: introduce and use _revsbetween Bryan O'Sullivan <bryano@fb.com> parents: 16861 diff changeset	239
26006 1ffd97cbf9a2 reachableroots: default to the C implementation Laurent Charignon <lcharignon@fb.com> parents: 26002 diff changeset	240 def reachableroots(repo, roots, heads, includepath=False):
1ffd97cbf9a2 reachableroots: default to the C implementation Laurent Charignon <lcharignon@fb.com> parents: 26002 diff changeset	241 """return (heads(::<roots> and ::<heads>))
1ffd97cbf9a2 reachableroots: default to the C implementation Laurent Charignon <lcharignon@fb.com> parents: 26002 diff changeset	242
1ffd97cbf9a2 reachableroots: default to the C implementation Laurent Charignon <lcharignon@fb.com> parents: 26002 diff changeset	243 If includepath is True, return (<roots>::<heads>)."""
1ffd97cbf9a2 reachableroots: default to the C implementation Laurent Charignon <lcharignon@fb.com> parents: 26002 diff changeset	244 if not roots:
1ffd97cbf9a2 reachableroots: default to the C implementation Laurent Charignon <lcharignon@fb.com> parents: 26002 diff changeset	245 return baseset()
26093 204131131766 reachableroots: use smartset min Pierre-Yves David <pierre-yves.david@fb.com> parents: 26091 diff changeset	246 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	247 roots = list(roots)
26006 1ffd97cbf9a2 reachableroots: default to the C implementation Laurent Charignon <lcharignon@fb.com> parents: 26002 diff changeset	248 heads = list(heads)
1ffd97cbf9a2 reachableroots: default to the C implementation Laurent Charignon <lcharignon@fb.com> parents: 26002 diff changeset	249 try:
26094 df41c7be16d6 reachableroots: construct and sort baseset in revset module Yuya Nishihara <yuya@tcha.org> parents: 26093 diff changeset	250 revs = repo.changelog.reachableroots(minroot, heads, roots, includepath)
26006 1ffd97cbf9a2 reachableroots: default to the C implementation Laurent Charignon <lcharignon@fb.com> parents: 26002 diff changeset	251 except AttributeError:
26095 6eed95ca4c03 revset: mark reachablerootspure as private Yuya Nishihara <yuya@tcha.org> parents: 26094 diff changeset	252 revs = _reachablerootspure(repo, minroot, roots, heads, includepath)
26094 df41c7be16d6 reachableroots: construct and sort baseset in revset module Yuya Nishihara <yuya@tcha.org> parents: 26093 diff changeset	253 revs = baseset(revs)
df41c7be16d6 reachableroots: construct and sort baseset in revset module Yuya Nishihara <yuya@tcha.org> parents: 26093 diff changeset	254 revs.sort()
df41c7be16d6 reachableroots: construct and sort baseset in revset module Yuya Nishihara <yuya@tcha.org> parents: 26093 diff changeset	255 return revs
26006 1ffd97cbf9a2 reachableroots: default to the C implementation Laurent Charignon <lcharignon@fb.com> parents: 26002 diff changeset	256
32904 582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	257 def _changesrange(fctx1, fctx2, linerange2, diffopts):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	258 """Return `(diffinrange, linerange1)` where `diffinrange` is True
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	259 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	260 `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	261 """
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	262 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	263 filteredblocks, linerange1 = mdiff.blocksinrange(blocks, linerange2)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	264 diffinrange = any(stype == '!' for _, stype in filteredblocks)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	265 return diffinrange, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	266
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	267 def blockancestors(fctx, fromline, toline, followfirst=False):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	268 """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	269 `fromline`-`toline` range.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	270 """
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	271 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	272 fctx = fctx.introfilectx()
32904 582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	273 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	274 while visit:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	275 c, linerange2 = visit.pop(max(visit))
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	276 pl = c.parents()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	277 if followfirst:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	278 pl = pl[:1]
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	279 if not pl:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	280 # The block originates from the initial revision.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	281 yield c, linerange2
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	282 continue
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	283 inrange = False
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	284 for p in pl:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	285 inrangep, linerange1 = _changesrange(p, c, linerange2, diffopts)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	286 inrange = inrange or inrangep
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	287 if linerange1[0] == linerange1[1]:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	288 # 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	289 # 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	290 # branch.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	291 continue
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	292 # 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	293 # _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	294 # (as srcrev) instead possibly topmost introrev.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	295 p._descendantrev = c.rev()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	296 visit[p.linkrev(), p.filenode()] = p, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	297 if inrange:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	298 yield c, linerange2
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	299
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	300 def blockdescendants(fctx, fromline, toline):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	301 """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	302 `fromline`-`toline` range.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	303 """
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	304 # 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	305 # its parents.
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	306 try:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	307 c, linerange1 = next(blockancestors(fctx, fromline, toline))
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	308 except StopIteration:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	309 pass
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	310 else:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	311 if c == fctx:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	312 yield c, linerange1
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 diffopts = patch.diffopts(fctx._repo.ui)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	315 fl = fctx.filelog()
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	316 seen = {fctx.filerev(): (fctx, (fromline, toline))}
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	317 for i in fl.descendants([fctx.filerev()]):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	318 c = fctx.filectx(i)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	319 inrange = False
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	320 for x in fl.parentrevs(i):
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	321 try:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	322 p, linerange2 = seen[x]
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	323 except KeyError:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	324 # nullrev or other branch
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	325 continue
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	326 inrangep, linerange1 = _changesrange(c, p, linerange2, diffopts)
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	327 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	328 # 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	329 # 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	330 # 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	331 # information.
b2670290eab4 followlines: join merge parents line ranges in blockdescendants() (issue5595) Denis Laxalde <denis.laxalde@logilab.fr> parents: 33080 diff changeset	332 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	333 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	334 linerange1 = min(lbs), max(ubs)
32904 582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	335 seen[i] = c, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	336 if inrange:
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	337 yield c, linerange1
582080a4a812 dagop: move blockancestors() and blockdescendants() from context Yuya Nishihara <yuya@tcha.org> parents: 32903 diff changeset	338
32903 27932a76a88d dagop: split module hosting DAG-related algorithms from revset Yuya Nishihara <yuya@tcha.org> parents: 32885 diff changeset	339 def toposort(revs, parentsfunc, firstbranch=()):
29347 98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	340 """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	341
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	342 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	343 the number of parallel branches and their interleaving.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	344
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	345 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	346
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	347 o 4
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	348 \|
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	349 o 1
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	350 \|
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	351 \| o 3
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	352 \| \|
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	353 \| o 2
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	354 \|/
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	355 o 0
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	356
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	357 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	358 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	359 occur behind a merge.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	360 """
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	361
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	362 ### Quick summary of the algorithm
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	363 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	364 # 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	365 # 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	366 # "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	367 # branches with interleaved revisions.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	368 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	369 # During iteration revs are split into two groups:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	370 # A) revision already emitted
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	371 # 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	372 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	373 # for each REV, we do the following logic:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	374 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	375 # 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	376 # 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	377 # 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	378 # group first.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	379 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	380 # 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	381 # 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	382 # now awaiting for REV.parents() to be available.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	383 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	384 # 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	385 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	386 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	387 # 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	388 # puts it in group (A) from above).
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	389
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	390 revs.sort(reverse=True)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	391
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	392 # 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	393 # 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	394 # need to delay the revisions that reference them.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	395 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	396 # 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	397 # 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	398 # emitted.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	399 unblocked = set(firstbranch)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	400
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	401 # 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	402 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	403 # (revs: lists of revs waiting to be displayed,
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	404 # 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	405 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	406 # 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	407 # 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	408 # 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	409 # 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	410 # 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	411 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	412 # 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	413 # 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	414 # 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	415 # 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	416 # 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	417 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	418 # 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	419 # 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	420 # '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	421 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	422 # 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	423 # 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	424 groups = [([], unblocked)]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	425 pendingheap = []
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	426 pendingset = set()
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	427
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	428 heapq.heapify(pendingheap)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	429 heappop = heapq.heappop
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	430 heappush = heapq.heappush
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	431 for currentrev in revs:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	432 # 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	433 if currentrev not in pendingset:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	434 heappush(pendingheap, -currentrev)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	435 pendingset.add(currentrev)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	436 # 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	437 # processed.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	438 rev = None
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	439 while rev != currentrev:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	440 rev = -heappop(pendingheap)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	441 pendingset.remove(rev)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	442
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	443 # 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	444 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	445
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	446 if matching:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	447 # 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	448 # on the same revision.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	449 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	450 # 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	451 # observed. For example, given two groups:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	452 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	453 # revs [5, 4] waiting for 1
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	454 # revs [3, 2] waiting for 1
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	455 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	456 # 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	457 # 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	458 # 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	459 # 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	460 # 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	461 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	462 # 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	463 # 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	464 # 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	465 # 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	466 targetidx = matching.pop(0)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	467 trevs, tparents = groups[targetidx]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	468 for i in matching:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	469 gr = groups[i]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	470 trevs.extend(gr[0])
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	471 tparents \|= gr[1]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	472 # 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	473 # (starting from the last subgroup for performance and
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	474 # sanity reasons)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	475 for i in reversed(matching):
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	476 del groups[i]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	477 else:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	478 # 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	479 targetidx = len(groups)
32291 bd872f64a8ba cleanup: use set literals Martin von Zweigbergk <martinvonz@google.com> parents: 32085 diff changeset	480 groups.append(([], {rev}))
29347 98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	481
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	482 gr = groups[targetidx]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	483
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	484 # 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	485 # 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	486 # that relied on this rev must precede it.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	487 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	488 # 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	489 # new nodes.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	490 if rev == currentrev: # only display stuff in rev
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	491 gr[0].append(rev)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	492 gr[1].remove(rev)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	493 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	494 gr[1].update(parents)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	495 for p in parents:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	496 if p not in pendingset:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	497 pendingset.add(p)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	498 heappush(pendingheap, -p)
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	499
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	500 # Look for a subgroup to display
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	501 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	502 # 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	503 # 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	504 # 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	505 # 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	506 # subgroup. The heuristic could probably be better.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	507 #
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	508 # 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	509 # 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	510 # well.
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	511 if not unblocked:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	512 if len(groups) > 1: # display other subset
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	513 targetidx = 1
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	514 gr = groups[1]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	515 elif not gr[1] & unblocked:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	516 gr = None
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	517
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	518 if gr is not None:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	519 # 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	520 # subgroup
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	521 unblocked \|= gr[1]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	522 # output all revisions in the subgroup
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	523 for r in gr[0]:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	524 yield r
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	525 # delete the subgroup that you just output
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	526 # 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	527 if targetidx:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	528 del groups[targetidx]
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	529 else:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	530 gr[0][:] = []
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	531 # 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	532 # iterate over
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	533 for g in groups:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	534 for r in g[0]:
98535ad46fc0 revset: move groupbranchiter over from graphmod Martijn Pieters <mjpieters@fb.com> parents: 29346 diff changeset	535 yield r

Mercurial > public > mercurial-scm > hg

annotate mercurial/dagop.py @ 35273:8dee2080f35c