#13102: orphan family instances can leak through the EPS in --make mode -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * cc: ezyang (added) Comment: Are you sure? It used to be the case that instances simply accumulated, so a module could "see" an instance (of a type class, say) that it didn't import, even transitively. But I belived we fixed that some time ago. I think it's in the call to `hptInstances` in `tcRnImports`. Ah but that's the ''home'' package, and your point is about some external package. Maybe you are right... Can you show how this can compromise type safety. Presumably it's through an un-detected type-family inconsistency? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13102#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13102: orphan family instances can leak through the EPS in --make mode -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Aha! You are right! The relevant ticket is #2182. One thing unsaid there is that non-orphan instances cannot be a problem because the module defining a non-orphan instance must be in the transitive closure of modules below the one being compiled. It's just orphan modules that we need to take care about. A huge shortcoming is that this very cunning plan has no Note describing the Grand Plan, at least not that I can see. There ought to be one, with references to the note from the scattered bits of code that implement it. It does seem plausible that that the same thing would work for family instances. Hooray. Finally `hptInstances` appears to do the job (including family instances) for the home package, by glomming up all the instances from the home- package modules below this one. But the clever orphan module approach should work for the home package too, so perhaps we can kill off `hptInstances`? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13102#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13102: orphan family instances can leak through the EPS in --make mode -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): There are several issues here. Let's focus on external packages for now. By "instance" I mean type-class instance or family instance. 1. Ensuring we have ''enough'' instances. That is, have we loaded `M.hi`, and hence added its instances into the `eps_inst_env`? * For non-orphan instances, that's guaranteed. * Note that it's guaranteed even for wired-in type constructors because we do the `checkWiredInTyCon` or `ifCheckWiredInThing`. * For orphan instances we need to take care; I think we just aggressively load all orphan modules. 2. Ensuring we do not have ''too many'' instances. When doing instance lookup we don't want to "see" any instances that are not transitively below us. * Again this is guaranteed for non-orphan instances. * For orphan instances we use the cunning plan in comment:2. * Wired-in things are below everything so I think it's a non-issue. 3. Checking family-instance consistency. Here I am not so clear, but we should write down the plan. Does that taxonomy help? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13102#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13102: orphan family instances can leak through the EPS in --make mode -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: rwbarton Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by rwbarton): * owner: => rwbarton -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13102#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13102: orphan family instances can leak through the EPS in --make mode -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: rwbarton Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Ben Gamari ): In [changeset:"8f49f6de2121541d3bf8254abb402b6e7bfee8fb/ghc" 8f49f6d/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="8f49f6de2121541d3bf8254abb402b6e7bfee8fb" Add a failing test for #13102 Test Plan: harbormaster Reviewers: austin, ezyang, bgamari Reviewed By: bgamari Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D3005 GHC Trac Issues: #13102 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13102#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13102: orphan family instances can leak through the EPS in --make mode -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: rwbarton Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by ezyang): Just popping in: rwbarton, in the overloaded lists case, why don't we just consider `GHC.Exts` as visible always? In fact, we already do something like this for wired in things: see `Note [Loading instances for wired-in things]`. There should only be a fixed number of these... -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13102#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13102: orphan family instances can leak through the EPS in --make mode -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: rwbarton Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by rwbarton): Let me try to explain the situation with `OverloadedLists` more clearly. I'm just going to talk about the ''class'' instances since there is already something subtle going on there. Say that a class instance is * ''loaded'' if we have read the interface file that contains it; in this case into the EPS. I don't think it makes a real difference here, so I'll always assume we are talking about instances defined in external packages. * ''transitively imported'' from the module `M` that we're compiling if `M` imports (directly or indirectly) the module `D` that defines the class instance in question. * ''visible'' in the module `M` that we're compiling if we are allowed to use the instance to solve a constraint while compiling `M`. Clearly an instance must be loaded in order to be visible, but otherwise it's our job to implement the test for visibility so that it corresponds to the semantics that we want. The Haskell Report says

Thus, an instance declaration is in scope if and only if a chain of `import` declarations leads to the module containing the instance declaration.

