src/hb-ot-layout-gsub-table.hh

   1 /*
   2  * Copyright © 2007,2008,2009,2010  Red Hat, Inc.
   3  * Copyright © 2010,2012,2013  Google, Inc.
   4  *
   5  *  This is part of HarfBuzz, a text shaping library.
   6  *
   7  * Permission is hereby granted, without written agreement and without
   8  * license or royalty fees, to use, copy, modify, and distribute this
   9  * software and its documentation for any purpose, provided that the
  10  * above copyright notice and the following two paragraphs appear in
  11  * all copies of this software.
  12  *
  13  * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
  14  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
  15  * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
  16  * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
  17  * DAMAGE.
  18  *
  19  * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
  20  * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  21  * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
  22  * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
  23  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
  24  *
  25  * Red Hat Author(s): Behdad Esfahbod
  26  * Google Author(s): Behdad Esfahbod
  27  */
  28
  29 #ifndef HB_OT_LAYOUT_GSUB_TABLE_HH
  30 #define HB_OT_LAYOUT_GSUB_TABLE_HH
  31
  32 #include "hb-ot-layout-gsubgpos.hh"
  33
  34
  35 namespace OT {
  36
  37
  38 static inline void SingleSubst_serialize (hb_serialize_context_t *c,
  39                                           hb_array_t<const GlyphID> glyphs,
  40                                           hb_array_t<const GlyphID> substitutes);
  41
  42 struct SingleSubstFormat1
  43 {
  44   bool intersects (const hb_set_t *glyphs) const
  45   { return (this+coverage).intersects (glyphs); }
  46
  47   void closure (hb_closure_context_t *c) const
  48   {
  49     for (Coverage::Iter iter (this+coverage); iter.more (); iter.next ())
  50     {
  51       /* TODO Switch to range-based API to work around malicious fonts.
  52        * https://github.com/harfbuzz/harfbuzz/issues/363 */
  53       hb_codepoint_t glyph_id = iter.get_glyph ();
  54       if (c->glyphs->has (glyph_id))
  55         c->out->add ((glyph_id + deltaGlyphID) & 0xFFFFu);
  56     }
  57   }
  58
  59   void collect_glyphs (hb_collect_glyphs_context_t *c) const
  60   {
  61     if (unlikely (!(this+coverage).add_coverage (c->input))) return;
  62     for (Coverage::Iter iter (this+coverage); iter.more (); iter.next ())
  63     {
  64       /* TODO Switch to range-based API to work around malicious fonts.
  65        * https://github.com/harfbuzz/harfbuzz/issues/363 */
  66       hb_codepoint_t glyph_id = iter.get_glyph ();
  67       c->output->add ((glyph_id + deltaGlyphID) & 0xFFFFu);
  68     }
  69   }
  70
  71   const Coverage &get_coverage () const { return this+coverage; }
  72
  73   bool would_apply (hb_would_apply_context_t *c) const
  74   {
  75     TRACE_WOULD_APPLY (this);
  76     return_trace (c->len == 1 && (this+coverage).get_coverage (c->glyphs[0]) != NOT_COVERED);
  77   }
  78
  79   bool apply (hb_ot_apply_context_t *c) const
  80   {
  81     TRACE_APPLY (this);
  82     hb_codepoint_t glyph_id = c->buffer->cur().codepoint;
  83     unsigned int index = (this+coverage).get_coverage (glyph_id);
  84     if (likely (index == NOT_COVERED)) return_trace (false);
  85
  86     /* According to the Adobe Annotated OpenType Suite, result is always
  87      * limited to 16bit. */
  88     glyph_id = (glyph_id + deltaGlyphID) & 0xFFFFu;
  89     c->replace_glyph (glyph_id);
  90
  91     return_trace (true);
  92   }
  93
  94   bool serialize (hb_serialize_context_t *c,
  95                   hb_array_t<const GlyphID> glyphs,
  96                   int delta)
  97   {
  98     TRACE_SERIALIZE (this);
  99     if (unlikely (!c->extend_min (*this))) return_trace (false);
 100     if (unlikely (!coverage.serialize (c, this).serialize (c, glyphs))) return_trace (false);
 101     deltaGlyphID.set (delta); /* TODO(serialize) overflow? */
 102     return_trace (true);
 103   }
 104
 105   bool subset (hb_subset_context_t *c) const
 106   {
 107     TRACE_SUBSET (this);
 108     const hb_set_t &glyphset = *c->plan->glyphset;
 109     const hb_map_t &glyph_map = *c->plan->glyph_map;
 110     hb_vector_t<GlyphID> from;
 111     hb_vector_t<GlyphID> to;
 112     hb_codepoint_t delta = deltaGlyphID;
 113     for (Coverage::Iter iter (this+coverage); iter.more (); iter.next ())
 114     {
 115       if (!glyphset.has (iter.get_glyph ())) continue;
 116       from.push ()->set (glyph_map[iter.get_glyph ()]);
 117       to.push ()->set (glyph_map[(iter.get_glyph () + delta) & 0xFFFF]);
 118     }
 119     c->serializer->propagate_error (from, to);
 120     SingleSubst_serialize (c->serializer, from, to);
 121     return_trace (from.length);
 122   }
 123
 124   bool sanitize (hb_sanitize_context_t *c) const
 125   {
 126     TRACE_SANITIZE (this);
 127     return_trace (coverage.sanitize (c, this) && deltaGlyphID.sanitize (c));
 128   }
 129
 130   protected:
 131   HBUINT16      format;                 /* Format identifier--format = 1 */
 132   OffsetTo<Coverage>
 133                 coverage;               /* Offset to Coverage table--from
 134                                          * beginning of Substitution table */
 135   HBINT16       deltaGlyphID;           /* Add to original GlyphID to get
 136                                          * substitute GlyphID */
 137   public:
 138   DEFINE_SIZE_STATIC (6);
 139 };
 140
 141 struct SingleSubstFormat2
 142 {
 143   bool intersects (const hb_set_t *glyphs) const
 144   { return (this+coverage).intersects (glyphs); }
 145
 146   void closure (hb_closure_context_t *c) const
 147   {
 148     unsigned int count = substitute.len;
 149     for (Coverage::Iter iter (this+coverage); iter.more (); iter.next ())
 150     {
 151       if (unlikely (iter.get_coverage () >= count))
 152         break; /* Work around malicious fonts. https://github.com/harfbuzz/harfbuzz/issues/363 */
 153       if (c->glyphs->has (iter.get_glyph ()))
 154         c->out->add (substitute[iter.get_coverage ()]);
 155     }
 156   }
 157
 158   void collect_glyphs (hb_collect_glyphs_context_t *c) const
 159   {
 160     if (unlikely (!(this+coverage).add_coverage (c->input))) return;
 161     unsigned int count = substitute.len;
 162     for (Coverage::Iter iter (this+coverage); iter.more (); iter.next ())
 163     {
 164       if (unlikely (iter.get_coverage () >= count))
 165         break; /* Work around malicious fonts. https://github.com/harfbuzz/harfbuzz/issues/363 */
 166       c->output->add (substitute[iter.get_coverage ()]);
 167     }
 168   }
 169
 170   const Coverage &get_coverage () const { return this+coverage; }
 171
 172   bool would_apply (hb_would_apply_context_t *c) const
 173   {
 174     TRACE_WOULD_APPLY (this);
 175     return_trace (c->len == 1 && (this+coverage).get_coverage (c->glyphs[0]) != NOT_COVERED);
 176   }
 177
 178   bool apply (hb_ot_apply_context_t *c) const
 179   {
 180     TRACE_APPLY (this);
 181     unsigned int index = (this+coverage).get_coverage (c->buffer->cur().codepoint);
 182     if (likely (index == NOT_COVERED)) return_trace (false);
 183
 184     if (unlikely (index >= substitute.len)) return_trace (false);
 185
 186     c->replace_glyph (substitute[index]);
 187
 188     return_trace (true);
 189   }
 190
 191   bool serialize (hb_serialize_context_t *c,
 192                   hb_array_t<const GlyphID> glyphs,
 193                   hb_array_t<const GlyphID> substitutes)
 194   {
 195     TRACE_SERIALIZE (this);
 196     if (unlikely (!c->extend_min (*this))) return_trace (false);
 197     if (unlikely (!substitute.serialize (c, substitutes))) return_trace (false);
 198     if (unlikely (!coverage.serialize (c, this).serialize (c, glyphs))) return_trace (false);
 199     return_trace (true);
 200   }
 201
 202   bool subset (hb_subset_context_t *c) const
 203   {
 204     TRACE_SUBSET (this);
 205     const hb_set_t &glyphset = *c->plan->glyphset;
 206     const hb_map_t &glyph_map = *c->plan->glyph_map;
 207     hb_vector_t<GlyphID> from;
 208     hb_vector_t<GlyphID> to;
 209     for (Coverage::Iter iter (this+coverage); iter.more (); iter.next ())
 210     {
 211       if (!glyphset.has (iter.get_glyph ())) continue;
 212       from.push ()->set (glyph_map[iter.get_glyph ()]);
 213       to.push ()->set (glyph_map[substitute[iter.get_coverage ()]]);
 214     }
 215     c->serializer->propagate_error (from, to);
 216     SingleSubst_serialize (c->serializer, from, to);
 217     return_trace (from.length);
 218   }
 219
 220   bool sanitize (hb_sanitize_context_t *c) const
 221   {
 222     TRACE_SANITIZE (this);
 223     return_trace (coverage.sanitize (c, this) && substitute.sanitize (c));
 224   }
 225
 226   protected:
 227   HBUINT16      format;                 /* Format identifier--format = 2 */
 228   OffsetTo<Coverage>
 229                 coverage;               /* Offset to Coverage table--from
 230                                          * beginning of Substitution table */
 231   ArrayOf<GlyphID>
 232                 substitute;             /* Array of substitute
 233                                          * GlyphIDs--ordered by Coverage Index */
 234   public:
 235   DEFINE_SIZE_ARRAY (6, substitute);
 236 };
 237
 238 struct SingleSubst
 239 {
 240   bool serialize (hb_serialize_context_t *c,
 241                   hb_array_t<const GlyphID> glyphs,
 242                   hb_array_t<const GlyphID> substitutes)
 243   {
 244     TRACE_SERIALIZE (this);
 245     if (unlikely (!c->extend_min (u.format))) return_trace (false);
 246     unsigned int format = 2;
 247     int delta = 0;
 248     if (glyphs.length)
 249     {
 250       format = 1;
 251       /* TODO(serialize) check for wrap-around */
 252       delta = substitutes[0] - glyphs[0];
 253       for (unsigned int i = 1; i < glyphs.length; i++)
 254         if (delta != (int) (substitutes[i] - glyphs[i])) {
 255           format = 2;
 256           break;
 257         }
 258     }
 259     u.format.set (format);
 260     switch (u.format) {
 261     case 1: return_trace (u.format1.serialize (c, glyphs, delta));
 262     case 2: return_trace (u.format2.serialize (c, glyphs, substitutes));
 263     default:return_trace (false);
 264     }
 265   }
 266
 267   template <typename context_t>
 268   typename context_t::return_t dispatch (context_t *c) const
 269   {
 270     TRACE_DISPATCH (this, u.format);
 271     if (unlikely (!c->may_dispatch (this, &u.format))) return_trace (c->no_dispatch_return_value ());
 272     switch (u.format) {
 273     case 1: return_trace (c->dispatch (u.format1));
 274     case 2: return_trace (c->dispatch (u.format2));
 275     default:return_trace (c->default_return_value ());
 276     }
 277   }
 278
 279   protected:
 280   union {
 281   HBUINT16              format;         /* Format identifier */
 282   SingleSubstFormat1    format1;
 283   SingleSubstFormat2    format2;
 284   } u;
 285 };
 286
 287 static inline void
 288 SingleSubst_serialize (hb_serialize_context_t *c,
 289                        hb_array_t<const GlyphID> glyphs,
 290                        hb_array_t<const GlyphID> substitutes)
 291 { c->start_embed<SingleSubst> ()->serialize (c, glyphs, substitutes); }
 292
 293 struct Sequence
 294 {
 295   void closure (hb_closure_context_t *c) const
 296   {
 297     unsigned int count = substitute.len;
 298     for (unsigned int i = 0; i < count; i++)
 299       c->out->add (substitute[i]);
 300   }
 301
 302   void collect_glyphs (hb_collect_glyphs_context_t *c) const
 303   { c->output->add_array (substitute.arrayZ, substitute.len); }
 304
 305   bool apply (hb_ot_apply_context_t *c) const
 306   {
 307     TRACE_APPLY (this);
 308     unsigned int count = substitute.len;
 309
 310     /* Special-case to make it in-place and not consider this
 311      * as a "multiplied" substitution. */
 312     if (unlikely (count == 1))
 313     {
 314       c->replace_glyph (substitute.arrayZ[0]);
 315       return_trace (true);
 316     }
 317     /* Spec disallows this, but Uniscribe allows it.
 318      * https://github.com/harfbuzz/harfbuzz/issues/253 */
 319     else if (unlikely (count == 0))
 320     {
 321       c->buffer->delete_glyph ();
 322       return_trace (true);
 323     }
 324
 325     unsigned int klass = _hb_glyph_info_is_ligature (&c->buffer->cur()) ?
 326                          HB_OT_LAYOUT_GLYPH_PROPS_BASE_GLYPH : 0;
 327
 328     for (unsigned int i = 0; i < count; i++) {
 329       _hb_glyph_info_set_lig_props_for_component (&c->buffer->cur(), i);
 330       c->output_glyph_for_component (substitute.arrayZ[i], klass);
 331     }
 332     c->buffer->skip_glyph ();
 333
 334     return_trace (true);
 335   }
 336
 337   bool serialize (hb_serialize_context_t *c,
 338                   hb_array_t<const GlyphID> glyphs)
 339   {
 340     TRACE_SERIALIZE (this);
 341     return_trace (substitute.serialize (c, glyphs));
 342   }
 343
 344   bool sanitize (hb_sanitize_context_t *c) const
 345   {
 346     TRACE_SANITIZE (this);
 347     return_trace (substitute.sanitize (c));
 348   }
 349
 350   protected:
 351   ArrayOf<GlyphID>
 352                 substitute;             /* String of GlyphIDs to substitute */
 353   public:
 354   DEFINE_SIZE_ARRAY (2, substitute);
 355 };
 356
 357 struct MultipleSubstFormat1
 358 {
 359   bool intersects (const hb_set_t *glyphs) const
 360   { return (this+coverage).intersects (glyphs); }
 361
 362   void closure (hb_closure_context_t *c) const
 363   {
 364     unsigned int count = sequence.len;
 365     for (Coverage::Iter iter (this+coverage); iter.more (); iter.next ())
 366     {
 367       if (unlikely (iter.get_coverage () >= count))
 368         break; /* Work around malicious fonts. https://github.com/harfbuzz/harfbuzz/issues/363 */
 369       if (c->glyphs->has (iter.get_glyph ()))
 370         (this+sequence[iter.get_coverage ()]).closure (c);
 371     }
 372   }
 373
 374   void collect_glyphs (hb_collect_glyphs_context_t *c) const
 375   {
 376     if (unlikely (!(this+coverage).add_coverage (c->input))) return;
 377     unsigned int count = sequence.len;
 378     for (unsigned int i = 0; i < count; i++)
 379       (this+sequence[i]).collect_glyphs (c);
 380   }
 381
 382   const Coverage &get_coverage () const { return this+coverage; }
 383
 384   bool would_apply (hb_would_apply_context_t *c) const
 385   {
 386     TRACE_WOULD_APPLY (this);
 387     return_trace (c->len == 1 && (this+coverage).get_coverage (c->glyphs[0]) != NOT_COVERED);
 388   }
 389
 390   bool apply (hb_ot_apply_context_t *c) const
 391   {
 392     TRACE_APPLY (this);
 393
 394     unsigned int index = (this+coverage).get_coverage (c->buffer->cur().codepoint);
 395     if (likely (index == NOT_COVERED)) return_trace (false);
 396
 397     return_trace ((this+sequence[index]).apply (c));
 398   }
 399
 400   bool serialize (hb_serialize_context_t *c,
 401                   hb_array_t<const GlyphID> glyphs,
 402                   hb_array_t<const unsigned int> substitute_len_list,
 403                   hb_array_t<const GlyphID> substitute_glyphs_list)
 404   {
 405     TRACE_SERIALIZE (this);
 406     if (unlikely (!c->extend_min (*this))) return_trace (false);
 407     if (unlikely (!sequence.serialize (c, glyphs.length))) return_trace (false);
 408     for (unsigned int i = 0; i < glyphs.length; i++)
 409     {
 410       unsigned int substitute_len = substitute_len_list[i];
 411       if (unlikely (!sequence[i].serialize (c, this)
 412                                 .serialize (c, substitute_glyphs_list.sub_array (0, substitute_len))))
 413         return_trace (false);
 414       substitute_glyphs_list += substitute_len;
 415     }
 416     return_trace (coverage.serialize (c, this).serialize (c, glyphs));
 417   }
 418
 419   bool subset (hb_subset_context_t *c) const
 420   {
 421     TRACE_SUBSET (this);
 422     // TODO(subset)
 423     return_trace (false);
 424   }
 425
 426   bool sanitize (hb_sanitize_context_t *c) const
 427   {
 428     TRACE_SANITIZE (this);
 429     return_trace (coverage.sanitize (c, this) && sequence.sanitize (c, this));
 430   }
 431
 432   protected:
 433   HBUINT16      format;                 /* Format identifier--format = 1 */
 434   OffsetTo<Coverage>
 435                 coverage;               /* Offset to Coverage table--from
 436                                          * beginning of Substitution table */
 437   OffsetArrayOf<Sequence>
 438                 sequence;               /* Array of Sequence tables
 439                                          * ordered by Coverage Index */
 440   public:
 441   DEFINE_SIZE_ARRAY (6, sequence);
 442 };
 443
 444 struct MultipleSubst
 445 {
 446   bool serialize (hb_serialize_context_t *c,
 447                   hb_array_t<const GlyphID> glyphs,
 448                   hb_array_t<const unsigned int> substitute_len_list,
 449                   hb_array_t<const GlyphID> substitute_glyphs_list)
 450   {
 451     TRACE_SERIALIZE (this);
 452     if (unlikely (!c->extend_min (u.format))) return_trace (false);
 453     unsigned int format = 1;
 454     u.format.set (format);
 455     switch (u.format) {
 456     case 1: return_trace (u.format1.serialize (c, glyphs, substitute_len_list, substitute_glyphs_list));
 457     default:return_trace (false);
 458     }
 459   }
 460
 461   template <typename context_t>
 462   typename context_t::return_t dispatch (context_t *c) const
 463   {
 464     TRACE_DISPATCH (this, u.format);
 465     if (unlikely (!c->may_dispatch (this, &u.format))) return_trace (c->no_dispatch_return_value ());
 466     switch (u.format) {
 467     case 1: return_trace (c->dispatch (u.format1));
 468     default:return_trace (c->default_return_value ());
 469     }
 470   }
 471
 472   protected:
 473   union {
 474   HBUINT16              format;         /* Format identifier */
 475   MultipleSubstFormat1  format1;
 476   } u;
 477 };
 478
 479 struct AlternateSet
 480 {
 481   void closure (hb_closure_context_t *c) const
 482   {
 483     unsigned int count = alternates.len;
 484     for (unsigned int i = 0; i < count; i++)
 485       c->out->add (alternates[i]);
 486   }
 487
 488   void collect_glyphs (hb_collect_glyphs_context_t *c) const
 489   { c->output->add_array (alternates.arrayZ, alternates.len); }
 490
 491   bool apply (hb_ot_apply_context_t *c) const
 492   {
 493     TRACE_APPLY (this);
 494     unsigned int count = alternates.len;
 495
 496     if (unlikely (!count)) return_trace (false);
 497
 498     hb_mask_t glyph_mask = c->buffer->cur().mask;
 499     hb_mask_t lookup_mask = c->lookup_mask;
 500
 501     /* Note: This breaks badly if two features enabled this lookup together. */
 502     unsigned int shift = hb_ctz (lookup_mask);
 503     unsigned int alt_index = ((lookup_mask & glyph_mask) >> shift);
 504
 505     /* If alt_index is MAX, randomize feature if it is the rand feature. */
 506     if (alt_index == HB_OT_MAP_MAX_VALUE && c->random)
 507       alt_index = c->random_number () % count + 1;
 508
 509     if (unlikely (alt_index > count || alt_index == 0)) return_trace (false);
 510
 511     c->replace_glyph (alternates[alt_index - 1]);
 512
 513     return_trace (true);
 514   }
 515
 516   bool serialize (hb_serialize_context_t *c,
 517                   hb_array_t<const GlyphID> glyphs)
 518   {
 519     TRACE_SERIALIZE (this);
 520     return_trace (alternates.serialize (c, glyphs));
 521   }
 522
 523   bool sanitize (hb_sanitize_context_t *c) const
 524   {
 525     TRACE_SANITIZE (this);
 526     return_trace (alternates.sanitize (c));
 527   }
 528
 529   protected:
 530   ArrayOf<GlyphID>
 531                 alternates;             /* Array of alternate GlyphIDs--in
 532                                          * arbitrary order */
 533   public:
 534   DEFINE_SIZE_ARRAY (2, alternates);
 535 };
 536
 537 struct AlternateSubstFormat1
 538 {
 539   bool intersects (const hb_set_t *glyphs) const
 540   { return (this+coverage).intersects (glyphs); }
 541
 542   void closure (hb_closure_context_t *c) const
 543   {
 544     unsigned int count = alternateSet.len;
 545     for (Coverage::Iter iter (this+coverage); iter.more (); iter.next ())
 546     {
 547       if (unlikely (iter.get_coverage () >= count))
 548         break; /* Work around malicious fonts. https://github.com/harfbuzz/harfbuzz/issues/363 */
 549       if (c->glyphs->has (iter.get_glyph ()))
 550         (this+alternateSet[iter.get_coverage ()]).closure (c);
 551     }
 552   }
 553
 554   void collect_glyphs (hb_collect_glyphs_context_t *c) const
 555   {
 556     if (unlikely (!(this+coverage).add_coverage (c->input))) return;
 557     unsigned int count = alternateSet.len;
 558     for (Coverage::Iter iter (this+coverage); iter.more (); iter.next ())
 559     {
 560       if (unlikely (iter.get_coverage () >= count))
 561         break; /* Work around malicious fonts. https://github.com/harfbuzz/harfbuzz/issues/363 */
 562       (this+alternateSet[iter.get_coverage ()]).collect_glyphs (c);
 563     }
 564   }
 565
 566   const Coverage &get_coverage () const { return this+coverage; }
 567
 568   bool would_apply (hb_would_apply_context_t *c) const
 569   {
 570     TRACE_WOULD_APPLY (this);
 571     return_trace (c->len == 1 && (this+coverage).get_coverage (c->glyphs[0]) != NOT_COVERED);
 572   }
 573
 574   bool apply (hb_ot_apply_context_t *c) const
 575   {
 576     TRACE_APPLY (this);
 577
 578     unsigned int index = (this+coverage).get_coverage (c->buffer->cur().codepoint);
 579     if (likely (index == NOT_COVERED)) return_trace (false);
 580
 581     return_trace ((this+alternateSet[index]).apply (c));
 582   }
 583
 584   bool serialize (hb_serialize_context_t *c,
 585                   hb_array_t<const GlyphID> glyphs,
 586                   hb_array_t<const unsigned int> alternate_len_list,
 587                   hb_array_t<const GlyphID> alternate_glyphs_list)
 588   {
 589     TRACE_SERIALIZE (this);
 590     if (unlikely (!c->extend_min (*this))) return_trace (false);
 591     if (unlikely (!alternateSet.serialize (c, glyphs.length))) return_trace (false);
 592     for (unsigned int i = 0; i < glyphs.length; i++)
 593     {
 594       unsigned int alternate_len = alternate_len_list[i];
 595       if (unlikely (!alternateSet[i].serialize (c, this)
 596                                     .serialize (c, alternate_glyphs_list.sub_array (0, alternate_len))))
 597         return_trace (false);
 598       alternate_glyphs_list += alternate_len;
 599     }
 600     return_trace (coverage.serialize (c, this).serialize (c, glyphs));
 601   }
 602
 603   bool subset (hb_subset_context_t *c) const
 604   {
 605     TRACE_SUBSET (this);
 606     // TODO(subset)
 607     return_trace (false);
 608   }
 609
 610   bool sanitize (hb_sanitize_context_t *c) const
 611   {
 612     TRACE_SANITIZE (this);
 613     return_trace (coverage.sanitize (c, this) && alternateSet.sanitize (c, this));
 614   }
 615
 616   protected:
 617   HBUINT16      format;                 /* Format identifier--format = 1 */
 618   OffsetTo<Coverage>
 619                 coverage;               /* Offset to Coverage table--from
 620                                          * beginning of Substitution table */
 621   OffsetArrayOf<AlternateSet>
 622                 alternateSet;           /* Array of AlternateSet tables
 623                                          * ordered by Coverage Index */
 624   public:
 625   DEFINE_SIZE_ARRAY (6, alternateSet);
 626 };
 627
 628 struct AlternateSubst
 629 {
 630   bool serialize (hb_serialize_context_t *c,
 631                   hb_array_t<const GlyphID> glyphs,
 632                   hb_array_t<const unsigned int> alternate_len_list,
 633                   hb_array_t<const GlyphID> alternate_glyphs_list)
 634   {
 635     TRACE_SERIALIZE (this);
 636     if (unlikely (!c->extend_min (u.format))) return_trace (false);
 637     unsigned int format = 1;
 638     u.format.set (format);
 639     switch (u.format) {
 640     case 1: return_trace (u.format1.serialize (c, glyphs, alternate_len_list, alternate_glyphs_list));
 641     default:return_trace (false);
 642     }
 643   }
 644
 645   template <typename context_t>
 646   typename context_t::return_t dispatch (context_t *c) const
 647   {
 648     TRACE_DISPATCH (this, u.format);
 649     if (unlikely (!c->may_dispatch (this, &u.format))) return_trace (c->no_dispatch_return_value ());
 650     switch (u.format) {
 651     case 1: return_trace (c->dispatch (u.format1));
 652     default:return_trace (c->default_return_value ());
 653     }
 654   }
 655
 656   protected:
 657   union {
 658   HBUINT16              format;         /* Format identifier */
 659   AlternateSubstFormat1 format1;
 660   } u;
 661 };
 662
 663
 664 struct Ligature
 665 {
 666   bool intersects (const hb_set_t *glyphs) const
 667   {
 668     unsigned int count = component.lenP1;
 669     for (unsigned int i = 1; i < count; i++)
 670       if (!glyphs->has (component[i]))
 671         return false;
 672     return true;
 673   }
 674
 675   void closure (hb_closure_context_t *c) const
 676   {
 677     unsigned int count = component.lenP1;
 678     for (unsigned int i = 1; i < count; i++)
 679       if (!c->glyphs->has (component[i]))
 680         return;
 681     c->out->add (ligGlyph);
 682   }
 683
 684   void collect_glyphs (hb_collect_glyphs_context_t *c) const
 685   {
 686     c->input->add_array (component.arrayZ, component.lenP1 ? component.lenP1 - 1 : 0);
 687     c->output->add (ligGlyph);
 688   }
 689
 690   bool would_apply (hb_would_apply_context_t *c) const
 691   {
 692     TRACE_WOULD_APPLY (this);
 693     if (c->len != component.lenP1)
 694       return_trace (false);
 695
 696     for (unsigned int i = 1; i < c->len; i++)
 697       if (likely (c->glyphs[i] != component[i]))
 698         return_trace (false);
 699
 700     return_trace (true);
 701   }
 702
 703   bool apply (hb_ot_apply_context_t *c) const
 704   {
 705     TRACE_APPLY (this);
 706     unsigned int count = component.lenP1;
 707
 708     if (unlikely (!count)) return_trace (false);
 709
 710     /* Special-case to make it in-place and not consider this
 711      * as a "ligated" substitution. */
 712     if (unlikely (count == 1))
 713     {
 714       c->replace_glyph (ligGlyph);
 715       return_trace (true);
 716     }
 717
 718     unsigned int total_component_count = 0;
 719
 720     unsigned int match_length = 0;
 721     unsigned int match_positions[HB_MAX_CONTEXT_LENGTH];
 722
 723     if (likely (!match_input (c, count,
 724                               &component[1],
 725                               match_glyph,
 726                               nullptr,
 727                               &match_length,
 728                               match_positions,
 729                               &total_component_count)))
 730       return_trace (false);
 731
 732     ligate_input (c,
 733                   count,
 734                   match_positions,
 735                   match_length,
 736                   ligGlyph,
 737                   total_component_count);
 738
 739     return_trace (true);
 740   }
 741
 742   bool serialize (hb_serialize_context_t *c,
 743                   GlyphID ligature,
 744                   hb_array_t<const GlyphID> components /* Starting from second */)
 745   {
 746     TRACE_SERIALIZE (this);
 747     if (unlikely (!c->extend_min (*this))) return_trace (false);
 748     ligGlyph = ligature;
 749     if (unlikely (!component.serialize (c, components))) return_trace (false);
 750     return_trace (true);
 751   }
 752
 753   public:
 754   bool sanitize (hb_sanitize_context_t *c) const
 755   {
 756     TRACE_SANITIZE (this);
 757     return_trace (ligGlyph.sanitize (c) && component.sanitize (c));
 758   }
 759
 760   protected:
 761   GlyphID       ligGlyph;               /* GlyphID of ligature to substitute */
 762   HeadlessArrayOf<GlyphID>
 763                 component;              /* Array of component GlyphIDs--start
 764                                          * with the second  component--ordered
 765                                          * in writing direction */
 766   public:
 767   DEFINE_SIZE_ARRAY (4, component);
 768 };
 769
 770 struct LigatureSet
 771 {
 772   bool intersects (const hb_set_t *glyphs) const
 773   {
 774     unsigned int num_ligs = ligature.len;
 775     for (unsigned int i = 0; i < num_ligs; i++)
 776       if ((this+ligature[i]).intersects (glyphs))
 777         return true;
 778     return false;
 779   }
 780
 781   void closure (hb_closure_context_t *c) const
 782   {
 783     unsigned int num_ligs = ligature.len;
 784     for (unsigned int i = 0; i < num_ligs; i++)
 785       (this+ligature[i]).closure (c);
 786   }
 787
 788   void collect_glyphs (hb_collect_glyphs_context_t *c) const
 789   {
 790     unsigned int num_ligs = ligature.len;
 791     for (unsigned int i = 0; i < num_ligs; i++)
 792       (this+ligature[i]).collect_glyphs (c);
 793   }
 794
 795   bool would_apply (hb_would_apply_context_t *c) const
 796   {
 797     TRACE_WOULD_APPLY (this);
 798     unsigned int num_ligs = ligature.len;
 799     for (unsigned int i = 0; i < num_ligs; i++)
 800     {
 801       const Ligature &lig = this+ligature[i];
 802       if (lig.would_apply (c))
 803         return_trace (true);
 804     }
 805     return_trace (false);
 806   }
 807
 808   bool apply (hb_ot_apply_context_t *c) const
 809   {
 810     TRACE_APPLY (this);
 811     unsigned int num_ligs = ligature.len;
 812     for (unsigned int i = 0; i < num_ligs; i++)
 813     {
 814       const Ligature &lig = this+ligature[i];
 815       if (lig.apply (c)) return_trace (true);
 816     }
 817
 818     return_trace (false);
 819   }
 820
 821   bool serialize (hb_serialize_context_t *c,
 822                   hb_array_t<const GlyphID> ligatures,
 823                   hb_array_t<const unsigned int> component_count_list,
 824                   hb_array_t<const GlyphID> &component_list /* Starting from second for each ligature */)
 825   {
 826     TRACE_SERIALIZE (this);
 827     if (unlikely (!c->extend_min (*this))) return_trace (false);
 828     if (unlikely (!ligature.serialize (c, ligatures.length))) return_trace (false);
 829     for (unsigned int i = 0; i < ligatures.length; i++)
 830     {
 831       unsigned int component_count = MAX<int> (component_count_list[i] - 1, 0);
 832       if (unlikely (!ligature[i].serialize (c, this)
 833                                 .serialize (c,
 834                                             ligatures[i],
 835                                             component_list.sub_array (0, component_count))))
 836         return_trace (false);
 837       component_list += component_count;
 838     }
 839     return_trace (true);
 840   }
 841
 842   bool sanitize (hb_sanitize_context_t *c) const
 843   {
 844     TRACE_SANITIZE (this);
 845     return_trace (ligature.sanitize (c, this));
 846   }
 847
 848   protected:
 849   OffsetArrayOf<Ligature>
 850                 ligature;               /* Array LigatureSet tables
 851                                          * ordered by preference */
 852   public:
 853   DEFINE_SIZE_ARRAY (2, ligature);
 854 };
 855
 856 struct LigatureSubstFormat1
 857 {
 858   bool intersects (const hb_set_t *glyphs) const
 859   {
 860     unsigned int count = ligatureSet.len;
 861     for (Coverage::Iter iter (this+coverage); iter.more (); iter.next ())
 862     {
 863       if (unlikely (iter.get_coverage () >= count))
 864         break; /* Work around malicious fonts. https://github.com/harfbuzz/harfbuzz/issues/363 */
 865       if (glyphs->has (iter.get_glyph ()) &&
 866           (this+ligatureSet[iter.get_coverage ()]).intersects (glyphs))
 867         return true;
 868     }
 869     return false;
 870   }
 871
 872   void closure (hb_closure_context_t *c) const
 873   {
 874     unsigned int count = ligatureSet.len;
 875     for (Coverage::Iter iter (this+coverage); iter.more (); iter.next ())
 876     {
 877       if (unlikely (iter.get_coverage () >= count))
 878         break; /* Work around malicious fonts. https://github.com/harfbuzz/harfbuzz/issues/363 */
 879       if (c->glyphs->has (iter.get_glyph ()))
 880         (this+ligatureSet[iter.get_coverage ()]).closure (c);
 881     }
 882   }
 883
 884   void collect_glyphs (hb_collect_glyphs_context_t *c) const
 885   {
 886     if (unlikely (!(this+coverage).add_coverage (c->input))) return;
 887     unsigned int count = ligatureSet.len;
 888     for (Coverage::Iter iter (this+coverage); iter.more (); iter.next ())
 889     {
 890       if (unlikely (iter.get_coverage () >= count))
 891         break; /* Work around malicious fonts. https://github.com/harfbuzz/harfbuzz/issues/363 */
 892       (this+ligatureSet[iter.get_coverage ()]).collect_glyphs (c);
 893     }
 894   }
 895
 896   const Coverage &get_coverage () const { return this+coverage; }
 897
 898   bool would_apply (hb_would_apply_context_t *c) const
 899   {
 900     TRACE_WOULD_APPLY (this);
 901     unsigned int index = (this+coverage).get_coverage (c->glyphs[0]);
 902     if (likely (index == NOT_COVERED)) return_trace (false);
 903
 904     const LigatureSet &lig_set = this+ligatureSet[index];
 905     return_trace (lig_set.would_apply (c));
 906   }
 907
 908   bool apply (hb_ot_apply_context_t *c) const
 909   {
 910     TRACE_APPLY (this);
 911
 912     unsigned int index = (this+coverage).get_coverage (c->buffer->cur().codepoint);
 913     if (likely (index == NOT_COVERED)) return_trace (false);
 914
 915     const LigatureSet &lig_set = this+ligatureSet[index];
 916     return_trace (lig_set.apply (c));
 917   }
 918
 919   bool serialize (hb_serialize_context_t *c,
 920                   hb_array_t<const GlyphID> first_glyphs,
 921                   hb_array_t<const unsigned int> ligature_per_first_glyph_count_list,
 922                   hb_array_t<const GlyphID> ligatures_list,
 923                   hb_array_t<const unsigned int> component_count_list,
 924                   hb_array_t<const GlyphID> component_list /* Starting from second for each ligature */)
 925   {
 926     TRACE_SERIALIZE (this);
 927     if (unlikely (!c->extend_min (*this))) return_trace (false);
 928     if (unlikely (!ligatureSet.serialize (c, first_glyphs.length))) return_trace (false);
 929     for (unsigned int i = 0; i < first_glyphs.length; i++)
 930     {
 931       unsigned int ligature_count = ligature_per_first_glyph_count_list[i];
 932       if (unlikely (!ligatureSet[i].serialize (c, this)
 933                                    .serialize (c,
 934                                                ligatures_list.sub_array (0, ligature_count),
 935                                                component_count_list.sub_array (0, ligature_count),
 936                                                component_list))) return_trace (false);
 937       ligatures_list += ligature_count;
 938       component_count_list += ligature_count;
 939     }
 940     return_trace (coverage.serialize (c, this).serialize (c, first_glyphs));
 941   }
 942
 943   bool subset (hb_subset_context_t *c) const
 944   {
 945     TRACE_SUBSET (this);
 946     // TODO(subset)
 947     return_trace (false);
 948   }
 949
 950   bool sanitize (hb_sanitize_context_t *c) const
 951   {
 952     TRACE_SANITIZE (this);
 953     return_trace (coverage.sanitize (c, this) && ligatureSet.sanitize (c, this));
 954   }
 955
 956   protected:
 957   HBUINT16      format;                 /* Format identifier--format = 1 */
 958   OffsetTo<Coverage>
 959                 coverage;               /* Offset to Coverage table--from
 960                                          * beginning of Substitution table */
 961   OffsetArrayOf<LigatureSet>
 962                 ligatureSet;            /* Array LigatureSet tables
 963                                          * ordered by Coverage Index */
 964   public:
 965   DEFINE_SIZE_ARRAY (6, ligatureSet);
 966 };
 967
 968 struct LigatureSubst
 969 {
 970   bool serialize (hb_serialize_context_t *c,
 971                   hb_array_t<const GlyphID> first_glyphs,
 972                   hb_array_t<const unsigned int> ligature_per_first_glyph_count_list,
 973                   hb_array_t<const GlyphID> ligatures_list,
 974                   hb_array_t<const unsigned int> component_count_list,
 975                   hb_array_t<const GlyphID> component_list /* Starting from second for each ligature */)
 976   {
 977     TRACE_SERIALIZE (this);
 978     if (unlikely (!c->extend_min (u.format))) return_trace (false);
 979     unsigned int format = 1;
 980     u.format.set (format);
 981     switch (u.format) {
 982     case 1: return_trace (u.format1.serialize (c,
 983                                                first_glyphs,
 984                                                ligature_per_first_glyph_count_list,
 985                                                ligatures_list,
 986                                                component_count_list,
 987                                                component_list));
 988     default:return_trace (false);
 989     }
 990   }
 991
 992   template <typename context_t>
 993   typename context_t::return_t dispatch (context_t *c) const
 994   {
 995     TRACE_DISPATCH (this, u.format);
 996     if (unlikely (!c->may_dispatch (this, &u.format))) return_trace (c->no_dispatch_return_value ());
 997     switch (u.format) {
 998     case 1: return_trace (c->dispatch (u.format1));
 999     default:return_trace (c->default_return_value ());
1000     }
1001   }
1002
1003   protected:
1004   union {
1005   HBUINT16              format;         /* Format identifier */
1006   LigatureSubstFormat1  format1;
1007   } u;
1008 };
1009
1010
1011 struct ContextSubst : Context {};
1012
1013 struct ChainContextSubst : ChainContext {};
1014
1015 struct ExtensionSubst : Extension<ExtensionSubst>
1016 {
1017   typedef struct SubstLookupSubTable SubTable;
1018
1019   bool is_reverse () const;
1020 };
1021
1022
1023 struct ReverseChainSingleSubstFormat1
1024 {
1025   bool intersects (const hb_set_t *glyphs) const
1026   {
1027     if (!(this+coverage).intersects (glyphs))
1028       return false;
1029
1030     const OffsetArrayOf<Coverage> &lookahead = StructAfter<OffsetArrayOf<Coverage> > (backtrack);
1031
1032     unsigned int count;
1033
1034     count = backtrack.len;
1035     for (unsigned int i = 0; i < count; i++)
1036       if (!(this+backtrack[i]).intersects (glyphs))
1037         return false;
1038
1039     count = lookahead.len;
1040     for (unsigned int i = 0; i < count; i++)
1041       if (!(this+lookahead[i]).intersects (glyphs))
1042         return false;
1043
1044     return true;
1045   }
1046
1047   void closure (hb_closure_context_t *c) const
1048   {
1049     const OffsetArrayOf<Coverage> &lookahead = StructAfter<OffsetArrayOf<Coverage> > (backtrack);
1050
1051     unsigned int count;
1052
1053     count = backtrack.len;
1054     for (unsigned int i = 0; i < count; i++)
1055       if (!(this+backtrack[i]).intersects (c->glyphs))
1056         return;
1057
1058     count = lookahead.len;
1059     for (unsigned int i = 0; i < count; i++)
1060       if (!(this+lookahead[i]).intersects (c->glyphs))
1061         return;
1062
1063     const ArrayOf<GlyphID> &substitute = StructAfter<ArrayOf<GlyphID> > (lookahead);
1064     count = substitute.len;
1065     for (Coverage::Iter iter (this+coverage); iter.more (); iter.next ())
1066     {
1067       if (unlikely (iter.get_coverage () >= count))
1068         break; /* Work around malicious fonts. https://github.com/harfbuzz/harfbuzz/issues/363 */
1069       if (c->glyphs->has (iter.get_glyph ()))
1070         c->out->add (substitute[iter.get_coverage ()]);
1071     }
1072   }
1073
1074   void collect_glyphs (hb_collect_glyphs_context_t *c) const
1075   {
1076     if (unlikely (!(this+coverage).add_coverage (c->input))) return;
1077
1078     unsigned int count;
1079
1080     count = backtrack.len;
1081     for (unsigned int i = 0; i < count; i++)
1082       if (unlikely (!(this+backtrack[i]).add_coverage (c->before))) return;
1083
1084     const OffsetArrayOf<Coverage> &lookahead = StructAfter<OffsetArrayOf<Coverage> > (backtrack);
1085     count = lookahead.len;
1086     for (unsigned int i = 0; i < count; i++)
1087       if (unlikely (!(this+lookahead[i]).add_coverage (c->after))) return;
1088
1089     const ArrayOf<GlyphID> &substitute = StructAfter<ArrayOf<GlyphID> > (lookahead);
1090     count = substitute.len;
1091     c->output->add_array (substitute.arrayZ, substitute.len);
1092   }
1093
1094   const Coverage &get_coverage () const { return this+coverage; }
1095
1096   bool would_apply (hb_would_apply_context_t *c) const
1097   {
1098     TRACE_WOULD_APPLY (this);
1099     return_trace (c->len == 1 && (this+coverage).get_coverage (c->glyphs[0]) != NOT_COVERED);
1100   }
1101
1102   bool apply (hb_ot_apply_context_t *c) const
1103   {
1104     TRACE_APPLY (this);
1105     if (unlikely (c->nesting_level_left != HB_MAX_NESTING_LEVEL))
1106       return_trace (false); /* No chaining to this type */
1107
1108     unsigned int index = (this+coverage).get_coverage (c->buffer->cur().codepoint);
1109     if (likely (index == NOT_COVERED)) return_trace (false);
1110
1111     const OffsetArrayOf<Coverage> &lookahead = StructAfter<OffsetArrayOf<Coverage> > (backtrack);
1112     const ArrayOf<GlyphID> &substitute = StructAfter<ArrayOf<GlyphID> > (lookahead);
1113
1114   unsigned int start_index = 0, end_index = 0;
1115     if (match_backtrack (c,
1116                          backtrack.len, (HBUINT16 *) backtrack.arrayZ,
1117                          match_coverage, this,
1118                          &start_index) &&
1119         match_lookahead (c,
1120                          lookahead.len, (HBUINT16 *) lookahead.arrayZ,
1121                          match_coverage, this,
1122                          1, &end_index))
1123     {
1124       c->buffer->unsafe_to_break_from_outbuffer (start_index, end_index);
1125       c->replace_glyph_inplace (substitute[index]);
1126       /* Note: We DON'T decrease buffer->idx.  The main loop does it
1127        * for us.  This is useful for preventing surprises if someone
1128        * calls us through a Context lookup. */
1129       return_trace (true);
1130     }
1131
1132     return_trace (false);
1133   }
1134
1135   bool subset (hb_subset_context_t *c) const
1136   {
1137     TRACE_SUBSET (this);
1138     // TODO(subset)
1139     return_trace (false);
1140   }
1141
1142   bool sanitize (hb_sanitize_context_t *c) const
1143   {
1144     TRACE_SANITIZE (this);
1145     if (!(coverage.sanitize (c, this) && backtrack.sanitize (c, this)))
1146       return_trace (false);
1147     const OffsetArrayOf<Coverage> &lookahead = StructAfter<OffsetArrayOf<Coverage> > (backtrack);
1148     if (!lookahead.sanitize (c, this))
1149       return_trace (false);
1150     const ArrayOf<GlyphID> &substitute = StructAfter<ArrayOf<GlyphID> > (lookahead);
1151     return_trace (substitute.sanitize (c));
1152   }
1153
1154   protected:
1155   HBUINT16      format;                 /* Format identifier--format = 1 */
1156   OffsetTo<Coverage>
1157                 coverage;               /* Offset to Coverage table--from
1158                                          * beginning of table */
1159   OffsetArrayOf<Coverage>
1160                 backtrack;              /* Array of coverage tables
1161                                          * in backtracking sequence, in glyph
1162                                          * sequence order */
1163   OffsetArrayOf<Coverage>
1164                 lookaheadX;             /* Array of coverage tables
1165                                          * in lookahead sequence, in glyph
1166                                          * sequence order */
1167   ArrayOf<GlyphID>
1168                 substituteX;            /* Array of substitute
1169                                          * GlyphIDs--ordered by Coverage Index */
1170   public:
1171   DEFINE_SIZE_MIN (10);
1172 };
1173
1174 struct ReverseChainSingleSubst
1175 {
1176   template <typename context_t>
1177   typename context_t::return_t dispatch (context_t *c) const
1178   {
1179     TRACE_DISPATCH (this, u.format);
1180     if (unlikely (!c->may_dispatch (this, &u.format))) return_trace (c->no_dispatch_return_value ());
1181     switch (u.format) {
1182     case 1: return_trace (c->dispatch (u.format1));
1183     default:return_trace (c->default_return_value ());
1184     }
1185   }
1186
1187   protected:
1188   union {
1189   HBUINT16                              format;         /* Format identifier */
1190   ReverseChainSingleSubstFormat1        format1;
1191   } u;
1192 };
1193
1194
1195
1196 /*
1197  * SubstLookup
1198  */
1199
1200 struct SubstLookupSubTable
1201 {
1202   friend struct Lookup;
1203   friend struct SubstLookup;
1204
1205   enum Type {
1206     Single              = 1,
1207     Multiple            = 2,
1208     Alternate           = 3,
1209     Ligature            = 4,
1210     Context             = 5,
1211     ChainContext        = 6,
1212     Extension           = 7,
1213     ReverseChainSingle  = 8
1214   };
1215
1216   template <typename context_t>
1217   typename context_t::return_t dispatch (context_t *c, unsigned int lookup_type) const
1218   {
1219     TRACE_DISPATCH (this, lookup_type);
1220     switch (lookup_type) {
1221     case Single:                return_trace (u.single.dispatch (c));
1222     case Multiple:              return_trace (u.multiple.dispatch (c));
1223     case Alternate:             return_trace (u.alternate.dispatch (c));
1224     case Ligature:              return_trace (u.ligature.dispatch (c));
1225     case Context:               return_trace (u.context.dispatch (c));
1226     case ChainContext:          return_trace (u.chainContext.dispatch (c));
1227     case Extension:             return_trace (u.extension.dispatch (c));
1228     case ReverseChainSingle:    return_trace (u.reverseChainContextSingle.dispatch (c));
1229     default:                    return_trace (c->default_return_value ());
1230     }
1231   }
1232
1233   protected:
1234   union {
1235   SingleSubst                   single;
1236   MultipleSubst                 multiple;
1237   AlternateSubst                alternate;
1238   LigatureSubst                 ligature;
1239   ContextSubst                  context;
1240   ChainContextSubst             chainContext;
1241   ExtensionSubst                extension;
1242   ReverseChainSingleSubst       reverseChainContextSingle;
1243   } u;
1244   public:
1245   DEFINE_SIZE_MIN (0);
1246 };
1247
1248
1249 struct SubstLookup : Lookup
1250 {
1251   typedef SubstLookupSubTable SubTable;
1252
1253   const SubTable& get_subtable (unsigned int i) const
1254   { return Lookup::get_subtable<SubTable> (i); }
1255
1256   static bool lookup_type_is_reverse (unsigned int lookup_type)
1257   { return lookup_type == SubTable::ReverseChainSingle; }
1258
1259   bool is_reverse () const
1260   {
1261     unsigned int type = get_type ();
1262     if (unlikely (type == SubTable::Extension))
1263       return CastR<ExtensionSubst> (get_subtable(0)).is_reverse ();
1264     return lookup_type_is_reverse (type);
1265   }
1266
1267   bool apply (hb_ot_apply_context_t *c) const
1268   {
1269     TRACE_APPLY (this);
1270     return_trace (dispatch (c));
1271   }
1272
1273   bool intersects (const hb_set_t *glyphs) const
1274   {
1275     hb_intersects_context_t c (glyphs);
1276     return dispatch (&c);
1277   }
1278
1279   hb_closure_context_t::return_t closure (hb_closure_context_t *c, unsigned int this_index) const
1280   {
1281     if (!c->should_visit_lookup (this_index))
1282       return hb_closure_context_t::default_return_value ();
1283
1284     c->set_recurse_func (dispatch_closure_recurse_func);
1285
1286     hb_closure_context_t::return_t ret = dispatch (c);
1287
1288     c->flush ();
1289
1290     return ret;
1291   }
1292
1293   hb_collect_glyphs_context_t::return_t collect_glyphs (hb_collect_glyphs_context_t *c) const
1294   {
1295     c->set_recurse_func (dispatch_recurse_func<hb_collect_glyphs_context_t>);
1296     return dispatch (c);
1297   }
1298
1299   template <typename set_t>
1300   void add_coverage (set_t *glyphs) const
1301   {
1302     hb_add_coverage_context_t<set_t> c (glyphs);
1303     dispatch (&c);
1304   }
1305
1306   bool would_apply (hb_would_apply_context_t *c,
1307                     const hb_ot_layout_lookup_accelerator_t *accel) const
1308   {
1309     TRACE_WOULD_APPLY (this);
1310     if (unlikely (!c->len))  return_trace (false);
1311     if (!accel->may_have (c->glyphs[0]))  return_trace (false);
1312       return_trace (dispatch (c));
1313   }
1314
1315   static bool apply_recurse_func (hb_ot_apply_context_t *c, unsigned int lookup_index);
1316
1317   SubTable& serialize_subtable (hb_serialize_context_t *c,
1318                                        unsigned int i)
1319   { return get_subtables<SubTable> ()[i].serialize (c, this); }
1320
1321   bool serialize_single (hb_serialize_context_t *c,
1322                          uint32_t lookup_props,
1323                          hb_array_t<const GlyphID> glyphs,
1324                          hb_array_t<const GlyphID> substitutes)
1325   {
1326     TRACE_SERIALIZE (this);
1327     if (unlikely (!Lookup::serialize (c, SubTable::Single, lookup_props, 1))) return_trace (false);
1328     return_trace (serialize_subtable (c, 0).u.single.serialize (c, glyphs, substitutes));
1329   }
1330
1331   bool serialize_multiple (hb_serialize_context_t *c,
1332                            uint32_t lookup_props,
1333                            hb_array_t<const GlyphID> glyphs,
1334                            hb_array_t<const unsigned int> substitute_len_list,
1335                            hb_array_t<const GlyphID> substitute_glyphs_list)
1336   {
1337     TRACE_SERIALIZE (this);
1338     if (unlikely (!Lookup::serialize (c, SubTable::Multiple, lookup_props, 1))) return_trace (false);
1339     return_trace (serialize_subtable (c, 0).u.multiple.serialize (c,
1340                                                                   glyphs,
1341                                                                   substitute_len_list,
1342                                                                   substitute_glyphs_list));
1343   }
1344
1345   bool serialize_alternate (hb_serialize_context_t *c,
1346                             uint32_t lookup_props,
1347                             hb_array_t<const GlyphID> glyphs,
1348                             hb_array_t<const unsigned int> alternate_len_list,
1349                             hb_array_t<const GlyphID> alternate_glyphs_list)
1350   {
1351     TRACE_SERIALIZE (this);
1352     if (unlikely (!Lookup::serialize (c, SubTable::Alternate, lookup_props, 1))) return_trace (false);
1353     return_trace (serialize_subtable (c, 0).u.alternate.serialize (c,
1354                                                                    glyphs,
1355                                                                    alternate_len_list,
1356                                                                    alternate_glyphs_list));
1357   }
1358
1359   bool serialize_ligature (hb_serialize_context_t *c,
1360                            uint32_t lookup_props,
1361                            hb_array_t<const GlyphID> first_glyphs,
1362                            hb_array_t<const unsigned int> ligature_per_first_glyph_count_list,
1363                            hb_array_t<const GlyphID> ligatures_list,
1364                            hb_array_t<const unsigned int> component_count_list,
1365                            hb_array_t<const GlyphID> component_list /* Starting from second for each ligature */)
1366   {
1367     TRACE_SERIALIZE (this);
1368     if (unlikely (!Lookup::serialize (c, SubTable::Ligature, lookup_props, 1))) return_trace (false);
1369     return_trace (serialize_subtable (c, 0).u.ligature.serialize (c,
1370                                                                   first_glyphs,
1371                                                                   ligature_per_first_glyph_count_list,
1372                                                                   ligatures_list,
1373                                                                   component_count_list,
1374                                                                   component_list));
1375   }
1376
1377   template <typename context_t>
1378   static typename context_t::return_t dispatch_recurse_func (context_t *c, unsigned int lookup_index);
1379
1380   static hb_closure_context_t::return_t dispatch_closure_recurse_func (hb_closure_context_t *c, unsigned int lookup_index)
1381   {
1382     if (!c->should_visit_lookup (lookup_index))
1383       return HB_VOID;
1384
1385     hb_closure_context_t::return_t ret = dispatch_recurse_func (c, lookup_index);
1386
1387     /* While in theory we should flush here, it will cause timeouts because a recursive
1388      * lookup can keep growing the glyph set.  Skip, and outer loop will retry up to
1389      * HB_CLOSURE_MAX_STAGES time, which should be enough for every realistic font. */
1390     //c->flush ();
1391
1392     return ret;
1393   }
1394
1395   template <typename context_t>
1396   typename context_t::return_t dispatch (context_t *c) const
1397   { return Lookup::dispatch<SubTable> (c); }
1398
1399   bool subset (hb_subset_context_t *c) const
1400   { return Lookup::subset<SubTable> (c); }
1401
1402   bool sanitize (hb_sanitize_context_t *c) const
1403   { return Lookup::sanitize<SubTable> (c); }
1404 };
1405
1406 /*
1407  * GSUB -- Glyph Substitution
1408  * https://docs.microsoft.com/en-us/typography/opentype/spec/gsub
1409  */
1410
1411 struct GSUB : GSUBGPOS
1412 {
1413   static constexpr hb_tag_t tableTag = HB_OT_TAG_GSUB;
1414
1415   const SubstLookup& get_lookup (unsigned int i) const
1416   { return CastR<SubstLookup> (GSUBGPOS::get_lookup (i)); }
1417
1418   bool subset (hb_subset_context_t *c) const
1419   { return GSUBGPOS::subset<SubstLookup> (c); }
1420
1421   bool sanitize (hb_sanitize_context_t *c) const
1422   { return GSUBGPOS::sanitize<SubstLookup> (c); }
1423
1424   HB_INTERNAL bool is_blacklisted (hb_blob_t *blob,
1425                                    hb_face_t *face) const;
1426
1427   typedef GSUBGPOS::accelerator_t<GSUB> accelerator_t;
1428 };
1429
1430
1431 struct GSUB_accelerator_t : GSUB::accelerator_t {};
1432
1433
1434 /* Out-of-class implementation for methods recursing */
1435
1436 /*static*/ inline bool ExtensionSubst::is_reverse () const
1437 {
1438   unsigned int type = get_type ();
1439   if (unlikely (type == SubTable::Extension))
1440     return CastR<ExtensionSubst> (get_subtable<SubTable>()).is_reverse ();
1441   return SubstLookup::lookup_type_is_reverse (type);
1442 }
1443
1444 template <typename context_t>
1445 /*static*/ inline typename context_t::return_t SubstLookup::dispatch_recurse_func (context_t *c, unsigned int lookup_index)
1446 {
1447   const SubstLookup &l = c->face->table.GSUB.get_relaxed ()->table->get_lookup (lookup_index);
1448   return l.dispatch (c);
1449 }
1450
1451 /*static*/ inline bool SubstLookup::apply_recurse_func (hb_ot_apply_context_t *c, unsigned int lookup_index)
1452 {
1453   const SubstLookup &l = c->face->table.GSUB.get_relaxed ()->table->get_lookup (lookup_index);
1454   unsigned int saved_lookup_props = c->lookup_props;
1455   unsigned int saved_lookup_index = c->lookup_index;
1456   c->set_lookup_index (lookup_index);
1457   c->set_lookup_props (l.get_props ());
1458   bool ret = l.dispatch (c);
1459   c->set_lookup_index (saved_lookup_index);
1460   c->set_lookup_props (saved_lookup_props);
1461   return ret;
1462 }
1463
1464 } /* namespace OT */
1465
1466
1467 #endif /* HB_OT_LAYOUT_GSUB_TABLE_HH */