{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE RecordWildCards #-}
module Distribution.Solver.Modular.Dependency (
    -- * Variables
    Var(..)
  , showVar
  , varPN
    -- * Conflict sets
  , ConflictSet
  , ConflictMap
  , CS.showConflictSet
    -- * Constrained instances
  , CI(..)
    -- * Flagged dependencies
  , FlaggedDeps
  , FlaggedDep(..)
  , LDep(..)
  , Dep(..)
  , PkgComponent(..)
  , ExposedComponent(..)
  , DependencyReason(..)
  , showDependencyReason
  , flattenFlaggedDeps
  , QualifyOptions(..)
  , qualifyDeps
  , unqualifyDeps
    -- * Reverse dependency map
  , RevDepMap
    -- * Goals
  , Goal(..)
  , GoalReason(..)
  , QGoalReason
  , goalToVar
  , varToConflictSet
  , goalReasonToConflictSet
  , goalReasonToConflictSetWithConflict
  , dependencyReasonToConflictSet
  , dependencyReasonToConflictSetWithVersionConstraintConflict
  , dependencyReasonToConflictSetWithVersionConflict
  ) where

import Prelude ()
import qualified Data.Map as M
import qualified Data.Set as S
import Distribution.Solver.Compat.Prelude hiding (pi)

import Language.Haskell.Extension (Extension(..), Language(..))

import Distribution.Solver.Modular.ConflictSet (ConflictSet, ConflictMap)
import Distribution.Solver.Modular.Flag
import Distribution.Solver.Modular.Package
import Distribution.Solver.Modular.Var
import Distribution.Solver.Modular.Version
import qualified Distribution.Solver.Modular.ConflictSet as CS

import Distribution.Solver.Types.ComponentDeps (Component(..))
import Distribution.Solver.Types.PackagePath
import Distribution.Types.LibraryName
import Distribution.Types.PkgconfigVersionRange
import Distribution.Types.UnqualComponentName

{-------------------------------------------------------------------------------
  Constrained instances
-------------------------------------------------------------------------------}

-- | Constrained instance. It represents the allowed instances for a package,
-- which can be either a fixed instance or a version range.
data CI = Fixed I | Constrained VR
  deriving (CI -> CI -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: CI -> CI -> Bool
$c/= :: CI -> CI -> Bool
== :: CI -> CI -> Bool
$c== :: CI -> CI -> Bool
Eq, Int -> CI -> ShowS
[CI] -> ShowS
CI -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [CI] -> ShowS
$cshowList :: [CI] -> ShowS
show :: CI -> String
$cshow :: CI -> String
showsPrec :: Int -> CI -> ShowS
$cshowsPrec :: Int -> CI -> ShowS
Show)

{-------------------------------------------------------------------------------
  Flagged dependencies
-------------------------------------------------------------------------------}

-- | Flagged dependencies
--
-- 'FlaggedDeps' is the modular solver's view of a packages dependencies:
-- rather than having the dependencies indexed by component, each dependency
-- defines what component it is in.
--
-- Note that each dependency is associated with a Component. We must know what
-- component the dependencies belong to, or else we won't be able to construct
-- fine-grained reverse dependencies.
type FlaggedDeps qpn = [FlaggedDep qpn]

-- | Flagged dependencies can either be plain dependency constraints,
-- or flag-dependent dependency trees.
data FlaggedDep qpn =
    -- | Dependencies which are conditional on a flag choice.
    Flagged (FN qpn) FInfo (TrueFlaggedDeps qpn) (FalseFlaggedDeps qpn)
    -- | Dependencies which are conditional on whether or not a stanza
    -- (e.g., a test suite or benchmark) is enabled.
  | Stanza  (SN qpn)       (TrueFlaggedDeps qpn)
    -- | Dependencies which are always enabled, for the component 'comp'.
  | Simple (LDep qpn) Component

-- | Conservatively flatten out flagged dependencies
--
-- NOTE: We do not filter out duplicates.
flattenFlaggedDeps :: FlaggedDeps qpn -> [(LDep qpn, Component)]
flattenFlaggedDeps :: forall qpn. FlaggedDeps qpn -> [(LDep qpn, Component)]
flattenFlaggedDeps = forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap forall qpn. FlaggedDep qpn -> [(LDep qpn, Component)]
aux
  where
    aux :: FlaggedDep qpn -> [(LDep qpn, Component)]
    aux :: forall qpn. FlaggedDep qpn -> [(LDep qpn, Component)]
aux (Flagged FN qpn
_ FInfo
_ TrueFlaggedDeps qpn
t TrueFlaggedDeps qpn
f) = forall qpn. FlaggedDeps qpn -> [(LDep qpn, Component)]
flattenFlaggedDeps TrueFlaggedDeps qpn
t forall a. [a] -> [a] -> [a]
++ forall qpn. FlaggedDeps qpn -> [(LDep qpn, Component)]
flattenFlaggedDeps TrueFlaggedDeps qpn
f
    aux (Stanza  SN qpn
_   TrueFlaggedDeps qpn
t)   = forall qpn. FlaggedDeps qpn -> [(LDep qpn, Component)]
flattenFlaggedDeps TrueFlaggedDeps qpn
t
    aux (Simple LDep qpn
d Component
c)      = [(LDep qpn
d, Component
c)]

type TrueFlaggedDeps  qpn = FlaggedDeps qpn
type FalseFlaggedDeps qpn = FlaggedDeps qpn

-- | A 'Dep' labeled with the reason it was introduced.
--
-- 'LDep' intentionally has no 'Functor' instance because the type variable
-- is used both to record the dependencies as well as who's doing the
-- depending; having a 'Functor' instance makes bugs where we don't distinguish
-- these two far too likely. (By rights 'LDep' ought to have two type variables.)
data LDep qpn = LDep (DependencyReason qpn) (Dep qpn)

-- | A dependency (constraint) associates a package name with a constrained
-- instance. It can also represent other types of dependencies, such as
-- dependencies on language extensions.
data Dep qpn = Dep (PkgComponent qpn) CI  -- ^ dependency on a package component
             | Ext Extension              -- ^ dependency on a language extension
             | Lang Language              -- ^ dependency on a language version
             | Pkg PkgconfigName PkgconfigVersionRange  -- ^ dependency on a pkg-config package
  deriving forall a b. a -> Dep b -> Dep a
forall a b. (a -> b) -> Dep a -> Dep b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: forall a b. a -> Dep b -> Dep a
$c<$ :: forall a b. a -> Dep b -> Dep a
fmap :: forall a b. (a -> b) -> Dep a -> Dep b
$cfmap :: forall a b. (a -> b) -> Dep a -> Dep b
Functor

-- | An exposed component within a package. This type is used to represent
-- build-depends and build-tool-depends dependencies.
data PkgComponent qpn = PkgComponent qpn ExposedComponent
  deriving (PkgComponent qpn -> PkgComponent qpn -> Bool
forall qpn. Eq qpn => PkgComponent qpn -> PkgComponent qpn -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: PkgComponent qpn -> PkgComponent qpn -> Bool
$c/= :: forall qpn. Eq qpn => PkgComponent qpn -> PkgComponent qpn -> Bool
== :: PkgComponent qpn -> PkgComponent qpn -> Bool
$c== :: forall qpn. Eq qpn => PkgComponent qpn -> PkgComponent qpn -> Bool
Eq, PkgComponent qpn -> PkgComponent qpn -> Bool
PkgComponent qpn -> PkgComponent qpn -> Ordering
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall {qpn}. Ord qpn => Eq (PkgComponent qpn)
forall qpn. Ord qpn => PkgComponent qpn -> PkgComponent qpn -> Bool
forall qpn.
Ord qpn =>
PkgComponent qpn -> PkgComponent qpn -> Ordering
forall qpn.
Ord qpn =>
PkgComponent qpn -> PkgComponent qpn -> PkgComponent qpn
min :: PkgComponent qpn -> PkgComponent qpn -> PkgComponent qpn
$cmin :: forall qpn.
Ord qpn =>
PkgComponent qpn -> PkgComponent qpn -> PkgComponent qpn
max :: PkgComponent qpn -> PkgComponent qpn -> PkgComponent qpn
$cmax :: forall qpn.
Ord qpn =>
PkgComponent qpn -> PkgComponent qpn -> PkgComponent qpn
>= :: PkgComponent qpn -> PkgComponent qpn -> Bool
$c>= :: forall qpn. Ord qpn => PkgComponent qpn -> PkgComponent qpn -> Bool
> :: PkgComponent qpn -> PkgComponent qpn -> Bool
$c> :: forall qpn. Ord qpn => PkgComponent qpn -> PkgComponent qpn -> Bool
<= :: PkgComponent qpn -> PkgComponent qpn -> Bool
$c<= :: forall qpn. Ord qpn => PkgComponent qpn -> PkgComponent qpn -> Bool
< :: PkgComponent qpn -> PkgComponent qpn -> Bool
$c< :: forall qpn. Ord qpn => PkgComponent qpn -> PkgComponent qpn -> Bool
compare :: PkgComponent qpn -> PkgComponent qpn -> Ordering
$ccompare :: forall qpn.
Ord qpn =>
PkgComponent qpn -> PkgComponent qpn -> Ordering
Ord, forall a b. a -> PkgComponent b -> PkgComponent a
forall a b. (a -> b) -> PkgComponent a -> PkgComponent b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: forall a b. a -> PkgComponent b -> PkgComponent a
$c<$ :: forall a b. a -> PkgComponent b -> PkgComponent a
fmap :: forall a b. (a -> b) -> PkgComponent a -> PkgComponent b
$cfmap :: forall a b. (a -> b) -> PkgComponent a -> PkgComponent b
Functor, Int -> PkgComponent qpn -> ShowS
forall qpn. Show qpn => Int -> PkgComponent qpn -> ShowS
forall qpn. Show qpn => [PkgComponent qpn] -> ShowS
forall qpn. Show qpn => PkgComponent qpn -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [PkgComponent qpn] -> ShowS
$cshowList :: forall qpn. Show qpn => [PkgComponent qpn] -> ShowS
show :: PkgComponent qpn -> String
$cshow :: forall qpn. Show qpn => PkgComponent qpn -> String
showsPrec :: Int -> PkgComponent qpn -> ShowS
$cshowsPrec :: forall qpn. Show qpn => Int -> PkgComponent qpn -> ShowS
Show)

-- | A component that can be depended upon by another package, i.e., a library
-- or an executable.
data ExposedComponent =
    ExposedLib LibraryName
  | ExposedExe UnqualComponentName
  deriving (ExposedComponent -> ExposedComponent -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: ExposedComponent -> ExposedComponent -> Bool
$c/= :: ExposedComponent -> ExposedComponent -> Bool
== :: ExposedComponent -> ExposedComponent -> Bool
$c== :: ExposedComponent -> ExposedComponent -> Bool
Eq, Eq ExposedComponent
ExposedComponent -> ExposedComponent -> Bool
ExposedComponent -> ExposedComponent -> Ordering
ExposedComponent -> ExposedComponent -> ExposedComponent
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: ExposedComponent -> ExposedComponent -> ExposedComponent
$cmin :: ExposedComponent -> ExposedComponent -> ExposedComponent
max :: ExposedComponent -> ExposedComponent -> ExposedComponent
$cmax :: ExposedComponent -> ExposedComponent -> ExposedComponent
>= :: ExposedComponent -> ExposedComponent -> Bool
$c>= :: ExposedComponent -> ExposedComponent -> Bool
> :: ExposedComponent -> ExposedComponent -> Bool
$c> :: ExposedComponent -> ExposedComponent -> Bool
<= :: ExposedComponent -> ExposedComponent -> Bool
$c<= :: ExposedComponent -> ExposedComponent -> Bool
< :: ExposedComponent -> ExposedComponent -> Bool
$c< :: ExposedComponent -> ExposedComponent -> Bool
compare :: ExposedComponent -> ExposedComponent -> Ordering
$ccompare :: ExposedComponent -> ExposedComponent -> Ordering
Ord, Int -> ExposedComponent -> ShowS
[ExposedComponent] -> ShowS
ExposedComponent -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [ExposedComponent] -> ShowS
$cshowList :: [ExposedComponent] -> ShowS
show :: ExposedComponent -> String
$cshow :: ExposedComponent -> String
showsPrec :: Int -> ExposedComponent -> ShowS
$cshowsPrec :: Int -> ExposedComponent -> ShowS
Show)

-- | The reason that a dependency is active. It identifies the package and any
-- flag and stanza choices that introduced the dependency. It contains
-- everything needed for creating ConflictSets or describing conflicts in solver
-- log messages.
data DependencyReason qpn = DependencyReason qpn (Map Flag FlagValue) (S.Set Stanza)
  deriving (forall a b. a -> DependencyReason b -> DependencyReason a
forall a b. (a -> b) -> DependencyReason a -> DependencyReason b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: forall a b. a -> DependencyReason b -> DependencyReason a
$c<$ :: forall a b. a -> DependencyReason b -> DependencyReason a
fmap :: forall a b. (a -> b) -> DependencyReason a -> DependencyReason b
$cfmap :: forall a b. (a -> b) -> DependencyReason a -> DependencyReason b
Functor, DependencyReason qpn -> DependencyReason qpn -> Bool
forall qpn.
Eq qpn =>
DependencyReason qpn -> DependencyReason qpn -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: DependencyReason qpn -> DependencyReason qpn -> Bool
$c/= :: forall qpn.
Eq qpn =>
DependencyReason qpn -> DependencyReason qpn -> Bool
== :: DependencyReason qpn -> DependencyReason qpn -> Bool
$c== :: forall qpn.
Eq qpn =>
DependencyReason qpn -> DependencyReason qpn -> Bool
Eq, Int -> DependencyReason qpn -> ShowS
forall qpn. Show qpn => Int -> DependencyReason qpn -> ShowS
forall qpn. Show qpn => [DependencyReason qpn] -> ShowS
forall qpn. Show qpn => DependencyReason qpn -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [DependencyReason qpn] -> ShowS
$cshowList :: forall qpn. Show qpn => [DependencyReason qpn] -> ShowS
show :: DependencyReason qpn -> String
$cshow :: forall qpn. Show qpn => DependencyReason qpn -> String
showsPrec :: Int -> DependencyReason qpn -> ShowS
$cshowsPrec :: forall qpn. Show qpn => Int -> DependencyReason qpn -> ShowS
Show)

-- | Print the reason that a dependency was introduced.
showDependencyReason :: DependencyReason QPN -> String
showDependencyReason :: DependencyReason QPN -> String
showDependencyReason (DependencyReason QPN
qpn Map Flag FlagValue
flags Set Stanza
stanzas) =
    forall a. [a] -> [[a]] -> [a]
intercalate String
" " forall a b. (a -> b) -> a -> b
$
        QPN -> String
showQPN QPN
qpn
      forall a. a -> [a] -> [a]
: forall a b. (a -> b) -> [a] -> [b]
map (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Flag -> FlagValue -> String
showFlagValue) (forall k a. Map k a -> [(k, a)]
M.toList Map Flag FlagValue
flags)
     forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
map (\Stanza
s -> Stanza -> Bool -> String
showSBool Stanza
s Bool
True) (forall a. Set a -> [a]
S.toList Set Stanza
stanzas)

-- | Options for goal qualification (used in 'qualifyDeps')
--
-- See also 'defaultQualifyOptions'
data QualifyOptions = QO {
    -- | Do we have a version of base relying on another version of base?
    QualifyOptions -> Bool
qoBaseShim :: Bool

    -- Should dependencies of the setup script be treated as independent?
  , QualifyOptions -> Bool
qoSetupIndependent :: Bool
  }
  deriving Int -> QualifyOptions -> ShowS
[QualifyOptions] -> ShowS
QualifyOptions -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [QualifyOptions] -> ShowS
$cshowList :: [QualifyOptions] -> ShowS
show :: QualifyOptions -> String
$cshow :: QualifyOptions -> String
showsPrec :: Int -> QualifyOptions -> ShowS
$cshowsPrec :: Int -> QualifyOptions -> ShowS
Show

-- | Apply built-in rules for package qualifiers
--
-- Although the behaviour of 'qualifyDeps' depends on the 'QualifyOptions',
-- it is important that these 'QualifyOptions' are _static_. Qualification
-- does NOT depend on flag assignment; in other words, it behaves the same no
-- matter which choices the solver makes (modulo the global 'QualifyOptions');
-- we rely on this in 'linkDeps' (see comment there).
--
-- NOTE: It's the _dependencies_ of a package that may or may not be independent
-- from the package itself. Package flag choices must of course be consistent.
qualifyDeps :: QualifyOptions -> QPN -> FlaggedDeps PN -> FlaggedDeps QPN
qualifyDeps :: QualifyOptions -> QPN -> FlaggedDeps PN -> FlaggedDeps QPN
qualifyDeps QO{Bool
qoSetupIndependent :: Bool
qoBaseShim :: Bool
qoSetupIndependent :: QualifyOptions -> Bool
qoBaseShim :: QualifyOptions -> Bool
..} (Q pp :: PackagePath
pp@(PackagePath Namespace
ns Qualifier
q) PN
pn) = FlaggedDeps PN -> FlaggedDeps QPN
go
  where
    go :: FlaggedDeps PN -> FlaggedDeps QPN
    go :: FlaggedDeps PN -> FlaggedDeps QPN
go = forall a b. (a -> b) -> [a] -> [b]
map FlaggedDep PN -> FlaggedDep QPN
go1

    go1 :: FlaggedDep PN -> FlaggedDep QPN
    go1 :: FlaggedDep PN -> FlaggedDep QPN
go1 (Flagged FN PN
fn FInfo
nfo FlaggedDeps PN
t FlaggedDeps PN
f) = forall qpn.
FN qpn
-> FInfo
-> TrueFlaggedDeps qpn
-> TrueFlaggedDeps qpn
-> FlaggedDep qpn
Flagged (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a. PackagePath -> a -> Qualified a
Q PackagePath
pp) FN PN
fn) FInfo
nfo (FlaggedDeps PN -> FlaggedDeps QPN
go FlaggedDeps PN
t) (FlaggedDeps PN -> FlaggedDeps QPN
go FlaggedDeps PN
f)
    go1 (Stanza  SN PN
sn     FlaggedDeps PN
t)   = forall qpn. SN qpn -> TrueFlaggedDeps qpn -> FlaggedDep qpn
Stanza  (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a. PackagePath -> a -> Qualified a
Q PackagePath
pp) SN PN
sn)     (FlaggedDeps PN -> FlaggedDeps QPN
go FlaggedDeps PN
t)
    go1 (Simple LDep PN
dep Component
comp)    = forall qpn. LDep qpn -> Component -> FlaggedDep qpn
Simple (LDep PN -> Component -> LDep QPN
goLDep LDep PN
dep Component
comp) Component
comp

    -- Suppose package B has a setup dependency on package A.
    -- This will be recorded as something like
    --
    -- > LDep (DependencyReason "B") (Dep (PkgComponent "A" (ExposedLib LMainLibName)) (Constrained AnyVersion))
    --
    -- Observe that when we qualify this dependency, we need to turn that
    -- @"A"@ into @"B-setup.A"@, but we should not apply that same qualifier
    -- to the DependencyReason.
    goLDep :: LDep PN -> Component -> LDep QPN
    goLDep :: LDep PN -> Component -> LDep QPN
