pubgrub

type CacheStats ¶

type CacheStats struct {
	VersionsCalls     int
	VersionsCacheHits int
	VersionsHitRate   float64

	DepsCalls     int
	DepsCacheHits int
	DepsHitRate   float64

	TotalCalls     int
	TotalCacheHits int
	OverallHitRate float64
}

CacheStats returns statistics about cache performance.

type CachedSource ¶

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

CachedSource wraps a Source and caches GetVersions and GetDependencies calls to improve performance when the same queries are made repeatedly.

WHEN TO USE: CachedSource is most beneficial for: - Sources with expensive network I/O (package registries, APIs) - Sources with disk I/O or database queries - Running multiple dependency resolutions without recreating the source - Build systems that resolve dependencies repeatedly

WHEN NOT TO USE: CachedSource adds ~3-5% overhead for: - InMemorySource (already fast, no repeated queries in CDCL solver) - Simple, single-shot dependency resolutions - Sources where queries are naturally cached upstream

The cache is maintained for the lifetime of the CachedSource instance and assumes that version lists and dependencies are immutable during solving.

func NewCachedSource(source Source) *CachedSource

func (c *CachedSource) ClearCache()

func (c *CachedSource) GetCacheStats() CacheStats

func (c *CachedSource) GetDependencies(name Name, version Version) ([]Term, error)

func (c *CachedSource) GetVersions(name Name) ([]Version, error)

type CollapsedReporter ¶

type CollapsedReporter struct{}

CollapsedReporter produces a more compact error format

func (r *CollapsedReporter) Report(incomp *Incompatibility) string

type CombinedSource ¶

type CombinedSource []Source

CombinedSource aggregates multiple package sources into a single source. When querying for versions or dependencies, it tries each source in order and combines the results.

This is useful for:

• Combining local and remote package sources
• Implementing package source fallbacks
• Testing with mixed source types

Example:

local := &InMemorySource{}
remote := &RegistrySource{}
combined := CombinedSource{local, remote}
solver := NewSolver(root, combined)

func (s CombinedSource) GetDependencies(name Name, version Version) ([]Term, error)

func (s CombinedSource) GetVersions(name Name) ([]Version, error)

type Condition ¶

type Condition interface {
	// String returns a human-readable representation of the condition.
	String() string

	// Satisfies returns true if the given version meets the condition.
	Satisfies(ver Version) bool
}

Condition represents a constraint on package versions. Basic conditions like equality are built-in, but custom conditions can be implemented by satisfying this interface.

Built-in implementations:

• EqualsCondition: Exact version match
• VersionSetCondition: Version range constraints

Example custom condition:

type MinVersionCondition struct {
    MinVersion Version
}

func (mvc MinVersionCondition) String() string {
    return fmt.Sprintf(">=%s", mvc.MinVersion)
}

func (mvc MinVersionCondition) Satisfies(ver Version) bool {
    return ver.Sort(mvc.MinVersion) >= 0
}

type DefaultReporter ¶

type DefaultReporter struct{}

DefaultReporter produces readable error messages with hierarchical structure

func (r *DefaultReporter) Report(incomp *Incompatibility) string

type DependencyError ¶

type DependencyError struct {
	Package Name
	Version Version
	Err     error
}

DependencyError represents an error while fetching dependencies

func (e *DependencyError) Error() string

func (e *DependencyError) Unwrap() error

type EqualsCondition ¶

type EqualsCondition struct {
	Version Version
}

EqualsCondition represents an exact version match constraint. This is the most basic condition type, requiring a version to exactly match the specified version.

For more flexible constraints like version ranges, use VersionSetCondition with ParseVersionRange.

Example:

cond := EqualsCondition{Version: SimpleVersion("1.0.0")}
fmt.Println(cond.Satisfies(SimpleVersion("1.0.0"))) // true
fmt.Println(cond.Satisfies(SimpleVersion("1.0.1"))) // false

func (c EqualsCondition) Satisfies(ver Version) bool

func (c EqualsCondition) String() string

type ErrIterationLimit ¶

type ErrIterationLimit struct {
	Steps int
}

ErrIterationLimit is returned when the solver exceeds its maximum iteration count. This prevents infinite loops in pathological cases. Configure with WithMaxSteps(0) to disable the limit (not recommended for untrusted inputs).

Example:

