TcRnTypes.hs 158 KB
Newer Older
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

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
Gabor Greif's avatar
Gabor Greif committed
13
like fashion when entering expressions... etc.
14 15

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

19
{-# LANGUAGE CPP, DeriveFunctor, ExistentialQuantification, GeneralizedNewtypeDeriving,
20
             ViewPatterns #-}
21

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

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

32 33 34
        -- Frontend types (shouldn't really be here)
        FrontendResult(..),

35
        -- Renamer types
36
        ErrCtxt, RecFieldEnv,
37
        ImportAvails(..), emptyImportAvails, plusImportAvails,
38
        WhereFrom(..), mkModDeps, modDepsElts,
39

40
        -- Typechecker types
41
        TcTypeEnv, TcBinderStack, TcBinder(..),
42
        TcTyThing(..), PromotionErr(..),
43
        IdBindingInfo(..), ClosedTypeId, RhsNames,
44
        IsGroupClosed(..),
45
        SelfBootInfo(..),
46
        pprTcTyThingCategory, pprPECategory, CompleteMatch(..),
47

48
        -- Desugaring types
49
        DsM, DsLclEnv(..), DsGblEnv(..),
50 51
        DsMetaEnv, DsMetaVal(..), CompleteMatchMap,
        mkCompleteMatchMap, extendCompleteMatchMap,
52

53
        -- Template Haskell
54 55
        ThStage(..), SpliceType(..), PendingStuff(..),
        topStage, topAnnStage, topSpliceStage,
56
        ThLevel, impLevel, outerLevel, thLevel,
57
        ForeignSrcLang(..),
58

59
        -- Arrows
60
        ArrowCtxt(..),
61

62
        -- TcSigInfo
63
        TcSigFun, TcSigInfo(..), TcIdSigInfo(..),
64
        TcIdSigInst(..), TcPatSynInfo(..),
65
        isPartialSig, hasCompleteSig,
66

67 68 69
        -- QCInst
        QCInst(..), isPendingScInst,

70
        -- Canonical constraints
71 72
        Xi, Ct(..), Cts, emptyCts, andCts, andManyCts, pprCts,
        singleCt, listToCts, ctsElts, consCts, snocCts, extendCtsList,
73
        isEmptyCts, isCTyEqCan, isCFunEqCan,
74
        isPendingScDict, superClassesMightHelp, getPendingWantedScs,
75
        isCDictCan_Maybe, isCFunEqCan_maybe,
76
        isCNonCanonical, isWantedCt, isDerivedCt,
77
        isGivenCt, isHoleCt, isOutOfScopeCt, isExprHoleCt, isTypeHoleCt,
Eric Seidel's avatar
Eric Seidel committed
78
        isUserTypeErrorCt, getUserTypeErrorMsg,
79
        ctEvidence, ctLoc, setCtLoc, ctPred, ctFlavour, ctEqRel, ctOrigin,
80
        ctEvId, mkTcEqPredLikeEv,
81
        mkNonCanonical, mkNonCanonicalCt, mkGivens,
82
        mkIrredCt, mkInsolubleCt,
83
        ctEvPred, ctEvLoc, ctEvOrigin, ctEvEqRel,
84
        ctEvExpr, ctEvTerm, ctEvCoercion, ctEvEvId,
85 86
        tyCoVarsOfCt, tyCoVarsOfCts,
        tyCoVarsOfCtList, tyCoVarsOfCtsList,
87

88
        WantedConstraints(..), insolubleWC, emptyWC, isEmptyWC,
89
        isSolvedWC, andWC, unionsWC, mkSimpleWC, mkImplicWC,
90 91
        addInsols, insolublesOnly, addSimples, addImplics,
        tyCoVarsOfWC, dropDerivedWC, dropDerivedSimples,
92
        tyCoVarsOfWCList, insolubleCt, insolubleEqCt,
93
        isDroppableCt, insolubleImplic,
94
        arisesFromGivens,
95

96 97
        Implication(..), newImplication, implicationPrototype,
        implicLclEnv, implicDynFlags,
98
        ImplicStatus(..), isInsolubleStatus, isSolvedStatus,
99
        SubGoalDepth, initialSubGoalDepth, maxSubGoalDepth,
100
        bumpSubGoalDepth, subGoalDepthExceeded,
101
        CtLoc(..), ctLocSpan, ctLocEnv, ctLocLevel, ctLocOrigin,
102
        ctLocTypeOrKind_maybe,
Simon Peyton Jones's avatar
Simon Peyton Jones committed
103
        ctLocDepth, bumpCtLocDepth, isGivenLoc,
104
        setCtLocOrigin, updateCtLocOrigin, setCtLocEnv, setCtLocSpan,
105
        CtOrigin(..), exprCtOrigin, lexprCtOrigin, matchesCtOrigin, grhssCtOrigin,
106
        isVisibleOrigin, toInvisibleOrigin,
107 108
        TypeOrKind(..), isTypeLevel, isKindLevel,
        pprCtOrigin, pprCtLoc,
109
        pushErrCtxt, pushErrCtxtSameOrigin,
110

111

112
        SkolemInfo(..), pprSigSkolInfo, pprSkolInfo,
113

114
        CtEvidence(..), TcEvDest(..),
115
        mkKindLoc, toKindLoc, mkGivenLoc,
116
        isWanted, isGiven, isDerived, isGivenOrWDeriv,
117
        ctEvRole,
118

119
        wrapType, wrapTypeWithImplication,
120
        removeBindingShadowing,
121

122 123 124
        -- Constraint solver plugins
        TcPlugin(..), TcPluginResult(..), TcPluginSolver,
        TcPluginM, runTcPluginM, unsafeTcPluginTcM,
125
        getEvBindsTcPluginM,
126

127
        CtFlavour(..), ShadowInfo(..), ctEvFlavour,
128
        CtFlavourRole, ctEvFlavourRole, ctFlavourRole,
129 130
        eqCanRewrite, eqCanRewriteFR, eqMayRewriteFR,
        eqCanDischargeFR,
131
        funEqCanDischarge, funEqCanDischargeF,
132

133
        -- Pretty printing
134
        pprEvVarTheta,
135
        pprEvVars, pprEvVarWithType,
136

137
        -- Misc other types
138
        TcId, TcIdSet,
Edward Z. Yang's avatar
Edward Z. Yang committed
139
        Hole(..), holeOcc,
140 141 142 143 144
        NameShape(..),

        -- Role annotations
        RoleAnnotEnv, emptyRoleAnnotEnv, mkRoleAnnotEnv,
        lookupRoleAnnot, getRoleAnnots,
145

146 147 148 149
  ) where

#include "HsVersions.h"

150 151
import GhcPrelude

152
import HsSyn
153
import CoreSyn
154
import HscTypes
155
import TcEvidence
156
import Type
157
import Class    ( Class )
158
import TyCon    ( TyCon, TyConFlavour, tyConKind )
159
import TyCoRep  ( coHoleCoVar )
160
import Coercion ( Coercion, mkHoleCo )
cactus's avatar
cactus committed
161
import ConLike  ( ConLike(..) )
162
import DataCon  ( DataCon, dataConUserType, dataConOrigArgTys )
163
import PatSyn   ( PatSyn, pprPatSynType )
164
import Id       ( idType, idName )
165
import FieldLabel ( FieldLabel )
166
import TcType
167
import Annotations
168 169
import InstEnv
import FamInstEnv
170
import PmExpr
171
import IOEnv
172 173
import RdrName
import Name
174
import NameEnv
175
import NameSet
176
import Avail
177
import Var
178
import FV
179
import VarEnv
180
import Module
181 182 183
import SrcLoc
import VarSet
import ErrUtils
184
import UniqFM
185 186
import UniqSupply
import BasicTypes
187
import Bag
Ian Lynagh's avatar
Ian Lynagh committed
188
import DynFlags
189
import Outputable
190
import ListSetOps
191
import FastString
192
import qualified GHC.LanguageExtensions as LangExt
Edward Z. Yang's avatar
Edward Z. Yang committed
193
import Fingerprint
194
import Util
195
import PrelNames ( isUnboundName )
196
import CostCentreState
197

198
import Control.Monad (ap, msum)
quchen's avatar
quchen committed
199
import qualified Control.Monad.Fail as MonadFail
200
import Data.Set      ( Set )
201
import qualified Data.Set as S
202

203
import Data.List ( sort )
204
import Data.Map ( Map )
205 206
import Data.Dynamic  ( Dynamic )
import Data.Typeable ( TypeRep )
207
import Data.Maybe    ( mapMaybe )
208
import GHCi.Message
209
import GHCi.RemoteTypes
210

211 212
import {-# SOURCE #-} TcHoleFitTypes ( HoleFitPlugin )

213
import qualified Language.Haskell.TH as TH
214

Edward Z. Yang's avatar
Edward Z. Yang committed
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
-- | A 'NameShape' is a substitution on 'Name's that can be used
-- to refine the identities of a hole while we are renaming interfaces
-- (see 'RnModIface').  Specifically, a 'NameShape' for
-- 'ns_module_name' @A@, defines a mapping from @{A.T}@
-- (for some 'OccName' @T@) to some arbitrary other 'Name'.
--
-- The most intruiging thing about a 'NameShape', however, is
-- how it's constructed.  A 'NameShape' is *implied* by the
-- exported 'AvailInfo's of the implementor of an interface:
-- if an implementor of signature @<H>@ exports @M.T@, you implicitly
-- define a substitution from @{H.T}@ to @M.T@.  So a 'NameShape'
-- is computed from the list of 'AvailInfo's that are exported
-- by the implementation of a module, or successively merged
-- together by the export lists of signatures which are joining
-- together.
--
-- It's not the most obvious way to go about doing this, but it
-- does seem to work!
--
-- NB: Can't boot this and put it in NameShape because then we
-- start pulling in too many DynFlags things.
data NameShape = NameShape {
        ns_mod_name :: ModuleName,
        ns_exports :: [AvailInfo],
        ns_map :: OccEnv Name
    }


243 244 245
{-
************************************************************************
*                                                                      *
246
               Standard monad definition for TcRn
247
    All the combinators for the monad can be found in TcRnMonad
248 249
*                                                                      *
************************************************************************
250

251
The monad itself has to be defined here, because it is mentioned by ErrCtxt
252
-}
253

cactus's avatar
cactus committed
254
type TcRnIf a b = IOEnv (Env a b)
255 256 257 258 259 260 261 262 263 264 265 266
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
267 268 269 270 271 272

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

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

Rik Steenkamp's avatar
Rik Steenkamp committed
274
-- We 'stack' these envs through the Reader like monad infrastructure
275 276 277
-- as we move into an expression (although the change is focused in
-- the lcl type).
data Env gbl lcl
278
  = Env {
279
        env_top  :: !HscEnv, -- Top-level stuff that never changes
280
                             -- Includes all info about imported things
281
                             -- BangPattern is to fix leak, see #15111
282

283
        env_us   :: {-# UNPACK #-} !(IORef UniqSupply),
Rik Steenkamp's avatar
Rik Steenkamp committed
284
                             -- Unique supply for local variables
285

286 287
        env_gbl  :: gbl,     -- Info about things defined at the top level
                             -- of the module being compiled
288

289
        env_lcl  :: lcl      -- Nested stuff; changes as we go into
290
    }
291

Ian Lynagh's avatar
Ian Lynagh committed
292 293 294
instance ContainsDynFlags (Env gbl lcl) where
    extractDynFlags env = hsc_dflags (env_top env)

295 296 297
instance ContainsModule gbl => ContainsModule (Env gbl lcl) where
    extractModule env = extractModule (env_gbl env)

298 299 300 301 302 303 304 305 306 307 308 309

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

data IfGblEnv
  = IfGblEnv {
310 311 312
        -- Some information about where this environment came from;
        -- useful for debugging.
        if_doc :: SDoc,
313 314 315 316 317
        -- 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.
318
        -- See Note [Tying the knot] in TcIface
319 320 321 322 323 324 325 326 327 328 329
        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
Edward Z. Yang's avatar
Edward Z. Yang committed
330 331
        -- NB: This is a semantic module, see
        -- Note [Identity versus semantic module]
332 333
        if_mod :: Module,

334 335 336 337 338
        -- Whether or not the IfaceDecl came from a boot
        -- file or not; we'll use this to choose between
        -- NoUnfolding and BootUnfolding
        if_boot :: Bool,

339 340 341 342 343 344 345
        -- 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

Edward Z. Yang's avatar
Edward Z. Yang committed
346 347
        if_nsubst :: Maybe NameShape,

348 349 350
        -- This field is used to make sure "implicit" declarations
        -- (anything that cannot be exported in mi_exports) get
        -- wired up correctly in typecheckIfacesForMerging.  Most
351
        -- of the time it's @Nothing@.  See Note [Resolving never-exported Names in TcIface]
352 353 354
        -- in TcIface.
        if_implicits_env :: Maybe TypeEnv,

niteria's avatar
niteria committed
355 356
        if_tv_env  :: FastStringEnv TyVar,     -- Nested tyvar bindings
        if_id_env  :: FastStringEnv Id         -- Nested id binding
357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378
    }

{-
************************************************************************
*                                                                      *
                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:
-}

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
379 380
        , ds_complete_matches :: CompleteMatchMap
           -- Additional complete pattern matches
381 382
        , ds_cc_st   :: IORef CostCentreState
           -- Tracking indices for cost centre annotations
383 384 385 386 387 388 389
        }

instance ContainsModule DsGblEnv where
    extractModule = ds_mod

data DsLclEnv = DsLclEnv {
        dsl_meta    :: DsMetaEnv,        -- Template Haskell bindings
390
        dsl_loc     :: RealSrcSpan,      -- To put in pattern-matching error msgs
Simon Peyton Jones's avatar
Simon Peyton Jones committed
391 392 393 394 395

        -- See Note [Note [Type and Term Equality Propagation] in Check.hs
        -- These two fields are augmented as we walk inwards,
        -- through each patttern match in turn
        dsl_dicts   :: Bag EvVar,     -- Constraints from GADT pattern-matching
396
        dsl_tm_cs   :: Bag TmVarCt,      -- Constraints form term-level pattern matching
Simon Peyton Jones's avatar
Simon Peyton Jones committed
397 398 399

        dsl_pm_iter :: IORef Int  -- Number of iterations for pmcheck so far
                                  -- We fail if this gets too big
400 401 402 403 404 405 406 407 408 409 410
     }

-- 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

411 412
   | DsSplice (HsExpr GhcTc) -- These bindings are introduced by
                             -- the PendingSplices on a HsBracketOut
413 414 415 416 417 418 419 420 421 422


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

423 424 425 426 427 428 429 430
-- | 'FrontendResult' describes the result of running the
-- frontend of a Haskell module.  Usually, you'll get
-- a 'FrontendTypecheck', since running the frontend involves
-- typechecking a program, but for an hs-boot merge you'll
-- just get a ModIface, since no actual typechecking occurred.
--
-- This data type really should be in HscTypes, but it needs
-- to have a TcGblEnv which is only defined here.
431 432 433
data FrontendResult
        = FrontendTypecheck TcGblEnv

Edward Z. Yang's avatar
Edward Z. Yang committed
434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456
-- Note [Identity versus semantic module]
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- When typechecking an hsig file, it is convenient to keep track
-- of two different "this module" identifiers:
--
--      - The IDENTITY module is simply thisPackage + the module
--        name; i.e. it uniquely *identifies* the interface file
--        we're compiling.  For example, p[A=<A>]:A is an
--        identity module identifying the requirement named A
--        from library p.
--
--      - The SEMANTIC module, which is the actual module that
--        this signature is intended to represent (e.g. if
--        we have a identity module p[A=base:Data.IORef]:A,
--        then the semantic module is base:Data.IORef)
--
-- Which one should you use?
--
--      - In the desugarer and later phases of compilation,
--        identity and semantic modules coincide, since we never compile
--        signatures (we just generate blank object files for
--        hsig files.)
--
457 458 459 460 461 462 463
--        A corrolary of this is that the following invariant holds at any point
--        past desugaring,
--
--            if I have a Module, this_mod, in hand representing the module
--            currently being compiled,
--            then moduleUnitId this_mod == thisPackage dflags
--
Edward Z. Yang's avatar
Edward Z. Yang committed
464 465 466 467 468 469 470 471 472 473 474
--      - For any code involving Names, we want semantic modules.
--        See lookupIfaceTop in IfaceEnv, mkIface and addFingerprints
--        in MkIface, and tcLookupGlobal in TcEnv
--
--      - When reading interfaces, we want the identity module to
--        identify the specific interface we want (such interfaces
--        should never be loaded into the EPS).  However, if a
--        hole module <A> is requested, we look for A.hi
--        in the home library we are compiling.  (See LoadIface.)
--        Similarly, in RnNames we check for self-imports using
--        identity modules, to allow signatures to import their implementor.
475 476 477 478
--
--      - For recompilation avoidance, you want the identity module,
--        since that will actually say the specific interface you
--        want to track (and recompile if it changes)
Edward Z. Yang's avatar
Edward Z. Yang committed
479

Edward Z. Yang's avatar
Edward Z. Yang committed
480
-- | 'TcGblEnv' describes the top-level of the module at the
481 482
-- point at which the typechecker is finished work.
-- It is this structure that is handed on to the desugarer
483
-- For state that needs to be updated during the typechecking
Edward Z. Yang's avatar
Edward Z. Yang committed
484
-- phase and returned at end, use a 'TcRef' (= 'IORef').
485 486
data TcGblEnv
  = TcGblEnv {
487
        tcg_mod     :: Module,         -- ^ Module being compiled
Edward Z. Yang's avatar
Edward Z. Yang committed
488 489
        tcg_semantic_mod :: Module,    -- ^ If a signature, the backing module
            -- See also Note [Identity versus semantic module]
490
        tcg_src     :: HscSource,
491
          -- ^ What kind of module (regular Haskell, hs-boot, hsig)
492

493 494
        tcg_rdr_env :: GlobalRdrEnv,   -- ^ Top level envt; used during renaming
        tcg_default :: Maybe [Type],
495
          -- ^ Types used for defaulting. @Nothing@ => no @default@ decl
496

497 498
        tcg_fix_env   :: FixityEnv,     -- ^ Just for things in this module
        tcg_field_env :: RecFieldEnv,   -- ^ Just for things in this module
499
                                        -- See Note [The interactive package] in HscTypes
500

501
        tcg_type_env :: TypeEnv,
502
          -- ^ Global type env for the module we are compiling now.  All
503 504 505 506 507
          -- 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)
508 509 510
          --
          -- NB: for what "things in this module" means, see
          -- Note [The interactive package] in HscTypes
511 512 513 514 515 516 517

        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)

518
        tcg_inst_env     :: !InstEnv,
519
          -- ^ Instance envt for all /home-package/ modules;
520
          -- Includes the dfuns in tcg_insts
521 522 523
          -- NB. BangPattern is to fix a leak, see #15111
        tcg_fam_inst_env :: !FamInstEnv, -- ^ Ditto for family instances
          -- NB. BangPattern is to fix a leak, see #15111
524
        tcg_ann_env      :: AnnEnv,     -- ^ And for annotations
525 526 527 528 529 530 531

                -- 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,
532
          -- ^ Information about what was imported from where, including
533
          -- things bound in this module. Also store Safe Haskell info
534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558
          -- here about transitive trusted package requirements.
          --
          -- There are not many uses of this field, so you can grep for
          -- all them.
          --
          -- The ImportAvails records information about the following
          -- things:
          --
          --    1. All of the modules you directly imported (tcRnImports)
          --    2. The orphans (only!) of all imported modules in a GHCi
          --       session (runTcInteractive)
          --    3. The module that instantiated a signature
          --    4. Each of the signatures that merged in
          --
          -- It is used in the following ways:
          --    - imp_orphs is used to determine what orphan modules should be
          --      visible in the context (tcVisibleOrphanMods)
          --    - imp_finsts is used to determine what family instances should
          --      be visible (tcExtendLocalFamInstEnv)
          --    - To resolve the meaning of the export list of a module
          --      (tcRnExports)
          --    - imp_mods is used to compute usage info (mkIfaceTc, deSugar)
          --    - imp_trust_own_pkg is used for Safe Haskell in interfaces
          --      (mkIfaceTc, as well as in HscMain)
          --    - To create the Dependencies field in interface (mkDependencies)
559

560 561
        tcg_dus       :: DefUses,   -- ^ What is defined in this module and what is used.
        tcg_used_gres :: TcRef [GlobalRdrElt],  -- ^ Records occurrences of imported entities
562 563
          -- One entry for each occurrence; but may have different GREs for
          -- the same Name See Note [Tracking unused binding and imports]
564

565
        tcg_keep :: TcRef NameSet,
566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583
          -- ^ 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

584
        tcg_th_used :: TcRef Bool,
585 586
          -- ^ @True@ <=> Template Haskell syntax used.
          --
587
          -- We need this so that we can generate a dependency on the
Gabor Greif's avatar
Gabor Greif committed
588
          -- Template Haskell package, because the desugarer is going
589 590
          -- to emit loads of references to TH symbols.  The reference
          -- is implicit rather than explicit, so we have to zap a
591 592
          -- mutable variable.

593 594 595 596 597
        tcg_th_splice_used :: TcRef Bool,
          -- ^ @True@ <=> A Template Haskell splice was used.
          --
          -- Splices disable recompilation avoidance (see #481)

598 599 600 601
        tcg_th_top_level_locs :: TcRef (Set RealSrcSpan),
          -- ^ Locations of the top-level splices; used for providing details on
          -- scope in error messages for out-of-scope variables

602
        tcg_dfun_n  :: TcRef OccSet,
603
          -- ^ Allows us to choose unique DFun names.
604

Edward Z. Yang's avatar
Edward Z. Yang committed
605 606 607 608
        tcg_merged :: [(Module, Fingerprint)],
          -- ^ The requirements we merged with; we always have to recompile
          -- if any of these changed.

609
        -- The next fields accumulate the payload of the module
Gabor Greif's avatar
Gabor Greif committed
610
        -- The binds, rules and foreign-decl fields are collected
611
        -- initially in un-zonked form and are finally zonked in tcRnSrcDecls
612

613
        tcg_rn_exports :: Maybe [(Located (IE GhcRn), Avails)],
614
                -- Nothing <=> no explicit export list
615
                -- Is always Nothing if we don't want to retain renamed
616 617 618
                -- exports.
                -- If present contains each renamed export list item
                -- together with its exported names.
619

620
        tcg_rn_imports :: [LImportDecl GhcRn],
621 622
                -- 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
623

624
        tcg_rn_decls :: Maybe (HsGroup GhcRn),
625 626
          -- ^ Renamed decls, maybe.  @Nothing@ <=> Don't retain renamed
          -- decls.
627

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

630
        tcg_th_topdecls :: TcRef [LHsDecl GhcPs],
631 632
        -- ^ Top-level declarations from addTopDecls

633
        tcg_th_foreign_files :: TcRef [(ForeignSrcLang, FilePath)],
634
        -- ^ Foreign files emitted from TH.
635

636 637
        tcg_th_topnames :: TcRef NameSet,
        -- ^ Exact names bound in top-level declarations in tcg_th_topdecls
638

639
        tcg_th_modfinalizers :: TcRef [(TcLclEnv, ThModFinalizers)],
640 641
        -- ^ Template Haskell module finalizers.
        --
642
        -- They can use particular local environments.
643

644 645 646
        tcg_th_coreplugins :: TcRef [String],
        -- ^ Core plugins added by Template Haskell code.

647
        tcg_th_state :: TcRef (Map TypeRep Dynamic),
648
        tcg_th_remote_state :: TcRef (Maybe (ForeignRef (IORef QState))),
649
        -- ^ Template Haskell state
650

651
        tcg_ev_binds  :: Bag EvBind,        -- Top-level evidence bindings
652

653 654 655
        -- 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
656
        tcg_tr_module :: Maybe Id,   -- Id for $trModule :: GHC.Types.Module
657 658
                                             -- for which every module has a top-level defn
                                             -- except in GHCi in which case we have Nothing
659
        tcg_binds     :: LHsBinds GhcTc,     -- Value bindings in this module
660 661 662 663 664 665 666
        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
667 668 669
        tcg_rules     :: [LRuleDecl GhcTc],  -- ...Rules
        tcg_fords     :: [LForeignDecl GhcTc], -- ...Foreign import & exports
        tcg_patsyns   :: [PatSyn],            -- ...Pattern synonyms
670

671
        tcg_doc_hdr   :: Maybe LHsDocString, -- ^ Maybe Haddock header docs
672
        tcg_hpc       :: !AnyHpcUsage,       -- ^ @True@ if any part of the
673
                                             --  prog uses hpc instrumentation.
674
           -- NB. BangPattern is to fix a leak, see #15111
675

676 677 678
        tcg_self_boot :: SelfBootInfo,       -- ^ Whether this module has a
                                             -- corresponding hi-boot file

679
        tcg_main      :: Maybe Name,         -- ^ The Name of the main
680 681
                                             -- function, if this module is
                                             -- the main module.
682

683 684 685 686 687
        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.

688
        tcg_tc_plugins :: [TcPluginSolver],
689
        -- ^ A list of user-defined plugins for the constraint solver.
690 691
        tcg_hf_plugins :: [HoleFitPlugin],
        -- ^ A list of user-defined plugins for hole fit suggestions.
692

Edward Z. Yang's avatar
Edward Z. Yang committed
693 694 695
        tcg_top_loc :: RealSrcSpan,
        -- ^ The RealSrcSpan this module came from

696 697
        tcg_static_wc :: TcRef WantedConstraints,
          -- ^ Wanted constraints of static forms.
698
        -- See Note [Constraints in static forms].
699 700 701 702
        tcg_complete_matches :: [CompleteMatch],

        -- ^ Tracking indices for cost centre annotations
        tcg_cc_st   :: TcRef CostCentreState
703
    }
Lemmih's avatar
Lemmih committed
704

Edward Z. Yang's avatar
Edward Z. Yang committed
705 706 707
-- NB: topModIdentity, not topModSemantic!
-- Definition sites of orphan identities will be identity modules, not semantic
-- modules.
708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729

-- Note [Constraints in static forms]
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
--
-- When a static form produces constraints like
--
-- f :: StaticPtr (Bool -> String)
-- f = static show
--
-- we collect them in tcg_static_wc and resolve them at the end
-- of type checking. They need to be resolved separately because
-- we don't want to resolve them in the context of the enclosing
-- expression. Consider
--
-- g :: Show a => StaticPtr (a -> String)
-- g = static show
--
-- If the @Show a0@ constraint that the body of the static form produces was
-- resolved in the context of the enclosing expression, then the body of the
-- static form wouldn't be closed because the Show dictionary would come from
-- g's context instead of coming from the top level.

730 731 732 733
tcVisibleOrphanMods :: TcGblEnv -> ModuleSet
tcVisibleOrphanMods tcg_env
    = mkModuleSet (tcg_mod tcg_env : imp_orphs (tcg_imports tcg_env))

734
instance ContainsModule TcGblEnv where
Edward Z. Yang's avatar
Edward Z. Yang committed
735
    extractModule env = tcg_semantic_mod env
736

737 738 739
type RecFieldEnv = NameEnv [FieldLabel]
        -- Maps a constructor name *in this module*
        -- to the fields for that constructor.
740 741 742 743 744
        -- 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
745

746 747 748 749
data SelfBootInfo
  = NoSelfBoot    -- No corresponding hi-boot file
  | SelfBoot
       { sb_mds :: ModDetails   -- There was a hi-boot file,
750 751 752 753
       , sb_tcs :: NameSet }    -- defining these TyCons,
-- What is sb_tcs used for?  See Note [Extra dependencies from .hs-boot files]
-- in RnSource

754

755 756 757 758
{- Note [Tracking unused binding and imports]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
We gather two sorts of usage information

759 760 761 762 763 764 765 766
 * 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)
767
   This usage info is mainly gathered by the renamer's
768 769
   gathering of free-variables

770
 * tcg_used_gres
771
      Used only to report unused import declarations
772 773 774 775 776 777 778

      Records each *occurrence* an *imported* (not locally-defined) entity.
      The occurrence is recorded by keeping a GlobalRdrElt for it.
      These is not the GRE that is in the GlobalRdrEnv; rather it
      is recorded *after* the filtering done by pickGREs.  So it reflect
      /how that occurrence is in scope/.   See Note [GRE filtering] in
      RdrName.
779

780

781 782
************************************************************************
*                                                                      *
783
                The local typechecker environment
784 785
*                                                                      *
************************************************************************
786

Edward Z. Yang's avatar
Edward Z. Yang committed
787 788
Note [The Global-Env/Local-Env story]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
789
During type checking, we keep in the tcg_type_env
790 791
        * All types and classes
        * All Ids derived from types and classes (constructors, selectors)
792 793 794

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

Why?  Because they are now Ids not TcIds.  This final GlobalEnv is
798 799 800
        a) fed back (via the knot) to typechecking the
           unfoldings of interface signatures
        b) used in the ModDetails of this module
