TcRnTypes.lhs 62.5 KB
Newer Older
1

Gabor Greif's avatar
Gabor Greif committed
2
% (c) The University of Glasgow 2006-2012
3 4
% (c) The GRASP Project, Glasgow University, 1992-2002
%
5 6 7 8 9 10 11 12 13 14 15 16 17

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.

18 19
\begin{code}
module TcRnTypes(
20 21
        TcRnIf, TcRn, TcM, RnM, IfM, IfL, IfG, -- The monad is opaque outside this module
        TcRef,
22

23 24 25 26
        -- The environment types
        Env(..),
        TcGblEnv(..), TcLclEnv(..),
        IfGblEnv(..), IfLclEnv(..),
27

28 29 30 31
        -- Ranamer types
        ErrCtxt, RecFieldEnv(..),
        ImportAvails(..), emptyImportAvails, plusImportAvails,
        WhereFrom(..), mkModDeps,
32

33 34
        -- Typechecker types
        TcTypeEnv, TcIdBinder(..), TcTyThing(..), PromotionErr(..),
35
        pprTcTyThingCategory, pprPECategory,
36

37 38 39
        -- Template Haskell
        ThStage(..), topStage, topAnnStage, topSpliceStage,
        ThLevel, impLevel, outerLevel, thLevel,
40

41 42
        -- Arrows
        ArrowCtxt(NoArrowCtxt), newArrowScope, escapeArrowScope,
ross's avatar
ross committed
43

44
        -- Canonical constraints
45
        Xi, Ct(..), Cts, emptyCts, andCts, andManyCts, dropDerivedWC,
46
        singleCt, extendCts, isEmptyCts, isCTyEqCan, isCFunEqCan,
47
        isCDictCan_Maybe, isCFunEqCan_Maybe,
48
        isCIrredEvCan, isCNonCanonical, isWantedCt, isDerivedCt,
49
        isGivenCt, isHoleCt,
50
        ctEvidence,
51
        SubGoalDepth, mkNonCanonical, mkNonCanonicalCt,
52
        ctPred, ctEvPred, ctEvTerm, ctEvId,
53

54
        WantedConstraints(..), insolubleWC, emptyWC, isEmptyWC,
55
        andWC, unionsWC, addFlats, addImplics, mkFlatWC, addInsols,
56 57

        Implication(..),
58
        CtLoc(..), ctLocSpan, ctLocEnv, ctLocOrigin,
59
        ctLocDepth, bumpCtLocDepth,
60
        setCtLocOrigin, setCtLocEnv,
61
        CtOrigin(..),
62
        pushErrCtxt, pushErrCtxtSameOrigin,
63

64
        SkolemInfo(..),
65

66
        CtEvidence(..),
67 68
        mkGivenLoc,
        isWanted, isGiven,
69
        isDerived, canSolve, canRewrite,
Simon Peyton Jones's avatar
Simon Peyton Jones committed
70
        CtFlavour(..), ctEvFlavour, ctFlavour,
71

72
        -- Pretty printing
73
        pprEvVarTheta, pprWantedsWithLocs,
74
        pprEvVars, pprEvVarWithType,
75
        pprArising, pprArisingAt,
76

77 78 79
        -- Misc other types
        TcId, TcIdSet, TcTyVarBind(..), TcTyVarBinds

80 81 82 83
  ) where

#include "HsVersions.h"

84
import HsSyn
85
import HscTypes
86
import TcEvidence
87
import Type
88
import Class    ( Class )
89
import TyCon    ( TyCon )
90
import DataCon  ( DataCon, dataConUserType )
91
import TcType
92
import Annotations
93 94
import InstEnv
import FamInstEnv
95
import IOEnv
96 97
import RdrName
import Name
98
import NameEnv
99
import NameSet
100
import Avail
101 102
import Var
import VarEnv
103
import Module
104 105 106
import SrcLoc
import VarSet
import ErrUtils
107
import UniqFM
108 109
import UniqSupply
import BasicTypes
110
import Bag
Ian Lynagh's avatar
Ian Lynagh committed
111
import DynFlags
112
import Outputable
113
import ListSetOps
114
import FastString
115

