path: root/src/link/Wasm.zig

const Wasm = @This();

const std = @import("std");
const builtin = @import("builtin");
const mem = std.mem;
const Allocator = std.mem.Allocator;
const assert = std.debug.assert;
const fs = std.fs;
const leb = std.leb;
const log = std.log.scoped(.link);
const wasm = std.wasm;

const Atom = @import("Wasm/Atom.zig");
const Module = @import("../Module.zig");
const Compilation = @import("../Compilation.zig");
const CodeGen = @import("../arch/wasm/CodeGen.zig");
const codegen = @import("../codegen.zig");
const link = @import("../link.zig");
const lldMain = @import("../main.zig").lldMain;
const trace = @import("../tracy.zig").trace;
const build_options = @import("build_options");
const wasi_libc = @import("../wasi_libc.zig");
const Cache = @import("../Cache.zig");
const Type = @import("../type.zig").Type;
const TypedValue = @import("../TypedValue.zig");
const LlvmObject = @import("../codegen/llvm.zig").Object;
const Air = @import("../Air.zig");
const Liveness = @import("../Liveness.zig");
const Symbol = @import("Wasm/Symbol.zig");
const Object = @import("Wasm/Object.zig");
const types = @import("Wasm/types.zig");

pub const base_tag = link.File.Tag.wasm;

/// deprecated: Use `@import("Wasm/Atom.zig");`
pub const DeclBlock = Atom;

base: link.File,
/// Output name of the file
name: []const u8,
/// If this is not null, an object file is created by LLVM and linked with LLD afterwards.
llvm_object: ?*LlvmObject = null,
/// When importing objects from the host environment, a name must be supplied.
/// LLVM uses "env" by default when none is given. This would be a good default for Zig
/// to support existing code.
/// TODO: Allow setting this through a flag?
host_name: []const u8 = "env",
/// List of all `Decl` that are currently alive.
/// This is ment for bookkeeping so we can safely cleanup all codegen memory
/// when calling `deinit`
decls: std.AutoHashMapUnmanaged(*Module.Decl, void) = .{},
/// List of all symbols generated by Zig code.
symbols: std.ArrayListUnmanaged(Symbol) = .{},
/// List of symbol indexes which are free to be used.
symbols_free_list: std.ArrayListUnmanaged(u32) = .{},
/// Maps atoms to their segment index
atoms: std.AutoHashMapUnmanaged(u32, *Atom) = .{},
/// Atoms managed and created by the linker. This contains atoms
/// from object files, and not Atoms generated by a Decl.
managed_atoms: std.ArrayListUnmanaged(*Atom) = .{},
/// Represents the index into `segments` where the 'code' section
/// lives.
code_section_index: ?u32 = null,
/// The count of imported functions. This number will be appended
/// to the function indexes as their index starts at the lowest non-extern function.
imported_functions_count: u32 = 0,
/// The count of imported wasm globals. This number will be appended
/// to the global indexes when sections are merged.
imported_globals_count: u32 = 0,
/// The count of imported tables. This number will be appended
/// to the table indexes when sections are merged.
imported_tables_count: u32 = 0,
/// Map of symbol locations, represented by its `types.Import`
imports: std.AutoHashMapUnmanaged(SymbolLoc, types.Import) = .{},
/// Represents non-synthetic section entries.
/// Used for code, data and custom sections.
segments: std.ArrayListUnmanaged(Segment) = .{},
/// Maps a data segment key (such as .rodata) to the index into `segments`.
data_segments: std.StringArrayHashMapUnmanaged(u32) = .{},
/// A list of `types.Segment` which provide meta data
/// about a data symbol such as its name
segment_info: std.ArrayListUnmanaged(types.Segment) = .{},
/// Deduplicated string table for strings used by symbols, imports and exports.
string_table: StringTable = .{},

// Output sections
/// Output type section
func_types: std.ArrayListUnmanaged(wasm.Type) = .{},
/// Output function section
functions: std.ArrayListUnmanaged(wasm.Func) = .{},
/// Output global section
wasm_globals: std.ArrayListUnmanaged(wasm.Global) = .{},
/// Memory section
memories: wasm.Memory = .{ .limits = .{ .min = 0, .max = null } },
/// Output table section
tables: std.ArrayListUnmanaged(wasm.Table) = .{},
/// Output export section
exports: std.ArrayListUnmanaged(types.Export) = .{},

/// Indirect function table, used to call function pointers
/// When this is non-zero, we must emit a table entry,
/// as well as an 'elements' section.
///
/// Note: Key is symbol index, value represents the index into the table
function_table: std.AutoHashMapUnmanaged(u32, u32) = .{},

/// All object files and their data which are linked into the final binary
objects: std.ArrayListUnmanaged(Object) = .{},
/// A map of global names (read: offset into string table) to their symbol location
globals: std.AutoHashMapUnmanaged(u32, SymbolLoc) = .{},
/// Maps discarded symbols and their positions to the location of the symbol
/// it was resolved to
discarded: std.AutoHashMapUnmanaged(SymbolLoc, SymbolLoc) = .{},
/// List of all symbol locations which have been resolved by the linker and will be emit
/// into the final binary.
resolved_symbols: std.AutoArrayHashMapUnmanaged(SymbolLoc, void) = .{},
/// Maps a symbol's location to an atom. This can be used to find meta
/// data of a symbol, such as its size, or its offset to perform a relocation.
/// Undefined (and synthetic) symbols do not have an Atom and therefore cannot be mapped.
symbol_atom: std.AutoHashMapUnmanaged(SymbolLoc, *Atom) = .{},
/// Maps a symbol's location to its export name, which may differ from the decl's name
/// which does the exporting.
/// Note: The value represents the offset into the string table, rather than the actual string.
export_names: std.AutoHashMapUnmanaged(SymbolLoc, u32) = .{},

pub const Segment = struct {
    alignment: u32,
    size: u32,
    offset: u32,
};

pub const FnData = struct {
    type_index: u32,

    pub const empty: FnData = .{
        .type_index = undefined,
    };
};

pub const Export = struct {
    sym_index: ?u32 = null,
};

pub const SymbolLoc = struct {
    /// The index of the symbol within the specified file
    index: u32,
    /// The index of the object file where the symbol resides.
    /// When this is `null` the symbol comes from a non-object file.
    file: ?u16,

    /// From a given location, returns the corresponding symbol in the wasm binary
    pub fn getSymbol(self: SymbolLoc, wasm_bin: *const Wasm) *Symbol {
        if (wasm_bin.discarded.get(self)) |new_loc| {
            return new_loc.getSymbol(wasm_bin);
        }
        if (self.file) |object_index| {
            const object = wasm_bin.objects.items[object_index];
            return &object.symtable[self.index];
        }
        return &wasm_bin.symbols.items[self.index];
    }

    /// From a given location, returns the name of the symbol.
    pub fn getName(self: SymbolLoc, wasm_bin: *const Wasm) []const u8 {
        if (wasm_bin.discarded.get(self)) |new_loc| {
            return new_loc.getName(wasm_bin);
        }
        if (self.file) |object_index| {
            const object = wasm_bin.objects.items[object_index];
            return object.string_table.get(object.symtable[self.index].name);
        }
        return wasm_bin.string_table.get(wasm_bin.symbols.items[self.index].name);
    }
};

/// Generic string table that duplicates strings
/// and converts them into offsets instead.
pub const StringTable = struct {
    /// Table that maps string offsets, which is used to de-duplicate strings.
    /// Rather than having the offset map to the data, the `StringContext` holds all bytes of the string.
    /// The strings are stored as a contigious array where each string is zero-terminated.
    string_table: std.HashMapUnmanaged(
        u32,
        void,
        std.hash_map.StringIndexContext,
        std.hash_map.default_max_load_percentage,
    ) = .{},
    /// Holds the actual data of the string table.
    string_data: std.ArrayListUnmanaged(u8) = .{},

    /// Accepts a string and searches for a corresponding string.
    /// When found, de-duplicates the string and returns the existing offset instead.
    /// When the string is not found in the `string_table`, a new entry will be inserted
    /// and the new offset to its data will be returned.
    pub fn put(self: *StringTable, allocator: Allocator, string: []const u8) !u32 {
        const gop = try self.string_table.getOrPutContextAdapted(
            allocator,
            string,
            std.hash_map.StringIndexAdapter{ .bytes = &self.string_data },
            .{ .bytes = &self.string_data },
        );
        if (gop.found_existing) {
            const off = gop.key_ptr.*;
            log.debug("reusing string '{s}' at offset 0x{x}", .{ string, off });
            return off;
        }

        try self.string_data.ensureUnusedCapacity(allocator, string.len + 1);
        const offset = @intCast(u32, self.string_data.items.len);

        log.debug("writing new string '{s}' at offset 0x{x}", .{ string, offset });

        self.string_data.appendSliceAssumeCapacity(string);
        self.string_data.appendAssumeCapacity(0);

        gop.key_ptr.* = offset;

        return offset;
    }

    /// From a given offset, returns its corresponding string value.
    /// Asserts offset does not exceed bounds.
    pub fn get(self: StringTable, off: u32) []const u8 {
        assert(off < self.string_data.items.len);
        return mem.sliceTo(@ptrCast([*:0]const u8, self.string_data.items.ptr + off), 0);
    }

    /// Returns the offset of a given string when it exists.
    /// Will return null if the given string does not yet exist within the string table.
    pub fn getOffset(self: *StringTable, string: []const u8) ?u32 {
        return self.string_table.getKeyAdapted(
            string,
            std.hash_map.StringIndexAdapter{ .bytes = &self.string_data },
        );
    }

    /// Frees all resources of the string table. Any references pointing
    /// to the strings will be invalid.
    pub fn deinit(self: *StringTable, allocator: Allocator) void {
        self.string_data.deinit(allocator);
        self.string_table.deinit(allocator);
        self.* = undefined;
    }
};

pub fn openPath(allocator: Allocator, sub_path: []const u8, options: link.Options) !*Wasm {
    assert(options.object_format == .wasm);

    if (build_options.have_llvm and options.use_llvm) {
        return createEmpty(allocator, options);
    }

    const wasm_bin = try createEmpty(allocator, options);
    errdefer wasm_bin.base.destroy();

    // TODO: read the file and keep valid parts instead of truncating
    const file = try options.emit.?.directory.handle.createFile(sub_path, .{ .truncate = true, .read = true });
    wasm_bin.base.file = file;
    wasm_bin.name = sub_path;

    try file.writeAll(&(wasm.magic ++ wasm.version));

    // As sym_index '0' is reserved, we use it for our stack pointer symbol
    const sym_name = try wasm_bin.string_table.put(allocator, "__stack_pointer");
    const symbol = try wasm_bin.symbols.addOne(allocator);
    symbol.* = .{
        .name = sym_name,
        .tag = .global,
        .flags = 0,
        .index = 0,
    };
    const loc: SymbolLoc = .{ .file = null, .index = 0 };
    try wasm_bin.resolved_symbols.putNoClobber(allocator, loc, {});
    try wasm_bin.globals.putNoClobber(allocator, sym_name, loc);

    // For object files we will import the stack pointer symbol
    if (options.output_mode == .Obj) {
        symbol.setUndefined(true);
        try wasm_bin.imports.putNoClobber(
            allocator,
            .{ .file = null, .index = 0 },
            .{
                .module_name = try wasm_bin.string_table.put(allocator, wasm_bin.host_name),
                .name = sym_name,
                .kind = .{ .global = .{ .valtype = .i32, .mutable = true } },
            },
        );
    } else {
        symbol.setFlag(.WASM_SYM_VISIBILITY_HIDDEN);
        const global = try wasm_bin.wasm_globals.addOne(allocator);
        global.* = .{
            .global_type = .{
                .valtype = .i32,
                .mutable = true,
            },
            .init = .{ .i32_const = 0 },
        };
    }
    return wasm_bin;
}

