[gtk: 1/2] Avoid recursion in gtk_css_node_ensure_style()

[Benjamin Otte <otte src gnome org>]

commit fc823eb61002d1350305cba6ec718a7c4f6c05e1
Author: Alexander Larsson <alexl redhat com>
Date:   Thu Jun 4 12:10:31 2020 +0200

    Avoid recursion in gtk_css_node_ensure_style()
    
    gtk_css_node_ensure_style() recurses over previous siblings to ensure
    these have a style before its following sibling.  As seen in
    https://gitlab.gnome.org/GNOME/gtk/-/merge_requests/2027 this can
    cause us to stack overflow and crash if we have a lot of children.
    
    And even if we don't have *that* many children its still somewhat
    bad to have stack depths of the same magnitude as the number of
    children, both for performance reasons and debuggability.

 gtk/gtkcssnode.c | 45 +++++++++++++++++++++++++++++++++------------
 1 file changed, 33 insertions(+), 12 deletions(-)
---
diff --git a/gtk/gtkcssnode.c b/gtk/gtkcssnode.c
index 081662b084..9184ffe928 100644
--- a/gtk/gtkcssnode.c
+++ b/gtk/gtkcssnode.c
@@ -949,25 +949,16 @@ gtk_css_node_needs_new_style (GtkCssNode *cssnode)
 }
 
 static void
-gtk_css_node_ensure_style (GtkCssNode                   *cssnode,
-                           const GtkCountingBloomFilter *filter,
-                           gint64                        current_time)
+gtk_css_node_do_ensure_style (GtkCssNode                   *cssnode,
+                              const GtkCountingBloomFilter *filter,
+                              gint64                        current_time)
 {
   gboolean style_changed;
 
-  if (!gtk_css_node_needs_new_style (cssnode))
-    return;
-
-  if (cssnode->parent)
-    gtk_css_node_ensure_style (cssnode->parent, filter, current_time);
-
   if (cssnode->style_is_invalid)
     {
       GtkCssStyle *new_style;
 
-      if (cssnode->previous_sibling)
-        gtk_css_node_ensure_style (cssnode->previous_sibling, filter, current_time);
-
       g_clear_pointer (&cssnode->cache, gtk_css_node_style_cache_unref);
 
       new_style = GTK_CSS_NODE_GET_CLASS (cssnode)->update_style (cssnode,
@@ -990,6 +981,36 @@ gtk_css_node_ensure_style (GtkCssNode                   *cssnode,
   cssnode->style_is_invalid = FALSE;
 }
 
+static void
+gtk_css_node_ensure_style (GtkCssNode                   *cssnode,
+                           const GtkCountingBloomFilter *filter,
+                           gint64                        current_time)
+{
+  GtkCssNode *sibling;
+
+  if (!gtk_css_node_needs_new_style (cssnode))
+    return;
+
+  if (cssnode->parent)
+    gtk_css_node_ensure_style (cssnode->parent, filter, current_time);
+
+  /* Ensure all siblings before this have a valid style, in order
+   * starting at the first that needs it. */
+  sibling = cssnode;
+  while (sibling->style_is_invalid &&
+         sibling->previous_sibling != NULL &&
+         gtk_css_node_needs_new_style (sibling->previous_sibling))
+    sibling = sibling->previous_sibling;
+
+  while (sibling != cssnode)
+    {
+      gtk_css_node_do_ensure_style (sibling, filter, current_time);
+      sibling = sibling->next_sibling;
+    }
+
+  gtk_css_node_do_ensure_style (cssnode, filter, current_time);
+}
+
 GtkCssStyle *
 gtk_css_node_get_style (GtkCssNode *cssnode)
 {