solver := NewSolverWithOptions(
    []Source{root, source},
    WithMaxSteps(1000),
)
_, err := solver.Solve(root.Term())
if iterErr, ok := err.(ErrIterationLimit); ok {
    log.Printf("Solver exceeded %d steps", iterErr.Steps)
}

func (e ErrIterationLimit) Error() string

type ErrNoSolutionFound ¶

type ErrNoSolutionFound struct {
	Term Term
}

ErrNoSolutionFound is a simple error returned when solving fails without incompatibility tracking. For detailed error messages with derivation trees, enable WithIncompatibilityTracking and use NoSolutionError.

Example:

solver := NewSolver(root, source) // Tracking disabled by default
_, err := solver.Solve(root.Term())
if err != nil {
    if errors.Is(err, ErrNoSolutionFound{}) {
        // Handle no solution case
    }
}

func (e ErrNoSolutionFound) Error() string

type InMemorySource ¶

type InMemorySource struct {
	Packages map[Name]map[Version][]Term
}

InMemorySource provides an in-memory implementation of Source for testing and simple use cases. It stores all package versions and dependencies in memory without any I/O operations.

This is the simplest source implementation and is useful for:

• Testing dependency resolution scenarios
• Building example dependency graphs
• Prototyping before implementing a real package source

For production use cases with network or database access, consider wrapping your source with CachedSource for performance.

Example:

source := &InMemorySource{}
source.AddPackage("lodash", SimpleVersion("1.0.0"), []Term{
    NewTerm("core-js", EqualsCondition{Version: SimpleVersion("2.0.0")}),
})
source.AddPackage("core-js", SimpleVersion("2.0.0"), nil)

func (s *InMemorySource) AddPackage(name Name, version Version, deps []Term)

func (s *InMemorySource) GetDependencies(name Name, version Version) ([]Term, error)

func (s *InMemorySource) GetVersions(name Name) ([]Version, error)

type Incompatibility ¶

type Incompatibility struct {
	// Terms that are incompatible
	Terms []Term
	// Kind of incompatibility
	Kind IncompatibilityKind
	// Cause1 and Cause2 are set for derived incompatibilities (Kind == KindConflict)
	Cause1 *Incompatibility
	Cause2 *Incompatibility
	// Package and Version for KindFromDependency
	Package Name
	Version Version
}

Incompatibility represents a set of package requirements that cannot all be satisfied

func NewIncompatibilityConflict(terms []Term, cause1, cause2 *Incompatibility) *Incompatibility

func NewIncompatibilityFromDependency(pkg Name, ver Version, dependency Term) *Incompatibility

func NewIncompatibilityNoVersions(term Term) *Incompatibility

func (inc *Incompatibility) String() string

type IncompatibilityKind ¶

type IncompatibilityKind int

IncompatibilityKind represents the type/origin of an incompatibility

const (
	// KindNoVersions means no versions satisfy the constraint
	KindNoVersions IncompatibilityKind = iota
	// KindFromDependency means incompatibility from a package dependency
	KindFromDependency
	// KindConflict means derived from conflict resolution
	KindConflict
)

type Name ¶

type Name = unique.Handle[string]

Name represents a package name using value interning for memory efficiency. Multiple instances of the same package name share the same underlying memory.

Name uses Go's unique.Handle for efficient string interning, enabling:

• Fast equality comparisons (pointer comparison instead of string comparison)
• Reduced memory usage when the same package names appear frequently
• Safe concurrent access (interning is thread-safe)

func EmptyName() Name

func MakeName(s string) Name

pkg1 := MakeName("lodash")
pkg2 := MakeName("lodash")
// pkg1 == pkg2 (fast pointer comparison)

type NameVersion ¶

type NameVersion struct {
	Name    Name
	Version Version
}

NameVersion represents a resolved package with its selected version. This is the fundamental unit of a dependency resolution solution.

func (n NameVersion) String() string

type NoSolutionError ¶

type NoSolutionError struct {
	// Incompatibility is the root cause of the failure
	Incompatibility *Incompatibility
	// Reporter is used to format the error message (defaults to DefaultReporter)
	Reporter Reporter
}

NoSolutionError is returned when version solving fails with detailed explanation

// Same scenario but with collapsed reporter
source := &InMemorySource{}
source.AddPackage(MakeName("dropdown"), SimpleVersion("2.0.0"), []Term{
	NewTerm(MakeName("icons"), EqualsCondition{Version: SimpleVersion("2.0.0")}),
})
source.AddPackage(MakeName("icons"), SimpleVersion("1.0.0"), nil)
// Note: icons 2.0.0 doesn't exist

