Patchwork [4,of,5,STABLE,v2] revset: use manual iteration in _diffset

login
register
mail settings
Submitter Gregory Szorc
Date Sept. 8, 2014, 9:59 p.m.
Message ID <b8226fb4800578b0d7b0.1410213586@gps-mbp.local>
Download mbox | patch
Permalink /patch/5731/
State Rejected
Headers show

Comments

Gregory Szorc - Sept. 8, 2014, 9:59 p.m.
# HG changeset patch
# User Gregory Szorc <gregory.szorc@gmail.com>
# Date 1410194924 25200
#      Mon Sep 08 09:48:44 2014 -0700
# Node ID b8226fb4800578b0d7b05f255f4c26140e458256
# Parent  b2a51ed00298036887b54108e3c7faa10a2d8417
revset: use manual iteration in _diffset

The previous implementation of _diffset always expanded the subtracting
set during evaluation. This was simpler but sacrificed performance. This
patch restores the lazy evaluation of the subtracting sets by performing
manual iteration, similar to how _addset works.

Patch

diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -2638,14 +2638,53 @@  class _diffset(_lazysetiteratormixin):
 
     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
+                if self._ascending is None:
+                    s = self._r2.set()
+                    for r in self._r1:
+                        if r not in s:
+                            yield r
+                else:
+                    iter1 = iter(self._r1)
+                    iter2 = iter(self._r2)
+
+                    val1 = None
+                    val2 = None
+                    ascending = self._ascending
+
+                    try:
+                        while True:
+                            if val1 is None:
+                                val1 = iter1.next()
+                            if val2 is None:
+                                val2 = iter2.next()
+
+                            # Item appearing in both sets is cancelled out.
+                            if val1 == val2:
+                                val1 = None
+                                val2 = None
+                                continue
+
+                            if ascending:
+                                if val1 < val2:
+                                    yield val1
+                                    val1 = None
+                                else:
+                                    val2 = None
+                            else:
+                                if val1 > val2:
+                                    yield val1
+                                    val1 = None
+                                else:
+                                    val2 = None
+                    except StopIteration:
+                        # Flush any remaining values from the original set.
+                        # Values from the subtracting set are irrelevant.
+                        if val1 is not None:
+                            yield val1
+                            for val in iter1:
+                                yield val
 
             self._iter = _generatorset(gen())
 
         return self._iter