)]}' { "commit": "978535b09080edcc01302e80b37b9e1263c21db3", "tree": "4925c496b30177b7a8e5103e71623f79f9cd2a0d", "parents": [ "cb8e1e6014c9cbac9c557df519ad7e22bdcf7d7d" ], "author": { "name": "Shawn O. Pearce", "email": "spearce@spearce.org", "time": "Fri Jul 02 17:29:09 2010 -0700" }, "committer": { "name": "Shawn O. Pearce", "email": "spearce@spearce.org", "time": "Sat Jul 03 16:32:03 2010 -0700" }, "message": "Implement similarity based rename detection\n\nContent similarity based rename detection is performed only after\na linear time detection is performed using exact content match on\nthe ObjectIds. Any names which were paired up during that exact\nmatch phase are excluded from the inexact similarity based rename,\nwhich reduces the space that must be considered.\n\nDuring rename detection two entries cannot be marked as a rename\nif they are different types of files. This prevents a symlink from\nbeing renamed to a regular file, even if their blob content appears\nto be similar, or is identical.\n\nEfficiently comparing two files is performed by building up two\nhash indexes and hashing lines or short blocks from each file,\ncounting the number of bytes that each line or block represents.\n\nInstead of using a standard java.util.HashMap, we use a custom\nopen hashing scheme similiar to what we use in ObjecIdSubclassMap.\nThis permits us to have a very light-weight hash, with very little\nmemory overhead per cell stored.\n\nAs we only need two ints per record in the map (line/block key and\nnumber of bytes), we collapse them into a single long inside of\na long array, making very efficient use of available memory when\nwe create the index table. We only need object headers for the\nindex structure itself, and the index table, but not per-cell.\nThis offers a massive space savings over using java.util.HashMap.\n\nThe score calculation is done by approximating how many bytes are\nthe same between the two inputs (which for a delta would be how much\nis copied from the base into the result). The score is derived by\ndividing the approximate number of bytes in common into the length\nof the larger of the two input files.\n\nRight now the SimilarityIndex table should average about 1/2 full,\nwhich means we waste about 50% of our memory on empty entries\nafter we are done indexing a file and sort the table\u0027s contents.\nIf memory becomes an issue we could discard the table and copy all\nrecords over to a new array that is properly sized.\n\nBuilding the index requires O(M + N log N) time, where M is the\nsize of the input file in bytes, and N is the number of unique\nlines/blocks in the file. The N log N time constraint comes\nfrom the sort of the index table that is necessary to perform\nlinear time matching against another SimilarityIndex created for\na different file.\n\nTo actually perform the rename detection, a SxD matrix is created,\nplacing the sources (aka deletions) along one dimension and the\ndestinations (aka additions) along the other. A simple O(S x D)\nloop examines every cell in this matrix.\n\nA SimilarityIndex is built along the row and reused for each\ncolumn compare along that row, avoiding the costly index rebuild\nat the row level. A future improvement would be to load a smaller\nsquare matrix into SimilarityIndexes and process everything in that\nsub-matrix before discarding the column dimension and moving down\nto the next sub-matrix block along that same grid of rows.\n\nAn optional ProgressMonitor is permitted to be passed in, allowing\napplications to see the progress of the detector as it works through\nthe matrix cells. This provides some indication of current status\nfor very long running renames.\n\nThe default line/block hash function used by the SimilarityIndex\nmay not be optimal, and may produce too many collisions. It is\nborrowed from RawText\u0027s hash, which is used to quickly skip out of\na longer equality test if two lines have different hash functions.\nWe may need to refine this hash in the future, in order to minimize\nthe number of collisions we get on common source files.\n\nBased on a handful of test commits in JGit (especially my own\nrecent rename repository refactoring series), this rename detector\nproduces output that is very close to C Git. The content similarity\nscores are sometimes off by 1%, which is most probably caused by\nour SimilarityIndex type using a different hash function than C\nGit uses when it computes the delta size between any two objects\nin the rename matrix.\n\nBug: 318504\nChange-Id: I11dff969e8a2e4cf252636d857d2113053bdd9dc\nSigned-off-by: Shawn O. Pearce \u003cspearce@spearce.org\u003e\n", "tree_diff": [ { "type": "modify", "old_id": "4f84066f2e476e173fb7631c179eb58d430b910f", "old_mode": 33188, "old_path": "org.eclipse.jgit.test/tst/org/eclipse/jgit/diff/RenameDetectorTest.java", "new_id": "c4cb600db0b377ba520499b0d8d29f7949050303", "new_mode": 33188, "new_path": "org.eclipse.jgit.test/tst/org/eclipse/jgit/diff/RenameDetectorTest.java" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "9ab745fac9947b8fab10720f4fa19b28b6f9ff5c", "new_mode": 33188, "new_path": "org.eclipse.jgit.test/tst/org/eclipse/jgit/diff/SimilarityIndexTest.java" }, { "type": "modify", "old_id": "8d9e302a82ecb2ef2d85f5189dbc12195de91687", "old_mode": 33188, "old_path": "org.eclipse.jgit.test/tst/org/eclipse/jgit/patch/FileHeaderTest.java", "new_id": "17e99779cf3b74a7a39dd0954b65573fb045b387", "new_mode": 33188, "new_path": "org.eclipse.jgit.test/tst/org/eclipse/jgit/patch/FileHeaderTest.java" }, { "type": "modify", "old_id": "e97d373d9a2716fb69fea34c332a83d3466165f8", "old_mode": 33188, "old_path": "org.eclipse.jgit.test/tst/org/eclipse/jgit/patch/PatchCcTest.java", "new_id": "1d879cba679a8f43fecfdb699080545d33c23cca", "new_mode": 33188, "new_path": "org.eclipse.jgit.test/tst/org/eclipse/jgit/patch/PatchCcTest.java" }, { "type": "modify", "old_id": "76097cb5fdf26ce09f52ebaad3672e6652fe6746", "old_mode": 33188, "old_path": "org.eclipse.jgit/resources/org/eclipse/jgit/JGitText.properties", "new_id": "a8b9a33a4885e41959229a41f67e332fbcfb60c1", "new_mode": 33188, "new_path": "org.eclipse.jgit/resources/org/eclipse/jgit/JGitText.properties" }, { "type": "modify", "old_id": "a2e1cd1091fcd66858c37e3de9eb5f8c703fabf0", "old_mode": 33188, "old_path": "org.eclipse.jgit/src/org/eclipse/jgit/JGitText.java", "new_id": "ed5192cf5a3a5e2743d5395a46f82fdaec1f7e5e", "new_mode": 33188, "new_path": "org.eclipse.jgit/src/org/eclipse/jgit/JGitText.java" }, { "type": "modify", "old_id": "ac3ee9864e3f293303d98dc841ac0d7c4f527691", "old_mode": 33188, "old_path": "org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffEntry.java", "new_id": "e41ec567017b57512060e997bb2d3b162aabfcff", "new_mode": 33188, "new_path": "org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffEntry.java" }, { "type": "modify", "old_id": "50d81c966456506922fef39bf039c65042c0bcaf", "old_mode": 33188, "old_path": "org.eclipse.jgit/src/org/eclipse/jgit/diff/RenameDetector.java", "new_id": "8116e87ef02d22ac71347c10590d36f5bc3f0a69", "new_mode": 33188, "new_path": "org.eclipse.jgit/src/org/eclipse/jgit/diff/RenameDetector.java" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "d6026b5be21b231beaeec04962a87bae5fbfcf4a", "new_mode": 33188, "new_path": "org.eclipse.jgit/src/org/eclipse/jgit/diff/SimilarityIndex.java" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "c92b1e3bb15f87ccc36c3603d842723fa8f129cf", "new_mode": 33188, "new_path": "org.eclipse.jgit/src/org/eclipse/jgit/diff/SimilarityRenameDetector.java" }, { "type": "modify", "old_id": "35c2ee30372939dd909acb367c5aace5e59ad77f", "old_mode": 33188, "old_path": "org.eclipse.jgit/src/org/eclipse/jgit/patch/FileHeader.java", "new_id": "f2f2f2e742912387778d2ef2bd1392c0fe61304e", "new_mode": 33188, "new_path": "org.eclipse.jgit/src/org/eclipse/jgit/patch/FileHeader.java" } ] }