Re: Fix a pathological case in git detecting proper renames

On Nov 29, 2007, at 6:41 PM, Linus Torvalds wrote:

On Thu, 29 Nov 2007, Jeff King wrote:

quoted

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.

Glad I can be of use for something :)

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.

Yeah both of these dawned on me after my brain started working and  
thinking about what you were talking about when you say git manages  
'content' and thinking about how the content management correlates to  
the diffs we generate.

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

Only started using -M when a co-worker informed me about it.  But if I  
see other cases in the future I'll let you guys know.

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.

Much better.  I love with open source development works.

- k