{"thread":{"id":"3638","subject":"Fix up diffcore-rename scoring","startedAt":"2006-03-13T06:26:34Z","lastAt":"2006-04-14T17:46:56Z","messageCount":13,"participants":["Linus Torvalds","Junio C Hamano","Rutger Nijlunsing","Geert Bosch"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"17507","messageId":"Pine.LNX.4.64.0603122223160.3618@g5.osdl.org","threadId":"3638","inReplyTo":null,"subject":"Fix up diffcore-rename scoring","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-13T06:26:34Z","receivedAt":"2006-03-13T06:26:34Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThe \"score\" calculation for diffcore-rename was totally broken.\n\nIt scaled \"score\" as\n\n\tscore = src_copied * MAX_SCORE / dst->size;\n\nwhich means that you got a 100% similarity score even if src and dest were \ndifferent, if just every byte of dst was copied from src, even if source \nwas much larger than dst (eg we had copied 85% of the bytes, but _deleted_ \nthe remaining 15%).\n\nThat's clearly bogus. We should do the score calculation relative not to \nthe destination size, but to the max size of the two.\n\nThis seems to fix it.\n\nSigned-off-by: Linus Torvalds <torvalds@osdl.org>\n---\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex ed99fe2..e992698 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -133,7 +133,7 @@ static int estimate_similarity(struct di\n \t * match than anything else; the destination does not even\n \t * call into this function in that case.\n \t */\n-\tunsigned long delta_size, base_size, src_copied, literal_added;\n+\tunsigned long max_size, delta_size, base_size, src_copied, literal_added;\n \tunsigned long delta_limit;\n \tint score;\n \n@@ -144,9 +144,9 @@ static int estimate_similarity(struct di\n \tif (!S_ISREG(src->mode) || !S_ISREG(dst->mode))\n \t\treturn 0;\n \n-\tdelta_size = ((src->size < dst->size) ?\n-\t\t      (dst->size - src->size) : (src->size - dst->size));\n+\tmax_size = ((src->size > dst->size) ? src->size : dst->size);\n \tbase_size = ((src->size < dst->size) ? src->size : dst->size);\n+\tdelta_size = max_size - base_size;\n \n \t/* We would not consider edits that change the file size so\n \t * drastically.  delta_size must be smaller than\n@@ -174,12 +174,10 @@ static int estimate_similarity(struct di\n \t/* How similar are they?\n \t * what percentage of material in dst are from source?\n \t */\n-\tif (dst->size < src_copied)\n-\t\tscore = MAX_SCORE;\n-\telse if (!dst->size)\n+\tif (!dst->size)\n \t\tscore = 0; /* should not happen */\n \telse\n-\t\tscore = src_copied * MAX_SCORE / dst->size;\n+\t\tscore = src_copied * MAX_SCORE / max_size;\n \treturn score;\n }\n \n"},{"id":"17510","messageId":"Pine.LNX.4.64.0603122241100.3618@g5.osdl.org","threadId":"3638","inReplyTo":"Pine.LNX.4.64.0603122223160.3618@g5.osdl.org","subject":"Re: Fix up diffcore-rename scoring","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-13T06:44:40Z","receivedAt":"2006-03-13T06:44:40Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Mar 2006, Linus Torvalds wrote:\n> \n> The \"score\" calculation for diffcore-rename was totally broken.\n> \n> It scaled \"score\" as\n> \n> \tscore = src_copied * MAX_SCORE / dst->size;\n> \n> which means that you got a 100% similarity score even if src and dest were \n> different, if just every byte of dst was copied from src, even if source \n> was much larger than dst (eg we had copied 85% of the bytes, but _deleted_ \n> the remaining 15%).\n> \n> That's clearly bogus. We should do the score calculation relative not to \n> the destination size, but to the max size of the two.\n> \n> This seems to fix it.\n\nBtw, interestingly, this seems to actually improve on the rename \ndetection from your previous one, even though at the face of it, it \nshould just have made the scores go down.\n\nI'm not quite sure why, but perhaps it gave a bogus high score to some \nrename that wasn't very good, allowing the _real_ rename to make itself \nseen.\n\nOr maybe I did some mistake in testing it.\n\n\t\tLinus\n\nPS. You can still get a \"similarity score\" of 100 with the fixed scaling \neven if the source and the destination were different. That happens if \nevery byte was marked as \"copied\" by the similarity estimator. Which can \nhappen if you just move things around in the file - the end result is \ndifferent, but all the bytes are copied from the source.\n\nAt least with the fixed heuristic, that \"perfect similarity\" score can be \n_somehow_ be explained. The files are very similar in that they have the \nsame content, just in a different order ;)\n"},{"id":"17512","messageId":"7vmzfusuyq.fsf@assigned-by-dhcp.cox.net","threadId":"3638","inReplyTo":"Pine.LNX.4.64.0603122223160.3618@g5.osdl.org","subject":"Re: Fix up diffcore-rename scoring","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-13T06:46:21Z","receivedAt":"2006-03-13T06:46:21Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> The \"score\" calculation for diffcore-rename was totally broken.\n>\n> It scaled \"score\" as\n>\n> \tscore = src_copied * MAX_SCORE / dst->size;\n>\n> which means that you got a 100% similarity score even if src and dest were \n> different, if just every byte of dst was copied from src, even if source \n> was much larger than dst (eg we had copied 85% of the bytes, but _deleted_ \n> the remaining 15%).\n\nYour reading of the code is correct, but that is deliberate.\n\n>  \t/* How similar are they?\n>  \t * what percentage of material in dst are from source?\n>  \t */\n\nI wanted to say in such a case that dst was _really_ derived\nfrom the source.  I think using max may make more sense, but I\nneed to convince myself by looking at filepairs that this change\nstops detecting as renames, and this change starts detecting as\nrenames.\n"},{"id":"17513","messageId":"Pine.LNX.4.64.0603122256550.3618@g5.osdl.org","threadId":"3638","inReplyTo":"7vmzfusuyq.fsf@assigned-by-dhcp.cox.net","subject":"Re: Fix up diffcore-rename scoring","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-13T07:09:11Z","receivedAt":"2006-03-13T07:09:11Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Mar 2006, Junio C Hamano wrote:\n>\n> Linus Torvalds <torvalds@osdl.org> writes:\n> \n> > The \"score\" calculation for diffcore-rename was totally broken.\n> >\n> > It scaled \"score\" as\n> >\n> > \tscore = src_copied * MAX_SCORE / dst->size;\n> >\n> > which means that you got a 100% similarity score even if src and dest were \n> > different, if just every byte of dst was copied from src, even if source \n> > was much larger than dst (eg we had copied 85% of the bytes, but _deleted_ \n> > the remaining 15%).\n> \n> Your reading of the code is correct, but that is deliberate.\n> \n> >  \t/* How similar are they?\n> >  \t * what percentage of material in dst are from source?\n> >  \t */\n> \n> I wanted to say in such a case that dst was _really_ derived\n> from the source.  I think using max may make more sense, but I\n> need to convince myself by looking at filepairs that this change\n> stops detecting as renames, and this change starts detecting as\n> renames.\n\nJust compare the result. Just eye-balling the difference between the \nrename data from 2.6.12 to 2.6.14, the fixed score actually gets better \nrename detection. It actually finds 133 renames (as opposed to 132 for the \nbroken one), and the renames it finds are more sensible.\n\nFor example, the fixed version finds\n\n\tdrivers/i2c/chips/lm75.h -> drivers/hwmon/lm75.h\n\nwhich actually matches the other i2c/chips/ renames, while the broken one \ndoes\n\n\tdrivers/i2c/chips/lm75.h -> drivers/media/video/rds.h\n\nwhich just doesn't make any sense at all.\n\nNow, that said, they _both_ find some pretty funky renames. I think there \nis probably some serious room for improvement, regardless (or at least \nchanging the default similarity cut-off to something better ;)\n\n\t\tLinus\n"},{"id":"17514","messageId":"7v64missd1.fsf@assigned-by-dhcp.cox.net","threadId":"3638","inReplyTo":"Pine.LNX.4.64.0603122256550.3618@g5.osdl.org","subject":"Re: Fix up diffcore-rename scoring","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-13T07:42:34Z","receivedAt":"2006-03-13T07:42:34Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> Just compare the result...\n>\n> Now, that said, they _both_ find some pretty funky renames. I think there \n> is probably some serious room for improvement, regardless (or at least \n> changing the default similarity cut-off to something better ;)\n\nYes.  The \"compare with larger\" seems to cull nonsensical ones\nfound by \"next\" one much better.\n"},{"id":"17515","messageId":"Pine.LNX.4.64.0603122316160.3618@g5.osdl.org","threadId":"3638","inReplyTo":"Pine.LNX.4.64.0603122256550.3618@g5.osdl.org","subject":"Re: Fix up diffcore-rename scoring","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-13T07:44:44Z","receivedAt":"2006-03-13T07:44:44Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Mar 2006, Linus Torvalds wrote:\n> \n> Now, that said, they _both_ find some pretty funky renames. I think there \n> is probably some serious room for improvement, regardless (or at least \n> changing the default similarity cut-off to something better ;)\n\nI'm afraid that _good_ rename detection really ends up wanting to take \n\"longest possible sequence\" into account, exactly like the full xdelta \ndoes. \n\nInstead of doing a fixed-chunk thing and saying that any copy is \nequivalent to any other copy. That's simply not true. It's _much_ better \nto have one 24-byte copy than it is to have three 8-byte copies, but the \nnew faster diffcore-delta.c just can't see that.\n\nSo one big reason as to why it is fast in the first place is that it \nfundamentally just doesn't do a very good job ;(\n\nIt might be that the fast delta thing is a good way to ask \"is this even \nworth considering\", to cut down the O(m*n) rename/copy detection to \nsomething much smaller, and then use xdelta() to actually figure out what \nis a good rename and what isn't from a much smaller set of potential \ntargets.\n\nThat would actually allow us to be even _less_ precise. Screw that big \nhash-table etc, don't even try to be exact. Just try to be fairly fast, \nand then pick the top entries from the similarity array for more precise \ndiffing if there are multiple choices that look like they might be \npossible.\n\nThe appended alternate \"diffcore-delta.c\" doesn't do any of the caching \n(ie I wrote it so that it would be easy to change to make the _caller_ \nkeeps \"src\" constant, and iterates over destination - or the other way \naround - and would do the hash setup just once per src).\n\nStill, even with the existing setup, it's pretty fast for me (not much \nslower than your caching version even though it recalculates everything \nevery time). And it's not that far off, which tells me that if it was used \nas a \"first-pass filter\", we could afford to do a better job on the things \nthat it says are likely candidates.\n\nHmm? It really does bother me how the suggested rename detector finds \nstuff that clearly isn't. \n\n\t\t\tLinus\n\n----\n#include \"cache.h\"\n#include \"diff.h\"\n#include \"diffcore.h\"\n\n#define CHUNK (16)\n#define SILLYSIZE (65537)\nstatic int hashnr[SILLYSIZE];\n\nstatic void setup_hash(void)\n{\n\tmemset(hashnr, 0, sizeof(hashnr));\n}\n\nstatic void insert_hash(unsigned int hashval)\n{\n\thashval = hashval % SILLYSIZE;\n\thashnr[hashval]++;\n}\n\nstatic int find_hash(unsigned int hashval)\n{\n\thashval = hashval % SILLYSIZE;\n\tif (hashnr[hashval]) {\n\t\thashnr[hashval]--;\n\t\treturn 1;\n\t}\n\treturn 0;\n}\n\nint diffcore_count_changes(void *src, unsigned long src_size,\n\t\t\t   void *dst, unsigned long dst_size,\n\t\t\t   void **src_count_p,\n\t\t\t   void **dst_count_p,\n\t\t\t   unsigned long delta_limit,\n\t\t\t   unsigned long *src_copied,\n\t\t\t   unsigned long *literal_added)\n{\n\tunsigned long copied = 0;\n\tunsigned long literal = 0;\n\n\tsetup_hash();\n\twhile (src_size >= CHUNK) {\n\t\tunsigned int hashval = adler32(0, src, CHUNK);\n\t\tinsert_hash(hashval);\n\t\tsrc += CHUNK;\n\t\tsrc_size -= CHUNK;\n\t}\n\n\twhile (dst_size >= CHUNK) {\n\t\tunsigned int hashval = adler32(0, dst, CHUNK);\n\t\tif (find_hash(hashval)) {\n\t\t\tcopied += CHUNK;\n\t\t\tdst += CHUNK;\n\t\t\tdst_size -= CHUNK;\n\t\t\tcontinue;\n\t\t}\n\t\tliteral++;\n\t\tif (literal > delta_limit)\n\t\t\treturn -1;\n\t\tdst++;\n\t\tdst_size--;\n\t}\n\tliteral += dst_size;\n\n\t*src_copied = copied;\n\t*literal_added = literal;\n\treturn 0;\n}\n"},{"id":"17517","messageId":"7vzmjupqv0.fsf@assigned-by-dhcp.cox.net","threadId":"3638","inReplyTo":"Pine.LNX.4.64.0603122316160.3618@g5.osdl.org","subject":"Re: Fix up diffcore-rename scoring","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-13T10:43:15Z","receivedAt":"2006-03-13T10:43:15Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> Instead of doing a fixed-chunk thing and saying that any copy is \n> equivalent to any other copy. That's simply not true. It's _much_ better \n> to have one 24-byte copy than it is to have three 8-byte copies, but the \n> new faster diffcore-delta.c just can't see that.\n\nExactly.\n\nYou know what?  Once we start counting to detect 24-byte\nstraight copy and try distinguishing it from 3 separate 8-byte\ncopies, it will eventually lead us to what we have in\ndiff-delta.c anyway.  I avoided counting runs of bytes on\npurpose because I wanted to see how far we can go without it.\n\nThe primary reason I started the jc/diff topic branch was\nbecause we _might_ want to replace what is in the current\ndiff-delta.c with much finer-grained comparison code, and when\nthat happens, counting xdelta output for rename detection\npurpose would have stopped making sense.  For now we decided to\npostpone it for performance reasons, but we still might want to\nwhen Nico comes back with a better implementation.\n\nNow, I know the current diff-delta based similarity estimator we\nhave in \"main\" seems to do a reasonable if not perfect job,\nwithin a reasonabe amount of time.  And it does know how to\ncount copying of consecutive bytes.  In the worst case we could\njust fork the xdelta part of the code when Nico comes back with\nimproved finer-grained delta, and we can keep using the current\ndiff-delta code for rename detection.  Knowing we have that\nfallback position, I wanted to pursue a different avenue.\nDistinguishing a straight 24-byte run from three independent\n8-byte run, using hash to find the offset in the source and\nactually do maximum string match, is something we already know\nhow to do, because that is essentially what the current\ndiff-delta code does.\n\nBy the way, the reason the diffcore-delta code in \"next\" does\nnot do every-eight-bytes hash on the source material is to\nsomewhat alleviate the problem that comes from not detecting\ncopying of consecutive byte ranges.  If you have a 8-byte run\nthat is copied from source to destination, we would give it one\npoint (let's for now forget about false match coming from hash\ncollisions).  Since the source material is hashed at every byte\noffset, if we have 9-byte run copied from source to destination,\nthat is awarded two points (for the first 8-byte we award one\npoint, and then another 8-byte sequence starting from the second\nbyte we award another point; we are talking about an overlapping\nrange).  That way, the code does reward copying consecutive\nbytes around more heavily than copying things at random places.\nAt one extreme, if you copy 7-byte, throw in a garbage, another\n7-byte, throw in a garbage, and keep going, you would not get\nany point.\n\nIt's really a funky heuristics, and as you have seen, it\nsometimes gives spectaculary phony matches.  But in practice,\nwith some tweaking it seems to do an OK job.\n"},{"id":"17519","messageId":"Pine.LNX.4.64.0603130727350.3618@g5.osdl.org","threadId":"3638","inReplyTo":"7vzmjupqv0.fsf@assigned-by-dhcp.cox.net","subject":"Re: Fix up diffcore-rename scoring","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-13T15:38:53Z","receivedAt":"2006-03-13T15:38:53Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 13 Mar 2006, Junio C Hamano wrote:\n> \n> By the way, the reason the diffcore-delta code in \"next\" does\n> not do every-eight-bytes hash on the source material is to\n> somewhat alleviate the problem that comes from not detecting\n> copying of consecutive byte ranges.\n\nYes. However, there are better ways to do that in practice.\n\nThe most effective way that is generally used is to not use a fixed \nchunk-size, but use a terminating character, together with a \nminimum/maximum chunksize.\n\nThere's a pretty natural terminating character that works well for \nsources: '\\n'.\n\nSo the natural way to do similarity detection when most of the code is \nline-based is to do the hashing on chunks that follow the rule \"minimum of \n<n> bytes, maximum of <2*n> bytes, try to begin/end at a \\n\".\n\nSo if you don't see any '\\n' at all (or the only such one is less than <n> \nbytes into your current window), do the hash over a <2n>-byte chunk (this \ntakes care of binaries and/or long lines).\n\nThis - for source code - allows you to ignore trivial byte offset things, \nbecause you have a character that is used for synchronization. So you \ndon't need to do hashing at every byte in both files - you end up doing \nthe hashing only at line boundaries in practice. And it still _works_ for \nbinary files, although you effectively need bigger identical chunk-sizes \nto find similarities (for text-files, it finds similarities of size <n>, \nfor binaries the similarities need to effectively be of size 3*n, because \nyou chunk it up at ~2*n, and only generate the hash at certain offsets in \nthe source binary).\n\n\t\tLinus\n"},{"id":"17536","messageId":"20060314004939.GA26674@nospam.com","threadId":"3638","inReplyTo":"Pine.LNX.4.64.0603130727350.3618@g5.osdl.org","subject":"Re: Fix up diffcore-rename scoring","fromName":"Rutger Nijlunsing","fromEmail":"rutger@nospam.com","sentAt":"2006-03-14T00:49:39Z","receivedAt":"2006-03-14T00:49:39Z","isPatch":false,"sender":{"key":"rutger.nijlunsing@gmail.com","avatar":null},"body":"From: Rutger Nijlunsing <rutger@nospam.com>\nTo: Linus Torvalds <torvalds@osdl.org>\nCc: Junio C Hamano <junkio@cox.net>, git@vger.kernel.org\nBcc: \nSubject: Re: Fix up diffcore-rename scoring\nReply-To: git@wingding.demon.nl\nIn-Reply-To: <Pine.LNX.4.64.0603130727350.3618@g5.osdl.org>\nOrganization: M38c\n\nOn Mon, Mar 13, 2006 at 07:38:53AM -0800, Linus Torvalds wrote:\n> \n> \n> On Mon, 13 Mar 2006, Junio C Hamano wrote:\n> > \n> > By the way, the reason the diffcore-delta code in \"next\" does\n> > not do every-eight-bytes hash on the source material is to\n> > somewhat alleviate the problem that comes from not detecting\n> > copying of consecutive byte ranges.\n> \n> Yes. However, there are better ways to do that in practice.\n> \n> The most effective way that is generally used is to not use a fixed \n> chunk-size, but use a terminating character, together with a \n> minimum/maximum chunksize.\n> \n> There's a pretty natural terminating character that works well for \n> sources: '\\n'.\n> \n> So the natural way to do similarity detection when most of the code is \n> line-based is to do the hashing on chunks that follow the rule \"minimum of \n> <n> bytes, maximum of <2*n> bytes, try to begin/end at a \\n\".\n> \n> So if you don't see any '\\n' at all (or the only such one is less than <n> \n> bytes into your current window), do the hash over a <2n>-byte chunk (this \n> takes care of binaries and/or long lines).\n> \n> This - for source code - allows you to ignore trivial byte offset things, \n> because you have a character that is used for synchronization. So you \n> don't need to do hashing at every byte in both files - you end up doing \n> the hashing only at line boundaries in practice. And it still _works_ for \n> binary files, although you effectively need bigger identical chunk-sizes \n> to find similarities (for text-files, it finds similarities of size <n>, \n> for binaries the similarities need to effectively be of size 3*n, because \n> you chunk it up at ~2*n, and only generate the hash at certain offsets in \n> the source binary).\n\nThis looks like something I did last year as an experiment in the\npre-git times. The idea was to generate a patch-with-renames from two\n(large) source trees.\n\nAlgorithm:\n  - determine md5sum for each file (same idea as git's SHA1 sum)\n    if changed since last run\n  - only look at md5sums which do not match\n  - pool files into types, which might depend on extension and/or MIME type.\n    This is an optimisation.\n  - Only compare filepair _within_ one pool.\n  - The filepair order in one pool is determined by filename-similarity.\n    So pair [include/asm-ppc/ioctl.h, include/asm-powerpc/ioctl.h]\n    is inspected before pair\n       [include/asm-ppc/ioctl.h, arch/arm/plat-omap/clock.h] .\n  - For each file, create a hash from String line -> Integer occuranced .\n    Similarities are calculated by comparing two hashes.\n  - Keep as a rename-match all files which:\n    - have at most 50% new lines;\n    - have at most 25% lines deleted from them.\n\nI ran the code against v2.6.12 and v2.6.14 to be able to compare it\nwith the current contenders. Hopefully some ideas are harvestable...\n\nAlgorithm differences:\n  - '\\n' is used as boundary, independant on line length.\n    This is bad for binary files, and maybe even bad for text files.\n    So don't harvest :)\n  - don't look at the intersection percentage, but look at two values:\n    - percentage of lines added (default: max. 50%)\n    - percentage of lines removed (default: max. 25%)\n    This assumes files get bigger during development (at most 50%), and\n    not too much code is deleted (at most 25%).\n    Disadvantages:\n      - Two magic numbers instead of one.\n      - It's non-symmetrical. Diff A->B will find different renames from\n        diff B->A. This scares me, actually.\n  - to speed up the detection:\n    - don't start comparing files at random. Start comparing files which\n      have the same 'names' in it. So when v2.6.12 has a files called\n      arch/arm/mach-omap/clock.c, start comparing with files which have\n      most words the same. Currently, '-', '.', '_' and '/' are used\n      as word separators.\n      Advantage: don't match on the first match just above the\n        match-threshold.\n    (next heuristics are all optional:)\n    - only compare files with the same extension. This splits up all files\n      into groups, which makes it much faster.\n      In general, there's no reason to compare a .h with a .c file.\n    - only compare files with the same MIME type. Same as above, but also\n      works for files without extensions (so don't compare README with\n      Makefile)\n\nOk, the result:\n\n$ shpatch.rb -d linux-2.6.12,linux-2.6.14 | wc -l\n104   <-- That's bad. We're missing some renames here.\n\n$ shpatch.rb -d linux-2.6.12,linux-2.6.14 | sort -k 1.10\n\n+ 0% -23% arch/arm/configs/omnimeter_defconfig -> arch/arm/configs/collie_defconfig\n+ 5% - 9% arch/arm/mach-omap/board-generic.c -> arch/arm/mach-omap1/board-generic.c\n+ 0% - 8% arch/arm/mach-omap/board-h2.c -> arch/arm/mach-omap1/board-h2.c\n+ 0% - 5% arch/arm/mach-omap/board-h3.c -> arch/arm/mach-omap1/board-h3.c\n+ 0% - 3% arch/arm/mach-omap/board-innovator.c -> arch/arm/mach-omap1/board-innovator.c\n+ 0% - 9% arch/arm/mach-omap/board-netstar.c -> arch/arm/mach-omap1/board-netstar.c\n+ 9% -10% arch/arm/mach-omap/board-osk.c -> arch/arm/mach-omap1/board-osk.c\n+ 0% - 6% arch/arm/mach-omap/board-perseus2.c -> arch/arm/mach-omap1/board-perseus2.c\n+ 3% - 8% arch/arm/mach-omap/board-voiceblue.c -> arch/arm/mach-omap1/board-voiceblue.c\n+ 7% - 4% arch/arm/mach-omap/clock.c -> arch/arm/plat-omap/clock.c\n+ 0% - 0% arch/arm/mach-omap/clock.h -> arch/arm/plat-omap/clock.h\n+ 0% - 5% arch/arm/mach-omap/common.h -> include/asm-arm/arch-omap/common.h\n+ 2% - 1% arch/arm/mach-omap/dma.c -> arch/arm/plat-omap/dma.c\n+ 0% - 1% arch/arm/mach-omap/fpga.c -> arch/arm/mach-omap1/fpga.c\n+11% -11% arch/arm/mach-omap/gpio.c -> arch/arm/plat-omap/gpio.c\n+ 2% - 2% arch/arm/mach-omap/irq.c -> arch/arm/mach-omap1/irq.c\n+ 0% - 4% arch/arm/mach-omap/leds.c -> arch/arm/mach-omap1/leds.c\n+ 0% - 0% arch/arm/mach-omap/leds-h2p2-debug.c -> arch/arm/mach-omap1/leds-h2p2-debug.c\n+ 0% - 0% arch/arm/mach-omap/leds-innovator.c -> arch/arm/mach-omap1/leds-innovator.c\n+ 0% - 4% arch/arm/mach-omap/leds-osk.c -> arch/arm/mach-omap1/leds-osk.c\n+ 0% -25% arch/arm/mach-omap/Makefile.boot -> arch/arm/mach-omap1/Makefile.boot\n+ 1% - 2% arch/arm/mach-omap/mcbsp.c -> arch/arm/plat-omap/mcbsp.c\n+ 0% - 6% arch/arm/mach-omap/mux.c -> arch/arm/plat-omap/mux.c\n+ 0% - 0% arch/arm/mach-omap/ocpi.c -> arch/arm/plat-omap/ocpi.c\n+ 1% -18% arch/arm/mach-omap/pm.c -> arch/arm/plat-omap/pm.c\n+ 0% -11% arch/arm/mach-omap/sleep.S -> arch/arm/plat-omap/sleep.S\n+ 6% - 4% arch/arm/mach-omap/time.c -> arch/arm/mach-omap1/time.c\n+ 0% - 1% arch/arm/mach-omap/usb.c -> arch/arm/plat-omap/usb.c\n+ 2% - 1% arch/ia64/sn/include/pci/pcibr_provider.h -> include/asm-ia64/sn/pcibr_provider.h\n+ 0% - 2% arch/ia64/sn/include/pci/pic.h -> include/asm-ia64/sn/pic.h\n+ 0% - 0% arch/ia64/sn/include/pci/tiocp.h -> include/asm-ia64/sn/tiocp.h\n+ 3% -23% arch/m68knommu/platform/68VZ328/de2/config.c -> arch/m68knommu/platform/68VZ328/config.c\n+ 1% -18% arch/mips/configs/osprey_defconfig -> arch/mips/configs/qemu_defconfig\n+ 0% -12% arch/mips/vr41xx/zao-capcella/setup.c -> arch/mips/vr41xx/common/type.c\n+ 0% - 0% arch/ppc64/oprofile/op_impl.h -> include/asm-ppc64/oprofile_impl.h\n+ 3% -23% arch/ppc/configs/ash_defconfig -> arch/ppc64/configs/bpa_defconfig\n+ 2% -21% arch/ppc/configs/beech_defconfig -> arch/ppc/configs/ev64360_defconfig\n+ 5% -20% arch/ppc/configs/cedar_defconfig -> arch/ppc/configs/mpc8548_cds_defconfig\n+ 9% -17% arch/ppc/configs/k2_defconfig -> arch/ppc/configs/bamboo_defconfig\n+ 3% -25% arch/ppc/configs/mcpn765_defconfig -> arch/xtensa/configs/common_defconfig\n+ 2% -23% arch/ppc/configs/oak_defconfig -> arch/frv/defconfig\n+ 3% -16% arch/ppc/configs/SM850_defconfig -> arch/ppc/configs/mpc86x_ads_defconfig\n+ 3% -13% arch/ppc/configs/SPD823TS_defconfig -> arch/ppc/configs/mpc885ads_defconfig\n+19% -15% arch/um/kernel/tempfile.c -> arch/um/os-Linux/mem.c\n+ 0% - 5% arch/x86_64/kernel/semaphore.c -> lib/semaphore-sleepers.c\n+ 0% - 6% drivers/i2c/chips/adm1021.c -> drivers/hwmon/adm1021.c\n+ 0% - 4% drivers/i2c/chips/adm1025.c -> drivers/hwmon/adm1025.c\n+ 0% -17% drivers/i2c/chips/adm1026.c -> drivers/hwmon/adm1026.c\n+ 0% - 3% drivers/i2c/chips/adm1031.c -> drivers/hwmon/adm1031.c\n+ 0% - 4% drivers/i2c/chips/asb100.c -> drivers/hwmon/asb100.c\n+ 1% - 4% drivers/i2c/chips/ds1621.c -> drivers/hwmon/ds1621.c\n+ 0% - 1% drivers/i2c/chips/fscher.c -> drivers/hwmon/fscher.c\n+ 0% - 2% drivers/i2c/chips/fscpos.c -> drivers/hwmon/fscpos.c\n+ 0% - 2% drivers/i2c/chips/gl518sm.c -> drivers/hwmon/gl518sm.c\n+ 0% - 2% drivers/i2c/chips/gl520sm.c -> drivers/hwmon/gl520sm.c\n+ 3% -19% drivers/i2c/chips/it87.c -> drivers/hwmon/it87.c\n+ 4% -22% drivers/i2c/chips/lm63.c -> drivers/hwmon/lm63.c\n+ 0% - 6% drivers/i2c/chips/lm75.c -> drivers/hwmon/lm75.c\n+ 0% - 2% drivers/i2c/chips/lm75.h -> drivers/hwmon/lm75.h\n+ 0% - 3% drivers/i2c/chips/lm77.c -> drivers/hwmon/lm77.c\n+ 2% - 5% drivers/i2c/chips/lm78.c -> drivers/hwmon/lm78.c\n+ 0% - 3% drivers/i2c/chips/lm80.c -> drivers/hwmon/lm80.c\n+ 2% -21% drivers/i2c/chips/lm83.c -> drivers/hwmon/lm83.c\n+ 0% - 3% drivers/i2c/chips/lm85.c -> drivers/hwmon/lm85.c\n+ 0% - 4% drivers/i2c/chips/lm87.c -> drivers/hwmon/lm87.c\n+ 4% -20% drivers/i2c/chips/lm90.c -> drivers/hwmon/lm90.c\n+ 0% - 3% drivers/i2c/chips/lm92.c -> drivers/hwmon/lm92.c\n+ 0% - 3% drivers/i2c/chips/max1619.c -> drivers/hwmon/max1619.c\n+ 0% - 7% drivers/i2c/chips/sis5595.c -> drivers/hwmon/sis5595.c\n+ 0% -11% drivers/i2c/chips/smsc47b397.c -> drivers/hwmon/smsc47b397.c\n+ 0% - 9% drivers/i2c/chips/smsc47m1.c -> drivers/hwmon/smsc47m1.c\n+ 0% -23% drivers/i2c/chips/via686a.c -> drivers/hwmon/via686a.c\n+ 0% - 4% drivers/i2c/chips/w83627hf.c -> drivers/hwmon/w83627hf.c\n+ 1% - 5% drivers/i2c/chips/w83781d.c -> drivers/hwmon/w83781d.c\n+ 1% - 3% drivers/i2c/chips/w83l785ts.c -> drivers/hwmon/w83l785ts.c\n+14% -17% drivers/i2c/i2c-sensor-vid.c -> drivers/hwmon/hwmon-vid.c\n+ 0% - 0% drivers/infiniband/include/ib_cache.h -> include/rdma/ib_cache.h\n+ 0% - 3% drivers/infiniband/include/ib_fmr_pool.h -> include/rdma/ib_fmr_pool.h\n+ 9% - 7% drivers/infiniband/include/ib_mad.h -> include/rdma/ib_mad.h\n+ 0% - 0% drivers/infiniband/include/ib_pack.h -> include/rdma/ib_pack.h\n+ 1% - 6% drivers/infiniband/include/ib_sa.h -> include/rdma/ib_sa.h\n+ 0% -11% drivers/infiniband/include/ib_smi.h -> include/rdma/ib_smi.h\n+ 3% - 6% drivers/infiniband/include/ib_user_mad.h -> include/rdma/ib_user_mad.h\n+ 4% - 2% drivers/infiniband/include/ib_verbs.h -> include/rdma/ib_verbs.h\n+ 0% -16% include/asm-ppc64/ioctl.h -> include/asm-powerpc/ioctl.h\n+ 0% - 9% include/asm-ppc64/ioctls.h -> include/asm-powerpc/ioctls.h\n+ 5% - 9% include/asm-ppc64/mc146818rtc.h -> include/asm-powerpc/mc146818rtc.h\n+ 0% - 5% include/asm-ppc64/mman.h -> include/asm-powerpc/mman.h\n+ 2% -25% include/asm-ppc64/sembuf.h -> include/asm-powerpc/sembuf.h\n+ 3% -13% include/asm-ppc64/shmbuf.h -> include/asm-powerpc/shmbuf.h\n+ 0% -15% include/asm-ppc64/sockios.h -> include/asm-powerpc/sockios.h\n+ 1% - 5% include/asm-ppc64/topology.h -> include/asm-powerpc/topology.h\n+ 0% -15% include/asm-ppc64/user.h -> include/asm-powerpc/user.h\n+ 0% -21% include/asm-ppc/agp.h -> include/asm-powerpc/agp.h\n+12% -16% include/asm-ppc/msgbuf.h -> include/asm-xtensa/msgbuf.h\n+ 5% -25% include/asm-ppc/namei.h -> include/asm-powerpc/namei.h\n+ 4% -18% include/asm-ppc/param.h -> include/asm-powerpc/param.h\n+ 0% -13% include/asm-ppc/poll.h -> include/asm-powerpc/poll.h\n+ 0% -24% include/asm-ppc/shmbuf.h -> include/asm-xtensa/shmbuf.h\n+ 1% -17% include/asm-ppc/socket.h -> include/asm-powerpc/socket.h\n+ 0% - 9% include/asm-ppc/string.h -> include/asm-powerpc/string.h\n+ 1% -10% include/asm-ppc/termbits.h -> include/asm-powerpc/termbits.h\n+ 0% - 3% include/asm-ppc/termios.h -> include/asm-powerpc/termios.h\n+ 5% -22% include/asm-ppc/unaligned.h -> include/asm-powerpc/unaligned.h\n\nRegards,\nRutger.\n\n-- \nRutger Nijlunsing ---------------------------------- eludias ed dse.nl\nnever attribute to a conspiracy which can be explained by incompetence\n----------------------------------------------------------------------\n\n#!/usr/bin/env ruby\n\n# Usage: shpatch.rb --help\n\nrequire 'md5'\nrequire 'ostruct'\nrequire 'optparse'\n\n$config = OpenStruct.new\n$config.command = :PATCH\n$config.same_base = false\n$config.same_ext = true\n$config.same_mime = false\n$config.changed_content = true\n$config.max_removed = 25\t# 0 .. 100\n$config.max_added = 50\n$config.verbose = false\n\n# Default dirglobs to ignore\nignore_globs = [\n  \"BitKeeper\", \"PENDING\", \"SCCS\", \"CVS\", \"*.state\", \"*.o\", \"*.a\", \"*.so\",\n  \"*~\", \"#*#\", \"*.orig\", \"*.dll\"\n]\n\n# Option parsing\n$opts = OptionParser.new\n$opts.banner = %Q{\\\nGenerate a shellpatch file, or perform the patch in a shellpatch file.\nA shellpatch file is a patch file which contains shell-commands\nincluding 'mv' and 'patch'.\n\nDetermining the renames uses a lot of heuristics and a brute-force\napproach; your milage may vary. All trivial file renames are handled\nby comparing the complete contents. All remaining files (the list of\nadded and removed files) in then searched through to find matching\npairs: this is quite costly\n\nA cache of md5 sums is kept at the root of the repositories to make\nfinding differences fast.\n\n(c)2005 R. Nijlunsing <shpatch@tux.tmfweb.nl>\nLicense: GPLv2\n\nUsage: shpatch [options]\n\nDefaults options are within [brackets].\n\n}\n$opts.separator(\"Diff options\")\n$opts.on(\"-d\", \"--diff PATH1,PATH2\", Array,\n  \"Generate a shellpatch of the diff\", \"between two directories\") {\n  |paths|\n  if paths.size != 2\n    raise Exception.new(\"Need two directories for --diff\")\n  end\n  $config.command = :DIFF\n  $config.paths = paths\n}\n$opts.separator(\"Diff options for heuristics to finding renames with changed content\")\n$opts.on(\"--[no-]changed-content\",\n  \"Find renames with changed content [#{$config.changed_content}]\" ) { |cc|\n  $config.changed_content = cc\n}\n$opts.on(\"--[no-]same-base\",\n  \"Rename only to files with same basename [#{$config.same_base}]\") { |sb|\n  $config.same_base = sb\n}\n$opts.on(\"--[no-]same-ext\",\n  \"Rename only to same extention [#{$config.same_ext}]\") { |se|\n  $config.same_ext = se\n}\n$opts.on(\"--[no-]same-mime\",\n\t \"Rename only to same mimetype [#{$config.same_mime}]\") { |sm|\n  $config.same_mime = sm\n}\n$opts.on(\"--max-removed PERC\", String,\n  \"Max. percentage of source file which may\",\n  \"be removed while still being considered\",\n  \"a rename [#{$config.max_removed}]\"\n) { |perc| $config.max_removed = perc.to_i }\n$opts.on(\"--max-added PERC\", String,\n  \"Max. percentage of destination file which may\",\n  \"be added while still being considered\",\n  \"a rename [#{$config.max_added}]\"\n) { |perc| $config.max_added = perc.to_i }\n$opts.separator(\"Options to add to current patch\")\n$opts.on(\"--mv SOURCE DEST\", String, String,\n  \"Adds a rename to the current patch\", \"and perform the rename\") {\n  |path1, path2|\n  $config.command = :MV\n  $config.paths = [path1, path2]\n}\n$opts.separator(\"General options\")\n$opts.on(\"--[no-]verbose\", \"-v\", \"Be more verbose\") { |v| $config.verbose = v }\n$opts.on(\"--help\", \"-h\", \"This usage\") { puts $opts; exit 1 }\n%Q{\n\nExamples:\n  shpatch.rb --diff linux-2.6.8,linux-2.6.9 --max-removed 10\n    Generate a shellpatch with renames from directories\n    linux-2.6.8 to linux-2.6.9 . At most 10% of a file may be removed\n    between versions, otherwise they are considered different.\n}.split(\"\\n\").each { |line| $opts.separator(line) }\nbegin\n  $opts.parse!(ARGV)\nrescue Exception\n  puts \"#{$opts}\\n!!! #{$!}\"\n  exit 1\nend\n\nmodule Shell\n  # Escape string string so that it is parsed to the string itself\n  # E.g. Shell.escapeString(\"what's in a name\") = \"what\\'s\\ in\\ a\\ name\"\n  # Compare to Regexp.escape\n  def Shell.escape(string)\n    string.gsub(%r{([^-._0-9a-zA-Z/])}i, '\\\\\\\\\\1')\n  end\nend\n\n# One hunk in the patch\nclass RenameHunk\n  attr_accessor :from, :to\t# Strings: pathname from and to\n\n  def initialize(from, to)\n#    puts \"# Found a rename: #{Shell.escape(from)} -> #{Shell.escape(to)}\"\n    @from = from; @to = to\n  end\n  def command; \"mv\"; end\n  def to_s; \"#{command} #{Shell.escape(@from)} #{Shell.escape(@to)}\"; end\n  def execute(repo)\n    File.rename(\"#{repo.root}/#@from\", \"#{repo.root}/#@to\")\n  end\nend\n\nclass DeleteHunk\n  attr_accessor :pathname\n  def initialize(pathname); @pathname = pathname; end\n  def command; \"rm\"; end\n  def to_s; \"#{command} #{Shell.escape(@pathname)}\"; end\n  def execute(repo); File.delete(\"#{repo.root}/#@pathname\"); end\nend\n\nclass PatchHunk\n  attr_accessor :from, :to, :contents\n  def initialize(repo1, from, repo2, to)\n    @from = from; @to = to\n  end\n  def command; \"patch\"; end\n  def to_s\n    long_from = Shell.escape((from[0] == ?/ ? \"\" : repo1.root + \"/\") + from)\n    long_to = Shell.escape((to[0] == ?/ ? \"\" : repo2.root + \"/\") + to)\n    puts \"# Diffing #{long_from} -> #{long_to}\" if $config.verbose\n    @contents = File.popen(\"diff --unified #{long_from} #{long_to}\") { |io|\n      io.read\n    }\n\n    mark = \"_SHPATCHMARK_\"\n    # Make mark unique\n    mark += rand(10).to_s while @contents.index(mark)\n    \"#{command} <<#{mark}\\n#{@contents}#{mark}\"\n  end\nend\n\n# A filesystem as backing store\nclass FileSystem\n  SHPATCHSTATE_FILE = \".shpatch.state\"\n  SHPATCHSTATE_VERSION_STRING = \"shpatch.rb state version 20050418-2\"\n\n  attr_accessor :root\n  attr_accessor :cache_file # String: filename with signatures\n  attr_accessor :signature_cache # From Fixnum inode to Array [mtime, sig]\n  attr_accessor :signature_cache_changed # Boolean\n\n  # Reads the cache. When not readable in current directory, go\n  # up a level ('..')\n  def read_signatures\n    @signature_cache = {}\n    @signature_cache_changed = false\n    @cache_file = File.expand_path(\"#@root/#{SHPATCHSTATE_FILE}\")\n    cache_file = @cache_file\n    loop {\n      if FileTest.readable?(cache_file)\n\tFile.open(cache_file, \"rb\") do |file|\n\t  version_string = file.readline.chomp\n\t  if version_string == SHPATCHSTATE_VERSION_STRING\n\t    begin\n\t      @signature_cache = Marshal.load(file) \n\t      puts \"# Read signature cache with #{@signature_cache.size} signatures from #{cache_file.inspect}\" if $config.verbose\n\t      @cache_file = cache_file\n\t      break\n\t    rescue ArgumentError, EOFError\n\t      puts \"# (error reading state file: rebuilding file...)\" if $config.verbose\n\t    end\n\t  end\n\tend\n      end\n      parent_cache_file = File.expand_path(\n\tFile.dirname(cache_file) + \"/../\" + File.basename(cache_file)\n      )\n      break if parent_cache_file == cache_file\n      cache_file = parent_cache_file\n    }\n  end\n\n  def initialize(root)\n    raise \"#{root.inspect} does not exist\" if not File.exists?(root)\n    @root = root\n    read_signatures\n  end\n\n  def save_signatures\n    # Save all unsaved signature cache\n    return if !@signature_cache_changed\n    puts \"# Saving #{@signature_cache.size} signatures...\" if $config.verbose\n    pf = @cache_file\n    File.open(\"#{pf}.new\", \"wb+\") do |file|\n      file.puts SHPATCHSTATE_VERSION_STRING\n      Marshal.dump(@signature_cache, file)\n      File.rename(\"#{pf}.new\", pf)\n    end      \n  end\n\n  # Returns array of [mtime, one-line signature-string]\n  def signature(stat, filename)\n    signature = nil\n    key = [stat.dev, stat.ino]\n    cache = @signature_cache[key]\n    if cache and (cache[0] == stat.mtime)\n      signature = cache[1]\n    else\n      if $config.verbose\n\twhy = (cache ? \"#{(stat.mtime - cache[0]).to_i}s out of date\" : \"not indexed\")\n\tputs \"# Creating signature for #{filename.inspect} (#{why})\" \n      end\n      signature = MD5.new(File.read(filename)).digest\n      @signature_cache[key] = [stat.mtime, signature]\n      @signature_cache_changed = true\n    end\n    signature\n  end\n\n  def signature_from(prefix, res, from, ignoreRe)\n    Dir.new(\"#{prefix}#{from}\").entries.each { |elem|\n      next if (elem == \".\") or (elem == \"..\")\n      fullname = \"#{prefix}#{from}/#{elem}\"\n      if not fullname =~ ignoreRe\n\tstat = File.stat(fullname)\n\tif stat.directory?\n\t  signature_from(prefix, res, \"#{from}/#{elem}\", ignoreRe) \n\telse\n\t  rel_filename = \"#{from}/#{elem}\"[1..-1]\n\t  res[rel_filename] = signature(stat, fullname)\n\tend\n      end\n    }\n  end\n\n  # Returns all filenames within this filesystem with all signatures\n  def signatures(ignoreRe)\n    res = {}\n    prefix = File.expand_path(@root)\n    signature_from(prefix, res, \"\", ignoreRe)\n    save_signatures\n    res\n  end\n\n  def mime_type(filename)\n    path = @root + \"/\" + filename\n    ($mime_cache ||= {})[path] ||=\n      File.popen(\"file --mime #{Shell.escape(path)}\") { |io| io.read }.\n      gsub(%r{^.*:}, \"\").strip\n  end\n\n  # Read the contents of a file\n  def read(filename); File.read(@root + \"/\" + filename); end\nend\n\npatch = []\n\ndir1, dir2 = $config.paths\nrepo1 = FileSystem.new(dir1)\nrepo2 = FileSystem.new(dir2)\n\ndef re_from_globs(globs)\n  Regexp.new(\n    \"(\\\\A|/)(\" + globs.collect { |glob| \n       Regexp.escape(glob).gsub(\"\\\\*\", \"[^/]*\")\n    }.join(\"|\") + \")$\"\n  )\nend\n\nignore_globs += [\"BitKeeper/etc/ignore\", \".cvsignore\"].collect { |a|\n  [\"#{dir1}/#{a}\", \"#{dir2}/#{a}\"]\n}.flatten.find_all { |f| File.exists?(f) }.collect { |f|\n  File.readlines(f).collect { |line| line.chomp }\n}.flatten\nignore_globs = ignore_globs.uniq.sort\nignoreRe = re_from_globs(ignore_globs)\n\nputs \"# Retrieving signatures of #{dir1.inspect}\" if $config.verbose\nfile2sig1 = repo1.signatures(ignoreRe)\nputs \"# Retrieving signatures of #{dir2.inspect}\" if $config.verbose\nfile2sig2 = repo2.signatures(ignoreRe)\nfiles1 = file2sig1.keys.sort\nfiles2 = file2sig2.keys.sort\ncommon_files = files1 - (files1 - files2)\n\n# Different hash, same filename: patch\ncommon_files.each { |fname|\n  if file2sig1[fname] != file2sig2[fname]\n    patch << PatchHunk.new(repo1, fname, repo2, fname)\n  end\n  file2sig1.delete(fname)\n  file2sig2.delete(fname)\n}\n\n# Same hash, different filename: rename\nsig2file1 = file2sig1.invert\nsig2file2 = file2sig2.invert\nsigs1 = sig2file1.keys\nsigs2 = sig2file2.keys\ncommon_sigs = sigs1 - (sigs1 - sigs2)\ncommon_sigs.each { |sig|\n  from = sig2file1[sig]\n  to = sig2file2[sig]\n  patch << RenameHunk.new(from, to)\n  sig2file1.delete(sig)\n  sig2file2.delete(sig)\n  file2sig1.delete(from)\n  file2sig2.delete(to)\n}\n\n# statistics of contents of a file. Used for quick-compare\nclass FileContentStats\n  attr_accessor :size\t\t# Size of file in lines\n  attr_accessor :lines\t\t# Hash from String to Fixnum\n\n  # Counter number of lines removed and added as a percentage\n  # of the total file length. These are a measure for the degree\n  # of matching between the files.\n  def diff_match(other)\n    added = 0\n    removed = 0\n    @lines.each_pair { |line, count|\n      delta = other.lines[line] - count\n      if delta > 0\n\tadded += delta\n      else\n\tremoved += -delta\n      end\n    }\n    other.lines.each_pair { |line, count|\n      added += count if not @lines[line]\n    }\n    [added * 100 / other.size, removed * 100 / self.size]\n  end\n\n  def initialize(repo, path)\n    @lines = Hash.new(0)\n    size = 0\n    repo.read(path).delete(\"\\0\").each_line { |line|\n      @lines[line.intern] += 1\n      size += 1\n    }\n    @size = size\n  end\n\n  def self.cached(repo, path)\n    @@cache ||= {}\n    @@cache[[repo, path]] ||= self.new(repo, path)\n  end\nend\n\n# Categorize a file based on filename and/or contents\ndef pool_type(repo, path)\n  res = []\n  res << File.basename(path) if $config.same_base\n  res << File.extname(path) if $config.same_ext\n  res << repo.mime_type(path) if $config.same_mime\n  res\nend\n\n# Determine how much a filename looks like another filename\n# by splitting the filenames into words. Then count the\n# words which are the same.\ndef path_correlation(path1, path2)\n  comp1 = path1.split(%r{[-._/]})\n  comp2 = path2.split(%r{[-._/]})\n  (comp1 - (comp1 - comp2)).size\nend\n\nclass Array\n  # The inverse of an array is an hash from contents to index number.\n  def inverse; res = {}; each_with_index { |e, idx| res[e] = idx }; res; end\nend\n\nif $config.changed_content\n  files1 = file2sig1.keys.sort\n  files2 = file2sig2.keys.sort\n  all_added_files = files2 - files1\n  all_removed_files = files1 - files2\n\n  pools = {}\t\t\t# Group files into 'pools'\n  all_removed_files.each { |removed_file|\n    (pools[pool_type(repo1, removed_file)] ||= [[], []])[0] << removed_file\n  }\n  all_added_files.each { |added_file|\n    (pools[pool_type(repo2, added_file)] ||= [[], []])[1] << added_file\n  }\n\n  pools.each_pair { |key, pool|\n    removed_files, added_files = *pool\n    if $config.verbose and not removed_files.empty? and not added_files.empty?\n      puts \"# Comparing pool type #{key.inspect} with #{pool[0].size}x#{pool[1].size} filepairs\" \n    end\n\n    # Determine how 'special' or 'specific' a word is. We start with\n    # filenames containing special words.\n    words = {}\t\t\t# Group files by 'words'\n    removed_files.each { |removed_file|\n      removed_file.split(%r{[-._/]+}).uniq.each { |word|\n\twords[word] ||= [[], []]\n\twords[word][0] << removed_file\n      }\n    }\n    added_files.each { |added_file|\n      added_file.split(%r{[-._/]+}).uniq.each { |word|\n\twords[word] ||= [[], []]\n\twords[word][1] << added_file\n      }\n    }\n    word_importance = words.keys.find_all { |word|\n      (words[word][0].size * words[word][1].size) > 0\n    }.sort_by { |word|\n      words[word][0].size * words[word][1].size\n    }.reverse\n#    p word_importance\n    word_importance = word_importance.inverse\n    word_importance.default = 0\n\n    removed_files.sort_by { |removed_file|\n      removed_file.split(%r{[-._/]+}).uniq.inject(0) { |s, e|\n\t[s, word_importance[e]].max\n      }\n    }.reverse.each { |removed_file|\n#      puts removed_file\n      removed_file_stats = FileContentStats.new(repo1, removed_file)\n      added_files.sort_by { |f| -path_correlation(removed_file, f) }.\n        each { |added_file|\n\tadded_file_stats = FileContentStats.cached(repo2, added_file)\n\tremoved_size = removed_file_stats.size\n\tadded_size = added_file_stats.size\n\tmin_added = (added_size - removed_size) * 100 / added_size\n\tnext if min_added > $config.max_added\n\tmin_removed = (removed_size - added_size) * 100 / removed_size\n\tnext if min_removed > $config.max_removed\n\t\n\t# Calculate added & removed percentages\n\tadded, removed = removed_file_stats.diff_match(added_file_stats)\n\tif (added <= $config.max_added) && (removed <= $config.max_removed)\n\t  # We found a rename-match!\n\t  puts \"+%2i%% -%2i%% #{removed_file} -> #{added_file}\" % [added, removed] #if $config.verbose\n\t  patch << RenameHunk.new(removed_file, added_file)\n\t  # Don't match again against this added file:\n\t  added_files -= [added_file]\n\t  all_added_files -= [added_file]\n\t  all_removed_files -= [removed_file]\n\t  patch << PatchHunk.new(repo1, removed_file, repo2, added_file)\n\t  break\n\tend\n      }\n    }\n  }\nend\n\nall_added_files.each { |added_file|\n  patch << PatchHunk.new(repo1, \"/dev/null\", repo2, added_file)\n}\nall_removed_files.each { |removed_file|\n  patch << PatchHunk.new(repo1, removed_file, repo2, \"/dev/null\")\n}\n\n#patch.each { |hunk| puts hunk.to_s }\n"},{"id":"17537","messageId":"7virqhq1zf.fsf@assigned-by-dhcp.cox.net","threadId":"3638","inReplyTo":"Pine.LNX.4.64.0603130727350.3618@g5.osdl.org","subject":"Re: Fix up diffcore-rename scoring","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-14T00:55:16Z","receivedAt":"2006-03-14T00:55:16Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> There's a pretty natural terminating character that works well for \n> sources: '\\n'.\n\nGood to know that great minds think alike ;-).  There is a\nversion that did this line-oriented hashing, buried in the next\nbranch.  I'll see how well it performs within the context of the\ncurrent somewhat restructured code.\n"},{"id":"18433","messageId":"DFDDA9C5-D8D2-413F-8A06-4D727C8F9EED@adacore.com","threadId":"3638","inReplyTo":"Pine.LNX.4.64.0603122316160.3618@g5.osdl.org","subject":"Re: Fix up diffcore-rename scoring","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2006-04-06T21:01:04Z","receivedAt":"2006-04-06T21:01:04Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"\nOn Mar 13, 2006, at 02:44, Linus Torvalds wrote:\n> It might be that the fast delta thing is a good way to ask \"is this  \n> even\n> worth considering\", to cut down the O(m*n) rename/copy detection to\n> something much smaller, and then use xdelta() to actually figure  \n> out what\n> is a good rename and what isn't from a much smaller set of potential\n> targets.\n\nHere's a possible way to do that first cut. Basically,\ncompute a short (256-bit) fingerprint for each file, such\nthat the Hamming distance between two fingerprints is a measure\nfor their similarity. I'll include a draft write up below.\n\nMy initial implementation seems reasonably fast, works\ngreat for 4000 (decompressed) files (25M) randomly plucked\nfrom an old git.git repository without packs. It works OK for\ncomparing tar archives for GCC releases, but then it becomes\nclear that random walks aren't that random anymore and\nbecome dominated by repeated information, such as tar headers.\n\nSpeed is about 10MB/sec on my PowerBook, but one could cache\nfingerprints so they only need to be computed once.\nThe nice thing is that one can quickly find similar files\nonly using the fingerprint (and in practice file size),\nno filenames: this seems to fit the git model well.\n\nI'll attach my test implementation below, it uses\nDavid Mazieres Rabinpoly code and D. Phillips's fls code.\nPlease don't mind my C coding, it's not my native language.\nAlso, this may have some Darwinisms, although it should\nwork on Linux too.\n\n   -Geert\n\nEstimating Similarity\n\nFor estimating similarity between strings A and B, let\nSA and SB be the collection of all substrings with length\nW of A and B. Similarity now is defined as the ratio of\nthe intersection and the union of SA and SB.\n\nThe length W of these substrings is the window size, and here is\nchosen somewhat arbitrarily to be 48. The idea is to make them not\nso short that all context is lost (like counting symbol frequencies),\nbut not so long that a few small changes can affect a large portion\nof substrings.  Of course, a single symbol change may affect up to\n48 substrings.\n\nLet \"&\" be the string concatenation operator.\nIf A = S2 & S1 & S2 & S3 & S2, and B = S2 & S3 & S2 & S1 & S2,\nthen if the length of S2 is at least W - 1, the strings\nwill have the same set of substrings and be considered equal\nfor purpose of similarity checking.  This behavior is actually\nwelcome, since reordering sufficiently separated pieces of a\ndocument do not make it substantially different.\n\nInstead of computing the ratio of identical substrings directly,\ncompute a 1-bit hash for each substring and calculate the difference\nbetween the number of zeroes and ones. If the hashes appear random,\nthis difference follows a binomial distribution. Two files are\nconsidered \"likely similar\" if their differences have the same sign.\n\nThe assumption that the hashes are randomly distributed, is not\ntrue if there are many repeated substrings. For most applications,\nit will be sufficient to ignore such repetitions (by using a small\ncache of recently encountered hashes) as they do not convey much\nactual information. For example, for purposes of finding small\ndeltas between strings, duplicating existing text will not significantly\nincrease the delta.\n\nFor a string with N substrings, of which K changed, perform a random\nwalk of N steps in 1-dimensional space (see [1]): what is the  \nprobability\nthe origin was crossed an odd number of times in the last K steps?\nAs the expected distance is Sqrt (2 * N / Pi), this probability\ngets progressively smaller for larger N and a given ratio of N and K.\nFor larger files, the result should be quite stable.\n\n\nIn order to strengthen this similarity check and be able to\nquantify the degree of similarity, many independent 1-bit hashes\nare computed and counted for each string and assembled into\na bit vector of 256 bits, called the fingerprint. Each bit\nof the fingerprint represents the result of independent\nstatistical experiment. For similar strings, corresponding bits\nare more likely to be the same than for random strings.\n\nFor efficiency, a 64-bit hash is computed using a irreducible\nRabin polynomial of degree 63. The algebraic properties\nof these allow for efficient calculation over a sliding window\nof the input. [2] As the cryptographic advantages of randomly\ngenerated hash functions are not required, a fixed polynomial\nhas been chosen.\n\nThis 64-bit hash is expanded to 256 bits by using three bits\nto select 32 of the 256 bits in the fingerprint to update.\nSo, for every 8-bit character the polynomial needs updating,\nand 32 counters are incremented or decremented.\nSo, each of the 256 counters represents a random walk that\nis N / 4, for a string of length N.\n\nThe similarity of A and B can now be expressed as the Hamming\ndistance between the two bit vectors, divided by the expected\ndistance between two random vectors. This similarity score is\na number between 0 and 2, where smaller values mean the strings\nare more similar, and values of 1 or more mean they are dissimilar.\n\nOne of the unique properties of this fingerprint is the\nability to compare files in different locations by only\ntransmitting their fingerprint.\n\n\n"},{"id":"18571","messageId":"7vmzer4vmm.fsf@assigned-by-dhcp.cox.net","threadId":"3638","inReplyTo":"DFDDA9C5-D8D2-413F-8A06-4D727C8F9EED@adacore.com","subject":"Re: Fix up diffcore-rename scoring","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-11T22:04:17Z","receivedAt":"2006-04-11T22:04:17Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Geert Bosch <bosch@adacore.com> writes:\n\n> On Mar 13, 2006, at 02:44, Linus Torvalds wrote:\n>\n>> It might be that the fast delta thing is a good way to ask\n>> \"is this even worth considering\", to cut down the O(m*n)\n>> rename/copy detection to something much smaller, and then use\n>> xdelta() to actually figure out what is a good rename and\n>> what isn't from a much smaller set of potential targets.\n>\n>\n> Here's a possible way to do that first cut. Basically,\n> compute a short (256-bit) fingerprint for each file, such\n> that the Hamming distance between two fingerprints is a measure\n> for their similarity. I'll include a draft write up below.\n\nThanks for starting this.\n\nThere are a few things I need to talk about the way \"similarity\"\nis _used_ in the current algorithms.\n\nRename/copy detection outputs \"similarity\" but I suspect what\nthe algorithm wants is slightly different from what humans think\nof \"similarity\".  It is somewhere between \"similarity\" and\n\"commonness\".  When you are grading a 130-page report a student\nsubmitted, you would want to notice that last 30 pages are\nalmost verbatim copy from somebody else's report.  The student\nin question added 100-page original contents so maybe this is\nnot too bad, but if the report were a 30-page one, and the\nentier 30 pages were borrowed from somebody else's 130-page\nreport, you would _really_ want to notice.\n\nWhile reorganizaing a program, a nontrivial amount of text is\noften removed from an existing file and moved to a newly created\nfile.  Right now, the way similarity score is calculated has a\nheuristical cap to reject two files whose sizes are very\ndifferent, but to detect and show this kind of file split, the\nsizes of files should matter less.\n\nOn the other hand, taking this \"commonness matters\" to its\nextreme is not what we want.  We are producing \"diff\", so if a\n30-line new file was created by moving these 30 lines from\noriginally 130-line file (which is now 100 lines long), showing\nit as \"copy from the-130-line-file\" with a diff to remove\n100-lines is usually not what we want.  That's why the size cap\nmakes sense in rename similarity estimator.\n\nAnother place we use \"similarity\" is to break a file that got\nmodified too much.  This is done for two independent purposes.\n\nOne is to detect a case like this:\n\n\tmv B C\n        mv A B\n        small-edit B\n\nFile B's content is not related to what it had originally, but\nis derived from what was originally in A.  Usually rename/copy\ndetection tries to find rename/copy into files that _disappear_\nfrom the result, but with the above sequence, B never\ndisappears.  By looking at how dissimilar the preimage and\npostimage of B are, we tell the rename/copy detector that B,\nalthough it does not disappear, might have been renamed/copied\nfrom somewhere else.\n\nAnother is to present the final diff output as a complete\nrewrite.  When -B (break) is used without -M (rename) or -C\n(copy), or a file that got a lot of edit and got \"broken\" turned\nout to be purely a total edit (i.e. not renamed/copied from\nsomewhere else), we would present it as diff output that has\nonly one hunk, with bunch of '-' (removal) to remove all\noriginal contents first and then '+' (addition) to add all the\nnew contents, which is often easier to read than ordinary\nunidiff between two unrelated contents that matches up lines\nthat happen to be the same.  Empirically, it seems to give\nbetter result if the \"similarity\" threshold to \"break\" a file\n(i.e. to consider it might have been renamed/copied from\nsomewhere else) is set lower than the threashold to show the\ndiff as a complete rewrite patch.\n\nAlso we can make commonness matter even more in the similarlity\nused to \"break\" a file than rename detector, because if we are\ngoing to break it, we will not have to worry about the issue of\nshowing an annoying diff that removes 100 lines after copying a\n130-line file.  This implies that the break algorithm needs to\nuse two different kinds of similarity, one for breaking and then\nanother for deciding how to show the broken pieces as a diff.\n\nSorry if this write-up does not make much sense.  It ended up\nbeing a lot more incoherent than I hoped it to be.\n\nAnyway, sometime this week I'll find time to play with your code\nmyself.\n"},{"id":"18644","messageId":"C7296176-E37E-4BD3-A33A-36B79BEC8B39@adacore.com","threadId":"3638","inReplyTo":"7vmzer4vmm.fsf@assigned-by-dhcp.cox.net","subject":"Re: Fix up diffcore-rename scoring","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2006-04-14T17:46:56Z","receivedAt":"2006-04-14T17:46:56Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"\nOn Apr 11, 2006, at 18:04, Junio C Hamano wrote:\n>> Here's a possible way to do that first cut. Basically,\n>> compute a short (256-bit) fingerprint for each file, such\n>> that the Hamming distance between two fingerprints is a measure\n>> for their similarity. I'll include a draft write up below.\n>\n> Thanks for starting this.\n>\n> There are a few things I need to talk about the way \"similarity\"\n> is _used_ in the current algorithms.\n>\n> Rename/copy detection outputs \"similarity\" but I suspect what\n> the algorithm wants is slightly different from what humans think\n> of \"similarity\".  It is somewhere between \"similarity\" and\n> \"commonness\".  When you are grading a 130-page report a student\n> submitted, you would want to notice that last 30 pages are\n> almost verbatim copy from somebody else's report.  The student\n> in question added 100-page original contents so maybe this is\n> not too bad, but if the report were a 30-page one, and the\n> entier 30 pages were borrowed from somebody else's 130-page\n> report, you would _really_ want to notice.\n\nThere just isn't enough information in a 256-bit fingerprint\nto be able to determine if two strings have a long common\nsubstring. Also, when the input gets longer, like a few MB,\nor when the input has little information content (compresses\nvery well), statistical bias will reduce reliability.\n\nStill, I used the similarity test on large tar archives, such\nas complete GCC releases, and it does give reasonable\nsimilarity estimates. Non-related inputs rarely have scores\nabove 5.\n\npotomac%../gsimm - \nrd026c470aab28a1086403768a428358f218bba049d47e7d49f8589c2c0baca0c *.tar\n55746560 gcc-2.95.1.tar 123 3.1\n55797760 gcc-2.95.2.tar 112 11.8\n55787520 gcc-2.95.3.tar 112 11.8\n87490560 gcc-3.0.1.tar 112 11.8\n88156160 gcc-3.0.2.tar 78 38.6\n86630400 gcc-3.0.tar 80 37.0\n132495360 gcc-3.1.tar 0 100.0\n\nI'm mostly interested in the data storage aspects of git,\nlooking bottom-up at the blobs stored and deriving information\nfrom that. My similarity estimator allows one to look at thousands\nof large checked in files and quickly identify similar files.\nFor example, in the above case, you'd find it makes sense\nto store gcc-3.1.tar as a difference from gcc-3.0.tar.\nDoing an actual diff between these two archives takes a few\nseconds, while the fingerprints can be compared in microseconds.\n\n> While reorganizaing a program, a nontrivial amount of text is\n> often removed from an existing file and moved to a newly created\n> file.  Right now, the way similarity score is calculated has a\n> heuristical cap to reject two files whose sizes are very\n> different, but to detect and show this kind of file split, the\n> sizes of files should matter less.\nThe way to do this is to split a file at content-determined\nbreakpoints: check the last n bits of a cyclic checksum over\na sliding window, and break if they match a magic number.\nThis would split the file in blocks with expected size of 2^n.\nThen you'd store a fingerprint per chunk.\n> [...]\n> Another place we use \"similarity\" is to break a file that got\n> modified too much.  This is done for two independent purposes.\nThis could be done directly using the given algorithm.\n\n> [...] Usually rename/copy\n> detection tries to find rename/copy into files that _disappear_\n> from the result, but with the above sequence, B never\n> disappears.  By looking at how dissimilar the preimage and\n> postimage of B are, we tell the rename/copy detector that B,\n> although it does not disappear, might have been renamed/copied\n> from somewhere else.\nThis could also be cheaply determined by my similarity estimator.\nAlmost always, you'd have a high similarity score. When there is\na low score, you could verify with a more precise and expensive\nalgorithm to have a consistent decision on what is considered\na break.\n\nThere is a -v option that gives more verbose output, including\nestimated and actual average distances from the origin for the\nrandom walks. For random input they'll be very close, but for\ninput with a lot of repetition the actual average will be far\nlarger. The ratio can be used as a measure of reliability of\nthe fingerprint: ratio's closer to 1 are better.\n> Also we can make commonness matter even more in the similarlity\n> used to \"break\" a file than rename detector, because if we are\n> going to break it, we will not have to worry about the issue of\n> showing an annoying diff that removes 100 lines after copying a\n> 130-line file.  This implies that the break algorithm needs to\n> use two different kinds of similarity, one for breaking and then\n> another for deciding how to show the broken pieces as a diff.\n>\n> Sorry if this write-up does not make much sense.  It ended up\n> being a lot more incoherent than I hoped it to be.\nRegular diff algorithms will always give the most precise result.\nWhat my similarity estimator does is give a probability that\ntwo files have a lot of common substrings. Say, you'd have a\ngit archive with 10,000 blobs of about 1 MB, and you'd want\nto determine how to pack this. You clearly can't use diff\nprograms to solve this, but you can use the estimates.\n\n> Anyway, sometime this week I'll find time to play with your code\n> myself.\nThanks, I'm looking forward to your comments.\n\n   -Geert\n"}]}