[gtk/wip/otte/bitset] listbase: Compute rubberband region on-demand

[Benjamin Otte <otte src gnome org>]

commit 61514327a5773c74b81d4cdbd1393cd38c4bf11b
Author: Benjamin Otte <otte redhat com>
Date:   Fri Jun 26 02:56:38 2020 +0200

    listbase: Compute rubberband region on-demand
    
    Instead of storing the active items as we go, compute the affected items
    whenever the rubberband changes and in particular when the rubberband
    ends.
    That way, the rubberband is guaranteed to select a rectangle even
    after scrolling very far.
    
    This is achieved by having a get_items_in_rect() vfunc that selects all
    the items in the rubberbanded rectangle and returns them as a bitset.

 gtk/gtkgridview.c        |  32 ++++++++++++
 gtk/gtklistbase.c        | 133 +++++++++++++++++++++++++++--------------------
 gtk/gtklistbaseprivate.h |   2 +
 gtk/gtklistview.c        |  32 ++++++++++++
 4 files changed, 144 insertions(+), 55 deletions(-)
---
diff --git a/gtk/gtkgridview.c b/gtk/gtkgridview.c
index ac3d49cdda..3a1b96098e 100644
--- a/gtk/gtkgridview.c
+++ b/gtk/gtkgridview.c
@@ -21,6 +21,7 @@
 
 #include "gtkgridview.h"
 
+#include "gtkbitset.h"
 #include "gtkintl.h"
 #include "gtklistbaseprivate.h"
 #include "gtklistitemfactory.h"
@@ -452,6 +453,36 @@ gtk_grid_view_get_position_from_allocation (GtkListBase           *base,
   return TRUE;
 }
 
+static GtkBitset *
+gtk_grid_view_get_items_in_rect (GtkListBase        *base,
+                                 const GdkRectangle *rect)
+{
+  GtkGridView *self = GTK_GRID_VIEW (base);
+  guint first_row, last_row, first_column, last_column, n_items;
+  GtkBitset *result;
+
+  result = gtk_bitset_new_empty ();
+
+  n_items = gtk_list_base_get_n_items (base);
+  if (n_items == 0)
+    return result;
+
+  first_column = floor (rect->x / self->column_width);
+  last_column = floor ((rect->x + rect->width) / self->column_width);
+  if (!gtk_grid_view_get_cell_at_y (self, rect->y, &first_row, NULL, NULL))
+    first_row = rect->y < 0 ? 0 : n_items - 1;
+  if (!gtk_grid_view_get_cell_at_y (self, rect->y + rect->height, &last_row, NULL, NULL))
+    last_row = rect->y < 0 ? 0 : n_items - 1;
+
+  gtk_bitset_add_rectangle (result,
+                            first_row + first_column,
+                            last_column - first_column + 1,
+                            (last_row - first_row) / self->n_columns + 1,
+                            self->n_columns);
+
+  return result;
+}
+
 static guint
 gtk_grid_view_move_focus_along (GtkListBase *base,
                                 guint        pos,
@@ -1000,6 +1031,7 @@ gtk_grid_view_class_init (GtkGridViewClass *klass)
   list_base_class->list_item_augment_func = cell_augment;
   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;
   list_base_class->get_position_from_allocation = gtk_grid_view_get_position_from_allocation;
   list_base_class->move_focus_along = gtk_grid_view_move_focus_along;
   list_base_class->move_focus_across = gtk_grid_view_move_focus_across;
diff --git a/gtk/gtklistbase.c b/gtk/gtklistbase.c
index 7c4af31cb7..19bb54b2d2 100644
--- a/gtk/gtklistbase.c
+++ b/gtk/gtklistbase.c
@@ -47,7 +47,6 @@ struct _RubberbandData
   double              start_align_across;       /* alignment in horizontal direction */
   double              start_align_along;        /* alignment in vertical direction */
 
-  GtkBitset *active;
   double pointer_x, pointer_y;                  /* mouse coordinates in widget space */
   gboolean modify;
   gboolean extend;
@@ -1235,8 +1234,6 @@ gtk_list_base_class_init (GtkListBaseClass *klass)
   gtk_widget_class_add_binding_action (widget_class, GDK_KEY_backslash, GDK_CONTROL_MASK, 
"list.unselect-all", NULL);
 }
 
