{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE TypeFamilies #-}

-----------------------------------------------------------------------------

-----------------------------------------------------------------------------

-- |
-- Module      :  Distribution.Client.SolverInstallPlan
-- Copyright   :  (c) Duncan Coutts 2008
-- License     :  BSD-like
--
-- Maintainer  :  duncan@community.haskell.org
-- Stability   :  provisional
-- Portability :  portable
--
-- The 'SolverInstallPlan' is the graph of packages produced by the
-- dependency solver, and specifies at the package-granularity what
-- things are going to be installed.  To put it another way: the
-- dependency solver produces a 'SolverInstallPlan', which is then
-- consumed by various other parts of Cabal.
module Distribution.Client.SolverInstallPlan
  ( SolverInstallPlan (..)
  , SolverPlanPackage
  , ResolverPackage (..)

    -- * Operations on 'SolverInstallPlan's
  , new
  , toList
  , toMap
  , remove
  , showPlanIndex
  , showInstallPlan

    -- * Checking validity of plans
  , valid
  , closed
  , consistent
  , acyclic

    -- ** Details on invalid plans
  , SolverPlanProblem (..)
  , showPlanProblem
  , problems

    -- ** Querying the install plan
  , dependencyClosure
  , reverseDependencyClosure
  , topologicalOrder
  , reverseTopologicalOrder
  ) where

import Distribution.Client.Compat.Prelude hiding (toList)
import Prelude ()

import Distribution.Package
  ( HasUnitId (..)
  , Package (..)
  , PackageId
  , PackageIdentifier (..)
  , PackageName
  , packageName
  , packageVersion
  )
import qualified Distribution.Solver.Types.ComponentDeps as CD
import Distribution.Types.Flag (nullFlagAssignment)

import Distribution.Client.Types
  ( UnresolvedPkgLoc
  )
import Distribution.Version
  ( Version
  )

import Distribution.Solver.Types.ResolverPackage
import Distribution.Solver.Types.Settings
import Distribution.Solver.Types.SolverId
import Distribution.Solver.Types.SolverPackage

import Data.Array ((!))
import qualified Data.Foldable as Foldable
import qualified Data.Graph as OldGraph
import qualified Data.Map as Map
import Distribution.Compat.Graph (Graph, IsNode (..))
import qualified Distribution.Compat.Graph as Graph

type SolverPlanPackage = ResolverPackage UnresolvedPkgLoc

type SolverPlanIndex = Graph SolverPlanPackage

data SolverInstallPlan = SolverInstallPlan
  { SolverInstallPlan -> SolverPlanIndex
planIndex :: !SolverPlanIndex
  , SolverInstallPlan -> IndependentGoals
planIndepGoals :: !IndependentGoals
  }
  deriving ((forall x. SolverInstallPlan -> Rep SolverInstallPlan x)
-> (forall x. Rep SolverInstallPlan x -> SolverInstallPlan)
-> Generic SolverInstallPlan
forall x. Rep SolverInstallPlan x -> SolverInstallPlan
forall x. SolverInstallPlan -> Rep SolverInstallPlan x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cfrom :: forall x. SolverInstallPlan -> Rep SolverInstallPlan x
from :: forall x. SolverInstallPlan -> Rep SolverInstallPlan x
$cto :: forall x. Rep SolverInstallPlan x -> SolverInstallPlan
to :: forall x. Rep SolverInstallPlan x -> SolverInstallPlan
Generic)

{-
-- | Much like 'planPkgIdOf', but mapping back to full packages.
planPkgOf :: SolverInstallPlan
          -> Graph.Vertex
          -> SolverPlanPackage
planPkgOf plan v =
    case Graph.lookupKey (planIndex plan)
                         (planPkgIdOf plan v) of
      Just pkg -> pkg
      Nothing  -> error "InstallPlan: internal error: planPkgOf lookup failed"
-}

instance Binary SolverInstallPlan
instance Structured SolverInstallPlan

showPlanIndex :: [SolverPlanPackage] -> String
showPlanIndex :: [SolverPlanPackage] -> FilePath
showPlanIndex = FilePath -> [FilePath] -> FilePath
forall a. [a] -> [[a]] -> [a]
intercalate FilePath
"\n" ([FilePath] -> FilePath)
-> ([SolverPlanPackage] -> [FilePath])
-> [SolverPlanPackage]
-> FilePath
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (SolverPlanPackage -> FilePath)
-> [SolverPlanPackage] -> [FilePath]
forall a b. (a -> b) -> [a] -> [b]
map SolverPlanPackage -> FilePath
showPlanPackage

showInstallPlan :: SolverInstallPlan -> String
showInstallPlan :: SolverInstallPlan -> FilePath
showInstallPlan = [SolverPlanPackage] -> FilePath
showPlanIndex ([SolverPlanPackage] -> FilePath)
-> (SolverInstallPlan -> [SolverPlanPackage])
-> SolverInstallPlan
-> FilePath
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SolverInstallPlan -> [SolverPlanPackage]
toList

showPlanPackage :: SolverPlanPackage -> String
showPlanPackage :: SolverPlanPackage -> FilePath
showPlanPackage (PreExisting InstSolverPackage
ipkg) =
  FilePath
"PreExisting "
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ PackageIdentifier -> FilePath
forall a. Pretty a => a -> FilePath
prettyShow (InstSolverPackage -> PackageIdentifier
forall pkg. Package pkg => pkg -> PackageIdentifier
packageId InstSolverPackage
ipkg)
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ FilePath
" ("
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ UnitId -> FilePath
forall a. Pretty a => a -> FilePath
prettyShow (InstSolverPackage -> UnitId
forall pkg. HasUnitId pkg => pkg -> UnitId
installedUnitId InstSolverPackage
ipkg)
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ FilePath
")"
showPlanPackage (Configured SolverPackage UnresolvedPkgLoc
spkg) =
  FilePath
"Configured " FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ PackageIdentifier -> FilePath
forall a. Pretty a => a -> FilePath
prettyShow (SolverPackage UnresolvedPkgLoc -> PackageIdentifier
forall pkg. Package pkg => pkg -> PackageIdentifier
packageId SolverPackage UnresolvedPkgLoc
spkg) FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ FilePath
flags FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ FilePath
comps
  where
    flags :: FilePath
flags
      | FlagAssignment -> Bool
nullFlagAssignment FlagAssignment
fa = FilePath
""
      | Bool
otherwise = FilePath
" " FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ FlagAssignment -> FilePath
forall a. Pretty a => a -> FilePath
prettyShow (SolverPackage UnresolvedPkgLoc -> FlagAssignment
forall loc. SolverPackage loc -> FlagAssignment
solverPkgFlags SolverPackage UnresolvedPkgLoc
spkg)
      where
        fa :: FlagAssignment
fa = SolverPackage UnresolvedPkgLoc -> FlagAssignment
forall loc. SolverPackage loc -> FlagAssignment
solverPkgFlags SolverPackage UnresolvedPkgLoc
spkg

    comps :: FilePath
comps
      | Set Component -> Bool
forall a. Set a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null Set Component
deps = FilePath
""
      | Bool
otherwise = FilePath
" " FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ [FilePath] -> FilePath
unwords ((Component -> FilePath) -> [Component] -> [FilePath]
forall a b. (a -> b) -> [a] -> [b]
map Component -> FilePath
forall a. Pretty a => a -> FilePath
prettyShow ([Component] -> [FilePath]) -> [Component] -> [FilePath]
forall a b. (a -> b) -> a -> b
$ Set Component -> [Component]
forall a. Set a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
Foldable.toList Set Component
deps)
      where
        deps :: Set CD.Component
        deps :: Set Component
deps =
          ComponentDeps [SolverId] -> Set Component
forall a. ComponentDeps a -> Set Component
CD.components (SolverPackage UnresolvedPkgLoc -> ComponentDeps [SolverId]
forall loc. SolverPackage loc -> ComponentDeps [SolverId]
solverPkgLibDeps SolverPackage UnresolvedPkgLoc
spkg)
            Set Component -> Set Component -> Set Component
forall a. Semigroup a => a -> a -> a
<> ComponentDeps [SolverId] -> Set Component
forall a. ComponentDeps a -> Set Component
CD.components (SolverPackage UnresolvedPkgLoc -> ComponentDeps [SolverId]
forall loc. SolverPackage loc -> ComponentDeps [SolverId]
solverPkgExeDeps SolverPackage UnresolvedPkgLoc
spkg)

-- | Build an installation plan from a valid set of resolved packages.
new
  :: IndependentGoals
  -> SolverPlanIndex
  -> Either [SolverPlanProblem] SolverInstallPlan
new :: IndependentGoals
-> SolverPlanIndex -> Either [SolverPlanProblem] SolverInstallPlan
new IndependentGoals
indepGoals SolverPlanIndex
index =
  case IndependentGoals -> SolverPlanIndex -> [SolverPlanProblem]
problems IndependentGoals
indepGoals SolverPlanIndex
index of
    [] -> SolverInstallPlan -> Either [SolverPlanProblem] SolverInstallPlan
forall a b. b -> Either a b
Right (SolverPlanIndex -> IndependentGoals -> SolverInstallPlan
SolverInstallPlan SolverPlanIndex
index IndependentGoals
indepGoals)
    [SolverPlanProblem]
probs -> [SolverPlanProblem] -> Either [SolverPlanProblem] SolverInstallPlan
forall a b. a -> Either a b
Left [SolverPlanProblem]
probs

toList :: SolverInstallPlan -> [SolverPlanPackage]
toList :: SolverInstallPlan -> [SolverPlanPackage]
toList = SolverPlanIndex -> [SolverPlanPackage]
forall a. Graph a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
Foldable.toList (SolverPlanIndex -> [SolverPlanPackage])
-> (SolverInstallPlan -> SolverPlanIndex)
-> SolverInstallPlan
-> [SolverPlanPackage]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SolverInstallPlan -> SolverPlanIndex
planIndex

toMap :: SolverInstallPlan -> Map SolverId SolverPlanPackage
toMap :: SolverInstallPlan -> Map SolverId SolverPlanPackage
toMap = SolverPlanIndex -> Map (Key SolverPlanPackage) SolverPlanPackage
SolverPlanIndex -> Map SolverId SolverPlanPackage
forall a. Graph a -> Map (Key a) a
Graph.toMap (SolverPlanIndex -> Map SolverId SolverPlanPackage)
-> (SolverInstallPlan -> SolverPlanIndex)
-> SolverInstallPlan
-> Map SolverId SolverPlanPackage
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SolverInstallPlan -> SolverPlanIndex
planIndex

-- | Remove packages from the install plan. This will result in an
-- error if there are remaining packages that depend on any matching
-- package. This is primarily useful for obtaining an install plan for
-- the dependencies of a package or set of packages without actually
-- installing the package itself, as when doing development.
remove
  :: (SolverPlanPackage -> Bool)
  -> SolverInstallPlan
  -> Either
      [SolverPlanProblem]
      (SolverInstallPlan)
remove :: (SolverPlanPackage -> Bool)
-> SolverInstallPlan
-> Either [SolverPlanProblem] SolverInstallPlan
remove SolverPlanPackage -> Bool
shouldRemove SolverInstallPlan
plan =
  IndependentGoals
-> SolverPlanIndex -> Either [SolverPlanProblem] SolverInstallPlan
new (SolverInstallPlan -> IndependentGoals
planIndepGoals SolverInstallPlan
plan) SolverPlanIndex
newIndex
  where
    newIndex :: SolverPlanIndex
newIndex =
      [SolverPlanPackage] -> SolverPlanIndex
forall a. (IsNode a, Show (Key a)) => [a] -> Graph a
Graph.fromDistinctList ([SolverPlanPackage] -> SolverPlanIndex)
-> [SolverPlanPackage] -> SolverPlanIndex
forall a b. (a -> b) -> a -> b
$
        (SolverPlanPackage -> Bool)
-> [SolverPlanPackage] -> [SolverPlanPackage]
forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not (Bool -> Bool)
-> (SolverPlanPackage -> Bool) -> SolverPlanPackage -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SolverPlanPackage -> Bool
shouldRemove) (SolverInstallPlan -> [SolverPlanPackage]
toList SolverInstallPlan
plan)

