[Parser] Parse tables and element segments (#6147)

These module fields are especially complex to parse because they contain both
nontrivial types and instructions, so their parsing logic needs to be spread out
across the ParseDecls, ParseModuleTypes, and ParseDefs phases of parsing. This
applies to in-line elements in table definitions as well, which means we need to
be able to match a table to its in-line element segment across multiple phases.

7 files changed, 611 insertions, 40 deletions

diff --git a/src/parser/context-decls.cpp b/src/parser/context-decls.cpp
index 721127614..7d2d8a0a9 100644
--- a/src/parser/context-decls.cpp
+++ b/src/parser/context-decls.cpp
@@ -77,6 +77,59 @@ Result<> ParseDeclsCtx::addFunc(Name name,
   return Ok{};
 }
 
+Result<Table*> ParseDeclsCtx::addTableDecl(Index pos,
+                                           Name name,
+                                           ImportNames* importNames,
+                                           Limits limits) {
+  auto t = std::make_unique<Table>();
+  t->initial = limits.initial;
+  t->max = limits.max ? *limits.max : Table::kUnlimitedSize;
+  if (name.is()) {
+    if (wasm.getTableOrNull(name)) {
+      // TODO: if the existing table is not explicitly named, fix its name and
+      // continue.
+      return in.err(pos, "repeated table name");
+    }
+    t->setExplicitName(name);
+  } else {
+    name = (importNames ? "timport$" : "") + std::to_string(tableCounter++);
+    name = Names::getValidTableName(wasm, name);
+    t->name = name;
+  }
+  applyImportNames(*t, importNames);
+  return wasm.addTable(std::move(t));
+}
+
+Result<> ParseDeclsCtx::addTable(Name name,
+                                 const std::vector<Name>& exports,
+                                 ImportNames* import,
+                                 Limits limits,
+                                 Index pos) {
+  CHECK_ERR(checkImport(pos, import));
+  auto t = addTableDecl(pos, name, import, limits);
+  CHECK_ERR(t);
+  CHECK_ERR(addExports(in, wasm, *t, exports, ExternalKind::Table));
+  tableDefs.push_back({name, pos, Index(tableDefs.size())});
+  return Ok{};
+}
+
+Result<> ParseDeclsCtx::addImplicitElems(TypeT, ElemListT&& elems) {
+  auto& table = *wasm.tables.back();
+  auto e = std::make_unique<ElementSegment>();
+  e->table = table.name;
+  e->offset = Builder(wasm).makeConstPtr(0, Type::i32);
+  e->name = Names::getValidElementSegmentName(wasm, "implicit-elem");
+  wasm.addElementSegment(std::move(e));
+
+  // Record the index mapping so we can find this segment again to set its type
+  // and elements in later phases.
+  Index tableIndex = wasm.tables.size() - 1;
+  Index elemIndex = wasm.elementSegments.size() - 1;
+  implicitElemIndices[tableIndex] = elemIndex;
+
+  return Ok{};
+}
+
 Result<Memory*> ParseDeclsCtx::addMemoryDecl(Index pos,
                                              Name name,
                                              ImportNames* importNames,
@@ -84,7 +137,7 @@ Result<Memory*> ParseDeclsCtx::addMemoryDecl(Index pos,
   auto m = std::make_unique<Memory>();
   m->indexType = type.type;
   m->initial = type.limits.initial;
-  m->max = type.limits.max;
+  m->max = type.limits.max ? *type.limits.max : Memory::kUnlimitedSize;
   m->shared = type.shared;
   if (name) {
     // TODO: if the existing memory is not explicitly named, fix its name
@@ -160,6 +213,26 @@ Result<> ParseDeclsCtx::addGlobal(Name name,
   return Ok{};
 }
 
+Result<> ParseDeclsCtx::addElem(
+  Name name, TableIdxT*, std::optional<ExprT>, ElemListT&&, Index pos) {
+  auto e = std::make_unique<ElementSegment>();
+  if (name) {
+    if (wasm.getElementSegmentOrNull(name)) {
+      // TDOO: if the existing segment is not explicitly named, fix its name and
+      // continue.
+      return in.err(pos, "repeated element segment name");
+    }
+    e->setExplicitName(name);
+  } else {
+    name = std::to_string(elemCounter++);
+    name = Names::getValidElementSegmentName(wasm, name);
+    e->name = name;
+  }
+  elemDefs.push_back({name, pos, Index(wasm.elementSegments.size())});
+  wasm.addElementSegment(std::move(e));
+  return Ok{};
+}
+
 Result<> ParseDeclsCtx::addData(Name name,
                                 MemoryIdxT*,
                                 std::optional<ExprT>,
diff --git a/src/parser/context-defs.cpp b/src/parser/context-defs.cpp
index 76e61d4fb..e5c598b6b 100644
--- a/src/parser/context-defs.cpp
+++ b/src/parser/context-defs.cpp
@@ -72,6 +72,36 @@ Result<> ParseDefsCtx::addGlobal(Name,
   return Ok{};
 }
 
+Result<> ParseDefsCtx::addImplicitElems(Type,
+                                        std::vector<Expression*>&& elems) {
+  auto& e = wasm.elementSegments[implicitElemIndices.at(index)];
+  e->data = std::move(elems);
+  return Ok{};
+}
+
+Result<> ParseDefsCtx::addElem(Name,
+                               Name* table,
+                               std::optional<Expression*> offset,
+                               std::vector<Expression*>&& elems,
+                               Index pos) {
+  auto& e = wasm.elementSegments[index];
+  if (offset) {
+    e->offset = *offset;
+    if (table) {
+      e->table = *table;
+    } else if (wasm.tables.size() > 0) {
+      e->table = wasm.tables[0]->name;
+    } else {
+      return in.err(pos, "active element segment with no table");
+    }
+  } else {
+    e->offset = nullptr;
+    e->table = Name();
+  }
+  e->data = std::move(elems);
+  return Ok{};
+}
+
 Result<> ParseDefsCtx::addData(
   Name, Name* mem, std::optional<ExprT> offset, DataStringT, Index pos) {
   auto& d = wasm.dataSegments[index];
@@ -83,7 +113,7 @@ Result<> ParseDefsCtx::addData(
     } else if (wasm.memories.size() > 0) {
       d->memory = wasm.memories[0]->name;
     } else {
-      return in.err(pos, "active segment with no memory");
+      return in.err(pos, "active data segment with no memory");
     }
   } else {
     d->isPassive = true;
diff --git a/src/parser/contexts.h b/src/parser/contexts.h
index adb7694f6..8395f4dc4 100644
--- a/src/parser/contexts.h
+++ b/src/parser/contexts.h
@@ -41,7 +41,7 @@ inline std::vector<Type> getUnnamedTypes(const std::vector<NameType>& named) {
 
 struct Limits {
   uint64_t initial;
-  uint64_t max;
+  std::optional<uint64_t> max;
 };
 
 struct MemType {
@@ -94,6 +94,7 @@ struct NullTypeParserCtx {
   using GlobalTypeT = Ok;
   using TypeUseT = Ok;
   using LocalsT = Ok;
+  using ElemListT = Ok;
   using DataStringT = Ok;
 
   HeapTypeT makeFunc() { return Ok{}; }
@@ -265,7 +266,7 @@ template<typename Ctx> struct TypeParserCtx {
   DataStringT makeDataString() { return Ok{}; }
   void appendDataString(DataStringT&, std::string_view) {}
 
-  LimitsT makeLimits(uint64_t, std::optional<uint64_t>) { return Ok{}; }
+  Result<LimitsT> makeLimits(uint64_t, std::optional<uint64_t>) { return Ok{}; }
   LimitsT getLimitsFromData(DataStringT) { return Ok{}; }
 
   MemTypeT makeMemType(Type, LimitsT, bool) { return Ok{}; }
@@ -282,6 +283,7 @@ struct NullInstrParserCtx {
   using FieldIdxT = Ok;
   using FuncIdxT = Ok;
   using LocalIdxT = Ok;
+  using TableIdxT = Ok;
   using GlobalIdxT = Ok;
   using MemoryIdxT = Ok;
   using DataIdxT = Ok;
@@ -304,6 +306,8 @@ struct NullInstrParserCtx {
   LocalIdxT getLocalFromName(Name) { return Ok{}; }
   GlobalIdxT getGlobalFromIdx(uint32_t) { return Ok{}; }
   GlobalIdxT getGlobalFromName(Name) { return Ok{}; }
+  TableIdxT getTableFromIdx(uint32_t) { return Ok{}; }
+  TableIdxT getTableFromName(Name) { return Ok{}; }
   MemoryIdxT getMemoryFromIdx(uint32_t) { return Ok{}; }
   MemoryIdxT getMemoryFromName(Name) { return Ok{}; }
   DataIdxT getDataFromIdx(uint32_t) { return Ok{}; }
@@ -470,8 +474,11 @@ struct NullInstrParserCtx {
 // Phase 1: Parse definition spans for top-level module elements and determine
 // their indices and names.
 struct ParseDeclsCtx : NullTypeParserCtx, NullInstrParserCtx {
-  using DataStringT = std::vector<char>;
+  using ExprT = Ok;
   using LimitsT = Limits;
+  using ElemListT = Index;
+  using DataStringT = std::vector<char>;
+  using TableTypeT = Limits;
   using MemTypeT = MemType;
 
   ParseInput in;
@@ -488,18 +495,27 @@ struct ParseDeclsCtx : NullTypeParserCtx, NullInstrParserCtx {
   std::vector<DefPos> typeDefs;
   std::vector<DefPos> subtypeDefs;
   std::vector<DefPos> funcDefs;
+  std::vector<DefPos> tableDefs;
   std::vector<DefPos> memoryDefs;
   std::vector<DefPos> globalDefs;
+  std::vector<DefPos> elemDefs;
   std::vector<DefPos> dataDefs;
   std::vector<DefPos> tagDefs;
 
   // Positions of typeuses that might implicitly define new types.
   std::vector<Index> implicitTypeDefs;
 
+  // Map table indices to the indices of their implicit, in-line element
+  // segments. We need these to find associated segments in later parsing phases
+  // where we can parse their types and instructions.
+  std::unordered_map<Index, Index> implicitElemIndices;
+
   // Counters used for generating names for module elements.
   int funcCounter = 0;
+  int tableCounter = 0;
   int memoryCounter = 0;
   int globalCounter = 0;
+  int elemCounter = 0;
   int dataCounter = 0;
   int tagCounter = 0;
 
@@ -534,14 +550,24 @@ struct ParseDeclsCtx : NullTypeParserCtx, NullInstrParserCtx {
     typeDefs.push_back({{}, pos, Index(typeDefs.size())});
   }
 
+  Limits makeLimits(uint64_t n, std::optional<uint64_t> m) {
+    return Limits{n, m};
+  }
+
+  Index makeElemList(TypeT) { return 0; }
+  Index makeFuncElemList() { return 0; }
+  void appendElem(Index& elems, ExprT) { ++elems; }
+  void appendFuncElem(Index& elems, FuncIdxT) { ++elems; }
+
+  Limits getLimitsFromElems(Index elems) { return {elems, elems}; }
+
+  Limits makeTableType(Limits limits, TypeT) { return limits; }
+
   std::vector<char> makeDataString() { return {}; }
   void appendDataString(std::vector<char>& data, std::string_view str) {
     data.insert(data.end(), str.begin(), str.end());
   }
 
-  Limits makeLimits(uint64_t n, std::optional<uint64_t> m) {
-    return m ? Limits{n, *m} : Limits{n, Memory::kUnlimitedSize};
-  }
   Limits getLimitsFromData(const std::vector<char>& data) {
     uint64_t size = (data.size() + Memory::kPageSize - 1) / Memory::kPageSize;
     return {size, size};
@@ -567,6 +593,14 @@ struct ParseDeclsCtx : NullTypeParserCtx, NullInstrParserCtx {
                    std::optional<LocalsT>,
                    Index pos);
 
+  Result<Table*>
+  addTableDecl(Index pos, Name name, ImportNames* importNames, Limits limits);
+  Result<>
+  addTable(Name, const std::vector<Name>&, ImportNames*, Limits, Index);
+
+  // TODO: Record index of implicit elem for use when parsing types and instrs.
+  Result<> addImplicitElems(TypeT, ElemListT&& elems);
+
   Result<Memory*>
   addMemoryDecl(Index pos, Name name, ImportNames* importNames, MemType type);
 
@@ -587,6 +621,10 @@ struct ParseDeclsCtx : NullTypeParserCtx, NullInstrParserCtx {
                      std::optional<ExprT>,
                      Index pos);
 
+  Result<> addElem(Name, TableIdxT*, std::optional<ExprT>, ElemListT&&, Index);
+
+  Result<> addDeclareElem(Name, ElemListT&&, Index) { return Ok{}; }
+
   Result<> addData(Name name,
                    MemoryIdxT*,
                    std::optional<ExprT>,
@@ -741,25 +779,32 @@ struct ParseModuleTypesCtx : TypeParserCtx<ParseModuleTypesCtx>,
   // validate them when they are used.
 
   using GlobalTypeT = GlobalType;
+  using TableTypeT = Type;
   using TypeUseT = TypeUse;
 
+  using ElemListT = Type;
+
   ParseInput in;
 
   Module& wasm;
 
   const std::vector<HeapType>& types;
   const std::unordered_map<Index, HeapType>& implicitTypes;
+  const std::unordered_map<Index, Index>& implicitElemIndices;
 
   // The index of the current type.
   Index index = 0;
 
-  ParseModuleTypesCtx(std::string_view in,
-                      Module& wasm,
-                      const std::vector<HeapType>& types,
-                      const std::unordered_map<Index, HeapType>& implicitTypes,
-                      const IndexMap& typeIndices)
+  ParseModuleTypesCtx(
+    std::string_view in,
+    Module& wasm,
+    const std::vector<HeapType>& types,
+    const std::unordered_map<Index, HeapType>& implicitTypes,
+    const std::unordered_map<Index, Index>& implicitElemIndices,
+    const IndexMap& typeIndices)
     : TypeParserCtx<ParseModuleTypesCtx>(typeIndices), in(in), wasm(wasm),
-      types(types), implicitTypes(implicitTypes) {}
+      types(types), implicitTypes(implicitTypes),
+      implicitElemIndices(implicitElemIndices) {}
 
   Result<HeapTypeT> getHeapTypeFromIdx(Index idx) {
     if (idx >= types.size()) {
@@ -804,6 +849,18 @@ struct ParseModuleTypesCtx : TypeParserCtx<ParseModuleTypesCtx>,
     return {mutability, type};
   }
 
+  Type makeElemList(Type type) { return type; }
+  Type makeFuncElemList() { return Type(HeapType::func, Nullable); }
+  void appendElem(ElemListT&, ExprT) {}
+  void appendFuncElem(ElemListT&, FuncIdxT) {}
+
+  LimitsT getLimitsFromElems(ElemListT) { return Ok{}; }
+
+  Type makeTableType(LimitsT, Type type) { return type; }
+
+  LimitsT getLimitsFromData(DataStringT) { return Ok{}; }
+  MemTypeT makeMemType(Type, LimitsT, bool) { return Ok{}; }
+
   Result<> addFunc(Name name,
                    const std::vector<Name>&,
                    ImportNames*,
@@ -828,6 +885,23 @@ struct ParseModuleTypesCtx : TypeParserCtx<ParseModuleTypesCtx>,
     return Ok{};
   }
 
+  Result<> addTable(
+    Name, const std::vector<Name>&, ImportNames*, Type ttype, Index pos) {
+    auto& t = wasm.tables[index];
+    if (!ttype.isRef()) {
+      return in.err(pos, "expected reference type");
+    }
+    t->type = ttype;
+    return Ok{};
+  }
+
+  Result<> addImplicitElems(Type type, ElemListT&&) {
+    auto& t = wasm.tables[index];
+    auto& e = wasm.elementSegments[implicitElemIndices.at(index)];
+    e->type = t->type;
+    return Ok{};
+  }
+
   Result<>
   addMemory(Name, const std::vector<Name>&, ImportNames*, MemTypeT, Index) {
     return Ok{};
@@ -848,6 +922,15 @@ struct ParseModuleTypesCtx : TypeParserCtx<ParseModuleTypesCtx>,
   }
 
   Result<>
+  addElem(Name, TableIdxT*, std::optional<ExprT>, ElemListT&& type, Index) {
+    auto& e = wasm.elementSegments[index];
+    e->type = type;
+    return Ok{};
+  }
+
+  Result<> addDeclareElem(Name, ElemListT&&, Index) { return Ok{}; }
+
+  Result<>
   addTag(Name, const std::vector<Name>&, ImportNames*, TypeUse use, Index pos) {
     auto& t = wasm.tags[index];
     if (!use.type.isSignature()) {
@@ -861,15 +944,18 @@ struct ParseModuleTypesCtx : TypeParserCtx<ParseModuleTypesCtx>,
 // Phase 5: Parse module element definitions, including instructions.
 struct ParseDefsCtx : TypeParserCtx<ParseDefsCtx> {
   using GlobalTypeT = Ok;
+  using TableTypeT = Ok;
   using TypeUseT = HeapType;
 
   using ExprT = Expression*;
+  using ElemListT = std::vector<Expression*>;
 
   using FieldIdxT = Index;
   using FuncIdxT = Name;
   using LocalIdxT = Index;
   using LabelIdxT = Index;
   using GlobalIdxT = Name;
+  using TableIdxT = Name;
   using MemoryIdxT = Name;
   using DataIdxT = Name;
   using TagIdxT = Name;
@@ -883,6 +969,7 @@ struct ParseDefsCtx : TypeParserCtx<ParseDefsCtx> {
 
   const std::vector<HeapType>& types;
   const std::unordered_map<Index, HeapType>& implicitTypes;
+  const std::unordered_map<Index, Index>& implicitElemIndices;
 
   // The index of the current module element.
   Index index = 0;
@@ -903,9 +990,11 @@ struct ParseDefsCtx : TypeParserCtx<ParseDefsCtx> {
                Module& wasm,
                const std::vector<HeapType>& types,
                const std::unordered_map<Index, HeapType>& implicitTypes,
+               const std::unordered_map<Index, Index>& implicitElemIndices,
                const IndexMap& typeIndices)
     : TypeParserCtx(typeIndices), in(in), wasm(wasm), builder(wasm),
-      types(types), implicitTypes(implicitTypes), irBuilder(wasm) {}
+      types(types), implicitTypes(implicitTypes),
+      implicitElemIndices(implicitElemIndices), irBuilder(wasm) {}
 
   template<typename T> Result<T> withLoc(Index pos, Result<T> res) {
     if (auto err = res.getErr()) {
@@ -929,6 +1018,20 @@ struct ParseDefsCtx : TypeParserCtx<ParseDefsCtx> {
 
   GlobalTypeT makeGlobalType(Mutability, TypeT) { return Ok{}; }
 
+  std::vector<Expression*> makeElemList(TypeT) { return {}; }
+  std::vector<Expression*> makeFuncElemList() { return {}; }
+  void appendElem(std::vector<Expression*>& elems, Expression* expr) {
+    elems.push_back(expr);
+  }
+  void appendFuncElem(std::vector<Expression*>& elems, Name func) {
+    auto type = wasm.getFunction(func)->type;
+    elems.push_back(builder.makeRefFunc(func, type));
+  }
+
+  LimitsT getLimitsFromElems(std::vector<Expression*>& elems) { return Ok{}; }
+
+  TableTypeT makeTableType(LimitsT, Type) { return Ok{}; }
+
   Result<HeapTypeT> getHeapTypeFromIdx(Index idx) {
     if (idx >= types.size()) {
       return in.err("type index out of bounds");
@@ -999,6 +1102,20 @@ struct ParseDefsCtx : TypeParserCtx<ParseDefsCtx> {
     return name;
   }
 
+  Result<Name> getTableFromIdx(uint32_t idx) {
+    if (idx >= wasm.tables.size()) {
+      return in.err("table index out of bounds");
+    }
+    return wasm.tables[idx]->name;
+  }
+
+  Result<Name> getTableFromName(Name name) {
+    if (!wasm.getTableOrNull(name)) {
+      return in.err("table $" + name.toString() + " does not exist");
+    }
+    return name;
+  }
+
   Result<Name> getMemoryFromIdx(uint32_t idx) {
     if (idx >= wasm.memories.size()) {
       return in.err("memory index out of bounds");
@@ -1058,12 +1175,32 @@ struct ParseDefsCtx : TypeParserCtx<ParseDefsCtx> {
                    std::optional<LocalsT>,
                    Index pos);
 
+  Result<>
+  addTable(Name, const std::vector<Name>&, ImportNames*, TableTypeT, Index) {
+    return Ok{};
+  }
+
   Result<> addGlobal(Name,
                      const std::vector<Name>&,
                      ImportNames*,
                      GlobalTypeT,
                      std::optional<ExprT> exp,
                      Index);
+
+  Result<> addImplicitElems(Type type, std::vector<Expression*>&& elems);
+
+  Result<> addDeclareElem(Name, std::vector<Expression*>&&, Index) {
+    // TODO: Validate that referenced functions appear in a declaratve element
+    // segment.
+    return Ok{};
+  }
+
+  Result<> addElem(Name,
+                   Name* table,
+                   std::optional<Expression*> offset,
+                   std::vector<Expression*>&& elems,
+                   Index pos);
+
   Result<>
   addData(Name, Name* mem, std::optional<ExprT> offset, DataStringT, Index pos);
 
diff --git a/src/parser/parsers.h b/src/parser/parsers.h
index f16cca2b5..2bf9915eb 100644
--- a/src/parser/parsers.h
+++ b/src/parser/parsers.h
@@ -39,6 +39,7 @@ template<typename Ctx> MaybeResult<typename Ctx::ArrayT> arraytype(Ctx&);
 template<typename Ctx> Result<typename Ctx::LimitsT> limits32(Ctx&);
 template<typename Ctx> Result<typename Ctx::LimitsT> limits64(Ctx&);
 template<typename Ctx> Result<typename Ctx::MemTypeT> memtype(Ctx&);
+template<typename Ctx> Result<typename Ctx::TableTypeT> tabletype(Ctx&);
 template<typename Ctx> Result<typename Ctx::GlobalTypeT> globaltype(Ctx&);
 
 // Instructions
@@ -165,7 +166,11 @@ template<typename Ctx> MaybeResult<Index> maybeTypeidx(Ctx& ctx);
 template<typename Ctx> Result<typename Ctx::HeapTypeT> typeidx(Ctx&);
 template<typename Ctx>
 Result<typename Ctx::FieldIdxT> fieldidx(Ctx&, typename Ctx::HeapTypeT);
+template<typename Ctx> MaybeResult<typename Ctx::FuncIdxT> maybeFuncidx(Ctx&);
 template<typename Ctx> Result<typename Ctx::FuncIdxT> funcidx(Ctx&);
+template<typename Ctx> MaybeResult<typename Ctx::TableIdxT> maybeTableidx(Ctx&);
+template<typename Ctx> Result<typename Ctx::TableIdxT> tableidx(Ctx&);
+template<typename Ctx> MaybeResult<typename Ctx::TableIdxT> maybeTableuse(Ctx&);
 template<typename Ctx> MaybeResult<typename Ctx::MemoryIdxT> maybeMemidx(Ctx&);
 template<typename Ctx> Result<typename Ctx::MemoryIdxT> memidx(Ctx&);
 template<typename Ctx> MaybeResult<typename Ctx::MemoryIdxT> maybeMemuse(Ctx&);
@@ -182,8 +187,12 @@ template<typename Ctx> MaybeResult<typename Ctx::ModuleNameT> subtype(Ctx&);
 template<typename Ctx> MaybeResult<> deftype(Ctx&);
 template<typename Ctx> MaybeResult<typename Ctx::LocalsT> locals(Ctx&);
 template<typename Ctx> MaybeResult<> func(Ctx&);
+template<typename Ctx> MaybeResult<> table(Ctx&);
 template<typename Ctx> MaybeResult<> memory(Ctx&);
 template<typename Ctx> MaybeResult<> global(Ctx&);
+template<typename Ctx> MaybeResult<typename Ctx::ExprT> maybeElemexpr(Ctx&);
+template<typename Ctx> Result<typename Ctx::ElemListT> elemlist(Ctx&, bool);
+template<typename Ctx> MaybeResult<> elem(Ctx&);
 template<typename Ctx> Result<typename Ctx::DataStringT> datastring(Ctx&);
 template<typename Ctx> MaybeResult<> data(Ctx&);
 template<typename Ctx> MaybeResult<> tag(Ctx&);
@@ -539,6 +548,18 @@ template<typename Ctx> Result<typename Ctx::MemTypeT> memtype(Ctx& ctx) {
   return ctx.makeMemType(type, *limits, shared);
 }
 
+// tabletype ::= limits32 reftype
+template<typename Ctx> Result<typename Ctx::TableTypeT> tabletype(Ctx& ctx) {
+  auto limits = limits32(ctx);
+  CHECK_ERR(limits);
+  auto type = reftype(ctx);
+  CHECK_ERR(type);
+  if (!type) {
+    return ctx.in.err("expected reftype");
+  }
+  return ctx.makeTableType(*limits, *type);
+}
+
 // globaltype ::= t:valtype               => const t
 //              | '(' 'mut' t:valtype ')' => var t
 template<typename Ctx> Result<typename Ctx::GlobalTypeT> globaltype(Ctx& ctx) {
@@ -626,7 +647,7 @@ template<typename Ctx> MaybeResult<> instr(Ctx& ctx) {
     if (auto keyword = tok->getKeyword()) {
       if (keyword == "end"sv || keyword == "then"sv || keyword == "else"sv ||
           keyword == "catch"sv || keyword == "catch_all"sv ||
-          keyword == "delegate"sv) {
+          keyword == "delegate"sv || keyword == "ref"sv) {
         return {};
       }
     }
@@ -1693,16 +1714,60 @@ Result<typename Ctx::FieldIdxT> fieldidx(Ctx& ctx,
 
 // funcidx ::= x:u32 => x
 //           | v:id => x (if t.funcs[x] = v)
-template<typename Ctx> Result<typename Ctx::FuncIdxT> funcidx(Ctx& ctx) {
+template<typename Ctx>
+MaybeResult<typename Ctx::FuncIdxT> maybeFuncidx(Ctx& ctx) {
   if (auto x = ctx.in.takeU32()) {
     return ctx.getFuncFromIdx(*x);
   }
   if (auto id = ctx.in.takeID()) {
     return ctx.getFuncFromName(*id);
   }
+  return {};
+}
+
+template<typename Ctx> Result<typename Ctx::FuncIdxT> funcidx(Ctx& ctx) {
+  if (auto idx = maybeFuncidx(ctx)) {
+    CHECK_ERR(idx);
+    return *idx;
+  }
   return ctx.in.err("expected function index or identifier");
 }
 
+// tableidx ::= x:u23 => x
+//            | v:id => x (if tables[x] = v)
+template<typename Ctx>
+MaybeResult<typename Ctx::TableIdxT> maybeTableidx(Ctx& ctx) {
+  if (auto x = ctx.in.takeU32()) {
+    return ctx.getTableFromIdx(*x);
+  }
+  if (auto id = ctx.in.takeID()) {
+    return ctx.getTableFromName(*id);
+  }
+  return {};
+}
+
+template<typename Ctx> Result<typename Ctx::TableIdxT> tableidx(Ctx& ctx) {
+  if (auto idx = maybeTableidx(ctx)) {
+    CHECK_ERR(idx);
+    return *idx;
+  }
+  return ctx.in.err("expected table index or identifier");
+}
+
+// tableuse ::= '(' 'table' x:tableidx ')'
+template<typename Ctx>
+MaybeResult<typename Ctx::TableIdxT> maybeTableuse(Ctx& ctx) {
+  if (!ctx.in.takeSExprStart("table"sv)) {
+    return {};
+  }
+  auto idx = tableidx(ctx);
+  CHECK_ERR(idx);
+  if (!ctx.in.takeRParen()) {
+    return ctx.in.err("Expected end of memory use");
+  }
+  return *idx;
+}
+
 // memidx ::= x:u32 => x
 //          | v:id  => x (if memories[x] = v)
 template<typename Ctx>
@@ -2031,6 +2096,82 @@ template<typename Ctx> MaybeResult<> func(Ctx& ctx) {
   return Ok{};
 }
 
+// table ::= '(' 'table' id? ('(' 'export' name ')')*
+//               '(' 'import' mod:name nm:name ')'? tabletype ')'
+//         | '(' 'table' id? ('(' 'export' name ')')*
+//               reftype '(' 'elem' (elemexpr* | funcidx*) ')' ')'
+template<typename Ctx> MaybeResult<> table(Ctx& ctx) {
+  auto pos = ctx.in.getPos();
+  if (!ctx.in.takeSExprStart("table"sv)) {
+    return {};
+  }
+
+  Name name;
+  if (auto id = ctx.in.takeID()) {
+    name = *id;
+  }
+
+  auto exports = inlineExports(ctx.in);
+  CHECK_ERR(exports);
+
+  auto import = inlineImport(ctx.in);
+  CHECK_ERR(import);
+
+  // Reftype if we have inline elements.
+  auto type = reftype(ctx);
+  CHECK_ERR(type);
+
+  std::optional<typename Ctx::TableTypeT> ttype;
+  std::optional<typename Ctx::ElemListT> elems;
+  if (type) {
+    // We should have inline elements.
+    if (!ctx.in.takeSExprStart("elem"sv)) {
+      return ctx.in.err("expected table limits or inline elements");
+    }
+    if (import) {
+      return ctx.in.err("imported tables cannot have inline elements");
+    }
+
+    auto list = ctx.makeElemList(*type);
+    bool foundElem = false;
+    while (auto elem = maybeElemexpr(ctx)) {
+      CHECK_ERR(elem);
+      ctx.appendElem(list, *elem);
+      foundElem = true;
+    }
+
+    // If there were no elemexprs, then maybe we have funcidxs instead.
+    if (!foundElem) {
+      while (auto func = maybeFuncidx(ctx)) {
+        CHECK_ERR(func);
+        ctx.appendFuncElem(list, *func);
+      }
+    }
+
+    if (!ctx.in.takeRParen()) {
+      return ctx.in.err("expected end of inline elems");
+    }
+    ttype = ctx.makeTableType(ctx.getLimitsFromElems(list), *type);
+    elems = std::move(list);
+  } else {
+    auto tabtype = tabletype(ctx);
+    CHECK_ERR(tabtype);
+    ttype = *tabtype;
+  }
+
+  if (!ctx.in.takeRParen()) {
+    return ctx.in.err("expected end of table declaration");
+  }
+
+  CHECK_ERR(ctx.addTable(name, *exports, import.getPtr(), *ttype, pos));
+
+  if (elems) {
+    CHECK_ERR(ctx.addImplicitElems(*type, std::move(*elems)));
+  }
+
+  return Ok{};
+}
+
 // mem ::= '(' 'memory' id? ('(' 'export' name ')')*
 //             ('(' 'data' b:datastring ')' | memtype) ')'
 //       | '(' 'memory' id? ('(' 'export' name ')')*
@@ -2122,6 +2263,120 @@ template<typename Ctx> MaybeResult<> global(Ctx& ctx) {
   return Ok{};
 }
 
+// elemexpr ::= '(' 'item' expr ')' | '(' instr ')'
+template<typename Ctx>
+MaybeResult<typename Ctx::ExprT> maybeElemexpr(Ctx& ctx) {
+  MaybeResult<typename Ctx::ExprT> result;
+  if (ctx.in.takeSExprStart("item"sv)) {
+    result = expr(ctx);
+  } else if (ctx.in.takeLParen()) {
+    // TODO: `instr` should included both folded and unfolded instrs.
+    if (auto inst = instr(ctx)) {
+      CHECK_ERR(inst);
+    } else {
+      return ctx.in.err("expected instruction");
+    }
+    result = ctx.makeExpr();
+  } else {
+    return {};
+  }
+  CHECK_ERR(result);
+  if (!ctx.in.takeRParen()) {
+    return ctx.in.err("expected end of element expression");
+  }
+  return result;
+}
+
+// elemlist ::= reftype elemexpr* | 'func' funcidx*
+//            | funcidx* (iff the tableuse is omitted)
+template<typename Ctx>
+Result<typename Ctx::ElemListT> elemlist(Ctx& ctx, bool legacy) {
+  if (auto type = reftype(ctx)) {
+    auto res = ctx.makeElemList(*type);
+    while (auto elem = maybeElemexpr(ctx)) {
+      CHECK_ERR(elem);
+      ctx.appendElem(res, *elem);
+    }
+    return res;
+  } else if (ctx.in.takeKeyword("func"sv) || legacy) {
+    auto res = ctx.makeFuncElemList();
+    while (auto func = maybeFuncidx(ctx)) {
+      CHECK_ERR(func);
+      ctx.appendFuncElem(res, *func);
+    }
+    return res;
+  }
+  return ctx.in.err("expected element list");
+}
+
+// elem ::= '(' 'elem' id? x:tableuse? ('(' ('offset' e:expr | e:instr) ')')?
+//               elemlist ')'
+//        | '(' 'elem' id? 'declare' elemlist ')'
+template<typename Ctx> MaybeResult<> elem(Ctx& ctx) {
+  auto pos = ctx.in.getPos();
+  if (!ctx.in.takeSExprStart("elem"sv)) {
+    return {};
+  }
+
+  Name name;
+  if (auto id = ctx.in.takeID()) {
+    name = *id;
+  }
+
+  bool isDeclare = false;
+  MaybeResult<typename Ctx::TableIdxT> table;
+  std::optional<typename Ctx::ExprT> offset;
+
+  if (ctx.in.takeKeyword("declare"sv)) {
+    isDeclare = true;
+  } else {
+    table = maybeTableuse(ctx);
+    CHECK_ERR(table);
+
+    if (ctx.in.takeSExprStart("offset")) {
+      auto off = expr(ctx);
+      CHECK_ERR(off);
+      offset = *off;
+    } else {
+      // This may be an abbreviated offset instruction or it may be the
+      // beginning of the elemlist.
+      auto beforeLParen = ctx.in.getPos();
+      if (ctx.in.takeLParen()) {
+        if (auto inst = instr(ctx)) {
+          CHECK_ERR(inst);
+          auto off = ctx.makeExpr();
+          CHECK_ERR(off);
+          offset = *off;
+        } else {
+          // This must be the beginning of the elemlist instead.
+          ctx.in.lexer.setIndex(beforeLParen);
+        }
+      }
+    }
+    if (offset && !ctx.in.takeRParen()) {
+      return ctx.in.err("expected end of offset expression");
+    }
+  }
+
+  // If there is no explicit tableuse, we can use the legacy elemlist format.
+  bool legacy = !table;
+  auto elems = elemlist(ctx, legacy);
+  CHECK_ERR(elems);
+
+  if (!ctx.in.takeRParen()) {
+    return ctx.in.err("expected end of element segment");
+  }
+
+  if (isDeclare) {
+    CHECK_ERR(ctx.addDeclareElem(name, std::move(*elems), pos));
+  } else {
+    CHECK_ERR(
+      ctx.addElem(name, table.getPtr(), offset, std::move(*elems), pos));
+  }
+
+  return Ok{};
+}
+
 // datastring ::= (b:string)* => concat(b*)
 template<typename Ctx> Result<typename Ctx::DataStringT> datastring(Ctx& ctx) {
   auto data = ctx.makeDataString();
@@ -2236,6 +2491,10 @@ template<typename Ctx> MaybeResult<> modulefield(Ctx& ctx) {
     CHECK_ERR(res);
     return Ok{};
   }
+  if (auto res = table(ctx)) {
+    CHECK_ERR(res);
+    return Ok{};
+  }
   if (auto res = memory(ctx)) {
     CHECK_ERR(res);
     return Ok{};
@@ -2244,6 +2503,10 @@ template<typename Ctx> MaybeResult<> modulefield(Ctx& ctx) {
     CHECK_ERR(res);
     return Ok{};
   }
+  if (auto res = elem(ctx)) {
+    CHECK_ERR(res);
+    return Ok{};
+  }
   if (auto res = data(ctx)) {
     CHECK_ERR(res);
     return Ok{};
diff --git a/src/parser/wat-parser.cpp b/src/parser/wat-parser.cpp
index be3bca5c8..cc0f582fc 100644
--- a/src/parser/wat-parser.cpp
+++ b/src/parser/wat-parser.cpp
@@ -132,6 +132,7 @@ Result<> parseModule(Module& wasm, std::string_view input) {
   // Parse implicit type definitions and map typeuses without explicit types to
   // the correct types.
   std::unordered_map<Index, HeapType> implicitTypes;
+
   {
     ParseImplicitTypeDefsCtx ctx(input, types, implicitTypes, *typeIndices);
     for (Index pos : decls.implicitTypeDefs) {
@@ -142,18 +143,31 @@ Result<> parseModule(Module& wasm, std::string_view input) {
 
   {
     // Parse module-level types.
-    ParseModuleTypesCtx ctx(input, wasm, types, implicitTypes, *typeIndices);
+    ParseModuleTypesCtx ctx(input,
+                            wasm,
+                            types,
+                            implicitTypes,
+                            decls.implicitElemIndices,
+                            *typeIndices);
     CHECK_ERR(parseDefs(ctx, decls.funcDefs, func));
+    CHECK_ERR(parseDefs(ctx, decls.tableDefs, table));
     CHECK_ERR(parseDefs(ctx, decls.memoryDefs, memory));
     CHECK_ERR(parseDefs(ctx, decls.globalDefs, global));
+    CHECK_ERR(parseDefs(ctx, decls.elemDefs, elem));
     CHECK_ERR(parseDefs(ctx, decls.tagDefs, tag));
-    // TODO: Parse types of other module elements.
   }
   {
     // Parse definitions.
     // TODO: Parallelize this.
-    ParseDefsCtx ctx(input, wasm, types, implicitTypes, *typeIndices);
+    ParseDefsCtx ctx(input,
+                     wasm,
+                     types,
+                     implicitTypes,
+                     decls.implicitElemIndices,
+                     *typeIndices);
+    CHECK_ERR(parseDefs(ctx, decls.tableDefs, table));
     CHECK_ERR(parseDefs(ctx, decls.globalDefs, global));
+    CHECK_ERR(parseDefs(ctx, decls.elemDefs, elem));
     CHECK_ERR(parseDefs(ctx, decls.dataDefs, data));
 
     for (Index i = 0; i < decls.funcDefs.size(); ++i) {
diff --git a/src/support/result.h b/src/support/result.h
index acbf92966..ab71d3a53 100644
--- a/src/support/result.h
+++ b/src/support/result.h
@@ -75,6 +75,9 @@ template<typename T = Ok> struct MaybeResult {
   // conditions where errors should not get lost.
   operator bool() const { return !std::holds_alternative<None>(val); }
 
+  MaybeResult<T>& operator=(const MaybeResult<T>&) = default;
+  MaybeResult<T>& operator=(MaybeResult<T>&&) = default;
+
   Err* getErr() { return std::get_if<Err>(&val); }
   T& operator*() { return *std::get_if<T>(&val); }
   T* operator->() { return std::get_if<T>(&val); }
diff --git a/test/lit/wat-kitchen-sink.wast b/test/lit/wat-kitchen-sink.wast
index f23d494af..8da499174 100644
--- a/test/lit/wat-kitchen-sink.wast
+++ b/test/lit/wat-kitchen-sink.wast
@@ -25,18 +25,6 @@
 
   ;; CHECK:      (type $8 (func (param anyref)))
 
-  ;; CHECK:      (type $many (sub (func (param i32 i64 f32 f64) (result anyref (ref func)))))
-
-  ;; CHECK:      (type $10 (func))
-
-  ;; CHECK:      (type $11 (func (param i32)))
-
-  ;; CHECK:      (type $a0 (array i32))
-
-  ;; CHECK:      (type $13 (func (param i32 i32 i32)))
-
-  ;; CHECK:      (type $14 (func (param v128 i32) (result v128)))
-
   ;; CHECK:      (rec
   ;; CHECK-NEXT:  (type $s0 (struct ))
   (type $s0 (sub (struct)))
@@ -46,6 +34,18 @@
 
  (rec)
 
+ ;; CHECK:      (type $many (sub (func (param i32 i64 f32 f64) (result anyref (ref func)))))
+
+ ;; CHECK:      (type $12 (func))
+
+ ;; CHECK:      (type $13 (func (param i32)))
+
+ ;; CHECK:      (type $a0 (array i32))
+
+ ;; CHECK:      (type $15 (func (param i32 i32 i32)))
+
+ ;; CHECK:      (type $16 (func (param v128 i32) (result v128)))
+
  ;; CHECK:      (type $packed-i8 (array (mut i8)))
 
  ;; CHECK:      (type $packed-i16 (array (mut i16)))
@@ -167,6 +167,9 @@
  ;; imported memories
  (memory (export "mem") (export "mem2") (import "" "mem") 0)
 
+ ;; imported tables
+ (table (export "tab") (export "tab2") (import "" "tab") 0 funcref)
+
  ;; imported functions
  (func (export "f5.0") (export "f5.1") (import "mod" "f5"))
 
@@ -180,6 +183,8 @@
 
  ;; CHECK:      (import "" "mem" (memory $mimport$0 0))
 
+ ;; CHECK:      (import "" "tab" (table $timport$0 0 funcref))
+
  ;; CHECK:      (import "mod" "g1" (global $g1 i32))
 
  ;; CHECK:      (import "mod" "g2" (global $g2 (mut i64)))
@@ -237,10 +242,52 @@
 
  (data (memory 4) (offset i64.const 0) "64-bit")
 
- ;; tags
- (tag)
+ ;; tables
  ;; CHECK:      (data $1 (memory $mem-i64) (i64.const 0) "64-bit")
 
+ ;; CHECK:      (table $funcs 1 2 funcref)
+ (table $funcs 1 2 (ref null func))
+
+ ;; CHECK:      (table $table-any 3 3 anyref)
+ (table $table-any anyref (elem (item i32.const 0 ref.i31) (ref.null any) (item (ref.i31 (i32.const 0)))))
+
+ ;; elems
+ ;; CHECK:      (elem $implicit-elem (table $table-any) (i32.const 0) anyref (ref.i31
+ ;; CHECK-NEXT:  (i32.const 0)
+ ;; CHECK-NEXT: ) (ref.null none) (ref.i31
+ ;; CHECK-NEXT:  (i32.const 0)
+ ;; CHECK-NEXT: ))
+
+ ;; CHECK:      (elem $implicit-table (table $timport$0) (i32.const 0) funcref (ref.null nofunc) (ref.null nofunc) (ref.null nofunc))
+ (elem $implicit-table (offset i32.const 0) funcref (ref.null func) (item ref.null func) (item (ref.null func)))
+
+ ;; CHECK:      (elem $implicit-table-2 (table $timport$0) (i32.const 1) func)
+ (elem $implicit-table-2 (i32.const 1) funcref)
+
+ ;; CHECK:      (elem $implicit-table-indices (table $timport$0) (i32.const 2) func $fimport$0 $1 $f1)
+ (elem $implicit-table-indices (offset (i32.const 2)) func 0 1 2)
+
+ ;; CHECK:      (elem $implicit-table-legacy-indices (table $timport$0) (i32.const 3) func $fimport$0 $1 $f1 $f2)
+ (elem $implicit-table-legacy-indices (i32.const 3) 0 1 2 3)
+
+ ;; CHECK:      (elem $explicit-table (table $timport$0) (i32.const 0) funcref (ref.null nofunc))
+ (elem $explicit-table (table 0) (offset (i32.const 0)) funcref (item ref.null func))
+
+ ;; CHECK:      (elem $explicit-table-named (table $table-any) (i32.const 1) anyref)
+ (elem $explicit-table-named (table $table-any) (i32.const 1) anyref)
+
+ ;; CHECK:      (elem $passive (ref null $s0) (struct.new_default $s0) (struct.new_default $s0))
+ (elem $passive (ref null $s0) (item struct.new $s0) (struct.new $s0))
+
+ ;; CHECK:      (elem $passive-2 anyref (struct.new_default $s0) (struct.new_default $s0))
+ (elem $passive-2 anyref (item struct.new $s0) (struct.new $s0))
+
+ (elem $declare declare func 0 1 2 3)
+
+ (elem $declare-2 declare funcref (item ref.func 0) (ref.func 1) (item (ref.func 2)))
+
+ ;; tags
+ (tag)
  ;; CHECK:      (elem declare func $ref-func)
 
  ;; CHECK:      (tag $1)
@@ -265,6 +312,10 @@
 
  ;; CHECK:      (export "mem2" (memory $mimport$0))
 
+ ;; CHECK:      (export "tab" (table $timport$0))
+
+ ;; CHECK:      (export "tab2" (table $timport$0))
+
  ;; CHECK:      (export "f5.0" (func $fimport$0))
 
  ;; CHECK:      (export "f5.1" (func $fimport$0))
@@ -277,11 +328,11 @@
  ;; CHECK-NEXT:  (nop)
  ;; CHECK-NEXT: )
 
- ;; CHECK:      (func $f1 (type $11) (param $0 i32)
+ ;; CHECK:      (func $f1 (type $13) (param $0 i32)
  ;; CHECK-NEXT:  (nop)
  ;; CHECK-NEXT: )
  (func $f1 (param i32))
- ;; CHECK:      (func $f2 (type $11) (param $x i32)
+ ;; CHECK:      (func $f2 (type $13) (param $x i32)
  ;; CHECK-NEXT:  (nop)
  ;; CHECK-NEXT: )
  (func $f2 (param $x i32))
@@ -2294,7 +2345,7 @@
   drop
  )
 
- ;; CHECK:      (func $select (type $13) (param $0 i32) (param $1 i32) (param $2 i32)
+ ;; CHECK:      (func $select (type $15) (param $0 i32) (param $1 i32) (param $2 i32)
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (select
  ;; CHECK-NEXT:    (local.get $0)
@@ -2586,7 +2637,7 @@
   i32x4.extract_lane 3
  )
 
- ;; CHECK:      (func $simd-replace (type $14) (param $0 v128) (param $1 i32) (result v128)
+ ;; CHECK:      (func $simd-replace (type $16) (param $0 v128) (param $1 i32) (result v128)
  ;; CHECK-NEXT:  (i32x4.replace_lane 2
  ;; CHECK-NEXT:   (local.get $0)
  ;; CHECK-NEXT:   (local.get $1)
@@ -2624,7 +2675,7 @@
   v128.bitselect
  )
 
- ;; CHECK:      (func $simd-shift (type $14) (param $0 v128) (param $1 i32) (result v128)
+ ;; CHECK:      (func $simd-shift (type $16) (param $0 v128) (param $1 i32) (result v128)
  ;; CHECK-NEXT:  (i8x16.shl
  ;; CHECK-NEXT:   (local.get $0)
  ;; CHECK-NEXT:   (local.get $1)
@@ -2679,7 +2730,7 @@
   v128.store64_lane 4 align=4 0
  )
 
- ;; CHECK:      (func $memory-init (type $13) (param $0 i32) (param $1 i32) (param $2 i32)
+ ;; CHECK:      (func $memory-init (type $15) (param $0 i32) (param $1 i32) (param $2 i32)
  ;; CHECK-NEXT:  (memory.init $mem-i32 $passive
  ;; CHECK-NEXT:   (local.get $0)
  ;; CHECK-NEXT:   (local.get $1)