Function execution prioritization

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for assigning levels of priority to selected source code functions. One of the methods includes for each selected function, a respective associated first set of functions reachable from the selected function by at most N steps, and a respective associated second set of functions that are each reachable from the selected function by more than N steps and less than M steps are computed. A first partition having all selected functions whose respective associated first set of functions has at least one of the subject functions is computed. A second partition having selected functions not in the first partition and whose respective associated second set of functions has at least one of the subject functions is computed. Selected functions belonging to the first partition are assigned a higher priority than selected functions belonging to the second partition.

BACKGROUND

This specification relates to testing source code.

Source code is typically maintained by developers in a code base of source code using a version control system. Version control systems generally maintain multiple revisions of the source code in the code base, each revision being referred to as a snapshot. Each snapshot includes the source code of files of the code base as the files existed at a particular point in time.

Snapshots stored in a version control system can be represented as a directed, acyclical revision graph. Each node in the revision graph represents a commit of the source code. A commit represents a snapshot as well as other pertinent information about the snapshot such as the author of the snapshot, and data about ancestor commits of the node in the revision graph. A directed edge from a first node to a second node in the revision graph indicates that a commit represented by the first node is a previous commit than a commit represented by the second node, and that no intervening commits exist in the version control system.

A common approach to software testing is to require that a commit passes a suite of testing functions before the snapshot is merged into the code base. For large software projects with comprehensive test suites, running tests can take many hours. In many cases, a single test failure is sufficient to bar a commit from merging. Thus, when a test fails, all the time spent running the previous tests was time wasted. In other words, if the failing test had been run first, none of the other tests would have been required to run.

SUMMARY

This specification describes how a build system can assign levels of priority to testing functions used to test source code of snapshots in a code base. The levels of priority represent an ordering in which the testing functions should be executed, with testing functions having higher levels of priority to be executed before testing functions having lower priority.

The system can reduce the amount of time spent executing testing functions by assigning the levels of priority in a way that is dependent upon the code that is changed in the new commit. To do so, the system can assign the levels of priority in a way that makes it more likely that testing functions likely to fail are executed early in the testing process.

Particular embodiments of the subject matter described in this specification can be implemented so as to realize one or more of the following advantages. By prioritizing testing functions, a build system can reduce the amount of time spent executing testing suites that have failing testing functions. The system can automatically prioritize the testing functions in a way that tailored to each individual commit. The prioritization functionality can be integrated into an automatic testing system, and developers not need even have knowledge of or expertise in how to order the testing functions.

DETAILED DESCRIPTION

This specification describes techniques for prioritizing functions for a particular snapshot of a code base such that functions with higher levels of priority are more likely to uncover problems in the snapshot than functions with lower levels of priority.

The snapshot being considered will be referred to as the subject snapshot. Often, the subject snapshot is a proposed commit to a code base. A proposed commit includes a number of source code files that are changed relative to another snapshot of the code base. Thus, the subject snapshot includes modified source code files of the proposed commit plus baseline files from an ancestor snapshot in the code base.

A build system can use the techniques described below to assign levels of priority for any arbitrarily selected functions in a subject snapshot. The assigned levels of priority effectively order the selected functions in the subject snapshot according to a likelihood of each function uncovering problems in the snapshot. For clarity of explanation, the selected functions will be described as “testing functions” because a build system will typically use the prioritization techniques described below to assign levels of priority to testing functions in a testing suite. However, the same techniques can be used for any set of selected functions in a snapshot.

A build system executes a testing process by executing all testing functions in a testing suite in a particular order. Each testing function is typically designed to uncover errors in a particular snapshot. Some testing functions may return an explicit indication that the test passed or failed. Other testing functions may be considered to have passed by virtue of successfully executing in their entirety without crashing. Often, a snapshot is only allowed to be committed to the code base if all testing functions in the testing process have passed.

Functions that are reachable from testing functions, and whose functionality is directly or indirectly tested by testing functions, will be referred to as subject functions. That is, subject functions are either called directly by a testing function or called indirectly through a chain of one or more functions starting from a function called by the testing functions.

