tiny.sys.font

1/// Holds one enumeration's results and the directories still queued for the2/// walk over a byte region the caller supplies, so a caller reads the whole3/// enumeration back out of it. That byte region holds the entry records, then4/// the directory records, then the shared path arena. Each admission tests the5/// entry count, the directory count, and the remaining path bytes before it6/// writes anything, which leaves everything accepted so far untouched when one7/// of the three refuses, so a caller may read a refusal as the answer being cut8/// short at `entryCount`. The order of use runs `init`, then `activate`, then9/// admissions, then `deinit`, which hands the caller's storage back.10pub const Catalog = struct {11    phase: capacity.Phase,12    capacity: CatalogCapacity,13    storage: Storage,14    entry_count: u32,15    directory_count: u32,16    directory_head: u32,17    path_used: u32,1819    pub const storage_alignment: usize = 8;20    pub const Storage: type = []align(storage_alignment) u8;21    pub const Limits: type = CatalogLimits;22    pub const Capacity: type = CatalogCapacity;23    pub const Exhaustion: type = CatalogExhaustion;24    pub const InitError: type = CatalogInitError;2526    pub const work_limits: capacity.WorkLimits = .{27        .transition_steps_max = 1,28        .cleanup_steps_per_call_max = 0,29        .cleanup_calls_at_capacity_max = 0,30    };3132    pub const claim: capacity.Declaration = .{33        .source = .{34            .id = "sys.font_walk",35            .kind = .phase_static,36            .limit_source = .caller,37            .storage = .{38                .covered = &.{39                    .{40                        .id = "caller_font_entry_records",41                        .lifetime = .transferred,42                        .detail = "caller entry records for accepted font files",43                    },44                    .{45                        .id = "caller_font_directory_records",46                        .lifetime = .transferred,47                        .detail = "caller directory records for the depth bounded frontier",48                    },49                    .{50                        .id = "caller_font_path_bytes",51                        .lifetime = .transferred,52                        .detail = "caller path arena shared by entry and directory records",53                    },54                },55                .excluded = &.{56                    "caller-owned root set, walk options, and enumeration statistics",57                    "directory handles, iterator read buffers, and kernel path state",58                    "process environment strings borrowed while default roots resolve",59                },60            },61            .capacity = .{62                .inputs = &.{63                    capacity.bindInput(CatalogLimits, "entries", "entries"),64                    capacity.bindInput(CatalogLimits, "directories", "directories"),65                    capacity.bindInput(CatalogLimits, "path_bytes", "path_bytes"),66                },67                .type_selectors = &.{68                    capacity.bindType(Entry, "entry"),69                    capacity.bindType(Directory, "directory"),70                },71                .nodes = &.{72                    .{ .input = 0 },73                    .{ .input = 1 },74                    .{ .input = 2 },75                    .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 0 } } },76                    .{ .scale = .{ .node = 1, .coefficient = .{ .size_of_concrete_type = 1 } } },77                    .{ .add = .{ .left = 3, .right = 4 } },78                    .{ .add = .{ .left = 5, .right = 2 } },79                },80                .assertions = &.{.{81                    .scope = .closure_total,82                    .measure = .retained,83                    .relation = .exact,84                    .expression = 6,85                }},86            },87            .overload = .{88                .kind = .reject_before_mutation,89                .detail = "an admission past entry, directory, or path capacity writes nothing",90            },91            .risks = .{92                .transitive = .{93                    .status = .open,94                    .detail = "the walk enters directory iteration owned by the standard library",95                },96                .foreign = .{97                    .status = .open,98                    .detail = "directory handles and iterator read buffers belong to the kernel",99                },100            },101            .work = .{ .equation = "transition_steps <= 1 and cleanup_steps == 0" },102            .obligations = &.{103                .{ .key = "sys_font_walk_capacity_model", .role = .capacity_model },104                .{ .key = "sys_font_walk_overload", .role = .overload },105                .{ .key = "sys_font_walk_work_bound", .role = .work_bound },106            },107        },108        .bindings = .{109            .owner = @This(),110            .seal = .{111                .family = capacity.selector(@This().activate),112                .premise = .{113                    .class = .checked_semantic_fact,114                    .authority = .checker,115                },116            },117            .teardown = .{118                .family = capacity.selector(@This().deinit),119                .premise = .{120                    .class = .checked_semantic_fact,121                    .authority = .checker,122                },123            },124        },125    };126127    pub fn init(storage: Storage, limits: CatalogLimits) CatalogInitError!Catalog {128        const derived = try CatalogCapacity.derive(limits);129        if (storage.len < derived.storage_bytes) return error.StorageTooShort;130        return .{131            .phase = .initialization,132            .capacity = derived,133            .storage = storage,134            .entry_count = 0,135            .directory_count = 0,136            .directory_head = 0,137            .path_used = 0,138        };139    }140141    pub fn activate(self: *Catalog) void {142        std.debug.assert(self.phase == .initialization);143        self.phase = .steady;144    }145146    /// Resets the catalog so a caller reuses one region for a second147    /// enumeration. The call sets the entry count, the directory count, the148    /// queue position, and the used path bytes back to zero, while the caller's149    /// storage stays with the catalog.150    pub fn reset(self: *Catalog) void {151        std.debug.assert(self.phase == .steady);152        self.entry_count = 0;153        self.directory_count = 0;154        self.directory_head = 0;155        self.path_used = 0;156    }157158    /// Appends one accepted font file during the walk, taking its path, its159    /// size, its format, and the index of the root it came from. The entry160    /// count and the remaining path bytes are both checked before anything is161    /// written, so a refusal changes no record and no byte.162    pub fn appendEntry(163        self: *Catalog,164        path: []const u8,165        size_bytes: u64,166        format: Format,167        root: u8,168    ) CatalogExhaustion!void {169        std.debug.assert(self.phase == .steady);170        std.debug.assert(path.len != 0);171        if (self.entry_count == self.capacity.entries) return error.FontEntriesExhausted;172        const offset = try self.reservePath(path);173        self.entryStore()[self.entry_count] = .{174            .size_bytes = size_bytes,175            .path_offset = offset,176            .path_len = @intCast(path.len),177            .format = format,178            .root = root,179        };180        self.entry_count += 1;181    }182183    /// Puts one root directory on the queue and hands back the index of its184    /// record. The walk calls it once per font root before it starts185    /// descending. The record's parent index is its own index, which terminates186    /// the ancestor climb of the walk's cycle guard.187    pub fn appendRoot(188        self: *Catalog,189        path: []const u8,190        inode: u64,191        root: u8,192    ) CatalogExhaustion!u32 {193        const index = try self.appendDirectory(path, inode, self.directory_count, 0, root);194        std.debug.assert(self.directoryStore()[index].parent == index);195        return index;196    }197198    /// Puts one subdirectory on the queue, once the walk decides to descend199    /// into it, and hands back the index of its record. The record keeps the200    /// inode, the index of the record it was reached from, how far beneath the201    /// root it sits, and which root that is. The directory count and the202    /// remaining path bytes are both checked before anything is written, so a203    /// refusal changes no record and no byte.204    pub fn appendDirectory(205        self: *Catalog,206        path: []const u8,207        inode: u64,208        parent: u32,209        depth: u8,210        root: u8,211    ) CatalogExhaustion!u32 {212        std.debug.assert(self.phase == .steady);213        std.debug.assert(path.len != 0);214        if (self.directory_count == self.capacity.directories) {215            return error.FontDirectoriesExhausted;216        }217        const offset = try self.reservePath(path);218        std.debug.assert(self.directory_count < self.capacity.directories);219        const index = self.directory_count;220        std.debug.assert(parent <= index);221        self.directoryStore()[index] = .{222            .inode = inode,223            .path_offset = offset,224            .parent = parent,225            .path_len = @intCast(path.len),226            .depth = depth,227            .root = root,228        };229        self.directory_count += 1;230        return index;231    }232233    /// Drains the frontier one directory per turn for the walk, taking the next234    /// directory off the queue and returning its index. The call returns null235    /// once the frontier is drained. Records come back in the order they went236    /// in, which makes the walk breadth-first.237    pub fn takeDirectory(self: *Catalog) ?u32 {238        std.debug.assert(self.phase == .steady);239        std.debug.assert(self.directory_head <= self.directory_count);240        if (self.directory_head == self.directory_count) return null;241        const index = self.directory_head;242        self.directory_head += 1;243        return index;244    }245246    pub fn directoryAt(self: *const Catalog, index: u32) Directory {247        std.debug.assert(self.phase == .steady);248        std.debug.assert(index < self.directory_count);249        return self.directoryStore()[index];250    }251252    pub fn entryCount(self: *const Catalog) u32 {253        return self.entry_count;254    }255256    pub fn directoryCount(self: *const Catalog) u32 {257        return self.directory_count;258    }259260    pub fn pathBytesUsed(self: *const Catalog) u32 {261        return self.path_used;262    }263264    pub fn entries(self: *const Catalog) []const Entry {265        return self.entryStore()[0..self.entry_count];266    }267268    pub fn entryPath(self: *const Catalog, entry: Entry) []const u8 {269        const start = entry.path_offset;270        std.debug.assert(start + entry.path_len <= self.path_used);271        return self.pathStore()[start..][0..entry.path_len];272    }273274    pub fn directoryPath(self: *const Catalog, directory: Directory) []const u8 {275        const start = directory.path_offset;276        std.debug.assert(start + directory.path_len <= self.path_used);277        return self.pathStore()[start..][0..directory.path_len];278    }279280    pub fn deinit(self: *Catalog) Storage {281        std.debug.assert(self.phase == .steady);282        self.phase = .teardown;283        const storage = self.storage;284        self.* = undefined;285        return storage;286    }287288    fn reservePath(self: *Catalog, path: []const u8) CatalogExhaustion!u32 {289        std.debug.assert(path.len != 0);290        std.debug.assert(self.path_used <= self.capacity.path_bytes);291        if (path.len > path_bytes_limit) return error.FontPathBytesExhausted;292        const remaining = self.capacity.path_bytes - self.path_used;293        if (path.len > remaining) return error.FontPathBytesExhausted;294        const offset = self.path_used;295        @memcpy(self.pathStore()[offset..][0..path.len], path);296        self.path_used = offset + @as(u32, @intCast(path.len));297        std.debug.assert(self.path_used <= self.capacity.path_bytes);298        return offset;299    }300301    fn entryStore(self: *const Catalog) []Entry {302        std.debug.assert(self.storage.len >= self.capacity.storage_bytes);303        const bytes = self.storage[0 .. self.capacity.entries * @sizeOf(Entry)];304        return @alignCast(std.mem.bytesAsSlice(Entry, bytes));305    }306307    fn directoryStore(self: *const Catalog) []Directory {308        std.debug.assert(self.storage.len >= self.capacity.storage_bytes);309        const start = self.capacity.entries * @sizeOf(Entry);310        std.debug.assert(start % storage_alignment == 0);311        const count = self.capacity.directories * @sizeOf(Directory);312        const bytes = self.storage[start..][0..count];313        return @alignCast(std.mem.bytesAsSlice(Directory, bytes));314    }315316    fn pathStore(self: *const Catalog) []u8 {317        std.debug.assert(self.storage.len >= self.capacity.storage_bytes);318        const start = self.capacity.entries * @sizeOf(Entry) +319            self.capacity.directories * @sizeOf(Directory);320        return self.storage[start..][0..self.capacity.path_bytes];321    }322};

