When comparing file contents during the second loop through a rename
detection attempt we can skip the expensive byte-by-byte comparsion
if both source and destination files have valid SHA1 values.  This
improves performance by avoiding either an expensive open/mmap to
read the working tree copy, or an expensive inflate of a blob object.

Unfortunately we still have to at least initialize the sizes of the
source and destination files even if the SHA1 values don't match.
Failing to initialize the sizes causes a number of test cases to fail
and start reporting different copy/rename behavior than was expected.
Signed-off-by: NShawn O. Pearce <spearce@spearce.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

The idea is that we are interested in renaming into only one path, so
we do not care about renames that happen elsewhere.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

Introduces global inline:

	hashcmp(const unsigned char *sha1, const unsigned char *sha2)

Uses memcmp for comparison and returns the result based on the length of
the hash name (a future runtime decision).
Acked-by: NAlex Riesen <raa.lkml@gmail.com>
Signed-off-by: NDavid Rientjes <rientjes@google.com>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

The final output from diff used to compare pathnames between
preimage and postimage to tell if the filepair is a rename/copy.
By explicitly marking the filepair created by diffcore_rename(),
the output routine, resolve_rename_copy(), does not have to do
so anymore.  This helps feeding a filepair that has different
pathnames in one and two elements to the diff machinery (most
notably, comparing two blobs).
Signed-off-by: NJunio C Hamano <junkio@cox.net>

Signed-off-by: NJunio C Hamano <junkio@cox.net>

When a broken pair is matched up by rename detector to be merged
back, we do not want to say it is "dissimilar" with the
similarity index.  The output should just say they were changed,
taking the break score left by the earlier diffcore-break run if
any.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

The "score" calculation for diffcore-rename was totally broken.

It scaled "score" as

	score = src_copied * MAX_SCORE / dst->size;

which means that you got a 100% similarity score even if src and dest were
different, if just every byte of dst was copied from src, even if source
was much larger than dst (eg we had copied 85% of the bytes, but _deleted_
the remaining 15%).

That's clearly bogus. We should do the score calculation relative not to
the destination size, but to the max size of the two.

This seems to fix it.
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

To reduce wasted memory, wait until the hash fills up more
densely before we rehash.  This reduces the working set size a
bit further.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

This changes diffcore-rename to reuse statistics information
gathered during similarity estimation, and updates the hashtable
implementation used to keep track of the statistics to be
denser.  This seems to give better performance.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

The "similarity" logic was giving added material way too much
negative weight.  What we wanted to see was how similar the
post-change image was compared to the pre-change image, so the
natural definition of similarity is how much common things are
there, relative to the post-change image's size.

This simplifies things a lot.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

When a reference buffer is used multiple times then its index can be
computed only once and reused multiple times.  This patch adds an extra
pointer to a pointer argument (from_index) to diff_delta() for this.

If from_index is NULL then everything is like before.

If from_index is non NULL and *from_index is NULL then the index is
created and its location stored to *from_index.  In this case the caller
has the responsibility to free the memory pointed to by *from_index.

If from_index and *from_index are non NULL then the index is reused as
is.

This currently saves about 10% of CPU time to repack the git archive.
Signed-off-by: NNicolas Pitre <nico@cam.org>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

This is to rework diffcore break/rename/copy detection code
so that it does not affected when deltifier code gets improved.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

Spotted by Nicolas Pitre.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

dietlibc versions of malloc, calloc and realloc all return NULL if
they're told to allocate 0 bytes, causes the x* wrappers to die().

There are several more places where these calls could end up asking
for 0 bytes, too...

Maybe simply not die()-ing in the x* wrappers if 0/NULL is returned
when the requested size is zero is a safer and easier way to go.
Signed-off-by: NEric Wong <normalperson@yhbt.net>
Signed-off-by: NJunio C Hamano <junkio@cox.net>

When the user is interested in pure renames, there is no point
doing the similarity scores.  This changes the score argument
parsing to special case -M100 (otherwise, it is a precision
scaled value 0 <= v < 1 and would mean 0.1, not 1.0 --- if you
do mean 0.1, you can say -M1), and optimizes the diffcore_rename
transformation to only look at pure renames in that case.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

Signed-off-by: NJunio C Hamano <junkio@cox.net>

A while ago, a rename-detection limit logic was implemented as a
response to this thread:

	http://marc.theaimsgroup.com/?l=git&m=112413080630175

where gitweb was found to be using a lot of time and memory to
detect renames on huge commits.  git-diff family takes -l<num>
flag, and if the number of paths that are rename destination
candidates (i.e. new paths with -M, or modified paths with -C)
are larger than that number, skips rename/copy detection even
when -M or -C is specified on the command line.