-static void gtk_list_base_update_rubberband_selection (GtkListBase *self);
-
 static gboolean
 autoscroll_cb (GtkWidget     *widget,
                GdkFrameClock *frame_clock,
@@ -1430,16 +1427,22 @@ gtk_list_base_widget_to_list (GtkListBase *self,
     }
 }
 
-void
-gtk_list_base_allocate_rubberband (GtkListBase *self)
+static GtkBitset *
+gtk_list_base_get_items_in_rect (GtkListBase        *self,
+                                 const GdkRectangle *rect)
+{
+  return GTK_LIST_BASE_GET_CLASS (self)->get_items_in_rect (self, rect);
+}
+
+static gboolean
+gtk_list_base_get_rubberband_coords (GtkListBase  *self,
+                                     GdkRectangle *rect)
 {
   GtkListBasePrivate *priv = gtk_list_base_get_instance_private (self);
-  GtkRequisition min_size;
   int x1, x2, y1, y2;
-  int offset_x, offset_y;
 
   if (!priv->rubberband)
-    return;
+    return FALSE;
 
   if (priv->rubberband->start_tracker == NULL)
     {
@@ -1467,17 +1470,37 @@ gtk_list_base_allocate_rubberband (GtkListBase *self)
                                 priv->rubberband->pointer_x, priv->rubberband->pointer_y,
                                 &x2, &y2);
 
+  rect->x = MIN (x1, x2);
+  rect->y = MIN (y1, y2);
+  rect->width = ABS (x1 - x2) + 1;
+  rect->height = ABS (y1 - y2) + 1;
+
+  return TRUE;
+}
+
+void
+gtk_list_base_allocate_rubberband (GtkListBase *self)
+{
+  GtkListBasePrivate *priv = gtk_list_base_get_instance_private (self);
+  GtkRequisition min_size;
+  GdkRectangle rect;
+  int offset_x, offset_y;
+
+  if (!gtk_list_base_get_rubberband_coords (self, &rect))
+    return;
+
   gtk_widget_get_preferred_size (priv->rubberband->widget, &min_size, NULL);
+  rect.width = MAX (min_size.width, rect.width);
+  rect.height = MAX (min_size.height, rect.height);
 
   gtk_list_base_get_adjustment_values (self, OPPOSITE_ORIENTATION (priv->orientation), &offset_x, NULL, 
NULL);
   gtk_list_base_get_adjustment_values (self, priv->orientation, &offset_y, NULL, NULL);
+  rect.x -= offset_x;
+  rect.y -= offset_y;
 
   gtk_list_base_size_allocate_child (self,
                                      priv->rubberband->widget,
-                                     MIN (x1, x2) - offset_x,
-                                     MIN (y1, y2) - offset_y,
-                                     MAX (min_size.width, ABS (x1 - x2) + 1),
-                                     MAX (min_size.height, ABS (y1 - y2) + 1));
+                                     rect.x, rect.y, rect.width, rect.height);
 }
 
 static void
@@ -1518,7 +1541,6 @@ gtk_list_base_start_rubberband (GtkListBase *self,
   priv->rubberband->widget = gtk_gizmo_new ("rubberband",
                                             NULL, NULL, NULL, NULL, NULL, NULL);
   gtk_widget_set_parent (priv->rubberband->widget, GTK_WIDGET (self));
-  priv->rubberband->active = gtk_bitset_new_empty ();
 }
 
 static void
