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 #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       g_object_unref (child);
 498       if (prev && child == pobj)
 499         {
 500           return kount;
 501         }
 502
 503       if (flag && match_interfaces_lookup (child, mrp)
 504           && match_states_lookup (child, mrp)
 505           && match_roles_lookup (child, mrp)
 506           && match_attributes_lookup (child, mrp))
 507         {
 508
 509           ls = g_list_append (ls, child);
 510           kount++;
 511         }
 512
 513       if (!flag)
 514         flag = TRUE;
 515
 516       if (recurse && traverse_p (child, traverse))
 517         kount = sort_order_canonical (mrp, ls, kount,
 518                                       max, child, 0, TRUE,
 519                                       pobj, recurse, traverse);
 520     }
 521   return kount;
 522 }
 523
 524 static int
 525 sort_order_rev_canonical (MatchRulePrivate * mrp, GList * ls,
 526                           gint kount, gint max,
 527                           AtkObject * obj, gboolean flag, AtkObject * pobj)
 528 {
 529   AtkObject *nextobj;
 530   AtkObject *parent;
 531   glong indexinparent;
 532
 533   /* This breaks us out of the recursion. */
 534   if (!obj || obj == pobj)
 535     {
 536       return kount;
 537     }
 538
 539   /* Add to the list if it matches */
 540   if (flag && match_interfaces_lookup (obj, mrp)
 541       && match_states_lookup (obj, mrp)
 542       && match_roles_lookup (obj, mrp) && match_attributes_lookup (obj, mrp)
 543       && (max == 0 || kount < max))
 544     {
 545       ls = g_list_append (ls, obj);
 546       kount++;
 547     }
 548
 549   if (!flag)
 550     flag = TRUE;
 551
 552   /* Get the current nodes index in it's parent and the parent object. */
 553   indexinparent = atk_object_get_index_in_parent (obj);
 554   parent = atk_object_get_parent (obj);
 555
 556   if (indexinparent > 0 && (max == 0 || kount < max))
 557     {
 558       /* there are still some siblings to visit so get the previous sibling
 559          and get it's last descendant.
 560          First, get the previous sibling */
 561       nextobj = atk_object_ref_accessible_child (parent, indexinparent - 1);
 562       g_object_unref (nextobj);
 563
 564       /* Now, drill down the right side to the last descendant */
 565       while (atk_object_get_n_accessible_children (nextobj) > 0)
 566         {
 567           nextobj = atk_object_ref_accessible_child (nextobj,
 568                                                      atk_object_get_n_accessible_children
 569                                                      (nextobj) - 1);
 570           g_object_unref (nextobj);
 571         }
 572       /* recurse with the last descendant */
 573       kount = sort_order_rev_canonical (mrp, ls, kount, max,
 574                                         nextobj, TRUE, pobj);
 575     }
 576   else if (max == 0 || kount < max)
 577     {
 578       /* no more siblings so next node must be the parent */
 579       kount = sort_order_rev_canonical (mrp, ls, kount, max,
 580                                         parent, TRUE, pobj);
 581
 582     }
 583   return kount;
 584 }
 585
 586 static int
 587 query_exec (MatchRulePrivate * mrp, AtspiCollectionSortOrder sortby,
 588             GList * ls, gint kount, gint max,
 589             AtkObject * obj, glong index,
 590             gboolean flag,
 591             AtkObject * pobj, gboolean recurse, gboolean traverse)
 592 {
 593   switch (sortby)
 594     {
 595     case ATSPI_Collection_SORT_ORDER_CANONICAL:
 596       kount = sort_order_canonical (mrp, ls, 0, max, obj, index, flag,
 597                                     pobj, recurse, traverse);
 598       break;
 599     case ATSPI_Collection_SORT_ORDER_REVERSE_CANONICAL:
 600       kount = sort_order_canonical (mrp, ls, 0, max, obj, index, flag,
 601                                     pobj, recurse, traverse);
 602       break;
 603     default:
 604       kount = 0;
 605       g_warning ("Sort method not implemented yet");
 606       break;
 607     }
 608
 609   return kount;
 610 }
 611
 612 static gboolean
 613 bitarray_to_seq (dbus_uint32_t *array, int array_count, int **ret)
 614 {
 615   int out_size = 4;
 616   int out_count = 0;
 617   int i, j;
 618   int *out = (int *) g_malloc (out_size * sizeof (int));
 619
 620   if (!out)
 621     return FALSE;
 622   for (i = 0; i < array_count; i++)
 623     {
 624       for (j = 0; j < 32; j++)
 625         {
 626           if (array[i] & (1 << j))
 627             {
 628               if (out_count == out_size - 2)
 629                 {
 630                   out_size <<= 1;
 631                   out = (int *) g_realloc (out, out_size * sizeof (int));
 632                   if (!out)
 633                     return FALSE;
 634                 }
 635               out[out_count++] = i * 32 + j;
 636             }
 637         }
 638     }
 639   out[out_count] = BITARRAY_SEQ_TERM;
 640   *ret = out;
 641   return TRUE;
 642 }
 643
 644
 645 static dbus_bool_t
 646 read_mr (DBusMessageIter * iter, MatchRulePrivate * mrp)
 647 {
 648   DBusMessageIter iter_struct, iter_array, iter_dict, iter_dict_entry;
 649   dbus_uint32_t *array;
 650   dbus_int32_t matchType;
 651   int array_count;
 652   AtkAttribute *attr;
 653   int i;
 654
 655   dbus_message_iter_recurse (iter, &iter_struct);
 656
 657   /* states */
 658   dbus_message_iter_recurse (&iter_struct, &iter_array);
 659   dbus_message_iter_get_fixed_array (&iter_array, &array, &array_count);
 660   bitarray_to_seq (array, array_count, &mrp->states);
 661   for (i = 0; mrp->states[i] != BITARRAY_SEQ_TERM; i++)
 662     {
 663       mrp->states[i] = spi_atk_state_from_spi_state (mrp->states[i]);
 664     }
 665   dbus_message_iter_next (&iter_struct);
 666   dbus_message_iter_get_basic (&iter_struct, &matchType);
 667   dbus_message_iter_next (&iter_struct);
 668   mrp->statematchtype = matchType;;
 669
 670   /* attributes */
 671   mrp->attributes = NULL;
 672   dbus_message_iter_recurse (&iter_struct, &iter_dict);
 673   while (dbus_message_iter_get_arg_type (&iter_dict) != DBUS_TYPE_INVALID)
 674     {
 675       const char *key, *val;
 676       const char *p, *q;
 677       dbus_message_iter_recurse (&iter_dict, &iter_dict_entry);
 678       dbus_message_iter_get_basic (&iter_dict_entry, &key);
 679       dbus_message_iter_next (&iter_dict_entry);
 680       dbus_message_iter_get_basic (&iter_dict_entry, &val);
 681       p = q = val;
 682       for (;;)
 683       {
 684         if (*q == '\0' || (*q == ':' && (q == val || q[-1] != '\\')))
 685         {
 686           char *tmp;
 687           attr = g_new (AtkAttribute, 1);
 688           attr->name = g_strdup (key);
 689           attr->value = g_strdup (p);
 690           attr->value[q - p] = '\0';
 691           tmp = attr->value;
 692           while (*tmp != '\0')
 693           {
 694             if (*tmp == '\\')
 695               memmove (tmp, tmp + 1, strlen (tmp));
 696             else
 697               tmp++;
 698           }
 699           mrp->attributes = g_slist_prepend (mrp->attributes, attr);
 700           if (*q == '\0')
 701             break;
 702           else
 703             p = ++q;
 704         }
 705         else
 706           q++;
 707       }
 708       dbus_message_iter_next (&iter_dict);
 709     }
 710   dbus_message_iter_next (&iter_struct);
 711   dbus_message_iter_get_basic (&iter_struct, &matchType);
 712   mrp->attributematchtype = matchType;;
 713   dbus_message_iter_next (&iter_struct);
 714
 715   /* Get roles and role match */
 716   dbus_message_iter_recurse (&iter_struct, &iter_array);
 717   dbus_message_iter_get_fixed_array (&iter_array, &array, &array_count);
 718   bitarray_to_seq (array, array_count, &mrp->roles);
 719   dbus_message_iter_next (&iter_struct);
 720   dbus_message_iter_get_basic (&iter_struct, &matchType);
 721   mrp->rolematchtype = matchType;;
 722   dbus_message_iter_next (&iter_struct);
 723
 724   /* Get interfaces and interface match */
 725   dbus_message_iter_recurse (&iter_struct, &iter_array);
 726   mrp->ifaces = g_new0 (gchar *, 16);
 727   i = 0;
 728   while (i < 15 && dbus_message_iter_get_arg_type (&iter_array) != DBUS_TYPE_INVALID)
 729   {
 730     char *iface;
 731     dbus_message_iter_get_basic (&iter_array, &iface);
 732     mrp->ifaces [i] = g_strdup (iface);
 733     i++;
 734     dbus_message_iter_next (&iter_array);
 735   }
 736   dbus_message_iter_next (&iter_struct);
 737   dbus_message_iter_get_basic (&iter_struct, &matchType);
 738   mrp->interfacematchtype = matchType;;
 739   dbus_message_iter_next (&iter_struct);
 740   /* get invert */
 741   dbus_message_iter_get_basic (&iter_struct, &mrp->invert);
 742   dbus_message_iter_next (iter);
 743   return TRUE;
 744 }
 745
 746 static DBusMessage *
 747 return_and_free_list (DBusMessage * message, GList * ls)
 748 {
 749   DBusMessage *reply;
 750   DBusMessageIter iter, iter_array;
 751   GList *item;
 752
 753   reply = dbus_message_new_method_return (message);
 754   if (!reply)
 755     return NULL;
 756   dbus_message_iter_init_append (reply, &iter);
 757   if (!dbus_message_iter_open_container
 758       (&iter, DBUS_TYPE_ARRAY, "(so)", &iter_array))
 759     goto oom;
 760   for (item = ls; item; item = g_list_next (item))
 761     {
 762       spi_object_append_reference (&iter_array, ATK_OBJECT (item->data));
 763     }
 764   if (!dbus_message_iter_close_container (&iter, &iter_array))
 765     goto oom;
 766   g_list_free (ls);
 767   return reply;
 768 oom:
 769   // TODO: Handle out of memory
 770   g_list_free (ls);
 771   return reply;
 772 }
 773
 774 static void
 775 free_mrp_data (MatchRulePrivate * mrp)
 776 {
 777   g_free (mrp->states);
 778   atk_attribute_set_free (mrp->attributes);
 779   g_free (mrp->roles);
 780   g_strfreev (mrp->ifaces);
 781 }
 782
 783 static DBusMessage *
 784 GetMatchesFrom (DBusMessage * message,
 785                 AtkObject * current_object,
 786                 MatchRulePrivate * mrp,
 787                 const AtspiCollectionSortOrder sortby,
 788                 const dbus_bool_t isrestrict,
 789                 dbus_int32_t count, const dbus_bool_t traverse)
 790 {
 791   GList *ls = NULL;
 792   AtkObject *parent;
 793   glong index = atk_object_get_index_in_parent (current_object);
 794
 795   ls = g_list_append (ls, current_object);
 796
 797   if (!isrestrict)
 798     {
 799       parent = atk_object_get_parent (current_object);
 800       query_exec (mrp, sortby, ls, 0, count, parent, index,
 801                   FALSE, NULL, TRUE, traverse);
 802     }
 803   else
 804     query_exec (mrp, sortby, ls, 0, count,
 805                 current_object, 0, FALSE, NULL, TRUE, traverse);
 806
 807   ls = g_list_remove (ls, ls->data);
 808
 809   if (sortby == ATSPI_Collection_SORT_ORDER_REVERSE_CANONICAL)
 810     ls = g_list_reverse (ls);
 811
 812   free_mrp_data (mrp);
 813   return return_and_free_list (message, ls);
 814 }
 815
 816 /*
 817   inorder traversal from a given object in the hierarchy
 818 */
 819
 820 static int
 821 inorder (AtkObject * collection, MatchRulePrivate * mrp,
 822          GList * ls, gint kount, gint max,
 823          AtkObject * obj,
 824          gboolean flag, AtkObject * pobj, dbus_bool_t traverse)
 825 {
 826   int i = 0;
 827
 828   /* First, look through the children recursively. */
 829   kount = sort_order_canonical (mrp, ls, kount, max, obj, 0, TRUE,
 830                                 NULL, TRUE, TRUE);
 831
 832   /* Next, we look through the right subtree */
 833   while ((max == 0 || kount < max) && obj != collection)
 834     {
 835       AtkObject *parent = atk_object_get_parent (obj);
 836       i = atk_object_get_index_in_parent (obj);
 837       kount = sort_order_canonical (mrp, ls, kount, max, parent,
 838                                     i + 1, TRUE, FALSE, TRUE, TRUE);
 839       obj = parent;
 840     }
 841
 842   if (max == 0 || kount < max)
 843     {
 844       kount = sort_order_canonical (mrp, ls, kount, max,
 845                                     obj, i + 1, TRUE, FALSE, TRUE, TRUE);
 846     }
 847
 848   return kount;
 849 }
 850
 851 /*
 852   GetMatchesInOrder: get matches from a given object in an inorder traversal.
 853 */
 854
 855 static DBusMessage *
 856 GetMatchesInOrder (DBusMessage * message,
 857                    AtkObject * current_object,
 858                    MatchRulePrivate * mrp,
 859                    const AtspiCollectionSortOrder sortby,
 860                    const dbus_bool_t recurse,
 861                    dbus_int32_t count, const dbus_bool_t traverse)
 862 {
 863   GList *ls = NULL;
 864   AtkObject *obj;
 865
 866   ls = g_list_append (ls, current_object);
 867
 868   obj = ATK_OBJECT(spi_register_path_to_object (spi_global_register, dbus_message_get_path (message)));
 869
 870   inorder (obj, mrp, ls, 0, count,
 871            current_object, TRUE, NULL, traverse);
 872
 873   ls = g_list_remove (ls, ls->data);
 874
 875   if (sortby == ATSPI_Collection_SORT_ORDER_REVERSE_CANONICAL)
 876     ls = g_list_reverse (ls);
 877
 878   free_mrp_data (mrp);
 879   return return_and_free_list (message, ls);
 880 }
 881
 882 /*
 883   GetMatchesInBackOrder: get matches from a given object in a
 884   reverse order traversal.
 885 */
 886
 887 static DBusMessage *
 888 GetMatchesInBackOrder (DBusMessage * message,
 889                        AtkObject * current_object,
 890                        MatchRulePrivate * mrp,
 891                        const AtspiCollectionSortOrder sortby,
 892                        dbus_int32_t count)
 893 {
 894   GList *ls = NULL;
 895   AtkObject *collection;
 896
 897   ls = g_list_append (ls, current_object);
 898
 899   collection = ATK_OBJECT(spi_register_path_to_object (spi_global_register, dbus_message_get_path (message)));
 900
 901   sort_order_rev_canonical (mrp, ls, 0, count, current_object,
 902                             FALSE, collection);
 903
 904   ls = g_list_remove (ls, ls->data);
 905
 906   if (sortby == ATSPI_Collection_SORT_ORDER_REVERSE_CANONICAL)
 907     ls = g_list_reverse (ls);
 908
 909   free_mrp_data (mrp);
 910   return return_and_free_list (message, ls);
 911 }
 912
 913 static DBusMessage *
 914 GetMatchesTo (DBusMessage * message,
 915               AtkObject * current_object,
 916               MatchRulePrivate * mrp,
 917               const AtspiCollectionSortOrder sortby,
 918               const dbus_bool_t recurse,
 919               const dbus_bool_t isrestrict,
 920               dbus_int32_t count, const dbus_bool_t traverse)
 921 {
 922   GList *ls = NULL;
 923   AtkObject *obj;
 924   ls = g_list_append (ls, current_object);
 925
 926   if (recurse)
 927     {
 928       obj = ATK_OBJECT (atk_object_get_parent (current_object));
 929       query_exec (mrp, sortby, ls, 0, count,
 930                   obj, 0, TRUE, current_object, TRUE, traverse);
 931     }
 932   else
 933     {
 934       obj = ATK_OBJECT (spi_register_path_to_object (spi_global_register, dbus_message_get_path (message)));
 935       query_exec (mrp, sortby, ls, 0, count,
 936                   obj, 0, TRUE, current_object, TRUE, traverse);
 937
 938     }
 939
 940   ls = g_list_remove (ls, ls->data);
 941
 942   if (sortby != ATSPI_Collection_SORT_ORDER_REVERSE_CANONICAL)
 943     ls = g_list_reverse (ls);
 944
 945   free_mrp_data (mrp);
 946   return return_and_free_list (message, ls);
 947 }
 948
 949 static DBusMessage *
 950 impl_GetMatchesFrom (DBusConnection * bus, DBusMessage * message,
 951                      void *user_data)
 952 {
 953   char *current_object_path = NULL;
 954   AtkObject *current_object;
 955   DBusMessageIter iter;
 956   MatchRulePrivate rule;
 957   dbus_uint32_t sortby;
 958   dbus_uint32_t tree;
 959   dbus_int32_t count;
 960   dbus_bool_t traverse;
 961   const char *signature;
 962
 963   signature = dbus_message_get_signature (message);
 964   if (strcmp (signature, "o(aiia{ss}iaiiasib)uuib") != 0)
 965     {
 966       return droute_invalid_arguments_error (message);
 967     }
 968
 969   dbus_message_iter_init (message, &iter);
 970   dbus_message_iter_get_basic (&iter, &current_object_path);
 971   current_object = ATK_OBJECT (spi_register_path_to_object (spi_global_register, current_object_path));
 972   if (!current_object)
 973     {
 974       // TODO: object-not-found error
 975       return spi_dbus_general_error (message);
 976     }
 977   dbus_message_iter_next (&iter);
 978   if (!read_mr (&iter, &rule))
 979     {
 980       return spi_dbus_general_error (message);
 981     }
 982   dbus_message_iter_get_basic (&iter, &sortby);
 983   dbus_message_iter_next (&iter);
 984   dbus_message_iter_get_basic (&iter, &tree);
 985   dbus_message_iter_next (&iter);
 986   dbus_message_iter_get_basic (&iter, &count);
 987   dbus_message_iter_next (&iter);
 988   dbus_message_iter_get_basic (&iter, &traverse);
 989   dbus_message_iter_next (&iter);
 990
 991   switch (tree)
 992     {
 993     case ATSPI_Collection_TREE_RESTRICT_CHILDREN:
 994       return GetMatchesFrom (message, current_object,
 995                              &rule, sortby, TRUE, count, traverse);
 996       break;
 997     case ATSPI_Collection_TREE_RESTRICT_SIBLING:
 998       return GetMatchesFrom (message, current_object,
 999                              &rule, sortby, FALSE, count, traverse);
1000       break;
1001     case ATSPI_Collection_TREE_INORDER:
1002       return GetMatchesInOrder (message, current_object,
1003                                 &rule, sortby, TRUE, count, traverse);
1004       break;
1005     default:
1006       return NULL;
1007     }
1008 }
1009
1010 static DBusMessage *
1011 impl_GetMatchesTo (DBusConnection * bus, DBusMessage * message,
1012                    void *user_data)
1013 {
1014   char *current_object_path = NULL;
1015   AtkObject *current_object;
1016   DBusMessageIter iter;
1017   MatchRulePrivate rule;
1018   dbus_uint32_t sortby;
1019   dbus_uint32_t tree;
1020   dbus_bool_t recurse;
1021   dbus_int32_t count;
1022   dbus_bool_t traverse;
1023   const char *signature;
1024
1025   signature = dbus_message_get_signature (message);
1026   if (strcmp (signature, "o(aiia{ss}iaiiasib)uubib") != 0)
1027     {
1028       return droute_invalid_arguments_error (message);
1029     }
1030
1031   dbus_message_iter_init (message, &iter);
1032   dbus_message_iter_get_basic (&iter, &current_object_path);
1033   current_object = ATK_OBJECT (spi_register_path_to_object (spi_global_register, current_object_path));
1034   if (!current_object)
1035     {
1036       // TODO: object-not-found error
1037       return spi_dbus_general_error (message);
1038     }
1039   dbus_message_iter_next (&iter);
1040   if (!read_mr (&iter, &rule))
1041     {
1042       return spi_dbus_general_error (message);
1043     }
1044   dbus_message_iter_get_basic (&iter, &sortby);
1045   dbus_message_iter_next (&iter);
1046   dbus_message_iter_get_basic (&iter, &tree);
1047   dbus_message_iter_next (&iter);
1048   dbus_message_iter_get_basic (&iter, &recurse);
1049   dbus_message_iter_next (&iter);
1050   dbus_message_iter_get_basic (&iter, &count);
1051   dbus_message_iter_next (&iter);
1052   dbus_message_iter_get_basic (&iter, &traverse);
1053   dbus_message_iter_next (&iter);
1054
1055   switch (tree)
1056     {
1057     case ATSPI_Collection_TREE_RESTRICT_CHILDREN:
1058       return GetMatchesTo (message, current_object,
1059                            &rule, sortby, recurse, TRUE, count, traverse);
1060       break;
1061     case ATSPI_Collection_TREE_RESTRICT_SIBLING:
1062       return GetMatchesTo (message, current_object,
1063                            &rule, sortby, recurse, FALSE, count, traverse);
1064       break;
1065     case ATSPI_Collection_TREE_INORDER:
1066       return GetMatchesInBackOrder (message, current_object,
1067                                     &rule, sortby, count);
1068       break;
1069     default:
1070       return NULL;
1071     }
1072 }
1073
1074 static void
1075 append_accessible_properties (DBusMessageIter *iter, AtkObject *obj,
1076                               GArray *properties)
1077 {
1078   DBusMessageIter iter_struct, iter_dict, iter_dict_entry;
1079   AtkStateSet *set;
1080   gint i;
1081   gint count;
1082
1083   dbus_message_iter_open_container (iter, DBUS_TYPE_STRUCT, NULL, &iter_struct);
1084   spi_object_append_reference (&iter_struct, obj);
1085   dbus_message_iter_open_container (&iter_struct, DBUS_TYPE_ARRAY, "{sv}", &iter_dict);
1086   if (properties && properties->len)
1087   {
1088     gint i;
1089     for (i = 0; i < properties->len; i++)
1090     {
1091       gchar *prop = g_array_index (properties, char *, i);
1092       DRoutePropertyFunction func;
1093       GType type;
1094       func = _atk_bridge_find_property_func (prop, &type);
1095       if (func && G_TYPE_CHECK_INSTANCE_TYPE (obj, type))
1096       {
1097         dbus_message_iter_open_container (&iter_dict, DBUS_TYPE_DICT_ENTRY,
1098                                           NULL, &iter_dict_entry);
1099         dbus_message_iter_append_basic (&iter_dict_entry, DBUS_TYPE_STRING, &prop);
1100         func (&iter_dict_entry, obj);
1101         dbus_message_iter_close_container (&iter_dict, &iter_dict_entry);
1102       }
1103     }
1104   }
1105   else
1106   {
1107     GHashTableIter hi;
1108     gpointer key, value;
1109     g_hash_table_iter_init (&hi, spi_global_app_data->property_hash);
1110     while (g_hash_table_iter_next (&hi, &key, &value))
1111     {
1112       const DRouteProperty *prop = value;
1113       GType type = _atk_bridge_type_from_iface (key);
1114       if (!G_TYPE_CHECK_INSTANCE_TYPE (obj, type))
1115         continue;
1116       for (;prop->name; prop++)
1117       {
1118         const char *p = key + strlen (key);
1119         gchar *property_name;
1120         while (p[-1] != '.')
1121           p--;
1122         if (!strcmp (p, "Accessible"))
1123           property_name = g_strdup (prop->name);
1124         else
1125           property_name = g_strconcat (p, ".", prop->name, NULL);
1126         dbus_message_iter_open_container (&iter_dict, DBUS_TYPE_DICT_ENTRY,
1127                                           NULL, &iter_dict_entry);
1128         dbus_message_iter_append_basic (&iter_dict_entry, DBUS_TYPE_STRING, &property_name);
1129         g_free (property_name);
1130         prop->get (&iter_dict_entry, obj);
1131         dbus_message_iter_close_container (&iter_dict, &iter_dict_entry);
1132       }
1133     }
1134   }
1135   dbus_message_iter_close_container (&iter_struct, &iter_dict);
1136   dbus_message_iter_close_container (iter, &iter_struct);
1137
1138   set = atk_object_ref_state_set (obj);
1139   if (set)
1140   {
1141     gboolean md = atk_state_set_contains_state (set, ATK_STATE_MANAGES_DESCENDANTS);
1142     g_object_unref (set);
1143     if (md)
1144       return;
1145   }
1146   count = atk_object_get_n_accessible_children (obj);
1147   for (i = 0; i < count; i++)
1148   {
1149     AtkObject *child = atk_object_ref_accessible_child (obj, i);
1150     if (child)
1151     {
1152       append_accessible_properties (iter, child, properties);
1153       g_object_unref (child);
1154     }
1155   }
1156 }
1157
1158 static void
1159 skip (const char **p)
1160 {
1161   const char *sig = *p;
1162   gint nest = (*sig != 'a');
1163
1164   sig++;
1165   while (*sig)
1166   {
1167     if (*sig == '(' || *sig == '{')
1168       nest++;
1169     else if (*sig == ')' || *sig == '}')
1170       nest--;
1171     sig++;
1172   }
1173   *p = sig;
1174 }
1175
1176 static gboolean
1177 types_match (DBusMessageIter *iter, char c)
1178 {
1179   char t = dbus_message_iter_get_arg_type (iter);
1180
1181   if (t == 'r' && c == '(')
1182     return TRUE;
1183   else if (t != c)
1184     return FALSE;
1185 }
1186
1187 static void
1188 walk (DBusMessageIter *iter, const char *sig, gboolean array)
1189 {
1190   while (*sig && *sig != ')' && *sig != '}')
1191   {
1192     if (array && dbus_message_iter_get_arg_type (iter) == DBUS_TYPE_INVALID)
1193     break;
1194     if (!types_match (iter, *sig))
1195     {
1196       g_error ("Expected %s, got %c", sig, dbus_message_iter_get_arg_type (iter));
1197     }
1198     switch (*sig)
1199     {
1200     case 's':
1201       {
1202         const char *str;
1203         DBusError error;
1204         dbus_error_init (&error);
1205         dbus_message_iter_get_basic (iter, &str);
1206         g_print ("%s\n", str);
1207         if (!dbus_validate_utf8 (str, &error))
1208           g_error ("Bad UTF-8 string");
1209       }
1210       break;
1211     case 'a':
1212       {
1213         DBusMessageIter iter_array;
1214         dbus_message_iter_recurse (iter, &iter_array);
1215         walk (&iter_array, sig + 1, TRUE);
1216         skip (&sig);
1217       }
1218       break;
1219     case DBUS_TYPE_STRUCT:
1220     case DBUS_TYPE_DICT_ENTRY:
1221       {
1222         DBusMessageIter iter_struct;
1223         dbus_message_iter_recurse (iter, &iter_struct);
1224         walk (&iter_struct, sig + 1, FALSE);
1225         skip (&sig);
1226       }
1227     }
1228     dbus_message_iter_next (iter);
1229     if (!array)
1230       sig++;
1231   }
1232   if (dbus_message_iter_get_arg_type (iter) != DBUS_TYPE_INVALID)
1233     g_error ("Unexpected data '%c'", dbus_message_iter_get_arg_type (iter));
1234 }
1235
1236 static void
1237 walkm (DBusMessage *message)
1238 {
1239   DBusMessageIter iter;
1240   const char *sig = dbus_message_get_signature (message);
1241
1242   g_print ("sig: %s\n", sig);
1243   dbus_message_iter_init (message, &iter);
1244   walk (&iter, sig, FALSE);
1245 }
1246
1247 static DBusMessage *
1248 impl_GetTree (DBusConnection * bus,
1249               DBusMessage * message, void *user_data)
1250 {
1251   AtkObject *object = (AtkObject *) user_data;
1252   DBusMessage *reply;
1253   DBusMessageIter iter, iter_array;
1254   MatchRulePrivate rule;
1255   GArray *properties;
1256
1257   g_return_val_if_fail (ATK_IS_OBJECT (user_data),
1258                         droute_not_yet_handled_error (message));
1259
1260   if (strcmp (dbus_message_get_signature (message), "(aiia{ss}iaiiasib)as") != 0)
1261     return droute_invalid_arguments_error (message);
1262
1263   properties = g_array_new (TRUE, TRUE, sizeof (char *));
1264   dbus_message_iter_init (message, &iter);
1265   if (!read_mr (&iter, &rule))
1266     {
1267       return spi_dbus_general_error (message);
1268     }
1269
1270   dbus_message_iter_recurse (&iter, &iter_array);
1271   while (dbus_message_iter_get_arg_type (&iter_array) != DBUS_TYPE_INVALID)
1272   {
1273     const char *prop;
1274     dbus_message_iter_get_basic (&iter_array, &prop);
1275     g_array_append_val (properties, prop);
1276     dbus_message_iter_next (&iter_array);
1277   }
1278
1279   reply = dbus_message_new_method_return (message);
1280   if (reply)
1281     {
1282       dbus_message_iter_init_append (reply, &iter);
1283       dbus_message_iter_open_container (&iter, DBUS_TYPE_ARRAY, "((so)a{sv})",
1284                                         &iter_array);
1285       append_accessible_properties (&iter_array, object, properties);
1286       dbus_message_iter_close_container (&iter, &iter_array);
1287     }
1288 //walkm (reply);
1289   return reply;
1290 }
1291
1292 static DBusMessage *
1293 impl_GetMatches (DBusConnection * bus, DBusMessage * message, void *user_data)
1294 {
1295   AtkObject *obj = ATK_OBJECT (spi_register_path_to_object (spi_global_register, dbus_message_get_path (message)));
1296   DBusMessageIter iter;
1297   MatchRulePrivate rule;
1298   dbus_uint32_t sortby;
1299   dbus_int32_t count;
1300   dbus_bool_t traverse;
1301   GList *ls = NULL;
1302   const char *signature;
1303
1304   signature = dbus_message_get_signature (message);
1305   if (strcmp (signature, "(aiia{ss}iaiiasib)uib") != 0)
1306     {
1307       return droute_invalid_arguments_error (message);
1308     }
1309
1310   dbus_message_iter_init (message, &iter);
1311   if (!read_mr (&iter, &rule))
1312     {
1313       return spi_dbus_general_error (message);
1314     }
1315   dbus_message_iter_get_basic (&iter, &sortby);
1316   dbus_message_iter_next (&iter);
1317   dbus_message_iter_get_basic (&iter, &count);
1318   dbus_message_iter_next (&iter);
1319   dbus_message_iter_get_basic (&iter, &traverse);
1320   dbus_message_iter_next (&iter);
1321   ls = g_list_prepend (ls, obj);
1322   count = query_exec (&rule, sortby, ls, 0, count,
1323                       obj, 0, TRUE, NULL, TRUE, traverse);
1324   ls = g_list_remove (ls, ls->data);
1325
1326   if (sortby == ATSPI_Collection_SORT_ORDER_REVERSE_CANONICAL)
1327     ls = g_list_reverse (ls);
1328   free_mrp_data (&rule);
1329   return return_and_free_list (message, ls);
1330 }
1331
1332 static DRouteMethod methods[] = {
1333   {impl_GetMatchesFrom, "GetMatchesFrom"},
1334   {impl_GetMatchesTo, "GetMatchesTo"},
1335   {impl_GetTree, "GetTree"},
1336   {impl_GetMatches, "GetMatches"},
1337   {NULL, NULL}
1338 };
1339
1340 void
1341 spi_initialize_collection (DRoutePath * path)
1342 {
1343   spi_atk_add_interface (path,
1344                          ATSPI_DBUS_INTERFACE_COLLECTION, spi_org_a11y_atspi_Collection, methods, NULL);
1345 };