1/// Records one visited directory so the walk can descend from it and detect a2/// cycle. The record stores where its path sits in the path arena, its inode,3/// the record it was reached from, how deep it sits, and which root it came4/// from. The walk's cycle guard compares the inode against every ancestor's5/// inode by following the parent index, and a root's parent index is its own6/// index, which ends that climb.7pub const Directory = extern struct {8    inode: u64,9    path_offset: u32,10    parent: u32,11    path_len: u16,12    depth: u8,13    root: u8,14};

1/// Records one accepted font file so a caller walking admitted entries can get2/// each font's path and size. The record keeps where its path sits in the path3/// arena and how long it is, the file size, the format, and which root it came4/// from. The size and the format come from one stat call, so the file itself5/// stays closed, and `Catalog.entryPath` turns the offset and length back into6/// the path bytes.7pub const Entry = extern struct {8    size_bytes: u64,9    path_offset: u32,10    path_len: u16,11    format: Format,12    root: u8,13};

1/// Identifies which container a font file uses, among TrueType, OpenType, the2/// two collection containers, and Type 1, so a caller tells a TrueType file3/// from a Type 1 file. The answer comes from the text after the last dot in the4/// name, and no file gets opened to reach it.5pub const Format = enum(u8) {6    truetype,7    opentype,8    truetype_collection,9    opentype_collection,10    type1,1112    /// Decides whether a file is a font at all by reading the text after a13    /// name's last dot and matching it against the known extensions, upper and14    /// lower case alike. The matched extensions are ttf, otf, ttc, otc, and15    /// pfb, while a name with no dot, an empty extension, or an extension16    /// longer than `extension_bytes_max` returns null.17    pub fn fromName(name: []const u8) ?Format {18        const dot = std.mem.lastIndexOfScalar(u8, name, '.') orelse return null;19        const extension = name[dot + 1 ..];20        if (extension.len == 0 or extension.len > extension_bytes_max) return null;21        var lowered: [extension_bytes_max]u8 = undefined;22        for (extension, 0..) |byte, index| lowered[index] = std.ascii.toLower(byte);23        const folded = lowered[0..extension.len];24        if (std.mem.eql(u8, folded, "ttf")) return .truetype;25        if (std.mem.eql(u8, folded, "otf")) return .opentype;26        if (std.mem.eql(u8, folded, "ttc")) return .truetype_collection;27        if (std.mem.eql(u8, folded, "otc")) return .opentype_collection;28        if (std.mem.eql(u8, folded, "pfb")) return .type1;29        return null;30    }31};