The system can represent reachability of one function from another by generating data representing a call graph. A call graph has nodes and directed links in which each node represents a function and each directed link between a pair of nodes represents that one function represented by a first node of the pair calls another function represented by a second node of the pair. The system can compute the call graph using any appropriate technique, e.g., by computing a transitive closure over functions in the code base. In other words, a subject function S for a testing function T is any function such that tuple (T, S) is in the transitive closure over a call graph of the snapshot.

FIG. 1is a diagram of an example call graph. The call graph includes nodes representing five functions defined by the following pseudocode:

In this example, the functions T1 and T2 are testing functions, and the other functions are subject functions that are reachable from T1 and T2.

The function T1 is represented in the call graph by node110. The call graph shows that T1 directly calls the functions g, h, and j, represented by nodes120,150, and140respectively. The function i, represented by node130is another subject function that is reachable from T1.

The function T2 is represented in the call graph by node160. The call graph shows that T2 directly calls the functions h and i, represented by nodes150and130respectively. The other subject functions, g and j, represented by nodes120and140, are also reachable from T2.

The testing function T1 calls the function g directly but only calls the function i indirectly. Therefore, the success or failure of T1 depends more directly on the function g than on the function i. Therefore, the testing function T1 should have a higher priority in the testing process when a new commit changes the function g rather than the function i.

This is because any new errors introduced by the changes to a function are more likely to be encountered from a testing function that calls the function directly rather than another testing function that calls the function only indirectly.

On the other hand, the testing function T2 calls the function i directly but only calls the function g indirectly. Therefore, the testing function T2 should have a higher priority in the testing process when a new commit changes the function i rather than the function g.

Thus, if a new commit changes the function g, the system can assign a higher priority to T1 than T2. This means that the testing function T1 will be executed before the testing function T2.

But if a new commit changes the function i, the system can assign a higher priority to T2 than T1, meaning that the testing function T2 will be executed before the testing function T1.

FIG. 2is a diagram of an example system200. The system200is an example of a system that uses test procedure prioritization.

The system200includes a user device260in communication with a testing system202over a network, which can be any appropriate communications network, e.g., a local area network or the Internet.

The testing system202uses a testing utility210to run a plurality of tests on snapshots of a code base240. The testing utility210uses a testing configuration270to drive the testing of the source code. For example, the testing configuration270can include information specifying a number of functions in a snapshot as testing functions.

The components of the testing system202can be implemented as computer programs installed on one or more computers in one or more locations that are coupled to each through a network. Alternatively, the testing system202can be installed in whole or in part on a single computing device, e.g., the user device260.

In operation, the user device260provides a test command205to the testing system202. The test command205specifies a particular subject snapshot to be tested. The test command205may also specify a particular testing configuration270for the subject snapshot, e.g., a set of testing functions for the snapshot.

The testing utility210provides a request215for testing function prioritization for the snapshot to a testing function scorer250. The testing function scorer250assigns levels of priority to each of the testing functions identified by the testing configuration270. The testing function scorer250and the testing utility210can be integrated into a source code testing suite. In some implementations, the testing utility210is configured to automatically use the testing function scorer to order testing functions without a user of the user device260having to inspect the testing functions or the call graph235.

To do so, the testing function scorer250uses a call graph235computed by a call graph engine220. The call graph engine220can compute the call graph235either before or after the test command205is received. Because many adjacent snapshots in a revision graph are very similar, the call graph engine220need not generate a new call graph for each subsequent snapshot or for each received test command. As explained in more detail below, the call graph235may be for an ancestor snapshot of the snapshot specified by the test command205.

The testing function scorer250assigns levels of priority to the testing functions and returns the priority levels for the testing functions245to the testing utility210. The testing utility210can then use the priority levels245when running a testing process for the snapshot specified by the test command205.

After the testing process is completed, the testing utility210can return a notification275that the testing process succeeded or failed. In many systems, the snapshot can be merged into the code base only if the testing process succeeds.

