1/*
2 * Copyright (C) 2015-2019 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "AbstractModuleRecord.h"
28
29#include "Error.h"
30#include "Interpreter.h"
31#include "JSCInlines.h"
32#include "JSMap.h"
33#include "JSModuleEnvironment.h"
34#include "JSModuleNamespaceObject.h"
35#include "JSModuleRecord.h"
36#include "UnlinkedModuleProgramCodeBlock.h"
37#include "WebAssemblyModuleRecord.h"
38#include <wtf/Optional.h>
39
40namespace JSC {
41namespace AbstractModuleRecordInternal {
42static constexpr bool verbose = false;
43} // namespace AbstractModuleRecordInternal
44
45const ClassInfo AbstractModuleRecord::s_info = { "AbstractModuleRecord", &Base::s_info, nullptr, nullptr, CREATE_METHOD_TABLE(AbstractModuleRecord) };
46
47AbstractModuleRecord::AbstractModuleRecord(VM& vm, Structure* structure, const Identifier& moduleKey)
48 : Base(vm, structure)
49 , m_moduleKey(moduleKey)
50{
51}
52
53void AbstractModuleRecord::destroy(JSCell* cell)
54{
55 AbstractModuleRecord* thisObject = static_cast<AbstractModuleRecord*>(cell);
56 thisObject->AbstractModuleRecord::~AbstractModuleRecord();
57}
58
59void AbstractModuleRecord::finishCreation(JSGlobalObject* globalObject, VM& vm)
60{
61 Base::finishCreation(vm);
62 ASSERT(inherits(vm, info()));
63
64 auto scope = DECLARE_THROW_SCOPE(vm);
65 JSMap* map = JSMap::create(globalObject, vm, globalObject->mapStructure());
66 scope.releaseAssertNoException();
67 m_dependenciesMap.set(vm, this, map);
68 putDirect(vm, Identifier::fromString(vm, "dependenciesMap"_s), m_dependenciesMap.get());
69}
70
71void AbstractModuleRecord::visitChildren(JSCell* cell, SlotVisitor& visitor)
72{
73 AbstractModuleRecord* thisObject = jsCast<AbstractModuleRecord*>(cell);
74 ASSERT_GC_OBJECT_INHERITS(thisObject, info());
75 Base::visitChildren(thisObject, visitor);
76 visitor.append(thisObject->m_moduleEnvironment);
77 visitor.append(thisObject->m_moduleNamespaceObject);
78 visitor.append(thisObject->m_dependenciesMap);
79}
80
81void AbstractModuleRecord::appendRequestedModule(const Identifier& moduleName)
82{
83 m_requestedModules.add(moduleName.impl());
84}
85
86void AbstractModuleRecord::addStarExportEntry(const Identifier& moduleName)
87{
88 m_starExportEntries.add(moduleName.impl());
89}
90
91void AbstractModuleRecord::addImportEntry(const ImportEntry& entry)
92{
93 bool isNewEntry = m_importEntries.add(entry.localName.impl(), entry).isNewEntry;
94 ASSERT_UNUSED(isNewEntry, isNewEntry); // This is guaranteed by the parser.
95}
96
97void AbstractModuleRecord::addExportEntry(const ExportEntry& entry)
98{
99 bool isNewEntry = m_exportEntries.add(entry.exportName.impl(), entry).isNewEntry;
100 ASSERT_UNUSED(isNewEntry, isNewEntry); // This is guaranteed by the parser.
101}
102
103auto AbstractModuleRecord::tryGetImportEntry(UniquedStringImpl* localName) -> Optional<ImportEntry>
104{
105 const auto iterator = m_importEntries.find(localName);
106 if (iterator == m_importEntries.end())
107 return WTF::nullopt;
108 return Optional<ImportEntry>(iterator->value);
109}
110
111auto AbstractModuleRecord::tryGetExportEntry(UniquedStringImpl* exportName) -> Optional<ExportEntry>
112{
113 const auto iterator = m_exportEntries.find(exportName);
114 if (iterator == m_exportEntries.end())
115 return WTF::nullopt;
116 return Optional<ExportEntry>(iterator->value);
117}
118
119auto AbstractModuleRecord::ExportEntry::createLocal(const Identifier& exportName, const Identifier& localName) -> ExportEntry
120{
121 return ExportEntry { Type::Local, exportName, Identifier(), Identifier(), localName };
122}
123
124auto AbstractModuleRecord::ExportEntry::createIndirect(const Identifier& exportName, const Identifier& importName, const Identifier& moduleName) -> ExportEntry
125{
126 return ExportEntry { Type::Indirect, exportName, moduleName, importName, Identifier() };
127}
128
129auto AbstractModuleRecord::Resolution::notFound() -> Resolution
130{
131 return Resolution { Type::NotFound, nullptr, Identifier() };
132}
133
134auto AbstractModuleRecord::Resolution::error() -> Resolution
135{
136 return Resolution { Type::Error, nullptr, Identifier() };
137}
138
139auto AbstractModuleRecord::Resolution::ambiguous() -> Resolution
140{
141 return Resolution { Type::Ambiguous, nullptr, Identifier() };
142}
143
144AbstractModuleRecord* AbstractModuleRecord::hostResolveImportedModule(JSGlobalObject* globalObject, const Identifier& moduleName)
145{
146 VM& vm = globalObject->vm();
147 auto scope = DECLARE_THROW_SCOPE(vm);
148 JSValue moduleNameValue = identifierToJSValue(vm, moduleName);
149 JSValue entry = m_dependenciesMap->JSMap::get(globalObject, moduleNameValue);
150 RETURN_IF_EXCEPTION(scope, nullptr);
151 RELEASE_AND_RETURN(scope, jsCast<AbstractModuleRecord*>(entry.get(globalObject, Identifier::fromString(vm, "module"))));
152}
153
154auto AbstractModuleRecord::resolveImport(JSGlobalObject* globalObject, const Identifier& localName) -> Resolution
155{
156 VM& vm = globalObject->vm();
157 auto scope = DECLARE_THROW_SCOPE(vm);
158
159 Optional<ImportEntry> optionalImportEntry = tryGetImportEntry(localName.impl());
160 if (!optionalImportEntry)
161 return Resolution::notFound();
162
163 const ImportEntry& importEntry = *optionalImportEntry;
164 if (importEntry.type == AbstractModuleRecord::ImportEntryType::Namespace)
165 return Resolution::notFound();
166
167 AbstractModuleRecord* importedModule = hostResolveImportedModule(globalObject, importEntry.moduleRequest);
168 RETURN_IF_EXCEPTION(scope, Resolution::error());
169 return importedModule->resolveExport(globalObject, importEntry.importName);
170}
171
172struct AbstractModuleRecord::ResolveQuery {
173 struct Hash {
174 static unsigned hash(const ResolveQuery&);
175 static bool equal(const ResolveQuery&, const ResolveQuery&);
176 static constexpr bool safeToCompareToEmptyOrDeleted = true;
177 };
178 using HashTraits = WTF::CustomHashTraits<ResolveQuery>;
179
180 ResolveQuery(AbstractModuleRecord* moduleRecord, UniquedStringImpl* exportName)
181 : moduleRecord(moduleRecord)
182 , exportName(exportName)
183 {
184 }
185
186 ResolveQuery(AbstractModuleRecord* moduleRecord, const Identifier& exportName)
187 : ResolveQuery(moduleRecord, exportName.impl())
188 {
189 }
190
191 enum EmptyValueTag { EmptyValue };
192 ResolveQuery(EmptyValueTag)
193 {
194 }
195
196 enum DeletedValueTag { DeletedValue };
197 ResolveQuery(DeletedValueTag)
198 : moduleRecord(nullptr)
199 , exportName(WTF::HashTableDeletedValue)
200 {
201 }
202
203 bool isEmptyValue() const
204 {
205 return !exportName;
206 }
207
208 bool isDeletedValue() const
209 {
210 return exportName.isHashTableDeletedValue();
211 }
212
213 void dump(PrintStream& out) const
214 {
215 if (!moduleRecord) {
216 out.print("<empty>");
217 return;
218 }
219 out.print(moduleRecord->moduleKey(), " \"", exportName.get(), "\"");
220 }
221
222 // The module record is not marked from the GC. But these records are reachable from the JSGlobalObject.
223 // So we don't care the reachability to this record.
224 AbstractModuleRecord* moduleRecord;
225 RefPtr<UniquedStringImpl> exportName;
226};
227
228inline unsigned AbstractModuleRecord::ResolveQuery::Hash::hash(const ResolveQuery& query)
229{
230 return WTF::PtrHash<AbstractModuleRecord*>::hash(query.moduleRecord) + IdentifierRepHash::hash(query.exportName);
231}
232
233inline bool AbstractModuleRecord::ResolveQuery::Hash::equal(const ResolveQuery& lhs, const ResolveQuery& rhs)
234{
235 return lhs.moduleRecord == rhs.moduleRecord && lhs.exportName == rhs.exportName;
236}
237
238auto AbstractModuleRecord::tryGetCachedResolution(UniquedStringImpl* exportName) -> Optional<Resolution>
239{
240 const auto iterator = m_resolutionCache.find(exportName);
241 if (iterator == m_resolutionCache.end())
242 return WTF::nullopt;
243 return Optional<Resolution>(iterator->value);
244}
245
246void AbstractModuleRecord::cacheResolution(UniquedStringImpl* exportName, const Resolution& resolution)
247{
248 m_resolutionCache.add(exportName, resolution);
249}
250
251auto AbstractModuleRecord::resolveExportImpl(JSGlobalObject* globalObject, const ResolveQuery& root) -> Resolution
252{
253 VM& vm = globalObject->vm();
254 auto scope = DECLARE_THROW_SCOPE(vm);
255
256 if (AbstractModuleRecordInternal::verbose)
257 dataLog("Resolving ", root, "\n");
258
259 // https://tc39.github.io/ecma262/#sec-resolveexport
260
261 // How to avoid C++ recursion in this function:
262 // This function avoids C++ recursion of the naive ResolveExport implementation.
263 // Flatten the recursion to the loop with the task queue and frames.
264 //
265 // 1. pendingTasks
266 // We enqueue the recursive resolveExport call to this queue to avoid recursive calls in C++.
267 // The task has 3 types. (1) Query, (2) IndirectFallback and (3) GatherStars.
268 // (1) Query
269 // Querying the resolution to the current module.
270 // (2) IndirectFallback
271 // Examine the result of the indirect export resolution. Only when the indirect export resolution fails,
272 // we look into the star exports. (step 5-a-vi).
273 // (3) GatherStars
274 // Examine the result of the star export resolutions.
275 //
276 // 2. frames
277 // When the spec calls the resolveExport recursively, instead we append the frame
278 // (that holds the result resolution) to the frames and enqueue the task to the pendingTasks.
279 // The entry in the frames means the *local* resolution result of the specific recursive resolveExport.
280 //
281 // We should maintain the local resolution result instead of holding the global resolution result only.
282 // For example,
283 //
284 // star
285 // (1) ---> (2) "Resolve"
286 // |
287 // |
288 // +-> (3) "NotFound"
289 // |
290 // | star
291 // +-> (4) ---> (5) "Resolve" [here]
292 // |
293 // |
294 // +-> (6) "Error"
295 //
296 // Consider the above graph. The numbers represents the modules. Now we are [here].
297 // If we only hold the global resolution result during the resolveExport operation, [here],
298 // we decide the entire result of resolveExport is "Ambiguous", because there are multiple
299 // "Resolve" (in module (2) and (5)). However, this should become "Error" because (6) will
300 // propagate "Error" state to the (4), (4) will become "Error" and then, (1) will become
301 // "Error". We should aggregate the results at the star exports point ((4) and (1)).
302 //
303 // Usually, both "Error" and "Ambiguous" states will throw the syntax error. So except for the content of the
304 // error message, there are no difference. (And if we fix the (6) that raises "Error", next, it will produce
305 // the "Ambiguous" error due to (5). Anyway, user need to fix the both. So which error should be raised at first
306 // doesn't matter so much.
307 //
308 // However, this may become the problem under the module namespace creation.
309 // http://www.ecma-international.org/ecma-262/6.0/#sec-getmodulenamespace
310 // section 15.2.1.18, step 3-d-ii
311 // Here, we distinguish "Ambiguous" and "Error". When "Error" state is produced, we need to throw the propagated error.
312 // But if "Ambiguous" state comes, we just ignore the result.
313 // To follow the requirement strictly, in this implementation, we keep the local resolution result to produce the
314 // correct result under the above complex cases.
315
316 // Caching strategy:
317 // The resolveExport operation is frequently called. So caching results is important.
318 // We observe the following aspects and based on them construct the caching strategy.
319 // Here, we attempt to cache the resolution by constructing the map in module records.
320 // That means Module -> ExportName -> Maybe<Resolution>.
321 // Technically, all the AbstractModuleRecords have the Map<ExportName, Resolution> for caching.
322 //
323 // The important observations are that,
324 //
325 // - *cacheable* means that traversing to this node from a path will produce the same results as starting from this node.
326 //
327 // Here, we define the resovling route. We represent [?] as the module that has the local binding.
328 // And (?) as the module without the local binding.
329 //
330 // @ -> (A) -> (B) -> [C]
331 //
332 // We list the resolving route for each node.
333 //
334 // (A): (A) -> (B) -> [C]
335 // (B): (B) -> [C]
336 // [C]: [C]
337 //
338 // In this case, if we start the tracing from (B), the resolving route becomes (B) -> [C].
339 // So this is the same. At that time, we can say (B) is cacheable in the first tracing.
340 //
341 // - The cache ability of a node depends on the resolving route from this node.
342 //
343 // 1. The starting point is always cacheable.
344 //
345 // 2. A module that has resolved a local binding is always cacheable.
346 //
347 // @ -> (A) -> [B]
348 //
349 // In the above case, we can see the [B] as cacheable.
350 // This is because when starting from [B] node, we immediately resolve with the local binding.
351 // So the resolving route from [B] does not depend on the starting point.
352 //
353 // 3. If we don't follow any star links during the resolution, we can see all the traced nodes are cacheable.
354 //
355 // If there are non star links, it means that there is *no branch* in the module dependency graph.
356 // This *no branch* feature makes all the modules cachable.
357 //
358 // I.e, if we traverse one star link (even if we successfully resolve that star link),
359 // we must still traverse all other star links. I would also explain we don't run into
360 // this when resolving a local/indirect link. When resolving a local/indirect link,
361 // we won't traverse any star links.
362 // And since the module can hold only one local/indirect link for the specific export name (if there
363 // are multiple local/indirect links that has the same export name, it should be syntax error in the
364 // parsing phase.), there is no multiple outgoing links from a module.
365 //
366 // @ -> (A) --> (B) -> [C] -> (D) -> (E) -+
367 // ^ |
368 // | |
369 // +------------------------+
370 //
371 // When starting from @, [C] will be found as the module resolving the given binding.
372 // In this case, (B) can cache this resolution. Since the resolving route is the same to the one when
373 // starting from (B). After caching the above result, we attempt to resolve the same binding from (D).
374 //
375 // @
376 // |
377 // v
378 // @ -> (A) --> (B) -> [C] -> (D) -> (E) -+
379 // ^ |
380 // | |
381 // +------------------------+
382 //
383 // In this case, we can use the (B)'s cached result. And (E) can be cached.
384 //
385 // (E): The resolving route is now (E) -> (B) -> [C]. That is the same when starting from (E).
386 //
387 // No branching makes that the problematic *once-visited* node cannot be seen.
388 // The *once-visited* node makes the resolving route changed since when we see the *once-visited* node,
389 // we stop tracing this.
390 //
391 // If there is no star links and if we look *once-visited* node under no branching graph, *once-visited*
392 // node cannot resolve the requested binding. If the *once-visited* node can resolve the binding, we
393 // should have already finished the resolution before reaching this *once-visited* node.
394 //
395 // 4. Once we follow star links, we should not retrieve the result from the cache and should not cache.
396 //
397 // Star links are only the way to introduce branch.
398 // Once we follow the star links during the resolution, we cannot cache naively.
399 // This is because the cacheability depends on the resolving route. And branching produces the problematic *once-visited*
400 // nodes. Since we don't follow the *once-visited* node, the resolving route from the node becomes different from
401 // the resolving route when starting from this node.
402 //
403 // The following example explains when we should not retrieve the cache and cache the result.
404 //
405 // +----> (D) ------+
406 // | |
407 // | v
408 // (A) *----+----> (B) ---> [C]
409 // ^
410 // |
411 // @
412 //
413 // When starting from (B), we find [C]. In this resolving route, we don't find any star link.
414 // And by definition, (B) and [C] are cachable. (B) is the starting point. And [C] has the local binding.
415 //
416 // +----> (D) ------+
417 // | |
418 // | v
419 // @-> (A) *----+----> (B) ---> [C]
420 //
421 // But when starting from (A), we should not get the value from the cache. Because,
422 //
423 // 1. When looking (D), we reach [C] and make both resolved.
424 // 2. When looking (B), if we retrieved the last cache from (B), (B) becomes resolved.
425 // 3. But actually, (B) is not-found in this trial because (C) is already *once-visited*.
426 // 4. If we accidentally make (B) resolved, (A) becomes ambiguous. But the correct answer is resolved.
427 //
428 // Why is this problem caused? This is because the *once-visited* node makes the result not-found.
429 // In the second trial, (B) -> [C] result is changed from resolved to not-found.
430 //
431 // When does this become a problem? If the status of the *once-visited* node group is resolved,
432 // changing the result to not-found makes the result changed.
433 //
434 // This problem does not happen when we don't see any star link yet. Now, consider the minimum case.
435 //
436 // @-> (A) -> [ some graph ]
437 // ^ |
438 // | |
439 // +------------+
440 //
441 // In (A), we don't see any star link yet. So we can say that all the visited nodes does not have any local
442 // resolution. Because if they had a local/indirect resolution, we should have already finished the tracing.
443 //
444 // And even if the some graph will see the *once-visited* node (in this case, (A)), that does not affect the
445 // result of the resolution. Because even if we follow the link to (A) or not follow the link to (A), the status
446 // of the link is always not-found since (A) does not have any local resolution.
447 // In the above case, we can use the result of the [some graph].
448 //
449 // 5. Once we see star links, even if we have not yet traversed that star link path, we should disable caching.
450 //
451 // Here is the reason why:
452 //
453 // +-------------+
454 // | |
455 // v |
456 // (A) -> (B) -> (C) *-> [E]
457 // * ^
458 // | |
459 // v @
460 // [D]
461 //
462 // In the above case, (C) will be resolved with [D].
463 // (C) will see (A) and (A) gives up in (A) -> (B) -> (C) route. So, (A) will fallback to [D].
464 //
465 // +-------------+
466 // | |
467 // v |
468 // @-> (A) -> (B) -> (C) *-> [E]
469 // *
470 // |
471 // v
472 // [D]
473 //
474 // But in this case, (A) will be resolved with [E] (not [D]).
475 // (C) will attempt to follow the link to (A), but it fails.
476 // So (C) will fallback to the star link and found [E]. In this senario,
477 // (C) is now resolved with [E]'s result.
478 //
479 // The cause of this problem is also the same to 4.
480 // In the latter case, when looking (C), we cannot use the cached result in (C).
481 // Because the cached result of (C) depends on the *once-visited* node (A) and
482 // (A) has the fallback system with the star link.
483 // In the latter trial, we now assume that (A)'s status is not-found.
484 // But, actually, in the former trial, (A)'s status becomes resolved due to the fallback to the [D].
485 //
486 // To summarize the observations.
487 //
488 // 1. The starting point is always cacheable.
489 // 2. A module that has resolved a local binding is always cacheable.
490 // 3. If we don't follow any star links during the resolution, we can see all the traced nodes are cacheable.
491 // 4. Once we follow star links, we should not retrieve the result from the cache and should not cache the result.
492 // 5. Once we see star links, even if we have not yet traversed that star link path, we should disable caching.
493
494 using ResolveSet = WTF::HashSet<ResolveQuery, ResolveQuery::Hash, ResolveQuery::HashTraits>;
495 enum class Type { Query, IndirectFallback, GatherStars };
496 struct Task {
497 ResolveQuery query;
498 Type type;
499 };
500
501 auto typeString = [] (Type type) -> const char* {
502 switch (type) {
503 case Type::Query:
504 return "Query";
505 case Type::IndirectFallback:
506 return "IndirectFallback";
507 case Type::GatherStars:
508 return "GatherStars";
509 }
510 RELEASE_ASSERT_NOT_REACHED();
511 return nullptr;
512 };
513
514 Vector<Task, 8> pendingTasks;
515 ResolveSet resolveSet;
516
517 Vector<Resolution, 8> frames;
518
519 bool foundStarLinks = false;
520
521 frames.append(Resolution::notFound());
522
523 // Call when the query is not resolved in the current module.
524 // It will enqueue the star resolution requests. Return "false" if the error occurs.
525 auto resolveNonLocal = [&](const ResolveQuery& query) -> bool {
526 // https://tc39.github.io/ecma262/#sec-resolveexport
527 // section 15.2.1.16.3, step 6
528 // If the "default" name is not resolved in the current module, we need to throw an error and stop resolution immediately,
529 // Rationale to this error: A default export cannot be provided by an export *.
530 VM& vm = globalObject->vm();
531 auto scope = DECLARE_THROW_SCOPE(vm);
532 if (query.exportName == vm.propertyNames->defaultKeyword.impl())
533 return false;
534
535 // Enqueue the task to gather the results of the stars.
536 // And append the new Resolution frame to gather the local result of the stars.
537 pendingTasks.append(Task { query, Type::GatherStars });
538 foundStarLinks = true;
539 frames.append(Resolution::notFound());
540
541 // Enqueue the tasks in reverse order.
542 for (auto iterator = query.moduleRecord->starExportEntries().rbegin(), end = query.moduleRecord->starExportEntries().rend(); iterator != end; ++iterator) {
543 const RefPtr<UniquedStringImpl>& starModuleName = *iterator;
544 AbstractModuleRecord* importedModuleRecord = query.moduleRecord->hostResolveImportedModule(globalObject, Identifier::fromUid(vm, starModuleName.get()));
545 RETURN_IF_EXCEPTION(scope, false);
546 pendingTasks.append(Task { ResolveQuery(importedModuleRecord, query.exportName.get()), Type::Query });
547 }
548 return true;
549 };
550
551 // Return the current resolution value of the top frame.
552 auto currentTop = [&] () -> Resolution& {
553 ASSERT(!frames.isEmpty());
554 return frames.last();
555 };
556
557 // Merge the given resolution to the current resolution value of the top frame.
558 // If there is ambiguity, return "false". When the "false" is returned, we should make the result "ambiguous".
559 auto mergeToCurrentTop = [&] (const Resolution& resolution) -> bool {
560 if (resolution.type == Resolution::Type::NotFound)
561 return true;
562
563 if (currentTop().type == Resolution::Type::NotFound) {
564 currentTop() = resolution;
565 return true;
566 }
567
568 if (currentTop().moduleRecord != resolution.moduleRecord || currentTop().localName != resolution.localName)
569 return false;
570
571 return true;
572 };
573
574 auto cacheResolutionForQuery = [] (const ResolveQuery& query, const Resolution& resolution) {
575 ASSERT(resolution.type == Resolution::Type::Resolved);
576 query.moduleRecord->cacheResolution(query.exportName.get(), resolution);
577 };
578
579 pendingTasks.append(Task { root, Type::Query });
580 while (!pendingTasks.isEmpty()) {
581 const Task task = pendingTasks.takeLast();
582 const ResolveQuery& query = task.query;
583
584 if (AbstractModuleRecordInternal::verbose)
585 dataLog(" ", typeString(task.type), " ", task.query, "\n");
586
587 switch (task.type) {
588 case Type::Query: {
589 AbstractModuleRecord* moduleRecord = query.moduleRecord;
590
591 if (!resolveSet.add(task.query).isNewEntry)
592 continue;
593
594 // 5. Once we see star links, even if we have not yet traversed that star link path, we should disable caching.
595 if (!moduleRecord->starExportEntries().isEmpty())
596 foundStarLinks = true;
597
598 // 4. Once we follow star links, we should not retrieve the result from the cache and should not cache the result.
599 if (!foundStarLinks) {
600 if (Optional<Resolution> cachedResolution = moduleRecord->tryGetCachedResolution(query.exportName.get())) {
601 if (!mergeToCurrentTop(*cachedResolution))
602 return Resolution::ambiguous();
603 continue;
604 }
605 }
606
607 const Optional<ExportEntry> optionalExportEntry = moduleRecord->tryGetExportEntry(query.exportName.get());
608 if (!optionalExportEntry) {
609 // If there is no matched exported binding in the current module,
610 // we need to look into the stars.
611 bool success = resolveNonLocal(task.query);
612 EXCEPTION_ASSERT(!scope.exception() || !success);
613 if (!success)
614 return Resolution::error();
615 continue;
616 }
617
618 const ExportEntry& exportEntry = *optionalExportEntry;
619 switch (exportEntry.type) {
620 case ExportEntry::Type::Local: {
621 ASSERT(!exportEntry.localName.isNull());
622 Resolution resolution { Resolution::Type::Resolved, moduleRecord, exportEntry.localName };
623 // 2. A module that has resolved a local binding is always cacheable.
624 cacheResolutionForQuery(query, resolution);
625 if (!mergeToCurrentTop(resolution))
626 return Resolution::ambiguous();
627 continue;
628 }
629
630 case ExportEntry::Type::Indirect: {
631 AbstractModuleRecord* importedModuleRecord = moduleRecord->hostResolveImportedModule(globalObject, exportEntry.moduleName);
632 RETURN_IF_EXCEPTION(scope, Resolution::error());
633
634 // When the imported module does not produce any resolved binding, we need to look into the stars in the *current*
635 // module. To do this, we append the `IndirectFallback` task to the task queue.
636 pendingTasks.append(Task { query, Type::IndirectFallback });
637 // And append the new Resolution frame to check the indirect export will be resolved or not.
638 frames.append(Resolution::notFound());
639 pendingTasks.append(Task { ResolveQuery(importedModuleRecord, exportEntry.importName), Type::Query });
640 continue;
641 }
642 }
643 break;
644 }
645
646 case Type::IndirectFallback: {
647 Resolution resolution = frames.takeLast();
648
649 if (resolution.type == Resolution::Type::NotFound) {
650 // Indirect export entry does not produce any resolved binding.
651 // So we will investigate the stars.
652 bool success = resolveNonLocal(task.query);
653 EXCEPTION_ASSERT(!scope.exception() || !success);
654 if (!success)
655 return Resolution::error();
656 continue;
657 }
658
659 ASSERT_WITH_MESSAGE(resolution.type == Resolution::Type::Resolved, "When we see Error and Ambiguous, we immediately return from this loop. So here, only Resolved comes.");
660
661 // 3. If we don't follow any star links during the resolution, we can see all the traced nodes are cacheable.
662 // 4. Once we follow star links, we should not retrieve the result from the cache and should not cache the result.
663 if (!foundStarLinks)
664 cacheResolutionForQuery(query, resolution);
665
666 // If indirect export entry produces Resolved, we should merge it to the upper frame.
667 // And do not investigate the stars of the current module.
668 if (!mergeToCurrentTop(resolution))
669 return Resolution::ambiguous();
670 break;
671 }
672
673 case Type::GatherStars: {
674 Resolution resolution = frames.takeLast();
675 ASSERT_WITH_MESSAGE(resolution.type == Resolution::Type::Resolved || resolution.type == Resolution::Type::NotFound, "When we see Error and Ambiguous, we immediately return from this loop. So here, only Resolved and NotFound comes.");
676
677 // Merge the star resolution to the upper frame.
678 if (!mergeToCurrentTop(resolution))
679 return Resolution::ambiguous();
680 break;
681 }
682 }
683 }
684
685 ASSERT(frames.size() == 1);
686 // 1. The starting point is always cacheable.
687 if (frames[0].type == Resolution::Type::Resolved)
688 cacheResolutionForQuery(root, frames[0]);
689 return frames[0];
690}
691
692auto AbstractModuleRecord::resolveExport(JSGlobalObject* globalObject, const Identifier& exportName) -> Resolution
693{
694 // Look up the cached resolution first before entering the resolving loop, since the loop setup takes some cost.
695 if (Optional<Resolution> cachedResolution = tryGetCachedResolution(exportName.impl()))
696 return *cachedResolution;
697 return resolveExportImpl(globalObject, ResolveQuery(this, exportName.impl()));
698}
699
700static void getExportedNames(JSGlobalObject* globalObject, AbstractModuleRecord* root, IdentifierSet& exportedNames)
701{
702 VM& vm = globalObject->vm();
703 auto scope = DECLARE_THROW_SCOPE(vm);
704
705 HashSet<AbstractModuleRecord*> exportStarSet;
706 Vector<AbstractModuleRecord*, 8> pendingModules;
707
708 pendingModules.append(root);
709
710 while (!pendingModules.isEmpty()) {
711 AbstractModuleRecord* moduleRecord = pendingModules.takeLast();
712 if (exportStarSet.contains(moduleRecord))
713 continue;
714 exportStarSet.add(moduleRecord);
715
716 for (const auto& pair : moduleRecord->exportEntries()) {
717 const AbstractModuleRecord::ExportEntry& exportEntry = pair.value;
718 if (moduleRecord == root || vm.propertyNames->defaultKeyword != exportEntry.exportName)
719 exportedNames.add(exportEntry.exportName.impl());
720 }
721
722 for (const auto& starModuleName : moduleRecord->starExportEntries()) {
723 AbstractModuleRecord* requestedModuleRecord = moduleRecord->hostResolveImportedModule(globalObject, Identifier::fromUid(vm, starModuleName.get()));
724 RETURN_IF_EXCEPTION(scope, void());
725 pendingModules.append(requestedModuleRecord);
726 }
727 }
728}
729
730JSModuleNamespaceObject* AbstractModuleRecord::getModuleNamespace(JSGlobalObject* globalObject)
731{
732 VM& vm = globalObject->vm();
733 auto scope = DECLARE_THROW_SCOPE(vm);
734
735 // http://www.ecma-international.org/ecma-262/6.0/#sec-getmodulenamespace
736 if (m_moduleNamespaceObject)
737 return m_moduleNamespaceObject.get();
738
739 IdentifierSet exportedNames;
740 getExportedNames(globalObject, this, exportedNames);
741 RETURN_IF_EXCEPTION(scope, nullptr);
742
743 Vector<std::pair<Identifier, Resolution>> resolutions;
744 for (auto& name : exportedNames) {
745 Identifier ident = Identifier::fromUid(vm, name.get());
746 const Resolution resolution = resolveExport(globalObject, ident);
747 RETURN_IF_EXCEPTION(scope, nullptr);
748 switch (resolution.type) {
749 case Resolution::Type::NotFound:
750 throwSyntaxError(globalObject, scope, makeString("Exported binding name '", String(name.get()), "' is not found."));
751 return nullptr;
752
753 case Resolution::Type::Error:
754 throwSyntaxError(globalObject, scope, makeString("Exported binding name 'default' cannot be resolved by star export entries."));
755 return nullptr;
756
757 case Resolution::Type::Ambiguous:
758 break;
759
760 case Resolution::Type::Resolved:
761 resolutions.append({ WTFMove(ident), resolution });
762 break;
763 }
764 }
765
766 auto* moduleNamespaceObject = JSModuleNamespaceObject::create(globalObject, globalObject->moduleNamespaceObjectStructure(), this, WTFMove(resolutions));
767 RETURN_IF_EXCEPTION(scope, nullptr);
768 m_moduleNamespaceObject.set(vm, this, moduleNamespaceObject);
769 return moduleNamespaceObject;
770}
771
772void AbstractModuleRecord::link(JSGlobalObject* globalObject, JSValue scriptFetcher)
773{
774 VM& vm = globalObject->vm();
775 if (auto* jsModuleRecord = jsDynamicCast<JSModuleRecord*>(vm, this))
776 return jsModuleRecord->link(globalObject, scriptFetcher);
777#if ENABLE(WEBASSEMBLY)
778 if (auto* wasmModuleRecord = jsDynamicCast<WebAssemblyModuleRecord*>(vm, this))
779 return wasmModuleRecord->link(globalObject, scriptFetcher, nullptr, Wasm::CreationMode::FromModuleLoader);
780#endif
781 RELEASE_ASSERT_NOT_REACHED();
782}
783
784JS_EXPORT_PRIVATE JSValue AbstractModuleRecord::evaluate(JSGlobalObject* globalObject)
785{
786 VM& vm = globalObject->vm();
787 if (auto* jsModuleRecord = jsDynamicCast<JSModuleRecord*>(vm, this))
788 return jsModuleRecord->evaluate(globalObject);
789#if ENABLE(WEBASSEMBLY)
790 if (auto* wasmModuleRecord = jsDynamicCast<WebAssemblyModuleRecord*>(vm, this))
791 return wasmModuleRecord->evaluate(globalObject);
792#endif
793 RELEASE_ASSERT_NOT_REACHED();
794 return jsUndefined();
795}
796
797static String printableName(const RefPtr<UniquedStringImpl>& uid)
798{
799 if (uid->isSymbol())
800 return uid.get();
801 return WTF::makeString("'", String(uid.get()), "'");
802}
803
804static String printableName(const Identifier& ident)
805{
806 return printableName(ident.impl());
807}
808
809void AbstractModuleRecord::dump()
810{
811 dataLog("\nAnalyzing ModuleRecord key(", printableName(m_moduleKey), ")\n");
812
813 dataLog(" Dependencies: ", m_requestedModules.size(), " modules\n");
814 for (const auto& moduleName : m_requestedModules)
815 dataLog(" module(", printableName(moduleName), ")\n");
816
817 dataLog(" Import: ", m_importEntries.size(), " entries\n");
818 for (const auto& pair : m_importEntries) {
819 const ImportEntry& importEntry = pair.value;
820 dataLog(" import(", printableName(importEntry.importName), "), local(", printableName(importEntry.localName), "), module(", printableName(importEntry.moduleRequest), ")\n");
821 }
822
823 dataLog(" Export: ", m_exportEntries.size(), " entries\n");
824 for (const auto& pair : m_exportEntries) {
825 const ExportEntry& exportEntry = pair.value;
826 switch (exportEntry.type) {
827 case ExportEntry::Type::Local:
828 dataLog(" [Local] ", "export(", printableName(exportEntry.exportName), "), local(", printableName(exportEntry.localName), ")\n");
829 break;
830
831 case ExportEntry::Type::Indirect:
832 dataLog(" [Indirect] ", "export(", printableName(exportEntry.exportName), "), import(", printableName(exportEntry.importName), "), module(", printableName(exportEntry.moduleName), ")\n");
833 break;
834 }
835 }
836 for (const auto& moduleName : m_starExportEntries)
837 dataLog(" [Star] module(", printableName(moduleName.get()), ")\n");
838}
839
840} // namespace JSC
841