root := NewRootSource()
root.AddPackage(MakeName("dropdown"), EqualsCondition{Version: SimpleVersion("2.0.0")})

solver := NewSolver(root, source).EnableIncompatibilityTracking()
_, err := solver.Solve(root.Term())

if nsErr, ok := err.(*NoSolutionError); ok {
	// Use collapsed reporter for more compact output
	customErr := nsErr.WithReporter(&CollapsedReporter{})
	fmt.Println("Error:")
	fmt.Println(customErr.Error())
}

Output:

Error:
no versions of icons == 2.0.0 satisfy the constraint
And because dropdown 2.0.0 depends on icons == 2.0.0
And because dropdown == 2.0.0 is forbidden
And because $$root 1 depends on dropdown == 2.0.0
And because $$root == 1 is forbidden

// Create a conflict scenario:
// Package A v1.0 depends on B v1.0
// Package C v1.0 depends on B v2.0
// Root depends on both A and C
source := &InMemorySource{}
source.AddPackage(MakeName("A"), SimpleVersion("1.0.0"), []Term{
	NewTerm(MakeName("B"), EqualsCondition{Version: SimpleVersion("1.0.0")}),
})
source.AddPackage(MakeName("B"), SimpleVersion("1.0.0"), nil)
source.AddPackage(MakeName("B"), SimpleVersion("2.0.0"), nil)
source.AddPackage(MakeName("C"), SimpleVersion("1.0.0"), []Term{
	NewTerm(MakeName("B"), EqualsCondition{Version: SimpleVersion("2.0.0")}),
})

root := NewRootSource()
root.AddPackage(MakeName("A"), EqualsCondition{Version: SimpleVersion("1.0.0")})
root.AddPackage(MakeName("C"), EqualsCondition{Version: SimpleVersion("1.0.0")})

// Enable incompatibility tracking for detailed errors
solver := NewSolver(root, source).EnableIncompatibilityTracking()
_, err := solver.Solve(root.Term())

if err != nil {
	fmt.Println("Error:")
	fmt.Println(err.Error())
}

Output:

Error:
Because:
  Because:
    Because:
      Because C 1.0.0 depends on B == 2.0.0
    and:
      Because A 1.0.0 depends on B == 1.0.0
    these constraints conflict: C == 1.0.0 and A == 1.0.0
  and:
    Because $$root 1 depends on C == 1.0.0
  these constraints conflict: A == 1.0.0 and $$root == 1
and:
  Because $$root 1 depends on A == 1.0.0
$$root == 1 is forbidden.

func NewNoSolutionError(incomp *Incompatibility) *NoSolutionError

func (e *NoSolutionError) Error() string

func (e *NoSolutionError) Unwrap() error

func (e *NoSolutionError) WithReporter(reporter Reporter) *NoSolutionError

type PackageNotFoundError ¶

type PackageNotFoundError struct {
	Package Name
}

PackageNotFoundError indicates that a package is absent from the source.

func (e *PackageNotFoundError) Error() string

type PackageVersionNotFoundError ¶

type PackageVersionNotFoundError struct {
	Package Name
	Version Version
}

PackageVersionNotFoundError indicates a specific version is unavailable.

func (e *PackageVersionNotFoundError) Error() string

type Reporter ¶

type Reporter interface {
	// Report generates a human-readable error message from an incompatibility
	Report(incomp *Incompatibility) string
}

Reporter is an interface for formatting incompatibilities into error messages

type RootSource ¶

type RootSource []Term

RootSource provides a special source for initial dependency requirements. It creates a virtual "$$root" package that the solver uses as the starting point for dependency resolution.

In PubGrub, the root package has a single version ("1") whose dependencies are the user's initial requirements. This design allows the solver to treat the root requirements uniformly with other package dependencies.

Example:

root := NewRootSource()
root.AddPackage("lodash", EqualsCondition{Version: SimpleVersion("1.0.0")})
root.AddPackage("moment", EqualsCondition{Version: SimpleVersion("2.0.0")})
solver := NewSolver(root, otherSources...)
solution, _ := solver.Solve(root.Term())

func NewRootSource() *RootSource

func (s *RootSource) AddPackage(name Name, condition Condition)

func (s RootSource) GetDependencies(name Name, version Version) ([]Term, error)

func (s RootSource) GetVersions(name Name) ([]Version, error)

func (s *RootSource) Term() Term

type SemanticVersion ¶

