third_party/harfbuzz-ng/src/hb-ot-layout-gsub-table.hh

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