BinParser.v3

// Copyright 2019 Ben L. Titzer. All rights reserved.
// See LICENSE for details of Apache 2.0 license.

// Parses the binary format of WebAssembly and produces an in-memory module
// representation. The parser uses a "push" model which allows the creator to
// input segments of data into the parser incrementally, e.g. if streaming it
// over a network.
class BinParser(extensions: Extension.set, limits: Limits, err: ErrorGen, filename: string) extends BpFsmCallback {
	var tiering: ExecutionStrategy;
	var validate_code = true;
	var names = !TraceOptions.NO_NAMES.get();

	private def cache = Canon.globalCache;
	private var validator: CodeValidator;
	private var parser: WasmParser;
	private var decoder: DataReader;
	private var fsm: BpFsm;
	private var seen_section = -1;
	private var seen_sections = Array<bool>.new(BpSection.count);
	private var declared_func_count: u32;
	private var func_body_cursor: int;
	private var subtype_list: Vector<(u64, int)>;

	new() super(Module.new(filename)) {
		fsm = BpFsm.new(extensions, limits, err, this);
		decoder = fsm.decoder;
		parser = WasmParser.new(extensions, limits, module, err, fsm.decoder);
		if (tiering != null) tiering.onModuleStart(module, 0);
	}

	// Push new data into the parser from the specified range. The given
	// array is not modified or retained by this call; internal copies of
	// data are made if necessary. However, do not pass an array that could
	// be concurrently modified, as it may be decoded in place.
	def push(x: Array<byte>, xpos: int, xlength: int) -> this {
		if (xlength == 0) return; // nothing to do
		if (err.error()) return;  // already hit an error

		Metrics.load_time_us.run(fsm.push, (x, xpos, xlength));
	}
	// Finish the decoding of the pushed bytes, returning a valid module
	// upon success, or an error in {ErrorGen}.
	def finish() -> Module {
		return Metrics.load_time_us.run(finish0, ());
	}
	private def finish0() -> Module {
		var func_count = declared_func_count;
		if (func_count > 0 && !seen_sections[BpSection.Code.code]) {
			err.at(decoder).MissingCodeSection(func_count);
		}
		var data_count = module.explicit_data_count;
		if (data_count > 0 && !seen_sections[BpSection.Data.code]) {
			err.at(decoder.atLimit()).MissingDataSection(data_count);
		}
		return fsm.finish(if(tiering != null, tiering.onModuleFinish));
	}

