Query-by-example in large-scale code repositories

• US 9,317,260 B2
• Filed: 08/09/2013
• Issued: 04/19/2016
• Est. Priority Date: 08/09/2013
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Balachandran, Vipin
• Primary Examiner(s): Obisesan, Augustine K
• Application Number:
  US13/962,980
• Publication Number:
  US 20150046492A1
• Time in Patent Office: 984 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 8/36 Software reuse

Abstract

Systems and methods for performing query-by-example are described. A query module executing on the system may maintain a source code repository containing a plurality of source code files. Each of the plurality of source code files is associated with a corresponding source syntax structure generated based on said each of the plurality of source code files. The query module may receive a query snippet, and generate a query syntax structure based on the query snippet. The query module may then identify a first source code file from the plurality of source code files for being relevant to the query snippet. The being relevant to the query snippet is determined by a first relevance score which is calculated based on the query syntax structure and the first source code file'"'"'s corresponding source syntax structure.

Claims

1. A system configured to perform query-by-example, the system comprising a processor and a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions for:

maintaining, by a query module executing on the system, a source code repository containing a plurality of source code files, wherein each of the plurality of source code files is associated with a corresponding source syntax structure generated based on said each of the plurality of source code files and representative of a syntactic structure of said each of the plurality of source code files;

receiving, by the query module, a query snippet;

generating, by the query module, a query syntax structure based on the query snippet, wherein the query syntax structure represents a syntactic structure of the query snippet; and

identifying, by the query module, a first source code file from the plurality of source code files for being relevant to the query snippet by;

extracting a source sub-structure from a first syntax structure associated with the first source code file for matching with a query sub-structure extracted from the query syntax structure,

identifying a matching pattern contained in the source sub-structure and in the query sub-structure,

calculating a matching ratio based on the matching pattern, the source sub-structure'"'"'s size, and the query sub-structure'"'"'s size, and

assigning the matching ratio as a first similarity score upon a second determination that the matching ratio is above a predetermined matching threshold, and

identifying the first source code file upon a first determination that the first similarity score is above a predetermined similarity threshold, wherein the being relevant to the query snippet is determined by a first relevance score which is calculated based on the query syntax structure and the first source code file'"'"'s corresponding source syntax structure.

2. The system of claim 1, wherein the query syntax structure is a syntax tree containing a plurality of hierarchical nodes associated with syntactic elements extracted from the query snippet.

3. The system of claim 1, wherein the source sub-structure'"'"'s size and the query sub-structure'"'"'s size are above a predetermined size threshold, and the source sub-structure'"'"'s root node and the query sub-structure'"'"'s root node have a same node type.

4. The system of claim 1, wherein calculating the first similarity score comprises:

calculating the first similarity score by determining a tree edit distance between the source sub-structure and the query sub-structure.

5. The system of claim 1, wherein calculating the first similarity score comprises:

generating a source characteristic vector based on the source sub-structure;

generating a query characteristic vector based on the query sub-structure; and

calculating the first similarity score by determining a Euclidean distance between the source characteristic vector and the query characteristic vector.

6. The system of claim 5, wherein the source characteristic vector is a 1-level characteristic vector, and generating the source characteristic vector comprises:

recursively generating a set of child characteristic vectors for child nodes in the source sub-structure; and

generating the source characteristic vector by accumulating the set of child characteristic vectors.

7. The system of claim 1, wherein identifying the first source code file from the plurality of source code files comprises:

calculating a first similarity score based on a first source sub-structure extracted from the first syntax structure that matches a first query sub-structure extracted from the query syntax structure;

calculating a second similarity score based on a second source sub-structure extracted from the first syntax structure that matches a second query sub-structure extracted from the query syntax structure;

calculating the first relevance score based on the first similarity score and the second similarity score; and

identifying the first source code file upon a determination that the first relevance score is higher than a second relevance score calculated based on the query snippet and a second source code file selected from the plurality of the source code files.

8. The system of claim 7, wherein calculating the first relevance score comprises:

calculating the first relevance score by adjusting the first similarity score based on a first size of the first source sub-structure, a second size of a parent sub-structure of the first source sub-structure, or a location of the first source sub-structure in the first source code file.

9. A method for performing query-by-example, the method being performed in a system comprising a processor and a memory coupled with the processor, the method comprising:

maintaining, by a query module executing on the system, a source code repository containing a plurality of source code files, wherein each of the plurality of source code files is associated with a corresponding source syntax structure generated based on said each of the plurality of source code files and representative of a syntactic structure of said each of the plurality of source code files;

receiving, by the query module, a query snippet;

generating, by the query module, a query syntax structure based on the query snippet, wherein the query syntax structure represents a syntactic structure of the query snippet; and

identifying, by the query module, a first source code file from the plurality of source code files for being relevant to the query snippet by;

extracting a source sub-structure from a first syntax structure associated with the first source code file for matching with a query sub-structure extracted from the query syntax structure,

identifying a matching pattern contained in the source sub-structure and in the query sub-structure,

