TcRnTypes.hs 93.5 KB
Newer Older
Austin Seipp's avatar
Austin Seipp committed
1 2 3
{-
(c) The University of Glasgow 2006-2012
(c) The GRASP Project, Glasgow University, 1992-2002
4

5 6 7 8 9 10 11 12 13 14 15 16

Various types used during typechecking, please see TcRnMonad as well for
operations on these types. You probably want to import it, instead of this
module.

All the monads exported here are built on top of the same IOEnv monad. The
monad functions like a Reader monad in the way it passes the environment
around. This is done to allow the environment to be manipulated in a stack
like fashion when entering expressions... ect.

For state that is global and should be returned at the end (e.g not part
of the stack mechanism), you should use an TcRef (= IORef) to store them.
Austin Seipp's avatar
Austin Seipp committed
17
-}
18

19
{-# LANGUAGE CPP, ExistentialQuantification, GeneralizedNewtypeDeriving #-}
20

21
module TcRnTypes(
22 23
        TcRnIf, TcRn, TcM, RnM, IfM, IfL, IfG, -- The monad is opaque outside this module
        TcRef,
24

25 26 27 28
        -- The environment types
        Env(..),
        TcGblEnv(..), TcLclEnv(..),
        IfGblEnv(..), IfLclEnv(..),
29
        tcVisibleOrphanMods,
30

31
        -- Renamer types
32 33 34
        ErrCtxt, RecFieldEnv(..),
        ImportAvails(..), emptyImportAvails, plusImportAvails,
        WhereFrom(..), mkModDeps,
35

36
        -- Typechecker types
37 38
        TcTypeEnv, TcIdBinderStack, TcIdBinder(..),
        TcTyThing(..), PromotionErr(..),
39
        pprTcTyThingCategory, pprPECategory,
40

41 42 43 44
        -- Desugaring types
        DsM, DsLclEnv(..), DsGblEnv(..), PArrBuiltin(..),
        DsMetaEnv, DsMetaVal(..),

45
        -- Template Haskell
46
        ThStage(..), PendingStuff(..), topStage, topAnnStage, topSpliceStage,
47
        ThLevel, impLevel, outerLevel, thLevel,
48

49
        -- Arrows
50
        ArrowCtxt(..),
ross's avatar
ross committed
51

52
        -- Canonical constraints
53 54
        Xi, Ct(..), Cts, emptyCts, andCts, andManyCts, pprCts,
        singleCt, listToCts, ctsElts, consCts, snocCts, extendCtsList,
55
        isEmptyCts, isCTyEqCan, isCFunEqCan,
Simon Peyton Jones's avatar
Simon Peyton Jones committed
56
        isCDictCan_Maybe, isCFunEqCan_maybe,
57
        isCIrredEvCan, isCNonCanonical, isWantedCt, isDerivedCt,
58
        isGivenCt, isHoleCt, isOutOfScopeCt, isExprHoleCt, isTypeHoleCt,
59
        ctEvidence, ctLoc, setCtLoc, ctPred, ctFlavour, ctEqRel, ctOrigin,
60
        mkNonCanonical, mkNonCanonicalCt,
61
        ctEvPred, ctEvLoc, ctEvOrigin, ctEvEqRel,
62
        ctEvTerm, ctEvCoercion, ctEvId,
63

64
        WantedConstraints(..), insolubleWC, emptyWC, isEmptyWC,
65
        andWC, unionsWC, addSimples, addImplics, mkSimpleWC, addInsols,
66
        dropDerivedWC, dropDerivedSimples, dropDerivedInsols,
67
        isDroppableDerivedLoc, insolubleImplic, trulyInsoluble,
68

69
        Implication(..), ImplicStatus(..), isInsolubleStatus,
70 71
        SubGoalDepth, initialSubGoalDepth,
        bumpSubGoalDepth, subGoalDepthExceeded,
72
        CtLoc(..), ctLocSpan, ctLocEnv, ctLocLevel, ctLocOrigin,
73
        ctLocDepth, bumpCtLocDepth,
thomasw's avatar
thomasw committed
74
        setCtLocOrigin, setCtLocEnv, setCtLocSpan,
75
        CtOrigin(..), pprCtOrigin, pprCtLoc,
76
        pushErrCtxt, pushErrCtxtSameOrigin,
77

78
        SkolemInfo(..),
79

80
        CtEvidence(..),
81
        mkGivenLoc,
82
        isWanted, isGiven, isDerived,
eir@cis.upenn.edu's avatar
eir@cis.upenn.edu committed
83
        ctEvRole,
84

Adam Gundry's avatar
Adam Gundry committed
85 86 87
        -- Constraint solver plugins
        TcPlugin(..), TcPluginResult(..), TcPluginSolver,
        TcPluginM, runTcPluginM, unsafeTcPluginTcM,
88
        getEvBindsTcPluginM_maybe,
Adam Gundry's avatar
Adam Gundry committed
89

eir@cis.upenn.edu's avatar
eir@cis.upenn.edu committed
90
        CtFlavour(..), ctEvFlavour,
91 92
        CtFlavourRole, ctEvFlavourRole, ctFlavourRole,
        eqCanRewrite, eqCanRewriteFR, canDischarge, canDischargeF,
eir@cis.upenn.edu's avatar
eir@cis.upenn.edu committed
93

94
        -- Pretty printing
Austin Seipp's avatar
Austin Seipp committed
95
        pprEvVarTheta,
96
        pprEvVars, pprEvVarWithType,
97

98
        -- Misc other types
99
        TcId, TcIdSet, HoleSort(..)
100

101 102 103 104
  ) where

#include "HsVersions.h"

105
import HsSyn
Facundo Domínguez's avatar
Facundo Domínguez committed
106
import CoreSyn
107
import HscTypes
108
import TcEvidence
109
import Type
eir@cis.upenn.edu's avatar
eir@cis.upenn.edu committed
110
import CoAxiom  ( Role )
111
import Class    ( Class )
112
import TyCon    ( TyCon )
Gergő Érdi's avatar
Gergő Érdi committed
113
import ConLike  ( ConLike(..) )
114
import DataCon  ( DataCon, dataConUserType, dataConOrigArgTys )
115
import PatSyn   ( PatSyn, patSynType )
116
import TcType
117
import Annotations
118 119
import InstEnv
import FamInstEnv
120
import IOEnv
121 122
import RdrName
import Name
123
import NameEnv
124
import NameSet
125
import Avail
126 127
import Var
import VarEnv
128
import Module
129 130 131
import SrcLoc
import VarSet
import ErrUtils
132
import UniqFM
133 134
import UniqSupply
import BasicTypes
135
import Bag
Ian Lynagh's avatar
Ian Lynagh committed
136
import DynFlags
137
import Outputable
138
import ListSetOps
139
import FastString
140
import GHC.Fingerprint
141

142
import Data.Set (Set)
Adam Gundry's avatar
Adam Gundry committed
143
import Control.Monad (ap, liftM)
144 145

#ifdef GHCI
146 147 148 149
import Data.Map      ( Map )
import Data.Dynamic  ( Dynamic )
import Data.Typeable ( TypeRep )

150 151
import qualified Language.Haskell.TH as TH
#endif
152

Austin Seipp's avatar
Austin Seipp committed
153 154 155
{-
************************************************************************
*                                                                      *
156
               Standard monad definition for TcRn
157
    All the combinators for the monad can be found in TcRnMonad
Austin Seipp's avatar
Austin Seipp committed
158 159
*                                                                      *
************************************************************************
160

161
The monad itself has to be defined here, because it is mentioned by ErrCtxt
Austin Seipp's avatar
Austin Seipp committed
162
-}
163

Gergő Érdi's avatar
Gergő Érdi committed
164
type TcRnIf a b = IOEnv (Env a b)
165 166 167 168 169 170 171 172 173 174 175 176
type TcRn       = TcRnIf TcGblEnv TcLclEnv    -- Type inference
type IfM lcl    = TcRnIf IfGblEnv lcl         -- Iface stuff
type IfG        = IfM ()                      --    Top level
type IfL        = IfM IfLclEnv                --    Nested
type DsM        = TcRnIf DsGblEnv DsLclEnv    -- Desugaring

-- TcRn is the type-checking and renaming monad: the main monad that
-- most type-checking takes place in.  The global environment is
-- 'TcGblEnv', which tracks all of the top-level type-checking
-- information we've accumulated while checking a module, while the
-- local environment is 'TcLclEnv', which tracks local information as
-- we move inside expressions.
Edward Z. Yang's avatar
Edward Z. Yang committed
177 178 179 180 181 182

-- | Historical "renaming monad" (now it's just 'TcRn').
type RnM  = TcRn

-- | Historical "type-checking monad" (now it's just 'TcRn').
type TcM  = TcRn
183

184 185 186 187
-- We 'stack' these envs through the Reader like monad infastructure
-- as we move into an expression (although the change is focused in
-- the lcl type).
data Env gbl lcl
188
  = Env {
189 190
        env_top  :: HscEnv,  -- Top-level stuff that never changes
                             -- Includes all info about imported things
191

192 193
        env_us   :: {-# UNPACK #-} !(IORef UniqSupply),
                             -- Unique supply for local varibles
194

195 196
        env_gbl  :: gbl,     -- Info about things defined at the top level
                             -- of the module being compiled
197

198
        env_lcl  :: lcl      -- Nested stuff; changes as we go into
199
    }
200

Ian Lynagh's avatar
Ian Lynagh committed
201 202
instance ContainsDynFlags (Env gbl lcl) where
    extractDynFlags env = hsc_dflags (env_top env)
203 204
    replaceDynFlags env dflags
        = env {env_top = replaceDynFlags (env_top env) dflags}
Ian Lynagh's avatar
Ian Lynagh committed
205

206 207 208
instance ContainsModule gbl => ContainsModule (Env gbl lcl) where
    extractModule env = extractModule (env_gbl env)

209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327

{-
************************************************************************
*                                                                      *
                The interface environments
              Used when dealing with IfaceDecls
*                                                                      *
************************************************************************
-}

data IfGblEnv
  = IfGblEnv {
        -- The type environment for the module being compiled,
        -- in case the interface refers back to it via a reference that
        -- was originally a hi-boot file.
        -- We need the module name so we can test when it's appropriate
        -- to look in this env.
        if_rec_types :: Maybe (Module, IfG TypeEnv)
                -- Allows a read effect, so it can be in a mutable
                -- variable; c.f. handling the external package type env
                -- Nothing => interactive stuff, no loops possible
    }

data IfLclEnv
  = IfLclEnv {
        -- The module for the current IfaceDecl
        -- So if we see   f = \x -> x
        -- it means M.f = \x -> x, where M is the if_mod
        if_mod :: Module,

        -- The field is used only for error reporting
        -- if (say) there's a Lint error in it
        if_loc :: SDoc,
                -- Where the interface came from:
                --      .hi file, or GHCi state, or ext core
                -- plus which bit is currently being examined

        if_tv_env  :: UniqFM TyVar,     -- Nested tyvar bindings
                                        -- (and coercions)
        if_id_env  :: UniqFM Id         -- Nested id binding
    }

{-
************************************************************************
*                                                                      *
                Desugarer monad
*                                                                      *
************************************************************************

Now the mondo monad magic (yes, @DsM@ is a silly name)---carry around
a @UniqueSupply@ and some annotations, which
presumably include source-file location information:
-}

-- If '-XParallelArrays' is given, the desugarer populates this table with the corresponding
-- variables found in 'Data.Array.Parallel'.
--
data PArrBuiltin
        = PArrBuiltin
        { lengthPVar         :: Var     -- ^ lengthP
        , replicatePVar      :: Var     -- ^ replicateP
        , singletonPVar      :: Var     -- ^ singletonP
        , mapPVar            :: Var     -- ^ mapP
        , filterPVar         :: Var     -- ^ filterP
        , zipPVar            :: Var     -- ^ zipP
        , crossMapPVar       :: Var     -- ^ crossMapP
        , indexPVar          :: Var     -- ^ (!:)
        , emptyPVar          :: Var     -- ^ emptyP
        , appPVar            :: Var     -- ^ (+:+)
        , enumFromToPVar     :: Var     -- ^ enumFromToP
        , enumFromThenToPVar :: Var     -- ^ enumFromThenToP
        }

data DsGblEnv
        = DsGblEnv
        { ds_mod          :: Module             -- For SCC profiling
        , ds_fam_inst_env :: FamInstEnv         -- Like tcg_fam_inst_env
        , ds_unqual  :: PrintUnqualified
        , ds_msgs    :: IORef Messages          -- Warning messages
        , ds_if_env  :: (IfGblEnv, IfLclEnv)    -- Used for looking up global,
                                                -- possibly-imported things
        , ds_dph_env :: GlobalRdrEnv            -- exported entities of 'Data.Array.Parallel.Prim'
                                                -- iff '-fvectorise' flag was given as well as
                                                -- exported entities of 'Data.Array.Parallel' iff
                                                -- '-XParallelArrays' was given; otherwise, empty
        , ds_parr_bi :: PArrBuiltin             -- desugarar names for '-XParallelArrays'
        , ds_static_binds :: IORef [(Fingerprint, (Id,CoreExpr))]
          -- ^ Bindings resulted from floating static forms
        }

instance ContainsModule DsGblEnv where
    extractModule = ds_mod

data DsLclEnv = DsLclEnv {
        dsl_meta    :: DsMetaEnv,        -- Template Haskell bindings
        dsl_loc     :: SrcSpan           -- to put in pattern-matching error msgs
     }

-- Inside [| |] brackets, the desugarer looks
-- up variables in the DsMetaEnv
type DsMetaEnv = NameEnv DsMetaVal

data DsMetaVal
   = DsBound Id         -- Bound by a pattern inside the [| |].
                        -- Will be dynamically alpha renamed.
                        -- The Id has type THSyntax.Var

   | DsSplice (HsExpr Id) -- These bindings are introduced by
                          -- the PendingSplices on a HsBracketOut


{-
************************************************************************
*                                                                      *
                Global typechecker environment
*                                                                      *
************************************************************************
-}

Edward Z. Yang's avatar
Edward Z. Yang committed
328
-- | 'TcGblEnv' describes the top-level of the module at the
329 330
-- point at which the typechecker is finished work.
-- It is this structure that is handed on to the desugarer
331
-- For state that needs to be updated during the typechecking
Edward Z. Yang's avatar
Edward Z. Yang committed
332
-- phase and returned at end, use a 'TcRef' (= 'IORef').
333 334
data TcGblEnv
  = TcGblEnv {
335 336
        tcg_mod     :: Module,         -- ^ Module being compiled
        tcg_src     :: HscSource,
337
          -- ^ What kind of module (regular Haskell, hs-boot, hsig)
338 339
        tcg_sig_of  :: Maybe Module,
          -- ^ Are we being compiled as a signature of an implementation?
340 341
        tcg_mod_name :: Maybe (Located ModuleName),
          -- ^ @Nothing@: \"module X where\" is omitted
342 343 344
        tcg_impl_rdr_env :: Maybe GlobalRdrEnv,
          -- ^ Environment used only during -sig-of for resolving top level
          -- bindings.  See Note [Signature parameters in TcGblEnv and DynFlags]
345

346 347
        tcg_rdr_env :: GlobalRdrEnv,   -- ^ Top level envt; used during renaming
        tcg_default :: Maybe [Type],
348
          -- ^ Types used for defaulting. @Nothing@ => no @default@ decl
349

350 351
        tcg_fix_env   :: FixityEnv,     -- ^ Just for things in this module
        tcg_field_env :: RecFieldEnv,   -- ^ Just for things in this module
352
                                        -- See Note [The interactive package] in HscTypes
353

354
        tcg_type_env :: TypeEnv,
355
          -- ^ Global type env for the module we are compiling now.  All
356 357 358 359 360
          -- TyCons and Classes (for this module) end up in here right away,
          -- along with their derived constructors, selectors.
          --
          -- (Ids defined in this module start in the local envt, though they
          --  move to the global envt during zonking)
361 362 363
          --
          -- NB: for what "things in this module" means, see
          -- Note [The interactive package] in HscTypes
364 365 366 367 368 369 370 371 372

        tcg_type_env_var :: TcRef TypeEnv,
                -- Used only to initialise the interface-file
                -- typechecker in initIfaceTcRn, so that it can see stuff
                -- bound in this module when dealing with hi-boot recursions
                -- Updated at intervals (e.g. after dealing with types and classes)

        tcg_inst_env     :: InstEnv,
          -- ^ Instance envt for all /home-package/ modules;
373
          -- Includes the dfuns in tcg_insts
374
        tcg_fam_inst_env :: FamInstEnv, -- ^ Ditto for family instances
375
        tcg_ann_env      :: AnnEnv,     -- ^ And for annotations
376 377 378 379 380 381 382

                -- Now a bunch of things about this module that are simply
                -- accumulated, but never consulted until the end.
                -- Nevertheless, it's convenient to accumulate them along
                -- with the rest of the info from this module.
        tcg_exports :: [AvailInfo],     -- ^ What is exported
        tcg_imports :: ImportAvails,
383
          -- ^ Information about what was imported from where, including
384
          -- things bound in this module. Also store Safe Haskell info
385
          -- here about transative trusted packaage requirements.
386

387 388 389
        tcg_dus :: DefUses,   -- ^ What is defined in this module and what is used.
        tcg_used_rdrnames :: TcRef (Set RdrName),
          -- See Note [Tracking unused binding and imports]
390

391
        tcg_keep :: TcRef NameSet,
392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409
          -- ^ Locally-defined top-level names to keep alive.
          --
          -- "Keep alive" means give them an Exported flag, so that the
          -- simplifier does not discard them as dead code, and so that they
          -- are exposed in the interface file (but not to export to the
          -- user).
          --
          -- Some things, like dict-fun Ids and default-method Ids are "born"
          -- with the Exported flag on, for exactly the above reason, but some
          -- we only discover as we go.  Specifically:
          --
          --   * The to/from functions for generic data types
          --
          --   * Top-level variables appearing free in the RHS of an orphan
          --     rule
          --
          --   * Top-level variables appearing free in a TH bracket

410
        tcg_th_used :: TcRef Bool,
411 412
          -- ^ @True@ <=> Template Haskell syntax used.
          --
413
          -- We need this so that we can generate a dependency on the
Gabor Greif's avatar
typos  
Gabor Greif committed
414
          -- Template Haskell package, because the desugarer is going
415 416
          -- to emit loads of references to TH symbols.  The reference
          -- is implicit rather than explicit, so we have to zap a
417 418
          -- mutable variable.

419 420 421 422 423
        tcg_th_splice_used :: TcRef Bool,
          -- ^ @True@ <=> A Template Haskell splice was used.
          --
          -- Splices disable recompilation avoidance (see #481)

424
        tcg_dfun_n  :: TcRef OccSet,
425
          -- ^ Allows us to choose unique DFun names.
426

427
        -- The next fields accumulate the payload of the module
Gabor Greif's avatar
Gabor Greif committed
428
        -- The binds, rules and foreign-decl fields are collected
429
        -- initially in un-zonked form and are finally zonked in tcRnSrcDecls
430

431
        tcg_rn_exports :: Maybe [Located (IE Name)],
432 433
                -- Nothing <=> no explicit export list

434
        tcg_rn_imports :: [LImportDecl Name],
435 436
                -- Keep the renamed imports regardless.  They are not
                -- voluminous and are needed if you want to report unused imports
simonpj@microsoft.com's avatar
simonpj@microsoft.com committed
437

438
        tcg_rn_decls :: Maybe (HsGroup Name),
439 440
          -- ^ Renamed decls, maybe.  @Nothing@ <=> Don't retain renamed
          -- decls.
441

442
        tcg_dependent_files :: TcRef [FilePath], -- ^ dependencies from addDependentFile
GregWeber's avatar
GregWeber committed
443

444 445 446 447 448 449
#ifdef GHCI
        tcg_th_topdecls :: TcRef [LHsDecl RdrName],
        -- ^ Top-level declarations from addTopDecls

        tcg_th_topnames :: TcRef NameSet,
        -- ^ Exact names bound in top-level declarations in tcg_th_topdecls
450 451 452

        tcg_th_modfinalizers :: TcRef [TH.Q ()],
        -- ^ Template Haskell module finalizers
453 454 455

        tcg_th_state :: TcRef (Map TypeRep Dynamic),
        -- ^ Template Haskell state
456 457
#endif /* GHCI */

458
        tcg_ev_binds  :: Bag EvBind,        -- Top-level evidence bindings
459

460 461 462
        -- Things defined in this module, or (in GHCi)
        -- in the declarations for a single GHCi command.
        -- For the latter, see Note [The interactive package] in HscTypes
463 464 465 466 467 468 469 470 471 472 473 474
        tcg_binds     :: LHsBinds Id,        -- Value bindings in this module
        tcg_sigs      :: NameSet,            -- ...Top-level names that *lack* a signature
        tcg_imp_specs :: [LTcSpecPrag],      -- ...SPECIALISE prags for imported Ids
        tcg_warns     :: Warnings,           -- ...Warnings and deprecations
        tcg_anns      :: [Annotation],       -- ...Annotations
        tcg_tcs       :: [TyCon],            -- ...TyCons and Classes
        tcg_insts     :: [ClsInst],          -- ...Instances
        tcg_fam_insts :: [FamInst],          -- ...Family instances
        tcg_rules     :: [LRuleDecl Id],     -- ...Rules
        tcg_fords     :: [LForeignDecl Id],  -- ...Foreign import & exports
        tcg_vects     :: [LVectDecl Id],     -- ...Vectorisation declarations
        tcg_patsyns   :: [PatSyn],           -- ...Pattern synonyms
475

476
        tcg_doc_hdr   :: Maybe LHsDocString, -- ^ Maybe Haddock header docs
477 478 479
        tcg_hpc       :: AnyHpcUsage,        -- ^ @True@ if any part of the
                                             --  prog uses hpc instrumentation.

480
        tcg_main      :: Maybe Name,         -- ^ The Name of the main
481 482
                                             -- function, if this module is
                                             -- the main module.
Adam Gundry's avatar
Adam Gundry committed
483

484 485 486 487 488
        tcg_safeInfer :: TcRef (Bool, WarningMessages),
        -- ^ Has the typechecker inferred this module as -XSafe (Safe Haskell)
        -- See Note [Safe Haskell Overlapping Instances Implementation],
        -- although this is used for more than just that failure case.

Facundo Domínguez's avatar
Facundo Domínguez committed
489
        tcg_tc_plugins :: [TcPluginSolver],
490
        -- ^ A list of user-defined plugins for the constraint solver.
Facundo Domínguez's avatar
Facundo Domínguez committed
491 492 493

        tcg_static_wc :: TcRef WantedConstraints
          -- ^ Wanted constraints of static forms.
494
    }
495

496 497 498 499
tcVisibleOrphanMods :: TcGblEnv -> ModuleSet
tcVisibleOrphanMods tcg_env
    = mkModuleSet (tcg_mod tcg_env : imp_orphs (tcg_imports tcg_env))

500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546
-- Note [Signature parameters in TcGblEnv and DynFlags]
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- When compiling signature files, we need to know which implementation
-- we've actually linked against the signature.  There are three seemingly
-- redundant places where this information is stored: in DynFlags, there
-- is sigOf, and in TcGblEnv, there is tcg_sig_of and tcg_impl_rdr_env.
-- Here's the difference between each of them:
--
-- * DynFlags.sigOf is global per invocation of GHC.  If we are compiling
--   with --make, there may be multiple signature files being compiled; in
--   which case this parameter is a map from local module name to implementing
--   Module.
--
-- * HscEnv.tcg_sig_of is global per the compilation of a single file, so
--   it is simply the result of looking up tcg_mod in the DynFlags.sigOf
--   parameter.  It's setup in TcRnMonad.initTc.  This prevents us
--   from having to repeatedly do a lookup in DynFlags.sigOf.
--
-- * HscEnv.tcg_impl_rdr_env is a RdrEnv that lets us look up names
--   according to the sig-of module.  It's setup in TcRnDriver.tcRnSignature.
--   Here is an example showing why we need this map:
--
--  module A where
--      a = True
--
--  module ASig where
--      import B
--      a :: Bool
--
--  module B where
--      b = False
--
-- When we compile ASig --sig-of main:A, the default
-- global RdrEnv (tcg_rdr_env) has an entry for b, but not for a
-- (we never imported A).  So we have to look in a different environment
-- to actually get the original name.
--
-- By the way, why do we need to do the lookup; can't we just use A:a
-- as the name directly?  Well, if A is reexporting the entity from another
-- module, then the original name needs to be the real original name:
--
--  module C where
--      a = True
--
--  module A(a) where
--      import C

547 548 549
instance ContainsModule TcGblEnv where
    extractModule env = tcg_mod env

550 551 552 553 554 555 556 557 558 559 560 561
data RecFieldEnv
  = RecFields (NameEnv [Name])  -- Maps a constructor name *in this module*
                                -- to the fields for that constructor
              NameSet           -- Set of all fields declared *in this module*;
                                -- used to suppress name-shadowing complaints
                                -- when using record wild cards
                                -- E.g.  let fld = e in C {..}
        -- This is used when dealing with ".." notation in record
        -- construction and pattern matching.
        -- The FieldEnv deals *only* with constructors defined in *this*
        -- module.  For imported modules, we get the same info from the
        -- TypeEnv
562

Austin Seipp's avatar
Austin Seipp committed
563
{-
564 565 566 567 568 569 570 571 572 573 574
Note [Tracking unused binding and imports]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
We gather two sorts of usage information
 * tcg_dus (defs/uses)
      Records *defined* Names (local, top-level)
          and *used*    Names (local or imported)

      Used (a) to report "defined but not used"
               (see RnNames.reportUnusedNames)
           (b) to generate version-tracking usage info in interface
               files (see MkIface.mkUsedNames)
575
   This usage info is mainly gathered by the renamer's
576 577 578 579 580 581 582
   gathering of free-variables

 * tcg_used_rdrnames
      Records used *imported* (not locally-defined) RdrNames
      Used only to report unused import declarations
      Notice that they are RdrNames, not Names, so we can
      tell whether the reference was qualified or unqualified, which
583
      is esssential in deciding whether a particular import decl
584 585 586
      is unnecessary.  This info isn't present in Names.


Austin Seipp's avatar
Austin Seipp committed
587 588
************************************************************************
*                                                                      *
589
                The local typechecker environment
Austin Seipp's avatar
Austin Seipp committed
590 591
*                                                                      *
************************************************************************
592

Edward Z. Yang's avatar
Edward Z. Yang committed
593 594
Note [The Global-Env/Local-Env story]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
595
During type checking, we keep in the tcg_type_env
596 597
        * All types and classes
        * All Ids derived from types and classes (constructors, selectors)
598 599 600

At the end of type checking, we zonk the local bindings,
and as we do so we add to the tcg_type_env
601
        * Locally defined top-level Ids
602 603

Why?  Because they are now Ids not TcIds.  This final GlobalEnv is
604 605 606
        a) fed back (via the knot) to typechecking the
           unfoldings of interface signatures
        b) used in the ModDetails of this module
Austin Seipp's avatar
Austin Seipp committed
607
-}
608

609 610
data TcLclEnv           -- Changes as we move inside an expression
                        -- Discarded after typecheck/rename; not passed on to desugarer
611
  = TcLclEnv {
612
        tcl_loc        :: RealSrcSpan,     -- Source span
613
        tcl_ctxt       :: [ErrCtxt],       -- Error context, innermost on top
614
        tcl_tclvl      :: TcLevel,         -- Birthplace for new unification variables
615

616
        tcl_th_ctxt    :: ThStage,         -- Template Haskell context
617 618 619
        tcl_th_bndrs   :: ThBindEnv,       -- Binding level of in-scope Names
                                           -- defined in this module (not imported)

620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635
        tcl_arrow_ctxt :: ArrowCtxt,       -- Arrow-notation context

        tcl_rdr :: LocalRdrEnv,         -- Local name envt
                -- Maintained during renaming, of course, but also during
                -- type checking, solely so that when renaming a Template-Haskell
                -- splice we have the right environment for the renamer.
                --
                --   Does *not* include global name envt; may shadow it
                --   Includes both ordinary variables and type variables;
                --   they are kept distinct because tyvar have a different
                --   occurrence contructor (Name.TvOcc)
                -- We still need the unsullied global name env so that
                --   we can look up record field names

        tcl_env  :: TcTypeEnv,    -- The local type environment:
                                  -- Ids and TyVars defined in this module
636

637
        tcl_bndrs :: TcIdBinderStack,   -- Used for reporting relevant bindings
638 639 640

        tcl_tidy :: TidyEnv,      -- Used for tidying types; contains all
                                  -- in-scope type variables (but not term variables)
641 642 643 644 645

        tcl_tyvars :: TcRef TcTyVarSet, -- The "global tyvars"
                        -- Namely, the in-scope TyVars bound in tcl_env,
                        -- plus the tyvars mentioned in the types of Ids bound
                        -- in tcl_lenv.
646 647
                        -- Why mutable? see notes with tcGetGlobalTyVars

648 649
        tcl_lie  :: TcRef WantedConstraints,    -- Place to accumulate type constraints
        tcl_errs :: TcRef Messages              -- Place to accumulate errors
650 651
    }

652
type TcTypeEnv = NameEnv TcTyThing
653

654 655 656 657 658 659 660 661 662
type ThBindEnv = NameEnv (TopLevelFlag, ThLevel)
   -- Domain = all Ids bound in this module (ie not imported)
   -- The TopLevelFlag tells if the binding is syntactically top level.
   -- We need to know this, because the cross-stage persistence story allows
   -- cross-stage at arbitrary types if the Id is bound at top level.
   --
   -- Nota bene: a ThLevel of 'outerLevel' is *not* the same as being
   -- bound at top level!  See Note [Template Haskell levels] in TcSplice

663 664
{- Note [Given Insts]
   ~~~~~~~~~~~~~~~~~~
665
Because of GADTs, we have to pass inwards the Insts provided by type signatures
666
and existential contexts. Consider
667 668 669
        data T a where { T1 :: b -> b -> T [b] }
        f :: Eq a => T a -> Bool
        f (T1 x y) = [x]==[y]
670 671

The constructor T1 binds an existential variable 'b', and we need Eq [b].
672
Well, we have it, because Eq a refines to Eq [b], but we can only spot that if we
673 674 675
pass it inwards.

-}
676

677 678 679 680 681 682 683 684
-- | Type alias for 'IORef'; the convention is we'll use this for mutable
-- bits of data in 'TcGblEnv' which are updated during typechecking and
-- returned at the end.
type TcRef a     = IORef a
-- ToDo: when should I refer to it as a 'TcId' instead of an 'Id'?
type TcId        = Id
type TcIdSet     = IdSet

685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702
---------------------------
-- The TcIdBinderStack
---------------------------

type TcIdBinderStack = [TcIdBinder]
   -- This is a stack of locally-bound ids, innermost on top
   -- Used ony in error reporting (relevantBindings in TcError)

data TcIdBinder
  = TcIdBndr
       TcId
       TopLevelFlag    -- Tells whether the bindind is syntactically top-level
                       -- (The monomorphic Ids for a recursive group count
                       --  as not-top-level for this purpose.)

instance Outputable TcIdBinder where
   ppr (TcIdBndr id top_lvl) = ppr id <> brackets (ppr top_lvl)

703
---------------------------
704
-- Template Haskell stages and levels
705 706
---------------------------

707
data ThStage    -- See Note [Template Haskell state diagram] in TcSplice
708
  = Splice      -- Inside a top-level splice splice
709 710 711
                -- This code will be run *at compile time*;
                --   the result replaces the splice
                -- Binding level = 0
712
      Bool      -- True if in a typed splice, False otherwise
713 714 715

  | Comp        -- Ordinary Haskell code
                -- Binding level = 1
716

717
  | Brack                       -- Inside brackets
718 719 720 721 722 723 724 725 726
      ThStage                   --   Enclosing stage
      PendingStuff

data PendingStuff
  = RnPendingUntyped              -- Renaming the inside of an *untyped* bracket
      (TcRef [PendingRnSplice])   -- Pending splices in here

  | RnPendingTyped                -- Renaming the inside of a *typed* bracket

727
  | TcPending                     -- Typechecking the inside of a typed bracket
728 729
      (TcRef [PendingTcSplice])   --   Accumulate pending splices here
      (TcRef WantedConstraints)   --     and type constraints here
730 731 732

topStage, topAnnStage, topSpliceStage :: ThStage
topStage       = Comp
733 734
topAnnStage    = Splice False
topSpliceStage = Splice False
735 736

instance Outputable ThStage where
737 738 739
   ppr (Splice _)  = text "Splice"
   ppr Comp        = text "Comp"
   ppr (Brack s _) = text "Brack" <> parens (ppr s)
740

741
type ThLevel = Int
742 743 744 745 746
    -- NB: see Note [Template Haskell levels] in TcSplice
    -- Incremented when going inside a bracket,
    -- decremented when going inside a splice
    -- NB: ThLevel is one greater than the 'n' in Fig 2 of the
    --     original "Template meta-programming for Haskell" paper
747

748
impLevel, outerLevel :: ThLevel
749 750
impLevel = 0    -- Imported things; they can be used inside a top level splice
outerLevel = 1  -- Things defined outside brackets
751

752
thLevel :: ThStage -> ThLevel
753 754 755
thLevel (Splice _)  = 0
thLevel Comp        = 1
thLevel (Brack s _) = thLevel s + 1
756

ross's avatar
ross committed
757 758 759 760
---------------------------
-- Arrow-notation context
---------------------------

761 762
{- Note [Escaping the arrow scope]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ross's avatar
ross committed
763 764 765 766
In arrow notation, a variable bound by a proc (or enclosed let/kappa)
is not in scope to the left of an arrow tail (-<) or the head of (|..|).
For example

767
        proc x -> (e1 -< e2)
ross's avatar
ross committed
768 769 770 771

Here, x is not in scope in e1, but it is in scope in e2.  This can get
a bit complicated:

772 773
        let x = 3 in
        proc y -> (proc z -> e1) -< e2
ross's avatar
ross committed
774

775
Here, x and z are in scope in e1, but y is not.
776 777

We implement this by
ross's avatar
ross committed
778 779 780
recording the environment when passing a proc (using newArrowScope),
and returning to that (using escapeArrowScope) on the left of -< and the
head of (|..|).
781

782 783 784 785 786 787 788 789 790 791
All this can be dealt with by the *renamer*. But the type checker needs
to be involved too.  Example (arrowfail001)
  class Foo a where foo :: a -> ()
  data Bar = forall a. Foo a => Bar a
  get :: Bar -> ()
  get = proc x -> case x of Bar a -> foo -< a
Here the call of 'foo' gives rise to a (Foo a) constraint that should not
be captured by the pattern match on 'Bar'.  Rather it should join the
constraints from further out.  So we must capture the constraint bag
from further out in the ArrowCtxt that we push inwards.
ross's avatar
ross committed
792 793
-}

794
data ArrowCtxt   -- Note [Escaping the arrow scope]
ross's avatar
ross committed
795
  = NoArrowCtxt
796 797
  | ArrowCtxt LocalRdrEnv (TcRef WantedConstraints)

798

799 800 801 802
---------------------------
-- TcTyThing
---------------------------

Edward Z. Yang's avatar
Edward Z. Yang committed
803 804 805
-- | A typecheckable thing available in a local context.  Could be
-- 'AGlobal' 'TyThing', but also lexically scoped variables, etc.
-- See 'TcEnv' for how to retrieve a 'TyThing' given a 'Name'.
806
data TcTyThing
807
  = AGlobal TyThing             -- Used only in the return type of a lookup
808

809 810
  | ATcId   {           -- Ids defined in this module; may not be fully zonked
        tct_id     :: TcId,
811
        tct_closed :: TopLevelFlag }   -- See Note [Bindings with closed types]
812

813 814 815 816
  | ATyVar  Name TcTyVar        -- The type variable to which the lexically scoped type
                                -- variable is bound. We only need the Name
                                -- for error-message purposes; it is the corresponding
                                -- Name in the domain of the envt
817

dreixel's avatar
dreixel committed
818
  | AThing  TcKind   -- Used temporarily, during kind checking, for the
819
                     -- tycons and clases in this recursive group
dreixel's avatar
dreixel committed
820 821 822
                     -- Can be a mono-kind or a poly-kind; in TcTyClsDcls see
                     -- Note [Type checking recursive type and class declarations]

823
  | APromotionErr PromotionErr
824

825
data PromotionErr
826 827 828 829 830
  = TyConPE          -- TyCon used in a kind before we are ready
                     --     data T :: T -> * where ...
  | ClassPE          -- Ditto Class

  | FamDataConPE     -- Data constructor for a data family
831
                     -- See Note [AFamDataCon: not promoting data family constructors] in TcRnDriver
dreixel's avatar
dreixel committed
832

Krzysztof Gogolewski's avatar
Krzysztof Gogolewski committed
833
  | RecDataConPE     -- Data constructor in a recursive loop
834
                     -- See Note [ARecDataCon: recusion and promoting data constructors] in TcTyClsDecls
835
  | NoDataKinds      -- -XDataKinds not enabled
836

837
instance Outputable TcTyThing where     -- Debugging only
838
   ppr (AGlobal g)      = pprTyThing g
839 840
   ppr elt@(ATcId {})   = text "Identifier" <>
                          brackets (ppr (tct_id elt) <> dcolon
841
                                 <> ppr (varType (tct_id elt)) <> comma
842
                                 <+> ppr (tct_closed elt))
Simon Peyton Jones's avatar
Simon Peyton Jones committed
843
   ppr (ATyVar n tv)    = text "Type variable" <+> quotes (ppr n) <+> equals <+> ppr tv
844
   ppr (AThing k)       = text "AThing" <+> ppr k
845 846 847 848 849 850 851
   ppr (APromotionErr err) = text "APromotionErr" <+> ppr err

instance Outputable PromotionErr where
  ppr ClassPE      = text "ClassPE"
  ppr TyConPE      = text "TyConPE"
  ppr FamDataConPE = text "FamDataConPE"
  ppr RecDataConPE = text "RecDataConPE"
852
  ppr NoDataKinds  = text "NoDataKinds"
853 854

pprTcTyThingCategory :: TcTyThing -> SDoc
855 856 857 858 859 860 861 862 863 864 865
pprTcTyThingCategory (AGlobal thing)    = pprTyThingCategory thing
pprTcTyThingCategory (ATyVar {})        = ptext (sLit "Type variable")
pprTcTyThingCategory (ATcId {})         = ptext (sLit "Local identifier")
pprTcTyThingCategory (AThing {})        = ptext (sLit "Kinded thing")
pprTcTyThingCategory (APromotionErr pe) = pprPECategory pe

pprPECategory :: PromotionErr -> SDoc
pprPECategory ClassPE      = ptext (sLit "Class")
pprPECategory TyConPE      = ptext (sLit "Type constructor")
pprPECategory FamDataConPE = ptext (sLit "Data constructor")
pprPECategory RecDataConPE = ptext (sLit "Data constructor")
866
pprPECategory NoDataKinds  = ptext (sLit "Data constructor")
867

868 869
{- Note [Bindings with closed types]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
870 871 872 873 874
Consider

  f x = let g ys = map not ys
        in ...

875
Can we generalise 'g' under the OutsideIn algorithm?  Yes,
dreixel's avatar
dreixel committed
876
because all g's free variables are top-level; that is they themselves
877 878 879 880 881
have no free type variables, and it is the type variables in the
environment that makes things tricky for OutsideIn generalisation.

Definition:
   A variable is "closed", and has tct_closed set to TopLevel,
882 883
iff
   a) all its free variables are imported, or are let-bound with closed types
884 885 886 887
   b) generalisation is not restricted by the monomorphism restriction

Under OutsideIn we are free to generalise a closed let-binding.
This is an extension compared to the JFP paper on OutsideIn, which
888
used "top-level" as a proxy for "closed".  (It's not a good proxy
889 890 891 892
anyway -- the MR can make a top-level binding with a free type
variable.)

Note that:
893
  * A top-level binding may not be closed, if it suffers from the MR
894 895 896

  * A nested binding may be closed (eg 'g' in the example we started with)
    Indeed, that's the point; whether a function is defined at top level
897
    or nested is orthogonal to the question of whether or not it is closed
898 899 900 901 902

  * A binding may be non-closed because it mentions a lexically scoped
    *type variable*  Eg
        f :: forall a. blah
        f x = let g y = ...(y::a)...
Austin Seipp's avatar
Austin Seipp committed
903
-}
904

905
type ErrCtxt = (Bool, TidyEnv -> TcM (TidyEnv, MsgDoc))
906 907 908
        -- Monadic so that we have a chance
        -- to deal with bound type variables just before error
        -- message construction
909

910 911
        -- Bool:  True <=> this is a landmark context; do not
        --                 discard it when trimming for display
912

Austin Seipp's avatar
Austin Seipp committed
913 914 915
{-
************************************************************************
*                                                                      *
916
        Operations over ImportAvails
Austin Seipp's avatar
Austin Seipp committed
917 918 919
*                                                                      *
************************************************************************
-}
920

921 922 923 924 925 926 927 928 929 930 931 932
-- | 'ImportAvails' summarises what was imported from where, irrespective of
-- whether the imported things are actually used or not.  It is used:
--
--  * when processing the export list,
--
--  * when constructing usage info for the interface file,
--
--  * to identify the list of directly imported modules for initialisation
--    purposes and for optimised overlap checking of family instances,
--
--  * when figuring out what things are really unused
--
933
data ImportAvails
934
   = ImportAvails {
935 936
        imp_mods :: ImportedMods,
          --      = ModuleEnv [(ModuleName, Bool, SrcSpan, Bool)],
937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952
          -- ^ Domain is all directly-imported modules
          -- The 'ModuleName' is what the module was imported as, e.g. in
          -- @
          --     import Foo as Bar
          -- @
          -- it is @Bar@.
          --
          -- The 'Bool' means:
          --
          --  - @True@ => import was @import Foo ()@
          --
          --  - @False@ => import was some other form
          --
          -- Used
          --
          --   (a) to help construct the usage information in the interface
Krzysztof Gogolewski's avatar
Krzysztof Gogolewski committed
953
          --       file; if we import something we need to recompile if the
954 955 956 957 958 959 960 961
          --       export version changes
          --
          --   (b) to specify what child modules to initialise
          --