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_empty_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_empty_t (); }
  68   static return_t default_return_value () { return hb_empty_t (); }
  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 output[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, output);
 118     hb_set_clear (output);
 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, 0>
 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_empty_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_empty_t (); }
 160   static return_t default_return_value () { return hb_empty_t (); }
 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           if (match_glyph_data) 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           if (match_glyph_data) 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   signed last_base = -1; // GPOS uses
 481   unsigned last_base_until = 0; // GPOS uses
 482
 483   hb_ot_apply_context_t (unsigned int table_index_,
 484                       hb_font_t *font_,
 485                       hb_buffer_t *buffer_) :
 486                         iter_input (), iter_context (),
 487                         font (font_), face (font->face), buffer (buffer_),
 488                         recurse_func (nullptr),
 489                         gdef (
 490 #ifndef HB_NO_OT_LAYOUT
 491                               *face->table.GDEF->table
 492 #else
 493                               Null(GDEF)
 494 #endif
 495                              ),
 496                         var_store (gdef.get_var_store ()),
 497                         direction (buffer_->props.direction),
 498                         lookup_mask (1),
 499                         table_index (table_index_),
 500                         lookup_index ((unsigned int) -1),
 501                         lookup_props (0),
 502                         nesting_level_left (HB_MAX_NESTING_LEVEL),
 503                         debug_depth (0),
 504                         has_glyph_classes (gdef.has_glyph_classes ()),
 505                         auto_zwnj (true),
 506                         auto_zwj (true),
 507                         random (false),
 508                         random_state (1) { init_iters (); }
 509
 510   void init_iters ()
 511   {
 512     iter_input.init (this, false);
 513     iter_context.init (this, true);
 514   }
 515
 516   void set_lookup_mask (hb_mask_t mask) { lookup_mask = mask; last_base = -1; last_base_until = 0; init_iters (); }
 517   void set_auto_zwj (bool auto_zwj_) { auto_zwj = auto_zwj_; init_iters (); }
 518   void set_auto_zwnj (bool auto_zwnj_) { auto_zwnj = auto_zwnj_; init_iters (); }
 519   void set_random (bool random_) { random = random_; }
 520   void set_recurse_func (recurse_func_t func) { recurse_func = func; }
 521   void set_lookup_index (unsigned int lookup_index_) { lookup_index = lookup_index_; }
 522   void set_lookup_props (unsigned int lookup_props_) { lookup_props = lookup_props_; init_iters (); }
 523
 524   uint32_t random_number ()
 525   {
 526     /* http://www.cplusplus.com/reference/random/minstd_rand/ */
 527     random_state = random_state * 48271 % 2147483647;
 528     return random_state;
 529   }
 530
 531   bool match_properties_mark (hb_codepoint_t  glyph,
 532                               unsigned int    glyph_props,
 533                               unsigned int    match_props) const
 534   {
 535     /* If using mark filtering sets, the high short of
 536      * match_props has the set index.
 537      */
 538     if (match_props & LookupFlag::UseMarkFilteringSet)
 539       return gdef.mark_set_covers (match_props >> 16, glyph);
 540
 541     /* The second byte of match_props has the meaning
 542      * "ignore marks of attachment type different than
 543      * the attachment type specified."
 544      */
 545     if (match_props & LookupFlag::MarkAttachmentType)
 546       return (match_props & LookupFlag::MarkAttachmentType) == (glyph_props & LookupFlag::MarkAttachmentType);
 547
 548     return true;
 549   }
 550
 551   bool check_glyph_property (const hb_glyph_info_t *info,
 552                              unsigned int  match_props) const
 553   {
 554     hb_codepoint_t glyph = info->codepoint;
 555     unsigned int glyph_props = _hb_glyph_info_get_glyph_props (info);
 556
 557     /* Not covered, if, for example, glyph class is ligature and
 558      * match_props includes LookupFlags::IgnoreLigatures
 559      */
 560     if (glyph_props & match_props & LookupFlag::IgnoreFlags)
 561       return false;
 562
 563     if (unlikely (glyph_props & HB_OT_LAYOUT_GLYPH_PROPS_MARK))
 564       return match_properties_mark (glyph, glyph_props, match_props);
 565
 566     return true;
 567   }
 568
 569   void _set_glyph_props (hb_codepoint_t glyph_index,
 570                           unsigned int class_guess = 0,
 571                           bool ligature = false,
 572                           bool component = false) const
 573   {
 574     unsigned int add_in = _hb_glyph_info_get_glyph_props (&buffer->cur()) &
 575                           HB_OT_LAYOUT_GLYPH_PROPS_PRESERVE;
 576     add_in |= HB_OT_LAYOUT_GLYPH_PROPS_SUBSTITUTED;
 577     if (ligature)
 578     {
 579       add_in |= HB_OT_LAYOUT_GLYPH_PROPS_LIGATED;
 580       /* In the only place that the MULTIPLIED bit is used, Uniscribe
 581        * seems to only care about the "last" transformation between
 582        * Ligature and Multiple substitutions.  Ie. if you ligate, expand,
 583        * and ligate again, it forgives the multiplication and acts as
 584        * if only ligation happened.  As such, clear MULTIPLIED bit.
 585        */
 586       add_in &= ~HB_OT_LAYOUT_GLYPH_PROPS_MULTIPLIED;
 587     }
 588     if (component)
 589       add_in |= HB_OT_LAYOUT_GLYPH_PROPS_MULTIPLIED;
 590     if (likely (has_glyph_classes))
 591       _hb_glyph_info_set_glyph_props (&buffer->cur(), add_in | gdef.get_glyph_props (glyph_index));
 592     else if (class_guess)
 593       _hb_glyph_info_set_glyph_props (&buffer->cur(), add_in | class_guess);
 594   }
 595
 596   void replace_glyph (hb_codepoint_t glyph_index) const
 597   {
 598     _set_glyph_props (glyph_index);
 599     buffer->replace_glyph (glyph_index);
 600   }
 601   void replace_glyph_inplace (hb_codepoint_t glyph_index) const
 602   {
 603     _set_glyph_props (glyph_index);
 604     buffer->cur().codepoint = glyph_index;
 605   }
 606   void replace_glyph_with_ligature (hb_codepoint_t glyph_index,
 607                                            unsigned int class_guess) const
 608   {
 609     _set_glyph_props (glyph_index, class_guess, true);
 610     buffer->replace_glyph (glyph_index);
 611   }
 612   void output_glyph_for_component (hb_codepoint_t glyph_index,
 613                                           unsigned int class_guess) const
 614   {
 615     _set_glyph_props (glyph_index, class_guess, false, true);
 616     buffer->output_glyph (glyph_index);
 617   }
 618 };
 619
 620
 621 struct hb_get_subtables_context_t :
 622        hb_dispatch_context_t<hb_get_subtables_context_t, hb_empty_t, HB_DEBUG_APPLY>
 623 {
 624   template <typename Type>
 625   HB_INTERNAL static bool apply_to (const void *obj, OT::hb_ot_apply_context_t *c)
 626   {
 627     const Type *typed_obj = (const Type *) obj;
 628     return typed_obj->apply (c);
 629   }
 630
 631   typedef bool (*hb_apply_func_t) (const void *obj, OT::hb_ot_apply_context_t *c);
 632
 633   struct hb_applicable_t
 634   {
 635     template <typename T>
 636     void init (const T &obj_, hb_apply_func_t apply_func_)
 637     {
 638       obj = &obj_;
 639       apply_func = apply_func_;
 640       digest.init ();
 641       obj_.get_coverage ().add_coverage (&digest);
 642     }
 643
 644     bool apply (OT::hb_ot_apply_context_t *c) const
 645     {
 646       return digest.may_have (c->buffer->cur().codepoint) && apply_func (obj, c);
 647     }
 648
 649     private:
 650     const void *obj;
 651     hb_apply_func_t apply_func;
 652     hb_set_digest_t digest;
 653   };
 654
 655   typedef hb_vector_t<hb_applicable_t> array_t;
 656
 657   /* Dispatch interface. */
 658   const char *get_name () { return "GET_SUBTABLES"; }
 659   template <typename T>
 660   return_t dispatch (const T &obj)
 661   {
 662     hb_applicable_t *entry = array.push();
 663     entry->init (obj, apply_to<T>);
 664     return hb_empty_t ();
 665   }
 666   static return_t default_return_value () { return hb_empty_t (); }
 667
 668   hb_get_subtables_context_t (array_t &array_) :
 669                               array (array_),
 670                               debug_depth (0) {}
 671
 672   array_t &array;
 673   unsigned int debug_depth;
 674 };
 675
 676
 677
 678
 679 typedef bool (*intersects_func_t) (const hb_set_t *glyphs, const HBUINT16 &value, const void *data);
 680 typedef void (*collect_glyphs_func_t) (hb_set_t *glyphs, const HBUINT16 &value, const void *data);
 681 typedef bool (*match_func_t) (hb_codepoint_t glyph_id, const HBUINT16 &value, const void *data);
 682
 683 struct ContextClosureFuncs
 684 {
 685   intersects_func_t intersects;
 686 };
 687 struct ContextCollectGlyphsFuncs
 688 {
 689   collect_glyphs_func_t collect;
 690 };
 691 struct ContextApplyFuncs
 692 {
 693   match_func_t match;
 694 };
 695
 696
 697 static inline bool intersects_glyph (const hb_set_t *glyphs, const HBUINT16 &value, const void *data HB_UNUSED)
 698 {
 699   return glyphs->has (value);
 700 }
 701 static inline bool intersects_class (const hb_set_t *glyphs, const HBUINT16 &value, const void *data)
 702 {
 703   const ClassDef &class_def = *reinterpret_cast<const ClassDef *>(data);
 704   return class_def.intersects_class (glyphs, value);
 705 }
 706 static inline bool intersects_coverage (const hb_set_t *glyphs, const HBUINT16 &value, const void *data)
 707 {
 708   const OffsetTo<Coverage> &coverage = (const OffsetTo<Coverage>&)value;
 709   return (data+coverage).intersects (glyphs);
 710 }
 711
 712 static inline bool intersects_array (const hb_set_t *glyphs,
 713                                      unsigned int count,
 714                                      const HBUINT16 values[],
 715                                      intersects_func_t intersects_func,
 716                                      const void *intersects_data)
 717 {
 718   for (const HBUINT16 &_ : + hb_iter (values, count))
 719     if (intersects_func (glyphs, _, intersects_data)) return true;
 720   return false;
 721 }
 722
 723
 724 static inline void collect_glyph (hb_set_t *glyphs, const HBUINT16 &value, const void *data HB_UNUSED)
 725 {
 726   glyphs->add (value);
 727 }
 728 static inline void collect_class (hb_set_t *glyphs, const HBUINT16 &value, const void *data)
 729 {
 730   const ClassDef &class_def = *reinterpret_cast<const ClassDef *>(data);
 731   class_def.add_class (glyphs, value);
 732 }
 733 static inline void collect_coverage (hb_set_t *glyphs, const HBUINT16 &value, const void *data)
 734 {
 735   const OffsetTo<Coverage> &coverage = (const OffsetTo<Coverage>&)value;
 736   (data+coverage).add_coverage (glyphs);
 737 }
 738 static inline void collect_array (hb_collect_glyphs_context_t *c HB_UNUSED,
 739                                   hb_set_t *glyphs,
 740                                   unsigned int count,
 741                                   const HBUINT16 values[],
 742                                   collect_glyphs_func_t collect_func,
 743                                   const void *collect_data)
 744 {
 745   return
 746   + hb_iter (values, count)
 747   | hb_apply ([&] (const HBUINT16 &_) { collect_func (glyphs, _, collect_data); })
 748   ;
 749 }
 750
 751
 752 static inline bool match_glyph (hb_codepoint_t glyph_id, const HBUINT16 &value, const void *data HB_UNUSED)
 753 {
 754   return glyph_id == value;
 755 }
 756 static inline bool match_class (hb_codepoint_t glyph_id, const HBUINT16 &value, const void *data)
 757 {
 758   const ClassDef &class_def = *reinterpret_cast<const ClassDef *>(data);
 759   return class_def.get_class (glyph_id) == value;
 760 }
 761 static inline bool match_coverage (hb_codepoint_t glyph_id, const HBUINT16 &value, const void *data)
 762 {
 763   const OffsetTo<Coverage> &coverage = (const OffsetTo<Coverage>&)value;
 764   return (data+coverage).get_coverage (glyph_id) != NOT_COVERED;
 765 }
 766
 767 static inline bool would_match_input (hb_would_apply_context_t *c,
 768                                       unsigned int count, /* Including the first glyph (not matched) */
 769                                       const HBUINT16 input[], /* Array of input values--start with second glyph */
 770                                       match_func_t match_func,
 771                                       const void *match_data)
 772 {
 773   if (count != c->len)
 774     return false;
 775
 776   for (unsigned int i = 1; i < count; i++)
 777     if (likely (!match_func (c->glyphs[i], input[i - 1], match_data)))
 778       return false;
 779
 780   return true;
 781 }
 782 static inline bool match_input (hb_ot_apply_context_t *c,
 783                                 unsigned int count, /* Including the first glyph (not matched) */
 784                                 const HBUINT16 input[], /* Array of input values--start with second glyph */
 785                                 match_func_t match_func,
 786                                 const void *match_data,
 787                                 unsigned int *end_offset,
 788                                 unsigned int match_positions[HB_MAX_CONTEXT_LENGTH],
 789                                 unsigned int *p_total_component_count = nullptr)
 790 {
 791   TRACE_APPLY (nullptr);
 792
 793   if (unlikely (count > HB_MAX_CONTEXT_LENGTH)) return_trace (false);
 794
 795   hb_buffer_t *buffer = c->buffer;
 796
 797   hb_ot_apply_context_t::skipping_iterator_t &skippy_iter = c->iter_input;
 798   skippy_iter.reset (buffer->idx, count - 1);
 799   skippy_iter.set_match_func (match_func, match_data, input);
 800
 801   /*
 802    * This is perhaps the trickiest part of OpenType...  Remarks:
 803    *
 804    * - If all components of the ligature were marks, we call this a mark ligature.
 805    *
 806    * - If there is no GDEF, and the ligature is NOT a mark ligature, we categorize
 807    *   it as a ligature glyph.
 808    *
 809    * - Ligatures cannot be formed across glyphs attached to different components
 810    *   of previous ligatures.  Eg. the sequence is LAM,SHADDA,LAM,FATHA,HEH, and
 811    *   LAM,LAM,HEH form a ligature, leaving SHADDA,FATHA next to eachother.
 812    *   However, it would be wrong to ligate that SHADDA,FATHA sequence.
 813    *   There are a couple of exceptions to this:
 814    *
 815    *   o If a ligature tries ligating with marks that belong to it itself, go ahead,
 816    *     assuming that the font designer knows what they are doing (otherwise it can
 817    *     break Indic stuff when a matra wants to ligate with a conjunct,
 818    *
 819    *   o If two marks want to ligate and they belong to different components of the
 820    *     same ligature glyph, and said ligature glyph is to be ignored according to
 821    *     mark-filtering rules, then allow.
 822    *     https://github.com/harfbuzz/harfbuzz/issues/545
 823    */
 824
 825   unsigned int total_component_count = 0;
 826   total_component_count += _hb_glyph_info_get_lig_num_comps (&buffer->cur());
 827
 828   unsigned int first_lig_id = _hb_glyph_info_get_lig_id (&buffer->cur());
 829   unsigned int first_lig_comp = _hb_glyph_info_get_lig_comp (&buffer->cur());
 830
 831   enum {
 832     LIGBASE_NOT_CHECKED,
 833     LIGBASE_MAY_NOT_SKIP,
 834     LIGBASE_MAY_SKIP
 835   } ligbase = LIGBASE_NOT_CHECKED;
 836
 837   match_positions[0] = buffer->idx;
 838   for (unsigned int i = 1; i < count; i++)
 839   {
 840     if (!skippy_iter.next ()) return_trace (false);
 841
 842     match_positions[i] = skippy_iter.idx;
 843
 844     unsigned int this_lig_id = _hb_glyph_info_get_lig_id (&buffer->info[skippy_iter.idx]);
 845     unsigned int this_lig_comp = _hb_glyph_info_get_lig_comp (&buffer->info[skippy_iter.idx]);
 846
 847     if (first_lig_id && first_lig_comp)
 848     {
 849       /* If first component was attached to a previous ligature component,
 850        * all subsequent components should be attached to the same ligature
 851        * component, otherwise we shouldn't ligate them... */
 852       if (first_lig_id != this_lig_id || first_lig_comp != this_lig_comp)
 853       {
 854         /* ...unless, we are attached to a base ligature and that base
 855          * ligature is ignorable. */
 856         if (ligbase == LIGBASE_NOT_CHECKED)
 857         {
 858           bool found = false;
 859           const auto *out = buffer->out_info;
 860           unsigned int j = buffer->out_len;
 861           while (j && _hb_glyph_info_get_lig_id (&out[j - 1]) == first_lig_id)
 862           {
 863             if (_hb_glyph_info_get_lig_comp (&out[j - 1]) == 0)
 864             {
 865               j--;
 866               found = true;
 867               break;
 868             }
 869             j--;
 870           }
 871
 872           if (found && skippy_iter.may_skip (out[j]) == hb_ot_apply_context_t::matcher_t::SKIP_YES)
 873             ligbase = LIGBASE_MAY_SKIP;
 874           else
 875             ligbase = LIGBASE_MAY_NOT_SKIP;
 876         }
 877
 878         if (ligbase == LIGBASE_MAY_NOT_SKIP)
 879           return_trace (false);
 880       }
 881     }
 882     else
 883     {
 884       /* If first component was NOT attached to a previous ligature component,
 885        * all subsequent components should also NOT be attached to any ligature
 886        * component, unless they are attached to the first component itself! */
 887       if (this_lig_id && this_lig_comp && (this_lig_id != first_lig_id))
 888         return_trace (false);
 889     }
 890
 891     total_component_count += _hb_glyph_info_get_lig_num_comps (&buffer->info[skippy_iter.idx]);
 892   }
 893
 894   *end_offset = skippy_iter.idx - buffer->idx + 1;
 895
 896   if (p_total_component_count)
 897     *p_total_component_count = total_component_count;
 898
 899   return_trace (true);
 900 }
 901 static inline bool ligate_input (hb_ot_apply_context_t *c,
 902                                  unsigned int count, /* Including the first glyph */
 903                                  const unsigned int match_positions[HB_MAX_CONTEXT_LENGTH], /* Including the first glyph */
 904                                  unsigned int match_length,
 905                                  hb_codepoint_t lig_glyph,
 906                                  unsigned int total_component_count)
 907 {
 908   TRACE_APPLY (nullptr);
 909
 910   hb_buffer_t *buffer = c->buffer;
 911
 912   buffer->merge_clusters (buffer->idx, buffer->idx + match_length);
 913
 914   /* - If a base and one or more marks ligate, consider that as a base, NOT
 915    *   ligature, such that all following marks can still attach to it.
 916    *   https://github.com/harfbuzz/harfbuzz/issues/1109
 917    *
 918    * - If all components of the ligature were marks, we call this a mark ligature.
 919    *   If it *is* a mark ligature, we don't allocate a new ligature id, and leave
 920    *   the ligature to keep its old ligature id.  This will allow it to attach to
 921    *   a base ligature in GPOS.  Eg. if the sequence is: LAM,LAM,SHADDA,FATHA,HEH,
 922    *   and LAM,LAM,HEH for a ligature, they will leave SHADDA and FATHA with a
 923    *   ligature id and component value of 2.  Then if SHADDA,FATHA form a ligature
 924    *   later, we don't want them to lose their ligature id/component, otherwise
 925    *   GPOS will fail to correctly position the mark ligature on top of the
 926    *   LAM,LAM,HEH ligature.  See:
 927    *     https://bugzilla.gnome.org/show_bug.cgi?id=676343
 928    *
 929    * - If a ligature is formed of components that some of which are also ligatures
 930    *   themselves, and those ligature components had marks attached to *their*
 931    *   components, we have to attach the marks to the new ligature component
 932    *   positions!  Now *that*'s tricky!  And these marks may be following the
 933    *   last component of the whole sequence, so we should loop forward looking
 934    *   for them and update them.
 935    *
 936    *   Eg. the sequence is LAM,LAM,SHADDA,FATHA,HEH, and the font first forms a
 937    *   'calt' ligature of LAM,HEH, leaving the SHADDA and FATHA with a ligature
 938    *   id and component == 1.  Now, during 'liga', the LAM and the LAM-HEH ligature
 939    *   form a LAM-LAM-HEH ligature.  We need to reassign the SHADDA and FATHA to
 940    *   the new ligature with a component value of 2.
 941    *
 942    *   This in fact happened to a font...  See:
 943    *   https://bugzilla.gnome.org/show_bug.cgi?id=437633
 944    */
 945
 946   bool is_base_ligature = _hb_glyph_info_is_base_glyph (&buffer->info[match_positions[0]]);
 947   bool is_mark_ligature = _hb_glyph_info_is_mark (&buffer->info[match_positions[0]]);
 948   for (unsigned int i = 1; i < count; i++)
 949     if (!_hb_glyph_info_is_mark (&buffer->info[match_positions[i]]))
 950     {
 951       is_base_ligature = false;
 952       is_mark_ligature = false;
 953       break;
 954     }
 955   bool is_ligature = !is_base_ligature && !is_mark_ligature;
 956
 957   unsigned int klass = is_ligature ? HB_OT_LAYOUT_GLYPH_PROPS_LIGATURE : 0;
 958   unsigned int lig_id = is_ligature ? _hb_allocate_lig_id (buffer) : 0;
 959   unsigned int last_lig_id = _hb_glyph_info_get_lig_id (&buffer->cur());
 960   unsigned int last_num_components = _hb_glyph_info_get_lig_num_comps (&buffer->cur());
 961   unsigned int components_so_far = last_num_components;
 962
 963   if (is_ligature)
 964   {
 965     _hb_glyph_info_set_lig_props_for_ligature (&buffer->cur(), lig_id, total_component_count);
 966     if (_hb_glyph_info_get_general_category (&buffer->cur()) == HB_UNICODE_GENERAL_CATEGORY_NON_SPACING_MARK)
 967     {
 968       _hb_glyph_info_set_general_category (&buffer->cur(), HB_UNICODE_GENERAL_CATEGORY_OTHER_LETTER);
 969     }
 970   }
 971   c->replace_glyph_with_ligature (lig_glyph, klass);
 972
 973   for (unsigned int i = 1; i < count; i++)
 974   {
 975     while (buffer->idx < match_positions[i] && buffer->successful)
 976     {
 977       if (is_ligature)
 978       {
 979         unsigned int this_comp = _hb_glyph_info_get_lig_comp (&buffer->cur());
 980         if (this_comp == 0)
 981           this_comp = last_num_components;
 982         unsigned int new_lig_comp = components_so_far - last_num_components +
 983                                     hb_min (this_comp, last_num_components);
 984           _hb_glyph_info_set_lig_props_for_mark (&buffer->cur(), lig_id, new_lig_comp);
 985       }
 986       buffer->next_glyph ();
 987     }
 988
 989     last_lig_id = _hb_glyph_info_get_lig_id (&buffer->cur());
 990     last_num_components = _hb_glyph_info_get_lig_num_comps (&buffer->cur());
 991     components_so_far += last_num_components;
 992
 993     /* Skip the base glyph */
 994     buffer->idx++;
 995   }
 996
 997   if (!is_mark_ligature && last_lig_id) {
 998     /* Re-adjust components for any marks following. */
 999     for (unsigned int i = buffer->idx; i < buffer->len; i++) {
1000       if (last_lig_id == _hb_glyph_info_get_lig_id (&buffer->info[i])) {
1001         unsigned int this_comp = _hb_glyph_info_get_lig_comp (&buffer->info[i]);
1002         if (!this_comp)
1003           break;
1004         unsigned int new_lig_comp = components_so_far - last_num_components +
1005                                     hb_min (this_comp, last_num_components);
1006         _hb_glyph_info_set_lig_props_for_mark (&buffer->info[i], lig_id, new_lig_comp);
1007       } else
1008         break;
1009     }
1010   }
1011   return_trace (true);
1012 }
1013
1014 static inline bool match_backtrack (hb_ot_apply_context_t *c,
1015                                     unsigned int count,
1016                                     const HBUINT16 backtrack[],
1017                                     match_func_t match_func,
1018                                     const void *match_data,
1019                                     unsigned int *match_start)
1020 {
1021   TRACE_APPLY (nullptr);
1022
1023   hb_ot_apply_context_t::skipping_iterator_t &skippy_iter = c->iter_context;
1024   skippy_iter.reset (c->buffer->backtrack_len (), count);
1025   skippy_iter.set_match_func (match_func, match_data, backtrack);
1026
1027   for (unsigned int i = 0; i < count; i++)
1028     if (!skippy_iter.prev ())
1029       return_trace (false);
1030
1031   *match_start = skippy_iter.idx;
1032
1033   return_trace (true);
1034 }
1035
1036 static inline bool match_lookahead (hb_ot_apply_context_t *c,
1037                                     unsigned int count,
1038                                     const HBUINT16 lookahead[],
1039                                     match_func_t match_func,
1040                                     const void *match_data,
1041                                     unsigned int offset,
1042                                     unsigned int *end_index)
1043 {
1044   TRACE_APPLY (nullptr);
1045
1046   hb_ot_apply_context_t::skipping_iterator_t &skippy_iter = c->iter_context;
1047   skippy_iter.reset (c->buffer->idx + offset - 1, count);
1048   skippy_iter.set_match_func (match_func, match_data, lookahead);
1049
1050   for (unsigned int i = 0; i < count; i++)
1051     if (!skippy_iter.next ())
1052       return_trace (false);
1053
1054   *end_index = skippy_iter.idx + 1;
1055
1056   return_trace (true);
1057 }
1058
1059
1060
1061 struct LookupRecord
1062 {
1063   bool sanitize (hb_sanitize_context_t *c) const
1064   {
1065     TRACE_SANITIZE (this);
1066     return_trace (c->check_struct (this));
1067   }
1068
1069   HBUINT16      sequenceIndex;          /* Index into current glyph
1070                                          * sequence--first glyph = 0 */
1071   HBUINT16      lookupListIndex;        /* Lookup to apply to that
1072                                          * position--zero--based */
1073   public:
1074   DEFINE_SIZE_STATIC (4);
1075 };
1076
1077 template <typename context_t>
1078 static inline void recurse_lookups (context_t *c,
1079                                     unsigned int lookupCount,
1080                                     const LookupRecord lookupRecord[] /* Array of LookupRecords--in design order */)
1081 {
1082   for (unsigned int i = 0; i < lookupCount; i++)
1083     c->recurse (lookupRecord[i].lookupListIndex);
1084 }
1085
1086 static inline bool apply_lookup (hb_ot_apply_context_t *c,
1087                                  unsigned int count, /* Including the first glyph */
1088                                  unsigned int match_positions[HB_MAX_CONTEXT_LENGTH], /* Including the first glyph */
1089                                  unsigned int lookupCount,
1090                                  const LookupRecord lookupRecord[], /* Array of LookupRecords--in design order */
1091                                  unsigned int match_length)
1092 {
1093   TRACE_APPLY (nullptr);
1094
1095   hb_buffer_t *buffer = c->buffer;
1096   int end;
1097
1098   /* All positions are distance from beginning of *output* buffer.
1099    * Adjust. */
1100   {
1101     unsigned int bl = buffer->backtrack_len ();
1102     end = bl + match_length;
1103
1104     int delta = bl - buffer->idx;
1105     /* Convert positions to new indexing. */
1106     for (unsigned int j = 0; j < count; j++)
1107       match_positions[j] += delta;
1108   }
1109
1110   for (unsigned int i = 0; i < lookupCount && buffer->successful; i++)
1111   {
1112     unsigned int idx = lookupRecord[i].sequenceIndex;
1113     if (idx >= count)
1114       continue;
1115
1116     /* Don't recurse to ourself at same position.
1117      * Note that this test is too naive, it doesn't catch longer loops. */
1118     if (idx == 0 && lookupRecord[i].lookupListIndex == c->lookup_index)
1119       continue;
1120
1121     if (unlikely (!buffer->move_to (match_positions[idx])))
1122       break;
1123
1124     if (unlikely (buffer->max_ops <= 0))
1125       break;
1126
1127     unsigned int orig_len = buffer->backtrack_len () + buffer->lookahead_len ();
1128     if (!c->recurse (lookupRecord[i].lookupListIndex))
1129       continue;
1130
1131     unsigned int new_len = buffer->backtrack_len () + buffer->lookahead_len ();
1132     int delta = new_len - orig_len;
1133
1134     if (!delta)
1135       continue;
1136
1137     /* Recursed lookup changed buffer len.  Adjust.
1138      *
1139      * TODO:
1140      *
1141      * Right now, if buffer length increased by n, we assume n new glyphs
1142      * were added right after the current position, and if buffer length
1143      * was decreased by n, we assume n match positions after the current
1144      * one where removed.  The former (buffer length increased) case is
1145      * fine, but the decrease case can be improved in at least two ways,
1146      * both of which are significant:
1147      *
1148      *   - If recursed-to lookup is MultipleSubst and buffer length
1149      *     decreased, then it's current match position that was deleted,
1150      *     NOT the one after it.
1151      *
1152      *   - If buffer length was decreased by n, it does not necessarily
1153      *     mean that n match positions where removed, as there might
1154      *     have been marks and default-ignorables in the sequence.  We
1155      *     should instead drop match positions between current-position
1156      *     and current-position + n instead.
1157      *
1158      * It should be possible to construct tests for both of these cases.
1159      */
1160
1161     end += delta;
1162     if (end <= int (match_positions[idx]))
1163     {
1164       /* End might end up being smaller than match_positions[idx] if the recursed
1165        * lookup ended up removing many items, more than we have had matched.
1166        * Just never rewind end back and get out of here.
1167        * https://bugs.chromium.org/p/chromium/issues/detail?id=659496 */
1168       end = match_positions[idx];
1169       /* There can't be any further changes. */
1170       break;
1171     }
1172
1173     unsigned int next = idx + 1; /* next now is the position after the recursed lookup. */
1174
1175     if (delta > 0)
1176     {
1177       if (unlikely (delta + count > HB_MAX_CONTEXT_LENGTH))
1178         break;
1179     }
1180     else
1181     {
1182       /* NOTE: delta is negative. */
1183       delta = hb_max (delta, (int) next - (int) count);
1184       next -= delta;
1185     }
1186
1187     /* Shift! */
1188     memmove (match_positions + next + delta, match_positions + next,
1189              (count - next) * sizeof (match_positions[0]));
1190     next += delta;
1191     count += delta;
1192
1193     /* Fill in new entries. */
1194     for (unsigned int j = idx + 1; j < next; j++)
1195       match_positions[j] = match_positions[j - 1] + 1;
1196
1197     /* And fixup the rest. */
1198     for (; next < count; next++)
1199       match_positions[next] += delta;
1200   }
1201
1202   buffer->move_to (end);
1203
1204   return_trace (true);
1205 }
1206
1207
1208
1209 /* Contextual lookups */
1210
1211 struct ContextClosureLookupContext
1212 {
1213   ContextClosureFuncs funcs;
1214   const void *intersects_data;
1215 };
1216
1217 struct ContextCollectGlyphsLookupContext
1218 {
1219   ContextCollectGlyphsFuncs funcs;
1220   const void *collect_data;
1221 };
1222
1223 struct ContextApplyLookupContext
1224 {
1225   ContextApplyFuncs funcs;
1226   const void *match_data;
1227 };
1228
1229 static inline bool context_intersects (const hb_set_t *glyphs,
1230                                        unsigned int inputCount, /* Including the first glyph (not matched) */
1231                                        const HBUINT16 input[], /* Array of input values--start with second glyph */
1232                                        ContextClosureLookupContext &lookup_context)
1233 {
1234   return intersects_array (glyphs,
1235                            inputCount ? inputCount - 1 : 0, input,
1236                            lookup_context.funcs.intersects, lookup_context.intersects_data);
1237 }
1238
1239 static inline void context_closure_lookup (hb_closure_context_t *c,
1240                                            unsigned int inputCount, /* Including the first glyph (not matched) */
1241                                            const HBUINT16 input[], /* Array of input values--start with second glyph */
1242                                            unsigned int lookupCount,
1243                                            const LookupRecord lookupRecord[],
1244                                            ContextClosureLookupContext &lookup_context)
1245 {
1246   if (context_intersects (c->glyphs,
1247                           inputCount, input,
1248                           lookup_context))
1249     recurse_lookups (c,
1250                      lookupCount, lookupRecord);
1251 }
1252
1253 static inline void context_collect_glyphs_lookup (hb_collect_glyphs_context_t *c,
1254                                                   unsigned int inputCount, /* Including the first glyph (not matched) */
1255                                                   const HBUINT16 input[], /* Array of input values--start with second glyph */
1256                                                   unsigned int lookupCount,
1257                                                   const LookupRecord lookupRecord[],
1258                                                   ContextCollectGlyphsLookupContext &lookup_context)
1259 {
1260   collect_array (c, c->input,
1261                  inputCount ? inputCount - 1 : 0, input,
1262                  lookup_context.funcs.collect, lookup_context.collect_data);
1263   recurse_lookups (c,
1264                    lookupCount, lookupRecord);
1265 }
1266
1267 static inline bool context_would_apply_lookup (hb_would_apply_context_t *c,
1268                                                unsigned int inputCount, /* Including the first glyph (not matched) */
1269                                                const HBUINT16 input[], /* Array of input values--start with second glyph */
1270                                                unsigned int lookupCount HB_UNUSED,
1271                                                const LookupRecord lookupRecord[] HB_UNUSED,
1272                                                ContextApplyLookupContext &lookup_context)
1273 {
1274   return would_match_input (c,
1275                             inputCount, input,
1276                             lookup_context.funcs.match, lookup_context.match_data);
1277 }
1278 static inline bool context_apply_lookup (hb_ot_apply_context_t *c,
1279                                          unsigned int inputCount, /* Including the first glyph (not matched) */
1280                                          const HBUINT16 input[], /* Array of input values--start with second glyph */
1281                                          unsigned int lookupCount,
1282                                          const LookupRecord lookupRecord[],
1283                                          ContextApplyLookupContext &lookup_context)
1284 {
1285   unsigned int match_length = 0;
1286   unsigned int match_positions[HB_MAX_CONTEXT_LENGTH];
1287   return match_input (c,
1288                       inputCount, input,
1289                       lookup_context.funcs.match, lookup_context.match_data,
1290                       &match_length, match_positions)
1291       && (c->buffer->unsafe_to_break (c->buffer->idx, c->buffer->idx + match_length),
1292           apply_lookup (c,
1293                        inputCount, match_positions,
1294                        lookupCount, lookupRecord,
1295                        match_length));
1296 }
1297
1298 struct Rule
1299 {
1300   bool intersects (const hb_set_t *glyphs, ContextClosureLookupContext &lookup_context) const
1301   {
1302     return context_intersects (glyphs,
1303                                inputCount, inputZ.arrayZ,
1304                                lookup_context);
1305   }
1306
1307   void closure (hb_closure_context_t *c, ContextClosureLookupContext &lookup_context) const
1308   {
1309     const UnsizedArrayOf<LookupRecord> &lookupRecord = StructAfter<UnsizedArrayOf<LookupRecord>>
1310                                                        (inputZ.as_array ((inputCount ? inputCount - 1 : 0)));
1311     context_closure_lookup (c,
1312                             inputCount, inputZ.arrayZ,
1313                             lookupCount, lookupRecord.arrayZ,
1314                             lookup_context);
1315   }
1316
1317   void collect_glyphs (hb_collect_glyphs_context_t *c,
1318                        ContextCollectGlyphsLookupContext &lookup_context) const
1319   {
1320     const UnsizedArrayOf<LookupRecord> &lookupRecord = StructAfter<UnsizedArrayOf<LookupRecord>>
1321                                                        (inputZ.as_array (inputCount ? inputCount - 1 : 0));
1322     context_collect_glyphs_lookup (c,
1323                                    inputCount, inputZ.arrayZ,
1324                                    lookupCount, lookupRecord.arrayZ,
1325                                    lookup_context);
1326   }
1327
1328   bool would_apply (hb_would_apply_context_t *c,
1329                     ContextApplyLookupContext &lookup_context) const
1330   {
1331     const UnsizedArrayOf<LookupRecord> &lookupRecord = StructAfter<UnsizedArrayOf<LookupRecord>>
1332                                                        (inputZ.as_array (inputCount ? inputCount - 1 : 0));
1333     return context_would_apply_lookup (c,
1334                                        inputCount, inputZ.arrayZ,
1335                                        lookupCount, lookupRecord.arrayZ,
1336                                        lookup_context);
1337   }
1338
1339   bool apply (hb_ot_apply_context_t *c,
1340               ContextApplyLookupContext &lookup_context) const
1341   {
1342     TRACE_APPLY (this);
1343     const UnsizedArrayOf<LookupRecord> &lookupRecord = StructAfter<UnsizedArrayOf<LookupRecord>>
1344                                                        (inputZ.as_array (inputCount ? inputCount - 1 : 0));
1345     return_trace (context_apply_lookup (c, inputCount, inputZ.arrayZ, lookupCount, lookupRecord.arrayZ, lookup_context));
1346   }
1347
1348   public:
1349   bool sanitize (hb_sanitize_context_t *c) const
1350   {
1351     TRACE_SANITIZE (this);
1352     return_trace (inputCount.sanitize (c) &&
1353                   lookupCount.sanitize (c) &&
1354                   c->check_range (inputZ.arrayZ,
1355                                   inputZ.item_size * (inputCount ? inputCount - 1 : 0) +
1356                                   LookupRecord::static_size * lookupCount));
1357   }
1358
1359   protected:
1360   HBUINT16      inputCount;             /* Total number of glyphs in input
1361                                          * glyph sequence--includes the first
1362                                          * glyph */
1363   HBUINT16      lookupCount;            /* Number of LookupRecords */
1364   UnsizedArrayOf<HBUINT16>
1365                 inputZ;                 /* Array of match inputs--start with
1366                                          * second glyph */
1367 /*UnsizedArrayOf<LookupRecord>
1368                 lookupRecordX;*/        /* Array of LookupRecords--in
1369                                          * design order */
1370   public:
1371   DEFINE_SIZE_ARRAY (4, inputZ);
1372 };
1373
1374 struct RuleSet
1375 {
1376   bool intersects (const hb_set_t *glyphs,
1377                    ContextClosureLookupContext &lookup_context) const
1378   {
1379     return
1380     + hb_iter (rule)
1381     | hb_map (hb_add (this))
1382     | hb_map ([&] (const Rule &_) { return _.intersects (glyphs, lookup_context); })
1383     | hb_any
1384     ;
1385   }
1386
1387   void closure (hb_closure_context_t *c,
1388                 ContextClosureLookupContext &lookup_context) const
1389   {
1390     return
1391     + hb_iter (rule)
1392     | hb_map (hb_add (this))
1393     | hb_apply ([&] (const Rule &_) { _.closure (c, lookup_context); })
1394     ;
1395   }
1396
1397   void collect_glyphs (hb_collect_glyphs_context_t *c,
1398                        ContextCollectGlyphsLookupContext &lookup_context) const
1399   {
1400     return
1401     + hb_iter (rule)
1402     | hb_map (hb_add (this))
1403     | hb_apply ([&] (const Rule &_) { _.collect_glyphs (c, lookup_context); })
1404     ;
1405   }
1406
1407   bool would_apply (hb_would_apply_context_t *c,
1408                     ContextApplyLookupContext &lookup_context) const
1409   {
1410     return
1411     + hb_iter (rule)
1412     | hb_map (hb_add (this))
1413     | hb_map ([&] (const Rule &_) { return _.would_apply (c, lookup_context); })
1414     | hb_any
1415     ;
1416   }
1417
1418   bool apply (hb_ot_apply_context_t *c,
1419               ContextApplyLookupContext &lookup_context) const
1420   {
1421     TRACE_APPLY (this);
1422     return_trace (
1423     + hb_iter (rule)
1424     | hb_map (hb_add (this))
1425     | hb_map ([&] (const Rule &_) { return _.apply (c, lookup_context); })
1426     | hb_any
1427     )
1428     ;
1429   }
1430
1431   bool sanitize (hb_sanitize_context_t *c) const
1432   {
1433     TRACE_SANITIZE (this);
1434     return_trace (rule.sanitize (c, this));
1435   }
1436
1437   protected:
1438   OffsetArrayOf<Rule>
1439                 rule;                   /* Array of Rule tables
1440                                          * ordered by preference */
1441   public:
1442   DEFINE_SIZE_ARRAY (2, rule);
1443 };
1444
1445
1446 struct ContextFormat1
1447 {
1448   bool intersects (const hb_set_t *glyphs) const
1449   {
1450     struct ContextClosureLookupContext lookup_context = {
1451       {intersects_glyph},
1452       nullptr
1453     };
1454
1455     return
1456     + hb_zip (this+coverage, ruleSet)
1457     | hb_filter (*glyphs, hb_first)
1458     | hb_map (hb_second)
1459     | hb_map (hb_add (this))
1460     | hb_map ([&] (const RuleSet &_) { return _.intersects (glyphs, lookup_context); })
1461     | hb_any
1462     ;
1463   }
1464
1465   void closure (hb_closure_context_t *c) const
1466   {
1467     struct ContextClosureLookupContext lookup_context = {
1468       {intersects_glyph},
1469       nullptr
1470     };
1471
1472     + hb_zip (this+coverage, ruleSet)
1473     | hb_filter (*c->glyphs, hb_first)
1474     | hb_map (hb_second)
1475     | hb_map (hb_add (this))
1476     | hb_apply ([&] (const RuleSet &_) { _.closure (c, lookup_context); })
1477     ;
1478   }
1479
1480   void collect_glyphs (hb_collect_glyphs_context_t *c) const
1481   {
1482     (this+coverage).add_coverage (c->input);
1483
1484     struct ContextCollectGlyphsLookupContext lookup_context = {
1485       {collect_glyph},
1486       nullptr
1487     };
1488
1489     + hb_iter (ruleSet)
1490     | hb_map (hb_add (this))
1491     | hb_apply ([&] (const RuleSet &_) { _.collect_glyphs (c, lookup_context); })
1492     ;
1493   }
1494
1495   bool would_apply (hb_would_apply_context_t *c) const
1496   {
1497     const RuleSet &rule_set = this+ruleSet[(this+coverage).get_coverage (c->glyphs[0])];
1498     struct ContextApplyLookupContext lookup_context = {
1499       {match_glyph},
1500       nullptr
1501     };
1502     return rule_set.would_apply (c, lookup_context);
1503   }
1504
1505   const Coverage &get_coverage () const { return this+coverage; }
1506
1507   bool apply (hb_ot_apply_context_t *c) const
1508   {
1509     TRACE_APPLY (this);
1510     unsigned int index = (this+coverage).get_coverage (c->buffer->cur().codepoint);
1511     if (likely (index == NOT_COVERED))
1512       return_trace (false);
1513
1514     const RuleSet &rule_set = this+ruleSet[index];
1515     struct ContextApplyLookupContext lookup_context = {
1516       {match_glyph},
1517       nullptr
1518     };
1519     return_trace (rule_set.apply (c, lookup_context));
1520   }
1521
1522   bool subset (hb_subset_context_t *c) const
1523   {
1524     TRACE_SUBSET (this);
1525     // TODO(subset)
1526     return_trace (false);
1527   }
1528
1529   bool sanitize (hb_sanitize_context_t *c) const
1530   {
1531     TRACE_SANITIZE (this);
1532     return_trace (coverage.sanitize (c, this) && ruleSet.sanitize (c, this));
1533   }
1534
1535   protected:
1536   HBUINT16      format;                 /* Format identifier--format = 1 */
1537   OffsetTo<Coverage>
1538                 coverage;               /* Offset to Coverage table--from
1539                                          * beginning of table */
1540   OffsetArrayOf<RuleSet>
1541                 ruleSet;                /* Array of RuleSet tables
1542                                          * ordered by Coverage Index */
1543   public:
1544   DEFINE_SIZE_ARRAY (6, ruleSet);
1545 };
1546
1547
1548 struct ContextFormat2
1549 {
1550   bool intersects (const hb_set_t *glyphs) const
1551   {
1552     if (!(this+coverage).intersects (glyphs))
1553       return false;
1554
1555     const ClassDef &class_def = this+classDef;
1556
1557     struct ContextClosureLookupContext lookup_context = {
1558       {intersects_class},
1559       &class_def
1560     };
1561
1562     return
1563     + hb_enumerate (ruleSet)
1564     | hb_map ([&] (const hb_pair_t<unsigned, const OffsetTo<RuleSet> &> p)
1565               { return class_def.intersects_class (glyphs, p.first) &&
1566                        (this+p.second).intersects (glyphs, lookup_context); })
1567     | hb_any
1568     ;
1569   }
1570
1571   void closure (hb_closure_context_t *c) const
1572   {
1573     if (!(this+coverage).intersects (c->glyphs))
1574       return;
1575
1576     const ClassDef &class_def = this+classDef;
1577
1578     struct ContextClosureLookupContext lookup_context = {
1579       {intersects_class},
1580       &class_def
1581     };
1582
1583     return
1584     + hb_enumerate (ruleSet)
1585     | hb_filter ([&] (unsigned _)
1586                  { return class_def.intersects_class (c->glyphs, _); },
1587                  hb_first)
1588     | hb_map (hb_second)
1589     | hb_map (hb_add (this))
1590     | hb_apply ([&] (const RuleSet &_) { _.closure (c, lookup_context); })
1591     ;
1592   }
1593
1594   void collect_glyphs (hb_collect_glyphs_context_t *c) const
1595   {
1596     (this+coverage).add_coverage (c->input);
1597
1598     const ClassDef &class_def = this+classDef;
1599     struct ContextCollectGlyphsLookupContext lookup_context = {
1600       {collect_class},
1601       &class_def
1602     };
1603
1604     + hb_iter (ruleSet)
1605     | hb_map (hb_add (this))
1606     | hb_apply ([&] (const RuleSet &_) { _.collect_glyphs (c, lookup_context); })
1607     ;
1608   }
1609
1610   bool would_apply (hb_would_apply_context_t *c) const
1611   {
1612     const ClassDef &class_def = this+classDef;
1613     unsigned int index = class_def.get_class (c->glyphs[0]);
1614     const RuleSet &rule_set = this+ruleSet[index];
1615     struct ContextApplyLookupContext lookup_context = {
1616       {match_class},
1617       &class_def
1618     };
1619     return rule_set.would_apply (c, lookup_context);
1620   }
1621
1622   const Coverage &get_coverage () const { return this+coverage; }
1623
1624   bool apply (hb_ot_apply_context_t *c) const
1625   {
1626     TRACE_APPLY (this);
1627     unsigned int index = (this+coverage).get_coverage (c->buffer->cur().codepoint);
1628     if (likely (index == NOT_COVERED)) return_trace (false);
1629
1630     const ClassDef &class_def = this+classDef;
1631     index = class_def.get_class (c->buffer->cur().codepoint);
1632     const RuleSet &rule_set = this+ruleSet[index];
1633     struct ContextApplyLookupContext lookup_context = {
1634       {match_class},
1635       &class_def
1636     };
1637     return_trace (rule_set.apply (c, lookup_context));
1638   }
1639
1640   bool subset (hb_subset_context_t *c) const
1641   {
1642     TRACE_SUBSET (this);
1643     // TODO(subset)
1644     return_trace (false);
1645   }
1646
1647   bool sanitize (hb_sanitize_context_t *c) const
1648   {
1649     TRACE_SANITIZE (this);
1650     return_trace (coverage.sanitize (c, this) && classDef.sanitize (c, this) && ruleSet.sanitize (c, this));
1651   }
1652
1653   protected:
1654   HBUINT16      format;                 /* Format identifier--format = 2 */
1655   OffsetTo<Coverage>
1656                 coverage;               /* Offset to Coverage table--from
1657                                          * beginning of table */
1658   OffsetTo<ClassDef>
1659                 classDef;               /* Offset to glyph ClassDef table--from
1660                                          * beginning of table */
1661   OffsetArrayOf<RuleSet>
1662                 ruleSet;                /* Array of RuleSet tables
1663                                          * ordered by class */
1664   public:
1665   DEFINE_SIZE_ARRAY (8, ruleSet);
1666 };
1667
1668
1669 struct ContextFormat3
1670 {
1671   bool intersects (const hb_set_t *glyphs) const
1672   {
1673     if (!(this+coverageZ[0]).intersects (glyphs))
1674       return false;
1675
1676     struct ContextClosureLookupContext lookup_context = {
1677       {intersects_coverage},
1678       this
1679     };
1680     return context_intersects (glyphs,
1681                                glyphCount, (const HBUINT16 *) (coverageZ.arrayZ + 1),
1682                                lookup_context);
1683   }
1684
1685   void closure (hb_closure_context_t *c) const
1686   {
1687     if (!(this+coverageZ[0]).intersects (c->glyphs))
1688       return;
1689
1690     const LookupRecord *lookupRecord = &StructAfter<LookupRecord> (coverageZ.as_array (glyphCount));
1691     struct ContextClosureLookupContext lookup_context = {
1692       {intersects_coverage},
1693       this
1694     };
1695     context_closure_lookup (c,
1696                             glyphCount, (const HBUINT16 *) (coverageZ.arrayZ + 1),
1697                             lookupCount, lookupRecord,
1698                             lookup_context);
1699   }
1700
1701   void collect_glyphs (hb_collect_glyphs_context_t *c) const
1702   {
1703     (this+coverageZ[0]).add_coverage (c->input);
1704
1705     const LookupRecord *lookupRecord = &StructAfter<LookupRecord> (coverageZ.as_array (glyphCount));
1706     struct ContextCollectGlyphsLookupContext lookup_context = {
1707       {collect_coverage},
1708       this
1709     };
1710
1711     context_collect_glyphs_lookup (c,
1712                                    glyphCount, (const HBUINT16 *) (coverageZ.arrayZ + 1),
1713                                    lookupCount, lookupRecord,
1714                                    lookup_context);
1715   }
1716
1717   bool would_apply (hb_would_apply_context_t *c) const
1718   {
1719     const LookupRecord *lookupRecord = &StructAfter<LookupRecord> (coverageZ.as_array (glyphCount));
1720     struct ContextApplyLookupContext lookup_context = {
1721       {match_coverage},
1722       this
1723     };
1724     return context_would_apply_lookup (c,
1725                                        glyphCount, (const HBUINT16 *) (coverageZ.arrayZ + 1),
1726                                        lookupCount, lookupRecord,
1727                                        lookup_context);
1728   }
1729
1730   const Coverage &get_coverage () const { return this+coverageZ[0]; }
1731
1732   bool apply (hb_ot_apply_context_t *c) const
1733   {
1734     TRACE_APPLY (this);
1735     unsigned int index = (this+coverageZ[0]).get_coverage (c->buffer->cur().codepoint);
1736     if (likely (index == NOT_COVERED)) return_trace (false);
1737
1738     const LookupRecord *lookupRecord = &StructAfter<LookupRecord> (coverageZ.as_array (glyphCount));
1739     struct ContextApplyLookupContext lookup_context = {
1740       {match_coverage},
1741       this
1742     };
1743     return_trace (context_apply_lookup (c, glyphCount, (const HBUINT16 *) (coverageZ.arrayZ + 1), lookupCount, lookupRecord, lookup_context));
1744   }
1745
1746   bool subset (hb_subset_context_t *c) const
1747   {
1748     TRACE_SUBSET (this);
1749     // TODO(subset)
1750     return_trace (false);
1751   }
1752
1753   bool sanitize (hb_sanitize_context_t *c) const
1754   {
1755     TRACE_SANITIZE (this);
1756     if (!c->check_struct (this)) return_trace (false);
1757     unsigned int count = glyphCount;
1758     if (!count) return_trace (false); /* We want to access coverageZ[0] freely. */
1759     if (!c->check_array (coverageZ.arrayZ, count)) return_trace (false);
1760     for (unsigned int i = 0; i < count; i++)
1761       if (!coverageZ[i].sanitize (c, this)) return_trace (false);
1762     const LookupRecord *lookupRecord = &StructAfter<LookupRecord> (coverageZ.as_array (glyphCount));
1763     return_trace (c->check_array (lookupRecord, lookupCount));
1764   }
1765
1766   protected:
1767   HBUINT16      format;                 /* Format identifier--format = 3 */
1768   HBUINT16      glyphCount;             /* Number of glyphs in the input glyph
1769                                          * sequence */
1770   HBUINT16      lookupCount;            /* Number of LookupRecords */
1771   UnsizedArrayOf<OffsetTo<Coverage>>
1772                 coverageZ;              /* Array of offsets to Coverage
1773                                          * table in glyph sequence order */
1774 /*UnsizedArrayOf<LookupRecord>
1775                 lookupRecordX;*/        /* Array of LookupRecords--in
1776                                          * design order */
1777   public:
1778   DEFINE_SIZE_ARRAY (6, coverageZ);
1779 };
1780
1781 struct Context
1782 {
1783   template <typename context_t, typename ...Ts>
1784   typename context_t::return_t dispatch (context_t *c, Ts&&... ds) const
1785   {
1786     TRACE_DISPATCH (this, u.format);
1787     if (unlikely (!c->may_dispatch (this, &u.format))) return_trace (c->no_dispatch_return_value ());
1788     switch (u.format) {
1789     case 1: return_trace (c->dispatch (u.format1, hb_forward<Ts> (ds)...));
1790     case 2: return_trace (c->dispatch (u.format2, hb_forward<Ts> (ds)...));
1791     case 3: return_trace (c->dispatch (u.format3, hb_forward<Ts> (ds)...));
1792     default:return_trace (c->default_return_value ());
1793     }
1794   }
1795
1796   protected:
1797   union {
1798   HBUINT16              format;         /* Format identifier */
1799   ContextFormat1        format1;
1800   ContextFormat2        format2;
1801   ContextFormat3        format3;
1802   } u;
1803 };
1804
1805
1806 /* Chaining Contextual lookups */
1807
1808 struct ChainContextClosureLookupContext
1809 {
1810   ContextClosureFuncs funcs;
1811   const void *intersects_data[3];
1812 };
1813
1814 struct ChainContextCollectGlyphsLookupContext
1815 {
1816   ContextCollectGlyphsFuncs funcs;
1817   const void *collect_data[3];
1818 };
1819
1820 struct ChainContextApplyLookupContext
1821 {
1822   ContextApplyFuncs funcs;
1823   const void *match_data[3];
1824 };
1825
1826 static inline bool chain_context_intersects (const hb_set_t *glyphs,
1827                                              unsigned int backtrackCount,
1828                                              const HBUINT16 backtrack[],
1829                                              unsigned int inputCount, /* Including the first glyph (not matched) */
1830                                              const HBUINT16 input[], /* Array of input values--start with second glyph */
1831                                              unsigned int lookaheadCount,
1832                                              const HBUINT16 lookahead[],
1833                                              ChainContextClosureLookupContext &lookup_context)
1834 {
1835   return intersects_array (glyphs,
1836                            backtrackCount, backtrack,
1837                            lookup_context.funcs.intersects, lookup_context.intersects_data[0])
1838       && intersects_array (glyphs,
1839                            inputCount ? inputCount - 1 : 0, input,
1840                            lookup_context.funcs.intersects, lookup_context.intersects_data[1])
1841       && intersects_array (glyphs,
1842                           lookaheadCount, lookahead,
1843                           lookup_context.funcs.intersects, lookup_context.intersects_data[2]);
1844 }
1845
1846 static inline void chain_context_closure_lookup (hb_closure_context_t *c,
1847                                                  unsigned int backtrackCount,
1848                                                  const HBUINT16 backtrack[],
1849                                                  unsigned int inputCount, /* Including the first glyph (not matched) */
1850                                                  const HBUINT16 input[], /* Array of input values--start with second glyph */
1851                                                  unsigned int lookaheadCount,
1852                                                  const HBUINT16 lookahead[],
1853                                                  unsigned int lookupCount,
1854                                                  const LookupRecord lookupRecord[],
1855                                                  ChainContextClosureLookupContext &lookup_context)
1856 {
1857   if (chain_context_intersects (c->glyphs,
1858                                 backtrackCount, backtrack,
1859                                 inputCount, input,
1860                                 lookaheadCount, lookahead,
1861                                 lookup_context))
1862     recurse_lookups (c,
1863                      lookupCount, lookupRecord);
1864 }
1865
1866 static inline void chain_context_collect_glyphs_lookup (hb_collect_glyphs_context_t *c,
1867                                                         unsigned int backtrackCount,
1868                                                         const HBUINT16 backtrack[],
1869                                                         unsigned int inputCount, /* Including the first glyph (not matched) */
1870                                                         const HBUINT16 input[], /* Array of input values--start with second glyph */
1871                                                         unsigned int lookaheadCount,
1872                                                         const HBUINT16 lookahead[],
1873                                                         unsigned int lookupCount,
1874                                                         const LookupRecord lookupRecord[],
1875                                                         ChainContextCollectGlyphsLookupContext &lookup_context)
1876 {
1877   collect_array (c, c->before,
1878                  backtrackCount, backtrack,
1879                  lookup_context.funcs.collect, lookup_context.collect_data[0]);
1880   collect_array (c, c->input,
1881                  inputCount ? inputCount - 1 : 0, input,
1882                  lookup_context.funcs.collect, lookup_context.collect_data[1]);
1883   collect_array (c, c->after,
1884                  lookaheadCount, lookahead,
1885                  lookup_context.funcs.collect, lookup_context.collect_data[2]);
1886   recurse_lookups (c,
1887                    lookupCount, lookupRecord);
1888 }
1889
1890 static inline bool chain_context_would_apply_lookup (hb_would_apply_context_t *c,
1891                                                      unsigned int backtrackCount,
1892                                                      const HBUINT16 backtrack[] HB_UNUSED,
1893                                                      unsigned int inputCount, /* Including the first glyph (not matched) */
1894                                                      const HBUINT16 input[], /* Array of input values--start with second glyph */
1895                                                      unsigned int lookaheadCount,
1896                                                      const HBUINT16 lookahead[] HB_UNUSED,
1897                                                      unsigned int lookupCount HB_UNUSED,
1898                                                      const LookupRecord lookupRecord[] HB_UNUSED,
1899                                                      ChainContextApplyLookupContext &lookup_context)
1900 {
1901   return (c->zero_context ? !backtrackCount && !lookaheadCount : true)
1902       && would_match_input (c,
1903                             inputCount, input,
1904                             lookup_context.funcs.match, lookup_context.match_data[1]);
1905 }
1906
1907 static inline bool chain_context_apply_lookup (hb_ot_apply_context_t *c,
1908                                                unsigned int backtrackCount,
1909                                                const HBUINT16 backtrack[],
1910                                                unsigned int inputCount, /* Including the first glyph (not matched) */
1911                                                const HBUINT16 input[], /* Array of input values--start with second glyph */
1912                                                unsigned int lookaheadCount,
1913                                                const HBUINT16 lookahead[],
1914                                                unsigned int lookupCount,
1915                                                const LookupRecord lookupRecord[],
1916                                                ChainContextApplyLookupContext &lookup_context)
1917 {
1918   unsigned int start_index = 0, match_length = 0, end_index = 0;
1919   unsigned int match_positions[HB_MAX_CONTEXT_LENGTH];
1920   return match_input (c,
1921                       inputCount, input,
1922                       lookup_context.funcs.match, lookup_context.match_data[1],
1923                       &match_length, match_positions)
1924       && match_backtrack (c,
1925                           backtrackCount, backtrack,
1926                           lookup_context.funcs.match, lookup_context.match_data[0],
1927                           &start_index)
1928       && match_lookahead (c,
1929                           lookaheadCount, lookahead,
1930                           lookup_context.funcs.match, lookup_context.match_data[2],
1931                           match_length, &end_index)
1932       && (c->buffer->unsafe_to_break_from_outbuffer (start_index, end_index),
1933           apply_lookup (c,
1934                         inputCount, match_positions,
1935                         lookupCount, lookupRecord,
1936                         match_length));
1937 }
1938
1939 struct ChainRule
1940 {
1941   bool intersects (const hb_set_t *glyphs, ChainContextClosureLookupContext &lookup_context) const
1942   {
1943     const HeadlessArrayOf<HBUINT16> &input = StructAfter<HeadlessArrayOf<HBUINT16>> (backtrack);
1944     const ArrayOf<HBUINT16> &lookahead = StructAfter<ArrayOf<HBUINT16>> (input);
1945     return chain_context_intersects (glyphs,
1946                                      backtrack.len, backtrack.arrayZ,
1947                                      input.lenP1, input.arrayZ,
1948                                      lookahead.len, lookahead.arrayZ,
1949                                      lookup_context);
1950   }
1951
1952   void closure (hb_closure_context_t *c,
1953                 ChainContextClosureLookupContext &lookup_context) const
1954   {
1955     const HeadlessArrayOf<HBUINT16> &input = StructAfter<HeadlessArrayOf<HBUINT16>> (backtrack);
1956     const ArrayOf<HBUINT16> &lookahead = StructAfter<ArrayOf<HBUINT16>> (input);
1957     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord>> (lookahead);
1958     chain_context_closure_lookup (c,
1959                                   backtrack.len, backtrack.arrayZ,
1960                                   input.lenP1, input.arrayZ,
1961                                   lookahead.len, lookahead.arrayZ,
1962                                   lookup.len, lookup.arrayZ,
1963                                   lookup_context);
1964   }
1965
1966   void collect_glyphs (hb_collect_glyphs_context_t *c,
1967                        ChainContextCollectGlyphsLookupContext &lookup_context) const
1968   {
1969     const HeadlessArrayOf<HBUINT16> &input = StructAfter<HeadlessArrayOf<HBUINT16>> (backtrack);
1970     const ArrayOf<HBUINT16> &lookahead = StructAfter<ArrayOf<HBUINT16>> (input);
1971     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord>> (lookahead);
1972     chain_context_collect_glyphs_lookup (c,
1973                                          backtrack.len, backtrack.arrayZ,
1974                                          input.lenP1, input.arrayZ,
1975                                          lookahead.len, lookahead.arrayZ,
1976                                          lookup.len, lookup.arrayZ,
1977                                          lookup_context);
1978   }
1979
1980   bool would_apply (hb_would_apply_context_t *c,
1981                     ChainContextApplyLookupContext &lookup_context) const
1982   {
1983     const HeadlessArrayOf<HBUINT16> &input = StructAfter<HeadlessArrayOf<HBUINT16>> (backtrack);
1984     const ArrayOf<HBUINT16> &lookahead = StructAfter<ArrayOf<HBUINT16>> (input);
1985     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord>> (lookahead);
1986     return chain_context_would_apply_lookup (c,
1987                                              backtrack.len, backtrack.arrayZ,
1988                                              input.lenP1, input.arrayZ,
1989                                              lookahead.len, lookahead.arrayZ, lookup.len,
1990                                              lookup.arrayZ, lookup_context);
1991   }
1992
1993   bool apply (hb_ot_apply_context_t *c, ChainContextApplyLookupContext &lookup_context) const
1994   {
1995     TRACE_APPLY (this);
1996     const HeadlessArrayOf<HBUINT16> &input = StructAfter<HeadlessArrayOf<HBUINT16>> (backtrack);
1997     const ArrayOf<HBUINT16> &lookahead = StructAfter<ArrayOf<HBUINT16>> (input);
1998     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord>> (lookahead);
1999     return_trace (chain_context_apply_lookup (c,
2000                                               backtrack.len, backtrack.arrayZ,
2001                                               input.lenP1, input.arrayZ,
2002                                               lookahead.len, lookahead.arrayZ, lookup.len,
2003                                               lookup.arrayZ, lookup_context));
2004   }
2005
2006   template<typename Iterator,
2007            hb_requires (hb_is_iterator (Iterator))>
2008   void serialize_array (hb_serialize_context_t *c,
2009                         HBUINT16 len,
2010                         Iterator it) const
2011   {
2012     c->copy (len);
2013     for (const auto g : it)
2014     {
2015       HBUINT16 gid;
2016       gid = g;
2017       c->copy (gid);
2018     }
2019   }
2020
2021   ChainRule* copy (hb_serialize_context_t *c,
2022                    const hb_map_t *backtrack_map,
2023                    const hb_map_t *input_map = nullptr,
2024                    const hb_map_t *lookahead_map = nullptr) const
2025   {
2026     TRACE_SERIALIZE (this);
2027     auto *out = c->start_embed (this);
2028     if (unlikely (!out)) return_trace (nullptr);
2029
2030     const hb_map_t *mapping = backtrack_map;
2031     serialize_array (c, backtrack.len, + backtrack.iter ()
2032                                        | hb_map (mapping));
2033
2034     const HeadlessArrayOf<HBUINT16> &input = StructAfter<HeadlessArrayOf<HBUINT16>> (backtrack);
2035     if (input_map) mapping = input_map;
2036     serialize_array (c, input.lenP1, + input.iter ()
2037                                      | hb_map (mapping));
2038
2039     const ArrayOf<HBUINT16> &lookahead = StructAfter<ArrayOf<HBUINT16>> (input);
2040     if (lookahead_map) mapping = lookahead_map;
2041     serialize_array (c, lookahead.len, + lookahead.iter ()
2042                                        | hb_map (mapping));
2043
2044     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord>> (lookahead);
2045     c->copy (lookup);
2046
2047     return_trace (out);
2048   }
2049
2050   bool subset (hb_subset_context_t *c,
2051                const hb_map_t *backtrack_map = nullptr,
2052                const hb_map_t *input_map = nullptr,
2053                const hb_map_t *lookahead_map = nullptr) const
2054   {
2055     TRACE_SUBSET (this);
2056
2057     const HeadlessArrayOf<HBUINT16> &input = StructAfter<HeadlessArrayOf<HBUINT16>> (backtrack);
2058     const ArrayOf<HBUINT16> &lookahead = StructAfter<ArrayOf<HBUINT16>> (input);
2059
2060     if (!backtrack_map)
2061     {
2062       const hb_set_t &glyphset = *c->plan->glyphset ();
2063       if (!hb_all (backtrack, glyphset) ||
2064           !hb_all (input, glyphset) ||
2065           !hb_all (lookahead, glyphset))
2066         return_trace (false);
2067
2068       copy (c->serializer, c->plan->glyph_map);
2069     }
2070     else
2071     {
2072       if (!hb_all (backtrack, backtrack_map) ||
2073           !hb_all (input, input_map) ||
2074           !hb_all (lookahead, lookahead_map))
2075         return_trace (false);
2076
2077       copy (c->serializer, backtrack_map, input_map, lookahead_map);
2078     }
2079
2080     return_trace (true);
2081   }
2082
2083   bool sanitize (hb_sanitize_context_t *c) const
2084   {
2085     TRACE_SANITIZE (this);
2086     if (!backtrack.sanitize (c)) return_trace (false);
2087     const HeadlessArrayOf<HBUINT16> &input = StructAfter<HeadlessArrayOf<HBUINT16>> (backtrack);
2088     if (!input.sanitize (c)) return_trace (false);
2089     const ArrayOf<HBUINT16> &lookahead = StructAfter<ArrayOf<HBUINT16>> (input);
2090     if (!lookahead.sanitize (c)) return_trace (false);
2091     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord>> (lookahead);
2092     return_trace (lookup.sanitize (c));
2093   }
2094
2095   protected:
2096   ArrayOf<HBUINT16>
2097                 backtrack;              /* Array of backtracking values
2098                                          * (to be matched before the input
2099                                          * sequence) */
2100   HeadlessArrayOf<HBUINT16>
2101                 inputX;                 /* Array of input values (start with
2102                                          * second glyph) */
2103   ArrayOf<HBUINT16>
2104                 lookaheadX;             /* Array of lookahead values's (to be
2105                                          * matched after the input sequence) */
2106   ArrayOf<LookupRecord>
2107                 lookupX;                /* Array of LookupRecords--in
2108                                          * design order) */
2109   public:
2110   DEFINE_SIZE_MIN (8);
2111 };
2112
2113 struct ChainRuleSet
2114 {
2115   bool intersects (const hb_set_t *glyphs, ChainContextClosureLookupContext &lookup_context) const
2116   {
2117     return
2118     + hb_iter (rule)
2119     | hb_map (hb_add (this))
2120     | hb_map ([&] (const ChainRule &_) { return _.intersects (glyphs, lookup_context); })
2121     | hb_any
2122     ;
2123   }
2124   void closure (hb_closure_context_t *c, ChainContextClosureLookupContext &lookup_context) const
2125   {
2126     return
2127     + hb_iter (rule)
2128     | hb_map (hb_add (this))
2129     | hb_apply ([&] (const ChainRule &_) { _.closure (c, lookup_context); })
2130     ;
2131   }
2132
2133   void collect_glyphs (hb_collect_glyphs_context_t *c, ChainContextCollectGlyphsLookupContext &lookup_context) const
2134   {
2135     return
2136     + hb_iter (rule)
2137     | hb_map (hb_add (this))
2138     | hb_apply ([&] (const ChainRule &_) { _.collect_glyphs (c, lookup_context); })
2139     ;
2140   }
2141
2142   bool would_apply (hb_would_apply_context_t *c, ChainContextApplyLookupContext &lookup_context) const
2143   {
2144     return
2145     + hb_iter (rule)
2146     | hb_map (hb_add (this))
2147     | hb_map ([&] (const ChainRule &_) { return _.would_apply (c, lookup_context); })
2148     | hb_any
2149     ;
2150   }
2151
2152   bool apply (hb_ot_apply_context_t *c, ChainContextApplyLookupContext &lookup_context) const
2153   {
2154     TRACE_APPLY (this);
2155     return_trace (
2156     + hb_iter (rule)
2157     | hb_map (hb_add (this))
2158     | hb_map ([&] (const ChainRule &_) { return _.apply (c, lookup_context); })
2159     | hb_any
2160     )
2161     ;
2162   }
2163
2164   bool subset (hb_subset_context_t *c,
2165                const hb_map_t *backtrack_klass_map = nullptr,
2166                const hb_map_t *input_klass_map = nullptr,
2167                const hb_map_t *lookahead_klass_map = nullptr) const
2168   {
2169     TRACE_SUBSET (this);
2170
2171     auto snap = c->serializer->snapshot ();
2172     auto *out = c->serializer->start_embed (*this);
2173     if (unlikely (!c->serializer->extend_min (out))) return_trace (false);
2174
2175     for (const OffsetTo<ChainRule>& _ : rule)
2176     {
2177       if (!_) continue;
2178       auto *o = out->rule.serialize_append (c->serializer);
2179       if (unlikely (!o)) continue;
2180
2181       auto o_snap = c->serializer->snapshot ();
2182       if (!o->serialize_subset (c, _, this, out,
2183                                 backtrack_klass_map,
2184                                 input_klass_map,
2185                                 lookahead_klass_map))
2186       {
2187         out->rule.pop ();
2188         c->serializer->revert (o_snap);
2189       }
2190     }
2191
2192     bool ret = bool (out->rule);
2193     if (!ret) c->serializer->revert (snap);
2194
2195     return_trace (ret);
2196   }
2197
2198   bool sanitize (hb_sanitize_context_t *c) const
2199   {
2200     TRACE_SANITIZE (this);
2201     return_trace (rule.sanitize (c, this));
2202   }
2203
2204   protected:
2205   OffsetArrayOf<ChainRule>
2206                 rule;                   /* Array of ChainRule tables
2207                                          * ordered by preference */
2208   public:
2209   DEFINE_SIZE_ARRAY (2, rule);
2210 };
2211
2212 struct ChainContextFormat1
2213 {
2214   bool intersects (const hb_set_t *glyphs) const
2215   {
2216     struct ChainContextClosureLookupContext lookup_context = {
2217       {intersects_glyph},
2218       {nullptr, nullptr, nullptr}
2219     };
2220
2221     return
2222     + hb_zip (this+coverage, ruleSet)
2223     | hb_filter (*glyphs, hb_first)
2224     | hb_map (hb_second)
2225     | hb_map (hb_add (this))
2226     | hb_map ([&] (const ChainRuleSet &_) { return _.intersects (glyphs, lookup_context); })
2227     | hb_any
2228     ;
2229   }
2230
2231   void closure (hb_closure_context_t *c) const
2232   {
2233     struct ChainContextClosureLookupContext lookup_context = {
2234       {intersects_glyph},
2235       {nullptr, nullptr, nullptr}
2236     };
2237
2238     + hb_zip (this+coverage, ruleSet)
2239     | hb_filter (*c->glyphs, hb_first)
2240     | hb_map (hb_second)
2241     | hb_map (hb_add (this))
2242     | hb_apply ([&] (const ChainRuleSet &_) { _.closure (c, lookup_context); })
2243     ;
2244   }
2245
2246   void collect_glyphs (hb_collect_glyphs_context_t *c) const
2247   {
2248     (this+coverage).add_coverage (c->input);
2249
2250     struct ChainContextCollectGlyphsLookupContext lookup_context = {
2251       {collect_glyph},
2252       {nullptr, nullptr, nullptr}
2253     };
2254
2255     + hb_iter (ruleSet)
2256     | hb_map (hb_add (this))
2257     | hb_apply ([&] (const ChainRuleSet &_) { _.collect_glyphs (c, lookup_context); })
2258     ;
2259   }
2260
2261   bool would_apply (hb_would_apply_context_t *c) const
2262   {
2263     const ChainRuleSet &rule_set = this+ruleSet[(this+coverage).get_coverage (c->glyphs[0])];
2264     struct ChainContextApplyLookupContext lookup_context = {
2265       {match_glyph},
2266       {nullptr, nullptr, nullptr}
2267     };
2268     return rule_set.would_apply (c, lookup_context);
2269   }
2270
2271   const Coverage &get_coverage () const { return this+coverage; }
2272
2273   bool apply (hb_ot_apply_context_t *c) const
2274   {
2275     TRACE_APPLY (this);
2276     unsigned int index = (this+coverage).get_coverage (c->buffer->cur().codepoint);
2277     if (likely (index == NOT_COVERED)) return_trace (false);
2278
2279     const ChainRuleSet &rule_set = this+ruleSet[index];
2280     struct ChainContextApplyLookupContext lookup_context = {
2281       {match_glyph},
2282       {nullptr, nullptr, nullptr}
2283     };
2284     return_trace (rule_set.apply (c, lookup_context));
2285   }
2286
2287   bool subset (hb_subset_context_t *c) const
2288   {
2289     TRACE_SUBSET (this);
2290     const hb_set_t &glyphset = *c->plan->glyphset ();
2291     const hb_map_t &glyph_map = *c->plan->glyph_map;
2292
2293     auto *out = c->serializer->start_embed (*this);
2294     if (unlikely (!c->serializer->extend_min (out))) return_trace (false);
2295     out->format = format;
2296
2297     hb_sorted_vector_t<hb_codepoint_t> new_coverage;
2298     + hb_zip (this+coverage, ruleSet)
2299     | hb_filter (glyphset, hb_first)
2300     | hb_filter (subset_offset_array (c, out->ruleSet, this, out), hb_second)
2301     | hb_map (hb_first)
2302     | hb_map (glyph_map)
2303     | hb_sink (new_coverage)
2304     ;
2305
2306     out->coverage.serialize (c->serializer, out)
2307                  .serialize (c->serializer, new_coverage.iter ());
2308     return_trace (bool (new_coverage));
2309   }
2310
2311   bool sanitize (hb_sanitize_context_t *c) const
2312   {
2313     TRACE_SANITIZE (this);
2314     return_trace (coverage.sanitize (c, this) && ruleSet.sanitize (c, this));
2315   }
2316
2317   protected:
2318   HBUINT16      format;                 /* Format identifier--format = 1 */
2319   OffsetTo<Coverage>
2320                 coverage;               /* Offset to Coverage table--from
2321                                          * beginning of table */
2322   OffsetArrayOf<ChainRuleSet>
2323                 ruleSet;                /* Array of ChainRuleSet tables
2324                                          * ordered by Coverage Index */
2325   public:
2326   DEFINE_SIZE_ARRAY (6, ruleSet);
2327 };
2328
2329 struct ChainContextFormat2
2330 {
2331   bool intersects (const hb_set_t *glyphs) const
2332   {
2333     if (!(this+coverage).intersects (glyphs))
2334       return false;
2335
2336     const ClassDef &backtrack_class_def = this+backtrackClassDef;
2337     const ClassDef &input_class_def = this+inputClassDef;
2338     const ClassDef &lookahead_class_def = this+lookaheadClassDef;
2339
2340     struct ChainContextClosureLookupContext lookup_context = {
2341       {intersects_class},
2342       {&backtrack_class_def,
2343        &input_class_def,
2344        &lookahead_class_def}
2345     };
2346
2347     return
2348     + hb_enumerate (ruleSet)
2349     | hb_map ([&] (const hb_pair_t<unsigned, const OffsetTo<ChainRuleSet> &> p)
2350               { return input_class_def.intersects_class (glyphs, p.first) &&
2351                        (this+p.second).intersects (glyphs, lookup_context); })
2352     | hb_any
2353     ;
2354   }
2355   void closure (hb_closure_context_t *c) const
2356   {
2357     if (!(this+coverage).intersects (c->glyphs))
2358       return;
2359
2360     const ClassDef &backtrack_class_def = this+backtrackClassDef;
2361     const ClassDef &input_class_def = this+inputClassDef;
2362     const ClassDef &lookahead_class_def = this+lookaheadClassDef;
2363
2364     struct ChainContextClosureLookupContext lookup_context = {
2365       {intersects_class},
2366       {&backtrack_class_def,
2367        &input_class_def,
2368        &lookahead_class_def}
2369     };
2370
2371     return
2372     + hb_enumerate (ruleSet)
2373     | hb_filter ([&] (unsigned _)
2374                  { return input_class_def.intersects_class (c->glyphs, _); },
2375                  hb_first)
2376     | hb_map (hb_second)
2377     | hb_map (hb_add (this))
2378     | hb_apply ([&] (const ChainRuleSet &_) { _.closure (c, lookup_context); })
2379     ;
2380   }
2381
2382   void collect_glyphs (hb_collect_glyphs_context_t *c) const
2383   {
2384     (this+coverage).add_coverage (c->input);
2385
2386     const ClassDef &backtrack_class_def = this+backtrackClassDef;
2387     const ClassDef &input_class_def = this+inputClassDef;
2388     const ClassDef &lookahead_class_def = this+lookaheadClassDef;
2389
2390     struct ChainContextCollectGlyphsLookupContext lookup_context = {
2391       {collect_class},
2392       {&backtrack_class_def,
2393        &input_class_def,
2394        &lookahead_class_def}
2395     };
2396
2397     + hb_iter (ruleSet)
2398     | hb_map (hb_add (this))
2399     | hb_apply ([&] (const ChainRuleSet &_) { _.collect_glyphs (c, lookup_context); })
2400     ;
2401   }
2402
2403   bool would_apply (hb_would_apply_context_t *c) const
2404   {
2405     const ClassDef &backtrack_class_def = this+backtrackClassDef;
2406     const ClassDef &input_class_def = this+inputClassDef;
2407     const ClassDef &lookahead_class_def = this+lookaheadClassDef;
2408
2409     unsigned int index = input_class_def.get_class (c->glyphs[0]);
2410     const ChainRuleSet &rule_set = this+ruleSet[index];
2411     struct ChainContextApplyLookupContext lookup_context = {
2412       {match_class},
2413       {&backtrack_class_def,
2414        &input_class_def,
2415        &lookahead_class_def}
2416     };
2417     return rule_set.would_apply (c, lookup_context);
2418   }
2419
2420   const Coverage &get_coverage () const { return this+coverage; }
2421
2422   bool apply (hb_ot_apply_context_t *c) const
2423   {
2424     TRACE_APPLY (this);
2425     unsigned int index = (this+coverage).get_coverage (c->buffer->cur().codepoint);
2426     if (likely (index == NOT_COVERED)) return_trace (false);
2427
2428     const ClassDef &backtrack_class_def = this+backtrackClassDef;
2429     const ClassDef &input_class_def = this+inputClassDef;
2430     const ClassDef &lookahead_class_def = this+lookaheadClassDef;
2431
2432     index = input_class_def.get_class (c->buffer->cur().codepoint);
2433     const ChainRuleSet &rule_set = this+ruleSet[index];
2434     struct ChainContextApplyLookupContext lookup_context = {
2435       {match_class},
2436       {&backtrack_class_def,
2437        &input_class_def,
2438        &lookahead_class_def}
2439     };
2440     return_trace (rule_set.apply (c, lookup_context));
2441   }
2442
2443   bool subset (hb_subset_context_t *c) const
2444   {
2445     TRACE_SUBSET (this);
2446     auto *out = c->serializer->start_embed (*this);
2447     if (unlikely (!c->serializer->extend_min (out))) return_trace (false);
2448     out->format = format;
2449     out->coverage.serialize_subset (c, coverage, this, out);
2450
2451     hb_map_t backtrack_klass_map;
2452     out->backtrackClassDef.serialize_subset (c, backtrackClassDef, this, out, &backtrack_klass_map);
2453
2454     // subset inputClassDef based on glyphs survived in Coverage subsetting
2455     hb_map_t input_klass_map;
2456     out->inputClassDef.serialize_subset (c, inputClassDef, this, out, &input_klass_map);
2457
2458     hb_map_t lookahead_klass_map;
2459     out->lookaheadClassDef.serialize_subset (c, lookaheadClassDef, this, out, &lookahead_klass_map);
2460
2461     hb_vector_t<unsigned> rulesets;
2462     bool ret = true;
2463     for (const OffsetTo<ChainRuleSet>& _ : + hb_enumerate (ruleSet)
2464                                            | hb_filter (input_klass_map, hb_first)
2465                                            | hb_map (hb_second))
2466     {
2467       auto *o = out->ruleSet.serialize_append (c->serializer);
2468       if (unlikely (!o))
2469       {
2470         ret = false;
2471         break;
2472       }
2473       if (!o->serialize_subset (c, _, this, out,
2474                                 &backtrack_klass_map,
2475                                 &input_klass_map,
2476                                 &lookahead_klass_map))
2477       {
2478         rulesets.push (0);
2479       }
2480       else rulesets.push (1);
2481     }
2482
2483     if (!ret) return_trace (ret);
2484
2485     //prune empty trailing ruleSets
2486     unsigned count = rulesets.length;
2487     while (count > 0 && rulesets[count-1] == 0)
2488     {
2489       out->ruleSet.pop ();
2490       count--;
2491     }
2492
2493     return_trace (bool (out->ruleSet));
2494   }
2495
2496   bool sanitize (hb_sanitize_context_t *c) const
2497   {
2498     TRACE_SANITIZE (this);
2499     return_trace (coverage.sanitize (c, this) &&
2500                   backtrackClassDef.sanitize (c, this) &&
2501                   inputClassDef.sanitize (c, this) &&
2502                   lookaheadClassDef.sanitize (c, this) &&
2503                   ruleSet.sanitize (c, this));
2504   }
2505
2506   protected:
2507   HBUINT16      format;                 /* Format identifier--format = 2 */
2508   OffsetTo<Coverage>
2509                 coverage;               /* Offset to Coverage table--from
2510                                          * beginning of table */
2511   OffsetTo<ClassDef>
2512                 backtrackClassDef;      /* Offset to glyph ClassDef table
2513                                          * containing backtrack sequence
2514                                          * data--from beginning of table */
2515   OffsetTo<ClassDef>
2516                 inputClassDef;          /* Offset to glyph ClassDef
2517                                          * table containing input sequence
2518                                          * data--from beginning of table */
2519   OffsetTo<ClassDef>
2520                 lookaheadClassDef;      /* Offset to glyph ClassDef table
2521                                          * containing lookahead sequence
2522                                          * data--from beginning of table */
2523   OffsetArrayOf<ChainRuleSet>
2524                 ruleSet;                /* Array of ChainRuleSet tables
2525                                          * ordered by class */
2526   public:
2527   DEFINE_SIZE_ARRAY (12, ruleSet);
2528 };
2529
2530 struct ChainContextFormat3
2531 {
2532   bool intersects (const hb_set_t *glyphs) const
2533   {
2534     const OffsetArrayOf<Coverage> &input = StructAfter<OffsetArrayOf<Coverage>> (backtrack);
2535
2536     if (!(this+input[0]).intersects (glyphs))
2537       return false;
2538
2539     const OffsetArrayOf<Coverage> &lookahead = StructAfter<OffsetArrayOf<Coverage>> (input);
2540     struct ChainContextClosureLookupContext lookup_context = {
2541       {intersects_coverage},
2542       {this, this, this}
2543     };
2544     return chain_context_intersects (glyphs,
2545                                      backtrack.len, (const HBUINT16 *) backtrack.arrayZ,
2546                                      input.len, (const HBUINT16 *) input.arrayZ + 1,
2547                                      lookahead.len, (const HBUINT16 *) lookahead.arrayZ,
2548                                      lookup_context);
2549   }
2550
2551   void closure (hb_closure_context_t *c) const
2552   {
2553     const OffsetArrayOf<Coverage> &input = StructAfter<OffsetArrayOf<Coverage>> (backtrack);
2554
2555     if (!(this+input[0]).intersects (c->glyphs))
2556       return;
2557
2558     const OffsetArrayOf<Coverage> &lookahead = StructAfter<OffsetArrayOf<Coverage>> (input);
2559     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord>> (lookahead);
2560     struct ChainContextClosureLookupContext lookup_context = {
2561       {intersects_coverage},
2562       {this, this, this}
2563     };
2564     chain_context_closure_lookup (c,
2565                                   backtrack.len, (const HBUINT16 *) backtrack.arrayZ,
2566                                   input.len, (const HBUINT16 *) input.arrayZ + 1,
2567                                   lookahead.len, (const HBUINT16 *) lookahead.arrayZ,
2568                                   lookup.len, lookup.arrayZ,
2569                                   lookup_context);
2570   }
2571
2572   void collect_glyphs (hb_collect_glyphs_context_t *c) const
2573   {
2574     const OffsetArrayOf<Coverage> &input = StructAfter<OffsetArrayOf<Coverage>> (backtrack);
2575
2576     (this+input[0]).add_coverage (c->input);
2577
2578     const OffsetArrayOf<Coverage> &lookahead = StructAfter<OffsetArrayOf<Coverage>> (input);
2579     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord>> (lookahead);
2580     struct ChainContextCollectGlyphsLookupContext lookup_context = {
2581       {collect_coverage},
2582       {this, this, this}
2583     };
2584     chain_context_collect_glyphs_lookup (c,
2585                                          backtrack.len, (const HBUINT16 *) backtrack.arrayZ,
2586                                          input.len, (const HBUINT16 *) input.arrayZ + 1,
2587                                          lookahead.len, (const HBUINT16 *) lookahead.arrayZ,
2588                                          lookup.len, lookup.arrayZ,
2589                                          lookup_context);
2590   }
2591
2592   bool would_apply (hb_would_apply_context_t *c) const
2593   {
2594     const OffsetArrayOf<Coverage> &input = StructAfter<OffsetArrayOf<Coverage>> (backtrack);
2595     const OffsetArrayOf<Coverage> &lookahead = StructAfter<OffsetArrayOf<Coverage>> (input);
2596     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord>> (lookahead);
2597     struct ChainContextApplyLookupContext lookup_context = {
2598       {match_coverage},
2599       {this, this, this}
2600     };
2601     return chain_context_would_apply_lookup (c,
2602                                              backtrack.len, (const HBUINT16 *) backtrack.arrayZ,
2603                                              input.len, (const HBUINT16 *) input.arrayZ + 1,
2604                                              lookahead.len, (const HBUINT16 *) lookahead.arrayZ,
2605                                              lookup.len, lookup.arrayZ, lookup_context);
2606   }
2607
2608   const Coverage &get_coverage () const
2609   {
2610     const OffsetArrayOf<Coverage> &input = StructAfter<OffsetArrayOf<Coverage>> (backtrack);
2611     return this+input[0];
2612   }
2613
2614   bool apply (hb_ot_apply_context_t *c) const
2615   {
2616     TRACE_APPLY (this);
2617     const OffsetArrayOf<Coverage> &input = StructAfter<OffsetArrayOf<Coverage>> (backtrack);
2618
2619     unsigned int index = (this+input[0]).get_coverage (c->buffer->cur().codepoint);
2620     if (likely (index == NOT_COVERED)) return_trace (false);
2621
2622     const OffsetArrayOf<Coverage> &lookahead = StructAfter<OffsetArrayOf<Coverage>> (input);
2623     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord>> (lookahead);
2624     struct ChainContextApplyLookupContext lookup_context = {
2625       {match_coverage},
2626       {this, this, this}
2627     };
2628     return_trace (chain_context_apply_lookup (c,
2629                                               backtrack.len, (const HBUINT16 *) backtrack.arrayZ,
2630                                               input.len, (const HBUINT16 *) input.arrayZ + 1,
2631                                               lookahead.len, (const HBUINT16 *) lookahead.arrayZ,
2632                                               lookup.len, lookup.arrayZ, lookup_context));
2633   }
2634
2635   template<typename Iterator,
2636            hb_requires (hb_is_iterator (Iterator))>
2637   bool serialize_coverage_offsets (hb_subset_context_t *c,
2638                                    Iterator it,
2639                                    const void* src_base,
2640                                    const void* dst_base) const
2641   {
2642     TRACE_SERIALIZE (this);
2643     auto *out = c->serializer->start_embed<OffsetArrayOf<Coverage>> ();
2644
2645     if (unlikely (!c->serializer->allocate_size<HBUINT16> (HBUINT16::static_size))) return_trace (false);
2646
2647     + it
2648     | hb_apply (subset_offset_array (c, *out, src_base, dst_base))
2649     ;
2650
2651     return_trace (out->len);
2652   }
2653
2654   bool subset (hb_subset_context_t *c) const
2655   {
2656     TRACE_SUBSET (this);
2657
2658     auto *out = c->serializer->start_embed (this);
2659     if (unlikely (!out)) return_trace (false);
2660     if (unlikely (!c->serializer->embed (this->format))) return_trace (false);
2661
2662     if (!serialize_coverage_offsets (c, backtrack.iter (), this, out))
2663       return_trace (false);
2664
2665     const OffsetArrayOf<Coverage> &input = StructAfter<OffsetArrayOf<Coverage>> (backtrack);
2666     if (!serialize_coverage_offsets (c, input.iter (), this, out))
2667       return_trace (false);
2668
2669     const OffsetArrayOf<Coverage> &lookahead = StructAfter<OffsetArrayOf<Coverage>> (input);
2670     if (!serialize_coverage_offsets (c, lookahead.iter (), this, out))
2671       return_trace (false);
2672
2673     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord>> (lookahead);
2674     return_trace (c->serializer->copy (lookup));
2675   }
2676
2677   bool sanitize (hb_sanitize_context_t *c) const
2678   {
2679     TRACE_SANITIZE (this);
2680     if (!backtrack.sanitize (c, this)) return_trace (false);
2681     const OffsetArrayOf<Coverage> &input = StructAfter<OffsetArrayOf<Coverage>> (backtrack);
2682     if (!input.sanitize (c, this)) return_trace (false);
2683     if (!input.len) return_trace (false); /* To be consistent with Context. */
2684     const OffsetArrayOf<Coverage> &lookahead = StructAfter<OffsetArrayOf<Coverage>> (input);
2685     if (!lookahead.sanitize (c, this)) return_trace (false);
2686     const ArrayOf<LookupRecord> &lookup = StructAfter<ArrayOf<LookupRecord>> (lookahead);
2687     return_trace (lookup.sanitize (c));
2688   }
2689
2690   protected:
2691   HBUINT16      format;                 /* Format identifier--format = 3 */
2692   OffsetArrayOf<Coverage>
2693                 backtrack;              /* Array of coverage tables
2694                                          * in backtracking sequence, in  glyph
2695                                          * sequence order */
2696   OffsetArrayOf<Coverage>
2697                 inputX          ;       /* Array of coverage
2698                                          * tables in input sequence, in glyph
2699                                          * sequence order */
2700   OffsetArrayOf<Coverage>
2701                 lookaheadX;             /* Array of coverage tables
2702                                          * in lookahead sequence, in glyph
2703                                          * sequence order */
2704   ArrayOf<LookupRecord>
2705                 lookupX;                /* Array of LookupRecords--in
2706                                          * design order) */
2707   public:
2708   DEFINE_SIZE_MIN (10);
2709 };
2710
2711 struct ChainContext
2712 {
2713   template <typename context_t, typename ...Ts>
2714   typename context_t::return_t dispatch (context_t *c, Ts&&... ds) const
2715   {
2716     TRACE_DISPATCH (this, u.format);
2717     if (unlikely (!c->may_dispatch (this, &u.format))) return_trace (c->no_dispatch_return_value ());
2718     switch (u.format) {
2719     case 1: return_trace (c->dispatch (u.format1, hb_forward<Ts> (ds)...));
2720     case 2: return_trace (c->dispatch (u.format2, hb_forward<Ts> (ds)...));
2721     case 3: return_trace (c->dispatch (u.format3, hb_forward<Ts> (ds)...));
2722     default:return_trace (c->default_return_value ());
2723     }
2724   }
2725
2726   protected:
2727   union {
2728   HBUINT16              format; /* Format identifier */
2729   ChainContextFormat1   format1;
2730   ChainContextFormat2   format2;
2731   ChainContextFormat3   format3;
2732   } u;
2733 };
2734
2735
2736 template <typename T>
2737 struct ExtensionFormat1
2738 {
2739   unsigned int get_type () const { return extensionLookupType; }
2740
2741   template <typename X>
2742   const X& get_subtable () const
2743   { return this + CastR<LOffsetTo<typename T::SubTable>> (extensionOffset); }
2744
2745   template <typename context_t, typename ...Ts>
2746   typename context_t::return_t dispatch (context_t *c, Ts&&... ds) const
2747   {
2748     TRACE_DISPATCH (this, format);
2749     if (unlikely (!c->may_dispatch (this, this))) return_trace (c->no_dispatch_return_value ());
2750     return_trace (get_subtable<typename T::SubTable> ().dispatch (c, get_type (), hb_forward<Ts> (ds)...));
2751   }
2752
2753   /* This is called from may_dispatch() above with hb_sanitize_context_t. */
2754   bool sanitize (hb_sanitize_context_t *c) const
2755   {
2756     TRACE_SANITIZE (this);
2757     return_trace (c->check_struct (this) &&
2758                   extensionLookupType != T::SubTable::Extension);
2759   }
2760
2761   protected:
2762   HBUINT16      format;                 /* Format identifier. Set to 1. */
2763   HBUINT16      extensionLookupType;    /* Lookup type of subtable referenced
2764                                          * by ExtensionOffset (i.e. the
2765                                          * extension subtable). */
2766   Offset32      extensionOffset;        /* Offset to the extension subtable,
2767                                          * of lookup type subtable. */
2768   public:
2769   DEFINE_SIZE_STATIC (8);
2770 };
2771
2772 template <typename T>
2773 struct Extension
2774 {
2775   unsigned int get_type () const
2776   {
2777     switch (u.format) {
2778     case 1: return u.format1.get_type ();
2779     default:return 0;
2780     }
2781   }
2782   template <typename X>
2783   const X& get_subtable () const
2784   {
2785     switch (u.format) {
2786     case 1: return u.format1.template get_subtable<typename T::SubTable> ();
2787     default:return Null(typename T::SubTable);
2788     }
2789   }
2790
2791   template <typename context_t, typename ...Ts>
2792   typename context_t::return_t dispatch (context_t *c, Ts&&... ds) const
2793   {
2794     TRACE_DISPATCH (this, u.format);
2795     if (unlikely (!c->may_dispatch (this, &u.format))) return_trace (c->no_dispatch_return_value ());
2796     switch (u.format) {
2797     case 1: return_trace (u.format1.dispatch (c, hb_forward<Ts> (ds)...));
2798     default:return_trace (c->default_return_value ());
2799     }
2800   }
2801
2802   protected:
2803   union {
2804   HBUINT16              format;         /* Format identifier */
2805   ExtensionFormat1<T>   format1;
2806   } u;
2807 };
2808
2809
2810 /*
2811  * GSUB/GPOS Common
2812  */
2813
2814 struct hb_ot_layout_lookup_accelerator_t
2815 {
2816   template <typename TLookup>
2817   void init (const TLookup &lookup)
2818   {
2819     digest.init ();
2820     lookup.add_coverage (&digest);
2821
2822     subtables.init ();
2823     OT::hb_get_subtables_context_t c_get_subtables (subtables);
2824     lookup.dispatch (&c_get_subtables);
2825   }
2826   void fini () { subtables.fini (); }
2827
2828   bool may_have (hb_codepoint_t g) const
2829   { return digest.may_have (g); }
2830
2831   bool apply (hb_ot_apply_context_t *c) const
2832   {
2833     for (unsigned int i = 0; i < subtables.length; i++)
2834       if (subtables[i].apply (c))
2835         return true;
2836     return false;
2837   }
2838
2839   private:
2840   hb_set_digest_t digest;
2841   hb_get_subtables_context_t::array_t subtables;
2842 };
2843
2844 struct GSUBGPOS
2845 {
2846   bool has_data () const { return version.to_int (); }
2847   unsigned int get_script_count () const
2848   { return (this+scriptList).len; }
2849   const Tag& get_script_tag (unsigned int i) const
2850   { return (this+scriptList).get_tag (i); }
2851   unsigned int get_script_tags (unsigned int start_offset,
2852                                 unsigned int *script_count /* IN/OUT */,
2853                                 hb_tag_t     *script_tags /* OUT */) const
2854   { return (this+scriptList).get_tags (start_offset, script_count, script_tags); }
2855   const Script& get_script (unsigned int i) const
2856   { return (this+scriptList)[i]; }
2857   bool find_script_index (hb_tag_t tag, unsigned int *index) const
2858   { return (this+scriptList).find_index (tag, index); }
2859
2860   unsigned int get_feature_count () const
2861   { return (this+featureList).len; }
2862   hb_tag_t get_feature_tag (unsigned int i) const
2863   { return i == Index::NOT_FOUND_INDEX ? HB_TAG_NONE : (this+featureList).get_tag (i); }
2864   unsigned int get_feature_tags (unsigned int start_offset,
2865                                  unsigned int *feature_count /* IN/OUT */,
2866                                  hb_tag_t     *feature_tags /* OUT */) const
2867   { return (this+featureList).get_tags (start_offset, feature_count, feature_tags); }
2868   const Feature& get_feature (unsigned int i) const
2869   { return (this+featureList)[i]; }
2870   bool find_feature_index (hb_tag_t tag, unsigned int *index) const
2871   { return (this+featureList).find_index (tag, index); }
2872
2873   unsigned int get_lookup_count () const
2874   { return (this+lookupList).len; }
2875   const Lookup& get_lookup (unsigned int i) const
2876   { return (this+lookupList)[i]; }
2877
2878   bool find_variations_index (const int *coords, unsigned int num_coords,
2879                               unsigned int *index) const
2880   {
2881 #ifdef HB_NOVAR
2882     return false;
2883 #endif
2884     return (version.to_int () >= 0x00010001u ? this+featureVars : Null(FeatureVariations))
2885             .find_index (coords, num_coords, index);
2886   }
2887   const Feature& get_feature_variation (unsigned int feature_index,
2888                                         unsigned int variations_index) const
2889   {
2890 #ifndef HB_NO_VAR
2891     if (FeatureVariations::NOT_FOUND_INDEX != variations_index &&
2892         version.to_int () >= 0x00010001u)
2893     {
2894       const Feature *feature = (this+featureVars).find_substitute (variations_index,
2895                                                                    feature_index);
2896       if (feature)
2897         return *feature;
2898     }
2899 #endif
2900     return get_feature (feature_index);
2901   }
2902
2903   template <typename TLookup>
2904   bool subset (hb_subset_context_t *c) const
2905   {
2906     TRACE_SUBSET (this);
2907     auto *out = c->serializer->embed (*this);
2908     if (unlikely (!out)) return_trace (false);
2909
2910     out->scriptList.serialize_subset (c, scriptList, this, out);
2911     out->featureList.serialize_subset (c, featureList, this, out);
2912
2913     typedef OffsetListOf<TLookup> TLookupList;
2914     /* TODO Use intersects() to count how many subtables survive? */
2915     CastR<OffsetTo<TLookupList>> (out->lookupList)
2916       .serialize_subset (c,
2917                          CastR<OffsetTo<TLookupList>> (lookupList),
2918                          this,
2919                          out);
2920
2921 #ifndef HB_NO_VAR
2922     if (version.to_int () >= 0x00010001u)
2923      out->featureVars.serialize_copy (c->serializer, featureVars, this, out);
2924 #endif
2925
2926     return_trace (true);
2927   }
2928
2929   unsigned int get_size () const
2930   {
2931     return min_size +
2932            (version.to_int () >= 0x00010001u ? featureVars.static_size : 0);
2933   }
2934
2935   template <typename TLookup>
2936   bool sanitize (hb_sanitize_context_t *c) const
2937   {
2938     TRACE_SANITIZE (this);
2939     typedef OffsetListOf<TLookup> TLookupList;
2940     if (unlikely (!(version.sanitize (c) &&
2941                     likely (version.major == 1) &&
2942                     scriptList.sanitize (c, this) &&
2943                     featureList.sanitize (c, this) &&
2944                     CastR<OffsetTo<TLookupList>> (lookupList).sanitize (c, this))))
2945       return_trace (false);
2946
2947 #ifndef HB_NO_VAR
2948     if (unlikely (!(version.to_int () < 0x00010001u || featureVars.sanitize (c, this))))
2949       return_trace (false);
2950 #endif
2951
2952     return_trace (true);
2953   }
2954
2955   template <typename T>
2956   struct accelerator_t
2957   {
2958     void init (hb_face_t *face)
2959     {
2960       this->table = hb_sanitize_context_t().reference_table<T> (face);
2961       if (unlikely (this->table->is_blacklisted (this->table.get_blob (), face)))
2962       {
2963         hb_blob_destroy (this->table.get_blob ());
2964         this->table = hb_blob_get_empty ();
2965       }
2966
2967       this->lookup_count = table->get_lookup_count ();
2968
2969       this->accels = (hb_ot_layout_lookup_accelerator_t *) calloc (this->lookup_count, sizeof (hb_ot_layout_lookup_accelerator_t));
2970       if (unlikely (!this->accels))
2971         this->lookup_count = 0;
2972
2973       for (unsigned int i = 0; i < this->lookup_count; i++)
2974         this->accels[i].init (table->get_lookup (i));
2975     }
2976
2977     void fini ()
2978     {
2979       for (unsigned int i = 0; i < this->lookup_count; i++)
2980         this->accels[i].fini ();
2981       free (this->accels);
2982       this->table.destroy ();
2983     }
2984
2985     hb_blob_ptr_t<T> table;
2986     unsigned int lookup_count;
2987     hb_ot_layout_lookup_accelerator_t *accels;
2988   };
2989
2990   protected:
2991   FixedVersion<>version;        /* Version of the GSUB/GPOS table--initially set
2992                                  * to 0x00010000u */
2993   OffsetTo<ScriptList>
2994                 scriptList;     /* ScriptList table */
2995   OffsetTo<FeatureList>
2996                 featureList;    /* FeatureList table */
2997   OffsetTo<LookupList>
2998                 lookupList;     /* LookupList table */
2999   LOffsetTo<FeatureVariations>
3000                 featureVars;    /* Offset to Feature Variations
3001                                    table--from beginning of table
3002                                  * (may be NULL).  Introduced
3003                                  * in version 0x00010001. */
3004   public:
3005   DEFINE_SIZE_MIN (10);
3006 };
3007
3008
3009 } /* namespace OT */
3010
3011
3012 #endif /* HB_OT_LAYOUT_GSUBGPOS_HH */