Type.v3

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

// Value types for all Wasm values. Note that they may be recursive
// mutating the definition of heap types like {StructDecl} and {ArrayDecl}.
type ValueType {
	case BOTTOM;						// Bottom type
	case I32;						// 32-bit integer
	case I64;						// 64-bit integer
	case F32;						// 32-bit float
	case F64;						// 64-bit float
	case V128;						// 128-bit vector
	case Host(host: HostType);				// host-defined types
	case Ref(nullable: bool, heap: HeapType);

	def render(buf: StringBuilder) -> StringBuilder {
		return ValueTypes.render(this, null, buf);
	}
}
type HeapType {
	case ANY;
	case EXTERN;
	case EQ;
	case I31;
	case EXN;
	case NONE;
	case NOFUNC;
	case NOCONT;
	case NOEXTERN;
	case NOEXN;
	case Func(sig: SigDecl);
	case Struct(sdecl: StructDecl);
	case Array(array: ArrayDecl);
	case FwRef(index: int);
	case Cont(cont: ContDecl);

	def render(buf: StringBuilder) -> StringBuilder {
		match (this) {
			ANY => return buf.puts("any");
			EXTERN => return buf.puts("extern");
			EQ => return buf.puts("eq");
			I31 => return buf.puts("i31");
			EXN => return buf.puts("exn");
			NONE => return buf.puts("none");
			NOFUNC => return buf.puts("nofunc");
			NOEXN => return buf.puts("noexn");
			NOCONT => return buf.puts("nocont");
			NOEXTERN => return buf.puts("noextern");
			Func(sig) => return if(sig == null, buf.puts("func"), sig.render(buf));
			Struct(sdecl) => return if(sdecl == null, buf.puts("struct"), sdecl.render(buf));
			Array(array) => return if(array == null, buf.puts("array"), array.render(buf));
			Cont(cont) => return if(cont == null, buf.puts("cont"), cont.render(buf));
			FwRef(index) => return buf.put1("fwref #%d", index);
		}
	}
	def decl() -> HeapTypeDecl {
		match (this) {
			Func(sig) => return sig;
			Struct(sdecl) => return sdecl;
			Array(array) => return array;
			Cont(cont) => return cont;
			_ => return null;
		}
	}
}

