Code-Clone Detection and Analysis

• US 20110246968A1
• Filed: 04/01/2010
• Published: 10/06/2011
• Est. Priority Date: 04/01/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Qiu, Yingjun, Ge, Song, Zhang, Dongmei, Dang, Yingnong
• Granted Patent: US 9,110,769 B2
• Time in Patent Office: Days
• US Class Current: 717/125
• CPC Class Codes: G06F 8/71 Version control security arrangements therefor G06F21/57; Configuration management
• CPC Class Codes: G06F 8/75 Structural analysis for program understanding
• CPC Class Codes: G06F 8/751 Code clone detection

Abstract

Techniques for detecting, analyzing, and/or reporting code clone are described herein. In one or more implementations, clone-code detection is performed on one or more source code bases to find true and near clones of a subject code snippet that a user (e.g., a software developer) expressly or implicitly selected. In one or more other implementations, code clone is analyzed to estimate the code-improvement-potential (such as bug-potential and code-refactoring-potential) properties of clones. One or more other implementations present the results of code clone analysis with indications (e.g., rankings) of the estimated properties of the respective the clones.

Claims

1. A method implemented by one or more computing devices configured to detect and analyze code clone in one or more source code bases, the method comprising:

receiving a selection of a subject code snippet based at least in part upon user input;

at least partly in response to the receiving of the selection, obtaining the subject code snippet;

identifying a group of clone code snippets in the one or more source code bases, each of the identified clone code snippets of the group including a true clone and a near clone of the subject code snippet;

estimating code-improvement-potential properties of one or more of the clone code snippets of the group of found clone code snippets;

ranking at least some of the clone code snippets of the group based at least in part upon one or more of the estimated code-improvement-potential properties; and

causing presentation of the ranked clone code snippets of the group.

2. A method as recited in claim 1, further comprising, before the receiving and the obtaining, preprocessing the one or more source code bases to generate a statement hash dictionary, the preprocessing including:

parsing source code of the one or more source code bases to identify and normalize statements in the source code;

tokenizing the identified and normalized statements by mapping keywords and operators of each statement to a unique token;

indexing the tokenized statements to create an index value for each tokenized statement; and

storing each index value in the statement hash dictionary with an association between the index value of each tokenized statement and one or more locations in the source code where each unique tokenized statement is found,

the identifying of the group of clone code snippets comprises;

utilizing the statement hash dictionary and the subject code snippet to find the group of clone code snippets in the one or more source code bases; and

comparing tokenized statements in the subject code snippet and tokenized statements in the one or more source code bases to find the group of clone code snippets.

3. A method as recited in claim 1, wherein each of the identified clone code snippets of the group has a similarity metric relative to the subject code snippet, the similarity metric of each clone code snippet meeting or exceeding a similarity threshold, the similarity metric of each clone code snippet being calculated in accordance with:

4. A method as recited in claim 1, wherein the finding comprises:

rough-matching the subject code snippet to a list of candidate functions in the one or more source code bases, each candidate function being determined to include one or more possible cloned code snippets that have a likelihood of being a clone or near clone of the subject code snippet based upon a rough-matching calculation of functions in the one or more source code bases, at least some of the one or more possible cloned code snippets having a similarity metric falling below a defined similarity threshold; and

fine-matching the subject code snippet with the list of candidate functions, the fine-matching including identifying the clone code snippets of the group in the list of candidate functions that have the similarity metric that meets and/or exceeds the defined similarity threshold.

5. A method as recited in claim 1, wherein the estimating of the code-improvement-potential properties comprises calculating bug-potential estimation metrics of the clone code snippets of the group, the bug-potential estimation metric of a clone code snippet being a measure of a likelihood that the clone code snippet has one or more bugs.

6. A method as recited in claim 1, wherein the estimating of the code-improvement-potential properties comprises calculating code-refactoring-potential estimation metrics of the clone code snippets of the group, the code-refactoring-potential estimation metric of a clone code snippet being a measure of a likelihood that the clone code snippet is a viable candidate for refactoring.

7. A method as recited in claim 1, further comprising:

comparing statements of the subject code snippet and statements of at least one of the clone code snippets of the group; and

identifying differences, similarities, or both in the statements of the subject code snippet and the at least one of the clone code snippets.

