--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/mupdf-source/thirdparty/harfbuzz/src/graph/gsubgpos-graph.hh	Mon Sep 15 11:43:07 2025 +0200
@@ -0,0 +1,414 @@
+/*
+ * Copyright © 2022  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.
+ *
+ * Google Author(s): Garret Rieger
+ */
+
+#include "graph.hh"
+#include "../hb-ot-layout-gsubgpos.hh"
+#include "../OT/Layout/GSUB/ExtensionSubst.hh"
+#include "gsubgpos-context.hh"
+#include "pairpos-graph.hh"
+#include "markbasepos-graph.hh"
+
+#ifndef GRAPH_GSUBGPOS_GRAPH_HH
+#define GRAPH_GSUBGPOS_GRAPH_HH
+
+namespace graph {
+
+struct Lookup;
+
+template<typename T>
+struct ExtensionFormat1 : public OT::ExtensionFormat1<T>
+{
+  void reset(unsigned type)
+  {
+    this->format = 1;
+    this->extensionLookupType = type;
+    this->extensionOffset = 0;
+  }
+
+  bool sanitize (graph_t::vertex_t& vertex) const
+  {
+    int64_t vertex_len = vertex.obj.tail - vertex.obj.head;
+    return vertex_len >= OT::ExtensionFormat1<T>::static_size;
+  }
+
+  unsigned get_lookup_type () const
+  {
+    return this->extensionLookupType;
+  }
+
+  unsigned get_subtable_index (graph_t& graph, unsigned this_index) const
+  {
+    return graph.index_for_offset (this_index, &this->extensionOffset);
+  }
+};
+
+struct Lookup : public OT::Lookup
+{
+  unsigned number_of_subtables () const
+  {
+    return subTable.len;
+  }
+
+  bool sanitize (graph_t::vertex_t& vertex) const
+  {
+    int64_t vertex_len = vertex.obj.tail - vertex.obj.head;
+    if (vertex_len < OT::Lookup::min_size) return false;
+    return vertex_len >= this->get_size ();
+  }
+
+  bool is_extension (hb_tag_t table_tag) const
+  {
+    return lookupType == extension_type (table_tag);
+  }
+
+  bool make_extension (gsubgpos_graph_context_t& c,
+                       unsigned this_index)
+  {
+    unsigned type = lookupType;
+    unsigned ext_type = extension_type (c.table_tag);
+    if (!ext_type || is_extension (c.table_tag))
+    {
+      // NOOP
+      return true;
+    }
+
+    DEBUG_MSG (SUBSET_REPACK, nullptr,
+               "Promoting lookup type %u (obj %u) to extension.",
+               type,
+               this_index);
+
+    for (unsigned i = 0; i < subTable.len; i++)
+    {
+      unsigned subtable_index = c.graph.index_for_offset (this_index, &subTable[i]);
+      if (!make_subtable_extension (c,
+                                    this_index,
+                                    subtable_index))
+        return false;
+    }
+
+    lookupType = ext_type;
+    return true;
+  }
+
+  bool split_subtables_if_needed (gsubgpos_graph_context_t& c,
+                                  unsigned this_index)
+  {
+    unsigned type = lookupType;
+    bool is_ext = is_extension (c.table_tag);
+
+    if (c.table_tag != HB_OT_TAG_GPOS)
+      return true;
+
+    if (!is_ext &&
+        type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::Pair &&
+        type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::MarkBase)
+      return true;
+
+    hb_vector_t<hb_pair_t<unsigned, hb_vector_t<unsigned>>> all_new_subtables;
+    for (unsigned i = 0; i < subTable.len; i++)
+    {
+      unsigned subtable_index = c.graph.index_for_offset (this_index, &subTable[i]);
+      unsigned parent_index = this_index;
+      if (is_ext) {
+        unsigned ext_subtable_index = subtable_index;
+        parent_index = ext_subtable_index;
+        ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>* extension =
+            (ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>*)
+            c.graph.object (ext_subtable_index).head;
+        if (!extension || !extension->sanitize (c.graph.vertices_[ext_subtable_index]))
+          continue;
+
+        subtable_index = extension->get_subtable_index (c.graph, ext_subtable_index);
+        type = extension->get_lookup_type ();
+        if (type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::Pair
+            && type != OT::Layout::GPOS_impl::PosLookupSubTable::Type::MarkBase)
+          continue;
+      }
+
+      hb_vector_t<unsigned> new_sub_tables;
+      switch (type)
+      {
+      case 2:
+        new_sub_tables = split_subtable<PairPos> (c, parent_index, subtable_index); break;
+      case 4:
+        new_sub_tables = split_subtable<MarkBasePos> (c, parent_index, subtable_index); break;
+      default:
+        break;
+      }
+      if (new_sub_tables.in_error ()) return false;
+      if (!new_sub_tables) continue;
+      hb_pair_t<unsigned, hb_vector_t<unsigned>>* entry = all_new_subtables.push ();
+      entry->first = i;
+      entry->second = std::move (new_sub_tables);
+    }
+
+    if (all_new_subtables) {
+      add_sub_tables (c, this_index, type, all_new_subtables);
+    }
+
+    return true;
+  }
+
+  template<typename T>
+  hb_vector_t<unsigned> split_subtable (gsubgpos_graph_context_t& c,
+                                        unsigned parent_idx,
+                                        unsigned objidx)
+  {
+    T* sub_table = (T*) c.graph.object (objidx).head;
+    if (!sub_table || !sub_table->sanitize (c.graph.vertices_[objidx]))
+      return hb_vector_t<unsigned> ();
+
+    return sub_table->split_subtables (c, parent_idx, objidx);
+  }
+
+  void add_sub_tables (gsubgpos_graph_context_t& c,
+                       unsigned this_index,
+                       unsigned type,
+                       hb_vector_t<hb_pair_t<unsigned, hb_vector_t<unsigned>>>& subtable_ids)
+  {
+    bool is_ext = is_extension (c.table_tag);
+    auto& v = c.graph.vertices_[this_index];
+    fix_existing_subtable_links (c, this_index, subtable_ids);
+
+    unsigned new_subtable_count = 0;
+    for (const auto& p : subtable_ids)
+      new_subtable_count += p.second.length;
+
+    size_t new_size = v.table_size ()
+                      + new_subtable_count * OT::Offset16::static_size;
+    char* buffer = (char*) hb_calloc (1, new_size);
+    c.add_buffer (buffer);
+    hb_memcpy (buffer, v.obj.head, v.table_size());
+
+    v.obj.head = buffer;
+    v.obj.tail = buffer + new_size;
+
+    Lookup* new_lookup = (Lookup*) buffer;
+
+    unsigned shift = 0;
+    new_lookup->subTable.len = subTable.len + new_subtable_count;
+    for (const auto& p : subtable_ids)
+    {
+      unsigned offset_index = p.first + shift + 1;
+      shift += p.second.length;
+
+      for (unsigned subtable_id : p.second)
+      {
+        if (is_ext)
+        {
+          unsigned ext_id = create_extension_subtable (c, subtable_id, type);
+          c.graph.vertices_[subtable_id].parents.push (ext_id);
+          subtable_id = ext_id;
+        }
+
+        auto* link = v.obj.real_links.push ();
+        link->width = 2;
+        link->objidx = subtable_id;
+        link->position = (char*) &new_lookup->subTable[offset_index++] -
+                         (char*) new_lookup;
+        c.graph.vertices_[subtable_id].parents.push (this_index);
+      }
+    }
+
+    // Repacker sort order depends on link order, which we've messed up so resort it.
+    v.obj.real_links.qsort ();
+
+    // The head location of the lookup has changed, invalidating the lookups map entry
+    // in the context. Update the map.
+    c.lookups.set (this_index, new_lookup);
+  }
+
+  void fix_existing_subtable_links (gsubgpos_graph_context_t& c,
+                                    unsigned this_index,
+                                    hb_vector_t<hb_pair_t<unsigned, hb_vector_t<unsigned>>>& subtable_ids)
+  {
+    auto& v = c.graph.vertices_[this_index];
+    Lookup* lookup = (Lookup*) v.obj.head;
+
+    unsigned shift = 0;
+    for (const auto& p : subtable_ids)
+    {
+      unsigned insert_index = p.first + shift;
+      unsigned pos_offset = p.second.length * OT::Offset16::static_size;
+      unsigned insert_offset = (char*) &lookup->subTable[insert_index] - (char*) lookup;
+      shift += p.second.length;
+
+      for (auto& l : v.obj.all_links_writer ())
+      {
+        if (l.position > insert_offset) l.position += pos_offset;
+      }
+    }
+  }
+
+  unsigned create_extension_subtable (gsubgpos_graph_context_t& c,
+                                      unsigned subtable_index,
+                                      unsigned type)
+  {
+    unsigned extension_size = OT::ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>::static_size;
+
+    unsigned ext_index = c.create_node (extension_size);
+    if (ext_index == (unsigned) -1)
+      return -1;
+
+    auto& ext_vertex = c.graph.vertices_[ext_index];
+    ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>* extension =
+        (ExtensionFormat1<OT::Layout::GSUB_impl::ExtensionSubst>*) ext_vertex.obj.head;
+    extension->reset (type);
+
+    // Make extension point at the subtable.
+    auto* l = ext_vertex.obj.real_links.push ();
+
+    l->width = 4;
+    l->objidx = subtable_index;
+    l->position = 4;
+
+    return ext_index;
+  }
+
+  bool make_subtable_extension (gsubgpos_graph_context_t& c,
+                                unsigned lookup_index,
+                                unsigned subtable_index)
+  {
+    unsigned type = lookupType;
+
+    unsigned ext_index = create_extension_subtable(c, subtable_index, type);
+    if (ext_index == (unsigned) -1)
+      return false;
+
+    auto& lookup_vertex = c.graph.vertices_[lookup_index];
+    for (auto& l : lookup_vertex.obj.real_links.writer ())
+    {
+      if (l.objidx == subtable_index)
+        // Change lookup to point at the extension.
+        l.objidx = ext_index;
+    }
+
+    // Make extension point at the subtable.
+    auto& ext_vertex = c.graph.vertices_[ext_index];
+    auto& subtable_vertex = c.graph.vertices_[subtable_index];
+    ext_vertex.parents.push (lookup_index);
+    subtable_vertex.remap_parent (lookup_index, ext_index);
+
+    return true;
+  }
+
+ private:
+  unsigned extension_type (hb_tag_t table_tag) const
+  {
+    switch (table_tag)
+    {
+    case HB_OT_TAG_GPOS: return 9;
+    case HB_OT_TAG_GSUB: return 7;
+    default: return 0;
+    }
+  }
+};
+
+template <typename T>
+struct LookupList : public OT::LookupList<T>
+{
+  bool sanitize (const graph_t::vertex_t& vertex) const
+  {
+    int64_t vertex_len = vertex.obj.tail - vertex.obj.head;
+    if (vertex_len < OT::LookupList<T>::min_size) return false;
+    return vertex_len >= OT::LookupList<T>::item_size * this->len;
+  }
+};
+
+struct GSTAR : public OT::GSUBGPOS
+{
+  static GSTAR* graph_to_gstar (graph_t& graph)
+  {
+    const auto& r = graph.root ();
+
+    GSTAR* gstar = (GSTAR*) r.obj.head;
+    if (!gstar || !gstar->sanitize (r))
+      return nullptr;
+
+    return gstar;
+  }
+
+  const void* get_lookup_list_field_offset () const
+  {
+    switch (u.version.major) {
+    case 1: return u.version1.get_lookup_list_offset ();
+#ifndef HB_NO_BEYOND_64K
+    case 2: return u.version2.get_lookup_list_offset ();
+#endif
+    default: return 0;
+    }
+  }
+
+  bool sanitize (const graph_t::vertex_t& vertex)
+  {
+    int64_t len = vertex.obj.tail - vertex.obj.head;
+    if (len < OT::GSUBGPOS::min_size) return false;
+    return len >= get_size ();
+  }
+
+  void find_lookups (graph_t& graph,
+                     hb_hashmap_t<unsigned, Lookup*>& lookups /* OUT */)
+  {
+    switch (u.version.major) {
+      case 1: find_lookups<SmallTypes> (graph, lookups); break;
+#ifndef HB_NO_BEYOND_64K
+      case 2: find_lookups<MediumTypes> (graph, lookups); break;
+#endif
+    }
+  }
+
+  unsigned get_lookup_list_index (graph_t& graph)
+  {
+    return graph.index_for_offset (graph.root_idx (),
+                                   get_lookup_list_field_offset());
+  }
+
+  template<typename Types>
+  void find_lookups (graph_t& graph,
+                     hb_hashmap_t<unsigned, Lookup*>& lookups /* OUT */)
+  {
+    unsigned lookup_list_idx = get_lookup_list_index (graph);
+    const LookupList<Types>* lookupList =
+        (const LookupList<Types>*) graph.object (lookup_list_idx).head;
+    if (!lookupList || !lookupList->sanitize (graph.vertices_[lookup_list_idx]))
+      return;
+
+    for (unsigned i = 0; i < lookupList->len; i++)
+    {
+      unsigned lookup_idx = graph.index_for_offset (lookup_list_idx, &(lookupList->arrayZ[i]));
+      Lookup* lookup = (Lookup*) graph.object (lookup_idx).head;
+      if (!lookup || !lookup->sanitize (graph.vertices_[lookup_idx])) continue;
+      lookups.set (lookup_idx, lookup);
+    }
+  }
+};
+
+
+
+
+}
+
+#endif  /* GRAPH_GSUBGPOS_GRAPH_HH */