This commit makes the rename detection limit easier to use.  You
can have:

	[diff]
		renamelimit = 30

in your .git/config file to specify the default rename detection
limit.  You can override this from the command line; giving 0
means 'unlimited':

	git diff -M -l0

We might want to change the default behaviour, when you do not
have the configuration, to limit it to say 20 paths or so.  This
would also help the diffstat generation after a big 'git pull'.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

When many paths are modified, rename detection takes a lot of time.
The new option -l<num> can be used to disable rename detection when
more than <num> paths are possibly created as renames.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

It is a bit embarrassing that it took this long for a fix since the
problem was first reported on Aug 13th.

    Message-ID: <87y876gl1r.wl@mail2.atmark-techno.com>
    From: Yasushi SHOJI <yashi@atmark-techno.com>
    Newsgroups: gmane.comp.version-control.git
    Subject: [patch] possible memory leak in diff.c::diff_free_filepair()
    Date: Sat, 13 Aug 2005 19:58:56 +0900

This time I used valgrind to make sure that it does not overeagerly
discard memory that is still being used.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

When (A,B) ==> (B,C) rename-copy was detected, we incorrectly said
that C was created by copying B.  This is because we only check if the
path of rename/copy source still exists in the resulting tree to see
if the file is renamed out of existence.  In this case, the new B is
created by copying or renaming A, so the original B is lost and we
should say C is a rename of B not a copy of B.
Signed-off-by: NJunio C Hamano <junkio@cox.net>

The diff_delta() interface was extended to reject generating too big a
delta while we were working on the packed GIT archive format.

Take advantage of that when generating delta in the similarity estimator
used in diffcore-rename.c
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

Anything that generates a delta to see if two objects are close usually
isn't interested in the delta ends up being bigger than some specified
size, and this allows us to stop delta generation early when that
happens.

When rename/copy uses a file that was broken by diffcore-break
as the source, and the broken filepair gets merged back later,
the output was mislabeled as a rename.  In this case, the source
file ends up staying in the output, so we should label it as a
copy instead.
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

This cleans up diff_scoreopt_parse() function that is used to
parse the fractional notation -B, -C and -M option takes.  The
callers are modified to check for errors and complain.  Earlier
they silently ignored malformed input and falled back on the
default.
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

Make it return copied source and insertion separately, so that
later implementation of heuristics can use them more flexibly.

This does not change the heuristics implemented in
diffcore-rename nor diffcore-break in any way.
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

A new diffcore transformation, diffcore-break.c, is introduced.

When the -B flag is given, a patch that represents a complete
rewrite is broken into a deletion followed by a creation.  This
makes it easier to review such a complete rewrite patch.

The -B flag takes the same syntax as the -M and -C flags to
specify the minimum amount of non-source material the resulting
file needs to have to be considered a complete rewrite, and
defaults to 99% if not specified.

As the new test t4008-diff-break-rewrite.sh demonstrates, if a
file is a complete rewrite, it is broken into a delete/create
pair, which can further be subjected to the usual rename
detection if -M or -C is used.  For example, if file0 gets
completely rewritten to make it as if it were rather based on
file1 which itself disappeared, the following happens:

    The original change looks like this:

	file0     --> file0' (quite different from file0)
	file1     --> /dev/null

    After diffcore-break runs, it would become this:

	file0     --> /dev/null
	/dev/null --> file0'
	file1     --> /dev/null

    Then diffcore-rename matches them up:

	file1     --> file0'

The internal score values are finer grained now.  Earlier
maximum of 10000 has been raised to 60000; there is no user
visible changes but there is no reason to waste available bits.
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

The commit 15d061b4

    [PATCH] Fix the way diffcore-rename records unremoved source.

still leaves unneeded delete records in its output stream by
mistake, which was covered up by having an extra check to turn
such a delete into a no-op downstream.  Fix the check in the
diffcore-rename to simplify the output routine.
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

A new macro, DIFF_PAIR_RENAME(), is introduced to distinguish a
filepair that is a rename/copy (the definition of which is src
and dst are different paths, of course).  This removes the hack
used in the record_rename_pair() to always put a non-zero value
in the score field.
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

This attempts to optimize "diff-tree -[CM] --stdin", which
compares successible tree pairs.  This optimization does not
make much sense for other commands in the diff-* brothers.

When reading from --stdin and using rename/copy detection, the
patch makes diff-tree to read the current index file first.
This is done to reuse the optimization used by diff-cache in the
non-cached case.  Similarity estimator can avoid expanding a
blob if the index says what is in the work tree has an exact
copy of that blob already expanded.