type SemanticVersion struct {
	Major      int
	Minor      int
	Patch      int
	Prerelease string
	Build      string
}

SemanticVersion represents a semantic version (major.minor.patch[-prerelease][+build])

// Parse semantic versions
v1, _ := pubgrub.ParseSemanticVersion("1.2.3")
v2, _ := pubgrub.ParseSemanticVersion("1.2.4")
v3, _ := pubgrub.ParseSemanticVersion("2.0.0-alpha")

// Compare versions
fmt.Println("v1 < v2:", v1.Sort(v2) < 0)
fmt.Println("v2 > v1:", v2.Sort(v1) > 0)
fmt.Println("v3 (prerelease) < 2.0.0:", v3.Sort(pubgrub.NewSemanticVersion(2, 0, 0)) < 0)

Output:

v1 < v2: true
v2 > v1: true
v3 (prerelease) < 2.0.0: true

func NewSemanticVersion(major, minor, patch int) *SemanticVersion

func NewSemanticVersionWithPrerelease(major, minor, patch int, prerelease string) *SemanticVersion

func ParseSemanticVersion(s string) (*SemanticVersion, error)

func (sv *SemanticVersion) Sort(other Version) int

-1 if sv < other
 0 if sv == other
 1 if sv > other

func (sv *SemanticVersion) String() string

type SimpleVersion ¶

type SimpleVersion string

SimpleVersion provides a basic string-based version implementation. Versions are compared lexicographically using string comparison.

For semantic versioning support, use SemanticVersion instead.

Example:

v1 := SimpleVersion("1.0.0")
v2 := SimpleVersion("2.0.0")
fmt.Println(v1.Sort(v2)) // prints negative number (v1 < v2)

func (v SimpleVersion) Sort(other Version) int

func (v SimpleVersion) String() string

type Solution ¶

type Solution []NameVersion

Solution represents the complete set of resolved package versions. A solution maps package names to their selected versions, ensuring all dependency constraints are satisfied.

Example:

solution, err := solver.Solve(root.Term())
if err != nil {
    log.Fatal(err)
}
for pkg := range solution.All() {
    fmt.Printf("%s: %s\n", pkg.Name.Value(), pkg.Version)
}

func (s Solution) All() iter.Seq[NameVersion]

for pkg := range solution.All() {
    fmt.Printf("%s: %s\n", pkg.Name, pkg.Version)
}

func (s Solution) GetVersion(name Name) (Version, bool)

type Solver ¶

type Solver struct {
	Source Source
	// contains filtered or unexported fields
}

Solver implements the PubGrub dependency resolution algorithm with CDCL.

The solver uses Conflict-Driven Clause Learning (CDCL) to efficiently find valid package version assignments that satisfy all dependencies and constraints. It maintains learned incompatibilities to avoid repeating failed resolution attempts.

Basic usage:

root := NewRootSource()
root.AddPackage("myapp", EqualsCondition{Version: SimpleVersion("1.0.0")})

source := &InMemorySource{}
// ... populate source with packages ...

solver := NewSolver(root, source)
solution, err := solver.Solve(root.Term())

With options:

solver := NewSolverWithOptions(
    []Source{root, source},
    WithIncompatibilityTracking(true),
    WithMaxSteps(10000),
)

source := &InMemorySource{}
source.AddPackage(MakeName("foo"), SimpleVersion("1.0.0"), []Term{
	NewTerm(MakeName("bar"), EqualsCondition{Version: SimpleVersion("2.0.0")}),
})
source.AddPackage(MakeName("bar"), SimpleVersion("1.0.0"), nil)

root := NewRootSource()
root.AddPackage(MakeName("foo"), EqualsCondition{Version: SimpleVersion("1.0.0")})

// Without tracking, get simple error (backward compatible)
solver := NewSolver(root, source) // tracking disabled by default
_, err := solver.Solve(root.Term())

if err != nil {
	// Will be ErrNoSolutionFound, not NoSolutionError
	fmt.Printf("Error type: %T\n", err)
	// Error message will vary based on where solving fails
	if _, ok := err.(ErrNoSolutionFound); ok {
		fmt.Println("Got simple ErrNoSolutionFound (backward compatible)")
	}
}

Output:

Error type: pubgrub.ErrNoSolutionFound
Got simple ErrNoSolutionFound (backward compatible)

func NewSolver(sources ...Source) *Solver

root := NewRootSource()
source := &InMemorySource{}
solver := NewSolver(root, source)