116
import Data.Set (Set)
117 118 119 120
\end{code}


%************************************************************************
121 122
%*                                                                      *
               Standard monad definition for TcRn
123
    All the combinators for the monad can be found in TcRnMonad
124
%*                                                                      *
125 126
%************************************************************************

127
The monad itself has to be defined here, because it is mentioned by ErrCtxt
128 129

\begin{code}
130 131 132
type TcRef a     = IORef a
type TcId        = Id
type TcIdSet     = IdSet
133

134

135
type TcRnIf a b c = IOEnv (Env a b) c
136
type IfM lcl a  = TcRnIf IfGblEnv lcl a         -- Iface stuff
Simon Marlow's avatar
Simon Marlow committed
137

138 139
type IfG a  = IfM () a                          -- Top level
type IfL a  = IfM IfLclEnv a                    -- Nested
140
type TcRn a = TcRnIf TcGblEnv TcLclEnv a
141 142
type RnM  a = TcRn a            -- Historical
type TcM  a = TcRn a            -- Historical
143 144
\end{code}

145 146 147 148 149 150 151 152 153 154 155 156
Representation of type bindings to uninstantiated meta variables used during
constraint solving.

\begin{code}
data TcTyVarBind = TcTyVarBind TcTyVar TcType

type TcTyVarBinds = Bag TcTyVarBind

instance Outputable TcTyVarBind where
  ppr (TcTyVarBind tv ty) = ppr tv <+> text ":=" <+> ppr ty
\end{code}

157 158

%************************************************************************
159 160 161
%*                                                                      *
                The main environment types
%*                                                                      *
162 163 164
%************************************************************************

\begin{code}
165 166 167 168
-- 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
169
  = Env {
170 171
        env_top  :: HscEnv,  -- Top-level stuff that never changes
                             -- Includes all info about imported things
172

173 174
        env_us   :: {-# UNPACK #-} !(IORef UniqSupply),
                             -- Unique supply for local varibles
175

176 177
        env_gbl  :: gbl,     -- Info about things defined at the top level
                             -- of the module being compiled
178

179
        env_lcl  :: lcl      -- Nested stuff; changes as we go into
180
    }
181

Ian Lynagh's avatar
Ian Lynagh committed
182 183
instance ContainsDynFlags (Env gbl lcl) where
    extractDynFlags env = hsc_dflags (env_top env)
184 185
    replaceDynFlags env dflags
        = env {env_top = replaceDynFlags (env_top env) dflags}
Ian Lynagh's avatar
Ian Lynagh committed
186

187 188 189
instance ContainsModule gbl => ContainsModule (Env gbl lcl) where
    extractModule env = extractModule (env_gbl env)

190
-- TcGblEnv describes the top-level of the module at the
191 192
-- point at which the typechecker is finished work.
-- It is this structure that is handed on to the desugarer
193 194
-- For state that needs to be updated during the typechecking
-- phase and returned at end, use a TcRef (= IORef).
195 196 197

data TcGblEnv
  = TcGblEnv {
198 199
        tcg_mod     :: Module,         -- ^ Module being compiled
        tcg_src     :: HscSource,
200
          -- ^ What kind of module (regular Haskell, hs-boot, ext-core)
201

202 203
        tcg_rdr_env :: GlobalRdrEnv,   -- ^ Top level envt; used during renaming
        tcg_default :: Maybe [Type],
204
          -- ^ Types used for defaulting. @Nothing@ => no @default@ decl
205

206 207
        tcg_fix_env   :: FixityEnv,     -- ^ Just for things in this module
        tcg_field_env :: RecFieldEnv,   -- ^ Just for things in this module
208

209
        tcg_type_env :: TypeEnv,
210
          -- ^ Global type env for the module we are compiling now.  All
211 212 213 214 215 216 217 218 219 220 221 222 223 224
          -- 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)

        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;
225
          -- Includes the dfuns in tcg_insts
226 227 228 229 230 231 232 233
        tcg_fam_inst_env :: FamInstEnv, -- ^ Ditto for family instances

                -- 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,
234
          -- ^ Information about what was imported from where, including
235
          -- things bound in this module. Also store Safe Haskell info
236
          -- here about transative trusted packaage requirements.
237

238 239 240
        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]
