1 files changed, 203 insertions, 17 deletions

diff --git a/thirdparty/harfbuzz/src/graph/graph.hh b/thirdparty/harfbuzz/src/graph/graph.hh
index 52ca9dd142..b3aef558a2 100644
--- a/thirdparty/harfbuzz/src/graph/graph.hh
+++ b/thirdparty/harfbuzz/src/graph/graph.hh
@@ -24,6 +24,10 @@
  * Google Author(s): Garret Rieger
  */
 
+#include "../hb-set.hh"
+#include "../hb-priority-queue.hh"
+#include "../hb-serialize.hh"
+
 #ifndef GRAPH_GRAPH_HH
 #define GRAPH_GRAPH_HH
 
@@ -76,6 +80,22 @@ struct graph_t
       }
     }
 
+    void remove_real_link (unsigned child_index, const void* offset)
+    {
+      for (unsigned i = 0; i < obj.real_links.length; i++)
+      {
+        auto& link = obj.real_links[i];
+        if (link.objidx != child_index)
+          continue;
+
+        if ((obj.head + link.position) != offset)
+          continue;
+
+        obj.real_links.remove (i);
+        return;
+      }
+    }
+
     void remap_parents (const hb_vector_t<unsigned>& id_map)
     {
       for (unsigned i = 0; i < parents.length; i++)
@@ -107,6 +127,10 @@ struct graph_t
       return priority >= 3;
     }
 
+    size_t table_size () const {
+      return obj.tail - obj.head;
+    }
+
     int64_t modified_distance (unsigned order) const
     {
       // TODO(garretrieger): once priority is high enough, should try
@@ -199,13 +223,24 @@ struct graph_t
     return vertices_.length - 1;
   }
 
-  const hb_serialize_context_t::object_t& object(unsigned i) const
+  const hb_serialize_context_t::object_t& object (unsigned i) const
   {
     return vertices_[i].obj;
   }
 
   /*
    * Generates a new topological sorting of graph ordered by the shortest
+   * distance to each node if positions are marked as invalid.
+   */
+  void sort_shortest_distance_if_needed ()
+  {
+    if (!positions_invalid) return;
+    sort_shortest_distance ();
+  }
+
+
+  /*
+   * Generates a new topological sorting of graph ordered by the shortest
    * distance to each node.
    */
   void sort_shortest_distance ()
@@ -256,37 +291,91 @@ struct graph_t
 
     check_success (!queue.in_error ());
     check_success (!sorted_graph.in_error ());
-    if (!check_success (new_id == -1))
-      print_orphaned_nodes ();
 
     remap_all_obj_indices (id_map, &sorted_graph);
-
     hb_swap (vertices_, sorted_graph);
+
+    if (!check_success (new_id == -1))
+      print_orphaned_nodes ();
   }
 
   /*
-   * Assign unique space numbers to each connected subgraph of 32 bit offset(s).
+   * Finds the set of nodes (placed into roots) that should be assigned unique spaces.
+   * More specifically this looks for the top most 24 bit or 32 bit links in the graph.
+   * Some special casing is done that is specific to the layout of GSUB/GPOS tables.
    */
-  bool assign_32bit_spaces ()
+  void find_space_roots (hb_set_t& visited, hb_set_t& roots)
   {
-    unsigned root_index = root_idx ();
-    hb_set_t visited;
-    hb_set_t roots;
-    for (unsigned i = 0; i <= root_index; i++)
+    int root_index = (int) root_idx ();
+    for (int i = root_index; i >= 0; i--)
     {
+      if (visited.has (i)) continue;
+
       // Only real links can form 32 bit spaces
       for (auto& l : vertices_[i].obj.real_links)
       {
-        if (l.width == 4 && !l.is_signed)
+        if (l.is_signed || l.width < 3)
+          continue;
+
+        if (i == root_index && l.width == 3)
+          // Ignore 24bit links from the root node, this skips past the single 24bit
+          // pointer to the lookup list.
+          continue;
+
+        if (l.width == 3)
         {
-          roots.add (l.objidx);
-          find_subgraph (l.objidx, visited);
+          // A 24bit offset forms a root, unless there is 32bit offsets somewhere
+          // in it's subgraph, then those become the roots instead. This is to make sure
+          // that extension subtables beneath a 24bit lookup become the spaces instead
+          // of the offset to the lookup.
+          hb_set_t sub_roots;
+          find_32bit_roots (l.objidx, sub_roots);
+          if (sub_roots) {
+            for (unsigned sub_root_idx : sub_roots) {
+              roots.add (sub_root_idx);
+              find_subgraph (sub_root_idx, visited);
+            }
+            continue;
+          }
         }
+
+        roots.add (l.objidx);
+        find_subgraph (l.objidx, visited);
       }
     }
+  }
+
+  unsigned index_for_offset(unsigned node_idx, const void* offset) const
+  {
+    const auto& node = object (node_idx);
+    if (offset < node.head || offset >= node.tail) return -1;
+
+    for (const auto& link : node.real_links)
+    {
+      if (offset != node.head + link.position)
+        continue;
+      return link.objidx;
+    }
+
+    return -1;
+  }
 