801
-}
802

803 804
data TcLclEnv           -- Changes as we move inside an expression
                        -- Discarded after typecheck/rename; not passed on to desugarer
805
  = TcLclEnv {
806
        tcl_loc        :: RealSrcSpan,     -- Source span
807
        tcl_ctxt       :: [ErrCtxt],       -- Error context, innermost on top
808
        tcl_tclvl      :: TcLevel,         -- Birthplace for new unification variables
809

810
        tcl_th_ctxt    :: ThStage,         -- Template Haskell context
811 812 813 814 815
        tcl_th_bndrs   :: ThBindEnv,       -- and binder info
            -- The ThBindEnv records the TH binding level of in-scope Names
            -- defined in this module (not imported)
            -- We can't put this info in the TypeEnv because it's needed
            -- (and extended) in the renamer, for untyed splices
816

817 818 819 820 821 822 823 824 825 826
        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
827
                --   occurrence constructor (Name.TvOcc)
828 829 830 831 832
                -- 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
833

834 835
        tcl_bndrs :: TcBinderStack,   -- Used for reporting relevant bindings,
                                      -- and for tidying types
836 837 838 839 840

        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.
841
                        -- Why mutable? see notes with tcGetGlobalTyCoVars
842

843 844
        tcl_lie  :: TcRef WantedConstraints,    -- Place to accumulate type constraints
        tcl_errs :: TcRef Messages              -- Place to accumulate errors
845 846
    }