func NewSolverWithOptions(sources []Source, opts ...SolverOption) *Solver

func (s *Solver) ClearIncompatibilities()

func (s *Solver) Configure(opts ...SolverOption) *Solver

func (s *Solver) DisableIncompatibilityTracking() *Solver

func (s *Solver) EnableIncompatibilityTracking() *Solver

func (s *Solver) GetIncompatibilities() []*Incompatibility

source := &InMemorySource{}
source.AddPackage(MakeName("foo"), SimpleVersion("1.0.0"), []Term{
	NewTerm(MakeName("bar"), EqualsCondition{Version: SimpleVersion("2.0.0")}),
})
source.AddPackage(MakeName("bar"), SimpleVersion("1.0.0"), nil)

root := NewRootSource()
root.AddPackage(MakeName("foo"), EqualsCondition{Version: SimpleVersion("1.0.0")})

solver := NewSolver(root, source).EnableIncompatibilityTracking()
_, err := solver.Solve(root.Term())

if err != nil {
	fmt.Printf("Solving failed: %v\n", err)

	// Get all tracked incompatibilities
	incomps := solver.GetIncompatibilities()
	fmt.Printf("Tracked %d incompatibilities during solving\n", len(incomps))

	for i, incomp := range incomps {
		fmt.Printf("  [%d] %s (kind: %d)\n", i+1, incomp.String(), incomp.Kind)
	}
}

Output:

Solving failed: Because:
  Because:
    No versions of bar == 2.0.0 satisfy the constraint
  and:
    Because foo 1.0.0 depends on bar == 2.0.0
  foo == 1.0.0 is forbidden.
and:
  Because $$root 1 depends on foo == 1.0.0
$$root == 1 is forbidden.
Tracked 4 incompatibilities during solving
  [1] $$root 1 depends on foo == 1.0.0 (kind: 1)
  [2] foo 1.0.0 depends on bar == 2.0.0 (kind: 1)
  [3] foo == 1.0.0 is forbidden (kind: 2)
  [4] foo == 1.0.0 is forbidden (kind: 2)

func (s *Solver) Solve(root Term) (Solution, error)

type SolverOption ¶

type SolverOption func(*SolverOptions)

SolverOption is a functional option for configuring the solver.

func WithIncompatibilityTracking(enabled bool) SolverOption

solver := NewSolverWithOptions(
    []Source{root, source},
    WithIncompatibilityTracking(true),
)

func WithLogger(logger *slog.Logger) SolverOption

logger := slog.New(slog.NewTextHandler(os.Stderr, &slog.HandlerOptions{Level: slog.LevelDebug}))
solver := NewSolverWithOptions(
    []Source{root, source},
    WithLogger(logger),
)

func WithMaxSteps(steps int) SolverOption

solver := NewSolverWithOptions(
    []Source{root, source},
    WithMaxSteps(10000), // Limit to 10k iterations
)

func WithPreferHighestVersions(enabled bool) SolverOption

type SolverOptions ¶

type SolverOptions struct {
	// TrackIncompatibilities enables collecting learned clauses for error reporting.
	// When enabled, NoSolutionError will include a detailed derivation tree.
	// When disabled, returns simple ErrNoSolutionFound.
	TrackIncompatibilities bool

	// MaxSteps limits the number of solver iterations.
	// Set to 0 to disable the limit (not recommended for untrusted inputs).
	// Default: 100000
	MaxSteps int

	// Logger enables debug logging of solver operations.
	// When nil, no logging is performed.
	Logger *slog.Logger

	// PreferHighestVersions forces the solver to pick the highest allowed version.
	// When false, the solver uses a dependency-flexibility heuristic.
	PreferHighestVersions bool
}

SolverOptions configures the behavior of the dependency solver.

Options control:

• Incompatibility tracking for enhanced error reporting
• Maximum iteration limits to prevent infinite loops
• Debug logging for solver diagnostics

type Source ¶

type Source interface {
	// GetVersions returns all versions of a package in sorted order.
	// Versions should be sorted from lowest to highest, as the solver
	// selects from the highest available version.
	GetVersions(name Name) ([]Version, error)

	// GetDependencies returns the dependency terms for a specific package version.
	GetDependencies(name Name, version Version) ([]Term, error)
}

Source provides access to package versions and their dependencies. Implementations can fetch from in-memory stores, network registries, file systems, or any other package source.

Built-in implementations:

