{-# LANGUAGE LambdaCase      #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE DeriveTraversable #-}

module GHC.Unit.Module.Graph
   ( ModuleGraph
   , ModuleGraphNode(..)
   , nodeDependencies
   , emptyMG
   , mkModuleGraph
   , extendMG
   , extendMGInst
   , extendMG'
   , unionMG
   , isTemplateHaskellOrQQNonBoot
   , filterToposortToModules
   , mapMG
   , mgModSummaries
   , mgModSummaries'
   , mgLookupModule
   , mgTransDeps
   , showModMsg
   , moduleGraphNodeModule
   , moduleGraphNodeModSum

   , moduleGraphNodes
   , SummaryNode
   , summaryNodeSummary

   , NodeKey(..)
   , nodeKeyUnitId
   , nodeKeyModName
   , ModNodeKey
   , mkNodeKey
   , msKey


   , moduleGraphNodeUnitId

   , ModNodeKeyWithUid(..)
   )
where

import GHC.Prelude
import GHC.Platform

import qualified GHC.LanguageExtensions as LangExt

import GHC.Data.Maybe
import GHC.Data.Graph.Directed

import GHC.Driver.Backend
import GHC.Driver.Session

import GHC.Types.SourceFile ( hscSourceString )

import GHC.Unit.Module.ModSummary
import GHC.Unit.Types
import GHC.Utils.Outputable

import System.FilePath
import qualified Data.Map as Map
import GHC.Types.Unique.DSet
import qualified Data.Set as Set
import GHC.Unit.Module
import GHC.Linker.Static.Utils

import Data.Bifunctor
import Data.Either
import Data.Function
import GHC.Data.List.SetOps

-- | A '@ModuleGraphNode@' is a node in the '@ModuleGraph@'.
-- Edges between nodes mark dependencies arising from module imports
-- and dependencies arising from backpack instantiations.
data ModuleGraphNode
  -- | Instantiation nodes track the instantiation of other units
  -- (backpack dependencies) with the holes (signatures) of the current package.
  = InstantiationNode UnitId InstantiatedUnit
  -- | There is a module summary node for each module, signature, and boot module being built.
  | ModuleNode [NodeKey] ModSummary
  -- | Link nodes are whether are are creating a linked product (ie executable/shared object etc) for a unit.
  | LinkNode [NodeKey] UnitId

moduleGraphNodeModule :: ModuleGraphNode -> Maybe ModuleName
moduleGraphNodeModule :: ModuleGraphNode -> Maybe ModuleName
moduleGraphNodeModule ModuleGraphNode
mgn = ModSummary -> ModuleName
ms_mod_name forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (ModuleGraphNode -> Maybe ModSummary
moduleGraphNodeModSum ModuleGraphNode
mgn)

moduleGraphNodeModSum :: ModuleGraphNode -> Maybe ModSummary
moduleGraphNodeModSum :: ModuleGraphNode -> Maybe ModSummary
moduleGraphNodeModSum (InstantiationNode {}) = forall a. Maybe a
Nothing
moduleGraphNodeModSum (LinkNode {})          = forall a. Maybe a
Nothing
moduleGraphNodeModSum (ModuleNode [NodeKey]
_ ModSummary
ms)      = forall a. a -> Maybe a
Just ModSummary
ms

moduleGraphNodeUnitId :: ModuleGraphNode -> UnitId
moduleGraphNodeUnitId :: ModuleGraphNode -> UnitId
moduleGraphNodeUnitId ModuleGraphNode
mgn =
  case ModuleGraphNode
mgn of
    InstantiationNode UnitId
uid InstantiatedUnit
_iud -> UnitId
uid
    ModuleNode [NodeKey]
_ ModSummary
ms           -> GenUnit UnitId -> UnitId
toUnitId (forall unit. GenModule unit -> unit
moduleUnit (ModSummary -> Module
ms_mod ModSummary
ms))
    LinkNode [NodeKey]
_ UnitId
uid             -> UnitId
uid

instance Outputable ModuleGraphNode where
  ppr :: ModuleGraphNode -> SDoc
ppr = \case
    InstantiationNode UnitId
_ InstantiatedUnit
iuid -> forall a. Outputable a => a -> SDoc
ppr InstantiatedUnit
iuid
    ModuleNode [NodeKey]
nks ModSummary
ms -> forall a. Outputable a => a -> SDoc
ppr (ModSummary -> ModNodeKeyWithUid
msKey ModSummary
ms) forall doc. IsLine doc => doc -> doc -> doc
<+> forall a. Outputable a => a -> SDoc
ppr [NodeKey]
nks
    LinkNode [NodeKey]
uid UnitId
_     -> forall doc. IsLine doc => String -> doc
text String
"LN:" forall doc. IsLine doc => doc -> doc -> doc
<+> forall a. Outputable a => a -> SDoc
ppr [NodeKey]
uid

instance Eq ModuleGraphNode where
  == :: ModuleGraphNode -> ModuleGraphNode -> Bool
(==) = forall a. Eq a => a -> a -> Bool
(==) forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` ModuleGraphNode -> NodeKey
mkNodeKey

instance Ord ModuleGraphNode where
  compare :: ModuleGraphNode -> ModuleGraphNode -> Ordering
compare = forall a. Ord a => a -> a -> Ordering
compare forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` ModuleGraphNode -> NodeKey
mkNodeKey

data NodeKey = NodeKey_Unit {-# UNPACK #-} !InstantiatedUnit
             | NodeKey_Module {-# UNPACK #-} !ModNodeKeyWithUid
             | NodeKey_Link !UnitId
  deriving (NodeKey -> NodeKey -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: NodeKey -> NodeKey -> Bool
$c/= :: NodeKey -> NodeKey -> Bool
== :: NodeKey -> NodeKey -> Bool
$c== :: NodeKey -> NodeKey -> Bool
Eq, Eq NodeKey
NodeKey -> NodeKey -> Bool
NodeKey -> NodeKey -> Ordering
NodeKey -> NodeKey -> NodeKey
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 :: NodeKey -> NodeKey -> NodeKey
$cmin :: NodeKey -> NodeKey -> NodeKey
max :: NodeKey -> NodeKey -> NodeKey
$cmax :: NodeKey -> NodeKey -> NodeKey
>= :: NodeKey -> NodeKey -> Bool
$c>= :: NodeKey -> NodeKey -> Bool
> :: NodeKey -> NodeKey -> Bool
$c> :: NodeKey -> NodeKey -> Bool
<= :: NodeKey -> NodeKey -> Bool
$c<= :: NodeKey -> NodeKey -> Bool
< :: NodeKey -> NodeKey -> Bool
$c< :: NodeKey -> NodeKey -> Bool
compare :: NodeKey -> NodeKey -> Ordering
$ccompare :: NodeKey -> NodeKey -> Ordering
Ord)

instance Outputable NodeKey where
  ppr :: NodeKey -> SDoc
ppr NodeKey
nk = NodeKey -> SDoc
pprNodeKey NodeKey
nk

pprNodeKey :: NodeKey -> SDoc
pprNodeKey :: NodeKey -> SDoc
pprNodeKey (NodeKey_Unit InstantiatedUnit
iu) = forall a. Outputable a => a -> SDoc
ppr InstantiatedUnit
iu
pprNodeKey (NodeKey_Module ModNodeKeyWithUid
mk) = forall a. Outputable a => a -> SDoc
ppr ModNodeKeyWithUid
mk
pprNodeKey (NodeKey_Link UnitId
uid)  = forall a. Outputable a => a -> SDoc
ppr UnitId
uid

nodeKeyUnitId :: NodeKey -> UnitId
nodeKeyUnitId :: NodeKey -> UnitId
nodeKeyUnitId (NodeKey_Unit InstantiatedUnit
iu)   = forall unit. GenInstantiatedUnit unit -> unit
instUnitInstanceOf InstantiatedUnit
iu
nodeKeyUnitId (NodeKey_Module ModNodeKeyWithUid
mk) = ModNodeKeyWithUid -> UnitId
mnkUnitId ModNodeKeyWithUid
mk
nodeKeyUnitId (NodeKey_Link UnitId
uid)  = UnitId
uid

nodeKeyModName :: NodeKey -> Maybe ModuleName
nodeKeyModName :: NodeKey -> Maybe ModuleName
nodeKeyModName (NodeKey_Module ModNodeKeyWithUid
mk) = forall a. a -> Maybe a
Just (forall mod. GenWithIsBoot mod -> mod
gwib_mod forall a b. (a -> b) -> a -> b
$ ModNodeKeyWithUid -> ModuleNameWithIsBoot
mnkModuleName ModNodeKeyWithUid
mk)
nodeKeyModName NodeKey
_ = forall a. Maybe a
Nothing

data ModNodeKeyWithUid = ModNodeKeyWithUid { ModNodeKeyWithUid -> ModuleNameWithIsBoot
mnkModuleName :: !ModuleNameWithIsBoot
                                           , ModNodeKeyWithUid -> UnitId
mnkUnitId     :: !UnitId } deriving (ModNodeKeyWithUid -> ModNodeKeyWithUid -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: ModNodeKeyWithUid -> ModNodeKeyWithUid -> Bool
$c/= :: ModNodeKeyWithUid -> ModNodeKeyWithUid -> Bool
== :: ModNodeKeyWithUid -> ModNodeKeyWithUid -> Bool
$c== :: ModNodeKeyWithUid -> ModNodeKeyWithUid -> Bool
Eq, Eq ModNodeKeyWithUid
ModNodeKeyWithUid -> ModNodeKeyWithUid -> Bool
ModNodeKeyWithUid -> ModNodeKeyWithUid -> Ordering
ModNodeKeyWithUid -> ModNodeKeyWithUid -> ModNodeKeyWithUid
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 :: ModNodeKeyWithUid -> ModNodeKeyWithUid -> ModNodeKeyWithUid
$cmin :: ModNodeKeyWithUid -> ModNodeKeyWithUid -> ModNodeKeyWithUid
max :: ModNodeKeyWithUid -> ModNodeKeyWithUid -> ModNodeKeyWithUid
$cmax :: ModNodeKeyWithUid -> ModNodeKeyWithUid -> ModNodeKeyWithUid
>= :: ModNodeKeyWithUid -> ModNodeKeyWithUid -> Bool
$c>= :: ModNodeKeyWithUid -> ModNodeKeyWithUid -> Bool
> :: ModNodeKeyWithUid -> ModNodeKeyWithUid -> Bool
$c> :: ModNodeKeyWithUid -> ModNodeKeyWithUid -> Bool
<= :: ModNodeKeyWithUid -> ModNodeKeyWithUid -> Bool
$c<= :: ModNodeKeyWithUid -> ModNodeKeyWithUid -> Bool
< :: ModNodeKeyWithUid -> ModNodeKeyWithUid -> Bool
$c< :: ModNodeKeyWithUid -> ModNodeKeyWithUid -> Bool
compare :: ModNodeKeyWithUid -> ModNodeKeyWithUid -> Ordering
$ccompare :: ModNodeKeyWithUid -> ModNodeKeyWithUid -> Ordering
Ord)

instance Outputable ModNodeKeyWithUid where
  ppr :: ModNodeKeyWithUid -> SDoc
ppr (ModNodeKeyWithUid ModuleNameWithIsBoot
mnwib UnitId
uid) = forall a. Outputable a => a -> SDoc
ppr UnitId
uid forall doc. IsLine doc => doc -> doc -> doc
<> forall doc. IsLine doc => doc
colon forall doc. IsLine doc => doc -> doc -> doc
<> forall a. Outputable a => a -> SDoc
ppr ModuleNameWithIsBoot
mnwib

-- | A '@ModuleGraph@' contains all the nodes from the home package (only). See
-- '@ModuleGraphNode@' for information about the nodes.
--
-- Modules need to be compiled. hs-boots need to be typechecked before
-- the associated "real" module so modules with {-# SOURCE #-} imports can be
-- built. Instantiations also need to be typechecked to ensure that the module
-- fits the signature. Substantiation typechecking is roughly comparable to the
-- check that the module and its hs-boot agree.
--
-- The graph is not necessarily stored in topologically-sorted order.  Use
-- 'GHC.topSortModuleGraph' and 'GHC.Data.Graph.Directed.flattenSCC' to achieve this.
data ModuleGraph = ModuleGraph
  { ModuleGraph -> [ModuleGraphNode]
mg_mss :: [ModuleGraphNode]
  , ModuleGraph -> Map NodeKey (Set NodeKey)
mg_trans_deps :: Map.Map NodeKey (Set.Set NodeKey)
    -- A cached transitive dependency calculation so that a lot of work is not
    -- repeated whenever the transitive dependencies need to be calculated (for example, hptInstances)
  }

-- | Map a function 'f' over all the 'ModSummaries'.
-- To preserve invariants 'f' can't change the isBoot status.
mapMG :: (ModSummary -> ModSummary) -> ModuleGraph -> ModuleGraph
mapMG :: (ModSummary -> ModSummary) -> ModuleGraph -> ModuleGraph
mapMG ModSummary -> ModSummary
f mg :: ModuleGraph
mg@ModuleGraph{[ModuleGraphNode]
Map NodeKey (Set NodeKey)
mg_trans_deps :: Map NodeKey (Set NodeKey)
mg_mss :: [ModuleGraphNode]
mg_trans_deps :: ModuleGraph -> Map NodeKey (Set NodeKey)
mg_mss :: ModuleGraph -> [ModuleGraphNode]
..} = ModuleGraph
mg
  { mg_mss :: [ModuleGraphNode]
mg_mss = forall a b c. (a -> b -> c) -> b -> a -> c
flip forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [ModuleGraphNode]
mg_mss forall a b. (a -> b) -> a -> b
$ \case
      InstantiationNode UnitId
uid InstantiatedUnit
iuid -> UnitId -> InstantiatedUnit -> ModuleGraphNode
InstantiationNode UnitId
uid InstantiatedUnit
iuid
      LinkNode [NodeKey]
uid UnitId
nks -> [NodeKey] -> UnitId -> ModuleGraphNode
LinkNode [NodeKey]
uid UnitId
nks
      ModuleNode [NodeKey]
deps ModSummary
ms  -> [NodeKey] -> ModSummary -> ModuleGraphNode
ModuleNode [NodeKey]
deps (ModSummary -> ModSummary
f ModSummary
ms)
  }

unionMG :: ModuleGraph -> ModuleGraph -> ModuleGraph
unionMG :: ModuleGraph -> ModuleGraph -> ModuleGraph
unionMG ModuleGraph
a ModuleGraph
b =
  let new_mss :: [ModuleGraphNode]
new_mss = forall a. (a -> a -> Ordering) -> [a] -> [a]
nubOrdBy forall a. Ord a => a -> a -> Ordering
compare forall a b. (a -> b) -> a -> b
$ ModuleGraph -> [ModuleGraphNode]
mg_mss ModuleGraph
a forall a. Monoid a => a -> a -> a
`mappend` ModuleGraph -> [ModuleGraphNode]
mg_mss ModuleGraph
b
  in ModuleGraph {
        mg_mss :: [ModuleGraphNode]
mg_mss = [ModuleGraphNode]
new_mss
      , mg_trans_deps :: Map NodeKey (Set NodeKey)
mg_trans_deps = [ModuleGraphNode] -> Map NodeKey (Set NodeKey)
mkTransDeps [ModuleGraphNode]
new_mss
      }


mgTransDeps :: ModuleGraph -> Map.Map NodeKey (Set.Set NodeKey)
mgTransDeps :: ModuleGraph -> Map NodeKey (Set NodeKey)
mgTransDeps = ModuleGraph -> Map NodeKey (Set NodeKey)
mg_trans_deps

mgModSummaries :: ModuleGraph -> [ModSummary]
mgModSummaries :: ModuleGraph -> [ModSummary]
mgModSummaries ModuleGraph
mg = [ ModSummary
m | ModuleNode [NodeKey]
_ ModSummary
m <- ModuleGraph -> [ModuleGraphNode]
mgModSummaries' ModuleGraph
mg ]

mgModSummaries' :: ModuleGraph -> [ModuleGraphNode]
mgModSummaries' :: ModuleGraph -> [ModuleGraphNode]
mgModSummaries' = ModuleGraph -> [ModuleGraphNode]
mg_mss

-- | Look up a ModSummary in the ModuleGraph
-- Looks up the non-boot ModSummary
-- Linear in the size of the module graph
mgLookupModule :: ModuleGraph -> Module -> Maybe ModSummary
mgLookupModule :: ModuleGraph -> Module -> Maybe ModSummary
mgLookupModule ModuleGraph{[ModuleGraphNode]
Map NodeKey (Set NodeKey)
mg_trans_deps :: Map NodeKey (Set NodeKey)
mg_mss :: [ModuleGraphNode]
mg_trans_deps :: ModuleGraph -> Map NodeKey (Set NodeKey)
mg_mss :: ModuleGraph -> [ModuleGraphNode]
..} Module
m = forall a. [a] -> Maybe a
listToMaybe forall a b. (a -> b) -> a -> b
$ forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe ModuleGraphNode -> Maybe ModSummary
go [ModuleGraphNode]
mg_mss
  where
    go :: ModuleGraphNode -> Maybe ModSummary
go (ModuleNode [NodeKey]
_ ModSummary
ms)
      | IsBootInterface
NotBoot <- ModSummary -> IsBootInterface
isBootSummary ModSummary
ms
      , ModSummary -> Module
ms_mod ModSummary
ms forall a. Eq a => a -> a -> Bool
== Module
m
      = forall a. a -> Maybe a
Just ModSummary
ms
    go ModuleGraphNode
_ = forall a. Maybe a
Nothing

emptyMG :: ModuleGraph
emptyMG :: ModuleGraph
emptyMG = [ModuleGraphNode] -> Map NodeKey (Set NodeKey) -> ModuleGraph
ModuleGraph [] forall k a. Map k a
Map.empty

isTemplateHaskellOrQQNonBoot :: ModSummary -> Bool
isTemplateHaskellOrQQNonBoot :: ModSummary -> Bool
isTemplateHaskellOrQQNonBoot ModSummary
ms =
  (Extension -> DynFlags -> Bool
xopt Extension
LangExt.TemplateHaskell (ModSummary -> DynFlags
ms_hspp_opts ModSummary
ms)
    Bool -> Bool -> Bool
|| Extension -> DynFlags -> Bool
xopt Extension
LangExt.QuasiQuotes (ModSummary -> DynFlags
ms_hspp_opts ModSummary
ms)) Bool -> Bool -> Bool
&&
  (ModSummary -> IsBootInterface
isBootSummary ModSummary
ms forall a. Eq a => a -> a -> Bool
== IsBootInterface
NotBoot)

-- | Add an ExtendedModSummary to ModuleGraph. Assumes that the new ModSummary is
-- not an element of the ModuleGraph.
extendMG :: ModuleGraph -> [NodeKey] -> ModSummary -> ModuleGraph
extendMG :: ModuleGraph -> [NodeKey] -> ModSummary -> ModuleGraph
extendMG ModuleGraph{[ModuleGraphNode]
Map NodeKey (Set NodeKey)
mg_trans_deps :: Map NodeKey (Set NodeKey)
mg_mss :: [ModuleGraphNode]
mg_trans_deps :: ModuleGraph -> Map NodeKey (Set NodeKey)
mg_mss :: ModuleGraph -> [ModuleGraphNode]
..} [NodeKey]
deps ModSummary
ms = ModuleGraph
  { mg_mss :: [ModuleGraphNode]
mg_mss = [NodeKey] -> ModSummary -> ModuleGraphNode
ModuleNode [NodeKey]
deps ModSummary
ms forall a. a -> [a] -> [a]
: [ModuleGraphNode]
mg_mss
  , mg_trans_deps :: Map NodeKey (Set NodeKey)
mg_trans_deps = [ModuleGraphNode] -> Map NodeKey (Set NodeKey)
mkTransDeps ([NodeKey] -> ModSummary -> ModuleGraphNode
ModuleNode [NodeKey]
deps ModSummary
ms forall a. a -> [a] -> [a]
: [ModuleGraphNode]
mg_mss)
  }

mkTransDeps :: [ModuleGraphNode] -> Map.Map NodeKey (Set.Set NodeKey)
mkTransDeps :: [ModuleGraphNode] -> Map NodeKey (Set NodeKey)
mkTransDeps [ModuleGraphNode]
mss =
  let (Graph SummaryNode
gg, NodeKey -> Maybe SummaryNode
_lookup_node) = Bool
-> [ModuleGraphNode]
-> (Graph SummaryNode, NodeKey -> Maybe SummaryNode)
moduleGraphNodes Bool
False [ModuleGraphNode]
mss
  in forall key node.
Ord key =>
Graph node -> (node -> key) -> Map key (Set key)
allReachable Graph SummaryNode
gg (ModuleGraphNode -> NodeKey
mkNodeKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall key payload. Node key payload -> payload
node_payload)

extendMGInst :: ModuleGraph -> UnitId -> InstantiatedUnit -> ModuleGraph
extendMGInst :: ModuleGraph -> UnitId -> InstantiatedUnit -> ModuleGraph
extendMGInst ModuleGraph
mg UnitId
uid InstantiatedUnit
depUnitId = ModuleGraph
mg
  { mg_mss :: [ModuleGraphNode]
mg_mss = UnitId -> InstantiatedUnit -> ModuleGraphNode
InstantiationNode UnitId
uid InstantiatedUnit
depUnitId forall a. a -> [a] -> [a]
: ModuleGraph -> [ModuleGraphNode]
mg_mss ModuleGraph
mg
  }

extendMGLink :: ModuleGraph -> UnitId -> [NodeKey] -> ModuleGraph
extendMGLink :: ModuleGraph -> UnitId -> [NodeKey] -> ModuleGraph
extendMGLink ModuleGraph
mg UnitId
uid [NodeKey]
nks = ModuleGraph
mg { mg_mss :: [ModuleGraphNode]
mg_mss = [NodeKey] -> UnitId -> ModuleGraphNode
LinkNode [NodeKey]
nks UnitId
uid forall a. a -> [a] -> [a]
: ModuleGraph -> [ModuleGraphNode]
mg_mss ModuleGraph
mg }

extendMG' :: ModuleGraph -> ModuleGraphNode -> ModuleGraph
extendMG' :: ModuleGraph -> ModuleGraphNode -> ModuleGraph
extendMG' ModuleGraph
mg = \case
  InstantiationNode UnitId
uid InstantiatedUnit
depUnitId -> ModuleGraph -> UnitId -> InstantiatedUnit -> ModuleGraph
extendMGInst ModuleGraph
mg UnitId
uid InstantiatedUnit
depUnitId
  ModuleNode [NodeKey]
deps ModSummary
ms -> ModuleGraph -> [NodeKey] -> ModSummary -> ModuleGraph
extendMG ModuleGraph
mg [NodeKey]
deps ModSummary
ms
  LinkNode [NodeKey]
deps UnitId
uid   -> ModuleGraph -> UnitId -> [NodeKey] -> ModuleGraph
extendMGLink ModuleGraph
mg UnitId
uid [NodeKey]
deps

mkModuleGraph :: [ModuleGraphNode] -> ModuleGraph
mkModuleGraph :: [ModuleGraphNode] -> ModuleGraph
mkModuleGraph = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (forall a b c. (a -> b -> c) -> b -> a -> c
flip ModuleGraph -> ModuleGraphNode -> ModuleGraph
extendMG') ModuleGraph
emptyMG

-- | This function filters out all the instantiation nodes from each SCC of a
-- topological sort. Use this with care, as the resulting "strongly connected components"
-- may not really be strongly connected in a direct way, as instantiations have been
-- removed. It would probably be best to eliminate uses of this function where possible.
filterToposortToModules
  :: [SCC ModuleGraphNode] -> [SCC ModSummary]
filterToposortToModules :: [SCC ModuleGraphNode] -> [SCC ModSummary]
filterToposortToModules = forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe forall a b. (a -> b) -> a -> b
$ forall a b. (a -> Maybe b) -> SCC a -> Maybe (SCC b)
mapMaybeSCC forall a b. (a -> b) -> a -> b
$ \case
  InstantiationNode UnitId
_ InstantiatedUnit
_ -> forall a. Maybe a
Nothing
  LinkNode{} -> forall a. Maybe a
Nothing
  ModuleNode [NodeKey]
_deps ModSummary
node -> forall a. a -> Maybe a
Just ModSummary
node
  where
    -- This higher order function is somewhat bogus,
    -- as the definition of "strongly connected component"
    -- is not necessarily respected.
    mapMaybeSCC :: (a -> Maybe b) -> SCC a -> Maybe (SCC b)
    mapMaybeSCC :: forall a b. (a -> Maybe b) -> SCC a -> Maybe (SCC b)
mapMaybeSCC a -> Maybe b
f = \case
      AcyclicSCC a
a -> forall vertex. vertex -> SCC vertex
AcyclicSCC forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> Maybe b
f a
a
      CyclicSCC [a]
as -> case forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe a -> Maybe b
f [a]
as of
        [] -> forall a. Maybe a
Nothing
        [b
a] -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall vertex. vertex -> SCC vertex
AcyclicSCC b
a
        [b]
as -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall vertex. [vertex] -> SCC vertex
CyclicSCC [b]
as

showModMsg :: DynFlags -> Bool -> ModuleGraphNode -> SDoc
showModMsg :: DynFlags -> Bool -> ModuleGraphNode -> SDoc
showModMsg DynFlags
dflags Bool
_ (LinkNode {}) =
      let staticLink :: Bool
staticLink = case DynFlags -> GhcLink
ghcLink DynFlags
dflags of
                          GhcLink
LinkStaticLib -> Bool
True
                          GhcLink
_ -> Bool
False

          platform :: Platform
platform  = DynFlags -> Platform
targetPlatform DynFlags
dflags
          arch_os :: ArchOS
arch_os   = Platform -> ArchOS
platformArchOS Platform
platform
          exe_file :: String
exe_file  = ArchOS -> Bool -> Maybe String -> String
exeFileName ArchOS
arch_os Bool
staticLink (DynFlags -> Maybe String
outputFile_ DynFlags
dflags)
      in forall doc. IsLine doc => String -> doc
text String
exe_file
showModMsg DynFlags
_ Bool
_ (InstantiationNode UnitId
_uid InstantiatedUnit
indef_unit) =
  forall a. Outputable a => a -> SDoc
ppr forall a b. (a -> b) -> a -> b
$ forall unit. GenInstantiatedUnit unit -> unit
instUnitInstanceOf InstantiatedUnit
indef_unit
showModMsg DynFlags
dflags Bool
recomp (ModuleNode [NodeKey]
_ ModSummary
mod_summary) =
  if GeneralFlag -> DynFlags -> Bool
gopt GeneralFlag
Opt_HideSourcePaths DynFlags
dflags
      then forall doc. IsLine doc => String -> doc
text String
mod_str
      else forall doc. IsLine doc => [doc] -> doc
hsep forall a b. (a -> b) -> a -> b
$
         [ forall doc. IsLine doc => String -> doc
text (String
mod_str forall a. [a] -> [a] -> [a]
++ forall a. Int -> a -> [a]
replicate (forall a. Ord a => a -> a -> a
max Int
0 (Int
16 forall a. Num a => a -> a -> a
- forall (t :: * -> *) a. Foldable t => t a -> Int
length String
mod_str)) Char
' ')
         , forall doc. IsLine doc => Char -> doc
char Char
'('
         , forall doc. IsLine doc => String -> doc
text (String -> String
op forall a b. (a -> b) -> a -> b
$ ModSummary -> String
msHsFilePath ModSummary
mod_summary) forall doc. IsLine doc => doc -> doc -> doc
<> forall doc. IsLine doc => Char -> doc
char Char
','
         , SDoc
message, forall doc. IsLine doc => Char -> doc
char Char
')' ]

  where
    op :: String -> String
op       = String -> String
normalise
    mod_str :: String
mod_str  = ModuleName -> String
moduleNameString (forall unit. GenModule unit -> ModuleName
moduleName (ModSummary -> Module
ms_mod ModSummary
mod_summary)) forall a. [a] -> [a] -> [a]
++
               HscSource -> String
hscSourceString (ModSummary -> HscSource
ms_hsc_src ModSummary
mod_summary)
    dyn_file :: String
dyn_file = String -> String
op forall a b. (a -> b) -> a -> b
$ ModSummary -> String
msDynObjFilePath ModSummary
mod_summary
    obj_file :: String
obj_file = String -> String
op forall a b. (a -> b) -> a -> b
$ ModSummary -> String
msObjFilePath ModSummary
mod_summary
    files :: [String]
files    = [ String
obj_file ]
               forall a. [a] -> [a] -> [a]
++ [ String
dyn_file | GeneralFlag -> DynFlags -> Bool
gopt GeneralFlag
Opt_BuildDynamicToo DynFlags
dflags ]
               forall a. [a] -> [a] -> [a]
++ [ String
"interpreted" | GeneralFlag -> DynFlags -> Bool
gopt GeneralFlag
Opt_ByteCodeAndObjectCode DynFlags
dflags ]
    message :: SDoc
message = case Backend -> Bool -> Maybe String
backendSpecialModuleSource (DynFlags -> Backend
backend DynFlags
dflags) Bool
recomp of
                Just String
special -> forall doc. IsLine doc => String -> doc
text String
special
                Maybe String
Nothing -> forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
foldr1 (\SDoc
ofile SDoc
rest -> SDoc
ofile forall doc. IsLine doc => doc -> doc -> doc
<> forall doc. IsLine doc => doc
comma forall doc. IsLine doc => doc -> doc -> doc
<+> SDoc
rest) (forall a b. (a -> b) -> [a] -> [b]
map forall doc. IsLine doc => String -> doc
text [String]
files)



type SummaryNode = Node Int ModuleGraphNode

summaryNodeKey :: SummaryNode -> Int
summaryNodeKey :: SummaryNode -> Int
summaryNodeKey = forall key payload. Node key payload -> key
node_key

summaryNodeSummary :: SummaryNode -> ModuleGraphNode
summaryNodeSummary :: SummaryNode -> ModuleGraphNode
summaryNodeSummary = forall key payload. Node key payload -> payload
node_payload

-- | Collect the immediate dependencies of a ModuleGraphNode,
-- optionally avoiding hs-boot dependencies.
-- If the drop_hs_boot_nodes flag is False, and if this is a .hs and there is
-- an equivalent .hs-boot, add a link from the former to the latter.  This
-- has the effect of detecting bogus cases where the .hs-boot depends on the
-- .hs, by introducing a cycle.  Additionally, it ensures that we will always
-- process the .hs-boot before the .hs, and so the HomePackageTable will always
-- have the most up to date information.
nodeDependencies :: Bool -> ModuleGraphNode -> [NodeKey]
nodeDependencies :: Bool -> ModuleGraphNode -> [NodeKey]
nodeDependencies Bool
drop_hs_boot_nodes = \case
    LinkNode [NodeKey]
deps UnitId
_uid -> [NodeKey]
deps
    InstantiationNode UnitId
uid InstantiatedUnit
iuid ->
      ModNodeKeyWithUid -> NodeKey
NodeKey_Module forall b c a. (b -> c) -> (a -> b) -> a -> c
. (\ModuleName
mod -> ModuleNameWithIsBoot -> UnitId -> ModNodeKeyWithUid
ModNodeKeyWithUid (forall mod. mod -> IsBootInterface -> GenWithIsBoot mod
GWIB ModuleName
mod IsBootInterface
NotBoot) UnitId
uid)  forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. UniqDSet a -> [a]
uniqDSetToList (forall unit. GenInstantiatedUnit unit -> UniqDSet ModuleName
instUnitHoles InstantiatedUnit
iuid)
    ModuleNode [NodeKey]
deps ModSummary
_ms ->
      forall a b. (a -> b) -> [a] -> [b]
map NodeKey -> NodeKey
drop_hs_boot [NodeKey]
deps
  where
    -- Drop hs-boot nodes by using HsSrcFile as the key
    hs_boot_key :: IsBootInterface
hs_boot_key | Bool
drop_hs_boot_nodes = IsBootInterface
NotBoot -- is regular mod or signature
                | Bool
otherwise          = IsBootInterface
IsBoot

    drop_hs_boot :: NodeKey -> NodeKey
drop_hs_boot (NodeKey_Module (ModNodeKeyWithUid (GWIB ModuleName
mn IsBootInterface
IsBoot) UnitId
uid)) = (ModNodeKeyWithUid -> NodeKey
NodeKey_Module (ModuleNameWithIsBoot -> UnitId -> ModNodeKeyWithUid
ModNodeKeyWithUid (forall mod. mod -> IsBootInterface -> GenWithIsBoot mod
GWIB ModuleName
mn IsBootInterface
hs_boot_key) UnitId
uid))
    drop_hs_boot NodeKey
x = NodeKey
x

-- | Turn a list of graph nodes into an efficient queriable graph.
-- The first boolean parameter indicates whether nodes corresponding to hs-boot files
-- should be collapsed into their relevant hs nodes.
moduleGraphNodes :: Bool
  -> [ModuleGraphNode]
  -> (Graph SummaryNode, NodeKey -> Maybe SummaryNode)
moduleGraphNodes :: Bool
-> [ModuleGraphNode]
-> (Graph SummaryNode, NodeKey -> Maybe SummaryNode)
moduleGraphNodes Bool
drop_hs_boot_nodes [ModuleGraphNode]
summaries =
  (forall key payload.
Uniquable key =>
[Node key payload] -> Graph (Node key payload)
graphFromEdgedVerticesUniq [SummaryNode]
nodes, NodeKey -> Maybe SummaryNode
lookup_node)
  where
    -- Map from module to extra boot summary dependencies which need to be merged in
    (Map Module [NodeKey]
boot_summaries, [SummaryNode]
nodes) = forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList forall a. a -> a
id forall a b. (a -> b) -> a -> b
$ forall a b. [Either a b] -> ([a], [b])
partitionEithers (forall a b. (a -> b) -> [a] -> [b]
map (ModuleGraphNode, Int) -> Either (Module, [NodeKey]) SummaryNode
go [(ModuleGraphNode, Int)]
numbered_summaries)

      where
        go :: (ModuleGraphNode, Int) -> Either (Module, [NodeKey]) SummaryNode
go (ModuleGraphNode
s, Int
key) =
          case ModuleGraphNode
s of
                ModuleNode [NodeKey]
__deps ModSummary
ms | ModSummary -> IsBootInterface
isBootSummary ModSummary
ms forall a. Eq a => a -> a -> Bool
== IsBootInterface
IsBoot, Bool
drop_hs_boot_nodes
                  -- Using nodeDependencies here converts dependencies on other
                  -- boot files to dependencies on dependencies on non-boot files.
                  -> forall a b. a -> Either a b
Left (ModSummary -> Module
ms_mod ModSummary
ms, Bool -> ModuleGraphNode -> [NodeKey]
nodeDependencies Bool
drop_hs_boot_nodes ModuleGraphNode
s)
                ModuleGraphNode
_ -> Either (Module, [NodeKey]) SummaryNode
normal_case
          where
           normal_case :: Either (Module, [NodeKey]) SummaryNode
normal_case =
              let lkup_key :: Maybe Module
lkup_key = ModSummary -> Module
ms_mod forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ModuleGraphNode -> Maybe ModSummary
moduleGraphNodeModSum ModuleGraphNode
s
                  extra :: Maybe [NodeKey]
extra = (Maybe Module
lkup_key forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \Module
key -> forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup Module
key Map Module [NodeKey]
boot_summaries)

              in forall a b. b -> Either a b
Right forall a b. (a -> b) -> a -> b
$ forall key payload. payload -> key -> [key] -> Node key payload
DigraphNode ModuleGraphNode
s Int
key forall a b. (a -> b) -> a -> b
$ [NodeKey] -> [Int]
out_edge_keys forall a b. (a -> b) -> a -> b
$
                      (forall a. a -> Maybe a -> a
fromMaybe [] Maybe [NodeKey]
extra
                        forall a. [a] -> [a] -> [a]
++ Bool -> ModuleGraphNode -> [NodeKey]
nodeDependencies Bool
drop_hs_boot_nodes ModuleGraphNode
s)

    numbered_summaries :: [(ModuleGraphNode, Int)]
numbered_summaries = forall a b. [a] -> [b] -> [(a, b)]
zip [ModuleGraphNode]
summaries [Int
1..]

    lookup_node :: NodeKey -> Maybe SummaryNode
    lookup_node :: NodeKey -> Maybe SummaryNode
lookup_node NodeKey
key = forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup NodeKey
key (forall a. NodeMap a -> Map NodeKey a
unNodeMap NodeMap SummaryNode
node_map)

    lookup_key :: NodeKey -> Maybe Int
    lookup_key :: NodeKey -> Maybe Int
lookup_key = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap SummaryNode -> Int
summaryNodeKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. NodeKey -> Maybe SummaryNode
lookup_node

    node_map :: NodeMap SummaryNode
    node_map :: NodeMap SummaryNode
node_map = forall a. Map NodeKey a -> NodeMap a
NodeMap forall a b. (a -> b) -> a -> b
$
      forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList [ (ModuleGraphNode -> NodeKey
mkNodeKey ModuleGraphNode
s, SummaryNode
node)
                   | SummaryNode
node <- [SummaryNode]
nodes
                   , let s :: ModuleGraphNode
s = SummaryNode -> ModuleGraphNode
summaryNodeSummary SummaryNode
node
                   ]

    out_edge_keys :: [NodeKey] -> [Int]
    out_edge_keys :: [NodeKey] -> [Int]
out_edge_keys = forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe NodeKey -> Maybe Int
lookup_key
        -- If we want keep_hi_boot_nodes, then we do lookup_key with
        -- IsBoot; else False
newtype NodeMap a = NodeMap { forall a. NodeMap a -> Map NodeKey a
unNodeMap :: Map.Map NodeKey a }
  deriving (forall a b. a -> NodeMap b -> NodeMap a
forall a b. (a -> b) -> NodeMap a -> NodeMap 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 -> NodeMap b -> NodeMap a
$c<$ :: forall a b. a -> NodeMap b -> NodeMap a
fmap :: forall a b. (a -> b) -> NodeMap a -> NodeMap b
$cfmap :: forall a b. (a -> b) -> NodeMap a -> NodeMap b
Functor, Functor NodeMap
Foldable NodeMap
forall (t :: * -> *).
Functor t
-> Foldable t
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a. Monad m => NodeMap (m a) -> m (NodeMap a)
forall (f :: * -> *) a.
Applicative f =>
NodeMap (f a) -> f (NodeMap a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> NodeMap a -> m (NodeMap b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> NodeMap a -> f (NodeMap b)
sequence :: forall (m :: * -> *) a. Monad m => NodeMap (m a) -> m (NodeMap a)
$csequence :: forall (m :: * -> *) a. Monad m => NodeMap (m a) -> m (NodeMap a)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> NodeMap a -> m (NodeMap b)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> NodeMap a -> m (NodeMap b)
sequenceA :: forall (f :: * -> *) a.
Applicative f =>
NodeMap (f a) -> f (NodeMap a)
$csequenceA :: forall (f :: * -> *) a.
Applicative f =>
NodeMap (f a) -> f (NodeMap a)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> NodeMap a -> f (NodeMap b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> NodeMap a -> f (NodeMap b)
Traversable, forall a. Eq a => a -> NodeMap a -> Bool
forall a. Num a => NodeMap a -> a
forall a. Ord a => NodeMap a -> a
forall m. Monoid m => NodeMap m -> m
forall a. NodeMap a -> Bool
forall a. NodeMap a -> Int
forall a. NodeMap a -> [a]
forall a. (a -> a -> a) -> NodeMap a -> a
forall m a. Monoid m => (a -> m) -> NodeMap a -> m
forall b a. (b -> a -> b) -> b -> NodeMap a -> b
forall a b. (a -> b -> b) -> b -> NodeMap a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: forall a. Num a => NodeMap a -> a
$cproduct :: forall a. Num a => NodeMap a -> a
sum :: forall a. Num a => NodeMap a -> a
$csum :: forall a. Num a => NodeMap a -> a
minimum :: forall a. Ord a => NodeMap a -> a
$cminimum :: forall a. Ord a => NodeMap a -> a
maximum :: forall a. Ord a => NodeMap a -> a
$cmaximum :: forall a. Ord a => NodeMap a -> a
elem :: forall a. Eq a => a -> NodeMap a -> Bool
$celem :: forall a. Eq a => a -> NodeMap a -> Bool
length :: forall a. NodeMap a -> Int
$clength :: forall a. NodeMap a -> Int
null :: forall a. NodeMap a -> Bool
$cnull :: forall a. NodeMap a -> Bool
toList :: forall a. NodeMap a -> [a]
$ctoList :: forall a. NodeMap a -> [a]
foldl1 :: forall a. (a -> a -> a) -> NodeMap a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> NodeMap a -> a
foldr1 :: forall a. (a -> a -> a) -> NodeMap a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> NodeMap a -> a
foldl' :: forall b a. (b -> a -> b) -> b -> NodeMap a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> NodeMap a -> b
foldl :: forall b a. (b -> a -> b) -> b -> NodeMap a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> NodeMap a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> NodeMap a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> NodeMap a -> b
foldr :: forall a b. (a -> b -> b) -> b -> NodeMap a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> NodeMap a -> b
foldMap' :: forall m a. Monoid m => (a -> m) -> NodeMap a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> NodeMap a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> NodeMap a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> NodeMap a -> m
fold :: forall m. Monoid m => NodeMap m -> m
$cfold :: forall m. Monoid m => NodeMap m -> m
Foldable)

mkNodeKey :: ModuleGraphNode -> NodeKey
mkNodeKey :: ModuleGraphNode -> NodeKey
mkNodeKey = \case
  InstantiationNode UnitId
_ InstantiatedUnit
iu -> InstantiatedUnit -> NodeKey
NodeKey_Unit InstantiatedUnit
iu
  ModuleNode [NodeKey]
_ ModSummary
x -> ModNodeKeyWithUid -> NodeKey
NodeKey_Module forall a b. (a -> b) -> a -> b
$ ModSummary -> ModNodeKeyWithUid
msKey ModSummary
x
  LinkNode [NodeKey]
_ UnitId
uid   -> UnitId -> NodeKey
NodeKey_Link UnitId
uid

msKey :: ModSummary -> ModNodeKeyWithUid
msKey :: ModSummary -> ModNodeKeyWithUid
msKey ModSummary
ms = ModuleNameWithIsBoot -> UnitId -> ModNodeKeyWithUid
ModNodeKeyWithUid (ModSummary -> ModuleNameWithIsBoot
ms_mnwib ModSummary
ms) (ModSummary -> UnitId
ms_unitid ModSummary
ms)

type ModNodeKey = ModuleNameWithIsBoot