vsolver

package module
v0.2.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 5, 2016 License: MIT Imports: 22 Imported by: 239

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

Constants

View Source 
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
)

Variables

This section is empty.

Functions

func CreateVendorTree added in v0.2.0 

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

func ExternalReach added in v0.1.0 

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 IsAny added in v0.2.0 

func IsAny(c Constraint) bool

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

func IterativeScan added in v0.1.0 

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 BadOptsFailure added in v0.2.0 

type BadOptsFailure string

func (BadOptsFailure) Error added in v0.2.0 

func (e BadOptsFailure) Error() string

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 added in v0.2.0 

func Any() Constraint

Any returns a constraint that will match anything.

func NewConstraint 

func NewConstraint(body string, t ConstraintType) (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 {

	// 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 added in v0.2.0 

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 URI for accessing it, and the path at which it should be placed within a vendor directory.

TODO note that sometime soon, we also plan to allow pkgs. this'll change

func NewLockedProject added in v0.2.0 

func NewLockedProject(n ProjectName, v Version, uri, path 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 added in v0.2.0 

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 added in v0.2.0 

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 added in v0.2.0 

func (lp LockedProject) Version() Version

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

type Manifest added in v0.1.0 

type Manifest interface {
	Name() ProjectName
	GetDependencies() []ProjectDep
	GetDevDependencies() []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:

- A list of dependencies: project name, and a constraint - A list of development-time dependencies (e.g. for testing - only the root project's are incorporated)

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 PairedVersion added in v0.1.0 

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 added in v0.1.0 

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

type ProjectAtom added in v0.1.0 

type ProjectAtom struct {
	Ident   ProjectIdentifier
	Version Version
}

type ProjectDep 

type ProjectDep struct {
	Ident      ProjectIdentifier
	Constraint Constraint
}

type ProjectExistence 

type ProjectExistence uint8

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

type ProjectIdentifier 

type ProjectIdentifier struct {
	LocalName   ProjectName
	NetworkName string
}

type ProjectInfo 

type ProjectInfo struct {
	N ProjectName
	V Version
	Manifest
	Lock
}

ProjectInfo holds manifest and lock for a ProjectName at a Version

type ProjectManager added in v0.1.0 

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

type ProjectName added in v0.1.0 

type ProjectName string

type Result 

type Result interface {
	Lock
	Attempts() int
}

type Revision added in v0.1.0 

type Revision string

A Revision represents an immutable versioning identifier.

func (Revision) Intersect added in v0.1.0 

func (r Revision) Intersect(c Constraint) Constraint

func (Revision) Matches added in v0.1.0 

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 added in v0.1.0 

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 added in v0.1.0 

func (r Revision) String() string

String converts the Revision back into a string.

func (Revision) Type added in v0.2.0 

func (r Revision) Type() string

type SimpleLock added in v0.2.0 

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 added in v0.2.0 

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 added in v0.2.0 

func (l SimpleLock) Projects() []LockedProject

Projects returns the entire contents of the SimpleLock.

type SimpleManifest added in v0.2.0 

type SimpleManifest struct {
	N  ProjectName
	P  []ProjectDep
	DP []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) GetDependencies added in v0.2.0 

func (m SimpleManifest) GetDependencies() []ProjectDep

GetDependencies returns the project's dependencies.

func (SimpleManifest) GetDevDependencies added in v0.2.0 

func (m SimpleManifest) GetDevDependencies() []ProjectDep

GetDependencies returns the project's test dependencies.

func (SimpleManifest) Name added in v0.2.0 

func (m SimpleManifest) Name() ProjectName

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

type SolveError 

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

type SolveOpts added in v0.2.0 

type SolveOpts 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.
	N ProjectName
	// The root manifest. Required. This contains all the dependencies, constraints, and
	// other controls available to the root project.
	M 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.
	L Lock
	// 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
}

SolveOpts holds both options that govern solving behavior, and the actual inputs to the solving process.

func (SolveOpts) HashInputs added in v0.2.0 

func (o SolveOpts) HashInputs() []byte

HashInputs computes a hash digest of all data in a SolveOpts that are as function inputs to Solve().

The digest returned from this function is the same as the digest that would be included with a Solve() Result. As such, it's appropriate for comparison against the digest stored in a lock file, generated by a previous Solve(): if the digests match, then manifest and lock are in sync, and a Solve() is unnecessary.

(Basically, this is for memoization.)

type Solver 

type Solver interface {
	Solve(opts SolveOpts) (Result, error)
}

func NewSolver 

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

type SourceManager 

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

func NewSourceManager added in v0.1.0 

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

type UnpairedVersion added in v0.1.0 

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 NewBranch added in v0.2.0 

func NewBranch(body string) UnpairedVersion

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

func NewVersion added in v0.1.0 

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

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.