listitemmanager: Add a split vfunc and use it

Instead of randomly changing tiles, the listitemmanager gains a split
vfunc that listview and gridview implement so they can keep their tile
areas intact. The listitemmanager will now conform to these rules:

1. Never delete a tile.
   This ensures that all areas stay intact.

2. Never change the n_items of a tile other than setting them to 0.
   This causes "empty" areas to appear, but listview/gridview can
   easily check for them by checking for tile->n_items == 0.
   gtk_list_tile_gc() will get rid of them.

3. Adding items always creates new tiles that are added with empty area.
   That way they don't interrupt any existing machinery until the next
   allocation.

4. Adding/removing widgets has no effect on areas
   This is useful in particular when scrolling where new widgets are
   moving between tiles. When the manager moves the widgets, it may
   split some areas, but will not remove any existing tiles, so the
   whole area stays intact and the list can deal with further scroll
   events before an allocation.

This improve the situation for #3334

6 files changed, 201 insertions, 94 deletions

diff --git a/gtk/gtkgridview.c b/gtk/gtkgridview.c
index e5a440f74a..d067b8046a 100644
--- a/gtk/gtkgridview.c
+++ b/gtk/gtkgridview.c
@@ -152,6 +152,82 @@ dump (GtkGridView *self)
   g_print ("  => %u widgets in %u list rows\n", n_widgets, n_list_rows);
 }
 
