Patchwork [3,of,6] repoview: simplify process in _getstatichidden

login
register
mail settings
Submitter Pierre-Yves David
Date April 3, 2015, 10:23 p.m.
Message ID <52464cbacdf048fa115c.1428099828@marginatus.alto.octopoid.net>
Download mbox | patch
Permalink /patch/8488/
State Accepted
Commit f76595f6ed7c5147cbaf8ab823b5636d66476de3
Headers show

Comments

Pierre-Yves David - April 3, 2015, 10:23 p.m.
# HG changeset patch
# User Pierre-Yves David <pierre-yves.david@fb.com>
# Date 1428096953 25200
#      Fri Apr 03 14:35:53 2015 -0700
# Node ID 52464cbacdf048fa115caa7109baff6f2631211c
# Parent  ce977bd09297ff9320b60c3ed2ec45ba1103d147
repoview: simplify process in _getstatichidden

Since all children are processed before they parents we can apply the following algorithm:

For each revs (descending order):

* If I'm still hidden, no children will blocking me,
* If I'm not hidden, I must remove my parent from the hidden set,

This allow use to dynamically change the set of 'hidden' revision, dropping the
need for the 'actuallyhidden' dictionnary and 'blocked' boolean in the queue.

As before, we start iterating from all heads and stop at the first public
changesets. This ensure the hidden computation is 'O(not public())' instead of
'O(len(min(not public()):))'.
Durham Goode - April 3, 2015, 11:07 p.m.
On 4/3/15 3:23 PM, Pierre-Yves David wrote:
> # HG changeset patch
> # User Pierre-Yves David <pierre-yves.david@fb.com>
> # Date 1428096953 25200
> #      Fri Apr 03 14:35:53 2015 -0700
> # Node ID 52464cbacdf048fa115caa7109baff6f2631211c
> # Parent  ce977bd09297ff9320b60c3ed2ec45ba1103d147
> repoview: simplify process in _getstatichidden
>
> Since all children are processed before they parents we can apply the following algorithm:
>
> For each revs (descending order):
>
> * If I'm still hidden, no children will blocking me,
> * If I'm not hidden, I must remove my parent from the hidden set,
>
> This allow use to dynamically change the set of 'hidden' revision, dropping the
> need for the 'actuallyhidden' dictionnary and 'blocked' boolean in the queue.
>
> As before, we start iterating from all heads and stop at the first public
> changesets. This ensure the hidden computation is 'O(not public())' instead of
> 'O(len(min(not public()):))'.
>
> diff --git a/mercurial/repoview.py b/mercurial/repoview.py
> --- a/mercurial/repoview.py
> +++ b/mercurial/repoview.py
> @@ -30,39 +30,34 @@ def _getstatichidden(repo):
>       while keeping the graph consistent.
>   
>       A second pass will be done to apply "dynamic blocker" like bookmarks or
>       working directory parents."""
>       assert not repo.changelog.filteredrevs
> -    hideable = hideablerevs(repo)
> -    if hideable:
> -        actuallyhidden = {}
> +    hidden = set(hideablerevs(repo))
It doesn't matter right now, but we should start writing our algorithms 
such that they never require full knowledge of these kinds of sets 
(hidden, obsolete, etc).  For instance, in the future hideablerevs might 
become a lazily computed set (I have a patch that does it, but the perf 
impact is too low right now), and forcing it to become a set would 
defeat the purpose.  It's a mind set that will make these things more 
scalable later I think.

Patch

diff --git a/mercurial/repoview.py b/mercurial/repoview.py
--- a/mercurial/repoview.py
+++ b/mercurial/repoview.py
@@ -30,39 +30,34 @@  def _getstatichidden(repo):
     while keeping the graph consistent.
 
     A second pass will be done to apply "dynamic blocker" like bookmarks or
     working directory parents."""
     assert not repo.changelog.filteredrevs
-    hideable = hideablerevs(repo)
-    if hideable:
-        actuallyhidden = {}
+    hidden = set(hideablerevs(repo))
+    if hidden:
         getphase = repo._phasecache.phase
         getparentrevs = repo.changelog.parentrevs
-        heap = [(-r, False) for r in repo.changelog.headrevs()]
+        heap = [-r for r in repo.changelog.headrevs()]
         heapq.heapify(heap)
         heappop = heapq.heappop
         heappush = heapq.heappush
         while heap:
-            rev, blocked = heappop(heap)
-            rev = - rev
-            phase = getphase(repo, rev)
-            # Skip nodes which are public (guaranteed to not be hidden) and
-            # nodes which have already been processed and won't be blocked by
-            # the previous node.
-            if phase == 0 or (not blocked and rev in actuallyhidden):
+            rev = -heappop(heap)
+            # Skip nodes which are public (guaranteed to not be hidden)
+            if not getphase(repo, rev):
                 continue
-            if rev in hideable:
-                if blocked:
-                    actuallyhidden[rev] = False
-                else:
-                    actuallyhidden.setdefault(rev, True)
-            else:
-                blocked = True
-
-            for parent in (p for p in getparentrevs(rev) if p != nullrev):
-                heappush(heap, (- parent, blocked))
-    return set(rev for rev, hidden in actuallyhidden.iteritems() if hidden)
+            # All children have been processed so at that point, if no children
+            # removed 'rev' from the 'hidden' set, 'rev' is going to be hidden.
+            blocker = rev not in hidden
+            for parent in getparentrevs(rev):
+                if parent == nullrev:
+                    continue
+                if blocker:
+                    # If visible, ensure parent will be visible too
+                    hidden.discard(parent)
+                heappush(heap, -parent)
+    return hidden
 
 def _getdynamicblockers(repo):
     """Non-cacheable revisions blocking hidden changesets from being filtered.
 
     Get revisions that will block hidden changesets and are likely to change,