pub fn createEmpty(gpa: Allocator, options: link.Options) !*Wasm {
    const self = try gpa.create(Wasm);
    errdefer gpa.destroy(self);
    self.* = .{
        .base = .{
            .tag = .wasm,
            .options = options,
            .file = null,
            .allocator = gpa,
        },
        .name = undefined,
    };
    const use_llvm = build_options.have_llvm and options.use_llvm;
    const use_stage1 = build_options.is_stage1 and options.use_stage1;
    if (use_llvm and !use_stage1) {
        self.llvm_object = try LlvmObject.create(gpa, options);
    }
    return self;
}

fn parseInputFiles(self: *Wasm, files: []const []const u8) !void {
    for (files) |path| {
        if (try self.parseObjectFile(path)) continue;
        log.warn("Unexpected file format at path: '{s}'", .{path});
    }
}

/// Parses the object file from given path. Returns true when the given file was an object
/// file and parsed successfully. Returns false when file is not an object file.
/// May return an error instead when parsing failed.
fn parseObjectFile(self: *Wasm, path: []const u8) !bool {
    const file = try fs.cwd().openFile(path, .{});
    errdefer file.close();

    var object = Object.create(self.base.allocator, file, path) catch |err| switch (err) {
        error.InvalidMagicByte, error.NotObjectFile => {
            log.warn("Self hosted linker does not support non-object file parsing: {s}", .{@errorName(err)});
            return false;
        },
        else => |e| return e,
    };
    errdefer object.deinit(self.base.allocator);
    try self.objects.append(self.base.allocator, object);
    return true;
}

fn resolveSymbolsInObject(self: *Wasm, object_index: u16) !void {
    const object: Object = self.objects.items[object_index];
    log.debug("Resolving symbols in object: '{s}'", .{object.name});

    for (object.symtable) |symbol, i| {
        const sym_index = @intCast(u32, i);
        const location: SymbolLoc = .{
            .file = object_index,
            .index = sym_index,
        };
        const sym_name = object.string_table.get(symbol.name);
        const sym_name_index = try self.string_table.put(self.base.allocator, sym_name);

        if (symbol.isLocal()) {
            if (symbol.isUndefined()) {
                log.err("Local symbols are not allowed to reference imports", .{});
                log.err("  symbol '{s}' defined in '{s}'", .{ sym_name, object.name });
                return error.undefinedLocal;
            }
            try self.resolved_symbols.putNoClobber(self.base.allocator, location, {});
            continue;
        }

        // TODO: locals are allowed to have duplicate symbol names
        // TODO: Store undefined symbols so we can verify at the end if they've all been found
        // if not, emit an error (unless --allow-undefined is enabled).
        const maybe_existing = try self.globals.getOrPut(self.base.allocator, sym_name_index);
        if (!maybe_existing.found_existing) {
            maybe_existing.value_ptr.* = location;
            try self.resolved_symbols.putNoClobber(self.base.allocator, location, {});
            continue;
        }

        const existing_loc = maybe_existing.value_ptr.*;
        const existing_sym: *Symbol = existing_loc.getSymbol(self);

        const existing_file_path = if (existing_loc.file) |file| blk: {
            break :blk self.objects.items[file].name;
        } else self.name;

        if (!existing_sym.isUndefined()) {
            if (!symbol.isUndefined()) {
                log.err("symbol '{s}' defined multiple times", .{sym_name});
                log.err("  first definition in '{s}'", .{existing_file_path});
                log.err("  next definition in '{s}'", .{object.name});
                return error.SymbolCollision;
            }

            continue; // Do not overwrite defined symbols with undefined symbols
        }

        // when both symbols are weak, we skip overwriting
        if (existing_sym.isWeak() and symbol.isWeak()) {
            continue;
        }

        // simply overwrite with the new symbol
        log.debug("Overwriting symbol '{s}'", .{sym_name});
        log.debug("  old definition in '{s}'", .{existing_file_path});
        log.debug("  new definition in '{s}'", .{object.name});
        try self.discarded.putNoClobber(self.base.allocator, maybe_existing.value_ptr.*, location);
        maybe_existing.value_ptr.* = location;
        try self.globals.put(self.base.allocator, sym_name_index, location);
        try self.resolved_symbols.put(self.base.allocator, location, {});
        assert(self.resolved_symbols.swapRemove(existing_loc));
    }
}

pub fn deinit(self: *Wasm) void {
    const gpa = self.base.allocator;
    if (build_options.have_llvm) {
        if (self.llvm_object) |llvm_object| llvm_object.destroy(gpa);
    }

    var decl_it = self.decls.keyIterator();
    while (decl_it.next()) |decl_ptr| {
        decl_ptr.*.link.wasm.deinit(gpa);
    }

    for (self.func_types.items) |*func_type| {
        func_type.deinit(gpa);
    }
    for (self.segment_info.items) |segment_info| {
        gpa.free(segment_info.name);
    }
    for (self.objects.items) |*object| {
        object.file.?.close();
        object.deinit(gpa);
    }

    self.decls.deinit(gpa);
    self.symbols.deinit(gpa);
    self.symbols_free_list.deinit(gpa);
    self.globals.deinit(gpa);
    self.resolved_symbols.deinit(gpa);
    self.discarded.deinit(gpa);
    self.symbol_atom.deinit(gpa);
    self.export_names.deinit(gpa);
    self.atoms.deinit(gpa);
    for (self.managed_atoms.items) |managed_atom| {
        managed_atom.deinit(gpa);
        gpa.destroy(managed_atom);
    }
    self.managed_atoms.deinit(gpa);
    self.segments.deinit(gpa);
    self.data_segments.deinit(gpa);
    self.segment_info.deinit(gpa);
    self.objects.deinit(gpa);

    // free output sections
    self.imports.deinit(gpa);
    self.func_types.deinit(gpa);
    self.functions.deinit(gpa);
    self.wasm_globals.deinit(gpa);
    self.function_table.deinit(gpa);
    self.tables.deinit(gpa);
    self.exports.deinit(gpa);

    self.string_table.deinit(gpa);
}

pub fn allocateDeclIndexes(self: *Wasm, decl: *Module.Decl) !void {
    if (self.llvm_object) |_| return;
    if (decl.link.wasm.sym_index != 0) return;

    try self.symbols.ensureUnusedCapacity(self.base.allocator, 1);
    try self.decls.putNoClobber(self.base.allocator, decl, {});

    const atom = &decl.link.wasm;

    var symbol: Symbol = .{
        .name = undefined, // will be set after updateDecl
        .flags = @enumToInt(Symbol.Flag.WASM_SYM_BINDING_LOCAL),
        .tag = undefined, // will be set after updateDecl
        .index = undefined, // will be set after updateDecl
    };

    if (self.symbols_free_list.popOrNull()) |index| {
        atom.sym_index = index;
        self.symbols.items[index] = symbol;
    } else {
        atom.sym_index = @intCast(u32, self.symbols.items.len);
        self.symbols.appendAssumeCapacity(symbol);
    }

    try self.resolved_symbols.putNoClobber(self.base.allocator, atom.symbolLoc(), {});
    try self.symbol_atom.putNoClobber(self.base.allocator, atom.symbolLoc(), atom);
}

pub fn updateFunc(self: *Wasm, module: *Module, func: *Module.Fn, air: Air, liveness: Liveness) !void {
    if (build_options.skip_non_native and builtin.object_format != .wasm) {
        @panic("Attempted to compile for object format that was disabled by build configuration");
    }
    if (build_options.have_llvm) {
        if (self.llvm_object) |llvm_object| return llvm_object.updateFunc(module, func, air, liveness);
    }
    const decl = func.owner_decl;
    assert(decl.link.wasm.sym_index != 0); // Must call allocateDeclIndexes()

    decl.link.wasm.clear(self.base.allocator);

    var code_writer = std.ArrayList(u8).init(self.base.allocator);
    defer code_writer.deinit();
    const result = try codegen.generateFunction(
        &self.base,
        decl.srcLoc(),
        func,
        air,
        liveness,
        &code_writer,
        .none,
    );

    const code = switch (result) {
        .appended => code_writer.items,
        .fail => |em| {
            decl.analysis = .codegen_failure;
            try module.failed_decls.put(module.gpa, decl, em);
            return;
        },
    };

    return self.finishUpdateDecl(decl, code);
}

// Generate code for the Decl, storing it in memory to be later written to
// the file on flush().
pub fn updateDecl(self: *Wasm, module: *Module, decl: *Module.Decl) !void {
    if (build_options.skip_non_native and builtin.object_format != .wasm) {
        @panic("Attempted to compile for object format that was disabled by build configuration");
    }
    if (build_options.have_llvm) {
        if (self.llvm_object) |llvm_object| return llvm_object.updateDecl(module, decl);
    }

    assert(decl.link.wasm.sym_index != 0); // Must call allocateDeclIndexes()

    decl.link.wasm.clear(self.base.allocator);

    if (decl.isExtern()) {
        return self.addOrUpdateImport(decl);
    }

    if (decl.val.castTag(.function)) |_| {
        return;
    } else if (decl.val.castTag(.extern_fn)) |_| {
        return;
    }
    const val = if (decl.val.castTag(.variable)) |payload| payload.data.init else decl.val;

    var code_writer = std.ArrayList(u8).init(self.base.allocator);
    defer code_writer.deinit();

    const res = try codegen.generateSymbol(
        &self.base,
        decl.srcLoc(),
        .{ .ty = decl.ty, .val = val },
        &code_writer,
        .none,
        .{ .parent_atom_index = decl.link.wasm.sym_index },
    );

    const code = switch (res) {
        .externally_managed => |x| x,
        .appended => code_writer.items,
        .fail => |em| {
            decl.analysis = .codegen_failure;
            try module.failed_decls.put(module.gpa, decl, em);
            return;
        },
    };

    return self.finishUpdateDecl(decl, code);
}

fn finishUpdateDecl(self: *Wasm, decl: *Module.Decl, code: []const u8) !void {
    if (decl.isExtern()) {
        return self.addOrUpdateImport(decl);
    }

    if (code.len == 0) return;
    const atom: *Atom = &decl.link.wasm;
    atom.size = @intCast(u32, code.len);
    atom.alignment = decl.ty.abiAlignment(self.base.options.target);
    const symbol = &self.symbols.items[atom.sym_index];

    const full_name = try decl.getFullyQualifiedName(self.base.allocator);
    defer self.base.allocator.free(full_name);
    symbol.name = try self.string_table.put(self.base.allocator, full_name);
    try atom.code.appendSlice(self.base.allocator, code);
}

/// Lowers a constant typed value to a local symbol and atom.
/// Returns the symbol index of the local
/// The given `decl` is the parent decl whom owns the constant.
pub fn lowerUnnamedConst(self: *Wasm, decl: *Module.Decl, tv: TypedValue) !u32 {
    assert(tv.ty.zigTypeTag() != .Fn); // cannot create local symbols for functions

    // Create and initialize a new local symbol and atom
    const local_index = decl.link.wasm.locals.items.len;
    const fqdn = try decl.getFullyQualifiedName(self.base.allocator);
    defer self.base.allocator.free(fqdn);
    const name = try std.fmt.allocPrintZ(self.base.allocator, "__unnamed_{s}_{d}", .{ fqdn, local_index });
    defer self.base.allocator.free(name);
    var symbol: Symbol = .{
        .name = try self.string_table.put(self.base.allocator, name),
        .flags = 0,
        .tag = .data,
        .index = undefined,
    };
    symbol.setFlag(.WASM_SYM_BINDING_LOCAL);

    const atom = try decl.link.wasm.locals.addOne(self.base.allocator);
    atom.* = Atom.empty;
    atom.alignment = tv.ty.abiAlignment(self.base.options.target);
    try self.symbols.ensureUnusedCapacity(self.base.allocator, 1);

    if (self.symbols_free_list.popOrNull()) |index| {
        atom.sym_index = index;
        self.symbols.items[index] = symbol;
    } else {
        atom.sym_index = @intCast(u32, self.symbols.items.len);
        self.symbols.appendAssumeCapacity(symbol);
    }
    try self.resolved_symbols.putNoClobber(self.base.allocator, atom.symbolLoc(), {});
    try self.symbol_atom.putNoClobber(self.base.allocator, atom.symbolLoc(), atom);

    var value_bytes = std.ArrayList(u8).init(self.base.allocator);
    defer value_bytes.deinit();

    const module = self.base.options.module.?;
    const result = try codegen.generateSymbol(
        &self.base,
        decl.srcLoc(),
        tv,
        &value_bytes,
        .none,
        .{
            .parent_atom_index = atom.sym_index,
            .addend = null,
        },
    );
    const code = switch (result) {
        .externally_managed => |x| x,
        .appended => value_bytes.items,
        .fail => |em| {
            decl.analysis = .codegen_failure;
            try module.failed_decls.put(module.gpa, decl, em);
            return error.AnalysisFail;
        },
    };

    atom.size = @intCast(u32, code.len);
    try atom.code.appendSlice(self.base.allocator, code);
    return atom.sym_index;
}