FIG. 3is a flow chart of an example process for assigning levels of priority to a plurality of functions of a subject snapshot. The process can be implemented by an appropriately programmed system of one or more computers, e.g., the testing function scorer250ofFIG. 2.

The system identifies a plurality of selected functions that call other functions defined in source code of a subject snapshot (310). The selected functions may or may not also be part of the subject snapshot. The subject snapshot can be a proposed commit of source code for the code base, and the selected functions can be testing functions that call other functions defined in the snapshot. Commonly, if all of the testing functions pass for the proposed commit, the proposed commit can be merged into the code base.

The system can identify the selected functions in a variety of ways. For example, developers of the code base can designate one or more functions in the source code as testing functions in a variety of ways. For example, testing functions may be annotated in the source code as testing functions or identified as using a common testing framework, e.g., JUint or gtest. In addition, developers can designate one or more files or directories of the code base as locations that contain testing functions. Alternatively, the developers can generate one or more metadata configuration files, e.g., XML files, that designate functions as testing functions.

The system obtains data representing a call graph of the source code of the subject snapshot (320). As described above, the call graph represents reachability relations between functions in the source code. The system can either compute the call graph by analyzing relationships between functions in the snapshot or obtain the call graph from another source.

For complex code bases, computing call graphs for snapshots can be computationally expensive. Therefore, to reduce this extra computation overhead, the system can reuse a call graph that was previously computed for another call graph in the code base.

For example, the call graph can be a call graph computed for a parent snapshot of the subject snapshot or an ancestor of the subject snapshot. In large code bases, the differences between adjacent snapshots in a revision graph are typically very small. Thus, a call graph computed for a parent snapshot is often accurate enough for assigning levels of priority for the subject snapshot that is subsequent to the previous snapshot.

Even if the changes in the subject snapshot are not small, the testing process can still be performed without any significant problems. The effect is simply that the levels of priority assigned to the testing functions might be less ideal than if the call graph were computed explicitly for the subject snapshot.

The system identifies a plurality of subject functions in the subject snapshot (330). In general, the subject functions are functions that are reachable from the selected functions. Often the subject functions are functions that a plurality of testing functions are designed to test.

Developers of the system can specify the subject functions in any appropriate way, e.g., by using metadata or configuration files as described above with reference to identifying testing functions.

In some implementations, the system identifies the subject functions as functions that were touched by the subject snapshot relative an ancestor of the subject snapshot of the code base. In other words, the system designates any function that is modified or added relative to the previous commit as a subject functions.

The system assigns levels of priority to each of the plurality of selected functions (340). The levels of priority generally provide a partitioning or ranking for in what order the selected functions should be executed. In general, the system uses the call graph to determine an ordering of selected functions that makes errors in the subject functions more likely to be found earlier when the selected functions are executed in an order determined by the assigned levels of priority. In other words, errors in the subject functions touched by the subject commit are more likely to be found by executing a selected function having a higher priority than a selected function having a lower priority. Example techniques for assigning levels of priority to selected functions based on the subject functions are described in more detail below with reference toFIGS. 4-5.

The system optionally executes the selected functions in an order determined by the assigned levels of priority (350). For example, a static analysis system can assign the levels of priority and can provide the levels of priority to a build system. The build system can then run the testing functions in an order based on the assigned levels of priority. Alternatively, the build system can assign the levels of priority as well as execute the testing functions according to the assigned levels of priority.

FIG. 4is a flow chart of an example process for partitioning a plurality of selected testing functions. In general, partitioning testing functions involves assigning each of the testing functions to one of multiple partitions, D1through DN. Then, when the testing functions are executed, all testing functions in D1are executed first before any testing functions in D2are executed, and so on down to the last partition DN. The example process inFIG. 4generates only two partitions. However, the example process can be similarly carried out to any arbitrary number of partitions, e.g., 5, 10, or 50 partitions. This example process assumes the existence of a call graph for a subject snapshot, as well as a plurality of testing functions. For example, the testing functions can be specified as described above with reference toFIG. 3. The process can be implemented by an appropriately programmed system of one or more computers, e.g., the testing function scorer250ofFIG. 2.

