/*

 * Copyright © 2007,2008,2009  Red Hat, Inc.

 * Copyright © 2010,2012  Google, Inc.

 *

 *  This is part of HarfBuzz, a text shaping library.

 *

 * Permission is hereby granted, without written agreement and without

 * license or royalty fees, to use, copy, modify, and distribute this

 * software and its documentation for any purpose, provided that the

 * above copyright notice and the following two paragraphs appear in

 * all copies of this software.

 *

 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR

 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES

 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN

 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH

 * DAMAGE.

 *

 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,

 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND

 * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS

 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO

 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.

 *

 * Red Hat Author(s): Behdad Esfahbod

 * Google Author(s): Behdad Esfahbod

 */

#ifndef HB_OT_LAYOUT_COMMON_PRIVATE_HH

#define HB_OT_LAYOUT_COMMON_PRIVATE_HH

#include "hb-ot-layout-private.hh"

#include "hb-open-type-private.hh"

#include "hb-set-private.hh"

namespace OT {

#define TRACE_DISPATCH(this, format) \

        hb_auto_trace_t<context_t::max_debug_depth, typename context_t::return_t> trace \

        (&c->debug_depth, c->get_name (), this, HB_FUNC, \

         "format %d", (int) format);

#define NOT_COVERED             ((unsigned int) -1)

#define MAX_NESTING_LEVEL       6

#define MAX_CONTEXT_LENGTH      64

/*

 *

 * OpenType Layout Common Table Formats

 *

 */

/*

 * Script, ScriptList, LangSys, Feature, FeatureList, Lookup, LookupList

 */

template <typename Type>

struct Record

{

  inline int cmp (hb_tag_t a) const {

    return tag.cmp (a);

  }

  struct sanitize_closure_t {

    hb_tag_t tag;

    const void *list_base;

  };

  inline bool sanitize (hb_sanitize_context_t *c, const void *base) const

  {

    TRACE_SANITIZE (this);

    const sanitize_closure_t closure = {tag, base};

    return_trace (c->check_struct (this) && offset.sanitize (c, base, &closure));

  }

  Tag           tag;            /* 4-byte Tag identifier */

  OffsetTo<Type>

                offset;         /* Offset from beginning of object holding

                                 * the Record */

  public:

  DEFINE_SIZE_STATIC (6);

};

template <typename Type>

struct RecordArrayOf : SortedArrayOf<Record<Type> > {

  inline const Tag& get_tag (unsigned int i) const

  {

    /* We cheat slightly and don't define separate Null objects

     * for Record types.  Instead, we return the correct Null(Tag)

     * here. */

    if (unlikely (i >= this->len)) return Null(Tag);

    return (*this)[i].tag;

  }

  inline unsigned int get_tags (unsigned int start_offset,

                                unsigned int *record_count /* IN/OUT */,

                                hb_tag_t     *record_tags /* OUT */) const

  {

    if (record_count) {

      const Record<Type> *arr = this->sub_array (start_offset, record_count);

      unsigned int count = *record_count;

      for (unsigned int i = 0; i < count; i++)

        record_tags[i] = arr[i].tag;

    }

    return this->len;

  }

  inline bool find_index (hb_tag_t tag, unsigned int *index) const

  {

    /* If we want to allow non-sorted data, we can lsearch(). */

    int i = this->/*lsearch*/bsearch (tag);

    if (i != -1) {

        if (index) *index = i;

        return true;

    } else {

      if (index) *index = Index::NOT_FOUND_INDEX;

      return false;

    }

  }

};

template <typename Type>

struct RecordListOf : RecordArrayOf<Type>

{

  inline const Type& operator [] (unsigned int i) const

  { return this+RecordArrayOf<Type>::operator [](i).offset; }

  inline bool sanitize (hb_sanitize_context_t *c) const

  {

    TRACE_SANITIZE (this);

    return_trace (RecordArrayOf<Type>::sanitize (c, this));

  }

};

struct RangeRecord

{

  inline int cmp (hb_codepoint_t g) const {

    return g < start ? -1 : g <= end ? 0 : +1 ;

  }

  inline bool sanitize (hb_sanitize_context_t *c) const

  {

    TRACE_SANITIZE (this);

    return_trace (c->check_struct (this));

  }

  inline bool intersects (const hb_set_t *glyphs) const {

    return glyphs->intersects (start, end);

  }

  template <typename set_t>

  inline void add_coverage (set_t *glyphs) const {

    glyphs->add_range (start, end);

  }

  GlyphID       start;          /* First GlyphID in the range */

  GlyphID       end;            /* Last GlyphID in the range */

  USHORT        value;          /* Value */

  public:

