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