1/// Holds the three environment values that shape the Linux list: `HOME`,2/// `XDG_DATA_HOME`, and `XDG_DATA_DIRS`. A program fills it from the running3/// process with `hostEnvironment`, while a test fills it with literals so the4/// search order can be checked on any machine without touching the process5/// environment.6pub const Environment = struct {7    home: ?[]const u8 = null,8    xdg_data_home: ?[]const u8 = null,9    xdg_data_dirs: ?[]const u8 = null,10};

1/// Keeps a list of absolute font directories in inline storage, ordered as the2/// search visits them, which a caller holds across a resolve and a walk with no3/// allocation anywhere in between. Once either bound is reached the set refuses4/// the next directory and adds one to `dropped`, which leaves a caller whose5/// machine lists more directories than the bound with the prefix that fits and6/// a count of what fell away.7pub const RootSet = struct {8    bytes: [root_bytes_max]u8 = undefined,9    spans: [roots_max]Span = @splat(.{ .offset = 0, .len = 0 }),10    count: u8 = 0,11    dropped: u16 = 0,12    used: u16 = 0,1314    pub fn clear(self: *RootSet) void {15        self.count = 0;16        self.dropped = 0;17        self.used = 0;18    }1920    pub fn path(self: *const RootSet, index: u8) []const u8 {21        std.debug.assert(index < self.count);22        const span = self.spans[index];23        std.debug.assert(span.len != 0);24        std.debug.assert(span.offset + span.len <= self.used);25        return self.bytes[span.offset..][0..span.len];26    }2728    /// Adds `directory` to the end of the list, when the path is absolute, the29    /// list lacks it, and the bytes fit, and reports whether it went in. A30    /// caller uses it to add a root of its own to the platform's list. Trailing31    /// separators are trimmed before the comparison and the copy, while a32    /// relative, empty, or duplicate path returns false and leaves `dropped`33    /// alone so `dropped` counts capacity refusals only.34    pub fn append(self: *RootSet, directory: []const u8) bool {35        const trimmed = sys.path.trimTrailingSeparators(directory);36        if (trimmed.len == 0 or !sys.path.isAbsolute(trimmed)) return false;37        for (0..self.count) |index| {38            if (std.mem.eql(u8, self.path(@intCast(index)), trimmed)) return false;39        }40        if (self.count == roots_max or trimmed.len > root_bytes_max - self.used) {41            self.dropped +|= 1;42            return false;43        }44        const offset = self.used;45        @memcpy(self.bytes[offset..][0..trimmed.len], trimmed);46        self.spans[self.count] = .{ .offset = offset, .len = @intCast(trimmed.len) };47        self.count += 1;48        self.used = offset + @as(u16, @intCast(trimmed.len));49        std.debug.assert(self.count <= roots_max);50        std.debug.assert(self.used <= root_bytes_max);51        return true;52    }5354    /// Joins `parent` and `child` with a single separator and adds the result.55    /// Platform lists build most of their roots this way, joining a directory56    /// from the environment to a fixed suffix. A join longer than the path57    /// buffer counts a drop and returns false.58    pub fn appendJoined(self: *RootSet, parent: []const u8, child: []const u8) bool {59        var buffer: [std.Io.Dir.max_path_bytes]u8 = undefined;60        const trimmed = sys.path.trimTrailingSeparators(parent);61        const joined = std.fmt.bufPrint(&buffer, "{s}/{s}", .{ trimmed, child }) catch {62            self.dropped +|= 1;63            return false;64        };65        return self.append(joined);66    }67};

