[PATCH 3 of 5 STABLE v2] revset: more optimally handle __sub__ (issue4352)

[Gregory Szorc]

# HG changeset patch
# User Gregory Szorc <gregory.szorc at gmail.com>
# Date 1410195265 25200
#      Mon Sep 08 09:54:25 2014 -0700
# Node ID b2a51ed00298036887b54108e3c7faa10a2d8417
# Parent  3e8808bd267f9c2f6a650247a3a4ba926ee6c624
revset: more optimally handle __sub__ (issue4352)

This patch introduces the _diffset class. This class is used to more
optimally compute set differences (__sub__).

The initial implementation in this patch is not yet fully optimal.
If the set on the right hand side of the "-" operator is a lazy set,
it will be evaluated fully before results are returned. In the
future, this set should be iterated much like _addset does it.

The new class is not used anywhere yet. Upcoming patches will change
that.

diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -2625,8 +2625,32 @@ class _addset(_lazysetiteratormixin):
 
     def __contains__(self, x):
         return x in self._r1 or x in self._r2
 
+class _diffset(_lazysetiteratormixin):
+    """Represents the difference between two sets.
+
+    This class is similar to _addset. It exists to optimally compute the
+    difference between two sets. Its impact is most felt when operating
+    on two lazy sets.
+    """
+    def __contains__(self, x):
+        return x in self._list
+
+    def _iterator(self):
+        if self._iter is None:
+            def gen():
+                # We could further optimize this if r2 is ordered. See
+                # _addset._iterator for inspiration.
+                s = self._r2.set()
+                for r in self._r1:
+                    if r not in s:
+                        yield r
+
+            self._iter = _generatorset(gen())
+
+        return self._iter
+
 class _generatorset(object):
     """Wrap a generator for lazy iteration
 
     Wrapper structure for generators that provides lazy membership and can