Discovering and exploiting relationships in software repositories

• US 9,129,038 B2
• Filed: 02/28/2010
• Issued: 09/08/2015
• Est. Priority Date: 07/05/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Begel, Andrew, Zimmermann, Thomas, Venolia, Gina D., Khoo, Yit Phang
• Primary Examiner(s): CHAVIS, JOHN Q
• Application Number:
  US12/714,522
• Publication Number:
  US 20100211924A1
• Time in Patent Office: 2,018 Days
• Field of Search: 717/101
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9038 Presentation of query results
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06F 8/74 Reverse engineering; Extracting design information from source code

Abstract

Software development items can be represented in a graph data structure. Relationships between the represented items can be detected and reflected in the graph data structure. Queries can be run against the data structure to determine which software development items are related to each other. Implicit query can be implemented in a software development context. A graph browser can present panes showing related items.

In some embodiments, a set of regular expressions can be used to identify paths in a graph. Probability scores for the identified paths can be computed. Path data for the identified paths, including the probability scores, can be stored in a searchable location accessible by one or more applications. A query of the path data can be processed to return query results associated with at least one of the identified paths.

Claims

1. A computing device comprising:

one or more hardware processors; and

one or more hardware memory devices or hardware storage devices having instructions stored thereon that, when executed by the one or more hardware processors, cause the one or more hardware processors to;

identify paths in a graph, wherein one or more of the identified paths are defined by a set of regular expressions, nodes of the graph represent software development items and are separated by edges describing relationships between individual nodes, and the one or more of the identified paths have corresponding nodes and corresponding edges arranged consecutively that correlate with one or more corresponding sequences of ordered terms in the set of regular expressions;

compute probability scores for the one or more of the identified paths; and

store path data for the one or more of the identified paths in a searchable location accessible by one or more applications, wherein the path data includes the computed probability scores,

wherein the software development items represented by the nodes of the graph include programming language constructs.

2. The computing device of claim 1, wherein the instructions cause the one or more hardware processors to:

process a query of the path data to identify one or more query results associated with an individual identified path that is defined by an individual regular expression; and

return the one or more query results in response to the query, wherein the one or more query results satisfy one or more terms of the query.

3. The computing device of claim 2, wherein the individual identified path comprises two nodes separated by an intervening node and intervening edges.

4. The computing device of claim 3, wherein one or both of the intervening node or the intervening edges describe a connection between the two nodes in the individual identified path.

5. The computing device of claim 1, wherein the instructions cause the one or more hardware processors to compute the probability scores by computing at least one individual probability score based on a linguistic similarity between two individual paired nodes of the graph.

6. The computing device of claim 5, wherein the instructions cause the one or more hardware processors to compute the probability scores by:

determining an extent of linguistic similarity between the two individual paired nodes; and

based on the extent of linguistic similarity, computing the at least one individual probability score.

7. The computing device of claim 1, wherein the instructions cause the one or more hardware processors to:

process a query of the path data to identify query results associated with at least two of the identified paths; and

rank the at least two of the identified paths based at least in part on one or more of the computed probability scores.

8. The computing device of claim 1, wherein the instructions cause the one or more hardware processors to:

load less than an entirety of the graph in memory before the paths of the graph are identified and before the probability scores are computed.

9. The computing device of claim 1, wherein the instructions cause the one or more hardware processors to:

prune a portion of the nodes of the graph before the paths of the graph are identified.

10. A system comprising:

a graph builder configured to represent software development items as nodes of a graph and to detect relationships between individual nodes of the graph;

a graph analysis module configured to utilize a set of one or more user-defined regular expressions to compute path data for paths of the graph, wherein one or more of the paths are defined by an individual user-defined regular expression, and wherein individual paths comprise two or more of the nodes and at least one edge describing at least one of the relationships;

a query module configured to;

receive a query, and

responsive to receiving the query, search the path data and return query results describing at least one of the paths; and

at least one hardware processor configured to execute the graph builder, the graph analysis module, and the query module.

11. The system of claim 10, wherein the graph analysis module is further configured to:

load a portion of the graph into memory prior to computing the path data;

or

prune one or more nodes of the graph prior to computing the path data.

12. The system of claim 10, wherein the graph analysis module is further configured to compute probability scores for the paths, and wherein at least one of the probability scores is computed based on linguistic similarity between at least two nodes of the at least one path described in the query results.

13. The system of claim 12, wherein the least one path described in the query results comprises a plurality of described paths, and wherein the query module is further configured to rank the plurality of described paths based at least in part on one or more of the probability scores.

14. The system of claim 10, wherein the at least one path described in the query results includes two paired nodes separated by an intervening node and intervening edges, and wherein one or both of the intervening node or the intervening edges describe a connection between the two paired nodes.

15. A method performed by a computing device, the method comprising:

providing path data for a graph based on a set of regular expressions, wherein providing the path data comprises;

identifying paths of the graph, wherein at least one of the identified paths is defined by an individual regular expression of the set, and wherein the identified paths include nodes representing software development items and edges describing relationships between individual nodes,

computing probability scores for individual identified paths,

identifying additional paths, wherein individual identified additional paths comprise two or more of the identified paths, and

computing additional probability scores for the identified additional paths based on the computed probability scores; and

processing a query of the path data to identify query results that satisfy the query,

wherein processing the query comprises ranking multiple nodes to be included in the query results based at least in part on one or more of the computed probability scores or the computed additional probability scores.

16. The method of claim 15, wherein computing the probability scores for the individual identified paths comprises assigning a standard probability score to at least one of the individual identified paths.

17. The method of claim 15, wherein computing the probability scores for the individual identified paths comprises computing individual probability scores for one or more of the individual identified paths based on linguistic similarities between individual paired nodes of the one or more individual identified paths.

18. The method of claim 17, wherein computing the individual probability scores comprises:

determining an extent of textual overlap between the individual paired nodes; and

based on the extent of textual overlap, computing the individual probability scores.

19. The method of claim 15, further comprising restricting access to one or more of the nodes based on a user profile.

20. The method of claim 15, wherein the software development items include a person.

21. The method of claim 15, wherein:

the software development items represented by the nodes of the graph include software developers, object classes, methods, software bugs, code check-ins, and source code changes, and

the relationships described by the edges of the graph indicate that;

a first one of the software development items contains a second one of the software development items,

a third one of the software development items mentions a fourth one of the software development items,

a fifth one of the software development items was sent by a first one of the software developers and received by a second one of the software developers, and

a sixth one of the software development items was authored by a third one of the software developers.