[PATCH 2 of 3] dagop: extract core algorithm of annotate() from context.py

[Yuya Nishihara]

# HG changeset patch
# User Yuya Nishihara <yuya at tcha.org>
# Date 1519849187 18000
#      Wed Feb 28 15:19:47 2018 -0500
# Node ID f634f309bed610e84b4ff151044f320461509e78
# Parent  6dc3fa2f85e1ab545cfcdf9bcba7aab6aacdd322
dagop: extract core algorithm of annotate() from context.py

See the previous patch for why.

diff --git a/mercurial/context.py b/mercurial/context.py
--- a/mercurial/context.py
+++ b/mercurial/context.py
@@ -32,7 +32,6 @@ from . import (
     error,
     fileset,
     match as matchmod,
-    mdiff,
     obsolete as obsmod,
     obsutil,
     patch,
@@ -976,22 +975,6 @@ class basefilectx(object):
         the line number at the first appearance in the managed file, otherwise,
         number has a fixed value of False.
         '''
-        annotateline = dagop.annotateline
-        _annotatepair = dagop._annotatepair
-
-        def lines(text):
-            if text.endswith("\n"):
-                return text.count("\n")
-            return text.count("\n") + int(bool(text))
-
-        if linenumber:
-            def decorate(text, rev):
-                return ([annotateline(fctx=rev, lineno=i)
-                         for i in xrange(1, lines(text) + 1)], text)
-        else:
-            def decorate(text, rev):
-                return ([annotateline(fctx=rev)] * lines(text), text)
-
         getlog = util.lrucachefunc(lambda x: self._repo.file(x))
 
         def parents(f):
@@ -1027,60 +1010,8 @@ class basefilectx(object):
                 ac = cl.ancestors([base.rev()], inclusive=True)
             base._ancestrycontext = ac
 
-        # This algorithm would prefer to be recursive, but Python is a
-        # bit recursion-hostile. Instead we do an iterative
-        # depth-first search.
-
-        # 1st DFS pre-calculates pcache and needed
-        visit = [base]
-        pcache = {}
-        needed = {base: 1}
-        while visit:
-            f = visit.pop()
-            if f in pcache:
-                continue
-            pl = parents(f)
-            pcache[f] = pl
-            for p in pl:
-                needed[p] = needed.get(p, 0) + 1
-                if p not in pcache:
-                    visit.append(p)
-
-        # 2nd DFS does the actual annotate
-        visit[:] = [base]
-        hist = {}
-        while visit:
-            f = visit[-1]
-            if f in hist:
-                visit.pop()
-                continue
-
-            ready = True
-            pl = pcache[f]
-            for p in pl:
-                if p not in hist:
-                    ready = False
-                    visit.append(p)
-            if ready:
-                visit.pop()
-                curr = decorate(f.data(), f)
-                skipchild = False
-                if skiprevs is not None:
-                    skipchild = f._changeid in skiprevs
-                curr = _annotatepair([hist[p] for p in pl], f, curr, skipchild,
-                                     diffopts)
-                for p in pl:
-                    if needed[p] == 1:
-                        del hist[p]
-                        del needed[p]
-                    else:
-                        needed[p] -= 1
-
-                hist[f] = curr
-                del pcache[f]
-
-        lineattrs, text = hist[base]
-        return pycompat.ziplist(lineattrs, mdiff.splitnewlines(text))
+        return dagop.annotate(base, parents, linenumber=linenumber,
+                              skiprevs=skiprevs, diffopts=diffopts)
 
     def ancestors(self, followfirst=False):
         visit = {}
diff --git a/mercurial/dagop.py b/mercurial/dagop.py
--- a/mercurial/dagop.py
+++ b/mercurial/dagop.py
@@ -17,6 +17,7 @@ from . import (
     mdiff,
     node,
     patch,
+    pycompat,
     smartset,
 )
 
@@ -429,6 +430,80 @@ def _annotatepair(parents, childfctx, ch
                         child[0][bk] = attr.evolve(parent[0][ak], skip=True)
     return child
 
+def annotate(base, parents, linenumber=False, skiprevs=None, diffopts=None):
+    """Core algorithm for filectx.annotate()
+
+    `parents(fctx)` is a function returning a list of parent filectxs.
+    """
+
+    def lines(text):
+        if text.endswith("\n"):
+            return text.count("\n")
+        return text.count("\n") + int(bool(text))
+
+    if linenumber:
+        def decorate(text, rev):
+            return ([annotateline(fctx=rev, lineno=i)
+                     for i in xrange(1, lines(text) + 1)], text)
+    else:
+        def decorate(text, rev):
+            return ([annotateline(fctx=rev)] * lines(text), text)
+
+    # This algorithm would prefer to be recursive, but Python is a
+    # bit recursion-hostile. Instead we do an iterative
+    # depth-first search.
+
+    # 1st DFS pre-calculates pcache and needed
+    visit = [base]
+    pcache = {}
+    needed = {base: 1}
+    while visit:
+        f = visit.pop()
+        if f in pcache:
+            continue
+        pl = parents(f)
+        pcache[f] = pl
+        for p in pl:
+            needed[p] = needed.get(p, 0) + 1
+            if p not in pcache:
+                visit.append(p)
+
+    # 2nd DFS does the actual annotate
+    visit[:] = [base]
+    hist = {}
+    while visit:
+        f = visit[-1]
+        if f in hist:
+            visit.pop()
+            continue
+
+        ready = True
+        pl = pcache[f]
+        for p in pl:
+            if p not in hist:
+                ready = False
+                visit.append(p)
+        if ready:
+            visit.pop()
+            curr = decorate(f.data(), f)
+            skipchild = False
+            if skiprevs is not None:
+                skipchild = f._changeid in skiprevs
+            curr = _annotatepair([hist[p] for p in pl], f, curr, skipchild,
+                                 diffopts)
+            for p in pl:
+                if needed[p] == 1:
+                    del hist[p]
+                    del needed[p]
+                else:
+                    needed[p] -= 1
+
+            hist[f] = curr
+            del pcache[f]
+
+    lineattrs, text = hist[base]
+    return pycompat.ziplist(lineattrs, mdiff.splitnewlines(text))
+
 def toposort(revs, parentsfunc, firstbranch=()):
     """Yield revisions from heads to roots one (topo) branch at a time.