id,summary,reporter,owner,description,type,status,priority,milestone,component,version,resolution,keywords,cc,os,architecture,failure,difficulty,testcase,blockedby,blocking,related
5307,Problems with new cyclic dependency error message,simonmar,simonpj,"I encountered a ""head: empty list"" failure and tracked it down to the new `cyclicModuleErr` in `GhcMake.hs`.  Basically the problem is that I had a module loop that went through a `.hs-boot` module, and the code is ignoring source imports when looking for a cycle to display.

{{{
    get_deps m = filter (\k -> Map.member k dep_env) (map unLoc (ms_home_imps m))
}}}

However, if I add source imports here, then GHC failed to terminate.  I think this is because the algorithm for finding the shortest cycle has terrible complexity:

{{{
    shortest visited m 
      | m `elem` visited
      = m : reverse (takeWhile (/= m) visited)
      | otherwise
      = minWith length (map (shortest (m:visited)) deps)
      where
        Just deps = Map.lookup m dep_env
}}}

I tried a few things to fix this (restricting the search to loops that go through the root module, and using a lazy length comparison), but neither helped.  I suspect we need to use a proper shortest-path algorithm here.

To reproduce, edit `GHC/Fingerprint.hs-boot` in the base package to add an extra import:
{{{
import Foreign.Ptr
}}}

I think we need to sort this out before the release since it's a regression, so marking it as ""highest"".",bug,closed,highest,7.2.1,Compiler,7.0.3,fixed,,,Unknown/Multiple,Unknown/Multiple,None/Unknown,,,,,