view mercurial/dagutil.py @ 39180:8de526995844

dagutil: use revlog.parentrevs() for resolving parent revisions

And remove parents() since it is no longer used.

revlog.parentrevs() is almost the same as parents(). The main
difference is that parentrevs() can return nullrev. dagop.headrevs()
already handles nullrev. We add an inline check for nullrev in the
other call site to account for the difference.

.. api:: parents() removed from dagutil classes

   Use parentrevs() on the storage object instead.

Differential Revision: https://phab.mercurial-scm.org/D4328

# dagutil.py - dag utilities for mercurial
#
# Copyright 2010 Benoit Boissinot <[e-mail]>
# and Peter Arrenbrecht <[e-mail]>
#
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version.

from __future__ import absolute_import

from .node import nullrev

from . import (
    dagop,
)

class revlogdag(object):
    '''dag interface to a revlog'''

    def __init__(self, revlog):
        self._revlog = revlog

    def linearize(self, ixs):
        '''linearize and topologically sort a list of revisions

        The linearization process tries to create long runs of revs where
        a child rev comes immediately after its first parent. This is done by
        visiting the heads of the given revs in inverse topological order,
        and for each visited rev, visiting its second parent, then its first
        parent, then adding the rev itself to the output list.
        '''
        sorted = []
        visit = list(dagop.headrevs(ixs, self._revlog.parentrevs))
        visit.sort(reverse=True)
        finished = set()

        while visit:
            cur = visit.pop()
            if cur < 0:
                cur = -cur - 1
                if cur not in finished:
                    sorted.append(cur)
                    finished.add(cur)
            else:
                visit.append(-cur - 1)
                visit += [p for p in self._revlog.parentrevs(cur)
                          if p != nullrev and p in ixs and p not in finished]
        assert len(sorted) == len(ixs)
        return sorted