cabal-install-solver
Safe HaskellSafe-Inferred
LanguageHaskell2010

Distribution.Solver.Modular.Tree

Synopsis

Documentation

data POption Source #

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

Instances details
Show POption Source # 
Instance details

Defined in Distribution.Solver.Modular.Tree

Methods

showsPrec :: Int -> POption -> ShowS #

show :: POption -> String #

showList :: [POption] -> ShowS #

Eq POption Source # 
Instance details

Defined in Distribution.Solver.Modular.Tree

Methods

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

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

data Tree d c Source #

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 Source #

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

Instances details
Foldable (TreeF d c) Source # 
Instance details

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) Source # 
Instance details

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) #

Functor (TreeF d c) Source # 
Instance details

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 #

type Weight = Double Source #

data FailReason Source #

Constructors

UnsupportedExtension Extension 
UnsupportedLanguage Language 
MissingPkgconfigPackage PkgconfigName PkgconfigVersionRange 
MissingPkgconfigProgram 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 
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

Instances details
Show FailReason Source # 
Instance details

Defined in Distribution.Solver.Modular.Tree

Methods

showsPrec :: Int -> FailReason -> ShowS #

show :: FailReason -> String #

showList :: [FailReason] -> ShowS #

Eq FailReason Source # 
Instance details

Defined in Distribution.Solver.Modular.Tree

Methods

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

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

data ConflictingDep Source #

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

Constructors

ConflictingDep (DependencyReason QPN) (PkgComponent QPN) CI 

Instances

Instances details
Show ConflictingDep Source # 
Instance details

Defined in Distribution.Solver.Modular.Tree

Methods

showsPrec :: Int -> ConflictingDep -> ShowS #

show :: ConflictingDep -> String #

showList :: [ConflictingDep] -> ShowS #

Eq ConflictingDep Source # 
Instance details

Defined in Distribution.Solver.Modular.Tree

Methods

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

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

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

Anamorphism on trees.

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

Catamorphism on trees.

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

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

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

Paramorphism on trees.

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

zeroOrOneChoices :: Tree d c -> Bool Source #

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 Source #

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) Source #

type EndoTreeTrav d c = TreeTrav d c c Source #