//! 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: `ready@4.3: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){a@0.0:u3;b@0.3: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", (try parse(arena, "[4]`struct std::pair`")).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); }