Jun Wu <quark@fb.com> [Sat, 03 Mar 2018 12:38:41 -0800] rev 36702
xdiff: add a bdiff hunk mode
xdiff generated hunks for the differences (ex. questionmarks in the
`@@ -?,? +?,? @@` part from `diff --git` output). However, bdiff generates
matched hunks instead.
This patch adds a `XDL_EMIT_BDIFFHUNK` flag used by the output function
`xdl_call_hunk_func`. Once set, xdiff will generate bdiff-like hunks
instead. That makes it easier to use xdiff as a drop-in replacement of bdiff.
Note that since `bdiff('', '')` returns `[(0, 0, 0, 0)]`, the shortcut path
`if (xscr)` is removed. I have checked functions called with `xscr` argument
(`xdl_mark_ignorable`, `xdl_call_hunk_func`, `xdl_emit_diff`,
`xdl_free_script`) work just fine with `xscr = NULL`.
Test Plan:
Will be tested in a later patch.
Differential Revision: https://phab.mercurial-scm.org/D2575
Jun Wu <quark@fb.com> [Sat, 03 Mar 2018 10:39:55 -0800] rev 36701
xdiff: remove patience and histogram diff algorithms
Patience diff is the normal diff algorithm, plus some greediness that
unconditionally matches common common unique lines. That means it is easy to
construct cases to let it generate suboptimal result, like:
```
open('a', 'w').write('\n'.join(list('a' + 'x' * 300 + 'u' + 'x' * 700 + 'a\n')))
open('b', 'w').write('\n'.join(list('b' + 'x' * 700 + 'u' + 'x' * 300 + 'b\n')))
```
Patience diff has been advertised as being able to generate better results for
some C code changes. However, the more scientific way to do that is the
indention heuristic [1].
Since patience diff could generate suboptimal result more easily and its
"better" diff feature could be replaced by the new indention heuristic, let's
just remove it and its variant histogram diff to simplify the code.
[1]: https://github.com/git/git/commit/433860f3d0beb0c6f205290bd16cda413148f098
Test Plan:
`gcc -fPIC *.c --shared -o xdiff.so` still builds.
Differential Revision: https://phab.mercurial-scm.org/D2573
Jun Wu <quark@fb.com> [Sat, 03 Mar 2018 10:39:43 -0800] rev 36700
xdiff: vendor xdiff library from git
Vendor git's xdiff library from git commit
d7c6c2369d7c6c2369ac21141b7c6cceaebc6414ec3da14ad using GPL2+ license.
There is another recent user report that hg diff generates suboptimal
result. It seems the fix to issue4074 isn't good enough. I crafted some
other interesting cases, and hg diff barely has any advantage compared with
gnu diffutils or git diff.
| testcase | gnu diffutils | hg diff | git diff |
| | lines time | lines time | lines time |
| patience | 6 0.00 | 602 0.08 | 6 0.00 |
| random | 91772 0.90 | 109462 0.70 | 91772 0.24 |
| json | 2 0.03 | 1264814 1.81 | 2 0.29 |
"lines" means the size of the output, i.e. the count of "+/-" lines. "time"
means seconds needed to do the calculation. Both are the smaller the better.
"hg diff" counts Python startup overhead.
Git and GNU diffutils generate optimal results. For the "json" case, git can
have an optimization that does a scan for common prefix and suffix first,
and match them if the length is greater than half of the text. See
https://neil.fraser.name/news/2006/03/12/. That would make git the fastest
for all above cases.
About testcases:
patience:
Aiming for the weakness of the greedy "patience diff" algorithm. Using
git's patience diff option would also get suboptimal result. Generated using
the Python script:
```
open('a', 'w').write('\n'.join(list('a' + 'x' * 300 + 'u' + 'x' * 700 + 'a\n')))
open('b', 'w').write('\n'.join(list('b' + 'x' * 700 + 'u' + 'x' * 300 + 'b\n')))
```
random:
Generated using the script in `test-issue4074.t`. It practically makes the
algorithm suffer. Impressively, git wins in both performance and diff
quality.
json:
The recent user reported case. It's a single line movement near the end of a
very large (800K lines) JSON file.
Test Plan:
Code taken as-is.
Differential Revision: https://phab.mercurial-scm.org/D2572
# no-check-commit for vendored code
Ryan McElroy <rmcelroy@fb.com> [Sat, 03 Mar 2018 14:30:21 -0800] rev 36699
templater: provide hint for multi-line templates with parse errors
Previously, we punted. Now we "rewrite" the template's newlines to r'\n' and
offset the hint appropriately.
Differential Revision: https://phab.mercurial-scm.org/D2609
Ryan McElroy <rmcelroy@fb.com> [Sat, 03 Mar 2018 14:23:40 -0800] rev 36698
templater: add hint to template parse errors to help locate issues
Previously, we would print the error name and location, but this isn't as
helpful as we can be. Let's add a hint that shows the location where we
encountered the parse error.
Differential Revision: https://phab.mercurial-scm.org/D2608
Pulkit Goyal <7895pulkit@gmail.com> [Fri, 02 Mar 2018 07:17:06 +0530] rev 36697
py3: use b"%d" to covert integer to bytes instead of str
Differential Revision: https://phab.mercurial-scm.org/D2618