Another optimization the patch makes is to check only file sizes
first to terminate similarity estimation early.  In order for
this to work, it needs a way to tell the size of the blob
without expanding it.  Since an obvious way of doing it, which
is to keep all the blobs previously used in the memory, is too
costly, it does so by keeping the filesize for each object it
has already seen in memory.
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

Earier version of diffcore-rename used to keep unmodified
filepair in its output so that the last stage of the processing
that tells renames from copies can make all of rename/copy to
copies.  However this had a bad interaction with other diffcore
filters that wanted to run after diffcore-rename, in that such
unmodified filepair must be retained for proper distinction
between renames and copies to happen.

This patch fixes the problem by changing the way diffcore-rename
records the information needed to distinguish "all are copies"
case and "the last one is a rename" case.
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

This removes a field that is no longer used from diff_score
structure.
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

This introduces a new function to free a common data structure,
and plugs some leaks.
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

The math to reject delta that is too big was confused.
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

The second round similarity estimator simply used the size of
the xdelta itself to estimate the extent of damage.  This patch
keeps that logic to detect big insertions to terminate the check
early, but otherwise looks at the generated delta in order to
estimate the extent of edit more accurately.
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

Earlier implementation had a major screw-up in the memory
management area.  Rename/copy logic sometimes borrowed a pointer
to a structure without any provision for downstream to determine
which pointer is shared and which is not.  This resulted in the
later clean-up code to sometimes double free such structure,
resulting in a segfault.  This made -M and -C useless.

Another problem the earlier implementation had was that it
reordered the patches, and forced the logic to differentiate
renames and copies to depend on that particular order.  This
problem was fixed by teaching rename/copy detection logic not to
do any reordering, and rename-copy differentiator not to depend
on the order of the patches.  The diffs will leave rename/copy
detector in the same destination path order as the patch that
was fed into it.  Some test vectors have been reordered to
accommodate this change.

It also adds a sanity check logic to the human-readable diff-raw
output to detect paths with embedded TAB and LF characters,
which cannot be expressed with that format.  This idea came up
during a discussion with Chris Wedgwood.
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

For later stages to reorder patches, pruning logic and rename detection
logic should not decide which delete to discard (because another entry
said it will take over the file as a rename) until the very end.

Also fix some tests that were assuming the earlier "last one is rename
or keep everything else is copy" semantics of diff-raw format, which no
longer is true.
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

The rename/copy detection logic in earlier round was only good
enough to show patch output and discussion on the mailing list
about the diff-raw format updates revealed many problems with
it.  This patch fixes all the ones known to me, without making
things I want to do later impossible, mostly related to patch
reordering.

 (1) Earlier rename/copy detector determined which one is rename
     and which one is copy too early, which made it impossible
     to later introduce diffcore transformers to reorder
     patches.  This patch fixes it by moving that logic to the
     very end of the processing.

 (2) Earlier output routine diff_flush() was pruning all the
     "no-change" entries indiscriminatingly.  This was done due
     to my false assumption that one of the requirements in the
     diff-raw output was not to show such an entry (which
     resulted in my incorrect comment about "diff-helper never
     being able to be equivalent to built-in diff driver").  My
     special thanks go to Linus for correcting me about this.
     When we produce diff-raw output, for the downstream to be
     able to tell renames from copies, sometimes it _is_
     necessary to output "no-change" entries, and this patch
     adds diffcore_prune() function for doing it.

 (3) Earlier diff_filepair structure was trying to be not too
     specific about rename/copy operations, but the purpose of
     the structure was to record one or two paths, which _was_
     indeed about rename/copy.  This patch discards xfrm_msg
     field which was trying to be generic for this wrong reason,
     and introduces a couple of fields (rename_score and
     rename_rank) that are explicitly specific to rename/copy
     logic.  One thing to note is that the information in a
     single diff_filepair structure _still_ does not distinguish
     renames from copies, and it is deliberately so.  This is to
     allow patches to be reordered in later stages.

 (4) This patch also adds some tests about diff-raw format
     output and makes sure that necessary "no-change" entries
     appear on the output.
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

Earlier round was not treating symbolic links carefully enough,
and would have produced diff output that renamed/copied then
edited the contents of a symbolic link, which made no practical
sense.  Change it to detect only pure renames.
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

This moves the path selection logic from individual programs to a new
diffcore transformer (diff-tree still needs to have its own for
performance reasons).  Also the header printing code in diff-tree was
tweaked not to produce anything when pickaxe is in effect and there is
nothing interesting to report.  An interesting example is the following
in the GIT archive itself:

    $ git-whatchanged -p -C -S'or something in a real script'
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>

When the minimum score is specified as 0 (meaning "use default
value"), set it to the default as we are told.
Signed-off-by: NJunio C Hamano <junkio@cox.net>
Signed-off-by: NLinus Torvalds <torvalds@osdl.org>