// Utility functions associated with value types.
component ValueTypes {
	def ANYREF = ValueType.Ref(true, HeapType.ANY);
	def EXTERNREF = ValueType.Ref(true, HeapType.EXTERN);
	def EQREF = ValueType.Ref(true, HeapType.EQ);
	def I31REF = ValueType.Ref(true, HeapType.I31);
	def ARRAYREF = ValueType.Ref(true, HeapType.Array(null));
	def NONEREF = ValueType.Ref(true, HeapType.NONE);
	def FUNCREF = ValueType.Ref(true, HeapType.Func(null));
	def STRUCTREF = ValueType.Ref(true, HeapType.Struct(null));
	def EXNREF = ValueType.Ref(true, HeapType.EXN);
	def CONTREF = ValueType.Ref(true, HeapType.Cont(null));

	def NULLCONTREF = ValueType.Ref(true, HeapType.NOCONT);
	def NULLEXNREF = ValueType.Ref(true, HeapType.NOEXN);
	def NULLREF = ValueType.Ref(true, HeapType.NONE);
	def NULLFUNCREF = ValueType.Ref(true, HeapType.NOFUNC);
	def NULLEXTERNREF = ValueType.Ref(true, HeapType.NOEXTERN);


	def ANYREF_NONNULL = ValueType.Ref(false, HeapType.ANY);
	def EXTERNREF_NONNULL = ValueType.Ref(false, HeapType.EXTERN);
	def EQREF_NONNULL = ValueType.Ref(false, HeapType.EQ);
	def I31REF_NONNULL = ValueType.Ref(false, HeapType.I31);
	def FUNCREF_NONNULL = ValueType.Ref(false, HeapType.Func(null));
	def ARRAYREF_NONNULL = ValueType.Ref(false, HeapType.Array(null));
	def EXNREF_NONNULL = ValueType.Ref(false, HeapType.EXN);

	def NONE = Array<ValueType>.new(0);
	def NO_HEAPTYPES = Array<HeapType>.new(0);

	def ONE_STRUCTREF_TYPE: Array<ValueType> = [STRUCTREF];
	def ONE_ARRAYREF_TYPE: Array<ValueType> = [ARRAYREF];
	def ONE_CONTREF_TYPE: Array<ValueType> = [CONTREF];

	// Helper utility for a final signature type with no supertypes.
	def newSig = SigDecl.new(true, NO_HEAPTYPES, _, _);

	// Render a value type, careful not to recurse into any type in {seen}.
	def render(vt: ValueType, seen: List<Decl>, buf: StringBuilder) -> StringBuilder {
		var s: string;
		match (vt) {
			BOTTOM => s = "<bottom>";
			I32 => s = "i32";
			I64 => s = "i64";
			F32 => s = "f32";
			F64 => s = "f64";
			V128 => s = "v128";
			Host(host) => return host.render(buf);
			Ref(nullable, heap) => return renderHeapType(buf, seen, nullable, heap);
		}
		return buf.puts(s);
	}
	def renderHeapType(buf: StringBuilder, seen: List<Decl>, nullable: bool, heap: HeapType) -> StringBuilder {
		match (heap) {
			ANY => renderSimpleRef(buf, nullable, "any");
			EXTERN => renderSimpleRef(buf, nullable, "extern");
			EQ => renderSimpleRef(buf, nullable, "eq");
			I31 => renderSimpleRef(buf, nullable, "i31");
			EXN => renderSimpleRef(buf, nullable, "exn");
			NONE => buf.puts(if(nullable, "nullref", "(ref none)"));
			NOEXN => buf.puts(if(nullable, "nullexnref", "(ref noexn)"));
			NOCONT => buf.puts(if(nullable, "nullcontref", "(ref nocont)"));
			NOFUNC => buf.puts(if(nullable, "nullfuncref", "(ref nofunc)"));
			NOEXTERN => buf.puts(if(nullable, "nullexternref", "(ref noextern)"));
			Func(sig) => {
				if (sig == null) renderSimpleRef(buf, nullable, "func");
				else sig.render2(seen, buf.puts("(ref ")).puts(")");
			}
			Struct(sdecl) => {
				if (sdecl == null) renderSimpleRef(buf, nullable, "struct");
				else renderIndexedRef(buf, nullable, "struct", sdecl.heaptype_index);
			}
			Array(array) => {
				if (array == null) renderSimpleRef(buf, nullable, "struct");
				else renderIndexedRef(buf, nullable, "array", array.heaptype_index);
			}
			Cont(cont) => {
				if (cont == null) renderSimpleRef(buf, nullable, "cont");
				else renderIndexedRef(buf, nullable, "cont", cont.heaptype_index);
			}
			FwRef(index) => buf.put1("(fw-ref #%d)", index);
		}
		return buf;
	}
	def renderSimpleRef(buf: StringBuilder, nullable: bool, str: string) {
		if (nullable) buf.puts(str).puts("ref");
		else buf.puts("(ref ").puts(str).puts(")");
	}
	def renderIndexedRef(buf: StringBuilder, nullable: bool, str: string, index: int) {
		buf.puts("(ref ");
		if (nullable) buf.puts("null ");
		buf.put2("%s #%d)", str, index);
	}
	def isNumeric(t: ValueType) -> bool {
		match (t) {
			BOTTOM, I32, I64, F32, F64, V128 => return true;
			_ => return false;
		}
	}
	def isPrimitive(t: ValueType) -> bool {
		match (t) {
			BOTTOM, I32, I64, F32, F64, V128 => return true;
			_ => return false;
		}
	}
	def isRef(t: ValueType) -> bool {
		match (t) {
			BOTTOM, Ref, Host => return true;
			_ => return false;
		}
	}
	def isAssignable(from: ValueType, to: ValueType) -> bool {
		if (from == to) return true;
		if (from == ValueType.BOTTOM) return true;
		var eq = TypeRelation.compare(from, to);
		return eq == TypeEquiv.EQUAL || eq == TypeEquiv.SUB;
	}
	def isCompatibleParamType = ValueType.==; // invariant function types for now
	def isCompatibleReturnType = ValueType.==; // invariant function types for now
	def isAssignableHeap(from: HeapTypeDecl, to: HeapTypeDecl) -> bool {
		if (from.canonEq(to)) return true;
		var eq = TypeRelation.compareSuperTypeChain(from, to);
		return eq == TypeEquiv.EQUAL || eq == TypeEquiv.SUB;
	}
	def hasDefaultValue(t: ValueType) -> bool {
		match (t) {
			Ref(nullable, ht) => return nullable;
			_ => return true;
		}
	}
	def kind(t: ValueType) -> ValueKind {
		match (t) {
			I32 => return ValueKind.I32;
			I64 => return ValueKind.I64;
			F32 => return ValueKind.F32;
			F64 => return ValueKind.F64;
			V128 => return ValueKind.V128;
			Ref(nullable, ht) => return if(HeapType.Cont.?(ht), Continuations.valueKind, ValueKind.REF);
			_ => return ValueKind.REF;
		}
	}
	def Ref(nullable: bool, ht: HeapTypeDecl) -> ValueType.Ref {
		match (ht) {
			x: StructDecl => return ValueType.Ref(nullable, HeapType.Struct(x));
			x: ArrayDecl => return ValueType.Ref(nullable, HeapType.Array(x));
			x: SigDecl => return ValueType.Ref(nullable, HeapType.Func(x));
			x: ContDecl => return ValueType.Ref(nullable, HeapType.Cont(x));
			_ => return ValueTypes.ANYREF; // should not happen
		}
	}
	def RefStruct(nullable: bool, x: StructDecl) -> ValueType.Ref {
		return ValueType.Ref(nullable, HeapType.Struct(x));
	}
	def RefArray(nullable: bool, x: ArrayDecl) -> ValueType.Ref {
		return ValueType.Ref(nullable, HeapType.Array(x));
	}
	def RefFunc(nullable: bool, x: SigDecl) -> ValueType.Ref {
		return ValueType.Ref(nullable, HeapType.Func(x));
	}
}

