Transitive VS Non-Transitive Dependency In Build

Introduction

In computer science, dependency is a concept used to describe the relationship between different entities. In the context of build system, dependency is used to describe the relationship between different build targets.

In this article, I will discuss two types of dependencies, including transitive dependency and non-transitive dependency, and their applications in modern build systems, such as CMake and Bazel.

Transitive VS Non-Transitive Dependency

There are only two types of dependency: transitive and non-transitive.

Suppose B has an explicitly transitive dependency on A. Every transitive dependency of A will become a transitive dependency of B. Every non-transitive dependency of A is invisible to B. B has access to A and every transitive dependency of A.

Suppose B has an explicitly non-transitive dependency on A. Every transitive dependency of A will not become a transitive dependency of B. Every non-transitive dependency of A is invisible to B. B has access to A and every transitive dependency of A.

We could say, non-transitive dependency prevents the propagation of interface, and transitive dependency allows the propagation of interface.

Transitive VS Non-Transitive Dependency In CMake

In CMake, there are three types of dependencies: PUBLIC, PRIVATE, and INTERFACE. I have described the differences between these three types of dependencies in the previous article “CMake: Public VS Private VS Interface”. In retrospect, declaring a dependency as PUBLIC is equivalent to declaring a transitive dependency, and declaring a dependency as PRIVATE is equivalent to declaring a non-transitive dependency. Declaring a dependency as INTERFACE is equivalent to declaring a transitive dependency, but the dependency is not used by the immediate target. Understanding the differences between these three types of dependencies in this way is much conciser and easier.

Transitive VS Non-Transitive Dependency In Bazel

Bazel has a concept of transitive dependency but it does not seem to have a concept of non-transitive dependency. Therefore, the native Bazel build rules only have a keyword deps to declare dependencies. The deps keyword is equivalent to declaring a transitive dependency and it’s also equivalent to declaring a dependency as PUBLIC in CMake. However, because the native Bazel rules do not have a concept of non-transitive dependency, it is not possible to prevent the propagation of unwanted interface using the native Bazel build rules. As a result, the build can become fragile due to sometimes the declared dependency graph will become an underapproximation of the actual dependencies. A concrete example has been described in the official “Bazel Dependencies Concept”.

Fortunately, Bazel allows the user to define custom build rules. By defining custom build rules, the user can define and implement the concept of both transitive and non-transitive dependencies. Because the dependency interface is well managed, the build can become more reliable.

References

• CMake: Public VS Private VS Interface
• Bazel Dependencies
• Functional Dependency - Wikipedia
• Transitive & Non Transitive Functional Dependency | Functional Dependency & Normalization
• Transitive Closure - Wikipedia