Searching code by specifying its behavior

Patent metadata

Field	Value
Publication number	US-8972372-B2
Application number	US-201314111956-A
Country	US
Kind code	B2
Filing date	Apr 17, 2013
Priority date	Apr 17, 2012
Publication date	Mar 3, 2015
Grant date	Mar 3, 2015

Abstract

Systems and methods are disclosed for receiving a first specification that identifies program code behavior associated with a plurality of documents. The specification includes an input-output pair with a first data entity and a second data entity. The systems and methods further include identifying one or more documents, within the plurality of documents, that are configured to (i) use at least a portion of the first data entity as an input to program code associated with particular ones of the documents, and (ii) provide at least a portion of the second data entity as output associated with the program code, wherein the particular ones of the documents correspond to a positive matching between one or more constraints associated with each document and one or more constraints associated with the specification, and generating search results comprising the identified one or more documents.

First claim

What is claimed is:

1. A computer implemented method of providing search results, the method comprising:
receiving a first specification that comprises an input-output pair including a first data entity and a second data entity;
for each module of program code of a plurality of modules of program code, supplying to a constraint solver one or more input-output constraints based on the input-output pair of the first specification and one or more code constraints based on the module of program code;
receiving from the constraint solver, for each module of program code, a result indicating whether the code constraints based on the module of program code are satisfiable with the input-output constraints; and
generating search results referencing one or more modules of program code having a positive result from the constraint solver and providing the search results to a user.

2. The method of claim 1 , wherein the first data entity and the second data entity each comprise multiple and distinct data components.

3. The method of claim 1 , further comprising automatically encoding each of the plurality of modules of program code into code constraints using symbolic analysis of at least a portion of semantics within the module of program code, wherein using symbolic analysis includes characterizing one or more behaviors of the module of program code that would be exhibited by the module when the module is executed.

4. The method of claim 1 , further comprising receiving one or more additional specifications and refining the search results based on the additional specifications; and generating and providing the refined search results to the user.

5. The method of claim 1 , wherein the first data entity and the second data entity are selected from the group consisting of integers, strings, Booleans, characters, files, arrays, lists, maps, and tables.

6. The method of claim 1 , wherein the first data entity includes an input of a first file type and the second data entity includes an output of a second file type.

7. The method of claim 1 , wherein the first data entity is a file and the second data entity is a linked list in which each node of the linked list includes content in the file and one or more additional rows of data.

8. The method of claim 1 , wherein the specification is a Uniform Resource Locator (URL) and the first data entity includes one or more RSS feeds and the second data entity includes a subset of the RSS feeds that match the specification.

9. The method of claim 1 , wherein the first data entity is one or more database tables and the second data entity is a portion of the one or more database tables.

10. The method of claim 1 , wherein the first data entity is an extensible markup language (XML) file type and the second data entity is a Structure Query Language (SQL) file type.

11. The method of claim 1 , wherein the first data entity is a file and the second data entity includes an integer and a Boolean data type.

12. A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:
receiving a first specification that identifies program code behavior associated with a plurality of documents, wherein the specification comprises an input-output pair including a first data entity and a second data entity;
for each module of program code of a plurality of modules of program code, supplying to a constraint solver one or more input-output constraints based on the input-output pair of the first specification and one or more code constraints based on the module of program code;
receiving from the constraint solver, for each module of program code, a result indicating whether the code constraints based on the module of program code are satisfiable with the input-output constraints; and
generating search results referencing one or more modules of program code having a positive result from the constraint solver and providing the search results to a user.

13. The computer-readable medium of claim 12 , the operations further comprising automatically encoding each of the plurality of modules of program code into code constraints using symbolic analysis of at least a portion of semantics within the module of program code, wherein using symbolic analysis includes characterizing one or more behaviors of the module of program code that would be exhibited by the module when the module is executed.

14. The computer-readable medium of claim 12 , wherein the first data entity is a file and the second data entity is a linked list in which each node of the linked list includes content in the file and one or more additional rows of data.

15. The computer-readable medium of claim 12 , wherein the specification is a Uniform Resource Locator (URL) and the first data entity includes one or more RSS feeds and the second data entity includes a subset of the RSS feeds that match the specification.

16. The computer-readable medium of claim 12 , wherein the first data entity is one or more database tables and the second data entity is a portion of the one or more database tables.

17. The computer-readable medium of claim 12 , wherein the first data entity is an extensible markup language (XML) file type and the second data entity is a Structure Query Language (SQL) file type.

18. A system of one or more computers comprising:
a processor; and
a memory storing a plurality of instructions executable by the processor, the instructions including:
an encoder module configured to map each module of program code of a plurality of modules of program code to one or more constraints, and generate mapped program code for each module of program code, the mapping based at least in part on a predetermined behavior for the module of program code that would be exhibited by the module when the module is executed;
a solver module configured to determine whether one or more code constraints based on the mapped program code for a particular module are satisfiable by a constraint solver with one or more input-output constraints of a first specification comprising an input-output pair and identify one or more modules of program code that that have code constraints that are satisfiable with the input-output constraints; and
a refiner module configured to incrementally refine the mapped program code.

19. The electronic system of claim 18 , wherein the encoder module is configured to modify an indexing scheme used by the system for indexing the modules of program code, wherein the modified indexing scheme is based on the predetermined behavior for each module of program code.

20. The electronic system of claim 18 , wherein the system further comprises a constraint relaxer module configured to relax one or more constraints, and wherein the solver module is configured to identify one or more modules of program code that have relaxed code constraints relaxed by the constraint relaxer module that are satisfiable with the input-output constraints.

21. A computer implemented method of providing search results, comprising:
identifying a plurality of documents that are indexed according to a first scheme and associated with a first set of information;
generating a second scheme that associates, based on predefined mapping information, the first set of information with a second set of information;
indexing the plurality of documents according to the second scheme and storing the documents in a repository

Assignees

• Nutech Ventures

Inventors

• Elbaum Sebastian
• Stolee Kathryn

Classifications

• G06F16/951

  Indexing; Web crawling techniques · CPC title

• G06F8/70 Primary

  Software maintenance or management · CPC title

• G06F16/93 Primary

  Document management systems · CPC title

• G06F8/74

  Reverse engineering; Extracting design information from source code · CPC title

• G06F8/36

  Software reuse · CPC title