[modules] Detect and throw exceptions for cyclic dependencies

src/objects.cc

 // Copyright 2015 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/objects.h"
 
 #include <cmath>
 #include <iomanip>
 #include <memory>
 #include <sstream>
+#include <unordered_map>
+#include <unordered_set>
 
 #include "src/objects-inl.h"
 
 #include "src/accessors.h"
 #include "src/allocation-site-scopes.h"
 #include "src/api-arguments-inl.h"
 #include "src/api-natives.h"
 #include "src/api.h"
 #include "src/base/bits.h"
 #include "src/base/utils/random-number-generator.h"
@@ skipping 19552 matching lines @@
 
 bool JSReceiver::HasProxyInPrototype(Isolate* isolate) {
   for (PrototypeIterator iter(isolate, this, kStartAtReceiver,
                               PrototypeIterator::END_AT_NULL);
        !iter.IsAtEnd(); iter.AdvanceIgnoringProxies()) {
     if (iter.GetCurrent<Object>()->IsJSProxy()) return true;
   }
   return false;
 }
 
+namespace {
+
+template <typename T>
+struct HandleValueHash {
+  V8_INLINE size_t operator()(Handle<T> handle) const { return handle->Hash(); }
+};
+
+struct ModuleHandleEqual {
+  V8_INLINE bool operator()(Handle<Module> lhs, Handle<Module> rhs) const {
+    return *lhs == *rhs;
+  }
+};
+
+struct StringHandleEqual {
+  V8_INLINE bool operator()(Handle<String> lhs, Handle<String> rhs) const {
+    return lhs->Equals(*rhs);
+  }
+};
+
+class UnorderedStringSet
+    : public std::unordered_set<Handle<String>, HandleValueHash<String>,
+                                StringHandleEqual,
+                                zone_allocator<Handle<String>>> {
+ public:
+  explicit UnorderedStringSet(Zone* zone)
+      : std::unordered_set<Handle<String>, HandleValueHash<String>,
+                           StringHandleEqual, zone_allocator<Handle<String>>>(
+            2 /* bucket count */, HandleValueHash<String>(),
+            StringHandleEqual(), zone_allocator<Handle<String>>(zone)) {}
+};
+
+}  // anonymous namespace
+
+class Module::ResolveSet
+    : public std::unordered_map<
+          Handle<Module>, UnorderedStringSet*, HandleValueHash<Module>,
+          ModuleHandleEqual, zone_allocator<std::pair<const Handle<Module>,
+                                                      UnorderedStringSet*>>> {
+ public:
+  explicit ResolveSet(Zone* zone)
+      : std::unordered_map<Handle<Module>, UnorderedStringSet*,
+                           HandleValueHash<Module>, ModuleHandleEqual,
+                           zone_allocator<std::pair<const Handle<Module>,
+                                                    UnorderedStringSet*>>>(
+            2 /* bucket count */, HandleValueHash<Module>(),
+            ModuleHandleEqual(),
+            zone_allocator<
+                std::pair<const Handle<Module>, UnorderedStringSet*>>(zone)),
+        zone_(zone) {}
+
+  Zone* zone() const { return zone_; }
+
+ private:
+  Zone* zone_;
+};
+
 void Module::CreateIndirectExport(Handle<Module> module, Handle<String> name,
                                   Handle<ModuleInfoEntry> entry) {
   Isolate* isolate = module->GetIsolate();
   Handle<ObjectHashTable> exports(module->exports(), isolate);
   DCHECK(exports->Lookup(name)->IsTheHole(isolate));
   exports = ObjectHashTable::Put(exports, name, entry);
   module->set_exports(*exports);
 }
 
 void Module::CreateExport(Handle<Module> module, Handle<FixedArray> names) {
@@ skipping 30 matching lines @@
 Handle<Object> Module::LoadImport(Handle<Module> module, Handle<String> name,
                                   int module_request) {
   Isolate* isolate = module->GetIsolate();
   Handle<Module> requested_module(
       Module::cast(module->requested_modules()->get(module_request)), isolate);
   return Module::LoadExport(requested_module, name);
 }
 
 MaybeHandle<Cell> Module::ResolveImport(Handle<Module> module,
                                         Handle<String> name, int module_request,
-                                        bool must_resolve) {
+                                        bool must_resolve,
+                                        Module::ResolveSet* resolve_set) {
   Isolate* isolate = module->GetIsolate();
   Handle<Module> requested_module(
       Module::cast(module->requested_modules()->get(module_request)), isolate);
-  return Module::ResolveExport(requested_module, name, must_resolve);
+  return Module::ResolveExport(requested_module, name, must_resolve,
+                               resolve_set);
 }
 
 MaybeHandle<Cell> Module::ResolveExport(Handle<Module> module,
-                                        Handle<String> name,
-                                        bool must_resolve) {
-  // TODO(neis): Detect cycles.
-
+                                        Handle<String> name, bool must_resolve,
+                                        Module::ResolveSet* resolve_set) {
   Isolate* isolate = module->GetIsolate();
   Handle<Object> object(module->exports()->Lookup(name), isolate);
-
   if (object->IsCell()) {
     // Already resolved (e.g. because it's a local export).
     return Handle<Cell>::cast(object);
   }
 
+  // Must be an indirect export of some sort, so we need to detect cycles.
+  {
+    // Attempt insertion with a null string set.
+    auto result = resolve_set->insert({module, nullptr});
+    UnorderedStringSet*& name_set = result.first->second;
+    bool did_insert = result.second;
+    if (did_insert) {
+      // |module| wasn't in the map previously, so allocate a new name set.
+      Zone* zone = resolve_set->zone();
+      name_set =
+          new (zone->New(sizeof(UnorderedStringSet))) UnorderedStringSet(zone);
+    } else if (name_set->count(name)) {
+      // TODO(adamk): Throwing here is incorrect in the case of star exports.
+      THROW_NEW_ERROR(
+          isolate,
+          NewSyntaxError(MessageTemplate::kCyclicModuleDependency, name), Cell);
+    }
+    name_set->insert(name);
+  }
+
   if (object->IsModuleInfoEntry()) {
     // Not yet resolved indirect export.
     Handle<ModuleInfoEntry> entry = Handle<ModuleInfoEntry>::cast(object);
     int module_request = Smi::cast(entry->module_request())->value();
     Handle<String> import_name(String::cast(entry->import_name()), isolate);
 
     Handle<Cell> cell;
-    if (!ResolveImport(module, import_name, module_request, true)
+    if (!ResolveImport(module, import_name, module_request, true, resolve_set)
              .ToHandle(&cell)) {
       DCHECK(isolate->has_pending_exception());
       return MaybeHandle<Cell>();
     }
 
     // The export table may have changed but the entry in question should be
     // unchanged.
     Handle<ObjectHashTable> exports(module->exports(), isolate);
     DCHECK(exports->Lookup(name)->IsModuleInfoEntry());
 
     exports = ObjectHashTable::Put(exports, name, cell);
     module->set_exports(*exports);
     return cell;
   }
 
   DCHECK(object->IsTheHole(isolate));
-  return Module::ResolveExportUsingStarExports(module, name, must_resolve);
+  return Module::ResolveExportUsingStarExports(module, name, must_resolve,
+                                               resolve_set);
 }
 
-MaybeHandle<Cell> Module::ResolveExportUsingStarExports(Handle<Module> module,
-                                                        Handle<String> name,
-                                                        bool must_resolve) {
+MaybeHandle<Cell> Module::ResolveExportUsingStarExports(
+    Handle<Module> module, Handle<String> name, bool must_resolve,
+    Module::ResolveSet* resolve_set) {
   Isolate* isolate = module->GetIsolate();
   if (!name->Equals(isolate->heap()->default_string())) {
     // Go through all star exports looking for the given name.  If multiple star
     // exports provide the name, make sure they all map it to the same cell.
     Handle<Cell> unique_cell;
     Handle<FixedArray> special_exports(module->info()->special_exports(),
                                        isolate);
     for (int i = 0, n = special_exports->length(); i < n; ++i) {
       i::Handle<i::ModuleInfoEntry> entry(
           i::ModuleInfoEntry::cast(special_exports->get(i)), isolate);
       if (!entry->export_name()->IsUndefined(isolate)) {
         continue;  // Indirect export.
       }
       int module_request = Smi::cast(entry->module_request())->value();
 
       Handle<Cell> cell;
-      if (ResolveImport(module, name, module_request, false).ToHandle(&cell)) {
+      if (ResolveImport(module, name, module_request, false, resolve_set)
+              .ToHandle(&cell)) {
         if (unique_cell.is_null()) unique_cell = cell;
         if (*unique_cell != *cell) {
           THROW_NEW_ERROR(
               isolate, NewSyntaxError(MessageTemplate::kAmbiguousExport, name),
               Cell);
         }
       } else if (isolate->has_pending_exception()) {
         return MaybeHandle<Cell>();
       }
     }
@@ skipping 72 matching lines @@
       isolate->ThrowIllegalOperation();
       return false;
     }
     Handle<Module> requested_module = Utils::OpenHandle(*api_requested_module);
     module->requested_modules()->set(i, *requested_module);
     if (!Instantiate(requested_module, context, callback, callback_data)) {
       return false;
     }
   }
 
+  Zone zone(isolate->allocator());
+
   // Resolve imports.
   Handle<FixedArray> regular_imports(module_info->regular_imports(), isolate);
   for (int i = 0, n = regular_imports->length(); i < n; ++i) {
     Handle<ModuleInfoEntry> entry(
         ModuleInfoEntry::cast(regular_imports->get(i)), isolate);
     Handle<String> name(String::cast(entry->import_name()), isolate);
     int module_request = Smi::cast(entry->module_request())->value();
-    if (ResolveImport(module, name, module_request, true).is_null()) {
+    ResolveSet resolve_set(&zone);
+    if (ResolveImport(module, name, module_request, true, &resolve_set)
+            .is_null()) {
       return false;
     }
   }
 
   // Resolve indirect exports.
   for (int i = 0, n = special_exports->length(); i < n; ++i) {
     Handle<ModuleInfoEntry> entry(
         ModuleInfoEntry::cast(special_exports->get(i)), isolate);
     Handle<Object> name(entry->export_name(), isolate);
     if (name->IsUndefined(isolate)) continue;  // Star export.
-    if (ResolveExport(module, Handle<String>::cast(name), true).is_null()) {
+    ResolveSet resolve_set(&zone);
+    if (ResolveExport(module, Handle<String>::cast(name), true, &resolve_set)
+            .is_null()) {
       return false;
     }
   }
 
   return true;
 }
 
 }  // namespace internal
 }  // namespace v8