[GHC] #13251: Must perform family consistency check on non-imported identifiers

[GHC]

#13251: Must perform family consistency check on non-imported identifiers
-------------------------------------+-------------------------------------
        Reporter:  ezyang            |                Owner:
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler (Type    |              Version:  8.1
  checker)                           |
      Resolution:                    |             Keywords:  TypeFamilies
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  GHC accepts       |  Unknown/Multiple
  invalid program                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 Here's a summary.

 === Instance providers ===

 * Define an '''instance provider''' thus: a module A is an instance
 provider for M if the class and family instances in A, and those of A's
 instance providers, are visible in M.

 * An '''orphan instance provider''' for M is an instance provider for M
 that is also an orphan module.

 Instance providers come from three places:

 * M's direct imports are clearly import providers for M.

 * Less obviously, the use of a wired-in `TyCon` to deal with built-in
 syntax (e.g. overloaded lists) may add a new instance provider that was
 not (transitively) imported.  A particular case is `GHC.Exts`.

 * Also less obviously, if Template Haskell splices in a definition like
 {{{
 f = P.Q.g
 }}}
   then `P.Q` becomes an instance provider, because the family instances
 available there may have been used to typecheck `P.Q.g`.



 === Consistency checking ===

 We must do family-instance consistency checks for the transitive closure
 of
 all M's instance providers.

 The easiest place to do this is right at the end of type checking, when we
 have a complete set of instance providers to check.  The only downside is
 that, in the meantime, we could have inconsistent type-family instances,
 and we would need to account for that in type-family lookup (for example
 by returning not-found).

 === Instance lookup ===

 Generally, we vigorously load instances into a single instance environment
 in the External Package State.  But which ones are visible?  Answer: the
 instance providers.  We can use this to filter out the instance(s) we
 match on.  But we need only check against the orphan instance providers
 because if the instance is in a no-orphan module X, then X must be in the
 instance providers else how could we be looking up that particular
 predicate?

 === Tracking instance providers ===

 We can track the instance providers by accumulating

 * M's direct imports
 * Modules loaded by `checkWiredInTyCon`
 * Ditto for Template Haskell

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13251#comment:5>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler