macho: unify concept of SymbolWithLoc across drivers

12 files changed, 88 insertions, 127 deletions

diff --git a/src/arch/aarch64/Emit.zig b/src/arch/aarch64/Emit.zig
index 8cf2386138..68c28ed8aa 100644
--- a/src/arch/aarch64/Emit.zig
+++ b/src/arch/aarch64/Emit.zig
@@ -670,7 +670,7 @@ fn mirCallExtern(emit: *Emit, inst: Mir.Inst.Index) !void {
 
     if (emit.bin_file.cast(link.File.MachO)) |macho_file| {
         // Add relocation to the decl.
-        const atom_index = macho_file.getAtomIndexForSymbol(.{ .sym_index = relocation.atom_index, .file = null }).?;
+        const atom_index = macho_file.getAtomIndexForSymbol(.{ .sym_index = relocation.atom_index }).?;
         const target = macho_file.getGlobalByIndex(relocation.sym_index);
         try link.File.MachO.Atom.addRelocation(macho_file, atom_index, .{
             .type = .branch,
@@ -885,9 +885,9 @@ fn mirLoadMemoryPie(emit: *Emit, inst: Mir.Inst.Index) !void {
     if (emit.bin_file.cast(link.File.MachO)) |macho_file| {
         const Atom = link.File.MachO.Atom;
         const Relocation = Atom.Relocation;
-        const atom_index = macho_file.getAtomIndexForSymbol(.{ .sym_index = data.atom_index, .file = null }).?;
+        const atom_index = macho_file.getAtomIndexForSymbol(.{ .sym_index = data.atom_index }).?;
         try Atom.addRelocations(macho_file, atom_index, &[_]Relocation{ .{
-            .target = .{ .sym_index = data.sym_index, .file = null },
+            .target = .{ .sym_index = data.sym_index },
             .offset = offset,
             .addend = 0,
             .pcrel = true,
@@ -898,7 +898,7 @@ fn mirLoadMemoryPie(emit: *Emit, inst: Mir.Inst.Index) !void {
                 else => unreachable,
             },
         }, .{
-            .target = .{ .sym_index = data.sym_index, .file = null },
+            .target = .{ .sym_index = data.sym_index },
             .offset = offset + 4,
             .addend = 0,
             .pcrel = false,
diff --git a/src/arch/x86_64/Emit.zig b/src/arch/x86_64/Emit.zig
index 12b5294015..050772b2ce 100644
--- a/src/arch/x86_64/Emit.zig
+++ b/src/arch/x86_64/Emit.zig
@@ -43,9 +43,7 @@ pub fn emitMir(emit: *Emit) Error!void {
                 }),
                 .linker_extern_fn => |symbol| if (emit.bin_file.cast(link.File.MachO)) |macho_file| {
                     // Add relocation to the decl.
-                    const atom_index = macho_file.getAtomIndexForSymbol(
-                        .{ .sym_index = symbol.atom_index, .file = null },
-                    ).?;
+                    const atom_index = macho_file.getAtomIndexForSymbol(.{ .sym_index = symbol.atom_index }).?;
                     const target = macho_file.getGlobalByIndex(symbol.sym_index);
                     try link.File.MachO.Atom.addRelocation(macho_file, atom_index, .{
                         .type = .branch,
@@ -77,10 +75,7 @@ pub fn emitMir(emit: *Emit) Error!void {
                 .linker_import,
                 .linker_tlv,
                 => |symbol| if (emit.bin_file.cast(link.File.MachO)) |macho_file| {
-                    const atom_index = macho_file.getAtomIndexForSymbol(.{
-                        .sym_index = symbol.atom_index,
-                        .file = null,
-                    }).?;
+                    const atom_index = macho_file.getAtomIndexForSymbol(.{ .sym_index = symbol.atom_index }).?;
                     try link.File.MachO.Atom.addRelocation(macho_file, atom_index, .{
                         .type = switch (lowered_relocs[0].target) {
                             .linker_got => .got,
@@ -88,7 +83,7 @@ pub fn emitMir(emit: *Emit) Error!void {
                             .linker_tlv => .tlv,
                             else => unreachable,
                         },
-                        .target = .{ .sym_index = symbol.sym_index, .file = null },
+                        .target = .{ .sym_index = symbol.sym_index },
                         .offset = @as(u32, @intCast(end_offset - 4)),
                         .addend = 0,
                         .pcrel = true,
diff --git a/src/link/MachO.zig b/src/link/MachO.zig
index 92aae67c22..440c26260a 100644
--- a/src/link/MachO.zig
+++ b/src/link/MachO.zig
@@ -249,20 +249,14 @@ const DeclMetadata = struct {
 
     fn getExport(m: DeclMetadata, macho_file: *const MachO, name: []const u8) ?u32 {
         for (m.exports.items) |exp| {
-            if (mem.eql(u8, name, macho_file.getSymbolName(.{
-                .sym_index = exp,
-                .file = null,
-            }))) return exp;
+            if (mem.eql(u8, name, macho_file.getSymbolName(.{ .sym_index = exp }))) return exp;
         }
         return null;
     }
 
     fn getExportPtr(m: *DeclMetadata, macho_file: *MachO, name: []const u8) ?*u32 {
         for (m.exports.items) |*exp| {
-            if (mem.eql(u8, name, macho_file.getSymbolName(.{
-                .sym_index = exp.*,
-                .file = null,
-            }))) return exp;
+            if (mem.eql(u8, name, macho_file.getSymbolName(.{ .sym_index = exp.* }))) return exp;
         }
         return null;
     }
@@ -284,21 +278,20 @@ const ResolveAction = struct {
     };
 };
 
-pub const SymbolWithLoc = struct {
+pub const SymbolWithLoc = extern struct {
     // Index into the respective symbol table.
     sym_index: u32,
 
-    // null means it's a synthetic global.
-    file: ?u32 = null,
+    // 0 means it's a synthetic global.
+    file: u32 = 0,
 
-    pub fn eql(this: SymbolWithLoc, other: SymbolWithLoc) bool {
-        if (this.file == null and other.file == null) {
-            return this.sym_index == other.sym_index;
-        }
-        if (this.file != null and other.file != null) {
-            return this.sym_index == other.sym_index and this.file.? == other.file.?;
-        }
-        return false;
+    pub fn getFile(self: SymbolWithLoc) ?u32 {
+        if (self.file == 0) return null;
+        return self.file - 1;
+    }
+
+    pub fn eql(self: SymbolWithLoc, other: SymbolWithLoc) bool {
+        return self.file == other.file and self.sym_index == other.sym_index;
     }
 };
 
@@ -1576,7 +1569,7 @@ pub fn allocateSpecialSymbols(self: *MachO) !void {
         "__mh_execute_header",
     }) |name| {
         const global = self.getGlobal(name) orelse continue;
-        if (global.file != null) continue;
+        if (global.getFile() != null) continue;
         const sym = self.getSymbolPtr(global);
         const seg = self.getSegment(self.text_section_index.?);
         sym.n_sect = 1;
@@ -1597,7 +1590,7 @@ pub fn createAtom(self: *MachO) !Atom.Index {
     try self.atom_by_index_table.putNoClobber(gpa, sym_index, atom_index);
     atom.* = .{
         .sym_index = sym_index,
-        .file = null,
+        .file = 0,
         .size = 0,
         .prev_index = null,
         .next_index = null,
@@ -1664,7 +1657,7 @@ fn createMhExecuteHeaderSymbol(self: *MachO) !void {
 
     const gpa = self.base.allocator;
     const sym_index = try self.allocateSymbol();
-    const sym_loc = SymbolWithLoc{ .sym_index = sym_index, .file = null };
+    const sym_loc = SymbolWithLoc{ .sym_index = sym_index };
     const sym = self.getSymbolPtr(sym_loc);
     sym.* = .{
         .n_strx = try self.strtab.insert(gpa, "__mh_execute_header"),
@@ -1684,7 +1677,7 @@ fn createDsoHandleSymbol(self: *MachO) !void {
 
     const gpa = self.base.allocator;
     const sym_index = try self.allocateSymbol();
-    const sym_loc = SymbolWithLoc{ .sym_index = sym_index, .file = null };
+    const sym_loc = SymbolWithLoc{ .sym_index = sym_index };
     const sym = self.getSymbolPtr(sym_loc);
     sym.* = .{
         .n_strx = try self.strtab.insert(gpa, "___dso_handle"),
@@ -1998,10 +1991,7 @@ fn allocateGlobal(self: *MachO) !u32 {
         }
     };
 
-    self.globals.items[index] = .{
-        .sym_index = 0,
-        .file = null,
-    };
+    self.globals.items[index] = .{ .sym_index = 0 };
 
     return index;
 }
@@ -2613,7 +2603,7 @@ pub fn updateDeclExports(
             try decl_metadata.exports.append(gpa, sym_index);
             break :blk sym_index;
         };
-        const sym_loc = SymbolWithLoc{ .sym_index = sym_index, .file = null };
+        const sym_loc = SymbolWithLoc{ .sym_index = sym_index };
         const sym = self.getSymbolPtr(sym_loc);
         sym.* = .{
             .n_strx = try self.strtab.insert(gpa, exp_name),
@@ -2643,7 +2633,7 @@ pub fn updateDeclExports(
             error.MultipleSymbolDefinitions => {
                 // TODO: this needs rethinking
                 const global = self.getGlobal(exp_name).?;
-                if (sym_loc.sym_index != global.sym_index and global.file != null) {
+                if (sym_loc.sym_index != global.sym_index and global.getFile() != null) {
                     _ = try mod.failed_exports.put(mod.gpa, exp, try Module.ErrorMsg.create(
                         gpa,
                         decl.srcLoc(mod),
@@ -2672,7 +2662,7 @@ pub fn deleteDeclExport(
     defer gpa.free(exp_name);
     const sym_index = metadata.getExportPtr(self, exp_name) orelse return;
 
-    const sym_loc = SymbolWithLoc{ .sym_index = sym_index.*, .file = null };
+    const sym_loc = SymbolWithLoc{ .sym_index = sym_index.* };
     const sym = self.getSymbolPtr(sym_loc);
     log.debug("deleting export '{s}'", .{exp_name});
     assert(sym.sect() and sym.ext());
@@ -2688,10 +2678,7 @@ pub fn deleteDeclExport(
     if (self.resolver.fetchRemove(exp_name)) |entry| {
         defer gpa.free(entry.key);
         self.globals_free_list.append(gpa, entry.value) catch {};
-        self.globals.items[entry.value] = .{
-            .sym_index = 0,
-            .file = null,
-        };
+        self.globals.items[entry.value] = .{ .sym_index = 0 };
     }
 
     sym_index.* = 0;
@@ -2730,10 +2717,10 @@ pub fn getDeclVAddr(self: *MachO, decl_index: Module.Decl.Index, reloc_info: Fil
 
     const this_atom_index = try self.getOrCreateAtomForDecl(decl_index);
     const sym_index = self.getAtom(this_atom_index).getSymbolIndex().?;
-    const atom_index = self.getAtomIndexForSymbol(.{ .sym_index = reloc_info.parent_atom_index, .file = null }).?;
+    const atom_index = self.getAtomIndexForSymbol(.{ .sym_index = reloc_info.parent_atom_index }).?;
     try Atom.addRelocation(self, atom_index, .{
         .type = .unsigned,
-        .target = .{ .sym_index = sym_index, .file = null },
+        .target = .{ .sym_index = sym_index },
         .offset = @as(u32, @intCast(reloc_info.offset)),
         .addend = reloc_info.addend,
         .pcrel = false,
@@ -3514,7 +3501,7 @@ fn writeSymtab(self: *MachO) !SymtabCtx {
 
     for (self.locals.items, 0..) |sym, sym_id| {
         if (sym.n_strx == 0) continue; // no name, skip
-        const sym_loc = SymbolWithLoc{ .sym_index = @as(u32, @intCast(sym_id)), .file = null };
+        const sym_loc = SymbolWithLoc{ .sym_index = @as(u32, @intCast(sym_id)) };
         if (self.symbolIsTemp(sym_loc)) continue; // local temp symbol, skip
         if (self.getGlobal(self.getSymbolName(sym_loc)) != null) continue; // global symbol is either an export or import, skip
         try locals.append(sym);
@@ -3934,13 +3921,13 @@ pub fn symbolIsTemp(self: *MachO, sym_with_loc: SymbolWithLoc) bool {
 
 /// Returns pointer-to-symbol described by `sym_with_loc` descriptor.
 pub fn getSymbolPtr(self: *MachO, sym_with_loc: SymbolWithLoc) *macho.nlist_64 {
-    assert(sym_with_loc.file == null);
+    assert(sym_with_loc.getFile() == null);
     return &self.locals.items[sym_with_loc.sym_index];
 }
 
 /// Returns symbol described by `sym_with_loc` descriptor.
 pub fn getSymbol(self: *const MachO, sym_with_loc: SymbolWithLoc) macho.nlist_64 {
-    assert(sym_with_loc.file == null);
+    assert(sym_with_loc.getFile() == null);
     return self.locals.items[sym_with_loc.sym_index];
 }
 
@@ -4006,7 +3993,7 @@ pub fn getAtomPtr(self: *MachO, atom_index: Atom.Index) *Atom {
 /// Returns atom if there is an atom referenced by the symbol described by `sym_with_loc` descriptor.
 /// Returns null on failure.
 pub fn getAtomIndexForSymbol(self: *MachO, sym_with_loc: SymbolWithLoc) ?Atom.Index {
-    assert(sym_with_loc.file == null);
+    assert(sym_with_loc.getFile() == null);
     return self.atom_by_index_table.get(sym_with_loc.sym_index);
 }
 
@@ -4034,13 +4021,31 @@ pub inline fn getPageSize(cpu_arch: std.Target.Cpu.Arch) u16 {
     };
 }
 
-pub fn findFirst(comptime T: type, haystack: []align(1) const T, start: usize, predicate: anytype) usize {
+/// Binary search
+pub fn bsearch(comptime T: type, haystack: []align(1) const T, predicate: anytype) usize {
     if (!@hasDecl(@TypeOf(predicate), "predicate"))
         @compileError("Predicate is required to define fn predicate(@This(), T) bool");
 
-    if (start == haystack.len) return start;
+    var min: usize = 0;
+    var max: usize = haystack.len;
+    while (min < max) {
+        const index = (min + max) / 2;
+        const curr = haystack[index];
+        if (predicate.predicate(curr)) {
+            min = index + 1;
+        } else {
+            max = index;
+        }
+    }
+    return min;
+}
+
+/// Linear search
+pub fn lsearch(comptime T: type, haystack: []align(1) const T, predicate: anytype) usize {
+    if (!@hasDecl(@TypeOf(predicate), "predicate"))
+        @compileError("Predicate is required to define fn predicate(@This(), T) bool");
 
-    var i = start;
+    var i: usize = 0;
     while (i < haystack.len) : (i += 1) {
         if (predicate.predicate(haystack[i])) break;
     }
diff --git a/src/link/MachO/Atom.zig b/src/link/MachO/Atom.zig
index 970371e455..7dc97003aa 100644
--- a/src/link/MachO/Atom.zig
+++ b/src/link/MachO/Atom.zig
@@ -17,16 +17,19 @@ const MachO = @import("../MachO.zig");
 pub const Relocation = @import("Relocation.zig");
 const SymbolWithLoc = MachO.SymbolWithLoc;
 
-/// Each decl always gets a local symbol with the fully qualified name.
-/// The vaddr and size are found here directly.
-/// The file offset is found by computing the vaddr offset from the section vaddr
-/// the symbol references, and adding that to the file offset of the section.
+/// Each Atom always gets a symbol with the fully qualified name.
+/// The symbol can reside in any object file context structure in `symtab` array
+/// (see `Object`), or if the symbol is a synthetic symbol such as a GOT cell or
+/// a stub trampoline, it can be found in the linkers `locals` arraylist.
 /// If this field is 0, it means the codegen size = 0 and there is no symbol or
 /// offset table entry.
 sym_index: u32,
 
-/// null means symbol defined by Zig source.
-file: ?u32,
+/// 0 means an Atom is a synthetic Atom such as a GOT cell defined by the linker.
+/// Otherwise, it is the index into appropriate object file (indexing from 1).
+/// Prefer using `getFile()` helper to get the file index out rather than using
+/// the field directly.
+file: u32,
 
 /// Size and alignment of this atom
 /// Unlike in Elf, we need to store the size of this symbol as part of
diff --git a/src/link/MachO/DebugSymbols.zig b/src/link/MachO/DebugSymbols.zig
index 07bf409836..602ee1ed63 100644
--- a/src/link/MachO/DebugSymbols.zig
+++ b/src/link/MachO/DebugSymbols.zig
@@ -475,7 +475,7 @@ fn writeSymtab(self: *DebugSymbols, macho_file: *MachO) !void {
 
     for (macho_file.locals.items, 0..) |sym, sym_id| {
         if (sym.n_strx == 0) continue; // no name, skip
-        const sym_loc = MachO.SymbolWithLoc{ .sym_index = @as(u32, @intCast(sym_id)), .file = null };
+        const sym_loc = MachO.SymbolWithLoc{ .sym_index = @as(u32, @intCast(sym_id)) };
         if (macho_file.symbolIsTemp(sym_loc)) continue; // local temp symbol, skip
         if (macho_file.getGlobal(macho_file.getSymbolName(sym_loc)) != null) continue; // global symbol is either an export or import, skip
         var out_sym = sym;
diff --git a/src/link/MachO/Object.zig b/src/link/MachO/Object.zig
index fe517d11be..5e67a334c0 100644
--- a/src/link/MachO/Object.zig
+++ b/src/link/MachO/Object.zig
@@ -23,9 +23,10 @@ const Atom = @import("ZldAtom.zig");
 const AtomIndex = @import("zld.zig").AtomIndex;
 const DwarfInfo = @import("DwarfInfo.zig");
 const LoadCommandIterator = macho.LoadCommandIterator;
-const Zld = @import("zld.zig").Zld;
-const SymbolWithLoc = @import("zld.zig").SymbolWithLoc;
+const MachO = @import("../MachO.zig");
+const SymbolWithLoc = MachO.SymbolWithLoc;
 const UnwindInfo = @import("UnwindInfo.zig");
+const Zld = @import("zld.zig").Zld;
 
 name: []const u8,
 mtime: u64,
@@ -314,10 +315,10 @@ fn filterSymbolsBySection(symbols: []macho.nlist_64, n_sect: u8) struct {
         }
     };
 
-    const index = @import("zld.zig").lsearch(macho.nlist_64, symbols, FirstMatch{
+    const index = MachO.lsearch(macho.nlist_64, symbols, FirstMatch{
         .n_sect = n_sect,
     });
-    const len = @import("zld.zig").lsearch(macho.nlist_64, symbols[index..], FirstNonMatch{
+    const len = MachO.lsearch(macho.nlist_64, symbols[index..], FirstNonMatch{
         .n_sect = n_sect,
     });
 
@@ -336,10 +337,10 @@ fn filterSymbolsByAddress(symbols: []macho.nlist_64, start_addr: u64, end_addr:
         }
     };
 
-    const index = @import("zld.zig").lsearch(macho.nlist_64, symbols, Predicate{
+    const index = MachO.lsearch(macho.nlist_64, symbols, Predicate{
         .addr = start_addr,
     });
-    const len = @import("zld.zig").lsearch(macho.nlist_64, symbols[index..], Predicate{
+    const len = MachO.lsearch(macho.nlist_64, symbols[index..], Predicate{
         .addr = end_addr,
     });
 
@@ -631,8 +632,8 @@ fn filterRelocs(
         }
     };
 
-    const start = @import("zld.zig").bsearch(macho.relocation_info, relocs, Predicate{ .addr = end_addr });
-    const len = @import("zld.zig").lsearch(macho.relocation_info, relocs[start..], LPredicate{ .addr = start_addr });
+    const start = MachO.bsearch(macho.relocation_info, relocs, Predicate{ .addr = end_addr });
+    const len = MachO.lsearch(macho.relocation_info, relocs[start..], LPredicate{ .addr = start_addr });
 
     return .{ .start = @as(u32, @intCast(start)), .len = @as(u32, @intCast(len)) };
 }
@@ -1031,7 +1032,7 @@ pub fn getSymbolByAddress(self: Object, addr: u64, sect_hint: ?u8) u32 {
     if (sect_hint) |sect_id| {
         if (self.source_section_index_lookup[sect_id].len > 0) {
             const lookup = self.source_section_index_lookup[sect_id];
-            const target_sym_index = @import("zld.zig").lsearch(
+            const target_sym_index = MachO.lsearch(
                 i64,
                 self.source_address_lookup[lookup.start..][0..lookup.len],
                 Predicate{ .addr = @as(i64, @intCast(addr)) },
@@ -1046,7 +1047,7 @@ pub fn getSymbolByAddress(self: Object, addr: u64, sect_hint: ?u8) u32 {
         return self.getSectionAliasSymbolIndex(sect_id);
     }
 
-    const target_sym_index = @import("zld.zig").lsearch(i64, self.source_address_lookup, Predicate{
+    const target_sym_index = MachO.lsearch(i64, self.source_address_lookup, Predicate{
         .addr = @as(i64, @intCast(addr)),
     });
     assert(target_sym_index > 0);
diff --git a/src/link/MachO/UnwindInfo.zig b/src/link/MachO/UnwindInfo.zig
index aff1681d38..49a3ab9d01 100644
--- a/src/link/MachO/UnwindInfo.zig
+++ b/src/link/MachO/UnwindInfo.zig
@@ -15,8 +15,9 @@ const Allocator = mem.Allocator;
 const Atom = @import("ZldAtom.zig");
 const AtomIndex = @import("zld.zig").AtomIndex;
 const EhFrameRecord = eh_frame.EhFrameRecord;
+const MachO = @import("../MachO.zig");
 const Object = @import("Object.zig");
-const SymbolWithLoc = @import("zld.zig").SymbolWithLoc;
+const SymbolWithLoc = MachO.SymbolWithLoc;
 const Zld = @import("zld.zig").Zld;
 
 const N_DEAD = @import("zld.zig").N_DEAD;
diff --git a/src/link/MachO/ZldAtom.zig b/src/link/MachO/ZldAtom.zig
index f97bfca326..6bcd74ff0c 100644
--- a/src/link/MachO/ZldAtom.zig
+++ b/src/link/MachO/ZldAtom.zig
@@ -22,7 +22,7 @@ const Arch = std.Target.Cpu.Arch;
 const AtomIndex = @import("zld.zig").AtomIndex;
 const Object = @import("Object.zig");
 const Relocation = @import("Relocation.zig");
-const SymbolWithLoc = @import("zld.zig").SymbolWithLoc;
+const SymbolWithLoc = @import("../MachO.zig").SymbolWithLoc;
 const Zld = @import("zld.zig").Zld;
 
 /// Each Atom always gets a symbol with the fully qualified name.
diff --git a/src/link/MachO/dead_strip.zig b/src/link/MachO/dead_strip.zig
index 563d68cc89..42d1604a0d 100644
--- a/src/link/MachO/dead_strip.zig
+++ b/src/link/MachO/dead_strip.zig
@@ -11,7 +11,8 @@ const mem = std.mem;
 const Allocator = mem.Allocator;
 const AtomIndex = @import("zld.zig").AtomIndex;
 const Atom = @import("ZldAtom.zig");
-const SymbolWithLoc = @import("zld.zig").SymbolWithLoc;
+const MachO = @import("../MachO.zig");
+const SymbolWithLoc = MachO.SymbolWithLoc;
 const SymbolResolver = @import("zld.zig").SymbolResolver;
 const UnwindInfo = @import("UnwindInfo.zig");
 const Zld = @import("zld.zig").Zld;
diff --git a/src/link/MachO/eh_frame.zig b/src/link/MachO/eh_frame.zig
index 9a30e863b9..6ef7a79977 100644
--- a/src/link/MachO/eh_frame.zig
+++ b/src/link/MachO/eh_frame.zig
@@ -9,8 +9,9 @@ const log = std.log.scoped(.eh_frame);
 const Allocator = mem.Allocator;
 const AtomIndex = @import("zld.zig").AtomIndex;
 const Atom = @import("ZldAtom.zig");
+const MachO = @import("../MachO.zig");
 const Relocation = @import("Relocation.zig");
-const SymbolWithLoc = @import("zld.zig").SymbolWithLoc;
+const SymbolWithLoc = MachO.SymbolWithLoc;
 const UnwindInfo = @import("UnwindInfo.zig");
 const Zld = @import("zld.zig").Zld;
 
diff --git a/src/link/MachO/thunks.zig b/src/link/MachO/thunks.zig
index 82d0451225..66ae57e970 100644
--- a/src/link/MachO/thunks.zig
+++ b/src/link/MachO/thunks.zig
@@ -17,8 +17,9 @@ const aarch64 = @import("../../arch/aarch64/bits.zig");
 const Allocator = mem.Allocator;
 const Atom = @import("ZldAtom.zig");
 const AtomIndex = @import("zld.zig").AtomIndex;
+const MachO = @import("../MachO.zig");
 const Relocation = @import("Relocation.zig");
-const SymbolWithLoc = @import("zld.zig").SymbolWithLoc;
+const SymbolWithLoc = MachO.SymbolWithLoc;
 const Zld = @import("zld.zig").Zld;
 
 pub const ThunkIndex = u32;
diff --git a/src/link/MachO/zld.zig b/src/link/MachO/zld.zig
index 6ca227c430..5307a3ac02 100644
--- a/src/link/MachO/zld.zig
+++ b/src/link/MachO/zld.zig
@@ -32,6 +32,7 @@ const Md5 = std.crypto.hash.Md5;
 const LibStub = @import("../tapi.zig").LibStub;
 const Object = @import("Object.zig");
 const StringTable = @import("../strtab.zig").StringTable;
+const SymbolWithLoc = MachO.SymbolWithLoc;
 const Trie = @import("Trie.zig");
 const UnwindInfo = @import("UnwindInfo.zig");
 
@@ -2038,8 +2039,8 @@ pub const Zld = struct {
             }
         };
 
-        const start = lsearch(macho.data_in_code_entry, dices, Predicate{ .addr = start_addr });
-        const end = lsearch(macho.data_in_code_entry, dices[start..], Predicate{ .addr = end_addr }) + start;
+        const start = MachO.lsearch(macho.data_in_code_entry, dices, Predicate{ .addr = start_addr });
+        const end = MachO.lsearch(macho.data_in_code_entry, dices[start..], Predicate{ .addr = end_addr }) + start;
 
         return dices[start..end];
     }
@@ -3021,23 +3022,6 @@ const IndirectPointer = struct {
     }
 };
 
-pub const SymbolWithLoc = extern struct {
-    // Index into the respective symbol table.
-    sym_index: u32,
-
-    // 0 means it's a synthetic global.
-    file: u32 = 0,
-
-    pub fn getFile(self: SymbolWithLoc) ?u32 {
-        if (self.file == 0) return null;
-        return self.file - 1;
-    }
-
-    pub fn eql(self: SymbolWithLoc, other: SymbolWithLoc) bool {
-        return self.file == other.file and self.sym_index == other.sym_index;
-    }
-};
-
 pub const SymbolResolver = struct {
     arena: Allocator,
     table: std.StringHashMap(u32),
@@ -3636,34 +3620,3 @@ pub fn linkWithZld(macho_file: *MachO, comp: *Compilation, prog_node: *std.Progr
         macho_file.base.lock = man.toOwnedLock();
     }
 }
-
-/// Binary search
-pub fn bsearch(comptime T: type, haystack: []align(1) const T, predicate: anytype) usize {
-    if (!@hasDecl(@TypeOf(predicate), "predicate"))
-        @compileError("Predicate is required to define fn predicate(@This(), T) bool");
-
-    var min: usize = 0;
-    var max: usize = haystack.len;
-    while (min < max) {
-        const index = (min + max) / 2;
-        const curr = haystack[index];
-        if (predicate.predicate(curr)) {
-            min = index + 1;
-        } else {
-            max = index;
-        }
-    }
-    return min;
-}
-
-/// Linear search
-pub fn lsearch(comptime T: type, haystack: []align(1) const T, predicate: anytype) usize {
-    if (!@hasDecl(@TypeOf(predicate), "predicate"))
-        @compileError("Predicate is required to define fn predicate(@This(), T) bool");
-
-    var i: usize = 0;
-    while (i < haystack.len) : (i += 1) {
-        if (predicate.predicate(haystack[i])) break;
-    }
-    return i;
-}