[ES6] Cache the resolution result in JSModuleRecord
authorutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 14 Sep 2015 21:15:19 +0000 (21:15 +0000)
committerutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 14 Sep 2015 21:15:19 +0000 (21:15 +0000)
https://bugs.webkit.org/show_bug.cgi?id=148896

Reviewed by Saam Barati.

The resolveExport operation is frequently called. For example,
1. When instantiating the module environment, we call it for each exported name and imported
   name.
2. When linking the imported module environment to the code block, we call it to resolve the
   resolution.
3. When looking up the property from the namespace object, we call it to look up the original
   module for the imported binding.
4. When creating the namespace object, we need to collect all the exported names from the module
   and need to resolve them by calling resolveExport.

However, resolveExport takes some cost. It traces the imported modules and resolves the reference
queried by the original module.

The resolveExport operation is pure function; given a module record and an export name,
it always returns the same result. So we cache resolution results in the module record to avoid
repeated resolveExport calls with the same arguments.
Here, we only cache the correctly resolved references, since,
1. We rarely looked up the non-correctly-resolved ones. In the linking phase, attempting to
   resolve non-correctly-resolved ones throws a syntax error. So only namespace object creation
   phase does it in a syntax valid script.
2. This strategy limits the size of the cache map. The number of the correctly exported bindings
   is defined by the modules' code. So the size does not become infinitely large.

Currently, the all modules cannot be linked twice. For example,

  graph 1

  -> (A) -> (B)

  graph 2

  -> (C) -> (A) -> (B)

We cannot test the behavior now because when executing the graph 2, (A) and (B) are already linked,
it raises an error in the current loader spec. But it should be allowed[1] since it will occur when
there is multiple module tag in WebCore.

[1]: https://github.com/whatwg/loader/issues/41

* runtime/JSModuleRecord.cpp:
(JSC::JSModuleRecord::ResolveQuery::Hash::hash):
(JSC::JSModuleRecord::ResolveQuery::Hash::equal):
(JSC::JSModuleRecord::cacheResolution):
(JSC::ResolveQueryHash::hash): Deleted.
(JSC::ResolveQueryHash::equal): Deleted.
(JSC::resolveExportLoop): Deleted.
* runtime/JSModuleRecord.h:
* tests/modules/caching-should-not-make-ambiguous.js: Added.
* tests/modules/caching-should-not-make-ambiguous/A.js: Added.
* tests/modules/caching-should-not-make-ambiguous/B.js: Added.
* tests/modules/caching-should-not-make-ambiguous/C.js: Added.
* tests/modules/caching-should-not-make-ambiguous/D.js: Added.
* tests/modules/caching-should-not-make-ambiguous/main.js: Added.
* tests/modules/different-view.js: Added.
(from.string_appeared_here.shouldThrow):
* tests/modules/different-view/A.js: Added.
* tests/modules/different-view/B.js: Added.
* tests/modules/different-view/C.js: Added.
* tests/modules/different-view/D.js: Added.
* tests/modules/different-view/E.js: Added.
* tests/modules/different-view/main.js: Added.
* tests/modules/fallback-ambiguous.js: Added.
(from.string_appeared_here.shouldThrow):
* tests/modules/fallback-ambiguous/A.js: Added.
* tests/modules/fallback-ambiguous/B.js: Added.
* tests/modules/fallback-ambiguous/C.js: Added.
* tests/modules/fallback-ambiguous/D.js: Added.
* tests/modules/fallback-ambiguous/E.js: Added.
* tests/modules/fallback-ambiguous/main.js: Added.
* tests/modules/self-star-link.js: Added.
* tests/modules/self-star-link/A.js: Added.
* tests/modules/self-star-link/B.js: Added.
* tests/modules/self-star-link/C.js: Added.
* tests/modules/self-star-link/D.js: Added.
* tests/modules/self-star-link/E.js: Added.
* tests/modules/uncacheable-when-see-star.js: Added.
* tests/modules/uncacheable-when-see-star/A-pre.js: Added.
* tests/modules/uncacheable-when-see-star/A.js: Added.
* tests/modules/uncacheable-when-see-star/B.js: Added.
* tests/modules/uncacheable-when-see-star/C.js: Added.
* tests/modules/uncacheable-when-see-star/D.js: Added.
* tests/modules/uncacheable-when-see-star/E-pre.js: Added.
* tests/modules/uncacheable-when-see-star/E.js: Added.
* tests/modules/uncacheable-when-see-star/main1.js: Added.
* tests/modules/uncacheable-when-see-star/main2.js: Added.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@189747 268f45cc-cd09-0410-ab3c-d52691b4dbfc

39 files changed:
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/runtime/JSModuleRecord.cpp
Source/JavaScriptCore/runtime/JSModuleRecord.h
Source/JavaScriptCore/tests/modules/caching-should-not-make-ambiguous.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/caching-should-not-make-ambiguous/A.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/caching-should-not-make-ambiguous/B.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/caching-should-not-make-ambiguous/C.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/caching-should-not-make-ambiguous/D.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/caching-should-not-make-ambiguous/main.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/different-view.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/different-view/A.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/different-view/B.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/different-view/C.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/different-view/D.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/different-view/E.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/different-view/main.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/fallback-ambiguous.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/fallback-ambiguous/A.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/fallback-ambiguous/B.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/fallback-ambiguous/C.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/fallback-ambiguous/D.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/fallback-ambiguous/E.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/fallback-ambiguous/main.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/self-star-link.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/self-star-link/A.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/self-star-link/B.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/self-star-link/C.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/self-star-link/D.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/self-star-link/E.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/uncacheable-when-see-star.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/A-pre.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/A.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/B.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/C.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/D.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/E-pre.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/E.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/main1.js [new file with mode: 0644]
Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/main2.js [new file with mode: 0644]

