tiny.smg.lines
Defined in tiny.smg.
API (4)
Actions
Public operations.
Types and contracts
Public types and contracts.
Source
Source: tools/smg/src/lines.zig
zig
const std = @import("std");const alloc_phase = @import("alloc_phase");pub const SourceLines = struct { pub const Limits = struct { source: []const u8, }; pub const Capacity = struct { starts: usize, bytes: usize, pub fn derive(limits: Limits) error{CapacityOverflow}!Capacity { const starts = try logicalLineCount(std.mem.count(u8, limits.source, "\n")); return .{ .starts = starts, .bytes = try sourceLineBytes(starts), }; } }; pub const InitError = std.mem.Allocator.Error || error{CapacityOverflow}; pub const claim: alloc_phase.capacity.Declaration = .{ .source = .{ .id = "smg.source_line_index", .kind = .phase_static, .limit_source = .caller, .storage = .{ .covered = &.{ .{ .id = "one_exact_byte_offset_per_logical_source_line_for_one_file", .lifetime = .steady, .detail = "one exact byte offset per logical source line for one file", }, }, .excluded = &.{ "borrowed source file bytes", "parser tree and AST scratch storage", "retained graph nodes edges names and metadata", }, }, .capacity = .{ .inputs = &.{ alloc_phase.capacity.bindInput(Limits, "source", "source"), }, .type_selectors = &.{ alloc_phase.capacity.bindType(usize, "usize"), }, .nodes = &.{ .{ .collection = .{ .byte_count = .{ .input = 0, .byte = '\n', } } }, .{ .constant = 1 }, .{ .add = .{ .left = 0, .right = 1 } }, .{ .scale = .{ .node = 2, .coefficient = .{ .size_of_concrete_type = 0 }, } }, }, .assertions = &.{.{ .scope = .closure_total, .measure = .retained, .relation = .exact, .expression = 3, }}, }, .overload = .{ .kind = .reject_before_seal, .detail = "checked line and byte counts plus one exact acquisition reject overflow or OOM before activation", }, .risks = .{ .transitive = .{ .status = .witnessed, .detail = "line fill and all steady lookup operations remain allocation-free under a sealed allocator", }, .foreign = .{ .status = .excluded, .detail = "the index is process-local caller-owned memory with no operating-system or callback edge", }, }, .obligations = &.{ .{ .key = "smg_source_line_index_capacity_capacity_model", .role = .capacity_model }, .{ .key = "smg_source_line_index_capacity_overload", .role = .overload }, .{ .key = "smg_source_line_index_oom", .role = .overload }, .{ .key = "smg_source_line_index_sealed_transitive_risk", .role = .transitive_risk }, .{ .key = "smg_source_line_index_sealed_foreign_risk", .role = .foreign_risk }, .{ .key = "smg_source_line_index_integration", .role = .custom }, }, }, .bindings = .{ .owner = @This(), .seal = .{ .family = alloc_phase.capacity.selector(@This().activate), .premise = .{ .class = .checked_semantic_fact, .authority = .checker, }, }, .teardown = .{ .family = alloc_phase.capacity.selector(@This().deinit), .premise = .{ .class = .checked_semantic_fact, .authority = .checker, }, }, }, }; phase: alloc_phase.capacity.Phase, capacity: Capacity, source: []const u8, starts: []usize, pub fn init(allocator: std.mem.Allocator, limits: Limits) InitError!SourceLines { const capacity = try Capacity.derive(limits); return .{ .phase = .initialization, .capacity = capacity, .source = limits.source, .starts = try allocator.alloc(usize, capacity.starts), }; } pub fn fill(self: *SourceLines) void { std.debug.assert(self.phase == .initialization); self.starts[0] = 0; var filled: usize = 1; for (self.source, 0..) |byte, index| { if (byte != '\n') continue; self.starts[filled] = index + 1; filled += 1; } std.debug.assert(filled == self.starts.len); } pub fn activate(self: *SourceLines) void { std.debug.assert(self.phase == .initialization); std.debug.assert(self.starts.len == self.capacity.starts); self.phase = .steady; } pub fn deinit(self: *SourceLines, allocator: std.mem.Allocator) void { std.debug.assert(self.phase != .teardown); self.phase = .teardown; allocator.free(self.starts); self.* = undefined; }};fn logicalLineCount(newline_count: usize) error{CapacityOverflow}!usize { return std.math.add(usize, newline_count, 1) catch error.CapacityOverflow;}fn sourceLineBytes(starts: usize) error{CapacityOverflow}!usize { return std.math.mul(usize, starts, @sizeOf(usize)) catch error.CapacityOverflow;}comptime { alloc_phase.capacity.requireAllocatorExactOwnerShape(SourceLines);}pub fn lineStartByte(source_lines: SourceLines, line: i64) usize { if (line <= 1) return 0; const index: usize = @intCast(line - 1); if (index >= source_lines.starts.len) return source_lines.source.len; return source_lines.starts[index];}pub fn lineEndByte(source_lines: SourceLines, line: i64) usize { if (line <= 0) return 0; const index: usize = @intCast(line - 1); if (index + 1 < source_lines.starts.len) return trimCarriage(source_lines.source, source_lines.starts[index + 1] - 1); return source_lines.source.len;}pub fn lineForByte(source_lines: SourceLines, byte_offset: usize) i64 { var low: usize = 0; var high = source_lines.starts.len; while (low < high) { const mid = low + (high - low) / 2; if (source_lines.starts[mid] <= byte_offset) { low = mid + 1; } else { high = mid; } } return @intCast(low);}fn trimCarriage(source: []const u8, index: usize) usize { if (index > 0 and source[index - 1] == '\r') return index - 1; return index;}test "source lines map line numbers to byte offsets" { const source = " first\r\nsecond\n third"; var source_lines = try SourceLines.init(std.testing.allocator, .{ .source = source }); defer source_lines.deinit(std.testing.allocator); source_lines.fill(); source_lines.activate(); try std.testing.expectEqual(@as(usize, 0), lineStartByte(source_lines, 1)); try std.testing.expectEqual(@as(usize, 7), lineEndByte(source_lines, 1)); try std.testing.expectEqual(@as(usize, 9), lineStartByte(source_lines, 2)); try std.testing.expectEqual(@as(i64, 1), lineForByte(source_lines, 8)); try std.testing.expectEqual(@as(i64, 2), lineForByte(source_lines, 9));}test "source line index capacity matches an independent newline model" { comptime { @stardustClaim( @import("alloc_phase").capacity.witness(SourceLines, "smg_source_line_index_capacity_capacity_model"), null, null, null, null, null, null, ); } comptime { @stardustClaim( @import("alloc_phase").capacity.witness(SourceLines, "smg_source_line_index_capacity_overload"), null, null, null, null, null, null, ); } const dense_source: [256]u8 = @splat('\n'); const sources = [_][]const u8{ "", "one", "one\n", "one\ntwo\nthree", &dense_source, }; const expected = [_]usize{ 1, 1, 2, 3, dense_source.len + 1 }; for (sources, expected) |source, starts| { const capacity = try SourceLines.Capacity.derive(.{ .source = source }); var source_lines = try SourceLines.init(std.testing.allocator, .{ .source = source }); defer source_lines.deinit(std.testing.allocator); try std.testing.expectEqual(starts, capacity.starts); try std.testing.expectEqual(starts * @sizeOf(usize), capacity.bytes); try std.testing.expectEqual(capacity.bytes, source_lines.starts.len * @sizeOf(usize)); try std.testing.expectEqual(try declaredSourceLineBytes(source), capacity.bytes); } try std.testing.expectEqual( std.math.maxInt(usize), try logicalLineCount(std.math.maxInt(usize) - 1), ); try std.testing.expectError( error.CapacityOverflow, logicalLineCount(std.math.maxInt(usize)), ); const starts_max = std.math.maxInt(usize) / @sizeOf(usize); try std.testing.expectEqual(starts_max * @sizeOf(usize), try sourceLineBytes(starts_max)); if (starts_max < std.math.maxInt(usize)) { try std.testing.expectError(error.CapacityOverflow, sourceLineBytes(starts_max + 1)); }}fn declaredSourceLineBytes(source: []const u8) !usize { const spec = SourceLines.claim.source.capacity; var values: [spec.nodes.len]usize = undefined; for (spec.nodes, 0..) |node, index| { values[index] = switch (node) { .constant => |value| std.math.cast(usize, value) orelse return error.CapacityOverflow, .add => |pair| std.math.add(usize, values[pair.left], values[pair.right]) catch return error.CapacityOverflow, .scale => |scale| scaled: { const selector = switch (scale.coefficient) { .size_of_concrete_type => |selector| selector, else => return error.InvalidCapacityDeclaration, }; const byte_size = std.math.cast( usize, spec.type_selectors[selector].byte_size, ) orelse return error.CapacityOverflow; break :scaled std.math.mul(usize, values[scale.node], byte_size) catch return error.CapacityOverflow; }, .collection => |projection| switch (projection) { .byte_count => |count| if (count.input == 0) std.mem.countScalar(u8, source, count.byte) else return error.InvalidCapacityDeclaration, else => return error.InvalidCapacityDeclaration, }, else => return error.InvalidCapacityDeclaration, }; } std.debug.assert(spec.assertions.len == 1); const assertion = spec.assertions[0]; std.debug.assert(assertion.scope == .closure_total); std.debug.assert(assertion.measure == .retained); std.debug.assert(assertion.relation == .exact); return values[assertion.expression];}fn checkSourceLineIndexInitAllocationFailures(allocator: std.mem.Allocator) !void { var source_lines = try SourceLines.init(allocator, .{ .source = "one\ntwo\nthree" }); source_lines.deinit(allocator);}test "source line index initialization cleans allocation failure and retries" { comptime { @stardustClaim( @import("alloc_phase").capacity.witness(SourceLines, "smg_source_line_index_oom"), null, null, null, null, null, null, ); } try std.testing.checkAllAllocationFailures( std.testing.allocator, checkSourceLineIndexInitAllocationFailures, .{}, ); var source_lines = try SourceLines.init(std.testing.allocator, .{ .source = "one\ntwo" }); defer source_lines.deinit(std.testing.allocator); source_lines.fill(); source_lines.activate(); try std.testing.expectEqual(alloc_phase.capacity.Phase.steady, source_lines.phase);}test "source line index fills and serves byte mappings while sealed" { comptime { @stardustClaim( @import("alloc_phase").capacity.witness(SourceLines, "smg_source_line_index_sealed_transitive_risk"), null, null, null, null, null, null, ); } comptime { @stardustClaim( @import("alloc_phase").capacity.witness(SourceLines, "smg_source_line_index_sealed_foreign_risk"), null, null, null, null, null, null, ); } const source = "first\nsecond\nthird"; var phase_allocator = try alloc_phase.SealedPhaseAllocator.init(std.testing.allocator); var source_lines = try SourceLines.init( phase_allocator.initializationAllocator(), .{ .source = source }, ); defer { if (phase_allocator.phase() == .initialization) phase_allocator.abortInitialization(); if (phase_allocator.phase() == .steady) phase_allocator.beginTeardown(); source_lines.deinit(phase_allocator.teardownAllocator()); phase_allocator.deinit(); } const starts_pointer = source_lines.starts.ptr; phase_allocator.seal(); source_lines.fill(); source_lines.activate(); try std.testing.expectEqual(@as(usize, 6), lineStartByte(source_lines, 2)); try std.testing.expectEqual(@as(usize, 12), lineEndByte(source_lines, 2)); try std.testing.expectEqual(@as(i64, 3), lineForByte(source_lines, 14)); try std.testing.expectEqual(starts_pointer, source_lines.starts.ptr); try std.testing.expectEqual(@as(u64, 0), phase_allocator.violations().total());}Source: tools/smg/src/root.zig:24
zig
pub const lines = @import("lines.zig");Audit
| Definitions | 4 |
|---|---|
| Public names | 4 |
| Members | 0 |
| Version | 26.7.0 |
| Revision | daab053ee433 |