Boost logo

Boost-Build :

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-13 14:36:52

On building the dependency tree, I think I see what to do.

Building a target from sources goes like this:

construct a set of build properties by expanding the build property set
find G, the set of generators which match the build property set
remove all but the "most-specific" matches from G
find the generator in G which would generate the least nonzero number of
invoke that generator to build the dependency graph for the target

For this procedure to work, generators clearly have to be more than just
functions: they should be "objects" of some kind, probably based on the new
class.jam module. I'm now going to describe the details of how the system
interacts with these generators. Please keep in mind that making generators
into classes can help to hide the details of this process from the
implementor of a particular generator. Don't be surprised if this seems a
bit low-level.

Generators will be chosen based on a set of build properties. A generator's
matching criteria are composed of 3 lists:


A generator doesn't match unless all of its required-properties match
The matching process for a generator looks like this:

local match ;
if $(required-properties) in $(build-properties)
match = $(required-properties)
[ set.intersection optional-properties $(build-properties) ] ;
for local r in $(rules)
match = [ $(r) $(match) ] ; # maybe some other arguments, too
return match ;

The specificity of a match is given by the length of its match list.
Basically, generators that match more properties will be more likely to be


The generator will have a function which returns the targets it would
produce when satisfying a build request. To produce this list it may well
invoke the matching and target calculation process again on some or all of
the source files, with the build property set changed to reflect the
generator's input target types. For example, a generator for executables
comes across a CPP file in a list of sources. It then replaces target types
in the build request with its list of input target types (OBJ LIB,...). The
matching process finds a generator which matches <target-type>OBJ with
optional <source-type>CPP. This generator, if eventually selected, is the
one that invokes the C++ compiler.

Why is CPP an <source-type>CPP an optional property for the C++ compiler?
Consider what happens when a a YPP source file appears in the list of
sources: the C++ generator should still be matched - it will want to invoke
the matching process itself once again, hopefully finding a generator which
matches <target-type>CPP/<source-type>YPP.

Any generator whose target calculation is invoked at this step is free to
cache the information it has produced for re-use in the graph building
phase, which comes next.


Rather than making 2 passes into each generator, perhaps it would be better
to do it in a single pass. The only reason to do it in 2 passes is to avoid
generating lots of extra targets which won't get used. On the other hand,
the make procedure starts from the requested targets and descends the
dependency graph. If after each matching step we simply refuse to link any
targets other than the ones on the shortest path into the dependency graph,
we may do much better. This manages to avoid all problems of cacheing the
results of target calculation, for example. If we want to do any
postprocessing on the targets (e.g., invoking rules with action blocks, I
don't know what else), we only need to make a record of the dependency graph
which is accessible to the Jam code. It's easy enough to do that by
providing a bottleneck routine for establishing dependencies (we want that

How does this sound?


David Abrahams, C++ library designer for hire

C++ Booster (
email: david.abrahams_at_[hidden]


Boost-Build list run by bdawes at, david.abrahams at, gregod at, cpdaniel at, john at