# HG changeset patch
# User Durham Goode <durham@fb.com>
# Date 2014-03-31 23:03:34
# Node ID f52e4ca93529d876f36631583645b8fa34b5a8d2
# Parent  04e1596d5dbdc7cb14f16c1ed60c22d599cf24de

revset: improve roots revset performance

Previously we would iterate over every item in the subset, checking if it was in
the provided args. This often meant iterating over every rev in the repo.

Now we iterate over the args provided, checking if they exist in the subset.
On a large repo this brings setting phase boundaries (which use this revset
roots(X:: - X::Y)) down from 0.8 seconds to 0.4 seconds.

The "roots((tip~100::) - (tip~100::tip))" revset in revsetbenchmarks shows it
going from 0.12s to 0.10s, so we should be able to catch regressions here in the
future.

This actually introduces a regression in 'roots(all())' (0.2s to 0.26s) since
we're now using spansets, which are slightly slower to do containment checks on.
I believe this trade off is worth it, since it makes the revset O(number of
args) instead of O(size of repo).

diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -1480,8 +1480,8 @@ def roots(repo, subset, x):
     """``roots(set)``
     Changesets in set with no parent changeset in set.
     """
-    s = getset(repo, baseset(repo.changelog), x).set()
-    subset = baseset([r for r in subset if r in s])
+    s = getset(repo, spanset(repo), x).set()
+    subset = baseset([r for r in s if r in subset.set()])
     cs = _children(repo, subset, s)
     return subset - cs