match_states_all_p (AtkObject *child, gint *set)

  gboolean ret = TRUE;

  if (set == NULL || set[0] == BITARRAY_SEQ_TERM)

    return TRUE;

  chs = atk_object_ref_state_set (child);

  for (i = 0; set[i] != BITARRAY_SEQ_TERM; i++)

      if (!atk_state_set_contains_state (chs, set[i]))

          ret = FALSE;

          break;

  g_object_unref (chs);

  return ret;

match_states_lookup (AtkObject *child, MatchRulePrivate *mrp)

  switch (mrp->statematchtype)

    case ATSPI_Collection_MATCH_ALL:

      if (match_states_all_p (child, mrp->states))

        return TRUE;

      break;

  return FALSE;

match_roles_all_p (AtkObject *child, gint *roles)

  if (roles == NULL || roles[0] == BITARRAY_SEQ_TERM)

    return TRUE;

match_roles_none_p (AtkObject *child, gint *roles)

  if (roles == NULL || roles[0] == BITARRAY_SEQ_TERM)

  role = spi_get_role (child);

  for (i = 0; roles[i] != BITARRAY_SEQ_TERM; i++)

    if (role == roles[i])

      return FALSE;

  return TRUE;

match_roles_lookup (AtkObject *child, MatchRulePrivate *mrp)

  switch (mrp->rolematchtype)

    case ATSPI_Collection_MATCH_ALL:

      if (match_roles_all_p (child, mrp->roles))

        return TRUE;

    case ATSPI_Collection_MATCH_NONE:

      if (match_roles_none_p (child, mrp->roles))

        return TRUE;

      break;

  return FALSE;

match_interfaces_all_p (AtkObject *obj, gchar **ifaces)

  if (ifaces == NULL)

  for (i = 0; ifaces[i]; i++)

  return TRUE;

match_interfaces_lookup (AtkObject *child, MatchRulePrivate *mrp)

  switch (mrp->interfacematchtype)

    case ATSPI_Collection_MATCH_ALL:

      if (match_interfaces_all_p (child, mrp->ifaces))

        return TRUE;

match_attributes_all_p (AtkObject *child, AtkAttributeSet *attributes)

  gboolean flag = FALSE;

  if (attributes == NULL || g_slist_length (attributes) == 0)

    return TRUE;