@@ -1543,10 +1565,17 @@ gtk_list_base_stop_rubberband (GtkListBase *self)
   if (model != NULL)
     {
       GtkBitset *selected, *mask;
+      GdkRectangle rect;
+      GtkBitset *rubberband_selection;
+
+      if (!gtk_list_base_get_rubberband_coords (self, &rect))
+        return;
+
+      rubberband_selection = gtk_list_base_get_items_in_rect (self, &rect);
 
       if (priv->rubberband->extend)
         {
-          mask = gtk_bitset_ref (priv->rubberband->active);
+          mask = gtk_bitset_ref (rubberband_selection);
         }
       else
         {
@@ -1557,80 +1586,74 @@ gtk_list_base_stop_rubberband (GtkListBase *self)
       if (priv->rubberband->modify)
         selected = gtk_bitset_new_empty ();
       else
-        selected = gtk_bitset_ref (priv->rubberband->active);
+        selected = gtk_bitset_ref (rubberband_selection);
 
       gtk_selection_model_set_selection (model, selected, mask);
 
       gtk_bitset_unref (selected);
       gtk_bitset_unref (mask);
+      gtk_bitset_unref (rubberband_selection);
     }
 
   gtk_list_item_tracker_free (priv->item_manager, priv->rubberband->start_tracker);
   g_clear_pointer (&priv->rubberband->widget, gtk_widget_unparent);
-  g_clear_pointer (&priv->rubberband->active, gtk_bitset_unref);
   g_free (priv->rubberband);
   priv->rubberband = NULL;
 
   remove_autoscroll (self);
-
-  gtk_widget_queue_draw (GTK_WIDGET (self));
 }
 
 static void
-gtk_list_base_update_rubberband (GtkListBase *self,
-                                 double       x,
-                                 double       y)
+gtk_list_base_update_rubberband_selection (GtkListBase *self)
 {
   GtkListBasePrivate *priv = gtk_list_base_get_instance_private (self);
+  GtkListItemManagerItem *item;
+  GdkRectangle rect;
+  guint pos;
+  GtkBitset *rubberband_selection;
 
-  if (!priv->rubberband)
+  if (!gtk_list_base_get_rubberband_coords (self, &rect))
     return;
 
-  priv->rubberband->pointer_x = x;
-  priv->rubberband->pointer_y = y;
-
-  gtk_list_base_update_rubberband_selection (self);
+  rubberband_selection = gtk_list_base_get_items_in_rect (self, &rect);
 
-  update_autoscroll (self, x, y);
+  pos = 0;
+  for (item = gtk_list_item_manager_get_first (priv->item_manager);
+       item != NULL;
+       item = gtk_rb_tree_node_get_next (item))
+    {
+      if (item->widget)
+        {
+          if (gtk_bitset_contains (rubberband_selection, pos))
+            gtk_widget_set_state_flags (item->widget, GTK_STATE_FLAG_ACTIVE, FALSE);
+          else
+            gtk_widget_unset_state_flags (item->widget, GTK_STATE_FLAG_ACTIVE);
+        }
+      
+      pos += item->n_items;
+    }
 
-  gtk_widget_queue_draw (GTK_WIDGET (self));
+  gtk_bitset_unref (rubberband_selection);
 }
 
 static void
