Modified cache API to include index and child count rather than children

The original cache API was problematic for QT AT-SPI because it forces
enumeration of all children, preventing lazy instantiation of objects.
The API now sends the object's index in parent and child count (or -1 if
not known / children should not be cached) rather than an array of
children.
Also made cache of children a GPtrArray rather than a GList, since it
may contain holes.  If an object has not yet been instantiated for a
particular child, then its value will be set to NULL, and
atspi_accessible_get_child_at_index will make a dbus call to fetch the
child, at which point it will be cached.

https://bugzilla.gnome.org/show_bug.cgi?id=650090

6 files changed, 126 insertions, 98 deletions

diff --git a/atspi/atspi-accessible.c b/atspi/atspi-accessible.c
index 2d773575..85970d25 100644
--- a/atspi/atspi-accessible.c
+++ b/atspi/atspi-accessible.c
@@ -118,6 +118,8 @@ atspi_accessible_init (AtspiAccessible *accessible)
 #endif
 
   accessible->priv = atspi_accessible_get_instance_private (accessible);
+
+  accessible->children = g_ptr_array_new_with_free_func (g_object_unref);
 }
 
 static void
@@ -126,8 +128,7 @@ atspi_accessible_dispose (GObject *object)
   AtspiAccessible *accessible = ATSPI_ACCESSIBLE (object);
   AtspiEvent e;
   AtspiAccessible *parent;
-  GList *children;
-  GList *l;
+  gint i;
 
   /* TODO: Only fire if object not already marked defunct */
   memset (&e, 0, sizeof (e));
@@ -137,45 +138,32 @@ atspi_accessible_dispose (GObject *object)
   e.detail2 = 0;
   _atspi_send_event (&e);
 
-  if (accessible->states)
-  {
-    g_object_unref (accessible->states);
-    accessible->states = NULL;
-  }
+  g_clear_object (&accessible->states);
 
   parent = accessible->accessible_parent;
-  if (parent && parent->children)
-  {
-    GList*ls = g_list_find (parent->children, accessible);
-    if(ls)
-    {
-      gboolean replace = (ls == parent->children);
-      ls = g_list_remove (ls, accessible);
-      if (replace)
-        parent->children = ls;
-      g_object_unref (object);
-    }
-  }
-
   if (parent)
   {
-    g_object_unref (parent);
     accessible->accessible_parent = NULL;
+    if (parent->children)
+      g_ptr_array_remove (parent->children, accessible);
+    g_object_unref (parent);
   }
 
-  children = accessible->children;
-  accessible->children = NULL;
-  for (l = children; l; l = l->next)
+  if (accessible->children) for (i = accessible->children->len - 1; i >= 0; i--)
   {
-    AtspiAccessible *child = l->data;
+    AtspiAccessible *child = g_ptr_array_index (accessible->children, i);
     if (child && child->accessible_parent == accessible)
     {
-      g_object_unref (accessible);
       child->accessible_parent = NULL;
+      g_object_unref (accessible);
     }
-    g_object_unref (child);
   }
-  g_list_free (children);
+
+  if (accessible->children)
+  {
+    g_ptr_array_free (accessible->children, TRUE);
+    accessible->children = NULL;
+  }
 
   G_OBJECT_CLASS (atspi_accessible_parent_class) ->dispose (object);
 }
@@ -199,8 +187,7 @@ atspi_accessible_finalize (GObject *object)
   g_print ("at-spi: finalize: %d objects\n", accessible_count);
 #endif
 
-  G_OBJECT_CLASS (atspi_accessible_parent_class)
-    ->finalize (object);
+  G_OBJECT_CLASS (atspi_accessible_parent_class)->finalize (object);
 }
 
 static void
@@ -337,7 +324,10 @@ atspi_accessible_get_child_count (AtspiAccessible *obj, GError **error)
     return ret;
   }
 
-  return g_list_length (obj->children);
+  if (!obj->children)
+    return 0;	/* assume it's disposed */
+
+  return obj->children->len;
 }
 
 /**
@@ -356,22 +346,34 @@ atspi_accessible_get_child_at_index (AtspiAccessible *obj,
                             GError **error)
 {
   AtspiAccessible *child;
+  DBusMessage *reply;
 
   g_return_val_if_fail (obj != NULL, NULL);
 
-  if (!_atspi_accessible_test_cache (obj, ATSPI_CACHE_CHILDREN))
+  if (_atspi_accessible_test_cache (obj, ATSPI_CACHE_CHILDREN))
   {
-    DBusMessage *reply;
-    reply = _atspi_dbus_call_partial (obj, atspi_interface_accessible,
-                                     "GetChildAtIndex", error, "i",
-                                     child_index);
-    return _atspi_dbus_return_accessible_from_message (reply);
+    if (!obj->children)
+      return NULL;	/* assume disposed */
+
+    child = g_ptr_array_index (obj->children, child_index);
+    if (child)
+      return g_object_ref (child);
   }
 
