33.6. Construction of the Build Graph

During validation, abuild creates a DependencyGraph object to represent the space of build items and their dependencies. It performs a topological sort on this graph to determine dependency order as well as to detect errors and cycles in the dependency graph. During the actual build, abuild needs to expand the dependency graph to include not just build items but build item/platform pairs. Every “instantiated” build item has to exist on a particular platform. We refer to this platform-aware dependency graph as the build graph. The build graph can be inspected by running abuild with the --dump-build-graph command-line option. For information about the format of this output, see Appendix H, --dump-build-graph Format.

33.6.1. Validation

There are several steps required in order to determine exactly which build items are to be built on which platforms and which build item/platform pairs depend on which other pairs. Before we do anything else, we need to perform several validations and computations. The first of these is the determination of what platform types a build item belongs to. For most build items, this is simply the list of platform types declared in the build item's Abuild.conf file. For build items that have no build or interface files, there are no platform types declared. In this case, the rules are different: if the build item declares any dependencies and all of its directly declared dependencies have identical platform type sets, then the build item inherits its platform types from the items it depends on. Otherwise, it has no platform types and has the special target type all. Note that this analysis is performed on build items in reverse dependency order (forward build order). That way, every build item's platform types and target type has been determined before any items that depend on it are analyzed.

Once we have determined the list of platform types for each build item, we can figure out which platforms a build item may be built on. We refer to the list as the buildable platform list. The buildable platform list for a build item is included in the --dump-data output (see Appendix F, --dump-data Format). Note that this is generally a broader list than the list of platforms on which a given build item will actually be built; the actual build platform list is determined later in the build graph construction process. For build items that have a specific target type and platform types, the list of buildable platforms is the union of all platforms supported on all platform types a build item has. For items of target type all, we don't explicitly compute a buildable platform list. These platforms are allowed to “build” on any platform since there are no actual build steps for such build items. (Remember that for a build item to have target type all, it must not have any declared platform types, and this in turn means that it must have no build or interface files.)

When we compute the buildable platform lists, we also pre-initialize the build platform list (the list of platforms on which the item will actually be built) by including all buildable platforms that are selected by default on the basis of any platform selectors, as described in Section 24.1, “Platform Selection”, that may be in effect. For build items of target type all, we would not add any items to the list at this step.

All of the above steps can be completed without knowing which build items are actually included in the build set. These computations, in fact, are determined at startup for every build item in every known build tree regardless of whether the items are in the build set.

The above validations are all completed before abuild starts to build. If any errors are found in the above checks, abuild will report them and exit before it attempts to construct the build graph. This means that the build graph construction itself can operate under the assumption that all of the above constraints have been satisfied.

33.6.2. Construction

The next step is the construction of the actual build graph itself. This is performed only when all previous validations have been performed successfully, and this step is also performed only for build items that are actually in the build set. We present a prose description of the process here. For a fully detailed description, please read the comments and code in addItemToBuildGraph in Abuild-build.cc (and in other places it references) in the abuild sources.

We construct the build graph in reverse build order; i.e., we start with least depended-on build item and end with the most depended-on build item. That way, each item is added to the build graph before any item it depends on is added. This is the opposite of the order in which we compute the platform types. This makes it possible to modify an item's build platform list while processing items that depend on it. Therefore, at the time a build item is added to the build graph, its build platform list will have been fully computed. The build platform list may be the initial list as computed during validation, or it may have been modified during the addition of its reverse dependencies to the build graph. When a build item is added to the build graph, a node is added to the build graph for each platform on which the item is being built. Each node of the build graph therefore corresponds to a build item/platform pair. [65]

Then, for each direct dependency, we determine which instance of it (which of its platforms) we will depend on for each of our platforms. If the dependency in question is declared with a platform selector, we pick the best platform from among the dependency's buildable platform list that satisfies the platform selector and make this the override platform. If there are no matches, it is an error. If an override platform is selected, it applies to this dependency for all instances of the current item.

