GSoC: OOD detection

[Paul Smith]

Hi all; sorry this is a bit slow.  Soccer season is starting and I'm
very busy!  This email will be a bit of a brain dump so please bear with
me.

First, to be clear: there is no definitive, set-in-stone design yet, by
any means.  The patch Ramon sent was really just a first stab at coming
to grips with what it might take to implement the feature.  There are
lots of decisions to be made and nothing has been ruled out yet.

That being said, I do have a number of ideas that have been percolating
in my brain over the years.  Of course they could well be completely off
the mark.  Please feel free to speak up: it is in no way too late!

Before anything else, it's important to realize that there are two
distinct, yet interdependent capabilities we are discussing here: the
first is the ability to use a separate algorithm for OOD determination,
and that's the one we've been talking about so far.  But the second one
is at least as important and, in my opinion, the more challenging
design-wise: that is stateful make; the ability to keep some state
information across invocations of make.  I don't think there are too
many OOD algorithms that you can choose that wouldn't require persistent
state.  Deciding how to store that state, especially when you don't
really know what format it will be in (obviously the state to be stored
will vary with the OOD algorithm chosen), provide it to the OOD
algorithm, etc. is a design challenge.

So, let's talk about the OOD algorithm first.  Ramon's suggestion was to
have the OOD algorithm actually be customizable on a per-target basis.
Apparently the Plan9 build tool can do this.  As soon as I read that I
immediately thought that providing the OOD algorithm as a variable
value, and allowing us to take advantage of target-specific variables,
is a very nice feature.  And, as Ramon points out, it CAN be changed
without modifying makefiles by setting the value on the command line
(whether this will actually work or not depends on the algorithm and the
makefiles, as Tom points out).

In more detail, this is what I was thinking from a user interface
standpoint:

     1. The value of the .OUT_OF_DATE variable would be expanded once
        for each target when make tries to decide if that target is out
        of date; this would be after each of the prerequisites have
        already been evaluated of course.
     2. The .OUT_OF_DATE value would obtained using the normal methods:
        first via target-specific and/or pattern-specific values, and
        failing that the global value.
     3. All of the automatic variables for that target would be in-scope
        when the value is expanded, so things like $@, $<, $^, and $?
        can be used.
     4. The result of the expansion would either be the empty string
        ("false", in make terms), in which case the target is declared
        up-to-date, or a non-empty string ("true", in make terms), in
        which case the target needs to be rebuilt.
     5. If the target needs to be rebuilt (.OUT_OF_DATE expands to a
        non-empty string), the expanded value would be kept as the
        "state" for that target.  This value would be made available in
        the target's command script as a new automatic variable,
        something like $= maybe.  Obviously this value would also be
        available to the .OUT_OF_DATE expansion the NEXT time the target
        was evaluated (as in step #3 above).  To be clear: when
        expanding .OUT_OF_DATE, the value of the automatic variable
        would be the PREVIOUS state value; when expanding the commands
        for a target the value of the automatic variable would be the
        NEW state value after expanding .OUT_OF_DATE.
     6. If the rebuild of the target fails, then the state for that
        target is thrown out.

There are obviously a lot of things to decide here.  It may well be, for
example, that just using the expansion of .OUT_OF_DATE as the target
state is not good enough; for example some algorithms might want to keep
some state regarding the target AFTER it's been built; .OUT_OF_DATE is
expanded BEFORE the target is built, obviously.  Also, it's almost
certain that some algorithms will want to know what the expanded command
script will be (to implement something like Solaris make's .KEEP_STATE
feature) so we'll have to introduce a variable containing that value...
but that's problematic as well since just expanding the command script
twice can change its behavior (what if it contains a $(shell...) or
$(eval...)?).  This might be an example of state that can't be kept
until after the command script is completed.

And of course there's the difficulty of how make actually stores the
state, as I mentioned above.  Whatever method is used needs to be robust
in the face of parallel make, and multiple concurrent invocations of
make in the same directory, with the same makefile.

Also there's the problem Ramon mentioned about the inheritability of
target-specific variables.  This cuts both ways: I can easily see it
being DESIRABLE to inherit the value of .OUT_OF_DATE, as well as
undesirable.  It may well be that we will have to solve this problem by
introducing some way of having target-specific variables that are not
inherited.

Additionally, I do have concerns about performance, just as David
mentioned.  There are a couple of points to make here:

     A. Hopefully in the same release as this new feature, we will have
        Guile integrated as an embedded scripting language.  This will
        give a lot of flexibility for creating .OUT_OF_DATE values
        without requiring the use of $(shell ...).
     B. We could easily create some pre-defined OOD algorithms that we
        think people would like to use quite often, and have those built
        in (written in C in make).  For example, the default value
        for .OUT_OF_DATE could be "time-last-modified" which would be a
        built-in value that uses the "traditional" make OOD algorithm.
     C. We could also do something such as David suggests with plugins.
        I'm not sure about this, but it's possible we could even get
        that for free from Guile, as they might have some kind of plugin
        capability similar to Perl's, etc.


PS. I am in no way wedded to any of the variable names here: if you have
suggestions you like better please let us know!

-- 
-------------------------------------------------------------------------------
 Paul D. Smith <address@hidden>          Find some GNU make tips at:
 http://www.gnu.org                      http://make.paulandlesley.org
 "Please remain calm...I may be mad, but I am a professional." --Mad Scientist