vsolver

README

vsolver

vsolver is a specialized SAT solver, designed as an engine for Go package management. The initial plan is integration into glide, but vsolver could be used by any tool interested in fully solving the package management problem.

NOTE - vsolver isn’t ready yet, but it’s getting close.

The implementation is derived from the solver used in Dart's pub package management tool.

Assumptions

Package management is far too complex to be assumption-less. vsolver tries to keep its assumptions to the minimum, supporting as many situations as is possible while still maintaining a predictable, well-formed system.

• Go 1.6, or 1.5 with GO15VENDOREXPERIMENT = 1 set. vendor directories are a requirement.
• You don't manually change what's under vendor/. That’s tooling’s job.
• A project concept, where projects comprise the set of Go packages in a rooted tree on the filesystem. By happy (not) accident, that rooted tree is exactly the same set of packages covered by a vendor/ directory.
• A manifest-and-lock approach to tracking project manifest data. The solver takes manifest (and, optionally, lock)-type data as inputs, and produces lock-type data as its output. Tools decide how to actually store this data, but these should generally be at the root of the project tree.

Manifests? Locks? Eeew. Yes, we also think it'd be swell if we didn't need metadata files. We love the idea of Go packages as standalone, self-describing code. Unfortunately, the wheels come off that idea as soon as versioning and cross-project/repository dependencies happen. Universe alignment is hard; trying to intermix version information directly with the code would only make matters worse.

Arguments

Some folks are against using a solver in Go. Even the concept is repellent. These are some of the arguments that are raised:

"It seems complicated, and idiomatic Go things are simple!"

Complaining about this is shooting the messenger.

Selecting acceptable versions out of a big dependency graph is a boolean satisfiability (or SAT) problem: given all possible combinations of valid dependencies, we’re trying to find a set that satisfies all the mutual requirements. Obviously that requires version numbers lining up, but it can also (and vsolver will/does) enforce invariants like “no import cycles” and type compatibility between packages. All of those requirements must be rechecked every time we discovery and add a new project to the graph.

SAT was one of the very first problems to be proven NP-complete. OF COURSE IT’S COMPLICATED. We didn’t make it that way. Truth is, though, solvers are an ideal way of tackling this kind of problem: it lets us walk the line between pretending like versions don’t exist (a la go get) and pretending like only one version of a dep could ever work, ever (most of the current community tools).

"(Tool X) uses a solver and I don't like that tool’s UX!"

Sure, there are plenty of abstruse package managers relying on SAT solvers out there. But that doesn’t mean they ALL have to be confusing. vsolver’s algorithms are artisinally handcrafted with ❤️ for Go’s use case, and we are committed to making Go dependency management a grokkable process.

Features

Yes, most people will probably find most of this list incomprehensible right now. We'll improve/add explanatory links as we go!

