Boost logo

Boost-Build :

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-03 17:12:46

Oops, this message was (obviously) not meant to go out yet. Feel free to
read what's there, though.


----- Original Message -----
From: "David Abrahams" <david.abrahams_at_[hidden]>
To: <jamboost_at_[hidden]>
Sent: Thursday, January 03, 2002 4:45 PM
Subject: [jamboost] Building the dependency graph: followup

This is a followup message to the one below (on which I've also corrected
the formatting of the 2nd diagram). I am going to try to treat some of the
questions raised.

I like the idea raised at the end of using a toolset class with overridable
rules to control what gets built. For the most part, that allows an
arbitrarily fine level of control over intermediate targets and

I also don't want to give the toolset too much power. There will be build
jobs outside the domain of the toolset. For example, people will want rules
to generate documentation, e.g. using TeX. I would like the tools for doing
these other jobs to be first-class citizens in the build system; they
shouldn't be folded into the toolset description and they have a similar
need for capability and configuration.

Lex/Flex/Yacc/Bison is an example of a sort of build tool which raises
interesting problems, and thus may help us to discover the right approach.
An abstract target description given by the user for an exectutable target
might well include lex and yacc source, in addition to C, C++, Fortran,
etc... These tools clearly need to be able to cooperate with a toolset to
generate the dependency graph for some abstract targets. Literate
programming tools which extract code from documentation might fall into a
similar category.

I believe that the ultimate arbiter of control ought to be the type of
target being generated. So, the toolset would get "first crack" at any
abstract target that it declares it can generate (e.g. EXE, LIB, DLL,
IMPLIB...). This allows us to deal simply with the simpler cases of, e.g.,
documentation generation which doesn't require the sort of "mixed
intervention" described above for Lex/Yacc: The TeX module would declare. At
that point, the question becomes a bit simpler: when it encounters a source
file which it doesn't know how to handle,

This message is concerned with building the dependency graph. That job
includes the generation of intermediate targets (e.g. when building an exe
from sources, the object files are intermediate) and the invoking of rules
which establish dependency relationships and build actions.

I keep finding myself with the need to create new target types out of
existing ones. For example, a python extension (PYD) is a kind of shared
library. Conceptually, target types form a sort of inheritance hierarchy in
my mind:
+--------+ +--------+ 'Link'
| source | 'Archive'..+ object +..............>| executable
+----+---+ : +---+----+ :
| : | : |
+-------+----+ +----------+-+----------+ :
| | | : | | V |
+----------+ +--+--+Asm +--+--+ : +--+--+ +----+---+ +--+--+
| compiled | | ASM |...>| OBJ | :...>| LIB | | IMPLIB | | DLL | |
+----+-----+ +-----+ +-----+ +-----+ +--------+ +--+--+
| ^ ^ ^ ^ |
+---+--+ : : : : +--+--+
| | : : : : | PYD |
+--+--+ +-+-+ : : : : +-----+
| CPP | | C +....:..........: :
+--+--+ +---+ 'C' : :
: : :

The ALL_CAPS names represent concrete target types. The dotted lines above
represent rules that can be invoked to build one type of target from

Given a "main target" and a set of "source targets", a simple algorithm for
determining the chain of targets and rules might be based on finding the
shortest path in the above graph, traversing inheritance and build action
links, from the source types to the target types. Some open questions:

1. Some rules combine multiple sources into a single target (e.g. Archive,
Link). How does the algorithm decide when targets are combined?

2. It seems to me that in general, a toolset may change the dotted lines in
the above graph. The simplest example I can think of is that of Win32
compilers that use response files, resulting in the following:

+--------+ +--------+ Cmd +=====+ Link
+------------+ | source | 'Archive'..+ object
+....>[ RSP ].....>| executable | +----+---+ :
+---+----+ +=====+ : +------+-----+ |
: | : | +-------+----+
+----------+-+-------------+ : +----+----+ | |
| : | | V | | +----------+
+--+--+Asm +--+--+ : +--+--+ +----+---+ +--+--+ +--+--+ |
compiled | | ASM |...>| OBJ | :...>| LIB | | IMPLIB | | DLL | | EXE
| +----+-----+ +-----+ +-----+ +-----+ +--------+ +--+--+
+-----+ | ^ ^ ^ ^
| +---+--+ : : : :
+--+--+ | | : : : :
| PYD | +--+--+ +-+-+ : : : :
+-----+ | CPP | | C +....:..........: :
+--+--+ +---+ 'C' : : :
: : :................:..........:
Other examples would be front-end C++ compilers that can't produce object
files directly, but need to run some 'C' compiler as the back end. Should we
try to provide this flexibility in a general way, or does it make sense to
ask these toolsets to simply implement the rules in terms of sub-rules, as
we do now for response file handling? The latter approach keeps the basic
graph structure fixed, but allows arbitrarily fine granularity to be
introduced into each construction rule. I am not certain whether the
limitation of a fixed graph structure is acceptable. Thoughts?

One thought might be to use the "class" facility in
tools/build/new/class.jam to make each toolset a separate class with
overridable methods which generate targets from sources. So, the "method"
EXE<-source would be invoked to build an executable from sources. The
default implementation would in turn invoke OBJ<-{type} where {type} is the
concrete source type for each source file, and then Link to build the
executable from the resulting objects. The Win32 response file toolset base
class could implement the outer 'Link' rule by calling the 'Cmd' rule and
the 'inner-link' rule (or something).

A scheme like this one ties the structure of the dependency graph to the
toolset. I am not sure whether that's acceptable, since we're talking about
allowing orthogonal features like STLPort and Python (with multiple version
selection). Does it make sense for so much control to reside with the
toolset, or do these other features need a way to intervene?


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