lib/syn/src/span/capacity.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! The arithmetic computes, from one limit the caller chooses, how many bytes the storage for a
2 //! line's marks needs. A caller with a fixed memory budget wants that size before it allocates
3 //! anything, and wants a limit too large to size refused. The number of marks on a line has to be
4 //! bounded by something the caller controls.
5 //!
6 //! The bound is the line length: each kept mark covers at least one byte and no two overlap, so a
7 //! line of n bytes yields at most n marks, and the storage holds as many marks as the limit has
8 //! bytes (*span capacity*). The storage is one region of that many marks, aligned for one mark, so
9 //! its size in bytes is the limit times the size of one mark.
10 //!
11 //! - *text limit*: the longest line, in bytes, whose marks the storage keeps
12 //! - *span*: one marked byte range of a line and its role
13 //! - *span storage*: the caller's buffer that receives one line's marks
14 const std = @import("std");
15 const model = @import("model.zig");
16
17 /// The byte alignment of one `Span`. `Storage.init` requests its region at this alignment, so the
18 /// region can be read as an array of `Span` values.
19 pub const storage_alignment: usize = @alignOf(model.Span);
20
21 /// The one limit the caller chooses for span storage. A caller fills it in once to say how long a
22 /// line may be before its spans are dropped. `Capacity.derive` and `Storage.init` both take it.
23 pub const Limits = struct {
24 /// The text limit, in bytes. A longer line is still scanned but keeps no spans. The storage
25 /// holds exactly this many spans. Zero is allowed and gives storage with no room, so every
26 /// nonempty line is discarded. The README example uses 4096.
27 max_text_bytes: usize,
28 };
29
30 /// The one way sizing can fail. A caller of `Capacity.derive` or `Storage.init` handles it for a
31 /// limit too large to size. `CapacityOverflow` means the limit times the size of one span does not
32 /// fit in a `usize`. The largest accepted limit is the largest `usize` divided by the size of one
33 /// span.
34 pub const DeriveError = error{CapacityOverflow};
35
36 /// The sizes that follow from one `Limits` value, computed without allocating. A caller derives it
37 /// before allocating, to learn the exact bytes span storage will take, and the storage keeps its
38 /// own copy.
39 pub const Capacity = struct {
40 /// The limits the sizes were derived from, as given.
41 limits: Limits,
42 /// The span capacity: how many spans the storage holds, equal to `limits.max_text_bytes`. A
43 /// line within the limit never needs more, because each kept span covers at least one byte and
44 /// no two overlap.
45 span_capacity: usize,
46 /// The bytes those spans take: `span_capacity` times the size of one `Span`.
47 span_bytes: usize,
48 /// The bytes `Storage.init` allocates, in one region, equal to `span_bytes`. `Storage.status`
49 /// reports the same number, and the README example checks that the two agree. The byte count is
50 /// zero when the limit is zero, and then `Storage.init` allocates nothing.
51 storage_bytes: usize,
52
53 /// Returns the sizes for `limits`. A caller computes the storage size ahead of time, for
54 /// example to check a memory budget, and `Storage.init` calls it too. `Capacity.derive` fails
55 /// with `error.CapacityOverflow` when `max_text_bytes` times the size of one `Span` overflows a
56 /// `usize`. The call allocates nothing and reads nothing but its argument.
57 pub fn derive(limits: Limits) DeriveError!Capacity {
58 const span_bytes = std.math.mul(
59 usize,
60 limits.max_text_bytes,
61 @sizeOf(model.Span),
62 ) catch return error.CapacityOverflow;
63 return .{
64 .limits = limits,
65 .span_capacity = limits.max_text_bytes,
66 .span_bytes = span_bytes,
67 .storage_bytes = span_bytes,
68 };
69 }
70 };
71
72 fn modelCapacity(limits: Limits) DeriveError!Capacity {
73 const span_bytes = @as(u128, limits.max_text_bytes) * @sizeOf(model.Span);
74 if (span_bytes > std.math.maxInt(usize)) return error.CapacityOverflow;
75 return .{
76 .limits = limits,
77 .span_capacity = limits.max_text_bytes,
78 .span_bytes = @intCast(span_bytes),
79 .storage_bytes = @intCast(span_bytes),
80 };
81 }
82
83 test "syntax span capacity matches an independent byte model" {
84 comptime {
85 @stardustClaim(
86 @import("alloc_phase").capacity.witness(@import("./root.zig").Storage, "syn_span_capacity"),
87 null,
88 null,
89 null,
90 null,
91 null,
92 null,
93 );
94 }
95
96 const limits = Limits{ .max_text_bytes = 40 };
97 try std.testing.expectEqual(try modelCapacity(limits), try Capacity.derive(limits));
98 try std.testing.expectEqual(
99 @as(usize, 40 * @sizeOf(model.Span)),
100 (try Capacity.derive(limits)).storage_bytes,
101 );
102 try std.testing.expectEqual(
103 @as(usize, 0),
104 (try Capacity.derive(.{ .max_text_bytes = 0 })).storage_bytes,
105 );
106 }
107
108 test "syntax span capacity accepts its largest representable text limit" {
109 const max_text_bytes = std.math.maxInt(usize) / @sizeOf(model.Span);
110 const capacity = try Capacity.derive(.{ .max_text_bytes = max_text_bytes });
111 try std.testing.expectEqual(
112 max_text_bytes * @sizeOf(model.Span),
113 capacity.storage_bytes,
114 );
115 try std.testing.expectError(
116 error.CapacityOverflow,
117 Capacity.derive(.{ .max_text_bytes = max_text_bytes + 1 }),
118 );
119 }