goLDep (LDep DependencyReason PN
dr Dep PN
dep) Component
comp = forall qpn. DependencyReason qpn -> Dep qpn -> LDep qpn
LDep (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a. PackagePath -> a -> Qualified a
Q PackagePath
pp) DependencyReason PN
dr) (Dep PN -> Component -> Dep QPN
goD Dep PN
dep Component
comp)

    goD :: Dep PN -> Component -> Dep QPN
    goD :: Dep PN -> Component -> Dep QPN
goD (Ext  Extension
ext)    Component
_    = forall qpn. Extension -> Dep qpn
Ext  Extension
ext
    goD (Lang Language
lang)   Component
_    = forall qpn. Language -> Dep qpn
Lang Language
lang
    goD (Pkg PkgconfigName
pkn PkgconfigVersionRange
vr)  Component
_    = forall qpn. PkgconfigName -> PkgconfigVersionRange -> Dep qpn
Pkg PkgconfigName
pkn PkgconfigVersionRange
vr
    goD (Dep dep :: PkgComponent PN
dep@(PkgComponent PN
qpn (ExposedExe UnqualComponentName
_)) CI
ci) Component
_ =
        forall qpn. PkgComponent qpn -> CI -> Dep qpn
Dep (forall a. PackagePath -> a -> Qualified a
Q (Namespace -> Qualifier -> PackagePath
PackagePath Namespace
ns (PN -> PN -> Qualifier
QualExe PN
pn PN
qpn)) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> PkgComponent PN
dep) CI
ci
    goD (Dep dep :: PkgComponent PN
dep@(PkgComponent PN
qpn (ExposedLib LibraryName
_)) CI
ci) Component
comp
      | PN -> Bool
