Clone Doctor Logo

IntroductionPresentationDownload

Near Miss Clone Detection

  • Compute Unifier/Bindings of all pairs of trees

    • Unifier (�macro�) = shared structure of pair (may be empty)
      • if (a>b+c)� and if (r*bɭ)� has unifier if (#1>#2)�
    • Bindings = substitution converting unifier to instance
      • Bindings #1= a, #2 = b+c gives if (a>b+c)�
      • Bindings #1= r*b, #2 = 1 gives if (r*bɭ)�

  • N^2: Use hashing to control costs

    • Small trees (identifiers) given hash code zero [ICSM98]

    For each tree I and J in same hash bucket
    If CompareTree(I,J)> similarity_threshold
    NoteClonePair(I,J)
    RemoveSubclones(I)
    RemoveSubclones(J)

Previous slide Next slide Back to first slide View graphic version

Morter Logo

Comments or questions: [email protected]