Patent Description:
There are many software development tools available to assist a software developer to develop source code. Often these tools do not provide enough support to find existing code fragments that can be used to create code for an intended purpose. <NPL>, describes discovering regularities in source code is of great interest to software engineers, both in academia and in industry, as regularities can provide useful information to help in a variety of tasks such as code comprehension, code refactoring, and fault localisation. However, traditional pattern mining algorithms often find too many patterns of little use and hence are not suitable for discovering useful regularities. "<NPL>, describes in general, for frequent pattern mining problems, the candidate enumeration process exhaustively enumerates all possible combinations of itemsets that are a subset of a given database. This process is known to be very expensive since, in many circumstances, the number of candidates to enumerate is quite large, and also the frequent patterns present in real-world data can be fairly long. Efficient techniques attacking different issues and problems relevant to the enumeration problem are therefore highly sought after. In addition to the enumeration problem, another important problem of frequent pattern mining is to efficiently count and prune away any itemsets discovered to be infrequent. Due to the large number of candidates that can be generated from the vast amount of data, an efficient and scalable counting approach is critically important. Another problem when extracting all frequent subtrees from a complex tree database, is that the number of patterns presented to the user can be very large, thereby making the results hard to analyze and gain insights from.

<NPL>, discloses a framework for offering recommendations to novice programmers solving a particular programming problem. The programming problem is created by the instructor who also "creates/finds different implementations of the programming problem. In an example a knowledge base of <NUM> different algorithms is built. This document teaches that the framework offers recommendations using markers based on the best matching target implementation. The best matching target implementation is determined by generating an abstract syntax tree (AST) for each target implementation and minimising a distance from a source tree to the target tree.

Source code programs are mined to discover previously unknown patterns that may be used in the development of source code. The source code patterns or idioms are detected from the application of a data mining technique applied to methods of various source code programs. The large corpus of methods from these source code programs are converted into simplified trees that represent the syntactic structure and semantic data of a method. The data mining technique detects closed and maximal frequent subtrees from the simplified trees which represent the largest frequently-occurring patterns. These patterns are matched with methods that have a similar syntactic structure and which use similar types and method calls.

Aspects of the present invention pertain to data mining source code programs for frequently-used source code patterns or idioms from a large corpus of existing source code. Data mining is the process of discovering previously unknown patterns in large datasets. In one aspect, a data mining technique is applied to detect patterns in source code methods that may be used in other methods having a similar syntactic structure, and similar type and method usage. Simplified trees that represent the syntactic structure and type and method usage of a source code fragment, such as a method, are mined to find closed and maximal frequent subtrees. These subtrees represent the largest frequently-occurring patterns that are associated with a particular type and method usage. These patterns are then used in an idiom web service and/or a code completion system to assist users (e.g., developers, customers, clients, etc.) in the development of source code programs.

Attention now turns to a further discussion of the system, devices, components, and methods utilized in mining for source code patterns.

<FIG> illustrates a block diagram of an exemplary system <NUM> in which various aspects of the invention may be practiced. In one aspect, system <NUM> includes a simplified tree generation phase <NUM> and a frequent subtree mining phase <NUM>. The simplified tree generation phase <NUM> generates simplified trees representing the syntax structure and semantic properties of various methods taken from a large corpus of source code programs. The frequent subtree mining phase <NUM> mines the simplified trees to detect closed and maximal frequent subtrees representing large patterns that occur frequently. These patterns are represented in pattern trees.

In the simplified tree generation phase <NUM>, a source code extraction component <NUM> extracts source code programs <NUM> from a source code repository <NUM>. A static code analyzer <NUM> (e.g., parser, front-end compiler, language compiler) parses the selected source code programs <NUM> to generate a corresponding syntax tree and a semantic model <NUM>.

The source code repository <NUM> may be a file archive and web hosting facility that stores large amounts of source code either privately or publicly. The source code repository <NUM> can be structured as a version control system, such as GIT, Mercurial, etc. The source code programs residing in the source code repository <NUM> vary and may be written in different programming languages.

The source code extraction component <NUM> obtains several selected source code programs <NUM> which may be written in the same or different programming languages. A programming language utilizes a context-free grammar that is a set of rules that describe all possible strings in a formal programming language. The selected source code programs <NUM> can come from different domains, such as without limitation, scientific computing, web development, dataflow programming, machine learning, and the like.

