#5307: Problems with new cyclic dependency error message
---------------------------------+------------------------------------------
Reporter: simonmar | Owner:
Type: bug | Status: new
Priority: highest | Milestone: 7.2.1
Component: Compiler | Version: 7.0.3
Keywords: | Testcase:
Blockedby: | Difficulty:
Os: Unknown/Multiple | Blocking:
Architecture: Unknown/Multiple | Failure: None/Unknown
---------------------------------+------------------------------------------
Old description:
> 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.
>
> This cut-down version of what I was doing should be enough to trigger the
> problem: add a file `GHC/Fingerprint.hs-boot` to the base package
> containing:
>
> {{{
> module GHC.Fingerprint ( ) where
>
> import GHC.Ptr
> import GHC.Word
> import GHC.Base
> }}}
>
> and added a `SOURCE` import of `GHC.Fingerprint` to `Data.Typeable`.
>
> I think we need to sort this out before the release since it's a
> regression, so marking it as "highest".
New description:
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".
--
Comment(by simonpj):
* Problem 1: we must take account of source imports:
{{{
A.hs
module A where
import {-# SOURCE #-} B
B.hs-boot
module B where
import A
}}}
* Problem 2: when reporting such a loop we should say which are hs-boot
files.
* Problem 3: the shortest path thing is exponential if there is a lot of
sharing in the module import graph.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5307#comment:1>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
