diff -r 000000000000 -r 6474c204b198 js/src/frontend/ParseNode.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/js/src/frontend/ParseNode.cpp Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,767 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * vim: set ts=8 sts=4 et sw=4 tw=99: + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "frontend/ParseNode-inl.h" + +#include "frontend/Parser.h" + +#include "jscntxtinlines.h" + +using namespace js; +using namespace js::frontend; + +using mozilla::IsFinite; + +/* + * Asserts to verify assumptions behind pn_ macros. + */ +#define pn_offsetof(m) offsetof(ParseNode, m) + +JS_STATIC_ASSERT(pn_offsetof(pn_link) == pn_offsetof(dn_uses)); + +#undef pn_offsetof + +#ifdef DEBUG +void +ParseNode::checkListConsistency() +{ + JS_ASSERT(isArity(PN_LIST)); + ParseNode **tail; + uint32_t count = 0; + if (pn_head) { + ParseNode *pn, *last; + for (pn = last = pn_head; pn; last = pn, pn = pn->pn_next, count++) + ; + tail = &last->pn_next; + } else { + tail = &pn_head; + } + JS_ASSERT(pn_tail == tail); + JS_ASSERT(pn_count == count); +} +#endif + +/* Add |node| to |parser|'s free node list. */ +void +ParseNodeAllocator::freeNode(ParseNode *pn) +{ + /* Catch back-to-back dup recycles. */ + JS_ASSERT(pn != freelist); + + /* + * It's too hard to clear these nodes from the AtomDefnMaps, etc. that + * hold references to them, so we never free them. It's our caller's job to + * recognize and process these, since their children do need to be dealt + * with. + */ + JS_ASSERT(!pn->isUsed()); + JS_ASSERT(!pn->isDefn()); + +#ifdef DEBUG + /* Poison the node, to catch attempts to use it without initializing it. */ + memset(pn, 0xab, sizeof(*pn)); +#endif + + pn->pn_next = freelist; + freelist = pn; +} + +namespace { + +/* + * A work pool of ParseNodes. The work pool is a stack, chained together + * by nodes' pn_next fields. We use this to avoid creating deep C++ stacks + * when recycling deep parse trees. + * + * Since parse nodes are probably allocated in something close to the order + * they appear in a depth-first traversal of the tree, making the work pool + * a stack should give us pretty good locality. + */ +class NodeStack { + public: + NodeStack() : top(nullptr) { } + bool empty() { return top == nullptr; } + void push(ParseNode *pn) { + pn->pn_next = top; + top = pn; + } + void pushUnlessNull(ParseNode *pn) { if (pn) push(pn); } + /* Push the children of the PN_LIST node |pn| on the stack. */ + void pushList(ParseNode *pn) { + /* This clobbers pn->pn_head if the list is empty; should be okay. */ + *pn->pn_tail = top; + top = pn->pn_head; + } + ParseNode *pop() { + JS_ASSERT(!empty()); + ParseNode *hold = top; /* my kingdom for a prog1 */ + top = top->pn_next; + return hold; + } + private: + ParseNode *top; +}; + +} /* anonymous namespace */ + +/* + * Push the children of |pn| on |stack|. Return true if |pn| itself could be + * safely recycled, or false if it must be cleaned later (pn_used and pn_defn + * nodes, and all function nodes; see comments for CleanFunctionList in + * SemanticAnalysis.cpp). Some callers want to free |pn|; others + * (js::ParseNodeAllocator::prepareNodeForMutation) don't care about |pn|, and + * just need to take care of its children. + */ +static bool +PushNodeChildren(ParseNode *pn, NodeStack *stack) +{ + switch (pn->getArity()) { + case PN_CODE: + /* + * Function nodes are linked into the function box tree, and may appear + * on method lists. Both of those lists are singly-linked, so trying to + * update them now could result in quadratic behavior when recycling + * trees containing many functions; and the lists can be very long. So + * we put off cleaning the lists up until just before function + * analysis, when we call CleanFunctionList. + * + * In fact, we can't recycle the parse node yet, either: it may appear + * on a method list, and reusing the node would corrupt that. Instead, + * we clear its pn_funbox pointer to mark it as deleted; + * CleanFunctionList recycles it as well. + * + * We do recycle the nodes around it, though, so we must clear pointers + * to them to avoid leaving dangling references where someone can find + * them. + */ + pn->pn_funbox = nullptr; + stack->pushUnlessNull(pn->pn_body); + pn->pn_body = nullptr; + return false; + + case PN_NAME: + /* + * Because used/defn nodes appear in AtomDefnMaps and elsewhere, we + * don't recycle them. (We'll recover their storage when we free the + * temporary arena.) However, we do recycle the nodes around them, so + * clean up the pointers to avoid dangling references. The top-level + * decls table carries references to them that later iterations through + * the compileScript loop may find, so they need to be neat. + * + * pn_expr and pn_lexdef share storage; the latter isn't an owning + * reference. + */ + if (!pn->isUsed()) { + stack->pushUnlessNull(pn->pn_expr); + pn->pn_expr = nullptr; + } + return !pn->isUsed() && !pn->isDefn(); + + case PN_LIST: + pn->checkListConsistency(); + stack->pushList(pn); + break; + case PN_TERNARY: + stack->pushUnlessNull(pn->pn_kid1); + stack->pushUnlessNull(pn->pn_kid2); + stack->pushUnlessNull(pn->pn_kid3); + break; + case PN_BINARY: + case PN_BINARY_OBJ: + if (pn->pn_left != pn->pn_right) + stack->pushUnlessNull(pn->pn_left); + stack->pushUnlessNull(pn->pn_right); + break; + case PN_UNARY: + stack->pushUnlessNull(pn->pn_kid); + break; + case PN_NULLARY: + return !pn->isUsed() && !pn->isDefn(); + default: + ; + } + + return true; +} + +/* + * Prepare |pn| to be mutated in place into a new kind of node. Recycle all + * |pn|'s recyclable children (but not |pn| itself!), and disconnect it from + * metadata structures (the function box tree). + */ +void +ParseNodeAllocator::prepareNodeForMutation(ParseNode *pn) +{ + if (!pn->isArity(PN_NULLARY)) { + /* Put |pn|'s children (but not |pn| itself) on a work stack. */ + NodeStack stack; + PushNodeChildren(pn, &stack); + /* + * For each node on the work stack, push its children on the work stack, + * and free the node if we can. + */ + while (!stack.empty()) { + pn = stack.pop(); + if (PushNodeChildren(pn, &stack)) + freeNode(pn); + } + } +} + +/* + * Return the nodes in the subtree |pn| to the parser's free node list, for + * reallocation. + */ +ParseNode * +ParseNodeAllocator::freeTree(ParseNode *pn) +{ + if (!pn) + return nullptr; + + ParseNode *savedNext = pn->pn_next; + + NodeStack stack; + for (;;) { + if (PushNodeChildren(pn, &stack)) + freeNode(pn); + if (stack.empty()) + break; + pn = stack.pop(); + } + + return savedNext; +} + +/* + * Allocate a ParseNode from parser's node freelist or, failing that, from + * cx's temporary arena. + */ +void * +ParseNodeAllocator::allocNode() +{ + if (ParseNode *pn = freelist) { + freelist = pn->pn_next; + return pn; + } + + void *p = alloc.alloc(sizeof (ParseNode)); + if (!p) + js_ReportOutOfMemory(cx); + return p; +} + +/* used only by static create methods of subclasses */ + +ParseNode * +ParseNode::create(ParseNodeKind kind, ParseNodeArity arity, FullParseHandler *handler) +{ + const Token &tok = handler->currentToken(); + return handler->new_(kind, JSOP_NOP, arity, tok.pos); +} + +ParseNode * +ParseNode::append(ParseNodeKind kind, JSOp op, ParseNode *left, ParseNode *right, + FullParseHandler *handler) +{ + if (!left || !right) + return nullptr; + + JS_ASSERT(left->isKind(kind) && left->isOp(op) && (js_CodeSpec[op].format & JOF_LEFTASSOC)); + + ListNode *list; + if (left->pn_arity == PN_LIST) { + list = &left->as(); + } else { + ParseNode *pn1 = left->pn_left, *pn2 = left->pn_right; + list = handler->new_(kind, op, pn1); + if (!list) + return nullptr; + list->append(pn2); + } + + list->append(right); + list->pn_pos.end = right->pn_pos.end; + + return list; +} + +ParseNode * +ParseNode::newBinaryOrAppend(ParseNodeKind kind, JSOp op, ParseNode *left, ParseNode *right, + FullParseHandler *handler, ParseContext *pc, + bool foldConstants) +{ + if (!left || !right) + return nullptr; + + /* + * Ensure that the parse tree is faithful to the source when "use asm" (for + * the purpose of type checking). + */ + if (pc->useAsmOrInsideUseAsm()) + return handler->new_(kind, op, left, right); + + /* + * Flatten a left-associative (left-heavy) tree of a given operator into + * a list to reduce js::FoldConstants and js::frontend::EmitTree recursion. + */ + if (left->isKind(kind) && left->isOp(op) && (js_CodeSpec[op].format & JOF_LEFTASSOC)) + return append(kind, op, left, right, handler); + + return handler->new_(kind, op, left, right); +} + +const char * +Definition::kindString(Kind kind) +{ + static const char * const table[] = { + "", js_var_str, js_const_str, js_let_str, js_function_str, "argument", "unknown" + }; + + JS_ASSERT(unsigned(kind) <= unsigned(ARG)); + return table[kind]; +} + +namespace js { +namespace frontend { + +/* + * This function assumes the cloned tree is for use in the same statement and + * binding context as the original tree. + */ +template <> +ParseNode * +Parser::cloneParseTree(ParseNode *opn) +{ + JS_CHECK_RECURSION(context, return nullptr); + + ParseNode *pn = handler.new_(opn->getKind(), opn->getOp(), opn->getArity(), + opn->pn_pos); + if (!pn) + return nullptr; + pn->setInParens(opn->isInParens()); + pn->setDefn(opn->isDefn()); + pn->setUsed(opn->isUsed()); + + switch (pn->getArity()) { +#define NULLCHECK(e) JS_BEGIN_MACRO if (!(e)) return nullptr; JS_END_MACRO + + case PN_CODE: + NULLCHECK(pn->pn_funbox = newFunctionBox(pn, opn->pn_funbox->function(), pc, + Directives(/* strict = */ opn->pn_funbox->strict), + opn->pn_funbox->generatorKind())); + NULLCHECK(pn->pn_body = cloneParseTree(opn->pn_body)); + pn->pn_cookie = opn->pn_cookie; + pn->pn_dflags = opn->pn_dflags; + pn->pn_blockid = opn->pn_blockid; + break; + + case PN_LIST: + pn->makeEmpty(); + for (ParseNode *opn2 = opn->pn_head; opn2; opn2 = opn2->pn_next) { + ParseNode *pn2; + NULLCHECK(pn2 = cloneParseTree(opn2)); + pn->append(pn2); + } + pn->pn_xflags = opn->pn_xflags; + break; + + case PN_TERNARY: + NULLCHECK(pn->pn_kid1 = cloneParseTree(opn->pn_kid1)); + NULLCHECK(pn->pn_kid2 = cloneParseTree(opn->pn_kid2)); + NULLCHECK(pn->pn_kid3 = cloneParseTree(opn->pn_kid3)); + break; + + case PN_BINARY: + NULLCHECK(pn->pn_left = cloneParseTree(opn->pn_left)); + if (opn->pn_right != opn->pn_left) + NULLCHECK(pn->pn_right = cloneParseTree(opn->pn_right)); + else + pn->pn_right = pn->pn_left; + pn->pn_iflags = opn->pn_iflags; + break; + + case PN_BINARY_OBJ: + NULLCHECK(pn->pn_left = cloneParseTree(opn->pn_left)); + if (opn->pn_right != opn->pn_left) + NULLCHECK(pn->pn_right = cloneParseTree(opn->pn_right)); + else + pn->pn_right = pn->pn_left; + pn->pn_binary_obj = opn->pn_binary_obj; + break; + + case PN_UNARY: + NULLCHECK(pn->pn_kid = cloneParseTree(opn->pn_kid)); + break; + + case PN_NAME: + // PN_NAME could mean several arms in pn_u, so copy the whole thing. + pn->pn_u = opn->pn_u; + if (opn->isUsed()) { + /* + * The old name is a use of its pn_lexdef. Make the clone also be a + * use of that definition. + */ + Definition *dn = pn->pn_lexdef; + + pn->pn_link = dn->dn_uses; + dn->dn_uses = pn; + } else if (opn->pn_expr) { + NULLCHECK(pn->pn_expr = cloneParseTree(opn->pn_expr)); + + /* + * If the old name is a definition, the new one has pn_defn set. + * Make the old name a use of the new node. + */ + if (opn->isDefn()) { + opn->setDefn(false); + handler.linkUseToDef(opn, (Definition *) pn); + } + } + break; + + case PN_NULLARY: + pn->pn_u = opn->pn_u; + break; + +#undef NULLCHECK + } + return pn; +} + +/* + * Used by Parser::forStatement and comprehensionTail to clone the TARGET in + * for (var/const/let TARGET in EXPR) + * + * opn must be the pn_head of a node produced by Parser::variables, so its form + * is known to be LHS = NAME | [LHS] | {id:LHS}. + * + * The cloned tree is for use only in the same statement and binding context as + * the original tree. + */ +template <> +ParseNode * +Parser::cloneLeftHandSide(ParseNode *opn) +{ + ParseNode *pn = handler.new_(opn->getKind(), opn->getOp(), opn->getArity(), + opn->pn_pos); + if (!pn) + return nullptr; + pn->setInParens(opn->isInParens()); + pn->setDefn(opn->isDefn()); + pn->setUsed(opn->isUsed()); + + if (opn->isArity(PN_LIST)) { + JS_ASSERT(opn->isKind(PNK_ARRAY) || opn->isKind(PNK_OBJECT)); + pn->makeEmpty(); + for (ParseNode *opn2 = opn->pn_head; opn2; opn2 = opn2->pn_next) { + ParseNode *pn2; + if (opn->isKind(PNK_OBJECT)) { + JS_ASSERT(opn2->isArity(PN_BINARY)); + JS_ASSERT(opn2->isKind(PNK_COLON)); + + ParseNode *tag = cloneParseTree(opn2->pn_left); + if (!tag) + return nullptr; + ParseNode *target = cloneLeftHandSide(opn2->pn_right); + if (!target) + return nullptr; + + pn2 = handler.new_(PNK_COLON, JSOP_INITPROP, opn2->pn_pos, tag, target); + } else if (opn2->isArity(PN_NULLARY)) { + JS_ASSERT(opn2->isKind(PNK_ELISION)); + pn2 = cloneParseTree(opn2); + } else { + pn2 = cloneLeftHandSide(opn2); + } + + if (!pn2) + return nullptr; + pn->append(pn2); + } + pn->pn_xflags = opn->pn_xflags; + return pn; + } + + JS_ASSERT(opn->isArity(PN_NAME)); + JS_ASSERT(opn->isKind(PNK_NAME)); + + /* If opn is a definition or use, make pn a use. */ + pn->pn_u.name = opn->pn_u.name; + pn->setOp(JSOP_SETNAME); + if (opn->isUsed()) { + Definition *dn = pn->pn_lexdef; + + pn->pn_link = dn->dn_uses; + dn->dn_uses = pn; + } else { + pn->pn_expr = nullptr; + if (opn->isDefn()) { + /* We copied some definition-specific state into pn. Clear it out. */ + pn->pn_cookie.makeFree(); + pn->pn_dflags &= ~PND_BOUND; + pn->setDefn(false); + + handler.linkUseToDef(pn, (Definition *) opn); + } + } + return pn; +} + +} /* namespace frontend */ +} /* namespace js */ + +#ifdef DEBUG + +static const char * const parseNodeNames[] = { +#define STRINGIFY(name) #name, + FOR_EACH_PARSE_NODE_KIND(STRINGIFY) +#undef STRINGIFY +}; + +void +frontend::DumpParseTree(ParseNode *pn, int indent) +{ + if (pn == nullptr) + fprintf(stderr, "#NULL"); + else + pn->dump(indent); +} + +static void +IndentNewLine(int indent) +{ + fputc('\n', stderr); + for (int i = 0; i < indent; ++i) + fputc(' ', stderr); +} + +void +ParseNode::dump() +{ + dump(0); + fputc('\n', stderr); +} + +void +ParseNode::dump(int indent) +{ + switch (pn_arity) { + case PN_NULLARY: + ((NullaryNode *) this)->dump(); + break; + case PN_UNARY: + ((UnaryNode *) this)->dump(indent); + break; + case PN_BINARY: + ((BinaryNode *) this)->dump(indent); + break; + case PN_BINARY_OBJ: + ((BinaryObjNode *) this)->dump(indent); + break; + case PN_TERNARY: + ((TernaryNode *) this)->dump(indent); + break; + case PN_CODE: + ((CodeNode *) this)->dump(indent); + break; + case PN_LIST: + ((ListNode *) this)->dump(indent); + break; + case PN_NAME: + ((NameNode *) this)->dump(indent); + break; + default: + fprintf(stderr, "#", + (void *) this, unsigned(getKind()), unsigned(pn_arity)); + break; + } +} + +void +NullaryNode::dump() +{ + switch (getKind()) { + case PNK_TRUE: fprintf(stderr, "#true"); break; + case PNK_FALSE: fprintf(stderr, "#false"); break; + case PNK_NULL: fprintf(stderr, "#null"); break; + + case PNK_NUMBER: { + ToCStringBuf cbuf; + const char *cstr = NumberToCString(nullptr, &cbuf, pn_dval); + if (!IsFinite(pn_dval)) + fputc('#', stderr); + if (cstr) + fprintf(stderr, "%s", cstr); + else + fprintf(stderr, "%g", pn_dval); + break; + } + + case PNK_STRING: + JSString::dumpChars(pn_atom->chars(), pn_atom->length()); + break; + + default: + fprintf(stderr, "(%s)", parseNodeNames[getKind()]); + } +} + +void +UnaryNode::dump(int indent) +{ + const char *name = parseNodeNames[getKind()]; + fprintf(stderr, "(%s ", name); + indent += strlen(name) + 2; + DumpParseTree(pn_kid, indent); + fprintf(stderr, ")"); +} + +void +BinaryNode::dump(int indent) +{ + const char *name = parseNodeNames[getKind()]; + fprintf(stderr, "(%s ", name); + indent += strlen(name) + 2; + DumpParseTree(pn_left, indent); + IndentNewLine(indent); + DumpParseTree(pn_right, indent); + fprintf(stderr, ")"); +} + +void +BinaryObjNode::dump(int indent) +{ + const char *name = parseNodeNames[getKind()]; + fprintf(stderr, "(%s ", name); + indent += strlen(name) + 2; + DumpParseTree(pn_left, indent); + IndentNewLine(indent); + DumpParseTree(pn_right, indent); + fprintf(stderr, ")"); +} + +void +TernaryNode::dump(int indent) +{ + const char *name = parseNodeNames[getKind()]; + fprintf(stderr, "(%s ", name); + indent += strlen(name) + 2; + DumpParseTree(pn_kid1, indent); + IndentNewLine(indent); + DumpParseTree(pn_kid2, indent); + IndentNewLine(indent); + DumpParseTree(pn_kid3, indent); + fprintf(stderr, ")"); +} + +void +CodeNode::dump(int indent) +{ + const char *name = parseNodeNames[getKind()]; + fprintf(stderr, "(%s ", name); + indent += strlen(name) + 2; + DumpParseTree(pn_body, indent); + fprintf(stderr, ")"); +} + +void +ListNode::dump(int indent) +{ + const char *name = parseNodeNames[getKind()]; + fprintf(stderr, "(%s [", name); + if (pn_head != nullptr) { + indent += strlen(name) + 3; + DumpParseTree(pn_head, indent); + ParseNode *pn = pn_head->pn_next; + while (pn != nullptr) { + IndentNewLine(indent); + DumpParseTree(pn, indent); + pn = pn->pn_next; + } + } + fprintf(stderr, "])"); +} + +void +NameNode::dump(int indent) +{ + if (isKind(PNK_NAME) || isKind(PNK_DOT)) { + if (isKind(PNK_DOT)) + fprintf(stderr, "(."); + + if (!pn_atom) { + fprintf(stderr, "#"); + } else { + const jschar *s = pn_atom->chars(); + size_t len = pn_atom->length(); + if (len == 0) + fprintf(stderr, "#"); + for (size_t i = 0; i < len; i++) { + if (s[i] > 32 && s[i] < 127) + fputc(s[i], stderr); + else if (s[i] <= 255) + fprintf(stderr, "\\x%02x", (unsigned int) s[i]); + else + fprintf(stderr, "\\u%04x", (unsigned int) s[i]); + } + } + + if (isKind(PNK_DOT)) { + fputc(' ', stderr); + DumpParseTree(expr(), indent + 2); + fputc(')', stderr); + } + return; + } + + JS_ASSERT(!isUsed()); + const char *name = parseNodeNames[getKind()]; + if (isUsed()) + fprintf(stderr, "(%s)", name); + else { + fprintf(stderr, "(%s ", name); + indent += strlen(name) + 2; + DumpParseTree(expr(), indent); + fprintf(stderr, ")"); + } +} +#endif + +ObjectBox::ObjectBox(JSObject *object, ObjectBox* traceLink) + : object(object), + traceLink(traceLink), + emitLink(nullptr) +{ + JS_ASSERT(!object->is()); +} + +ObjectBox::ObjectBox(JSFunction *function, ObjectBox* traceLink) + : object(function), + traceLink(traceLink), + emitLink(nullptr) +{ + JS_ASSERT(object->is()); + JS_ASSERT(asFunctionBox()->function() == function); +} + +FunctionBox * +ObjectBox::asFunctionBox() +{ + JS_ASSERT(isFunctionBox()); + return static_cast(this); +} + +void +ObjectBox::trace(JSTracer *trc) +{ + ObjectBox *box = this; + while (box) { + MarkObjectRoot(trc, &box->object, "parser.object"); + if (box->isFunctionBox()) + box->asFunctionBox()->bindings.trace(trc); + box = box->traceLink; + } +}