In one aspect, the static code analyzer <NUM> generates an abstract syntax tree (AST) <NUM> for each method in each selected source code program. An AST is a tree that represents the abstract syntactic structure of a language construct in the grammar of the programming language of the program, where each interior node and the root node represent an operator and the children of the root and interior nodes represent the operands of that operator. The syntax tree is augmented with the semantic properties of each code construct.

The static code analyzer <NUM> generates a semantic model for the AST <NUM>. The semantic model includes all the semantic information about the program. The semantic model includes information on the symbols referenced at a specific location in the program. Every namespace, type, method, property, field, event, parameter, label, and local variable maybe represented by a symbol. Symbols may also include additional information that a static code analyzer determines from the program, such as methods and properties associated with the symbol. The semantic model encapsulates all this data into the AST.

The abstract syntax tree is then trimmed by an AST trimmer <NUM> into a simplified tree which is a more abstract representation of the AST. An AST is a sparse and compact representation of a parse tree. Data mining an AST is more difficult due to the sparsity of the data in the AST. For this reason, the AST trimmer <NUM> trims the AST into a more abstract tree, referred to as simplified tree <NUM>, by supplementing the AST with the semantic data from the semantic model. The AST trimmer <NUM> generates metadata containing the location of the source code program (e.g., URL, etc.) represented by AST. The simplified trees <NUM> and their associated metadata are stored in a simplified tree repository <NUM>.

The simplified tree repository <NUM> may retrieve an input query <NUM> to generate frequently-requested pattern trees that match the specifications of the input query <NUM>. These pattern trees are generated to those applications and services that utilize pattern trees from a particular domain. Simplified trees that correspond to an input query are found and processed in the frequent subtree mining phase <NUM>.

The frequent mining phase <NUM> includes a pre-processing component <NUM>, a frequent subtree mining component <NUM>, and a post-processing component <NUM>. The pre-processing component <NUM> filters out data in the simplified tree, further trims the tree, and/or group the trees into clusters. Simplified trees corresponding to small methods, methods that are too large to process, or methods that appear to be automatically-generated may be eliminated by the pre-processing component <NUM>.

The frequent subtree mining component <NUM> searches for closed and maximal frequent subtrees across a set of simplified trees, T. A maximal frequent subtree is a frequent subtree that is not part of any other frequent subtree. Given a set of simplified trees, referred to as the training data set of trees, the support of a simplified tree, T, is defined as a fraction of the trees in T in which T occurs. A simplified tree, T, is frequent if its support is at least a user-specified threshold. A frequent subtree t is maximal if none of its supertrees are frequent. Support refers to the frequency of a subtree amongst all the trees in the set of simplified trees. A frequent subtree is closed when none of its supertrees has the same support.

The frequent subtree mining component <NUM> generates a number of closed and maximal frequent subtrees. The post-processing component <NUM> filters out duplicate subtrees, or merges similar trees, and stores the resulting subtrees as the pattern trees which are stored in a pattern tree storage <NUM>. In addition, the post-processing component <NUM> deletes subtrees that do not have nodes representing types or method invocations. The frequent subtree mining phase <NUM> generates subtrees having nodes that include methods/APIs and types that can be matched to simplified trees containing nodes with similar methods/APIs and types. Types and method/API invocations are the most frequently-used code constructs of a program and are a more robust source of idioms.

For each pattern tree in the pattern tree storage <NUM>, an entry includes a pattern tree, a type index, one or more method name indices, a count, and a source <NUM>. The count represents the number of times the pattern is found amongst all the simplified trees in the simplified tree repository <NUM>, the type index represents the type associated with the pattern tree, the method indices represent the method names associated with the pattern tree, and the source indicates the location of the source code program from which the pattern tree was generated. The source may include a Uniform Resource Locator (URL), repository name, project name, file name, etc..

<FIG> illustrates an exemplary code completion system <NUM> that utilizes the pattern trees. In one or more aspects, code completion may be a function or feature integrated into a software development environment or tool, such as a source code editor and/or integrated development environment (IDE). Code completion may be embodied as a tool or feature that can be an add-on, plug-in, extension and/or component of a source code editor, IDE, or combination thereof.

In one aspect, a source code editor <NUM> may include a user interface <NUM> and a parser <NUM>. The user interface <NUM> includes a set of features or functions for writing and editing a source code program. The user interface <NUM> may utilize a pop-up window to present a list of code snippets to finish a program construct. A developer may browse through the code snippet candidates and select one from the list. In this manner, the code completion system <NUM> serves as documentation in addition to being an assistance to writing code quickly.

