Bug #31624 for Perl-Critic: Policy suggestion : identify similar/duplicate code for refactoring

My, you don't think small, do you? Care to submit an implementation of this policy? Yes, this is a good idea, but it'll take a decent amount of effort to do it.

I'll try to think about this a little over the next couple of week, at least on an algorithmic level. My initial thought is that you can read in each Perl document, strip comments and whitespace, and then walk the PDOM tree (not yet clear to me how to do this), and simply use each subtree (maybe above a certain size) as a hash key, and push a structure recording various attributes about that subtree onto the value. When you encounter a PDOM subtree with the same structure again, you will know that you already have a key that matches, so you can push a new value on for that hash key recording the attributes about this subtree. Once you've been been through all the documents in the distribution, you can then iterate over the hash doing more fine grained comparisons of the subtrees whose structures were the same, to see if they really are similar. I have no idea yet whether this is even remotely close to an idea that might work, but if I get time will see if I can come up with a toy implementation. On Dec 17, 2007, at 8:02 PM, ELLIOTJS via RT wrote: Show quoted text

I think it would probably be better to implement this as a stand-alone tool. We could probably wrap it with a test module, similar to Test::Perl::Critic. I've been looking at the source code for CPD. From my initial investigation, it appears that it only looks for exact duplicates among blocks of code. So I think changing a variable name in an otherwise duplicate block would constitute "different" code. I'm not yet sure how CPD figures out the appropriate block size (e.g once it finds a matching line, does it just keep appending lines until they don't match anymore). I think we could improve upon this in a couple ways. First, we can normalize things like variable names (and possibly literal strings) so the comparison will focus on semantic duplication. Second, we could compute a score (e.g. from 1 to 100) that indicates how strong the match is. There's a lot of literature on finding plagiarism in documents, which is a very similar problem. If you happen to find a particularly useful discussion or algorithm, please send me a link. -Jeff