Have block edit distances been computed on large code bases?

Question

There is an enormous mass of source code in this world, and I think it's safe to say that most of this source code was once copied from elsewhere, then modified. There is a decent chance of the (small, incremental) modifications having been made traceable in some kind of version control repository, but the (larger-scale) copying of source code usually isn't traceable in this way.

It would be nice to make it easy to detect it anyway.

As far as I can see, the reason it isn't is ultimately that our paradigm for looking at changes is modelled after diff: we compute changes as a collection of per-character insertions and deletions, disregarding the possibility of using block edit operations such as copy, cut, and paste. This doesn't match actual code development practices, in which blockwise copies, cuts and pastes are all too common. Allowing these, we can take two arbitrary code bases and 'reconstruct' an 'ideal' minimal distance between them, measured in terms of change operations that developers are actually likely to use, which includes cut, copy, and paste. This would allow us to reconstruct an 'ideal' change history in code bases in circumstances where the actual change history is missing (e.g. when no version control system has been used, or when code has been copied verbatim from one code base into another).

There seems to be a sound computational reason that this isn't routinely provided already: it seems too expensive. Even with just per-character insertions and deletions, computing the minimal difference between two arbitrary strings already takes quadratic time in the size of the difference found; diff doesn't evcen attempt to do this perfectly. If we also allow blockwise copies and/or moves at a constant cost, the problem of determining the minimal edit distance between two arbitrary strings becomes NP-complete. However, it has been argued that realistic constraints can be imposed that make the problem quadratic again. (I am linking to this paper, but I haven't actually read it yet.)

My question to you: have you ever seen an application of block edit distance computations (that is, including substring moves and/or deletions and/or copies) in a piece of software built to compare the similarity of two pieces of software? Does there exist a common, widely available tool that supports this? (A diff on steroids.) Or has there been a project to use such a technique to detect copy-and-paste operations within a large base of source code?

(The reason I'm asking is that source code does not at all consist of arbitrary strings. These problems are NP-hard for arbitrary strings, but they may well turn out be in P for source code found in practice.)

Answer 1

I do not know about publicly available tools to do it, but I did fair amount of diff related algorithms and one tool to check similarities between codes.

There are some basics to start with:

0) diff operates well on similar changed texts and falls into worst case when they are different.

1) Tools to check similarities on codes that I have seen, used and written were all operating on AST trees, disregarding formatting, variable and function names. Even though when codes exhibited packaging into functions it gave really hard time. So after that technique like SSA and strip code of functions was applied.

2) Languages that allow same thing to be done in several ways are to be treated as same expressions.

3) Sometimes code is translated into another language. So perfectly working transpilers should exist in first place. Every transpiler I have used was not fully functional, maybe I am not aware of new achievements, but as I checked there is no tool "write in any language you want and get source in any other".

4) There are situations like using well known algorithms, or copying from one book. Also there is probability that two codes are the same, or almost the same (same AST, same language), and are not copied.

5) There might be a lot of false positives, and even if we overcome above problems, what would be the outcome of such search?

There is no tool to produce comparable and working solution to JS. And nowadays many projects are getting JS spin off. Also with tools like emscripten (to operate on LLVM code) makes it virtually impossible to keep track of code.

If you take Levenshtein distance as a measure, you should probably consider above points. This seems convincing to me that it is really not sufficient to start tracking such changes in open source code, as there are tons of them.