{-# LANGUAGE TypeFamilies #-}
module Distribution.Solver.Modular.Cycles (
detectCyclesPhase
) where
import Prelude hiding (cycle)
import qualified Data.Map as M
import qualified Data.Set as S
import qualified Distribution.Compat.Graph as G
import Distribution.Simple.Utils (ordNub)
import Distribution.Solver.Modular.Dependency
import Distribution.Solver.Modular.Flag
import Distribution.Solver.Modular.Tree
import qualified Distribution.Solver.Modular.ConflictSet as CS
import Distribution.Solver.Types.ComponentDeps (Component)
import Distribution.Solver.Types.PackagePath
detectCyclesPhase :: Tree d c -> Tree d c
detectCyclesPhase :: forall d c. Tree d c -> Tree d c
detectCyclesPhase = Tree d c -> Tree d c
forall d c. Tree d c -> Tree d c
go
where
go :: Tree d c -> Tree d c
go :: forall d c. Tree d c -> Tree d c
go (PChoice Qualified PackageName
qpn RevDepMap
rdm c
gr WeightedPSQ [Weight] POption (Tree d c)
cs) =
Qualified PackageName
-> RevDepMap
-> c
-> WeightedPSQ [Weight] POption (Tree d c)
-> Tree d c
forall d c.
Qualified PackageName
-> RevDepMap
-> c
-> WeightedPSQ [Weight] POption (Tree d c)
-> Tree d c
PChoice Qualified PackageName
qpn RevDepMap
rdm c
gr (WeightedPSQ [Weight] POption (Tree d c) -> Tree d c)
-> WeightedPSQ [Weight] POption (Tree d c) -> Tree d c
forall a b. (a -> b) -> a -> b
$ (Tree d c -> Tree d c)
-> WeightedPSQ [Weight] POption (Tree d c)
-> WeightedPSQ [Weight] POption (Tree d c)
forall a b.
(a -> b)
-> WeightedPSQ [Weight] POption a -> WeightedPSQ [Weight] POption b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Qualified PackageName -> Tree d c -> Tree d c
forall d c. Qualified PackageName -> Tree d c -> Tree d c
checkChild Qualified PackageName
qpn) ((Tree d c -> Tree d c)
-> WeightedPSQ [Weight] POption (Tree d c)
-> WeightedPSQ [Weight] POption (Tree d c)
forall a b.
(a -> b)
-> WeightedPSQ [Weight] POption a -> WeightedPSQ [Weight] POption b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Tree d c -> Tree d c
forall d c. Tree d c -> Tree d c
go WeightedPSQ [Weight] POption (Tree d c)
cs)
go (FChoice qfn :: QFN
qfn@(FN Qualified PackageName
qpn Flag
_) RevDepMap
rdm c
gr WeakOrTrivial
w FlagType
m Bool
d WeightedPSQ [Weight] Bool (Tree d c)
cs) =
QFN
-> RevDepMap
-> c
-> WeakOrTrivial
-> FlagType
-> Bool
-> WeightedPSQ [Weight] Bool (Tree d c)
-> Tree d c
forall d c.
QFN
-> RevDepMap
-> c
-> WeakOrTrivial
-> FlagType
-> Bool
-> WeightedPSQ [Weight] Bool (Tree d c)
-> Tree d c
FChoice QFN
qfn RevDepMap
rdm c
gr WeakOrTrivial
w FlagType
m Bool
d (WeightedPSQ [Weight] Bool (Tree d c) -> Tree d c)
-> WeightedPSQ [Weight] Bool (Tree d c) -> Tree d c
forall a b. (a -> b) -> a -> b
$ (Tree d c -> Tree d c)
-> WeightedPSQ [Weight] Bool (Tree d c)
-> WeightedPSQ [Weight] Bool (Tree d c)
forall a b.
(a -> b)
-> WeightedPSQ [Weight] Bool a -> WeightedPSQ [Weight] Bool b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Qualified PackageName -> Tree d c -> Tree d c
forall d c. Qualified PackageName -> Tree d c -> Tree d c
checkChild Qualified PackageName
qpn) ((Tree d c -> Tree d c)
-> WeightedPSQ [Weight] Bool (Tree d c)
-> WeightedPSQ [Weight] Bool (Tree d c)
forall a b.
(a -> b)
-> WeightedPSQ [Weight] Bool a -> WeightedPSQ [Weight] Bool b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Tree d c -> Tree d c
forall d c. Tree d c -> Tree d c
go WeightedPSQ [Weight] Bool (Tree d c)
cs)
go (SChoice qsn :: QSN
qsn@(SN Qualified PackageName
qpn Stanza
_) RevDepMap
rdm c
gr WeakOrTrivial
w WeightedPSQ [Weight] Bool (Tree d c)
cs) =
QSN
-> RevDepMap
-> c
-> WeakOrTrivial
-> WeightedPSQ [Weight] Bool (Tree d c)
-> Tree d c
forall d c.
QSN
-> RevDepMap
-> c
-> WeakOrTrivial
-> WeightedPSQ [Weight] Bool (Tree d c)
-> Tree d c
SChoice QSN
qsn RevDepMap
rdm c
gr WeakOrTrivial
w (WeightedPSQ [Weight] Bool (Tree d c) -> Tree d c)
-> WeightedPSQ [Weight] Bool (Tree d c) -> Tree d c
forall a b. (a -> b) -> a -> b
$ (Tree d c -> Tree d c)
-> WeightedPSQ [Weight] Bool (Tree d c)
-> WeightedPSQ [Weight] Bool (Tree d c)
forall a b.
(a -> b)
-> WeightedPSQ [Weight] Bool a -> WeightedPSQ [Weight] Bool b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Qualified PackageName -> Tree d c -> Tree d c
forall d c. Qualified PackageName -> Tree d c -> Tree d c
checkChild Qualified PackageName
qpn) ((Tree d c -> Tree d c)
-> WeightedPSQ [Weight] Bool (Tree d c)
-> WeightedPSQ [Weight] Bool (Tree d c)
forall a b.
(a -> b)
-> WeightedPSQ [Weight] Bool a -> WeightedPSQ [Weight] Bool b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Tree d c -> Tree d c
forall d c. Tree d c -> Tree d c
go WeightedPSQ [Weight] Bool (Tree d c)
cs)
go (GoalChoice RevDepMap
rdm PSQ (Goal (Qualified PackageName)) (Tree d c)
cs) = RevDepMap
-> PSQ (Goal (Qualified PackageName)) (Tree d c) -> Tree d c
forall d c.
RevDepMap
-> PSQ (Goal (Qualified PackageName)) (Tree d c) -> Tree d c
GoalChoice RevDepMap
rdm ((Tree d c -> Tree d c)
-> PSQ (Goal (Qualified PackageName)) (Tree d c)
-> PSQ (Goal (Qualified PackageName)) (Tree d c)
forall a b.
(a -> b)
-> PSQ (Goal (Qualified PackageName)) a
-> PSQ (Goal (Qualified PackageName)) b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Tree d c -> Tree d c
forall d c. Tree d c -> Tree d c
go PSQ (Goal (Qualified PackageName)) (Tree d c)
cs)
go x :: Tree d c
x@(Fail ConflictSet
_ FailReason
_) = Tree d c
x
go x :: Tree d c
x@(Done RevDepMap
_ d
_) = Tree d c
x
checkChild :: QPN -> Tree d c -> Tree d c
checkChild :: forall d c. Qualified PackageName -> Tree d c -> Tree d c
checkChild Qualified PackageName
qpn x :: Tree d c
x@(PChoice Qualified PackageName
_ RevDepMap
rdm c
_ WeightedPSQ [Weight] POption (Tree d c)
_) = Qualified PackageName -> RevDepMap -> Tree d c -> Tree d c
forall d c.
Qualified PackageName -> RevDepMap -> Tree d c -> Tree d c
failIfCycle Qualified PackageName
qpn RevDepMap
rdm Tree d c
x
checkChild Qualified PackageName
qpn x :: Tree d c
x@(FChoice QFN
_ RevDepMap
rdm c
_ WeakOrTrivial
_ FlagType
_ Bool
_ WeightedPSQ [Weight] Bool (Tree d c)
_) = Qualified PackageName -> RevDepMap -> Tree d c -> Tree d c
forall d c.
Qualified PackageName -> RevDepMap -> Tree d c -> Tree d c
failIfCycle Qualified PackageName
qpn RevDepMap
rdm Tree d c
x
checkChild Qualified PackageName
qpn x :: Tree d c
x@(SChoice QSN
_ RevDepMap
rdm c
_ WeakOrTrivial
_ WeightedPSQ [Weight] Bool (Tree d c)
_) = Qualified PackageName -> RevDepMap -> Tree d c -> Tree d c
forall d c.
Qualified PackageName -> RevDepMap -> Tree d c -> Tree d c
failIfCycle Qualified PackageName
qpn RevDepMap
rdm Tree d c
x
checkChild Qualified PackageName
qpn x :: Tree d c
x@(GoalChoice RevDepMap
rdm PSQ (Goal (Qualified PackageName)) (Tree d c)
_) = Qualified PackageName -> RevDepMap -> Tree d c -> Tree d c
forall d c.
Qualified PackageName -> RevDepMap -> Tree d c -> Tree d c
failIfCycle Qualified PackageName
qpn RevDepMap
rdm Tree d c
x
checkChild Qualified PackageName
_ x :: Tree d c
x@(Fail ConflictSet
_ FailReason
_) = Tree d c
x
checkChild Qualified PackageName
qpn x :: Tree d c
x@(Done RevDepMap
rdm d
_) = Qualified PackageName -> RevDepMap -> Tree d c -> Tree d c
forall d c.
Qualified PackageName -> RevDepMap -> Tree d c -> Tree d c
failIfCycle Qualified PackageName
qpn RevDepMap
rdm Tree d c
x
failIfCycle :: QPN -> RevDepMap -> Tree d c -> Tree d c
failIfCycle :: forall d c.
Qualified PackageName -> RevDepMap -> Tree d c -> Tree d c
failIfCycle Qualified PackageName
qpn RevDepMap
rdm Tree d c
x =
case Qualified PackageName -> RevDepMap -> Maybe ConflictSet
findCycles Qualified PackageName
qpn RevDepMap
rdm of
Maybe ConflictSet
Nothing -> Tree d c
x
Just ConflictSet
relSet -> ConflictSet -> FailReason -> Tree d c
forall d c. ConflictSet -> FailReason -> Tree d c
Fail ConflictSet
relSet FailReason
CyclicDependencies
findCycles :: QPN -> RevDepMap -> Maybe ConflictSet
findCycles :: Qualified PackageName -> RevDepMap -> Maybe ConflictSet
findCycles Qualified PackageName
pkg RevDepMap
rdm =
if Bool
hasCycle
then let scc :: G.Graph RevDepMapNode
scc :: Graph RevDepMapNode
scc = case Graph RevDepMapNode -> [[RevDepMapNode]]
forall a. Graph a -> [[a]]
G.cycles (Graph RevDepMapNode -> [[RevDepMapNode]])
-> Graph RevDepMapNode -> [[RevDepMapNode]]
forall a b. (a -> b) -> a -> b
$ RevDepMap -> Graph RevDepMapNode
revDepMapToGraph RevDepMap
rdm of
[] -> [Char] -> Graph RevDepMapNode
forall {c}. [Char] -> c
findCyclesError [Char]
"cannot find a strongly connected component"
[RevDepMapNode]
c : [[RevDepMapNode]]
_ -> [RevDepMapNode] -> Graph RevDepMapNode
forall a. (IsNode a, Show (Key a)) => [a] -> Graph a
G.fromDistinctList [RevDepMapNode]
c
next :: QPN -> QPN
next :: Qualified PackageName -> Qualified PackageName
next Qualified PackageName
p = case Graph RevDepMapNode -> Key RevDepMapNode -> Maybe [RevDepMapNode]
forall a. Graph a -> Key a -> Maybe [a]
G.neighbors Graph RevDepMapNode
scc Key RevDepMapNode
Qualified PackageName
p of
Just (RevDepMapNode
n : [RevDepMapNode]
_) -> RevDepMapNode -> Key RevDepMapNode
forall a. IsNode a => a -> Key a
G.nodeKey RevDepMapNode
n
Maybe [RevDepMapNode]
_ -> [Char] -> Qualified PackageName
forall {c}. [Char] -> c
findCyclesError [Char]
"cannot find next node in the cycle"
oneCycle :: [QPN]
oneCycle :: [Qualified PackageName]
oneCycle = case (Qualified PackageName -> Qualified PackageName)
-> Qualified PackageName -> [Qualified PackageName]
forall a. (a -> a) -> a -> [a]
iterate Qualified PackageName -> Qualified PackageName
next Qualified PackageName
pkg of
[] -> [Char] -> [Qualified PackageName]
forall {c}. [Char] -> c
findCyclesError [Char]
"empty cycle"
Qualified PackageName
x : [Qualified PackageName]
xs -> Qualified PackageName
x Qualified PackageName
-> [Qualified PackageName] -> [Qualified PackageName]
forall a. a -> [a] -> [a]
: (Qualified PackageName -> Bool)
-> [Qualified PackageName] -> [Qualified PackageName]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (Qualified PackageName -> Qualified PackageName -> Bool
forall a. Eq a => a -> a -> Bool
/= Qualified PackageName
x) [Qualified PackageName]
xs
in ConflictSet -> Maybe ConflictSet
forall a. a -> Maybe a
Just (ConflictSet -> Maybe ConflictSet)
-> ConflictSet -> Maybe ConflictSet
forall a b. (a -> b) -> a -> b
$ [Var (Qualified PackageName)] -> ConflictSet
CS.fromList ([Var (Qualified PackageName)] -> ConflictSet)
-> [Var (Qualified PackageName)] -> ConflictSet
forall a b. (a -> b) -> a -> b
$ (Qualified PackageName -> Var (Qualified PackageName))
-> [Qualified PackageName] -> [Var (Qualified PackageName)]
forall a b. (a -> b) -> [a] -> [b]
map Qualified PackageName -> Var (Qualified PackageName)
forall qpn. qpn -> Var qpn
P [Qualified PackageName]
oneCycle
else Maybe ConflictSet
forall a. Maybe a
Nothing
where
hasCycle :: Bool
hasCycle :: Bool
hasCycle = Qualified PackageName
pkg Qualified PackageName -> Set (Qualified PackageName) -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.member` [Qualified PackageName] -> Set (Qualified PackageName)
closure (Qualified PackageName -> [Qualified PackageName]
neighbors Qualified PackageName
pkg)
closure :: [QPN] -> S.Set QPN
closure :: [Qualified PackageName] -> Set (Qualified PackageName)
closure = (Set (Qualified PackageName)
-> Qualified PackageName -> Set (Qualified PackageName))
-> Set (Qualified PackageName)
-> [Qualified PackageName]
-> Set (Qualified PackageName)
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl Set (Qualified PackageName)
-> Qualified PackageName -> Set (Qualified PackageName)
go Set (Qualified PackageName)
forall a. Set a
S.empty
where
go :: S.Set QPN -> QPN -> S.Set QPN
go :: Set (Qualified PackageName)
-> Qualified PackageName -> Set (Qualified PackageName)
go Set (Qualified PackageName)
s Qualified PackageName
x =
if Qualified PackageName
x Qualified PackageName -> Set (Qualified PackageName) -> Bool
forall a. Ord a => a -> Set a -> Bool
`S.member` Set (Qualified PackageName)
s
then Set (Qualified PackageName)
s
else (Set (Qualified PackageName)
-> Qualified PackageName -> Set (Qualified PackageName))
-> Set (Qualified PackageName)
-> [Qualified PackageName]
-> Set (Qualified PackageName)
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl Set (Qualified PackageName)
-> Qualified PackageName -> Set (Qualified PackageName)
go (Qualified PackageName
-> Set (Qualified PackageName) -> Set (Qualified PackageName)
forall a. Ord a => a -> Set a -> Set a
S.insert Qualified PackageName
x Set (Qualified PackageName)
s) ([Qualified PackageName] -> Set (Qualified PackageName))
-> [Qualified PackageName] -> Set (Qualified PackageName)
forall a b. (a -> b) -> a -> b
$ Qualified PackageName -> [Qualified PackageName]
neighbors Qualified PackageName
x
neighbors :: QPN -> [QPN]
neighbors :: Qualified PackageName -> [Qualified PackageName]
neighbors Qualified PackageName
x = case Qualified PackageName
x Qualified PackageName
-> RevDepMap -> Maybe [(Component, Qualified PackageName)]
forall k a. Ord k => k -> Map k a -> Maybe a
`M.lookup` RevDepMap
rdm of
Maybe [(Component, Qualified PackageName)]
Nothing -> [Char] -> [Qualified PackageName]
forall {c}. [Char] -> c
findCyclesError [Char]
"cannot find node"
Just [(Component, Qualified PackageName)]
xs -> ((Component, Qualified PackageName) -> Qualified PackageName)
-> [(Component, Qualified PackageName)] -> [Qualified PackageName]
forall a b. (a -> b) -> [a] -> [b]
map (Component, Qualified PackageName) -> Qualified PackageName
forall a b. (a, b) -> b
snd [(Component, Qualified PackageName)]
xs
findCyclesError :: [Char] -> c
findCyclesError = [Char] -> c
forall a. HasCallStack => [Char] -> a
error ([Char] -> c) -> ([Char] -> [Char]) -> [Char] -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([Char]
"Distribution.Solver.Modular.Cycles.findCycles: " [Char] -> [Char] -> [Char]
forall a. [a] -> [a] -> [a]
++)
data RevDepMapNode = RevDepMapNode QPN [(Component, QPN)]
instance G.IsNode RevDepMapNode where
type Key RevDepMapNode = QPN
nodeKey :: RevDepMapNode -> Key RevDepMapNode
nodeKey (RevDepMapNode Qualified PackageName
qpn [(Component, Qualified PackageName)]
_) = Key RevDepMapNode
Qualified PackageName
qpn
nodeNeighbors :: RevDepMapNode -> [Key RevDepMapNode]
nodeNeighbors (RevDepMapNode Qualified PackageName
_ [(Component, Qualified PackageName)]
ns) = [Key RevDepMapNode] -> [Key RevDepMapNode]
forall a. Ord a => [a] -> [a]
ordNub ([Key RevDepMapNode] -> [Key RevDepMapNode])
-> [Key RevDepMapNode] -> [Key RevDepMapNode]
forall a b. (a -> b) -> a -> b
$ ((Component, Qualified PackageName) -> Key RevDepMapNode)
-> [(Component, Qualified PackageName)] -> [Key RevDepMapNode]
forall a b. (a -> b) -> [a] -> [b]
map (Component, Qualified PackageName) -> Key RevDepMapNode
(Component, Qualified PackageName) -> Qualified PackageName
forall a b. (a, b) -> b
snd [(Component, Qualified PackageName)]
ns
revDepMapToGraph :: RevDepMap -> G.Graph RevDepMapNode
revDepMapToGraph :: RevDepMap -> Graph RevDepMapNode
revDepMapToGraph RevDepMap
rdm = [RevDepMapNode] -> Graph RevDepMapNode
forall a. (IsNode a, Show (Key a)) => [a] -> Graph a
G.fromDistinctList
[Qualified PackageName
-> [(Component, Qualified PackageName)] -> RevDepMapNode
RevDepMapNode Qualified PackageName
qpn [(Component, Qualified PackageName)]
ns | (Qualified PackageName
qpn, [(Component, Qualified PackageName)]
ns) <- RevDepMap
-> [(Qualified PackageName, [(Component, Qualified PackageName)])]
forall k a. Map k a -> [(k, a)]
M.toList RevDepMap
rdm]