This section describes how abuild traverses build trees to resolve build item names to paths. Here we describe the process at a level of detail that is closer to the code. The traverse function in the abuild source code is responsible for the behavior described here. It will likely be necessary to read this section more than once to fully understand what is happening as some parts of the description won't make sense without knowing about parts you won't have read yet. (Fortunately, the human brain is better at resolving circular dependencies than a build system is.)

Internally, abuild maintains tree data structures to hold onto the shape and contents of build forests: BuildForest, BuildTree and BuildItem. The BuildForest object has a map from build tree names to BuildTree objects and also from build item names to BuildItem objects. The BuildForest object also contains the list of backing areas that apply to the forest as well as the list of items and trees that are specified as deleted in the Abuild.backing file.

The BuildTree object contains tree-specific information, such as the tree's list of plugins, tree dependencies, supported traits, etc. It also contains the absolute path of the root build item of the tree. The BuildItem object contains the absolute path of the build item, the name of the containing build tree, its dependencies, and various other information from the Abuild.conf file. Additionally, both objects store the tree's or item's backing depth, which is a count of the number of backing areas that had to be followed to resolve the item or tree. Although the backing depth is an integer value, nothing in abuild cares about the depth other than whether it is zero or not. A backing depth of zero indicates that the tree or item appears locally in the current forest.

When abuild starts up, it first locates the root of the local forest. It does this by starting with the current directory and walking up the file system (toward the root) until it encounters an Abuild.conf that is not referenced as a child of the next higher Abuild.conf, if any. When it finds such an Abuild.conf, it verifies that it is either a tree root build item or that is has only a child-dirs key. In either case, it is the root of the forest. Otherwise, it is an error, and abuild indicates that it is not able to find the forest root.

Once abuild has found the root of the local build tree, it begins traversal. The actual traversal logic is more complicated than what is described here because it contains code to recognize the abuild 1.0 build tree structure (with external directories and unnamed trees) as well as the simpler 1.1 format. We omit those details from the description and refer you instead to comments in the code. Continuing with our description of the 1.1 traversal algorithm, we just read each build item's Abuild.conf doing a breadth-first traversal of the tree formed by following child-dirs keys. If the child directory does not exist and the forest has a backing area, we ignore this condition. This is what allows backed forests to be sparse. Otherwise, if the directory exists, it must have an Abuild.conf, and no directory between the child directory and the parent may have Abuild.conf files (possible only if a child-dirs value has multiple path elements).

After traversing the local forest, abuild traverses each backing area, creating a separate BuildForest object for each backing forest. Finally, once abuild has traversed all the build items in all known forests, abuild creates a dependency graph of backing areas. Then, working from the leaves of the dependency graph, it copies into the forest from the backing areas all the BuildTree and BuildItem objects of items and trees that do not appear locally and increments the backing depth of the local copies. Items that are marked as deleted or that are in trees that are marked as deleted are not copied. Also, trees that are marked as deleted are not copied. This is where abuild notices if you have multiple backing areas and one of them backs to another. In this case, abuild simply ignores the further back of the backing areas since it will already get copies of those items and trees through the closer backing area.

Finally, after all the traversal is completed, abuild validates each forest, again starting with the furthest back forest and working toward the local forest. Numerous validations are performed. For details, please refer to the validateForest method in the abuild source code.