vsolver

package module
v0.0.1 Latest Latest
Warning

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

 Go to latest Published: Mar 17, 2016 License: MIT Imports: 5 Imported by: 239

README

vsolver

vsolver is a SAT solver specifically built 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 two-file (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.
  • A project concept, where projects comprise the tree of Go packages rooted at the manifest/lock file pair.
  • 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.

Disliking solvers because "It seems complicated, idiomatic Go things are simple!" or "(Tool X) uses a solver and I don't like it" is just shooting the messenger. Remember, the enemy is not the SAT solver - it's the challenges inherent in the dependency resolution problem domain.

Features

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

  • Actually working/passing tests
  • 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

This section is empty.

Variables

View Source 
var VTCTCompat = [...]ConstraintType{
	C_Revision,
	C_Branch,
	C_Version,
	C_Semver | C_SemverRange,
}

Functions

This section is empty.

Types

type Constraint 

type Constraint interface {
	Type() ConstraintType
	Body() string
	Allows(Version) bool
	UnionAllowsAny(Constraint) bool
}

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 (
	C_Revision ConstraintType = 1 << iota
	C_Branch
	C_Version
	C_Semver
	C_SemverRange
	C_ExactMatch = C_Revision | C_Branch | C_Version | C_Semver
	C_FlexMatch  = C_SemverRange
)

type Dependency 

type Dependency struct {
	Depender ProjectID
	Dep      ProjectDep
}

type InfoLevel 

type InfoLevel uint
const (
	FromCache InfoLevel = 1 << iota
)

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
	GetProjectID(ProjectIdentifier) *ProjectID
}

type ProjectDep 

type ProjectDep struct {
	ID         ProjectIdentifier
	Constraint Constraint
}

type ProjectExistence 

type ProjectExistence uint8

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

const (
	// DoesNotExist indicates that a particular project URI cannot be located,
	// at any level. It is represented as 1, rather than 0, to differentiate it
	// from the zero-value (which is ExistenceUnknown).
	DoesNotExist ProjectExistence = 1 << iota

	// 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

	// ExistsInVendor 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 in no way be
	// construed as exhaustive.
	ExistsInVendor

	// 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

	// Indicates that the upstream project, in addition to existing, is also
	// accessible.
	//
	// Different hosting providers treat unauthorized access differently:
	// GitHub, for example, returns 404 (or the equivalent) when attempting unauthorized
	// access, whereas BitBucket returns 403 (or 302 login redirect). Thus,
	// while the ExistsUpstream and UpstreamAccessible bits should always only
	// be on or off together when interacting with Github, it is possible that a
	// BitBucket provider might report ExistsUpstream, but not UpstreamAccessible.
	//
	// For most purposes, non-existence and inaccessibility are treated the
	// same, but clearly delineating the two allows slightly improved UX.
	UpstreamAccessible

	// The zero value; indicates that no work has yet been done to determine the
	// existence level of a project.
	ExistenceUnknown ProjectExistence = 0
)

type ProjectID 

type ProjectID struct {
	ID      ProjectIdentifier
	Version Version
}

TODO naming lolol

type ProjectIdentifier 

type ProjectIdentifier string

type ProjectInfo 

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

ProjectInfo holds the spec and lock information for a given ProjectID

type Result 

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

	// 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
}

type SolveError 

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

type SolveFailure 

type SolveFailure uint
const (
	// Indicates that no version solution could be found
	NoVersionSolution SolveFailure = 1 << iota
	IncompatibleVersionType
)

type Solver 

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

func NewSolver 

func NewSolver(sm SourceManager) Solver

type SourceManager 

type SourceManager interface {
	GetProjectInfo(ProjectID) (ProjectInfo, error)
	ListVersions(ProjectIdentifier) ([]ProjectID, error)
	ProjectExists(ProjectIdentifier) bool
}

type Spec 

type Spec interface {
	ID() ProjectIdentifier
	GetDependencies() []ProjectDep
	GetDevDependencies() []ProjectDep
}

type Version 

type Version struct {
	// The type of version identifier
	Type VersionType
	// The version identifier itself
	Info   string
	SemVer *semver.Version
}

type VersionQueue 

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

func NewVersionQueue 

func NewVersionQueue(ref ProjectIdentifier, lockv *ProjectID, sm SourceManager) (*VersionQueue, error)

type VersionType 

type VersionType uint8

The type of the version - branch, revision, or version 

const (
	V_Revision VersionType = iota
	V_Branch
	V_Version
	V_Semver
)

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.