241

242
        tcg_keep :: TcRef NameSet,
243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260
          -- ^ 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

261
        tcg_th_used :: TcRef Bool,
262 263
          -- ^ @True@ <=> Template Haskell syntax used.
          --
264
          -- We need this so that we can generate a dependency on the
Gabor Greif's avatar
typos  
Gabor Greif committed
265
          -- Template Haskell package, because the desugarer is going
266 267
          -- to emit loads of references to TH symbols.  The reference
          -- is implicit rather than explicit, so we have to zap a
268 269
          -- mutable variable.

270 271 272 273 274
        tcg_th_splice_used :: TcRef Bool,
          -- ^ @True@ <=> A Template Haskell splice was used.
          --
          -- Splices disable recompilation avoidance (see #481)

275
        tcg_dfun_n  :: TcRef OccSet,
276
          -- ^ Allows us to choose unique DFun names.
277

278 279 280
        -- The next fields accumulate the payload of the module
        -- The binds, rules and foreign-decl fiels are collected
        -- initially in un-zonked form and are finally zonked in tcRnSrcDecls
281

282
        tcg_rn_exports :: Maybe [Located (IE Name)],
283
        tcg_rn_imports :: [LImportDecl Name],
284 285
                -- 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
286

287
        tcg_rn_decls :: Maybe (HsGroup Name),
288 289
          -- ^ Renamed decls, maybe.  @Nothing@ <=> Don't retain renamed
          -- decls.
290

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

293 294 295
        tcg_ev_binds  :: Bag EvBind,        -- Top-level evidence bindings
        tcg_binds     :: LHsBinds Id,       -- Value bindings in this module
        tcg_sigs      :: NameSet,           -- ...Top-level names that *lack* a signature
296
        tcg_imp_specs :: [LTcSpecPrag],     -- ...SPECIALISE prags for imported Ids
297 298
        tcg_warns     :: Warnings,          -- ...Warnings and deprecations
        tcg_anns      :: [Annotation],      -- ...Annotations
dreixel's avatar
dreixel committed
299
        tcg_tcs       :: [TyCon],           -- ...TyCons and Classes
300
        tcg_insts     :: [ClsInst],         -- ...Instances
301
        tcg_fam_insts :: [FamInst Branched],-- ...Family instances
302 303 304
        tcg_rules     :: [LRuleDecl Id],    -- ...Rules
        tcg_fords     :: [LForeignDecl Id], -- ...Foreign import & exports
        tcg_vects     :: [LVectDecl Id],    -- ...Vectorisation declarations
305

306
        tcg_doc_hdr   :: Maybe LHsDocString, -- ^ Maybe Haddock header docs
307 308 309
        tcg_hpc       :: AnyHpcUsage,        -- ^ @True@ if any part of the
                                             --  prog uses hpc instrumentation.

310
        tcg_main      :: Maybe Name,         -- ^ The Name of the main
311 312
                                             -- function, if this module is
                                             -- the main module.
313 314 315
        tcg_safeInfer :: TcRef Bool          -- Has the typechecker
                                             -- inferred this module
                                             -- as -XSafe (Safe Haskell)
316
    }
317

318 319 320
instance ContainsModule TcGblEnv where
    extractModule env = tcg_mod env

321 322 323 324 325 326 327 328 329 330 331 332
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
333 334
\end{code}

335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357
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)
   This usage info is mainly gathered by the renamer's 
   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
      is esssential in deciding whether a particular import decl 
      is unnecessary.  This info isn't present in Names.


358
%************************************************************************
359 360 361 362
%*                                                                      *
                The interface environments
              Used when dealing with IfaceDecls
