revset: optimize missing ancestor expressions

A missing ancestor expression is any expression of the form (::x - ::y) or
equivalent. Such expressions are remarkably common, and so far have involved
multiple walks down the DAG, followed by a set difference operation.

With this patch, such expressions will be transformed into uses of the fast
algorithm at ancestor.missingancestor.

For a repository with over 600,000 revisions, perfrevset for '::tip - ::-10000'
returns:

Before: ! wall 3.999575 comb 4.000000 user 3.910000 sys 0.090000 (best of 3)
After:  ! wall 0.132423 comb 0.130000 user 0.130000 sys 0.000000 (best of 75)

mercurial/revset.py

@@ -1749,7 +1749,24 b' def optimize(x, small):'
     elif op == 'and':
         wa, ta = optimize(x[1], True)
         wb, tb = optimize(x[2], True)
+
+        # (::x and not ::y)/(not ::y and ::x) have a fast path
+        def ismissingancestors(revs, bases):
+            return (
+                revs[0] == 'func'
+                and getstring(revs[1], _('not a symbol')) == 'ancestors'
+                and bases[0] == 'not'
+                and bases[1][0] == 'func'
+                and getstring(bases[1][1], _('not a symbol')) == 'ancestors')
+
         w = min(wa, wb)
+        if ismissingancestors(ta, tb):
+            return w, ('func', ('symbol', '_missingancestors'),
+                       ('list', ta[2], tb[1][2]))
+        if ismissingancestors(tb, ta):
+            return w, ('func', ('symbol', '_missingancestors'),
+                       ('list', tb[2], ta[1][2]))
+
         if wa > wb:
             return w, (op, tb, ta)
         return w, (op, ta, tb)

tests/test-revset.t

@@ -444,6 +444,70 b' ancestor can accept 0 or more arguments'
   $ log 'tag(tip)'
   9
 
+check that conversion to _missingancestors works
+  $ try --optimize '::3 - ::1'
+  (minus
+    (dagrangepre
+      ('symbol', '3'))
+    (dagrangepre
+      ('symbol', '1')))
+  * optimized:
+  (func
+    ('symbol', '_missingancestors')
+    (list
+      ('symbol', '3')
+      ('symbol', '1')))
+  3
+  $ try --optimize 'ancestors(1) - ancestors(3)'
+  (minus
+    (func
+      ('symbol', 'ancestors')
+      ('symbol', '1'))
+    (func
+      ('symbol', 'ancestors')
+      ('symbol', '3')))
+  * optimized:
+  (func
+    ('symbol', '_missingancestors')
+    (list
+      ('symbol', '1')
+      ('symbol', '3')))
+  $ try --optimize 'not ::2 and ::6'
+  (and
+    (not
+      (dagrangepre
+        ('symbol', '2')))
+    (dagrangepre
+      ('symbol', '6')))
+  * optimized:
+  (func
+    ('symbol', '_missingancestors')
+    (list
+      ('symbol', '6')
+      ('symbol', '2')))
+  3
+  4
+  5
+  6
+  $ try --optimize 'ancestors(6) and not ancestors(4)'
+  (and
+    (func
+      ('symbol', 'ancestors')
+      ('symbol', '6'))
+    (not
+      (func
+        ('symbol', 'ancestors')
+        ('symbol', '4'))))
+  * optimized:
+  (func
+    ('symbol', '_missingancestors')
+    (list
+      ('symbol', '6')
+      ('symbol', '4')))
+  3
+  5
+  6
+
 we can use patterns when searching for tags
 
   $ log 'tag("1..*")'