Ovid

Now this is going to be very useful. Thanks Ovid :)

Interesting approach. A few months back i worked on a copy-paste detector that uses the same approach as used for natural text: Levenshtein Distance.

In my case i ran all the relevant code through PPI to get subs and individual code blocks out of the document, then removed noise from them (whitespace, etc.) and then simply compared each text block to all other ones and output them sorted by Levenshtein distance.

It still needs some finetuning and doesn't run all that fast, but with a big body of legacy code already helped me find duplicate blocks that were copy-pasted and subtly altered; for example by changing how the values are returned, or how some vars are named.

I should publicize that sometime.

I have found that when using words as atoms, not chars, we could compute levenstein distance much faster. I think it is applicable to code comparison case.

Here is the function I am using:

 
sub edit_distance {
    my @a = split (/\W+/, lc($_[0]));
    my @b = split (/\W+/, lc($_[1]));
    return scalar(@b) if scalar(@a) == 0;
    return scalar(@a) if scalar(@b) == 0;
    my @r;
    for my $i (0..$#a) {
        $r[$i][0] = $i;
    }
    for my $j (0..$#b) {
        $r[0][$j] = $j;
    }
    for my $i (1..$#a) {
        for my $j (1..$#b) {
            $r[$i][$j] = min(
                $r[$i-1][$j] + 1,
                $r[$i][$j-1] + 1,
                $r[$i-1][$j-1] + ($a[$i] ne $b[$j])
            );

        }
    }
    $r[$#a][$#b];
}

Best regards

I've done something similar, but across multiple programming languages. We typically had multi-gigabyte collections, and precise locations were harder, but the basic approach I used was very different, and probably worth discussing.

First, I worked a line at a time through the files. We couldn't parse, because of the use of different languages. Each line I used a hash (Adler32 for speed) with a little canonicalization of spaces and case. Then I used a rolling hash on the hashes (yes, I know, but it worked) with a window size of about 5, which seemed to be comparable to the PMD CPD -- I know that uses tokens rather than lines, but it was good enough. I could have used a rolling has on tokens directly, but identifying a mostly language independent set of tokens is far from trivial.

I'd planned to write a second pass to validate results, but other tasks took priority as the basics worked. Anyways, with the rolling hash, any collision at all implies a candidate duplicate window, which can then be tested in more detail, now knowing which lines and which files to assess. Using this as a prefilter technique might add a good amount of performance, and also let the process scale. As an interim, we needed to estimate the amount of duplication as a metric, and this approach was sufficient for that, and could process gigabytes as fast as they came off the disk.

I'd intended to roll this from Perl into a pure C utility. That's still in my dev folder, unfortunately.

There are a million variants on edit-distance-like techniques, all under the "sequence alignment" umbrella. I'd actually recommend using a technique that finds the best local alignments between the text and itself, then any promising off-diagonal alignments can be pursued.

I don't see a complete solution to the variable-renaming issue, but perhaps it can be included in the distance metric between string elements.

Finally, duplicate code is closely related to compressibility. If there's a compression algorithm implementation that allows fine-grained inspection of the compression tables & their statistics, that might be a fruitful area too.