Re: build system rules & algorithms

[Paul Smith]

On Fri, 2009-06-19 at 14:35 -0400, Mike Shal wrote:
> On 6/18/09, Paul Smith <address@hidden> wrote:
> > The major difference between an "Alpha" and "Beta" build system is more
> >  fundamental.  The idea behind a "Beta" system, as I understand the
> >  paper, is that BECAUSE it knows a priori which source files have changed
> >  it doesn't have to walk the DAG "backwards" starting from the goal and
> >  working back to the sources like make does.  Instead it can start with
> >  the sources, since it knows them already, and work forward towards the
> >  goal.
> >
> >  This reduces the complexity and scope of the "possible paths" searching
> >  through the DAG and gives you a lot of performance improvement,
> >  especially on builds where only a few source files have changed.
> 
> This is an excellent summary. Perhaps I should've had you write the
> paper - it would've been much more concise :).

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?

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.

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.