# HG changeset patch
# User Denis Laxalde <denis.laxalde@logilab.fr>
# Date 1482962617 -3600
# Node ID ce662ee40d2deb7620594133f0fed7b09a01c45d
# Parent  3eeb8e138e5ccef411da783013518fbcb31b3e55
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).

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 -r 3eeb8e138e5c -r ce662ee40d2d mercurial/context.py
--- a/mercurial/context.py	Tue Jan 03 18:15:58 2017 +0100
+++ b/mercurial/context.py	Wed Dec 28 23:03:37 2016 +0100
@@ -1153,6 +1153,42 @@
         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."""