Build Systems in terms of DAGs and CFGs

Reducible1 CFGs are ones with edges that can be turned into two disjoint sets: forward edges and back edges. The forward edges need to form a DAG and no loops can have multiple entry points. That is, goto statements produce irreducible CFGs.

Thought: a build system should only allow automatic reducible CFGs. But, enricing a reducible CFG with an irreducible edge seems ok as long as that edge can only be traversed manually.

Tekton triggers are just like specifying a transition function, but specialized to only be the entry. It maps events to actions.

If a build system can be thought of as reduction of a graph, then that’s essentially the same as graph traversal with an identity function. If you allow user defined transition functions, you get things like triggers, onFailure, etc., for free.

Further, if the functions must be specified in a total language, they’re mostly equivalent to a completely unrolled and statically expanded CFG with an identity transition function. Well, as long as the DSL for constructing the CFG is not expressive enough to allow for fully dynamic dependencies; if it is, things still work, but the unrolled graph won’t be known until runtime