  DEFINE_SIZE_STATIC (6);

};

DEFINE_NULL_DATA (RangeRecord, "\000\001");

struct IndexArray : ArrayOf<Index>

{

  inline unsigned int get_indexes (unsigned int start_offset,

                                   unsigned int *_count /* IN/OUT */,

                                   unsigned int *_indexes /* OUT */) const

  {

    if (_count) {

      const USHORT *arr = this->sub_array (start_offset, _count);

      unsigned int count = *_count;

      for (unsigned int i = 0; i < count; i++)

        _indexes[i] = arr[i];

    }

    return this->len;

  }

};

struct Script;

struct LangSys;

struct Feature;

struct LangSys

{

  inline unsigned int get_feature_count (void) const

  { return featureIndex.len; }

  inline hb_tag_t get_feature_index (unsigned int i) const

  { return featureIndex[i]; }

  inline unsigned int get_feature_indexes (unsigned int start_offset,

                                           unsigned int *feature_count /* IN/OUT */,

                                           unsigned int *feature_indexes /* OUT */) const

  { return featureIndex.get_indexes (start_offset, feature_count, feature_indexes); }

  inline bool has_required_feature (void) const { return reqFeatureIndex != 0xFFFFu; }

  inline unsigned int get_required_feature_index (void) const

  {

    if (reqFeatureIndex == 0xFFFFu)

      return Index::NOT_FOUND_INDEX;

   return reqFeatureIndex;;

  }

  inline bool sanitize (hb_sanitize_context_t *c,

                        const Record<LangSys>::sanitize_closure_t * = NULL) const

  {

    TRACE_SANITIZE (this);

    return_trace (c->check_struct (this) && featureIndex.sanitize (c));

  }

  Offset<>      lookupOrderZ;   /* = Null (reserved for an offset to a

                                 * reordering table) */

  USHORT        reqFeatureIndex;/* Index of a feature required for this

                                 * language system--if no required features

                                 * = 0xFFFFu */

  IndexArray    featureIndex;   /* Array of indices into the FeatureList */

  public:

  DEFINE_SIZE_ARRAY (6, featureIndex);

};

DEFINE_NULL_DATA (LangSys, "\0\0\xFF\xFF");

struct Script

{

  inline unsigned int get_lang_sys_count (void) const

  { return langSys.len; }

  inline const Tag& get_lang_sys_tag (unsigned int i) const

  { return langSys.get_tag (i); }

  inline unsigned int get_lang_sys_tags (unsigned int start_offset,

                                         unsigned int *lang_sys_count /* IN/OUT */,

                                         hb_tag_t     *lang_sys_tags /* OUT */) const

  { return langSys.get_tags (start_offset, lang_sys_count, lang_sys_tags); }

  inline const LangSys& get_lang_sys (unsigned int i) const

  {

    if (i == Index::NOT_FOUND_INDEX) return get_default_lang_sys ();

    return this+langSys[i].offset;

  }

  inline bool find_lang_sys_index (hb_tag_t tag, unsigned int *index) const

  { return langSys.find_index (tag, index); }

  inline bool has_default_lang_sys (void) const { return defaultLangSys != 0; }

  inline const LangSys& get_default_lang_sys (void) const { return this+defaultLangSys; }

  inline bool sanitize (hb_sanitize_context_t *c,

                        const Record<Script>::sanitize_closure_t * = NULL) const

  {

    TRACE_SANITIZE (this);

    return_trace (defaultLangSys.sanitize (c, this) && langSys.sanitize (c, this));

  }

  protected:

  OffsetTo<LangSys>

                defaultLangSys; /* Offset to DefaultLangSys table--from

                                 * beginning of Script table--may be Null */

  RecordArrayOf<LangSys>

                langSys;        /* Array of LangSysRecords--listed

                                 * alphabetically by LangSysTag */

  public:

  DEFINE_SIZE_ARRAY (4, langSys);

};

typedef RecordListOf<Script> ScriptList;

/* http://www.microsoft.com/typography/otspec/features_pt.htm#size */

struct FeatureParamsSize

{

  inline bool sanitize (hb_sanitize_context_t *c) const

