This is an archive of the discontinued Mercurial Phabricator instance.

Differential D2577

mdiff: prefer xdiff for diff calculation
AbandonedPublic

Authored by quark on Mar 2 2018, 7:25 PM.

Details

Reviewers
ryanmce
Group Reviewers
hg-reviewers
Summary

Let's switch to xdiff for its better diff quality and faster performance!

bdiff is still used as a fallback for cases xdiff isn't built, or the pure
Python version.

Test Plan

Added the "patience" test case mentioned in previous commit. It fails
with a huge diff output before this change.

I expected some annotate/diff output changes due to diff blocks being
shifted around. Let's see what sandcastle says. I'll make adjustments
accordingly.

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

ryanmce created this revision.Mar 2 2018, 7:25 PM
durin42 added a subscriber: durin42.Mar 3 2018, 10:10 AM
durin42 added inline comments.
mercurial/mdiff.py
34

Rather than this, let's try to get the xdiffblocks function (and if it's not there set it to none), and then we could rework the below code to use xdiffblocks instead of blocks if experimental.xdiff is set to true - that'll make it easier to do some testing of both codepaths.

quark added a subscriber: quark.Mar 3 2018, 12:35 PM
quark added inline comments.
mercurial/mdiff.py
34

The diff functions below do not have an ui object. Would you be okay if the config is global? ex. something like

# mdiff.py
def setdiffalgo(name):
    global blocks
    if name == 'xdiff':
        blocks = ...
    else: ...
# dispatch.py
    ui = ....
    mdiff.setdiffalgo(...)
ryanmce added inline comments.Mar 3 2018, 2:14 PM
mercurial/mdiff.py
34

I chatted with people here at the sprint. I'm going to see if we can pass in the diff algo in from calling functions, falling back to bdiff if none is specified.

indygreg added a subscriber: indygreg.Mar 3 2018, 2:19 PM
indygreg added inline comments.
mercurial/mdiff.py
34

global state is evil. Especially on functionality that calls out to C and may release the GIL. If we have multi-threaded applications, things could get in a very bad state.

I'd encourage you to plumb in the diff algorithm to use into the diffopts. Even if the diff algorithm is only visible for user-visible diffs (as opposed to say storage diffs), that's a win.

quark added a reviewer: ryanmce.Mar 3 2018, 3:10 PM
quark commandeered this revision.

Took the diffopts approach - note: merge conflicts improvements are gone since mdiff.get_matching_blocks is not covered.

quark abandoned this revision.Mar 3 2018, 3:10 PM

Revision Contents
Changeset List

PathPackages
Mmercurial/mdiff.py (11 lines)
Mtests/hghave.py (8 lines)
AMtests/test-diff-antipatience.t (41 lines)

Diff 6420

mercurial/mdiff.py

util, util,
) )
_missing_newline_marker = "\\ No newline at end of file\n" _missing_newline_marker = "\\ No newline at end of file\n"
bdiff = policy.importmod(r'bdiff') bdiff = policy.importmod(r'bdiff')
mpatch = policy.importmod(r'mpatch') mpatch = policy.importmod(r'mpatch')
blocks = bdiff.blocks
fixws = bdiff.fixws fixws = bdiff.fixws
patches = mpatch.patches patches = mpatch.patches
patchedsize = mpatch.patchedsize patchedsize = mpatch.patchedsize
textdiff = bdiff.bdiff textdiff = bdiff.bdiff
splitnewlines = bdiff.splitnewlines splitnewlines = bdiff.splitnewlines
try:
durin42Unsubmitted
Not Done

Rather than this, let's try to get the xdiffblocks function (and if it's not there set it to none), and then we could rework the below code to use xdiffblocks instead of blocks if experimental.xdiff is set to true - that'll make it easier to do some testing of both codepaths.

durin42: Rather than this, let's try to get the xdiffblocks function (and if it's not there set it to…
quarkAuthorUnsubmitted
Not Done

The diff functions below do not have an ui object. Would you be okay if the config is global? ex. something like

# mdiff.py
def setdiffalgo(name):
    global blocks
    if name == 'xdiff':
        blocks = ...
    else: ...
# dispatch.py
    ui = ....
    mdiff.setdiffalgo(...)
quark: The diff functions below do not have an `ui` object. Would you be okay if the config is global?
ryanmceUnsubmitted
Not Done

I chatted with people here at the sprint. I'm going to see if we can pass in the diff algo in from calling functions, falling back to bdiff if none is specified.

ryanmce: I chatted with people here at the sprint. I'm going to see if we can pass in the diff algo in…
indygregUnsubmitted
Not Done

global state is evil. Especially on functionality that calls out to C and may release the GIL. If we have multi-threaded applications, things could get in a very bad state.

