compiler/typecheck/TcInstDcls.lhs

   1 %
   2 % (c) The University of Glasgow 2006
   3 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
   4 %
   5
   6 TcInstDecls: Typechecking instance declarations
   7
   8 \begin{code}
   9 module TcInstDcls ( tcInstDecls1, tcInstDecls2 ) where
  10
  11 import HsSyn
  12 import TcBinds
  13 import TcTyClsDecls
  14 import TcClassDcl
  15 import TcRnMonad
  16 import TcMType
  17 import TcType
  18 import Inst
  19 import InstEnv
  20 import FamInst
  21 import FamInstEnv
  22 import TcDeriv
  23 import TcEnv
  24 import RnEnv    ( lookupGlobalOccRn )
  25 import RnSource ( addTcgDUs )
  26 import TcHsType
  27 import TcUnify
  28 import TcSimplify
  29 import Type
  30 import Coercion
  31 import TyCon
  32 import TypeRep
  33 import DataCon
  34 import Class
  35 import Var
  36 import Id
  37 import MkId
  38 import Name
  39 import NameSet
  40 import DynFlags
  41 import SrcLoc
  42 import Util
  43 import Outputable
  44 import Bag
  45 import BasicTypes
  46 import HscTypes
  47 import FastString
  48
  49 import Data.Maybe
  50 import Control.Monad
  51 import Data.List
  52
  53 #include "HsVersions.h"
  54 \end{code}
  55
  56 Typechecking instance declarations is done in two passes. The first
  57 pass, made by @tcInstDecls1@, collects information to be used in the
  58 second pass.
  59
  60 This pre-processed info includes the as-yet-unprocessed bindings
  61 inside the instance declaration.  These are type-checked in the second
  62 pass, when the class-instance envs and GVE contain all the info from
  63 all the instance and value decls.  Indeed that's the reason we need
  64 two passes over the instance decls.
  65
  66
  67 Note [How instance declarations are translated]
  68 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  69 Here is how we translation instance declarations into Core
  70
  71 Running example:
  72         class C a where
  73            op1, op2 :: Ix b => a -> b -> b
  74            op2 = <dm-rhs>
  75
  76         instance C a => C [a]
  77            {-# INLINE [2] op1 #-}
  78            op1 = <rhs>
  79 ===>
  80         -- Method selectors
  81         op1,op2 :: forall a. C a => forall b. Ix b => a -> b -> b
  82         op1 = ...
  83         op2 = ...
  84
  85         -- Default methods get the 'self' dictionary as argument
  86         -- so they can call other methods at the same type
  87         -- Default methods get the same type as their method selector
  88         $dmop2 :: forall a. C a => forall b. Ix b => a -> b -> b
  89         $dmop2 = /\a. \(d:C a). /\b. \(d2: Ix b). <dm-rhs>
  90                -- NB: type variables 'a' and 'b' are *both* in scope in <dm-rhs>
  91                -- Note [Tricky type variable scoping]
  92
  93         -- A top-level definition for each instance method
  94         -- Here op1_i, op2_i are the "instance method Ids"
  95         {-# INLINE [2] op1_i #-}  -- From the instance decl bindings
  96         op1_i, op2_i :: forall a. C a => forall b. Ix b => [a] -> b -> b
  97         op1_i = /\a. \(d:C a).
  98                let this :: C [a]
  99                    this = df_i a d
 100                      -- Note [Subtle interaction of recursion and overlap]
 101
 102                    local_op1 :: forall b. Ix b => [a] -> b -> b
 103                    local_op1 = <rhs>
 104                      -- Source code; run the type checker on this
 105                      -- NB: Type variable 'a' (but not 'b') is in scope in <rhs>
 106                      -- Note [Tricky type variable scoping]
 107
 108                in local_op1 a d
 109
 110         op2_i = /\a \d:C a. $dmop2 [a] (df_i a d)
 111
 112         -- The dictionary function itself
 113         {-# INLINE df_i #-}     -- Always inline dictionary functions
 114         df_i :: forall a. C a -> C [a]
 115         df_i = /\a. \d:C a. letrec d' = MkC (op1_i  a   d)
 116                                             ($dmop2 [a] d')
 117                             in d'
 118                 -- But see Note [Default methods in instances]
 119                 -- We can't apply the type checker to the default-method call
 120
 121 * The dictionary function itself is inlined as vigorously as we
 122   possibly can, so that we expose that dictionary constructor to
 123   selectors as much as poss.  That is why the op_i stuff is in
 124   *separate* bindings, so that the df_i binding is small enough
 125   to inline.  See Note [Inline dfuns unconditionally].
 126
 127 * Note that df_i may be mutually recursive with both op1_i and op2_i.
 128   It's crucial that df_i is not chosen as the loop breaker, even
 129   though op1_i has a (user-specified) INLINE pragma.
 130   Not even once!  Else op1_i, op2_i may be inlined into df_i.
 131
 132 * Instead the idea is to inline df_i into op1_i, which may then select
 133   methods from the MkC record, and thereby break the recursion with
 134   df_i, leaving a *self*-recurisve op1_i.  (If op1_i doesn't call op at
 135   the same type, it won't mention df_i, so there won't be recursion in
 136   the first place.)
 137
 138 * If op1_i is marked INLINE by the user there's a danger that we won't
 139   inline df_i in it, and that in turn means that (since it'll be a
 140   loop-breaker because df_i isn't), op1_i will ironically never be
 141   inlined.  We need to fix this somehow -- perhaps allowing inlining
 142   of INLINE functions inside other INLINE functions.
 143
 144 Note [Subtle interaction of recursion and overlap]
 145 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 146 Consider this
 147   class C a where { op1,op2 :: a -> a }
 148   instance C a => C [a] where
 149     op1 x = op2 x ++ op2 x
 150     op2 x = ...
 151   intance C [Int] where
 152     ...
 153
 154 When type-checking the C [a] instance, we need a C [a] dictionary (for
 155 the call of op2).  If we look up in the instance environment, we find
 156 an overlap.  And in *general* the right thing is to complain (see Note
 157 [Overlapping instances] in InstEnv).  But in *this* case it's wrong to
 158 complain, because we just want to delegate to the op2 of this same
 159 instance.
 160
 161 Why is this justified?  Because we generate a (C [a]) constraint in
 162 a context in which 'a' cannot be instantiated to anything that matches
 163 other overlapping instances, or else we would not be excecuting this
 164 version of op1 in the first place.
 165
 166 It might even be a bit disguised:
 167
 168   nullFail :: C [a] => [a] -> [a]
 169   nullFail x = op2 x ++ op2 x
 170
 171   instance C a => C [a] where
 172     op1 x = nullFail x
 173
 174 Precisely this is used in package 'regex-base', module Context.hs.
 175 See the overlapping instances for RegexContext, and the fact that they
 176 call 'nullFail' just like the example above.  The DoCon package also
 177 does the same thing; it shows up in module Fraction.hs
 178
 179 Conclusion: when typechecking the methods in a C [a] instance, we want
 180 to have C [a] available.  That is why we have the strange local
 181 definition for 'this' in the definition of op1_i in the example above.
 182 We can typecheck the defintion of local_op1, and when doing tcSimplifyCheck
 183 we supply 'this' as a given dictionary.  Only needed, though, if there
 184 are some type variales involved; otherwise there can be no overlap and
 185 none of this arises.
 186
 187 Note [Tricky type variable scoping]
 188 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 189 In our example
 190         class C a where
 191            op1, op2 :: Ix b => a -> b -> b
 192            op2 = <dm-rhs>
 193
 194         instance C a => C [a]
 195            {-# INLINE [2] op1 #-}
 196            op1 = <rhs>
 197
 198 note that 'a' and 'b' are *both* in scope in <dm-rhs>, but only 'a' is
 199 in scope in <rhs>.  In particular, we must make sure that 'b' is in
 200 scope when typechecking <dm-rhs>.  This is achieved by subFunTys,
 201 which brings appropriate tyvars into scope. This happens for both
 202 <dm-rhs> and for <rhs>, but that doesn't matter: the *renamer* will have
 203 complained if 'b' is mentioned in <rhs>.
 204
 205 Note [Inline dfuns unconditionally]
 206 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 207 The code above unconditionally inlines dict funs.  Here's why.
 208 Consider this program:
 209
 210     test :: Int -> Int -> Bool
 211     test x y = (x,y) == (y,x) || test y x
 212     -- Recursive to avoid making it inline.
 213
 214 This needs the (Eq (Int,Int)) instance.  If we inline that dfun
 215 the code we end up with is good:
 216
 217     Test.$wtest =
 218         \r -> case ==# [ww ww1] of wild {
 219                 PrelBase.False -> Test.$wtest ww1 ww;
 220                 PrelBase.True ->
 221                   case ==# [ww1 ww] of wild1 {
 222                     PrelBase.False -> Test.$wtest ww1 ww;
 223                     PrelBase.True -> PrelBase.True [];
 224                   };
 225             };
 226     Test.test = \r [w w1]
 227             case w of w2 {
 228               PrelBase.I# ww ->
 229                   case w1 of w3 { PrelBase.I# ww1 -> Test.$wtest ww ww1; };
 230             };
 231
 232 If we don't inline the dfun, the code is not nearly as good:
 233
 234     (==) = case PrelTup.$fEq(,) PrelBase.$fEqInt PrelBase.$fEqInt of tpl {
 235               PrelBase.:DEq tpl1 tpl2 -> tpl2;
 236             };
 237
 238     Test.$wtest =
 239         \r [ww ww1]
 240             let { y = PrelBase.I#! [ww1]; } in
 241             let { x = PrelBase.I#! [ww]; } in
 242             let { sat_slx = PrelTup.(,)! [y x]; } in
 243             let { sat_sly = PrelTup.(,)! [x y];
 244             } in
 245               case == sat_sly sat_slx of wild {
 246                 PrelBase.False -> Test.$wtest ww1 ww;
 247                 PrelBase.True -> PrelBase.True [];
 248               };
 249
 250     Test.test =
 251         \r [w w1]
 252             case w of w2 {
 253               PrelBase.I# ww ->
 254                   case w1 of w3 { PrelBase.I# ww1 -> Test.$wtest ww ww1; };
 255             };
 256
 257 Why didn't GHC inline $fEq in those days?  Because it looked big:
 258
 259     PrelTup.zdfEqZ1T{-rcX-}
 260         = \ @ a{-reT-} :: * @ b{-reS-} :: *
 261             zddEq{-rf6-} _Ks :: {PrelBase.Eq{-23-} a{-reT-}}
 262             zddEq1{-rf7-} _Ks :: {PrelBase.Eq{-23-} b{-reS-}} ->
 263             let {
 264               zeze{-rf0-} _Kl :: (b{-reS-} -> b{-reS-} -> PrelBase.Bool{-3c-})
 265               zeze{-rf0-} = PrelBase.zeze{-01L-}@ b{-reS-} zddEq1{-rf7-} } in
 266             let {
 267               zeze1{-rf3-} _Kl :: (a{-reT-} -> a{-reT-} -> PrelBase.Bool{-3c-})
 268               zeze1{-rf3-} = PrelBase.zeze{-01L-} @ a{-reT-} zddEq{-rf6-} } in
 269             let {
 270               zeze2{-reN-} :: ((a{-reT-}, b{-reS-}) -> (a{-reT-}, b{-reS-})-> PrelBase.Bool{-3c-})
 271               zeze2{-reN-} = \ ds{-rf5-} _Ks :: (a{-reT-}, b{-reS-})
 272                                ds1{-rf4-} _Ks :: (a{-reT-}, b{-reS-}) ->
 273                              case ds{-rf5-}
 274                              of wild{-reW-} _Kd { (a1{-rf2-} _Ks, a2{-reZ-} _Ks) ->
 275                              case ds1{-rf4-}
 276                              of wild1{-reX-} _Kd { (b1{-rf1-} _Ks, b2{-reY-} _Ks) ->
 277                              PrelBase.zaza{-r4e-}
 278                                (zeze1{-rf3-} a1{-rf2-} b1{-rf1-})
 279                                (zeze{-rf0-} a2{-reZ-} b2{-reY-})
 280                              }
 281                              } } in
 282             let {
 283               a1{-reR-} :: ((a{-reT-}, b{-reS-})-> (a{-reT-}, b{-reS-})-> PrelBase.Bool{-3c-})
 284               a1{-reR-} = \ a2{-reV-} _Ks :: (a{-reT-}, b{-reS-})
 285                             b1{-reU-} _Ks :: (a{-reT-}, b{-reS-}) ->
 286                           PrelBase.not{-r6I-} (zeze2{-reN-} a2{-reV-} b1{-reU-})
 287             } in
 288               PrelBase.zdwZCDEq{-r8J-} @ (a{-reT-}, b{-reS-}) a1{-reR-} zeze2{-reN-})
 289
 290 and it's not as bad as it seems, because it's further dramatically
 291 simplified: only zeze2 is extracted and its body is simplified.
 292
 293
 294 %************************************************************************
 295 %*                                                                      *
 296 \subsection{Extracting instance decls}
 297 %*                                                                      *
 298 %************************************************************************
 299
 300 Gather up the instance declarations from their various sources
 301
 302 \begin{code}
 303 tcInstDecls1    -- Deal with both source-code and imported instance decls
 304    :: [LTyClDecl Name]          -- For deriving stuff
 305    -> [LInstDecl Name]          -- Source code instance decls
 306    -> [LDerivDecl Name]         -- Source code stand-alone deriving decls
 307    -> TcM (TcGblEnv,            -- The full inst env
 308            [InstInfo Name],     -- Source-code instance decls to process;
 309                                 -- contains all dfuns for this module
 310            HsValBinds Name)     -- Supporting bindings for derived instances
 311
 312 tcInstDecls1 tycl_decls inst_decls deriv_decls
 313   = checkNoErrs $
 314     do {        -- Stop if addInstInfos etc discovers any errors
 315                 -- (they recover, so that we get more than one error each
 316                 -- round)
 317
 318                 -- (1) Do class and family instance declarations
 319        ; let { idxty_decls = filter (isFamInstDecl . unLoc) tycl_decls }
 320        ; local_info_tycons <- mapAndRecoverM tcLocalInstDecl1  inst_decls
 321        ; idx_tycons        <- mapAndRecoverM tcIdxTyInstDeclTL idxty_decls
 322
 323        ; let { (local_info,
 324                 at_tycons_s)   = unzip local_info_tycons
 325              ; at_idx_tycons   = concat at_tycons_s ++ idx_tycons
 326              ; clas_decls      = filter (isClassDecl.unLoc) tycl_decls
 327              ; implicit_things = concatMap implicitTyThings at_idx_tycons
 328              ; aux_binds       = mkAuxBinds at_idx_tycons
 329              }
 330
 331                 -- (2) Add the tycons of indexed types and their implicit
 332                 --     tythings to the global environment
 333        ; tcExtendGlobalEnv (at_idx_tycons ++ implicit_things) $ do {
 334
 335                 -- (3) Instances from generic class declarations
 336        ; generic_inst_info <- getGenericInstances clas_decls
 337
 338                 -- Next, construct the instance environment so far, consisting
 339                 -- of
 340                 --   a) local instance decls
 341                 --   b) generic instances
 342                 --   c) local family instance decls
 343        ; addInsts local_info         $
 344          addInsts generic_inst_info  $
 345          addFamInsts at_idx_tycons   $ do {
 346
 347                 -- (4) Compute instances from "deriving" clauses;
 348                 -- This stuff computes a context for the derived instance
 349                 -- decl, so it needs to know about all the instances possible
 350                 -- NB: class instance declarations can contain derivings as
 351                 --     part of associated data type declarations
 352          failIfErrsM            -- If the addInsts stuff gave any errors, don't
 353                                 -- try the deriving stuff, becuase that may give
 354                                 -- more errors still
 355        ; (deriv_inst_info, deriv_binds, deriv_dus)
 356               <- tcDeriving tycl_decls inst_decls deriv_decls
 357        ; gbl_env <- addInsts deriv_inst_info getGblEnv
 358        ; return ( addTcgDUs gbl_env deriv_dus,
 359                   generic_inst_info ++ deriv_inst_info ++ local_info,
 360                   aux_binds `plusHsValBinds` deriv_binds)
 361     }}}
 362   where
 363     -- Make sure that toplevel type instance are not for associated types.
 364     -- !!!TODO: Need to perform this check for the TyThing of type functions,
 365     --          too.
 366     tcIdxTyInstDeclTL ldecl@(L loc decl) =
 367       do { tything <- tcFamInstDecl ldecl
 368          ; setSrcSpan loc $
 369              when (isAssocFamily tything) $
 370                addErr $ assocInClassErr (tcdName decl)
 371          ; return tything
 372          }
 373     isAssocFamily (ATyCon tycon) =
 374       case tyConFamInst_maybe tycon of
 375         Nothing       -> panic "isAssocFamily: no family?!?"
 376         Just (fam, _) -> isTyConAssoc fam
 377     isAssocFamily _ = panic "isAssocFamily: no tycon?!?"
 378
 379 assocInClassErr :: Name -> SDoc
 380 assocInClassErr name =
 381   ptext (sLit "Associated type") <+> quotes (ppr name) <+>
 382   ptext (sLit "must be inside a class instance")
 383
 384 addInsts :: [InstInfo Name] -> TcM a -> TcM a
 385 addInsts infos thing_inside
 386   = tcExtendLocalInstEnv (map iSpec infos) thing_inside
 387
 388 addFamInsts :: [TyThing] -> TcM a -> TcM a
 389 addFamInsts tycons thing_inside
 390   = tcExtendLocalFamInstEnv (map mkLocalFamInstTyThing tycons) thing_inside
 391   where
 392     mkLocalFamInstTyThing (ATyCon tycon) = mkLocalFamInst tycon
 393     mkLocalFamInstTyThing tything        = pprPanic "TcInstDcls.addFamInsts"
 394                                                     (ppr tything)
 395 \end{code}
 396
 397 \begin{code}
 398 tcLocalInstDecl1 :: LInstDecl Name
 399                  -> TcM (InstInfo Name, [TyThing])
 400         -- A source-file instance declaration
 401         -- Type-check all the stuff before the "where"
 402         --
 403         -- We check for respectable instance type, and context
 404 tcLocalInstDecl1 (L loc (InstDecl poly_ty binds uprags ats))
 405   = setSrcSpan loc                      $
 406     addErrCtxt (instDeclCtxt1 poly_ty)  $
 407
 408     do  { is_boot <- tcIsHsBoot
 409         ; checkTc (not is_boot || (isEmptyLHsBinds binds && null uprags))
 410                   badBootDeclErr
 411
 412         ; (tyvars, theta, tau) <- tcHsInstHead poly_ty
 413
 414         -- Now, check the validity of the instance.
 415         ; (clas, inst_tys) <- checkValidInstHead tau
 416         ; checkValidInstance tyvars theta clas inst_tys
 417
 418         -- Next, process any associated types.
 419         ; idx_tycons <- recoverM (return []) $
 420                      do { idx_tycons <- checkNoErrs $ mapAndRecoverM tcFamInstDecl ats
 421                         ; checkValidAndMissingATs clas (tyvars, inst_tys)
 422                                                   (zip ats idx_tycons)
 423                         ; return idx_tycons }
 424
 425         -- Finally, construct the Core representation of the instance.
 426         -- (This no longer includes the associated types.)
 427         ; dfun_name <- newDFunName clas inst_tys (getLoc poly_ty)
 428                 -- Dfun location is that of instance *header*
 429         ; overlap_flag <- getOverlapFlag
 430         ; let (eq_theta,dict_theta) = partition isEqPred theta
 431               theta'         = eq_theta ++ dict_theta
 432               dfun           = mkDictFunId dfun_name tyvars theta' clas inst_tys
 433               ispec          = mkLocalInstance dfun overlap_flag
 434
 435         ; return (InstInfo { iSpec  = ispec,
 436                               iBinds = VanillaInst binds uprags },
 437                   idx_tycons)
 438         }
 439   where
 440     -- We pass in the source form and the type checked form of the ATs.  We
 441     -- really need the source form only to be able to produce more informative
 442     -- error messages.
 443     checkValidAndMissingATs :: Class
 444                             -> ([TyVar], [TcType])     -- instance types
 445                             -> [(LTyClDecl Name,       -- source form of AT
 446                                  TyThing)]             -- Core form of AT
 447                             -> TcM ()
 448     checkValidAndMissingATs clas inst_tys ats
 449       = do { -- Issue a warning for each class AT that is not defined in this
 450              -- instance.
 451            ; let class_ats   = map tyConName (classATs clas)
 452                  defined_ats = listToNameSet . map (tcdName.unLoc.fst)  $ ats
 453                  omitted     = filterOut (`elemNameSet` defined_ats) class_ats
 454            ; warn <- doptM Opt_WarnMissingMethods
 455            ; mapM_ (warnTc warn . omittedATWarn) omitted
 456
 457              -- Ensure that all AT indexes that correspond to class parameters
 458              -- coincide with the types in the instance head.  All remaining
 459              -- AT arguments must be variables.  Also raise an error for any
 460              -- type instances that are not associated with this class.
 461            ; mapM_ (checkIndexes clas inst_tys) ats
 462            }
 463
 464     checkIndexes clas inst_tys (hsAT, ATyCon tycon)
 465 -- !!!TODO: check that this does the Right Thing for indexed synonyms, too!
 466       = checkIndexes' clas inst_tys hsAT
 467                       (tyConTyVars tycon,
 468                        snd . fromJust . tyConFamInst_maybe $ tycon)
 469     checkIndexes _ _ _ = panic "checkIndexes"
 470
 471     checkIndexes' clas (instTvs, instTys) hsAT (atTvs, atTys)
 472       = let atName = tcdName . unLoc $ hsAT
 473         in
 474         setSrcSpan (getLoc hsAT)       $
 475         addErrCtxt (atInstCtxt atName) $
 476         case find ((atName ==) . tyConName) (classATs clas) of
 477           Nothing     -> addErrTc $ badATErr clas atName  -- not in this class
 478           Just atycon ->
 479             case assocTyConArgPoss_maybe atycon of
 480               Nothing   -> panic "checkIndexes': AT has no args poss?!?"
 481               Just poss ->
 482
 483                 -- The following is tricky!  We need to deal with three
 484                 -- complications: (1) The AT possibly only uses a subset of
 485                 -- the class parameters as indexes and those it uses may be in
 486                 -- a different order; (2) the AT may have extra arguments,
 487                 -- which must be type variables; and (3) variables in AT and
 488                 -- instance head will be different `Name's even if their
 489                 -- source lexemes are identical.
 490                 --
 491                 -- e.g.    class C a b c where
 492                 --           data D b a :: * -> *           -- NB (1) b a, omits c
 493                 --         instance C [x] Bool Char where
 494                 --           data D Bool [x] v = MkD x [v]  -- NB (2) v
 495                 --                -- NB (3) the x in 'instance C...' have differnt
 496                 --                --        Names to x's in 'data D...'
 497                 --
 498                 -- Re (1), `poss' contains a permutation vector to extract the
 499                 -- class parameters in the right order.
 500                 --
 501                 -- Re (2), we wrap the (permuted) class parameters in a Maybe
 502                 -- type and use Nothing for any extra AT arguments.  (First
 503                 -- equation of `checkIndex' below.)
 504                 --
 505                 -- Re (3), we replace any type variable in the AT parameters
 506                 -- that has the same source lexeme as some variable in the
 507                 -- instance types with the instance type variable sharing its
 508                 -- source lexeme.
 509                 --
 510                 let relevantInstTys = map (instTys !!) poss
 511                     instArgs        = map Just relevantInstTys ++
 512                                       repeat Nothing  -- extra arguments
 513                     renaming        = substSameTyVar atTvs instTvs
 514                 in
 515                 zipWithM_ checkIndex (substTys renaming atTys) instArgs
 516
 517     checkIndex ty Nothing
 518       | isTyVarTy ty         = return ()
 519       | otherwise            = addErrTc $ mustBeVarArgErr ty
 520     checkIndex ty (Just instTy)
 521       | ty `tcEqType` instTy = return ()
 522       | otherwise            = addErrTc $ wrongATArgErr ty instTy
 523
 524     listToNameSet = addListToNameSet emptyNameSet
 525
 526     substSameTyVar []       _            = emptyTvSubst
 527     substSameTyVar (tv:tvs) replacingTvs =
 528       let replacement = case find (tv `sameLexeme`) replacingTvs of
 529                         Nothing  -> mkTyVarTy tv
 530                         Just rtv -> mkTyVarTy rtv
 531           --
 532           tv1 `sameLexeme` tv2 =
 533             nameOccName (tyVarName tv1) == nameOccName (tyVarName tv2)
 534       in
 535       extendTvSubst (substSameTyVar tvs replacingTvs) tv replacement
 536 \end{code}
 537
 538
 539 %************************************************************************
 540 %*                                                                      *
 541       Type-checking instance declarations, pass 2
 542 %*                                                                      *
 543 %************************************************************************
 544
 545 \begin{code}
 546 tcInstDecls2 :: [LTyClDecl Name] -> [InstInfo Name]
 547              -> TcM (LHsBinds Id, TcLclEnv)
 548 -- (a) From each class declaration,
 549 --      generate any default-method bindings
 550 -- (b) From each instance decl
 551 --      generate the dfun binding
 552
 553 tcInstDecls2 tycl_decls inst_decls
 554   = do  { -- (a) Default methods from class decls
 555           (dm_binds_s, dm_ids_s) <- mapAndUnzipM tcClassDecl2 $
 556                                     filter (isClassDecl.unLoc) tycl_decls
 557         ; tcExtendIdEnv (concat dm_ids_s) $ do
 558
 559           -- (b) instance declarations
 560         ; inst_binds_s <- mapM tcInstDecl2 inst_decls
 561
 562           -- Done
 563         ; let binds = unionManyBags dm_binds_s `unionBags`
 564                       unionManyBags inst_binds_s
 565         ; tcl_env <- getLclEnv -- Default method Ids in here
 566         ; return (binds, tcl_env) }
 567
 568 tcInstDecl2 :: InstInfo Name -> TcM (LHsBinds Id)
 569 tcInstDecl2 (InstInfo { iSpec = ispec, iBinds = ibinds })
 570   = recoverM (return emptyLHsBinds)             $
 571     setSrcSpan loc                              $
 572     addErrCtxt (instDeclCtxt2 (idType dfun_id)) $
 573     tc_inst_decl2 dfun_id ibinds
 574  where
 575         dfun_id    = instanceDFunId ispec
 576         loc        = getSrcSpan dfun_id
 577 \end{code}
 578
 579
 580 \begin{code}
 581 tc_inst_decl2 :: Id -> InstBindings Name -> TcM (LHsBinds Id)
 582 -- Returns a binding for the dfun
 583
 584 ------------------------
 585 -- Derived newtype instances; surprisingly tricky!
 586 --
 587 --      class Show a => Foo a b where ...
 588 --      newtype N a = MkN (Tree [a]) deriving( Foo Int )
 589 --
 590 -- The newtype gives an FC axiom looking like
 591 --      axiom CoN a ::  N a ~ Tree [a]
 592 --   (see Note [Newtype coercions] in TyCon for this unusual form of axiom)
 593 --
 594 -- So all need is to generate a binding looking like:
 595 --      dfunFooT :: forall a. (Foo Int (Tree [a], Show (N a)) => Foo Int (N a)
 596 --      dfunFooT = /\a. \(ds:Show (N a)) (df:Foo (Tree [a])).
 597 --                case df `cast` (Foo Int (sym (CoN a))) of
 598 --                   Foo _ op1 .. opn -> Foo ds op1 .. opn
 599 --
 600 -- If there are no superclasses, matters are simpler, because we don't need the case
 601 -- see Note [Newtype deriving superclasses] in TcDeriv.lhs
 602
 603 tc_inst_decl2 dfun_id (NewTypeDerived coi)
 604   = do  { let rigid_info   = InstSkol
 605               origin       = SigOrigin rigid_info
 606               inst_ty      = idType dfun_id
 607         ; (inst_tvs', theta, inst_head_ty) <- tcSkolSigType rigid_info inst_ty
 608                 -- inst_head_ty is a PredType
 609
 610         ; let (cls, cls_inst_tys) = tcSplitDFunHead inst_head_ty
 611               (class_tyvars, sc_theta, _, _) = classBigSig cls
 612               cls_tycon = classTyCon cls
 613               sc_theta' = substTheta (zipOpenTvSubst class_tyvars cls_inst_tys) sc_theta
 614               Just (initial_cls_inst_tys, last_ty) = snocView cls_inst_tys
 615
 616               (rep_ty, wrapper)
 617                  = case coi of
 618                      IdCo   -> (last_ty, idHsWrapper)
 619                      ACo co -> (snd (coercionKind co), WpCast (mk_full_coercion co))
 620
 621                  -----------------------
 622                  --        mk_full_coercion
 623                  -- The inst_head looks like (C s1 .. sm (T a1 .. ak))
 624                  -- But we want the coercion (C s1 .. sm (sym (CoT a1 .. ak)))
 625                  --        with kind (C s1 .. sm (T a1 .. ak)  ~  C s1 .. sm <rep_ty>)
 626                  --        where rep_ty is the (eta-reduced) type rep of T
 627                  -- So we just replace T with CoT, and insert a 'sym'
 628                  -- NB: we know that k will be >= arity of CoT, because the latter fully eta-reduced
 629
 630               mk_full_coercion co = mkTyConApp cls_tycon
 631                                          (initial_cls_inst_tys ++ [mkSymCoercion co])
 632                  -- Full coercion : (Foo Int (Tree [a]) ~ Foo Int (N a)
 633
 634               rep_pred = mkClassPred cls (initial_cls_inst_tys ++ [rep_ty])
 635                  -- In our example, rep_pred is (Foo Int (Tree [a]))
 636
 637         ; sc_loc     <- getInstLoc InstScOrigin
 638         ; sc_dicts   <- newDictBndrs sc_loc sc_theta'
 639         ; inst_loc   <- getInstLoc origin
 640         ; dfun_dicts <- newDictBndrs inst_loc theta
 641         ; rep_dict   <- newDictBndr inst_loc rep_pred
 642         ; this_dict  <- newDictBndr inst_loc (mkClassPred cls cls_inst_tys)
 643
 644         -- Figure out bindings for the superclass context from dfun_dicts
 645         -- Don't include this_dict in the 'givens', else
 646         -- sc_dicts get bound by just selecting from this_dict!!
 647         ; sc_binds <- addErrCtxt superClassCtxt $
 648                       tcSimplifySuperClasses inst_loc this_dict dfun_dicts
 649                                              (rep_dict:sc_dicts)
 650
 651         -- It's possible that the superclass stuff might unified something
 652         -- in the envt with one of the clas_tyvars
 653         ; checkSigTyVars inst_tvs'
 654
 655         ; let coerced_rep_dict = wrapId wrapper (instToId rep_dict)
 656
 657         ; body <- make_body cls_tycon cls_inst_tys sc_dicts coerced_rep_dict
 658         ; let dict_bind = noLoc $ VarBind (instToId this_dict) (noLoc body)
 659
 660         ; return (unitBag $ noLoc $
 661                   AbsBinds inst_tvs' (map instToVar dfun_dicts)
 662                             [(inst_tvs', dfun_id, instToId this_dict, [])]
 663                             (dict_bind `consBag` sc_binds)) }
 664   where
 665       -----------------------
 666       --     (make_body C tys scs coreced_rep_dict)
 667       --                returns
 668       --     (case coerced_rep_dict of { C _ ops -> C scs ops })
 669       -- But if there are no superclasses, it returns just coerced_rep_dict
 670       -- See Note [Newtype deriving superclasses] in TcDeriv.lhs
 671
 672     make_body cls_tycon cls_inst_tys sc_dicts coerced_rep_dict
 673         | null sc_dicts         -- Case (a)
 674         = return coerced_rep_dict
 675         | otherwise             -- Case (b)
 676         = do { op_ids            <- newSysLocalIds (fsLit "op") op_tys
 677              ; dummy_sc_dict_ids <- newSysLocalIds (fsLit "sc") (map idType sc_dict_ids)
 678              ; let the_pat = ConPatOut { pat_con = noLoc cls_data_con, pat_tvs = [],
 679                                          pat_dicts = dummy_sc_dict_ids,
 680                                          pat_binds = emptyLHsBinds,
 681                                          pat_args = PrefixCon (map nlVarPat op_ids),
 682                                          pat_ty = pat_ty}
 683                    the_match = mkSimpleMatch [noLoc the_pat] the_rhs
 684                    the_rhs = mkHsConApp cls_data_con cls_inst_tys $
 685                              map HsVar (sc_dict_ids ++ op_ids)
 686
 687                 -- Warning: this HsCase scrutinises a value with a PredTy, which is
 688                 --          never otherwise seen in Haskell source code. It'd be
 689                 --          nicer to generate Core directly!
 690              ; return (HsCase (noLoc coerced_rep_dict) $
 691                        MatchGroup [the_match] (mkFunTy pat_ty pat_ty)) }
 692         where
 693           sc_dict_ids  = map instToId sc_dicts
 694           pat_ty       = mkTyConApp cls_tycon cls_inst_tys
 695           cls_data_con = head (tyConDataCons cls_tycon)
 696           cls_arg_tys  = dataConInstArgTys cls_data_con cls_inst_tys
 697           op_tys       = dropList sc_dict_ids cls_arg_tys
 698
 699 ------------------------
 700 -- Ordinary instances
 701
 702 tc_inst_decl2 dfun_id (VanillaInst monobinds uprags)
 703   = do { let rigid_info = InstSkol
 704              inst_ty    = idType dfun_id
 705
 706         -- Instantiate the instance decl with skolem constants
 707        ; (inst_tyvars', dfun_theta', inst_head') <- tcSkolSigType rigid_info inst_ty
 708                 -- These inst_tyvars' scope over the 'where' part
 709                 -- Those tyvars are inside the dfun_id's type, which is a bit
 710                 -- bizarre, but OK so long as you realise it!
 711        ; let
 712             (clas, inst_tys') = tcSplitDFunHead inst_head'
 713             (class_tyvars, sc_theta, _, op_items) = classBigSig clas
 714
 715              -- Instantiate the super-class context with inst_tys
 716             sc_theta' = substTheta (zipOpenTvSubst class_tyvars inst_tys') sc_theta
 717             origin    = SigOrigin rigid_info
 718
 719          -- Create dictionary Ids from the specified instance contexts.
 720        ; sc_loc     <- getInstLoc InstScOrigin
 721        ; sc_dicts   <- newDictOccs sc_loc sc_theta'             -- These are wanted
 722        ; inst_loc   <- getInstLoc origin
 723        ; dfun_dicts <- newDictBndrs inst_loc dfun_theta'        -- Includes equalities
 724        ; this_dict  <- newDictBndr inst_loc (mkClassPred clas inst_tys')
 725
 726                 -- Default-method Ids may be mentioned in synthesised RHSs,
 727                 -- but they'll already be in the environment.
 728
 729         -- Typecheck the methods
 730        ; let this_dict_id  = instToId this_dict
 731              dfun_lam_vars = map instToVar dfun_dicts   -- Includes equalities
 732              prag_fn    = mkPragFun uprags
 733              loc        = getSrcSpan dfun_id
 734              tc_meth    = tcInstanceMethod loc clas inst_tyvars'
 735                                  dfun_dicts
 736                                  dfun_theta' inst_tys'
 737                                  this_dict dfun_id
 738                                  prag_fn monobinds
 739        ; (meth_exprs, meth_binds) <- tcExtendTyVarEnv inst_tyvars'  $
 740                                 mapAndUnzipM tc_meth op_items
 741
 742          -- Figure out bindings for the superclass context
 743          -- Don't include this_dict in the 'givens', else
 744          -- sc_dicts get bound by just selecting  from this_dict!!
 745        ; sc_binds <- addErrCtxt superClassCtxt $
 746                      tcSimplifySuperClasses inst_loc this_dict dfun_dicts sc_dicts
 747                 -- Note [Recursive superclasses]
 748
 749         -- It's possible that the superclass stuff might unified something
 750         -- in the envt with one of the inst_tyvars'
 751        ; checkSigTyVars inst_tyvars'
 752
 753        -- Deal with 'SPECIALISE instance' pragmas
 754        ;  prags <- tcPrags dfun_id (filter isSpecInstLSig uprags)
 755
 756        -- Create the result bindings
 757        ; let dict_constr   = classDataCon clas
 758              inline_prag | null dfun_dicts  = []
 759                          | otherwise        = [L loc (InlinePrag (alwaysInlineSpec FunLike))]
 760                      -- Always inline the dfun; this is an experimental decision
 761                      -- because it makes a big performance difference sometimes.
 762                      -- Often it means we can do the method selection, and then
 763                      -- inline the method as well.  Marcin's idea; see comments below.
 764                      --
 765                      -- BUT: don't inline it if it's a constant dictionary;
 766                      -- we'll get all the benefit without inlining, and we get
 767                      -- a **lot** of code duplication if we inline it
 768                      --
 769                      --      See Note [Inline dfuns] below
 770
 771              sc_dict_vars  = map instToVar sc_dicts
 772              dict_bind     = L loc (VarBind this_dict_id dict_rhs)
 773              dict_rhs      = foldl (\ f a -> L loc (HsApp f (L loc a))) inst_constr meth_exprs
 774              inst_constr   = L loc $ wrapId (mkWpApps sc_dict_vars <.> mkWpTyApps inst_tys')
 775                                        (dataConWrapId dict_constr)
 776                      -- We don't produce a binding for the dict_constr; instead we
 777                      -- rely on the simplifier to unfold this saturated application
 778                      -- We do this rather than generate an HsCon directly, because
 779                      -- it means that the special cases (e.g. dictionary with only one
 780                      -- member) are dealt with by the common MkId.mkDataConWrapId code rather
 781                      -- than needing to be repeated here.
 782
 783
 784              main_bind = noLoc $ AbsBinds
 785                                  inst_tyvars'
 786                                  dfun_lam_vars
 787                                  [(inst_tyvars', dfun_id, this_dict_id, inline_prag ++ prags)]
 788                                  (dict_bind `consBag` sc_binds)
 789
 790        ; showLIE (text "instance")
 791        ; return (main_bind `consBag` unionManyBags meth_binds) }
 792 \end{code}
 793
 794 Note [Recursive superclasses]
 795 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 796 See Trac #1470 for why we would *like* to add "this_dict" to the
 797 available instances here.  But we can't do so because then the superclases
 798 get satisfied by selection from this_dict, and that leads to an immediate
 799 loop.  What we need is to add this_dict to Avails without adding its
 800 superclasses, and we currently have no way to do that.
 801
 802
 803 %************************************************************************
 804 %*                                                                      *
 805       Type-checking an instance method
 806 %*                                                                      *
 807 %************************************************************************
 808
 809 tcInstanceMethod
 810 - Make the method bindings, as a [(NonRec, HsBinds)], one per method
 811 - Remembering to use fresh Name (the instance method Name) as the binder
 812 - Bring the instance method Ids into scope, for the benefit of tcInstSig
 813 - Use sig_fn mapping instance method Name -> instance tyvars
 814 - Ditto prag_fn
 815 - Use tcValBinds to do the checking
 816
 817 \begin{code}
 818 tcInstanceMethod :: SrcSpan -> Class -> [TcTyVar] -> [Inst]
 819                  -> TcThetaType -> [TcType]
 820                  -> Inst -> Id
 821                  -> TcPragFun -> LHsBinds Name
 822                  -> (Id, DefMeth)
 823                  -> TcM (HsExpr Id, LHsBinds Id)
 824         -- The returned inst_meth_ids all have types starting
 825         --      forall tvs. theta => ...
 826
 827 tcInstanceMethod loc clas tyvars dfun_dicts theta inst_tys
 828                  this_dict dfun_id prag_fn binds_in (sel_id, dm_info)
 829   = do  { cloned_this <- cloneDict this_dict
 830                 -- Need to clone the dict in case it is floated out, and
 831                 -- then clashes with its friends
 832         ; uniq1 <- newUnique
 833         ; let local_meth_name = mkInternalName uniq1 sel_occ loc   -- Same OccName
 834               this_dict_bind  = L loc $ VarBind (instToId cloned_this) $
 835                                 L loc $ wrapId meth_wrapper dfun_id
 836               mb_this_bind | null tyvars = Nothing
 837                            | otherwise   = Just (cloned_this, this_dict_bind)
 838                 -- Only need the this_dict stuff if there are type variables
 839                 -- involved; otherwise overlap is not possible
 840                 -- See Note [Subtle interaction of recursion and overlap]
 841
 842               tc_body rn_bind = do { (meth_id, tc_binds) <- tcInstanceMethodBody
 843                                                 InstSkol clas tyvars dfun_dicts theta inst_tys
 844                                                 mb_this_bind sel_id
 845                                                 local_meth_name
 846                                                 meth_sig_fn meth_prag_fn rn_bind
 847                                    ; return (wrapId meth_wrapper meth_id, tc_binds) }
 848
 849         ; case (findMethodBind sel_name local_meth_name binds_in, dm_info) of
 850                 -- There is a user-supplied method binding, so use it
 851             (Just user_bind, _) -> tc_body user_bind
 852
 853                 -- The user didn't supply a method binding, so we have to make
 854                 -- up a default binding, in a way depending on the default-method info
 855
 856             (Nothing, GenDefMeth) -> do         -- Derivable type classes stuff
 857                         { meth_bind <- mkGenericDefMethBind clas inst_tys sel_id local_meth_name
 858                         ; tc_body meth_bind }
 859
 860             (Nothing, NoDefMeth) -> do          -- No default method in the class
 861                         { warn <- doptM Opt_WarnMissingMethods
 862                         ; warnTc (warn  -- Warn only if -fwarn-missing-methods
 863                                   && reportIfUnused (getOccName sel_id))
 864                                         -- Don't warn about _foo methods
 865                                  omitted_meth_warn
 866                         ; return (error_rhs, emptyBag) }
 867
 868             (Nothing, DefMeth) -> do    -- An polymorphic default method
 869                         {   -- Build the typechecked version directly,
 870                             -- without calling typecheck_method;
 871                             -- see Note [Default methods in instances]
 872                           dm_name <- lookupGlobalOccRn (mkDefMethRdrName sel_name)
 873                                         -- Might not be imported, but will be an OrigName
 874                         ; dm_id   <- tcLookupId dm_name
 875                         ; return (wrapId dm_wrapper dm_id, emptyBag) } }
 876   where
 877     sel_name = idName sel_id
 878     sel_occ  = nameOccName sel_name
 879     this_dict_id = instToId this_dict
 880
 881     meth_prag_fn _ = prag_fn sel_name
 882     meth_sig_fn _  = Just []    -- The 'Just' says "yes, there's a type sig"
 883                         -- But there are no scoped type variables from local_method_id
 884                         -- Only the ones from the instance decl itself, which are already
 885                         -- in scope.  Example:
 886                         --      class C a where { op :: forall b. Eq b => ... }
 887                         --      instance C [c] where { op = <rhs> }
 888                         -- In <rhs>, 'c' is scope but 'b' is not!
 889
 890     error_rhs    = HsApp error_fun error_msg
 891     error_fun    = L loc $ wrapId (WpTyApp meth_tau) nO_METHOD_BINDING_ERROR_ID
 892     error_msg    = L loc (HsLit (HsStringPrim (mkFastString error_string)))
 893     meth_tau     = funResultTy (applyTys (idType sel_id) inst_tys)
 894     error_string = showSDoc (hcat [ppr loc, text "|", ppr sel_id ])
 895
 896     dm_wrapper   = WpApp this_dict_id <.> mkWpTyApps inst_tys
 897
 898     omitted_meth_warn :: SDoc
 899     omitted_meth_warn = ptext (sLit "No explicit method nor default method for")
 900                         <+> quotes (ppr sel_id)
 901
 902     dfun_lam_vars = map instToVar dfun_dicts
 903     meth_wrapper = mkWpApps dfun_lam_vars <.> mkWpTyApps (mkTyVarTys tyvars)
 904
 905
 906 wrapId :: HsWrapper -> id -> HsExpr id
 907 wrapId wrapper id = mkHsWrap wrapper (HsVar id)
 908 \end{code}
 909
 910 Note [Default methods in instances]
 911 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 912 Consider this
 913
 914    class Baz v x where
 915       foo :: x -> x
 916       foo y = y
 917
 918    instance Baz Int Int
 919
 920 From the class decl we get
 921
 922    $dmfoo :: forall v x. Baz v x => x -> x
 923
 924 Notice that the type is ambiguous.  That's fine, though. The instance decl generates
 925
 926    $dBazIntInt = MkBaz ($dmfoo Int Int $dBazIntInt)
 927
 928 BUT this does mean we must generate the dictionary translation directly, rather
 929 than generating source-code and type-checking it.  That was the bug ing
 930 Trac #1061. In any case it's less work to generate the translated version!
 931
 932
 933 %************************************************************************
 934 %*                                                                      *
 935 \subsection{Error messages}
 936 %*                                                                      *
 937 %************************************************************************
 938
 939 \begin{code}
 940 instDeclCtxt1 :: LHsType Name -> SDoc
 941 instDeclCtxt1 hs_inst_ty
 942   = inst_decl_ctxt (case unLoc hs_inst_ty of
 943                         HsForAllTy _ _ _ (L _ (HsPredTy pred)) -> ppr pred
 944                         HsPredTy pred                    -> ppr pred
 945                         _                                -> ppr hs_inst_ty)     -- Don't expect this
 946 instDeclCtxt2 :: Type -> SDoc
 947 instDeclCtxt2 dfun_ty
 948   = inst_decl_ctxt (ppr (mkClassPred cls tys))
 949   where
 950     (_,_,cls,tys) = tcSplitDFunTy dfun_ty
 951
 952 inst_decl_ctxt :: SDoc -> SDoc
 953 inst_decl_ctxt doc = ptext (sLit "In the instance declaration for") <+> quotes doc
 954
 955 superClassCtxt :: SDoc
 956 superClassCtxt = ptext (sLit "When checking the super-classes of an instance declaration")
 957
 958 atInstCtxt :: Name -> SDoc
 959 atInstCtxt name = ptext (sLit "In the associated type instance for") <+>
 960                   quotes (ppr name)
 961
 962 mustBeVarArgErr :: Type -> SDoc
 963 mustBeVarArgErr ty =
 964   sep [ ptext (sLit "Arguments that do not correspond to a class parameter") <+>
 965         ptext (sLit "must be variables")
 966       , ptext (sLit "Instead of a variable, found") <+> ppr ty
 967       ]
 968
 969 wrongATArgErr :: Type -> Type -> SDoc
 970 wrongATArgErr ty instTy =
 971   sep [ ptext (sLit "Type indexes must match class instance head")
 972       , ptext (sLit "Found") <+> quotes (ppr ty)
 973         <+> ptext (sLit "but expected") <+> quotes (ppr instTy)
 974       ]
 975 \end{code}