dagutil: fix off-by-one in inverserevlogdag buildup

mercurial/dagutil.py

@@ -1,277 +1,277 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
 from i18n import _
 
 
 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)
         '''
         raise NotImplementedError()
 
     def descendantset(self, starts, stops=None):
         '''
         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
 
         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.
         '''
         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
 
     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(self.headsetofconnecteds(ixs))
         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.parents(cur)
                           if p in ixs and p not in finished]
         assert len(sorted) == len(ixs)
         return sorted
 
 
 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
+        self._walkfrom = rev
 
     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

tests/test-setdiscovery.t

@@ -1,268 +1,268 b''
 
 Function to test discovery between two repos in both directions, using both the local shortcut
 (which is currently not activated by default) and the full remotable protocol:
 
   $ testdesc() { # revs_a, revs_b, dagdesc
   >     if [ -d foo ]; then rm -rf foo; fi
   >     hg init foo
   >     cd foo
   >     hg debugbuilddag "$3"
   >     hg clone . a $1 --quiet
   >     hg clone . b $2 --quiet
   >     echo
   >     echo "% -- a -> b tree"
   >     hg -R a debugdiscovery b --verbose --old
   >     echo
   >     echo "% -- a -> b set"
   >     hg -R a debugdiscovery b --verbose --debug
   >     echo
   >     echo "% -- b -> a tree"
   >     hg -R b debugdiscovery a --verbose --old
   >     echo
   >     echo "% -- b -> a set"
   >     hg -R b debugdiscovery a --verbose --debug
   >     cd ..
   > }
 
 
 Small superset:
 
   $ testdesc '-ra1 -ra2' '-rb1 -rb2 -rb3' '
   > +2:f +1:a1:b1
   > <f +4 :a2
   > +5 :b2
   > <f +3 :b3'
   
   % -- a -> b tree
   comparing with b
   searching for changes
   unpruned common: b5714e113bc0 66f7d451a68b 01241442b3c2
   common heads: b5714e113bc0 01241442b3c2
   local is subset
   
   % -- a -> b set
   comparing with b
   query 1; heads
   searching for changes
   all local heads known remotely
   common heads: b5714e113bc0 01241442b3c2
   local is subset
   
   % -- b -> a tree
   comparing with a
   searching for changes
   unpruned common: b5714e113bc0 01241442b3c2
   common heads: b5714e113bc0 01241442b3c2
   remote is subset
   
   % -- b -> a set
   comparing with a
   query 1; heads
   searching for changes
   all remote heads known locally
   common heads: b5714e113bc0 01241442b3c2
   remote is subset
 
 
 Many new:
 
   $ testdesc '-ra1 -ra2' '-rb' '
   > +2:f +3:a1 +3:b
   > <f +30 :a2'
   
   % -- a -> b tree
   comparing with b
   searching for changes
   unpruned common: bebd167eb94d
   common heads: bebd167eb94d
   
   % -- a -> b set
   comparing with b
   query 1; heads
   searching for changes
   taking initial sample
   searching: 2 queries
   query 2; still undecided: 29, sample size is: 29
   2 total queries
   common heads: bebd167eb94d
   
   % -- b -> a tree
   comparing with a
   searching for changes
   unpruned common: bebd167eb94d 66f7d451a68b
   common heads: bebd167eb94d
   
   % -- b -> a set
   comparing with a
   query 1; heads
   searching for changes
   taking initial sample
   searching: 2 queries
   query 2; still undecided: 2, sample size is: 2
   2 total queries
   common heads: bebd167eb94d
 
 
 Both sides many new with stub:
 
   $ testdesc '-ra1 -ra2' '-rb' '
   > +2:f +2:a1 +30 :b
   > <f +30 :a2'
   
   % -- a -> b tree
   comparing with b
   searching for changes
   unpruned common: 2dc09a01254d
   common heads: 2dc09a01254d
   
   % -- a -> b set
   comparing with b
   query 1; heads
   searching for changes
   taking initial sample
   searching: 2 queries
   query 2; still undecided: 29, sample size is: 29
   2 total queries
   common heads: 2dc09a01254d
   
   % -- b -> a tree
   comparing with a
   searching for changes
   unpruned common: 66f7d451a68b 2dc09a01254d
   common heads: 2dc09a01254d
   
   % -- b -> a set
   comparing with a
   query 1; heads
   searching for changes
   taking initial sample
   searching: 2 queries
   query 2; still undecided: 29, sample size is: 29
   2 total queries
   common heads: 2dc09a01254d
 
 
 Both many new:
 
   $ testdesc '-ra' '-rb' '
   > +2:f +30 :b
   > <f +30 :a'
   
   % -- a -> b tree
   comparing with b
   searching for changes
   unpruned common: 66f7d451a68b
   common heads: 66f7d451a68b
   
   % -- a -> b set
   comparing with b
   query 1; heads
   searching for changes
   taking quick initial sample
   searching: 2 queries
   query 2; still undecided: 31, sample size is: 31
   2 total queries
   common heads: 66f7d451a68b
   
   % -- b -> a tree
   comparing with a
   searching for changes
   unpruned common: 66f7d451a68b
   common heads: 66f7d451a68b
   
   % -- b -> a set
   comparing with a
   query 1; heads
   searching for changes
   taking quick initial sample
   searching: 2 queries
   query 2; still undecided: 31, sample size is: 31
   2 total queries
   common heads: 66f7d451a68b
 
 
 Both many new skewed:
 
   $ testdesc '-ra' '-rb' '
   > +2:f +30 :b
   > <f +50 :a'
   
   % -- a -> b tree
   comparing with b
   searching for changes
   unpruned common: 66f7d451a68b
   common heads: 66f7d451a68b
   
   % -- a -> b set
   comparing with b
   query 1; heads
   searching for changes
   taking quick initial sample
   searching: 2 queries
   query 2; still undecided: 51, sample size is: 51
   2 total queries
   common heads: 66f7d451a68b
   
   % -- b -> a tree
   comparing with a
   searching for changes
   unpruned common: 66f7d451a68b
   common heads: 66f7d451a68b
   
   % -- b -> a set
   comparing with a
   query 1; heads
   searching for changes
   taking quick initial sample
   searching: 2 queries
   query 2; still undecided: 31, sample size is: 31
   2 total queries
   common heads: 66f7d451a68b
 
 
 Both many new on top of long history:
 
   $ testdesc '-ra' '-rb' '
   > +1000:f +30 :b
   > <f +50 :a'
   
   % -- a -> b tree
   comparing with b
   searching for changes
   unpruned common: 7ead0cba2838
   common heads: 7ead0cba2838
   
   % -- a -> b set
   comparing with b
   query 1; heads
   searching for changes
   taking quick initial sample
   searching: 2 queries
   query 2; still undecided: 1049, sample size is: 11
   sampling from both directions
   searching: 3 queries
   query 3; still undecided: 31, sample size is: 31
   3 total queries
   common heads: 7ead0cba2838
   
   % -- b -> a tree
   comparing with a
   searching for changes
   unpruned common: 7ead0cba2838
   common heads: 7ead0cba2838
   
   % -- b -> a set
   comparing with a
   query 1; heads
   searching for changes
   taking quick initial sample
   searching: 2 queries
   query 2; still undecided: 1029, sample size is: 11
   sampling from both directions
   searching: 3 queries
-  query 3; still undecided: 16, sample size is: 16
+  query 3; still undecided: 15, sample size is: 15
   3 total queries
   common heads: 7ead0cba2838