lib/syn/src/span/storage.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! The buffer that receives the marks of each line: one region, allocated when the buffer is
2 //! created, freed when it is destroyed, and reused for every line in between. A program that marks
3 //! up text inside a loop that must not allocate needs all of that memory taken up front, and a
4 //! check that nothing is taken later. The buffer cannot know in advance how long a line will be, so
5 //! it needs a rule for a line that does not fit. Marks arrive one at a time, some from a routine
6 //! that starts partway through a line, so they need a common origin and a check that they stay in
7 //! order.
8 //!
9 //! `Storage` passes through three stages (*phase*): creation takes the allocator and allocates the
10 //! region, activation makes it ready for scanning, and destruction frees it, and every scanning
11 //! call checks that the storage is active. A line longer than the limit keeps none of its marked
12 //! byte ranges (*span*). The storage counts such a line, and the scan still runs so that its effect
13 //! on later lines stays exact. Spans must arrive in order, touching spans of one kind merge, and an
14 //! offset added to each appended span (*base*) lets a routine scan the tail of a line. A
15 //! compile-time record next to the type (*capacity claim*) states what it allocates, how that size
16 //! follows from the limit, and what a long line does, and the repository's allocation checks read
17 //! it.
18 //!
19 //! - *discarded line*: a line too long for its marks to be kept
20 //! - *text limit*: the longest line, in bytes, whose marks the storage keeps
21 //! - *span storage*: the caller's buffer that receives one line's marks
22 //! - *span capacity*: the number of marks the storage holds
23 const std = @import("std");
24 const alloc_phase = @import("alloc_phase");
25 const capacity_mod = @import("capacity.zig");
26 const model = @import("model.zig");
27
28 /// A caller reads it from `Storage.status` to check sizes and to count dropped lines, as the README
29 /// example and the tests do. The value is a copy of the sizes and counters of span storage at one
30 /// moment.
31 pub 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 the
43 /// storage was created.
44 high_water_spans: usize,
45 /// The number of discarded lines since the storage was created. The count stops at the largest
46 /// `u64`.
47 discarded_line_count: u64,
48 };
49
50 /// 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`. No
53 /// scan allocates once it is active. The storage offers no locking, so one storage serves one
54 /// thread at a time.
55 pub const Storage = struct {
56 /// The phase: `initialization` after `init`, `steady` after `activate`, and `teardown` after
57 /// `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 capacity
65 /// 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` still
72 /// moves it to the end of each span it drops. `append` checks that each new span starts at or
73 /// 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 largest
80 /// `u64`.
81 discarded_line_count: u64 = 0,
82
83 /// A caller names the limit type through `Storage`. The type is the same type as
84 /// `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 as
87 /// `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 set
90 /// 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;
95
96 /// The repository's allocation checks and tests read it to confirm what the storage allocates
97 /// and when. The declaration is the capacity claim of span storage, fixed at compile time. The
98 /// claim states that the storage holds ordered span values for the steady phase, and that the
99 /// caller's text and scanner state lie outside it. The limit comes from the caller, and the
100 /// retained bytes equal `max_text_bytes` times the size of one `Span` exactly. A line over the
101 /// limit drops its spans while the scan still advances the state. Scanners write only into the
102 /// region, and scanning crosses no operating-system boundary. `activate` seals the storage
103 /// against allocation, and `deinit` ends its life. Each named obligation, such as
104 /// `syn_span_capacity` or `syn_span_boundaries`, points to a test that witnesses one part of
105 /// 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 };
187
188 /// A caller creates the storage once, before any scan, with the allocator that will later free
189 /// 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. The
191 /// call returns the storage in the initialization phase, so `activate` must come before any
192 /// scan. The call fails with `error.OutOfMemory` when the allocator fails, or
193 /// `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 else
200 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 }
212
213 /// A caller calls it once after `init` to make the storage ready for scanning. The call moves
214 /// the storage from initialization to steady. The caller must call it exactly once, right after
215 /// `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 }
221
222 /// 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 the
224 /// length of the next one. For a line longer than the text limit, the call marks the line
225 /// discarded, adds one to the discarded count, and fails with
226 /// `error.MaterializationCapacityExceeded`. A line within the limit is marked complete. The
227 /// 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 }
243
244 /// The scan uses it to record spans for the tail of a line after a carried comment or string
245 /// 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 }
254
255 /// Scanners call it once for each token they mark. The call records one span, shifted by the
256 /// base. The call ignores a span of zero length. Each span must start at or after the end of
257 /// the previous one and end within the line, and the call asserts both. The call merges a span
258 /// into the previous one when the two touch and share a kind. On a discarded line, the call
259 /// tracks only where the span ends and stores nothing. The call never allocates, because a line
260 /// 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 }
290
291 /// A renderer reads the spans of the current line here after each scan. The call returns the
292 /// spans of the most recent line, in order. The slice points into the storage, and the next
293 /// scan overwrites it. The slice is empty after a discarded line. The call requires the steady
294 /// phase.
295 pub fn items(self: *const Storage) []const model.Span {
296 std.debug.assert(self.phase == .steady);
297 return self.spans.items;
298 }
299
300 /// Tests use it to check that a scan marked a given token with a given kind. The call returns
301 /// 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 and
313 span.end <= text.len and
314 std.mem.eql(u8, text[span.start..span.end], token)) return true;
315 }
316 return false;
317 }
318
319 /// 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 }
332
333 /// A caller releases the region when it has finished marking up text. The call frees the region
334 /// with `allocator`, which must be the allocator given to `init`. The call moves the storage to
335 /// 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 }
348
349 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 };
379
380 fn 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 }
387
388 fn checkInitFailures(allocator: std.mem.Allocator) !void {
389 var storage = try Storage.init(allocator, .{ .max_text_bytes = 40 });
390 storage.deinit(allocator);
391 }
392
393 test "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 }
405
406 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());
411
412 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 }
418
419 test "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 }
431
432 try std.testing.checkAllAllocationFailures(std.testing.allocator, checkInitFailures, .{});
433 }
434
435 comptime {
436 alloc_phase.capacity.requireAllocatorRejectingOwnerShape(Storage);
437 }