combine-diff: move show_log_first logic/action out of paths scanning

Judging from sample outputs and tests nothing changes in diff -c output,
and this change will help later patches, when we'll be refactoring paths
scanning into its own function with several variants - the
show_log_first logic / code will stay common to all of them.

NOTE: only now we have to take care to explicitly not show anything if
    parents array is empty, as in fact there are some clients in Git code,
    which calls diff_tree_combined() in such a way.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
combine-diff: move changed-paths scanning logic into its own function

Move code for finding paths for which diff(commit,parent_i) is not-empty
for all parents to separate function - at present we have generic (and
slow) code for this job, which translates 1 n-parent problem to n
1-parent problems and then intersect results, and will be adding another
limited, but faster, paths scanning implementation in the next patch.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tree-diff: no need to manually verify that there is no mode change for a path

Because if there is, such two tree entries would never be compared as
equal - the code in base_name_compare() explicitly compares modes, if
there is a change for dir bit, even for equal paths, entries would
compare as different.

The code I'm removing here is from 2005 April 262e82b4 (Fix diff-tree
recursion), which pre-dates base_name_compare() introduction in 958ba6c9
(Introduce "base_name_compare()" helper function) by a month.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tree-diff: no need to pass match to skip_uninteresting()

It is neither used there as input, nor the output written through it, is
used outside.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tree-diff: show_tree() is not needed

We don't need special code for showing added/removed subtree, because we
can do the same via diff_tree_sha1, just passing NULL for absent tree.

And compared to show_tree(), which was calling show_entry() for every
tree entry, that would lead to the same show_entry() callings:

    show_tree(t):
        for e in t.entries:
            show_entry(e)

    diff_tree_sha1(NULL, new):  /* the same applies to (old, NULL) */
        diff_tree(t1=NULL, t2)
            ...
            if (!t1->size)
                show_entry(t2)
            ...

and possible overhead is negligible, since after the patch, timing for

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

for navy.git and `linux.git v3.10..v3.11` is practically the same.

So let's say goodbye to show_tree() - it removes some code, but also,
and what is important, consolidates more code for showing/recursing into
trees into one place.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
grep: add grep.fullName config variable

This configuration variable sets the default for the --full-name option.

Signed-off-by: Andreas Schwab <schwab@linux-m68k.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tree-diff: consolidate code for emitting diffs and recursion in one place

Currently both compare_tree_entry() and show_entry() invoke opt diff
callbacks (opt->add_remove() and opt->change()), and also they both have
code which decides whether to recurse into sub-tree, and whether to emit
a tree as separate entry if DIFF_OPT_TREE_IN_RECURSIVE is set.

I.e. we have code duplication and logic scattered on two places.

Let's consolidate it - all diff emiting code and recurion logic moves
to show_entry, which is now named as show_path, because it shows diff
for a path, based on up to two tree entries, with actual diff emitting
code being kept in new helper emit_diff() for clarity.

What we have as the result, is that compare_tree_entry is now free from
code with logic for diff generation, and also performance is not
affected as timings for

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

for navy.git and `linux.git v3.10..v3.11`, just like in previous patch,
stay the same.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tree-diff: don't assume compare_tree_entry() returns -1,0,1

It does, but we'll be reworking it in the next patch after it won't, and
besides it is better to stick to standard
strcmp/memcmp/base_name_compare/etc... convention, where comparison
function returns <0, =0, >0

Regarding performance, comparing for <0, =0, >0 should be a little bit
faster, than switch, because it is just 1 test-without-immediate
instruction and then up to 3 conditional branches, and in switch you
have up to 3 tests with immediate and up to 3 conditional branches.

No worry, that update_tree_entry(t2) is duplicated for =0 and >0 - it
will be good after we'll be adding support for multiparent walker and
will stay that way.

=0 case goes first, because it happens more often in real diffs - i.e.
paths are the same.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tree-diff: move all action-taking code out of compare_tree_entry()

- let it do only comparison.

This way the code is cleaner and more structured - cmp function only
compares, and the driver takes action based on comparison result.

There should be no change in performance, as effectively, we just move
if series from on place into another, and merge it to was-already-there
same switch/if, so the result is maybe a little bit faster.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tree-diff: rename compare_tree_entry -> tree_entry_pathcmp

Since previous commit, this function does not compare entry hashes, and
mode are compared fully outside of it. So what it does is compare entry
names and DIR bit in modes. Reflect this in its name.

Add documentation stating the semantics, and move the note about
files/dirs comparison to it.

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

We moved all action-taking code below show_path() in recent HEAD~~
(tree-diff: move all action-taking code out of compare_tree_entry).

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
tree-diff: simplify tree_entry_pathcmp

Since an earlier "Finally switch over tree descriptors to contain a
pre-parsed entry", we can safely access all tree_desc->entry fields
directly instead of first "extracting" them through
tree_entry_extract.

Use it. The code generated stays the same - only it now visually looks
cleaner.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
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 convention for prefixing
such helpers with "ll_". So the final renaming is

    diff_tree() -> ll_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
ll_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
ll_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>
Acked-by: Thomas Schwinge <thomas@codesourcery.com> (GNU Hurd changes)
Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t1400: fix name and expected result of one test

The test

    stdin -z create ref fails with zero new value

actually passes an empty new value, not a zero new value.  So rename
the test s/zero/empty/, and change the expected error from

    fatal: create $c given zero new value

to

    fatal: create $c missing <newvalue>

Of course, this makes the test fail now, because although "git
update-ref" tries to distinguish between these two errors, it does not
succeed in this situation.  Fixing it is more than a one-liner, so
mark the test test_expect_failure for now.  The failure will be fixed
later in this patch series.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>