michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "frontend/NameFunctions.h"
michael@0: 
michael@0: #include "jsfun.h"
michael@0: #include "jsprf.h"
michael@0: 
michael@0: #include "frontend/BytecodeCompiler.h"
michael@0: #include "frontend/ParseNode.h"
michael@0: #include "frontend/SharedContext.h"
michael@0: #include "vm/StringBuffer.h"
michael@0: 
michael@0: using namespace js;
michael@0: using namespace js::frontend;
michael@0: 
michael@0: namespace {
michael@0: 
michael@0: class NameResolver
michael@0: {
michael@0:     static const size_t MaxParents = 100;
michael@0: 
michael@0:     ExclusiveContext *cx;
michael@0:     size_t nparents;                /* number of parents in the parents array */
michael@0:     ParseNode *parents[MaxParents]; /* history of ParseNodes we've been looking at */
michael@0:     StringBuffer *buf;              /* when resolving, buffer to append to */
michael@0: 
michael@0:     /* Test whether a ParseNode represents a function invocation */
michael@0:     bool call(ParseNode *pn) {
michael@0:         return pn && pn->isKind(PNK_CALL);
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Append a reference to a property named |name| to |buf|. If |name| is
michael@0:      * a proper identifier name, then we append '.name'; otherwise, we
michael@0:      * append '["name"]'.
michael@0:      *
michael@0:      * Note that we need the IsIdentifier check for atoms from both
michael@0:      * PNK_NAME nodes and PNK_STRING nodes: given code like a["b c"], the
michael@0:      * front end will produce a PNK_DOT with a PNK_NAME child whose name
michael@0:      * contains spaces.
michael@0:      */
michael@0:     bool appendPropertyReference(JSAtom *name) {
michael@0:         if (IsIdentifier(name))
michael@0:             return buf->append(".") && buf->append(name);
michael@0: 
michael@0:         /* Quote the string as needed. */
michael@0:         JSString *source = js_QuoteString(cx, name, '"');
michael@0:         return source && buf->append("[") && buf->append(source) && buf->append("]");
michael@0:     }
michael@0: 
michael@0:     /* Append a number to buf. */
michael@0:     bool appendNumber(double n) {
michael@0:         char number[30];
michael@0:         int digits = JS_snprintf(number, sizeof(number), "%g", n);
michael@0:         return buf->appendInflated(number, digits);
michael@0:     }
michael@0: 
michael@0:     /* Append "[<n>]" to buf, referencing a property named by a numeric literal. */
michael@0:     bool appendNumericPropertyReference(double n) {
michael@0:         return buf->append("[") && appendNumber(n) && buf->append("]");
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Walk over the given ParseNode, converting it to a stringified name that
michael@0:      * respresents where the function is being assigned to.
michael@0:      */
michael@0:     bool nameExpression(ParseNode *n) {
michael@0:         switch (n->getKind()) {
michael@0:           case PNK_DOT:
michael@0:             return nameExpression(n->expr()) && appendPropertyReference(n->pn_atom);
michael@0: 
michael@0:           case PNK_NAME:
michael@0:             return buf->append(n->pn_atom);
michael@0: 
michael@0:           case PNK_THIS:
michael@0:             return buf->append("this");
michael@0: 
michael@0:           case PNK_ELEM:
michael@0:             return nameExpression(n->pn_left) &&
michael@0:                    buf->append("[") &&
michael@0:                    nameExpression(n->pn_right) &&
michael@0:                    buf->append("]");
michael@0: 
michael@0:           case PNK_NUMBER:
michael@0:             return appendNumber(n->pn_dval);
michael@0: 
michael@0:           default:
michael@0:             /*
michael@0:              * Technically this isn't an "abort" situation, we're just confused
michael@0:              * on what to call this function, but failures in naming aren't
michael@0:              * treated as fatal.
michael@0:              */
michael@0:             return false;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * When naming an anonymous function, the process works loosely by walking
michael@0:      * up the AST and then translating that to a string. The stringification
michael@0:      * happens from some far-up assignment and then going back down the parse
michael@0:      * tree to the function definition point.
michael@0:      *
michael@0:      * This function will walk up the parse tree, gathering relevant nodes used
michael@0:      * for naming, and return the assignment node if there is one. The provided
michael@0:      * array and size will be filled in, and the returned node could be nullptr
michael@0:      * if no assignment is found. The first element of the array will be the
michael@0:      * innermost node relevant to naming, and the last element will be the
michael@0:      * outermost node.
michael@0:      */
michael@0:     ParseNode *gatherNameable(ParseNode **nameable, size_t *size) {
michael@0:         *size = 0;
michael@0: 
michael@0:         for (int pos = nparents - 1; pos >= 0; pos--) {
michael@0:             ParseNode *cur = parents[pos];
michael@0:             if (cur->isAssignment())
michael@0:                 return cur;
michael@0: 
michael@0:             switch (cur->getKind()) {
michael@0:               case PNK_NAME:     return cur;  /* found the initialized declaration */
michael@0:               case PNK_THIS:     return cur;  /* Setting a property of 'this'. */
michael@0:               case PNK_FUNCTION: return nullptr; /* won't find an assignment or declaration */
michael@0: 
michael@0:               case PNK_RETURN:
michael@0:                 /*
michael@0:                  * Normally the relevant parent of a node is its direct parent, but
michael@0:                  * sometimes with code like:
michael@0:                  *
michael@0:                  *    var foo = (function() { return function() {}; })();
michael@0:                  *
michael@0:                  * the outer function is just a helper to create a scope for the
michael@0:                  * returned function. Hence the name of the returned function should
michael@0:                  * actually be 'foo'.  This loop sees if the current node is a
michael@0:                  * PNK_RETURN, and if there is a direct function call we skip to
michael@0:                  * that.
michael@0:                  */
michael@0:                 for (int tmp = pos - 1; tmp > 0; tmp--) {
michael@0:                     if (isDirectCall(tmp, cur)) {
michael@0:                         pos = tmp;
michael@0:                         break;
michael@0:                     } else if (call(cur)) {
michael@0:                         /* Don't skip too high in the tree */
michael@0:                         break;
michael@0:                     }
michael@0:                     cur = parents[tmp];
michael@0:                 }
michael@0:                 break;
michael@0: 
michael@0:               case PNK_COLON:
michael@0:                 /*
michael@0:                  * Record the PNK_COLON but skip the PNK_OBJECT so we're not
michael@0:                  * flagged as a contributor.
michael@0:                  */
michael@0:                 pos--;
michael@0:                 /* fallthrough */
michael@0: 
michael@0:               default:
michael@0:                 /* Save any other nodes we encounter on the way up. */
michael@0:                 JS_ASSERT(*size < MaxParents);
michael@0:                 nameable[(*size)++] = cur;
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         return nullptr;
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Resolve the name of a function. If the function already has a name
michael@0:      * listed, then it is skipped. Otherwise an intelligent name is guessed to
michael@0:      * assign to the function's displayAtom field
michael@0:      */
michael@0:     bool resolveFun(ParseNode *pn, HandleAtom prefix, MutableHandleAtom retAtom) {
michael@0:         JS_ASSERT(pn != nullptr && pn->isKind(PNK_FUNCTION));
michael@0:         RootedFunction fun(cx, pn->pn_funbox->function());
michael@0: 
michael@0:         StringBuffer buf(cx);
michael@0:         this->buf = &buf;
michael@0: 
michael@0:         retAtom.set(nullptr);
michael@0: 
michael@0:         /* If the function already has a name, use that */
michael@0:         if (fun->displayAtom() != nullptr) {
michael@0:             if (prefix == nullptr) {
michael@0:                 retAtom.set(fun->displayAtom());
michael@0:                 return true;
michael@0:             }
michael@0:             if (!buf.append(prefix) ||
michael@0:                 !buf.append("/") ||
michael@0:                 !buf.append(fun->displayAtom()))
michael@0:                 return false;
michael@0:             retAtom.set(buf.finishAtom());
michael@0:             return !!retAtom;
michael@0:         }
michael@0: 
michael@0:         /* If a prefix is specified, then it is a form of namespace */
michael@0:         if (prefix != nullptr && (!buf.append(prefix) || !buf.append("/")))
michael@0:             return false;
michael@0: 
michael@0:         /* Gather all nodes relevant to naming */
michael@0:         ParseNode *toName[MaxParents];
michael@0:         size_t size;
michael@0:         ParseNode *assignment = gatherNameable(toName, &size);
michael@0: 
michael@0:         /* If the function is assigned to something, then that is very relevant */
michael@0:         if (assignment) {
michael@0:             if (assignment->isAssignment())
michael@0:                 assignment = assignment->pn_left;
michael@0:             if (!nameExpression(assignment))
michael@0:                 return true;
michael@0:         }
michael@0: 
michael@0:         /*
michael@0:          * Other than the actual assignment, other relevant nodes to naming are
michael@0:          * those in object initializers and then particular nodes marking a
michael@0:          * contribution.
michael@0:          */
michael@0:         for (int pos = size - 1; pos >= 0; pos--) {
michael@0:             ParseNode *node = toName[pos];
michael@0: 
michael@0:             if (node->isKind(PNK_COLON)) {
michael@0:                 ParseNode *left = node->pn_left;
michael@0:                 if (left->isKind(PNK_NAME) || left->isKind(PNK_STRING)) {
michael@0:                     if (!appendPropertyReference(left->pn_atom))
michael@0:                         return false;
michael@0:                 } else if (left->isKind(PNK_NUMBER)) {
michael@0:                     if (!appendNumericPropertyReference(left->pn_dval))
michael@0:                         return false;
michael@0:                 }
michael@0:             } else {
michael@0:                 /*
michael@0:                  * Don't have consecutive '<' characters, and also don't start
michael@0:                  * with a '<' character.
michael@0:                  */
michael@0:                 if (!buf.empty() && *(buf.end() - 1) != '<' && !buf.append("<"))
michael@0:                     return false;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         /*
michael@0:          * functions which are "genuinely anonymous" but are contained in some
michael@0:          * other namespace are rather considered as "contributing" to the outer
michael@0:          * function, so give them a contribution symbol here.
michael@0:          */
michael@0:         if (!buf.empty() && *(buf.end() - 1) == '/' && !buf.append("<"))
michael@0:             return false;
michael@0: 
michael@0:         if (buf.empty())
michael@0:             return true;
michael@0: 
michael@0:         retAtom.set(buf.finishAtom());
michael@0:         if (!retAtom)
michael@0:             return false;
michael@0:         fun->setGuessedAtom(retAtom);
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Tests whether parents[pos] is a function call whose callee is cur.
michael@0:      * This is the case for functions which do things like simply create a scope
michael@0:      * for new variables and then return an anonymous function using this scope.
michael@0:      */
michael@0:     bool isDirectCall(int pos, ParseNode *cur) {
michael@0:         return pos >= 0 && call(parents[pos]) && parents[pos]->pn_head == cur;
michael@0:     }
michael@0: 
michael@0:   public:
michael@0:     explicit NameResolver(ExclusiveContext *cx) : cx(cx), nparents(0), buf(nullptr) {}
michael@0: 
michael@0:     /*
michael@0:      * Resolve all names for anonymous functions recursively within the
michael@0:      * ParseNode instance given. The prefix is for each subsequent name, and
michael@0:      * should initially be nullptr.
michael@0:      */
michael@0:     bool resolve(ParseNode *cur, HandleAtom prefixArg = js::NullPtr()) {
michael@0:         RootedAtom prefix(cx, prefixArg);
michael@0:         if (cur == nullptr)
michael@0:             return true;
michael@0: 
michael@0:         if (cur->isKind(PNK_FUNCTION) && cur->isArity(PN_CODE)) {
michael@0:             RootedAtom prefix2(cx);
michael@0:             if (!resolveFun(cur, prefix, &prefix2))
michael@0:                 return false;
michael@0: 
michael@0:             /*
michael@0:              * If a function looks like (function(){})() where the parent node
michael@0:              * of the definition of the function is a call, then it shouldn't
michael@0:              * contribute anything to the namespace, so don't bother updating
michael@0:              * the prefix to whatever was returned.
michael@0:              */
michael@0:             if (!isDirectCall(nparents - 1, cur))
michael@0:                 prefix = prefix2;
michael@0:         }
michael@0:         if (nparents >= MaxParents)
michael@0:             return true;
michael@0:         parents[nparents++] = cur;
michael@0: 
michael@0:         switch (cur->getArity()) {
michael@0:           case PN_NULLARY:
michael@0:             break;
michael@0:           case PN_NAME:
michael@0:             if (!resolve(cur->maybeExpr(), prefix))
michael@0:                 return false;
michael@0:             break;
michael@0:           case PN_UNARY:
michael@0:             if (!resolve(cur->pn_kid, prefix))
michael@0:                 return false;
michael@0:             break;
michael@0:           case PN_BINARY:
michael@0:           case PN_BINARY_OBJ:
michael@0:             if (!resolve(cur->pn_left, prefix))
michael@0:                 return false;
michael@0: 
michael@0:             /*
michael@0:              * FIXME? Occasionally pn_left == pn_right for something like
michael@0:              * destructuring assignment in (function({foo}){}), so skip the
michael@0:              * duplicate here if this is the case because we want to traverse
michael@0:              * everything at most once.
michael@0:              */
michael@0:             if (cur->pn_left != cur->pn_right)
michael@0:                 if (!resolve(cur->pn_right, prefix))
michael@0:                     return false;
michael@0:             break;
michael@0:           case PN_TERNARY:
michael@0:             if (!resolve(cur->pn_kid1, prefix))
michael@0:                 return false;
michael@0:             if (!resolve(cur->pn_kid2, prefix))
michael@0:                 return false;
michael@0:             if (!resolve(cur->pn_kid3, prefix))
michael@0:                 return false;
michael@0:             break;
michael@0:           case PN_CODE:
michael@0:             JS_ASSERT(cur->isKind(PNK_FUNCTION));
michael@0:             if (!resolve(cur->pn_body, prefix))
michael@0:                 return false;
michael@0:             break;
michael@0:           case PN_LIST:
michael@0:             for (ParseNode *nxt = cur->pn_head; nxt; nxt = nxt->pn_next)
michael@0:                 if (!resolve(nxt, prefix))
michael@0:                     return false;
michael@0:             break;
michael@0:         }
michael@0:         nparents--;
michael@0:         return true;
michael@0:     }
michael@0: };
michael@0: 
michael@0: } /* anonymous namespace */
michael@0: 
michael@0: bool
michael@0: frontend::NameFunctions(ExclusiveContext *cx, ParseNode *pn)
michael@0: {
michael@0:     NameResolver nr(cx);
michael@0:     return nr.resolve(pn);
michael@0: }