Test Trac #9036
[ghc.git] / docs / comm / the-beast / renamer.html
1 <!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
2 <html>
3 <head>
4 <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=ISO-8859-1">
5 <title>The GHC Commentary - The Glorious Renamer</title>
6 </head>
7
8 <body BGCOLOR="FFFFFF">
9 <h1>The GHC Commentary - The Glorious Renamer</h1>
10 <p>
11 The <em>renamer</em> sits between the parser and the typechecker.
12 However, its operation is quite tightly interwoven with the
13 typechecker. This is partially due to support for Template Haskell,
14 where spliced code has to be renamed and type checked. In particular,
15 top-level splices lead to multiple rounds of renaming and type
16 checking.
17 </p>
18 <p>
19 The main externally used functions of the renamer are provided by the
20 module <code>rename/RnSource.lhs</code>. In particular, we have
21 </p>
22 <blockquote>
23 <pre>
24 rnSrcDecls :: HsGroup RdrName -> RnM (TcGblEnv, HsGroup Name)
25 rnTyClDecls :: [LTyClDecl RdrName] -> RnM [LTyClDecl Name]
26 rnSplice :: HsSplice RdrName -> RnM (HsSplice Name, FreeVars)</pre>
27 </blockquote>
28 <p>
29 All of which execute in the renamer monad <code>RnM</code>. The first
30 function, <code>rnSrcDecls</code> renames a binding group; the second,
31 <code>rnTyClDecls</code> renames a list of (toplevel) type and class
32 declarations; and the third, <code>rnSplice</code> renames a Template
33 Haskell splice. As the types indicate, the main task of the renamer is
34 to convert converts all the <tt>RdrNames</tt> to <a
35 href="names.html"><tt>Names</tt></a>, which includes a number of
36 well-formedness checks (no duplicate declarations, all names are in
37 scope, and so on). In addition, the renamer performs other, not
38 strictly name-related, well-formedness checks, which includes checking
39 that the appropriate flags have been supplied whenever language
40 extensions are used in the source.
41 </p>
42
43 <h2>RdrNames</h2>
44 <p>
45 A <tt>RdrName.RdrName</tt> is pretty much just a string (for an
46 unqualified name like "<tt>f</tt>") or a pair of strings (for a
47 qualified name like "<tt>M.f</tt>"):
48 </p>
49 <blockquote>
50 <pre>
51 data RdrName
52 = Unqual OccName
53 -- Used for ordinary, unqualified occurrences
54
55 | Qual Module OccName
56 -- A qualified name written by the user in
57 -- *source* code. The module isn't necessarily
58 -- the module where the thing is defined;
59 -- just the one from which it is imported
60
61 | Orig Module OccName
62 -- An original name; the module is the *defining* module.
63 -- This is used when GHC generates code that will be fed
64 -- into the renamer (e.g. from deriving clauses), but where
65 -- we want to say "Use Prelude.map dammit".
66
67 | Exact Name
68 -- We know exactly the Name. This is used
69 -- (a) when the parser parses built-in syntax like "[]"
70 -- and "(,)", but wants a RdrName from it
71 -- (b) when converting names to the RdrNames in IfaceTypes
72 -- Here an Exact RdrName always contains an External Name
73 -- (Internal Names are converted to simple Unquals)
74 -- (c) by Template Haskell, when TH has generated a unique name</pre>
75 </blockquote>
76 <p>
77 The OccName type is described in <a href="names.html#occname">The
78 truth about names</a>.
79 </p>
80
81 <h2>The Renamer Monad</h2>
82 <p>
83 Due to the tight integration of the renamer with the typechecker, both
84 use the same monad in recent versions of GHC. So, we have
85 </p>
86 <blockquote>
87 <pre>
88 type RnM a = TcRn a -- Historical
89 type TcM a = TcRn a -- Historical</pre>
90 </blockquote>
91 <p>
92 with the combined monad defined as
93 </p>
94 <blockquote>
95 <pre>
96 type TcRn a = TcRnIf TcGblEnv TcLclEnv a
97 type TcRnIf a b c = IOEnv (Env a b) c
98
99 data Env gbl lcl -- Changes as we move into an expression
100 = Env {
101 env_top :: HscEnv, -- Top-level stuff that never changes
102 -- Includes all info about imported things
103
104 env_us :: TcRef UniqSupply, -- Unique supply for local varibles
105
106 env_gbl :: gbl, -- Info about things defined at the top level
107 -- of the module being compiled
108
109 env_lcl :: lcl -- Nested stuff; changes as we go into
110 -- an expression
111 }</pre>
112 </blockquote>
113 <p>
114 the details of the global environment type <code>TcGblEnv</code> and
115 local environment type <code>TcLclEnv</code> are also defined in the
116 module <code>typecheck/TcRnTypes.lhs</code>. The monad
117 <code>IOEnv</code> is defined in <code>utils/IOEnv.hs</code> and extends
118 the vanilla <code>IO</code> monad with an additional state parameter
119 <code>env</code> that is treated as in a reader monad. (Side effecting
120 operations, such as updating the unique supply, are done with
121 <code>TcRef</code>s, which are simply a synonym for <code>IORef</code>s.)
122 </p>
123
124 <h2>Name Space Management</h2>
125 <p>
126 As anticipated by the variants <code>Orig</code> and <code>Exact</code>
127 of <code>RdrName</code> some names should not change during renaming,
128 whereas others need to be turned into unique names. In this context,
129 the two functions <code>RnEnv.newTopSrcBinder</code> and
130 <code>RnEnv.newLocals</code> are important:
131 </p>
132 <blockquote>
133 <pre>
134 newTopSrcBinder :: Module -> Maybe Name -> Located RdrName -> RnM Name
135 newLocalsRn :: [Located RdrName] -> RnM [Name]</pre>
136 </blockquote>
137 <p>
138 The two functions introduces new toplevel and new local names,
139 respectively, where the first two arguments to
140 <code>newTopSrcBinder</code> determine the currently compiled module and
141 the parent construct of the newly defined name. Both functions create
142 new names only for <code>RdrName</code>s that are neither exact nor
143 original.
144 </p>
145
146 <h3>Introduction of Toplevel Names: Global RdrName Environment</h3>
147 <p>
148 A global <code>RdrName</code> environment
149 <code>RdrName.GlobalRdrEnv</code> is a map from <code>OccName</code>s to
150 lists of qualified names. More precisely, the latter are
151 <code>Name</code>s with an associated <code>Provenance</code>:
152 </p>
153 <blockquote>
154 <pre>
155 data Provenance
156 = LocalDef -- Defined locally
157 Module
158
159 | Imported -- Imported
160 [ImportSpec] -- INVARIANT: non-empty
161 Bool -- True iff the thing was named *explicitly*
162 -- in *any* of the import specs rather than being
163 -- imported as part of a group;
164 -- e.g.
165 -- import B
166 -- import C( T(..) )
167 -- Here, everything imported by B, and the constructors of T
168 -- are not named explicitly; only T is named explicitly.
169 -- This info is used when warning of unused names.</pre>
170 </blockquote>
171 <p>
172 The part of the global <code>RdrName</code> environment for a module
173 that contains the local definitions is created by the function
174 <code>RnNames.importsFromLocalDecls</code>, which also computes a data
175 structure recording all imported declarations in the form of a value of
176 type <code>TcRnTypes.ImportAvails</code>.
177 </p>
178 <p>
179 The function <code>importsFromLocalDecls</code>, in turn, makes use of
180 <code>RnNames.getLocalDeclBinders :: Module -> HsGroup RdrName -> RnM
181 [AvailInfo]</code> to extract all declared names from a binding group,
182 where <code>HscTypes.AvailInfo</code> is essentially a collection of
183 <code>Name</code>s; i.e., <code>getLocalDeclBinders</code>, on the fly,
184 generates <code>Name</code>s from the <code>RdrName</code>s of all
185 top-level binders of the module represented by the <code>HsGroup
186 RdrName</code> argument.
187 </p>
188 <p>
189 It is important to note that all this happens before the renamer
190 actually descends into the toplevel bindings of a module. In other
191 words, before <code>TcRnDriver.rnTopSrcDecls</code> performs the
192 renaming of a module by way of <code>RnSource.rnSrcDecls</code>, it uses
193 <code>importsFromLocalDecls</code> to set up the global
194 <code>RdrName</code> environment, which contains <code>Name</code>s for
195 all imported <em>and</em> all locally defined toplevel binders. Hence,
196 when the helpers of <code>rnSrcDecls</code> come across the
197 <em>defining</em> occurrences of a toplevel <code>RdrName</code>, they
198 don't rename it by generating a new name, but they simply look up its
199 name in the global <code>RdrName</code> environment.
200 </p>
201
202 <h2>Rebindable syntax</h2>
203 <p>
204 In Haskell when one writes "3" one gets "fromInteger 3", where
205 "fromInteger" comes from the Prelude (regardless of whether the
206 Prelude is in scope). If you want to completely redefine numbers,
207 that becomes inconvenient. So GHC lets you say
208 "-fno-implicit-prelude"; in that case, the "fromInteger" comes from
209 whatever is in scope. (This is documented in the User Guide.)
210 </p>
211 <p>
212 This feature is implemented as follows (I always forget).
213 <ul>
214 <li>Names that are implicitly bound by the Prelude, are marked by the
215 type <code>HsExpr.SyntaxExpr</code>. Moreover, the association list
216 <code>HsExpr.SyntaxTable</code> is set up by the renamer to map
217 rebindable names to the value they are bound to.
218 </li>
219 <li>Currently, five constructs related to numerals
220 (<code>HsExpr.NegApp</code>, <code>HsPat.NPat</code>,
221 <code>HsPat.NPlusKPat</code>, <code>HsLit.HsIntegral</code>, and
222 <code>HsLit.HsFractional</code>) and
223 two constructs related to code>do</code> expressions
224 (<code>HsExpr.BindStmt</code> and
225 <code>HsExpr.ExprStmt</code>) have rebindable syntax.
226 </li>
227 <li> When the parser builds these constructs, it puts in the
228 built-in Prelude Name (e.g. PrelNum.fromInteger).
229 </li>
230 <li> When the renamer encounters these constructs, it calls
231 <tt>RnEnv.lookupSyntaxName</tt>.
232 This checks for <tt>-fno-implicit-prelude</tt>; if not, it just
233 returns the same Name; otherwise it takes the occurrence name of the
234 Name, turns it into an unqualified RdrName, and looks it up in the
235 environment. The returned name is plugged back into the construct.
236 </li>
237 <li> The typechecker uses the Name to generate the appropriate typing
238 constraints.
239 </li>
240 </ul>
241
242 <p><small>
243 <!-- hhmts start -->
244 Last modified: Wed May 4 17:16:15 EST 2005
245 <!-- hhmts end -->
246 </small>
247 </body>
248 </html>
249