gtk: Add GtkTreeListModel

This is a GListModel implementation with a neat API that can be used to
implement trees inside GtkListBox.

11 files changed, 2166 insertions, 0 deletions

diff --git a/docs/reference/gtk/gtk4-docs.xml b/docs/reference/gtk/gtk4-docs.xml
index 6ad9a1164f..2104d147ea 100644
--- a/docs/reference/gtk/gtk4-docs.xml
+++ b/docs/reference/gtk/gtk4-docs.xml
@@ -41,6 +41,11 @@
       <xi:include href="visual_index.xml" />
     </chapter>
 
+    <chapter id="Lists">
+      <title>GListModel support</title>
+      <xi:include href="xml/gtktreelistmodel.xml" />
+    </chapter>
+
     <chapter id="Application">
       <title>Application support</title>
       <xi:include href="xml/gtkapplication.xml" />
diff --git a/gtk/gtk.h b/gtk/gtk.h
index ec151e5b87..6363fe8210 100644
--- a/gtk/gtk.h
+++ b/gtk/gtk.h
@@ -220,6 +220,7 @@
 #include <gtk/gtktooltip.h>
 #include <gtk/gtktestutils.h>
 #include <gtk/gtktreednd.h>
+#include <gtk/gtktreelistmodel.h>
 #include <gtk/gtktreemodel.h>
 #include <gtk/gtktreemodelfilter.h>
 #include <gtk/gtktreemodelsort.h>
