Use a typedef for the submodule_foreach callback.

tree: mark a tree as already sorted

This fits with the style for the rest of the project, but more
importantly, makes life easier for bindings authors who auto-generate
code.

The trees are sorted on-disk, so we don't have to go over them
again. This cuts almost a fifth of time spent parsing trees.

CMakeLists: Compare CMAKE_SIZEOF_VOID_P as a number, not as a string

checkout test: Apply umask to file-mode test as well

tree: use a specialised mode parse function

index: canonicalize inserted paths safely

When adding to the index, we look to see if a portion of the given
path matches a portion of a path in the index.  If so, we will use
the existing path information.  For example, when adding `foo/bar.c`,
if there is an index entry to `FOO/other` and the filesystem is case
insensitive, then we will put `bar.c` into the existing tree instead
of creating a new one with a different case.

Use `strncmp` to do that instead of `memcmp`.  When we `bsearch`
into the index, we locate the position where the new entry would
go.  The index entry at that position does not necessarily have
a relation to the entry we're adding, so we cannot make assumptions
and use `memcmp`.  Instead, compare them as strings.

When canonicalizing paths, we look for the first index entry that
matches a given substring.

Instead of going out to strtol, which is made to parse generic numbers,
copy a parse function from git which is specialised for file modes.

Fix the file-mode test to expect system umask being applied to the
created file as well (it is currently applied to the directory only).
This fixes the test on systems where umask != 022.

Signed-off-by: Michał Górny <mgorny@gentoo.org>

tree: mark cloned tree entries as un-pooled

When duplicating a `struct git_tree_entry` with
`git_tree_entry_dup` the resulting structure is not allocated
inside a memory pool. As we do a 1:1 copy of the original struct,
though, we also copy the `pooled` field, which is set to `true`
for pooled entries. This results in a huge memory leak as we
never free tree entries that were duplicated from a pooled
tree entry.

Fix this by marking the newly duplicated entry as un-pooled.

Improvements to tree parsing speed

Compiler warning fixes

Return an error in case the length is too big. Also take this
opportunity to have a single allocating function for the size and
overflow logic.

Recursive Merge

This reduces the size of the struct from 32 to 26 bytes, and leaves a
single padding byte at the end of the struct (which comes from the
zero-length array).

We already know the size due to the `memchr()` so use that information
instead of calling `strlen()` on it.

These are rather small allocations, so we end up spending a non-trivial
amount of time asking the OS for memory. Since these entries are tied to
the lifetime of their tree, we can give the tree a pool so we speed up
the allocations.

We've already looked at the filename with `memchr()` and then used
`strlen()` to allocate the entry. We already know how much we have to
advance to get to the object id, so add the filename length instead of
looking at each byte again.

When building a recursive merge base, allow conflicts to occur.
Use the file (with conflict markers) as the common ancestor.

The user has already seen and dealt with this conflict by virtue
of having a criss-cross merge.  If they resolved this conflict
identically in both branches, then there will be no conflict in the
result.  This is the best case scenario.

If they did not resolve the conflict identically in the two branches,
then we will generate a new conflict.  If the user is simply using
standard conflict output then the results will be fairly sensible.
But if the user is using a mergetool or using diff3 output, then the
common ancestor will be a conflict file (itself with diff3 output,
haha!).  This is quite terrible, but it matches git's behavior.

Use annotated commits to act as our virtual bases, instead of regular
commits, to avoid polluting the odb with virtual base commits and
trees.  Instead, build an annotated commit with an index and pointers
to the commits that it was merged from.

When there are more than two common ancestors, continue merging the
virtual base with the additional common ancestors, effectively
octopus merging a new virtual base.