lib/filigree/src/caret.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const fixtures = @import("fixture/root.zig");
3 const shape = @import("shape/root.zig");
4 const unicode = @import("unicode");
5
6 pub const LineHit = struct {
7 byte_offset: usize,
8 advance: f32,
9 };
10
11 pub fn advanceForByteOffset(run: shape.GlyphRun, byte_offset: usize, text_len: usize) f32 {
12 const target = @min(byte_offset, text_len);
13 var pen: f32 = 0;
14 const map = run.clusterMap();
15 for (run.clusters, 0..) |cluster, cluster_index| {
16 const start = clampedSourceOffset(cluster.source.start, text_len);
17 const end = clampedSourceOffset(cluster.source.end, text_len);
18 const advance = clusterAdvance(run, cluster.glyphs);
19 if (target <= start) return pen;
20 if (target < end) return pen + advanceWithinCluster(map, cluster_index, target, advance, text_len);
21 pen += advance;
22 }
23 return pen;
24 }
25
26 pub fn hitTestAdvance(run: shape.GlyphRun, x: f32, text: []const u8) LineHit {
27 var pen: f32 = 0;
28 const map = run.clusterMap();
29 for (run.clusters, 0..) |cluster, cluster_index| {
30 const advance = clusterAdvance(run, cluster.glyphs);
31 if (x <= pen) {
32 const byte_offset = clampedSourceOffset(cluster.source.start, text.len);
33 return .{ .byte_offset = byte_offset, .advance = pen };
34 }
35 if (x < pen + advance) {
36 const stop = nearestStopInCluster(map, cluster_index, x - pen, advance, text);
37 return .{ .byte_offset = stop.byte_offset, .advance = pen + stop.advance };
38 }
39 pen += advance;
40 }
41 return .{ .byte_offset = text.len, .advance = pen };
42 }
43
44 pub fn hitTestAdvanceByLength(run: shape.GlyphRun, x: f32, text_len: usize) LineHit {
45 var pen: f32 = 0;
46 const map = run.clusterMap();
47 for (run.clusters, 0..) |cluster, cluster_index| {
48 const advance = clusterAdvance(run, cluster.glyphs);
49 if (x <= pen) {
50 const byte_offset = clampedSourceOffset(cluster.source.start, text_len);
51 return .{ .byte_offset = byte_offset, .advance = pen };
52 }
53 if (x < pen + advance) {
54 const stop = nearestEndpoint(map, cluster_index, x - pen, advance, text_len);
55 return .{ .byte_offset = stop.byte_offset, .advance = pen + stop.advance };
56 }
57 pen += advance;
58 }
59 return .{ .byte_offset = text_len, .advance = pen };
60 }
61
62 fn clampedSourceOffset(source_offset: u32, text_len: usize) usize {
63 return @min(@as(usize, @intCast(source_offset)), text_len);
64 }
65
66 fn advanceWithinCluster(map: shape.ClusterMap, cluster_index: usize, byte_offset: usize, advance: f32, text_len: usize) f32 {
67 const count = map.clusterCaretStopCount(cluster_index) orelse return midpointAdvance(byte_offset, cluster_index, map, advance, text_len);
68 if (count == 0) return 0;
69 var previous = stopInCluster(map, cluster_index, 0, advance, text_len);
70 if (byte_offset <= previous.byte_offset) return previous.advance;
71 var stop_index: usize = 1;
72 while (stop_index < count) : (stop_index += 1) {
73 const current = stopInCluster(map, cluster_index, stop_index, advance, text_len);
74 if (byte_offset == current.byte_offset) return current.advance;
75 if (byte_offset < current.byte_offset) {
76 const span = current.byte_offset - previous.byte_offset;
77 if (span == 0) return current.advance;
78 const numerator: f32 = @floatFromInt(byte_offset - previous.byte_offset);
79 const denominator: f32 = @floatFromInt(span);
80 return previous.advance + (current.advance - previous.advance) * (numerator / denominator);
81 }
82 previous = current;
83 }
84 return previous.advance;
85 }
86
87 fn midpointAdvance(byte_offset: usize, cluster_index: usize, map: shape.ClusterMap, advance: f32, text_len: usize) f32 {
88 const range = map.clusterSourceRange(cluster_index) orelse return 0;
89 const start = clampedSourceOffset(range.start, text_len);
90 const end = clampedSourceOffset(range.end, text_len);
91 if (end <= start) return 0;
92 if (byte_offset <= start) return 0;
93 if (byte_offset >= end) return advance;
94 const numerator: f32 = @floatFromInt(byte_offset - start);
95 const denominator: f32 = @floatFromInt(end - start);
96 return advance * (numerator / denominator);
97 }
98
99 fn nearestStopInCluster(map: shape.ClusterMap, cluster_index: usize, x: f32, advance: f32, text: []const u8) LineHit {
100 const count = map.clusterCaretStopCount(cluster_index) orelse 0;
101 if (count > 2) return nearestExplicitStopInCluster(map, cluster_index, x, advance, text.len);
102 const range = map.clusterSourceRange(cluster_index) orelse return .{ .byte_offset = text.len, .advance = advance };
103 const start = clampedSourceOffset(range.start, text.len);
104 const end = clampedSourceOffset(range.end, text.len);
105 const fraction = if (advance <= 0) @as(f32, 0) else std.math.clamp(x / advance, @as(f32, 0), @as(f32, 1));
106 const byte_offset = byteOffsetInGraphemeSegments(text, start, end, fraction);
107 return .{
108 .byte_offset = byte_offset,
109 .advance = advanceWithinCluster(map, cluster_index, byte_offset, advance, text.len),
110 };
111 }
112
113 fn nearestExplicitStopInCluster(map: shape.ClusterMap, cluster_index: usize, x: f32, advance: f32, text_len: usize) LineHit {
114 const count = map.clusterCaretStopCount(cluster_index) orelse 0;
115 var nearest = stopInCluster(map, cluster_index, 0, advance, text_len);
116 var nearest_distance = @abs(x - nearest.advance);
117 var stop_index: usize = 1;
118 while (stop_index < count) : (stop_index += 1) {
119 const stop = stopInCluster(map, cluster_index, stop_index, advance, text_len);
120 const distance = @abs(x - stop.advance);
121 if (distance < nearest_distance or (distance == nearest_distance and stop.byte_offset > nearest.byte_offset)) {
122 nearest = stop;
123 nearest_distance = distance;
124 }
125 }
126 return nearest;
127 }
128
129 fn nearestEndpoint(map: shape.ClusterMap, cluster_index: usize, x: f32, advance: f32, text_len: usize) LineHit {
130 const range = map.clusterSourceRange(cluster_index) orelse return .{ .byte_offset = text_len, .advance = advance };
131 const start = clampedSourceOffset(range.start, text_len);
132 const end = clampedSourceOffset(range.end, text_len);
133 if (x < advance * 0.5) return .{ .byte_offset = start, .advance = 0 };
134 return .{ .byte_offset = end, .advance = advance };
135 }
136
137 fn stopInCluster(map: shape.ClusterMap, cluster_index: usize, stop_index: usize, advance: f32, text_len: usize) LineHit {
138 const count = map.clusterCaretStopCount(cluster_index) orelse 0;
139 const stop = map.clusterCaretStop(cluster_index, stop_index) orelse 0;
140 if (stop_index == 0) {
141 return .{ .byte_offset = clampedSourceOffset(stop, text_len), .advance = 0 };
142 }
143 if (stop_index + 1 >= count) {
144 return .{ .byte_offset = clampedSourceOffset(stop, text_len), .advance = advance };
145 }
146 if (map.clusterLigatureCaret(cluster_index, stop_index - 1)) |caret| {
147 return .{
148 .byte_offset = clampedSourceOffset(stop, text_len),
149 .advance = @as(f32, @floatFromInt(caret.x_offset)) / 64.0,
150 };
151 }
152 const range = map.clusterSourceRange(cluster_index) orelse return .{ .byte_offset = clampedSourceOffset(stop, text_len), .advance = advance };
153 const start = clampedSourceOffset(range.start, text_len);
154 const end = clampedSourceOffset(range.end, text_len);
155 if (end <= start) return .{ .byte_offset = clampedSourceOffset(stop, text_len), .advance = 0 };
156 const relative = clampedSourceOffset(stop, text_len) - start;
157 const span = end - start;
158 return .{
159 .byte_offset = clampedSourceOffset(stop, text_len),
160 .advance = advance * (@as(f32, @floatFromInt(relative)) / @as(f32, @floatFromInt(span))),
161 };
162 }
163
164 fn byteOffsetInGraphemeSegments(text: []const u8, start: usize, end: usize, fraction: f32) usize {
165 if (end <= start) return start;
166 const safe_start = @min(start, text.len);
167 const safe_end = @min(@max(end, safe_start), text.len);
168 if (safe_end <= safe_start) return safe_start;
169
170 const segment_count = graphemeSegmentCount(text, safe_start, safe_end) catch return nearestEndpointByFraction(safe_start, safe_end, fraction);
171 if (segment_count == 0) return safe_start;
172 const target = @min(
173 @as(usize, @intFromFloat(@round(std.math.clamp(fraction, @as(f32, 0), @as(f32, 1)) * @as(f32, @floatFromInt(segment_count))))),
174 segment_count,
175 );
176 if (target == 0) return safe_start;
177 if (target >= segment_count) return safe_end;
178 return graphemeBoundaryAt(text, safe_start, safe_end, target) catch nearestEndpointByFraction(safe_start, safe_end, fraction);
179 }
180
181 fn graphemeSegmentCount(text: []const u8, start: usize, end: usize) !usize {
182 var iterator = try unicode.SourceIterator.init(.{ .utf8 = text[start..end] }, @intCast(start));
183 var state: unicode.GraphemeState = .{};
184 var count: usize = 0;
185 while (try iterator.next()) |scalar| {
186 if (!state.consume(scalar.codepoint)) count += 1;
187 }
188 return count;
189 }
190
191 fn graphemeBoundaryAt(text: []const u8, start: usize, end: usize, target: usize) !usize {
192 var iterator = try unicode.SourceIterator.init(.{ .utf8 = text[start..end] }, @intCast(start));
193 var state: unicode.GraphemeState = .{};
194 var index: usize = 0;
195 while (try iterator.next()) |scalar| {
196 if (!state.consume(scalar.codepoint)) {
197 if (index == target) return @intCast(scalar.source.start);
198 index += 1;
199 }
200 }
201 return end;
202 }
203
204 fn nearestEndpointByFraction(start: usize, end: usize, fraction: f32) usize {
205 if (fraction < 0.5) return start;
206 return end;
207 }
208
209 fn clusterAdvance(run: shape.GlyphRun, span: shape.GlyphSpan) f32 {
210 var advance: f32 = 0;
211 var index: usize = @intCast(span.start);
212 const end: usize = @min(@as(usize, @intCast(span.end)), run.glyphs.len);
213 while (index < end) : (index += 1) {
214 advance += @as(f32, @floatFromInt(run.glyphs[index].x_advance)) / 64.0;
215 }
216 return advance;
217 }
218
219 test "caret hit test chooses grapheme boundaries inside clusters" {
220 const glyphs = [_]shape.ShapedGlyph{
221 .{ .glyph_id = 1, .cluster = 0, .cluster_index = 0, .source_start = 0, .source_end = 2, .source_codepoint_count = 2, .x_advance = 1152, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
222 .{ .glyph_id = 2, .cluster = 2, .cluster_index = 1, .source_start = 2, .source_end = 3, .x_advance = 576, .y_advance = 0, .x_offset = 0, .y_offset = 0 },
223 };
224 const clusters = [_]shape.Cluster{
225 .{ .source = .{ .start = 0, .end = 2 }, .glyphs = .{ .start = 0, .end = 1 }, .codepoint_count = 2 },
226 .{ .source = .{ .start = 2, .end = 3 }, .glyphs = .{ .start = 1, .end = 2 } },
227 };
228 const run = shape.GlyphRun{
229 .glyphs = &glyphs,
230 .clusters = &clusters,
231 .ligature_carets = &.{},
232 .total_x_advance = 1728,
233 .total_y_advance = 0,
234 .direction = .ltr,
235 .writing_mode = .horizontal,
236 .output_order = .visual,
237 };
238
239 try std.testing.expectEqual(@as(f32, 0), advanceForByteOffset(run, 0, 3));
240 try std.testing.expectEqual(@as(f32, 9), advanceForByteOffset(run, 1, 3));
241 try std.testing.expectEqual(@as(f32, 18), advanceForByteOffset(run, 2, 3));
242 try std.testing.expectEqual(@as(f32, 27), advanceForByteOffset(run, 3, 3));
243 try std.testing.expectEqual(LineHit{ .byte_offset = 0, .advance = 0 }, hitTestAdvance(run, 4.4, "=>x"));
244 try std.testing.expectEqual(LineHit{ .byte_offset = 1, .advance = 9 }, hitTestAdvance(run, 9, "=>x"));
245 try std.testing.expectEqual(LineHit{ .byte_offset = 2, .advance = 18 }, hitTestAdvance(run, 16, "=>x"));
246 try std.testing.expectEqual(LineHit{ .byte_offset = 3, .advance = 27 }, hitTestAdvance(run, 24, "=>x"));
247 }
248
249 test "caret hit test uses ligature stops" {
250 const glyphs = [_]shape.ShapedGlyph{
251 .{
252 .glyph_id = 9,
253 .cluster = 0,
254 .cluster_index = 0,
255 .source_start = 0,
256 .source_end = 2,
257 .source_codepoint_count = 2,
258 .x_advance = 640,
259 .y_advance = 0,
260 .x_offset = 0,
261 .y_offset = 0,
262 .glyph_class = .ligature,
263 .ligature_caret_start = 0,
264 .ligature_caret_count = 1,
265 },
266 };
267 const clusters = [_]shape.Cluster{
268 .{ .source = .{ .start = 0, .end = 2 }, .glyphs = .{ .start = 0, .end = 1 }, .codepoint_count = 2 },
269 };
270 const carets = [_]shape.LigatureCaret{
271 .{ .x_offset = 384 },
272 };
273 const run = shape.GlyphRun{
274 .glyphs = &glyphs,
275 .clusters = &clusters,
276 .ligature_carets = &carets,
277 .total_x_advance = 640,
278 .total_y_advance = 0,
279 .direction = .ltr,
280 .writing_mode = .horizontal,
281 .output_order = .visual,
282 };
283
284 try std.testing.expectEqual(@as(f32, 6), advanceForByteOffset(run, 1, 2));
285 try std.testing.expectEqual(LineHit{ .byte_offset = 1, .advance = 6 }, hitTestAdvance(run, 5.1, "fi"));
286 try std.testing.expectEqual(LineHit{ .byte_offset = 2, .advance = 10 }, hitTestAdvance(run, 8.3, "fi"));
287 }
288
289 test "caret hit test uses OpenType GDEF ligature stops" {
290 const text = "fi";
291 const bytes = try fixtures.createWithGsubLigatureAndGdefCarets(std.testing.allocator);
292 defer std.testing.allocator.free(bytes);
293
294 var shaper = shape.Font.initFromBytes(bytes.ptr, bytes.len) orelse return error.TestUnexpectedResult;
295 defer shaper.deinit();
296 shaper.setPixelHeightScale(20);
297
298 var context = shape.Context.init(std.testing.allocator, .{});
299 defer context.deinit();
300
301 var output = try shape.Output.init(std.testing.allocator, .{
302 .max_glyphs = 256,
303 .max_ligature_carets = 256,
304 });
305 defer output.deinit(std.testing.allocator);
306
307 try context.shapeRun(.{ .font = &shaper, .text = .{ .utf8 = text } }, &output);
308 const run = output.run();
309 const map = run.clusterMap();
310 const caret = map.clusterLigatureCaret(0, 0).?;
311
312 try std.testing.expectEqual(@as(usize, 1), run.glyphs.len);
313 try std.testing.expectEqual(@as(usize, 1), run.ligature_carets.len);
314 try std.testing.expectEqual(false, caret.synthesized);
315 try std.testing.expectEqual(@as(f32, 5), advanceForByteOffset(run, 1, text.len));
316 try std.testing.expectEqual(LineHit{ .byte_offset = 1, .advance = 5 }, hitTestAdvance(run, 4.6, text));
317 try std.testing.expectEqual(LineHit{ .byte_offset = 2, .advance = 10 }, hitTestAdvance(run, 7.6, text));
318 }