847 848 849 850 851 852 853 854
type ErrCtxt = (Bool, TidyEnv -> TcM (TidyEnv, MsgDoc))
        -- Monadic so that we have a chance
        -- to deal with bound type variables just before error
        -- message construction

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

855
type TcTypeEnv = NameEnv TcTyThing
856

857 858 859 860 861 862 863 864 865
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

866 867
{- Note [Given Insts]
   ~~~~~~~~~~~~~~~~~~
868
Because of GADTs, we have to pass inwards the Insts provided by type signatures
869
and existential contexts. Consider
870 871 872
        data T a where { T1 :: b -> b -> T [b] }
        f :: Eq a => T a -> Bool
        f (T1 x y) = [x]==[y]
873 874

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

-}
879

880 881 882 883 884 885 886 887
-- | 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

888
---------------------------
889
-- The TcBinderStack
890 891
---------------------------

892 893 894 895 896
type TcBinderStack = [TcBinder]
   -- This is a stack of locally-bound ids and tyvars,
   --   innermost on top
   -- Used only in error reporting (relevantBindings in TcError),
   --   and in tidying
Simon Peyton Jones's avatar
Simon Peyton Jones committed
897 898
   -- We can't use the tcl_env type environment, because it doesn't
   --   keep track of the nesting order
