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