Compute the coverage order ahead of time

Store a full matrix for the partial order of
coverage subsets. To avoid this growing too
large, use an indirection to store the information
only once for identical charsets.

On my system, with 4000 fonts, I see ~300 different
charsets. Computing the full matrix takes a while -
~240ms. But we only have to do this once, we do it
in a thread, and we can possibly store it and
load it from disk.

Unlike our other thread use, we won't block for
the coverage, ever. Until it is available, things
are simply slower.

With the coverage order data, we can avoid most
of the expensive charset subset calculations when
trimming fontsets.

This finally gets a font chooser up on the screen
in less a second, on my system (~800ms).

4 files changed, 360 insertions, 9 deletions

diff --git a/pango/meson.build b/pango/meson.build
index 777f5374..79dabe77 100644
--- a/pango/meson.build
+++ b/pango/meson.build
@@ -185,6 +185,7 @@ if build_pangoft2
     'pangofc-font.c',
     'pangofc-fontmap.c',
     'pangofc-decoder.c',
+    'pangofc-coverageorder.c',
     'pango-trace.c',
   ]
 
diff --git a/pango/pangofc-coverageorder-private.h b/pango/pangofc-coverageorder-private.h
new file mode 100644
index 00000000..6537ed06
--- /dev/null
+++ b/pango/pangofc-coverageorder-private.h
@@ -0,0 +1,40 @@
+/* Pango
+ * coverageorder.h:
+ *
+ * Copyright (C) 2020 Red Hat, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Authors: Matthias Clasen
+ */
+
+#ifndef __COVERAGE_ORDER_H__
+#define __COVERAGE_ORDER_H__
+
+#include <glib.h>
+#include <fontconfig/fontconfig.h>
+
+G_BEGIN_DECLS
+
+typedef struct _CoverageOrder CoverageOrder;
+
+CoverageOrder * coverage_order_new       (FcFontSet     *fonts);
+void            coverage_order_free      (CoverageOrder *co);
+gboolean        coverage_order_is_subset (CoverageOrder *co,
+                                          FcPattern     *p1,
+                                          FcPattern     *p2);
+
+G_END_DECLS
+
+#endif /* __COVERAGE_ORDER_H__ */
diff --git a/pango/pangofc-coverageorder.c b/pango/pangofc-coverageorder.c
new file mode 100644
index 00000000..86114b38
--- /dev/null
+++ b/pango/pangofc-coverageorder.c
@@ -0,0 +1,239 @@
+/* Pango
+ * coverageorder.c:
+ *
+ * Copyright (C) 2020 Red Hat, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Authors: Matthias Clasen
+ */
+
+#include "config.h"
+
+#include "pangofc-coverageorder-private.h"
+#include <glib.h>
+
+/* BitMatrix is a simple matrix of bits that can be
+ * addressed by their row and column.
+ */
+typedef struct _BitMatrix BitMatrix;
+
+struct _BitMatrix
+{
+  int rows;
+  int cols;
+  char *bits;
+};
+
+static void
+bit_matrix_free (BitMatrix *b)
+{
+  g_free (b->bits);
+  g_free (b);
+}
+
+static BitMatrix *
+bit_matrix_new (int rows, int cols)
+{
+  BitMatrix *b = g_new (BitMatrix, 1);
+
+  b->rows = rows;
+  b->cols = cols;
+  b->bits = g_new0 (char, (rows * cols) / 8 + 1);
+
+  return b;
+}
+
+static gboolean
+bit_matrix_get (BitMatrix *b, int i, int j)
+{
+  int pos = i * b->cols + j;
+  int byte = pos / 8;
+  int bit = pos % 8;
+
+  return (b->bits[byte] & (1 << bit)) != 0;
+}
+
+static void
+bit_matrix_set (BitMatrix *b, int i, int j, gboolean value)
+{
+  int pos = i * b->cols + j;
+  int byte = pos / 8;
+  int bit = pos % 8;
+
+  if (value)
+    b->bits[byte] = b->bits[byte] | (1 << bit);
+  else
+    b->bits[byte] = b->bits[byte] & ~(1 << bit);
+}
+
+/* By coverage order, we mean the partial order that is defined on
+ * the fonts by the subset relation on their charsets. This order
+ * only depends on the font configuration, and can be computed
+ * ahead of time or even saved to disk.
+ *
+ * An important aspect of why this works is that in practice,
+ * many fonts have the same coverage, so our matrix stays much
+ * smaller than |fonts| * |fonts|.
+ */
+
+struct _CoverageOrder
+{
+  GHashTable *idx;
+  BitMatrix *order;
+};
+
+/*
+ * coverage_order_free:
+ *
+ * Frees a CoverageOrder struct and all associated memory.
+ */
+void
+coverage_order_free (CoverageOrder *co)
+{
+  g_hash_table_unref (co->idx);
+  bit_matrix_free (co->order);
+  g_free (co);
+}
+
+/*
+ * coverage_order_is_subset:
+ * @co: a #CoverageOrder
+ * @p1: a pattern
+ * @p2: another pattern
+ *
+ * Determines if the charset of @p1 is a subset
+ * of the charset of @p2.
+ *
+ * Returns: %TRUE if @p1 is a subset of @p2
+ */
+gboolean
+coverage_order_is_subset (CoverageOrder *co,
+                          FcPattern     *p1,
+                          FcPattern     *p2)
+{
+  int idx1, idx2;
+
+  idx1 = GPOINTER_TO_INT (g_hash_table_lookup (co->idx, p1)) - 1;
+  idx2 = GPOINTER_TO_INT (g_hash_table_lookup (co->idx, p2)) - 1;
+
+  return bit_matrix_get (co->order, idx1, idx2);
+}
+
+/*
+ * coverage_order_new:
+ * @fonts: a set of fonts
+ *
+ * Compute the coverage order for the fonts in @fonts.
+ *
+ * Returns: a new #CoverageOrder
+ */
+CoverageOrder *
+coverage_order_new (FcFontSet *fonts)
+{
+  CoverageOrder *co;
+  int *idx;
+  GPtrArray *coverages;
+  int max, i, j;
+
+  co = g_new (CoverageOrder, 1);
+
+  co->idx = g_hash_table_new (g_direct_hash, g_direct_equal);
+
+  idx = g_new (int, fonts->nfont);
+  coverages = g_ptr_array_new ();
+
+  /* First group the fonts that have the same
+   * charset, by giving them the same 'index'.
+   */
+  max = -1;
+  for (i = 0; i < fonts->nfont; i++)
+    {
+      FcPattern *p1 = fonts->fonts[i];
+      FcCharSet *c1;
+
+      FcPatternGetCharSet (p1, "charset", 0, &c1);
+      idx[i] = max + 1;
+      for (j = 0; j < i; j++)
+        {
+          FcPattern *p2 = fonts->fonts[j];
+          FcCharSet *c2;
+
+          FcPatternGetCharSet (p2, "charset", 0, &c2);
+
+          if (FcCharSetEqual (c1, c2))
+            {
+              idx[i] = idx[j];
+              break;
+            }
+        }
+
+      g_hash_table_insert (co->idx, p1, GINT_TO_POINTER (idx[i] + 1));
+      if (idx[i] > max)
+        {
+          g_ptr_array_add (coverages, c1);
+          max = idx[i];
+        }
+    }
+
+  /* Now compute the full incidence matrix for the
+   * remaining charsets.
+   */
+  co->order = bit_matrix_new (coverages->len, coverages->len);
+
+  for (i = 0; i < coverages->len; i++)
+    {
+      FcCharSet *ci = g_ptr_array_index (coverages, i);
+      bit_matrix_set (co->order, i, i, TRUE);
+      for (j = 0; j < i; j++)
+        {
+          FcCharSet *cj = g_ptr_array_index (coverages, j);
+          gboolean v;
+          int k;
+
+          v = FALSE;
+          for (k = 0; k < coverages->len; k++)
+            {
+              if (bit_matrix_get (co->order, j, k) &&
+                  bit_matrix_get (co->order, k, i))
+                {
+                  v = TRUE;
+                  break;
+                }
+            }
+
+          if (v || FcCharSetIsSubset (cj, ci))
+            bit_matrix_set (co->order, j, i, TRUE);
+
+          v = FALSE;
+          for (k = 0; k < coverages->len; k++)
+            {
+              if (bit_matrix_get (co->order, i, k) &&
+                  bit_matrix_get (co->order, k, j))
+                {
+                  v = TRUE;
+                  break;
+                }
+            }
+
+          if (v || FcCharSetIsSubset (ci, cj))
+            bit_matrix_set (co->order, i, j, TRUE);
+        }
+    }
+
+  g_ptr_array_unref (coverages);
+  g_free (idx);
+
+  return co;
+}
diff --git a/pango/pangofc-fontmap.c b/pango/pangofc-fontmap.c
index d859c493..a2aefcf3 100644
--- a/pango/pangofc-fontmap.c
+++ b/pango/pangofc-fontmap.c
@@ -55,6 +55,7 @@
 #include "pango-enum-types.h"
 #include "pango-coverage-private.h"
 #include "pango-trace-private.h"