The system computes for each testing function an associated first set of functions that are each reachable from the testing function along a path in the call graph having at most N steps (410). N is a predetermined integer constant. In other words, the system computes, for each testing function, all functions that are reachable from the testing function along a path that is at most N steps long. If, for example, N is 1, the system identifies all functions that are called directly by the testing function.

To do so, the system can iterate over each of the designated testing functions and determine, from the call graph data, which other functions are reachable from the testing function along paths that are at most N steps.

The system computes for each testing function an associated second set of functions that are each reachable from the testing function along a path in the call graph having more than N steps and less than M steps (420). M is also a predetermined constant that is larger than N. In other words, the system computes, for each testing function, all functions that are reachable from the testing function along paths that are greater than N but less than M.

The system identifies a plurality of subject functions in the subject snapshot (430), e.g., as described above with reference toFIG. 3.

The system computes a first partition D1having all testing functions whose respective associated first set of functions has at least one of the subject functions (440). That is, the system determines which testing functions have a first set of functions in which at least one of the subject functions appears. In other words, the system adds to the first partition D1all testing functions from which a subject function is reachable along a path that is at most N steps long.

The system computes a second partition D2having all testing functions not in D1and whose respective associated second set of functions has at least one of the subject functions (450). That is, the system determines which testing functions have a second set of functions in which at least one of the subject functions appears. In other words, the system adds to the second partition D2all testing functions from which a subject function is reachable along a path that is between N and M steps long.

The system assigns testing functions belonging to D1a higher priority than the testing functions belonging to D2(460). As described above, this means that to increase the likelihood of uncovering errors introduced by the subject functions, the functions in D1should all be executed before any of the functions in D2.

The example process inFIG. 4implicitly generates a last partition that includes all testing functions not in any of the generated partitions, e.g., testing functions not in D1and not in D2. The system can thus assign the lowest priority of all to the testing functions in the last partition. And in general, for any number of K partitions that the system generates, testing functions that are not added to any of the K partitions can be assigned the lowest priority.

In some implementations, the system generates partitions for each integer value from 1 to M−1. For example, if M is 6, the system generates different partitions for paths of length 1, 2, 3, 4, and 5.

The system can also optionally rank testing functions within a partition according to how many of the subject functions occur in the respective associated sets of functions. For example, if in the partition D1there is a first testing function T1that calls two subject functions directly and a second testing function T2that calls only one subject function directly, the system can assign a higher priority level to T1than to T2.

The system can also rank testing functions within a partition based on where the testing function would fall if it weren't in its current partition. In other words, the system effectively ranks testing functions within a partition by respective second-closest subject functions to the testing function.

FIG. 5is a flow chart of an example process for ranking testing functions by score. The system can assign the scores based on lengths of call graph paths between testing functions and subject functions and on a number of identified call graph paths between testing functions and subject functions. This example process assumes the existence of a call graph for a subject snapshot, as well as a plurality of testing functions. For example, the testing functions can be specified as described above with reference toFIG. 3. The process can be implemented by an appropriately programmed system of one or more computers, e.g., the testing function scorer250ofFIG. 2.

The process can be implemented by an appropriately programmed system of one or more computers, e.g., the testing function scorer250ofFIG. 2.

The system identifies a plurality of subject functions (510), e.g., as described above with reference toFIG. 3.

The system identifies, for each testing function and each subject function, all subject functions reachable from the testing function along shortest paths of length N or less (520).

The value N represents a maximum path length of subject functions reachable from the testing function.

For example, the system can use the call graph to determine respective sets of subject functions that are reachable from each of the testing functions along respective shortest paths that are of length N or less. In some implementations, N is a predetermined constant. In some other implementations, N is a user-specified configuration parameter, 3, 5, or 10. Alternatively, the system can be configured to operate without the constant N by setting N to be equal to the length of the longest path in the call graph.

