lib/filigree/src/shape/output.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const model = @import("model.zig");
4
5 const ShapedGlyph = model.ShapedGlyph;
6 const Cluster = model.Cluster;
7 const LigatureCaret = model.LigatureCaret;
8 const Direction = model.Direction;
9 const WritingMode = model.WritingMode;
10 const OutputOrder = model.OutputOrder;
11 const GlyphRun = model.GlyphRun;
12
13 const OutputLimits = struct {
14 /// Peak glyph slots, including the pre-substitution run. Also bounds clusters.
15 max_glyphs: usize,
16 /// Caret records retained across substitution and positioning passes.
17 max_ligature_carets: usize,
18 };
19
20 const OutputCapacity = struct {
21 limits: OutputLimits,
22 cluster_offset: usize,
23 caret_offset: usize,
24 storage_bytes: usize,
25
26 pub fn derive(limits: OutputLimits) error{CapacityOverflow}!OutputCapacity {
27 if (limits.max_glyphs > std.math.maxInt(u32)) return error.CapacityOverflow;
28 if (limits.max_ligature_carets > std.math.maxInt(u32)) return error.CapacityOverflow;
29 const glyphs = try placed(ShapedGlyph, 0, limits.max_glyphs);
30 const clusters = try placed(Cluster, glyphs.end, limits.max_glyphs);
31 const carets = try placed(LigatureCaret, clusters.end, limits.max_ligature_carets);
32 return .{
33 .limits = limits,
34 .cluster_offset = clusters.start,
35 .caret_offset = carets.start,
36 .storage_bytes = carets.end,
37 };
38 }
39 };
40
41 const Region = struct { start: usize, end: usize };
42
43 fn placed(comptime T: type, offset: usize, count: usize) error{CapacityOverflow}!Region {
44 const mask: usize = @alignOf(T) - 1;
45 const padded = std.math.add(usize, offset, mask) catch return error.CapacityOverflow;
46 const start = padded & ~mask;
47 const bytes = std.math.mul(usize, count, @sizeOf(T)) catch return error.CapacityOverflow;
48 return .{
49 .start = start,
50 .end = std.math.add(usize, start, bytes) catch return error.CapacityOverflow,
51 };
52 }
53
54 fn typedSlice(
55 comptime T: type,
56 bytes: []align(Output.storage_alignment) u8,
57 offset: usize,
58 count: usize,
59 ) []T {
60 const region = bytes[offset..][0 .. count * @sizeOf(T)];
61 return std.mem.bytesAsSlice(T, @as([]align(@alignOf(T)) u8, @alignCast(region)));
62 }
63
64 pub const Output = struct {
65 phase: alloc_phase.capacity.Phase,
66 capacity: Capacity,
67 bytes: []align(storage_alignment) u8,
68 glyphs: std.ArrayList(ShapedGlyph),
69 clusters: std.ArrayList(Cluster),
70 ligature_carets: std.ArrayList(LigatureCaret),
71 total_x_advance: i32 = 0,
72 total_y_advance: i32 = 0,
73 direction: Direction = .ltr,
74 writing_mode: WritingMode = .horizontal,
75 output_order: OutputOrder = .visual,
76
77 pub const Limits: type = OutputLimits;
78 pub const Capacity: type = OutputCapacity;
79 pub const Exhaustion = error{OutputCapacityExceeded};
80 pub const InitError = std.mem.Allocator.Error || error{CapacityOverflow};
81 pub const storage_alignment: usize = @max(
82 @alignOf(ShapedGlyph),
83 @alignOf(Cluster),
84 @alignOf(LigatureCaret),
85 );
86
87 pub const claim: alloc_phase.capacity.Declaration = .{
88 .source = .{
89 .id = "filigree.shape_output",
90 .kind = .phase_static,
91 .limit_source = .caller,
92 .storage = .{
93 .covered = &.{
94 .{
95 .id = "shaped_glyphs",
96 .lifetime = .steady,
97 .detail = "glyph positions and source associations",
98 },
99 .{
100 .id = "shaped_clusters",
101 .lifetime = .steady,
102 .detail = "at most one cluster per glyph slot",
103 },
104 .{
105 .id = "ligature_carets",
106 .lifetime = .steady,
107 .detail = "caller-budgeted font caret records",
108 },
109 },
110 .excluded = &.{
111 "source text and font bytes",
112 "shape context scratch and fallback segmentation",
113 },
114 },
115 .capacity = .{
116 .inputs = &.{
117 alloc_phase.capacity.bindInput(Limits, "max_glyphs", "max_glyphs"),
118 alloc_phase.capacity.bindInput(
119 Limits,
120 "max_ligature_carets",
121 "max_ligature_carets",
122 ),
123 },
124 .type_selectors = &.{
125 alloc_phase.capacity.bindType(ShapedGlyph, "shapedglyph"),
126 alloc_phase.capacity.bindType(Cluster, "cluster"),
127 alloc_phase.capacity.bindType(LigatureCaret, "ligaturecaret"),
128 },
129 .nodes = &.{
130 .{ .input = 0 },
131 .{ .input = 1 },
132 .{ .scale = .{
133 .node = 0,
134 .coefficient = .{ .size_of_concrete_type = 0 },
135 } },
136 .{ .alignment = .{ .node = 2, .alignment = .{ .concrete_type = 1 } } },
137 .{ .scale = .{
138 .node = 0,
139 .coefficient = .{ .size_of_concrete_type = 1 },
140 } },
141 .{ .add = .{ .left = 3, .right = 4 } },
142 .{ .alignment = .{ .node = 5, .alignment = .{ .concrete_type = 2 } } },
143 .{ .scale = .{
144 .node = 1,
145 .coefficient = .{ .size_of_concrete_type = 2 },
146 } },
147 .{ .add = .{ .left = 6, .right = 7 } },
148 },
149 .assertions = &.{.{
150 .scope = .closure_total,
151 .measure = .retained,
152 .relation = .exact,
153 .expression = 8,
154 }},
155 },
156 .overload = .{
157 .kind = .reject_before_mutation,
158 .detail = "appends reject before mutation; shape calls clear failed runs",
159 },
160 .risks = .{
161 .transitive = .{
162 .status = .witnessed,
163 .detail = "operations use the slab without allocator capability",
164 },
165 .foreign = .{
166 .status = .excluded,
167 .detail = "output storage crosses no foreign boundary",
168 },
169 },
170 .obligations = &.{
171 .{ .key = "filigree_shape_output_capacity", .role = .capacity_model },
172 .{ .key = "filigree_shape_output_oom", .role = .custom },
173 .{ .key = "filigree_shape_output_boundaries", .role = .overload },
174 .{ .key = "filigree_shape_output_sealed", .role = .transitive_risk },
175 .{ .key = "filigree_shape_output_root", .role = .custom },
176 },
177 },
178 .bindings = .{
179 .owner = @This(),
180 .seal = .{
181 .family = alloc_phase.capacity.selector(@This().activate),
182 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
183 },
184 .teardown = .{
185 .family = alloc_phase.capacity.selector(@This().deinit),
186 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
187 },
188 },
189 };
190
191 /// Acquires and activates exact output storage. Font substitutions can expand
192 /// glyphs and carets, so callers select both limits independently of source length.
193 pub fn init(allocator: std.mem.Allocator, limits: Limits) InitError!Output {
194 const capacity = try Capacity.derive(limits);
195 const bytes = try allocator.alignedAlloc(
196 u8,
197 .fromByteUnits(storage_alignment),
198 capacity.storage_bytes,
199 );
200 var output: Output = .{
201 .phase = .initialization,
202 .capacity = capacity,
203 .bytes = bytes,
204 .glyphs = .initBuffer(typedSlice(ShapedGlyph, bytes, 0, limits.max_glyphs)),
205 .clusters = .initBuffer(typedSlice(
206 Cluster,
207 bytes,
208 capacity.cluster_offset,
209 limits.max_glyphs,
210 )),
211 .ligature_carets = .initBuffer(typedSlice(
212 LigatureCaret,
213 bytes,
214 capacity.caret_offset,
215 limits.max_ligature_carets,
216 )),
217 };
218 output.activate();
219 return output;
220 }
221
222 pub fn activate(self: *Output) void {
223 std.debug.assert(self.phase == .initialization);
224 self.assertStorage();
225 self.phase = .steady;
226 }
227
228 /// Releases the initialization slab through the same allocator used by init.
229 pub fn deinit(self: *Output, allocator: std.mem.Allocator) void {
230 self.assertStorage();
231 allocator.free(self.bytes);
232 self.* = undefined;
233 }
234
235 pub fn ensureUnused(
236 self: *const Output,
237 glyphs: usize,
238 clusters: usize,
239 carets: usize,
240 ) Exhaustion!void {
241 std.debug.assert(self.phase == .steady);
242 std.debug.assert(self.glyphs.items.len <= self.glyphs.capacity);
243 std.debug.assert(self.clusters.items.len <= self.clusters.capacity);
244 std.debug.assert(self.ligature_carets.items.len <= self.ligature_carets.capacity);
245 if (glyphs > self.glyphs.capacity - self.glyphs.items.len or
246 clusters > self.clusters.capacity - self.clusters.items.len or
247 carets > self.ligature_carets.capacity - self.ligature_carets.items.len)
248 {
249 return error.OutputCapacityExceeded;
250 }
251 }
252
253 pub fn appendGlyph(self: *Output, glyph: ShapedGlyph) Exhaustion!void {
254 try self.ensureUnused(1, 0, 0);
255 self.glyphs.appendAssumeCapacity(glyph);
256 }
257
258 pub fn appendCluster(self: *Output, cluster: Cluster) Exhaustion!void {
259 try self.ensureUnused(0, 1, 0);
260 self.clusters.appendAssumeCapacity(cluster);
261 }
262
263 fn assertStorage(self: *const Output) void {
264 std.debug.assert(self.bytes.len == self.capacity.storage_bytes);
265 std.debug.assert(self.glyphs.capacity == self.capacity.limits.max_glyphs);
266 std.debug.assert(self.clusters.capacity == self.capacity.limits.max_glyphs);
267 std.debug.assert(self.ligature_carets.capacity == self.capacity.limits.max_ligature_carets);
268 std.debug.assert(self.glyphs.items.len <= self.glyphs.capacity);
269 std.debug.assert(self.clusters.items.len <= self.clusters.capacity);
270 std.debug.assert(self.ligature_carets.items.len <= self.ligature_carets.capacity);
271 }
272
273 pub fn clearRetainingCapacity(self: *Output) void {
274 std.debug.assert(self.phase == .steady);
275 self.glyphs.clearRetainingCapacity();
276 self.clusters.clearRetainingCapacity();
277 self.ligature_carets.clearRetainingCapacity();
278 self.total_x_advance = 0;
279 self.total_y_advance = 0;
280 self.direction = .ltr;
281 self.writing_mode = .horizontal;
282 self.output_order = .visual;
283 }
284
285 /// Returns a borrowed glyph run invalidated by mutation, `clearRetainingCapacity`, or deinit.
286 pub fn run(self: *const Output) GlyphRun {
287 return .{
288 .glyphs = self.glyphs.items,
289 .clusters = self.clusters.items,
290 .ligature_carets = self.ligature_carets.items,
291 .total_x_advance = self.total_x_advance,
292 .total_y_advance = self.total_y_advance,
293 .direction = self.direction,
294 .writing_mode = self.writing_mode,
295 .output_order = self.output_order,
296 };
297 }
298
299 pub fn glyphCapacity(self: *const Output) usize {
300 return self.glyphs.capacity;
301 }
302
303 pub fn clusterCapacity(self: *const Output) usize {
304 return self.clusters.capacity;
305 }
306
307 pub fn ligatureCaretCapacity(self: *const Output) usize {
308 return self.ligature_carets.capacity;
309 }
310 };
311
312 comptime {
313 alloc_phase.capacity.requireAllocatorRejectingOwnerShape(Output);
314 }
315
316 fn modelBytes(limits: Output.Limits) u128 {
317 const glyph_bytes = @as(u128, limits.max_glyphs) * @sizeOf(ShapedGlyph);
318 const cluster_align = @as(u128, @alignOf(Cluster));
319 const cluster_start = ((glyph_bytes + cluster_align - 1) / cluster_align) * cluster_align;
320 const cluster_end = cluster_start + @as(u128, limits.max_glyphs) * @sizeOf(Cluster);
321 const caret_align = @as(u128, @alignOf(LigatureCaret));
322 const caret_start = ((cluster_end + caret_align - 1) / caret_align) * caret_align;
323 return caret_start + @as(u128, limits.max_ligature_carets) * @sizeOf(LigatureCaret);
324 }
325
326 test "shaping output capacity matches independent aligned memory model" {
327 comptime {
328 alloc_phase.capacity.record(
329 alloc_phase.capacity.witness(Output, "filigree_shape_output_capacity"),
330 );
331 }
332 for ([_]Output.Limits{
333 .{ .max_glyphs = 0, .max_ligature_carets = 0 },
334 .{ .max_glyphs = 1, .max_ligature_carets = 0 },
335 .{ .max_glyphs = 37, .max_ligature_carets = 23 },
336 .{ .max_glyphs = 4096, .max_ligature_carets = 2048 },
337 }) |limits| {
338 const capacity = try Output.Capacity.derive(limits);
339 try std.testing.expectEqual(modelBytes(limits), @as(u128, capacity.storage_bytes));
340 }
341 try std.testing.expectError(error.CapacityOverflow, Output.Capacity.derive(.{
342 .max_glyphs = std.math.maxInt(usize),
343 .max_ligature_carets = 0,
344 }));
345 try std.testing.expectError(error.CapacityOverflow, Output.Capacity.derive(.{
346 .max_glyphs = 0,
347 .max_ligature_carets = std.math.maxInt(usize),
348 }));
349 }
350
351 fn checkInitFailure(allocator: std.mem.Allocator) !void {
352 var output = try Output.init(allocator, .{
353 .max_glyphs = 13,
354 .max_ligature_carets = 7,
355 });
356 defer output.deinit(allocator);
357 try output.ensureUnused(13, 13, 7);
358 }
359
360 test "shaping output initialization OOM is clean and retryable" {
361 comptime {
362 alloc_phase.capacity.record(
363 alloc_phase.capacity.witness(Output, "filigree_shape_output_oom"),
364 );
365 }
366 try std.testing.checkAllAllocationFailures(std.testing.allocator, checkInitFailure, .{});
367 }
368
369 const sample_glyph: ShapedGlyph = .{
370 .glyph_id = 1,
371 .cluster = 0,
372 .x_advance = 1,
373 .y_advance = 0,
374 .x_offset = 0,
375 .y_offset = 0,
376 };
377 const sample_cluster: Cluster = .{
378 .source = .{ .start = 0, .end = 1 },
379 .glyphs = .{ .start = 0, .end = 1 },
380 };
381
382 test "shaping output rejects exact plus one without changing prior contents" {
383 comptime {
384 alloc_phase.capacity.record(
385 alloc_phase.capacity.witness(Output, "filigree_shape_output_boundaries"),
386 );
387 }
388 var output = try Output.init(std.testing.allocator, .{
389 .max_glyphs = 1,
390 .max_ligature_carets = 1,
391 });
392 defer output.deinit(std.testing.allocator);
393 try output.appendGlyph(sample_glyph);
394 try output.appendCluster(sample_cluster);
395 try output.ensureUnused(0, 0, 1);
396 output.ligature_carets.appendAssumeCapacity(.{ .x_offset = 9 });
397 try std.testing.expectError(error.OutputCapacityExceeded, output.appendGlyph(sample_glyph));
398 try std.testing.expectError(error.OutputCapacityExceeded, output.appendCluster(sample_cluster));
399 try std.testing.expectError(error.OutputCapacityExceeded, output.ensureUnused(0, 0, 1));
400 try std.testing.expectEqual(sample_glyph, output.run().glyphs[0]);
401 try std.testing.expectEqual(sample_cluster, output.run().clusters[0]);
402 try std.testing.expectEqual(@as(i32, 9), output.run().ligature_carets[0].x_offset);
403 output.clearRetainingCapacity();
404 try output.ensureUnused(1, 1, 1);
405 var empty = try Output.init(std.testing.allocator, .{
406 .max_glyphs = 0,
407 .max_ligature_carets = 0,
408 });
409 defer empty.deinit(std.testing.allocator);
410 try std.testing.expectError(error.OutputCapacityExceeded, empty.appendGlyph(sample_glyph));
411 try empty.ensureUnused(0, 0, 0);
412 }
413
414 test "shaping output cold sealed use and varying counts preserve pointers" {
415 comptime {
416 alloc_phase.capacity.record(
417 alloc_phase.capacity.witness(Output, "filigree_shape_output_sealed"),
418 );
419 }
420 var counting = std.testing.FailingAllocator.init(std.testing.allocator, .{});
421 const allocator = counting.allocator();
422 var output = try Output.init(allocator, .{
423 .max_glyphs = 4096,
424 .max_ligature_carets = 4096,
425 });
426 defer output.deinit(allocator);
427 const allocations = counting.alloc_index;
428 counting.fail_index = allocations;
429 const glyph_pointer = output.glyphs.items.ptr;
430 const cluster_pointer = output.clusters.items.ptr;
431 const caret_pointer = output.ligature_carets.items.ptr;
432 for ([_]usize{ 4096, 0, 1, 37, 4096 }) |count| {
433 output.clearRetainingCapacity();
434 for (0..count) |_| {
435 try output.appendGlyph(sample_glyph);
436 try output.appendCluster(sample_cluster);
437 try output.ensureUnused(0, 0, 1);
438 output.ligature_carets.appendAssumeCapacity(.{ .x_offset = 9 });
439 }
440 try std.testing.expectEqual(count, output.run().glyphs.len);
441 try std.testing.expectEqual(count, output.run().clusters.len);
442 try std.testing.expectEqual(count, output.run().ligature_carets.len);
443 try std.testing.expectEqual(glyph_pointer, output.glyphs.items.ptr);
444 try std.testing.expectEqual(cluster_pointer, output.clusters.items.ptr);
445 try std.testing.expectEqual(caret_pointer, output.ligature_carets.items.ptr);
446 }
447 try std.testing.expectEqual(@as(usize, 1), allocations);
448 try std.testing.expectEqual(allocations, counting.alloc_index);
449 try std.testing.expectEqual(output.capacity.storage_bytes, counting.allocated_bytes);
450 }
451
452 test "shaping output is exported through the public shape namespace" {
453 comptime {
454 alloc_phase.capacity.record(
455 alloc_phase.capacity.witness(Output, "filigree_shape_output_root"),
456 );
457 }
458 try std.testing.expect(@import("root.zig").Output == Output);
459 }