LibJS: Refactor interpreter to use Script and Source Text Modules

This also refactors interpreter creation to follow
InitializeHostDefinedRealm, but I couldn't fit it in the title :^)

This allows us to follow the spec much more closely rather than being
completely ad-hoc with just the parse node instead of having all the
surrounding data such as the realm of the parse node.

The interpreter creation refactor creates the global execution context
once and doesn't take it off the stack. This allows LibWeb to take the
global execution context and manually handle it, following the HTML
spec. The HTML spec calls this the "realm execution context" of the
environment settings object.

It also allows us to specify the globalThis type, as it can be
different from the global object type. For example, on the web, Window
global objects use a WindowProxy global this value to enforce the same
origin policy on operations like [[GetOwnProperty]].

Finally, it allows us to directly call Program::execute in perform_eval
and perform_shadow_realm_eval as this moves
global_declaration_instantiation into Interpreter::run
(ScriptEvaluation) as per the spec.

Note that this doesn't evalulate Source Text Modules yet or refactor
the bytecode interpreter, that's work for future us :^)

This patch was originally build by Luke for the environment settings
object change but was also needed for modules. So I (davidot) have
modified it with the new completion changes and setup for that.

Co-authored-by: davidot <davidot@serenityos.org>

20 files changed, 293 insertions, 129 deletions

diff --git a/Meta/Lagom/Fuzzers/FuzzJs.cpp b/Meta/Lagom/Fuzzers/FuzzJs.cpp
index 19dcb8a404..b10b03a54a 100644
--- a/Meta/Lagom/Fuzzers/FuzzJs.cpp
+++ b/Meta/Lagom/Fuzzers/FuzzJs.cpp
@@ -1,27 +1,25 @@
 /*
  * Copyright (c) 2020, the SerenityOS developers.
+ * Copyright (c) 2022, Luke Wilde <lukew@serenityos.org>
  *
  * SPDX-License-Identifier: BSD-2-Clause
  */
 
 #include <AK/StringView.h>
 #include <LibJS/Interpreter.h>
-#include <LibJS/Lexer.h>
-#include <LibJS/Parser.h>
 #include <LibJS/Runtime/GlobalObject.h>
+#include <LibJS/Script.h>
 #include <stddef.h>
 #include <stdint.h>
 
 extern "C" int LLVMFuzzerTestOneInput(const uint8_t* data, size_t size)
 {
     auto js = StringView(static_cast<const unsigned char*>(data), size);
-    auto lexer = JS::Lexer(js);
-    auto parser = JS::Parser(lexer);
-    auto program = parser.parse_program();
-    if (!parser.has_errors()) {
-        auto vm = JS::VM::create();
-        auto interpreter = JS::Interpreter::create<JS::GlobalObject>(*vm);
-        (void)interpreter->run(interpreter->global_object(), *program);
-    }
+    auto vm = JS::VM::create();
+    auto interpreter = JS::Interpreter::create<JS::GlobalObject>(*vm);
+    auto parse_result = JS::Script::parse(js, interpreter->realm());
+    if (!parse_result.is_error())
+        (void)interpreter->run(parse_result.value());
+
     return 0;
 }
diff --git a/Meta/Lagom/Fuzzers/FuzzilliJs.cpp b/Meta/Lagom/Fuzzers/FuzzilliJs.cpp
index 530e570601..e5190b310c 100644
--- a/Meta/Lagom/Fuzzers/FuzzilliJs.cpp
+++ b/Meta/Lagom/Fuzzers/FuzzilliJs.cpp
@@ -207,13 +207,11 @@ int main(int, char**)
 
         auto js = StringView(static_cast<const unsigned char*>(data_buffer.data()), script_size);
 