qBase PN
qpn   = forall qpn. PkgComponent qpn -> CI -> Dep qpn
Dep (forall a. PackagePath -> a -> Qualified a
Q (Namespace -> Qualifier -> PackagePath
PackagePath Namespace
ns (PN -> Qualifier
QualBase  PN
pn)) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> PkgComponent PN
dep) CI
ci
      | Component -> Bool
qSetup Component
comp = forall qpn. PkgComponent qpn -> CI -> Dep qpn
Dep (forall a. PackagePath -> a -> Qualified a
Q (Namespace -> Qualifier -> PackagePath
PackagePath Namespace
ns (PN -> Qualifier
QualSetup PN
pn)) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> PkgComponent PN
dep) CI
ci
      | Bool
otherwise   = forall qpn. PkgComponent qpn -> CI -> Dep qpn
Dep (forall a. PackagePath -> a -> Qualified a
Q (Namespace -> Qualifier -> PackagePath
PackagePath Namespace
ns Qualifier
inheritedQ    ) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> PkgComponent PN
dep) CI
ci

    -- If P has a setup dependency on Q, and Q has a regular dependency on R, then
    -- we say that the 'Setup' qualifier is inherited: P has an (indirect) setup
    -- dependency on R. We do not do this for the base qualifier however.
    --
    -- The inherited qualifier is only used for regular dependencies; for setup
    -- and base dependencies we override the existing qualifier. See #3160 for
    -- a detailed discussion.
    inheritedQ :: Qualifier
    inheritedQ :: Qualifier
