fetch: handle overlaping refspecs on --prune

We need to consider that a remote-tracking branch may match more than
one rhs of a fetch refspec. In such a case, it is not enough to stop at
the first match but look at all of the matches in order to determine
whether a head is stale.

To this goal, introduce a variant of query_refspecs which returns all of
the matching refspecs and loop over those answers to check for
staleness.

Signed-off-by: Carlos Martín Nieto <cmn@elego.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
apply --ignore-space-change: lines with and without leading whitespaces do not match

The fuzzy_matchlines() function is used when attempting to resurrect
a patch that is whitespace-damaged, or when applying a patch that
was produced against an old codebase to the codebase after
indentation change.

The patch may want to change a line "a_bc" ("_" is used throught
this description for a whitespace to make it stand out) in the
original into something else, and we may not find "a_bc" in the
current source, but there may be "a__bc" (two spaces instead of one
the whitespace-damaged patch claims to expect).  By ignoring the
amount of whitespaces, it forces "git apply" to consider that "a_bc"
in the broken patch meant to refer to "a__bc" in reality.

However, the implementation special cases a run of whitespaces at
the beginning of a line and makes "abc" match "_abc", even though a
whitespace in the middle of string never matches a 0-width gap,
e.g. "a_bc" does not match "abc".  A run of whitespace at the end of
one string does not match a 0-width end of line on the other line,
either, e.g. "abc_" does not match "abc".

Fix this inconsistency by making the code skip leading whitespaces
only when both strings begin with a whitespace.  This makes the
option mean the same as the option of the same name in "diff" and
"git diff".

Note that I am not sure if anybody sane should use this option in
the first place.  The fuzzy match logic may be able to find the
original line that the patch author may have meant to touch because
it does not fully trust what the original lines say (i.e. context
lines prefixed by " " and old lines prefixed by "-" does not have to
exactly match the contents the patch is applied to).  There is no
reason for us to trust what the replacement lines (i.e. new lines
prefixed by "+") say, either, but with this option enabled, we end
up copying these new lines with suspicious whitespace distributions
literally into the patched result.  But as long as we keep it, we
should make it do its insane thing consistently.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
tree-diff: remove special-case diff-emitting code for empty-tree cases

While walking trees, we iterate their entries from lowest to highest in
sort order, so empty tree means all entries were already went over.

If we artificially assign +infinity value to such tree "entry", it will
go after all usual entries, and through the usual driver loop we will be
taking the same actions, which were hand-coded for special cases, i.e.

    t1 empty, t2 non-empty
        pathcmp(+∞, t2) -> +1
        show_path(/*t1=*/NULL, t2);     /* = t1 > t2 case in main loop */

    t1 non-empty, t2-empty
        pathcmp(t1, +∞) -> -1
        show_path(t1, /*t2=*/NULL);     /* = t1 < t2 case in main loop */

In other words when we have t1 and t2, we return a sign that tells the
caller to indicate the "earlier" one to be emitted, and by returning the
sign that causes the non-empty side to be emitted, we will automatically
cause the entries from the remaining side to be emitted, without
attempting to touch the empty side at all.  We can teach
tree_entry_pathcmp() to pretend that an empty tree has an element that
sorts after anything else to achieve this.

Right now we never go to when compared tree descriptors are both
infinity, as this condition is checked in the loop beginning as
finishing criteria, but will do so in the future, when there will be
several parents iterated simultaneously, and some pair of them would run
to the end.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tree-diff: diff_tree() should now be static

We reworked all its users to use the functionality through
diff_tree_sha1 variant in recent patches (see "tree-diff: allow
diff_tree_sha1 to accept NULL sha1" and what comes next).

diff_tree() is now not used outside tree-diff.c - make it static.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tree-diff: rework diff_tree interface to be sha1 based

In the next commit this will allow to reduce intermediate calls, when
recursing into subtrees - at that stage we know only subtree sha1, and
it is natural for tree walker to start from that phase. For now we do

    diff_tree
        show_path
            diff_tree_sha1
                diff_tree
                    ...

and the change will allow to reduce it to

    diff_tree
        show_path
            diff_tree

Also, it will allow to omit allocating strbuf for each subtree, and just
reuse the common strbuf via playing with its len.

The above-mentioned improvements go in the next 2 patches.

The downside is that try_to_follow_renames(), if active, we cause
re-reading of 2 initial trees, which was negligible based on my timings,
and which is outweighed cogently by the upsides.

NOTE To keep with the current interface and semantics, I needed to
rename the function from diff_tree() to diff_tree_sha1(). As
diff_tree_sha1() was already used, and the function we are talking here
is its more low-level helper, let's use Linux convention for prefixing
such helpers with double underscore. So the final renaming is

    diff_tree() -> __diff_tree_sha1()

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tree-diff: no need to call "full" diff_tree_sha1 from show_path()

As described in previous commit, when recursing into sub-trees, we can
use lower-level tree walker, since its interface is now sha1 based.

The change is ok, because diff_tree_sha1() only invokes
__diff_tree_sha1(), and also, if base is empty, try_to_follow_renames().
But base is not empty here, as we have added a path and '/' before
recursing.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tree-diff: reuse base str(buf) memory on sub-tree recursion

instead of allocating it all the time for every subtree in
__diff_tree_sha1, let's allocate it once in diff_tree_sha1, and then all
callee just use it in stacking style, without memory allocations.

This should be faster, and for me this change gives the following
slight speedups for

    git log --raw --no-abbrev --no-renames --format='%H'

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

    before      0.618s      1.903s
    after       0.611s      1.889s
    speedup     1.1%        0.7%

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Portable alloca for Git

In the next patch we'll have to use alloca() for performance reasons,
but since alloca is non-standardized and is not portable, let's have a
trick with compatibility wrappers:

1. at configure time, determine, do we have working alloca() through
   alloca.h, and define

    #define HAVE_ALLOCA_H

   if yes.

2. in code

    #ifdef HAVE_ALLOCA_H
    # include <alloca.h>
    # define xalloca(size)      (alloca(size))
    # define xalloca_free(p)    do {} while(0)
    #else
    # define xalloca(size)      (xmalloc(size))
    # define xalloca_free(p)    (free(p))
    #endif

   and use it like

   func() {
       p = xalloca(size);
       ...

       xalloca_free(p);
   }

This way, for systems, where alloca is available, we'll have optimal
on-stack allocations with fast executions. On the other hand, on
systems, where alloca is not available, this gracefully fallbacks to
xmalloc/free.

Both autoconf and config.mak.uname configurations were updated. For
autoconf, we are not bothering considering cases, when no alloca.h is
available, but alloca() works some other way - its simply alloca.h is
available and works or not, everything else is deep legacy.

For config.mak.uname, I've tried to make my almost-sure guess for where
alloca() is available, but since I only have access to Linux it is the
only change I can be sure about myself, with relevant to other changed
systems people Cc'ed.

NOTE

SunOS and Windows had explicit -DHAVE_ALLOCA_H in their configurations.
I've changed that to now-common HAVE_ALLOCA_H=YesPlease which should be
correct.

Cc: Brandon Casey <drafnel@gmail.com>
Cc: Marius Storm-Olsen <mstormo@gmail.com>
Cc: Johannes Sixt <j6t@kdbg.org>
Cc: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Cc: Ramsay Jones <ramsay@ramsay1.demon.co.uk>
Cc: Gerrit Pape <pape@smarden.org>
Cc: Petr Salinger <Petr.Salinger@seznam.cz>
Cc: Jonathan Nieder <jrnieder@gmail.com>
Cc: Thomas Schwinge <tschwinge@gnu.org>
Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
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 "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_first_parent_only())

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) alloca(), for small arrays, is used for "runs not slower for
   nparent=1 case than before" goal - if we change it to xmalloc()/free()
   the timings get ~1% worse. For alloca() we use just-introduced
   xalloca/xalloca_free compatibility wrappers, so it should not be a
   portability problem.

