Understanding the Resolver
The resolver can be thought of as the "brain" of Buckaroo. It is the component that figures out which versions of packages will satisfy the user's dependencies. This article should give you a high-level understanding of how the resolver works.
Buckaroo makes two design decisions that impact the resolution algorithm in an unique way:
- Git is used as a package registry (see Git as a Package Registry)
- The manifest of each package is part of source control
The details of fetching packages and package versions is handled by another component: the "Source Explorer". The Source Explorer is given to the resolver with the following (high-level) interface:
- Fetch versions for a given package
- Fetch the manifest for a given package and version
Note that this interface implies that fetching transitive dependencies will take multiple steps.
In theory, resolving the dependency graph is equivalent to solving a satisfiability problem:
- Every package identifier is a variable
- Every version is a possible value for each variable
- The version constraints form an equation to satisfy
In practice however, the resolver needs to work with partial information. In order to reveal the complete search space (using the Source Explorer), we would need to download all versions of all packages that are in the transitive closure of dependencies, which would take several days for common use-cases! Revealing the complete search space is impractical.
This means that the resolver must select candidates (package versions) without knowing all of the constraints. We can make our best guess, but the resolver will occasionally make wrong decisions and need to backtrack. In the backtracking process, we have the opportunity to prune the search space using any information about the conflict we have discovered.
Let's look at a few different scenarios in the resolution process:
Suppose the user has a manifest with dependencies on A@1.x and B@2.x:
The resolver then picks a constraint to explore. We have no information to help us prioritize, so we can explore A@1.x or B@2.x first. In this case, we pick A@1.x.
We find a version A@1.0, and add it to the selection:
It turns out that A@1.0 also depends on B@2.0. We intersect these constraints as follows:
B@2.x ∩ B@2.0 ⇔ B@2.0
So now we have one dependency left to select: B@2.0.
Fortunately, this version exists and has no further dependencies:
The resolution process is now complete.
In this example, the resolver will select a version that results in a failure. When this happens, we need to backtrack and try a different path.
We find A@1.1, and add this to the selection:
But now we have a problem! The merged constraint on B will have no versions:
B@2.x ∩ B@3.0 ⇔ Ø
To solve this, we need to backtrack. A@1.1 is deselected and we try A@1.0 instead:
A@1.0 depends on B@2.0, so now our constraint on B is:
B@2.x ∩ B@2.0 ⇔ B@2.0
B@2.0 has no further dependencies, so we are done!
