src/dom/js/jsparse.h

   1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  *
   3  * ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is Mozilla Communicator client code, released
  17  * March 31, 1998.
  18  *
  19  * The Initial Developer of the Original Code is
  20  * Netscape Communications Corporation.
  21  * Portions created by the Initial Developer are Copyright (C) 1998
  22  * the Initial Developer. All Rights Reserved.
  23  *
  24  * Contributor(s):
  25  *
  26  * Alternatively, the contents of this file may be used under the terms of
  27  * either of the GNU General Public License Version 2 or later (the "GPL"),
  28  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  29  * in which case the provisions of the GPL or the LGPL are applicable instead
  30  * of those above. If you wish to allow use of your version of this file only
  31  * under the terms of either the GPL or the LGPL, and not to allow others to
  32  * use your version of this file under the terms of the MPL, indicate your
  33  * decision by deleting the provisions above and replace them with the notice
  34  * and other provisions required by the GPL or the LGPL. If you do not delete
  35  * the provisions above, a recipient may use your version of this file under
  36  * the terms of any one of the MPL, the GPL or the LGPL.
  37  *
  38  * ***** END LICENSE BLOCK ***** */
  39
  40 #ifndef jsparse_h___
  41 #define jsparse_h___
  42 /*
  43  * JS parser definitions.
  44  */
  45 #include "jsprvtd.h"
  46 #include "jspubtd.h"
  47 #include "jsscan.h"
  48
  49 JS_BEGIN_EXTERN_C
  50
  51 /*
  52  * Parsing builds a tree of nodes that directs code generation.  This tree is
  53  * not a concrete syntax tree in all respects (for example, || and && are left
  54  * associative, but (A && B && C) translates into the right-associated tree
  55  * <A && <B && C>> so that code generation can emit a left-associative branch
  56  * around <B && C> when A is false).  Nodes are labeled by token type, with a
  57  * JSOp secondary label when needed:
  58  *
  59  * Label        Variant     Members
  60  * -----        -------     -------
  61  * <Definitions>
  62  * TOK_FUNCTION func        pn_funAtom: atom holding function object containing
  63  *                            arg and var properties.  We create the function
  64  *                            object at parse (not emit) time to specialize arg
  65  *                            and var bytecodes early.
  66  *                          pn_body: TOK_LC node for function body statements
  67  *                          pn_flags: TCF_FUN_* flags (see jsemit.h) collected
  68  *                            while parsing the function's body
  69  *                          pn_tryCount: of try statements in function
  70  *
  71  * <Statements>
  72  * TOK_LC       list        pn_head: list of pn_count statements
  73  * TOK_EXPORT   list        pn_head: list of pn_count TOK_NAMEs or one TOK_STAR
  74  *                            (which is not a multiply node)
  75  * TOK_IMPORT   list        pn_head: list of pn_count sub-trees of the form
  76  *                            a.b.*, a[b].*, a.*, a.b, or a[b] -- but never a.
  77  *                            Each member is expressed with TOK_DOT or TOK_LB.
  78  *                            Each sub-tree's root node has a pn_op in the set
  79  *                            JSOP_IMPORT{ALL,PROP,ELEM}
  80  * TOK_IF       ternary     pn_kid1: cond, pn_kid2: then, pn_kid3: else or null
  81  * TOK_SWITCH   binary      pn_left: discriminant
  82  *                          pn_right: list of TOK_CASE nodes, with at most one
  83  *                            TOK_DEFAULT node
  84  * TOK_CASE,    binary      pn_left: case expr or null if TOK_DEFAULT
  85  * TOK_DEFAULT              pn_right: TOK_LC node for this case's statements
  86  *                          pn_val: constant value if lookup or table switch
  87  * TOK_WHILE    binary      pn_left: cond, pn_right: body
  88  * TOK_DO       binary      pn_left: body, pn_right: cond
  89  * TOK_FOR      binary      pn_left: either
  90  *                            for/in loop: a binary TOK_IN node with
  91  *                              pn_left:  TOK_VAR or TOK_NAME to left of 'in'
  92  *                                if TOK_VAR, its pn_extra may have PNX_POPVAR
  93  *                                and PNX_FORINVAR bits set
  94  *                              pn_right: object expr to right of 'in'
  95  *                            for(;;) loop: a ternary TOK_RESERVED node with
  96  *                              pn_kid1:  init expr before first ';'
  97  *                              pn_kid2:  cond expr before second ';'
  98  *                              pn_kid3:  update expr after second ';'
  99  *                              any kid may be null
 100  *                          pn_right: body
 101  * TOK_THROW    unary       pn_op: JSOP_THROW, pn_kid: exception
 102  * TOK_TRY      ternary     pn_kid1: try block
 103  *                          pn_kid2: catch blocks or null
 104  *                          pn_kid3: finally block or null
 105  * TOK_CATCH    ternary     pn_kid1: PN_NAME node for catch var (with pn_expr
 106  *                                   null or the catch guard expression)
 107  *                          pn_kid2: more catch blocks or null
 108  *                          pn_kid3: catch block statements
 109  * TOK_BREAK    name        pn_atom: label or null
 110  * TOK_CONTINUE name        pn_atom: label or null
 111  * TOK_WITH     binary      pn_left: head expr, pn_right: body
 112  * TOK_VAR      list        pn_head: list of pn_count TOK_NAME nodes
 113  *                                   each name node has
 114  *                                     pn_atom: variable name
 115  *                                     pn_expr: initializer or null
 116  * TOK_RETURN   unary       pn_kid: return expr or null
 117  * TOK_SEMI     unary       pn_kid: expr or null statement
 118  * TOK_COLON    name        pn_atom: label, pn_expr: labeled statement
 119  *
 120  * <Expressions>
 121  * All left-associated binary trees of the same type are optimized into lists
 122  * to avoid recursion when processing expression chains.
 123  * TOK_COMMA    list        pn_head: list of pn_count comma-separated exprs
 124  * TOK_ASSIGN   binary      pn_left: lvalue, pn_right: rvalue
 125  *                          pn_op: JSOP_ADD for +=, etc.
 126  * TOK_HOOK     ternary     pn_kid1: cond, pn_kid2: then, pn_kid3: else
 127  * TOK_OR       binary      pn_left: first in || chain, pn_right: rest of chain
 128  * TOK_AND      binary      pn_left: first in && chain, pn_right: rest of chain
 129  * TOK_BITOR    binary      pn_left: left-assoc | expr, pn_right: ^ expr
 130  * TOK_BITXOR   binary      pn_left: left-assoc ^ expr, pn_right: & expr
 131  * TOK_BITAND   binary      pn_left: left-assoc & expr, pn_right: EQ expr
 132  * TOK_EQOP     binary      pn_left: left-assoc EQ expr, pn_right: REL expr
 133  *                          pn_op: JSOP_EQ, JSOP_NE, JSOP_NEW_EQ, JSOP_NEW_NE
 134  * TOK_RELOP    binary      pn_left: left-assoc REL expr, pn_right: SH expr
 135  *                          pn_op: JSOP_LT, JSOP_LE, JSOP_GT, JSOP_GE
 136  * TOK_SHOP     binary      pn_left: left-assoc SH expr, pn_right: ADD expr
 137  *                          pn_op: JSOP_LSH, JSOP_RSH, JSOP_URSH
 138  * TOK_PLUS,    binary      pn_left: left-assoc ADD expr, pn_right: MUL expr
 139  *                          pn_extra: if a left-associated binary TOK_PLUS
 140  *                            tree has been flattened into a list (see above
 141  *                            under <Expressions>), pn_extra will contain
 142  *                            PNX_STRCAT if at least one list element is a
 143  *                            string literal (TOK_STRING); if such a list has
 144  *                            any non-string, non-number term, pn_extra will
 145  *                            contain PNX_CANTFOLD.
 146  *                          pn_
 147  * TOK_MINUS                pn_op: JSOP_ADD, JSOP_SUB
 148  * TOK_STAR,    binary      pn_left: left-assoc MUL expr, pn_right: UNARY expr
 149  * TOK_DIVOP                pn_op: JSOP_MUL, JSOP_DIV, JSOP_MOD
 150  * TOK_UNARYOP  unary       pn_kid: UNARY expr, pn_op: JSOP_NEG, JSOP_POS,
 151  *                          JSOP_NOT, JSOP_BITNOT, JSOP_TYPEOF, JSOP_VOID
 152  * TOK_INC,     unary       pn_kid: MEMBER expr
 153  * TOK_DEC
 154  * TOK_NEW      list        pn_head: list of ctor, arg1, arg2, ... argN
 155  *                          pn_count: 1 + N (where N is number of args)
 156  *                          ctor is a MEMBER expr
 157  * TOK_DELETE   unary       pn_kid: MEMBER expr
 158  * TOK_DOT      name        pn_expr: MEMBER expr to left of .
 159  *                          pn_atom: name to right of .
 160  * TOK_LB       binary      pn_left: MEMBER expr to left of [
 161  *                          pn_right: expr between [ and ]
 162  * TOK_LP       list        pn_head: list of call, arg1, arg2, ... argN
 163  *                          pn_count: 1 + N (where N is number of args)
 164  *                          call is a MEMBER expr naming a callable object
 165  * TOK_RB       list        pn_head: list of pn_count array element exprs
 166  *                          [,,] holes are represented by TOK_COMMA nodes
 167  *                          #n=[...] produces TOK_DEFSHARP at head of list
 168  *                          pn_extra: PN_ENDCOMMA if extra comma at end
 169  * TOK_RC       list        pn_head: list of pn_count TOK_COLON nodes where
 170  *                          each has pn_left: property id, pn_right: value
 171  *                          #n={...} produces TOK_DEFSHARP at head of list
 172  * TOK_DEFSHARP unary       pn_num: jsint value of n in #n=
 173  *                          pn_kid: null for #n=[...] and #n={...}, primary
 174  *                          if #n=primary for function, paren, name, object
 175  *                          literal expressions
 176  * TOK_USESHARP nullary     pn_num: jsint value of n in #n#
 177  * TOK_RP       unary       pn_kid: parenthesized expression
 178  * TOK_NAME,    name        pn_atom: name, string, or object atom
 179  * TOK_STRING,              pn_op: JSOP_NAME, JSOP_STRING, or JSOP_OBJECT, or
 180  *                                 JSOP_REGEXP
 181  * TOK_OBJECT               If JSOP_NAME, pn_op may be JSOP_*ARG or JSOP_*VAR
 182  *                          with pn_slot >= 0 and pn_attrs telling const-ness
 183  * TOK_NUMBER   dval        pn_dval: double value of numeric literal
 184  * TOK_PRIMARY  nullary     pn_op: JSOp bytecode
 185  */
 186 typedef enum JSParseNodeArity {
 187     PN_FUNC     = -3,
 188     PN_LIST     = -2,
 189     PN_TERNARY  =  3,
 190     PN_BINARY   =  2,
 191     PN_UNARY    =  1,
 192     PN_NAME     = -1,
 193     PN_NULLARY  =  0
 194 } JSParseNodeArity;
 195
 196 struct JSParseNode {
 197     JSTokenType         pn_type;
 198     JSTokenPos          pn_pos;
 199     JSOp                pn_op;
 200     ptrdiff_t           pn_offset;      /* first generated bytecode offset */
 201     JSParseNodeArity    pn_arity;
 202     union {
 203         struct {                        /* TOK_FUNCTION node */
 204             JSAtom      *funAtom;       /* atomized function object */
 205             JSParseNode *body;          /* TOK_LC list of statements */
 206             uint32      flags;          /* accumulated tree context flags */
 207             uint32      tryCount;       /* count of try statements in body */
 208         } func;
 209         struct {                        /* list of next-linked nodes */
 210             JSParseNode *head;          /* first node in list */
 211             JSParseNode **tail;         /* ptr to ptr to last node in list */
 212             uint32      count;          /* number of nodes in list */
 213             uint32      extra;          /* extra comma flag for [1,2,,] */
 214         } list;
 215         struct {                        /* ternary: if, for(;;), ?: */
 216             JSParseNode *kid1;          /* condition, discriminant, etc. */
 217             JSParseNode *kid2;          /* then-part, case list, etc. */
 218             JSParseNode *kid3;          /* else-part, default case, etc. */
 219         } ternary;
 220         struct {                        /* two kids if binary */
 221             JSParseNode *left;
 222             JSParseNode *right;
 223             jsval       val;            /* switch case value */
 224         } binary;
 225         struct {                        /* one kid if unary */
 226             JSParseNode *kid;
 227             jsint       num;            /* -1 or sharp variable number */
 228         } unary;
 229         struct {                        /* name, labeled statement, etc. */
 230             JSAtom      *atom;          /* name or label atom, null if slot */
 231             JSParseNode *expr;          /* object or initializer */
 232             jsint       slot;           /* -1 or arg or local var slot */
 233             uintN       attrs;          /* attributes if local var or const */
 234         } name;
 235         jsdouble        dval;           /* aligned numeric literal value */
 236     } pn_u;
 237     JSParseNode         *pn_next;       /* to align dval and pn_u on RISCs */
 238 };
 239
 240 #define pn_funAtom      pn_u.func.funAtom
 241 #define pn_body         pn_u.func.body
 242 #define pn_flags        pn_u.func.flags
 243 #define pn_tryCount     pn_u.func.tryCount
 244 #define pn_head         pn_u.list.head
 245 #define pn_tail         pn_u.list.tail
 246 #define pn_count        pn_u.list.count
 247 #define pn_extra        pn_u.list.extra
 248 #define pn_kid1         pn_u.ternary.kid1
 249 #define pn_kid2         pn_u.ternary.kid2
 250 #define pn_kid3         pn_u.ternary.kid3
 251 #define pn_left         pn_u.binary.left
 252 #define pn_right        pn_u.binary.right
 253 #define pn_val          pn_u.binary.val
 254 #define pn_kid          pn_u.unary.kid
 255 #define pn_num          pn_u.unary.num
 256 #define pn_atom         pn_u.name.atom
 257 #define pn_expr         pn_u.name.expr
 258 #define pn_slot         pn_u.name.slot
 259 #define pn_attrs        pn_u.name.attrs
 260 #define pn_dval         pn_u.dval
 261
 262 /* PN_LIST pn_extra flags. */
 263 #define PNX_STRCAT      0x01            /* TOK_PLUS list has string term */
 264 #define PNX_CANTFOLD    0x02            /* TOK_PLUS list has unfoldable term */
 265 #define PNX_POPVAR      0x04            /* TOK_VAR last result needs popping */
 266 #define PNX_FORINVAR    0x08            /* TOK_VAR is left kid of TOK_IN node,
 267                                            which is left kid of TOK_FOR */
 268 #define PNX_ENDCOMMA    0x10            /* array literal has comma at end */
 269
 270 /*
 271  * Move pn2 into pn, preserving pn->pn_pos and pn->pn_offset and handing off
 272  * any kids in pn2->pn_u, by clearing pn2.
 273  */
 274 #define PN_MOVE_NODE(pn, pn2)                                                 \
 275     JS_BEGIN_MACRO                                                            \
 276         (pn)->pn_type = (pn2)->pn_type;                                       \
 277         (pn)->pn_op = (pn2)->pn_op;                                           \
 278         (pn)->pn_arity = (pn2)->pn_arity;                                     \
 279         (pn)->pn_u = (pn2)->pn_u;                                             \
 280         PN_CLEAR_NODE(pn2);                                                   \
 281     JS_END_MACRO
 282
 283 #define PN_CLEAR_NODE(pn)                                                     \
 284     JS_BEGIN_MACRO                                                            \
 285         (pn)->pn_type = TOK_EOF;                                              \
 286         (pn)->pn_op = JSOP_NOP;                                               \
 287         (pn)->pn_arity = PN_NULLARY;                                          \
 288     JS_END_MACRO
 289
 290 /* True if pn is a parsenode representing a literal constant. */
 291 #define PN_IS_CONSTANT(pn)                                                    \
 292     ((pn)->pn_type == TOK_NUMBER ||                                           \
 293      (pn)->pn_type == TOK_STRING ||                                           \
 294      ((pn)->pn_type == TOK_PRIMARY && (pn)->pn_op != JSOP_THIS))
 295
 296 /*
 297  * Compute a pointer to the last JSParseNode element in a singly-linked list.
 298  * NB: list must be non-empty for correct PN_LAST usage!
 299  */
 300 #define PN_LAST(list) \
 301     ((JSParseNode *)((char *)(list)->pn_tail - offsetof(JSParseNode, pn_next)))
 302
 303 #define PN_INIT_LIST(list)                                                    \
 304     JS_BEGIN_MACRO                                                            \
 305         (list)->pn_head = NULL;                                               \
 306         (list)->pn_tail = &(list)->pn_head;                                   \
 307         (list)->pn_count = 0;                                                 \
 308     JS_END_MACRO
 309
 310 #define PN_INIT_LIST_1(list, pn)                                              \
 311     JS_BEGIN_MACRO                                                            \
 312         (list)->pn_head = (pn);                                               \
 313         (list)->pn_tail = &(pn)->pn_next;                                     \
 314         (list)->pn_count = 1;                                                 \
 315     JS_END_MACRO
 316
 317 #define PN_APPEND(list, pn)                                                   \
 318     JS_BEGIN_MACRO                                                            \
 319         *(list)->pn_tail = (pn);                                              \
 320         (list)->pn_tail = &(pn)->pn_next;                                     \
 321         (list)->pn_count++;                                                   \
 322     JS_END_MACRO
 323
 324 /*
 325  * Parse a top-level JS script.
 326  *
 327  * The caller must prevent the GC from running while this function is active,
 328  * because atoms and function newborns are not rooted yet.
 329  */
 330 extern JS_FRIEND_API(JSParseNode *)
 331 js_ParseTokenStream(JSContext *cx, JSObject *chain, JSTokenStream *ts);
 332
 333 extern JS_FRIEND_API(JSBool)
 334 js_CompileTokenStream(JSContext *cx, JSObject *chain, JSTokenStream *ts,
 335                       JSCodeGenerator *cg);
 336
 337 extern JSBool
 338 js_CompileFunctionBody(JSContext *cx, JSTokenStream *ts, JSFunction *fun);
 339
 340 extern JSBool
 341 js_FoldConstants(JSContext *cx, JSParseNode *pn, JSTreeContext *tc);
 342
 343 JS_END_EXTERN_C
 344
 345 #endif /* jsparse_h___ */