[gtk/wip/otte/css: 2/2] css: Use the bloom filter for change matching

[Benjamin Otte <otte src gnome org>]

commit d488f68a25f2619d6426aa56f1aac64182706bf4
Author: Benjamin Otte <otte redhat com>
Date:   Mon Jan 27 03:26:39 2020 +0100

    css: Use the bloom filter for change matching
    
    Instead of just doing radical change matching on the node itself, also
    consider the parent nodes via the bloom filter.
    
    This means a radical change is now also one where the parent
    name/id/classes change, but since that's considered a radical change on
    the parent already, those things are slow anyway.
    
    Improves the benchmark times for CSS validation during backdrop
    transitions in widget-factory from 45ms to 35ms on my machine.

 gtk/gtkcssnode.c                 |  4 +-
 gtk/gtkcssprovider.c             |  2 +-
 gtk/gtkcssselector.c             | 90 ++++++++++++++++++++--------------------
 gtk/gtkcssselectorprivate.h      |  3 +-
 testsuite/css/change/test5.nodes |  4 +-
 5 files changed, 53 insertions(+), 50 deletions(-)
---
diff --git a/gtk/gtkcssnode.c b/gtk/gtkcssnode.c
index b88e9f4fa3..ab52c2bcd3 100644
--- a/gtk/gtkcssnode.c
+++ b/gtk/gtkcssnode.c
@@ -87,7 +87,9 @@
 
 /* When these change we do a full restyling. Otherwise we try to figure out
  * if we need to change things. */
-#define GTK_CSS_RADICAL_CHANGE (GTK_CSS_CHANGE_ID | GTK_CSS_CHANGE_NAME | GTK_CSS_CHANGE_CLASS | 
GTK_CSS_CHANGE_SOURCE | GTK_CSS_CHANGE_PARENT_STYLE)
+#define GTK_CSS_RADICAL_CHANGE (GTK_CSS_CHANGE_ID | GTK_CSS_CHANGE_NAME | GTK_CSS_CHANGE_CLASS | \
+                                GTK_CSS_CHANGE_PARENT_ID | GTK_CSS_CHANGE_PARENT_NAME | 
GTK_CSS_CHANGE_PARENT_CLASS | \
+                                GTK_CSS_CHANGE_SOURCE | GTK_CSS_CHANGE_PARENT_STYLE)
 
 /* When these change, we need to recompute the change flags for the new style
  * since they may have changed.
diff --git a/gtk/gtkcssprovider.c b/gtk/gtkcssprovider.c
index bf109506c4..2cd6347811 100644
--- a/gtk/gtkcssprovider.c
+++ b/gtk/gtkcssprovider.c
@@ -496,7 +496,7 @@ gtk_css_style_provider_lookup (GtkStyleProvider             *provider,
     }
 
   if (change)
-    *change = _gtk_css_selector_tree_get_change_all (priv->tree, node);
+    *change = gtk_css_selector_tree_get_change_all (priv->tree, filter, node);
 }
 
 static void
diff --git a/gtk/gtkcssselector.c b/gtk/gtkcssselector.c
index 8f4bbf0113..dfb002e32b 100644
--- a/gtk/gtkcssselector.c
+++ b/gtk/gtkcssselector.c
@@ -1957,21 +1957,6 @@ _gtk_css_selector_tree_match_all (const GtkCssSelectorTree     *tree,
   return tm.results;
 }
 
-/* The code for collecting matches assumes that the name, id and classes
- * of a node remain unchanged, and anything else can change. This needs to
- * be kept in sync with the definition of 'radical change' in gtkcssnode.c.
- */
-
-static gboolean
-gtk_css_selector_match_for_change (const GtkCssSelector *selector,
-                                   GtkCssNode           *node)
-{
-  if (selector->class->category != GTK_CSS_SELECTOR_CATEGORY_SIMPLE_RADICAL)
-    return TRUE;
-
-  return selector->class->match_one (selector, node);
-}
-
 /* When checking for changes via the tree we need to know if a rule further
    down the tree matched, because if so we need to add "our bit" to the
    Change. For instance in a match like *.class:active we'll
@@ -1983,39 +1968,56 @@ gtk_css_selector_match_for_change (const GtkCssSelector *selector,
    that change != 0 on any match. */
 #define GTK_CSS_CHANGE_GOT_MATCH GTK_CSS_CHANGE_RESERVED_BIT
 
-static GtkCssChange
-gtk_css_selector_tree_collect_change (const GtkCssSelectorTree *tree)
-{
-  GtkCssChange change = 0;
-  const GtkCssSelectorTree *prev;
-
-  for (prev = gtk_css_selector_tree_get_previous (tree);
-       prev != NULL;
-       prev = gtk_css_selector_tree_get_sibling (prev))
-    change |= gtk_css_selector_tree_collect_change (prev);
-
-  change = tree->selector.class->get_change (&tree->selector, change);
-
-  return change;
-}
+/* The code for collecting matches assumes that the name, id and classes
+ * of a node remain unchanged, and anything else can change. This needs to
+ * be kept in sync with the definition of 'radical change' in gtkcssnode.c.
+ */
 
 static GtkCssChange
