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:kernel/names.dart';
import 'package:vm/metadata/procedure_attributes.dart';
import 'package:vm/metadata/table_selector.dart';
import 'package:vm/metadata/unreachable.dart';
import 'package:wasm_builder/wasm_builder.dart' as w;

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

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

  Translator get translator => dispatchTable.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.
  late final ParameterInfo paramInfo;

  /// Is this an implicit or explicit setter?
  final bool isSetter;

  /// Is this an index setter?
  final bool isIndexSetter;

  /// 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.
  late bool useMultipleEntryPoints;

  /// Whether the computation of [paramInfo] should enforce usage of sentinels
  /// for optional parameters.
  late bool _useSentinelForOptionalParameters;

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

  /// Whether callers should synthesize a `null` return value.
  ///
  /// Will be set during `_computeSignature`.
  late final bool synthesizeNullReturnValue;

  /// Whether the call will never return and callers can emit an
  /// `unreachable()` after the call.
  ///
  /// Will be set during `_computeSignature`.
  late final bool synthesizeNoReturn;

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

  SelectorTargets? _checked;
  SelectorTargets? _unchecked;
  SelectorTargets? _normal;

  /// The set of references we use to calculate the [paramInfo].
  final List<Reference> _references = [];

  SelectorTargets targets({required bool unchecked}) {
    if (useMultipleEntryPoints) {
      assert(
        _checked!.allTargetRanges.length == _unchecked!.allTargetRanges.length,
      );
      return unchecked ? _unchecked! : _checked!;
    }
    assert(_checked == null && _unchecked == null);
    return _normal!;
  }

  SelectorInfo._(
    this.dispatchTable,
    this.id,
    this.name,
    this.callCount, {
    required this.isSetter,
    required this.isIndexSetter,
  });

  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 bool isSetterOrIndexSetter = (isSetter || isIndexSetter);
    final int returnCount = isSetterOrIndexSetter ? 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,
    ).allTargetRanges;
    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 (Variable param in function.namedParameters)
              param.name!: typeForParam(param, param.isRequired),
          };
          returns = returnCount == 0
              ? 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.topType);
        }
      }
    }

    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],
        isReceiver: i == 0,
      ),
    );
    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),
    );
    if (outputs case [
      w.RefType(heapType: w.HeapType.none, nullable: final nullable),
    ]) {
      // All functions are guaranteed to return null or are unreachable.
      // => Prune signature to not return anything
      // => Tell callers to synthesize `null` or emit `unreachable`.
      outputs.clear();
      synthesizeNullReturnValue = nullable;
      synthesizeNoReturn = !nullable;
    } else {
      synthesizeNullReturnValue = isSetterOrIndexSetter;
      synthesizeNoReturn = false;
    }
    return translator.typesBuilder.defineFunction([
      inputs[0],
      ...typeParameters,
      ...inputs.sublist(1),
    ], outputs);
  }

  w.ValueType _upperBound(
    Set<w.ValueType> types, {
    required bool ensureBoxed,
    bool isReceiver = false,
  }) {
    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.topType;
    }
    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
      ? {..._checked!._targetSet, ..._unchecked!._targetSet}
      : _normal!._targetSet;

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

/// The set of possible targets for a given selector.
///
/// Will have an entry for all concrete classes (i.e. classes that are
/// allocated according to TFA) that respond to this selector.
///
/// We group (class-id, target) entries with consecutive class ids together if
/// they have the same entry.
///
/// A call site will dispatch in different ways to these targets:
///
///   * dynamic call sites will use a dynamic invocation forwarder function
///   which loads the receiver class id, switches on the class id and emit direct
///   calls to the targets (it uses [allTargetRanges] for this).
///
///   * an interface call will
///
///       * call the target directly if there's only one possible target
///
///       * call a polymorphic dispatcher function (if some of the targets are
///         marked via `@pragma('wasm:static-dispatch')` - which will emit
///         direct calls to targets based on the [staticDispatchRanges] and
///         fallback to the dispatch table call (if there's target ranges not
///         covered in [staticDispatchRanges])
///
///       * call the dispatch table entry (if there's more than one possible
///       target and [staticDispatchRanges] is empty)
///
///
/// * [_dispatchTableRanges] contains the target ranges we call indirectly
///   via the dispatch table
///
/// * [staticDispatchRanges] contains the target ranges we call directly via
///   class id checks + calls (directly or via [PolymorphicDispatchers])
///
class SelectorTargets {
  /// All targets of this selector.
  ///
  /// This set is split up in the disjoint [_dispatchTableRanges] and
  /// [staticDispatchRanges].
  final List<({Range range, Reference target})> allTargetRanges;

