The idea of xdl_change_compact() is fairly simple:

* Proceed through groups of changed lines in the file to be compacted,
  keeping track of the corresponding location in the "other" file.

* If possible, slide the group up and down to try to give the most
  aesthetically pleasing diff. Whenever it is slid, the current location
  in the other file needs to be adjusted.

But these simple concepts are obfuscated by a lot of index handling that
is written in terse, subtle, and varied patterns. I found it very hard
to convince myself that the function was correct.

So introduce a "struct group" that represents a group of changed lines
in a file. Add some functions that perform elementary operations on
groups:

* Initialize a group to the first group in a file
* Move to the next or previous group in a file
* Slide a group up or down

Even though the resulting code is longer, I think it is easier to
understand and review. Its performance is not changed
appreciably (though it would be if `group_next()` and `group_previous()`
were not inlined).

...and in fact, the rewriting helped me discover another bug in the
--compaction-heuristic code: The update of blank_lines was never done
for the highest possible position of the group. This means that it could
fail to slide the group to its highest possible position, even if that
position had a blank line as its last line. So for example, it yielded
the following diff:

    $ git diff --no-index --compaction-heuristic a.txt b.txt
    diff --git a/a.txt b/b.txt
    index e53969f..0d60c5fe 100644
    --- a/a.txt
    +++ b/b.txt
    @@ -1,3 +1,7 @@
     1
     A
    +
    +B
    +
    +A
     2

when in fact the following diff is better (according to the rules of
--compaction-heuristic):

    $ git diff --no-index --compaction-heuristic a.txt b.txt
    diff --git a/a.txt b/b.txt
    index e53969f..0d60c5fe 100644
    --- a/a.txt
    +++ b/b.txt
    @@ -1,3 +1,7 @@
     1
    +A
    +
    +B
    +
     A
     2

The new code gives the bottom answer.

Original Git commit: e8adf23d1ee97b57c8aea32ee8365203b77c0e42

There is no reason for it to take an array and two indexes as argument,
as it only accesses two elements of the array.

Original Git commit: 152598cbb667471c8f5be16e199922a41452b2d5

It is a common pattern in xdl_change_compact to check that hashes and
strings match. The resulting code to perform this change causes very
long lines and makes it hard to follow the intention. Introduce a helper
function recs_match which performs both checks to increase
code readability.

Original Git commit: 92e5b62fec0e9b647429e8d3736c571c434dd375

time: Export `git_time_monotonic`

cmake: add curl library path

Read binary patches (with no binary data)

refspec: do not set empty rhs for fetch refspecs

When creating and printing diffs, deal with binary deltas that have
binary data specially, versus diffs that have a binary file but lack the
actual binary data.

The `PKG_CHECK_MODULES` function searches a pkg-config module and
then proceeds to set various variables containing information on
how to link to the library. In contrast to the `FIND_PACKAGE`
function, the library path set by `PKG_CHECK_MODULES` will not
necessarily contain linking instructions with a complete path to
the library, though. So when a library is not installed in a
standard location, the linker might later fail due to being
unable to locate it.

While we already honor this when configuring libssh2 by adding
`LIBSSH2_LIBRARY_DIRS` to the link directories, we fail to do so
for libcurl, preventing us to build libgit2 on e.g. FreeBSD. Fix
the issue by adding the curl library directory to the linker
search path.

Instead of skipping printing a binary diff when there is no data, skip
printing when we have a status of `UNMODIFIED`.  This is more in-line
with our internal data model and allows us to expand the notion of
binary data.

In the future, there may have no data because the files were unmodified
(there was no data to produce) or it may have no data because there was
no data given to us in a patch.  We want to treat these cases
separately.

patch_generate: only calculate binary diffs if requested

When generating diffs for binary files, we load and decompress
the blobs in order to generate the actual diff, which can be very
costly. While we cannot avoid this for the case when we are
called with the `GIT_DIFF_SHOW_BINARY` flag, we do not have to
load the blobs in the case where this flag is not set, as the
caller is expected to have no interest in the actual content of
binary files.

Fix the issue by only generating a binary diff when the caller is
actually interested in the diff. As libgit2 uses heuristics to
determine that a blob contains binary data by inspecting its size
without loading from the ODB, this saves us quite some time when
diffing in a repository with binary files.

tests: index: do not re-allocate index

According to the reference the git_checkout_tree and git_checkout_head
functions should accept NULL in the opts field

This was broken since the opts field was dereferenced and thus lead to a
crash.

README: adjust URL to libqgit2 repository

Plug a memory leak caused by re-allocating a `git_index`
structure which has already been allocated by the test suite's
initializer.

transports: http: set substream as disconnected after closing

Teach `git_patch_from_diff` about parsed diffs

Ensure that `git_patch_from_diff` can return the patch for parsed diffs,
not just generate a patch for a generated diff.

filesystem_iterator: fixed double free on error

Support index v4

ignore: allow unignoring basenames in subdirectories

When calling `http_connect` on a subtransport whose stream is already
connected, we first close the stream in case no keep-alive is in use.
When doing so, we do not reset the transport's connection state,
though. Usually, this will do no harm in case the subsequent connect
will succeed. But when the connection fails we are left with a
substransport which is tagged as connected but which has no valid
stream attached.

Fix the issue by resetting the subtransport's connected-state when
closing its stream in `http_connect`.

The .gitignore file allows for patterns which unignore previous
ignore patterns. When unignoring a previous pattern, there are
basically three cases how this is matched when no globbing is
used:

1. when a previous file has been ignored, it can be unignored by
   using its exact name, e.g.

   foo/bar
   !foo/bar

2. when a file in a subdirectory has been ignored, it can be
   unignored by using its basename, e.g.

   foo/bar
   !bar

3. when all files with a basename are ignored, a specific file
   can be unignored again by specifying its path in a
   subdirectory, e.g.

   bar
   !foo/bar

The first problem in libgit2 is that we did not correctly treat
the second case. While we verified that the negative pattern
matches the tail of the positive one, we did not verify if it
only matches the basename of the positive pattern. So e.g. we
would have also negated a pattern like

    foo/fruz_bar
    !bar

Furthermore, we did not check for the third case, where a
basename is being unignored in a certain subdirectory again.

Both issues are fixed with this commit.

Support reading and writing index v4.  Index v4 uses a very simple
compression scheme for pathnames, but is otherwise similar to index v3.

Signed-off-by: David Turner <dturner@twitter.com>

This code is ported from git.git

Signed-off-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: David Turner <dturner@twopensource.com>

stransport memory management improvements

tests: blob: remove unused callback function

When failing to initialize a new stransport stream, we try to
release already allocated memory by calling out to
`git_stream_free`, which in turn called out to the stream's
`free` function pointer. As we only initialize the function
pointer later on, this leads to a `NULL` pointer exception.

Furthermore, plug another memory leak when failing to create the
SSL context.

odb: only provide the empty tree

stransport: make internal functions static

diff: document `git_diff_from_buffer`