diff --git a/mercurial/manifest.py b/mercurial/manifest.py
--- a/mercurial/manifest.py
+++ b/mercurial/manifest.py
@@ -35,6 +35,9 @@ from .utils import (
 parsers = policy.importmod(r'parsers')
 propertycache = util.propertycache
 
+# Allow tests to more easily test the alternate path in manifestdict.fastdelta()
+FASTDELTA_TEXTDIFF_THRESHOLD = 1000
+
 def _parse(data):
     # This method does a little bit of excessive-looking
     # precondition checking. This is so that the behavior of this
@@ -558,7 +561,7 @@ class manifestdict(object):
         addbuf = util.buffer(base)
 
         changes = list(changes)
-        if len(changes) < 1000:
+        if len(changes) < FASTDELTA_TEXTDIFF_THRESHOLD:
             # start with a readonly loop that finds the offset of
             # each line and creates the deltas
             for f, todelete in changes:
diff --git a/tests/test-manifest.t b/tests/test-manifest.t
--- a/tests/test-manifest.t
+++ b/tests/test-manifest.t
@@ -201,3 +201,94 @@ hg update should warm the cache too
   total cache data size 425 bytes, on-disk 425 bytes
   $ hg log -r '0' --debug | grep 'manifest:'
   manifest:    0:fce2a30dedad1eef4da95ca1dc0004157aa527cf
+
+Test file removal (especially with pure).  The tests are crafted such that there
+will be contiguous spans of existing entries to ensure that is handled properly.
+(In this case, a.txt, aa.txt and c.txt, cc.txt, and ccc.txt)
+
+  $ cat > $TESTTMP/manifest.py <<EOF
+  > from mercurial import (
+  >     extensions,
+  >     manifest,
+  > )
+  > def extsetup(ui):
+  >     manifest.FASTDELTA_TEXTDIFF_THRESHOLD = 0
+  > EOF
+  $ cat >> $HGRCPATH <<EOF
+  > [extensions]
+  > manifest = $TESTTMP/manifest.py
+  > EOF
+
+BROKEN: Pure removes should actually remove all dropped entries
+
+  $ hg init repo
+  $ cd repo
+  $ echo a > a.txt
+  $ echo aa > aa.txt
+  $ echo b > b.txt
+  $ echo c > c.txt
+  $ echo c > cc.txt
+  $ echo c > ccc.txt
+  $ echo b > d.txt
+  $ echo c > e.txt
+  $ hg ci -Aqm 'a-e'
+
+  $ hg rm b.txt d.txt
+  $ hg ci -m 'remove b and d'
+
+  $ hg debugdata -m 1
+  a.txt\x00b789fdd96dc2f3bd229c1dd8eedf0fc60e2b68e3 (esc)
+  aa.txt\x00a4bdc161c8fbb523c9a60409603f8710ff49a571 (esc)
+  \x00.txt\x001e88685f5ddec574a34c70af492f95b6debc8741 (esc) (pure !)
+  c.txt\x00149da44f2a4e14f488b7bd4157945a9837408c00 (esc)
+  cc.txt\x00149da44f2a4e14f488b7bd4157945a9837408c00 (esc)
+  ccc.txt\x00149da44f2a4e14f488b7bd4157945a9837408c00 (esc)
+  \x00.txt\x001e88685f5ddec574a34c70af492f95b6debc8741 (esc) (pure !)
+  e.txt\x00149da44f2a4e14f488b7bd4157945a9837408c00 (esc)
+
+  $ hg up -C . 2>&1 | grep ValueError || true
+      raise ValueError("Manifest lines not in sorted order.") (pure !)
+  ValueError: Manifest lines not in sorted order. (pure !)
+
+  $ hg verify || true
+  checking changesets
+  checking manifests
+   manifest@1: reading delta c1f6b2f803ac: Non-hexadecimal digit found (pure !)
+  crosschecking files in changesets and manifests
+  checking files
+  checked 2 changesets with 8 changes to 8 files
+  1 integrity errors encountered! (pure !)
+  (first damaged changeset appears to be 1) (pure !)
+
+  $ hg rollback -q --config ui.rollback=True
+  $ hg rm b.txt d.txt
+  $ echo bb > bb.txt
+
+BROKEN: A mix of adds and removes should remove all dropped entries.
+
+  $ hg ci -Aqm 'remove b and d; add bb'
+
+  $ hg debugdata -m 1
+  a.txt\x00b789fdd96dc2f3bd229c1dd8eedf0fc60e2b68e3 (esc)
+  aa.txt\x00a4bdc161c8fbb523c9a60409603f8710ff49a571 (esc)
+  bb.txt\x0004c6faf8a9fdd848a5304dfc1704749a374dff44 (esc)
+  c.txt\x00149da44f2a4e14f488b7bd4157945a9837408c00 (esc)
+  cc.txt\x00149da44f2a4e14f488b7bd4157945a9837408c00 (esc)
+  ccc.txt\x00149da44f2a4e14f488b7bd4157945a9837408c00 (esc)
+  \x00.txt\x001e88685f5ddec574a34c70af492f95b6debc8741 (esc) (pure !)
+  e.txt\x00149da44f2a4e14f488b7bd4157945a9837408c00 (esc)
+
+  $ hg up -C . 2>&1 | grep ValueError || true
+      raise ValueError("Manifest lines not in sorted order.") (pure !)
+  ValueError: Manifest lines not in sorted order. (pure !)
+
+  $ hg verify || true
+  checking changesets
+  checking manifests
+   manifest@1: reading delta 0a0385480090: Manifest lines not in sorted order. (pure !)
+  crosschecking files in changesets and manifests
+   bb.txt@1: in changeset but not in manifest (pure !)
+  checking files
+  checked 2 changesets with 9 changes to 9 files
+  2 integrity errors encountered! (pure !)
+  (first damaged changeset appears to be 1) (pure !)