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