user/sven/git.git/diffcore-rename.c, branch v1.7.3.5

Add a macro DIFF_QUEUE_CLEAR.

2010-05-07T16:34:27Z

Refactor the diff_queue_struct code, this macro help to reset the structure. Signed-off-by: Bo Yang Signed-off-by: Junio C Hamano

diffcore-rename: reduce memory footprint by freeing blob data early

2009-11-21T06:13:47Z

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

Fix typos / spelling in comments

2009-04-23T02:02:12Z

Signed-off-by: Mike Ralphson Signed-off-by: Junio C Hamano

Rename detection: Avoid repeated filespec population

2009-01-21T08:14:12Z

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 Signed-off-by: Junio C Hamano

Add file delete/create info when we overflow rename_limit

2008-10-28T15:58:42Z

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 Signed-off-by: Junio C Hamano

diff: make "too many files" rename warning optional

2008-05-03T20:40:43Z

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 Signed-off-by: Junio C Hamano

Merge branch 'jc/rename'

2008-04-09T08:09:12Z

* 'jc/rename' (early part): Optimize rename detection for a huge diff

rename: warn user when we have turned off rename detection

2008-03-01T09:30:15Z

Signed-off-by: Jeff King Signed-off-by: Junio C Hamano

Optimize rename detection for a huge diff

2008-02-13T23:44:20Z

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 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

Fix a pathological case in git detecting proper renames

2007-11-30T23:49:17Z

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