Split up binary format writing code to match spec

9 files changed, 458 insertions, 285 deletions

diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/WasmBinaryFormat.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/WasmBinaryFormat.java
index b21ea2a0..761c9ea5 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/structure/WasmBinaryFormat.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/WasmBinaryFormat.java
@@ -1,290 +1,13 @@
 package org.shedlang.compiler.backends.wasm.structure;
 
-import org.pcollections.PVector;
 import org.shedlang.compiler.backends.wasm.structure.ast.WasmModule;
-import org.shedlang.compiler.backends.wasm.structure.ast.imports.WasmImport;
-import org.shedlang.compiler.backends.wasm.structure.ast.imports.WasmImportDescriptor;
-import org.shedlang.compiler.backends.wasm.structure.ast.types.*;
+import org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatModules;
 
 import java.io.IOException;
 import java.io.OutputStream;
-import java.nio.charset.StandardCharsets;
-import java.util.HashMap;
-import java.util.HexFormat;
-import java.util.List;
-import java.util.Map;
-import java.util.stream.Stream;
 
 public class WasmBinaryFormat {
-    private static final byte[] WASM_MAGIC = HexFormat.of().parseHex("0061736D");
-    private static final byte[] WASM_VERSION = HexFormat.of().parseHex("01000000");
-
-    private enum SectionType {
-        CUSTOM(0),
-        TYPE(1),
-        IMPORT(2),
-        FUNCTION(3),
-        TABLE(4),
-        MEMORY(5),
-        GLOBAL(6),
-        EXPORT(7),
-        START(8),
-        ELEMENT(9),
-        CODE(10),
-        DATA(11),
-        DATA_COUNT(12),
-        TAG(13);
-
-        private final byte id;
-
-        SectionType(int id) {
-            this.id = (byte) id;
-        }
-    }
-
     public static void serializeModule(WasmModule module, OutputStream outputStream) throws IOException {
-        var writer = new BinaryWriter();
-        writer.writeBytes(WASM_MAGIC);
-        writer.writeBytes(WASM_VERSION);
-        writeTypeSection(module.types(), writer);
-        writeImportSection(module, writer);
-        writeNameSection(module, writer);
-
-        outputStream.write(writer.toBytes());
-    }
-
-    private static void writeTypeSection(
-        PVector<WasmFuncType> types,
-        BinaryWriter writer
-    ) throws IOException {
-        if (types.size() > 0) {
-            writeSection(SectionType.TYPE, writer, () -> {
-                writeVec(
-                    types,
-                    type -> writeFuncType(type, writer),
-                    writer
-                );
-            });
-        }
-    }
-
-    private static void writeImportSection(
-        WasmModule module,
-        BinaryWriter writer
-    ) throws IOException {
-        if (module.imports().size() > 0) {
-            writeSection(SectionType.IMPORT, writer, () -> {
-                var funcTypeToTypeIndex = new HashMap<WasmFuncType, Integer>();
-                for (var funcIndex = 0; funcIndex < module.types().size(); funcIndex++) {
-                    funcTypeToTypeIndex.put(module.types().get(funcIndex), funcIndex);
-                }
-
-                writeVec(
-                    module.imports(),
-                    import_ -> writeImport(import_, funcTypeToTypeIndex, writer),
-                    writer
-                );
-            });
-        }
-    }
-
-    private static void writeImport(
-        WasmImport import_,
-        Map<WasmFuncType, Integer> funcTypeToTypeIndex,
-        BinaryWriter writer
-    ) {
-        writeString(import_.moduleName(), writer);
-        writeString(import_.entityName(), writer);
-        switch (import_.descriptor()) {
-            case WasmImportDescriptor.Func func -> {
-                writer.writeByte(0x00);
-                var typeIndex = funcTypeToTypeIndex.get(func.type());
-                writeTypeIndex(typeIndex, writer);
-            }
-            case WasmImportDescriptor.Table table -> {
-                writer.writeByte(0x01);
-                writeTableType(table.type(), writer);
-            }
-            case WasmImportDescriptor.Memory memory -> {
-                writer.writeByte(0x02);
-                writeMemoryType(memory.type(), writer);
-            }
-            case WasmImportDescriptor.Global global -> {
-                writer.writeByte(0x03);
-                writeGlobalType(global.type(), writer);
-            }
-        }
-    }
-
-    private static void writeNameSection(WasmModule module, BinaryWriter writer) throws IOException {
-        if (module.imports().size() > 0) {
-            writeSection(SectionType.CUSTOM, writer, () -> {
-                writeString("name", writer);
-                writeNameSectionFunctionNameSubsection(module, writer);
-            });
-        }
-    }
-
-    private static void writeNameSectionFunctionNameSubsection(WasmModule module, BinaryWriter writer) throws IOException {
-        writeSection((byte) 1, writer, () -> {
-            var importedFunctions = module.imports().stream()
-                .flatMap(import_ -> switch (import_.descriptor()) {
-                    case WasmImportDescriptor.Func func -> Stream.of(func);
-                    default -> Stream.empty();
-                })
-                .toList();
-
-            writeVec(
-                importedFunctions,
-                (funcIndex, func) -> {
-                    writeFuncIndex(funcIndex, writer);
-                    writeString(func.identifier(), writer);
-                },
-                writer
-            );
-        });
-    }
-
-    private static void writeFuncIndex(int funcIndex, BinaryWriter writer) {
-        Leb128Encoding.encodeUnsignedInt32(funcIndex, writer);
-    }
-
-    private static void writeTypeIndex(int typeIndex, BinaryWriter writer) {
-        Leb128Encoding.encodeUnsignedInt32(typeIndex, writer);
-    }
-
-    private static void writeFuncType(WasmFuncType type, BinaryWriter writer) throws IOException {
-        writer.writeByte((byte) 0x60);
-        writeValueTypeVector(type.params(), writer);
-        writeValueTypeVector(type.results(), writer);
-    }
-
-    private static void writeMemoryType(WasmMemoryType type, BinaryWriter writer) {
-        writeLimits(type.limits(), writer);
-    }
-
-    private static void writeGlobalType(WasmGlobalType type, BinaryWriter writer) {
-        writeValueType(type.valueType(), writer);
-        var mutabilityEncoding = switch (type.mutability()) {
-            case MUTABLE -> 0x01;
-            case IMMUTABLE -> 0x00;
-        };
-        writer.writeByte(mutabilityEncoding);
-    }
-
-    private static void writeReferenceType(WasmReferenceType type, BinaryWriter writer) {
-        var encoding = switch (type) {
-            case FUNC_REF -> 0x70;
-            case EXTERN_REF -> 0x6f;
-        };
-        writer.writeByte(encoding);
-    }
-
-    private static void writeTableType(WasmTableType type, BinaryWriter writer) {
-        writeReferenceType(type.elementType(), writer);
-        writeLimits(type.limits(), writer);
-    }
-
-    private static void writeValueTypeVector(List<WasmValueType> types, BinaryWriter writer) throws IOException {
-        writeVec(
-            types,
-            type -> writeValueType(type, writer),
-            writer
-        );
-    }
-
-    private static void writeValueType(WasmValueType type, BinaryWriter writer) {
-        var encoding = switch (type) {
-            case I32 -> 0x7f;
-            case I64 -> 0x7e;
-            case F32 -> 0x7d;
-            case F64 -> 0x7c;
-        };
-        writer.writeByte((byte) encoding);
-    }
-
-    private static void writeLimits(WasmLimits limits, BinaryWriter writer) {
-        if (limits.max().isPresent()) {
-            writer.writeByte(0x01);
-            Leb128Encoding.encodeUnsignedInt32(limits.min(), writer);
-            Leb128Encoding.encodeUnsignedInt32(limits.max().getAsInt(), writer);
-        } else {
-            writer.writeByte(0x00);
-            Leb128Encoding.encodeUnsignedInt32(limits.min(), writer);
-        }
-    }
-
-    interface Write {
-        void write() throws IOException;
-    }
-
-    private static void writeSection(
-        SectionType sectionType,
-        BinaryWriter writer,
-        Write writeContent
-    ) throws IOException {
-        writeSection(sectionType.id, writer, writeContent);
-    }
-
-    private static void writeSection(
-        byte id,
-        BinaryWriter writer,
-        Write writeContent
-    ) throws IOException {
-        // https://webassembly.github.io/spec/core/binary/modules.html#sections
-        //
-        // Each section consists of:
-        // * a one-byte section ID
-        // * the u32 size of the contents, in bytes
-        // * the actual contents
-        writer.writeByte(id);
-
-        var sizePosition = writer.position();
-        Leb128Encoding.encodePaddedUnsignedInt32(0, writer);
-
-        var contentStartPosition = writer.position();
-        writeContent.write();
-        var contentEndPosition = writer.position();
-
-        var size = contentEndPosition - contentStartPosition;
-        writer.seek(sizePosition);
-        Leb128Encoding.encodePaddedUnsignedInt32(size, writer);
-        writer.seek(contentEndPosition);
-    }
-
-    interface WriteElement<T> {
-        void write(T element) throws IOException;
-    }
-
-    interface WriteIndexedElement<T> {
-        void write(int index, T element) throws IOException;
-    }
-
-    private static <T> void writeVec(
-        List<T> vec,
-        WriteElement<T> writeElement,
-        BinaryWriter writer
-    ) throws IOException {
-        Leb128Encoding.encodeUnsignedInt32(vec.size(), writer);
-        for (var element : vec) {
-            writeElement.write(element);
-        }
-    }
-
-    private static <T> void writeVec(
-        List<T> vec,
-        WriteIndexedElement<T> writeElement,
-        BinaryWriter writer
-    ) throws IOException {
-        Leb128Encoding.encodeUnsignedInt32(vec.size(), writer);
-        for (var elementIndex = 0; elementIndex < vec.size(); elementIndex++) {
-            writeElement.write(elementIndex, vec.get(elementIndex));
-        }
-    }
-
-    private static void writeString(String value, BinaryWriter writer) {
-        var bytes = value.getBytes(StandardCharsets.UTF_8);
-        Leb128Encoding.encodeUnsignedInt32(bytes.length, writer);
-        writer.writeBytes(bytes);
+        WasmBinaryFormatModules.serializeModule(module, outputStream);
     }
 }
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/types/WasmNumberType.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/types/WasmNumberType.java
new file mode 100644
index 00000000..c40ba00f
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/types/WasmNumberType.java
@@ -0,0 +1,8 @@
+package org.shedlang.compiler.backends.wasm.structure.ast.types;
+
+public enum WasmNumberType {
+    I32,
+    I64,
+    F32,
+    F64,
+}
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/types/WasmValueType.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/types/WasmValueType.java
index d46bc8e8..99664f5c 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/types/WasmValueType.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/types/WasmValueType.java
@@ -1,8 +1,10 @@
 package org.shedlang.compiler.backends.wasm.structure.ast.types;
 