• InMemorySource: Simple in-memory storage for testing
• CombinedSource: Aggregates multiple sources
• RootSource: Special source for initial requirements
• CachedSource: Wraps a source with caching for performance

Example custom source:

type RegistrySource struct {
    BaseURL string
    Client  *http.Client
}

func (rs *RegistrySource) GetVersions(name Name) ([]Version, error) {
    resp, err := rs.Client.Get(rs.BaseURL + "/packages/" + name.Value() + "/versions")
    // ... parse response ...
}

func (rs *RegistrySource) GetDependencies(name Name, version Version) ([]Term, error) {
    resp, err := rs.Client.Get(rs.BaseURL + "/packages/" + name.Value() + "/" + version.String())
    // ... parse response ...
}

type Term ¶

type Term struct {
	Name      Name
	Condition Condition
	Positive  bool
}

Term represents a dependency constraint, either positive or negative. A positive term (e.g., "lodash >=1.0.0") asserts that a package must satisfy the condition. A negative term (e.g., "not lodash ==1.5.0") excludes versions that match the condition.

Terms are the building blocks of dependency resolution, combining package names with version constraints and polarity.

func NewNegativeTerm(name Name, condition Condition) Term

func NewTerm(name Name, condition Condition) Term

func (t Term) IsPositive() bool

func (t Term) Negate() Term

func (t Term) SatisfiedBy(ver Version) bool

func (t Term) String() string

type Version ¶

type Version interface {
	// String returns a human-readable representation of the version.
	String() string

	// Sort compares this version to another.
	// Returns:
	//   - negative if this version < other
	//   - zero if this version == other
	//   - positive if this version > other
	Sort(other Version) int
}

Version represents a package version in the dependency resolution system. Implementations must provide string representation and comparison.

The PubGrub algorithm is version-type agnostic - any type can be used as long as it implements this interface. Built-in implementations include:

• SimpleVersion: Lexicographic string comparison
• SemanticVersion: Full semver with major.minor.patch ordering

Example custom version:

type DateVersion time.Time

func (dv DateVersion) String() string {
    return time.Time(dv).Format("2006-01-02")
}

func (dv DateVersion) Sort(other Version) int {
    otherDate, ok := other.(DateVersion)
    if !ok {
        return strings.Compare(dv.String(), other.String())
    }
    return time.Time(dv).Compare(time.Time(otherDate))
}

type VersionError ¶

type VersionError struct {
	Package Name
	Message string
}

VersionError represents an error related to version constraints

func (e *VersionError) Error() string

type VersionIntervalSet ¶

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

VersionIntervalSet implements VersionSet using sorted, disjoint intervals. This representation efficiently handles common version constraints like ranges and unions.

Intervals are stored in normalized form: sorted, non-empty, non-overlapping, and with no adjacent intervals that could be merged. This ensures efficient set operations and canonical string representations.

Example:

set := &VersionIntervalSet{}
set1 := ParseVersionRange(">=1.0.0, <2.0.0")
set2 := ParseVersionRange(">=1.5.0, <3.0.0")
union := set1.Union(set2) // >=1.0.0, <3.0.0

func (s *VersionIntervalSet) Complement() VersionSet

func (s *VersionIntervalSet) Contains(version Version) bool

func (s *VersionIntervalSet) Empty() VersionSet

func (s *VersionIntervalSet) Full() VersionSet

func (s *VersionIntervalSet) Intersection(other VersionSet) VersionSet

func (s *VersionIntervalSet) Intervals() iter.Seq[versionInterval]

for interval := range versionSet.Intervals() {
    fmt.Printf("Range: %v to %v\n", interval.lower, interval.upper)
}

func (s *VersionIntervalSet) IsDisjoint(other VersionSet) bool

func (s *VersionIntervalSet) IsEmpty() bool

func (s *VersionIntervalSet) IsSubset(other VersionSet) bool

func (s *VersionIntervalSet) Singleton(version Version) VersionSet

func (s *VersionIntervalSet) String() string

func (s *VersionIntervalSet) Union(other VersionSet) VersionSet

type VersionSet ¶

