[wasm-merge] Handle chains of import/export (#5813)

When a module item is imported and directly reexported by an
intermediate module, we need to perform several name lookups and use its
name in the initial module rather than the intermediate name when fusing
imports and exports.

6 files changed, 68 insertions, 1 deletions

diff --git a/src/tools/wasm-merge.cpp b/src/tools/wasm-merge.cpp
index ff2ab6d46..47dd1e111 100644
--- a/src/tools/wasm-merge.cpp
+++ b/src/tools/wasm-merge.cpp
@@ -235,6 +235,21 @@ void updateNames(Module& wasm, KindNameUpdates& kindNameUpdates) {
     }
 
   private:
+    Name resolveName(NameUpdates& updates, const Name newName) {
+      // Iteratively lookup the updated name
+      // We detect loops to ensure termination
+      std::set<Name> visited;
+      Name name = newName;
+      while (1) {
+        auto iter = updates.find(name);
+        if (iter == updates.end() || visited.find(name) != visited.end()) {
+          return name;
+        }
+        visited.insert(name);
+        name = iter->second;
+      }
+    }
+
     void mapName(ModuleItemKind kind, Name& name) {
       auto iter = kindNameUpdates.find(kind);
       if (iter == kindNameUpdates.end()) {
@@ -243,7 +258,7 @@ void updateNames(Module& wasm, KindNameUpdates& kindNameUpdates) {
       auto& nameUpdates = iter->second;
       auto iter2 = nameUpdates.find(name);
       if (iter2 != nameUpdates.end()) {
-        name = iter2->second;
+        name = resolveName(nameUpdates, iter2->second);
       }
     }
   } nameMapper(kindNameUpdates);
diff --git a/test/lit/merge/chain.wat b/test/lit/merge/chain.wat
new file mode 100644
index 000000000..f87914931
--- /dev/null
+++ b/test/lit/merge/chain.wat
@@ -0,0 +1,24 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+;; RUN: wasm-merge %s first %s.second second %s.third third --rename-export-conflicts -all -S -o - | filecheck %s
+
+;; Test chains of imports / exports: the first module export a function,
+;; which is reexported by the second and imported by the third.
+
+(module
+  (func (export "f"))
+)
+;; CHECK:      (type $none_=>_none (func))
+
+;; CHECK:      (export "f" (func $0))
+
+;; CHECK:      (export "g" (func $0))
+
+;; CHECK:      (export "h" (func $0_2))
+
+;; CHECK:      (func $0 (type $none_=>_none)
+;; CHECK-NEXT:  (nop)
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $0_2 (type $none_=>_none)
+;; CHECK-NEXT:  (call $0)
+;; CHECK-NEXT: )
diff --git a/test/lit/merge/chain.wat.second b/test/lit/merge/chain.wat.second
new file mode 100644
index 000000000..dae1ace36
--- /dev/null
+++ b/test/lit/merge/chain.wat.second
@@ -0,0 +1,4 @@
+(module
+  (import "first" "f" (func $f))
+  (export "g" (func $f))
+)
diff --git a/test/lit/merge/chain.wat.third b/test/lit/merge/chain.wat.third
new file mode 100644
index 000000000..cffbe5ba6
--- /dev/null
+++ b/test/lit/merge/chain.wat.third
@@ -0,0 +1,4 @@
+(module
+  (import "second" "g" (func $g))
+  (func (export "h") (call $g))
+)
diff --git a/test/lit/merge/import_cycle.wat b/test/lit/merge/import_cycle.wat
new file mode 100644
index 000000000..0261eabc5
--- /dev/null
+++ b/test/lit/merge/import_cycle.wat
@@ -0,0 +1,16 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+;; RUN: wasm-merge %s first %s.second second -S -o - | filecheck %s
+
+;; Test that wasm-merge terminates when there are importation cycles
+
+(module
+  ;; CHECK:      (type $none_=>_none (func))
+
+  ;; CHECK:      (import "second" "g" (func $f))
+  (import "second" "g" (func $f))
+  ;; CHECK:      (import "first" "f" (func $f_1))
+
+  ;; CHECK:      (export "f" (func $f_1))
+  (export "f" (func $f))
+)
+;; CHECK:      (export "g" (func $f))
diff --git a/test/lit/merge/import_cycle.wat.second b/test/lit/merge/import_cycle.wat.second
new file mode 100644
index 000000000..dae1ace36
--- /dev/null
+++ b/test/lit/merge/import_cycle.wat.second
@@ -0,0 +1,4 @@
+(module
+  (import "first" "f" (func $f))
+  (export "g" (func $f))
+)