  /// All targets of this selector that are invoked via the dispatch table (if
  /// any).
  ///
  /// This is a subset of [allTargetRanges]. These need entries in the
  /// dispatch table.
  final List<({Range range, Reference target})> _dispatchTableRanges;

  /// Targets that an interface call will check & directly call before falling
  /// back to dispatch table calls.
  ///
  /// This is a subset of [allTargetRanges]. These don't need entries in the
  /// dispatch table.
  ///
  /// 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 [_dispatchTableRanges], `class ID + offset` gives the
  /// offset of the class member for this selector.
  int? offset;

  SelectorTargets(
    this.allTargetRanges,
    this._dispatchTableRanges,
    this.staticDispatchRanges,
  ) {
    assert(
      allTargetRanges.length ==
          (_dispatchTableRanges.length + staticDispatchRanges.length),
    );
    assert(
      (() {
        int d = 0;
        int s = 0;
        for (int i = 0; i < allTargetRanges.length; ++i) {
          final e = allTargetRanges[i];
          if (d < _dispatchTableRanges.length && _dispatchTableRanges[d] == e) {
            d++;
            continue;
          }
          if (s < staticDispatchRanges.length && staticDispatchRanges[s] == e) {
            s++;
            continue;
          }
          return false;
        }
        return true;
      })(),
    );
  }

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

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

  final Map<TreeNode, ProcedureAttributesMetadata> procedureAttributeMetadata;

  final Translator translator;

  final List<TableSelectorInfo> _selectorMetadata;

  /// Maps selector IDs to selectors.
  final Map<int, SelectorInfo> _selectorInfo = {};

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

  /// For direct calls across modules one can also use the existing table slots
  /// in the dispatch table (instead of adding more slots to static call table).
  late final Map<Reference, int> _tableIndexForReference;

  late final w.TableBuilder _definedWasmTable;
  late final WasmTableImporter _importedWasmTables = WasmTableImporter(
    translator,
    'dispatch',
  );

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

