Boost.Build V2 Architecture

Jobs dictated by Jam

First, let's outline the constraints that come from the build tool. The main tasks of any build system using Jam are:

Establish targets
Generate build actions for the targets
Attach variables to the targets which will be substituted into build actions
Establish dependency relationships between the targets
Establish target locations.

I'll refer to steps 1-4 above as "building the dependency graph". There are also some details to handle header scanning, but the list above covers most of it.

Build Procedure

Preamble

We will implement a variation of Rene Rivera's ideas for allowing Boost.Build to work "out-of-the-box", with no environment variable settings. The idea involves searching upward from the invocation directory for "boost-build.jam" and "project-root.jam", which can then be loaded to get the location of the build system installation and project-specific settings, respectively. There are two core Jam extensions I expect to rely on for this functionality:

The PWD builtin rule, which returns the absolute path name of the directory from which Jam was invoked. PWD can be stolen from Matt Armstrong's guest branch at Perforce.
The ARGV builtin rule, which returns the arguments with which Jam was invoked. $(ARGV[1]) can be used to find the name that was used to invoke Jam, which can be used as a key to whether to implement stock Perforce Jam behavior or Boost.Build behavior.
I note that this combined functionality would obviate the need for "subproject" and "project-root" rules in Jamfiles, except where the user wants to declare a project-id.

Initialization

We check the name used to invoke Jam, and if the name is not the recognized Boost.Jam invocation ("bjam") we continue with the execution of the builtin Jambase.

Otherwise, when we recognize a Boost.Jam invocation, we:

We attempt to load "boost-build.jam" by searching from the current invocation directory up to the root of the file-system and in the paths specified by BOOST_BUILD_PATH. Within this, one invokes the "boost-build" rule to indicate where the Boost.Build system files are, and to load them.
If the Boost.Build system isn't loaded yet we error and exit, giving brief instructions on possible errors.
We attempt to load "project-root.jam" by searching from the current invocation directory up to the root of the file-system. When found its location is noted as the PROJECT_ROOT.
Finaly we load the "Jamfile" in the invocation directory. There are various spellings considered when finding the "Jamfile", the pattern for the name must fit: (J|j)amfile[.jam].

** the current Jambase gives an error about FTJam toolset definitions etc., if BOOST_BUILD_PATH is not set and the toolset definition is not set either. Probably that message should be extended to say something about setting BOOST_BUILD_PATH so that people are not confused. The FTJam toolset definitions aren't needed unless you're building Jam itself. Shall we dump FTJam functionality that we don't absolutely need?

Configuration

boost-build.jam first loads two modules, site-config.jam and user-config.jam. We can put empty versions in the Boost.Build directory so that there is no error if users don't put their own somewhere earlier in BOOST_BUILD_PATH (we'll re-use that trick a lot). The Actually, these should probably contain lots of commented-out code which does basic configuration jobs. What do these things look like? For one thing, I'd like to avoid having the user set a bunch of obscure global variables. Let's do this through rule invocations:

     # ---- Sample site-config.jam file ----
     # loads the msvc module, which registers it as an available
     # toolset. No special toolset location/configuration information
     # is given, so it is assumed that the toolset is already set up
     # (e.g. VCVARS32.BAT has been called), or that it's installed in
     # its standard location.
     using msvc ;

     # As above, but tells the system that we have two versions of the
     # gcc toolset installed, in the specified locations, with 2.95.3
     # being the default. The 'using' rule loads the given module and
     # calls its "configure" method with the rest of its
     # arguments. How a module treats configuration information, of
     # course, is up to the module.
     using gcc : 2.95.3 /usr/local/gcc-2.95.3
                 3.0.2 /usr/local/gcc-3.0.2
               ;

     # Same idea as above.
     using stlport : 4.5 ~/stlport-4.5
                     4.6b2 ~/stlport-4.6b2
                   ;

     # does what ALL_LOCATE_TARGET currently does
     locate-built-targets bigdrive:/dave/builds ;

Abstract Target Specification

The system reads the Jamfile in the invocation directory. Jamfiles contain mostly declarative rule invocations. Declarative rules build data structures describing targets (and other things, e.g. toolsets in toolset description files). Of course a Jamfile may also import modules and invoke rules that do more heavy-duty work. There are several important reason to use declarative rules in Jamfiles. First, the current system which constructs a dependency/action graph as each descriptive rule is read is quite inefficient for large projects. Secondly, we are unable to make any delayed decisions based on the entire contents of the jamfile. For example, we might want to do something completely different with the target descriptions, e.g. generate makefiles. Finally, it is too easy for the rules invoked and variables set by the user in a Jamfile to interfere with the build process.

