combine-diff: coalesce lost lines optimally

This replaces the greedy implementation to coalesce lost lines by using
dynamic programming to find the Longest Common Subsequence.

The O(n²) time complexity is obviously bigger than previous
implementation but it can produce shorter diff results (and most likely
easier to read).

List of lost lines is now doubly-linked because we reverse-read it when
reading the direction matrix.

Signed-off-by: Antoine Pelisse <apelisse@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
rerere forget: grok files containing NUL

Using 'git rerere forget .' after a merge that involved binary files
runs into an infinite loop if the binary file contains a zero byte.
Replace a strchrnul by memchr because the former does not make progress
as soon as the NUL is encountered.

Signed-off-by: Johannes Sixt <j6t@kdbg.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
builtin/help.c: split "-a" processing into two

"help -a" (help all) gives the list of available commands and then
further gives hints on the use of "git help".   Separate these into
two steps, because we will add "help -g" (help guides) that want to
also show the overall hints after it is done.

While at it, change the definition of the "-a" option to use OPT_BOOL,
not the deprecated OPT_BOOLEAN.  We do not behave differently when
the user gives the "-a" option multiple times, e.g. "git help -a -a".

Signed-off-by: Philip Oakley <philipoakley@iee.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
builtin/help.c: add --guide option

Logic, but no actions, included.

The --all commands option, if given, will display the list of
available commands.

The --guide option's list of guides will then be displayed.

The common commands list is only displayed if neither option, nor a
command or guide name, is given.

Signed-off-by: Philip Oakley <philipoakley@iee.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
builtin/help.c: add list_common_guides_help() function

This implements what "help -g" introduced in the previous step does.

Signed-off-by: Philip Oakley <philipoakley@iee.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
help: mention -a and -g option, and 'git help <concept>' usage.

Reword the overall help given at the end of "git help -a/-g" to
mention how to get help on individual commands and concepts.

Signed-off-by: Philip Oakley <philipoakley@iee.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
doc: include --guide option description for "git help"

Note that the ability to display an individual guide was always
possible. Include this in the update.

Also tell readers how git(1) can be accessed, especially for Git for
Windows users who do not have the 'man' command.  Likewise include a
commentary on how to access this page (Catch 22).

Signed-off-by: Philip Oakley <philipoakley@iee.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
rerere forget: do not segfault if not all stages are present

The loop that fills in the buffers that are later passed to the merge
driver exits early when not all stages of a path are present in the index.
But since the buffer pointers are not initialized in advance, the
subsequent accesses are undefined.

Initialize buffer pointers in advance to avoid undefined behavior later.

That is not sufficient, though, to get correct operation of handle_cache().
The function replays a conflicted merge to extract the part inside the
conflict markers. As written, the loop exits early when a stage is missing.
Consequently, the buffers for later stages that would be present in the
index are not filled in and the merge is replayed with incomplete data.

Fix it by investigating all stages of the given path.

Signed-off-by: Johannes Sixt <j6t@kdbg.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
diffcore-pickaxe: remove unnecessary call to get_textconv()

The fill_one() function is responsible for finding and filling the
textconv filter as necessary, and is called by diff_grep() function
that implements "git log -G<pattern>".

The has_changes() function that implements "git log -S<block>" calls
get_textconv() for two sides being compared, before it checks to see
if it was asked to perform the pickaxe limiting.  Move the code
around to avoid this wastage.

After has_changes() calls get_textconv() to obtain textconv for both
sides, fill_one() is called to use them.

By adding get_textconv() to diff_grep() and relieving fill_one() of
responsibility to find the textconv filter, we can avoid calling
get_textconv() twice in has_changes().

With this change it's also no longer necessary for fill_one() to
modify the textconv argument, therefore pass a pointer instead of a
pointer to a pointer.

Signed-off-by: Simon Ruderich <simon@ruderich.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
diffcore-pickaxe: remove fill_one()

