[Strings] Add string.compare (#5453)

See WebAssembly/stringref#58

14 files changed, 112 insertions, 33 deletions

diff --git a/scripts/gen-s-parser.py b/scripts/gen-s-parser.py
index 6572cda49..f6c8e6e28 100755
--- a/scripts/gen-s-parser.py
+++ b/scripts/gen-s-parser.py
@@ -620,7 +620,8 @@ instructions = [
     ("string.encode_wtf8_array",   "makeStringEncode(s, StringEncodeWTF8Array)"),
     ("string.encode_wtf16_array",  "makeStringEncode(s, StringEncodeWTF16Array)"),
     ("string.concat",        "makeStringConcat(s)"),
-    ("string.eq",            "makeStringEq(s)"),
+    ("string.eq",            "makeStringEq(s, StringEqEqual)"),
+    ("string.compare",       "makeStringEq(s, StringEqCompare)"),
     ("string.as_wtf8",       "makeStringAs(s, StringAsWTF8)"),
     ("string.as_wtf16",      "makeStringAs(s, StringAsWTF16)"),
     ("string.as_iter",       "makeStringAs(s, StringAsIter)"),
diff --git a/src/binaryen-c.cpp b/src/binaryen-c.cpp
index 32dcfd8db..cd53f9ced 100644
--- a/src/binaryen-c.cpp
+++ b/src/binaryen-c.cpp
@@ -1880,7 +1880,7 @@ BinaryenExpressionRef BinaryenStringEq(BinaryenModuleRef module,
                                        BinaryenExpressionRef right) {
   return static_cast<Expression*>(
     Builder(*(Module*)module)
-      .makeStringEq((Expression*)left, (Expression*)right));
+      .makeStringEq(StringEqEqual, (Expression*)left, (Expression*)right));
 }
 BinaryenExpressionRef BinaryenStringAs(BinaryenModuleRef module,
                                        BinaryenOp op,
diff --git a/src/gen-s-parser.inc b/src/gen-s-parser.inc
index b44329388..6f2c24a47 100644
--- a/src/gen-s-parser.inc
+++ b/src/gen-s-parser.inc
@@ -3138,13 +3138,21 @@ switch (buf[0]) {
                     }
                   }
                   case 'c': {
-                    switch (buf[10]) {
-                      case 'c':
-                        if (op == "string.concat"sv) { return makeStringConcat(s); }
-                        goto parse_error;
-                      case 's':
-                        if (op == "string.const"sv) { return makeStringConst(s); }
+                    switch (buf[9]) {
+                      case 'm':
+                        if (op == "string.compare"sv) { return makeStringEq(s, StringEqCompare); }
                         goto parse_error;
+                      case 'n': {
+                        switch (buf[10]) {
+                          case 'c':
+                            if (op == "string.concat"sv) { return makeStringConcat(s); }
+                            goto parse_error;
+                          case 's':
+                            if (op == "string.const"sv) { return makeStringConst(s); }
+                            goto parse_error;
+                          default: goto parse_error;
+                        }
+                      }
                       default: goto parse_error;
                     }
                   }
@@ -3178,7 +3186,7 @@ switch (buf[0]) {
                         }
                       }
                       case 'q':
-                        if (op == "string.eq"sv) { return makeStringEq(s); }
+                        if (op == "string.eq"sv) { return makeStringEq(s, StringEqEqual); }
                         goto parse_error;
                       default: goto parse_error;
                     }
