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