D7076: copies: compute the exact set of revision to walk

[marmoute (Pierre-Yves David)]

marmoute created this revision.
Herald added a subscriber: mercurial-devel.
Herald added a reviewer: hg-reviewers.

REVISION SUMMARY
  This change make the code clearer by removing the revision queue. It comes
  without very noticeable performance impact. However the simpler code will be
  easier to update in later changesets.
  
  revision: large amount; added files: large amount; rename small amount; c3b14617fbd7 9ba6ab77fd29
  before: ! wall 2.132175 comb 2.140000 user 2.120000 sys 0.020000 (median of 5)
  after:  ! wall 2.088245 comb 2.080000 user 2.070000 sys 0.010000 (median of 5)
  revision: large amount; added files: small amount; rename small amount; c3b14617fbd7 f650a9b140d2
  before: ! wall 2.802585 comb 2.810000 user 2.780000 sys 0.030000 (median of 5)
  after:  ! wall 2.781835 comb 2.770000 user 2.730000 sys 0.040000 (median of 5)
  revision: large amount; added files: large amount; rename large amount; 08ea3258278e d9fa043f30c0
  before: ! wall 0.306071 comb 0.300000 user 0.290000 sys 0.010000 (median of 33)
  after:  ! wall 0.299616 comb 0.290000 user 0.290000 sys 0.000000 (median of 33)
  revision: small amount; added files: large amount; rename large amount; df6f7a526b60 a83dc6a2d56f
  before: ! wall 0.017486 comb 0.010000 user 0.010000 sys 0.000000 (median of 169)
  after:  ! wall 0.018396 comb 0.020000 user 0.020000 sys 0.000000 (median of 161)
  revision: small amount; added files: large amount; rename small amount; 4aa4e1f8e19a 169138063d63
  before: ! wall 0.001981 comb 0.000000 user 0.000000 sys 0.000000 (median of 1000)
  after:  ! wall 0.002172 comb 0.000000 user 0.000000 sys 0.000000 (median of 1000)
  revision: small amount; added files: small amount; rename small amount; 4bc173b045a6 964879152e2e
  before: ! wall 0.000090 comb 0.000000 user 0.000000 sys 0.000000 (median of 10009)
  after:  ! wall 0.000143 comb 0.000000 user 0.000000 sys 0.000000 (median of 6188)
  revision: medium amount; added files: large amount; rename medium amount; c95f1ced15f2 2c68e87c3efe
  before: ! wall 0.254525 comb 0.250000 user 0.250000 sys 0.000000 (median of 39)
  after:  ! wall 0.258774 comb 0.258974 user 0.252564 sys 0.006410 (avg of 39)
  revision: medium amount; added files: medium amount; rename small amount; d343da0c55a8 d7746d32bf9d
  before: ! wall 0.039678 comb 0.040000 user 0.040000 sys 0.000000 (median of 100)
  after:  ! wall 0.038630 comb 0.040000 user 0.040000 sys 0.000000 (median of 100)

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D7076

AFFECTED FILES
  mercurial/copies.py
  tests/test-copies.t

CHANGE DETAILS

diff --git a/tests/test-copies.t b/tests/test-copies.t
--- a/tests/test-copies.t
+++ b/tests/test-copies.t
@@ -236,7 +236,7 @@
   $ hg debugpathcopies 1 2
   y -> x
   $ hg debugpathcopies 1 3
-  $ hg debugpathcopies 2 3
+  $ FOO=1 hg debugpathcopies 2 3
   x -> y
 
 Copy file from either side in a merge
diff --git a/mercurial/copies.py b/mercurial/copies.py
--- a/mercurial/copies.py
+++ b/mercurial/copies.py
@@ -306,7 +306,6 @@
 def _changesetforwardcopies(a, b, match):
     if a.rev() in (node.nullrev, b.rev()):
         return {}
-
     repo = a.repo()
     children = {}
     revinfo = _revinfogetter(repo)
@@ -314,6 +313,8 @@
 
     cl = repo.changelog
     missingrevs = cl.findmissingrevs(common=[a.rev()], heads=[b.rev()])
+    mrset = set(missingrevs)
+    roots = set()
     for r in missingrevs:
         for p in parents(r):
             if p == node.nullrev:
@@ -322,17 +323,23 @@
                 children[p] = [r]
             else:
                 children[p].append(r)
+            if p not in mrset:
+                roots.add(p)
+    if not roots:
+        # no common revision to track copies from
+        return {}
+    min_root = min(roots)
 
-    roots = set(children) - set(missingrevs)
-    work = [r for r in roots]
+    from_head = set(cl.reachableroots(min_root, [b.rev()], list(roots), includepath=True))
+
+    iterrevs = set(from_head)
+    iterrevs &= mrset
+    iterrevs.update(roots)
+    iterrevs.remove(b.rev())
     all_copies = dict((r, {}) for r in roots)
-    heapq.heapify(work)
     alwaysmatch = match.always()
-    while work:
-        r = heapq.heappop(work)
+    for r in sorted(iterrevs):
         copies = all_copies.pop(r)
-        if r == b.rev():
-            return copies
         for i, c in enumerate(children[r]):
             p1, p2, p1copies, p2copies, removed = revinfo(c)
             if r == p1:
@@ -358,7 +365,6 @@
                     del newcopies[f]
             othercopies = all_copies.get(c)
             if othercopies is None:
-                heapq.heappush(work, c)
                 all_copies[c] = newcopies
             else:
                 # we are the second parent to work on c, we need to merge our
@@ -378,7 +384,7 @@
                 else:
                     newcopies.update(othercopies)
                     all_copies[c] = newcopies
-    assert False
+    return all_copies[b.rev()]
 
 
 def _forwardcopies(a, b, base=None, match=None):



To: marmoute, #hg-reviewers
Cc: mercurial-devel