[GHC] #11348: Local open type families instances ignored during type checking

[GHC]

#11348: Local open type families instances ignored during type checking
-------------------------------------+-------------------------------------
        Reporter:  alexvieth         |                Owner:
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.0.1-rc1
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  GHC rejects       |  Unknown/Multiple
  valid program                      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 Yes, exactly.  That is ''much'' simpler than "meta-nodes", and had the
 great merit of being correct (see third bullet).

 I'm not too stressed about efficiency.  You need only do this for the open
 type-family instances, and there are seldom zillions of them.  If you want
 something a bit more efficient, try this:

 * Start with a set of pairs `(fam-inst-decl, free-vars)`, where `free-
 vars` is a list of ''locally-defined'' type/class constructors mentioned
 anywhere in the instance. I'll call them the **gate vars** of the fam-
 inst-decl.

 * Typecheck any instances whose gate list is empty.

 * Turn the set of pairs into a finite map as follows: for each pair `(fid,
 g:gs)`, add `g -> (fid, gs)` to the finite map.  Tis is the **gate map**.

 * After typechecking a SCC of types/classes, take each one `T` in turn.
 Look up `T` in the gate map.  For each `(fid, gs)` that it maps to, if
 `gs` is empty, that instance is ready to typecheck; if not, take one gate
 from `gs`. If it already in the type env, drop it and take another from
 `gs`.  Once you find on active gate (i.e. not yet type-checked) and re-add
 the depleted pair to the gate map as before.

 That's it really.  Essentially we cross off the gate vars one by one until
 none are left.

 You'd need to document this carefully.

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