Recently I wrote about directed acyclic graphs, and how you can derive topological orderings from them. Now let’s look at a more practical example.
Gradle is a build tool. It is built on tasks.
There are dependencies among the tasks (i.e. we can’t
build if we haven’t run
compileJava). Instead of just storing a linked list type structure in which we do the tasks, Gradle internally stores the dependency graph as a DAG.
To illustrate this example, I have a demo Spring Boot application, with dependencies in Spring MVC & Tomcat (web). I also made it a Kotlin project. Other than that, it’s the standard application the Spring Initializr will generate.
Let’s look at a section of the graph (technically everything needed to run
assemble, which is one of the two tasks needed for
gradle build to run (the other being
TLDR – a gradle task is a single atomic piece of work for a build, such as compiling classes or generating javadoc.
Now, if we want to get a valid order in which to run the tasks (Gradle does this internally), we need to topologically sort the DAG.
tsort <<EOF compileKotlin compileJava compileKotlin jar compileKotlin bootJar compileJava classes processResources classes classes bootJar classes jar classes inspectClassesForKotlinIC inspectClassesForKotlinICjar jar assemble bootJar assemble EOF
And the result is a valid order in which to run the tasks:
processResources compileKotlin compileJava classes bootJar inspectClassesForKotlinIC jar assemble
As we said, Gradle has to topologically sort the DAG internally. In order to see it’s linear ordering, run
gradle assemble -m.
:compileKotlin SKIPPED :compileJava SKIPPED :processResources SKIPPED :classes SKIPPED :bootJar SKIPPED :inspectClassesForKotlinIC SKIPPED :jar SKIPPED :assemble SKIPPED BUILD SUCCESSFUL in 0s
It is different, but only slightly. Recall that topological orderings are not unique (there are multiple ways to put your clothes on in the morning).