-- ------------------------------------------------------------

-- * Checking validity of plans

-- ------------------------------------------------------------

-- | A valid installation plan is a set of packages that is 'acyclic',
-- 'closed' and 'consistent'. Also, every 'ConfiguredPackage' in the
-- plan has to have a valid configuration (see 'configuredPackageValid').
--
-- * if the result is @False@ use 'problems' to get a detailed list.
valid
  :: IndependentGoals
  -> SolverPlanIndex
  -> Bool
valid :: IndependentGoals -> SolverPlanIndex -> Bool
valid IndependentGoals
indepGoals SolverPlanIndex
index =
  [SolverPlanProblem] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null ([SolverPlanProblem] -> Bool) -> [SolverPlanProblem] -> Bool
forall a b. (a -> b) -> a -> b
$ IndependentGoals -> SolverPlanIndex -> [SolverPlanProblem]
problems IndependentGoals
indepGoals SolverPlanIndex
index

data SolverPlanProblem
  = PackageMissingDeps
      SolverPlanPackage
      [PackageIdentifier]
  | PackageCycle [SolverPlanPackage]
  | PackageInconsistency PackageName [(PackageIdentifier, Version)]
  | PackageStateInvalid SolverPlanPackage SolverPlanPackage

showPlanProblem :: SolverPlanProblem -> String
showPlanProblem :: SolverPlanProblem -> FilePath
showPlanProblem (PackageMissingDeps SolverPlanPackage
pkg [PackageIdentifier]
missingDeps) =
  FilePath