899

900
data TcBinder
901 902
  = TcIdBndr
       TcId
903
       TopLevelFlag    -- Tells whether the binding is syntactically top-level
904 905
                       -- (The monomorphic Ids for a recursive group count
                       --  as not-top-level for this purpose.)
906

907 908 909 910 911
  | TcIdBndr_ExpType  -- Variant that allows the type to be specified as
                      -- an ExpType
       Name
       ExpType
       TopLevelFlag
912

913 914 915 916 917 918
  | TcTvBndr          -- e.g.   case x of P (y::a) -> blah
       Name           -- We bind the lexical name "a" to the type of y,
       TyVar          -- which might be an utterly different (perhaps
                      -- existential) tyvar

instance Outputable TcBinder where
919 920
   ppr (TcIdBndr id top_lvl)           = ppr id <> brackets (ppr top_lvl)
   ppr (TcIdBndr_ExpType id _ top_lvl) = ppr id <> brackets (ppr top_lvl)
921
   ppr (TcTvBndr name tv)              = ppr name <+> ppr tv
922

923 924 925 926
instance HasOccName TcBinder where
    occName (TcIdBndr id _)             = occName (idName id)
    occName (TcIdBndr_ExpType name _ _) = occName name
    occName (TcTvBndr name _)           = occName name