	def decodeSection(kind: BpSection, size: u32, d: DataReader) {
		var start = d.pos;
		decoder = parser.decoder = d;
//		parser.debugBuffer();
		enforceSectionOrder(kind, d.addr_of(d.pos-1));
		err.section = kind;
		match (kind) {
			Unknown => readCustomSection(size);
			Type => {
				var count = readCountAndReserve("types", module.heaptypes, limits.max_num_types);
				readLoop("type", count, readDefType);
			}
			Import => {
				var count = readCountAndReserve("imports", module.imports, limits.max_num_imports);
				readLoop("imports", count, readImportDecl);
			}
			Function => {
				var count = readCountAndReserve("functions", module.functions, limits.max_num_functions);
				declared_func_count = u32.!(count);
				readLoop("functions", count, readFuncDecl);
			}
			Table => {
				var count = readCountAndReserve("tables", module.tables, limits.max_num_tables);
				readLoop("tables", count, readTableDecl);
			}
			Memory => {
				var count = readCountAndReserve("memories", module.memories, limits.max_num_memories);
				readLoop("memories", count, readMemoryDecl);
			}
			Tag => {
				var count = readCountAndReserve("tags", module.tags, limits.max_num_tags);
				readLoop("tags", count, readTagDecl);
			}
			Global => {
				var count = readCountAndReserve("globals", module.globals, limits.max_num_globals);
				readLoop("globals", count, readGlobalDecl);
			}
			Export => {
				var count = readCountAndReserve("exports", module.exports, limits.max_num_exports);
				var set = StringSet.new(count);
				readLoop("exports", count, readExportDecl(_, set));
			}
			// note: Code section handled specially by BpFsm.
			Data => {
				var pos = decoder.pos;
				var count = readCountAndReserve("data segments", module.data, limits.max_num_data_segments);
				if (module.explicit_data_count >= 0 && count != module.explicit_data_count) {
					return err.rel(decoder, pos).DataCountMismatch(module.explicit_data_count, u32.!(count));
				}
				readLoop("data segments", count, readDataDecl);
			}
			Element => {
				var count = readCountAndReserve("elements", module.elems, limits.max_num_table_entries);
				readLoop("elements", count, readElemDecl);
			}
			Start => readStartSection();
			DataCount => readDataCountSection();
			_ => return err.at(d).InvalidSectionCode(kind.code);
		}
		if (Trace.binparse) {
			Trace.OUT.put2("======== end section code %d (%s) ========", kind.code, kind.name).ln();
		}

		err.section = BpSection.Unknown;
		var read = u64.!(d.pos - start);
		if (read < size) {
			err.at(d).IncompleteSection(kind.code, read, size);
		}
	}
	def enforceSectionOrder(kind: BpSection, addr: u64) {
		if (kind == BpSection.Unknown) return;
		if (!extensions.REPEAT_SECTIONS) {
			// enforce section ordering and uniqueness
			if (seen_sections[kind.code]) return err.abs(addr).DuplicateSection(kind);
			else if (kind.tag < seen_section) return err.abs(addr).OutOfOrderSection(kind);
		}
		seen_sections[kind.code] = true;
		seen_section = kind.tag;
	}
	def beginCodeSection(addr: u64, count: u32) {
		var kind = BpSection.Code;
		enforceSectionOrder(kind, addr);
		if (count != declared_func_count) {
			// TODO: count >= remaining_func_count ?
			err.abs(addr).FuncCountMismatch(declared_func_count, count);
		}
		if (tiering != null) tiering.onCodeSectionStart(module, count, 0); // TODO: size
	}
	def readCustomSection(size: u32) {
		var start = decoder.pos;
		var name = parser.readUtf8String("custom section name");
		var payload_len = int.!(size) - (decoder.pos - start);
		if (payload_len < 0) {
			return err.rel(decoder, start).CustomSectionNameLengthTooLong(name.length, size);
		}
		var payload = decoder.readN(payload_len);
		module.custom_sections.put(CustomSection.new(name, payload));
		if (names && Strings.equal("name", name)) module.names = NameSection.new(module, payload);
	}
	def readLoop(thing_name: string, count: int, read: int -> void) {
		for (i < count) {
			if (err.error()) break;
			err.index = i;
			if (Trace.binparse) Trace.OUT.put2("-->%s #%d", thing_name, i).ln();
			read(i);
		}
	}
	def readStartSection() {
		var pt = decoder.pos;
		var f = parser.readFuncRef();
		if (f != null) {
			module.start_function = f.func_index;
			var sig = f.sig;
			if (sig.params.length > 0 || sig.results.length > 0) {
				err.rel(decoder, pt).IllegalStartFunctionType(sig);
			}
		}
	}
	def readDataCountSection() {
		var count = parser.readU32_i("data count", limits.max_num_data_segments);
		if (count < limits.max_grow_size) module.data.grow(count);
		module.explicit_data_count = count;
	}
	def decodeFunctionBody(index: u32, size: u32, decoder: DataReader) {
		if (Trace.binparse) Trace.OUT.put1("-->body #%d", index).ln();
		parser.decoder = decoder;
		var start = decoder.pos;
		var f: FuncDecl, i = func_body_cursor;
		err.section = BpSection.Code;
		err.index = i;
		while (true) {
			if (i >= module.functions.length) {
				err.at(decoder).FuncCountMismatch(declared_func_count, index);
				return;
			}
			f = module.functions[i++];
			if (!f.imported()) break;
		}
		func_body_cursor = i;
		var body = decoder.readN(int.!(size));
		if (tiering != null) tiering.onFuncBody(module, index, body, err);
		decoder.at(start);
		f.setOrigCode(body);
		if (!validate_code) return;
		if (validator == null) validator = CodeValidator.new(extensions, limits, module, err);
		if (tiering != null) tiering.onFuncValidationStart(module, f);
		var r = validator.validate(f, decoder);
		if (tiering != null) tiering.onFuncValidationFinish(module, f, err);
	}
	def readI32Expr(quantity: string) -> InitExpr {
		return readInitExpr(quantity, ValueType.I32);
	}
	def readInitExpr(quantity: string, expected: ValueType) -> InitExpr {
		var prev_pos = decoder.pos;
		if (validator == null) validator = CodeValidator.new(extensions, limits, module, err);
		var sig: SigDecl;
		match (expected) {
			I32 => sig = SigCache.v_i;
			I64 => sig = SigCache.v_l;
			F32 => sig = SigCache.v_f;
			F64 => sig = SigCache.v_d;
			V128 => sig = SigCache.v_s;
			_ => sig = SigDecl.new(true, ValueTypes.NO_HEAPTYPES, SigCache.arr_v, [expected]);
		}
		var r = validator.validateInitExpr(sig, decoder);
		match (r) {
			Ok => return validator.init_stack.pop();
			_ => return InitExpr.I32(0); // TODO: return invalid initexpr?
		}
	}
	def readTableDecl(index: int) {
		var pt = decoder.pos;
		var decl: TableDecl;
		if (extensions.FUNCTION_REFERENCES && decoder.peek1() == 0x40) {
			parser.readByte("table type", BpConstants.renderNone);
			var zero = decoder.read1();
			if (zero != 0) err.rel(decoder, pt + 1).ExpectedTableTypeZeroByte(zero);
			var elemType = readElemType();
			var limits = readTableLimits();
			decl = TableDecl.new(elemType, limits.size);
			decl.has_default_elem = true;
			decl.default_elem = readInitExpr("table elem initializer", elemType);
		} else {
			var elemType = readElemType();
			var limits = readTableLimits();
			if (!ValueTypes.hasDefaultValue(elemType)) {
				err.rel(decoder, pt).ExpectedTypeWithDefaultValue(elemType);
			}
			decl = TableDecl.new(elemType, limits.size);
		}
		module.addDecl(decl);
	}
	def readCountAndReserve<T>(quantity: string, vec: Vector<T>, max: u32) -> int {
		var pt = decoder.pos;
		var count = parser.readU32_i(quantity, max);
		var total = vec.length + count;
		if (total > max) {
			err.rel(decoder, pt).TotalExceededMaximum(quantity, u32.!(total), max);
		} else {
			vec.grow(total);
		}
		return count;
	}
	def reserveOne<T>(pt: int, quantity: string, vec: Vector<T>, max: u32) {
		var total = u32.view(vec.length) + 1u;
		if (total > max) {
			err.rel(decoder, pt).TotalExceededMaximum(quantity, total, max);
		}
	}
	def readTableLimits() -> TableLimits {
		var pt = decoder.pos;
		var flags = parser.readByte("table flags", BpConstants.renderTableFlags);
		if ((flags & ~(limits.ok_table_flags)) != 0) err.rel(decoder, pt).InvalidTableFlags(flags);
		var size = readSizeConstraint(flags, limits.max_num_table_entries, "table");
		return TableLimits(size);

	}
	def readMemLimits() -> MemLimits {
		var pt = decoder.pos;
		var flags = parser.readByte("memory flags", BpConstants.renderMemoryFlags);
		if ((flags & ~(limits.ok_memory_flags)) != 0) err.rel(decoder, pt).InvalidMemoryFlags(flags);

		var size = readSizeConstraint(flags, limits.max_legal_memory_pages, "memory");

		var shared = (flags & BpMemoryFlag.Shared.mask) != 0;
		if (shared && size.maximum == Max.None) err.rel(decoder, pt).ExpectedSharedMemoryMaximum();

		var log2_pageSize: u5 = BpConstants.log2_WASM_PAGE_SIZE;
		var has_page_size = (flags & BpMemoryFlag.HasPageSize.mask) != 0;
		if (has_page_size) {
			log2_pageSize = u5.!(parser.readU32("pagesize (log2)", limits.max_log2_page_size));
		}

		return MemLimits(size, shared, log2_pageSize);
	}
	def readSizeConstraint(flags: byte, maxLegal: u64, quantity: string) -> SizeConstraint {
		var is64 = (flags & BpMemoryFlag.Is64.mask) != 0;
		var initial = parser.readU32orU64(is64, "initial", maxLegal);
		if ((flags & BpMemoryFlag.HasMax.mask) == 0) {
			return SizeConstraint(is64, initial, Max.None);
		}
		var pt = decoder.pos;
		var max = parser.readU32orU64(is64, "maximum", maxLegal);
		if (max < initial) err.rel(decoder, pt).MaximumLessThanInitial(quantity, max, initial);
		return SizeConstraint(is64, initial, Max.Set(max));
	}
	def readElemType() -> ValueType.Ref {
		return parser.readRefType(true);
	}
	def readDefType(index: int) {
		var recgrp_start = module.heaptypes.length;
		parser.max_fw_index = recgrp_start;
		var pt = decoder.pos;
		var code = readDefTypeCode();
		if (extensions.GC) {
			var count = 1;
			if (code == BpDefTypeCode.REC.code) { // parse as a recursion group
				count = parser.readU32_i("recursion group count", limits.max_num_types);
				parser.max_legal_index = recgrp_start + count;
				for (i < count) {
					var pt = decoder.pos;
					var code = readDefTypeCode();
					readDefSingleType(pt, code, ValueTypes.NO_HEAPTYPES);
				}
			} else { // treat as a single type in its own recursion group
				parser.max_legal_index = recgrp_start + count;
				readDefSingleType(pt, code, ValueTypes.NO_HEAPTYPES);
			}
			if (err.ok()) {
				cache.doGroup(module.heaptypes, recgrp_start, count);
				parser.max_fw_index = parser.max_legal_index = module.heaptypes.length;
				if (subtype_list != null && subtype_list.length > 0) { // check declared subtypes
					for (i < subtype_list.length) {
						var t = subtype_list[i];
						if (t.1 >= module.heaptypes.length) continue; // potential decode error
						HeapTypeDecls.checkSupertypes(t.0, module.heaptypes[t.1], err);
					}
					subtype_list.clear();
				}
			}
		} else {
			// parse a single type
			parser.max_legal_index = parser.max_fw_index;
			readDefSingleType(pt, code, ValueTypes.NO_HEAPTYPES);
			if (err.ok()) {
				var i = module.heaptypes.length - 1;
				module.heaptypes[i] = cache.doOne(module.heaptypes[i]);
				parser.max_fw_index = parser.max_legal_index = module.heaptypes.length;
			}
		}
	}
	def readDefTypeCode() -> byte {
		return parser.readByte("deftype code", BpConstants.renderDefTypeCode); // XXX: LEB not allowed here
	}
	def readDefSingleType(pt: int, code: byte, supertypes: Array<HeapType>) {
		var final = 1;
		if (extensions.GC) {
			if (code == BpDefTypeCode.SUB.code) final = 0;
			else if (code == BpDefTypeCode.SUB_FINAL.code) final = 1;
			else final = 2;
			if (final != 2) {
				var count = parser.readU32_i("supertype count", limits.max_supertypes);
				supertypes = Array<HeapType>.new(count);
				for (i < count) {
					var pt = decoder.pos;
					var index = parser.readU32_i("type index", u32.view(module.heaptypes.length));
					supertypes[i] = parser.toHeapType(pt, index);
				}
				pt = decoder.pos;
				code = readDefTypeCode();

				if (subtype_list == null) subtype_list = Vector.new();
				subtype_list.put(decoder.addr_of(pt), module.heaptypes.length);
			}
		}

		match (code) {
			BpDefTypeCode.Function.code => return readDefFuncType(final != 0, supertypes);
			BpDefTypeCode.Struct.code => if (extensions.GC) return readDefStructType(final != 0, supertypes);
			BpDefTypeCode.Array.code => if (extensions.GC) return readDefArrayType(final != 0, supertypes);
			BpDefTypeCode.Continuation.code => {
				if (extensions.STACK_SWITCHING)
					return readDefContType(final != 0, supertypes);
			}
		}
		err.rel(decoder, pt).InvalidTypeDeclCode(code);
	}
	def readDefFuncType(final: bool, supertypes: Array<HeapType>) {
		var ptypes = parser.readValueTypes("param count", limits.max_num_func_params);
		if (!err.ok()) return;
		var rtypes = parser.readValueTypes("result count", limits.max_num_func_results);
		if (!err.ok()) return;
		var decl = SigDecl.new(final, supertypes, ptypes, rtypes);
		module.addDecl(decl);
		decl.recgrp_index = decl.heaptype_index - parser.max_fw_index;
	}
	def readDefStructType(final: bool, supertypes: Array<HeapType>) {
		var count = parser.readU32_i("field count", limits.max_num_struct_fields);
		if (!err.ok()) return;
		var field_types = Array<StorageType>.new(count);
		for (j < field_types.length) {
			field_types[j] = readStorageType();
		}
		if (!err.ok()) return;
		var decl = StructDecl.new(final, supertypes, field_types);
		module.addDecl(decl);
		decl.recgrp_index = decl.heaptype_index - parser.max_fw_index;
	}
	def readDefArrayType(final: bool, supertypes: Array<HeapType>) {
		var elem_type = readStorageType();
		if (!err.ok()) return;
		var decl = ArrayDecl.new(final, supertypes, [elem_type]);
		module.addDecl(decl);
		decl.recgrp_index = decl.heaptype_index - parser.max_fw_index;
	}
	def readDefContType(final: bool, supertypes: Array<HeapType>) {
		var pt = decoder.pos;
		var sig_index = parser.readU32_i("cont sigature index", u32.!(module.heaptypes.length));
		if (!err.ok()) return;
		var sig_htype = module.heaptypes[sig_index];
		if (!SigDecl.?(sig_htype)) {
			err.rel(decoder, pt).ExpectedSignature(sig_htype);
			return;
		}
		var decl = ContDecl.new(final, supertypes, SigDecl.!(sig_htype));
		module.addDecl(decl);
		decl.recgrp_index = decl.heaptype_index - parser.max_fw_index;
	}
	def readStorageType() -> StorageType {
		var pt = decoder.pos;
		var code = parser.readTypeCode();
		var vt: ValueType, packed: Packedness;
		match (code) {
			BpTypeCode.I8.val => { vt = ValueType.I32; packed = Packedness.PACKED_I8; }
			BpTypeCode.I16.val => { vt = ValueType.I32; packed = Packedness.PACKED_I16; }
			_ => vt = parser.readValueTypeSuffix(pt, code);
		}
		var mut = readMutability();
		return StorageType(vt, packed, mut);
	}
	def readImportDecl(index: int) {
		var module_name = parser.readUtf8String("import module name");
		var field_name = parser.readUtf8String("import field name");
		var pt = decoder.pos;
		var kind = parser.readByte("import kind", BpConstants.renderImportKind);
		var decl: Decl;
		match (kind) {
			BpImportExportKind.Function.code => {
				reserveOne(pt, "functions", module.functions, limits.max_num_functions);
				var sig_index = parser.readSigIndex();
				decl = FuncDecl.new(sig_index);
			}
			BpImportExportKind.Table.code => {
				reserveOne(pt, "tables", module.tables, limits.max_num_tables);
				var et = readElemType();
				var l = readTableLimits();
				decl = TableDecl.new(et, l.size);
			}
			BpImportExportKind.Memory.code => {
				reserveOne(pt, "memories", module.memories, limits.max_num_memories);
				var l = readMemLimits();
				decl = MemoryDecl.new(l.size, l.shared, l.log2_pageSize);
			}
			BpImportExportKind.Global.code => {
				reserveOne(pt, "globals", module.globals, limits.max_num_globals);
				var t = parser.readValueType();
				var mut = readMutability();
				decl = GlobalDecl.new(t, mut, InitExpr.I32(0));
			}
			BpImportExportKind.Tag.code => {
				reserveOne(pt, "tags", module.tags, limits.max_num_tags);
				var b = parser.readByte("attribute", BpConstants.renderAttribute);
				var sig_index = parser.readSigIndex();
				decl = TagDecl.new(sig_index);
			}
		}
		if (decl == null) err.rel(decoder, pt).InvalidImportKind(kind);
		else module.addImport(module_name, field_name, decl);
	}
	def readFuncDecl(index: int) {
		var pt = decoder.pos;
		var sig_index = parser.readSigIndex();
		var decl = FuncDecl.new(sig_index);
		module.addDecl(decl);
	}
	def readMemoryDecl(index: int) {
		var l = readMemLimits();
		var decl = MemoryDecl.new(l.size, l.shared, l.log2_pageSize);
		module.addDecl(decl);
	}
	def readTagDecl(index: int) {
		var pt = decoder.pos;
		var b = parser.readByte("attribute", BpConstants.renderAttribute);
		if (b != 0) err.rel(decoder, pt).InvalidTagAttribute(b);
		pt = decoder.pos;
		var sig_index = parser.readSigIndex();
		var decl = TagDecl.new(sig_index);
		module.addDecl(decl);
		if (u32.view(sig_index) < module.heaptypes.length) {
			var sig = SigDecl.!(module.heaptypes[sig_index]);
			if (sig.results.length > 0 && !extensions.STACK_SWITCHING) {
				err.rel(decoder, pt).InvalidTagSignature(sig);
			}
		}
	}
	def readGlobalDecl(index: int) {
		var vt = parser.readValueType();
		var mut = readMutability();
		var pos = decoder.pos;
		var expr = readInitExpr("global initializer", vt);
		var decl = GlobalDecl.new(vt, mut, expr);
		module.addDecl(decl);
	}
	def readMutability() -> bool {
		var pt = decoder.pos;
		var flags = parser.readByte("mutability", BpConstants.renderMutability);
		if ((flags & 0xFE) != 0) {
			err.rel(decoder, pt).InvalidGlobalFlags(flags);
		}
		return (flags & BpGlobalFlag.Mutable.mask) != 0;
	}
	def readExportDecl(index: int, exportSet: StringSet) {
		var pt = decoder.pos;
		var name = parser.readUtf8String("export name");
		if (exportSet != null && exportSet.add(name)) {
			err.rel(decoder, pt).DuplicateExport(index);
		}
		var decl = readExportWithoutName();
		module.exports.put(name, decl);
	}
	def readExportWithoutName() -> Decl {
		var pt = decoder.pos;
		var kind = parser.readByte("export kind", BpConstants.renderImportKind);
		var decl: Decl;
		match (kind) {
			BpImportExportKind.Function.code => decl = parser.readFuncRef();
			BpImportExportKind.Table.code => decl = parser.readTableRef();
			BpImportExportKind.Memory.code => decl = parser.readMemoryRef(true);
			BpImportExportKind.Global.code => decl = parser.readGlobalRef();
			BpImportExportKind.Tag.code => decl = parser.readTagRef();
			_ => err.rel(decoder, pt).InvalidExportKind(kind);
		}
		return decl;
	}
	def readElemDecl(index: int) {
		var pt = decoder.pos;
		var flags = parser.readByte("elem flags", BpConstants.renderNone);
		var vt: ValueType = ValueTypes.FUNCREF, mode: SegmentMode, details: ElemDetails;
		match (flags) {
			0 => {
				var t = parser.checkTableIndex(pt, 0);
				var offset = readI32Expr("elements offset");
				mode = SegmentMode.Active(t.1, offset);
				details = readElemFuncIndexes(t.1);
			}
			1 => {
				mode = SegmentMode.Passive;
				parser.readElemKind();
				details = readElemFuncIndexes(int.max);
			}
			2 => {
				var t = parser.readAndCheckTableIndex();
				var offset = readI32Expr("elements offset");
				parser.readElemKind();
				mode = SegmentMode.Active(t.1, offset);
				details = readElemFuncIndexes(t.1);
			}
			3 => {
				mode = SegmentMode.Declarative;
				parser.readElemKind();
				details = readElemFuncIndexes(int.max);
			}
			4 => {
				var t = parser.checkTableIndex(pt, 0);
				var offset = readI32Expr("elements offset");
				mode = SegmentMode.Active(t.1, offset);
				var elemtype = if(t.0 != null, ValueType.Ref(true, t.0.elemtype.heap), ValueTypes.FUNCREF);
				checkElemsType(pt, t.0, elemtype);
				details = readElemInitExprs(vt);
			}
			5 => {
				mode = SegmentMode.Passive;
				vt = parser.readRefType(false);
				details = readElemInitExprs(vt);
			}
			6 => {
				var t = parser.readAndCheckTableIndex();
				var offset = readI32Expr("elements offset");
				mode = SegmentMode.Active(t.1, offset);
				vt = parser.readRefType(false);
				checkElemsType(pt, t.0, vt);
				details = readElemInitExprs(vt);
			}
			7 => {
				mode = SegmentMode.Declarative;
				vt = parser.readRefType(false);
				details = readElemInitExprs(vt);
			}
			_ => {
				err.rel(decoder, pt).InvalidElemFlags(flags);
			}
		}
		var d = ElemDecl.new(vt, mode, details);
		module.elems.put(d);
	}
	def readElemFuncIndexes(table_index: int) -> ElemDetails.FuncRefs {
		var count = parser.readU32_i("element count", limits.max_num_table_entries);
		var elemType: ValueType, expected_sig: SigDecl;
		if (table_index < module.tables.length) {
			elemType = module.tables[table_index].elemtype;
			match (elemType) {
				Ref(nullable, heap) => match (heap) {
					Func(sig) => expected_sig = sig;
					_ => err.at(decoder).TypeMismatchInElemInit(elemType, ValueTypes.FUNCREF);
				}
				_ => err.at(decoder).TypeMismatchInElemInit(elemType, ValueTypes.FUNCREF);
			}
		}
		var array = Array<int>.new(count);
		for (i < array.length) {
			var pt = decoder.pos;
			var f = parser.readFuncRef();
			if (f != null) {
				f.reffed = true;
				array[i] = f.func_index;
				if (expected_sig != null && !f.sig.isAssignableSig(expected_sig)) {
					err.rel(decoder, pt).TypeMismatchInElemInit(elemType, ValueTypes.RefFunc(false, f.sig));
				}
			}
		}
		return ElemDetails.FuncRefs(array);
	}
	def readElemInitExprs(elemType: ValueType) -> ElemDetails.Exprs {
		var count = parser.readU32_i("element count66", limits.max_num_table_entries);
		var array = Array<InitExpr>.new(count);
		for (i < array.length) {
			var pt = decoder.pos;
			var expr = readInitExpr("element", elemType);
			array[i] = expr;
		}
		return ElemDetails.Exprs(array);
	}
	def readDataDecl(index: int) {
		var pt = decoder.pos;
		var flags = parser.readByte("data flags", BpConstants.renderNone);
		var mode: SegmentMode;
		match (flags) {
			0 => {
				var mem_index = parser.checkIndex(pt, "memory", 0, module.memories.length).1;
				var offset = readI32Expr("data element offset");
				mode = SegmentMode.Active(mem_index, offset);
			}
			1 => {
				mode = SegmentMode.Passive;
			}
			2 => {
				var mem_index = parser.readMemoryIndex();
				var offset = readI32Expr("data element offset");
				mode = SegmentMode.Active(mem_index, offset);
			}
			_ => {
				err.rel(decoder, pt).InvalidDataFlags(flags);
			}
		}
		var len = parser.readU32_i("data segment size", limits.max_data_segment_size);
		var data = decoder.readN(len);
		var d = DataDecl.new(mode, data);
		module.data.put(d);
	}
	def checkElemsType(pt: int, table: TableDecl, vt: ValueType) {
		if (table == null) return;
		if (ValueTypes.isAssignable(vt, table.elemtype)) return;
		err.rel(decoder, pt).ElementTypeMismatch(table.elemtype, vt);
	}
} // end BinParser

