1 # dagutil.py - dag utilities for mercurial

     2 #

     3 # Copyright 2010 Benoit Boissinot <bboissin@gmail.com>

     4 # and Peter Arrenbrecht <peter@arrenbrecht.ch>

     5 #

     6 # This software may be used and distributed according to the terms of the

     7 # GNU General Public License version 2 or any later version.

     8 

     9 from __future__ import absolute_import

    10 

    11 from .i18n import _

    12 from .node import nullrev

    13 

    14 class basedag(object):

    15     '''generic interface for DAGs

    16 

    17     terms:

    18     "ix" (short for index) identifies a nodes internally,

    19     "id" identifies one externally.

    20 

    21     All params are ixs unless explicitly suffixed otherwise.

    22     Pluralized params are lists or sets.

    23     '''

    24 

    25     def __init__(self):

    26         self._inverse = None

    27 

    28     def nodeset(self):

    29         '''set of all node ixs'''

    30         raise NotImplementedError

    31 

    32     def heads(self):

    33         '''list of head ixs'''

    34         raise NotImplementedError

    35 

    36     def parents(self, ix):

    37         '''list of parents ixs of ix'''

    38         raise NotImplementedError

    39 

    40     def inverse(self):

    41         '''inverse DAG, where parents becomes children, etc.'''

    42         raise NotImplementedError

    43 

    44     def ancestorset(self, starts, stops=None):

    45         '''

    46         set of all ancestors of starts (incl), but stop walk at stops (excl)

    47         '''

    48         raise NotImplementedError

    49 

    50     def descendantset(self, starts, stops=None):

    51         '''

    52         set of all descendants of starts (incl), but stop walk at stops (excl)

    53         '''

    54         return self.inverse().ancestorset(starts, stops)

    55 

    56     def headsetofconnecteds(self, ixs):

    57         '''

    58         subset of connected list of ixs so that no node has a descendant in it

    59 

    60         By "connected list" we mean that if an ancestor and a descendant are in

    61         the list, then so is at least one path connecting them.

    62         '''

    63         raise NotImplementedError

    64 

    65     def externalize(self, ix):

    66         '''return a node id'''

    67         return self._externalize(ix)

    68 

    69     def externalizeall(self, ixs):

    70         '''return a list of (or set if given a set) of node ids'''

    71         ids = self._externalizeall(ixs)

    72         if isinstance(ixs, set):

    73             return set(ids)

    74         return list(ids)

    75 

    76     def internalize(self, id):

    77         '''return a node ix'''

    78         return self._internalize(id)

    79 

    80     def internalizeall(self, ids, filterunknown=False):

    81         '''return a list of (or set if given a set) of node ixs'''

    82         ixs = self._internalizeall(ids, filterunknown)

    83         if isinstance(ids, set):

    84             return set(ixs)

    85         return list(ixs)

    86 

    87 

    88 class genericdag(basedag):

    89     '''generic implementations for DAGs'''

    90 

    91     def ancestorset(self, starts, stops=None):

    92         if stops:

    93             stops = set(stops)

    94         else:

    95             stops = set()

    96         seen = set()

    97         pending = list(starts)

    98         while pending:

    99             n = pending.pop()

   100             if n not in seen and n not in stops:

   101                 seen.add(n)

   102                 pending.extend(self.parents(n))

   103         return seen

   104 

   105     def headsetofconnecteds(self, ixs):

   106         hds = set(ixs)

   107         if not hds:

   108             return hds

   109         for n in ixs:

   110             for p in self.parents(n):

   111                 hds.discard(p)

   112         assert hds

   113         return hds

   114 

   115 

   116 class revlogbaseddag(basedag):

   117     '''generic dag interface to a revlog'''

   118 

   119     def __init__(self, revlog, nodeset):

   120         basedag.__init__(self)

   121         self._revlog = revlog

   122         self._heads = None

   123         self._nodeset = nodeset

   124 

   125     def nodeset(self):

   126         return self._nodeset

   127 

   128     def heads(self):

   129         if self._heads is None:

   130             self._heads = self._getheads()

   131         return self._heads

   132 

   133     def _externalize(self, ix):

   134         return self._revlog.index[ix][7]

   135     def _externalizeall(self, ixs):

   136         idx = self._revlog.index

   137         return [idx[i][7] for i in ixs]

   138 

   139     def _internalize(self, id):

   140         ix = self._revlog.rev(id)

   141         if ix == nullrev:

   142             raise LookupError(id, self._revlog.indexfile, _('nullid'))

   143         return ix

   144     def _internalizeall(self, ids, filterunknown):

   145         rl = self._revlog

   146         if filterunknown:

   147             return [r for r in map(rl.nodemap.get, ids)

   148                     if (r is not None

   149                         and r != nullrev

   150                         and r not in rl.filteredrevs)]

   151         return [self._internalize(i) for i in ids]

   152 

   153 

   154 class revlogdag(revlogbaseddag):

   155     '''dag interface to a revlog'''

   156 

   157     def __init__(self, revlog, localsubset=None):

   158         revlogbaseddag.__init__(self, revlog, set(revlog))

   159         self._heads = localsubset

   160 

   161     def _getheads(self):

   162         return [r for r in self._revlog.headrevs() if r != nullrev]

   163 

   164     def parents(self, ix):

   165         rlog = self._revlog

   166         idx = rlog.index

   167         revdata = idx[ix]

   168         prev = revdata[5]

   169         if prev != nullrev:

   170             prev2 = revdata[6]

   171             if prev2 == nullrev:

   172                 return [prev]

   173             return [prev, prev2]

   174         prev2 = revdata[6]

   175         if prev2 != nullrev:

   176             return [prev2]

   177         return []

   178 

   179     def inverse(self):

   180         if self._inverse is None:

   181             self._inverse = inverserevlogdag(self)

   182         return self._inverse

   183 

   184     def ancestorset(self, starts, stops=None):

   185         rlog = self._revlog

   186         idx = rlog.index

   187         if stops:

   188             stops = set(stops)

   189         else:

   190             stops = set()

   191         seen = set()

   192         pending = list(starts)

   193         while pending:

   194             rev = pending.pop()

   195             if rev not in seen and rev not in stops:

   196                 seen.add(rev)

   197                 revdata = idx[rev]

   198                 for i in [5, 6]:

   199                     prev = revdata[i]

   200                     if prev != nullrev:

   201                         pending.append(prev)

   202         return seen

   203 

   204     def headsetofconnecteds(self, ixs):

   205         if not ixs:

   206             return set()

   207         rlog = self._revlog

   208         idx = rlog.index

   209         headrevs = set(ixs)

   210         for rev in ixs:

   211             revdata = idx[rev]

   212             for i in [5, 6]:

   213                 prev = revdata[i]

   214                 if prev != nullrev:

   215                     headrevs.discard(prev)

   216         assert headrevs

   217         return headrevs

   218 

   219     def linearize(self, ixs):

   220         '''linearize and topologically sort a list of revisions

   221 

   222         The linearization process tries to create long runs of revs where

   223         a child rev comes immediately after its first parent. This is done by

   224         visiting the heads of the given revs in inverse topological order,

   225         and for each visited rev, visiting its second parent, then its first

   226         parent, then adding the rev itself to the output list.

   227         '''

   228         sorted = []

   229         visit = list(self.headsetofconnecteds(ixs))

   230         visit.sort(reverse=True)

   231         finished = set()

   232 

   233         while visit:

   234             cur = visit.pop()

   235             if cur < 0:

   236                 cur = -cur - 1

   237                 if cur not in finished:

   238                     sorted.append(cur)

   239                     finished.add(cur)

   240             else:

   241                 visit.append(-cur - 1)

   242                 visit += [p for p in self.parents(cur)

   243                           if p in ixs and p not in finished]

   244         assert len(sorted) == len(ixs)

   245         return sorted

   246 

   247 

   248 class inverserevlogdag(revlogbaseddag, genericdag):

   249     '''inverse of an existing revlog dag; see revlogdag.inverse()'''

   250 

   251     def __init__(self, orig):

   252         revlogbaseddag.__init__(self, orig._revlog, orig._nodeset)

   253         self._orig = orig

   254         self._children = {}

   255         self._roots = []

   256         self._walkfrom = len(self._revlog) - 1

   257 

   258     def _walkto(self, walkto):

   259         rev = self._walkfrom

   260         cs = self._children

   261         roots = self._roots

   262         idx = self._revlog.index

   263         while rev >= walkto:

   264             data = idx[rev]

   265             isroot = True

   266             for prev in [data[5], data[6]]: # parent revs

   267                 if prev != nullrev:

   268                     cs.setdefault(prev, []).append(rev)

   269                     isroot = False

   270             if isroot:

   271                 roots.append(rev)

   272             rev -= 1

   273         self._walkfrom = rev

   274 

   275     def _getheads(self):

   276         self._walkto(nullrev)

   277         return self._roots

   278 

   279     def parents(self, ix):

   280         if ix is None:

   281             return []

   282         if ix <= self._walkfrom:

   283             self._walkto(ix)

   284         return self._children.get(ix, [])

   285 

   286     def inverse(self):

   287         return self._orig