927

928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944
-- fixes #12177
-- Builds up a list of bindings whose OccName has not been seen before
-- i.e., If    ys  = removeBindingShadowing xs
-- then
--  - ys is obtained from xs by deleting some elements
--  - ys has no duplicate OccNames
--  - The first duplicated OccName in xs is retained in ys
-- Overloaded so that it can be used for both GlobalRdrElt in typed-hole
-- substitutions and TcBinder when looking for relevant bindings.
removeBindingShadowing :: HasOccName a => [a] -> [a]
removeBindingShadowing bindings = reverse $ fst $ foldl
    (\(bindingAcc, seenNames) binding ->
    if occName binding `elemOccSet` seenNames -- if we've seen it
        then (bindingAcc, seenNames)              -- skip it
        else (binding:bindingAcc, extendOccSet seenNames (occName binding)))
    ([], emptyOccSet) bindings

945
---------------------------
946
-- Template Haskell stages and levels
947 948
---------------------------

949 950
data SpliceType = Typed | Untyped

951
data ThStage    -- See Note [Template Haskell state diagram] in TcSplice
952 953 954 955
  = Splice SpliceType -- Inside a top-level splice
                      -- This code will be run *at compile time*;
                      --   the result replaces the splice
                      -- Binding level = 0
956

957 958 959 960 961 962 963 964 965 966 967 968 969 970 971
  | RunSplice (TcRef [ForeignRef (TH.Q ())])
      -- Set when running a splice, i.e. NOT when renaming or typechecking the
      -- Haskell code for the splice. See Note [RunSplice ThLevel].
      --
      -- Contains a list of mod finalizers collected while executing the splice.
      --
      -- 'addModFinalizer' inserts finalizers here, and from here they are taken
      -- to construct an @HsSpliced@ annotation for untyped splices. See Note
      -- [Delaying modFinalizers in untyped splices] in "RnSplice".
      --
      -- For typed splices, the typechecker takes finalizers from here and
      -- inserts them in the list of finalizers in the global environment.
      --
      -- See Note [Collecting modFinalizers in typed splices] in "TcSplice".