inheritedQ = case Qualifier
q of
                   QualSetup PN
_  -> Qualifier
q
                   QualExe PN
_ PN
_  -> Qualifier
q
                   Qualifier
QualToplevel -> Qualifier
q
                   QualBase PN
_   -> Qualifier
QualToplevel

    -- Should we qualify this goal with the 'Base' package path?
    qBase :: PN -> Bool
    qBase :: PN -> Bool
qBase PN
dep = Bool
qoBaseShim Bool -> Bool -> Bool
&& PN -> String
unPackageName PN
dep forall a. Eq a => a -> a -> Bool
== String
"base"

    -- Should we qualify this goal with the 'Setup' package path?
    qSetup :: Component -> Bool
    qSetup :: Component -> Bool
qSetup Component
comp = Bool
qoSetupIndependent Bool -> Bool -> Bool
&& Component
comp forall a. Eq a => a -> a -> Bool
== Component
ComponentSetup

-- | Remove qualifiers from set of dependencies
--
-- This is used during link validation: when we link package @Q.A@ to @Q'.A@,
-- then all dependencies @Q.B@ need to be linked to @Q'.B@. In order to compute
-- what to link these dependencies to, we need to requalify @Q.B@ to become
-- @Q'.B@; we do this by first removing all qualifiers and then calling
-- 'qualifyDeps' again.
unqualifyDeps :: FlaggedDeps QPN -> FlaggedDeps PN
unqualifyDeps :: FlaggedDeps QPN -> FlaggedDeps PN
unqualifyDeps = FlaggedDeps QPN -> FlaggedDeps PN
go
  where
    go :: FlaggedDeps QPN -> FlaggedDeps PN
    go :: FlaggedDeps QPN -> FlaggedDeps PN
