Update Harfbuzz to 8.4.0

Pick-to: 5.15 6.2 6.5 6.7 6.7.1
Fixes: QTBUG-124757
Change-Id: I1fa9259c2f7cb45b4dcec8956c2186735c89fb95
Reviewed-by: Volker Hilsheimer <volker.hilsheimer@qt.io>

1 files changed, 50 insertions, 2 deletions

diff --git a/src/3rdparty/harfbuzz-ng/src/hb-repacker.hh b/src/3rdparty/harfbuzz-ng/src/hb-repacker.hh
index e9cd376ad3..ed40f271cc 100644
--- a/src/3rdparty/harfbuzz-ng/src/hb-repacker.hh
+++ b/src/3rdparty/harfbuzz-ng/src/hb-repacker.hh
@@ -239,6 +239,54 @@ bool _try_isolating_subgraphs (const hb_vector_t<graph::overflow_record_t>& over
 }
 
 static inline
+bool _resolve_shared_overflow(const hb_vector_t<graph::overflow_record_t>& overflows,
+                              int overflow_index,
+                              graph_t& sorted_graph)
+{
+  const graph::overflow_record_t& r = overflows[overflow_index];
+
+  // Find all of the parents in overflowing links that link to this
+  // same child node. We will then try duplicating the child node and
+  // re-assigning all of these parents to the duplicate.
+  hb_set_t parents;
+  parents.add(r.parent);
+  for (int i = overflow_index - 1; i >= 0; i--) {
+    const graph::overflow_record_t& r2 = overflows[i];
+    if (r2.child == r.child) {
+      parents.add(r2.parent);
+    }
+  }
+
+  unsigned result = sorted_graph.duplicate(&parents, r.child);
+  if (result == (unsigned) -1 && parents.get_population() > 2) {
+    // All links to the child are overflowing, so we can't include all
+    // in the duplication. Remove one parent from the duplication.
+    // Remove the lowest index parent, which will be the closest to the child.
+    parents.del(parents.get_min());
+    result = sorted_graph.duplicate(&parents, r.child);
+  }
+
+  if (result == (unsigned) -1) return result;
+
+  if (parents.get_population() > 1) {
+    // If the duplicated node has more than one parent pre-emptively raise it's priority to the maximum.
+    // This will place it close to the parents. Node's with only one parent, don't need this as normal overflow
+    // resolution will raise priority if needed.
+    //
+    // Reasoning: most of the parents to this child are likely at the same layer in the graph. Duplicating
+    // the child will theoretically allow it to be placed closer to it's parents. However, due to the shortest
+    // distance sort by default it's placement will remain in the same layer, thus it will remain in roughly the
+    // same position (and distance from parents) as the original child node. The overflow resolution will attempt
+    // to move nodes closer, but only for non-shared nodes. Since this node is shared, it will simply be given
+    // further duplication which defeats the attempt to duplicate with multiple parents. To fix this we
+    // pre-emptively raise priority now which allows the duplicated node to pack into the same layer as it's parents.
+    sorted_graph.vertices_[result].give_max_priority();
+  }
+
+  return result;
+}
+
+static inline
 bool _process_overflows (const hb_vector_t<graph::overflow_record_t>& overflows,
                          hb_set_t& priority_bumped_parents,
                          graph_t& sorted_graph)
@@ -254,7 +302,7 @@ bool _process_overflows (const hb_vector_t<graph::overflow_record_t>& overflows,
     {
       // The child object is shared, we may be able to eliminate the overflow
       // by duplicating it.
-      if (sorted_graph.duplicate (r.parent, r.child) == (unsigned) -1) continue;
+      if (!_resolve_shared_overflow(overflows, i, sorted_graph)) continue;
       return true;
     }
 
@@ -388,7 +436,7 @@ template<typename T>
 inline hb_blob_t*
 hb_resolve_overflows (const T& packed,
                       hb_tag_t table_tag,
-                      unsigned max_rounds = 20,
+                      unsigned max_rounds = 32,
                       bool recalculate_extensions = false) {
   graph_t sorted_graph (packed);
   if (sorted_graph.in_error ())