I'd encourage you to plumb in the diff algorithm to use into the diffopts. Even if the diff algorithm is only visible for user-visible diffs (as opposed to say storage diffs), that's a win.

indygreg: global state is evil. Especially on functionality that calls out to C and may release the GIL.
from .cext import xdiff
blocks = xdiff.blocks
except ImportError:
blocks = bdiff.blocks
class diffopts(object): class diffopts(object):
'''context is the number of context lines '''context is the number of context lines
text treats all files as text text treats all files as text
showfunc enables diff -p output showfunc enables diff -p output
git enables the git extended patch format git enables the git extended patch format
nodates removes dates from diff headers nodates removes dates from diff headers
nobinary ignores binary files nobinary ignores binary files
noprefix disables the 'a/' and 'b/' prefixes (ignored in plain mode) noprefix disables the 'a/' and 'b/' prefixes (ignored in plain mode)
line1 and line2 are text1 and text2 split with splitnewlines() if line1 and line2 are text1 and text2 split with splitnewlines() if
they are already available. they are already available.
""" """
if opts is None: if opts is None:
opts = defaultopts opts = defaultopts
if opts.ignorews or opts.ignorewsamount or opts.ignorewseol: if opts.ignorews or opts.ignorewsamount or opts.ignorewseol:
text1 = wsclean(opts, text1, False) text1 = wsclean(opts, text1, False)
text2 = wsclean(opts, text2, False) text2 = wsclean(opts, text2, False)
diff = bdiff.blocks(text1, text2) diff = blocks(text1, text2)
for i, s1 in enumerate(diff): for i, s1 in enumerate(diff):
# The first match is special. # The first match is special.
# we've either found a match starting at line 0 or a match later # we've either found a match starting at line 0 or a match later
# in the file. If it starts later, old and new below will both be # in the file. If it starts later, old and new below will both be
# empty and we'll continue to the next match. # empty and we'll continue to the next match.
if i > 0: if i > 0:
s = diff[i - 1] s = diff[i - 1]
else: else:
def patch(a, bin): def patch(a, bin):
if len(a) == 0: if len(a) == 0:
# skip over trivial delta header # skip over trivial delta header
return util.buffer(bin, 12) return util.buffer(bin, 12)
return mpatch.patches(a, [bin]) return mpatch.patches(a, [bin])
# similar to difflib.SequenceMatcher.get_matching_blocks # similar to difflib.SequenceMatcher.get_matching_blocks
def get_matching_blocks(a, b): def get_matching_blocks(a, b):
return [(d[0], d[2], d[1] - d[0]) for d in bdiff.blocks(a, b)] return [(d[0], d[2], d[1] - d[0]) for d in blocks(a, b)]
def trivialdiffheader(length): def trivialdiffheader(length):
return struct.pack(">lll", 0, 0, length) if length else '' return struct.pack(">lll", 0, 0, length) if length else ''
def replacediffheader(oldlen, newlen): def replacediffheader(oldlen, newlen):
return struct.pack(">lll", 0, oldlen, newlen) return struct.pack(">lll", 0, oldlen, newlen)

tests/hghave.py

@check("clang-libfuzzer", "clang new enough to include libfuzzer") @check("clang-libfuzzer", "clang new enough to include libfuzzer")
def has_clang_libfuzzer(): def has_clang_libfuzzer():
mat = matchoutput('clang --version', 'clang version (\d)') mat = matchoutput('clang --version', 'clang version (\d)')
if mat: if mat:
# libfuzzer is new in clang 6 # libfuzzer is new in clang 6
return int(mat.group(1)) > 5 return int(mat.group(1)) > 5
return False return False
@check("xdiff", "xdiff algorithm")
def has_xdiff():
try:
from mercurial.cext import xdiff
return xdiff.blocks('', '') == [(0, 0, 0, 0)]
except ImportError:
return False

tests/test-diff-antipatience.t

  • This file was added.
#require xdiff
Test case that makes use of the weakness of patience diff algorithm
$ hg init
>>> open('a', 'w').write('\n'.join(list('a' + 'x' * 300 + 'u' + 'x' * 700 + 'a\n')))
$ hg commit -m 1 -A a
>>> open('a', 'w').write('\n'.join(list('b' + 'x' * 700 + 'u' + 'x' * 300 + 'b\n')))
$ hg diff
diff -r 6c45a8fe8cb6 a
--- a/a Thu Jan 01 00:00:00 1970 +0000
+++ b/a Thu Jan 01 00:00:00 1970 +0000
@@ -1,4 +1,4 @@
-a
+b
x
x
x
@@ -299,7 +299,6 @@
x
x
x
-u
x
x
x
@@ -700,6 +699,7 @@
x
x
x
+u
x
x
x
@@ -1000,5 +1000,5 @@
x
x
x
-a
+b