diff --git a/gtk/gtkcssrbtree.c b/gtk/gtkcssrbtree.c
new file mode 100644
index 0000000000..fed8cc9c76
--- /dev/null
+++ b/gtk/gtkcssrbtree.c
@@ -0,0 +1,761 @@
+/* gtkrbtree.c
+ * Copyright (C) 2000  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library 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
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "config.h"
+
+#include "gtkcssrbtreeprivate.h"
+
+#include "gtkdebug.h"
+
+typedef struct _GtkCssRbNode GtkCssRbNode;
+
+struct _GtkCssRbTree
+{
+  guint ref_count;
+
+  gsize element_size;
+  gsize augment_size;
+  GtkCssRbTreeAugmentFunc augment_func;
+  GDestroyNotify clear_func;
+  GDestroyNotify clear_augment_func;
+
+  GtkCssRbNode *root;
+};
+
+struct _GtkCssRbNode
+{
+  guint red :1;
+  guint dirty :1;
+
+  GtkCssRbNode *left;
+  GtkCssRbNode *right;
+  GtkCssRbNode *parent;
+};
+
+#define NODE_FROM_POINTER(ptr) ((GtkCssRbNode *) ((ptr) ? (((guchar *) (ptr)) - sizeof (GtkCssRbNode)) : NULL))
+#define NODE_TO_POINTER(node) ((gpointer) ((node) ? (((guchar *) (node)) + sizeof (GtkCssRbNode)) : NULL))
+#define NODE_TO_AUG_POINTER(tree, node) ((gpointer) ((node) ? (((guchar *) (node)) + sizeof (GtkCssRbNode) + (tree)->element_size) : NULL))
+
+static inline gsize
+gtk_css_rb_node_get_size (GtkCssRbTree *tree)
+{
+  return sizeof (GtkCssRbNode) + tree->element_size + tree->augment_size;
+}
+
+static GtkCssRbNode *
+gtk_css_rb_node_new (GtkCssRbTree *tree)
+{
+  GtkCssRbNode *result;
+
+  result = g_slice_alloc0 (gtk_css_rb_node_get_size (tree));
+
+  result->red = TRUE;
+  result->dirty = TRUE;
+
+  return result;
+}
+
+static void
+gtk_css_rb_node_free (GtkCssRbTree *tree,
+                      GtkCssRbNode *node)
+{
+  if (tree->clear_func)
+    tree->clear_func (NODE_TO_POINTER (node));
+  if (tree->clear_augment_func)
+    tree->clear_augment_func (NODE_TO_AUG_POINTER (tree, node));
+
+  g_slice_free1 (gtk_css_rb_node_get_size (tree), node);
+}
+
+static void
+gtk_css_rb_node_free_deep (GtkCssRbTree *tree,
+                           GtkCssRbNode *node)
+{
+  GtkCssRbNode *right = node->right;
+
+  if (node->left)
+    gtk_css_rb_node_free_deep (tree, node->left);
+
+  gtk_css_rb_node_free (tree, node);
+
+  if (right)
+    gtk_css_rb_node_free_deep (tree, right);
+}
+
+static void
+gtk_css_rb_node_mark_dirty (GtkCssRbNode *node,
+                            gboolean      mark_parent)
+{
+  if (node->dirty)
+    return;
+  
+  node->dirty = TRUE;
+
+  if (mark_parent && node->parent)
+    gtk_css_rb_node_mark_dirty (node->parent, TRUE);
+}
+
+static void
+gtk_css_rb_node_clean (GtkCssRbTree *tree,
+                       GtkCssRbNode *node)
+{
+  if (!node->dirty)
+    return;
+
+  node->dirty = FALSE;
+  if (tree->augment_func)
+    tree->augment_func (tree,
+                        NODE_TO_AUG_POINTER (tree, node),
+                        NODE_TO_POINTER (node),
+                        NODE_TO_POINTER (node->left),
+                        NODE_TO_POINTER (node->right));
+}
+
+static GtkCssRbNode *
+gtk_css_rb_node_get_first (GtkCssRbNode *node)
+{
+  while (node->left)
+    node = node->left;
+
+  return node;
+}
+
+static GtkCssRbNode *
+gtk_css_rb_node_get_last (GtkCssRbNode *node)
+{
+  while (node->right)
+    node = node->right;
+
+  return node;
+}
+
+static GtkCssRbNode *
+gtk_css_rb_node_get_previous (GtkCssRbNode *node)
+{
+  GtkCssRbNode *parent;
+
+  if (node->left)
+    return gtk_css_rb_node_get_last (node->left);
+
+  for (parent = node->parent; parent != NULL; parent = node->parent)
+    {
+      if (parent->right == node)
+        return parent;
+
+      node = parent;
+    }
+
+  return NULL;
+}
+
+static GtkCssRbNode *
+gtk_css_rb_node_get_next (GtkCssRbNode *node)
+{
+  GtkCssRbNode *parent;
+
+  if (node->right)
+    return gtk_css_rb_node_get_first (node->right);
+
+  for (parent = node->parent; parent != NULL; parent = node->parent)
+    {
+      if (parent->left == node)
+        return parent;
+
+      node = parent;
+    }
+
+  return NULL;
+}
+
+static void
+gtk_css_rb_node_rotate_left (GtkCssRbTree *tree,
+                             GtkCssRbNode *node)
+{
+  GtkCssRbNode *right;
+
+  right = node->right;
+
+  node->right = right->left;
+  if (right->left)
+    right->left->parent = node;
+
+  right->parent = node->parent;
+  if (node->parent)
+    {
+      if (node == node->parent->left)
+	node->parent->left = right;
+      else
+	node->parent->right = right;
+    }
+  else
+    {
+      tree->root = right;
+    }
+
+  right->left = node;
+  node->parent = right;
+
+  gtk_css_rb_node_mark_dirty (node, FALSE);
+  gtk_css_rb_node_mark_dirty (right, FALSE);
+}
+
+static void
+gtk_css_rb_node_rotate_right (GtkCssRbTree *tree,
+                              GtkCssRbNode *node)
+{
+  GtkCssRbNode *left;
+
+  left = node->left;
+
+  node->left = left->right;
+  if (left->right)
+    left->right->parent = node;
+
+  left->parent = node->parent;
+  if (node->parent)
+    {
+      if (node == node->parent->right)
+	node->parent->right = left;
+      else
+	node->parent->left = left;
+    }
+  else
+    {
+      tree->root = left;
+    }
+
+  /* link node and left */
+  left->right = node;
+  node->parent = left;
+
+  gtk_css_rb_node_mark_dirty (node, FALSE);
+  gtk_css_rb_node_mark_dirty (left, FALSE);
+}
+
+static gboolean
+is_red (GtkCssRbNode *node_or_null)
+{
+  if (node_or_null == NULL)
+    return FALSE;
+  else
+    return node_or_null->red;
+}
+
+static inline gboolean
+is_black (GtkCssRbNode *node_or_null)
+{
+  return !is_red (node_or_null);
+}
+
+static void
+set_black (GtkCssRbNode *node_or_null)
+{
+  if (node_or_null == NULL)
+    return;
+
+  node_or_null->red = FALSE;
+}
+
+static void
+set_red (GtkCssRbNode *node_or_null)
+{
+  if (node_or_null == NULL)
+    return;
+
+  node_or_null->red = TRUE;
+}
+
+static void
+gtk_css_rb_tree_insert_fixup (GtkCssRbTree *tree,
+                              GtkCssRbNode *node)
+{
+
+  /* check Red-Black properties */
+  while (node->parent && is_red (node->parent))
+    {
+      /* we have a violation */
+      g_assert (node->parent->parent);
+
+      if (node->parent == node->parent->parent->left)
+	{
+	  GtkCssRbNode *uncle = node->parent->parent->right;
+
+	  if (is_red (uncle))
+	    {
+	      /* uncle is red */
+	      set_black (node->parent);
+              set_black (uncle);
+              set_red (node->parent->parent);
+	      node = node->parent->parent;
+	    }
+	  else
+	    {
+	      /* uncle is black */
+	      if (node == node->parent->right)
+		{
+		  /* make node a left child */
+		  node = node->parent;
+		  gtk_css_rb_node_rotate_left (tree, node);
+		}
+	      /* recolor and rotate */
+              set_black (node->parent);
+              set_red (node->parent->parent);
+	      gtk_css_rb_node_rotate_right (tree, node->parent->parent);
+	    }
+	}
+      else
+	{
+	  /* mirror image of above code */
+	  GtkCssRbNode *uncle = node->parent->parent->left;
+
+	  if (is_red (uncle))
+	    {
+	      /* uncle is red */
+              set_black (node->parent);
+              set_black (uncle);
+              set_red (node->parent->parent);
+	      node = node->parent->parent;
+	    }
+	  else
+	    {
+              /* uncle is black */
+	      if (node == node->parent->left)
+		{
+		  node = node->parent;
+		  gtk_css_rb_node_rotate_right (tree, node);
+		}
+	      set_black (node->parent);
+	      set_red (node->parent->parent);
+	      gtk_css_rb_node_rotate_left (tree, node->parent->parent);
+	    }
+	}
+    }
+
+  set_black (tree->root);
+}
+
+static void
+gtk_css_rb_tree_remove_node_fixup (GtkCssRbTree *tree,
+                                   GtkCssRbNode *node,
+                                   GtkCssRbNode *parent)
+{
+  while (node->parent && is_black (node))
+    {
+      if (node == parent->left)
+	{
+	  GtkCssRbNode *w = parent->right;
+
+	  if (is_red (w))
+	    {
+	      set_black (w);
+              set_red (parent);
+	      gtk_css_rb_node_rotate_left (tree, parent);
+	      w = parent->right;
+	    }
+	  if (is_black (w->left) && is_black (w->right))
+	    {
+	      set_red (w);
+	      node = parent;
+	    }
+	  else
+	    {
+	      if (is_black (w->right))
+		{
+		  set_black (w->left);
+		  set_red (w);
+		  gtk_css_rb_node_rotate_right (tree, w);
+		  w = parent->right;
+		}
+	      w->red = parent->red;
+	      set_black (parent);
+              set_black (w->right);
+	      gtk_css_rb_node_rotate_left (tree, parent);
+	      node = tree->root;
+	    }
+	}
+      else
+	{
+	  GtkCssRbNode *w = parent->left;
+	  if (is_red (w))
+	    {
+	      set_black (w);
+	      set_red (parent);
+	      gtk_css_rb_node_rotate_right (tree, parent);
+	      w = parent->left;
+	    }
+	  if (is_black (w->right) && is_black (w->left))
+	    {
+	      set_red (w);
+	      node = parent;
+	    }
+	  else
+	    {
+	      if (is_black (w->left))
+		{
+		  set_black (w->right);
+		  set_red (w);
+		  gtk_css_rb_node_rotate_left (tree, w);
+		  w = parent->left;
+		}
+	      w->red = parent->red;
+	      set_black (parent);
+	      set_black (w->left);
+	      gtk_css_rb_node_rotate_right (tree, parent);
+	      node = tree->root;
+	    }
+	}
+
+      parent = node->parent;
+    }
+
+  set_black (node);
+}
+
+GtkCssRbTree *
+gtk_css_rb_tree_new_for_size (gsize                   element_size,
+                              gsize                   augment_size,
+                              GtkCssRbTreeAugmentFunc augment_func,
+                              GDestroyNotify          clear_func,
+                              GDestroyNotify          clear_augment_func)
+{
+  GtkCssRbTree *tree;
+
+  tree = g_slice_new0 (GtkCssRbTree);
+  tree->ref_count = 1;
+
+  tree->element_size = element_size;
+  tree->augment_size = augment_size;
+  tree->augment_func = augment_func;
+  tree->clear_func = clear_func;
+  tree->clear_augment_func = clear_augment_func;
+
+  return tree;
+}
+
+GtkCssRbTree *
+gtk_css_rb_tree_ref (GtkCssRbTree *tree)
+{
+  tree->ref_count++;
+
+  return tree;
+}
+
+void
+gtk_css_rb_tree_unref (GtkCssRbTree *tree)
+{
+  tree->ref_count--;
+  if (tree->ref_count > 0)
+    return;
+
+  if (tree->root)
+    gtk_css_rb_node_free_deep (tree, tree->root);
+    
+  g_slice_free (GtkCssRbTree, tree);
+}
+
+gpointer
+gtk_css_rb_tree_get_first (GtkCssRbTree *tree)
+{
+  if (tree->root == NULL)
+    return NULL;
+
+  return NODE_TO_POINTER (gtk_css_rb_node_get_first (tree->root));
+}
+
+gpointer
+gtk_css_rb_tree_get_last (GtkCssRbTree *tree)
+{
+  if (tree->root == NULL)
+    return NULL;
+
+  return NODE_TO_POINTER (gtk_css_rb_node_get_last (tree->root));
+}
+
+gpointer
+gtk_css_rb_tree_get_previous (GtkCssRbTree *tree,
+                              gpointer      node)
+{
+  return NODE_TO_POINTER (gtk_css_rb_node_get_previous (NODE_FROM_POINTER (node)));
+}
+
+gpointer
+gtk_css_rb_tree_get_next (GtkCssRbTree *tree,
+                          gpointer      node)
+{
+  return NODE_TO_POINTER (gtk_css_rb_node_get_next (NODE_FROM_POINTER (node)));
+}
+
+gpointer
+gtk_css_rb_tree_get_root (GtkCssRbTree *tree)
+{
+  return NODE_TO_POINTER (tree->root);
+}
+
+gpointer
+gtk_css_rb_tree_get_parent (GtkCssRbTree *tree,
+                            gpointer      node)
+{
+  return NODE_TO_POINTER (NODE_FROM_POINTER (node)->parent);
+}
+
+gpointer
+gtk_css_rb_tree_get_left (GtkCssRbTree *tree,
+                          gpointer      node)
+{
+  return NODE_TO_POINTER (NODE_FROM_POINTER (node)->left);
+}
+
+gpointer
+gtk_css_rb_tree_get_right (GtkCssRbTree *tree,
+                           gpointer      node)
+{
+  return NODE_TO_POINTER (NODE_FROM_POINTER (node)->right);
+}
+
+gpointer
+gtk_css_rb_tree_get_augment (GtkCssRbTree *tree,
+                             gpointer      node)
+{
+  GtkCssRbNode *rbnode = NODE_FROM_POINTER (node);
+
+  gtk_css_rb_node_clean (tree, rbnode);
+
+  return NODE_TO_AUG_POINTER (tree, rbnode);
+}
+
+void
+gtk_css_rb_tree_mark_dirty (GtkCssRbTree *tree,
+                            gpointer      node)
+{
+  gtk_css_rb_node_mark_dirty (NODE_FROM_POINTER (node), TRUE);
+}
+
+gpointer
+gtk_css_rb_tree_insert_before (GtkCssRbTree *tree,
+                              gpointer      node)
+{
+  GtkCssRbNode *result;
+
+  /* setup new node */
+  result = gtk_css_rb_node_new (tree);
+
+  if (tree->root == NULL)
+    {
+      g_assert (node == NULL);
+      tree->root = result;
+    }
+  else if (node == NULL)
+    {
+      return gtk_css_rb_tree_insert_after (tree, gtk_css_rb_tree_get_last (tree));
+    }
+  else
+    {
+      GtkCssRbNode *current = NODE_FROM_POINTER (node);
+
+      if (current->left)
+        {
+          current = gtk_css_rb_node_get_last (current->left);
+          current->right = result;
+        }
+      else
+        {
+          current->left = result;
+        }
+      result->parent = current;
+      gtk_css_rb_node_mark_dirty (current, TRUE);
+    }
+
+  gtk_css_rb_tree_insert_fixup (tree, result);
+
+  return NODE_TO_POINTER (result);
+}
+
+gpointer
+gtk_css_rb_tree_insert_after (GtkCssRbTree *tree,
+                             gpointer      node)
+{
+  GtkCssRbNode *result;
+
+  /* setup new node */
+  result = gtk_css_rb_node_new (tree);
+
+  if (tree->root == NULL)
+    {
+      g_assert (node == NULL);
+      tree->root = result;
+    }
+  else if (node == NULL)
+    {
+      return gtk_css_rb_tree_insert_before (tree, gtk_css_rb_tree_get_first (tree));
+    }
+  else
+    {
+      GtkCssRbNode *current = NODE_FROM_POINTER (node);
+
+      if (current->right)
+        {
+          current = gtk_css_rb_node_get_first (current->right);
+          current->left = result;
+        }
+      else
+        {
+          current->right = result;
+        }
+      result->parent = current;
+      gtk_css_rb_node_mark_dirty (current, TRUE);
+    }
+
+  gtk_css_rb_tree_insert_fixup (tree, result);
+
+  return NODE_TO_POINTER (result);
+}
+
+void
+gtk_css_rb_tree_remove (GtkCssRbTree *tree,
+                        gpointer      node)
+{
+  GtkCssRbNode *x, *y, *real_node;
+  
+  real_node = NODE_FROM_POINTER (node);
+  y = real_node;
+  if (y->left && y->right)
+    {
+      y = y->right;
+
+      while (y->left)
+	y = y->left;
+    }
+
+  /* x is y's only child, or nil */
+  if (y->left)
+    x = y->left;
+  else
+    x = y->right;
+
+  /* remove y from the parent chain */
+  if (x != NULL)
+    x->parent = y->parent;
+  if (y->parent)
+    {
+      if (y == y->parent->left)
+	y->parent->left = x;
+      else
+	y->parent->right = x;
+      gtk_css_rb_node_mark_dirty (y->parent, TRUE);
+    }
+  else
+    {
+      tree->root = x;
+    }
+
+  /* We need to clean up the validity of the tree.
+   */
+  if (x && is_black (y))
+    gtk_css_rb_tree_remove_node_fixup (tree, x, y->parent);
+
+  if (y != real_node)
+    {
+      /* Move the node over */
+      if (is_red (real_node) != is_red (y))
+	y->red = !y->red;
+
+      y->left = real_node->left;
+      if (y->left)
+        y->left->parent = y;
+      y->right = real_node->right;
+      if (y->right)
+        y->right->parent = y;
+      y->parent = real_node->parent;
+      if (y->parent)
+        {
+          if (y->parent->left == real_node)
+            y->parent->left = y;
+          else
+            y->parent->right = y;
+          gtk_css_rb_node_mark_dirty (y->parent, TRUE);
+        }
+      else
+        {
+          tree->root = y;
+        }
+      gtk_css_rb_node_mark_dirty (y, TRUE);
+    }
+
+  gtk_css_rb_node_free (tree, real_node);
+}
+
+void
+gtk_css_rb_tree_remove_all (GtkCssRbTree *tree)
+{
+  if (tree->root)
+    gtk_css_rb_node_free_deep (tree, tree->root);
+
+  tree->root = NULL;
+}
+
+gpointer
+gtk_css_rb_tree_find (GtkCssRbTree           *tree,
+                      gpointer               *out_before,
+                      gpointer               *out_after,
+                      GtkCssRbTreeFindFunc    find_func,
+                      gpointer                user_data)
+{
+  GtkCssRbNode *node, *before = NULL, *after = NULL;
+  int cmp;
+
+  if (tree->root == NULL)
+    {
+      if (out_before)
+        *out_before = NULL;
+      if (out_after)
+        *out_after = NULL;
+
+      return NULL;
+    }
+
+  node = tree->root;
+  for (cmp = find_func (tree, NODE_TO_POINTER (node), user_data);
+       cmp != 0;
+       cmp = find_func (tree, NODE_TO_POINTER (node), user_data))
+    {
+      if (cmp < 0)
+        {
+          before = node;
+          node = node->right;
+        }
+      else /* cmp > 0 */
+        {
+          after = node;
+          node = node->left;
+        }
+      if (node == NULL)
+        {
+          if (out_before)
+            *out_before = NODE_TO_POINTER (before);
+          if (out_after)
+            *out_after = NODE_TO_POINTER (after);
+          return NULL;;
+        }
+    }
+
+  if (out_before)
+    *out_before = NODE_TO_POINTER (gtk_css_rb_node_get_previous (node));
+  if (out_after)
+    *out_after = NODE_TO_POINTER (gtk_css_rb_node_get_next (node));
+
+  return NODE_TO_POINTER (node);
+}
diff --git a/gtk/gtkcssrbtreeprivate.h b/gtk/gtkcssrbtreeprivate.h
new file mode 100644
index 0000000000..f80108dba8
--- /dev/null
+++ b/gtk/gtkcssrbtreeprivate.h
@@ -0,0 +1,90 @@
+/* gtkrb_tree.h
+ * Copyright (C) 2000  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library 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
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/* A Red-Black Tree implementation used specifically by GtkTreeView.
+ */
+#ifndef __GTK_CSS_RB_TREE_H__
+#define __GTK_CSS_RB_TREE_H__
+
+#include <glib.h>
+
+
+G_BEGIN_DECLS
+
+
+typedef struct _GtkCssRbTree GtkCssRbTree;
+
+typedef void            (* GtkCssRbTreeAugmentFunc)     (GtkCssRbTree           *tree,
+                                                         gpointer                node_augment,
+                                                         gpointer                node,
+                                                         gpointer                left,
+                                                         gpointer                right);
+typedef int             (* GtkCssRbTreeFindFunc)        (GtkCssRbTree           *tree,
+                                                         gpointer                node,
+                                                         gpointer                user_data);
+
+GtkCssRbTree *          gtk_css_rb_tree_new_for_size    (gsize                   element_size,
+                                                         gsize                   augment_size,
+                                                         GtkCssRbTreeAugmentFunc augment_func,
+                                                         GDestroyNotify          clear_func,
+                                                         GDestroyNotify          clear_augment_func);
+#define gtk_css_rb_tree_new(type, augment_type, augment_func, clear_func, clear_augment_func) \
+  gtk_css_rb_tree_new_for_size (sizeof (type), sizeof (augment_type), (augment_func), (clear_func), (clear_augment_func))
+
+GtkCssRbTree *          gtk_css_rb_tree_ref             (GtkCssRbTree           *tree);
+void                    gtk_css_rb_tree_unref           (GtkCssRbTree           *tree);
+
+gpointer                gtk_css_rb_tree_get_first       (GtkCssRbTree           *tree);
+gpointer                gtk_css_rb_tree_get_last        (GtkCssRbTree           *tree);
+gpointer                gtk_css_rb_tree_get_previous    (GtkCssRbTree           *tree,
+                                                         gpointer                node);
+gpointer                gtk_css_rb_tree_get_next        (GtkCssRbTree           *tree,
+                                                         gpointer                node);
+
+gpointer                gtk_css_rb_tree_get_root        (GtkCssRbTree           *tree);
+gpointer                gtk_css_rb_tree_get_parent      (GtkCssRbTree           *tree,
+                                                         gpointer                node);
+gpointer                gtk_css_rb_tree_get_left        (GtkCssRbTree           *tree,
+                                                         gpointer                node);
+gpointer                gtk_css_rb_tree_get_right       (GtkCssRbTree           *tree,
+                                                         gpointer                node);
+gpointer                gtk_css_rb_tree_get_augment     (GtkCssRbTree           *tree,
+                                                         gpointer                node);
+
+void                    gtk_css_rb_tree_mark_dirty      (GtkCssRbTree           *tree,
+                                                         gpointer                node);
+
+gpointer                gtk_css_rb_tree_insert_before   (GtkCssRbTree           *tree,
+                                                         gpointer                node);
+gpointer                gtk_css_rb_tree_insert_after    (GtkCssRbTree           *tree,
+                                                         gpointer                node);
+void                    gtk_css_rb_tree_remove          (GtkCssRbTree           *tree,
+                                                         gpointer                node);
+void                    gtk_css_rb_tree_remove_all      (GtkCssRbTree           *tree);
+
+gpointer                gtk_css_rb_tree_find            (GtkCssRbTree           *tree,
+                                                         gpointer               *out_before,
+                                                         gpointer               *out_after,
+                                                         GtkCssRbTreeFindFunc    find_func,
+                                                         gpointer                user_data);
+
+
+
+G_END_DECLS
+
+
+#endif /* __GTK_CSS_RB_TREE_H__ */
diff --git a/gtk/gtktreelistmodel.c b/gtk/gtktreelistmodel.c
new file mode 100644
index 0000000000..313b62dea5
--- /dev/null
+++ b/gtk/gtktreelistmodel.c
@@ -0,0 +1,821 @@
+/*
+ * Copyright © 2018 Benjamin Otte
+ *
+ * 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.1 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/>.
+ *
+ * Authors: Benjamin Otte <otte@gnome.org>
+ */
+
+#include "config.h"
+
+#include "gtktreelistmodel.h"
+
+#include "gtkcssrbtreeprivate.h"
+#include "gtkintl.h"
+#include "gtkprivate.h"
+
+enum {
+  PROP_0,
+  PROP_AUTOEXPAND,
+  PROP_ROOT_MODEL,
+  NUM_PROPERTIES
+};
+
+typedef struct _TreeNode TreeNode;
+typedef struct _TreeAugment TreeAugment;
+
+struct _TreeNode
+{
+  GListModel *model;
+  GtkCssRbTree *children;
+  union {
+    TreeNode *parent;
+    GtkTreeListModel *list;
+  };
+
+  guint empty : 1;
+  guint is_root : 1;
+};
+
+struct _TreeAugment
+{
+  guint n_items;
+  guint n_local;
+};
+
+struct _GtkTreeListModel
+{
+  GObject parent_instance;
+
+  TreeNode root_node;
+
+  GtkTreeListModelCreateModelFunc create_func;
+  gpointer user_data;
+  GDestroyNotify user_destroy;
+
+  guint autoexpand : 1;
+};
+
+struct _GtkTreeListModelClass
+{
+  GObjectClass parent_class;
+};
+
+static GParamSpec *properties[NUM_PROPERTIES] = { NULL, };
+
+static GtkTreeListModel *
+tree_node_get_tree_list_model (TreeNode *node)
+{
+  for (; !node->is_root; node = node->parent)
+    { }
+
+  return node->list;
+}
+
+static TreeNode *
+tree_node_get_nth_child (TreeNode *node,
+                         guint     position)
+{
+  GtkCssRbTree *tree;
+  TreeNode *child, *tmp;
+  TreeAugment *aug;
+
+  tree = node->children;
+  child = gtk_css_rb_tree_get_root (tree);
+
+  while (TRUE)
+    {
+      tmp = gtk_css_rb_tree_get_left (tree, child);
+      if (tmp)
+        {
+          aug = gtk_css_rb_tree_get_augment (tree, tmp);
+          if (position < aug->n_local)
+            {
+              child = tmp;
+              continue;
+            }
+          position -= aug->n_local;
+        }
+
+      if (position == 0)
+        return child;
+
+      position--;
+
+      child = gtk_css_rb_tree_get_right (tree, child);
+    }
+
+  g_return_val_if_reached (NULL);
+}
+
+static guint
+tree_node_get_n_children (TreeNode *node)
+{
+  TreeAugment *child_aug;
+  TreeNode *child_node;
+
+  if (node->children == NULL)
+    return 0;
+
+  child_node = gtk_css_rb_tree_get_root (node->children);
+  if (child_node == NULL)
+    return 0;
+
+  child_aug = gtk_css_rb_tree_get_augment (node->children, child_node);
+
+  return child_aug->n_items;
+}
+
+static guint
+tree_node_get_local_position (GtkCssRbTree *tree,
+                              TreeNode     *node)
+{
+  TreeNode *left, *parent;
+  TreeAugment *left_aug;
+  guint n;
+  
+  left = gtk_css_rb_tree_get_left (tree, node);
+  if (left)
+    {
+      left_aug = gtk_css_rb_tree_get_augment (tree, left);
+      n = left_aug->n_local;
+    }
+  else
+    {
+      n = 0;
+    }
+
+  for (parent = gtk_css_rb_tree_get_parent (tree, node);
+       parent;
+       parent = gtk_css_rb_tree_get_parent (tree, node))
+    {
+      left = gtk_css_rb_tree_get_left (tree, parent);
+      if (left == node)
+        {
+          /* we are the left node, nothing changes */
+        }
+      else
+        {
+          /* we are the right node */
+          n++;
+          if (left)
+            {
+              left_aug = gtk_css_rb_tree_get_augment (tree, left);
+              n += left_aug->n_local;
+            }
+        }
+      node = parent;
+    }
+
+  return n;
+}
+
+static guint
+tree_node_get_position (TreeNode *node)
+{
+  GtkCssRbTree *tree;
+  TreeNode *left, *parent;
+  TreeAugment *left_aug;
+  guint n;
+  
+  for (n = 0;
+       !node->is_root;
+       node = node->parent, n++)
+    {
+      tree = node->parent->children;
+
+      left = gtk_css_rb_tree_get_left (tree, node);
+      if (left)
+        {
+          left_aug = gtk_css_rb_tree_get_augment (tree, left);
+          n += left_aug->n_items;
+        }
+
+      for (parent = gtk_css_rb_tree_get_parent (tree, node);
+           parent;
+           parent = gtk_css_rb_tree_get_parent (tree, node))
+        {
+          left = gtk_css_rb_tree_get_left (tree, parent);
+          if (left == node)
+            {
+              /* we are the left node, nothing changes */
+            }
+          else
+            {
+              /* we are the right node */
+              n += 1 + tree_node_get_n_children (parent);
+              if (left)
+                {
+                  left_aug = gtk_css_rb_tree_get_augment (tree, left);
+                  n += left_aug->n_items;
+                }
+            }
+          node = parent;
+        }
+    }
+  /* the root isn't visible */
+  n--;
+
+  return n;
+}
+
+static void
+tree_node_mark_dirty (TreeNode *node)
+{
+  for (;
+       !node->is_root;
+       node = node->parent)
+    {
+      gtk_css_rb_tree_mark_dirty (node->parent->children, node);
+    }
+}
+
+static TreeNode *
+gtk_tree_list_model_get_nth (GtkTreeListModel *self,
+                             guint             position)
+{
+  GtkCssRbTree *tree;
+  TreeNode *node, *tmp;
+  guint n_children;
+
+  n_children = tree_node_get_n_children (&self->root_node);
+  if (n_children <= position)
+    return NULL;
+
+  tree = self->root_node.children;
+  node = gtk_css_rb_tree_get_root (tree);
+
+  while (TRUE)
+    {
+      tmp = gtk_css_rb_tree_get_left (tree, node);
+      if (tmp)
+        {
+          TreeAugment *aug = gtk_css_rb_tree_get_augment (tree, tmp);
+          if (position < aug->n_items)
+            {
+              node = tmp;
+              continue;
+            }
+          position -= aug->n_items;
+        }
+
+      if (position == 0)
+        return node;
+
+      position--;
+
+      n_children = tree_node_get_n_children (node);
+      if (position < n_children)
+        {
+          tree = node->children;
+          node = gtk_css_rb_tree_get_root (tree);
+          continue;
+        }
+      position -= n_children;
+
+      node = gtk_css_rb_tree_get_right (tree, node);
+    }
+
+  g_return_val_if_reached (NULL);
+}
+
+static GType
+gtk_tree_list_model_get_item_type (GListModel *list)
+{
+  GtkTreeListModel *self = GTK_TREE_LIST_MODEL (list);
+
+  return g_list_model_get_item_type (self->root_node.model);
+}
+
+static guint
+gtk_tree_list_model_get_n_items (GListModel *list)
+{
+  GtkTreeListModel *self = GTK_TREE_LIST_MODEL (list);
+
+  return tree_node_get_n_children (&self->root_node);
+}
+
+static gpointer
+gtk_tree_list_model_get_item (GListModel *list,
+                              guint       position)
+{
+  GtkTreeListModel *self = GTK_TREE_LIST_MODEL (list);
+  TreeNode *node, *parent;
+
+  node = gtk_tree_list_model_get_nth (self, position);
+  if (node == NULL)
+    return NULL;
+
+  parent = node->parent;
+  return g_list_model_get_item (parent->model,
+                                tree_node_get_local_position (parent->children, node));
+}
+
+static void
+gtk_tree_list_model_model_init (GListModelInterface *iface)
+{
+  iface->get_item_type = gtk_tree_list_model_get_item_type;
+  iface->get_n_items = gtk_tree_list_model_get_n_items;
+  iface->get_item = gtk_tree_list_model_get_item;
+}
+
+G_DEFINE_TYPE_WITH_CODE (GtkTreeListModel, gtk_tree_list_model, G_TYPE_OBJECT,
+                         G_IMPLEMENT_INTERFACE (G_TYPE_LIST_MODEL, gtk_tree_list_model_model_init))
+
+static void
+gtk_tree_list_model_augment (GtkCssRbTree *tree,
+                             gpointer      _aug,
+                             gpointer      _node,
+                             gpointer      left,
+                             gpointer      right)
+{
+  TreeAugment *aug = _aug;
+
+  aug->n_items = 1;
+  aug->n_items += tree_node_get_n_children (_node);
+  aug->n_local = 1;
+
+  if (left)
+    {
+      TreeAugment *left_aug = gtk_css_rb_tree_get_augment (tree, left);
+      aug->n_items += left_aug->n_items;
+      aug->n_local += left_aug->n_local;
+    }
+  if (right)
+    {
+      TreeAugment *right_aug = gtk_css_rb_tree_get_augment (tree, right);
+      aug->n_items += right_aug->n_items;
+      aug->n_local += right_aug->n_local;
+    }
+}
+
+static guint
+gtk_tree_list_model_expand_node (GtkTreeListModel *self,
+                                 TreeNode         *node);
+
+static void
+gtk_tree_list_model_items_changed_cb (GListModel *model,
+                                      guint       position,
+                                      guint       removed,
+                                      guint       added,
+                                      TreeNode   *node)
+{
+  GtkTreeListModel *self;
+  TreeNode *child;
+  guint i, tree_position, tree_removed, tree_added, n_local;
+
+  self = tree_node_get_tree_list_model (node);
+  n_local = g_list_model_get_n_items (model) - added + removed;
+
+  if (position < n_local)
+    {
+      child = tree_node_get_nth_child (node, position);
+      tree_position = tree_node_get_position (child);
+    }
+  else
+    {
+      child = NULL;
+      tree_position = tree_node_get_position (node) + tree_node_get_n_children (node) + 1;
+    }
+
+  if (removed)
+    {
+      TreeNode *tmp;
+
+      g_assert (child != NULL);
+      if (position + removed < n_local)
+        {
+          TreeNode *end = tree_node_get_nth_child (node, position + removed);
+          tree_removed = tree_node_get_position (end) - tree_position;
+        }
+      else
+        {
+          tree_removed = tree_node_get_position (node) + tree_node_get_n_children (node) + 1 - tree_position;
+        }
+
+      for (i = 0; i < removed; i++)
+        {
+          tmp = child;
+          child = gtk_css_rb_tree_get_next (node->children, child);
+          gtk_css_rb_tree_remove (node->children, tmp);
+        }
+    }
+  else
+    {
+      tree_removed = 0;
+    }
+
+  tree_added = added;
+  for (i = 0; i < added; i++)
+    {
+      child = gtk_css_rb_tree_insert_before (node->children, child);
+      child->parent = node;
+    }
+  if (self->autoexpand)
+    {
+      for (i = 0; i < added; i++)
+        {
+          tree_added += gtk_tree_list_model_expand_node (self, child);
+          child = gtk_css_rb_tree_get_next (node->children, child);
+        }
+    }
+
+  tree_node_mark_dirty (node);
+
+  g_list_model_items_changed (G_LIST_MODEL (self),
+                              tree_position,
+                              tree_removed,
+                              tree_added);
+}
+
+static void
+gtk_tree_list_model_clear_node (gpointer data)
+{
+  TreeNode *node = data;
+
+  if (node->model)
+    {
+      g_signal_handlers_disconnect_by_func (node->model,
+                                            gtk_tree_list_model_items_changed_cb,
+                                            node);
+      g_object_unref (node->model);
+    }
+  if (node->children)
+    gtk_css_rb_tree_unref (node->children);
+}
+
+static void
+gtk_tree_list_model_init_node (GtkTreeListModel *list,
+                               TreeNode         *self,
+                               GListModel       *model)
+{
+  gsize i, n;
+  TreeNode *node;
+
+  self->model = g_object_ref (model);
+  g_signal_connect (model,
+                    "items-changed",
+                    G_CALLBACK (gtk_tree_list_model_items_changed_cb),
+                    self);
+  self->children = gtk_css_rb_tree_new (TreeNode,
+                                        TreeAugment,
+                                        gtk_tree_list_model_augment,
+                                        gtk_tree_list_model_clear_node,
+                                        NULL);
+
+  n = g_list_model_get_n_items (model);
+  node = NULL;
+  for (i = 0; i < n; i++)
+    {
+      node = gtk_css_rb_tree_insert_after (self->children, node);
+      node->parent = self;
+      if (list->autoexpand)
+        gtk_tree_list_model_expand_node (list, node);
+    }
+}
+
+static void
+gtk_tree_list_model_set_property (GObject      *object,
+                                  guint         prop_id,
+                                  const GValue *value,
+                                  GParamSpec   *pspec)
+{
+  GtkTreeListModel *self = GTK_TREE_LIST_MODEL (object);
+
+  switch (prop_id)
+    {
+    case PROP_AUTOEXPAND:
+      gtk_tree_list_model_set_autoexpand (self, g_value_get_boolean (value));
+      break;
+
+    default:
+      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
+      break;
+    }
+}
+
+static void 
+gtk_tree_list_model_get_property (GObject     *object,
+                                  guint        prop_id,
+                                  GValue      *value,
+                                  GParamSpec  *pspec)
+{
+  GtkTreeListModel *self = GTK_TREE_LIST_MODEL (object);
+
+  switch (prop_id)
+    {
+    case PROP_AUTOEXPAND:
+      g_value_set_boolean (value, self->autoexpand);
+      break;
+
+    case PROP_ROOT_MODEL:
+      g_value_set_object (value, self->root_node.model);
+      break;
+
+    default:
+      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
+      break;
+    }
+}
+
+static void
+gtk_tree_list_model_finalize (GObject *object)
+{
+  GtkTreeListModel *self = GTK_TREE_LIST_MODEL (object);
+
+  gtk_tree_list_model_clear_node (&self->root_node);
+  if (self->user_destroy)
+    self->user_destroy (self->user_data);
+
+  G_OBJECT_CLASS (gtk_tree_list_model_parent_class)->finalize (object);
+};
+
+static void
+gtk_tree_list_model_class_init (GtkTreeListModelClass *class)
+{
+  GObjectClass *gobject_class = G_OBJECT_CLASS (class);
+
+  gobject_class->set_property = gtk_tree_list_model_set_property;
+  gobject_class->get_property = gtk_tree_list_model_get_property;
+  gobject_class->finalize = gtk_tree_list_model_finalize;
+
+  /**
+   * GtkTreeListModel:autoexpand:
+   *
+   * If all rows should be expanded by default
+   */
+  properties[PROP_AUTOEXPAND] =
+      g_param_spec_boolean ("autoexpand",
+                            P_("autoexpand"),
+                            P_("If all rows should be expanded by default"),
+                            FALSE,
+                            GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
+
+  /**
+   * GtkTreeListModel:root-model:
+   *
+   * The root model displayed
+   */
+  properties[PROP_ROOT_MODEL] =
+      g_param_spec_object ("root-model",
+                           P_("Root model"),
+                           P_("The root model displayed"),
+                           G_TYPE_LIST_MODEL,
+                           GTK_PARAM_READABLE | G_PARAM_EXPLICIT_NOTIFY);
+
+  g_object_class_install_properties (gobject_class, NUM_PROPERTIES, properties);
+}
+
+static void
+gtk_tree_list_model_init (GtkTreeListModel *self)
+{
+  self->root_node.list = self;
+  self->root_node.is_root = TRUE;
+}
+
+/**
+ * gtk_tree_list_model_new:
+ * @root: The #GListModel to use as root
+ * @autoexpand: %TRUE to set the autoexpand property and expand the @root model
+ * @create_func: Function to call to create the #GListModel for the children
+ *     of an item
+ * @user_data: Data to pass to @create_func
+ * @user_destroy: Function to call to free @user_data
+ *
+ * Creates a new empty #GtkTreeListModel displaying @root with all rows collapsed.
+ * 
+ * Returns: a newly created #GtkTreeListModel. 
+ **/
+GtkTreeListModel *
+gtk_tree_list_model_new (GListModel                      *root,
+                         gboolean                         autoexpand,
+                         GtkTreeListModelCreateModelFunc  create_func,
+                         gpointer                         user_data,
+                         GDestroyNotify                   user_destroy)
+{
+  GtkTreeListModel *self;
+
+  g_return_val_if_fail (G_IS_LIST_MODEL (root), NULL);
+  g_return_val_if_fail (create_func != NULL, NULL);
+
+  self = g_object_new (GTK_TYPE_TREE_LIST_MODEL,
+                       "autoexpand", autoexpand,
+                       NULL);
+
+  self->create_func = create_func;
+  self->user_data = user_data;
+  self->user_destroy = user_destroy;
+
+  gtk_tree_list_model_init_node (self, &self->root_node, g_object_ref (root));
+
+  return self;
+}
+
+/**
+ * gtk_tree_list_model_set_autoexpand:
+ * @self: a #GtkTreeListModel
+ * @autoexpand: %TRUE to make the model autoexpand its rows
+ *
+ * If set to %TRUE, the model will recursively expand all rows that
+ * get added to the model. This can be either rows added by changes
+ * to the underlying models or via gtk_tree_list_model_set_expanded().
+ **/
+void
+gtk_tree_list_model_set_autoexpand (GtkTreeListModel *self,
+                                    gboolean          autoexpand)
+{
+  g_return_if_fail (GTK_IS_TREE_LIST_MODEL (self));
+
+  if (self->autoexpand == autoexpand)
+    return;
+
+  self->autoexpand = autoexpand;
+
+  g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_AUTOEXPAND]);
+}
+
+/**
+ * gtk_tree_list_model_get_autoexpand:
+ * @self: a #GtkTreeListModel
+ *
+ * Gets whether the model is set to automatically expand new rows
+ * that get added. This can be either rows added by changes to the
+ * underlying models or via gtk_tree_list_model_set_expanded().
+ *
+ * Returns: %TRUE if the model is set to autoexpand
+ **/
+gboolean
+gtk_tree_list_model_get_autoexpand (GtkTreeListModel *self)
+{
+  g_return_val_if_fail (GTK_IS_TREE_LIST_MODEL (self), FALSE);
+
+  return self->autoexpand;
+}
+
+guint
+gtk_tree_list_model_get_depth (GtkTreeListModel *self,
+                               guint             position)
+{
+  TreeNode *node;
+  guint depth;
+
+  g_return_val_if_fail (GTK_IS_TREE_LIST_MODEL (self), FALSE);
+
+  node = gtk_tree_list_model_get_nth (self, position);
+  if (node == NULL)
+    return 0;
+
+  depth = 0;
+  for (node = node->parent;
+       !node->is_root;
+       node = node->parent)
+    depth++;
+
+  return depth;
+}
+
+static GListModel *
+tree_node_create_model (GtkTreeListModel *self,
+                        TreeNode         *node)
+{
+  TreeNode *parent = node->parent;
+  GListModel *model;
+  GObject *item;
+
+  item = g_list_model_get_item (parent->model,
+                                tree_node_get_local_position (parent->children, node));
+  model = self->create_func (item, self->user_data);
+  g_object_unref (item);
+  if (model == NULL)
+    node->empty = TRUE;
+
+  return model;
+}
+
+static guint
+gtk_tree_list_model_expand_node (GtkTreeListModel *self,
+                                 TreeNode         *node)
+{
+  GListModel *model;
+
+  if (node->empty)
+    return 0;
+  
+  if (node->model != NULL)
+    return 0;
+
+  model = tree_node_create_model (self, node);
+
+  if (model == NULL)
+    return 0;
+  
+  g_assert (g_list_model_get_item_type (model) == g_list_model_get_item_type (self->root_node.model));
+  gtk_tree_list_model_init_node (self, node, model);
+
+  tree_node_mark_dirty (node);
+  
+  return tree_node_get_n_children (node);
+}
+
+static void
+gtk_tree_list_model_collapse_node (GtkTreeListModel *self,
+                                   guint             position,
+                                   TreeNode         *node)
+{      
+  guint n_items;
+
+  if (node->model == NULL)
+    return;
+
+  n_items = tree_node_get_n_children (node);
+
+  g_clear_pointer (&node->children, gtk_css_rb_tree_unref);
+  g_clear_object (&node->model);
+
+  tree_node_mark_dirty (node);
+
+  if (n_items > 0)
+    g_list_model_items_changed (G_LIST_MODEL (self), position + 1, n_items, 0);
+}
+
+void
+gtk_tree_list_model_set_expanded (GtkTreeListModel *self,
+                                  guint             position,
+                                  gboolean          expanded)
+{
+  TreeNode *node;
+  guint n_items;
+
+  g_return_if_fail (GTK_IS_TREE_LIST_MODEL (self));
+
+  node = gtk_tree_list_model_get_nth (self, position);
+  if (node == NULL)
+    return;
+
+  if (expanded)
+    {
+      n_items = gtk_tree_list_model_expand_node (self, node);
+      if (n_items > 0)
+        g_list_model_items_changed (G_LIST_MODEL (self), position + 1, 0, n_items);
+    }
+  else
+    {
+      gtk_tree_list_model_collapse_node (self, position, node);
+    }
+}
+
+gboolean
+gtk_tree_list_model_get_expanded (GtkTreeListModel *self,
+                                  guint             position)
+{
+  TreeNode *node;
+
+  g_return_val_if_fail (GTK_IS_TREE_LIST_MODEL (self), FALSE);
+
+  node = gtk_tree_list_model_get_nth (self, position);
+  if (node == NULL)
+    return FALSE;
+
+  return node->children != NULL;
+}
+
+gboolean
+gtk_tree_list_model_is_expandable (GtkTreeListModel *self,
+                                   guint             position)
+{
+  GListModel *model;
+  TreeNode *node;
+
+  g_return_val_if_fail (GTK_IS_TREE_LIST_MODEL (self), FALSE);
+
+  node = gtk_tree_list_model_get_nth (self, position);
+  if (node == NULL)
+    return FALSE;
+
+  if (node->empty)
+    return FALSE;
+
+  if (node->model)
+    return TRUE;
+
+  model = tree_node_create_model (self, node);
+  if (model)
+    {
+      g_object_unref (model);
+      return TRUE;
+    }
+
+  return FALSE;
+}
+
diff --git a/gtk/gtktreelistmodel.h b/gtk/gtktreelistmodel.h
new file mode 100644
index 0000000000..59d6d77986
--- /dev/null
+++ b/gtk/gtktreelistmodel.h
@@ -0,0 +1,71 @@
+/*
+ * Copyright © 2018 Benjamin Otte
+ *
+ * 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.1 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/>.
+ *
+ * Authors: Benjamin Otte <otte@gnome.org>
+ */
+
+#ifndef __GTK_TREE_LIST_MODEL_H__
+#define __GTK_TREE_LIST_MODEL_H__
+
+
+#if !defined (__GTK_H_INSIDE__) && !defined (GTK_COMPILATION)
+#error "Only <gtk/gtk.h> can be included directly."
+#endif
+
+#include <gio/gio.h>
+#include <gtk/gtkwidget.h>
+
+
+G_BEGIN_DECLS
+
+#define GTK_TYPE_TREE_LIST_MODEL (gtk_tree_list_model_get_type ())
+
+GDK_AVAILABLE_IN_ALL
+G_DECLARE_FINAL_TYPE (GtkTreeListModel, gtk_tree_list_model, GTK, TREE_LIST_MODEL, GObject)
+
+typedef GListModel * (* GtkTreeListModelCreateModelFunc) (gpointer item, gpointer data);
+
+GDK_AVAILABLE_IN_ALL
+GtkTreeListModel *      gtk_tree_list_model_new                 (GListModel             *root,
+                                                                 gboolean                autoexpand,
+                                                                 GtkTreeListModelCreateModelFunc create_func,
+                                                                 gpointer                data,
+                                                                 GDestroyNotify          data_destroy);
+
+GDK_AVAILABLE_IN_ALL
+void                    gtk_tree_list_model_set_autoexpand      (GtkTreeListModel       *self,
+                                                                 gboolean                autoexpand);
+GDK_AVAILABLE_IN_ALL
+gboolean                gtk_tree_list_model_get_autoexpand      (GtkTreeListModel       *self);
+
+GDK_AVAILABLE_IN_ALL
+guint                   gtk_tree_list_model_get_depth           (GtkTreeListModel       *self,
+                                                                 guint                   position);
+GDK_AVAILABLE_IN_ALL
+void                    gtk_tree_list_model_set_expanded        (GtkTreeListModel       *self,
+                                                                 guint                   position,
+                                                                 gboolean                expanded);
+GDK_AVAILABLE_IN_ALL
+gboolean                gtk_tree_list_model_get_expanded        (GtkTreeListModel       *self,
+                                                                 guint                   position);
+GDK_AVAILABLE_IN_ALL
+gboolean                gtk_tree_list_model_is_expandable       (GtkTreeListModel       *self,
+                                                                 guint                   position);
+
+
+G_END_DECLS
+
+#endif /* __GTK_TREE_LIST_MODEL_H__ */
diff --git a/gtk/meson.build b/gtk/meson.build
index 92b811ee56..63d92174b5 100644
--- a/gtk/meson.build
+++ b/gtk/meson.build
@@ -79,6 +79,7 @@ gtk_private_sources = files([
   'gtkcssparser.c',
   'gtkcsspathnode.c',
   'gtkcsspositionvalue.c',
+  'gtkcssrbtree.c',
   'gtkcssrepeatvalue.c',
   'gtkcssrgbavalue.c',
   'gtkcssselector.c',
@@ -366,6 +367,7 @@ gtk_public_sources = files([
   'gtktooltip.c',
   'gtktooltipwindow.c',
   'gtktreednd.c',
+  'gtktreelistmodel.c',
   'gtktreemenu.c',
   'gtktreemodel.c',
   'gtktreemodelfilter.c',
@@ -587,6 +589,7 @@ gtk_public_headers = files([
   'gtktoolshell.h',
   'gtktooltip.h',
   'gtktreednd.h',
+  'gtktreelistmodel.h',
   'gtktreemodel.h',
   'gtktreemodelfilter.h',
   'gtktreemodelsort.h',
diff --git a/tests/meson.build b/tests/meson.build
index 16beab8d36..a6d6350662 100644
--- a/tests/meson.build
+++ b/tests/meson.build
@@ -112,6 +112,7 @@ gtk_tests = [
   ['testrevealer'],
   ['testrevealer2'],
   ['testtitlebar'],
+  ['testtreelistmodel'],
   ['testsplitheaders'],
   ['teststackedheaders'],
   ['testactionbar'],
diff --git a/tests/testtreelistmodel.c b/tests/testtreelistmodel.c
new file mode 100644
index 0000000000..e22b2bcec2
--- /dev/null
+++ b/tests/testtreelistmodel.c
@@ -0,0 +1,152 @@
+#include <gtk/gtk.h>
+
+static GListModel *
+create_list_model_for_directory (gpointer file,
+                                 gpointer unused)
+{
+  GFileEnumerator *enumerate;
+  GListStore *store;
+  GFile *child;
+  GFileInfo *info;
+
+  enumerate = g_file_enumerate_children (file,
+                                         G_FILE_ATTRIBUTE_STANDARD_TYPE
+                                         "," G_FILE_ATTRIBUTE_STANDARD_NAME,
+                                         0,
+                                         NULL,
+                                         NULL);
+  if (enumerate == NULL)
+    return NULL;
+
+  store = g_list_store_new (G_TYPE_FILE);
+
+  while (g_file_enumerator_iterate (enumerate, &info, NULL, NULL, NULL))
+    {
+      if (info == NULL)
+        break;
+
+      if (g_file_info_get_file_type (info) != G_FILE_TYPE_DIRECTORY)
+        continue;
+
+      child = g_file_get_child (file, g_file_info_get_name (info));
+      g_list_store_append (store, child);
+      g_object_unref (child);
+    }
+
+  g_object_unref (enumerate);
+
+  return G_LIST_MODEL (store);
+}
+
+static GtkTreeListModel *
+get_tree_list_model (GtkWidget *row)
+{
+  return GTK_TREE_LIST_MODEL (g_object_get_data (G_OBJECT (gtk_widget_get_parent (row)), "model"));
+}
+
+static void
+expand_clicked (GtkWidget *button,
+                GtkWidget *row)
+{
+  gtk_tree_list_model_set_expanded (get_tree_list_model (row),
+                                    gtk_list_box_row_get_index (GTK_LIST_BOX_ROW (row)),
+                                    TRUE);
+}
+
+static void
+collapse_clicked (GtkWidget *button,
+                GtkWidget *row)
+{
+  gtk_tree_list_model_set_expanded (get_tree_list_model (row),
+                                    gtk_list_box_row_get_index (GTK_LIST_BOX_ROW (row)),
+                                    FALSE);
+}
+
+static GtkWidget *
+create_widget_for_model (gpointer file,
+                         gpointer root)
+{
+  GtkWidget *row, *box, *child;
+  GFile *iter;
+  guint depth;
+
+  row = gtk_list_box_row_new ();
+
+  depth = 0;
+  for (iter = g_object_ref (g_file_get_parent (file));
+       !g_file_equal (root, iter);
+       g_set_object (&iter, g_file_get_parent (iter)))
+    {
+      g_object_unref (iter);
+      depth++;
+    }
+  g_object_unref (iter);
+  g_object_unref (iter);
+
+  box = gtk_box_new (GTK_ORIENTATION_HORIZONTAL, 0);
+  gtk_container_add (GTK_CONTAINER (row), box);
+
+  if (depth > 0)
+    {
+      child = gtk_box_new (GTK_ORIENTATION_HORIZONTAL, 0);
+      gtk_widget_set_size_request (child, 16 * depth, 0);
+      gtk_container_add (GTK_CONTAINER (box), child);
+    }
+
+  child = gtk_button_new_from_icon_name ("list-remove-symbolic");
+  gtk_button_set_relief (GTK_BUTTON (child), GTK_RELIEF_NONE);
+  g_signal_connect (child, "clicked", G_CALLBACK (collapse_clicked), row);
+  gtk_container_add (GTK_CONTAINER (box), child);
+
+  child = gtk_button_new_from_icon_name ("list-add-symbolic");
+  gtk_button_set_relief (GTK_BUTTON (child), GTK_RELIEF_NONE);
+  g_signal_connect (child, "clicked", G_CALLBACK (expand_clicked), row);
+  gtk_container_add (GTK_CONTAINER (box), child);
+
+  child = gtk_label_new (g_file_get_basename (file));
+  gtk_container_add (GTK_CONTAINER (box), child);
+
+  return row;
+}
+
+int
+main (int argc, char *argv[])
+{
+  GtkWidget *win;
+  GtkWidget *sw;
+  GtkWidget *listbox;
+  GListModel *model, *dirmodel;
+  GFile *root;
+
+  gtk_init ();
+
+  win = gtk_window_new (GTK_WINDOW_TOPLEVEL);
+  gtk_window_set_default_size (GTK_WINDOW (win), 400, 600);
+  g_signal_connect (win, "destroy", G_CALLBACK (gtk_main_quit), win);
+
+  sw = gtk_scrolled_window_new (NULL, NULL);
+  gtk_container_add (GTK_CONTAINER (win), sw);
+
+  listbox = gtk_list_box_new ();
+  gtk_container_add (GTK_CONTAINER (sw), listbox);
+
+  root = g_file_new_for_path (g_get_current_dir ());
+  dirmodel = create_list_model_for_directory (root, NULL);
+  model = G_LIST_MODEL (gtk_tree_list_model_new (dirmodel,
+                                                 FALSE,
+                                                 create_list_model_for_directory,
+                                                 NULL, NULL));
+  g_object_unref (dirmodel);
+  gtk_list_box_bind_model (GTK_LIST_BOX (listbox),
+                           model,
+                           create_widget_for_model,
+                           root, g_object_unref);
+  g_object_set_data (G_OBJECT (listbox), "model", model);
+  g_object_unref (model);
+
+  gtk_widget_show (win);
+
+  gtk_main ();
+
+  return 0;
+}
diff --git a/testsuite/gtk/meson.build b/testsuite/gtk/meson.build
index 296aca3206..963355cfbe 100644
--- a/testsuite/gtk/meson.build
+++ b/testsuite/gtk/meson.build
@@ -44,6 +44,7 @@ tests = [
   ['templates'],
   ['textbuffer'],
   ['textiter'],
+  ['treelistmodel'],
   ['treemodel', ['treemodel.c', 'liststore.c', 'treestore.c', 'filtermodel.c',
                  'modelrefcount.c', 'sortmodel.c', 'gtktreemodelrefcount.c']],
   ['treepath'],
diff --git a/testsuite/gtk/treelistmodel.c b/testsuite/gtk/treelistmodel.c
new file mode 100644
index 0000000000..af6683ab66
--- /dev/null
+++ b/testsuite/gtk/treelistmodel.c
@@ -0,0 +1,260 @@
+/* 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>
+
+static GQuark number_quark;
+static GQuark changes_quark;
+
+static guint
+get (GListModel *model,
+     guint       position)
+{
+  GObject *object = g_list_model_get_item (model, position);
+  g_assert (object != NULL);
+  return GPOINTER_TO_UINT (g_object_get_qdata (object, number_quark));
+}
+
+static char *
+model_to_string (GListModel *model)
+{
+  GString *string = g_string_new (NULL);
+  guint i;
+
+  for (i = 0; i < g_list_model_get_n_items (model); i++)
+    {
+      if (i > 0)
+        g_string_append (string, " ");
+      g_string_append_printf (string, "%u", get (model, i));
+    }
+
+  return g_string_free (string, FALSE);
+}
+
+static GListStore *
+new_store (guint start,
+           guint end,
+           guint step);
+
+static void
+prepend (GListStore *store,
+         guint       number,
+         guint       step)
+{
+  GObject *object;
+
+  /* 0 cannot be differentiated from NULL, so don't use it */
+  g_assert (number != 0);
+
+  if (step / 10)
+    object = G_OBJECT (new_store (number - 9 * step / 10, number, step / 10));
+  else
+    object = g_object_new (G_TYPE_OBJECT, NULL);
+  g_object_set_qdata (object, number_quark, GUINT_TO_POINTER (number));
+  g_list_store_insert (store, 0, object);
+  g_object_unref (object);
+}
+
+#define assert_model(model, expected) G_STMT_START{ \
+  char *s = model_to_string (G_LIST_MODEL (model)); \
+  if (!g_str_equal (s, expected)) \
+     g_assertion_message_cmpstr (G_LOG_DOMAIN, __FILE__, __LINE__, G_STRFUNC, \
+         #model " == " #expected, s, "==", expected); \
+  g_free (s); \
+}G_STMT_END
+
+#define assert_changes(model, expected) G_STMT_START{ \
+  GString *changes = g_object_get_qdata (G_OBJECT (model), changes_quark); \
+  if (!g_str_equal (changes->str, expected)) \
+     g_assertion_message_cmpstr (G_LOG_DOMAIN, __FILE__, __LINE__, G_STRFUNC, \
+         #model " == " #expected, changes->str, "==", expected); \
+  g_string_set_size (changes, 0); \
+}G_STMT_END
+
+static GListStore *
+new_empty_store (void)
+{
+  return g_list_store_new (G_TYPE_OBJECT);
+}
+
+static GListStore *
+new_store (guint start,
+           guint end,
+           guint step)
+{
+  GListStore *store = new_empty_store ();
+  guint i;
+
+  for (i = start; i <= end; i += step)
+    prepend (store, i, step);
+
+  return store;
+}
+
+static void
+items_changed (GListModel *model,
+               guint       position,
+               guint       removed,
+               guint       added,
+               GString    *changes)
+{
+  g_assert (removed != 0 || added != 0);
+
+  if (changes->len)
+    g_string_append (changes, ", ");
+
+  if (removed == 1 && added == 0)
+    {
+      g_string_append_printf (changes, "-%u", position);
+    }
+  else if (removed == 0 && added == 1)
+    {
+      g_string_append_printf (changes, "+%u", position);
+    }
+  else
+    {
+      g_string_append_printf (changes, "%u", position);
+      if (removed > 0)
+        g_string_append_printf (changes, "-%u", removed);
+      if (added > 0)
+        g_string_append_printf (changes, "+%u", added);
+    }
+}
+
+static void
+free_changes (gpointer data)
+{
+  GString *changes = data;
+
+  /* all changes must have been checked via assert_changes() before */
+  g_assert_cmpstr (changes->str, ==, "");
+
+  g_string_free (changes, TRUE);
+}
+
+static GListModel *
+create_sub_model_cb (gpointer item,
+                     gpointer unused)
+{
+  if (G_IS_LIST_MODEL (item))
+    return item;
+
+  return NULL;
+}
+
+static GtkTreeListModel *
+new_model (guint    size,
+           gboolean expanded)
+{
+  GtkTreeListModel *tree;
+  GString *changes;
+
+  tree = gtk_tree_list_model_new (G_LIST_MODEL (new_store (size, size, size)), expanded, create_sub_model_cb, NULL, NULL);
+  changes = g_string_new ("");
+  g_object_set_qdata_full (G_OBJECT(tree), changes_quark, changes, free_changes);
+  g_signal_connect (tree, "items-changed", G_CALLBACK (items_changed), changes);
+
+  return tree;
+}
+
+static void
+test_expand (void)
+{
+  GtkTreeListModel *tree = new_model (100, FALSE);
+  guint i;
+
+  assert_model (tree, "100");
+
+  for (i = g_list_model_get_n_items (G_LIST_MODEL (tree)); i > 0; i--)
+    {
+      gtk_tree_list_model_set_expanded (tree, i - 1, TRUE);
+    }
+  assert_model (tree, "100 100 90 80 70 60 50 40 30 20 10");
+  assert_changes (tree, "1+10");
+
+  for (i = g_list_model_get_n_items (G_LIST_MODEL (tree)); i > 0; i--)
+    {
+      gtk_tree_list_model_set_expanded (tree, i - 1, TRUE);
+    }
+  assert_model (tree, "100 100 100 99 98 97 96 95 94 93 92 91 90 90 89 88 87 86 85 84 83 82 81 80 80 79 78 77 76 75 74 73 72 71 70 70 69 68 67 66 65 64 63 62 61 60 60 59 58 57 56 55 54 53 52 51 50 50 49 48 47 46 45 44 43 42 41 40 40 39 38 37 36 35 34 33 32 31 30 30 29 28 27 26 25 24 23 22 21 20 20 19 18 17 16 15 14 13 12 11 10 10 9 8 7 6 5 4 3 2 1");
+  assert_changes (tree, "11+10, 10+10, 9+10, 8+10, 7+10, 6+10, 5+10, 4+10, 3+10, 2+10");
+
+  for (i = g_list_model_get_n_items (G_LIST_MODEL (tree)); i > 0; i--)
+    {
+      gtk_tree_list_model_set_expanded (tree, i - 1, TRUE);
+    }
+  assert_model (tree, "100 100 100 99 98 97 96 95 94 93 92 91 90 90 89 88 87 86 85 84 83 82 81 80 80 79 78 77 76 75 74 73 72 71 70 70 69 68 67 66 65 64 63 62 61 60 60 59 58 57 56 55 54 53 52 51 50 50 49 48 47 46 45 44 43 42 41 40 40 39 38 37 36 35 34 33 32 31 30 30 29 28 27 26 25 24 23 22 21 20 20 19 18 17 16 15 14 13 12 11 10 10 9 8 7 6 5 4 3 2 1");
+  assert_changes (tree, "");
+
+  g_object_unref (tree);
+}
+
+static void
+test_remove_some (void)
+{
+  GtkTreeListModel *tree = new_model (100, TRUE);
+  gpointer item;
+
+  assert_model (tree, "100 100 100 99 98 97 96 95 94 93 92 91 90 90 89 88 87 86 85 84 83 82 81 80 80 79 78 77 76 75 74 73 72 71 70 70 69 68 67 66 65 64 63 62 61 60 60 59 58 57 56 55 54 53 52 51 50 50 49 48 47 46 45 44 43 42 41 40 40 39 38 37 36 35 34 33 32 31 30 30 29 28 27 26 25 24 23 22 21 20 20 19 18 17 16 15 14 13 12 11 10 10 9 8 7 6 5 4 3 2 1");
+  assert_changes (tree, "");
+
+  item = g_list_model_get_item (G_LIST_MODEL (tree), 1);
+  g_assert (G_IS_LIST_MODEL (item));
+  g_list_store_remove (item, 3);
+  assert_model (tree, "100 100 100 99 98 96 95 94 93 92 91 90 90 89 88 87 86 85 84 83 82 81 80 80 79 78 77 76 75 74 73 72 71 70 70 69 68 67 66 65 64 63 62 61 60 60 59 58 57 56 55 54 53 52 51 50 50 49 48 47 46 45 44 43 42 41 40 40 39 38 37 36 35 34 33 32 31 30 30 29 28 27 26 25 24 23 22 21 20 20 19 18 17 16 15 14 13 12 11 10 10 9 8 7 6 5 4 3 2 1");
+  assert_changes (tree, "-5");
+
+  item = g_list_model_get_item (G_LIST_MODEL (tree), 0);
+  g_assert (G_IS_LIST_MODEL (item));
+  g_list_store_remove (item, 3);
+  assert_model (tree, "100 100 100 99 98 96 95 94 93 92 91 90 90 89 88 87 86 85 84 83 82 81 80 80 79 78 77 76 75 74 73 72 71 60 60 59 58 57 56 55 54 53 52 51 50 50 49 48 47 46 45 44 43 42 41 40 40 39 38 37 36 35 34 33 32 31 30 30 29 28 27 26 25 24 23 22 21 20 20 19 18 17 16 15 14 13 12 11 10 10 9 8 7 6 5 4 3 2 1");
+  assert_changes (tree, "33-11");
+
+  item = g_list_model_get_item (G_LIST_MODEL (tree), 88);
+  g_assert (G_IS_LIST_MODEL (item));
+  g_list_store_remove (item, 9);
+  assert_model (tree, "100 100 100 99 98 96 95 94 93 92 91 90 90 89 88 87 86 85 84 83 82 81 80 80 79 78 77 76 75 74 73 72 71 60 60 59 58 57 56 55 54 53 52 51 50 50 49 48 47 46 45 44 43 42 41 40 40 39 38 37 36 35 34 33 32 31 30 30 29 28 27 26 25 24 23 22 21 20 20 19 18 17 16 15 14 13 12 11 10 10 9 8 7 6 5 4 3 2");
+  assert_changes (tree, "-98");
+
+  item = g_list_model_get_item (G_LIST_MODEL (tree), 0);
+  g_assert (G_IS_LIST_MODEL (item));
+  g_list_store_remove (item, 8);
+  assert_model (tree, "100 100 100 99 98 96 95 94 93 92 91 90 90 89 88 87 86 85 84 83 82 81 80 80 79 78 77 76 75 74 73 72 71 60 60 59 58 57 56 55 54 53 52 51 50 50 49 48 47 46 45 44 43 42 41 40 40 39 38 37 36 35 34 33 32 31 30 30 29 28 27 26 25 24 23 22 21 20 20 19 18 17 16 15 14 13 12 11");
+  assert_changes (tree, "88-10");
+
+  g_object_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");
+
+  number_quark = g_quark_from_static_string ("Hell and fire was spawned to be released.");
+  changes_quark = g_quark_from_static_string ("What did I see? Can I believe what I saw?");
+
+  g_test_add_func ("/treelistmodel/expand", test_expand);
+  g_test_add_func ("/treelistmodel/remove_some", test_remove_some);
+
+  return g_test_run ();
+}