package org.graalvm.wasm;
import com.oracle.truffle.api.CallTarget;
import com.oracle.truffle.api.CompilerDirectives;
import org.graalvm.wasm.Linker.ResolutionDag.DataSym;
import org.graalvm.wasm.Linker.ResolutionDag.ExportMemorySym;
import org.graalvm.wasm.Linker.ResolutionDag.ImportMemorySym;
import org.graalvm.wasm.Linker.ResolutionDag.Resolver;
import org.graalvm.wasm.Linker.ResolutionDag.Sym;
import org.graalvm.wasm.SymbolTable.FunctionType;
import org.graalvm.wasm.constants.GlobalModifier;
import org.graalvm.wasm.exception.Failure;
import org.graalvm.wasm.exception.WasmException;
import org.graalvm.wasm.memory.WasmMemory;
import org.graalvm.wasm.nodes.WasmBlockNode;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.BiConsumer;
import static org.graalvm.wasm.Linker.ResolutionDag.CallsiteSym;
import static org.graalvm.wasm.Linker.ResolutionDag.CodeEntrySym;
import static org.graalvm.wasm.Linker.ResolutionDag.ElemSym;
import static org.graalvm.wasm.Linker.ResolutionDag.ExportFunctionSym;
import static org.graalvm.wasm.Linker.ResolutionDag.ExportGlobalSym;
import static org.graalvm.wasm.Linker.ResolutionDag.ExportTableSym;
import static org.graalvm.wasm.Linker.ResolutionDag.ImportFunctionSym;
import static org.graalvm.wasm.Linker.ResolutionDag.ImportGlobalSym;
import static org.graalvm.wasm.Linker.ResolutionDag.ImportTableSym;
import static org.graalvm.wasm.Linker.ResolutionDag.InitializeGlobalSym;
import static org.graalvm.wasm.Linker.ResolutionDag.NO_RESOLVE_ACTION;
public class Linker {
public enum LinkState {
nonLinked,
inProgress,
linked
}
private final ResolutionDag resolutionDag;
Linker() {
this.resolutionDag = new ResolutionDag();
}
public void tryLink(WasmInstance instance) {
if (instance.isNonLinked()) {
tryLinkOutsidePartialEvaluation(instance);
CompilerDirectives.transferToInterpreterAndInvalidate();
}
}
@CompilerDirectives.TruffleBoundary
private void tryLinkOutsidePartialEvaluation(WasmInstance entryPointInstance) {
if (entryPointInstance.isNonLinked()) {
final WasmContext context = WasmContext.getCurrent();
Map<String, WasmInstance> instances = context.moduleInstances();
for (WasmInstance instance : instances.values()) {
if (instance.isNonLinked()) {
instance.setLinkInProgress();
for (BiConsumer<WasmContext, WasmInstance> action : instance.module().linkActions()) {
action.accept(context, instance);
}
}
}
linkTopologically();
assignTypeEquivalenceClasses();
for (WasmInstance instance : instances.values()) {
if (instance.isLinkInProgress()) {
instance.module().setParsed();
}
}
for (WasmInstance instance : instances.values()) {
if (instance.isLinkInProgress()) {
final WasmFunction start = instance.symbolTable().startFunction();
if (start != null) {
instance.target(start.index()).call(new Object[0]);
}
instance.setLinkCompleted();
}
}
}
}
private void linkTopologically() {
final Resolver[] sortedResolutions = resolutionDag.toposort();
for (Resolver resolver : sortedResolutions) {
resolver.runActionOnce();
}
}
private static void assignTypeEquivalenceClasses() {
final Map<String, WasmInstance> instances = WasmContext.getCurrent().moduleInstances();
final Map<FunctionType, Integer> equivalenceClasses = new HashMap<>();
int nextEquivalenceClass = SymbolTable.FIRST_EQUIVALENCE_CLASS;
for (WasmInstance instance : instances.values()) {
if (instance.isLinkInProgress() && !instance.module().isParsed()) {
final SymbolTable symtab = instance.symbolTable();
for (int index = 0; index < symtab.typeCount(); index++) {
FunctionType type = symtab.typeAt(index);
Integer equivalenceClass = equivalenceClasses.get(type);
if (equivalenceClass == null) {
equivalenceClass = nextEquivalenceClass;
equivalenceClasses.put(type, equivalenceClass);
nextEquivalenceClass++;
}
symtab.setEquivalenceClass(index, equivalenceClass);
}
for (int index = 0; index < symtab.numFunctions(); index++) {
final WasmFunction function = symtab.function(index);
function.setTypeEquivalenceClass(symtab.equivalenceClass(function.typeIndex()));
}
}
}
}
void resolveGlobalImport(WasmContext context, WasmInstance instance, ImportDescriptor importDescriptor, int globalIndex, byte valueType, byte mutability) {
final String importedGlobalName = importDescriptor.memberName;
final String importedModuleName = importDescriptor.moduleName;
final Runnable resolveAction = () -> {
final WasmInstance importedInstance = context.moduleInstances().get(importedModuleName);
if (importedInstance == null) {
throw WasmException.create(Failure.UNSPECIFIED_UNLINKABLE, "Module '" + importedModuleName + "', referenced in the import of global variable '" +
importedGlobalName + "' into module '" + instance.name() + "', does not exist.");
}
Integer exportedGlobalIndex = importedInstance.symbolTable().exportedGlobals().get(importedGlobalName);
if (exportedGlobalIndex == null) {
throw WasmException.create(Failure.UNSPECIFIED_UNLINKABLE, "Global variable '" + importedGlobalName + "', imported into module '" + instance.name() +
"', was not exported in the module '" + importedModuleName + "'.");
}
int exportedValueType = importedInstance.symbolTable().globalValueType(exportedGlobalIndex);
if (exportedValueType != valueType) {
throw WasmException.create(Failure.UNSPECIFIED_UNLINKABLE, "Global variable '" + importedGlobalName + "' is imported into module '" + instance.name() +
"' with the type " + WasmType.toString(valueType) + ", " +
"'but it was exported in the module '" + importedModuleName + "' with the type " + WasmType.toString(exportedValueType) + ".");
}
int exportedMutability = importedInstance.symbolTable().globalMutability(exportedGlobalIndex);
if (exportedMutability != mutability) {
throw WasmException.create(Failure.UNSPECIFIED_UNLINKABLE, "Global variable '" + importedGlobalName + "' is imported into module '" + instance.name() +
"' with the modifier " + GlobalModifier.asString(mutability) + ", " +
"'but it was exported in the module '" + importedModuleName + "' with the modifier " + GlobalModifier.asString(exportedMutability) + ".");
}
int address = importedInstance.globalAddress(exportedGlobalIndex);
instance.setGlobalAddress(globalIndex, address);
};
final ImportGlobalSym importGlobalSym = new ImportGlobalSym(instance.name(), importDescriptor);
final Sym[] dependencies = new Sym[]{new ExportGlobalSym(importedModuleName, importedGlobalName)};
resolutionDag.resolveLater(importGlobalSym, dependencies, resolveAction);
resolutionDag.resolveLater(new InitializeGlobalSym(instance.name(), globalIndex), new Sym[]{importGlobalSym}, NO_RESOLVE_ACTION);
}
void resolveGlobalExport(WasmModule module, String globalName, int globalIndex) {
final Sym[] dependencies;
dependencies = new Sym[]{new InitializeGlobalSym(module.name(), globalIndex)};
resolutionDag.resolveLater(new ExportGlobalSym(module.name(), globalName), dependencies, NO_RESOLVE_ACTION);
}
void resolveGlobalInitialization(WasmInstance instance, int globalIndex) {
final Sym[] dependencies = ResolutionDag.NO_DEPENDENCIES;
resolutionDag.resolveLater(new InitializeGlobalSym(instance.name(), globalIndex), dependencies, NO_RESOLVE_ACTION);
}
void resolveGlobalInitialization(WasmContext context, WasmInstance instance, int globalIndex, int sourceGlobalIndex) {
final Runnable resolveAction = () -> {
final int sourceAddress = instance.globalAddress(sourceGlobalIndex);
final long sourceValue = context.globals().loadAsLong(sourceAddress);
final int address = instance.globalAddress(globalIndex);
context.globals().storeLong(address, sourceValue);
};
final Sym[] dependencies = new Sym[]{new InitializeGlobalSym(instance.name(), sourceGlobalIndex)};
resolutionDag.resolveLater(new InitializeGlobalSym(instance.name(), globalIndex), dependencies, resolveAction);
}
void resolveFunctionImport(WasmContext context, WasmInstance instance, WasmFunction function) {
final Runnable resolveAction = () -> {
final WasmInstance importedInstance = context.moduleInstances().get(function.importedModuleName());
if (importedInstance == null) {
throw WasmException.create(
Failure.UNSPECIFIED_UNLINKABLE,
"The module '" + function.importedModuleName() + "', referenced by the import '" + function.importedFunctionName() + "' in the module '" + instance.name() +
"', does not exist.");
}
WasmFunction importedFunction;
importedFunction = importedInstance.module().exportedFunctions().get(function.importedFunctionName());
if (importedFunction == null) {
throw WasmException.create(Failure.UNSPECIFIED_UNLINKABLE, "The imported function '" + function.importedFunctionName() + "', referenced in the module '" + instance.name() +
"', does not exist in the imported module '" + function.importedModuleName() + "'.");
}
final CallTarget target = importedInstance.target(importedFunction.index());
instance.setTarget(function.index(), target);
};
final Sym[] dependencies = new Sym[]{new ExportFunctionSym(function.importDescriptor().moduleName, function.importDescriptor().memberName)};
resolutionDag.resolveLater(new ImportFunctionSym(instance.name(), function.importDescriptor()), dependencies, resolveAction);
}
void resolveFunctionExport(WasmModule module, int functionIndex, String exportedFunctionName) {
final ImportDescriptor importDescriptor = module.symbolTable().function(functionIndex).importDescriptor();
final Sym[] dependencies = (importDescriptor != null) ? new Sym[]{new ImportFunctionSym(module.name(), importDescriptor)} : ResolutionDag.NO_DEPENDENCIES;
resolutionDag.resolveLater(new ExportFunctionSym(module.name(), exportedFunctionName), dependencies, NO_RESOLVE_ACTION);
}
void resolveCallsite(WasmInstance instance, WasmBlockNode block, int controlTableOffset, WasmFunction function) {
final Runnable resolveAction = () -> {
block.resolveCallNode(controlTableOffset);
};
final Sym[] dependencies = new Sym[]{function.isImported() ? new ImportFunctionSym(instance.name(), function.importDescriptor()) : new CodeEntrySym(instance.name(), function.index())};
resolutionDag.resolveLater(new CallsiteSym(instance.name(), block.startOfset(), controlTableOffset), dependencies, resolveAction);
}
void resolveCodeEntry(WasmModule module, int functionIndex) {
resolutionDag.resolveLater(new CodeEntrySym(module.name(), functionIndex), ResolutionDag.NO_DEPENDENCIES, NO_RESOLVE_ACTION);
}
void resolveMemoryImport(WasmContext context, WasmInstance instance, ImportDescriptor importDescriptor, int initSize, int maxSize) {
String importedModuleName = importDescriptor.moduleName;
String importedMemoryName = importDescriptor.memberName;
final Runnable resolveAction = () -> {
final WasmInstance importedInstance = context.moduleInstances().get(importedModuleName);
if (importedInstance == null) {
throw WasmException.create(Failure.UNSPECIFIED_UNLINKABLE, String.format("The module '%s', referenced in the import of memory '%s' in module '%s', does not exist",
importedModuleName, importedMemoryName, instance.name()));
}
final String exportedMemoryName = importedInstance.symbolTable().exportedMemory();
if (exportedMemoryName == null) {
throw WasmException.create(Failure.UNSPECIFIED_UNLINKABLE,
String.format("The imported module '%s' does not export any memories, so cannot resolve memory '%s' imported in module '%s'.",
importedModuleName, importedMemoryName, instance.name()));
}
if (!exportedMemoryName.equals(importedMemoryName)) {
throw WasmException.create(Failure.UNSPECIFIED_UNLINKABLE, String.format("The imported module '%s' exports a memory '%s', but module '%s' imports a memory '%s'.",
importedModuleName, exportedMemoryName, instance.name(), importedModuleName));
}
final WasmMemory memory = importedInstance.memory();
if (memory.maxPageSize() >= 0 && (initSize > memory.maxPageSize() || maxSize > memory.maxPageSize())) {
throw WasmException.create(Failure.UNSPECIFIED_UNLINKABLE,
String.format("The memory '%s' in the imported module '%s' has maximum size %d, but module '%s' imports it with maximum size '%d'",
importedMemoryName, importedModuleName, memory.maxPageSize(), instance.name(), maxSize));
}
if (memory.pageSize() < initSize) {
memory.grow(initSize - memory.pageSize());
}
instance.setMemory(memory);
};
resolutionDag.resolveLater(new ImportMemorySym(instance.name(), importDescriptor), new Sym[]{new ExportMemorySym(importedModuleName, importedMemoryName)}, resolveAction);
}
void resolveMemoryExport(WasmInstance instance, String exportedMemoryName) {
WasmModule module = instance.module();
final ImportDescriptor importDescriptor = module.symbolTable().importedMemory();
final Sym[] dependencies = importDescriptor != null ? new Sym[]{new ImportMemorySym(module.name(), importDescriptor)} : ResolutionDag.NO_DEPENDENCIES;
resolutionDag.resolveLater(new ExportMemorySym(module.name(), exportedMemoryName), dependencies, () -> {
});
}
void resolveDataSegment(WasmContext context, WasmInstance instance, int dataSegmentId, int offsetAddress, int offsetGlobalIndex, int byteLength, byte[] data) {
Assert.assertTrue(instance.symbolTable().memoryExists(), String.format("No memory declared or imported in the module '%s'", instance.name()), Failure.UNSPECIFIED_MALFORMED);
final Runnable resolveAction = () -> {
assert (offsetAddress != -1) ^ (offsetGlobalIndex != -1) : "Both an offset address and a offset global are specified for the data segment.";
WasmMemory memory = instance.memory();
Assert.assertNotNull(memory, String.format("No memory declared or imported in the module '%s'", instance.name()), Failure.UNSPECIFIED_MALFORMED);
int baseAddress;
if (offsetGlobalIndex != -1) {
final int offsetGlobalAddress = instance.globalAddress(offsetGlobalIndex);
Assert.assertTrue(offsetGlobalAddress != -1, "The global variable '" + offsetGlobalIndex + "' for the offset of the data segment " +
dataSegmentId + " in module '" + instance.name() + "' was not initialized.", Failure.UNSPECIFIED_MALFORMED);
baseAddress = context.globals().loadAsInt(offsetGlobalAddress);
} else {
baseAddress = offsetAddress;
}
for (int writeOffset = 0; writeOffset != byteLength; ++writeOffset) {
byte b = data[writeOffset];
memory.store_i32_8(null, baseAddress + writeOffset, b);
}
};
final ArrayList<Sym> dependencies = new ArrayList<>();
if (instance.symbolTable().importedMemory() != null) {
dependencies.add(new ImportMemorySym(instance.name(), instance.symbolTable().importedMemory()));
}
if (dataSegmentId > 0) {
dependencies.add(new DataSym(instance.name(), dataSegmentId - 1));
}
if (offsetGlobalIndex != -1) {
dependencies.add(new InitializeGlobalSym(instance.name(), offsetGlobalIndex));
}
resolutionDag.resolveLater(new DataSym(instance.name(), dataSegmentId), dependencies.toArray(new Sym[dependencies.size()]), resolveAction);
}
void resolveTableImport(WasmContext context, WasmInstance instance, ImportDescriptor importDescriptor, int initSize, int maxSize) {
final Runnable resolveAction = () -> {
final WasmInstance importedInstance = context.moduleInstances().get(importDescriptor.moduleName);
final String importedModuleName = importDescriptor.moduleName;
if (importedInstance == null) {
throw WasmException.create(Failure.UNSPECIFIED_UNLINKABLE, String.format("Imported module '%s', referenced in module '%s', does not exist.", importedModuleName, instance.name()));
} else {
final String importedTableName = importDescriptor.memberName;
final String exportedTableName = importedInstance.symbolTable().exportedTable();
if (exportedTableName == null) {
throw WasmException.create(Failure.UNSPECIFIED_UNLINKABLE,
String.format("The imported module '%s' does not export any tables, so cannot resolve table '%s' imported in module '%s'.",
importedModuleName, importedTableName, instance.name()));
}
if (!exportedTableName.equals(importedTableName)) {
throw WasmException.create(Failure.UNSPECIFIED_UNLINKABLE, String.format("The imported module '%s' exports a table '%s', but module '%s' imports a table '%s'.",
importedModuleName, exportedTableName, instance.name(), importedTableName));
}
final WasmTable table = importedInstance.table();
final int declaredMaxSize = table.maxSize();
if (declaredMaxSize >= 0 && (initSize > declaredMaxSize || maxSize > declaredMaxSize)) {
throw WasmException.create(Failure.UNSPECIFIED_UNLINKABLE,
String.format("The table '%s' in the imported module '%s' has maximum size %d, but module '%s' imports it with maximum size '%d'",
importedTableName, importedModuleName, declaredMaxSize, instance.name(), maxSize));
}
table.ensureSizeAtLeast(initSize);
instance.setTable(table);
}
};
Sym[] dependencies = new Sym[]{new ExportTableSym(importDescriptor.moduleName, importDescriptor.memberName)};
resolutionDag.resolveLater(new ImportTableSym(instance.name(), importDescriptor), dependencies, resolveAction);
}
void resolveTableExport(WasmModule module, String exportedTableName) {
final ImportDescriptor importDescriptor = module.symbolTable().importedTable();
final Sym[] dependencies = importDescriptor != null ? new Sym[]{new ImportTableSym(module.name(), importDescriptor)} : ResolutionDag.NO_DEPENDENCIES;
resolutionDag.resolveLater(new ExportTableSym(module.name(), exportedTableName), dependencies, NO_RESOLVE_ACTION);
}
void resolveElemSegment(WasmContext context, WasmInstance instance, int elemSegmentId, int offsetAddress, int offsetGlobalIndex, int segmentLength, WasmFunction[] functions) {
Assert.assertTrue(instance.symbolTable().tableExists(), String.format("No table declared or imported in the module '%s'", instance.name()), Failure.UNSPECIFIED_MALFORMED);
final Runnable resolveAction = () -> {
assert (offsetAddress != -1) ^ (offsetGlobalIndex != -1) : "Both an offset address and a offset global are specified for the elem segment.";
final WasmTable table = instance.table();
Assert.assertNotNull(table, String.format("No table declared or imported in the module '%s'", instance.name()), Failure.UNSPECIFIED_MALFORMED);
int baseAddress;
if (offsetGlobalIndex != -1) {
final int offsetGlobalAddress = instance.globalAddress(offsetGlobalIndex);
Assert.assertTrue(offsetGlobalAddress != -1, "The global variable '" + offsetGlobalIndex + "' for the offset of the elem segment " +
elemSegmentId + " in module '" + instance.name() + "' was not initialized.", Failure.UNSPECIFIED_MALFORMED);
baseAddress = context.globals().loadAsInt(offsetGlobalAddress);
} else {
baseAddress = offsetAddress;
}
table.ensureSizeAtLeast(baseAddress + segmentLength);
for (int index = 0; index != segmentLength; ++index) {
final WasmFunction function = functions[index];
final CallTarget target = instance.target(function.index());
table.initialize(baseAddress + index, new WasmFunctionInstance(function, target));
}
};
final ArrayList<Sym> dependencies = new ArrayList<>();
if (instance.symbolTable().importedTable() != null) {
dependencies.add(new ImportTableSym(instance.name(), instance.symbolTable().importedTable()));
}
if (offsetGlobalIndex != -1) {
dependencies.add(new InitializeGlobalSym(instance.name(), offsetGlobalIndex));
}
for (WasmFunction function : functions) {
if (function.importDescriptor() != null) {
dependencies.add(new ImportFunctionSym(instance.name(), function.importDescriptor()));
}
}
resolutionDag.resolveLater(new ElemSym(instance.name(), elemSegmentId), dependencies.toArray(new Sym[dependencies.size()]), resolveAction);
}
static class ResolutionDag {
public static final Runnable NO_RESOLVE_ACTION = () -> {
};
private static final Sym[] NO_DEPENDENCIES = new Sym[0];
abstract static class Sym {
}
static class ImportGlobalSym extends Sym {
final String moduleName;
final ImportDescriptor importDescriptor;
ImportGlobalSym(String moduleName, ImportDescriptor importDescriptor) {
this.moduleName = moduleName;
this.importDescriptor = importDescriptor;
}
@Override
public String toString() {
return String.format("(import global %s from %s into %s)", importDescriptor.memberName, importDescriptor.moduleName, moduleName);
}
@Override
public int hashCode() {
return moduleName.hashCode() ^ importDescriptor.hashCode();
}
@Override
public boolean equals(Object object) {
if (!(object instanceof ImportGlobalSym)) {
return false;
}
final ImportGlobalSym that = (ImportGlobalSym) object;
return this.moduleName.equals(that.moduleName) && this.importDescriptor.equals(that.importDescriptor);
}
}
static class ExportGlobalSym extends Sym {
final String moduleName;
final String globalName;
ExportGlobalSym(String moduleName, String globalName) {
this.moduleName = moduleName;
this.globalName = globalName;
}
@Override
public String toString() {
return String.format("(export global %s from %s)", globalName, moduleName);
}
@Override
public int hashCode() {
return moduleName.hashCode() ^ globalName.hashCode();
}
@Override
public boolean equals(Object object) {
if (!(object instanceof ExportGlobalSym)) {
return false;
}
final ExportGlobalSym that = (ExportGlobalSym) object;
return this.moduleName.equals(that.moduleName) && this.globalName.equals(that.globalName);
}
}
static class InitializeGlobalSym extends Sym {
final String moduleName;
final int globalIndex;
InitializeGlobalSym(String moduleName, int globalIndex) {
this.moduleName = moduleName;
this.globalIndex = globalIndex;
}
@Override
public String toString() {
return String.format("(init global %d in %s)", globalIndex, moduleName);
}
@Override
public int hashCode() {
return Integer.hashCode(globalIndex) ^ moduleName.hashCode();
}
@Override
public boolean equals(Object object) {
if (!(object instanceof InitializeGlobalSym)) {
return false;
}
final InitializeGlobalSym that = (InitializeGlobalSym) object;
return this.globalIndex == that.globalIndex && this.moduleName.equals(that.moduleName);
}
}
static class ImportFunctionSym extends Sym {
final String moduleName;
final ImportDescriptor importDescriptor;
ImportFunctionSym(String moduleName, ImportDescriptor importDescriptor) {
this.moduleName = moduleName;
this.importDescriptor = importDescriptor;
}
@Override
public String toString() {
return String.format("(import func %s from %s into %s)", importDescriptor.memberName, importDescriptor.moduleName, moduleName);
}
@Override
public int hashCode() {
return moduleName.hashCode() ^ importDescriptor.hashCode();
}
@Override
public boolean equals(Object object) {
if (!(object instanceof ImportFunctionSym)) {
return false;
}
final ImportFunctionSym that = (ImportFunctionSym) object;
return this.moduleName.equals(that.moduleName) && this.importDescriptor.equals(that.importDescriptor);
}
}
static class ExportFunctionSym extends Sym {
final String moduleName;
final String functionName;
ExportFunctionSym(String moduleName, String functionName) {
this.moduleName = moduleName;
this.functionName = functionName;
}
@Override
public String toString() {
return String.format("(export func %s from %s)", functionName, moduleName);
}
@Override
public int hashCode() {
return moduleName.hashCode() ^ functionName.hashCode();
}
@Override
public boolean equals(Object object) {
if (!(object instanceof ExportFunctionSym)) {
return false;
}
final ExportFunctionSym that = (ExportFunctionSym) object;
return this.moduleName.equals(that.moduleName) && this.functionName.equals(that.functionName);
}
}
static class CallsiteSym extends Sym {
final String moduleName;
final int instructionOffset;
final int controlTableOffset;
CallsiteSym(String moduleName, int instructionOffset, int controlTableOffset) {
this.moduleName = moduleName;
this.instructionOffset = instructionOffset;
this.controlTableOffset = controlTableOffset;
}
@Override
public String toString() {
return String.format("(callsite at %d in %s)", instructionOffset, moduleName);
}
@Override
public int hashCode() {
return moduleName.hashCode() ^ instructionOffset ^ (controlTableOffset << 16);
}
@Override
public boolean equals(Object object) {
if (!(object instanceof CallsiteSym)) {
return false;
}
final CallsiteSym that = (CallsiteSym) object;
return this.instructionOffset == that.instructionOffset && this.controlTableOffset == that.controlTableOffset && this.moduleName.equals(that.moduleName);
}
}
static class CodeEntrySym extends Sym {
final String moduleName;
final int functionIndex;
CodeEntrySym(String moduleName, int functionIndex) {
this.moduleName = moduleName;
this.functionIndex = functionIndex;
}
@Override
public String toString() {
return String.format("(code entry at %d in %s)", functionIndex, moduleName);
}
@Override
public int hashCode() {
return moduleName.hashCode() ^ functionIndex;
}
@Override
public boolean equals(Object object) {
if (!(object instanceof CodeEntrySym)) {
return false;
}
final CodeEntrySym that = (CodeEntrySym) object;
return this.functionIndex == that.functionIndex && this.moduleName.equals(that.moduleName);
}
}
static class ImportMemorySym extends Sym {
final String moduleName;
final ImportDescriptor importDescriptor;
ImportMemorySym(String moduleName, ImportDescriptor importDescriptor) {
this.moduleName = moduleName;
this.importDescriptor = importDescriptor;
}
@Override
public String toString() {
return String.format("(import memory %s from %s into %s)", importDescriptor.memberName, importDescriptor.moduleName, moduleName);
}
@Override
public int hashCode() {
return moduleName.hashCode() ^ importDescriptor.hashCode();
}
@Override
public boolean equals(Object object) {
if (!(object instanceof ImportMemorySym)) {
return false;
}
final ImportMemorySym that = (ImportMemorySym) object;
return this.moduleName.equals(that.moduleName) && this.importDescriptor.equals(that.importDescriptor);
}
}
static class ExportMemorySym extends Sym {
final String moduleName;
final String memoryName;
ExportMemorySym(String moduleName, String memoryName) {
this.moduleName = moduleName;
this.memoryName = memoryName;
}
@Override
public String toString() {
return String.format("(export memory %s from %s)", memoryName, moduleName);
}
@Override
public int hashCode() {
return moduleName.hashCode() ^ memoryName.hashCode();
}
@Override
public boolean equals(Object object) {
if (!(object instanceof ExportMemorySym)) {
return false;
}
final ExportMemorySym that = (ExportMemorySym) object;
return this.moduleName.equals(that.moduleName) && this.memoryName.equals(that.memoryName);
}
}
static class DataSym extends Sym {
final String moduleName;
final int dataSegmentId;
DataSym(String moduleName, int dataSegmentId) {
this.moduleName = moduleName;
this.dataSegmentId = dataSegmentId;
}
@Override
public String toString() {
return String.format("(data %d in %s)", dataSegmentId, moduleName);
}
@Override
public int hashCode() {
return moduleName.hashCode() ^ dataSegmentId;
}
@Override
public boolean equals(Object object) {
if (!(object instanceof DataSym)) {
return false;
}
final DataSym that = (DataSym) object;
return this.dataSegmentId == that.dataSegmentId && this.moduleName.equals(that.moduleName);
}
}
static class ImportTableSym extends Sym {
final String moduleName;
final ImportDescriptor importDescriptor;
ImportTableSym(String moduleName, ImportDescriptor importDescriptor) {
this.moduleName = moduleName;
this.importDescriptor = importDescriptor;
}
@Override
public String toString() {
return String.format("(import memory %s from %s into %s)", importDescriptor.memberName, importDescriptor.moduleName, moduleName);
}
@Override
public int hashCode() {
return moduleName.hashCode() ^ importDescriptor.hashCode();
}
@Override
public boolean equals(Object object) {
if (!(object instanceof ImportTableSym)) {
return false;
}
final ImportTableSym that = (ImportTableSym) object;
return this.moduleName.equals(that.moduleName) && this.importDescriptor.equals(that.importDescriptor);
}
}
static class ExportTableSym extends Sym {
final String moduleName;
final String tableName;
ExportTableSym(String moduleName, String tableName) {
this.moduleName = moduleName;
this.tableName = tableName;
}
@Override
public String toString() {
return String.format("(export memory %s from %s)", tableName, moduleName);
}
@Override
public int hashCode() {
return moduleName.hashCode() ^ tableName.hashCode();
}
@Override
public boolean equals(Object object) {
if (!(object instanceof ExportTableSym)) {
return false;
}
final ExportTableSym that = (ExportTableSym) object;
return this.moduleName.equals(that.moduleName) && this.tableName.equals(that.tableName);
}
}
static class ElemSym extends Sym {
final String moduleName;
final int elemSegmentId;
ElemSym(String moduleName, int dataSegmentId) {
this.moduleName = moduleName;
this.elemSegmentId = dataSegmentId;
}
@Override
public String toString() {
return String.format("(data %d in %s)", elemSegmentId, moduleName);
}
@Override
public int hashCode() {
return moduleName.hashCode() ^ elemSegmentId;
}
@Override
public boolean equals(Object object) {
if (!(object instanceof ElemSym)) {
return false;
}
final ElemSym that = (ElemSym) object;
return this.elemSegmentId == that.elemSegmentId && this.moduleName.equals(that.moduleName);
}
}
static class Resolver {
final Sym element;
final Sym[] dependencies;
Runnable action;
Resolver(Sym element, Sym[] dependencies, Runnable action) {
this.element = element;
this.dependencies = dependencies;
this.action = action;
}
@Override
public String toString() {
return "Resolver(" + element + ")";
}
public void runActionOnce() {
if (this.action != null) {
this.action.run();
this.action = null;
}
}
}
private final Map<Sym, Resolver> resolutions;
ResolutionDag() {
this.resolutions = new HashMap<>();
}
void resolveLater(Sym element, Sym[] dependencies, Runnable action) {
resolutions.put(element, new Resolver(element, dependencies, action));
}
void clear() {
resolutions.clear();
}
private static String renderCycle(List<Sym> stack) {
StringBuilder result = new StringBuilder();
String arrow = "";
for (Sym sym : stack) {
result.append(arrow).append(sym.toString());
arrow = " -> ";
}
return result.toString();
}
private void toposort(Sym sym, Map<Sym, Boolean> marks, ArrayList<Resolver> sorted, List<Sym> stack) {
final Resolver resolver = resolutions.get(sym);
if (resolver != null) {
final Boolean mark = marks.get(sym);
if (Boolean.TRUE.equals(mark)) {
return;
}
if (Boolean.FALSE.equals(mark)) {
throw WasmException.create(Failure.UNSPECIFIED_UNLINKABLE, String.format("Detected a cycle in the import dependencies: %s",
renderCycle(stack)));
}
marks.put(sym, Boolean.FALSE);
stack.add(sym);
for (Sym dependency : resolver.dependencies) {
toposort(dependency, marks, sorted, stack);
}
marks.put(sym, Boolean.TRUE);
stack.remove(stack.size() - 1);
sorted.add(resolver);
}
}
Resolver[] toposort() {
Map<Sym, Boolean> marks = new HashMap<>();
ArrayList<Resolver> sorted = new ArrayList<>();
for (Sym sym : resolutions.keySet()) {
toposort(sym, marks, sorted, new ArrayList<>());
}
return sorted.toArray(new Resolver[sorted.size()]);
}
}
}