pkg/dart2wasm/lib/dispatch_table.dart

// 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: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;

import 'class_info.dart';
import 'dynamic_modules.dart';
import 'param_info.dart';
import 'reference_extensions.dart';
import 'translator.dart';

typedef ModuleSelectorTargets = ({
  SelectorTargets? checked,
  SelectorTargets? unchecked,
  SelectorTargets? normal
});

/// 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;

  // The ID of the selector in the main module. Only populated for dynamic
  // modules.
  final Map<Member, int> _mainModuleIds = {};

  /// 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;

  /// Whether we create multiple entry points for the selector.
  ///
  /// We create multiple entry points when any implementation of this selector
  /// performs type checks on the passed arguments.
  bool useMultipleEntryPoints = false;

  bool isDynamicModuleOverrideable = false;
  bool isDynamicModuleCallable = false;

  /// 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();

  /// The selector's member's name.
  final String name;

  /// Whether the selector is for `Object.noSuchMethod`. We introduce instance
  /// invocations of `noSuchMethod` in dynamic calls, so we always add
  /// `noSuchMethod` overrides to the dispatch table.
  final bool isNoSuchMethod;

  late final ModuleSelectorTargets _mainModuleTargets;
  late final ModuleSelectorTargets _dynamicModuleTargets;

  SelectorTargets targets(
      {required bool unchecked, required bool dynamicModule}) {
    final selectorTargets =
        dynamicModule ? _dynamicModuleTargets : _mainModuleTargets;
    if (useMultipleEntryPoints) {
      assert(selectorTargets.checked!.targetRanges.length ==
          selectorTargets.unchecked!.targetRanges.length);
      return (unchecked ? selectorTargets.unchecked : selectorTargets.checked)!;
    }
    assert(
        selectorTargets.checked == null && selectorTargets.unchecked == null);
    return selectorTargets.normal!;
  }

  SelectorInfo._(
    this.translator,
    this.id,
    this.name,
    this.callCount,
    this.paramInfo, {
    required this.isSetter,
    required this.isNoSuchMethod,
  });

  int mainModuleIdForTarget(Member member) => _mainModuleIds[member]!;

  String entryPointName(bool unchecked) {
    if (!useMultipleEntryPoints) return name;
    return '$name (${unchecked ? 'unchecked' : 'checked'})';
  }

  /// 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);
    Iterable<({Reference target, Range range})> targetRanges =
        targets(unchecked: false, dynamicModule: false).targetRanges;
    if (translator.isDynamicModule) {
      targetRanges = targetRanges.followedBy(
          targets(unchecked: false, dynamicModule: true).targetRanges);
    }
    for (final (range: _, :target) in targetRanges) {
      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 = [translator.typeOfReturnValue(member)];
        } 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 {
          final typeForParam = translator.typeOfParameterVariable;
          positional = [
            for (int i = 0; i < function.positionalParameters.length; i++)
              typeForParam(function.positionalParameters[i],
                  i < function.requiredParameterCount)
          ];
          named = {
            for (VariableDeclaration param in function.namedParameters)
              param.name!: typeForParam(param, param.isRequired)
          };
          returns = target.isSetter
              ? const []
              : [translator.typeOfReturnValue(member)];
        }
      }
      assert(returns.length <= outputSets.length);
      inputSets[0].add(translator.translateType(receiver));
      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.translateReturnType(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 translator.typesBuilder.defineFunction(
        [inputs[0], ...typeParameters, ...inputs.sublist(1)], outputs);
  }

  w.ValueType _upperBound(Set<w.ValueType> types, {required bool ensureBoxed}) {
    if (types.isEmpty) {
      // This happens if the selector doesn't have any targets. Any call site of
      // such a selector is unreachable. Though such call sites still have to
      // evaluate receiver and arguments. Doing so requires the signature. So we
      // create a dummy signature with top types.
      return translator.topInfo.nullableType;
    }
    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);
  }

  late final Set<Reference> _targetSet = useMultipleEntryPoints
      ? {
          ..._mainModuleTargets.checked!._targetSet,
          ..._mainModuleTargets.unchecked!._targetSet,
          if (translator.isDynamicModule) ...{
            ..._dynamicModuleTargets.checked!._targetSet,
            ..._dynamicModuleTargets.unchecked!._targetSet,
          }
        }
      : {
          ..._mainModuleTargets.normal!._targetSet,
          if (translator.isDynamicModule)
            ..._dynamicModuleTargets.normal!._targetSet
        };

  bool containsTarget(Reference target) => _targetSet.contains(target);
}

