Skip to content

Latest commit

 

History

History
84 lines (51 loc) · 7.58 KB

the-solver.md

File metadata and controls

84 lines (51 loc) · 7.58 KB
Raw
title
The Solver

At the heart of dep is a constraint solving engine - a CDCL-style SMT solver, tailored specifically to the domain of Go package management. It lives in the github.com/golang/dep/gps package, and is where the work of determining a valid, transitively complete dependency graph (aka, the contents of Gopkg.lock) is performed.

This page will eventually detail the solver's mechanics, but in the meantime, there are docs for an older version of the solver that are still accurate enough to provide a rough picture of its behavior.

Solving invariants

The solver guarantees certain invariants in every complete solution it returns. Each invariant is explored in detail later, but they can be summarized as follows:

  • All rules specified in activated [[constraint]] stanzas in both the current project and dependency projects will be satisfied, unless superseded by a [[override]] stanza in the current project.
  • For all import paths pointing into a given project, the version of the project selected will contain "valid" Go packages in the corresponding directory.
  • If an import comment is specified by a package, any import paths addressing that package will be of the form specified in the comment.
  • For any given import path, all instances of that import path will use the exact same casing.

The solver is an iterative algorithm, working its way project-by-project through possible dependency graphs. In order to select a project, it must first prove that, to the best of its current knowledge, all of the above conditions are met. When the solver cannot find a solution, failure is defined in terms of a project's version's inability to meet one of the above criteria.

[[constraint]] rules

As described in the Gopkg.toml docs, each [[constraint]] stanza is associated with a single project, and each stanza can contain both a version rule and a source rule. For any given project P, all dependers on P whose constraint rules are "activated" must express mutually compatible rules. That means:

  • For version rules, all activated constraints on P must intersect, and and there must be at least one published version must exist in the intersecting space. Intersection varies depending on version rule type:
    • For revision and branch, it must be a string-literal match.
    • For version, if the string is not a valid semantic version, then it must be a string-literal match.
    • For version that are valid semantic version ranges, intersection is standard set-theoretic intersection of the possible values in each range range. Semantic versions without ranges are treated as a single element set (e.g., version = "=v1.0.0") for intersection purposes.
  • For source rules, all projects with a particular dependency must either express a string-equal source value, or have no source value at all. This allows one dependency to specify an alternate source, and other dependencies to play along if they have no opinion. (NB: this play-along behavior may be removed in a future version.)

If the current project's Gopkg.toml has an [[override]] on P, then all [[constraint]] declarations (including any in the current project) are ignored, obviating the possibility of conflict.

Activated constraints

Just because a [[constraint]] on P appears in D's Gopkg.toml doesn't necessarily mean the constraint on P is considered active. A package in P must be imported by a package in D - and, if D is not the current project, then one of its packages importing P must also be imported.

Given the following dependency graph, where C is the current project:

C -> D
C -> P
D/subpkg -> P

Even though C imports D, because D/subpkg is not reachable through C's imports, any [[constraint]] declared in D's Gopkg.toml' on P will not be active.

The reasoning behind this behavior is explained further in this gist.

Package validity

dep does only superficial validation of code in packages, but it does do some. For a package to be considered valid, three things must be true:

  • The package must not contain any local imports. Note: this disallows something the standard toolchain compiler does allow, which is normally means dep must support it. However, local imports are already strongly discouraged in the toolchain, and skipping them allows dep to avoid dot-dot hell.

If any of the above are untrue, the code in a package is considered malformed, and cannot be used in a solution.

It is not immediately disqualifying for a project to merely contain some invalid packages; they must be imported for the invariant to be broken. So, if P/invalid is a subpackage with invalid code in it, then it is still acceptable if C -> P. However, internal imports within P are also considered, so this import chain:

C -> P
P -> invalid

will result in an error, as C imports a package that will necessarily result in the import of an invalid package.

Import comments

Go 1.4 introduced import comments, which allow a package to specify the import path that must be used when addressing it. For example, import "github.com/golang/net/dict" would point to a valid package, but because it uses an import comment to enforce that it must be imported as golang.org/x/net/dict, dep would reject any project attempting to import it directly through its github address.

Because most projects are consistent about their import comment use over time, this issue typically only occurs when adding a new dependency or attempting to revive an older project.

Note: dep does not currently enforce this rule, but it needs to.

Remediation: change the code by fixing the offending import paths. If the offending import paths are not in the current project and you don't directly control the dependency, you'll have to fork and fix it yourself, then use source to point to your fork.

Import path casing

The standard Go toolchain compiler does not allow import paths that vary only in case to exist in the same build. For example, either of github.com/sirupsen/logrus or github.com/Sirupsen/logrus are fine (GitHub treats usernames as case-insensitive) individually, but they cannot exist in the same project.

The solver keeps track of the accepted case variant for each import path it's processed. Any subsequent projects it sees that introduces a case-only variation for a known import path will be rejected.

Remediation: Pick a casing variation (all lowercase is usually the right answer), and enforce it universally across the depgraph. As it has to be respected in all dependencies, as well, this may necessitate pull requests and possibly forking of dependencies, if you don't control them directly.