index 219e8e6..d051e5e 100644 (file)
@@ -1,3 +1,96 @@
+2015-09-14  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        [ES6] Cache the resolution result in JSModuleRecord
+        https://bugs.webkit.org/show_bug.cgi?id=148896
+
+        Reviewed by Saam Barati.
+
+        The resolveExport operation is frequently called. For example,
+        1. When instantiating the module environment, we call it for each exported name and imported
+           name.
+        2. When linking the imported module environment to the code block, we call it to resolve the
+           resolution.
+        3. When looking up the property from the namespace object, we call it to look up the original
+           module for the imported binding.
+        4. When creating the namespace object, we need to collect all the exported names from the module
+           and need to resolve them by calling resolveExport.
+
+        However, resolveExport takes some cost. It traces the imported modules and resolves the reference
+        queried by the original module.
+
+        The resolveExport operation is pure function; given a module record and an export name,
+        it always returns the same result. So we cache resolution results in the module record to avoid
+        repeated resolveExport calls with the same arguments.
+        Here, we only cache the correctly resolved references, since,
+        1. We rarely looked up the non-correctly-resolved ones. In the linking phase, attempting to
+           resolve non-correctly-resolved ones throws a syntax error. So only namespace object creation
+           phase does it in a syntax valid script.
+        2. This strategy limits the size of the cache map. The number of the correctly exported bindings
+           is defined by the modules' code. So the size does not become infinitely large.
+
+        Currently, the all modules cannot be linked twice. For example,
+
+          graph 1
+
+          -> (A) -> (B)
+
+          graph 2
+
+          -> (C) -> (A) -> (B)
+
+        We cannot test the behavior now because when executing the graph 2, (A) and (B) are already linked,
+        it raises an error in the current loader spec. But it should be allowed[1] since it will occur when
+        there is multiple module tag in WebCore.
+
+        [1]: https://github.com/whatwg/loader/issues/41
+
+        * runtime/JSModuleRecord.cpp:
+        (JSC::JSModuleRecord::ResolveQuery::Hash::hash):
+        (JSC::JSModuleRecord::ResolveQuery::Hash::equal):
+        (JSC::JSModuleRecord::cacheResolution):
+        (JSC::ResolveQueryHash::hash): Deleted.
+        (JSC::ResolveQueryHash::equal): Deleted.
+        (JSC::resolveExportLoop): Deleted.
+        * runtime/JSModuleRecord.h:
+        * tests/modules/caching-should-not-make-ambiguous.js: Added.
+        * tests/modules/caching-should-not-make-ambiguous/A.js: Added.
+        * tests/modules/caching-should-not-make-ambiguous/B.js: Added.
+        * tests/modules/caching-should-not-make-ambiguous/C.js: Added.
+        * tests/modules/caching-should-not-make-ambiguous/D.js: Added.
+        * tests/modules/caching-should-not-make-ambiguous/main.js: Added.
+        * tests/modules/different-view.js: Added.
+        (from.string_appeared_here.shouldThrow):
+        * tests/modules/different-view/A.js: Added.
+        * tests/modules/different-view/B.js: Added.
+        * tests/modules/different-view/C.js: Added.
+        * tests/modules/different-view/D.js: Added.
+        * tests/modules/different-view/E.js: Added.
+        * tests/modules/different-view/main.js: Added.
+        * tests/modules/fallback-ambiguous.js: Added.
+        (from.string_appeared_here.shouldThrow):
+        * tests/modules/fallback-ambiguous/A.js: Added.
+        * tests/modules/fallback-ambiguous/B.js: Added.
+        * tests/modules/fallback-ambiguous/C.js: Added.
+        * tests/modules/fallback-ambiguous/D.js: Added.
+        * tests/modules/fallback-ambiguous/E.js: Added.
+        * tests/modules/fallback-ambiguous/main.js: Added.
+        * tests/modules/self-star-link.js: Added.
+        * tests/modules/self-star-link/A.js: Added.
+        * tests/modules/self-star-link/B.js: Added.
+        * tests/modules/self-star-link/C.js: Added.
+        * tests/modules/self-star-link/D.js: Added.
+        * tests/modules/self-star-link/E.js: Added.
+        * tests/modules/uncacheable-when-see-star.js: Added.
+        * tests/modules/uncacheable-when-see-star/A-pre.js: Added.
+        * tests/modules/uncacheable-when-see-star/A.js: Added.
+        * tests/modules/uncacheable-when-see-star/B.js: Added.
+        * tests/modules/uncacheable-when-see-star/C.js: Added.
+        * tests/modules/uncacheable-when-see-star/D.js: Added.
+        * tests/modules/uncacheable-when-see-star/E-pre.js: Added.
+        * tests/modules/uncacheable-when-see-star/E.js: Added.
+        * tests/modules/uncacheable-when-see-star/main1.js: Added.
+        * tests/modules/uncacheable-when-see-star/main2.js: Added.
+
 2015-09-14  Sukolsak Sakshuwong  <sukolsak@gmail.com>
 
         Implement the arithmetic instructions for floats in WebAssembly