@@ -8812,21 +8820,33 @@ switch (buf[0]) {
                     }
                   }
                   case 'c': {
-                    switch (buf[10]) {
-                      case 'c':
-                        if (op == "string.concat"sv) {
-                          auto ret = makeStringConcat(ctx, pos);
+                    switch (buf[9]) {
+                      case 'm':
+                        if (op == "string.compare"sv) {
+                          auto ret = makeStringEq(ctx, pos, StringEqCompare);
                           CHECK_ERR(ret);
                           return *ret;
                         }
                         goto parse_error;
-                      case 's':
-                        if (op == "string.const"sv) {
-                          auto ret = makeStringConst(ctx, pos);
-                          CHECK_ERR(ret);
-                          return *ret;
+                      case 'n': {
+                        switch (buf[10]) {
+                          case 'c':
+                            if (op == "string.concat"sv) {
+                              auto ret = makeStringConcat(ctx, pos);
+                              CHECK_ERR(ret);
+                              return *ret;
+                            }
+                            goto parse_error;
+                          case 's':
+                            if (op == "string.const"sv) {
+                              auto ret = makeStringConst(ctx, pos);
+                              CHECK_ERR(ret);
+                              return *ret;
+                            }
+                            goto parse_error;
+                          default: goto parse_error;
                         }
-                        goto parse_error;
+                      }
                       default: goto parse_error;
                     }
                   }
@@ -8877,7 +8897,7 @@ switch (buf[0]) {
                       }
                       case 'q':
                         if (op == "string.eq"sv) {
-                          auto ret = makeStringEq(ctx, pos);
+                          auto ret = makeStringEq(ctx, pos, StringEqEqual);
                           CHECK_ERR(ret);
                           return *ret;
                         }
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index 38e88fde5..d9a4c38e5 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -2424,7 +2424,18 @@ struct PrintExpressionContents
   void visitStringConcat(StringConcat* curr) {
     printMedium(o, "string.concat");
   }
-  void visitStringEq(StringEq* curr) { printMedium(o, "string.eq"); }
+  void visitStringEq(StringEq* curr) {
+    switch (curr->op) {
+      case StringEqEqual:
+        printMedium(o, "string.eq");
+        break;
+      case StringEqCompare:
+        printMedium(o, "string.compare");
+        break;
+      default:
+        WASM_UNREACHABLE("invalid string.eq*");
+    }
+  }
   void visitStringAs(StringAs* curr) {
     switch (curr->op) {
       case StringAsWTF8:
diff --git a/src/wasm-binary.h b/src/wasm-binary.h
index afb48106e..9ec097c57 100644
--- a/src/wasm-binary.h
+++ b/src/wasm-binary.h
@@ -1162,6 +1162,7 @@ enum ASTNodes {
   StringViewIterAdvance = 0xa2,
   StringViewIterRewind = 0xa3,
   StringViewIterSlice = 0xa4,
+  StringCompare = 0xa8,
   StringNewWTF8Array = 0xb0,
   StringNewWTF16Array = 0xb1,
   StringEncodeWTF8Array = 0xb2,
diff --git a/src/wasm-builder.h b/src/wasm-builder.h
index 263ee80fd..c25293999 100644
--- a/src/wasm-builder.h
+++ b/src/wasm-builder.h
@@ -1057,8 +1057,9 @@ public:
     ret->finalize();
     return ret;
   }
-  StringEq* makeStringEq(Expression* left, Expression* right) {
+  StringEq* makeStringEq(StringEqOp op, Expression* left, Expression* right) {
     auto* ret = wasm.allocator.alloc<StringEq>();
+    ret->op = op;
     ret->left = left;
     ret->right = right;
     ret->finalize();
diff --git a/src/wasm-delegations-fields.def b/src/wasm-delegations-fields.def
index 019cdbc0d..d9226b3d7 100644
--- a/src/wasm-delegations-fields.def
+++ b/src/wasm-delegations-fields.def
@@ -757,6 +757,7 @@ switch (DELEGATE_ID) {
   }
   case Expression::Id::StringEqId: {
     DELEGATE_START(StringEq);
+    DELEGATE_FIELD_INT(StringEq, op);
     DELEGATE_FIELD_CHILD(StringEq, right);
     DELEGATE_FIELD_CHILD(StringEq, left);
     DELEGATE_END(StringEq);
diff --git a/src/wasm-s-parser.h b/src/wasm-s-parser.h
index d5ca2d320..942f4c919 100644
--- a/src/wasm-s-parser.h
+++ b/src/wasm-s-parser.h
@@ -309,7 +309,7 @@ private:
   Expression* makeStringMeasure(Element& s, StringMeasureOp op);
   Expression* makeStringEncode(Element& s, StringEncodeOp op);
   Expression* makeStringConcat(Element& s);
-  Expression* makeStringEq(Element& s);
+  Expression* makeStringEq(Element& s, StringEqOp op);
   Expression* makeStringAs(Element& s, StringAsOp op);
   Expression* makeStringWTF8Advance(Element& s);
   Expression* makeStringWTF16Get(Element& s);
diff --git a/src/wasm.h b/src/wasm.h
index f7683e6bb..d5b52b315 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -605,6 +605,11 @@ enum StringEncodeOp {
   StringEncodeWTF16Array,
 };
 
+enum StringEqOp {
+  StringEqEqual,
+  StringEqCompare,
+};
+
 enum StringAsOp {
   StringAsWTF8,
   StringAsWTF16,
@@ -1748,6 +1753,8 @@ class StringEq : public SpecificExpression<Expression::StringEqId> {
 public:
   StringEq(MixedArena& allocator) {}
 
+  StringEqOp op;
+
   Expression* left;
   Expression* right;
 
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index abd51fcef..65734e68d 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -7345,12 +7345,17 @@ bool WasmBinaryBuilder::maybeVisitStringConcat(Expression*& out,
 }
 
 bool WasmBinaryBuilder::maybeVisitStringEq(Expression*& out, uint32_t code) {
-  if (code != BinaryConsts::StringEq) {
+  StringEqOp op;
+  if (code == BinaryConsts::StringEq) {
+    op = StringEqEqual;
+  } else if (code == BinaryConsts::StringCompare) {
+    op = StringEqCompare;
+  } else {
     return false;
   }
   auto* right = popNonVoidExpression();
   auto* left = popNonVoidExpression();
-  out = Builder(wasm).makeStringEq(left, right);
+  out = Builder(wasm).makeStringEq(op, left, right);
   return true;
 }
 
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 0c413af2a..829025a2c 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -3090,9 +3090,9 @@ Expression* SExpressionWasmBuilder::makeStringConcat(Element& s) {
                                         parseExpression(s[2]));
 }
 
-Expression* SExpressionWasmBuilder::makeStringEq(Element& s) {
-  return Builder(wasm).makeStringEq(parseExpression(s[1]),
-                                    parseExpression(s[2]));
+Expression* SExpressionWasmBuilder::makeStringEq(Element& s, StringEqOp op) {
+  return Builder(wasm).makeStringEq(
+    op, parseExpression(s[1]), parseExpression(s[2]));
 }
 
 Expression* SExpressionWasmBuilder::makeStringAs(Element& s, StringAsOp op) {
diff --git a/src/wasm/wasm-stack.cpp b/src/wasm/wasm-stack.cpp
index 35ef12993..1f5722b59 100644
--- a/src/wasm/wasm-stack.cpp
+++ b/src/wasm/wasm-stack.cpp
@@ -2370,7 +2370,17 @@ void BinaryInstWriter::visitStringConcat(StringConcat* curr) {
 }
 
 void BinaryInstWriter::visitStringEq(StringEq* curr) {
-  o << int8_t(BinaryConsts::GCPrefix) << U32LEB(BinaryConsts::StringEq);
+  o << int8_t(BinaryConsts::GCPrefix);
+  switch (curr->op) {
+    case StringEqEqual:
+      o << U32LEB(BinaryConsts::StringEq);
+      break;
+    case StringEqCompare:
+      o << U32LEB(BinaryConsts::StringCompare);
+      break;
+    default:
+      WASM_UNREACHABLE("invalid string.eq*");
+  }
 }
 
 void BinaryInstWriter::visitStringAs(StringAs* curr) {
diff --git a/src/wasm/wat-parser.cpp b/src/wasm/wat-parser.cpp
index 66bba8862..dfc2190f3 100644
--- a/src/wasm/wat-parser.cpp
+++ b/src/wasm/wat-parser.cpp
@@ -2383,7 +2383,8 @@ template<typename Ctx>
 Result<typename Ctx::InstrT> makeStringEncode(Ctx&, Index, StringEncodeOp op);
 template<typename Ctx>
 Result<typename Ctx::InstrT> makeStringConcat(Ctx&, Index);
-template<typename Ctx> Result<typename Ctx::InstrT> makeStringEq(Ctx&, Index);
+template<typename Ctx>
+Result<typename Ctx::InstrT> makeStringEq(Ctx&, Index, StringEqOp);
 template<typename Ctx>
 Result<typename Ctx::InstrT> makeStringAs(Ctx&, Index, StringAsOp op);
 template<typename Ctx>
@@ -3589,7 +3590,7 @@ Result<typename Ctx::InstrT> makeStringConcat(Ctx& ctx, Index pos) {
 }
 
 template<typename Ctx>
-Result<typename Ctx::InstrT> makeStringEq(Ctx& ctx, Index pos) {
+Result<typename Ctx::InstrT> makeStringEq(Ctx& ctx, Index pos, StringEqOp op) {
   return ctx.in.err("unimplemented instruction");
 }
 
diff --git a/test/lit/strings.wast b/test/lit/strings.wast
index f0b4730d7..22e433479 100644
--- a/test/lit/strings.wast
+++ b/test/lit/strings.wast
@@ -16,10 +16,10 @@
 
   ;; CHECK:      (type $stringref_=>_none (func (param stringref)))
 
-  ;; CHECK:      (type $stringref_stringview_wtf8_stringview_wtf16_stringview_iter_=>_none (func (param stringref stringview_wtf8 stringview_wtf16 stringview_iter)))
-
   ;; CHECK:      (type $stringref_stringref_=>_none (func (param stringref stringref)))
 
+  ;; CHECK:      (type $stringref_stringview_wtf8_stringview_wtf16_stringview_iter_=>_none (func (param stringref stringview_wtf8 stringview_wtf16 stringview_iter)))
+
   ;; CHECK:      (type $array (array (mut i8)))
   (type $array (array_subtype (mut i8) data))
   ;; CHECK:      (type $array16 (array (mut i16)))
@@ -250,6 +250,27 @@
     )
   )
 
+  ;; CHECK:      (func $string.compare (type $stringref_stringref_=>_none) (param $a stringref) (param $b stringref)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.eqz
+  ;; CHECK-NEXT:    (string.compare
+  ;; CHECK-NEXT:     (local.get $a)
+  ;; CHECK-NEXT:     (local.get $b)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $string.compare (param $a stringref) (param $b stringref)
+    (drop
+      (i32.eqz ;; validate the output is an i32
+        (string.compare
+          (local.get $a)
+          (local.get $b)
+        )
+      )
+    )
+  )
+
   ;; CHECK:      (func $string.is_usv_sequence (type $stringref_=>_none) (param $ref stringref)
   ;; CHECK-NEXT:  (drop
   ;; CHECK-NEXT:   (i32.eqz