"Package "
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ PackageIdentifier -> FilePath
forall a. Pretty a => a -> FilePath
prettyShow (SolverPlanPackage -> PackageIdentifier
forall pkg. Package pkg => pkg -> PackageIdentifier
packageId SolverPlanPackage
pkg)
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ FilePath
" depends on the following packages which are missing from the plan: "
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ FilePath -> [FilePath] -> FilePath
forall a. [a] -> [[a]] -> [a]
intercalate FilePath
", " ((PackageIdentifier -> FilePath)
-> [PackageIdentifier] -> [FilePath]
forall a b. (a -> b) -> [a] -> [b]
map PackageIdentifier -> FilePath
forall a. Pretty a => a -> FilePath
prettyShow [PackageIdentifier]
missingDeps)
showPlanProblem (PackageCycle [SolverPlanPackage]
cycleGroup) =
  FilePath
"The following packages are involved in a dependency cycle "
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ FilePath -> [FilePath] -> FilePath
forall a. [a] -> [[a]] -> [a]
intercalate FilePath
", " ((SolverPlanPackage -> FilePath)
-> [SolverPlanPackage] -> [FilePath]
forall a b. (a -> b) -> [a] -> [b]
map (PackageIdentifier -> FilePath
forall a. Pretty a => a -> FilePath
prettyShow (PackageIdentifier -> FilePath)
-> (SolverPlanPackage -> PackageIdentifier)
-> SolverPlanPackage
-> FilePath
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SolverPlanPackage -> PackageIdentifier
forall pkg. Package pkg => pkg -> PackageIdentifier
packageId) [SolverPlanPackage]
cycleGroup)
showPlanProblem (PackageInconsistency PackageName
name [(PackageIdentifier, Version)]
inconsistencies) =
  FilePath
"Package "
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ PackageName -> FilePath
forall a. Pretty a => a -> FilePath
prettyShow PackageName
name
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ FilePath
" is required by several packages,"
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ FilePath
" but they require inconsistent versions:\n"
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ [FilePath] -> FilePath
unlines
      [ FilePath
"  package "
        FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ PackageIdentifier -> FilePath
forall a. Pretty a => a -> FilePath
prettyShow PackageIdentifier
pkg
        FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ FilePath
" requires "
        FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ PackageIdentifier -> FilePath
forall a. Pretty a => a -> FilePath
prettyShow (PackageName -> Version -> PackageIdentifier
PackageIdentifier PackageName
name Version
ver)
      | (PackageIdentifier
pkg, Version
ver) <- [(PackageIdentifier, Version)]
inconsistencies
      ]
