1294065 - Describe "transitive closure" in taskgraph docs

Status: RESOLVED FIXED

(Taskcluster :: Services, defect)

Description

[Dustin J. Mitchell [:dustin] (he/him)]

From bug 1287018:

Transitive closure is a fancy name for this sort of operation:

 * start with a set of nodes (without edges)
 * add all edges pointing away from any of those nodes, and any nodes attached to those edges
 * repeat until nothing changes

The effect is this: imagine you start with a linux32 test job and a linux64 test job.  So start with those two nodes.  Each one depends on a docker image building task, so add the edge pointing to that docker task and the docker task itself.  And each test task depends on a build task, so add the edges pointing to those build tasks, and the build tasks themselves.  Then repeat: we already have everything that the test tasks point to.  The docker tasks don't point to anything.  But the build tasks point to different docker image build tasks (they run in a different image), so we add those edges and nodes.  And repeat again.  This time, there are no new edges or nodes to add, so we are done.  And as you can see, the graph we've built now includes everything we wanted (the test jobs) plus everything required to do that (docker images, builds).

Comment 1

[Dustin J. Mitchell [:dustin] (he/him)]

Attachment: Bug 1294065: describe transitive closure;

Review commit: https://reviewboard.mozilla.org/r/70686/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/70686/

Comment 2

[Greg Arndt [:garndt]]

Comment on attachment 8779756 [details]
Bug 1294065: describe transitive closure;

https://reviewboard.mozilla.org/r/70686/#review68856

Comment 3

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/b05830100426
describe transitive closure; r=garndt

Comment 4

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/b05830100426