• Passing bestiary of tests brought over from dart
• Dependency constraints based on SemVer, branches, and revisions. AKA, "all the ways you might depend on Go code now, but coherently organized."
• Define different network addresses for a given import path
• Global project aliasing. This is a bit different than the previous.
• Bi-modal analysis (project-level and package-level)
• Specific sub-package dependencies
• Enforcing an acyclic project graph (mirroring the Go compiler's enforcement of an acyclic package import graph)
• On-the-fly static analysis (e.g. for incompatibility assessment, type escaping)
• Optional package duplication as a conflict resolution mechanism
• Faaaast, enabled by aggressive caching of project metadata
• Lock information parameterized by build tags (including, but not limited to, GOOS/GOARCH)
• Non-repository root and nested manifest/lock pairs

Note that these goals are not fixed - we may drop some as we continue working. Some are also probably out of scope for the solver itself, but still related to the solver's operation.

Documentation

Index

• func CreateVendorTree(basedir string, l Lock, sm SourceManager, sv bool) error
• func IsAny(c Constraint) bool
• type Constraint
  • func Any() Constraint
  • func NewSemverConstraint(body string) (Constraint, error)
• type LocalImportsError
  • func (e *LocalImportsError) Error() string
• type Lock
• type LockedProject
  • func NewLockedProject(n ProjectName, v Version, uri, path string, pkgs []string) LockedProject
  • func (lp LockedProject) Ident() ProjectIdentifier
  • func (lp LockedProject) Path() string
  • func (lp LockedProject) Version() Version
• type Manifest
• type Package
• type PackageOrErr
• type PackageTree
  • func (t PackageTree) ExternalReach(main, tests bool, ignore map[string]bool) map[string][]string
  • func (t PackageTree) ListExternalImports(main, tests bool, ignore map[string]bool) ([]string, error)
• type PairedVersion
• type ProjectAnalyzer
• type ProjectDep
• type ProjectIdentifier
• type ProjectName
• type Revision
  • func (r Revision) Intersect(c Constraint) Constraint
  • func (r Revision) Matches(v Version) bool
  • func (r Revision) MatchesAny(c Constraint) bool
  • func (r Revision) String() string
  • func (r Revision) Type() string
• type SimpleLock
  • func (SimpleLock) InputHash() []byte
  • func (l SimpleLock) Projects() []LockedProject
• type SimpleManifest
  • func (m SimpleManifest) DependencyConstraints() []ProjectDep
  • func (m SimpleManifest) Name() ProjectName
  • func (m SimpleManifest) TestDependencyConstraints() []ProjectDep
• type Solution
• type SolveArgs
• type SolveOpts
• type Solver
  • func Prepare(args SolveArgs, opts SolveOpts, sm SourceManager) (Solver, error)
• type SourceManager
  • func NewSourceManager(an ProjectAnalyzer, cachedir, basedir string, force bool) (SourceManager, error)
• type UnpairedVersion
  • func NewBranch(body string) UnpairedVersion
  • func NewVersion(body string) UnpairedVersion
• type Version

Functions

func CreateVendorTree

func CreateVendorTree(basedir string, l Lock, sm SourceManager, sv bool) error

CreateVendorTree takes a basedir and a Lock, and exports all the projects listed in the lock to the appropriate target location within the basedir.

It requires a SourceManager to do the work, and takes a flag indicating whether or not to strip vendor directories contained in the exported dependencies.

func IsAny

func IsAny(c Constraint) bool

IsAny indicates if the provided constraint is the wildcard "Any" constraint.

Types

type Constraint

type Constraint interface {
	fmt.Stringer
	// Matches indicates if the provided Version is allowed by the Constraint.
	Matches(Version) bool
	// MatchesAny indicates if the intersection of the Constraint with the
	// provided Constraint would yield a Constraint that could allow *any*
	// Version.
	MatchesAny(Constraint) bool
	// Intersect computes the intersection of the Constraint with the provided
	// Constraint.
	Intersect(Constraint) Constraint
	// contains filtered or unexported methods
}

A Constraint provides structured limitations on the versions that are admissible for a given project.

As with Version, it has a private method because the vsolver's internal implementation of the problem is complete, and the system relies on type magic to operate.

func Any

func Any() Constraint

Any returns a constraint that will match anything.

func NewSemverConstraint

func NewSemverConstraint(body string) (Constraint, error)

NewSemverConstraint attempts to construct a semver Constraint object from the input string.

If the input string cannot be made into a valid semver Constraint, an error is returned.

type LocalImportsError

type LocalImportsError struct {
	Dir          string
	LocalImports []string
}

LocalImportsError indicates that a package contains at least one relative import that will prevent it from compiling.

TODO add a Files property once we're doing our own per-file parsing

func (*LocalImportsError) Error

func (e *LocalImportsError) Error() string

type Lock

type Lock interface {

	// The hash of inputs to vsolver that resulted in this lock data
	InputHash() []byte

	// Projects returns the list of LockedProjects contained in the lock data.
	Projects() []LockedProject
}

Lock represents data from a lock file (or however the implementing tool chooses to store it) at a particular version that is relevant to the satisfiability solving process.

In general, the information produced by vsolver on finding a successful solution is all that would be necessary to constitute a lock file, though tools can include whatever other information they want in their storage.

type LockedProject

type LockedProject struct {
	// contains filtered or unexported fields
}

LockedProject is a single project entry from a lock file. It expresses the project's name, one or both of version and underlying revision, the network URI for accessing it, the path at which it should be placed within a vendor directory, and the packages that are used in it.

func NewLockedProject

func NewLockedProject(n ProjectName, v Version, uri, path string, pkgs []string) LockedProject

NewLockedProject creates a new LockedProject struct with a given name, version, upstream repository URI, and on-disk path at which the project is to be checked out under a vendor directory.

Note that passing a nil version will cause a panic. This is a correctness measure to ensure that the solver is never exposed to a version-less lock entry. Such a case would be meaningless - the solver would have no choice but to simply dismiss that project. By creating a hard failure case via panic instead, we are trying to avoid inflicting the resulting pain on the user by instead forcing a decision on the Analyzer implementation.

func (LockedProject) Ident

func (lp LockedProject) Ident() ProjectIdentifier

Ident returns the identifier describing the project. This includes both the local name (the root name by which the project is referenced in import paths) and the network name, where the upstream source lives.

func (LockedProject) Path

func (lp LockedProject) Path() string

Path returns the path relative to the vendor directory to which the locked project should be checked out.

func (LockedProject) Version

func (lp LockedProject) Version() Version

Version assembles together whatever version and/or revision data is available into a single Version.

type Manifest

type Manifest interface {
	Name() ProjectName
	DependencyConstraints() []ProjectDep
	TestDependencyConstraints() []ProjectDep
}

Manifest represents the data from a manifest file (or however the implementing tool chooses to store it) at a particular version that is relevant to the satisfiability solving process. That means constraints on dependencies, both for normal dependencies and for tests.

Finding a solution that satisfies the constraints expressed by all of these dependencies (and those from all other projects, transitively), is what the solver does.

Note that vsolver does perform static analysis on all projects' codebases; if dependencies it finds through that analysis are missing from what the Manifest lists, it is considered an error that will eliminate that version from consideration in the solving algorithm.

type Package

type Package struct {
	ImportPath, CommentPath string
	Name                    string
	Imports                 []string
	TestImports             []string
}

Package represents a Go package. It contains a subset of the information go/build.Package does.

type PackageOrErr

type PackageOrErr struct {
	P   Package
	Err error
}

PackageOrErr stores the results of attempting to parse a single directory for Go source code.

type PackageTree

type PackageTree struct {
	ImportRoot string
	Packages   map[string]PackageOrErr
}

A PackageTree represents the results of recursively parsing a tree of packages, starting at the ImportRoot. The results of parsing the files in the directory identified by each import path - a Package or an error - are stored in the Packages map, keyed by that import path.

func (PackageTree) ExternalReach

func (t PackageTree) ExternalReach(main, tests bool, ignore map[string]bool) map[string][]string

ExternalReach looks through a PackageTree and computes the list of external packages (not logical children of PackageTree.ImportRoot) that are transitively imported by the internal packages in the tree.

main indicates whether (true) or not (false) to include main packages in the analysis. main packages should generally be excluded when analyzing the non-root dependency, as they inherently can't be imported.

tests indicates whether (true) or not (false) to include imports from test files in packages when computing the reach map.

ignore is a map of import paths that, if encountered, should be excluded from analysis. This exclusion applies to both internal and external packages. If an external import path is ignored, it is simply omitted from the results.

If an internal path is ignored, then it is excluded from all transitive dependency chains and does not appear as a key in the final map. That is, if you ignore A/foo, then the external package list for all internal packages that import A/foo will not include external packages were only reachable through A/foo.

Visually, this means that, given a PackageTree with root A and packages at A, A/foo, and A/bar, and the following import chain:

A -> A/foo -> A/bar -> B/baz

If you ignore A/foo, then the returned map would be:

 map[string][]string{
	"A": []string{},
	"A/bar": []string{"B/baz"},
 }

It is safe to pass a nil map if there are no packages to ignore.

func (PackageTree) ListExternalImports

func (t PackageTree) ListExternalImports(main, tests bool, ignore map[string]bool) ([]string, error)

ListExternalImports computes a sorted, deduplicated list of all the external packages that are reachable through imports from all valid packages in the PackageTree.

main and tests determine whether main packages and test imports should be included in the calculation.

"External" is defined as anything not prefixed, after path cleaning, by the PackageTree.ImportRoot. This includes stdlib.

If an internal path is ignored, all of the external packages that it uniquely imports are omitted. Note, however, that no internal transitivity checks are made here - every non-ignored package in the tree is considered independently. That means, given a PackageTree with root A and packages at A, A/foo, and A/bar, and the following import chain:

A -> A/foo -> A/bar -> B/baz

If you ignore A or A/foo, A/bar will still be visited, and B/baz will be returned, because this method visits ALL packages in the tree, not only those reachable from the root (or any other) packages. If your use case requires interrogating external imports with respect to only specific package entry points, you need ExternalReach() instead.

It is safe to pass a nil map if there are no packages to ignore.

If an internal package has an error (that is, PackageOrErr is Err), it is excluded from consideration. Internal packages that transitively import the error package are also excluded. So, if:

  -> B/foo
 /
A
 \
  -> A/bar -> B/baz

And A/bar has some error in it, then both A and A/bar will be eliminated from consideration; neither B/foo nor B/baz will be in the results. If A/bar, with its errors, is ignored, however, then A will remain, and B/foo will be in the results.

type PairedVersion

type PairedVersion interface {
	Version
	// Underlying returns the immutable Revision that identifies this Version.
	Underlying() Revision
	// contains filtered or unexported methods
}

PairedVersion represents a normal Version, but paired with its corresponding, underlying Revision.

type ProjectAnalyzer

type ProjectAnalyzer interface {
	GetInfo(build.Context, ProjectName) (Manifest, Lock, error)
}

A ProjectAnalyzer is responsible for analyzing a path for Manifest and Lock information. Tools relying on vsolver must implement one.

type ProjectDep

type ProjectDep struct {
	Ident      ProjectIdentifier
	Constraint Constraint
}

type ProjectIdentifier

type ProjectIdentifier struct {
	LocalName   ProjectName
	NetworkName string
}

type ProjectName

type ProjectName string

type Revision

type Revision string

A Revision represents an immutable versioning identifier.

func (Revision) Intersect

func (r Revision) Intersect(c Constraint) Constraint

func (Revision) Matches

func (r Revision) Matches(v Version) bool

Matches is the Revision acting as a constraint; it checks to see if the provided version is the same Revision as itself.

func (Revision) MatchesAny

func (r Revision) MatchesAny(c Constraint) bool

MatchesAny is the Revision acting as a constraint; it checks to see if the provided version is the same Revision as itself.

func (Revision) String

func (r Revision) String() string

String converts the Revision back into a string.

func (Revision) Type

func (r Revision) Type() string

type SimpleLock

type SimpleLock []LockedProject

SimpleLock is a helper for tools to easily describe lock data when they know that no hash, or other complex information, is available.

func (SimpleLock) InputHash

func (SimpleLock) InputHash() []byte

InputHash always returns an empty string for SimpleLock. This makes it useless as a stable lock to be written to disk, but still useful for some ephemeral purposes.

func (SimpleLock) Projects

func (l SimpleLock) Projects() []LockedProject

Projects returns the entire contents of the SimpleLock.

type SimpleManifest

type SimpleManifest struct {
	N        ProjectName
	Deps     []ProjectDep
	TestDeps []ProjectDep
}

SimpleManifest is a helper for tools to enumerate manifest data. It's generally intended for ephemeral manifests, such as those Analyzers create on the fly for projects with no manifest metadata, or metadata through a foreign tool's idioms.

func (SimpleManifest) DependencyConstraints

func (m SimpleManifest) DependencyConstraints() []ProjectDep

GetDependencies returns the project's dependencies.

func (SimpleManifest) Name

func (m SimpleManifest) Name() ProjectName

Name returns the name of the project described by the manifest.

func (SimpleManifest) TestDependencyConstraints

func (m SimpleManifest) TestDependencyConstraints() []ProjectDep

GetDependencies returns the project's test dependencies.

type Solution

type Solution interface {
	Lock
	Attempts() int
}

A Solution is returned by a solver run. It is mostly just a Lock, with some additional methods that report information about the solve run.

type SolveArgs

type SolveArgs struct {
	// The path to the root of the project on which the solver is working.
	Root string

	// The 'name' of the project. Required. This should (must?) correspond to subpath of
	// Root that exists under a GOPATH.
	Name ProjectName

	// The root manifest. Required. This contains all the dependencies, constraints, and
	// other controls available to the root project.
	Manifest Manifest

	// The root lock. Optional. Generally, this lock is the output of a previous solve run.
	//
	// If provided, the solver will attempt to preserve the versions specified
	// in the lock, unless ToChange or ChangeAll settings indicate otherwise.
	Lock Lock

	// A list of packages (import paths) to ignore. These can be in the root
	// project, or from elsewhere. Ignoring a package means that both it and its
	// imports will be disregarded by all relevant solver operations.
	Ignore []string
}

SolveArgs comprise the required inputs for a Solve run.

type SolveOpts

type SolveOpts struct {
	// Downgrade indicates whether the solver will attempt to upgrade (false) or
	// downgrade (true) projects that are not locked, or are marked for change.
	//
	// Upgrading is, by far, the most typical case. The field is named
	// 'Downgrade' so that the bool's zero value corresponds to that most
	// typical case.
	Downgrade bool

	// ChangeAll indicates that all projects should be changed - that is, any
	// versions specified in the root lock file should be ignored.
	ChangeAll bool

	// ToChange is a list of project names that should be changed - that is, any
	// versions specified for those projects in the root lock file should be
	// ignored.
	//
	// Passing ChangeAll has subtly different behavior from enumerating all
	// projects into ToChange. In general, ToChange should *only* be used if the
	// user expressly requested an upgrade for a specific project.
	ToChange []ProjectName

	// Trace controls whether the solver will generate informative trace output
	// as it moves through the solving process.
	Trace bool

	// TraceLogger is the logger to use for generating trace output. If Trace is
	// true but no logger is provided, solving will result in an error.
	TraceLogger *log.Logger
}

SolveOpts holds additional options that govern solving behavior.

type Solver

type Solver interface {
	HashInputs() ([]byte, error)
	Solve() (Solution, error)
}

A Solver is the main workhorse of vsolver: given a set of project inputs, it performs a constraint solving analysis to develop a complete Result that can be used as a lock file, and to populate a vendor directory.

func Prepare

func Prepare(args SolveArgs, opts SolveOpts, sm SourceManager) (Solver, error)

Prepare readies a Solver for use.

This function reads and validates the provided SolveArgs and SolveOpts. If a problem with the inputs is detected, an error is returned. Otherwise, a Solver is returned, ready to hash and check inputs or perform a solving run.

type SourceManager

type SourceManager interface {
	// RepoExists checks if a repository exists, either upstream or in the
	// SourceManager's central repository cache.
	RepoExists(ProjectName) (bool, error)

	// VendorCodeExists checks if a code tree exists within the stored vendor
	// directory for the the provided import path name.
	VendorCodeExists(ProjectName) (bool, error)

	// ListVersions retrieves a list of the available versions for a given
	// repository name.
	ListVersions(ProjectName) ([]Version, error)

	// RevisionPresentIn indicates whether the provided Version is present in the given
	// repository. A nil response indicates the version is valid.
	RevisionPresentIn(ProjectName, Revision) (bool, error)

	// ListPackages retrieves a tree of the Go packages at or below the provided
	// import path, at the provided version.
	ListPackages(ProjectName, Version) (PackageTree, error)

	// GetProjectInfo returns manifest and lock information for the provided
	// import path. vsolver currently requires that projects be rooted at their
	// repository root, which means that this ProjectName must also be a
	// repository root.
	GetProjectInfo(ProjectName, Version) (Manifest, Lock, error)

	// ExportProject writes out the tree of the provided import path, at the
	// provided version, to the provided directory.
	ExportProject(ProjectName, Version, string) error

	// Release lets go of any locks held by the SourceManager.
	Release()
}

A SourceManager is responsible for retrieving, managing, and interrogating source repositories. Its primary purpose is to serve the needs of a Solver, but it is handy for other purposes, as well.

vsolver's built-in SourceManager, accessible via NewSourceManager(), is intended to be generic and sufficient for any purpose. It provides some additional semantics around the methods defined here.

func NewSourceManager

func NewSourceManager(an ProjectAnalyzer, cachedir, basedir string, force bool) (SourceManager, error)

NewSourceManager produces an instance of vsolver's built-in SourceManager. It takes a cache directory (where local instances of upstream repositories are stored), a base directory for the project currently being worked on, and a force flag indicating whether to overwrite the global cache lock file (if present).

The returned SourceManager aggressively caches information wherever possible. It is recommended that, if tools need to do preliminary, work involving upstream repository analysis prior to invoking a solve run, that they create this SourceManager as early as possible and use it to their ends. That way, the solver can benefit from any caches that may have already been warmed.

vsolver's SourceManager is intended to be threadsafe (if it's not, please file a bug!). It should certainly be safe to reuse from one solving run to the next; however, the fact that it takes a basedir as an argument makes it much less useful for simultaneous use by separate solvers operating on different root projects. This architecture may change in the future.