showPlanProblem (PackageStateInvalid SolverPlanPackage
pkg SolverPlanPackage
pkg') =
  FilePath
"Package "
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ PackageIdentifier -> FilePath
forall a. Pretty a => a -> FilePath
prettyShow (SolverPlanPackage -> PackageIdentifier
forall pkg. Package pkg => pkg -> PackageIdentifier
packageId SolverPlanPackage
pkg)
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ FilePath
" is in the "
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ SolverPlanPackage -> FilePath
forall {loc}. ResolverPackage loc -> FilePath
showPlanState SolverPlanPackage
pkg
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ FilePath
" state but it depends on package "
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ PackageIdentifier -> FilePath
forall a. Pretty a => a -> FilePath
prettyShow (SolverPlanPackage -> PackageIdentifier
forall pkg. Package pkg => pkg -> PackageIdentifier
packageId SolverPlanPackage
pkg')
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ FilePath
" which is in the "
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ SolverPlanPackage -> FilePath
forall {loc}. ResolverPackage loc -> FilePath
showPlanState SolverPlanPackage
pkg'
    FilePath -> FilePath -> FilePath
forall a. [a] -> [a] -> [a]
++ FilePath
" state"
  where
    showPlanState :: ResolverPackage loc -> FilePath
showPlanState (PreExisting InstSolverPackage
_) = FilePath
"pre-existing"
    showPlanState (Configured SolverPackage loc
_) = FilePath
"configured"

-- | For an invalid plan, produce a detailed list of problems as human readable
-- error messages. This is mainly intended for debugging purposes.
-- Use 'showPlanProblem' for a human readable explanation.
problems
  :: IndependentGoals
  -> SolverPlanIndex
  -> [SolverPlanProblem]
problems :: IndependentGoals -> SolverPlanIndex -> [SolverPlanProblem]
problems IndependentGoals
indepGoals SolverPlanIndex
index =
  [ SolverPlanPackage -> [PackageIdentifier] -> SolverPlanProblem
PackageMissingDeps
    SolverPlanPackage
pkg
    ( (SolverId -> Maybe PackageIdentifier)
-> [SolverId] -> [PackageIdentifier]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe
        ((SolverPlanPackage -> PackageIdentifier)
-> Maybe SolverPlanPackage -> Maybe PackageIdentifier
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap SolverPlanPackage -> PackageIdentifier
forall pkg. Package pkg => pkg -> PackageIdentifier
packageId (Maybe SolverPlanPackage -> Maybe PackageIdentifier)
-> (SolverId -> Maybe SolverPlanPackage)
-> SolverId
-> Maybe PackageIdentifier
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (SolverId -> SolverPlanIndex -> Maybe SolverPlanPackage)
-> SolverPlanIndex -> SolverId -> Maybe SolverPlanPackage
forall a b c. (a -> b -> c) -> b -> a -> c
flip Key SolverPlanPackage -> SolverPlanIndex -> Maybe SolverPlanPackage
SolverId -> SolverPlanIndex -> Maybe SolverPlanPackage
forall a. IsNode a => Key a -> Graph a -> Maybe a
Graph.lookup SolverPlanIndex
index)
        [SolverId]
missingDeps
    )
  | (SolverPlanPackage
pkg, [SolverId]
missingDeps) <- SolverPlanIndex -> [(SolverPlanPackage, [Key SolverPlanPackage])]
forall a. Graph a -> [(a, [Key a])]
Graph.broken SolverPlanIndex
index
  ]
    [SolverPlanProblem] -> [SolverPlanProblem] -> [SolverPlanProblem]
forall a. [a] -> [a] -> [a]
++ [ [SolverPlanPackage] -> SolverPlanProblem
PackageCycle [SolverPlanPackage]
cycleGroup
       | [SolverPlanPackage]
cycleGroup <- SolverPlanIndex -> [[SolverPlanPackage]]
forall a. Graph a -> [[a]]
Graph.cycles SolverPlanIndex
index
       ]
    [SolverPlanProblem] -> [SolverPlanProblem] -> [SolverPlanProblem]
forall a. [a] -> [a] -> [a]
++ [ PackageName -> [(PackageIdentifier, Version)] -> SolverPlanProblem
PackageInconsistency PackageName
name [(PackageIdentifier, Version)]
inconsistencies
       | (PackageName
name, [(PackageIdentifier, Version)]
inconsistencies) <-
          IndependentGoals
-> SolverPlanIndex
-> [(PackageName, [(PackageIdentifier, Version)])]
dependencyInconsistencies IndependentGoals
indepGoals SolverPlanIndex
index
       ]
    [SolverPlanProblem] -> [SolverPlanProblem] -> [SolverPlanProblem]
forall a. [a] -> [a] -> [a]
++ [ SolverPlanPackage -> SolverPlanPackage -> SolverPlanProblem
PackageStateInvalid SolverPlanPackage
pkg SolverPlanPackage
pkg'
       | SolverPlanPackage
pkg <- SolverPlanIndex -> [SolverPlanPackage]
forall a. Graph a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
Foldable.toList SolverPlanIndex
index
       , Just SolverPlanPackage
pkg' <-
          (SolverId -> Maybe SolverPlanPackage)
-> [SolverId] -> [Maybe SolverPlanPackage]
forall a b. (a -> b) -> [a] -> [b]
map
            ((SolverId -> SolverPlanIndex -> Maybe SolverPlanPackage)
-> SolverPlanIndex -> SolverId -> Maybe SolverPlanPackage
forall a b c. (a -> b -> c) -> b -> a -> c
flip Key SolverPlanPackage -> SolverPlanIndex -> Maybe SolverPlanPackage
SolverId -> SolverPlanIndex -> Maybe SolverPlanPackage
forall a. IsNode a => Key a -> Graph a -> Maybe a
Graph.lookup SolverPlanIndex
index)
            (SolverPlanPackage -> [Key SolverPlanPackage]
forall a. IsNode a => a -> [Key a]
nodeNeighbors SolverPlanPackage
pkg)
       , Bool -> Bool
not (SolverPlanPackage -> SolverPlanPackage -> Bool
stateDependencyRelation SolverPlanPackage
pkg SolverPlanPackage
pkg')
       ]

-- | Compute all roots of the install plan, and verify that the transitive
-- plans from those roots are all consistent.
--
-- NOTE: This does not check for dependency cycles. Moreover, dependency cycles
-- may be absent from the subplans even if the larger plan contains a dependency
-- cycle. Such cycles may or may not be an issue; either way, we don't check
-- for them here.
dependencyInconsistencies
  :: IndependentGoals
  -> SolverPlanIndex
  -> [(PackageName, [(PackageIdentifier, Version)])]
dependencyInconsistencies :: IndependentGoals
-> SolverPlanIndex
-> [(PackageName, [(PackageIdentifier, Version)])]
dependencyInconsistencies IndependentGoals
indepGoals SolverPlanIndex
index =
  (SolverPlanIndex
 -> [(PackageName, [(PackageIdentifier, Version)])])
-> [SolverPlanIndex]
-> [(PackageName, [(PackageIdentifier, Version)])]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap SolverPlanIndex -> [(PackageName, [(PackageIdentifier, Version)])]
dependencyInconsistencies' [SolverPlanIndex]
subplans
  where
    subplans :: [SolverPlanIndex]
    subplans :: [SolverPlanIndex]
subplans =
      -- Not Graph.closure!!
      ([SolverId] -> SolverPlanIndex)
-> [[SolverId]] -> [SolverPlanIndex]
forall a b. (a -> b) -> [a] -> [b]
map
        (SolverPlanIndex -> [SolverId] -> SolverPlanIndex
nonSetupClosure SolverPlanIndex
index)
        (IndependentGoals -> SolverPlanIndex -> [[SolverId]]
rootSets IndependentGoals
indepGoals SolverPlanIndex
index)

-- NB: When we check for inconsistencies, packages from the setup
-- scripts don't count as part of the closure (this way, we
-- can build, e.g., Cabal-1.24.1 even if its setup script is
-- built with Cabal-1.24.0).
--
-- This is a best effort function that swallows any non-existent
-- SolverIds.
nonSetupClosure
  :: SolverPlanIndex
  -> [SolverId]
  -> SolverPlanIndex
nonSetupClosure :: SolverPlanIndex -> [SolverId] -> SolverPlanIndex
nonSetupClosure SolverPlanIndex
index [SolverId]
pkgids0 = SolverPlanIndex -> [SolverId] -> SolverPlanIndex
closure SolverPlanIndex
forall a. IsNode a => Graph a
Graph.empty [SolverId]
pkgids0
  where
    closure :: Graph SolverPlanPackage -> [SolverId] -> SolverPlanIndex
    closure :: SolverPlanIndex -> [SolverId] -> SolverPlanIndex
closure SolverPlanIndex
completed [] = SolverPlanIndex
completed
    closure SolverPlanIndex
completed (SolverId
pkgid : [SolverId]
pkgids) =
      case Key SolverPlanPackage -> SolverPlanIndex -> Maybe SolverPlanPackage
forall a. IsNode a => Key a -> Graph a -> Maybe a
Graph.lookup Key SolverPlanPackage
SolverId
pkgid SolverPlanIndex
index of
        Maybe SolverPlanPackage
Nothing -> SolverPlanIndex -> [SolverId] -> SolverPlanIndex
closure SolverPlanIndex
completed [SolverId]
pkgids
        Just SolverPlanPackage
pkg ->
          case Key SolverPlanPackage -> SolverPlanIndex -> Maybe SolverPlanPackage
forall a. IsNode a => Key a -> Graph a -> Maybe a
Graph.lookup (SolverPlanPackage -> Key SolverPlanPackage
forall a. IsNode a => a -> Key a
nodeKey SolverPlanPackage
pkg) SolverPlanIndex
completed of
            Just SolverPlanPackage
_ -> SolverPlanIndex -> [SolverId] -> SolverPlanIndex
closure SolverPlanIndex
completed [SolverId]
pkgids
            Maybe SolverPlanPackage
Nothing -> SolverPlanIndex -> [SolverId] -> SolverPlanIndex
closure SolverPlanIndex
completed' [SolverId]
pkgids'
              where
                completed' :: SolverPlanIndex
completed' = SolverPlanPackage -> SolverPlanIndex -> SolverPlanIndex
forall a. IsNode a => a -> Graph a -> Graph a
Graph.insert SolverPlanPackage
pkg SolverPlanIndex
completed
                pkgids' :: [SolverId]
pkgids' = ComponentDeps [SolverId] -> [SolverId]
forall a. Monoid a => ComponentDeps a -> a
CD.nonSetupDeps (SolverPlanPackage -> ComponentDeps [SolverId]
forall loc. ResolverPackage loc -> ComponentDeps [SolverId]
resolverPackageLibDeps SolverPlanPackage
pkg) [SolverId] -> [SolverId] -> [SolverId]
forall a. [a] -> [a] -> [a]
++ [SolverId]
pkgids

-- | Compute the root sets of a plan
--
-- A root set is a set of packages whose dependency closure must be consistent.
-- This is the set of all top-level library roots (taken together normally, or
-- as singletons sets if we are considering them as independent goals), along
-- with all setup dependencies of all packages.
rootSets :: IndependentGoals -> SolverPlanIndex -> [[SolverId]]
rootSets :: IndependentGoals -> SolverPlanIndex -> [[SolverId]]
rootSets (IndependentGoals Bool
indepGoals) SolverPlanIndex
index =
  if Bool
indepGoals
    then (SolverId -> [SolverId]) -> [SolverId] -> [[SolverId]]
forall a b. (a -> b) -> [a] -> [b]
map (SolverId -> [SolverId] -> [SolverId]
forall a. a -> [a] -> [a]
: []) [SolverId]
libRoots
    else
      [[SolverId]
libRoots]
        [[SolverId]] -> [[SolverId]] -> [[SolverId]]
forall a. [a] -> [a] -> [a]
++ SolverPlanIndex -> [[SolverId]]
setupRoots SolverPlanIndex
index
  where
    libRoots :: [SolverId]
    libRoots :: [SolverId]
libRoots = SolverPlanIndex -> [SolverId]
libraryRoots SolverPlanIndex
index

-- | Compute the library roots of a plan
--
-- The library roots are the set of packages with no reverse dependencies
-- (no reverse library dependencies but also no reverse setup dependencies).
libraryRoots :: SolverPlanIndex -> [SolverId]
libraryRoots :: SolverPlanIndex -> [SolverId]
libraryRoots SolverPlanIndex
index =
  (Int -> SolverId) -> [Int] -> [SolverId]
forall a b. (a -> b) -> [a] -> [b]
map (SolverPlanPackage -> Key SolverPlanPackage
SolverPlanPackage -> SolverId
forall a. IsNode a => a -> Key a
nodeKey (SolverPlanPackage -> SolverId)
-> (Int -> SolverPlanPackage) -> Int -> SolverId
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> SolverPlanPackage
toPkgId) [Int]
roots
  where
    (Graph
graph, Int -> SolverPlanPackage
toPkgId, Key SolverPlanPackage -> Maybe Int
_) = SolverPlanIndex
-> (Graph, Int -> SolverPlanPackage,
    Key SolverPlanPackage -> Maybe Int)
forall a. Graph a -> (Graph, Int -> a, Key a -> Maybe Int)
Graph.toGraph SolverPlanIndex
index
    indegree :: Array Int Int
indegree = Graph -> Array Int Int
OldGraph.indegree Graph
graph
    roots :: [Int]
roots = (Int -> Bool) -> [Int] -> [Int]
forall a. (a -> Bool) -> [a] -> [a]
filter Int -> Bool
isRoot (Graph -> [Int]
OldGraph.vertices Graph
graph)
    isRoot :: Int -> Bool
isRoot Int
v = Array Int Int
indegree Array Int Int -> Int -> Int
forall i e. Ix i => Array i e -> i -> e
! Int
v Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0

-- | The setup dependencies of each package in the plan
setupRoots :: SolverPlanIndex -> [[SolverId]]
setupRoots :: SolverPlanIndex -> [[SolverId]]
setupRoots =
  ([SolverId] -> Bool) -> [[SolverId]] -> [[SolverId]]
forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not (Bool -> Bool) -> ([SolverId] -> Bool) -> [SolverId] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [SolverId] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null)
    ([[SolverId]] -> [[SolverId]])
-> (SolverPlanIndex -> [[SolverId]])
-> SolverPlanIndex
-> [[SolverId]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (SolverPlanPackage -> [SolverId])
-> [SolverPlanPackage] -> [[SolverId]]
forall a b. (a -> b) -> [a] -> [b]
map (ComponentDeps [SolverId] -> [SolverId]
forall a. Monoid a => ComponentDeps a -> a
CD.setupDeps (ComponentDeps [SolverId] -> [SolverId])
-> (SolverPlanPackage -> ComponentDeps [SolverId])
-> SolverPlanPackage
-> [SolverId]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SolverPlanPackage -> ComponentDeps [SolverId]
forall loc. ResolverPackage loc -> ComponentDeps [SolverId]
resolverPackageLibDeps)
    ([SolverPlanPackage] -> [[SolverId]])
-> (SolverPlanIndex -> [SolverPlanPackage])
-> SolverPlanIndex
-> [[SolverId]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SolverPlanIndex -> [SolverPlanPackage]
forall a. Graph a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
Foldable.toList

-- | Given a package index where we assume we want to use all the packages
-- (use 'dependencyClosure' if you need to get such a index subset) find out
-- if the dependencies within it use consistent versions of each package.
-- Return all cases where multiple packages depend on different versions of
-- some other package.
--
-- Each element in the result is a package name along with the packages that
-- depend on it and the versions they require. These are guaranteed to be
-- distinct.
dependencyInconsistencies'
  :: SolverPlanIndex
  -> [(PackageName, [(PackageIdentifier, Version)])]
dependencyInconsistencies' :: SolverPlanIndex -> [(PackageName, [(PackageIdentifier, Version)])]
dependencyInconsistencies' SolverPlanIndex
index =
  [ (PackageName
name, [(PackageIdentifier
pid, SolverPlanPackage -> Version
forall pkg. Package pkg => pkg -> Version
packageVersion SolverPlanPackage
dep) | (SolverPlanPackage
dep, [PackageIdentifier]
pids) <- [(SolverPlanPackage, [PackageIdentifier])]
uses, PackageIdentifier
pid <- [PackageIdentifier]
pids])
  | (PackageName
name, Map SolverId (SolverPlanPackage, [PackageIdentifier])
ipid_map) <- Map
  PackageName (Map SolverId (SolverPlanPackage, [PackageIdentifier]))
-> [(PackageName,
     Map SolverId (SolverPlanPackage, [PackageIdentifier]))]
forall k a. Map k a -> [(k, a)]
Map.toList Map
  PackageName (Map SolverId (SolverPlanPackage, [PackageIdentifier]))
inverseIndex
  , let uses :: [(SolverPlanPackage, [PackageIdentifier])]
uses = Map SolverId (SolverPlanPackage, [PackageIdentifier])
-> [(SolverPlanPackage, [PackageIdentifier])]
forall k a. Map k a -> [a]
Map.elems Map SolverId (SolverPlanPackage, [PackageIdentifier])
ipid_map
  , [SolverPlanPackage] -> Bool
reallyIsInconsistent (((SolverPlanPackage, [PackageIdentifier]) -> SolverPlanPackage)
-> [(SolverPlanPackage, [PackageIdentifier])]
-> [SolverPlanPackage]
forall a b. (a -> b) -> [a] -> [b]
map (SolverPlanPackage, [PackageIdentifier]) -> SolverPlanPackage
forall a b. (a, b) -> a
fst [(SolverPlanPackage, [PackageIdentifier])]
uses)
  ]
  where
    -- For each package name (of a dependency, somewhere)
    --   and each installed ID of that package
    --     the associated package instance
    --     and a list of reverse dependencies (as source IDs)
    inverseIndex :: Map PackageName (Map SolverId (SolverPlanPackage, [PackageId]))
    inverseIndex :: Map
  PackageName (Map SolverId (SolverPlanPackage, [PackageIdentifier]))
inverseIndex =
      (Map SolverId (SolverPlanPackage, [PackageIdentifier])
 -> Map SolverId (SolverPlanPackage, [PackageIdentifier])
 -> Map SolverId (SolverPlanPackage, [PackageIdentifier]))
-> [(PackageName,
     Map SolverId (SolverPlanPackage, [PackageIdentifier]))]
-> Map
     PackageName (Map SolverId (SolverPlanPackage, [PackageIdentifier]))
forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
Map.fromListWith
        (((SolverPlanPackage, [PackageIdentifier])
 -> (SolverPlanPackage, [PackageIdentifier])
 -> (SolverPlanPackage, [PackageIdentifier]))
-> Map SolverId (SolverPlanPackage, [PackageIdentifier])
-> Map SolverId (SolverPlanPackage, [PackageIdentifier])
-> Map SolverId (SolverPlanPackage, [PackageIdentifier])
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith (\(SolverPlanPackage
a, [PackageIdentifier]
b) (SolverPlanPackage
_, [PackageIdentifier]
b') -> (SolverPlanPackage
a, [PackageIdentifier]
b [PackageIdentifier] -> [PackageIdentifier] -> [PackageIdentifier]
forall a. [a] -> [a] -> [a]
++ [PackageIdentifier]
b')))
        [ (SolverPlanPackage -> PackageName
forall pkg. Package pkg => pkg -> PackageName
packageName SolverPlanPackage
dep, [(SolverId, (SolverPlanPackage, [PackageIdentifier]))]
-> Map SolverId (SolverPlanPackage, [PackageIdentifier])
forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList [(SolverId
sid, (SolverPlanPackage
dep, [SolverPlanPackage -> PackageIdentifier
forall pkg. Package pkg => pkg -> PackageIdentifier
packageId SolverPlanPackage
pkg]))])
        | -- For each package @pkg@
        SolverPlanPackage
pkg <- SolverPlanIndex -> [SolverPlanPackage]
forall a. Graph a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
Foldable.toList SolverPlanIndex
index
        , -- Find out which @sid@ @pkg@ depends on
        SolverId
sid <- ComponentDeps [SolverId] -> [SolverId]
forall a. Monoid a => ComponentDeps a -> a
CD.nonSetupDeps (SolverPlanPackage -> ComponentDeps [SolverId]
forall loc. ResolverPackage loc -> ComponentDeps [SolverId]
resolverPackageLibDeps SolverPlanPackage
pkg)
        , -- And look up those @sid@ (i.e., @sid@ is the ID of @dep@)
        Just SolverPlanPackage
dep <- [Key SolverPlanPackage -> SolverPlanIndex -> Maybe SolverPlanPackage
forall a. IsNode a => Key a -> Graph a -> Maybe a
Graph.lookup Key SolverPlanPackage
SolverId
sid SolverPlanIndex
index]
        ]

    -- If, in a single install plan, we depend on more than one version of a
    -- package, then this is ONLY okay in the (rather special) case that we
    -- depend on precisely two versions of that package, and one of them
    -- depends on the other. This is necessary for example for the base where
    -- we have base-3 depending on base-4.
    reallyIsInconsistent :: [SolverPlanPackage] -> Bool
    reallyIsInconsistent :: [SolverPlanPackage] -> Bool
reallyIsInconsistent [] = Bool
False
    reallyIsInconsistent [SolverPlanPackage
_p] = Bool
False
    reallyIsInconsistent [SolverPlanPackage
p1, SolverPlanPackage
p2] =
      let pid1 :: Key SolverPlanPackage
pid1 = SolverPlanPackage -> Key SolverPlanPackage
forall a. IsNode a => a -> Key a
nodeKey SolverPlanPackage
p1
          pid2 :: Key SolverPlanPackage
pid2 = SolverPlanPackage -> Key SolverPlanPackage
forall a. IsNode a => a -> Key a
nodeKey SolverPlanPackage
p2
       in Key SolverPlanPackage
SolverId
pid1 SolverId -> [SolverId] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`notElem` ComponentDeps [SolverId] -> [SolverId]
forall a. Monoid a => ComponentDeps a -> a
CD.nonSetupDeps (SolverPlanPackage -> ComponentDeps [SolverId]
forall loc. ResolverPackage loc -> ComponentDeps [SolverId]
resolverPackageLibDeps SolverPlanPackage
p2)
            Bool -> Bool -> Bool
&& Key SolverPlanPackage
SolverId
pid2 SolverId -> [SolverId] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`notElem` ComponentDeps [SolverId] -> [SolverId]
forall a. Monoid a => ComponentDeps a -> a
CD.nonSetupDeps (SolverPlanPackage -> ComponentDeps [SolverId]
forall loc. ResolverPackage loc -> ComponentDeps [SolverId]
resolverPackageLibDeps SolverPlanPackage
p1)
    reallyIsInconsistent [SolverPlanPackage]
_ = Bool
True

-- | The graph of packages (nodes) and dependencies (edges) must be acyclic.
--
-- * if the result is @False@ use 'PackageIndex.dependencyCycles' to find out
--   which packages are involved in dependency cycles.
acyclic :: SolverPlanIndex -> Bool
acyclic :: SolverPlanIndex -> Bool
acyclic = [[SolverPlanPackage]] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null ([[SolverPlanPackage]] -> Bool)
-> (SolverPlanIndex -> [[SolverPlanPackage]])
-> SolverPlanIndex
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SolverPlanIndex -> [[SolverPlanPackage]]
forall a. Graph a -> [[a]]
Graph.cycles

-- | An installation plan is closed if for every package in the set, all of
-- its dependencies are also in the set. That is, the set is closed under the
-- dependency relation.
--
-- * if the result is @False@ use 'PackageIndex.brokenPackages' to find out
--   which packages depend on packages not in the index.
closed :: SolverPlanIndex -> Bool
closed :: SolverPlanIndex -> Bool
closed = [(SolverPlanPackage, [SolverId])] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null ([(SolverPlanPackage, [SolverId])] -> Bool)
-> (SolverPlanIndex -> [(SolverPlanPackage, [SolverId])])
-> SolverPlanIndex
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SolverPlanIndex -> [(SolverPlanPackage, [Key SolverPlanPackage])]
SolverPlanIndex -> [(SolverPlanPackage, [SolverId])]
forall a. Graph a -> [(a, [Key a])]
Graph.broken

-- | An installation plan is consistent if all dependencies that target a
-- single package name, target the same version.
--
-- This is slightly subtle. It is not the same as requiring that there be at
-- most one version of any package in the set. It only requires that of
-- packages which have more than one other package depending on them. We could
-- actually make the condition even more precise and say that different
-- versions are OK so long as they are not both in the transitive closure of
-- any other package (or equivalently that their inverse closures do not
-- intersect). The point is we do not want to have any packages depending
-- directly or indirectly on two different versions of the same package. The
-- current definition is just a safe approximation of that.
--
-- * if the result is @False@ use 'PackageIndex.dependencyInconsistencies' to
--   find out which packages are.
consistent :: SolverPlanIndex -> Bool
consistent :: SolverPlanIndex -> Bool
consistent = [(PackageName, [(PackageIdentifier, Version)])] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null ([(PackageName, [(PackageIdentifier, Version)])] -> Bool)
-> (SolverPlanIndex
    -> [(PackageName, [(PackageIdentifier, Version)])])
-> SolverPlanIndex
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IndependentGoals
-> SolverPlanIndex
-> [(PackageName, [(PackageIdentifier, Version)])]
dependencyInconsistencies (Bool -> IndependentGoals
IndependentGoals Bool
False)

-- | The states of packages have that depend on each other must respect
-- this relation. That is for very case where package @a@ depends on
-- package @b@ we require that @dependencyStatesOk a b = True@.
stateDependencyRelation
  :: SolverPlanPackage
  -> SolverPlanPackage
  -> Bool
stateDependencyRelation :: SolverPlanPackage -> SolverPlanPackage -> Bool
stateDependencyRelation PreExisting{} PreExisting{} = Bool
True
stateDependencyRelation (Configured SolverPackage UnresolvedPkgLoc
_) PreExisting{} = Bool
True
stateDependencyRelation (Configured SolverPackage UnresolvedPkgLoc
_) (Configured SolverPackage UnresolvedPkgLoc
_) = Bool
True
stateDependencyRelation SolverPlanPackage
_ SolverPlanPackage
_ = Bool
False

-- | Compute the dependency closure of a package in a install plan
dependencyClosure
  :: SolverInstallPlan
  -> [SolverId]
  -> [SolverPlanPackage]
dependencyClosure :: SolverInstallPlan -> [SolverId] -> [SolverPlanPackage]
dependencyClosure SolverInstallPlan
plan = [SolverPlanPackage]
-> Maybe [SolverPlanPackage] -> [SolverPlanPackage]
forall a. a -> Maybe a -> a
fromMaybe [] (Maybe [SolverPlanPackage] -> [SolverPlanPackage])
-> ([SolverId] -> Maybe [SolverPlanPackage])
-> [SolverId]
-> [SolverPlanPackage]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SolverPlanIndex
-> [Key SolverPlanPackage] -> Maybe [SolverPlanPackage]
forall a. Graph a -> [Key a] -> Maybe [a]
Graph.closure (SolverInstallPlan -> SolverPlanIndex
planIndex SolverInstallPlan
plan)

reverseDependencyClosure
  :: SolverInstallPlan
  -> [SolverId]
  -> [SolverPlanPackage]
reverseDependencyClosure :: SolverInstallPlan -> [SolverId] -> [SolverPlanPackage]
reverseDependencyClosure SolverInstallPlan
plan = [SolverPlanPackage]
-> Maybe [SolverPlanPackage] -> [SolverPlanPackage]
forall a. a -> Maybe a -> a
fromMaybe [] (Maybe [SolverPlanPackage] -> [SolverPlanPackage])
-> ([SolverId] -> Maybe [SolverPlanPackage])
-> [SolverId]
-> [SolverPlanPackage]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SolverPlanIndex
-> [Key SolverPlanPackage] -> Maybe [SolverPlanPackage]
forall a. Graph a -> [Key a] -> Maybe [a]
Graph.revClosure (SolverInstallPlan -> SolverPlanIndex
planIndex SolverInstallPlan
plan)

topologicalOrder
  :: SolverInstallPlan
  -> [SolverPlanPackage]
topologicalOrder :: SolverInstallPlan -> [SolverPlanPackage]
topologicalOrder SolverInstallPlan
plan = SolverPlanIndex -> [SolverPlanPackage]
forall a. Graph a -> [a]
Graph.topSort (SolverInstallPlan -> SolverPlanIndex
planIndex SolverInstallPlan
plan)

reverseTopologicalOrder
  :: SolverInstallPlan
  -> [SolverPlanPackage]
reverseTopologicalOrder :: SolverInstallPlan -> [SolverPlanPackage]
reverseTopologicalOrder SolverInstallPlan
plan = SolverPlanIndex -> [SolverPlanPackage]
forall a. Graph a -> [a]
Graph.revTopSort (SolverInstallPlan -> SolverPlanIndex
planIndex SolverInstallPlan
plan)