fill_one is _almost_ identical to just calling fill_textconv; the
exception is that for the !DIFF_FILE_VALID case, fill_textconv gives us
an empty buffer rather than a NULL one. Since we currently use the NULL
pointer as a signal that the file is not present on one side of the
diff, we must now switch to using DIFF_FILE_VALID to make the same
check.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Simon Ruderich <simon@ruderich.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
diffcore-pickaxe: respect --no-textconv

git log -S doesn't respect --no-textconv:

    $ echo '*.txt diff=wrong' > .gitattributes
    $ git -c diff.wrong.textconv='xxx' log --no-textconv -Sfoo
    error: cannot run xxx: No such file or directory
    fatal: unable to read files to diff

Reported-by: Matthieu Moy <Matthieu.Moy@grenoble-inp.fr>
Signed-off-by: Simon Ruderich <simon@ruderich.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
diffcore-pickaxe: port optimization from has_changes() to diff_grep()

These two functions are called in the same codeflow to implement
"log -S<block>" and "log -G<pattern>", respectively, but the latter
lacked two obvious optimizations the former implemented, namely:

 - When a pickaxe limit is not given at all, they should return
   without wasting any cycle;

 - When both sides of the filepair are the same, and the same
   textconv conversion apply to them, return early, as there will be
   no interesting differences between the two anyway.

Also release the filespec data once the processing is done (this is
not about leaking memory--it is about releasing data we finished
looking at as early as possible).

Signed-off-by: Junio C Hamano <gitster@pobox.com>
diffcore-pickaxe: fix leaks in "log -S<block>" and "log -G<pattern>"

The diff_grep() and has_changes() functions had early return
codepaths for unmerged filepairs, which simply returned 0.  When we
taught textconv filter to them, one was ignored and continued to
return early without freeing the result filtered by textconv, and
the other had a failed attempt to fix, which allowed the planned
return value 0 to be overwritten by a bogus call to contains().

Signed-off-by: Junio C Hamano <gitster@pobox.com>
diffcore-pickaxe: unify code for log -S/-G

The logic flow of has_changes() used for "log -S" and diff_grep()
used for "log -G" are essentially the same.  See if we have both
sides that could be different in any interesting way, slurp the
contents in core, possibly after applying textconv, inspect the
contents, clean-up and report the result.  The only difference
between the two is how "inspect" step works.

Unify this codeflow in a helper, pickaxe_match(), which takes a
callback function that implements the specific "inspect" step.

After removing the common scaffolding code from the existing
has_changes() and diff_grep(), they each becomes such a callback
function suitable for passing to pickaxe_match().

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t/README: --immediate skips cleanup commands for failed tests

Signed-off-by: Simon Ruderich <simon@ruderich.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
archive: clarify explanation of --worktree-attributes

Make it a bit clearer that --worktree-attributes is about files in the
working tree (checked out files, possibly changed) and not the current
working directory ($PWD).  Link to the ATTRIBUTES section, which has
more details.

Reported-by: Amit Bakshi <ambakshi@gmail.com>
Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t: make PIPE a standard test prerequisite

The 'PIPE' test prerequisite was already defined identically by t9010
and t9300, therefore it makes sense to make it a predefined
prerequisite.

Signed-off-by: Adam Spiers <git@adamspiers.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Typo fix: replacing it's -> its

Signed-off-by: Benoit Bourbie <benoit.bourbie@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'po/help-guides'

"git help" learned "-g" option to show the list of guides just like
list of commands are given with "-a".

* po/help-guides:
  doc: include --guide option description for "git help"
  help: mention -a and -g option, and 'git help <concept>' usage.
  builtin/help.c: add list_common_guides_help() function
  builtin/help.c: add --guide option
  builtin/help.c: split "-a" processing into two
Merge branch 'js/rerere-forget-protect-against-NUL'

A few bugfixes to "git rerere" working on corner case merge
conflicts.

* js/rerere-forget-protect-against-NUL:
  rerere forget: do not segfault if not all stages are present
  rerere forget: grok files containing NUL