Distribution.Solver.Modular.Tree

Documentation

data POption

A package option is a package instance with an optional linking annotation

The modular solver has a number of package goals to solve for, and can only pick a single package version for a single goal. In order to allow to install multiple versions of the same package as part of a single solution the solver uses qualified goals. For example, 0.P and 1.P might both be qualified goals for P, allowing to pick a difference version of package P for 0.P and 1.P.

Linking is an essential part of this story. In addition to picking a specific version for 1.P, the solver can also decide to link 1.P to 0.P (or vice versa). It means that 1.P and 0.P really must be the very same package (and hence must have the same build time configuration, and their dependencies must also be the exact same).

See http://www.well-typed.com/blog/2015/03/qualified-goals/ for details.

Constructors

POption I (Maybe PackagePath)

Instances

Eq POption

Defined in Distribution.Solver.Modular.Tree

Methods

(==) :: POption -> POption -> Bool

(/=) :: POption -> POption -> Bool

Show POption

Defined in Distribution.Solver.Modular.Tree

Methods

showsPrec :: Int -> POption -> ShowS

show :: POption -> String

showList :: [POption] -> ShowS

data Tree d c

Type of the search tree. Inlining the choice nodes for now. Weights on package, flag, and stanza choices control the traversal order.

The tree can hold additional data on Done nodes (type d) and choice nodes (type c). For example, during the final traversal, choice nodes contain the variables that introduced the choices, and Done nodes contain the assignments for all variables.

TODO: The weight type should be changed from [Double] to Double to avoid giving too much weight to preferences that are applied later.

Constructors

PChoice QPN RevDepMap c (WeightedPSQ [Weight] POption (Tree d c))

Choose a version for a package (or choose to link)

FChoice QFN RevDepMap c WeakOrTrivial FlagType Bool (WeightedPSQ [Weight] Bool (Tree d c))

Choose a value for a flag

The Bool is the default value.

SChoice QSN RevDepMap c WeakOrTrivial (WeightedPSQ [Weight] Bool (Tree d c))

Choose whether or not to enable a stanza

GoalChoice RevDepMap (PSQ (Goal QPN) (Tree d c))

Choose which choice to make next

Invariants:

• PSQ should never be empty
• For each choice we additionally record the QGoalReason why we are introducing that goal into tree. Note that most of the time we are working with Tree QGoalReason; in that case, we must have the invariant that the QGoalReason cached in the PChoice, FChoice or SChoice directly below a GoalChoice node must equal the reason recorded on that GoalChoice node.

Done RevDepMap d

We're done -- we found a solution!

Fail ConflictSet FailReason

We failed to find a solution in this path through the tree

data TreeF d c a

Functor for the tree type. a is the type of nodes' children. d and c have the same meaning as in Tree.

Constructors

PChoiceF QPN RevDepMap c (WeightedPSQ [Weight] POption a)

FChoiceF QFN RevDepMap c WeakOrTrivial FlagType Bool (WeightedPSQ [Weight] Bool a)

SChoiceF QSN RevDepMap c WeakOrTrivial (WeightedPSQ [Weight] Bool a)

GoalChoiceF RevDepMap (PSQ (Goal QPN) a)

DoneF RevDepMap d

FailF ConflictSet FailReason

Instances

Functor (TreeF d c)

Defined in Distribution.Solver.Modular.Tree

Methods

fmap :: (a -> b) -> TreeF d c a -> TreeF d c b

(<$) :: a -> TreeF d c b -> TreeF d c a

Foldable (TreeF d c)

Defined in Distribution.Solver.Modular.Tree

Methods

fold :: Monoid m => TreeF d c m -> m

foldMap :: Monoid m => (a -> m) -> TreeF d c a -> m

foldMap' :: Monoid m => (a -> m) -> TreeF d c a -> m

foldr :: (a -> b -> b) -> b -> TreeF d c a -> b

foldr' :: (a -> b -> b) -> b -> TreeF d c a -> b

foldl :: (b -> a -> b) -> b -> TreeF d c a -> b

foldl' :: (b -> a -> b) -> b -> TreeF d c a -> b

foldr1 :: (a -> a -> a) -> TreeF d c a -> a

