compiler/typecheck/TcRnTypes.lhs

   1
   2 % (c) The University of Glasgow 2006
   3 % (c) The GRASP Project, Glasgow University, 1992-2002
   4 %
   5 \begin{code}
   6 module TcRnTypes(
   7         TcRnIf, TcRn, TcM, RnM, IfM, IfL, IfG, -- The monad is opaque outside this module
   8         TcRef,
   9
  10         -- The environment types
  11         Env(..),
  12         TcGblEnv(..), TcLclEnv(..),
  13         IfGblEnv(..), IfLclEnv(..),
  14
  15         -- Ranamer types
  16         ErrCtxt, RecFieldEnv(..),
  17         ImportAvails(..), emptyImportAvails, plusImportAvails,
  18         WhereFrom(..), mkModDeps,
  19
  20         -- Typechecker types
  21         TcTypeEnv, TcTyThing(..), pprTcTyThingCategory,
  22
  23         -- Template Haskell
  24         ThStage(..), topStage, topAnnStage, topSpliceStage,
  25         ThLevel, impLevel, outerLevel, thLevel,
  26
  27         -- Arrows
  28         ArrowCtxt(NoArrowCtxt), newArrowScope, escapeArrowScope,
  29
  30         -- Constraints
  31         Untouchables(..), inTouchableRange,
  32         WantedConstraints, emptyWanteds, andWanteds, extendWanteds,
  33         WantedConstraint(..), WantedEvVar(..), wantedEvVarLoc,
  34         wantedEvVarToVar, wantedEvVarPred, splitWanteds,
  35
  36         evVarsToWanteds,
  37         Implication(..),
  38         CtLoc(..), ctLocSpan, ctLocOrigin, setCtLocOrigin,
  39         CtOrigin(..), EqOrigin(..),
  40         WantedLoc, GivenLoc,
  41
  42         SkolemInfo(..),
  43
  44         -- Pretty printing
  45         pprEvVarTheta, pprWantedsWithLocs, pprWantedWithLoc,
  46         pprEvVars, pprEvVarWithType,
  47         pprArising, pprArisingAt,
  48
  49         -- Misc other types
  50         TcId, TcIdSet, TcTyVarBind(..), TcTyVarBinds
  51
  52   ) where
  53
  54 #include "HsVersions.h"
  55
  56 import HsSyn
  57 import HscTypes
  58 import Type
  59 import TcType
  60 import Annotations
  61 import InstEnv
  62 import FamInstEnv
  63 import IOEnv
  64 import RdrName
  65 import Name
  66 import NameEnv
  67 import NameSet
  68 import Var
  69 import VarEnv
  70 import Module
  71 import SrcLoc
  72 import VarSet
  73 import ErrUtils
  74 import UniqFM
  75 import UniqSupply
  76 import Unique
  77 import BasicTypes
  78 import Bag
  79 import Outputable
  80 import ListSetOps
  81 import FastString
  82 import StaticFlags( opt_ErrorSpans )
  83
  84 import Data.Set (Set)
  85 \end{code}
  86
  87
  88 %************************************************************************
  89 %*                                                                      *
  90                Standard monad definition for TcRn
  91     All the combinators for the monad can be found in TcRnMonad
  92 %*                                                                      *
  93 %************************************************************************
  94
  95 The monad itself has to be defined here, because it is mentioned by ErrCtxt
  96
  97 \begin{code}
  98 type TcRef a     = IORef a
  99 type TcId        = Id                   -- Type may be a TcType  DV: WHAT??????????
 100 type TcIdSet     = IdSet
 101
 102
 103 type TcRnIf a b c = IOEnv (Env a b) c
 104 type IfM lcl a  = TcRnIf IfGblEnv lcl a         -- Iface stuff
 105
 106 type IfG a  = IfM () a                          -- Top level
 107 type IfL a  = IfM IfLclEnv a                    -- Nested
 108 type TcRn a = TcRnIf TcGblEnv TcLclEnv a
 109 type RnM  a = TcRn a            -- Historical
 110 type TcM  a = TcRn a            -- Historical
 111 \end{code}
 112
 113 Representation of type bindings to uninstantiated meta variables used during
 114 constraint solving.
 115
 116 \begin{code}
 117 data TcTyVarBind = TcTyVarBind TcTyVar TcType
 118
 119 type TcTyVarBinds = Bag TcTyVarBind
 120
 121 instance Outputable TcTyVarBind where
 122   ppr (TcTyVarBind tv ty) = ppr tv <+> text ":=" <+> ppr ty
 123 \end{code}
 124
 125
 126 %************************************************************************
 127 %*                                                                      *
 128                 The main environment types
 129 %*                                                                      *
 130 %************************************************************************
 131
 132 \begin{code}
 133 data Env gbl lcl        -- Changes as we move into an expression
 134   = Env {
 135         env_top  :: HscEnv,     -- Top-level stuff that never changes
 136                                 -- Includes all info about imported things
 137
 138         env_us   :: {-# UNPACK #-} !(IORef UniqSupply),
 139                                 -- Unique supply for local varibles
 140
 141         env_gbl  :: gbl,        -- Info about things defined at the top level
 142                                 -- of the module being compiled
 143
 144         env_lcl  :: lcl         -- Nested stuff; changes as we go into
 145     }
 146
 147 -- TcGblEnv describes the top-level of the module at the
 148 -- point at which the typechecker is finished work.
 149 -- It is this structure that is handed on to the desugarer
 150
 151 data TcGblEnv
 152   = TcGblEnv {
 153         tcg_mod     :: Module,         -- ^ Module being compiled
 154         tcg_src     :: HscSource,
 155           -- ^ What kind of module (regular Haskell, hs-boot, ext-core)
 156
 157         tcg_rdr_env :: GlobalRdrEnv,   -- ^ Top level envt; used during renaming
 158         tcg_default :: Maybe [Type],
 159           -- ^ Types used for defaulting. @Nothing@ => no @default@ decl
 160
 161         tcg_fix_env   :: FixityEnv,     -- ^ Just for things in this module
 162         tcg_field_env :: RecFieldEnv,   -- ^ Just for things in this module
 163
 164         tcg_type_env :: TypeEnv,
 165           -- ^ Global type env for the module we are compiling now.  All
 166           -- TyCons and Classes (for this module) end up in here right away,
 167           -- along with their derived constructors, selectors.
 168           --
 169           -- (Ids defined in this module start in the local envt, though they
 170           --  move to the global envt during zonking)
 171
 172         tcg_type_env_var :: TcRef TypeEnv,
 173                 -- Used only to initialise the interface-file
 174                 -- typechecker in initIfaceTcRn, so that it can see stuff
 175                 -- bound in this module when dealing with hi-boot recursions
 176                 -- Updated at intervals (e.g. after dealing with types and classes)
 177
 178         tcg_inst_env     :: InstEnv,
 179           -- ^ Instance envt for /home-package/ modules; Includes the dfuns in
 180           -- tcg_insts
 181         tcg_fam_inst_env :: FamInstEnv, -- ^ Ditto for family instances
 182
 183                 -- Now a bunch of things about this module that are simply
 184                 -- accumulated, but never consulted until the end.
 185                 -- Nevertheless, it's convenient to accumulate them along
 186                 -- with the rest of the info from this module.
 187         tcg_exports :: [AvailInfo],     -- ^ What is exported
 188         tcg_imports :: ImportAvails,
 189           -- ^ Information about what was imported from where, including
 190           -- things bound in this module.
 191
 192         tcg_dus :: DefUses,
 193           -- ^ What is defined in this module and what is used.
 194           -- The latter is used to generate
 195           --
 196           --  (a) version tracking; no need to recompile if these things have
 197           --      not changed version stamp
 198           --
 199           --  (b) unused-import info
 200
 201         tcg_keep :: TcRef NameSet,
 202           -- ^ Locally-defined top-level names to keep alive.
 203           --
 204           -- "Keep alive" means give them an Exported flag, so that the
 205           -- simplifier does not discard them as dead code, and so that they
 206           -- are exposed in the interface file (but not to export to the
 207           -- user).
 208           --
 209           -- Some things, like dict-fun Ids and default-method Ids are "born"
 210           -- with the Exported flag on, for exactly the above reason, but some
 211           -- we only discover as we go.  Specifically:
 212           --
 213           --   * The to/from functions for generic data types
 214           --
 215           --   * Top-level variables appearing free in the RHS of an orphan
 216           --     rule
 217           --
 218           --   * Top-level variables appearing free in a TH bracket
 219
 220         tcg_inst_uses :: TcRef NameSet,
 221           -- ^ Home-package Dfuns actually used.
 222           --
 223           -- Used to generate version dependencies This records usages, rather
 224           -- like tcg_dus, but it has to be a mutable variable so it can be
 225           -- augmented when we look up an instance.  These uses of dfuns are
 226           -- rather like the free variables of the program, but are implicit
 227           -- instead of explicit.
 228
 229         tcg_th_used :: TcRef Bool,
 230           -- ^ @True@ <=> Template Haskell syntax used.
 231           --
 232           -- We need this so that we can generate a dependency on the Template
 233           -- Haskell package, becuase the desugarer is going to emit loads of
 234           -- references to TH symbols.  It's rather like tcg_inst_uses; the
 235           -- reference is implicit rather than explicit, so we have to zap a
 236           -- mutable variable.
 237
 238         tcg_dfun_n  :: TcRef OccSet,
 239           -- ^ Allows us to choose unique DFun names.
 240
 241         -- The next fields accumulate the payload of the module
 242         -- The binds, rules and foreign-decl fiels are collected
 243         -- initially in un-zonked form and are finally zonked in tcRnSrcDecls
 244
 245         tcg_rn_exports :: Maybe [Located (IE Name)],
 246         tcg_rn_imports :: [LImportDecl Name],
 247                 -- Keep the renamed imports regardless.  They are not
 248                 -- voluminous and are needed if you want to report unused imports
 249
 250         tcg_used_rdrnames :: TcRef (Set RdrName),
 251                 -- The set of used *imported* (not locally-defined) RdrNames
 252                 -- Used only to report unused import declarations
 253
 254         tcg_rn_decls :: Maybe (HsGroup Name),
 255           -- ^ Renamed decls, maybe.  @Nothing@ <=> Don't retain renamed
 256           -- decls.
 257
 258         tcg_ev_binds  :: Bag EvBind,        -- Top-level evidence bindings
 259         tcg_binds     :: LHsBinds Id,       -- Value bindings in this module
 260         tcg_sigs      :: NameSet,           -- ...Top-level names that *lack* a signature
 261         tcg_imp_specs :: [LTcSpecPrag],     -- ...SPECIALISE prags for imported Ids
 262         tcg_warns     :: Warnings,          -- ...Warnings and deprecations
 263         tcg_anns      :: [Annotation],      -- ...Annotations
 264         tcg_insts     :: [Instance],        -- ...Instances
 265         tcg_fam_insts :: [FamInst],         -- ...Family instances
 266         tcg_rules     :: [LRuleDecl Id],    -- ...Rules
 267         tcg_fords     :: [LForeignDecl Id], -- ...Foreign import & exports
 268
 269         tcg_doc_hdr   :: Maybe LHsDocString, -- ^ Maybe Haddock header docs
 270         tcg_hpc       :: AnyHpcUsage,        -- ^ @True@ if any part of the
 271                                              --  prog uses hpc instrumentation.
 272
 273         tcg_main      :: Maybe Name          -- ^ The Name of the main
 274                                              -- function, if this module is
 275                                              -- the main module.
 276     }
 277
 278 data RecFieldEnv
 279   = RecFields (NameEnv [Name])  -- Maps a constructor name *in this module*
 280                                 -- to the fields for that constructor
 281               NameSet           -- Set of all fields declared *in this module*;
 282                                 -- used to suppress name-shadowing complaints
 283                                 -- when using record wild cards
 284                                 -- E.g.  let fld = e in C {..}
 285         -- This is used when dealing with ".." notation in record
 286         -- construction and pattern matching.
 287         -- The FieldEnv deals *only* with constructors defined in *this*
 288         -- module.  For imported modules, we get the same info from the
 289         -- TypeEnv
 290 \end{code}
 291
 292 %************************************************************************
 293 %*                                                                      *
 294                 The interface environments
 295               Used when dealing with IfaceDecls
 296 %*                                                                      *
 297 %************************************************************************
 298
 299 \begin{code}
 300 data IfGblEnv
 301   = IfGblEnv {
 302         -- The type environment for the module being compiled,
 303         -- in case the interface refers back to it via a reference that
 304         -- was originally a hi-boot file.
 305         -- We need the module name so we can test when it's appropriate
 306         -- to look in this env.
 307         if_rec_types :: Maybe (Module, IfG TypeEnv)
 308                 -- Allows a read effect, so it can be in a mutable
 309                 -- variable; c.f. handling the external package type env
 310                 -- Nothing => interactive stuff, no loops possible
 311     }
 312
 313 data IfLclEnv
 314   = IfLclEnv {
 315         -- The module for the current IfaceDecl
 316         -- So if we see   f = \x -> x
 317         -- it means M.f = \x -> x, where M is the if_mod
 318         if_mod :: Module,
 319
 320         -- The field is used only for error reporting
 321         -- if (say) there's a Lint error in it
 322         if_loc :: SDoc,
 323                 -- Where the interface came from:
 324                 --      .hi file, or GHCi state, or ext core
 325                 -- plus which bit is currently being examined
 326
 327         if_tv_env  :: UniqFM TyVar,     -- Nested tyvar bindings
 328         if_id_env  :: UniqFM Id         -- Nested id binding
 329     }
 330 \end{code}
 331
 332
 333 %************************************************************************
 334 %*                                                                      *
 335                 The local typechecker environment
 336 %*                                                                      *
 337 %************************************************************************
 338
 339 The Global-Env/Local-Env story
 340 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 341 During type checking, we keep in the tcg_type_env
 342         * All types and classes
 343         * All Ids derived from types and classes (constructors, selectors)
 344
 345 At the end of type checking, we zonk the local bindings,
 346 and as we do so we add to the tcg_type_env
 347         * Locally defined top-level Ids
 348
 349 Why?  Because they are now Ids not TcIds.  This final GlobalEnv is
 350         a) fed back (via the knot) to typechecking the
 351            unfoldings of interface signatures
 352         b) used in the ModDetails of this module
 353
 354 \begin{code}
 355 data TcLclEnv           -- Changes as we move inside an expression
 356                         -- Discarded after typecheck/rename; not passed on to desugarer
 357   = TcLclEnv {
 358         tcl_loc  :: SrcSpan,            -- Source span
 359         tcl_ctxt :: [ErrCtxt],          -- Error context, innermost on top
 360         tcl_errs :: TcRef Messages,     -- Place to accumulate errors
 361
 362         tcl_th_ctxt    :: ThStage,            -- Template Haskell context
 363         tcl_arrow_ctxt :: ArrowCtxt,          -- Arrow-notation context
 364
 365         tcl_rdr :: LocalRdrEnv,         -- Local name envt
 366                 -- Maintained during renaming, of course, but also during
 367                 -- type checking, solely so that when renaming a Template-Haskell
 368                 -- splice we have the right environment for the renamer.
 369                 --
 370                 --   Does *not* include global name envt; may shadow it
 371                 --   Includes both ordinary variables and type variables;
 372                 --   they are kept distinct because tyvar have a different
 373                 --   occurrence contructor (Name.TvOcc)
 374                 -- We still need the unsullied global name env so that
 375                 --   we can look up record field names
 376
 377         tcl_env  :: TcTypeEnv,    -- The local type environment: Ids and
 378                                   -- TyVars defined in this module
 379
 380         tcl_tyvars :: TcRef TcTyVarSet, -- The "global tyvars"
 381                         -- Namely, the in-scope TyVars bound in tcl_env,
 382                         -- plus the tyvars mentioned in the types of Ids bound
 383                         -- in tcl_lenv.
 384                         -- Why mutable? see notes with tcGetGlobalTyVars
 385
 386         tcl_lie   :: TcRef WantedConstraints,    -- Place to accumulate type constraints
 387
 388         -- TcMetaTyVars have
 389         tcl_meta  :: TcRef Unique,  -- The next free unique for TcMetaTyVars
 390                                     -- Guaranteed to be allocated linearly
 391         tcl_untch :: Unique         -- Any TcMetaTyVar with
 392                                     --     unique >= tcl_untch is touchable
 393                                     --     unique <  tcl_untch is untouchable
 394     }
 395
 396 type TcTypeEnv = NameEnv TcTyThing
 397
 398
 399 {- Note [Given Insts]
 400    ~~~~~~~~~~~~~~~~~~
 401 Because of GADTs, we have to pass inwards the Insts provided by type signatures
 402 and existential contexts. Consider
 403         data T a where { T1 :: b -> b -> T [b] }
 404         f :: Eq a => T a -> Bool
 405         f (T1 x y) = [x]==[y]
 406
 407 The constructor T1 binds an existential variable 'b', and we need Eq [b].
 408 Well, we have it, because Eq a refines to Eq [b], but we can only spot that if we
 409 pass it inwards.
 410
 411 -}
 412
 413 ---------------------------
 414 -- Template Haskell stages and levels
 415 ---------------------------
 416
 417 data ThStage    -- See Note [Template Haskell state diagram] in TcSplice
 418   = Splice      -- Top-level splicing
 419                 -- This code will be run *at compile time*;
 420                 --   the result replaces the splice
 421                 -- Binding level = 0
 422
 423   | Comp        -- Ordinary Haskell code
 424                 -- Binding level = 1
 425
 426   | Brack                       -- Inside brackets
 427       ThStage                   --   Binding level = level(stage) + 1
 428       (TcRef [PendingSplice])   --   Accumulate pending splices here
 429       (TcRef WantedConstraints) --     and type constraints here
 430
 431 topStage, topAnnStage, topSpliceStage :: ThStage
 432 topStage       = Comp
 433 topAnnStage    = Splice
 434 topSpliceStage = Splice
 435
 436 instance Outputable ThStage where
 437    ppr Splice        = text "Splice"
 438    ppr Comp          = text "Comp"
 439    ppr (Brack s _ _) = text "Brack" <> parens (ppr s)
 440
 441 type ThLevel = Int
 442         -- See Note [Template Haskell levels] in TcSplice
 443         -- Incremented when going inside a bracket,
 444         -- decremented when going inside a splice
 445         -- NB: ThLevel is one greater than the 'n' in Fig 2 of the
 446         --     original "Template meta-programming for Haskell" paper
 447
 448 impLevel, outerLevel :: ThLevel
 449 impLevel = 0    -- Imported things; they can be used inside a top level splice
 450 outerLevel = 1  -- Things defined outside brackets
 451 -- NB: Things at level 0 are not *necessarily* imported.
 452 --      eg  $( \b -> ... )   here b is bound at level 0
 453 --
 454 -- For example:
 455 --      f = ...
 456 --      g1 = $(map ...)         is OK
 457 --      g2 = $(f ...)           is not OK; because we havn't compiled f yet
 458
 459 thLevel :: ThStage -> ThLevel
 460 thLevel Splice        = 0
 461 thLevel Comp          = 1
 462 thLevel (Brack s _ _) = thLevel s + 1
 463
 464 ---------------------------
 465 -- Arrow-notation context
 466 ---------------------------
 467
 468 {-
 469 In arrow notation, a variable bound by a proc (or enclosed let/kappa)
 470 is not in scope to the left of an arrow tail (-<) or the head of (|..|).
 471 For example
 472
 473         proc x -> (e1 -< e2)
 474
 475 Here, x is not in scope in e1, but it is in scope in e2.  This can get
 476 a bit complicated:
 477
 478         let x = 3 in
 479         proc y -> (proc z -> e1) -< e2
 480
 481 Here, x and z are in scope in e1, but y is not.  We implement this by
 482 recording the environment when passing a proc (using newArrowScope),
 483 and returning to that (using escapeArrowScope) on the left of -< and the
 484 head of (|..|).
 485 -}
 486
 487 data ArrowCtxt
 488   = NoArrowCtxt
 489   | ArrowCtxt (Env TcGblEnv TcLclEnv)
 490
 491 -- Record the current environment (outside a proc)
 492 newArrowScope :: TcM a -> TcM a
 493 newArrowScope
 494   = updEnv $ \env ->
 495         env { env_lcl = (env_lcl env) { tcl_arrow_ctxt = ArrowCtxt env } }
 496
 497 -- Return to the stored environment (from the enclosing proc)
 498 escapeArrowScope :: TcM a -> TcM a
 499 escapeArrowScope
 500   = updEnv $ \ env -> case tcl_arrow_ctxt (env_lcl env) of
 501         NoArrowCtxt -> env
 502         ArrowCtxt env' -> env'
 503
 504 ---------------------------
 505 -- TcTyThing
 506 ---------------------------
 507
 508 data TcTyThing
 509   = AGlobal TyThing             -- Used only in the return type of a lookup
 510
 511   | ATcId   {           -- Ids defined in this module; may not be fully zonked
 512         tct_id    :: TcId,
 513         tct_level :: ThLevel }
 514
 515   | ATyVar  Name TcType         -- The type to which the lexically scoped type vaiable
 516                                 -- is currently refined. We only need the Name
 517                                 -- for error-message purposes; it is the corresponding
 518                                 -- Name in the domain of the envt
 519
 520   | AThing  TcKind              -- Used temporarily, during kind checking, for the
 521                                 --      tycons and clases in this recursive group
 522
 523 instance Outputable TcTyThing where     -- Debugging only
 524    ppr (AGlobal g)      = pprTyThing g
 525    ppr elt@(ATcId {})   = text "Identifier" <>
 526                           brackets (ppr (tct_id elt) <> dcolon
 527                                  <> ppr (varType (tct_id elt)) <> comma
 528                                  <+> ppr (tct_level elt))
 529    ppr (ATyVar tv _)    = text "Type variable" <+> quotes (ppr tv)
 530    ppr (AThing k)       = text "AThing" <+> ppr k
 531
 532 pprTcTyThingCategory :: TcTyThing -> SDoc
 533 pprTcTyThingCategory (AGlobal thing) = pprTyThingCategory thing
 534 pprTcTyThingCategory (ATyVar {})     = ptext (sLit "Type variable")
 535 pprTcTyThingCategory (ATcId {})      = ptext (sLit "Local identifier")
 536 pprTcTyThingCategory (AThing {})     = ptext (sLit "Kinded thing")
 537 \end{code}
 538
 539 \begin{code}
 540 type ErrCtxt = (Bool, TidyEnv -> TcM (TidyEnv, Message))
 541         -- Monadic so that we have a chance
 542         -- to deal with bound type variables just before error
 543         -- message construction
 544
 545         -- Bool:  True <=> this is a landmark context; do not
 546         --                 discard it when trimming for display
 547 \end{code}
 548
 549
 550 %************************************************************************
 551 %*                                                                      *
 552         Operations over ImportAvails
 553 %*                                                                      *
 554 %************************************************************************
 555
 556 \begin{code}
 557 -- | 'ImportAvails' summarises what was imported from where, irrespective of
 558 -- whether the imported things are actually used or not.  It is used:
 559 --
 560 --  * when processing the export list,
 561 --
 562 --  * when constructing usage info for the interface file,
 563 --
 564 --  * to identify the list of directly imported modules for initialisation
 565 --    purposes and for optimised overlap checking of family instances,
 566 --
 567 --  * when figuring out what things are really unused
 568 --
 569 data ImportAvails
 570    = ImportAvails {
 571         imp_mods :: ModuleEnv [(ModuleName, Bool, SrcSpan)],
 572           -- ^ Domain is all directly-imported modules
 573           -- The 'ModuleName' is what the module was imported as, e.g. in
 574           -- @
 575           --     import Foo as Bar
 576           -- @
 577           -- it is @Bar@.
 578           --
 579           -- The 'Bool' means:
 580           --
 581           --  - @True@ => import was @import Foo ()@
 582           --
 583           --  - @False@ => import was some other form
 584           --
 585           -- Used
 586           --
 587           --   (a) to help construct the usage information in the interface
 588           --       file; if we import somethign we need to recompile if the
 589           --       export version changes
 590           --
 591           --   (b) to specify what child modules to initialise
 592           --
 593           -- We need a full ModuleEnv rather than a ModuleNameEnv here,
 594           -- because we might be importing modules of the same name from
 595           -- different packages. (currently not the case, but might be in the
 596           -- future).
 597
 598         imp_dep_mods :: ModuleNameEnv (ModuleName, IsBootInterface),
 599           -- ^ Home-package modules needed by the module being compiled
 600           --
 601           -- It doesn't matter whether any of these dependencies
 602           -- are actually /used/ when compiling the module; they
 603           -- are listed if they are below it at all.  For
 604           -- example, suppose M imports A which imports X.  Then
 605           -- compiling M might not need to consult X.hi, but X
 606           -- is still listed in M's dependencies.
 607
 608         imp_dep_pkgs :: [PackageId],
 609           -- ^ Packages needed by the module being compiled, whether directly,
 610           -- or via other modules in this package, or via modules imported
 611           -- from other packages.
 612
 613         imp_orphs :: [Module],
 614           -- ^ Orphan modules below us in the import tree (and maybe including
 615           -- us for imported modules)
 616
 617         imp_finsts :: [Module]
 618           -- ^ Family instance modules below us in the import tree (and maybe
 619           -- including us for imported modules)
 620       }
 621
 622 mkModDeps :: [(ModuleName, IsBootInterface)]
 623           -> ModuleNameEnv (ModuleName, IsBootInterface)
 624 mkModDeps deps = foldl add emptyUFM deps
 625                where
 626                  add env elt@(m,_) = addToUFM env m elt
 627
 628 emptyImportAvails :: ImportAvails
 629 emptyImportAvails = ImportAvails { imp_mods     = emptyModuleEnv,
 630                                    imp_dep_mods = emptyUFM,
 631                                    imp_dep_pkgs = [],
 632                                    imp_orphs    = [],
 633                                    imp_finsts   = [] }
 634
 635 plusImportAvails ::  ImportAvails ->  ImportAvails ->  ImportAvails
 636 plusImportAvails
 637   (ImportAvails { imp_mods = mods1,
 638                   imp_dep_mods = dmods1, imp_dep_pkgs = dpkgs1,
 639                   imp_orphs = orphs1, imp_finsts = finsts1 })
 640   (ImportAvails { imp_mods = mods2,
 641                   imp_dep_mods = dmods2, imp_dep_pkgs = dpkgs2,
 642                   imp_orphs = orphs2, imp_finsts = finsts2 })
 643   = ImportAvails { imp_mods     = plusModuleEnv_C (++) mods1 mods2,
 644                    imp_dep_mods = plusUFM_C plus_mod_dep dmods1 dmods2,
 645                    imp_dep_pkgs = dpkgs1 `unionLists` dpkgs2,
 646                    imp_orphs    = orphs1 `unionLists` orphs2,
 647                    imp_finsts   = finsts1 `unionLists` finsts2 }
 648   where
 649     plus_mod_dep (m1, boot1) (m2, boot2)
 650         = WARN( not (m1 == m2), (ppr m1 <+> ppr m2) $$ (ppr boot1 <+> ppr boot2) )
 651                 -- Check mod-names match
 652           (m1, boot1 && boot2)  -- If either side can "see" a non-hi-boot interface, use that
 653 \end{code}
 654
 655 %************************************************************************
 656 %*                                                                      *
 657 \subsection{Where from}
 658 %*                                                                      *
 659 %************************************************************************
 660
 661 The @WhereFrom@ type controls where the renamer looks for an interface file
 662
 663 \begin{code}
 664 data WhereFrom
 665   = ImportByUser IsBootInterface        -- Ordinary user import (perhaps {-# SOURCE #-})
 666   | ImportBySystem                      -- Non user import.
 667
 668 instance Outputable WhereFrom where
 669   ppr (ImportByUser is_boot) | is_boot     = ptext (sLit "{- SOURCE -}")
 670                              | otherwise   = empty
 671   ppr ImportBySystem                       = ptext (sLit "{- SYSTEM -}")
 672 \end{code}
 673
 674
 675 %************************************************************************
 676 %*                                                                      *
 677                 Wanted constraints
 678
 679      These are forced to be in TcRnTypes because
 680            TcLclEnv mentions WantedConstraints
 681            WantedConstraint mentions CtLoc
 682            CtLoc mentions ErrCtxt
 683            ErrCtxt mentions TcM
 684 %*                                                                      *
 685 v%************************************************************************
 686
 687 \begin{code}
 688 data Untouchables = NoUntouchables
 689                   | TouchableRange
 690                           Unique  -- Low end
 691                           Unique  -- High end
 692  -- A TcMetaTyvar is *touchable* iff its unique u satisfies
 693  --   u >= low
 694  --   u < high
 695
 696 instance Outputable Untouchables where
 697   ppr NoUntouchables = ptext (sLit "No untouchables")
 698   ppr (TouchableRange low high) = ptext (sLit "Touchable range:") <+>
 699                                   ppr low <+> char '-' <+> ppr high
 700
 701 inTouchableRange :: Untouchables -> TcTyVar -> Bool
 702 inTouchableRange NoUntouchables _ = True
 703 inTouchableRange (TouchableRange low high) tv
 704   = uniq >= low && uniq < high
 705   where
 706     uniq = varUnique tv
 707
 708 type WantedConstraints = Bag WantedConstraint
 709
 710 data WantedConstraint
 711   = WcEvVar  WantedEvVar
 712   | WcImplic Implication
 713   -- ToDo: add literals, methods
 714
 715 -- EvVar defined in module Var.lhs:
 716 -- Evidence variables include all *quantifiable* constraints
 717 --   dictionaries
 718 --   implicit parameters
 719 --   coercion variables
 720
 721 data WantedEvVar   -- The sort of constraint over which one can lambda-abstract
 722    = WantedEvVar
 723          EvVar       -- The variable itself; make a binding for it please
 724          WantedLoc   -- How the constraint arose in the first place
 725                      -- (used for error messages only)
 726
 727 type WantedLoc = CtLoc CtOrigin
 728 type GivenLoc  = CtLoc SkolemInfo
 729
 730 data Implication
 731   = Implic {
 732       ic_untch :: Untouchables, -- Untouchables: unification variables
 733                                   -- free in the environment
 734       ic_env   :: TcTypeEnv,    -- The type environment
 735                                   -- Used only when generating error messages
 736           -- Generally, ic_untch is a superset of tvsof(ic_env)
 737           -- However, we don't zonk ic_env when zonking the Implication
 738           -- Instead we do that when generating a skolem-escape error message
 739
 740       ic_skols  :: TcTyVarSet,   -- Introduced skolems
 741                                  -- See Note [Skolems in an implication]
 742
 743       ic_scoped :: [TcTyVar],    -- List of scoped variables to be unified
 744                                  -- bijectively to a subset of ic_tyvars
 745                                  -- Note [Scoped pattern variable]
 746
 747       ic_given  :: [EvVar],      -- Given evidence variables
 748                                  --   (order does not matter)
 749
 750       ic_wanted :: WantedConstraints,    -- Wanted constraints
 751
 752       ic_binds  :: EvBindsVar,   -- Points to the place to fill in the
 753                                  -- abstraction and bindings
 754
 755       ic_loc   :: GivenLoc }
 756
 757 evVarsToWanteds :: WantedLoc -> [EvVar] -> WantedConstraints
 758 evVarsToWanteds loc evs = listToBag [WcEvVar (WantedEvVar ev loc) | ev <- evs]
 759
 760 wantedEvVarLoc :: WantedEvVar -> WantedLoc
 761 wantedEvVarLoc (WantedEvVar _ loc) = loc
 762
 763 wantedEvVarToVar :: WantedEvVar -> EvVar
 764 wantedEvVarToVar (WantedEvVar ev _) = ev
 765
 766 wantedEvVarPred :: WantedEvVar -> PredType
 767 wantedEvVarPred (WantedEvVar ev _)  = evVarPred ev
 768
 769 splitWanteds :: WantedConstraints -> (Bag WantedEvVar, Bag Implication)
 770 splitWanteds wanted = partitionBagWith pick wanted
 771   where
 772     pick (WcEvVar v)  = Left v
 773     pick (WcImplic i) = Right i
 774 \end{code}
 775
 776 Note [Skolems in an implication]
 777 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 778 The skolems in an implication are not there to perform a skolem escape
 779 check.  That happens because all the environment variables are in the
 780 untouchables, and therefore cannot be unified with anything at all,
 781 let alone the skolems.
 782
 783 Instead, ic_skols is used only when considering floating a constraint
 784 outside the implication in TcSimplify.floatEqualities or
 785 TcSimplify.approximateImplications
 786
 787 Note [Scoped pattern variables]
 788 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 789    data T where K :: forall a,b. a -> b -> T
 790
 791    ...(case x of K (p::c) (q::d) -> ...)...
 792
 793 We create fresh MetaTvs for c,d, and later check that they are
 794 bound bijectively to the skolems we created for a,b.  So the
 795 implication constraint looks like
 796             ic_skols  = {a',b'}  -- Skolem tvs created from a,b
 797             ic_scoped = {c',d'}  -- Meta tvs created from c,d
 798
 799 \begin{code}
 800 emptyWanteds :: WantedConstraints
 801 emptyWanteds = emptyBag
 802
 803 andWanteds :: WantedConstraints -> WantedConstraints -> WantedConstraints
 804 andWanteds = unionBags
 805
 806 extendWanteds :: WantedConstraints -> WantedConstraint -> WantedConstraints
 807 extendWanteds = snocBag
 808 \end{code}
 809
 810 \begin{code}
 811 pprEvVars :: [EvVar] -> SDoc    -- Print with their types
 812 pprEvVars ev_vars = vcat (map pprEvVarWithType ev_vars)
 813
 814 pprEvVarTheta :: [EvVar] -> SDoc
 815 pprEvVarTheta ev_vars = pprTheta (map evVarPred ev_vars)
 816
 817 pprEvVarWithType :: EvVar -> SDoc
 818 pprEvVarWithType v = ppr v <+> dcolon <+> pprPred (evVarPred v)
 819
 820 pprWantedsWithLocs :: Bag WantedConstraint -> SDoc
 821 pprWantedsWithLocs = foldrBag (($$) . pprWantedWithLoc) empty
 822
 823 pprWantedWithLoc :: WantedConstraint -> SDoc
 824 pprWantedWithLoc (WcImplic i) = ppr i
 825 pprWantedWithLoc (WcEvVar v)  = pprWantedEvVarWithLoc v
 826
 827 instance Outputable WantedConstraint where
 828   ppr (WcEvVar v)  = ppr v
 829   ppr (WcImplic i) = ppr i
 830
 831 -- Adding -ferror-spans makes the output more voluminous
 832 instance Outputable WantedEvVar where
 833   ppr wev | opt_ErrorSpans = pprWantedEvVarWithLoc wev
 834           | otherwise      = pprWantedEvVar wev
 835
 836 pprWantedEvVarWithLoc, pprWantedEvVar :: WantedEvVar -> SDoc
 837 pprWantedEvVarWithLoc (WantedEvVar v loc) = hang (pprEvVarWithType v)
 838                                                2 (pprArisingAt loc)
 839 pprWantedEvVar        (WantedEvVar v _)   = pprEvVarWithType v
 840
 841 instance Outputable Implication where
 842   ppr (Implic { ic_untch = untch, ic_skols = skols, ic_given = given
 843               , ic_wanted = wanted, ic_binds = binds, ic_loc = loc })
 844    = ptext (sLit "Implic") <+> braces
 845      (sep [ ptext (sLit "Untouchables = ") <+> ppr untch
 846           , ptext (sLit "Skolems = ") <+> ppr skols
 847           , ptext (sLit "Given = ") <+> pprEvVars given
 848           , ptext (sLit "Wanted = ") <+> ppr wanted
 849           , ptext (sLit "Binds = ") <+> ppr binds
 850           , pprSkolInfo (ctLocOrigin loc)
 851           , ppr (ctLocSpan loc) ])
 852 \end{code}
 853
 854 %************************************************************************
 855 %*                                                                      *
 856             CtLoc, CtOrigin
 857 %*                                                                      *
 858 %************************************************************************
 859
 860 The 'CtLoc' and 'CtOrigin' types gives information about where a
 861 *wanted constraint* came from.  This is important for decent error
 862 message reporting because dictionaries don't appear in the original
 863 source code.  Doubtless this type will evolve...
 864
 865 \begin{code}
 866 -------------------------------------------
 867 data CtLoc orig = CtLoc orig SrcSpan [ErrCtxt]
 868
 869 ctLocSpan :: CtLoc o -> SrcSpan
 870 ctLocSpan (CtLoc _ s _) = s
 871
 872 ctLocOrigin :: CtLoc o -> o
 873 ctLocOrigin (CtLoc o _ _) = o
 874
 875 setCtLocOrigin :: CtLoc o -> o' -> CtLoc o'
 876 setCtLocOrigin (CtLoc _ s c) o = CtLoc o s c
 877
 878 pprArising :: CtOrigin -> SDoc
 879 pprArising (TypeEqOrigin {}) = empty
 880 pprArising orig              = text "arising from" <+> ppr orig
 881
 882 pprArisingAt :: CtLoc CtOrigin -> SDoc
 883 pprArisingAt (CtLoc o s _) = sep [pprArising o, text "at" <+> ppr s]
 884
 885 -------------------------------------------
 886 -- CtOrigin gives the origin of *wanted* constraints
 887 data CtOrigin
 888   = OccurrenceOf Name           -- Occurrence of an overloaded identifier
 889   | AppOrigin                   -- An application of some kind
 890
 891   | SpecPragOrigin Name         -- Specialisation pragma for identifier
 892
 893   | TypeEqOrigin EqOrigin
 894
 895   | IPOccOrigin  (IPName Name)  -- Occurrence of an implicit parameter
 896
 897   | LiteralOrigin (HsOverLit Name)      -- Occurrence of a literal
 898   | NegateOrigin                        -- Occurrence of syntactic negation
 899
 900   | ArithSeqOrigin (ArithSeqInfo Name) -- [x..], [x..y] etc
 901   | PArrSeqOrigin  (ArithSeqInfo Name) -- [:x..y:] and [:x,y..z:]
 902   | SectionOrigin
 903   | TupleOrigin                        -- (..,..)
 904   | ExprSigOrigin       -- e :: ty
 905   | PatSigOrigin        -- p :: ty
 906   | PatOrigin           -- Instantiating a polytyped pattern at a constructor
 907   | RecordUpdOrigin
 908   | ViewPatOrigin
 909
 910   | ScOrigin            -- Typechecking superclasses of an instance declaration
 911   | DerivOrigin         -- Typechecking deriving
 912   | StandAloneDerivOrigin -- Typechecking stand-alone deriving
 913   | DefaultOrigin       -- Typechecking a default decl
 914   | DoOrigin            -- Arising from a do expression
 915   | ProcOrigin          -- Arising from a proc expression
 916   | AnnOrigin           -- An annotation
 917
 918 data EqOrigin
 919   = UnifyOrigin
 920        { uo_actual   :: TcType
 921        , uo_expected :: TcType }
 922
 923 instance Outputable CtOrigin where
 924   ppr orig = pprO orig
 925
 926 pprO :: CtOrigin -> SDoc
 927 pprO (OccurrenceOf name)   = hsep [ptext (sLit "a use of"), quotes (ppr name)]
 928 pprO AppOrigin             = ptext (sLit "an application")
 929 pprO (SpecPragOrigin name) = hsep [ptext (sLit "a specialisation pragma for"), quotes (ppr name)]
 930 pprO (IPOccOrigin name)    = hsep [ptext (sLit "a use of implicit parameter"), quotes (ppr name)]
 931 pprO RecordUpdOrigin       = ptext (sLit "a record update")
 932 pprO ExprSigOrigin         = ptext (sLit "an expression type signature")
 933 pprO PatSigOrigin          = ptext (sLit "a pattern type signature")
 934 pprO PatOrigin             = ptext (sLit "a pattern")
 935 pprO ViewPatOrigin         = ptext (sLit "a view pattern")
 936 pprO (LiteralOrigin lit)   = hsep [ptext (sLit "the literal"), quotes (ppr lit)]
 937 pprO (ArithSeqOrigin seq)  = hsep [ptext (sLit "the arithmetic sequence"), quotes (ppr seq)]
 938 pprO (PArrSeqOrigin seq)   = hsep [ptext (sLit "the parallel array sequence"), quotes (ppr seq)]
 939 pprO SectionOrigin         = ptext (sLit "an operator section")
 940 pprO TupleOrigin           = ptext (sLit "a tuple")
 941 pprO NegateOrigin          = ptext (sLit "a use of syntactic negation")
 942 pprO ScOrigin              = ptext (sLit "the superclasses of an instance declaration")
 943 pprO DerivOrigin           = ptext (sLit "the 'deriving' clause of a data type declaration")
 944 pprO StandAloneDerivOrigin = ptext (sLit "a 'deriving' declaration")
 945 pprO DefaultOrigin         = ptext (sLit "a 'default' declaration")
 946 pprO DoOrigin              = ptext (sLit "a do statement")
 947 pprO ProcOrigin            = ptext (sLit "a proc expression")
 948 pprO (TypeEqOrigin eq)     = ptext (sLit "an equality") <+> ppr eq
 949 pprO AnnOrigin             = ptext (sLit "an annotation")
 950
 951 instance Outputable EqOrigin where
 952   ppr (UnifyOrigin t1 t2) = ppr t1 <+> char '~' <+> ppr t2
 953 \end{code}