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 two data structures: a BuildTree and a BuildItem. The BuildTree object has a map from build item names to the BuildItem object for that name. It also has a mapping of relative paths to either build item names or to the empty string in the case of unnamed build items. It stores the path to the root of its backing area and a map from declared external paths to external build tree root absolute paths.

The BuildItem object contains the absolute path of the build item, the path of the root of its local build tree, its backing depth (how many levels of backing areas you have to cross to get to the item), its external depth (how many levels of externals you have to cross to get to the item), and various information read from Abuild.conf or computed from the dependency graph.

When abuild starts up, it finds an Abuild.conf in the current directory (or parent directory if abuild is started from inside an output directory) and follows parent-dir pointers until it finds an Abuild.conf that has no parent-dir key. This is the root of the build tree. Once abuild has found the root of the local build tree, it begins traversal. Before traversing the local build tree, it first traverses the backing area tree and any externals. This is done by calling traverse recursively. Note that we traverse the backing area first since we allow externals to be resolved in backing areas: if no directory exists at the path specified for an external, we see if any backing area declared the same external and, if so, we consider the external reference to be satisfied since we'll get all its items through the backing area. Once abuild has finished traversing the backing area and externals, and therefore all their backing areas and externals, it contains all the information it needs to finish traversing the local tree.

The process by which abuild traverses a specific build tree is fairly straightforward: we traverse through the child-dirs pointers starting from the root build item, ensuring that the links between parents and children are bidirectional. If a directory referenced in a child-dirs key does not exist in the local build tree, abuild computes the location of the missing directory relative to the top of the local build tree and then checks to see whether there is a valid build item at the same position relative to the root of one of the build trees in your backing area chain (but not your externals; they are handled differently). If there is, then we don't consider the lack of that child directory to be an error. Note that we do not do anything with the information about what is actually at that location, we just keep traversing as if that directory were there and had been traversed successfully. In effect, this is exactly what has happened since we have completed traversal of the backing area in which we found the path. This policy has the same effect as searching for unknown build item names in our backing area chain. There is no need to determine that the location in the backing area is the same item or even is a named item at all. In fact, doing so would make it impossible to rearrange build items in local trees with backing areas since our local tree would never be able to diverge in directory structure from the backing area. One side effect of this is that it is not possible to remove a build item name from the namespace in a local tree if that name is present in a backing area by simply removing it from the local tree. If you need to remove an item in this way, you must also list its name in the deleted key of the root build item's Abuild.conf as discussed in Section 10.7, “Deleted Build Item”.

Once abuild has finished traversing the local build tree (skipping any paths that could be resolved in a backing area) and has established a local mapping between names and paths, it then goes through the externals and backing area and supplements its name to path mapping with any names that were found there. Abuild looks in externals first. For each build item in our externals, we check to make sure we don't have the same name locally. If we do and that name resolves to a different absolute path, it's an error. If we do and that name resolves to the same absolute path, we ignore it since it just means we have more than one path to the same build item through various externals, as will become more clear momentarily. If we don't have an item of that name, we copy the BuildItem structure from the external into our own build tree, thus making the name known to us, and we increment the external depth in the copy. Now to clarify the point about multiple paths to a build item through various externals: if some build tree T1 has ../T2 and ../T3 as externals and T2 also has ../T3 as an external, every build item local to T3 will also be a member of T2 since it will have been copied during the traversal of T2. When we try to copy items from ../T3, assuming we copy from ../T2 first, the items will already be there, but it will not be an error. (See Figure 29.1, “Multiple Paths to a Build Item”.)

Figure 29.1. Multiple Paths to a Build Item

/T1 inherits C directly from both /T2 and /T3, but this is not an error since they are the same item.

This does imply that the value of the external depth parameter can be ambiguous, but it doesn't really matter: the only thing that's important about backing depth and external depth is whether they are zero or not.

Once we have done this process for all externals, we perform a similar process for backing areas. For each item that exists in our backing area (and therefore, its backing area and externals) that does not exist in our own tree or its externals, we copy it just like we did for externals, and increment the backing depth of our local copy. If we see a build item with a name that conflicts with an item we already have, we ignore it. This is the normal case of local build items shadowing those in the backing area. We also take care to avoid copying any item from a backing area that was deleted in an external.

After abuild has finished copying build items from backing areas and externals, it iterates through the list of deleted items, verifies that they exist in the current tree with a backing depth greater than zero and an external depth equal to zero (reporting an error if not), and then removes them from the current build tree.

Note that backing areas may have externals and externals may have backing areas. They are, after all, build trees in their own right. This means that a particular build tree may be reachable from the local build tree by multiple paths. Abuild imposes no requirements on the shape of the external and backing area graph (other than it contain no cycles) because additional restrictions are not necessary. Ordinarily, if A1 backs to A2 and B1 backs to B2, then if A1 has B1 as an external, one would expect A2 to have B2 as an external. This means that B2 is reachable from A1 through two distinct paths. There's no reason though that A1 couldn't have backed to A3 which backs to A2. It's even okay if A1 backs to A3 and A3 doesn't back to anything as long as A3 doesn't depend on anything in one of the B areas. This flexibility makes it possible to do things like add dependencies on new externals or remove dependencies on externals from a side branch in your version control system. If abuild placed restrictions on the shape of the backing area/external tree, many of these operations would not be possible. Abuild enforces its integrity guarantee directly, and that's really a strong enough check to ensure that backing area/external anomalies that matter will be caught.

There is nothing inherent about abuild that would preclude an implementation that allows multiple parallel backing areas to be declared for a single build tree, but given the availability of externals and the fact that backing areas are transitive (a build tree inherits from its backing area's backing area), it should be sufficient to have only a single backing area, and it simplifies both abuild's own internal logic and the ability for a user to figure out what is going to be found where. Besides, in order for abuild's guarantee to be satisfied, it would be necessary for every build tree to search its backing areas' backing areas in the same order anyway. ^[48]