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