8. A method as recited in claim 1, wherein the causing presentation of the ranked clone code snippets of the group comprises:

concurrently displaying statements of the subject code snippet and statements of at least one of the clone code snippets of the group; and

indicating differences, similarities, or both in the statements of the subject code snippet and the at least one of the clone code snippets.

9. A method as recited in claim 1, wherein the causing presentation of the ranked clone code snippets of the group comprises at least one of the following:

causing to be displayed the presented ranked clone code snippets in an order relative to rankings;

indicating a relative ranking of the presented ranked clone code snippets;

or

providing one or more of the estimated code-improvement-potential properties of each of the presented ranked clone code snippets.

10. A method as recited in claim 1 further comprising receiving user input identifying and confirming code-improvement-potential properties of one or more of the clone code snippets of the one or more source code bases as being immune to code-clone detection.

11. A method as recited in claim 1 further comprising

identifying one or more code snippets of the one or more source code bases as being immune to code-clone detection;

and

excluding the identified immune code snippets from the group of clone code snippets, thereby excluding the identified immune code snippets from one or more of the finding, estimating, ranking, or causing presentation.

12. One or more computer-readable media storing processor-executable instructions that, when executed, cause one or more processors to perform a method comprising:

receiving a selection of a subject code snippet based at least in part upon user input;

at least partly in response to the receiving of the selection, obtaining the subject code snippet;

identifying a group of clone code snippets in one or more source code bases, each of the identified clone code snippets of the group having a similarity metric that meets or exceeds a similarity threshold, the similarity metric of an identified clone code snippet being indicative of a similarity between the identified clone code snippet and the subject code snippet.

13. One or more computer-readable media as recited in claim 12, wherein the identifying comprises:

rough-matching the subject code snippet to a list of candidate functions in the one or more source code bases, each candidate function being determined to include one or more possible cloned code snippets that have a likelihood of being a clone of the subject code snippet based upon a rough-matching calculation of functions in the one or more source code bases, the similarity metric of at least some of the one or more possible cloned code snippets falling below the similarity threshold; and

fine-matching the subject code snippet with the list of candidate functions, the fine-matching including identifying the clone code snippets of the group in the list of candidate functions that have the similarity metric that meets or exceeds the similarity threshold.

14. One or more computer-readable media as recited in claim 12, the method further comprising:

comparing statements of the subject code snippet and statements of at least one of the clone code snippets of the group; and

identifying differences, similarities, or both in the statements of the subject code snippet and the at least one of the clone code snippets.

15. One or more computer-readable media as recited in claim 12, the method further comprising:

concurrently displaying statements of the subject code snippet and statements of at least one of the clone code snippets of the group; and

indicating differences, similarities, or both in the statements of the subject code snippet and the at least one of the clone code snippets.

16. One or more computer-readable media storing processor-executable instructions that, when executed, cause one or more processors to perform a method of analyzing code clone in one or more source code bases, the method comprising:

obtaining a group of clone code snippets, each clone code snippet being a true clone or near clone of a subject code snippet;

estimating code-improvement-potential properties of each of the clone code snippets of the group of clone code snippets; and

causing presentation of at least some of the clone code snippets of the group of the clone code snippets with an indication of the estimated code-improvement-potential properties of the presented clone code snippets.

17. One or more computer-readable media as recited in claim 16, the method further comprising ranking the clone code snippets of the group code clone based at least in part upon one or more of the estimated code-improvement-potential properties.

18. One or more computer-readable media as recited in claim 16, the method further comprising:

comparing statements of the subject code snippet and statements of at least one of the clone code snippets of the group; and

identifying differences, similarities, or both in the statements of the subject code snippet and the at least one of the clone code snippets.

19. One or more computer-readable media as recited in claim 16, wherein the estimating of the code-improvement-potential properties comprises calculating bug-potential estimation metrics of the clone code snippets of the group, the bug-potential estimation metric of a clone code snippet being a measure of a likelihood that the clone code snippet has one or more bugs.

20. One or more computer-readable media as recited in claim 16, wherein the estimating of the code-improvement-potential properties comprises calculating code-refactoring-potential estimation metrics of the clone code snippets of the group, the code-refactoring-potential estimation metric of a clone code snippet being a measure of a likelihood that the specific clone code snippet is a viable candidate for refactoring.