solver

package
v0.35.3-geaaru Latest Latest
Warning

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

 Go to latest Published: Apr 3, 2023 License: GPL-3.0 Imports: 22 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	SingleCoreSimple = 0
	SingleCoreV2     = 1
)
View Source 
const (
	NoAction      = 0
	Solved        = iota
	NoSolution    = iota
	Going         = iota
	ActionRemoved = iota
	ActionAdded   = iota

	DoNoop = false

	ActionDomains = 3 // Bump it if you increase the number of actions

	DefaultMaxAttempts     = 9000
	DefaultLearningRate    = 0.7
	DefaultDiscount        = 1.0
	DefaultInitialObserved = 999999

	QLearningResolverType = "qlearning"
)
View Source 
const (
	SolverV2ResolverType = "solverv2"
)

Variables

View Source 
var AvailableResolvers = strings.Join([]string{
	QLearningResolverType,
	SolverV2ResolverType,
}, " ")

Functions

This section is empty.

Types

type ActionType 

type ActionType int

type Choice 

type Choice struct {
	Package string     `json:"pack"`
	Action  ActionType `json:"action"`
}

Choice implements qlearning.Action for a package choice for removal from wanted targets

func ChoiceFromString 

func ChoiceFromString(s string) (*Choice, error)

func (*Choice) Apply 

func (choice *Choice) Apply(state qlearning.State) qlearning.State

Apply updates the state of the solver for the package choice.

func (*Choice) String 

func (choice *Choice) String() string

String returns the character for the current action.

type Explainer 

type Explainer struct{}

func (*Explainer) Solve 

func (*Explainer) Solve(f bf.Formula, s PackageSolver) (PackagesAssertions, error)

Solve tries to find the MUS (minimum unsat) formula from the original problem. it returns an error with the decoded dimacs

type FormulasGate 

type FormulasGate struct {
	Formulas []bf.Formula
}

type Options 

type Options struct {
	Type        SolverType `yaml:"type,omitempty"`
	Concurrency int        `yaml:"concurrency,omitempty"`
}

func DecodeImplementation 

func DecodeImplementation(i string) (ans Options)

func (Options) Resolver 

func (opts Options) Resolver() PackageResolver

func (Options) ResolverIsSet 

func (opts Options) ResolverIsSet() bool

type PackageAssert 

type PackageAssert struct {
	Package *pkg.DefaultPackage
	Value   bool
	Hash    PackageHash
}

PackageAssert represent a package assertion. It is composed of a Package and a Value which is indicating the absence or not of the associated package state.

func (*PackageAssert) Explain 

func (a *PackageAssert) Explain()

func (*PackageAssert) String 

func (a *PackageAssert) String() string

func (*PackageAssert) ToString 

func (a *PackageAssert) ToString() string

type PackageHash 

type PackageHash struct {
	BuildHash   string
	PackageHash string
}

type PackageResolver 

type PackageResolver interface {
	Solve(bf.Formula, PackageSolver) (PackagesAssertions, error)
}

PackageResolver assists PackageSolver on unsat cases

func NewQLearningResolver 

func NewQLearningResolver(LearningRate, Discount float32, MaxAttempts, initialObservedDelta int) PackageResolver

Defaults LearningRate 0.7, Discount 1.0

func SimpleQLearningSolver 

func SimpleQLearningSolver() PackageResolver

type PackageSolver 

type PackageSolver interface {
	SetDefinitionDatabase(pkg.PackageDatabase)
	Install(p pkg.Packages) (PackagesAssertions, error)
	RelaxedInstall(p pkg.Packages) (PackagesAssertions, error)

	Uninstall(checkconflicts, full bool, candidate ...pkg.Package) (pkg.Packages, error)
	ConflictsWithInstalled(p pkg.Package) (bool, error)
	ConflictsWith(p pkg.Package, ls pkg.Packages) (bool, error)
	Conflicts(pack pkg.Package, lsp pkg.Packages) (bool, error)

	World() pkg.Packages
	Upgrade(checkconflicts, full bool) (pkg.Packages, PackagesAssertions, error)

	UpgradeUniverse(dropremoved bool) (pkg.Packages, PackagesAssertions, error)
	UninstallUniverse(toremove pkg.Packages) (pkg.Packages, error)

	SetResolver(PackageResolver)

	Solve() (PackagesAssertions, error)

	GetType() SolverType
}