/// For a given decl, find the given symbol index's atom, and create a relocation for the type.
/// Returns the given pointer address
pub fn getDeclVAddr(
    self: *Wasm,
    decl: *const Module.Decl,
    reloc_info: link.File.RelocInfo,
) !u64 {
    const target_symbol_index = decl.link.wasm.sym_index;
    assert(target_symbol_index != 0);
    assert(reloc_info.parent_atom_index != 0);
    const atom = self.symbol_atom.get(.{ .file = null, .index = reloc_info.parent_atom_index }).?;
    const is_wasm32 = self.base.options.target.cpu.arch == .wasm32;
    if (decl.ty.zigTypeTag() == .Fn) {
        assert(reloc_info.addend == 0); // addend not allowed for function relocations
        // We found a function pointer, so add it to our table,
        // as function pointers are not allowed to be stored inside the data section.
        // They are instead stored in a function table which are called by index.
        try self.addTableFunction(target_symbol_index);
        try atom.relocs.append(self.base.allocator, .{
            .index = target_symbol_index,
            .offset = @intCast(u32, reloc_info.offset),
            .relocation_type = if (is_wasm32) .R_WASM_TABLE_INDEX_I32 else .R_WASM_TABLE_INDEX_I64,
        });
    } else {
        try atom.relocs.append(self.base.allocator, .{
            .index = target_symbol_index,
            .offset = @intCast(u32, reloc_info.offset),
            .relocation_type = if (is_wasm32) .R_WASM_MEMORY_ADDR_I32 else .R_WASM_MEMORY_ADDR_I64,
            .addend = reloc_info.addend,
        });
    }
    // we do not know the final address at this point,
    // as atom allocation will determine the address and relocations
    // will calculate and rewrite this. Therefore, we simply return the symbol index
    // that was targeted.
    return target_symbol_index;
}

pub fn deleteExport(self: *Wasm, exp: Export) void {
    if (self.llvm_object) |_| return;
    const sym_index = exp.sym_index orelse return;
    const loc: SymbolLoc = .{ .file = null, .index = sym_index };
    const symbol = loc.getSymbol(self);
    const symbol_name = self.string_table.get(symbol.name);
    log.debug("Deleting export for decl '{s}'", .{symbol_name});
    if (self.export_names.fetchRemove(loc)) |kv| {
        assert(self.globals.remove(kv.value));
    } else {
        assert(self.globals.remove(symbol.name));
    }
}

pub fn updateDeclExports(
    self: *Wasm,
    module: *Module,
    decl: *const Module.Decl,
    exports: []const *Module.Export,
) !void {
    if (build_options.skip_non_native and builtin.object_format != .wasm) {
        @panic("Attempted to compile for object format that was disabled by build configuration");
    }
    if (build_options.have_llvm) {
        if (self.llvm_object) |llvm_object| return llvm_object.updateDeclExports(module, decl, exports);
    }

    for (exports) |exp| {
        if (exp.options.section) |section| {
            try module.failed_exports.putNoClobber(module.gpa, exp, try Module.ErrorMsg.create(
                module.gpa,
                decl.srcLoc(),
                "Unimplemented: ExportOptions.section '{s}'",
                .{section},
            ));
            continue;
        }

        const export_name = try self.string_table.put(self.base.allocator, exp.options.name);
        if (self.globals.getPtr(export_name)) |existing_loc| {
            if (existing_loc.index == decl.link.wasm.sym_index) continue;
            const existing_sym: Symbol = existing_loc.getSymbol(self).*;

            const exp_is_weak = exp.options.linkage == .Internal or exp.options.linkage == .Weak;
            // When both the to-bo-exported symbol and the already existing symbol
            // are strong symbols, we have a linker error.
            // In the other case we replace one with the other.
            if (!exp_is_weak and !existing_sym.isWeak()) {
                try module.failed_exports.put(module.gpa, exp, try Module.ErrorMsg.create(
                    module.gpa,
                    decl.srcLoc(),
                    \\LinkError: symbol '{s}' defined multiple times
                    \\  first definition in '{s}'
                    \\  next definition in '{s}'
                ,
                    .{ exp.options.name, self.name, self.name },
                ));
                continue;
            } else if (exp_is_weak) {
                continue; // to-be-exported symbol is weak, so we keep the existing symbol
            } else {
                existing_loc.index = decl.link.wasm.sym_index;
                existing_loc.file = null;
                exp.link.wasm.sym_index = existing_loc.index;
            }
        }

        const sym_index = exp.exported_decl.link.wasm.sym_index;
        const sym_loc = exp.exported_decl.link.wasm.symbolLoc();
        const symbol = sym_loc.getSymbol(self);
        switch (exp.options.linkage) {
            .Internal => {
                symbol.setFlag(.WASM_SYM_VISIBILITY_HIDDEN);
                symbol.setFlag(.WASM_SYM_BINDING_WEAK);
            },
            .Weak => {
                symbol.setFlag(.WASM_SYM_BINDING_WEAK);
            },
            .Strong => {}, // symbols are strong by default
            .LinkOnce => {
                try module.failed_exports.putNoClobber(module.gpa, exp, try Module.ErrorMsg.create(
                    module.gpa,
                    decl.srcLoc(),
                    "Unimplemented: LinkOnce",
                    .{},
                ));
                continue;
            },
        }
        // Ensure the symbol will be exported using the given name
        if (!mem.eql(u8, exp.options.name, sym_loc.getName(self))) {
            try self.export_names.put(self.base.allocator, sym_loc, export_name);
        }

        symbol.setGlobal(true);
        try self.globals.put(
            self.base.allocator,
            export_name,
            sym_loc,
        );

        // if the symbol was previously undefined, remove it as an import
        _ = self.imports.remove(sym_loc);
        exp.link.wasm.sym_index = sym_index;
    }
}

pub fn freeDecl(self: *Wasm, decl: *Module.Decl) void {
    if (build_options.have_llvm) {
        if (self.llvm_object) |llvm_object| return llvm_object.freeDecl(decl);
    }
    const atom = &decl.link.wasm;
    self.symbols_free_list.append(self.base.allocator, atom.sym_index) catch {};
    _ = self.decls.remove(decl);
    self.symbols.items[atom.sym_index].tag = .dead;
    for (atom.locals.items) |local_atom| {
        const local_symbol = &self.symbols.items[local_atom.sym_index];
        local_symbol.tag = .dead; // also for any local symbol
        self.symbols_free_list.append(self.base.allocator, local_atom.sym_index) catch {};
        assert(self.resolved_symbols.swapRemove(local_atom.symbolLoc()));
        assert(self.symbol_atom.remove(local_atom.symbolLoc()));
    }

    if (decl.isExtern()) {
        assert(self.imports.remove(atom.symbolLoc()));
    }
    assert(self.resolved_symbols.swapRemove(atom.symbolLoc()));
    assert(self.symbol_atom.remove(atom.symbolLoc()));
    atom.deinit(self.base.allocator);
}

/// Appends a new entry to the indirect function table
pub fn addTableFunction(self: *Wasm, symbol_index: u32) !void {
    const index = @intCast(u32, self.function_table.count());
    try self.function_table.put(self.base.allocator, symbol_index, index);
}

/// Assigns indexes to all indirect functions.
/// Starts at offset 1, where the value `0` represents an unresolved function pointer
/// or null-pointer
fn mapFunctionTable(self: *Wasm) void {
    var it = self.function_table.valueIterator();
    var index: u32 = 1;
    while (it.next()) |value_ptr| : (index += 1) {
        value_ptr.* = index;
    }
}

fn addOrUpdateImport(self: *Wasm, decl: *Module.Decl) !void {
    // For the import name itself, we use the decl's name, rather than the fully qualified name
    const decl_name_index = try self.string_table.put(self.base.allocator, mem.sliceTo(decl.name, 0));
    const symbol_index = decl.link.wasm.sym_index;
    const symbol: *Symbol = &self.symbols.items[symbol_index];
    symbol.setUndefined(true);
    symbol.setGlobal(true);
    try self.globals.putNoClobber(
        self.base.allocator,
        decl_name_index,
        .{ .file = null, .index = symbol_index },
    );
    try self.resolved_symbols.put(self.base.allocator, .{ .file = null, .index = symbol_index }, {});

    switch (decl.ty.zigTypeTag()) {
        .Fn => {
            const gop = try self.imports.getOrPut(self.base.allocator, .{ .index = symbol_index, .file = null });
            const module_name = if (decl.getExternFn().?.lib_name) |lib_name| blk: {
                break :blk mem.sliceTo(lib_name, 0);
            } else self.host_name;
            if (!gop.found_existing) {
                gop.value_ptr.* = .{
                    .module_name = try self.string_table.put(self.base.allocator, module_name),
                    .name = decl_name_index,
                    .kind = .{ .function = decl.fn_link.wasm.type_index },
                };
            }
        },
        else => @panic("TODO: Implement undefined symbols for non-function declarations"),
    }
}

const Kind = union(enum) {
    data: void,
    function: FnData,
};

/// Parses an Atom and inserts its metadata into the corresponding sections.
fn parseAtom(self: *Wasm, atom: *Atom, kind: Kind) !void {
    const symbol = (SymbolLoc{ .file = null, .index = atom.sym_index }).getSymbol(self);
    const final_index: u32 = switch (kind) {
        .function => |fn_data| result: {
            const index = @intCast(u32, self.functions.items.len + self.imported_functions_count);
            try self.functions.append(self.base.allocator, .{ .type_index = fn_data.type_index });
            symbol.tag = .function;
            symbol.index = index;

            if (self.code_section_index == null) {
                self.code_section_index = @intCast(u32, self.segments.items.len);
                try self.segments.append(self.base.allocator, .{
                    .alignment = atom.alignment,
                    .size = atom.size,
                    .offset = 0,
                });
            }

            break :result self.code_section_index.?;
        },
        .data => result: {
            // TODO: Add mutables global decls to .bss section instead
            const segment_name = try std.mem.concat(self.base.allocator, u8, &.{
                ".rodata.",
                self.string_table.get(symbol.name),
            });
            errdefer self.base.allocator.free(segment_name);
            const segment_info: types.Segment = .{
                .name = segment_name,
                .alignment = atom.alignment,
                .flags = 0,
            };
            symbol.tag = .data;

            const should_merge = self.base.options.output_mode != .Obj;
            const gop = try self.data_segments.getOrPut(self.base.allocator, segment_info.outputName(should_merge));
            if (gop.found_existing) {
                const index = gop.value_ptr.*;
                self.segments.items[index].size += atom.size;

                // segment indexes can be off by 1 due to also containing a segment
                // for the code section, so we must check if the existing segment
                // is larger than that of the code section, and substract the index by 1 in such case.
                const info_add = if (self.code_section_index) |idx| blk: {
                    if (idx < index) break :blk @as(u32, 1);
                    break :blk 0;
                } else @as(u32, 0);
                symbol.index = index - info_add;
                // segment info already exists, so free its memory
                self.base.allocator.free(segment_name);
                break :result index;
            } else {
                const index = @intCast(u32, self.segments.items.len);
                try self.segments.append(self.base.allocator, .{
                    .alignment = atom.alignment,
                    .size = 0,
                    .offset = 0,
                });
                gop.value_ptr.* = index;

                const info_index = @intCast(u32, self.segment_info.items.len);
                try self.segment_info.append(self.base.allocator, segment_info);
                symbol.index = info_index;
                break :result index;
            }
        },
    };

    const segment: *Segment = &self.segments.items[final_index];
    segment.alignment = std.math.max(segment.alignment, atom.alignment);
    segment.size = std.mem.alignForwardGeneric(
        u32,
        std.mem.alignForwardGeneric(u32, segment.size, atom.alignment) + atom.size,
        segment.alignment,
    );

    if (self.atoms.getPtr(final_index)) |last| {
        last.*.next = atom;
        atom.prev = last.*;
        last.* = atom;
    } else {
        try self.atoms.putNoClobber(self.base.allocator, final_index, atom);
    }
}