type UnpairedVersion

type UnpairedVersion interface {
	Version
	// Is takes the underlying Revision that this UnpairedVersion corresponds
	// to and unites them into a PairedVersion.
	Is(Revision) PairedVersion
	// contains filtered or unexported methods
}

UnpairedVersion represents a normal Version, with a method for creating a VersionPair by indicating the version's corresponding, underlying Revision.

func NewBranch

func NewBranch(body string) UnpairedVersion

NewBranch creates a new Version to represent a floating version (in general, a branch).

func NewVersion

func NewVersion(body string) UnpairedVersion

NewVersion creates a Semver-typed Version if the provided version string is valid semver, and a plain/non-semver version if not.

type Version

type Version interface {
	Constraint
	// Indicates the type of version - Revision, Branch, Version, or Semver
	Type() string
}

Version represents one of the different types of versions used by vsolver.

Version composes Constraint, because all versions can be used as a constraint (where they allow one, and only one, version - themselves), but constraints are not necessarily discrete versions.

Version is an interface, but it contains private methods, which restricts it to vsolver's own internal implementations. We do this for the confluence of two reasons: the implementation of Versions is complete (there is no case in which we'd need other types), and the implementation relies on type magic under the hood, which would be unsafe to do if other dynamic types could be hiding behind the interface.