In one aspect, the parser <NUM> reads the source code entered into the source code editor <NUM> for a method and generates a corresponding abstract syntax tree for the source code of the method. The parser <NUM> continuously updates the abstract syntax tree as the developer creates and edits the source code of the method in the source code editor <NUM>.

At certain points in the editing process, the user interface <NUM> will detect that the user has entered a particular character which will initiate code completion. In one aspect, the character that initiates code completion, or marker character, may be an end-of-line character. The end-of-line character indicates that the current line of code is finished and that the cursor is positioned at a new line in the source code editor. The user interface <NUM> will then request code snippet candidates from the code completion component <NUM> to present to the developer.

Upon detection of the marker character, the code completion component <NUM> receives a query <NUM> containing the abstract syntax tree and semantic model representing a code fragment of the source code program in the source code editor <NUM>. In one aspect, the code fragment is the current method being developed in the source code editor <NUM>. The code completion component <NUM> uses the AST trimmer <NUM> to generate a corresponding simplified tree <NUM>. The simplified tree <NUM> is used as the query <NUM> for the pattern search component <NUM> to search the serialized pattern tree storage <NUM> for matching pattern trees <NUM>.

The matched pattern trees <NUM> are then converted into code snippets by the pattern-to-code transformer <NUM> using the content of the query <NUM> to customize variables and arguments with local variables from the query <NUM>. The code snippet candidates <NUM> are then returned back to the user interface <NUM> of the source code editor <NUM> which provides the code snippets to the developer.

<FIG> illustrates an exemplary idiom web service that utilizes the pattern trees. A code idiom or idiom is a frequently occurring source code pattern. The idiom web service <NUM> provides a service that returns code snippets associated with the types and methods specified in the query. In one or more aspects, a software development tool, such as an development environment (e.g., source code editor, IDE) <NUM>, may interact, through a network, with the idiom web service <NUM> to obtain code snippets that contain the types and methods contained in a current context of the source code being developed in the development environment <NUM>. The development environment <NUM> may include an idiom web service extension <NUM> that facilitates communication with the idiom web service <NUM>.

It should be noted that the disclosure is not limited to the use of a development environment interacting with the idiom web service and that any application and/or device may request code snippets for any set or combination of types and methods.

Furthermore, the term "method" is to include Application Programing Interface (API), function, and procedure. A type is a data attribute that indicates the intended use of the data. The term "type" is based on the type system of a programming language. For example, in a strongly-typed programming language, such as C#, the type system includes value types and reference types. A value type has its own copy of the data and a reference type stores a reference to the data. Value types in C# include simple type, enum types, struct types, and nullable value types. Reference types in C# include class types, interface types, array types and delegate types. A class type defines a data structure that contains data members, such as fields, and function members, such as methods and properties. In one aspect of the disclosure, a "type" pertains to a class type or object-oriented classes. "Type usage" refers to the manner in which a class is utilized, such as creating objects of a class, calling methods from a class, and interacting with other classes. However, it should be noted that the disclosure is not limited to just class-based types and may be applied to any other code constructs or combinations thereof.

The goal of the idiom web service <NUM> is to find patterns of code that occur commonly across other methods that have a similar context to the code being edited. For example, if a developer is writing a method that receives a string of text and a FileStream as parameters, the idiom web service <NUM> will return common code patterns that write text to a file.

Initially, a context query <NUM> is sent to the idiom web service <NUM> to find out which types and methods of interest occur frequently together. The context query <NUM> contains the types and methods of interest (i.e., context) and the idiom web service <NUM> returns a count of the number of times the requested types and methods occur frequently together.

The idiom web service <NUM> includes an idiom search component <NUM>, a cache pattern tree storage <NUM>, and a batched query list <NUM>. The idiom web service <NUM> receives the request for the count of the number of times the requested types and methods occur together <NUM> and returns back the counts of how often the types and methods are found in a pattern tree using the cache pattern tree storage <NUM>. The cache pattern tree storage <NUM> has the same data format as described in pattern tree storage <NUM> in <FIG>.

The most frequently occurring sets of types and methods form the basis for the idiom search query <NUM>. The idiom search query <NUM> contains a set of types and methods selected by the development environment <NUM> for the idiom web service <NUM> to produce the associated patterns. The idiom search component <NUM> searches the cache pattern tree storage <NUM> for patterns or idioms <NUM> matching the types and methods of the query <NUM>. If none are found, then the idiom search component <NUM> returns a response indicating that none are found and query <NUM> is stored in the batched query list <NUM>. The batched query list <NUM> contains the missed queries <NUM> that were not found. At periodic intervals, the batched queries and any other queries are mined to generate pattern trees and related data that are added to the idiom web service's cache pattern tree storage <NUM>. Otherwise, the idiom search component <NUM> returns each idiom or pattern and its respective location or source <NUM>.

