Problems with new cyclic dependency error message
|Reported by:||simonmar||Owned by:||simonpj|
|Type of failure:||None/Unknown||Difficulty:|
|Test Case:||Blocked By:|
Description (last modified by 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:
I think we need to sort this out before the release since it's a regression, so marking it as "highest".