diff --git a/mercurial/commands.py b/mercurial/commands.py
--- a/mercurial/commands.py
+++ b/mercurial/commands.py
@@ -2965,21 +2965,17 @@ def debugrebuilddirstate(ui, repo, rev, 
     wlock = repo.wlock()
     try:
         dirstate = repo.dirstate
-
+        changedfiles = None
         # See command doc for what minimal does.
         if opts.get('minimal'):
+            manifestfiles = set(ctx.manifest().keys())
             dirstatefiles = set(dirstate)
-            ctxfiles = set(ctx.manifest().keys())
-            for file in (dirstatefiles | ctxfiles):
-                indirstate = file in dirstatefiles
-                inctx = file in ctxfiles
-
-                if indirstate and not inctx and dirstate[file] != 'a':
-                    dirstate.drop(file)
-                elif inctx and not indirstate:
-                    dirstate.normallookup(file)
-        else:
-            dirstate.rebuild(ctx.node(), ctx.manifest())
+            manifestonly = manifestfiles - dirstatefiles
+            dsonly = dirstatefiles - manifestfiles
+            dsnotadded = set(f for f in dsonly if dirstate[f] != 'a')
+            changedfiles =  manifestonly | dsnotadded
+
+        dirstate.rebuild(ctx.node(), ctx.manifest(), changedfiles)
     finally:
         wlock.release()
 
diff --git a/mercurial/dirstate.py b/mercurial/dirstate.py
--- a/mercurial/dirstate.py
+++ b/mercurial/dirstate.py
@@ -639,17 +639,22 @@ class dirstate(object):
 
     def rebuild(self, parent, allfiles, changedfiles=None):
         if changedfiles is None:
+            # Rebuild entire dirstate
             changedfiles = allfiles
-        oldmap = self._map
-        self.clear()
-        for f in allfiles:
-            if f not in changedfiles:
-                self._map[f] = oldmap[f]
+            lastnormaltime = self._lastnormaltime
+            self.clear()
+            self._lastnormaltime = lastnormaltime
+
+        for f in changedfiles:
+            mode = 0o666
+            if f in allfiles and 'x' in allfiles.flags(f):
+                mode = 0o777
+
+            if f in allfiles:
+                self._map[f] = dirstatetuple('n', mode, -1, 0)
             else:
-                if 'x' in allfiles.flags(f):
-                    self._map[f] = dirstatetuple('n', 0o777, -1, 0)
-                else:
-                    self._map[f] = dirstatetuple('n', 0o666, -1, 0)
+                self._map.pop(f, None)
+
         self._pl = (parent, nullid)
         self._dirty = True
 
diff --git a/tests/test-rebuildstate.t b/tests/test-rebuildstate.t
--- a/tests/test-rebuildstate.t
+++ b/tests/test-rebuildstate.t
@@ -115,7 +115,7 @@ dirstate
   $ hg debugrebuilddirstate --minimal
   $ hg debugdirstate --nodates
   r   0          0 * bar (glob)
-  n   0         -1 * foo (glob)
+  n 644         -1 * foo (glob)
   a   0         -1 * qux (glob)
   $ hg status -A
   A qux