Patchwork [1,of,4,V3,part,2] revlog: move ancestor generation out to a new class

login
register
mail settings
Submitter Siddharth Agarwal
Date Dec. 18, 2012, 5:30 a.m.
Message ID <492535c0a3b45125888c.1355808610@sid0x220>
Download mbox | patch
Permalink /patch/182/
State Accepted
Commit 9abc55ef85b58ce784ccb009aed7dfc395914239
Headers show

Comments

Siddharth Agarwal - Dec. 18, 2012, 5:30 a.m.
# HG changeset patch
# User Siddharth Agarwal <sid0 at fb.com>
# Date 1355805744 28800
# Node ID 492535c0a3b45125888c7d20d402857cecaeae00
# Parent  aca213182e8fffe65fecff0af0b373f4c0a3cdfc
revlog: move ancestor generation out to a new class

This refactoring is to prepare for implementing lazy membership.
Pierre-Yves David - Dec. 18, 2012, 10:30 a.m.
On Mon, Dec 17, 2012 at 09:30:10PM -0800, Siddharth Agarwal wrote:
> # HG changeset patch
> # User Siddharth Agarwal <sid0 at fb.com>
> # Date 1355805744 28800
> # Node ID 492535c0a3b45125888c7d20d402857cecaeae00
> # Parent  aca213182e8fffe65fecff0af0b373f4c0a3cdfc
> revlog: move ancestor generation out to a new class
> 
> This refactoring is to prepare for implementing lazy membership.
> 
> diff -r aca213182e8f -r 492535c0a3b4 mercurial/ancestor.py
> --- a/mercurial/ancestor.py	Mon Dec 17 15:08:37 2012 -0800
> +++ b/mercurial/ancestor.py	Mon Dec 17 20:42:24 2012 -0800
> @@ -5,7 +5,7 @@
>  # This software may be used and distributed according to the terms of the
>  # GNU General Public License version 2 or any later version.
>  
> -import error, heapq
> +import error, heapq, util
>  from node import nullrev
>  
>  def ancestors(pfunc, *orignodes):
> @@ -316,3 +316,53 @@
>  
>      missing.reverse()
>      return missing
> +
> +class lazyancestors(object):
> +    def __init__(self, cl, revs, stoprev=0, inclusive=False):
> +        """Create a new object generating ancestors for the given revs. Does
> +        not generate revs lower than stoprev.
> +
> +        This is computed lazily starting from revs. The object only supports
> +        iteration.
> +
> +        cl should be a changelog and revs should be an iterable. inclusive is
> +        a boolean that indicates whether revs should be included. Revs lower
> +        than stoprev will not be generated.
> +
> +        Result does not include the null revision."""
> +        self._parentrevs = cl.parentrevs
> +        self._initrevs = revs
> +        self._stoprev = stoprev
> +        self._inclusive = inclusive
> +
> +    def __iter__(self):
> +        """Generate the ancestors of _initrevs in reverse topological order.
> +
> +        If inclusive is False, yield a sequence of revision numbers starting
> +        with the parents of each revision in revs, i.e., each revision is *not*
> +        considered an ancestor of itself.  Results are in breadth-first order:
> +        parents of each rev in revs, then parents of those, etc.
> +
> +        If inclusive is True, yield all the revs first (ignoring stoprev),

I think we should honor stoprev here. That seems more sensible.

> +        then yield all the ancestors of revs as when inclusive is False.
> +        If an element in revs is an ancestor of a different rev it is not
> +        yielded again."""
> +        seen = set([nullrev])

We do not need to add nullrev here as stoprev is at least 0

> +        if self._inclusive:
> +            for rev in revs:

UnboundLocalError: local variable 'revs' referenced before assignment

Looks like you swapped those line with the ones bellow and never ran this code.

> +                yield rev
> +            seen.update(revs)
> +
> +        parentrevs = self._parentrevs
> +        revs = self._initrevs
> +        stoprev = self._stoprev
> +        visit = util.deque(revs)
> +
> +        while visit:
> +            for parent in parentrevs(visit.popleft()):
> +                if parent < stoprev:
> +                    continue
> +                if parent not in seen:
> +                    visit.append(parent)
> +                    seen.add(parent)
> +                    yield parent

what about a single branch ?

if parent >= stoprev and parent not in seen:


> diff -r aca213182e8f -r 492535c0a3b4 mercurial/revlog.py
> --- a/mercurial/revlog.py	Mon Dec 17 15:08:37 2012 -0800
> +++ b/mercurial/revlog.py	Mon Dec 17 20:42:24 2012 -0800
> @@ -345,31 +345,10 @@
>          """Generate the ancestors of 'revs' in reverse topological order.
>          Does not generate revs lower than stoprev.
>  
> -        If inclusive is False, yield a sequence of revision numbers starting
> -        with the parents of each revision in revs, i.e., each revision is *not*
> -        considered an ancestor of itself.  Results are in breadth-first order:
> -        parents of each rev in revs, then parents of those, etc.
> +        See the documentation for ancestor.lazyancestors for more details."""
>  
> -        If inclusive is True, yield all the revs first (ignoring stoprev),
> -        then yield all the ancestors of revs as when inclusive is False.
> -        If an element in revs is an ancestor of a different rev it is not
> -        yielded again.
> -
> -        Result does not include the null revision."""
> -        visit = util.deque(revs)
> -        seen = set([nullrev])
> -        if inclusive:
> -            for rev in revs:
> -                yield rev
> -            seen.update(revs)
> -        while visit:
> -            for parent in self.parentrevs(visit.popleft()):
> -                if parent < stoprev:
> -                    continue
> -                if parent not in seen:
> -                    visit.append(parent)
> -                    seen.add(parent)
> -                    yield parent
> +        return ancestor.lazyancestors(self, revs, stoprev=stoprev,
> +                                      inclusive=inclusive)
>  
>      def descendants(self, revs):
>          """Generate the descendants of 'revs' in revision order.
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel at selenic.com
> http://selenic.com/mailman/listinfo/mercurial-devel
Siddharth Agarwal - Dec. 18, 2012, 6:23 p.m.
On 12/18/2012 02:30 AM, Pierre-Yves David wrote:
> I think we should honor stoprev here. That seems more sensible.