fn allocateAtoms(self: *Wasm) !void {
    var it = self.atoms.valueIterator();
    while (it.next()) |current_atom| {
        var atom: *Atom = current_atom.*.getFirst();
        var offset: u32 = 0;
        while (true) {
            offset = std.mem.alignForwardGeneric(u32, offset, atom.alignment);
            atom.offset = offset;
            const symbol_loc = atom.symbolLoc();
            log.debug("Atom '{s}' allocated from 0x{x:0>8} to 0x{x:0>8} size={d}", .{
                symbol_loc.getName(self),
                offset,
                offset + atom.size,
                atom.size,
            });
            offset += atom.size;
            self.symbol_atom.putAssumeCapacity(atom.symbolLoc(), atom); // Update atom pointers
            atom = atom.next orelse break;
        }
    }
}

fn setupImports(self: *Wasm) !void {
    log.debug("Merging imports", .{});
    var discarded_it = self.discarded.keyIterator();
    while (discarded_it.next()) |discarded| {
        if (discarded.file == null) {
            // remove an import if it was resolved
            if (self.imports.remove(discarded.*)) {
                log.debug("Removed symbol '{s}' as an import", .{
                    discarded.getName(self),
                });
            }
        }
    }

    for (self.resolved_symbols.keys()) |symbol_loc| {
        if (symbol_loc.file == null) {
            // imports generated by Zig code are already in the `import` section
            continue;
        }

        const symbol = symbol_loc.getSymbol(self);
        if (symbol.tag == .data or !symbol.requiresImport()) {
            continue;
        }

        log.debug("Symbol '{s}' will be imported from the host", .{symbol_loc.getName(self)});
        const object = self.objects.items[symbol_loc.file.?];
        const import = object.findImport(symbol.tag.externalType(), symbol.index);

        // We copy the import to a new import to ensure the names contain references
        // to the internal string table, rather than of the object file.
        var new_imp: types.Import = .{
            .module_name = try self.string_table.put(self.base.allocator, object.string_table.get(import.module_name)),
            .name = try self.string_table.put(self.base.allocator, object.string_table.get(import.name)),
            .kind = import.kind,
        };
        // TODO: De-duplicate imports when they contain the same names and type
        try self.imports.putNoClobber(self.base.allocator, symbol_loc, new_imp);
    }

    // Assign all indexes of the imports to their representing symbols
    var function_index: u32 = 0;
    var global_index: u32 = 0;
    var table_index: u32 = 0;
    var it = self.imports.iterator();
    while (it.next()) |entry| {
        const symbol = entry.key_ptr.*.getSymbol(self);
        const import: types.Import = entry.value_ptr.*;
        switch (import.kind) {
            .function => {
                symbol.index = function_index;
                function_index += 1;
            },
            .global => {
                symbol.index = global_index;
                global_index += 1;
            },
            .table => {
                symbol.index = table_index;
                table_index += 1;
            },
            else => unreachable,
        }
    }
    self.imported_functions_count = function_index;
    self.imported_globals_count = global_index;
    self.imported_tables_count = table_index;

    log.debug("Merged ({d}) functions, ({d}) globals, and ({d}) tables into import section", .{
        function_index,
        global_index,
        table_index,
    });
}

/// Takes the global, function and table section from each linked object file
/// and merges it into a single section for each.
fn mergeSections(self: *Wasm) !void {
    // append the indirect function table if initialized
    if (self.string_table.getOffset("__indirect_function_table")) |offset| {
        const sym_loc = self.globals.get(offset).?;
        const table: wasm.Table = .{
            .limits = .{ .min = @intCast(u32, self.function_table.count()), .max = null },
            .reftype = .funcref,
        };
        sym_loc.getSymbol(self).index = @intCast(u32, self.tables.items.len) + self.imported_tables_count;
        try self.tables.append(self.base.allocator, table);
    }

    for (self.resolved_symbols.keys()) |sym_loc| {
        if (sym_loc.file == null) {
            // Zig code-generated symbols are already within the sections and do not
            // require to be merged
            continue;
        }

        const object = self.objects.items[sym_loc.file.?];
        const symbol = &object.symtable[sym_loc.index];
        if (symbol.isUndefined() or (symbol.tag != .function and symbol.tag != .global and symbol.tag != .table)) {
            // Skip undefined symbols as they go in the `import` section
            // Also skip symbols that do not need to have a section merged.
            continue;
        }

        const offset = object.importedCountByKind(symbol.tag.externalType());
        const index = symbol.index - offset;
        switch (symbol.tag) {
            .function => {
                const original_func = object.functions[index];
                symbol.index = @intCast(u32, self.functions.items.len) + self.imported_functions_count;
                try self.functions.append(self.base.allocator, original_func);
            },
            .global => {
                const original_global = object.globals[index];
                symbol.index = @intCast(u32, self.wasm_globals.items.len) + self.imported_globals_count;
                try self.wasm_globals.append(self.base.allocator, original_global);
            },
            .table => {
                const original_table = object.tables[index];
                symbol.index = @intCast(u32, self.tables.items.len) + self.imported_tables_count;
                try self.tables.append(self.base.allocator, original_table);
            },
            else => {},
        }
    }

    log.debug("Merged ({d}) functions", .{self.functions.items.len});
    log.debug("Merged ({d}) globals", .{self.wasm_globals.items.len});
    log.debug("Merged ({d}) tables", .{self.tables.items.len});
}

/// Merges function types of all object files into the final
/// 'types' section, while assigning the type index to the representing
/// section (import, export, function).
fn mergeTypes(self: *Wasm) !void {
    for (self.resolved_symbols.keys()) |sym_loc| {
        if (sym_loc.file == null) {
            // zig code-generated symbols are already present in final type section
            continue;
        }
        const object = self.objects.items[sym_loc.file.?];
        const symbol = object.symtable[sym_loc.index];
        if (symbol.tag != .function) {
            // Only functions have types
            continue;
        }

        if (symbol.isUndefined()) {
            log.debug("Adding type from extern function '{s}'", .{sym_loc.getName(self)});
            const import: *types.Import = self.imports.getPtr(sym_loc).?;
            const original_type = object.func_types[import.kind.function];
            import.kind.function = try self.putOrGetFuncType(original_type);
        } else {
            log.debug("Adding type from function '{s}'", .{sym_loc.getName(self)});
            const func = &self.functions.items[symbol.index - self.imported_functions_count];
            func.type_index = try self.putOrGetFuncType(object.func_types[func.type_index]);
        }
    }
    log.debug("Completed merging and deduplicating types. Total count: ({d})", .{self.func_types.items.len});
}

fn setupExports(self: *Wasm) !void {
    if (self.base.options.output_mode == .Obj) return;
    log.debug("Building exports from symbols", .{});

    for (self.resolved_symbols.keys()) |sym_loc| {
        const symbol = sym_loc.getSymbol(self);
        if (!symbol.isExported()) continue;

        const sym_name = sym_loc.getName(self);
        const export_name = if (self.export_names.get(sym_loc)) |name| name else symbol.name;
        const exp: types.Export = .{
            .name = export_name,
            .kind = symbol.tag.externalType(),
            .index = symbol.index,
        };
        log.debug("Exporting symbol '{s}' as '{s}' at index: ({d})", .{ sym_name, self.string_table.get(exp.name), exp.index });
        try self.exports.append(self.base.allocator, exp);
    }

    log.debug("Completed building exports. Total count: ({d})", .{self.exports.items.len});
}

fn setupStart(self: *Wasm) !void {
    const entry_name = self.base.options.entry orelse "_start";

    const symbol_name_offset = self.string_table.getOffset(entry_name) orelse {
        if (self.base.options.output_mode == .Exe) {
            if (self.base.options.wasi_exec_model == .reactor) return; // Not required for reactors
        } else {
            return; // No entry point needed for non-executable wasm files
        }
        log.err("Entry symbol '{s}' missing", .{entry_name});
        return error.MissingSymbol;
    };

    const symbol_loc = self.globals.get(symbol_name_offset).?;
    const symbol = symbol_loc.getSymbol(self);
    if (symbol.tag != .function) {
        log.err("Entry symbol '{s}' is not a function", .{entry_name});
        return error.InvalidEntryKind;
    }

    // Ensure the symbol is exported so host environment can access it
    if (self.base.options.output_mode != .Obj) {
        symbol.setFlag(.WASM_SYM_EXPORTED);
    }
}

/// Sets up the memory section of the wasm module, as well as the stack.
fn setupMemory(self: *Wasm) !void {
    log.debug("Setting up memory layout", .{});
    const page_size = 64 * 1024;
    const stack_size = self.base.options.stack_size_override orelse page_size * 1;
    const stack_alignment = 16; // wasm's stack alignment as specified by tool-convention
    // Always place the stack at the start by default
    // unless the user specified the global-base flag
    var place_stack_first = true;
    var memory_ptr: u64 = if (self.base.options.global_base) |base| blk: {
        place_stack_first = false;
        break :blk base;
    } else 0;

    const is_obj = self.base.options.output_mode == .Obj;

    if (place_stack_first and !is_obj) {
        memory_ptr = std.mem.alignForwardGeneric(u64, memory_ptr, stack_alignment);
        memory_ptr += stack_size;
        // We always put the stack pointer global at index 0
        self.wasm_globals.items[0].init.i32_const = @bitCast(i32, @intCast(u32, memory_ptr));
    }

    var offset: u32 = @intCast(u32, memory_ptr);
    for (self.segments.items) |*segment, i| {
        // skip 'code' segments
        if (self.code_section_index) |index| {
            if (index == i) continue;
        }
        memory_ptr = std.mem.alignForwardGeneric(u64, memory_ptr, segment.alignment);
        memory_ptr += segment.size;
        segment.offset = offset;
        offset += segment.size;
    }

    if (!place_stack_first and !is_obj) {
        memory_ptr = std.mem.alignForwardGeneric(u64, memory_ptr, stack_alignment);
        memory_ptr += stack_size;
        self.wasm_globals.items[0].init.i32_const = @bitCast(i32, @intCast(u32, memory_ptr));
    }

    // Setup the max amount of pages
    // For now we only support wasm32 by setting the maximum allowed memory size 2^32-1
    const max_memory_allowed: u64 = (1 << 32) - 1;

    if (self.base.options.initial_memory) |initial_memory| {
        if (!std.mem.isAlignedGeneric(u64, initial_memory, page_size)) {
            log.err("Initial memory must be {d}-byte aligned", .{page_size});
            return error.MissAlignment;
        }
        if (memory_ptr > initial_memory) {
            log.err("Initial memory too small, must be at least {d} bytes", .{memory_ptr});
            return error.MemoryTooSmall;
        }
        if (initial_memory > max_memory_allowed) {
            log.err("Initial memory exceeds maximum memory {d}", .{max_memory_allowed});
            return error.MemoryTooBig;
        }
        memory_ptr = initial_memory;
    }

    // In case we do not import memory, but define it ourselves,
    // set the minimum amount of pages on the memory section.
    self.memories.limits.min = @intCast(u32, std.mem.alignForwardGeneric(u64, memory_ptr, page_size) / page_size);
    log.debug("Total memory pages: {d}", .{self.memories.limits.min});

    if (self.base.options.max_memory) |max_memory| {
        if (!std.mem.isAlignedGeneric(u64, max_memory, page_size)) {
            log.err("Maximum memory must be {d}-byte aligned", .{page_size});
            return error.MissAlignment;
        }
        if (memory_ptr > max_memory) {
            log.err("Maxmimum memory too small, must be at least {d} bytes", .{memory_ptr});
            return error.MemoryTooSmall;
        }
        if (max_memory > max_memory_allowed) {
            log.err("Maximum memory exceeds maxmium amount {d}", .{max_memory_allowed});
            return error.MemoryTooBig;
        }
        self.memories.limits.max = @intCast(u32, max_memory / page_size);
        log.debug("Maximum memory pages: {d}", .{self.memories.limits.max});
    }
}