-gtk_css_selector_tree_get_change (const GtkCssSelectorTree *tree,
-                                 GtkCssNode               *node)
+gtk_css_selector_tree_get_change (const GtkCssSelectorTree     *tree,
+                                  const GtkCountingBloomFilter *filter,
+                                 GtkCssNode                   *node,
+                                  gboolean                      skipping)
 {
   GtkCssChange change = 0;
   const GtkCssSelectorTree *prev;
 
-  if (!gtk_css_selector_match_for_change (&tree->selector, node))
-    return 0;
-
-  if (!gtk_css_selector_is_simple (&tree->selector))
-    return gtk_css_selector_tree_collect_change (tree) | GTK_CSS_CHANGE_GOT_MATCH;
+  switch (tree->selector.class->category)
+    {
+      case GTK_CSS_SELECTOR_CATEGORY_SIMPLE:
+        break;
+      case GTK_CSS_SELECTOR_CATEGORY_SIMPLE_RADICAL:
+        if (skipping)
+          break;
+        if (node)
+          {
+            if (!tree->selector.class->match_one (&tree->selector, node))
+              return 0;
+          }
+        else if (filter)
+          {
+            if (!gtk_counting_bloom_filter_may_contain (filter,
+                                                        gtk_css_selector_hash_one (&tree->selector)))
+              return 0;
+          }
+        break;
+      case GTK_CSS_SELECTOR_CATEGORY_PARENT:
+        skipping = FALSE;
+        node = NULL;
+        break;
+      case GTK_CSS_SELECTOR_CATEGORY_SIBLING:
+        skipping = TRUE;
+        node = NULL;
+        break;
+      default:
+        g_assert_not_reached ();
+        return 0;
+    }
 
   for (prev = gtk_css_selector_tree_get_previous (tree);
        prev != NULL;
        prev = gtk_css_selector_tree_get_sibling (prev))
-    change |= gtk_css_selector_tree_get_change (prev, node);
+    change |= gtk_css_selector_tree_get_change (prev, filter, node, skipping);
 
   if (change || gtk_css_selector_tree_get_matches (tree))
     change = tree->selector.class->get_change (&tree->selector, change & ~GTK_CSS_CHANGE_GOT_MATCH) | 
GTK_CSS_CHANGE_GOT_MATCH;
@@ -2030,17 +2032,15 @@ _gtk_css_selector_tree_is_empty (const GtkCssSelectorTree *tree)
 }
 
 GtkCssChange
-_gtk_css_selector_tree_get_change_all (const GtkCssSelectorTree *tree,
-                                      GtkCssNode               *node)
+gtk_css_selector_tree_get_change_all (const GtkCssSelectorTree     *tree,
+                                      const GtkCountingBloomFilter *filter,
+                                     GtkCssNode                   *node)
 {
-  GtkCssChange change;
-
-  change = 0;
+  GtkCssChange change = 0;
 
-  /* no need to foreach here because we abort for non-simple selectors */
   for (; tree != NULL;
        tree = gtk_css_selector_tree_get_sibling (tree))
-    change |= gtk_css_selector_tree_get_change (tree, node);
+    change |= gtk_css_selector_tree_get_change (tree, filter, node, FALSE);
 
   /* Never return reserved bit set */
   return change & ~GTK_CSS_CHANGE_RESERVED_BIT;
diff --git a/gtk/gtkcssselectorprivate.h b/gtk/gtkcssselectorprivate.h
index a1e265d5d2..4d8e39f376 100644
--- a/gtk/gtkcssselectorprivate.h
+++ b/gtk/gtkcssselectorprivate.h
@@ -45,7 +45,8 @@ void         _gtk_css_selector_tree_free             (GtkCssSelectorTree       *
 GPtrArray *  _gtk_css_selector_tree_match_all        (const GtkCssSelectorTree *tree,
                                                       const GtkCountingBloomFilter *filter,
                                                      GtkCssNode               *node);
-GtkCssChange _gtk_css_selector_tree_get_change_all   (const GtkCssSelectorTree *tree,
+GtkCssChange gtk_css_selector_tree_get_change_all    (const GtkCssSelectorTree *tree,
+                                                      const GtkCountingBloomFilter *filter,
                                                      GtkCssNode               *node);
 void         _gtk_css_selector_tree_match_print      (const GtkCssSelectorTree *tree,
                                                      GString                  *str);
diff --git a/testsuite/css/change/test5.nodes b/testsuite/css/change/test5.nodes
index dbcbd2adf8..f9b7c8e94d 100644
--- a/testsuite/css/change/test5.nodes
+++ b/testsuite/css/change/test5.nodes
@@ -1,9 +1,9 @@
 window.background:dir(ltr)    
   decoration:dir(ltr)    
   grid.horizontal:dir(ltr)    
-    label:dir(ltr)    name|sibling-name|parent-name|parent-sibling-name
+    label:dir(ltr)    
     box.horizontal:dir(ltr)    
-    label:dir(ltr)    name|sibling-name|parent-name|parent-sibling-name
+    label:dir(ltr)    
     button:dir(ltr)    
       box.horizontal:dir(ltr)    
         checkbutton:dir(ltr)