class SelectorTargets {
  /// Targets for all concrete classes implementing this selector.
  ///
  /// As a subclass hierarchy often inherits the same target, we associate the
  /// target with a range of class ids. The ranges are non-empty,
  /// non-overlapping and sorted in ascending order.
  final List<({Range range, Reference target})> targetRanges;

  /// Targets that a interface call will check & directly call before falling
  /// back to dispatch table calls.
  ///
  /// The targets in here are mainly the ones annotated with
  /// `@pragma('wasm:static-dispatch')`. The compiler will generate then code
  /// that first checks the receiver for those targets directly and issue direct
  /// calls before falling back to dispatch table calls.
  final List<({Range range, Reference target})> staticDispatchRanges;

  /// Offset of the selector in the dispatch table.
  ///
  /// For a class in [targetRanges], `class ID + offset` gives the offset of the
  /// class member for this selector.
  int? offset;

  SelectorTargets(this.targetRanges, this.staticDispatchRanges);

  late final Set<Reference> _targetSet =
      targetRanges.map((e) => e.target).toSet();
}

/// Builds the dispatch table for member calls.
class DispatchTable {
  static const _functionType = w.RefType.func(nullable: true);

  final Translator translator;
  final List<TableSelectorInfo> _selectorMetadata;

  /// 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 [_definedWasmTable]. 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;
  List<Reference?>? _dynamicModuleTable;

  late final w.TableBuilder _definedWasmTable;
  final WasmTableImporter _importedWasmTables;

  w.TableBuilder? _dynamicModuleDefinedWasmTable;
  w.Table get dynamicModuleDefinedWasmTable => _dynamicModuleDefinedWasmTable!;

  /// The Wasm table for the dispatch table.
  w.Table getWasmTable(w.ModuleBuilder module) =>
      _importedWasmTables.get(_definedWasmTable, module);

  DispatchTable(this.translator)
      : _selectorMetadata =
            (translator.component.metadata["vm.table-selector.metadata"]
                    as TableSelectorMetadataRepository)
                .mapping[translator.component]!
                .selectors,
        _importedWasmTables = WasmTableImporter(translator, 'dispatch');