The system computes, for each testing function and each identified subject function reachable from the testing function along paths of length N or less, a relatedness score between the testing function and the subject function (530). The relatedness score represents a measure of relatedness between a testing function and a subject function, with higher scores representing that the testing function and the subject function are more closely related.

The relatedness score for a testing function and a subject function is influenced by two factors: (1) the length of the paths from the testing function to the subject function, and (2) the number of identified paths from the testing function to the subject function.

The first factor, the length of the paths, is inversely related to the measure of relatedness. In other words, as the path lengths increase, the relatedness score decreases.

The second factor, the number of paths, is directly related to the measure of relatedness. In other words, as the number of paths increases, the relatedness score increases.

The system can use these two factors to compute the measure of relatedness between the testing function and the subject function in any appropriate way. In some implementations, the system computes the relatedness score RSfor a subject function S using characteristics of each path Pifrom the testing function to the subject function S according to:

This formulation means that for subject functions that are not reachable along one or more paths of length N or less, the relatedness score is zero.

For the testing function T1110inFIG. 1and the subject function g120inFIG. 1, the relatedness score would be 1.5. For the testing function T2160and the subject function g120, the relatedness score would be 0.5.

The system computes, for each testing function, a priority score using the relatedness scores computed for the testing function (540). The system can combine all relatedness scores for a particular testing function in any appropriate way. For example, the system can sum or multiply all non-zero relatedness scores for a particular function.

For example, two of the functions fromFIG. 1are subject functions, e.g., the function g150and the function j140, the priority score for the testing function T1110would be 1.333 (for j140)+1.5 (for g120)=2.833.

Meanwhile, the priority score for the testing function T2160would be 0.5 (for j140)+0.5 (for g120)=1.0.

Thus, when the subject functions are the function g150and the function j140, the priority scores indicate that the testing function T1110should be executed before the testing function T2160. Doing so makes it more likely on average that failures introduced in the subject functions will be found earlier in the testing process.

The priority scores themselves can generally be used to rank the testing functions in an order that can be used during the testing process, either by a build system or a system that computed the priority scores. In other words, each testing function is executed in an order determined by the priority scores.

The system can also partition the testing functions according to the priority scores. Thus, functions within a partition having higher priority scores are executed before functions within a partition having lower priority scores, but within each partition, the system can execute the functions in any order.

Thus, the system optionally ranks the testing functions according to the priority scores (550) and executes the testing functions in an order based on the priority scores (560).

To provide for interaction with a user, embodiments of the subject matter described in this specification can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube) monitor, an LCD (liquid crystal display) monitor, or an OLED display, for displaying information to the user, as well as input devices for providing input to the computer, e.g., a keyboard, a mouse, or a presence sensitive display or other surface. Other kinds of devices can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input. In addition, a computer can interact with a user by sending resources to and receiving resources from a device that is used by the user; for example, by sending web pages to a web browser on a user's client device in response to requests received from the web browser.

Embodiment 1 is a method for assigning levels of priority to a plurality of selected functions, the method comprising:identifying a plurality of selected functions that call other functions defined in source code of a subject snapshot of a code base;obtaining data representing a call graph of the source code of the code base, wherein the call graph has nodes and directed links, each node representing a function in the source code, and wherein each link between each pair of nodes represents that a first function of the pair calls a second function of the pair;computing, for each selected function, a respective associated first set of functions that are each reachable from the selected function along a path in the call graph having at most N steps, wherein N is a predetermined constant;computing, for each selected function, a respective associated second set of functions that are each reachable from the selected function along a path in the call graph having more than N steps and less than M steps, wherein M is a predetermined constant;identifying a plurality of subject functions in the subject snapshot;computing a first partition D1having all selected functions whose respective associated first set of functions has at least one of the subject functions; andcomputing a second partition D2having selected functions not in D1and whose respective associated second set of functions has at least one of the subject functions; andassigning the selected functions belonging to D1a higher priority than the selected functions belonging to D2.