Attention now turns to a description of the various exemplary methods that utilize the system and devices disclosed herein. Operations for the aspects may be further described with reference to various exemplary methods. It may be appreciated that the representative methods do not necessarily have to be executed in the order presented, or in any particular order, unless otherwise indicated. Moreover, various activities described with respect to the methods can be executed in serial or parallel fashion, or any combination of serial and parallel operations. In one or more aspects, the method illustrates operations for the systems and devices disclosed herein.

<FIG> illustrates an exemplary method for generating closed and maximal frequent subtrees. Referring to <FIG> and <FIG>, source code programs are selected from one or more source code repositories <NUM> as the code samples (block <NUM>). Each method of each program is parsed by the static code analyzer <NUM> into a respective abstract syntax tree and semantic model <NUM>. The abstract syntax tree is augmented with its semantic model (e.g., type information, method/API names) (block <NUM>). Each abstract syntax tree is trimmed (block <NUM>) to generate a corresponding simplified tree (block <NUM>).

The simplified trees are mined to generate closed and maximal frequent subtrees (block <NUM>) which are then stored as pattern trees in a respective pattern tree storage (block <NUM>). In one aspect, a user may designate the type of mined subtree, such as closed, maximal frequent, or closed and maximal frequent subtrees. The pattern tree storage <NUM> includes a count for each pattern tree that represents how often the pattern is found overall in the pattern trees in the pattern tree storage <NUM> (block <NUM>). In addition, the pattern tree storage <NUM> includes a type index and method indices for each pattern tree along with the source of the program from which the pattern tree was derived (block <NUM>). The pattern trees may then be deployed to an idiom web service (block <NUM>) and/or into a code completion system (block <NUM>).

For the code completion system, the pattern trees need to be accessed quickly. For this reason, the pattern trees are serialized into a single file, such as a JavaScript Object Notation (JSON) file, and accessed as attribute-value pairs. The JSON file will also contain a source code string representing the locations of the corresponding source code, the methods/APIs used in the pattern, and the namespaces used in the pattern for each pattern tree Hence, the JSON file will contain many patterns and their respective information. Each pattern has a pattern tree, several URL locations since a pattern may be found in different URL locations, namespaces used in the pattern, and the methods/APIs used in the pattern. (Collectively, block <NUM>).

Attention now turns to an exemplary method <NUM> of mining the simplified trees for closed and maximal frequent subtrees. The problem of subtree mining is to find the frequently occurring subtrees that satisfy the conditions of frequency, maximal, and closure. A subtree is frequent if its support adheres to the user-specified threshold. A frequent subtree is closed if none of its super trees have the same support. A frequent subtree is maximal if none of its super trees is frequent. A super tree is a larger tree that contains a frequent subtree.

Turning to <FIG> and <FIG>, the frequent subtree mining component <NUM> obtains the data mining parameters, such as the user-specified support threshold (block <NUM>). The frequent subtree mining component <NUM> then determines the frequent subtrees by finding the single-node trees of the simplified trees that satisfy the support threshold (block <NUM>). A single-node tree is a root or interior node of a simplified tree.

From the set of frequent subtrees, the frequent subtree mining component <NUM> expands those frequent subtrees until the closure condition and/or maximal condition is satisfied (block <NUM>). For each frequent subtree (block <NUM>), the frequent subtree is expanded or grown into a number of possible subtrees (block <NUM>). Each of the possible subtrees is grown independently and in parallel with all the other subtrees by adding one node at a time until the subtree satisfies the closure and/or maximal condition (block <NUM>). The frequency counts of a subtree occurring in a source tree are accumulated (block <NUM>). The frequent subtrees having satisfied the closure and/or maximal condition are then output as the pattern trees (block <NUM>).

Attention now turns to an exemplary method <NUM> of a code completion system utilizing the closed and maximal frequent subtrees. Referring to <FIG> and <FIG>, initially, the source code editor <NUM> is configured with a code completion system that uses closed and maximal frequent subtrees (block <NUM>). In one aspect, the code completion system <NUM> may be configured as an extension to the source code editor <NUM> as an auxiliary executable file having additional capabilities. The extension may be implemented as an add-on or plugin, such as a Dynamic Link Library (DLL).

