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