  SelectorInfo selectorForTarget(Reference target) {
    Member member = target.asMember;
    bool isGetter = target.isGetter || target.isTearOffReference;
    ProcedureAttributesMetadata metadata =
        translator.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 =
        translator.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 isDynamicModuleOverrideable =
        member.isDynamicModuleOverrideable(translator.coreTypes);

    final selector = _selectorInfo.putIfAbsent(
        selectorId,
        () => SelectorInfo._(translator, selectorId, member.name.text,
            _selectorMetadata[selectorId].callCount, paramInfo,
            isSetter: isSetter,
            isNoSuchMethod: member == translator.objectNoSuchMethod));
    assert(selector.isSetter == isSetter);
    final useMultipleEntryPoints = !member.isAbstract &&
        !member.isExternal &&
        !target.isGetter &&
        !target.isTearOffReference &&
        translator.needToCheckTypesFor(member);
    selector.useMultipleEntryPoints |= useMultipleEntryPoints;
    selector.isDynamicModuleOverrideable |= isDynamicModuleOverrideable;
    selector.isDynamicModuleCallable |=
        member.isDynamicModuleCallable(translator.coreTypes);

    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);
      }
    }

    final mainModuleIds = translator.dynamicModuleInfo?.selectorIds[member];
    if (mainModuleIds != null) {
      selector._mainModuleIds[member] =
          isGetter ? mainModuleIds.$1 : mainModuleIds.$2;
    } else {
      selector._mainModuleIds[member] = selectorId;
    }
    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 to selector IDs of the class
    final selectorsInClass = <Class, Map<SelectorInfo, Reference>>{};
    final staticDispatchPragmas = <Reference>{};

    // Add classes to selector targets for their members
    for (ClassInfo info in translator.classesSupersFirst) {
      final Class cls = info.cls ?? translator.coreTypes.objectClass;
      final Map<SelectorInfo, Reference> selectors;

      // 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`.
      final ClassInfo? superInfo = info.superInfo;
      if (superInfo == null || cls == translator.wasmTypesBaseClass) {
        selectors = {};
      } else {
        final Class superCls =
            superInfo.cls ?? translator.coreTypes.objectClass;
        selectors = Map.of(selectorsInClass[superCls]!);
      }

      /// 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, bool staticDispatch) {
        SelectorInfo selector = _createSelectorForTarget(reference);
        if (reference.asMember.isAbstract) {
          // Reference is abstract, do not override inherited concrete member
          selectors[selector] ??= reference;
        } else {
          // Reference is concrete, override inherited member
          selectors[selector] = reference;

          if (staticDispatch) staticDispatchPragmas.add(reference);
        }
      }

      // 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 cls.members) {
        // Skip static members
        if (!member.isInstanceMember) {
          continue;
        }
        final bool staticDispatch =
            translator.getPragma<bool>(member, 'wasm:static-dispatch', true) ??
                false;
        if (member is Field) {
          addMember(member.getterReference, staticDispatch);
          if (member.hasSetter) {
            final target = member.setterReference!;
            addMember(target, staticDispatch);
          }
        } else if (member is Procedure) {
          final target = member.reference;
          addMember(target, staticDispatch);
          final procedureMetadata =
              translator.procedureAttributeMetadata[member]!;
          // `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 &&
              (procedureMetadata.hasTearOffUses ||
                  // Only concrete members have 'hasTearOffUse' but for dynamic
                  // module compilations, there may be any concrete
                  // implementations yet. We check if the member is dynamically
                  // overrideable at the tearoff sites as they might not be
                  // tree-shaken. We still need a selector at the tearoff site.
                  (translator.dynamicModuleSupportEnabled &&
                      _selectorMetadata[
                              procedureMetadata.methodOrSetterSelectorId]
                          .tornOff))) {
            addMember(member.tearOffReference, staticDispatch);
          }
        }
      }
      selectorsInClass[cls] = selectors;
    }

    List<Reference?> processTargets(int start, int end, bool isDynamicModule) {
      final selectorTargets = <SelectorInfo, Map<int, Reference>>{};
      for (int classId = start; classId <= end; ++classId) {
        final cls = translator.classes[classId].cls;
        if (cls != null) {
          selectorsInClass[cls]!.forEach((selectorInfo, target) {
            if (!target.asMember.isAbstract) {
              selectorTargets.putIfAbsent(selectorInfo, () => {})[classId] =
                  target;
            }
          });
        }
      }

      selectorTargets
          .forEach((SelectorInfo selector, Map<int, Reference> targets) {
        final List<({Range range, Reference target})> ranges = targets.entries
            .map((entry) =>
                (range: Range(entry.key, entry.key), target: entry.value))
            .toList()
          ..sort((a, b) => a.range.start.compareTo(b.range.start));
        assert(ranges.isNotEmpty);
        int writeIndex = 0;
        for (int readIndex = 1; readIndex < ranges.length; ++readIndex) {
          final current = ranges[writeIndex];
          final next = ranges[readIndex];
          assert(next.range.length == 1);
          if ((current.range.end + 1) == next.range.start &&
              identical(current.target, next.target)) {
            ranges[writeIndex] = (
              range: Range(current.range.start, next.range.end),
              target: current.target
            );
          } else {
            ranges[++writeIndex] = next;
          }
        }
        ranges.length = writeIndex + 1;

        final staticDispatchRanges = selector.isDynamicModuleOverrideable
            ? const <({Range range, Reference target})>[]
            : (translator.options.polymorphicSpecialization ||
                    ranges.length == 1)
                ? ranges
                : ranges
                    .where(
                        (range) => staticDispatchPragmas.contains(range.target))
                    .toList();
        if (selector.useMultipleEntryPoints) {
          ({Range range, Reference target}) getChecked(
            ({Range range, Reference target}) targetRange,
            bool unchecked,
          ) =>
              (
                range: targetRange.range,
                target: translator.getFunctionEntry(targetRange.target,
                    uncheckedEntry: unchecked)
              );
          final checkedTargets = SelectorTargets(
            ranges.map((r) => getChecked(r, false)).toList(),
            staticDispatchRanges.map((r) => getChecked(r, false)).toList(),
          );
          final uncheckedTargets = SelectorTargets(
            ranges.map((r) => getChecked(r, true)).toList(),
            staticDispatchRanges.map((r) => getChecked(r, true)).toList(),
          );
          final targets = (
            normal: null,
            checked: checkedTargets,
            unchecked: uncheckedTargets
          );
          if (isDynamicModule) {
            selector._dynamicModuleTargets = targets;
          } else {
            selector._mainModuleTargets = targets;
          }
        } else {
          final normalTargets = SelectorTargets(ranges, staticDispatchRanges);
          final targets =
              (normal: normalTargets, checked: null, unchecked: null);
          if (isDynamicModule) {
            selector._dynamicModuleTargets = targets;
          } else {
            selector._mainModuleTargets = targets;
          }
        }
      });

      // Assign selector offsets

      bool isUsedViaDispatchTableCall(SelectorInfo selector) {
        // 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.
        if (selector.isNoSuchMethod) {
          return true;
        }
        if (selector.isDynamicModuleCallable) return true;

        if (selector.callCount == 0) {
          return false;
        }
        if (selector.isDynamicModuleOverrideable) return true;

        final targets =
            selector.targets(unchecked: false, dynamicModule: isDynamicModule);

        if (targets.targetRanges.length <= 1) return false;
        if (!isDynamicModule &&
            targets.staticDispatchRanges.length ==
                targets.targetRanges.length) {
          return false;
        }

        return true;
      }

      final List<SelectorInfo> selectors =
          selectorTargets.keys.where(isUsedViaDispatchTableCall).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) =>
          selectorTargets[selector]!.length * 10 + selector.callCount;

      selectors.sort((a, b) => selectorSortWeight(b) - selectorSortWeight(a));

      final rows = <Row<Reference>>[];
      for (final selector in selectors) {
        Row<Reference> buildRow(
            List<({Range range, Reference target})> targetRanges) {
          final rowValues = <({int index, Reference value})>[];
          for (final (:range, :target) in targetRanges) {
            for (int classId = range.start; classId <= range.end; ++classId) {
              final adjustedClassId = classId - start;
              rowValues.add((index: adjustedClassId, value: target));
            }
          }
          rowValues.sort((a, b) => a.index.compareTo(b.index));
          return Row(rowValues);
        }

        final selectorTargets = isDynamicModule
            ? selector._dynamicModuleTargets
            : selector._mainModuleTargets;

        if (selector.useMultipleEntryPoints) {
          rows.add(buildRow((selectorTargets.checked!.targetRanges)));
          rows.add(buildRow((selectorTargets.unchecked!.targetRanges)));
        } else {
          rows.add(buildRow((selectorTargets.normal!.targetRanges)));
        }
      }

      final table = buildRowDisplacementTable<Reference>(rows);

      int rowIndex = 0;
      for (final selector in selectors) {
        final selectorTargets = isDynamicModule
            ? selector._dynamicModuleTargets
            : selector._mainModuleTargets;
        if (selector.useMultipleEntryPoints) {
          selectorTargets.checked!.offset = rows[rowIndex++].offset;
          selectorTargets.unchecked!.offset = rows[rowIndex++].offset;
        } else {
          selectorTargets.normal!.offset = rows[rowIndex++].offset;
        }
      }

      _selectorInfo.forEach((_, selector) {
        if (!selectorTargets.containsKey(selector)) {
          // There are no concrete implementations for the given [selector].
          // But there may be an abstract interface target which is targed by a
          // call. In this case the call should be unreachable.
          final targets = selector.useMultipleEntryPoints
              ? (
                  normal: null,
                  checked: SelectorTargets(const [], const []),
                  unchecked: SelectorTargets(const [], const [])
                )
              : (
                  normal: SelectorTargets(const [], const []),
                  checked: null,
                  unchecked: null,
                );
          if (isDynamicModule) {
            selector._dynamicModuleTargets = targets;
          } else {
            selector._mainModuleTargets = targets;
          }
        }
      });

      return table;
    }

    table = processTargets(
        0, translator.classIdNumbering.maxConcreteClassId, false);

    _definedWasmTable =
        translator.mainModule.tables.define(_functionType, table.length);
    if (!translator.dynamicModuleSupportEnabled) {
      // Dynamic modules don't need direct access to the main module's table.
      // Accesses are routed through global dispatch function refs.
      for (final module in translator.modules) {
        // Ensure the dispatch table is imported into every module as the first
        // table.
        getWasmTable(module);
      }
    }

    if (translator.isDynamicModule) {
      _dynamicModuleTable = processTargets(
          translator.classIdNumbering.firstDynamicModuleClassId,
          translator.classIdNumbering.maxDynamicModuleConcreteClassId!,
          true);

      _dynamicModuleDefinedWasmTable = translator.dynamicModule.tables
          .define(_functionType, _dynamicModuleTable!.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);
        // Any call to the dispatch table is guaranteed to hit a target.
        //
        // If a target is in a deferred module and that deferred module hasn't
        // been loaded yet, then the entry is `null`.
        //
        // Though we can only hit a target if that target's class has been
        // allocated. In order for the class to be allocated, the deferred
        // module must've been loaded to call the constructor.
        if (fun != null) {
          final targetModule = translator.moduleForReference(target);
          if (targetModule == _definedWasmTable.enclosingModule) {
            _definedWasmTable.setElement(i, fun);
          } else {
            // This will generate the imported table if it doesn't already
            // exist.
            (getWasmTable(targetModule) as w.ImportedTable).setElements[i] =
                fun;
          }
        }
      }
    }
    final dynamicModuleDefinedWasmTable = _dynamicModuleDefinedWasmTable;
    if (dynamicModuleDefinedWasmTable != null) {
      final dynamicModuleTable = _dynamicModuleTable!;
      final targetModule = dynamicModuleDefinedWasmTable.enclosingModule;
      for (int i = 0; i < dynamicModuleTable.length; i++) {
        Reference? target = dynamicModuleTable[i];
        if (target != null) {
          w.BaseFunction? fun =
              translator.functions.getExistingFunction(target);
          if (fun != null) {
            if (fun.enclosingModule != targetModule) {
              if (target.asMember
                  .isDynamicModuleCallable(translator.coreTypes)) {
                fun = translator.functions.importFunctionToDynamicModule(fun);
              } else {
                continue;
              }
            }
            dynamicModuleDefinedWasmTable.setElement(i, fun);
          }
        }
      }
    }
  }
}

