Re: build system rules & algorithms

[Mike Shal]

On 6/19/09, Paul Smith <address@hidden> wrote:
> The things that I wonder about are the kinds of things that always trip
>  up makefiles.  For example, what if a target updates another file as a
>  side-effect?  Presumably tup starts with a set of files that it knows
>  have changed but how does it handle changes to files that happen while
>  tup is running?

Some of the confusion here might be because the paper is slightly
mis-representative of how tup actually views the DAG. The file-based
nodes in the DAG are always inputs and/or outputs to command nodes.
Each command node has an NxM relationship, and it is required that all
outputs of a command are specified. The reason this isn't really
covered in the paper is because I'm not certain the
commands-in-the-DAG approach is necessarily optimal. At least, I've
made no attempt to prove that it is.

I guess here you're thinking about how make would generate parse.h as
a side-effect of generating parse.c when running bison on parse.y. In
tup, both parse.c and parse.y have to be specified as outputs of the
bison command. If the user doesn't specify an output, tup should catch
it and return an error. Similarly for the parallelism guarantee, if a
command reads from an input that itself is an output of another
command, the user must specify that in the Tupfile. If not, it also
returns an error. Here is how the RMCH DAG would look to tup:

http://gittup.org/tup/tup_dag_3.png

(This was hand-generated, since the real graph has some extra info in
it corresponding to directory ownership and such). The tup
implementation of the update algorithm basically takes the input
"main.c was changed", then walks the DAG and executes the command
lines in the rectangular nodes. The oval (file-based) nodes are merely
used for ordering the topological sort. You can see that if parse.y is
in the input list, there is no decision-making or worry about
side-effects when it gets to parse.c - both parse.c and parse.h will
have already been generated by the bison command.

I don't think tup handles the case where the user modifies a file
while tup is running particularly well. Ideally tup would stop the
existing build and restart it. At present, it is up to the user to do
it.

>  What about commands that output multiple targets?  What about "barriers"
>  in parallelism where you need X to complete before Y can run, but you
>  don't need to rebuild X just because Y completed.  If you look through
>  some of the advanced features of make, they were added to support
>  specific, important use-cases.

The bison command above is an example with multiple targets. As for
barriers, I think tup handles the case where you want to auto-generate
a header file before compiling C files pretty well. Tup has an
"order-only" prerequisite list, similar to make. If you list a header
in the order-only list, then during the initial build, the header will
be generated before any of those files are compiled. If the generated
header changes, only the C files that actually included it are
re-compiled. There may be other examples of barriers where tup falls
flat, though. I have only really experimented with the auto-generated
header/C file example.

>
>  I guess part of the question is the expressiveness of the tupfile
>  syntax.
>
>  To be honest I've been "thinking backwards" like make for so long that
>  it's hard to think forwards in a general way.  I think I'd need to sit
>  down with some concrete examples of strange and unusual build situations
>  and decide (a) whether they were strange only because of the way make
>  works and a "Beta" build system would allow them to work more
>  straightforwardly, or (b) if they're really problematic cases and how
>  one would approach them in a "Beta" system.

In the coming weeks I hope to put up a page that walks through the
process of building up a project, along with the corresponding graphs.
I don't know if that will really help answer the question of whether
or not the unusual situations are more straightforward in general for
Beta systems. I imagine Beta systems will have their own
idiosyncrasies for certain build problems as well. If you come up with
particularly strange build situations, I might like to add them to tup
as tests. Sometimes I wonder if a build system is nothing more than a
random collection of corner cases...

Thanks!
-Mike