// A finite state machine that implements a push-based parser for binary
// modules. This class handles the decoding of complete sections and complete
// function bodies, invoking callbacks when sections, bodies, and the overall
// module is finished.
class BpFsm extends WasmParser {
	def callback: BpFsmCallback;
	var section_decoder: DataReader;
	var function_decoder: DataReader;

	// Internal state
	var state: BpFsmState;
	var current_pos: int;
	var more = true;
	var accept = false;
	var current_section: BpSection;
	var section_start: u64;
	var section_size: u32;
	var function_body_count: u32;
	var current_function_body: u32;
	var function_body_start: u64;
	var function_body_size: u32;
	private var total_bytes: u32;

	new(extensions: Extension.set, limits: Limits, err: ErrorGen, callback: BpFsmCallback)
			super(extensions, limits, callback.module,
				err,
				Decoder.new(null, err)) {
		decoder.onEOF = eof_set_flag;
		section_decoder = Decoder.new(null, err);
		section_decoder.onEOF = eof_is_section_overflow;
		function_decoder = Decoder.new(null, err);
		function_decoder.onEOF = eof_is_function_overflow;
	}

	def push(x: Array<byte>, xpos: int, xlength: int) {
		eof = false;
		decoder.putk(0, x, xpos, xlength);
		var l = u32.!(xlength);
		total_bytes += l;
		Metrics.load_bytes.val += l;
		decodeLoop();
	}
	def finish(onAccept: (Module, u32, ErrorGen) -> void) -> Module {
		eof = false;
		more = false;
		decodeLoop();
		if (accept) {
			if (onAccept != null && err.ok()) onAccept(callback.module, total_bytes, err);
			if (err.ok()) return callback.module;
		}
		return null;
	}

