Exact Clone Detection on ASTs/DAGs

1. Parse Source files into Abstract SyntaxTrees (DAGs)

2. For each subtree, hash into a bucket

3. For each subtree i:

If node i marked as subclone, mark i`s children as subclones

If node i marked as clone, done with i

For each subtree j?i in same bucket as i

if EqualTrees(i,j) // can stop on clone children having same clone master

Mark i as (master) clone of i; mark j as clone of i

Mark children(i), children(j) as subclones

4. For each subtree i:

if node(i) marked as clone and node(i) not marked as subclone

Print �Node �,i,� is a clone�, Node(i)

Improvements over Source Line method:

Language parser automatically ignores blanks, comments, linebreaks

Language name resolution (DAG) not confused by identical identifiers

DAG version can unify near-misses written using different names

Can be extended to handle near-misses as parameters

Can be extended to handle simple commutative operations

Integrated into DMS, which can manage detected clones

Previous slide

Next slide

Back to first slide

View graphic version

Comments or questions: [email protected]