Bug 433529: Part 1 - Statically resolve names for anonymous functions. r=jimb
authorAlex Crichton <acrichton@mozilla.com>
Sat, 18 Aug 2012 21:33:20 -0700
changeset 105146 d7568555261ce6c7166c880f35bd64d5ba99a94b
parent 105145 7dab8a726f441a8ea59ffb6d2cb0e7e97f120135
child 105147 4ebcfba34c383b8829d8e4d2e57d9ac248085249
push id55
push usershu@rfrn.org
push dateThu, 30 Aug 2012 01:33:09 +0000
reviewersjimb
bugs433529
milestone17.0a1
Bug 433529: Part 1 - Statically resolve names for anonymous functions. r=jimb
js/src/Makefile.in
js/src/frontend/BytecodeCompiler.cpp
js/src/frontend/NameFunctions.cpp
js/src/frontend/NameFunctions.h
--- a/js/src/Makefile.in
+++ b/js/src/Makefile.in
@@ -115,16 +115,17 @@ CPPSRCS		= \
 		Debugger.cpp \
 		GlobalObject.cpp \
 		ObjectImpl.cpp \
 		Stack.cpp \
 		String.cpp \
 		BytecodeCompiler.cpp \
 		BytecodeEmitter.cpp \
 		FoldConstants.cpp \
+		NameFunctions.cpp \
 		ParallelArray.cpp \
 		ParseMaps.cpp \
 		ParseNode.cpp \
 		Parser.cpp \
 		SPSProfiler.cpp \
 		TokenStream.cpp \
 		TestingFunctions.cpp \
 		LifoAlloc.cpp \
--- a/js/src/frontend/BytecodeCompiler.cpp
+++ b/js/src/frontend/BytecodeCompiler.cpp
@@ -6,16 +6,17 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "frontend/BytecodeCompiler.h"
 
 #include "jsprobes.h"
 
 #include "frontend/BytecodeEmitter.h"
 #include "frontend/FoldConstants.h"
+#include "frontend/NameFunctions.h"
 #include "vm/GlobalObject.h"
 
 #include "jsinferinlines.h"
 
 #include "frontend/ParseMaps-inl.h"
 #include "frontend/Parser-inl.h"
 #include "frontend/SharedContext-inl.h"
 
@@ -186,16 +187,18 @@ frontend::CompileScript(JSContext *cx, H
         }
 
         pn = parser.statement();
         if (!pn)
             return NULL;
 
         if (!FoldConstants(cx, pn, &parser))
             return NULL;
+        if (!NameFunctions(cx, pn))
+            return NULL;
 
         pc.functionList = NULL;
 
         if (!EmitTree(cx, &bce, pn))
             return NULL;
 
 #if JS_HAS_XML_SUPPORT
         if (!pn->isKind(PNK_SEMI) || !pn->pn_kid || !pn->pn_kid->isXMLItem())
