QUERY-BY-EXAMPLE IN LARGE-SCALE CODE REPOSITORIES

• US 20150046492A1
• Filed: 08/09/2013
• Published: 02/12/2015
• Est. Priority Date: 08/09/2013
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: BALACHANDRAN, Vipin
• Granted Patent: US 9,317,260 B2
• Time in Patent Office: Days
• US Class Current: 707/772
• 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;

receiving, by the query module, a query snippet;

generating, by the query module, a query syntax structure based on 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, 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.

3. The system of claim 1, wherein the first source code file is associated with a first source syntax structure, and identifying the first source code file from the plurality of source code files comprises:

extracting a source sub-structure from the first syntax structure for matching with a query sub-structure extracted from the query syntax structure;

calculating a first similarity score based on the source sub-structure and the query sub-structure; and

identifying the first source code file upon a first determination that the first similarity score is above a predetermined similarity threshold.

4. The system of claim 3, 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.

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

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 the first similarity score upon a second determination that the matching ratio is above a predetermined matching threshold.

6. The system of claim 3, 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.

7. The system of claim 3, 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.

8. The system of claim 7, 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.

9. The system of claim 1, wherein the first source code file is associated with a first syntax structure, and 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.

10. The system of claim 9, 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.

2. The system of claim 2, 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. 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 plurality of source code files, wherein each of the plurality of source code files is associated with a corresponding plurality of source characteristic vectors generated based on said each of the plurality of source code files;

receiving, by a query module, a query snippet;

generating, by the query module, a plurality of query characteristic vectors based on 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, wherein the being relevant to the query snippet is determined by a first relevance score calculated based on the plurality of query characteristic vectors and the first source code file'"'"'s corresponding plurality of source characteristic vectors.

12. The method of claim 11, wherein the generating the plurality of query characteristic vectors comprises:

generating a syntax structure based on the query snippet, wherein the syntax structure contains a plurality of hierarchical nodes associated with syntactic elements extracted from the query snippet; and

recursively generating the plurality of query characteristic vectors by processing each one of the plurality of hierarchical nodes.

13. The method of claim 11, wherein the first source code file is associated with a first plurality of source characteristic vectors, and identifying the first source code file from the plurality of source code files comprises:

identifying a first source characteristic vector from the first plurality of source characteristic vectors for matching a first query characteristic vector selected from the plurality of query characteristic vectors;

calculating a first similarity score based on the first source characteristic vector and the first query characteristic vector; and

identifying the first source code file upon a first determination that the first similarity score is above a predetermined similarity threshold.

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

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

15. The method of claim 13, wherein the first relevance score is calculated by adjusting the first similarity score based on a first size of a first portion of the first source code file related to the first source characteristic vector, a second size of a second portion of the first source code file that covers the first portion, or a location of the first source code file associated with the first source characteristic vector.

16. The method of claim 13, wherein identifying the first source code file from the plurality of source code files further comprises:

upon a determination that a second source characteristic vector selected from the first plurality of source characteristic vectors covers the first source characteristic vector and matches the first query characteristic vector, calculating the first similarity score based on the second characteristic vector and the first query characteristic vector.

17. The method of claim 13, wherein identifying the first source code file from the plurality of source code files further comprises:

calculating a second similarity score based on a second source characteristic vector selected from the plurality of source characteristic vectors and a second query characteristic vector selected from the plurality of query characteristic vectors;

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.

18. A non-transitory machine readable storage medium embodying computer software, the computer software causing a computer to perform a method, the method comprising

maintaining, by a query module executing on the system, a plurality of source code files, wherein each of the plurality of source code files is associated with a corresponding plurality of source characteristic vectors generated based on said each of the plurality of source code files;

receiving, by a query module, a query snippet;

generating, by the query module, a plurality of query characteristic vectors based on 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, wherein the being relevant to the query snippet is determined by a first relevance score calculated based on the plurality of query characteristic vectors and the first source code file'"'"'s corresponding plurality of source characteristic vectors.

19. The non-transitory machine readable storage medium as recited in claim 18, wherein the first source code file is associated with a first plurality of source characteristic vectors, and identifying the first source code file from the plurality of source code files comprises:

identifying a first source characteristic vector from the first plurality of source characteristic vectors that matches a first query characteristic vector selected from the plurality of query characteristic vectors;

calculating a first similarity score based on the first source characteristic vector and the first query characteristic vector; and

identifying the first source code file upon a first determination that the first similarity score is above a predetermined similarity threshold.

20. The non-transitory machine readable storage medium as recited in claim 19, wherein identifying the first source code file from the plurality of source code files further comprises:

calculating a second similarity score based on a second source characteristic vector selected from the plurality of source characteristic vectors and a second query characteristic vector selected from the plurality of query characteristic vectors;

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 which is calculated based on the query snippet and a second source code file selected from the plurality of the source code files.