so we could simply define 1. A class instance is visible if and only if it is transitively imported. However, GHC's implementation is actually 2. A class instance is visible if and only if ''either'' it is transitively imported, ''or'' it is a non-orphan instance: it mentions something (a class or type) in the instance head that is defined in the same module. The intention is that definition 2 is equivalent to definition 1, but cheaper to compute as we don't have to carry around a larger set of all transitively imported modules, and don't have to do a membership query in this set in the common case of a candidate matching instance that is non- orphan. See `Note [Instance lookup and orphan instances]`: {{{ Suppose we are compiling a module M, and we have a zillion packages loaded, and we are looking up an instance for C (T W). If we find a match in module 'X' from package 'p', should be "in scope"; that is, is p:X in the transitive closure of modules imported from M? The difficulty is that the "zillion packages" might include ones loaded through earlier invocations of the GHC API, or earlier module loads in GHCi. They might not be in the dependencies of M itself; and if not, the instances in them should not be visible. Trac #2182, #8427. There are two cases: * If the instance is *not an orphan*, then module X defines C, T, or W. And in order for those types to be involved in typechecking M, it must be that X is in the transitive closure of M's imports. So we can use the instance. * If the instance *is an orphan*, the above reasoning does not apply. So we keep track of the set of orphan modules transitively below M; this is the ie_visible field of InstEnvs, of type VisibleOrphanModules. If module p:X is in this set, then we can use the instance, otherwise we can't. }}} Now, here's what happens in the situation with `OverloadedLists`. With this extension enabled, a list literal `[True]` desugars to a function call `fromListN 1 (True : [])`, where the `[]` in the desugaring is the constructor of the list type. I call this desugaring, but the reference to `fromListN` is really inserted in the renamer (`rnExpr (ExplicitList _ _ exps) = ...`). `fromListN` is a method of the class `IsList`, which is defined in `GHC.Exts`: {{{#!hs class IsList l where type Item l fromList :: [Item l] -> l fromListN :: Int -> [Item l] -> l -- the Int is the length of the list fromListN _ = fromList toList :: l -> [Item l] }}} The instance for `[a]` is also defined in `GHC.Exts`: {{{#!hs instance IsList [a] where type (Item [a]) = a fromList = id toList = id }}} Crucially `GHC.Exts` is ''not'' transitively imported by `Prelude`; so typically it will not be transitively imported in a module that uses `OverloadedLists`. (You can verify this easily since `GHC.Exts` defines instances of the type family `Item`, and it doesn't show up as a family instance import of a module that only imports `Prelude`. But remember this whole comment is about class instances, not family instances.) So suppose we want to type check the program {{{#!hs {-# LANGUAGE OverloadedLists #-} module Ol where f :: [Bool] f = [True] }}} It means {{{#!hs f :: [Bool] f = GHC.Exts.fromListN 1 (True : []) }}} and recall {{{#!hs fromListN :: IsList l => Int -> [Item l] -> l }}} So in order to type check `f`, we need to use the instance `IsList [a]`. (Let's ignore the issue of knowing that `Item [a] ~ a`, since this comment is not about family instance visibility.) The instance `IsList [a]` will certainly have been loaded, because we read the interface file for `GHC.Exts` in order to find out the type for `fromListN`. Now, consider our definitions 1 and 2 of class instance visibility. According to definition 1, the instance `IsList [a]` ''should not'' be visible because the module `GHC.Exts` in which it is defined is not transitively imported by the module we are compiling. However, the instance `IsList [a]` is not an orphan! So according to definition 2, the instance ''is'' visible. The upshot is that GHC treats the instance as visible and accepts the program, which is certainly the desired end result; but a strict interpretation of the standard says that GHC should reject the program, given the way that the `IsList` class is implemented. The problem is with this sentence from the Note quoted above:

And in order for those types [here `IsList`] to be involved in typechecking M, it must be that X is in the transitive closure of M's imports.

It's not true in this example. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13102#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13102: orphan family instances can leak through the EPS in --make mode -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: rwbarton Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by ezyang): simonpj and I chatted about this, and we came up with a short term and a long term solution. * The short term solution is to special-case GHC.Exts so that it is always visible. This should be pretty easy to do. * But, if we look at how the compiler handles finding instances of wired in things, there is a `checkWiredInTyCon` function which we specifically call in order to bring in the instances for a wired in thing. So really, the desired semantics are, if we call `checkWiredInTyCon` on a `TyCon`, we want to act AS IF we had an implicit import of this `TyCon`. This means checking it for family instance consistency (see #13251) and considering it visible. But now that I think about it, it seems very awkward to actually get this info to the list of visible info, since we won't really bang on the TyCon until we're about to do an instance lookup; might be a little fiddly to get that to work. But the long term solution is something like this: an implicit reference to a wired in thing counts as an import to that defining module. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13102#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13102: orphan family instances can leak through the EPS in --make mode -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: rwbarton Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by ezyang): * I think there are two possible cases where code change would be necessary (but I don't think any of them actually apply): - If GHC.Exts defined orphans, we should still treat those orphans as visible. But I don't think we have any orphans. Would be good to check. - You are right that one can't define an instance of IsList without importing it, so we should be able to get away without the check. And evidently this doesn't apply if GHC.Exts does have orphans, because that means we can define an instance without importing GHC.Exts * Yes, I guess we have to handle known-key things. Hmm, we don't call `checkWiredInTyCon` for those, so there might be trouble. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13102#comment:17 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13102: orphan family instances can leak through the EPS in --make mode -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: rwbarton Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Ben Gamari ): In [changeset:"bedcb71659253bb8ab5d449df8e3ee884cc85d46/ghc" bedcb71/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="bedcb71659253bb8ab5d449df8e3ee884cc85d46" Check local type family instances against all imported ones We previously checked type family instance declarations in a module for consistency with all instances that we happened to have read into the EPS or HPT. It was possible to arrange that an imported type family instance (used by an imported function) was in a module whose interface file was never read during compilation; then we wouldn't check consistency of local instances with this imported instance and as a result type safety was lost. With this patch, we still check consistency of local type family instances with all type family instances that we have loaded; but we make sure to load the interface files of all our imports that define family instances first. More selective consistency checking is left to #13102. On the other hand, we can now safely assume when we import a module that it has been checked for consistency with its imports. So we can save checking in checkFamInstConsistency, and overall we should have less work to do now. This patch also adds a note describing the Plan for ensuring type family consistency. Test Plan: Two new tests added; harbormaster Reviewers: austin, simonpj, bgamari Reviewed By: simonpj, bgamari Subscribers: ggreif, thomie Differential Revision: https://phabricator.haskell.org/D2992 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13102#comment:19 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#13102: orphan family instances can leak through the EPS in --make mode -------------------------------------+------------------------------------- Reporter: rwbarton | Owner: rwbarton Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: 9729 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by crockeea): * related: => 9729 Comment: ezyang thought that #9729 might be an example of this bug. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13102#comment:21 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler