/[jscoverage]/trunk/js/jsparse.h
ViewVC logotype

Contents of /trunk/js/jsparse.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 507 - (show annotations)
Sun Jan 10 07:23:34 2010 UTC (9 years, 11 months ago) by siliconforks
File MIME type: text/plain
File size: 40224 byte(s)
Update SpiderMonkey from Firefox 3.6rc1.

1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sw=4 et tw=78:
3 *
4 * ***** BEGIN LICENSE BLOCK *****
5 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
6 *
7 * The contents of this file are subject to the Mozilla Public License Version
8 * 1.1 (the "License"); you may not use this file except in compliance with
9 * the License. You may obtain a copy of the License at
10 * http://www.mozilla.org/MPL/
11 *
12 * Software distributed under the License is distributed on an "AS IS" basis,
13 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
14 * for the specific language governing rights and limitations under the
15 * License.
16 *
17 * The Original Code is Mozilla Communicator client code, released
18 * March 31, 1998.
19 *
20 * The Initial Developer of the Original Code is
21 * Netscape Communications Corporation.
22 * Portions created by the Initial Developer are Copyright (C) 1998
23 * the Initial Developer. All Rights Reserved.
24 *
25 * Contributor(s):
26 *
27 * Alternatively, the contents of this file may be used under the terms of
28 * either of the GNU General Public License Version 2 or later (the "GPL"),
29 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
30 * in which case the provisions of the GPL or the LGPL are applicable instead
31 * of those above. If you wish to allow use of your version of this file only
32 * under the terms of either the GPL or the LGPL, and not to allow others to
33 * use your version of this file under the terms of the MPL, indicate your
34 * decision by deleting the provisions above and replace them with the notice
35 * and other provisions required by the GPL or the LGPL. If you do not delete
36 * the provisions above, a recipient may use your version of this file under
37 * the terms of any one of the MPL, the GPL or the LGPL.
38 *
39 * ***** END LICENSE BLOCK ***** */
40
41 #ifndef jsparse_h___
42 #define jsparse_h___
43 /*
44 * JS parser definitions.
45 */
46 #include "jsversion.h"
47 #include "jsprvtd.h"
48 #include "jspubtd.h"
49 #include "jsatom.h"
50 #include "jsscan.h"
51
52 JS_BEGIN_EXTERN_C
53
54 /*
55 * Parsing builds a tree of nodes that directs code generation. This tree is
56 * not a concrete syntax tree in all respects (for example, || and && are left
57 * associative, but (A && B && C) translates into the right-associated tree
58 * <A && <B && C>> so that code generation can emit a left-associative branch
59 * around <B && C> when A is false). Nodes are labeled by token type, with a
60 * JSOp secondary label when needed:
61 *
62 * Label Variant Members
63 * ----- ------- -------
64 * <Definitions>
65 * TOK_FUNCTION name pn_funbox: ptr to JSFunctionBox holding function
66 * object containing arg and var properties. We
67 * create the function object at parse (not emit)
68 * time to specialize arg and var bytecodes early.
69 * pn_body: TOK_UPVARS if the function's source body
70 * depends on outer names, else TOK_ARGSBODY
71 * if formal parameters, else TOK_LC node for
72 * function body statements
73 * pn_cookie: static level and var index for function
74 * pn_dflags: PND_* definition/use flags (see below)
75 * pn_blockid: block id number
76 * TOK_ARGSBODY list list of formal parameters followed by TOK_LC node
77 * for function body statements as final element
78 * pn_count: 1 + number of formal parameters
79 * TOK_UPVARS nameset pn_names: lexical dependencies (JSDefinitions)
80 * defined in enclosing scopes, or ultimately not
81 * defined (free variables, either global property
82 * references or reference errors).
83 * pn_argsbody: TOK_ARGSBODY or TOK_LC node
84 *
85 * <Statements>
86 * TOK_LC list pn_head: list of pn_count statements
87 * TOK_IF ternary pn_kid1: cond, pn_kid2: then, pn_kid3: else or null
88 * TOK_SWITCH binary pn_left: discriminant
89 * pn_right: list of TOK_CASE nodes, with at most one
90 * TOK_DEFAULT node, or if there are let bindings
91 * in the top level of the switch body's cases, a
92 * TOK_LEXICALSCOPE node that contains the list of
93 * TOK_CASE nodes.
94 * TOK_CASE, binary pn_left: case expr or null if TOK_DEFAULT
95 * TOK_DEFAULT pn_right: TOK_LC node for this case's statements
96 * pn_val: constant value if lookup or table switch
97 * TOK_WHILE binary pn_left: cond, pn_right: body
98 * TOK_DO binary pn_left: body, pn_right: cond
99 * TOK_FOR binary pn_left: either
100 * for/in loop: a binary TOK_IN node with
101 * pn_left: TOK_VAR or TOK_NAME to left of 'in'
102 * if TOK_VAR, its pn_xflags may have PNX_POPVAR
103 * and PNX_FORINVAR bits set
104 * pn_right: object expr to right of 'in'
105 * for(;;) loop: a ternary TOK_RESERVED node with
106 * pn_kid1: init expr before first ';'
107 * pn_kid2: cond expr before second ';'
108 * pn_kid3: update expr after second ';'
109 * any kid may be null
110 * pn_right: body
111 * TOK_THROW unary pn_op: JSOP_THROW, pn_kid: exception
112 * TOK_TRY ternary pn_kid1: try block
113 * pn_kid2: null or TOK_RESERVED list of
114 * TOK_LEXICALSCOPE nodes, each with pn_expr pointing
115 * to a TOK_CATCH node
116 * pn_kid3: null or finally block
117 * TOK_CATCH ternary pn_kid1: TOK_NAME, TOK_RB, or TOK_RC catch var node
118 * (TOK_RB or TOK_RC if destructuring)
119 * pn_kid2: null or the catch guard expression
120 * pn_kid3: catch block statements
121 * TOK_BREAK name pn_atom: label or null
122 * TOK_CONTINUE name pn_atom: label or null
123 * TOK_WITH binary pn_left: head expr, pn_right: body
124 * TOK_VAR list pn_head: list of TOK_NAME or TOK_ASSIGN nodes
125 * each name node has
126 * pn_used: false
127 * pn_atom: variable name
128 * pn_expr: initializer or null
129 * each assignment node has
130 * pn_left: TOK_NAME with pn_used true and
131 * pn_lexdef (NOT pn_expr) set
132 * pn_right: initializer
133 * TOK_RETURN unary pn_kid: return expr or null
134 * TOK_SEMI unary pn_kid: expr or null statement
135 * TOK_COLON name pn_atom: label, pn_expr: labeled statement
136 *
137 * <Expressions>
138 * All left-associated binary trees of the same type are optimized into lists
139 * to avoid recursion when processing expression chains.
140 * TOK_COMMA list pn_head: list of pn_count comma-separated exprs
141 * TOK_ASSIGN binary pn_left: lvalue, pn_right: rvalue
142 * pn_op: JSOP_ADD for +=, etc.
143 * TOK_HOOK ternary pn_kid1: cond, pn_kid2: then, pn_kid3: else
144 * TOK_OR binary pn_left: first in || chain, pn_right: rest of chain
145 * TOK_AND binary pn_left: first in && chain, pn_right: rest of chain
146 * TOK_BITOR binary pn_left: left-assoc | expr, pn_right: ^ expr
147 * TOK_BITXOR binary pn_left: left-assoc ^ expr, pn_right: & expr
148 * TOK_BITAND binary pn_left: left-assoc & expr, pn_right: EQ expr
149 * TOK_EQOP binary pn_left: left-assoc EQ expr, pn_right: REL expr
150 * pn_op: JSOP_EQ, JSOP_NE,
151 * JSOP_STRICTEQ, JSOP_STRICTNE
152 * TOK_RELOP binary pn_left: left-assoc REL expr, pn_right: SH expr
153 * pn_op: JSOP_LT, JSOP_LE, JSOP_GT, JSOP_GE
154 * TOK_SHOP binary pn_left: left-assoc SH expr, pn_right: ADD expr
155 * pn_op: JSOP_LSH, JSOP_RSH, JSOP_URSH
156 * TOK_PLUS, binary pn_left: left-assoc ADD expr, pn_right: MUL expr
157 * pn_xflags: if a left-associated binary TOK_PLUS
158 * tree has been flattened into a list (see above
159 * under <Expressions>), pn_xflags will contain
160 * PNX_STRCAT if at least one list element is a
161 * string literal (TOK_STRING); if such a list has
162 * any non-string, non-number term, pn_xflags will
163 * contain PNX_CANTFOLD.
164 * pn_
165 * TOK_MINUS pn_op: JSOP_ADD, JSOP_SUB
166 * TOK_STAR, binary pn_left: left-assoc MUL expr, pn_right: UNARY expr
167 * TOK_DIVOP pn_op: JSOP_MUL, JSOP_DIV, JSOP_MOD
168 * TOK_UNARYOP unary pn_kid: UNARY expr, pn_op: JSOP_NEG, JSOP_POS,
169 * JSOP_NOT, JSOP_BITNOT, JSOP_TYPEOF, JSOP_VOID
170 * TOK_INC, unary pn_kid: MEMBER expr
171 * TOK_DEC
172 * TOK_NEW list pn_head: list of ctor, arg1, arg2, ... argN
173 * pn_count: 1 + N (where N is number of args)
174 * ctor is a MEMBER expr
175 * TOK_DELETE unary pn_kid: MEMBER expr
176 * TOK_DOT, name pn_expr: MEMBER expr to left of .
177 * TOK_DBLDOT pn_atom: name to right of .
178 * TOK_LB binary pn_left: MEMBER expr to left of [
179 * pn_right: expr between [ and ]
180 * TOK_LP list pn_head: list of call, arg1, arg2, ... argN
181 * pn_count: 1 + N (where N is number of args)
182 * call is a MEMBER expr naming a callable object
183 * TOK_RB list pn_head: list of pn_count array element exprs
184 * [,,] holes are represented by TOK_COMMA nodes
185 * pn_xflags: PN_ENDCOMMA if extra comma at end
186 * TOK_RC list pn_head: list of pn_count binary TOK_COLON nodes
187 * TOK_COLON binary key-value pair in object initializer or
188 * destructuring lhs
189 * pn_left: property id, pn_right: value
190 * var {x} = object destructuring shorthand shares
191 * PN_NAME node for x on left and right of TOK_COLON
192 * node in TOK_RC's list, has PNX_DESTRUCT flag
193 * TOK_DEFSHARP unary pn_num: jsint value of n in #n=
194 * pn_kid: primary function, paren, name, object or
195 * array literal expressions
196 * TOK_USESHARP nullary pn_num: jsint value of n in #n#
197 * TOK_NAME, name pn_atom: name, string, or object atom
198 * TOK_STRING, pn_op: JSOP_NAME, JSOP_STRING, or JSOP_OBJECT, or
199 * JSOP_REGEXP
200 * TOK_REGEXP If JSOP_NAME, pn_op may be JSOP_*ARG or JSOP_*VAR
201 * with pn_cookie telling (staticLevel, slot) (see
202 * jsscript.h's UPVAR macros) and pn_dflags telling
203 * const-ness and static analysis results
204 * TOK_NAME name If pn_used, TOK_NAME uses the lexdef member instead
205 * of the expr member it overlays
206 * TOK_NUMBER dval pn_dval: double value of numeric literal
207 * TOK_PRIMARY nullary pn_op: JSOp bytecode
208 *
209 * <E4X node descriptions>
210 * TOK_ANYNAME nullary pn_op: JSOP_ANYNAME
211 * pn_atom: cx->runtime->atomState.starAtom
212 * TOK_AT unary pn_op: JSOP_TOATTRNAME; pn_kid attribute id/expr
213 * TOK_DBLCOLON binary pn_op: JSOP_QNAME
214 * pn_left: TOK_ANYNAME or TOK_NAME node
215 * pn_right: TOK_STRING "*" node, or expr within []
216 * name pn_op: JSOP_QNAMECONST
217 * pn_expr: TOK_ANYNAME or TOK_NAME left operand
218 * pn_atom: name on right of ::
219 * TOK_XMLELEM list XML element node
220 * pn_head: start tag, content1, ... contentN, end tag
221 * pn_count: 2 + N where N is number of content nodes
222 * N may be > x.length() if {expr} embedded
223 * TOK_XMLLIST list XML list node
224 * pn_head: content1, ... contentN
225 * TOK_XMLSTAGO, list XML start, end, and point tag contents
226 * TOK_XMLETAGC, pn_head: tag name or {expr}, ... XML attrs ...
227 * TOK_XMLPTAGO
228 * TOK_XMLNAME nullary pn_atom: XML name, with no {expr} embedded
229 * TOK_XMLNAME list pn_head: tag name or {expr}, ... name or {expr}
230 * TOK_XMLATTR, nullary pn_atom: attribute value string; pn_op: JSOP_STRING
231 * TOK_XMLCDATA,
232 * TOK_XMLCOMMENT
233 * TOK_XMLPI nullary pn_atom: XML processing instruction target
234 * pn_atom2: XML PI content, or null if no content
235 * TOK_XMLTEXT nullary pn_atom: marked-up text, or null if empty string
236 * TOK_LC unary {expr} in XML tag or content; pn_kid is expr
237 *
238 * So an XML tag with no {expr} and three attributes is a list with the form:
239 *
240 * (tagname attrname1 attrvalue1 attrname2 attrvalue2 attrname2 attrvalue3)
241 *
242 * An XML tag with embedded expressions like so:
243 *
244 * <name1{expr1} name2{expr2}name3={expr3}>
245 *
246 * would have the form:
247 *
248 * ((name1 {expr1}) (name2 {expr2} name3) {expr3})
249 *
250 * where () bracket a list with elements separated by spaces, and {expr} is a
251 * TOK_LC unary node with expr as its kid.
252 *
253 * Thus, the attribute name/value pairs occupy successive odd and even list
254 * locations, where pn_head is the TOK_XMLNAME node at list location 0. The
255 * parser builds the same sort of structures for elements:
256 *
257 * <a x={x}>Hi there!<b y={y}>How are you?</b><answer>{x + y}</answer></a>
258 *
259 * translates to:
260 *
261 * ((a x {x}) 'Hi there!' ((b y {y}) 'How are you?') ((answer) {x + y}))
262 *
263 * <Non-E4X node descriptions, continued>
264 *
265 * Label Variant Members
266 * ----- ------- -------
267 * TOK_LEXICALSCOPE name pn_op: JSOP_LEAVEBLOCK or JSOP_LEAVEBLOCKEXPR
268 * pn_objbox: block object in JSObjectBox holder
269 * pn_expr: block body
270 * TOK_ARRAYCOMP list pn_head: list of pn_count (1 or 2) elements
271 * if pn_count is 2, first element is #n=[...]
272 * last element is block enclosing for loop(s)
273 * and optionally if-guarded TOK_ARRAYPUSH
274 * TOK_ARRAYPUSH unary pn_op: JSOP_ARRAYCOMP
275 * pn_kid: array comprehension expression
276 */
277 typedef enum JSParseNodeArity {
278 PN_NULLARY, /* 0 kids, only pn_atom/pn_dval/etc. */
279 PN_UNARY, /* one kid, plus a couple of scalars */
280 PN_BINARY, /* two kids, plus a couple of scalars */
281 PN_TERNARY, /* three kids */
282 PN_FUNC, /* function definition node */
283 PN_LIST, /* generic singly linked list */
284 PN_NAME, /* name use or definition node */
285 PN_NAMESET /* JSAtomList + JSParseNode ptr */
286 } JSParseNodeArity;
287
288 struct JSDefinition;
289
290 struct JSParseNode {
291 uint32 pn_type:16, /* TOK_* type, see jsscan.h */
292 pn_op:8, /* see JSOp enum and jsopcode.tbl */
293 pn_arity:5, /* see JSParseNodeArity enum */
294 pn_parens:1, /* this expr was enclosed in parens */
295 pn_used:1, /* name node is on a use-chain */
296 pn_defn:1; /* this node is a JSDefinition */
297
298 #define PN_OP(pn) ((JSOp)(pn)->pn_op)
299 #define PN_TYPE(pn) ((JSTokenType)(pn)->pn_type)
300
301 JSTokenPos pn_pos; /* two 16-bit pairs here, for 64 bits */
302 int32 pn_offset; /* first generated bytecode offset */
303 JSParseNode *pn_next; /* intrinsic link in parent PN_LIST */
304 JSParseNode *pn_link; /* def/use link (alignment freebie) */
305 union {
306 struct { /* list of next-linked nodes */
307 JSParseNode *head; /* first node in list */
308 JSParseNode **tail; /* ptr to ptr to last node in list */
309 uint32 count; /* number of nodes in list */
310 uint32 xflags:12, /* extra flags, see below */
311 blockid:20; /* see name variant below */
312 } list;
313 struct { /* ternary: if, for(;;), ?: */
314 JSParseNode *kid1; /* condition, discriminant, etc. */
315 JSParseNode *kid2; /* then-part, case list, etc. */
316 JSParseNode *kid3; /* else-part, default case, etc. */
317 } ternary;
318 struct { /* two kids if binary */
319 JSParseNode *left;
320 JSParseNode *right;
321 jsval val; /* switch case value */
322 uintN iflags; /* JSITER_* flags for TOK_FOR node */
323 } binary;
324 struct { /* one kid if unary */
325 JSParseNode *kid;
326 jsint num; /* -1 or sharp variable number */
327 JSBool hidden; /* hidden genexp-induced JSOP_YIELD */
328 } unary;
329 struct { /* name, labeled statement, etc. */
330 union {
331 JSAtom *atom; /* lexical name or label atom */
332 JSFunctionBox *funbox; /* function object */
333 JSObjectBox *objbox; /* block or regexp object */
334 };
335 union {
336 JSParseNode *expr; /* function body, var initializer, or
337 base object of TOK_DOT */
338 JSDefinition *lexdef; /* lexical definition for this use */
339 };
340 uint32 cookie; /* upvar cookie with absolute frame
341 level (not relative skip), possibly
342 in current frame */
343 uint32 dflags:12, /* definition/use flags, see below */
344 blockid:20; /* block number, for subset dominance
345 computation */
346 } name;
347 struct { /* lexical dependencies + sub-tree */
348 JSAtomSet names; /* set of names with JSDefinitions */
349 JSParseNode *tree; /* sub-tree containing name uses */
350 } nameset;
351 struct { /* PN_NULLARY variant for E4X */
352 JSAtom *atom; /* first atom in pair */
353 JSAtom *atom2; /* second atom in pair or null */
354 } apair;
355 jsdouble dval; /* aligned numeric literal value */
356 } pn_u;
357
358 #define pn_funbox pn_u.name.funbox
359 #define pn_body pn_u.name.expr
360 #define pn_cookie pn_u.name.cookie
361 #define pn_dflags pn_u.name.dflags
362 #define pn_blockid pn_u.name.blockid
363 #define pn_index pn_u.name.blockid /* reuse as object table index */
364 #define pn_head pn_u.list.head
365 #define pn_tail pn_u.list.tail
366 #define pn_count pn_u.list.count
367 #define pn_xflags pn_u.list.xflags
368 #define pn_kid1 pn_u.ternary.kid1
369 #define pn_kid2 pn_u.ternary.kid2
370 #define pn_kid3 pn_u.ternary.kid3
371 #define pn_left pn_u.binary.left
372 #define pn_right pn_u.binary.right
373 #define pn_val pn_u.binary.val
374 #define pn_iflags pn_u.binary.iflags
375 #define pn_kid pn_u.unary.kid
376 #define pn_num pn_u.unary.num
377 #define pn_hidden pn_u.unary.hidden
378 #define pn_atom pn_u.name.atom
379 #define pn_objbox pn_u.name.objbox
380 #define pn_expr pn_u.name.expr
381 #define pn_lexdef pn_u.name.lexdef
382 #define pn_names pn_u.nameset.names
383 #define pn_tree pn_u.nameset.tree
384 #define pn_dval pn_u.dval
385 #define pn_atom2 pn_u.apair.atom2
386
387 /*
388 * The pn_expr and lexdef members are arms of an unsafe union. Unless you
389 * know exactly what you're doing, use only the following methods to access
390 * them. For less overhead and assertions for protection, use pn->expr()
391 * and pn->lexdef(). Otherwise, use pn->maybeExpr() and pn->maybeLexDef().
392 */
393 JSParseNode *expr() const {
394 JS_ASSERT(!pn_used);
395 JS_ASSERT(pn_arity == PN_NAME || pn_arity == PN_FUNC);
396 return pn_expr;
397 }
398
399 JSDefinition *lexdef() const {
400 JS_ASSERT(pn_used);
401 JS_ASSERT(pn_arity == PN_NAME);
402 return pn_lexdef;
403 }
404
405 JSParseNode *maybeExpr() { return pn_used ? NULL : expr(); }
406 JSDefinition *maybeLexDef() { return pn_used ? lexdef() : NULL; }
407
408 /* PN_FUNC and PN_NAME pn_dflags bits. */
409 #define PND_LET 0x01 /* let (block-scoped) binding */
410 #define PND_CONST 0x02 /* const binding (orthogonal to let) */
411 #define PND_INITIALIZED 0x04 /* initialized declaration */
412 #define PND_ASSIGNED 0x08 /* set if ever LHS of assignment */
413 #define PND_TOPLEVEL 0x10 /* function at top of body or prog */
414 #define PND_BLOCKCHILD 0x20 /* use or def is direct block child */
415 #define PND_GVAR 0x40 /* gvar binding, can't close over
416 because it could be deleted */
417 #define PND_PLACEHOLDER 0x80 /* placeholder definition for lexdep */
418 #define PND_FUNARG 0x100 /* downward or upward funarg usage */
419 #define PND_BOUND 0x200 /* bound to a stack or global slot */
420
421 /* Flags to propagate from uses to definition. */
422 #define PND_USE2DEF_FLAGS (PND_ASSIGNED | PND_FUNARG)
423
424 /* PN_LIST pn_xflags bits. */
425 #define PNX_STRCAT 0x01 /* TOK_PLUS list has string term */
426 #define PNX_CANTFOLD 0x02 /* TOK_PLUS list has unfoldable term */
427 #define PNX_POPVAR 0x04 /* TOK_VAR last result needs popping */
428 #define PNX_FORINVAR 0x08 /* TOK_VAR is left kid of TOK_IN node,
429 which is left kid of TOK_FOR */
430 #define PNX_ENDCOMMA 0x10 /* array literal has comma at end */
431 #define PNX_XMLROOT 0x20 /* top-most node in XML literal tree */
432 #define PNX_GROUPINIT 0x40 /* var [a, b] = [c, d]; unit list */
433 #define PNX_NEEDBRACES 0x80 /* braces necessary due to closure */
434 #define PNX_FUNCDEFS 0x100 /* contains top-level function
435 statements */
436 #define PNX_DESTRUCT 0x200 /* destructuring special cases:
437 1. shorthand syntax used, at present
438 object destructuring ({x,y}) only;
439 2. the first child of function body
440 is code evaluating destructuring
441 arguments */
442 #define PNX_HOLEY 0x400 /* array initialiser has holes */
443
444 uintN frameLevel() const {
445 JS_ASSERT(pn_arity == PN_FUNC || pn_arity == PN_NAME);
446 return UPVAR_FRAME_SKIP(pn_cookie);
447 }
448
449 uintN frameSlot() const {
450 JS_ASSERT(pn_arity == PN_FUNC || pn_arity == PN_NAME);
451 return UPVAR_FRAME_SLOT(pn_cookie);
452 }
453
454 bool test(uintN flag) const {
455 JS_ASSERT(pn_arity == PN_FUNC || pn_arity == PN_NAME);
456 return !!(pn_dflags & flag);
457 }
458
459 bool isLet() const { return test(PND_LET); }
460 bool isConst() const { return test(PND_CONST); }
461 bool isInitialized() const { return test(PND_INITIALIZED); }
462 bool isTopLevel() const { return test(PND_TOPLEVEL); }
463 bool isBlockChild() const { return test(PND_BLOCKCHILD); }
464 bool isPlaceholder() const { return test(PND_PLACEHOLDER); }
465
466 /* Defined below, see after struct JSDefinition. */
467 bool isAssigned() const;
468 bool isFunArg() const;
469 void setFunArg();
470
471 void become(JSParseNode *pn2);
472 void clear();
473
474 /* True if pn is a parsenode representing a literal constant. */
475 bool isLiteral() const {
476 return PN_TYPE(this) == TOK_NUMBER ||
477 PN_TYPE(this) == TOK_STRING ||
478 (PN_TYPE(this) == TOK_PRIMARY && PN_OP(this) != JSOP_THIS);
479 }
480
481 /*
482 * Compute a pointer to the last element in a singly-linked list. NB: list
483 * must be non-empty for correct PN_LAST usage -- this is asserted!
484 */
485 JSParseNode *last() const {
486 JS_ASSERT(pn_arity == PN_LIST);
487 JS_ASSERT(pn_count != 0);
488 return (JSParseNode *)((char *)pn_tail - offsetof(JSParseNode, pn_next));
489 }
490
491 void makeEmpty() {
492 JS_ASSERT(pn_arity == PN_LIST);
493 pn_head = NULL;
494 pn_tail = &pn_head;
495 pn_count = 0;
496 pn_xflags = 0;
497 pn_blockid = 0;
498 }
499
500 void initList(JSParseNode *pn) {
501 JS_ASSERT(pn_arity == PN_LIST);
502 pn_head = pn;
503 pn_tail = &pn->pn_next;
504 pn_count = 1;
505 pn_xflags = 0;
506 pn_blockid = 0;
507 }
508
509 void append(JSParseNode *pn) {
510 JS_ASSERT(pn_arity == PN_LIST);
511 *pn_tail = pn;
512 pn_tail = &pn->pn_next;
513 pn_count++;
514 }
515 };
516
517 /*
518 * JSDefinition is a degenerate subtype of the PN_FUNC and PN_NAME variants of
519 * JSParseNode, allocated only for function, var, const, and let declarations
520 * that define truly lexical bindings. This means that a child of a TOK_VAR
521 * list may be a JSDefinition instead of a JSParseNode. The pn_defn bit is set
522 * for all JSDefinitions, clear otherwise.
523 *
524 * Note that not all var declarations are definitions: JS allows multiple var
525 * declarations in a function or script, but only the first creates the hoisted
526 * binding. JS programmers do redeclare variables for good refactoring reasons,
527 * for example:
528 *
529 * function foo() {
530 * ...
531 * for (var i ...) ...;
532 * ...
533 * for (var i ...) ...;
534 * ...
535 * }
536 *
537 * Not all definitions bind lexical variables, alas. In global and eval code
538 * var may re-declare a pre-existing property having any attributes, with or
539 * without JSPROP_PERMANENT. In eval code, indeed, ECMA-262 Editions 1 through
540 * 3 require function and var to bind deletable bindings. Global vars thus are
541 * properties of the global object, so they can be aliased even if they can't
542 * be deleted.
543 *
544 * Only bindings within function code may be treated as lexical, of course with
545 * the caveat that hoisting means use before initialization is allowed. We deal
546 * with use before declaration in one pass as follows (error checking elided):
547 *
548 * for (each use of unqualified name x in parse order) {
549 * if (this use of x is a declaration) {
550 * if (x in tc->decls) { // redeclaring
551 * pn = allocate a PN_NAME JSParseNode;
552 * } else { // defining
553 * dn = lookup x in tc->lexdeps;
554 * if (dn) // use before def
555 * remove x from tc->lexdeps;
556 * else // def before use
557 * dn = allocate a PN_NAME JSDefinition;
558 * map x to dn via tc->decls;
559 * pn = dn;
560 * }
561 * insert pn into its parent TOK_VAR list;
562 * } else {
563 * pn = allocate a JSParseNode for this reference to x;
564 * dn = lookup x in tc's lexical scope chain;
565 * if (!dn) {
566 * dn = lookup x in tc->lexdeps;
567 * if (!dn) {
568 * dn = pre-allocate a JSDefinition for x;
569 * map x to dn in tc->lexdeps;
570 * }
571 * }
572 * append pn to dn's use chain;
573 * }
574 * }
575 *
576 * See jsemit.h for JSTreeContext and its top*Stmt, decls, and lexdeps members.
577 *
578 * Notes:
579 *
580 * 0. To avoid bloating JSParseNode, we steal a bit from pn_arity for pn_defn
581 * and set it on a JSParseNode instead of allocating a JSDefinition.
582 *
583 * 1. Due to hoisting, a definition cannot be eliminated even if its "Variable
584 * statement" (ECMA-262 12.2) can be proven to be dead code. RecycleTree in
585 * jsparse.cpp will not recycle a node whose pn_defn bit is set.
586 *
587 * 2. "lookup x in tc's lexical scope chain" gives up on def/use chaining if a
588 * with statement is found along the the scope chain, which includes tc,
589 * tc->parent, etc. Thus we eagerly connect an inner function's use of an
590 * outer's var x if the var x was parsed before the inner function.
591 *
592 * 3. A use may be eliminated as dead by the constant folder, which therefore
593 * must remove the dead name node from its singly-linked use chain, which
594 * would mean hashing to find the definition node and searching to update
595 * the pn_link pointing at the use to be removed. This is costly, so as for
596 * dead definitions, we do not recycle dead pn_used nodes.
597 *
598 * At the end of parsing a function body or global or eval program, tc->lexdeps
599 * holds the lexical dependencies of the parsed unit. The name to def/use chain
600 * mappings are then merged into the parent tc->lexdeps.
601 *
602 * Thus if a later var x is parsed in the outer function satisfying an earlier
603 * inner function's use of x, we will remove dn from tc->lexdeps and re-use it
604 * as the new definition node in the outer function's parse tree.
605 *
606 * When the compiler unwinds from the outermost tc, tc->lexdeps contains the
607 * definition nodes with use chains for all free variables. These are either
608 * global variables or reference errors.
609 *
610 * We analyze whether a binding is initialized, whether the bound names is ever
611 * assigned apart from its initializer, and if the bound name definition or use
612 * is in a direct child of a block. These PND_* flags allow a subset dominance
613 * computation telling whether an initialized var dominates its uses. An inner
614 * function using only such outer vars (and formal parameters) can be optimized
615 * into a flat closure. See JSOP_{GET,CALL}DSLOT.
616 *
617 * Another important subset dominance relation: ... { var x = ...; ... x ... }
618 * where x is not assigned after initialization and not used outside the block.
619 * This style is common in the absence of 'let'. Even though the var x is not
620 * at top level, we can tell its initialization dominates all uses cheaply,
621 * because the above one-pass algorithm sees the definition before any uses,
622 * and because all uses are contained in the same block as the definition.
623 *
624 * We also analyze function uses to flag upward/downward funargs, optimizing
625 * Algol-like (not passed as funargs, only ever called) lightweight functions
626 * using cx->display. See JSOP_{GET,CALL}UPVAR.
627 *
628 * This means that closure optimizations may be frustrated by with, eval, or
629 * assignment to an outer var. Such hard cases require heavyweight functions
630 * and JSOP_NAME, etc.
631 */
632 #define dn_uses pn_link
633
634 struct JSDefinition : public JSParseNode
635 {
636 /*
637 * We store definition pointers in PN_NAMESET JSAtomLists in the AST, but
638 * due to redefinition these nodes may become uses of other definitions.
639 * This is unusual, so we simply chase the pn_lexdef link to find the final
640 * definition node. See methods called from JSCompiler::analyzeFunctions.
641 *
642 * FIXME: MakeAssignment mutates for want of a parent link...
643 */
644 JSDefinition *resolve() {
645 JSParseNode *pn = this;
646 while (!pn->pn_defn) {
647 if (pn->pn_type == TOK_ASSIGN) {
648 pn = pn->pn_left;
649 continue;
650 }
651 pn = pn->lexdef();
652 }
653 return (JSDefinition *) pn;
654 }
655
656 bool test(uintN flag) const {
657 JS_ASSERT(pn_defn);
658 if (pn_dflags & flag)
659 return true;
660 #ifdef DEBUG
661 for (JSParseNode *pn = dn_uses; pn; pn = pn->pn_link) {
662 JS_ASSERT(!pn->pn_defn);
663 JS_ASSERT(!(pn->pn_dflags & flag));
664 }
665 #endif
666 return false;
667 }
668
669 bool isAssigned() const {
670 return test(PND_ASSIGNED);
671 }
672
673 bool isFunArg() const {
674 return test(PND_FUNARG);
675 }
676
677 bool isFreeVar() const {
678 JS_ASSERT(pn_defn);
679 return pn_cookie == FREE_UPVAR_COOKIE || test(PND_GVAR);
680 }
681
682 // Grr, windows.h or something under it #defines CONST...
683 #ifdef CONST
684 # undef CONST
685 #endif
686 enum Kind { VAR, CONST, LET, FUNCTION, ARG, UNKNOWN };
687
688 bool isBindingForm() { return int(kind()) <= int(LET); }
689
690 static const char *kindString(Kind kind);
691
692 Kind kind() {
693 if (PN_TYPE(this) == TOK_FUNCTION)
694 return FUNCTION;
695 JS_ASSERT(PN_TYPE(this) == TOK_NAME);
696 if (PN_OP(this) == JSOP_NOP)
697 return UNKNOWN;
698 if (PN_OP(this) == JSOP_GETARG)
699 return ARG;
700 if (isConst())
701 return CONST;
702 if (isLet())
703 return LET;
704 return VAR;
705 }
706 };
707
708 /*
709 * These two are overridden by JSDefinition and we cannot afford virtual
710 * methods -- so we use the mighty 'if' statement!
711 */
712 inline bool
713 JSParseNode::isAssigned() const
714 {
715 #ifdef DEBUG
716 if (pn_defn)
717 return ((JSDefinition *)this)->isAssigned();
718 #endif
719 return test(PND_ASSIGNED);
720 }
721
722 inline bool
723 JSParseNode::isFunArg() const
724 {
725 #ifdef DEBUG
726 if (pn_defn)
727 return ((JSDefinition *)this)->isFunArg();
728 #endif
729 return test(PND_FUNARG);
730 }
731
732 inline void
733 JSParseNode::setFunArg()
734 {
735 /*
736 * pn_defn NAND pn_used must be true, per this chart:
737 *
738 * pn_defn pn_used
739 * 0 0 anonymous function used implicitly, e.g. by
740 * hidden yield in a genexp
741 * 0 1 a use of a definition or placeholder
742 * 1 0 a definition or placeholder
743 * 1 1 error: this case must not be possible
744 */
745 JS_ASSERT(!(pn_defn & pn_used));
746 if (pn_used)
747 pn_lexdef->pn_dflags |= PND_FUNARG;
748 pn_dflags |= PND_FUNARG;
749 }
750
751 struct JSObjectBox {
752 JSObjectBox *traceLink;
753 JSObjectBox *emitLink;
754 JSObject *object;
755 };
756
757 #define JSFB_LEVEL_BITS 14
758
759 struct JSFunctionBox : public JSObjectBox
760 {
761 JSParseNode *node;
762 JSFunctionBox *siblings;
763 JSFunctionBox *kids;
764 JSFunctionBox *parent;
765 uint32 queued:1,
766 inLoop:1, /* in a loop in parent function */
767 level:JSFB_LEVEL_BITS,
768 tcflags:16;
769 };
770
771 struct JSFunctionBoxQueue {
772 JSFunctionBox **vector;
773 size_t head, tail;
774 size_t lengthMask;
775
776 size_t count() { return head - tail; }
777 size_t length() { return lengthMask + 1; }
778
779 JSFunctionBoxQueue()
780 : vector(NULL), head(0), tail(0), lengthMask(0) { }
781
782 bool init(uint32 count) {
783 lengthMask = JS_BITMASK(JS_CeilingLog2(count));
784 vector = new JSFunctionBox*[length()];
785 return !!vector;
786 }
787
788 ~JSFunctionBoxQueue() { delete[] vector; }
789
790 void push(JSFunctionBox *funbox) {
791 if (!funbox->queued) {
792 JS_ASSERT(count() < length());
793 vector[head++ & lengthMask] = funbox;
794 funbox->queued = true;
795 }
796 }
797
798 JSFunctionBox *pull() {
799 if (tail == head)
800 return NULL;
801 JS_ASSERT(tail < head);
802 JSFunctionBox *funbox = vector[tail++ & lengthMask];
803 funbox->queued = false;
804 return funbox;
805 }
806 };
807
808 #define NUM_TEMP_FREELISTS 6U /* 32 to 2048 byte size classes (32 bit) */
809
810 struct JSCompiler {
811 JSContext *context;
812 JSAtomListElement *aleFreeList;
813 void *tempFreeList[NUM_TEMP_FREELISTS];
814 JSTokenStream tokenStream;
815 void *tempPoolMark; /* initial JSContext.tempPool mark */
816 JSPrincipals *principals; /* principals associated with source */
817 JSStackFrame *callerFrame; /* scripted caller frame for eval and dbgapi */
818 JSParseNode *nodeList; /* list of recyclable parse-node structs */
819 uint32 functionCount; /* number of functions in current unit */
820 JSObjectBox *traceListHead; /* list of parsed object for GC tracing */
821 JSTempValueRooter tempRoot; /* root to trace traceListHead */
822
823 JSCompiler(JSContext *cx, JSPrincipals *prin = NULL, JSStackFrame *cfp = NULL)
824 : context(cx), aleFreeList(NULL), tokenStream(cx), principals(NULL),
825 callerFrame(cfp), nodeList(NULL), functionCount(0), traceListHead(NULL)
826 {
827 memset(tempFreeList, 0, sizeof tempFreeList);
828 setPrincipals(prin);
829 JS_ASSERT_IF(cfp, cfp->script);
830 }
831
832 ~JSCompiler();
833
834 /*
835 * Initialize a compiler. Parameters are passed on to init tokenStream.
836 * The compiler owns the arena pool "tops-of-stack" space above the current
837 * JSContext.tempPool mark. This means you cannot allocate from tempPool
838 * and save the pointer beyond the next JSCompiler destructor invocation.
839 */
840 bool init(const jschar *base, size_t length,
841 FILE *fp, const char *filename, uintN lineno);
842
843 void setPrincipals(JSPrincipals *prin);
844
845 /*
846 * Parse a top-level JS script.
847 */
848 JSParseNode *parse(JSObject *chain);
849
850 #if JS_HAS_XML_SUPPORT
851 JSParseNode *parseXMLText(JSObject *chain, bool allowList);
852 #endif
853
854 /*
855 * Allocate a new parsed object or function container from cx->tempPool.
856 */
857 JSObjectBox *newObjectBox(JSObject *obj);
858
859 JSFunctionBox *newFunctionBox(JSObject *obj, JSParseNode *fn, JSTreeContext *tc);
860
861 /*
862 * Create a new function object given tree context (tc), optional name
863 * (atom may be null) and lambda flag (JSFUN_LAMBDA or 0).
864 */
865 JSFunction *newFunction(JSTreeContext *tc, JSAtom *atom, uintN lambda);
866
867 /*
868 * Analyze the tree of functions nested within a single compilation unit,
869 * starting at funbox, recursively walking its kids, then following its
870 * siblings, their kids, etc.
871 */
872 bool analyzeFunctions(JSFunctionBox *funbox, uint16& tcflags);
873 bool markFunArgs(JSFunctionBox *funbox, uintN tcflags);
874 void setFunctionKinds(JSFunctionBox *funbox, uint16& tcflags);
875
876 void trace(JSTracer *trc);
877
878 static bool
879 compileFunctionBody(JSContext *cx, JSFunction *fun, JSPrincipals *principals,
880 const jschar *chars, size_t length,
881 const char *filename, uintN lineno);
882
883 static JSScript *
884 compileScript(JSContext *cx, JSObject *scopeChain, JSStackFrame *callerFrame,
885 JSPrincipals *principals, uint32 tcflags,
886 const jschar *chars, size_t length,
887 FILE *file, const char *filename, uintN lineno,
888 JSString *source = NULL);
889 };
890
891 /*
892 * Convenience macro to access JSCompiler.tokenStream as a pointer.
893 */
894 #define TS(jsc) (&(jsc)->tokenStream)
895
896 extern JSBool
897 js_FoldConstants(JSContext *cx, JSParseNode *pn, JSTreeContext *tc,
898 bool inCond = false);
899
900 JS_END_EXTERN_C
901
902 #endif /* jsparse_h___ */

  ViewVC Help
Powered by ViewVC 1.1.24