index fb36428..843c94e 100644 (file)
@@ -164,7 +164,13 @@ auto JSModuleRecord::resolveImport(ExecState* exec, const Identifier& localName)
     return importedModule->resolveExport(exec, importEntry.importName);
 }
 
-struct ResolveQuery {
+struct JSModuleRecord::ResolveQuery {
+    struct Hash {
+        static unsigned hash(const ResolveQuery&);
+        static bool equal(const ResolveQuery&, const ResolveQuery&);
+        static const bool safeToCompareToEmptyOrDeleted = true;
+    };
+
     ResolveQuery(JSModuleRecord* moduleRecord, UniquedStringImpl* exportName)
         : moduleRecord(moduleRecord)
         , exportName(exportName)
@@ -204,25 +210,34 @@ struct ResolveQuery {
     RefPtr<UniquedStringImpl> exportName;
 };
 
-struct ResolveQueryHash {
-    static unsigned hash(const ResolveQuery&);
-    static bool equal(const ResolveQuery&, const ResolveQuery&);
-    static const bool safeToCompareToEmptyOrDeleted = true;
-};
-
-inline unsigned ResolveQueryHash::hash(const ResolveQuery& query)
+inline unsigned JSModuleRecord::ResolveQuery::Hash::hash(const ResolveQuery& query)
 {
     return WTF::PtrHash<JSModuleRecord*>::hash(query.moduleRecord) + IdentifierRepHash::hash(query.exportName);
 }
 
-inline bool ResolveQueryHash::equal(const ResolveQuery& lhs, const ResolveQuery& rhs)
+inline bool JSModuleRecord::ResolveQuery::Hash::equal(const ResolveQuery& lhs, const ResolveQuery& rhs)
 {
     return lhs.moduleRecord == rhs.moduleRecord && lhs.exportName == rhs.exportName;
 }
 
-static JSModuleRecord::Resolution resolveExportLoop(ExecState* exec, const ResolveQuery& root)
+auto JSModuleRecord::tryGetCachedResolution(UniquedStringImpl* exportName) -> Optional<Resolution>
+{
+    const auto iterator = m_resolutionCache.find(exportName);
+    if (iterator == m_resolutionCache.end())
+        return Nullopt;
+    return Optional<Resolution>(iterator->value);
+}
+
+void JSModuleRecord::cacheResolution(UniquedStringImpl* exportName, const Resolution& resolution)
+{
+    m_resolutionCache.add(exportName, resolution);
+}
+
+auto JSModuleRecord::resolveExportImpl(ExecState* exec, const ResolveQuery& root) -> Resolution
 {
     // http://www.ecma-international.org/ecma-262/6.0/#sec-resolveexport
+
+    // How to avoid C++ recursion in this function:
     // This function avoids C++ recursion of the naive ResolveExport implementation.
     // Flatten the recursion to the loop with the task queue and frames.
     //
@@ -277,8 +292,185 @@ static JSModuleRecord::Resolution resolveExportLoop(ExecState* exec, const Resol
     // To follow the requirement strictly, in this implementation, we keep the local resolution result to produce the
     // correct result under the above complex cases.
 
-    using Resolution = JSModuleRecord::Resolution;
-    typedef WTF::HashSet<ResolveQuery, ResolveQueryHash, WTF::CustomHashTraits<ResolveQuery>> ResolveSet;
+    // Caching strategy:
+    // The resolveExport operation is frequently called. So caching results is important.
+    // We observe the following aspects and based on them construct the caching strategy.
+    // Here, we attempt to cache the resolution by constructing the map in module records.
+    // That means  Module -> ExportName -> Maybe<Resolution>.
+    // Technically, all the JSModuleRecords have the Map<ExportName, Resolution> for caching.
+    //
+    // The important observations are that,
+    //
+    //  - *cacheable* means that traversing to this node from a path will produce the same results as starting from this node.
+    //
+    //    Here, we define the resovling route. We represent [?] as the module that has the local binding.
+    //    And (?) as the module without the local binding.
+    //
+    //      @ -> (A) -> (B) -> [C]
+    //
+    //    We list the resolving route for each node.
+    //
+    //    (A): (A) -> (B) -> [C]
+    //    (B): (B) -> [C]
+    //    [C]: [C]
+    //
+    //    In this case, if we start the tracing from (B), the resolving route becomes (B) -> [C].
+    //    So this is the same. At that time, we can say (B) is cacheable in the first tracing.
+    //
+    //  - The cache ability of a node depends on the resolving route from this node.
+    //
+    // 1. The starting point is always cacheable.
+    //
+    // 2. A module that has resolved a local binding is always cacheable.
+    //
+    //  @ -> (A) -> [B]
+    //
+    //  In the above case, we can see the [B] as cacheable.
+    //  This is because when starting from [B] node, we immediately resolve with the local binding.
+    //  So the resolving route from [B] does not depend on the starting point.
+    //
+    // 3. If we don't follow any star links during the resolution, we can see all the traced nodes are cacheable.
+    //
+    //  If there are non star links, it means that there is *no branch* in the module dependency graph.
+    //  This *no branch* feature makes all the modules cachable.
+    //
+    //  I.e, if we traverse one star link (even if we successfully resolve that star link),
+    //  we must still traverse all other star links. I would also explain we don't run into
+    //  this when resolving a local/indirect link. When resolving a local/indirect link,
+    //  we won't traverse any star links.
+    //  And since the module can hold only one local/indirect link for the specific export name (if there
+    //  are multiple local/indirect links that has the same export name, it should be syntax error in the
+    //  parsing phase.), there is no multiple outgoing links from a module.
+    //
+    //  @ -> (A) --> (B) -> [C] -> (D) -> (E) -+
+    //                ^                        |
+    //                |                        |
+    //                +------------------------+
+    //
+    //  When starting from @, [C] will be found as the module resolving the given binding.
+    //  In this case, (B) can cache this resolution. Since the resolving route is the same to the one when
+    //  starting from (B). After caching the above result, we attempt to resolve the same binding from (D).
+    //
+    //                              @
+    //                              |
+    //                              v
+    //  @ -> (A) --> (B) -> [C] -> (D) -> (E) -+
+    //                ^                        |
+    //                |                        |
+    //                +------------------------+
+    //
+    //  In this case, we can use the (B)'s cached result. And (E) can be cached.
+    //
+    //    (E): The resolving route is now (E) -> (B) -> [C]. That is the same when starting from (E).
+    //
+    //  No branching makes that the problematic *once-visited* node cannot be seen.
+    //  The *once-visited* node makes the resolving route changed since when we see the *once-visited* node,
+    //  we stop tracing this.
+    //
+    //  If there is no star links and if we look *once-visited* node under no branching graph, *once-visited*
+    //  node cannot resolve the requested binding. If the *once-visited* node can resolve the binding, we
+    //  should have already finished the resolution before reaching this *once-visited* node.
+    //
+    // 4. Once we follow star links, we should not retrieve the result from the cache and should not cache.
+    //
+    //  Star links are only the way to introduce branch.
+    //  Once we follow the star links during the resolution, we cannot cache naively.
+    //  This is because the cacheability depends on the resolving route. And branching produces the problematic *once-visited*
+    //  nodes. Since we don't follow the *once-visited* node, the resolving route from the node becomes different from
+    //  the resolving route when starting from this node.
+    //
+    //  The following example explains when we should not retrieve the cache and cache the result.
+    //
+    //               +----> (D) ------+
+    //               |                |
+    //               |                v
+    //      (A) *----+----> (B) ---> [C]
+    //                       ^
+    //                       |
+    //                       @
+    //
+    //  When starting from (B), we find [C]. In this resolving route, we don't find any star link.
+    //  And by definition, (B) and [C] are cachable. (B) is the starting point. And [C] has the local binding.
+    //
+    //               +----> (D) ------+
+    //               |                |
+    //               |                v
+    //  @-> (A) *----+----> (B) ---> [C]
+    //
+    //  But when starting from (A), we should not get the value from the cache. Because,
+    //
+    //    1. When looking (D), we reach [C] and make both resolved.
+    //    2. When looking (B), if we retrieved the last cache from (B), (B) becomes resolved.
+    //    3. But actually, (B) is not-found in this trial because (C) is already *once-visited*.
+    //    4. If we accidentally make (B) resolved, (A) becomes ambiguous. But the correct answer is resolved.
+    //
+    //  Why is this problem caused? This is because the *once-visited* node makes the result not-found.
+    //  In the second trial, (B) -> [C] result is changed from resolved to not-found.
+    //
+    //  When does this become a problem? If the status of the *once-visited* node group is resolved,
+    //  changing the result to not-found makes the result changed.
+    //
+    //  This problem does not happen when we don't see any star link yet. Now, consider the minimum case.
+    //
+    //  @-> (A) -> [ some graph ]
+    //       ^            |
+    //       |            |
+    //       +------------+
+    //
+    //  In (A), we don't see any star link yet. So we can say that all the visited nodes does not have any local
+    //  resolution. Because if they had a local/indirect resolution, we should have already finished the tracing.
+    //
+    //  And even if the some graph will see the *once-visited* node (in this case, (A)), that does not affect the
+    //  result of the resolution. Because even if we follow the link to (A) or not follow the link to (A), the status
+    //  of the link is always not-found since (A) does not have any local resolution.
+    //  In the above case, we can use the result of the [some graph].
+    //
+    // 5. Once we see star links, even if we have not yet traversed that star link path, we should disable caching.
+    //
+    //  Here is the reason why:
+    //
+    //       +-------------+
+    //       |             |
+    //       v             |
+    //      (A) -> (B) -> (C) *-> [E]
+    //       *             ^
+    //       |             |
+    //       v             @
+    //      [D]
+    //
+    //  In the above case, (C) will be resolved with [D].
+    //  (C) will see (A) and (A) gives up in (A) -> (B) -> (C) route. So, (A) will fallback to [D].
+    //
+    //       +-------------+
+    //       |             |
+    //       v             |
+    //  @-> (A) -> (B) -> (C) *-> [E]
+    //       *
+    //       |
+    //       v
+    //      [D]
+    //
+    //  But in this case, (A) will be resolved with [E] (not [D]).
+    //  (C) will attempt to follow the link to (A), but it fails.
+    //  So (C) will fallback to the star link and found [E]. In this senario,
+    //  (C) is now resolved with [E]'s result.
+    //
+    //  The cause of this problem is also the same to 4.
+    //  In the latter case, when looking (C), we cannot use the cached result in (C).
+    //  Because the cached result of (C) depends on the *once-visited* node (A) and
+    //  (A) has the fallback system with the star link.
+    //  In the latter trial, we now assume that (A)'s status is not-found.
+    //  But, actually, in the former trial, (A)'s status becomes resolved due to the fallback to the [D].
+    //
+    // To summarize the observations.
+    //
+    //  1. The starting point is always cacheable.
+    //  2. A module that has resolved a local binding is always cacheable.
+    //  3. If we don't follow any star links during the resolution, we can see all the traced nodes are cacheable.
+    //  4. Once we follow star links, we should not retrieve the result from the cache and should not cache the result.
+    //  5. Once we see star links, even if we have not yet traversed that star link path, we should disable caching.
+
+    typedef WTF::HashSet<ResolveQuery, ResolveQuery::Hash, WTF::CustomHashTraits<ResolveQuery>> ResolveSet;
     enum class Type { Query, IndirectFallback, GatherStars };
     struct Task {
         ResolveQuery query;
@@ -288,8 +480,11 @@ static JSModuleRecord::Resolution resolveExportLoop(ExecState* exec, const Resol
     Vector<Task, 8> pendingTasks;
     ResolveSet resolveSet;
     HashSet<JSModuleRecord*> starSet;
+
     Vector<Resolution, 8> frames;
 
+    bool foundStarLinks = false;
+
     frames.append(Resolution::notFound());
 
     // Call when the query is not resolved in the current module.
@@ -309,8 +504,10 @@ static JSModuleRecord::Resolution resolveExportLoop(ExecState* exec, const Resol
         // Enqueue the task to gather the results of the stars.
         // And append the new Resolution frame to gather the local result of the stars.
         pendingTasks.append(Task { query, Type::GatherStars });
+        foundStarLinks = true;
         frames.append(Resolution::notFound());
 
+
         // Enqueue the tasks in reverse order.
         for (auto iterator = query.moduleRecord->starExportEntries().rbegin(), end = query.moduleRecord->starExportEntries().rend(); iterator != end; ++iterator) {
             const RefPtr<UniquedStringImpl>& starModuleName = *iterator;
@@ -343,6 +540,11 @@ static JSModuleRecord::Resolution resolveExportLoop(ExecState* exec, const Resol
         return true;
     };
 
+    auto cacheResolutionForQuery = [] (const ResolveQuery& query, const Resolution& resolution) {
+        ASSERT(resolution.type == Resolution::Type::Resolved);
+        query.moduleRecord->cacheResolution(query.exportName.get(), resolution);
+    };
+
     pendingTasks.append(Task { root, Type::Query });
     while (!pendingTasks.isEmpty()) {
         const Task task = pendingTasks.takeLast();
@@ -350,11 +552,25 @@ static JSModuleRecord::Resolution resolveExportLoop(ExecState* exec, const Resol
 
         switch (task.type) {
         case Type::Query: {
+            JSModuleRecord* moduleRecord = query.moduleRecord;
+
             if (!resolveSet.add(task.query).isNewEntry)
                 continue;
 
-            JSModuleRecord* moduleRecord = query.moduleRecord;
-            const Optional<JSModuleRecord::ExportEntry> optionalExportEntry = moduleRecord->tryGetExportEntry(query.exportName.get());
+            //  5. Once we see star links, even if we have not yet traversed that star link path, we should disable caching.
+            if (!moduleRecord->starExportEntries().isEmpty())
+                foundStarLinks = true;
+
+            //  4. Once we follow star links, we should not retrieve the result from the cache and should not cache the result.
+            if (!foundStarLinks) {
+                if (Optional<Resolution> cachedResolution = moduleRecord->tryGetCachedResolution(query.exportName.get())) {
+                    if (!mergeToCurrentTop(*cachedResolution))
+                        return Resolution::ambiguous();
+                    continue;
+                }
+            }
+
+            const Optional<ExportEntry> optionalExportEntry = moduleRecord->tryGetExportEntry(query.exportName.get());
             if (!optionalExportEntry) {
                 // If there is no matched exported binding in the current module,
                 // we need to look into the stars.
@@ -363,15 +579,19 @@ static JSModuleRecord::Resolution resolveExportLoop(ExecState* exec, const Resol
                 continue;
             }
 
-            const JSModuleRecord::ExportEntry& exportEntry = *optionalExportEntry;
+            const ExportEntry& exportEntry = *optionalExportEntry;
             switch (exportEntry.type) {
-            case JSModuleRecord::ExportEntry::Type::Local:
-            case JSModuleRecord::ExportEntry::Type::Namespace:
-                if (!mergeToCurrentTop(Resolution { Resolution::Type::Resolved, moduleRecord, exportEntry.localName }))
+            case ExportEntry::Type::Local:
+            case ExportEntry::Type::Namespace: {
+                Resolution resolution { Resolution::Type::Resolved, moduleRecord, exportEntry.localName };
+                //  2. A module that has resolved a local binding is always cacheable.
+                cacheResolutionForQuery(query, resolution);
+                if (!mergeToCurrentTop(resolution))
                     return Resolution::ambiguous();
                 continue;
+            }
 
-            case JSModuleRecord::ExportEntry::Type::Indirect: {
+            case ExportEntry::Type::Indirect: {
                 JSModuleRecord* importedModuleRecord = moduleRecord->hostResolveImportedModule(exec, exportEntry.moduleName);
 
                 // When the imported module does not produce any resolved binding, we need to look into the stars in the *current*
@@ -387,7 +607,7 @@ static JSModuleRecord::Resolution resolveExportLoop(ExecState* exec, const Resol
         }
 
         case Type::IndirectFallback: {
-            JSModuleRecord::Resolution resolution = frames.takeLast();
+            Resolution resolution = frames.takeLast();
 
             if (resolution.type == Resolution::Type::NotFound) {
                 // Indirect export entry does not produce any resolved binding.
@@ -397,6 +617,13 @@ static JSModuleRecord::Resolution resolveExportLoop(ExecState* exec, const Resol
                 continue;
             }
 
+            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.");
+
+            //  3. If we don't follow any star links during the resolution, we can see all the traced nodes are cacheable.
+            //  4. Once we follow star links, we should not retrieve the result from the cache and should not cache the result.
+            if (!foundStarLinks)
+                cacheResolutionForQuery(query, resolution);
+
             // If indirect export entry produces Resolved, we should merge it to the upper frame.
             // And do not investigate the stars of the current module.
             if (!mergeToCurrentTop(resolution))
@@ -405,9 +632,11 @@ static JSModuleRecord::Resolution resolveExportLoop(ExecState* exec, const Resol
         }
 
         case Type::GatherStars: {
+            Resolution resolution = frames.takeLast();
+            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.");
+
             // Merge the star resolution to the upper frame.
-            JSModuleRecord::Resolution starResolution = frames.takeLast();
-            if (!mergeToCurrentTop(starResolution))
+            if (!mergeToCurrentTop(resolution))
                 return Resolution::ambiguous();
             break;
         }
@@ -415,12 +644,18 @@ static JSModuleRecord::Resolution resolveExportLoop(ExecState* exec, const Resol
     }
 
     ASSERT(frames.size() == 1);
+    //  1. The starting point is always cacheable.
+    if (frames[0].type == Resolution::Type::Resolved)
+        cacheResolutionForQuery(root, frames[0]);
     return frames[0];
 }
 
 auto JSModuleRecord::resolveExport(ExecState* exec, const Identifier& exportName) -> Resolution
 {
-    return resolveExportLoop(exec, ResolveQuery(this, exportName.impl()));
+    // Look up the cached resolution first before entering the resolving loop, since the loop setup takes some cost.
+    if (Optional<Resolution> cachedResolution = tryGetCachedResolution(exportName.impl()))
+        return *cachedResolution;
+    return resolveExportImpl(exec, ResolveQuery(this, exportName.impl()));
 }
 
 static void getExportedNames(ExecState* exec, JSModuleRecord* root, IdentifierSet& exportedNames)
index 70a190f..30de7f5 100644 (file)
@@ -163,6 +163,11 @@ private:
 
     void instantiateDeclarations(ExecState*, ModuleProgramExecutable*);
 
+    struct ResolveQuery;
+    static Resolution resolveExportImpl(ExecState*, const ResolveQuery&);
+    Optional<Resolution> tryGetCachedResolution(UniquedStringImpl* exportName);
+    void cacheResolution(UniquedStringImpl* exportName, const Resolution&);
+
     // The loader resolves the given module name to the module key. The module key is the unique value to represent this module.
     Identifier m_moduleKey;
 
@@ -181,7 +186,7 @@ private:
     //
     //      In the above case, (2) may throw the error earlier than (1)
     //
-    // But, in the all cases, we will throw the syntax error. So except for the content of the syntax error,
+    // But, in all the cases, we will throw the syntax error. So except for the content of the syntax error,
     // there are no difference.
 
     // Map localName -> ImportEntry.
@@ -202,6 +207,13 @@ private:
     WriteBarrier<ModuleProgramExecutable> m_moduleProgramExecutable;
     WriteBarrier<JSModuleEnvironment> m_moduleEnvironment;
     WriteBarrier<JSModuleNamespaceObject> m_moduleNamespaceObject;
+
+    // We assume that all the JSModuleRecord are retained by ModuleLoaderObject's registry.
+    // So here, we don't visit each object for GC. The resolution cache map caches the once
+    // looked up correctly resolved resolution, since (1) we rarely looked up the non-resolved one,
+    // and (2) if we cache all the attempts the size of the map becomes infinitely large.
+    typedef HashMap<RefPtr<UniquedStringImpl>, Resolution, IdentifierRepHash, HashTraits<RefPtr<UniquedStringImpl>>> Resolutions;
+    Resolutions m_resolutionCache;
 };
 
 } // namespace JSC
diff --git a/Source/JavaScriptCore/tests/modules/caching-should-not-make-ambiguous.js b/Source/JavaScriptCore/tests/modules/caching-should-not-make-ambiguous.js
new file mode 100644 (file)
index 0000000..42513ed
--- /dev/null
@@ -0,0 +1,5 @@
+//                +----> (D) ------+
+//                |                |
+//                |                v
+//   @-> (A) *----+----> (B) ---> [C]
+import { A } from "caching-should-not-make-ambiguous/main.js"
diff --git a/Source/JavaScriptCore/tests/modules/caching-should-not-make-ambiguous/A.js b/Source/JavaScriptCore/tests/modules/caching-should-not-make-ambiguous/A.js
new file mode 100644 (file)
index 0000000..a366e37
--- /dev/null
@@ -0,0 +1,2 @@
+export * from "./D.js"
+export * from "./B.js"
diff --git a/Source/JavaScriptCore/tests/modules/caching-should-not-make-ambiguous/B.js b/Source/JavaScriptCore/tests/modules/caching-should-not-make-ambiguous/B.js
new file mode 100644 (file)
index 0000000..672bccf
--- /dev/null
@@ -0,0 +1 @@
+export { A } from "./C.js"
diff --git a/Source/JavaScriptCore/tests/modules/caching-should-not-make-ambiguous/C.js b/Source/JavaScriptCore/tests/modules/caching-should-not-make-ambiguous/C.js
new file mode 100644 (file)
index 0000000..d308e2c
--- /dev/null
@@ -0,0 +1 @@
+export let A = 42;
diff --git a/Source/JavaScriptCore/tests/modules/caching-should-not-make-ambiguous/D.js b/Source/JavaScriptCore/tests/modules/caching-should-not-make-ambiguous/D.js
new file mode 100644 (file)
index 0000000..672bccf
--- /dev/null
@@ -0,0 +1 @@
+export { A } from "./C.js"
diff --git a/Source/JavaScriptCore/tests/modules/caching-should-not-make-ambiguous/main.js b/Source/JavaScriptCore/tests/modules/caching-should-not-make-ambiguous/main.js
new file mode 100644 (file)
index 0000000..e90b535
--- /dev/null
@@ -0,0 +1 @@
+export { A } from "./A.js"
diff --git a/Source/JavaScriptCore/tests/modules/different-view.js b/Source/JavaScriptCore/tests/modules/different-view.js
new file mode 100644 (file)
index 0000000..f81e89c
--- /dev/null
@@ -0,0 +1,7 @@
+import { shouldBe, shouldThrow } from "./resources/assert.js"
+
+shouldThrow(() => {
+    loadModule('./different-view/main.js');
+}, `SyntaxError: Importing binding name 'A' cannot be resolved due to ambiguous multiple bindings.`);
+
+
diff --git a/Source/JavaScriptCore/tests/modules/different-view/A.js b/Source/JavaScriptCore/tests/modules/different-view/A.js
new file mode 100644 (file)
index 0000000..3fdbb60
--- /dev/null
@@ -0,0 +1,2 @@
+export * from "./B.js";
+export * from "./E.js";
diff --git a/Source/JavaScriptCore/tests/modules/different-view/B.js b/Source/JavaScriptCore/tests/modules/different-view/B.js
new file mode 100644 (file)
index 0000000..386dd71
--- /dev/null
@@ -0,0 +1,2 @@
+export * from "./C.js"
+export * from "./D.js"
diff --git a/Source/JavaScriptCore/tests/modules/different-view/C.js b/Source/JavaScriptCore/tests/modules/different-view/C.js
new file mode 100644 (file)
index 0000000..ce80935
--- /dev/null
@@ -0,0 +1 @@
+export * from "./A.js"
diff --git a/Source/JavaScriptCore/tests/modules/different-view/D.js b/Source/JavaScriptCore/tests/modules/different-view/D.js
new file mode 100644 (file)
index 0000000..d308e2c
--- /dev/null
@@ -0,0 +1 @@
+export let A = 42;
diff --git a/Source/JavaScriptCore/tests/modules/different-view/E.js b/Source/JavaScriptCore/tests/modules/different-view/E.js
new file mode 100644 (file)
index 0000000..210cb0e
--- /dev/null
@@ -0,0 +1 @@
+export let A = 50;
diff --git a/Source/JavaScriptCore/tests/modules/different-view/main.js b/Source/JavaScriptCore/tests/modules/different-view/main.js
new file mode 100644 (file)
index 0000000..c24f972
--- /dev/null
@@ -0,0 +1 @@
+import { A } from "./A.js"
diff --git a/Source/JavaScriptCore/tests/modules/fallback-ambiguous.js b/Source/JavaScriptCore/tests/modules/fallback-ambiguous.js
new file mode 100644 (file)
index 0000000..36b60fe
--- /dev/null
@@ -0,0 +1,12 @@
+//        +-----------------+
+//        |                 |
+//        v                 |
+//       (A) -> (C) -> (D) *+-> [E]
+//        *      ^
+//        |      |
+//        v      @
+//       (B)
+import { shouldThrow } from "./resources/assert.js"
+shouldThrow(() => {
+    loadModule("./fallback-ambiguous/main.js");
+}, `SyntaxError: Indirectly exported binding name 'A' cannot be resolved due to ambiguous multiple bindings.`);
diff --git a/Source/JavaScriptCore/tests/modules/fallback-ambiguous/A.js b/Source/JavaScriptCore/tests/modules/fallback-ambiguous/A.js
new file mode 100644 (file)
index 0000000..1ca4822
--- /dev/null
@@ -0,0 +1,2 @@
+export { A } from "./C.js"
+export * from "./B.js"
diff --git a/Source/JavaScriptCore/tests/modules/fallback-ambiguous/B.js b/Source/JavaScriptCore/tests/modules/fallback-ambiguous/B.js
new file mode 100644 (file)
index 0000000..210cb0e
--- /dev/null
@@ -0,0 +1 @@
+export let A = 50;
diff --git a/Source/JavaScriptCore/tests/modules/fallback-ambiguous/C.js b/Source/JavaScriptCore/tests/modules/fallback-ambiguous/C.js
new file mode 100644 (file)
index 0000000..6af0588
--- /dev/null
@@ -0,0 +1 @@
+export { A } from "./D.js"
diff --git a/Source/JavaScriptCore/tests/modules/fallback-ambiguous/D.js b/Source/JavaScriptCore/tests/modules/fallback-ambiguous/D.js
new file mode 100644 (file)
index 0000000..c251632
--- /dev/null
@@ -0,0 +1,2 @@
+export * from "./A.js"
+export * from "./E.js"
diff --git a/Source/JavaScriptCore/tests/modules/fallback-ambiguous/E.js b/Source/JavaScriptCore/tests/modules/fallback-ambiguous/E.js
new file mode 100644 (file)
index 0000000..d308e2c
--- /dev/null
@@ -0,0 +1 @@
+export let A = 42;
diff --git a/Source/JavaScriptCore/tests/modules/fallback-ambiguous/main.js b/Source/JavaScriptCore/tests/modules/fallback-ambiguous/main.js
new file mode 100644 (file)
index 0000000..672bccf
--- /dev/null
@@ -0,0 +1 @@
+export { A } from "./C.js"
diff --git a/Source/JavaScriptCore/tests/modules/self-star-link.js b/Source/JavaScriptCore/tests/modules/self-star-link.js
new file mode 100644 (file)
index 0000000..d5e3376
--- /dev/null
@@ -0,0 +1,15 @@
+//       +-------------+
+//       |             |
+//       v             |
+//  @-> (A) -> (B) -> (C) *-> [E]
+//       *
+//       |
+//       v
+//      [D]
+import { A } from "./self-star-link/A.js"
+import { shouldBe } from "./resources/assert.js"
+import { A as AfromC } from "./self-star-link/C.js"
+import { A as AfromB } from "./self-star-link/B.js"
+shouldBe(A, 'E');
+shouldBe(AfromC, 'D');
+shouldBe(AfromB, 'D');
diff --git a/Source/JavaScriptCore/tests/modules/self-star-link/A.js b/Source/JavaScriptCore/tests/modules/self-star-link/A.js
new file mode 100644 (file)
index 0000000..a79e928
--- /dev/null
@@ -0,0 +1,2 @@
+export { A } from "./B.js"
+export * from "./D.js"
diff --git a/Source/JavaScriptCore/tests/modules/self-star-link/B.js b/Source/JavaScriptCore/tests/modules/self-star-link/B.js
new file mode 100644 (file)
index 0000000..672bccf
--- /dev/null
@@ -0,0 +1 @@
+export { A } from "./C.js"
diff --git a/Source/JavaScriptCore/tests/modules/self-star-link/C.js b/Source/JavaScriptCore/tests/modules/self-star-link/C.js
new file mode 100644 (file)
index 0000000..6cc6194
--- /dev/null
@@ -0,0 +1,2 @@
+export { A } from "./A.js"
+export * from "./E.js"
diff --git a/Source/JavaScriptCore/tests/modules/self-star-link/D.js b/Source/JavaScriptCore/tests/modules/self-star-link/D.js
new file mode 100644 (file)
index 0000000..5c938f5
--- /dev/null
@@ -0,0 +1 @@
+export let A = 'D';
diff --git a/Source/JavaScriptCore/tests/modules/self-star-link/E.js b/Source/JavaScriptCore/tests/modules/self-star-link/E.js
new file mode 100644 (file)
index 0000000..4315381
--- /dev/null
@@ -0,0 +1 @@
+export let A = 'E';
diff --git a/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star.js b/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star.js
new file mode 100644 (file)
index 0000000..4192b51
--- /dev/null
@@ -0,0 +1,13 @@
+//       (A) *--> [B]
+//            |    ^
+//            |    |
+//            +-> (C) *-> (D)
+//                 ^
+//                 |
+//                (E)
+//                 ^
+//                 |
+//                 @
+
+import "uncacheable-when-see-star/main1.js"
+import "uncacheable-when-see-star/main2.js"
diff --git a/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/A-pre.js b/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/A-pre.js
new file mode 100644 (file)
index 0000000..e90b535
--- /dev/null
@@ -0,0 +1 @@
+export { A } from "./A.js"
diff --git a/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/A.js b/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/A.js
new file mode 100644 (file)
index 0000000..6124764
--- /dev/null
@@ -0,0 +1,2 @@
+export * from "./B.js"
+export * from "./C.js"
diff --git a/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/B.js b/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/B.js
new file mode 100644 (file)
index 0000000..5dc929f
--- /dev/null
@@ -0,0 +1 @@
+export let A = 40;
diff --git a/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/C.js b/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/C.js
new file mode 100644 (file)
index 0000000..a79e928
--- /dev/null
@@ -0,0 +1,2 @@
+export { A } from "./B.js"
+export * from "./D.js"
diff --git a/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/D.js b/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/D.js
new file mode 100644 (file)
index 0000000..8b13789
--- /dev/null
@@ -0,0 +1 @@
+
diff --git a/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/E-pre.js b/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/E-pre.js
new file mode 100644 (file)
index 0000000..7d3aa04
--- /dev/null
@@ -0,0 +1 @@
+export { A } from "./E.js"
diff --git a/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/E.js b/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/E.js
new file mode 100644 (file)
index 0000000..672bccf
--- /dev/null
@@ -0,0 +1 @@
+export { A } from "./C.js"
diff --git a/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/main1.js b/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/main1.js
new file mode 100644 (file)
index 0000000..f2373b9
--- /dev/null
@@ -0,0 +1 @@
+import { A } from "./E-pre.js"
diff --git a/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/main2.js b/Source/JavaScriptCore/tests/modules/uncacheable-when-see-star/main2.js
new file mode 100644 (file)
index 0000000..597376a
--- /dev/null
@@ -0,0 +1 @@
+import { A } from "./A-pre.js"