Dependency Resolution

One of the core tasks of git ws is to allow describing dependencies of a particular project to other (possibly related) projects (which are all maintained as git repositories) and assemble them in a single workspace. But, how exactly does this dependency resolution procedure work? This chapter describes the core mechanisms that git ws employs to get its job done.

The Manifest

When working with git ws, one of the core ingredients used is the manifest. Besides some informational meta information, one of the tasks of a manifest is to specify dependencies to other projects. Consider a project HelloWorld, which in turn depends on a library FooLib it needs to work. The manifest of the HelloWorld project could look like that:

[[dependencies]]
name = "FooLib"
revision = "v2.3.4"

In this case, the assumption is that the projects HelloWorld and FooLib are stored both side-by-side on the same server. In addition, HelloWorld pulls in a specific version - v2.3.4 of the library. Dependency resolution in this case is pretty much straightforward: git ws starts with the main project and reads its manifest. That manifest points to FooLib, so the dependency tree would look like this:

HelloWorld
└── FooLib (revision='v2.3.4')

And the resulting (very simplified) workspace created for that project would look like this:

HelloWorld
├── FooLib
│   └── git-ws.toml
└── HelloWorld
    └── git-ws.toml

So far, so good. However, most projects are not as simple as that.

Transitive Dependencies

In the very simple example given above, we assumed that the dependencies of the main project in turn are simple and self-contained. However, more often than not this is not the case. So, what if the FooLib needed by HelloWorld needs yet another library - BarLib - to work? git ws has us covered here by allowing dependencies to be transitive: If a project pulled in as a dependency also has a valid manifest and - in it - specifies further dependencies, these dependencies are pulled in as well and are made a part of the resulting workspace! Assume that a newer version of FooLib has the following manifest:

[[dependencies]]
name = "BarLib"
revision = "v42.0"

The resulting dependency tree now would rather look like this:

HelloWorld
└── FooLib (revision='v2.4.0')
    └── BarLib (revision='v42.0')

And the (simplified) workspace would look like this:

HelloWorld
├── BarLib
│   └── README.md
├── FooLib
│   └── git-ws.toml
└── HelloWorld
    └── git-ws.toml

The First Wins Rule

In an ideal world, a main project and all of its dependencies - direct as well as transitive ones - would form a tree structure. However, often it is not as simple as that. Consider the following:

We need to extend HelloWorld again, adding a dependency to yet another library BazLib:

[[dependencies]]
name = "FooLib"
revision = "v2.4.0"

[[dependencies]]
name = "BazLib"
revision = "v5.6.7"

That library also specifies BarLib as a dependency, but at another revision:

[[dependencies]]
name = "BarLib"
revision = "v44.0"

So, what will happen in this scenario? Let’s check the dependency tree:

HelloWorld
├── FooLib (revision='v2.4.0')
│   └── BarLib (revision='v42.0')
└── BazLib (revision='v5.6.7')
    └── BarLib (revision='v44.0')*

The tree looks somehow as expected, however, note that the second occurrence of BarLib is annotated with a *. This means that it is not used! We can easily prove this showing the checked out revisions of all projects in the workspace:

git ws git describe -- --all
# ===== ../HelloWorld (MAIN 'HelloWorld', revision='main') =====
# heads/main
# ===== ../FooLib ('FooLib', revision='v2.4.0') =====
# tags/v2.4.0
# ===== ../BazLib ('BazLib', revision='v5.6.7') =====
# tags/v5.6.7
# ===== . ('BarLib', revision='v42.0') =====
# tags/v42.0

This is because of the First Wins rule git ws uses for resolving (conflicting) dependencies: If there are two dependencies specified to be mounted to the same path but referring to different revisions, the tool will pick whichever revision has been specified first. Manifests are evaluated via a breadth first search over the tree structure, where the dependencies of one manifest are evaluated in order as seen in the manifest. In the example, this means:

  • Evaluation starts at the HelloWorld project.

    • First, we find FooLib at v2.4.0 and add it to the workspace. As this project has a manifest on its own, we start evaluating it.

    • Next at this level, we find BazLib at v5.6.7, which we also add.

    • This concludes this manifest, so we continue checking the dependencies of our first level dependencies:

      • The first (and only) dependency we find for FooLib is BarLib at revision v42.0, so we add it to the workspace.

      • Next, we check BarLib again, this time at v44.0, but as it already has been added to the workspace, we skip it.

This leads us to an interesting pattern that can be used in git ws.

Dependency Overriding

If you closely check the example again, you might notice something: HelloWorld pulls in both FooLib and BazLib. Both of them require BarLib to work, but at different revisions. By the order of dependencies in the main project, we see v42.0 of BarLib first, but BazLib explicitly needs it at v44.0. Usually, libraries (or programs) tend to be forward compatible, i.e. using FooLib with a newer version of BarLib would work. But in the workspace that will be constructed, we end up with a version of BazLib that will need to build and run against an older version of BarLib than expected. This - in turn - might fail quite quickly on us.

However, with the First Win Rules at hand, we can easily fix such a workspace by explicitly pulling in a dependency directly in the manifest of the main project:

[[dependencies]]
name = "FooLib"
revision = "v2.4.0"

[[dependencies]]
name = "BazLib"
revision = "v5.6.7"

[[dependencies]]
name = "BarLib"
revision = "v44.0"

By putting the dependency towards BarLib directly into the manifest of the main project, we can pin its version to whatever is needed - in our case, we can explicitly set it to v44.0, which should work for both FooLib and BarLib.

An extreme form of this approach is when using manifest freezing: Creating a frozen manifest basically creates a manifest with all pulled in dependencies resolved in one flat list with their revision set to a fixed version. This will cause git ws to ignore any of the dependencies coming in transitively to be ignored (as they already are specified in the manifest of the main project).