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