-  child = g_list_nth_data (obj->children, child_index);
+  reply = _atspi_dbus_call_partial (obj, atspi_interface_accessible,
+                                   "GetChildAtIndex", error, "i", child_index);
+  child = _atspi_dbus_return_accessible_from_message (reply);
+
   if (!child)
     return NULL;
-  return g_object_ref (child);
+
+  if (_atspi_accessible_test_cache (obj, ATSPI_CACHE_CHILDREN))
+  {
+      if (child_index >= obj->children->len)
+        g_ptr_array_set_size (obj->children, child_index + 1);
+    g_ptr_array_index (obj->children, child_index) = g_object_ref (child);
+  }
+  return child;
 }
 
 /**
@@ -388,31 +390,23 @@ atspi_accessible_get_child_at_index (AtspiAccessible *obj,
 gint
 atspi_accessible_get_index_in_parent (AtspiAccessible *obj, GError **error)
 {
-  GList *l;
   gint i = 0;
+  dbus_int32_t ret = -1;
 
   g_return_val_if_fail (obj != NULL, -1);
-  if (_atspi_accessible_test_cache (obj, ATSPI_CACHE_PARENT) &&
-      !obj->accessible_parent)
-    return -1;
-  if (!obj->accessible_parent ||
-      !_atspi_accessible_test_cache (obj->accessible_parent,
-                                     ATSPI_CACHE_CHILDREN))
+  if (_atspi_accessible_test_cache (obj, ATSPI_CACHE_PARENT))
   {
-    dbus_int32_t ret = -1;
-    _atspi_dbus_call (obj, atspi_interface_accessible,
-                      "GetIndexInParent", NULL, "=>i", &ret);
-    return ret;
-  }
+    if (!obj->accessible_parent)
+      return -1;
 
-  l = obj->accessible_parent->children;
-  while (l)
-  {
-    if (l->data == obj) return i;
-    l = g_list_next (l);
-    i++;
+    for (i = 0; i < obj->accessible_parent->children->len; i++)
+      if (g_ptr_array_index (obj->accessible_parent->children, i) == obj)
+        return i;
   }
-  return -1;
+
+  _atspi_dbus_call (obj, atspi_interface_accessible,
+                    "GetIndexInParent", NULL, "=>i", &ret);
+  return ret;
 }
 
 typedef struct
@@ -1623,21 +1617,21 @@ atspi_accessible_set_cache_mask (AtspiAccessible *accessible, AtspiCache mask)
 
 /**
  * atspi_accessible_clear_cache:
- * @accessible: The #AtspiAccessible whose cache to clear.
+ * @obj: The #AtspiAccessible whose cache to clear.
  *
  * Clears the cached information for the given accessible and all of its
  * descendants.
  */
 void
-atspi_accessible_clear_cache (AtspiAccessible *accessible)
+atspi_accessible_clear_cache (AtspiAccessible *obj)
 {
-  GList *l;
+  gint i;
 
-  if (accessible)
+  if (obj)
   {
-    accessible->cached_properties = ATSPI_CACHE_NONE;
-    for (l = accessible->children; l; l = l->next)
-      atspi_accessible_clear_cache (l->data);
+    obj->cached_properties = ATSPI_CACHE_NONE;
+    for (i = 0; i < obj->children->len; i++)
+      atspi_accessible_clear_cache (g_ptr_array_index (obj->children, i));
   }
 }
 