// Implementation detail in comparing recursive types. Computes the relation between
// two types that may be mutually recursive, including subtyping between structs,
// arrays, and functions.
enum TypeEquiv {
	UNRELATED,
	SUPER,
	EQUAL,
	SUB
}
component TypeRelation {
	// Compare two types for equality or subtyping.
	def compare(from: ValueType, to: ValueType) -> TypeEquiv {
		if (from == to) return TypeEquiv.EQUAL;
		match (from) {
			Host(fhost) => match (to) {
				Host(thost) => {
					if (fhost.isAssignableTo(to)) return TypeEquiv.SUB;
					if (thost.isAssignableTo(from)) return TypeEquiv.SUPER;
					return TypeEquiv.UNRELATED;
				}
				_ => return if(fhost != null && fhost.isAssignableTo(to), TypeEquiv.SUB, TypeEquiv.UNRELATED);
			}
			Ref(fnullable, fheap) => match (to) {
				Ref(tnullable, theap) => {
					var eq = compareNullable(fnullable, tnullable);
					return combineEq(eq, compareHeapTypes(fheap, theap));
				}
				_ => ;
			}
			_ => ;
		}
		// Left-hand side primitive, but right-hand side could still be abstract or host
		match (to) {
			Host(thost) => if (thost.isAssignableTo(from)) return TypeEquiv.SUPER;
			_ => ;
		}
		return TypeEquiv.UNRELATED;
	}
	def compareHeapTypes(from: HeapType, to: HeapType) -> TypeEquiv {
		if (from == to) return TypeEquiv.EQUAL;
		match (from) {
			ANY => match (to) {
				EQ, I31, Array, Struct, NONE => return TypeEquiv.SUPER;
				_ => ;
			}
			EQ => match (to) {
				ANY => return TypeEquiv.SUB;
				I31, Array, Struct, NONE => return TypeEquiv.SUPER;
				_ => ;
			}
			I31 => match (to) {
				EQ, ANY => return TypeEquiv.SUB;
				NONE => return TypeEquiv.SUPER;
				_ => ;
			}
			Struct(fstruct) => match (to) {
				EQ, ANY => return TypeEquiv.SUB;
				Struct(tstruct) => return compareSuperTypeChain(fstruct, tstruct);
				NONE => return TypeEquiv.SUPER;
				_ => ;
			}
			Array(farray) => match (to) {
				EQ, ANY => return TypeEquiv.SUB;
				Array(tarray) => return compareSuperTypeChain(farray, tarray);
				NONE => return TypeEquiv.SUPER;
				_ => ;
			}
			NONE => match (to) {
				EQ, ANY, I31, Array, Struct => return TypeEquiv.SUB;
				_ => ;
			}
			EXTERN => match (to) {
				NOEXTERN => return TypeEquiv.SUPER;
				_ => ;
			}
			NOEXTERN => match (to) {
				EXTERN => return TypeEquiv.SUB;
				_ => ;
			}
			EXN => match (to) {
				NOEXN => return TypeEquiv.SUPER;
				_ => ;
			}
			NOEXN => match (to) {
				EXN => return TypeEquiv.SUB;
				_ => ;
			}
			Func(fsig) => match (to) {
				Func(tsig) => return compareSuperTypeChain(fsig, tsig);
				NOFUNC => return TypeEquiv.SUPER;
				_ => ;
			}
			NOFUNC => match (to) {
				Func => return TypeEquiv.SUB;
				_ => ;
			}
			Cont(fcont) => match (to) {
				Cont(tcont) => {
					return compareSuperTypeChain(fcont, tcont);
				}
				NOCONT => return TypeEquiv.SUPER;
				_ => ;
			}
			NOCONT => match (to) {
				Cont => return TypeEquiv.SUB;
				_ => ;
			}
			_ => ;
		}
		return TypeEquiv.UNRELATED;
	}
	def compareSuperTypeChain(from: HeapTypeDecl, to: HeapTypeDecl) -> TypeEquiv {
		if (from == to) return TypeEquiv.EQUAL;
		if (from == null) return TypeEquiv.SUPER;
		if (to == null) return TypeEquiv.SUB;
		for (f = from; f != null; f = f.getFirstSuperType()) {
			if (f.canonEq(to)) return TypeEquiv.SUB;
		}
		for (t = to; t != null; t = t.getFirstSuperType()) {
			if (from.canonEq(t)) return TypeEquiv.SUPER;
		}
		return TypeEquiv.UNRELATED;
	}
	def compareNullable(f: bool, t: bool) -> TypeEquiv {
		return if(f,
			if(t, TypeEquiv.EQUAL, TypeEquiv.SUPER),
			if(t, TypeEquiv.SUB, TypeEquiv.EQUAL));
	}
	def combineEq(a: TypeEquiv, b: TypeEquiv) -> TypeEquiv {
		if (a == TypeEquiv.UNRELATED) return a;
		match (b) {
			UNRELATED => return TypeEquiv.UNRELATED;
			SUPER => return if(a == TypeEquiv.SUB, TypeEquiv.UNRELATED, TypeEquiv.SUPER);
			EQUAL => return a;
			SUB => return if(a == TypeEquiv.SUPER, TypeEquiv.UNRELATED, TypeEquiv.SUB);
		}
	}
}

