src/hb-ot-layout-gsubgpos.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_GSUBGPOS_HH
  30 #define HB_OT_LAYOUT_GSUBGPOS_HH
  31
  32 #include "hb.hh"
  33 #include "hb-buffer.hh"
  34 #include "hb-map.hh"
  35 #include "hb-set.hh"
  36 #include "hb-ot-map.hh"
  37 #include "hb-ot-layout-common.hh"
  38 #include "hb-ot-layout-gdef-table.hh"
  39
  40
  41 namespace OT {
  42
  43
  44 struct hb_intersects_context_t :
  45        hb_dispatch_context_t<hb_intersects_context_t, bool, 0>
  46 {
  47   const char *get_name () { return "INTERSECTS"; }
  48   template <typename T>
  49   return_t dispatch (const T &obj) { return obj.intersects (this->glyphs); }
  50   static return_t default_return_value () { return false; }
  51   bool stop_sublookup_iteration (return_t r) const { return r; }
  52
  53   const hb_set_t *glyphs;
  54   unsigned int debug_depth;
  55
  56   hb_intersects_context_t (const hb_set_t *glyphs_) :
  57                              glyphs (glyphs_),
  58                              debug_depth (0) {}
  59 };
  60
  61 struct hb_closure_context_t :
  62        hb_dispatch_context_t<hb_closure_context_t, hb_void_t, 0>
  63 {
  64   const char *get_name () { return "CLOSURE"; }
  65   typedef return_t (*recurse_func_t) (hb_closure_context_t *c, unsigned int lookup_index);
  66   template <typename T>
  67   return_t dispatch (const T &obj) { obj.closure (this); return HB_VOID; }
  68   static return_t default_return_value () { return HB_VOID; }
  69   void recurse (unsigned int lookup_index)
  70   {
  71     if (unlikely (nesting_level_left == 0 || !recurse_func))
  72       return;
  73
  74     nesting_level_left--;
  75     recurse_func (this, lookup_index);
  76     nesting_level_left++;
  77   }
  78
  79   bool should_visit_lookup (unsigned int lookup_index)
  80   {
  81     if (is_lookup_done (lookup_index))
  82       return false;
  83     done_lookups->set (lookup_index, glyphs->get_population ());
  84     return true;
  85   }
  86
  87   bool is_lookup_done (unsigned int lookup_index)
  88   {
  89     /* Have we visited this lookup with the current set of glyphs? */
  90     return done_lookups->get (lookup_index) == glyphs->get_population ();
  91   }
  92
  93   hb_face_t *face;
  94   hb_set_t *glyphs;
  95   hb_set_t out[1];
  96   recurse_func_t recurse_func;
  97   unsigned int nesting_level_left;
  98   unsigned int debug_depth;
  99
 100   hb_closure_context_t (hb_face_t *face_,
 101                         hb_set_t *glyphs_,
 102                         hb_map_t *done_lookups_,
 103                         unsigned int nesting_level_left_ = HB_MAX_NESTING_LEVEL) :
 104                           face (face_),
 105                           glyphs (glyphs_),
 106                           recurse_func (nullptr),
 107                           nesting_level_left (nesting_level_left_),
 108                           debug_depth (0),
 109                           done_lookups (done_lookups_) {}
 110
 111   ~hb_closure_context_t () { flush (); }
 112
 113   void set_recurse_func (recurse_func_t func) { recurse_func = func; }
 114
 115   void flush ()
 116   {
 117     hb_set_union (glyphs, out);
 118     hb_set_clear (out);
 119   }
 120
 121   private:
 122   hb_map_t *done_lookups;
 123 };
 124
 125
 126 struct hb_would_apply_context_t :
 127        hb_dispatch_context_t<hb_would_apply_context_t, bool, HB_DEBUG_WOULD_APPLY>
 128 {
 129   const char *get_name () { return "WOULD_APPLY"; }
 130   template <typename T>
 131   return_t dispatch (const T &obj) { return obj.would_apply (this); }
 132   static return_t default_return_value () { return false; }
 133   bool stop_sublookup_iteration (return_t r) const { return r; }
 134
 135   hb_face_t *face;
 136   const hb_codepoint_t *glyphs;
 137   unsigned int len;
 138   bool zero_context;
 139   unsigned int debug_depth;
 140
 141   hb_would_apply_context_t (hb_face_t *face_,
 142                             const hb_codepoint_t *glyphs_,
 143                             unsigned int len_,
 144                             bool zero_context_) :
 145                               face (face_),
 146                               glyphs (glyphs_),
 147                               len (len_),
 148                               zero_context (zero_context_),
 149                               debug_depth (0) {}
 150 };
 151
 152
 153 struct hb_collect_glyphs_context_t :
 154        hb_dispatch_context_t<hb_collect_glyphs_context_t, hb_void_t, 0>
 155 {
 156   const char *get_name () { return "COLLECT_GLYPHS"; }
 157   typedef return_t (*recurse_func_t) (hb_collect_glyphs_context_t *c, unsigned int lookup_index);
 158   template <typename T>
 159   return_t dispatch (const T &obj) { obj.collect_glyphs (this); return HB_VOID; }
 160   static return_t default_return_value () { return HB_VOID; }
 161   void recurse (unsigned int lookup_index)
 162   {
 163     if (unlikely (nesting_level_left == 0 || !recurse_func))
 164       return;
 165
 166     /* Note that GPOS sets recurse_func to nullptr already, so it doesn't get
 167      * past the previous check.  For GSUB, we only want to collect the output
 168      * glyphs in the recursion.  If output is not requested, we can go home now.
 169      *
 170      * Note further, that the above is not exactly correct.  A recursed lookup
 171      * is allowed to match input that is not matched in the context, but that's
 172      * not how most fonts are built.  It's possible to relax that and recurse
 173      * with all sets here if it proves to be an issue.
 174      */
 175
 176     if (output == hb_set_get_empty ())
 177       return;
 178
 179     /* Return if new lookup was recursed to before. */
 180     if (recursed_lookups->has (lookup_index))
 181       return;
 182
 183     hb_set_t *old_before = before;
 184     hb_set_t *old_input  = input;
 185     hb_set_t *old_after  = after;
 186     before = input = after = hb_set_get_empty ();
 187
 188     nesting_level_left--;
 189     recurse_func (this, lookup_index);
 190     nesting_level_left++;
 191
 192     before = old_before;
 193     input  = old_input;
 194     after  = old_after;
 195
 196     recursed_lookups->add (lookup_index);
 197   }
 198
 199   hb_face_t *face;
 200   hb_set_t *before;
 201   hb_set_t *input;
 202   hb_set_t *after;
 203   hb_set_t *output;
 204   recurse_func_t recurse_func;
 205   hb_set_t *recursed_lookups;
 206   unsigned int nesting_level_left;
 207   unsigned int debug_depth;
 208
 209   hb_collect_glyphs_context_t (hb_face_t *face_,
 210                                hb_set_t  *glyphs_before, /* OUT.  May be NULL */
 211                                hb_set_t  *glyphs_input,  /* OUT.  May be NULL */
 212                                hb_set_t  *glyphs_after,  /* OUT.  May be NULL */
 213                                hb_set_t  *glyphs_output, /* OUT.  May be NULL */
 214                                unsigned int nesting_level_left_ = HB_MAX_NESTING_LEVEL) :
 215                               face (face_),
 216                               before (glyphs_before ? glyphs_before : hb_set_get_empty ()),
 217                               input  (glyphs_input  ? glyphs_input  : hb_set_get_empty ()),
 218                               after  (glyphs_after  ? glyphs_after  : hb_set_get_empty ()),
 219                               output (glyphs_output ? glyphs_output : hb_set_get_empty ()),
 220                               recurse_func (nullptr),
 221                               recursed_lookups (hb_set_create ()),
 222                               nesting_level_left (nesting_level_left_),
 223                               debug_depth (0) {}
 224   ~hb_collect_glyphs_context_t () { hb_set_destroy (recursed_lookups); }
 225
 226   void set_recurse_func (recurse_func_t func) { recurse_func = func; }
 227 };
 228
 229
 230
 231 template <typename set_t>
 232 struct hb_add_coverage_context_t :
 233        hb_dispatch_context_t<hb_add_coverage_context_t<set_t>, const Coverage &, HB_DEBUG_GET_COVERAGE>
 234 {
 235   const char *get_name () { return "GET_COVERAGE"; }
 236   typedef const Coverage &return_t;
 237   template <typename T>
 238   return_t dispatch (const T &obj) { return obj.get_coverage (); }
 239   static return_t default_return_value () { return Null(Coverage); }
 240   bool stop_sublookup_iteration (return_t r) const
 241   {
 242     r.add_coverage (set);
 243     return false;
 244   }
 245
 246   hb_add_coverage_context_t (set_t *set_) :
 247                             set (set_),
 248                             debug_depth (0) {}
 249
 250   set_t *set;
 251   unsigned int debug_depth;
 252 };
 253
 254
 255 struct hb_ot_apply_context_t :
 256        hb_dispatch_context_t<hb_ot_apply_context_t, bool, HB_DEBUG_APPLY>
 257 {
 258   struct matcher_t
 259   {
 260     matcher_t () :
 261              lookup_props (0),
 262              ignore_zwnj (false),
 263              ignore_zwj (false),
 264              mask (-1),
 265 #define arg1(arg) (arg) /* Remove the macro to see why it's needed! */
 266              syllable arg1(0),
 267 #undef arg1
 268              match_func (nullptr),
 269              match_data (nullptr) {}
 270
 271     typedef bool (*match_func_t) (hb_codepoint_t glyph_id, const HBUINT16 &value, const void *data);
 272
 273     void set_ignore_zwnj (bool ignore_zwnj_) { ignore_zwnj = ignore_zwnj_; }
 274     void set_ignore_zwj (bool ignore_zwj_) { ignore_zwj = ignore_zwj_; }
 275     void set_lookup_props (unsigned int lookup_props_) { lookup_props = lookup_props_; }
 276     void set_mask (hb_mask_t mask_) { mask = mask_; }
 277     void set_syllable (uint8_t syllable_)  { syllable = syllable_; }
 278     void set_match_func (match_func_t match_func_,
 279                                 const void *match_data_)
 280     { match_func = match_func_; match_data = match_data_; }
 281
 282     enum may_match_t {
 283       MATCH_NO,
 284       MATCH_YES,
 285       MATCH_MAYBE
 286     };
 287
 288     may_match_t may_match (const hb_glyph_info_t &info,
 289                                   const HBUINT16        *glyph_data) const
 290     {
 291       if (!(info.mask & mask) ||
 292           (syllable && syllable != info.syllable ()))
 293         return MATCH_NO;
 294
 295       if (match_func)
 296         return match_func (info.codepoint, *glyph_data, match_data) ? MATCH_YES : MATCH_NO;
 297
 298       return MATCH_MAYBE;
 299     }
 300
 301     enum may_skip_t {
 302       SKIP_NO,
 303       SKIP_YES,
 304       SKIP_MAYBE
 305     };
 306
 307     may_skip_t may_skip (const hb_ot_apply_context_t *c,
 308                          const hb_glyph_info_t       &info) const
 309     {
 310       if (!c->check_glyph_property (&info, lookup_props))
 311         return SKIP_YES;
 312
 313       if (unlikely (_hb_glyph_info_is_default_ignorable_and_not_hidden (&info) &&
 314                     (ignore_zwnj || !_hb_glyph_info_is_zwnj (&info)) &&
 315                     (ignore_zwj || !_hb_glyph_info_is_zwj (&info))))
 316         return SKIP_MAYBE;
 317
 318       return SKIP_NO;
 319     }
 320
 321     protected:
 322     unsigned int lookup_props;
 323     bool ignore_zwnj;
 324     bool ignore_zwj;
 325     hb_mask_t mask;
 326     uint8_t syllable;
 327     match_func_t match_func;
 328     const void *match_data;
 329   };
 330
 331   struct skipping_iterator_t
 332   {
 333     void init (hb_ot_apply_context_t *c_, bool context_match = false)
 334     {
 335       c = c_;
 336       match_glyph_data = nullptr;
 337       matcher.set_match_func (nullptr, nullptr);
 338       matcher.set_lookup_props (c->lookup_props);
 339       /* Ignore ZWNJ if we are matching GPOS, or matching GSUB context and asked to. */
 340       matcher.set_ignore_zwnj (c->table_index == 1 || (context_match && c->auto_zwnj));
 341       /* Ignore ZWJ if we are matching context, or asked to. */
 342       matcher.set_ignore_zwj  (context_match || c->auto_zwj);
 343       matcher.set_mask (context_match ? -1 : c->lookup_mask);
 344     }
 345     void set_lookup_props (unsigned int lookup_props)
 346     {
 347       matcher.set_lookup_props (lookup_props);
 348     }
 349     void set_match_func (matcher_t::match_func_t match_func_,
 350                          const void *match_data_,
 351                          const HBUINT16 glyph_data[])
 352     {
 353       matcher.set_match_func (match_func_, match_data_);
 354       match_glyph_data = glyph_data;
 355     }
 356
 357     void reset (unsigned int start_index_,
 358                        unsigned int num_items_)
 359     {
 360       idx = start_index_;
 361       num_items = num_items_;
 362       end = c->buffer->len;
 363       matcher.set_syllable (start_index_ == c->buffer->idx ? c->buffer->cur().syllable () : 0);
 364     }
 365
 366     void reject () { num_items++; match_glyph_data--; }
 367
 368     matcher_t::may_skip_t
 369     may_skip (const hb_glyph_info_t &info) const
 370     { return matcher.may_skip (c, info); }
 371
 372     bool next ()
 373     {
 374       assert (num_items > 0);
 375       while (idx + num_items < end)
 376       {
 377         idx++;
 378         const hb_glyph_info_t &info = c->buffer->info[idx];
 379
 380         matcher_t::may_skip_t skip = matcher.may_skip (c, info);
 381         if (unlikely (skip == matcher_t::SKIP_YES))
 382           continue;
 383
 384         matcher_t::may_match_t match = matcher.may_match (info, match_glyph_data);
 385         if (match == matcher_t::MATCH_YES ||
 386             (match == matcher_t::MATCH_MAYBE &&
 387              skip == matcher_t::SKIP_NO))
 388         {
 389           num_items--;
 390           match_glyph_data++;
 391           return true;
 392         }
 393
 394         if (skip == matcher_t::SKIP_NO)
 395           return false;
 396       }
 397       return false;
 398     }
 399     bool prev ()
 400     {
 401       assert (num_items > 0);
 402       while (idx > num_items - 1)
 403       {
 404         idx--;
 405         const hb_glyph_info_t &info = c->buffer->out_info[idx];
 406
 407         matcher_t::may_skip_t skip = matcher.may_skip (c, info);
 408         if (unlikely (skip == matcher_t::SKIP_YES))
 409           continue;
 410
 411         matcher_t::may_match_t match = matcher.may_match (info, match_glyph_data);
 412         if (match == matcher_t::MATCH_YES ||
 413             (match == matcher_t::MATCH_MAYBE &&
 414              skip == matcher_t::SKIP_NO))
 415         {
 416           num_items--;
 417           match_glyph_data++;
 418           return true;
 419         }
 420
 421         if (skip == matcher_t::SKIP_NO)
 422           return false;
 423       }
 424       return false;
 425     }
 426
 427     unsigned int idx;
 428     protected:
 429     hb_ot_apply_context_t *c;
 430     matcher_t matcher;
 431     const HBUINT16 *match_glyph_data;
 432
 433     unsigned int num_items;
 434     unsigned int end;
 435   };
 436
 437
 438   const char *get_name () { return "APPLY"; }
 439   typedef return_t (*recurse_func_t) (hb_ot_apply_context_t *c, unsigned int lookup_index);
 440   template <typename T>
 441   return_t dispatch (const T &obj) { return obj.apply (this); }
 442   static return_t default_return_value () { return false; }
 443   bool stop_sublookup_iteration (return_t r) const { return r; }
 444   return_t recurse (unsigned int sub_lookup_index)
 445   {
 446     if (unlikely (nesting_level_left == 0 || !recurse_func || buffer->max_ops-- <= 0))
 447       return default_return_value ();
 448
 449     nesting_level_left--;
 450     bool ret = recurse_func (this, sub_lookup_index);
 451     nesting_level_left++;
 452     return ret;
 453   }
 454
 455   skipping_iterator_t iter_input, iter_context;
 456
 457   hb_font_t *font;
 458   hb_face_t *face;
 459   hb_buffer_t *buffer;
 460   recurse_func_t recurse_func;
 461   const GDEF &gdef;
 462   const VariationStore &var_store;
 463
 464   hb_direction_t direction;
 465   hb_mask_t lookup_mask;
 466   unsigned int table_index; /* GSUB/GPOS */
 467   unsigned int lookup_index;
 468   unsigned int lookup_props;
 469   unsigned int nesting_level_left;
 470   unsigned int debug_depth;
 471
 472   bool has_glyph_classes;
 473   bool auto_zwnj;
 474   bool auto_zwj;
 475   bool random;
 476
 477   uint32_t random_state;
 478
 479
 480   hb_ot_apply_context_t (unsigned int table_index_,
 481                       hb_font_t *font_,
 482                       hb_buffer_t *buffer_) :
 483                         iter_input (), iter_context (),
 484                         font (font_), face (font->face), buffer (buffer_),
 485                         recurse_func (nullptr),
 486                         gdef (*face->table.GDEF->table),
 487                         var_store (gdef.get_var_store ()),
 488                         direction (buffer_->props.direction),
 489                         lookup_mask (1),
 490                         table_index (table_index_),
 491                         lookup_index ((unsigned int) -1),
 492                         lookup_props (0),
 493                         nesting_level_left (HB_MAX_NESTING_LEVEL),
 494                         debug_depth (0),
 495                         has_glyph_classes (gdef.has_glyph_classes ()),
 496                         auto_zwnj (true),
 497                         auto_zwj (true),
 498                         random (false),
 499                         random_state (1) { init_iters (); }
 500
 501   void init_iters ()
 502   {
 503     iter_input.init (this, false);
 504     iter_context.init (this, true);
 505   }
 506
 507   void set_lookup_mask (hb_mask_t mask) { lookup_mask = mask; init_iters (); }
 508   void set_auto_zwj (bool auto_zwj_) { auto_zwj = auto_zwj_; init_iters (); }
 509   void set_auto_zwnj (bool auto_zwnj_) { auto_zwnj = auto_zwnj_; init_iters (); }
 510   void set_random (bool random_) { random = random_; }
 511   void set_recurse_func (recurse_func_t func) { recurse_func = func; }
 512   void set_lookup_index (unsigned int lookup_index_) { lookup_index = lookup_index_; }
 513   void set_lookup_props (unsigned int lookup_props_) { lookup_props = lookup_props_; init_iters (); }
 514
 515   uint32_t random_number ()
 516   {
 517     /* http://www.cplusplus.com/reference/random/minstd_rand/ */
 518     random_state = random_state * 48271 % 2147483647;
 519     return random_state;
 520   }
 521
 522   bool match_properties_mark (hb_codepoint_t  glyph,
 523                               unsigned int    glyph_props,
 524                               unsigned int    match_props) const
 525   {
 526     /* If using mark filtering sets, the high short of
 527      * match_props has the set index.
 528      */
 529     if (match_props & LookupFlag::UseMarkFilteringSet)
 530       return gdef.mark_set_covers (match_props >> 16, glyph);
 531
 532     /* The second byte of match_props has the meaning
 533      * "ignore marks of attachment type different than
 534      * the attachment type specified."
 535      */
 536     if (match_props & LookupFlag::MarkAttachmentType)
 537       return (match_props & LookupFlag::MarkAttachmentType) == (glyph_props & LookupFlag::MarkAttachmentType);
 538
 539     return true;
 540   }
 541
 542   bool check_glyph_property (const hb_glyph_info_t *info,
 543                              unsigned int  match_props) const
 544   {
 545     hb_codepoint_t glyph = info->codepoint;
 546     unsigned int glyph_props = _hb_glyph_info_get_glyph_props (info);
 547
 548     /* Not covered, if, for example, glyph class is ligature and
 549      * match_props includes LookupFlags::IgnoreLigatures
 550      */
 551     if (glyph_props & match_props & LookupFlag::IgnoreFlags)
 552       return false;
 553
 554     if (unlikely (glyph_props & HB_OT_LAYOUT_GLYPH_PROPS_MARK))
 555       return match_properties_mark (glyph, glyph_props, match_props);
 556
 557     return true;
 558   }
 559
 560   void _set_glyph_props (hb_codepoint_t glyph_index,
 561                           unsigned int class_guess = 0,
 562                           bool ligature = false,
 563                           bool component = false) const
 564   {
 565     unsigned int add_in = _hb_glyph_info_get_glyph_props (&buffer->cur()) &
 566                           HB_OT_LAYOUT_GLYPH_PROPS_PRESERVE;
 567     add_in |= HB_OT_LAYOUT_GLYPH_PROPS_SUBSTITUTED;
 568     if (ligature)
 569     {
 570       add_in |= HB_OT_LAYOUT_GLYPH_PROPS_LIGATED;
 571       /* In the only place that the MULTIPLIED bit is used, Uniscribe
 572        * seems to only care about the "last" transformation between
 573        * Ligature and Multiple substitutions.  Ie. if you ligate, expand,
 574        * and ligate again, it forgives the multiplication and acts as
 575        * if only ligation happened.  As such, clear MULTIPLIED bit.
 576        */
 577       add_in &= ~HB_OT_LAYOUT_GLYPH_PROPS_MULTIPLIED;
 578     }
 579     if (component)
 580       add_in |= HB_OT_LAYOUT_GLYPH_PROPS_MULTIPLIED;
 581     if (likely (has_glyph_classes))
 582       _hb_glyph_info_set_glyph_props (&buffer->cur(), add_in | gdef.get_glyph_props (glyph_index));
 583     else if (class_guess)
 584       _hb_glyph_info_set_glyph_props (&buffer->cur(), add_in | class_guess);
 585   }
 586
 587   void replace_glyph (hb_codepoint_t glyph_index) const
 588   {
 589     _set_glyph_props (glyph_index);
 590     buffer->replace_glyph (glyph_index);
 591   }
 592   void replace_glyph_inplace (hb_codepoint_t glyph_index) const
 593   {
 594     _set_glyph_props (glyph_index);
 595     buffer->cur().codepoint = glyph_index;
 596   }
 597   void replace_glyph_with_ligature (hb_codepoint_t glyph_index,
 598                                            unsigned int class_guess) const
 599   {
 600     _set_glyph_props (glyph_index, class_guess, true);
 601     buffer->replace_glyph (glyph_index);
 602   }
 603   void output_glyph_for_component (hb_codepoint_t glyph_index,
 604                                           unsigned int class_guess) const
 605   {
 606     _set_glyph_props (glyph_index, class_guess, false, true);
 607     buffer->output_glyph (glyph_index);
 608   }
 609 };
 610
 611
 612 struct hb_get_subtables_context_t :
 613        hb_dispatch_context_t<hb_get_subtables_context_t, hb_void_t, HB_DEBUG_APPLY>
 614 {
 615   template <typename Type>
 616   static bool apply_to (const void *obj, OT::hb_ot_apply_context_t *c)
 617   {
 618     const Type *typed_obj = (const Type *) obj;
 619     return typed_obj->apply (c);
 620   }
 621
 622   typedef bool (*hb_apply_func_t) (const void *obj, OT::hb_ot_apply_context_t *c);
 623
 624   struct hb_applicable_t
 625   {
 626     template <typename T>
 627     void init (const T &obj_, hb_apply_func_t apply_func_)
 628     {
 629       obj = &obj_;
 630       apply_func = apply_func_;
 631       digest.init ();
 632       obj_.get_coverage ().add_coverage (&digest);
 633     }
 634
 635     bool apply (OT::hb_ot_apply_context_t *c) const
 636     {
 637       return digest.may_have (c->buffer->cur().codepoint) && apply_func (obj, c);
 638     }
 639
 640     private:
 641     const void *obj;
 642     hb_apply_func_t apply_func;
 643     hb_set_digest_t digest;
 644   };
 645
 646   typedef hb_vector_t<hb_applicable_t> array_t;
 647
 648   /* Dispatch interface. */
 649   const char *get_name () { return "GET_SUBTABLES"; }
 650   template <typename T>
 651   return_t dispatch (const T &obj)
 652   {
 653     hb_applicable_t *entry = array.push();
 654     entry->init (obj, apply_to<T>);
 655     return HB_VOID;
 656   }
 657   static return_t default_return_value () { return HB_VOID; }
 658
 659   hb_get_subtables_context_t (array_t &array_) :
 660                               array (array_),
 661                               debug_depth (0) {}
 662
 663   array_t &array;
 664   unsigned int debug_depth;
 665 };
 666
 667
 668
 669
 670 typedef bool (*intersects_func_t) (const hb_set_t *glyphs, const HBUINT16 &value, const void *data);
 671 typedef void (*collect_glyphs_func_t) (hb_set_t *glyphs, const HBUINT16 &value, const void *data);
 672 typedef bool (*match_func_t) (hb_codepoint_t glyph_id, const HBUINT16 &value, const void *data);
 673
 674 struct ContextClosureFuncs
 675 {
 676   intersects_func_t intersects;
 677 };
 678 struct ContextCollectGlyphsFuncs
 679 {
 680   collect_glyphs_func_t collect;
 681 };
 682 struct ContextApplyFuncs
 683 {
 684   match_func_t match;
 685 };
 686
 687
 688 static inline bool intersects_glyph (const hb_set_t *glyphs, const HBUINT16 &value, const void *data HB_UNUSED)
 689 {
 690   return glyphs->has (value);
 691 }
 692 static inline bool intersects_class (const hb_set_t *glyphs, const HBUINT16 &value, const void *data)
 693 {
 694   const ClassDef &class_def = *reinterpret_cast<const ClassDef *>(data);
 695   return class_def.intersects_class (glyphs, value);
 696 }
 697 static inline bool intersects_coverage (const hb_set_t *glyphs, const HBUINT16 &value, const void *data)
 698 {
 699   const OffsetTo<Coverage> &coverage = (const OffsetTo<Coverage>&)value;
 700   return (data+coverage).intersects (glyphs);
 701 }
 702
 703 static inline bool intersects_array (const hb_set_t *glyphs,
 704                                      unsigned int count,
 705                                      const HBUINT16 values[],
 706                                      intersects_func_t intersects_func,
 707                                      const void *intersects_data)
 708 {
 709   for (unsigned int i = 0; i < count; i++)
 710     if (likely (!intersects_func (glyphs, values[i], intersects_data)))
 711       return false;
 712   return true;
 713 }
 714
 715
 716 static inline void collect_glyph (hb_set_t *glyphs, const HBUINT16 &value, const void *data HB_UNUSED)
 717 {
 718   glyphs->add (value);
 719 }
 720 static inline void collect_class (hb_set_t *glyphs, const HBUINT16 &value, const void *data)
 721 {
 722   const ClassDef &class_def = *reinterpret_cast<const ClassDef *>(data);
 723   class_def.add_class (glyphs, value);
 724 }
 725 static inline void collect_coverage (hb_set_t *glyphs, const HBUINT16 &value, const void *data)
 726 {
 727   const OffsetTo<Coverage> &coverage = (const OffsetTo<Coverage>&)value;
 728   (data+coverage).add_coverage (glyphs);
 729 }
 730 static inline void collect_array (hb_collect_glyphs_context_t *c HB_UNUSED,
 731                                   hb_set_t *glyphs,
 732                                   unsigned int count,
 733                                   const HBUINT16 values[],
 734                                   collect_glyphs_func_t collect_func,
 735                                   const void *collect_data)
 736 {
 737   for (unsigned int i = 0; i < count; i++)
 738     collect_func (glyphs, values[i], collect_data);
 739 }
 740
 741
 742 static inline bool match_glyph (hb_codepoint_t glyph_id, const HBUINT16 &value, const void *data HB_UNUSED)
 743 {
 744   return glyph_id == value;
 745 }
 746 static inline bool match_class (hb_codepoint_t glyph_id, const HBUINT16 &value, const void *data)
 747 {
 748   const ClassDef &class_def = *reinterpret_cast<const ClassDef *>(data);
 749   return class_def.get_class (glyph_id) == value;
 750 }
 751 static inline bool match_coverage (hb_codepoint_t glyph_id, const HBUINT16 &value, const void *data)
 752 {
 753   const OffsetTo<Coverage> &coverage = (const OffsetTo<Coverage>&)value;
 754   return (data+coverage).get_coverage (glyph_id) != NOT_COVERED;
 755 }
 756
 757 static inline bool would_match_input (hb_would_apply_context_t *c,
 758                                       unsigned int count, /* Including the first glyph (not matched) */
 759                                       const HBUINT16 input[], /* Array of input values--start with second glyph */
 760                                       match_func_t match_func,
 761                                       const void *match_data)
 762 {
 763   if (count != c->len)
 764     return false;
 765
 766   for (unsigned int i = 1; i < count; i++)
 767     if (likely (!match_func (c->glyphs[i], input[i - 1], match_data)))
 768       return false;
 769
 770   return true;
 771 }
 772 static inline bool match_input (hb_ot_apply_context_t *c,
 773                                 unsigned int count, /* Including the first glyph (not matched) */
 774                                 const HBUINT16 input[], /* Array of input values--start with second glyph */
 775                                 match_func_t match_func,
 776                                 const void *match_data,
 777                                 unsigned int *end_offset,
 778                                 unsigned int match_positions[HB_MAX_CONTEXT_LENGTH],
 779                                 unsigned int *p_total_component_count = nullptr)
 780 {
 781   TRACE_APPLY (nullptr);
 782
 783   if (unlikely (count > HB_MAX_CONTEXT_LENGTH)) return_trace (false);
 784
 785   hb_buffer_t *buffer = c->buffer;
 786
 787   hb_ot_apply_context_t::skipping_iterator_t &skippy_iter = c->iter_input;
 788   skippy_iter.reset (buffer->idx, count - 1);
 789   skippy_iter.set_match_func (match_func, match_data, input);
 790
 791   /*
 792    * This is perhaps the trickiest part of OpenType...  Remarks:
 793    *
 794    * - If all components of the ligature were marks, we call this a mark ligature.
 795    *
 796    * - If there is no GDEF, and the ligature is NOT a mark ligature, we categorize
 797    *   it as a ligature glyph.
 798    *
 799    * - Ligatures cannot be formed across glyphs attached to different components
 800    *   of previous ligatures.  Eg. the sequence is LAM,SHADDA,LAM,FATHA,HEH, and
 801    *   LAM,LAM,HEH form a ligature, leaving SHADDA,FATHA next to eachother.
 802    *   However, it would be wrong to ligate that SHADDA,FATHA sequence.
 803    *   There are a couple of exceptions to this:
 804    *
 805    *   o If a ligature tries ligating with marks that belong to it itself, go ahead,
 806    *     assuming that the font designer knows what they are doing (otherwise it can
 807    *     break Indic stuff when a matra wants to ligate with a conjunct,
 808    *
 809    *   o If two marks want to ligate and they belong to different components of the
 810    *     same ligature glyph, and said ligature glyph is to be ignored according to
 811    *     mark-filtering rules, then allow.
 812    *     https://github.com/harfbuzz/harfbuzz/issues/545
 813    */
 814
 815   unsigned int total_component_count = 0;
 816   total_component_count += _hb_glyph_info_get_lig_num_comps (&buffer->cur());
 817
 818   unsigned int first_lig_id = _hb_glyph_info_get_lig_id (&buffer->cur());
 819   unsigned int first_lig_comp = _hb_glyph_info_get_lig_comp (&buffer->cur());
 820
 821   enum {
 822     LIGBASE_NOT_CHECKED,
 823     LIGBASE_MAY_NOT_SKIP,
 824     LIGBASE_MAY_SKIP
 825   } ligbase = LIGBASE_NOT_CHECKED;
 826
 827   match_positions[0] = buffer->idx;
 828   for (unsigned int i = 1; i < count; i++)
 829   {
 830     if (!skippy_iter.next ()) return_trace (false);
 831
 832     match_positions[i] = skippy_iter.idx;
 833
 834     unsigned int this_lig_id = _hb_glyph_info_get_lig_id (&buffer->info[skippy_iter.idx]);
 835     unsigned int this_lig_comp = _hb_glyph_info_get_lig_comp (&buffer->info[skippy_iter.idx]);
 836
 837     if (first_lig_id && first_lig_comp)
 838     {
 839       /* If first component was attached to a previous ligature component,
 840        * all subsequent components should be attached to the same ligature
 841        * component, otherwise we shouldn't ligate them... */
 842       if (first_lig_id != this_lig_id || first_lig_comp != this_lig_comp)
 843       {
 844         /* ...unless, we are attached to a base ligature and that base
 845          * ligature is ignorable. */
 846         if (ligbase == LIGBASE_NOT_CHECKED)
 847         {
 848           bool found = false;
 849           const hb_glyph_info_t *out = buffer->out_info;
 850           unsigned int j = buffer->out_len;
 851           while (j && _hb_glyph_info_get_lig_id (&out[j - 1]) == first_lig_id)
 852           {
 853             if (_hb_glyph_info_get_lig_comp (&out[j - 1]) == 0)
 854             {
 855               j--;
 856               found = true;
 857               break;
 858             }
 859             j--;
 860           }
 861
 862           if (found && skippy_iter.may_skip (out[j]) == hb_ot_apply_context_t::matcher_t::SKIP_YES)
 863             ligbase = LIGBASE_MAY_SKIP;
 864           else
 865             ligbase = LIGBASE_MAY_NOT_SKIP;
 866         }
 867
 868         if (ligbase == LIGBASE_MAY_NOT_SKIP)
 869           return_trace (false);
 870       }
 871     }
 872     else
 873     {
 874       /* If first component was NOT attached to a previous ligature component,
 875        * all subsequent components should also NOT be attached to any ligature
 876        * component, unless they are attached to the first component itself! */
 877       if (this_lig_id && this_lig_comp && (this_lig_id != first_lig_id))
 878         return_trace (false);
 879     }
 880
 881     total_component_count += _hb_glyph_info_get_lig_num_comps (&buffer->info[skippy_iter.idx]);
 882   }
 883
 884   *end_offset = skippy_iter.idx - buffer->idx + 1;
 885
 886   if (p_total_component_count)
 887     *p_total_component_count = total_component_count;
 888
 889   return_trace (true);
 890 }
 891 static inline bool ligate_input (hb_ot_apply_context_t *c,
 892                                  unsigned int count, /* Including the first glyph */
 893                                  const unsigned int match_positions[HB_MAX_CONTEXT_LENGTH], /* Including the first glyph */
 894                                  unsigned int match_length,
 895                                  hb_codepoint_t lig_glyph,
 896                                  unsigned int total_component_count)
 897 {
 898   TRACE_APPLY (nullptr);
 899
 900   hb_buffer_t *buffer = c->buffer;
 901
 902   buffer->merge_clusters (buffer->idx, buffer->idx + match_length);
 903
 904   /* - If a base and one or more marks ligate, consider that as a base, NOT
 905    *   ligature, such that all following marks can still attach to it.
 906    *   https://github.com/harfbuzz/harfbuzz/issues/1109
 907    *
 908    * - If all components of the ligature were marks, we call this a mark ligature.
 909    *   If it *is* a mark ligature, we don't allocate a new ligature id, and leave
 910    *   the ligature to keep its old ligature id.  This will allow it to attach to
 911    *   a base ligature in GPOS.  Eg. if the sequence is: LAM,LAM,SHADDA,FATHA,HEH,
 912    *   and LAM,LAM,HEH for a ligature, they will leave SHADDA and FATHA with a
 913    *   ligature id and component value of 2.  Then if SHADDA,FATHA form a ligature
 914    *   later, we don't want them to lose their ligature id/component, otherwise
 915    *   GPOS will fail to correctly position the mark ligature on top of the
 916    *   LAM,LAM,HEH ligature.  See:
 917    *     https://bugzilla.gnome.org/show_bug.cgi?id=676343
 918    *
 919    * - If a ligature is formed of components that some of which are also ligatures
 920    *   themselves, and those ligature components had marks attached to *their*
 921    *   components, we have to attach the marks to the new ligature component
 922    *   positions!  Now *that*'s tricky!  And these marks may be following the
 923    *   last component of the whole sequence, so we should loop forward looking
 924    *   for them and update them.
 925    *
 926    *   Eg. the sequence is LAM,LAM,SHADDA,FATHA,HEH, and the font first forms a
 927    *   'calt' ligature of LAM,HEH, leaving the SHADDA and FATHA with a ligature
 928    *   id and component == 1.  Now, during 'liga', the LAM and the LAM-HEH ligature
 929    *   form a LAM-LAM-HEH ligature.  We need to reassign the SHADDA and FATHA to
 930    *   the new ligature with a component value of 2.
 931    *
 932    *   This in fact happened to a font...  See:
 933    *   https://bugzilla.gnome.org/show_bug.cgi?id=437633
 934    */
 935
 936   bool is_base_ligature = _hb_glyph_info_is_base_glyph (&buffer->info[match_positions[0]]);
 937   bool is_mark_ligature = _hb_glyph_info_is_mark (&buffer->info[match_positions[0]]);
 938   for (unsigned int i = 1; i < count; i++)
 939     if (!_hb_glyph_info_is_mark (&buffer->info[match_positions[i]]))
 940     {
 941       is_base_ligature = false;
 942       is_mark_ligature = false;
 943       break;
 944     }
 945   bool is_ligature = !is_base_ligature && !is_mark_ligature;
 946
 947   unsigned int klass = is_ligature ? HB_OT_LAYOUT_GLYPH_PROPS_LIGATURE : 0;
 948   unsigned int lig_id = is_ligature ? _hb_allocate_lig_id (buffer) : 0;
 949   unsigned int last_lig_id = _hb_glyph_info_get_lig_id (&buffer->cur());
 950   unsigned int last_num_components = _hb_glyph_info_get_lig_num_comps (&buffer->cur());
 951   unsigned int components_so_far = last_num_components;
 952
 953   if (is_ligature)
 954   {
 955     _hb_glyph_info_set_lig_props_for_ligature (&buffer->cur(), lig_id, total_component_count);
 956     if (_hb_glyph_info_get_general_category (&buffer->cur()) == HB_UNICODE_GENERAL_CATEGORY_NON_SPACING_MARK)
 957     {
 958       _hb_glyph_info_set_general_category (&buffer->cur(), HB_UNICODE_GENERAL_CATEGORY_OTHER_LETTER);
 959     }
 960   }
 961   c->replace_glyph_with_ligature (lig_glyph, klass);
 962
 963   for (unsigned int i = 1; i < count; i++)
 964   {
 965     while (buffer->idx < match_positions[i] && buffer->successful)
 966     {
 967       if (is_ligature)
 968       {
 969         unsigned int this_comp = _hb_glyph_info_get_lig_comp (&buffer->cur());
 970         if (this_comp == 0)
 971           this_comp = last_num_components;
 972         unsigned int new_lig_comp = components_so_far - last_num_components +
 973                                     MIN (this_comp, last_num_components);
 974           _hb_glyph_info_set_lig_props_for_mark (&buffer->cur(), lig_id, new_lig_comp);
 975       }
 976       buffer->next_glyph ();
 977     }
 978
 979     last_lig_id = _hb_glyph_info_get_lig_id (&buffer->cur());
 980     last_num_components = _hb_glyph_info_get_lig_num_comps (&buffer->cur());
 981     components_so_far += last_num_components;
 982
 983     /* Skip the base glyph */
 984     buffer->idx++;
 985   }
 986
 987   if (!is_mark_ligature && last_lig_id) {
 988     /* Re-adjust components for any marks following. */
 989     for (unsigned int i = buffer->idx; i < buffer->len; i++) {
 990       if (last_lig_id == _hb_glyph_info_get_lig_id (&buffer->info[i])) {
 991         unsigned int this_comp = _hb_glyph_info_get_lig_comp (&buffer->info[i]);
 992         if (!this_comp)
 993           break;
 994         unsigned int new_lig_comp = components_so_far - last_num_components +
 995                                     MIN (this_comp, last_num_components);
 996         _hb_glyph_info_set_lig_props_for_mark (&buffer->info[i], lig_id, new_lig_comp);
 997       } else
 998         break;
 999     }
1000   }
1001   return_trace (true);
1002 }
1003
1004 static inline bool match_backtrack (hb_ot_apply_context_t *c,
1005                                     unsigned int count,
1006                                     const HBUINT16 backtrack[],
1007                                     match_func_t match_func,
1008                                     const void *match_data,
1009                                     unsigned int *match_start)
1010 {
1011   TRACE_APPLY (nullptr);
1012
1013   hb_ot_apply_context_t::skipping_iterator_t &skippy_iter = c->iter_context;
1014   skippy_iter.reset (c->buffer->backtrack_len (), count);
1015   skippy_iter.set_match_func (match_func, match_data, backtrack);
1016
1017   for (unsigned int i = 0; i < count; i++)
1018     if (!skippy_iter.prev ())
1019       return_trace (false);
1020
1021   *match_start = skippy_iter.idx;
1022
1023   return_trace (true);
1024 }
1025
1026 static inline bool match_lookahead (hb_ot_apply_context_t *c,
1027                                     unsigned int count,
1028                                     const HBUINT16 lookahead[],
1029                                     match_func_t match_func,
1030                                     const void *match_data,
1031                                     unsigned int offset,
1032                                     unsigned int *end_index)
1033 {
1034   TRACE_APPLY (nullptr);
1035
1036   hb_ot_apply_context_t::skipping_iterator_t &skippy_iter = c->iter_context;
1037   skippy_iter.reset (c->buffer->idx + offset - 1, count);
1038   skippy_iter.set_match_func (match_func, match_data, lookahead);
1039
1040   for (unsigned int i = 0; i < count; i++)
1041     if (!skippy_iter.next ())
1042       return_trace (false);
1043
1044   *end_index = skippy_iter.idx + 1;
1045
1046   return_trace (true);
1047 }
1048
1049
1050
1051 struct LookupRecord
1052 {
1053   bool sanitize (hb_sanitize_context_t *c) const
1054   {
1055     TRACE_SANITIZE (this);
1056     return_trace (c->check_struct (this));
1057   }
1058
1059   HBUINT16      sequenceIndex;          /* Index into current glyph
1060                                          * sequence--first glyph = 0 */
1061   HBUINT16      lookupListIndex;        /* Lookup to apply to that
1062                                          * position--zero--based */
1063   public:
1064   DEFINE_SIZE_STATIC (4);
1065 };
1066
1067 template <typename context_t>
1068 static inline void recurse_lookups (context_t *c,
1069                                     unsigned int lookupCount,
1070                                     const LookupRecord lookupRecord[] /* Array of LookupRecords--in design order */)
1071 {
1072   for (unsigned int i = 0; i < lookupCount; i++)
1073     c->recurse (lookupRecord[i].lookupListIndex);
1074 }
1075
1076 static inline bool apply_lookup (hb_ot_apply_context_t *c,
1077                                  unsigned int count, /* Including the first glyph */
1078                                  unsigned int match_positions[HB_MAX_CONTEXT_LENGTH], /* Including the first glyph */
1079                                  unsigned int lookupCount,
1080                                  const LookupRecord lookupRecord[], /* Array of LookupRecords--in design order */
1081                                  unsigned int match_length)
1082 {
1083   TRACE_APPLY (nullptr);
1084
1085   hb_buffer_t *buffer = c->buffer;
1086   int end;
1087
1088   /* All positions are distance from beginning of *output* buffer.
1089    * Adjust. */
1090   {
1091     unsigned int bl = buffer->backtrack_len ();
1092     end = bl + match_length;
1093
1094     int delta = bl - buffer->idx;
1095     /* Convert positions to new indexing. */
1096     for (unsigned int j = 0; j < count; j++)
1097       match_positions[j] += delta;
1098   }
1099
1100   for (unsigned int i = 0; i < lookupCount && buffer->successful; i++)
1101   {
1102     unsigned int idx = lookupRecord[i].sequenceIndex;
1103     if (idx >= count)
1104       continue;
1105
1106     /* Don't recurse to ourself at same position.
1107      * Note that this test is too naive, it doesn't catch longer loops. */
1108     if (idx == 0 && lookupRecord[i].lookupListIndex == c->lookup_index)
1109       continue;
1110
1111     if (unlikely (!buffer->move_to (match_positions[idx])))
1112       break;
1113
1114     if (unlikely (buffer->max_ops <= 0))
1115       break;
1116
1117     unsigned int orig_len = buffer->backtrack_len () + buffer->lookahead_len ();
1118     if (!c->recurse (lookupRecord[i].lookupListIndex))
1119       continue;
1120
1121     unsigned int new_len = buffer->backtrack_len () + buffer->lookahead_len ();
1122     int delta = new_len - orig_len;
1123
1124     if (!delta)
1125       continue;
1126
1127     /* Recursed lookup changed buffer len.  Adjust.
1128      *
1129      * TODO:
1130      *
1131      * Right now, if buffer length increased by n, we assume n new glyphs
1132      * were added right after the current position, and if buffer length
1133      * was decreased by n, we assume n match positions after the current
1134      * one where removed.  The former (buffer length increased) case is
1135      * fine, but the decrease case can be improved in at least two ways,
1136      * both of which are significant:
1137      *
1138      *   - If recursed-to lookup is MultipleSubst and buffer length
1139      *     decreased, then it's current match position that was deleted,
1140      *     NOT the one after it.
1141      *
1142      *   - If buffer length was decreased by n, it does not necessarily
1143      *     mean that n match positions where removed, as there might
1144      *     have been marks and default-ignorables in the sequence.  We
1145      *     should instead drop match positions between current-position
1146      *     and current-position + n instead.
1147      *
1148      * It should be possible to construct tests for both of these cases.
1149      */
1150
1151     end += delta;
1152     if (end <= int (match_positions[idx]))
1153     {
1154       /* End might end up being smaller than match_positions[idx] if the recursed
1155        * lookup ended up removing many items, more than we have had matched.
1156        * Just never rewind end back and get out of here.
1157        * https://bugs.chromium.org/p/chromium/issues/detail?id=659496 */
1158       end = match_positions[idx];
1159       /* There can't be any further changes. */
1160       break;
1161     }
1162
1163     unsigned int next = idx + 1; /* next now is the position after the recursed lookup. */
1164
1165     if (delta > 0)
1166     {
1167       if (unlikely (delta + count > HB_MAX_CONTEXT_LENGTH))
1168         break;
1169     }
1170     else
1171     {
1172       /* NOTE: delta is negative. */
1173       delta = MAX (delta, (int) next - (int) count);
1174       next -= delta;
1175     }
1176
1177     /* Shift! */
1178     memmove (match_positions + next + delta, match_positions + next,
1179              (count - next) * sizeof (match_positions[0]));
1180     next += delta;
1181     count += delta;
1182
1183     /* Fill in new entries. */
1184     for (unsigned int j = idx + 1; j < next; j++)
1185       match_positions[j] = match_positions[j - 1] + 1;
1186
1187     /* And fixup the rest. */
1188     for (; next < count; next++)
1189       match_positions[next] += delta;
1190   }
1191
1192   buffer->move_to (end);
1193
1194   return_trace (true);
1195 }
1196
1197
1198
1199 /* Contextual lookups */
1200
1201 struct ContextClosureLookupContext
1202 {
1203   ContextClosureFuncs funcs;
1204   const void *intersects_data;
1205 };
1206
1207 struct ContextCollectGlyphsLookupContext
1208 {
1209   ContextCollectGlyphsFuncs funcs;
1210   const void *collect_data;
1211 };
1212
1213 struct ContextApplyLookupContext
1214 {
1215   ContextApplyFuncs funcs;
1216   const void *match_data;
1217 };
1218
1219 static inline bool context_intersects (const hb_set_t *glyphs,
1220                                        unsigned int inputCount, /* Including the first glyph (not matched) */
1221                                        const HBUINT16 input[], /* Array of input values--start with second glyph */
1222                                        ContextClosureLookupContext &lookup_context)
1223 {
1224   return intersects_array (glyphs,
1225                            inputCount ? inputCount - 1 : 0, input,
1226                            lookup_context.funcs.intersects, lookup_context.intersects_data);
1227 }
1228
1229 static inline void context_closure_lookup (hb_closure_context_t *c,
1230                                            unsigned int inputCount, /* Including the first glyph (not matched) */
1231                                            const HBUINT16 input[], /* Array of input values--start with second glyph */
1232                                            unsigned int lookupCount,
1233                                            const LookupRecord lookupRecord[],
1234                                            ContextClosureLookupContext &lookup_context)
1235 {
1236   if (context_intersects (c->glyphs,
1237                           inputCount, input,
1238                           lookup_context))
1239     recurse_lookups (c,
1240                      lookupCount, lookupRecord);
1241 }
1242
1243 static inline void context_collect_glyphs_lookup (hb_collect_glyphs_context_t *c,
1244                                                   unsigned int inputCount, /* Including the first glyph (not matched) */
1245                                                   const HBUINT16 input[], /* Array of input values--start with second glyph */
1246                                                   unsigned int lookupCount,
1247                                                   const LookupRecord lookupRecord[],
1248                                                   ContextCollectGlyphsLookupContext &lookup_context)
1249 {
1250   collect_array (c, c->input,
1251                  inputCount ? inputCount - 1 : 0, input,
1252                  lookup_context.funcs.collect, lookup_context.collect_data);
1253   recurse_lookups (c,
1254                    lookupCount, lookupRecord);
1255 }
1256
1257 static inline bool context_would_apply_lookup (hb_would_apply_context_t *c,
1258                                                unsigned int inputCount, /* Including the first glyph (not matched) */
1259                                                const HBUINT16 input[], /* Array of input values--start with second glyph */
1260                                                unsigned int lookupCount HB_UNUSED,
1261                                                const LookupRecord lookupRecord[] HB_UNUSED,
1262                                                ContextApplyLookupContext &lookup_context)
1263 {
1264   return would_match_input (c,
1265                             inputCount, input,
1266                             lookup_context.funcs.match, lookup_context.match_data);
1267 }
1268 static inline bool context_apply_lookup (hb_ot_apply_context_t *c,
1269                                          unsigned int inputCount, /* Including the first glyph (not matched) */
1270                                          const HBUINT16 input[], /* Array of input values--start with second glyph */
1271                                          unsigned int lookupCount,
1272                                          const LookupRecord lookupRecord[],
1273                                          ContextApplyLookupContext &lookup_context)
1274 {
1275   unsigned int match_length = 0;
1276   unsigned int match_positions[HB_MAX_CONTEXT_LENGTH];
1277   return match_input (c,
1278                       inputCount, input,
1279                       lookup_context.funcs.match, lookup_context.match_data,
1280                       &match_length, match_positions)
1281       && (c->buffer->unsafe_to_break (c->buffer->idx, c->buffer->idx + match_length),
1282           apply_lookup (c,
1283                        inputCount, match_positions,
1284                        lookupCount, lookupRecord,
1285                        match_length));
1286 }
1287
1288 struct Rule
1289 {
1290   bool intersects (const hb_set_t *glyphs, ContextClosureLookupContext &lookup_context) const
1291   {
1292     return context_intersects (glyphs,
1293                                inputCount, inputZ.arrayZ,
1294                                lookup_context);
1295   }
1296
1297   void closure (hb_closure_context_t *c, ContextClosureLookupContext &lookup_context) const
1298   {
1299     const UnsizedArrayOf<LookupRecord> &lookupRecord = StructAfter<UnsizedArrayOf<LookupRecord> >
1300                                                        (inputZ.as_array ((inputCount ? inputCount - 1 : 0)));
1301     context_closure_lookup (c,
1302                             inputCount, inputZ.arrayZ,
1303                             lookupCount, lookupRecord.arrayZ,
1304                             lookup_context);
1305   }
1306
1307   void collect_glyphs (hb_collect_glyphs_context_t *c,
1308                        ContextCollectGlyphsLookupContext &lookup_context) const
1309   {
1310     const UnsizedArrayOf<LookupRecord> &lookupRecord = StructAfter<UnsizedArrayOf<LookupRecord> >
1311                                                        (inputZ.as_array (inputCount ? inputCount - 1 : 0));
1312     context_collect_glyphs_lookup (c,
1313                                    inputCount, inputZ.arrayZ,
1314                                    lookupCount, lookupRecord.arrayZ,
1315                                    lookup_context);
1316   }
1317
1318   bool would_apply (hb_would_apply_context_t *c,
1319                     ContextApplyLookupContext &lookup_context) const
1320   {
1321     TRACE_WOULD_APPLY (this);
1322     const UnsizedArrayOf<LookupRecord> &lookupRecord = StructAfter<UnsizedArrayOf<LookupRecord> >
1323                                                        (inputZ.as_array (inputCount ? inputCount - 1 : 0));
1324     return_trace (context_would_apply_lookup (c, inputCount, inputZ.arrayZ, lookupCount, lookupRecord.arrayZ, lookup_context));
1325   }
1326
1327   bool apply (hb_ot_apply_context_t *c,
1328               ContextApplyLookupContext &lookup_context) const
1329   {
1330     TRACE_APPLY (this);
1331     const UnsizedArrayOf<LookupRecord> &lookupRecord = StructAfter<UnsizedArrayOf<LookupRecord> >
1332                                                        (inputZ.as_array (inputCount ? inputCount - 1 : 0));
1333     return_trace (context_apply_lookup (c, inputCount, inputZ.arrayZ, lookupCount, lookupRecord.arrayZ, lookup_context));
1334   }
1335
1336   public:
1337   bool sanitize (hb_sanitize_context_t *c) const
1338   {
1339     TRACE_SANITIZE (this);
1340     return_trace (inputCount.sanitize (c) &&
1341                   lookupCount.sanitize (c) &&
1342                   c->check_range (inputZ.arrayZ,
1343                                   inputZ.item_size * (inputCount ? inputCount - 1 : 0) +
1344                                   LookupRecord::static_size * lookupCount));
1345   }
1346
1347   protected:
1348   HBUINT16      inputCount;             /* Total number of glyphs in input
1349                                          * glyph sequence--includes the first
1350                                          * glyph */
1351   HBUINT16      lookupCount;            /* Number of LookupRecords */
1352   UnsizedArrayOf<HBUINT16>
1353                 inputZ;                 /* Array of match inputs--start with
1354                                          * second glyph */
1355 /*UnsizedArrayOf<LookupRecord>
1356                 lookupRecordX;*/        /* Array of LookupRecords--in
1357                                          * design order */
1358   public:
1359   DEFINE_SIZE_ARRAY (4, inputZ);
1360 };
1361
1362 struct RuleSet
1363 {
1364   bool intersects (const hb_set_t *glyphs,
1365                    ContextClosureLookupContext &lookup_context) const
1366   {
1367     unsigned int num_rules = rule.len;
1368     for (unsigned int i = 0; i < num_rules; i++)
1369       if ((this+rule[i]).intersects (glyphs, lookup_context))
1370         return true;
1371     return false;
1372   }
1373
1374   void closure (hb_closure_context_t *c,
1375                 ContextClosureLookupContext &lookup_context) const
1376   {
1377     unsigned int num_rules = rule.len;
1378     for (unsigned int i = 0; i < num_rules; i++)
1379       (this+rule[i]).closure (c, lookup_context);
1380   }
1381
1382   void collect_glyphs (hb_collect_glyphs_context_t *c,
1383                        ContextCollectGlyphsLookupContext &lookup_context) const
1384   {
1385     unsigned int num_rules = rule.len;
1386     for (unsigned int i = 0; i < num_rules; i++)
1387       (this+rule[i]).collect_glyphs (c, lookup_context);
1388   }
1389
1390   bool would_apply (hb_would_apply_context_t *c,
1391                     ContextApplyLookupContext &lookup_context) const
1392   {
1393     TRACE_WOULD_APPLY (this);
1394     unsigned int num_rules = rule.len;
1395     for (unsigned int i = 0; i < num_rules; i++)
1396     {
1397       if ((this+rule[i]).would_apply (c, lookup_context))
1398         return_trace (true);
1399     }
1400     return_trace (false);
1401   }
1402
1403   bool apply (hb_ot_apply_context_t *c,
1404               ContextApplyLookupContext &lookup_context) const
1405   {
1406     TRACE_APPLY (this);
1407     unsigned int num_rules = rule.len;
1408     for (unsigned int i = 0; i < num_rules; i++)
1409     {
1410       if ((this+rule[i]).apply (c, lookup_context))
1411         return_trace (true);
1412     }
1413     return_trace (false);
1414   }
1415
1416   bool sanitize (hb_sanitize_context_t *c) const
1417   {
1418     TRACE_SANITIZE (this);
1419     return_trace (rule.sanitize (c, this));
1420   }
1421
1422   protected:
1423   OffsetArrayOf<Rule>
1424                 rule;                   /* Array of Rule tables
1425                                          * ordered by preference */
1426   public:
1427   DEFINE_SIZE_ARRAY (2, rule);
1428 };
1429
1430
1431 struct ContextFormat1
1432 {
1433   bool intersects (const hb_set_t *glyphs) const
1434   {
1435     struct ContextClosureLookupContext lookup_context = {
1436       {intersects_glyph},
1437       nullptr
1438     };
1439
1440     unsigned int count = ruleSet.len;
1441     for (Coverage::Iter iter (this+coverage); iter.more (); iter.next ())
1442     {
1443       if (unlikely (iter.get_coverage () >= count))
1444         break; /* Work around malicious fonts. https://github.com/harfbuzz/harfbuzz/issues/363 */
1445       if (glyphs->has (iter.get_glyph ()) &&
1446           (this+ruleSet[iter.get_coverage ()]).intersects (glyphs, lookup_context))
1447         return true;
1448     }
1449     return false;
1450   }
1451
1452   void closure (hb_closure_context_t *c) const
1453   {
1454     struct ContextClosureLookupContext lookup_context = {
1455       {intersects_glyph},
1456       nullptr
1457     };
1458
1459     unsigned int count = ruleSet.len;
1460     for (Coverage::Iter iter (this+coverage); iter.more (); iter.next ())
1461     {
1462       if (unlikely (iter.get_coverage () >= count))
1463         break; /* Work around malicious fonts. https://github.com/harfbuzz/harfbuzz/issues/363 */
1464       if (c->glyphs->has (iter.get_glyph ()))
1465         (this+ruleSet[iter.get_coverage ()]).closure (c, lookup_context);
1466     }
1467   }
1468
1469   void collect_glyphs (hb_collect_glyphs_context_t *c) const
1470   {
1471     (this+coverage).add_coverage (c->input);
1472
1473     struct ContextCollectGlyphsLookupContext lookup_context = {
1474       {collect_glyph},
1475       nullptr
1476     };
1477
1478     unsigned int count = ruleSet.len;
1479     for (unsigned int i = 0; i < count; i++)
1480       (this+ruleSet[i]).collect_glyphs (c, lookup_context);
1481   }
1482
1483   bool would_apply (hb_would_apply_context_t *c) const
1484   {
1485     TRACE_WOULD_APPLY (this);
1486
1487     const RuleSet &rule_set = this+ruleSet[(this+coverage).get_coverage (c->glyphs[0])];
1488     struct ContextApplyLookupContext lookup_context = {
1489       {match_glyph},
1490       nullptr
1491     };
1492     return_trace (rule_set.would_apply (c, lookup_context));
1493   }
1494
1495   const Coverage &get_coverage () const { return this+coverage; }
1496
1497   bool apply (hb_ot_apply_context_t *c) const
1498   {
1499     TRACE_APPLY (this);
1500     unsigned int index = (this+coverage).get_coverage (c->buffer->cur().codepoint);
1501     if (likely (index == NOT_COVERED))
1502       return_trace (false);
1503
1504     const RuleSet &rule_set = this+ruleSet[index];
1505     struct ContextApplyLookupContext lookup_context = {
1506       {match_glyph},
1507       nullptr
1508     };
1509     return_trace (rule_set.apply (c, lookup_context));
1510   }
1511
1512   bool subset (hb_subset_context_t *c) const
1513   {
1514     TRACE_SUBSET (this);
1515     // TODO(subset)
1516     return_trace (false);
1517   }
1518
1519   bool sanitize (hb_sanitize_context_t *c) const
1520   {
1521     TRACE_SANITIZE (this);
1522     return_trace (coverage.sanitize (c, this) && ruleSet.sanitize (c, this));
1523   }
1524
1525   protected:
1526   HBUINT16      format;                 /* Format identifier--format = 1 */
1527   OffsetTo<Coverage>
1528                 coverage;               /* Offset to Coverage table--from
1529                                          * beginning of table */
1530   OffsetArrayOf<RuleSet>
1531                 ruleSet;                /* Array of RuleSet tables
1532                                          * ordered by Coverage Index */
1533   public:
1534   DEFINE_SIZE_ARRAY (6, ruleSet);
1535 };
1536
1537
1538 struct ContextFormat2
1539 {
1540   bool intersects (const hb_set_t *glyphs) const
1541   {
1542     if (!(this+coverage).intersects (glyphs))
1543       return false;
1544
1545     const ClassDef &class_def = this+classDef;
1546
1547     struct ContextClosureLookupContext lookup_context = {
1548       {intersects_class},
1549       &class_def
1550     };
1551
1552     unsigned int count = ruleSet.len;
1553     for (unsigned int i = 0; i < count; i++)
1554       if (class_def.intersects_class (glyphs, i) &&
1555           (this+ruleSet[i]).intersects (glyphs, lookup_context))
1556         return true;
1557
1558     return false;
1559   }
1560
1561   void closure (hb_closure_context_t *c) const
1562   {
1563     if (!(this+coverage).intersects (c->glyphs))
1564       return;
1565
1566     const ClassDef &class_def = this+classDef;
1567
1568     struct ContextClosureLookupContext lookup_context = {
1569       {intersects_class},
1570       &class_def
1571     };
1572
1573     unsigned int count = ruleSet.len;
1574     for (unsigned int i = 0; i < count; i++)
1575       if (class_def.intersects_class (c->glyphs, i)) {
1576         const RuleSet &rule_set = this+ruleSet[i];
1577         rule_set.closure (c, lookup_context);
1578       }
1579   }
1580
1581   void collect_glyphs (hb_collect_glyphs_context_t *c) const
1582   {
1583     (this+coverage).add_coverage (c->input);
1584
1585     const ClassDef &class_def = this+classDef;
1586     struct ContextCollectGlyphsLookupContext lookup_context = {
1587       {collect_class},
1588       &class_def
1589     };
1590
1591     unsigned int count = ruleSet.len;
1592     for (unsigned int i = 0; i < count; i++)
1593       (this+ruleSet[i]).collect_glyphs (c, lookup_context);
1594   }
1595
1596   bool would_apply (hb_would_apply_context_t *c) const
1597   {
1598     TRACE_WOULD_APPLY (this);
1599
1600     const ClassDef &class_def = this+classDef;
1601     unsigned int index = class_def.get_class (c->glyphs[0]);
1602     const RuleSet &rule_set = this+ruleSet[index];
1603     struct ContextApplyLookupContext lookup_context = {
1604       {match_class},
1605       &class_def
1606     };
1607     return_trace (rule_set.would_apply (c, lookup_context));
1608   }
1609
1610   const Coverage &get_coverage () const { return this+coverage; }
1611
1612   bool apply (hb_ot_apply_context_t *c) const
1613   {
1614     TRACE_APPLY (this);
1615     unsigned int index = (this+coverage).get_coverage (c->buffer->cur().codepoint);
1616     if (likely (index == NOT_COVERED)) return_trace (false);
1617
1618     const ClassDef &class_def = this+classDef;
1619     index = class_def.get_class (c->buffer->cur().codepoint);
1620     const RuleSet &rule_set = this+ruleSet[index];
1621     struct ContextApplyLookupContext lookup_context = {
1622       {match_class},
1623       &class_def
1624     };
1625     return_trace (rule_set.apply (c, lookup_context));
1626   }
1627
1628   bool subset (hb_subset_context_t *c) const
1629   {
1630     TRACE_SUBSET (this);
1631     // TODO(subset)
1632     return_trace (false);
1633   }
1634
1635   bool sanitize (hb_sanitize_context_t *c) const
1636   {
1637     TRACE_SANITIZE (this);
1638     return_trace (coverage.sanitize (c, this) && classDef.sanitize (c, this) && ruleSet.sanitize (c, this));
1639   }
1640
1641   protected:
1642   HBUINT16      format;                 /* Format identifier--format = 2 */
1643   OffsetTo<Coverage>
1644                 coverage;               /* Offset to Coverage table--from
1645                                          * beginning of table */
1646   OffsetTo<ClassDef>
1647                 classDef;               /* Offset to glyph ClassDef table--from
1648                                          * beginning of table */
1649   OffsetArrayOf<RuleSet>
1650                 ruleSet;                /* Array of RuleSet tables
1651                                          * ordered by class */
1652   public:
1653   DEFINE_SIZE_ARRAY (8, ruleSet);
1654 };
1655
1656
1657 struct ContextFormat3
1658 {
1659   bool intersects (const hb_set_t *glyphs) const
1660   {
1661     if (!(this+coverageZ[0]).intersects (glyphs))
1662       return false;
1663
1664     struct ContextClosureLookupContext lookup_context = {
1665       {intersects_coverage},
1666       this
1667     };
1668     return context_intersects (glyphs,
1669                                glyphCount, (const HBUINT16 *) (coverageZ.arrayZ + 1),
1670                                lookup_context);
1671   }
1672
1673   void closure (hb_closure_context_t *c) const
1674   {
1675     if (!(this+coverageZ[0]).intersects (c->glyphs))
1676       return;
1677
1678     const LookupRecord *lookupRecord = &StructAfter<LookupRecord> (coverageZ.as_array (glyphCount));
1679     struct ContextClosureLookupContext lookup_context = {
1680       {intersects_coverage},
1681       this
1682     };
1683     context_closure_lookup (c,
1684                             glyphCount, (const HBUINT16 *) (coverageZ.arrayZ + 1),
1685                             lookupCount, lookupRecord,
1686                             lookup_context);
1687   }
1688
1689   void collect_glyphs (hb_collect_glyphs_context_t *c) const
1690   {
1691     (this+coverageZ[0]).add_coverage (c->input);
1692
1693     const LookupRecord *lookupRecord = &StructAfter<LookupRecord> (coverageZ.as_array (glyphCount));
1694     struct ContextCollectGlyphsLookupContext lookup_context = {
1695       {collect_coverage},
1696       this
1697     };
1698
1699     context_collect_glyphs_lookup (c,
1700                                    glyphCount, (const HBUINT16 *) (coverageZ.arrayZ + 1),
1701                                    lookupCount, lookupRecord,
1702                                    lookup_context);
1703   }
1704
1705   bool would_apply (hb_would_apply_context_t *c) const
1706   {
1707     TRACE_WOULD_APPLY (this);
1708
1709     const LookupRecord *lookupRecord = &StructAfter<LookupRecord> (coverageZ.as_array (glyphCount));
1710     struct ContextApplyLookupContext lookup_context = {
1711       {match_coverage},
1712       this
1713     };
1714     return_trace (context_would_apply_lookup (c, glyphCount, (const HBUINT16 *) (coverageZ.arrayZ + 1), lookupCount, lookupRecord, lookup_context));
1715   }
1716
1717   const Coverage &get_coverage () const { return this+coverageZ[0]; }
1718
1719   bool apply (hb_ot_apply_context_t *c) const
1720   {
1721     TRACE_APPLY (this);
1722     unsigned int index = (this+coverageZ[0]).get_coverage (c->buffer->cur().codepoint);
1723     if (likely (index == NOT_COVERED)) return_trace (false);
1724
1725     const LookupRecord *lookupRecord = &StructAfter<LookupRecord> (coverageZ.as_array (glyphCount));
1726     struct ContextApplyLookupContext lookup_context = {
1727       {match_coverage},
1728       this
1729     };
1730     return_trace (context_apply_lookup (c, glyphCount, (const HBUINT16 *) (coverageZ.arrayZ + 1), lookupCount, lookupRecord, lookup_context));
1731   }
1732
1733   bool subset (hb_subset_context_t *c) const
1734   {
1735     TRACE_SUBSET (this);
1736     // TODO(subset)
1737     return_trace (false);
1738   }
1739
1740   bool sanitize (hb_sanitize_context_t *c) const
1741   {
1742     TRACE_SANITIZE (this);
1743     if (!c->check_struct (this)) return_trace (false);
1744     unsigned int count = glyphCount;
1745     if (!count) return_trace (false); /* We want to access coverageZ[0] freely. */
1746     if (!c->check_array (coverageZ.arrayZ, count)) return_trace (false);
1747     for (unsigned int i = 0; i < count; i++)
1748       if (!coverageZ[i].sanitize (c, this)) return_trace (false);
1749     const LookupRecord *lookupRecord = &StructAfter<LookupRecord> (coverageZ.as_array (glyphCount));
1750     return_trace (c->check_array (lookupRecord, lookupCount));
1751   }
1752
1753   protected:
1754   HBUINT16      format;                 /* Format identifier--format = 3 */
1755   HBUINT16      glyphCount;             /* Number of glyphs in the input glyph
1756                                          * sequence */
1757   HBUINT16      lookupCount;            /* Number of LookupRecords */
1758   UnsizedArrayOf<OffsetTo<Coverage> >
1759                 coverageZ;              /* Array of offsets to Coverage
1760                                          * table in glyph sequence order */
1761 /*UnsizedArrayOf<LookupRecord>
1762                 lookupRecordX;*/        /* Array of LookupRecords--in
1763                                          * design order */
1764   public:
1765   DEFINE_SIZE_ARRAY (6, coverageZ);
1766 };
1767
1768 struct Context
1769 {
1770   template <typename context_t>
1771   typename context_t::return_t dispatch (context_t *c) const
1772   {
1773     TRACE_DISPATCH (this, u.format);
1774     if (unlikely (!c->may_dispatch (this, &u.format))) return_trace (c->no_dispatch_return_value ());
1775     switch (u.format) {
1776     case 1: return_trace (c->dispatch (u.format1));
1777     case 2: return_trace (c->dispatch (u.format2));
1778     case 3: return_trace (c->dispatch (u.format3));
1779     default:return_trace (c->default_return_value ());
1780     }
1781   }
1782
1783   protected:
1784   union {
1785   HBUINT16              format;         /* Format identifier */
1786   ContextFormat1        format1;
1787   ContextFormat2        format2;
1788   ContextFormat3        format3;
1789   } u;
1790 };
1791
1792
1793 /* Chaining Contextual lookups */
1794
1795 struct ChainContextClosureLookupContext
1796 {
1797   ContextClosureFuncs funcs;
1798   const void *intersects_data[3];
1799 };
1800
1801 struct ChainContextCollectGlyphsLookupContext
1802 {
1803   ContextCollectGlyphsFuncs funcs;
1804   const void *collect_data[3];
1805 };
1806
1807 struct ChainContextApplyLookupContext
1808 {
1809   ContextApplyFuncs funcs;
1810   const void *match_data[3];
1811 };
1812
1813 static inline bool chain_context_intersects (const hb_set_t *glyphs,
1814                                              unsigned int backtrackCount,
1815                                              const HBUINT16 backtrack[],
1816                                              unsigned int inputCount, /* Including the first glyph (not matched) */
1817                                              const HBUINT16 input[], /* Array of input values--start with second glyph */
1818                                              unsigned int lookaheadCount,
1819                                              const HBUINT16 lookahead[],
1820                                              ChainContextClosureLookupContext &lookup_context)
1821 {
1822   return intersects_array (glyphs,
1823                            backtrackCount, backtrack,
1824                            lookup_context.funcs.intersects, lookup_context.intersects_data[0])
1825       && intersects_array (glyphs,
1826                            inputCount ? inputCount - 1 : 0, input,
1827                            lookup_context.funcs.intersects, lookup_context.intersects_data[1])
1828       && intersects_array (glyphs,
1829                           lookaheadCount, lookahead,
1830                           lookup_context.funcs.intersects, lookup_context.intersects_data[2]);
1831 }
1832
1833 static inline void chain_context_closure_lookup (hb_closure_context_t *c,
1834                                                  unsigned int backtrackCount,
1835                                                  const HBUINT16 backtrack[],
1836                                                  unsigned int inputCount, /* Including the first glyph (not matched) */
1837                                                  const HBUINT16 input[], /* Array of input values--start with second glyph */
1838                                                  unsigned int lookaheadCount,
1839                                                  const HBUINT16 lookahead[],
1840                                                  unsigned int lookupCount,
1841                                                  const LookupRecord lookupRecord[],
1842                                                  ChainContextClosureLookupContext &lookup_context)
1843 {
1844   if (chain_context_intersects (c->glyphs,
1845                                 backtrackCount, backtrack,
1846                                 inputCount, input,
1847                                 lookaheadCount, lookahead,
1848                                 lookup_context))
1849     recurse_lookups (c,
1850                      lookupCount, lookupRecord);
1851 }
1852
1853 static inline void chain_context_collect_glyphs_lookup (hb_collect_glyphs_context_t *c,
1854                                                         unsigned int backtrackCount,
1855                                                         const HBUINT16 backtrack[],
1856                                                         unsigned int inputCount, /* Including the first glyph (not matched) */
1857                                                         const HBUINT16 input[], /* Array of input values--start with second glyph */
1858                                                         unsigned int lookaheadCount,
1859                                                         const HBUINT16 lookahead[],
1860                                                         unsigned int lookupCount,
1861                                                         const LookupRecord lookupRecord[],
1862                                                         ChainContextCollectGlyphsLookupContext &lookup_context)
1863 {
1864   collect_array (c, c->before,
1865                  backtrackCount, backtrack,
1866                  lookup_context.funcs.collect, lookup_context.collect_data[0]);
1867   collect_array (c, c->input,
1868                  inputCount ? inputCount - 1 : 0, input,
1869                  lookup_context.funcs.collect, lookup_context.collect_data[1]);
1870   collect_array (c, c->after,
1871                  lookaheadCount, lookahead,
1872                  lookup_context.funcs.collect, lookup_context.collect_data[2]);
1873   recurse_lookups (c,
1874                    lookupCount, lookupRecord);
1875 }
1876
1877 static inline bool chain_context_would_apply_lookup (hb_would_apply_context_t *c,
1878                                                      unsigned int backtrackCount,
1879                                                      const HBUINT16 backtrack[] HB_UNUSED,
1880                                                      unsigned int inputCount, /* Including the first glyph (not matched) */
1881                                                      const HBUINT16 input[], /* Array of input values--start with second glyph */
1882                                                      unsigned int lookaheadCount,
1883                                                      const HBUINT16 lookahead[] HB_UNUSED,
1884                                                      unsigned int lookupCount HB_UNUSED,
1885                                                      const LookupRecord lookupRecord[] HB_UNUSED,
1886                                                      ChainContextApplyLookupContext &lookup_context)
1887 {
1888   return (c->zero_context ? !backtrackCount && !lookaheadCount : true)
1889       && would_match_input (c,
1890                             inputCount, input,
1891                             lookup_context.funcs.match, lookup_context.match_data[1]);
1892 }
1893
1894 static inline bool chain_context_apply_lookup (hb_ot_apply_context_t *c,
1895                                                unsigned int backtrackCount,
1896                                                const HBUINT16 backtrack[],
1897                                                unsigned int inputCount, /* Including the first glyph (not matched) */
1898                                                const HBUINT16 input[], /* Array of input values--start with second glyph */
1899                                                unsigned int lookaheadCount,
1900                                                const HBUINT16 lookahead[],
1901                                                unsigned int lookupCount,
1902                                                const LookupRecord lookupRecord[],
1903                                                ChainContextApplyLookupContext &lookup_context)
1904 {
1905   unsigned int start_index = 0, match_length = 0, end_index = 0;
1906   unsigned int match_positions[HB_MAX_CONTEXT_LENGTH];
1907   return match_input (c,
1908                       inputCount, input,
1909                       lookup_context.funcs.match, lookup_context.match_data[1],
1910                       &match_length, match_positions)
1911       && match_backtrack (c,
1912                           backtrackCount, backtrack,
1913                           lookup_context.funcs.match, lookup_context.match_data[0],
1914                           &start_index)
1915       && match_lookahead (c,
1916                           lookaheadCount, lookahead,
1917                           lookup_context.funcs.match, lookup_context.match_data[2],
1918                           match_length, &end_index)
1919       && (c->buffer->unsafe_to_break_from_outbuffer (start_index, end_index),
1920           apply_lookup (c,
1921                         inputCount, match_positions,
1922                         lookupCount, lookupRecord,
1923                         match_length));
1924 }
1925
1926 struct ChainRule
1927 {
1928   bool intersects (const hb_set_t *glyphs, ChainContextClosureLookupContext &lookup_context) const
1929   {
1930     const HeadlessArrayOf<HBUINT16> &input = StructAfter<HeadlessArrayOf<HBUINT16> > (backtrack);
1931     const ArrayOf<HBUINT16> &lookahead = StructAfter<ArrayOf<HBUINT16> > (input);
1932     return chain_context_intersects (glyphs,
1933                                      backtrack.len, backtrack.arrayZ,
1934                                      input.lenP1, input.arrayZ,
1935                                      lookahead.len, lookahead.arrayZ,
1936                                      lookup_context);
1937   }
1938
1939   void closure (hb_closure_context_t *c,
1940                 ChainContextClosureLookupContext &lookup_context) const
1941   {
1942     const HeadlessArrayOf<HBUINT16> &input = StructAfter<HeadlessArrayOf<HBUINT16> > (backtrack);
1943     const ArrayOf<HBUINT16> &lookahead = StructAfter<ArrayOf<HBUINT16> > (input);
1944     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord> > (lookahead);
1945     chain_context_closure_lookup (c,
1946                                   backtrack.len, backtrack.arrayZ,
1947                                   input.lenP1, input.arrayZ,
1948                                   lookahead.len, lookahead.arrayZ,
1949                                   lookup.len, lookup.arrayZ,
1950                                   lookup_context);
1951   }
1952
1953   void collect_glyphs (hb_collect_glyphs_context_t *c,
1954                        ChainContextCollectGlyphsLookupContext &lookup_context) const
1955   {
1956     const HeadlessArrayOf<HBUINT16> &input = StructAfter<HeadlessArrayOf<HBUINT16> > (backtrack);
1957     const ArrayOf<HBUINT16> &lookahead = StructAfter<ArrayOf<HBUINT16> > (input);
1958     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord> > (lookahead);
1959     chain_context_collect_glyphs_lookup (c,
1960                                          backtrack.len, backtrack.arrayZ,
1961                                          input.lenP1, input.arrayZ,
1962                                          lookahead.len, lookahead.arrayZ,
1963                                          lookup.len, lookup.arrayZ,
1964                                          lookup_context);
1965   }
1966
1967   bool would_apply (hb_would_apply_context_t *c,
1968                     ChainContextApplyLookupContext &lookup_context) const
1969   {
1970     TRACE_WOULD_APPLY (this);
1971     const HeadlessArrayOf<HBUINT16> &input = StructAfter<HeadlessArrayOf<HBUINT16> > (backtrack);
1972     const ArrayOf<HBUINT16> &lookahead = StructAfter<ArrayOf<HBUINT16> > (input);
1973     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord> > (lookahead);
1974     return_trace (chain_context_would_apply_lookup (c,
1975                                                     backtrack.len, backtrack.arrayZ,
1976                                                     input.lenP1, input.arrayZ,
1977                                                     lookahead.len, lookahead.arrayZ, lookup.len,
1978                                                     lookup.arrayZ, lookup_context));
1979   }
1980
1981   bool apply (hb_ot_apply_context_t *c, ChainContextApplyLookupContext &lookup_context) const
1982   {
1983     TRACE_APPLY (this);
1984     const HeadlessArrayOf<HBUINT16> &input = StructAfter<HeadlessArrayOf<HBUINT16> > (backtrack);
1985     const ArrayOf<HBUINT16> &lookahead = StructAfter<ArrayOf<HBUINT16> > (input);
1986     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord> > (lookahead);
1987     return_trace (chain_context_apply_lookup (c,
1988                                               backtrack.len, backtrack.arrayZ,
1989                                               input.lenP1, input.arrayZ,
1990                                               lookahead.len, lookahead.arrayZ, lookup.len,
1991                                               lookup.arrayZ, lookup_context));
1992   }
1993
1994   bool sanitize (hb_sanitize_context_t *c) const
1995   {
1996     TRACE_SANITIZE (this);
1997     if (!backtrack.sanitize (c)) return_trace (false);
1998     const HeadlessArrayOf<HBUINT16> &input = StructAfter<HeadlessArrayOf<HBUINT16> > (backtrack);
1999     if (!input.sanitize (c)) return_trace (false);
2000     const ArrayOf<HBUINT16> &lookahead = StructAfter<ArrayOf<HBUINT16> > (input);
2001     if (!lookahead.sanitize (c)) return_trace (false);
2002     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord> > (lookahead);
2003     return_trace (lookup.sanitize (c));
2004   }
2005
2006   protected:
2007   ArrayOf<HBUINT16>
2008                 backtrack;              /* Array of backtracking values
2009                                          * (to be matched before the input
2010                                          * sequence) */
2011   HeadlessArrayOf<HBUINT16>
2012                 inputX;                 /* Array of input values (start with
2013                                          * second glyph) */
2014   ArrayOf<HBUINT16>
2015                 lookaheadX;             /* Array of lookahead values's (to be
2016                                          * matched after the input sequence) */
2017   ArrayOf<LookupRecord>
2018                 lookupX;                /* Array of LookupRecords--in
2019                                          * design order) */
2020   public:
2021   DEFINE_SIZE_MIN (8);
2022 };
2023
2024 struct ChainRuleSet
2025 {
2026   bool intersects (const hb_set_t *glyphs, ChainContextClosureLookupContext &lookup_context) const
2027   {
2028     unsigned int num_rules = rule.len;
2029     for (unsigned int i = 0; i < num_rules; i++)
2030       if ((this+rule[i]).intersects (glyphs, lookup_context))
2031         return true;
2032     return false;
2033   }
2034   void closure (hb_closure_context_t *c, ChainContextClosureLookupContext &lookup_context) const
2035   {
2036     unsigned int num_rules = rule.len;
2037     for (unsigned int i = 0; i < num_rules; i++)
2038       (this+rule[i]).closure (c, lookup_context);
2039   }
2040
2041   void collect_glyphs (hb_collect_glyphs_context_t *c, ChainContextCollectGlyphsLookupContext &lookup_context) const
2042   {
2043     unsigned int num_rules = rule.len;
2044     for (unsigned int i = 0; i < num_rules; i++)
2045       (this+rule[i]).collect_glyphs (c, lookup_context);
2046   }
2047
2048   bool would_apply (hb_would_apply_context_t *c, ChainContextApplyLookupContext &lookup_context) const
2049   {
2050     TRACE_WOULD_APPLY (this);
2051     unsigned int num_rules = rule.len;
2052     for (unsigned int i = 0; i < num_rules; i++)
2053       if ((this+rule[i]).would_apply (c, lookup_context))
2054         return_trace (true);
2055
2056     return_trace (false);
2057   }
2058
2059   bool apply (hb_ot_apply_context_t *c, ChainContextApplyLookupContext &lookup_context) const
2060   {
2061     TRACE_APPLY (this);
2062     unsigned int num_rules = rule.len;
2063     for (unsigned int i = 0; i < num_rules; i++)
2064       if ((this+rule[i]).apply (c, lookup_context))
2065         return_trace (true);
2066
2067     return_trace (false);
2068   }
2069
2070   bool sanitize (hb_sanitize_context_t *c) const
2071   {
2072     TRACE_SANITIZE (this);
2073     return_trace (rule.sanitize (c, this));
2074   }
2075
2076   protected:
2077   OffsetArrayOf<ChainRule>
2078                 rule;                   /* Array of ChainRule tables
2079                                          * ordered by preference */
2080   public:
2081   DEFINE_SIZE_ARRAY (2, rule);
2082 };
2083
2084 struct ChainContextFormat1
2085 {
2086   bool intersects (const hb_set_t *glyphs) const
2087   {
2088     struct ChainContextClosureLookupContext lookup_context = {
2089       {intersects_glyph},
2090       {nullptr, nullptr, nullptr}
2091     };
2092
2093     unsigned int count = ruleSet.len;
2094     for (Coverage::Iter iter (this+coverage); iter.more (); iter.next ())
2095     {
2096       if (unlikely (iter.get_coverage () >= count))
2097         break; /* Work around malicious fonts. https://github.com/harfbuzz/harfbuzz/issues/363 */
2098       if (glyphs->has (iter.get_glyph ()) &&
2099           (this+ruleSet[iter.get_coverage ()]).intersects (glyphs, lookup_context))
2100         return true;
2101     }
2102     return false;
2103   }
2104
2105   void closure (hb_closure_context_t *c) const
2106   {
2107     struct ChainContextClosureLookupContext lookup_context = {
2108       {intersects_glyph},
2109       {nullptr, nullptr, nullptr}
2110     };
2111
2112     unsigned int count = ruleSet.len;
2113     for (Coverage::Iter iter (this+coverage); iter.more (); iter.next ())
2114     {
2115       if (unlikely (iter.get_coverage () >= count))
2116         break; /* Work around malicious fonts. https://github.com/harfbuzz/harfbuzz/issues/363 */
2117       if (c->glyphs->has (iter.get_glyph ()))
2118         (this+ruleSet[iter.get_coverage ()]).closure (c, lookup_context);
2119     }
2120   }
2121
2122   void collect_glyphs (hb_collect_glyphs_context_t *c) const
2123   {
2124     (this+coverage).add_coverage (c->input);
2125
2126     struct ChainContextCollectGlyphsLookupContext lookup_context = {
2127       {collect_glyph},
2128       {nullptr, nullptr, nullptr}
2129     };
2130
2131     unsigned int count = ruleSet.len;
2132     for (unsigned int i = 0; i < count; i++)
2133       (this+ruleSet[i]).collect_glyphs (c, lookup_context);
2134   }
2135
2136   bool would_apply (hb_would_apply_context_t *c) const
2137   {
2138     TRACE_WOULD_APPLY (this);
2139
2140     const ChainRuleSet &rule_set = this+ruleSet[(this+coverage).get_coverage (c->glyphs[0])];
2141     struct ChainContextApplyLookupContext lookup_context = {
2142       {match_glyph},
2143       {nullptr, nullptr, nullptr}
2144     };
2145     return_trace (rule_set.would_apply (c, lookup_context));
2146   }
2147
2148   const Coverage &get_coverage () const { return this+coverage; }
2149
2150   bool apply (hb_ot_apply_context_t *c) const
2151   {
2152     TRACE_APPLY (this);
2153     unsigned int index = (this+coverage).get_coverage (c->buffer->cur().codepoint);
2154     if (likely (index == NOT_COVERED)) return_trace (false);
2155
2156     const ChainRuleSet &rule_set = this+ruleSet[index];
2157     struct ChainContextApplyLookupContext lookup_context = {
2158       {match_glyph},
2159       {nullptr, nullptr, nullptr}
2160     };
2161     return_trace (rule_set.apply (c, lookup_context));
2162   }
2163
2164   bool subset (hb_subset_context_t *c) const
2165   {
2166     TRACE_SUBSET (this);
2167     // TODO(subset)
2168     return_trace (false);
2169   }
2170
2171   bool sanitize (hb_sanitize_context_t *c) const
2172   {
2173     TRACE_SANITIZE (this);
2174     return_trace (coverage.sanitize (c, this) && ruleSet.sanitize (c, this));
2175   }
2176
2177   protected:
2178   HBUINT16      format;                 /* Format identifier--format = 1 */
2179   OffsetTo<Coverage>
2180                 coverage;               /* Offset to Coverage table--from
2181                                          * beginning of table */
2182   OffsetArrayOf<ChainRuleSet>
2183                 ruleSet;                /* Array of ChainRuleSet tables
2184                                          * ordered by Coverage Index */
2185   public:
2186   DEFINE_SIZE_ARRAY (6, ruleSet);
2187 };
2188
2189 struct ChainContextFormat2
2190 {
2191   bool intersects (const hb_set_t *glyphs) const
2192   {
2193     if (!(this+coverage).intersects (glyphs))
2194       return false;
2195
2196     const ClassDef &backtrack_class_def = this+backtrackClassDef;
2197     const ClassDef &input_class_def = this+inputClassDef;
2198     const ClassDef &lookahead_class_def = this+lookaheadClassDef;
2199
2200     struct ChainContextClosureLookupContext lookup_context = {
2201       {intersects_class},
2202       {&backtrack_class_def,
2203        &input_class_def,
2204        &lookahead_class_def}
2205     };
2206
2207     unsigned int count = ruleSet.len;
2208     for (unsigned int i = 0; i < count; i++)
2209       if (input_class_def.intersects_class (glyphs, i) &&
2210           (this+ruleSet[i]).intersects (glyphs, lookup_context))
2211         return true;
2212
2213     return false;
2214   }
2215   void closure (hb_closure_context_t *c) const
2216   {
2217     if (!(this+coverage).intersects (c->glyphs))
2218       return;
2219
2220     const ClassDef &backtrack_class_def = this+backtrackClassDef;
2221     const ClassDef &input_class_def = this+inputClassDef;
2222     const ClassDef &lookahead_class_def = this+lookaheadClassDef;
2223
2224     struct ChainContextClosureLookupContext lookup_context = {
2225       {intersects_class},
2226       {&backtrack_class_def,
2227        &input_class_def,
2228        &lookahead_class_def}
2229     };
2230
2231     unsigned int count = ruleSet.len;
2232     for (unsigned int i = 0; i < count; i++)
2233       if (input_class_def.intersects_class (c->glyphs, i)) {
2234         const ChainRuleSet &rule_set = this+ruleSet[i];
2235         rule_set.closure (c, lookup_context);
2236       }
2237   }
2238
2239   void collect_glyphs (hb_collect_glyphs_context_t *c) const
2240   {
2241     (this+coverage).add_coverage (c->input);
2242
2243     const ClassDef &backtrack_class_def = this+backtrackClassDef;
2244     const ClassDef &input_class_def = this+inputClassDef;
2245     const ClassDef &lookahead_class_def = this+lookaheadClassDef;
2246
2247     struct ChainContextCollectGlyphsLookupContext lookup_context = {
2248       {collect_class},
2249       {&backtrack_class_def,
2250        &input_class_def,
2251        &lookahead_class_def}
2252     };
2253
2254     unsigned int count = ruleSet.len;
2255     for (unsigned int i = 0; i < count; i++)
2256       (this+ruleSet[i]).collect_glyphs (c, lookup_context);
2257   }
2258
2259   bool would_apply (hb_would_apply_context_t *c) const
2260   {
2261     TRACE_WOULD_APPLY (this);
2262
2263     const ClassDef &backtrack_class_def = this+backtrackClassDef;
2264     const ClassDef &input_class_def = this+inputClassDef;
2265     const ClassDef &lookahead_class_def = this+lookaheadClassDef;
2266
2267     unsigned int index = input_class_def.get_class (c->glyphs[0]);
2268     const ChainRuleSet &rule_set = this+ruleSet[index];
2269     struct ChainContextApplyLookupContext lookup_context = {
2270       {match_class},
2271       {&backtrack_class_def,
2272        &input_class_def,
2273        &lookahead_class_def}
2274     };
2275     return_trace (rule_set.would_apply (c, lookup_context));
2276   }
2277
2278   const Coverage &get_coverage () const { return this+coverage; }
2279
2280   bool apply (hb_ot_apply_context_t *c) const
2281   {
2282     TRACE_APPLY (this);
2283     unsigned int index = (this+coverage).get_coverage (c->buffer->cur().codepoint);
2284     if (likely (index == NOT_COVERED)) return_trace (false);
2285
2286     const ClassDef &backtrack_class_def = this+backtrackClassDef;
2287     const ClassDef &input_class_def = this+inputClassDef;
2288     const ClassDef &lookahead_class_def = this+lookaheadClassDef;
2289
2290     index = input_class_def.get_class (c->buffer->cur().codepoint);
2291     const ChainRuleSet &rule_set = this+ruleSet[index];
2292     struct ChainContextApplyLookupContext lookup_context = {
2293       {match_class},
2294       {&backtrack_class_def,
2295        &input_class_def,
2296        &lookahead_class_def}
2297     };
2298     return_trace (rule_set.apply (c, lookup_context));
2299   }
2300
2301   bool subset (hb_subset_context_t *c) const
2302   {
2303     TRACE_SUBSET (this);
2304     // TODO(subset)
2305     return_trace (false);
2306   }
2307
2308   bool sanitize (hb_sanitize_context_t *c) const
2309   {
2310     TRACE_SANITIZE (this);
2311     return_trace (coverage.sanitize (c, this) &&
2312                   backtrackClassDef.sanitize (c, this) &&
2313                   inputClassDef.sanitize (c, this) &&
2314                   lookaheadClassDef.sanitize (c, this) &&
2315                   ruleSet.sanitize (c, this));
2316   }
2317
2318   protected:
2319   HBUINT16      format;                 /* Format identifier--format = 2 */
2320   OffsetTo<Coverage>
2321                 coverage;               /* Offset to Coverage table--from
2322                                          * beginning of table */
2323   OffsetTo<ClassDef>
2324                 backtrackClassDef;      /* Offset to glyph ClassDef table
2325                                          * containing backtrack sequence
2326                                          * data--from beginning of table */
2327   OffsetTo<ClassDef>
2328                 inputClassDef;          /* Offset to glyph ClassDef
2329                                          * table containing input sequence
2330                                          * data--from beginning of table */
2331   OffsetTo<ClassDef>
2332                 lookaheadClassDef;      /* Offset to glyph ClassDef table
2333                                          * containing lookahead sequence
2334                                          * data--from beginning of table */
2335   OffsetArrayOf<ChainRuleSet>
2336                 ruleSet;                /* Array of ChainRuleSet tables
2337                                          * ordered by class */
2338   public:
2339   DEFINE_SIZE_ARRAY (12, ruleSet);
2340 };
2341
2342 struct ChainContextFormat3
2343 {
2344   bool intersects (const hb_set_t *glyphs) const
2345   {
2346     const OffsetArrayOf<Coverage> &input = StructAfter<OffsetArrayOf<Coverage> > (backtrack);
2347
2348     if (!(this+input[0]).intersects (glyphs))
2349       return false;
2350
2351     const OffsetArrayOf<Coverage> &lookahead = StructAfter<OffsetArrayOf<Coverage> > (input);
2352     struct ChainContextClosureLookupContext lookup_context = {
2353       {intersects_coverage},
2354       {this, this, this}
2355     };
2356     return chain_context_intersects (glyphs,
2357                                      backtrack.len, (const HBUINT16 *) backtrack.arrayZ,
2358                                      input.len, (const HBUINT16 *) input.arrayZ + 1,
2359                                      lookahead.len, (const HBUINT16 *) lookahead.arrayZ,
2360                                      lookup_context);
2361   }
2362
2363   void closure (hb_closure_context_t *c) const
2364   {
2365     const OffsetArrayOf<Coverage> &input = StructAfter<OffsetArrayOf<Coverage> > (backtrack);
2366
2367     if (!(this+input[0]).intersects (c->glyphs))
2368       return;
2369
2370     const OffsetArrayOf<Coverage> &lookahead = StructAfter<OffsetArrayOf<Coverage> > (input);
2371     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord> > (lookahead);
2372     struct ChainContextClosureLookupContext lookup_context = {
2373       {intersects_coverage},
2374       {this, this, this}
2375     };
2376     chain_context_closure_lookup (c,
2377                                   backtrack.len, (const HBUINT16 *) backtrack.arrayZ,
2378                                   input.len, (const HBUINT16 *) input.arrayZ + 1,
2379                                   lookahead.len, (const HBUINT16 *) lookahead.arrayZ,
2380                                   lookup.len, lookup.arrayZ,
2381                                   lookup_context);
2382   }
2383
2384   void collect_glyphs (hb_collect_glyphs_context_t *c) const
2385   {
2386     const OffsetArrayOf<Coverage> &input = StructAfter<OffsetArrayOf<Coverage> > (backtrack);
2387
2388     (this+input[0]).add_coverage (c->input);
2389
2390     const OffsetArrayOf<Coverage> &lookahead = StructAfter<OffsetArrayOf<Coverage> > (input);
2391     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord> > (lookahead);
2392     struct ChainContextCollectGlyphsLookupContext lookup_context = {
2393       {collect_coverage},
2394       {this, this, this}
2395     };
2396     chain_context_collect_glyphs_lookup (c,
2397                                          backtrack.len, (const HBUINT16 *) backtrack.arrayZ,
2398                                          input.len, (const HBUINT16 *) input.arrayZ + 1,
2399                                          lookahead.len, (const HBUINT16 *) lookahead.arrayZ,
2400                                          lookup.len, lookup.arrayZ,
2401                                          lookup_context);
2402   }
2403
2404   bool would_apply (hb_would_apply_context_t *c) const
2405   {
2406     TRACE_WOULD_APPLY (this);
2407
2408     const OffsetArrayOf<Coverage> &input = StructAfter<OffsetArrayOf<Coverage> > (backtrack);
2409     const OffsetArrayOf<Coverage> &lookahead = StructAfter<OffsetArrayOf<Coverage> > (input);
2410     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord> > (lookahead);
2411     struct ChainContextApplyLookupContext lookup_context = {
2412       {match_coverage},
2413       {this, this, this}
2414     };
2415     return_trace (chain_context_would_apply_lookup (c,
2416                                                     backtrack.len, (const HBUINT16 *) backtrack.arrayZ,
2417                                                     input.len, (const HBUINT16 *) input.arrayZ + 1,
2418                                                     lookahead.len, (const HBUINT16 *) lookahead.arrayZ,
2419                                                     lookup.len, lookup.arrayZ, lookup_context));
2420   }
2421
2422   const Coverage &get_coverage () const
2423   {
2424     const OffsetArrayOf<Coverage> &input = StructAfter<OffsetArrayOf<Coverage> > (backtrack);
2425     return this+input[0];
2426   }
2427
2428   bool apply (hb_ot_apply_context_t *c) const
2429   {
2430     TRACE_APPLY (this);
2431     const OffsetArrayOf<Coverage> &input = StructAfter<OffsetArrayOf<Coverage> > (backtrack);
2432
2433     unsigned int index = (this+input[0]).get_coverage (c->buffer->cur().codepoint);
2434     if (likely (index == NOT_COVERED)) return_trace (false);
2435
2436     const OffsetArrayOf<Coverage> &lookahead = StructAfter<OffsetArrayOf<Coverage> > (input);
2437     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord> > (lookahead);
2438     struct ChainContextApplyLookupContext lookup_context = {
2439       {match_coverage},
2440       {this, this, this}
2441     };
2442     return_trace (chain_context_apply_lookup (c,
2443                                               backtrack.len, (const HBUINT16 *) backtrack.arrayZ,
2444                                               input.len, (const HBUINT16 *) input.arrayZ + 1,
2445                                               lookahead.len, (const HBUINT16 *) lookahead.arrayZ,
2446                                               lookup.len, lookup.arrayZ, lookup_context));
2447   }
2448
2449   bool subset (hb_subset_context_t *c) const
2450   {
2451     TRACE_SUBSET (this);
2452     // TODO(subset)
2453     return_trace (false);
2454   }
2455
2456   bool sanitize (hb_sanitize_context_t *c) const
2457   {
2458     TRACE_SANITIZE (this);
2459     if (!backtrack.sanitize (c, this)) return_trace (false);
2460     const OffsetArrayOf<Coverage> &input = StructAfter<OffsetArrayOf<Coverage> > (backtrack);
2461     if (!input.sanitize (c, this)) return_trace (false);
2462     if (!input.len) return_trace (false); /* To be consistent with Context. */
2463     const OffsetArrayOf<Coverage> &lookahead = StructAfter<OffsetArrayOf<Coverage> > (input);
2464     if (!lookahead.sanitize (c, this)) return_trace (false);
2465     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord> > (lookahead);
2466     return_trace (lookup.sanitize (c));
2467   }
2468
2469   protected:
2470   HBUINT16      format;                 /* Format identifier--format = 3 */
2471   OffsetArrayOf<Coverage>
2472                 backtrack;              /* Array of coverage tables
2473                                          * in backtracking sequence, in  glyph
2474                                          * sequence order */
2475   OffsetArrayOf<Coverage>
2476                 inputX          ;       /* Array of coverage
2477                                          * tables in input sequence, in glyph
2478                                          * sequence order */
2479   OffsetArrayOf<Coverage>
2480                 lookaheadX;             /* Array of coverage tables
2481                                          * in lookahead sequence, in glyph
2482                                          * sequence order */
2483   ArrayOf<LookupRecord>
2484                 lookupX;                /* Array of LookupRecords--in
2485                                          * design order) */
2486   public:
2487   DEFINE_SIZE_MIN (10);
2488 };
2489
2490 struct ChainContext
2491 {
2492   template <typename context_t>
2493   typename context_t::return_t dispatch (context_t *c) const
2494   {
2495     TRACE_DISPATCH (this, u.format);
2496     if (unlikely (!c->may_dispatch (this, &u.format))) return_trace (c->no_dispatch_return_value ());
2497     switch (u.format) {
2498     case 1: return_trace (c->dispatch (u.format1));
2499     case 2: return_trace (c->dispatch (u.format2));
2500     case 3: return_trace (c->dispatch (u.format3));
2501     default:return_trace (c->default_return_value ());
2502     }
2503   }
2504
2505   protected:
2506   union {
2507   HBUINT16              format; /* Format identifier */
2508   ChainContextFormat1   format1;
2509   ChainContextFormat2   format2;
2510   ChainContextFormat3   format3;
2511   } u;
2512 };
2513
2514
2515 template <typename T>
2516 struct ExtensionFormat1
2517 {
2518   unsigned int get_type () const { return extensionLookupType; }
2519
2520   template <typename X>
2521   const X& get_subtable () const
2522   {
2523     unsigned int offset = extensionOffset;
2524     if (unlikely (!offset)) return Null(typename T::SubTable);
2525     return StructAtOffset<typename T::SubTable> (this, offset);
2526   }
2527
2528   template <typename context_t>
2529   typename context_t::return_t dispatch (context_t *c) const
2530   {
2531     TRACE_DISPATCH (this, format);
2532     if (unlikely (!c->may_dispatch (this, this))) return_trace (c->no_dispatch_return_value ());
2533     return_trace (get_subtable<typename T::SubTable> ().dispatch (c, get_type ()));
2534   }
2535
2536   /* This is called from may_dispatch() above with hb_sanitize_context_t. */
2537   bool sanitize (hb_sanitize_context_t *c) const
2538   {
2539     TRACE_SANITIZE (this);
2540     return_trace (c->check_struct (this) &&
2541                   extensionOffset != 0 &&
2542                   extensionLookupType != T::SubTable::Extension);
2543   }
2544
2545   protected:
2546   HBUINT16      format;                 /* Format identifier. Set to 1. */
2547   HBUINT16      extensionLookupType;    /* Lookup type of subtable referenced
2548                                          * by ExtensionOffset (i.e. the
2549                                          * extension subtable). */
2550   HBUINT32      extensionOffset;        /* Offset to the extension subtable,
2551                                          * of lookup type subtable. */
2552   public:
2553   DEFINE_SIZE_STATIC (8);
2554 };
2555
2556 template <typename T>
2557 struct Extension
2558 {
2559   unsigned int get_type () const
2560   {
2561     switch (u.format) {
2562     case 1: return u.format1.get_type ();
2563     default:return 0;
2564     }
2565   }
2566   template <typename X>
2567   const X& get_subtable () const
2568   {
2569     switch (u.format) {
2570     case 1: return u.format1.template get_subtable<typename T::SubTable> ();
2571     default:return Null(typename T::SubTable);
2572     }
2573   }
2574
2575   template <typename context_t>
2576   typename context_t::return_t dispatch (context_t *c) const
2577   {
2578     TRACE_DISPATCH (this, u.format);
2579     if (unlikely (!c->may_dispatch (this, &u.format))) return_trace (c->no_dispatch_return_value ());
2580     switch (u.format) {
2581     case 1: return_trace (u.format1.dispatch (c));
2582     default:return_trace (c->default_return_value ());
2583     }
2584   }
2585
2586   protected:
2587   union {
2588   HBUINT16              format;         /* Format identifier */
2589   ExtensionFormat1<T>   format1;
2590   } u;
2591 };
2592
2593
2594 /*
2595  * GSUB/GPOS Common
2596  */
2597
2598 struct hb_ot_layout_lookup_accelerator_t
2599 {
2600   template <typename TLookup>
2601   void init (const TLookup &lookup)
2602   {
2603     digest.init ();
2604     lookup.add_coverage (&digest);
2605
2606     subtables.init ();
2607     OT::hb_get_subtables_context_t c_get_subtables (subtables);
2608     lookup.dispatch (&c_get_subtables);
2609   }
2610   void fini () { subtables.fini (); }
2611
2612   bool may_have (hb_codepoint_t g) const
2613   { return digest.may_have (g); }
2614
2615   bool apply (hb_ot_apply_context_t *c) const
2616   {
2617     for (unsigned int i = 0; i < subtables.length; i++)
2618       if (subtables[i].apply (c))
2619         return true;
2620     return false;
2621   }
2622
2623   private:
2624   hb_set_digest_t digest;
2625   hb_get_subtables_context_t::array_t subtables;
2626 };
2627
2628 struct GSUBGPOS
2629 {
2630   bool has_data () const { return version.to_int (); }
2631   unsigned int get_script_count () const
2632   { return (this+scriptList).len; }
2633   const Tag& get_script_tag (unsigned int i) const
2634   { return (this+scriptList).get_tag (i); }
2635   unsigned int get_script_tags (unsigned int start_offset,
2636                                 unsigned int *script_count /* IN/OUT */,
2637                                 hb_tag_t     *script_tags /* OUT */) const
2638   { return (this+scriptList).get_tags (start_offset, script_count, script_tags); }
2639   const Script& get_script (unsigned int i) const
2640   { return (this+scriptList)[i]; }
2641   bool find_script_index (hb_tag_t tag, unsigned int *index) const
2642   { return (this+scriptList).find_index (tag, index); }
2643
2644   unsigned int get_feature_count () const
2645   { return (this+featureList).len; }
2646   hb_tag_t get_feature_tag (unsigned int i) const
2647   { return i == Index::NOT_FOUND_INDEX ? HB_TAG_NONE : (this+featureList).get_tag (i); }
2648   unsigned int get_feature_tags (unsigned int start_offset,
2649                                  unsigned int *feature_count /* IN/OUT */,
2650                                  hb_tag_t     *feature_tags /* OUT */) const
2651   { return (this+featureList).get_tags (start_offset, feature_count, feature_tags); }
2652   const Feature& get_feature (unsigned int i) const
2653   { return (this+featureList)[i]; }
2654   bool find_feature_index (hb_tag_t tag, unsigned int *index) const
2655   { return (this+featureList).find_index (tag, index); }
2656
2657   unsigned int get_lookup_count () const
2658   { return (this+lookupList).len; }
2659   const Lookup& get_lookup (unsigned int i) const
2660   { return (this+lookupList)[i]; }
2661
2662   bool find_variations_index (const int *coords, unsigned int num_coords,
2663                               unsigned int *index) const
2664   { return (version.to_int () >= 0x00010001u ? this+featureVars : Null(FeatureVariations))
2665            .find_index (coords, num_coords, index); }
2666   const Feature& get_feature_variation (unsigned int feature_index,
2667                                         unsigned int variations_index) const
2668   {
2669     if (FeatureVariations::NOT_FOUND_INDEX != variations_index &&
2670         version.to_int () >= 0x00010001u)
2671     {
2672       const Feature *feature = (this+featureVars).find_substitute (variations_index,
2673                                                                    feature_index);
2674       if (feature)
2675         return *feature;
2676     }
2677     return get_feature (feature_index);
2678   }
2679
2680   template <typename TLookup>
2681   bool subset (hb_subset_context_t *c) const
2682   {
2683     TRACE_SUBSET (this);
2684     struct GSUBGPOS *out = c->serializer->embed (*this);
2685     if (unlikely (!out)) return_trace (false);
2686
2687     out->scriptList.serialize_subset (c, this+scriptList, out);
2688     out->featureList.serialize_subset (c, this+featureList, out);
2689
2690     typedef OffsetListOf<TLookup> TLookupList;
2691     /* TODO Use intersects() to count how many subtables survive? */
2692     CastR<OffsetTo<TLookupList> > (out->lookupList)
2693       .serialize_subset (c,
2694                          this+CastR<const OffsetTo<TLookupList> > (lookupList),
2695                          out);
2696
2697     if (version.to_int () >= 0x00010001u)
2698      out->featureVars.serialize_subset (c, this+featureVars, out);
2699
2700     return_trace (true);
2701   }
2702
2703   unsigned int get_size () const
2704   {
2705     return min_size +
2706            (version.to_int () >= 0x00010001u ? featureVars.static_size : 0);
2707   }
2708
2709   template <typename TLookup>
2710   bool sanitize (hb_sanitize_context_t *c) const
2711   {
2712     TRACE_SANITIZE (this);
2713     typedef OffsetListOf<TLookup> TLookupList;
2714     return_trace (version.sanitize (c) &&
2715                   likely (version.major == 1) &&
2716                   scriptList.sanitize (c, this) &&
2717                   featureList.sanitize (c, this) &&
2718                   CastR<OffsetTo<TLookupList> > (lookupList).sanitize (c, this) &&
2719                   (version.to_int () < 0x00010001u || featureVars.sanitize (c, this)));
2720   }
2721
2722   template <typename T>
2723   struct accelerator_t
2724   {
2725     void init (hb_face_t *face)
2726     {
2727       this->table = hb_sanitize_context_t().reference_table<T> (face);
2728       if (unlikely (this->table->is_blacklisted (this->table.get_blob (), face)))
2729       {
2730         hb_blob_destroy (this->table.get_blob ());
2731         this->table = hb_blob_get_empty ();
2732       }
2733
2734       this->lookup_count = table->get_lookup_count ();
2735
2736       this->accels = (hb_ot_layout_lookup_accelerator_t *) calloc (this->lookup_count, sizeof (hb_ot_layout_lookup_accelerator_t));
2737       if (unlikely (!this->accels))
2738         this->lookup_count = 0;
2739
2740       for (unsigned int i = 0; i < this->lookup_count; i++)
2741         this->accels[i].init (table->get_lookup (i));
2742     }
2743
2744     void fini ()
2745     {
2746       for (unsigned int i = 0; i < this->lookup_count; i++)
2747         this->accels[i].fini ();
2748       free (this->accels);
2749       this->table.destroy ();
2750     }
2751
2752     hb_blob_ptr_t<T> table;
2753     unsigned int lookup_count;
2754     hb_ot_layout_lookup_accelerator_t *accels;
2755   };
2756
2757   protected:
2758   FixedVersion<>version;        /* Version of the GSUB/GPOS table--initially set
2759                                  * to 0x00010000u */
2760   OffsetTo<ScriptList>
2761                 scriptList;     /* ScriptList table */
2762   OffsetTo<FeatureList>
2763                 featureList;    /* FeatureList table */
2764   OffsetTo<LookupList>
2765                 lookupList;     /* LookupList table */
2766   LOffsetTo<FeatureVariations>
2767                 featureVars;    /* Offset to Feature Variations
2768                                    table--from beginning of table
2769                                  * (may be NULL).  Introduced
2770                                  * in version 0x00010001. */
2771   public:
2772   DEFINE_SIZE_MIN (10);
2773 };
2774
2775
2776 } /* namespace OT */
2777
2778
2779 #endif /* HB_OT_LAYOUT_GSUBGPOS_HH */