summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorGabriel Schneider <[email protected]>2026-11-10 11:32:21 -0300
committerGabriel Schneider <[email protected]>2026-11-10 12:08:27 -0300
commitb426a8a99bcad81ecbb41d1f2a2e83738c29d8e1 (patch)
tree06e303f1f33ce53cfc2d8a2043e24f032877f9ad /src
parent7f363779cb99b0820cce69c433bcfab87bb3d709 (diff)
downloadcomputeranim-b426a8a99bcad81ecbb41d1f2a2e83738c29d8e1.tar.gz
computeranim-b426a8a99bcad81ecbb41d1f2a2e83738c29d8e1.zip
llvm: a pass that instruments for animation, its runtime, ztrace cc
llvm/pass.cpp is an LLVM pass plugin: lines, stores, loads, calls and variables, each call into the runtime carrying names and type descriptions, selected by globs (-ztrace-only, -ztrace-mem), before the optimizer by default. src/instr/rt.zig is the runtime (libztrace-rt.a), which also answers clang's own coverage and -finstrument-functions hooks; src/instr/types.zig the grammar of the type descriptions and its parser. ztrace cc adds all of it to a compiler command. test-llvm compiles fib, two sorts, a linked list and a BFS through ztrace cc and asserts on their recordings; bench-llvm measures what each selection costs. Co-Authored-By: Claude Fable 5.2 <[email protected]>
Diffstat (limited to 'src')
-rw-r--r--src/cli/cc.zig116
-rw-r--r--src/cli/main.zig2
-rw-r--r--src/instr/bench.zig70
-rw-r--r--src/instr/rt.zig227
-rw-r--r--src/instr/test.zig464
-rw-r--r--src/instr/types.zig215
6 files changed, 1094 insertions, 0 deletions
diff --git a/src/cli/cc.zig b/src/cli/cc.zig
new file mode 100644
index 0000000..1d08b51
--- /dev/null
+++ b/src/cli/cc.zig
@@ -0,0 +1,116 @@
+//! ztrace cc: a compiler command with the instrumentation added, so a
+//! program compiled from source records itself under `ztrace run`.
+const std = @import("std");
+const util = @import("util.zig");
+const fail = util.fail;
+
+pub const usage =
+ \\usage: ztrace cc [--instr LIST] [--only GLOBS] [--mem GLOBS] [--late] [--plugin SO] [--rt A] -- CLANG ARGS
+ \\
+ \\Runs CLANG (clang, clang++) with ARGS and -g, the pass plugin and its
+ \\options, and when the command links, the runtime:
+ \\
+ \\ ztrace cc -- clang sort.c -o sort && ztrace run -- ./sort
+ \\
+ \\ --instr LIST comma separated, default lines,calls,vars,stores
+ \\ lines `line` at each source line reached
+ \\ stores `mem_write`, with the bytes, after each store to a
+ \\ variable or through a pointer; a memset or
+ \\ memcpy is one, of its first 64 KiB at most
+ \\ loads `mem_read` after each load
+ \\ calls `call` at function entry, `ret` with the value at exit
+ \\ vars `variable` for each named local and global:
+ \\ address, size, name, type description
+ \\ from stock clang, no plugin and no names:
+ \\ edges `edge` (-fsanitize-coverage=trace-pc-guard)
+ \\ cmps `cmp`, and `edge`: clang compares only along with edges
+ \\ (-fsanitize-coverage=trace-pc-guard,trace-cmp)
+ \\ cyg `call`, `ret` (-finstrument-functions)
+ \\ --only GLOBS comma separated; the plugin instruments only the functions
+ \\ and globals whose name, source path or source file name
+ \\ matches one: 'sort*,*/vdbe.c'
+ \\ --mem GLOBS of those, the functions whose stores and loads are recorded
+ \\ (default: all of them). Stores are most of a recording:
+ \\ in a large program, name where memory matters.
+ \\ --late instrument after optimization: the stores and lines of the
+ \\ code that runs, not of the source
+ \\ --plugin SO the pass (default: ../lib/ztrace-pass.so from this program)
+ \\ --rt A the runtime (default: ../lib/libztrace-rt.a)
+ \\
+;
+
+pub fn run(init: std.process.Init, args: []const [:0]const u8) !void {
+ const arena = init.arena.allocator();
+ var instr: []const u8 = "lines,calls,vars,stores";
+ var only: ?[]const u8 = null;
+ var mem: ?[]const u8 = null;
+ var late = false;
+ var plugin: ?[]const u8 = null;
+ var rt: ?[]const u8 = null;
+ var i: usize = 0;
+ while (i < args.len) : (i += 1) {
+ const arg = args[i];
+ if (std.mem.eql(u8, arg, "--")) {
+ i += 1;
+ break;
+ } else if (std.mem.eql(u8, arg, "--late")) {
+ late = true;
+ } else if (i + 1 < args.len and std.mem.eql(u8, arg, "--instr")) {
+ i += 1;
+ instr = args[i];
+ } else if (i + 1 < args.len and std.mem.eql(u8, arg, "--only")) {
+ i += 1;
+ only = args[i];
+ } else if (i + 1 < args.len and std.mem.eql(u8, arg, "--mem")) {
+ i += 1;
+ mem = args[i];
+ } else if (i + 1 < args.len and std.mem.eql(u8, arg, "--plugin")) {
+ i += 1;
+ plugin = args[i];
+ } else if (i + 1 < args.len and std.mem.eql(u8, arg, "--rt")) {
+ i += 1;
+ rt = args[i];
+ } else fail(usage, .{});
+ }
+ if (i >= args.len) fail(usage, .{});
+ const lib = try std.fs.path.join(arena, &.{ try std.process.executableDirPathAlloc(init.io, arena), "..", "lib" });
+
+ var argv: std.ArrayList([]const u8) = .empty;
+ for (args[i..]) |arg| try argv.append(arena, arg);
+ // What a command that only links does not use is no warning.
+ try argv.appendSlice(arena, &.{ "--start-no-unused-arguments", "-g" });
+ // The plugin's own words, which it checks; the rest are clang's flags.
+ var pass: std.ArrayList(u8) = .empty;
+ var words = std.mem.tokenizeScalar(u8, instr, ',');
+ while (words.next()) |word| {
+ if (std.mem.eql(u8, word, "edges")) {
+ try argv.append(arena, "-fsanitize-coverage=trace-pc-guard");
+ } else if (std.mem.eql(u8, word, "cmps")) {
+ try argv.append(arena, "-fsanitize-coverage=trace-pc-guard,trace-cmp");
+ } else if (std.mem.eql(u8, word, "cyg")) {
+ try argv.append(arena, "-finstrument-functions");
+ } else try pass.print(arena, "{s}{s}", .{ if (pass.items.len > 0) "," else "", word });
+ }
+ if (pass.items.len > 0) {
+ const so = plugin orelse try std.fs.path.join(arena, &.{ lib, "ztrace-pass.so" });
+ // -load as well: the plugin's options must exist when -mllvm is read,
+ // which is before -fpass-plugin loads it.
+ try argv.appendSlice(arena, &.{ try std.fmt.allocPrint(arena, "-fpass-plugin={s}", .{so}), "-Xclang", "-load", "-Xclang", so });
+ try argv.appendSlice(arena, &.{ "-mllvm", try std.fmt.allocPrint(arena, "-ztrace-instr={s}", .{pass.items}) });
+ if (only) |globs| try argv.appendSlice(arena, &.{ "-mllvm", try std.fmt.allocPrint(arena, "-ztrace-only={s}", .{globs}) });
+ if (mem) |globs| try argv.appendSlice(arena, &.{ "-mllvm", try std.fmt.allocPrint(arena, "-ztrace-mem={s}", .{globs}) });
+ if (late) try argv.appendSlice(arena, &.{ "-mllvm", "-ztrace-late" });
+ }
+ try argv.append(arena, "--end-no-unused-arguments");
+ // The command links unless it says where to stop. The whole archive: with
+ // -fsanitize-coverage clang links weak callbacks of its own first, and
+ // only a runtime already in the link replaces them. -x none: after an
+ // -x c the archive would be read as source.
+ const links = for (args[i..]) |arg| {
+ if (std.mem.eql(u8, arg, "-c") or std.mem.eql(u8, arg, "-S") or std.mem.eql(u8, arg, "-E") or std.mem.eql(u8, arg, "-fsyntax-only")) break false;
+ } else true;
+ if (links) try argv.appendSlice(arena, &.{ "-x", "none", "-Wl,--whole-archive", rt orelse try std.fs.path.join(arena, &.{ lib, "libztrace-rt.a" }), "-Wl,--no-whole-archive" });
+
+ const err = std.process.replace(init.io, .{ .argv = argv.items });
+ fail("{s}: {t}\n", .{ argv.items[0], err });
+}
diff --git a/src/cli/main.zig b/src/cli/main.zig
index 72b894a..1ac019f 100644
--- a/src/cli/main.zig
+++ b/src/cli/main.zig
@@ -9,6 +9,7 @@ const commands = .{
.run = @import("run.zig"),
.dump = @import("dump.zig"),
.show = @import("show.zig"),
+ .cc = @import("cc.zig"),
};
const usage =
@@ -19,6 +20,7 @@ const usage =
\\ run record a program that carries a ring producer (agent, instrumentation)
\\ dump print a recording's events
\\ show print a recording's summary, or the program's state at a moment
+ \\ cc compile a program with instrumentation that records it
\\
\\`ztrace COMMAND --help` for each.
\\
diff --git a/src/instr/bench.zig b/src/instr/bench.zig
new file mode 100644
index 0000000..38ad1a3
--- /dev/null
+++ b/src/instr/bench.zig
@@ -0,0 +1,70 @@
+//! What instrumentation costs, measured on a target: runs PROGRAM and prints
+//! one line, its wall time in milliseconds and the events it emitted by kind.
+//!
+//! bench PROGRAM ARGS with a ring, drained and counted, nothing recorded
+//! bench --untraced PROGRAM ARGS with no ring: the calls return at once
+//! bench --step PROGRAM ARGS held at each `line` by the ring's stop mask, resumed at once
+//!
+//! llvm/bench.sh makes the tables from it.
+const std = @import("std");
+const linux = std.os.linux;
+const zt = @import("ztrace");
+
+var counts: [64]u64 = @splat(0);
+
+pub fn main(init: std.process.Init) !void {
+ const arena = init.arena.allocator();
+ const args = try init.minimal.args.toSlice(arena);
+ const mode: enum { ring, untraced, step } = if (args.len > 1 and std.mem.eql(u8, args[1], "--untraced")) .untraced else if (args.len > 1 and std.mem.eql(u8, args[1], "--step")) .step else .ring;
+ const rest = args[@as(usize, 1) + @intFromBool(mode != .ring) ..];
+ if (rest.len == 0) return error.Usage;
+ const argv = try arena.allocSentinel(?[*:0]const u8, rest.len, null);
+ for (argv, rest) |*dst, s| dst.* = s.ptr;
+ const env = init.minimal.environ.block.slice;
+
+ const start = zt.event.now();
+ if (mode == .untraced) {
+ const pid = linux.fork();
+ if (pid == 0) {
+ _ = linux.execve(argv[0].?, argv.ptr, env.ptr);
+ linux.exit_group(127);
+ }
+ var status: u32 = 0;
+ _ = linux.waitpid(@intCast(pid), @ptrCast(&status), 0);
+ } else {
+ var session = try zt.host.Session.spawn(arena, argv[0].?, argv.ptr, env, .{ .stop_mask = if (mode == .step) zt.Kind.line.bit() else 0 });
+ defer session.close();
+ const ring = &session.ring;
+ // Step mode answers each stop at once. Otherwise the consumer drains
+ // what there is and sleeps a moment, never on the ring's futex: so
+ // the producer pays neither a wake nor for a cache line the consumer
+ // keeps taking, and the time is the cost of producing.
+ while (true) {
+ const rec = ring.peek() orelse {
+ if (session.exit_code != null) break;
+ var status: u32 = 0;
+ if (linux.waitpid(session.pid, @ptrCast(&status), linux.W.NOHANG) != 0) {
+ session.exit_code = 0;
+ } else if (mode == .step) std.atomic.spinLoopHint() else _ = linux.nanosleep(&.{ .sec = 0, .nsec = 200_000 }, null);
+ continue;
+ };
+ const kind = rec.ev.kind;
+ counts[@intFromEnum(kind)] += 1;
+ ring.advance(rec);
+ if (mode == .step and kind == .line) ring.resumeAll();
+ }
+ }
+ const ms = @as(f64, @floatFromInt(zt.event.now() - start)) / 1e6;
+
+ var buf: [1024]u8 = undefined;
+ var out = std.Io.File.stdout().writer(init.io, &buf);
+ const w = &out.interface;
+ var total: u64 = 0;
+ for (counts) |n| total += n;
+ try w.print("{d:.2} {d}", .{ ms, total });
+ for (counts, 0..) |n, kind| {
+ if (n > 0) try w.print(" {t}={d}", .{ @as(zt.Kind, @enumFromInt(kind)), n });
+ }
+ try w.print("\n", .{});
+ try w.flush();
+}
diff --git a/src/instr/rt.zig b/src/instr/rt.zig
new file mode 100644
index 0000000..3719409
--- /dev/null
+++ b/src/instr/rt.zig
@@ -0,0 +1,227 @@
+//! libztrace-rt.a: what compiler-instrumented code calls, linked into the
+//! target; every call becomes an event in the ring the tracer handed over,
+//! or returns at once when there is none. Two faces:
+//!
+//! Our pass (llvm/pass.cpp):
+//! __zt_line(file, line, column) line a0=file a1=line a2=column
+//! __zt_store(addr, size) mem_write a0=addr a1=len, the bytes (see `wrote`)
+//! __zt_load(addr, size) mem_read a0=addr a1=len
+//! __zt_enter(name, type, sp, site) call a0=function name a1=call site a2=sp a3=function type
+//! __zt_exit(name, value, size) ret a0=function name a1=value, aux=bytes of value (0: none)
+//! __zt_var(addr, size, name, type, arg) variable a0=addr a1=size a2=name a3=type, aux=N for the Nth parameter
+//! file, name and type arrive as pointers to text records and leave as
+//! string ids. The records, and the program's globals, sit in two sections
+//! the pass filled: before the first event the runtime numbers the texts
+//! and emits each as a `string` (from thread 0: no thread), and each global
+//! as a `variable` with one `mem_write` of what it holds, from the thread
+//! that got there first, which is inside no call yet. A local is declared,
+//! never dumped: what it holds arrives with the stores.
+//!
+//! No pc in `line`, `mem_write` and `mem_read`, though event.zig has a
+//! place for one: the source line is the place, and seven bytes would be a
+//! third of each of them in a recording.
+//!
+//! Stock clang, no plugin:
+//! -fsanitize-coverage=trace-pc-guard edge a0=pc
+//! -fsanitize-coverage=trace-cmp cmp aux=operand bytes a0=pc a1=lhs a2=rhs
+//! -finstrument-functions call a0=function address a1=call site a2=frame
+//! ret a0=function address
+//!
+//! Raw syscalls only, no allocation: a store may be anywhere.
+// shortcut: one program, one runtime: the texts of a shared library loaded later are never numbered; walk its sections on dlopen when a target needs it.
+const std = @import("std");
+const linux = std.os.linux;
+const zt = @import("ztrace");
+
+/// 0 untried, 1 starting, 2 tracing, 3 not traced.
+var state: std.atomic.Value(u8) = .init(0);
+var ring: *zt.Ring = undefined;
+
+fn start(tid: u32) bool {
+ @branchHint(.cold);
+ while (true) switch (state.load(.acquire)) {
+ 2 => return true,
+ 3 => return false,
+ // Another thread is emitting the names: nothing may get ahead of them.
+ 1 => _ = linux.sched_yield(),
+ else => if (state.cmpxchgStrong(0, 1, .acquire, .monotonic) == null) {
+ const found = zt.client.get();
+ if (found) |r| {
+ ring = r;
+ names();
+ globals(tid);
+ }
+ state.store(if (found != null) 2 else 3, .release);
+ },
+ };
+}
+
+fn put(tid: u32, kind: zt.Kind, aux: u16, a: [6]u64, payload: []const u8) void {
+ ring.emit(.{ .ts = zt.event.now(), .tid = tid, .kind = kind, .aux = aux, .a = a }, payload);
+}
+
+const Thread = struct {
+ /// A gettid a thread, not an event: the syscall would be half the cost
+ /// of an event.
+ // shortcut: a forked child keeps its parent's tid; reset it in a fork hook once a target forks.
+ tid: u32 = 0,
+ inside: bool = false,
+};
+threadlocal var thread: Thread = .{};
+
+/// The calling thread, for one event; `inside` is the caller's to clear.
+/// Null when nobody listens, or when the thread is already in here: what the
+/// runtime calls (memcpy and strlen, in a libc compiled with the pass) must
+/// not trace itself.
+fn enter() ?*Thread {
+ const s = state.load(.monotonic);
+ if (s == 3) return null;
+ const t = &thread;
+ if (t.inside) return null;
+ t.inside = true;
+ if (t.tid == 0) t.tid = @intCast(linux.gettid());
+ if (s == 2 or start(t.tid)) return t;
+ t.inside = false;
+ return null;
+}
+
+/// An event with no text in it: a text's id is read after `enter`, which
+/// may be what numbers it.
+fn emit(kind: zt.Kind, aux: u16, a: [6]u64, payload: []const u8) void {
+ const t = enter() orelse return;
+ defer t.inside = false;
+ put(t.tid, kind, aux, a, payload);
+}
+
+/// The `mem_write`s of one write (a store, a memset, a memcpy, a global's
+/// first contents), in pieces that fit the smallest ring. a1 is how much was
+/// written from a0 on, so the first piece says the whole length; a payload
+/// shorter than a1 is all that is recorded of it. A write is recorded up to
+/// `most`: a megabyte cleared is not a megabyte in the recording.
+const most = 64 << 10;
+
+fn wrote(tid: u32, addr: usize, len: usize) void {
+ var at: usize = 0;
+ while (at < @min(len, most)) : (at += 2048) {
+ const bytes: [*]const u8 = @ptrFromInt(addr + at);
+ put(tid, .mem_write, 0, .{ addr + at, len - at, 0, 0, 0, 0 }, bytes[0..@min(len - at, 2048)]);
+ }
+}
+
+/// The bounds the linker gives a section named like a C identifier; both 0
+/// when no object has the section.
+fn section(comptime name: []const u8) [2]usize {
+ return .{
+ @intFromPtr(@extern(?*const u8, .{ .name = "__start_" ++ name, .linkage = .weak })),
+ @intFromPtr(@extern(?*const u8, .{ .name = "__stop_" ++ name, .linkage = .weak })),
+ };
+}
+
+/// A text of the program, in section ztrace_strs: this, then the text,
+/// padded to 8 bytes.
+const Text = extern struct {
+ /// The string id. The pass leaves 0, to be numbered here from 1: ids
+ /// small enough to cost a recording a byte or two each. It fixes only
+ /// the ids nothing but a viewer looks up (`types.defId`).
+ id: u64,
+ len: u64,
+};
+
+fn names() void {
+ var at, const end = section("ztrace_strs");
+ var next: u64 = 0;
+ while (at < end) {
+ const text: *Text = @ptrFromInt(at);
+ if (text.id == 0) {
+ next += 1;
+ text.id = next;
+ }
+ const bytes: [*]const u8 = @ptrFromInt(at + @sizeOf(Text));
+ // A text the ring cannot hold is cut: better than none of it.
+ put(0, .string, 0, .{ text.id, 0, 0, 0, 0, 0 }, bytes[0..@min(text.len, ring.hdr.capacity / 2)]);
+ at += @sizeOf(Text) + std.mem.alignForward(usize, text.len, 8);
+ }
+}
+
+/// ztrace_vars: (address, size, name, type)*.
+fn globals(tid: u32) void {
+ var at, const end = section("ztrace_vars");
+ while (at < end) : (at += 32) {
+ const g: *const extern struct { addr: u64, size: u64, name: *const Text, type: *const Text } = @ptrFromInt(at);
+ put(tid, .variable, 0, .{ g.addr, g.size, g.name.id, g.type.id, 0, 0 }, "");
+ wrote(tid, g.addr, g.size);
+ }
+}
+
+// The pass.
+
+export fn __zt_line(file: *const Text, line: u32, column: u32) void {
+ const t = enter() orelse return;
+ defer t.inside = false;
+ put(t.tid, .line, 0, .{ file.id, line, column, 0, 0, 0 }, "");
+}
+
+export fn __zt_store(addr: usize, size: u64) void {
+ const t = enter() orelse return;
+ defer t.inside = false;
+ wrote(t.tid, addr, size);
+}
+
+export fn __zt_load(addr: usize, size: u64) void {
+ emit(.mem_read, 0, .{ addr, size, 0, 0, 0, 0 }, "");
+}
+
+export fn __zt_enter(name: *const Text, type_text: *const Text, sp: usize, site: usize) void {
+ const t = enter() orelse return;
+ defer t.inside = false;
+ put(t.tid, .call, 0, .{ name.id, site, sp, type_text.id, 0, 0 }, "");
+}
+
+export fn __zt_exit(name: *const Text, value: u64, size: u32) void {
+ const t = enter() orelse return;
+ defer t.inside = false;
+ put(t.tid, .ret, @intCast(size), .{ name.id, value, 0, 0, 0, 0 }, "");
+}
+
+export fn __zt_var(addr: usize, size: u64, name: *const Text, type_text: *const Text, arg: u32) void {
+ const t = enter() orelse return;
+ defer t.inside = false;
+ put(t.tid, .variable, @truncate(arg), .{ addr, size, name.id, type_text.id, 0, 0 }, "");
+}
+
+// Stock clang.
+
+export fn __sanitizer_cov_trace_pc_guard_init(_: *u32, _: *u32) void {}
+
+export fn __sanitizer_cov_trace_pc_guard(_: *u32) void {
+ emit(.edge, 0, .{ @returnAddress(), 0, 0, 0, 0, 0 }, "");
+}
+
+comptime {
+ for (.{ u8, u16, u32, u64 }) |T| {
+ const f = struct {
+ fn cmp(lhs: T, rhs: T) callconv(.c) void {
+ emit(.cmp, @sizeOf(T), .{ @returnAddress(), lhs, rhs, 0, 0, 0 }, "");
+ }
+ }.cmp;
+ for (.{ "", "const_" }) |c| @export(&f, .{ .name = std.fmt.comptimePrint("__sanitizer_cov_trace_{s}cmp{d}", .{ c, @sizeOf(T) }) });
+ }
+}
+
+/// `cases` is (count, bits, values...). One event a switch, not one a case:
+/// rhs is the case taken, or the first when it is the default.
+export fn __sanitizer_cov_trace_switch(value: u64, cases: [*]const u64) void {
+ var rhs = cases[2];
+ for (cases[2..][0..cases[0]]) |c| {
+ if (c == value) rhs = c;
+ }
+ emit(.cmp, @intCast(cases[1] / 8), .{ @returnAddress(), value, rhs, 0, 0, 0 }, "");
+}
+
+export fn __cyg_profile_func_enter(function: usize, site: usize) void {
+ emit(.call, 0, .{ function, site, @frameAddress(), 0, 0, 0 }, "");
+}
+
+export fn __cyg_profile_func_exit(function: usize, _: usize) void {
+ emit(.ret, 0, .{ function, 0, 0, 0, 0, 0 }, "");
+}
diff --git a/src/instr/test.zig b/src/instr/test.zig
new file mode 100644
index 0000000..3b67c62
--- /dev/null
+++ b/src/instr/test.zig
@@ -0,0 +1,464 @@
+//! The pass and the runtime on real programs: each test reads the recording
+//! of a target the build compiled with `ztrace cc` and ran under `ztrace
+//! run` (their paths come from build/llvm.zig), as a viewer would: names
+//! and types from the recording alone.
+const std = @import("std");
+const linux = std.os.linux;
+const zt = @import("ztrace");
+const types = @import("types");
+const recordings = @import("recordings");
+
+const gpa = std.testing.allocator;
+const io = std.testing.io;
+const expect = std.testing.expect;
+const expectEqual = std.testing.expectEqual;
+const expectEqualSlices = std.testing.expectEqualSlices;
+const expectEqualStrings = std.testing.expectEqualStrings;
+
+const Item = struct { moment: u64, ev: zt.Event, payload: []const u8 };
+
+/// A recording, its events in order with the moment each is in, and the id
+/// the runtime gave each text.
+const Recording = struct {
+ arena: std.heap.ArenaAllocator,
+ trace: zt.Trace,
+ items: []Item,
+ ids: std.StringHashMapUnmanaged(u64) = .empty,
+
+ fn open(path: []const u8) !Recording {
+ var r: Recording = .{ .arena = .init(gpa), .trace = try zt.Trace.open(gpa, io, path), .items = &.{} };
+ errdefer r.close();
+ const arena = r.arena.allocator();
+ var items: std.ArrayList(Item) = .empty;
+ for (0..r.trace.len) |m| {
+ var events = try (try r.trace.moment(m)).events(arena);
+ while (events.next()) |item| {
+ try items.append(arena, .{ .moment = m, .ev = item.ev, .payload = item.payload });
+ if (item.ev.kind == .string) try r.ids.put(arena, item.payload, item.ev.a[0]);
+ }
+ }
+ r.items = items.items;
+ return r;
+ }
+
+ /// The id of a text; 0, which nothing has, for one the program lacks.
+ fn id(r: *const Recording, text: []const u8) u64 {
+ return r.ids.get(text) orelse 0;
+ }
+
+ fn close(r: *Recording) void {
+ r.trace.close();
+ r.arena.deinit();
+ }
+
+ fn last(r: *const Recording) !zt.store.Moment {
+ return r.trace.moment(r.trace.len - 1);
+ }
+
+ fn string(r: *Recording, of: u64) ![]const u8 {
+ const buf = try r.arena.allocator().alloc(u8, 4096);
+ return (try (try r.last()).string(of, buf)) orelse error.NoSuchString;
+ }
+
+ /// The first `variable` event of that name and type.
+ fn variable(r: *Recording, name: []const u8, type_text: []const u8) !zt.Event {
+ for (r.items) |item| {
+ if (item.ev.kind == .variable and item.ev.a[2] == r.id(name) and item.ev.a[3] == r.id(type_text)) return item.ev;
+ }
+ return error.NoSuchVariable;
+ }
+
+ fn count(r: *const Recording, kind: zt.Kind, a0: u64) usize {
+ var n: usize = 0;
+ for (r.items) |item| n += @intFromBool(item.ev.kind == kind and item.ev.a[0] == a0);
+ return n;
+ }
+
+ /// `T` from the memory recorded as of a moment; every byte must be known.
+ fn read(moment: zt.store.Moment, comptime T: type, addr: u64) !T {
+ var out: T = undefined;
+ var known: [@sizeOf(T)]bool = undefined;
+ try moment.read(addr, std.mem.asBytes(&out), &known);
+ try expect(std.mem.allEqual(bool, &known, true));
+ return out;
+ }
+};
+
+/// The calls of fib(n) from `at` on must be the tree of the source: each
+/// declares its parameter and stores n in it (the recorder keeps the bytes
+/// of a store only where they changed memory: the value is read there),
+/// calls fib(n-1) then fib(n-2), and returns their sum from the frame it
+/// entered. Returns the sum.
+fn fibTree(r: *const Recording, at: *usize, calls: *usize, n: u32) !u32 {
+ const items = r.items;
+ const fib = r.id("fib");
+ while (!((items[at.*].ev.kind == .call or items[at.*].ev.kind == .ret) and items[at.*].ev.a[0] == fib)) at.* += 1;
+ const call, const param, const store = .{ items[at.*].ev, items[at.* + 1].ev, items[at.* + 2] };
+ at.* += 3;
+ calls.* += 1;
+ try expectEqual(zt.Kind.call, call.kind);
+ try expectEqual(r.id("fn(u32)u32"), call.a[3]);
+ try expectEqual(zt.Kind.variable, param.kind);
+ try expectEqual(@as(u16, 1), param.aux);
+ try expectEqual(r.id("n"), param.a[2]);
+ try expectEqual(zt.Kind.mem_write, store.ev.kind);
+ try expectEqual(param.a[0], store.ev.a[0]);
+ try expectEqual(n, try Recording.read(try r.trace.moment(store.moment), u32, param.a[0]));
+
+ const result = if (n < 2) n else try fibTree(r, at, calls, n - 1) + try fibTree(r, at, calls, n - 2);
+ while (items[at.*].ev.kind != .ret) at.* += 1;
+ const ret = items[at.*].ev;
+ at.* += 1;
+ try expectEqual(fib, ret.a[0]);
+ try expectEqual(@as(u64, result), ret.a[1]);
+ try expectEqual(@as(u16, 4), ret.aux);
+ return result;
+}
+
+test "fib: the call tree, arguments and results" {
+ var r = try Recording.open(recordings.fib);
+ defer r.close();
+ var at: usize = 0;
+ var calls: usize = 0;
+ try expectEqual(@as(u32, 8), try fibTree(&r, &at, &calls, 6));
+ try expectEqual(@as(usize, 25), calls);
+ try expectEqual(@as(usize, 25), r.count(.call, r.id("fib")));
+ try expectEqual(@as(usize, 25), r.count(.ret, r.id("fib")));
+ try expectEqualStrings("fib", try r.string(r.id("fib")));
+ // Numbered from 1: a name costs a recording a byte or two each time.
+ try expect(r.id("fib") != 0 and r.id("fib") <= r.ids.count());
+
+ // The recorder's stack at the first fib(1): main, then fib six deep.
+ var seen: usize = 0;
+ const deepest = for (r.items) |item| {
+ if (item.ev.kind == .call and item.ev.a[0] == r.id("fib")) seen += 1;
+ if (seen == 6) break item;
+ } else unreachable;
+ const stack = try (try r.trace.moment(deepest.moment)).stack(gpa, deepest.ev.tid);
+ defer gpa.free(stack);
+ try expectEqual(@as(usize, 7), stack.len);
+ try expectEqual(r.id("main"), stack[0].function);
+ for (stack[1..], stack[0 .. stack.len - 1]) |frame, outer| {
+ try expectEqual(r.id("fib"), frame.function);
+ try expect(frame.sp < outer.sp);
+ }
+}
+
+test "sort: both arrays end sorted, and the lines run as often as the source says" {
+ try sortChecks(recordings.sort);
+}
+
+test "sort -O2: the optimizer keeps what the pass put in before it" {
+ try sortChecks(recordings.sort_O2);
+}
+
+fn sortChecks(recording: []const u8) !void {
+ var r = try Recording.open(recording);
+ defer r.close();
+ const unsorted = [8]i32{ 5, 2, 9, 1, 7, 3, 8, 4 };
+ const sorted = [8]i32{ 1, 2, 3, 4, 5, 7, 8, 9 };
+ for ([_][]const u8{ "bubbled", "inserted" }) |name| {
+ const v = try r.variable(name, "[8]i32");
+ try expectEqual(@as(u64, 32), v.a[1]);
+ try expectEqual(sorted, try Recording.read(try r.last(), [8]i32, v.a[0]));
+ }
+ // The constant they are copied from is a global: known from the start.
+ const source = try r.variable("unsorted", "[8]i32");
+ try expectEqual(unsorted, try Recording.read(try r.trace.moment(0), [8]i32, source.a[0]));
+
+ // Inside bubble the recorder knows its locals, and the array as it then was.
+ const in_bubble = for (r.items) |item| {
+ if (item.ev.kind == .line and item.ev.tid != 0 and (try (try r.trace.moment(item.moment)).stack(r.arena.allocator(), item.ev.tid)).len == 2) break item;
+ } else unreachable;
+ const then = try r.trace.moment(in_bubble.moment);
+ try expectEqual(unsorted, try Recording.read(then, [8]i32, (try r.variable("bubbled", "[8]i32")).a[0]));
+ var depth_of_a: u32 = 0;
+ for (try then.variables(r.arena.allocator())) |v| {
+ if (v.name == r.id("a")) depth_of_a = v.depth;
+ }
+ try expectEqual(@as(u32, 2), depth_of_a);
+ // After main returned only the global is left.
+ const left = try (try r.last()).variables(r.arena.allocator());
+ try expectEqual(@as(usize, 1), left.len);
+ try expectEqual(r.id("unsorted"), left[0].name);
+
+ // Every line event is a line of the one source file, which the recording names.
+ var file: u64 = 0;
+ var hits: [64]u32 = @splat(0);
+ for (r.items) |item| {
+ if (item.ev.kind != .line) continue;
+ if (file == 0) file = item.ev.a[0];
+ try expectEqual(file, item.ev.a[0]);
+ hits[item.ev.a[1]] += 1;
+ }
+ const path = try r.string(file);
+ try expect(std.mem.endsWith(u8, path, "targets/instr_sort.c"));
+ const text = try std.Io.Dir.cwd().readFileAlloc(io, path, r.arena.allocator(), .limited(1 << 20));
+ // The array has 13 inversions: bubble sort swaps that often, insertion
+ // sort shifts that often. Bubble sort compares 8*7/2 times.
+ const expected = [_]struct { []const u8, u32 }{
+ .{ "if (a[j] > a[j + 1]) {", 28 },
+ .{ "a[j + 1] = t;", 13 },
+ .{ "a[j + 1] = a[j];", 13 },
+ .{ "int key = a[i];", 7 },
+ .{ "bubble(bubbled, N);", 1 },
+ };
+ var found: usize = 0;
+ var lines = std.mem.splitScalar(u8, text, '\n');
+ var number: usize = 1;
+ while (lines.next()) |line| : (number += 1) {
+ const code = std.mem.trim(u8, line, " ");
+ // No event on a line with no code.
+ if (code.len == 0 or std.mem.startsWith(u8, code, "//") or std.mem.startsWith(u8, code, "#")) try expectEqual(@as(u32, 0), hits[number]);
+ for (expected) |e| {
+ if (!std.mem.eql(u8, code, e[0])) continue;
+ try expectEqual(e[1], hits[number]);
+ found += 1;
+ }
+ }
+ try expectEqual(expected.len, found);
+}
+
+/// The values of a list from `head` on, following `next` through the memory
+/// recorded as of `moment`, by the offsets of the node's description.
+fn listValues(moment: zt.store.Moment, node: types.Type, head: u64, out: []i32) ![]i32 {
+ var at = head;
+ var n: usize = 0;
+ while (at != 0) : (n += 1) {
+ out[n] = try Recording.read(moment, i32, at + node.field("value").?.offset);
+ at = try Recording.read(moment, u64, at + node.field("next").?.offset);
+ }
+ return out[0..n];
+}
+
+test "list: the recorded stores are the list, at every push and at the end" {
+ var r = try Recording.open(recordings.list);
+ defer r.close();
+ const arena = r.arena.allocator();
+
+ // From the variable to the shape of a node, through the type descriptions.
+ const list = try r.variable("list", "*`struct node`");
+ const pointer = try types.parse(arena, try r.string(list.a[3]));
+ const node = try types.parse(arena, try r.string(types.defId(pointer.pointer.named)));
+ try expectEqual(@as(?u64, 16), node.size());
+ try expectEqualStrings("struct node", node.field("next").?.type.pointer.named);
+
+ // Each push returns a list one longer: its squares, newest first.
+ var buf: [8]i32 = undefined;
+ var pushes: usize = 0;
+ for (r.items) |item| {
+ if (item.ev.kind != .ret or item.ev.a[0] != r.id("push")) continue;
+ pushes += 1;
+ const values = try listValues(try r.trace.moment(item.moment), node, item.ev.a[1], &buf);
+ try expectEqual(pushes, values.len);
+ for (values, 0..) |v, i| try expectEqual(@as(i32, @intCast((pushes - i) * (pushes - i))), v);
+ }
+ try expectEqual(@as(usize, 5), pushes);
+
+ // Reversed in place, and left in the global.
+ const end = try r.last();
+ const head = try Recording.read(end, u64, list.a[0]);
+ try expectEqualSlices(i32, &.{ 1, 4, 9, 16, 25 }, try listValues(end, node, head, &buf));
+ const globals = try end.variables(arena);
+ try expectEqual(@as(usize, 1), globals.len);
+ try expectEqual(@as(u32, 0), globals[0].depth);
+}
+
+test "bfs: distances and visiting order, the graph known from the start" {
+ var r = try Recording.open(recordings.bfs);
+ defer r.close();
+ const end = try r.last();
+
+ const distance = try r.variable("distance", "[7]i32");
+ try expectEqual([7]i32{ 0, 1, 1, 2, 3, 4, -1 }, try Recording.read(end, [7]i32, distance.a[0]));
+ const order = try r.variable("order", "[7]i32");
+ try expectEqual([7]i32{ 0, 1, 2, 3, 4, 5, 0 }, try Recording.read(end, [7]i32, order.a[0]));
+
+ // The edge list is constant: in the first moment already. The matrix
+ // main builds from it is symmetric and has each edge twice.
+ const edges = try Recording.read(try r.trace.moment(0), [6][2]i32, (try r.variable("edges", "[6][2]i32")).a[0]);
+ const adjacent = try Recording.read(end, [7][7]i32, (try r.variable("adjacent", "[7][7]i32")).a[0]);
+ var ones: usize = 0;
+ for (adjacent) |row| {
+ for (row) |cell| ones += @intCast(cell);
+ }
+ try expectEqual(2 * edges.len, ones);
+ for (edges) |e| try expectEqual(@as(i32, 1), adjacent[@intCast(e[1])][@intCast(e[0])]);
+
+ // bfs returns how many it reached; its queue lived only during the call.
+ const queue = try r.variable("queue", "[7]i32");
+ for (r.items) |item| {
+ if (item.ev.kind != .ret or item.ev.a[0] != r.id("bfs")) continue;
+ try expectEqual(@as(u64, 6), item.ev.a[1]);
+ try expectEqual([6]i32{ 0, 1, 2, 3, 4, 5 }, try Recording.read(try r.trace.moment(item.moment), [6]i32, queue.a[0]));
+ }
+ try expectEqual(@as(usize, 1), r.count(.ret, r.id("bfs")));
+ for (try end.variables(r.arena.allocator())) |v| try expect(v.name != r.id("queue"));
+}
+
+test "only: nothing outside the selection, by function name" {
+ var r = try Recording.open(recordings.sort_only);
+ defer r.close();
+ // Of three functions and a global, bubble alone: its call, its five locals.
+ var calls: usize = 0;
+ var variables: usize = 0;
+ var writes: usize = 0;
+ for (r.items) |item| switch (item.ev.kind) {
+ .call => {
+ try expectEqual(r.id("bubble"), item.ev.a[0]);
+ calls += 1;
+ },
+ .variable => variables += 1,
+ .mem_write => writes += 1,
+ .line => try expect(item.ev.a[1] >= 11 and item.ev.a[1] <= 21),
+ else => {},
+ };
+ try expectEqual(@as(usize, 1), calls);
+ try expectEqual(@as(usize, 5), variables);
+ try expect(writes > 13);
+ try expect(r.ids.get("bubble") != null and r.ids.get("insertion") == null and r.ids.get("unsorted") == null);
+}
+
+test "mem: lines and calls in the whole file, stores in one function" {
+ var r = try Recording.open(recordings.sort_mem);
+ defer r.close();
+ var full = try Recording.open(recordings.sort);
+ defer full.close();
+ // The file's name selects all of it: every line and call of the full recording.
+ for ([_]zt.Kind{ .line, .call, .ret, .variable }) |kind| {
+ var here: usize = 0;
+ var there: usize = 0;
+ for (r.items) |item| here += @intFromBool(item.ev.kind == kind);
+ for (full.items) |item| there += @intFromBool(item.ev.kind == kind);
+ try expectEqual(there, here);
+ }
+ // Stores only while insertion runs; the one before is the global's contents.
+ var inside = false;
+ var writes: usize = 0;
+ for (r.items) |item| switch (item.ev.kind) {
+ .call, .ret => inside = item.ev.kind == .call and item.ev.a[0] == r.id("insertion"),
+ .mem_write => {
+ try expect(inside or item.ev.a[0] == (try r.variable("unsorted", "[8]i32")).a[0]);
+ writes += @intFromBool(inside);
+ },
+ else => {},
+ };
+ try expect(writes > 13);
+}
+
+test "big: a megabyte written is 64 KiB recorded" {
+ var r = try Recording.open(recordings.big);
+ defer r.close();
+ const end = try r.last();
+ for ([_][]const u8{ "from", "to" }) |name| {
+ const v = try r.variable(name, "[1048576]c8");
+ var bytes: [(64 << 10) + 1]u8 = undefined;
+ var known: [bytes.len]bool = undefined;
+ try end.read(v.a[0], &bytes, &known);
+ try expect(std.mem.allEqual(u8, bytes[0 .. 64 << 10], 7));
+ try expect(std.mem.allEqual(bool, known[0 .. 64 << 10], true));
+ try expect(!known[64 << 10]);
+ }
+ // Four megabytes of globals and writes: four times 64 KiB, and the keyframe.
+ try expect((try std.Io.Dir.cwd().statFile(io, recordings.big, .{})).size < 1 << 20);
+
+ // As the runtime emits them, before the recorder: pieces, each saying how
+ // much was written from its address on.
+ const arena = r.arena.allocator();
+ const path = try arena.dupeSentinel(u8, recordings.big_program, 0);
+ var session = try zt.host.Session.spawn(arena, path, &.{ path, null }, &.{}, .{});
+ defer session.close();
+ const Pieces = struct {
+ name: u64 = 0,
+ from: u64 = 0,
+ bytes: u64 = 0,
+ first: u64 = 0,
+ last: u64 = 0,
+
+ fn emit(ctx: *anyopaque, ev: *const zt.Event, payload: []const u8) anyerror!void {
+ const p: *@This() = @ptrCast(@alignCast(ctx));
+ if (ev.kind == .string and std.mem.eql(u8, payload, "from")) p.name = ev.a[0];
+ if (ev.kind == .variable and ev.a[2] == p.name) p.from = ev.a[0];
+ // The memset, not the global's first contents.
+ if (ev.kind != .mem_write or ev.a[0] -% p.from >= 1 << 20 or payload[0] != 7) return;
+ try expect(payload.len <= 2048 and ev.a[1] >= payload.len);
+ if (p.bytes == 0) p.first = ev.a[1];
+ p.bytes += payload.len;
+ p.last = ev.a[1];
+ }
+ };
+ var pieces: Pieces = .{};
+ while (try session.pump(.{ .ctx = &pieces, .emitFn = Pieces.emit }, std.time.ns_per_ms)) {}
+ try expectEqual(@as(u64, 64 << 10), pieces.bytes);
+ try expectEqual(@as(u64, 1 << 20), pieces.first);
+ try expectEqual(@as(u64, (1 << 20) - (64 << 10) + 2048), pieces.last);
+}
+
+test "own: a program's own memcpy is traced when the program calls it, not when the runtime does" {
+ var r = try Recording.open(recordings.own);
+ defer r.close();
+ // Every mem_write the runtime emits it copies with this memcpy.
+ try expect(r.count(.mem_write, (try r.variable("to", "[8]c8")).a[0]) > 0);
+ try expectEqual(@as(usize, 1), r.count(.call, r.id("memcpy")));
+ try expectEqual(@as(usize, 1), r.count(.call, r.id("strlen")));
+ for (r.items) |item| {
+ if (item.ev.kind == .ret and item.ev.a[0] == r.id("strlen")) try expectEqual(@as(u64, 7), item.ev.a[1]);
+ }
+ try expectEqualStrings("abcdefg", std.mem.sliceTo(&try Recording.read(try r.last(), [8]u8, (try r.variable("to", "[8]c8")).a[0]), 0));
+}
+
+test "step: the ring holds the target at every line, its memory there to read" {
+ var r = try Recording.open(recordings.sort);
+ defer r.close();
+ const arena = r.arena.allocator();
+ var lines: usize = 0;
+ for (r.items) |item| lines += @intFromBool(item.ev.kind == .line);
+
+ const path = try arena.dupeSentinel(u8, recordings.sort_program, 0);
+ var session = try zt.host.Session.spawn(arena, path, &.{ path, null }, &.{}, .{ .stop_mask = zt.Kind.line.bit() });
+ defer session.close();
+ const ring = &session.ring;
+
+ // The array as the events so far say it is, against the target's own.
+ var name: u64 = 0;
+ var addr: u64 = 0;
+ var told: [32]u8 = @splat(0);
+ var compared: usize = 0;
+ var stops: usize = 0;
+ while (true) {
+ const rec = ring.peek() orelse {
+ if (session.exit_code != null) break;
+ var status: u32 = 0;
+ if (linux.waitpid(session.pid, @ptrCast(&status), linux.W.NOHANG) != 0) session.exit_code = linux.W.EXITSTATUS(status) else ring.wait(std.time.ns_per_ms);
+ continue;
+ };
+ const ev = rec.ev.*;
+ if (ev.kind == .string and std.mem.eql(u8, rec.payload, "bubbled")) name = ev.a[0];
+ if (ev.kind == .variable and ev.a[2] == name) addr = ev.a[0];
+ if (ev.kind == .mem_write and ev.a[0] >= addr and ev.a[0] + ev.a[1] <= addr + told.len) {
+ @memcpy(told[ev.a[0] - addr ..][0..rec.payload.len], rec.payload);
+ // From the first copy into it on; before, it is whatever the stack held.
+ compared += @intFromBool(compared == 0 and rec.payload.len == told.len);
+ }
+ ring.advance(rec);
+ if (ev.kind != .line) continue;
+
+ // Held: it emits nothing more until resumed.
+ while (ring.hdr.stopped.load(.acquire) == 0) std.atomic.spinLoopHint();
+ try expect(ring.peek() == null);
+ var live: [32]u8 = undefined;
+ const local = [_]std.posix.iovec{.{ .base = &live, .len = live.len }};
+ const remote = [_]std.posix.iovec_const{.{ .base = @ptrFromInt(addr), .len = live.len }};
+ try expectEqual(live.len, linux.process_vm_readv(session.pid, &local, &remote, 0));
+ if (compared > 0) {
+ try expectEqualSlices(u8, &told, &live);
+ compared += 1;
+ }
+ stops += 1;
+ ring.resumeAll();
+ }
+ try expectEqual(lines, stops);
+ try expect(compared > lines - 16);
+ try expectEqual(@as(?u8, 10), session.exit_code);
+ try expectEqualSlices(i32, &.{ 1, 2, 3, 4, 5, 7, 8, 9 }, &std.mem.bytesToValue([8]i32, &told));
+}
diff --git a/src/instr/types.zig b/src/instr/types.zig
new file mode 100644
index 0000000..1f6615a
--- /dev/null
+++ b/src/instr/types.zig
@@ -0,0 +1,215 @@
+//! The type descriptions the pass (llvm/pass.cpp) attaches to variables and
+//! functions: what a viewer needs to draw a value from its bytes, with no
+//! DWARF. A `variable` event's a3 and a `call` event's a3 are the string ids
+//! of one:
+//!
+//! type := 'void'
+//! | KIND BITS i32 u64 f64, c8 a character, b8 a boolean, x128 opaque bits
+//! | '*' type a pointer or a reference: 8 bytes
+//! | '[' COUNT ']' type an array; [3][4]i32 is three rows of four
+//! | 'fn(' (type (',' type)*)? ')' type a function: its parameters ('...' when variadic), its result
+//! | ('struct' | 'union') '(' BYTES '){' field* '}'
+//! | 'enum(' type '){' (NAME '=' VALUE ';')* '}'
+//! | '`' NAME '`' a named type, described elsewhere
+//! field := NAME '@' BYTE ('.' BIT)? ':' type ';'
+//!
+//! A field sits at a byte offset. A bit-field adds the bit it starts at
+//! within that byte, counted from the least significant, and is as wide as
+//! its type: `[email protected]:u1`. An anonymous member or a C++ base has an empty
+//! NAME. A flexible or variable-length array has COUNT 0.
+//!
+//! A named type is `struct NAME`, `union NAME`, `enum NAME`, or a typedef's
+//! bare name (in C++ qualified: `struct v8::internal::Isolate`). What it is
+//! is one more string, with the id `defId(NAME)`: of all the pass's string
+//! ids (small numbers, given when the program starts) the only ones that
+//! follow from a text. A type the program only declares has none. So a
+//! struct is described once however many variables have it, and one that
+//! points to itself ends:
+//!
+//! struct node { int value; struct node *next; } *head;
+//! size_t n;
+//!
+//! type of head *`struct node`
+//! defId("struct node") struct(16){value@0:i32;next@8:*`struct node`;}
+//! type of n `size_t`
+//! defId("size_t") u64
+const std = @import("std");
+
+pub const Type = union(enum) {
+ void,
+ scalar: Scalar,
+ pointer: *const Type,
+ array: struct { len: u64, elem: *const Type },
+ function: struct { params: []const Type, variadic: bool, result: *const Type },
+ record: struct { kind: enum { @"struct", @"union" }, size: u64, fields: []const Field },
+ @"enum": struct { base: *const Type, items: []const Item },
+ /// Look its description up at `defId`.
+ named: []const u8,
+
+ /// Bytes a value takes. Null for void, a function, and a named type:
+ /// resolve the name first.
+ pub fn size(t: Type) ?u64 {
+ return switch (t) {
+ .void, .function, .named => null,
+ .scalar => |s| (s.bits + 7) / 8,
+ .pointer => 8,
+ .array => |a| a.len * (a.elem.size() orelse return null),
+ .record => |r| r.size,
+ .@"enum" => |e| e.base.size(),
+ };
+ }
+
+ /// The field of a struct or union by name.
+ pub fn field(t: Type, name: []const u8) ?Field {
+ if (t != .record) return null;
+ for (t.record.fields) |f| {
+ if (std.mem.eql(u8, f.name, name)) return f;
+ }
+ return null;
+ }
+};
+
+pub const Scalar = struct {
+ kind: enum(u8) { int = 'i', uint = 'u', float = 'f', char = 'c', bool = 'b', @"opaque" = 'x' },
+ bits: u16,
+};
+
+pub const Field = struct { name: []const u8, offset: u64, bit: u3 = 0, type: Type };
+pub const Item = struct { name: []const u8, value: i128 };
+
+/// The string id of the description of the named type `name`: FNV-1a of
+/// "=" and the name, with the top bit, which no numbered id has.
+pub fn defId(name: []const u8) u64 {
+ var h = std.hash.Fnv1a_64.init();
+ h.update("=");
+ h.update(name);
+ return h.final() | 1 << 63;
+}
+
+pub const Error = error{ BadType, OutOfMemory };
+
+/// A description as a tree, allocated in `arena`; its names point into `text`.
+pub fn parse(arena: std.mem.Allocator, text: []const u8) Error!Type {
+ var p: Parser = .{ .arena = arena, .text = text };
+ const t = try p.type();
+ return if (p.at == text.len) t else error.BadType;
+}
+
+const Parser = struct {
+ arena: std.mem.Allocator,
+ text: []const u8,
+ at: usize = 0,
+
+ fn eat(p: *Parser, word: []const u8) bool {
+ if (!std.mem.startsWith(u8, p.text[p.at..], word)) return false;
+ p.at += word.len;
+ return true;
+ }
+
+ /// The text up to `end`, which is consumed.
+ fn until(p: *Parser, end: u8) ![]const u8 {
+ const len = std.mem.indexOfScalar(u8, p.text[p.at..], end) orelse return error.BadType;
+ defer p.at += len + 1;
+ return p.text[p.at..][0..len];
+ }
+
+ fn number(p: *Parser, comptime T: type, end: u8) !T {
+ return std.fmt.parseInt(T, try p.until(end), 10) catch error.BadType;
+ }
+
+ fn box(p: *Parser, t: Type) !*const Type {
+ const out = try p.arena.create(Type);
+ out.* = t;
+ return out;
+ }
+
+ fn @"type"(p: *Parser) Error!Type {
+ if (p.eat("void")) return .void;
+ if (p.eat("*")) return .{ .pointer = try p.box(try p.type()) };
+ if (p.eat("`")) return .{ .named = try p.until('`') };
+ if (p.eat("[")) {
+ const len = try p.number(u64, ']');
+ return .{ .array = .{ .len = len, .elem = try p.box(try p.type()) } };
+ }
+ if (p.eat("fn(")) {
+ var params: std.ArrayList(Type) = .empty;
+ var variadic = false;
+ while (!p.eat(")")) {
+ if (p.eat("...")) variadic = true else try params.append(p.arena, try p.type());
+ _ = p.eat(",");
+ }
+ return .{ .function = .{ .params = params.items, .variadic = variadic, .result = try p.box(try p.type()) } };
+ }
+ if (p.eat("enum(")) {
+ const base = try p.box(try p.type());
+ if (!p.eat("){")) return error.BadType;
+ var items: std.ArrayList(Item) = .empty;
+ while (!p.eat("}")) try items.append(p.arena, .{ .name = try p.until('='), .value = try p.number(i128, ';') });
+ return .{ .@"enum" = .{ .base = base, .items = items.items } };
+ }
+ const is_union = p.eat("union(");
+ if (is_union or p.eat("struct(")) {
+ const bytes = try p.number(u64, ')');
+ if (!p.eat("{")) return error.BadType;
+ var fields: std.ArrayList(Field) = .empty;
+ while (!p.eat("}")) {
+ var f: Field = .{ .name = try p.until('@'), .offset = 0, .type = .void };
+ var place = std.mem.splitScalar(u8, try p.until(':'), '.');
+ f.offset = std.fmt.parseInt(u64, place.first(), 10) catch return error.BadType;
+ if (place.next()) |bit| f.bit = std.fmt.parseInt(u3, bit, 10) catch return error.BadType;
+ f.type = try p.type();
+ if (!p.eat(";")) return error.BadType;
+ try fields.append(p.arena, f);
+ }
+ return .{ .record = .{ .kind = if (is_union) .@"union" else .@"struct", .size = bytes, .fields = fields.items } };
+ }
+ if (p.at < p.text.len and std.mem.indexOfScalar(u8, "iufcbx", p.text[p.at]) != null) {
+ const start = p.at + 1;
+ p.at = start;
+ while (p.at < p.text.len and std.ascii.isDigit(p.text[p.at])) p.at += 1;
+ return .{ .scalar = .{ .kind = @enumFromInt(p.text[start - 1]), .bits = std.fmt.parseInt(u16, p.text[start..p.at], 10) catch return error.BadType } };
+ }
+ return error.BadType;
+ }
+};
+
+test "descriptions parse to what the pass meant" {
+ var arena_state: std.heap.ArenaAllocator = .init(std.testing.allocator);
+ defer arena_state.deinit();
+ const arena = arena_state.allocator();
+
+ const node = try parse(arena, "struct(16){value@0:i32;next@8:*`struct node`;}");
+ try std.testing.expectEqual(@as(?u64, 16), node.size());
+ try std.testing.expectEqual(Scalar{ .kind = .int, .bits = 32 }, node.field("value").?.type.scalar);
+ const next = node.field("next").?;
+ try std.testing.expectEqual(@as(u64, 8), next.offset);
+ try std.testing.expectEqualStrings("struct node", next.type.pointer.named);
+ try std.testing.expect(node.field("prev") == null);
+
+ // Bit-fields, an anonymous union member, an array of arrays.
+ const bits = try parse(arena, "struct(24){[email protected]:u3;[email protected]:i5;@8:union(8){d@0:f64;p@0:*void;};m@16:[2][3]c8;}");
+ try std.testing.expectEqual(@as(u3, 3), bits.field("b").?.bit);
+ try std.testing.expectEqual(Scalar{ .kind = .int, .bits = 5 }, bits.field("b").?.type.scalar);
+ try std.testing.expectEqual(@as(usize, 2), bits.field("").?.type.record.fields.len);
+ try std.testing.expectEqual(@as(?u64, 6), bits.field("m").?.type.size());
+ try std.testing.expectEqual(@as(u64, 3), bits.field("m").?.type.array.elem.array.len);
+
+ const f = (try parse(arena, "fn(*`struct node`,i32,...)*c8")).function;
+ try std.testing.expectEqual(@as(usize, 2), f.params.len);
+ try std.testing.expect(f.variadic);
+ try std.testing.expectEqual(Scalar{ .kind = .char, .bits = 8 }, f.result.pointer.scalar);
+ try std.testing.expectEqual(Type.void, (try parse(arena, "fn()void")).function.result.*);
+
+ const e = (try parse(arena, "enum(i32){LOW=-1;HIGH=5;}")).@"enum";
+ try std.testing.expectEqualStrings("HIGH", e.items[1].name);
+ try std.testing.expectEqual(@as(i128, -1), e.items[0].value);
+ // A name may hold anything but a backquote.
+ try std.testing.expectEqualStrings("struct std::pair<int, char *>", (try parse(arena, "[4]`struct std::pair<int, char *>`")).array.elem.named);
+
+ for ([_][]const u8{ "", "i", "i32x", "struct(8){a@0:i32}", "[x]i32", "*", "`open", "fn(i32" }) |bad| try std.testing.expectError(error.BadType, parse(arena, bad));
+
+ // FNV-1a of "=", worked out by hand. That the pass agrees is the list
+ // test of src/instr/test.zig, on a real program.
+ try std.testing.expectEqual(@as(u64, 0xaf63b04c8601a1c8), defId(""));
+ try std.testing.expectEqual(@as(u64, 1), defId("size_t") >> 63);
+}