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