PackageSolver is an interface to a generic package solving algorithm

func NewResolver 

func NewResolver(t Options, installed pkg.PackageDatabase, definitiondb pkg.PackageDatabase, solverdb pkg.PackageDatabase, re PackageResolver) PackageSolver

NewResolver accepts as argument two lists of packages, the first is the initial set, the second represent all the known packages. Using constructors as in the future we foresee warmups for hot-restore solver cache

func NewSolver 

func NewSolver(t Options, installed pkg.PackageDatabase, definitiondb pkg.PackageDatabase, solverdb pkg.PackageDatabase) PackageSolver

NewSolver accepts as argument two lists of packages, the first is the initial set, the second represent all the known packages.

type PackagesAssertions 

type PackagesAssertions []PackageAssert

func DecodeModel 

func DecodeModel(model map[string]bool, db pkg.PackageDatabase) (PackagesAssertions, error)

DecodeModel decodes a model from the SAT solver to package assertions (PackageAssert)

func (PackagesAssertions) AssertionHash 

func (assertions PackagesAssertions) AssertionHash() string

func (PackagesAssertions) Cut 

func (assertions PackagesAssertions) Cut(p pkg.Package) PackagesAssertions

Cut returns an assertion list of installed (filter by Value) "cutted" until the package is found (included)

func (PackagesAssertions) Drop 

func (assertions PackagesAssertions) Drop(p pkg.Package) PackagesAssertions

func (PackagesAssertions) EnsureOrder 

func (assertions PackagesAssertions) EnsureOrder() PackagesAssertions

func (PackagesAssertions) Explain 

func (assertions PackagesAssertions) Explain() string

func (PackagesAssertions) HashFrom 

func (assertions PackagesAssertions) HashFrom(p pkg.Package) string

HashFrom computes the assertion hash From a given package. It drops it from the assertions and checks it's not the only one. if it's unique it marks it specially - so the hash which is generated is unique for the selected package

func (PackagesAssertions) Len 

func (a PackagesAssertions) Len() int

func (PackagesAssertions) Less 

func (a PackagesAssertions) Less(i, j int) bool

func (PackagesAssertions) Mark 

func (assertions PackagesAssertions) Mark(p pkg.Package) PackagesAssertions

Mark returns a new assertion with the package marked

func (PackagesAssertions) Order 

func (assertions PackagesAssertions) Order(definitiondb pkg.PackageDatabase, fingerprint string) (PackagesAssertions, error)

func (PackagesAssertions) SaltedAssertionHash 

func (assertions PackagesAssertions) SaltedAssertionHash(salts map[string]string) string

func (PackagesAssertions) SaltedHashFrom 

func (assertions PackagesAssertions) SaltedHashFrom(p pkg.Package, salts map[string]string) string

func (PackagesAssertions) Search 

func (assertions PackagesAssertions) Search(f string) *PackageAssert

func (PackagesAssertions) SearchByName 

func (assertions PackagesAssertions) SearchByName(f string) *PackageAssert

func (PackagesAssertions) Swap 

func (a PackagesAssertions) Swap(i, j int)

func (PackagesAssertions) ToDB 

func (assertions PackagesAssertions) ToDB() pkg.PackageDatabase

func (PackagesAssertions) TrueLen 

func (a PackagesAssertions) TrueLen() int

type QLearningResolver 