2) 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.

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

4) 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 ("tree-diff: reuse base
str(buf) memory on sub-tree recursion", HEAD~~) so for nparent=1 case,
net timings stays approximately the same.

The output also stayed the same.

(*) If we revert 1)-4) 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 in "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 'jk/subtree-prefix' into jch

A stray environment variable $prefix could have leaked into and
affected the behaviour of the "subtree" script.

* jk/subtree-prefix:
  subtree: initialize "prefix" variable
Merge branch 'ah/doc-gitk-config' into jch

* ah/doc-gitk-config:
  Documentation/gitk: document the location of the configulation file
Merge branch 'fr/add-interactive-argv-array' into jch

* fr/add-interactive-argv-array:
  add: use struct argv_array in run_add_interactive()
Merge branch 'jk/pack-bitmap' into jch

Instead of dying when asked to (re)pack with the reachability
bitmap when a bitmap cannot be built, just (re)pack without
producing a bitmap in such a case, with a warning.

* jk/pack-bitmap:
  pack-objects: turn off bitmaps when skipping objects
Merge branch 'jk/pack-bitmap-progress' into jch

The progress output while repacking and transferring objects showed
an apparent large silence while writing the objects out of existing
packfiles, when the reachability bitmap was in use.

* jk/pack-bitmap-progress:
  pack-objects: show reused packfile objects in "Counting objects"
  pack-objects: show progress for reused packfiles
Merge branch 'ks/tree-diff-nway' (early part) into jch

* 'ks/tree-diff-nway' (early part):
  tree-diff: simplify tree_entry_pathcmp
  tree-diff: show_path prototype is not needed anymore
  tree-diff: rename compare_tree_entry -> tree_entry_pathcmp
  tree-diff: move all action-taking code out of compare_tree_entry()
  tree-diff: don't assume compare_tree_entry() returns -1,0,1
  tree-diff: consolidate code for emitting diffs and recursion in one place
  tree-diff: show_tree() is not needed
  tree-diff: no need to pass match to skip_uninteresting()
  tree-diff: no need to manually verify that there is no mode change for a path
  combine-diff: move changed-paths scanning logic into its own function
  combine-diff: move show_log_first logic/action out of paths scanning
Merge branch 'bp/commit-p-editor' into jch

When it is not necessary to edit a commit log message (e.g. "git
commit -m" is given a message without specifying "-e"), we used to
disable the spawning of the editor by overriding GIT_EDITOR, but
this means all the uses of the editor, other than to edit the
commit log message, are also affected.

* bp/commit-p-editor:
  run-command: mark run_hook_with_custom_index as deprecated
  merge hook tests: fix and update tests
  merge: fix GIT_EDITOR override for commit hook
  commit: fix patch hunk editing with "commit -p -m"
  test patch hunk editing with "commit -p -m"
  merge hook tests: use 'test_must_fail' instead of '!'
  merge hook tests: fix missing '&&' in test
Merge branch 'ys/fsck-commit-parsing' into jch

* ys/fsck-commit-parsing:
  fsck.c:fsck_commit(): use skip_prefix() to verify and skip constant
  fsck.c:fsck_ident(): ident points at a const string

# Conflicts:
# 	fsck.c
Merge branch 'bg/rebase-off-of-previous-branch' into jch

* bg/rebase-off-of-previous-branch:
  rebase: allow "-" short-hand for the previous branch
Merge branch 'dt/tests-with-env-not-subshell' into jch

* dt/tests-with-env-not-subshell:
  tests: use "env" to run commands with temporary env-var settings