Problems with new cyclic dependency error message
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".