1/// The outcome of resolving the platform's default roots, either the count of2/// roots written or the reason none were, so a caller can tell an empty3/// platform from an empty search.4pub const Support = union(enum) {5    supported: u8,6    unsupported: Unsupported,7};

1/// The reason a platform reports no font roots, read by a caller that got none.2pub const Unsupported = enum {3    /// `lib/sys` carries no list of font directories for this operating system.4    platform,5};

1/// The limits a caller sets on one walk.2pub const Options = struct {3    /// Sets how many levels beneath a root the walk goes, which a caller lowers4    /// to keep a walk shallow and cheap. The default is six, and zero reads the5    /// roots alone.6    depth_max: u8 = 6,7};

1/// Provides a counter for each kind of thing the walk saw and passed over, so a2/// caller can tell a complete enumeration from one that skipped part of the3/// tree. Counters saturate at their maximum, so a reported maximum means at4/// least that many.5pub const Stats = struct {6    roots_visited: u32 = 0,7    roots_missing: u32 = 0,8    directories_visited: u32 = 0,9    directories_unreadable: u32 = 0,10    directories_depth_skipped: u32 = 0,11    directories_cycle_skipped: u32 = 0,12    directories_truncated: u32 = 0,13    files_seen: u32 = 0,14    files_unreadable: u32 = 0,15    paths_too_long: u32 = 0,16};

