daemon: move daemonize() to libgit.a

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
gc: config option for running --auto in background

`gc --auto` takes time and can block the user temporarily (but not any
less annoyingly). Make it run in background on systems that support
it. The only thing lost with running in background is printouts. But
gc output is not really interesting. You can keep it in foreground by
changing gc.autodetach.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
diffcore-order: export generic ordering interface

diffcore_order() interface only accepts a queue of `struct
diff_filepair`.

In the next patches, we'll want to order `struct combine_diff_path`
by path, so let's first rework diffcore-order to also provide
generic low-level interface for ordering arbitrary objects, provided
they have path accessors.

The new interface is:

    - `struct obj_order`    for describing objects to ordering routine, and
    - order_objects()       for actually doing the ordering work.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
diff test: add tests for combine-diff with orderfile

In the next patch combine-diff will have special code-path for taking
orderfile into account. Prepare for making changes by introducing
coverage tests for that case.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
combine-diff: optimize combine_diff_path sets intersection

When generating combined diff, for each commit, we intersect diff
paths from diff(parent_0,commit) to diff(parent_i,commit) comparing
all paths pairs, i.e. doing it the quadratic way. That is correct,
but could be optimized.

Paths come from trees in sorted (= tree) order, and so does diff_tree()
emits resulting paths in that order too. Now if we look at diffcore
transformations, all of them, except diffcore_order, preserve resulting
path ordering:

    - skip_stat_unmatch, grep, pickaxe, filter
                            -- just skip elements -> order stays preserved

    - break                 -- just breaks diff for a path, adding path
                               dup after the path -> order stays preserved

    - detect rename/copy    -- resulting paths are emitted sorted
                               (verified empirically)

So only diffcore_order changes diff paths ordering.

But diffcore_order meaning affects only presentation - i.e. only how to
show the diff, so we could do all the internal computations without
paths reordering, and order only resultant paths set. This is faster,
since, if we know two paths sets are all ordered, their intersection
could be done in linear time.

This patch does just that.

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

                linux.git v3.10..v3.11

            log     log -c

    before  1.9s    20.4s
    after   1.9s    16.6s

                navy.git    (private repo)

            log     log -c

    before  0.83s   15.6s
    after   0.83s    2.1s

P.S.

I think linux.git case is sped up not so much as the second one, since
in navy.git, there are more exotic (subtree, etc) merges.

P.P.S.

My tracing showed that the rest of the time (16.6s vs 1.9s) is usually
spent in computing huge diffs from commit to second parent. Will try to
deal with it, if I'll have time.

P.P.P.S.

For combine_diff_path, ->len is not needed anymore - will remove it in
the next noisy cleanup path, to maintain good signal/noise ratio here.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
combine-diff: combine_diff_path.len is not needed anymore

The field was used in order to speed-up name comparison and also to
mark removed paths by setting it to 0.

Because the updated code does significantly less strcmp and also
just removes paths from the list and free right after we know a path
will not be needed, it is not needed anymore.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
combine-diff: simplify intersect_paths() further

Linus once said:

    I actually wish more people understood the really core low-level
    kind of coding. Not big, complex stuff like the lockless name
    lookup, but simply good use of pointers-to-pointers etc. For
    example, I've seen too many people who delete a singly-linked
    list entry by keeping track of the "prev" entry, and then to
    delete the entry, doing something like

	if (prev)
	    prev->next = entry->next;
	else
	    list_head = entry->next;

    and whenever I see code like that, I just go "This person
    doesn't understand pointers". And it's sadly quite common.

    People who understand pointers just use a "pointer to the entry
    pointer", and initialize that with the address of the
    list_head. And then as they traverse the list, they can remove
    the entry without using any conditionals, by just doing a "*pp =
    entry->next".

Applying that simplification lets us lose 7 lines from this function
even while adding 2 lines of comment.

I was tempted to squash this into the original commit, but because
the benchmarking described in the commit log is without this
simplification, I decided to keep it a separate follow-up patch.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
tests: add checking that combine-diff emits only correct paths

where "correct paths" stands for paths that are different to all
parents.

Up until now, we were testing combined diff only on one file, or on
several files which were all different (t4038-diff-combined.sh).

As recent thinko in "simplify intersect_paths() further" showed, and
also, since we are going to rework code for finding paths different to
all parents, lets write at least basic tests.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
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>
Merge branch 'nd/daemonize-gc' into next

Allow running "gc --auto" in the background.

* nd/daemonize-gc:
  gc: config option for running --auto in background
  daemon: move daemonize() to libgit.a
Merge branch 'jk/run-network-tests-by-default' into next

Teach "make test" to run networking tests when possible by default.

* jk/run-network-tests-by-default:
  tests: turn on network daemon tests by default
Merge branch 'ks/combine-diff' into next

By avoiding running full two-way diff between the resulting
revision and each of its N parents, combine-diff can be sped up
significantly.

* ks/combine-diff:
  tests: add checking that combine-diff emits only correct paths
  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