// Heap type declarations.
class HeapTypeDecl(final: bool, supertypes: Array<HeapType>) extends Decl {
	var hash = 0;
	var heaptype_index = -1;
	var canon_id = -1;
	var recgrp_index = 0;

	def render(buf: StringBuilder) -> StringBuilder;
	def getFirstSuperType() -> HeapTypeDecl {
		if (supertypes == null || supertypes.length < 1) return null;
		match (supertypes[0]) {
			Struct(decl) => return decl;
			Array(decl) => return decl;
			Func(decl) => return decl;
			_ => return null;
		}
	}
	def putUid(buf: StringBuilder) -> StringBuilder {
		if (Trace.uid) buf.put1("@%d", canon_id);
		return buf;
	}
	def canonEq(that: HeapTypeDecl) -> bool { // TODO: remove the need for this method altogether.
		return this == that || (this.canon_id != -1 && this.canon_id == that.canon_id);
	}
}

// Packedness and mutability for fields and array elements. (ext:gc)
enum Packedness { UNPACKED, PACKED_I8, PACKED_I16 }
type StorageType(valtype: ValueType, pack: Packedness, mutable: bool) { }

// Struct type declaration. (ext:gc)
class StructDecl extends HeapTypeDecl {
	def field_types: Array<StorageType>;
	def defaultable = allHaveDefaultValues(field_types);

	new(final: bool, supertypes: Array<HeapType>, field_types) super(final, supertypes) {}

	def render(buf: StringBuilder) -> StringBuilder {
		return putUid(buf.put1("struct #%d", heaptype_index));
	}
}

// Array type declaration. (ext:gc)
class ArrayDecl extends HeapTypeDecl {
	def elem_types: Array<StorageType>;
	def defaultable = allHaveDefaultValues(elem_types);

	new(final: bool, supertypes: Array<HeapType>, elem_types) super(final, supertypes) {}

	def render(buf: StringBuilder) -> StringBuilder {
		return putUid(buf.put1("array #%d", heaptype_index));
	}
}

// Continuation type declaration. (ext:stack-switching)
class ContDecl extends HeapTypeDecl {
	var sig_ref: HeapType;
	var sig: SigDecl;

	new(final: bool, supertypes: Array<HeapType>, sig_ref) super(final, supertypes) {}

	def render(buf: StringBuilder) -> StringBuilder {
		return putUid(buf.put2("cont #%d (%q)", heaptype_index, if(sig != null, sig.render, sig_ref.render)));
	}
}

// Signature of a function.
class SigDecl extends HeapTypeDecl {
	def params: Array<ValueType>;
	def results: Array<ValueType>;

