Home | History | Annotate | Download | only in objects 
      1 // Copyright 2017 the V8 project authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include <unordered_map>
      6 #include <unordered_set>
      7 
      8 #include "src/objects/module.h"
      9 
     10 #include "src/accessors.h"
     11 #include "src/api-inl.h"
     12 #include "src/ast/modules.h"
     13 #include "src/objects-inl.h"
     14 #include "src/objects/hash-table-inl.h"
     15 #include "src/objects/js-generator-inl.h"
     16 #include "src/objects/module-inl.h"
     17 
     18 namespace v8 {
     19 namespace internal {
     20 
     21 namespace {
     22 
     23 struct ModuleHandleHash {
     24   V8_INLINE size_t operator()(Handle<Module> module) const {
     25     return module->hash();
     26   }
     27 };
     28 
     29 struct ModuleHandleEqual {
     30   V8_INLINE bool operator()(Handle<Module> lhs, Handle<Module> rhs) const {
     31     return *lhs == *rhs;
     32   }
     33 };
     34 
     35 struct StringHandleHash {
     36   V8_INLINE size_t operator()(Handle<String> string) const {
     37     return string->Hash();
     38   }
     39 };
     40 
     41 struct StringHandleEqual {
     42   V8_INLINE bool operator()(Handle<String> lhs, Handle<String> rhs) const {
     43     return lhs->Equals(*rhs);
     44   }
     45 };
     46 
     47 class UnorderedStringSet
     48     : public std::unordered_set<Handle<String>, StringHandleHash,
     49                                 StringHandleEqual,
     50                                 ZoneAllocator<Handle<String>>> {
     51  public:
     52   explicit UnorderedStringSet(Zone* zone)
     53       : std::unordered_set<Handle<String>, StringHandleHash, StringHandleEqual,
     54                            ZoneAllocator<Handle<String>>>(
     55             2 /* bucket count */, StringHandleHash(), StringHandleEqual(),
     56             ZoneAllocator<Handle<String>>(zone)) {}
     57 };
     58 
     59 class UnorderedModuleSet
     60     : public std::unordered_set<Handle<Module>, ModuleHandleHash,
     61                                 ModuleHandleEqual,
     62                                 ZoneAllocator<Handle<Module>>> {
     63  public:
     64   explicit UnorderedModuleSet(Zone* zone)
     65       : std::unordered_set<Handle<Module>, ModuleHandleHash, ModuleHandleEqual,
     66                            ZoneAllocator<Handle<Module>>>(
     67             2 /* bucket count */, ModuleHandleHash(), ModuleHandleEqual(),
     68             ZoneAllocator<Handle<Module>>(zone)) {}
     69 };
     70 
     71 class UnorderedStringMap
     72     : public std::unordered_map<
     73           Handle<String>, Handle<Object>, StringHandleHash, StringHandleEqual,
     74           ZoneAllocator<std::pair<const Handle<String>, Handle<Object>>>> {
     75  public:
     76   explicit UnorderedStringMap(Zone* zone)
     77       : std::unordered_map<
     78             Handle<String>, Handle<Object>, StringHandleHash, StringHandleEqual,
     79             ZoneAllocator<std::pair<const Handle<String>, Handle<Object>>>>(
     80             2 /* bucket count */, StringHandleHash(), StringHandleEqual(),
     81             ZoneAllocator<std::pair<const Handle<String>, Handle<Object>>>(
     82                 zone)) {}
     83 };
     84 
     85 }  // anonymous namespace
     86 
     87 class Module::ResolveSet
     88     : public std::unordered_map<
     89           Handle<Module>, UnorderedStringSet*, ModuleHandleHash,
     90           ModuleHandleEqual,
     91           ZoneAllocator<std::pair<const Handle<Module>, UnorderedStringSet*>>> {
     92  public:
     93   explicit ResolveSet(Zone* zone)
     94       : std::unordered_map<Handle<Module>, UnorderedStringSet*,
     95                            ModuleHandleHash, ModuleHandleEqual,
     96                            ZoneAllocator<std::pair<const Handle<Module>,
     97                                                    UnorderedStringSet*>>>(
     98             2 /* bucket count */, ModuleHandleHash(), ModuleHandleEqual(),
     99             ZoneAllocator<std::pair<const Handle<Module>, UnorderedStringSet*>>(
    100                 zone)),
    101         zone_(zone) {}
    102 
    103   Zone* zone() const { return zone_; }
    104 
    105  private:
    106   Zone* zone_;
    107 };
    108 
    109 namespace {
    110 
    111 int ExportIndex(int cell_index) {
    112   DCHECK_EQ(ModuleDescriptor::GetCellIndexKind(cell_index),
    113             ModuleDescriptor::kExport);
    114   return cell_index - 1;
    115 }
    116 
    117 int ImportIndex(int cell_index) {
    118   DCHECK_EQ(ModuleDescriptor::GetCellIndexKind(cell_index),
    119             ModuleDescriptor::kImport);
    120   return -cell_index - 1;
    121 }
    122 
    123 }  // anonymous namespace
    124 
    125 void Module::CreateIndirectExport(Isolate* isolate, Handle<Module> module,
    126                                   Handle<String> name,
    127                                   Handle<ModuleInfoEntry> entry) {
    128   Handle<ObjectHashTable> exports(module->exports(), isolate);
    129   DCHECK(exports->Lookup(name)->IsTheHole(isolate));
    130   exports = ObjectHashTable::Put(exports, name, entry);
    131   module->set_exports(*exports);
    132 }
    133 
    134 void Module::CreateExport(Isolate* isolate, Handle<Module> module,
    135                           int cell_index, Handle<FixedArray> names) {
    136   DCHECK_LT(0, names->length());
    137   Handle<Cell> cell =
    138       isolate->factory()->NewCell(isolate->factory()->undefined_value());
    139   module->regular_exports()->set(ExportIndex(cell_index), *cell);
    140 
    141   Handle<ObjectHashTable> exports(module->exports(), isolate);
    142   for (int i = 0, n = names->length(); i < n; ++i) {
    143     Handle<String> name(String::cast(names->get(i)), isolate);
    144     DCHECK(exports->Lookup(name)->IsTheHole(isolate));
    145     exports = ObjectHashTable::Put(exports, name, cell);
    146   }
    147   module->set_exports(*exports);
    148 }
    149 
    150 Cell* Module::GetCell(int cell_index) {
    151   DisallowHeapAllocation no_gc;
    152   Object* cell;
    153   switch (ModuleDescriptor::GetCellIndexKind(cell_index)) {
    154     case ModuleDescriptor::kImport:
    155       cell = regular_imports()->get(ImportIndex(cell_index));
    156       break;
    157     case ModuleDescriptor::kExport:
    158       cell = regular_exports()->get(ExportIndex(cell_index));
    159       break;
    160     case ModuleDescriptor::kInvalid:
    161       UNREACHABLE();
    162       break;
    163   }
    164   return Cell::cast(cell);
    165 }
    166 
    167 Handle<Object> Module::LoadVariable(Isolate* isolate, Handle<Module> module,
    168                                     int cell_index) {
    169   return handle(module->GetCell(cell_index)->value(), isolate);
    170 }
    171 
    172 void Module::StoreVariable(Handle<Module> module, int cell_index,
    173                            Handle<Object> value) {
    174   DCHECK_EQ(ModuleDescriptor::GetCellIndexKind(cell_index),
    175             ModuleDescriptor::kExport);
    176   module->GetCell(cell_index)->set_value(*value);
    177 }
    178 
    179 #ifdef DEBUG
    180 void Module::PrintStatusTransition(Status new_status) {
    181   if (FLAG_trace_module_status) {
    182     StdoutStream os;
    183     os << "Changing module status from " << status() << " to " << new_status
    184        << " for ";
    185     script()->GetNameOrSourceURL()->Print(os);
    186 #ifndef OBJECT_PRINT
    187     os << "\n";
    188 #endif  // OBJECT_PRINT
    189   }
    190 }
    191 #endif  // DEBUG
    192 
    193 void Module::SetStatus(Status new_status) {
    194   DisallowHeapAllocation no_alloc;
    195   DCHECK_LE(status(), new_status);
    196   DCHECK_NE(new_status, Module::kErrored);
    197 #ifdef DEBUG
    198   PrintStatusTransition(new_status);
    199 #endif  // DEBUG
    200   set_status(new_status);
    201 }
    202 
    203 void Module::ResetGraph(Isolate* isolate, Handle<Module> module) {
    204   DCHECK_NE(module->status(), kInstantiating);
    205   DCHECK_NE(module->status(), kEvaluating);
    206   if (module->status() != kPreInstantiating) return;
    207   Handle<FixedArray> requested_modules(module->requested_modules(), isolate);
    208   Reset(isolate, module);
    209   for (int i = 0; i < requested_modules->length(); ++i) {
    210     Handle<Object> descendant(requested_modules->get(i), isolate);
    211     if (descendant->IsModule()) {
    212       ResetGraph(isolate, Handle<Module>::cast(descendant));
    213     } else {
    214       DCHECK(descendant->IsUndefined(isolate));
    215     }
    216   }
    217 }
    218 
    219 void Module::Reset(Isolate* isolate, Handle<Module> module) {
    220   Factory* factory = isolate->factory();
    221 
    222   DCHECK(module->status() == kPreInstantiating ||
    223          module->status() == kInstantiating);
    224   DCHECK(module->exception()->IsTheHole(isolate));
    225   DCHECK(module->import_meta()->IsTheHole(isolate));
    226   // The namespace object cannot exist, because it would have been created
    227   // by RunInitializationCode, which is called only after this module's SCC
    228   // succeeds instantiation.
    229   DCHECK(!module->module_namespace()->IsJSModuleNamespace());
    230 
    231   Handle<ObjectHashTable> exports =
    232       ObjectHashTable::New(isolate, module->info()->RegularExportCount());
    233   Handle<FixedArray> regular_exports =
    234       factory->NewFixedArray(module->regular_exports()->length());
    235   Handle<FixedArray> regular_imports =
    236       factory->NewFixedArray(module->regular_imports()->length());
    237   Handle<FixedArray> requested_modules =
    238       factory->NewFixedArray(module->requested_modules()->length());
    239 
    240   if (module->status() == kInstantiating) {
    241     module->set_code(JSFunction::cast(module->code())->shared());
    242   }
    243 #ifdef DEBUG
    244   module->PrintStatusTransition(kUninstantiated);
    245 #endif  // DEBUG
    246   module->set_status(kUninstantiated);
    247   module->set_exports(*exports);
    248   module->set_regular_exports(*regular_exports);
    249   module->set_regular_imports(*regular_imports);
    250   module->set_requested_modules(*requested_modules);
    251   module->set_dfs_index(-1);
    252   module->set_dfs_ancestor_index(-1);
    253 }
    254 
    255 void Module::RecordError(Isolate* isolate) {
    256   DisallowHeapAllocation no_alloc;
    257   DCHECK(exception()->IsTheHole(isolate));
    258   Object* the_exception = isolate->pending_exception();
    259   DCHECK(!the_exception->IsTheHole(isolate));
    260 
    261   set_code(info());
    262 #ifdef DEBUG
    263   PrintStatusTransition(Module::kErrored);
    264 #endif  // DEBUG
    265   set_status(Module::kErrored);
    266   set_exception(the_exception);
    267 }
    268 
    269 Object* Module::GetException() {
    270   DisallowHeapAllocation no_alloc;
    271   DCHECK_EQ(status(), Module::kErrored);
    272   DCHECK(!exception()->IsTheHole());
    273   return exception();
    274 }
    275 
    276 SharedFunctionInfo* Module::GetSharedFunctionInfo() const {
    277   DisallowHeapAllocation no_alloc;
    278   DCHECK_NE(status(), Module::kEvaluating);
    279   DCHECK_NE(status(), Module::kEvaluated);
    280   switch (status()) {
    281     case kUninstantiated:
    282     case kPreInstantiating:
    283       DCHECK(code()->IsSharedFunctionInfo());
    284       return SharedFunctionInfo::cast(code());
    285     case kInstantiating:
    286       DCHECK(code()->IsJSFunction());
    287       return JSFunction::cast(code())->shared();
    288     case kInstantiated:
    289       DCHECK(code()->IsJSGeneratorObject());
    290       return JSGeneratorObject::cast(code())->function()->shared();
    291     case kEvaluating:
    292     case kEvaluated:
    293     case kErrored:
    294       UNREACHABLE();
    295   }
    296 
    297   UNREACHABLE();
    298 }
    299 
    300 MaybeHandle<Cell> Module::ResolveImport(Isolate* isolate, Handle<Module> module,
    301                                         Handle<String> name, int module_request,
    302                                         MessageLocation loc, bool must_resolve,
    303                                         Module::ResolveSet* resolve_set) {
    304   Handle<Module> requested_module(
    305       Module::cast(module->requested_modules()->get(module_request)), isolate);
    306   Handle<String> specifier(
    307       String::cast(module->info()->module_requests()->get(module_request)),
    308       isolate);
    309   MaybeHandle<Cell> result =
    310       Module::ResolveExport(isolate, requested_module, specifier, name, loc,
    311                             must_resolve, resolve_set);
    312   DCHECK_IMPLIES(isolate->has_pending_exception(), result.is_null());
    313   return result;
    314 }
    315 
    316 MaybeHandle<Cell> Module::ResolveExport(Isolate* isolate, Handle<Module> module,
    317                                         Handle<String> module_specifier,
    318                                         Handle<String> export_name,
    319                                         MessageLocation loc, bool must_resolve,
    320                                         Module::ResolveSet* resolve_set) {
    321   DCHECK_GE(module->status(), kPreInstantiating);
    322   DCHECK_NE(module->status(), kEvaluating);
    323   Handle<Object> object(module->exports()->Lookup(export_name), isolate);
    324   if (object->IsCell()) {
    325     // Already resolved (e.g. because it's a local export).
    326     return Handle<Cell>::cast(object);
    327   }
    328 
    329   // Check for cycle before recursing.
    330   {
    331     // Attempt insertion with a null string set.
    332     auto result = resolve_set->insert({module, nullptr});
    333     UnorderedStringSet*& name_set = result.first->second;
    334     if (result.second) {
    335       // |module| wasn't in the map previously, so allocate a new name set.
    336       Zone* zone = resolve_set->zone();
    337       name_set =
    338           new (zone->New(sizeof(UnorderedStringSet))) UnorderedStringSet(zone);
    339     } else if (name_set->count(export_name)) {
    340       // Cycle detected.
    341       if (must_resolve) {
    342         return isolate->Throw<Cell>(
    343             isolate->factory()->NewSyntaxError(
    344                 MessageTemplate::kCyclicModuleDependency, export_name,
    345                 module_specifier),
    346             &loc);
    347       }
    348       return MaybeHandle<Cell>();
    349     }
    350     name_set->insert(export_name);
    351   }
    352 
    353   if (object->IsModuleInfoEntry()) {
    354     // Not yet resolved indirect export.
    355     Handle<ModuleInfoEntry> entry = Handle<ModuleInfoEntry>::cast(object);
    356     Handle<String> import_name(String::cast(entry->import_name()), isolate);
    357     Handle<Script> script(module->script(), isolate);
    358     MessageLocation new_loc(script, entry->beg_pos(), entry->end_pos());
    359 
    360     Handle<Cell> cell;
    361     if (!ResolveImport(isolate, module, import_name, entry->module_request(),
    362                        new_loc, true, resolve_set)
    363              .ToHandle(&cell)) {
    364       DCHECK(isolate->has_pending_exception());
    365       return MaybeHandle<Cell>();
    366     }
    367 
    368     // The export table may have changed but the entry in question should be
    369     // unchanged.
    370     Handle<ObjectHashTable> exports(module->exports(), isolate);
    371     DCHECK(exports->Lookup(export_name)->IsModuleInfoEntry());
    372 
    373     exports = ObjectHashTable::Put(exports, export_name, cell);
    374     module->set_exports(*exports);
    375     return cell;
    376   }
    377 
    378   DCHECK(object->IsTheHole(isolate));
    379   return Module::ResolveExportUsingStarExports(isolate, module,
    380                                                module_specifier, export_name,
    381                                                loc, must_resolve, resolve_set);
    382 }
    383 
    384 MaybeHandle<Cell> Module::ResolveExportUsingStarExports(
    385     Isolate* isolate, Handle<Module> module, Handle<String> module_specifier,
    386     Handle<String> export_name, MessageLocation loc, bool must_resolve,
    387     Module::ResolveSet* resolve_set) {
    388   if (!export_name->Equals(ReadOnlyRoots(isolate).default_string())) {
    389     // Go through all star exports looking for the given name.  If multiple star
    390     // exports provide the name, make sure they all map it to the same cell.
    391     Handle<Cell> unique_cell;
    392     Handle<FixedArray> special_exports(module->info()->special_exports(),
    393                                        isolate);
    394     for (int i = 0, n = special_exports->length(); i < n; ++i) {
    395       i::Handle<i::ModuleInfoEntry> entry(
    396           i::ModuleInfoEntry::cast(special_exports->get(i)), isolate);
    397       if (!entry->export_name()->IsUndefined(isolate)) {
    398         continue;  // Indirect export.
    399       }
    400 
    401       Handle<Script> script(module->script(), isolate);
    402       MessageLocation new_loc(script, entry->beg_pos(), entry->end_pos());
    403 
    404       Handle<Cell> cell;
    405       if (ResolveImport(isolate, module, export_name, entry->module_request(),
    406                         new_loc, false, resolve_set)
    407               .ToHandle(&cell)) {
    408         if (unique_cell.is_null()) unique_cell = cell;
    409         if (*unique_cell != *cell) {
    410           return isolate->Throw<Cell>(isolate->factory()->NewSyntaxError(
    411                                           MessageTemplate::kAmbiguousExport,
    412                                           module_specifier, export_name),
    413                                       &loc);
    414         }
    415       } else if (isolate->has_pending_exception()) {
    416         return MaybeHandle<Cell>();
    417       }
    418     }
    419 
    420     if (!unique_cell.is_null()) {
    421       // Found a unique star export for this name.
    422       Handle<ObjectHashTable> exports(module->exports(), isolate);
    423       DCHECK(exports->Lookup(export_name)->IsTheHole(isolate));
    424       exports = ObjectHashTable::Put(exports, export_name, unique_cell);
    425       module->set_exports(*exports);
    426       return unique_cell;
    427     }
    428   }
    429 
    430   // Unresolvable.
    431   if (must_resolve) {
    432     return isolate->Throw<Cell>(
    433         isolate->factory()->NewSyntaxError(MessageTemplate::kUnresolvableExport,
    434                                            module_specifier, export_name),
    435         &loc);
    436   }
    437   return MaybeHandle<Cell>();
    438 }
    439 
    440 bool Module::Instantiate(Isolate* isolate, Handle<Module> module,
    441                          v8::Local<v8::Context> context,
    442                          v8::Module::ResolveCallback callback) {
    443 #ifdef DEBUG
    444   if (FLAG_trace_module_status) {
    445     StdoutStream os;
    446     os << "Instantiating module ";
    447     module->script()->GetNameOrSourceURL()->Print(os);
    448 #ifndef OBJECT_PRINT
    449     os << "\n";
    450 #endif  // OBJECT_PRINT
    451   }
    452 #endif  // DEBUG
    453 
    454   if (!PrepareInstantiate(isolate, module, context, callback)) {
    455     ResetGraph(isolate, module);
    456     return false;
    457   }
    458   Zone zone(isolate->allocator(), ZONE_NAME);
    459   ZoneForwardList<Handle<Module>> stack(&zone);
    460   unsigned dfs_index = 0;
    461   if (!FinishInstantiate(isolate, module, &stack, &dfs_index, &zone)) {
    462     for (auto& descendant : stack) {
    463       Reset(isolate, descendant);
    464     }
    465     DCHECK_EQ(module->status(), kUninstantiated);
    466     return false;
    467   }
    468   DCHECK(module->status() == kInstantiated || module->status() == kEvaluated ||
    469          module->status() == kErrored);
    470   DCHECK(stack.empty());
    471   return true;
    472 }
    473 
    474 bool Module::PrepareInstantiate(Isolate* isolate, Handle<Module> module,
    475                                 v8::Local<v8::Context> context,
    476                                 v8::Module::ResolveCallback callback) {
    477   DCHECK_NE(module->status(), kEvaluating);
    478   DCHECK_NE(module->status(), kInstantiating);
    479   if (module->status() >= kPreInstantiating) return true;
    480   module->SetStatus(kPreInstantiating);
    481   STACK_CHECK(isolate, false);
    482 
    483   // Obtain requested modules.
    484   Handle<ModuleInfo> module_info(module->info(), isolate);
    485   Handle<FixedArray> module_requests(module_info->module_requests(), isolate);
    486   Handle<FixedArray> requested_modules(module->requested_modules(), isolate);
    487   for (int i = 0, length = module_requests->length(); i < length; ++i) {
    488     Handle<String> specifier(String::cast(module_requests->get(i)), isolate);
    489     v8::Local<v8::Module> api_requested_module;
    490     if (!callback(context, v8::Utils::ToLocal(specifier),
    491                   v8::Utils::ToLocal(module))
    492              .ToLocal(&api_requested_module)) {
    493       isolate->PromoteScheduledException();
    494       return false;
    495     }
    496     Handle<Module> requested_module = Utils::OpenHandle(*api_requested_module);
    497     requested_modules->set(i, *requested_module);
    498   }
    499 
    500   // Recurse.
    501   for (int i = 0, length = requested_modules->length(); i < length; ++i) {
    502     Handle<Module> requested_module(Module::cast(requested_modules->get(i)),
    503                                     isolate);
    504     if (!PrepareInstantiate(isolate, requested_module, context, callback)) {
    505       return false;
    506     }
    507   }
    508 
    509   // Set up local exports.
    510   // TODO(neis): Create regular_exports array here instead of in factory method?
    511   for (int i = 0, n = module_info->RegularExportCount(); i < n; ++i) {
    512     int cell_index = module_info->RegularExportCellIndex(i);
    513     Handle<FixedArray> export_names(module_info->RegularExportExportNames(i),
    514                                     isolate);
    515     CreateExport(isolate, module, cell_index, export_names);
    516   }
    517 
    518   // Partially set up indirect exports.
    519   // For each indirect export, we create the appropriate slot in the export
    520   // table and store its ModuleInfoEntry there.  When we later find the correct
    521   // Cell in the module that actually provides the value, we replace the
    522   // ModuleInfoEntry by that Cell (see ResolveExport).
    523   Handle<FixedArray> special_exports(module_info->special_exports(), isolate);
    524   for (int i = 0, n = special_exports->length(); i < n; ++i) {
    525     Handle<ModuleInfoEntry> entry(
    526         ModuleInfoEntry::cast(special_exports->get(i)), isolate);
    527     Handle<Object> export_name(entry->export_name(), isolate);
    528     if (export_name->IsUndefined(isolate)) continue;  // Star export.
    529     CreateIndirectExport(isolate, module, Handle<String>::cast(export_name),
    530                          entry);
    531   }
    532 
    533   DCHECK_EQ(module->status(), kPreInstantiating);
    534   return true;
    535 }
    536 
    537 bool Module::RunInitializationCode(Isolate* isolate, Handle<Module> module) {
    538   DCHECK_EQ(module->status(), kInstantiating);
    539   Handle<JSFunction> function(JSFunction::cast(module->code()), isolate);
    540   DCHECK_EQ(MODULE_SCOPE, function->shared()->scope_info()->scope_type());
    541   Handle<Object> receiver = isolate->factory()->undefined_value();
    542   Handle<Object> argv[] = {module};
    543   MaybeHandle<Object> maybe_generator =
    544       Execution::Call(isolate, function, receiver, arraysize(argv), argv);
    545   Handle<Object> generator;
    546   if (!maybe_generator.ToHandle(&generator)) {
    547     DCHECK(isolate->has_pending_exception());
    548     return false;
    549   }
    550   DCHECK_EQ(*function, Handle<JSGeneratorObject>::cast(generator)->function());
    551   module->set_code(*generator);
    552   return true;
    553 }
    554 
    555 bool Module::MaybeTransitionComponent(Isolate* isolate, Handle<Module> module,
    556                                       ZoneForwardList<Handle<Module>>* stack,
    557                                       Status new_status) {
    558   DCHECK(new_status == kInstantiated || new_status == kEvaluated);
    559   SLOW_DCHECK(
    560       // {module} is on the {stack}.
    561       std::count_if(stack->begin(), stack->end(),
    562                     [&](Handle<Module> m) { return *m == *module; }) == 1);
    563   DCHECK_LE(module->dfs_ancestor_index(), module->dfs_index());
    564   if (module->dfs_ancestor_index() == module->dfs_index()) {
    565     // This is the root of its strongly connected component.
    566     Handle<Module> ancestor;
    567     do {
    568       ancestor = stack->front();
    569       stack->pop_front();
    570       DCHECK_EQ(ancestor->status(),
    571                 new_status == kInstantiated ? kInstantiating : kEvaluating);
    572       if (new_status == kInstantiated) {
    573         if (!RunInitializationCode(isolate, ancestor)) return false;
    574       }
    575       ancestor->SetStatus(new_status);
    576     } while (*ancestor != *module);
    577   }
    578   return true;
    579 }
    580 
    581 bool Module::FinishInstantiate(Isolate* isolate, Handle<Module> module,
    582                                ZoneForwardList<Handle<Module>>* stack,
    583                                unsigned* dfs_index, Zone* zone) {
    584   DCHECK_NE(module->status(), kEvaluating);
    585   if (module->status() >= kInstantiating) return true;
    586   DCHECK_EQ(module->status(), kPreInstantiating);
    587   STACK_CHECK(isolate, false);
    588 
    589   // Instantiate SharedFunctionInfo and mark module as instantiating for
    590   // the recursion.
    591   Handle<SharedFunctionInfo> shared(SharedFunctionInfo::cast(module->code()),
    592                                     isolate);
    593   Handle<JSFunction> function =
    594       isolate->factory()->NewFunctionFromSharedFunctionInfo(
    595           shared, isolate->native_context());
    596   module->set_code(*function);
    597   module->SetStatus(kInstantiating);
    598   module->set_dfs_index(*dfs_index);
    599   module->set_dfs_ancestor_index(*dfs_index);
    600   stack->push_front(module);
    601   (*dfs_index)++;
    602 
    603   // Recurse.
    604   Handle<FixedArray> requested_modules(module->requested_modules(), isolate);
    605   for (int i = 0, length = requested_modules->length(); i < length; ++i) {
    606     Handle<Module> requested_module(Module::cast(requested_modules->get(i)),
    607                                     isolate);
    608     if (!FinishInstantiate(isolate, requested_module, stack, dfs_index, zone)) {
    609       return false;
    610     }
    611 
    612     DCHECK_NE(requested_module->status(), kEvaluating);
    613     DCHECK_GE(requested_module->status(), kInstantiating);
    614     SLOW_DCHECK(
    615         // {requested_module} is instantiating iff it's on the {stack}.
    616         (requested_module->status() == kInstantiating) ==
    617         std::count_if(stack->begin(), stack->end(), [&](Handle<Module> m) {
    618           return *m == *requested_module;
    619         }));
    620 
    621     if (requested_module->status() == kInstantiating) {
    622       module->set_dfs_ancestor_index(
    623           std::min(module->dfs_ancestor_index(),
    624                    requested_module->dfs_ancestor_index()));
    625     }
    626   }
    627 
    628   Handle<Script> script(module->script(), isolate);
    629   Handle<ModuleInfo> module_info(module->info(), isolate);
    630 
    631   // Resolve imports.
    632   Handle<FixedArray> regular_imports(module_info->regular_imports(), isolate);
    633   for (int i = 0, n = regular_imports->length(); i < n; ++i) {
    634     Handle<ModuleInfoEntry> entry(
    635         ModuleInfoEntry::cast(regular_imports->get(i)), isolate);
    636     Handle<String> name(String::cast(entry->import_name()), isolate);
    637     MessageLocation loc(script, entry->beg_pos(), entry->end_pos());
    638     ResolveSet resolve_set(zone);
    639     Handle<Cell> cell;
    640     if (!ResolveImport(isolate, module, name, entry->module_request(), loc,
    641                        true, &resolve_set)
    642              .ToHandle(&cell)) {
    643       return false;
    644     }
    645     module->regular_imports()->set(ImportIndex(entry->cell_index()), *cell);
    646   }
    647 
    648   // Resolve indirect exports.
    649   Handle<FixedArray> special_exports(module_info->special_exports(), isolate);
    650   for (int i = 0, n = special_exports->length(); i < n; ++i) {
    651     Handle<ModuleInfoEntry> entry(
    652         ModuleInfoEntry::cast(special_exports->get(i)), isolate);
    653     Handle<Object> name(entry->export_name(), isolate);
    654     if (name->IsUndefined(isolate)) continue;  // Star export.
    655     MessageLocation loc(script, entry->beg_pos(), entry->end_pos());
    656     ResolveSet resolve_set(zone);
    657     if (ResolveExport(isolate, module, Handle<String>(),
    658                       Handle<String>::cast(name), loc, true, &resolve_set)
    659             .is_null()) {
    660       return false;
    661     }
    662   }
    663 
    664   return MaybeTransitionComponent(isolate, module, stack, kInstantiated);
    665 }
    666 
    667 MaybeHandle<Object> Module::Evaluate(Isolate* isolate, Handle<Module> module) {
    668 #ifdef DEBUG
    669   if (FLAG_trace_module_status) {
    670     StdoutStream os;
    671     os << "Evaluating module ";
    672     module->script()->GetNameOrSourceURL()->Print(os);
    673 #ifndef OBJECT_PRINT
    674     os << "\n";
    675 #endif  // OBJECT_PRINT
    676   }
    677 #endif  // DEBUG
    678   if (module->status() == kErrored) {
    679     isolate->Throw(module->GetException());
    680     return MaybeHandle<Object>();
    681   }
    682   DCHECK_NE(module->status(), kEvaluating);
    683   DCHECK_GE(module->status(), kInstantiated);
    684   Zone zone(isolate->allocator(), ZONE_NAME);
    685 
    686   ZoneForwardList<Handle<Module>> stack(&zone);
    687   unsigned dfs_index = 0;
    688   Handle<Object> result;
    689   if (!Evaluate(isolate, module, &stack, &dfs_index).ToHandle(&result)) {
    690     for (auto& descendant : stack) {
    691       DCHECK_EQ(descendant->status(), kEvaluating);
    692       descendant->RecordError(isolate);
    693     }
    694     DCHECK_EQ(module->GetException(), isolate->pending_exception());
    695     return MaybeHandle<Object>();
    696   }
    697   DCHECK_EQ(module->status(), kEvaluated);
    698   DCHECK(stack.empty());
    699   return result;
    700 }
    701 
    702 MaybeHandle<Object> Module::Evaluate(Isolate* isolate, Handle<Module> module,
    703                                      ZoneForwardList<Handle<Module>>* stack,
    704                                      unsigned* dfs_index) {
    705   if (module->status() == kErrored) {
    706     isolate->Throw(module->GetException());
    707     return MaybeHandle<Object>();
    708   }
    709   if (module->status() >= kEvaluating) {
    710     return isolate->factory()->undefined_value();
    711   }
    712   DCHECK_EQ(module->status(), kInstantiated);
    713   STACK_CHECK(isolate, MaybeHandle<Object>());
    714 
    715   Handle<JSGeneratorObject> generator(JSGeneratorObject::cast(module->code()),
    716                                       isolate);
    717   module->set_code(
    718       generator->function()->shared()->scope_info()->ModuleDescriptorInfo());
    719   module->SetStatus(kEvaluating);
    720   module->set_dfs_index(*dfs_index);
    721   module->set_dfs_ancestor_index(*dfs_index);
    722   stack->push_front(module);
    723   (*dfs_index)++;
    724 
    725   // Recursion.
    726   Handle<FixedArray> requested_modules(module->requested_modules(), isolate);
    727   for (int i = 0, length = requested_modules->length(); i < length; ++i) {
    728     Handle<Module> requested_module(Module::cast(requested_modules->get(i)),
    729                                     isolate);
    730     RETURN_ON_EXCEPTION(
    731         isolate, Evaluate(isolate, requested_module, stack, dfs_index), Object);
    732 
    733     DCHECK_GE(requested_module->status(), kEvaluating);
    734     DCHECK_NE(requested_module->status(), kErrored);
    735     SLOW_DCHECK(
    736         // {requested_module} is evaluating iff it's on the {stack}.
    737         (requested_module->status() == kEvaluating) ==
    738         std::count_if(stack->begin(), stack->end(), [&](Handle<Module> m) {
    739           return *m == *requested_module;
    740         }));
    741 
    742     if (requested_module->status() == kEvaluating) {
    743       module->set_dfs_ancestor_index(
    744           std::min(module->dfs_ancestor_index(),
    745                    requested_module->dfs_ancestor_index()));
    746     }
    747   }
    748 
    749   // Evaluation of module body.
    750   Handle<JSFunction> resume(
    751       isolate->native_context()->generator_next_internal(), isolate);
    752   Handle<Object> result;
    753   ASSIGN_RETURN_ON_EXCEPTION(
    754       isolate, result, Execution::Call(isolate, resume, generator, 0, nullptr),
    755       Object);
    756   DCHECK(static_cast<JSIteratorResult*>(JSObject::cast(*result))
    757              ->done()
    758              ->BooleanValue(isolate));
    759 
    760   CHECK(MaybeTransitionComponent(isolate, module, stack, kEvaluated));
    761   return handle(
    762       static_cast<JSIteratorResult*>(JSObject::cast(*result))->value(),
    763       isolate);
    764 }
    765 
    766 namespace {
    767 
    768 void FetchStarExports(Isolate* isolate, Handle<Module> module, Zone* zone,
    769                       UnorderedModuleSet* visited) {
    770   DCHECK_GE(module->status(), Module::kInstantiating);
    771 
    772   if (module->module_namespace()->IsJSModuleNamespace()) return;  // Shortcut.
    773 
    774   bool cycle = !visited->insert(module).second;
    775   if (cycle) return;
    776   Handle<ObjectHashTable> exports(module->exports(), isolate);
    777   UnorderedStringMap more_exports(zone);
    778 
    779   // TODO(neis): Only allocate more_exports if there are star exports.
    780   // Maybe split special_exports into indirect_exports and star_exports.
    781 
    782   ReadOnlyRoots roots(isolate);
    783   Handle<FixedArray> special_exports(module->info()->special_exports(),
    784                                      isolate);
    785   for (int i = 0, n = special_exports->length(); i < n; ++i) {
    786     Handle<ModuleInfoEntry> entry(
    787         ModuleInfoEntry::cast(special_exports->get(i)), isolate);
    788     if (!entry->export_name()->IsUndefined(roots)) {
    789       continue;  // Indirect export.
    790     }
    791 
    792     Handle<Module> requested_module(
    793         Module::cast(module->requested_modules()->get(entry->module_request())),
    794         isolate);
    795 
    796     // Recurse.
    797     FetchStarExports(isolate, requested_module, zone, visited);
    798 
    799     // Collect all of [requested_module]'s exports that must be added to
    800     // [module]'s exports (i.e. to [exports]).  We record these in
    801     // [more_exports].  Ambiguities (conflicting exports) are marked by mapping
    802     // the name to undefined instead of a Cell.
    803     Handle<ObjectHashTable> requested_exports(requested_module->exports(),
    804                                               isolate);
    805     for (int i = 0, n = requested_exports->Capacity(); i < n; ++i) {
    806       Object* key;
    807       if (!requested_exports->ToKey(roots, i, &key)) continue;
    808       Handle<String> name(String::cast(key), isolate);
    809 
    810       if (name->Equals(roots.default_string())) continue;
    811       if (!exports->Lookup(name)->IsTheHole(roots)) continue;
    812 
    813       Handle<Cell> cell(Cell::cast(requested_exports->ValueAt(i)), isolate);
    814       auto insert_result = more_exports.insert(std::make_pair(name, cell));
    815       if (!insert_result.second) {
    816         auto it = insert_result.first;
    817         if (*it->second == *cell || it->second->IsUndefined(roots)) {
    818           // We already recorded this mapping before, or the name is already
    819           // known to be ambiguous.  In either case, there's nothing to do.
    820         } else {
    821           DCHECK(it->second->IsCell());
    822           // Different star exports provide different cells for this name, hence
    823           // mark the name as ambiguous.
    824           it->second = roots.undefined_value_handle();
    825         }
    826       }
    827     }
    828   }
    829 
    830   // Copy [more_exports] into [exports].
    831   for (const auto& elem : more_exports) {
    832     if (elem.second->IsUndefined(isolate)) continue;  // Ambiguous export.
    833     DCHECK(!elem.first->Equals(ReadOnlyRoots(isolate).default_string()));
    834     DCHECK(elem.second->IsCell());
    835     exports = ObjectHashTable::Put(exports, elem.first, elem.second);
    836   }
    837   module->set_exports(*exports);
    838 }
    839 
    840 }  // anonymous namespace
    841 
    842 Handle<JSModuleNamespace> Module::GetModuleNamespace(Isolate* isolate,
    843                                                      Handle<Module> module,
    844                                                      int module_request) {
    845   Handle<Module> requested_module(
    846       Module::cast(module->requested_modules()->get(module_request)), isolate);
    847   return Module::GetModuleNamespace(isolate, requested_module);
    848 }
    849 
    850 Handle<JSModuleNamespace> Module::GetModuleNamespace(Isolate* isolate,
    851                                                      Handle<Module> module) {
    852   Handle<HeapObject> object(module->module_namespace(), isolate);
    853   ReadOnlyRoots roots(isolate);
    854   if (!object->IsUndefined(roots)) {
    855     // Namespace object already exists.
    856     return Handle<JSModuleNamespace>::cast(object);
    857   }
    858 
    859   // Collect the export names.
    860   Zone zone(isolate->allocator(), ZONE_NAME);
    861   UnorderedModuleSet visited(&zone);
    862   FetchStarExports(isolate, module, &zone, &visited);
    863   Handle<ObjectHashTable> exports(module->exports(), isolate);
    864   ZoneVector<Handle<String>> names(&zone);
    865   names.reserve(exports->NumberOfElements());
    866   for (int i = 0, n = exports->Capacity(); i < n; ++i) {
    867     Object* key;
    868     if (!exports->ToKey(roots, i, &key)) continue;
    869     names.push_back(handle(String::cast(key), isolate));
    870   }
    871   DCHECK_EQ(static_cast<int>(names.size()), exports->NumberOfElements());
    872 
    873   // Sort them alphabetically.
    874   std::sort(names.begin(), names.end(),
    875             [&isolate](Handle<String> a, Handle<String> b) {
    876               return String::Compare(isolate, a, b) ==
    877                      ComparisonResult::kLessThan;
    878             });
    879 
    880   // Create the namespace object (initially empty).
    881   Handle<JSModuleNamespace> ns = isolate->factory()->NewJSModuleNamespace();
    882   ns->set_module(*module);
    883   module->set_module_namespace(*ns);
    884 
    885   // Create the properties in the namespace object. Transition the object
    886   // to dictionary mode so that property addition is faster.
    887   PropertyAttributes attr = DONT_DELETE;
    888   JSObject::NormalizeProperties(ns, CLEAR_INOBJECT_PROPERTIES,
    889                                 static_cast<int>(names.size()),
    890                                 "JSModuleNamespace");
    891   for (const auto& name : names) {
    892     JSObject::SetNormalizedProperty(
    893         ns, name, Accessors::MakeModuleNamespaceEntryInfo(isolate, name),
    894         PropertyDetails(kAccessor, attr, PropertyCellType::kMutable));
    895   }
    896   JSObject::PreventExtensions(ns, kThrowOnError).ToChecked();
    897 
    898   // Optimize the namespace object as a prototype, for two reasons:
    899   // - The object's map is guaranteed not to be shared. ICs rely on this.
    900   // - We can store a pointer from the map back to the namespace object.
    901   //   Turbofan can use this for inlining the access.
    902   JSObject::OptimizeAsPrototype(ns);
    903 
    904   Handle<PrototypeInfo> proto_info =
    905       Map::GetOrCreatePrototypeInfo(Handle<JSObject>::cast(ns), isolate);
    906   proto_info->set_module_namespace(*ns);
    907   return ns;
    908 }
    909 
    910 MaybeHandle<Object> JSModuleNamespace::GetExport(Isolate* isolate,
    911                                                  Handle<String> name) {
    912   Handle<Object> object(module()->exports()->Lookup(name), isolate);
    913   if (object->IsTheHole(isolate)) {
    914     return isolate->factory()->undefined_value();
    915   }
    916 
    917   Handle<Object> value(Handle<Cell>::cast(object)->value(), isolate);
    918   if (value->IsTheHole(isolate)) {
    919     THROW_NEW_ERROR(
    920         isolate, NewReferenceError(MessageTemplate::kNotDefined, name), Object);
    921   }
    922 
    923   return value;
    924 }
    925 
    926 Maybe<PropertyAttributes> JSModuleNamespace::GetPropertyAttributes(
    927     LookupIterator* it) {
    928   Handle<JSModuleNamespace> object = it->GetHolder<JSModuleNamespace>();
    929   Handle<String> name = Handle<String>::cast(it->GetName());
    930   DCHECK_EQ(it->state(), LookupIterator::ACCESSOR);
    931 
    932   Isolate* isolate = it->isolate();
    933 
    934   Handle<Object> lookup(object->module()->exports()->Lookup(name), isolate);
    935   if (lookup->IsTheHole(isolate)) {
    936     return Just(ABSENT);
    937   }
    938 
    939   Handle<Object> value(Handle<Cell>::cast(lookup)->value(), isolate);
    940   if (value->IsTheHole(isolate)) {
    941     isolate->Throw(*isolate->factory()->NewReferenceError(
    942         MessageTemplate::kNotDefined, name));
    943     return Nothing<PropertyAttributes>();
    944   }
    945 
    946   return Just(it->property_attributes());
    947 }
    948 
    949 }  // namespace internal
    950 }  // namespace v8
    951