strip: calculate list of extra nodes to save and pass it to changegroupsubset

When we remove revision N from the repository, all revisions >= N are
affected: either it's a descendant from N and will also be removed, or
it's not a descendant of N and will be renumbered.

As a consequence, we have to (at least temporarily) remove all filelog
and manifest revisions that have a linkrev >= N, readding some of them
later.

Unfortunately, it's possible to have a revlog with two revisions
r1 and r2 such that r1 < r2, but linkrev(r1) > linkrev(r2).  If we try
to strip revision linkrev(r1) from the repository, we'll also lose
revision r2 when we truncate this revlog.

We already use changegroupsubset to create a temporary changegroup
containing the revisions that have to be restored, but that function is
unable to detect that we also wanted to save the r2 in the case above.

So we manually calculate these extra nodes and pass it to changegroupsubset.

This should fix issue764.

tests/test-strip-cross

@@ -0,0 +1,61 b''
+#!/bin/sh
+
+# test stripping of filelogs where the linkrev doesn't always increase
+
+echo '[extensions]' >> $HGRCPATH
+echo 'hgext.mq =' >> $HGRCPATH
+
+hg init orig
+cd orig
+
+hidefilename()
+{
+    sed -e 's/saving bundle to .*strip-backup/saving bundle to strip-backup/'
+}
+
+commit()
+{
+    hg up -qC null
+    count=1
+    for i in "$@"; do
+	for f in $i; do
+	    echo $count > $f
+	done
+	count=`expr $count + 1`
+    done
+    hg commit -qAm "$*"
+}
+
+# 2 1 0 2 0 1 2
+commit '201 210'
+
+commit '102 120' '210'
+
+commit '021'
+
+commit '201' '021 120'
+
+commit '012 021' '102 201' '120 210'
+
+commit '102 120' '012 210' '021 201'
+
+commit '201 210' '021 120' '012 102'
+
+cd ..
+hg clone -q -U -r -1 -r -2 -r -3 orig crossed
+
+for i in crossed/.hg/store/{00manifest.i,data/*.i}; do
+    echo $i
+    hg debugindex $i
+    echo
+done
+
+for i in 0 1 2; do
+    hg clone -q -U --pull crossed $i
+    echo "% Trying to strip revision $i"
+    hg --cwd $i strip $i 2>&1 | hidefilename
+    echo "% Verifying"
+    hg --cwd $i verify
+    echo
+done
+

tests/test-strip-cross.out

@@ -0,0 +1,87 b''
+crossed/.hg/store/00manifest.i
+   rev    offset  length   base linkrev nodeid       p1           p2
+     0         0     112      0       0 6f105cbb914d 000000000000 000000000000
+     1       112     123      0       1 8f3d04e263e5 000000000000 000000000000
+     2       235     122      0       2 f0ef8726ac4f 000000000000 000000000000
+
+crossed/.hg/store/data/012.i
+   rev    offset  length   base linkrev nodeid       p1           p2
+     0         0       3      0       0 b8e02f643373 000000000000 000000000000
+     1         3       3      1       1 5d9299349fc0 000000000000 000000000000
+     2         6       3      2       2 2661d26c6496 000000000000 000000000000
+
+crossed/.hg/store/data/021.i
+   rev    offset  length   base linkrev nodeid       p1           p2
+     0         0       3      0       0 b8e02f643373 000000000000 000000000000
+     1         3       3      1       2 5d9299349fc0 000000000000 000000000000
+     2         6       3      2       1 2661d26c6496 000000000000 000000000000
+
+crossed/.hg/store/data/102.i
+   rev    offset  length   base linkrev nodeid       p1           p2
+     0         0       3      0       1 b8e02f643373 000000000000 000000000000
+     1         3       3      1       0 5d9299349fc0 000000000000 000000000000
+     2         6       3      2       2 2661d26c6496 000000000000 000000000000
+
+crossed/.hg/store/data/120.i
+   rev    offset  length   base linkrev nodeid       p1           p2
+     0         0       3      0       1 b8e02f643373 000000000000 000000000000
+     1         3       3      1       2 5d9299349fc0 000000000000 000000000000
+     2         6       3      2       0 2661d26c6496 000000000000 000000000000
+
+crossed/.hg/store/data/201.i
+   rev    offset  length   base linkrev nodeid       p1           p2
+     0         0       3      0       2 b8e02f643373 000000000000 000000000000
+     1         3       3      1       0 5d9299349fc0 000000000000 000000000000
+     2         6       3      2       1 2661d26c6496 000000000000 000000000000
+
+crossed/.hg/store/data/210.i
+   rev    offset  length   base linkrev nodeid       p1           p2
+     0         0       3      0       2 b8e02f643373 000000000000 000000000000
+     1         3       3      1       1 5d9299349fc0 000000000000 000000000000
+     2         6       3      2       0 2661d26c6496 000000000000 000000000000
+
+% Trying to strip revision 0
+saving bundle to strip-backup/cbb8c2f0a2e3-backup
+saving bundle to strip-backup/cbb8c2f0a2e3-temp
+adding branch
+adding changesets
+adding manifests
+adding file changes
+added 2 changesets with 12 changes to 6 files (+1 heads)
+% Verifying
+checking changesets
+checking manifests
+crosschecking files in changesets and manifests
+checking files
+6 files, 2 changesets, 12 total revisions
+
+% Trying to strip revision 1
+saving bundle to strip-backup/124ecc0cbec9-backup
+saving bundle to strip-backup/124ecc0cbec9-temp
+adding branch
+adding changesets
+adding manifests
+adding file changes
+added 1 changesets with 10 changes to 6 files (+1 heads)
+% Verifying
+checking changesets
+checking manifests
+crosschecking files in changesets and manifests
+checking files
+6 files, 2 changesets, 12 total revisions
+
+% Trying to strip revision 2
+saving bundle to strip-backup/f6439b304a1a-backup
+saving bundle to strip-backup/f6439b304a1a-temp
+adding branch
+adding changesets
+adding manifests
+adding file changes
+added 0 changesets with 6 changes to 4 files
+% Verifying
+checking changesets
+checking manifests
+crosschecking files in changesets and manifests
+checking files
+6 files, 2 changesets, 12 total revisions
+

mercurial/repair.py

@@ -21,9 +21,9 b' def _limitheads(cl, stoprev):'
             seen[p] = 1
     return heads
 
-def _bundle(repo, bases, heads, node, suffix):
+def _bundle(repo, bases, heads, node, suffix, extranodes=None):
     """create a bundle with the specified revisions as a backup"""
-    cg = repo.changegroupsubset(bases, heads, 'strip')
+    cg = repo.changegroupsubset(bases, heads, 'strip', extranodes)
     backupdir = repo.join("strip-backup")
     if not os.path.isdir(backupdir):
         os.mkdir(backupdir)
@@ -44,6 +44,42 b' def _collectfilenodes(repo, striprev):'
 
     return filenodes
 
+def _collectextranodes(repo, files, link):
+    """return the nodes that have to be saved before the strip"""
+    def collectone(revlog):
+        extra = []
+        startrev = count = revlog.count()
+        # find the truncation point of the revlog
+        for i in xrange(0, count):
+            node = revlog.node(i)
+            lrev = revlog.linkrev(node)
+            if lrev >= link:
+                startrev = i + 1
+                break
+
+        # see if any revision after that point has a linkrev less than link
+        # (we have to manually save these guys)
+        for i in xrange(startrev, count):
+            node = revlog.node(i)
+            lrev = revlog.linkrev(node)
+            if lrev < link:
+                extra.append((node, cl.node(lrev)))
+
+        return extra
+
+    extranodes = {}
+    cl = repo.changelog
+    extra = collectone(repo.manifest)
+    if extra:
+        extranodes[1] = extra
+    for fname in files:
+        f = repo.file(fname)
+        extra = collectone(f)
+        if extra:
+            extranodes[fname] = extra
+
+    return extranodes
+
 def _stripall(repo, striprev, filenodes):
     """strip the requested nodes from the filelogs"""
     # we go in two steps here so the strip loop happens in a
@@ -102,23 +138,27 b' def strip(ui, repo, node, backup="all"):'
                 if cl.rev(x) > striprev:
                     savebases[x] = 1
 
+    filenodes = _collectfilenodes(repo, striprev)
+
+    extranodes = _collectextranodes(repo, filenodes, striprev)
+
     # create a changegroup for all the branches we need to keep
     if backup == "all":
         _bundle(repo, [node], cl.heads(), node, 'backup')
-    if saveheads:
-        chgrpfile = _bundle(repo, savebases.keys(), saveheads, node, 'temp')
+    if saveheads or extranodes:
+        chgrpfile = _bundle(repo, savebases.keys(), saveheads, node, 'temp',
+                            extranodes)
 
-    filenodes = _collectfilenodes(repo, striprev)
     _stripall(repo, striprev, filenodes)
 
     change = cl.read(node)
     cl.strip(striprev, striprev)
     repo.manifest.strip(repo.manifest.rev(change[0]), striprev)
-    if saveheads:
+    if saveheads or extranodes:
         ui.status("adding branch\n")
         f = open(chgrpfile, "rb")
         gen = changegroup.readbundle(f, chgrpfile)
-        repo.addchangegroup(gen, 'strip', 'bundle:' + chgrpfile)
+        repo.addchangegroup(gen, 'strip', 'bundle:' + chgrpfile, True)
         f.close()
         if backup != "strip":
             os.unlink(chgrpfile)

mercurial/revlog.py

@@ -1238,20 +1238,17 b' class revlog(object):'
         return node
 
     def strip(self, rev, minlink):
-        if self.count() == 0 or rev >= self.count():
+        if self.count() == 0:
             return
 
         if isinstance(self.index, lazyindex):
             self._loadindexmap()
 
-        # When stripping away a revision, we need to make sure it
-        # does not actually belong to an older changeset.
-        # The minlink parameter defines the oldest revision
-        # we're allowed to strip away.
-        while minlink > self.index[rev][4]:
-            rev += 1
-            if rev >= self.count():
-                return
+        for rev in xrange(0, self.count()):
+            if self.index[rev][4] >= minlink:
+                break
+        else:
+            return
 
         # first truncate the files on disk
         end = self.start(rev)