  DispatchTable(this.translator)
    : procedureAttributeMetadata = translator.procedureAttributeMetadata,
      _selectorMetadata =
          (translator.component.metadata[TableSelectorMetadataRepository
                      .repositoryTag]
                  as TableSelectorMetadataRepository)
              .mapping[translator.component]!
              .selectors;

  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]!;
  }

  /// Returns a dispatch table index if the [target] is going to be in the
  /// dispatch table.
  ///
  /// NOTE: The [target] can occur in multiple slots in the dispatch table and
  /// we return the first such index.
  int? indexForTarget(Reference target) => _tableIndexForReference[target];

  SelectorInfo _createSelectorForTarget(Reference target) {
    Member member = target.asMember;
    bool isGetter = target.isGetter || target.isTearOffReference;
    bool isSetter = target.isSetter;
    bool isIndexSetter = member.name == indexSetName;
    ProcedureAttributesMetadata metadata = procedureAttributeMetadata[member]!;
    int selectorId = isGetter
        ? metadata.getterSelectorId
        : metadata.methodOrSetterSelectorId;

    // _WasmBase and its subclass methods cannot be called dynamically
    assert(!translator.isWasmType(member.enclosingClass!));

    // The compiler will generate calls to `noSuchMethod` in the dynamic
    // invocation forwarders. So we ensure that the call count is positive.
    final isNoSuchMethod = member == translator.objectNoSuchMethod;
    final callCount =
        _selectorMetadata[selectorId].callCount + (isNoSuchMethod ? 1 : 0);
    final selector = _selectorInfo.putIfAbsent(
      selectorId,
      () => SelectorInfo._(
        this,
        selectorId,
        member.name.text,
        callCount,
        isSetter: isSetter,
        isIndexSetter: isIndexSetter,
      ),
    );
    assert(selector.isSetter == isSetter);
    assert(selector.isIndexSetter == isIndexSetter);
    selector._references.add(target);

    return selector;
  }

  void _initializeWasmTable() {
    _definedWasmTable = translator.mainModule.tables.define(
      _functionType,
      _table.length,
    );
    for (final module in translator.modules) {
      // Ensure the dispatch table is imported into every module as the first
      // table.
      getWasmTable(module);
    }
  }

  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;

      // Wasm objects are not Dart objects. They carry no class id information
      // and we cannot dispatch methods on them.
      if (translator.isWasmType(cls)) {
        selectorsInClass[cls] = {};
        continue;
      }

      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) {
        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 = 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) {
            addMember(member.tearOffReference, staticDispatch);
          }
        }
      }
      selectorsInClass[cls] = selectors;
    }

    final selectorTargets = <SelectorInfo, Map<int, Reference>>{};
    for (
      int classId = 0;
      classId <= translator.classIdNumbering.maxConcreteClassId;
      ++classId
    ) {
      final cls = translator.classes[classId].cls;
      if (cls != null) {
        selectorsInClass[cls]!.forEach((selectorInfo, target) {
          if (!target.asMember.isAbstract) {
            selectorTargets.putIfAbsent(selectorInfo, () => {})[classId] =
                target;
          }
        });
      }
    }

    _selectorInfo.forEach((_, selector) {
      if (!selectorTargets.containsKey(selector)) {
        // There are no concrete implementations for the given [selector].
        selector._normal = SelectorTargets([], [], []);
        selector.useMultipleEntryPoints = false;
        selector._useSentinelForOptionalParameters = true;
        selector.paramInfo = _parameterInfoFromReferences(
          translator.unreachableMetadata,
          selector._references,
          selector._useSentinelForOptionalParameters,
        );
      } else {
        // Will be initialized in the `selectorTargets.forEach()` below.
      }
    });
    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;

      bool useMultipleEntryPoints = false;
      final implementationReferences = <Reference>[];
      for (final targetRange in ranges) {
        final target = targetRange.target;
        final member = target.asMember;
        assert(!member.isAbstract);

        // Compute [useMultipleEntryPoints]
        if (!member.isExternal &&
            !target.isGetter &&
            !target.isTearOffReference &&
            translator.needToCheckTypesFor(member)) {
          useMultipleEntryPoints = true;
        }
        implementationReferences.add(target);
      }
      selector.useMultipleEntryPoints = useMultipleEntryPoints;

      if (implementationReferences.isNotEmpty) {
        // We have global knowledge of all targets of the selector. We can use
        // this global knowledge to compute the [ParameterInfo].
        selector._references.clear();
        selector._references.addAll(implementationReferences);
        selector._useSentinelForOptionalParameters = false;
      } else {
        // We may have no targets for the selector, but there may
        // still be calls to it (see e.g. https://dartbug.com/60733).
        //
        // In this case make caller pass sentinel if the optional parameter is
        // not provided.
        selector._useSentinelForOptionalParameters = true;
      }
      selector.paramInfo = _parameterInfoFromReferences(
        translator.unreachableMetadata,
        selector._references,
        selector._useSentinelForOptionalParameters,
      );

      // Split up [ranges] into those that are statically dispatched to and
      // those are used via dispatch table.
      final tableDispatchRanges = <({Range range, Reference target})>[];
      final staticDispatchRanges = <({Range range, Reference target})>[];
      if (ranges.length == 1) {
        staticDispatchRanges.add(ranges.single);
      } else {
        for (final range in ranges) {
          if (translator.options.polymorphicSpecialization ||
              staticDispatchPragmas.contains(range.target)) {
            staticDispatchRanges.add(range);
          } else {
            tableDispatchRanges.add(range);
          }
        }
      }
      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(),
          tableDispatchRanges.map((r) => getChecked(r, false)).toList(),
          staticDispatchRanges.map((r) => getChecked(r, false)).toList(),
        );
        final uncheckedTargets = SelectorTargets(
          ranges.map((r) => getChecked(r, true)).toList(),
          tableDispatchRanges.map((r) => getChecked(r, true)).toList(),
          staticDispatchRanges.map((r) => getChecked(r, true)).toList(),
        );
        selector._checked = checkedTargets;
        selector._unchecked = uncheckedTargets;
      } else {
        final normalTargets = SelectorTargets(
          ranges,
          tableDispatchRanges,
          staticDispatchRanges,
        );
        selector._normal = normalTargets;
      }
    });

    // Assign selector offsets

    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;
            rowValues.add((index: adjustedClassId, value: target));
          }
        }
        rowValues.sort((a, b) => a.index.compareTo(b.index));
        return Row(rowValues);
      }

      if (selector.useMultipleEntryPoints) {
        rows.add(buildRow((selector._checked!._dispatchTableRanges)));
        rows.add(buildRow((selector._unchecked!._dispatchTableRanges)));
      } else {
        rows.add(buildRow((selector._normal!._dispatchTableRanges)));
      }
    }

    _table = buildRowDisplacementTable<Reference>(rows);
    _tableIndexForReference = {};
    for (int i = 0; i < _table.length; ++i) {
      final entry = _table[i];
      if (entry == null) continue;
      _tableIndexForReference[entry] ??= i;
    }

    int rowIndex = 0;
    for (final selector in selectors) {
      if (selector.useMultipleEntryPoints) {
        selector._checked!.offset = rows[rowIndex++].offset;
        selector._unchecked!.offset = rows[rowIndex++].offset;
      } else {
        selector._normal!.offset = rows[rowIndex++].offset;
      }
    }

    _initializeWasmTable();
  }

  void output() {
    final mainModule = translator.mainModule.module;

    int calculateStrideWidthHelper(
      Reference target,
      int start, {
      required bool includeNull,
      required bool includeArbitraryNonMainEntries,
    }) {
      final width = calculateStrideWith(start, target, _table, (
        Reference? next,
      ) {
        // If the entry is the same as before we can extend the stride.
        if (next == target) return true;

        // Any call to the dispatch table will succeed. If there's an empty slot
        // in the table, we are guaranteed no calls will invoke it. That in
        // return means its safe to put any entry in there, as it will not be
        // used.
        //
        // => If putting an entry in there makes the stride larger and allows us
        //    to use `table.fill` we'll do so.
        if (next == null) return includeNull;
        final nextFunction = translator.functions.getExistingFunction(next);
        if (nextFunction == null) return includeNull;

        final nextIsInMainModule = nextFunction.enclosingModule == mainModule;
        if (includeArbitraryNonMainEntries && !nextIsInMainModule) {
          return true;
        }

        return false;
      });
      int lastIncluding = start + width - 1;
      while (_table[lastIncluding] != target) {
        lastIncluding--;
      }
      return lastIncluding - start + 1;
    }

    void processTableRange(int start, int end, bool includeMainModuleEntries) {
      while (start < end) {
        final Reference? target = _table[start];
        if (target == null) {
          start++;
          continue;
        }
        final targetFunction = translator.functions.getExistingFunction(target);
        if (targetFunction == null) {
          start++;
          continue;
        }

        final targetInMain = targetFunction.enclosingModule == mainModule;
        if (targetInMain && !includeMainModuleEntries) {
          start++;
          continue;
        }

        final includeArbitraryNonMainEntries = targetInMain;
        final strideWidth = calculateStrideWidthHelper(
          target,
          start,
          includeNull: true,
          includeArbitraryNonMainEntries: includeArbitraryNonMainEntries,
        );
        final strideWidthOnlyTarget = calculateStrideWidthHelper(
          target,
          start,
          includeNull: false,
          includeArbitraryNonMainEntries: false,
        );

        final targetModuleBuilder =
            translator.moduleToBuilder[targetFunction.enclosingModule]!;
        final targetTable = getWasmTable(targetModuleBuilder);
        if (strideWidth >= strideElementTableLimit) {
          targetModuleBuilder.elements.declarativeSegmentBuilder.declare(
            targetFunction,
          );
          final b = targetModuleBuilder.startFunction.body;

          // This may fill entries
          //   - which should be [target]
          //
          //   - which should be null (unused entries)
          //
          //   - which should be 3rd party targets
          //     (iff [includeArbitraryNonMainEntries])
          //     => Those incorrect entries are not used until the deferred
          //     units containing them are loaded, and those deferred units
          //     should override those slots (see below)
          b.fillTableRange(targetTable, start, strideWidth, targetFunction);

          if (includeArbitraryNonMainEntries) {
            // We wrote the `target` to table slots which should contain targets
            // from deferred modules. Ensure the deferred modules override those
            // slots when loaded.
            processTableRange(start, start + strideWidth, false);
          }

          start += strideWidth;
        } else {
          // We don't issue a `table.fill` instruction, so only fill in the
          // slots that are exactly `target`.
          for (int i = 0; i < strideWidthOnlyTarget; ++i) {
            targetModuleBuilder.elements
                .activeFunctionSegmentBuilderFor(targetTable)
                .setFunctionAt(start + i, targetFunction);
          }
          start += strideWidthOnlyTarget;
        }
      }
    }

    processTableRange(0, _table.length, true);
  }
}

