I want to make things as simple as possible, but no simpler. -- Albert Einstein
This document describes the dependency resolution module of Rebar, a proposal for the SC Build and SC Config sections of the Software Carpentry design competition. The dependency resolution module falls under the SC Build category. A separate submission covers the Config module. That document should be read before this one.
Rebar is a radically simple proposal, motivated in large part by the needless complexity of the existing toolset. One can expect many advantages of this simplicity. Further, if the design is found to err on the side of too simple, it should be easy to add needed features later.
A great deal of the needless complexity of the existing make/autoconf toolset comes from improper factorization of the problem. The Rebar design addresses this by proposing a single tool to take on the functions traditionally performed by both make and autoconf, not to mention automake, libtool, and the gnome-config. The Rebar design is quite simple in spite of the ambitious scope.
The operation of Rebar on a project consists of three phases:
This document covers only the last step, as these are the functions corresponding most closely to the role of make in the traditional toolset.
As a result of the overall Rebar architecture, the dependency resolution module has no interface of its own. Rather, it simply uses the main Rebar interface, described in more detail in the Rebar configuration proposal.
As such, this document contains no man pages or examples of usage.
We do, however, propose an internal interface within Rebar to keep the implementation modular. Basically, the dependency analysis module passes an acyclic dependency graph, with each intermediate and final target represented as a node, and each dependency as an edge. The dependency resolution module also has access to the resolved configuration parameters (such as choice of compiler, compile flags, etc).
The basic functionality is simple almost to the point of being trivial. Rebar simply traverses the dependency graph in a topologically sorted order, at each point invoking the actual compiler or other tool specified in the configuration parameters. As such, an extremely simple implementation of the Rebar interface is practical.
However, there are a number of more advanced features that are highly desirable and warrant additional implementation complexity. First, Rebar should be able to build in parallel, much as make -j. Second, Rebar should maintain a cache of intermediate targets with different configuration parameters. For example, it makes sense to keep .o files around for optimized, debugging, and profiling versions of the build. The user should be able to request any of these builds, and have only a minimal number of .o files recompiled. The traditional toolset does not support this feature, and it is in fact quite time-consuming and painful to switch between build versions.
A good way to implement this cache would be to use the hash of all inputs to a target and relevant configuration parameters as a key into the database. Any reasonable replacement policy, such as LRU, should work effectively to keep the size of the cache manageable.
An extremely common error in writing Makefiles is neglecting to include a dependency. Often, make builds the project correctly anyway for the original developer. A common symptom is that make -j 1 works all of the time, while a higher degree of parallelism causes failures (the ORBit project was a long-suffering victim of this problem).
Rebar proposes a "sandbox mode" to solve this problem, in which targets are built in a sandbox containing only the inputs listed in the project file. Thus, if any of these inputs are omitted, the build will fail immediately and reliably.
Often, the result of a build step may require further dependency analysis. For example, a piece of autogenerated code may include a header file. This dependency cannot be known until the code is generated. Thus, the internal interface contains a mechanism to invoke the dependency analysis step, augmenting the dependency graph as it is built.
This recursive behavior is a rather strong argument for combining the configuration and build tools into one - the other alternative is to provide a mechanism for recursive invocation of the tools as is currently done in make and autoconf. This mechanism is a source of great complexity and is quite error-prone.
Simply resolving the dependencies, once they are analyzed by a configuration tool, is a very simple task. By integrating it into the config tool, we avoid the complexity of requiring another interface. Yet, even such a simple approach is capable of more "advanced" features such as sandbox mode, well beyond reach of the traditional make/autoconf toolset. In conjunction with the configuration and dependency analysis modules of Rebar, I believe the module outlined here would make an extremely useful tool for building software.
This document is released under the Software Carpentry version of the Open Publication License.