go = forall a b. (a -> b) -> [a] -> [b]
map FlaggedDep QPN -> FlaggedDep PN
go1

    go1 :: FlaggedDep QPN -> FlaggedDep PN
    go1 :: FlaggedDep QPN -> FlaggedDep PN
go1 (Flagged FN QPN
fn FInfo
nfo FlaggedDeps QPN
t FlaggedDeps QPN
f) = forall qpn.
FN qpn
-> FInfo
-> TrueFlaggedDeps qpn
-> TrueFlaggedDeps qpn
-> FlaggedDep qpn
Flagged (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap QPN -> PN
unq FN QPN
fn) FInfo
nfo (FlaggedDeps QPN -> FlaggedDeps PN
go FlaggedDeps QPN
t) (FlaggedDeps QPN -> FlaggedDeps PN
go FlaggedDeps QPN
f)
    go1 (Stanza  SN QPN
sn     FlaggedDeps QPN
t)   = forall qpn. SN qpn -> TrueFlaggedDeps qpn -> FlaggedDep qpn
Stanza  (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap QPN -> PN
unq SN QPN
sn)     (FlaggedDeps QPN -> FlaggedDeps PN
go FlaggedDeps QPN
t)
    go1 (Simple LDep QPN
dep Component
comp)    = forall qpn. LDep qpn -> Component -> FlaggedDep qpn
Simple (LDep QPN -> LDep PN
goLDep LDep QPN
dep) Component
comp

    goLDep :: LDep QPN -> LDep PN
    goLDep :: LDep QPN -> LDep PN