/// From a given object's index and the index of the segment, returns the corresponding
/// index of the segment within the final data section. When the segment does not yet
/// exist, a new one will be initialized and appended. The new index will be returned in that case.
pub fn getMatchingSegment(self: *Wasm, object_index: u16, relocatable_index: u32) !u32 {
    const object: Object = self.objects.items[object_index];
    const relocatable_data = object.relocatable_data[relocatable_index];
    const index = @intCast(u32, self.segments.items.len);

    switch (relocatable_data.type) {
        .data => {
            const segment_info = object.segment_info[relocatable_data.index];
            const merge_segment = self.base.options.output_mode != .Obj;
            const result = try self.data_segments.getOrPut(self.base.allocator, segment_info.outputName(merge_segment));
            if (!result.found_existing) {
                result.value_ptr.* = index;
                try self.segments.append(self.base.allocator, .{
                    .alignment = 1,
                    .size = 0,
                    .offset = 0,
                });
                return index;
            } else return result.value_ptr.*;
        },
        .code => return self.code_section_index orelse blk: {
            self.code_section_index = index;
            try self.segments.append(self.base.allocator, .{
                .alignment = 1,
                .size = 0,
                .offset = 0,
            });
            break :blk index;
        },
        .custom => return error.@"TODO: Custom section relocations for wasm",
    }
}

fn resetState(self: *Wasm) void {
    for (self.segment_info.items) |*segment_info| {
        self.base.allocator.free(segment_info.name);
    }
    var decl_it = self.decls.keyIterator();
    while (decl_it.next()) |decl| {
        const atom = &decl.*.link.wasm;
        atom.next = null;
        atom.prev = null;

        for (atom.locals.items) |*local_atom| {
            local_atom.next = null;
            local_atom.prev = null;
        }
    }
    self.functions.clearRetainingCapacity();
    self.exports.clearRetainingCapacity();
    self.segments.clearRetainingCapacity();
    self.segment_info.clearRetainingCapacity();
    self.data_segments.clearRetainingCapacity();
    self.atoms.clearRetainingCapacity();
    self.symbol_atom.clearRetainingCapacity();
    self.code_section_index = null;
}

pub fn flush(self: *Wasm, comp: *Compilation) !void {
    if (self.base.options.emit == null) {
        if (build_options.have_llvm) {
            if (self.llvm_object) |llvm_object| {
                return try llvm_object.flushModule(comp);
            }
        }
        return;
    }
    if (build_options.have_llvm and self.base.options.use_lld) {
        return self.linkWithLLD(comp);
    } else {
        return self.flushModule(comp);
    }
}

pub fn flushModule(self: *Wasm, comp: *Compilation) !void {
    const tracy = trace(@src());
    defer tracy.end();

    if (build_options.have_llvm) {
        if (self.llvm_object) |llvm_object| {
            return try llvm_object.flushModule(comp);
        }
    }

    // The amount of sections that will be written
    var section_count: u32 = 0;
    // Index of the code section. Used to tell relocation table where the section lives.
    var code_section_index: ?u32 = null;
    // Index of the data section. Used to tell relocation table where the section lives.
    var data_section_index: ?u32 = null;

    // Used for all temporary memory allocated during flushin
    var arena_instance = std.heap.ArenaAllocator.init(self.base.allocator);
    defer arena_instance.deinit();
    const arena = arena_instance.allocator();

    // Positional arguments to the linker such as object files and static archives.
    var positionals = std.ArrayList([]const u8).init(arena);
    try positionals.ensureUnusedCapacity(self.base.options.objects.len);

    for (self.base.options.objects) |object| {
        positionals.appendAssumeCapacity(object.path);
    }

    for (comp.c_object_table.keys()) |c_object| {
        try positionals.append(c_object.status.success.object_path);
    }
    // TODO: Also link with other objects such as compiler-rt
    try self.parseInputFiles(positionals.items);

    var object_index: u16 = 0;
    while (object_index < self.objects.items.len) : (object_index += 1) {
        try self.resolveSymbolsInObject(object_index);
    }

    // When we finish/error we reset the state of the linker
    // So we can rebuild the binary file on each incremental update
    defer self.resetState();
    try self.setupStart();
    try self.setupImports();
    var decl_it = self.decls.keyIterator();
    while (decl_it.next()) |decl| {
        if (decl.*.isExtern()) continue;
        const atom = &decl.*.link.wasm;
        if (decl.*.ty.zigTypeTag() == .Fn) {
            try self.parseAtom(atom, .{ .function = decl.*.fn_link.wasm });
        } else {
            try self.parseAtom(atom, .data);
        }

        // also parse atoms for a decl's locals
        for (atom.locals.items) |*local_atom| {
            try self.parseAtom(local_atom, .data);
        }
    }

    while (object_index > 0) {
        object_index -= 1;
        try self.objects.items[object_index].parseIntoAtoms(self.base.allocator, object_index, self);
    }

    try self.setupMemory();
    try self.allocateAtoms();
    self.mapFunctionTable();
    try self.mergeSections();
    try self.mergeTypes();
    try self.setupExports();

    const file = self.base.file.?;
    const header_size = 5 + 1;
    const is_obj = self.base.options.output_mode == .Obj;

    // No need to rewrite the magic/version header
    try file.setEndPos(@sizeOf(@TypeOf(wasm.magic ++ wasm.version)));
    try file.seekTo(@sizeOf(@TypeOf(wasm.magic ++ wasm.version)));

    // Type section
    if (self.func_types.items.len != 0) {
        const header_offset = try reserveVecSectionHeader(file);
        const writer = file.writer();
        log.debug("Writing type section. Count: ({d})", .{self.func_types.items.len});
        for (self.func_types.items) |func_type| {
            try leb.writeULEB128(writer, wasm.function_type);
            try leb.writeULEB128(writer, @intCast(u32, func_type.params.len));
            for (func_type.params) |param_ty| try leb.writeULEB128(writer, wasm.valtype(param_ty));
            try leb.writeULEB128(writer, @intCast(u32, func_type.returns.len));
            for (func_type.returns) |ret_ty| try leb.writeULEB128(writer, wasm.valtype(ret_ty));
        }

        try writeVecSectionHeader(
            file,
            header_offset,
            .type,
            @intCast(u32, (try file.getPos()) - header_offset - header_size),
            @intCast(u32, self.func_types.items.len),
        );
        section_count += 1;
    }

    // Import section
    const import_memory = self.base.options.import_memory or is_obj;
    const import_table = self.base.options.import_table or is_obj;
    if (self.imports.count() != 0 or import_memory or import_table) {
        const header_offset = try reserveVecSectionHeader(file);
        const writer = file.writer();

        // import table is always first table so emit that first
        if (import_table) {
            const table_imp: types.Import = .{
                .module_name = try self.string_table.put(self.base.allocator, self.host_name),
                .name = try self.string_table.put(self.base.allocator, "__indirect_function_table"),
                .kind = .{
                    .table = .{
                        .limits = .{
                            .min = @intCast(u32, self.function_table.count()),
                            .max = null,
                        },
                        .reftype = .funcref,
                    },
                },
            };
            try self.emitImport(writer, table_imp);
        }

        var it = self.imports.iterator();
        while (it.next()) |entry| {
            assert(entry.key_ptr.*.getSymbol(self).isUndefined());
            const import = entry.value_ptr.*;
            try self.emitImport(writer, import);
        }

        if (import_memory) {
            const mem_imp: types.Import = .{
                .module_name = try self.string_table.put(self.base.allocator, self.host_name),
                .name = try self.string_table.put(self.base.allocator, "__linear_memory"),
                .kind = .{ .memory = self.memories.limits },
            };
            try self.emitImport(writer, mem_imp);
        }

        try writeVecSectionHeader(
            file,
            header_offset,
            .import,
            @intCast(u32, (try file.getPos()) - header_offset - header_size),
            @intCast(u32, self.imports.count() + @boolToInt(import_memory) + @boolToInt(import_table)),
        );
        section_count += 1;
    }

    // Function section
    if (self.functions.items.len != 0) {
        const header_offset = try reserveVecSectionHeader(file);
        const writer = file.writer();
        for (self.functions.items) |function| {
            try leb.writeULEB128(writer, function.type_index);
        }

        try writeVecSectionHeader(
            file,
            header_offset,
            .function,
            @intCast(u32, (try file.getPos()) - header_offset - header_size),
            @intCast(u32, self.functions.items.len),
        );
        section_count += 1;
    }

    // Table section
    const export_table = self.base.options.export_table;
    if (!import_table and self.function_table.count() != 0) {
        const header_offset = try reserveVecSectionHeader(file);
        const writer = file.writer();

        try leb.writeULEB128(writer, wasm.reftype(.funcref));
        try emitLimits(writer, .{
            .min = @intCast(u32, self.function_table.count()) + 1,
            .max = null,
        });

        try writeVecSectionHeader(
            file,
            header_offset,
            .table,
            @intCast(u32, (try file.getPos()) - header_offset - header_size),
            @as(u32, 1),
        );
        section_count += 1;
    }

    // Memory section
    if (!import_memory) {
        const header_offset = try reserveVecSectionHeader(file);
        const writer = file.writer();

        try emitLimits(writer, self.memories.limits);
        try writeVecSectionHeader(
            file,
            header_offset,
            .memory,
            @intCast(u32, (try file.getPos()) - header_offset - header_size),
            @as(u32, 1), // wasm currently only supports 1 linear memory segment
        );
        section_count += 1;
    }

    // Global section (used to emit stack pointer)
    if (self.wasm_globals.items.len > 0) {
        const header_offset = try reserveVecSectionHeader(file);
        const writer = file.writer();

        for (self.wasm_globals.items) |global| {
            try writer.writeByte(wasm.valtype(global.global_type.valtype));
            try writer.writeByte(@boolToInt(global.global_type.mutable));
            try emitInit(writer, global.init);
        }

        try writeVecSectionHeader(
            file,
            header_offset,
            .global,
            @intCast(u32, (try file.getPos()) - header_offset - header_size),
            @intCast(u32, self.wasm_globals.items.len),
        );
        section_count += 1;
    }

    // Export section
    if (self.exports.items.len != 0 or export_table or !import_memory) {
        const header_offset = try reserveVecSectionHeader(file);
        const writer = file.writer();
        for (self.exports.items) |exp| {
            const name = self.string_table.get(exp.name);
            try leb.writeULEB128(writer, @intCast(u32, name.len));
            try writer.writeAll(name);
            try leb.writeULEB128(writer, @enumToInt(exp.kind));
            try leb.writeULEB128(writer, exp.index);
        }

        if (export_table) {
            try leb.writeULEB128(writer, @intCast(u32, "__indirect_function_table".len));
            try writer.writeAll("__indirect_function_table");
            try writer.writeByte(wasm.externalKind(.table));
            try leb.writeULEB128(writer, @as(u32, 0)); // function table is always the first table
        }

        if (!import_memory) {
            try leb.writeULEB128(writer, @intCast(u32, "memory".len));
            try writer.writeAll("memory");
            try writer.writeByte(wasm.externalKind(.memory));
            try leb.writeULEB128(writer, @as(u32, 0));
        }

        try writeVecSectionHeader(
            file,
            header_offset,
            .@"export",
            @intCast(u32, (try file.getPos()) - header_offset - header_size),
            @intCast(u32, self.exports.items.len) + @boolToInt(export_table) + @boolToInt(!import_memory),
        );
        section_count += 1;
    }

    // element section (function table)
    if (self.function_table.count() > 0) {
        const header_offset = try reserveVecSectionHeader(file);
        const writer = file.writer();

        var flags: u32 = 0x2; // Yes we have a table
        try leb.writeULEB128(writer, flags);
        try leb.writeULEB128(writer, @as(u32, 0)); // index of that table. TODO: Store synthetic symbols
        try emitInit(writer, .{ .i32_const = 1 }); // We start at index 1, so unresolved function pointers are invalid
        try leb.writeULEB128(writer, @as(u8, 0));
        try leb.writeULEB128(writer, @intCast(u32, self.function_table.count()));
        var symbol_it = self.function_table.keyIterator();
        while (symbol_it.next()) |symbol_index_ptr| {
            try leb.writeULEB128(writer, self.symbols.items[symbol_index_ptr.*].index);
        }

        try writeVecSectionHeader(
            file,
            header_offset,
            .element,
            @intCast(u32, (try file.getPos()) - header_offset - header_size),
            @as(u32, 1),
        );
        section_count += 1;
    }

    // Code section
    if (self.code_section_index) |code_index| {
        const header_offset = try reserveVecSectionHeader(file);
        const writer = file.writer();
        var atom: *Atom = self.atoms.get(code_index).?.getFirst();
        while (true) {
            if (!is_obj) {
                try atom.resolveRelocs(self);
            }
            try leb.writeULEB128(writer, atom.size);
            try writer.writeAll(atom.code.items);
            atom = atom.next orelse break;
        }
        try writeVecSectionHeader(
            file,
            header_offset,
            .code,
            @intCast(u32, (try file.getPos()) - header_offset - header_size),
            @intCast(u32, self.functions.items.len),
        );
        code_section_index = section_count;
        section_count += 1;
    }

    // Data section
    if (self.data_segments.count() != 0) {
        const header_offset = try reserveVecSectionHeader(file);
        const writer = file.writer();

        var it = self.data_segments.iterator();
        var segment_count: u32 = 0;
        while (it.next()) |entry| {
            // do not output 'bss' section unless we import memory and therefore
            // want to guarantee the data is zero initialized
            if (std.mem.eql(u8, entry.key_ptr.*, ".bss") and !import_memory) continue;
            segment_count += 1;
            const atom_index = entry.value_ptr.*;
            var atom: *Atom = self.atoms.getPtr(atom_index).?.*.getFirst();
            var segment = self.segments.items[atom_index];

            // flag and index to memory section (currently, there can only be 1 memory section in wasm)
            try leb.writeULEB128(writer, @as(u32, 0));
            // offset into data section
            try emitInit(writer, .{ .i32_const = @bitCast(i32, segment.offset) });
            try leb.writeULEB128(writer, segment.size);

            // fill in the offset table and the data segments
            var current_offset: u32 = 0;
            while (true) {
                if (!is_obj) {
                    try atom.resolveRelocs(self);
                }

                // Pad with zeroes to ensure all segments are aligned
                if (current_offset != atom.offset) {
                    const diff = atom.offset - current_offset;
                    try writer.writeByteNTimes(0, diff);
                    current_offset += diff;
                }
                assert(current_offset == atom.offset);
                assert(atom.code.items.len == atom.size);
                try writer.writeAll(atom.code.items);

                current_offset += atom.size;
                if (atom.next) |next| {
                    atom = next;
                } else {
                    // also pad with zeroes when last atom to ensure
                    // segments are aligned.
                    if (current_offset != segment.size) {
                        try writer.writeByteNTimes(0, segment.size - current_offset);
                        current_offset += segment.size - current_offset;
                    }
                    break;
                }
            }
            assert(current_offset == segment.size);
        }

        try writeVecSectionHeader(
            file,
            header_offset,
            .data,
            @intCast(u32, (try file.getPos()) - header_offset - header_size),
            @intCast(u32, segment_count),
        );
        data_section_index = section_count;
        section_count += 1;
    }

    if (is_obj) {
        // relocations need to point to the index of a symbol in the final symbol table. To save memory,
        // we never store all symbols in a single table, but store a location reference instead.
        // This means that for a relocatable object file, we need to generate one and provide it to the relocation sections.
        var symbol_table = std.AutoArrayHashMap(SymbolLoc, u32).init(arena);
        try self.emitLinkSection(file, arena, &symbol_table);
        if (code_section_index) |code_index| {
            try self.emitCodeRelocations(file, arena, code_index, symbol_table);
        }
        if (data_section_index) |data_index| {
            try self.emitDataRelocations(file, arena, data_index, symbol_table);
        }
    } else {
        try self.emitNameSection(file, arena);
    }
}

