Coverage Report

Created: 2026-09-28 10:59

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/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 */