type QLearningResolver struct {
	Attempts int

	ToAttempt int

	Attempted map[string]bool

	Solver  PackageSolver
	Formula bf.Formula

	Targets pkg.Packages
	Current pkg.Packages

	Agent *qlearning.SimpleAgent
	// contains filtered or unexported fields
}

func (*QLearningResolver) Choose 

func (resolver *QLearningResolver) Choose(c Choice) bool

Choose applies a pack attempt, returning true if the formula returns sat.

Choose updates the resolver's state.

func (*QLearningResolver) IsComplete 

func (resolver *QLearningResolver) IsComplete() int

Returns the current state.

func (*QLearningResolver) Log 

func (resolver *QLearningResolver) Log(msg string, args ...interface{})

Log is a wrapper of fmt.Printf. If Game.debug is true, Log will print to stdout.

func (*QLearningResolver) Next 

func (resolver *QLearningResolver) Next() []qlearning.Action

Next creates a new slice of qlearning.Action instances. A possible action is created for each package that could be removed from the formula's target

func (*QLearningResolver) Reward 

func (resolver *QLearningResolver) Reward(action *qlearning.StateAction) float32

Reward returns a score for a given qlearning.StateAction. Reward is a member of the qlearning.Rewarder interface. If the choice will make sat the formula, a positive score is returned. Otherwise, a static -1000 is returned.

func (*QLearningResolver) Solve 

func (resolver *QLearningResolver) Solve(f bf.Formula, s PackageSolver) (PackagesAssertions, error)

func (*QLearningResolver) String 

func (resolver *QLearningResolver) String() string

String returns a consistent hash for the current env state to be used in a qlearning.Agent.

func (*QLearningResolver) Try 

func (resolver *QLearningResolver) Try(c Choice) error

type Solver 

type Solver struct {
	DefinitionDatabase pkg.PackageDatabase
	SolverDatabase     pkg.PackageDatabase
	Wanted             pkg.Packages
	InstalledDatabase  pkg.PackageDatabase

	Resolver PackageResolver
}

Solver is the default solver for luet

func (*Solver) BuildFormula 

func (s *Solver) BuildFormula() (bf.Formula, error)

BuildFormula builds the main solving formula that is evaluated by the sat solver.

func (*Solver) BuildInstalled 

func (s *Solver) BuildInstalled() (bf.Formula, error)

func (*Solver) BuildPartialWorld 

func (s *Solver) BuildPartialWorld(includeInstalled bool) (bf.Formula, error)

BuildWorld builds the formula which olds the requirements from the package definitions which are available (global state)

func (*Solver) BuildWorld 

func (s *Solver) BuildWorld(includeInstalled bool) (bf.Formula, error)

BuildWorld builds the formula which olds the requirements from the package definitions which are available (global state)

func (*Solver) Conflicts 

func (s *Solver) Conflicts(pack pkg.Package, lsp pkg.Packages) (bool, error)

Conflicts acts like ConflictsWith, but uses package's reverse dependencies to determine if it conflicts with the given set

func (*Solver) ConflictsWith 

func (s *Solver) ConflictsWith(pack pkg.Package, lsp pkg.Packages) (bool, error)

ConflictsWith return true if a package is part of the requirement set of a list of package return false otherwise (and thus it is NOT relevant to the given list)

func (*Solver) ConflictsWithInstalled 

func (s *Solver) ConflictsWithInstalled(p pkg.Package) (bool, error)

func (*Solver) GetType 

func (s *Solver) GetType() SolverType

func (*Solver) Install 

func (s *Solver) Install(c pkg.Packages) (PackagesAssertions, error)

Install returns the assertions necessary in order to install the packages in a system. It calculates the best result possible, trying to maximize new packages.

func (*Solver) Installed 

func (s *Solver) Installed() pkg.Packages

func (*Solver) RelaxedInstall 

func (s *Solver) RelaxedInstall(c pkg.Packages) (PackagesAssertions, error)

Install given a list of packages, returns package assertions to indicate the packages that must be installed in the system in order to statisfy all the constraints

