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