[Parser] Parse tags and throw (#6126)

Also fix the parser to correctly error if an imported item appears after a
non-imported item and make the corresponding fix to the test.

5 files changed, 144 insertions, 11 deletions

diff --git a/src/parser/context-decls.cpp b/src/parser/context-decls.cpp
index 17b389488..721127614 100644
--- a/src/parser/context-decls.cpp
+++ b/src/parser/context-decls.cpp
@@ -69,9 +69,7 @@ Result<> ParseDeclsCtx::addFunc(Name name,
                                 TypeUseT type,
                                 std::optional<LocalsT>,
                                 Index pos) {
-  if (import && hasNonImport) {
-    return in.err(pos, "import after non-import");
-  }
+  CHECK_ERR(checkImport(pos, import));
   auto f = addFuncDecl(pos, name, import);
   CHECK_ERR(f);
   CHECK_ERR(addExports(in, wasm, *f, exports, ExternalKind::Function));
@@ -109,9 +107,7 @@ Result<> ParseDeclsCtx::addMemory(Name name,
                                   ImportNames* import,
                                   MemType type,
                                   Index pos) {
-  if (import && hasNonImport) {
-    return in.err(pos, "import after non-import");
-  }
+  CHECK_ERR(checkImport(pos, import));
   auto m = addMemoryDecl(pos, name, import, type);
   CHECK_ERR(m);
   CHECK_ERR(addExports(in, wasm, *m, exports, ExternalKind::Memory));
@@ -156,9 +152,7 @@ Result<> ParseDeclsCtx::addGlobal(Name name,
                                   GlobalTypeT,
                                   std::optional<ExprT>,
                                   Index pos) {
-  if (import && hasNonImport) {
-    return in.err(pos, "import after non-import");
-  }
+  CHECK_ERR(checkImport(pos, import));
   auto g = addGlobalDecl(pos, name, import);
   CHECK_ERR(g);
   CHECK_ERR(addExports(in, wasm, *g, exports, ExternalKind::Global));
@@ -190,4 +184,36 @@ Result<> ParseDeclsCtx::addData(Name name,
   return Ok{};
 }
 
+Result<Tag*>
+ParseDeclsCtx::addTagDecl(Index pos, Name name, ImportNames* importNames) {
+  auto t = std::make_unique<Tag>();
+  if (name) {
+    if (wasm.getTagOrNull(name)) {
+      // TODO: if the existing tag is not explicitly named, fix its name and
+      // continue.
+      return in.err(pos, "repeated tag name");
+    }
+    t->setExplicitName(name);
+  } else {
+    name = (importNames ? "timport$" : "") + std::to_string(tagCounter++);
+    name = Names::getValidTagName(wasm, name);
+    t->name = name;
+  }
+  applyImportNames(*t, importNames);
+  return wasm.addTag(std::move(t));
+}
+
+Result<> ParseDeclsCtx::addTag(Name name,
+                               const std::vector<Name>& exports,
+                               ImportNames* import,
+                               TypeUseT type,
+                               Index pos) {
+  CHECK_ERR(checkImport(pos, import));
+  auto t = addTagDecl(pos, name, import);
+  CHECK_ERR(t);
+  CHECK_ERR(addExports(in, wasm, *t, exports, ExternalKind::Tag));
+  tagDefs.push_back({name, pos, Index(tagDefs.size())});
+  return Ok{};
+}
+
 } // namespace wasm::WATParser
diff --git a/src/parser/contexts.h b/src/parser/contexts.h
index 192442c84..ed4d1283c 100644
--- a/src/parser/contexts.h
+++ b/src/parser/contexts.h
@@ -286,6 +286,7 @@ struct NullInstrParserCtx {
   using MemoryIdxT = Ok;
   using DataIdxT = Ok;
   using LabelIdxT = Ok;
+  using TagIdxT = Ok;
 
   using MemargT = Ok;
 
@@ -309,6 +310,8 @@ struct NullInstrParserCtx {
   DataIdxT getDataFromName(Name) { return Ok{}; }
   LabelIdxT getLabelFromIdx(uint32_t) { return Ok{}; }
   LabelIdxT getLabelFromName(Name) { return Ok{}; }
+  TagIdxT getTagFromIdx(uint32_t) { return Ok{}; }
+  TagIdxT getTagFromName(Name) { return Ok{}; }
 
   MemargT getMemarg(uint64_t, uint32_t) { return Ok{}; }
 
@@ -393,6 +396,7 @@ struct NullInstrParserCtx {
   Result<> makeRefIsNull(Index) { return Ok{}; }
   Result<> makeRefFunc(Index, FuncIdxT) { return Ok{}; }
   Result<> makeRefEq(Index) { return Ok{}; }
+  Result<> makeThrow(Index, TagIdxT) { return Ok{}; }
   template<typename HeapTypeT> Result<> makeCallRef(Index, HeapTypeT, bool) {
     return Ok{};
   }
@@ -480,6 +484,7 @@ struct ParseDeclsCtx : NullTypeParserCtx, NullInstrParserCtx {
   std::vector<DefPos> memoryDefs;
   std::vector<DefPos> globalDefs;
   std::vector<DefPos> dataDefs;
+  std::vector<DefPos> tagDefs;
 
   // Positions of typeuses that might implicitly define new types.
   std::vector<Index> implicitTypeDefs;
@@ -489,10 +494,22 @@ struct ParseDeclsCtx : NullTypeParserCtx, NullInstrParserCtx {
   int memoryCounter = 0;
   int globalCounter = 0;
   int dataCounter = 0;
+  int tagCounter = 0;
 
   // Used to verify that all imports come before all non-imports.
   bool hasNonImport = false;
 
+  Result<> checkImport(Index pos, ImportNames* import) {
+    if (import) {
+      if (hasNonImport) {
+        return in.err(pos, "import after non-import");
+      }
+    } else {
+      hasNonImport = true;
+    }
+    return Ok{};
+  }
+
   ParseDeclsCtx(std::string_view in, Module& wasm) : in(in), wasm(wasm) {}
 
   void addFuncType(SignatureT) {}
@@ -568,6 +585,14 @@ struct ParseDeclsCtx : NullTypeParserCtx, NullInstrParserCtx {
                    std::optional<ExprT>,
                    std::vector<char>&& data,
                    Index pos);
+
+  Result<Tag*> addTagDecl(Index pos, Name name, ImportNames* importNames);
+
+  Result<> addTag(Name name,
+                  const std::vector<Name>& exports,
+                  ImportNames* import,
+                  TypeUseT type,
+                  Index pos);
 };
 
 // Phase 2: Parse type definitions into a TypeBuilder.
@@ -814,6 +839,16 @@ struct ParseModuleTypesCtx : TypeParserCtx<ParseModuleTypesCtx>,
     g->type = type.type;
     return Ok{};
   }
+
+  Result<>
+  addTag(Name, const std::vector<Name>&, ImportNames*, TypeUse use, Index pos) {
+    auto& t = wasm.tags[index];
+    if (!use.type.isSignature()) {
+      return in.err(pos, "tag type must be a signature");
+    }
+    t->sig = use.type.getSignature();
+    return Ok{};
+  }
 };
 
 // Phase 5: Parse module element definitions, including instructions.
@@ -830,6 +865,7 @@ struct ParseDefsCtx : TypeParserCtx<ParseDefsCtx> {
   using GlobalIdxT = Name;
   using MemoryIdxT = Name;
   using DataIdxT = Name;
+  using TagIdxT = Name;
 
   using MemargT = Memarg;
 
@@ -990,6 +1026,20 @@ struct ParseDefsCtx : TypeParserCtx<ParseDefsCtx> {
     return irBuilder.getLabelIndex(name);
   }
 
+  Result<Name> getTagFromIdx(uint32_t idx) {
+    if (idx >= wasm.tags.size()) {
+      return in.err("tag index out of bounds");
+    }
+    return wasm.tags[idx]->name;
+  }
+
+  Result<Name> getTagFromName(Name name) {
+    if (!wasm.getTagOrNull(name)) {
+      return in.err("tag $" + name.toString() + " does not exist");
+    }
+    return name;
+  }
+
   Result<TypeUseT> makeTypeUse(Index pos,
                                std::optional<HeapTypeT> type,
                                ParamsT* params,
@@ -1009,6 +1059,7 @@ struct ParseDefsCtx : TypeParserCtx<ParseDefsCtx> {
                      Index);
   Result<>
   addData(Name, Name* mem, std::optional<ExprT> offset, DataStringT, Index pos);
+
   Result<Index> addScratchLocal(Index pos, Type type) {
     if (!func) {
       return in.err(pos,
@@ -1288,6 +1339,10 @@ struct ParseDefsCtx : TypeParserCtx<ParseDefsCtx> {
 
   Result<> makeRefEq(Index pos) { return withLoc(pos, irBuilder.makeRefEq()); }
 
+  Result<> makeThrow(Index pos, Name tag) {
+    return withLoc(pos, irBuilder.makeThrow(tag));
+  }
+
   Result<> makeCallRef(Index pos, HeapType type, bool isReturn) {
     return withLoc(pos, irBuilder.makeCallRef(type, isReturn));
   }
diff --git a/src/parser/parsers.h b/src/parser/parsers.h
index 41e625657..9201314dc 100644
--- a/src/parser/parsers.h
+++ b/src/parser/parsers.h
@@ -174,6 +174,7 @@ template<typename Ctx> MaybeResult<typename Ctx::MemoryIdxT> maybeMemuse(Ctx&);
 template<typename Ctx> Result<typename Ctx::GlobalIdxT> globalidx(Ctx&);
 template<typename Ctx> Result<typename Ctx::LocalIdxT> localidx(Ctx&);
 template<typename Ctx> Result<typename Ctx::LabelIdxT> labelidx(Ctx&);
+template<typename Ctx> Result<typename Ctx::TagIdxT> tagidx(Ctx&);
 template<typename Ctx> Result<typename Ctx::TypeUseT> typeuse(Ctx&);
 MaybeResult<ImportNames> inlineImport(ParseInput&);
 Result<std::vector<Name>> inlineExports(ParseInput&);
@@ -186,6 +187,7 @@ template<typename Ctx> MaybeResult<> memory(Ctx&);
 template<typename Ctx> MaybeResult<> global(Ctx&);
 template<typename Ctx> Result<typename Ctx::DataStringT> datastring(Ctx&);
 template<typename Ctx> MaybeResult<> data(Ctx&);
+template<typename Ctx> MaybeResult<> tag(Ctx&);
 template<typename Ctx> MaybeResult<> modulefield(Ctx&);
 template<typename Ctx> Result<> module(Ctx&);
 
@@ -1274,7 +1276,9 @@ Result<> makeTryOrCatchBody(Ctx& ctx, Index pos, Type type, bool isTry) {
 }
 
 template<typename Ctx> Result<> makeThrow(Ctx& ctx, Index pos) {
-  return ctx.in.err("unimplemented instruction");
+  auto tag = tagidx(ctx);
+  CHECK_ERR(tag);
+  return ctx.makeThrow(pos, *tag);
 }
 
 template<typename Ctx> Result<> makeRethrow(Ctx& ctx, Index pos) {
@@ -1627,6 +1631,18 @@ template<typename Ctx> Result<typename Ctx::LabelIdxT> labelidx(Ctx& ctx) {
   return ctx.in.err("expected label index or identifier");
 }
 
+// tagidx ::= x:u32 => x
+//          | v:id => x (if tags[x] = v)
+template<typename Ctx> Result<typename Ctx::TagIdxT> tagidx(Ctx& ctx) {
+  if (auto x = ctx.in.takeU32()) {
+    return ctx.getTagFromIdx(*x);
+  }
+  if (auto id = ctx.in.takeID()) {
+    return ctx.getTagFromName(*id);
+  }
+  return ctx.in.err("expected tag index or identifier");
+}
+
 // typeuse ::= '(' 'type' x:typeidx ')'                                => x, []
 //                 (if typedefs[x] = [t1*] -> [t2*]
 //           | '(' 'type' x:typeidx ')' ((t1,IDs):param)* (t2:result)* => x, IDs
@@ -2011,6 +2027,36 @@ template<typename Ctx> MaybeResult<> data(Ctx& ctx) {
   return Ok{};
 }
 
+// tag ::= '(' 'tag' id? ('(' 'export' name ')')*
+//            ('(' 'import' mod:name nm:name ')')? typeuse ')'
+template<typename Ctx> MaybeResult<> tag(Ctx& ctx) {
+  auto pos = ctx.in.getPos();
+  if (!ctx.in.takeSExprStart("tag"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);
+
+  auto type = typeuse(ctx);
+  CHECK_ERR(type);
+
+  if (!ctx.in.takeRParen()) {
+    return ctx.in.err("expected end of tag");
+  }
+
+  CHECK_ERR(ctx.addTag(name, *exports, import.getPtr(), *type, pos));
+  return Ok{};
+}
+
 // modulefield ::= deftype
 //               | import
 //               | func
@@ -2021,6 +2067,7 @@ template<typename Ctx> MaybeResult<> data(Ctx& ctx) {
 //               | start
 //               | elem
 //               | data
+//               | tag
 template<typename Ctx> MaybeResult<> modulefield(Ctx& ctx) {
   if (auto t = ctx.in.peek(); !t || t->isRParen()) {
     return {};
@@ -2045,6 +2092,10 @@ template<typename Ctx> MaybeResult<> modulefield(Ctx& ctx) {
     CHECK_ERR(res);
     return Ok{};
   }
+  if (auto res = tag(ctx)) {
+    CHECK_ERR(res);
+    return Ok{};
+  }
   return ctx.in.err("unrecognized module field");
 }
 
diff --git a/src/parser/wat-parser.cpp b/src/parser/wat-parser.cpp
index 7e106d3b9..be3bca5c8 100644
--- a/src/parser/wat-parser.cpp
+++ b/src/parser/wat-parser.cpp
@@ -146,6 +146,7 @@ Result<> parseModule(Module& wasm, std::string_view input) {
     CHECK_ERR(parseDefs(ctx, decls.funcDefs, func));
     CHECK_ERR(parseDefs(ctx, decls.memoryDefs, memory));
     CHECK_ERR(parseDefs(ctx, decls.globalDefs, global));
+    CHECK_ERR(parseDefs(ctx, decls.tagDefs, tag));
     // TODO: Parse types of other module elements.
   }
   {
diff --git a/src/parser/wat-parser.h b/src/parser/wat-parser.h
index d3ad8d7f3..b31523af9 100644
--- a/src/parser/wat-parser.h
+++ b/src/parser/wat-parser.h
@@ -29,4 +29,4 @@ Result<> parseModule(Module& wasm, std::string_view in);
 
 } // namespace wasm::WATParser
 
-#endif // paser_wat_parser_h
+#endif // parser_wat_parser_h