1pub const directories_max: usize = 1 << 16;

1/// The ceilings on the three counts a caller picks as limits: files,2/// directories, and path bytes. A limit past any of the three is refused with3/// `CapacityExceeded`.4pub const entries_max: usize = 1 << 20;

1/// The longest extension `Format.fromName` will case-fold before matching, at2/// eight bytes. A longer extension is no extension.3pub const extension_bytes_max: usize = 8;

1/// Defines the longest path the catalog will take, which lets a record hold its2/// length in sixteen bits. A longer path is refused with3/// `FontPathBytesExhausted`.4pub const path_bytes_limit: usize = std.math.maxInt(u16);

1pub const path_bytes_max: usize = 1 << 26;

1/// Fills `set` with the directories this machine's operating system keeps fonts2/// in, ordered as the search visits them. A caller enumerating host fonts3/// starts here.4pub fn defaultRoots(set: *RootSet, environment: Environment) Support {5    return rootsFor(set, native_os, environment);6}

1/// Looks up `HOME`, `XDG_DATA_HOME`, and `XDG_DATA_DIRS` in the running2/// process, for a caller running against the real host.3pub fn hostEnvironment() Environment {4    return .{5        .home = env.get("HOME"),6        .xdg_data_home = env.get("XDG_DATA_HOME"),7        .xdg_data_dirs = env.get("XDG_DATA_DIRS"),8    };9}

1/// The largest total byte count a root set retains for its root paths, at 4096.2/// Past it the set refuses roots and counts them in `dropped`.3pub const root_bytes_max: usize = 4096;

1/// Fills `set` for the operating system named by `os_tag` after clearing the2/// set first, so a test on one host can check another platform's search order3/// and the refusal an unlisted one produces. Linux and the BSD targets take the4/// XDG order, the Apple targets take the Library order, and every other target5/// reports itself unsupported.6pub fn rootsFor(7    set: *RootSet,8    os_tag: std.Target.Os.Tag,9    environment: Environment,10) Support {11    set.clear();12    return switch (os_tag) {13        .linux, .freebsd, .netbsd, .openbsd, .dragonfly, .illumos, .hurd => .{14            .supported = linuxRoots(set, environment),15        },16        .macos, .maccatalyst, .ios, .tvos, .watchos, .visionos => .{17            .supported = appleRoots(set, environment),18        },19        else => .{ .unsupported = .platform },20    };21}