fn emitNameSection(self: *Wasm, file: fs.File, arena: Allocator) !void {
    const Name = struct {
        index: u32,
        name: []const u8,

        fn lessThan(context: void, lhs: @This(), rhs: @This()) bool {
            _ = context;
            return lhs.index < rhs.index;
        }
    };

    var funcs = try std.ArrayList(Name).initCapacity(arena, self.functions.items.len + self.imported_functions_count);
    var globals = try std.ArrayList(Name).initCapacity(arena, self.wasm_globals.items.len + self.imported_globals_count);
    var segments = try std.ArrayList(Name).initCapacity(arena, self.data_segments.count());

    for (self.resolved_symbols.keys()) |sym_loc| {
        const symbol = sym_loc.getSymbol(self).*;
        const name = if (symbol.isUndefined()) blk: {
            break :blk self.string_table.get(self.imports.get(sym_loc).?.name);
        } else sym_loc.getName(self);
        switch (symbol.tag) {
            .function => funcs.appendAssumeCapacity(.{ .index = symbol.index, .name = name }),
            .global => globals.appendAssumeCapacity(.{ .index = symbol.index, .name = name }),
            else => {},
        }
    }
    // data segments are already 'ordered'
    for (self.data_segments.keys()) |key, index| {
        segments.appendAssumeCapacity(.{ .index = @intCast(u32, index), .name = key });
    }

    std.sort.sort(Name, funcs.items, {}, Name.lessThan);
    std.sort.sort(Name, globals.items, {}, Name.lessThan);

    const header_offset = try reserveCustomSectionHeader(file);
    const writer = file.writer();
    try leb.writeULEB128(writer, @intCast(u32, "name".len));
    try writer.writeAll("name");

    try self.emitNameSubsection(.function, funcs.items, writer);
    try self.emitNameSubsection(.global, globals.items, writer);
    try self.emitNameSubsection(.data_segment, segments.items, writer);

    try writeCustomSectionHeader(
        file,
        header_offset,
        @intCast(u32, (try file.getPos()) - header_offset - 6),
    );
}

fn emitNameSubsection(self: *Wasm, section_id: std.wasm.NameSubsection, names: anytype, writer: anytype) !void {
    // We must emit subsection size, so first write to a temporary list
    var section_list = std.ArrayList(u8).init(self.base.allocator);
    defer section_list.deinit();
    const sub_writer = section_list.writer();

    try leb.writeULEB128(sub_writer, @intCast(u32, names.len));
    for (names) |name| {
        log.debug("Emit symbol '{s}' type({s})", .{ name.name, @tagName(section_id) });
        try leb.writeULEB128(sub_writer, name.index);
        try leb.writeULEB128(sub_writer, @intCast(u32, name.name.len));
        try sub_writer.writeAll(name.name);
    }

    // From now, write to the actual writer
    try leb.writeULEB128(writer, @enumToInt(section_id));
    try leb.writeULEB128(writer, @intCast(u32, section_list.items.len));
    try writer.writeAll(section_list.items);
}

fn emitLimits(writer: anytype, limits: wasm.Limits) !void {
    try leb.writeULEB128(writer, @boolToInt(limits.max != null));
    try leb.writeULEB128(writer, limits.min);
    if (limits.max) |max| {
        try leb.writeULEB128(writer, max);
    }
}

fn emitInit(writer: anytype, init_expr: wasm.InitExpression) !void {
    switch (init_expr) {
        .i32_const => |val| {
            try writer.writeByte(wasm.opcode(.i32_const));
            try leb.writeILEB128(writer, val);
        },
        .i64_const => |val| {
            try writer.writeByte(wasm.opcode(.i64_const));
            try leb.writeILEB128(writer, val);
        },
        .f32_const => |val| {
            try writer.writeByte(wasm.opcode(.f32_const));
            try writer.writeIntLittle(u32, @bitCast(u32, val));
        },
        .f64_const => |val| {
            try writer.writeByte(wasm.opcode(.f64_const));
            try writer.writeIntLittle(u64, @bitCast(u64, val));
        },
        .global_get => |val| {
            try writer.writeByte(wasm.opcode(.global_get));
            try leb.writeULEB128(writer, val);
        },
    }
    try writer.writeByte(wasm.opcode(.end));
}

fn emitImport(self: *Wasm, writer: anytype, import: types.Import) !void {
    const module_name = self.string_table.get(import.module_name);
    try leb.writeULEB128(writer, @intCast(u32, module_name.len));
    try writer.writeAll(module_name);

    const name = self.string_table.get(import.name);
    try leb.writeULEB128(writer, @intCast(u32, name.len));
    try writer.writeAll(name);

    try writer.writeByte(@enumToInt(import.kind));
    switch (import.kind) {
        .function => |type_index| try leb.writeULEB128(writer, type_index),
        .global => |global_type| {
            try leb.writeULEB128(writer, wasm.valtype(global_type.valtype));
            try writer.writeByte(@boolToInt(global_type.mutable));
        },
        .table => |table| {
            try leb.writeULEB128(writer, wasm.reftype(table.reftype));
            try emitLimits(writer, table.limits);
        },
        .memory => |limits| {
            try emitLimits(writer, limits);
        },
    }
}