func (*Solver) SetDefinitionDatabase 

func (s *Solver) SetDefinitionDatabase(db pkg.PackageDatabase)

SetDefinitionDatabase is a setter for the definition Database

func (*Solver) SetResolver 

func (s *Solver) SetResolver(r PackageResolver)

SetResolver is a setter for the unsat resolver backend

func (*Solver) Solve 

func (s *Solver) Solve() (PackagesAssertions, error)

Solve builds the formula given the current state and returns package assertions

func (*Solver) Uninstall 

func (s *Solver) Uninstall(checkconflicts, full bool, packs ...pkg.Package) (pkg.Packages, error)

Uninstall takes a candidate package and return a list of packages that would be removed in order to purge the candidate. Returns error if unsat.

func (*Solver) UninstallUniverse 

func (s *Solver) UninstallUniverse(toremove pkg.Packages) (pkg.Packages, error)

UninstallUniverse takes a list of candidate package and return a list of packages that would be removed in order to purge the candidate. Uses the solver to check constraints and nothing else

It can be compared to the counterpart Uninstall as this method acts like a uninstall --full it removes all the packages and its deps. taking also in consideration other packages that might have revdeps

func (*Solver) Upgrade 

func (s *Solver) Upgrade(checkconflicts, full bool) (pkg.Packages, PackagesAssertions, error)

func (*Solver) UpgradeUniverse 

func (s *Solver) UpgradeUniverse(dropremoved bool) (pkg.Packages, PackagesAssertions, error)

UpgradeUniverse mark packages for removal and returns a solution. It considers the Universe db as authoritative See also on the subject: https://arxiv.org/pdf/1007.1021.pdf

func (*Solver) World 

func (s *Solver) World() pkg.Packages

type SolverType 

type SolverType int

type SolverV2 

type SolverV2 struct {
	*Solver
}

func NewSolverV2 

func NewSolverV2(t Options,
	installed, definitiondb, solverdb pkg.PackageDatabase,
	re PackageResolver) *SolverV2

func (*SolverV2) BuildFormula 

func (s *SolverV2) BuildFormula() (*bf.Formula, error)

BuildFormula builds the main solving formula that is evaluated by the sat solver.

func (*SolverV2) BuildInstalled 

func (s *SolverV2) BuildInstalled(ff *FormulasGate) error

func (*SolverV2) BuildWorld 

func (s *SolverV2) BuildWorld(includeInstalled bool) (*bf.Formula, error)

BuildWorld builds the formula which olds the requirements from the package definitions which are available (global state)

func (*SolverV2) GetType 

func (s *SolverV2) GetType() SolverType

func (*SolverV2) Install 

func (s *SolverV2) Install(c pkg.Packages) (PackagesAssertions, error)

Install returns the assertions necessary in order to install the packages in a system. It calculates the best result possible, trying to maximize new packages.

func (*SolverV2) RelaxedInstall 

func (s *SolverV2) RelaxedInstall(c pkg.Packages) (PackagesAssertions, error)

func (*SolverV2) Solve 

func (s *SolverV2) Solve() (PackagesAssertions, error)

Solve builds the formula given the current state and returns package assertions

func (*SolverV2) Uninstall 

func (s *SolverV2) Uninstall(checkconflicts, full bool,
	packs ...pkg.Package) (pkg.Packages, error)

Uninstall takes a candidate package and return a list of packages that would be removed in order to purge the candidate. Returns error if unsat.

func (*SolverV2) Upgrade 

func (s *SolverV2) Upgrade(checkconflicts, full bool) (pkg.Packages, PackagesAssertions, error)

type UpgradeResponse 

type UpgradeResponse struct {
	ToUninstall    *pkg.Packages
	ToInstall      *pkg.Packages
	InstalledCopy  *pkg.PackageDatabase
	PacksToUpgrade *[]pkg.Package
}

func NewUpgradeResponse 

func NewUpgradeResponse() *UpgradeResponse

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.