tiny.choir.bytecode.image

1const std = @import("std");2const bytecode = @import("root.zig");3const Reader = bytecode.Reader;45pub const Limits = struct { bytes: u32, entities: u32, depth: u16 };6pub const Range = struct { start: u32, count: u32 };78/// A counted sequence in the existing bytecode format, borrowing immutable bytes.9pub const Ids = struct {10    bytes: []const u8,11    count: u32,1213    pub fn at(self: Ids, index: u32) ?u32 {14        if (index >= self.count) return null;15        var reader = Reader.init(self.bytes);16        for (0..index) |_| _ = reader.readULEBToU32() catch return null;17        return reader.readULEBToU32() catch null;18    }19};2021pub const Operation = struct {22    name: []const u8,23    location: u32,24    parent_block: ?u32,25    results: Range,26    operands: Ids,27    attributes: []const u8,28    attribute_count: u32,29    properties: ?u32,30    successors: Ids,31    region_count: u32,32    encoded: []const u8,33};3435pub const Region = struct { operation: u32, position: u32, block_count: u32 };36pub const Block = struct { region: u32, position: u32, arguments: Range, operation_count: u32 };37pub const Value = struct {38    owner: union(enum) { operation: u32, block: u32 },39    position: u32,40    type: u32,41    location: u32,42};4344/// All ordinals and table records refer to this one bytecode image.45pub const View = struct {46    bytes: []const u8,47    operations: []const Operation,48    regions: []const Region,49    blocks: []const Block,50    values: []const Value,51    strings: []const []const u8,52    dialects: []const bytecode.DialectEntry,53    types: []const []const u8,54    attributes: []const []const u8,55    locations: []const []const u8,56    resources: []const bytecode.Resource,5758    pub fn region(self: View, operation: u32, position: u32) ?u32 {59        for (self.regions, 0..) |item, ordinal| {60            if (item.operation == operation and item.position == position) return @intCast(ordinal);61        }62        return null;63    }6465    pub fn block(self: View, region_ordinal: u32, position: u32) ?u32 {66        for (self.blocks, 0..) |item, ordinal| {67            if (item.region == region_ordinal and item.position == position) {68                return @intCast(ordinal);69            }70        }71        return null;72    }7374    pub fn successor(self: View, operation: u32, position: u32) ?u32 {75        if (operation >= self.operations.len) return null;76        const op = self.operations[operation];77        const parent = op.parent_block orelse return null;78        const local = op.successors.at(position) orelse return null;79        return self.block(self.blocks[parent].region, local);80    }81};8283/// Owns only lookup metadata. The caller keeps the immutable bytecode bytes alive.84pub const Index = opaque {85    pub fn create(allocator: std.mem.Allocator, bytes: []const u8, limits: Limits) !*Index {86        if (bytes.len > limits.bytes) return error.ImageLimit;87        const state = try allocator.create(Data);88        state.* = .{ .allocator = allocator, .bytes = bytes, .limits = limits };89        errdefer state.destroy();90        try state.read();91        return @ptrCast(state);92    }9394    pub fn destroy(self: *Index) void {95        data(self).destroy();96    }9798    pub fn view(self: *const Index) View {99        const state: *const Data = @ptrCast(@alignCast(self));100        return .{101            .bytes = state.bytes,102            .operations = state.operations.items,103            .regions = state.regions.items,104            .blocks = state.blocks.items,105            .values = state.values.items,106            .strings = state.strings.items,107            .dialects = state.dialects.items,108            .types = state.types.items,109            .attributes = state.attributes.items,110            .locations = state.locations.items,111            .resources = state.resources.items,112        };113    }114};115116const Data = struct {117    allocator: std.mem.Allocator,118    bytes: []const u8,119    limits: Limits,120    entities: u32 = 0,121    operations: std.ArrayList(Operation) = .empty,122    regions: std.ArrayList(Region) = .empty,123    blocks: std.ArrayList(Block) = .empty,124    values: std.ArrayList(Value) = .empty,125    strings: std.ArrayList([]const u8) = .empty,126    dialects: std.ArrayList(bytecode.DialectEntry) = .empty,127    types: std.ArrayList([]const u8) = .empty,128    attributes: std.ArrayList([]const u8) = .empty,129    locations: std.ArrayList([]const u8) = .empty,130    resources: std.ArrayList(bytecode.Resource) = .empty,131132    fn destroy(self: *Data) void {133        inline for (.{134            "operations", "regions",    "blocks",    "values",    "strings", "dialects",135            "types",      "attributes", "locations", "resources",136        }) |field| @field(self, field).deinit(self.allocator);137        self.allocator.destroy(self);138    }139140    fn append(self: *Data, comptime field: []const u8, value: anytype) !u32 {141        if (self.entities == self.limits.entities) return error.ImageLimit;142        const list = &@field(self, field);143        const ordinal: u32 = @intCast(list.items.len);144        try list.append(self.allocator, value);145        self.entities += 1;146        return ordinal;147    }148149    fn count(self: *const Data, reader: *Reader) !u32 {150        const result = try reader.readULEBToU32();151        if (result > self.limits.entities) return error.ImageLimit;152        return result;153    }154155    fn read(self: *Data) !void {156        const sections = try bytecode.inspectSections(self.bytes);157        try self.readStrings(sections.strings orelse return error.MissingStrings);158        if (sections.dialects) |bytes| try self.readDialects(bytes);159        if (sections.types) |bytes| try self.readTable(bytes, "types", readType);160        if (sections.attrs) |bytes| try self.readTable(bytes, "attributes", readAttribute);161        if (sections.locs) |bytes| try self.readTable(bytes, "locations", readLocation);162        if (sections.resources) |bytes| try self.readResources(bytes);163        var reader = Reader.init(sections.module orelse return error.MissingModule);164        try self.readOperation(&reader, null, 0, 0);165        try atEnd(reader);166    }167168    fn readStrings(self: *Data, bytes: []const u8) !void {169        var reader = Reader.init(bytes);170        const length = try self.count(&reader);171        for (0..length) |_| _ = try self.append("strings", try reader.readBytesWithLen());172        try atEnd(reader);173    }174175    fn readDialects(self: *Data, bytes: []const u8) !void {176        var reader = Reader.init(bytes);177        const length = try self.count(&reader);178        for (0..length) |_| {179            const name = try self.string(&reader);180            _ = try self.append("dialects", bytecode.DialectEntry{181                .name = name,182                .version = try reader.readULEBToU32(),183                .flags = try reader.readULEBToU32(),184            });185        }186        try atEnd(reader);187    }188189    fn readTable(190        self: *Data,191        bytes: []const u8,192        comptime field: []const u8,193        comptime parse: anytype,194    ) !void {195        var reader = Reader.init(bytes);196        const length = try self.count(&reader);197        for (0..length) |_| {198            const start = reader.offset;199            try parse(self, &reader);200            _ = try self.append(field, bytes[start..reader.offset]);201        }202        try atEnd(reader);203    }204205    fn string(self: *const Data, reader: *Reader) ![]const u8 {206        return self.strings.items[try reference(reader, self.strings.items.len)];207    }208209    fn readType(self: *Data, reader: *Reader) !void {210        switch (try tag(bytecode.TypeKind, reader)) {211            .builtin_scalar => {212                _ = try tag(bytecode.BuiltinScalarKind, reader);213                _ = try reader.readByte();214            },215            .dialect, .dialect_only => |kind| {216                _ = try reference(reader, self.dialects.items.len);217                if (kind == .dialect) _ = try self.string(reader);218                if (try boolean(reader)) _ = try self.string(reader);219            },220        }221    }222223    fn readAttribute(self: *Data, reader: *Reader) !void {224        switch (try tag(bytecode.AttrKind, reader)) {225            .integer => {226                _ = try reader.readSLEB();227                _ = try reader.readByte();228                _ = try boolean(reader);229            },230            .float_ => {231                _ = try reader.readU64();232                _ = try reader.readByte();233            },234            .bool_ => _ = try boolean(reader),235            .string => _ = try reader.readBytesWithLen(),236            .symbol_ref => {237                _ = try reader.readBytesWithLen();238                try self.readStringsList(reader);239            },240            .string_list => try self.readStringsList(reader),241            .type_list => _ = try self.ids(reader, self.types.items.len),242            .array => _ = try self.ids(reader, self.attributes.items.len),243            .dialect => {244                _ = try reference(reader, self.dialects.items.len);245                _ = try self.string(reader);246                _ = try reader.readBytesWithLen();247            },248        }249    }250251    fn readStringsList(self: *const Data, reader: *Reader) !void {252        const length = try self.count(reader);253        for (0..length) |_| _ = try reader.readBytesWithLen();254    }255256    fn readLocation(self: *Data, reader: *Reader) !void {257        const previous = self.locations.items.len;258        switch (try tag(bytecode.LocationKind, reader)) {259            .unknown => {},260            .file => {261                _ = try self.string(reader);262                _ = try reader.readULEBToU32();263                _ = try reader.readULEBToU32();264            },265            .file_range => {266                _ = try self.string(reader);267                const start = try reader.readULEB();268                _ = try reader.readULEBToU32();269                _ = try reader.readULEBToU32();270                if (start > try reader.readULEB()) return error.InvalidTable;271                _ = try reader.readULEBToU32();272                _ = try reader.readULEBToU32();273            },274            .name => {275                _ = try self.string(reader);276                if (try boolean(reader)) _ = try reference(reader, previous);277            },278            .fused => _ = try self.ids(reader, previous),279            .call_site => {280                _ = try reference(reader, previous);281                _ = try reference(reader, previous);282            },283        }284    }285286    fn readResources(self: *Data, bytes: []const u8) !void {287        var reader = Reader.init(bytes);288        const length = try self.count(&reader);289        for (0..length) |_| {290            var value: bytecode.Resource = undefined;291            inline for (@typeInfo(bytecode.Resource).@"struct".field_names) |field| {292                @field(value, field) = try reader.readBytesWithLen();293            }294            _ = try self.append("resources", value);295        }296        try atEnd(reader);297    }298299    fn ids(self: *const Data, reader: *Reader, bound: usize) !Ids {300        const length = try self.count(reader);301        const start = reader.offset;302        for (0..length) |_| _ = try reference(reader, bound);303        return .{ .count = length, .bytes = reader.bytes[start..reader.offset] };304    }305306    fn readOperation(307        self: *Data,308        reader: *Reader,309        parent: ?u32,310        blocks: u32,311        depth: u16,312    ) anyerror!void {313        if (depth > self.limits.depth) return error.ImageLimit;314        const start = reader.offset;315        const ordinal = try self.append("operations", @as(Operation, undefined));316        const name = try self.string(reader);317        const location = try reference(reader, self.locations.items.len);318        const types = try self.ids(reader, self.types.items.len);319        const operands = try self.ids(reader, self.values.items.len);320        const attributes = try self.readNamedAttributes(reader);321        const properties = if (try boolean(reader))322            try reference(reader, self.attributes.items.len)323        else324            null;325        const successors = try self.ids(reader, blocks);326        const regions = try self.count(reader);327        const results = try self.defineResults(types, ordinal, location);328        for (0..regions) |position| try self.readRegion(reader, ordinal, @intCast(position), depth);329        self.operations.items[ordinal] = .{330            .name = name,331            .location = location,332            .parent_block = parent,333            .results = results,334            .operands = operands,335            .attributes = attributes.bytes,336            .attribute_count = attributes.count,337            .properties = properties,338            .successors = successors,339            .region_count = regions,340            .encoded = reader.bytes[start..reader.offset],341        };342    }343344    fn readNamedAttributes(self: *Data, reader: *Reader) !Ids {345        const length = try self.count(reader);346        const start = reader.offset;347        var previous: ?[]const u8 = null;348        for (0..length) |_| {349            const name = try self.string(reader);350            if (previous) |prior| {351                if (!std.mem.lessThan(u8, prior, name)) return error.InvalidTable;352            }353            previous = name;354            _ = try reference(reader, self.attributes.items.len);355        }356        return .{ .count = length, .bytes = reader.bytes[start..reader.offset] };357    }358359    fn defineResults(self: *Data, types: Ids, operation: u32, location: u32) !Range {360        const range = Range{ .start = @intCast(self.values.items.len), .count = types.count };361        var reader = Reader.init(types.bytes);362        for (0..types.count) |position| {363            _ = try self.append("values", Value{364                .owner = .{ .operation = operation },365                .position = @intCast(position),366                .type = try reader.readULEBToU32(),367                .location = location,368            });369        }370        return range;371    }372373    fn readRegion(self: *Data, reader: *Reader, operation: u32, position: u32, depth: u16) !void {374        const length = try self.count(reader);375        const ordinal = try self.append("regions", Region{376            .operation = operation,377            .position = position,378            .block_count = length,379        });380        for (0..length) |index| try self.readBlock(reader, ordinal, @intCast(index), length, depth);381    }382383    fn readBlock(384        self: *Data,385        reader: *Reader,386        region: u32,387        position: u32,388        blocks: u32,389        depth: u16,390    ) !void {391        const ordinal = try self.append("blocks", @as(Block, undefined));392        const length = try self.count(reader);393        const range = Range{ .start = @intCast(self.values.items.len), .count = length };394        for (0..length) |index| {395            _ = try self.append("values", Value{396                .owner = .{ .block = ordinal },397                .position = @intCast(index),398                .type = try reference(reader, self.types.items.len),399                .location = try reference(reader, self.locations.items.len),400            });401        }402        const operations = try self.count(reader);403        self.blocks.items[ordinal] = .{404            .region = region,405            .position = position,406            .arguments = range,407            .operation_count = operations,408        };409        if (operations > 0 and depth == std.math.maxInt(u16)) return error.ImageLimit;410        for (0..operations) |_| try self.readOperation(reader, ordinal, blocks, depth + 1);411    }412};413414fn reference(reader: *Reader, bound: usize) !u32 {415    const ordinal = try reader.readULEBToU32();416    if (ordinal >= bound) return error.InvalidTable;417    return ordinal;418}419420fn boolean(reader: *Reader) !bool {421    return switch (try reader.readByte()) {422        0 => false,423        1 => true,424        else => error.InvalidTable,425    };426}427428fn tag(comptime T: type, reader: *Reader) !T {429    return std.enums.fromInt(T, try reader.readByte()) orelse error.InvalidTable;430}431432fn atEnd(reader: Reader) !void {433    if (reader.offset != reader.bytes.len) return error.InvalidTable;434}435436fn data(index: *Index) *Data {437    return @ptrCast(@alignCast(index));438}439440fn testBytes(allocator: std.mem.Allocator) ![]u8 {441    const ir = @import("../core/root.zig");442    var context = try ir.Context.init(allocator, ir.Context.Limits.testing);443    defer context.deinit(allocator);444    try context.allowUnregistered();445    var state = ir.Operation.State.init("test.function", .getFile("test", 1, 1));446    state.addRegion();447    const root = try context.createOperation(state);448    const block = try root.getRegion(0).?.addBlock();449    const typ = try context.getDialectTypeFromNameWithKey("test.word", "32");450    const argument = try block.addArgument(typ, .getFile("argument", 2, 3));451    var child_state = ir.Operation.State.init("test.add", .getFile("operation", 4, 5));452    child_state.addOperands(&.{ argument, argument });453    child_state.addTypes(&.{typ});454    child_state.addAttributes(&.{.{ .name = "answer", .value = try context.getI64Attr(42) }});455    const child = try context.createOperation(child_state);456    try block.addOperation(child);457    const resources = [_]bytecode.Resource{.{458        .namespace = "test",459        .name = "data",460        .type_id = "bytes",461        .data = "resource",462    }};463    return bytecode.encodeModuleWithResources(allocator, root, &resources);464}465466const test_limits = Limits{ .bytes = 65536, .entities = 1024, .depth = 32 };467468test "bytecode image exposes immutable entities after originating Context destruction" {469    const allocator = std.testing.allocator;470    const bytes = try testBytes(allocator);471    defer allocator.free(bytes);472    const index = try Index.create(allocator, bytes, test_limits);473    defer index.destroy();474    const view = index.view();475    try std.testing.expectEqual(2, view.operations.len);476    try std.testing.expectEqual(1, view.blocks.len);477    try std.testing.expectEqual(1, view.regions.len);478    try std.testing.expectEqual(2, view.values.len);479    try std.testing.expectEqualStrings("test.function", view.operations[0].name);480    try std.testing.expectEqualStrings("test.add", view.operations[1].name);481    try std.testing.expectEqual(0, view.operations[1].parent_block.?);482    try std.testing.expectEqual(0, view.operations[1].operands.at(0).?);483    try std.testing.expectEqual(0, view.operations[1].operands.at(1).?);484    try std.testing.expectEqual(1, view.operations[1].results.start);485    try std.testing.expectEqual(0, view.region(0, 0).?);486    try std.testing.expectEqual(0, view.block(0, 0).?);487    try std.testing.expectEqualStrings("resource", view.resources[0].data);488    var location = Reader.init(view.locations[view.values[0].location]);489    try std.testing.expectEqual(490        bytecode.LocationKind.file,491        try tag(bytecode.LocationKind, &location),492    );493    try std.testing.expectEqualStrings("argument", view.strings[try location.readULEBToU32()]);494    try std.testing.expectEqual(2, try location.readULEBToU32());495    try std.testing.expectEqual(3, try location.readULEBToU32());496    var attribute = Reader.init(view.attributes[0]);497    try std.testing.expectEqual(bytecode.AttrKind.integer, try tag(bytecode.AttrKind, &attribute));498    try std.testing.expectEqual(42, try attribute.readSLEB());499}500501fn allocationScenario(allocator: std.mem.Allocator, bytes: []const u8) !void {502    const index = try Index.create(allocator, bytes, test_limits);503    defer index.destroy();504    try std.testing.expectEqual(2, index.view().operations.len);505}506507test "bytecode image bounds malformed input and cleans every indexing allocation failure" {508    const allocator = std.testing.allocator;509    const bytes = try testBytes(allocator);510    defer allocator.free(bytes);511    try std.testing.checkAllAllocationFailures(allocator, allocationScenario, .{bytes});512    var limits = test_limits;513    limits.entities = 1;514    try std.testing.expectError(error.ImageLimit, Index.create(allocator, bytes, limits));515    limits = test_limits;516    limits.depth = 0;517    try std.testing.expectError(error.ImageLimit, Index.create(allocator, bytes, limits));518    try std.testing.expectError(519        error.InvalidSection,520        Index.create(allocator, bytes[0 .. bytes.len - 1], test_limits),521    );522}

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