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 is super-extra-much not functional yet :)

The current implementation is based heavily on the solver used in Dart's pub package management tool. Significant changes are planned to suit Go's particular constraints; in pursuit of those, we also may refactor to adapt from a more fully general SAT-solving approach.

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. While the solver mostly doesn't touch vendor directories themselves, it's basically insane to try to solve this problem without them.
• A manifest-and-lock approach to tracking project manifest data. The solver takes manifest (and, optionally, lock)-type information as inputs, and produces lock-type information as its output. (An implementing tool gets to decide whether these are represented as one or two files).
• A project concept, where projects comprise the set of Go packages in a rooted tree on the filesystem. (Generally, the root should be where the manifest/lock are, but that's up to the tool.) Happily, that’s the same set of packages that a vendor/ directory covers.
• You don't manually change what's under vendor/ - leave it up to the vsolver-driven tool.

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, though, that idea goes off the rails as soon as versioning and cross-project/repository dependencies happen, because universe alignment is hard.

Some folks are against using a solver in Go - even just the concept. Their reasons for it often include things like "(Tool X) uses a solver and I don't like that tool’s UX!" or "It seems complicated, and idiomatic Go things are simple!" But that’s just shooting the messenger. Dependency resolution is a well-understood, NP-complete problem. It’s that problem that’s the enemy, not solvers. And especially not this one! It’s a friendly solver - one that aims for transparency in the choices it makes, and the resolution failures it encounters.

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."
• 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

• Constants
• func ExternalReach(basedir, projname string) (rm map[string][]string, err error)
• func IterativeScan(path string) ([]string, error)
• type Constraint
  • func NewConstraint(t ConstraintType, body string) (Constraint, error)
• type ConstraintType
• type Dependency
• type Lock
• type Manifest
• type PairedVersion
• type ProjectAnalyzer
• type ProjectAtom
• type ProjectDep
• type ProjectExistence
• type ProjectInfo
• type ProjectManager
• type ProjectName
• type Result
  • func (r Result) CreateVendorTree(basedir string, sm SourceManager) error
• 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
• type SolveError
• type Solver
  • func NewSolver(sm SourceManager, l *logrus.Logger) Solver
• type SourceManager
  • func NewSourceManager(cachedir, basedir string, upgrade, force bool, an ProjectAnalyzer) (SourceManager, error)
• type UnpairedVersion
  • func NewFloatingVersion(body string) UnpairedVersion
  • func NewVersion(body string) UnpairedVersion
• type Version

Constants

const (
	// ExistsInLock indicates that a project exists (i.e., is mentioned in) a
	// lock file.
	// TODO not sure if it makes sense to have this IF it's just the source
	// manager's responsibility for putting this together - the implication is
	// that this is the root lock file, right?
	ExistsInLock = 1 << iota

	// ExistsInManifest indicates that a project exists (i.e., is mentioned in)
	// a manifest.
	ExistsInManifest

	// ExistsInVendorRoot indicates that a project exists in a vendor directory
	// at the predictable location based on import path. It does NOT imply, much
	// less guarantee, any of the following:
	//   - That the code at the expected location under vendor is at the version
	//   given in a lock file
	//   - That the code at the expected location under vendor is from the
	//   expected upstream project at all
	//   - That, if this flag is not present, the project does not exist at some
	//   unexpected/nested location under vendor
	//   - That the full repository history is available. In fact, the
	//   assumption should be that if only this flag is on, the full repository
	//   history is likely not available (locally)
	//
	// In short, the information encoded in this flag should not be construed as
	// exhaustive.
	ExistsInVendorRoot

	// ExistsInCache indicates that a project exists on-disk in the local cache.
	// It does not guarantee that an upstream exists, thus it cannot imply
	// that the cache is at all correct - up-to-date, or even of the expected
	// upstream project repository.
	//
	// Additionally, this refers only to the existence of the local repository
	// itself; it says nothing about the existence or completeness of the
	// separate metadata cache.
	ExistsInCache

	// ExistsUpstream indicates that a project repository was locatable at the
	// path provided by a project's URI (a base import path).
	ExistsUpstream
)

Functions

func ExternalReach

func ExternalReach(basedir, projname string) (rm map[string][]string, err error)

ExternalReach takes a base directory (a project root), and computes the list of external dependencies (not under the tree at that project root) that are imported by packages in that project tree.

projname indicates the import path-level name that constitutes the root of the project tree (used to decide whether an encountered import path is "internal" or "external").

func IterativeScan

func IterativeScan(path string) ([]string, error)

IterativeScan attempts to obtain a list of imported dependencies from a package. This scanning is different from ImportDir as part of the go/build package. It looks over different permutations of the supported OS/Arch to try and find all imports. This is different from setting UseAllFiles to true on the build Context. It scopes down to just the supported OS/Arch.

Note, there are cases where multiple packages are in the same directory. This usually happens with an example that has a main package and a +build tag of ignore. This is a bit of a hack. It causes UseAllFiles to have errors.

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 NewConstraint

func NewConstraint(t ConstraintType, body string) (Constraint, error)

NewConstraint constructs an appropriate Constraint object from the input parameters.

type ConstraintType

type ConstraintType uint8

const (
	RevisionConstraint ConstraintType = iota
	BranchConstraint
	VersionConstraint
	SemverConstraint
)

type Dependency

type Dependency struct {
	Depender ProjectAtom
	Dep      ProjectDep
}

type Lock

type Lock interface {
	// Indicates the version of the solver used to generate this lock file
	SolverVersion() string
	// The hash of inputs to the solver that resulted in this lock file
	InputHash() string
	// Returns the identifier for a project in the lock file, or nil if the
	// named project is not present in the lock file
	GetProjectAtom(ProjectName) *ProjectAtom
}

type Manifest

type Manifest interface {
	Name() ProjectName
	GetDependencies() []ProjectDep
	GetDevDependencies() []ProjectDep
}

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) (ProjectInfo, error)
}

