import { Set, HashMap, HashSet } from 'zena:collections'; import { Program } from '../../program.zena'; import { ClassType, FunctionType, MixinType, InterfaceType, TypeId } from '../../types.zena'; import { Node, NodeId, ClassDeclaration, MethodDefinition, FieldDefinition, AccessorDeclaration, TypeAnnotation, Identifier, SymbolPropertyName, MemberExpression, } from '../../ast.zena'; import { SymbolId } from '../../scope/symbol.zena'; import { SemanticModel, memberKeyOf } from '../../semantic-model.zena'; import { collectMixinMembers, findMixinDeclaration, MixinKey, getSignatureKey, InterfaceKey, getInterfaceKey, } from '../codegen-utils.zena'; import { getClassTypeParameters, getInterfaceTypeParameters, substituteTypeParamsInCodegen } from '../type-mapping.zena'; import { WasmModule } from '../wasm-module.zena'; /** * ClassHierarchyAnalysis (CHA) manages caching and lookups for class hierarchies, * dynamic method overrides, field/accessor inheritance, and subclass relationships. */ export final class ClassHierarchyAnalysis { program: Program; instantiatedSpecializedClasses: HashSet; wasm: WasmModule; implementingMethodCache = new Map>(); implementingMethodNulls = new Map>(); implementingMethodsCache = new Map>>(); implementingFieldCache = new Map>(); implementingFieldNulls = new Map>(); implementingAccessorCache = new Map>(); implementingAccessorNulls = new Map>(); subclassRelationCache = new Map(); subclassesByBaseId = new Map>(); classDeclTypeCache = new Map(); classMixinIdsCache = new Map>(); classModels: HashMap; new(this.program, this.instantiatedSpecializedClasses, this.wasm, this.classModels); getClassMixinIds(cd: ClassDeclaration, symId: SymbolId, model: SemanticModel): HashMap { if (let (true, cached) = this.classMixinIdsCache.get(symId)) { return cached; } let seenIds = new Map(); collectMixinSymbolIds(this.program, model, cd.mixins, seenIds); this.classMixinIdsCache[symId] = seenIds; return seenIds; } /** * The declaration bodies that supply members to `ct`, one step of a * superclass walk, in the order a lookup should search them: a * declared class's own body; for the class a `with M` clause builds, * M's body and then the mixins M itself applies (`mixin M with A`), * the last applied first, since a later mixin overrides an earlier * one. Without the composed mixins, a method a class gets through * `M` from `A` has no declaration to reach. */ #declarationBodies(ct: ClassType): GrowableArray { let out = new Array(); this.#appendDeclarationBodies((ct.genericSource ?? ct).symbolId, ct.sourcePath, ct.isMixinIntermediate, ct.mixins, out); return out; } #appendDeclarationBodies(lookupId: SymbolId, sourcePath: String, isMixin: boolean, composed: GrowableArray, out: GrowableArray): void { var model: SemanticModel | null = null; if (sourcePath != "") { if (let (true, unit) = this.program.unitsByPath.get(sourcePath)) { model = unit.model; } } if (model == null) { if (let (true, m) = this.program.modelIndex.symbolToModel.get(lookupId)) { model = m; } } if (model == null) { return; } let found = model as SemanticModel; if (found.classDeclarations.has(lookupId)) { out.push(new DeclarationBody(found, found.classDeclarations[lookupId].body)); } else if (found.mixinDeclarations.has(lookupId)) { out.push(new DeclarationBody(found, found.mixinDeclarations[lookupId].body)); } if (!isMixin) { return; } var i = composed.length - 1; while (i >= 0) { let mt = composed[i]; let source = mt.genericSource ?? mt; this.#appendDeclarationBodies(source.symbolId, source.sourcePath, true, source.mixins, out); i -= 1; } } findImplementingMethod(cType: ClassType, mName: String, isStatic: boolean = false): MethodDefinition | null { let startClassId = if (cType.genericSource != null) (cType.genericSource as ClassType).id else cType.id; let cacheKey = (if (isStatic) "static#" else "") + mName; if (let (true, nulls) = this.implementingMethodNulls.get(startClassId)) { if (nulls.has(cacheKey)) { return null; } } if (let (true, cache) = this.implementingMethodCache.get(startClassId)) { if (let (true, cached) = cache.get(cacheKey)) { return cached; } } var curr: ClassType | null = cType; while (curr != null) { let ct = curr; for (let decl in this.#declarationBodies(ct)) { let model = decl.model; let body = decl.body; for (let member in body) { if (member is MethodDefinition) { if (member.isAbstract || member.isStatic != isStatic) { continue; } let name = getMethodName(model, member); if (matchMemberName(name, mName)) { if (!this.implementingMethodCache.has(startClassId)) { this.implementingMethodCache[startClassId] = new Map(); } this.implementingMethodCache[startClassId][cacheKey] = member; return member; } } } } curr = ct.superType; } if (!this.implementingMethodNulls.has(startClassId)) { this.implementingMethodNulls[startClassId] = new Set(); } this.implementingMethodNulls[startClassId].add(cacheKey); return null; } findImplementingMethods(cType: ClassType, mName: String): GrowableArray { let startClassId = if (cType.genericSource != null) (cType.genericSource as ClassType).id else cType.id; if (let (true, cache) = this.implementingMethodsCache.get(startClassId)) { if (let (true, cached) = cache.get(mName)) { return cached; } } let methods = new Array(); let seenSigs = new Set(); var curr: ClassType | null = cType; while (curr != null) { let ct = curr; for (let decl in this.#declarationBodies(ct)) { let model = decl.model; let body = decl.body; for (let member in body) { if (member is MethodDefinition) { if (member.isAbstract) { continue; } let name = getMethodName(model, member); if (matchMemberName(name, mName)) { let mType = model.getNodeType(member); if (mType is FunctionType) { let sigKey = (if (member.isStatic) "static#" else "") + getSignatureKey(mType); if (!seenSigs.has(sigKey)) { methods.push(member); seenSigs.add(sigKey); } } } } } } curr = ct.superType; } if (!this.implementingMethodsCache.has(startClassId)) { this.implementingMethodsCache[startClassId] = new Map>(); } this.implementingMethodsCache[startClassId][mName] = methods; return methods; } findImplementingField(cType: ClassType, fName: String): FieldDefinition | null { let startClassId = if (cType.genericSource != null) (cType.genericSource as ClassType).id else cType.id; if (let (true, nulls) = this.implementingFieldNulls.get(startClassId)) { if (nulls.has(fName)) { return null; } } if (let (true, cache) = this.implementingFieldCache.get(startClassId)) { if (let (true, cached) = cache.get(fName)) { return cached; } } var curr: ClassType | null = cType; while (curr != null) { let ct = curr; for (let decl in this.#declarationBodies(ct)) { let model = decl.model; let body = decl.body; for (let member in body) { if (member is FieldDefinition) { if (member.isAbstract) { continue; } let name = memberKeyOf(model, member.name as Node); if (matchMemberName(name, fName)) { if (!this.implementingFieldCache.has(startClassId)) { this.implementingFieldCache[startClassId] = new Map(); } this.implementingFieldCache[startClassId][fName] = member; return member; } } } } curr = ct.superType; } if (!this.implementingFieldNulls.has(startClassId)) { this.implementingFieldNulls[startClassId] = new Set(); } this.implementingFieldNulls[startClassId].add(fName); return null; } findImplementingAccessor(cType: ClassType, accName: String): AccessorDeclaration | null { let startClassId = if (cType.genericSource != null) (cType.genericSource as ClassType).id else cType.id; if (let (true, nulls) = this.implementingAccessorNulls.get(startClassId)) { if (nulls.has(accName)) { return null; } } if (let (true, cache) = this.implementingAccessorCache.get(startClassId)) { if (let (true, cached) = cache.get(accName)) { return cached; } } var curr: ClassType | null = cType; while (curr != null) { let ct = curr; for (let decl in this.#declarationBodies(ct)) { let model = decl.model; let body = decl.body; for (let member in body) { if (member is AccessorDeclaration) { let name = getAccessorName(model, member); if (accName.length > 4 && member.getter != null && accName.sliceBytes(0, 4) == "get#") { let targetProp = accName.sliceBytes(4, accName.length); if (matchMemberName(name, targetProp)) { if (!this.implementingAccessorCache.has(startClassId)) { this.implementingAccessorCache[startClassId] = new Map(); } this.implementingAccessorCache[startClassId][accName] = member; return member; } } if (accName.length > 4 && member.setter != null && accName.sliceBytes(0, 4) == "set#") { let targetProp = accName.sliceBytes(4, accName.length); if (matchMemberName(name, targetProp)) { if (!this.implementingAccessorCache.has(startClassId)) { this.implementingAccessorCache[startClassId] = new Map(); } this.implementingAccessorCache[startClassId][accName] = member; return member; } } } } } curr = ct.superType; } if (!this.implementingAccessorNulls.has(startClassId)) { this.implementingAccessorNulls[startClassId] = new Set(); } this.implementingAccessorNulls[startClassId].add(accName); return null; } findImplementingFields(cType: ClassType, fName: String): GrowableArray { let fields = new Array(); var seenStatic = false; var seenInstance = false; var curr: ClassType | null = cType; while (curr != null && (!seenStatic || !seenInstance)) { let ct = curr; for (let decl in this.#declarationBodies(ct)) { let model = decl.model; let body = decl.body; for (let member in body) { if (member is FieldDefinition) { if (member.isAbstract) { continue; } if (member.isStatic && seenStatic) { continue; } if (!member.isStatic && seenInstance) { continue; } let name = memberKeyOf(model, member.name as Node); if (matchMemberName(name, fName)) { fields.push(member); if (member.isStatic) { seenStatic = true; } else { seenInstance = true; } } } } } curr = ct.superType; } return fields; } findImplementingAccessors(cType: ClassType, accName: String): GrowableArray { let accessors = new Array(); // Only an accessor slot's name, `get#x` or `set#x`, names an // accessor. Member dependency records ask with method names too, // and resolving every accessor's name to answer them was most of // what a traversal cost. if (accName.length <= 4) { return accessors; } let wantsGetter = accName.startsWith("get#"); if (!wantsGetter && !accName.startsWith("set#")) { return accessors; } let targetProp = accName.sliceBytes(4, accName.length); var seenStatic = false; var seenInstance = false; var curr: ClassType | null = cType; while (curr != null && (!seenStatic || !seenInstance)) { let ct = curr; for (let decl in this.#declarationBodies(ct)) { let model = decl.model; let body = decl.body; for (let member in body) { if (member is AccessorDeclaration) { if (member.isStatic && seenStatic) { continue; } if (!member.isStatic && seenInstance) { continue; } let hasKind = if (wantsGetter) member.getter != null else member.setter != null; if (hasKind && matchMemberName(getAccessorName(model, member), targetProp)) { accessors.push(member); if (member.isStatic) { seenStatic = true; } else { seenInstance = true; } } } } } curr = ct.superType; } return accessors; } isSubclassOf(ct: ClassType, baseType: ClassType): boolean { let key = ((ct.id as i32) << 16) | (baseType.id as i32); if (let (true, cached) = this.subclassRelationCache.get(key)) { return cached; } let res = this.isSubclassOfDirect(ct, baseType); this.subclassRelationCache[key] = res; return res; } isSubclassOfDirect(ct: ClassType, baseType: ClassType): boolean { var curr: ClassType | null = ct; while (curr != null) { let currVal = curr; if (currVal.id == baseType.id) return true; if (currVal.genericSource != null && (currVal.genericSource as ClassType).id == baseType.id) return true; if (currVal.symbolId == baseType.symbolId) return true; if (currVal.genericSource != null && (currVal.genericSource as ClassType).symbolId == baseType.symbolId) return true; curr = currVal.superType; } return false; } collectAllBaseClassIds(ct: ClassType, list: HashSet): void { var curr: ClassType | null = ct; while (curr != null) { let currVal = curr; list.add(currVal.symbolId); let {genericSource} = currVal; if (genericSource != null) { list.add(genericSource.symbolId); } curr = currVal.superType; } } registerInstantiatedClass(ct: ClassType): void { let baseIds = new Set(); this.collectAllBaseClassIds(ct, baseIds); for (let baseId in baseIds) { if (!this.subclassesByBaseId.has(baseId)) { this.subclassesByBaseId[baseId] = new Array(); } this.subclassesByBaseId[baseId].push(ct); } } findInstantiatedSubclasses(baseType: ClassType): GrowableArray { let baseSymId = baseType.symbolId; if (let (true, list) = this.subclassesByBaseId.get(baseSymId)) { return list; } return new Array(); } collectAllImplementedInterfaces(ct: ClassType): GrowableArray { let list = new Array(); let seen = new Map(); let ctParams = getClassTypeParameters(ct); for (let iface in ct.implementsList) { let resolved = substituteTypeParamsInCodegen(this.wasm, ctParams, ct.typeArguments, iface) as InterfaceType; this.addInterfaceToTransitiveList(resolved, list, seen); } var curr = ct.superType; while (curr != null) { let superCt = curr; let superCtParams = getClassTypeParameters(superCt); for (let iface in superCt.implementsList) { let resolved = substituteTypeParamsInCodegen(this.wasm, superCtParams, superCt.typeArguments, iface) as InterfaceType; this.addInterfaceToTransitiveList(resolved, list, seen); } curr = superCt.superType; } return list; } addInterfaceToTransitiveList(it: InterfaceType, list: GrowableArray, seen: HashMap): void { let key = getInterfaceKey(it); if (!seen.has(key)) { seen[key] = true; list.push(it); for (let ext in it.extendsList) { let resolvedExt = substituteTypeParamsInCodegen(this.wasm, getInterfaceTypeParameters(it), it.typeArguments, ext) as InterfaceType; this.addInterfaceToTransitiveList(resolvedExt, list, seen); } } } } function matchMemberName(name: String, target: String): boolean { if (name == target) { return true; } if (name.length > 0 && name.sliceBytes(0, 1) == ":") { return name.sliceBytes(1, name.length) == target; } return false; } function getMethodName(model: SemanticModel, md: MethodDefinition): String { return memberKeyOf(model, md.name as Node); } function getAccessorName(model: SemanticModel, acc: AccessorDeclaration): String { return memberKeyOf(model, acc.name as Node); } function collectMixinSymbolIds( program: Program, model: SemanticModel, mixinAnns: GrowableArray | null, seenIds: HashMap ): void { if (mixinAnns == null) { return; } for (let ann in mixinAnns) { let sym = model.resolve(ann); if (sym != null) { let id = sym.id; if (!seenIds.has(id)) { seenIds[id] = true; let mt = model.getBindingType(sym); if (mt is MixinType) { let md = findMixinDeclaration(program, mt); if (md != null) { collectMixinSymbolIds(program, model, md.mixins, seenIds); } } } } } } /** One declaration's member list, with the model that checked it. */ final class DeclarationBody { model: SemanticModel; body: GrowableArray; new(this.model, this.body); }