view hgext/pager.py @ 36671:34e2ff1f9cd8

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

# pager.py - display output using a pager
#
# Copyright 2008 David Soria Parra <[e-mail]>
#
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version.
#
# To load the extension, add it to your configuration file:
#
#   [extension]
#   pager =
#
# Run 'hg help pager' to get info on configuration.

'''browse command output with an external pager (DEPRECATED)

Forcibly enable paging for individual commands that don't typically
request pagination with the attend-<command> option. This setting
takes precedence over ignore options and defaults::

  [pager]
  attend-cat = false
'''
from __future__ import absolute_import

from mercurial import (
    cmdutil,
    commands,
    dispatch,
    extensions,
    registrar,
    )

# Note for extension authors: ONLY specify testedwith = 'ships-with-hg-core' for
# extensions which SHIP WITH MERCURIAL. Non-mainline extensions should
# be specifying the version(s) of Mercurial they are tested with, or
# leave the attribute unspecified.
testedwith = 'ships-with-hg-core'

configtable = {}
configitem = registrar.configitem(configtable)

configitem('pager', 'attend',
        default=lambda: attended,
)

def uisetup(ui):

    def pagecmd(orig, ui, options, cmd, cmdfunc):
        auto = options['pager'] == 'auto'
        if auto and not ui.pageractive:
            usepager = False
            attend = ui.configlist('pager', 'attend')
            ignore = ui.configlist('pager', 'ignore')
            cmds, _ = cmdutil.findcmd(cmd, commands.table)

            for cmd in cmds:
                var = 'attend-%s' % cmd
                if ui.config('pager', var, None):
                    usepager = ui.configbool('pager', var, True)
                    break
                if (cmd in attend or
                     (cmd not in ignore and not attend)):
                    usepager = True
                    break

            if usepager:
                # Slight hack: the attend list is supposed to override
                # the ignore list for the pager extension, but the
                # core code doesn't know about attend, so we have to
                # lobotomize the ignore list so that the extension's
                # behavior is preserved.
                ui.setconfig('pager', 'ignore', '', 'pager')
                ui.pager('extension-via-attend-' + cmd)
            else:
                ui.disablepager()
        return orig(ui, options, cmd, cmdfunc)

    extensions.wrapfunction(dispatch, '_runcommand', pagecmd)

attended = ['annotate', 'cat', 'diff', 'export', 'glog', 'log', 'qdiff']