The source code editor <NUM> continuously tracks the source code that is input and displayed in the user interface <NUM>. The parser <NUM> formats the source code into an augmented abstract syntax tree having type information. In one aspect, the source code editor <NUM> tracks the source code of a method that is currently under development. (Collectively, block <NUM>).

Upon detection of a marker character, the augmented abstract syntax tree is sent to the code completion system <NUM> for code snippet candidates <NUM> (block <NUM>). The AST trimmer <NUM> generates a simplified tree <NUM> from the abstract syntax tree contained in the query <NUM> (block <NUM>). The pattern search component <NUM> searches for similar trees in the serialized pattern tree storage <NUM> (block <NUM>). Those trees having the same types and method invocations as the simplified tree are accessed through the type and method indices in the serialized pattern tree storage (block <NUM>). A threshold amount of pattern trees is considered based on the top closest matches (block <NUM>).

For the closest matching pattern trees, the top few branches of those pattern trees are matched with the last few branches of the code query's simplified tree. The pattern contained in the remaining portion of the pattern tree is converted into a code snippet (block <NUM>) The pattern-to-code transformer <NUM> transforms each of the matched pattern trees <NUM> into a code snippet using the local data contained in the query <NUM> (block <NUM>). The code snippet candidates <NUM> are then returned to the source code editor <NUM> (block <NUM>).

Attention now turns to an exemplary method <NUM> of an idiom web service utilizing the pattern trees. Turning to <FIG> and <FIG>, the idiom web service <NUM> is configured with the pattern trees that represent the most frequently-used types and methods. The cache pattern tree storage <NUM> is loaded with this data so that the idiom web service <NUM> is able to respond quickly to the queries it receives. An offline process is used to generate pattern trees and the associated data (types, methods, counts) for the most likely contexts that the developers will encounter (block <NUM>). This is done by looking at the contexts that occur most frequently in the source code programs that have already been mined.

For example, the top <NUM>,<NUM> frequently-used types across the mined source code programs are each made into a query. Each query contains a context of just one type. Then the top <NUM>,<NUM> frequently-called methods are used to create <NUM>,<NUM> more queries in the same way. Next the top <NUM>,<NUM> frequent pairs of co-occurring types are used to create queries. For example, if FileStream and TextWriter are the two types that are used together the most across all methods in the set of source code programs, then a query that includes these two types is created to be processed. Then the second most frequently co-occurring pair of types is determined and a query is created. This is done also for the top <NUM>,<NUM> frequent pairs of method calls. Finally, queries for the <NUM>,<NUM> most frequent triples of types that co-occur are created and the <NUM>,<NUM> most frequent triples of method calls.

Once the queries are generated, each query is used to extract matching simplified trees from the simplified tree repository <NUM> which are input into the frequent subtree mining phase <NUM>. The frequent subtree mining phase <NUM> will generate the pattern trees and the associated types, methods, and counts that will be used to prime the cache pattern tree storage <NUM> (block <NUM>). The development environment <NUM> that interacts with the idiom web service is configured with an extension <NUM> that facilitates the communications between the development environment <NUM> and the idiom web service <NUM> (block <NUM>).

The idiom web service <NUM> receives a request from the development environment <NUM> seeking a count of how often the methods and types contained in a query occur in another method (block <NUM>). The idiom web service <NUM> searches the cache pattern tree storage <NUM> for this information and returns the counts (block <NUM>).

The idiom web service <NUM> may receive a second query <NUM> requesting methods that use a specific set of types and methods (block <NUM>). The idiom search component <NUM> searches the cache pattern tree storage <NUM> and if found, returns the set of methods that contain the corresponding pattern tree as well as the source location for each method (block <NUM>). If the idiom search component <NUM> fails to find the requested types and methods, the query is placed in the batched query list <NUM> (block <NUM>). At periodic intervals, the queries in the batched query list <NUM> are mined to generate pattern trees that are added to the cache pattern tree storage <NUM> (block <NUM>).

Attention now turns to <FIG>, <FIG>, <FIG> and <FIG> which illustrate aspects of the frequent source code pattern mining. <FIG> illustrates an exemplary source code fragment of a PreloadTables method <NUM> written in the C# programming language. The code fragment <NUM> includes the method declaration statement <NUM> which identifies the method name as PreloadTables. There are two string variables, connectionString and query String, that are declared in statements <NUM>, <NUM>. The using statement <NUM> includes an instantiation of a connection object that is assigned the result of the method invocation SqlConnection. The SqlConnection method is invoked with the parameter connectionString. The using statement <NUM> invokes the method connection. Open() <NUM>.