	private def decodeLoop() {
		while (true) {
			advance();
			if (eof) return;
			if (accept) return;
			if (err.error()) return;
		}
	}
	private def advance() {
		current_pos = decoder.pos;
		if (Trace.binparse) {
// TODO: this is debug code, not tracing code
//			Trace.OUT.put3("@+%d [%d bytes] BpFsm.state=%s", decoder.addr(),
//				decoder.available(), state.name).ln();
		}
		match (state) {
			MAGIC => {
				if (Trace.binparse) Trace.OUT.puts("======== begin module ========").ln();
				var pt = decoder.pos;
				var magic = decoder.read_u32();
				if (eof) return if(!retry(), err.at(decoder).EOFMagicWord());
				if (magic != BpConstants.WASM_MAGIC) err.rel(decoder, pt).InvalidMagicWord(magic);
				state = BpFsmState.VERSION;
			}
			VERSION => {
				var pt = decoder.pos;
				var version = decoder.read_u32();
				if (eof) return if(!retry(), err.at(decoder).EOFWasmVersion());
				if (version != BpConstants.WASM_VERSION) err.rel(decoder, pt).InvalidWasmVersion(version);
				state = BpFsmState.SECTION_START;
			}
			SECTION_START => {
				var b = readByte("section code", BpConstants.renderSectionName);
				if (eof) {
					if (!retry()) accept = true;
					return;
				}
				current_section = checkSectionCode(b);
				if (Trace.binparse) {
					Trace.OUT.put2("======== begin section code %d (%s) ========", current_section.code, current_section.name).ln();
				}
				state = BpFsmState.SECTION;
			}
			SECTION => {
				var pt = decoder.pos;
				section_size = readU32("section size", limits.max_module_size);
				if (eof) return if(!retry(), err_incomplete_section(decoder.addr_of(pt), 0));
				section_start = decoder.addr();
				state = BpFsmState.SECTION_WITH_SIZE;
			}
			SECTION_WITH_SIZE => {
				match (current_section) {
					Code => {  // code section handled specially, one function body at a time
						function_body_count = readU32("function body count", limits.max_num_functions);
						if (eof) return if(!retry(), err_incomplete_section(section_start, section_size));
						function_body_start = decoder.addr();
						current_function_body = 0;
						state = BpFsmState.BODY;
						callback.beginCodeSection(function_body_start, function_body_count);
					}
					_ => {
						decoder.sub_bytes(section_decoder, int.!(section_size));
						if (eof) return if(!retry(), err_incomplete_section(section_start, section_size));
						callback.decodeSection(current_section, section_size, section_decoder);
						state = BpFsmState.SECTION_START;
					}
				}
			}
			BODY => {
				if (current_function_body == function_body_count) { // already read N bodies
					var read = decoder.addr() - section_start;
					if (read < section_size) err.at(decoder).IncompleteSection(BpSection.Code.code, read, section_size);
					if (read > section_size) err.at(decoder).OverflowSection(BpSection.Code.code, read, section_size);
					state = BpFsmState.SECTION_START;
				} else {
					function_body_size = readU32("function body size", limits.max_func_size);
					if (eof) return if(!retry(), err_incomplete_function(current_function_body, 0));
					state = BpFsmState.BODY_WITH_SIZE;
				}
			}
			BODY_WITH_SIZE => {
				decoder.sub_bytes(function_decoder, int.!(function_body_size));
				var next_start = decoder.addr();
				if (eof) return if(!retry(), err_incomplete_function(current_function_body, function_body_size));
				callback.decodeFunctionBody(current_function_body, function_body_size, function_decoder);
				function_body_start = next_start;
				current_function_body++;
				state = BpFsmState.BODY;
			}
		}
	}
	def retry() -> bool {
		if (more) {
			decoder.at(current_pos);
			return true;
		}
		return false;
	}
	def checkSectionCode(b: byte) -> BpSection {
		if (!BpConstants.valid_section[b]) {
			err.at(decoder).InvalidSectionCode(b);
		}
		return BpConstants.enum_section[b];
	}
	def eof_is_section_overflow(d: DataReader, pos: int, size: int, msg: string) {
		var kind = current_section.code;
		var read = d.addr_of(pos) - section_start;
		var size = section_size;
		err.rel(d, pos).OverflowSection(kind, read, size);
	}
	def eof_is_function_overflow(d: DataReader, pos: int, size: int, msg: string) {
		var read = d.addr_of(pos) - function_body_start;
		var size = function_body_size;
		err.rel(d, pos).OverflowFunctionBody(read, size);
	}
	def err_incomplete_section(addr: u64, size: u32) {
		var kind = current_section;
		var read = decoder.addr() - addr;
		err.at(decoder).IncompleteSection(kind.code, read, size);
	}
	def err_incomplete_function(index: u32, size: u32) {
		var read = decoder.addr() - function_body_start;
		err.at(decoder).IncompleteFunctionBody(read, size);
	}
}
// The callbacks for sections, function bodies, and finishing a module.
class BpFsmCallback(module: Module) {
	def decodeSection(kind: BpSection, size: u32, d: DataReader);
	def beginCodeSection(addr: u64, count: u32) {}
	def decodeFunctionBody(index: u32, size: u32, d: DataReader);
}
// The states for the module parser finite state machine.
enum BpFsmState {
	MAGIC,
	VERSION,
	SECTION_START,
	SECTION,
	SECTION_WITH_SIZE,
	BODY,
	BODY_WITH_SIZE
}

