[gtk/wip/matthiasc/css-change: 3/27] css: Faster matching for simple selectors

[Matthias Clasen <matthiasc src gnome org>]

commit 436af79fa7efe3d2f1d3dc9804d10966c36b7aca
Author: Matthias Clasen <mclasen redhat com>
Date:   Sun Jan 12 13:12:07 2020 -0500

    css: Faster matching for simple selectors
    
    Inline simple selectors for node matchers.
    A bit ugly, but works.

 gtk/gtkcssmatcher.c        |  40 ++++++++---
 gtk/gtkcssmatcherprivate.h |  18 ++---
 gtk/gtkcssselector.c       | 163 ++++++++++++++++++++++++++++++++++++++++++---
 3 files changed, 193 insertions(+), 28 deletions(-)
---
diff --git a/gtk/gtkcssmatcher.c b/gtk/gtkcssmatcher.c
index 0fee1ea6c3..a1007c1217 100644
--- a/gtk/gtkcssmatcher.c
+++ b/gtk/gtkcssmatcher.c
@@ -160,14 +160,14 @@ gtk_css_matcher_widget_path_has_position (const GtkCssMatcher *matcher,
 }
 
 static const GtkCssMatcherClass GTK_CSS_MATCHER_WIDGET_PATH = {
+  GTK_CSS_MATCHER_TYPE_WIDGET_PATH,
   gtk_css_matcher_widget_path_get_parent,
   gtk_css_matcher_widget_path_get_previous,
   gtk_css_matcher_widget_path_get_state,
   gtk_css_matcher_widget_path_has_name,
   gtk_css_matcher_widget_path_has_class,
   gtk_css_matcher_widget_path_has_id,
-  gtk_css_matcher_widget_path_has_position,
-  FALSE
+  gtk_css_matcher_widget_path_has_position
 };
 
 gboolean
@@ -336,14 +336,14 @@ gtk_css_matcher_node_has_position (const GtkCssMatcher *matcher,
 }
 
 static const GtkCssMatcherClass GTK_CSS_MATCHER_NODE = {
+  GTK_CSS_MATCHER_TYPE_NODE,
   gtk_css_matcher_node_get_parent,
   gtk_css_matcher_node_get_previous,
   gtk_css_matcher_node_get_state,
   gtk_css_matcher_node_has_name,
   gtk_css_matcher_node_has_class,
   gtk_css_matcher_node_has_id,
-  gtk_css_matcher_node_has_position,
-  FALSE
+  gtk_css_matcher_node_has_position
 };
 
 void
@@ -421,14 +421,14 @@ gtk_css_matcher_any_has_position (const GtkCssMatcher *matcher,
 }
 
 static const GtkCssMatcherClass GTK_CSS_MATCHER_ANY = {
+  GTK_CSS_MATCHER_TYPE_ANY,
   gtk_css_matcher_any_get_parent,
   gtk_css_matcher_any_get_previous,
   gtk_css_matcher_any_get_state,
   gtk_css_matcher_any_has_name,
   gtk_css_matcher_any_has_class,
   gtk_css_matcher_any_has_id,
-  gtk_css_matcher_any_has_position,
-  TRUE
+  gtk_css_matcher_any_has_position
 };
 
 void
@@ -496,15 +496,15 @@ gtk_css_matcher_superset_has_position (const GtkCssMatcher *matcher,
   return TRUE;
 }
 