  {

    TRACE_SANITIZE (this);

    if (unlikely (!c->check_struct (this))) return_trace (false);

    /* This subtable has some "history", if you will.  Some earlier versions of

     * Adobe tools calculated the offset of the FeatureParams sutable from the

     * beginning of the FeatureList table!  Now, that is dealt with in the

     * Feature implementation.  But we still need to be able to tell junk from

     * real data.  Note: We don't check that the nameID actually exists.

     *

     * Read Roberts wrote on 9/15/06 on opentype-list@indx.co.uk :

     *

     * Yes, it is correct that a new version of the AFDKO (version 2.0) will be

     * coming out soon, and that the makeotf program will build a font with a

     * 'size' feature that is correct by the specification.

     *

     * The specification for this feature tag is in the "OpenType Layout Tag

     * Registry". You can see a copy of this at:

     * http://partners.adobe.com/public/developer/opentype/index_tag8.html#size

     *

     * Here is one set of rules to determine if the 'size' feature is built

     * correctly, or as by the older versions of MakeOTF. You may be able to do

     * better.

     *

     * Assume that the offset to the size feature is according to specification,

     * and make the following value checks. If it fails, assume the the size

     * feature is calculated as versions of MakeOTF before the AFDKO 2.0 built it.

     * If this fails, reject the 'size' feature. The older makeOTF's calculated the

     * offset from the beginning of the FeatureList table, rather than from the

     * beginning of the 'size' Feature table.

     *

     * If "design size" == 0:

     *     fails check

     *

     * Else if ("subfamily identifier" == 0 and

     *     "range start" == 0 and

     *     "range end" == 0 and

     *     "range start" == 0 and

     *     "menu name ID" == 0)

     *     passes check: this is the format used when there is a design size

     * specified, but there is no recommended size range.

     *

     * Else if ("design size" <  "range start" or

     *     "design size" >   "range end" or

     *     "range end" <= "range start" or

     *     "menu name ID"  < 256 or

     *     "menu name ID"  > 32767 or

     *     menu name ID is not a name ID which is actually in the name table)

     *     fails test

     * Else

     *     passes test.

     */

    if (!designSize)

      return_trace (false);

    else if (subfamilyID == 0 &&

             subfamilyNameID == 0 &&

             rangeStart == 0 &&

             rangeEnd == 0)

      return_trace (true);

    else if (designSize < rangeStart ||

             designSize > rangeEnd ||

             subfamilyNameID < 256 ||

             subfamilyNameID > 32767)

      return_trace (false);

    else

      return_trace (true);

  }

  USHORT        designSize;     /* Represents the design size in 720/inch

                                 * units (decipoints).  The design size entry

                                 * must be non-zero.  When there is a design

                                 * size but no recommended size range, the

                                 * rest of the array will consist of zeros. */

  USHORT        subfamilyID;    /* Has no independent meaning, but serves

                                 * as an identifier that associates fonts

                                 * in a subfamily. All fonts which share a

                                 * Preferred or Font Family name and which

                                 * differ only by size range shall have the

                                 * same subfamily value, and no fonts which

                                 * differ in weight or style shall have the

                                 * same subfamily value. If this value is

                                 * zero, the remaining fields in the array

                                 * will be ignored. */

  USHORT        subfamilyNameID;/* If the preceding value is non-zero, this

                                 * value must be set in the range 256 - 32767

                                 * (inclusive). It records the value of a

                                 * field in the name table, which must

                                 * contain English-language strings encoded

                                 * in Windows Unicode and Macintosh Roman,

                                 * and may contain additional strings

                                 * localized to other scripts and languages.

                                 * Each of these strings is the name an

                                 * application should use, in combination

                                 * with the family name, to represent the

                                 * subfamily in a menu.  Applications will

                                 * choose the appropriate version based on

                                 * their selection criteria. */

  USHORT        rangeStart;     /* Large end of the recommended usage range

                                 * (inclusive), stored in 720/inch units

                                 * (decipoints). */

  USHORT        rangeEnd;       /* Small end of the recommended usage range

                                   (exclusive), stored in 720/inch units

                                 * (decipoints). */

  public:

  DEFINE_SIZE_STATIC (10);

};

/* http://www.microsoft.com/typography/otspec/features_pt.htm#ssxx */

struct FeatureParamsStylisticSet

{

  inline bool sanitize (hb_sanitize_context_t *c) const

  {

    TRACE_SANITIZE (this);

    /* Right now minorVersion is at zero.  Which means, any table supports

     * the uiNameID field. */

    return_trace (c->check_struct (this));

  }

  USHORT        version;        /* (set to 0): This corresponds to a “minor”

                                 * version number. Additional data may be

                                 * added to the end of this Feature Parameters

                                 * table in the future. */

  USHORT        uiNameID;       /* The 'name' table name ID that specifies a

                                 * string (or strings, for multiple languages)

                                 * for a user-interface label for this

                                 * feature.  The values of uiLabelNameId and

                                 * sampleTextNameId are expected to be in the

                                 * font-specific name ID range (256-32767),

                                 * though that is not a requirement in this

                                 * Feature Parameters specification. The

                                 * user-interface label for the feature can

                                 * be provided in multiple languages. An

                                 * English string should be included as a

                                 * fallback. The string should be kept to a

                                 * minimal length to fit comfortably with

                                 * different application interfaces. */