+#include "pangofc-coverageorder-private.h"
 #include <hb-ft.h>
 
 
@@ -167,6 +168,9 @@ struct _PangoFcFontMapPrivate
 
   FcConfig *config;
   FcFontSet *fonts;
+
+  CoverageOrder *coverage_order;
+  GCancellable *coverage_cancellable;
 };
 
 struct _PangoFcFontFaceData
@@ -1077,10 +1081,7 @@ pango_fc_patterns_get_font_pattern (PangoFcPatterns *pats, int i, gboolean *prep
     {
       int f, k;
 
-      /* Find the i'th fontset skipping the ones that are
-       * not adding coverage.
-       */
-
+      /* Find the i'th fontset while doing coverage trimming. */
       if (!pats->skip)
         {
           pats->skip = g_new0 (char, fontset->nfont);
@@ -1091,14 +1092,33 @@ pango_fc_patterns_get_font_pattern (PangoFcPatterns *pats, int i, gboolean *prep
         {
           if (pats->skip[f] == 0) /* calculate whether to skip */
             {
-              FcCharSet *fcs;
-              FcBool added = FcFalse;
+              int l;
 
-              FcPatternGetCharSet (fontset->fonts[f], "charset", 0, &fcs);
+              if (pats->fontmap->priv->coverage_order)
+                {
+                  for (l = 0; l < f; l++) /* see if a previous font covers it */
+                    {
+                      if (coverage_order_is_subset (pats->fontmap->priv->coverage_order,
+                                                    fontset->fonts[f],
+                                                    fontset->fonts[l]))
+                        {
+                          pats->skip[f] = 1;
+                          break;
+                        }
+                    }
+                }
+
+              if (pats->skip[f] == 0) /* have to do it the hard way */
+                {
+                  FcCharSet *fcs;
+                  FcBool added = FcFalse;
 
-              FcCharSetMerge (pats->cs, fcs, &added);
+                  FcPatternGetCharSet (fontset->fonts[f], "charset", 0, &fcs);
 
-              pats->skip[f] = added ? 2 : 1;
+                  FcCharSetMerge (pats->cs, fcs, &added);
+
+                  pats->skip[f] = added ? 2 : 1;
+                }
             }
 
           if (pats->skip[f] == 2) /* don't skip */
@@ -1469,6 +1489,12 @@ pango_fc_font_map_fini (PangoFcFontMap *fcfontmap)
   PangoFcFontMapPrivate *priv = fcfontmap->priv;
   int i;
 
+  if (priv->coverage_cancellable)
+    {
+      g_cancellable_cancel (priv->coverage_cancellable);
+      g_clear_object (&priv->coverage_cancellable);
+    }
+  g_clear_pointer (&priv->coverage_order, coverage_order_free);
   g_clear_pointer (&priv->fonts, FcFontSetDestroy);
 
   g_queue_free (priv->fontset_cache);
@@ -2346,6 +2372,7 @@ pango_fc_font_map_set_config (PangoFcFontMap *fcfontmap,
 
   fcfontmap->priv->config = fcconfig;
 
+  g_clear_pointer (&fcfontmap->priv->coverage_order, coverage_order_free);
   g_clear_pointer (&fcfontmap->priv->fonts, FcFontSetDestroy);
 
   if (oldconfig != fcconfig)
@@ -2381,11 +2408,39 @@ pango_fc_font_map_get_config (PangoFcFontMap *fcfontmap)
   return fcfontmap->priv->config;
 }
 
+static void
+compute_coverage_order_in_thread (GTask        *task,
+                                  gpointer      source_object,
+                                  gpointer      task_data,
+                                  GCancellable *cancellable)
+{
+  FcFontSet *fonts = task_data;
+  CoverageOrder *coverage_order;
+  gint64 before = PANGO_TRACE_CURRENT_TIME;
+
+  coverage_order = coverage_order_new (fonts);
+
+  pango_trace_mark (before, "compute_coverage_order", NULL);
+
+  g_task_return_pointer (task, coverage_order, (GDestroyNotify)coverage_order_free);
+}
+
+static void
+coverage_computed (GObject      *source_object,
+                   GAsyncResult *result,
+                   gpointer      data)
+{
+  PangoFcFontMap *fcfontmap = PANGO_FC_FONT_MAP (source_object);
+
+  fcfontmap->priv->coverage_order = g_task_propagate_pointer (G_TASK (result), NULL);
+}
+
 static FcFontSet *
 pango_fc_font_map_get_config_fonts (PangoFcFontMap *fcfontmap)
 {
   if (fcfontmap->priv->fonts == NULL)
     {
+      GTask *task;
       FcFontSet *sets[2];
 
       wait_for_fc_init ();
@@ -2393,6 +2448,22 @@ pango_fc_font_map_get_config_fonts (PangoFcFontMap *fcfontmap)
       sets[0] = FcConfigGetFonts (fcfontmap->priv->config, 0);
       sets[1] = FcConfigGetFonts (fcfontmap->priv->config, 1);
       fcfontmap->priv->fonts = filter_by_format (sets, 2);
+
+      g_clear_pointer (&fcfontmap->priv->coverage_order, coverage_order_free);
+
+      if (fcfontmap->priv->coverage_cancellable)
+        {
+          g_cancellable_cancel (fcfontmap->priv->coverage_cancellable);
+          g_clear_object (&fcfontmap->priv->coverage_cancellable);
+        }
+
+      fcfontmap->priv->coverage_cancellable = g_cancellable_new ();
+
+      task = g_task_new (fcfontmap, fcfontmap->priv->coverage_cancellable, coverage_computed, NULL);
+      g_task_set_name (task, "[pango] compute_coverage_order");
+      g_task_set_task_data (task, font_set_copy (fcfontmap->priv->fonts), (GDestroyNotify)FcFontSetDestroy);
+      g_task_run_in_thread (task, compute_coverage_order_in_thread);
+      g_object_unref (task);
     }
 
   return fcfontmap->priv->fonts;