Implement `array` basic heap type (#5148)

`array` is the supertype of all defined array types and for now is a subtype of
`data`. (Once `data` becomes `struct` this will no longer be true.) Update the
binary and text parsing of `array.len` to ignore the obsolete type annotation
and update the binary emitting to emit a zero in place of the old type
annotation and the text printing to print an arbitrary heap type for the
annotation. A follow-on PR will add support for the newer unannotated version of
`array.len`.

5 files changed, 136 insertions, 43 deletions

diff --git a/test/example/c-api-kitchen-sink.txt b/test/example/c-api-kitchen-sink.txt
index 3d2b74938..5c6400ce5 100644
--- a/test/example/c-api-kitchen-sink.txt
+++ b/test/example/c-api-kitchen-sink.txt
@@ -25,10 +25,10 @@ BinaryenHeapTypeAny: 2
 BinaryenHeapTypeEq: 3
 BinaryenHeapTypeI31: 4
 BinaryenHeapTypeData: 5
-BinaryenHeapTypeString: 6
-BinaryenHeapTypeStringviewWTF8: 7
-BinaryenHeapTypeStringviewWTF16: 8
-BinaryenHeapTypeStringviewIter: 9
+BinaryenHeapTypeString: 7
+BinaryenHeapTypeStringviewWTF8: 8
+BinaryenHeapTypeStringviewWTF16: 9
+BinaryenHeapTypeStringviewIter: 10
 BinaryenFeatureMVP: 0
 BinaryenFeatureAtomics: 1
 BinaryenFeatureBulkMemory: 16
diff --git a/test/gtest/type-builder.cpp b/test/gtest/type-builder.cpp
index a397041bf..5760838da 100644
--- a/test/gtest/type-builder.cpp
+++ b/test/gtest/type-builder.cpp
@@ -506,6 +506,7 @@ TEST_F(IsorecursiveTest, TestBasicTypeRelations) {
   HeapType eq = HeapType::eq;
   HeapType i31 = HeapType::i31;
   HeapType data = HeapType::data;
+  HeapType array = HeapType::array;
   HeapType string = HeapType::string;
   HeapType stringview_wtf8 = HeapType::stringview_wtf8;
   HeapType stringview_wtf16 = HeapType::stringview_wtf16;
@@ -551,6 +552,7 @@ TEST_F(IsorecursiveTest, TestBasicTypeRelations) {
   assertLUB(ext, eq, {});
   assertLUB(ext, i31, {});
   assertLUB(ext, data, {});
+  assertLUB(ext, array, {});
   assertLUB(ext, string, {});
   assertLUB(ext, stringview_wtf8, {});
   assertLUB(ext, stringview_wtf16, {});
@@ -567,6 +569,7 @@ TEST_F(IsorecursiveTest, TestBasicTypeRelations) {
   assertLUB(func, eq, {});
   assertLUB(func, i31, {});
   assertLUB(func, data, {});
+  assertLUB(func, array, {});
   assertLUB(func, string, {});
   assertLUB(func, stringview_wtf8, {});
   assertLUB(func, stringview_wtf16, {});
@@ -582,6 +585,7 @@ TEST_F(IsorecursiveTest, TestBasicTypeRelations) {
   assertLUB(any, eq, any);
   assertLUB(any, i31, any);
   assertLUB(any, data, any);
+  assertLUB(any, array, any);
   assertLUB(any, string, any);
   assertLUB(any, stringview_wtf8, any);
   assertLUB(any, stringview_wtf16, any);
@@ -596,6 +600,7 @@ TEST_F(IsorecursiveTest, TestBasicTypeRelations) {
   assertLUB(eq, eq, eq);
   assertLUB(eq, i31, eq);
   assertLUB(eq, data, eq);
+  assertLUB(eq, array, eq);
   assertLUB(eq, string, any);
   assertLUB(eq, stringview_wtf8, any);
   assertLUB(eq, stringview_wtf16, any);
@@ -609,6 +614,7 @@ TEST_F(IsorecursiveTest, TestBasicTypeRelations) {
 
   assertLUB(i31, i31, i31);
   assertLUB(i31, data, eq);
+  assertLUB(i31, array, eq);
   assertLUB(i31, string, any);
   assertLUB(i31, stringview_wtf8, any);
   assertLUB(i31, stringview_wtf16, any);
@@ -621,6 +627,7 @@ TEST_F(IsorecursiveTest, TestBasicTypeRelations) {
   assertLUB(i31, defArray, eq);
 
   assertLUB(data, data, data);
+  assertLUB(data, array, data);
   assertLUB(data, string, any);
   assertLUB(data, stringview_wtf8, any);
   assertLUB(data, stringview_wtf16, any);
@@ -632,6 +639,18 @@ TEST_F(IsorecursiveTest, TestBasicTypeRelations) {
   assertLUB(data, defStruct, data);
   assertLUB(data, defArray, data);
 
+  assertLUB(array, array, array);
+  assertLUB(array, string, any);
+  assertLUB(array, stringview_wtf8, any);
+  assertLUB(array, stringview_wtf16, any);
+  assertLUB(array, stringview_iter, any);
+  assertLUB(array, none, array);
+  assertLUB(array, noext, {});
+  assertLUB(array, nofunc, {});
+  assertLUB(array, defFunc, {});
+  assertLUB(array, defStruct, data);
+  assertLUB(array, defArray, array);
+
   assertLUB(string, string, string);
   assertLUB(string, stringview_wtf8, any);
   assertLUB(string, stringview_wtf16, any);
@@ -865,13 +884,14 @@ TEST_F(NominalTest, TestDepth) {
     C = built[2];
   }
 
-  // any < eq < data < specific struct and array types
+  // any :> eq :> data :> array :> specific array types
   EXPECT_EQ(HeapType(HeapType::any).getDepth(), 0U);
   EXPECT_EQ(HeapType(HeapType::eq).getDepth(), 1U);
   EXPECT_EQ(HeapType(HeapType::data).getDepth(), 2U);
+  EXPECT_EQ(HeapType(HeapType::array).getDepth(), 3U);
   EXPECT_EQ(A.getDepth(), 3U);
   EXPECT_EQ(B.getDepth(), 4U);
-  EXPECT_EQ(C.getDepth(), 3U);
+  EXPECT_EQ(C.getDepth(), 4U);
 
   // Signature types are subtypes of func.
   EXPECT_EQ(HeapType(HeapType::func).getDepth(), 0U);
diff --git a/test/heap-types.wast.from-wast b/test/heap-types.wast.from-wast
index dd3067e5a..4994857e2 100644
--- a/test/heap-types.wast.from-wast
+++ b/test/heap-types.wast.from-wast
@@ -383,10 +383,7 @@
  )
  (func $unreachables-array-6
   (drop
-   (block ;; (replaces something unreachable we can't emit)
-    (drop
-     (unreachable)
-    )
+   (array.len array
     (unreachable)
    )
   )
diff --git a/test/lit/arrays.wast b/test/lit/arrays.wast
new file mode 100644
index 000000000..b79ca1844
--- /dev/null
+++ b/test/lit/arrays.wast
@@ -0,0 +1,72 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+
+;; Check that array types and operations are emitted properly in the binary format.
+
+;; RUN: wasm-opt %s -all -S -o - | filecheck %s
+;; RUN: wasm-opt %s -all --roundtrip -S -o - | filecheck %s --check-prefix=ROUNDTRIP
+
+;; Check that we can roundtrip through the text format as well.
+
+;; RUN: wasm-opt %s -all -S -o - | wasm-opt -all -S -o - | filecheck %s
+
+(module
+ (type $byte-array (array (mut i8)))
+ ;; CHECK:      (type $ref|array|_=>_i32 (func (param (ref array)) (result i32)))
+
+ ;; CHECK:      (type $nullref_=>_i32 (func (param nullref) (result i32)))
+
+ ;; CHECK:      (type $arrayref_=>_i32 (func (param arrayref) (result i32)))
+
+ ;; CHECK:      (func $len (param $a (ref array)) (result i32)
+ ;; CHECK-NEXT:  (array.len array
+ ;; CHECK-NEXT:   (local.get $a)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ ;; ROUNDTRIP:      (type $ref|array|_=>_i32 (func (param (ref array)) (result i32)))
+
+ ;; ROUNDTRIP:      (type $nullref_=>_i32 (func (param nullref) (result i32)))
+
+ ;; ROUNDTRIP:      (type $arrayref_=>_i32 (func (param arrayref) (result i32)))
+
+ ;; ROUNDTRIP:      (func $len (param $a (ref array)) (result i32)
+ ;; ROUNDTRIP-NEXT:  (array.len array
+ ;; ROUNDTRIP-NEXT:   (local.get $a)
+ ;; ROUNDTRIP-NEXT:  )
+ ;; ROUNDTRIP-NEXT: )
+ (func $len (param $a (ref array)) (result i32)
+  ;; TODO: remove the unused type annotation
+  (array.len $byte-array
+   (local.get $a)
+  )
+ )
+
+ ;; CHECK:      (func $impossible-len (param $none nullref) (result i32)
+ ;; CHECK-NEXT:  (array.len none
+ ;; CHECK-NEXT:   (local.get $none)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ ;; ROUNDTRIP:      (func $impossible-len (param $none nullref) (result i32)
+ ;; ROUNDTRIP-NEXT:  (array.len none
+ ;; ROUNDTRIP-NEXT:   (local.get $none)
+ ;; ROUNDTRIP-NEXT:  )
+ ;; ROUNDTRIP-NEXT: )
+ (func $impossible-len (param $none nullref) (result i32)
+  (array.len $byte-array
+   (local.get $none)
+  )
+ )
+
+ ;; CHECK:      (func $unreachable-len (param $a arrayref) (result i32)
+ ;; CHECK-NEXT:  (array.len array
+ ;; CHECK-NEXT:   (unreachable)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ ;; ROUNDTRIP:      (func $unreachable-len (param $a arrayref) (result i32)
+ ;; ROUNDTRIP-NEXT:  (unreachable)
+ ;; ROUNDTRIP-NEXT: )
+ (func $unreachable-len (param $a arrayref) (result i32)
+  (array.len $byte-array
+   (unreachable)
+  )
+ )
+)
diff --git a/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt b/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
index e984e8be5..8006cb2a6 100644
--- a/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
+++ b/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
@@ -1,45 +1,49 @@
 total
- [exports]      : 7       
- [funcs]        : 7       
+ [exports]      : 8       
+ [funcs]        : 11      
  [globals]      : 6       
  [imports]      : 5       
  [memories]     : 1       
  [memory-data]  : 22      
- [table-data]   : 8       
+ [table-data]   : 7       
  [tables]       : 1       
- [tags]         : 2       
- [total]        : 433     
- [vars]         : 6       
+ [tags]         : 0       
+ [total]        : 748     
+ [vars]         : 19      
+ ArrayInit      : 5       
+ AtomicFence    : 1       
  AtomicRMW      : 1       
- Binary         : 56      
- Block          : 36      
- Break          : 4       
- Call           : 22      
- CallRef        : 8       
- Const          : 113     
+ Binary         : 84      
+ Block          : 90      
+ Break          : 14      
+ Call           : 19      
+ CallIndirect   : 2       
+ CallRef        : 2       
+ Const          : 176     
  Drop           : 5       
- GlobalGet      : 24      
- GlobalSet      : 11      
+ GlobalGet      : 58      
+ GlobalSet      : 25      
  I31Get         : 2       
- I31New         : 7       
- If             : 14      
- Load           : 17      
- LocalGet       : 24      
- LocalSet       : 17      
- Loop           : 4       
+ I31New         : 4       
+ If             : 39      
+ Load           : 22      
+ LocalGet       : 31      
+ LocalSet       : 21      
+ Loop           : 14      
+ MemoryCopy     : 1       
  MemoryFill     : 1       
- Nop            : 1       
+ Nop            : 17      
+ RefAs          : 4       
  RefEq          : 2       
- RefFunc        : 18      
+ RefFunc        : 9       
  RefIs          : 1       
- RefNull        : 2       
- Return         : 12      
- SIMDExtract    : 1       
- SIMDLoad       : 1       
- Select         : 7       
- Store          : 2       
- StructNew      : 1       
- Switch         : 1       
- TupleMake      : 2       
- Unary          : 13      
- Unreachable    : 3       
+ RefNull        : 5       
+ Return         : 29      
+ SIMDExtract    : 3       
+ SIMDReplace    : 1       
+ Select         : 3       
+ Store          : 5       
+ StructNew      : 2       
+ TupleExtract   : 1       
+ TupleMake      : 6       
+ Unary          : 43