%*                                                                      *
363 364 365
%************************************************************************

\begin{code}
366
data IfGblEnv
367
  = IfGblEnv {
368 369 370 371 372 373 374 375 376
        -- 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
377 378 379 380
    }

data IfLclEnv
  = IfLclEnv {
381 382 383 384 385 386 387 388 389 390 391 392 393 394 395
        -- 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
396 397 398
    }
\end{code}

399 400

%************************************************************************
401 402 403
%*                                                                      *
                The local typechecker environment
%*                                                                      *
404 405 406 407 408
%************************************************************************

The Global-Env/Local-Env story
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
During type checking, we keep in the tcg_type_env
409 410
        * All types and classes
        * All Ids derived from types and classes (constructors, selectors)
411 412 413

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

Why?  Because they are now Ids not TcIds.  This final GlobalEnv is
417 418 419
        a) fed back (via the knot) to typechecking the
           unfoldings of interface signatures
        b) used in the ModDetails of this module
420 421

\begin{code}
422 423
data TcLclEnv           -- Changes as we move inside an expression
                        -- Discarded after typecheck/rename; not passed on to desugarer
424
  = TcLclEnv {
425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444
        tcl_loc        :: SrcSpan,         -- Source span
        tcl_ctxt       :: [ErrCtxt],       -- Error context, innermost on top
        tcl_untch      :: Untouchables,    -- Birthplace for new unification variables
        tcl_th_ctxt    :: ThStage,         -- Template Haskell context
        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
445 446 447

        tcl_bndrs :: [TcIdBinder],   -- Stack of locally-bound Ids, innermost on top
                                     -- Used only for error reporting
448 449 450

        tcl_tidy :: TidyEnv,      -- Used for tidying types; contains all
                                  -- in-scope type variables (but not term variables)
451 452 453 454 455

        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.
456 457
                        -- Why mutable? see notes with tcGetGlobalTyVars

458 459
        tcl_lie  :: TcRef WantedConstraints,    -- Place to accumulate type constraints
        tcl_errs :: TcRef Messages              -- Place to accumulate errors
460 461
    }

462
type TcTypeEnv = NameEnv TcTyThing
463
data TcIdBinder = TcIdBndr TcId TopLevelFlag
464

465 466
{- Note [Given Insts]
   ~~~~~~~~~~~~~~~~~~
467
Because of GADTs, we have to pass inwards the Insts provided by type signatures
468
and existential contexts. Consider
469 470 471
        data T a where { T1 :: b -> b -> T [b] }
        f :: Eq a => T a -> Bool
        f (T1 x y) = [x]==[y]
472 473

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

-}
478

479
---------------------------
480
-- Template Haskell stages and levels
481 482
---------------------------

483 484 485 486 487 488 489 490
data ThStage    -- See Note [Template Haskell state diagram] in TcSplice
  = Splice      -- Top-level splicing
                -- This code will be run *at compile time*;
                --   the result replaces the splice
                -- Binding level = 0

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

492 493 494 495
  | Brack                       -- Inside brackets
      ThStage                   --   Binding level = level(stage) + 1
      (TcRef [PendingSplice])   --   Accumulate pending splices here
      (TcRef WantedConstraints) --     and type constraints here
496 497 498 499 500 501 502 503

topStage, topAnnStage, topSpliceStage :: ThStage
topStage       = Comp
topAnnStage    = Splice
topSpliceStage = Splice

instance Outputable ThStage where
   ppr Splice        = text "Splice"
504
   ppr Comp          = text "Comp"
505 506
   ppr (Brack s _ _) = text "Brack" <> parens (ppr s)

507
type ThLevel = Int
508
        -- See Note [Template Haskell levels] in TcSplice
509 510 511 512
        -- 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
513