bool _isUsedViaDispatchTableCall(SelectorInfo selector) {
  if (selector.callCount == 0) return false;

  final targets = selector.targets(unchecked: false);
  return targets._dispatchTableRanges.isNotEmpty;
}

ParameterInfo _parameterInfoFromReferences(
  UnreachableNodeMetadataRepository unreachableMetadata,
  List<Reference> references,
  bool useDefaultValueSentinel,
) {
  final unreachableNodeMapping = unreachableMetadata.mapping;
  // We know all target implementations (closed world) if all of them use
  // the same default value for optionals, we can make the caller pass it.
  final first = references.first;
  final firstMember = first.asMember;
  final paramInfo = ParameterInfo.fromMember(
    first,
    useDefaultValueSentinel ||
        firstMember.isAbstract ||
        unreachableNodeMapping[firstMember] != null,
  );
  for (final target in references.skip(1)) {
    final targetMember = target.asMember;
    paramInfo.merge(
      ParameterInfo.fromMember(
        target,
        useDefaultValueSentinel ||
            targetMember.isAbstract ||
            unreachableNodeMapping[targetMember] != null,
      ),
    );
  }
  return paramInfo;
}

/// 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.
///
/// If [uniqueOffsets] is `true` then no two rows will be assigned the same
/// offset.
///
/// The offset of all [Row]s will be initialized.
List<V?> buildRowDisplacementTable<V extends Object>(
  List<Row<V>> rows, {
  int firstAvailable = 0,
  bool uniqueOffsets = false,
}) {
  final offsetsTaken = <int>{};
  final table = <V?>[];
  for (final row in rows) {
    final values = row.values;
    int offset = firstAvailable - values.first.index;
    bool fits;
    do {
      fits = true;
      if (uniqueOffsets) {
        while (offsetsTaken.contains(offset)) {
          offset++;
        }
      }
      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;
    if (uniqueOffsets) offsetsTaken.add(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;
}

/// Calculates the size of repeated entries in the table.
///
/// If the table has many repeated elements a caller may choose to not issue
/// repeated entries in the element section but instead fill the table slots in
/// the `start` function of the module.
int calculateStrideWith<T>(
  int start,
  T startEntry,
  List<T?> table,
  bool Function(T?) matches,
) {
  int end = start + 1;
  while (end < table.length) {
    if (!matches(table[end])) break;
    end++;
  }
  return end - start;
}

/// If the stride of the current table entry is more than this we initialize
/// that table section in #start function instead of the element section.
///
/// This has the benefit that instead of adding O(stride-width) entries in the
/// element section we have O(1) addition to the start function (which uses a
/// `table.fill` instruction to fill the entire range with the same value)
const strideElementTableLimit = 100;

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