match_attributes_none_p (AtkObject *child, AtkAttributeSet *attributes)

  length = g_slist_length (attributes);

  if (length == 0)

  oa = atk_object_get_attributes (child);

  oa_length = g_slist_length (oa);

  for (i = 0; i < length; i++)

      AtkAttribute *attr = g_slist_nth_data (attributes, i);

      for (k = 0; k < oa_length; k++)

          AtkAttribute *oa_attr = g_slist_nth_data (oa, k);

          if (!g_ascii_strcasecmp (oa_attr->name, attr->name) &&

  atk_attribute_set_free (oa);

  return TRUE;

match_attributes_lookup (AtkObject *child, MatchRulePrivate *mrp)

  switch (mrp->attributematchtype)

    case ATSPI_Collection_MATCH_ALL:

      if (match_attributes_all_p (child, mrp->attributes))

        return TRUE;

    case ATSPI_Collection_MATCH_NONE:

      if (match_attributes_none_p (child, mrp->attributes))

        return TRUE;

traverse_p (AtkObject *child, const gboolean traverse)

  if (traverse)

    return TRUE;

    return !child_collection_p (child);

sort_order_canonical (MatchRulePrivate *mrp, GList *ls, gint kount, gint max, AtkObject *obj, glong index, gboolean flag, AtkObject *pobj, gboolean recurse, gboolean traverse)

  gint i = index;

  glong acount = atk_object_get_n_accessible_children (obj);

  gboolean prev = pobj ? TRUE : FALSE;

  if (acount > MAX_CHILDREN)

  for (; i < acount && (max == 0 || kount < max); i++)

      AtkObject *child = atk_object_ref_accessible_child (obj, i);

      if (!child)

      if (prev && child == pobj)

      if (flag && match_interfaces_lookup (child, mrp) && match_states_lookup (child, mrp) && match_roles_lookup (child, mrp) && match_attributes_lookup (child, mrp))

          ls = g_list_append (ls, child);

          kount++;

      if (!flag)

      if (recurse && traverse_p (child, traverse))

        kount = sort_order_canonical (mrp, ls, kount,

      g_object_unref (child);

  return kount;

sort_order_rev_canonical (MatchRulePrivate *mrp, GList *ls, gint kount, gint max, AtkObject *obj, gboolean flag, AtkObject *pobj)

  if (!obj || obj == pobj)

      return kount;

  if (flag && match_interfaces_lookup (obj, mrp) && match_states_lookup (obj, mrp) && match_roles_lookup (obj, mrp) && match_attributes_lookup (obj, mrp) && (max == 0 || kount < max))

      ls = g_list_append (ls, obj);

      kount++;

  indexinparent = atk_object_get_index_in_parent (obj);

  parent = atk_object_get_parent (obj);

  if (indexinparent > 0 && (max == 0 || kount < max))

      nextobj = atk_object_ref_accessible_child (parent, indexinparent - 1);

      while (nextobj && atk_object_get_n_accessible_children (nextobj) > 0)

      kount = sort_order_rev_canonical (mrp, ls, kount, max,

      if (nextobj)

        g_object_unref (nextobj);

  else if (max == 0 || kount < max)

      kount = sort_order_rev_canonical (mrp, ls, kount, max,

  return kount;

query_exec (MatchRulePrivate *mrp, AtspiCollectionSortOrder sortby, GList *ls, gint kount, gint max, AtkObject *obj, glong index, gboolean flag, AtkObject *pobj, gboolean recurse, gboolean traverse)

  switch (sortby)

    case ATSPI_Collection_SORT_ORDER_CANONICAL:

      kount = sort_order_canonical (mrp, ls, 0, max, obj, index, flag,

      break;

  return kount;

bitarray_to_seq (dbus_uint32_t *array, int array_count, int **ret)

  int out_size = 4;

  int out_count = 0;

  int *out = (int *) g_malloc (out_size * sizeof (int));

  for (i = 0; i < array_count; i++)

      for (j = 0; j < 32; j++)

          if (array[i] & (1 << j))

              if (out_count == out_size - 2)

              out[out_count++] = i * 32 + j;

  out[out_count] = BITARRAY_SEQ_TERM;

  *ret = out;

  return TRUE;

read_mr (DBusMessageIter *iter, MatchRulePrivate *mrp)

  dbus_message_iter_recurse (iter, &iter_struct);

  dbus_message_iter_recurse (&iter_struct, &iter_array);

  dbus_message_iter_get_fixed_array (&iter_array, &array, &array_count);

  bitarray_to_seq (array, array_count, &mrp->states);

  for (i = 0; mrp->states[i] != BITARRAY_SEQ_TERM; i++)

      mrp->states[i] = spi_atk_state_from_spi_state (mrp->states[i]);

  dbus_message_iter_next (&iter_struct);

  dbus_message_iter_get_basic (&iter_struct, &matchType);

  dbus_message_iter_next (&iter_struct);

  mrp->statematchtype = matchType;

  mrp->attributes = NULL;

  dbus_message_iter_recurse (&iter_struct, &iter_dict);

  while (dbus_message_iter_get_arg_type (&iter_dict) != DBUS_TYPE_INVALID)

      dbus_message_iter_recurse (&iter_dict, &iter_dict_entry);

      dbus_message_iter_get_basic (&iter_dict_entry, &key);

      dbus_message_iter_next (&iter_dict_entry);

      dbus_message_iter_get_basic (&iter_dict_entry, &val);

      p = q = val;

          if (*q == '\0' || (*q == ':' && (q == val || q[-1] != '\\')))

              attr = g_new (AtkAttribute, 1);

              attr->name = g_strdup (key);

              attr->value = g_strdup (p);

              attr->value[q - p] = '\0';

              tmp = attr->value;

              while (*tmp != '\0')

                  if (*tmp == '\\')

                    tmp++;

              mrp->attributes = g_slist_prepend (mrp->attributes, attr);

              if (*q == '\0')

                break;

            q++;

      dbus_message_iter_next (&iter_dict);

  dbus_message_iter_next (&iter_struct);

  dbus_message_iter_get_basic (&iter_struct, &matchType);

  mrp->attributematchtype = matchType;

  dbus_message_iter_next (&iter_struct);

  dbus_message_iter_recurse (&iter_struct, &iter_array);

  dbus_message_iter_get_fixed_array (&iter_array, &array, &array_count);

  bitarray_to_seq (array, array_count, &mrp->roles);

  dbus_message_iter_next (&iter_struct);

  dbus_message_iter_get_basic (&iter_struct, &matchType);

  mrp->rolematchtype = matchType;

  dbus_message_iter_next (&iter_struct);

  dbus_message_iter_recurse (&iter_struct, &iter_array);

  mrp->ifaces = g_new0 (gchar *, 16);

  i = 0;

  while (i < 15 && dbus_message_iter_get_arg_type (&iter_array) != DBUS_TYPE_INVALID)

  dbus_message_iter_next (&iter_struct);

  dbus_message_iter_get_basic (&iter_struct, &matchType);

  mrp->interfacematchtype = matchType;

  dbus_message_iter_next (&iter_struct);

  dbus_message_iter_get_basic (&iter_struct, &mrp->invert);

  dbus_message_iter_next (iter);

  return TRUE;

return_and_free_list (DBusMessage *message, GList *ls)

  reply = dbus_message_new_method_return (message);

  if (!reply)

  dbus_message_iter_init_append (reply, &iter);

  if (!dbus_message_iter_open_container (&iter, DBUS_TYPE_ARRAY, "(so)", &iter_array))

  for (item = ls; item; item = g_list_next (item))

      spi_object_append_reference (&iter_array, ATK_OBJECT (item->data));

  if (!dbus_message_iter_close_container (&iter, &iter_array))

  g_list_free (ls);

  return reply;

free_mrp_data (MatchRulePrivate *mrp)

  g_free (mrp->states);

  atk_attribute_set_free (mrp->attributes);

  g_free (mrp->roles);

  g_strfreev (mrp->ifaces);

}

inorder (AtkObject *collection, MatchRulePrivate *mrp, GList *ls, gint kount, gint max, AtkObject *obj, gboolean flag, AtkObject *pobj, dbus_bool_t traverse)

  int i = 0;

  kount = sort_order_canonical (mrp, ls, kount, max, obj, 0, TRUE,

  while ((max == 0 || kount < max) && obj && obj != collection)

      AtkObject *parent = atk_object_get_parent (obj);

      i = atk_object_get_index_in_parent (obj);

      kount = sort_order_canonical (mrp, ls, kount, max, parent,

                                    i + 1, TRUE, FALSE, TRUE, TRUE);

      obj = parent;

  if (max == 0 || kount < max)

      kount = sort_order_canonical (mrp, ls, kount, max,

                                    obj, i + 1, TRUE, FALSE, TRUE, TRUE);

  return kount;

GetMatchesInOrder (DBusMessage *message,

  GList *ls = NULL;

  ls = g_list_append (ls, current_object);

  obj = ATK_OBJECT (spi_register_path_to_object (spi_global_register, dbus_message_get_path (message)));

  inorder (obj, mrp, ls, 0, count,

  ls = g_list_remove (ls, ls->data);

  if (sortby == ATSPI_Collection_SORT_ORDER_REVERSE_CANONICAL)

  free_mrp_data (mrp);

  return return_and_free_list (message, ls);

GetMatchesInBackOrder (DBusMessage *message,

  GList *ls = NULL;

  ls = g_list_append (ls, current_object);

  collection = ATK_OBJECT (spi_register_path_to_object (spi_global_register, dbus_message_get_path (message)));

  sort_order_rev_canonical (mrp, ls, 0, count, current_object,

  ls = g_list_remove (ls, ls->data);

  if (sortby == ATSPI_Collection_SORT_ORDER_REVERSE_CANONICAL)

  free_mrp_data (mrp);

  return return_and_free_list (message, ls);

impl_GetMatchesFrom (DBusConnection *bus, DBusMessage *message, void *user_data)

  char *current_object_path = NULL;

  signature = dbus_message_get_signature (message);

  if (strcmp (signature, "o(aiia{ss}iaiiasib)uuib") != 0)

  dbus_message_iter_init (message, &iter);

  dbus_message_iter_get_basic (&iter, &current_object_path);

  current_object = ATK_OBJECT (spi_register_path_to_object (spi_global_register, current_object_path));

  if (!current_object)

  dbus_message_iter_next (&iter);

  if (!read_mr (&iter, &rule))

  dbus_message_iter_get_basic (&iter, &sortby);

  dbus_message_iter_next (&iter);

  dbus_message_iter_get_basic (&iter, &tree);

  dbus_message_iter_next (&iter);

  dbus_message_iter_get_basic (&iter, &count);

  dbus_message_iter_next (&iter);

  dbus_message_iter_get_basic (&iter, &traverse);

  dbus_message_iter_next (&iter);

  switch (tree)

    case ATSPI_Collection_TREE_INORDER:

      return GetMatchesInOrder (message, current_object,

impl_GetMatchesTo (DBusConnection *bus, DBusMessage *message, void *user_data)

  char *current_object_path = NULL;

  signature = dbus_message_get_signature (message);

  if (strcmp (signature, "o(aiia{ss}iaiiasib)uubib") != 0)

  dbus_message_iter_init (message, &iter);

  dbus_message_iter_get_basic (&iter, &current_object_path);

  current_object = ATK_OBJECT (spi_register_path_to_object (spi_global_register, current_object_path));

  if (!current_object)

  dbus_message_iter_next (&iter);

  if (!read_mr (&iter, &rule))

  dbus_message_iter_get_basic (&iter, &sortby);

  dbus_message_iter_next (&iter);

  dbus_message_iter_get_basic (&iter, &tree);

  dbus_message_iter_next (&iter);

  dbus_message_iter_get_basic (&iter, &recurse);

  dbus_message_iter_next (&iter);

  dbus_message_iter_get_basic (&iter, &count);

  dbus_message_iter_next (&iter);

  dbus_message_iter_get_basic (&iter, &traverse);

  dbus_message_iter_next (&iter);

  switch (tree)

    case ATSPI_Collection_TREE_INORDER:

      return GetMatchesInBackOrder (message, current_object,

impl_GetMatches (DBusConnection *bus, DBusMessage *message, void *user_data)

  AtkObject *obj = ATK_OBJECT (spi_register_path_to_object (spi_global_register, dbus_message_get_path (message)));

  GList *ls = NULL;

  signature = dbus_message_get_signature (message);

  if (strcmp (signature, "(aiia{ss}iaiiasib)uib") != 0)

  dbus_message_iter_init (message, &iter);

  if (!read_mr (&iter, &rule))

  dbus_message_iter_get_basic (&iter, &sortby);

  dbus_message_iter_next (&iter);

  dbus_message_iter_get_basic (&iter, &count);

  dbus_message_iter_next (&iter);

  dbus_message_iter_get_basic (&iter, &traverse);

  dbus_message_iter_next (&iter);

  ls = g_list_prepend (ls, obj);

  count = query_exec (&rule, sortby, ls, 0, count,

  ls = g_list_remove (ls, ls->data);

  if (sortby == ATSPI_Collection_SORT_ORDER_REVERSE_CANONICAL)

  free_mrp_data (&rule);

  return return_and_free_list (message, ls);

spi_initialize_collection (DRoutePath *path)

  spi_atk_add_interface (path,

};