make depend

[Wayne Throop]

In <853 at enea.UUCP>, Kim Walden objects to the notion of dynamic
dependency derivation, saying:

>I do not agree with your proposal, because:
>
>        1. Very few people really understand the implications
>           of make's basic model as it is, so the least thing
>           we would want to do is to complicate it further.
>
>        2. It would not solve the problem anyway.
>
>           In the example, make itself forces the generated file foo.c
>           up-to-date before invoking a command to extract include lines
>           from it.
>           But an extraction command will have to deal with nested includes,
>           and when an INCLUDED file is a generated file, the command cannot
>           force it up-to-date, and hence cannot proceed to search the
>           file for more include lines.
>
>           The hen-and-egg syndrome is still there, and cannot be
>           circumvented.

I find myself agreeing with point 1.  Adding yet another wart to make is
not the answer.  However, point 2 turns out not to be the case, since I
use an existing make-like tool that dynamically derives dependencies.
Kim's objections are quite valid, but my original posting (in
retrospect) did not adequately present my position.  Let me try to
clarify.

First, my example was illustrative only.  I did not mean to imply that I
thought that warping the existing make was the proper way to proceed.  I
chose a make-like syntax, since most readers are faminiar with it.  The
actual syntax of the tool I use is very un-make-like, as is it's basic
model of the world.

Second, when I said in my original article that the "include file
includes another file" problem could be solved, I had reason to be
pretty sure I was right.  Because it has been solved.  Granted, it has
problems with conditionally included files, but then, so does Kim's
tool.  I made no claim to dynamic derivation's superiority, just that it
was a viable alternative.  (On the other hand, since user-specified
dependency rules can easily be added, it probably IS better in cases
where non-standard derivations are used.  Back on the original hand, it
is NOT better in cases where all the transforms you want to apply are
known to a make-file generator.)

So: how does it deal with the include file problem?  Well, the basic
model is that for each buildable item there is a derivation action, and
a construction action.  The derivation action tells the dependency
manager what items need to be built before the construction action can
take place.  If these are include files, they have derivation actions
that specify that the recursively included files must be available
before the level-one include file can be considered available.

Given the sources
    foo.c
        #include "a.h"
        foo(){}
    a.h
        #include "b.h"
    b.h
        /* no more includes */

Our automated build tool produced this trace:

    % 01 VISITING foo.c.cc
    % 02   DERIVING foo.c.cc
    % 03     VISITING foo.c.c_source
    % 03       Changed:   File sources:foo.c
    % 03       Invoking build macro for foo.c.c_source
    % 03     END VISITING foo.c.c_source {Ok}
    % 02     Changed:   File foo.c
    % 02     Invoking derive macro for foo.c.cc
    % 02   END DERIVING foo.c.cc {Ok}
    % 02   VISITING a.h.c_source
    % 03     DERIVING a.h.c_source
    % 03       Changed:   File sources:a.h
    % 03       Invoking derive macro for a.h.c_source
    % 03     END DERIVING a.h.c_source {Ok}
    % 03     VISITING b.h.c_source
    % 04       DERIVING b.h.c_source
    % 04         Changed:   File sources:b.h
    % 04         Invoking derive macro for b.h.c_source
    % 04       END DERIVING b.h.c_source {Ok}
    % 03       Changed:   File sources:b.h
    % 03       Invoking build macro for b.h.c_source
    % 03     END VISITING b.h.c_source {Ok}
    % 02     Changed:   File sources:a.h
    % 02     Changed:   File b.h
    % 02     Invoking build macro for a.h.c_source
    % 02   END VISITING a.h.c_source {Ok}
    % 01   Changed:   File foo.c
    % 01   Changed:   File a.h
    % 01   Invoking build macro for foo.c.cc
    % 01 END VISITING foo.c.cc {Ok}

A lot of huffing and puffing to go through for a fairly simple compile,
but note that in these cases foo.c, a.h and b.h are all GENERATED FILES!
That is, they didn't exist in the file system at the start of the
"make", but were instead in a source archive.  The "Invoking build macro
for <mumble>.c_source" are the "extract from archive" actions.  Thus
there is nothing to prevent the derive action for a.h to force b.h to be
created on the fly, if b.h is produced by something else.  In fact, this
sort of thing is done in many of our automated builds.  The crucial
ability here is that derive actions can communicate with the dependency
manager.

The chicken-and-egg problem does not arise here.  In fact, if there are
no circular dependencies, I don't see how it CAN arise.  And, if there
are circular dependencies, I don't see how any automated method can do
much better.

The crucial points I am trying to make:
  - Dynamic derivation is conceptually simple.
    In a dynamic derivation, a derive rule needs only to know locally
    what is going on.  EG, I have a C file as input and I want to know
    what include files there are.  I don't need to worry about the fact
    that the C file was produced YAPG (yet another program generator),
    nor do I care what the original source was, or even if there WAS an
    original source in any traditional sense.  In a from-source
    derivation, the deriver needs to know globally what transforms are
    going to be made.
  - Dynamic derivation is flexible.
    It is easy to add new derivation rules, and these new rules don't
    need to know about how the entire world fits together.
  - Dynamic derivation is practical.
    It exists in a working system, and further development is proceeding
    on these tools.  It turns out that I am not at liberty to distribute
    these tools (and they don't run under unix anyhow), but I can do the
    next best thing and distribute the idea.  As Kim pointed out,
    enhancing make is not the best way to implement dynamic dependancy
    generation.  Creating a simpler but more flexible tool "from
    scratch" seems a better idea.  (A reasonable first-cut version of
    the tool itself can be implemented in a couple of man-weeks.)
-- 
Wayne Throop at Data General, RTP, NC
<the-known-world>!mcnc!rti-sel!rtp47!throopw