atk-adaptor/collection.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 "atk-dbus.h"
  31
  32 #include "spi-common/bitarray.h"
  33 #include "spi-common/spi-dbus.h"
  34
  35 #define get_object(message) atk_dbus_get_object(dbus_message_get_path(message))
  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    Accessibility_Role role;
 186
 187      if (roles == NULL || roles[0] == BITARRAY_SEQ_TERM) return TRUE;
 188      else if (roles[1] != BITARRAY_SEQ_TERM) return FALSE;
 189
 190      return (atk_object_get_role(child) == roles[0]);
 191
 192 }
 193
 194 static gboolean
 195 match_roles_any_p (AtkObject *child,
 196                    gint *roles)
 197 {
 198      AtkRole role;
 199      int i;
 200
 201      if (roles == NULL || roles[0] == BITARRAY_SEQ_TERM) return TRUE;
 202
 203      role = atk_object_get_role(child);
 204
 205      for (i = 0; roles[i] != BITARRAY_SEQ_TERM; i++)
 206           if (role  == roles[i])
 207                return TRUE;
 208
 209      return FALSE;
 210 }
 211
 212 static gboolean
 213 match_roles_none_p (AtkObject *child,
 214                     gint *roles)
 215 {
 216   AtkRole role;
 217      int i;
 218
 219      if (roles == NULL || roles[0] == BITARRAY_SEQ_TERM) return TRUE;
 220
 221      role = atk_object_get_role(child);
 222
 223      for (i = 0; roles[i] != BITARRAY_SEQ_TERM; i++)
 224           if (role == roles[i])
 225                return FALSE;
 226
 227      return TRUE;
 228 }
 229
 230 static gboolean
 231 match_roles_lookup (AtkObject *child,
 232                     MatchRulePrivate *mrp)
 233 {
 234       switch (mrp->rolematchtype){
 235          case Accessibility_Collection_MATCH_ALL :
 236               if (match_roles_all_p (child, mrp->roles))
 237                    return TRUE;
 238               break;
 239
 240          case  Accessibility_Collection_MATCH_ANY :
 241               if (match_roles_any_p (child, mrp->roles))
 242                    return TRUE;
 243               break;
 244
 245          case  Accessibility_Collection_MATCH_NONE :
 246               if (match_roles_none_p (child, mrp->roles))
 247                    return TRUE;
 248               break;
 249
 250       default : break;
 251
 252          }
 253       return FALSE;
 254 }
 255
 256 static gboolean
 257 match_interfaces_all_p (AtkObject *obj,
 258                         gchar **ifaces)
 259 {
 260      gint i;
 261
 262      if (ifaces == NULL)
 263        return TRUE;
 264
 265      for (i = 0; ifaces[i]; i++)
 266        if (!child_interface_p (obj, ifaces [i])){
 267                return FALSE;
 268        }
 269      return TRUE;
 270 }
 271
 272 static gboolean
 273 match_interfaces_any_p (AtkObject *obj,
 274                         gchar **ifaces)
 275 {
 276      gint i;
 277
 278      if (ifaces == NULL)
 279        return TRUE;
 280
 281
 282      for (i = 0; ifaces[i]; i++)
 283        if (child_interface_p (obj, ifaces [i])){
 284                 return TRUE;
 285        }
 286      return FALSE;
 287 }
 288
 289 static gboolean
 290 match_interfaces_none_p (AtkObject *obj,
 291                          gchar **ifaces)
 292 {
 293      gint i;
 294
 295      for (i = 0; ifaces[i]; i++)
 296            if (child_interface_p (obj, ifaces [i]))
 297                 return FALSE;
 298
 299      return TRUE;
 300 }
 301
 302 static gboolean
 303 match_interfaces_lookup (AtkObject *child,
 304                          MatchRulePrivate *mrp)
 305 {
 306      switch (mrp->interfacematchtype){
 307
 308      case Accessibility_Collection_MATCH_ALL :
 309           if (match_interfaces_all_p (child, mrp->ifaces))
 310                return TRUE;
 311           break;
 312
 313      case  Accessibility_Collection_MATCH_ANY :
 314           if (match_interfaces_any_p (child, mrp->ifaces))
 315                return TRUE;
 316           break;
 317
 318      case  Accessibility_Collection_MATCH_NONE :
 319           if (match_interfaces_none_p (child, mrp->ifaces))
 320                return TRUE;
 321           break;
 322
 323       default : break;
 324      }
 325
 326      return FALSE;
 327 }
 328
 329 #define split_attributes(attributes) (g_strsplit (attributes, ";", 0))
 330
 331 static gboolean
 332 match_attributes_all_p (AtkObject *child,
 333                         AtkAttributeSet *attributes)
 334 {
 335      int i, k;
 336      AtkAttributeSet *oa;
 337      gint length, oa_length;
 338      gboolean flag = FALSE;
 339
 340      if (attributes == NULL || g_slist_length (attributes) == 0)
 341           return TRUE;
 342
 343      oa =  atk_object_get_attributes(child);
 344      length = g_slist_length(attributes);
 345      oa_length = g_slist_length(oa);
 346
 347      for (i = 0; i < length; i++) {
 348           AtkAttribute *attr = g_slist_nth_data(attributes, i);
 349           for (k = 0; k < oa_length; k++) {
 350                AtkAttribute *oa_attr = g_slist_nth_data(attributes, i);
 351                if (!g_ascii_strcasecmp (oa_attr->name, attr->name) &&
 352                    !g_ascii_strcasecmp (oa_attr->value, attr->value)){
 353                     flag = TRUE;
 354                     break;
 355                }
 356                else
 357                     flag = FALSE;
 358                }
 359           if (!flag) {
 360                atk_attribute_set_free(oa);
 361                return FALSE;
 362           }
 363      }
 364      atk_attribute_set_free(oa);
 365      return TRUE;
 366 }
 367
 368 static gboolean
 369 match_attributes_any_p (AtkObject *child,
 370                         AtkAttributeSet *attributes)
 371 {
 372      int i, k;
 373
 374      AtkAttributeSet *oa;
 375      gint length, oa_length;
 376
 377      length = g_slist_length(attributes);
 378      if (length == 0)
 379           return TRUE;
 380
 381      oa = atk_object_get_attributes(child);
 382      oa_length = g_slist_length(oa);
 383
 384      for (i = 0; i < length; i++){
 385           AtkAttribute *attr = g_slist_nth_data(attributes, i);
 386           for (k = 0; k < oa_length; k++){
 387                AtkAttribute *oa_attr = g_slist_nth_data(attributes, i);
 388                if (!g_ascii_strcasecmp (oa_attr->name, attr->name) &&
 389                    !g_ascii_strcasecmp (oa_attr->value, attr->value)){
 390                     atk_attribute_set_free(oa);
 391                     return TRUE;
 392                     }
 393                }
 394           }
 395      atk_attribute_set_free(oa);
 396      return FALSE;
 397 }
 398
 399 static gboolean
 400 match_attributes_none_p (AtkObject *child,
 401                          AtkAttributeSet *attributes)
 402 {
 403      int i, k;
 404
 405      AtkAttributeSet *oa;
 406      gint length, oa_length;
 407
 408      length = g_slist_length(attributes);
 409      if (length == 0)
 410           return TRUE;
 411
 412      oa = atk_object_get_attributes(child);
 413      oa_length = g_slist_length(oa);
 414
 415      for (i = 0; i < length; i++){
 416           AtkAttribute *attr = g_slist_nth_data(attributes, i);
 417           for (k = 0; k < oa_length; k++){
 418                AtkAttribute *oa_attr = g_slist_nth_data(attributes, i);
 419                if (!g_ascii_strcasecmp (oa_attr->name, attr->name) &&
 420                    !g_ascii_strcasecmp (oa_attr->value, attr->value)){
 421                     atk_attribute_set_free(oa);
 422                     return FALSE;
 423                     }
 424                }
 425           }
 426      atk_attribute_set_free(oa);
 427      return TRUE;
 428 }
 429
 430 static gboolean
 431 match_attributes_lookup (AtkObject *child, MatchRulePrivate *mrp)
 432 {
 433      switch (mrp->attributematchtype){
 434
 435           case Accessibility_Collection_MATCH_ALL :
 436           if (match_attributes_all_p (child, mrp->attributes))
 437                return TRUE;
 438           break;
 439
 440      case  Accessibility_Collection_MATCH_ANY :
 441           if (match_attributes_any_p (child, mrp->attributes))
 442                return TRUE;
 443           break;
 444
 445      case  Accessibility_Collection_MATCH_NONE :
 446           if (match_attributes_none_p (child, mrp->attributes))
 447                return TRUE;
 448           break;
 449
 450       default : break;
 451      }
 452      return FALSE;
 453 }
 454
 455 static gboolean
 456 traverse_p (AtkObject *child,
 457             const gboolean traverse)
 458 {
 459   if (traverse)
 460     return TRUE;
 461   else return !child_collection_p (child);
 462 }
 463
 464 static int
 465 sort_order_canonical (MatchRulePrivate *mrp, GList *ls,
 466                       gint kount, gint max,
 467                       AtkObject *obj, glong index, gboolean flag,
 468                       AtkObject *pobj, gboolean recurse,
 469                       gboolean traverse)
 470 {
 471      gint i = index;
 472      glong acount  = atk_object_get_n_accessible_children (obj);
 473      gboolean prev = pobj? TRUE : FALSE;
 474
 475      for (; i < acount && (max == 0 || kount < max); i++){
 476           AtkObject *child =
 477                         atk_object_ref_accessible_child(obj, i);
 478
 479           g_object_unref(child);
 480           if (prev && child == pobj){
 481             return kount;
 482           }
 483
 484           if (flag  && match_interfaces_lookup (child, mrp)
 485                     && match_states_lookup (child, mrp)
 486                     && match_roles_lookup (child, mrp)
 487                     && match_attributes_lookup (child, mrp)
 488                     ){
 489
 490             ls = g_list_append (ls, child);
 491             kount++;
 492           }
 493
 494           if (!flag)
 495                flag = TRUE;
 496
 497           if (recurse && traverse_p (child, traverse))
 498             kount = sort_order_canonical (mrp, ls,  kount,
 499                                           max, child, 0, TRUE,
 500                                           pobj, recurse, traverse);
 501      }
 502      return kount;
 503 }
 504
 505 static int
 506 sort_order_rev_canonical (MatchRulePrivate *mrp, GList *ls,
 507                       gint kount, gint max,
 508                       AtkObject *obj, gboolean flag,
 509                       AtkObject *pobj)
 510 {
 511     AtkObject *nextobj;
 512     AtkObject *parent;
 513     glong indexinparent;
 514
 515     /* This breaks us out of the recursion. */
 516     if (!obj || obj == pobj)
 517     {
 518         return kount;
 519     }
 520
 521     /* Add to the list if it matches */
 522     if (flag && match_interfaces_lookup (obj, mrp)
 523                && match_states_lookup (obj, mrp)
 524                && match_roles_lookup (obj, mrp)
 525                && match_attributes_lookup (obj, mrp))
 526     {
 527          ls = g_list_append (ls, obj);
 528          kount++;
 529     }
 530
 531     if(!flag) flag = TRUE;
 532
 533     /* Get the current nodes index in it's parent and the parent object. */
 534     indexinparent = atk_object_get_index_in_parent (obj);
 535     parent = atk_object_get_parent(obj);
 536
 537     if(indexinparent > 0)
 538     {
 539          /* there are still some siblings to visit so get the previous sibling
 540             and get it's last descendant.
 541             First, get the previous sibling */
 542          nextobj = atk_object_ref_accessible_child (parent,
 543                                                              indexinparent-1);
 544          g_object_unref(nextobj);
 545
 546          /* Now, drill down the right side to the last descendant */
 547          while(atk_object_get_n_accessible_children (nextobj) > 0)
 548          {
 549               nextobj = atk_object_ref_accessible_child(nextobj,
 550                  atk_object_get_n_accessible_children (nextobj)-1);
 551               g_object_unref (nextobj);
 552          }
 553          /* recurse with the last descendant */
 554          kount = sort_order_rev_canonical (mrp, ls,  kount, max,
 555                                        nextobj, TRUE, pobj);
 556     }
 557     else
 558     {
 559          /* no more siblings so next node must be the parent */
 560          kount = sort_order_rev_canonical (mrp, ls,  kount, max,
 561                                        parent, TRUE, pobj);
 562
 563     }
 564     return kount;
 565 }
 566
 567 static int
 568 query_exec (MatchRulePrivate *mrp,  Accessibility_Collection_SortOrder sortby,
 569             GList *ls, gint kount, gint max,
 570             AtkObject *obj, glong index,
 571             gboolean flag,
 572             AtkObject *pobj,
 573             gboolean recurse, gboolean traverse)
 574 {
 575      switch (sortby) {
 576      case Accessibility_Collection_SORT_ORDER_CANONICAL :
 577        kount = sort_order_canonical(mrp, ls, 0, max, obj, index, flag,
 578                                     pobj, recurse, traverse);
 579        break;
 580      case Accessibility_Collection_SORT_ORDER_REVERSE_CANONICAL :
 581        kount = sort_order_canonical(mrp, ls, 0, max, obj, index, flag,
 582                                     pobj, recurse, traverse);
 583        break;
 584      default:
 585        kount = 0;
 586        g_warning ("Sort method not implemented yet");
 587        break;
 588      }
 589
 590      return kount;
 591 }
 592
 593 static dbus_bool_t
 594 read_mr(DBusMessageIter *iter, MatchRulePrivate *mrp)
 595 {
 596   DBusMessageIter mrc, arrayc;
 597   dbus_uint32_t *array;
 598   dbus_int32_t matchType;
 599   int array_count;
 600   char *str;
 601   AtkAttribute *attr;
 602   int i;
 603   char *interfaces = NULL;
 604
 605   // TODO: error checking
 606   dbus_message_iter_recurse(iter, &mrc);
 607   dbus_message_iter_recurse(&mrc, &arrayc);
 608   dbus_message_iter_get_fixed_array(&arrayc, &array, &array_count);
 609   bitarray_to_seq(array, array_count, &mrp->states);
 610   for (i = 0; mrp->states[i] != BITARRAY_SEQ_TERM; i++)
 611   {
 612     mrp->states[i] = spi_atk_state_from_spi_state (mrp->states[i]);
 613   }
 614   dbus_message_iter_next(&mrc);
 615   dbus_message_iter_read_basic(&mrc, &matchType);
 616   dbus_message_iter_next(&mrc);
 617   mrp->statematchtype = matchType;;
 618   /* attributes */
 619   dbus_message_iter_recurse(&mrc, &arrayc);
 620   mrp->attributes = NULL;
 621   while (dbus_message_iter_get_arg_type(&arrayc) != DBUS_TYPE_INVALID)
 622   {
 623     dbus_message_iter_get_basic(&arrayc, &str);
 624     // TODO: remove this print
 625     g_print("Got attribute: %s\n", str);
 626     attr = g_new (AtkAttribute, 1);
 627     if (attr)
 628     {
 629       int len = strcspn(str, ":");
 630       attr->name = g_strndup(str, len);
 631       if (str[len] == ':')
 632       {
 633         len++;
 634         if (str[len] == ' ') len++;
 635         attr->value = g_strdup(str + len);
 636       }
 637       else attr->value = NULL;
 638       mrp->attributes = g_slist_prepend(mrp->attributes, attr);
 639     }
 640     dbus_message_iter_next(&arrayc);
 641   }
 642   dbus_message_iter_next(&mrc);
 643   dbus_message_iter_read_basic(&mrc, &matchType);
 644   mrp->attributematchtype = matchType;;
 645   dbus_message_iter_next(&mrc);
 646   /* Get roles and role match */
 647   dbus_message_iter_recurse(&mrc, &arrayc);
 648   dbus_message_iter_get_fixed_array(&arrayc, &array, &array_count);
 649   bitarray_to_seq(array, array_count, &mrp->roles);
 650   dbus_message_iter_next(&mrc);
 651   dbus_message_iter_read_basic(&mrc, &matchType);
 652   mrp->rolematchtype = matchType;;
 653   dbus_message_iter_next(&mrc);
 654   /* Get interfaces and interface match */
 655   dbus_message_iter_read_basic(&mrc, &interfaces);
 656   dbus_message_iter_next(&mrc);
 657   mrp->ifaces = g_strsplit(interfaces, ";", 0);
 658   dbus_message_iter_read_basic(&mrc, &matchType);
 659   mrp->interfacematchtype = matchType;;
 660   dbus_message_iter_next(&mrc);
 661   /* get invert */
 662   dbus_message_iter_read_basic(&mrc, &mrp->invert);
 663   dbus_message_iter_next(iter);
 664   return TRUE;
 665 }
 666
 667 static DBusMessage *
 668 return_and_free_list(DBusMessage *message, GList *ls)
 669 {
 670   DBusMessage *reply;
 671   DBusMessageIter iter, iter_array;
 672   GList *item;
 673
 674   reply = dbus_message_new_method_return(message);
 675   if (!reply) return NULL;
 676   dbus_message_iter_init_append(reply, &iter);
 677   if (!dbus_message_iter_open_container(&iter, DBUS_TYPE_ARRAY, "o", &iter_array)) goto oom;
 678   for (item = ls; item; item = g_list_next(item))
 679   {
 680       char *path = (char *) spi_dbus_get_path((AtkObject *)item->data);
 681       dbus_message_iter_append_basic(&iter_array, DBUS_TYPE_OBJECT_PATH, &path);
 682       g_free(path);
 683   }
 684   if (!dbus_message_iter_close_container(&iter, &iter_array)) goto oom;
 685   g_list_free (ls);
 686   return reply;
 687 oom:
 688   // TODO: Handle out of memory
 689   g_list_free (ls);
 690   return reply;
 691 }
 692
 693 static void free_mrp_data(MatchRulePrivate *mrp)
 694 {
 695   g_free(mrp->states);
 696   atk_attribute_set_free(mrp->attributes);
 697   g_free(mrp->roles);
 698   g_strfreev(mrp->ifaces);
 699 }
 700
 701 static DBusMessage *
 702 getMatchesFrom (DBusMessage *message,
 703                      AtkObject *current_object,
 704                      MatchRulePrivate *mrp,
 705                      const Accessibility_Collection_SortOrder sortby,
 706                      const dbus_bool_t isrestrict,
 707                      dbus_int32_t  count,
 708                      const dbus_bool_t traverse)
 709 {
 710      GList *ls = NULL;
 711      AtkObject *parent;
 712      glong index =
 713            atk_object_get_index_in_parent (current_object);
 714      gint kount = 0;
 715
 716      ls = g_list_append (ls, current_object);
 717
 718      if (!isrestrict)
 719      {
 720           parent = atk_object_get_parent (current_object);
 721           kount = query_exec (mrp,  sortby, ls, 0, count, parent, index,
 722                               FALSE, NULL, TRUE, traverse);
 723      }
 724      else
 725           kount = query_exec (mrp,  sortby, ls, 0, count,
 726                               current_object, 0, FALSE, NULL,
 727                               TRUE, traverse);
 728
 729      ls = g_list_remove (ls, ls->data);
 730
 731      if (sortby == Accessibility_Collection_SORT_ORDER_REVERSE_CANONICAL)
 732        ls = g_list_reverse (ls);
 733
 734      free_mrp_data (mrp);
 735      return return_and_free_list (message, ls);
 736 }
 737
 738 /*
 739   inorder traversal from a given object in the hierarchy
 740 */
 741
 742 static int
 743 inorder (AtkObject *collection, MatchRulePrivate *mrp,
 744         GList *ls, gint kount, gint max,
 745         AtkObject *obj,
 746         gboolean flag,
 747         AtkObject *pobj,
 748         dbus_bool_t traverse)
 749 {
 750   int i = 0;
 751
 752   /* First, look through the children recursively. */
 753   kount = sort_order_canonical (mrp, ls, kount, max, obj, 0, TRUE,
 754                                 NULL, TRUE, TRUE);
 755
 756   /* Next, we look through the right subtree */
 757   while ((max == 0 || kount < max)
 758           && obj != collection)
 759   {
 760     AtkObject *parent =
 761                                 atk_object_get_parent (obj);
 762     i = atk_object_get_index_in_parent (obj);
 763     kount  = sort_order_canonical (mrp, ls, kount, max, parent,
 764                                    i+1, TRUE, FALSE, TRUE, TRUE);
 765     obj = parent;
 766   }
 767
 768   if (kount < max)
 769   {
 770      kount = sort_order_canonical (mrp, ls, kount, max,
 771                                    obj, i + 1, TRUE, FALSE,
 772                                    TRUE, TRUE);
 773   }
 774
 775   return kount;
 776 }
 777
 778 /*
 779   GetMatchesInOrder: get matches from a given object in an inorder traversal.
 780 */
 781
 782 static DBusMessage *
 783 getMatchesInOrder (DBusMessage *message,
 784                    AtkObject *current_object,
 785                    MatchRulePrivate *mrp,
 786                    const Accessibility_Collection_SortOrder sortby,
 787                    const dbus_bool_t recurse,
 788                    dbus_int32_t count,
 789                    const dbus_bool_t traverse)
 790 {
 791   GList *ls = NULL;
 792   AtkObject *obj;
 793   gint kount = 0;
 794
 795   ls = g_list_append (ls, current_object);
 796
 797   obj = atk_dbus_get_object (dbus_message_get_path (message));
 798
 799   kount = inorder (obj, mrp, ls, 0, count,
 800                    current_object, TRUE, NULL, traverse);
 801
 802   ls = g_list_remove (ls, ls->data);
 803
 804   if (sortby == Accessibility_Collection_SORT_ORDER_REVERSE_CANONICAL)
 805     ls = g_list_reverse (ls);
 806
 807   free_mrp_data (mrp);
 808   return return_and_free_list (message, ls);
 809 }
 810
 811 /*
 812   GetMatchesInBackOrder: get matches from a given object in a
 813   reverse order traversal.
 814 */
 815
 816 static DBusMessage *
 817 getMatchesInBackOrder (DBusMessage *message,
 818                    AtkObject *current_object,
 819                    MatchRulePrivate *mrp,
 820                    const Accessibility_Collection_SortOrder sortby,
 821                    dbus_int32_t count)
 822 {
 823   GList *ls = NULL;
 824   AtkObject *collection;
 825   gint kount = 0;
 826
 827   ls = g_list_append (ls, current_object);
 828
 829   collection = atk_dbus_get_object (dbus_message_get_path (message));
 830
 831   kount = sort_order_rev_canonical (mrp, ls, 0, count, current_object,
 832                                    FALSE, collection);
 833
 834   ls = g_list_remove (ls, ls->data);
 835
 836   if (sortby == Accessibility_Collection_SORT_ORDER_REVERSE_CANONICAL)
 837     ls = g_list_reverse (ls);
 838
 839   free_mrp_data (mrp);
 840   return return_and_free_list (message, ls);
 841 }
 842
 843 static DBusMessage *
 844 getMatchesTo (DBusMessage *message,
 845               AtkObject *current_object,
 846               MatchRulePrivate *mrp,
 847               const Accessibility_Collection_SortOrder sortby,
 848               const dbus_bool_t recurse,
 849               const dbus_bool_t isrestrict,
 850               dbus_int32_t  count,
 851               const dbus_bool_t traverse)
 852 {
 853   GList *ls = NULL;
 854   AtkObject *obj;
 855   gint kount = 0;
 856
 857   ls = g_list_append (ls, current_object);
 858
 859   if (recurse){
 860     obj = atk_object_get_parent (current_object);
 861     kount =  query_exec (mrp,  sortby, ls, 0, count,
 862                          obj, 0, TRUE, current_object, TRUE, traverse);
 863   }
 864   else{
 865     obj = atk_dbus_get_object (dbus_message_get_path (message));
 866     kount = query_exec (mrp,  sortby, ls, 0, count,
 867                         obj, 0, TRUE, current_object, TRUE, traverse);
 868
 869   }
 870
 871   ls = g_list_remove (ls, ls->data);
 872
 873   if (sortby != Accessibility_Collection_SORT_ORDER_REVERSE_CANONICAL)
 874     ls = g_list_reverse (ls);
 875
 876   free_mrp_data (mrp);
 877   return return_and_free_list (message, ls);
 878 }
 879
 880 static DBusMessage *
 881 impl_getMatchesFrom (DBusConnection *bus, DBusMessage *message, void *user_data)
 882 {
 883   char *current_object_path = NULL;
 884   AtkObject *current_object;
 885   DBusMessageIter iter;
 886   MatchRulePrivate rule;
 887   dbus_uint16_t sortby;
 888   dbus_uint16_t tree;
 889   dbus_int32_t count;
 890   dbus_bool_t traverse;
 891   GList *ls = NULL;
 892
 893   dbus_message_iter_init(message, &iter);
 894   dbus_message_iter_get_basic (&iter, current_object_path);
 895   current_object = atk_dbus_get_object (current_object_path);
 896   if (!current_object)
 897   {
 898     // TODO: object-not-found error
 899     return spi_dbus_general_error (message);
 900   }
 901   dbus_message_iter_next (&iter);
 902   if (!read_mr(&iter, &rule))
 903   {
 904     return spi_dbus_general_error (message);
 905   }
 906   dbus_message_iter_get_basic(&iter, &sortby);
 907   dbus_message_iter_next(&iter);
 908   dbus_message_iter_get_basic(&iter, &tree);
 909   dbus_message_iter_next(&iter);
 910   dbus_message_iter_get_basic(&iter, &count);
 911   dbus_message_iter_next(&iter);
 912   dbus_message_iter_get_basic(&iter, &traverse);
 913   dbus_message_iter_next(&iter);
 914
 915   switch (tree){
 916   case Accessibility_Collection_TREE_RESTRICT_CHILDREN :
 917     return getMatchesFrom (message, current_object,
 918                            &rule, sortby, TRUE, count, traverse);
 919     break;
 920   case Accessibility_Collection_TREE_RESTRICT_SIBLING :
 921     return getMatchesFrom (message, current_object,
 922                            &rule, sortby, FALSE, count, traverse);
 923     break;
 924   case Accessibility_Collection_TREE_INORDER :
 925     return getMatchesInOrder (message, current_object,
 926                               &rule, sortby, TRUE, count, traverse);
 927     break;
 928   default : return NULL;
 929   }
 930 }
 931
 932 static DBusMessage *
 933 impl_getMatchesTo (DBusConnection *bus, DBusMessage *message, void *user_data)
 934 {
 935   char *current_object_path = NULL;
 936   AtkObject *current_object;
 937   DBusMessageIter iter;
 938   MatchRulePrivate rule;
 939   dbus_uint16_t sortby;
 940   dbus_uint16_t tree;
 941   dbus_bool_t recurse;
 942   dbus_int32_t count;
 943   dbus_bool_t traverse;
 944   GList *ls = NULL;
 945
 946   dbus_message_iter_init(message, &iter);
 947   dbus_message_iter_get_basic (&iter, current_object_path);
 948   current_object = atk_dbus_get_object (current_object_path);
 949   if (!current_object)
 950   {
 951     // TODO: object-not-found error
 952     return spi_dbus_general_error (message);
 953   }
 954   dbus_message_iter_next (&iter);
 955   if (!read_mr(&iter, &rule))
 956   {
 957     return spi_dbus_general_error (message);
 958   }
 959   dbus_message_iter_get_basic(&iter, &sortby);
 960   dbus_message_iter_next(&iter);
 961   dbus_message_iter_get_basic(&iter, &tree);
 962   dbus_message_iter_next(&iter);
 963   dbus_message_iter_get_basic(&iter, &recurse);
 964   dbus_message_iter_next(&iter);
 965   dbus_message_iter_get_basic(&iter, &count);
 966   dbus_message_iter_next(&iter);
 967   dbus_message_iter_get_basic(&iter, &traverse);
 968   dbus_message_iter_next(&iter);
 969
 970   switch (tree){
 971   case Accessibility_Collection_TREE_RESTRICT_CHILDREN :
 972     return getMatchesTo (message, current_object,
 973                          &rule, sortby, recurse, TRUE, count, traverse);
 974     break;
 975   case Accessibility_Collection_TREE_RESTRICT_SIBLING :
 976     return getMatchesTo (message, current_object,
 977                          &rule, sortby, recurse, FALSE, count, traverse);
 978     break;
 979   case Accessibility_Collection_TREE_INORDER :
 980     return getMatchesInBackOrder (message, current_object,
 981                                   &rule, sortby, count);
 982     break;
 983   default : return NULL;
 984   }
 985 }
 986
 987 static DBusMessage *
 988 impl_getMatches(DBusConnection *bus, DBusMessage *message, void *user_data)
 989 {
 990   AtkObject *obj = get_object(message);
 991   DBusMessageIter iter;
 992   MatchRulePrivate rule;
 993   dbus_uint16_t sortby;
 994   dbus_int32_t count;
 995   dbus_bool_t traverse;
 996   GList *ls = NULL;
 997
 998   dbus_message_iter_init(message, &iter);
 999   if (!read_mr(&iter, &rule))
1000   {
1001     return spi_dbus_general_error (message);
1002   }
1003   dbus_message_iter_get_basic(&iter, &sortby);
1004   dbus_message_iter_next(&iter);
1005   dbus_message_iter_get_basic(&iter, &count);
1006   dbus_message_iter_next(&iter);
1007   dbus_message_iter_get_basic(&iter, &traverse);
1008   dbus_message_iter_next(&iter);
1009      ls = g_list_prepend (ls, obj);
1010   count = query_exec (&rule, sortby, ls, 0, count,
1011                          obj, 0, TRUE, NULL, TRUE, traverse);
1012      ls = g_list_remove (ls, ls->data);
1013
1014      if (sortby == Accessibility_Collection_SORT_ORDER_REVERSE_CANONICAL)
1015        ls = g_list_reverse (ls);
1016      free_mrp_data (&rule);
1017      return return_and_free_list (message, ls);
1018 }
1019
1020 static DRouteMethod methods[] = {
1021   { impl_getMatchesFrom, "getMatchesFrom" },
1022   { impl_getMatchesTo, "getMatchesTo" },
1023   { impl_getMatches, "getMatches" },
1024   {NULL, NULL}
1025 };
1026
1027 void
1028 spi_initialize_collection (DRoutePath *path)
1029 {
1030   droute_path_add_interface (path,
1031                              SPI_DBUS_INTERFACE_COLLECTION,
1032                              methods,
1033                              NULL);
1034 };