[PATCH] revset: make parents() O(number of parents)

[Durham Goode]

# HG changeset patch
# User Durham Goode <durham at fb.com>
# Date 1410559251 25200
#      Fri Sep 12 15:00:51 2014 -0700
# Node ID 73e9a122290c3428b0c71353c566e7ab7c50ebbb
# Parent  f40b873cf6aa1a7b0f401c3df8090e6fb8000698
revset: make parents() O(number of parents)

Strip executes a revset like this:

max(parents(_intlist('1234\x001235')) - _intlist('1234\x001235'))

Previously the parents() revset would do 'subset & parents' which iterates over
each item in the subset and checks if it's in parents.  subset is usually the
entire repo (a spanset) so this takes a while.

Reversing the parameters to be 'parents & subset' means the operation becomes
O(number of parents) instead of O(size of repo). It also means the result gets
evaluated immediately (since parents isn't a lazy set), but I think this is a
win in most scenarios.

This shaves 0.3 seconds off strip (amend/histedit/rebase/etc) for large repositories.

revset #0: parents(20000)
0) obsolete feature not enabled but 54243 markers found!
! wall 0.006256 comb 0.010000 user 0.010000 sys 0.000000 (best of 289)
1) obsolete feature not enabled but 54243 markers found!
! wall 0.000391 comb 0.000000 user 0.000000 sys 0.000000 (best of 4323)

diff --git a/contrib/revsetbenchmarks.txt b/contrib/revsetbenchmarks.txt
--- a/contrib/revsetbenchmarks.txt
+++ b/contrib/revsetbenchmarks.txt
@@ -24,3 +24,4 @@
 roots((0:tip)::)
 (not public() - obsolete())
 (_intlist('20000\x0020001')) and merge()
+parents(20000)
diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -1238,7 +1238,7 @@
     cl = repo.changelog
     for r in getset(repo, spanset(repo), x):
         ps.update(cl.parentrevs(r))
-    return subset & ps
+    return baseset(ps) & subset
 
 def parentspec(repo, subset, x, n):
     """``set^0``