// Represents the binary encoding of a value type, before resolution through a module or instance
// to a ValueType.
type ValueTypeCode(code: i8, index: i32) #unboxed {
	def toAbstractValueType(module: Module) -> ValueType {
		match (code) {
			BpTypeCode.I32.val => return ValueType.I32;
			BpTypeCode.I64.val => return ValueType.I64;
			BpTypeCode.F32.val => return ValueType.F32;
			BpTypeCode.F64.val => return ValueType.F64;
			BpTypeCode.V128.val => return ValueType.V128;
			BpTypeCode.FUNCREF.val => return ValueTypes.FUNCREF;
			BpTypeCode.EXTERNREF.val => return ValueTypes.EXTERNREF;
			BpTypeCode.ANYREF.val => return ValueTypes.ANYREF;
			BpTypeCode.EQREF.val => return ValueTypes.EQREF;
			BpTypeCode.REF.val => {
				if (index >= 0) return ValueTypes.Ref(false, module.heaptypes[index]);
				return ValueType.Ref(false, toHeapType());
			}
			BpTypeCode.REF_NULL.val => {
				if (index >= 0) return ValueTypes.Ref(true, module.heaptypes[index]);
				return ValueType.Ref(true, toHeapType());
			}
			BpTypeCode.STRUCTREF.val => return ValueTypes.STRUCTREF;
			BpTypeCode.I31REF.val => return ValueTypes.I31REF;
			BpTypeCode.NULLFUNCREF.val => return ValueTypes.NULLFUNCREF;
			BpTypeCode.NULLEXTERNREF.val => return ValueTypes.NULLEXTERNREF;
			BpTypeCode.ARRAYREF.val => return ValueTypes.ARRAYREF;
			BpTypeCode.EXNREF.val => return ValueTypes.EXNREF;
			BpTypeCode.NULLREF.val => return ValueTypes.NULLREF;
			_ => return fail();
		}
	}
	def toConcreteValueType(instance: Instance) -> ValueType {
		match (code) {
			BpTypeCode.I32.val => return ValueType.I32;
			BpTypeCode.I64.val => return ValueType.I64;
			BpTypeCode.F32.val => return ValueType.F32;
			BpTypeCode.F64.val => return ValueType.F64;
			BpTypeCode.V128.val => return ValueType.V128;
			BpTypeCode.FUNCREF.val => return ValueTypes.FUNCREF;
			BpTypeCode.EXTERNREF.val => return ValueTypes.EXTERNREF;
			BpTypeCode.ANYREF.val => return ValueTypes.ANYREF;
			BpTypeCode.EQREF.val => return ValueTypes.EQREF;
			BpTypeCode.REF.val => {
				if (index >= 0) return ValueTypes.Ref(false, instance.heaptypes[index]);
				return ValueType.Ref(false, toHeapType());
			}
			BpTypeCode.REF_NULL.val => {
				if (index >= 0) return ValueTypes.Ref(true, instance.heaptypes[index]);
				return ValueType.Ref(true, toHeapType());
			}
			BpTypeCode.STRUCTREF.val => return ValueTypes.STRUCTREF;
			BpTypeCode.I31REF.val => return ValueTypes.I31REF;
			BpTypeCode.NULLFUNCREF.val => return ValueTypes.NULLFUNCREF;
			BpTypeCode.NULLEXTERNREF.val => return ValueTypes.NULLEXTERNREF;
			BpTypeCode.ARRAYREF.val => return ValueTypes.ARRAYREF;
			BpTypeCode.EXNREF.val => return ValueTypes.EXNREF;
			BpTypeCode.NULLREF.val => return ValueTypes.NULLREF;
			_ => return fail();
		}
	}
	def toAbstractValueKind() -> ValueKind {
		match (code) {
			BpTypeCode.I32.val => return ValueKind.I32;
			BpTypeCode.I64.val => return ValueKind.I64;
			BpTypeCode.F32.val => return ValueKind.F32;
			BpTypeCode.F64.val => return ValueKind.F64;
			BpTypeCode.V128.val => return ValueKind.V128;
			BpTypeCode.FUNCREF.val,
			BpTypeCode.EXTERNREF.val,
			BpTypeCode.ANYREF.val,
			BpTypeCode.EQREF.val,
			BpTypeCode.REF.val,
			BpTypeCode.REF_NULL.val,
			BpTypeCode.STRUCTREF.val,
			BpTypeCode.I31REF.val,
			BpTypeCode.NULLFUNCREF.val,
			BpTypeCode.NULLEXTERNREF.val,
			BpTypeCode.ARRAYREF.val,
			BpTypeCode.EXNREF.val,
			BpTypeCode.NULLREF.val => return ValueKind.REF;
			_ => return fail();
		}
	}
	def toHeapType() -> HeapType {
		match (index) {
			BpTypeCode.FUNCREF.val => return ValueTypes.FUNCREF.heap;
			BpTypeCode.EXTERNREF.val => return ValueTypes.EXTERNREF.heap;
			BpTypeCode.ANYREF.val => return ValueTypes.ANYREF.heap;
			BpTypeCode.EQREF.val => return ValueTypes.EQREF.heap;
			BpTypeCode.STRUCTREF.val => return ValueTypes.STRUCTREF.heap;
			BpTypeCode.I31REF.val => return ValueTypes.I31REF.heap;
			BpTypeCode.NULLFUNCREF.val => return ValueTypes.NULLFUNCREF.heap;
			BpTypeCode.NULLEXTERNREF.val => return ValueTypes.NULLEXTERNREF.heap;
			BpTypeCode.ARRAYREF.val => return ValueTypes.ARRAYREF.heap;
			BpTypeCode.EXNREF.val => return ValueTypes.EXNREF.heap;
			BpTypeCode.NULLREF.val => return ValueTypes.NULLREF.heap;
			_ => return fail();
		}
	}
	def toConcreteValueKind(instance: Instance) -> ValueKind {
		return toAbstractValueKind();
	}
	def fail<T>() -> T {
		var d: T;
		System.error("InternalError", Strings.format1("invalid or illegal value type code %d", code));
		return d;
	}
}
type MemArg(flags: u32, memory_index: u31, offset: u64) #unboxed { }
type BrOnCastImm(flags: u8, depth: u31, ht1: int, ht2: int) #unboxed {
	def typeCode1() -> ValueTypeCode {
		return ValueTypeCode(if((flags & 1) != 0, BpTypeCode.REF_NULL.val, BpTypeCode.REF.val), ht1);
	}
	def typeCode2() -> ValueTypeCode {
		return ValueTypeCode(if((flags & 2) != 0, BpTypeCode.REF_NULL.val, BpTypeCode.REF.val), ht2);
	}
	def null1() -> bool { return (flags & 1) != 0; }
	def null2() -> bool { return (flags & 2) != 0; }
}
type MemLimits(size: SizeConstraint, shared: bool, log2_pageSize: u5) #unboxed { }
type TableLimits(size: SizeConstraint) #unboxed { }