<FIG> illustrates an exemplary simplified tree <NUM> for the PreloadTables method. The simplified tree <NUM> contains a root node <NUM>, several interior nodes <NUM> - <NUM>, <NUM>-<NUM> and leaf nodes <NUM>, <NUM>, <NUM>-<NUM>. Each node in the simplified tree <NUM> contains a label that identifies a code construct found in the source code. The simplified tree <NUM> contains type information describing the classes associated with various code constructs. For example, node <NUM> represents that the type of the argument used in the object instantiation is a string. In addition, the simplified tree represents the syntactic structure of the PreloadTables method.

<FIG> illustrates an exemplary pattern tree <NUM>. The pattern tree <NUM> contains a root node <NUM>, a first subtree <NUM> shown in <FIG> and a second subtree shown in <FIG>.

<FIG> illustrates the use of the pattern tree for code completion. An exemplary display <NUM> is shown having a user interface <NUM> in which a user's source code is being developed. The source code under development is the PreloadTables method. The code completion system transforms the PreloadTables method shown in user interface <NUM> into the simplified tree <NUM> shown in <FIG>. The pattern tree, shown in <FIG>, is found as a matched pattern with the simplified tree. The pattern tree is matched with the simplified tree <NUM> and finds that subtree <NUM> is a subtree of the user's simplified tree <NUM>. This match indicates that code fragment <NUM> in code fragment <NUM> already exists in a portion <NUM> of the user's PreloadTables() method. The subtree <NUM> shown in <FIG> is then displayed as a code snippet candidate <NUM> to be inserted at location <NUM>.

Attention now turns to a discussion of the exemplary operating environments. <FIG> illustrates an exemplary operating environment of a frequent pattern mining system that generates pattern trees. <FIG> illustrates an exemplary operating environment of a code completion system that utilizes the pattern trees. <FIG> illustrates an exemplary operating environment of an idiom web service that provides pattern trees in an on-demand service. It should be noted that the exemplary operating environments are not limited to those shown in <FIG> and other configurations are possible, including combinations of the components shown in <FIG>.

Turning to <FIG>, an exemplary frequent pattern mining system <NUM> includes a computing device <NUM> that performs the frequent pattern mining coupled to a computing device <NUM> that supports a source code repository. The computing devices <NUM>, <NUM> communicate through network <NUM>. However, it should be noted that the aspects disclosed herein is not constrained to any particular configuration of devices and that other configurations are possible.

A computing device <NUM>, <NUM> may be any type of electronic device, such as, without limitation, a mobile device, a personal digital assistant, a mobile computing device, a smart phone, a cellular telephone, a handheld computer, a server, a server array or server farm, a web server, a network server, a blade server, an Internet server, a work station, a mini-computer, a mainframe computer, a supercomputer, a network appliance, a web appliance, an Internet-of-Things (IOT) device, a distributed computing system, multiprocessor systems, or combination thereof. The operating environment <NUM> may be configured in a network environment, a distributed environment, a multi-processor environment, or a stand-alone computing device having access to remote or local storage devices.

A computing device <NUM>, <NUM> may include one or more processors <NUM>, <NUM>, one or more communication interfaces <NUM>, <NUM>, one or more storage devices <NUM>, <NUM>, one or more input/output devices <NUM>, <NUM> and one or more memory devices <NUM>, <NUM>. A processor <NUM>, <NUM> may be any commercially available or customized processor and may include dual microprocessors and multi-processor architectures. A communication interface <NUM>, <NUM> facilitates wired or wireless communications between the computing devices and other devices.

A storage device <NUM>, <NUM> may be computer-readable medium that does not contain propagating signals, such as modulated data signals transmitted through a carrier wave. Examples of a storage device may include without limitation RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD), or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage, all of which do not contain propagating signals, such as modulated data signals transmitted through a carrier wave. There may be multiple storage devices in a computing device. The input/output devices <NUM>, <NUM>, may include a keyboard, mouse, pen, voice input device, touch input device, display, speakers, printers, etc., and any combination thereof.

A memory device <NUM>, <NUM> may be any non-transitory computer-readable storage media that may store executable procedures, applications, and data. The computer-readable storage media does not pertain to propagated signals, such as modulated data signals transmitted through a carrier wave. It may be any type of non-transitory memory device (e.g., random access memory, read-only memory, etc.), magnetic storage, volatile storage, non-volatile storage, optical storage, DVD, CD, floppy disk drive, etc. that does not pertain to propagated signals, such as modulated data signals transmitted through a carrier wave. A memory device may also include one or more external storage devices or remotely located storage devices that do not pertain to propagated signals, such as modulated data signals transmitted through a carrier wave.