Embodiment 2 is the method of embodiment 1, further comprising:computing a third partition D3having selected functions not belonging to D1or D2; andassigning the selected functions belonging to D3a lower priority than the selected functions belonging to D2.

Embodiment 3 is the method of any one of embodiments 1-2, wherein the plurality of selected functions are testing functions for testing source code of the subject snapshot.

Embodiment 4 is the method of any one of embodiments 1-3, wherein assigning the higher priority designates that all selected functions in D1will be executed before any selected functions in D2are executed.

Embodiment 5 is the method of embodiment 4, further comprising executing all selected functions in D1before executing any selected functions in Dz.

Embodiment 6 is the method of any one of embodiments 1-5, wherein identifying the plurality of subject functions comprises determining which functions have changed in the subject snapshot relative to a previous snapshot of the code base.

Embodiment 7 is the method of any one of embodiments 1-6, wherein obtaining the call graph comprises obtaining the call graph of a previous snapshot rather than a call graph of the subject snapshot.

Embodiment 8 is the method of any one of embodiments 1-7, further comprising:computing for each selected function in D1a respective number of subject functions that occurs in the first set of functions for the selected function; andassigning respective levels of priority to selected functions within D1based on the computed respective number of subject functions.

Embodiment 9 is the method of any one of embodiments 1-8, further comprising:computing, for each selected function within a partition, a second partition to which the selected function would belong if the selected function did not belong to the partition; andassigning respective levels of priority to selected functions within the partition based on the computed second partitions for each selected function within the partition.

Embodiment 10 is a method for assigning priority scores to a plurality of selected functions, the method comprising:identifying a plurality of subject functions of a subject snapshot of a code base;obtaining data representing a call graph of source code of the code base, wherein the call graph has nodes and directed links, each node representing a function in the source code, and wherein each link between each pair of nodes represents that a first function of the pair calls a second function of the pair;identifying, for each subject function, one or more selected functions in the subject snapshot from which each of the subject functions are reachable along paths of length N or less;computing, for each selected function and each identified subject function, a respective relatedness score that is based on (1) the lengths of the paths from the selected function to the subject function, and (2) a number of identified paths from the selected function to the subject function;computing, for each selected function, a respective priority score based on the relatedness scores computed for the selected function; andassigning the selected functions a level of priority based on the priority scores.

Embodiment 11 is the method of embodiment 10, wherein the plurality of selected functions are testing functions for testing source code of the subject snapshot.

Embodiment 12 is the method of embodiment 11, wherein each testing function defines a procedure that determines whether or not the subject snapshot can be merged into the code base.

Embodiment 13 is the method of any one of embodiments 10-12, further comprising:ranking the selected functions based on the priority scores; andexecuting the selected functions in an order according to the ranking.

Embodiment 14 is the method of any one of embodiments 10-13, wherein computing, for each selected function and each identified subject function, a respective relatedness score comprises computing the relatedness score RS for a subject function S according to:

RS=∑1length⁡(Pi),wherein each length (Pi) represents a length of a path from the selected function to one of the subject functions.

Embodiment 15 is the method of any one of embodiments 10-14, wherein computing, for each selected function, the respective priority score for the selected function comprises computing a sum of the relatedness scores for the selected function.

Embodiment 16 is the method of any one of embodiments 10-15, wherein identifying the plurality of subject functions comprises determining which functions have changed in the subject snapshot relative to a previous snapshot of the code base.

Embodiment 17 is the method of any one of embodiments 10-16, wherein obtaining data representing the call graph comprises obtaining the call graph of a previous snapshot rather than a call graph of the subject snapshot.

Embodiment 18 is a system comprising: one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform the method of any one of embodiments 1 to 17.

Embodiment 19 is a computer storage medium encoded with a computer program, the program comprising instructions that are operable, when executed by data processing apparatus, to cause the data processing apparatus to perform the method of any one of embodiments 1 to 17.