/*
 * Copyright 2026 WebAssembly Community Group participants
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

// Make all structs and arrays shared and makes all functions unshared. This
// serves two purposes: 1) converts unshared Wasm GC programs to use the shared
// heap for testing, and 2) lowers shared Wasm GC programs that use shared
// functions so they can run on experimental implementations that do not support
// shared functions.
//
// Because shared structs and arrays cannot contain unshared function
// references, replace function references in structs and arrays with indices
// into a function table that will be duplicated on each thread. Because
// arbitrary unknown function references may be written into structs and arrays
// and there is no way to look up a table index given a function reference,
// function references cannot be replaced only inside structs and arrays.
// Replace all function references in the module with table indices and fix up
// all instructions that consume function references (e.g. call_ref, casts)
// accordingly. Use i31 references to represent the table indices to avoid
// further complications from mapping function references to non-reference
// values.
//
// Although the shared objects prototype supports shared externrefs in general,
// it is not the case that arbitrary unshared externrefs can be made shared. To
// work around this, also lower unshared externrefs to i31ref table indices.
// Unlike function references, which we assume form a closed set whose table
// indices are meaningful across threads, there can be an arbitrary number of
// externrefs at runtime and only those that are imported as globals can be
// assumed to be meaningful across different threads. As a result, the externref
// table supports growing over time and externrefs rather than their table
// indices are still passed at the module boundary, unlike for function
// references.

#include "ir/drop.h"
#include "ir/eh-utils.h"
#include "ir/module-utils.h"
#include "ir/names.h"
#include "ir/type-updating.h"
#include "ir/utils.h"
#include "literal.h"
#include "pass.h"
#include "support/name.h"
#include "wasm-builder.h"
#include "wasm-features.h"
#include "wasm-traversal.h"
#include "wasm-type.h"
#include "wasm.h"

#include <unordered_map>
#include <vector>

namespace wasm {

// Track several components used to store references in a table:
//  - The table itself
//  - Runtime functions for converting between references and table indices
//  - Utilities for inserting calls to these runtime functions as necessary.
// The table and runtime functions are only added to the module if they are
// used.
struct LazyTable {
  Module* wasm = nullptr;
  // The desired table name.
  Name base;
  // The non-conflicting version of `base`, if ever accessed.
  Name name;
  // The table type.
  Type type;
  // The names of conversion functions, if ever used.
  Name refToIndexName;
  Name indexToRefName;
  // Initial elements used to populate the table via an active element segment.
  std::vector<Expression*> init;

  LazyTable(Name base, Type type) : base(base), type(type) {}

  Name getName() {
    assert(wasm);
    if (!name) {
      name = Names::getValidTableName(*wasm, base);
    }
    return name;
  }

  Name getRefToIndexName() {
    assert(wasm);
    if (!refToIndexName) {
      std::string funcName = type.getHeapType().toString() + "_to_index";
      refToIndexName = Names::getValidFunctionName(*wasm, funcName);
      getName();
    }
    return refToIndexName;
  }

  Name getIndexToRefName() {
    assert(wasm);
    if (!indexToRefName) {
      std::string funcName = "index_to_" + type.getHeapType().toString();
      indexToRefName = Names::getValidFunctionName(*wasm, funcName);
      getName();
    }
    return indexToRefName;
  }

  // In normal operation, we are making types in the any hierarchy shared, but
  // with pass arg 'make-shared-objects-unshared', we overwrite this to make
  // them unshared instead. That helps separate the performance difference from
  // using the shared heap from the performance difference due to other
  // transformations we do in this pass.
  Shareability shared = Shared;

  void addRefToIndexFunction() {
    // (func $<t>_to_index (param $ref <t>) (result (ref null (shared i31)))
    //   (local $idx i32)
    //   (if (result (ref null (shared i31)))
    //     (ref.is_null (local.get $ref))
    //     (then
    //       (ref.null (shared none))
    //     )
    //     (else
    //       (if (result (ref (shared i31)))
    //         (i32.ge_s
    //           (local.tee $idx
    //             (table.grow $<table> (local.get $ref) (i32.const 1))
    //           )
    //           (i32.const 0)
    //         )
    //         (then
    //           (ref.i31_shared (local.get $idx))
    //         )
    //         (else
    //           (unreachable)
    //         )
    //       )
    //     )
    //   )
    // )
    Builder builder(*wasm);

    Type sharedI31Nullable = Type(HeapTypes::i31.getBasic(shared), Nullable);
    Type sharedI31NonNull = Type(HeapTypes::i31.getBasic(shared), NonNullable);
    auto* isNull = builder.makeRefIsNull(builder.makeLocalGet(0, type));
    auto* retNull = builder.makeRefNull(HeapTypes::none.getBasic(shared));
    auto* grow = builder.makeTableGrow(getName(),
                                       builder.makeLocalGet(0, type),
                                       builder.makeConst(Literal(int32_t(1))));
    auto* tee = builder.makeLocalTee(1, grow, Type::i32);
    auto* geZero =
      builder.makeBinary(GeSInt32, tee, builder.makeConst(Literal(int32_t(0))));
    auto* retIndex =
      builder.makeRefI31(builder.makeLocalGet(1, Type::i32), shared);
    auto* checkGrow = builder.makeIf(
      geZero, retIndex, builder.makeUnreachable(), sharedI31NonNull);

    auto* body = builder.makeIf(isNull, retNull, checkGrow, sharedI31Nullable);
    auto func = Builder::makeFunction(
      refToIndexName, Signature(type, sharedI31Nullable), {Type::i32}, body);
    func->hasExplicitName = true;
    wasm->addFunction(std::move(func));
  }

  void addIndexToRefFunction() {
    // (func $index_to_<t> (param $idx (ref null (shared i31))) (result <t>)
    //   (if (result <type>)
    //     (ref.is_null (local.get $idx))
    //     (then
    //       (ref.null <bottom>)
    //     )
    //     (else
    //       (table.get $<table> (i31.get_u (local.get $idx)))
    //     )
    //   )
    // )
    Builder builder(*wasm);

    Type sharedI31Nullable = Type(HeapTypes::i31.getBasic(shared), Nullable);
    auto* isNull =
      builder.makeRefIsNull(builder.makeLocalGet(0, sharedI31Nullable));
    auto* retNull = builder.makeRefNull(type.getHeapType().getBottom());
    auto* getRef = builder.makeTableGet(
      getName(),
      builder.makeI31Get(builder.makeLocalGet(0, sharedI31Nullable), false),
      type);

    auto* body = builder.makeIf(isNull, retNull, getRef, type);
    auto func = Builder::makeFunction(
      indexToRefName, Signature(sharedI31Nullable, type), {}, body);
    func->hasExplicitName = true;
    wasm->addFunction(std::move(func));
  }

  // Add the table, conversion functions, and active element segment if the
  // table was ever used.
  void maybeAdd(Address max) {
    assert(wasm);
    if (!name) {
      return;
    }
    Table* table = wasm->addTable(Builder::makeTable(name));
    table->type = type;
    table->initial = init.size();
    table->max = max;
    if (refToIndexName) {
      addRefToIndexFunction();
    }
    if (indexToRefName) {
      addIndexToRefFunction();
    }
    if (!init.empty()) {
      Builder builder(*wasm);
      Name segName = Names::getValidElementSegmentName(*wasm, base);
      auto* offset = builder.makeConst(Literal(int32_t(0)));
      auto* segment = wasm->addElementSegment(
        Builder::makeElementSegment(segName, name, offset));
      segment->type = type;
      segment->data = std::move(init);
    }
  }

  bool canHold(Type t) const {
    return t.isRef() && !t.isNull() && Type::isSubType(t, type);
  }

  bool hasHoldable(Type t) const {
    if (t.isTuple()) {
      for (Type elem : t) {
        if (hasHoldable(elem)) {
          return true;
        }
      }
      return false;
    }
    return canHold(t);
  }

  bool funcHasTableType(Function* func) const {
    Signature sig = func->type.getHeapType().getSignature();
    return hasHoldable(sig.params) || hasHoldable(sig.results);
  }

  Expression* convertToRef(Expression* arg, Type origType) {
    if (!canHold(origType)) {
      return arg;
    }
    Builder builder(*wasm);
    Expression* res = builder.makeCall(getIndexToRefName(), {arg}, type);
    if (origType != type) {
      res = builder.makeRefCast(res, origType);
    }
    return res;
  }

  Expression* convertToIndex(Expression* arg, Type origType, Type targetType) {
    if (!canHold(origType)) {
      return arg;
    }
    Builder builder(*wasm);
    Type sharedI31Nullable = Type(HeapTypes::i31.getBasic(shared), Nullable);
    Expression* res =
      builder.makeCall(getRefToIndexName(), {arg}, sharedI31Nullable);
    if (targetType.isNonNullable()) {
      res = builder.makeRefAs(RefAsNonNull, res);
    }
    return res;
  }
};

struct MakeSharedObjects
  : WalkerPass<PostWalker<MakeSharedObjects,
                          UnifiedExpressionVisitor<MakeSharedObjects>>> {
  Shareability shared = Shared;
  Type funcref = Type(HeapTypes::func, Nullable);
  Type externref = Type(HeapTypes::ext, Nullable);

  // Tables storing unshared funcrefs and externrefs that are lowered to shared
  // i31ref indices inside the module.
  LazyTable funcTable{"funcs", funcref};
  LazyTable externTable{"externs", externref};

  // Map from function name to index in `funcTable`.
  std::unordered_map<Name, Index> funcIndices;

  // Imported helper functions used to lower `extern.convert_any` and
  // `any.convert_extern`, if needed.
  Name anyToExternName;
  Name externToAnyName;

  Name getAnyToExternName() {
    if (!anyToExternName) {
      anyToExternName =
        Names::getValidFunctionName(*getModule(), "any_to_extern");
    }
    return anyToExternName;
  }

  Name getExternToAnyName() {
    if (!externToAnyName) {
      externToAnyName =
        Names::getValidFunctionName(*getModule(), "extern_to_any");
    }
    return externToAnyName;
  }

  Index getIndex(RefFunc* curr) {
    auto [it, inserted] =
      funcIndices.insert({curr->func, funcTable.init.size()});
    if (inserted) {
      funcTable.init.push_back(curr);
    }
    return it->second;
  }

  HeapType updatedHeapType(HeapType type) {
    if (type.isMaybeShared(HeapType::func) || type.isSignature()) {
      return HeapTypes::i31.getBasic(shared);
    }
    if (type.isMaybeShared(HeapType::nofunc)) {
      return HeapTypes::none.getBasic(shared);
    }
    if (type == HeapType::ext || type == HeapType::string) {
      return HeapTypes::i31.getBasic(shared);
    }
    if (type == HeapType::noext) {
      return HeapTypes::none.getBasic(shared);
    }
    if (type.isBasic()) {
      return type.getBasic(shared);
    }
    return type;
  }

  Type updatedSingleType(Type type) {
    if (type.isRef()) {
      return type.with(updatedHeapType(type.getHeapType()));
    }
    return type;
  }

  Type updatedType(Type type) {
    if (type.isTuple()) {
      std::vector<Type> elems;
      elems.reserve(type.size());
      for (auto t : type) {
        elems.push_back(updatedSingleType(t));
      }
      return Type(elems);
    }
    return updatedSingleType(type);
  }

  void updateType(Type& type) { type = updatedType(type); }

  Type getBoundaryType(Type origType, Type rewrittenType) {
    Signature origSig = origType.getHeapType().getSignature();
    Signature rewrittenSig = rewrittenType.getHeapType().getSignature();

    std::vector<Type> params;
    Index i = 0;
    for (Type param : origSig.params) {
      if (externTable.canHold(param)) {
        params.push_back(param);
      } else {
        params.push_back(rewrittenSig.params[i]);
      }
      ++i;
    }

    std::vector<Type> results;
    Index j = 0;
    for (Type result : origSig.results) {
      if (externTable.canHold(result)) {
        results.push_back(result);
      } else {
        results.push_back(rewrittenSig.results[j]);
      }
      ++j;
    }

    return Type(Signature(Type(params), Type(results)),
                NonNullable,
                origType.getExactness());
  }

  void wrapImport(Function* func, Type origType) {
    // Create a new imported function with the boundary type. The original
    // function (which has lowered param and result types) is no longer an
    // import and is given a body that calls the new import and converts the
    // externrefs to and from indices.
    Builder builder(*getModule());
    Name origName = func->name;
    Name importName = Names::getValidFunctionName(
      *getModule(), origName.toString() + "$import");

    Type boundaryType = getBoundaryType(origType, func->type);

    auto importFunc = std::make_unique<Function>();
    importFunc->name = importName;
    importFunc->module = func->module;
    importFunc->base = func->base;
    importFunc->type = boundaryType;
    importFunc->hasExplicitName = true;

    func->module = Name();
    func->base = Name();
    func->type = Type(func->type.getHeapType(), NonNullable, Exact);

    // Convert indices passed as params to externrefs.
    Signature boundarySig = boundaryType.getHeapType().getSignature();
    std::vector<Expression*> callArgs;
    Index i = 0;
    for (Type param : boundarySig.params) {
      Type localType = func->getParams()[i];
      Expression* get = builder.makeLocalGet(i, localType);
      callArgs.push_back(externTable.convertToRef(get, param));
      ++i;
    }

    Type extResults = boundarySig.results;
    auto* call = builder.makeCall(importName, callArgs, extResults);

    // Convert externrefs received as results to indices.
    if (!externTable.hasHoldable(extResults)) {
      func->body = call;
    } else if (extResults.isSingle()) {
      Type targetType = func->getResults();
      func->body = externTable.convertToIndex(call, extResults, targetType);
    } else {
      Index scratch = Builder::addVar(func, extResults);
      auto* set = builder.makeLocalSet(scratch, call);
      std::vector<Expression*> tupleElems;
      Index j = 0;
      for (Type t : extResults) {
        auto* extract = builder.makeTupleExtract(
          builder.makeLocalGet(scratch, extResults), j);
        tupleElems.push_back(
          externTable.convertToIndex(extract, t, func->getResults()[j]));
        ++j;
      }
      auto* tupleMake = builder.makeTupleMake(tupleElems);
      func->body = builder.makeBlock({set, tupleMake});
    }

    getModule()->addFunction(std::move(importFunc));
  }

  Name wrapExport(Export* ex, Type origType) {
    // Wrap the exported function with a new function that calls the original
    // exported function, converting externref params into indices and index
    // results into externrefs.
    Builder builder(*getModule());
    auto* internalFunc = getModule()->getFunction(*ex->getInternalName());
    Name origName = internalFunc->name;
    Name exportWrapperName = Names::getValidFunctionName(
      *getModule(), origName.toString() + "$export");

    Type boundaryType = getBoundaryType(origType, internalFunc->type);

    auto exportWrapper = std::make_unique<Function>();
    exportWrapper->name = exportWrapperName;
    exportWrapper->type = Type(boundaryType.getHeapType(), NonNullable, Exact);
    exportWrapper->hasExplicitName = true;

    // Forward params, converting externrefs to indices.
    Signature boundarySig = boundaryType.getHeapType().getSignature();
    std::vector<Expression*> callArgs;
    Index i = 0;
    for (Type param : boundarySig.params) {
      Type localType = exportWrapper->getParams()[i];
      Expression* get = builder.makeLocalGet(i, localType);
      Type targetType = internalFunc->getParams()[i];
      callArgs.push_back(externTable.convertToIndex(get, param, targetType));
      ++i;
    }

    Type internalResults = internalFunc->getResults();
    auto* call = builder.makeCall(origName, callArgs, internalResults);

    // Forward results, converting indices to externrefs.
    Type extResults = boundarySig.results;
    if (!externTable.hasHoldable(extResults)) {
      exportWrapper->body = call;
    } else if (extResults.isSingle()) {
      exportWrapper->body = externTable.convertToRef(call, extResults);
    } else {
      Index scratch = Builder::addVar(exportWrapper.get(), internalResults);
      auto* set = builder.makeLocalSet(scratch, call);
      std::vector<Expression*> tupleElems;
      Index j = 0;
      for (Type t : extResults) {
        auto* extract = builder.makeTupleExtract(
          builder.makeLocalGet(scratch, internalResults), j);
        tupleElems.push_back(externTable.convertToRef(extract, t));
        ++j;
      }
      auto* tupleMake = builder.makeTupleMake(tupleElems);
      exportWrapper->body = builder.makeBlock({set, tupleMake});
    }

    getModule()->addFunction(std::move(exportWrapper));
    ex->setInternalName(exportWrapperName);
    return exportWrapperName;
  }

  void visitRefFunc(RefFunc* curr) {
    Builder builder(*getModule());
    replaceCurrent(
      builder.makeRefI31(builder.makeConst(Literal(getIndex(curr))), shared));
  }

  std::unordered_map<CallRef*, HeapType> callRefTypes;
  bool hasBlockNestedPop = false;

  void walkFunction(Function* curr) {
    hasBlockNestedPop = false;
    // Update local types before walking the body so that any scratch locals
    // added during the walk with original boundary types (e.g. externref) are
    // not overwritten afterward.
    for (auto& type : curr->vars) {
      updateType(type);
    }
    // When we replace call_ref target operands with i31s, we will lose
    // information we need about the intended call target type. Collect those
    // types up front before we update anything.
    struct CallRefCollector : PostWalker<CallRefCollector> {
      std::unordered_map<CallRef*, HeapType>& types;
      CallRefCollector(std::unordered_map<CallRef*, HeapType>& types)
        : types(types) {}
      void visitCallRef(CallRef* curr) {
        if (curr->target->type.isSignature()) {
          types[curr] = curr->target->type.getHeapType();
        }
      }
    };
    CallRefCollector collector(callRefTypes);
    collector.walk(curr->body);
    WalkerPass::walkFunction(curr);
    if (hasBlockNestedPop) {
      EHUtils::handleBlockNestedPops(curr, *getModule());
    }
  }

  void visitCallRef(CallRef* curr) {
    updateType(curr->type);
    Builder builder(*getModule());
    auto it = callRefTypes.find(curr);
    if (it == callRefTypes.end()) {
      // The target type wasn't a signature, so it must have been null or
      // unreachable.
      replaceCurrent(
        getDroppedChildrenAndAppend(curr,
                                    *getModule(),
                                    getPassOptions(),
                                    builder.makeUnreachable(),
                                    DropMode::IgnoreParentEffects));
      return;
    }
    auto type = it->second;
    callRefTypes.erase(it);
    replaceCurrent(
      builder.makeCallIndirect(funcTable.getName(),
                               builder.makeI31Get(curr->target, false),
                               curr->operands,
                               type,
                               curr->isReturn));
  }

  void visitCallIndirect(CallIndirect* curr) {
    updateType(curr->type);
    Builder builder(*getModule());
    Name oldTable = curr->table;
    Type oldTableType = updatedType(getModule()->getTable(oldTable)->type);
    auto* index = builder.makeTableGet(oldTable, curr->target, oldTableType);
    curr->target = builder.makeI31Get(index, false);
    curr->table = funcTable.getName();
  }

  void visitRefTest(RefTest* curr) {
    if (curr->type == Type::unreachable) {
      return;
    }
    auto castHeapType = curr->castType.getHeapType();
    if (castHeapType.isMaybeShared(HeapType::func) ||
        castHeapType.isMaybeShared(HeapType::nofunc)) {
      // This always passes or fails except possibly due to nulls.
      updateType(curr->castType);
      return;
    }
    if (!castHeapType.isSignature()) {
      updateType(curr->castType);
      return;
    }
    Builder builder(*getModule());
    if (curr->ref->type.isNonNullable()) {
      // (ref.test castType (table.get $t (i31.get_u ref)))
      curr->ref = builder.makeTableGet(
        funcTable.getName(), builder.makeI31Get(curr->ref, false), funcref);
      return;
    }
    // (if (result i32)
    //   (ref.is_null (local.tee $scratch ref))
    //   (then (i32.const 1) OR (i32.const 0))
    //   (else (ref.test castType
    //     (table.get $t (i31.get_u (local.get $scratch))))
    //   )
    // )
    auto scratchType = curr->ref->type;
    Index scratch = Builder::addVar(getFunction(), scratchType);
    auto* cond = builder.makeRefIsNull(
      builder.makeLocalTee(scratch, curr->ref, scratchType));
    auto* ifNull =
      builder.makeConst(Literal(int32_t(curr->castType.isNullable())));
    curr->ref = builder.makeTableGet(
      funcTable.getName(),
      builder.makeI31Get(builder.makeLocalGet(scratch, scratchType), false),
      funcref);
    replaceCurrent(builder.makeIf(cond, ifNull, curr, Type::i32));
  }

  void visitRefCast(RefCast* curr) {
    if (curr->type == Type::unreachable) {
      return;
    }
    auto castHeapType = curr->type.getHeapType();
    if (castHeapType.isMaybeShared(HeapType::func) ||
        castHeapType.isMaybeShared(HeapType::nofunc)) {
      // This always passes or fails except possibly due to nulls.
      updateType(curr->type);
      return;
    }
    if (!castHeapType.isSignature()) {
      updateType(curr->type);
      return;
    }
    if (getPassOptions().trapsNeverHappen) {
      // shared i31 in, shared i31 out, no matter what the cast source and
      // target are.
      replaceCurrent(curr->ref);
      return;
    }
    // (if (result sharedi31ref)
    //   (ref.is_null (local.tee $scratch ref)),
    //   (then (local.get $scratch) OR (unreachable))
    //   (else
    //     (if (result sharedi31ref)
    //        (ref.test castType
    //          (table.get $t (i31.get_u (local.get $scratch)))
    //        (then (ref.as_non_null? (local.get $scratch)))
    //        (else (unreachable))
    //     )
    //   )
    // )
    Builder builder(*getModule());
    auto newCastType = updatedType(curr->type);
    auto scratchType = curr->ref->type;
    Index scratch = Builder::addVar(getFunction(), scratchType);
    auto* tee = builder.makeLocalTee(scratch, curr->ref, scratchType);
    auto* isNull = builder.makeRefIsNull(tee);
    Expression* ifNull = nullptr;
    if (curr->type.isNullable()) {
      ifNull = builder.makeLocalGet(scratch, scratchType);
    } else {
      ifNull = builder.makeUnreachable();
    }
    auto* getScratch = builder.makeLocalGet(scratch, scratchType);
    auto* i31get = builder.makeI31Get(getScratch, false);
    auto* tableGet = builder.makeTableGet(funcTable.getName(), i31get, funcref);
    auto* refTest = builder.makeRefTest(tableGet, curr->type);
    Expression* ifPass = builder.makeLocalGet(scratch, scratchType);
    if (curr->type.isNonNullable()) {
      ifPass = builder.makeRefAs(RefAsNonNull, ifPass);
    }
    auto* ifFail = builder.makeUnreachable();
    auto* ifNonNull = builder.makeIf(refTest, ifPass, ifFail, newCastType);
    replaceCurrent(builder.makeIf(isNull, ifNull, ifNonNull, newCastType));
  }

  void visitBrOn(BrOn* curr) {
    if (curr->type == Type::unreachable) {
      return;
    }
    if (curr->op != BrOnCast && curr->op != BrOnCastFail) {
      return;
    }
    auto castHeapType = curr->castType.getHeapType();
    if (castHeapType.isMaybeShared(HeapType::func) ||
        castHeapType.isMaybeShared(HeapType::nofunc)) {
      // This always passes or fails except possibly due to nulls.
      updateType(curr->castType);
      return;
    }
    WASM_UNREACHABLE("TODO: br_on");
  }

  void visitRefAs(RefAs* curr) {
    if (curr->type == Type::unreachable) {
      return;
    }
    if (curr->op == AnyConvertExtern) {
      Type extType = Type(HeapTypes::ext, curr->type.getNullability());
      Expression* ext = externTable.convertToRef(curr->value, extType);
      Builder builder(*getModule());
      Type sharedAnyNullable = Type(HeapTypes::any.getBasic(shared), Nullable);
      Expression* call =
        builder.makeCall(getExternToAnyName(), {ext}, sharedAnyNullable);
      if (curr->type.isNonNullable()) {
        call = builder.makeRefAs(RefAsNonNull, call);
      }
      replaceCurrent(call);
    } else if (curr->op == ExternConvertAny) {
      Builder builder(*getModule());
      Expression* call =
        builder.makeCall(getAnyToExternName(), {curr->value}, externref);
      Type extType = Type(HeapTypes::ext, curr->type.getNullability());
      Type targetType = updatedType(curr->type);
      replaceCurrent(externTable.convertToIndex(call, extType, targetType));
    }
  }

  void visitExpression(Expression* curr) {
    updateType(curr->type);

#define DELEGATE_ID curr->_id
#define DELEGATE_START(id) [[maybe_unused]] auto* cast = curr->cast<id>();
#define DELEGATE_GET_FIELD(id, field) cast->field
#define DELEGATE_FIELD_TYPE(id, field) updateType(cast->field);
#define DELEGATE_FIELD_CHILD(id, field)
#define DELEGATE_FIELD_INT(id, field)
#define DELEGATE_FIELD_LITERAL(id, field)
#define DELEGATE_FIELD_NAME(id, field)
#define DELEGATE_FIELD_SCOPE_NAME_DEF(id, field)
#define DELEGATE_FIELD_SCOPE_NAME_USE(id, field)
#define DELEGATE_FIELD_HEAPTYPE(id, field)
#define DELEGATE_FIELD_ADDRESS(id, field)
#include "wasm-delegations-fields.def"
  }

  // Compute the boundary parameter types for a tag, keeping externref
  // parameters unchanged while lowering other parameter types.
  Type getTagBoundaryParams(Type origParams) {
    std::vector<Type> params;
    for (Type t : origParams) {
      params.push_back(externTable.canHold(t) ? t : updatedType(t));
    }
    return Type(params);
  }

  // Convert lowered i31ref operands back to externrefs when throwing a tag
  // that expects externref parameters.
  void visitThrow(Throw* curr) {
    visitExpression(curr);
    Type origParams = getModule()->getTag(curr->tag)->params();
    for (Index i = 0; i < curr->operands.size(); ++i) {
      curr->operands[i] =
        externTable.convertToRef(curr->operands[i], origParams[i]);
    }
  }

  // Wrap pops with externref types in conversions from the caught externrefs
  // to i31ref table indices.
  void visitPop(Pop* curr) {
    if (!externTable.hasHoldable(curr->type)) {
      visitExpression(curr);
      return;
    }
    Type origParams = curr->type;
    Type internalParams = updatedType(origParams);
    Type boundaryParams = getTagBoundaryParams(origParams);
    curr->type = boundaryParams;
    if (origParams.isSingle()) {
      replaceCurrent(
        externTable.convertToIndex(curr, origParams, internalParams));
      return;
    }
    Builder builder(*getModule());
    Index scratch = Builder::addVar(getFunction(), boundaryParams);
    auto* set = builder.makeLocalSet(scratch, curr);
    std::vector<Expression*> elems;
    elems.reserve(origParams.size());
    for (Index i = 0; i < origParams.size(); ++i) {
      auto* extract = builder.makeTupleExtract(
        builder.makeLocalGet(scratch, boundaryParams), i);
      elems.push_back(
        externTable.convertToIndex(extract, origParams[i], internalParams[i]));
    }
    replaceCurrent(builder.makeSequence(set, builder.makeTupleMake(elems)));
    hasBlockNestedPop = true;
  }

  void visitTable(Table* curr) { updateType(curr->type); }

  void visitElementSegment(ElementSegment* curr) { updateType(curr->type); }

  // Create a new imported global with the original externref type and add it
  // to the externref table at instantiation time. The original global ceases to
  // be an import and is initialized to the shared i31 table index so internal
  // uses of the global receive the table index.
  void wrapGlobalImport(Global* global, Type origType) {
    // Mutable imported/exported externref globals are not supported because all
    // accesses to them would have to be rewritten to be function calls that
    // accessed the externref table. We cannot update such accesses outside this
    // module.
    if (global->mutable_ == Mutable) {
      Fatal() << "Cannot wrap mutable global " << global->name;
    }
    Builder builder(*getModule());
    Name origName = global->name;
    Name importName =
      Names::getValidGlobalName(*getModule(), origName.toString() + "$import");

    auto importGlobal = std::make_unique<Global>();
    importGlobal->name = importName;
    importGlobal->module = global->module;
    importGlobal->base = global->base;
    importGlobal->type = origType;
    importGlobal->mutable_ = false;
    importGlobal->hasExplicitName = true;

    Index index = externTable.init.size();
    externTable.init.push_back(builder.makeGlobalGet(importName, origType));

    global->module = Name();
    global->base = Name();
    global->init =
      builder.makeRefI31(builder.makeConst(Literal(int32_t(index))), shared);

    getModule()->addGlobal(std::move(importGlobal));
  }

  struct GlobalImportToWrap {
    Global* global;
    Type origType;
  };
  std::vector<GlobalImportToWrap> globalImportsToWrap;

  void visitGlobal(Global* curr) {
    if (curr->imported() && externTable.canHold(curr->type)) {
      globalImportsToWrap.push_back({curr, curr->type});
    }
    updateType(curr->type);
  }

  void doWalkModule(Module* wasm) {
    if (hasArgument("make-shared-objects-unshared")) {
      shared = Unshared;
    }
    funcTable.wasm = wasm;
    funcTable.shared = shared;
    externTable.wasm = wasm;
    externTable.shared = shared;
    if (shared == Shared) {
      wasm->features.setSharedEverything();
    }
    WalkerPass::doWalkModule(wasm);
  }

  struct FuncImportToWrap {
    Function* func;
    Type origType;
  };

  struct ExportToWrap {
    Export* ex;
    Type origType;
  };

  struct TagToUpdate {
    Tag* tag;
    HeapType origType;
  };

  void visitModule(Module* wasm) {
    std::vector<FuncImportToWrap> importsToWrap;
    for (auto& func : wasm->functions) {
      if (func->imported() && externTable.funcHasTableType(func.get())) {
        importsToWrap.push_back({func.get(), func->type});
      }
    }

    std::vector<ExportToWrap> exportsToWrap;
    for (auto& ex : wasm->exports) {
      if (ex->kind == ExternalKind::Function) {
        if (auto* name = ex->getInternalName()) {
          auto* func = wasm->getFunction(*name);
          if (externTable.funcHasTableType(func)) {
            exportsToWrap.push_back(ExportToWrap{ex.get(), func->type});
          }
        }
      }
    }

    std::vector<TagToUpdate> tagsToUpdate;
    for (auto& tag : wasm->tags) {
      if (externTable.hasHoldable(tag->params())) {
        tagsToUpdate.push_back({tag.get(), tag->type});
      }
    }

    rewriteTypes();

    for (auto& [tag, origType] : tagsToUpdate) {
      tag->type = getBoundaryType(Type(origType, NonNullable),
                                  Type(tag->type, NonNullable))
                    .getHeapType();
    }

    for (auto& info : globalImportsToWrap) {
      wrapGlobalImport(info.global, info.origType);
    }
    for (auto& info : importsToWrap) {
      wrapImport(info.func, info.origType);
    }
    std::unordered_map<Function*, Name> wrappedExports;
    for (auto& info : exportsToWrap) {
      auto* internalFunc = wasm->getFunction(*info.ex->getInternalName());
      auto [it, inserted] = wrappedExports.insert({internalFunc, Name()});
      if (inserted) {
        it->second = wrapExport(info.ex, info.origType);
      } else {
        info.ex->setInternalName(it->second);
      }
    }

    funcTable.maybeAdd(funcTable.init.size());
    addExternTable();
    ReFinalize().run(getPassRunner(), wasm);
    ReFinalize().walkModuleCode(wasm);
  }

  void rewriteTypes() {
    auto info = ModuleUtils::getOptimizedIndexedHeapTypes(*getModule());
    TypeBuilder builder(info.types.size());

    auto map = [&](HeapType type) -> HeapType {
      if (auto newType = updatedHeapType(type); newType.isBasic()) {
        return newType;
      }
      return builder[info.indices.at(type)];
    };

    for (Index i = 0; i < info.types.size(); ++i) {
      if (info.types[i].getRecGroupIndex() == 0) {
        builder.createRecGroup(i, info.types[i].getRecGroup().size());
      }
      builder[i].copy(info.types[i], map);
      if (info.types[i].isSignature()) {
        builder[i].setShared(Unshared);
        // `map` will have mapped any supertype to i31, which means the copy
        // will not have its supertype set. Fix it.
        if (auto super = info.types[i].getDeclaredSuperType()) {
          builder[i].subTypeOf(builder[info.indices.at(*super)]);
        }
      } else {
        builder[i].setShared(shared);
      }
    }

    auto built = builder.build();
    if (auto* err = built.getError()) {
      Fatal() << "Failed to build types: " << err->index << ": " << err->reason;
    }

    assert(info.types.size() == built->size());
    std::unordered_map<HeapType, HeapType> oldToNew;
    for (Index i = 0; i < info.types.size(); ++i) {
      oldToNew[info.types[i]] = (*built)[i];
    }

    GlobalTypeRewriter rewriter(*getModule(), getPassOptions().worldMode);
    rewriter.mapTypes(oldToNew);
    rewriter.mapTypeNamesAndIndices(oldToNew);
  }

  void addAnyToExternFunction() {
    Type sharedAnyNullable = Type(HeapTypes::any.getBasic(shared), Nullable);
    Type externrefNullable = Type(HeapTypes::ext, Nullable);
    auto importFunc = Builder::makeFunction(
      anyToExternName, Signature(sharedAnyNullable, externrefNullable), {});
    importFunc->module = "env";
    importFunc->base = "any_to_extern";
    importFunc->hasExplicitName = true;
    getModule()->addFunction(std::move(importFunc));
  }

  void addExternToAnyFunction() {
    Type externrefNullable = Type(HeapTypes::ext, Nullable);
    Type sharedAnyNullable = Type(HeapTypes::any.getBasic(shared), Nullable);
    auto importFunc = Builder::makeFunction(
      externToAnyName, Signature(externrefNullable, sharedAnyNullable), {});
    importFunc->module = "env";
    importFunc->base = "extern_to_any";
    importFunc->hasExplicitName = true;
    getModule()->addFunction(std::move(importFunc));
  }

  void addExternTable() {
    externTable.maybeAdd(Table::kUnlimitedSize);
    if (anyToExternName) {
      addAnyToExternFunction();
    }
    if (externToAnyName) {
      addExternToAnyFunction();
    }
  }

  std::unique_ptr<Pass> create() override {
    return std::make_unique<MakeSharedObjects>();
  }
};

Pass* createMakeSharedObjectsPass() { return new MakeSharedObjects(); }

} // namespace wasm