[PATCH 2 of 3 V4] context: add a `blockancestors(fctx, fromline, toline)` function

[Denis Laxalde]

# HG changeset patch
# User Denis Laxalde <denis.laxalde at logilab.fr>
# Date 1482962617 -3600
#      Wed Dec 28 23:03:37 2016 +0100
# Node ID ae66a9ae337e267ecb47f8e2610c308fd81743b7
# Parent  7f94fa66ee380f223e4790129ff3bd03884b4a26
# EXP-Topic linerange-log/revset
context: add a `blockancestors(fctx, fromline, toline)` function

This yields ancestors of `fctx` by only keeping changesets touching the file
within specified linerange = (fromline, toline).

The algorithm is currently limited to following only the first parent in case
of merge (might be improved later).

Matching revisions are found by inspecting the result of `mdiff.allblocks()`,
filtered by `mdiff.blocksinrange()`, to find out if there are blocks of type
"!" within specified line range.

If, at some iteration, an ancestor with an empty line range is encountered,
the algorithm stops as it means that the considered block of lines actually
has been introduced in the revision of this iteration. Otherwise, we finally
yield the initial revision of the file as the block originates from it.

When a merge changeset is encountered during ancestors lookup, we consider
there's a diff in the current line range as long as there is a diff between
the merge changeset and at least one of its parents (in the current line
range).

diff --git a/mercurial/context.py b/mercurial/context.py
--- a/mercurial/context.py
+++ b/mercurial/context.py
@@ -1153,6 +1153,42 @@ class filectx(basefilectx):
         return [filectx(self._repo, self._path, fileid=x,
                         filelog=self._filelog) for x in c]
 
+def blockancestors(fctx, fromline, toline):
+    """Yield ancestors of `fctx` with respect to the block of lines within
+    `fromline`-`toline` range.
+    """
+    def changesrange(fctx1, fctx2, linerange2):
+        """Return `(diffinrange, linerange1)` where `diffinrange` is True
+        if diff from fctx2 to fctx1 has changes in linerange2 and
+        `linerange1` is the new line range for fctx1.
+        """
+        diffopts = patch.diffopts(fctx._repo.ui)
+        blocks = mdiff.allblocks(fctx1.data(), fctx2.data(), diffopts)
+        filteredblocks, linerange1 = mdiff.blocksinrange(blocks, linerange2)
+        diffinrange = any(stype == '!' for _, stype in filteredblocks)
+        return diffinrange, linerange1
+
+    visit = {(fctx.linkrev(), fctx.filenode()): (fctx, (fromline, toline))}
+    while visit:
+        c, linerange2 = visit.pop(max(visit))
+        pl = c.parents()
+        if not pl:
+            # The block originates from the initial revision.
+            yield c
+            continue
+        inrange = False
+        for p in pl:
+            inrangep, linerange1 = changesrange(p, c, linerange2)
+            inrange = inrange or inrangep
+            if linerange1[0] == linerange1[1]:
+                # Parent's linerange is empty, meaning that the block got
+                # introduced in this revision; no need to go futher in this
+                # branch.
+                continue
+            visit[p.linkrev(), p.filenode()] = p, linerange1
+        if inrange:
+            yield c
+
 class committablectx(basectx):
     """A committablectx object provides common functionality for a context that
     wants the ability to commit, e.g. workingctx or memctx."""