Opened 9 years ago

Closed 8 years ago

#5307 closed bug (fixed)

Problems with new cyclic dependency error message

Reported by: simonmar Owned by: simonpj
Priority: highest Milestone: 7.2.1
Component: Compiler Version: 7.0.3
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

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)
        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".

Change History (6)

comment:1 Changed 9 years ago by simonpj

Description: modified (diff)
  • Problem 1: we must take account of source imports:
      module A where
      import {-# SOURCE #-} B
      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.

comment:2 Changed 9 years ago by simonmar

Owner: set to simonpj

comment:3 Changed 9 years ago by simonmar

Here's how to generate some test data:

module Main where

import System.Random
import System.IO
import Control.Monad
import Control.Applicative
import qualified Data.Map as Map
import Text.Printf
import System.Environment

main = do
  [x,y] <- fmap (fmap read) getArgs
  (g1,g2) <- split <$> getStdGen

  let edges = take y [ (x,[y]) | (x,y) <- zip (randomRs (1,x) g1)
                                              (randomRs (1,x) g2) ]
      edgemap = Map.fromListWith (++) edges

  forM_ [1..x] $ \m -> do
    h <- openFile ("M" ++ show m ++ ".hs") WriteMode
    hPrintf h  "module M%d where\n" m
    mapM_ (hPrintf h "import M%d\n") (Map.findWithDefault [] m edgemap :: [Int])
    hClose h

use it like this (to generate 100 modules with 1000 random imports):

  $ ghc modloop.hs
  $ ./modloop 100 1000
  $ ghc -M M1

for me, this sends GHC off into a little world of its own...

comment:4 Changed 9 years ago by simonpj@…

commit e85902183d290b3ee8bdd242d10bf60b963f3f28

Author: Simon Peyton Jones <>
Date:   Fri Jul 22 08:56:42 2011 +0100

    Implement a findCycle function in Digraph,
    and use it to report module loops nicely
    This fixes Trac #5307. Now we get
        Module imports form a cycle:
                 module `M8' (.\M8.hs)
                imports `M1' (M1.hs)
          which imports `M9' (.\M9.hs-boot)
          which imports `M8' (.\M8.hs)
    And the algorithm is linear time.

 compiler/main/GhcMake.hs   |   67 +++++++++++++---------------------
 compiler/utils/Digraph.lhs |   85 +++++++++++++++++++++++++++++++++++++++----
 compiler/utils/Util.lhs    |    6 +++-
 3 files changed, 107 insertions(+), 51 deletions(-)

comment:5 Changed 9 years ago by simonpj

Status: newmerge

The above patch fixes this bug. A test is a bit fiddly, so I'm not creating one :-)

This is a bug, so worth merging to 7.2


comment:6 Changed 8 years ago by igloo

Resolution: fixed
Status: mergeclosed
Note: See TracTickets for help on using tickets.