solver

Documentation

Overview

Solver provides operations on packages: install, remove, upgrade, check integrity and others.

A package is an object comprised of a unique key (tentative release name, version, namespace, chart name), and digested information about the chart that it relates to (dependency relations, chart and repo URL, current and desired state..).

To perform a package operation, for example, "install packageA", we:

1. Build a database of all packages in the world, which contains: - Packages deployed in cluster (releases). - Packages in the known repositories. - Requested changes to packages (to install, to remove, to upgrade).

   The gophersat/solver MAXSAT/Pseudo-Boolean solver operates over unique strings: in our case, the package string fingerprint, created from its unique key.

   The database contains information on a package current state (unknown, installed, removed) and desired state (unknown, installed, removed). The database can also be queried to obtain a list of packages that differ only in the version.

   Adding packages to the database can happen in any order (e.g: first toModify, later releases, and at last repos). This means that db.Add() will intelligently merge new information into the package in the db, if the package is already present.

2. Iterate through the package database and create pseudo-boolean constraints for the package fingerprint: - If package needs to be installed or not - If it depends on another package(s) - If it conflicts with other similar packages that differ with it only in version). - If we want to minimize or maximize the distance between present version and wanted version (upgrade to major versions, never upgrade, etc)

3. Find a solution to the SAT dependency problem if exists, or the contradiction if there's no solution. The result is a list of tuple of: - Fingerprints (each corresponding with a package), and - Resulting state of the package (if the package should be present in the system or not).

4. We then iterate through the result list, separating the packages into different sets by checking their current, desired, and resulting state: unchanged packages, packages to install, packages to remove.

Index

• func CalculateSemverDistanceToZero(semversion string) (distance int)
• func PrintPkgTree(tr *PkgTree) (output string)
• type OutputMode
• type PkgDB
  • func CreatePkgDBInstance() *PkgDB
  • func GetPkgdDBInstance() *PkgDB
  • func (pkgdb *PkgDB) Add(p *pkg.Pkg)
  • func (pkgdb *PkgDB) DebugPrintDB(logger log.Logger)
  • func (pkgdb *PkgDB) GetMapOfVersionsByBaseFingerPrint(basefp string) map[string]string
  • func (pkgdb *PkgDB) GetOrderedPackageFingerprintsThatDifferOnVersionByPackage(p *pkg.Pkg) (fps []string, weights []int)
  • func (pkgdb *PkgDB) GetPackageByFingerprint(fp string) *pkg.Pkg
• type PkgResultSet
• type PkgTree
• type Solver
  • func New(strategy SolverStrategy, logger log.Logger) (s *Solver)
  • func (s *Solver) BuildConstraints(p *pkg.Pkg) (constrs []maxsat.Constr)
  • func (s *Solver) BuildWorldMock(pkgs []*pkg.Pkg)
  • func (s *Solver) FormatOutput(t OutputMode) (output string)
  • func (s *Solver) GeneratePkgSets(wantedPkg *pkg.Pkg)
  • func (s *Solver) IsSAT() bool
  • func (s *Solver) Solve(wantedPkg *pkg.Pkg)
  • func (s *Solver) SortPkgSets()
• type SolverStrategy

Examples

• Solver

Functions

func CalculateSemverDistanceToZero

func CalculateSemverDistanceToZero(semversion string) (distance int)

func PrintPkgTree

func PrintPkgTree(tr *PkgTree) (output string)

PrintPkgTree returns an ascii tree of the corresponding tree, taking care of printing the correct pipe delimiters and tabulation.

Types

type OutputMode

type OutputMode int

const (
	JSON OutputMode = iota
	YAML
	Table
)

type PkgDB

type PkgDB struct {
	*sync.Mutex
	// contains filtered or unexported fields
}