goLDep (LDep DependencyReason QPN
dr Dep QPN
dep) = forall qpn. DependencyReason qpn -> Dep qpn -> LDep qpn
LDep (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap QPN -> PN
unq DependencyReason QPN
dr) (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap QPN -> PN
unq Dep QPN
dep)

    unq :: QPN -> PN
    unq :: QPN -> PN
unq (Q PackagePath
_ PN
pn) = PN
pn

{-------------------------------------------------------------------------------
  Reverse dependency map
-------------------------------------------------------------------------------}

-- | A map containing reverse dependencies between qualified
-- package names.
type RevDepMap = Map QPN [(Component, QPN)]

{-------------------------------------------------------------------------------
  Goals
-------------------------------------------------------------------------------}

-- | A goal is just a solver variable paired with a reason.
-- The reason is only used for tracing.
data Goal qpn = Goal (Var qpn) (GoalReason qpn)
  deriving (Goal qpn -> Goal qpn -> Bool
forall qpn. Eq qpn => Goal qpn -> Goal qpn -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Goal qpn -> Goal qpn -> Bool
$c/= :: forall qpn. Eq qpn => Goal qpn -> Goal qpn -> Bool
== :: Goal qpn -> Goal qpn -> Bool
$c== :: forall qpn. Eq qpn => Goal qpn -> Goal qpn -> Bool
Eq, Int -> Goal qpn -> ShowS
forall qpn. Show qpn => Int -> Goal qpn -> ShowS
forall qpn. Show qpn => [Goal qpn] -> ShowS
forall qpn. Show qpn => Goal qpn -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Goal qpn] -> ShowS
$cshowList :: forall qpn. Show qpn => [Goal qpn] -> ShowS
show :: Goal qpn -> String
$cshow :: forall qpn. Show qpn => Goal qpn -> String
showsPrec :: Int -> Goal qpn -> ShowS
$cshowsPrec :: forall qpn. Show qpn => Int -> Goal qpn -> ShowS
Show, forall a b. a -> Goal b -> Goal a
forall a b. (a -> b) -> Goal a -> Goal b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: forall a b. a -> Goal b -> Goal a
$c<$ :: forall a b. a -> Goal b -> Goal a
fmap :: forall a b. (a -> b) -> Goal a -> Goal b
$cfmap :: forall a b. (a -> b) -> Goal a -> Goal b
Functor)