972 973
  | Comp        -- Ordinary Haskell code
                -- Binding level = 1
974

975
  | Brack                       -- Inside brackets
976 977 978 979 980 981 982 983 984
      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

985
  | TcPending                     -- Typechecking the inside of a typed bracket
986 987
      (TcRef [PendingTcSplice])   --   Accumulate pending splices here
      (TcRef WantedConstraints)   --     and type constraints here
988 989 990

topStage, topAnnStage, topSpliceStage :: ThStage
topStage       = Comp
991 992
topAnnStage    = Splice Untyped
topSpliceStage = Splice Untyped
993 994

instance Outputable ThStage where
995 996 997 998
   ppr (Splice _)    = text "Splice"
   ppr (RunSplice _) = text "RunSplice"
   ppr Comp          = text "Comp"
   ppr (Brack s _)   = text "Brack" <> parens (ppr s)
999

1000
type ThLevel = Int
1001 1002 1003 1004 1005
    -- 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
1006

1007
impLevel, outerLevel :: ThLevel
1008 1009
impLevel = 0    -- Imported things; they can be used inside a top level splice
outerLevel = 1  -- Things defined outside brackets
1010

1011
thLevel :: ThStage -> ThLevel
1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026
thLevel (Splice _)    = 0
thLevel (RunSplice _) =
    -- See Note [RunSplice ThLevel].
    panic "thLevel: called when running a splice"
thLevel Comp          = 1
thLevel (Brack s _)   = thLevel s + 1

{- Node [RunSplice ThLevel]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The 'RunSplice' stage is set when executing a splice, and only when running a
splice. In particular it is not set when the splice is renamed or typechecked.

'RunSplice' is needed to provide a reference where 'addModFinalizer' can insert
the finalizer (see Note [Delaying modFinalizers in untyped splices]), and
'addModFinalizer' runs when doing Q things. Therefore, It doesn't make sense to
1027
set 'RunSplice' when renaming or typechecking the splice, where 'Splice',
1028
'Brack' or 'Comp' are used instead.
1029 1030

-}
1031

