tests: turn on network daemon tests by default

We do not run the httpd nor git-daemon tests by default, as
they are rather heavyweight and require network access
(albeit over localhost). However, it would be nice if more
pepole ran them, for two reasons:

  1. We would get more test coverage on more systems.

  2. The point of the test suite is to find regressions. It
     is very easy to change some of the underlying code and
     break the httpd code without realizing you are even
     affecting it. Running the httpd tests helps find these
     problems sooner (ideally before the patches even hit
     the list).

We still want to leave an "out", though, for people who really do
not want to run them. For that reason, the GIT_TEST_HTTPD and
GIT_TEST_GIT_DAEMON variables are now tri-state booleans
(true/false/auto), so you can say GIT_TEST_HTTPD=false to turn the
tests back off.  To support those who want a stable single way to
disable these tests across versions of Git before and after this
change, an empty string explicitly set to these variables is also
taken as "false", so the behaviour changes only for those who:

  a. did not express any preference by leaving these variables
     unset.  They did not test these features before, but now they
     do; or

  b. did express that they want to test these features by setting
     GIT_TEST_FEATURE=false (or any equivalent other ways to tell
     "false" to Git, e.g. "0"), which has been a valid but funny way
     to say that they do want to test the feature only because we
     used to interpret any non-empty string to mean "yes please
     test".  They no longer test that feature.

In addition, we are forgiving of common setup failures (e.g., you do
not have apache installed, or have an old version) when the
tri-state is "auto" (or unset), but report an error when it is
"true". This makes "auto" a sane default, as we should not cause
failures on setups where the tests cannot run. But it allows people
who use "true" to catch regressions in their system (e.g., they
uninstalled apache, but were expecting their automated test runs to
test git-httpd, and would want to be notified).

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tree-diff: rework diff_tree() to generate diffs for multiparent cases as well

Previously diff_tree(), which is now named __diff_tree_sha1(), was
generating diff_filepair(s) for two trees t1 and t2, and that was
usually used for a commit as t1=HEAD~, and t2=HEAD - i.e. to see changes
a commit introduces.

In Git, however, we have fundamentally built flexibility in that a
commit can have many parents - 1 for a plain commit, 2 for a simple merge,
but also more than 2 for merging several heads at once.

For merges there is a so called combine-diff, which shows diff, a merge
introduces by itself, omitting changes done by any parent. That works
through first finding paths, that are different to all parents, and then
showing generalized diff, with separate columns for +/- for each parent.
The code lives in combine-diff.c .

There is an impedance mismatch, however, in that a commit could
generally have any number of parents, and that while diffing trees, we
divide cases for 2-tree diffs and more-than-2-tree diffs. I mean there
is no special casing for multiple parents commits in e.g.
revision-walker .

That impedance mismatch *hurts* *performance* *badly* for generating
combined diffs - in c839f1bd (combine-diff: optimize combine_diff_path
sets intersection) I've already removed some slowness from it, but from
the timings provided there, it could be seen, that combined diffs still
cost more than an order of magnitude more cpu time, compared to diff for
usual commits, and that would only be an optimistic estimate, if we take
into account that for e.g. linux.git there is only one merge for several
dozens of plain commits.

That slowness comes from the fact that currently, while generating
combined diff, a lot of time is spent computing diff(commit,commit^2)
just to only then intersect that huge diff to almost small set of files
from diff(commit,commit^1).

That's because at present, to compute combine-diff, for first finding
paths, that "every parent touches", we use the following combine-diff
property/definition:

D(A,P1...Pn) = D(A,P1) ^ ... ^ D(A,Pn)      (w.r.t. paths)

where

D(A,P1...Pn) is combined diff between commit A, and parents Pi

and

D(A,Pi) is usual two-tree diff Pi..A

So if any of that D(A,Pi) is huge, tracting 1 n-parent combine-diff as n
1-parent diffs and intersecting results will be slow.

And usually, for linux.git and other topic-based workflows, that
D(A,P2) is huge, because, if merge-base of A and P2, is several dozens
of merges (from A, via first parent) below, that D(A,P2) will be diffing
sum of merges from several subsystems to 1 subsystem.

The solution is to avoid computing n 1-parent diffs, and to find
changed-to-all-parents paths via scanning A's and all Pi's trees
simultaneously, at each step comparing their entries, and based on that
comparison, populate paths result, and deduce we could *skip*
*recursing* into subdirectories, if at least for 1 parent, sha1 of that
dir tree is the same as in A. That would save us from doing significant
amount of needless work.

