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.)