We have a set of many components (software libraries and/or applications) known as a Bill of Materials (BOM). Many of these components depend on other components, forming a dependency graph (no cycles).
These components are under active development, with new versions being released over time. The BOM lists each component at a specific version, with the idea that all components of the BOM will work successfully together when used as dependencies of a derivative work.
For example, suppose we have the following components:
- Guava v21 ← no dependencies
- Math v1 ← depends on Guava v21
- Storage v1 ← depends on Guava v21
- App v1 ← depends on Math v1, Storage v1 (and therefore, transitively, on Guava v21)
Now suppose the developers of Math want to use a new feature of Guava. They update its dependency on Guava to v27, and release a new Math v2.
We want to update our App to use Math v2, to inherit some bug-fixes. Because Guava v27 breaks backwards compatibility with Guava v21, we will encounter what's known as a diamond dependency conflict: If App uses Guava v21 then Math v2 will break, and if it uses Guava v27 then Storage v1 will break. This is a well-known problem in dependency management, with the typical solution being to update Storage to work with Guava v27, so that Math and Storage can once again be used together.
As the number of components intended to work together grows, it is increasingly important to have a source of truth for which versions of which components may be successfully combined—i.e. are tested and known to work together. The purpose of a BOM is to be this source of truth.
Furthermore, given a prospective set of components for our BOM, we need to actually perform the testing. Fortunately, every component has a test suite we can execute against any dependency configuration of our choice. If the test suite passes, we know that particular dependency configuration is compatible with the component at that version.
In our example above, BOM v1 consists of {Guava v21, Math v1, Storage v1, App v1}. We run the test suites for each component against BOM v1, and all pass. BOM v1 is deployed to production, and everyone is happy.
Then, Math v2 is released depending on Guava v27. As naive BOM maintainers, we upgrade those two components, producing BOM v2: {Guava v27, Math v2, Storage v1, App v1}. We then run the following tests:
- Guava v27 ← no dependencies [PASSES]
- Math v2 ← with Guava v27 [PASSES]
- Storage v1 ← with Guava v27 (!) [FAILS]
- App v1 ← with Guava v27, Math v2, Storage v1 [FAILS]
The Guava and Math tests pass, but the Storage test fails because Storage relies on a feature of Guava v21 that was removed from Guava v27. We have successfully detected this "version skew" and can now take steps to remedy it, then produce a BOM v3 with version harmony restored.
Unfortunately, executing the test suites can be slow, which adds up as the number of components in the BOM grows. Ideally, if a component passes tests with a particular dependency configuration, we should remember that for next time.
In our example above, suppose that after BOM v3 {Guava v27, Math v2, Storage v2, App v1}, we release a shiny new App v2, with same dependencies, and bump App to v2 in the BOM, resulting in BOM v4 {Guava v27, Math v2, Storage v2, App v2}.
To validate BOM v4, we run the following tests:
A) Guava v27 ← no dependencies
B) Math v2 ← with Guava v27
C) Storage v2 ← with Guava v27
D) App v2 ← with Guava v27, Math v2, Storage v2
But we already know that tests A, B, and C pass, from our prior testing of BOM v3. The only test that is really new is D.
QUESTION: How can we avoid executing tests A, B, and C in this scenario, while still executing D?
SOLUTION
Add a pre-test: before testing a component, we compute its dependency configuration, hash it, and check whether the hash is in the set of known successful configurations. If so: skip it. Or if not: we run the test, and then if it's successful, add the hash to the success set for next time.
With this approach, we can skip the A, B, and C tests for BOM v4, because their hashes will be the same as they were for BOM v3.
Unfortunately, we notice that computing dependency configurations is also slow, taking ~5 seconds per component. For our little 4-component BOM it's not too bad, but for our enterprise-level BOM with 200 components, we are spending 15+ minutes just calculating which components need testing, any time a single component version is incremented in the BOM!
QUESTION: How can we avoid calculating dependency configurations?
SOLUTION
We concoct a new scheme: instead of caching dependency configurations as hashes, we cache the previously successful configurations themselves. To discern whether a component needs testing, we iterate its previously successful configurations, checking whether any of them are subsets of the BOM being tested.
Extending our previous example, suppose we release a series of new BOMs as follows:
-
BOM v5: Guava v27 → v27.1
-
BOM v6: Guava v27.1 → v27.2
-
BOM v7: Guava v27.2 → v27.3
-
BOM v8: add two new components:
- E) Network v1 ← no dependencies
- F) Server v1 ← Network v1, App v2 (transitive: Guava v27, Math v2, Storage v2)
-
BOM v9: Network v1 → v2
-
BOM v10: Network v2 → v3
BOMs v4 through v9 are all perfectly harmonious with passing tests.
Now it's time to validate BOM v10. We need to run the following tests:
A) Guava v27.3 ← no dependencies
B) Math v2 ← with Guava v27.3
C) Storage v2 ← with Guava v27.3
D) App v2 ← with Guava v27.3, Math v2, Storage v2
E) Network v3 ← no dependencies
F) Server v1 ← with Network v3, App v2, Guava v27.3, Math v2, Storage v2
For test A, we look up previously successful configurations for Guava v27.3. There is only one, the empty set, appended during BOM v7 testing. The empty set is a subset of BOM v10, so we skip test A.
For test B, we look up previously successful configurations for Math v2. There are several:
- {Guava v27} - appended while testing BOM v2
- {Guava v27.1} - appended while testing BOM v5
- {Guava v27.2} - appended while testing BOM v6
- {Guava v27.3} - appended while testing BOM v7
We iterate these configurations. Is {Guava v27} a subset of BOM v10? No. How about {Guava v27.1}? Nope. Neither is {Guava v27.2}. But finally with {Guava v27.3}, we have a match! Test skipped.
Tests C and D will be skipped in a similar manner, while test E will be executed since Network v3 is new and has no previously successful configurations.
For Test F, Server v1's previously successful configurations are:
- {Network v1, App v2, Guava v27.3, Math v2, Storage v2} - appended while testing BOM v8
- {Network v2, App v2, Guava v27.3, Math v2, Storage v2} - appended while testing BOM v9
But neither of these is a subset of BOM v10, because BOM v10 includes Network v3, which is new. So Test F needs to run.
The scheme works, but questions remain:
-
What is the time and space complexity as more BOMs are released?
-
Is there a data structure that could save time and/or space compared to the simple "list of sets" employed above?
-
Do any other optimizations or approaches come to mind?
MY THOUGHTS
Worst case, if 199 components of a 200-component BOM depend on Guava, and Guava is bumped 50 times, each of the 199 components will accumulate 50 previously successful dependency configurations. The 199 components might be maximally dependent (Z depends on A thru Y, Y depends on A thru X, X depends on A thru W, etc.): 198+197+196+...+2+1+0 total dependency edges. Generalizing: a BOM with N releases of C components each will have C success sets, with N elements each, with C*(C+1)/2 ~= C² dependencies across all components per release. So O(NC²) space to store, and O(NC²) time to check versus the BOM set.
This worst case is not likely, though; in practice we don't have maximal dependence across components. We also almost always increase rather than decrease component versions in the BOM, meaning we could potentially store the list of success sets in some ordered data structure (KD tree?). But doing this feels overly complex to me, especially since in practice, this problem is not going to scale into the millions or billions of components nor BOM releases. The real-world scale is hundreds of components, and hundreds-to-eventually-thousands of BOM releases.
A simpler helper data structure would be to record, for each BOM component, which success sets it is part of. Then, instead of iterating thousands of prior success sets and checking if each is a subset, we iterate the hundreds of BOM components, intersecting their relevant success sets, i.e. "whittling down" the success sets we have to check. But I have not deeply analyzed how effective such an approach might actually be.
In practice, I am planning to implement the "list of prior success sets" approach naively, without further optimizations as speculated here. I'm mostly interested in further optimizations academically, since I think my real-world version of the problem won't scale to a point where performance becomes an issue.
