summaryrefslogtreecommitdiff
path: root/diffcore-rename.c
AgeCommit message (Collapse)AuthorFilesLines
2014-03-18Merge branch 'dd/use-alloc-grow'Libravatar Junio C Hamano1-10/+2
Replace open-coded reallocation with ALLOC_GROW() macro. * dd/use-alloc-grow: sha1_file.c: use ALLOC_GROW() in pretend_sha1_file() read-cache.c: use ALLOC_GROW() in add_index_entry() builtin/mktree.c: use ALLOC_GROW() in append_to_tree() attr.c: use ALLOC_GROW() in handle_attr_line() dir.c: use ALLOC_GROW() in create_simplify() reflog-walk.c: use ALLOC_GROW() replace_object.c: use ALLOC_GROW() in register_replace_object() patch-ids.c: use ALLOC_GROW() in add_commit() diffcore-rename.c: use ALLOC_GROW() diff.c: use ALLOC_GROW() commit.c: use ALLOC_GROW() in register_commit_graft() cache-tree.c: use ALLOC_GROW() in find_subtree() bundle.c: use ALLOC_GROW() in add_to_ref_list() builtin/pack-objects.c: use ALLOC_GROW() in check_pbase_path()
2014-03-14Merge branch 'nd/i18n-progress'Libravatar Junio C Hamano1-1/+1
Mark the progress indicators from various time-consuming commands for i18n/l10n. * nd/i18n-progress: i18n: mark all progress lines for translation
2014-03-03diffcore-rename.c: use ALLOC_GROW()Libravatar Dmitry S. Dolzhenko1-10/+2
Use ALLOC_GROW() instead of open-coding it in locate_rename_dst() and register_rename_src(). Signed-off-by: Dmitry S. Dolzhenko <dmitrys.dolzhenko@yandex.ru> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-02-24i18n: mark all progress lines for translationLibravatar Nguyễn Thái Ngọc Duy1-1/+1
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2013-11-18diffcore-rename.c: use new hash map implementationLibravatar Karsten Blees1-35/+13
Signed-off-by: Karsten Blees <blees@dcon.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2013-11-18diffcore-rename.c: simplify finding exact renamesLibravatar Karsten Blees1-55/+20
The find_exact_renames function currently only uses the hash table for grouping, i.e.: 1. add sources 2. add destinations 3. iterate all buckets, per bucket: 4. split sources from destinations 5. iterate destinations, per destination: 6. iterate sources to find best match This can be simplified by utilizing the lookup functionality of the hash table, i.e.: 1. add sources 2. iterate destinations, per destination: 3. lookup sources matching the current destination 4. iterate sources to find best match This saves several iterations and file_similarity allocations for the destinations. Signed-off-by: Karsten Blees <blees@dcon.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2013-11-18diffcore-rename.c: move code around to prepare for the next patchLibravatar Karsten Blees1-49/+49
No actual code changes, just move hash_filespec up and outdent part of find_identical_files. Signed-off-by: Karsten Blees <blees@dcon.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2013-03-16Preallocate hash tables when the number of inserts are known in advanceLibravatar Nguyễn Thái Ngọc Duy1-0/+1
This avoids unnecessary re-allocations and reinsertions. On webkit.git (i.e. about 182k inserts to the name hash table), this reduces about 100ms out of 3s user time. Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2012-08-27Merge branch 'jk/maint-null-in-trees'Libravatar Junio C Hamano1-1/+1
We do not want a link to 0{40} object stored anywhere in our objects. * jk/maint-null-in-trees: fsck: detect null sha1 in tree entries do not write null sha1s to on-disk index diff: do not use null sha1 as a sentinel value
2012-07-29diff: do not use null sha1 as a sentinel valueLibravatar Jeff King1-1/+1
The diff code represents paths using the diff_filespec struct. This struct has a sha1 to represent the sha1 of the content at that path, as well as a sha1_valid member which indicates whether its sha1 field is actually useful. If sha1_valid is not true, then the filespec represents a working tree file (e.g., for the no-index case, or for when the index is not up-to-date). The diff_filespec is only used internally, though. At the interfaces to the diff subsystem, callers feed the sha1 directly, and we create a diff_filespec from it. It's at that point that we look at the sha1 and decide whether it is valid or not; callers may pass the null sha1 as a sentinel value to indicate that it is not. We should not typically see the null sha1 coming from any other source (e.g., in the index itself, or from a tree). However, a corrupt tree might have a null sha1, which would cause "diff --patch" to accidentally diff the working tree version of a file instead of treating it as a blob. This patch extends the edges of the diff interface to accept a "sha1_valid" flag whenever we accept a sha1, and to use that flag when creating a filespec. In some cases, this means passing the flag through several layers, making the code change larger than would be desirable. One alternative would be to simply die() upon seeing corrupted trees with null sha1s. However, this fix more directly addresses the problem (while bogus sha1s in a tree are probably a bad thing, it is really the sentinel confusion sending us down the wrong code path that is what makes it devastating). And it means that git is more capable of examining and debugging these corrupted trees. For example, you can still "diff --raw" such a tree to find out when the bogus entry was introduced; you just cannot do a "--patch" diff (just as you could not with any other corrupted tree, as we do not have any content to diff). Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2012-03-23teach diffcore-rename to optionally ignore empty contentLibravatar Jeff King1-0/+6
Our rename detection is a heuristic, matching pairs of removed and added files with similar or identical content. It's unlikely to be wrong when there is actual content to compare, and we already take care not to do inexact rename detection when there is not enough content to produce good results. However, we always do exact rename detection, even when the blob is tiny or empty. It's easy to get false positives with an empty blob, simply because it is an obvious content to use as a boilerplate (e.g., when telling git that an empty directory is worth tracking via an empty .gitignore). This patch lets callers specify whether or not they are interested in using empty files as rename sources and destinations. The default is "yes", keeping the original behavior. It works by detecting the empty-blob sha1 for rename sources and destinations. One more flexible alternative would be to allow the caller to specify a minimum size for a blob to be "interesting" for rename detection. But that would catch small boilerplate files, not large ones (e.g., if you had the GPL COPYING file in many directories). A better alternative would be to allow a "-rename" gitattribute to allow boilerplate files to be marked as such. I'll leave the complexity of that solution until such time as somebody actually wants it. The complaints we've seen so far revolve around empty files, so let's start with the simple thing. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2011-05-02Merge branch 'mz/maint-rename-unmerged'Libravatar Junio C Hamano1-2/+5
* mz/maint-rename-unmerged: diffcore-rename: don't consider unmerged path as source
2011-04-29diffcore-rename.c: avoid set-but-not-used warningLibravatar Jim Meyering1-2/+1
Since 9d8a5a5 (diffcore-rename: refactor "too many candidates" logic, 2011-01-06), diffcore_rename() initializes num_src but does not use it anymore. "-Wunused-but-set-variable" in gcc-4.6 complains about this. Signed-off-by: Jim Meyering <meyering@redhat.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2011-03-23diffcore-rename: don't consider unmerged path as sourceLibravatar Martin von Zweigbergk1-2/+5
Since e9c8409 (diff-index --cached --raw: show tree entry on the LHS for unmerged entries., 2007-01-05), an unmerged entry should be detected by using DIFF_PAIR_UNMERGED(p), not by noticing both one and two sides of the filepair records mode=0 entries. However, it forgot to update some parts of the rename detection logic. This only makes difference in the "diff --cached" codepath where an unmerged filepair carries information on the entries that came from the tree. It probably hasn't been noticed for a long time because nobody would run "diff -M" during a conflict resolution, but "git status" uses rename detection when it internally runs "diff-index" and "diff-files" and gives nonsense results. In an unmerged pair, "one" side can have a valid filespec to record the tree entry (e.g. what's in HEAD) when running "diff --cached". This can be used as a rename source to other paths in the index that are not unmerged. The path that is unmerged by definition does not have the final content yet (i.e. "two" side cannot have a valid filespec), so it can never be a rename destination. Use the DIFF_PAIR_UNMERGED() to detect unmerged filepair correctly, and allow the valid "one" side of an unmerged filepair to be considered a potential rename source, but never to be considered a rename destination. Commit message and first two test cases by Junio, the rest by Martin. Signed-off-by: Martin von Zweigbergk <martin.von.zweigbergk@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2011-03-22diffcore-rename: fall back to -C when -C -C busts the rename limitLibravatar Junio C Hamano1-2/+36
When there are too many paths in the project, the number of rename source candidates "git diff -C -C" finds will exceed the rename detection limit, and no inexact rename detection is performed. We however could fall back to "git diff -C" if the number of modified paths is sufficiently small. Signed-off-by: Junio C Hamano <gitster@pobox.com>
2011-03-22diffcore-rename: record filepair for rename srcLibravatar Junio C Hamano1-11/+12
This will allow us to later skip unmodified entries added due to "-C -C". We might also want to do something similar to rename_dst side, but that would only be for the sake of symmetry and not necessary for this series. Signed-off-by: Junio C Hamano <gitster@pobox.com>
2011-03-22diffcore-rename: refactor "too many candidates" logicLibravatar Junio C Hamano1-18/+29
Move the logic to a separate function, to be enhanced by later patches in the series. While at it, swap the condition used in the if statement from "if it is too big then do this" to "if it would fit then do this". Signed-off-by: Junio C Hamano <gitster@pobox.com> --- Rebased to 'master' as the logic to use the result of this logic was updated recently, together with the addition of eye-candy.
2011-03-19Merge branch 'jk/merge-rename-ux'Libravatar Junio C Hamano1-2/+13
* jk/merge-rename-ux: pull: propagate --progress to merge merge: enable progress reporting for rename detection add inexact rename detection progress infrastructure commit: stop setting rename limit bump rename limit defaults (again) merge: improve inexact rename limit warning
2011-02-21add inexact rename detection progress infrastructureLibravatar Jeff King1-0/+10
We might spend many seconds doing inexact rename detection with no output. It's nice to let the user know that something is actually happening. This patch adds the infrastructure, but no callers actually turn on progress reporting. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2011-02-21merge: improve inexact rename limit warningLibravatar Jeff King1-2/+3
The warning is generated deep in the diffcore code, which means that it will come first, followed possibly by a spew of conflicts, making it hard to see. Instead, let's have diffcore pass back the information about how big the rename limit would needed to have been, and then the caller can provide a more appropriate message (and at a more appropriate time). No refactoring of other non-merge callers is necessary, because nobody else was even using the warn_on_rename_limit feature. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2011-02-18diffcore-rename: improve estimate_similarity() heuristicsLibravatar Linus Torvalds1-1/+1
The logic to quickly dismiss potential rename pairs was broken. It would too eagerly dismiss possible renames when all of the difference was due to pure new data (or deleted data). Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2011-02-18diffcore-rename: properly honor the difference between -M and -CLibravatar Linus Torvalds1-27/+26
We would allow rename detection to do copy detection even when asked purely for renames. That confuses users, but more importantly it can terminally confuse the recursive merge rename logic. Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2011-02-18for_each_hash: allow passing a 'void *data' pointer to callbackLibravatar Linus Torvalds1-6/+8
For the find_exact_renames() function, this allows us to pass the diff_options structure pointer to the low-level routines. We will use that to distinguish between the "rename" and "copy" cases. Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2010-05-07Add a macro DIFF_QUEUE_CLEAR.Libravatar Bo Yang1-2/+1
Refactor the diff_queue_struct code, this macro help to reset the structure. Signed-off-by: Bo Yang <struggleyb.nku@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2009-11-20diffcore-rename: reduce memory footprint by freeing blob data earlyLibravatar Junio C Hamano1-2/+5
After running one round of estimate_similarity(), filespecs on either side will have populated their cnt_data fields, and we do not need the blob text anymore. We used to retain the blob data to optimize for smaller projects (not freeing the blob data here would mean that the final output phase would not have to re-read it), but we are efficient enough without such optimization for smaller projects anyway, and freeing memory early will help larger projects. Signed-off-by: Junio C Hamano <gitster@pobox.com>
2009-04-22Fix typos / spelling in commentsLibravatar Mike Ralphson1-1/+1
Signed-off-by: Mike Ralphson <mike@abacus.co.uk> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2009-01-21Rename detection: Avoid repeated filespec populationLibravatar Björn Steinbrink1-2/+7
In diffcore_rename, we assume that the blob contents in the filespec aren't required anymore after estimate_similarity has been called and thus we free it. But estimate_similarity might return early when the file sizes differ too much. In that case, cnt_data is never set and the next call to estimate_similarity will populate the filespec again, eventually rereading the same blob over and over again. To fix that, we first get the blob sizes and only when the blob contents are actually required, and when cnt_data will be set, the full filespec is populated, once. Signed-off-by: Björn Steinbrink <B.Steinbrink@gmx.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2008-10-28Add file delete/create info when we overflow rename_limitLibravatar Linus Torvalds1-1/+1
When we refuse to do rename detection due to having too many files created or deleted, let the user know the numbers. That way there is a reasonable starting point for setting the diff.renamelimit option. Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2008-05-03diff: make "too many files" rename warning optionalLibravatar Jeff King1-1/+2
In many cases, the warning ends up as clutter, because the diff is being done "behind the scenes" from the user (e.g., when generating a commit diffstat), and whether we show renames or not is not particularly interesting to the user. However, in the case of a merge (which is what motivated the warning in the first place), it is a useful hint as to why a merge with renames might have failed. This patch makes the warning optional based on the code calling into diffcore. We default to not showing the warning, but turn it on for merges. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2008-04-09Merge branch 'jc/rename'Libravatar Junio C Hamano1-22/+58
* 'jc/rename' (early part): Optimize rename detection for a huge diff
2008-03-01rename: warn user when we have turned off rename detectionLibravatar Jeff King1-3/+4
Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2008-02-13Optimize rename detection for a huge diffLibravatar Junio C Hamano1-22/+58
When there are N deleted paths and M created paths, we used to allocate (N x M) "struct diff_score" that record how similar each of the pair is, and picked the <src,dst> pair that gives the best match first, and then went on to process worse matches. This sorting is done so that when two new files in the postimage that are similar to the same file deleted from the preimage, we can process the more similar one first, and when processing the second one, it can notice "Ah, the source I was planning to say I am a copy of is already taken by somebody else" and continue on to match itself with another file in the preimage with a lessor match. This matters to a change introduced between 1.5.3.X series and 1.5.4-rc, that lets the code to favor unused matches first and then falls back to using already used matches. This instead allocates and keeps only a handful rename source candidates per new files in the postimage. I.e. it makes the memory requirement from O(N x M) to O(M). For each dst, we compute similarlity with all sources (i.e. the number of similarity estimate computations is still O(N x M)), but we keep handful best src candidates for each dst. Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-11-30Fix a pathological case in git detecting proper renamesLibravatar Linus Torvalds1-0/+13
On Thu, 29 Nov 2007, Jeff King wrote: > > I think it will get worse, because you are simultaneously calculating > all of the similarity scores bit by bit rather than doing a loop. Though > perhaps you mean at the end you will end up with a list of src/dst pairs > sorted by score, and you can loop over that. Well, after thinking about this a bit, I think there's a solution that may work well with the current thing too: instead of looping just *once* over the list of rename pairs, loop twice - and simply refuse to do copies on the first loop. This trivial patch does that, and turns Kumar's test-case into a perfect rename list. It's not pretty, it's not smart, but it seems to work. There's something to be said for keeping it simple and stupid. And it should not be nearly as expensive as it may _look_. Yes, the loop is "(i = 0; i < num_create * num_src; i++)", but the important part is that the whole array is sorted by rename score, and we have a if (mx[i].score < minimum_score) break; in it, so uthe loop actually would tend to terminate rather quickly. Anyway, Kumar, the thing to take away from this is: - git really doesn't even *care* about the whole "rename detection" internally, and any commits you have done with renames are totally independent of the heuristics we then use to *show* the renames. - the rename detection really is for just two reasons: (a) keep humans happy, and keep the diffs small and (b) help automatic merging across renames. So getting renames right is certainly good, but it's more of a "politeness" issue than a "correctness" issue, although the merge portion of it does matter a lot sometimes. - the important thing here is that you can commit your changes and not worry about them being somehow "corrupted" by lack of rename detection, even if you commit them with a version of git that doesn't do rename detection the way you expected it. The rename detection is an "after-the-fact" thing, not something that actually gets saved in the repository, which is why we can change the heuristics _after_ seeing examples, and the examples magically correct themselves! - try out the two patches I've posted, and see if they work for you. They pass the test-suite, and the output for your example commit looks sane, but hey, if you have other test-cases, try them out. Here's Kumar's pretty diffstat with both my patches: Makefile | 6 +++--- board/{cds => freescale}/common/cadmus.c | 0 board/{cds => freescale}/common/cadmus.h | 0 board/{cds => freescale}/common/eeprom.c | 0 board/{cds => freescale}/common/eeprom.h | 0 board/{cds => freescale}/common/ft_board.c | 0 board/{cds => freescale}/common/via.c | 0 board/{cds => freescale}/common/via.h | 0 board/{cds => freescale}/mpc8541cds/Makefile | 0 board/{cds => freescale}/mpc8541cds/config.mk | 0 board/{cds => freescale}/mpc8541cds/init.S | 0 board/{cds => freescale}/mpc8541cds/mpc8541cds.c | 0 board/{cds => freescale}/mpc8541cds/u-boot.lds | 4 ++-- board/{cds => freescale}/mpc8548cds/Makefile | 0 board/{cds => freescale}/mpc8548cds/config.mk | 0 board/{cds => freescale}/mpc8548cds/init.S | 0 board/{cds => freescale}/mpc8548cds/mpc8548cds.c | 0 board/{cds => freescale}/mpc8548cds/u-boot.lds | 4 ++-- board/{cds => freescale}/mpc8555cds/Makefile | 0 board/{cds => freescale}/mpc8555cds/config.mk | 0 board/{cds => freescale}/mpc8555cds/init.S | 0 board/{cds => freescale}/mpc8555cds/mpc8555cds.c | 0 board/{cds => freescale}/mpc8555cds/u-boot.lds | 4 ++-- 23 files changed, 9 insertions(+), 9 deletions(-) and here it is before: Makefile | 6 +- board/cds/mpc8548cds/Makefile | 60 ----- board/cds/mpc8555cds/Makefile | 60 ----- board/cds/mpc8555cds/init.S | 255 -------------------- board/cds/mpc8555cds/u-boot.lds | 150 ------------ board/{cds => freescale}/common/cadmus.c | 0 board/{cds => freescale}/common/cadmus.h | 0 board/{cds => freescale}/common/eeprom.c | 0 board/{cds => freescale}/common/eeprom.h | 0 board/{cds => freescale}/common/ft_board.c | 0 board/{cds => freescale}/common/via.c | 0 board/{cds => freescale}/common/via.h | 0 board/{cds => freescale}/mpc8541cds/Makefile | 0 board/{cds => freescale}/mpc8541cds/config.mk | 0 board/{cds => freescale}/mpc8541cds/init.S | 0 board/{cds => freescale}/mpc8541cds/mpc8541cds.c | 0 board/{cds => freescale}/mpc8541cds/u-boot.lds | 4 +- .../mpc8541cds => freescale/mpc8548cds}/Makefile | 0 board/{cds => freescale}/mpc8548cds/config.mk | 0 board/{cds => freescale}/mpc8548cds/init.S | 0 board/{cds => freescale}/mpc8548cds/mpc8548cds.c | 0 board/{cds => freescale}/mpc8548cds/u-boot.lds | 4 +- .../mpc8541cds => freescale/mpc8555cds}/Makefile | 0 board/{cds => freescale}/mpc8555cds/config.mk | 0 .../mpc8541cds => freescale/mpc8555cds}/init.S | 0 board/{cds => freescale}/mpc8555cds/mpc8555cds.c | 0 .../mpc8541cds => freescale/mpc8555cds}/u-boot.lds | 4 +- 27 files changed, 9 insertions(+), 534 deletions(-) so it certainly makes the diffs prettier. Linus Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-11-30Fix a pathological case in git detecting proper renamesLibravatar Linus Torvalds1-9/+16
Kumar Gala had a case in the u-boot archive with multiple renames of files with identical contents, and git would turn those into multiple "copy" operations of one of the sources, and just deleting the other sources. This patch makes the git exact rename detection prefer to spread out the renames over the multiple sources, rather than do multiple copies of one source. NOTE! The changes are a bit larger than required, because I also renamed the variables named "one" and "two" to "target" and "source" respectively. That makes the logic easier to follow, especially as the "one" was illogically the target and not the soruce, for purely historical reasons (this piece of code used to traverse over sources and targets in the wrong order, and when we fixed that, we didn't fix the names back then. So I fixed them now). The important part of this change is just the trivial score calculations for when files have identical contents: /* Give higher scores to sources that haven't been used already */ score = !source->rename_used; score += basename_same(source, target); and when we have multiple choices we'll now pick the choice that gets the best rename score, rather than only looking at whether the basename matched. It's worth noting a few gotchas: - this scoring is currently only done for the "exact match" case. In particular, in Kumar's example, even after this patch, the inexact match case is still done as a copy+delete rather than as two renames: delete mode 100644 board/cds/mpc8555cds/u-boot.lds copy board/{cds => freescale}/mpc8541cds/u-boot.lds (97%) rename board/{cds/mpc8541cds => freescale/mpc8555cds}/u-boot.lds (97%) because apparently the "cds/mpc8541cds/u-boot.lds" copy looked a bit more similar to both end results. That said, I *suspect* we just have the exact same issue there - the similarity analysis just gave identical (or at least very _close_ to identical) similarity points, and we do not have any logic to prefer multiple renames over a copy/delete there. That is a separate patch. - When you have identical contents and identical basenames, the actual entry that is chosen is still picked fairly "at random" for the first one (but the subsequent ones will prefer entries that haven't already been used). It's not actually really random, in that it actually depends on the relative alphabetical order of the files (which in turn will have impacted the order that the entries got hashed!), so it gives consistent results that can be explained. But I wanted to point it out as an issue for when anybody actually does cross-renames. In Kumar's case the choice is the right one (and for a single normal directory rename it should always be, since the relative alphabetical sorting of the files will be identical), and we now get: rename board/{cds => freescale}/mpc8541cds/init.S (100%) rename board/{cds => freescale}/mpc8548cds/init.S (100%) which is the "expected" answer. However, it might still be better to change the pedantic "exact same basename" on/off choice into a more graduated "how similar are the pathnames" scoring situation, in order to be more likely to get the exact rename choice that people *expect* to see, rather than other alternatives that may *technically* be equally good, but are surprising to a human. It's also unclear whether we should consider "basenames are equal" or "have already used this as a source" to be more important. This gives them equal weight, but I suspect we might want to just multiple the "basenames are equal" weight by two, or something, to prefer equal basenames even if that causes a copy/delete pair. I dunno. Anyway, what I'm just saying in a really long-winded manner is that I think this is right as-is, but it's not the complete solution, and it may want some further tweaking in the future. Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
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>