	new(final: bool, supertypes: Array<HeapType>, params, results) super(final, supertypes) {}

	def isAssignableSig(that: SigDecl) -> bool {
		if (that == null) return false;
		return Arrays.allTrue(this.params, that.params, ValueTypes.isCompatibleParamType) &&
			Arrays.allTrue(this.results, that.results, ValueTypes.isCompatibleReturnType);
	}
	def render(buf: StringBuilder) -> StringBuilder {
		return render2(null, buf);
	}
	def render2(seen: List<Decl>, buf: StringBuilder) -> StringBuilder {
		for (l = seen; l != null; l = l.tail) {
			if (l.head == this) return buf.put1("#%d", heaptype_index);
		}
		seen = List.new(this, seen);
		buf.puts("[");
		for (i < params.length) {
			if (i > 0) buf.puts(" ");
			ValueTypes.render(params[i], seen, buf);
		}
		buf.puts("] -> [");
		for (i < results.length) {
			if (i > 0) buf.puts(" ");
			ValueTypes.render(results[i], seen, buf);
		}
		buf.puts("]");
		return putUid(buf);
	}
	def dup() -> SigDecl {
		var ns = SigDecl.new(final, supertypes, params, results);
		ns.canon_id = this.canon_id;
		return ns;
	}
}

def allHaveDefaultValues(at: Array<StorageType>) -> bool {
	for (t in at) if (!ValueTypes.hasDefaultValue(t.valtype)) return false;
	return true;
}

component HeapTypeDecls {
	def checkSupertypes(addr: u64, t: HeapTypeDecl, error: ErrorGen) {
		if (t.supertypes == null || t.supertypes.length < 1) return; // nothing to do
		match (t) {
			x: StructDecl => {
				for (s in t.supertypes) {
					if (!HeapType.Struct.?(s)) return error.abs(addr).IllegalSupertype(x, s);
					var y = HeapType.Struct.!(s).sdecl;
					if (y.final) return error.abs(addr).FinalSupertype(x, s);
					if (x.field_types.length < y.field_types.length) return error.abs(addr).IllegalSupertype(x, s);
					for (i < y.field_types.length) {
						if (!checkStorageType(x.field_types[i], y.field_types[i])) return error.abs(addr).IllegalSupertype(x, s);
					}
				}
			}
			x: ArrayDecl => {
				for (s in t.supertypes) {
					if (!HeapType.Array.?(s)) return error.abs(addr).IllegalSupertype(x, s);
					var y = HeapType.Array.!(s).array;
					if (y.final) return error.abs(addr).FinalSupertype(x, s);
					if (!Arrays.allTrue(x.elem_types, y.elem_types, checkStorageType)) return error.abs(addr).IllegalSupertype(x, s);
				}
			}
			x: SigDecl => {
				for (s in t.supertypes) {
					if (!HeapType.Func.?(s)) return error.abs(addr).IllegalSupertype(x, s);
					var y = HeapType.Func.!(s).sig;
					if (y.final) return error.abs(addr).FinalSupertype(x, s);
					if (!Arrays.allTrue(x.results, y.results, ValueTypes.isAssignable)) return error.abs(addr).IllegalSupertype(x, s);
					if (!Arrays.allTrue(y.params, x.params, ValueTypes.isAssignable)) return error.abs(addr).IllegalSupertype(x, s);
				}
			}
			x: ContDecl => {
				for (s in t.supertypes) {
					if (!HeapType.Cont.?(s)) return error.abs(addr).IllegalSupertype(x, s);
					var y = HeapType.Cont.!(s).cont.sig;
					if (y.final) return error.abs(addr).FinalSupertype(x, s);
					if (!Arrays.allTrue(x.sig.results, y.results, ValueTypes.isAssignable)) return error.abs(addr).IllegalSupertype(x, s);
					if (!Arrays.allTrue(y.params, x.sig.params, ValueTypes.isAssignable)) return error.abs(addr).IllegalSupertype(x, s);
				}
			}
		}
	}
	def checkStorageType(sub: StorageType, sup: StorageType) -> bool {
		if (sub.pack != sup.pack) return false;
		if (sup.mutable) return sub.mutable && sub.valtype == sup.valtype;
		return !sub.mutable && ValueTypes.isAssignable(sub.valtype, sup.valtype);
	}
	def renderStorageType(t: StorageType, buf: StringBuilder) -> StringBuilder {
		match (t.pack) {
			PACKED_I8 => buf.puts("i8");
			PACKED_I16 => buf.puts("i16");
			_ => t.valtype.render(buf);
		}
		return buf;
	}
}