/** * Equality and hashing lowering, split out of lowering.zena: the * synthesized case-class operator== / hashCode bodies, the erased * (eqref-tiered) equality used by `==` on erased operands, and the * equals/hash intrinsics from zena:map — plus the call/fast-path * helpers only they use. Each function takes the shared LoweringContext; * bodies are streaming's shapes exactly (see the per-function docs). */ import { CallExpression } from '../../ast.zena'; import { BooleanType, ClassType, F32Type, F64Type, FieldInfo, I32Type, I64Type, NullType, HoleType, RecordType, TupleType, Type, UnionType, baseType, instantiateClassType, } from '../../types.zena'; import { ValType, ValTypeAnyRef, ValTypeEqRef, ValTypeF32, ValTypeF64, ValTypeI32, ValTypeI64, ValTypeV128, ValTypeRef, ValTypeRefNull, ValTypeStructRef, isNullableAnyRef, isRefValType, refTargetOf, sameHeapType, } from '../wasm.zena'; import { targetUsesJsStrings } from '../../targets.zena'; import { ClassCodegenInfo, RecordDispatchInfo, WasmField, WasmFunction, WasmModule, WasmSignature, WasmStruct, isValSubtype, recordShapeFieldName, } from '../wasm-module.zena'; import { TemplateAbandon } from './template.zena'; import { getClassKey, getClassMethodKey, getMemberRootClass, presentWordName, } from '../codegen-utils.zena'; import { InlineLayout, eraseTypeParameters, getClassTypeParameters, recordWasmFields, sortedOptionalNames, substituteTypeParamsInCodegen, } from '../type-mapping.zena'; import { ValueEqField, isExistentialRecord, valueEqFields, valueEqKey, valueEqOperand, valueHashKey, } from '../value-equality.zena'; import { IrBody, IrOp, IrRefField, IrRefFunc } from './ir.zena'; import { existentialHash, existentialUnderlying } from './existential.zena'; import { lowerExpr } from './lowering.zena'; import { LoweringContext, ZirUnsupported, noValues, oneValue, twoValues, } from './lowering-context.zena'; /** Bail with the lowering-side message shape (reason @function). */ function bail(cx: LoweringContext, reason: String): never { throw new ZirUnsupported(`${reason} @${cx.func.name ?? '?'}`); } function isNullableRef(vt: ValType) { return isNullableAnyRef(vt); } /** True when the struct IS the String struct (covers generic * specializations with String arguments). Identity-first via * sameHeapType: an index-only comparison matched EVERY struct * before layout() assigned indices. */ function isStringStruct(cx: LoweringContext, st: WasmStruct): boolean { let strClass = cx.wasm.stringClass; if (strClass == null) { return false; } if (let (true, info) = cx.wasm.classInfos.get(getClassKey(strClass))) { return sameHeapType(info.structType, st); } return false; } /** String's operator== function, or a bail. (Inline throw rather than a * bail() call: written when the checker did not treat a never-returning * call as terminating. It does now, so this could be simplified.) */ function stringEqFunc(cx: LoweringContext): WasmFunction { let strClass = cx.wasm.stringClass; if (strClass != null) { let key = getClassMethodKey(getClassKey(strClass), "=="); if (let (true, m) = cx.wasm.classMethodMap.get(key)) { return m; } } throw new ZirUnsupported('string eq method'); } /** Direct call to a devirtualized single-result unary method * (hashCode, the string-hash helper), coercing the receiver. */ function callUnary(cx: LoweringContext, fn: WasmFunction, v: i32) { if (fn.signature.params.length != 1 || fn.signature.returns.length != 1) { bail(cx, 'unary method shape'); } let recv = cx.coerceTo(v, fn.signature.params[0]); let funcRef = cx.b.addRef(new IrRefFunc(fn)); return cx.b.callFunc(funcRef, oneValue(recv), fn.signature.returns[0]); } /** Direct call to a two-operand boolean method (String.== or a * devirtualized operator==), coercing operands to its params. */ function callEqMethod(cx: LoweringContext, method: WasmFunction, a: i32, b2: i32) { let sig = method.signature; if (sig.params.length != 2 || sig.returns.length != 1) { bail(cx, 'eq method shape'); } let ca = cx.coerceTo(a, sig.params[0]); let cb = cx.coerceTo(b2, sig.params[1]); let funcRef = cx.b.addRef(new IrRefFunc(method)); return cx.b.callFunc(funcRef, twoValues(ca, cb), sig.returns[0]); } /** i64 -> i32 hash fold (lo ^ hi), shared by the hash intrinsic * and the case-class hashCode synthesis (mirrors streaming). */ function hashI64Fold(cx: LoweringContext, v: i32) { let i32vt = new ValTypeI32() as ValType; let lo = cx.b.emit(IrOp.i32_wrap_i64, i32vt, v, -1); let thirtyTwo = cx.b.constI64(32 as i64, new ValTypeI64() as ValType); let shifted = cx.b.binary(IrOp.i64_shr_u, new ValTypeI64() as ValType, v, thirtyTwo); let hi = cx.b.emit(IrOp.i32_wrap_i64, i32vt, shifted, -1); return cx.b.binary(IrOp.i32_xor, i32vt, lo, hi); } /** Call the runtime string-hash helper on a String value. */ function callStringHash(cx: LoweringContext, v: i32) { let hashFn = cx.wasm.stringHashFunc; if (hashFn == null) { bail(cx, 'string hash helper'); } return callUnary(cx, hashFn, v); } /** * The reference-equality fast path around a content-equality call, * as a value-producing diamond (blocks + a merge parameter, since * ZIR has no select over calls): * * same = ref.eq a b * / \\ * same: true nullSafe && either null? * | yes: 0 no: call ==(a, b) * \\ / * merge(result: i32) * * `same` covers both the identical-reference case and, when * nullSafe, the both-null case (ref.eq of two nulls is true), so * the null arm only sees exactly-one-null — never equal. Callers * with non-nullable operands pass nullSafe=false and skip the null * checks entirely. */ function refEqFastPathCall(cx: LoweringContext, method: WasmFunction, a: i32, b2: i32, nullSafe: boolean) { let i32vt = new ValTypeI32() as ValType; let same = cx.b.emit(IrOp.ref_eq, i32vt, a, b2); let sameB = cx.b.newBlock(); let restB = cx.b.newBlock(); cx.b.brIf(same, sameB, noValues(), restB, noValues()); let mergeB = cx.b.newBlock(); let result = cx.b.blockParam(mergeB, i32vt); cx.b.switchTo(sameB); let one = cx.b.constI32(1, i32vt); cx.b.br(mergeB, oneValue(one)); cx.b.switchTo(restB); if (nullSafe) { let aNull = cx.b.emit(IrOp.ref_is_null, i32vt, a, -1); let bNull = cx.b.emit(IrOp.ref_is_null, i32vt, b2, -1); let anyNull = cx.b.binary(IrOp.i32_or, i32vt, aNull, bNull); let nullB = cx.b.newBlock(); let callB = cx.b.newBlock(); cx.b.brIf(anyNull, nullB, noValues(), callB, noValues()); cx.b.switchTo(nullB); let zero = cx.b.constI32(0, i32vt); cx.b.br(mergeB, oneValue(zero)); cx.b.switchTo(callB); } let called = callEqMethod(cx, method, a, b2); cx.b.br(mergeB, oneValue(called)); cx.b.switchTo(mergeB); return result; } /** The codegen info of a class an equality test names. */ function equalityClassInfo(cx: LoweringContext, ct: ClassType) { var infoOpt: ClassCodegenInfo | null = null; if (let (true, info) = cx.wasm.classInfos.get(getClassKey(ct))) { infoOpt = info; } if (infoOpt == null) { bail(cx, 'equality class not discovered'); } return infoOpt; } function refTestOf(cx: LoweringContext, v: i32, st: WasmStruct) { return cx.b.emit(IrOp.ref_test, new ValTypeI32(), v, cx.b.internType(new ValTypeRef(st) as ValType)); } function refCastTo(cx: LoweringContext, v: i32, st: WasmStruct) { let vt = new ValTypeRef(st) as ValType; if (isValSubtype(cx.valueTypeOf(v), vt)) { return v; } return cx.b.emit(IrOp.ref_cast, vt, v, cx.b.internType(vt)); } /** * Whether a class can have instances: its struct was laid out. A class no * reached code instantiates is left out of the type section, and so is * every class below it. */ function laidOut(info: ClassCodegenInfo) { return info.structType.index >= 0; } /** True when `v` is exactly of the class `info` describes, not a subclass. */ function exactlyOf(cx: LoweringContext, v: i32, info: ClassCodegenInfo) { let i32vt = new ValTypeI32() as ValType; var acc = refTestOf(cx, v, info.structType); for (let sub in info.subclasses) { if (!laidOut(sub)) { continue; } let isSub = refTestOf(cx, v, sub.structType); let notSub = cx.b.emit(IrOp.i32_eqz, i32vt, isSub, -1); acc = cx.b.binary(IrOp.i32_and, i32vt, acc, notSub); } return acc; } /** `info`'s subtree, each class after all of its subclasses. */ function subtreePostOrder(info: ClassCodegenInfo, out: GrowableArray): void { for (let sub in info.subclasses) { if (laidOut(sub)) { subtreePostOrder(sub, out); } } out.push(info); } /** * Whether `other` is of exactly `self`'s class, found by testing `self` * against the declaring class's subtree, subclasses first, so the first * match is its own class. */ function subtreeExactTest(cx: LoweringContext, self: i32, other: i32, info: ClassCodegenInfo) { let i32vt = new ValTypeI32() as ValType; let order = new Array(); subtreePostOrder(info, order); let mergeB = cx.b.newBlock(); let result = cx.b.blockParam(mergeB, i32vt); for (var k = 0; k < order.length - 1; k += 1) { let x = order[k]; let isX = refTestOf(cx, self, x.structType); let thenB = cx.b.newBlock(); let nextB = cx.b.newBlock(); cx.b.brIf(isX, thenB, noValues(), nextB, noValues()); cx.b.switchTo(thenB); cx.b.br(mergeB, oneValue(exactlyOf(cx, other, x))); cx.b.switchTo(nextB); } cx.b.br(mergeB, oneValue(exactlyOf(cx, other, info))); cx.b.switchTo(mergeB); return result; } /** * The test at the top of a declared `operator ==`: `other` is of exactly * the receiver's runtime class (equality.md, "Overrides compare the same * class"). An instance-of test would make `point == point3` true while * `point3 == point` is false. * * A declaring class with no subclasses needs only a test of `other`. * Otherwise the same object passes at once, and a different one is tested * against the declaring class's subtree. Comparing the two objects' vtables * would be shorter, but reading the field keeps every class's vtable global * alive in a hierarchy that otherwise dispatches nothing. */ export function exactClassTest(cx: LoweringContext, self: i32, other: i32, declaring: ClassType): i32 { let info = equalityClassInfo(cx, declaring); if (!info.subclasses.some((sub) => laidOut(sub))) { return refTestOf(cx, other, info.structType); } let i32vt = new ValTypeI32() as ValType; let same = cx.b.emit(IrOp.ref_eq, i32vt, self, other); let sameB = cx.b.newBlock(); let otherB = cx.b.newBlock(); let mergeB = cx.b.newBlock(); let result = cx.b.blockParam(mergeB, i32vt); cx.b.brIf(same, sameB, noValues(), otherB, noValues()); cx.b.switchTo(sameB); cx.b.br(mergeB, oneValue(cx.b.constI32(1, i32vt))); cx.b.switchTo(otherB); cx.b.br(mergeB, oneValue(subtreeExactTest(cx, self, other, info))); cx.b.switchTo(mergeB); return result; } /** * The classes below `info` that introduce `operator ==`: each declares or * derives one and its superclass has none. A class below one of them is * covered by its dispatch, so the walk stops there. One whose operator was * never reached has no instances (reachability reaches the operator of * every instantiated class below a compared base), so it needs no test. */ function equalityIntroducers(cx: LoweringContext, info: ClassCodegenInfo, out: GrowableArray): void { equalityIntroducersIn(cx.wasm, info, out); } function equalityIntroducersIn(wasm: WasmModule, info: ClassCodegenInfo, out: GrowableArray): void { for (let sub in info.subclasses) { if (!laidOut(sub)) { continue; } let sct = sub.structType.classType; if (sct != null && sct.members.has("==")) { if (wasm.classMethodMap.has(getClassMethodKey(getClassKey(sct), "=="))) { out.push(sub); } } else { equalityIntroducersIn(wasm, sub, out); } } } /** * Whether `==` on class `ct` is identity: neither `ct` nor any class * below it in the module declares or derives an operator. Template * lowering (template.zena) records this for the classes a template * compares, and asks it again of each specialization. */ export function identityEqualityIn(wasm: WasmModule, ct: ClassType): boolean { if (ct.members.has("==")) { return false; } if (let (true, info) = wasm.classInfos.get(getClassKey(ct))) { let introducers = new GrowableArray(); equalityIntroducersIn(wasm, info, introducers); return introducers.length == 0; } return false; } /** * How many introducing classes a comparison tests inline before it calls * the shared erased dispatch instead. */ let inlineIntroducerLimit = 4; /** `a == b` with both operands non-null references of class `ct` or below. */ function classEqNonNull(cx: LoweringContext, a: i32, b2: i32, ct: ClassType): i32 { let i32vt = new ValTypeI32() as ValType; if (ct.members.has("==")) { // The operator's parameter is the class that roots its slot; an // operand outside it is a different class, so never equal. let root = getMemberRootClass(ct, "=="); let rootSt = equalityClassInfo(cx, root).structType; if (isValSubtype(cx.valueTypeOf(b2), new ValTypeRef(rootSt) as ValType)) { return cx.operatorMemberOn("==", a, b2, ct); } let inRoot = refTestOf(cx, b2, rootSt); let callB = cx.b.newBlock(); let falseB = cx.b.newBlock(); let mergeB = cx.b.newBlock(); let result = cx.b.blockParam(mergeB, i32vt); cx.b.brIf(inRoot, callB, noValues(), falseB, noValues()); cx.b.switchTo(falseB); cx.b.br(mergeB, oneValue(cx.b.constI32(0, i32vt))); cx.b.switchTo(callB); cx.b.br(mergeB, oneValue(cx.operatorMemberOn("==", a, refCastTo(cx, b2, rootSt), ct))); cx.b.switchTo(mergeB); return result; } // No operator on `ct`: its root's equality is identity, overridden by // the classes below it that introduce one. let introducers = new Array(); equalityIntroducers(cx, equalityClassInfo(cx, ct), introducers); if (introducers.length == 0) { return cx.b.binary(IrOp.ref_eq, i32vt, a, b2); } // A long list is the shared erased dispatch's: `a` is a `ct`, so only // the classes below `ct` can match there too, and one call replaces a // copy of the tests at every comparison. A sealed base whose cases each // derive `==` is the usual way to get here, and its fields compared in // every case's derived operator multiplied the copies. let shared = cx.wasm.erasedEqFunc; if (shared != null && introducers.length > inlineIntroducerLimit) { return cx.b.callFunc(cx.b.addRef(new IrRefFunc(shared)), twoValues(a, b2), i32vt); } let mergeB = cx.b.newBlock(); let result = cx.b.blockParam(mergeB, i32vt); for (let x in introducers) { let xct = x.structType.classType as ClassType; let isX = refTestOf(cx, a, x.structType); let thenB = cx.b.newBlock(); let nextB = cx.b.newBlock(); cx.b.brIf(isX, thenB, noValues(), nextB, noValues()); cx.b.switchTo(thenB); let otherIsX = refTestOf(cx, b2, x.structType); let callB = cx.b.newBlock(); let falseB = cx.b.newBlock(); cx.b.brIf(otherIsX, callB, noValues(), falseB, noValues()); cx.b.switchTo(falseB); cx.b.br(mergeB, oneValue(cx.b.constI32(0, i32vt))); cx.b.switchTo(callB); let eqX = classEqNonNull(cx, refCastTo(cx, a, x.structType), refCastTo(cx, b2, x.structType), xct); cx.b.br(mergeB, oneValue(eqX)); cx.b.switchTo(nextB); } cx.b.br(mergeB, oneValue(cx.b.binary(IrOp.ref_eq, i32vt, a, b2))); cx.b.switchTo(mergeB); return result; } /** * `a == b` on operands of class type `ct`, either of which may be null * (equality.md, "Virtual equality with an identity default"). Two nulls are * equal and a null never equals an object; otherwise the runtime class's * `operator ==` answers, which is identity unless some class declares or * derives one. */ export function lowerClassEquality(cx: LoweringContext, a: i32, b2: i32, ct: ClassType): i32 { let i32vt = new ValTypeI32() as ValType; let recorder = cx.b.recorder; if (recorder != null) { // Template mode copies only identity comparisons: an operator, and // the classes below `ct` that introduce one, differ between the // classes a type parameter stands for. if (!identityEqualityIn(cx.wasm, ct)) { throw new TemplateAbandon('class equality'); } recorder.noteIdentityEquality(ct); } if (!ct.members.has("==")) { let introducers = new Array(); equalityIntroducers(cx, equalityClassInfo(cx, ct), introducers); if (introducers.length == 0) { // Identity throughout, and ref.eq already treats null as itself. return cx.b.binary(IrOp.ref_eq, i32vt, a, b2); } } let aNullable = isNullableRef(cx.valueTypeOf(a)); let bNullable = isNullableRef(cx.valueTypeOf(b2)); if (!aNullable && !bNullable) { return classEqNonNull(cx, a, b2, ct); } let aNull = if (aNullable) cx.b.emit(IrOp.ref_is_null, i32vt, a, -1) else cx.b.constI32(0, i32vt); let bNull = if (bNullable) cx.b.emit(IrOp.ref_is_null, i32vt, b2, -1) else cx.b.constI32(0, i32vt); let anyNull = cx.b.binary(IrOp.i32_or, i32vt, aNull, bNull); let nullB = cx.b.newBlock(); let valueB = cx.b.newBlock(); let mergeB = cx.b.newBlock(); let result = cx.b.blockParam(mergeB, i32vt); cx.b.brIf(anyNull, nullB, noValues(), valueB, noValues()); cx.b.switchTo(nullB); cx.b.br(mergeB, oneValue(cx.b.binary(IrOp.i32_and, i32vt, aNull, bNull))); cx.b.switchTo(valueB); let aV = if (aNullable) cx.coerceTo(a, new ValTypeRef(refTargetOf(cx.valueTypeOf(a)) as WasmStruct) as ValType) else a; let bV = if (bNullable) cx.coerceTo(b2, new ValTypeRef(refTargetOf(cx.valueTypeOf(b2)) as WasmStruct) as ValType) else b2; cx.b.br(mergeB, oneValue(classEqNonNull(cx, aV, bV, ct))); cx.b.switchTo(mergeB); return result; } /** * The type of the synthesized function's class's field `name`, as the * instantiation sees it, when it is a record or tuple; else null. The * derived `==` and `hashCode` treat such a field by value, like any `==` * on it, which its wasm type alone (a reference) cannot tell. */ function caseValueFieldType(cx: LoweringContext, name: String): Type | null { let owner = cx.func.classType; if (owner == null) { return null; } let ct = owner as ClassType; if (let (true, member) = ct.members.get(name)) { if (member is FieldInfo && !member.isStatic) { let t = substituteTypeParamsInCodegen(cx.wasm, getClassTypeParameters(ct), ct.typeArguments, member.type); if (valueEqOperand(t) != null) { return t; } } } return null; } /** Field-wise equality for the synthesized case-class ==. */ function synthFieldEq(cx: LoweringContext, f: WasmField, a: i32, b2: i32) { let i32vt = new ValTypeI32() as ValType; let ft = f.type; if (ft is ValTypeI32) { return cx.b.binary(IrOp.i32_eq, i32vt, a, b2); } if (ft is ValTypeI64) { return cx.b.binary(IrOp.i64_eq, i32vt, a, b2); } if (ft is ValTypeF32) { return cx.b.binary(IrOp.f32_eq, i32vt, a, b2); } if (ft is ValTypeF64) { return cx.b.binary(IrOp.f64_eq, i32vt, a, b2); } let fieldStruct = refTargetOf(ft); if (fieldStruct is WasmStruct) { let eqFunc: WasmFunction | null = if (isStringStruct(cx, fieldStruct)) { stringEqFunc(cx) } else { null }; if (eqFunc == null && fieldStruct.classType != null) { let fct = fieldStruct.classType as ClassType; if (!fct.isExtension) { // The field's runtime class answers, as for `==` anywhere. return lowerClassEquality(cx, a, b2, fct); } } if (eqFunc != null) { // Null-safe reference fast path around the content equality // (see refEqFastPathCall): struct fields are nullable refs. return refEqFastPathCall(cx, eqFunc, a, b2, true); } } // Fallback: reference identity (also covers arrays/closures). return cx.b.emit(IrOp.ref_eq, i32vt, a, b2); } /** Field-wise hash for the synthesized case-class hashCode. */ function synthFieldHash(cx: LoweringContext, st: WasmStruct, f: WasmField, selfC: i32) { let i32vt = new ValTypeI32() as ValType; let ft = f.type; // A record or tuple field hashes its fields, consistent with `==`. let valueType = caseValueFieldType(cx, f.name as String); if (valueType != null) { let fieldRef = cx.b.addRef(new IrRefField(st, f.name as String)); return lowerValueHash(cx, valueType as Type, cx.b.emit(IrOp.struct_get, ft, selfC, fieldRef)); } if (ft is ValTypeF32) { let fieldRef = cx.b.addRef(new IrRefField(st, f.name as String)); let v = cx.b.emit(IrOp.struct_get, ft, selfC, fieldRef); let zero32 = cx.b.constF32(0.0, new ValTypeF32()); let norm32 = cx.b.binary(IrOp.f32_add, new ValTypeF32() as ValType, v, zero32); return cx.b.emit(IrOp.i32_reinterpret_f32, new ValTypeI32(), norm32, -1); } if (ft is ValTypeF64) { let fieldRef = cx.b.addRef(new IrRefField(st, f.name as String)); let v = cx.b.emit(IrOp.struct_get, ft, selfC, fieldRef); let zero64 = cx.b.constF64(0.0, new ValTypeF64()); let norm64 = cx.b.binary(IrOp.f64_add, new ValTypeF64() as ValType, v, zero64); let bits = cx.b.emit(IrOp.i64_reinterpret_f64, new ValTypeI64(), norm64, -1); return hashI64Fold(cx, bits); } if (ft is ValTypeI32) { let fieldRef = cx.b.addRef(new IrRefField(st, f.name as String)); return cx.b.emit(IrOp.struct_get, ft, selfC, fieldRef); } if (ft is ValTypeI64) { let fieldRef = cx.b.addRef(new IrRefField(st, f.name as String)); let v = cx.b.emit(IrOp.struct_get, ft, selfC, fieldRef); return hashI64Fold(cx, v); } // Fresh binding: the narrowing state after the bail/return chain // above over-narrows `ft`. let ftRef = f.type; let fieldStruct = refTargetOf(ftRef); if (fieldStruct is WasmStruct) { var hashFunc: WasmFunction | null = if (isStringStruct(cx, fieldStruct) && cx.wasm.stringHashFunc != null) { cx.wasm.stringHashFunc } else { null }; var hashVtInfo: ClassCodegenInfo | null = null; var hashSlotSig: WasmSignature | null = null; if (hashFunc == null && fieldStruct.classType != null) { let fct = fieldStruct.classType as ClassType; if (fct.members.has("hashCode")) { hashFunc = cx.resolveDevirtualizedMethod(fct, "hashCode"); if (hashFunc == null) { // Overridden in some subclass: dispatch through the // field class's vtable, like any virtual method call. var resolvedOpt: WasmFunction | null = null; var hc: ClassType | null = fct; while (hc != null && resolvedOpt == null) { var hg: ClassType | null = hc; while (hg != null && resolvedOpt == null) { let key = getClassMethodKey(getClassKey(hg), 'hashCode'); if (let (true, m) = cx.wasm.classMethodMap.get(key)) { resolvedOpt = m; } hg = hg.genericSource; } hc = hc.superType; } let infoOpt2 = if (let (true, info) = cx.wasm.classInfos.get(getClassKey(fct))) info else null; if (resolvedOpt == null || infoOpt2 == null) { bail(cx, 'case hash field dispatch'); } if (cx.vtableSlotIndex(infoOpt2, 'hashCode') < 0) { bail(cx, 'case hash field dispatch'); } hashVtInfo = infoOpt2; hashSlotSig = resolvedOpt.signature; } } } if (hashFunc != null || hashSlotSig != null) { let fieldRef = cx.b.addRef(new IrRefField(st, f.name as String)); let v = cx.b.emit(IrOp.struct_get, ft, selfC, fieldRef); // Null-safe: null hashes to 0. let isNull = cx.b.emit(IrOp.ref_is_null, i32vt, v, -1); let nullB = cx.b.newBlock(); let callB = cx.b.newBlock(); cx.b.brIf(isNull, nullB, noValues(), callB, noValues()); let mergeB = cx.b.newBlock(); let result = cx.b.blockParam(mergeB, i32vt); cx.b.switchTo(nullB); let zero = cx.b.constI32(0, i32vt); cx.b.br(mergeB, oneValue(zero)); cx.b.switchTo(callB); let called = if (hashSlotSig != null) { let nonNullV = cx.stripNonNull(v); cx.lowerVtableCall(nonNullV, hashVtInfo as ClassCodegenInfo, 'hashCode', hashSlotSig, oneValue(nonNullV), hashSlotSig.returns[0]) } else { callUnary(cx, hashFunc as WasmFunction, v) }; cx.b.br(mergeB, oneValue(called)); cx.b.switchTo(mergeB); return result; } } // Unsupported field kinds hash to 0 (mirrors streaming). return cx.b.constI32(0, i32vt); } /** * Synthesized case-class operator== (mirrors the streaming * generator): `other` must ref.test as this struct, then every * field compares equal — numerics by value, Strings by content and * classes through a DEVIRTUALIZED operator== (both null-safely), * other references by identity. Virtual dispatch bails to * streaming. */ export function lowerCaseClassEq(cx: LoweringContext): IrBody { let sig = cx.func.signature; if (sig.params.length != 2 || sig.returns.length != 1 || cx.func.structType == null) { bail(cx, 'case eq shape'); } let st = cx.func.structType as WasmStruct; let i32vt = new ValTypeI32() as ValType; let entry = cx.b.newBlock(); let params = new Array(); for (let vt in sig.params) { params.push(cx.b.blockParam(entry, vt)); } cx.b.switchTo(entry); let stVt = new ValTypeRef(st) as ValType; let test = cx.b.emit(IrOp.ref_test, i32vt, params[1], cx.b.internType(stVt)); if (st.fields.length <= 1) { cx.b.ret(test); return cx.b.finish(); } let thenB = cx.b.newBlock(); let elseB = cx.b.newBlock(); cx.b.brIf(test, thenB, noValues(), elseB, noValues()); let mergeB = cx.b.newBlock(); let resultParam = cx.b.blockParam(mergeB, i32vt); cx.b.switchTo(elseB); let zero = cx.b.constI32(0, i32vt); cx.b.br(mergeB, oneValue(zero)); cx.b.switchTo(thenB); let selfC = cx.b.emit(IrOp.ref_cast, stVt, params[0], cx.b.internType(stVt)); let otherC = cx.b.emit(IrOp.ref_cast, stVt, params[1], cx.b.internType(stVt)); var acc = -1; for (let f in st.fields) { if (f.name == null || (f.name as String) == "") { continue; } let fieldRef = cx.b.addRef(new IrRefField(st, f.name as String)); let a = cx.b.emit(IrOp.struct_get, f.type, selfC, fieldRef); let b2 = cx.b.emit(IrOp.struct_get, f.type, otherC, fieldRef); let valueType = caseValueFieldType(cx, f.name as String); let fe = if (valueType != null) lowerValueEq(cx, valueType as Type, a, valueType as Type, b2) else synthFieldEq(cx, f, a, b2); acc = if (acc == -1) fe else cx.b.binary(IrOp.i32_and, i32vt, acc, fe); } if (acc == -1) { acc = cx.b.constI32(1, i32vt); } cx.b.br(mergeB, oneValue(acc)); cx.b.switchTo(mergeB); cx.b.ret(resultParam); return cx.b.finish(); } /** * Synthesized case-class hashCode (mirrors the streaming * generator): h = fold(h * 31 + fieldHash). Numerics hash by value * (i64 folds lo ^ hi), Strings through the runtime helper and * class fields through a DEVIRTUALIZED hashCode (both null-safely, * null hashing to 0); other reference fields hash to 0. Float * fields bail (no reinterpret ops in ZIR yet). */ export function lowerCaseClassHash(cx: LoweringContext): IrBody { let sig = cx.func.signature; if (sig.params.length != 1 || sig.returns.length != 1 || cx.func.structType == null) { bail(cx, 'case hash shape'); } let st = cx.func.structType as WasmStruct; let i32vt = new ValTypeI32() as ValType; let entry = cx.b.newBlock(); let params = new Array(); for (let vt in sig.params) { params.push(cx.b.blockParam(entry, vt)); } cx.b.switchTo(entry); if (st.fields.length <= 1) { cx.b.ret(cx.b.constI32(0, i32vt)); return cx.b.finish(); } let stVt = new ValTypeRef(st) as ValType; let selfC = cx.b.emit(IrOp.ref_cast, stVt, params[0], cx.b.internType(stVt)); var h = -1; for (let f in st.fields) { if (f.name == null || (f.name as String) == "") { continue; } let fh = synthFieldHash(cx, st, f, selfC); if (h == -1) { h = fh; } else { let thirtyOne = cx.b.constI32(31, i32vt); let scaled = cx.b.binary(IrOp.i32_mul, i32vt, h, thirtyOne); h = cx.b.binary(IrOp.i32_add, i32vt, scaled, fh); } } if (h == -1) { h = cx.b.constI32(0, i32vt); } cx.b.ret(h); return cx.b.finish(); } /** * `a == b` for record or tuple operands of types `lType` and `rType`, * with or without `| null` (docs/design/equality.md, "Structural * equality for records and tuples"): both null is true, one null is * false, and otherwise the pair's comparison function answers. Operands * whose fields do not pair up are never equal. */ export function lowerValueEq(cx: LoweringContext, lType: Type, a: i32, rType: Type, b2: i32): i32 { let i32vt = new ValTypeI32() as ValType; let l = valueEqOperand(lType); let r = valueEqOperand(rType); if (l == null || r == null) { bail(cx, 'structural equality operand'); } // An existential compares the record it holds, whose shape only the // run time knows: the erased comparison unwraps it and compares by // shape and fields. if (isExistentialRecord(l as Type) || isExistentialRecord(r as Type)) { return lowerErasedEq(cx, a, b2); } let fieldsOpt = valueEqFields(l as Type, r as Type); if (fieldsOpt == null) { return cx.b.constI32(0, i32vt); } let fields = fieldsOpt as GrowableArray; // An operand held as its fields (an exploded parameter, a held `var` // or result, a literal operand) compares here, from the fields, so its // record is never built. let fromFields = cx.explodedRecords.has(a) || cx.explodedRecords.has(b2); var found: WasmFunction | null = null; if (let (true, f) = cx.wasm.valueEqFuncs.get(valueEqKey(l as Type, r as Type))) { found = f; } if (found == null && !fromFields) { bail(cx, 'structural equality not reached'); } let compare = (x: i32, y: i32) => if (fromFields) inlineValueEq(cx, l as Type, x, r as Type, y, fields) else callEqMethod(cx, found as WasmFunction, x, y); let aNullable = isNullableRef(cx.valueTypeOf(a)); let bNullable = isNullableRef(cx.valueTypeOf(b2)); if (!aNullable && !bNullable) { return compare(a, b2); } let aNull = if (aNullable) cx.b.emit(IrOp.ref_is_null, i32vt, a, -1) else cx.b.constI32(0, i32vt); let bNull = if (bNullable) cx.b.emit(IrOp.ref_is_null, i32vt, b2, -1) else cx.b.constI32(0, i32vt); let anyNull = cx.b.binary(IrOp.i32_or, i32vt, aNull, bNull); let nullB = cx.b.newBlock(); let valueB = cx.b.newBlock(); let mergeB = cx.b.newBlock(); let result = cx.b.blockParam(mergeB, i32vt); cx.b.brIf(anyNull, nullB, noValues(), valueB, noValues()); cx.b.switchTo(nullB); cx.b.br(mergeB, oneValue(cx.b.binary(IrOp.i32_and, i32vt, aNull, bNull))); cx.b.switchTo(valueB); cx.b.br(mergeB, oneValue(compare(a, b2))); cx.b.switchTo(mergeB); return result; } /** * The class a field of type `t` holds (without `| null`), when it is a * laid-out class that is not an extension. */ function fieldClassOf(cx: LoweringContext, t: Type): ClassType | null { var b = baseType(t); if (b is UnionType) { var only: Type | null = null; var count = 0; for (let m in b.types) { if (!(m is NullType)) { only = m; count += 1; } } if (count != 1 || only == null) { return null; } b = baseType(only as Type); } if (!(b is ClassType)) { return null; } let ct = eraseTypeParameters(cx.wasm, b) as ClassType; if (ct.isExtension || !cx.wasm.classInfos.has(getClassKey(ct))) { return null; } return ct; } /** * The class two fields compare at: the wider of the two when one class * extends the other (`{a: Dog}` against `{a: Animal}` compares at * `Animal`), else the left one's. */ function comparedClassOf(cx: LoweringContext, tl: Type, tr: Type): ClassType | null { let l = fieldClassOf(cx, tl); let r = fieldClassOf(cx, tr); if (l == null || r == null) { return l; } let rKey = getClassKey(r as ClassType); var s: ClassType | null = l; while (s != null) { if (getClassKey(s as ClassType) == rKey) { return r; } s = (s as ClassType).superType; } return l; } /** * One pair of fields of a structural comparison, typed `tl` and `tr`, * each compared with its own type's `==`: nested records and tuples * through their pair's function, numbers by value, `String` by content, * a class through its `operator ==`, and any other reference through * the erased comparison. */ function valueFieldEq(cx: LoweringContext, tl: Type, a: i32, tr: Type, b2: i32) { let i32vt = new ValTypeI32() as ValType; if (valueEqOperand(tl) != null && valueEqOperand(tr) != null) { return lowerValueEq(cx, tl, a, tr, b2); } let vt = cx.valueTypeOf(a); if (vt is ValTypeI32) { return cx.b.binary(IrOp.i32_eq, i32vt, a, b2); } if (vt is ValTypeI64) { return cx.b.binary(IrOp.i64_eq, i32vt, a, b2); } if (vt is ValTypeF32) { return cx.b.binary(IrOp.f32_eq, i32vt, a, b2); } if (vt is ValTypeF64) { return cx.b.binary(IrOp.f64_eq, i32vt, a, b2); } let ct = comparedClassOf(cx, tl, tr); if (ct != null) { let st = refTargetOf(vt); if (st is WasmStruct && isStringStruct(cx, st)) { return refEqFastPathCall(cx, stringEqFunc(cx), a, b2, true); } return lowerClassEquality(cx, a, b2, ct as ClassType); } if (!isRefValType(vt) || !isRefValType(cx.valueTypeOf(b2))) { bail(cx, 'structural equality field type'); } return lowerErasedEq(cx, a, b2); } /** * `a == b2` for two inline values in the slots of one layout (#812): every * pair of slots equal. A write fills the slots its member does not use * with defaults, so equal values agree on those too, and the discriminant * slots are among the pairs compared. Each slot compares with the `==` of * the type a member puts there, null-safely where a member leaves it * empty. */ export function lowerInlineEq(cx: LoweringContext, layout: InlineLayout, a: GrowableArray, b2: GrowableArray): i32 { let i32vt = new ValTypeI32() as ValType; let falseB = cx.b.newBlock(); let mergeB = cx.b.newBlock(); let result = cx.b.blockParam(mergeB, i32vt); for (var s = 0; s < layout.slots.length; s += 1) { let t = slotElementType(layout, s); if (t == null) { continue; } let same = nullSafeFieldEq(cx, t, a[s], b2[s]); let next = cx.b.newBlock(); cx.b.brIf(same, next, noValues(), falseB, noValues()); cx.b.switchTo(next); } cx.b.br(mergeB, oneValue(cx.b.constI32(1, i32vt))); cx.b.switchTo(falseB); cx.b.br(mergeB, oneValue(cx.b.constI32(0, i32vt))); cx.b.switchTo(mergeB); return result; } /** * The type a member puts in slot `s` of `layout`, a literal's base type * for a discriminant, or null for a slot that only `_` fills. */ function slotElementType(layout: InlineLayout, s: i32): Type | null { for (var m = 0; m < layout.members.length; m += 1) { let row = layout.memberSlots[m]; for (var i = 0; i < row.length; i += 1) { if (row[i] != s) { continue; } let el = layout.members[m].elementTypes[i]; if (el is HoleType) { continue; } return baseType(el); } } return null; } /** `valueFieldEq`, with both null equal and one null unequal. */ function nullSafeFieldEq(cx: LoweringContext, t: Type, a: i32, b2: i32): i32 { let i32vt = new ValTypeI32() as ValType; let aNullable = isNullableRef(cx.valueTypeOf(a)); let bNullable = isNullableRef(cx.valueTypeOf(b2)); if (!aNullable && !bNullable) { return valueFieldEq(cx, t, a, t, b2); } let aNull = if (aNullable) cx.b.emit(IrOp.ref_is_null, i32vt, a, -1) else cx.b.constI32(0, i32vt); let bNull = if (bNullable) cx.b.emit(IrOp.ref_is_null, i32vt, b2, -1) else cx.b.constI32(0, i32vt); let anyNull = cx.b.binary(IrOp.i32_or, i32vt, aNull, bNull); let nullB = cx.b.newBlock(); let valueB = cx.b.newBlock(); let mergeB = cx.b.newBlock(); let result = cx.b.blockParam(mergeB, i32vt); cx.b.brIf(anyNull, nullB, noValues(), valueB, noValues()); cx.b.switchTo(nullB); cx.b.br(mergeB, oneValue(cx.b.binary(IrOp.i32_and, i32vt, aNull, bNull))); cx.b.switchTo(valueB); let aValue = if (aNullable) cx.reassertNonNull(a, cx.nonNullOf(cx.valueTypeOf(a))) else a; let bValue = if (bNullable) cx.reassertNonNull(b2, cx.nonNullOf(cx.valueTypeOf(b2))) else b2; cx.b.br(mergeB, oneValue(valueFieldEq(cx, t, aValue, t, bValue))); cx.b.switchTo(mergeB); return result; } /** * Whether the optional field `name` is present in `rec`, an i32 0 or 1, * read from the record's `$present` word through dispatch `d`; 1 for a * required field. */ function presenceOf(cx: LoweringContext, d: RecordDispatchInfo, name: String, optional: boolean, rec: i32) { let i32vt = new ValTypeI32() as ValType; if (!optional) { return cx.b.constI32(1, i32vt); } let i64vt = new ValTypeI64() as ValType; let bit = d.optionalBitOf(name); let word = cx.recordDispatchRead(d, presentWordName(bit >> 6), rec); let shifted = cx.b.binary(IrOp.i64_shr_u, i64vt, word, cx.b.constI64((bit & 63) as i64, i64vt)); let masked = cx.b.binary(IrOp.i64_and, i64vt, shifted, cx.b.constI64(1, i64vt)); return cx.b.emit(IrOp.i32_wrap_i64, i32vt, masked, -1); } /** * The body of a structural comparison function (`valueEqLeft` and * `valueEqRight` set): each pair of fields in turn, returning false at * the first that differs. A pair of optional fields is equal when both * are absent, or both present with equal values; their values are read * only when present. */ export function lowerValueEqFunction(cx: LoweringContext): IrBody { let func = cx.func; let l = func.valueEqLeft as Type; let r = func.valueEqRight as Type; let fieldsOpt = valueEqFields(l, r); let sig = func.signature; if (fieldsOpt == null || sig.params.length != 2 || sig.returns.length != 1) { bail(cx, 'structural equality function shape'); } let fields = fieldsOpt as GrowableArray; let i32vt = new ValTypeI32() as ValType; let entry = cx.b.newBlock(); let a = cx.b.blockParam(entry, sig.params[0]); let b2 = cx.b.blockParam(entry, sig.params[1]); cx.b.switchTo(entry); if (fields.length == 0) { cx.b.ret(cx.b.constI32(1, i32vt)); return cx.b.finish(); } let falseB = cx.b.newBlock(); emitFieldComparisons(cx, l, a, r, b2, fields, falseB); cx.b.ret(cx.b.constI32(1, i32vt)); cx.b.switchTo(falseB); cx.b.ret(cx.b.constI32(0, i32vt)); return cx.b.finish(); } /** * Compares `a` and `b2`, records or tuples of types `l` and `r`, pair of * fields by pair, branching to `falseB` at the first pair that differs. * Leaves the builder in the block reached when every pair is equal. A * pair of optional fields is equal when both are absent, or both present * with equal values; their values are read only when present. A record * held as its fields (`explodedRecords`) answers its reads from them. */ function emitFieldComparisons(cx: LoweringContext, l: Type, a: i32, r: Type, b2: i32, fields: GrowableArray, falseB: i32): void { let i32vt = new ValTypeI32() as ValType; for (let f in fields) { let nextB = cx.b.newBlock(); var va = -1; var vb = -1; if (l is RecordType && r is RecordType) { let dl = cx.recordDispatchOf(l); let dr = cx.recordDispatchOf(r); if (f.leftOptional || f.rightOptional) { let pl = presenceOf(cx, dl, f.name, f.leftOptional, a); let pr = presenceOf(cx, dr, f.name, f.rightOptional, b2); let samePresenceB = cx.b.newBlock(); cx.b.brIf(cx.b.binary(IrOp.i32_eq, i32vt, pl, pr), samePresenceB, noValues(), falseB, noValues()); cx.b.switchTo(samePresenceB); let presentB = cx.b.newBlock(); cx.b.brIf(pl, presentB, noValues(), nextB, noValues()); cx.b.switchTo(presentB); } va = cx.recordDispatchRead(dl, f.name, a); vb = cx.recordDispatchRead(dr, f.name, b2); } else { va = tupleElement(cx, a, f.name); vb = tupleElement(cx, b2, f.name); } cx.b.brIf(valueFieldEq(cx, f.left, va, f.right, vb), nextB, noValues(), falseB, noValues()); cx.b.switchTo(nextB); } } /** * `a == b2` compared at the site, pair of fields by pair: what * `lowerValueEq` does when an operand is a record held as its fields, so * the comparison reads the fields instead of passing a record to the * pair's function. */ function inlineValueEq(cx: LoweringContext, l: Type, a: i32, r: Type, b2: i32, fields: GrowableArray): i32 { let i32vt = new ValTypeI32() as ValType; if (fields.length == 0) { return cx.b.constI32(1, i32vt); } let falseB = cx.b.newBlock(); let mergeB = cx.b.newBlock(); let result = cx.b.blockParam(mergeB, i32vt); emitFieldComparisons(cx, l, a, r, b2, fields, falseB); cx.b.br(mergeB, oneValue(cx.b.constI32(1, i32vt))); cx.b.switchTo(falseB); cx.b.br(mergeB, oneValue(cx.b.constI32(0, i32vt))); cx.b.switchTo(mergeB); return result; } /** * `hashOf(v)` when `v`, a reference, is not null, and 0 when it is. * Non-null values pass straight through. */ function nullSafeHash(cx: LoweringContext, v: i32, hashOf: (nonNull: i32) => i32) { let i32vt = new ValTypeI32() as ValType; let vt = cx.valueTypeOf(v); if (!isNullableRef(vt)) { return hashOf(v); } let nullB = cx.b.newBlock(); let valueB = cx.b.newBlock(); let mergeB = cx.b.newBlock(); let result = cx.b.blockParam(mergeB, i32vt); cx.b.brIf(cx.b.emit(IrOp.ref_is_null, i32vt, v, -1), nullB, noValues(), valueB, noValues()); cx.b.switchTo(nullB); cx.b.br(mergeB, oneValue(cx.b.constI32(0, i32vt))); cx.b.switchTo(valueB); let nonNull = cx.coerceTo(v, new ValTypeRef(refTargetOf(vt) as WasmStruct) as ValType); cx.b.br(mergeB, oneValue(hashOf(nonNull))); cx.b.switchTo(mergeB); return result; } /** * The hash of `v`, a record or tuple of type `t` (with or without * `| null`), through the type's hash function. Null hashes to 0. */ export function lowerValueHash(cx: LoweringContext, t: Type, v: i32): i32 { let type = valueEqOperand(t); if (type == null) { bail(cx, 'structural hash operand'); } // An existential hashes the record it holds, through its table. let existential = baseType(type as Type); if (existential is RecordType) { let rec = existential; if (rec.isExistential) { return existentialHash(cx, v, cx.recordDispatchOf(rec)); } } var found: WasmFunction | null = null; if (let (true, f) = cx.wasm.valueHashFuncs.get(valueHashKey(type as Type))) { found = f; } if (found == null) { bail(cx, 'structural hash not reached'); } let fn = found as WasmFunction; return nullSafeHash(cx, v, (nonNull) => callUnary(cx, fn, nonNull)); } /** * The hash of one field of type `t`, consistent with comparing it by its * type's `==` (`valueFieldEq`): nested records and tuples through their * functions, numbers by value, `String` by content, a class through its * `hashCode`. A field whose `==` is identity or erased, such as a class * without `hashCode`, an array or a closure, contributes 0, which no * `==` can disagree with. */ function fieldHash(cx: LoweringContext, t: Type, v: i32) { let i32vt = new ValTypeI32() as ValType; if (valueEqOperand(t) != null) { return lowerValueHash(cx, t, v); } let numeric = hashNumeric(cx, v); if (numeric >= 0) { return numeric; } let ct = fieldClassOf(cx, t); if (ct == null) { return cx.b.constI32(0, i32vt); } let fieldClass = ct as ClassType; let strClass = cx.wasm.stringClass; let isString = strClass != null && cx.canonicalKeyOf(fieldClass) == cx.canonicalKeyOf(strClass); if (!isString && !fieldClass.members.has('hashCode')) { return cx.b.constI32(0, i32vt); } return nullSafeHash(cx, v, (nonNull) => hashClassValue(cx, fieldClass, nonNull)); } /** * The body of a record or tuple type's hash function (`valueHashType` * set): `h * 31 + field` over the fields in `valueEqFields` order, as the * case-class `hashCode` folds. An optional field contributes its value's * hash only when present, so two equal records hash alike. */ export function lowerValueHashFunction(cx: LoweringContext): IrBody { let t = cx.func.valueHashType as Type; let fieldsOpt = valueEqFields(t, t); let sig = cx.func.signature; if (fieldsOpt == null || sig.params.length != 1 || sig.returns.length != 1) { bail(cx, 'structural hash function shape'); } let fields = fieldsOpt as GrowableArray; let i32vt = new ValTypeI32() as ValType; let entry = cx.b.newBlock(); let v = cx.b.blockParam(entry, sig.params[0]); cx.b.switchTo(entry); var h = cx.b.constI32(0, i32vt); for (let f in fields) { var fh = -1; if (t is RecordType) { let d = cx.recordDispatchOf(t); if (f.leftOptional) { let presentB = cx.b.newBlock(); let absentB = cx.b.newBlock(); let mergeB = cx.b.newBlock(); let merged = cx.b.blockParam(mergeB, i32vt); cx.b.brIf(presenceOf(cx, d, f.name, true, v), presentB, noValues(), absentB, noValues()); cx.b.switchTo(presentB); cx.b.br(mergeB, oneValue( fieldHash(cx, f.left, cx.recordDispatchRead(d, f.name, v)))); cx.b.switchTo(absentB); cx.b.br(mergeB, oneValue(cx.b.constI32(0, i32vt))); cx.b.switchTo(mergeB); fh = merged; } else { fh = fieldHash(cx, f.left, cx.recordDispatchRead(d, f.name, v)); } } else { fh = fieldHash(cx, f.left, tupleElement(cx, v, f.name)); } let scaled = cx.b.binary(IrOp.i32_mul, i32vt, h, cx.b.constI32(31, i32vt)); h = cx.b.binary(IrOp.i32_add, i32vt, scaled, fh); } cx.b.ret(h); return cx.b.finish(); } /** Element `name` (its index as a string) of the tuple `t`. */ function tupleElement(cx: LoweringContext, t: i32, name: String): i32 { let st = refTargetOf(cx.valueTypeOf(t)); if (!(st is WasmStruct)) { bail(cx, 'tuple equality operand'); } let tupleStruct = st as WasmStruct; let index = tupleStruct.fieldIndexByName(name); if (index < 0) { bail(cx, 'tuple equality element'); } return cx.b.emit(IrOp.struct_get, tupleStruct.fields[index].type, t, cx.b.addRef(new IrRefField(tupleStruct, name))); } /** * Erased equality over eqref-typed operands: identity, then null, then * the runtime class's `operator ==` through the shared dispatch, else * false. Without the dispatch (nothing marked equality as dispatched) * the references are simply different. */ export function lowerErasedEq(cx: LoweringContext, leftIn: i32, rightIn: i32): i32 { let i32vt = new ValTypeI32() as ValType; let eqVt = new ValTypeEqRef() as ValType; var left = leftIn; var right = rightIn; if (cx.valueTypeOf(left) is ValTypeAnyRef) { left = cx.b.emit(IrOp.ref_cast, eqVt, left, cx.b.internType(eqVt)); } if (cx.valueTypeOf(right) is ValTypeAnyRef) { right = cx.b.emit(IrOp.ref_cast, eqVt, right, cx.b.internType(eqVt)); } let merge = cx.b.newBlock(); let res = cx.b.blockParam(merge, i32vt); let one = cx.b.constI32(1, i32vt); let zero = cx.b.constI32(0, i32vt); let same = cx.b.binary(IrOp.ref_eq, i32vt, left, right); let notSameB = cx.b.newBlock(); cx.b.brIf(same, merge, oneValue(one), notSameB, noValues()); cx.b.switchTo(notSameB); let lNull = cx.b.emit(IrOp.ref_is_null, i32vt, left, -1); let rNull = cx.b.emit(IrOp.ref_is_null, i32vt, right, -1); let anyNull = cx.b.binary(IrOp.i32_or, i32vt, lNull, rNull); let contB = cx.b.newBlock(); cx.b.brIf(anyNull, merge, oneValue(zero), contB, noValues()); // The runtime class's operator: the shared dispatch tests each class // that introduces one (lowerErasedEqDispatch). Every comparison through // an erased or interface operand goes there, so `==` means the same // through `anyref` as at the value's own class. cx.b.switchTo(contB); let dispatchOpt = cx.wasm.erasedEqFunc; if (dispatchOpt != null) { let dispatch = dispatchOpt; let answer = cx.b.callFunc(cx.b.addRef(new IrRefFunc(dispatch)), twoValues(left, right), i32vt); cx.b.br(merge, oneValue(answer)); cx.b.switchTo(merge); return res; } // Different or non-comparable references: false. cx.b.br(merge, oneValue(zero)); cx.b.switchTo(merge); return res; } /** * The introducing classes the erased dispatch tests: each declares or * derives a reached `operator ==` and its superclass has none, so one * instance-of test covers its whole subtree and the operator's own * dispatch picks the override. String first, as the common case; the rest * in type order, so the output does not depend on hash order. */ function erasedEqualityIntroducers(cx: LoweringContext) { let found = new Array(); for (let entry in cx.wasm.classInfos) { let info = entry.value; let ct = info.structType.classType; if (ct == null || ct.isExtension || !laidOut(info) || !ct.members.has("==")) { continue; } if (!cx.wasm.classMethodMap.has(getClassMethodKey(getClassKey(ct), "=="))) { continue; } let sup = ct.superType; if (sup != null && (sup as ClassType).members.has("==")) { continue; } found.push(info); } // Insertion sort by type index: small, stable, deterministic. for (var i = 1; i < found.length; i += 1) { let x = found[i]; var j = i - 1; while (j >= 0 && found[j].structType.index > x.structType.index) { found[j + 1] = found[j]; j -= 1; } found[j + 1] = x; } let ordered = new Array(); for (let info in found) { if (isStringStruct(cx, info.structType)) { ordered.push(info); } } for (let info in found) { if (!isStringStruct(cx, info.structType)) { ordered.push(info); } } return ordered; } /** * One dispatch per distinct fat pointer type among the record types the * program converts to a slot that does not know their shape (the * checker's `erasedRecordTypes`): only those reach this comparison. * Record types whose getters have the same signatures share a fat * pointer type; any one of their dispatches describes the fields' wasm * types, which is all the comparison reads. In program order, so the * output does not depend on hash order. */ function erasedRecordFatPointers(cx: LoweringContext) { let out = new Array(); let program = cx.wasm.program; if (program == null) { return out; } for (let unit in program.units) { for (let rt in unit.model.erasedRecordTypes) { let dOpt = cx.wasm.findRecordDispatch( recordWasmFields(cx.wasm, rt, null), sortedOptionalNames(rt)); if (dOpt == null) { continue; } let d = dOpt; var seen = false; for (let e in out) { if (e.fatPtrType === d.fatPtrType) { seen = true; } } if (!seen) { out.push(d); } } } return out; } /** * `a == b` for a record `a` of fat pointer type `d.fatPtrType` and a * reference `b` whose type is not known (#399): `b` must be a record of * the same shape, which the dispatch table's `` id tells, since * shapes can share a fat pointer type. Then each field compares, read * through each value's own table: numbers by value, references through * `$erasedEq` again, which is where String's content equality and a * nested record's come from. */ function erasedRecordEq(cx: LoweringContext, d: RecordDispatchInfo, a: i32, b2: i32) { let i32vt = new ValTypeI32() as ValType; let fat = d.fatPtrType; let otherIsRecord = refTestOf(cx, b2, fat); let bothB = cx.b.newBlock(); let differentB = cx.b.newBlock(); cx.b.brIf(otherIsRecord, bothB, noValues(), differentB, noValues()); cx.b.switchTo(differentB); cx.b.ret(cx.b.constI32(0, i32vt)); cx.b.switchTo(bothB); let af = refCastTo(cx, a, fat); let bf = refCastTo(cx, b2, fat); let vtVt = new ValTypeRef(d.vtableType) as ValType; let aVt = cx.b.emit(IrOp.iface_vtable, vtVt, af, -1); let bVt = cx.b.emit(IrOp.iface_vtable, vtVt, bf, -1); let shapeRef = cx.b.addRef(new IrRefField(d.vtableType, recordShapeFieldName)); let aShape = cx.b.emit(IrOp.struct_get, i32vt, aVt, shapeRef); let bShape = cx.b.emit(IrOp.struct_get, i32vt, bVt, shapeRef); let sameShape = cx.b.binary(IrOp.i32_eq, i32vt, aShape, bShape); let fieldsB = cx.b.newBlock(); let otherShapeB = cx.b.newBlock(); cx.b.brIf(sameShape, fieldsB, noValues(), otherShapeB, noValues()); cx.b.switchTo(otherShapeB); cx.b.ret(cx.b.constI32(0, i32vt)); cx.b.switchTo(fieldsB); let structVt = new ValTypeStructRef() as ValType; let aInst = cx.b.emit(IrOp.iface_instance, structVt, af, -1); let bInst = cx.b.emit(IrOp.iface_instance, structVt, bf, -1); var acc = cx.b.constI32(1, i32vt); for (var i = 0; i < d.fields.length; i += 1) { let sig = d.getterTypes[i]; let name = d.fields[i].name; if (sig.returns.length != 1 || name == null) { continue; } let fieldRef = cx.b.addRef(new IrRefField(d.vtableType, name as String)); let getterVt = new ValTypeRef(sig) as ValType; let ga = cx.b.emit(IrOp.struct_get, getterVt, aVt, fieldRef); let gb = cx.b.emit(IrOp.struct_get, getterVt, bVt, fieldRef); let fieldVt = sig.returns[0]; let va = cx.b.callRef(ga, oneValue(aInst), fieldVt); let vb = cx.b.callRef(gb, oneValue(bInst), fieldVt); acc = cx.b.binary(IrOp.i32_and, i32vt, acc, erasedFieldEq(cx, fieldVt, va, vb)); } return acc; } /** Two field values of wasm type `vt`, compared as the erased `==` does. */ function erasedFieldEq(cx: LoweringContext, vt: ValType, a: i32, b2: i32): i32 { let i32vt = new ValTypeI32() as ValType; if (vt is ValTypeI32) { return cx.b.binary(IrOp.i32_eq, i32vt, a, b2); } if (vt is ValTypeI64) { return cx.b.binary(IrOp.i64_eq, i32vt, a, b2); } if (vt is ValTypeF32) { return cx.b.binary(IrOp.f32_eq, i32vt, a, b2); } if (vt is ValTypeF64) { return cx.b.binary(IrOp.f64_eq, i32vt, a, b2); } if (!isRefValType(vt)) { bail(cx, 'erased record field type'); } let sig = cx.func.signature; let left = cx.coerceTo(a, sig.params[0]); let right = cx.coerceTo(b2, sig.params[1]); return cx.b.callFunc(cx.b.addRef(new IrRefFunc(cx.func)), twoValues(left, right), i32vt); } /** * The body of `$erasedEq(a, b)`: equality of two references whose class * the caller does not know (equality.md, "Equality through interfaces and * anyref"). Identity, then null; then a test of `a` against each class * that introduces an `operator ==`. When one matches, `b` must be of that * class too, and that class's operator answers through its own dispatch * (lowerClassEquality's path). A class that matches none compares * identity, already answered. */ export function lowerErasedEqDispatch(cx: LoweringContext): IrBody { let i32vt = new ValTypeI32() as ValType; let sig = cx.func.signature; let entry = cx.b.newBlock(); let a = cx.b.blockParam(entry, sig.params[0]); let b2 = cx.b.blockParam(entry, sig.params[1]); cx.b.switchTo(entry); let same = cx.b.emit(IrOp.ref_eq, i32vt, a, b2); let sameB = cx.b.newBlock(); let restB = cx.b.newBlock(); cx.b.brIf(same, sameB, noValues(), restB, noValues()); cx.b.switchTo(sameB); cx.b.ret(cx.b.constI32(1, i32vt)); cx.b.switchTo(restB); let aNull = cx.b.emit(IrOp.ref_is_null, i32vt, a, -1); let bNull = cx.b.emit(IrOp.ref_is_null, i32vt, b2, -1); let anyNull = cx.b.binary(IrOp.i32_or, i32vt, aNull, bNull); let nullB = cx.b.newBlock(); let testsB = cx.b.newBlock(); cx.b.brIf(anyNull, nullB, noValues(), testsB, noValues()); cx.b.switchTo(nullB); cx.b.ret(cx.b.constI32(0, i32vt)); cx.b.switchTo(testsB); // An existential compares as the record it holds: compare again with // that in its place, one side at a time. for (let e in cx.wasm.existentialDispatchInfos) { for (var side = 0; side < 2; side += 1) { let operand = if (side == 0) a else b2; let isExistential = refTestOf(cx, operand, e.fatPtrType); let unwrapB = cx.b.newBlock(); let nextB = cx.b.newBlock(); cx.b.brIf(isExistential, unwrapB, noValues(), nextB, noValues()); cx.b.switchTo(unwrapB); let held = cx.coerceTo(existentialUnderlying(cx, refCastTo(cx, operand, e.fatPtrType), e), sig.params[0]); let pair = if (side == 0) twoValues(held, b2) else twoValues(a, held); cx.b.ret(cx.b.callFunc(cx.b.addRef(new IrRefFunc(cx.func)), pair, i32vt)); cx.b.switchTo(nextB); } } for (let d in erasedRecordFatPointers(cx)) { let isRecord = refTestOf(cx, a, d.fatPtrType); let recordB = cx.b.newBlock(); let nextB = cx.b.newBlock(); cx.b.brIf(isRecord, recordB, noValues(), nextB, noValues()); cx.b.switchTo(recordB); cx.b.ret(erasedRecordEq(cx, d, a, b2)); cx.b.switchTo(nextB); } for (let x in erasedEqualityIntroducers(cx)) { let xct = x.structType.classType as ClassType; let isX = refTestOf(cx, a, x.structType); let thenB = cx.b.newBlock(); let nextB = cx.b.newBlock(); cx.b.brIf(isX, thenB, noValues(), nextB, noValues()); cx.b.switchTo(thenB); let otherIsX = refTestOf(cx, b2, x.structType); let callB = cx.b.newBlock(); let falseB = cx.b.newBlock(); cx.b.brIf(otherIsX, callB, noValues(), falseB, noValues()); cx.b.switchTo(falseB); cx.b.ret(cx.b.constI32(0, i32vt)); cx.b.switchTo(callB); cx.b.ret(classEqNonNull(cx, refCastTo(cx, a, x.structType), refCastTo(cx, b2, x.structType), xct)); cx.b.switchTo(nextB); } cx.b.ret(cx.b.constI32(0, i32vt)); return cx.b.finish(); } /** * equals(a, b) — the @intrinsic declare from zena:map, * type-directed like the streaming backend's generateGlobalIntrinsic * but restricted to the tiers ZIR can express today. Could this be * written in Zena? Only once the language can constrain the type * parameter (equals) — the dispatch below is exactly what * such a bound would monomorphize to, and the string/hash helpers it * calls ARE Zena functions. Until then the type dispatch lives here * (routed by intrinsics.zena's lowerIntrinsic). By operand wasm * type — * numerics -> the type's eq instruction; * String/String -> String.operator== (content equality); * class w/ == -> ref.eq fast path around a DEVIRTUALIZED * operator== (see refEqFastPathCall); * anything else (nullable refs, erased operands, virtual ==) * -> bail to streaming. */ export function lowerEqIntrinsic(cx: LoweringContext, call: CallExpression): i32 { let i32vt = new ValTypeI32() as ValType; if (call.args.length != 2) { bail(cx, 'eq arity'); } let a = lowerExpr(cx, call.args[0], null); let b2 = lowerExpr(cx, call.args[1], null); let va = cx.valueTypeOf(a); let vb = cx.valueTypeOf(b2); if (va is ValTypeI32 && vb is ValTypeI32) { return cx.b.binary(IrOp.i32_eq, i32vt, a, b2); } if (va is ValTypeI64 && vb is ValTypeI64) { return cx.b.binary(IrOp.i64_eq, i32vt, a, b2); } if (va is ValTypeF32 && vb is ValTypeF32) { return cx.b.binary(IrOp.f32_eq, i32vt, a, b2); } if (va is ValTypeF64 && vb is ValTypeF64) { return cx.b.binary(IrOp.f64_eq, i32vt, a, b2); } if (va is ValTypeV128 && vb is ValTypeV128) { let eqVec = cx.b.emit(IrOp.simd_binary, new ValTypeV128(), cx.b.pushExtra(twoValues(a, b2)), 0x23); return cx.b.emit(IrOp.simd_unary, i32vt, eqVec, 0x63); } // Records and tuples compare field by field (lowerValueEq). let ta0 = cx.substitutedNodeType(call.args[0]); let tb0 = cx.substitutedNodeType(call.args[1]); if (ta0 != null && tb0 != null && valueEqOperand(ta0 as Type) != null && valueEqOperand(tb0 as Type) != null) { return lowerValueEq(cx, ta0 as Type, a, tb0 as Type, b2); } // Reference operands: String content equality, or a class // operator== behind the reference fast path. let ctA = cx.classTypeOfValue(a); let ctB = cx.classTypeOfValue(b2); if (ctA == null || ctB == null) { // An interface value or an erased reference: the runtime class // answers, through the erased comparison. let ta = cx.substitutedNodeType(call.args[0]); let tb = cx.substitutedNodeType(call.args[1]); if (ta == null || tb == null || !isRefValType(va) || !isRefValType(vb)) { bail(cx, 'eq operand type'); } return lowerErasedEq(cx, cx.unwrapFatPointer(ta as Type, a), cx.unwrapFatPointer(tb as Type, b2)); } let strClass = cx.wasm.stringClass; if (strClass != null && cx.canonicalKeyOf(ctA) == cx.canonicalKeyOf(strClass) && cx.canonicalKeyOf(ctB) == cx.canonicalKeyOf(strClass)) { return callEqMethod(cx, stringEqFunc(cx), a, b2); } if (!ctA.isExtension) { return lowerClassEquality(cx, a, b2, ctA); } if (isNullableRef(va) || isNullableRef(vb)) { bail(cx, 'nullable eq operand'); } return cx.b.binary(IrOp.ref_eq, new ValTypeI32(), a, b2); } /** * hash(v): by operand wasm type — * i32 -> the value itself; * i64 -> lo ^ hi fold (mirrors streaming); * String -> the runtime string-hash helper; * class w/hashCode -> DEVIRTUALIZED direct call; * floats -> +0.0 normalize, reinterpret (f64 folds); * nullable refs, erased operands -> bail; * overridden hashCode -> vtable dispatch. */ export function lowerHashIntrinsic(cx: LoweringContext, call: CallExpression): i32 { if (call.args.length != 1) { bail(cx, 'hash arity'); } let v = lowerExpr(cx, call.args[0], null); // A record or tuple hashes its fields, through its type's function. let t = cx.substitutedNodeType(call.args[0]); if (t != null && valueEqOperand(t as Type) != null) { return lowerValueHash(cx, t as Type, v); } let numeric = hashNumeric(cx, v); if (numeric >= 0) { return numeric; } let ctV = cx.classTypeOfValue(v); if (ctV == null) { bail(cx, 'hash operand type'); } return hashClassValue(cx, ctV as ClassType, v); } /** * The hash of a numeric or vector value, by its wasm type: an i32 is * itself, an i64 folds, floats hash their bits after normalizing -0.0. * -1 when `v` is a reference. */ function hashNumeric(cx: LoweringContext, v: i32): i32 { let vv = cx.valueTypeOf(v); if (vv is ValTypeI32) { return v; } if (vv is ValTypeI64) { return hashI64Fold(cx, v); } // Floats hash by bit pattern after adding +0.0 (streaming's shape // exactly — the add canonicalizes -0.0 to +0.0 so both zeros land // in one bucket; both backends must produce identical hashes). if (vv is ValTypeF32) { let zero32 = cx.b.constF32(0.0, new ValTypeF32()); let norm32 = cx.b.binary(IrOp.f32_add, new ValTypeF32() as ValType, v, zero32); return cx.b.emit(IrOp.i32_reinterpret_f32, new ValTypeI32(), norm32, -1); } if (vv is ValTypeF64) { let zero64 = cx.b.constF64(0.0, new ValTypeF64()); let norm64 = cx.b.binary(IrOp.f64_add, new ValTypeF64() as ValType, v, zero64); let bits = cx.b.emit(IrOp.i64_reinterpret_f64, new ValTypeI64(), norm64, -1); return hashI64Fold(cx, bits); } if (vv is ValTypeV128) { let i32vt = new ValTypeI32() as ValType; let e0 = cx.b.emit(IrOp.simd_extract_lane, i32vt, v, cx.b.pushExtra(twoValues(0x1B, 0))); let e1 = cx.b.emit(IrOp.simd_extract_lane, i32vt, v, cx.b.pushExtra(twoValues(0x1B, 1))); let e2 = cx.b.emit(IrOp.simd_extract_lane, i32vt, v, cx.b.pushExtra(twoValues(0x1B, 2))); let e3 = cx.b.emit(IrOp.simd_extract_lane, i32vt, v, cx.b.pushExtra(twoValues(0x1B, 3))); let x01 = cx.b.binary(IrOp.i32_xor, i32vt, e0, e1); let x23 = cx.b.binary(IrOp.i32_xor, i32vt, e2, e3); return cx.b.binary(IrOp.i32_xor, i32vt, x01, x23); } return -1; } /** * The hash of `v`, a value of class `ctV`: `String` through the runtime * helper, any other class through its `hashCode`, called directly when * no reached subclass overrides it and through the vtable when one does. */ function hashClassValue(cx: LoweringContext, ctV: ClassType, v: i32): i32 { let vv = cx.valueTypeOf(v); let strClass = cx.wasm.stringClass; if (strClass != null && !targetUsesJsStrings(cx.wasm.target) && cx.canonicalKeyOf(ctV) == cx.canonicalKeyOf(strClass)) { return callStringHash(cx, v); } if (isNullableRef(vv)) { bail(cx, 'nullable hash operand'); } let hashMethod = cx.resolveDevirtualizedMethod(ctV, "hashCode"); if (hashMethod != null) { return callUnary(cx, hashMethod, v); } if (cx.b.recorder != null) { // The dispatch below finds its slot's signature by its own walk of // the class chain, which template mode does not record. throw new TemplateAbandon('overridden hashCode'); } // Overridden hashCode: dispatch through the vtable, like the // case-class hash synthesizer does for its fields. var resolvedOpt: WasmFunction | null = null; var hc: ClassType | null = ctV; while (hc != null && resolvedOpt == null) { var hg: ClassType | null = hc; while (hg != null && resolvedOpt == null) { let key = getClassMethodKey(getClassKey(hg), 'hashCode'); if (let (true, m) = cx.wasm.classMethodMap.get(key)) { resolvedOpt = m; } hg = hg.genericSource; } hc = hc.superType; } let ci = if (let (true, info) = cx.wasm.classInfos.get(getClassKey(ctV))) info else null; if (resolvedOpt == null || ci == null) { bail(cx, 'hash operand type'); } if (cx.vtableSlotIndex(ci, 'hashCode') < 0) { bail(cx, 'hash operand type'); } let hsig = resolvedOpt.signature; let recv = cx.conformReceiver(v, hsig.params[0], 'hash receiver type'); return cx.lowerVtableCall(recv, ci, 'hashCode', hsig, oneValue(recv), hsig.returns[0]); }