Memory device <NUM> may include an operating system <NUM>, a source code extraction component <NUM>, a static code analyzer <NUM>, a pre-processing component <NUM>, an AST trimmer <NUM>, a simplified tree repository <NUM>, a frequent subtree mining component <NUM>, a post-processing component <NUM>, pattern tree storage <NUM>, and other applications and data <NUM>. Memory device <NUM> may include an operating system <NUM>, a source code repository <NUM> and other applications and data <NUM>.

Network <NUM> may be configured as an ad hoc network, an intranet, an extranet, a virtual private network (VPN), a local area network (LAN), a wireless LAN (WLAN), a wide area network (WAN), a wireless WAN (WWAN), a metropolitan network (MAN), the Internet, a portions of the Public Switched Telephone Network (PSTN), plain old telephone service (POTS) network, a wireless network, a WiFi® network, or any other type of network or combination of networks.

Network <NUM> may employ a variety of wired and/or wireless communication protocols and/or technologies. Various generations of different communication protocols and/or technologies that may be employed by a network may include, without limitation, Global System for Mobile Communication (GSM), General Packet Radio Services (GPRS), Enhanced Data GSM Environment (EDGE), Code Division Multiple Access (CDMA), Wideband Code Division Multiple Access (W-CDMA), Code Division Multiple Access <NUM>, (CDMA-<NUM>), High Speed Downlink Packet Access (HSDPA), Long Term Evolution (LTE), Universal Mobile Telecommunications System (UMTS), Evolution-Data Optimized (Ev-DO), Worldwide Interoperability for Microwave Access (WiMax), Time Division Multiple Access (TDMA), Orthogonal Frequency Division Multiplexing (OFDM), Ultra Wide Band (UWB), Wireless Application Protocol (WAP), User Datagram Protocol (UDP), Transmission Control Protocol/ Internet Protocol (TCP/IP), any portion of the Open Systems Interconnection (OSI) model protocols, Session Initiated Protocol/ Real-Time Transport Protocol (SIP/RTP), Short Message Service (SMS), Multimedia Messaging Service (MMS), or any other communication protocols and/or technologies.

<FIG> represents an exemplary operating environment of a code completion system <NUM>. The code completion system <NUM> includes a computing device <NUM> having one or more processors <NUM>, one or more communication interfaces <NUM>, one or more storage devices <NUM>, input/output devices <NUM>, and one or more memory devices <NUM>, as described above. The memory device <NUM> may include an operating system <NUM>, one or more source code files <NUM>, an IDE <NUM> having a source code editor <NUM>, a user interface <NUM>, and a parser <NUM>. The memory device <NUM> may also include a code completion component <NUM> having an AST trimmer <NUM>, a pattern search component <NUM>, a serialized pattern tree storage <NUM>, a pattern-to-code transformer <NUM> in addition to other applications and data <NUM>.

<FIG> represents an exemplary operating environment of an idiom web service <NUM>. The idiom web service includes one or more computing devices <NUM> coupled to a computing device <NUM> of a developer through a network <NUM>. Computing devices <NUM>, <NUM> have one or more processors <NUM>, <NUM>, one or more communication interfaces <NUM>, <NUM>, one or more storage devices <NUM>, <NUM>, input/output devices <NUM>, <NUM>, and one or more memory devices <NUM>, <NUM>, as described above. Memory device <NUM> includes an operating system <NUM>, an idiom search component <NUM>, a cache pattern tree storage <NUM>, a batched query list <NUM>, and other applications and data <NUM>. Memory device <NUM> includes an operating system <NUM>, a development environment <NUM>, an idiom web service extension <NUM>, and other applications and data <NUM>.

Aspects of the subject matter disclosed herein pertain to the technical problem of identifying large frequently-occurring source code patterns or idioms from methods/APIs that can be used in various phases of code development. The technical features associated with addressing this problem involves mining a large corpus of source code programs for closed and maximal frequent subtrees that represent the largest and frequently-used source code patterns from methods which can then be used in other methods using similar types and methods. The closed and maximal frequent subtrees consider the syntactic structure of the methods mined in addition to the type information associated with these methods and method invocation usage. These subtrees represent source code patterns that are readily available from within the code development system thereby making the development process faster and more efficient. In addition, the source code patterns are provided from an on-demand web service thereby available to a wider range of applications other than code development tools.