fn linkWithLLD(self: *Wasm, comp: *Compilation) !void {
    const tracy = trace(@src());
    defer tracy.end();

    var arena_allocator = std.heap.ArenaAllocator.init(self.base.allocator);
    defer arena_allocator.deinit();
    const arena = arena_allocator.allocator();

    const directory = self.base.options.emit.?.directory; // Just an alias to make it shorter to type.
    const full_out_path = try directory.join(arena, &[_][]const u8{self.base.options.emit.?.sub_path});

    // If there is no Zig code to compile, then we should skip flushing the output file because it
    // will not be part of the linker line anyway.
    const module_obj_path: ?[]const u8 = if (self.base.options.module) |module| blk: {
        const use_stage1 = build_options.is_stage1 and self.base.options.use_stage1;
        if (use_stage1) {
            const obj_basename = try std.zig.binNameAlloc(arena, .{
                .root_name = self.base.options.root_name,
                .target = self.base.options.target,
                .output_mode = .Obj,
            });
            switch (self.base.options.cache_mode) {
                .incremental => break :blk try module.zig_cache_artifact_directory.join(
                    arena,
                    &[_][]const u8{obj_basename},
                ),
                .whole => break :blk try fs.path.join(arena, &.{
                    fs.path.dirname(full_out_path).?, obj_basename,
                }),
            }
        }

        try self.flushModule(comp);

        if (fs.path.dirname(full_out_path)) |dirname| {
            break :blk try fs.path.join(arena, &.{ dirname, self.base.intermediary_basename.? });
        } else {
            break :blk self.base.intermediary_basename.?;
        }
    } else null;

    const is_obj = self.base.options.output_mode == .Obj;

    const compiler_rt_path: ?[]const u8 = if (self.base.options.include_compiler_rt and !is_obj)
        comp.compiler_rt_static_lib.?.full_object_path
    else
        null;

    const target = self.base.options.target;

    const id_symlink_basename = "lld.id";

    var man: Cache.Manifest = undefined;
    defer if (!self.base.options.disable_lld_caching) man.deinit();

    var digest: [Cache.hex_digest_len]u8 = undefined;

    if (!self.base.options.disable_lld_caching) {
        man = comp.cache_parent.obtain();

        // We are about to obtain this lock, so here we give other processes a chance first.
        self.base.releaseLock();

        comptime assert(Compilation.link_hash_implementation_version == 2);

        for (self.base.options.objects) |obj| {
            _ = try man.addFile(obj.path, null);
            man.hash.add(obj.must_link);
        }
        for (comp.c_object_table.keys()) |key| {
            _ = try man.addFile(key.status.success.object_path, null);
        }
        try man.addOptionalFile(module_obj_path);
        try man.addOptionalFile(compiler_rt_path);
        man.hash.addOptionalBytes(self.base.options.entry);
        man.hash.addOptional(self.base.options.stack_size_override);
        man.hash.add(self.base.options.import_memory);
        man.hash.add(self.base.options.import_table);
        man.hash.add(self.base.options.export_table);
        man.hash.addOptional(self.base.options.initial_memory);
        man.hash.addOptional(self.base.options.max_memory);
        man.hash.add(self.base.options.shared_memory);
        man.hash.addOptional(self.base.options.global_base);
        man.hash.add(self.base.options.export_symbol_names.len);
        // strip does not need to go into the linker hash because it is part of the hash namespace
        for (self.base.options.export_symbol_names) |symbol_name| {
            man.hash.addBytes(symbol_name);
        }

        // We don't actually care whether it's a cache hit or miss; we just need the digest and the lock.
        _ = try man.hit();
        digest = man.final();

        var prev_digest_buf: [digest.len]u8 = undefined;
        const prev_digest: []u8 = Cache.readSmallFile(
            directory.handle,
            id_symlink_basename,
            &prev_digest_buf,
        ) catch |err| blk: {
            log.debug("WASM LLD new_digest={s} error: {s}", .{ std.fmt.fmtSliceHexLower(&digest), @errorName(err) });
            // Handle this as a cache miss.
            break :blk prev_digest_buf[0..0];
        };
        if (mem.eql(u8, prev_digest, &digest)) {
            log.debug("WASM LLD digest={s} match - skipping invocation", .{std.fmt.fmtSliceHexLower(&digest)});
            // Hot diggity dog! The output binary is already there.
            self.base.lock = man.toOwnedLock();
            return;
        }
        log.debug("WASM LLD prev_digest={s} new_digest={s}", .{ std.fmt.fmtSliceHexLower(prev_digest), std.fmt.fmtSliceHexLower(&digest) });

        // We are about to change the output file to be different, so we invalidate the build hash now.
        directory.handle.deleteFile(id_symlink_basename) catch |err| switch (err) {
            error.FileNotFound => {},
            else => |e| return e,
        };
    }

    if (is_obj) {
        // LLD's WASM driver does not support the equivalent of `-r` so we do a simple file copy
        // here. TODO: think carefully about how we can avoid this redundant operation when doing
        // build-obj. See also the corresponding TODO in linkAsArchive.
        const the_object_path = blk: {
            if (self.base.options.objects.len != 0)
                break :blk self.base.options.objects[0].path;

            if (comp.c_object_table.count() != 0)
                break :blk comp.c_object_table.keys()[0].status.success.object_path;

            if (module_obj_path) |p|
                break :blk p;

            // TODO I think this is unreachable. Audit this situation when solving the above TODO
            // regarding eliding redundant object -> object transformations.
            return error.NoObjectsToLink;
        };
        // This can happen when using --enable-cache and using the stage1 backend. In this case
        // we can skip the file copy.
        if (!mem.eql(u8, the_object_path, full_out_path)) {
            try fs.cwd().copyFile(the_object_path, fs.cwd(), full_out_path, .{});
        }
    } else {
        // Create an LLD command line and invoke it.
        var argv = std.ArrayList([]const u8).init(self.base.allocator);
        defer argv.deinit();
        // We will invoke ourselves as a child process to gain access to LLD.
        // This is necessary because LLD does not behave properly as a library -
        // it calls exit() and does not reset all global data between invocations.
        try argv.appendSlice(&[_][]const u8{ comp.self_exe_path.?, "wasm-ld" });
        try argv.append("-error-limit=0");

        if (self.base.options.lto) {
            switch (self.base.options.optimize_mode) {
                .Debug => {},
                .ReleaseSmall => try argv.append("-O2"),
                .ReleaseFast, .ReleaseSafe => try argv.append("-O3"),
            }
        }

        if (self.base.options.import_memory) {
            try argv.append("--import-memory");
        }

        if (self.base.options.import_table) {
            assert(!self.base.options.export_table);
            try argv.append("--import-table");
        }

        if (self.base.options.export_table) {
            assert(!self.base.options.import_table);
            try argv.append("--export-table");
        }

        if (self.base.options.strip) {
            try argv.append("-s");
        }

        if (self.base.options.initial_memory) |initial_memory| {
            const arg = try std.fmt.allocPrint(arena, "--initial-memory={d}", .{initial_memory});
            try argv.append(arg);
        }

        if (self.base.options.max_memory) |max_memory| {
            const arg = try std.fmt.allocPrint(arena, "--max-memory={d}", .{max_memory});
            try argv.append(arg);
        }

        if (self.base.options.shared_memory) {
            try argv.append("--shared-memory");
        }

        if (self.base.options.global_base) |global_base| {
            const arg = try std.fmt.allocPrint(arena, "--global-base={d}", .{global_base});
            try argv.append(arg);
        } else {
            // We prepend it by default, so when a stack overflow happens the runtime will trap correctly,
            // rather than silently overwrite all global declarations. See https://github.com/ziglang/zig/issues/4496
            //
            // The user can overwrite this behavior by setting the global-base
            try argv.append("--stack-first");
        }

        var auto_export_symbols = true;
        // Users are allowed to specify which symbols they want to export to the wasm host.
        for (self.base.options.export_symbol_names) |symbol_name| {
            const arg = try std.fmt.allocPrint(arena, "--export={s}", .{symbol_name});
            try argv.append(arg);
            auto_export_symbols = false;
        }

        if (self.base.options.rdynamic) {
            try argv.append("--export-dynamic");
            auto_export_symbols = false;
        }

        if (auto_export_symbols) {
            if (self.base.options.module) |module| {
                // when we use stage1, we use the exports that stage1 provided us.
                // For stage2, we can directly retrieve them from the module.
                const use_stage1 = build_options.is_stage1 and self.base.options.use_stage1;
                if (use_stage1) {
                    for (comp.export_symbol_names.items) |symbol_name| {
                        try argv.append(try std.fmt.allocPrint(arena, "--export={s}", .{symbol_name}));
                    }
                } else {
                    const skip_export_non_fn = target.os.tag == .wasi and
                        self.base.options.wasi_exec_model == .command;
                    for (module.decl_exports.values()) |exports| {
                        for (exports) |exprt| {
                            if (skip_export_non_fn and exprt.exported_decl.ty.zigTypeTag() != .Fn) {
                                // skip exporting symbols when we're building a WASI command
                                // and the symbol is not a function
                                continue;
                            }
                            const symbol_name = exprt.exported_decl.name;
                            const arg = try std.fmt.allocPrint(arena, "--export={s}", .{symbol_name});
                            try argv.append(arg);
                        }
                    }
                }
            }
        }

        if (self.base.options.entry) |entry| {
            try argv.append("--entry");
            try argv.append(entry);
        }

        if (self.base.options.output_mode == .Exe) {
            // Increase the default stack size to a more reasonable value of 1MB instead of
            // the default of 1 Wasm page being 64KB, unless overridden by the user.
            try argv.append("-z");
            const stack_size = self.base.options.stack_size_override orelse 1048576;
            const arg = try std.fmt.allocPrint(arena, "stack-size={d}", .{stack_size});
            try argv.append(arg);

            if (self.base.options.wasi_exec_model == .reactor) {
                // Reactor execution model does not have _start so lld doesn't look for it.
                try argv.append("--no-entry");
            }
        } else {
            if (self.base.options.stack_size_override) |stack_size| {
                try argv.append("-z");
                const arg = try std.fmt.allocPrint(arena, "stack-size={d}", .{stack_size});
                try argv.append(arg);
            }
            try argv.append("--no-entry"); // So lld doesn't look for _start.
        }
        try argv.appendSlice(&[_][]const u8{
            "--allow-undefined",
            "-o",
            full_out_path,
        });

        if (target.os.tag == .wasi) {
            const is_exe_or_dyn_lib = self.base.options.output_mode == .Exe or
                (self.base.options.output_mode == .Lib and self.base.options.link_mode == .Dynamic);
            if (is_exe_or_dyn_lib) {
                const wasi_emulated_libs = self.base.options.wasi_emulated_libs;
                for (wasi_emulated_libs) |crt_file| {
                    try argv.append(try comp.get_libc_crt_file(
                        arena,
                        wasi_libc.emulatedLibCRFileLibName(crt_file),
                    ));
                }

                if (self.base.options.link_libc) {
                    try argv.append(try comp.get_libc_crt_file(
                        arena,
                        wasi_libc.execModelCrtFileFullName(self.base.options.wasi_exec_model),
                    ));
                    try argv.append(try comp.get_libc_crt_file(arena, "libc.a"));
                }

                if (self.base.options.link_libcpp) {
                    try argv.append(comp.libcxx_static_lib.?.full_object_path);
                    try argv.append(comp.libcxxabi_static_lib.?.full_object_path);
                }
            }
        }

        // Positional arguments to the linker such as object files.
        var whole_archive = false;
        for (self.base.options.objects) |obj| {
            if (obj.must_link and !whole_archive) {
                try argv.append("-whole-archive");
                whole_archive = true;
            } else if (!obj.must_link and whole_archive) {
                try argv.append("-no-whole-archive");
                whole_archive = false;
            }
            try argv.append(obj.path);
        }
        if (whole_archive) {
            try argv.append("-no-whole-archive");
            whole_archive = false;
        }

        for (comp.c_object_table.keys()) |key| {
            try argv.append(key.status.success.object_path);
        }
        if (module_obj_path) |p| {
            try argv.append(p);
        }

        if (self.base.options.output_mode != .Obj and
            !self.base.options.skip_linker_dependencies and
            !self.base.options.link_libc)
        {
            try argv.append(comp.libc_static_lib.?.full_object_path);
        }

        if (compiler_rt_path) |p| {
            try argv.append(p);
        }

        if (self.base.options.verbose_link) {
            // Skip over our own name so that the LLD linker name is the first argv item.
            Compilation.dump_argv(argv.items[1..]);
        }

        if (std.process.can_spawn) {
            // If possible, we run LLD as a child process because it does not always
            // behave properly as a library, unfortunately.
            // https://github.com/ziglang/zig/issues/3825
            const child = try std.ChildProcess.init(argv.items, arena);
            defer child.deinit();

            if (comp.clang_passthrough_mode) {
                child.stdin_behavior = .Inherit;
                child.stdout_behavior = .Inherit;
                child.stderr_behavior = .Inherit;

                const term = child.spawnAndWait() catch |err| {
                    log.err("unable to spawn {s}: {s}", .{ argv.items[0], @errorName(err) });
                    return error.UnableToSpawnSelf;
                };
                switch (term) {
                    .Exited => |code| {
                        if (code != 0) {
                            std.process.exit(code);
                        }
                    },
                    else => std.process.abort(),
                }
            } else {
                child.stdin_behavior = .Ignore;
                child.stdout_behavior = .Ignore;
                child.stderr_behavior = .Pipe;

                try child.spawn();

                const stderr = try child.stderr.?.reader().readAllAlloc(arena, 10 * 1024 * 1024);

                const term = child.wait() catch |err| {
                    log.err("unable to spawn {s}: {s}", .{ argv.items[0], @errorName(err) });
                    return error.UnableToSpawnSelf;
                };

                switch (term) {
                    .Exited => |code| {
                        if (code != 0) {
                            // TODO parse this output and surface with the Compilation API rather than
                            // directly outputting to stderr here.
                            std.debug.print("{s}", .{stderr});
                            return error.LLDReportedFailure;
                        }
                    },
                    else => {
                        log.err("{s} terminated with stderr:\n{s}", .{ argv.items[0], stderr });
                        return error.LLDCrashed;
                    },
                }

                if (stderr.len != 0) {
                    log.warn("unexpected LLD stderr:\n{s}", .{stderr});
                }
            }
        } else {
            const exit_code = try lldMain(arena, argv.items, false);
            if (exit_code != 0) {
                if (comp.clang_passthrough_mode) {
                    std.process.exit(exit_code);
                } else {
                    return error.LLDReportedFailure;
                }
            }
        }
    }

    if (!self.base.options.disable_lld_caching) {
        // Update the file with the digest. If it fails we can continue; it only
        // means that the next invocation will have an unnecessary cache miss.
        Cache.writeSmallFile(directory.handle, id_symlink_basename, &digest) catch |err| {
            log.warn("failed to save linking hash digest symlink: {s}", .{@errorName(err)});
        };
        // Again failure here only means an unnecessary cache miss.
        man.writeManifest() catch |err| {
            log.warn("failed to write cache manifest when linking: {s}", .{@errorName(err)});
        };
        // We hang on to this lock so that the output file path can be used without
        // other processes clobbering it.
        self.base.lock = man.toOwnedLock();
    }
}