PkgDB implements a database of 1 key (packages' fingerprints) and 1 value (*pkg.Pkg). Each package contains also a table of base fingerprints for packages that are the similar to the current package and only differ in the version.

If a package is already present in the database, when adding, it would get merged with the existent entry in a way to complete unknown info of that package.

var PkgDBInstance *PkgDB

func CreatePkgDBInstance

func CreatePkgDBInstance() *PkgDB

func GetPkgdDBInstance

func GetPkgdDBInstance() *PkgDB

func (*PkgDB) Add

func (pkgdb *PkgDB) Add(p *pkg.Pkg)

Add adds a package to the database, and if a package was already present in the database, it makes sure to update it, in a way that only unknown info to that package is added.

func (*PkgDB) DebugPrintDB

func (pkgdb *PkgDB) DebugPrintDB(logger log.Logger)

func (*PkgDB) GetMapOfVersionsByBaseFingerPrint

func (pkgdb *PkgDB) GetMapOfVersionsByBaseFingerPrint(basefp string) map[string]string

func (*PkgDB) GetOrderedPackageFingerprintsThatDifferOnVersionByPackage

func (pkgdb *PkgDB) GetOrderedPackageFingerprintsThatDifferOnVersionByPackage(p *pkg.Pkg) (fps []string, weights []int)

func (*PkgDB) GetPackageByFingerprint

func (pkgdb *PkgDB) GetPackageByFingerprint(fp string) *pkg.Pkg

type PkgResultSet

type PkgResultSet struct {
	PresentUnchanged []*pkg.Pkg
	ToInstall        *PkgTree
	ToRemove         []*pkg.Pkg
	Status           string
	Inconsistencies  []string
}

PkgResultSet contains the status outcome of solving, and the different sets of packages derived from the outcome. It will be marshalled into Yaml and Json.

type PkgTree

type PkgTree struct {
	Node      *pkg.Pkg
	Relations []*PkgTree
}

PkgTree is a polytree (directed, acyclic graph) of packages. Used for storing the tree of packages to be installed.

type Solver

type Solver struct {
	PkgDB        *PkgDB       // DB containing packages
	PkgResultSet PkgResultSet // outcome of sat solving
	Strategy     SolverStrategy
	// contains filtered or unexported fields
}

Solver performs SAT solving of dependency problems. It codifies the state of the world into packages, saved into a package database. It gets created with a specific SolverStrategy, and contains the results in PkgResultSet.

Example

wantedPkg := pkg.NewPkgMock("wantedbaz", "1.0.0", "wantedbazns",
	// dependency relations of wantedbaz:
	[]*pkg.PkgRel{{
		ReleaseName: "myawesomedep",
		Namespace:   "myawesomedeptargetns",
		SemverRange: "~0.1.0",
		ChartName:   "myawesomedep",
	}},
	nil, pkg.Unknown, pkg.Present)

// Create a slice of mock packages:
pkgs := []*pkg.Pkg{
	pkg.NewPkgMock("notinstalledbar", "1.0.0", "notinstalledtargetns", nil, nil, pkg.Unknown, pkg.Unknown),
	pkg.NewPkgMock("notinstalledbar", "2.0.0", "notinstalledtargetns", nil, nil, pkg.Unknown, pkg.Unknown),
	pkg.NewPkgMock("myawesomedep", "0.1.100", "myawesomedeptargetns", nil, nil, pkg.Unknown, pkg.Unknown),
	// package to modify (install, in this case, see pkg.DesiredState set to Present):
	wantedPkg,
	// releases already in the cluster:
	pkg.NewPkgMock("installedfoo", "1.0.0", "installedns", nil, nil, pkg.Present, pkg.Unknown),
}

// create our own Logger that satisfies impl/cli.Logger, but with a buffer for tests
buf := new(bytes.Buffer)
logger := logcli.NewStandard()
logger.InfoOut = buf
logger.WarnOut = buf
logger.ErrorOut = buf
logger.DebugOut = buf
log.Current = logger
// logger.Level = log.DebugLevel

s := New(InstallOne, logger)

// Fill the DB with our mock packages:
s.BuildWorldMock(pkgs)
s.PkgDB.DebugPrintDB(logger)

// Call the solver
s.Solve(wantedPkg)

fmt.Println(s.FormatOutput(YAML))

Output:

presentunchanged:
- releasename: installedfoo
  version: 1.0.0
  namespace: installedns
  chartname: installedfoo
  dependsrel: []
  dependsoptionalrel: []
  repository: ourrepo
  parentchartpath: ""
  currentstate: 1
  desiredstate: 0
  pinnedver: 0
toinstall:
  node:
    releasename: wantedbaz
    version: 1.0.0
    namespace: wantedbazns
    chartname: wantedbaz
    dependsrel:
    - releasename: myawesomedep
      namespace: myawesomedeptargetns
      semverrange: ~0.1.0
      chartname: myawesomedep
    dependsoptionalrel: []
    repository: ourrepo
    parentchartpath: ""
    currentstate: 0
    desiredstate: 1
    pinnedver: 0
  relations:
  - node:
      releasename: myawesomedep
      version: 0.1.100
      namespace: myawesomedeptargetns
      chartname: myawesomedep
      dependsrel: []
      dependsoptionalrel: []
      repository: ourrepo
      parentchartpath: ""
      currentstate: 0
      desiredstate: 0
      pinnedver: 0
    relations: []
toremove: []
status: SAT
inconsistencies: []

func New

func New(strategy SolverStrategy, logger log.Logger) (s *Solver)

New creates a new Solver, initializing its database.

func (*Solver) BuildConstraints

func (s *Solver) BuildConstraints(p *pkg.Pkg) (constrs []maxsat.Constr)

BuildConstraints generates all constraints for package p

func (*Solver) BuildWorldMock

func (s *Solver) BuildWorldMock(pkgs []*pkg.Pkg)

BuildWorldMock fills the database with pkgs instead of releases, charts from repositories, and so. Useful for testing.

func (*Solver) FormatOutput

func (s *Solver) FormatOutput(t OutputMode) (output string)

func (*Solver) GeneratePkgSets

func (s *Solver) GeneratePkgSets(wantedPkg *pkg.Pkg)

GeneratePkgSets obtains back the sets of packages from IDs.

func (*Solver) IsSAT

func (s *Solver) IsSAT() bool

func (*Solver) Solve

func (s *Solver) Solve(wantedPkg *pkg.Pkg)

func (*Solver) SortPkgSets

func (s *Solver) SortPkgSets()

type SolverStrategy

type SolverStrategy int

const (
	InstallOne SolverStrategy = iota

	UpgradeOne
)