Opened 13 years ago

Last modified 3 years ago

#1012 new bug

ghc panic with mutually recursive modules and template haskell

Reported by: guest Owned by:
Priority: lowest Milestone:
Component: Template Haskell Version: 6.8.2
Keywords: hs-boot Cc: leuschner@…, ozgurakgun@…, m@…, mgsloan
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case: TH_import_loop
Blocked By: Blocking:
Related Tickets: #9032 Differential Rev(s):
Wiki Page:

Description

When compiling the files below using ghc --make Main.hs I get the following error:

[1 of 5] Compiling ModuleA[boot]    ( ModuleA.hs-boot, nothing )
[2 of 5] Compiling ModuleC          ( ModuleC.hs, ModuleC.o )
[3 of 5] Compiling ModuleB          ( ModuleB.hs, ModuleB.o )
Loading package base ... linking ... done.
Loading package template-haskell ... linking ... done.
ghc-6.6: panic! (the 'impossible' happened)
  (GHC version 6.6 for powerpc-apple-darwin):
        Maybe.fromJust: Nothing

ModuleA.hs:

module ModuleA where

import ModuleB

ModuleA.hs-boot:

module ModuleA where

ModuleB.hs:

{-# OPTIONS -fth #-}
module ModuleB where

import ModuleC

$(nothing)

ModuleC.hs:

module ModuleC where

import Language.Haskell.TH

import {-# SOURCE #-} ModuleA

nothing = return [] :: Q [Dec]

Main.hs:

module Main.hs

import ModuleA

main = return ()

Change History (42)

comment:1 Changed 13 years ago by igloo

Architecture: powerpcMultiple
Milestone: _|_
Operating System: MacOS XMultiple
Test Case: TH_import_loop

Urk, this looks tricky. It will probably want to wait until we can use code spliced in earlier in a module in later splices in the same module.

comment:2 Changed 13 years ago by simonmar

This now gives a slightly improved error message, as a result of the fix for #936:

[1 of 5] Compiling A[boot]          ( A.hs-boot, nothing )
[2 of 5] Compiling C                ( C.hs, C.o )
[3 of 5] Compiling B                ( B.hs, B.o )
Loading package base ... linking ... done.
module main:A cannot be linked; it is only available as a boot module

Simon: please feel free to edit the error message if you can think of a way to improve it (compiler/ghci/Linker.hs). Should we close this bug? Perhaps document the shortcoming in the TH docs?

comment:3 Changed 13 years ago by simonpj

Type: bugmerge

I've updated the docs. Ian, please merge.

Wed Jan 31 09:14:51 GMT 2007 simonpj@…

  • Add note about Template Haskell and mutual recursion

Simon

comment:4 Changed 13 years ago by igloo

Resolution: fixed
Status: newclosed

Merged.

comment:5 Changed 12 years ago by fons

Resolution: fixed
Status: closedreopened

Don't know if this deserves its own ticket but it seems that ghci (or ghc --make) fails when running a compile-time function imported from a mutually-recursive group of modules which _doesn't_ include the module currently being compiled.

ModuleA.hs-boot

module ModuleA where

ModuleA.hs

module ModuleA where
import ModuleC

ModuleC.hs

module ModuleC where

import Language.Haskell.TH

import {-# SOURCE #-} ModuleA

nothing = return [] :: Q [Dec]

ModuleB.hs (makes use of a function of C but is _not_ included in the group of recursive modules)

{-# LANGUAGE TemplateHaskell #-}
module ModuleB where

import ModuleC

$(nothing)
$ ghci ModuleB.hs
GHCi, version 6.8.1: http://www.haskell.org/ghc/  :? for help
Loading package base ... linking ... done.
[1 of 4] Compiling ModuleA[boot]    ( ModuleA.hs-boot, interpreted )
[2 of 4] Compiling ModuleC          ( ModuleC.hs, interpreted )
[3 of 4] Compiling ModuleB          ( ModuleB.hs, interpreted )
module main:ModuleA cannot be linked; it is only available as a boot module
> 

Furthermore, it would be really useful if the error message indicated the compilation failed due to Template Haskell. (It took me a while to figure out why it was caused)

Last edited 3 years ago by ezyang (previous) (diff)

comment:6 Changed 12 years ago by fons

curiously enough compiling the following module doesn't cuase any problems.

Main.hs

module Main where

import ModuleB

main = return ()

$ ghc --make Main.hs
[1 of 5] Compiling ModuleA[boot]    ( ModuleA.hs-boot, ModuleA.o-boot )
[2 of 5] Compiling ModuleC          ( ModuleC.hs, ModuleC.o )
[3 of 5] Compiling ModuleA          ( ModuleA.hs, ModuleA.o )
[4 of 5] Compiling ModuleB          ( ModuleB.hs, ModuleB.o )
Loading package base ... linking ... done.
Loading package array-0.1.0.0 ... linking ... done.
Loading package packedstring-0.1.0.0 ... linking ... done.
Loading package containers-0.1.0.0 ... linking ... done.
Loading package pretty-1.0.0.0 ... linking ... done.
Loading package template-haskell ... linking ... done.
[5 of 5] Compiling Main             ( Main.hs, Main.o )
Linking Main ...

comment:7 Changed 12 years ago by fons

Type: mergebug
Version: 6.66.8.2

comment:8 Changed 12 years ago by fons

Component: CompilerTemplate Haskell

comment:9 Changed 12 years ago by simonmar

Since ModuleB is outside the ModuleA/ModuleC loop, it can import ModuleA without creating any new loops, and I bet this will work around the problem and get you unblocked.

What's happening is that the dependency analysis isn't figuring out that the real ModuleA must be compiled before ModuleB. I think the solution is something along the lines of: every module that depends on a module in a cycle, but is not a member of that cycle, should have an implicit dependency on each of the modules in the cycle.

comment:10 Changed 12 years ago by simonmar

Milestone: _|_6.8 branch

comment:11 Changed 12 years ago by simonpj

Resolution: fixed
Status: reopenedclosed

Simon is right: B.hs depends on C.hs, which depends on A.hs-boot. I think it's quite accidental that A happens to be compiled before B in your "curiously enough" case, but after B in your original case.

All you need do is to make B depend on A, thus

{-# LANGUAGE TemplateHaskell #-}
module ModuleB where

import ModuleC
import ModuleA

$(nothing)

and it all works fine. Use -v to see the compilation order.

I will clarify the documentation, thus:

You can only run a function at compile time if it is imported from another module that is not part of a mutually-recursive group of modules that includes the module currently being compiled. Furthermore, all of the modules of the mutually-recursive group must be reachable by non-SOURCE imports from the module where the splice is to be run.

Fri Jan  4 12:19:39 GMT 2008  simonpj@microsoft.com
  * Document SOURCE pragma; clarify TH behavior for 
    mutually-recurive modules (Trac #1012)

It's not clear to me how to improve the error message, at least not without adding more plumbing to say "I'm in a Template Haskell splice". Let's see if it happens again.

Meanwhile I'll close the bug.

Simon

comment:12 in reply to:  11 Changed 12 years ago by fons

Replying to simonpj:

Simon is right: B.hs depends on C.hs, which depends on A.hs-boot. I think it's quite accidental that A happens to be compiled before B in your "curiously enough" case, but after B in your original case.

All you need do is to make B depend on A, thus

{-# LANGUAGE TemplateHaskell #-}
module ModuleB where

import ModuleC
import ModuleA

$(nothing)

and it all works fine. Use -v to see the compilation order.

I finally managed to solve the problem "turning around" the circular dependencies of my project (tranforming the SOURCE imports of the loop in normal onces and vice versa). However, the workaround suggested by Simon should work as you said.

Meanwhile I'll close the bug.

As far as I understand, ghc's dependency analysis could be improved (otherwise a workaround would not be needed). I don't personally think this bug should be closed and include it as a limitation in the docs before considering simonmar's proposal, that is:

What's happening is that the dependency analysis isn't figuring out that the real ModuleA must be compiled before ModuleB. I think the solution is something along the lines of: every module that depends on a module in a cycle, but is not a member of that cycle, should have an implicit dependency on each of the modules in the cycle.

comment:13 Changed 12 years ago by igloo

Milestone: 6.8 branch_|_
Resolution: fixed
Status: closedreopened

I agree that it is still a bug, but I've put it back in the _|_ milestone as it's easy to work-around, and I assume that if it was trivial to fix then SPJ would have done so.

comment:14 Changed 12 years ago by simonpj

Milestone: _|_6.10 branch

Fair enough. I have taken a little look at this, based on fons's suggestion "every module M that depends on a module C in a cycle, but is not a member of that cycle, should have an implicit dependency on each of the modules C1.. Cn in the cycle.". Yes, I think that would not be too hard to do. There are two places to think about:

  • ghc --make: When deciding the up-sweep order, first do a SCC analysis finding strongly connected components of modules, and top-sort those components. Then linearise each component. That gives a linear order that respects fons's suggestion.
  • ghc -M: similar story, but less neat. We have to emit lots of extra dependencies in the makefile, so that M depends on C1..Cn.

Not very hard, but more than an hours work. Let's do it for 6.10.

Simon

comment:15 Changed 11 years ago by simonmar

Architecture: MultipleUnknown/Multiple

comment:16 Changed 11 years ago by simonmar

Operating System: MultipleUnknown/Multiple

comment:17 Changed 10 years ago by igloo

Milestone: 6.10 branch6.12 branch

comment:18 Changed 9 years ago by igloo

Milestone: 6.12 branch6.12.3

comment:19 Changed 9 years ago by igloo

Milestone: 6.12.36.14.1
Priority: normallow

comment:20 Changed 9 years ago by igloo

Milestone: 7.0.17.0.2

comment:21 Changed 8 years ago by igloo

Milestone: 7.0.27.2.1

comment:22 Changed 8 years ago by dleuschner

Cc: leuschner@… added
Type of failure: None/Unknown

Just a note: Of course this is not an important bug/limitation. It would be still nice if it would just work. It took me some time to realise what the problem is, find this bug report and the section in the manual and reorganise the code to accomodate for the limitation. Before that I did several clean/rebuild, rebuild without "make -j" cycles to be sure that it's not a problem with the build system. It's a bit unexpected because normally GHC just does everything I want (and even more). :-)

comment:23 Changed 8 years ago by igloo

Milestone: 7.2.17.4.1

comment:24 Changed 8 years ago by igloo

Milestone: 7.4.17.6.1
Priority: lowlowest

comment:25 Changed 7 years ago by igloo

Milestone: 7.6.17.6.2

comment:26 Changed 6 years ago by ozgura

Cc: ozgurakgun@… added

comment:27 Changed 6 years ago by goldfire

I just got bitten by this, and I don't see a clean reorganization. While I agree that this should be "lowest" priority, I thought I'd document my real-life use case:

The singletons library generates a fair amount of code using TH. In particular, it produces instances for classes, type families, and data families. Accordingly, the TH code needs to know the names of these classes and families, and the names of the class members. In the main module of the library, I want to use the TH code to produce lots of instances for datatypes exported from base (Bool, Maybe, (), ...). I don't want these instances to be orphans. So, I'm stuck.

I'll illustrate further with some code:

Module Data.Singletons (boot):

data family Sing (a :: k)

Module Data.Singletons.Singletons:

import {-# SOURCE #-} Data.Singletons

singName :: Name
singName = ''Sing

genSingletons :: [Name] -> Q [Dec]
genSingletons = ...

Module Data.Singletons:

import Data.Singletons.Singletons

data family Sing (a :: k)
$(genSingletons [''Bool, ''Maybe, ''Either, ''[]])

This all seems quite sensible to me, yet GHC can't do it. It seems I have several bad options: 1) allow orphans, defining the Sing family in a different module than its instances; 2) hand-write the instances I want, avoiding the loop; or 3) use mkName to create the names. I'm going to do (3), but it feels dirty and fragile.

Note: I do see why calling a function at compile time that is defined in a module in a mutually-recursive group with the calling module could be very bad. But, I'm not quite doing that here. That said, I don't see an easy way to allow what I want, prohibit the bad behavior, and not pollute the syntax and implementation of it all. The reason for this comment is just to document a case where I'm a little hamstrung by this missing behavior, not that I really want resources dedicated to finding a fix here.

comment:28 Changed 6 years ago by isaacdupree

goldfire: Can you move data family Sing (a :: k) to a new private module Data.Singletons.Sing that both Data.Singletons and Data.Singletons.Singletons import (and that Data.Singletons re-exports for the sake of library users)? (getting rid of the module cycle)

comment:29 in reply to:  28 Changed 6 years ago by goldfire

Sure, but then the instances generated from the TH code written in Data.Singletons.Singletons are all orphans. I think using mkName makes the library a better "citizen" than do orphan instances.

comment:30 Changed 6 years ago by Joachim Breitner <mail@…>

In 84b4e9b4e2f1de48d573ec5035a687d318f7b651/testsuite:

TH_import_loops fails for GHCi again

This reverts commit c0e50e9214b5ecb21435d7da70986d30d6128402 and is related to
ticket #1012.

comment:31 Changed 6 years ago by Ian Lynagh <igloo@…>

In dbf3b55ff58fc762beef1fc102cb7c6348efac9c/ghc:

Add a test for trac #1012: Problems with TH and recursive module imports

comment:32 Changed 5 years ago by thoughtpolice

Milestone: 7.6.27.10.1

Moving to 7.10.1.

comment:33 Changed 5 years ago by mboes

Cc: m@… added

FWIW, I just ran into this very same issue. My use case is identical in structure to goldfire's, but is unrelated to the singletons library.

comment:34 Changed 5 years ago by jstolarek

#9032 looks related (not sure if it's a duplicate or not).

comment:35 Changed 5 years ago by thoughtpolice

Milestone: 7.10.17.12.1

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:36 Changed 5 years ago by thoughtpolice

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:37 Changed 4 years ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

comment:38 in reply to:  34 Changed 4 years ago by thomie

Replying to jstolarek:

#9032 looks related (not sure if it's a duplicate or not).

It's not a duplicate. #9032 is fixed, but make test TEST=TH_import_loop (this ticket) is still failing.

comment:39 Changed 4 years ago by thomie

Milestone: 8.0.1

comment:40 Changed 3 years ago by mgsloan

Cc: mgsloan added

I just ran into this as well. There is a fairly generic usecase that requires this: defining TH that generates instances of a class, and then using that TH to generate non-orphan instances. Pretty much the same as the usecase Richard outlines above.

comment:41 Changed 3 years ago by ezyang

Keywords: hs-boot added

comment:42 Changed 3 years ago by ezyang

This bug still exists in GHC 8.0, although it can be a bit tricky to trigger if the topsort picks an ordering of modules which masks the error. I found this especially surprising because in the parallel upsweep case we seem to try to block, c.f. this comment in GhcMake

2. A module that depends on a module in an external loop can't proceed
   until the entire loop is re-typechecked.

and this code:

    -- If this module depends on a module within a loop then it must wait for
    -- that loop to get re-typechecked, i.e. it must wait on the module that
    -- finishes that loop. These extra dependencies are this module's
    -- "external" loop dependencies, because this module is outside of the
    -- loop(s) in question.
    let ext_loop_deps = Set.fromList
            [ head loop | loop <- comp_graph_loops
                        , any (`Set.member` textual_deps) loop
                        , this_build_mod `notElem` loop ]
Note: See TracTickets for help on using tickets.