+static GtkListTile *
+gtk_grid_view_split (GtkListBase *base,
+                     GtkListTile *tile,
+                     guint        n_items)
+{
+  GtkGridView *self = GTK_GRID_VIEW (base);
+  GtkListTile *split;
+  guint col, row_height;
+
+  row_height = tile->area.height / MAX (tile->n_items / self->n_columns, 1);
+
+  /* split off the multirow at the top */
+  if (n_items >= self->n_columns)
+    {
+      guint top_rows = n_items / self->n_columns;
+      guint top_items = top_rows * self->n_columns;
+
+      split = tile;
+      tile = gtk_list_tile_split (self->item_manager, tile, top_items);
+      gtk_list_tile_set_area (self->item_manager,
+                              tile,
+                              &(GdkRectangle) {
+                                split->area.x,
+                                split->area.y + row_height * top_rows,
+                                split->area.width,
+                                split->area.height - row_height * top_rows,
+                              });
+      gtk_list_tile_set_area_size (self->item_manager,
+                                   split,
+                                   split->area.width,
+                                   row_height * top_rows);
+      n_items -= top_items;
+      if (n_items == 0)
+        return tile;
+    }
+
+  /* split off the multirow at the bottom */
+  if (tile->n_items > self->n_columns)
+    {
+      split = gtk_list_tile_split (self->item_manager, tile, self->n_columns);
+      gtk_list_tile_set_area (self->item_manager,
+                              split,
+                              &(GdkRectangle) {
+                                tile->area.x,
+                                tile->area.y + row_height,
+                                tile->area.width,
+                                tile->area.height - row_height,
+                              });
+      gtk_list_tile_set_area_size (self->item_manager,
+                                   tile,
+                                   tile->area.width,
+                                   row_height);
+    }
+
+  g_assert (n_items < tile->n_items);
+  g_assert (tile->n_items <= self->n_columns);
+
+  /* now it's a single row, do a split at the column boundary */
+  col = tile->area.x / self->column_width;
+  split = gtk_list_tile_split (self->item_manager, tile, n_items);
+  gtk_list_tile_set_area (self->item_manager,
+                          split,
+                          &(GdkRectangle) {
+                            ceil ((col + n_items) * self->column_width),
+                            tile->area.y,
+                            ceil ((col + n_items + split->n_items) * self->column_width),
+                            tile->area.height,
+                          });
+  gtk_list_tile_set_area_size (self->item_manager,
+                               tile,
+                               ceil ((col + n_items) * self->column_width) - tile->area.x,
+                               tile->area.height);
+  
+  return split;
+}
+
 static gboolean
 gtk_grid_view_get_allocation_along (GtkListBase *base,
                                     guint        pos,
@@ -813,6 +889,7 @@ gtk_grid_view_class_init (GtkGridViewClass *klass)
 
   list_base_class->list_item_name = "child";
   list_base_class->list_item_role = GTK_ACCESSIBLE_ROLE_GRID_CELL;
+  list_base_class->split = gtk_grid_view_split;
   list_base_class->get_allocation_along = gtk_grid_view_get_allocation_along;
   list_base_class->get_allocation_across = gtk_grid_view_get_allocation_across;
   list_base_class->get_items_in_rect = gtk_grid_view_get_items_in_rect;
diff --git a/gtk/gtklistbase.c b/gtk/gtklistbase.c
index 0392abd37b..d4996d74a3 100644
--- a/gtk/gtklistbase.c
+++ b/gtk/gtklistbase.c
@@ -1870,6 +1870,14 @@ gtk_list_base_drag_leave (GtkDropControllerMotion *motion,
   remove_autoscroll (GTK_LIST_BASE (widget));
 }
 
+static GtkListTile *
+gtk_list_base_split_func (gpointer     data,
+                          GtkListTile *tile,
+                          guint        n_items)
+{
+  return GTK_LIST_BASE_GET_CLASS (data)->split (data, tile, n_items);
+}
+
 static void
 gtk_list_base_init_real (GtkListBase      *self,
                          GtkListBaseClass *g_class)
@@ -1879,7 +1887,9 @@ gtk_list_base_init_real (GtkListBase      *self,
 
   priv->item_manager = gtk_list_item_manager_new (GTK_WIDGET (self),
                                                   g_class->list_item_name,
-                                                  g_class->list_item_role);
+                                                  g_class->list_item_role,
+                                                  gtk_list_base_split_func,
+                                                  self);
   priv->anchor = gtk_list_item_tracker_new (priv->item_manager);
   priv->anchor_side_along = GTK_PACK_START;
   priv->anchor_side_across = GTK_PACK_START;
diff --git a/gtk/gtklistbaseprivate.h b/gtk/gtklistbaseprivate.h
index af70843c40..e6047a758c 100644
--- a/gtk/gtklistbaseprivate.h
+++ b/gtk/gtklistbaseprivate.h
@@ -37,6 +37,10 @@ struct _GtkListBaseClass
   const char *         list_item_name;
   GtkAccessibleRole    list_item_role;
 
+  GtkListTile *        (* split)                                (GtkListBase            *self,
+                                                                 GtkListTile            *tile,
+                                                                 guint                   n_items);
+
   void                 (* adjustment_value_changed)             (GtkListBase            *self,
                                                                  GtkOrientation          orientation);
   gboolean             (* get_allocation_along)                 (GtkListBase            *self,
diff --git a/gtk/gtklistitemmanager.c b/gtk/gtklistitemmanager.c
index a1e9e05595..d2ba9aaa10 100644
--- a/gtk/gtklistitemmanager.c
+++ b/gtk/gtklistitemmanager.c
@@ -39,6 +39,9 @@ struct _GtkListItemManager
 
   GtkRbTree *items;
   GSList *trackers;
+
+  GtkListTile * (* split_func) (gpointer, GtkListTile *, guint);
+  gpointer user_data;
 };
 
 struct _GtkListItemManagerClass
@@ -131,7 +134,9 @@ gtk_list_item_manager_clear_node (gpointer _tile)
 GtkListItemManager *
 gtk_list_item_manager_new (GtkWidget         *widget,
                            const char        *item_css_name,
-                           GtkAccessibleRole  item_role)
+                           GtkAccessibleRole  item_role,
+                           GtkListTile *      (* split_func) (gpointer, GtkListTile *, guint),
+                           gpointer           user_data)
 {
   GtkListItemManager *self;
 
@@ -143,6 +148,8 @@ gtk_list_item_manager_new (GtkWidget         *widget,
   self->widget = widget;
   self->item_css_name = g_intern_string (item_css_name);
   self->item_role = item_role;
+  self->split_func = split_func;
+  self->user_data = user_data;
 
   self->items = gtk_rb_tree_new_for_size (sizeof (GtkListTile),
                                           sizeof (GtkListTileAugment),
@@ -494,37 +501,47 @@ restart:
     }
 }
 
+static GtkListTile *
+gtk_list_item_manager_ensure_split (GtkListItemManager *self,
+                                    GtkListTile        *tile,
+                                    guint               n_items)
+{
+  return self->split_func (self->user_data, tile, n_items);
+}
+
 static void
 gtk_list_item_manager_remove_items (GtkListItemManager *self,
                                     GHashTable         *change,
                                     guint               position,
                                     guint               n_items)
 {
-  GtkListTile *tile;
+  GtkListTile *tile, *next;
+  guint offset;
 
   if (n_items == 0)
     return;
 
-  tile = gtk_list_item_manager_get_nth (self, position, NULL);
+  tile = gtk_list_item_manager_get_nth (self, position, &offset);
+  if (offset)
+    tile = gtk_list_item_manager_ensure_split (self, tile, offset);
 
   while (n_items > 0)
     {
       if (tile->n_items > n_items)
         {
-          tile->n_items -= n_items;
-          gtk_rb_tree_node_mark_dirty (tile);
-          n_items = 0;
-        }
-      else
-        {
-          GtkListTile *next = gtk_rb_tree_node_get_next (tile);
-          if (tile->widget)
-            gtk_list_item_manager_release_list_item (self, change, tile->widget);
-          tile->widget = NULL;
-          n_items -= tile->n_items;
-          gtk_rb_tree_remove (self->items, tile);
-          tile = next;
+          gtk_list_item_manager_ensure_split (self, tile, n_items);
+          g_assert (tile->n_items <= n_items);
         }
+
+      next = gtk_rb_tree_node_get_next (tile);
+      if (tile->widget)
+        gtk_list_item_manager_release_list_item (self, change, tile->widget);
+      tile->widget = NULL;
+      n_items -= tile->n_items;
+      tile->n_items = 0;
+      gtk_rb_tree_node_mark_dirty (tile);
+
+      tile = next;
     }
 
   gtk_widget_queue_resize (GTK_WIDGET (self->widget));
@@ -542,10 +559,11 @@ gtk_list_item_manager_add_items (GtkListItemManager *self,
     return;
 
   tile = gtk_list_item_manager_get_nth (self, position, &offset);
+  if (offset)
+    tile = gtk_list_item_manager_ensure_split (self, tile, offset);
 
-  if (tile == NULL || tile->widget)
-    tile = gtk_rb_tree_insert_before (self->items, tile);
-  tile->n_items += n_items;
+  tile = gtk_rb_tree_insert_before (self->items, tile);
+  tile->n_items = n_items;
   gtk_rb_tree_node_mark_dirty (tile);
 
   gtk_widget_queue_resize (GTK_WIDGET (self->widget));
@@ -645,7 +663,7 @@ static void
 gtk_list_item_manager_release_items (GtkListItemManager *self,
                                      GQueue             *released)
 {
-  GtkListTile *tile, *prev, *next;
+  GtkListTile *tile;
   guint position, i, n_items, query_n_items;
   gboolean tracked;
 
@@ -670,28 +688,9 @@ gtk_list_item_manager_release_items (GtkListItemManager *self,
             {
               g_queue_push_tail (released, tile->widget);
               tile->widget = NULL;
-              i++;
-              prev = gtk_rb_tree_node_get_previous (tile);
-              if (prev && gtk_list_item_manager_merge_list_items (self, prev, tile))
-                tile = prev;
-              next = gtk_rb_tree_node_get_next (tile);
-              if (next && next->widget == NULL)
-                {
-                  i += next->n_items;
-                  if (!gtk_list_item_manager_merge_list_items (self, next, tile))
-                    g_assert_not_reached ();
-                  tile = gtk_rb_tree_node_get_next (next);
-                }
-              else
-                {
-                  tile = next;
-                }
-            }
-          else
-            {
-              i += tile->n_items;
-              tile = gtk_rb_tree_node_get_next (tile);
             }
+          i += tile->n_items;
+          tile = gtk_rb_tree_node_get_next (tile);
         }
       position += query_n_items;
     }
@@ -702,7 +701,7 @@ gtk_list_item_manager_ensure_items (GtkListItemManager *self,
                                     GHashTable         *change,
                                     guint               update_start)
 {
-  GtkListTile *tile, *new_tile;
+  GtkListTile *tile, *other_tile;
   GtkWidget *widget, *insert_after;
   guint position, i, n_items, query_n_items, offset;
   GQueue released = G_QUEUE_INIT;
@@ -726,69 +725,60 @@ gtk_list_item_manager_ensure_items (GtkListItemManager *self,
         }
 
       tile = gtk_list_item_manager_get_nth (self, position, &offset);
-      for (new_tile = tile;
-           new_tile && new_tile->widget == NULL;
-           new_tile = gtk_rb_tree_node_get_previous (new_tile))
+      for (other_tile = tile;
+           other_tile && other_tile->widget == NULL;
+           other_tile = gtk_rb_tree_node_get_previous (other_tile))
          { /* do nothing */ }
-      insert_after = new_tile ? new_tile->widget : NULL;
+      insert_after = other_tile ? other_tile->widget : NULL;
 
       if (offset > 0)
-        {
-          g_assert (tile != NULL);
-          new_tile = gtk_rb_tree_insert_before (self->items, tile);
-          new_tile->n_items = offset;
-          tile->n_items -= offset;
-          gtk_rb_tree_node_mark_dirty (tile);
-        }
+        tile = gtk_list_item_manager_ensure_split (self, tile, offset);
 
       for (i = 0; i < query_n_items; i++)
         {
           g_assert (tile != NULL);
+
+          while (tile->n_items == 0)
+            tile = gtk_rb_tree_node_get_next (tile);
+
           if (tile->n_items > 1)
-            {
-              new_tile = gtk_rb_tree_insert_before (self->items, tile);
-              new_tile->n_items = 1;
-              tile->n_items--;
-              gtk_rb_tree_node_mark_dirty (tile);
-            }
-          else
-            {
-              new_tile = tile;
-              tile = gtk_rb_tree_node_get_next (tile);
-            }
-          if (new_tile->widget == NULL)
+            gtk_list_item_manager_ensure_split (self, tile, 1);
+
+          if (tile->widget == NULL)
             {
               if (change)
                 {
-                  new_tile->widget = gtk_list_item_manager_try_reacquire_list_item (self,
-                                                                                    change,
-                                                                                    position + i,
-                                                                                    insert_after);
+                  tile->widget = gtk_list_item_manager_try_reacquire_list_item (self,
+                                                                                change,
+                                                                                position + i,
+                                                                                insert_after);
                 }
-              if (new_tile->widget == NULL)
+              if (tile->widget == NULL)
                 {
-                  new_tile->widget = g_queue_pop_head (&released);
-                  if (new_tile->widget)
+                  tile->widget = g_queue_pop_head (&released);
+                  if (tile->widget)
                     {
                       gtk_list_item_manager_move_list_item (self,
-                                                            new_tile->widget,
+                                                            tile->widget,
                                                             position + i,
                                                             insert_after);
                     }
                   else
                     {
-                      new_tile->widget = gtk_list_item_manager_acquire_list_item (self,
-                                                                                  position + i,
-                                                                                  insert_after);
+                      tile->widget = gtk_list_item_manager_acquire_list_item (self,
+                                                                              position + i,
+                                                                              insert_after);
                     }
                 }
             }
           else
             {
               if (update_start <= position + i)
-                gtk_list_item_manager_update_list_item (self, new_tile->widget, position + i);
+                gtk_list_item_manager_update_list_item (self, tile->widget, position + i);
             }
-          insert_after = new_tile->widget;
+          insert_after = tile->widget;
+
+          tile = gtk_rb_tree_node_get_next (tile);
         }
       position += query_n_items;
     }
@@ -858,27 +848,22 @@ gtk_list_item_manager_model_items_changed_cb (GListModel         *model,
               continue;
             }
 
+          while (offset >= tile->n_items)
+            {
+              offset -= tile->n_items;
+              tile = gtk_rb_tree_node_get_next (tile);
+            }
           if (offset > 0)
             {
-              new_tile = gtk_rb_tree_insert_before (self->items, tile);
-              new_tile->n_items = offset;
-              tile->n_items -= offset;
+              tile = gtk_list_item_manager_ensure_split (self, tile, offset);
               offset = 0;
-              gtk_rb_tree_node_mark_dirty (tile);
             }
 
+          new_tile = tile;
           if (tile->n_items == 1)
-            {
-              new_tile = tile;
-              tile = gtk_rb_tree_node_get_next (tile);
-            }
+            tile = gtk_rb_tree_node_get_next (tile);
           else
-            {
-              new_tile = gtk_rb_tree_insert_before (self->items, tile);
-              new_tile->n_items = 1;
-              tile->n_items--;
-              gtk_rb_tree_node_mark_dirty (tile);
-            }
+            tile = gtk_list_item_manager_ensure_split (self, tile, 1);
 
           new_tile->widget = widget;
           insert_after = widget;
diff --git a/gtk/gtklistitemmanagerprivate.h b/gtk/gtklistitemmanagerprivate.h
index 14d058a377..6dcbfc21ce 100644
--- a/gtk/gtklistitemmanagerprivate.h
+++ b/gtk/gtklistitemmanagerprivate.h
@@ -63,7 +63,9 @@ GType                   gtk_list_item_manager_get_type          (void) G_GNUC_CO
 
 GtkListItemManager *    gtk_list_item_manager_new               (GtkWidget              *widget,
                                                                  const char             *item_css_name,
-                                                                 GtkAccessibleRole       item_role);
+                                                                 GtkAccessibleRole       item_role,
+                                                                 GtkListTile *           (* split_func) (gpointer, GtkListTile *, guint),
+                                                                 gpointer                user_data);
 
 void                    gtk_list_item_manager_get_tile_bounds   (GtkListItemManager     *self,
                                                                  GdkRectangle           *out_bounds);
diff --git a/gtk/gtklistview.c b/gtk/gtklistview.c
index 4f88338f1e..3c939da806 100644
--- a/gtk/gtklistview.c
+++ b/gtk/gtklistview.c
@@ -200,6 +200,34 @@ gtk_list_view_get_list_height (GtkListView *self)
   return aug->area.height;
 }
 
+static GtkListTile *
+gtk_list_view_split (GtkListBase *base,
+                     GtkListTile *tile,
+                     guint        n_items)
+{
+  GtkListView *self = GTK_LIST_VIEW (base);
+  GtkListTile *new_tile;
+  guint row_height;
+
+  row_height = tile->area.height / tile->n_items;
+
+  new_tile = gtk_list_tile_split (self->item_manager, tile, n_items);
+  gtk_list_tile_set_area_size (self->item_manager,
+                               tile,
+                               tile->area.width,
+                               row_height * tile->n_items);
+  gtk_list_tile_set_area (self->item_manager,
+                          new_tile,
+                          &(GdkRectangle) {
+                            tile->area.x,
+                            tile->area.y + tile->area.height,
+                            tile->area.width,
+                            row_height * new_tile->n_items
+                          });
+
+  return new_tile;
+}
+
 static gboolean
 gtk_list_view_get_allocation_along (GtkListBase *base,
                                     guint        pos,
@@ -663,6 +691,7 @@ gtk_list_view_class_init (GtkListViewClass *klass)
 
   list_base_class->list_item_name = "row";
   list_base_class->list_item_role = GTK_ACCESSIBLE_ROLE_LIST_ITEM;
+  list_base_class->split = gtk_list_view_split;
   list_base_class->get_allocation_along = gtk_list_view_get_allocation_along;
   list_base_class->get_allocation_across = gtk_list_view_get_allocation_across;
   list_base_class->get_items_in_rect = gtk_list_view_get_items_in_rect;