A system is disclosed having one or more processors coupled to a memory. The memory has one or more programs that are configured to be executed by the one or more processors. The programs include instructions that: obtain a plurality of trees, a tree representing a syntactic structure of a method of a source code program and including type data of the method; perform a closed and maximal frequent subtree data mining analysis on the plurality of trees to produce one or more idioms, an idiom representing a frequently-occurring source code pattern within the plurality of trees; and utilize the idioms to facilitate source code development.

In addition, the one or more programs include instructions that: generate a plurality of pattern trees from the closed and maximal frequent subtree data mining analysis. A pattern tree represents at least one idiom and the pattern tree is indexed by a type and at least one method. The one or more programs include further instructions that: utilize the plurality of pattern trees to generate code snippet candidates to complete a code fragment. In one or more aspects, the one or more programs include instructions that: utilize the plurality of pattern trees to provide an idiom associated with a requested type and method.

Additionally, the one or more programs include instructions that: associate a count with each of the plurality of pattern trees, the count indicating a number of types and methods associated with each pattern tree; and provide the count for a requested type and method. A pattern tree includes a source from which a respective idiom was derived. The pattern trees are generated from methods of source code programs from one or more source code repositories. In one or more aspects, the type data includes classes of objects used in methods.

A method is disclosed comprising: receiving, on a computing device having a processor coupled to a memory, source code of a first method; transforming the first method into a tree, the tree representing the syntactic structure of the source code of the first method and including type data of the first method; matching the tree with a pattern tree, a pattern tree representing a closed and/or maximal frequent subtree mined from methods of existing source code programs; generating a code snippet from the matched pattern tree; and displaying the code snippet as a candidate to complete the first method.

In one aspect, matching the tree with the pattern tree further comprises: finding the pattern tree based on a type and method associated with the tree matching a type and method associated with the pattern tree. Additionally, the method further comprises: matching a first subtree of the pattern tree with the tree; obtaining a second subtree of the pattern tree, wherein the second subtree does not match the tree; and transforming the second subtree into the code snippet.

The generation of a tree further comprises parsing the source code of the method into an abstract syntax tree; and adding type data of the method into the abstract syntax tree. In one or more aspects, the method further comprises displaying a location with the code snippet, the location representing a source from which the code snippet originated. Additionally, when no matching pattern tree is found, the first method is mined to obtain a corresponding pattern tree. The type data includes classes of objects used in the first method.

A device is disclosed comprising a processor and a memory. The processor is configured to: obtain a plurality of idioms generated through application of a data mining technique on methods of a plurality of source code programs, an idiom representing a frequently-occurring source code pattern associated with a type and one or more methods; receive a first request for an idiom from the plurality of idioms, the request including a type and method associated with a second method; find an idiom that matches the type and method of the second method from the plurality of idioms; and transmit a response including the found idiom.

In one or more aspects, the processor is further configured to associate a count with each idiom of the plurality of idioms, the count representing a frequency of a combination of the type and methods of an idiom appearing in other idioms. Additionally, the processor is further configured to receive a request for a count of idioms associated with a first type and a first method; search the plurality of idioms for a requested idiom associated with the first type and the first method; and return a count of the idioms matching the requested idioms. The data mining technique generates closed and maximal frequent subtrees and a type is a class of an object.

Claim 1:
A system comprising:
one or more processors (<NUM>) coupled to a memory (<NUM>); and
one or more programs (<NUM>-<NUM>), wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs including instructions that:
obtain a plurality of trees, a tree representing a syntactic structure of a method of a source code program (<NUM>), the tree having nodes, at least one node associated with a type and/or method invocation;
perform a closed and maximal frequent subtree data mining analysis on the plurality of trees to produce one or more idioms (<NUM>), an idiom representing a frequently-occurring source code pattern within the plurality of trees; and
utilize the idioms to facilitate source code development (<NUM>, <NUM>);
generate a plurality of pattern trees from the closed and maximal frequent subtree data mining analysis (<NUM>, <NUM>), a pattern tree representing at least one idiom, wherein a pattern tree is indexed by a type and/or at least one method;
utilize the plurality of pattern trees to generate code snippet candidates to complete a code fragment (<NUM>) by:
receiving source code of a first method;
transforming the source code of the first method into a simplified tree, the simplified tree including type data and method invocations used in the first method;
matching the simplified tree with one of the plurality of pattern trees, a pattern tree representing a closed and/or maximal frequent subtree mined from methods of existing source code programs, the pattern tree associated with similar type data and/or method invocations as the simplified tree;
generating the code snippet from the matched pattern tree; and
displaying the code snippet as a candidate to complete the first method.