[Strings] Add a string lowering pass using magic imports (#6497)

The latest idea for efficient string constants is to encode the constants in
the import names of their globals and implement fast paths in the engines for
materializing those constants at instantiation time without needing to parse
anything in JS. This strategy only works for valid strings (i.e. strings without
unpaired surrogates) because only valid strings can be used as import names in
the WebAssembly syntax.

Add a new configuration of the StringLowering pass that encodes valid string
contents in import names, falling back to the JSON custom section approach for
invalid strings.

To test this chang, update the printer to escape import and export names
properly and update the legacy parser to parse escapes in import and export
names properly. As a drive-by, remove the incorrect check in the parser that the
import module and base names are non-empty.

6 files changed, 111 insertions, 14 deletions

diff --git a/test/lit/help/wasm-opt.test b/test/lit/help/wasm-opt.test
index 84b5049dd..ff07586f2 100644
--- a/test/lit/help/wasm-opt.test
+++ b/test/lit/help/wasm-opt.test
@@ -478,6 +478,10 @@
 ;; CHECK-NEXT:   --string-lowering                             lowers wasm strings and
 ;; CHECK-NEXT:                                                 operations to imports
 ;; CHECK-NEXT:
+;; CHECK-NEXT:   --string-lowering-magic-imports               same as string-lowering, but
+;; CHECK-NEXT:                                                 encodes well-formed strings as
+;; CHECK-NEXT:                                                 magic imports
+;; CHECK-NEXT:
 ;; CHECK-NEXT:   --strip                                       deprecated; same as strip-debug
 ;; CHECK-NEXT:
 ;; CHECK-NEXT:   --strip-debug                                 strip debug info (including the
diff --git a/test/lit/help/wasm2js.test b/test/lit/help/wasm2js.test
index 3ab4099de..493542135 100644
--- a/test/lit/help/wasm2js.test
+++ b/test/lit/help/wasm2js.test
@@ -432,6 +432,10 @@
 ;; CHECK-NEXT:   --string-lowering                             lowers wasm strings and
 ;; CHECK-NEXT:                                                 operations to imports
 ;; CHECK-NEXT:
+;; CHECK-NEXT:   --string-lowering-magic-imports               same as string-lowering, but
+;; CHECK-NEXT:                                                 encodes well-formed strings as
+;; CHECK-NEXT:                                                 magic imports
+;; CHECK-NEXT:
 ;; CHECK-NEXT:   --strip                                       deprecated; same as strip-debug
 ;; CHECK-NEXT:
 ;; CHECK-NEXT:   --strip-debug                                 strip debug info (including the
diff --git a/test/lit/passes/string-lowering-imports.wast b/test/lit/passes/string-lowering-imports.wast
new file mode 100644
index 000000000..6a908139e
--- /dev/null
+++ b/test/lit/passes/string-lowering-imports.wast
@@ -0,0 +1,86 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+
+;; RUN: wasm-opt %s -all --string-lowering-magic-imports --remove-unused-module-elements -S -o - | filecheck %s
+;; RUN: wasm-opt %s -all --string-lowering-magic-imports --remove-unused-module-elements --roundtrip -S -o - | filecheck %s --check-prefix=RTRIP
+
+(module
+  ;; CHECK:      (type $0 (func))
+
+  ;; CHECK:      (import "\'" "bar" (global $string.const_bar (ref extern)))
+
+  ;; CHECK:      (import "\'" "foo" (global $string.const_foo (ref extern)))
+
+  ;; CHECK:      (import "\'" "needs\tescaping\00.\'#%- .\r\n\\08\0c\n\r\t.\ea\99\ae" (global $"string.const_needs\tescaping\00.\'#%- .\r\n\\08\0c\n\r\t.\ea\99\ae" (ref extern)))
+
+  ;; CHECK:      (import "string.const" "0" (global $"string.const_unpaired high surrogate \ed\a0\80 " (ref extern)))
+
+  ;; CHECK:      (import "string.const" "1" (global $"string.const_unpaired low surrogate \ed\bd\88 " (ref extern)))
+
+  ;; CHECK:      (export "consts" (func $consts))
+
+  ;; CHECK:      (func $consts (type $0)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (global.get $string.const_foo)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (global.get $string.const_bar)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (global.get $"string.const_needs\tescaping\00.\'#%- .\r\n\\08\0c\n\r\t.\ea\99\ae")
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (global.get $"string.const_unpaired high surrogate \ed\a0\80 ")
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (global.get $"string.const_unpaired low surrogate \ed\bd\88 ")
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  ;; RTRIP:      (type $0 (func))
+
+  ;; RTRIP:      (import "\'" "bar" (global $gimport$0 (ref extern)))
+
+  ;; RTRIP:      (import "\'" "foo" (global $gimport$1 (ref extern)))
+
+  ;; RTRIP:      (import "\'" "needs\tescaping\00.\'#%- .\r\n\\08\0c\n\r\t.\ea\99\ae" (global $gimport$2 (ref extern)))
+
+  ;; RTRIP:      (import "string.const" "0" (global $gimport$3 (ref extern)))
+
+  ;; RTRIP:      (import "string.const" "1" (global $gimport$4 (ref extern)))
+
+  ;; RTRIP:      (export "consts" (func $consts))
+
+  ;; RTRIP:      (func $consts (type $0)
+  ;; RTRIP-NEXT:  (drop
+  ;; RTRIP-NEXT:   (global.get $gimport$1)
+  ;; RTRIP-NEXT:  )
+  ;; RTRIP-NEXT:  (drop
+  ;; RTRIP-NEXT:   (global.get $gimport$0)
+  ;; RTRIP-NEXT:  )
+  ;; RTRIP-NEXT:  (drop
+  ;; RTRIP-NEXT:   (global.get $gimport$2)
+  ;; RTRIP-NEXT:  )
+  ;; RTRIP-NEXT:  (drop
+  ;; RTRIP-NEXT:   (global.get $gimport$3)
+  ;; RTRIP-NEXT:  )
+  ;; RTRIP-NEXT:  (drop
+  ;; RTRIP-NEXT:   (global.get $gimport$4)
+  ;; RTRIP-NEXT:  )
+  ;; RTRIP-NEXT: )
+  (func $consts (export "consts")
+    (drop
+      (string.const "foo")
+    )
+    (drop
+      (string.const "bar")
+    )
+    (drop
+      (string.const "needs\tescaping\00.'#%- .\r\n\\08\0C\0A\0D\09.ꙮ")
+    )
+    (drop
+      (string.const "unpaired high surrogate \ED\A0\80 ")
+    )
+    (drop
+      (string.const "unpaired low surrogate \ED\BD\88 ")
+    )
+  )
+)
diff --git a/test/lit/passes/string-lowering.wast b/test/lit/passes/string-lowering.wast
index c060bc8bd..de684889a 100644
--- a/test/lit/passes/string-lowering.wast
+++ b/test/lit/passes/string-lowering.wast
@@ -16,6 +16,12 @@
     (drop
       (string.const "needs\tescaping\00.'#%\"- .\r\n\\08\0C\0A\0D\09.ꙮ")
     )
+    (drop
+      (string.const "unpaired high surrogate \ED\A0\80 ")
+    )
+    (drop
+      (string.const "unpaired low surrogate \ED\BD\88 ")
+    )
   )
 )
 
@@ -24,7 +30,14 @@
 ;;
 ;; RUN: wasm-opt %s --string-lowering -all -S -o - | filecheck %s
 ;;
-;; CHECK: custom section "string.consts", size 69, contents: "[\"bar\",\"foo\",\"needs\\tescaping\\u0000.'#%\\\"- .\\r\\n\\\\08\\f\\n\\r\\t.\\ua66e\"]"
+;; If we use magic imports, only invalid strings should be present in the JSON.
+;;
+;; RUN: wasm-opt %s --string-lowering-magic-imports -all -S -o - \
+;; RUN:     | filecheck %s --check-prefix=MAGIC
+;;
+;; CHECK: custom section "string.consts", size 136, contents: "[\"bar\",\"foo\",\"needs\\tescaping\\u0000.'#%\\\"- .\\r\\n\\\\08\\f\\n\\r\\t.\\ua66e\",\"unpaired high surrogate \\ud800 \",\"unpaired low surrogate \\udf48 \"]"
+;;
+;; MAGIC: custom section "string.consts", size 68, contents: "[\"unpaired high surrogate \\ud800 \",\"unpaired low surrogate \\udf48 \"]"
 
 ;; The custom section should parse OK using JSON.parse from node.
 ;; (Note we run --remove-unused-module-elements to remove externref-using
@@ -33,5 +46,6 @@
 ;; RUN: wasm-opt %s --string-lowering --remove-unused-module-elements -all -o %t.wasm
 ;; RUN: node %S/string-lowering.js %t.wasm | filecheck %s --check-prefix=CHECK-JS
 ;;
-;; CHECK-JS: string: ["bar","foo","needs\tescaping\x00.'#%\"- .\r\n\\08\f\n\r\t.\ua66e"]
-;; CHECK-JS: JSON: ["bar","foo","needs\tescaping\x00.'#%\"- .\r\n\\08\f\n\r\t.ꙮ"]
+;; CHECK-JS: string: ["bar","foo","needs\tescaping\x00.'#%\"- .\r\n\\08\f\n\r\t.\ua66e","unpaired high surrogate \ud800 ","unpaired low surrogate \udf48 "]
+;;
+;; CHECK-JS: JSON: ["bar","foo","needs\tescaping\x00.'#%\"- .\r\n\\08\f\n\r\t.ꙮ","unpaired high surrogate \ud800 ","unpaired low surrogate \udf48 "]
diff --git a/test/spec/import-after-memory.fail.wast b/test/spec/import-after-memory.fail.wast
deleted file mode 100644
index fbe582a93..000000000
--- a/test/spec/import-after-memory.fail.wast
+++ /dev/null
@@ -1 +0,0 @@
-(module (memory 0) (import "" "" (global i32)))
diff --git a/test/spec/old_import.wast b/test/spec/old_import.wast
index eba633388..a68df1389 100644
--- a/test/spec/old_import.wast
+++ b/test/spec/old_import.wast
@@ -126,16 +126,6 @@
 (assert_trap (invoke "call" (i32.const 3)) "uninitialized element")
 (assert_trap (invoke "call" (i32.const 100)) "undefined element")
 
-
-(assert_invalid
-  (module (import "" "" (table 10 funcref)) (import "" "" (table 10 funcref)))
-  "multiple tables"
-)
-(assert_invalid
-  (module (import "" "" (table 10 funcref)) (table 10 funcref))
-  "multiple tables"
-)
-
 (assert_unlinkable
   (module (import "spectest" "unknown" (table 10 funcref)))
   "unknown import"