Modified cache API to include index and child count rather than childrencache-refactor

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.

6 files changed, 140 insertions, 95 deletions

diff --git a/atspi/atspi-accessible.c b/atspi/atspi-accessible.c
index 9c21f446..a5d2928d 100644
--- a/atspi/atspi-accessible.c
+++ b/atspi/atspi-accessible.c
@@ -104,6 +104,8 @@ atspi_accessible_init (AtspiAccessible *accessible)
   accessible_count++;
   printf("at-spi: init: %d objects\n", accessible_count);
 #endif
+
+  accessible->children = g_ptr_array_new_with_free_func (g_object_unref);
 }
 
 static void
@@ -112,6 +114,7 @@ atspi_accessible_dispose (GObject *object)
   AtspiAccessible *accessible = ATSPI_ACCESSIBLE (object);
   AtspiEvent e;
   AtspiAccessible *parent;
+  gint i;
 
   /* TODO: Only fire if object not already marked defunct */
   memset (&e, 0, sizeof (e));
@@ -128,23 +131,30 @@ atspi_accessible_dispose (GObject *object)
   }
 
   parent = accessible->accessible_parent;
-  if (parent && parent->children)
+  if (parent)
+  {
+    accessible->accessible_parent = NULL;
+    if (parent->children)
+      g_ptr_array_remove (parent->children, accessible);
+    g_object_unref (parent);
+  }
+
+  while (accessible->children && accessible->children->len > 0)
   {
-    GList*ls = g_list_find (parent->children, accessible);
-    if(ls)
+    int index = accessible->children->len - 1;
+    AtspiAccessible *child = g_ptr_array_index (accessible->children, index);
+    if (child && child->accessible_parent == accessible)
     {
-      gboolean replace = (ls == parent->children);
-      ls = g_list_remove (ls, accessible);
-      if (replace)
-        parent->children = ls;
-      g_object_unref (object);
+      child->accessible_parent = NULL;
+      g_object_unref (accessible);
     }
+    g_ptr_array_remove_index (accessible->children, index);
   }
 
-  if (parent)
+  if (accessible->children)
   {
-    g_object_unref (parent);
-    accessible->accessible_parent = NULL;
+    g_ptr_array_free (accessible->children, TRUE);
+    accessible->children = NULL;
   }
 
   G_OBJECT_CLASS (atspi_accessible_parent_class) ->dispose (object);
@@ -165,8 +175,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
@@ -419,7 +428,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;
 }
 
 /**
@@ -438,22 +450,33 @@ 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;
 }
 
 /**
@@ -469,28 +492,22 @@ 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_uint32_t ret = -1;
 
   g_return_val_if_fail (obj != NULL, -1);
   if (!obj->accessible_parent) return -1;
-  if (!_atspi_accessible_test_cache (obj->accessible_parent,
+  if (_atspi_accessible_test_cache (obj->accessible_parent,
                                      ATSPI_CACHE_CHILDREN))
   {
-    dbus_uint32_t ret = -1;
-    _atspi_dbus_call (obj, atspi_interface_accessible,
-                      "GetIndexInParent", NULL, "=>u", &ret);
-    return ret;
+    for (i = 0; i < obj->accessible_parent->children->len; i++)
+      if (g_ptr_array_index (obj->accessible_parent->children, i) == obj)
+        return i;
   }
 
-  l = obj->accessible_parent->children;
-  while (l)
-  {
-    if (l->data == obj) return i;
-    l = g_list_next (l);
-    i++;
-  }
-  return -1;
+  _atspi_dbus_call (obj, atspi_interface_accessible,
+                    "GetIndexInParent", NULL, "=>u", &ret);
+  return ret;
 }
 
 typedef struct
@@ -1442,21 +1459,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;
+  int 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 987f696c..45d0cea5 100644
--- a/atspi/atspi-accessible.h
+++ b/atspi/atspi-accessible.h
@@ -45,7 +45,7 @@ struct _AtspiAccessible
 {
   AtspiObject parent;
   AtspiAccessible *accessible_parent;
-  GList *children;
+  GPtrArray *children;
   AtspiRole role;
   gint interfaces;
   char *name;
@@ -132,7 +132,7 @@ GArray * atspi_accessible_get_interfaces (AtspiAccessible *obj);
 
 void atspi_accessible_set_cache_mask (AtspiAccessible *accessible, AtspiCache mask);
 
-void atspi_accessible_clear_cache (AtspiAccessible *accessible);
+void atspi_accessible_clear_cache (AtspiAccessible *obj);
 
 /* private */
 void _atspi_accessible_add_cache (AtspiAccessible *accessible, AtspiCache flag);