1032 1033 1034 1035
---------------------------
-- Arrow-notation context
---------------------------

1036 1037
{- Note [Escaping the arrow scope]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1038 1039 1040 1041
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

1042
        proc x -> (e1 -< e2)
1043 1044 1045 1046

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

1047 1048
        let x = 3 in
        proc y -> (proc z -> e1) -< e2
1049

1050
Here, x and z are in scope in e1, but y is not.
1051 1052

We implement this by
1053 1054 1055
recording the environment when passing a proc (using newArrowScope),
and returning to that (using escapeArrowScope) on the left of -< and the
head of (|..|).
1056

1057 1058 1059 1060 1061 1062 1063 1064 1065 1066
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.
1067 1068
-}

1069
data ArrowCtxt   -- Note [Escaping the arrow scope]
1070
  = NoArrowCtxt
1071 1072
  | ArrowCtxt LocalRdrEnv (TcRef WantedConstraints)

1073

1074 1075 1076 1077
---------------------------
-- TcTyThing
---------------------------

Edward Z. Yang's avatar
Edward Z. Yang committed
1078 1079 1080
-- | 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'.
1081
data TcTyThing
1082
  = AGlobal TyThing             -- Used only in the return type of a lookup
1083

1084 1085 1086 1087
  | ATcId           -- Ids defined in this module; may not be fully zonked
      { tct_id   :: TcId
      , tct_info :: IdBindingInfo   -- See Note [Meaning of IdBindingInfo]
      }
1088

1089
  | ATyVar  Name TcTyVar   -- See Note [Type variables in the type environment]
1090

1091
  | ATcTyCon TyCon   -- Used temporarily, during kind checking, for the
1092
                     -- tycons and clases in this recursive group
1093 1094
                     -- The TyCon is always a TcTyCon.  Its kind
                     -- can be a mono-kind or a poly-kind; in TcTyClsDcls see
dreixel's avatar
dreixel committed
1095 1096
                     -- Note [Type checking recursive type and class declarations]

1097
  | APromotionErr PromotionErr
1098

1099
data PromotionErr
1100 1101 1102 1103 1104
  = TyConPE          -- TyCon used in a kind before we are ready
                     --     data T :: T -> * where ...
  | ClassPE          -- Ditto Class

  | FamDataConPE     -- Data constructor for a data family
1105 1106
                     -- See Note [AFamDataCon: not promoting data family constructors]
                     -- in TcEnv.
1107 1108 1109 1110
  | ConstrainedDataConPE PredType
                     -- Data constructor with a non-equality context
                     -- See Note [Don't promote data constructors with
                     --           non-equality contexts] in TcHsType
1111 1112
  | PatSynPE         -- Pattern synonyms
                     -- See Note [Don't promote pattern synonyms] in TcEnv
dreixel's avatar
dreixel committed
1113

Krzysztof Gogolewski's avatar
Krzysztof Gogolewski committed
1114
  | RecDataConPE     -- Data constructor in a recursive loop
1115
                     -- See Note [Recursion and promoting data constructors] in TcTyClsDecls
1116 1117
  | NoDataKindsTC    -- -XDataKinds not enabled (for a tycon)
  | NoDataKindsDC    -- -XDataKinds not enabled (for a datacon)
1118

1119
instance Outputable TcTyThing where     -- Debugging only
1120
   ppr (AGlobal g)      = ppr g
1121 1122
   ppr elt@(ATcId {})   = text "Identifier" <>
                          brackets (ppr (tct_id elt) <> dcolon
1123
                                 <> ppr (varType (tct_id elt)) <> comma
1124
                                 <+> ppr (tct_info elt))
1125
   ppr (ATyVar n tv)    = text "Type variable" <+> quotes (ppr n) <+> equals <+> ppr tv
1126
                            <+> dcolon <+> ppr (varType tv)
1127
   ppr (ATcTyCon tc)    = text "ATcTyCon" <+> ppr tc <+> dcolon <+> ppr (tyConKind tc)
1128 1129
   ppr (APromotionErr err) = text "APromotionErr" <+> ppr err

1130
-- | IdBindingInfo describes how an Id is bound.
1131 1132 1133
--
-- It is used for the following purposes:
-- a) for static forms in TcExpr.checkClosedInStaticForm and
1134 1135
-- b) to figure out when a nested binding can be generalised,
--    in TcBinds.decideGeneralisationPlan.
1136
--
1137
data IdBindingInfo -- See Note [Meaning of IdBindingInfo and ClosedTypeId]
1138 1139
    = NotLetBound
    | ClosedLet
1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188
    | NonClosedLet
         RhsNames        -- Used for (static e) checks only
         ClosedTypeId    -- Used for generalisation checks
                         -- and for (static e) checks

-- | IsGroupClosed describes a group of mutually-recursive bindings
data IsGroupClosed
  = IsGroupClosed
      (NameEnv RhsNames)  -- Free var info for the RHS of each binding in the goup
                          -- Used only for (static e) checks

      ClosedTypeId        -- True <=> all the free vars of the group are
                          --          imported or ClosedLet or
                          --          NonClosedLet with ClosedTypeId=True.
                          --          In particular, no tyvars, no NotLetBound

type RhsNames = NameSet   -- Names of variables, mentioned on the RHS of
                          -- a definition, that are not Global or ClosedLet

type ClosedTypeId = Bool
  -- See Note [Meaning of IdBindingInfo and ClosedTypeId]