foldl1 :: (a -> a -> a) -> TreeF d c a -> a

toList :: TreeF d c a -> [a]

null :: TreeF d c a -> Bool

length :: TreeF d c a -> Int

elem :: Eq a => a -> TreeF d c a -> Bool

maximum :: Ord a => TreeF d c a -> a

minimum :: Ord a => TreeF d c a -> a

sum :: Num a => TreeF d c a -> a

product :: Num a => TreeF d c a -> a

Traversable (TreeF d c)

Defined in Distribution.Solver.Modular.Tree

Methods

traverse :: Applicative f => (a -> f b) -> TreeF d c a -> f (TreeF d c b)

sequenceA :: Applicative f => TreeF d c (f a) -> f (TreeF d c a)

mapM :: Monad m => (a -> m b) -> TreeF d c a -> m (TreeF d c b)

sequence :: Monad m => TreeF d c (m a) -> m (TreeF d c a)

type Weight = Double

data FailReason

Constructors

UnsupportedExtension Extension

UnsupportedLanguage Language

MissingPkgconfigPackage PkgconfigName PkgconfigVersionRange

NewPackageDoesNotMatchExistingConstraint ConflictingDep

ConflictingConstraints ConflictingDep ConflictingDep

NewPackageIsMissingRequiredComponent ExposedComponent (DependencyReason QPN)

NewPackageHasPrivateRequiredComponent ExposedComponent (DependencyReason QPN)

NewPackageHasUnbuildableRequiredComponent ExposedComponent (DependencyReason QPN)

PackageRequiresMissingComponent QPN ExposedComponent

PackageRequiresPrivateComponent QPN ExposedComponent

PackageRequiresUnbuildableComponent QPN ExposedComponent

CannotInstall

CannotReinstall

NotExplicit

Shadowed

Broken UnitId

UnknownPackage

GlobalConstraintVersion VR ConstraintSource

GlobalConstraintInstalled ConstraintSource

GlobalConstraintSource ConstraintSource

GlobalConstraintFlag ConstraintSource

ManualFlag

MalformedFlagChoice QFN

MalformedStanzaChoice QSN

EmptyGoalChoice

Backjump

MultipleInstances

DependenciesNotLinked String

CyclicDependencies

UnsupportedSpecVer Ver

Instances

Eq FailReason

Defined in Distribution.Solver.Modular.Tree

Methods

(==) :: FailReason -> FailReason -> Bool

(/=) :: FailReason -> FailReason -> Bool

Show FailReason

Defined in Distribution.Solver.Modular.Tree

Methods

showsPrec :: Int -> FailReason -> ShowS

show :: FailReason -> String

showList :: [FailReason] -> ShowS

data ConflictingDep

Information about a dependency involved in a conflict, for error messages.

Constructors

ConflictingDep (DependencyReason QPN) (PkgComponent QPN) CI

Instances

Eq ConflictingDep

Defined in Distribution.Solver.Modular.Tree

Methods

(==) :: ConflictingDep -> ConflictingDep -> Bool

(/=) :: ConflictingDep -> ConflictingDep -> Bool

Show ConflictingDep

Defined in Distribution.Solver.Modular.Tree

Methods

showsPrec :: Int -> ConflictingDep -> ShowS

show :: ConflictingDep -> String

showList :: [ConflictingDep] -> ShowS

ana :: (a -> TreeF d c a) -> a -> Tree d c

Anamorphism on trees.

cata :: (TreeF d c a -> a) -> Tree d c -> a

Catamorphism on trees.

inn :: TreeF d c (Tree d c) -> Tree d c

innM :: Monad m => TreeF d c (m (Tree d c)) -> m (Tree d c)

para :: (TreeF d c (a, Tree d c) -> a) -> Tree d c -> a

Paramorphism on trees.

trav :: TreeTrav d c a -> Tree d c -> Tree d a

zeroOrOneChoices :: Tree d c -> Bool

Approximates the number of active choices that are available in a node. Note that we count goal choices as having one choice, always.

active :: Tree d c -> Bool

Determines whether a tree is active, i.e., isn't a failure node.

type TreeTrav d c a = TreeF d c (Tree d a) -> TreeF d a (Tree d a)

type EndoTreeTrav d c = TreeTrav d c c