summaryrefslogtreecommitdiff
path: root/diffcore-rename.c
AgeCommit message (Collapse)AuthorFilesLines
2007-10-26Do the fuzzy rename detection limits with the exact renames removedLibravatar Linus Torvalds1-14/+18
When we do the fuzzy rename detection, we don't care about the destinations that we already handled with the exact rename detector. And, in fact, the code already knew that - but the rename limiter, which used to run *before* exact renames were detected, did not. This fixes it so that the rename detection limiter now bases its decisions on the *remaining* rename counts, rather than the original ones. Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-10-26Fix ugly magic special case in exact rename detectionLibravatar Linus Torvalds1-13/+14
For historical reasons, the exact rename detection had populated the filespecs for the entries it compared, and the rest of the similarity analysis depended on that. I hadn't even bothered to debug why that was the case when I re-did the rename detection, I just made the new one have the same broken behaviour, with a note about this special case. This fixes that fixme. The reason the exact rename detector needed to fill in the file sizes of the files it checked was that the _inexact_ rename detector was broken, and started comparing file sizes before it filled them in. Fixing that allows the exact phase to do the sane thing of never even caring (since all *it* cares about is really just the SHA1 itself, not the size nor the contents). It turns out that this also indirectly fixes a bug: trying to populate all the filespecs will run out of virtual memory if there is tons and tons of possible rename options. The fuzzy similarity analysis does the right thing in this regard, and free's the blob info after it has generated the hash tables, so the special case code caused more trouble than just some extra illogical code. Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-10-26Do exact rename detection regardless of rename limitsLibravatar Linus Torvalds1-6/+6
Now that the exact rename detection is linear-time (with a very small constant factor to boot), there is no longer any reason to limit it by the number of files involved. In some trivial testing, I created a repository with a directory that had a hundred thousand files in it (all with different contents), and then moved that directory to show the effects of renaming 100,000 files. With the new code, that resulted in [torvalds@woody big-rename]$ time ~/git/git show -C | wc -l 400006 real 0m2.071s user 0m1.520s sys 0m0.576s ie the code can correctly detect the hundred thousand renames in about 2 seconds (the number "400006" comes from four lines for each rename: diff --git a/really-big-dir/file-1-1-1-1-1 b/moved-big-dir/file-1-1-1-1-1 similarity index 100% rename from really-big-dir/file-1-1-1-1-1 rename to moved-big-dir/file-1-1-1-1-1 and the extra six lines is from a one-liner commit message and all the commit information and spacing). Most of those two seconds weren't even really the rename detection, it's really all the other stuff needed to get there. With the old code, this wouldn't have been practically possible. Doing a pairwise check of the ten billion possible pairs would have been prohibitively expensive. In fact, even with the rename limiter in place, the old code would waste a lot of time just on the diff_filespec checks, and despite not even trying to find renames, it used to look like: [torvalds@woody big-rename]$ time git show -C | wc -l 1400006 real 0m12.337s user 0m12.285s sys 0m0.192s ie we used to take 12 seconds for this load and not even do any rename detection! (The number 1400006 comes from fourteen lines per file moved: seven lines each for the delete and the create of a one-liner file, and the same extra six lines of commit information). Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-10-26Do linear-time/space rename logic for exact renamesLibravatar Linus Torvalds1-63/+148
This implements a smarter rename detector for exact renames, which rather than doing a pairwise comparison (time O(m*n)) will just hash the files into a hash-table (size O(n+m)), and only do pairwise comparisons to renames that have the same hash (time O(n+m) except for unrealistic hash collissions, which we just cull aggressively). Admittedly the exact rename case is not nearly as interesting as the generic case, but it's an important case none-the-less. A similar general approach should work for the generic case too, but even then you do need to handle the exact renames/copies separately (to avoid the inevitable added cost factor that comes from the _size_ of the file), so this is worth doing. In the expectation that we will indeed do the same hashing trick for the general rename case, this code uses a generic hash-table implementation that can be used for other things too. In fact, we might be able to consolidate some of our existing hash tables with the new generic code in hash.[ch]. Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-10-26copy vs rename detection: avoid unnecessary O(n*m) loopsLibravatar Linus Torvalds1-51/+17
The core rename detection had some rather stupid code to check if a pathname was used by a later modification or rename, which basically walked the whole pathname space for all renames for each rename, in order to tell whether it was a pure rename (no remaining users) or should be considered a copy (other users of the source file remaining). That's really silly, since we can just keep a count of users around, and replace all those complex and expensive loops with just testing that simple counter (but this all depends on the previous commit that shared the diff_filespec data structure by using a separate reference count). Note that the reference count is not the same as the rename count: they behave otherwise rather similarly, but the reference count is tied to the allocation (and decremented at de-allocation, so that when it turns zero we can get rid of the memory), while the rename count is tied to the renames and is decremented when we find a rename (so that when it turns zero we know that it was a rename, not a copy). Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-10-26Ref-count the filespecs used by diffcoreLibravatar Linus Torvalds1-10/+6
Rather than copy the filespecs when introducing new versions of them (for rename or copy detection), use a refcount and increment the count when reusing the diff_filespec. This avoids unnecessary allocations, but the real reason behind this is a future enhancement: we will want to track shared data across the copy/rename detection. In order to efficiently notice when a filespec is used by a rename, the rename machinery wants to keep track of a rename usage count which is shared across all different users of the filespec. Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-10-26Split out "exact content match" phase of rename detectionLibravatar Linus Torvalds1-34/+56
This makes the exact content match a separate function of its own. Partly to cut down a bit on the size of the diffcore_rename() function (which is too complex as it is), and partly because there are smarter ways to do this than an O(m*n) loop over it all, and that function should be rewritten to take that into account. Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-10-02rename diff_free_filespec_data_large() to diff_free_filespec_blob()Libravatar Junio C Hamano1-2/+2
Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-10-02diffcore-rename: cache file deltasLibravatar Jeff King1-3/+4
We find rename candidates by computing a fingerprint hash of each file, and then comparing those fingerprints. There are inherently O(n^2) comparisons, so it pays in CPU time to hoist the (rather expensive) computation of the fingerprint out of that loop (or to cache it once we have computed it once). Previously, we didn't keep the filespec information around because then we had the potential to consume a great deal of memory. However, instead of keeping all of the filespec data, we can instead just keep the fingerprint. This patch implements and uses diff_free_filespec_data_large to accomplish that goal. We also have to change estimate_similarity not to needlessly repopulate the filespec data when we already have the hash. Practical tests showed 4.5x speedup for a 10% memory usage increase. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-09-14Fix the rename detection limit checkingLibravatar Linus Torvalds1-2/+17
This adds more proper rename detection limits. Instead of just checking the limit against the number of potential rename destinations, we verify that the rename matrix (which is what really matters) doesn't grow ridiculously large, and we also make sure that we don't overflow when doing the matrix size calculation. This also changes the default limits from unlimited, to a rename matrix that is limited to 100 entries on a side. You can raise it with the config entry, or by using the "-l<n>" command line flag, but at least the default is now a sane number that avoids spending lots of time (and memory) in situations that likely don't merit it. The choice of default value is of course very debatable. Limiting the rename matrix to a 100x100 size will mean that even if you have just one obvious rename, but you also create (or delete) 10,000 files, the rename matrix will be so big that we disable the heuristics. Sounds reasonable to me, but let's see if people hit this (and, perhaps more importantly, actually *care*) in real life. Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-07-02Merge branch 'jc/diffcore'Libravatar Junio C Hamano1-2/+1
* jc/diffcore: diffcore-delta.c: Ignore CR in CRLF for text files diffcore-delta.c: update the comment on the algorithm. diffcore_filespec: add is_binary diffcore_count_changes: pass diffcore_filespec
2007-06-30diffcore_count_changes: pass diffcore_filespecLibravatar Junio C Hamano1-2/+1
We may want to use richer information on the data we are dealing with in this function, so instead of passing a buffer address and length, just pass the diffcore_filespec structure. Existing callers always call this function with parameters taken from a filespec anyway, so there is no functionality changes. Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-06-24diffcore-rename: don't change similarity index based on basename equalityLibravatar René Scharfe1-4/+7
This implements a suggestion from Johannes. It uses a separate field in struct diff_score to keep the result of the file name comparison in the rename detection logic. This reverts the value of the similarity index to be a function of file contents, only, and basename comparison is only used to decide between files with equal amounts of content changes. Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-06-22diffcore-rename: favour identical basenamesLibravatar Johannes Schindelin1-1/+32
When there are several candidates for a rename source, and one of them has an identical basename to the rename target, take that one. Noticed by Govind Salinas, posted by Shawn O. Pearce, partial patch by Linus Torvalds. Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-05-07diff -M: release the preimage candidate blobs after rename detection.Libravatar Junio C Hamano1-0/+1
We released the postimage candidate blobs after we are done to reduce memory pressure. Do the same for preimage candidate blobs. Signed-off-by: Junio C Hamano <junkio@cox.net>
2007-03-07Cast 64 bit off_t to 32 bit size_tLibravatar Shawn O. Pearce1-3/+4
Some systems have sizeof(off_t) == 8 while sizeof(size_t) == 4. This implies that we are able to access and work on files whose maximum length is around 2^63-1 bytes, but we can only malloc or mmap somewhat less than 2^32-1 bytes of memory. On such a system an implicit conversion of off_t to size_t can cause the size_t to wrap, resulting in unexpected and exciting behavior. Right now we are working around all gcc warnings generated by the -Wshorten-64-to-32 option by passing the off_t through xsize_t(). In the future we should make xsize_t on such problematic platforms detect the wrapping and die if such a file is accessed. Signed-off-by: Shawn O. Pearce <spearce@spearce.org> Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-12-14Bypass expensive content comparsion during rename detection.Libravatar Shawn O. Pearce1-0/+2
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: Shawn O. Pearce <spearce@spearce.org> Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-11-04git-pickaxe: rename detection optimizationLibravatar Junio C Hamano1-1/+5
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: Junio C Hamano <junkio@cox.net>
2006-08-17Do not use memcmp(sha1_1, sha1_2, 20) with hardcoded length.Libravatar David Rientjes1-1/+1
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: Alex Riesen <raa.lkml@gmail.com> Signed-off-by: David Rientjes <rientjes@google.com> Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-08-03diff.c: do not use pathname comparison to tell renamesLibravatar Junio C Hamano1-0/+1
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: Junio C Hamano <junkio@cox.net>
2006-07-06diffcore-rename: try matching up renames without populating filespec first.Libravatar Junio C Hamano1-11/+22
Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-04-08diffcore-rename: fix merging back a broken pair.Libravatar Junio C Hamano1-4/+10
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: Junio C Hamano <junkio@cox.net>
2006-03-12Fix up diffcore-rename scoringLibravatar Linus Torvalds1-7/+5
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: Linus Torvalds <torvalds@osdl.org> Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-03-12diffcore-delta: make the hash a bit denser.Libravatar Junio C Hamano1-2/+2
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: Junio C Hamano <junkio@cox.net>
2006-03-12diffcore-rename: somewhat optimized.Libravatar Junio C Hamano1-0/+3
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: Junio C Hamano <junkio@cox.net>
2006-03-02diffcore-rename: similarity estimator fix.Libravatar Junio C Hamano1-12/+8
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: Junio C Hamano <junkio@cox.net>
2006-02-28diffcore-rename: split out the delta counting code.Libravatar Junio C Hamano1-23/+5
This is to rework diffcore break/rename/copy detection code so that it does not affected when deltifier code gets improved. Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-02-22diffcore-rename: plug memory leak.Libravatar Junio C Hamano1-1/+3
Spotted by Nicolas Pitre. Signed-off-by: Junio C Hamano <junkio@cox.net>
2005-12-26short circuit out of a few places where we would allocate zero bytesLibravatar Eric Wong1-1/+1
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: Eric Wong <normalperson@yhbt.net> Signed-off-by: Junio C Hamano <junkio@cox.net>
2005-11-21rename detection with -M100 means "exact renames only".Libravatar Junio C Hamano1-0/+3
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: Junio C Hamano <junkio@cox.net>
2005-11-15diff: make default rename detection limit configurable.Libravatar Junio C Hamano1-1/+1
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: Junio C Hamano <junkio@cox.net>
2005-09-24Diff: -l<num> to limit rename/copy detection.Libravatar Junio C Hamano1-2/+6
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: Junio C Hamano <junkio@cox.net>
2005-09-15Plug diff leaks.Libravatar Junio C Hamano1-24/+32
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: Junio C Hamano <junkio@cox.net>
2005-09-10Fix copy marking from diffcore-rename.Libravatar Junio C Hamano1-4/+36
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: Junio C Hamano <junkio@cox.net>
2005-06-28[PATCH] Use enhanced diff_delta() in the similarity estimator.Libravatar Junio C Hamano1-1/+6
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: Junio C Hamano <junkio@cox.net> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-06-25Add a "max_size" parameter to diff_delta()Libravatar Linus Torvalds1-1/+1
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.
2005-06-12[PATCH] Fix rename/copy when dealing with temporarily broken pairs.Libravatar Junio C Hamano1-2/+8
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: Junio C Hamano <junkio@cox.net> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-06-03[PATCH] diff: Clean up diff_scoreopt_parse().Libravatar Junio C Hamano1-18/+0
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: Junio C Hamano <junkio@cox.net> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-06-03[PATCH] Tweak count-delta interfaceLibravatar Junio C Hamano1-4/+11
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: Junio C Hamano <junkio@cox.net> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-05-30[PATCH] Add -B flag to diff-* brothers.Libravatar Junio C Hamano1-13/+32
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: Junio C Hamano <junkio@cox.net> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-05-30[PATCH] diff: fix the culling of unneeded delete record.Libravatar Junio C Hamano1-11/+33
The commit 15d061b435a7e3b6bead39df3889f4af78c4b00a [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: Junio C Hamano <junkio@cox.net> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-05-30[PATCH] diff: code clean-up and removal of rename hack.Libravatar Junio C Hamano1-1/+1
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: Junio C Hamano <junkio@cox.net> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-05-29[PATCH] Optimize diff-tree -[CM] --stdinLibravatar Junio C Hamano1-5/+14
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: Junio C Hamano <junkio@cox.net> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-05-29[PATCH] Fix the way diffcore-rename records unremoved source.Libravatar Junio C Hamano1-39/+24
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: Junio C Hamano <junkio@cox.net> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-05-29[PATCH] Remove unused rank field from diff_core structure.Libravatar Junio C Hamano1-1/+0
This removes a field that is no longer used from diff_score structure. Signed-off-by: Junio C Hamano <junkio@cox.net> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-05-29[PATCH] Introduce diff_free_filepair() funcion.Libravatar Junio C Hamano1-5/+2
This introduces a new function to free a common data structure, and plugs some leaks. Signed-off-by: Junio C Hamano <junkio@cox.net> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-05-29[PATCH] Fix math thinko in similarity estimator.Libravatar Junio C Hamano1-1/+1
The math to reject delta that is too big was confused. Signed-off-by: Junio C Hamano <junkio@cox.net> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-05-24[PATCH] Update rename/copy similarity estimator.Libravatar Junio C Hamano1-5/+11
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: Junio C Hamano <junkio@cox.net> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-05-24[PATCH] Redo rename/copy detection logic.Libravatar Junio C Hamano1-204/+181
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: Junio C Hamano <junkio@cox.net> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-05-23[PATCH] Fix diff-pruning logic which was running prune too early.Libravatar Junio C Hamano1-23/+2
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: Junio C Hamano <junkio@cox.net> Signed-off-by: Linus Torvalds <torvalds@osdl.org>