Next, still processing an individual dependency, we iterate through the item's list of build platforms to decide which of the dependency's platforms each instance will depend on. We refer to this as the dependency platform. If we previously computed an override platform for this dependency, we just use that as the dependency platform. Otherwise, we pick the best match from among the dependency's buildable platform list. If the dependency is type all, it can be “built” on any platform, so the dependency platform is the current build platform of the item. If the dependency is actually buildable on the exact platform that we are considering, then it is the best match and the dependency platform is the current platform. Otherwise, we have to search for a platform from a compatible platform type. To do this, we determine the platform type that contains the current platform and then get a list of compatible platform types (as discussed in Section 24.2, “Dependencies and Platform Compatibility”) in order of preference. Then we iterate through this list until we find a platform type that is in the dependency's list of platform types. Once we have identified this type, we find the best matching platform in that type and use that as the dependency platform. The best matching platform will be first selected platform, or if no platforms are selected, then it will be the first unselected platform. If no platforms are available, it is an error.

If we have successfully determined a dependency platform from among the dependency's buildable platform list, we next add that to the dependency's actual build platform list if it's not already there. This is the mechanism by which as-needed platform selection occurs. An example of this is presented in Section 24.5, “Cross-Platform Dependency Example”. So if item A on p1 wants item B on p2, then item B will be built on p2 even if p2 would not have been selected to build for B based on platform selectors. There are many ways in which this can happen including B being in a different build tree with different plugins or A using a platform-specific dependency to depend on B.

33.6.3. Implications

Even if the exact steps of constructing the build graph are involved, there are some implications that are worth separate discussion. Specifically, a build item of target type all may depend on any build item, and any build item may depend on an item of target type all. For other build items, if a build item depends on another build item and declares the dependency with a -platform=selector option, the dependency must have the platform type mentioned in the platform selector. If a build item depends on another item without a platform-specific dependency, the dependency must be buildable on at least one platform type that is compatible with (or exactly matches) each platform type of the depending build item. Since all platform types are compatible with indep, this means that any build item may depend on any other build item whose target type is platform-independent. (This was actually a special case prior to abuild 1.1.4, but now it falls out from the fact that indep is made the parent platform type of all platform types that don't declare a parent.) For example, if A has platform types X and Y and depends on B which has types X, Y, and Z, this is okay because B has all of A's platform types. Likewise, if platform types X and Y both declared type XY as a parent and B has types XY and Z, that would also be fine since each of A's types can be matched with at least one of B's types. It would be an error if B depended on A in either case since the instances of B building for platform type Z would not be able to satisfy their dependences on A since it doesn't support that platform type or anything compatible with that platform type.

Another important point involves the exact way in which we search for a compatible platform. Note that we first search for a compatible platform type and, once we have found one, we pick the best platform in that type. This is subtly different from picking the first matching platform from any compatible platform type. To illustrate the difference, consider the case of A, which has platform type X, depending on B, which has platform types Y and Z, where X declares Y as a parent and Y declares Z as a parent. In this case, A on X will always depend on B on Y even if Y has no platforms and Z does. The reason for this is that platform types are static but platforms within types are influenced by the environment. If Y has no platforms, this should result in a build error. If we fell back to Z, instead the lack of platforms for Y would actually change the shape of the build graph, which goes against abuild's design. If it were specifically desired to fall back on one thing if something else weren't available, there are ways to make that happen (using autoconfiguration or other similar mechanisms) that don't require the actual build graph itself to change shape.

There are also some implications of the way pass-through items (items of type all) ignore dependencies when no matching platform is available. This is discussed in Section 24.4, “Dependencies and Pass-through Build Items”. Specifically, if a pass-through item depends on multiple items of different types, it's possible for the pass-through to effectively connect one of its reverse dependencies to multiple of its forward dependencies. So if A depends on P which depends on one item of type indep and one item of A's platform type, A will end up with both of P's dependencies in its dependency list. This is a consequence of the fact that the dependency platform computation is performed separately for each build platform and for each dependency of a given item.

[65] The actual build graph node is a string made up of three fields: a fixed-width numeric prefix representing the build tree, the item name, and the platform name. Numeric prefixes for the trees are assigned based on a topological sort of the tree dependency graph. When build graph nodes are sorted lexically, the result is a topologically sorted list of trees each containing a lexically sorted list of items in the tree. This is the mechanism that abuild uses to build items in less dependent trees before items in more dependent trees.