tiny.coz.source_map

1const std = @import("std");23const profile = @import("profile.zig");45pub const Interval = struct {6    base: usize,7    limit: usize,89    pub fn init(base: usize, limit: usize) !Interval {10        if (limit <= base) return error.InvalidInterval;11        return .{ .base = base, .limit = limit };12    }1314    pub fn unit(address: usize) Interval {15        return .{ .base = address, .limit = address +| 1 };16    }1718    pub fn shifted(self: Interval, offset: usize) Interval {19        return .{ .base = self.base +% offset, .limit = self.limit +% offset };20    }2122    pub fn contains(self: Interval, address: usize) bool {23        return self.base <= address and address < self.limit;24    }2526    pub fn overlaps(self: Interval, other: Interval) bool {27        return self.base < other.limit and other.base < self.limit;28    }29};3031pub const Line = struct {32    file: *File,33    number: u64,34    samples: std.atomic.Value(u64) = .init(0),3536    pub fn addSample(self: *Line) void {37        _ = self.samples.fetchAdd(1, .monotonic);38    }3940    pub fn sampleCount(self: *const Line) u64 {41        return self.samples.load(.monotonic);42    }4344    pub fn location(self: *const Line) profile.Location {45        return .{ .file = self.file.name, .line = self.number };46    }47};4849pub const File = struct {50    name: []const u8,51    lines: std.AutoHashMapUnmanaged(u64, *Line) = .empty,5253    fn getLine(self: *File, allocator: std.mem.Allocator, number: u64) !*Line {54        if (self.lines.get(number)) |line| return line;5556        const line = try allocator.create(Line);57        errdefer allocator.destroy(line);58        line.* = .{ .file = self, .number = number };5960        try self.lines.put(allocator, number, line);61        return line;62    }6364    fn hasLine(self: *const File, number: u64) bool {65        return self.lines.contains(number);66    }6768    fn findLine(self: *const File, number: u64) ?*Line {69        return self.lines.get(number);70    }7172    fn deinit(self: *File, allocator: std.mem.Allocator) void {73        var iter = self.lines.valueIterator();74        while (iter.next()) |line| allocator.destroy(line.*);75        self.lines.deinit(allocator);76        self.* = undefined;77    }78};7980pub const QueuedRange = struct {81    filename: []const u8,82    line: u64,83    range: Interval,84    preferred: bool = false,85};8687pub const RangeEntry = struct {88    range: Interval,89    line: *Line,90};9192pub const Sample = struct {93    ip: usize,94    callchain: []const usize = &.{},95};9697pub const Match = struct {98    line: ?*Line = null,99    selected_hit: bool = false,100};101102pub const Index = struct {103    files: std.StringHashMapUnmanaged(*File) = .empty,104    ranges: std.ArrayListUnmanaged(RangeEntry) = .empty,105    unresolved: std.AutoHashMapUnmanaged(usize, void) = .empty,106107    pub fn deinit(self: *Index, allocator: std.mem.Allocator) void {108        var iter = self.files.iterator();109        while (iter.next()) |entry| {110            entry.value_ptr.*.deinit(allocator);111            allocator.destroy(entry.value_ptr.*);112            allocator.free(entry.key_ptr.*);113        }114        self.files.deinit(allocator);115        self.ranges.deinit(allocator);116        self.unresolved.deinit(allocator);117        self.* = .{};118    }119120    pub fn markUnresolved(self: *Index, allocator: std.mem.Allocator, address: usize) !void {121        try self.unresolved.put(allocator, address, {});122    }123124    pub fn isUnresolved(self: *const Index, address: usize) bool {125        return self.unresolved.contains(address);126    }127128    pub fn getFile(self: *Index, allocator: std.mem.Allocator, filename: []const u8) !*File {129        if (self.files.get(filename)) |file| return file;130131        const owned_name = try allocator.dupe(u8, filename);132        errdefer allocator.free(owned_name);133134        const file = try allocator.create(File);135        errdefer allocator.destroy(file);136        file.* = .{ .name = owned_name };137138        try self.files.put(allocator, owned_name, file);139        return file;140    }141142    pub fn getLine(self: *Index, allocator: std.mem.Allocator, filename: []const u8, line_no: u64) !*Line {143        return (try self.getFile(allocator, filename)).getLine(allocator, line_no);144    }145146    pub fn addRange(147        self: *Index,148        allocator: std.mem.Allocator,149        filename: []const u8,150        line_no: u64,151        range: Interval,152    ) !*Line {153        if (self.findOverlappingRange(range)) |entry| return entry.line;154155        const line = try self.getLine(allocator, filename, line_no);156        const index = self.rangeInsertIndex(range);157        try self.ranges.insert(allocator, index, .{ .range = range, .line = line });158        return line;159    }160161    pub fn addQueuedRanges(self: *Index, allocator: std.mem.Allocator, queued: []QueuedRange) !void {162        std.mem.sort(QueuedRange, queued, {}, queuedRangeLessThan);163        for (queued) |entry| {164            _ = try self.addRange(allocator, entry.filename, entry.line, entry.range);165        }166    }167168    pub fn findLineByAddress(self: *const Index, address: usize) ?*Line {169        var low: usize = 0;170        var high: usize = self.ranges.items.len;171        while (low < high) {172            const mid = low + (high - low) / 2;173            const entry = self.ranges.items[mid];174            if (address < entry.range.base) {175                high = mid;176            } else if (address >= entry.range.limit) {177                low = mid + 1;178            } else {179                return entry.line;180            }181        }182        return null;183    }184185    pub fn findLineByName(self: *Index, text: []const u8) ?*Line {186        const colon = std.mem.indexOfScalar(u8, text, ':') orelse return null;187        const filename = text[0..colon];188        const line_no = std.fmt.parseUnsigned(u64, text[colon + 1 ..], 10) catch return null;189190        var iter = self.files.valueIterator();191        while (iter.next()) |file| {192            if (std.mem.endsWith(u8, file.*.name, filename) and file.*.hasLine(line_no)) {193                return file.*.findLine(line_no);194            }195        }196        return null;197    }198199    pub fn matchSample(self: *const Index, sample: Sample, selected: ?*const Line) Match {200        var result: Match = .{};201        var first_hit = false;202203        if (self.findLineByAddress(sample.ip)) |line| {204            result.line = line;205            first_hit = true;206            if (selectedLineMatches(selected, line)) return .{ .line = line, .selected_hit = true };207        }208209        for (sample.callchain) |pc| {210            const address = pc -| 1;211            if (self.findLineByAddress(address)) |line| {212                if (!first_hit) {213                    first_hit = true;214                    result.line = line;215                }216                if (selectedLineMatches(selected, line)) return .{ .line = line, .selected_hit = true };217            }218        }219220        return result;221    }222223    fn findOverlappingRange(self: *const Index, range: Interval) ?RangeEntry {224        for (self.ranges.items) |entry| {225            if (entry.range.overlaps(range)) return entry;226            if (entry.range.base >= range.limit) return null;227        }228        return null;229    }230231    fn rangeInsertIndex(self: *const Index, range: Interval) usize {232        for (self.ranges.items, 0..) |entry, index| {233            if (range.base < entry.range.base) return index;234        }235        return self.ranges.items.len;236    }237};238239fn selectedLineMatches(selected: ?*const Line, line: *const Line) bool {240    return if (selected) |expected| expected == line else false;241}242243fn queuedRangeLessThan(_: void, lhs: QueuedRange, rhs: QueuedRange) bool {244    if (lhs.range.base != rhs.range.base) return lhs.range.base < rhs.range.base;245    if (lhs.range.limit != rhs.range.limit) return lhs.range.limit < rhs.range.limit;246    if (lhs.preferred != rhs.preferred) return lhs.preferred and !rhs.preferred;247    if (lhs.line != rhs.line) return lhs.line < rhs.line;248    return std.mem.lessThan(u8, lhs.filename, rhs.filename);249}250251test "interval contains points in half-open range" {252    const interval = try Interval.init(10, 20);253254    try std.testing.expect(!interval.contains(9));255    try std.testing.expect(interval.contains(10));256    try std.testing.expect(interval.contains(19));257    try std.testing.expect(!interval.contains(20));258    try std.testing.expect(interval.overlaps(try Interval.init(19, 30)));259    try std.testing.expect(!interval.overlaps(try Interval.init(20, 30)));260}261262test "map remembers addresses marked unresolvable" {263    var map: Index = .{};264    defer map.deinit(std.testing.allocator);265266    try std.testing.expect(!map.isUnresolved(0x1000));267    try map.markUnresolved(std.testing.allocator, 0x1000);268    try map.markUnresolved(std.testing.allocator, 0x1000);269    try std.testing.expect(map.isUnresolved(0x1000));270    try std.testing.expect(!map.isUnresolved(0x1001));271}272273test "map interns files and lines and accumulates samples" {274    var map: Index = .{};275    defer map.deinit(std.testing.allocator);276277    const first = try map.getLine(std.testing.allocator, "/tmp/app.zig", 12);278    const second = try map.getLine(std.testing.allocator, "/tmp/app.zig", 12);279    first.addSample();280    first.addSample();281282    try std.testing.expectEqual(first, second);283    try std.testing.expectEqualStrings("/tmp/app.zig", first.file.name);284    try std.testing.expectEqual(@as(u64, 12), first.number);285    try std.testing.expectEqual(@as(u64, 2), second.sampleCount());286}287288test "queued ranges prefer inline attribution for identical ranges" {289    var map: Index = .{};290    defer map.deinit(std.testing.allocator);291292    var queued = [_]QueuedRange{293        .{ .filename = "/tmp/original.zig", .line = 8, .range = try Interval.init(100, 120) },294        .{ .filename = "/tmp/inline.zig", .line = 4, .range = try Interval.init(100, 120), .preferred = true },295    };296297    try map.addQueuedRanges(std.testing.allocator, &queued);298299    const line = map.findLineByAddress(110).?;300    try std.testing.expectEqualStrings("/tmp/inline.zig", line.file.name);301    try std.testing.expectEqual(@as(u64, 4), line.number);302    try std.testing.expectEqual(@as(usize, 1), map.ranges.items.len);303}304305test "overlapping ranges keep the first inserted attribution" {306    var map: Index = .{};307    defer map.deinit(std.testing.allocator);308309    const first = try map.addRange(std.testing.allocator, "/tmp/first.zig", 1, try Interval.init(10, 20));310    const second = try map.addRange(std.testing.allocator, "/tmp/second.zig", 2, try Interval.init(15, 25));311312    try std.testing.expectEqual(first, second);313    try std.testing.expectEqualStrings("/tmp/first.zig", map.findLineByAddress(16).?.file.name);314}315316test "address lookup uses sorted half-open ranges" {317    var map: Index = .{};318    defer map.deinit(std.testing.allocator);319320    _ = try map.addRange(std.testing.allocator, "/tmp/b.zig", 2, try Interval.init(30, 40));321    _ = try map.addRange(std.testing.allocator, "/tmp/a.zig", 1, try Interval.init(10, 20));322323    try std.testing.expectEqualStrings("/tmp/a.zig", map.findLineByAddress(10).?.file.name);324    try std.testing.expect(map.findLineByAddress(20) == null);325    try std.testing.expectEqualStrings("/tmp/b.zig", map.findLineByAddress(39).?.file.name);326}327328test "name lookup matches file suffix only when the line exists" {329    var map: Index = .{};330    defer map.deinit(std.testing.allocator);331332    _ = try map.getLine(std.testing.allocator, "/home/me/src/main.zig", 42);333334    try std.testing.expect(map.findLineByName("src/main.zig:42") != null);335    try std.testing.expect(map.findLineByName("src/main.zig:41") == null);336    try std.testing.expect(map.findLineByName("main.zig") == null);337    try std.testing.expect(map.findLineByName("main.zig:not-a-line") == null);338}339340test "sample matching prefers selected callchain line over first ip hit" {341    var map: Index = .{};342    defer map.deinit(std.testing.allocator);343344    const ip_line = try map.addRange(std.testing.allocator, "/tmp/ip.zig", 1, try Interval.init(100, 110));345    const selected = try map.addRange(std.testing.allocator, "/tmp/selected.zig", 2, try Interval.init(200, 210));346347    const matched = map.matchSample(.{ .ip = 105, .callchain = &.{206} }, selected);348349    try std.testing.expectEqual(selected, matched.line.?);350    try std.testing.expect(matched.selected_hit);351    try std.testing.expect(ip_line != matched.line.?);352}353354test "sample matching keeps first line when selected line is absent" {355    var map: Index = .{};356    defer map.deinit(std.testing.allocator);357358    const first = try map.addRange(std.testing.allocator, "/tmp/first.zig", 1, try Interval.init(100, 110));359    _ = try map.addRange(std.testing.allocator, "/tmp/second.zig", 2, try Interval.init(200, 210));360361    const matched = map.matchSample(.{ .ip = 0, .callchain = &.{ 110, 210 } }, null);362363    try std.testing.expectEqual(first, matched.line.?);364    try std.testing.expect(!matched.selected_hit);365}

1pub const source_map = @import("map.zig");