import qualified Data.Map.Strict as M

 import Control.Monad.Trans.Class

 import System.IO.Unsafe (unsafeInterleaveIO)

 import qualified Data.List.NonEmpty as NE

 {-

 Note [The ModuleGraph]

                 -- which case there can be repeats

 downsweep hsc_env diag_wrapper msg old_summaries maybe_base_graph excl_mods allow_dup_roots = do

   n_jobs     <- mkWorkerLimit (hsc_dflags hsc_env)

   withMakeEnv n_jobs hsc_env diag_wrapper msg $ \make_env -> do

     (root_errs, root_summaries) <- rootSummariesParallel n_jobs make_env (hsc_targets hsc_env)

                                      (getRootSummary excl_mods summ_cache imps_cache)

 downsweepThunk hsc_env mod_summary = unsafeInterleaveIO $ do

   debugTraceMsg (hsc_logger hsc_env) 3 $ text "Computing Module Graph thunk..."

   njobs <- mkWorkerLimit (hsc_dflags hsc_env)

   withMakeEnv njobs hsc_env mkUnknownDiagnostic Nothing $ \make_env -> do

     let env = DownsweepEnv

           { ds_hsc_env         = hsc_env

   let cached_nodes = Map.fromList [ (mkNodeKey n, NSuccess n) | n <- mg_mss (hsc_mod_graph hsc_env) ]

   n_jobs     <- mkWorkerLimit (hsc_dflags hsc_env)

   withMakeEnv n_jobs hsc_env mkUnknownDiagnostic Nothing $ \make_env -> do

     let env = DownsweepEnv

           { ds_hsc_env         = hsc_env

     njobs <- mkWorkerLimit (hsc_dflags hsc_env)

     nodes <- mapM process installed_mods

     withMakeEnv njobs hsc_env mkUnknownDiagnostic Nothing $ \make_env -> do

       let env = DownsweepEnv

             { ds_hsc_env         = hsc_env

 -- * Orchestrator: downsweepFromRootNodes

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

 -- | A cache from file paths to the already summarised modules. The same file

 -- can be used in multiple units so the map is actually also keyed by which

         all_deps    <- loopUnits module_deps (hscActiveUnitId ds_hsc_env) root_uids

         deps'       <- loopInstantiations all_deps (getHomeUnitInstantiations ds_hsc_env)

         return deps'

      let downsweep_errs = lefts (M.elems f_cache)

          downsweep_nodes = [ s | NSuccess s <- M.elems deps' ]

 modifySummCache :: ModSummaryCache -> (ModSummaryCacheMap -> ModSummaryCacheMap) -> IO ()

 modifyImpsCache :: ImportsCache    -> (ImportsCacheMap    -> ImportsCacheMap)    -> IO ()

 -- | A cache from a module import (in given home unit context, with a package

 -- qualifier, and the imported module name (with or without SOURCE)) to the

 loopUnits           :: M.Map NodeKey (NodeRes ModuleGraphNode) -> UnitId -> [UnitId]            -> DownsweepM (M.Map NodeKey (NodeRes ModuleGraphNode))

 loopInstantiations  :: M.Map NodeKey (NodeRes ModuleGraphNode) -> [(UnitId, InstantiatedUnit)]  -> DownsweepM (M.Map NodeKey (NodeRes ModuleGraphNode))

 loopFromInteractive :: M.Map NodeKey (NodeRes ModuleGraphNode) -> Module -> [InteractiveImport] -> DownsweepM (M.Map NodeKey (NodeRes ModuleGraphNode))

 loopModuleNodeInfos base_map       = loopDownsweepNodes base_map . map DSMod

 loopUnits           base_map homud = loopDownsweepNodes base_map . map (DSUnit homud)

 loopInstantiations  base_map       = loopDownsweepNodes base_map . map (uncurry DSInst)

         FoundHomeWithError (_uid, _e) -> return

           ( Nothing, [] )

           -- the error @e@ is already stored in the summarisation cache,

         FoundHome s -> return

           -- MP: This assumes that we can only instantiate non home units, which is probably fair enough for now.

           ( Just $ mkModuleEdge lvl (NodeKey_Module (mnKey s))

         -> IO (Either DriverMessages ModSummary)

 summariseFile hsc_env' home_unit summ_cache_ref src_fn mb_phase maybe_buf

         case M.lookup (homeUnitId home_unit, src_fn_os) file_summ_cache of

           Just (Right (chd_summary, SummFresh)) ->

             -- Fresh: use it straight away

     find_it :: IO SummariseResult

     find_it = do

       case M.lookup cache_key imps_cache of

         Just result -> return result

         Nothing -> do

     -- Adjust location to point to the hs-boot source file,

     -- hi file, object file, when is_boot says so

     let src_fn = expectJust (ml_hs_file location)

     -- Reject the cache result if the module name doesn't match the inferred

     -- module name based on the file name.

   -- abort.

   | NSkip

 -- graph by iteratively expanding a node into a payload and a list of children

 -- nodes to visit next.

 --

 -- The @expand@ function returns an 'NResult'. See the 'NResult' documentation

 -- for more information about each result type.

 --

 -- Example usage: @n@ is instanced to @DownsweepNode@, @k@ is @NodeKey@, and @v@ is @ModuleNodeEdge@.

 --

 -- See also Note [Downsweep Control Flow and Caching]

          => Maybe (Map.Map k (NodeRes v))

          -- ^ Base map, existing results. We won't re-expand any of the nodes

          -- already present in this map.

          -- ^ The root nodes from where to start traversal

          -> (n -> k)

          -- ^ Compute the key which uniquely identifies this node

          -- ^ Expand this node into its payload result and into the list of

          -- children nodes to visit next.

          -- ^ The result accumulates the payload of expanding the root nodes

          -- and all nodes transitively reachable from those roots.

   where

 {-

 Note [Downsweep Control Flow and Caching]