lib/sys/src/font/walk.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const catalog_module = @import("catalog.zig");
3 const roots_module = @import("roots.zig");
4
5 const Catalog = catalog_module.Catalog;
6 const Format = catalog_module.Format;
7 const RootSet = roots_module.RootSet;
8
9 /// Hard ceiling of 16 levels on descent that caps two things: how many steps
10 /// the cycle guard climbs, and any `Options.depth_max` a caller sets for the
11 /// walk to assert against.
12 pub const depth_limit: u8 = 16;
13
14 /// Caps how many directory entries get read out of a single directory before
15 /// the walk moves on, so a caller reading statistics knows what one enormous
16 /// directory does to an enumeration in progress. A directory past this bound is
17 /// counted in `directories_truncated`, and the walk carries on with the next
18 /// one.
19 pub const entries_per_directory_max: u32 = 1 << 20;
20
21 /// The limits a caller sets on one walk.
22 pub const Options = struct {
23 /// Sets how many levels beneath a root the walk goes, which a caller lowers
24 /// to keep a walk shallow and cheap. The default is six, and zero reads the
25 /// roots alone.
26 depth_max: u8 = 6,
27 };
28
29 /// Provides a counter for each kind of thing the walk saw and passed over, so a
30 /// caller can tell a complete enumeration from one that skipped part of the
31 /// tree. Counters saturate at their maximum, so a reported maximum means at
32 /// least that many.
33 pub const Stats = struct {
34 roots_visited: u32 = 0,
35 roots_missing: u32 = 0,
36 directories_visited: u32 = 0,
37 directories_unreadable: u32 = 0,
38 directories_depth_skipped: u32 = 0,
39 directories_cycle_skipped: u32 = 0,
40 directories_truncated: u32 = 0,
41 files_seen: u32 = 0,
42 files_unreadable: u32 = 0,
43 paths_too_long: u32 = 0,
44 };
45
46 /// Combines the capacity refusals of the catalog with cancellation, so a caller
47 /// distinguishes a full catalog from a cancelled walk because nothing else
48 /// stops one. A cancellation from the io implementation travels out to the
49 /// caller.
50 pub const Error = Catalog.Exhaustion || error{Canceled};
51
52 /// Puts every font file found beneath the directories in `set` into `catalog`
53 /// and leaves an account of what it passed over in `stats`, so a caller can run
54 /// one enumeration and read the result out of its own catalog storage. The
55 /// roots are admitted first and the directories are then drained in admission
56 /// order, so the descent is breadth-first.
57 ///
58 /// A directory that will not open, a file that disappears between the listing
59 /// and the stat, and a name too long for `std.Io.Dir.max_path_bytes` each add
60 /// to a counter and leave the walk running. Capacity refusal and cancellation
61 /// are the two things that stop the walk, and a refusal leaves the accepted
62 /// prefix in the catalog. The call overwrites `stats` at its start, and it
63 /// asserts an empty catalog and an `options.depth_max` within `depth_limit`.
64 pub fn enumerate(
65 io: std.Io,
66 catalog: *Catalog,
67 set: *const RootSet,
68 options: Options,
69 stats: *Stats,
70 ) Error!void {
71 std.debug.assert(options.depth_max <= depth_limit);
72 std.debug.assert(catalog.entryCount() == 0);
73 std.debug.assert(catalog.directoryCount() == 0);
74 stats.* = .{};
75 var path_buffer: [std.Io.Dir.max_path_bytes]u8 = undefined;
76 for (0..set.count) |index| {
77 try admitRoot(io, catalog, set.path(@intCast(index)), @intCast(index), stats);
78 }
79 var drained: u32 = 0;
80 while (catalog.takeDirectory()) |index| {
81 std.debug.assert(drained < catalog.directoryCount());
82 std.debug.assert(index == drained);
83 drained += 1;
84 try readDirectory(io, catalog, index, options, &path_buffer, stats);
85 }
86 std.debug.assert(drained == catalog.directoryCount());
87 std.debug.assert(stats.roots_visited <= set.count);
88 }
89
90 fn admitRoot(
91 io: std.Io,
92 catalog: *Catalog,
93 root_path: []const u8,
94 root: u8,
95 stats: *Stats,
96 ) Error!void {
97 std.debug.assert(root_path.len != 0);
98 std.debug.assert(std.fs.path.isAbsolute(root_path));
99 const stat = std.Io.Dir.cwd().statFile(io, root_path, .{}) catch |err| switch (err) {
100 error.Canceled => return error.Canceled,
101 else => {
102 stats.roots_missing +|= 1;
103 return;
104 },
105 };
106 if (stat.kind != .directory) {
107 stats.roots_missing +|= 1;
108 return;
109 }
110 _ = try catalog.appendRoot(root_path, stat.inode, root);
111 stats.roots_visited +|= 1;
112 }
113
114 fn readDirectory(
115 io: std.Io,
116 catalog: *Catalog,
117 index: u32,
118 options: Options,
119 path_buffer: []u8,
120 stats: *Stats,
121 ) Error!void {
122 const record = catalog.directoryAt(index);
123 std.debug.assert(record.depth <= options.depth_max);
124 const directory_path = catalog.directoryPath(record);
125 std.debug.assert(directory_path.len != 0);
126 std.debug.assert(path_buffer.len == std.Io.Dir.max_path_bytes);
127 var directory = std.Io.Dir.openDirAbsolute(io, directory_path, .{
128 .iterate = true,
129 }) catch |err| switch (err) {
130 error.Canceled => return error.Canceled,
131 else => {
132 stats.directories_unreadable +|= 1;
133 return;
134 },
135 };
136 defer directory.close(io);
137 stats.directories_visited +|= 1;
138 var iterator = directory.iterate();
139 var seen: u32 = 0;
140 while (seen < entries_per_directory_max) : (seen += 1) {
141 const entry = iterator.next(io) catch |err| switch (err) {
142 error.Canceled => return error.Canceled,
143 else => {
144 stats.directories_unreadable +|= 1;
145 return;
146 },
147 } orelse return;
148 const child = join(path_buffer, directory_path, entry.name) orelse {
149 stats.paths_too_long +|= 1;
150 continue;
151 };
152 try admitChild(io, catalog, directory, index, entry, child, options, stats);
153 }
154 stats.directories_truncated +|= 1;
155 }
156
157 fn admitChild(
158 io: std.Io,
159 catalog: *Catalog,
160 directory: std.Io.Dir,
161 parent: u32,
162 entry: std.Io.Dir.Entry,
163 child_path: []const u8,
164 options: Options,
165 stats: *Stats,
166 ) Error!void {
167 const record = catalog.directoryAt(parent);
168 std.debug.assert(entry.name.len != 0);
169 std.debug.assert(child_path.len > entry.name.len);
170 switch (entry.kind) {
171 .directory => try admitDirectory(
172 catalog,
173 parent,
174 entry.inode,
175 child_path,
176 options,
177 stats,
178 ),
179 .file => try admitFile(io, catalog, directory, entry.name, child_path, record.root, stats),
180 .sym_link, .unknown => {
181 const stat = directory.statFile(io, entry.name, .{}) catch |err| switch (err) {
182 error.Canceled => return error.Canceled,
183 else => {
184 stats.files_unreadable +|= 1;
185 return;
186 },
187 };
188 switch (stat.kind) {
189 .directory => try admitDirectory(
190 catalog,
191 parent,
192 stat.inode,
193 child_path,
194 options,
195 stats,
196 ),
197 .file => try admitStatted(
198 catalog,
199 entry.name,
200 child_path,
201 stat,
202 record.root,
203 stats,
204 ),
205 else => {},
206 }
207 },
208 else => {},
209 }
210 }
211
212 fn admitDirectory(
213 catalog: *Catalog,
214 parent: u32,
215 inode: u64,
216 child_path: []const u8,
217 options: Options,
218 stats: *Stats,
219 ) Error!void {
220 const record = catalog.directoryAt(parent);
221 std.debug.assert(options.depth_max <= depth_limit);
222 std.debug.assert(record.depth <= options.depth_max);
223 if (record.depth == options.depth_max) {
224 stats.directories_depth_skipped +|= 1;
225 return;
226 }
227 if (ancestorHolds(catalog, parent, inode)) {
228 stats.directories_cycle_skipped +|= 1;
229 return;
230 }
231 _ = try catalog.appendDirectory(
232 child_path,
233 inode,
234 parent,
235 record.depth + 1,
236 record.root,
237 );
238 }
239
240 fn admitFile(
241 io: std.Io,
242 catalog: *Catalog,
243 directory: std.Io.Dir,
244 name: []const u8,
245 child_path: []const u8,
246 root: u8,
247 stats: *Stats,
248 ) Error!void {
249 std.debug.assert(name.len != 0);
250 std.debug.assert(std.mem.endsWith(u8, child_path, name));
251 stats.files_seen +|= 1;
252 const format = Format.fromName(name) orelse return;
253 const stat = directory.statFile(io, name, .{}) catch |err| switch (err) {
254 error.Canceled => return error.Canceled,
255 else => {
256 stats.files_unreadable +|= 1;
257 return;
258 },
259 };
260 if (stat.kind != .file) return;
261 try catalog.appendEntry(child_path, stat.size, format, root);
262 }
263
264 fn admitStatted(
265 catalog: *Catalog,
266 name: []const u8,
267 child_path: []const u8,
268 stat: std.Io.File.Stat,
269 root: u8,
270 stats: *Stats,
271 ) Error!void {
272 std.debug.assert(name.len != 0);
273 std.debug.assert(stat.kind == .file);
274 stats.files_seen +|= 1;
275 const format = Format.fromName(name) orelse return;
276 try catalog.appendEntry(child_path, stat.size, format, root);
277 }
278
279 fn ancestorHolds(catalog: *const Catalog, from: u32, inode: u64) bool {
280 std.debug.assert(from < catalog.directoryCount());
281 var index = from;
282 var steps: u8 = 0;
283 while (steps <= depth_limit) : (steps += 1) {
284 const record = catalog.directoryAt(index);
285 std.debug.assert(record.parent <= index);
286 if (record.inode == inode) return true;
287 if (record.parent == index) return false;
288 index = record.parent;
289 }
290 return false;
291 }
292
293 fn join(buffer: []u8, parent: []const u8, name: []const u8) ?[]const u8 {
294 std.debug.assert(parent.len != 0);
295 std.debug.assert(name.len != 0);
296 const total = parent.len + 1 + name.len;
297 if (total > buffer.len) return null;
298 @memcpy(buffer[0..parent.len], parent);
299 buffer[parent.len] = '/';
300 @memcpy(buffer[parent.len + 1 ..][0..name.len], name);
301 std.debug.assert(buffer[parent.len] == '/');
302 return buffer[0..total];
303 }