514
impLevel, outerLevel :: ThLevel
515 516
impLevel = 0    -- Imported things; they can be used inside a top level splice
outerLevel = 1  -- Things defined outside brackets
517
-- NB: Things at level 0 are not *necessarily* imported.
518
--      eg  $( \b -> ... )   here b is bound at level 0
519
--
520 521 522 523
-- For example:
--      f = ...
--      g1 = $(map ...)         is OK
--      g2 = $(f ...)           is not OK; because we havn't compiled f yet
524

525 526 527 528
thLevel :: ThStage -> ThLevel
thLevel Splice        = 0
thLevel Comp          = 1
thLevel (Brack s _ _) = thLevel s + 1
529

ross's avatar
ross committed
530 531 532 533
---------------------------
-- Arrow-notation context
---------------------------

534 535
{- Note [Escaping the arrow scope]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ross's avatar
ross committed
536 537 538 539
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

540
        proc x -> (e1 -< e2)
ross's avatar
ross committed
541 542 543 544

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

545 546
        let x = 3 in
        proc y -> (proc z -> e1) -< e2
ross's avatar
ross committed
547

548
Here, x and z are in scope in e1, but y is not.
549 550

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

555
All this can be dealt with by the *renamer*; by the time we get to
556
the *type checker* we have sorted out the scopes
ross's avatar
ross committed
557 558
-}

ross's avatar
ross committed
559 560 561
data ArrowCtxt
  = NoArrowCtxt
  | ArrowCtxt (Env TcGblEnv TcLclEnv)
ross's avatar
ross committed
562 563 564 565 566

-- Record the current environment (outside a proc)
newArrowScope :: TcM a -> TcM a
newArrowScope
  = updEnv $ \env ->
567
        env { env_lcl = (env_lcl env) { tcl_arrow_ctxt = ArrowCtxt env } }
ross's avatar
ross committed
568 569 570

-- Return to the stored environment (from the enclosing proc)
escapeArrowScope :: TcM a -> TcM a
ross's avatar
ross committed
571 572
escapeArrowScope
  = updEnv $ \ env -> case tcl_arrow_ctxt (env_lcl env) of
573 574
        NoArrowCtxt -> env
        ArrowCtxt env' -> env'
575

576 577 578 579
---------------------------
-- TcTyThing
---------------------------

580
data TcTyThing
581
  = AGlobal TyThing             -- Used only in the return type of a lookup
582

583 584 585 586
  | ATcId   {           -- Ids defined in this module; may not be fully zonked
        tct_id     :: TcId,
        tct_closed :: TopLevelFlag,   -- See Note [Bindings with closed types]
        tct_level  :: ThLevel }
587

588 589 590 591
  | 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
592

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

598
  | APromotionErr PromotionErr
599

600
data PromotionErr
601 602 603 604 605
  = TyConPE          -- TyCon used in a kind before we are ready
                     --     data T :: T -> * where ...
  | ClassPE          -- Ditto Class

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

608
  | RecDataConPE     -- Data constructor in a reuursive loop
609
                     -- See Note [ARecDataCon: recusion and promoting data constructors] in TcTyClsDecls
610
  | NoDataKinds      -- -XDataKinds not enabled
611

612
instance Outputable TcTyThing where     -- Debugging only
613
   ppr (AGlobal g)      = pprTyThing g
614 615
   ppr elt@(ATcId {})   = text "Identifier" <>
                          brackets (ppr (tct_id elt) <> dcolon
616
                                 <> ppr (varType (tct_id elt)) <> comma
617 618
                                 <+> ppr (tct_closed elt) <> comma
                                 <+> ppr (tct_level elt))
Simon Peyton Jones's avatar
Simon Peyton Jones committed
619
   ppr (ATyVar n tv)    = text "Type variable" <+> quotes (ppr n) <+> equals <+> ppr tv
620
   ppr (AThing k)       = text "AThing" <+> ppr k
621 622 623 624 625 626 627
   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"
628
  ppr NoDataKinds  = text "NoDataKinds"
629 630

pprTcTyThingCategory :: TcTyThing -> SDoc
631 632 633 634 635 636 637 638 639 640 641
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")
642
pprPECategory NoDataKinds  = ptext (sLit "Data constructor")
643 644
\end{code}

