Repository navigation
Expand file tree
/
Copy pathAbstractModuleRecord.cpp
More file actions
1278 lines (1137 loc) · 56.2 KB
/
Copy pathAbstractModuleRecord.cpp
File metadata and controls
1278 lines (1137 loc) · 56.2 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/*
* Copyright (C) 2015-2021 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "config.h"
#include "AbstractModuleRecord.h"
#include "CyclicModuleRecord.h"
#include "Error.h"
#include "JSCInlines.h"
#include "JSInternalFieldObjectImplInlines.h"
#include "JSMapInlines.h"
#include "JSModuleEnvironment.h"
#include "JSModuleLoader.h"
#include "JSModuleNamespaceObject.h"
#include "JSModuleRecord.h"
#include "JSPromise.h"
#include "SyntheticModuleRecord.h"
#include "VMTrapsInlines.h"
#include "WebAssemblyModuleRecord.h"
#include <wtf/text/MakeString.h>
namespace JSC {
namespace AbstractModuleRecordInternal {
static constexpr bool verbose = false;
} // namespace AbstractModuleRecordInternal
const ClassInfo AbstractModuleRecord::s_info = { "AbstractModuleRecord"_s, &Base::s_info, nullptr, nullptr, CREATE_METHOD_TABLE(AbstractModuleRecord) };
AbstractModuleRecord::AsyncEvaluationOrder::AsyncEvaluationOrder(int64_t order)
: m_order(order)
{
}
int64_t AbstractModuleRecord::AsyncEvaluationOrder::order() const
{
ASSERT(hasOrder());
return m_order;
}
auto AbstractModuleRecord::AsyncEvaluationOrder::order(int64_t order) -> AsyncEvaluationOrder&
{
ASSERT(order >= 0);
m_order = order;
return *this;
}
AbstractModuleRecord::AbstractModuleRecord(VM& vm, Structure* structure, Identifier moduleKey)
: Base(vm, structure)
, m_moduleKey(WTF::move(moduleKey))
{
}
void AbstractModuleRecord::finishCreation(JSGlobalObject*, VM& vm)
{
Base::finishCreation(vm);
ASSERT(inherits(info()));
auto values = initialValues();
ASSERT(values.size() == numberOfInternalFields);
for (unsigned index = 0; index < values.size(); ++index)
Base::internalField(index).set(vm, this, values[index]);
}
template<typename Visitor>
void AbstractModuleRecord::visitChildrenImpl(JSCell* cell, Visitor& visitor)
{
AbstractModuleRecord* thisObject = jsCast<AbstractModuleRecord*>(cell);
ASSERT_GC_OBJECT_INHERITS(thisObject, info());
Base::visitChildren(thisObject, visitor);
visitor.append(thisObject->m_moduleEnvironment);
visitor.append(thisObject->m_moduleNamespaceObject);
visitor.append(thisObject->m_cycleRoot);
visitor.append(thisObject->m_topLevelCapability);
visitor.append(thisObject->m_asyncCapability);
Locker locker { thisObject->cellLock() };
visitor.append(thisObject->m_asyncParentModules.begin(), thisObject->m_asyncParentModules.end());
auto values = thisObject->m_dependencies.values();
visitor.append(values.begin(), values.end());
for (const auto& [key, loadedModule] : thisObject->m_loadedModules)
visitor.append(loadedModule.m_module);
}
DEFINE_VISIT_CHILDREN(AbstractModuleRecord);
ScriptFetchParameters::Type AbstractModuleRecord::ModuleRequest::type(ScriptFetchParameters::Type fallback) const
{
if (m_attributes)
return m_attributes->type();
return fallback;
}
AbstractModuleRecord::LoadedModuleRequest::LoadedModuleRequest(VM& vm, ModuleRequest moduleRequest, AbstractModuleRecord* loadedModule, JSCell* owner)
: ModuleRequest(WTF::move(moduleRequest))
, m_module(vm, owner, loadedModule)
{
}
bool AbstractModuleRecord::ModuleRequest::operator==(const ModuleRequest& other) const
{
if (this == &other)
return true;
if (m_specifier != other.m_specifier)
return false;
if (!!m_attributes != !!other.m_attributes)
return false;
if (m_attributes)
return m_attributes->type() == other.m_attributes->type();
return true;
}
void AbstractModuleRecord::appendRequestedModule(const Identifier& moduleName, RefPtr<ScriptFetchParameters>&& attributes)
{
m_requestedModules.append({ moduleName, WTF::move(attributes) });
}
void AbstractModuleRecord::addStarExportEntry(const Identifier& moduleName)
{
m_starExportEntries.add(moduleName.impl());
}
void AbstractModuleRecord::addImportEntry(const ImportEntry& entry)
{
bool isNewEntry = m_importEntries.add(entry.localName.impl(), entry).isNewEntry;
ASSERT_UNUSED(isNewEntry, isNewEntry); // This is guaranteed by the parser.
}
void AbstractModuleRecord::addExportEntry(const ExportEntry& entry)
{
bool isNewEntry = m_exportEntries.add(entry.exportName.impl(), entry).isNewEntry;
ASSERT_UNUSED(isNewEntry, isNewEntry); // This is guaranteed by the parser.
}
auto AbstractModuleRecord::tryGetImportEntry(UniquedStringImpl* localName) -> std::optional<ImportEntry>
{
const auto iterator = m_importEntries.find(localName);
if (iterator == m_importEntries.end())
return std::nullopt;
return std::optional<ImportEntry>(iterator->value);
}
auto AbstractModuleRecord::tryGetExportEntry(UniquedStringImpl* exportName) -> std::optional<ExportEntry>
{
const auto iterator = m_exportEntries.find(exportName);
if (iterator == m_exportEntries.end())
return std::nullopt;
return std::optional<ExportEntry>(iterator->value);
}
auto AbstractModuleRecord::ExportEntry::createLocal(const Identifier& exportName, const Identifier& localName) -> ExportEntry
{
return ExportEntry { Type::Local, exportName, Identifier(), Identifier(), localName };
}
auto AbstractModuleRecord::ExportEntry::createIndirect(const Identifier& exportName, const Identifier& importName, const Identifier& moduleName) -> ExportEntry
{
return ExportEntry { Type::Indirect, exportName, moduleName, importName, Identifier() };
}
auto AbstractModuleRecord::ExportEntry::createNamespace(const Identifier& exportName, const Identifier& moduleName) -> ExportEntry
{
return ExportEntry { Type::Namespace, exportName, moduleName, Identifier(), Identifier() };
}
auto AbstractModuleRecord::Resolution::notFound() -> Resolution
{
return Resolution { Type::NotFound, nullptr, Identifier() };
}
auto AbstractModuleRecord::Resolution::error() -> Resolution
{
return Resolution { Type::Error, nullptr, Identifier() };
}
auto AbstractModuleRecord::Resolution::ambiguous() -> Resolution
{
return Resolution { Type::Ambiguous, nullptr, Identifier() };
}
AbstractModuleRecord* AbstractModuleRecord::hostResolveImportedModule(JSGlobalObject* globalObject, const Identifier& moduleName)
{
if (auto iter = m_dependencies.find(moduleName.string()); iter != m_dependencies.end())
return iter->value.get();
return globalObject->moduleLoader()->maybeGetImportedModule(this, moduleName);
}
auto AbstractModuleRecord::resolveImport(JSGlobalObject* globalObject, const Identifier& localName) -> Resolution
{
VM& vm = globalObject->vm();
auto scope = DECLARE_THROW_SCOPE(vm);
std::optional<ImportEntry> optionalImportEntry = tryGetImportEntry(localName.impl());
if (!optionalImportEntry)
return Resolution::notFound();
const ImportEntry& importEntry = *optionalImportEntry;
if (importEntry.type == AbstractModuleRecord::ImportEntryType::Namespace)
return Resolution::notFound();
AbstractModuleRecord* importedModule = hostResolveImportedModule(globalObject, importEntry.moduleRequest);
RETURN_IF_EXCEPTION(scope, Resolution::error());
return importedModule->resolveExport(globalObject, importEntry.importName);
}
struct AbstractModuleRecord::ResolveQuery {
struct Hash {
static unsigned hash(const ResolveQuery&);
static bool equal(const ResolveQuery&, const ResolveQuery&);
static constexpr bool safeToCompareToEmptyOrDeleted = true;
};
using HashTraits = WTF::CustomHashTraits<ResolveQuery>;
ResolveQuery(AbstractModuleRecord* moduleRecord, UniquedStringImpl* exportName)
: moduleRecord(moduleRecord)
, exportName(exportName)
{
}
ResolveQuery(AbstractModuleRecord* moduleRecord, const Identifier& exportName)
: ResolveQuery(moduleRecord, exportName.impl())
{
}
enum EmptyValueTag { EmptyValue };
ResolveQuery(EmptyValueTag)
{
}
enum DeletedValueTag { DeletedValue };
ResolveQuery(DeletedValueTag)
: moduleRecord(nullptr)
, exportName(WTF::HashTableDeletedValue)
{
}
bool NODELETE isEmptyValue() const
{
return !exportName;
}
bool NODELETE isDeletedValue() const
{
return exportName.isHashTableDeletedValue();
}
void dump(PrintStream& out) const
{
if (!moduleRecord) {
out.print("<empty>");
return;
}
out.print(moduleRecord->moduleKey(), " \"", exportName.get(), "\"");
}
// The module record is not marked from the GC. But these records are reachable from the JSGlobalObject.
// So we don't care the reachability to this record.
AbstractModuleRecord* moduleRecord;
RefPtr<UniquedStringImpl> exportName;
};
inline unsigned NODELETE AbstractModuleRecord::ResolveQuery::Hash::hash(const ResolveQuery& query)
{
return WTF::PtrHash<AbstractModuleRecord*>::hash(query.moduleRecord) + IdentifierRepHash::hash(query.exportName);
}
inline bool NODELETE AbstractModuleRecord::ResolveQuery::Hash::equal(const ResolveQuery& lhs, const ResolveQuery& rhs)
{
return lhs.moduleRecord == rhs.moduleRecord && lhs.exportName == rhs.exportName;
}
auto AbstractModuleRecord::tryGetCachedResolution(UniquedStringImpl* exportName) -> std::optional<Resolution>
{
const auto iterator = m_resolutionCache.find(exportName);
if (iterator == m_resolutionCache.end())
return std::nullopt;
return std::optional<Resolution>(iterator->value);
}
void AbstractModuleRecord::cacheResolution(UniquedStringImpl* exportName, const Resolution& resolution)
{
m_resolutionCache.add(exportName, resolution);
}
auto AbstractModuleRecord::resolveExportImpl(JSGlobalObject* globalObject, const ResolveQuery& root) -> Resolution
{
VM& vm = globalObject->vm();
auto scope = DECLARE_THROW_SCOPE(vm);
if (AbstractModuleRecordInternal::verbose)
dataLog("Resolving ", root, "\n");
// https://tc39.github.io/ecma262/#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.
//
// 1. pendingTasks
// We enqueue the recursive resolveExport call to this queue to avoid recursive calls in C++.
// The task has 3 types. (1) Query, (2) IndirectFallback and (3) GatherStars.
// (1) Query
// Querying the resolution to the current module.
// (2) IndirectFallback
// Examine the result of the indirect export resolution. Only when the indirect export resolution fails,
// we look into the star exports. (step 5-a-vi).
// (3) GatherStars
// Examine the result of the star export resolutions.
//
// 2. frames
// When the spec calls the resolveExport recursively, instead we append the frame
// (that holds the result resolution) to the frames and enqueue the task to the pendingTasks.
// The entry in the frames means the *local* resolution result of the specific recursive resolveExport.
//
// We should maintain the local resolution result instead of holding the global resolution result only.
// For example,
//
// star
// (1) ---> (2) "Resolve"
// |
// |
// +-> (3) "NotFound"
// |
// | star
// +-> (4) ---> (5) "Resolve" [here]
// |
// |
// +-> (6) "Error"
//
// Consider the above graph. The numbers represents the modules. Now we are [here].
// If we only hold the global resolution result during the resolveExport operation, [here],
// we decide the entire result of resolveExport is "Ambiguous", because there are multiple
// "Resolve" (in module (2) and (5)). However, this should become "Error" because (6) will
// propagate "Error" state to the (4), (4) will become "Error" and then, (1) will become
// "Error". We should aggregate the results at the star exports point ((4) and (1)).
//
// Usually, both "Error" and "Ambiguous" states will throw the syntax error. So except for the content of the
// error message, there are no difference. (And if we fix the (6) that raises "Error", next, it will produce
// the "Ambiguous" error due to (5). Anyway, user need to fix the both. So which error should be raised at first
// doesn't matter so much.
//
// However, this may become the problem under the module namespace creation.
// http://www.ecma-international.org/ecma-262/6.0/#sec-getmodulenamespace
// section 15.2.1.18, step 3-d-ii
// Here, we distinguish "Ambiguous" and "Error". When "Error" state is produced, we need to throw the propagated error.
// But if "Ambiguous" state comes, we just ignore the result.
// To follow the requirement strictly, in this implementation, we keep the local resolution result to produce the
// correct result under the above complex cases.
// 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 AbstractModuleRecords 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.
using ResolveSet = WTF::UncheckedKeyHashSet<ResolveQuery, ResolveQuery::Hash, ResolveQuery::HashTraits>;
enum class Type { Query, IndirectFallback, GatherStars };
struct Task {
ResolveQuery query;
Type type;
};
auto typeString = [] (Type type) -> const char* {
switch (type) {
case Type::Query:
return "Query";
case Type::IndirectFallback:
return "IndirectFallback";
case Type::GatherStars:
return "GatherStars";
}
RELEASE_ASSERT_NOT_REACHED();
return nullptr;
};
Vector<Task, 8> pendingTasks;
ResolveSet resolveSet;
Vector<Resolution, 8> frames;
bool foundStarLinks = false;
frames.append(Resolution::notFound());
// Call when the query is not resolved in the current module.
// It will enqueue the star resolution requests. Return "false" if the error occurs.
auto resolveNonLocal = [&](const ResolveQuery& query) -> bool {
// https://tc39.github.io/ecma262/#sec-resolveexport
// section 15.2.1.16.3, step 6
// If the "default" name is not resolved in the current module, we need to throw an error and stop resolution immediately,
// Rationale to this error: A default export cannot be provided by an export *.
VM& vm = globalObject->vm();
auto scope = DECLARE_THROW_SCOPE(vm);
if (query.exportName == vm.propertyNames->defaultKeyword.impl())
return false;
// 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;
AbstractModuleRecord* importedModuleRecord = query.moduleRecord->hostResolveImportedModule(globalObject, Identifier::fromUid(vm, starModuleName.get()));
RETURN_IF_EXCEPTION(scope, false);
pendingTasks.append(Task { ResolveQuery(importedModuleRecord, query.exportName.get()), Type::Query });
}
return true;
};
// Return the current resolution value of the top frame.
auto currentTop = [&] () -> Resolution& {
ASSERT(!frames.isEmpty());
return frames.last();
};
// Merge the given resolution to the current resolution value of the top frame.
// If there is ambiguity, return "false". When the "false" is returned, we should make the result "ambiguous".
auto mergeToCurrentTop = [&] (const Resolution& resolution) -> bool {
if (resolution.type == Resolution::Type::NotFound)
return true;
if (currentTop().type == Resolution::Type::NotFound) {
currentTop() = resolution;
return true;
}
if (currentTop().moduleRecord != resolution.moduleRecord || currentTop().localName != resolution.localName)
return false;
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();
const ResolveQuery& query = task.query;
if (AbstractModuleRecordInternal::verbose)
dataLog(" ", typeString(task.type), " ", task.query, "\n");
switch (task.type) {
case Type::Query: {
AbstractModuleRecord* moduleRecord = query.moduleRecord;
if (!resolveSet.add(task.query).isNewEntry)
continue;
// 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 (std::optional<Resolution> cachedResolution = moduleRecord->tryGetCachedResolution(query.exportName.get())) {
if (!mergeToCurrentTop(*cachedResolution))
return Resolution::ambiguous();
continue;
}
}
const std::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.
bool success = resolveNonLocal(task.query);
EXCEPTION_ASSERT(!scope.exception() || !success);
if (!success)
return Resolution::error();
continue;
}
const ExportEntry& exportEntry = *optionalExportEntry;
switch (exportEntry.type) {
case ExportEntry::Type::Local: {
ASSERT(!exportEntry.localName.isNull());
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 ExportEntry::Type::Indirect: {
AbstractModuleRecord* importedModuleRecord = moduleRecord->hostResolveImportedModule(globalObject, exportEntry.moduleName);
RETURN_IF_EXCEPTION(scope, Resolution::error());
// When the imported module does not produce any resolved binding, we need to look into the stars in the *current*
// module. To do this, we append the `IndirectFallback` task to the task queue.
pendingTasks.append(Task { query, Type::IndirectFallback });
// And append the new Resolution frame to check the indirect export will be resolved or not.
frames.append(Resolution::notFound());
pendingTasks.append(Task { ResolveQuery(importedModuleRecord, exportEntry.importName), Type::Query });
continue;
}
case ExportEntry::Type::Namespace: {
AbstractModuleRecord* importedModuleRecord = moduleRecord->hostResolveImportedModule(globalObject, exportEntry.moduleName);
RETURN_IF_EXCEPTION(scope, Resolution::error());
Resolution resolution { Resolution::Type::Resolved, importedModuleRecord, vm.propertyNames->starNamespacePrivateName };
// 2. A module that has resolved a module namespace binding is always cacheable.
cacheResolutionForQuery(query, resolution);
if (!mergeToCurrentTop(resolution))
return Resolution::ambiguous();
continue;
}
}
break;
}
case Type::IndirectFallback: {
Resolution resolution = frames.takeLast();
if (resolution.type == Resolution::Type::NotFound) {
// Indirect export entry does not produce any resolved binding.
// So we will investigate the stars.
bool success = resolveNonLocal(task.query);
EXCEPTION_ASSERT(!scope.exception() || !success);
if (!success)
return Resolution::error();
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))
return Resolution::ambiguous();
break;
}
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.
if (!mergeToCurrentTop(resolution))
return Resolution::ambiguous();
break;
}
}
}
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 AbstractModuleRecord::resolveExport(JSGlobalObject* globalObject, const Identifier& exportName) -> Resolution
{
// Look up the cached resolution first before entering the resolving loop, since the loop setup takes some cost.
if (std::optional<Resolution> cachedResolution = tryGetCachedResolution(exportName.impl()))
return *cachedResolution;
return resolveExportImpl(globalObject, ResolveQuery(this, exportName.impl()));
}
static void getExportedNames(JSGlobalObject* globalObject, AbstractModuleRecord* root, IdentifierSet& exportedNames)
{
VM& vm = globalObject->vm();
auto scope = DECLARE_THROW_SCOPE(vm);
UncheckedKeyHashSet<AbstractModuleRecord*> exportStarSet;
Vector<AbstractModuleRecord*, 8> pendingModules;
pendingModules.append(root);
while (!pendingModules.isEmpty()) {
AbstractModuleRecord* moduleRecord = pendingModules.takeLast();
if (exportStarSet.contains(moduleRecord))
continue;
exportStarSet.add(moduleRecord);
for (const auto& pair : moduleRecord->exportEntries()) {
const AbstractModuleRecord::ExportEntry& exportEntry = pair.value;
if (moduleRecord == root || vm.propertyNames->defaultKeyword != exportEntry.exportName)
exportedNames.add(exportEntry.exportName.impl());
}
for (const auto& starModuleName : moduleRecord->starExportEntries()) {
AbstractModuleRecord* requestedModuleRecord = moduleRecord->hostResolveImportedModule(globalObject, Identifier::fromUid(vm, starModuleName.get()));
RETURN_IF_EXCEPTION(scope, void());
pendingModules.append(requestedModuleRecord);
}
}
}
JSModuleNamespaceObject* AbstractModuleRecord::getModuleNamespace(JSGlobalObject* globalObject)
{
VM& vm = globalObject->vm();
auto scope = DECLARE_THROW_SCOPE(vm);
#if ASSERT_ENABLED
if (auto* cyclic = dynamicDowncast<CyclicModuleRecord>(this))
ASSERT(cyclic->status() != CyclicModuleRecord::Status::New && cyclic->status() != CyclicModuleRecord::Status::Unlinked);
#endif
// http://www.ecma-international.org/ecma-262/6.0/#sec-getmodulenamespace
if (m_moduleNamespaceObject)
return m_moduleNamespaceObject.get();
IdentifierSet exportedNames;
getExportedNames(globalObject, this, exportedNames);
RETURN_IF_EXCEPTION(scope, nullptr);
Vector<std::pair<Identifier, Resolution>> resolutions;
for (auto& name : exportedNames) {
Identifier ident = Identifier::fromUid(vm, name.get());
const Resolution resolution = resolveExport(globalObject, ident);
RETURN_IF_EXCEPTION(scope, nullptr);
switch (resolution.type) {
case Resolution::Type::NotFound:
throwSyntaxError(globalObject, scope, makeString("Exported binding name '"_s, StringView(name.get()), "' is not found."_s));
return nullptr;
case Resolution::Type::Error:
throwSyntaxError(globalObject, scope, "Exported binding name 'default' cannot be resolved by star export entries."_s);
return nullptr;
case Resolution::Type::Ambiguous:
break;
case Resolution::Type::Resolved:
resolutions.append({ WTF::move(ident), resolution });
break;
}
}
auto* moduleNamespaceObject = JSModuleNamespaceObject::create(globalObject, globalObject->moduleNamespaceObjectStructure(), this, WTF::move(resolutions));
RETURN_IF_EXCEPTION(scope, nullptr);
// Materialize *namespace* slot with module namespace object unless the module environment is not yet materialized, in which case we'll do it in setModuleEnvironment
if (m_moduleEnvironment) {
bool putResult = false;
constexpr bool shouldThrowReadOnlyError = false;
constexpr bool ignoreReadOnlyErrors = true;
symbolTablePutTouchWatchpointSet(m_moduleEnvironment.get(), globalObject, vm.propertyNames->starNamespacePrivateName, moduleNamespaceObject, shouldThrowReadOnlyError, ignoreReadOnlyErrors, putResult);
RETURN_IF_EXCEPTION(scope, nullptr);
}
m_moduleNamespaceObject.set(vm, this, moduleNamespaceObject);
return moduleNamespaceObject;
}
JSPromise* AbstractModuleRecord::asyncCapability() const
{
return m_asyncCapability.get();
}
void AbstractModuleRecord::asyncCapability(VM& vm, JSPromise* promise)
{
m_asyncCapability.set(vm, this, promise);
}
void AbstractModuleRecord::setModuleEnvironment(JSGlobalObject* globalObject, JSModuleEnvironment* moduleEnvironment)
{
VM& vm = globalObject->vm();
auto scope = DECLARE_THROW_SCOPE(vm);
ASSERT(!m_moduleEnvironment);
// If module namespace object is materialized, we will materialize *namespace* slot too.
if (m_moduleNamespaceObject) {
bool putResult = false;
constexpr bool shouldThrowReadOnlyError = false;
constexpr bool ignoreReadOnlyErrors = true;
symbolTablePutTouchWatchpointSet(moduleEnvironment, globalObject, vm.propertyNames->starNamespacePrivateName, m_moduleNamespaceObject.get(), shouldThrowReadOnlyError, ignoreReadOnlyErrors, putResult);
RETURN_IF_EXCEPTION(scope, void());
}
m_moduleEnvironment.set(vm, this, moduleEnvironment);
}
void AbstractModuleRecord::link(JSGlobalObject* globalObject, JSValue scriptFetcher)
{
if (auto* cyclicModuleRecord = dynamicDowncast<CyclicModuleRecord>(this))
cyclicModuleRecord->link(globalObject, scriptFetcher); // can throw
else if (auto* moduleRecord = dynamicDowncast<SyntheticModuleRecord>(this))
moduleRecord->link(globalObject, scriptFetcher);
else
RELEASE_ASSERT_NOT_REACHED();
}
JS_EXPORT_PRIVATE JSValue AbstractModuleRecord::evaluate(JSGlobalObject* globalObject, JSValue sentValue, JSValue resumeMode)
{
VM& vm = globalObject->vm();
auto scope = DECLARE_THROW_SCOPE(vm);
if (auto* jsModuleRecord = dynamicDowncast<JSModuleRecord>(this))
RELEASE_AND_RETURN(scope, jsModuleRecord->evaluate(globalObject, sentValue, resumeMode));
#if ENABLE(WEBASSEMBLY)
if (auto* wasmModuleRecord = dynamicDowncast<WebAssemblyModuleRecord>(this)) {
// WebAssembly imports need to be supplied during evaluation so that, e.g.,
// JS module exports are actually available to be read and installed as import
// bindings.
wasmModuleRecord->initializeImports(globalObject, nullptr, Wasm::CreationMode::FromModuleLoader);
RETURN_IF_EXCEPTION(scope, jsUndefined());
wasmModuleRecord->initializeExports(globalObject);
RETURN_IF_EXCEPTION(scope, jsUndefined());
RELEASE_AND_RETURN(scope, wasmModuleRecord->evaluate(globalObject));
}
#endif
if (auto* syntheticRecord = dynamicDowncast<SyntheticModuleRecord>(this))
RELEASE_AND_RETURN(scope, syntheticRecord->evaluate(globalObject));
RELEASE_ASSERT_NOT_REACHED();
return jsUndefined();
}
JSPromise* AbstractModuleRecord::evaluate(JSGlobalObject* globalObject)
{
VM& vm = globalObject->vm();
auto wrap = [&](JSValue value) -> JSPromise* {
if (!value)
return nullptr;
if (auto* promise = dynamicDowncast<JSPromise>(value))
return promise;
auto* promise = JSPromise::create(vm, globalObject->promiseStructure());
promise->resolve(globalObject, vm, value);
return promise;
};
if (auto* cyclicRecord = dynamicDowncast<CyclicModuleRecord>(this))
return wrap(cyclicRecord->evaluate(globalObject));
if (auto* syntheticRecord = dynamicDowncast<SyntheticModuleRecord>(this))
return wrap(syntheticRecord->evaluate(globalObject));
RELEASE_ASSERT_NOT_REACHED();
return nullptr;
}
void AbstractModuleRecord::evaluateModuleSync(JSGlobalObject* globalObject)
{
// EvaluateModuleSync(module)
// https://tc39.es/ecma262/#sec-EvaluateModuleSync
VM& vm = globalObject->vm();
auto scope = DECLARE_THROW_SCOPE(vm);
ASSERT(!inherits(JSModuleRecord::info()));
JSPromise* promise = evaluate(globalObject);
RETURN_IF_EXCEPTION(scope, void());
// "the caller guarantees that module's evaluation will return an already settled promise"
ASSERT(promise->status() != JSPromise::Status::Pending);
if (promise->status() == JSPromise::Status::Rejected)
throwException(globalObject, scope, promise->result());
}
static void checkSafeToRecurse(JSGlobalObject* globalObject, ThrowScope& scope)
{
if (!globalObject->vm().isSafeToRecurse())
throwRangeError(globalObject, scope, "Maximum call stack size exceeded"_s);
}
unsigned AbstractModuleRecord::innerModuleEvaluation(JSGlobalObject* globalObject, Vector<AbstractModuleRecord*, 8>& stack, unsigned index)
{
// InnerModuleEvaluation(module, stack, index)
// https://tc39.es/ecma262/#sec-innermoduleevaluation
constexpr auto invalid = static_cast<unsigned>(-1);
using Status = CyclicModuleRecord::Status;
VM& vm = globalObject->vm();
auto scope = DECLARE_THROW_SCOPE(vm);
auto* module = dynamicDowncast<CyclicModuleRecord>(this);
// 1. If module is not a Cyclic Module Record, then
if (!module) {
// 1.a. Perform ? EvaluateModuleSync(module).
evaluateModuleSync(globalObject);
RETURN_IF_EXCEPTION(scope, invalid);
// 1.b. Return index.
return index;
}
// 2. If module.[[Status]] is either EVALUATING-ASYNC or EVALUATED, then
if (auto status = module->status(); status == Status::EvaluatingAsync || status == Status::Evaluated) {
// 2.a. If module.[[EvaluationError]] is EMPTY, return index.
JSValue evaluationError = module->evaluationError();
if (!evaluationError)
RELEASE_AND_RETURN(scope, index);
// 2.b. Otherwise, return ? module.[[EvaluationError]].
scope.throwException(globalObject, evaluationError);
return invalid;
}
// 3. If module.[[Status]] is EVALUATING, return index.
if (module->status() == Status::Evaluating)
RELEASE_AND_RETURN(scope, index);
// 4. Assert: module.[[Status]] is LINKED.
ASSERT(module->status() == Status::Linked);
// 5. Set module.[[Status]] to EVALUATING.
module->status(Status::Evaluating);
// 6. Let moduleIndex be index.
unsigned moduleIndex = index;