-public enum WasmValueType {
-    I32,
-    I64,
-    F32,
-    F64
+public sealed interface WasmValueType {
+    WasmValueType I32 = new Number(WasmNumberType.I32);
+    WasmValueType I64 = new Number(WasmNumberType.I64);
+    WasmValueType F32 = new Number(WasmNumberType.F32);
+    WasmValueType F64 = new Number(WasmNumberType.F64);
+
+    record Number(WasmNumberType type) implements WasmValueType {}
 }
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/Leb128Encoding.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/Leb128Encoding.java
index bcd7de5f..e0c4734d 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/structure/Leb128Encoding.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/Leb128Encoding.java
@@ -1,4 +1,6 @@
-package org.shedlang.compiler.backends.wasm.structure;
+package org.shedlang.compiler.backends.wasm.structure.binary;
+
+import org.shedlang.compiler.backends.wasm.structure.BinaryWriter;
 
 public class Leb128Encoding {
     private Leb128Encoding() {
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatConventions.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatConventions.java
new file mode 100644
index 00000000..9dc25ffa
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatConventions.java
@@ -0,0 +1,45 @@
+package org.shedlang.compiler.backends.wasm.structure.binary;
+
+import org.shedlang.compiler.backends.wasm.structure.BinaryWriter;
+
+import java.io.IOException;
+import java.util.List;
+
+public class WasmBinaryFormatConventions {
+    // Corresponds to https://webassembly.github.io/spec/core/binary/conventions.html
+
+    private WasmBinaryFormatConventions() {
+    }
+
+    // == Vectors ==
+
+    interface WriteElement<T> {
+        void write(T element) throws IOException;
+    }
+
+    static <T> void writeVec(
+        List<T> vec,
+        WriteElement<T> writeElement,
+        BinaryWriter writer
+    ) throws IOException {
+        Leb128Encoding.encodeUnsignedInt32(vec.size(), writer);
+        for (var element : vec) {
+            writeElement.write(element);
+        }
+    }
+
+    interface WriteIndexedElement<T> {
+        void write(int index, T element) throws IOException;
+    }
+
+    static <T> void writeVec(
+        List<T> vec,
+        WriteIndexedElement<T> writeElement,
+        BinaryWriter writer
+    ) throws IOException {
+        Leb128Encoding.encodeUnsignedInt32(vec.size(), writer);
+        for (var elementIndex = 0; elementIndex < vec.size(); elementIndex++) {
+            writeElement.write(elementIndex, vec.get(elementIndex));
+        }
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatModules.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatModules.java
new file mode 100644
index 00000000..919149aa
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatModules.java
@@ -0,0 +1,182 @@
+package org.shedlang.compiler.backends.wasm.structure.binary;
+
+import org.pcollections.PVector;
+import org.shedlang.compiler.backends.wasm.structure.BinaryWriter;
+import org.shedlang.compiler.backends.wasm.structure.ast.WasmModule;
+import org.shedlang.compiler.backends.wasm.structure.ast.imports.WasmImport;
+import org.shedlang.compiler.backends.wasm.structure.ast.imports.WasmImportDescriptor;
+import org.shedlang.compiler.backends.wasm.structure.ast.types.WasmFuncType;
+
+import java.io.IOException;
+import java.io.OutputStream;
+import java.util.HashMap;
+import java.util.HexFormat;
+import java.util.Map;
+
+import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatConventions.writeVec;
+import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatNameSection.writeNameSection;
+import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatTypes.*;
+import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatValues.writeString;
+
+public class WasmBinaryFormatModules {
+    // Corresponds to https://webassembly.github.io/spec/core/binary/modules.html
+
+    private WasmBinaryFormatModules() {
+    }
+
+    // == Indices ==
+
+    static void writeTypeIndex(int typeIndex, BinaryWriter writer) {
+        Leb128Encoding.encodeUnsignedInt32(typeIndex, writer);
+    }
+
+    static void writeFuncIndex(int funcIndex, BinaryWriter writer) {
+        Leb128Encoding.encodeUnsignedInt32(funcIndex, writer);
+    }
+
+    // == Sections ==
+
+    interface Write {
+        void write() throws IOException;
+    }
+
+    static void writeSection(
+        SectionId sectionId,
+        BinaryWriter writer,
+        Write writeContent
+    ) throws IOException {
+        // https://webassembly.github.io/spec/core/binary/modules.html#sections
+        //
+        // Each section consists of:
+        // * a one-byte section ID
+        // * the u32 size of the contents, in bytes
+        // * the actual contents
+        writer.writeByte(sectionId.id);
+
+        var sizePosition = writer.position();
+        Leb128Encoding.encodePaddedUnsignedInt32(0, writer);
+
+        var contentStartPosition = writer.position();
+        writeContent.write();
+        var contentEndPosition = writer.position();
+
+        var size = contentEndPosition - contentStartPosition;
+        writer.seek(sizePosition);
+        Leb128Encoding.encodePaddedUnsignedInt32(size, writer);
+        writer.seek(contentEndPosition);
+    }
+
+    enum SectionId {
+        CUSTOM(0),
+        TYPE(1),
+        IMPORT(2),
+        FUNCTION(3),
+        TABLE(4),
+        MEMORY(5),
+        GLOBAL(6),
+        EXPORT(7),
+        START(8),
+        ELEMENT(9),
+        CODE(10),
+        DATA(11),
+        DATA_COUNT(12),
+        TAG(13);
+
+        private final byte id;
+
+        SectionId(int id) {
+            this.id = (byte) id;
+        }
+    }
+
+    // == Type Section ==
+
+    private static void writeTypeSection(
+        PVector<WasmFuncType> types,
+        BinaryWriter writer
+    ) throws IOException {
+        if (types.size() > 0) {
+            writeSection(SectionId.TYPE, writer, () -> {
+                writeVec(
+                    types,
+                    type -> writeFuncType(type, writer),
+                    writer
+                );
+            });
+        }
+    }
+
+    // == Import Section ==
+
+    private static void writeImportSection(
+        WasmModule module,
+        BinaryWriter writer
+    ) throws IOException {
+        if (module.imports().size() > 0) {
+            writeSection(SectionId.IMPORT, writer, () -> {
+                var funcTypeToTypeIndex = new HashMap<WasmFuncType, Integer>();
+                for (var funcIndex = 0; funcIndex < module.types().size(); funcIndex++) {
+                    funcTypeToTypeIndex.put(module.types().get(funcIndex), funcIndex);
+                }
+
+                writeVec(
+                    module.imports(),
+                    import_ -> writeImport(import_, funcTypeToTypeIndex, writer),
+                    writer
+                );
+            });
+        }
+    }
+
+    private static void writeImport(
+        WasmImport import_,
+        Map<WasmFuncType, Integer> funcTypeToTypeIndex,
+        BinaryWriter writer
+    ) {
+        writeString(import_.moduleName(), writer);
+        writeString(import_.entityName(), writer);
+        writeImportDesciptor(import_.descriptor(), funcTypeToTypeIndex, writer);
+    }
+
+    private static void writeImportDesciptor(
+        WasmImportDescriptor descriptor,
+        Map<WasmFuncType, Integer> funcTypeToTypeIndex,
+        BinaryWriter writer
+    ) {
+        switch (descriptor) {
+            case WasmImportDescriptor.Func func -> {
+                writer.writeByte(0x00);
+                var typeIndex = funcTypeToTypeIndex.get(func.type());
+                writeTypeIndex(typeIndex, writer);
+            }
+            case WasmImportDescriptor.Table table -> {
+                writer.writeByte(0x01);
+                writeTableType(table.type(), writer);
+            }
+            case WasmImportDescriptor.Memory memory -> {
+                writer.writeByte(0x02);
+                writeMemoryType(memory.type(), writer);
+            }
+            case WasmImportDescriptor.Global global -> {
+                writer.writeByte(0x03);
+                writeGlobalType(global.type(), writer);
+            }
+        }
+    }
+
+    // == Modules ==
+
+    private static final byte[] WASM_MAGIC = HexFormat.of().parseHex("0061736D");
+    private static final byte[] WASM_VERSION = HexFormat.of().parseHex("01000000");
+
+    public static void serializeModule(WasmModule module, OutputStream outputStream) throws IOException {
+        var writer = new BinaryWriter();
+        writer.writeBytes(WASM_MAGIC);
+        writer.writeBytes(WASM_VERSION);
+        writeTypeSection(module.types(), writer);
+        writeImportSection(module, writer);
+        writeNameSection(module, writer);
+
+        outputStream.write(writer.toBytes());
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatNameSection.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatNameSection.java
new file mode 100644
index 00000000..31b5a9ab
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatNameSection.java
@@ -0,0 +1,95 @@
+package org.shedlang.compiler.backends.wasm.structure.binary;
+
+import org.shedlang.compiler.backends.wasm.structure.BinaryWriter;
+import org.shedlang.compiler.backends.wasm.structure.ast.WasmModule;
+import org.shedlang.compiler.backends.wasm.structure.ast.imports.WasmImportDescriptor;
+import org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatModules.SectionId;
+
+import java.io.IOException;
+import java.util.List;
+import java.util.stream.Stream;
+
+import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatConventions.writeVec;
+import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatModules.writeFuncIndex;
+import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatModules.writeSection;
+import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatValues.writeString;
+
+public class WasmBinaryFormatNameSection {
+    // Corresponds to https://webassembly.github.io/spec/core/appendix/custom.html#name-section
+
+    private WasmBinaryFormatNameSection() {
+    }
+
+    // == Name Section ==
+
+    static void writeNameSection(WasmModule module, BinaryWriter writer) throws IOException {
+        if (module.imports().size() > 0) {
+            writeSection(SectionId.CUSTOM, writer, () -> {
+                writeString("name", writer);
+                writeNameSectionFunctionNameSubsection(module, writer);
+            });
+        }
+    }
+
+    // == Subsections ==
+
+    private static void writeNameSubsection(
+        NameSubsectionId sectionId,
+        BinaryWriter writer,
+        WasmBinaryFormatModules.Write writeContent
+    ) throws IOException {
+        writer.writeByte(sectionId.id);
+
+        var sizePosition = writer.position();
+        Leb128Encoding.encodePaddedUnsignedInt32(0, writer);
+
+        var contentStartPosition = writer.position();
+        writeContent.write();
+        var contentEndPosition = writer.position();
+
+        var size = contentEndPosition - contentStartPosition;
+        writer.seek(sizePosition);
+        Leb128Encoding.encodePaddedUnsignedInt32(size, writer);
+        writer.seek(contentEndPosition);
+    }
+
+    private enum NameSubsectionId {
+        MODULE_NAME(0),
+        FUNCTION_NAMES(1),
+        LOCAL_NAMES(2);
+
+        private final byte id;
+
+        NameSubsectionId(int id) {
+            this.id = (byte) id;
+        }
+    }
+
+    // == Name Maps ==
+
+    private static void writeNameMap(BinaryWriter writer, List<WasmImportDescriptor.Func> importedFunctions) throws IOException {
+        writeVec(
+            importedFunctions,
+            (funcIndex, func) -> {
+                writeFuncIndex(funcIndex, writer);
+                writeString(func.identifier(), writer);
+            },
+            writer
+        );
+    }
+
+    // == Function Names ==
+
+    private static void writeNameSectionFunctionNameSubsection(WasmModule module, BinaryWriter writer) throws IOException {
+        writeNameSubsection(NameSubsectionId.FUNCTION_NAMES, writer, () -> {
+            var importedFunctions = module.imports().stream()
+                .flatMap(import_ -> switch (import_.descriptor()) {
+                    case WasmImportDescriptor.Func func -> Stream.of(func);
+                    default -> Stream.empty();
+                })
+                .toList();
+
+            writeNameMap(writer, importedFunctions);
+        });
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatTypes.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatTypes.java
new file mode 100644
index 00000000..97a8e7db
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatTypes.java
@@ -0,0 +1,101 @@
+package org.shedlang.compiler.backends.wasm.structure.binary;
+
+import org.shedlang.compiler.backends.wasm.structure.BinaryWriter;
+import org.shedlang.compiler.backends.wasm.structure.ast.types.*;
+
+import java.io.IOException;
+import java.util.List;
+
+import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatConventions.writeVec;
+
+public class WasmBinaryFormatTypes {
+    // Corresponds to https://webassembly.github.io/spec/core/binary/types.html
+
+    private WasmBinaryFormatTypes() {
+    }
+
+    // == Number Types ==
+
+    static void writeNumberType(WasmNumberType type, BinaryWriter writer) {
+        var encoding = switch (type) {
+            case I32 -> 0x7f;
+            case I64 -> 0x7e;
+            case F32 -> 0x7d;
+            case F64 -> 0x7c;
+        };
+        writer.writeByte((byte) encoding);
+    }
+
+    // == Reference Types ==
+
+    static void writeReferenceType(WasmReferenceType type, BinaryWriter writer) {
+        var encoding = switch (type) {
+            case FUNC_REF -> 0x70;
+            case EXTERN_REF -> 0x6f;
+        };
+        writer.writeByte(encoding);
+    }
+
+    // == Value Types ==
+
+    static void writeValueType(WasmValueType type, BinaryWriter writer) {
+        switch (type) {
+            case WasmValueType.Number number -> {
+                writeNumberType(number.type(), writer);
+            }
+        }
+    }
+
+    private static void writeValueTypeVector(List<WasmValueType> types, BinaryWriter writer) throws IOException {
+        writeVec(
+            types,
+            type -> writeValueType(type, writer),
+            writer
+        );
+    }
+
+    // == Function Types ==
+
+    static void writeFuncType(WasmFuncType type, BinaryWriter writer) throws IOException {
+        writer.writeByte((byte) 0x60);
+        writeValueTypeVector(type.params(), writer);
+        writeValueTypeVector(type.results(), writer);
+    }
+
+    // == Limits ==
+
+    static void writeLimits(WasmLimits limits, BinaryWriter writer) {
+        if (limits.max().isPresent()) {
+            writer.writeByte(0x01);
+            Leb128Encoding.encodeUnsignedInt32(limits.min(), writer);
+            Leb128Encoding.encodeUnsignedInt32(limits.max().getAsInt(), writer);
+        } else {
+            writer.writeByte(0x00);
+            Leb128Encoding.encodeUnsignedInt32(limits.min(), writer);
+        }
+    }
+
+    // == Memory Types ==
+
+    static void writeMemoryType(WasmMemoryType type, BinaryWriter writer) {
+        writeLimits(type.limits(), writer);
+    }
+
+    // == Table Types ==
+
+    static void writeTableType(WasmTableType type, BinaryWriter writer) {
+        writeReferenceType(type.elementType(), writer);
+        writeLimits(type.limits(), writer);
+    }
+
+    // == Global Types ==
+
+    static void writeGlobalType(WasmGlobalType type, BinaryWriter writer) {
+        writeValueType(type.valueType(), writer);
+        var mutabilityEncoding = switch (type.mutability()) {
+            case MUTABLE -> 0x01;
+            case IMMUTABLE -> 0x00;
+        };
+        writer.writeByte(mutabilityEncoding);
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatValues.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatValues.java
new file mode 100644
index 00000000..b34dc7e2
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatValues.java
@@ -0,0 +1,15 @@
+package org.shedlang.compiler.backends.wasm.structure.binary;
+
+import org.shedlang.compiler.backends.wasm.structure.BinaryWriter;
+
+import java.nio.charset.StandardCharsets;
+
+public class WasmBinaryFormatValues {
+    // Corresponds to https://webassembly.github.io/spec/core/binary/values.html
+
+    static void writeString(String value, BinaryWriter writer) {
+        var bytes = value.getBytes(StandardCharsets.UTF_8);
+        Leb128Encoding.encodeUnsignedInt32(bytes.length, writer);
+        writer.writeBytes(bytes);
+    }
+}