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 Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 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  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with this library; if not, write to the
  19  * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  20  * Boston, MA 02110-1301, 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 #include "bridge.h"
  30
  31 #include "bitarray.h"
  32 #include "spi-dbus.h"
  33 #include "accessible-stateset.h"
  34
  35 #include "accessible-register.h"
  36 #include "object.h"
  37 #include "introspection.h"
  38
  39 typedef struct _MatchRulePrivate MatchRulePrivate;
  40 struct _MatchRulePrivate
  41 {
  42   gint *states;
  43   AtspiCollectionMatchType statematchtype;
  44   AtkAttributeSet *attributes;
  45   AtspiCollectionMatchType attributematchtype;
  46   gint *roles;
  47   AtspiCollectionMatchType rolematchtype;
  48   gchar **ifaces;
  49   AtspiCollectionMatchType interfacematchtype;
  50   gboolean invert;
  51 };
  52
  53 static gboolean
  54 child_interface_p (AtkObject * child, gchar * repo_id)
  55 {
  56   if (!strcasecmp (repo_id, "action"))
  57     return ATK_IS_ACTION (child);
  58   if (!strcasecmp (repo_id, "component"))
  59     return ATK_IS_COMPONENT (child);
  60   if (!strcasecmp (repo_id, "editabletext"))
  61     return ATK_IS_EDITABLE_TEXT (child);
  62   if (!strcasecmp (repo_id, "text"))
  63     return ATK_IS_TEXT (child);
  64   if (!strcasecmp (repo_id, "hypertext"))
  65     return ATK_IS_HYPERTEXT (child);
  66   if (!strcasecmp (repo_id, "image"))
  67     return ATK_IS_IMAGE (child);
  68   if (!strcasecmp (repo_id, "selection"))
  69     return ATK_IS_SELECTION (child);
  70   if (!strcasecmp (repo_id, "table"))
  71     return ATK_IS_TABLE (child);
  72   if (!strcasecmp (repo_id, "value"))
  73     return ATK_IS_VALUE (child);
  74   if (!strcasecmp (repo_id, "streamablecontent"))
  75     return ATK_IS_STREAMABLE_CONTENT (child);
  76   if (!strcasecmp (repo_id, "document"))
  77     return ATK_IS_DOCUMENT (child);
  78   return FALSE;
  79 }
  80
  81 #define child_collection_p(ch) (TRUE)
  82
  83 static gboolean
  84 match_states_all_p (AtkObject * child, gint * set)
  85 {
  86   AtkStateSet *chs;
  87   gint i;
  88   gboolean ret = TRUE;
  89
  90   if (set == NULL || set[0] == BITARRAY_SEQ_TERM)
  91     return TRUE;
  92
  93   chs = atk_object_ref_state_set (child);
  94
  95   // TODO: use atk-state_set_contains_states; would be more efficient
  96   for (i = 0; set[i] != BITARRAY_SEQ_TERM; i++)
  97     {
  98       if (!atk_state_set_contains_state (chs, set[i]))
  99         {
 100           ret = FALSE;
 101           break;
 102         }
 103     }
 104
 105   g_object_unref (chs);
 106   return ret;
 107 }
 108
 109 static gboolean
 110 match_states_any_p (AtkObject * child, gint * set)
 111 {
 112   AtkStateSet *chs;
 113   gint i;
 114   gboolean ret = FALSE;
 115
 116   if (set == NULL || set[0] == BITARRAY_SEQ_TERM)
 117     return TRUE;
 118
 119   chs = atk_object_ref_state_set (child);
 120
 121   for (i = 0; set[i] != BITARRAY_SEQ_TERM; i++)
 122     {
 123       if (atk_state_set_contains_state (chs, set[i]))
 124         {
 125           ret = TRUE;
 126           break;
 127         }
 128     }
 129
 130   g_object_unref (chs);
 131   return ret;
 132 }
 133
 134 static gboolean
 135 match_states_none_p (AtkObject * child, gint * set)
 136 {
 137   AtkStateSet *chs;
 138   gint i;
 139   gboolean ret = TRUE;
 140
 141   if (set == NULL || set[0] == BITARRAY_SEQ_TERM)
 142     return TRUE;
 143
 144   chs = atk_object_ref_state_set (child);
 145
 146   for (i = 0; set[i] != BITARRAY_SEQ_TERM; i++)
 147     {
 148       if (atk_state_set_contains_state (chs, set[i]))
 149         {
 150           ret = FALSE;
 151           break;
 152         }
 153     }
 154
 155   g_object_unref (chs);
 156   return ret;
 157 }
 158
 159 // TODO: need to convert at-spi roles/states to atk roles/states */
 160 static gboolean
 161 match_states_lookup (AtkObject * child, MatchRulePrivate * mrp)
 162 {
 163   switch (mrp->statematchtype)
 164     {
 165     case ATSPI_Collection_MATCH_ALL:
 166       if (match_states_all_p (child, mrp->states))
 167         return TRUE;
 168       break;
 169
 170     case ATSPI_Collection_MATCH_ANY:
 171       if (match_states_any_p (child, mrp->states))
 172         return TRUE;
 173       break;
 174
 175     case ATSPI_Collection_MATCH_NONE:
 176       if (match_states_none_p (child, mrp->states))
 177         return TRUE;
 178       break;
 179
 180     default:
 181       break;
 182     }
 183
 184   return FALSE;
 185 }
 186
 187 // TODO: Map at-spi -> atk roles at mrp creation instead of doing this;
 188 // would be more efficient
 189 #define spi_get_role(obj) spi_accessible_role_from_atk_role(atk_object_get_role(obj))
 190
 191 static gboolean
 192 match_roles_all_p (AtkObject * child, gint * roles)
 193 {
 194   if (roles == NULL || roles[0] == BITARRAY_SEQ_TERM)
 195     return TRUE;
 196   else if (roles[1] != BITARRAY_SEQ_TERM)
 197     return FALSE;
 198
 199   return (atk_object_get_role (child) == roles[0]);
 200
 201 }
 202
 203 static gboolean
 204 match_roles_any_p (AtkObject * child, gint * roles)
 205 {
 206   AtspiRole role;
 207   int i;
 208
 209   if (roles == NULL || roles[0] == BITARRAY_SEQ_TERM)
 210     return TRUE;
 211
 212   role = spi_accessible_role_from_atk_role (atk_object_get_role (child));
 213
 214   for (i = 0; roles[i] != BITARRAY_SEQ_TERM; i++)
 215     if (role == roles[i])
 216       return TRUE;
 217
 218   return FALSE;
 219 }
 220
 221 static gboolean
 222 match_roles_none_p (AtkObject * child, gint * roles)
 223 {
 224   AtkRole role;
 225   int i;
 226
 227   if (roles == NULL || roles[0] == BITARRAY_SEQ_TERM)
 228     return TRUE;
 229
 230   role = atk_object_get_role (child);
 231
 232   for (i = 0; roles[i] != BITARRAY_SEQ_TERM; i++)
 233     if (role == roles[i])
 234       return FALSE;
 235
 236   return TRUE;
 237 }
 238
 239 static gboolean
 240 match_roles_lookup (AtkObject * child, MatchRulePrivate * mrp)
 241 {
 242   switch (mrp->rolematchtype)
 243     {
 244     case ATSPI_Collection_MATCH_ALL:
 245       if (match_roles_all_p (child, mrp->roles))
 246         return TRUE;
 247       break;
 248
 249     case ATSPI_Collection_MATCH_ANY:
 250       if (match_roles_any_p (child, mrp->roles))
 251         return TRUE;
 252       break;
 253
 254     case ATSPI_Collection_MATCH_NONE:
 255       if (match_roles_none_p (child, mrp->roles))
 256         return TRUE;
 257       break;
 258
 259     default:
 260       break;
 261
 262     }
 263   return FALSE;
 264 }
 265
 266 static gboolean
 267 match_interfaces_all_p (AtkObject * obj, gchar ** ifaces)
 268 {
 269   gint i;
 270
 271   if (ifaces == NULL)
 272     return TRUE;
 273
 274   for (i = 0; ifaces[i]; i++)
 275     if (!child_interface_p (obj, ifaces[i]))
 276       {
 277         return FALSE;
 278       }
 279   return TRUE;
 280 }
 281
 282 static gboolean
 283 match_interfaces_any_p (AtkObject * obj, gchar ** ifaces)
 284 {
 285   gint i;
 286
 287   if (ifaces == NULL)
 288     return TRUE;
 289
 290
 291   for (i = 0; ifaces[i]; i++)
 292     if (child_interface_p (obj, ifaces[i]))
 293       {
 294         return TRUE;
 295       }
 296   return FALSE;
 297 }
 298
 299 static gboolean
 300 match_interfaces_none_p (AtkObject * obj, gchar ** ifaces)
 301 {
 302   gint i;
 303
 304   for (i = 0; ifaces[i]; i++)
 305     if (child_interface_p (obj, ifaces[i]))
 306       return FALSE;
 307
 308   return TRUE;
 309 }
 310
 311 static gboolean
 312 match_interfaces_lookup (AtkObject * child, MatchRulePrivate * mrp)
 313 {
 314   switch (mrp->interfacematchtype)
 315     {
 316
 317     case ATSPI_Collection_MATCH_ALL:
 318       if (match_interfaces_all_p (child, mrp->ifaces))
 319         return TRUE;
 320       break;
 321
 322     case ATSPI_Collection_MATCH_ANY:
 323       if (match_interfaces_any_p (child, mrp->ifaces))
 324         return TRUE;
 325       break;
 326
 327     case ATSPI_Collection_MATCH_NONE:
 328       if (match_interfaces_none_p (child, mrp->ifaces))
 329         return TRUE;
 330       break;
 331
 332     default:
 333       break;
 334     }
 335
 336   return FALSE;
 337 }
 338
 339 #define split_attributes(attributes) (g_strsplit (attributes, ";", 0))
 340
 341 static gboolean
 342 match_attributes_all_p (AtkObject * child, AtkAttributeSet * attributes)
 343 {
 344   int i, k;
 345   AtkAttributeSet *oa;
 346   gint length, oa_length;
 347   gboolean flag = FALSE;
 348
 349   if (attributes == NULL || g_slist_length (attributes) == 0)
 350     return TRUE;
 351
 352   oa = atk_object_get_attributes (child);
 353   length = g_slist_length (attributes);
 354   oa_length = g_slist_length (oa);
 355
 356   for (i = 0; i < length; i++)
 357     {
 358       AtkAttribute *attr = g_slist_nth_data (attributes, i);
 359       for (k = 0; k < oa_length; k++)
 360         {
 361           AtkAttribute *oa_attr = g_slist_nth_data (attributes, i);
 362           if (!g_ascii_strcasecmp (oa_attr->name, attr->name) &&
 363               !g_ascii_strcasecmp (oa_attr->value, attr->value))
 364             {
 365               flag = TRUE;
 366               break;
 367             }
 368           else
 369             flag = FALSE;
 370         }
 371       if (!flag)
 372         {
 373           atk_attribute_set_free (oa);
 374           return FALSE;
 375         }
 376     }
 377   atk_attribute_set_free (oa);
 378   return TRUE;
 379 }
 380
 381 static gboolean
 382 match_attributes_any_p (AtkObject * child, AtkAttributeSet * attributes)
 383 {
 384   int i, k;
 385
 386   AtkAttributeSet *oa;
 387   gint length, oa_length;
 388
 389   length = g_slist_length (attributes);
 390   if (length == 0)
 391     return TRUE;
 392
 393   oa = atk_object_get_attributes (child);
 394   oa_length = g_slist_length (oa);
 395
 396   for (i = 0; i < length; i++)
 397     {
 398       AtkAttribute *attr = g_slist_nth_data (attributes, i);
 399       for (k = 0; k < oa_length; k++)
 400         {
 401           AtkAttribute *oa_attr = g_slist_nth_data (oa, k);
 402           if (!g_ascii_strcasecmp (oa_attr->name, attr->name) &&
 403               !g_ascii_strcasecmp (oa_attr->value, attr->value))
 404             {
 405               atk_attribute_set_free (oa);
 406               return TRUE;
 407             }
 408         }
 409     }
 410   atk_attribute_set_free (oa);
 411   return FALSE;
 412 }
 413
 414 static gboolean
 415 match_attributes_none_p (AtkObject * child, AtkAttributeSet * attributes)
 416 {
 417   int i, k;
 418
 419   AtkAttributeSet *oa;
 420   gint length, oa_length;
 421
 422   length = g_slist_length (attributes);
 423   if (length == 0)
 424     return TRUE;
 425
 426   oa = atk_object_get_attributes (child);
 427   oa_length = g_slist_length (oa);
 428
 429   for (i = 0; i < length; i++)
 430     {
 431       AtkAttribute *attr = g_slist_nth_data (attributes, i);
 432       for (k = 0; k < oa_length; k++)
 433         {
 434           AtkAttribute *oa_attr = g_slist_nth_data (attributes, i);
 435           if (!g_ascii_strcasecmp (oa_attr->name, attr->name) &&
 436               !g_ascii_strcasecmp (oa_attr->value, attr->value))
 437             {
 438               atk_attribute_set_free (oa);
 439               return FALSE;
 440             }
 441         }
 442     }
 443   atk_attribute_set_free (oa);
 444   return TRUE;
 445 }
 446
 447 static gboolean
 448 match_attributes_lookup (AtkObject * child, MatchRulePrivate * mrp)
 449 {
 450   switch (mrp->attributematchtype)
 451     {
 452
 453     case ATSPI_Collection_MATCH_ALL:
 454       if (match_attributes_all_p (child, mrp->attributes))
 455         return TRUE;
 456       break;
 457
 458     case ATSPI_Collection_MATCH_ANY:
 459       if (match_attributes_any_p (child, mrp->attributes))
 460         return TRUE;
 461       break;
 462
 463     case ATSPI_Collection_MATCH_NONE:
 464       if (match_attributes_none_p (child, mrp->attributes))
 465         return TRUE;
 466       break;
 467
 468     default:
 469       break;
 470     }
 471   return FALSE;
 472 }
 473
 474 static gboolean
 475 traverse_p (AtkObject * child, const gboolean traverse)
 476 {
 477   if (traverse)
 478     return TRUE;
 479   else
 480     return !child_collection_p (child);
 481 }
 482
 483 static int
 484 sort_order_canonical (MatchRulePrivate * mrp, GList * ls,
 485                       gint kount, gint max,
 486                       AtkObject * obj, glong index, gboolean flag,
 487                       AtkObject * pobj, gboolean recurse, gboolean traverse)
 488 {
 489   gint i = index;
 490   glong acount = atk_object_get_n_accessible_children (obj);
 491   gboolean prev = pobj ? TRUE : FALSE;
 492
 493   for (; i < acount && (max == 0 || kount < max); i++)
 494     {
 495       AtkObject *child = atk_object_ref_accessible_child (obj, i);
 496
 497       if (!child)
 498         continue;
 499
 500       if (prev && child == pobj)
 501         {
 502           g_object_unref (child);
 503           return kount;
 504         }
 505
 506       if (flag && match_interfaces_lookup (child, mrp)
 507           && match_states_lookup (child, mrp)
 508           && match_roles_lookup (child, mrp)
 509           && match_attributes_lookup (child, mrp))
 510         {
 511
 512           ls = g_list_append (ls, child);
 513           kount++;
 514         }
 515
 516       if (!flag)
 517         flag = TRUE;
 518
 519       if (recurse && traverse_p (child, traverse))
 520         kount = sort_order_canonical (mrp, ls, kount,
 521                                       max, child, 0, TRUE,
 522                                       pobj, recurse, traverse);
 523       g_object_unref (child);
 524     }
 525   return kount;
 526 }
 527
 528 static int
 529 sort_order_rev_canonical (MatchRulePrivate * mrp, GList * ls,
 530                           gint kount, gint max,
 531                           AtkObject * obj, gboolean flag, AtkObject * pobj)
 532 {
 533   AtkObject *nextobj;
 534   AtkObject *parent;
 535   glong indexinparent;
 536
 537   /* This breaks us out of the recursion. */
 538   if (!obj || obj == pobj)
 539     {
 540       return kount;
 541     }
 542
 543   /* Add to the list if it matches */
 544   if (flag && match_interfaces_lookup (obj, mrp)
 545       && match_states_lookup (obj, mrp)
 546       && match_roles_lookup (obj, mrp) && match_attributes_lookup (obj, mrp)
 547       && (max == 0 || kount < max))
 548     {
 549       ls = g_list_append (ls, obj);
 550       kount++;
 551     }
 552
 553   if (!flag)
 554     flag = TRUE;
 555
 556   /* Get the current nodes index in it's parent and the parent object. */
 557   indexinparent = atk_object_get_index_in_parent (obj);
 558   parent = atk_object_get_parent (obj);
 559
 560   if (indexinparent > 0 && (max == 0 || kount < max))
 561     {
 562       /* there are still some siblings to visit so get the previous sibling
 563          and get it's last descendant.
 564          First, get the previous sibling */
 565       nextobj = atk_object_ref_accessible_child (parent, indexinparent - 1);
 566
 567       /* Now, drill down the right side to the last descendant */
 568       while (nextobj && atk_object_get_n_accessible_children (nextobj) > 0)
 569         {
 570           AtkObject *follow;
 571
 572           follow = atk_object_ref_accessible_child (nextobj,
 573                                                      atk_object_get_n_accessible_children
 574                                                      (nextobj) - 1);
 575           g_object_unref (nextobj);
 576           nextobj = follow;
 577         }
 578       /* recurse with the last descendant */
 579       kount = sort_order_rev_canonical (mrp, ls, kount, max,
 580                                         nextobj, TRUE, pobj);
 581       if (nextobj)
 582          g_object_unref (nextobj);
 583     }
 584   else if (max == 0 || kount < max)
 585     {
 586       /* no more siblings so next node must be the parent */
 587       kount = sort_order_rev_canonical (mrp, ls, kount, max,
 588                                         parent, TRUE, pobj);
 589
 590     }
 591   return kount;
 592 }
 593
 594 static int
 595 query_exec (MatchRulePrivate * mrp, AtspiCollectionSortOrder sortby,
 596             GList * ls, gint kount, gint max,
 597             AtkObject * obj, glong index,
 598             gboolean flag,
 599             AtkObject * pobj, gboolean recurse, gboolean traverse)
 600 {
 601   switch (sortby)
 602     {
 603     case ATSPI_Collection_SORT_ORDER_CANONICAL:
 604       kount = sort_order_canonical (mrp, ls, 0, max, obj, index, flag,
 605                                     pobj, recurse, traverse);
 606       break;
 607     case ATSPI_Collection_SORT_ORDER_REVERSE_CANONICAL:
 608       kount = sort_order_canonical (mrp, ls, 0, max, obj, index, flag,
 609                                     pobj, recurse, traverse);
 610       break;
 611     default:
 612       kount = 0;
 613       g_warning ("Sort method not implemented yet");
 614       break;
 615     }
 616
 617   return kount;
 618 }
 619
 620 static gboolean
 621 bitarray_to_seq (dbus_uint32_t *array, int array_count, int **ret)
 622 {
 623   int out_size = 4;
 624   int out_count = 0;
 625   int i, j;
 626   int *out = (int *) g_malloc (out_size * sizeof (int));
 627
 628   if (!out)
 629     return FALSE;
 630   for (i = 0; i < array_count; i++)
 631     {
 632       for (j = 0; j < 32; j++)
 633         {
 634           if (array[i] & (1 << j))
 635             {
 636               if (out_count == out_size - 2)
 637                 {
 638                   out_size <<= 1;
 639                   out = (int *) g_realloc (out, out_size * sizeof (int));
 640                   if (!out)
 641                     return FALSE;
 642                 }
 643               out[out_count++] = i * 32 + j;
 644             }
 645         }
 646     }
 647   out[out_count] = BITARRAY_SEQ_TERM;
 648   *ret = out;
 649   return TRUE;
 650 }
 651
 652
 653 static dbus_bool_t
 654 read_mr (DBusMessageIter * iter, MatchRulePrivate * mrp)
 655 {
 656   DBusMessageIter iter_struct, iter_array, iter_dict, iter_dict_entry;
 657   dbus_uint32_t *array;
 658   dbus_int32_t matchType;
 659   int array_count;
 660   AtkAttribute *attr;
 661   int i;
 662
 663   dbus_message_iter_recurse (iter, &iter_struct);
 664
 665   /* states */
 666   dbus_message_iter_recurse (&iter_struct, &iter_array);
 667   dbus_message_iter_get_fixed_array (&iter_array, &array, &array_count);
 668   bitarray_to_seq (array, array_count, &mrp->states);
 669   for (i = 0; mrp->states[i] != BITARRAY_SEQ_TERM; i++)
 670     {
 671       mrp->states[i] = spi_atk_state_from_spi_state (mrp->states[i]);
 672     }
 673   dbus_message_iter_next (&iter_struct);
 674   dbus_message_iter_get_basic (&iter_struct, &matchType);
 675   dbus_message_iter_next (&iter_struct);
 676   mrp->statematchtype = matchType;;
 677
 678   /* attributes */
 679   mrp->attributes = NULL;
 680   dbus_message_iter_recurse (&iter_struct, &iter_dict);
 681   while (dbus_message_iter_get_arg_type (&iter_dict) != DBUS_TYPE_INVALID)
 682     {
 683       const char *key, *val;
 684       const char *p, *q;
 685       dbus_message_iter_recurse (&iter_dict, &iter_dict_entry);
 686       dbus_message_iter_get_basic (&iter_dict_entry, &key);
 687       dbus_message_iter_next (&iter_dict_entry);
 688       dbus_message_iter_get_basic (&iter_dict_entry, &val);
 689       p = q = val;
 690       for (;;)
 691       {
 692         if (*q == '\0' || (*q == ':' && (q == val || q[-1] != '\\')))
 693         {
 694           char *tmp;
 695           attr = g_new (AtkAttribute, 1);
 696           attr->name = g_strdup (key);
 697           attr->value = g_strdup (p);
 698           attr->value[q - p] = '\0';
 699           tmp = attr->value;
 700           while (*tmp != '\0')
 701           {
 702             if (*tmp == '\\')
 703               memmove (tmp, tmp + 1, strlen (tmp));
 704             else
 705               tmp++;
 706           }
 707           mrp->attributes = g_slist_prepend (mrp->attributes, attr);
 708           if (*q == '\0')
 709             break;
 710           else
 711             p = ++q;
 712         }
 713         else
 714           q++;
 715       }
 716       dbus_message_iter_next (&iter_dict);
 717     }
 718   dbus_message_iter_next (&iter_struct);
 719   dbus_message_iter_get_basic (&iter_struct, &matchType);
 720   mrp->attributematchtype = matchType;;
 721   dbus_message_iter_next (&iter_struct);
 722
 723   /* Get roles and role match */
 724   dbus_message_iter_recurse (&iter_struct, &iter_array);
 725   dbus_message_iter_get_fixed_array (&iter_array, &array, &array_count);
 726   bitarray_to_seq (array, array_count, &mrp->roles);
 727   dbus_message_iter_next (&iter_struct);
 728   dbus_message_iter_get_basic (&iter_struct, &matchType);
 729   mrp->rolematchtype = matchType;;
 730   dbus_message_iter_next (&iter_struct);
 731
 732   /* Get interfaces and interface match */
 733   dbus_message_iter_recurse (&iter_struct, &iter_array);
 734   mrp->ifaces = g_new0 (gchar *, 16);
 735   i = 0;
 736   while (i < 15 && dbus_message_iter_get_arg_type (&iter_array) != DBUS_TYPE_INVALID)
 737   {
 738     char *iface;
 739     dbus_message_iter_get_basic (&iter_array, &iface);
 740     mrp->ifaces [i] = g_strdup (iface);
 741     i++;
 742     dbus_message_iter_next (&iter_array);
 743   }
 744   dbus_message_iter_next (&iter_struct);
 745   dbus_message_iter_get_basic (&iter_struct, &matchType);
 746   mrp->interfacematchtype = matchType;;
 747   dbus_message_iter_next (&iter_struct);
 748   /* get invert */
 749   dbus_message_iter_get_basic (&iter_struct, &mrp->invert);
 750   dbus_message_iter_next (iter);
 751   return TRUE;
 752 }
 753
 754 static DBusMessage *
 755 return_and_free_list (DBusMessage * message, GList * ls)
 756 {
 757   DBusMessage *reply;
 758   DBusMessageIter iter, iter_array;
 759   GList *item;
 760
 761   reply = dbus_message_new_method_return (message);
 762   if (!reply)
 763     return NULL;
 764   dbus_message_iter_init_append (reply, &iter);
 765   if (!dbus_message_iter_open_container
 766       (&iter, DBUS_TYPE_ARRAY, "(so)", &iter_array))
 767     goto oom;
 768   for (item = ls; item; item = g_list_next (item))
 769     {
 770       spi_object_append_reference (&iter_array, ATK_OBJECT (item->data));
 771     }
 772   if (!dbus_message_iter_close_container (&iter, &iter_array))
 773     goto oom;
 774   g_list_free (ls);
 775   return reply;
 776 oom:
 777   // TODO: Handle out of memory
 778   g_list_free (ls);
 779   return reply;
 780 }
 781
 782 static void
 783 free_mrp_data (MatchRulePrivate * mrp)
 784 {
 785   g_free (mrp->states);
 786   atk_attribute_set_free (mrp->attributes);
 787   g_free (mrp->roles);
 788   g_strfreev (mrp->ifaces);
 789 }
 790
 791 static DBusMessage *
 792 GetMatchesFrom (DBusMessage * message,
 793                 AtkObject * current_object,
 794                 MatchRulePrivate * mrp,
 795                 const AtspiCollectionSortOrder sortby,
 796                 const dbus_bool_t isrestrict,
 797                 dbus_int32_t count, const dbus_bool_t traverse)
 798 {
 799   GList *ls = NULL;
 800   AtkObject *parent;
 801   glong index = atk_object_get_index_in_parent (current_object);
 802
 803   ls = g_list_append (ls, current_object);
 804
 805   if (!isrestrict)
 806     {
 807       parent = atk_object_get_parent (current_object);
 808       query_exec (mrp, sortby, ls, 0, count, parent, index,
 809                   FALSE, NULL, TRUE, traverse);
 810     }
 811   else
 812     query_exec (mrp, sortby, ls, 0, count,
 813                 current_object, 0, FALSE, NULL, TRUE, traverse);
 814
 815   ls = g_list_remove (ls, ls->data);
 816
 817   if (sortby == ATSPI_Collection_SORT_ORDER_REVERSE_CANONICAL)
 818     ls = g_list_reverse (ls);
 819
 820   free_mrp_data (mrp);
 821   return return_and_free_list (message, ls);
 822 }
 823
 824 /*
 825   inorder traversal from a given object in the hierarchy
 826 */
 827
 828 static int
 829 inorder (AtkObject * collection, MatchRulePrivate * mrp,
 830          GList * ls, gint kount, gint max,
 831          AtkObject * obj,
 832          gboolean flag, AtkObject * pobj, dbus_bool_t traverse)
 833 {
 834   int i = 0;
 835
 836   /* First, look through the children recursively. */
 837   kount = sort_order_canonical (mrp, ls, kount, max, obj, 0, TRUE,
 838                                 NULL, TRUE, TRUE);
 839
 840   /* Next, we look through the right subtree */
 841   while ((max == 0 || kount < max) && obj && obj != collection)
 842     {
 843       AtkObject *parent = atk_object_get_parent (obj);
 844       i = atk_object_get_index_in_parent (obj);
 845       kount = sort_order_canonical (mrp, ls, kount, max, parent,
 846                                     i + 1, TRUE, FALSE, TRUE, TRUE);
 847       obj = parent;
 848     }
 849
 850   if (max == 0 || kount < max)
 851     {
 852       kount = sort_order_canonical (mrp, ls, kount, max,
 853                                     obj, i + 1, TRUE, FALSE, TRUE, TRUE);
 854     }
 855
 856   return kount;
 857 }
 858
 859 /*
 860   GetMatchesInOrder: get matches from a given object in an inorder traversal.
 861 */
 862
 863 static DBusMessage *
 864 GetMatchesInOrder (DBusMessage * message,
 865                    AtkObject * current_object,
 866                    MatchRulePrivate * mrp,
 867                    const AtspiCollectionSortOrder sortby,
 868                    const dbus_bool_t recurse,
 869                    dbus_int32_t count, const dbus_bool_t traverse)
 870 {
 871   GList *ls = NULL;
 872   AtkObject *obj;
 873
 874   ls = g_list_append (ls, current_object);
 875
 876   obj = ATK_OBJECT(spi_register_path_to_object (spi_global_register, dbus_message_get_path (message)));
 877
 878   inorder (obj, mrp, ls, 0, count,
 879            current_object, TRUE, NULL, traverse);
 880
 881   ls = g_list_remove (ls, ls->data);
 882
 883   if (sortby == ATSPI_Collection_SORT_ORDER_REVERSE_CANONICAL)
 884     ls = g_list_reverse (ls);
 885
 886   free_mrp_data (mrp);
 887   return return_and_free_list (message, ls);
 888 }
 889
 890 /*
 891   GetMatchesInBackOrder: get matches from a given object in a
 892   reverse order traversal.
 893 */
 894
 895 static DBusMessage *
 896 GetMatchesInBackOrder (DBusMessage * message,
 897                        AtkObject * current_object,
 898                        MatchRulePrivate * mrp,
 899                        const AtspiCollectionSortOrder sortby,
 900                        dbus_int32_t count)
 901 {
 902   GList *ls = NULL;
 903   AtkObject *collection;
 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   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 == ATSPI_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 AtspiCollectionSortOrder 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   ls = g_list_append (ls, current_object);
 933
 934   if (recurse)
 935     {
 936       obj = ATK_OBJECT (atk_object_get_parent (current_object));
 937       query_exec (mrp, sortby, ls, 0, count,
 938                   obj, 0, TRUE, current_object, TRUE, traverse);
 939     }
 940   else
 941     {
 942       obj = ATK_OBJECT (spi_register_path_to_object (spi_global_register, dbus_message_get_path (message)));
 943       query_exec (mrp, sortby, ls, 0, count,
 944                   obj, 0, TRUE, current_object, TRUE, traverse);
 945
 946     }
 947
 948   ls = g_list_remove (ls, ls->data);
 949
 950   if (sortby != ATSPI_Collection_SORT_ORDER_REVERSE_CANONICAL)
 951     ls = g_list_reverse (ls);
 952
 953   free_mrp_data (mrp);
 954   return return_and_free_list (message, ls);
 955 }
 956
 957 static DBusMessage *
 958 impl_GetMatchesFrom (DBusConnection * bus, DBusMessage * message,
 959                      void *user_data)
 960 {
 961   char *current_object_path = NULL;
 962   AtkObject *current_object;
 963   DBusMessageIter iter;
 964   MatchRulePrivate rule;
 965   dbus_uint32_t sortby;
 966   dbus_uint32_t tree;
 967   dbus_int32_t count;
 968   dbus_bool_t traverse;
 969   const char *signature;
 970
 971   signature = dbus_message_get_signature (message);
 972   if (strcmp (signature, "o(aiia{ss}iaiiasib)uuib") != 0)
 973     {
 974       return droute_invalid_arguments_error (message);
 975     }
 976
 977   dbus_message_iter_init (message, &iter);
 978   dbus_message_iter_get_basic (&iter, &current_object_path);
 979   current_object = ATK_OBJECT (spi_register_path_to_object (spi_global_register, current_object_path));
 980   if (!current_object)
 981     {
 982       // TODO: object-not-found error
 983       return spi_dbus_general_error (message);
 984     }
 985   dbus_message_iter_next (&iter);
 986   if (!read_mr (&iter, &rule))
 987     {
 988       return spi_dbus_general_error (message);
 989     }
 990   dbus_message_iter_get_basic (&iter, &sortby);
 991   dbus_message_iter_next (&iter);
 992   dbus_message_iter_get_basic (&iter, &tree);
 993   dbus_message_iter_next (&iter);
 994   dbus_message_iter_get_basic (&iter, &count);
 995   dbus_message_iter_next (&iter);
 996   dbus_message_iter_get_basic (&iter, &traverse);
 997   dbus_message_iter_next (&iter);
 998
 999   switch (tree)
1000     {
1001     case ATSPI_Collection_TREE_RESTRICT_CHILDREN:
1002       return GetMatchesFrom (message, current_object,
1003                              &rule, sortby, TRUE, count, traverse);
1004       break;
1005     case ATSPI_Collection_TREE_RESTRICT_SIBLING:
1006       return GetMatchesFrom (message, current_object,
1007                              &rule, sortby, FALSE, count, traverse);
1008       break;
1009     case ATSPI_Collection_TREE_INORDER:
1010       return GetMatchesInOrder (message, current_object,
1011                                 &rule, sortby, TRUE, count, traverse);
1012       break;
1013     default:
1014       return NULL;
1015     }
1016 }
1017
1018 static DBusMessage *
1019 impl_GetMatchesTo (DBusConnection * bus, DBusMessage * message,
1020                    void *user_data)
1021 {
1022   char *current_object_path = NULL;
1023   AtkObject *current_object;
1024   DBusMessageIter iter;
1025   MatchRulePrivate rule;
1026   dbus_uint32_t sortby;
1027   dbus_uint32_t tree;
1028   dbus_bool_t recurse;
1029   dbus_int32_t count;
1030   dbus_bool_t traverse;
1031   const char *signature;
1032
1033   signature = dbus_message_get_signature (message);
1034   if (strcmp (signature, "o(aiia{ss}iaiiasib)uubib") != 0)
1035     {
1036       return droute_invalid_arguments_error (message);
1037     }
1038
1039   dbus_message_iter_init (message, &iter);
1040   dbus_message_iter_get_basic (&iter, &current_object_path);
1041   current_object = ATK_OBJECT (spi_register_path_to_object (spi_global_register, current_object_path));
1042   if (!current_object)
1043     {
1044       // TODO: object-not-found error
1045       return spi_dbus_general_error (message);
1046     }
1047   dbus_message_iter_next (&iter);
1048   if (!read_mr (&iter, &rule))
1049     {
1050       return spi_dbus_general_error (message);
1051     }
1052   dbus_message_iter_get_basic (&iter, &sortby);
1053   dbus_message_iter_next (&iter);
1054   dbus_message_iter_get_basic (&iter, &tree);
1055   dbus_message_iter_next (&iter);
1056   dbus_message_iter_get_basic (&iter, &recurse);
1057   dbus_message_iter_next (&iter);
1058   dbus_message_iter_get_basic (&iter, &count);
1059   dbus_message_iter_next (&iter);
1060   dbus_message_iter_get_basic (&iter, &traverse);
1061   dbus_message_iter_next (&iter);
1062
1063   switch (tree)
1064     {
1065     case ATSPI_Collection_TREE_RESTRICT_CHILDREN:
1066       return GetMatchesTo (message, current_object,
1067                            &rule, sortby, recurse, TRUE, count, traverse);
1068       break;
1069     case ATSPI_Collection_TREE_RESTRICT_SIBLING:
1070       return GetMatchesTo (message, current_object,
1071                            &rule, sortby, recurse, FALSE, count, traverse);
1072       break;
1073     case ATSPI_Collection_TREE_INORDER:
1074       return GetMatchesInBackOrder (message, current_object,
1075                                     &rule, sortby, count);
1076       break;
1077     default:
1078       return NULL;
1079     }
1080 }
1081
1082 static void
1083 append_accessible_properties (DBusMessageIter *iter, AtkObject *obj,
1084                               GArray *properties)
1085 {
1086   DBusMessageIter iter_struct, iter_dict, iter_dict_entry;
1087   AtkStateSet *set;
1088   gint i;
1089   gint count;
1090
1091   dbus_message_iter_open_container (iter, DBUS_TYPE_STRUCT, NULL, &iter_struct);
1092   spi_object_append_reference (&iter_struct, obj);
1093   dbus_message_iter_open_container (&iter_struct, DBUS_TYPE_ARRAY, "{sv}", &iter_dict);
1094   if (properties && properties->len)
1095   {
1096     gint i;
1097     for (i = 0; i < properties->len; i++)
1098     {
1099       gchar *prop = g_array_index (properties, char *, i);
1100       DRoutePropertyFunction func;
1101       GType type;
1102       func = _atk_bridge_find_property_func (prop, &type);
1103       if (func && G_TYPE_CHECK_INSTANCE_TYPE (obj, type))
1104       {
1105         dbus_message_iter_open_container (&iter_dict, DBUS_TYPE_DICT_ENTRY,
1106                                           NULL, &iter_dict_entry);
1107         dbus_message_iter_append_basic (&iter_dict_entry, DBUS_TYPE_STRING, &prop);
1108         func (&iter_dict_entry, obj);
1109         dbus_message_iter_close_container (&iter_dict, &iter_dict_entry);
1110       }
1111     }
1112   }
1113   else
1114   {
1115     GHashTableIter hi;
1116     gpointer key, value;
1117     g_hash_table_iter_init (&hi, spi_global_app_data->property_hash);
1118     while (g_hash_table_iter_next (&hi, &key, &value))
1119     {
1120       const DRouteProperty *prop = value;
1121       GType type = _atk_bridge_type_from_iface (key);
1122       if (!G_TYPE_CHECK_INSTANCE_TYPE (obj, type))
1123         continue;
1124       for (;prop->name; prop++)
1125       {
1126         const char *p = key + strlen (key);
1127         gchar *property_name;
1128         while (p[-1] != '.')
1129           p--;
1130         if (!strcmp (p, "Accessible"))
1131           property_name = g_strdup (prop->name);
1132         else
1133           property_name = g_strconcat (p, ".", prop->name, NULL);
1134         dbus_message_iter_open_container (&iter_dict, DBUS_TYPE_DICT_ENTRY,
1135                                           NULL, &iter_dict_entry);
1136         dbus_message_iter_append_basic (&iter_dict_entry, DBUS_TYPE_STRING, &property_name);
1137         g_free (property_name);
1138         prop->get (&iter_dict_entry, obj);
1139         dbus_message_iter_close_container (&iter_dict, &iter_dict_entry);
1140       }
1141     }
1142   }
1143   dbus_message_iter_close_container (&iter_struct, &iter_dict);
1144   dbus_message_iter_close_container (iter, &iter_struct);
1145
1146   set = atk_object_ref_state_set (obj);
1147   if (set)
1148   {
1149     gboolean md = atk_state_set_contains_state (set, ATK_STATE_MANAGES_DESCENDANTS);
1150     g_object_unref (set);
1151     if (md)
1152       return;
1153   }
1154   count = atk_object_get_n_accessible_children (obj);
1155   for (i = 0; i < count; i++)
1156   {
1157     AtkObject *child = atk_object_ref_accessible_child (obj, i);
1158     if (child)
1159     {
1160       append_accessible_properties (iter, child, properties);
1161       g_object_unref (child);
1162     }
1163   }
1164 }
1165
1166 #if 0
1167 static void
1168 skip (const char **p)
1169 {
1170   const char *sig = *p;
1171   gint nest = (*sig != 'a');
1172
1173   sig++;
1174   while (*sig)
1175   {
1176     if (*sig == '(' || *sig == '{')
1177       nest++;
1178     else if (*sig == ')' || *sig == '}')
1179       nest--;
1180     sig++;
1181   }
1182   *p = sig;
1183 }
1184
1185 static gboolean
1186 types_match (DBusMessageIter *iter, char c)
1187 {
1188   char t = dbus_message_iter_get_arg_type (iter);
1189
1190   if (t == 'r' && c == '(')
1191     return TRUE;
1192   else
1193     return (t == c);
1194 }
1195
1196 static void
1197 walk (DBusMessageIter *iter, const char *sig, gboolean array)
1198 {
1199   while (*sig && *sig != ')' && *sig != '}')
1200   {
1201     if (array && dbus_message_iter_get_arg_type (iter) == DBUS_TYPE_INVALID)
1202     break;
1203     if (!types_match (iter, *sig))
1204     {
1205       g_error ("Expected %s, got %c", sig, dbus_message_iter_get_arg_type (iter));
1206     }
1207     switch (*sig)
1208     {
1209     case 's':
1210       {
1211         const char *str;
1212         DBusError error;
1213         dbus_error_init (&error);
1214         dbus_message_iter_get_basic (iter, &str);
1215         g_print ("%s\n", str);
1216         if (!dbus_validate_utf8 (str, &error))
1217           g_error ("Bad UTF-8 string");
1218       }
1219       break;
1220     case 'a':
1221       {
1222         DBusMessageIter iter_array;
1223         dbus_message_iter_recurse (iter, &iter_array);
1224         walk (&iter_array, sig + 1, TRUE);
1225         skip (&sig);
1226       }
1227       break;
1228     case DBUS_TYPE_STRUCT:
1229     case DBUS_TYPE_DICT_ENTRY:
1230       {
1231         DBusMessageIter iter_struct;
1232         dbus_message_iter_recurse (iter, &iter_struct);
1233         walk (&iter_struct, sig + 1, FALSE);
1234         skip (&sig);
1235       }
1236     }
1237     dbus_message_iter_next (iter);
1238     if (!array)
1239       sig++;
1240   }
1241   if (dbus_message_iter_get_arg_type (iter) != DBUS_TYPE_INVALID)
1242     g_error ("Unexpected data '%c'", dbus_message_iter_get_arg_type (iter));
1243 }
1244
1245 static void
1246 walkm (DBusMessage *message)
1247 {
1248   DBusMessageIter iter;
1249   const char *sig = dbus_message_get_signature (message);
1250
1251   g_print ("sig: %s\n", sig);
1252   dbus_message_iter_init (message, &iter);
1253   walk (&iter, sig, FALSE);
1254 }
1255 #endif
1256
1257 static DBusMessage *
1258 impl_GetTree (DBusConnection * bus,
1259               DBusMessage * message, void *user_data)
1260 {
1261   AtkObject *object = (AtkObject *) user_data;
1262   DBusMessage *reply;
1263   DBusMessageIter iter, iter_array;
1264   MatchRulePrivate rule;
1265   GArray *properties;
1266
1267   g_return_val_if_fail (ATK_IS_OBJECT (user_data),
1268                         droute_not_yet_handled_error (message));
1269
1270   if (strcmp (dbus_message_get_signature (message), "(aiia{ss}iaiiasib)as") != 0)
1271     return droute_invalid_arguments_error (message);
1272
1273   properties = g_array_new (TRUE, TRUE, sizeof (char *));
1274   dbus_message_iter_init (message, &iter);
1275   if (!read_mr (&iter, &rule))
1276     {
1277       return spi_dbus_general_error (message);
1278     }
1279
1280   dbus_message_iter_recurse (&iter, &iter_array);
1281   while (dbus_message_iter_get_arg_type (&iter_array) != DBUS_TYPE_INVALID)
1282   {
1283     const char *prop;
1284     dbus_message_iter_get_basic (&iter_array, &prop);
1285     g_array_append_val (properties, prop);
1286     dbus_message_iter_next (&iter_array);
1287   }
1288
1289   reply = dbus_message_new_method_return (message);
1290   if (reply)
1291     {
1292       dbus_message_iter_init_append (reply, &iter);
1293       dbus_message_iter_open_container (&iter, DBUS_TYPE_ARRAY, "((so)a{sv})",
1294                                         &iter_array);
1295       append_accessible_properties (&iter_array, object, properties);
1296       dbus_message_iter_close_container (&iter, &iter_array);
1297     }
1298 #if 0
1299   walkm (reply);
1300 #endif
1301   return reply;
1302 }
1303
1304 static DBusMessage *
1305 impl_GetMatches (DBusConnection * bus, DBusMessage * message, void *user_data)
1306 {
1307   AtkObject *obj = ATK_OBJECT (spi_register_path_to_object (spi_global_register, dbus_message_get_path (message)));
1308   DBusMessageIter iter;
1309   MatchRulePrivate rule;
1310   dbus_uint32_t sortby;
1311   dbus_int32_t count;
1312   dbus_bool_t traverse;
1313   GList *ls = NULL;
1314   const char *signature;
1315
1316   signature = dbus_message_get_signature (message);
1317   if (strcmp (signature, "(aiia{ss}iaiiasib)uib") != 0)
1318     {
1319       return droute_invalid_arguments_error (message);
1320     }
1321
1322   dbus_message_iter_init (message, &iter);
1323   if (!read_mr (&iter, &rule))
1324     {
1325       return spi_dbus_general_error (message);
1326     }
1327   dbus_message_iter_get_basic (&iter, &sortby);
1328   dbus_message_iter_next (&iter);
1329   dbus_message_iter_get_basic (&iter, &count);
1330   dbus_message_iter_next (&iter);
1331   dbus_message_iter_get_basic (&iter, &traverse);
1332   dbus_message_iter_next (&iter);
1333   ls = g_list_prepend (ls, obj);
1334   count = query_exec (&rule, sortby, ls, 0, count,
1335                       obj, 0, TRUE, NULL, TRUE, traverse);
1336   ls = g_list_remove (ls, ls->data);
1337
1338   if (sortby == ATSPI_Collection_SORT_ORDER_REVERSE_CANONICAL)
1339     ls = g_list_reverse (ls);
1340   free_mrp_data (&rule);
1341   return return_and_free_list (message, ls);
1342 }
1343
1344 static DRouteMethod methods[] = {
1345   {impl_GetMatchesFrom, "GetMatchesFrom"},
1346   {impl_GetMatchesTo, "GetMatchesTo"},
1347   {impl_GetTree, "GetTree"},
1348   {impl_GetMatches, "GetMatches"},
1349   {NULL, NULL}
1350 };
1351
1352 void
1353 spi_initialize_collection (DRoutePath * path)
1354 {
1355   spi_atk_add_interface (path,
1356                          ATSPI_DBUS_INTERFACE_COLLECTION, spi_org_a11y_atspi_Collection, methods, NULL);
1357 };