{"id":1133,"date":"2019-07-26T07:23:36","date_gmt":"2019-07-26T06:23:36","guid":{"rendered":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/?p=1133"},"modified":"2019-07-27T23:44:57","modified_gmt":"2019-07-27T22:44:57","slug":"stroll","status":"publish","type":"post","link":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/stroll\/","title":{"rendered":"Stroll: an experimental build system"},"content":{"rendered":"

I’d like to share an experiment in developing a language-agnostic build system\u00a0that does not require the user to specify dependencies between individual build tasks. By “language-agnostic” I mean the user does not need to learn a new language or a special file format for describing build tasks — existing scripts or executable files can be used as build tasks directly without modification.<\/p>\n

I call this build system Stroll<\/a> because its build algorithm reminds me of strolling through a park where you’ve never been before, trying to figure out an optimal path to your target destination, and likely going in circles occasionally until you’ve built up a complete mental map of the park.<\/p>\n

<\/p>\n

Main idea<\/h3>\n

Most build systems require the user to specify both build tasks<\/em>\u00a0as well as dependencies<\/em> between the tasks: knowing the dependencies allows the build system to determine which tasks need to be executed when you modify some of the source files. From personal experience, describing dependencies accurately is difficult and is often a source of frustration.<\/p>\n

Build tasks and their dependencies are typically described using domain-specific task description languages: Make<\/a> uses makefiles,\u00a0Bazel<\/a> uses a Python-inspired\u00a0Starlark<\/a>,\u00a0Shake<\/a> uses Haskell, etc. While learning a new\u00a0task description language is not a big deal, translating an existing build system to a new language may take years (or maybe I’m just slow).<\/p>\n

Stroll is different. You use your favourite language(s) to describe build tasks, put them in a directory, and ask Stroll to execute them. Stroll does not look inside the tasks; it treats the tasks as black boxes and finds the dependencies between them by tracking their\u00a0file accesses. This process is not optimal in the sense that a task may fail because its dependency is not ready and, therefore, will need to be built again later, but in the end, Stroll will learn the complete and accurate dependency graph and will store it to speed up future builds.<\/p>\n

There is a build system called Fabricate<\/a> that also tracks file accesses to automatically compute accurate task dependencies, but it requires the user to describe build tasks in a lightweight Python DSL and preschedule them by calling the tasks in the right order, essentially asking the user to do the strolling part themselves. Fabricate is cool and inspired Stroll but I’d like to explore this corner of the build systems space a bit further.<\/p>\n

Demo<\/h3>\n

Stroll is just an experiment and I’m not sure if the main idea behind it is feasible, but it can already be used to automate some simple collections of build tasks. Let me give you a demo. I’m using Windows below but the demo works on Linux too.<\/p>\n

Consider a simple “Hello, World!” program stored in the file src\/main.c<\/span>:<\/p>\n

\n
#include <stdio.h><\/span>\r\n\r\nint<\/span> main<\/span>()\r\n{\r\n    printf(\"Hello, World!<\/span>\\n<\/span>\"<\/span>);\r\n    return<\/span> 0<\/span>;\r\n}\r\n<\/pre>\n<\/div>\n
We can build an executable bin\/main.exe<\/span> from it by using the following simple build script build\/main.bat<\/span>:<\/p>\n
\n
mkdir<\/span> bin\r\ngcc<\/span> src\/<\/span>main.<\/span>c -<\/span>o bin\/<\/span>main.<\/span>exe\r\n<\/pre>\n<\/div>\n
Let’s ask Stroll to build our little project:<\/p>\n
\n
$<\/span> stroll build\r\nExecuting build\/main.bat...<\/span>\r\nDone\r\n<\/span>\r\n$<\/span> bin\/main.exe\r\nHello, World!<\/span>\r\n<\/pre>\n<\/div>\n
When executing build tasks, Stroll tracks their file accesses and stores the discovered information next to the build scripts, by appending the extension .stroll<\/span>\u00a0to their names:<\/p>\n
\n
$<\/span> cat build\/main.bat.stroll\r\nexit-code: ExitSuccess<\/span>\r\noperations:<\/span>\r\n  bin\/main.exe:<\/span>\r\n    write: efc851e573be26cf8fe726caf70facf924ccdbae5c4fce241fdbe728b3abde76<\/span>\r\n  src\/main.c:<\/span>\r\n    read: bc31bb10c238be7ee34fd86edec0dc99d145f56067b13b82c351608efd38763c<\/span>\r\n  build\/main.bat:<\/span>\r\n    read: da9a4390693741b8d52388f18b1c5ccc418531bc3b0a64900890c381a31e7839<\/span>\r\n<\/pre>\n<\/div>\n
As you can see, Stroll recorded the exit code of the script, two file reads and one file write, along with the corresponding hashes of file contents.<\/p>\n
We can ask Stroll to visualise the discovered dependency graph:<\/p>\n
\n
$<\/span> stroll -g build | dot -Tpng -Gdpi=600 -o graph.png\r\n<\/pre>\n<\/div>\n
The flag -g<\/span> tells Stroll to print out the discovered dependency graph in the DOT format<\/a> that we subsequently convert to the following PNG file:<\/p>\n
\"Dependency<\/a><\/p>\n
The green box indicates that the only build task main<\/span> is up-to-date. This means Stroll will not execute it in the next run unless any of its inputs or outputs change. If we modify src\/main.c<\/span>\u00a0and regenerate the dependency graph, we can see that the task main<\/span> is now out-of-date:<\/p>\n
\"Dependency<\/a><\/p>\n
The specific dependency that is out-of-date is shown by a dashed edge. Note that Stroll is a self-tracking build system<\/em>, i.e. it tracks changes not only in sources and build artefacts but in build tasks too.<\/p>\n
To make the example a bit more interesting, let’s add\u00a0a library providing a greeting function greet<\/span>\u00a0in files src\/lib\/lib.h<\/span> and src\/lib\/lib.c<\/span>:<\/p>\n
\n
$<\/span> cat src\/lib\/lib.h\r\nvoid greet(char *name);<\/span>\r\n\r\n$<\/span> cat src\/lib\/lib.c\r\n#<\/span>include <stdio.h>\r\n#<\/span>include <lib.h>\r\n\r\nvoid greet(char *name)<\/span>\r\n{<\/span>\r\n    printf(\"Hello, %s!\\n\", name);<\/span>\r\n}<\/span>\r\n<\/pre>\n<\/div>\n
To compile the library we will add a new build task\u00a0build\/lib.bat<\/span>:<\/p>\n
\n
mkdir<\/span> bin\/<\/span>lib\r\ngcc<\/span> -Isrc<\/span>\/<\/span>lib -<\/span>c src\/<\/span>lib\/<\/span>lib.<\/span>c -<\/span>o bin\/<\/span>lib\/<\/span>lib.<\/span>o\r\n<\/pre>\n<\/div>\n
If we look at the dependency graph before running Stroll we’ll see:<\/p>\n
\"Dependency<\/a><\/p>\n
The new task lib<\/span> appeared in the graph but without any dependencies; it is marked as out-of-date because Stroll has never executed it. If we run Stroll now, it will execute both tasks reaching the following state:<\/p>\n
\"Dependency<\/a><\/p>\n
The tasks are currently independent and can be built in parallel but let’s make use of the library by modifying the main<\/span> source file as follows:<\/p>\n
\n
#include <lib.h><\/span>\r\n\r\nint<\/span> main<\/span>()\r\n{\r\n    greet(\"World\"<\/span>);\r\n    return<\/span> 0<\/span>;\r\n}\r\n<\/pre>\n<\/div>\n
If we run Stroll now, the build will fail:<\/p>\n
\n
$<\/span> stroll build\r\nExecuting build\/main.bat...<\/span>\r\nScript build\/main.bat has failed.<\/span>\r\nDone<\/span>\r\n\r\n$<\/span> cat build\/main.bat.stderr\r\nA subdirectory or file bin already exists.<\/span>\r\nsrc\\main.c:2:17: fatal error: lib.h: No such file or directory<\/span>\r\ncompilation terminated.<\/span>\r\n<\/pre>\n<\/div>\n
By examining the file build\/main.bat.stderr<\/span>\u00a0helpfully created by Stroll, we can see that the build failed because we forgot to modify the build script and point\u00a0gcc<\/span> to our library. An error is visualised by a task with a double border:<\/p>\n
\"Dependency<\/a><\/p>\n
Let’s fix the script main\/build.bat<\/span>:<\/p>\n
\n
mkdir<\/span> bin\r\ngcc<\/span> -Isrc<\/span>\/<\/span>lib src\/<\/span>main.<\/span>c bin\/<\/span>lib\/<\/span>lib.<\/span>o -<\/span>o bin\/<\/span>main.<\/span>exe\r\n<\/pre>\n<\/div>\n
With this fix, Stroll completes successfully and produces the following dependency graph:<\/p>\n
\"Dependency<\/a><\/p>\n
We can now demonstrate the early cut-off<\/em> feature by adding a comment to the file src\/lib\/lib.c<\/span>. Before running Stroll let’s check that this change makes both lib<\/span> and main<\/span> out-of-date:<\/p>\n
\"Dependency<\/a><\/p>\n
As you can see, both tasks are now marked as out-of-date: lib<\/span>\u2019s direct input has changed, which transitively also affects main<\/span>. Let’s Stroll:<\/p>\n
\n
$<\/span> stroll build\r\nExecuting build\/lib.bat...<\/span>\r\nDone<\/span>\r\n<\/pre>\n<\/div>\n
Stroll has rebuilt the library but the file bin\/lib\/lib.o<\/span> didn’t change, thus restoring the up-to-date status of the task\u00a0main<\/span>.<\/p>\n
Finally, to clean up after our experiments, let’s create a new task clean<\/span> and place it into a different directory: clean\/clean.bat<\/span>.<\/p>\n
<\/p>\n
\n
$<\/span> cat clean\/clean.bat\r\nrm bin\/lib\/lib.o<\/span>\r\nrm bin\/main.exe<\/span>\r\n\r\n$<\/span> stroll clean\r\nExecuting clean\/clean.bat...<\/span>\r\nDone<\/span>\r\n<\/pre>\n<\/div>\n
The corresponding dependency graph shows two outputs — the deleted binary files.<\/p>\n
\"Dependency<\/a><\/p>\n
As you might have noticed, Stroll uses directories as collections of build tasks related to a common build target. To build a target we simply run Stroll in the corresponding directory. If you’d like to build just a single task from a directory, you can specify the full path, for example:<\/p>\n
\n
$<\/span> stroll build\/lib.bat\r\nExecuting build\/lib.bat...<\/span>\r\n<\/pre>\n<\/div>\n
This executes the\u00a0lib<\/span>\u00a0task (regardless of its current status). Note that the main<\/span> task is currently out-of-date because clean<\/span> deleted its output:<\/p>\n
\"Dependency<\/a><\/p>\n
To complete the build, run stroll build<\/span>, which will execute only the main<\/span> task, as desired.<\/p>\n
Challenge:<\/strong> <\/span>Try to orchestrate a situation, where Stroll would execute one of the tasks twice, hence demonstrating that Stroll is not a minimal build system.<\/p>\n
Under the hood<\/h3>\n
Stroll is implemented in ~400 lines of Haskell (including comments) and uses the following libraries in addition to the standard ones:<\/p>\n