1/// The largest number of roots a root set retains, at 24. Past it the set2/// refuses roots and counts them in `dropped`.3pub const roots_max: u8 = 24;

1/// Combines the capacity refusals of the catalog with cancellation, so a caller2/// distinguishes a full catalog from a cancelled walk because nothing else3/// stops one. A cancellation from the io implementation travels out to the4/// caller.5pub const Error = Catalog.Exhaustion || error{Canceled};

1/// Hard ceiling of 16 levels on descent that caps two things: how many steps2/// the cycle guard climbs, and any `Options.depth_max` a caller sets for the3/// walk to assert against.4pub const depth_limit: u8 = 16;

1/// Caps how many directory entries get read out of a single directory before2/// the walk moves on, so a caller reading statistics knows what one enormous3/// directory does to an enumeration in progress. A directory past this bound is4/// counted in `directories_truncated`, and the walk carries on with the next5/// one.6pub const entries_per_directory_max: u32 = 1 << 20;

1/// Puts every font file found beneath the directories in `set` into `catalog`2/// and leaves an account of what it passed over in `stats`, so a caller can run3/// one enumeration and read the result out of its own catalog storage. The4/// roots are admitted first and the directories are then drained in admission5/// order, so the descent is breadth-first.6///7/// A directory that will not open, a file that disappears between the listing8/// and the stat, and a name too long for `std.Io.Dir.max_path_bytes` each add9/// to a counter and leave the walk running. Capacity refusal and cancellation10/// are the two things that stop the walk, and a refusal leaves the accepted11/// prefix in the catalog. The call overwrites `stats` at its start, and it12/// asserts an empty catalog and an `options.depth_max` within `depth_limit`.13pub fn enumerate(14    io: std.Io,15    catalog: *Catalog,16    set: *const RootSet,17    options: Options,18    stats: *Stats,19) Error!void {20    std.debug.assert(options.depth_max <= depth_limit);21    std.debug.assert(catalog.entryCount() == 0);22    std.debug.assert(catalog.directoryCount() == 0);23    stats.* = .{};24    var path_buffer: [std.Io.Dir.max_path_bytes]u8 = undefined;25    for (0..set.count) |index| {26        try admitRoot(io, catalog, set.path(@intCast(index)), @intCast(index), stats);27    }28    var drained: u32 = 0;29    while (catalog.takeDirectory()) |index| {30        std.debug.assert(drained < catalog.directoryCount());31        std.debug.assert(index == drained);32        drained += 1;33        try readDirectory(io, catalog, index, options, &path_buffer, stats);34    }35    std.debug.assert(drained == catalog.directoryCount());36    std.debug.assert(stats.roots_visited <= set.count);37}

1const sys = @import("../root.zig");2const catalog = @import("catalog.zig");3const roots = @import("roots.zig");4const walk = @import("walk.zig");56pub const required_capabilities = sys.capabilities.host(&.{ .environment, .filesystem });78pub const fixture = @import("fixture.zig");910pub const Catalog = catalog.Catalog;11pub const Directory = catalog.Directory;12pub const Entry = catalog.Entry;13pub const Format = catalog.Format;14pub const directories_max = catalog.directories_max;15pub const entries_max = catalog.entries_max;16pub const extension_bytes_max = catalog.extension_bytes_max;17pub const path_bytes_limit = catalog.path_bytes_limit;18pub const path_bytes_max = catalog.path_bytes_max;1920pub const Environment = roots.Environment;21pub const RootSet = roots.RootSet;22pub const Support = roots.Support;23pub const Unsupported = roots.Unsupported;24pub const defaultRoots = roots.defaultRoots;25pub const rootsFor = roots.rootsFor;26pub const hostEnvironment = roots.hostEnvironment;27pub const root_bytes_max = roots.root_bytes_max;28pub const roots_max = roots.roots_max;2930pub const Error = walk.Error;31pub const Options = walk.Options;32pub const Stats = walk.Stats;33pub const depth_limit = walk.depth_limit;34pub const entries_per_directory_max = walk.entries_per_directory_max;35pub const enumerate = walk.enumerate;

1pub const font = @import("font/root.zig");