[gtk] cssrbtree: Fix a crasher
- From: Benjamin Otte <otte src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gtk] cssrbtree: Fix a crasher
- Date: Wed, 19 Sep 2018 02:32:14 +0000 (UTC)
commit 5bf009a203000ee2d5ddd8b66cd855197d66c8e5
Author: Benjamin Otte <otte redhat com>
Date: Wed Sep 19 04:26:37 2018 +0200
cssrbtree: Fix a crasher
After removing elements, there were a few cases where the tree wasn't
properly balanced which could further down violate assumptions about the
layout.
Attached is the original testcase that triggered it. I didn't bother
simplifying it.
gtk/gtkcssrbtree.c | 4 +-
testsuite/gtk/cssrbtree-crash.c | 286 ++++++++++++++++++++++++++++++++++++++++
testsuite/gtk/meson.build | 1 +
3 files changed, 289 insertions(+), 2 deletions(-)
---
diff --git a/gtk/gtkcssrbtree.c b/gtk/gtkcssrbtree.c
index fed8cc9c76..d791f042b3 100644
--- a/gtk/gtkcssrbtree.c
+++ b/gtk/gtkcssrbtree.c
@@ -353,7 +353,7 @@ gtk_css_rb_tree_remove_node_fixup (GtkCssRbTree *tree,
GtkCssRbNode *node,
GtkCssRbNode *parent)
{
- while (node->parent && is_black (node))
+ while (node != tree->root && is_black (node))
{
if (node == parent->left)
{
@@ -664,7 +664,7 @@ gtk_css_rb_tree_remove (GtkCssRbTree *tree,
/* We need to clean up the validity of the tree.
*/
- if (x && is_black (y))
+ if (is_black (y))
gtk_css_rb_tree_remove_node_fixup (tree, x, y->parent);
if (y != real_node)
diff --git a/testsuite/gtk/cssrbtree-crash.c b/testsuite/gtk/cssrbtree-crash.c
new file mode 100644
index 0000000000..3d1036148f
--- /dev/null
+++ b/testsuite/gtk/cssrbtree-crash.c
@@ -0,0 +1,286 @@
+/* GtkRBTree tests.
+ *
+ * Copyright (C) 2011, Red Hat, Inc.
+ * Authors: Benjamin Otte <otte gnome org>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser 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
+ * Lesser 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/>.
+ */
+
+#include <locale.h>
+
+#include <gtk/gtk.h>
+
+#include "gtk/gtkcssrbtreeprivate.h"
+
+typedef struct _Node Node;
+typedef struct _Aug Aug;
+
+struct _Node {
+ guint unused;
+};
+
+struct _Aug {
+ guint n_items;
+};
+
+static void
+augment (GtkCssRbTree *tree,
+ gpointer _aug,
+ gpointer _node,
+ gpointer left,
+ gpointer right)
+{
+ Aug *aug = _aug;
+
+ aug->n_items = 1;
+
+ if (left)
+ {
+ Aug *left_aug = gtk_css_rb_tree_get_augment (tree, left);
+
+ aug->n_items += left_aug->n_items;
+ }
+
+ if (right)
+ {
+ Aug *right_aug = gtk_css_rb_tree_get_augment (tree, right);
+
+ aug->n_items += right_aug->n_items;
+ }
+}
+
+static Node *
+get (GtkCssRbTree *tree,
+ guint pos)
+{
+ Node *node, *tmp;
+
+ node = gtk_css_rb_tree_get_root (tree);
+
+ while (node)
+ {
+ tmp = gtk_css_rb_tree_get_left (tree, node);
+ if (tmp)
+ {
+ Aug *aug = gtk_css_rb_tree_get_augment (tree, tmp);
+ if (pos < aug->n_items)
+ {
+ node = tmp;
+ continue;
+ }
+ pos -= aug->n_items;
+ }
+
+ if (pos < 1)
+ break;
+ pos--;
+
+ node = gtk_css_rb_tree_get_right (tree, node);
+ }
+
+ return node;
+}
+
+static void
+add (GtkCssRbTree *tree,
+ guint pos)
+{
+ Node *node = get (tree, pos);
+
+ gtk_css_rb_tree_insert_before (tree, node);
+}
+
+static void
+delete (GtkCssRbTree *tree,
+ guint pos)
+{
+ Node *node = get (tree, pos);
+
+ gtk_css_rb_tree_remove (tree, node);
+}
+
+static guint
+print_node (GtkCssRbTree *tree,
+ Node *node,
+ guint depth,
+ const char *prefix,
+ guint n)
+{
+ Node *child;
+
+ child = gtk_css_rb_tree_get_left (tree, node);
+ if (child)
+ n = print_node (tree, child, depth + 1, "/", n);
+ g_print ("%*s %u\n", 2 * depth, prefix, n);
+ n++;
+ child = gtk_css_rb_tree_get_right (tree, node);
+ if (child)
+ n = print_node (tree, child, depth + 1, "\\", n);
+
+ return n;
+}
+
+static void
+print (GtkCssRbTree *tree)
+{
+ print_node (tree, gtk_css_rb_tree_get_root (tree), 0, "", 0);
+}
+
+static void
+test_crash (void)
+{
+ GtkCssRbTree *tree;
+ guint i;
+
+ tree = gtk_css_rb_tree_new (Node, Aug, augment, NULL, NULL);
+
+ for (i = 0; i < 300; i++)
+ add (tree, i);
+ print (tree);
+ delete (tree, 144);
+ add (tree, 56);
+ delete (tree, 113);
+ delete (tree, 278);
+ delete (tree, 45);
+ delete (tree, 108);
+ delete (tree, 41);
+ add (tree, 56);
+ add (tree, 200);
+ delete (tree, 127);
+ delete (tree, 222);
+ add (tree, 80);
+ add (tree, 143);
+ add (tree, 216);
+ delete (tree, 177);
+ delete (tree, 193);
+ add (tree, 190);
+ delete (tree, 288);
+ add (tree, 45);
+ add (tree, 57);
+ add (tree, 211);
+ delete (tree, 103);
+ add (tree, 152);
+ delete (tree, 60);
+ add (tree, 185);
+ delete (tree, 167);
+ add (tree, 92);
+ delete (tree, 104);
+ delete (tree, 110);
+ delete (tree, 115);
+ add (tree, 32);
+ delete (tree, 44);
+ add (tree, 159);
+ add (tree, 271);
+ delete (tree, 35);
+ add (tree, 250);
+ delete (tree, 36);
+ add (tree, 284);
+ delete (tree, 82);
+ delete (tree, 248);
+ add (tree, 22);
+ delete (tree, 284);
+ add (tree, 88);
+ delete (tree, 182);
+ add (tree, 70);
+ add (tree, 55);
+ delete (tree, 6);
+ add (tree, 85);
+ delete (tree, 36);
+ delete (tree, 33);
+ delete (tree, 108);
+ add (tree, 229);
+ delete (tree, 269);
+ add (tree, 20);
+ add (tree, 170);
+ delete (tree, 154);
+ add (tree, 26);
+ add (tree, 211);
+ delete (tree, 167);
+ add (tree, 183);
+ add (tree, 292);
+ delete (tree, 2);
+ add (tree, 5);
+ delete (tree, 14);
+ delete (tree, 91);
+ add (tree, 172);
+ add (tree, 99);
+ delete (tree, 3);
+ delete (tree, 74);
+ delete (tree, 122);
+ add (tree, 87);
+ add (tree, 176);
+ delete (tree, 294);
+ add (tree, 169);
+ delete (tree, 41);
+ add (tree, 95);
+ delete (tree, 185);
+ add (tree, 218);
+ delete (tree, 62);
+ delete (tree, 175);
+ add (tree, 196);
+ delete (tree, 33);
+ delete (tree, 46);
+ add (tree, 30);
+ add (tree, 72);
+ delete (tree, 196);
+ delete (tree, 291);
+ add (tree, 198);
+ delete (tree, 181);
+ add (tree, 105);
+ delete (tree, 75);
+ add (tree, 30);
+ add (tree, 261);
+ delete (tree, 284);
+ delete (tree, 214);
+ delete (tree, 134);
+ add (tree, 153);
+ delete (tree, 46);
+ add (tree, 154);
+ add (tree, 266);
+ delete (tree, 272);
+ delete (tree, 150);
+ add (tree, 131);
+ delete (tree, 208);
+ add (tree, 241);
+ add (tree, 31);
+ add (tree, 151);
+ add (tree, 266);
+ delete (tree, 285);
+ add (tree, 178);
+ add (tree, 159);
+ add (tree, 203);
+ delete (tree, 266);
+ add (tree, 52);
+ delete (tree, 104);
+ add (tree, 243);
+ delete (tree, 12);
+ add (tree, 20);
+ delete (tree, 68);
+ print (tree);
+ delete (tree, 102);
+
+ gtk_css_rb_tree_unref (tree);
+}
+
+int
+main (int argc, char *argv[])
+{
+ g_test_init (&argc, &argv, NULL);
+ setlocale (LC_ALL, "C");
+ g_test_bug_base ("http://bugzilla.gnome.org/show_bug.cgi?id=%s");
+
+ g_test_add_func ("/csrbtree/crash", test_crash);
+
+ return g_test_run ();
+}
diff --git a/testsuite/gtk/meson.build b/testsuite/gtk/meson.build
index 8721eedfdd..d2837bb0bc 100644
--- a/testsuite/gtk/meson.build
+++ b/testsuite/gtk/meson.build
@@ -17,6 +17,7 @@ tests = [
['cellarea'],
['check-icon-names'],
['cssprovider'],
+ ['cssrbtree-crash', ['../../gtk/gtkcssrbtree.c'], ['-DGTK_COMPILATION', '-UG_ENABLE_DEBUG']],
['defaultvalue'],
['entry'],
['filterlistmodel'],
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]