lib/coz/src/map.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 const profile = @import("profile.zig");
4
5 pub const Interval = struct {
6 base: usize,
7 limit: usize,
8
9 pub fn init(base: usize, limit: usize) !Interval {
10 if (limit <= base) return error.InvalidInterval;
11 return .{ .base = base, .limit = limit };
12 }
13
14 pub fn unit(address: usize) Interval {
15 return .{ .base = address, .limit = address +| 1 };
16 }
17
18 pub fn shifted(self: Interval, offset: usize) Interval {
19 return .{ .base = self.base +% offset, .limit = self.limit +% offset };
20 }
21
22 pub fn contains(self: Interval, address: usize) bool {
23 return self.base <= address and address < self.limit;
24 }
25
26 pub fn overlaps(self: Interval, other: Interval) bool {
27 return self.base < other.limit and other.base < self.limit;
28 }
29 };
30
31 pub const Line = struct {
32 file: *File,
33 number: u64,
34 samples: std.atomic.Value(u64) = .init(0),
35
36 pub fn addSample(self: *Line) void {
37 _ = self.samples.fetchAdd(1, .monotonic);
38 }
39
40 pub fn sampleCount(self: *const Line) u64 {
41 return self.samples.load(.monotonic);
42 }
43
44 pub fn location(self: *const Line) profile.Location {
45 return .{ .file = self.file.name, .line = self.number };
46 }
47 };
48
49 pub const File = struct {
50 name: []const u8,
51 lines: std.AutoHashMapUnmanaged(u64, *Line) = .empty,
52
53 fn getLine(self: *File, allocator: std.mem.Allocator, number: u64) !*Line {
54 if (self.lines.get(number)) |line| return line;
55
56 const line = try allocator.create(Line);
57 errdefer allocator.destroy(line);
58 line.* = .{ .file = self, .number = number };
59
60 try self.lines.put(allocator, number, line);
61 return line;
62 }
63
64 fn hasLine(self: *const File, number: u64) bool {
65 return self.lines.contains(number);
66 }
67
68 fn findLine(self: *const File, number: u64) ?*Line {
69 return self.lines.get(number);
70 }
71
72 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 };
79
80 pub const QueuedRange = struct {
81 filename: []const u8,
82 line: u64,
83 range: Interval,
84 preferred: bool = false,
85 };
86
87 pub const RangeEntry = struct {
88 range: Interval,
89 line: *Line,
90 };
91
92 pub const Sample = struct {
93 ip: usize,
94 callchain: []const usize = &.{},
95 };
96
97 pub const Match = struct {
98 line: ?*Line = null,
99 selected_hit: bool = false,
100 };
101
102 pub const Index = struct {
103 files: std.StringHashMapUnmanaged(*File) = .empty,
104 ranges: std.ArrayListUnmanaged(RangeEntry) = .empty,
105 unresolved: std.AutoHashMapUnmanaged(usize, void) = .empty,
106
107 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 }
119
120 pub fn markUnresolved(self: *Index, allocator: std.mem.Allocator, address: usize) !void {
121 try self.unresolved.put(allocator, address, {});
122 }
123
124 pub fn isUnresolved(self: *const Index, address: usize) bool {
125 return self.unresolved.contains(address);
126 }
127
128 pub fn getFile(self: *Index, allocator: std.mem.Allocator, filename: []const u8) !*File {
129 if (self.files.get(filename)) |file| return file;
130
131 const owned_name = try allocator.dupe(u8, filename);
132 errdefer allocator.free(owned_name);
133
134 const file = try allocator.create(File);
135 errdefer allocator.destroy(file);
136 file.* = .{ .name = owned_name };
137
138 try self.files.put(allocator, owned_name, file);
139 return file;
140 }
141
142 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 }
145
146 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;
154
155 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 }
160
161 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 }
167
168 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 }
184
185 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;
189
190 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 }
198
199 pub fn matchSample(self: *const Index, sample: Sample, selected: ?*const Line) Match {
200 var result: Match = .{};
201 var first_hit = false;
202
203 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 }
208
209 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 }
219
220 return result;
221 }
222
223 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 }
230
231 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 };
238
239 fn selectedLineMatches(selected: ?*const Line, line: *const Line) bool {
240 return if (selected) |expected| expected == line else false;
241 }
242
243 fn 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 }
250
251 test "interval contains points in half-open range" {
252 const interval = try Interval.init(10, 20);
253
254 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 }
261
262 test "map remembers addresses marked unresolvable" {
263 var map: Index = .{};
264 defer map.deinit(std.testing.allocator);
265
266 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 }
272
273 test "map interns files and lines and accumulates samples" {
274 var map: Index = .{};
275 defer map.deinit(std.testing.allocator);
276
277 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();
281
282 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 }
287
288 test "queued ranges prefer inline attribution for identical ranges" {
289 var map: Index = .{};
290 defer map.deinit(std.testing.allocator);
291
292 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 };
296
297 try map.addQueuedRanges(std.testing.allocator, &queued);
298
299 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 }
304
305 test "overlapping ranges keep the first inserted attribution" {
306 var map: Index = .{};
307 defer map.deinit(std.testing.allocator);
308
309 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));
311
312 try std.testing.expectEqual(first, second);
313 try std.testing.expectEqualStrings("/tmp/first.zig", map.findLineByAddress(16).?.file.name);
314 }
315
316 test "address lookup uses sorted half-open ranges" {
317 var map: Index = .{};
318 defer map.deinit(std.testing.allocator);
319
320 _ = 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));
322
323 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 }
327
328 test "name lookup matches file suffix only when the line exists" {
329 var map: Index = .{};
330 defer map.deinit(std.testing.allocator);
331
332 _ = try map.getLine(std.testing.allocator, "/home/me/src/main.zig", 42);
333
334 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 }
339
340 test "sample matching prefers selected callchain line over first ip hit" {
341 var map: Index = .{};
342 defer map.deinit(std.testing.allocator);
343
344 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));
346
347 const matched = map.matchSample(.{ .ip = 105, .callchain = &.{206} }, selected);
348
349 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 }
353
354 test "sample matching keeps first line when selected line is absent" {
355 var map: Index = .{};
356 defer map.deinit(std.testing.allocator);
357
358 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));
360
361 const matched = map.matchSample(.{ .ip = 0, .callchain = &.{ 110, 210 } }, null);
362
363 try std.testing.expectEqual(first, matched.line.?);
364 try std.testing.expect(!matched.selected_hit);
365 }