Opened 2 years ago

Last modified 2 years ago

#11999 new bug

expressing injectivity on functional dependencies gives orphan instances warnings

Reported by: dredozubov Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.10.3
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

Class.hs

{-# LANGUAGE DataKinds, FlexibleInstances, FunctionalDependencies, KindSignatures, MultiParamTypeClasses, TypeFamilies #-}

module Class where

class C a b | a -> b, b -> a

Lib.hs

{-# LANGUAGE DataKinds, FlexibleInstances, MultiParamTypeClasses, TypeFamilies #-}

module Lib where

import Class


newtype Local = Local ()

instance C Local ()

gives

/Users/dr/workspace/broken-ophans-ghc/src/Lib.hs:10:1: warning: [-Worphans]
    Orphan instance: instance C Local ()
    To avoid this
        move the instance declaration to the module of the class or of the type, or
        wrap the type with a newtype and declare the instance on the new type.

It seems weird to me and it is either a bug in the orphan instances checker or there is some fundamental aspect which i don't undestand. I've been able to reproduce this with 7.10.3 and 8-rc4. I've compiled a git repo with minimalistic example of this: https://github.com/dredozubov/broken-instances-minimal

Change History (2)

comment:1 Changed 2 years ago by dredozubov

This code comment was brought to my attention on IRC:

Note [Orphans]
~~~~~~~~~~~~~~
Class instances, rules, and family instances are divided into orphans
and non-orphans.  Roughly speaking, an instance/rule is an orphan if
its left hand side mentions nothing defined in this module.  Orphan-hood
has two major consequences

 * A module that contains orphans is called an "orphan module".  If
   the module being compiled depends (transitively) on an oprhan
   module M, then M.hi is read in regardless of whether M is oherwise
   needed. This is to ensure that we don't miss any instance decls in
   M.  But it's painful, because it means we need to keep track of all
   the orphan modules below us.

 * A non-orphan is not finger-printed separately.  Instead, for
   fingerprinting purposes it is treated as part of the entity it
   mentions on the LHS.  For example
      data T = T1 | T2
      instance Eq T where ....
   The instance (Eq T) is incorprated as part of T's fingerprint.

   In constrast, orphans are all fingerprinted together in the
   mi_orph_hash field of the ModIface.

   See MkIface.addFingerprints.

Orphan-hood is computed
  * For class instances:
      when we make a ClsInst
    (because it is needed during instance lookup)

  * For rules and family instances:
       when we generate an IfaceRule (MkIface.coreRuleToIfaceRule)
                     or IfaceFamInst (MkIface.instanceToIfaceInst)

Note [When exactly is an instance decl an orphan?]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  (see MkIface.instanceToIfaceInst, which implements this)
Roughly speaking, an instance is an orphan if its head (after the =>)
mentions nothing defined in this module.

Functional dependencies complicate the situation though. Consider

  module M where { class C a b | a -> b }

and suppose we are compiling module X:

  module X where
        import M
        data T = ...
        instance C Int T where ...

This instance is an orphan, because when compiling a third module Y we
might get a constraint (C Int v), and we'd want to improve v to T.  So
we must make sure X's instances are loaded, even if we do not directly
use anything from X.

More precisely, an instance is an orphan iff

  If there are no fundeps, then at least of the names in
  the instance head is locally defined.

  If there are fundeps, then for every fundep, at least one of the
  names free in a *non-determined* part of the instance head is
  defined in this module.

(Note that these conditions hold trivially if the class is locally
defined.)

lpaste version: http://lpaste.net/162420.

It mentions this issue, but it still feels like a broken behavior to me. I'll leave it to the people more knowledgeable that me to decide if that's can be considered a bug.

Last edited 2 years ago by dredozubov (previous) (diff)

comment:2 in reply to:  1 Changed 2 years ago by rahulmutt

Note [When exactly is an instance decl an orphan?]

(see MkIface.instanceToIfaceInst, which implements this)

Roughly speaking, an instance is an orphan if its head (after the =>) mentions nothing defined in this module.

Functional dependencies complicate the situation though. Consider

module M where { class C a b | a -> b }

and suppose we are compiling module X:

module X where

import M data T = ... instance C Int T where ...

This instance is an orphan, because when compiling a third module Y we might get a constraint (C Int v), and we'd want to improve v to T. So we must make sure X's instances are loaded, even if we do not directly use anything from X.

This part of the note explains why your example would be considered an orphan instance. Otherwise you can define instances that may not be "seen" as intended.

Note: See TracTickets for help on using tickets.