Such approach is very similar to what diff_tree() does, only there we
deal with scanning only 2 trees simultaneously, and for n+1 tree, the
logic is a bit more complex:

D(A,X1...Xn) calculation scheme
-------------------------------

D(A,X1...Xn) = D(A,X1) ^ ... ^ D(A,Xn)       (regarding resulting paths set)

     D(A,Xj)         - diff between A..Xj
     D(A,X1...Xn)    - combined diff from A to parents X1,...,Xn

We start from all trees, which are sorted, and compare their entries in
lock-step:

      A     X1       Xn
      -     -        -
     |a|   |x1|     |xn|
     |-|   |--| ... |--|      i = argmin(x1...xn)
     | |   |  |     |  |
     |-|   |--|     |--|
     |.|   |. |     |. |
      .     .        .
      .     .        .

at any time there could be 3 cases:

     1)  a < xi;
     2)  a > xi;
     3)  a = xi.

Schematic deduction of what every case means, and what to do, follows:

1)  a < xi  ->  ∀j a ∉ Xj  ->  "+a" ∈ D(A,Xj)  ->  D += "+a";  a↓

2)  a > xi

    2.1) ∃j: xj > xi  ->  "-xi" ∉ D(A,Xj)  ->  D += ø;  ∀ xk=xi  xk↓
    2.2) ∀j  xj = xi  ->  xj ∉ A  ->  "-xj" ∈ D(A,Xj)  ->  D += "-xi";  ∀j xj↓

3)  a = xi

    3.1) ∃j: xj > xi  ->  "+a" ∈ D(A,Xj)  ->  only xk=xi remains to investigate
    3.2) xj = xi  ->  investigate δ(a,xj)
     |
     |
     v

    3.1+3.2) looking at δ(a,xk) ∀k: xk=xi - if all != ø  ->

                      ⎧δ(a,xk)  - if xk=xi
             ->  D += ⎨
                      ⎩"+a"     - if xk>xi

    in any case a↓  ∀ xk=xi  xk↓

~

For comparison, here is how diff_tree() works:

D(A,B) calculation scheme
-------------------------

    A     B
    -     -
   |a|   |b|    a < b   ->  a ∉ B   ->   D(A,B) +=  +a    a↓
   |-|   |-|    a > b   ->  b ∉ A   ->   D(A,B) +=  -b    b↓
   | |   | |    a = b   ->  investigate δ(a,b)            a↓ b↓
   |-|   |-|
   |.|   |.|
    .     .
    .     .

~~~~~~~~

This patch generalizes diff tree-walker to work with arbitrary number of
parents as described above - i.e. now there is a resulting tree t, and
some parents trees tp[i] i=[0..nparent). The generalization builds on
the fact that usual diff

D(A,B)

is by definition the same as combined diff

D(A,[B]),

so if we could rework the code for common case and make it be not slower
for nparent=1 case, usual diff(t1,t2) generation will not be slower, and
multiparent diff tree-walker would greatly benefit generating
combine-diff.

What we do is as follows:

1) diff tree-walker __diff_tree_sha1() is internally reworked to be
   a paths generator (new name diff_tree_paths()), with each generated path
   being `struct combine_diff_path` with info for path, new sha1,mode and for
   every parent which sha1,mode it was in it.

2) From that info, we can still generate usual diff queue with
   struct diff_filepairs, via "exporting" generated
   combine_diff_path, if we know we run for nparent=1 case.
   (see emit_diff() which is now named emit_diff_p0only())

3) In order for diff_can_quit_early(), which checks

       DIFF_OPT_TST(opt, HAS_CHANGES))

   to work, that exporting have to be happening not in bulk, but
   incrementally, one diff path at a time.

   For such consumers, there is a new callback in diff_options
   introduced:

       ->pathchange(opt, struct combine_diff_path *)

   which, if set to !NULL, is called for every generated path.

   (see new compat __diff_tree_sha1() wrapper around new paths
    generator for setup)

4) The paths generation itself, is reworked from previous
   __diff_tree_sha1() code according to "D(A,X1...Xn) calculation
   scheme" provided above:

   On the start we allocate [nparent] arrays in place what was
   earlier just for one parent tree.

   then we just generalize loops, and comparison according to the
   algorithm.

Some notes(*):

1) For loops,

 i = 0; do { ... } while (++i < nparent);

is used instead of

 for (i = 0; i < nparent; ++i)
     ...

because for the former case, the compiler have to emit additional
prologue code which checks for i >= nparent case before entering the
loop.

As we require nparent must be >0, that additional overhead
conflicts with the "runs not slower for nparent=1 case than before"
goal.

2) alloca(), for small arrays, is used for the same reason - if we change
it to xmalloc()/free() the timings get worse

3) For every parent tree, we need to keep a tag, whether entry from that
parent equals to entry from minimal parent. For performance reasons I'm
keeping that tag in entry's mode field in unused bit - see S_IFXMIN_NEQ.
   Not doing so, we'd need to alloca another [nparent] array, which hurts
   performance.

4) For emitted paths, memory could be reused, if we know the path was
   processed via callback and will not be needed later. We efficient
   hand-made realloc-style __path_appendnew(), that saves us from ~1-1.5%
   of potential additional slowdown.

5) goto(s) are used in several places, as the code executes a little bit
   faster with lowered register pressure.

Also

- we should now check for FIND_COPIES_HARDER not only when two entries
  names are the same, and their hashes are equal, but also for a case,
  when a path was removed from some of all parents having it.

  The reason is, if we don't, that path won't be emitted at all (see
  "a > xi" case), and we'll just skip it, and FIND_COPIES_HARDER wants
  all paths - with diff or without - to be emitted, to be later analyzed
  for being copies sources.

  The new check is only necessary for nparent >1, as for nparent=1 case
  xmin_eqtotal always =1 =nparent, and a path is always added to diff as
  removal.

~~~~~~~~

Timings for

    # without -c, i.e. testing only nparent=1 case
    `git log --raw --no-abbrev --no-renames`

before and after the patch are as follows:

                navy.git        linux.git v3.10..v3.11

    before      0.611s          1.889s
    after       0.619s          1.907s
    slowdown    1.3%            0.9%

This timings show we did no harm to usual diff(tree1,tree2) generation.
>From the table we can see that we actually did ~1% slowdown, but I think
I've "earned" that 1% in the previous patch (729f7e8e in pu) so for
nparent=1 case, net timings stays approximately the same.

The output also stayed the same.

(*) If we revert 1)-5) to more usual techniques, for nparent=1 case,
    we'll get ~2-2.5% of additional slowdown, which I've tried to avoid, as
   "do no harm for nparent=1 case" rule.

For linux.git, combined diff will run an order of magnitude faster and
appropriate timings will be provided in the next commit, as we'll be
taking advantage of the new diff tree-walker for combined-diff
generation there.

P.S. and combined diff is not some exotic/for-play-only stuff - for
example for a program I write to represent Git archives as readonly
filesystem, there is initial scan with

    `git log --reverse --raw --no-abbrev --no-renames -c`

to extract log of what was created/changed when, as a result building a
map

    {}  sha1    ->  in which commit (and date) a content was added

that `-c` means also show combined diff for merges, and without them, if
a merge is non-trivial (merges changes from two parents with both having
separate changes to a file), or an evil one, the map will not be full,
i.e. some valid sha1 would be absent from it.

That case was my initial motivation for combined diffs speedup.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
combine-diff: speed it up, by using multiparent diff

 tree-walker directly

As was recently shown (c839f1bd "combine-diff: optimize
combine_diff_path sets intersection"), combine-diff runs very slowly. In
that commit we optimized paths sets intersection, but that accounted
only for ~ 25% of the slowness, and as my tracing showed, for linux.git
v3.10..v3.11, for merges a lot of time is spent computing
diff(commit,commit^2) just to only then intersect that huge diff to
almost small set of files from diff(commit,commit^1).

In previous commit, we described the problem in more details, and
reworked the diff tree-walker to be general one - i.e. to work in
multiple parent case too. Now is the time to take advantage of it for
finding paths for combine diff.

The implementation is straightforward - if we know, we can get generated
diff paths directly, and at present that means no diff filtering or
rename/copy detection was requested(*), we can call multiparent tree-walker
directly and get ready paths.

(*) because e.g. at present, all diffcore transformations work on
    diff_filepair queues, but in the future, that limitation can be
    lifted, if filters would operate directly on combine_diff_paths.

Timings for `git log --raw --no-abbrev --no-renames` without `-c` ("git log")
and with `-c` ("git log -c") and with `-c --merges` ("git log -c --merges")
before and after the patch are as follows:

                linux.git v3.10..v3.11

            log     log -c     log -c --merges

    before  1.9s    16.4s      15.2s
    after   1.9s     2.4s       1.1s

The result stayed the same.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'kb/fast-hashmap' (early part) into jch

* 'kb/fast-hashmap' (early part):
  name-hash: retire unused index_name_exists()
  hashmap.h: Use 'unsigned int' for hash-codes everywhere
  Drop unnecessary #includes from test-hashmap
  Add test-hashmap to .gitignore
  read-cache.c: fix memory leaks caused by removed cache entries
  builtin/update-index.c: cleanup update_one
  fix 'git update-index --verbose --again' output
  remove old hash.[ch] implementation
  name-hash.c: remove cache entries instead of marking them CE_UNHASHED
  name-hash.c: use new hash map implementation for cache entries
  name-hash.c: remove unreferenced directory entries
  name-hash.c: use new hash map implementation for directories
  diffcore-rename.c: use new hash map implementation
  diffcore-rename.c: simplify finding exact renames
  diffcore-rename.c: move code around to prepare for the next patch
  buitin/describe.c: use new hash map implementation
  add a hashtable implementation that supports O(1) removal
  submodule: don't access the .gitmodules cache entry after removing it
Merge branch 'nv/commit-gpgsign-config' into jch

Introduce commit.gpgsign configuration variable to force every
commit to be GPG signed.  The variable cannot be overriden from the
command line of some of the commands that create commits except for
"git commit" and "git commit-tree", but I am not convinced that it
is a good idea to sprinkle support for --no-gpg-sign everywhere.

* nv/commit-gpgsign-config:
  test the commit.gpgsign config option
  commit-tree: add and document --no-gpg-sign
  Add the commit.gpgsign option to sign all commits
Merge branch 'jk/pack-bitmap' into jch

Borrows the bitmap index into packfiles from JGit to speed up
enumeration of objects involved in a commit range without having to
fully traverse the history.

* jk/pack-bitmap: (26 commits)
  ewah: unconditionally ntohll ewah data
  ewah: support platforms that require aligned reads
  read-cache: use get_be32 instead of hand-rolled ntoh_l
  block-sha1: factor out get_be and put_be wrappers
  do not discard revindex when re-preparing packfiles
  pack-bitmap: implement optional name_hash cache
  t/perf: add tests for pack bitmaps
  t: add basic bitmap functionality tests
  count-objects: recognize .bitmap in garbage-checking
  repack: consider bitmaps when performing repacks
  repack: handle optional files created by pack-objects
  repack: turn exts array into array-of-struct
  repack: stop using magic number for ARRAY_SIZE(exts)
  pack-objects: implement bitmap writing
  rev-list: add bitmap mode to speed up object lists
  pack-objects: use bitmaps when packing objects
  pack-objects: split add_object_entry
  pack-bitmap: add support for bitmap indexes
  documentation: add documentation for the bitmap format
  ewah: compressed bitmap implementation
  ...

# Conflicts:
# 	builtin/pack-objects.c
# 	builtin/repack.c
Merge branch 'da/pull-ff-configuration' into jch

"git pull" learned to pay attention to pull.ff configuration
variable.

* da/pull-ff-configuration:
  pull: add --ff-only to the help text
  pull: add pull.ff configuration
Merge branch 'dk/blame-janitorial' (early part) into jch

* 'dk/blame-janitorial' (early part):
  builtin/blame.c::prepare_lines: fix allocation size of sb->lineno
  Eliminate same_suspect function in builtin/blame.c
  builtin/blame.c: struct blame_entry does not need a prev link
Merge branch 'bk/refresh-missing-ok-in-merge-recursive' into jch

Allows "merge-recursive" to work in an empty (temporary) working
tree again when there are renames involved, correcting an old
regression in 1.7.7 era.

* bk/refresh-missing-ok-in-merge-recursive:
  merge-recursive.c: Tolerate missing files while refreshing index
  read-cache.c: Extend make_cache_entry refresh flag with options
  read-cache.c: Refactor --ignore-missing implementation
  t3030-merge-recursive: Test known breakage with empty work tree
Merge branch 'ds/rev-parse-required-args' into jch

"git rev-parse --default" without the required option argument did
not diagnose it as an error.

* ds/rev-parse-required-args:
  rev-parse: check i before using argv[i] against argc
Merge branch 'jk/config-path-include-fix' into jch

include.path variable (or any variable that expects a path that can
use ~username expansion) in the configuration file is not a
boolean, but the code failed to check it.

* jk/config-path-include-fix:
  handle_path_include: don't look at NULL value
  expand_user_path: do not look at NULL path
Merge branch 'nd/diff-quiet-stat-dirty' into jch

"git diff --quiet -- pathspec1 pathspec2" sometimes did not return
correct status value.

* nd/diff-quiet-stat-dirty:
  diff: do not quit early on stat-dirty files
  Move diffcore_skip_stat_unmatch core logic out for reuse later
Merge branch 'nd/submodule-pathspec-ending-with-slash' into jch

Allow "git cmd path/", when the 'path' is where a submodule is
bound to the top-level working tree, to match 'path', despite the
extra and unnecessary trailing slash.

* nd/submodule-pathspec-ending-with-slash:
  clean: use cache_name_is_other()
  clean: replace match_pathspec() with dir_path_match()
  Pass directory indicator to match_pathspec_item()
  match_pathspec: match pathspec "foo/" against directory "foo"
  dir.c: prepare match_pathspec_item for taking more flags
  Rename match_pathspec_depth() to match_pathspec()
  Convert some match_pathspec_depth() to dir_path_match()
  Convert some match_pathspec_depth() to ce_path_match()

# Conflicts:
# 	t/t4010-diff-pathspec.sh
Merge branch 'bs/stdio-undef-before-redef' into jch

When we replace broken macros from stdio.h in git-compat-util.h,
#undef them to avoid re-definition warnings from the C
preprocessor.

* bs/stdio-undef-before-redef:
  git-compat-util.h: #undef (v)snprintf before #define them
Merge branch 'ep/varscope' into jch

Shrink lifetime of variables by moving their definitions to an
inner scope where appropriate.

* ep/varscope:
  builtin/gc.c: reduce scope of variables
  builtin/fetch.c: reduce scope of variable
  builtin/commit.c: reduce scope of variables
  builtin/clean.c: reduce scope of variable
  builtin/blame.c: reduce scope of variables
  builtin/apply.c: reduce scope of variables
  bisect.c: reduce scope of variable
Merge branch 'ks/diff-c-with-diff-order' into jch

Teach combine-diff to honour the path-output-order imposed by
diffcore-order.

* ks/diff-c-with-diff-order:
  combine-diff: simplify intersect_paths() further
  combine-diff: combine_diff_path.len is not needed anymore
  combine-diff: optimize combine_diff_path sets intersection
  diff test: add tests for combine-diff with orderfile
  diffcore-order: export generic ordering interface
Merge branch 'wk/submodule-on-branch' into jch

Makes sure 'submodule update' modes that do not detach HEADs can
be used more pleasantly by checking out a concrete branch when
cloning them to prime the well.

* wk/submodule-on-branch:
  Documentation: Describe 'submodule update --remote' use case
  submodule: Explicit local branch creation in module_clone
  submodule: Document module_clone arguments in comments
  submodule: Make 'checkout' update_module explicit

# Conflicts:
# 	t/t7406-submodule-update.sh
Merge branch 'mw/symlinks' into jch

All subcommands that take pathspecs mishandled an in-tree symbolic
link when given it as a full path from the root (which arguably is
a sick way to use pathspecs).  "git ls-files -s $(pwd)/RelNotes" in
our tree is an easy reproduction recipe.

* mw/symlinks:
  setup: don't dereference in-tree symlinks for absolute paths
  setup: add abspath_part_inside_repo() function
  t0060: add tests for prefix_path when path begins with work tree
  t0060: add test for prefix_path when path == work tree
  t0060: add test for prefix_path on symlinks via absolute paths
  t3004: add test for ls-files on symlinks via absolute paths
Merge branch 'nd/test-rename-reset' into jch

* nd/test-rename-reset:
  t7101, t7014: rename test files to indicate what that file is for
Merge branch 'ks/tree-diff-walk' into jch

* ks/tree-diff-walk:
  Finally switch over tree descriptors to contain a pre-parsed entry
  revision: convert to using diff_tree_sha1()
  line-log: convert to using diff_tree_sha1()
  tree-diff: convert diff_root_tree_sha1() to just call diff_tree_sha1 with old=NULL
  tree-diff: allow diff_tree_sha1 to accept NULL sha1