atk-adaptor/collection-adaptor.c

   1 /*
   2  * AT-SPI - Assistive Technology Service Provider Interface
   3  * (Gnome Accessibility Project; http://developer.gnome.org/projects/gap)
   4  *
   5  * Copyright 2007 IBM Corp.
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Library General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Library General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Library General Public
  18  * License along with this library; if not, write to the
  19  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  20  * Boston, MA 02111-1307, USA.
  21  */
  22
  23 /* collection.c: implements the Collection interface */
  24
  25 #include <string.h>
  26
  27 #include <atk/atk.h>
  28 #include <droute/droute.h>
  29
  30 #include "accessible-register.h"
  31 #include "accessible-marshaller.h"
  32
  33 #include "common/bitarray.h"
  34 #include "common/spi-dbus.h"
  35 #include "common/spi-stateset.h"
  36
  37 typedef struct _MatchRulePrivate MatchRulePrivate;
  38 struct _MatchRulePrivate
  39 {
  40   gint *states;
  41   Accessibility_Collection_MatchType statematchtype;
  42   AtkAttributeSet *attributes;
  43   Accessibility_Collection_MatchType attributematchtype;
  44   gint *roles;
  45   Accessibility_Collection_MatchType rolematchtype;
  46   gchar **ifaces;
  47   Accessibility_Collection_MatchType interfacematchtype;
  48   gboolean invert;
  49 };
  50
  51 static gboolean
  52 child_interface_p (AtkObject * child, gchar * repo_id)
  53 {
  54   if (!strcasecmp (repo_id, "action"))
  55     return atk_is_action (child);
  56   if (!strcasecmp (repo_id, "component"))
  57     return atk_is_component (child);
  58   if (!strcasecmp (repo_id, "editabletext"))
  59     return atk_is_editable_text (child);
  60   if (!strcasecmp (repo_id, "text"))
  61     return atk_is_text (child);
  62   if (!strcasecmp (repo_id, "hypertext"))
  63     return atk_is_hypertext (child);
  64   if (!strcasecmp (repo_id, "image"))
  65     return atk_is_image (child);
  66   if (!strcasecmp (repo_id, "selection"))
  67     return atk_is_selection (child);
  68   if (!strcasecmp (repo_id, "table"))
  69     return atk_is_table (child);
  70   if (!strcasecmp (repo_id, "value"))
  71     return atk_is_value (child);
  72   if (!strcasecmp (repo_id, "streamablecontent"))
  73     return atk_is_streamable_content (child);
  74   if (!strcasecmp (repo_id, "document"))
  75     return atk_is_document (child);
  76   return FALSE;
  77 }
  78
  79 #define child_collection_p(ch) (TRUE)
  80
  81 static gboolean
  82 match_states_all_p (AtkObject * child, gint * set)
  83 {
  84   AtkStateSet *chs;
  85   gint i;
  86   gboolean ret = TRUE;
  87
  88   if (set == NULL)
  89     return TRUE;
  90
  91   chs = atk_object_ref_state_set (child);
  92
  93   // TODO: use atk-state_set_contains_states; would be more efficient
  94   for (i = 0; set[i] != BITARRAY_SEQ_TERM; i++)
  95     {
  96       if (!atk_state_set_contains_state (chs, set[i]))
  97         {
  98           ret = FALSE;
  99           break;
 100         }
 101     }
 102
 103   g_object_unref (chs);
 104   return ret;
 105 }
 106
 107 static gboolean
 108 match_states_any_p (AtkObject * child, gint * set)
 109 {
 110   AtkStateSet *chs;
 111   gint i;
 112   gboolean ret = FALSE;
 113
 114   if (set == NULL)
 115     return TRUE;
 116
 117   chs = atk_object_ref_state_set (child);
 118
 119   for (i = 0; set[i] != BITARRAY_SEQ_TERM; i++)
 120     {
 121       if (!atk_state_set_contains_state (chs, set[i]))
 122         {
 123           ret = TRUE;
 124           break;
 125         }
 126     }
 127
 128   g_object_unref (chs);
 129   return ret;
 130 }
 131
 132 static gboolean
 133 match_states_none_p (AtkObject * child, gint * set)
 134 {
 135   AtkStateSet *chs;
 136   gint i;
 137   gboolean ret = TRUE;
 138
 139   if (set == NULL)
 140     return TRUE;
 141
 142   chs = atk_object_ref_state_set (child);
 143
 144   for (i = 0; set[i] != BITARRAY_SEQ_TERM; i++)
 145     {
 146       if (atk_state_set_contains_state (chs, set[i]))
 147         {
 148           ret = FALSE;
 149           break;
 150         }
 151     }
 152
 153   g_object_unref (chs);
 154   return ret;
 155 }
 156
 157 // TODO: need to convert at-spi roles/states to atk roles/states */
 158 static gboolean
 159 match_states_lookup (AtkObject * child, MatchRulePrivate * mrp)
 160 {
 161   switch (mrp->statematchtype)
 162     {
 163     case Accessibility_Collection_MATCH_ALL:
 164       if (match_states_all_p (child, mrp->states))
 165         return TRUE;
 166       break;
 167
 168     case Accessibility_Collection_MATCH_ANY:
 169       if (match_states_any_p (child, mrp->states))
 170         return TRUE;
 171       break;
 172
 173     case Accessibility_Collection_MATCH_NONE:
 174       if (match_states_none_p (child, mrp->states))
 175         return TRUE;
 176       break;
 177
 178     default:
 179       break;
 180     }
 181
 182   return FALSE;
 183 }
 184
 185 // TODO: Map at-spi -> atk roles at mrp creation instead of doing this;
 186 // would be more efficient
 187 #define spi_get_role(obj) spi_accessible_role_from_atk_role(atk_object_get_role(obj))
 188
 189 static gboolean
 190 match_roles_all_p (AtkObject * child, gint * roles)
 191 {
 192   if (roles == NULL || roles[0] == BITARRAY_SEQ_TERM)
 193     return TRUE;
 194   else if (roles[1] != BITARRAY_SEQ_TERM)
 195     return FALSE;
 196
 197   return (atk_object_get_role (child) == roles[0]);
 198
 199 }
 200
 201 static gboolean
 202 match_roles_any_p (AtkObject * child, gint * roles)
 203 {
 204   Accessibility_Role role;
 205   int i;
 206
 207   if (roles == NULL || roles[0] == BITARRAY_SEQ_TERM)
 208     return TRUE;
 209
 210   role = spi_accessible_role_from_atk_role (atk_object_get_role (child));
 211
 212   for (i = 0; roles[i] != BITARRAY_SEQ_TERM; i++)
 213     if (role == roles[i])
 214       return TRUE;
 215
 216   return FALSE;
 217 }
 218
 219 static gboolean
 220 match_roles_none_p (AtkObject * child, gint * roles)
 221 {
 222   AtkRole role;
 223   int i;
 224
 225   if (roles == NULL || roles[0] == BITARRAY_SEQ_TERM)
 226     return TRUE;
 227
 228   role = atk_object_get_role (child);
 229
 230   for (i = 0; roles[i] != BITARRAY_SEQ_TERM; i++)
 231     if (role == roles[i])
 232       return FALSE;
 233
 234   return TRUE;
 235 }
 236
 237 static gboolean
 238 match_roles_lookup (AtkObject * child, MatchRulePrivate * mrp)
 239 {
 240   switch (mrp->rolematchtype)
 241     {
 242     case Accessibility_Collection_MATCH_ALL:
 243       if (match_roles_all_p (child, mrp->roles))
 244         return TRUE;
 245       break;
 246
 247     case Accessibility_Collection_MATCH_ANY:
 248       if (match_roles_any_p (child, mrp->roles))
 249         return TRUE;
 250       break;
 251
 252     case Accessibility_Collection_MATCH_NONE:
 253       if (match_roles_none_p (child, mrp->roles))
 254         return TRUE;
 255       break;
 256
 257     default:
 258       break;
 259
 260     }
 261   return FALSE;
 262 }
 263
 264 static gboolean
 265 match_interfaces_all_p (AtkObject * obj, gchar ** ifaces)
 266 {
 267   gint i;
 268
 269   if (ifaces == NULL)
 270     return TRUE;
 271
 272   for (i = 0; ifaces[i]; i++)
 273     if (!child_interface_p (obj, ifaces[i]))
 274       {
 275         return FALSE;
 276       }
 277   return TRUE;
 278 }
 279
 280 static gboolean
 281 match_interfaces_any_p (AtkObject * obj, gchar ** ifaces)
 282 {
 283   gint i;
 284
 285   if (ifaces == NULL)
 286     return TRUE;
 287
 288
 289   for (i = 0; ifaces[i]; i++)
 290     if (child_interface_p (obj, ifaces[i]))
 291       {
 292         return TRUE;
 293       }
 294   return FALSE;
 295 }
 296
 297 static gboolean
 298 match_interfaces_none_p (AtkObject * obj, gchar ** ifaces)
 299 {
 300   gint i;
 301
 302   for (i = 0; ifaces[i]; i++)
 303     if (child_interface_p (obj, ifaces[i]))
 304       return FALSE;
 305
 306   return TRUE;
 307 }
 308
 309 static gboolean
 310 match_interfaces_lookup (AtkObject * child, MatchRulePrivate * mrp)
 311 {
 312   switch (mrp->interfacematchtype)
 313     {
 314
 315     case Accessibility_Collection_MATCH_ALL:
 316       if (match_interfaces_all_p (child, mrp->ifaces))
 317         return TRUE;
 318       break;
 319
 320     case Accessibility_Collection_MATCH_ANY:
 321       if (match_interfaces_any_p (child, mrp->ifaces))
 322         return TRUE;
 323       break;
 324
 325     case Accessibility_Collection_MATCH_NONE:
 326       if (match_interfaces_none_p (child, mrp->ifaces))
 327         return TRUE;
 328       break;
 329
 330     default:
 331       break;
 332     }
 333
 334   return FALSE;
 335 }
 336
 337 #define split_attributes(attributes) (g_strsplit (attributes, ";", 0))
 338
 339 static gboolean
 340 match_attributes_all_p (AtkObject * child, AtkAttributeSet * attributes)
 341 {
 342   int i, k;
 343   AtkAttributeSet *oa;
 344   gint length, oa_length;
 345   gboolean flag = FALSE;
 346
 347   if (attributes == NULL || g_slist_length (attributes) == 0)
 348     return TRUE;
 349
 350   oa = atk_object_get_attributes (child);
 351   length = g_slist_length (attributes);
 352   oa_length = g_slist_length (oa);
 353
 354   for (i = 0; i < length; i++)
 355     {
 356       AtkAttribute *attr = g_slist_nth_data (attributes, i);
 357       for (k = 0; k < oa_length; k++)
 358         {
 359           AtkAttribute *oa_attr = g_slist_nth_data (attributes, i);
 360           if (!g_ascii_strcasecmp (oa_attr->name, attr->name) &&
 361               !g_ascii_strcasecmp (oa_attr->value, attr->value))
 362             {
 363               flag = TRUE;
 364               break;
 365             }
 366           else
 367             flag = FALSE;
 368         }
 369       if (!flag)
 370         {
 371           atk_attribute_set_free (oa);
 372           return FALSE;
 373         }
 374     }
 375   atk_attribute_set_free (oa);
 376   return TRUE;
 377 }
 378
 379 static gboolean
 380 match_attributes_any_p (AtkObject * child, AtkAttributeSet * attributes)
 381 {
 382   int i, k;
 383
 384   AtkAttributeSet *oa;
 385   gint length, oa_length;
 386
 387   length = g_slist_length (attributes);
 388   if (length == 0)
 389     return TRUE;
 390
 391   oa = atk_object_get_attributes (child);
 392   oa_length = g_slist_length (oa);
 393
 394   for (i = 0; i < length; i++)
 395     {
 396       AtkAttribute *attr = g_slist_nth_data (attributes, i);
 397       for (k = 0; k < oa_length; k++)
 398         {
 399           AtkAttribute *oa_attr = g_slist_nth_data (attributes, i);
 400           if (!g_ascii_strcasecmp (oa_attr->name, attr->name) &&
 401               !g_ascii_strcasecmp (oa_attr->value, attr->value))
 402             {
 403               atk_attribute_set_free (oa);
 404               return TRUE;
 405             }
 406         }
 407     }
 408   atk_attribute_set_free (oa);
 409   return FALSE;
 410 }
 411
 412 static gboolean
 413 match_attributes_none_p (AtkObject * child, AtkAttributeSet * attributes)
 414 {
 415   int i, k;
 416
 417   AtkAttributeSet *oa;
 418   gint length, oa_length;
 419
 420   length = g_slist_length (attributes);
 421   if (length == 0)
 422     return TRUE;
 423
 424   oa = atk_object_get_attributes (child);
 425   oa_length = g_slist_length (oa);
 426
 427   for (i = 0; i < length; i++)
 428     {
 429       AtkAttribute *attr = g_slist_nth_data (attributes, i);
 430       for (k = 0; k < oa_length; k++)
 431         {
 432           AtkAttribute *oa_attr = g_slist_nth_data (attributes, i);
 433           if (!g_ascii_strcasecmp (oa_attr->name, attr->name) &&
 434               !g_ascii_strcasecmp (oa_attr->value, attr->value))
 435             {
 436               atk_attribute_set_free (oa);
 437               return FALSE;
 438             }
 439         }
 440     }
 441   atk_attribute_set_free (oa);
 442   return TRUE;
 443 }
 444
 445 static gboolean
 446 match_attributes_lookup (AtkObject * child, MatchRulePrivate * mrp)
 447 {
 448   switch (mrp->attributematchtype)
 449     {
 450
 451     case Accessibility_Collection_MATCH_ALL:
 452       if (match_attributes_all_p (child, mrp->attributes))
 453         return TRUE;
 454       break;
 455
 456     case Accessibility_Collection_MATCH_ANY:
 457       if (match_attributes_any_p (child, mrp->attributes))
 458         return TRUE;
 459       break;
 460
 461     case Accessibility_Collection_MATCH_NONE:
 462       if (match_attributes_none_p (child, mrp->attributes))
 463         return TRUE;
 464       break;
 465
 466     default:
 467       break;
 468     }
 469   return FALSE;
 470 }
 471
 472 static gboolean
 473 traverse_p (AtkObject * child, const gboolean traverse)
 474 {
 475   if (traverse)
 476     return TRUE;
 477   else
 478     return !child_collection_p (child);
 479 }
 480
 481 static int
 482 sort_order_canonical (MatchRulePrivate * mrp, GList * ls,
 483                       gint kount, gint max,
 484                       AtkObject * obj, glong index, gboolean flag,
 485                       AtkObject * pobj, gboolean recurse, gboolean traverse)
 486 {
 487   gint i = index;
 488   glong acount = atk_object_get_n_accessible_children (obj);
 489   gboolean prev = pobj ? TRUE : FALSE;
 490
 491   for (; i < acount && (max == 0 || kount < max); i++)
 492     {
 493       AtkObject *child = atk_object_ref_accessible_child (obj, i);
 494
 495       g_object_unref (child);
 496       if (prev && child == pobj)
 497         {
 498           return kount;
 499         }
 500
 501       if (flag && match_interfaces_lookup (child, mrp)
 502           && match_states_lookup (child, mrp)
 503           && match_roles_lookup (child, mrp)
 504           && match_attributes_lookup (child, mrp))
 505         {
 506
 507           ls = g_list_append (ls, child);
 508           kount++;
 509         }
 510
 511       if (!flag)
 512         flag = TRUE;
 513
 514       if (recurse && traverse_p (child, traverse))
 515         kount = sort_order_canonical (mrp, ls, kount,
 516                                       max, child, 0, TRUE,
 517                                       pobj, recurse, traverse);
 518     }
 519   return kount;
 520 }
 521
 522 static int
 523 sort_order_rev_canonical (MatchRulePrivate * mrp, GList * ls,
 524                           gint kount, gint max,
 525                           AtkObject * obj, gboolean flag, AtkObject * pobj)
 526 {
 527   AtkObject *nextobj;
 528   AtkObject *parent;
 529   glong indexinparent;
 530
 531   /* This breaks us out of the recursion. */
 532   if (!obj || obj == pobj)
 533     {
 534       return kount;
 535     }
 536
 537   /* Add to the list if it matches */
 538   if (flag && match_interfaces_lookup (obj, mrp)
 539       && match_states_lookup (obj, mrp)
 540       && match_roles_lookup (obj, mrp) && match_attributes_lookup (obj, mrp))
 541     {
 542       ls = g_list_append (ls, obj);
 543       kount++;
 544     }
 545
 546   if (!flag)
 547     flag = TRUE;
 548
 549   /* Get the current nodes index in it's parent and the parent object. */
 550   indexinparent = atk_object_get_index_in_parent (obj);
 551   parent = atk_object_get_parent (obj);
 552
 553   if (indexinparent > 0)
 554     {
 555       /* there are still some siblings to visit so get the previous sibling
 556          and get it's last descendant.
 557          First, get the previous sibling */
 558       nextobj = atk_object_ref_accessible_child (parent, indexinparent - 1);
 559       g_object_unref (nextobj);
 560
 561       /* Now, drill down the right side to the last descendant */
 562       while (atk_object_get_n_accessible_children (nextobj) > 0)
 563         {
 564           nextobj = atk_object_ref_accessible_child (nextobj,
 565                                                      atk_object_get_n_accessible_children
 566                                                      (nextobj) - 1);
 567           g_object_unref (nextobj);
 568         }
 569       /* recurse with the last descendant */
 570       kount = sort_order_rev_canonical (mrp, ls, kount, max,
 571                                         nextobj, TRUE, pobj);
 572     }
 573   else
 574     {
 575       /* no more siblings so next node must be the parent */
 576       kount = sort_order_rev_canonical (mrp, ls, kount, max,
 577                                         parent, TRUE, pobj);
 578
 579     }
 580   return kount;
 581 }
 582
 583 static int
 584 query_exec (MatchRulePrivate * mrp, Accessibility_Collection_SortOrder sortby,
 585             GList * ls, gint kount, gint max,
 586             AtkObject * obj, glong index,
 587             gboolean flag,
 588             AtkObject * pobj, gboolean recurse, gboolean traverse)
 589 {
 590   switch (sortby)
 591     {
 592     case Accessibility_Collection_SORT_ORDER_CANONICAL:
 593       kount = sort_order_canonical (mrp, ls, 0, max, obj, index, flag,
 594                                     pobj, recurse, traverse);
 595       break;
 596     case Accessibility_Collection_SORT_ORDER_REVERSE_CANONICAL:
 597       kount = sort_order_canonical (mrp, ls, 0, max, obj, index, flag,
 598                                     pobj, recurse, traverse);
 599       break;
 600     default:
 601       kount = 0;
 602       g_warning ("Sort method not implemented yet");
 603       break;
 604     }
 605
 606   return kount;
 607 }
 608
 609 static gboolean
 610 bitarray_to_seq (int *array, int array_count, int **ret)
 611 {
 612   int out_size = 4;
 613   int out_count = 0;
 614   int i, j;
 615   int *out = (int *) g_malloc (out_size * sizeof (int));
 616
 617   if (!out)
 618     return FALSE;
 619   for (i = 0; i < array_count; i++)
 620     {
 621       for (j = 0; j < 32; j++)
 622         {
 623           if (array[i] & (1 << j))
 624             {
 625               if (out_count == out_size - 2)
 626                 {
 627                   out_size <<= 1;
 628                   out = (int *) g_realloc (out, out_size * sizeof (int));
 629                   if (!out)
 630                     return FALSE;
 631                 }
 632               out[out_count++] = i * 32 + j;
 633             }
 634         }
 635     }
 636   out[out_count] = BITARRAY_SEQ_TERM;
 637   *ret = out;
 638   return TRUE;
 639 }
 640
 641
 642 static dbus_bool_t
 643 read_mr (DBusMessageIter * iter, MatchRulePrivate * mrp)
 644 {
 645   DBusMessageIter mrc, arrayc;
 646   dbus_uint32_t *array;
 647   dbus_int32_t matchType;
 648   int array_count;
 649   AtkAttribute *attr;
 650   int i;
 651   const char *str;
 652   char *interfaces = NULL;
 653
 654   dbus_message_iter_recurse (iter, &mrc);
 655   dbus_message_iter_recurse (&mrc, &arrayc);
 656   dbus_message_iter_get_fixed_array (&arrayc, &array, &array_count);
 657   bitarray_to_seq (array, array_count, &mrp->states);
 658   for (i = 0; mrp->states[i] != BITARRAY_SEQ_TERM; i++)
 659     {
 660       mrp->states[i] = spi_atk_state_from_spi_state (mrp->states[i]);
 661     }
 662   dbus_message_iter_next (&mrc);
 663   dbus_message_iter_get_basic (&mrc, &matchType);
 664   dbus_message_iter_next (&mrc);
 665   mrp->statematchtype = matchType;;
 666   /* attributes */
 667   mrp->attributes = NULL;
 668   if (dbus_message_iter_get_arg_type (&mrc) == DBUS_TYPE_STRING)
 669     {
 670       char *str;
 671       gchar **attributes;
 672       gchar **pp;
 673       dbus_message_iter_get_basic (&mrc, &str);
 674       attributes = g_strsplit (str, "\n", -1);
 675       for (pp = attributes; *pp; pp++)
 676         {
 677           str = *pp;
 678           attr = g_new (AtkAttribute, 1);
 679           if (attr)
 680             {
 681               int len = strcspn (str, ":");
 682               attr->name = g_strndup (str, len);
 683               if (str[len] == ':')
 684                 {
 685                   len++;
 686                   if (str[len] == ' ')
 687                     len++;
 688                   attr->value = g_strdup (str + len);
 689                 }
 690               else
 691                 attr->value = NULL;
 692               mrp->attributes = g_slist_prepend (mrp->attributes, attr);
 693             }
 694         }
 695       g_strfreev (attributes);
 696     }
 697   else
 698     {
 699       dbus_message_iter_recurse (&mrc, &arrayc);
 700       while (dbus_message_iter_get_arg_type (&arrayc) != DBUS_TYPE_INVALID)
 701         {
 702           dbus_message_iter_get_basic (&arrayc, &str);
 703           // TODO: remove this print
 704           g_print ("Got attribute: %s\n", str);
 705           attr = g_new (AtkAttribute, 1);
 706           if (attr)
 707             {
 708               int len = strcspn (str, ":");
 709               attr->name = g_strndup (str, len);
 710               if (str[len] == ':')
 711                 {
 712                   len++;
 713                   if (str[len] == ' ')
 714                     len++;
 715                   attr->value = g_strdup (str + len);
 716                 }
 717               else
 718                 attr->value = NULL;
 719               mrp->attributes = g_slist_prepend (mrp->attributes, attr);
 720             }
 721           dbus_message_iter_next (&arrayc);
 722         }
 723     }
 724   dbus_message_iter_next (&mrc);
 725   dbus_message_iter_get_basic (&mrc, &matchType);
 726   mrp->attributematchtype = matchType;;
 727   dbus_message_iter_next (&mrc);
 728   /* Get roles and role match */
 729   dbus_message_iter_recurse (&mrc, &arrayc);
 730   dbus_message_iter_get_fixed_array (&arrayc, &array, &array_count);
 731   bitarray_to_seq (array, array_count, &mrp->roles);
 732   dbus_message_iter_next (&mrc);
 733   dbus_message_iter_get_basic (&mrc, &matchType);
 734   mrp->rolematchtype = matchType;;
 735   dbus_message_iter_next (&mrc);
 736   /* Get interfaces and interface match */
 737   dbus_message_iter_get_basic (&mrc, &interfaces);
 738   dbus_message_iter_next (&mrc);
 739   mrp->ifaces = g_strsplit (interfaces, ";", 0);
 740   dbus_message_iter_get_basic (&mrc, &matchType);
 741   mrp->interfacematchtype = matchType;;
 742   dbus_message_iter_next (&mrc);
 743   /* get invert */
 744   dbus_message_iter_get_basic (&mrc, &mrp->invert);
 745   dbus_message_iter_next (iter);
 746   return TRUE;
 747 }
 748
 749 static DBusMessage *
 750 return_and_free_list (DBusMessage * message, GList * ls)
 751 {
 752   DBusMessage *reply;
 753   DBusMessageIter iter, iter_array;
 754   GList *item;
 755
 756   reply = dbus_message_new_method_return (message);
 757   if (!reply)
 758     return NULL;
 759   dbus_message_iter_init_append (reply, &iter);
 760   if (!dbus_message_iter_open_container
 761       (&iter, DBUS_TYPE_ARRAY, "(so)", &iter_array))
 762     goto oom;
 763   for (item = ls; item; item = g_list_next (item))
 764     {
 765       spi_dbus_append_name_and_path (message, &iter_array,
 766                                      ATK_OBJECT (item->data), TRUE, FALSE);
 767     }
 768   if (!dbus_message_iter_close_container (&iter, &iter_array))
 769     goto oom;
 770   g_list_free (ls);
 771   return reply;
 772 oom:
 773   // TODO: Handle out of memory
 774   g_list_free (ls);
 775   return reply;
 776 }
 777
 778 static void
 779 free_mrp_data (MatchRulePrivate * mrp)
 780 {
 781   g_free (mrp->states);
 782   atk_attribute_set_free (mrp->attributes);
 783   g_free (mrp->roles);
 784   g_strfreev (mrp->ifaces);
 785 }
 786
 787 static DBusMessage *
 788 GetMatchesFrom (DBusMessage * message,
 789                 AtkObject * current_object,
 790                 MatchRulePrivate * mrp,
 791                 const Accessibility_Collection_SortOrder sortby,
 792                 const dbus_bool_t isrestrict,
 793                 dbus_int32_t count, const dbus_bool_t traverse)
 794 {
 795   GList *ls = NULL;
 796   AtkObject *parent;
 797   glong index = atk_object_get_index_in_parent (current_object);
 798   gint kount = 0;
 799
 800   ls = g_list_append (ls, current_object);
 801
 802   if (!isrestrict)
 803     {
 804       parent = atk_object_get_parent (current_object);
 805       kount = query_exec (mrp, sortby, ls, 0, count, parent, index,
 806                           FALSE, NULL, TRUE, traverse);
 807     }
 808   else
 809     kount = query_exec (mrp, sortby, ls, 0, count,
 810                         current_object, 0, FALSE, NULL, TRUE, traverse);
 811
 812   ls = g_list_remove (ls, ls->data);
 813
 814   if (sortby == Accessibility_Collection_SORT_ORDER_REVERSE_CANONICAL)
 815     ls = g_list_reverse (ls);
 816
 817   free_mrp_data (mrp);
 818   return return_and_free_list (message, ls);
 819 }
 820
 821 /*
 822   inorder traversal from a given object in the hierarchy
 823 */
 824
 825 static int
 826 inorder (AtkObject * collection, MatchRulePrivate * mrp,
 827          GList * ls, gint kount, gint max,
 828          AtkObject * obj,
 829          gboolean flag, AtkObject * pobj, dbus_bool_t traverse)
 830 {
 831   int i = 0;
 832
 833   /* First, look through the children recursively. */
 834   kount = sort_order_canonical (mrp, ls, kount, max, obj, 0, TRUE,
 835                                 NULL, TRUE, TRUE);
 836
 837   /* Next, we look through the right subtree */
 838   while ((max == 0 || kount < max) && obj != collection)
 839     {
 840       AtkObject *parent = atk_object_get_parent (obj);
 841       i = atk_object_get_index_in_parent (obj);
 842       kount = sort_order_canonical (mrp, ls, kount, max, parent,
 843                                     i + 1, TRUE, FALSE, TRUE, TRUE);
 844       obj = parent;
 845     }
 846
 847   if (kount < max)
 848     {
 849       kount = sort_order_canonical (mrp, ls, kount, max,
 850                                     obj, i + 1, TRUE, FALSE, TRUE, TRUE);
 851     }
 852
 853   return kount;
 854 }
 855
 856 /*
 857   GetMatchesInOrder: get matches from a given object in an inorder traversal.
 858 */
 859
 860 static DBusMessage *
 861 GetMatchesInOrder (DBusMessage * message,
 862                    AtkObject * current_object,
 863                    MatchRulePrivate * mrp,
 864                    const Accessibility_Collection_SortOrder sortby,
 865                    const dbus_bool_t recurse,
 866                    dbus_int32_t count, const dbus_bool_t traverse)
 867 {
 868   GList *ls = NULL;
 869   AtkObject *obj;
 870   gint kount = 0;
 871
 872   ls = g_list_append (ls, current_object);
 873
 874   obj = atk_dbus_path_to_object (dbus_message_get_path (message));
 875
 876   kount = inorder (obj, mrp, ls, 0, count,
 877                    current_object, TRUE, NULL, traverse);
 878
 879   ls = g_list_remove (ls, ls->data);
 880
 881   if (sortby == Accessibility_Collection_SORT_ORDER_REVERSE_CANONICAL)
 882     ls = g_list_reverse (ls);
 883
 884   free_mrp_data (mrp);
 885   return return_and_free_list (message, ls);
 886 }
 887
 888 /*
 889   GetMatchesInBackOrder: get matches from a given object in a
 890   reverse order traversal.
 891 */
 892
 893 static DBusMessage *
 894 GetMatchesInBackOrder (DBusMessage * message,
 895                        AtkObject * current_object,
 896                        MatchRulePrivate * mrp,
 897                        const Accessibility_Collection_SortOrder sortby,
 898                        dbus_int32_t count)
 899 {
 900   GList *ls = NULL;
 901   AtkObject *collection;
 902   gint kount = 0;
 903
 904   ls = g_list_append (ls, current_object);
 905
 906   collection = atk_dbus_path_to_object (dbus_message_get_path (message));
 907
 908   kount = sort_order_rev_canonical (mrp, ls, 0, count, current_object,
 909                                     FALSE, collection);
 910
 911   ls = g_list_remove (ls, ls->data);
 912
 913   if (sortby == Accessibility_Collection_SORT_ORDER_REVERSE_CANONICAL)
 914     ls = g_list_reverse (ls);
 915
 916   free_mrp_data (mrp);
 917   return return_and_free_list (message, ls);
 918 }
 919
 920 static DBusMessage *
 921 GetMatchesTo (DBusMessage * message,
 922               AtkObject * current_object,
 923               MatchRulePrivate * mrp,
 924               const Accessibility_Collection_SortOrder sortby,
 925               const dbus_bool_t recurse,
 926               const dbus_bool_t isrestrict,
 927               dbus_int32_t count, const dbus_bool_t traverse)
 928 {
 929   GList *ls = NULL;
 930   AtkObject *obj;
 931   gint kount = 0;
 932   ls = g_list_append (ls, current_object);
 933
 934   if (recurse)
 935     {
 936       obj = atk_object_get_parent (current_object);
 937       kount = query_exec (mrp, sortby, ls, 0, count,
 938                           obj, 0, TRUE, current_object, TRUE, traverse);
 939     }
 940   else
 941     {
 942       obj = atk_dbus_path_to_object (dbus_message_get_path (message));
 943       kount = query_exec (mrp, sortby, ls, 0, count,
 944                           obj, 0, TRUE, current_object, TRUE, traverse);
 945
 946     }
 947
 948   ls = g_list_remove (ls, ls->data);
 949
 950   if (sortby != Accessibility_Collection_SORT_ORDER_REVERSE_CANONICAL)
 951     ls = g_list_reverse (ls);
 952
 953   free_mrp_data (mrp);
 954   return return_and_free_list (message, ls);
 955 }
 956
 957 static DBusMessage *
 958 impl_GetMatchesFrom (DBusConnection * bus, DBusMessage * message,
 959                      void *user_data)
 960 {
 961   char *current_object_path = NULL;
 962   AtkObject *current_object;
 963   DBusMessageIter iter;
 964   MatchRulePrivate rule;
 965   dbus_uint32_t sortby;
 966   dbus_uint32_t tree;
 967   dbus_int32_t count;
 968   dbus_bool_t traverse;
 969   GList *ls = NULL;
 970   const char *signature;
 971
 972   signature = dbus_message_get_signature (message);
 973   if (strcmp (signature, "o(aiisiaiisib)uuib") != 0 &&
 974       strcmp (signature, "o(aii(as)iaiisib)uuib") != 0)
 975     {
 976       return droute_invalid_arguments_error (message);
 977     }
 978
 979   dbus_message_iter_init (message, &iter);
 980   dbus_message_iter_get_basic (&iter, &current_object_path);
 981   current_object = atk_dbus_path_to_object (current_object_path);
 982   if (!current_object)
 983     {
 984       // TODO: object-not-found error
 985       return spi_dbus_general_error (message);
 986     }
 987   dbus_message_iter_next (&iter);
 988   if (!read_mr (&iter, &rule))
 989     {
 990       return spi_dbus_general_error (message);
 991     }
 992   dbus_message_iter_get_basic (&iter, &sortby);
 993   dbus_message_iter_next (&iter);
 994   dbus_message_iter_get_basic (&iter, &tree);
 995   dbus_message_iter_next (&iter);
 996   dbus_message_iter_get_basic (&iter, &count);
 997   dbus_message_iter_next (&iter);
 998   dbus_message_iter_get_basic (&iter, &traverse);
 999   dbus_message_iter_next (&iter);
1000
1001   switch (tree)
1002     {
1003     case Accessibility_Collection_TREE_RESTRICT_CHILDREN:
1004       return GetMatchesFrom (message, current_object,
1005                              &rule, sortby, TRUE, count, traverse);
1006       break;
1007     case Accessibility_Collection_TREE_RESTRICT_SIBLING:
1008       return GetMatchesFrom (message, current_object,
1009                              &rule, sortby, FALSE, count, traverse);
1010       break;
1011     case Accessibility_Collection_TREE_INORDER:
1012       return GetMatchesInOrder (message, current_object,
1013                                 &rule, sortby, TRUE, count, traverse);
1014       break;
1015     default:
1016       return NULL;
1017     }
1018 }
1019
1020 static DBusMessage *
1021 impl_GetMatchesTo (DBusConnection * bus, DBusMessage * message,
1022                    void *user_data)
1023 {
1024   char *current_object_path = NULL;
1025   AtkObject *current_object;
1026   DBusMessageIter iter;
1027   MatchRulePrivate rule;
1028   dbus_uint32_t sortby;
1029   dbus_uint32_t tree;
1030   dbus_bool_t recurse;
1031   dbus_int32_t count;
1032   dbus_bool_t traverse;
1033   GList *ls = NULL;
1034   const char *signature;
1035
1036   signature = dbus_message_get_signature (message);
1037   if (strcmp (signature, "o(aiisiaiisib)uubib") != 0 &&
1038       strcmp (signature, "o(aii(as)iaiisib)uubib") != 0)
1039     {
1040       return droute_invalid_arguments_error (message);
1041     }
1042
1043   dbus_message_iter_init (message, &iter);
1044   dbus_message_iter_get_basic (&iter, &current_object_path);
1045   current_object = atk_dbus_path_to_object (current_object_path);
1046   if (!current_object)
1047     {
1048       // TODO: object-not-found error
1049       return spi_dbus_general_error (message);
1050     }
1051   dbus_message_iter_next (&iter);
1052   if (!read_mr (&iter, &rule))
1053     {
1054       return spi_dbus_general_error (message);
1055     }
1056   dbus_message_iter_get_basic (&iter, &sortby);
1057   dbus_message_iter_next (&iter);
1058   dbus_message_iter_get_basic (&iter, &tree);
1059   dbus_message_iter_next (&iter);
1060   dbus_message_iter_get_basic (&iter, &recurse);
1061   dbus_message_iter_next (&iter);
1062   dbus_message_iter_get_basic (&iter, &count);
1063   dbus_message_iter_next (&iter);
1064   dbus_message_iter_get_basic (&iter, &traverse);
1065   dbus_message_iter_next (&iter);
1066
1067   switch (tree)
1068     {
1069     case Accessibility_Collection_TREE_RESTRICT_CHILDREN:
1070       return GetMatchesTo (message, current_object,
1071                            &rule, sortby, recurse, TRUE, count, traverse);
1072       break;
1073     case Accessibility_Collection_TREE_RESTRICT_SIBLING:
1074       return GetMatchesTo (message, current_object,
1075                            &rule, sortby, recurse, FALSE, count, traverse);
1076       break;
1077     case Accessibility_Collection_TREE_INORDER:
1078       return GetMatchesInBackOrder (message, current_object,
1079                                     &rule, sortby, count);
1080       break;
1081     default:
1082       return NULL;
1083     }
1084 }
1085
1086 static DBusMessage *
1087 impl_GetMatches (DBusConnection * bus, DBusMessage * message, void *user_data)
1088 {
1089   AtkObject *obj = atk_dbus_path_to_object (dbus_message_get_path (message));
1090   DBusMessageIter iter;
1091   MatchRulePrivate rule;
1092   dbus_uint32_t sortby;
1093   dbus_int32_t count;
1094   dbus_bool_t traverse;
1095   GList *ls = NULL;
1096   const char *signature;
1097
1098   signature = dbus_message_get_signature (message);
1099   if (strcmp (signature, "(aiisiaiisib)uib") != 0 &&
1100       strcmp (signature, "(aii(as)iaiisib)uib") != 0)
1101     {
1102       return droute_invalid_arguments_error (message);
1103     }
1104
1105   dbus_message_iter_init (message, &iter);
1106   if (!read_mr (&iter, &rule))
1107     {
1108       return spi_dbus_general_error (message);
1109     }
1110   dbus_message_iter_get_basic (&iter, &sortby);
1111   dbus_message_iter_next (&iter);
1112   dbus_message_iter_get_basic (&iter, &count);
1113   dbus_message_iter_next (&iter);
1114   dbus_message_iter_get_basic (&iter, &traverse);
1115   dbus_message_iter_next (&iter);
1116   ls = g_list_prepend (ls, obj);
1117   count = query_exec (&rule, sortby, ls, 0, count,
1118                       obj, 0, TRUE, NULL, TRUE, traverse);
1119   ls = g_list_remove (ls, ls->data);
1120
1121   if (sortby == Accessibility_Collection_SORT_ORDER_REVERSE_CANONICAL)
1122     ls = g_list_reverse (ls);
1123   free_mrp_data (&rule);
1124   return return_and_free_list (message, ls);
1125 }
1126
1127 static DRouteMethod methods[] = {
1128   {impl_GetMatchesFrom, "GetMatchesFrom"},
1129   {impl_GetMatchesTo, "GetMatchesTo"},
1130   {impl_GetMatches, "GetMatches"},
1131   {NULL, NULL}
1132 };
1133
1134 void
1135 spi_initialize_collection (DRoutePath * path)
1136 {
1137   droute_path_add_interface (path,
1138                              SPI_DBUS_INTERFACE_COLLECTION, methods, NULL);
1139 };