[PATCH 2 of 3 gca-revset V3] revset: add optimization for heads(commonancestors())

[Sean Farley]

# HG changeset patch
# User Sean Farley <sean at farley.io>
# Date 1530051981 25200
#      Tue Jun 26 15:26:21 2018 -0700
# Branch gca-revset
# Node ID 31ada9bee6360235a9fb027b867b50fba721ebb7
# Parent  20b61392326c251c5898ab34a610829113e3da0b
revset: add optimization for heads(commonancestors())

Previously, the only way to get these commits were (tested on
mozilla-central):

hg perfrevset 'heads(::a7cf55 and ::d8b15)'
! wall 4.988366 comb 4.960000 user 4.780000 sys 0.180000 (best of 3)

After this patch:

(python)
hg perfrevset 'heads(commonancestors(a7cf55 + d8b15))'
! wall 0.002155 comb 0.000000 user 0.000000 sys 0.000000 (best of 1107)

(C)
hg perfrevset 'heads(commonancestors(a7cf55 + d8b15))'
! wall 0.000568 comb 0.000000 user 0.000000 sys 0.000000 (best of 4646)

diff --git a/mercurial/revset.py b/mercurial/revset.py
index 9b9d274..0630845 100644
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -359,10 +359,23 @@ def ancestors(repo, subset, x):
             raise error.ParseError(_("negative depth"))
         stopdepth = n + 1
     return _ancestors(repo, subset, args['set'],
                       startdepth=startdepth, stopdepth=stopdepth)
 
+# for internal use
+ at predicate('_commonancestorheads(set)', safe=True)
+def _commonancestorheads(repo, subset, x):
+    # This is an internal method is for quickly calculating "heads(::x and
+    # ::y)"
+
+    # These greatest common ancestors are the same ones that the consesus bid
+    # merge will find.
+    h = heads(repo, fullreposet(repo), x, defineorder)
+
+    ancs = repo.changelog._commonancestorsheads(*list(h))
+    return subset & baseset(ancs)
+
 @predicate('commonancestors(set)', safe=True)
 def commonancestors(repo, subset, x):
     """Returns all common ancestors of the set.
 
     This method is for calculating "::x and ::y" (i.e. all the ancestors that
diff --git a/mercurial/revsetlang.py b/mercurial/revsetlang.py
index 6331709..e559563 100644
--- a/mercurial/revsetlang.py
+++ b/mercurial/revsetlang.py
@@ -457,10 +457,16 @@ def _optimize(x):
         return w, (op, x[1], t)
     elif op == 'func':
         f = getsymbol(x[1])
         wa, ta = _optimize(x[2])
         w = getattr(symbols.get(f), '_weight', 1)
+        m = _match('commonancestors(_)', ta)
+
+        # Optimize heads(commonancestors(_)) because we have a fast version
+        if f == 'heads' and m:
+            return w + wa, _build('_commonancestorheads(_)', m[1])
+
         return w + wa, (op, x[1], ta)
     raise ValueError('invalid operator %r' % op)
 
 def optimize(tree):
     """Optimize evaluatable tree
diff --git a/tests/test-merge-criss-cross.t b/tests/test-merge-criss-cross.t
index 4901da2..c86f25d 100644
--- a/tests/test-merge-criss-cross.t
+++ b/tests/test-merge-criss-cross.t
@@ -408,10 +408,25 @@ Verify how the output looks and and how 
   getting d1/f3 to d2/f3
    d2/f4: local directory rename, both created -> m (premerge)
   3 files updated, 0 files merged, 0 files removed, 0 files unresolved
   (branch merge, don't forget to commit)
 
+Test the greatest common ancestor returning multiple changesets
+
+  $ hg log -r 'heads(commonancestors(head()))'
+  changeset:   1:0f6b37dbe527
+  user:        test
+  date:        Thu Jan 01 00:00:00 1970 +0000
+  summary:     1 first change f1
+  
+  changeset:   2:d1d156401c1b
+  parent:      0:40494bf2444c
+  user:        test
+  date:        Thu Jan 01 00:00:00 1970 +0000
+  summary:     2 first change f2
+  
+
   $ cd ..
 
 http://stackoverflow.com/questions/9350005/how-do-i-specify-a-merge-base-to-use-in-a-hg-merge/9430810
 
   $ hg init ancestor-merging
diff --git a/tests/test-revset2.t b/tests/test-revset2.t
index cfd0e08..d1db5d5 100644
--- a/tests/test-revset2.t
+++ b/tests/test-revset2.t
@@ -1832,5 +1832,23 @@ Test `draft() & ::x` optimization
           (symbol '_list')
           (string 'S1\x00D2\x00P5'))
         (keyvalue
           (symbol 'depth')
           (symbol '1')))))
+
+test commonancestors and its optimization
+
+  $ hg debugrevspec --verify -p analyzed -p optimized 'heads(commonancestors(head()))'
+  * analyzed:
+  (func
+    (symbol 'heads')
+    (func
+      (symbol 'commonancestors')
+      (func
+        (symbol 'head')
+        None)))
+  * optimized:
+  (func
+    (symbol '_commonancestorheads')
+    (func
+      (symbol 'head')
+      None))