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