a11y: Use a DOM-like API for iterating accessible objects

The `get_child_at_index()` API model comes from AT-SPI, and it's not an
efficient design, especially when coupled with large widgets.

Replace `get_child_at_index()` with `get_first_accessible_child()` and
`get_next_accessible_sibling()`.

That allows efficiently retrieving all the children, simplifies the
implementation of GtkAccessible in GtkWidget and closely resembeles the
GtkWidget API.

Getting the last child and previous sibling for iterating backwards is
not a part of the interface at the moment, but they can be added at a
later date.

Note that this change required tracking the next stack page in
GtkStackPage.

5 files changed, 111 insertions, 68 deletions

diff --git a/gtk/a11y/gtkatspicontext.c b/gtk/a11y/gtkatspicontext.c
index 82f88627fa..0643ed6089 100644
--- a/gtk/a11y/gtkatspicontext.c
+++ b/gtk/a11y/gtkatspicontext.c
@@ -337,23 +337,19 @@ get_index_in (GtkAccessible *parent,
               GtkAccessible *child)
 {
   GtkAccessible *candidate;
-  int res;
-  int idx;
+  guint res;
 
   if (parent == NULL)
     return -1;
 
-  idx = 0;
   res = 0;
-  while (true)
+for (candidate = gtk_accessible_get_first_accessible_child (parent);
+       candidate != NULL;
+       candidate = gtk_accessible_get_next_accessible_sibling (candidate))
     {
-      candidate = gtk_accessible_get_child_at_index (parent, idx);
-      if (!candidate)
-        break;
       if (candidate == child)
         return res;
 
-      idx++;
       if (!gtk_accessible_should_present (candidate))
         continue;
 
@@ -497,7 +493,7 @@ handle_accessible_method (GDBusConnection       *connection,
     {
       GtkATContext *context = NULL;
       GtkAccessible *accessible;
-      int idx, presentable_idx, child_idx;
+      int idx, presentable_idx;
 
       g_variant_get (parameters, "(i)", &idx);
 
@@ -506,11 +502,10 @@ handle_accessible_method (GDBusConnection       *connection,
       GtkAccessible *child;
 
       presentable_idx = 0;
-      child_idx = 0;
-      do
+      for (child = gtk_accessible_get_first_accessible_child (accessible);
+           child != NULL;
+           child = gtk_accessible_get_next_accessible_sibling (child))
         {
-          child = gtk_accessible_get_child_at_index (accessible, child_idx);
-          child_idx += 1;
           if (!gtk_accessible_should_present (child))
               continue;
 
@@ -519,8 +514,6 @@ handle_accessible_method (GDBusConnection       *connection,
           presentable_idx++;
 
         }
-      while (child != NULL);
-
       if (child)
         {
           context = gtk_accessible_get_at_context (child);
@@ -549,13 +542,10 @@ handle_accessible_method (GDBusConnection       *connection,
       GtkAccessible *accessible = gtk_at_context_get_accessible (GTK_AT_CONTEXT (self));
 
       GtkAccessible *child;
-      guint idx = 0;
-
-      while (true)
-        {
-          child = gtk_accessible_get_child_at_index (accessible, idx);
-          if(!child)
-            break;
+      for (child = gtk_accessible_get_first_accessible_child (accessible);
+           child != NULL;
+           child = gtk_accessible_get_next_accessible_sibling (child))
+      {
           if (!gtk_accessible_should_present (child))
             continue;
 
@@ -1708,16 +1698,13 @@ gtk_at_spi_context_get_child_count (GtkAtSpiContext *self)
 
   GtkAccessible *accessible = gtk_at_context_get_accessible (GTK_AT_CONTEXT (self));
   int n_children = 0;
-  int idx = 0;
-  
-  GtkAccessible *child;
 
-  while (true)
+  GtkAccessible *child = NULL;
+
+  for (child = gtk_accessible_get_first_accessible_child (accessible);
+       child != NULL;
+       child = gtk_accessible_get_next_accessible_sibling (child))
     {
-      child = gtk_accessible_get_child_at_index (accessible, idx);
-      if (!child)
-        break;
-      idx++;
       if (!gtk_accessible_should_present (child))
         continue;
 
diff --git a/gtk/gtkaccessible.c b/gtk/gtkaccessible.c
index b9101a79d3..a029d09f81 100644
--- a/gtk/gtkaccessible.c
+++ b/gtk/gtkaccessible.c
@@ -40,8 +40,8 @@
  *
  * Every accessible implementation is part of a tree of accessible objects.
  * Normally, this tree corresponds to the widget tree, but can be customized
- * by reimplementing the [vfunc@Gtk.Accessible.get_accessible_parent]
- * and [vfunc@Gtk.Accessible.get_child_at_index] virtual functions.
+ * by reimplementing the [vfunc@Gtk.Accessible.get_accessible_parent],
+ * [vfunc@Gtk.Accessible.get_first_accessible_child] and [vfunc@Gtk.Accessible.get_next_accessible_sibling] virtual functions.
  * Note that you can not create a top-level accessible object as of now,
  * which means that you must always have a parent accessible object.
  */
@@ -115,22 +115,39 @@ gtk_accessible_get_accessible_parent (GtkAccessible *self)
 
 
 /**
- * gtk_accessible_get_child_at_index:
+ * gtk_accessible_get_first_accessible_child:
  * @self: a `GtkAccessible`
- * @idx: the index of the child to get
  *
- * Retrieves the child `GtkAccessible` for this `GtkAccessible` with the given @index.
+ * Retrieves the first child `GtkAccessible` for this `GtkAccessible`.
  *
- * Returns: (transfer none) (nullable): the child `GtkAccessible` with the given @index or %NULL if the index is outside range
+ * Returns: (transfer none) (nullable): the first `GtkAccessible` child of @self, if @self has accessible children, %NULL otherwise
  *
  * since: 4.10
  */
 GtkAccessible *
-gtk_accessible_get_child_at_index (GtkAccessible *self, guint idx)
+gtk_accessible_get_first_accessible_child (GtkAccessible *self)
 {
   g_return_val_if_fail (GTK_IS_ACCESSIBLE (self), NULL);
 
-  return GTK_ACCESSIBLE_GET_IFACE (self)->get_child_at_index (self, idx);
+  return GTK_ACCESSIBLE_GET_IFACE (self)->get_first_accessible_child (self);
+}
+
+/**
+ * gtk_accessible_get_next_accessible_sibling:
+ * @self: a `GtkAccessible`
+ *
+ * Retrieves the next `GtkAccessible` sibling of this `GtkAccessible`.
+ *
+ * Returns: (transfer none) (nullable): the next `GtkAccessible` sibling of @self, if @self has a next sibling, %NULL otherwise
+ *
+ * since: 4.10
+ */
+GtkAccessible *
+gtk_accessible_get_next_accessible_sibling (GtkAccessible *self)
+{
+  g_return_val_if_fail (GTK_IS_ACCESSIBLE (self), NULL);
+
+  return GTK_ACCESSIBLE_GET_IFACE (self)->get_next_accessible_sibling (self);
 }
 
 /**
diff --git a/gtk/gtkaccessible.h b/gtk/gtkaccessible.h
index a557d49fec..4146a8d57e 100644
--- a/gtk/gtkaccessible.h
+++ b/gtk/gtkaccessible.h
@@ -100,20 +100,28 @@ struct _GtkAccessibleInterface
    * @self: a `GtkAccessible`
    * 
    * Returns the parent `GtkAccessible` of @self.
-   * Be sure not to return %NULL, as a top-level `GtkAccessible` which is not a
-   * top-level window is not supported.
+   * A return value of %NULL implies that the accessible represents a top-level
+   * accessible object, which currently also implies that the accessible
+   * represents something which is in the list of top-level widgets.
    */
   GtkAccessible *       (* get_accessible_parent)  (GtkAccessible *self);
   
   /**
-   * GtkaccessibleInterface::get_child_at_index:
+   * GtkaccessibleInterface::get_first_accessible_child:
    * @self: a `GtkAccessible`
-   * @idx: the index of the child
    * 
-   * Returns the child of @self whose position corresponds to @index.
-   * If @index is not valid for @self's children, return -1.
+   * Returns the first accessible child of @self, or %NULL if @self has none
    */
-  GtkAccessible *       (* get_child_at_index)  (GtkAccessible *self, guint idx);
+  GtkAccessible *       (* get_first_accessible_child)  (GtkAccessible *self);
+
+
+  /**
+   * GtkaccessibleInterface::get_next_accessible_sibling:
+   * @self: a `GtkAccessible`
+   * 
+   * Returns the next accessible sibling of @self, or %NULL if @self has none
+   */
+  GtkAccessible *       (* get_next_accessible_sibling)  (GtkAccessible *self);
 
   /**
    * GtkAccessibleInterface::get_bounds:
@@ -142,7 +150,10 @@ GDK_AVAILABLE_IN_4_10
 GtkAccessible * gtk_accessible_get_accessible_parent(GtkAccessible *self);
 
 GDK_AVAILABLE_IN_4_10
-GtkAccessible * gtk_accessible_get_child_at_index(GtkAccessible *self, guint idx);
+GtkAccessible * gtk_accessible_get_first_accessible_child(GtkAccessible *self);
+
+GDK_AVAILABLE_IN_4_10
+GtkAccessible * gtk_accessible_get_next_accessible_sibling(GtkAccessible *self);
 
 GDK_AVAILABLE_IN_4_10
 gboolean gtk_accessible_get_bounds (GtkAccessible *self, int *x, int *y, int *width, int *height);
diff --git a/gtk/gtkstack.c b/gtk/gtkstack.c
index fa47587b1b..4b9ccc1aa0 100644
--- a/gtk/gtkstack.c
+++ b/gtk/gtkstack.c
@@ -212,6 +212,8 @@ struct _GtkStackPage
   char *icon_name;
   GtkWidget *last_focus;
 
+  GtkStackPage *next_page;
+
   GtkATContext *at_context;
 
   guint needs_attention : 1;
@@ -268,17 +270,24 @@ gtk_stack_page_accessible_get_accessible_parent (GtkAccessible *accessible)
 }
 
 static GtkAccessible *
-gtk_stack_page_accessible_get_child_at_index(GtkAccessible *accessible,
-                                             guint          idx)
+gtk_stack_page_accessible_get_first_accessible_child(GtkAccessible *accessible)
 {
   GtkStackPage *page = GTK_STACK_PAGE (accessible);
 
-  if (idx == 0 && page->widget != NULL)
+  if (page->widget != NULL)
     return GTK_ACCESSIBLE (page->widget);
   else
     return NULL;
 }
 
+static GtkAccessible *
+gtk_stack_page_accessible_get_next_accessible_sibling(GtkAccessible *accessible)
+{
+  GtkStackPage *page = GTK_STACK_PAGE (accessible);
+
+  return GTK_ACCESSIBLE (page->next_page);
+}
+
 static gboolean
 gtk_stack_page_accessible_get_bounds (GtkAccessible *accessible,
                                       int           *x,
@@ -299,7 +308,8 @@ gtk_stack_page_accessible_init (GtkAccessibleInterface *iface)
   iface->get_at_context = gtk_stack_page_accessible_get_at_context;
   iface->get_platform_state = gtk_stack_page_accessible_get_platform_state;
   iface->get_accessible_parent = gtk_stack_page_accessible_get_accessible_parent;
-  iface->get_child_at_index = gtk_stack_page_accessible_get_child_at_index;
+  iface->get_first_accessible_child = gtk_stack_page_accessible_get_first_accessible_child;
+  iface->get_next_accessible_sibling = gtk_stack_page_accessible_get_next_accessible_sibling;
   iface->get_bounds = gtk_stack_page_accessible_get_bounds;
 }
 
@@ -669,7 +679,7 @@ gtk_stack_pages_get_property (GObject    *object,
 
     case PAGES_PROP_N_ITEMS:
       g_value_set_uint (value, gtk_stack_pages_get_n_items (G_LIST_MODEL (self)));
-      break;  
+      break;
 
     default:
       G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
@@ -776,18 +786,18 @@ gtk_stack_buildable_interface_init (GtkBuildableIface *iface)
 }
 
 static GtkAccessible *
-gtk_stack_accessible_get_child_at_index (GtkAccessible *accessible, guint idx)
+gtk_stack_accessible_get_first_accessible_child (GtkAccessible *accessible)
 {
   GtkStack *stack = GTK_STACK (accessible);
   GtkStackPrivate *priv = gtk_stack_get_instance_private (stack);
-  GtkStackPage *page = g_ptr_array_index (priv->children, idx);
+  GtkStackPage *page = g_ptr_array_index (priv->children, 0);
   return GTK_ACCESSIBLE (page);
 }
 
 static void
 gtk_stack_accessible_init (GtkAccessibleInterface *iface)
 {
-  iface->get_child_at_index = gtk_stack_accessible_get_child_at_index;
+  iface->get_first_accessible_child = gtk_stack_accessible_get_first_accessible_child;
 }
 
 static void stack_remove (GtkStack  *stack,
@@ -1657,6 +1667,18 @@ gtk_stack_add_page (GtkStack     *stack,
         }
     }
 
+
+  if (priv->children->len > 0)
+    {
+      GtkStackPage *prev_last = g_ptr_array_index (priv->children, priv->children->len - 1);
+
+      prev_last->next_page = child_info;
+    }
+  else
+    {
+      child_info->next_page = NULL;
+    }
+
   g_ptr_array_add (priv->children, g_object_ref (child_info));
 
   gtk_widget_set_child_visible (child_info->widget, FALSE);
@@ -1710,6 +1732,16 @@ stack_remove (GtkStack  *stack,
 
     g_ptr_array_remove (priv->children, child_info);
 
+  for (guint prev_idx = 0; prev_idx < priv->children->len; prev_idx++)
+    {
+      GtkStackPage *prev_page = g_ptr_array_index (priv->children, prev_idx);
+      if (prev_page->next_page == child_info)
+        {
+          prev_page->next_page = child_info->next_page;
+          break;
+        }
+    }
+
   g_object_unref (child_info);
 
   if (!in_dispose &&
diff --git a/gtk/gtkwidget.c b/gtk/gtkwidget.c
index ed56005039..606f2d352f 100644
--- a/gtk/gtkwidget.c
+++ b/gtk/gtkwidget.c
@@ -8472,20 +8472,15 @@ gtk_widget_accessible_get_accessible_parent (GtkAccessible *self)
 }
 
 static GtkAccessible *
-gtk_widget_accessible_get_child_at_index (GtkAccessible *self,
-                                          guint          idx)
+gtk_widget_accessible_get_next_accessible_sibling (GtkAccessible *self)
 {
-  guint i = 0;
-  GtkWidget *child;
-  for (child = gtk_widget_get_first_child (GTK_WIDGET (self));
-               child != NULL;
-               child = gtk_widget_get_next_sibling (child))
-    {
-      if (i == idx)
-        return GTK_ACCESSIBLE (child);
-      i++;
-    }
-  return NULL;
+  return GTK_ACCESSIBLE (gtk_widget_get_next_sibling (GTK_WIDGET (self)));
+}
+
+static GtkAccessible *
+gtk_widget_accessible_get_first_accessible_child (GtkAccessible *self)
+{
+  return GTK_ACCESSIBLE (gtk_widget_get_first_child (GTK_WIDGET (self)));
 }
 
 static gboolean
@@ -8526,7 +8521,8 @@ gtk_widget_accessible_interface_init (GtkAccessibleInterface *iface)
   iface->get_at_context = gtk_widget_accessible_get_at_context;
   iface->get_platform_state = gtk_widget_accessible_get_platform_state;
   iface->get_accessible_parent = gtk_widget_accessible_get_accessible_parent;
-  iface->get_child_at_index = gtk_widget_accessible_get_child_at_index;
+  iface->get_first_accessible_child = gtk_widget_accessible_get_first_accessible_child;
+  iface->get_next_accessible_sibling = gtk_widget_accessible_get_next_accessible_sibling;
   iface->get_bounds = gtk_widget_accessible_get_bounds;
 }