type ProjectAtom

type ProjectAtom struct {
	Name    ProjectName
	Version Version
}

type ProjectDep

type ProjectDep struct {
	Name       ProjectName
	Constraint Constraint
}

type ProjectExistence

type ProjectExistence uint8

ProjectExistence values represent the extent to which a project "exists."

type ProjectInfo

type ProjectInfo struct {
	Manifest
	Lock
	// contains filtered or unexported fields
}

ProjectInfo holds the spec and lock information for a given ProjectAtom

type ProjectManager

type ProjectManager interface {
	GetInfoAt(Version) (ProjectInfo, error)
	ListVersions() ([]Version, error)
	CheckExistence(ProjectExistence) bool
	ExportVersionTo(Version, string) error
}

type ProjectName

type ProjectName string

type Result

type Result struct {
	// A list of the projects selected by the solver. nil if solving failed.
	Projects []ProjectAtom

	// The number of solutions that were attempted
	Attempts int

	// The error that ultimately prevented reaching a successful conclusion. nil
	// if solving was successful.
	// TODO proper error types
	SolveFailure error
}

func (Result) CreateVendorTree

func (r Result) CreateVendorTree(basedir string, sm SourceManager) error

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

Admits 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

AdmitsAny 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.

type SolveError

type SolveError interface {
	error
	Children() []error
}

type Solver

type Solver interface {
	Solve(root ProjectInfo, toUpgrade []ProjectName) Result
}

func NewSolver

func NewSolver(sm SourceManager, l *logrus.Logger) Solver

type SourceManager

type SourceManager interface {
	GetProjectInfo(ProjectAtom) (ProjectInfo, error)
	ListVersions(ProjectName) ([]Version, error)
	RepoExists(ProjectName) (bool, error)
	VendorCodeExists(ProjectName) (bool, error)
	ExportAtomTo(ProjectAtom, string) error
	Release()
}

func NewSourceManager

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

type UnpairedVersion

type UnpairedVersion interface {
	Version
	// Is takes the underlying Revision that this (Unpaired)Version 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 NewFloatingVersion

func NewFloatingVersion(body string) UnpairedVersion

NewFloatingVersion 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 {
	// Version composes Stringer to ensure that all versions can be serialized
	// to a string
	fmt.Stringer
	// contains filtered or unexported methods
}

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

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)
• 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.