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