Back to index

lightning-sunbird  0.9+nobinonly
jsparse.h
Go to the documentation of this file.
00001 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
00002  * vim: set ts=8 sw=4 et tw=78:
00003  *
00004  * ***** BEGIN LICENSE BLOCK *****
00005  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00006  *
00007  * The contents of this file are subject to the Mozilla Public License Version
00008  * 1.1 (the "License"); you may not use this file except in compliance with
00009  * the License. You may obtain a copy of the License at
00010  * http://www.mozilla.org/MPL/
00011  *
00012  * Software distributed under the License is distributed on an "AS IS" basis,
00013  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00014  * for the specific language governing rights and limitations under the
00015  * License.
00016  *
00017  * The Original Code is Mozilla Communicator client code, released
00018  * March 31, 1998.
00019  *
00020  * The Initial Developer of the Original Code is
00021  * Netscape Communications Corporation.
00022  * Portions created by the Initial Developer are Copyright (C) 1998
00023  * the Initial Developer. All Rights Reserved.
00024  *
00025  * Contributor(s):
00026  *
00027  * Alternatively, the contents of this file may be used under the terms of
00028  * either of the GNU General Public License Version 2 or later (the "GPL"),
00029  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00030  * in which case the provisions of the GPL or the LGPL are applicable instead
00031  * of those above. If you wish to allow use of your version of this file only
00032  * under the terms of either the GPL or the LGPL, and not to allow others to
00033  * use your version of this file under the terms of the MPL, indicate your
00034  * decision by deleting the provisions above and replace them with the notice
00035  * and other provisions required by the GPL or the LGPL. If you do not delete
00036  * the provisions above, a recipient may use your version of this file under
00037  * the terms of any one of the MPL, the GPL or the LGPL.
00038  *
00039  * ***** END LICENSE BLOCK ***** */
00040 
00041 #ifndef jsparse_h___
00042 #define jsparse_h___
00043 /*
00044  * JS parser definitions.
00045  */
00046 #include "jsconfig.h"
00047 #include "jsprvtd.h"
00048 #include "jspubtd.h"
00049 #include "jsscan.h"
00050 
00051 JS_BEGIN_EXTERN_C
00052 
00053 /*
00054  * Parsing builds a tree of nodes that directs code generation.  This tree is
00055  * not a concrete syntax tree in all respects (for example, || and && are left
00056  * associative, but (A && B && C) translates into the right-associated tree
00057  * <A && <B && C>> so that code generation can emit a left-associative branch
00058  * around <B && C> when A is false).  Nodes are labeled by token type, with a
00059  * JSOp secondary label when needed:
00060  *
00061  * Label        Variant     Members
00062  * -----        -------     -------
00063  * <Definitions>
00064  * TOK_FUNCTION func        pn_funAtom: atom holding function object containing
00065  *                            arg and var properties.  We create the function
00066  *                            object at parse (not emit) time to specialize arg
00067  *                            and var bytecodes early.
00068  *                          pn_body: TOK_LC node for function body statements
00069  *                          pn_flags: TCF_FUN_* flags (see jsemit.h) collected
00070  *                            while parsing the function's body
00071  *                          pn_tryCount: of try statements in function
00072  *
00073  * <Statements>
00074  * TOK_LC       list        pn_head: list of pn_count statements
00075  * TOK_EXPORT   list        pn_head: list of pn_count TOK_NAMEs or one TOK_STAR
00076  *                            (which is not a multiply node)
00077  * TOK_IMPORT   list        pn_head: list of pn_count sub-trees of the form
00078  *                            a.b.*, a[b].*, a.*, a.b, or a[b] -- but never a.
00079  *                            Each member is expressed with TOK_DOT or TOK_LB.
00080  *                            Each sub-tree's root node has a pn_op in the set
00081  *                            JSOP_IMPORT{ALL,PROP,ELEM}
00082  * TOK_IF       ternary     pn_kid1: cond, pn_kid2: then, pn_kid3: else or null
00083  * TOK_SWITCH   binary      pn_left: discriminant
00084  *                          pn_right: list of TOK_CASE nodes, with at most one
00085  *                            TOK_DEFAULT node, or if there are let bindings
00086  *                            in the top level of the switch body's cases, a
00087  *                            TOK_LEXICALSCOPE node that contains the list of
00088  *                            TOK_CASE nodes.
00089  * TOK_CASE,    binary      pn_left: case expr or null if TOK_DEFAULT
00090  * TOK_DEFAULT              pn_right: TOK_LC node for this case's statements
00091  *                          pn_val: constant value if lookup or table switch
00092  * TOK_WHILE    binary      pn_left: cond, pn_right: body
00093  * TOK_DO       binary      pn_left: body, pn_right: cond
00094  * TOK_FOR      binary      pn_left: either
00095  *                            for/in loop: a binary TOK_IN node with
00096  *                              pn_left:  TOK_VAR or TOK_NAME to left of 'in'
00097  *                                if TOK_VAR, its pn_extra may have PNX_POPVAR
00098  *                                and PNX_FORINVAR bits set
00099  *                              pn_right: object expr to right of 'in'
00100  *                            for(;;) loop: a ternary TOK_RESERVED node with
00101  *                              pn_kid1:  init expr before first ';'
00102  *                              pn_kid2:  cond expr before second ';'
00103  *                              pn_kid3:  update expr after second ';'
00104  *                              any kid may be null
00105  *                          pn_right: body
00106  * TOK_THROW    unary       pn_op: JSOP_THROW, pn_kid: exception
00107  * TOK_TRY      ternary     pn_kid1: try block
00108  *                          pn_kid2: null or TOK_RESERVED list of
00109  *                          TOK_LEXICALSCOPE nodes, each with pn_expr pointing
00110  *                          to a TOK_CATCH node
00111  *                          pn_kid3: null or finally block
00112  * TOK_CATCH    ternary     pn_kid1: TOK_NAME, TOK_RB, or TOK_RC catch var node
00113  *                                   (TOK_RB or TOK_RC if destructuring)
00114  *                          pn_kid2: null or the catch guard expression
00115  *                          pn_kid3: catch block statements
00116  * TOK_BREAK    name        pn_atom: label or null
00117  * TOK_CONTINUE name        pn_atom: label or null
00118  * TOK_WITH     binary      pn_left: head expr, pn_right: body
00119  * TOK_VAR      list        pn_head: list of pn_count TOK_NAME nodes
00120  *                                   each name node has
00121  *                                     pn_atom: variable name
00122  *                                     pn_expr: initializer or null
00123  * TOK_RETURN   unary       pn_kid: return expr or null
00124  * TOK_SEMI     unary       pn_kid: expr or null statement
00125  * TOK_COLON    name        pn_atom: label, pn_expr: labeled statement
00126  *
00127  * <Expressions>
00128  * All left-associated binary trees of the same type are optimized into lists
00129  * to avoid recursion when processing expression chains.
00130  * TOK_COMMA    list        pn_head: list of pn_count comma-separated exprs
00131  * TOK_ASSIGN   binary      pn_left: lvalue, pn_right: rvalue
00132  *                          pn_op: JSOP_ADD for +=, etc.
00133  * TOK_HOOK     ternary     pn_kid1: cond, pn_kid2: then, pn_kid3: else
00134  * TOK_OR       binary      pn_left: first in || chain, pn_right: rest of chain
00135  * TOK_AND      binary      pn_left: first in && chain, pn_right: rest of chain
00136  * TOK_BITOR    binary      pn_left: left-assoc | expr, pn_right: ^ expr
00137  * TOK_BITXOR   binary      pn_left: left-assoc ^ expr, pn_right: & expr
00138  * TOK_BITAND   binary      pn_left: left-assoc & expr, pn_right: EQ expr
00139  * TOK_EQOP     binary      pn_left: left-assoc EQ expr, pn_right: REL expr
00140  *                          pn_op: JSOP_EQ, JSOP_NE, JSOP_NEW_EQ, JSOP_NEW_NE
00141  * TOK_RELOP    binary      pn_left: left-assoc REL expr, pn_right: SH expr
00142  *                          pn_op: JSOP_LT, JSOP_LE, JSOP_GT, JSOP_GE
00143  * TOK_SHOP     binary      pn_left: left-assoc SH expr, pn_right: ADD expr
00144  *                          pn_op: JSOP_LSH, JSOP_RSH, JSOP_URSH
00145  * TOK_PLUS,    binary      pn_left: left-assoc ADD expr, pn_right: MUL expr
00146  *                          pn_extra: if a left-associated binary TOK_PLUS
00147  *                            tree has been flattened into a list (see above
00148  *                            under <Expressions>), pn_extra will contain
00149  *                            PNX_STRCAT if at least one list element is a
00150  *                            string literal (TOK_STRING); if such a list has
00151  *                            any non-string, non-number term, pn_extra will
00152  *                            contain PNX_CANTFOLD.
00153  *                          pn_
00154  * TOK_MINUS                pn_op: JSOP_ADD, JSOP_SUB
00155  * TOK_STAR,    binary      pn_left: left-assoc MUL expr, pn_right: UNARY expr
00156  * TOK_DIVOP                pn_op: JSOP_MUL, JSOP_DIV, JSOP_MOD
00157  * TOK_UNARYOP  unary       pn_kid: UNARY expr, pn_op: JSOP_NEG, JSOP_POS,
00158  *                          JSOP_NOT, JSOP_BITNOT, JSOP_TYPEOF, JSOP_VOID
00159  * TOK_INC,     unary       pn_kid: MEMBER expr
00160  * TOK_DEC
00161  * TOK_NEW      list        pn_head: list of ctor, arg1, arg2, ... argN
00162  *                          pn_count: 1 + N (where N is number of args)
00163  *                          ctor is a MEMBER expr
00164  * TOK_DELETE   unary       pn_kid: MEMBER expr
00165  * TOK_DOT,     name        pn_expr: MEMBER expr to left of .
00166  * TOK_DBLDOT               pn_atom: name to right of .
00167  * TOK_LB       binary      pn_left: MEMBER expr to left of [
00168  *                          pn_right: expr between [ and ]
00169  * TOK_LP       list        pn_head: list of call, arg1, arg2, ... argN
00170  *                          pn_count: 1 + N (where N is number of args)
00171  *                          call is a MEMBER expr naming a callable object
00172  * TOK_RB       list        pn_head: list of pn_count array element exprs
00173  *                          [,,] holes are represented by TOK_COMMA nodes
00174  *                          #n=[...] produces TOK_DEFSHARP at head of list
00175  *                          pn_extra: PN_ENDCOMMA if extra comma at end
00176  * TOK_RC       list        pn_head: list of pn_count TOK_COLON nodes where
00177  *                          each has pn_left: property id, pn_right: value
00178  *                          #n={...} produces TOK_DEFSHARP at head of list
00179  * TOK_DEFSHARP unary       pn_num: jsint value of n in #n=
00180  *                          pn_kid: null for #n=[...] and #n={...}, primary
00181  *                          if #n=primary for function, paren, name, object
00182  *                          literal expressions
00183  * TOK_USESHARP nullary     pn_num: jsint value of n in #n#
00184  * TOK_RP       unary       pn_kid: parenthesized expression
00185  * TOK_NAME,    name        pn_atom: name, string, or object atom
00186  * TOK_STRING,              pn_op: JSOP_NAME, JSOP_STRING, or JSOP_OBJECT, or
00187  *                                 JSOP_REGEXP
00188  * TOK_OBJECT               If JSOP_NAME, pn_op may be JSOP_*ARG or JSOP_*VAR
00189  *                          with pn_slot >= 0 and pn_attrs telling const-ness
00190  * TOK_NUMBER   dval        pn_dval: double value of numeric literal
00191  * TOK_PRIMARY  nullary     pn_op: JSOp bytecode
00192  *
00193  * <E4X node descriptions>
00194  * TOK_ANYNAME  nullary     pn_op: JSOP_ANYNAME
00195  *                          pn_atom: cx->runtime->atomState.starAtom
00196  * TOK_AT       unary       pn_op: JSOP_TOATTRNAME; pn_kid attribute id/expr
00197  * TOK_DBLCOLON binary      pn_op: JSOP_QNAME
00198  *                          pn_left: TOK_ANYNAME or TOK_NAME node
00199  *                          pn_right: TOK_STRING "*" node, or expr within []
00200  *              name        pn_op: JSOP_QNAMECONST
00201  *                          pn_expr: TOK_ANYNAME or TOK_NAME left operand
00202  *                          pn_atom: name on right of ::
00203  * TOK_XMLELEM  list        XML element node
00204  *                          pn_head: start tag, content1, ... contentN, end tag
00205  *                          pn_count: 2 + N where N is number of content nodes
00206  *                                    N may be > x.length() if {expr} embedded
00207  * TOK_XMLLIST  list        XML list node
00208  *                          pn_head: content1, ... contentN
00209  * TOK_XMLSTAGO, list       XML start, end, and point tag contents
00210  * TOK_XMLETAGC,            pn_head: tag name or {expr}, ... XML attrs ...
00211  * TOK_XMLPTAGO
00212  * TOK_XMLNAME  nullary     pn_atom: XML name, with no {expr} embedded
00213  * TOK_XMLNAME  list        pn_head: tag name or {expr}, ... name or {expr}
00214  * TOK_XMLATTR, nullary     pn_atom: attribute value string; pn_op: JSOP_STRING
00215  * TOK_XMLCDATA,
00216  * TOK_XMLCOMMENT
00217  * TOK_XMLPI    nullary     pn_atom: XML processing instruction target
00218  *                          pn_atom2: XML PI content, or null if no content
00219  * TOK_XMLTEXT  nullary     pn_atom: marked-up text, or null if empty string
00220  * TOK_LC       unary       {expr} in XML tag or content; pn_kid is expr
00221  *
00222  * So an XML tag with no {expr} and three attributes is a list with the form:
00223  *
00224  *    (tagname attrname1 attrvalue1 attrname2 attrvalue2 attrname2 attrvalue3)
00225  *
00226  * An XML tag with embedded expressions like so:
00227  *
00228  *    <name1{expr1} name2{expr2}name3={expr3}>
00229  *
00230  * would have the form:
00231  *
00232  *    ((name1 {expr1}) (name2 {expr2} name3) {expr3})
00233  *
00234  * where () bracket a list with elements separated by spaces, and {expr} is a
00235  * TOK_LC unary node with expr as its kid.
00236  *
00237  * Thus, the attribute name/value pairs occupy successive odd and even list
00238  * locations, where pn_head is the TOK_XMLNAME node at list location 0.  The
00239  * parser builds the same sort of structures for elements:
00240  *
00241  *    <a x={x}>Hi there!<b y={y}>How are you?</b><answer>{x + y}</answer></a>
00242  *
00243  * translates to:
00244  *
00245  *    ((a x {x}) 'Hi there!' ((b y {y}) 'How are you?') ((answer) {x + y}))
00246  *
00247  * <Non-E4X node descriptions, continued>
00248  *
00249  * Label              Variant   Members
00250  * -----              -------   -------
00251  * TOK_LEXICALSCOPE   name      pn_op: JSOP_LEAVEBLOCK or JSOP_LEAVEBLOCKEXPR
00252  *                              pn_atom: block object
00253  *                              pn_expr: block body
00254  * TOK_ARRAYCOMP      list      pn_head: list of pn_count (1 or 2) elements
00255  *                              if pn_count is 2, first element is #n=[...]
00256  *                                last element is block enclosing for loop(s)
00257  *                                and optionally if-guarded TOK_ARRAYPUSH
00258  *                              pn_extra: stack slot, used during code gen
00259  * TOK_ARRAYPUSH      unary     pn_op: JSOP_ARRAYCOMP
00260  *                              pn_kid: array comprehension expression
00261  */
00262 typedef enum JSParseNodeArity {
00263     PN_FUNC     = -3,
00264     PN_LIST     = -2,
00265     PN_TERNARY  =  3,
00266     PN_BINARY   =  2,
00267     PN_UNARY    =  1,
00268     PN_NAME     = -1,
00269     PN_NULLARY  =  0
00270 } JSParseNodeArity;
00271 
00272 struct JSParseNode {
00273     uint16              pn_type;
00274     uint8               pn_op;
00275     int8                pn_arity;
00276     JSTokenPos          pn_pos;
00277     ptrdiff_t           pn_offset;      /* first generated bytecode offset */
00278     union {
00279         struct {                        /* TOK_FUNCTION node */
00280             JSAtom      *funAtom;       /* atomized function object */
00281             JSParseNode *body;          /* TOK_LC list of statements */
00282             uint32      flags;          /* accumulated tree context flags */
00283             uint32      tryCount;       /* count of try statements in body */
00284         } func;
00285         struct {                        /* list of next-linked nodes */
00286             JSParseNode *head;          /* first node in list */
00287             JSParseNode **tail;         /* ptr to ptr to last node in list */
00288             uint32      count;          /* number of nodes in list */
00289             uint32      extra;          /* extra flags, see below */
00290         } list;
00291         struct {                        /* ternary: if, for(;;), ?: */
00292             JSParseNode *kid1;          /* condition, discriminant, etc. */
00293             JSParseNode *kid2;          /* then-part, case list, etc. */
00294             JSParseNode *kid3;          /* else-part, default case, etc. */
00295         } ternary;
00296         struct {                        /* two kids if binary */
00297             JSParseNode *left;
00298             JSParseNode *right;
00299             jsval       val;            /* switch case value */
00300         } binary;
00301         struct {                        /* one kid if unary */
00302             JSParseNode *kid;
00303             jsint       num;            /* -1 or sharp variable number */
00304         } unary;
00305         struct {                        /* name, labeled statement, etc. */
00306             JSAtom      *atom;          /* name or label atom, null if slot */
00307             JSParseNode *expr;          /* object or initializer */
00308             jsint       slot;           /* -1 or arg or local var slot */
00309             uintN       attrs;          /* attributes if local var or const */
00310         } name;
00311         struct {
00312             JSAtom      *atom;          /* first atom in pair */
00313             JSAtom      *atom2;         /* second atom in pair or null */
00314         } apair;
00315         jsdouble        dval;           /* aligned numeric literal value */
00316     } pn_u;
00317     JSParseNode         *pn_next;       /* to align dval and pn_u on RISCs */
00318     JSTokenStream       *pn_ts;         /* token stream for error reports */
00319     JSAtom              *pn_source;     /* saved source for decompilation */
00320 };
00321 
00322 #define pn_funAtom      pn_u.func.funAtom
00323 #define pn_body         pn_u.func.body
00324 #define pn_flags        pn_u.func.flags
00325 #define pn_tryCount     pn_u.func.tryCount
00326 #define pn_head         pn_u.list.head
00327 #define pn_tail         pn_u.list.tail
00328 #define pn_count        pn_u.list.count
00329 #define pn_extra        pn_u.list.extra
00330 #define pn_kid1         pn_u.ternary.kid1
00331 #define pn_kid2         pn_u.ternary.kid2
00332 #define pn_kid3         pn_u.ternary.kid3
00333 #define pn_left         pn_u.binary.left
00334 #define pn_right        pn_u.binary.right
00335 #define pn_val          pn_u.binary.val
00336 #define pn_kid          pn_u.unary.kid
00337 #define pn_num          pn_u.unary.num
00338 #define pn_atom         pn_u.name.atom
00339 #define pn_expr         pn_u.name.expr
00340 #define pn_slot         pn_u.name.slot
00341 #define pn_attrs        pn_u.name.attrs
00342 #define pn_dval         pn_u.dval
00343 #define pn_atom2        pn_u.apair.atom2
00344 
00345 /* PN_LIST pn_extra flags. */
00346 #define PNX_STRCAT      0x01            /* TOK_PLUS list has string term */
00347 #define PNX_CANTFOLD    0x02            /* TOK_PLUS list has unfoldable term */
00348 #define PNX_POPVAR      0x04            /* TOK_VAR last result needs popping */
00349 #define PNX_FORINVAR    0x08            /* TOK_VAR is left kid of TOK_IN node,
00350                                            which is left kid of TOK_FOR */
00351 #define PNX_ENDCOMMA    0x10            /* array literal has comma at end */
00352 #define PNX_XMLROOT     0x20            /* top-most node in XML literal tree */
00353 #define PNX_GROUPINIT   0x40            /* var [a, b] = [c, d]; unit list */
00354 #define PNX_NEEDBRACES  0x80            /* braces necessary due to closure */
00355 
00356 /*
00357  * Move pn2 into pn, preserving pn->pn_pos and pn->pn_offset and handing off
00358  * any kids in pn2->pn_u, by clearing pn2.
00359  */
00360 #define PN_MOVE_NODE(pn, pn2)                                                 \
00361     JS_BEGIN_MACRO                                                            \
00362         (pn)->pn_type = (pn2)->pn_type;                                       \
00363         (pn)->pn_op = (pn2)->pn_op;                                           \
00364         (pn)->pn_arity = (pn2)->pn_arity;                                     \
00365         (pn)->pn_u = (pn2)->pn_u;                                             \
00366         PN_CLEAR_NODE(pn2);                                                   \
00367     JS_END_MACRO
00368 
00369 #define PN_CLEAR_NODE(pn)                                                     \
00370     JS_BEGIN_MACRO                                                            \
00371         (pn)->pn_type = TOK_EOF;                                              \
00372         (pn)->pn_op = JSOP_NOP;                                               \
00373         (pn)->pn_arity = PN_NULLARY;                                          \
00374     JS_END_MACRO
00375 
00376 /* True if pn is a parsenode representing a literal constant. */
00377 #define PN_IS_CONSTANT(pn)                                                    \
00378     ((pn)->pn_type == TOK_NUMBER ||                                           \
00379      (pn)->pn_type == TOK_STRING ||                                           \
00380      ((pn)->pn_type == TOK_PRIMARY && (pn)->pn_op != JSOP_THIS))
00381 
00382 /*
00383  * Compute a pointer to the last JSParseNode element in a singly-linked list.
00384  * NB: list must be non-empty for correct PN_LAST usage!
00385  */
00386 #define PN_LAST(list) \
00387     ((JSParseNode *)((char *)(list)->pn_tail - offsetof(JSParseNode, pn_next)))
00388 
00389 #define PN_INIT_LIST(list)                                                    \
00390     JS_BEGIN_MACRO                                                            \
00391         (list)->pn_head = NULL;                                               \
00392         (list)->pn_tail = &(list)->pn_head;                                   \
00393         (list)->pn_count = (list)->pn_extra = 0;                              \
00394     JS_END_MACRO
00395 
00396 #define PN_INIT_LIST_1(list, pn)                                              \
00397     JS_BEGIN_MACRO                                                            \
00398         (list)->pn_head = (pn);                                               \
00399         (list)->pn_tail = &(pn)->pn_next;                                     \
00400         (list)->pn_count = 1;                                                 \
00401         (list)->pn_extra = 0;                                                 \
00402     JS_END_MACRO
00403 
00404 #define PN_APPEND(list, pn)                                                   \
00405     JS_BEGIN_MACRO                                                            \
00406         *(list)->pn_tail = (pn);                                              \
00407         (list)->pn_tail = &(pn)->pn_next;                                     \
00408         (list)->pn_count++;                                                   \
00409     JS_END_MACRO
00410 
00411 /*
00412  * Parse a top-level JS script.
00413  *
00414  * The caller must prevent the GC from running while this function is active,
00415  * because atoms and function newborns are not rooted yet.
00416  */
00417 extern JS_FRIEND_API(JSParseNode *)
00418 js_ParseTokenStream(JSContext *cx, JSObject *chain, JSTokenStream *ts);
00419 
00420 extern JS_FRIEND_API(JSBool)
00421 js_CompileTokenStream(JSContext *cx, JSObject *chain, JSTokenStream *ts,
00422                       JSCodeGenerator *cg);
00423 
00424 extern JSBool
00425 js_CompileFunctionBody(JSContext *cx, JSTokenStream *ts, JSFunction *fun);
00426 
00427 extern JSBool
00428 js_FoldConstants(JSContext *cx, JSParseNode *pn, JSTreeContext *tc);
00429 
00430 #if JS_HAS_XML_SUPPORT
00431 JS_FRIEND_API(JSParseNode *)
00432 js_ParseXMLTokenStream(JSContext *cx, JSObject *chain, JSTokenStream *ts,
00433                        JSBool allowList);
00434 #endif
00435 
00436 JS_END_EXTERN_C
00437 
00438 #endif /* jsparse_h___ */