diff --git a/board/cds/mpc8541cds/u-boot.lds b/board/freescale/mpc8555cds/u-boot.ldssimilarity index 97%rename from board/cds/mpc8541cds/u-boot.ldsrename to board/freescale/mpc8555cds/u-boot.ldsindex 7a5daef..df21ea8 100644--- a/board/cds/mpc8541cds/u-boot.lds+++ b/board/freescale/mpc8555cds/u-boot.lds
I did some git-mv and got the following:
the problem is git seems confused about what file was associated with its
source.
Well, I wouldn't say "confused". It found multiple identical options for
the source, and picked the first one (where "first one" may not be obvious
to a human, it can depend on an internal hash order).
But if you have the resultant git tree somewhere public (or just send me
the exact "git mv" and revision to recreate), I'll happily give it a look,
to see if we can improve our heuristics to be closer to what a human would
expect.
For example, in this case, it looks like there were two totally identical
"init.S" files that got renamed with the same identical content to two new
names. YOU seem to expect that it would stay as two renames, but from a
content angle, since the two sources were identical, it's a totally
arbitrary choice whether it's a "copy one source to two destinations and
delete the other source" or whether it's two cases of "move one source to
another destination" (and the latter case also has the issue of which way
to move it).
(You also had two identical Makefile's with the exact same issue).
So git doesn't care about how you did the rename, it only cares about the
end result, and the exact same way that it will detect a rename if you
implement it as a "copy file" and then a later "delete old file", it will
also potentially go the other way, or just decide that identical contents
moved in different ways.
But we can certainly tweak the heuristics. For example, if we find
multiple identical renames, right now we just pick one fairly at random,
and have no logic to prefer independent renames over "multiple copies and
a delete". But this code is actually fairly simple, and with a good
example I can easily add heurstics (for example, it probably *is* better
to consider it to be two renames, just because the resulting diff will be
smaller - since a "delete" diff is much larger than a rename diff).
Linus
From: Kumar Gala <hidden> Date: 2016-06-15 22:43:55
On Nov 29, 2007, at 11:44 AM, Linus Torvalds wrote:
On Thu, 29 Nov 2007, Kumar Gala wrote:
quoted
I did some git-mv and got the following:
the problem is git seems confused about what file was associated
with its
source.
Well, I wouldn't say "confused". It found multiple identical options
for
the source, and picked the first one (where "first one" may not be
obvious
to a human, it can depend on an internal hash order).
But if you have the resultant git tree somewhere public (or just
send me
the exact "git mv" and revision to recreate), I'll happily give it a
look,
to see if we can improve our heuristics to be closer to what a human
would
expect.
For example, in this case, it looks like there were two totally
identical
"init.S" files that got renamed with the same identical content to
two new
names. YOU seem to expect that it would stay as two renames, but
from a
content angle, since the two sources were identical, it's a totally
arbitrary choice whether it's a "copy one source to two destinations
and
delete the other source" or whether it's two cases of "move one
source to
another destination" (and the latter case also has the issue of
which way
to move it).
(You also had two identical Makefile's with the exact same issue).
So git doesn't care about how you did the rename, it only cares
about the
end result, and the exact same way that it will detect a rename if you
implement it as a "copy file" and then a later "delete old file", it
will
also potentially go the other way, or just decide that identical
contents
moved in different ways.
I was guessing most of this but wanted to make sure there wasn't some
cool feature of git I wasn't aware of.
But we can certainly tweak the heuristics. For example, if we find
multiple identical renames, right now we just pick one fairly at
random,
and have no logic to prefer independent renames over "multiple
copies and
a delete". But this code is actually fairly simple, and with a good
example I can easily add heurstics (for example, it probably *is*
better
to consider it to be two renames, just because the resulting diff
will be
smaller - since a "delete" diff is much larger than a rename diff).
In the case of multiple identical matches can we look at the file name
as a possible heuristic?
- k
In the case of multiple identical matches can we look at the file name as a
possible heuristic?
We already do. But we only do the base-name part and check it for
exactness, since moving across directories is very common, and we
explicitly want to pick up files that have the same base name.
However, in your case, not only did you have the same content, you had the
same basename too! So git considered your renames to be totally identical
wrt scoring with the current heuristics, and just picked one source at
random.
And the current heuristics don't even have any "if you already found a
rename, avoid picking the same one twice", so it would pick the *same*
source both times, which is why it looked like "two copies and one
delete".
This is why I'd like to have a real-life example. I can change the
heuristics, and I even know what are likely to be better heuristics, but I
still want to actually see and play with an example so that when I send
Junio a patch, I can explain it and say I've tested it with something
real..
Linus
From: Kumar Gala <hidden> Date: 2016-06-15 22:43:55
On Nov 29, 2007, at 1:27 PM, Linus Torvalds wrote:
On Thu, 29 Nov 2007, Kumar Gala wrote:
quoted
In the case of multiple identical matches can we look at the file
name as a
possible heuristic?
We already do. But we only do the base-name part and check it for
exactness, since moving across directories is very common, and we
explicitly want to pick up files that have the same base name.
However, in your case, not only did you have the same content, you
had the
same basename too! So git considered your renames to be totally
identical
wrt scoring with the current heuristics, and just picked one source at
random.
And the current heuristics don't even have any "if you already found a
rename, avoid picking the same one twice", so it would pick the *same*
source both times, which is why it looked like "two copies and one
delete".
This is why I'd like to have a real-life example. I can change the
heuristics, and I even know what are likely to be better heuristics,
but I
still want to actually see and play with an example so that when I
send
Junio a patch, I can explain it and say I've tested it with something
real..
Ok, this is a real example from the u-boot tree. If you give me a
little while I can point you at a kernel.org git tree that showed this
issue.
- k
From: Kumar Gala <hidden> Date: 2016-06-15 22:43:55
This is why I'd like to have a real-life example. I can change the
heuristics, and I even know what are likely to be better heuristics,
but I
still want to actually see and play with an example so that when I
send
Junio a patch, I can explain it and say I've tested it with something
real..
Ok, here's the tree:
git.kernel.org:/pub/scm/boot/u-boot/galak/u-boot.git linus_git
and the commit that is doing the file movement is:
ba30ae3cc2e92d4b2362fbc01bedb659615e123e
let me know if there is anything else you need.
- k
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>
---
On Thu, 29 Nov 2007, Kumar Gala wrote:
let me know if there is anything else you need.
No, this was all right, and I've already got a patch ready for you to try.
So this patch actually does do what you want (for the exact renames, if
not for the u-boot.lds file), but I wanted to just point out that we will
almost certainly at least want to extend it to the inexact rename
detection logic too, _and_ we may well want to make the "score"
calculation a bit more involved depending on the actual filename, rather
than just depend on the equality of the basename.
Linus
---
diffcore-rename.c | 25 ++++++++++++++++---------
1 files changed, 16 insertions(+), 9 deletions(-)
@@ -244,28 +244,35 @@ static int find_identical_files(struct file_similarity *src,*Walkoverallthedestinations...*/do{-structdiff_filespec*one=dst->filespec;+structdiff_filespec*target=dst->filespec;structfile_similarity*p,*best;-inti=100;+inti=100,best_score=-1;/**..tofindthebestsourcematch*/best=NULL;for(p=src;p;p=p->next){-structdiff_filespec*two=p->filespec;+intscore;+structdiff_filespec*source=p->filespec;/* False hash collission? */-if(hashcmp(one->sha1,two->sha1))+if(hashcmp(source->sha1,target->sha1))continue;/* Non-regular files? If so, the modes must match! */-if(!S_ISREG(one->mode)||!S_ISREG(two->mode)){-if(one->mode!=two->mode)+if(!S_ISREG(source->mode)||!S_ISREG(target->mode)){+if(source->mode!=target->mode)continue;}-best=p;-if(basename_same(one,two))-break;+/* Give higher scores to sources that haven't been used already */+score=!source->rename_used;+score+=basename_same(source,target);+if(score>best_score){+best=p;+best_score=score;+if(score==2)+break;+}/* Too many identical alternatives? Pick one */if(!--i)
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.
Side note: just in case people were expecting me to actually _ship_ that
separate patch that handles the fuzzy matches too.. I wasn't planning on
doing that patch. The way the fuzzy rename detection is currently done,
that's actually quite painful.
For the fuzzy rename detection, we generate the full score matrix, and
sort it by the score, up front. So all the scoring - and more importantly,
all the sorting - has actually been done before we actually start looking
at *any* renames at all, so we cannot easily do the same thing I did for
the exact renames, namely to take into account _earlier_ renames in the
scoring. Because those earlier renames have simply not been done when the
score is calculated.
This would probably become easier to do with the linear-time hash-based
similarity engine (the stuff Jeff King was working on), but the way the
code is currently structured - with no incremental rename detection at
all, and with all the scoring in one global table - it's pretty painful.
Linus
From: Jeff King <hidden> Date: 2016-06-15 22:43:55
On Thu, Nov 29, 2007 at 03:03:06PM -0800, Linus Torvalds wrote:
This would probably become easier to do with the linear-time hash-based
similarity engine (the stuff Jeff King was working on), but the way the
code is currently structured - with no incremental rename detection at
all, and with all the scoring in one global table - it's pretty painful.
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.
-Peff
From: Jakub Narebski <hidden> Date: 2016-06-15 22:43:55
Linus Torvalds wrote:
On Thu, 29 Nov 2007, Kumar Gala wrote:
quoted
I did some git-mv and got the following:
the problem is git seems confused about what file was associated with its
source.
Well, I wouldn't say "confused". It found multiple identical options for
the source, and picked the first one (where "first one" may not be obvious
to a human, it can depend on an internal hash order).
By the way, which git version do you use? IIRC we have improved rename
detection heuristics to take into account similarity of filenames when
contents is identical...
...ah, I see, it is git 1.5.3.4
--
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git
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
---
diffcore-rename.c | 13 +++++++++++++
1 files changed, 13 insertions(+), 0 deletions(-)
@@ -497,6 +497,19 @@ void diffcore_rename(struct diff_options *options)qsort(mx,num_create*num_src,sizeof(*mx),score_compare);for(i=0;i<num_create*num_src;i++){structdiff_rename_dst*dst=&rename_dst[mx[i].dst];+structdiff_filespec*src;+if(dst->pair)+continue;/* already done, either exact or fuzzy. */+if(mx[i].score<minimum_score)+break;/* there is no more usable pair. */+src=rename_src[mx[i].src].one;+if(src->rename_used)+continue;+record_rename_pair(mx[i].dst,mx[i].src,mx[i].score);+rename_count++;+}+for(i=0;i<num_create*num_src;i++){+structdiff_rename_dst*dst=&rename_dst[mx[i].dst];if(dst->pair)continue;/* already done, either exact or fuzzy. */if(mx[i].score<minimum_score)
From: Jeff King <hidden> Date: 2016-06-15 22:43:55
On Thu, Nov 29, 2007 at 04:41:09PM -0800, Linus Torvalds wrote:
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.
I think the slowdown is a non-issue. From the benchmarking I did in the
past, all of the time was spent _before_ even getting to the qsort of
scores. So even if you doubled the expense of that loop, it would have a
negligible impact.
But I haven't actually benchmarked this new patch, of course.
-Peff
From: Kumar Gala <hidden> Date: 2016-06-15 22:43:55
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.