diff --git a/mercurial/changelog.py b/mercurial/changelog.py
--- a/mercurial/changelog.py
+++ b/mercurial/changelog.py
@@ -80,21 +80,25 @@ def encodeextra(d):
     ]
     return "\0".join(items)
 
-def encodecopies(copies):
-    items = [
-        '%s\0%s' % (k, copies[k])
-        for k in sorted(copies)
-    ]
+def encodecopies(files, copies):
+    items = []
+    for i, dst in enumerate(files):
+        if dst in copies:
+            items.append('%d\0%s' % (i, copies[dst]))
+    if len(items) != len(copies):
+        raise error.ProgrammingError('some copy targets missing from file list')
     return "\n".join(items)
 
-def decodecopies(data):
+def decodecopies(files, data):
     try:
         copies = {}
         for l in data.split('\n'):
-            k, v = l.split('\0')
-            copies[k] = v
+            strindex, src = l.split('\0')
+            i = int(strindex)
+            dst = files[i]
+            copies[dst] = src
         return copies
-    except ValueError:
+    except (ValueError, IndexError):
         # Perhaps someone had chosen the same key name (e.g. "p1copies") and
         # used different syntax for the value.
         return None
@@ -336,12 +340,12 @@ class changelogrevision(object):
     @property
     def p1copies(self):
         rawcopies = self.extra.get('p1copies')
-        return rawcopies and decodecopies(rawcopies)
+        return rawcopies and decodecopies(self.files, rawcopies)
 
     @property
     def p2copies(self):
         rawcopies = self.extra.get('p2copies')
-        return rawcopies and decodecopies(rawcopies)
+        return rawcopies and decodecopies(self.files, rawcopies)
 
     @property
     def description(self):
@@ -631,11 +635,11 @@ class changelog(revlog.revlog):
         extrasentries = p1copies, p2copies, filesadded, filesremoved
         if extra is None and any(x is not None for x in extrasentries):
             extra = {}
+        sortedfiles = sorted(files)
         if p1copies is not None:
-            extra['p1copies'] = encodecopies(p1copies)
+            extra['p1copies'] = encodecopies(sortedfiles, p1copies)
         if p2copies is not None:
-            extra['p2copies'] = encodecopies(p2copies)
-        sortedfiles = sorted(files)
+            extra['p2copies'] = encodecopies(sortedfiles, p2copies)
         if filesadded is not None:
             extra['filesadded'] = encodefileindices(sortedfiles, filesadded)
         if filesremoved is not None:
diff --git a/tests/test-copies-in-changeset.t b/tests/test-copies-in-changeset.t
--- a/tests/test-copies-in-changeset.t
+++ b/tests/test-copies-in-changeset.t
@@ -27,9 +27,9 @@ Check that copies are recorded correctly
   files: b c d
   filesadded: 0\x001\x002 (esc)
   
-  p1copies: b\x00a (esc)
-  c\x00a (esc)
-  d\x00a (esc)
+  p1copies: 0\x00a (esc)
+  1\x00a (esc)
+  2\x00a (esc)
   $ hg showcopies
   a -> b
   a -> c
@@ -49,7 +49,7 @@ Check that renames are recorded correctl
   filesadded: 1
   filesremoved: 0
   
-  p1copies: b2\x00b (esc)
+  p1copies: 1\x00b (esc)
   $ hg showcopies
   b -> b2
 
@@ -67,7 +67,7 @@ even though there is no filelog entry.
   $ hg changesetcopies
   files: c
   
-  p1copies: c\x00b2 (esc)
+  p1copies: 0\x00b2 (esc)
   $ hg showcopies
   b2 -> c
   $ hg debugindex c
@@ -97,9 +97,9 @@ File 'f' exists only in p1, so 'i' shoul
   files: g h i
   filesadded: 0\x001\x002 (esc)
   
-  p1copies: g\x00a (esc)
-  i\x00f (esc)
-  p2copies: h\x00d (esc)
+  p1copies: 0\x00a (esc)
+  2\x00f (esc)
+  p2copies: 1\x00d (esc)
   $ hg showcopies
   a -> g
   d -> h
@@ -114,7 +114,7 @@ Test writing to both changeset and filel
   filesadded: 0
   filesremoved: 
   
-  p1copies: j\x00a (esc)
+  p1copies: 0\x00a (esc)
   p2copies: 
   $ hg debugdata j 0
   \x01 (esc)
@@ -173,9 +173,9 @@ Test rebasing a commit with copy informa
   $ hg mv a b
   $ hg ci -qm 'rename a to b'
   $ hg rebase -d 1 --config rebase.experimental.inmemory=yes
-  rebasing 2:acfc33f3aa6d "rename a to b" (tip)
+  rebasing 2:fc7287ac5b9b "rename a to b" (tip)
   merging a and b to b
-  saved backup bundle to $TESTTMP/rebase-rename/.hg/strip-backup/acfc33f3aa6d-81d0180d-rebase.hg
+  saved backup bundle to $TESTTMP/rebase-rename/.hg/strip-backup/fc7287ac5b9b-8f2a95ec-rebase.hg
   $ hg st --change . --copies
   A b
     a
diff --git a/tests/test-copies.t b/tests/test-copies.t
--- a/tests/test-copies.t
+++ b/tests/test-copies.t
@@ -559,7 +559,7 @@ Grafting revision 4 on top of revision 2
   @  5 added d, modified b
   |  b1
   ~  diff -r 5a4825cc2926 -r 94a2f1a0e8e2 b1 (no-changeset !)
-  ~  diff -r df722b7fe2d5 -r ba3ddbbdfd96 b1 (changeset !)
+  ~  diff -r 0a0ed3b3251c -r d544fb655520 b1 (changeset !)
      --- a/b1	Thu Jan 01 00:00:00 1970 +0000
      +++ b/b1	Thu Jan 01 00:00:00 1970 +0000
      @@ -1,1 +1,2 @@