fn reserveVecSectionHeader(file: fs.File) !u64 {
    // section id + fixed leb contents size + fixed leb vector length
    const header_size = 1 + 5 + 5;
    // TODO: this should be a single lseek(2) call, but fs.File does not
    // currently provide a way to do this.
    try file.seekBy(header_size);
    return (try file.getPos()) - header_size;
}

fn reserveCustomSectionHeader(file: fs.File) !u64 {
    // unlike regular section, we don't emit the count
    const header_size = 1 + 5;
    // TODO: this should be a single lseek(2) call, but fs.File does not
    // currently provide a way to do this.
    try file.seekBy(header_size);
    return (try file.getPos()) - header_size;
}

fn writeVecSectionHeader(file: fs.File, offset: u64, section: wasm.Section, size: u32, items: u32) !void {
    var buf: [1 + 5 + 5]u8 = undefined;
    buf[0] = @enumToInt(section);
    leb.writeUnsignedFixed(5, buf[1..6], size);
    leb.writeUnsignedFixed(5, buf[6..], items);
    try file.pwriteAll(&buf, offset);
}

fn writeCustomSectionHeader(file: fs.File, offset: u64, size: u32) !void {
    var buf: [1 + 5]u8 = undefined;
    buf[0] = 0; // 0 = 'custom' section
    leb.writeUnsignedFixed(5, buf[1..6], size);
    try file.pwriteAll(&buf, offset);
}

fn emitLinkSection(self: *Wasm, file: fs.File, arena: Allocator, symbol_table: *std.AutoArrayHashMap(SymbolLoc, u32)) !void {
    const offset = try reserveCustomSectionHeader(file);
    const writer = file.writer();
    // emit "linking" custom section name
    const section_name = "linking";
    try leb.writeULEB128(writer, section_name.len);
    try writer.writeAll(section_name);

    // meta data version, which is currently '2'
    try leb.writeULEB128(writer, @as(u32, 2));

    // For each subsection type (found in types.Subsection) we can emit a section.
    // Currently, we only support emitting segment info and the symbol table.
    try self.emitSymbolTable(file, arena, symbol_table);
    try self.emitSegmentInfo(file, arena);

    const size = @intCast(u32, (try file.getPos()) - offset - 6);
    try writeCustomSectionHeader(file, offset, size);
}

fn emitSymbolTable(self: *Wasm, file: fs.File, arena: Allocator, symbol_table: *std.AutoArrayHashMap(SymbolLoc, u32)) !void {
    // After emitting the subtype, we must emit the subsection's length
    // so first write it to a temporary arraylist to calculate the length
    // and then write all data at once.
    var payload = std.ArrayList(u8).init(arena);
    const writer = payload.writer();

    try leb.writeULEB128(file.writer(), @enumToInt(types.SubsectionType.WASM_SYMBOL_TABLE));

    var symbol_count: u32 = 0;
    for (self.resolved_symbols.keys()) |sym_loc| {
        const symbol = sym_loc.getSymbol(self).*;
        if (symbol.tag == .dead) continue; // Do not emit dead symbols
        try symbol_table.putNoClobber(sym_loc, symbol_count);
        symbol_count += 1;
        log.debug("Emit symbol: {}", .{symbol});
        try leb.writeULEB128(writer, @enumToInt(symbol.tag));
        try leb.writeULEB128(writer, symbol.flags);

        const sym_name = if (self.export_names.get(sym_loc)) |exp_name| self.string_table.get(exp_name) else sym_loc.getName(self);
        switch (symbol.tag) {
            .data => {
                try leb.writeULEB128(writer, @intCast(u32, sym_name.len));
                try writer.writeAll(sym_name);

                if (symbol.isDefined()) {
                    try leb.writeULEB128(writer, symbol.index);
                    const atom = self.symbol_atom.get(sym_loc).?;
                    try leb.writeULEB128(writer, @as(u32, atom.offset));
                    try leb.writeULEB128(writer, @as(u32, atom.size));
                }
            },
            .section => {
                try leb.writeULEB128(writer, symbol.index);
            },
            else => {
                try leb.writeULEB128(writer, symbol.index);
                if (symbol.isDefined()) {
                    try leb.writeULEB128(writer, @intCast(u32, sym_name.len));
                    try writer.writeAll(sym_name);
                }
            },
        }
    }

    var buf: [5]u8 = undefined;
    leb.writeUnsignedFixed(5, &buf, symbol_count);
    try payload.insertSlice(0, &buf);
    try leb.writeULEB128(file.writer(), @intCast(u32, payload.items.len));

    const iovec: std.os.iovec_const = .{
        .iov_base = payload.items.ptr,
        .iov_len = payload.items.len,
    };
    try file.writevAll(&.{iovec});
}

fn emitSegmentInfo(self: *Wasm, file: fs.File, arena: Allocator) !void {
    var payload = std.ArrayList(u8).init(arena);
    const writer = payload.writer();
    try leb.writeULEB128(file.writer(), @enumToInt(types.SubsectionType.WASM_SEGMENT_INFO));
    try leb.writeULEB128(writer, @intCast(u32, self.segment_info.items.len));
    for (self.segment_info.items) |segment_info| {
        log.debug("Emit segment: {s} align({d}) flags({b})", .{
            segment_info.name,
            @ctz(u32, segment_info.alignment),
            segment_info.flags,
        });
        try leb.writeULEB128(writer, @intCast(u32, segment_info.name.len));
        try writer.writeAll(segment_info.name);
        try leb.writeULEB128(writer, @ctz(u32, segment_info.alignment));
        try leb.writeULEB128(writer, segment_info.flags);
    }

    try leb.writeULEB128(file.writer(), @intCast(u32, payload.items.len));
    const iovec: std.os.iovec_const = .{
        .iov_base = payload.items.ptr,
        .iov_len = payload.items.len,
    };
    try file.writevAll(&.{iovec});
}

fn getULEB128Size(uint_value: anytype) u32 {
    const T = @TypeOf(uint_value);
    const U = if (@typeInfo(T).Int.bits < 8) u8 else T;
    var value = @intCast(U, uint_value);

    var size: u32 = 0;
    while (value != 0) : (size += 1) {
        value >>= 7;
    }
    return size;
}

/// For each relocatable section, emits a custom "relocation.<section_name>" section
fn emitCodeRelocations(
    self: *Wasm,
    file: fs.File,
    arena: Allocator,
    section_index: u32,
    symbol_table: std.AutoArrayHashMap(SymbolLoc, u32),
) !void {
    const code_index = self.code_section_index orelse return;
    var payload = std.ArrayList(u8).init(arena);
    const writer = payload.writer();

    // write custom section information
    const name = "reloc.CODE";
    try leb.writeULEB128(writer, @intCast(u32, name.len));
    try writer.writeAll(name);
    try leb.writeULEB128(writer, section_index);
    const reloc_start = payload.items.len;

    var count: u32 = 0;
    var atom: *Atom = self.atoms.get(code_index).?.getFirst();
    // for each atom, we calculate the uleb size and append that
    var size_offset: u32 = 5; // account for code section size leb128
    while (true) {
        size_offset += getULEB128Size(atom.size);
        for (atom.relocs.items) |relocation| {
            count += 1;
            const sym_loc: SymbolLoc = .{ .file = atom.file, .index = relocation.index };
            const symbol_index = symbol_table.get(sym_loc).?;
            try leb.writeULEB128(writer, @enumToInt(relocation.relocation_type));
            const offset = atom.offset + relocation.offset + size_offset;
            try leb.writeULEB128(writer, offset);
            try leb.writeULEB128(writer, symbol_index);
            if (relocation.relocation_type.addendIsPresent()) {
                try leb.writeULEB128(writer, relocation.addend orelse 0);
            }
            log.debug("Emit relocation: {}", .{relocation});
        }
        atom = atom.next orelse break;
    }
    if (count == 0) return;
    var buf: [5]u8 = undefined;
    leb.writeUnsignedFixed(5, &buf, count);
    try payload.insertSlice(reloc_start, &buf);
    const iovec: std.os.iovec_const = .{
        .iov_base = payload.items.ptr,
        .iov_len = payload.items.len,
    };
    const header_offset = try reserveCustomSectionHeader(file);
    try file.writevAll(&.{iovec});
    const size = @intCast(u32, payload.items.len);
    try writeCustomSectionHeader(file, header_offset, size);
}

fn emitDataRelocations(
    self: *Wasm,
    file: fs.File,
    arena: Allocator,
    section_index: u32,
    symbol_table: std.AutoArrayHashMap(SymbolLoc, u32),
) !void {
    if (self.data_segments.count() == 0) return;
    var payload = std.ArrayList(u8).init(arena);
    const writer = payload.writer();

    // write custom section information
    const name = "reloc.DATA";
    try leb.writeULEB128(writer, @intCast(u32, name.len));
    try writer.writeAll(name);
    try leb.writeULEB128(writer, section_index);
    const reloc_start = payload.items.len;

    var count: u32 = 0;
    // for each atom, we calculate the uleb size and append that
    var size_offset: u32 = 5; // account for code section size leb128
    for (self.data_segments.values()) |segment_index| {
        var atom: *Atom = self.atoms.get(segment_index).?.getFirst();
        while (true) {
            size_offset += getULEB128Size(atom.size);
            for (atom.relocs.items) |relocation| {
                count += 1;
                const sym_loc: SymbolLoc = .{
                    .file = atom.file,
                    .index = relocation.index,
                };
                const symbol_index = symbol_table.get(sym_loc).?;
                try leb.writeULEB128(writer, @enumToInt(relocation.relocation_type));
                const offset = atom.offset + relocation.offset + size_offset;
                try leb.writeULEB128(writer, offset);
                try leb.writeULEB128(writer, symbol_index);
                if (relocation.relocation_type.addendIsPresent()) {
                    try leb.writeULEB128(writer, relocation.addend orelse 0);
                }
                log.debug("Emit relocation: {}", .{relocation});
            }
            atom = atom.next orelse break;
        }
    }
    if (count == 0) return;

    var buf: [5]u8 = undefined;
    leb.writeUnsignedFixed(5, &buf, count);
    try payload.insertSlice(reloc_start, &buf);
    const iovec: std.os.iovec_const = .{
        .iov_base = payload.items.ptr,
        .iov_len = payload.items.len,
    };
    const header_offset = try reserveCustomSectionHeader(file);
    try file.writevAll(&.{iovec});
    const size = @intCast(u32, payload.items.len);
    try writeCustomSectionHeader(file, header_offset, size);
}

/// Searches for an a matching function signature, when not found
/// a new entry will be made. The index of the existing/new signature will be returned.
pub fn putOrGetFuncType(self: *Wasm, func_type: wasm.Type) !u32 {
    var index: u32 = 0;
    while (index < self.func_types.items.len) : (index += 1) {
        if (self.func_types.items[index].eql(func_type)) return index;
    }

    // functype does not exist.
    const params = try self.base.allocator.dupe(wasm.Valtype, func_type.params);
    errdefer self.base.allocator.free(params);
    const returns = try self.base.allocator.dupe(wasm.Valtype, func_type.returns);
    errdefer self.base.allocator.free(returns);
    try self.func_types.append(self.base.allocator, .{
        .params = params,
        .returns = returns,
    });
    return index;
}