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