setdiscovery: limit lines to 80 characters

mercurial/dagutil.py

@@ -1,242 +1,248 b''
 # 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 node import nullrev
 
 
 class basedag(object):
     '''generic interface for DAGs
 
     terms:
     "ix" (short for index) identifies a nodes internally,
     "id" identifies one externally.
 
     All params are ixs unless explicitly suffixed otherwise.
     Pluralized params are lists or sets.
     '''
 
     def __init__(self):
         self._inverse = None
 
     def nodeset(self):
         '''set of all node idxs'''
         raise NotImplementedError()
 
     def heads(self):
         '''list of head ixs'''
         raise NotImplementedError()
 
     def parents(self, ix):
         '''list of parents ixs of ix'''
         raise NotImplementedError()
 
     def inverse(self):
         '''inverse DAG, where parents becomes children, etc.'''
         raise NotImplementedError()
 
     def ancestorset(self, starts, stops=None):
-        '''set of all ancestors of starts (incl), but stop walk at stops (excl)'''
+        '''
+        set of all ancestors of starts (incl), but stop walk at stops (excl)
+        '''
         raise NotImplementedError()
 
     def descendantset(self, starts, stops=None):
-        '''set of all descendants of starts (incl), but stop walk at stops (excl)'''
+        '''
+        set of all descendants of starts (incl), but stop walk at stops (excl)
+        '''
         return self.inverse().ancestorset(starts, stops)
 
     def headsetofconnecteds(self, ixs):
-        '''subset of connected list of ixs so that no node has a descendant in it
+        '''
+        subset of connected list of ixs so that no node has a descendant in it
 
         By "connected list" we mean that if an ancestor and a descendant are in
-        the list, then so is at least one path connecting them.'''
+        the list, then so is at least one path connecting them.
+        '''
         raise NotImplementedError()
 
     def externalize(self, ix):
         '''return a list of (or set if given a set) of node ids'''
         return self._externalize(ix)
 
     def externalizeall(self, ixs):
         '''return a list of (or set if given a set) of node ids'''
         ids = self._externalizeall(ixs)
         if isinstance(ixs, set):
             return set(ids)
         return list(ids)
 
     def internalize(self, id):
         '''return a list of (or set if given a set) of node ixs'''
         return self._internalize(id)
 
     def internalizeall(self, ids, filterunknown=False):
         '''return a list of (or set if given a set) of node ids'''
         ixs = self._internalizeall(ids, filterunknown)
         if isinstance(ids, set):
             return set(ixs)
         return list(ixs)
 
 
 class genericdag(basedag):
     '''generic implementations for DAGs'''
 
     def ancestorset(self, starts, stops=None):
         stops = stops and set(stops) or set()
         seen = set()
         pending = list(starts)
         while pending:
             n = pending.pop()
             if n not in seen and n not in stops:
                 seen.add(n)
                 pending.extend(self.parents(n))
         return seen
 
     def headsetofconnecteds(self, ixs):
         hds = set(ixs)
         if not hds:
             return hds
         for n in ixs:
             for p in self.parents(n):
                 hds.discard(p)
         assert hds
         return hds
 
 
 class revlogbaseddag(basedag):
     '''generic dag interface to a revlog'''
 
     def __init__(self, revlog, nodeset):
         basedag.__init__(self)
         self._revlog = revlog
         self._heads = None
         self._nodeset = nodeset
 
     def nodeset(self):
         return self._nodeset
 
     def heads(self):
         if self._heads is None:
             self._heads = self._getheads()
         return self._heads
 
     def _externalize(self, ix):
         return self._revlog.index[ix][7]
     def _externalizeall(self, ixs):
         idx = self._revlog.index
         return [idx[i][7] for i in ixs]
 
     def _internalize(self, id):
         ix = self._revlog.rev(id)
         if ix == nullrev:
             raise LookupError(id, self._revlog.indexfile, _('nullid'))
         return ix
     def _internalizeall(self, ids, filterunknown):
         rl = self._revlog
         if filterunknown:
             return [r for r in map(rl.nodemap.get, ids)
                     if r is not None and r != nullrev]
         return map(self._internalize, ids)
 
 
 class revlogdag(revlogbaseddag):
     '''dag interface to a revlog'''
 
     def __init__(self, revlog):
         revlogbaseddag.__init__(self, revlog, set(xrange(len(revlog))))
 
     def _getheads(self):
         return [r for r in self._revlog.headrevs() if r != nullrev]
 
     def parents(self, ix):
         rlog = self._revlog
         idx = rlog.index
         revdata = idx[ix]
         prev = revdata[5]
         if prev != nullrev:
             prev2 = revdata[6]
             if prev2 == nullrev:
                 return [prev]
             return [prev, prev2]
         prev2 = revdata[6]
         if prev2 != nullrev:
             return [prev2]
         return []
 
     def inverse(self):
         if self._inverse is None:
             self._inverse = inverserevlogdag(self)
         return self._inverse
 
     def ancestorset(self, starts, stops=None):
         rlog = self._revlog
         idx = rlog.index
         stops = stops and set(stops) or set()
         seen = set()
         pending = list(starts)
         while pending:
             rev = pending.pop()
             if rev not in seen and rev not in stops:
                 seen.add(rev)
                 revdata = idx[rev]
                 for i in [5, 6]:
                     prev = revdata[i]
                     if prev != nullrev:
                         pending.append(prev)
         return seen
 
     def headsetofconnecteds(self, ixs):
         if not ixs:
             return set()
         rlog = self._revlog
         idx = rlog.index
         headrevs = set(ixs)
         for rev in ixs:
             revdata = idx[rev]
             for i in [5, 6]:
                 prev = revdata[i]
                 if prev != nullrev:
                     headrevs.discard(prev)
         assert headrevs
         return headrevs
 
 
 class inverserevlogdag(revlogbaseddag, genericdag):
     '''inverse of an existing revlog dag; see revlogdag.inverse()'''
 
     def __init__(self, orig):
         revlogbaseddag.__init__(self, orig._revlog, orig._nodeset)
         self._orig = orig
         self._children = {}
         self._roots = []
         self._walkfrom = len(self._revlog) - 1
 
     def _walkto(self, walkto):
         rev = self._walkfrom
         cs = self._children
         roots = self._roots
         idx = self._revlog.index
         while rev >= walkto:
             data = idx[rev]
             isroot = True
             for prev in [data[5], data[6]]: # parent revs
                 if prev != nullrev:
                     cs.setdefault(prev, []).append(rev)
                     isroot = False
             if isroot:
                 roots.append(rev)
             rev -= 1
         self._walkfrom = rev - 1
 
     def _getheads(self):
         self._walkto(nullrev)
         return self._roots
 
     def parents(self, ix):
         if ix is None:
             return []
         if ix <= self._walkfrom:
             self._walkto(ix)
         return self._children.get(ix, [])
 
     def inverse(self):
         return self._orig

mercurial/setdiscovery.py

@@ -1,178 +1,178 b''
 # setdiscovery.py - improved discovery of common nodeset 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 node import nullid
 from i18n import _
 import random, collections, util, dagutil
 
 def _updatesample(dag, nodes, sample, always, quicksamplesize=0):
     # if nodes is empty we scan the entire graph
     if nodes:
         heads = dag.headsetofconnecteds(nodes)
     else:
         heads = dag.heads()
     dist = {}
     visit = collections.deque(heads)
     seen = set()
     factor = 1
     while visit:
         curr = visit.popleft()
         if curr in seen:
             continue
         d = dist.setdefault(curr, 1)
         if d > factor:
             factor *= 2
         if d == factor:
             if curr not in always: # need this check for the early exit below
                 sample.add(curr)
                 if quicksamplesize and (len(sample) >= quicksamplesize):
                     return
         seen.add(curr)
         for p in dag.parents(curr):
             if not nodes or p in nodes:
                 dist.setdefault(p, d + 1)
                 visit.append(p)
 
 def _setupsample(dag, nodes, size):
     if len(nodes) <= size:
         return set(nodes), None, 0
     always = set(dag.heads())
     desiredlen = size - len(always)
     if desiredlen <= 0:
         # This could be bad if there are very many heads, all unknown to the
         # server. We're counting on long request support here.
         return always, None, desiredlen
     return always, set(), desiredlen
 
 def _takequicksample(dag, nodes, size, initial):
     always, sample, desiredlen = _setupsample(dag, nodes, size)
     if sample is None:
         return always
     if initial:
         fromset = None
     else:
         fromset = nodes
     _updatesample(dag, fromset, sample, always, quicksamplesize=desiredlen)
     sample.update(always)
     return sample
 
 def _takefullsample(dag, nodes, size):
     always, sample, desiredlen = _setupsample(dag, nodes, size)
     if sample is None:
         return always
     # update from heads
     _updatesample(dag, nodes, sample, always)
     # update from roots
     _updatesample(dag.inverse(), nodes, sample, always)
     assert sample
     if len(sample) > desiredlen:
         sample = set(random.sample(sample, desiredlen))
     elif len(sample) < desiredlen:
         more = desiredlen - len(sample)
         sample.update(random.sample(list(nodes - sample - always), more))
     sample.update(always)
     return sample
 
 def findcommonheads(ui, local, remote,
                     initialsamplesize=100,
                     fullsamplesize=200,
                     abortwhenunrelated=True):
-    '''Return a tuple (common, anyincoming, remoteheads) used to identify missing
-    nodes from or in remote.
+    '''Return a tuple (common, anyincoming, remoteheads) used to identify
+    missing nodes from or in remote.
 
     shortcutlocal determines whether we try use direct access to localrepo if
     remote is actually local.
     '''
     roundtrips = 0
     cl = local.changelog
     dag = dagutil.revlogdag(cl)
     nodes = dag.nodeset()
 
     # early exit if we know all the specified server heads already
     ui.debug("query 1; heads\n")
     roundtrips += 1
     srvheadhashes = remote.heads()
 
     ## TODO We might want to request an additional random sample of the server's
     ## nodes batched with the heads query here.
 
     if cl.tip() == nullid:
         if srvheadhashes != [nullid]:
             return [nullid], True, srvheadhashes
         return [nullid], False, []
 
-    # start actual discovery (we note this before the next "if" for compatibility
-    # reasons)
+    # start actual discovery (we note this before the next "if" for
+    # compatibility reasons)
     ui.status(_("searching for changes\n"))
 
     srvheads = dag.internalizeall(srvheadhashes, filterunknown=True)
     if len(srvheads) == len(srvheadhashes):
         ui.note("all remote heads known locally\n")
         return (srvheadhashes, False, srvheadhashes,)
 
     # full blown discovery
     undecided = nodes # own nodes where I don't know if the server knows them
     common = set() # own nodes I know we both know
     missing = set() # own nodes I know the server lacks
 
     # treat remote heads as a first implicit sample response
     common.update(dag.ancestorset(srvheads))
     undecided.difference_update(common)
     # use cheapish initial sample
     if common:
         ui.debug("taking initial sample\n")
         sample = _takefullsample(dag, undecided, size=fullsamplesize)
     else:
         ui.debug("taking quick initial sample\n")
         sample = _takequicksample(dag, nodes, size=initialsamplesize,
                                   initial=True)
 
     roundtrips += 1
     ui.progress(_('searching'), roundtrips, unit=_('queries'))
     ui.debug("query %i; still undecided: %i, sample size is: %i\n"
              % (roundtrips, len(undecided), len(sample)))
     # indices between sample and externalized version must match
     sample = list(sample)
     yesno = remote.known(dag.externalizeall(sample))
 
     while undecided:
         commoninsample = set(n for i, n in enumerate(sample) if yesno[i])
         common.update(dag.ancestorset(commoninsample, common))
 
         missinginsample = [n for i, n in enumerate(sample) if not yesno[i]]
         missing.update(dag.descendantset(missinginsample, missing))
 
         undecided.difference_update(missing)
         undecided.difference_update(common)
 
         if not undecided:
             break
 
         ui.note("sampling from both directions\n")
         sample = _takefullsample(dag, undecided, size=fullsamplesize)
 
         roundtrips += 1
         ui.progress(_('searching'), roundtrips, unit=_('queries'))
         ui.debug("query %i; still undecided: %i, sample size is: %i\n"
                  % (roundtrips, len(undecided), len(sample)))
         # indices between sample and externalized version must match
         sample = list(sample)
         yesno = remote.known(dag.externalizeall(sample))
 
     result = dag.headsetofconnecteds(common)
     ui.progress(_('searching'), None)
     ui.debug("%d total queries\n" % roundtrips)
 
     if not result and srvheadhashes != [nullid]:
         if abortwhenunrelated:
             raise util.Abort(_("repository is unrelated"))
         else:
             ui.warn(_("warning: repository is unrelated\n"))
         return (set([nullid]), True, srvheadhashes,)
 
     return (dag.externalizeall(result), True, srvheadhashes,)