I would be far more comfortable doing this in a separate patch series.

I've addressed the rest of your comments; thanks.
Kevin Bullock - Dec. 18, 2012, 7:22 p.m.
On Dec 18, 2012, at 12:23 PM, Siddharth Agarwal wrote:

> On 12/18/2012 02:30 AM, Pierre-Yves David wrote:
>> I think we should honor stoprev here. That seems more sensible.
> 
> I would be far more comfortable doing this in a separate patch series.

Agreed. If we try to address it here then the review has to include checking caller's expectations... pretty significant scope creep.

pacem in terris / ??? / ?????? / ????????? / ??
Kevin R. Bullock

Patch

diff -r aca213182e8f -r 492535c0a3b4 mercurial/ancestor.py
--- a/mercurial/ancestor.py	Mon Dec 17 15:08:37 2012 -0800
+++ b/mercurial/ancestor.py	Mon Dec 17 20:42:24 2012 -0800
@@ -5,7 +5,7 @@ 
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
-import error, heapq
+import error, heapq, util
 from node import nullrev
 
 def ancestors(pfunc, *orignodes):
@@ -316,3 +316,53 @@ 
 
     missing.reverse()
     return missing
+
+class lazyancestors(object):
+    def __init__(self, cl, revs, stoprev=0, inclusive=False):
+        """Create a new object generating ancestors for the given revs. Does
+        not generate revs lower than stoprev.
+
+        This is computed lazily starting from revs. The object only supports
+        iteration.
+
+        cl should be a changelog and revs should be an iterable. inclusive is
+        a boolean that indicates whether revs should be included. Revs lower
+        than stoprev will not be generated.
+
+        Result does not include the null revision."""
+        self._parentrevs = cl.parentrevs
+        self._initrevs = revs
+        self._stoprev = stoprev
+        self._inclusive = inclusive
+
+    def __iter__(self):
+        """Generate the ancestors of _initrevs in reverse topological order.
+
+        If inclusive is False, yield a sequence of revision numbers starting
+        with the parents of each revision in revs, i.e., each revision is *not*
+        considered an ancestor of itself.  Results are in breadth-first order:
+        parents of each rev in revs, then parents of those, etc.
+
+        If inclusive is True, yield all the revs first (ignoring stoprev),
+        then yield all the ancestors of revs as when inclusive is False.
+        If an element in revs is an ancestor of a different rev it is not
+        yielded again."""
+        seen = set([nullrev])
+        if self._inclusive:
+            for rev in revs:
+                yield rev
+            seen.update(revs)
+
+        parentrevs = self._parentrevs
+        revs = self._initrevs
+        stoprev = self._stoprev
+        visit = util.deque(revs)
+
+        while visit:
+            for parent in parentrevs(visit.popleft()):
+                if parent < stoprev:
+                    continue
+                if parent not in seen:
+                    visit.append(parent)
+                    seen.add(parent)
+                    yield parent
diff -r aca213182e8f -r 492535c0a3b4 mercurial/revlog.py
--- a/mercurial/revlog.py	Mon Dec 17 15:08:37 2012 -0800
+++ b/mercurial/revlog.py	Mon Dec 17 20:42:24 2012 -0800
@@ -345,31 +345,10 @@ 
         """Generate the ancestors of 'revs' in reverse topological order.
         Does not generate revs lower than stoprev.
 
-        If inclusive is False, yield a sequence of revision numbers starting
-        with the parents of each revision in revs, i.e., each revision is *not*
-        considered an ancestor of itself.  Results are in breadth-first order:
-        parents of each rev in revs, then parents of those, etc.
+        See the documentation for ancestor.lazyancestors for more details."""
 
-        If inclusive is True, yield all the revs first (ignoring stoprev),
-        then yield all the ancestors of revs as when inclusive is False.
-        If an element in revs is an ancestor of a different rev it is not
-        yielded again.
-
-        Result does not include the null revision."""
-        visit = util.deque(revs)
-        seen = set([nullrev])
-        if inclusive:
-            for rev in revs:
-                yield rev
-            seen.update(revs)
-        while visit:
-            for parent in self.parentrevs(visit.popleft()):
-                if parent < stoprev:
-                    continue
-                if parent not in seen:
-                    visit.append(parent)
-                    seen.add(parent)
-                    yield parent
+        return ancestor.lazyancestors(self, revs, stoprev=stoprev,
+                                      inclusive=inclusive)
 
     def descendants(self, revs):
         """Generate the descendants of 'revs' in revision order.