diff --git a/atspi/atspi-event-listener.c b/atspi/atspi-event-listener.c
index b81e5b6c..49c4d0f7 100644
--- a/atspi/atspi-event-listener.c
+++ b/atspi/atspi-event-listener.c
@@ -176,18 +176,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;
-    GList *new_list = g_list_insert (event->source->children, g_object_ref (child), event->detail1);
-    if (new_list)
-      event->source->children = new_list;
+    }
+    /* 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 616dc224..7ff9ad02 100644
--- a/atspi/atspi-misc.c
+++ b/atspi/atspi-misc.c
@@ -323,12 +323,9 @@ add_app_to_desktop (AtspiAccessible *a, const char *bus_name)
   AtspiAccessible *obj = ref_accessible (bus_name, atspi_path_root);
   if (obj)
   {
-    GList *new_list = g_list_append (a->children, obj);
-    if (new_list)
-    {
-      a->children = new_list;
-      return TRUE;
-    }
+    g_ptr_array_remove (a->children, obj);
+    g_ptr_array_add (a->children, obj);
+    return TRUE;
   }
   else
   {
@@ -345,41 +342,42 @@ send_children_changed (AtspiAccessible *parent, AtspiAccessible *child, gboolean
   memset (&e, 0, sizeof (e));
   e.type = (add? "object:children-changed:add": "object:children-changed:remove");
   e.source = parent;
-  e.detail1 = g_list_index (parent->children, child);
+  e.detail1 = atspi_accessible_get_index_in_parent (child, NULL);
   e.detail2 = 0;
   _atspi_send_event (&e);
 }
 
 static void
-unref_object_and_descendants (AtspiAccessible *obj)
+dispose_object_and_descendants (AtspiAccessible *obj)
 {
-  GList *l;
+  gint i;
 
-  for (l = obj->children; l; l = l->next)
+  for (i = 0; i < obj->children->len; i++)
   {
-    unref_object_and_descendants (l->data);
+    AtspiAccessible *child = g_ptr_array_index (obj->children, i);
+    if (child)
+      dispose_object_and_descendants (child);
   }
-  g_object_unref (obj);
+  g_object_run_dispose (G_OBJECT (obj));
 }
 
 static gboolean
 remove_app_from_desktop (AtspiAccessible *a, const char *bus_name)
 {
-  GList *l;
+  gint i;
   AtspiAccessible *child;
 
-  for (l = a->children; l; l = l->next)
+  for (i = 0; i < a->children->len; i++)
   {
-    child = l->data;
-    if (!strcmp (bus_name, child->parent.app->bus_name)) break;
+    child = g_ptr_array_index (a->children, i);
+    if (child && !strcmp (bus_name, child->parent.app->bus_name))
+      break;
   }
-  if (!l)
-  {
+  if (i == a->children->len)
     return FALSE;
-  }
   send_children_changed (a, child, FALSE);
-  a->children = g_list_remove (a->children, child);
-  unref_object_and_descendants (child);
+  dispose_object_and_descendants (child);
+  g_ptr_array_remove (a->children, child);
   return TRUE;
 }
 
@@ -400,12 +398,13 @@ get_reference_from_iter (DBusMessageIter *iter, const char **app_name, const cha
 static void
 add_accessible_from_iter (DBusMessageIter *iter)
 {
-  GList *new_list;
+  dbus_int32_t index, count;
   DBusMessageIter iter_struct, iter_array;
   const char *app_name, *path;
   AtspiAccessible *accessible;
   const char *name, *description;
   dbus_uint32_t role;
+  gboolean children_cached = FALSE;
 
   dbus_message_iter_recurse (iter, &iter_struct);
 
@@ -424,20 +423,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);
-    new_list = g_list_append (accessible->children, child);
-    if (new_list) accessible->children = new_list;
+    /* 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 */
@@ -446,8 +465,7 @@ add_accessible_from_iter (DBusMessageIter *iter)
   dbus_message_iter_next (&iter_struct);
 
   /* name */
-  if (accessible->name)
-    g_free (accessible->name);
+  g_free (accessible->name);
   dbus_message_iter_get_basic (&iter_struct, &name);
   accessible->name = g_strdup (name);
   dbus_message_iter_next (&iter_struct);
@@ -458,8 +476,7 @@ add_accessible_from_iter (DBusMessageIter *iter)
   dbus_message_iter_next (&iter_struct);
 
   /* description */
-  if (accessible->description)
-    g_free (accessible->description);
+  g_free (accessible->description);
   dbus_message_iter_get_basic (&iter_struct, &description);
   accessible->description = g_strdup (description);
   dbus_message_iter_next (&iter_struct);
@@ -470,7 +487,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
@@ -636,15 +654,18 @@ _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 *sender = dbus_message_get_sender (message);
+  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));
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>