-- | Reason why a goal is being added to a goal set.
data GoalReason qpn =
    UserGoal                              -- introduced by a build target
  | DependencyGoal (DependencyReason qpn) -- introduced by a package
  deriving (GoalReason qpn -> GoalReason qpn -> Bool
forall qpn. Eq qpn => GoalReason qpn -> GoalReason qpn -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: GoalReason qpn -> GoalReason qpn -> Bool
$c/= :: forall qpn. Eq qpn => GoalReason qpn -> GoalReason qpn -> Bool
== :: GoalReason qpn -> GoalReason qpn -> Bool
$c== :: forall qpn. Eq qpn => GoalReason qpn -> GoalReason qpn -> Bool
Eq, Int -> GoalReason qpn -> ShowS
forall qpn. Show qpn => Int -> GoalReason qpn -> ShowS
forall qpn. Show qpn => [GoalReason qpn] -> ShowS
forall qpn. Show qpn => GoalReason qpn -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [GoalReason qpn] -> ShowS
$cshowList :: forall qpn. Show qpn => [GoalReason qpn] -> ShowS
show :: GoalReason qpn -> String
$cshow :: forall qpn. Show qpn => GoalReason qpn -> String
showsPrec :: Int -> GoalReason qpn -> ShowS
$cshowsPrec :: forall qpn. Show qpn => Int -> GoalReason qpn -> ShowS
Show, forall a b. a -> GoalReason b -> GoalReason a
forall a b. (a -> b) -> GoalReason a -> GoalReason b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: forall a b. a -> GoalReason b -> GoalReason a
$c<$ :: forall a b. a -> GoalReason b -> GoalReason a
fmap :: forall a b. (a -> b) -> GoalReason a -> GoalReason b
$cfmap :: forall a b. (a -> b) -> GoalReason a -> GoalReason b
Functor)

type QGoalReason = GoalReason QPN

goalToVar :: Goal a -> Var a
goalToVar :: forall a. Goal a -> Var a
goalToVar (Goal Var a
v GoalReason a
_) = Var a
v

-- | Compute a singleton conflict set from a 'Var'
varToConflictSet :: Var QPN -> ConflictSet
varToConflictSet :: Var QPN -> ConflictSet
varToConflictSet = Var QPN -> ConflictSet
CS.singleton

-- | Convert a 'GoalReason' to a 'ConflictSet' that can be used when the goal
-- leads to a conflict.
goalReasonToConflictSet :: GoalReason QPN -> ConflictSet
goalReasonToConflictSet :: GoalReason QPN -> ConflictSet
goalReasonToConflictSet GoalReason QPN
UserGoal            = ConflictSet
CS.empty
goalReasonToConflictSet (DependencyGoal DependencyReason QPN
dr) = DependencyReason QPN -> ConflictSet
dependencyReasonToConflictSet DependencyReason QPN
dr

-- | Convert a 'GoalReason' to a 'ConflictSet' containing the reason that the
-- conflict occurred, namely the conflict set variables caused a conflict by
-- introducing the given package goal. See the documentation for 'GoalConflict'.
--
-- This function currently only specifies the reason for the conflict in the
-- simple case where the 'GoalReason' does not involve any flags or stanzas.
-- Otherwise, it falls back to calling 'goalReasonToConflictSet'.
goalReasonToConflictSetWithConflict :: QPN -> GoalReason QPN -> ConflictSet
goalReasonToConflictSetWithConflict :: QPN -> GoalReason QPN -> ConflictSet
goalReasonToConflictSetWithConflict QPN
goal (DependencyGoal (DependencyReason QPN
qpn Map Flag FlagValue
flags Set Stanza
stanzas))
  | forall k a. Map k a -> Bool
M.null Map Flag FlagValue
flags Bool -> Bool -> Bool
&& forall a. Set a -> Bool
S.null Set Stanza
stanzas =
      Var QPN -> Conflict -> ConflictSet
CS.singletonWithConflict (forall qpn. qpn -> Var qpn
P QPN
qpn) forall a b. (a -> b) -> a -> b
$ QPN -> Conflict
CS.GoalConflict QPN
goal
goalReasonToConflictSetWithConflict QPN
_    GoalReason QPN
gr = GoalReason QPN -> ConflictSet
goalReasonToConflictSet GoalReason QPN
gr

-- | This function returns the solver variables responsible for the dependency.
-- It drops the values chosen for flag and stanza variables, which are only
-- needed for log messages.
dependencyReasonToConflictSet :: DependencyReason QPN -> ConflictSet
dependencyReasonToConflictSet :: DependencyReason QPN -> ConflictSet
dependencyReasonToConflictSet (DependencyReason QPN
qpn Map Flag FlagValue
flags Set Stanza
stanzas) =
    [Var QPN] -> ConflictSet
