tiny.syn.span.capacity

1//! The arithmetic computes, from one limit the caller chooses, how many bytes the storage for a2//! line's marks needs. A caller with a fixed memory budget wants that size before it allocates3//! anything, and wants a limit too large to size refused. The number of marks on a line has to be4//! 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 a7//! line of n bytes yields at most n marks, and the storage holds as many marks as the limit has8//! bytes (*span capacity*). The storage is one region of that many marks, aligned for one mark, so9//! 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 keeps12//! - *span*: one marked byte range of a line and its role13//! - *span storage*: the caller's buffer that receives one line's marks14const std = @import("std");15const model = @import("model.zig");1617/// The byte alignment of one `Span`. `Storage.init` requests its region at this alignment, so the18/// region can be read as an array of `Span` values.19pub const storage_alignment: usize = @alignOf(model.Span);2021/// The one limit the caller chooses for span storage. A caller fills it in once to say how long a22/// line may be before its spans are dropped. `Capacity.derive` and `Storage.init` both take it.23pub const Limits = struct {24    /// The text limit, in bytes. A longer line is still scanned but keeps no spans. The storage25    /// holds exactly this many spans. Zero is allowed and gives storage with no room, so every26    /// nonempty line is discarded. The README example uses 4096.27    max_text_bytes: usize,28};2930/// The one way sizing can fail. A caller of `Capacity.derive` or `Storage.init` handles it for a31/// limit too large to size. `CapacityOverflow` means the limit times the size of one span does not32/// fit in a `usize`. The largest accepted limit is the largest `usize` divided by the size of one33/// span.34pub const DeriveError = error{CapacityOverflow};3536/// The sizes that follow from one `Limits` value, computed without allocating. A caller derives it37/// before allocating, to learn the exact bytes span storage will take, and the storage keeps its38/// own copy.39pub 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`. A43    /// line within the limit never needs more, because each kept span covers at least one byte and44    /// 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 is50    /// zero when the limit is zero, and then `Storage.init` allocates nothing.51    storage_bytes: usize,5253    /// Returns the sizes for `limits`. A caller computes the storage size ahead of time, for54    /// example to check a memory budget, and `Storage.init` calls it too. `Capacity.derive` fails55    /// with `error.CapacityOverflow` when `max_text_bytes` times the size of one `Span` overflows a56    /// `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};7172fn 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}8283test "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    }9596    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}107108test "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}

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