-static const GtkCssMatcherClass GTK_CSS_MATCHER_SUPERSET2 = {
+static const GtkCssMatcherClass GTK_CSS_MATCHER_SUPERSET = {
+  GTK_CSS_MATCHER_TYPE_SUPERSET,
   gtk_css_matcher_superset_get_parent,
   gtk_css_matcher_superset_get_previous,
   gtk_css_matcher_superset_get_state,
   gtk_css_matcher_superset_has_name,
   gtk_css_matcher_superset_has_class,
   gtk_css_matcher_superset_has_id,
-  gtk_css_matcher_superset_has_position,
-  FALSE
+  gtk_css_matcher_superset_has_position
 };
 
 void
@@ -516,8 +516,27 @@ _gtk_css_matcher_superset_init (GtkCssMatcher       *matcher,
   g_return_if_fail (subset != NULL);
   g_return_if_fail ((relevant & ~(GTK_CSS_CHANGE_CLASS | GTK_CSS_CHANGE_NAME | GTK_CSS_CHANGE_POSITION | 
GTK_CSS_CHANGE_STATE)) == 0);
 
-  *klass = GTK_CSS_MATCHER_SUPERSET2;
+  switch (subset->klass->matcher_type)
+    {
+    case GTK_CSS_MATCHER_TYPE_NODE:
+      matcher->node = subset->node;
+      if (!(relevant & GTK_CSS_CHANGE_STATE))
+        matcher->node.node_state = gtk_css_matcher_superset_get_state (matcher);
+      break;
+    case GTK_CSS_MATCHER_TYPE_WIDGET_PATH:
+      matcher->path = subset->path;
+      break;
+    case GTK_CSS_MATCHER_TYPE_ANY:
+      break;
+    case GTK_CSS_MATCHER_TYPE_SUPERSET:
+    default:
+      g_assert_not_reached ();
+      break;
+    }
+
+  *klass = GTK_CSS_MATCHER_SUPERSET;
 
+  klass->matcher_type = subset->klass->matcher_type;
   if (relevant & GTK_CSS_CHANGE_CLASS)
     klass->has_class = subset->klass->has_class;
   if (relevant & GTK_CSS_CHANGE_NAME)
@@ -529,6 +548,5 @@ _gtk_css_matcher_superset_init (GtkCssMatcher       *matcher,
   if (relevant & GTK_CSS_CHANGE_STATE)
     klass->get_state = subset->klass->get_state;
 
-  *matcher = *subset;
   matcher->klass = klass;
 }
diff --git a/gtk/gtkcssmatcherprivate.h b/gtk/gtkcssmatcherprivate.h
index 6f5e9d195c..89c889bd61 100644
--- a/gtk/gtkcssmatcherprivate.h
+++ b/gtk/gtkcssmatcherprivate.h
@@ -29,7 +29,15 @@ typedef struct _GtkCssMatcherSuperset GtkCssMatcherSuperset;
 typedef struct _GtkCssMatcherWidgetPath GtkCssMatcherWidgetPath;
 typedef struct _GtkCssMatcherClass GtkCssMatcherClass;
 
+typedef enum {
+  GTK_CSS_MATCHER_TYPE_WIDGET_PATH,
+  GTK_CSS_MATCHER_TYPE_NODE,
+  GTK_CSS_MATCHER_TYPE_ANY,
+  GTK_CSS_MATCHER_TYPE_SUPERSET
+} GtkCssMatcherType;
+
 struct _GtkCssMatcherClass {
+  GtkCssMatcherType matcher_type;
   gboolean        (* get_parent)                  (GtkCssMatcher          *matcher,
                                                    const GtkCssMatcher    *child);
   gboolean        (* get_previous)                (GtkCssMatcher          *matcher,
@@ -46,7 +54,6 @@ struct _GtkCssMatcherClass {
                                                    gboolean               forward,
                                                    int                    a,
                                                    int                    b);
-  gboolean is_any;
 };
 
 struct _GtkCssMatcherWidgetPath {
@@ -67,17 +74,10 @@ struct _GtkCssMatcherNode {
   guint                     n_classes;
 };
 
-struct _GtkCssMatcherSuperset {
-  const GtkCssMatcherClass *klass;
-  const GtkCssMatcher      *subset;
-  GtkCssChange              relevant;
-};
-
 union _GtkCssMatcher {
   const GtkCssMatcherClass *klass;
   GtkCssMatcherWidgetPath   path;
   GtkCssMatcherNode         node;
-  GtkCssMatcherSuperset     superset;
 };
 
 gboolean          _gtk_css_matcher_init           (GtkCssMatcher          *matcher,
@@ -145,7 +145,7 @@ _gtk_css_matcher_has_position (const GtkCssMatcher *matcher,
 static inline gboolean
 _gtk_css_matcher_matches_any (const GtkCssMatcher *matcher)
 {
-  return matcher->klass->is_any;
+  return matcher->klass->matcher_type == GTK_CSS_MATCHER_TYPE_ANY;
 }
 
 
diff --git a/gtk/gtkcssselector.c b/gtk/gtkcssselector.c
index 2b7461e5eb..b1f7d3350c 100644
--- a/gtk/gtkcssselector.c
+++ b/gtk/gtkcssselector.c
@@ -1803,6 +1803,91 @@ gtk_css_selectors_skip_initial_selector (GtkCssSelector *selector, const GtkCssS
   return (GtkCssSelector *)gtk_css_selector_previous (selector);
 }
 
+static inline gboolean
+match_node_name (const GtkCssMatcher *matcher,
+                 const char          *name)
+{
+  return matcher->node.node_name == name;
+}
+
+static inline gboolean
+match_node_id (const GtkCssMatcher *matcher,
+               const char          *id)
+{
+  return matcher->node.node_id == id;
+}
+
+static inline gboolean
+match_node_class (const GtkCssMatcher *matcher,
+                  GQuark               class_name)
+{
+  const GQuark *classes = matcher->node.classes;
+
+  switch (matcher->node.n_classes)
+    {
+    case 3:
+      if (classes[2] == class_name)
+        return TRUE;
+      G_GNUC_FALLTHROUGH;
+
+    case 2:
+      if (classes[1] == class_name)
+        return TRUE;
+      G_GNUC_FALLTHROUGH;
+
+    case 1:
+      if (classes[0] == class_name)
+        return TRUE;
+      G_GNUC_FALLTHROUGH;
+
+    case 0:
+      return FALSE;
+
+    default:
+      return gtk_css_node_has_class (matcher->node.node, class_name);
+    }
+
+  return FALSE;
+}
+
+static inline gboolean
+match_node_state (const GtkCssMatcher *matcher,
+                  GtkStateFlags        state)
+{
+  return (matcher->node.node_state & state) == state;
+}
+
+static inline gboolean
+gtk_css_selector_match_node (const GtkCssSelector *selector,
+                             const GtkCssMatcher  *matcher)
+{
+  if (selector->class == &GTK_CSS_SELECTOR_NAME)
+    return match_node_name (matcher, selector->name.name);
+
+  if (selector->class == &GTK_CSS_SELECTOR_CLASS)
+    return match_node_class (matcher, selector->style_class.style_class);
+
+  if (selector->class == &GTK_CSS_SELECTOR_PSEUDOCLASS_STATE)
+    return match_node_state (matcher, selector->state.state);
+
+  if (selector->class == &GTK_CSS_SELECTOR_ID)
+    return match_node_id (matcher, selector->id.name);
+
+  if (selector->class == &GTK_CSS_SELECTOR_NOT_NAME)
+    return !match_node_name (matcher, selector->name.name);
+
+  if (selector->class == &GTK_CSS_SELECTOR_NOT_CLASS)
+    return !match_node_class (matcher, selector->style_class.style_class);
+
+  if (selector->class == &GTK_CSS_SELECTOR_NOT_PSEUDOCLASS_STATE)
+    return !match_node_state (matcher, selector->state.state);
+
+  if (selector->class == &GTK_CSS_SELECTOR_NOT_ID)
+    return !match_node_id (matcher, selector->id.name);
+
+  return gtk_css_selector_match (selector, matcher);
+}
+
 static gboolean
 gtk_css_selector_tree_match_foreach (const GtkCssSelector *selector,
                                      const GtkCssMatcher  *matcher,
@@ -1824,15 +1909,42 @@ gtk_css_selector_tree_match_foreach (const GtkCssSelector *selector,
   return FALSE;
 }
 
+static gboolean
+gtk_css_selector_tree_match_node_foreach (const GtkCssSelector *selector,
+                                          const GtkCssMatcher  *matcher,
+                                          gpointer              res)
+{
+  const GtkCssSelectorTree *tree = (const GtkCssSelectorTree *) selector;
+  const GtkCssSelectorTree *prev;
+
+  if (!gtk_css_selector_match_node (selector, matcher))
+    return FALSE;
+
+  gtk_css_selector_tree_found_match (tree, res);
+
+  for (prev = gtk_css_selector_tree_get_previous (tree);
+       prev != NULL;
+       prev = gtk_css_selector_tree_get_sibling (prev))
+    gtk_css_selector_foreach (&prev->selector, matcher, gtk_css_selector_tree_match_node_foreach, res);
+
+  return FALSE;
+}
+
 GPtrArray *
 _gtk_css_selector_tree_match_all (const GtkCssSelectorTree *tree,
                                  const GtkCssMatcher *matcher)
 {
   GPtrArray *array = NULL;
+  GtkCssSelectorForeachFunc func;
+
+  if (matcher->klass->matcher_type == GTK_CSS_MATCHER_TYPE_NODE)
+    func = gtk_css_selector_tree_match_node_foreach;
+  else
+    func = gtk_css_selector_tree_match_foreach;
 
   for (; tree != NULL;
-       tree = gtk_css_selector_tree_get_sibling (tree))
-    gtk_css_selector_foreach (&tree->selector, matcher, gtk_css_selector_tree_match_foreach, &array);
+         tree = gtk_css_selector_tree_get_sibling (tree))
+      gtk_css_selector_foreach (&tree->selector, matcher, func, &array);
 
   return array;
 }
@@ -1868,13 +1980,14 @@ static GtkCssChange
 gtk_css_selector_tree_get_change (const GtkCssSelectorTree *tree,
                                  const GtkCssMatcher      *matcher)
 {
+  const GtkCssSelector *selector = &tree->selector;
   GtkCssChange change = 0;
   const GtkCssSelectorTree *prev;
 
-  if (!gtk_css_selector_match (&tree->selector, matcher))
+  if (!gtk_css_selector_match (selector, matcher))
     return 0;
 
-  if (!tree->selector.class->is_simple)
+  if (!selector->class->is_simple)
     return tree->change | GTK_CSS_CHANGE_GOT_MATCH;
 
   for (prev = gtk_css_selector_tree_get_previous (tree);
@@ -1883,7 +1996,32 @@ gtk_css_selector_tree_get_change (const GtkCssSelectorTree *tree,
     change |= gtk_css_selector_tree_get_change (prev, matcher);
 
   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;
+    change = tree->selector.class->get_change (selector, change & ~GTK_CSS_CHANGE_GOT_MATCH) | 
GTK_CSS_CHANGE_GOT_MATCH;
+
+  return change;
+}
+
+static GtkCssChange
+gtk_css_selector_tree_get_change_node (const GtkCssSelectorTree *tree,
+                                      const GtkCssMatcher      *matcher)
+{
+  const GtkCssSelector *selector = &tree->selector;
+  GtkCssChange change = 0;
+  const GtkCssSelectorTree *prev;
+
+  if (!gtk_css_selector_match_node (selector, matcher))
+    return 0;
+
+  if (!selector->class->is_simple)
+    return tree->change | GTK_CSS_CHANGE_GOT_MATCH;
+
+  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_node (prev, matcher);
+
+  if (change || gtk_css_selector_tree_get_matches (tree))
+    change = tree->selector.class->get_change (selector, change & ~GTK_CSS_CHANGE_GOT_MATCH) | 
GTK_CSS_CHANGE_GOT_MATCH;
 
   return change;
 }
@@ -1903,9 +2041,18 @@ _gtk_css_selector_tree_get_change_all (const GtkCssSelectorTree *tree,
   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, matcher);
+  if (matcher->klass->matcher_type == GTK_CSS_MATCHER_TYPE_NODE)
+    {
+      for (; tree != NULL;
+           tree = gtk_css_selector_tree_get_sibling (tree))
+         change |= gtk_css_selector_tree_get_change_node (tree, matcher);
+    }
+  else
+    {
+      for (; tree != NULL;
+           tree = gtk_css_selector_tree_get_sibling (tree))
+         change |= gtk_css_selector_tree_get_change (tree, matcher);
+    }
 
   /* Never return reserved bit set */
   return change & ~GTK_CSS_CHANGE_RESERVED_BIT;