summaryrefslogtreecommitdiff
path: root/src/instr/types.zig
blob: 1f6615ad11b9b5f3d3aec25de438254dd11568b0 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
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);
}