ghc cyclic import error confusing

[Simon Marlow]

On 09/04/2011 04:32, Evan Laforge wrote:
> I've found ghc's cyclic import error to be rather confusing, and I
> finally took the time to understand why.  Here's an example:
>
> Module imports form a cycle for modules:
>   Cmd.Cmd (./Cmd/Cmd.hs)
>     imports: Perform.Midi.Instrument Instrument.MidiDb Instrument.Db
>   Perform.Midi.Instrument (./Perform/Midi/Instrument.hs)
>     imports: Cmd.Cmd
>   Instrument.MidiDb (./Instrument/MidiDb.hs)
>     imports: Perform.Midi.Instrument
>   Instrument.Db (./Instrument/Db.hs)
>     imports: Instrument.Search Instrument.MidiDb
>              Perform.Midi.Instrument
>   Instrument.Search (./Instrument/Search.hs)
>     imports: Instrument.MidiDb Perform.Midi.Instrument
>
> It seems to be in a strange order and mentions extraneous modules.  I
> would find this much easier to read:
>
> Perform.Midi.Instrument ->  Cmd.Cmd ->  Instrument.MidiDb ->
> Perform.Midi.Instrument

So the algorithm that GHC uses is this:

   - do a strongly connected component analysis
   - build until we hit a cycle
   - then, report the error for the cycle

Now, the modules in the cycle are a strongly connected component: every 
module is reachable from every other module by following imports.  We 
report all the modules in the strongly connected component and their 
imports, but omit imports of modules outside the cycle.

> Instead, the order goes Cmd.Cmd ->  Instrument.MidiDb, and then goes
> backwards to Perform.Midi.Instrument ->  Cmd.Cmd.  Then it goes forward
> again to Instrument.MidiDb ->  Perform.Midi.Instrument.  So the order
> makes you jump around if you want to trace the import chain.  The
> duplicated module that joins the cycle is not visually highlighted.
> Whats more, it further confuses the eye by merging in multiple loops.
> I suppose it could be useful to include additional loops, but I would
> find it easier to read if they were included on their own line, such
> as:
>
> Cmd.Cmd ->  Instrument.Db ->  Instrument.Search ->
> Perform.Midi.Instrument ->  Cmd.Cmd
>
> However, I think probably the shortest loop is the most interesting
> one, and if there are multiple shortest loops, simply picking one
> randomly is likely to be sufficient.

Picking the shortest one sounds reasonable.  However, there could be a 
single edge which if removed will break all the loops, and they might 
want to know which it is.

If you want to play with this, the code is very localised: it is a few 
lines in GhcMake.cyclicModuleError

http://hackage.haskell.org/trac/ghc/browser/compiler/main/GhcMake.hs#L1446

Cheers,
	Simon