[EH] Improve catch validation (#4315)

This improves validation of `catch` bodies mostly by checking the
validity of `pop`s.

For every `catch` body:
- Checks if its tag exists
- If the tag's type is none:
  - Ensures there shouldn't be any `pop`s
- If the tag's type is not none:
  - Checks if there's a single `pop` within the catch body
  - Checks if the tag type matches the `pop`'s type
  - Checks if the `pop`'s location is valid

For every `catch_all` body:
- Ensures there shuldn't be any `pop`s

This uncovers several bugs related to `pop`s in existing tests, which
this PR also fixes.

5 files changed, 177 insertions, 0 deletions

diff --git a/src/ir/CMakeLists.txt b/src/ir/CMakeLists.txt
index f598f3d72..b625cebe7 100644
--- a/src/ir/CMakeLists.txt
+++ b/src/ir/CMakeLists.txt
@@ -2,6 +2,7 @@ FILE(GLOB ir_HEADERS *.h)
 set(ir_SOURCES
   ExpressionAnalyzer.cpp
   ExpressionManipulator.cpp
+  eh-utils.cpp
   intrinsics.cpp
   names.cpp
   properties.cpp
diff --git a/src/ir/eh-utils.cpp b/src/ir/eh-utils.cpp
new file mode 100644
index 000000000..de85478a2
--- /dev/null
+++ b/src/ir/eh-utils.cpp
@@ -0,0 +1,71 @@
+/*
+ * Copyright 2021 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.
+ */
+
+#include "ir/eh-utils.h"
+#include "ir/branch-utils.h"
+
+namespace wasm {
+
+namespace EHUtils {
+
+bool isPopValid(Expression* catchBody) {
+  Expression* firstChild = nullptr;
+  auto* block = catchBody->dynCast<Block>();
+  if (!block) {
+    firstChild = catchBody;
+  } else {
+    // When there are multiple expressions within a catch body, an implicit
+    // block is created within it for convenience purposes, and if there are no
+    // branches that targets the block, it will be omitted when written back.
+    // But if there is a branch targetting this block, this block cannot be
+    // removed, and 'pop''s location will be like
+    // (catch $e
+    //   (block $l0
+    //     (pop i32) ;; within a block!
+    //     (br $l0)
+    //     ...
+    //   )
+    // )
+    // which is invalid.
+    if (BranchUtils::BranchSeeker::has(block, block->name)) {
+      return false;
+    }
+    // There should be a pop somewhere
+    if (block->list.empty()) {
+      return false;
+    }
+    firstChild = *block->list.begin();
+  }
+
+  // Go down the line for the first child until we reach a leaf. A pop should be
+  // in that first-decendent line.
+  while (true) {
+    if (firstChild->is<Pop>()) {
+      return true;
+    }
+    // We use ValueChildIterator in order not to go into block/loop/try/if
+    // bodies, because a pop cannot be in those control flow expressions.
+    ValueChildIterator it(firstChild);
+    if (it.begin() == it.end()) {
+      return false;
+    }
+    firstChild = *it.begin();
+  }
+}
+
+} // namespace EHUtils
+
+} // namespace wasm
diff --git a/src/ir/eh-utils.h b/src/ir/eh-utils.h
new file mode 100644
index 000000000..844fda448
--- /dev/null
+++ b/src/ir/eh-utils.h
@@ -0,0 +1,38 @@
+/*
+ * Copyright 2021 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.
+ */
+
+#ifndef wasm_ir_eh_h
+#define wasm_ir_eh_h
+
+namespace wasm {
+
+class Expression;
+
+namespace EHUtils {
+
+// Returns true if a 'pop' instruction exists in a valid location, which means
+// right after a 'catch' instruction in binary writing order.
+// - This assumes there should be at least a single pop. So given a catch body
+//   whose tag type is void or a catch_all's body, this returns false.
+// - This returns true even if there are more pops after the first one within a
+//   catch body, which is invalid. That will be taken care of in validation.
+bool isPopValid(Expression* catchBody);
+
+} // namespace EHUtils
+
+} // namespace wasm
+
+#endif // wasm_ir_eh_h
diff --git a/src/ir/iteration.h b/src/ir/iteration.h
index b3553f1ec..29d183678 100644
--- a/src/ir/iteration.h
+++ b/src/ir/iteration.h
@@ -53,6 +53,8 @@ template<class Specific> class AbstractChildIterator {
       return index != other.index || &parent != &(other.parent);
     }
 
+    bool operator==(const Iterator& other) const { return !(*this != other); }
+
     void operator++() { index++; }
 
     Expression*& operator*() {
diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp
index bb0e99cc2..86b537bf5 100644
--- a/src/wasm/wasm-validator.cpp
+++ b/src/wasm/wasm-validator.cpp
@@ -19,6 +19,7 @@
 #include <sstream>
 #include <unordered_set>
 
+#include "ir/eh-utils.h"
 #include "ir/features.h"
 #include "ir/global-utils.h"
 #include "ir/intrinsics.h"
@@ -2143,6 +2144,70 @@ void FunctionValidator::visitTry(Try* curr) {
                 curr,
                 "try cannot have both catch and delegate at the same time");
 
+  // Given a catch body, find pops corresponding to the catch
+  auto findPops = [](Expression* expr) {
+    SmallVector<Pop*, 1> pops;
+    SmallVector<Expression*, 8> work;
+    work.push_back(expr);
+    while (!work.empty()) {
+      auto* curr = work.back();
+      work.pop_back();
+      if (auto* pop = curr->dynCast<Pop>()) {
+        pops.push_back(pop);
+      } else if (auto* try_ = curr->dynCast<Try>()) {
+        // We don't go into inner catch bodies; pops in inner catch bodies
+        // belong to the inner catches
+        work.push_back(try_->body);
+      } else {
+        for (auto* child : ChildIterator(curr)) {
+          work.push_back(child);
+        }
+      }
+    }
+    return pops;
+  };
+
+  for (Index i = 0; i < curr->catchTags.size(); i++) {
+    Name tagName = curr->catchTags[i];
+    auto* tag = getModule()->getTagOrNull(tagName);
+    if (!shouldBeTrue(tag != nullptr, curr, "")) {
+      getStream() << "tag name is invalid: " << tagName << "\n";
+    }
+
+    auto* catchBody = curr->catchBodies[i];
+    SmallVector<Pop*, 1> pops = findPops(catchBody);
+    if (tag->sig.params == Type::none) {
+      if (!shouldBeTrue(pops.empty(), curr, "")) {
+        getStream() << "catch's tag (" << tagName
+                    << ") doesn't have any params, but there are pops";
+      }
+    } else {
+      if (shouldBeTrue(pops.size() == 1, curr, "")) {
+        auto* pop = *pops.begin();
+        if (!shouldBeSubType(pop->type, tag->sig.params, curr, "")) {
+          getStream()
+            << "catch's tag (" << tagName
+            << ")'s pop doesn't have the same type as the tag's params";
+        }
+        if (!shouldBeTrue(EHUtils::isPopValid(catchBody), curr, "")) {
+          getStream() << "catch's body (" << tagName
+                      << ")'s pop's location is not valid";
+        }
+      } else {
+        getStream() << "catch's tag (" << tagName
+                    << ") has params, so there should be a single pop within "
+                       "the catch body";
+      }
+    }
+  }
+
+  if (curr->hasCatchAll()) {
+    auto* catchAllBody = curr->catchBodies.back();
+    shouldBeTrue(findPops(catchAllBody).empty(),
+                 curr,
+                 "catch_all's body should not have pops");
+  }
+
   if (curr->isDelegate()) {
     noteDelegate(curr->delegateTarget, curr);
   }