The mailing address for the FSF has changed over the years.  Rather than
updating the address across all files, refer readers to gnu.org, as the
GNU GPL documentation now suggests for license notices.  The mailing
address is retained in the full license files (COPYING and LGPL-2.1).

The old address is still present in t/diff-lib/COPYING.  This is
intentional, as the file is used in tests and the contents are not
expected to change.

Signed-off-by: Todd Zullinger <tmz@pobox.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

A common mistake when writing binary search is to allow possible
integer overflow by using the simple average:

	mid = (min + max) / 2;

Instead, use the overflow-safe version:

	mid = min + (max - min) / 2;

This translation is safe since the operation occurs inside a loop
conditioned on "min < max". The included changes were found using
the following git grep:

	git grep '/ *2;' '*.c'

Making this cleanup will prevent future review friction when a new
binary search is contructed based on existing code.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Reviewed-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

When adding a new function to the end of a file, it's enough to know
that 1) the addition is at the end of the file; and 2) there is a
function _somewhere_ in there.

If we had simply been changing the end of an existing function, then we
would also be deleting something from the old version.

This fixes the case where we add e.g.

	// Begin of dummy
	static int dummy(void)
	{
	}

to the end of the file.

Signed-off-by: Vegard Nossum <vegard.nossum@oracle.com>
Acked-by: René Scharfe <l.s.r@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

"git diff" and its family had two experimental heuristics to shift
the contents of a hunk to make the patch easier to read.  One of
them turns out to be better than the other, so leave only the
"--indent-heuristic" option and remove the other one.

* jc/retire-compaction-heuristics:
  diff: retire "compaction" heuristics

When a patch inserts a block of lines, whose last lines are the
same as the existing lines that appear before the inserted block,
"git diff" can choose any place between these existing lines as the
boundary between the pre-context and the added lines (adjusting the
end of the inserted block as appropriate) to come up with variants
of the same patch, and some variants are easier to read than others.

We have been trying to improve the choice of this boundary, and Git
2.11 shipped with an experimental "compaction-heuristic".  Since
then another attempt to improve the logic further resulted in a new
"indent-heuristic" logic.  It is agreed that the latter gives better
result overall, and the former outlived its usefulness.

Retire "compaction", and keep "indent" as an experimental feature.
The latter hopefully will be turned on by default in a future
release, but that should be done as a separate step.

Suggested-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

The xdiff code hashes every line of both sides of a diff,
and then compares those hashes to find duplicates. The
overall performance depends both on how fast we can compute
the hashes, but also on how many hash collisions we see.

The idea of XDL_FAST_HASH is to speed up the hash
computation. But the generated hashes have worse collision
behavior. This means that in some cases it speeds diffs up
(running "git log -p" on git.git improves by ~8% with it),
but in others it can slow things down. One pathological case
saw over a 100x slowdown[1].

There may be a better hash function that covers both
properties, but in the meantime we are better off with the
original hash. It's slightly slower in the common case, but
it has fewer surprising pathological cases.

[1] http://public-inbox.org/git/20141222041944.GA441@peff.net/

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

Clean-up for a recently graduated topic.

* mh/diff-indent-heuristic:
  xdiff: rename "struct group" to "struct xdlgroup"

Commit e8adf23 (xdl_change_compact(): introduce the concept
of a change group, 2016-08-22) added a "struct group" type
to xdiff/xdiffi.c. But the POSIX system header "grp.h"
already defines "struct group" (it is part of the getgrnam
interface). This happens to work because the new type is
local to xdiffi.c, and the xdiff code includes a relatively
small set of system headers. But it will break compilation
if xdiff ever switches to using git-compat-util.h.  It can
also probably cause confusion with tools that look at the
whole code base, like coccinelle or ctags.

Let's resolve by giving the xdiff variant a scoped name,
which is closer to other xdiff types anyway (e.g.,
xdlfile_t, though note that xdiff is fond if typedefs when
Git usually is not).

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

Output from "git diff" can be made easier to read by selecting
which lines are common and which lines are added/deleted
intelligently when the lines before and after the changed section
are the same.  A command line option is added to help with the
experiment to find a good heuristics.

* mh/diff-indent-heuristic:
  blame: honor the diff heuristic options and config
  parse-options: add parse_opt_unknown_cb()
  diff: improve positioning of add/delete blocks in diffs
  xdl_change_compact(): introduce the concept of a change group
  recs_match(): take two xrecord_t pointers as arguments
  is_blank_line(): take a single xrecord_t as argument
  xdl_change_compact(): only use heuristic if group can't be matched
  xdl_change_compact(): fix compaction heuristic to adjust ixo

"git diff -W" output needs to extend the context backward to
include the header line of the current function and also forward to
include the body of the entire current function up to the header
line of the next one.  This process may have to merge to adjacent
hunks, but the code forgot to do so in some cases.

* rs/xdiff-merge-overlapping-hunks-for-W-context:
  xdiff: fix merging of hunks with -W context and -u context