pantsbuild / pants / 35088

0%

main: 93%

push

travis-ci-com

Implement RuleGraph construction using data flow analysis (#10645)

### Problem

Rule graph construction time became exponential worse recently as more rules were added to a particular cluster in the graph: in particular, the set of rules around target construction. See #10504.

Additionally, rule graph construction error reporting had become unmanageable with existing recursive rule graph construction algorithm: failing to construct a rule graph meant running post-facto logic to attempt to discern what had happened by re-constructing a graph of likely errors, which was slow and error prone. See #10440.

Attempting to solve these two issues in the existing recursive rule graph algorithm proved to be a dead end: the logic that it used to attempt to deal with cycles was beginning to fail to deal with more complicated cyclic structures, and was contributing to the total runtime by backtracking out of cycles. 

### Solution

Move to constructing a `RuleGraph` using data flow analysis on the rule call graph. Additionally, replace `RootRule` definitions (which were used to "plug" holes in the rule graph in places where external inputs were expected, but which were in practice sprinkled everywhere someone thought they might be necessary) with `QueryRule` definitions, which correspond almost* 1:1 with `Schedule.product_request` callsites.

The new construction algorithm is broken up into phases:

1. Building a polymorphic graph, where all sources of a particular dependency are included, but without regard for which types are available at a callsite. This phase will fail fast if no `Query` or `Get` anywhere in the graph provides a particular `Param` type.
2. Run [live variable analysis](https://en.wikipedia.org/wiki/Live_variable_analysis) on the polymorphic graph to compute the initial set of `Params` used by each node in the graph. During this phase, each node in the graph has a reference to all possible sources of a particular type, and so th... (continued)

257 of 257 new or added lines in 62 files covered. (100.0%)

0 of 28918 relevant lines covered (0.0%)

0.0 hits per line