645

646 647
Note [Bindings with closed types]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
648 649 650 651 652
Consider

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

653
Can we generalise 'g' under the OutsideIn algorithm?  Yes,
dreixel's avatar
dreixel committed
654
because all g's free variables are top-level; that is they themselves
655 656 657 658 659 660
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,
661
      iff
662 663 664 665 666
   a) all its free variables are imported, or are themselves closed
   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
667
used "top-level" as a proxy for "closed".  (It's not a good proxy
668 669 670 671 672 673 674 675
anyway -- the MR can make a top-level binding with a free type
variable.)

Note that:
  * A top-level binding may not be closed, if it suffer 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
676
    or nested is orthogonal to the question of whether or not it is closed
677 678 679 680 681 682

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

683

684
\begin{code}
685
type ErrCtxt = (Bool, TidyEnv -> TcM (TidyEnv, MsgDoc))
686 687 688
        -- Monadic so that we have a chance
        -- to deal with bound type variables just before error
        -- message construction
689

690 691
        -- Bool:  True <=> this is a landmark context; do not
        --                 discard it when trimming for display
692 693 694 695
\end{code}


%************************************************************************
696 697 698
%*                                                                      *
        Operations over ImportAvails
%*                                                                      *
699 700 701
%************************************************************************

\begin{code}
702 703 704 705 706 707 708 709 710 711 712 713
-- | '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
--
714
data ImportAvails
715
   = ImportAvails {
716 717
        imp_mods :: ImportedMods,
          --      = ModuleEnv [(ModuleName, Bool, SrcSpan, Bool)],
718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742
          -- ^ 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
          --       file; if we import somethign we need to recompile if the
          --       export version changes
          --
          --   (b) to specify what child modules to initialise
          --
          -- We need a full ModuleEnv rather than a ModuleNameEnv here,
          -- because we might be importing modules of the same name from
          -- different packages. (currently not the case, but might be in the
          -- future).
743

744 745 746 747 748 749 750 751 752 753 754
        imp_dep_mods :: ModuleNameEnv (ModuleName, IsBootInterface),
          -- ^ Home-package modules needed by the module being compiled
          --
          -- It doesn't matter whether any of these dependencies
          -- are actually /used/ when compiling the module; they
          -- are listed if they are below it at all.  For
          -- example, suppose M imports A which imports X.  Then
          -- compiling M might not need to consult X.hi, but X
          -- is still listed in M's dependencies.

        imp_dep_pkgs :: [PackageId],
755 756 757
          -- ^ Packages needed by the module being compiled, whether directly,
          -- or via other modules in this package, or via modules imported
          -- from other packages.
758

759 760 761 762 763 764 765 766 767
        imp_trust_pkgs :: [PackageId],
          -- ^ This is strictly a subset of imp_dep_pkgs and records the
          -- packages the current module needs to trust for Safe Haskell
          -- compilation to succeed. A package is required to be trusted if
          -- we are dependent on a trustworthy module in that package.
          -- While perhaps making imp_dep_pkgs a tuple of (PackageId, Bool)
          -- where True for the bool indicates the package is required to be
          -- trusted is the more logical  design, doing so complicates a lot
          -- of code not concerned with Safe Haskell.
768
          -- See Note [RnNames . Tracking Trust Transitively]
769

770 771 772 773 774 775 776
        imp_trust_own_pkg :: Bool,
          -- ^ Do we require that our own package is trusted?
          -- This is to handle efficiently the case where a Safe module imports
          -- a Trustworthy module that resides in the same package as it.
          -- See Note [RnNames . Trust Own Package]

        imp_orphs :: [Module],
777 778
          -- ^ Orphan modules below us in the import tree (and maybe including
          -- us for imported modules)
779

780
        imp_finsts :: [Module]
781 782
          -- ^ Family instance modules below us in the import tree (and maybe
          -- including us for imported modules)
783 784
      }