@@ -326,16 +329,19 @@ frontend::CompileFunctionBody(JSContext 
     if (!funpc.generateFunctionBindings(cx, &script->bindings))
         return false;
 
     BytecodeEmitter funbce(/* parent = */ NULL, &parser, &funsc, script, /* callerFrame = */ NULL,
                            /* hasGlobalScope = */ false, options.lineno);
     if (!funbce.init())
         return false;
 
+    if (!NameFunctions(cx, pn))
+        return NULL;
+
     if (fn->pn_body) {
         JS_ASSERT(fn->pn_body->isKind(PNK_ARGSBODY));
         fn->pn_body->append(pn);
         fn->pn_body->pn_pos = pn->pn_pos;
         pn = fn->pn_body;
     }
 
     if (!SetSourceMap(cx, parser.tokenStream, ss, script))
new file mode 100644
--- /dev/null
+++ b/js/src/frontend/NameFunctions.cpp
@@ -0,0 +1,303 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sw=4 et 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/NameFunctions.h"
+#include "frontend/ParseNode.h"
+#include "frontend/SharedContext.h"
+
+#include "jsfun.h"
+#include "jsprf.h"
+
+#include "vm/String-inl.h"
+#include "vm/StringBuffer.h"
+
+using namespace js;
+using namespace js::frontend;
+
+class NameResolver
+{
+    static const size_t MaxParents = 100;
+
+    JSContext *cx;
+    size_t nparents;                /* number of parents in the parents array */
+    ParseNode *parents[MaxParents]; /* history of ParseNodes we've been looking at */
+    StringBuffer *buf;              /* when resolving, buffer to append to */
+
+    /* Test whether a ParseNode represents a function invocation */
+    bool call(ParseNode *pn) {
+        return pn && pn->isKind(PNK_LP);
+    }
+
+    /*
+     * Some special atoms like 'prototype' and '__proto__' aren't useful to show
+     * up in function names.
+     */
+    bool special(JSAtom *atom) {
+        return cx->runtime->atomState.protoAtom == atom ||
+               cx->runtime->atomState.classPrototypeAtom == atom;
+    }
+
+    /*
+     * Walk over the given ParseNode, converting it to a stringified name that
+     * respresents where the function is being assigned to.
+     */
+    bool nameExpression(ParseNode *n) {
+        switch (n->getKind()) {
+            case PNK_DOT:
+                return nameExpression(n->expr()) &&
+                       (special(n->pn_atom) ||
+                        (buf->append(".") && buf->append(n->pn_atom)));
+
+            case PNK_NAME:
+                return buf->append(n->pn_atom);
+
+            case PNK_LB:
+                return nameExpression(n->pn_left) &&
+                       buf->append("[") &&
+                       nameExpression(n->pn_right) &&
+                       buf->append("]");
+
+            case PNK_NUMBER: {
+                char number[30];
+                int digits = JS_snprintf(number, sizeof(number), "%g", n->pn_dval);
+                return buf->appendInflated(number, digits);
+            }
+
+            /*
+             * Technically this isn't an "abort" situation, we're just confused
+             * on what to call this function, but failures in naming aren't
+             * treated as fatal.
+             */
+            default:
+                return false;
+        }
+    }
+
+    /*
+     * When naming an anonymous function, the process works loosely by walking
+     * up the AST and then translating that to a string. The stringification
+     * happens from some far-up assignment and then going back down the parse
+     * tree to the function definition point.
+     *
+     * This function will walk up the parse tree, gathering relevant nodes used
+     * for naming, and return the assignment node if there is one. The provided
+     * array and size will be filled in, and the returned node could be NULL if
+     * no assignment is found. The first element of the array will be the
+     * innermost node relevant to naming, and the last element will be the
+     * outermost node.
+     */
+    ParseNode *gatherNameable(ParseNode **nameable, size_t *size) {
+        *size = 0;
+
+        for (int pos = nparents - 1; pos >= 0; pos--) {
+            ParseNode *cur = parents[pos];
+            if (cur->isAssignment())
+                return cur;
+
+            switch (cur->getKind()) {
+                case PNK_NAME:     return cur;  /* found the initialized declaration */
+                case PNK_FUNCTION: return NULL; /* won't find an assignment or declaration */
+                default:           break;       /* move on, nothing relevant */
+
+                /* These nodes are relevant to the naming process, so append */
+                case PNK_COLON:
+                case PNK_LP:
+                case PNK_NEW:
+                    JS_ASSERT(*size < MaxParents);
+                    nameable[(*size)++] = cur;
+                    break;
+            }
+
+            /*
+             * Normally the relevant parent of a node is its direct parent, but
+             * sometimes with code like:
+             *
+             *    var foo = (function() { return function() {}; })();
+             *
+             * the outer function is just a helper to create a scope for the
+             * returned function. Hence the name of the returned function should
+             * actually be 'foo'.  This loop sees if the current node is a
+             * PNK_RETURN, and if there is a direct function call we skip to
+             * that.
+             */
+            if (cur->isKind(PNK_RETURN)) {
+                for (int tmp = pos - 1; tmp > 0; tmp--) {
+                    if (isDirectCall(tmp, cur)) {
+                        pos = tmp;
+                        break;
+                    } else if (call(cur)) {
+                        /* Don't skip too high in the tree */
+                        break;
+                    }
+                    cur = parents[tmp];
+                }
+            }
+        }
+
+        return NULL;
+    }
+
+    /*
+     * Resolve the name of a function. If the function already has a name
+     * listed, then it is skipped. Otherwise an intelligent name is guessed to
+     * assign to the function's displayAtom field
+     */
+    JSAtom *resolveFun(ParseNode *pn, JSAtom *prefix) {
+        JS_ASSERT(pn != NULL && pn->isKind(PNK_FUNCTION));
+        JSFunction *fun = pn->pn_funbox->function();
+        if (nparents == 0)
+            return NULL;
+
+        StringBuffer buf(cx);
+        this->buf = &buf;
+
+        /* If the function already has a name, use that */
+        if (fun->displayAtom() != NULL) {
+            if (prefix == NULL)
+                return fun->atom();
+            if (!buf.append(prefix) ||
+                !buf.append("/") ||
+                !buf.append(fun->displayAtom()))
+                return NULL;
+            return buf.finishAtom();
+        }
+
+        /* If a prefix is specified, then it is a form of namespace */
+        if (prefix != NULL && (!buf.append(prefix) || !buf.append("/")))
+            return NULL;
+
+        /* Gather all nodes relevant to naming */
+        ParseNode *toName[MaxParents];
+        size_t size;
+        ParseNode *assignment = gatherNameable(toName, &size);
+
+        /* If the function is assigned to something, then that is very relevant */
+        if (assignment) {
+            if (assignment->isAssignment())
+                assignment = assignment->pn_left;
+            if (!nameExpression(assignment))
+                return NULL;
+        }
+
+        /*
+         * Other than the actual assignment, other relevant nodes to naming are
+         * those in object initializers and then particular nodes marking a
+         * contribution.
+         */
+        for (int pos = size - 1; pos >= 0; pos--) {
+            ParseNode *node = toName[pos];
+
+            if (node->isKind(PNK_COLON)) {
+                if (!node->pn_left->isKind(PNK_NAME))
+                    continue;
+                /* special atoms are skipped, but others are dot-appended */
+                if (!special(node->pn_left->pn_atom)) {
+                    if (!buf.append(".") || !buf.append(node->pn_left->pn_atom))
+                        return NULL;
+                }
+            } else {
+                /*
+                 * Don't have consecutive '<' characters, and also don't start
+                 * with a '<' character.
+                 */
+                if (!buf.empty() && *(buf.end() - 1) != '<' && !buf.append("<"))
+                    return NULL;
+            }
+        }
+
+        /*
+         * functions which are "genuinely anonymous" but are contained in some
+         * other namespace are rather considered as "contributing" to the outer
+         * function, so give them a contribution symbol here.
+         */
+        if (!buf.empty() && *(buf.end() - 1) == '/' && !buf.append("<"))
+            return NULL;
+
+        return buf.finishAtom();
+    }
+
+    /*
+     * Tests whether parents[pos] is a function call whose callee is cur.
+     * This is the case for functions which do things like simply create a scope
+     * for new variables and then return an anonymous function using this scope.
+     */
+    bool isDirectCall(int pos, ParseNode *cur) {
+        return pos >= 0 && call(parents[pos]) && parents[pos]->pn_head == cur;
+    }
+
+  public:
+    NameResolver(JSContext *cx) : cx(cx), nparents(0), buf(NULL) {}
+
+    /*
+     * Resolve all names for anonymous functions recursively within the
+     * ParseNode instance given. The prefix is for each subsequent name, and
+     * should initially be NULL.
+     */
+    void resolve(ParseNode *cur, JSAtom *prefix = NULL) {
+        if (cur == NULL)
+            return;
+
+        if (cur->isKind(PNK_FUNCTION) && cur->isArity(PN_FUNC)) {
+            JSAtom *prefix2 = resolveFun(cur, prefix);
+            /*
+             * If a function looks like (function(){})() where the parent node
+             * of the definition of the function is a call, then it shouldn't
+             * contribute anything to the namespace, so don't bother updating
+             * the prefix to whatever was returned.
+             */
+            if (!isDirectCall(nparents - 1, cur))
+                prefix = prefix2;
+        }
+        if (nparents >= MaxParents)
+            return;
+        parents[nparents++] = cur;
+
+        switch (cur->getArity()) {
+            case PN_NULLARY:
+                break;
+            case PN_NAME:
+                resolve(cur->maybeExpr(), prefix);
+                break;
+            case PN_UNARY:
+                resolve(cur->pn_kid, prefix);
+                break;
+            case PN_BINARY:
+                resolve(cur->pn_left, prefix);
+                /*
+                 * Occasionally pn_left == pn_right for something like
+                 * destructuring assignment in (function({foo}){}), so skip the
+                 * duplicate here if this is the case because we want to
+                 * traverse everything at most once.
+                 */
+                if (cur->pn_left != cur->pn_right)
+                    resolve(cur->pn_right, prefix);
+                break;
+            case PN_TERNARY:
+                resolve(cur->pn_kid1, prefix);
+                resolve(cur->pn_kid2, prefix);
+                resolve(cur->pn_kid3, prefix);
+                break;
+            case PN_FUNC:
+                JS_ASSERT(cur->isKind(PNK_FUNCTION));
+                resolve(cur->pn_body, prefix);
+                break;
+            case PN_LIST:
+                for (ParseNode *nxt = cur->pn_head; nxt; nxt = nxt->pn_next)
+                    resolve(nxt, prefix);
+                break;
+        }
+        nparents--;
+    }
+};
+
+bool
+frontend::NameFunctions(JSContext *cx, ParseNode *pn)
+{
+    NameResolver nr(cx);
+    nr.resolve(pn);
+    return true;
+}
new file mode 100644
--- /dev/null
+++ b/js/src/frontend/NameFunctions.h
@@ -0,0 +1,24 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sw=4 et 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/. */
+
+#ifndef NameFunctions_h__
+#define NameFunctions_h__
+
+struct JSContext;
+
+namespace js {
+namespace frontend {
+
+struct ParseNode;
+
+bool
+NameFunctions(JSContext *cx, ParseNode *pn);
+
+} /* namespace frontend */
+} /* namespace js */
+
+#endif /* NameFunctions_h__ */