{"thread":{"id":"31147","subject":"rename detection","startedAt":"2012-07-31T08:39:43Z","lastAt":"2012-08-01T21:07:10Z","messageCount":3,"participants":["Gerlando Falauto","Jeff King","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"196218","messageId":"501799CF.1080100@keymile.com","threadId":"31147","inReplyTo":null,"subject":"rename detection","fromName":"Gerlando Falauto","fromEmail":"gerlando.falauto@keymile.com","sentAt":"2012-07-31T08:39:43Z","receivedAt":"2012-07-31T08:39:43Z","isPatch":false,"sender":{"key":"gerlando.falauto@keymile.com","avatar":null},"body":"Hi everyone,\n\nI have some questions about rename detection.\nThe way I understand it, renames are not tracked in any way by GIT, at \nleast not in the repository. Instead some detection algorithm is \nexecuted when data is extracted from the repository, prior to being \npresented to the user (i.e., git format-patch, git log, git show \netc...), therefore depending on the command line and client used.\n\nSome of those mechanisms are also in place when stuff gets commited. For \ninstance, I get some rename indications when editing the commit message, \nand as the output of git commit itself.\nI would assume the mechanisms would be exactly the same.\n\nThings get a bit more complicated when you actually \"merge\" files (not \nin the git-tish sense, I mean physically move the content of one file \ninto the other). Here is a test which includes a bigger file within a \nsmaller file.\n\n=================== SCRIPT BEGIN ========================\ngit --version\ngit init\nhexdump -C -n 5120 /dev/urandom > file2\nhexdump -C -n 2560 /dev/urandom > file1\necho \"--------------------------\"\ngit add file1 file2\ngit commit -m \"first commit\"\ngit log --summary -M10% -C -1\necho \"--------------------------\"\n(head -n 40 file1; cat file2; tail -n+40 file1) > file3\ngit rm file1 file2\ngit add file3\ngit commit -m \"including file2 within file1 as file3\"\ngit log --summary -M10% -C -1\necho \"--------------------------\"\ngit mv file3 file1\ngit commit --amend -m \"including file2 within file1 as file1\"\ngit log --summary -M10% -C -1\necho \"--------------------------\"\ngit mv file1 file2\ngit commit --amend -m \"including file2 within file1 as file2\"\ngit log --summary -M10% -C -1\necho \"--------------------------\"\n\n=================== SCRIPT END ========================\n\n=================== OUTPUT BEGIN ========================\ngit version 1.7.10.4\nInitialized empty Git repository in /home/chfalag1/tmp/gittest/.git/\n--------------------------\n[master (root-commit) 6d997f5] first commit\n 2 files changed, 482 insertions(+)\n create mode 100644 file1\n create mode 100644 file2\ncommit 6d997f5bbed2e9452317991ca024a5a0e1715027\nAuthor: Gerlando Falauto \nDate: Tue Jul 31 10:27:42 2012 +0200\n\n first commit\n\n create mode 100644 file1\n create mode 100644 file2\n--------------------------\nrm 'file1'\nrm 'file2'\n[master 424edab] including file2 within file1 as file3\n 2 files changed, 162 insertions(+), 161 deletions(-)\n delete mode 100644 file1\n rename file2 => file3 (66%)\ncommit 424edab771495fc3a1b4c172b9fcef9418501266\nAuthor: Gerlando Falauto \nDate: Tue Jul 31 10:27:42 2012 +0200\n\n including file2 within file1 as file3\n\n delete mode 100644 file1\n rename file2 => file3 (66%)\n--------------------------\n[master ca70367] including file2 within file1 as file1\n 1 file changed, 162 insertions(+)\n rename file2 => file1 (66%)\ncommit ca7036705063adbbd3c8cd0b5bccd5fbf44075bf\nAuthor: Gerlando Falauto \nDate: Tue Jul 31 10:27:42 2012 +0200\n\n including file2 within file1 as file1\n\n delete mode 100644 file2\n--------------------------\n[master d7fdea4] including file2 within file1 as file2\n 2 files changed, 162 insertions(+), 161 deletions(-)\n delete mode 100644 file1\ncommit d7fdea4855efe8401562a53ec7093c80390ee274\nAuthor: Gerlando Falauto \nDate: Tue Jul 31 10:27:42 2012 +0200\n\n including file2 within file1 as file2\n\n delete mode 100644 file1\n--------------------------\n=================== OUTPUT END ========================\n\nSo including file2 (bigger) within file1 (smaller):\na) gets always (commit+extraction) detected as a rename file2=>file1 if \nthe merged file is file3 (new file).\nb) gets detected as a rename ONLY during commit (but not while \nextracting) if the merged file is file1 (existing file)\nc) doesn't ever get detected as a rename if the merged file is file2 \n(which makes sense, being file2 more similar to itself than to file1)\n\nSo now my two questions:\n\n1) Is the behavior in b) correct? Shouldn't it at least be made consistent?\n\n2) Would it make any sense to track (or detect) such \"inclusion\" cases? \nIs there any recommended or standard practice for performing such \noperations as file merge/split (i.e. when refactoring code or something)?\n\nThanks!\nGerlando\n"},{"id":"196302","messageId":"20120801203941.GA11940@sigill.intra.peff.net","threadId":"31147","inReplyTo":"501799CF.1080100@keymile.com","subject":"Re: rename detection","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-01T20:39:41Z","receivedAt":"2012-08-01T20:39:41Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 31, 2012 at 10:39:43AM +0200, Gerlando Falauto wrote:\n\n> I have some questions about rename detection.\n> The way I understand it, renames are not tracked in any way by GIT,\n> at least not in the repository. Instead some detection algorithm is\n> executed when data is extracted from the repository, prior to being\n> presented to the user (i.e., git format-patch, git log, git show\n> etc...), therefore depending on the command line and client used.\n\nRight. Rename detection is always part of performing a diff. The\ncommands you mention above are internally doing a diff between a commit\nand its parents. But you could also detect renames between any two\narbitrary trees.\n\nWhich is part of the reason that git does it this way. Giving each path\na unique identity and tracking the renames explicitly across history\nmeans that when comparing two arbitrary trees (which is how some other\nsystems do it), you would have to know the history relationship between\nthe trees in order to show the renames. That's slow (for example, when\nmerging, git does not look at the tree state of intermediate commits; it\nonly looks at the branch point and the two endpoints). It's also less\nflexible; git fundamentally does not care how each side reached its\nstate, only where it ended up.\n\n> Some of those mechanisms are also in place when stuff gets commited.\n> For instance, I get some rename indications when editing the commit\n> message, and as the output of git commit itself.\n> I would assume the mechanisms would be exactly the same.\n\nRight. The template shown by \"git commit\" is just the output of \"git\nstatus\", which is in turn just another diff. The \"to be committed\"\nsection is the diff between the HEAD and the index, and the \"changes not\nmarked for commit\" is the diff between the index and the working tree.\n\nAnd after you complete the commit, the summary shown is from the diff\nbetween what you committed and the previous commit.\n\n> Things get a bit more complicated when you actually \"merge\" files\n> (not in the git-tish sense, I mean physically move the content of one\n> file into the other). Here is a test which includes a bigger file\n> within a smaller file.\n> [...]\n> hexdump -C -n 5120 /dev/urandom > file2\n> hexdump -C -n 2560 /dev/urandom > file1\n> (head -n 40 file1; cat file2; tail -n+40 file1) > file3\n\nSo file3 has file2 stuck in the middle of file1. But since file2 is\ntwice as big as file1, that means the result is 1/3 file1, and 2/3\nfile2.\n\n> git rm file1 file2\n> git add file3\n> git commit -m \"including file2 within file1 as file3\"\n> git log --summary -M10% -C -1\n\nHere we should see a rename from file2 to file3 (we will choose file2\nbecause it shares more content with file3 than file1)\n\nAnd we do (I'm quoting your message out of order from here out to show\noutput next to commands):\n\n> [master 424edab] including file2 within file1 as file3\n> 2 files changed, 162 insertions(+), 161 deletions(-)\n> delete mode 100644 file1\n> rename file2 => file3 (66%)\n> commit 424edab771495fc3a1b4c172b9fcef9418501266\n> Author: Gerlando Falauto \n> Date: Tue Jul 31 10:27:42 2012 +0200\n> \n> including file2 within file1 as file3\n> \n> delete mode 100644 file1\n> rename file2 => file3 (66%)\n\nMoving on, we next put the new content in file1:\n\n> git mv file3 file1\n> git commit --amend -m \"including file2 within file1 as file1\"\n> git log --summary -M10% -C -1\n\nThe diff shown by the commit summary and by \"git log\" will be the diff\nbetween the initial state (both file1 and file2) and the new state\n(file1 is now mostly file2, and file2 has gone away). But you get\ninconsistent results, even though we are diffing the same trees:\n\n> [master ca70367] including file2 within file1 as file1\n> 1 file changed, 162 insertions(+)\n> rename file2 => file1 (66%)\n> commit ca7036705063adbbd3c8cd0b5bccd5fbf44075bf\n> Author: Gerlando Falauto \n> Date: Tue Jul 31 10:27:42 2012 +0200\n> \n> including file2 within file1 as file1\n> \n> delete mode 100644 file2\n\nWhy? Because the diff options used by git-commit to generate its summary\nare not the same as the ones you told git-log to use. The short answer\nis that you can get the same result by using \"-B\".\n\nTo understand why, you first need to understand how the rename detection\nworks. Basically, we have a set of candidate sources (files which were\nremoved) and a set of candidate destination (files which were added),\nand we try to match them up to create rename pairs by comparing their\ncontent. The comparison is expensive and has complexity O(src*dst), so\nwe want to keep those numbers low to keep the cost of the computation\ndown.\n\nFor basic renames (i.e., \"-M\") we consider only removed and added files\nas candidates, since a rename must involve those. When you specify \"-C\",\nthat looks for copies: we increase the source candidate set to include\nfiles which were modified but not deleted. In other words, a copy is\njust a rename where the source did not go away. We limit it to modified\nfiles for practical purposes; it keeps the computation low, and when you\nare copying the content, you tend to make modifications to the original\nfile.\n\nIf you specify --find-copies-harder (or use \"-C\" twice), git will also\ninclude even unmodified files in the source list. This is very expensive\nto compute, but can find instances where you copied without modifying\nthe original at all.\n\nBut what about the destination side? There is no orthogonal option to\nsay \"include all modified files in the destination list\". Such an option\ncould be used for finding a copy when a file existed, but absorbed most\nof another file (as in this case). But it turns out not to be needed, as\nyou'll see in a minute.\n\nSo at this point, you should understand why your \"git log\" does not show\nthe rename; because file1 existed both before and after, it is not a new\nfile, and therefore not a destination candidate. But why does \"git\ncommit\" show it?\n\nFor that, we have to understand what \"-B\" does: break detection. This\nacts on the diff results before they get to the rename phase, and tries\nto break apart file modifications that substantially rewrite the file\ncontent into two separate entries: deleting the old file, and adding the\nnew file at the same path. Those entries then become eligible source\nand destination candidates for rename detection.\n\nIn this case, file1 was substantially rewritten (2/3 of its content is\nnew), so we break it, letting us use it as both a source and destination\ncandidate. And since file2 is already a source candidate (since it went\naway), we do the exact same rename detection as above (modulo that the\ndestination candidate's path is now \"file1\" instead of \"file3\"), and\nfind that file2 is the best source.\n\nIn your final example, we do:\n\n> git mv file1 file2\n> git commit --amend -m \"including file2 within file1 as file2\"\n> git log --summary -M10% -C -1\n\nSame thing, except the content is placed in file2. And we get:\n\n> [master d7fdea4] including file2 within file1 as file2\n> 2 files changed, 162 insertions(+), 161 deletions(-)\n> delete mode 100644 file1\n> commit d7fdea4855efe8401562a53ec7093c80390ee274\n> Author: Gerlando Falauto \n> Date: Tue Jul 31 10:27:42 2012 +0200\n> \n> including file2 within file1 as file2\n> \n> delete mode 100644 file1\n\nNo rename detection at all, in either case. Why? In the log case, it is\nfor the same reason above; we don't have break detection turned on, and\nfile2 is not a destination candidate for renames.\n\nFor commit, it is because the break algorithm did not consider the\nresulting file2 to be different enough from its original version. That's\nbecause 2/3 of the content is the same, and only 1/3 actually changed.\nIf you feed the break-detector a low enough score (e.g., -B30%) then it\nwill consider it a rename (albeit a poor one). E.g.:\n\n git log --summary -B30% -M30%\n\n> So including file2 (bigger) within file1 (smaller):\n> a) gets always (commit+extraction) detected as a rename file2=>file1\n> if the merged file is file3 (new file).\n> b) gets detected as a rename ONLY during commit (but not while\n> extracting) if the merged file is file1 (existing file)\n> c) doesn't ever get detected as a rename if the merged file is file2\n> (which makes sense, being file2 more similar to itself than to file1)\n> \n> So now my two questions:\n> \n> 1) Is the behavior in b) correct? Shouldn't it at least be made consistent?\n> 2) Would it make any sense to track (or detect) such \"inclusion\"\n> cases? Is there any recommended or standard practice for performing\n> such operations as file merge/split (i.e. when refactoring code or\n> something)?\n\nHopefully the above has answered these questions for you.\n\nHowever, I hope it has also showed the limitations of pure file renames\nwhen you are looking at content movement from one file to another. For\nthat, you are much better off looking at something like \"git blame -C\nfile2\", which gives you line-by-line content attribution. For example,\non the final commit you produce in your example, it will properly show\nwhich lines came from file1 and which came from file2.\n\n-Peff\n"},{"id":"196303","messageId":"7vtxwme2yp.fsf@alter.siamese.dyndns.org","threadId":"31147","inReplyTo":"20120801203941.GA11940@sigill.intra.peff.net","subject":"Re: rename detection","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-01T21:07:10Z","receivedAt":"2012-08-01T21:07:10Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Hopefully the above has answered these questions for you.\n>\n> However, I hope it has also showed the limitations of pure file renames\n> when you are looking at content movement from one file to another.\n\nNice write-up.\n\nCare to save this somewhere more permanent (e.g. git.wiki.k.org or\nDocumentation/), after rewording the above to make it more clear\nthat the \"limitations\" you mention does not have anything to do with\nGit, but is a fundamental flaw in thinking that it is somehow useful\nto track that \"file A was renamed to file B\"?\n"}]}