calculating a matching ratio based on the matching pattern, the source sub-structure'"'"'s size, and the query sub-structure'"'"'s size, and

assigning the matching ratio as a first similarity score upon a second determination that the matching ratio is above a predetermined matching threshold, and

identifying the first source code file upon a first determination that the first similarity score is above a predetermined similarity threshold, wherein the being relevant to the query snippet is determined by a first relevance score which is calculated based on the query syntax structure and the first source code file'"'"'s corresponding source syntax structure.

10. The method of claim 9, wherein the query syntax structure is a syntax tree containing a plurality of hierarchical nodes associated with syntactic elements extracted from the query snippet.

11. The method of claim 9, wherein the source sub-structure'"'"'s size and the query sub-structure'"'"'s size are above a predetermined size threshold, and the source sub-structure'"'"'s root node and the query sub-structure'"'"'s root node have a same node type.

12. The method of claim 9, wherein calculating the first similarity score comprises:

calculating the first similarity score by determining a tree edit distance between the source sub-structure and the query sub-structure.

13. The method of claim 9, wherein calculating the first similarity score comprises:

generating a source characteristic vector based on the source sub-structure;

generating a query characteristic vector based on the query sub-structure; and

calculating the first similarity score by determining a Euclidean distance between the source characteristic vector and the query characteristic vector.

14. The method of claim 13, wherein the source characteristic vector is a 1-level characteristic vector, and generating the source characteristic vector comprises:

recursively generating a set of child characteristic vectors for child nodes in the source sub-structure; and

generating the source characteristic vector by accumulating the set of child characteristic vectors.

15. The method of claim 9, wherein identifying the first source code file from the plurality of source code files comprises:

calculating a first similarity score based on a first source sub-structure extracted from the first syntax structure that matches a first query sub-structure extracted from the query syntax structure;

calculating a second similarity score based on a second source sub-structure extracted from the first syntax structure that matches a second query sub-structure extracted from the query syntax structure;

calculating the first relevance score based on the first similarity score and the second similarity score; and

identifying the first source code file upon a determination that the first relevance score is higher than a second relevance score calculated based on the query snippet and a second source code file selected from the plurality of the source code files.

16. The method of claim 15, wherein calculating the first relevance score comprises:

calculating the first relevance score by adjusting the first similarity score based on a first size of the first source sub-structure, a second size of a parent sub-structure of the first source sub-structure, or a location of the first source sub-structure in the first source code file.

17. A non-transitory computer-readable storage medium that includes a set of instructions which, in response to execution by a processor, cause the processor to perform a method for performing query-by-example, the method being performed in a system comprising a processor and a memory coupled with the processor, the method comprising:

maintaining, by a query module executing on the system, a source code repository containing a plurality of source code files, wherein each of the plurality of source code files is associated with a corresponding source syntax structure generated based on said each of the plurality of source code files and representative of a syntactic structure of said each of the plurality of source code files;

receiving, by the query module, a query snippet;

generating, by the query module, a query syntax structure based on the query snippet, wherein the query syntax structure represents a syntactic structure of the query snippet; and

identifying, by the query module, a first source code file from the plurality of source code files for being relevant to the query snippet by;

extracting a source sub-structure from a first syntax structure associated with the first source code file for matching with a query sub-structure extracted from the query syntax structure,

identifying a matching pattern contained in the source sub-structure and in the query sub-structure,

calculating a matching ratio based on the matching pattern, the source sub-structure'"'"'s size, and the query sub-structure'"'"'s size, and

assigning the matching ratio as a first similarity score upon a second determination that the matching ratio is above a predetermined matching threshold, and identifying the first source code file upon a first determination that the first similarity score is above a predetermined similarity threshold, wherein the being relevant to the query snippet is determined by a first relevance score which is calculated based on the query syntax structure and the first source code file'"'"'s corresponding source syntax structure.

18. The non-transitory computer-readable storage medium of claim 17, wherein calculating the first similarity score comprises:

generating a source characteristic vector based on the source sub-structure;

generating a query characteristic vector based on the query sub-structure; and

calculating the first similarity score by determining a Euclidean distance between the source characteristic vector and the query characteristic vector.

20. The non-transitory computer-readable storage medium of claim 17, wherein identifying the first source code file from the plurality of source code files comprises:

calculating a first similarity score based on a first source sub-structure extracted from the first syntax structure that matches a first query sub-structure extracted from the query syntax structure;

calculating a second similarity score based on a second source sub-structure extracted from the first syntax structure that matches a second query sub-structure extracted from the query syntax structure;

calculating the first relevance score based on the first similarity score and the second similarity score; and

identifying the first source code file upon a determination that the first relevance score is higher than a second relevance score calculated based on the query snippet and a second source code file selected from the plurality of the source code files.

19. The non-transitory computer-readable storage medium 17, wherein the source characteristic vector is a 1-level characteristic vector, and generating the source characteristic vector comprises:

recursively generating a set of child characteristic vectors for child nodes in the source sub-structure; and

generating the source characteristic vector by accumulating the set of child characteristic vectors.