type VersionSet interface {
	// Empty returns a VersionSet containing no versions.
	Empty() VersionSet

	// Full returns a VersionSet containing all possible versions.
	Full() VersionSet

	// Singleton returns a VersionSet containing exactly one version.
	Singleton(version Version) VersionSet

	// Union returns the set of versions in either this set or the other.
	Union(other VersionSet) VersionSet

	// Intersection returns the set of versions in both this set and the other.
	Intersection(other VersionSet) VersionSet

	// Complement returns the set of versions NOT in this set.
	Complement() VersionSet

	// Contains tests if a specific version is in the set.
	Contains(version Version) bool

	// IsEmpty returns true if the set contains no versions.
	IsEmpty() bool

	// IsSubset returns true if all versions in this set are also in the other set.
	IsSubset(other VersionSet) bool

	// IsDisjoint returns true if this set and the other set have no versions in common.
	IsDisjoint(other VersionSet) bool

	// String returns a human-readable representation of the set.
	String() string
}

VersionSet represents a set of versions that can be used in version constraints. Implementations must be immutable – all operations return new instances.

VersionSet enables algebraic operations on version constraints, supporting:

• Union: combining multiple version ranges
• Intersection: finding common versions between constraints
• Complement: inverting version constraints
• Subset/Disjoint testing: analyzing constraint relationships

The primary implementation is VersionIntervalSet, which efficiently represents version ranges as sorted, non-overlapping intervals.

Example usage:

// Parse a version range from string
set1, _ := ParseVersionRange(">=1.0.0, <2.0.0")
set2, _ := ParseVersionRange(">=1.5.0, <3.0.0")

// Combine constraints
union := set1.Union(set2)        // >=1.0.0, <3.0.0
intersection := set1.Intersection(set2) // >=1.5.0, <2.0.0
complement := set1.Complement()   // <1.0.0 || >=2.0.0

func EmptyVersionSet() VersionSet

func FullVersionSet() VersionSet

func NewLowerBoundVersionSet(version Version, inclusive bool) VersionSet

v, _ := ParseSemanticVersion("1.0.0")
set := NewLowerBoundVersionSet(v, true) // >=1.0.0

func NewUpperBoundVersionSet(version Version, inclusive bool) VersionSet

v, _ := ParseSemanticVersion("2.0.0")
set := NewUpperBoundVersionSet(v, false) // <2.0.0

func NewVersionRangeSet(lower Version, lowerInclusive bool, upper Version, upperInclusive bool) VersionSet

// Create range [1.0.0, 2.0.0)
lower, _ := ParseSemanticVersion("1.0.0")
upper, _ := ParseSemanticVersion("2.0.0")
set := NewVersionRangeSet(lower, true, upper, false)

func ParseVersionRange(s string) (VersionSet, error)

ParseVersionRange(">=1.0.0, <2.0.0")     // [1.0.0, 2.0.0)
ParseVersionRange(">=1.0.0 || >=3.0.0")  // >=1.0.0 OR >=3.0.0
ParseVersionRange("*")                   // Any version
ParseVersionRange("==1.5.0")             // Exactly 1.5.0
ParseVersionRange("!=1.5.0")             // Not 1.5.0

// Simple range
range1, _ := pubgrub.ParseVersionRange(">=1.0.0")
fmt.Println("Range 1:", range1.String())

// Compound range (AND)
range2, _ := pubgrub.ParseVersionRange(">=1.0.0, <2.0.0")
fmt.Println("Range 2:", range2.String())

// Union range (OR)
range3, _ := pubgrub.ParseVersionRange(">=1.0.0, <2.0.0 || >=3.0.0")
fmt.Println("Range 3:", range3.String())

// Test if a version is in the range
v150, _ := pubgrub.ParseSemanticVersion("1.5.0")
fmt.Println("1.5.0 in range2:", range2.Contains(v150))

Output:

Range 1: >=1.0.0
Range 2: >=1.0.0, <2.0.0
Range 3: >=1.0.0, <2.0.0 || >=3.0.0
1.5.0 in range2: true

type VersionSetCondition ¶

type VersionSetCondition struct {
	Set VersionSet
}

VersionSetCondition implements Condition using a VersionSet. This enables using complex version constraints (ranges, unions, complements) as dependency conditions.

Example:

// Create a version range condition
set, _ := ParseVersionRange(">=1.0.0, <2.0.0")
condition := NewVersionSetCondition(set)
term := NewTerm("lodash", condition)

// Create an in-memory package source
source := &pubgrub.InMemorySource{}

// Add package versions with semantic versioning
v100, _ := pubgrub.ParseSemanticVersion("1.0.0")
v110, _ := pubgrub.ParseSemanticVersion("1.1.0")
v200, _ := pubgrub.ParseSemanticVersion("2.0.0")
v210, _ := pubgrub.ParseSemanticVersion("2.1.0")

