| 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
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,