CS.fromList forall a b. (a -> b) -> a -> b
$ forall qpn. qpn -> Var qpn
P QPN
qpn forall a. a -> [a] -> [a]
: [Var QPN]
flagVars forall a. [a] -> [a] -> [a]
++ forall a b. (a -> b) -> [a] -> [b]
map Stanza -> Var QPN
stanzaToVar (forall a. Set a -> [a]
S.toList Set Stanza
stanzas)
  where
    -- Filter out any flags that introduced the dependency with both values.
    -- They don't need to be included in the conflict set, because changing the
    -- flag value can't remove the dependency.
    flagVars :: [Var QPN]
    flagVars :: [Var QPN]
flagVars = [forall qpn. FN qpn -> Var qpn
F (forall qpn. qpn -> Flag -> FN qpn
FN QPN
qpn Flag
fn) | (Flag
fn, FlagValue
fv) <- forall k a. Map k a -> [(k, a)]
M.toList Map Flag FlagValue
flags, FlagValue
fv forall a. Eq a => a -> a -> Bool
/= FlagValue
FlagBoth]

    stanzaToVar :: Stanza -> Var QPN
    stanzaToVar :: Stanza -> Var QPN
stanzaToVar = forall qpn. SN qpn -> Var qpn
S forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall qpn. qpn -> Stanza -> SN qpn
SN QPN
qpn

-- | Convert a 'DependencyReason' to a 'ConflictSet' specifying that the
-- conflict occurred because the conflict set variables introduced a problematic
-- version constraint. See the documentation for 'VersionConstraintConflict'.
--
-- This function currently only specifies the reason for the conflict in the
-- simple case where the 'DependencyReason' does not involve any flags or
-- stanzas. Otherwise, it falls back to calling 'dependencyReasonToConflictSet'.
dependencyReasonToConflictSetWithVersionConstraintConflict :: QPN
                                                           -> Ver
                                                           -> DependencyReason QPN
                                                           -> ConflictSet
dependencyReasonToConflictSetWithVersionConstraintConflict :: QPN -> Ver -> DependencyReason QPN -> ConflictSet
dependencyReasonToConflictSetWithVersionConstraintConflict
    QPN
dependency Ver
excludedVersion dr :: DependencyReason QPN
dr@(DependencyReason QPN
qpn Map Flag FlagValue
flags Set Stanza
stanzas)
  | forall k a. Map k a -> Bool
M.null Map Flag FlagValue
flags Bool -> Bool -> Bool
&& forall a. Set a -> Bool
S.null Set Stanza
stanzas =
    Var QPN -> Conflict -> ConflictSet
CS.singletonWithConflict (forall qpn. qpn -> Var qpn
P QPN
qpn) forall a b. (a -> b) -> a -> b
$
    QPN -> Ver -> Conflict
CS.VersionConstraintConflict QPN
dependency Ver
excludedVersion
  | Bool
otherwise = DependencyReason QPN -> ConflictSet
dependencyReasonToConflictSet DependencyReason QPN
dr

-- | Convert a 'DependencyReason' to a 'ConflictSet' specifying that the
-- conflict occurred because the conflict set variables introduced a version of
-- a package that was excluded by a version constraint. See the documentation
-- for 'VersionConflict'.
--
-- This function currently only specifies the reason for the conflict in the
-- simple case where the 'DependencyReason' does not involve any flags or
-- stanzas. Otherwise, it falls back to calling 'dependencyReasonToConflictSet'.
dependencyReasonToConflictSetWithVersionConflict :: QPN
                                                 -> CS.OrderedVersionRange
                                                 -> DependencyReason QPN
                                                 -> ConflictSet
dependencyReasonToConflictSetWithVersionConflict :: QPN -> OrderedVersionRange -> DependencyReason QPN -> ConflictSet
dependencyReasonToConflictSetWithVersionConflict
    QPN
pkgWithVersionConstraint OrderedVersionRange
constraint dr :: DependencyReason QPN
dr@(DependencyReason QPN
qpn Map Flag FlagValue
flags Set Stanza
stanzas)
  | forall k a. Map k a -> Bool
M.null Map Flag FlagValue
flags Bool -> Bool -> Bool
&& forall a. Set a -> Bool
S.null Set Stanza
stanzas =
    Var QPN -> Conflict -> ConflictSet
CS.singletonWithConflict (forall qpn. qpn -> Var qpn
P QPN
qpn) forall a b. (a -> b) -> a -> b
$
    QPN -> OrderedVersionRange -> Conflict
CS.VersionConflict QPN
pkgWithVersionConstraint OrderedVersionRange
constraint
  | Bool
otherwise = DependencyReason QPN -> ConflictSet
dependencyReasonToConflictSet DependencyReason QPN
dr