/work/workdir/UnpackedTarball/harfbuzz/src/hb-depend-data.hh
Line | Count | Source |
1 | | /* |
2 | | * Copyright © 2024 Adobe, Inc. |
3 | | * |
4 | | * This is part of HarfBuzz, a text shaping library. |
5 | | * |
6 | | * Permission is hereby granted, without written agreement and without |
7 | | * license or royalty fees, to use, copy, modify, and distribute this |
8 | | * software and its documentation for any purpose, provided that the |
9 | | * above copyright notice and the following two paragraphs appear in |
10 | | * all copies of this software. |
11 | | * |
12 | | * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR |
13 | | * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES |
14 | | * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN |
15 | | * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH |
16 | | * DAMAGE. |
17 | | * |
18 | | * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, |
19 | | * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND |
20 | | * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS |
21 | | * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO |
22 | | * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. |
23 | | * |
24 | | * Adobe Author(s): Skef Iterum |
25 | | */ |
26 | | |
27 | | #ifndef HB_DEPEND_DATA_HH |
28 | | #define HB_DEPEND_DATA_HH |
29 | | |
30 | | /* This file exists to break include cycles: hb-ot-layout-gsubgpos.hh needs |
31 | | * hb_depend_data_builder_t for hb_depend_context_t, but hb-depend.hh pulls |
32 | | * in table headers that include hb-ot-layout-gsubgpos.hh. */ |
33 | | |
34 | | #include "hb.hh" |
35 | | |
36 | | #include "hb-multimap.hh" |
37 | | |
38 | | /* hb_subset_depend_edge_flags_t is defined in hb-depend.h (public header). |
39 | | * We redeclare it here under the same include-guard so internal code that |
40 | | * includes hb-depend-data.hh without going through hb-depend.h still gets |
41 | | * the type. The definitions must stay in sync. */ |
42 | | #ifndef HB_SUBSET_DEPEND_EDGE_FLAGS_T_DEFINED |
43 | | #define HB_SUBSET_DEPEND_EDGE_FLAGS_T_DEFINED |
44 | | typedef enum { |
45 | | HB_SUBSET_DEPEND_EDGE_FLAG_NONE = 0x00u, |
46 | | HB_SUBSET_DEPEND_EDGE_FLAG_FROM_CONTEXT_POSITION = 0x01u, |
47 | | HB_SUBSET_DEPEND_EDGE_FLAG_FROM_NESTED_CONTEXT = 0x02u, |
48 | | } hb_subset_depend_edge_flags_t; |
49 | | #endif |
50 | | /* Apply operator overloads now that hb.hh (and thus hb-algs.hh) is available. */ |
51 | | HB_MARK_AS_FLAG_T (hb_subset_depend_edge_flags_t); |
52 | | |
53 | | /* High bit of a context-set element marks it as an index into the sets array |
54 | | * rather than a raw glyph ID. */ |
55 | | #define HB_DEPEND_CONTEXT_SET_FLAG 0x80000000u |
56 | | |
57 | | /** |
58 | | * hb_depend_edge_t: |
59 | | * |
60 | | * Internal structure representing a single dependency edge in the graph. |
61 | | * Records that glyph A depends on glyph B through a specific OpenType |
62 | | * mechanism (table_tag), with additional metadata: |
63 | | * |
64 | | * - table_tag: Source table (GSUB, glyf, CFF, COLR, MATH, VARC) |
65 | | * - dependent: Target glyph ID |
66 | | * - layout_tag: Feature tag (for GSUB), else 0 |
67 | | * - ligature_set: Index into sets array for ligature components, else INVALID |
68 | | * - context_set: Index into sets array for context requirements, else INVALID |
69 | | * - flags: Edge flags (FROM_CONTEXT_POSITION, FROM_NESTED_CONTEXT) |
70 | | */ |
71 | | struct hb_depend_edge_t { |
72 | | hb_depend_edge_t() = delete; |
73 | | hb_depend_edge_t(hb_tag_t table_tag, |
74 | | hb_codepoint_t dependent, |
75 | | hb_tag_t layout_tag, |
76 | | hb_codepoint_t ligature_set, |
77 | | hb_codepoint_t context_set, |
78 | 0 | hb_subset_depend_edge_flags_t flags = HB_SUBSET_DEPEND_EDGE_FLAG_NONE) : table_tag(table_tag), |
79 | 0 | dependent(dependent), layout_tag(layout_tag), |
80 | 0 | ligature_set(ligature_set), context_set(context_set), |
81 | 0 | flags(flags) |
82 | 0 | {} |
83 | | |
84 | | bool operator == (const hb_depend_edge_t &o) const |
85 | 0 | { |
86 | | /* NOTE: flags intentionally excluded from equality comparison. |
87 | | * Flags are metadata about how an edge was discovered (e.g., |
88 | | * FROM_CONTEXT_POSITION, FROM_NESTED_CONTEXT), not part of the |
89 | | * edge's identity. Multiple discoveries of the same edge via |
90 | | * different paths should be treated as duplicates. */ |
91 | 0 | return table_tag == o.table_tag && |
92 | 0 | dependent == o.dependent && |
93 | 0 | layout_tag == o.layout_tag && |
94 | 0 | ligature_set == o.ligature_set && |
95 | 0 | context_set == o.context_set; |
96 | 0 | } |
97 | | |
98 | | uint32_t hash () const |
99 | 0 | { |
100 | | /* FNV-1a hash of all identity fields (excludes flags) */ |
101 | 0 | uint32_t current = 0x84222325; /* FNV-1a offset basis */ |
102 | 0 | current = current ^ hb_hash (table_tag); |
103 | 0 | current = current * 16777619; /* FNV-1a prime */ |
104 | 0 | current = current ^ hb_hash (dependent); |
105 | 0 | current = current * 16777619; |
106 | 0 | current = current ^ hb_hash (layout_tag); |
107 | 0 | current = current * 16777619; |
108 | 0 | current = current ^ hb_hash (ligature_set); |
109 | 0 | current = current * 16777619; |
110 | 0 | current = current ^ hb_hash (context_set); |
111 | 0 | current = current * 16777619; |
112 | 0 | return current; |
113 | 0 | } |
114 | | |
115 | | hb_tag_t table_tag; |
116 | | hb_codepoint_t dependent; |
117 | | hb_tag_t layout_tag; |
118 | | hb_codepoint_t ligature_set; |
119 | | hb_codepoint_t context_set; |
120 | | hb_subset_depend_edge_flags_t flags; |
121 | | }; |
122 | | |
123 | | /** |
124 | | * hb_depend_edge_key_t: |
125 | | * |
126 | | * Key structure for edge deduplication. Combines source glyph with edge record. |
127 | | * Uses the record's equality and hash operators for comparison. |
128 | | */ |
129 | | struct hb_depend_edge_key_t { |
130 | | hb_codepoint_t source; |
131 | | hb_depend_edge_t record; |
132 | | |
133 | 0 | hb_depend_edge_key_t () : source (0), record (0, 0, 0, HB_CODEPOINT_INVALID, HB_CODEPOINT_INVALID, HB_SUBSET_DEPEND_EDGE_FLAG_NONE) {} |
134 | | |
135 | | hb_depend_edge_key_t (hb_codepoint_t source, |
136 | | hb_tag_t table_tag, |
137 | | hb_tag_t layout_tag, |
138 | | hb_codepoint_t dependent, |
139 | | hb_codepoint_t ligature_set, |
140 | | hb_codepoint_t context_set) |
141 | 0 | : source (source), |
142 | 0 | record (table_tag, dependent, layout_tag, ligature_set, context_set, HB_SUBSET_DEPEND_EDGE_FLAG_NONE) {} |
143 | | |
144 | | bool operator == (const hb_depend_edge_key_t &o) const |
145 | 0 | { |
146 | 0 | return source == o.source && record == o.record; |
147 | 0 | } |
148 | | |
149 | | uint32_t hash () const |
150 | 0 | { |
151 | | /* Combine source hash with record hash */ |
152 | 0 | uint32_t current = 0x84222325; /* FNV-1a offset basis */ |
153 | 0 | current = current ^ hb_hash (source); |
154 | 0 | current = current * 16777619; /* FNV-1a prime */ |
155 | 0 | current = current ^ record.hash (); |
156 | 0 | current = current * 16777619; |
157 | 0 | return current; |
158 | 0 | } |
159 | | }; |
160 | | |
161 | | /** |
162 | | * hb_depend_glyph_record_t: |
163 | | * |
164 | | * Internal structure holding all dependency edges for a single glyph. |
165 | | */ |
166 | | struct hb_depend_glyph_record_t { |
167 | | hb_vector_t<hb_depend_edge_t> dependencies; |
168 | | }; |
169 | | |
170 | | /** |
171 | | * hb_depend_lookup_revmap_t: |
172 | | * |
173 | | * Internal structure tracking which features are associated with a lookup. |
174 | | * Used during GSUB dependency analysis to record the feature tags that |
175 | | * activate each lookup. |
176 | | */ |
177 | | struct hb_depend_lookup_revmap_t |
178 | | { |
179 | | hb_depend_lookup_revmap_t () = default; |
180 | 0 | explicit hb_depend_lookup_revmap_t (bool full) : full (full) {} |
181 | | hb_depend_lookup_revmap_t (const hb_depend_lookup_revmap_t &o) : full(o.full), |
182 | 0 | fv_indexes(o.fv_indexes) {} |
183 | | hb_depend_lookup_revmap_t (hb_depend_lookup_revmap_t &&o) : full(o.full), |
184 | 0 | fv_indexes(std::move(o.fv_indexes)) {} |
185 | | hb_depend_lookup_revmap_t& operator = (const hb_depend_lookup_revmap_t &o) |
186 | 0 | { |
187 | 0 | full = o.full; |
188 | 0 | fv_indexes = o.fv_indexes; |
189 | 0 | return *this; |
190 | 0 | } |
191 | | |
192 | | bool full = true; |
193 | | hb_set_t fv_indexes; |
194 | | }; |
195 | | |
196 | | /** |
197 | | * hb_depend_data_t: |
198 | | * |
199 | | * Persistent dependency graph data, retained for the lifetime of hb_subset_depend_t. |
200 | | * Contains only what is needed at query time: |
201 | | * - glyph_dependencies: Per-glyph edge lists |
202 | | * - sets: Ligature and context sets indexed by set ID |
203 | | * |
204 | | * Constructed via hb_depend_data_builder_t; immutable thereafter. |
205 | | */ |
206 | | struct hb_depend_data_t |
207 | | { |
208 | | /* Set storage: vector of heap-allocated sets (both ligature and context sets). |
209 | | * Using unique_ptr follows HarfBuzz pattern and provides stable pointers. */ |
210 | | hb_vector_t<hb::unique_ptr<hb_set_t>> sets; |
211 | | |
212 | | hb_vector_t<hb_depend_glyph_record_t> glyph_dependencies; |
213 | | |
214 | | const hb_set_t *get_set_from_index (hb_codepoint_t index) |
215 | 0 | { |
216 | 0 | if (index < sets.length) |
217 | 0 | return sets[index].get (); |
218 | 0 | return nullptr; |
219 | 0 | } |
220 | | |
221 | | unsigned int get_glyph_entry_count (hb_codepoint_t gid) const |
222 | 0 | { |
223 | 0 | if (gid < glyph_dependencies.length) |
224 | 0 | return glyph_dependencies[gid].dependencies.length; |
225 | 0 | return 0; |
226 | 0 | } |
227 | | |
228 | | bool get_glyph_entry (hb_codepoint_t gid, unsigned int index, |
229 | | hb_tag_t *table_tag, hb_codepoint_t *dependent, |
230 | | hb_tag_t *layout_tag, hb_codepoint_t *ligature_set, |
231 | | hb_codepoint_t *context_set, uint8_t *flags) |
232 | 0 | { |
233 | 0 | if (gid < glyph_dependencies.length && |
234 | 0 | index < glyph_dependencies[gid].dependencies.length) { |
235 | 0 | auto &d = glyph_dependencies[gid].dependencies[index]; |
236 | 0 | *table_tag = d.table_tag; |
237 | 0 | *dependent = d.dependent; |
238 | 0 | *layout_tag = d.layout_tag; |
239 | 0 | *ligature_set = d.ligature_set; |
240 | 0 | *context_set = d.context_set; |
241 | 0 | if (flags) *flags = d.flags; |
242 | 0 | return true; |
243 | 0 | } |
244 | 0 | return false; |
245 | 0 | } |
246 | | |
247 | | void print () |
248 | 0 | { |
249 | 0 | for (unsigned i = 0; i < glyph_dependencies.length; i++) { |
250 | 0 | auto &gd = glyph_dependencies[i]; |
251 | 0 | if (!gd.dependencies.length) |
252 | 0 | continue; |
253 | 0 | printf ("GID %u:\n", i); |
254 | 0 | for (auto &d : gd.dependencies) { |
255 | 0 | if (d.table_tag == HB_OT_TAG_GSUB) { |
256 | 0 | printf (" layout %c%c%c%c -> %u", HB_UNTAG(d.layout_tag), d.dependent); |
257 | 0 | if (d.ligature_set != HB_CODEPOINT_INVALID) |
258 | 0 | printf (" (ligature)"); |
259 | 0 | } else { |
260 | 0 | printf (" %c%c%c%c -> %u", HB_UNTAG(d.table_tag), d.dependent); |
261 | 0 | } |
262 | 0 | printf ("\n"); |
263 | 0 | } |
264 | 0 | } |
265 | 0 | } |
266 | | }; |
267 | | |
268 | | /** |
269 | | * hb_depend_data_builder_t: |
270 | | * |
271 | | * Temporary builder for constructing hb_depend_data_t. Holds all state |
272 | | * needed during graph extraction; goes out of scope (and is freed) when |
273 | | * construction is complete, leaving only hb_depend_data_t. |
274 | | * |
275 | | * Temporary state (freed on destruction): |
276 | | * - lookup_features: Packed lookup index to feature tag mapping |
277 | | * - lookup_feature_offsets: Per-lookup offsets into lookup_features |
278 | | * - edge_slots: Compact edge deduplication table |
279 | | * - set_to_index: Content-based dependency set deduplication map |
280 | | * - free_set_list: Indices of freed sets available for reuse |
281 | | * - current_context_set_index: Context requirements for current rule |
282 | | * - current_edge_flags: Flags to apply to edges being recorded |
283 | | */ |
284 | | struct hb_depend_data_builder_t |
285 | | { |
286 | | hb_depend_data_builder_t (hb_depend_data_t &data_) |
287 | | : current_context_set_index (HB_CODEPOINT_INVALID), |
288 | | current_edge_flags (HB_SUBSET_DEPEND_EDGE_FLAG_NONE), |
289 | 0 | data (data_) {} |
290 | | |
291 | | /* Forward to data for use during construction (e.g. from hb_depend_context_t) */ |
292 | | const hb_set_t *get_set_from_index (hb_codepoint_t index) |
293 | 0 | { return data.get_set_from_index (index); } |
294 | | |
295 | | /* Discard an unused set that was allocated but had no edges added. */ |
296 | | void discard_set (hb_codepoint_t set_index) |
297 | 0 | { |
298 | 0 | if (set_index >= data.sets.length) |
299 | 0 | { |
300 | 0 | DEBUG_MSG (SUBSET, nullptr, "Attempting to discard invalid set %u (max is %u)", |
301 | 0 | set_index, data.sets.length - 1); |
302 | 0 | return; |
303 | 0 | } |
304 | 0 | set_to_index.del (data.sets[set_index].get ()); |
305 | 0 | data.sets[set_index]->clear (); |
306 | 0 | check_success (free_set_list.push_or_fail (set_index)); |
307 | 0 | } |
308 | | |
309 | | hb_codepoint_t new_set (const hb_set_t &set) |
310 | 0 | { |
311 | 0 | hb_codepoint_t set_index; |
312 | 0 |
|
313 | 0 | if (free_set_list.length > 0) |
314 | 0 | { |
315 | 0 | set_index = free_set_list.pop (); |
316 | 0 | data.sets[set_index]->set (set); |
317 | 0 | if (unlikely (data.sets[set_index]->in_error ())) |
318 | 0 | return fail_invalid (); |
319 | 0 | } |
320 | 0 | else |
321 | 0 | { |
322 | 0 | set_index = data.sets.length; |
323 | 0 | hb_set_t *new_set = hb_set_create (); |
324 | 0 | if (unlikely (!new_set)) |
325 | 0 | return fail_invalid (); |
326 | 0 | new_set->set (set); |
327 | 0 | if (unlikely (new_set->in_error ())) |
328 | 0 | { |
329 | 0 | hb_set_destroy (new_set); |
330 | 0 | return fail_invalid (); |
331 | 0 | } |
332 | 0 | if (unlikely (!data.sets.push_or_fail (hb::unique_ptr<hb_set_t> {new_set}))) |
333 | 0 | return fail_invalid (); |
334 | 0 | } |
335 | 0 |
|
336 | 0 | return set_index; |
337 | 0 | } |
338 | | |
339 | | /* Find an existing dependency set with the same contents, or create one. */ |
340 | | hb_codepoint_t find_or_create_set (const hb_set_t &set, bool *created = nullptr) |
341 | 0 | { |
342 | 0 | hb_codepoint_t *existing_idx = nullptr; |
343 | 0 | if (set_to_index.has (&set, &existing_idx)) |
344 | 0 | { |
345 | 0 | if (created) *created = false; |
346 | 0 | return *existing_idx; |
347 | 0 | } |
348 | 0 |
|
349 | 0 | hb_codepoint_t new_idx = new_set (set); |
350 | 0 | if (unlikely (new_idx == HB_CODEPOINT_INVALID)) |
351 | 0 | return HB_CODEPOINT_INVALID; |
352 | 0 |
|
353 | 0 | if (unlikely (!set_to_index.set (data.sets[new_idx].get (), new_idx))) |
354 | 0 | return fail_invalid (); |
355 | 0 | if (created) *created = true; |
356 | 0 | return new_idx; |
357 | 0 | } |
358 | | |
359 | | hb_codepoint_t find_or_create_context_set (const hb_set_t &set) |
360 | 0 | { return find_or_create_set (set); } |
361 | | |
362 | | /* Build a context set from context information. |
363 | | * Encodes backtrack and lookahead requirements as a flattened set. |
364 | | * Returns HB_CODEPOINT_INVALID if no context. |
365 | | * |
366 | | * To ensure canonical encoding and avoid redundancy: |
367 | | * 1. First pass: collect all direct (single-glyph) requirements |
368 | | * 2. Second pass: create disjunction sets, subtracting direct requirements |
369 | | * 3. Combine: add direct requirements and filtered disjunction references |
370 | | */ |
371 | | hb_codepoint_t build_context_set (const hb_vector_t<hb_set_t> *backtrack_sets, |
372 | | const hb_vector_t<hb_set_t> *lookahead_sets) |
373 | 0 | { |
374 | 0 | if ((!backtrack_sets || backtrack_sets->length == 0) && |
375 | 0 | (!lookahead_sets || lookahead_sets->length == 0)) |
376 | 0 | return HB_CODEPOINT_INVALID; |
377 | 0 |
|
378 | 0 | /* First pass: collect all direct (single-glyph) requirements */ |
379 | 0 | hb_set_t direct_requirements; |
380 | 0 |
|
381 | 0 | if (backtrack_sets) |
382 | 0 | { |
383 | 0 | for (const auto &back_set : *backtrack_sets) |
384 | 0 | { |
385 | 0 | if (back_set.get_population () == 1) |
386 | 0 | direct_requirements.add (back_set.get_min ()); |
387 | 0 | } |
388 | 0 | } |
389 | 0 |
|
390 | 0 | if (lookahead_sets) |
391 | 0 | { |
392 | 0 | for (const auto &look_set : *lookahead_sets) |
393 | 0 | { |
394 | 0 | if (look_set.get_population () == 1) |
395 | 0 | direct_requirements.add (look_set.get_min ()); |
396 | 0 | } |
397 | 0 | } |
398 | 0 |
|
399 | 0 | /* Second pass: create disjunction sets, filtering out direct requirements */ |
400 | 0 | hb_set_t context_elements; |
401 | 0 |
|
402 | 0 | if (backtrack_sets) |
403 | 0 | { |
404 | 0 | for (const auto &back_set : *backtrack_sets) |
405 | 0 | { |
406 | 0 | if (back_set.get_population () > 1) |
407 | 0 | { |
408 | 0 | hb_set_t filtered_set; |
409 | 0 | filtered_set.set (back_set); |
410 | 0 | filtered_set.subtract (direct_requirements); |
411 | 0 | if (unlikely (filtered_set.in_error ())) |
412 | 0 | return fail_invalid (); |
413 | 0 |
|
414 | 0 | if (!filtered_set.is_empty ()) |
415 | 0 | { |
416 | 0 | hb_codepoint_t set_idx = find_or_create_context_set (filtered_set); |
417 | 0 | if (unlikely (set_idx == HB_CODEPOINT_INVALID)) |
418 | 0 | return HB_CODEPOINT_INVALID; |
419 | 0 | context_elements.add (HB_DEPEND_CONTEXT_SET_FLAG | set_idx); |
420 | 0 | } |
421 | 0 | } |
422 | 0 | } |
423 | 0 | } |
424 | 0 |
|
425 | 0 | if (lookahead_sets) |
426 | 0 | { |
427 | 0 | for (const auto &look_set : *lookahead_sets) |
428 | 0 | { |
429 | 0 | if (look_set.get_population () > 1) |
430 | 0 | { |
431 | 0 | hb_set_t filtered_set; |
432 | 0 | filtered_set.set (look_set); |
433 | 0 | filtered_set.subtract (direct_requirements); |
434 | 0 | if (unlikely (filtered_set.in_error ())) |
435 | 0 | return fail_invalid (); |
436 | 0 |
|
437 | 0 | if (!filtered_set.is_empty ()) |
438 | 0 | { |
439 | 0 | hb_codepoint_t set_idx = find_or_create_context_set (filtered_set); |
440 | 0 | if (unlikely (set_idx == HB_CODEPOINT_INVALID)) |
441 | 0 | return HB_CODEPOINT_INVALID; |
442 | 0 | context_elements.add (HB_DEPEND_CONTEXT_SET_FLAG | set_idx); |
443 | 0 | } |
444 | 0 | } |
445 | 0 | } |
446 | 0 | } |
447 | 0 |
|
448 | 0 | context_elements.union_ (direct_requirements); |
449 | 0 | if (unlikely (direct_requirements.in_error () || |
450 | 0 | context_elements.in_error ())) |
451 | 0 | return fail_invalid (); |
452 | 0 |
|
453 | 0 | if (context_elements.is_empty ()) |
454 | 0 | return HB_CODEPOINT_INVALID; |
455 | 0 |
|
456 | 0 | return find_or_create_context_set (context_elements); |
457 | 0 | } |
458 | | |
459 | | static uint64_t encode_edge_ref (hb_codepoint_t source, unsigned int index) |
460 | 0 | { return (uint64_t (source) + 1) << 32 | index; } |
461 | | |
462 | | static void decode_edge_ref (uint64_t ref, |
463 | | hb_codepoint_t *source, |
464 | | unsigned int *index) |
465 | 0 | { |
466 | 0 | *source = (ref >> 32) - 1; |
467 | 0 | *index = ref; |
468 | 0 | } |
469 | | |
470 | | uint32_t edge_hash (hb_codepoint_t source, const hb_depend_edge_t &record) const |
471 | 0 | { |
472 | 0 | hb_depend_edge_key_t key (source, record.table_tag, record.layout_tag, |
473 | 0 | record.dependent, record.ligature_set, |
474 | 0 | record.context_set); |
475 | 0 | return key.hash (); |
476 | 0 | } |
477 | | |
478 | | bool resize_edge_slots () |
479 | 0 | { |
480 | 0 | unsigned int new_size = edge_slots.length ? edge_slots.length * 2 : 8; |
481 | 0 | if (unlikely (new_size < edge_slots.length)) |
482 | 0 | return fail (); |
483 | | |
484 | 0 | hb_vector_t<uint64_t> new_slots; |
485 | 0 | if (unlikely (!new_slots.resize_exact (new_size))) |
486 | 0 | return fail (); |
487 | | |
488 | 0 | for (uint64_t ref : edge_slots) |
489 | 0 | { |
490 | 0 | if (!ref) |
491 | 0 | continue; |
492 | | |
493 | 0 | hb_codepoint_t source; |
494 | 0 | unsigned int index; |
495 | 0 | decode_edge_ref (ref, &source, &index); |
496 | 0 | const hb_depend_edge_t &record = data.glyph_dependencies[source].dependencies[index]; |
497 | 0 | unsigned int slot = edge_hash (source, record) & (new_size - 1); |
498 | 0 | unsigned int step = 0; |
499 | 0 | while (new_slots[slot]) |
500 | 0 | slot = (slot + ++step) & (new_size - 1); |
501 | 0 | new_slots[slot] = ref; |
502 | 0 | } |
503 | |
|
504 | 0 | edge_slots = std::move (new_slots); |
505 | 0 | return true; |
506 | 0 | } |
507 | | |
508 | | bool add_edge (hb_codepoint_t source, const hb_depend_edge_t &record) |
509 | 0 | { |
510 | | /* Store only a source and per-glyph edge index in each bucket. The edge |
511 | | * itself already lives in the output vector, where it can be compared to |
512 | | * resolve hash collisions exactly. Adding one to the encoded source |
513 | | * reserves zero as the empty-bucket value. */ |
514 | 0 | if (unlikely (!edge_slots.length || |
515 | 0 | uint64_t (edge_population) * 3 / 2 >= edge_slots.length - 1)) |
516 | 0 | if (unlikely (!resize_edge_slots ())) |
517 | 0 | return false; |
518 | | |
519 | 0 | unsigned int slot = edge_hash (source, record) & (edge_slots.length - 1); |
520 | 0 | unsigned int step = 0; |
521 | 0 | while (uint64_t ref = edge_slots[slot]) |
522 | 0 | { |
523 | 0 | hb_codepoint_t existing_source; |
524 | 0 | unsigned int existing_index; |
525 | 0 | decode_edge_ref (ref, &existing_source, &existing_index); |
526 | 0 | if (existing_source == source && |
527 | 0 | data.glyph_dependencies[source].dependencies[existing_index] == record) |
528 | 0 | return false; |
529 | 0 | slot = (slot + ++step) & (edge_slots.length - 1); |
530 | 0 | } |
531 | | |
532 | 0 | auto &dependencies = data.glyph_dependencies[source].dependencies; |
533 | 0 | unsigned int index = dependencies.length; |
534 | 0 | if (unlikely (!dependencies.push_or_fail (record))) |
535 | 0 | return fail (); |
536 | | |
537 | 0 | edge_slots[slot] = encode_edge_ref (source, index); |
538 | 0 | edge_population++; |
539 | 0 | return true; |
540 | 0 | } |
541 | | |
542 | | bool add_depend_layout (hb_codepoint_t target, hb_tag_t table_tag, |
543 | | hb_tag_t layout_tag, |
544 | | hb_codepoint_t dependent, |
545 | | hb_codepoint_t lig_set = HB_CODEPOINT_INVALID, |
546 | | hb_codepoint_t context_set = HB_CODEPOINT_INVALID, |
547 | | hb_subset_depend_edge_flags_t flags = HB_SUBSET_DEPEND_EDGE_FLAG_NONE) |
548 | 0 | { |
549 | 0 | if (target >= data.glyph_dependencies.length) { |
550 | 0 | DEBUG_MSG (SUBSET, nullptr, "Dependency glyph %u for %c%c%c%c too large", |
551 | 0 | target, HB_UNTAG(table_tag)); |
552 | 0 | return false; |
553 | 0 | } |
554 | | |
555 | 0 | return add_edge (target, hb_depend_edge_t (table_tag, dependent, layout_tag, |
556 | 0 | lig_set, context_set, flags)); |
557 | 0 | } |
558 | | |
559 | | bool add_gsub_lookup (hb_codepoint_t target, hb_codepoint_t lookup_index, |
560 | | hb_codepoint_t dependent, |
561 | | hb_codepoint_t lig_set = HB_CODEPOINT_INVALID, |
562 | | hb_codepoint_t context_set = HB_CODEPOINT_INVALID) |
563 | 0 | { |
564 | 0 | if (context_set == HB_CODEPOINT_INVALID) |
565 | 0 | context_set = current_context_set_index; |
566 | 0 | hb_subset_depend_edge_flags_t flags = current_edge_flags; |
567 | 0 |
|
568 | 0 | bool any_added = false; |
569 | 0 | for (uint64_t entry : get_lookup_features (lookup_index)) { |
570 | 0 | hb_tag_t t = (hb_tag_t) entry; |
571 | 0 | if (add_depend_layout (target, HB_OT_TAG_GSUB, t, dependent, lig_set, context_set, flags)) |
572 | 0 | any_added = true; |
573 | 0 | } |
574 | 0 | return any_added; |
575 | 0 | } |
576 | | |
577 | | bool init_lookup_features (unsigned lookup_count) |
578 | 0 | { |
579 | 0 | return check_success (lookup_feature_offsets.resize (lookup_count + 1)); |
580 | 0 | } |
581 | | |
582 | | bool add_lookup_feature (hb_codepoint_t lookup_index, hb_tag_t feature_tag) |
583 | 0 | { |
584 | 0 | if (feature_tag == HB_SET_VALUE_INVALID) |
585 | 0 | return true; |
586 | 0 |
|
587 | 0 | if (unlikely (!lookup_feature_offsets.length || |
588 | 0 | lookup_index >= lookup_feature_offsets.length - 1)) |
589 | 0 | return fail (); |
590 | 0 |
|
591 | 0 | uint64_t entry = ((uint64_t) lookup_index << 32) | feature_tag; |
592 | 0 | return check_success (lookup_features.push_or_fail (entry)); |
593 | 0 | } |
594 | | |
595 | | bool finish_lookup_features () |
596 | 0 | { |
597 | 0 | lookup_features.qsort ([] (uint64_t a, uint64_t b) { |
598 | 0 | return a < b ? -1 : a > b ? 1 : 0; |
599 | 0 | }); |
600 | 0 |
|
601 | 0 | unsigned write = 0; |
602 | 0 | for (uint64_t entry : lookup_features) |
603 | 0 | if (!write || entry != lookup_features[write - 1]) |
604 | 0 | lookup_features[write++] = entry; |
605 | 0 | lookup_features.shrink (write, false); |
606 | 0 |
|
607 | 0 | unsigned feature_index = 0; |
608 | 0 | unsigned lookup_count = lookup_feature_offsets.length - 1; |
609 | 0 | for (unsigned lookup_index = 0; lookup_index < lookup_count; lookup_index++) |
610 | 0 | { |
611 | 0 | lookup_feature_offsets[lookup_index] = feature_index; |
612 | 0 | while (feature_index < lookup_features.length && |
613 | 0 | lookup_features[feature_index] >> 32 == lookup_index) |
614 | 0 | feature_index++; |
615 | 0 | } |
616 | 0 | lookup_feature_offsets[lookup_count] = feature_index; |
617 | 0 | return true; |
618 | 0 | } |
619 | | |
620 | | hb_array_t<const uint64_t> get_lookup_features (hb_codepoint_t lookup_index) const |
621 | 0 | { |
622 | 0 | if (unlikely (!lookup_feature_offsets.length || |
623 | 0 | lookup_index >= lookup_feature_offsets.length - 1)) |
624 | 0 | return {}; |
625 | 0 |
|
626 | 0 | unsigned start = lookup_feature_offsets[lookup_index]; |
627 | 0 | unsigned end = lookup_feature_offsets[lookup_index + 1]; |
628 | 0 | return lookup_features.as_array ().sub_array (start, end - start); |
629 | 0 | } |
630 | | |
631 | | void add_depend (hb_codepoint_t target, hb_tag_t table_tag, |
632 | | hb_codepoint_t dependent, |
633 | | hb_codepoint_t lig_set = HB_CODEPOINT_INVALID, |
634 | | hb_codepoint_t context_set = HB_CODEPOINT_INVALID, |
635 | | hb_subset_depend_edge_flags_t flags = HB_SUBSET_DEPEND_EDGE_FLAG_NONE) |
636 | 0 | { |
637 | 0 | add_depend_layout (target, table_tag, HB_CODEPOINT_INVALID, dependent, lig_set, |
638 | 0 | context_set, flags); |
639 | 0 | } |
640 | | |
641 | | hb_codepoint_t get_nominal_glyph (hb_codepoint_t cp) |
642 | 0 | { return hb_map_get (&nominal_glyphs, cp); } |
643 | | |
644 | | HB_INTERNAL bool compile (hb_face_t *face); |
645 | | |
646 | 0 | bool fail () { successful = false; return false; } |
647 | 0 | hb_codepoint_t fail_invalid () { fail (); return HB_CODEPOINT_INVALID; } |
648 | 0 | bool check_success (bool s) { successful = (successful && s); return successful; } |
649 | | |
650 | | HB_INTERNAL void get_gsub_dependencies (hb_face_t *face); |
651 | | |
652 | | bool successful = true; |
653 | | hb_set_t unicodes; |
654 | | hb_map_t nominal_glyphs; |
655 | | hb_vector_t<uint64_t> lookup_features; |
656 | | hb_vector_t<unsigned> lookup_feature_offsets; |
657 | | hb_vector_t<uint64_t> edge_slots; |
658 | | unsigned int edge_population = 0; |
659 | | hb_hashmap_t<const hb_set_t*, hb_codepoint_t> set_to_index; |
660 | | hb_vector_t<hb_codepoint_t> free_set_list; |
661 | | hb_codepoint_t current_context_set_index; |
662 | | hb_subset_depend_edge_flags_t current_edge_flags; |
663 | | |
664 | | hb_depend_data_t &data; |
665 | | }; |
666 | | |
667 | | |
668 | | #endif /* HB_DEPEND_DATA_HH */ |