Simon Marlow's avatar
Simon Marlow committed
785
mkModDeps :: [(ModuleName, IsBootInterface)]
786
          -> ModuleNameEnv (ModuleName, IsBootInterface)
Simon Marlow's avatar
Simon Marlow committed
787
mkModDeps deps = foldl add emptyUFM deps
788 789
               where
                 add env elt@(m,_) = addToUFM env m elt
790

791
emptyImportAvails :: ImportAvails
792 793 794 795 796 797 798 799 800 801 802
emptyImportAvails = ImportAvails { imp_mods          = emptyModuleEnv,
                                   imp_dep_mods      = emptyUFM,
                                   imp_dep_pkgs      = [],
                                   imp_trust_pkgs    = [],
                                   imp_trust_own_pkg = False,
                                   imp_orphs         = [],
                                   imp_finsts        = [] }

-- | Union two ImportAvails
--
-- This function is a key part of Import handling, basically
Gabor Greif's avatar
Gabor Greif committed
803
-- for each import we create a separate ImportAvails structure
804
-- and then union them all together with this function.
805 806
plusImportAvails ::  ImportAvails ->  ImportAvails ->  ImportAvails
plusImportAvails
807
  (ImportAvails { imp_mods = mods1,
808 809
                  imp_dep_mods = dmods1, imp_dep_pkgs = dpkgs1,
                  imp_trust_pkgs = tpkgs1, imp_trust_own_pkg = tself1,
810 811
                  imp_orphs = orphs1, imp_finsts = finsts1 })
  (ImportAvails { imp_mods = mods2,
812 813
                  imp_dep_mods = dmods2, imp_dep_pkgs = dpkgs2,
                  imp_trust_pkgs = tpkgs2, imp_trust_own_pkg = tself2,
814
                  imp_orphs = orphs2, imp_finsts = finsts2 })
815 816 817 818 819 820 821
  = ImportAvails { imp_mods          = plusModuleEnv_C (++) mods1 mods2,
                   imp_dep_mods      = plusUFM_C plus_mod_dep dmods1 dmods2,
                   imp_dep_pkgs      = dpkgs1 `unionLists` dpkgs2,
                   imp_trust_pkgs    = tpkgs1 `unionLists` tpkgs2,
                   imp_trust_own_pkg = tself1 || tself2,
                   imp_orphs         = orphs1 `unionLists` orphs2,
                   imp_finsts        = finsts1 `unionLists` finsts2 }
822
  where
823
    plus_mod_dep (m1, boot1) (m2, boot2)
824 825 826
        = WARN( not (m1 == m2), (ppr m1 <+> ppr m2) $$ (ppr boot1 <+> ppr boot2) )
                -- Check mod-names match
          (m1, boot1 && boot2) -- If either side can "see" a non-hi-boot interface, use that
827 828 829
\end{code}

%************************************************************************
830
%*                                                                      *
831
\subsection{Where from}
832
%*                                                                      *
833 834 835 836 837
%************************************************************************

The @WhereFrom@ type controls where the renamer looks for an interface file