{- Note [Meaning of IdBindingInfo]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
NotLetBound means that
  the Id is not let-bound (e.g. it is bound in a
  lambda-abstraction or in a case pattern)

ClosedLet means that
   - The Id is let-bound,
   - Any free term variables are also Global or ClosedLet
   - Its type has no free variables (NB: a top-level binding subject
     to the MR might have free vars in its type)
   These ClosedLets can definitely be floated to top level; and we
   may need to do so for static forms.

   Property:   ClosedLet
             is equivalent to
               NonClosedLet emptyNameSet True

(NonClosedLet (fvs::RhsNames) (cl::ClosedTypeId)) means that
   - The Id is let-bound

   - The fvs::RhsNames contains the free names of the RHS,
     excluding Global and ClosedLet ones.

   - For the ClosedTypeId field see Note [Bindings with closed types]

For (static e) to be valid, we need for every 'x' free in 'e',
1189 1190
that x's binding is floatable to the top level.  Specifically:
   * x's RhsNames must be empty
1191 1192 1193 1194 1195 1196 1197 1198 1199
   * x's type has no free variables
See Note [Grand plan for static forms] in StaticPtrTable.hs.
This test is made in TcExpr.checkClosedInStaticForm.
Actually knowing x's RhsNames (rather than just its emptiness
or otherwise) is just so we can produce better error messages

Note [Bindings with closed types: ClosedTypeId]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Consider
1200

1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214
  f x = let g ys = map not ys
        in ...

Can we generalise 'g' under the OutsideIn algorithm?  Yes,
because all g's free variables are top-level; that is they themselves
have no free type variables, and it is the type variables in the
environment that makes things tricky for OutsideIn generalisation.

Here's the invariant:
   If an Id has ClosedTypeId=True (in its IdBindingInfo), then
   the Id's type is /definitely/ closed (has no free type variables).
   Specifically,
       a) The Id's acutal type is closed (has no free tyvars)
       b) Either the Id has a (closed) user-supplied type signature
Gabor Greif's avatar
Gabor Greif committed
1215
          or all its free variables are Global/ClosedLet
1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252
             or NonClosedLet with ClosedTypeId=True.
          In particular, none are NotLetBound.

Why is (b) needed?   Consider
    \x. (x :: Int, let y = x+1 in ...)
Initially x::alpha.  If we happen to typecheck the 'let' before the
(x::Int), y's type will have a free tyvar; but if the other way round
it won't.  So we treat any let-bound variable with a free
non-let-bound variable as not ClosedTypeId, regardless of what the
free vars of its type actually are.

But if it has a signature, all is well:
   \x. ...(let { y::Int; y = x+1 } in
           let { v = y+2 } in ...)...
Here the signature on 'v' makes 'y' a ClosedTypeId, so we can
generalise 'v'.

Note that:

  * A top-level binding may not have ClosedTypeId=True, if it suffers
    from the MR

  * 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 or nested is orthogonal to the question of whether or
    not it is closed.

  * 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)...

Under OutsideIn we are free to generalise an Id all of whose free
variables have ClosedTypeId=True (or imported).  This is an extension
compared to the JFP paper on OutsideIn, which used "top-level" as a
proxy for "closed".  (It's not a good proxy anyway -- the MR can make
a top-level binding with a free type variable.)
1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294

Note [Type variables in the type environment]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The type environment has a binding for each lexically-scoped
type variable that is in scope.  For example

  f :: forall a. a -> a
  f x = (x :: a)

  g1 :: [a] -> a
  g1 (ys :: [b]) = head ys :: b

  g2 :: [Int] -> Int
  g2 (ys :: [c]) = head ys :: c

* The forall'd variable 'a' in the signature scopes over f's RHS.

* The pattern-bound type variable 'b' in 'g1' scopes over g1's
  RHS; note that it is bound to a skolem 'a' which is not itself
  lexically in scope.

* The pattern-bound type variable 'c' in 'g2' is bound to
  Int; that is, pattern-bound type variables can stand for
  arbitrary types. (see
    GHC proposal #128 "Allow ScopedTypeVariables to refer to types"
    https://github.com/ghc-proposals/ghc-proposals/pull/128,
  and the paper
    "Type variables in patterns", Haskell Symposium 2018.


This is implemented by the constructor
   ATyVar Name TcTyVar
in the type environment.

* The Name is the name of the original, lexically scoped type
  variable

* The TcTyVar is sometimes a skolem (like in 'f'), and sometimes
  a unification variable (like in 'g1', 'g2').  We never zonk the
  type environment so in the latter case it always stays as a
  unification variable, although that variable may be later
  unified with a type (such as Int in 'g2').
1295
-}
1296 1297 1298 1299 1300 1301 1302

instance Outputable IdBindingInfo where
  ppr NotLetBound = text "NotLetBound"
  ppr ClosedLet = text "TopLevelLet"
  ppr (NonClosedLet fvs closed_type) =
    text "TopLevelLet" <+> ppr fvs <+> ppr closed_type

1303
instance Outputable PromotionErr where
1304 1305 1306 1307 1308 1309 1310 1311 1312
  ppr ClassPE                     = text "ClassPE"
  ppr TyConPE                     = text "TyConPE"
  ppr PatSynPE                    = text "PatSynPE"
  ppr FamDataConPE                = text "FamDataConPE"
  ppr (ConstrainedDataConPE pred) = text "ConstrainedDataConPE"
                                      <+> parens (ppr pred)
  ppr RecDataConPE                = text "RecDataConPE"
  ppr NoDataKindsTC               = text "NoDataKindsTC"
  ppr NoDataKindsDC               = text "NoDataKindsDC"
1313 1314

pprTcTyThingCategory :: TcTyThing -> SDoc
1315
pprTcTyThingCategory (AGlobal thing)    = pprTyThingCategory thing
1316 1317 1318
pprTcTyThingCategory (ATyVar {})        = text "Type variable"
pprTcTyThingCategory (ATcId {})         = text "Local identifier"
pprTcTyThingCategory (ATcTyCon {})     = text "Local tycon"
1319 1320 1321
pprTcTyThingCategory (APromotionErr pe) = pprPECategory pe

pprPECategory :: PromotionErr -> SDoc
1322 1323 1324 1325 1326 1327 1328 1329
pprPECategory ClassPE                = text "Class"
pprPECategory TyConPE                = text "Type constructor"
pprPECategory PatSynPE               = text "Pattern synonym"
pprPECategory FamDataConPE           = text "Data constructor"
pprPECategory ConstrainedDataConPE{} = text "Data constructor"
pprPECategory RecDataConPE           = text "Data constructor"
pprPECategory NoDataKindsTC          = text "Type constructor"
pprPECategory NoDataKindsDC          = text "Data constructor"
1330

1331 1332 1333
{-
************************************************************************
*                                                                      *
1334
        Operations over ImportAvails
1335 1336 1337
*                                                                      *