/// Build a row-displacement table based on fitting the [rows].
///
/// The returned list is the resulting row displacement table with `null`
/// entries representing unused space.
///
/// The offset of all [Row]s will be initialized.
List<V?> buildRowDisplacementTable<V extends Object>(List<Row<V>> rows,
    {int firstAvailable = 0}) {
  final table = <V?>[];
  for (final row in rows) {
    final values = row.values;
    int offset = firstAvailable - values.first.index;
    bool fits;
    do {
      fits = true;
      for (final value in values) {
        final int entry = offset + value.index;
        if (entry >= table.length) {
          // Fits
          break;
        }
        if (table[entry] != null) {
          fits = false;
          break;
        }
      }
      if (!fits) offset++;
    } while (!fits);
    row.offset = offset;
    for (final (:index, :value) in values) {
      final int tableIndex = offset + index;
      while (table.length <= tableIndex) {
        table.add(null);
      }
      assert(table[tableIndex] == null);
      table[tableIndex] = value;
    }
    while (firstAvailable < table.length && table[firstAvailable] != null) {
      firstAvailable++;
    }
  }
  return table;
}

class Row<V extends Object> {
  /// The values of the table row, represented sparsely as (index, value) tuples.
  final List<({int index, V value})> values;

  /// The given [values] must not be empty and should be sorted by index.
  Row(this.values) {
    assert(values.isNotEmpty);
    assert(() {
      int previous = values.first.index;
      for (final value in values.skip(1)) {
        if (value.index <= previous) return false;
        previous = value.index;
      }
      return true;
    }());
  }

  /// The selected offset of this row.
  late final int offset;

  int get width => values.last.index - values.first.index + 1;
  int get holes => width - values.length;
  int get density => (100 * values.length) ~/ width;
  int get sparsity => 100 - density;
}