-        auto lexer = JS::Lexer(js);
-        auto parser = JS::Parser(lexer);
-        auto program = parser.parse_program();
-        if (parser.has_errors()) {
+        auto parse_result = JS::Script::parse(js, interpreter->realm());
+        if (parse_result.is_error()) {
             result = 1;
         } else {
-            auto completion = interpreter->run(interpreter->global_object(), *program);
+            auto completion = interpreter->run(parse_result.value());
             if (completion.is_error()) {
                 result = 1;
                 vm->clear_exception();
diff --git a/Userland/Applications/Assistant/Providers.cpp b/Userland/Applications/Assistant/Providers.cpp
index f2a8c590ea..767432a56a 100644
--- a/Userland/Applications/Assistant/Providers.cpp
+++ b/Userland/Applications/Assistant/Providers.cpp
@@ -16,9 +16,8 @@
 #include <LibGUI/Clipboard.h>
 #include <LibGUI/FileIconProvider.h>
 #include <LibJS/Interpreter.h>
-#include <LibJS/Lexer.h>
-#include <LibJS/Parser.h>
 #include <LibJS/Runtime/GlobalObject.h>
+#include <LibJS/Script.h>
 #include <errno.h>
 #include <fcntl.h>
 #include <serenity.h>
@@ -93,12 +92,11 @@ void CalculatorProvider::query(String const& query, Function<void(NonnullRefPtrV
     auto interpreter = JS::Interpreter::create<JS::GlobalObject>(*vm);
 
     auto source_code = query.substring(1);
-    auto parser = JS::Parser(JS::Lexer(source_code));
-    auto program = parser.parse_program();
-    if (parser.has_errors())
+    auto parse_result = JS::Script::parse(source_code, interpreter->realm());
+    if (parse_result.is_error())
         return;
 
-    auto completion = interpreter->run(interpreter->global_object(), *program);
+    auto completion = interpreter->run(parse_result.value());
     if (completion.is_error())
         return;
 
diff --git a/Userland/Applications/Spreadsheet/JSIntegration.cpp b/Userland/Applications/Spreadsheet/JSIntegration.cpp
index a14d4d7fd9..5ddc2ffb46 100644
--- a/Userland/Applications/Spreadsheet/JSIntegration.cpp
+++ b/Userland/Applications/Spreadsheet/JSIntegration.cpp
@@ -355,8 +355,8 @@ JS_DEFINE_NATIVE_FUNCTION(SheetGlobalObject::get_column_bound)
     return JS::Value(bounds.row);
 }
 
-WorkbookObject::WorkbookObject(Workbook& workbook)
-    : JS::Object(*JS::Object::create(workbook.vm().interpreter().global_object(), workbook.vm().interpreter().global_object().object_prototype()))
+WorkbookObject::WorkbookObject(Workbook& workbook, JS::GlobalObject& global_object)
+    : JS::Object(*JS::Object::create(global_object, global_object.object_prototype()))
     , m_workbook(workbook)
 {
 }
diff --git a/Userland/Applications/Spreadsheet/JSIntegration.h b/Userland/Applications/Spreadsheet/JSIntegration.h
index 24ed2e8bd7..67eb5fcec5 100644
--- a/Userland/Applications/Spreadsheet/JSIntegration.h
+++ b/Userland/Applications/Spreadsheet/JSIntegration.h
@@ -49,7 +49,7 @@ class WorkbookObject final : public JS::Object {
     JS_OBJECT(WorkbookObject, JS::Object);
 
 public:
-    WorkbookObject(Workbook&);
+    WorkbookObject(Workbook&, JS::GlobalObject&);
 
     virtual ~WorkbookObject() override;
 
diff --git a/Userland/Applications/Spreadsheet/Spreadsheet.cpp b/Userland/Applications/Spreadsheet/Spreadsheet.cpp
index 6e60d5afef..a514921805 100644
--- a/Userland/Applications/Spreadsheet/Spreadsheet.cpp
+++ b/Userland/Applications/Spreadsheet/Spreadsheet.cpp
@@ -47,15 +47,19 @@ Sheet::Sheet(Workbook& workbook)
     global_object().define_direct_property("thisSheet", &global_object(), JS::default_attributes); // Self-reference is unfortunate, but required.
 
     // Sadly, these have to be evaluated once per sheet.
-    auto file_or_error = Core::File::open("/res/js/Spreadsheet/runtime.js", Core::OpenMode::ReadOnly);
+    constexpr StringView runtime_file_path = "/res/js/Spreadsheet/runtime.js";
+    auto file_or_error = Core::File::open(runtime_file_path, Core::OpenMode::ReadOnly);
     if (!file_or_error.is_error()) {
         auto buffer = file_or_error.value()->read_all();
-        JS::Parser parser { JS::Lexer(buffer) };
-        if (parser.has_errors()) {
+        auto script_or_error = JS::Script::parse(buffer, interpreter().realm(), runtime_file_path);
+        if (script_or_error.is_error()) {
             warnln("Spreadsheet: Failed to parse runtime code");
-            parser.print_errors();
+            for (auto& error : script_or_error.error()) {
+                // FIXME: This doesn't print hints anymore
+                warnln("SyntaxError: {}", error.to_string());
+            }
         } else {
-            (void)interpreter().run(global_object(), parser.parse_program());
+            (void)interpreter().run(script_or_error.value());
             if (auto* exception = interpreter().exception()) {
                 warnln("Spreadsheet: Failed to run runtime code:");
                 for (auto& traceback_frame : exception->traceback()) {
@@ -159,14 +163,14 @@ Sheet::ValueAndException Sheet::evaluate(StringView source, Cell* on_behalf_of)
     TemporaryChange cell_change { m_current_cell_being_evaluated, on_behalf_of };
     ScopeGuard clear_exception { [&] { interpreter().vm().clear_exception(); } };
 
-    auto parser = JS::Parser(JS::Lexer(source));
-    auto program = parser.parse_program();
-    if (parser.has_errors() || interpreter().exception())
+    auto script_or_error = JS::Script::parse(source, interpreter().realm());
+    // FIXME: Convert parser errors to exceptions to show them to the user.
+    if (script_or_error.is_error() || interpreter().exception())
         return { JS::js_undefined(), interpreter().exception() };
 
-    auto result = interpreter().run(global_object(), program);
+    auto result = interpreter().run(script_or_error.value());
     if (result.is_error()) {
-        auto exc = interpreter().exception();
+        auto* exc = interpreter().exception();
         return { JS::js_undefined(), exc };
     }
     return { result.value(), {} };
diff --git a/Userland/Applications/Spreadsheet/Workbook.cpp b/Userland/Applications/Spreadsheet/Workbook.cpp
index c79b872119..cf27699373 100644
--- a/Userland/Applications/Spreadsheet/Workbook.cpp
+++ b/Userland/Applications/Spreadsheet/Workbook.cpp
@@ -29,7 +29,7 @@ Workbook::Workbook(NonnullRefPtrVector<Sheet>&& sheets, GUI::Window& parent_wind
     , m_main_execution_context(m_vm->heap())
     , m_parent_window(parent_window)
 {
-    m_workbook_object = m_vm->heap().allocate<WorkbookObject>(m_interpreter->global_object(), *this);
+    m_workbook_object = m_vm->heap().allocate<WorkbookObject>(m_interpreter->global_object(), *this, m_interpreter->global_object());
     m_interpreter->global_object().define_direct_property("workbook", workbook_object(), JS::default_attributes);
 
     m_main_execution_context.current_node = nullptr;
diff --git a/Userland/DevTools/HackStudio/Debugger/EvaluateExpressionDialog.cpp b/Userland/DevTools/HackStudio/Debugger/EvaluateExpressionDialog.cpp
index 30df8d7398..42cd2a3192 100644
--- a/Userland/DevTools/HackStudio/Debugger/EvaluateExpressionDialog.cpp
+++ b/Userland/DevTools/HackStudio/Debugger/EvaluateExpressionDialog.cpp
@@ -108,19 +108,18 @@ void EvaluateExpressionDialog::handle_evaluation(const String& expression)
     m_output_container->remove_all_children();
     m_output_view->update();
 
-    auto parser = JS::Parser(JS::Lexer(expression));
-    auto program = parser.parse_program();
+    auto script_or_error = JS::Script::parse(expression, m_interpreter->realm());
 
     StringBuilder output_html;
     auto result = JS::ThrowCompletionOr<JS::Value> { JS::js_undefined() };
-    if (parser.has_errors()) {
-        auto error = parser.errors()[0];
+    if (script_or_error.is_error()) {
+        auto error = script_or_error.error()[0];
         auto hint = error.source_location_hint(expression);
         if (!hint.is_empty())
             output_html.append(String::formatted("<pre>{}</pre>", escape_html_entities(hint)));
         result = m_interpreter->vm().throw_completion<JS::SyntaxError>(m_interpreter->global_object(), error.to_string());
     } else {
-        result = m_interpreter->run(m_interpreter->global_object(), *program);
+        result = m_interpreter->run(script_or_error.value());
     }
 
     if (result.is_error()) {
diff --git a/Userland/Libraries/LibJS/AST.cpp b/Userland/Libraries/LibJS/AST.cpp
index 48e56eae39..461613fdb9 100644
--- a/Userland/Libraries/LibJS/AST.cpp
+++ b/Userland/Libraries/LibJS/AST.cpp
@@ -243,16 +243,8 @@ Completion BlockStatement::execute(Interpreter& interpreter, GlobalObject& globa
 
 Completion Program::execute(Interpreter& interpreter, GlobalObject& global_object) const
 {
-    // FIXME: This tries to be "ScriptEvaluation" and "evaluating scriptBody" at once. It shouldn't.
-    //        Clean this up and update perform_eval() / perform_shadow_realm_eval()
-
     InterpreterNodeScope node_scope { interpreter, *this };
 
-    VERIFY(interpreter.lexical_environment() && interpreter.lexical_environment()->is_global_environment());
-    auto& global_env = static_cast<GlobalEnvironment&>(*interpreter.lexical_environment());
-
-    TRY(global_declaration_instantiation(interpreter, global_object, global_env));
-
     return evaluate_statements(interpreter, global_object);
 }
 
diff --git a/Userland/Libraries/LibJS/Interpreter.cpp b/Userland/Libraries/LibJS/Interpreter.cpp
index 18d5034918..af08e232c1 100644
--- a/Userland/Libraries/LibJS/Interpreter.cpp
+++ b/Userland/Libraries/LibJS/Interpreter.cpp
@@ -1,6 +1,7 @@
 /*
  * Copyright (c) 2020, Andreas Kling <kling@serenityos.org>
  * Copyright (c) 2020-2021, Linus Groh <linusg@serenityos.org>
+ * Copyright (c) 2022, Luke Wilde <lukew@serenityos.org>
  *
  * SPDX-License-Identifier: BSD-2-Clause
  */
@@ -31,6 +32,7 @@ NonnullOwnPtr<Interpreter> Interpreter::create_with_existing_realm(Realm& realm)
 
 Interpreter::Interpreter(VM& vm)
     : m_vm(vm)
+    , m_global_execution_context(vm.heap())
 {
 }
 
@@ -38,42 +40,100 @@ Interpreter::~Interpreter()
 {
 }
 
-ThrowCompletionOr<Value> Interpreter::run(GlobalObject& global_object, const Program& program)
+// 16.1.6 ScriptEvaluation ( scriptRecord ), https://tc39.es/ecma262/#sec-runtime-semantics-scriptevaluation
+ThrowCompletionOr<Value> Interpreter::run(Script& script_record)
 {
-    // FIXME: Why does this receive a GlobalObject? Interpreter has one already, and this might not be in sync with the Realm's GlobalObject.
-
     auto& vm = this->vm();
     VERIFY(!vm.exception());
 
     VM::InterpreterExecutionScope scope(*this);
 
-    ExecutionContext execution_context(heap());
-    execution_context.current_node = &program;
-    execution_context.this_value = &global_object;
-    static FlyString global_execution_context_name = "(global execution context)";
-    execution_context.function_name = global_execution_context_name;
-    execution_context.lexical_environment = &realm().global_environment();
-    execution_context.variable_environment = &realm().global_environment();
-    execution_context.realm = &realm();
-    execution_context.is_strict_mode = program.is_strict_mode();
-    MUST(vm.push_execution_context(execution_context, global_object));
-    auto completion = program.execute(*this, global_object);
+    // 1. Let globalEnv be scriptRecord.[[Realm]].[[GlobalEnv]].
+    auto& global_environment = script_record.realm().global_environment();
+
+    // NOTE: This isn't in the spec but we require it.
+    auto& global_object = script_record.realm().global_object();
+
+    // 2. Let scriptContext be a new ECMAScript code execution context.
+    ExecutionContext script_context(vm.heap());
+
+    // 3. Set the Function of scriptContext to null. (This was done in the construction of script_context)
+
+    // 4. Set the Realm of scriptContext to scriptRecord.[[Realm]].
+    script_context.realm = &script_record.realm();
+
+    // FIXME: 5. Set the ScriptOrModule of scriptContext to scriptRecord.
+
+    // 6. Set the VariableEnvironment of scriptContext to globalEnv.
+    script_context.variable_environment = &global_environment;
+
+    // 7. Set the LexicalEnvironment of scriptContext to globalEnv.
+    script_context.lexical_environment = &global_environment;
+
+    // 8. Set the PrivateEnvironment of scriptContext to null.
+
+    // NOTE: This isn't in the spec, but we require it.
+    script_context.is_strict_mode = script_record.parse_node().is_strict_mode();
+
+    // FIXME: 9. Suspend the currently running execution context.
+
+    // 10. Push scriptContext onto the execution context stack; scriptContext is now the running execution context.
+    vm.push_execution_context(script_context, global_object);
+
+    // 11. Let scriptBody be scriptRecord.[[ECMAScriptCode]].
+    auto& script_body = script_record.parse_node();
+
+    // 12. Let result be GlobalDeclarationInstantiation(scriptBody, globalEnv).
+    auto instantiation_result = script_body.global_declaration_instantiation(*this, global_object, global_environment);
+    Completion result = instantiation_result.is_throw_completion() ? instantiation_result.throw_completion() : normal_completion({});
+
+    // 13. If result.[[Type]] is normal, then
+    if (result.type() == Completion::Type::Normal) {
+        // a. Set result to the result of evaluating scriptBody.
+        result = script_body.execute(*this, global_object);
+    }
+
+    // 14. If result.[[Type]] is normal and result.[[Value]] is empty, then
+    if (result.type() == Completion::Type::Normal && !result.value().has_value()) {
+        // a. Set result to NormalCompletion(undefined).
+        result = normal_completion(js_undefined());
+    }
+
+    // FIXME: 15. Suspend scriptContext and remove it from the execution context stack.
+    vm.pop_execution_context();
+
+    // 16. Assert: The execution context stack is not empty.
+    VERIFY(!vm.execution_context_stack().is_empty());
+
+    // FIXME: 17. Resume the context that is now on the top of the execution context stack as the running execution context.
 
     // At this point we may have already run any queued promise jobs via on_call_stack_emptied,
     // in which case this is a no-op.
+    // FIXME: These three should be moved out of Interpreter::run and give the host an option to run these, as it's up to the host when these get run.
+    //        https://tc39.es/ecma262/#sec-jobs for jobs and https://tc39.es/ecma262/#_ref_3508 for ClearKeptObjects
+    //        finish_execution_generation is particularly an issue for LibWeb, as the HTML spec wants to run it specifically after performing a microtask checkpoint.
+    //        The promise and registry cleanup queues don't cause LibWeb an issue, as LibWeb overrides the hooks that push onto these queues.
     vm.run_queued_promise_jobs();
 
     vm.run_queued_finalization_registry_cleanup_jobs();
 
-    vm.pop_execution_context();
-
     vm.finish_execution_generation();
 
-    if (completion.is_abrupt()) {
-        VERIFY(completion.type() == Completion::Type::Throw);
-        return completion.release_error();
+    // 18. Return Completion(result).
+    if (result.is_abrupt()) {
+        VERIFY(result.type() == Completion::Type::Throw);
+        return result.release_error();
     }
-    return completion.value().value_or(js_undefined());
+
+    VERIFY(result.value().has_value());
+    return *result.value();
+}
+
+ThrowCompletionOr<Value> Interpreter::run(SourceTextModule&)
+{
+    auto* error = InternalError::create(global_object(), "Can't run modules directly yet :^(");
+    vm().throw_exception(global_object(), Value { error });
+    return throw_completion(error);
 }
 
 GlobalObject& Interpreter::global_object()
diff --git a/Userland/Libraries/LibJS/Interpreter.h b/Userland/Libraries/LibJS/Interpreter.h
index 868cc423c1..aae9e76bc2 100644
--- a/Userland/Libraries/LibJS/Interpreter.h
+++ b/Userland/Libraries/LibJS/Interpreter.h
@@ -1,5 +1,6 @@
 /*
  * Copyright (c) 2020, Andreas Kling <kling@serenityos.org>
+ * Copyright (c) 2022, Luke Wilde <lukew@serenityos.org>
  *
  * SPDX-License-Identifier: BSD-2-Clause
  */
@@ -19,11 +20,14 @@
 #include <LibJS/Runtime/DeclarativeEnvironment.h>
 #include <LibJS/Runtime/ErrorTypes.h>
 #include <LibJS/Runtime/Exception.h>
+#include <LibJS/Runtime/GlobalEnvironment.h>
 #include <LibJS/Runtime/GlobalObject.h>
 #include <LibJS/Runtime/MarkedValueList.h>
 #include <LibJS/Runtime/Realm.h>
 #include <LibJS/Runtime/VM.h>
 #include <LibJS/Runtime/Value.h>
+#include <LibJS/Script.h>
+#include <LibJS/SourceTextModule.h>
 
 namespace JS {
 
@@ -34,26 +38,75 @@ struct ExecutingASTNodeChain {
 
 class Interpreter : public Weakable<Interpreter> {
 public:
-    template<typename GlobalObjectType, typename... Args>
-    static NonnullOwnPtr<Interpreter> create(VM& vm, Args&&... args)
+    // 9.6 InitializeHostDefinedRealm ( ), https://tc39.es/ecma262/#sec-initializehostdefinedrealm
+    template<typename GlobalObjectType, typename GlobalThisObjectType, typename... Args>
+    static NonnullOwnPtr<Interpreter> create(VM& vm, Args&&... args) requires(IsBaseOf<GlobalObject, GlobalObjectType>&& IsBaseOf<Object, GlobalThisObjectType>)
     {
         DeferGC defer_gc(vm.heap());
         auto interpreter = adopt_own(*new Interpreter(vm));
         VM::InterpreterExecutionScope scope(*interpreter);
-        auto* global_object = static_cast<GlobalObject*>(interpreter->heap().allocate_without_global_object<GlobalObjectType>(forward<Args>(args)...));
+
+        // 1. Let realm be CreateRealm().
         auto* realm = Realm::create(vm);
-        realm->set_global_object(*global_object, global_object);
+
+        // 2. Let newContext be a new execution context. (This was done in the Interpreter constructor)
+
+        // 3. Set the Function of newContext to null. (This is done for us when the execution context is constructed)
+
+        // 4. Set the Realm of newContext to realm.
+        interpreter->m_global_execution_context.realm = realm;
+
+        // 5. Set the ScriptOrModule of newContext to null. (This was done during execution context construction)
+
+        // 7. If the host requires use of an exotic object to serve as realm's global object, let global be such an object created in a host-defined manner.
+        //    Otherwise, let global be undefined, indicating that an ordinary object should be created as the global object.
+        auto* global_object = static_cast<GlobalObject*>(interpreter->heap().allocate_without_global_object<GlobalObjectType>(forward<Args>(args)...));
+
+        // 6. Push newContext onto the execution context stack; newContext is now the running execution context.
+        //    NOTE: This is out of order from the spec, but it shouldn't matter here.
+        vm.push_execution_context(interpreter->m_global_execution_context, *global_object);
+
+        // 8. If the host requires that the this binding in realm's global scope return an object other than the global object, let thisValue be such an object created
+        //    in a host-defined manner. Otherwise, let thisValue be undefined, indicating that realm's global this binding should be the global object.
+        if constexpr (IsSame<GlobalObjectType, GlobalThisObjectType>) {
+            // 9. Perform SetRealmGlobalObject(realm, global, thisValue).
+            realm->set_global_object(*global_object, global_object);
+        } else {
+            // FIXME: Should we pass args in here? Let's er on the side of caution and say yes.
+            auto* global_this_value = static_cast<Object*>(interpreter->heap().allocate_without_global_object<GlobalThisObjectType>(forward<Args>(args)...));
+
+            // 9. Perform SetRealmGlobalObject(realm, global, thisValue).
+            realm->set_global_object(*global_object, global_this_value);
+        }
+
+        // NOTE: These are not in the spec.
+        static FlyString global_execution_context_name = "(global execution context)";
+        interpreter->m_global_execution_context.function_name = global_execution_context_name;
+
         interpreter->m_global_object = make_handle(global_object);
         interpreter->m_realm = make_handle(realm);
+
+        // 10. Let globalObj be ? SetDefaultGlobalBindings(realm).
+        // 11. Create any host-defined global object properties on globalObj.
         static_cast<GlobalObjectType*>(global_object)->initialize_global_object();
+
+        // 12. Return NormalCompletion(empty).
         return interpreter;
     }
 
+    template<typename GlobalObjectType, typename... Args>
+    static NonnullOwnPtr<Interpreter> create(VM& vm, Args&&... args) requires IsBaseOf<GlobalObject, GlobalObjectType>
+    {
+        // NOTE: This function is here to facilitate step 8 of InitializeHostDefinedRealm. (Callers don't have to specify the same type twice if not necessary)
+        return create<GlobalObjectType, GlobalObjectType>(vm, args...);
+    }
+
     static NonnullOwnPtr<Interpreter> create_with_existing_realm(Realm&);
 
     ~Interpreter();
 
-    ThrowCompletionOr<Value> run(GlobalObject&, const Program&);
+    ThrowCompletionOr<Value> run(Script&);
+    ThrowCompletionOr<Value> run(SourceTextModule&);
 
     GlobalObject& global_object();
     const GlobalObject& global_object() const;
@@ -91,6 +144,9 @@ private:
 
     Handle<GlobalObject> m_global_object;
     Handle<Realm> m_realm;
+
+    // This is here to keep the global execution context alive for the entire lifespan of the Interpreter.
+    ExecutionContext m_global_execution_context;
 };
 
 }
diff --git a/Userland/Libraries/LibJS/Runtime/AbstractOperations.cpp b/Userland/Libraries/LibJS/Runtime/AbstractOperations.cpp
index 696284d27f..3dc90bc7e4 100644
--- a/Userland/Libraries/LibJS/Runtime/AbstractOperations.cpp
+++ b/Userland/Libraries/LibJS/Runtime/AbstractOperations.cpp
@@ -577,8 +577,7 @@ ThrowCompletionOr<Value> perform_eval(Value x, GlobalObject& caller_realm, Calle
             eval_result = {};
     } else {
         auto& ast_interpreter = vm.interpreter();
-        // FIXME: We need to use evaluate_statements() here because Program::execute() calls global_declaration_instantiation() when it shouldn't
-        eval_result = TRY(program->evaluate_statements(ast_interpreter, caller_realm));
+        eval_result = TRY(program->execute(ast_interpreter, caller_realm));
     }
 
     return eval_result.value_or(js_undefined());
diff --git a/Userland/Libraries/LibJS/Runtime/ShadowRealm.cpp b/Userland/Libraries/LibJS/Runtime/ShadowRealm.cpp
index 2022265c21..211a842e9d 100644
--- a/Userland/Libraries/LibJS/Runtime/ShadowRealm.cpp
+++ b/Userland/Libraries/LibJS/Runtime/ShadowRealm.cpp
@@ -115,9 +115,8 @@ ThrowCompletionOr<Value> perform_shadow_realm_eval(GlobalObject& global_object,
     // 20. If result.[[Type]] is normal, then
     if (!eval_result.is_throw_completion()) {
         // TODO: Optionally use bytecode interpreter?
-        // FIXME: We need to use evaluate_statements() here because Program::execute() calls global_declaration_instantiation() when it shouldn't
         // a. Set result to the result of evaluating body.
-        result = program->evaluate_statements(vm.interpreter(), eval_realm.global_object());
+        result = program->execute(vm.interpreter(), eval_realm.global_object());
     }
 
     // 21. If result.[[Type]] is normal and result.[[Value]] is empty, then
diff --git a/Userland/Libraries/LibJS/SourceTextModule.h b/Userland/Libraries/LibJS/SourceTextModule.h
index ac3cba673f..c318e721f5 100644
--- a/Userland/Libraries/LibJS/SourceTextModule.h
+++ b/Userland/Libraries/LibJS/SourceTextModule.h
@@ -19,6 +19,8 @@ public:
     static Result<NonnullRefPtr<SourceTextModule>, Vector<Parser::Error>> parse(StringView source_text, Realm&, StringView filename = {});
     virtual ~SourceTextModule();
 
+    Program const& parse_node() const { return *m_ecmascript_code; }
+
 private:
     explicit SourceTextModule(Realm&, NonnullRefPtr<Program>);
 
diff --git a/Userland/Libraries/LibTest/JavaScriptTestRunner.h b/Userland/Libraries/LibTest/JavaScriptTestRunner.h
index b1f4454d2b..b24f7b9b53 100644
--- a/Userland/Libraries/LibTest/JavaScriptTestRunner.h
+++ b/Userland/Libraries/LibTest/JavaScriptTestRunner.h
@@ -175,7 +175,6 @@ protected:
     void print_file_result(const JSFileResult& file_result) const;
 
     String m_common_path;
-    RefPtr<JS::Script> m_test_script;
 };
 
 class TestRunnerGlobalObject final : public JS::GlobalObject {
@@ -279,6 +278,14 @@ inline JSFileResult TestRunner::run_file_test(const String& test_path)
     double start_time = get_time_in_ms();
     auto interpreter = JS::Interpreter::create<TestRunnerGlobalObject>(*g_vm);
 
+    // Since g_vm is reused for each new interpreter, Interpreter::create will end up pushing multiple
+    // global execution contexts onto the VM's execution context stack. To prevent this, we immediately
+    // pop the global execution context off the execution context stack and manually handle pushing
+    // and popping it. Since the global execution context should be the only thing on the stack
+    // at interpreter creation, let's assert there is only one.
+    VERIFY(g_vm->execution_context_stack().size() == 1);
+    auto& global_execution_context = *g_vm->execution_context_stack().take_first();
+
     // FIXME: This is a hack while we're refactoring Interpreter/VM stuff.
     JS::VM::InterpreterExecutionScope scope(*interpreter);
 
@@ -323,26 +330,28 @@ inline JSFileResult TestRunner::run_file_test(const String& test_path)
         }
     }
 
-    if (!m_test_script) {
-        auto result = parse_script(m_common_path, interpreter->realm());
-        if (result.is_error()) {
-            warnln("Unable to parse test-common.js");
-            warnln("{}", result.error().error.to_string());
-            warnln("{}", result.error().hint);
-            cleanup_and_exit();
-        }
-        m_test_script = result.release_value();
+    // FIXME: Since a new interpreter is created every time with a new realm, we no longer cache the test-common.js file as scripts are parsed for the current realm only.
+    //        Find a way to cache this.
+    auto result = parse_script(m_common_path, interpreter->realm());
+    if (result.is_error()) {
+        warnln("Unable to parse test-common.js");
+        warnln("{}", result.error().error.to_string());
+        warnln("{}", result.error().hint);
+        cleanup_and_exit();
     }
+    auto test_script = result.release_value();
 
     if (g_run_bytecode) {
-        auto executable = JS::Bytecode::Generator::generate(m_test_script->parse_node());
+        auto executable = JS::Bytecode::Generator::generate(test_script->parse_node());
         executable.name = test_path;
         if (JS::Bytecode::g_dump_bytecode)
             executable.dump();
         JS::Bytecode::Interpreter bytecode_interpreter(interpreter->global_object(), interpreter->realm());
         MUST(bytecode_interpreter.run(executable));
     } else {
-        MUST(interpreter->run(interpreter->global_object(), m_test_script->parse_node()));
+        g_vm->push_execution_context(global_execution_context, interpreter->global_object());
+        MUST(interpreter->run(*test_script));
+        g_vm->pop_execution_context();
     }
 
     auto file_script = parse_script(test_path, interpreter->realm());
@@ -356,7 +365,9 @@ inline JSFileResult TestRunner::run_file_test(const String& test_path)
         JS::Bytecode::Interpreter bytecode_interpreter(interpreter->global_object(), interpreter->realm());
         (void)bytecode_interpreter.run(executable);
     } else {
-        (void)interpreter->run(interpreter->global_object(), file_script.value()->parse_node());
+        g_vm->push_execution_context(global_execution_context, interpreter->global_object());
+        (void)interpreter->run(file_script.value());
+        g_vm->pop_execution_context();
     }
 
     if (g_vm->exception())
diff --git a/Userland/Libraries/LibWeb/DOM/Document.cpp b/Userland/Libraries/LibWeb/DOM/Document.cpp
index 170c0a2e7b..f47bca16cb 100644
--- a/Userland/Libraries/LibWeb/DOM/Document.cpp
+++ b/Userland/Libraries/LibWeb/DOM/Document.cpp
@@ -679,15 +679,17 @@ JS::Interpreter& Document::interpreter()
 
 JS::Value Document::run_javascript(StringView source, StringView filename)
 {
-    auto parser = JS::Parser(JS::Lexer(source, filename));
-    auto program = parser.parse_program();
-    if (parser.has_errors()) {
-        parser.print_errors(false);
+    // FIXME: The only user of this function now is javascript: URLs. Refactor them to follow the spec: https://html.spec.whatwg.org/multipage/browsing-the-web.html#javascript-protocol
+    auto& interpreter = document().interpreter();
+    auto script_or_error = JS::Script::parse(source, interpreter.realm(), filename);
+    if (script_or_error.is_error()) {
+        // FIXME: Add error logging back.
         return JS::js_undefined();
     }
-    auto& interpreter = document().interpreter();
+
+    auto result = interpreter.run(script_or_error.value());
+
     auto& vm = interpreter.vm();
-    auto result = interpreter.run(interpreter.global_object(), *program);
     if (result.is_error()) {
         // FIXME: I'm sure the spec could tell us something about error propagation here!
         vm.clear_exception();
diff --git a/Userland/Libraries/LibWeb/HTML/Scripting/ClassicScript.cpp b/Userland/Libraries/LibWeb/HTML/Scripting/ClassicScript.cpp
index 92c1525dd9..0553dcd741 100644
--- a/Userland/Libraries/LibWeb/HTML/Scripting/ClassicScript.cpp
+++ b/Userland/Libraries/LibWeb/HTML/Scripting/ClassicScript.cpp
@@ -69,9 +69,15 @@ JS::Value ClassicScript::run(RethrowErrors rethrow_errors)
     (void)rethrow_errors;
 
     auto timer = Core::ElapsedTimer::start_new();
+
+    // 6. Otherwise, set evaluationStatus to ScriptEvaluation(script's record).
+    // FIXME: Interpreter::run doesn't currently return a JS::Completion.
     auto interpreter = JS::Interpreter::create_with_existing_realm(m_script_record->realm());
 
-    auto result = interpreter->run(interpreter->global_object(), m_script_record->parse_node());
+    auto result = interpreter->run(*m_script_record);
+
+    // FIXME: If ScriptEvaluation does not complete because the user agent has aborted the running script, leave evaluationStatus as null.
+
     dbgln("ClassicScript: Finished running script {}, Duration: {}ms", filename(), timer.elapsed());
     if (result.is_error()) {
         // FIXME: Propagate error according to the spec.
diff --git a/Userland/Services/WebContent/ClientConnection.cpp b/Userland/Services/WebContent/ClientConnection.cpp
index f7221caab9..75dd46a519 100644
--- a/Userland/Services/WebContent/ClientConnection.cpp
+++ b/Userland/Services/WebContent/ClientConnection.cpp
@@ -329,9 +329,11 @@ void ClientConnection::run_javascript(String const& js_source)
 
     auto& interpreter = page().top_level_browsing_context().active_document()->interpreter();
 
-    auto parser = JS::Parser(JS::Lexer(js_source));
-    auto program = parser.parse_program();
-    auto result = interpreter.run(interpreter.global_object(), *program);
+    auto script_or_error = JS::Script::parse(js_source, interpreter.realm(), "");
+    if (script_or_error.is_error())
+        return;
+
+    auto result = interpreter.run(script_or_error.value());
 
     if (result.is_error()) {
         dbgln("Exception :(");
diff --git a/Userland/Services/WebContent/WebContentConsoleClient.cpp b/Userland/Services/WebContent/WebContentConsoleClient.cpp
index c5c65fa135..a4a7e9de87 100644
--- a/Userland/Services/WebContent/WebContentConsoleClient.cpp
+++ b/Userland/Services/WebContent/WebContentConsoleClient.cpp
@@ -9,7 +9,7 @@
 #include "WebContentConsoleClient.h"
 #include <LibJS/Interpreter.h>
 #include <LibJS/MarkupGenerator.h>
-#include <LibJS/Parser.h>
+#include <LibJS/Script.h>
 #include <LibWeb/Bindings/WindowObject.h>
 #include <WebContent/ConsoleGlobalObject.h>
 
@@ -28,13 +28,11 @@ WebContentConsoleClient::WebContentConsoleClient(JS::Console& console, WeakPtr<J
 
 void WebContentConsoleClient::handle_input(String const& js_source)
 {
-    auto parser = JS::Parser(JS::Lexer(js_source));
-    auto program = parser.parse_program();
-
+    auto script_or_error = JS::Script::parse(js_source, m_interpreter->realm(), "");
     StringBuilder output_html;
     auto result = JS::ThrowCompletionOr<JS::Value> { JS::js_undefined() };
-    if (parser.has_errors()) {
-        auto error = parser.errors()[0];
+    if (script_or_error.is_error()) {
+        auto error = script_or_error.error()[0];
         auto hint = error.source_location_hint(js_source);
         if (!hint.is_empty())
             output_html.append(String::formatted("<pre>{}</pre>", escape_html_entities(hint)));
@@ -47,7 +45,7 @@ void WebContentConsoleClient::handle_input(String const& js_source)
         auto& this_value_before = m_interpreter->realm().global_environment().global_this_value();
         m_interpreter->realm().set_global_object(*m_console_global_object.cell(), &global_object_before);
 
-        result = m_interpreter->run(*m_console_global_object.cell(), *program);
+        result = m_interpreter->run(script_or_error.value());
 
         m_interpreter->realm().set_global_object(global_object_before, &this_value_before);
     }
diff --git a/Userland/Utilities/js.cpp b/Userland/Utilities/js.cpp
index cf376d8eda..40b960e1ab 100644
--- a/Userland/Utilities/js.cpp
+++ b/Userland/Utilities/js.cpp
@@ -62,6 +62,7 @@
 #include <LibJS/Runtime/Temporal/ZonedDateTime.h>
 #include <LibJS/Runtime/TypedArray.h>
 #include <LibJS/Runtime/Value.h>
+#include <LibJS/SourceTextModule.h>
 #include <LibLine/Editor.h>
 #include <LibMain/Main.h>
 #include <fcntl.h>
@@ -915,24 +916,22 @@ static bool write_to_file(String const& path)
 
 static bool parse_and_run(JS::Interpreter& interpreter, StringView source, StringView source_name)
 {
-    auto program_type = s_as_module ? JS::Program::Type::Module : JS::Program::Type::Script;
-    auto parser = JS::Parser(JS::Lexer(source), program_type);
-    auto program = parser.parse_program();
+    enum class ReturnEarly {
+        No,
+        Yes,
+    };
 
-    if (s_dump_ast)
-        program->dump(0);
+    JS::ThrowCompletionOr<JS::Value> result { JS::js_undefined() };
 
-    auto result = JS::ThrowCompletionOr<JS::Value> { JS::js_undefined() };
+    auto run_script_or_module = [&](Variant<NonnullRefPtr<JS::Script>, NonnullRefPtr<JS::SourceTextModule>> script_or_module) {
+        auto program = script_or_module.visit(
+            [](auto& visitor) -> NonnullRefPtr<JS::Program> {
+                return visitor->parse_node();
+            });
+
+        if (s_dump_ast)
+            program->dump(0);
 
-    if (parser.has_errors()) {
-        auto error = parser.errors()[0];
-        if (!s_disable_source_location_hints) {
-            auto hint = error.source_location_hint(source);
-            if (!hint.is_empty())
-                js_outln("{}", hint);
-        }
-        result = vm->throw_completion<JS::SyntaxError>(interpreter.global_object(), error.to_string());
-    } else {
         if (JS::Bytecode::g_dump_bytecode || s_run_bytecode) {
             auto executable = JS::Bytecode::Generator::generate(*program);
             executable.name = source_name;
@@ -949,10 +948,45 @@ static bool parse_and_run(JS::Interpreter& interpreter, StringView source, Strin
                 JS::Bytecode::Interpreter bytecode_interpreter(interpreter.global_object(), interpreter.realm());
                 result = bytecode_interpreter.run(executable);
             } else {
-                return true;
+                return ReturnEarly::Yes;
             }
         } else {
-            result = interpreter.run(interpreter.global_object(), *program);
+            result = script_or_module.visit(
+                [&](auto& visitor) {
+                    return interpreter.run(*visitor);
+                });
+        }
+
+        return ReturnEarly::No;
+    };
+
+    if (!s_as_module) {
+        auto script_or_error = JS::Script::parse(source, interpreter.realm(), source_name);
+        if (script_or_error.is_error()) {
+            auto error = script_or_error.error()[0];
+            auto hint = error.source_location_hint(source);
+            if (!hint.is_empty())
+                outln("{}", hint);
+            outln(error.to_string());
+            vm->throw_exception<JS::SyntaxError>(interpreter.global_object(), error.to_string());
+        } else {
+            auto return_early = run_script_or_module(move(script_or_error.value()));
+            if (return_early == ReturnEarly::Yes)
+                return true;
+        }
+    } else {
+        auto module_or_error = JS::SourceTextModule::parse(source, interpreter.realm(), source_name);
+        if (module_or_error.is_error()) {
+            auto error = module_or_error.error()[0];
+            auto hint = error.source_location_hint(source);
+            if (!hint.is_empty())
+                outln("{}", hint);
+            outln(error.to_string());
+            vm->throw_exception<JS::SyntaxError>(interpreter.global_object(), error.to_string());
+        } else {
+            auto return_early = run_script_or_module(move(module_or_error.value()));
+            if (return_early == ReturnEarly::Yes)
+                return true;
         }
     }
 
@@ -992,6 +1026,13 @@ static bool parse_and_run(JS::Interpreter& interpreter, StringView source, Strin
         last_value = JS::make_handle(result.value());
 
     if (result.is_error()) {
+        if (!vm->exception()) {
+            // Until js no longer relies on vm->exception() we have to set it in case the exception was cleared
+            VERIFY(result.throw_completion().value().has_value());
+            auto throw_value = result.release_error().release_value().release_value();
+            auto* exception = interpreter.heap().allocate<JS::Exception>(interpreter.global_object(), throw_value);
+            vm->set_exception(*exception);
+        }
         handle_exception();
         return false;
     } else if (s_print_last_result) {
@@ -1012,14 +1053,13 @@ static JS::ThrowCompletionOr<JS::Value> load_file_impl(JS::VM& vm, JS::GlobalObj
         return vm.throw_completion<JS::Error>(global_object, String::formatted("Failed to open '{}': {}", filename, file->error_string()));
     auto file_contents = file->read_all();
     auto source = StringView { file_contents };
-    auto parser = JS::Parser(JS::Lexer(source));
-    auto program = parser.parse_program();
-    if (parser.has_errors()) {
-        auto& error = parser.errors()[0];
+    auto script_or_error = JS::Script::parse(source, vm.interpreter().realm(), filename);
+    if (script_or_error.is_error()) {
+        auto& error = script_or_error.error()[0];
         return vm.throw_completion<JS::SyntaxError>(global_object, error.to_string());
     }
     // FIXME: Use eval()-like semantics and execute in current scope?
-    TRY(vm.interpreter().run(global_object, *program));
+    TRY(vm.interpreter().run(script_or_error.value()));
     return JS::js_undefined();
 }