lib/filigree/src/shape/line.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const model = @import("model.zig");
3 const unicode_data = @import("unicode");
4
5 const Allocator = std.mem.Allocator;
6 const ShapedGlyph = model.ShapedGlyph;
7 const Source = model.Source;
8
9 const LineBreakOpportunity = struct {
10 source_offset: u32,
11 action: unicode_data.LineBreakAction,
12 };
13
14 pub const LineBreakWorkspace = struct {
15 _opportunities: std.ArrayListUnmanaged(LineBreakOpportunity) = .empty,
16 _line_ends: std.ArrayListUnmanaged(u32) = .empty,
17
18 pub fn deinit(self: *LineBreakWorkspace, allocator: Allocator) void {
19 self._line_ends.deinit(allocator);
20 self._opportunities.deinit(allocator);
21 }
22
23 fn clear(self: *LineBreakWorkspace) void {
24 self._opportunities.clearRetainingCapacity();
25 self._line_ends.clearRetainingCapacity();
26 }
27 };
28
29 pub fn breakLinesInto(
30 allocator: Allocator,
31 glyphs: []const ShapedGlyph,
32 text: Source,
33 wrap_width: f64,
34 workspace: *LineBreakWorkspace,
35 ) ![]const u32 {
36 workspace.clear();
37 errdefer workspace.clear();
38
39 if (glyphs.len == 0 or wrap_width <= 0) {
40 try workspace._line_ends.append(allocator, @intCast(glyphs.len));
41 return workspace._line_ends.items;
42 }
43
44 try collectLineBreaksInto(
45 allocator,
46 text,
47 firstGlyphSourceOffset(glyphs),
48 &workspace._opportunities,
49 );
50
51 var line_width: f64 = 0;
52 var line_start: u32 = 0;
53 var last_text_break: u32 = 0;
54 var last_cluster_break: u32 = 0;
55
56 for (glyphs, 0..) |glyph, i| {
57 const advance: f64 = @as(f64, @floatFromInt(glyph.x_advance)) / 64.0;
58 line_width += advance;
59
60 if (i + 1 < glyphs.len) {
61 const next = glyphs[i + 1];
62 const cluster_boundary = next.cluster != glyph.cluster or next.cluster_index != glyph.cluster_index;
63 if (cluster_boundary and !next.flags.unsafe_to_break) {
64 const break_index: u32 = @intCast(i + 1);
65 last_cluster_break = break_index;
66 const text_break = lineBreakActionAt(workspace._opportunities.items, next.source_start);
67 if (text_break == .mandatory) {
68 try workspace._line_ends.append(allocator, break_index);
69 line_width = 0;
70 line_start = break_index;
71 last_text_break = 0;
72 last_cluster_break = 0;
73 continue;
74 }
75 if (text_break == .opportunity) {
76 last_text_break = break_index;
77 }
78 }
79 }
80
81 if (line_width > wrap_width) {
82 const selected_break = if (last_text_break > line_start) last_text_break else last_cluster_break;
83 if (selected_break <= line_start) continue;
84 try workspace._line_ends.append(allocator, selected_break);
85 line_start = selected_break;
86 line_width = 0;
87 var j: u32 = selected_break;
88 while (j <= @as(u32, @intCast(i))) : (j += 1) {
89 line_width += @as(f64, @floatFromInt(glyphs[j].x_advance)) / 64.0;
90 }
91 last_text_break = 0;
92 last_cluster_break = 0;
93 }
94 }
95
96 try workspace._line_ends.append(allocator, @intCast(glyphs.len));
97 return workspace._line_ends.items;
98 }
99
100 fn collectLineBreaksInto(
101 allocator: Allocator,
102 text: Source,
103 source_offset: u32,
104 breaks: *std.ArrayListUnmanaged(LineBreakOpportunity),
105 ) !void {
106 var iterator = try unicode_data.SourceIterator.init(text, source_offset);
107 var state: unicode_data.LineBreakState = .{};
108 while (try iterator.next()) |scalar| {
109 const action = state.consume(scalar.codepoint);
110 if (action != .prohibited) {
111 try breaks.append(allocator, .{
112 .source_offset = scalar.source.start,
113 .action = action,
114 });
115 }
116 }
117
118 const source_len = try text.byteLen();
119 const source_end = @as(usize, source_offset) + source_len;
120 if (source_end > std.math.maxInt(u32)) return error.SourceTooLong;
121 try breaks.append(allocator, .{
122 .source_offset = @intCast(source_end),
123 .action = state.finish(),
124 });
125 }
126
127 fn firstGlyphSourceOffset(glyphs: []const ShapedGlyph) u32 {
128 var offset: u32 = std.math.maxInt(u32);
129 for (glyphs) |glyph| {
130 offset = @min(offset, glyph.source_start);
131 }
132 if (offset == std.math.maxInt(u32)) return 0;
133 return offset;
134 }
135
136 fn lineBreakActionAt(breaks: []const LineBreakOpportunity, source_offset: u32) unicode_data.LineBreakAction {
137 var low: usize = 0;
138 var high: usize = breaks.len;
139 while (low < high) {
140 const mid = low + (high - low) / 2;
141 const found = breaks[mid];
142 if (source_offset < found.source_offset) {
143 high = mid;
144 } else if (source_offset > found.source_offset) {
145 low = mid + 1;
146 } else {
147 return found.action;
148 }
149 }
150 return .prohibited;
151 }
152
153 test "breakLinesInto single line" {
154 const alloc = std.testing.allocator;
155 var workspace = LineBreakWorkspace{};
156 defer workspace.deinit(alloc);
157 var glyphs = [_]ShapedGlyph{
158 .{ .glyph_id = 1, .cluster = 0, .cluster_index = 0, .source_start = 0, .source_end = 1, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
159 .{ .glyph_id = 2, .cluster = 1, .cluster_index = 1, .source_start = 1, .source_end = 2, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
160 };
161 const breaks = try breakLinesInto(alloc, &glyphs, .{ .utf8 = "AB" }, 100.0, &workspace);
162 try std.testing.expectEqual(@as(usize, 1), breaks.len);
163 try std.testing.expectEqual(@as(u32, 2), breaks[0]);
164 }
165
166 test "breakLinesInto wraps at Unicode space opportunities" {
167 const alloc = std.testing.allocator;
168 var workspace = LineBreakWorkspace{};
169 defer workspace.deinit(alloc);
170 var glyphs = [_]ShapedGlyph{
171 .{ .glyph_id = 1, .cluster = 0, .cluster_index = 0, .source_start = 0, .source_end = 1, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
172 .{ .glyph_id = 2, .cluster = 1, .cluster_index = 1, .source_start = 1, .source_end = 2, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
173 .{ .glyph_id = 3, .cluster = 2, .cluster_index = 2, .source_start = 2, .source_end = 3, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
174 .{ .glyph_id = 4, .cluster = 3, .cluster_index = 3, .source_start = 3, .source_end = 4, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
175 .{ .glyph_id = 5, .cluster = 4, .cluster_index = 4, .source_start = 4, .source_end = 5, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
176 };
177 const breaks = try breakLinesInto(alloc, &glyphs, .{ .utf8 = "AB CD" }, 25.0, &workspace);
178 try std.testing.expectEqual(@as(usize, 2), breaks.len);
179 try std.testing.expectEqual(@as(u32, 3), breaks[0]);
180 try std.testing.expectEqual(@as(u32, 5), breaks[1]);
181 }
182
183 test "breakLinesInto refuses break before closing punctuation after space" {
184 const alloc = std.testing.allocator;
185 var workspace = LineBreakWorkspace{};
186 defer workspace.deinit(alloc);
187 var glyphs = [_]ShapedGlyph{
188 .{ .glyph_id = 1, .cluster = 0, .cluster_index = 0, .source_start = 0, .source_end = 1, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
189 .{ .glyph_id = 2, .cluster = 1, .cluster_index = 1, .source_start = 1, .source_end = 2, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
190 .{ .glyph_id = 3, .cluster = 2, .cluster_index = 2, .source_start = 2, .source_end = 3, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
191 .{ .glyph_id = 4, .cluster = 3, .cluster_index = 3, .source_start = 3, .source_end = 4, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
192 };
193 const breaks = try breakLinesInto(alloc, &glyphs, .{ .utf8 = "A )B" }, 25.0, &workspace);
194 try std.testing.expectEqual(@as(usize, 2), breaks.len);
195 try std.testing.expectEqual(@as(u32, 3), breaks[0]);
196 try std.testing.expectEqual(@as(u32, 4), breaks[1]);
197 }
198
199 test "breakLinesInto keeps no break space with adjacent text" {
200 const alloc = std.testing.allocator;
201 var workspace = LineBreakWorkspace{};
202 defer workspace.deinit(alloc);
203 var glyphs = [_]ShapedGlyph{
204 .{ .glyph_id = 1, .cluster = 0, .cluster_index = 0, .source_start = 0, .source_end = 1, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
205 .{ .glyph_id = 2, .cluster = 1, .cluster_index = 1, .source_start = 1, .source_end = 3, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
206 .{ .glyph_id = 3, .cluster = 3, .cluster_index = 2, .source_start = 3, .source_end = 4, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
207 .{ .glyph_id = 4, .cluster = 4, .cluster_index = 3, .source_start = 4, .source_end = 5, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
208 .{ .glyph_id = 5, .cluster = 5, .cluster_index = 4, .source_start = 5, .source_end = 6, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
209 };
210 const breaks = try breakLinesInto(alloc, &glyphs, .{ .utf8 = "A\u{00a0}B C" }, 35.0, &workspace);
211 try std.testing.expectEqual(@as(usize, 2), breaks.len);
212 try std.testing.expectEqual(@as(u32, 4), breaks[0]);
213 try std.testing.expectEqual(@as(u32, 5), breaks[1]);
214 }
215
216 test "breakLinesInto skips unsafe cluster boundaries" {
217 const alloc = std.testing.allocator;
218 var workspace = LineBreakWorkspace{};
219 defer workspace.deinit(alloc);
220 var glyphs = [_]ShapedGlyph{
221 .{ .glyph_id = 1, .cluster = 0, .cluster_index = 0, .source_start = 0, .source_end = 1, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
222 .{ .glyph_id = 2, .cluster = 1, .cluster_index = 1, .source_start = 1, .source_end = 2, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0, .flags = .{ .unsafe_to_break = true } },
223 .{ .glyph_id = 3, .cluster = 2, .cluster_index = 2, .source_start = 2, .source_end = 3, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
224 .{ .glyph_id = 4, .cluster = 3, .cluster_index = 3, .source_start = 3, .source_end = 4, .x_advance = 640, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
225 };
226 const breaks = try breakLinesInto(alloc, &glyphs, .{ .utf8 = "ABCD" }, 15.0, &workspace);
227 try std.testing.expect(breaks.len >= 1);
228 try std.testing.expectEqual(@as(u32, 2), breaks[0]);
229 }
230
231 test "breakLinesInto independent workspaces preserve overlapping results" {
232 const allocator = std.testing.allocator;
233 var first_workspace = LineBreakWorkspace{};
234 defer first_workspace.deinit(allocator);
235 var second_workspace = LineBreakWorkspace{};
236 defer second_workspace.deinit(allocator);
237
238 var wrapped_glyphs: [5]ShapedGlyph = undefined;
239 fillLinearGlyphs(&wrapped_glyphs);
240 var single_line_glyphs: [2]ShapedGlyph = undefined;
241 fillLinearGlyphs(&single_line_glyphs);
242
243 const wrapped = try breakLinesInto(allocator, &wrapped_glyphs, .{ .utf8 = "AB CD" }, 25.0, &first_workspace);
244 const single_line = try breakLinesInto(allocator, &single_line_glyphs, .{ .utf8 = "AB" }, 100.0, &second_workspace);
245
246 try std.testing.expectEqualSlices(u32, &.{ 3, 5 }, wrapped);
247 try std.testing.expectEqualSlices(u32, &.{2}, single_line);
248 }
249
250 fn fillLinearGlyphs(glyphs: []ShapedGlyph) void {
251 for (glyphs, 0..) |*glyph, index| {
252 glyph.* = .{
253 .glyph_id = @intCast(index + 1),
254 .cluster = @intCast(index),
255 .cluster_index = @intCast(index),
256 .source_start = @intCast(index),
257 .source_end = @intCast(index + 1),
258 .x_advance = 640,
259 .y_advance = 0,
260 .x_offset = 0,
261 .y_offset = 0,
262 };
263 }
264 }
265
266 test "breakLinesInto warmed workspace needs no backing allocation" {
267 const text = "A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A";
268 var glyphs: [text.len]ShapedGlyph = undefined;
269 fillLinearGlyphs(&glyphs);
270
271 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{});
272 const allocator = failing.allocator();
273 var workspace = LineBreakWorkspace{};
274 defer workspace.deinit(allocator);
275
276 const first = try breakLinesInto(allocator, &glyphs, .{ .utf8 = text }, 25.0, &workspace);
277 const line_ends_ptr = first.ptr;
278 const opportunities_ptr = workspace._opportunities.items.ptr;
279
280 failing.fail_index = failing.alloc_index;
281 failing.resize_fail_index = failing.resize_index;
282 for (0..8) |_| {
283 const breaks = try breakLinesInto(allocator, &glyphs, .{ .utf8 = text }, 25.0, &workspace);
284 try std.testing.expectEqual(line_ends_ptr, breaks.ptr);
285 try std.testing.expectEqual(opportunities_ptr, workspace._opportunities.items.ptr);
286 }
287 try std.testing.expect(!failing.has_induced_failure);
288 }
289
290 test "breakLinesInto preserves warmed storage after opportunity growth fails" {
291 const small_text = "AB";
292 var small_glyphs: [small_text.len]ShapedGlyph = undefined;
293 fillLinearGlyphs(&small_glyphs);
294 const large_text = "A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A";
295 var large_glyphs: [large_text.len]ShapedGlyph = undefined;
296 fillLinearGlyphs(&large_glyphs);
297
298 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{});
299 const allocator = failing.allocator();
300 var workspace = LineBreakWorkspace{};
301 defer workspace.deinit(allocator);
302
303 _ = try breakLinesInto(allocator, &small_glyphs, .{ .utf8 = small_text }, 100.0, &workspace);
304 const line_ends_ptr = workspace._line_ends.items.ptr;
305 const line_ends_capacity = workspace._line_ends.capacity;
306 const opportunities_ptr = workspace._opportunities.items.ptr;
307 const opportunities_capacity = workspace._opportunities.capacity;
308
309 failing.fail_index = failing.alloc_index;
310 failing.resize_fail_index = failing.resize_index;
311 try std.testing.expectError(
312 error.OutOfMemory,
313 breakLinesInto(allocator, &large_glyphs, .{ .utf8 = large_text }, 1000.0, &workspace),
314 );
315 try std.testing.expect(failing.has_induced_failure);
316 try std.testing.expectEqual(@as(usize, 0), workspace._line_ends.items.len);
317 try std.testing.expectEqual(@as(usize, 0), workspace._opportunities.items.len);
318 try std.testing.expectEqual(line_ends_ptr, workspace._line_ends.items.ptr);
319 try std.testing.expectEqual(line_ends_capacity, workspace._line_ends.capacity);
320 try std.testing.expectEqual(opportunities_ptr, workspace._opportunities.items.ptr);
321 try std.testing.expectEqual(opportunities_capacity, workspace._opportunities.capacity);
322
323 failing.fail_index = std.math.maxInt(usize);
324 failing.resize_fail_index = std.math.maxInt(usize);
325 const recovered = try breakLinesInto(allocator, &small_glyphs, .{ .utf8 = small_text }, 100.0, &workspace);
326 try std.testing.expectEqualSlices(u32, &.{small_glyphs.len}, recovered);
327 try std.testing.expectEqual(line_ends_ptr, recovered.ptr);
328 }
329
330 test "breakLinesInto preserves line storage after output growth fails" {
331 const text = "A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A";
332 var glyphs: [text.len]ShapedGlyph = undefined;
333 fillLinearGlyphs(&glyphs);
334
335 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{});
336 const allocator = failing.allocator();
337 var workspace = LineBreakWorkspace{};
338 defer workspace.deinit(allocator);
339
340 _ = try breakLinesInto(allocator, &glyphs, .{ .utf8 = text }, 1000.0, &workspace);
341 const line_ends_ptr = workspace._line_ends.items.ptr;
342 const line_ends_capacity = workspace._line_ends.capacity;
343 const opportunities_ptr = workspace._opportunities.items.ptr;
344 const opportunities_capacity = workspace._opportunities.capacity;
345
346 failing.fail_index = failing.alloc_index;
347 failing.resize_fail_index = failing.resize_index;
348 try std.testing.expectError(
349 error.OutOfMemory,
350 breakLinesInto(allocator, &glyphs, .{ .utf8 = text }, 5.0, &workspace),
351 );
352 try std.testing.expect(failing.has_induced_failure);
353 try std.testing.expectEqual(@as(usize, 0), workspace._line_ends.items.len);
354 try std.testing.expectEqual(@as(usize, 0), workspace._opportunities.items.len);
355 try std.testing.expectEqual(line_ends_ptr, workspace._line_ends.items.ptr);
356 try std.testing.expectEqual(line_ends_capacity, workspace._line_ends.capacity);
357 try std.testing.expectEqual(opportunities_ptr, workspace._opportunities.items.ptr);
358 try std.testing.expectEqual(opportunities_capacity, workspace._opportunities.capacity);
359
360 failing.fail_index = std.math.maxInt(usize);
361 failing.resize_fail_index = std.math.maxInt(usize);
362 const recovered = try breakLinesInto(allocator, &glyphs, .{ .utf8 = text }, 5.0, &workspace);
363 try std.testing.expect(recovered.len > line_ends_capacity);
364 }