// Create version range conditions
range1x, _ := pubgrub.ParseVersionRange(">=1.0.0, <2.0.0")
range2x, _ := pubgrub.ParseVersionRange(">=2.0.0")

// Package A has multiple versions
source.AddPackage(pubgrub.MakeName("A"), v100, []pubgrub.Term{})
source.AddPackage(pubgrub.MakeName("A"), v110, []pubgrub.Term{
	pubgrub.NewTerm(pubgrub.MakeName("B"), pubgrub.NewVersionSetCondition(range2x)),
})

// Package B has multiple versions
source.AddPackage(pubgrub.MakeName("B"), v200, []pubgrub.Term{})
source.AddPackage(pubgrub.MakeName("B"), v210, []pubgrub.Term{})

// Create a root source that requires package A with version range
root := pubgrub.NewRootSource()
root.AddPackage(pubgrub.MakeName("A"), pubgrub.NewVersionSetCondition(range1x))

// Create a solver and solve
solver := pubgrub.NewSolver(root, source)
solution, err := solver.Solve(root.Term())

if err != nil {
	fmt.Printf("Error: %v\n", err)
	return
}

// Print the solution (sorted by name for consistency)
for _, nv := range solution {
	if nv.Name != pubgrub.MakeName("$$root") {
		fmt.Printf("%s = %s\n", nv.Name.Value(), nv.Version)
	}
}

Output:

A = 1.1.0
B = 2.1.0

func NewVersionSetCondition(set VersionSet) *VersionSetCondition

func (vsc *VersionSetCondition) Satisfies(ver Version) bool

func (vsc *VersionSetCondition) String() string

func (vsc *VersionSetCondition) ToVersionSet() VersionSet

type VersionSetConverter ¶ added in v0.2.0

type VersionSetConverter interface {
	// ToVersionSet converts the condition to a VersionSet for algebraic operations.
	ToVersionSet() VersionSet
}

VersionSetConverter is an optional interface that Condition implementations can provide to enable conversion to VersionSet for use with the CDCL solver.

The CDCL solver needs to perform set operations (intersection, union, complement) on version constraints. Conditions that implement this interface can participate in these operations, enabling them to work with unit propagation and conflict resolution.

Built-in conditions (EqualsCondition, VersionSetCondition) are already handled by the solver. Custom condition types should implement this interface to enable solver support.

Example custom condition:

type SemverCaretCondition struct {
    Base *SemanticVersion
}

func (sc SemverCaretCondition) String() string {
    return fmt.Sprintf("^%s", sc.Base)
}

func (sc SemverCaretCondition) Satisfies(ver Version) bool {
    sv, ok := ver.(*SemanticVersion)
    if !ok {
        return false
    }
    return sv.Major == sc.Base.Major &&
           sv.Sort(sc.Base) >= 0 &&
           sv.Major == sc.Base.Major
}

func (sc SemverCaretCondition) ToVersionSet() VersionSet {
    // Convert ^1.2.3 to >=1.2.3 <2.0.0
    upper := &SemanticVersion{Major: sc.Base.Major + 1}
    return NewVersionRangeSet(sc.Base, true, upper, false)
}

// Define a custom caret condition ^1.2.0
base, _ := pubgrub.ParseSemanticVersion("1.2.0")
caretCondition := CaretCondition{Base: base}

// Create a source with several versions
source := &pubgrub.InMemorySource{}
v1_2_0, _ := pubgrub.ParseSemanticVersion("1.2.0")
v1_3_0, _ := pubgrub.ParseSemanticVersion("1.3.0")
v2_0_0, _ := pubgrub.ParseSemanticVersion("2.0.0")

source.AddPackage(pubgrub.MakeName("mylib"), v1_2_0, nil)
source.AddPackage(pubgrub.MakeName("mylib"), v1_3_0, nil)
source.AddPackage(pubgrub.MakeName("mylib"), v2_0_0, nil)

// Use the custom condition
root := pubgrub.NewRootSource()
root.AddPackage(pubgrub.MakeName("mylib"), caretCondition)

// Solve
solver := pubgrub.NewSolver(root, source)
solution, _ := solver.Solve(root.Term())

// The solver picks the highest compatible version (1.3.0, not 2.0.0)
for _, nv := range solution {
	if nv.Name.Value() == "mylib" {
		fmt.Printf("Selected version: %s\n", nv.Version)
	}
}

Output:

Selected version: 1.3.0