-    // Mark everything not in the subgraphs of 32 bit roots as visited.
-    // This prevents 32 bit subgraphs from being connected via nodes not in the 32 bit subgraphs.
+
+  /*
+   * Assign unique space numbers to each connected subgraph of 24 bit and/or 32 bit offset(s).
+   * Currently, this is implemented specifically tailored to the structure of a GPOS/GSUB
+   * (including with 24bit offsets) table.
+   */
+  bool assign_spaces ()
+  {
+    update_parents ();
+
+    hb_set_t visited;
+    hb_set_t roots;
+    find_space_roots (visited, roots);
+
+    // Mark everything not in the subgraphs of the roots as visited. This prevents
+    // subgraphs from being connected via nodes not in those subgraphs.
     visited.invert ();
 
     if (!roots) return false;
@@ -422,6 +511,68 @@ struct graph_t
       find_subgraph (link.objidx, subgraph);
   }
 
+  size_t find_subgraph_size (unsigned node_idx, hb_set_t& subgraph, unsigned max_depth = -1)
+  {
+    if (subgraph.has (node_idx)) return 0;
+    subgraph.add (node_idx);
+
+    const auto& o = vertices_[node_idx].obj;
+    size_t size = o.tail - o.head;
+    if (max_depth == 0)
+      return size;
+
+    for (const auto& link : o.all_links ())
+      size += find_subgraph_size (link.objidx, subgraph, max_depth - 1);
+    return size;
+  }
+
+  /*
+   * Finds the topmost children of 32bit offsets in the subgraph starting
+   * at node_idx. Found indices are placed into 'found'.
+   */
+  void find_32bit_roots (unsigned node_idx, hb_set_t& found)
+  {
+    for (const auto& link : vertices_[node_idx].obj.all_links ())
+    {
+      if (!link.is_signed && link.width == 4) {
+        found.add (link.objidx);
+        continue;
+      }
+      find_32bit_roots (link.objidx, found);
+    }
+  }
+
+  /*
+   * Moves the child of old_parent_idx pointed to by old_offset to a new
+   * vertex at the new_offset.
+   */
+  template<typename O>
+  void move_child (unsigned old_parent_idx,
+                   const O* old_offset,
+                   unsigned new_parent_idx,
+                   const O* new_offset)
+  {
+    distance_invalid = true;
+    positions_invalid = true;
+
+    auto& old_v = vertices_[old_parent_idx];
+    auto& new_v = vertices_[new_parent_idx];
+
+    unsigned child_id = index_for_offset (old_parent_idx,
+                                          old_offset);
+
+    auto* new_link = new_v.obj.real_links.push ();
+    new_link->width = O::static_size;
+    new_link->objidx = child_id;
+    new_link->position = (const char*) new_offset - (const char*) new_v.obj.head;
+
+    auto& child = vertices_[child_id];
+    child.parents.push (new_parent_idx);
+
+    old_v.remove_real_link (child_id, old_offset);
+    child.remove_parent (old_parent_idx);
+  }
+
   /*
    * duplicates all nodes in the subgraph reachable from node_idx. Does not re-assign
    * links. index_map is updated with mappings from old id to new id. If a duplication has already
@@ -529,6 +680,39 @@ struct graph_t
     return true;
   }
 
+
+  /*
+   * Adds a new node to the graph, not connected to anything.
+   */
+  unsigned new_node (char* head, char* tail)
+  {
+    positions_invalid = true;
+    distance_invalid = true;
+
+    auto* clone = vertices_.push ();
+    if (vertices_.in_error ()) {
+      return -1;
+    }
+
+    clone->obj.head = head;
+    clone->obj.tail = tail;
+    clone->distance = 0;
+    clone->space = 0;
+
+    unsigned clone_idx = vertices_.length - 2;
+
+    // The last object is the root of the graph, so swap back the root to the end.
+    // The root's obj idx does change, however since it's root nothing else refers to it.
+    // all other obj idx's will be unaffected.
+    hb_swap (vertices_[vertices_.length - 2], *clone);
+
+    // Since the root moved, update the parents arrays of all children on the root.
+    for (const auto& l : root ().obj.all_links ())
+      vertices_[l.objidx].remap_parent (root_idx () - 1, root_idx ());
+
+    return clone_idx;
+  }
+
   /*
    * Raises the sorting priority of all children.
    */
@@ -622,7 +806,7 @@ struct graph_t
  private:
 
   /*
-   * Returns the numbers of incoming edges that are 32bits wide.
+   * Returns the numbers of incoming edges that are 24 or 32 bits wide.
    */
   unsigned wide_parents (unsigned node_idx, hb_set_t& parents) const
   {
@@ -636,7 +820,9 @@ struct graph_t
       // Only real links can be wide
       for (const auto& l : vertices_[p].obj.real_links)
       {
-        if (l.objidx == node_idx && l.width == 4 && !l.is_signed)
+        if (l.objidx == node_idx
+            && (l.width == 3 || l.width == 4)
+            && !l.is_signed)
         {
           count++;
           parents.add (p);