type BlockTypeCode(code: int, index: int) #unboxed {
	def toAbstractBlockType(module: Module) -> (Array<ValueType>, Array<ValueType>) {
		match (code) {
			BpTypeCode.EmptyBlock.val => return (SigCache.arr_v, SigCache.arr_v);
			BpTypeCode.I32.val => return (SigCache.arr_v, SigCache.arr_i);
			BpTypeCode.I64.val => return (SigCache.arr_v, SigCache.arr_l);
			BpTypeCode.F32.val => return (SigCache.arr_v, SigCache.arr_f);
			BpTypeCode.F64.val => return (SigCache.arr_v, SigCache.arr_d);
			BpTypeCode.V128.val => return (SigCache.arr_v, SigCache.arr_s);
			BpTypeCode.FUNCREF.val => return (SigCache.arr_v, SigCache.arr_g);
			BpTypeCode.EXTERNREF.val => return (SigCache.arr_v, SigCache.arr_e);
			BpTypeCode.ANYREF.val => return (SigCache.arr_v, SigCache.arr_r);
			BpTypeCode.EQREF.val => {
				return (SigCache.arr_v, [ValueTypes.EQREF]);
			}
			BpTypeCode.REF.val => {
				var vt = ValueTypeCode(i8.view(code), index).toAbstractValueType(module);
				return (SigCache.arr_v, [vt]);
			}
			BpTypeCode.REF_NULL.val => {
				var vt = ValueTypeCode(i8.view(code), index).toAbstractValueType(module);
				return (SigCache.arr_v, [vt]);
			}
			BpTypeCode.I31REF.val => {
				return (SigCache.arr_v, SigCache.arr_h);
			}
			BpTypeCode.NULLFUNCREF.val => {
				return (SigCache.arr_v, [ValueTypes.NULLFUNCREF]);
			}
			BpTypeCode.NULLEXTERNREF.val => {
				return (SigCache.arr_v, [ValueTypes.NULLEXTERNREF]);
			}
			BpTypeCode.STRUCTREF.val => {
				return (SigCache.arr_v, [ValueTypes.STRUCTREF]);
			}
			BpTypeCode.ARRAYREF.val => {
				return (SigCache.arr_v, [ValueTypes.ARRAYREF]);
			}
			BpTypeCode.EXNREF.val => {
				return (SigCache.arr_v, SigCache.arr_x);
			}
			BpTypeCode.NULLREF.val => {
				return (SigCache.arr_v, [ValueTypes.NULLREF]);
			}
		}
		var sig = SigDecl.!(module.heaptypes[code]);
		return (sig.params, sig.results);
	}
}