Distributed analysis and attribution of source code
Methods, systems, and apparatus, including computer programs encoded on computer storage media, for distributing analysis tasks and attribution tasks. One of the methods includes receiving data representing a plurality of snapshots of a code base, wherein each snapshot comprises source code files, wherein one or more snapshots have a parent snapshot in the code base according to a revision graph of snapshots in the code base. An attribution set is generated from the plurality of snapshots, the attribution set having a target set of attributable snapshots to be attributed and a support set of all parent snapshots of all snapshots in the target set. An attribution task is distributed for the attribution set to a particular worker node of a plurality of worker nodes.
1. A system comprising:
a manager node and a plurality of worker nodes, wherein:
the manager node comprises 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 manager node to perform operations comprising:
receiving a request to perform attribution tasks on a plurality of snapshots of a code base, wherein performing an attribution task on a snapshot comprises attributing characteristic segments of source code in the snapshot to respective responsible entities,
receiving data representing a revision graph, the revision graph representing parent and child relationships between snapshots of the code base, wherein a child snapshot is a subsequent snapshot of a parent snapshot in the code base,
generating an attribution set having at most N snapshots of the revision graph, wherein N is an integer greater than zero, the attribution set having a target subset of attributable snapshots and a support subset of parent snapshots of snapshots in the target subset, the snapshots in the support subset including one or more parent snapshots that do not occur in the target subset, and
submitting an attribution task for the attribution set to one worker node of the plurality of worker nodes; and
each worker node of the plurality of worker nodes comprises 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 worker node to perform operations comprising, for each attribution set provided to the worker node:
copying, to the worker node for each snapshot in the attribution set, analysis data that identifies characteristic segments of source code in the snapshot; and
attributing each characteristic segment of source code in each snapshot in the attribution set to a respective responsible entity.
2. The system of claim 1 , wherein submitting the attribution task for the attribution set to one worker node of the plurality of worker nodes comprises distributing the attributing task to a particular worker node of the plurality of worker nodes.
3. The system of claim 1 , wherein submitting the attribution task for the attribution set to one worker node of the plurality of worker nodes comprises adding an attribution task for the attribution set to a list of tasks for performance by a worker node of a plurality of worker nodes.
4. The system of claim 1 , wherein the manager node is configured to perform operations comprising:
determining that an attribution set of size N is not available according to attributable snapshots in the code base; and
in response to determining that an attribution set of size N is not available according to attributable snapshots in the code base, submitting an analysis task for a next unanalyzed snapshot to a particular worker node of a plurality of worker nodes.
5. The system of claim 1 , wherein the characteristic segments of source code are segments of source code that have coding defects that violate one or more source code coding standards.
6. The system of claim 1 , wherein the manager node is configured to perform operations comprising:
modifying a state of all snapshots in the attribution set from an attributable state to an attributing state, wherein a snapshot having an attributing state represents a snapshot currently allocated to an existing attribution task.
7. The system of claim 1 , wherein the manager node is configured to perform operations comprising:
determining that all parent snapshots of a particular snapshot have been analyzed; and
in response to determining that all parent snapshots of a particular snapshot have been analyzed, modifying a state of the particular snapshot from an analyzed state to an attributable state.
8. The system of claim 1 , wherein generating the attribution set comprises:
adding snapshots in the code base to the attribution set according to a particular order according to the revision graph.
9. The system of claim 8 , wherein the particular order is reverse chronological or reverse topological order.
10. The system of claim 1 , wherein generating an attribution set comprises:
selecting a next attributable snapshot;
generating a first attribution set having the selected next attributable snapshot in a first target subset of the first attribution set and having all parent snapshots of the next snapshot in a first support subset of the first attribution set; and
merging the first attribution set with a result attribution set.
11. The system of claim 10 , wherein merging the first attribution set with the result attribution set comprises:
adding, to a result target subset of the result attribution set, a first union of a first target subset of the first attribution set and the result target subset of the result attribution set;
adding, to a result support subset of the result attribution set, a second union of a first support subset of the first attribution set and the result support subset of the result attribution set; and
removing, from the result support subset, any snapshots that also occur in the result target subset.
12. The system of claim 11 , wherein the manager node is configured to perform operations comprising:
identifying a particular snapshot that has all parent snapshots in the result target subset or result support subset;
adding, to the result target subset, the particular snapshot; and
removing the particular snapshot from the result support subset.
13. The system of claim 1 , wherein the manager node is configured to perform operations comprising:
determining that no unanalyzed snapshots remain in the code base; and
in response to determining that no unanalyzed snapshots remain in the code base, generating an attribution set of one or more remaining attributable snapshots; and
submitting an attribution task for the attribution set to a particular worker node of a plurality of worker nodes.
14. The system of claim 1 , wherein generating the attribution set comprises:
encoding one or more constraints of the attribution set into an optimization framework, including a first constraint that specifies that each particular snapshot in a target subset needs all parent snapshots of the particular snapshot to occur in the target subset or the support subset; and
using an optimization solver of the optimization framework to obtain the attribution set.
15. A computer-implemented method comprising:
receiving, by a manager node, a request to perform attribution tasks on a plurality of snapshots of a code base, wherein performing an attribution task on a snapshot comprises attributing characteristic segments of source code in the snapshot to respective responsible entities;
receiving, by the manager node, data representing a revision graph, the revision graph representing parent and child snapshots between snapshots of the code base, wherein a child snapshot is a subsequent snapshot of a parent snapshot in the code base;
generating, by the manager node, an attribution set having at most N snapshots of the revision graph, wherein N is an integer greater than zero, the attribution set having a target subset of attributable snapshots to be attributed and a support subset of all parent snapshots of snapshots in the target subset, the snapshots in the support subset including one or more parent snapshots that do not occur in the target subset;
submitting, by the manager node, an attribution task for the attribution set to one worker node of a plurality of worker nodes;
copying, to the worker node for each snapshot in the attribution set, analysis data that identifies characteristic segments of source code in the snapshot; and
attributing, by the worker node, each characteristic segment of source code in each snapshot in the attribution set to a respective responsible entity.
16. The method of claim 15 , wherein submitting the attribution task for the attribution set to one worker node of the plurality of worker nodes comprises distributing an attribution task for the attribution set to a particular worker node of a plurality of worker nodes.
17. The method of claim 15 , wherein submitting the attribution task for the attribution set to one worker node of the plurality of worker nodes comprises adding an attribution task for the attribution set to a list of tasks for performance by a worker node of a plurality of worker nodes.
18. The method of claim 15 , further comprising:
modifying a state of all snapshots in the attribution set from an attributable state to an attributing state, wherein a snapshot having an attributing state represents a snapshot currently allocated to an existing attribution task.
19. The method of claim 15 , further comprising:
determining that all parent snapshots of a particular snapshot have been analyzed; and
in response to determining that all parent snapshots of a particular snapshot have been analyzed, modifying a state of the particular snapshot from an analyzed state to an attributable state.
20. The method of claim 15 , wherein generating the attribution set comprises:
adding snapshots in the code base to the attribution set according to a particular order according to the revision graph.
21. The method of claim 20 , wherein the particular order is reverse chronological or reverse topological order.
22. The method of claim 15 , wherein generating an attribution set comprises:
determining that an attribution set of size N is available according to attributable snapshots in the code base.
23. The method of claim 15 , wherein generating an attribution set comprises:
selecting a next attributable snapshot;
generating a first attribution set having the selected next attributable snapshot in a first target subset of the first attribution set and having all parent snapshots of the next snapshot in a first support subset of the first attribution set; and
merging the first attribution set with a result attribution set.
24. The method of claim 23 , wherein merging the first attribution set with the result attribution set comprises:
adding, to a result target subset of the result attribution set, a first union of a first target subset of the first attribution set and the result target subset of the result attribution set;
adding, to a result support subset of the result attribution set, a second union of a first support subset of the first attribution set and the result support subset of the result attribution set; and
removing, from the result support subset, any snapshots that also occur in the result target subset.
25. The method of claim 24 , further comprising:
identifying a particular snapshot that has all parent snapshots in the result target subset or result support subset;
adding, to the result target subset, the particular snapshot; and
removing the particular snapshot from the result support subset.
26. The method of claim 15 , further comprising:
determining that an attribution set of size N is not available according to attributable snapshots in the code base; and
in response to determining that an attribution set of size N is not available according to attributable snapshots in the code base, submitting an analysis task for a next unanalyzed snapshot to a particular worker node of the plurality of worker nodes.
27. The method of claim 15 , further comprising:
determining that no unanalyzed snapshots remain in the code base; and
in response to determining that no unanalyzed snapshots remain in the code base, generating an attribution set of one or more remaining attributable snapshots; and
submitting an attribution task for the attribution set to a particular worker node of a plurality of worker nodes.
28. The method of claim 15 , wherein generating the attribution set comprises:
encoding one or more constraints of the attribution set into an optimization framework, including a first constraint that specifies that each particular snapshot in a target subset needs all parent snapshots of the particular snapshot to occur in the target subset or the support subset; and
using an optimization solver of the optimization framework to obtain the attribution set.
29. The method of claim 15 , wherein the characteristic segments of source code are segments of source code that have coding defects that violate one or more source code coding standards.
30. A computer-implemented method comprising:
receiving data representing a plurality of snapshots of a code base, wherein each snapshot comprises source code files, wherein one or more snapshots have a parent snapshot in the code base according to a revision graph of snapshots in the code base;
generating an attribution set from the plurality of snapshots, the attribution set having a target subset of attributable snapshots to be attributed and a support subset of all parent snapshots of all snapshots in the target subset; and
submitting an attribution task for the attribution set to a first worker node of a plurality of worker nodes;
copying, to the first worker node for each snapshot in the attribution set, analysis data that identifies characteristic segments of source code in the snapshot;
attributing, by the first worker node, the characteristic segments of source code in each snapshot to a responsible entity;
determining that an attribution set of size N is not available according to attributable snapshots in the code base, wherein N is an integer greater than zero; and
in response to determining that an attribution set of size N is not available according to attributable snapshots in the code base, submitting an analysis task for a next unanalyzed snapshot to a second worker node of the plurality of worker nodes.
31. The method of claim 30 , wherein submitting the attribution task for the attribution set to a first worker node of the plurality of worker nodes comprises distributing an attribution task for the attribution set to the first worker node of a plurality of worker nodes.
32. The method of claim 30 , wherein submitting the attribution task for the attribution set to a first worker node of the plurality of worker nodes comprises adding an attribution task for the attribution set to a list of tasks for performance by a worker node of a plurality of worker nodes.
33. The method of claim 30 , further comprising:
modifying a state of all snapshots in the attribution set from an attributable state to an attributing state, wherein a snapshot having an attributing state represents a snapshot currently allocated to an existing attribution task.
34. The method of claim 30 , further comprising:
determining that all parent snapshots of a particular snapshot have been analyzed; and
in response to determining that all parent snapshots of a particular snapshot have been analyzed, modifying a state of the particular snapshot from an analyzed state to an attributable state.
35. The method of claim 30 , wherein generating the attribution set from the plurality of snapshots comprises:
adding snapshots in the code base to the attribution set according to a particular order according to the revision graph.
36. The method of claim 35 , wherein the particular order is reverse chronological or reverse topological order.
37. The method of claim 30 , wherein generating an attribution set from the plurality of snapshots comprises:
selecting a next attributable snapshot;
generating a first attribution set having the selected next attributable snapshot in a first target subset of the first attribution set and having all parent snapshots of the next snapshot in a first support subset of the first attribution set; and
merging the first attribution set with a result attribution set.
38. The method of claim 37 , wherein merging the first attribution set with the result attribution set comprises:
adding, to a result target subset of the result attribution set, a first union of a first target subset of the first attribution set and the result target subset of the result attribution set;
adding, to a result support subset of the result attribution set, a second union of a first support subset of the first attribution set and the result support subset of the result attribution set; and
removing, from the result support subset, any snapshots that also occur in the result target subset.
39. The method of claim 38 , further comprising:
identifying a particular snapshot that has all parent snapshots in the result target subset or result support subset;
adding, to the result target subset, the particular snapshot; and
removing the particular snapshot from the result support subset.
40. The method of claim 30 , further comprising:
determining that no unanalyzed snapshots remain in the code base; and
in response to determining that no unanalyzed snapshots remain in the code base, generating an attribution set of one or more remaining attributable snapshots; and
submitting an attribution task for the attribution set to a particular worker node of a plurality of worker nodes.
41. The method of claim 30 , wherein generating the attribution set from the plurality of snapshots comprises:
encoding one or more constraints of the attribution set into an optimization framework, including a first constraint that specifies that each particular snapshot in a target subset needs all parent snapshots of the particular snapshot to occur in the target subset or the support subset; and
using an optimization solver of the optimization framework to obtain the attribution set.
42. The method of claim 30 , wherein the characteristic segments of source code are segments of source code that have coding defects that violate one or more source code coding standards.
43. 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 operations comprising:
receiving data representing a plurality of snapshots of a code base, wherein each snapshot comprises source code files, wherein one or more snapshots have a parent snapshot in the code base according to a revision graph of snapshots in the code base;
generating an attribution set from the plurality of snapshots, the attribution set having a target subset of attributable snapshots to be attributed and a support subset of all parent snapshots of all snapshots in the target subset; and
submitting an attribution task for the attribution set to a first worker node of a plurality of worker nodes;
copying, to the first worker node for each snapshot in the attribution set, analysis data that identifies characteristic segments of source code in the snapshot;
attributing, by the first worker node, the characteristic segments of source code in each snapshot to a responsible entity;
determining that an attribution set of size N is not available according to attributable snapshots in the code base, wherein N is an integer greater than zero; and
in response to determining that an attribution set of size N is not available according to attributable snapshots in the code base, submitting an analysis task for a next unanalyzed snapshot to a second worker node of the plurality of worker nodes.
44. The system of claim 43 , wherein submitting the attribution task for the attribution set to a first worker node of the plurality of worker nodes comprises distributing an attribution task for the attribution set to the first worker node of a plurality of worker nodes.
45. The system of claim 43 , wherein submitting the attribution task for the attribution set to a first worker node of the plurality of worker nodes comprises adding an attribution task for the attribution set to a list of tasks for performance by a worker node of a plurality of worker nodes.
46. The system of claim 43 , wherein the operations further comprise:
modifying a state of all snapshots in the attribution set from an attributable state to an attributing state, wherein a snapshot having an attributing state represents a snapshot currently allocated to an existing attribution task.
47. The system of claim 43 , wherein the operations further comprise:
determining that all parent snapshots of a particular snapshot have been analyzed; and
in response to determining that all parent snapshots of a particular snapshot have been analyzed, modifying a state of the particular snapshot from an analyzed state to an attributable state.
48. The system of claim 43 , wherein generating the attribution set from the plurality of snapshots comprises:
adding snapshots in the code base to the attribution set according to a particular order according to the revision graph.
49. The system of claim 48 , wherein the particular order is reverse chronological or reverse topological order.
50. The system of claim 43 , wherein generating an attribution set from the plurality of snapshots comprises:
selecting a next attributable snapshot;
generating a first attribution set having the selected next attributable snapshot in a first target subset of the first attribution set and having all parent snapshots of the next snapshot in a first support subset of the first attribution set; and
merging the first attribution set with a result attribution set.
51. The system of claim 50 , wherein merging the first attribution set with the result attribution set comprises:
adding, to a result target subset of the result attribution set, a first union of a first target subset of the first attribution set and the result target subset of the result attribution set;
adding, to a result support subset of the result attribution set, a second union of a first support subset of the first attribution set and the result support subset of the result attribution set; and
removing, from the result support subset, any snapshots that also occur in the result target subset.
52. The system of claim 51 , wherein the operations further comprise:
identifying a particular snapshot that has all parent snapshots in the result target subset or result support subset;
adding, to the result target subset, the particular snapshot; and
removing the particular snapshot from the result support subset.
53. The system of claim 43 , wherein the operations further comprise:
determining that no unanalyzed snapshots remain in the code base; and
in response to determining that no unanalyzed snapshots remain in the code base, generating an attribution set of one or more remaining attributable snapshots; and
submitting an attribution task for the attribution set to a particular worker node of a plurality of worker nodes.
54. The system of claim 43 , wherein generating the attribution set from the plurality of snapshots comprises:
encoding one or more constraints of the attribution set into an optimization framework, including a first constraint that specifies that each particular snapshot in a target subset needs all parent snapshots of the particular snapshot to occur in the target subset or the support subset; and
using an optimization solver of the optimization framework to obtain the attribution set.
55. The system of claim 43 , wherein the characteristic segments of source code are segments of source code that have coding defects that violate one or more source code coding standards.