\begin{code}
838 839 840
data WhereFrom
  = ImportByUser IsBootInterface        -- Ordinary user import (perhaps {-# SOURCE #-})
  | ImportBySystem                      -- Non user import.
841 842
  | ImportByPlugin                      -- Importing a plugin; 
                                        -- See Note [Care with plugin imports] in LoadIface
843 844

instance Outputable WhereFrom where
Ian Lynagh's avatar
Ian Lynagh committed
845
  ppr (ImportByUser is_boot) | is_boot     = ptext (sLit "{- SOURCE -}")
846 847
                             | otherwise   = empty
  ppr ImportBySystem                       = ptext (sLit "{- SYSTEM -}")
848
  ppr ImportByPlugin                       = ptext (sLit "{- PLUGIN -}")
849 850
\end{code}

851
%************************************************************************
852
%*                                                                      *
853 854 855
%*                       Canonical constraints                          *
%*                                                                      *
%*   These are the constraints the low-level simplifier works with      *
856
%*                                                                      *
857 858 859 860
%************************************************************************


\begin{code}
861 862 863 864
-- The syntax of xi types:
-- xi ::= a | T xis | xis -> xis | ... | forall a. tau
-- Two important notes:
--      (i) No type families, unless we are under a ForAll
865 866
--      (ii) Note that xi types can contain unexpanded type synonyms;
--           however, the (transitive) expansions of those type synonyms
867 868 869
--           will not contain any type functions, unless we are under a ForAll.
-- We enforce the structure of Xi types when we flatten (TcCanonical)

870 871 872 873 874
type Xi = Type       -- In many comments, "xi" ranges over Xi

type Cts = Bag Ct

data Ct
875
  -- Atomic canonical constraints
876
  = CDictCan {  -- e.g.  Num xi
877
      cc_ev :: CtEvidence,   -- See Note [Ct/evidence invariant]
878
      cc_class  :: Class,
879 880
      cc_tyargs :: [Xi],

881
      cc_loc  :: CtLoc
882 883 884
    }

  | CIrredEvCan {  -- These stand for yet-unknown predicates
885
      cc_ev :: CtEvidence,   -- See Note [Ct/evidence invariant]
886
                   -- In CIrredEvCan, the ctev_pred of the evidence is flat
887
                   -- and hence it may only be of the form (tv xi1 xi2 ... xin)
888 889 890
                   -- Since, if it were a type constructor application, that'd make the
                   -- whole constraint a CDictCan, or CTyEqCan. And it can't be
                   -- a type family application either because it's a Xi type.
891
      cc_loc :: CtLoc
892 893
    }

894 895
  | CTyEqCan {  -- tv ~ xi      (recall xi means function free)
       -- Invariant:
896 897 898 899
       --   * tv not in tvs(xi)   (occurs check)
       --   * typeKind xi `compatKind` typeKind tv
       --       See Note [Spontaneous solving and kind compatibility]
       --   * We prefer unification variables on the left *JUST* for efficiency
900
      cc_ev :: CtEvidence,    -- See Note [Ct/evidence invariant]
901
      cc_tyvar  :: TcTyVar,
902
      cc_rhs    :: Xi,
903
      cc_loc    :: CtLoc
904 905
    }

906 907
  | CFunEqCan {  -- F xis ~ xi
                 -- Invariant: * isSynFamilyTyCon cc_fun
908
                 --            * typeKind (F xis) `compatKind` typeKind xi
909
      cc_ev     :: CtEvidence,  -- See Note [Ct/evidence invariant]
910 911 912 913
      cc_fun    :: TyCon,       -- A type function
      cc_tyargs :: [Xi],        -- Either under-saturated or exactly saturated
      cc_rhs    :: Xi,          --    *never* over-saturated (because if so
                                --    we should have decomposed)
914

915
      cc_loc  :: CtLoc
916

917 918
    }

919 920
  | CNonCanonical { -- See Note [NonCanonical Semantics]
      cc_ev  :: CtEvidence,
921
      cc_loc :: CtLoc
922
    }
923 924

  | CHoleCan {
925
      cc_ev  :: CtEvidence,
926 927
      cc_loc :: CtLoc,
      cc_occ :: OccName    -- The name of this hole
928
    }
929 930
\end{code}

931 932 933
Note [Ct/evidence invariant]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
If  ct :: Ct, then extra fields of 'ct' cache precisely the ctev_pred field
934
of (cc_ev ct), and is fully rewritten wrt the substitution.   Eg for CDictCan,
935 936
   ctev_pred (cc_ev ct) = (cc_class ct) (cc_tyargs ct)
This holds by construction; look at the unique place where CDictCan is
937 938 939 940
built (in TcCanonical).

In contrast, the type of the evidence *term* (ccev_evtm or ctev_evar) in
the evidence may *not* be fully zonked; we are careful not to look at it
Gabor Greif's avatar
Gabor Greif committed
941
during constraint solving.  See Note [Evidence field of CtEvidence]