diff --git a/atspi/atspi-accessible.h b/atspi/atspi-accessible.h
index 2c3f8cc7..443e395a 100644
--- a/atspi/atspi-accessible.h
+++ b/atspi/atspi-accessible.h
@@ -49,7 +49,7 @@ struct _AtspiAccessible
 {
   AtspiObject parent;
   AtspiAccessible *accessible_parent;
-  GList *children;
+  GPtrArray *children;
   AtspiRole role;
   gint interfaces;
   char *name;
@@ -163,7 +163,7 @@ const gchar* atspi_accessible_get_object_locale (AtspiAccessible *accessible, GE
 
 void atspi_accessible_set_cache_mask (AtspiAccessible *accessible, AtspiCache mask);
 
-void atspi_accessible_clear_cache (AtspiAccessible *accessible);
+void atspi_accessible_clear_cache (AtspiAccessible *obj);
 
 guint atspi_accessible_get_process_id (AtspiAccessible *accessible, GError **error);
 
diff --git a/atspi/atspi-event-listener.c b/atspi/atspi-event-listener.c
index 292e88ba..7746ea1f 100644
--- a/atspi/atspi-event-listener.c
+++ b/atspi/atspi-event-listener.c
@@ -210,18 +210,24 @@ cache_process_children_changed (AtspiEvent *event)
 
   if (!strncmp (event->type, "object:children-changed:add", 27))
   {
-    if (g_list_find (event->source->children, child))
+    g_ptr_array_remove (event->source->children, child); /* just to be safe */
+    if (event->detail1 < 0 || event->detail1 > event->source->children->len)
+    {
+      event->source->cached_properties &= ~ATSPI_CACHE_CHILDREN;
       return;
-    event->source->children = g_list_insert (event->source->children,
-                                             g_object_ref (child),
-                                             event->detail1);
+    }
+    /* Unfortunately, there's no g_ptr_array_insert or similar */
+    g_ptr_array_add (event->source->children, NULL);
+    memmove (event->source->children->pdata + event->detail1 + 1,
+             event->source->children->pdata + event->detail1,
+             (event->source->children->len - event->detail1 - 1) * sizeof (gpointer));
+    g_ptr_array_index (event->source->children, event->detail1) = g_object_ref (child);
   }
-  else if (g_list_find (event->source->children, child))
+  else
   {
-    event->source->children = g_list_remove (event->source->children, child);
+    g_ptr_array_remove (event->source->children, child);
     if (child == child->parent.app->root)
       g_object_run_dispose (G_OBJECT (child->parent.app));
-    g_object_unref (child);
   }
 }
 
diff --git a/atspi/atspi-misc.c b/atspi/atspi-misc.c
index 4cf7732c..075a968a 100644
--- a/atspi/atspi-misc.c
+++ b/atspi/atspi-misc.c
@@ -136,7 +136,7 @@ static void
 cleanup ()
 {
   GHashTable *refs;
-  GList *l;
+  gint i;
 
   refs = live_refs;
   live_refs = NULL;
@@ -154,14 +154,15 @@ cleanup ()
 
   if (!desktop)
     return;
-  for (l = desktop->children; l;)
+
+  /* TODO: Do we need this code, or should we just dispose the desktop? */
+  for (i = desktop->children->len - 1; i >= 0; i--)
   {
-    GList *next = l->next;
-    AtspiAccessible *child = l->data;
+    AtspiAccessible *child = g_ptr_array_index (desktop->children, i);
     g_object_run_dispose (G_OBJECT (child->parent.app));
     g_object_run_dispose (G_OBJECT (child));
-    l = next;
   }
+
   g_object_run_dispose (G_OBJECT (desktop->parent.app));
   g_object_unref (desktop);
   desktop = NULL;
@@ -277,7 +278,7 @@ ref_accessible (const char *app_name, const char *path)
     {
       app->root = _atspi_accessible_new (app, atspi_path_root);
       app->root->accessible_parent = atspi_get_desktop (0);
-      app->root->accessible_parent->children = g_list_append (app->root->accessible_parent->children, g_object_ref (app->root));
+      g_ptr_array_add (app->root->accessible_parent->children, g_object_ref (app->root));
     }
     return g_object_ref (app->root);
   }
@@ -423,6 +424,8 @@ add_accessible_from_iter (DBusMessageIter *iter)
   AtspiAccessible *accessible;
   const char *name, *description;
   dbus_uint32_t role;
+  gboolean children_cached = FALSE;
+  dbus_int32_t count, index;
 
   dbus_message_iter_recurse (iter, &iter_struct);
 
@@ -441,19 +444,40 @@ add_accessible_from_iter (DBusMessageIter *iter)
     g_object_unref (accessible->accessible_parent);
   accessible->accessible_parent = ref_accessible (app_name, path);
 
-  /* Get children */
-  while (accessible->children)
+  if (dbus_message_iter_get_arg_type (&iter_struct) == 'i')
   {
-    g_object_unref (accessible->children->data);
-    accessible->children = g_list_remove (accessible->children, accessible->children->data);
+    /* Get index in parent */
+    dbus_message_iter_get_basic (&iter_struct, &index);
+    if (index >= 0 && accessible->accessible_parent)
+    {
+      if (index >= accessible->accessible_parent->children->len)
+        g_ptr_array_set_size (accessible->accessible_parent->children, index + 1);
+      g_ptr_array_index (accessible->accessible_parent->children, index) = g_object_ref (accessible);
+    }
+
+    /* get child count */
+    dbus_message_iter_next (&iter_struct);
+    dbus_message_iter_get_basic (&iter_struct, &count);
+    if (count >= 0)
+    {
+      g_ptr_array_set_size (accessible->children, count);
+      children_cached = TRUE;
+    }
   }
-  dbus_message_iter_recurse (&iter_struct, &iter_array);
-  while (dbus_message_iter_get_arg_type (&iter_array) != DBUS_TYPE_INVALID)
+  else if (dbus_message_iter_get_arg_type (&iter_struct) == 'a')
   {
-    AtspiAccessible *child;
-    get_reference_from_iter (&iter_array, &app_name, &path);
-    child = ref_accessible (app_name, path);
-    accessible->children = g_list_append (accessible->children, child);
+    /* It's the old API with a list of children */
+    /* TODO: Perhaps remove this code eventually */
+    dbus_message_iter_recurse (&iter_struct, &iter_array);
+    while (dbus_message_iter_get_arg_type (&iter_array) != DBUS_TYPE_INVALID)
+    {
+      AtspiAccessible *child;
+      get_reference_from_iter (&iter_array, &app_name, &path);
+      child = ref_accessible (app_name, path);
+      g_ptr_array_remove (accessible->children, child);
+      g_ptr_array_add (accessible->children, child);
+    }
+    children_cached = TRUE;
   }
 
   /* interfaces */
@@ -486,7 +510,8 @@ add_accessible_from_iter (DBusMessageIter *iter)
   _atspi_accessible_add_cache (accessible, ATSPI_CACHE_NAME | ATSPI_CACHE_ROLE |
                                ATSPI_CACHE_PARENT | ATSPI_CACHE_DESCRIPTION);
   if (!atspi_state_set_contains (accessible->states,
-                                       ATSPI_STATE_MANAGES_DESCENDANTS))
+                                       ATSPI_STATE_MANAGES_DESCENDANTS) &&
+                                       children_cached)
     _atspi_accessible_add_cache (accessible, ATSPI_CACHE_CHILDREN);
 
   /* This is a bit of a hack since the cache holds a ref, so we don't need
@@ -664,17 +689,19 @@ _atspi_dbus_return_hyperlink_from_iter (DBusMessageIter *iter)
   return ref_hyperlink (app_name, path);
 }
 
-const char *cache_signal_type = "((so)(so)(so)a(so)assusau)";
+const char *cache_signal_type = "((so)(so)(so)iiassusau)";
+const char *old_cache_signal_type = "((so)(so)(so)a(so)assusau)";
 
 static DBusHandlerResult
 handle_add_accessible (DBusConnection *bus, DBusMessage *message, void *user_data)
 {
   DBusMessageIter iter;
+  const char *signature = dbus_message_get_signature (message);
 
-  if (strcmp (dbus_message_get_signature (message), cache_signal_type) != 0)
+  if (strcmp (signature, cache_signal_type) != 0 &&
+      strcmp (signature, old_cache_signal_type) != 0)
   {
-    g_warning ("AT-SPI: AddAccessible with unknown signature %s\n",
-               dbus_message_get_signature (message));
+    g_warning ("AT-SPI: AddAccessible with unknown signature %s\n", signature);
     return DBUS_HANDLER_RESULT_HANDLED;
   }
 
diff --git a/idl/cache.didl b/idl/cache.didl
index 8cb96939..3cf9b115 100644
--- a/idl/cache.didl
+++ b/idl/cache.didl
@@ -4,7 +4,8 @@ interface org.freestandards.atspi.Cache {
 	struct CacheItem {
 		object      path;
 		Reference   parent;
-		Reference[] children;
+		int index_in_parent;
+		int child_count;
 		string[]    interfaces;
 		string      name;
 		Role        role;
diff --git a/xml/Cache.xml b/xml/Cache.xml
index ad01bceb..e693b54c 100644
--- a/xml/Cache.xml
+++ b/xml/Cache.xml
@@ -3,12 +3,12 @@
 <interface name="org.a11y.atspi.Cache">
 
   <method name="GetItems">
-    <arg name="nodes" type="a((so)(so)a(so)assusau)" direction="out"/>
+    <arg name="nodes" type="a((so)(so)iiassusau)" direction="out"/>
     <annotation name="com.trolltech.QtDBus.QtTypeName.Out0" value="QSpiAccessibleCacheArray"/>
   </method>
 
   <signal name="AddAccessible">
-    <arg name="nodeAdded" type="((so)(so)a(so)assusau)"/>
+    <arg name="nodeAdded" type="((so)(so)iiassusau)"/>
     <annotation name="com.trolltech.QtDBus.QtTypeName.In0" value="QSpiAccessibleCacheItem"/>
   </signal>