| // Copyright (c) 2022, the Dart project authors. Please see the AUTHORS file | |
| // for details. All rights reserved. Use of this source code is governed by a | |
| // BSD-style license that can be found in the LICENSE file. | |
| import 'dart:math' show min; | |
| import 'package:dart2wasm/class_info.dart'; | |
| import 'package:dart2wasm/param_info.dart'; | |
| import 'package:dart2wasm/reference_extensions.dart'; | |
| import 'package:dart2wasm/translator.dart'; | |
| import 'package:kernel/ast.dart'; | |
| import 'package:vm/metadata/procedure_attributes.dart'; | |
| import 'package:vm/metadata/table_selector.dart'; | |
| import 'package:wasm_builder/wasm_builder.dart' as w; | |
| /// Information for a dispatch table selector. | |
| /// | |
| /// A selector encapsulates information to generate code that selects the right | |
| /// member (method, getter, setter) implementation in an instance invocation, | |
| /// from the dispatch table. Dispatch table is generated by [DispatchTable]. | |
| /// | |
| /// Target of a selector is a method, getter, or setter [Reference]. A target | |
| /// does not have to correspond to a user-written Dart member, it can be for a | |
| /// generated one. For example, for torn-off methods, we generate a [Reference] | |
| /// for the tear-off getter a selector for it. | |
| class SelectorInfo { | |
| final Translator translator; | |
| /// Unique ID of the selector. | |
| final int id; | |
| /// Number of use sites of the selector. | |
| final int callCount; | |
| /// Least upper bound of [ParameterInfo]s of all targets. | |
| final ParameterInfo paramInfo; | |
| /// Is this an implicit or explicit setter? | |
| final bool isSetter; | |
| /// Does this method have any tear-off uses? | |
| bool hasTearOffUses = false; | |
| /// Maps class IDs to the selector's member in the class. The member can be | |
| /// abstract. | |
| final Map<int, Reference> targets = {}; | |
| /// Wasm function type for the selector. | |
| /// | |
| /// This should be read after all targets have been added to the selector. | |
| late final w.FunctionType signature = _computeSignature(); | |
| /// IDs of classes that implement the member. This does not include abstract | |
| /// classes. | |
| late final List<int> classIds; | |
| /// Number of non-abstract references in [targets]. | |
| late final int targetCount; | |
| /// When [targetCount] is 1, this holds the only non-abstract target of the | |
| /// selector. | |
| late final Reference? singularTarget; | |
| /// Offset of the selector in the dispatch table. | |
| /// | |
| /// For a class in [targets], `class ID + offset` gives the offset of the | |
| /// class member for this selector. | |
| int? offset; | |
| w.ModuleBuilder get m => translator.m; | |
| /// The selector's member's name. | |
| String get name => paramInfo.member!.name.text; | |
| SelectorInfo._(this.translator, this.id, this.callCount, this.paramInfo, | |
| {required this.isSetter}); | |
| /// Compute the signature for the functions implementing members targeted by | |
| /// this selector. | |
| /// | |
| /// When the selector has multiple targets, the type of each parameter/return | |
| /// is the upper bound across all targets, such that all targets have the | |
| /// same signature, and the actual representation types of the parameters and | |
| /// returns are subtypes (resp. supertypes) of the types in the signature. | |
| w.FunctionType _computeSignature() { | |
| var nameIndex = paramInfo.nameIndex; | |
| final int returnCount = isSetter ? 0 : 1; | |
| List<Set<w.ValueType>> inputSets = | |
| List.generate(1 + paramInfo.paramCount, (_) => {}); | |
| List<Set<w.ValueType>> outputSets = List.generate(returnCount, (_) => {}); | |
| List<bool> ensureBoxed = List.filled(1 + paramInfo.paramCount, false); | |
| targets.forEach((classId, target) { | |
| Member member = target.asMember; | |
| DartType receiver = | |
| InterfaceType(member.enclosingClass!, Nullability.nonNullable); | |
| List<DartType> positional; | |
| Map<String, DartType> named; | |
| List<DartType> returns; | |
| if (member is Field) { | |
| if (target.isImplicitGetter) { | |
| positional = const []; | |
| named = const {}; | |
| returns = [member.getterType]; | |
| } else { | |
| positional = [member.setterType]; | |
| named = const {}; | |
| returns = const []; | |
| } | |
| } else { | |
| FunctionNode function = member.function!; | |
| if (target.isTearOffReference) { | |
| positional = const []; | |
| named = const {}; | |
| returns = [function.computeFunctionType(Nullability.nonNullable)]; | |
| } else { | |
| DartType typeForParam(VariableDeclaration param, int index) { | |
| if (param.isCovariantByClass) { | |
| // The type argument of a static type is not required to conform | |
| // to the bounds of the type variable. Thus, any object can be | |
| // passed to a parameter that is covariant by class. | |
| return translator.coreTypes.objectNullableRawType; | |
| } | |
| if (param.isCovariantByDeclaration) { | |
| if (hasTearOffUses) { | |
| // The type of a covariant parameter in the runtime function | |
| // type of a tear-off is always `Object?`. Thus, if the method | |
| // has any tear-off uses, any object could be passed into the | |
| // parameter. | |
| return translator.coreTypes.objectNullableRawType; | |
| } | |
| if (!translator.options.omitTypeChecks) { | |
| // A runtime type check of the parameter will be generated. | |
| // The value therefore must be boxed. | |
| ensureBoxed[index] = true; | |
| } | |
| } | |
| return param.type; | |
| } | |
| positional = [ | |
| for (int i = 0; i < function.positionalParameters.length; i++) | |
| typeForParam(function.positionalParameters[i], 1 + i) | |
| ]; | |
| named = { | |
| for (VariableDeclaration param in function.namedParameters) | |
| param.name!: typeForParam(param, 1 + nameIndex[param.name!]!) | |
| }; | |
| returns = target.isSetter ? const [] : [function.returnType]; | |
| } | |
| } | |
| assert(returns.length <= outputSets.length); | |
| inputSets[0].add(translator.translateType(receiver)); | |
| ensureBoxed[0] = member.enclosingClass != translator.ffiPointerClass; | |
| for (int i = 0; i < positional.length; i++) { | |
| DartType type = positional[i]; | |
| inputSets[1 + i].add(translator.translateType(type)); | |
| ensureBoxed[1 + i] |= | |
| paramInfo.positional[i] == ParameterInfo.defaultValueSentinel; | |
| } | |
| for (String name in named.keys) { | |
| int i = nameIndex[name]!; | |
| DartType type = named[name]!; | |
| inputSets[1 + i].add(translator.translateType(type)); | |
| ensureBoxed[1 + i] |= | |
| paramInfo.named[name] == ParameterInfo.defaultValueSentinel; | |
| } | |
| for (int i = 0; i < returnCount; i++) { | |
| if (i < returns.length) { | |
| DartType type = returns[i]; | |
| outputSets[i].add(translator.translateType(type)); | |
| } else { | |
| outputSets[i].add(translator.topInfo.nullableType); | |
| } | |
| } | |
| }); | |
| List<w.ValueType> typeParameters = List.filled(paramInfo.typeParamCount, | |
| translator.classInfo[translator.typeClass]!.nonNullableType); | |
| List<w.ValueType> inputs = List.generate(inputSets.length, | |
| (i) => _upperBound(inputSets[i], ensureBoxed: ensureBoxed[i])); | |
| if (name == '==') { | |
| // == can't be called with null | |
| inputs[1] = inputs[1].withNullability(false); | |
| } | |
| List<w.ValueType> outputs = List.generate(outputSets.length, | |
| (i) => _upperBound(outputSets[i], ensureBoxed: false)); | |
| return m.types.defineFunction( | |
| [inputs[0], ...typeParameters, ...inputs.sublist(1)], outputs); | |
| } | |
| w.ValueType _upperBound(Set<w.ValueType> types, {required bool ensureBoxed}) { | |
| if (!ensureBoxed && types.length == 1 && types.single.isPrimitive) { | |
| // Unboxed primitive. | |
| return types.single; | |
| } | |
| final bool nullable = types.any((type) => type.nullable); | |
| int minDepth = 999999999; | |
| Set<w.DefType> heapTypes = types | |
| .where((type) => type is! w.RefType || type.heapType is w.DefType) | |
| .map((type) { | |
| w.DefType def = type is w.RefType | |
| ? type.heapType as w.DefType | |
| : translator.classInfo[translator.boxedClasses[type]!]!.struct; | |
| minDepth = min(minDepth, def.depth); | |
| return def; | |
| }).toSet(); | |
| if (heapTypes.isEmpty) { | |
| // Only abstract heap types. | |
| Set<w.HeapType> heapTypes = | |
| types.map((type) => (type as w.RefType).heapType).toSet(); | |
| return w.RefType(heapTypes.single, nullable: nullable); | |
| } | |
| int targetDepth = minDepth; | |
| while (heapTypes.length > 1) { | |
| heapTypes = heapTypes.map((s) { | |
| while (s.depth > targetDepth) { | |
| s = s.superType!; | |
| } | |
| return s; | |
| }).toSet(); | |
| targetDepth -= 1; | |
| } | |
| return w.RefType.def(heapTypes.single, nullable: nullable); | |
| } | |
| } | |
| /// Builds the dispatch table for member calls. | |
| class DispatchTable { | |
| final Translator translator; | |
| final List<TableSelectorInfo> _selectorMetadata; | |
| final Map<TreeNode, ProcedureAttributesMetadata> _procedureAttributeMetadata; | |
| /// Maps selector IDs to selectors. | |
| final Map<int, SelectorInfo> _selectorInfo = {}; | |
| /// Maps member names to getter selectors with the same member name. | |
| final Map<String, Set<SelectorInfo>> _dynamicGetters = {}; | |
| /// Maps member names to setter selectors with the same member name. | |
| final Map<String, Set<SelectorInfo>> _dynamicSetters = {}; | |
| /// Maps member names to method selectors with the same member name. | |
| final Map<String, Set<SelectorInfo>> _dynamicMethods = {}; | |
| /// Contents of [wasmTable]. For a selector with ID S and a target class of | |
| /// the selector with ID C, `table[S + C]` gives the reference to the class | |
| /// member for the selector. | |
| late final List<Reference?> _table; | |
| /// The Wasm table for the dispatch table. | |
| late final w.TableBuilder wasmTable; | |
| w.ModuleBuilder get m => translator.m; | |
| DispatchTable(this.translator) | |
| : _selectorMetadata = | |
| (translator.component.metadata["vm.table-selector.metadata"] | |
| as TableSelectorMetadataRepository) | |
| .mapping[translator.component]! | |
| .selectors, | |
| _procedureAttributeMetadata = | |
| (translator.component.metadata["vm.procedure-attributes.metadata"] | |
| as ProcedureAttributesMetadataRepository) | |
| .mapping; | |
| SelectorInfo selectorForTarget(Reference target) { | |
| Member member = target.asMember; | |
| bool isGetter = target.isGetter || target.isTearOffReference; | |
| ProcedureAttributesMetadata metadata = _procedureAttributeMetadata[member]!; | |
| int selectorId = isGetter | |
| ? metadata.getterSelectorId | |
| : metadata.methodOrSetterSelectorId; | |
| return _selectorInfo[selectorId]!; | |
| } | |
| SelectorInfo _createSelectorForTarget(Reference target) { | |
| Member member = target.asMember; | |
| bool isGetter = target.isGetter || target.isTearOffReference; | |
| bool isSetter = target.isSetter; | |
| ProcedureAttributesMetadata metadata = _procedureAttributeMetadata[member]!; | |
| int selectorId = isGetter | |
| ? metadata.getterSelectorId | |
| : metadata.methodOrSetterSelectorId; | |
| ParameterInfo paramInfo = ParameterInfo.fromMember(target); | |
| // _WasmBase and its subclass methods cannot be called dynamically | |
| final cls = member.enclosingClass; | |
| final isWasmType = cls != null && translator.isWasmType(cls); | |
| final calledDynamically = !isWasmType && | |
| (metadata.getterCalledDynamically || | |
| metadata.methodOrSetterCalledDynamically || | |
| member.name.text == "call"); | |
| final selector = _selectorInfo.putIfAbsent( | |
| selectorId, | |
| () => SelectorInfo._(translator, selectorId, | |
| _selectorMetadata[selectorId].callCount, paramInfo, | |
| isSetter: isSetter)); | |
| assert(selector.isSetter == isSetter); | |
| selector.hasTearOffUses |= metadata.hasTearOffUses; | |
| selector.paramInfo.merge(paramInfo); | |
| if (calledDynamically) { | |
| if (isGetter) { | |
| (_dynamicGetters[member.name.text] ??= {}).add(selector); | |
| } else if (isSetter) { | |
| (_dynamicSetters[member.name.text] ??= {}).add(selector); | |
| } else { | |
| (_dynamicMethods[member.name.text] ??= {}).add(selector); | |
| } | |
| } | |
| return selector; | |
| } | |
| /// Get selectors for getters and tear-offs with the given name. | |
| Iterable<SelectorInfo> dynamicGetterSelectors(String memberName) => | |
| _dynamicGetters[memberName] ?? Iterable.empty(); | |
| /// Get selectors for setters with the given name. | |
| Iterable<SelectorInfo> dynamicSetterSelectors(String memberName) => | |
| _dynamicSetters[memberName] ?? Iterable.empty(); | |
| /// Get selectors for methods with the given name. | |
| Iterable<SelectorInfo> dynamicMethodSelectors(String memberName) => | |
| _dynamicMethods[memberName] ?? Iterable.empty(); | |
| void build() { | |
| // Collect class/selector combinations | |
| // Maps class IDs to selector IDs of the class | |
| List<Set<int>> selectorsInClass = []; | |
| // Add classes to selector targets for their members | |
| for (ClassInfo info in translator.classes) { | |
| Set<int> selectorIds = {}; | |
| final ClassInfo? superInfo = info.superInfo; | |
| // Add the class to its inherited members' selectors. Skip `_WasmBase`: | |
| // it's defined as a Dart class (in `dart._wasm` library) but it's special | |
| // and does not inherit from `Object`. | |
| if (superInfo != null && info.cls != translator.wasmTypesBaseClass) { | |
| int superId = superInfo.classId; | |
| selectorIds = Set.of(selectorsInClass[superId]); | |
| for (int selectorId in selectorIds) { | |
| SelectorInfo selector = _selectorInfo[selectorId]!; | |
| selector.targets[info.classId] = selector.targets[superId]!; | |
| } | |
| } | |
| /// Add a method (or getter, setter) of the current class ([info]) to | |
| /// [reference]'s selector's targets. | |
| /// | |
| /// Because we visit a superclass before its subclasses, if the class | |
| /// inherits [reference], then the selector will already have a target | |
| /// for the class. Override that target if [reference] is a not abstract. | |
| /// If it's abstract, then the superclass's method will be called, so do | |
| /// not update the target. | |
| void addMember(Reference reference) { | |
| SelectorInfo selector = _createSelectorForTarget(reference); | |
| if (reference.asMember.isAbstract) { | |
| // Reference is abstract, do not override inherited concrete member | |
| selector.targets[info.classId] ??= reference; | |
| } else { | |
| // Reference is concrete, override inherited member | |
| selector.targets[info.classId] = reference; | |
| } | |
| selectorIds.add(selector.id); | |
| } | |
| // Add the class to its non-static members' selectors. If `info.cls` is | |
| // `null`, that means [info] represents the `#Top` type, which is not a | |
| // Dart class but has the members of `Object`. | |
| for (Member member | |
| in info.cls?.members ?? translator.coreTypes.objectClass.members) { | |
| // Skip static members | |
| if (!member.isInstanceMember) { | |
| continue; | |
| } | |
| if (member is Field) { | |
| addMember(member.getterReference); | |
| if (member.hasSetter) addMember(member.setterReference!); | |
| } else if (member is Procedure) { | |
| addMember(member.reference); | |
| // `hasTearOffUses` can be true for operators as well, even though | |
| // it's not possible to tear-off an operator. (no syntax for it) | |
| if (member.kind == ProcedureKind.Method && | |
| _procedureAttributeMetadata[member]!.hasTearOffUses) { | |
| addMember(member.tearOffReference); | |
| } | |
| } | |
| } | |
| selectorsInClass.add(selectorIds); | |
| } | |
| // Build lists of class IDs and count targets | |
| for (SelectorInfo selector in _selectorInfo.values) { | |
| selector.classIds = selector.targets.keys | |
| .where((classId) => | |
| !(translator.classes[classId].cls?.isAbstract ?? true)) | |
| .toList() | |
| ..sort(); | |
| Set<Reference> targets = | |
| selector.targets.values.where((t) => !t.asMember.isAbstract).toSet(); | |
| selector.targetCount = targets.length; | |
| selector.singularTarget = targets.length == 1 ? targets.single : null; | |
| } | |
| // Assign selector offsets | |
| /// Whether the selector will be used in an instance invocation. | |
| /// | |
| /// If not, then we don't add the selector to the dispatch table and don't | |
| /// assign it a dispatch table offset. | |
| /// | |
| /// Special case for `objectNoSuchMethod`: we introduce instance | |
| /// invocations of `objectNoSuchMethod` in dynamic calls, so keep it alive | |
| /// even if there was no references to it from the Dart code. | |
| bool needsDispatch(SelectorInfo selector) => | |
| (selector.callCount > 0 && selector.targetCount > 1) || | |
| (selector.paramInfo.member! == translator.objectNoSuchMethod); | |
| List<SelectorInfo> selectors = | |
| _selectorInfo.values.where(needsDispatch).toList(); | |
| // Sort the selectors based on number of targets and number of use sites. | |
| // This is a heuristic to keep the table small. | |
| // | |
| // Place selectors with more targets first as they are less likely to fit | |
| // into the gaps left by selectors placed earlier. | |
| // | |
| // Among the selectors with approximately same number of targets, place | |
| // more used ones first, as the smaller selector offset will have a smaller | |
| // instruction encoding. | |
| int selectorSortWeight(SelectorInfo selector) => | |
| selector.classIds.length * 10 + selector.callCount; | |
| selectors.sort((a, b) => selectorSortWeight(b) - selectorSortWeight(a)); | |
| int firstAvailable = 0; | |
| _table = []; | |
| bool first = true; | |
| for (SelectorInfo selector in selectors) { | |
| int offset = first ? 0 : firstAvailable - selector.classIds.first; | |
| first = false; | |
| bool fits; | |
| do { | |
| fits = true; | |
| for (int classId in selector.classIds) { | |
| int entry = offset + classId; | |
| if (entry >= _table.length) { | |
| // Fits | |
| break; | |
| } | |
| if (_table[entry] != null) { | |
| fits = false; | |
| break; | |
| } | |
| } | |
| if (!fits) offset++; | |
| } while (!fits); | |
| selector.offset = offset; | |
| for (int classId in selector.classIds) { | |
| int entry = offset + classId; | |
| while (_table.length <= entry) { | |
| _table.add(null); | |
| } | |
| assert(_table[entry] == null); | |
| _table[entry] = selector.targets[classId]; | |
| } | |
| while (firstAvailable < _table.length && _table[firstAvailable] != null) { | |
| firstAvailable++; | |
| } | |
| } | |
| wasmTable = m.tables.define(w.RefType.func(nullable: true), _table.length); | |
| } | |
| void output() { | |
| for (int i = 0; i < _table.length; i++) { | |
| Reference? target = _table[i]; | |
| if (target != null) { | |
| w.BaseFunction? fun = translator.functions.getExistingFunction(target); | |
| if (fun != null) { | |
| wasmTable.setElement(i, fun); | |
| } | |
| } | |
| } | |
| } | |
| } |