  public:

  DEFINE_SIZE_STATIC (4);

};

/* http://www.microsoft.com/typography/otspec/features_ae.htm#cv01-cv99 */

struct FeatureParamsCharacterVariants

{

  inline bool sanitize (hb_sanitize_context_t *c) const

  {

    TRACE_SANITIZE (this);

    return_trace (c->check_struct (this) &&

                  characters.sanitize (c));

  }

  USHORT        format;                 /* Format number is set to 0. */

  USHORT        featUILableNameID;      /* The ‘name’ table name ID that

                                         * specifies a string (or strings,

                                         * for multiple languages) for a

                                         * user-interface label for this

                                         * feature. (May be NULL.) */

  USHORT        featUITooltipTextNameID;/* The ‘name’ table name ID that

                                         * specifies a string (or strings,

                                         * for multiple languages) that an

                                         * application can use for tooltip

                                         * text for this feature. (May be

                                         * NULL.) */

  USHORT        sampleTextNameID;       /* The ‘name’ table name ID that

                                         * specifies sample text that

                                         * illustrates the effect of this

                                         * feature. (May be NULL.) */

  USHORT        numNamedParameters;     /* Number of named parameters. (May

                                         * be zero.) */

  USHORT        firstParamUILabelNameID;/* The first ‘name’ table name ID

                                         * used to specify strings for

                                         * user-interface labels for the

                                         * feature parameters. (Must be zero

                                         * if numParameters is zero.) */

  ArrayOf<UINT24>

                characters;             /* Array of the Unicode Scalar Value

                                         * of the characters for which this

                                         * feature provides glyph variants.

                                         * (May be zero.) */

  public:

  DEFINE_SIZE_ARRAY (14, characters);

};

struct FeatureParams

{

  inline bool sanitize (hb_sanitize_context_t *c, hb_tag_t tag) const

  {

    TRACE_SANITIZE (this);

    if (tag == HB_TAG ('s','i','z','e'))

      return_trace (u.size.sanitize (c));

    if ((tag & 0xFFFF0000u) == HB_TAG ('s','s','\0','\0')) /* ssXX */

      return_trace (u.stylisticSet.sanitize (c));

    if ((tag & 0xFFFF0000u) == HB_TAG ('c','v','\0','\0')) /* cvXX */

      return_trace (u.characterVariants.sanitize (c));

    return_trace (true);

  }

  inline const FeatureParamsSize& get_size_params (hb_tag_t tag) const

  {

    if (tag == HB_TAG ('s','i','z','e'))

      return u.size;

    return Null(FeatureParamsSize);

  }

  private:

  union {

  FeatureParamsSize                     size;

  FeatureParamsStylisticSet             stylisticSet;

  FeatureParamsCharacterVariants        characterVariants;

  } u;

  DEFINE_SIZE_STATIC (17);

};

struct Feature

{

  inline unsigned int get_lookup_count (void) const

  { return lookupIndex.len; }

  inline hb_tag_t get_lookup_index (unsigned int i) const

  { return lookupIndex[i]; }

  inline unsigned int get_lookup_indexes (unsigned int start_index,

                                          unsigned int *lookup_count /* IN/OUT */,

                                          unsigned int *lookup_tags /* OUT */) const

  { return lookupIndex.get_indexes (start_index, lookup_count, lookup_tags); }

  inline const FeatureParams &get_feature_params (void) const

  { return this+featureParams; }

  inline bool sanitize (hb_sanitize_context_t *c,

                        const Record<Feature>::sanitize_closure_t *closure) const

  {

    TRACE_SANITIZE (this);

    if (unlikely (!(c->check_struct (this) && lookupIndex.sanitize (c))))

      return_trace (false);

    /* Some earlier versions of Adobe tools calculated the offset of the

     * FeatureParams subtable from the beginning of the FeatureList table!

     *

     * If sanitizing "failed" for the FeatureParams subtable, try it with the

     * alternative location.  We would know sanitize "failed" if old value

     * of the offset was non-zero, but it's zeroed now.

     *

     * Only do this for the 'size' feature, since at the time of the faulty

     * Adobe tools, only the 'size' feature had FeatureParams defined.

     */

    OffsetTo<FeatureParams> orig_offset = featureParams;

    if (unlikely (!featureParams.sanitize (c, this, closure ? closure->tag : HB_TAG_NONE)))

      return_trace (false);

    if (likely (orig_offset.is_null ()))

      return_trace (true);

    if (featureParams == 0 && closure &&

        closure->tag == HB_TAG ('s','i','z','e') &&