tiny.syn.span.storage

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

1//! The buffer that receives the marks of each line: one region, allocated when the buffer is2//! created, freed when it is destroyed, and reused for every line in between. A program that marks3//! up text inside a loop that must not allocate needs all of that memory taken up front, and a4//! check that nothing is taken later. The buffer cannot know in advance how long a line will be, so5//! it needs a rule for a line that does not fit. Marks arrive one at a time, some from a routine6//! that starts partway through a line, so they need a common origin and a check that they stay in7//! order.8//!9//! `Storage` passes through three stages (*phase*): creation takes the allocator and allocates the10//! region, activation makes it ready for scanning, and destruction frees it, and every scanning11//! call checks that the storage is active. A line longer than the limit keeps none of its marked12//! byte ranges (*span*). The storage counts such a line, and the scan still runs so that its effect13//! on later lines stays exact. Spans must arrive in order, touching spans of one kind merge, and an14//! offset added to each appended span (*base*) lets a routine scan the tail of a line. A15//! compile-time record next to the type (*capacity claim*) states what it allocates, how that size16//! follows from the limit, and what a long line does, and the repository's allocation checks read17//! it.18//!19//! - *discarded line*: a line too long for its marks to be kept20//! - *text limit*: the longest line, in bytes, whose marks the storage keeps21//! - *span storage*: the caller's buffer that receives one line's marks22//! - *span capacity*: the number of marks the storage holds23const std = @import("std");24const alloc_phase = @import("alloc_phase");25const capacity_mod = @import("capacity.zig");26const model = @import("model.zig");2728/// A caller reads it from `Storage.status` to check sizes and to count dropped lines, as the README29/// example and the tests do. The value is a copy of the sizes and counters of span storage at one30/// moment.31pub const Status = struct {32    /// The phase of the storage when the copy was taken.33    phase: alloc_phase.capacity.Phase,34    /// The bytes of the span region, as `Capacity.storage_bytes` gives them.35    storage_bytes: usize,36    /// The text limit the storage was created with.37    max_text_bytes: usize,38    /// The number of spans the region holds.39    span_capacity: usize,40    /// The number of spans held for the current line. The count is zero after a discarded line.41    span_count: usize,42    /// The high-water mark of spans per line: the most spans any one line has held since the43    /// storage was created.44    high_water_spans: usize,45    /// The number of discarded lines since the storage was created. The count stops at the largest46    /// `u64`.47    discarded_line_count: u64,48};4950/// A caller creates one before scanning and passes it to every `highlight` and `highlightLine`51/// call. Span storage holds the spans of the most recent line in one region allocated at creation.52/// The storage lifecycle runs `init`, then `activate`, then any number of scans, then `deinit`. No53/// scan allocates once it is active. The storage offers no locking, so one storage serves one54/// thread at a time.55pub const Storage = struct {56    /// The phase: `initialization` after `init`, `steady` after `activate`, and `teardown` after57    /// `deinit`. Every scanning call asserts `steady`.58    phase: alloc_phase.capacity.Phase,59    /// The sizes derived from the caller's limits at `init`.60    capacity: capacity_mod.Capacity,61    /// The one region allocated at `init`, aligned for `Span`, and empty when the limit is zero.62    /// `deinit` frees it.63    bytes: []align(capacity_mod.storage_alignment) u8,64    /// The spans of the current line, kept in `bytes` read as an array of `Span`. The capacity65    /// equals the span capacity and never grows.66    spans: std.ArrayList(model.Span),67    /// The length in bytes of the current line, set by `prepare`.68    text_bytes: usize = 0,69    /// The base: the offset `append` adds to each span, reset to zero at the start of every line.70    base: usize = 0,71    /// The end of the last span appended for the current line. On a discarded line, `append` still72    /// moves it to the end of each span it drops. `append` checks that each new span starts at or73    /// after it.74    last_end: usize = 0,75    /// Whether the spans of the current line are kept, `.complete` until a line is discarded.76    materialization: model.Materialization = .complete,77    /// The high-water mark, starting at zero.78    high_water_spans: usize = 0,79    /// The number of discarded lines since creation, starting at zero and stopping at the largest80    /// `u64`.81    discarded_line_count: u64 = 0,8283    /// A caller names the limit type through `Storage`. The type is the same type as84    /// `capacity.Limits`.85    pub const Limits: type = capacity_mod.Limits;86    /// A caller names the size type through `Storage`. The type is the same type as87    /// `capacity.Capacity`.88    pub const Capacity: type = capacity_mod.Capacity;89    /// A caller of `prepare` names the error through `Storage`. The error set is the same error set90    /// as `model.Exhaustion`. `prepare` returns it for a line longer than the text limit.91    pub const Exhaustion: type = model.Exhaustion;92    /// A caller of `init` handles these errors. The error set holds the errors `init` can return:93    /// `OutOfMemory` from the allocator, or `CapacityOverflow` for a limit too large to size.94    pub const InitError = std.mem.Allocator.Error || capacity_mod.DeriveError;9596    /// The repository's allocation checks and tests read it to confirm what the storage allocates97    /// and when. The declaration is the capacity claim of span storage, fixed at compile time. The98    /// claim states that the storage holds ordered span values for the steady phase, and that the99    /// caller's text and scanner state lie outside it. The limit comes from the caller, and the100    /// retained bytes equal `max_text_bytes` times the size of one `Span` exactly. A line over the101    /// limit drops its spans while the scan still advances the state. Scanners write only into the102    /// region, and scanning crosses no operating-system boundary. `activate` seals the storage103    /// against allocation, and `deinit` ends its life. Each named obligation, such as104    /// `syn_span_capacity` or `syn_span_boundaries`, points to a test that witnesses one part of105    /// the claim.106    pub const claim: alloc_phase.capacity.Declaration = .{107        .source = .{108            .id = "syn.span_storage",109            .kind = .phase_static,110            .limit_source = .caller,111            .storage = .{112                .covered = &.{113                    .{114                        .id = "ordered_syntax_span_descriptors",115                        .lifetime = .steady,116                        .detail = "ordered syntax span descriptors",117                    },118                },119                .excluded = &.{120                    "caller-owned text bytes",121                    "caller-owned multiline scanner state",122                    "Chic terminal cells and render scratch",123                },124            },125            .capacity = .{126                .inputs = &.{127                    alloc_phase.capacity.bindInput(Limits, "max_text_bytes", "max_text_bytes"),128                },129                .type_selectors = &.{130                    alloc_phase.capacity.bindType(model.Span, "span"),131                },132                .nodes = &.{133                    .{ .input = 0 },134                    .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 0 } } },135                },136                .assertions = &.{.{137                    .scope = .closure_total,138                    .measure = .retained,139                    .relation = .exact,140                    .expression = 1,141                }},142            },143            .overload = .{144                .kind = .drop,145                .detail = "over-capacity lines drop span materialization while exact scanning advances state",146            },147            .risks = .{148                .transitive = .{149                    .status = .witnessed,150                    .detail = "all scanners append only into the activated span region",151                },152                .foreign = .{153                    .status = .excluded,154                    .detail = "syntax scanning crosses no operating-system or foreign boundary",155                },156            },157            .obligations = &.{158                .{ .key = "syn_span_capacity", .role = .capacity_model },159                .{ .key = "syn_span_acquisition", .role = .custom },160                .{ .key = "syn_span_oom", .role = .custom },161                .{ .key = "syn_span_boundaries", .role = .overload },162                .{ .key = "syn_span_reuse", .role = .custom },163                .{ .key = "syn_span_sealed_overload", .role = .overload },164                .{ .key = "syn_span_sealed_transitive_risk", .role = .transitive_risk },165                .{ .key = "syn_span_sealed_foreign_risk", .role = .foreign_risk },166                .{ .key = "syn_span_root", .role = .custom },167            },168        },169        .bindings = .{170            .owner = @This(),171            .seal = .{172                .family = alloc_phase.capacity.selector(@This().activate),173                .premise = .{174                    .class = .checked_semantic_fact,175                    .authority = .checker,176                },177            },178            .teardown = .{179                .family = alloc_phase.capacity.selector(@This().deinit),180                .premise = .{181                    .class = .checked_semantic_fact,182                    .authority = .checker,183                },184            },185        },186    };187188    /// A caller creates the storage once, before any scan, with the allocator that will later free189    /// it. The call derives the sizes from `limits` and allocates one region of `storage_bytes`190    /// from `allocator`, aligned for `Span`. The call allocates nothing when the limit is zero. The191    /// call returns the storage in the initialization phase, so `activate` must come before any192    /// scan. The call fails with `error.OutOfMemory` when the allocator fails, or193    /// `error.CapacityOverflow` when the size does not fit in a `usize`, and then holds nothing.194    /// The same allocator must later be passed to `deinit`.195    pub fn init(allocator: std.mem.Allocator, limits: Limits) InitError!Storage {196        const capacity = try Capacity.derive(limits);197        const bytes = if (capacity.storage_bytes == 0)198            @as([]align(capacity_mod.storage_alignment) u8, &.{})199        else200            try allocator.alignedAlloc(201                u8,202                .fromByteUnits(capacity_mod.storage_alignment),203                capacity.storage_bytes,204            );205        return .{206            .phase = .initialization,207            .capacity = capacity,208            .bytes = bytes,209            .spans = .initBuffer(typedSlice(bytes, capacity.span_capacity)),210        };211    }212213    /// A caller calls it once after `init` to make the storage ready for scanning. The call moves214    /// the storage from initialization to steady. The caller must call it exactly once, right after215    /// `init`. After activation the storage allocates nothing more.216    pub fn activate(self: *Storage) void {217        std.debug.assert(self.phase == .initialization);218        self.assertStorage();219        self.phase = .steady;220    }221222    /// The scan calls it at the start of each line, so a caller of `highlight` or `highlightLine`223    /// never calls it directly. The call clears the spans of the previous line and records the224    /// length of the next one. For a line longer than the text limit, the call marks the line225    /// discarded, adds one to the discarded count, and fails with226    /// `error.MaterializationCapacityExceeded`. A line within the limit is marked complete. The227    /// call requires the steady phase.228    pub fn prepare(self: *Storage, text_bytes: usize) Exhaustion!void {229        std.debug.assert(self.phase == .steady);230        self.spans.clearRetainingCapacity();231        self.text_bytes = text_bytes;232        self.base = 0;233        self.last_end = 0;234        if (text_bytes > self.capacity.limits.max_text_bytes) {235            self.materialization = .discarded;236            self.discarded_line_count +|= 1;237            self.assertStorage();238            return error.MaterializationCapacityExceeded;239        }240        self.materialization = .complete;241        self.assertStorage();242    }243244    /// The scan uses it to record spans for the tail of a line after a carried comment or string245    /// closes. The call sets the base for every later appended span and returns the previous base,246    /// so the caller can put it back. The base may not exceed the length of the line.247    pub fn setBase(self: *Storage, base: usize) usize {248        std.debug.assert(self.phase == .steady);249        std.debug.assert(base <= self.text_bytes);250        const previous = self.base;251        self.base = base;252        return previous;253    }254255    /// Scanners call it once for each token they mark. The call records one span, shifted by the256    /// base. The call ignores a span of zero length. Each span must start at or after the end of257    /// the previous one and end within the line, and the call asserts both. The call merges a span258    /// into the previous one when the two touch and share a kind. On a discarded line, the call259    /// tracks only where the span ends and stores nothing. The call never allocates, because a line260    /// within the limit cannot need more spans than the region holds.261    pub fn append(self: *Storage, span: model.Span) void {262        std.debug.assert(self.phase == .steady);263        if (span.start >= span.end) return;264        std.debug.assert(span.end <= self.text_bytes - self.base);265        const adjusted = model.Span{266            .start = self.base + span.start,267            .end = self.base + span.end,268            .kind = span.kind,269        };270        std.debug.assert(self.last_end <= adjusted.start);271        if (self.materialization == .discarded) {272            self.last_end = adjusted.end;273            return;274        }275        if (self.spans.items.len != 0) {276            const last = &self.spans.items[self.spans.items.len - 1];277            std.debug.assert(last.end == self.last_end);278            std.debug.assert(last.end <= adjusted.start);279            if (last.end == adjusted.start and last.kind == adjusted.kind) {280                last.end = adjusted.end;281                self.last_end = adjusted.end;282                return;283            }284        }285        std.debug.assert(self.spans.items.len < self.spans.capacity);286        self.spans.appendAssumeCapacity(adjusted);287        self.last_end = adjusted.end;288        self.high_water_spans = @max(self.high_water_spans, self.spans.items.len);289    }290291    /// A renderer reads the spans of the current line here after each scan. The call returns the292    /// spans of the most recent line, in order. The slice points into the storage, and the next293    /// scan overwrites it. The slice is empty after a discarded line. The call requires the steady294    /// phase.295    pub fn items(self: *const Storage) []const model.Span {296        std.debug.assert(self.phase == .steady);297        return self.spans.items;298    }299300    /// Tests use it to check that a scan marked a given token with a given kind. The call returns301    /// true when some span of the current line has kind `kind` and covers exactly the bytes `token`302    /// in `text`. `text` must be the line that was scanned. The function checks every span in turn,303    /// so its cost grows with the number of spans. Every call in the repository is in a test.304    pub fn contains(305        self: *const Storage,306        text: []const u8,307        kind: model.Kind,308        token: []const u8,309    ) bool {310        std.debug.assert(self.phase == .steady);311        for (self.spans.items) |span| {312            if (span.kind == kind and313                span.end <= text.len and314                std.mem.eql(u8, text[span.start..span.end], token)) return true;315        }316        return false;317    }318319    /// A caller reads it to check sizes and to count discarded lines. The call returns a `Status`320    /// copy of the sizes and counters. The call works in every phase and changes nothing.321    pub fn status(self: *const Storage) Status {322        return .{323            .phase = self.phase,324            .storage_bytes = self.capacity.storage_bytes,325            .max_text_bytes = self.capacity.limits.max_text_bytes,326            .span_capacity = self.capacity.span_capacity,327            .span_count = self.spans.items.len,328            .high_water_spans = self.high_water_spans,329            .discarded_line_count = self.discarded_line_count,330        };331    }332333    /// A caller releases the region when it has finished marking up text. The call frees the region334    /// with `allocator`, which must be the allocator given to `init`. The call moves the storage to335    /// teardown and empties its fields, so a second call trips an assertion.336    pub fn deinit(self: *Storage, allocator: std.mem.Allocator) void {337        std.debug.assert(self.phase != .teardown);338        self.assertStorage();339        self.phase = .teardown;340        allocator.free(self.bytes);341        self.bytes = &.{};342        self.spans = .empty;343        self.text_bytes = 0;344        self.base = 0;345        self.last_end = 0;346        self.materialization = .complete;347    }348349    fn assertStorage(self: *const Storage) void {350        std.debug.assert(self.bytes.len == self.capacity.storage_bytes);351        std.debug.assert(self.spans.capacity == self.capacity.span_capacity);352        std.debug.assert(self.spans.items.len <= self.spans.capacity);353        std.debug.assert(self.high_water_spans <= self.spans.capacity);354        std.debug.assert(self.base <= self.text_bytes);355        std.debug.assert(self.last_end <= self.text_bytes);356        switch (self.materialization) {357            .complete => {358                std.debug.assert(359                    self.text_bytes <= self.capacity.limits.max_text_bytes,360                );361                if (self.spans.items.len == 0) {362                    std.debug.assert(self.last_end == 0);363                } else {364                    std.debug.assert(365                        self.last_end ==366                            self.spans.items[self.spans.items.len - 1].end,367                    );368                }369            },370            .discarded => {371                std.debug.assert(372                    self.text_bytes > self.capacity.limits.max_text_bytes,373                );374                std.debug.assert(self.spans.items.len == 0);375            },376        }377    }378};379380fn typedSlice(381    bytes: []align(capacity_mod.storage_alignment) u8,382    count: usize,383) []model.Span {384    const region: []align(@alignOf(model.Span)) u8 = @alignCast(bytes);385    return std.mem.bytesAsSlice(model.Span, region)[0..count];386}387388fn checkInitFailures(allocator: std.mem.Allocator) !void {389    var storage = try Storage.init(allocator, .{ .max_text_bytes = 40 });390    storage.deinit(allocator);391}392393test "syntax span storage acquires one exact region" {394    comptime {395        @stardustClaim(396            @import("alloc_phase").capacity.witness(Storage, "syn_span_acquisition"),397            null,398            null,399            null,400            null,401            null,402            null,403        );404    }405406    var counting = std.testing.FailingAllocator.init(std.testing.allocator, .{});407    const limits = capacity_mod.Limits{ .max_text_bytes = 40 };408    const capacity = try capacity_mod.Capacity.derive(limits);409    var storage = try Storage.init(counting.allocator(), limits);410    defer storage.deinit(counting.allocator());411412    try std.testing.expectEqual(@as(usize, 1), counting.alloc_index);413    try std.testing.expectEqual(capacity.storage_bytes, counting.allocated_bytes);414    try std.testing.expectEqual(alloc_phase.capacity.Phase.initialization, storage.status().phase);415    storage.activate();416    try std.testing.expectEqual(@intFromPtr(storage.bytes.ptr), @intFromPtr(storage.spans.allocatedSlice().ptr));417}418419test "syntax span storage retries after every allocation failure" {420    comptime {421        @stardustClaim(422            @import("alloc_phase").capacity.witness(Storage, "syn_span_oom"),423            null,424            null,425            null,426            null,427            null,428            null,429        );430    }431432    try std.testing.checkAllAllocationFailures(std.testing.allocator, checkInitFailures, .{});433}434435comptime {436    alloc_phase.capacity.requireAllocatorRejectingOwnerShape(Storage);437}