The system traverses the set of top-level targets and generates the dependency graph based on the expanded build description (the algorithm for expanding build descriptions is given at the bottom of this document). OK, so I've tossed off most of the work of the build system in one sentence. The rest of this document deals with that in more detail.

The basic algorithm is as follows:

Determine the subproject requirements
For each main target in the Jamfile:
- Generate the targets which correspond to source files
- Generate the subvariant targets of the main target
- For each subvariant of the main target
  - build the dependency graph between the source targets and the subvariant target

Determining the subproject requirements

This part is simple. The user tells us about the subproject using the following rules:

project.project ( project-id : requirements * : default-build * )

Declares a project or subproject. A subproject's id is a path, starting with the project id of which it is a subproject. The requirements and default build apply to any targets described in the Jamfile which do not explicitly declare others. A project rule invocation is mandatory in any Jamfile in a project which includes subprojects or uses other projects.

project.jamfile-location( root-to-jamfile )

Declares the location of this Jamfile with respect to the project root, in case the path given in the project rule does not describe the location of the Jamfile.

project.source-location( root-to-source )

Declares that relative paths in this Jamfile are all specified relative to the specified directory. Thus, a project with this structure:

root
+- build
|  `- Jamfile
`- src
   +- foo.c
   `- bar.c

might have the following Jamfile:

project.project foobar ;
project.jamfile-location build
project.source-location src ;

exe foobar : foo.c bar.c ;

Generating Targets

Target names given by users in a Jamfile aren't, in general, the names of targets that will actually be used by the build system, since elements such as subvariant grist come into play. In order to keep the system usable, however, ungristed names are "claimed" by the system for NOTFILE targets which correspond to the user's notion of what should be built. When multiple subvariant builds have been requested these NOTFILE targets will depend on several built target files.

Building A Target From Sources

Target declaration rules can of course be written to take the crude route of directly building the dependency graph, but that's makes for a limited, closed system. This describes how rules can be written which allow complex interactions between orthogonal build properties (e.g. STLPort support, Python support, toolset selection). The scheme used by Boost.Build relies on objects called "Generators" to do the work.

Finding the Generator Set

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

required-properties
optional-properties
rules

and an optional "category". If no category is supplied, the generator has the empty category.

A generator doesn't match the build request unless all of its required-properties are contained in the build request.

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)
          $(build-properties:G) # valueless properties match any value
          ] ;
    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 chosen. In each category with a matching generator is found, we select the generators with the longest match for the generator set.

Notes: These criteria handles things like target-type specificity. Properties in an inheritance/refinement hierarchy can be composite properties which expand to add properties for all of their bases. So for example,
<target=type>PYD
might expand to
<target-type>PYD <target-type-base>PYD
<target-type-base>DLL <target-type-base>executable
(see the bottom of this document if you need to refer to the target-type refinement hierarchy). A generator which wanted to match all executables might specify
<target-type-base>executable
as a required property. More-specific generators would still match if available. More-specific generators match better because they list /all/ of the base properties to which they apply:
pyd-generator requires:
    <target-type-base>executable
    <target-type-base>DLL
    <target-type-base>PYD

dll-generator requires:
    <target-type-base>executable
    <target-type-base>DLL

Build Property Expansion

In this step, all selected generators get an opportunity to modify the build properties associated with the build request:

For each generator in the generator set, call its "expand" rule to alter the properties in the build request. Most generators that can actually build targets will not want to implement expand; usually expand will only be used by generators that need to modify the build somehow, e.g. by adding #include paths. Note that the build property set is still one big wad available to all competing/interacting generators, so this would be an inappropriate place for a toolset generator to remove irrelevant properties.

Virtual Target Generation

In this step, each generator has an opportunity to build a representation of the virtual dependency graph for the requested target. By "virtual", I mean that the targets in the graph are objects with a record of their parents, children, build properties, etc., but that no DEPENDS calls or action rules have yet been invoked for them.

For each generator in the generator set, call its "execute" rule. The "execute" rule should return a list of the virtual targets generated in its dependency graph. Generators that don't succeed in producing targets will return the empty list.

At this point, the generator may collect a set of properties relevant to its target construction method into a subvariant identifier. A database of already-generated subvariant identifiers and their related targets can be queried to see if the subvariant already exists. If it does, the generator may use the cached data to return to its caller immediately.

To produce the dependency graph, a generator 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.
Why do we need <source-type>CPP at all? We don't: it's an optimization to prevent less-specific generators from being invoked for build-property expansion or virtual target generation.

Generators are typically matched based on a single desired target-type, but some generators produce more than one target. When returning its list of targets, a generator distinguishes the intermediate from final targets by dividing the list of targets into two sections, separated by a special symbol (say "@", since we seem to be using it for everythign). When an intemediate generator produces multiple targets, its parent transforms the targets it can cope with, and passes back any others to its parent as final targets. A multi-source generator like EXE<-{OBJ,LIB} will add any final targets that it can't cope with to its sources at that point in its list of sources.

Vladimir's favorite example has a dependency graph like this one:
targets   foo
   ^      / \
   |   a1.o a2.o
   |    |     |
   | a1.cpp a2.cpp
   |    |     |
   |  a.whl  a.dlp <--- one build action generates both WHL and DLP
   |     \   /
sources  asm.wd
To make the problem more interesting, let's reformulate the example:
targets   foo
          / \
       a1.o a2.o
        |     |
     a1.cpp   |
        |   a2.cpp
     a1.lex   |
        |     |
      a.whl  a.dlp <--- one build action generates both WHL and DLP
         \   /
         asm.wd
In the case of
EXE<-OBJ*, OBJ<-CPP, CPP<-LEX, LEX<-WHL, {WHL,DLP}<-WD,
--------------------------------------^
The arrow indicates a place where, as we're unwinding, we find that the generator can't cope with DLP, so with final targets enclosed in {}:
EXE<-OBJ*, OBJ<-CPP, CPP<-LEX, {LEX,DLP}<-WHL
EXE<-OBJ*, OBJ<-CPP, {CPP,DLP}<-LEX,
EXE<-OBJ*, {OBJ,DLP}<-CPP
Now find that OBJ* doesn't match DLP, so we search for DLP just like a source.

Before returning from its execute rule, each generator may collect "synthesized" build properties from the sources and/or intermediate targets generated by the matching process it invoked.

Note: A generator does not /have/ to build a new target. It may just modify properties of targets at the next level and pass the targets up to their caller.
For example, a Windows PYD generator might replace the target-type with DLL and reinvoke the process, then go back and add "_d" to the name of the generated file in the case of a Python debug build.

Virtual Target Selection

In this step, we select one of the dependency graphs generated by a generator in the generator set. The criterion is simple: we choose the graph whose generator returned the shortest list of targets. In other words, we choose the shortest path from sources to targets. The root target(s) of the dependency graph are labelled with the generator, so that the generator for any virtual target can be retrieved.

Actual Target Generation

In this step, we recursively descend the dependency graph, invoking the "finalize" rule of the generator associated with each target. In general, this will invoke action rules and DEPENDS to create the internal Jam dependency graph.

Sample Target Type Refinement Hierarchy Diagram


           +--------+                  +--------+ Cmd +-----+ Link +------------+
           | source |       'Archive'..+ object +....>| RSP +.....>| executable |
           +----+---+                : +---+----+     +-----+ :    +------+-----+
                |                    :     |                  :           |
        +-------+----+          +----------+-+-------------+  :      +----+----+
        |            |          |    :       |             |  V      |         |
    +----------+  +--+--+Asm +--+--+ :    +--+--+     +----+---+  +--+--+   +--+--+
    | compiled |  | ASM |...>| OBJ | :...>| LIB |     | IMPLIB |  | DLL |   | EXE |
    +----+-----+  +-----+    +-----+      +-----+     +--------+  +--+--+   +-----+
         |         ^  ^       ^  ^                                   |
     +---+--+      :  :       :  :                                +--+--+
     |      |      :  :       :  :                                | PYD |
  +--+--+ +-+-+    :  :       :  :                                +-----+
  | CPP | | C +....:..........:  :
  +--+--+ +---+ 'C'   :          :
     :                :          :
     :................:..........:
          'C++'

© Copyright David Abrahams 2002. Permission to copy, use, modify, sell and distribute this document is granted provided this copyright notice appears in all copies. This document is provided "as is" without express or implied warranty, and with no claim as to its suitability for any purpose.

Revised 21 January, 2002