-gtk_list_base_update_rubberband_selection (GtkListBase *self)
+gtk_list_base_update_rubberband (GtkListBase *self,
+                                 double       x,
+                                 double       y)
 {
   GtkListBasePrivate *priv = gtk_list_base_get_instance_private (self);
-  GdkRectangle rect;
-  GdkRectangle alloc;
-  GtkListItemManagerItem *item;
 
-  gtk_list_base_allocate_rubberband (self);
-  gtk_widget_get_allocation (priv->rubberband->widget, &rect);
-
-  for (item = gtk_list_item_manager_get_first (priv->item_manager);
-       item != NULL;
-       item = gtk_rb_tree_node_get_next (item))
-    {
-      guint pos;
+  if (!priv->rubberband)
+    return;
 
-      if (!item->widget)
-        continue;
+  priv->rubberband->pointer_x = x;
+  priv->rubberband->pointer_y = y;
 
-      pos = gtk_list_item_manager_get_item_position (priv->item_manager, item);
+  gtk_list_base_update_rubberband_selection (self);
 
-      gtk_widget_get_allocation (item->widget, &alloc);
+  update_autoscroll (self, x, y);
 
-      if (gdk_rectangle_intersect (&rect, &alloc, &alloc))
-        {
-          gtk_bitset_add (priv->rubberband->active, pos);
-          gtk_widget_set_state_flags (item->widget, GTK_STATE_FLAG_ACTIVE, FALSE);
-        }
-      else
-        {
-          gtk_bitset_remove (priv->rubberband->active, pos);
-          gtk_widget_unset_state_flags (item->widget, GTK_STATE_FLAG_ACTIVE);
-        }
-    }
+  gtk_widget_queue_allocate (GTK_WIDGET (self));
 }
 
 static void
diff --git a/gtk/gtklistbaseprivate.h b/gtk/gtklistbaseprivate.h
index 87df14d2d2..c714c63c0c 100644
--- a/gtk/gtklistbaseprivate.h
+++ b/gtk/gtklistbaseprivate.h
@@ -54,6 +54,8 @@ struct _GtkListBaseClass
                                                                  int                     along,
                                                                  guint                  *pos,
                                                                  cairo_rectangle_int_t  *area);
+  GtkBitset *          (* get_items_in_rect)                    (GtkListBase            *self,
+                                                                 const cairo_rectangle_int_t *rect);
   guint                (* move_focus_along)                     (GtkListBase            *self,
                                                                  guint                   pos,
                                                                  int                     steps);
diff --git a/gtk/gtklistview.c b/gtk/gtklistview.c
index 3bffebdeea..4139e071c3 100644
--- a/gtk/gtklistview.c
+++ b/gtk/gtklistview.c
@@ -21,6 +21,7 @@
 
 #include "gtklistview.h"
 
+#include "gtkbitset.h"
 #include "gtkintl.h"
 #include "gtklistbaseprivate.h"
 #include "gtklistitemmanagerprivate.h"
@@ -374,6 +375,36 @@ gtk_list_view_get_allocation_across (GtkListBase *base,
   return TRUE;
 }
 
+static GtkBitset *
+gtk_list_view_get_items_in_rect (GtkListBase                 *base,
+                                 const cairo_rectangle_int_t *rect)
+{
+  GtkListView *self = GTK_LIST_VIEW (base);
+  guint first, last, n_items;
+  GtkBitset *result;
+  ListRow *row;
+
+  result = gtk_bitset_new_empty ();
+
+  n_items = gtk_list_base_get_n_items (base);
+  if (n_items == 0)
+    return result;
+
+  row = gtk_list_view_get_row_at_y (self, rect->y, NULL);
+  if (row)
+    first = gtk_list_item_manager_get_item_position (self->item_manager, row);
+  else
+    first = rect->y < 0 ? 0 : n_items - 1;
+  row = gtk_list_view_get_row_at_y (self, rect->y + rect->height, NULL);
+  if (row)
+    last = gtk_list_item_manager_get_item_position (self->item_manager, row);
+  else
+    last = rect->y < 0 ? 0 : n_items - 1;
+
+  gtk_bitset_add_range_closed (result, first, last);
+  return result;
+}
+
 static guint
 gtk_list_view_move_focus_along (GtkListBase *base,
                                 guint        pos,
@@ -773,6 +804,7 @@ gtk_list_view_class_init (GtkListViewClass *klass)
   list_base_class->list_item_augment_func = list_row_augment;
   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;
   list_base_class->get_position_from_allocation = gtk_list_view_get_position_from_allocation;
   list_base_class->move_focus_along = gtk_list_view_move_focus_along;
   list_base_class->move_focus_across = gtk_list_view_move_focus_across;