Re: build system rules & algorithms

[Paul Smith]

On Thu, 2009-06-18 at 12:43 -0600, Tom Tromey wrote:
> >>>>> "Stephan" == Stephan Beal <address@hidden> writes:

> Checking dependencies on command text is possible, as is checking
> dependencies using file contents (as opposed to timestamps).  I think
> there is a patch for GNU make to implement this.  Also, I think these
> can be done currently using GNU make, though this requires weird code
> and is not pleasant.

There was a Google SOC project done to implement "user-defined out of
date handlers" in GNU make.  The final result was a fairly large patch
that did work.  More due to my lack of time than any fault of the SOC
coder, some of the user interface details in the end result seemed to me
to be too complex and I want to simplify them.  He is still working with
me on this; we are implementing this feature set as incremental changes
that are useful on their own, then tackling the next part.

I don't know how this will fare from an efficiency point of view,
however, since as designed now all of the guts of the dependency
checking are done through shell-out etc.

If there was an oracle such as you mention below that could be
integrated here I expect.

> As for turning make into a beta system: it seems like it could be done
> with a small inotify-based daemon.  An initial 'make' could run it and
> have it track relevant directories (perhaps telling it to add
> directories in subsequent runs).  Then, make would use it as an
> oracle: ask it about file status and get back answers.  Finally, if
> inotify fails, the daemon could fall back to invoking stat, meaning
> that make would continue working as it does now.
> 
> Is there a flaw with this plan?

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.

I don't think replacing the current "stat" implementation with a query
to an oracle would be a performance improvement, without the rest of the
changes to the basic algorithm of make.