[gtk/wip/otte/css: 4/5] cssselector: Rework how we handle the bloom filter

[Benjamin Otte <otte src gnome org>]

commit a8ceec15acdb400f6e2179ee4f02a8821f119719
Author: Benjamin Otte <otte redhat com>
Date:   Wed Jan 29 02:11:06 2020 +0100

    cssselector: Rework how we handle the bloom filter
    
    Instead of foreaching through all the previous selectors every time we
    bloom-filter, just bloom-filter the current element and return a special
    value if that filter fails (FALSE). If that happens, don't try
    filter-matching more nodes in the caller as we know it's an abort.

 gtk/gtkcssselector.c | 84 ++++++++++++----------------------------------------
 1 file changed, 19 insertions(+), 65 deletions(-)
---
diff --git a/gtk/gtkcssselector.c b/gtk/gtkcssselector.c
index 0745bc26e3..129c37b9c3 100644
--- a/gtk/gtkcssselector.c
+++ b/gtk/gtkcssselector.c
@@ -1835,7 +1835,7 @@ static GtkCssChange
 gtk_css_selector_tree_get_change (const GtkCssSelectorTree     *tree,
                                   const GtkCountingBloomFilter *filter,
                                  GtkCssNode                   *node,
-                                  gboolean                      in_sibling)
+                                  gboolean                      match_filter)
 {
   GtkCssChange change = 0;
   const GtkCssSelectorTree *prev;
@@ -1845,14 +1845,12 @@ gtk_css_selector_tree_get_change (const GtkCssSelectorTree     *tree,
       case GTK_CSS_SELECTOR_CATEGORY_SIMPLE:
         break;
       case GTK_CSS_SELECTOR_CATEGORY_SIMPLE_RADICAL:
-        if (in_sibling)
-          break;
         if (node)
           {
             if (!tree->selector.class->match_one (&tree->selector, node))
               return 0;
           }
-        else if (filter)
+        else if (match_filter && filter)
           {
             if (!gtk_counting_bloom_filter_may_contain (filter,
                                                         gtk_css_selector_hash_one (&tree->selector)))
@@ -1860,11 +1858,11 @@ gtk_css_selector_tree_get_change (const GtkCssSelectorTree     *tree,
           }
         break;
       case GTK_CSS_SELECTOR_CATEGORY_PARENT:
-        in_sibling = FALSE;
+        match_filter = TRUE;
         node = NULL;
         break;
       case GTK_CSS_SELECTOR_CATEGORY_SIBLING:
-        in_sibling = TRUE;
+        match_filter = FALSE;
         node = NULL;
         break;
       default:
@@ -1875,7 +1873,7 @@ gtk_css_selector_tree_get_change (const GtkCssSelectorTree     *tree,
   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, filter, node, in_sibling);
+    change |= gtk_css_selector_tree_get_change (prev, filter, node, match_filter);
 
   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;
@@ -1883,49 +1881,6 @@ gtk_css_selector_tree_get_change (const GtkCssSelectorTree     *tree,
   return change;
 }
 
-static gboolean
-gtk_css_selector_tree_match_bloom (const GtkCssSelectorTree     *tree,
-                                   const GtkCountingBloomFilter *filter,
-                                   gboolean                      in_sibling)
-{
-  const GtkCssSelectorTree *prev;
-
-  switch (tree->selector.class->category)
-    {
-      case GTK_CSS_SELECTOR_CATEGORY_SIMPLE:
-        break;
-      case GTK_CSS_SELECTOR_CATEGORY_SIMPLE_RADICAL:
-        if (in_sibling)
-          break;
-        if (!gtk_counting_bloom_filter_may_contain (filter,
-                                                    gtk_css_selector_hash_one (&tree->selector)))
-          return FALSE;
-        break;
-      case GTK_CSS_SELECTOR_CATEGORY_PARENT:
-        in_sibling = FALSE;
-        break;
-      case GTK_CSS_SELECTOR_CATEGORY_SIBLING:
-        in_sibling = TRUE;
-        break;
-      default:
-        g_assert_not_reached ();
-        return FALSE;
-    }
-
-  if (gtk_css_selector_tree_get_matches (tree))
-    return TRUE;
-
-  for (prev = gtk_css_selector_tree_get_previous (tree);
-       prev != NULL;
-       prev = gtk_css_selector_tree_get_sibling (prev))
-    {
-      if (gtk_css_selector_tree_match_bloom (prev, filter, in_sibling))
-        return TRUE;
-    }
-
-  return FALSE;
-}
-
 static void
 gtk_css_selector_tree_found_match (const GtkCssSelectorTree  *tree,
                                   GPtrArray                **results,
@@ -1948,33 +1903,32 @@ gtk_css_selector_tree_found_match (const GtkCssSelectorTree  *tree,
     *change |= GTK_CSS_CHANGE_GOT_MATCH;
 }
 
-static void
+static gboolean
 gtk_css_selector_tree_match (const GtkCssSelectorTree      *tree,
                              const GtkCountingBloomFilter  *filter,
+                             gboolean                       match_filter,
                              GtkCssNode                    *node,
-                             gboolean                       in_sibling,
                              GPtrArray                    **results,
                              GtkCssChange                  *change)
 {
   const GtkCssSelectorTree *prev;
   GtkCssNode *child;
 
+  if (match_filter && tree->selector.class->category == GTK_CSS_SELECTOR_CATEGORY_SIMPLE_RADICAL &&
+      !gtk_counting_bloom_filter_may_contain (filter, gtk_css_selector_hash_one (&tree->selector)))
+    return FALSE;
+
   if (!gtk_css_selector_match_one (&tree->selector, node))
     {
       if (change)
-        *change = gtk_css_selector_tree_get_change (tree, filter, node, in_sibling);
-      return;
+        *change = gtk_css_selector_tree_get_change (tree, filter, node, match_filter);
+      return TRUE;
     }
 
   gtk_css_selector_tree_found_match (tree, results, change);
 
-  if (!gtk_css_selector_is_simple (&tree->selector))
-    {
-      if (filter && !gtk_css_selector_tree_match_bloom (tree, filter, in_sibling))
-        goto out;
-
-      in_sibling = tree->selector.class->category == GTK_CSS_SELECTOR_CATEGORY_SIBLING;
-    }
+  if (!gtk_css_selector_is_simple (&tree->selector) && filter)
+    match_filter = tree->selector.class->category == GTK_CSS_SELECTOR_CATEGORY_PARENT;
 
   for (prev = gtk_css_selector_tree_get_previous (tree);
        prev != NULL;
@@ -1985,17 +1939,17 @@ gtk_css_selector_tree_match (const GtkCssSelectorTree      *tree,
            child = gtk_css_selector_iterator (&tree->selector, node, child))
         {
           GtkCssChange child_change = 0;
-          gtk_css_selector_tree_match (prev, filter, child, in_sibling, results, change ? &child_change : 
NULL);
+          if (!gtk_css_selector_tree_match (prev, filter, match_filter, child, results, change ? 
&child_change : NULL))
+            break;
           if (change)
             *change |= child_change;
         }
     }
 
-out:
   if (change && *change)
     *change = tree->selector.class->get_change (&tree->selector, *change & ~GTK_CSS_CHANGE_GOT_MATCH) | 
GTK_CSS_CHANGE_GOT_MATCH;
 
-  return;
+  return TRUE;
 }
 
 GPtrArray *
@@ -2013,7 +1967,7 @@ gtk_css_selector_tree_match_all (const GtkCssSelectorTree     *tree,
        tree = gtk_css_selector_tree_get_sibling (tree))
     {
       GtkCssChange child_change = 0;
-      gtk_css_selector_tree_match (tree, filter, node, FALSE, &results, change ? &child_change : NULL);
+      gtk_css_selector_tree_match (tree, filter, FALSE, node, &results, change ? &child_change : NULL);
       if (change)
         *change |= child_change;
     }