1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 * vim: set ts=8 sts=2 et sw=2 tw=80:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 #include "frontend/NameFunctions.h"
8
9 #include "mozilla/MemoryChecking.h"
10 #include "mozilla/ScopeExit.h"
11 #include "mozilla/Sprintf.h"
12
13 #include "frontend/BytecodeCompiler.h"
14 #include "frontend/ParseNode.h"
15 #include "frontend/ParseNodeVisitor.h"
16 #include "frontend/ParserAtom.h" // ParserAtomsTable
17 #include "frontend/SharedContext.h"
18 #include "util/Poison.h"
19 #include "util/StringBuffer.h"
20 #include "vm/JSFunction.h"
21
22 using namespace js;
23 using namespace js::frontend;
24
25 namespace {
26
27 class NameResolver : public ParseNodeVisitor<NameResolver> {
28 using Base = ParseNodeVisitor;
29
30 static const size_t MaxParents = 100;
31
32 ParserAtomsTable& parserAtoms_;
33 TaggedParserAtomIndex prefix_;
34
35 // Number of nodes in the parents array.
36 size_t nparents_;
37
38 // Stack of ParseNodes from the root to the current node.
39 // Only elements 0..nparents_ are initialized.
40 MOZ_INIT_OUTSIDE_CTOR
41 ParseNode* parents_[MaxParents];
42
43 // When naming a function, the buffer where the name is built.
44 // When we are not under resolveFun, buf_ is empty.
45 StringBuffer buf_;
46
47 /* Test whether a ParseNode represents a function invocation */
isCall(ParseNode * pn)48 bool isCall(ParseNode* pn) {
49 return pn && pn->isKind(ParseNodeKind::CallExpr);
50 }
51
52 /*
53 * Append a reference to a property named |name| to |buf_|. If |name| is
54 * a proper identifier name, then we append '.name'; otherwise, we
55 * append '["name"]'.
56 *
57 * Note that we need the IsIdentifier check for atoms from both
58 * ParseNodeKind::Name nodes and ParseNodeKind::String nodes:
59 * given code like a["b c"], the front end will produce a ParseNodeKind::Dot
60 * with a ParseNodeKind::Name child whose name contains spaces.
61 */
appendPropertyReference(TaggedParserAtomIndex name)62 bool appendPropertyReference(TaggedParserAtomIndex name) {
63 if (parserAtoms_.isIdentifier(name)) {
64 return buf_.append('.') && buf_.append(parserAtoms_, name);
65 }
66
67 /* Quote the string as needed. */
68 UniqueChars source = parserAtoms_.toQuotedString(cx_, name);
69 return source && buf_.append('[') &&
70 buf_.append(source.get(), strlen(source.get())) && buf_.append(']');
71 }
72
73 /* Append a number to buf_. */
appendNumber(double n)74 bool appendNumber(double n) {
75 char number[30];
76 int digits = SprintfLiteral(number, "%g", n);
77 return buf_.append(number, digits);
78 }
79
80 // Append "[<n>]" to buf_, referencing a property named by a numeric literal.
appendNumericPropertyReference(double n)81 bool appendNumericPropertyReference(double n) {
82 return buf_.append("[") && appendNumber(n) && buf_.append(']');
83 }
84
85 /*
86 * Walk over the given ParseNode, attempting to convert it to a stringified
87 * name that respresents where the function is being assigned to.
88 *
89 * |*foundName| is set to true if a name is found for the expression.
90 */
nameExpression(ParseNode * n,bool * foundName)91 bool nameExpression(ParseNode* n, bool* foundName) {
92 switch (n->getKind()) {
93 case ParseNodeKind::DotExpr: {
94 PropertyAccess* prop = &n->as<PropertyAccess>();
95 if (!nameExpression(&prop->expression(), foundName)) {
96 return false;
97 }
98 if (!*foundName) {
99 return true;
100 }
101 return appendPropertyReference(prop->right()->as<NameNode>().atom());
102 }
103
104 case ParseNodeKind::Name:
105 case ParseNodeKind::PrivateName: {
106 *foundName = true;
107 return buf_.append(parserAtoms_, n->as<NameNode>().atom());
108 }
109
110 case ParseNodeKind::ThisExpr:
111 *foundName = true;
112 return buf_.append("this");
113
114 case ParseNodeKind::ElemExpr: {
115 PropertyByValue* elem = &n->as<PropertyByValue>();
116 if (!nameExpression(&elem->expression(), foundName)) {
117 return false;
118 }
119 if (!*foundName) {
120 return true;
121 }
122 if (!buf_.append('[') || !nameExpression(elem->right(), foundName)) {
123 return false;
124 }
125 if (!*foundName) {
126 return true;
127 }
128 return buf_.append(']');
129 }
130
131 case ParseNodeKind::NumberExpr:
132 *foundName = true;
133 return appendNumber(n->as<NumericLiteral>().value());
134
135 default:
136 // We're confused as to what to call this function.
137 *foundName = false;
138 return true;
139 }
140 }
141
142 /*
143 * When naming an anonymous function, the process works loosely by walking
144 * up the AST and then translating that to a string. The stringification
145 * happens from some far-up assignment and then going back down the parse
146 * tree to the function definition point.
147 *
148 * This function will walk up the parse tree, gathering relevant nodes used
149 * for naming, and return the assignment node if there is one. The provided
150 * array and size will be filled in, and the returned node could be nullptr
151 * if no assignment is found. The first element of the array will be the
152 * innermost node relevant to naming, and the last element will be the
153 * outermost node.
154 */
gatherNameable(ParseNode ** nameable,size_t * size)155 ParseNode* gatherNameable(ParseNode** nameable, size_t* size) {
156 MOZ_ASSERT(nparents_ > 0);
157 MOZ_ASSERT(parents_[nparents_ - 1]->is<FunctionNode>());
158
159 *size = 0;
160
161 for (int pos = nparents_ - 2; pos >= 0; pos--) {
162 ParseNode* cur = parents_[pos];
163 if (cur->is<AssignmentNode>()) {
164 return cur;
165 }
166
167 switch (cur->getKind()) {
168 case ParseNodeKind::PrivateName:
169 case ParseNodeKind::Name:
170 return cur; // found the initialized declaration
171 case ParseNodeKind::ThisExpr:
172 return cur; // setting a property of 'this'
173 case ParseNodeKind::Function:
174 return nullptr; // won't find an assignment or declaration
175
176 case ParseNodeKind::ReturnStmt:
177 // Normally the relevant parent of a node is its direct parent, but
178 // sometimes with code like:
179 //
180 // var foo = (function() { return function() {}; })();
181 //
182 // the outer function is just a helper to create a scope for the
183 // returned function. Hence the name of the returned function should
184 // actually be 'foo'. This loop sees if the current node is a
185 // ParseNodeKind::Return, and if there is a direct function
186 // call we skip to that.
187 for (int tmp = pos - 1; tmp > 0; tmp--) {
188 if (isDirectCall(tmp, cur)) {
189 pos = tmp;
190 break;
191 }
192 if (isCall(cur)) {
193 // Don't skip too high in the tree.
194 break;
195 }
196 cur = parents_[tmp];
197 }
198 break;
199
200 case ParseNodeKind::PropertyDefinition:
201 case ParseNodeKind::Shorthand:
202 // Record the ParseNodeKind::PropertyDefinition/Shorthand but skip the
203 // ParseNodeKind::Object so we're not flagged as a contributor.
204 pos--;
205 [[fallthrough]];
206
207 default:
208 // Save any other nodes we encounter on the way up.
209 MOZ_ASSERT(*size < MaxParents);
210 nameable[(*size)++] = cur;
211 break;
212 }
213 }
214
215 return nullptr;
216 }
217
218 /*
219 * Resolve the name of a function. If the function already has a name
220 * listed, then it is skipped. Otherwise an intelligent name is guessed to
221 * assign to the function's displayAtom field.
222 */
resolveFun(FunctionNode * funNode,TaggedParserAtomIndex * retId)223 [[nodiscard]] bool resolveFun(FunctionNode* funNode,
224 TaggedParserAtomIndex* retId) {
225 MOZ_ASSERT(funNode != nullptr);
226
227 FunctionBox* funbox = funNode->funbox();
228
229 MOZ_ASSERT(buf_.empty());
230 auto resetBuf = mozilla::MakeScopeExit([&] { buf_.clear(); });
231
232 *retId = TaggedParserAtomIndex::null();
233
234 // If the function already has a name, use that.
235 if (funbox->displayAtom()) {
236 if (!prefix_) {
237 *retId = funbox->displayAtom();
238 return true;
239 }
240 if (!buf_.append(parserAtoms_, prefix_) || !buf_.append('/') ||
241 !buf_.append(parserAtoms_, funbox->displayAtom())) {
242 return false;
243 }
244 *retId = buf_.finishParserAtom(parserAtoms_);
245 return !!*retId;
246 }
247
248 // If a prefix is specified, then it is a form of namespace.
249 if (prefix_) {
250 if (!buf_.append(parserAtoms_, prefix_) || !buf_.append('/')) {
251 return false;
252 }
253 }
254
255 // Gather all nodes relevant to naming.
256 ParseNode* toName[MaxParents];
257 size_t size;
258 ParseNode* assignment = gatherNameable(toName, &size);
259
260 // If the function is assigned to something, then that is very relevant.
261 if (assignment) {
262 if (assignment->is<AssignmentNode>()) {
263 assignment = assignment->as<AssignmentNode>().left();
264 }
265 bool foundName = false;
266 if (!nameExpression(assignment, &foundName)) {
267 return false;
268 }
269 if (!foundName) {
270 return true;
271 }
272 }
273
274 // Other than the actual assignment, other relevant nodes to naming are
275 // those in object initializers and then particular nodes marking a
276 // contribution.
277 for (int pos = size - 1; pos >= 0; pos--) {
278 ParseNode* node = toName[pos];
279
280 if (node->isKind(ParseNodeKind::PropertyDefinition) ||
281 node->isKind(ParseNodeKind::Shorthand)) {
282 ParseNode* left = node->as<BinaryNode>().left();
283 if (left->isKind(ParseNodeKind::ObjectPropertyName) ||
284 left->isKind(ParseNodeKind::StringExpr)) {
285 if (!appendPropertyReference(left->as<NameNode>().atom())) {
286 return false;
287 }
288 } else if (left->isKind(ParseNodeKind::NumberExpr)) {
289 if (!appendNumericPropertyReference(
290 left->as<NumericLiteral>().value())) {
291 return false;
292 }
293 } else {
294 MOZ_ASSERT(left->isKind(ParseNodeKind::ComputedName) ||
295 left->isKind(ParseNodeKind::BigIntExpr));
296 }
297 } else {
298 // Don't have consecutive '<' characters, and also don't start
299 // with a '<' character.
300 if (!buf_.empty() && buf_.getChar(buf_.length() - 1) != '<' &&
301 !buf_.append('<')) {
302 return false;
303 }
304 }
305 }
306
307 // functions which are "genuinely anonymous" but are contained in some
308 // other namespace are rather considered as "contributing" to the outer
309 // function, so give them a contribution symbol here.
310 if (!buf_.empty() && buf_.getChar(buf_.length() - 1) == '/' &&
311 !buf_.append('<')) {
312 return false;
313 }
314
315 if (buf_.empty()) {
316 return true;
317 }
318
319 *retId = buf_.finishParserAtom(parserAtoms_);
320 if (!*retId) {
321 return false;
322 }
323
324 // Skip assigning the guessed name if the function has a (dynamically)
325 // computed inferred name.
326 if (!funNode->isDirectRHSAnonFunction()) {
327 funbox->setGuessedAtom(*retId);
328 }
329 return true;
330 }
331
332 /*
333 * Tests whether parents_[pos] is a function call whose callee is cur.
334 * This is the case for functions which do things like simply create a scope
335 * for new variables and then return an anonymous function using this scope.
336 */
isDirectCall(int pos,ParseNode * cur)337 bool isDirectCall(int pos, ParseNode* cur) {
338 return pos >= 0 && isCall(parents_[pos]) &&
339 parents_[pos]->as<BinaryNode>().left() == cur;
340 }
341
342 public:
visitFunction(FunctionNode * pn)343 [[nodiscard]] bool visitFunction(FunctionNode* pn) {
344 TaggedParserAtomIndex savedPrefix = prefix_;
345 TaggedParserAtomIndex newPrefix;
346 if (!resolveFun(pn, &newPrefix)) {
347 return false;
348 }
349
350 // If a function looks like (function(){})() where the parent node
351 // of the definition of the function is a call, then it shouldn't
352 // contribute anything to the namespace, so don't bother updating
353 // the prefix to whatever was returned.
354 if (!isDirectCall(nparents_ - 2, pn)) {
355 prefix_ = newPrefix;
356 }
357
358 bool ok = Base::visitFunction(pn);
359
360 prefix_ = savedPrefix;
361 return ok;
362 }
363
364 // Skip this type of node. It never contains functions.
visitCallSiteObj(CallSiteNode * callSite)365 [[nodiscard]] bool visitCallSiteObj(CallSiteNode* callSite) {
366 // This node only contains internal strings or undefined and an array -- no
367 // user-controlled expressions.
368 return true;
369 }
370
371 // Skip walking the list of string parts, which never contains functions.
visitTaggedTemplateExpr(BinaryNode * taggedTemplate)372 [[nodiscard]] bool visitTaggedTemplateExpr(BinaryNode* taggedTemplate) {
373 ParseNode* tag = taggedTemplate->left();
374
375 // The leading expression, e.g. |tag| in |tag`foo`|,
376 // that might contain functions.
377 if (!visit(tag)) {
378 return false;
379 }
380
381 // The callsite object node is first. This node only contains
382 // internal strings or undefined and an array -- no user-controlled
383 // expressions.
384 CallSiteNode* element =
385 &taggedTemplate->right()->as<ListNode>().head()->as<CallSiteNode>();
386 #ifdef DEBUG
387 {
388 ListNode* rawNodes = &element->head()->as<ListNode>();
389 MOZ_ASSERT(rawNodes->isKind(ParseNodeKind::ArrayExpr));
390 for (ParseNode* raw : rawNodes->contents()) {
391 MOZ_ASSERT(raw->isKind(ParseNodeKind::TemplateStringExpr));
392 }
393 for (ParseNode* cooked : element->contentsFrom(rawNodes->pn_next)) {
394 MOZ_ASSERT(cooked->isKind(ParseNodeKind::TemplateStringExpr) ||
395 cooked->isKind(ParseNodeKind::RawUndefinedExpr));
396 }
397 }
398 #endif
399
400 // Next come any interpolated expressions in the tagged template.
401 ParseNode* interpolated = element->pn_next;
402 for (; interpolated; interpolated = interpolated->pn_next) {
403 if (!visit(interpolated)) {
404 return false;
405 }
406 }
407
408 return true;
409 }
410
411 private:
412 // Speed hack: this type of node can't contain functions, so skip walking it.
internalVisitSpecList(ListNode * pn)413 [[nodiscard]] bool internalVisitSpecList(ListNode* pn) {
414 // Import/export spec lists contain import/export specs containing only
415 // pairs of names or strings. Alternatively, an export spec list may
416 // contain a single export batch specifier.
417 #ifdef DEBUG
418 bool isImport = pn->isKind(ParseNodeKind::ImportSpecList);
419 ParseNode* item = pn->head();
420 if (!isImport && item && item->isKind(ParseNodeKind::ExportBatchSpecStmt)) {
421 MOZ_ASSERT(item->is<NullaryNode>());
422 } else {
423 for (ParseNode* item : pn->contents()) {
424 if (item->is<UnaryNode>()) {
425 auto* spec = &item->as<UnaryNode>();
426 MOZ_ASSERT(spec->isKind(isImport
427 ? ParseNodeKind::ImportNamespaceSpec
428 : ParseNodeKind::ExportNamespaceSpec));
429 MOZ_ASSERT(spec->kid()->isKind(ParseNodeKind::Name) ||
430 spec->kid()->isKind(ParseNodeKind::StringExpr));
431 } else {
432 auto* spec = &item->as<BinaryNode>();
433 MOZ_ASSERT(spec->isKind(isImport ? ParseNodeKind::ImportSpec
434 : ParseNodeKind::ExportSpec));
435 MOZ_ASSERT(spec->left()->isKind(ParseNodeKind::Name) ||
436 spec->left()->isKind(ParseNodeKind::StringExpr));
437 MOZ_ASSERT(spec->right()->isKind(ParseNodeKind::Name) ||
438 spec->right()->isKind(ParseNodeKind::StringExpr));
439 }
440 }
441 }
442 #endif
443 return true;
444 }
445
446 public:
visitImportSpecList(ListNode * pn)447 [[nodiscard]] bool visitImportSpecList(ListNode* pn) {
448 return internalVisitSpecList(pn);
449 }
450
visitExportSpecList(ListNode * pn)451 [[nodiscard]] bool visitExportSpecList(ListNode* pn) {
452 return internalVisitSpecList(pn);
453 }
454
NameResolver(JSContext * cx,ParserAtomsTable & parserAtoms)455 explicit NameResolver(JSContext* cx, ParserAtomsTable& parserAtoms)
456 : ParseNodeVisitor(cx),
457 parserAtoms_(parserAtoms),
458 nparents_(0),
459 buf_(cx) {}
460
461 /*
462 * Resolve names for all anonymous functions in the given ParseNode tree.
463 */
visit(ParseNode * pn)464 [[nodiscard]] bool visit(ParseNode* pn) {
465 // Push pn to the parse node stack.
466 if (nparents_ >= MaxParents) {
467 // Silently skip very deeply nested functions.
468 return true;
469 }
470 auto initialParents = nparents_;
471 parents_[initialParents] = pn;
472 nparents_++;
473
474 bool ok = Base::visit(pn);
475
476 // Pop pn from the parse node stack.
477 nparents_--;
478 MOZ_ASSERT(initialParents == nparents_, "nparents imbalance detected");
479 MOZ_ASSERT(parents_[initialParents] == pn,
480 "pushed child shouldn't change underneath us");
481 AlwaysPoison(&parents_[initialParents], JS_OOB_PARSE_NODE_PATTERN,
482 sizeof(parents_[initialParents]), MemCheckKind::MakeUndefined);
483
484 return ok;
485 }
486 };
487
488 } /* anonymous namespace */
489
NameFunctions(JSContext * cx,ParserAtomsTable & parserAtoms,ParseNode * pn)490 bool frontend::NameFunctions(JSContext* cx, ParserAtomsTable& parserAtoms,
491 ParseNode* pn) {
492 AutoTraceLog traceLog(TraceLoggerForCurrentThread(cx),
493 TraceLogger_BytecodeNameFunctions);
494 NameResolver nr(cx, parserAtoms);
495 return nr.visit(pn);
496 }
497