test/screen-review-test.c

   1 /*
   2  * AT-SPI - Assistive Technology Service Provider Interface
   3  * (Gnome Accessibility Project; http://developer.gnome.org/projects/gap)
   4  *
   5  * Copyright 2001, 2002 Sun Microsystems Inc.,
   6  * Copyright 2001, 2002 Ximian, Inc.
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Library General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Library General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Library General Public
  19  * License along with this library; if not, write to the
  20  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  21  * Boston, MA 02111-1307, USA.
  22  */
  23
  24 #include <stdio.h>
  25 #include <strings.h>
  26 #include <stdlib.h>
  27 #include "../cspi/spi-private.h"
  28
  29 #undef CLIP_DEBUG
  30
  31 /*
  32  * Screen Review Algorithm Demonstration, Benchmark, and Test-bed.
  33  *
  34  * Issues:
  35  *
  36  * * there are bugs in the compositing code.
  37  *
  38  * * brute-force algorithm uses no client-side cache; performance mediocre.
  39  *
  40  * * we don't have good ordering information for the toplevel windows,
  41  *          and our current heuristic is not guaranteed if
  42  *          the active window is not always on top (i.e. autoraise is
  43  *          not enabled).
  44  *
  45  * * can't know about "inaccessible" objects that may be obscuring the
  46  *          accessible windows (inherent to API-based approach).
  47  *
  48  * * text column alignment is crude since it relies on a hard-coded
  49  *          (and arbitrary) ratio of horizontal pixels to character columns.
  50  *          For small proportional fonts, overruns are likely to result in
  51  *          occasional review lines that exceed the standard length.
  52  *
  53  * * (others).
  54  */
  55
  56 #undef CHUNK_LIST_DEBUG /* define to get list of text chunks before clip */
  57
  58 #define BOUNDS_CONTAIN_X_BOUNDS(b, p)  ( ((p).x>=(b).x) &&\
  59                                          (((p).x + (p).width) <= \
  60                                          ((b).x + (b).width)) && \
  61                                         ((b).width > 0) && ((b).height > 0))
  62
  63 #define BOUNDS_CONTAIN_Y(b, p)  (((p)>=(b)->y) && ((p)<=((b)->y + (b)->height))\
  64             && ((b)->width > 0) && ((b)->height > 0))
  65
  66 #define CHUNK_BOUNDS_BEFORE_START(c, i) ((i) && ((c)->clip_bounds.x < \
  67                                          (i)->clip_bounds.x))
  68
  69 #define CHUNK_BOUNDS_END_BEFORE_START(c, i) ((i) && \
  70                                          (((c)->clip_bounds.x + \
  71                                          (c)->clip_bounds.width) < \
  72                                          (i)->clip_bounds.x))
  73
  74 #define CHUNK_BOUNDS_AFTER_END(c, i) ((i) && ((c)->clip_bounds.x >= \
  75                                        ((i)->clip_bounds.x + \
  76                                         (i)->clip_bounds.width)))
  77
  78 #define CHUNK_BOUNDS_SPANS_END(c, i) ((i) && (((c)->clip_bounds.x + \
  79                                               (c)->clip_bounds.width) >= \
  80                                        ((i)->clip_bounds.x + \
  81                                         (i)->clip_bounds.width)))
  82 /*
  83  * #define CHUNK_BOUNDS_WITHIN(c, i)  ((i) && ((c)->clip_bounds.x >= \
  84  *                               (i)->text_bounds.x) && \
  85  *                               (((c)->clip_bounds.x + (c)->clip_bounds.width) \
  86  *                             <= ((i)->text_bounds.x + (i)->text_bounds.width)))
  87  */
  88
  89 #define IS_CLIPPING_CONTAINER(a) ((a) != SPI_ROLE_PAGE_TAB)
  90
  91 static void report_screen_review_line  (const AccessibleEvent *event, void *user_data);
  92
  93 static gint n_elements_traversed = 0;
  94 static AccessibleEventListener *mouseclick_listener;
  95
  96 typedef struct _BoundaryRect {
  97         long int x;
  98         long int y;
  99         long int width;
 100         long int height;
 101         AccessibleRole role; /* role of last clipping element */
 102         gboolean isClipped;
 103         gboolean isEmpty;
 104 } BoundaryRect;
 105
 106 typedef struct _TextChunk {
 107         char           *string;
 108         Accessible     *source;
 109         int             start_offset;
 110         int             end_offset;
 111         BoundaryRect    clip_bounds;
 112         BoundaryRect    text_bounds;
 113         BoundaryRect    start_char_bounds;
 114         BoundaryRect    end_char_bounds;
 115 } TextChunk;
 116
 117 typedef struct _ScreenReviewBuffer {
 118         GList *text_chunks;
 119 } ScreenReviewBuffer;
 120
 121 static gboolean isJava = FALSE;
 122
 123 int
 124 main (int argc, char **argv)
 125 {
 126   int i, j;
 127   int n_desktops;
 128   int n_apps;
 129   char *s;
 130   GTimer *timer;
 131   gdouble elapsed_time;
 132   Accessible *desktop;
 133   Accessible *application;
 134   const char *modules;
 135
 136   SPI_init ();
 137
 138   mouseclick_listener = SPI_createAccessibleEventListener (
 139           report_screen_review_line, NULL);
 140
 141   SPI_registerGlobalEventListener (mouseclick_listener,
 142                                    "Gtk:GtkWidget:button-press-event");
 143 #undef JAVA_TEST_HACK
 144 #ifdef JAVA_TEST_HACK /* Only use this to test Java apps */
 145   SPI_registerGlobalEventListener (mouseclick_listener,
 146                                    "object:text-caret-moved");
 147   isJava = TRUE;
 148 #endif
 149   SPI_event_main ();
 150
 151   putenv ("AT_BRIDGE_SHUTDOWN=1");
 152
 153   /*
 154    * TODO: Add a key event listener that calls test_exit, to
 155    * deregister and cleanup appropriately.
 156    */
 157
 158   return SPI_exit ();
 159 }
 160
 161 static inline gboolean
 162 chunk_bounds_within (TextChunk *chunk, TextChunk *test_chunk)
 163 {
 164         int x1, x2, tx1, tx2;
 165         gboolean gtx1, ltx2;
 166
 167         x1 = chunk->clip_bounds.x;
 168         x2 = x1 + chunk->clip_bounds.width;
 169         tx1 = test_chunk->clip_bounds.x;
 170         tx2 = tx1 + test_chunk->clip_bounds.width;
 171         gtx1 = (chunk->clip_bounds.x >= test_chunk->clip_bounds.x);
 172         ltx2 = (chunk->clip_bounds.x + chunk->clip_bounds.width
 173                 <= test_chunk->clip_bounds.x + test_chunk->clip_bounds.width);
 174         return gtx1 && ltx2;
 175 }
 176
 177 #define CHUNK_BOUNDS_WITHIN(a, b) chunk_bounds_within(a, b)
 178
 179 static BoundaryRect **
 180 clip_bounds_clone (BoundaryRect *bounds[])
 181 {
 182         int i;
 183         BoundaryRect **bounds_clone;
 184         bounds_clone = (BoundaryRect **)
 185                 g_new0 (gpointer, SPI_LAYER_LAST_DEFINED);
 186         for (i = 1; i < SPI_LAYER_LAST_DEFINED; ++i) {
 187                 bounds_clone[i] = g_new0 (BoundaryRect, 1);
 188                 *bounds_clone[i] = *bounds[i];
 189         }
 190         return bounds_clone;
 191 }
 192
 193 static void
 194 boundary_clip (BoundaryRect *bounds, BoundaryRect *clipBounds)
 195 {
 196         int x2 = bounds->x + bounds->width;
 197         int y2 = bounds->y + bounds->height;
 198 #ifdef CLIP_DEBUG
 199         fprintf (stderr, "bclip %d-%d, %d-%d; ",
 200                  bounds->x, x2,
 201                  clipBounds->x, clipBounds->x+clipBounds->width);
 202 #endif
 203         bounds->x = MAX (bounds->x, clipBounds->x);
 204         bounds->y = MAX (bounds->y, clipBounds->y);
 205         x2 =  MIN (x2,  clipBounds->x + clipBounds->width);
 206         y2 =  MIN (y2, clipBounds->y + clipBounds->height);
 207         bounds->width = MAX (x2 - bounds->x, 0);
 208         bounds->height = MAX (y2 - bounds->y, 0);
 209         if (!bounds->width || !bounds->height)
 210                 bounds->isEmpty = TRUE;
 211         if (IS_CLIPPING_CONTAINER (bounds->role)) {
 212                 *clipBounds = *bounds;
 213         }
 214 #ifdef CLIP_DEBUG
 215         fprintf (stderr, "%d-%d\n",
 216                  bounds->x, bounds->x+bounds->width);
 217 #endif
 218 }
 219
 220 static void
 221 boundary_xclip_head (BoundaryRect *bounds, BoundaryRect *clipBounds)
 222 {
 223         int x2;
 224         int cx2 = clipBounds->x + clipBounds->width;
 225         if (cx2 < bounds->x) return;
 226         x2 = bounds->x + bounds->width;
 227         if (cx2 <= x2) bounds->x = cx2;
 228         bounds->width = MAX (0, x2 - cx2);
 229 }
 230
 231 static void
 232 boundary_xclip_tail (BoundaryRect *bounds, BoundaryRect *clipBounds)
 233 {
 234         int x2 = bounds->x + bounds->width;
 235         if (clipBounds->x > x2) return;
 236         bounds->width = MAX (0, clipBounds->x - bounds->x);
 237 }
 238
 239 static TextChunk*
 240 text_chunk_copy (TextChunk *chunk)
 241 {
 242         TextChunk *copy = g_new0 (TextChunk, 1);
 243         *copy = *chunk;
 244         if (chunk->string) copy->string = g_strdup (chunk->string);
 245         if (copy->source) Accessible_ref (copy->source);
 246         return copy;
 247 }
 248
 249 static void
 250 text_chunk_tail_clip (TextChunk *bottom, TextChunk *top)
 251 {
 252 #ifdef CLIP_DEBUG
 253         fprintf (stderr, "bottom %d-%d, top %d-%d;",
 254                  bottom->clip_bounds.x,
 255                  bottom->clip_bounds.x + bottom->clip_bounds.width,
 256                  top->clip_bounds.x,
 257                  top->clip_bounds.x + top->clip_bounds.width);
 258 #endif
 259         boundary_xclip_tail (&bottom->text_bounds, &top->clip_bounds);
 260         boundary_xclip_tail (&bottom->clip_bounds, &top->clip_bounds);
 261         bottom->text_bounds.isClipped = TRUE;
 262         bottom->clip_bounds.isClipped = TRUE;
 263 #ifdef CLIP_DEBUG
 264         fprintf (stderr, "result %d-%d\n",
 265                  bottom->clip_bounds.x,
 266                  bottom->clip_bounds.x + bottom->clip_bounds.width);
 267 #endif
 268 }
 269
 270 static void
 271 text_chunk_head_clip (TextChunk *bottom, TextChunk *top)
 272 {
 273 #ifdef CLIP_DEBUG
 274         fprintf (stderr, "bottom %d-%d, top %d-%d;",
 275                  bottom->clip_bounds.x,
 276                  bottom->clip_bounds.x + bottom->clip_bounds.width,
 277                  top->clip_bounds.x,
 278                  top->clip_bounds.x + top->clip_bounds.width);
 279 #endif
 280         boundary_xclip_head (&bottom->text_bounds, &top->clip_bounds);
 281         boundary_xclip_head (&bottom->clip_bounds, &top->clip_bounds);
 282         bottom->text_bounds.isClipped = TRUE;
 283         bottom->clip_bounds.isClipped = TRUE;
 284 #ifdef CLIP_DEBUG
 285         fprintf (stderr, "result %d-%d\n",
 286                  bottom->clip_bounds.x,
 287                  bottom->clip_bounds.x + bottom->clip_bounds.width);
 288 #endif
 289 }
 290
 291 static GList *
 292 text_chunk_split_insert (GList *chunk_list, GList *iter, TextChunk *chunk)
 293 {
 294         TextChunk *iter_chunk = iter->data;
 295         TextChunk *iter_copy = text_chunk_copy (iter_chunk);
 296         /* TODO: FIXME something is wrong here */
 297 #ifdef CLIP_DEBUG
 298         fprintf (stderr, "***clip insert of %s into %s\n",
 299                  chunk->string ? chunk->string : "<null>",
 300                  iter_chunk->string ? iter_chunk->string : "<null>");
 301 #endif
 302         chunk_list = g_list_insert_before (chunk_list, iter, iter_copy);
 303         text_chunk_tail_clip (iter_copy, chunk);
 304         chunk_list = g_list_insert_before (chunk_list, iter, chunk);
 305         text_chunk_head_clip (iter_chunk, chunk);
 306         return chunk_list;
 307 }
 308
 309 /* #define PRINT_CHUNK_DEBUG(a, b, c, d) print_chunk_debug(a, b, c, d) */
 310
 311 #define PRINT_CHUNK_DEBUG(a, b, c, d)
 312
 313 #ifdef PRINT_CHUNK_DEBUG
 314 static void
 315 print_chunk_debug (TextChunk *chunk, char *opname, GList *prev, GList *next)
 316 {
 317         fprintf (stderr, "%sing chunk %s between %s and %s; %d-%d\n",
 318                  opname,
 319                  chunk->string,
 320                  (prev ? ((TextChunk *) prev->data)->string : "<null>"),
 321                  (next ? ((TextChunk *) next->data)->string : "<null>"),
 322                  chunk->clip_bounds.x,
 323                  chunk->text_bounds.x + chunk->text_bounds.width);
 324 }
 325 #endif
 326
 327 static GList *
 328 text_chunk_list_head_clip (GList *text_chunk_list,
 329                            TextChunk *chunk,
 330                            GList *next)
 331 {
 332         GList *target, *iter = next, *prev;
 333         prev = iter->prev;
 334 /*      if (chunk->string && strlen (chunk->string)) { */
 335                 text_chunk_list =
 336                         g_list_insert_before (text_chunk_list, next, chunk);
 337 /*      }*/
 338         while (iter && CHUNK_BOUNDS_SPANS_END (chunk, (TextChunk *)iter->data)) {
 339 #ifdef CLIP_DEBUG
 340                         fprintf (stderr, "deleting %s\n",
 341                                  ((TextChunk *)iter->data)->string);
 342 #endif
 343                         target = iter;
 344                         iter = iter->next;
 345                         text_chunk_list =
 346                                 g_list_delete_link (text_chunk_list, target);
 347         }
 348         if (iter && !CHUNK_BOUNDS_END_BEFORE_START (chunk,
 349                                                     (TextChunk *)iter->data)) {
 350                 text_chunk_head_clip ((TextChunk *)iter->data,
 351                                       chunk);
 352         }
 353         if (prev &&
 354             !CHUNK_BOUNDS_AFTER_END (
 355                     chunk,
 356                     (TextChunk *)prev->data)) {
 357                 text_chunk_tail_clip (
 358                         (TextChunk *)prev->data,
 359                         chunk);
 360         }
 361
 362         return text_chunk_list;
 363 }
 364
 365 static GList *
 366 text_chunk_list_clip_and_insert (GList *text_chunk_list,
 367                                  TextChunk *chunk,
 368                                  GList *prev,
 369                                  GList *next)
 370 {
 371 #ifdef CLIP_DEBUG
 372 /*      if (chunk->string) */
 373                 fprintf (stderr, "clip-and-insert for %s, between %s (%d) and %s (%d)\n",
 374                          chunk->string,
 375                          (prev && ((TextChunk *)prev->data)->string ? ((TextChunk *)prev->data)->string : "<null>"),
 376                          (prev ? ((TextChunk *)prev->data)->text_bounds.x : -1),
 377                          (next && ((TextChunk *)next->data)->string ? ((TextChunk *)next->data)->string : "<null>"),
 378                          (next ? ((TextChunk *)next->data)->text_bounds.x : -1));
 379 #endif
 380         /* cases: */
 381         if (!prev && !next) { /* first element in, no clip needed */
 382                 text_chunk_list =
 383                         g_list_append (text_chunk_list, chunk);
 384                 PRINT_CHUNK_DEBUG (chunk, "append",
 385                                    prev,
 386                                    NULL);
 387         } else { /* check for clip with prev */
 388                 /* if we split the prev */
 389                 if (prev &&
 390                     CHUNK_BOUNDS_WITHIN (chunk, (TextChunk *) prev->data)) {
 391                         text_chunk_list =
 392                                 text_chunk_split_insert (
 393                                         text_chunk_list,
 394                                         prev, chunk);
 395                 } else if (next) {
 396                     /* we split the 'next' element */
 397                     if (CHUNK_BOUNDS_WITHIN (chunk, (TextChunk *)next->data)) {
 398                             text_chunk_list =
 399                                     text_chunk_split_insert (text_chunk_list,
 400                                                              next, chunk);
 401                     } else {
 402                             /* do an insert +  head clip */
 403                             text_chunk_list =
 404                                     text_chunk_list_head_clip (
 405                                             text_chunk_list,
 406                                             chunk,
 407                                             next);
 408                     }
 409                 } else {
 410                         if (!CHUNK_BOUNDS_AFTER_END (chunk,
 411                                                      (TextChunk *) prev->data)) {
 412                                 text_chunk_tail_clip (prev->data, chunk);
 413                         }
 414                         text_chunk_list =
 415                                 g_list_append (text_chunk_list, chunk);
 416                 }
 417         }
 418         return text_chunk_list;
 419 }
 420
 421 static GList *
 422 text_chunk_list_insert_chunk (GList *text_chunk_list, TextChunk *chunk)
 423 {
 424         GList *iter = g_list_first (text_chunk_list);
 425         TextChunk *iter_chunk = NULL;
 426         do {
 427                 if (iter) iter_chunk = (TextChunk *) iter->data;
 428                 /* if we're ahead of the current element */
 429                 if (!iter) {
 430                         text_chunk_list =
 431                                 text_chunk_list_clip_and_insert (text_chunk_list,
 432                                                                  chunk,
 433                                                                  iter,
 434                                                                  NULL);
 435                         break;
 436                 } else if (CHUNK_BOUNDS_BEFORE_START (chunk, iter_chunk)) {
 437                         text_chunk_list =
 438                                 text_chunk_list_clip_and_insert (text_chunk_list,
 439                                                                  chunk,
 440                                                                  iter->prev,
 441                                                                  iter);
 442                         break;
 443                 } else if (!iter->next ) {
 444                         text_chunk_list =
 445                                 text_chunk_list_clip_and_insert (text_chunk_list,
 446                                                                  chunk,
 447                                                                  iter,
 448                                                                  NULL);
 449                         break;
 450                 }
 451                 if (iter) iter = iter->next;
 452         } while (iter);
 453         return text_chunk_list;
 454 }
 455
 456 static TextChunk *
 457 review_buffer_get_text_chunk (ScreenReviewBuffer *reviewBuffer,
 458                               Accessible *accessible, BoundaryRect *bounds,
 459                               int screen_x, int screen_y)
 460 {
 461         AccessibleText *text = NULL;
 462         AccessibleRole role;
 463         TextChunk *text_chunk;
 464         BoundaryRect start_char_bounds, end_char_bounds;
 465         char *s = NULL;
 466         int offset;
 467         long start, end;
 468         long x2, y2;
 469
 470         role = Accessible_getRole (accessible);
 471         text_chunk = g_new0 (TextChunk, 1);
 472         text_chunk->clip_bounds = *bounds;
 473         text_chunk->source = accessible;
 474         Accessible_ref (accessible);
 475         if (Accessible_isText (accessible)) {
 476                 text = Accessible_getText (accessible);
 477                 offset = AccessibleText_getOffsetAtPoint (text,
 478                                                           screen_x,
 479                                                           screen_y,
 480                                                           SPI_COORD_TYPE_SCREEN);
 481                 s = AccessibleText_getTextAtOffset (text, offset,
 482                                                     SPI_TEXT_BOUNDARY_LINE_START,
 483                                                     &start, &end);
 484                 if (end > start) {
 485                         AccessibleText_getCharacterExtents (
 486                                 text, start,
 487                                 &text_chunk->start_char_bounds.x,
 488                                 &text_chunk->start_char_bounds.y,
 489                                 &text_chunk->start_char_bounds.width,
 490                                 &text_chunk->start_char_bounds.height,
 491                                 SPI_COORD_TYPE_SCREEN);
 492 #ifdef CLIP_DEBUG
 493                         fprintf (stderr, "%s: start char (%d) x, width %d %d; ",
 494                                  s,
 495                                  start,
 496                                  text_chunk->start_char_bounds.x,
 497                                  text_chunk->start_char_bounds.width);
 498 #endif
 499                         if (s && strlen (s) && s[strlen (s) - 1] == '\n')
 500                                 end--;
 501                         AccessibleText_getCharacterExtents (
 502                                 text, end - 1,
 503                                 &text_chunk->end_char_bounds.x,
 504                                 &text_chunk->end_char_bounds.y,
 505                                 &text_chunk->end_char_bounds.width,
 506                                 &text_chunk->end_char_bounds.height,
 507                                 SPI_COORD_TYPE_SCREEN);
 508 #ifdef CLIP_DEBUG
 509                         fprintf (stderr, "end char (%d) x, width %d %d\n",
 510                                  end - 1,
 511                                  text_chunk->end_char_bounds.x,
 512                                  text_chunk->end_char_bounds.width);
 513 #endif
 514                 }
 515                 text_chunk->text_bounds.x = MIN (text_chunk->start_char_bounds.x,
 516                                                  text_chunk->end_char_bounds.x);
 517                 text_chunk->text_bounds.y = MIN (text_chunk->start_char_bounds.y,
 518                                                  text_chunk->end_char_bounds.y);
 519                 x2 = MAX (text_chunk->start_char_bounds.x +
 520                           text_chunk->start_char_bounds.width,
 521                           text_chunk->end_char_bounds.x +
 522                           text_chunk->end_char_bounds.width);
 523                 text_chunk->text_bounds.width = x2 - text_chunk->text_bounds.x;
 524                 y2 = MAX (text_chunk->start_char_bounds.y +
 525                           text_chunk->start_char_bounds.height,
 526                           text_chunk->end_char_bounds.y +
 527                           text_chunk->end_char_bounds.height);
 528                 text_chunk->text_bounds.height = y2 - text_chunk->text_bounds.y;
 529                 text_chunk->start_offset = start;
 530                 text_chunk->end_offset = end;
 531                 AccessibleText_unref (text);
 532         } else {
 533                 if (role == SPI_ROLE_PUSH_BUTTON ||
 534                     role == SPI_ROLE_CHECK_BOX ||
 535                     role == SPI_ROLE_LABEL ||
 536                     role == SPI_ROLE_MENU ||
 537                     role == SPI_ROLE_MENU_ITEM) { /* don't like this
 538                                                      special casing :-( */
 539                         s = Accessible_getName (accessible);
 540                         /* use name instead */
 541                         text_chunk->text_bounds = text_chunk->clip_bounds;
 542                         text_chunk->start_offset = 0;
 543                         text_chunk->end_offset = strlen (s);
 544                 }
 545         }
 546         if (text_chunk->text_bounds.x < text_chunk->clip_bounds.x) {
 547                 text_chunk->text_bounds.x = text_chunk->clip_bounds.x;
 548                 text_chunk->text_bounds.isClipped = TRUE;
 549         }
 550         if ((text_chunk->text_bounds.x +
 551              text_chunk->text_bounds.width)
 552             > (text_chunk->clip_bounds.x +
 553                text_chunk->clip_bounds.width)) {
 554                 text_chunk->text_bounds.width =
 555                         MAX (0, (text_chunk->clip_bounds.x +
 556                                  text_chunk->clip_bounds.width) -
 557                              text_chunk->text_bounds.x);
 558                 text_chunk->text_bounds.isClipped = TRUE;
 559         }
 560         if (!BOUNDS_CONTAIN_Y (&text_chunk->text_bounds,
 561                                screen_y)) {
 562 #ifdef CLIP_DEBUG
 563                 fprintf (stderr, "%s out of bounds (%d-%d)\n", s,
 564                          text_chunk->text_bounds.y,
 565                          text_chunk->text_bounds.y +
 566                          text_chunk->text_bounds.height);
 567 #endif
 568                 s = NULL;
 569                 text_chunk->start_offset = offset;
 570                 text_chunk->end_offset = offset;
 571         }
 572         if (s && strlen (s)) {
 573                 if (s[strlen(s)-1] == '\n') s[strlen(s)-1] = ' ';
 574                 /* XXX: if last char is newline, aren't its bounds wrong now? */
 575                 text_chunk->string = s;
 576 #ifdef CLIP_DEBUG
 577                 fprintf (stderr, "%s, bounds %d-%d; clip %d-%d\n",
 578                          s,
 579                          text_chunk->text_bounds.x,
 580                          text_chunk->text_bounds.x+text_chunk->text_bounds.width,
 581                          text_chunk->clip_bounds.x,
 582                          text_chunk->clip_bounds.x+text_chunk->clip_bounds.width);
 583 #endif
 584         } else {
 585                 text_chunk->string = NULL;
 586         }
 587         return text_chunk;
 588 }
 589
 590 static void
 591 debug_chunk_list (GList *iter)
 592 {
 593         TextChunk *chunk;
 594         while (iter) {
 595                 chunk = (TextChunk *)iter->data;
 596                 fprintf (stderr, "Chunk %s, clip %d-%d, text %d-%d\n",
 597                          chunk->string,
 598                          chunk->clip_bounds.x,
 599                          chunk->clip_bounds.x + chunk->clip_bounds.width,
 600                          chunk->text_bounds.x,
 601                          chunk->text_bounds.x + chunk->text_bounds.width);
 602                 iter = iter->next;
 603         }
 604 }
 605
 606 static void
 607 clip_into_buffers (Accessible *accessible,  BoundaryRect* parentClipBounds[],
 608                    ScreenReviewBuffer *reviewBuffers[],
 609                    int screen_x, int screen_y)
 610 {
 611         int n_children, child_n;
 612         Accessible *child;
 613         BoundaryRect bounds;
 614         BoundaryRect** clip_bounds;
 615         TextChunk *text_chunk;
 616         AccessibleComponent *component;
 617         AccessibleRole role;
 618         int layer;
 619
 620         clip_bounds = clip_bounds_clone (parentClipBounds);
 621         if (Accessible_isComponent (accessible)) {
 622                 role = Accessible_getRole (accessible);
 623                 component = Accessible_getComponent (accessible);
 624                 layer = AccessibleComponent_getLayer (component);
 625                 bounds = *clip_bounds[layer];
 626                 if (!bounds.isEmpty) {
 627                         AccessibleComponent_getExtents (component,
 628                                                         &bounds.x,
 629                                                         &bounds.y,
 630                                                         &bounds.width,
 631                                                         &bounds.height,
 632                                                         SPI_COORD_TYPE_SCREEN);
 633                         bounds.role = role;
 634                         if (clip_bounds[layer])
 635                                 boundary_clip (&bounds, clip_bounds[layer]);
 636                         if (BOUNDS_CONTAIN_Y (&bounds, screen_y)) {
 637                                 text_chunk = review_buffer_get_text_chunk (
 638                                         reviewBuffers[layer], accessible, &bounds,
 639                                         screen_x, screen_y);
 640                                 reviewBuffers[layer]->text_chunks =
 641                                         text_chunk_list_insert_chunk (
 642                                                 reviewBuffers[layer]->text_chunks,
 643                                                 text_chunk);
 644                         } else {
 645                                 bounds.isEmpty =
 646                                         IS_CLIPPING_CONTAINER (bounds.role);
 647                         }
 648                 }
 649                 Accessible_unref (component);
 650         }
 651         /*
 652          * we always descend into children in case they are in a higher layer
 653          * this can of course be optimized for the topmost layer...
 654          * but nobody uses that one! (SPI_LAYER_OVERLAY)
 655          */
 656         n_children = Accessible_getChildCount (accessible);
 657         for (child_n = 0; child_n < n_children; ++child_n) {
 658                 child = Accessible_getChildAtIndex (accessible, child_n);
 659                 clip_into_buffers (child, clip_bounds, reviewBuffers, screen_x, screen_y);
 660                 Accessible_unref (child);
 661         }
 662         /* TODO: free the parent clip bounds */
 663 }
 664
 665 #undef CHARACTER_CLIP_DEBUG
 666
 667 static char*
 668 text_chunk_get_clipped_substring_by_char (TextChunk *chunk, int start, int end)
 669 {
 670         BoundaryRect char_bounds;
 671         int i;
 672         char *s;
 673         GString *string = g_string_new ("");
 674         gunichar c;
 675         AccessibleText *text = Accessible_getText (chunk->source);
 676         for (i = start; i < end; ++i) {
 677                 AccessibleText_getCharacterExtents (text,
 678                                                     i,
 679                                                     &char_bounds.x,
 680                                                     &char_bounds.y,
 681                                                     &char_bounds.width,
 682                                                     &char_bounds.height,
 683                                                     SPI_COORD_TYPE_SCREEN);
 684 #ifdef CHARACTER_CLIP_DEBUG
 685                 fprintf (stderr, "testing %d-%d against %d-%d\n",
 686                          char_bounds.x, char_bounds.x+char_bounds.width,
 687                          chunk->text_bounds.x,
 688                          chunk->text_bounds.x + chunk->text_bounds.width);
 689 #endif
 690                 if (BOUNDS_CONTAIN_X_BOUNDS (chunk->text_bounds,
 691                                              char_bounds)) {
 692                         c = AccessibleText_getCharacterAtOffset (
 693                                 text, i);
 694 #ifdef CLIP_DEBUG
 695                         fprintf (stderr, "[%c]", c);
 696 #endif
 697                         g_string_append_unichar (string, c);
 698                 }
 699         }
 700         AccessibleText_unref (text);
 701         s = string->str;
 702         g_string_free (string, FALSE);
 703         return s;
 704 }
 705
 706
 707 /*
 708  * Note: this routine shouldn't have to do as much as it currently does,
 709  *       but at the moment it works around another bug (probably one in this
 710  *       code).
 711  */
 712 static char *
 713 string_strip_newlines (char *s, long offset, long *start_offset, long *end_offset)
 714 {
 715         int i;
 716         char *word_start = s;
 717         /* FIXME: potential memory leak here */
 718         for (i=0; s && s[i]; ++i)
 719         {
 720                 if (s [i] == '\n' && i > (offset - *start_offset) ) {
 721                         s [i] = '\0';
 722                         *end_offset = *start_offset + i;
 723                         return word_start;
 724                 } else if (s [i] == '\n') {
 725                         word_start = &s[i + 1];
 726                 }
 727         }
 728         return word_start;
 729 }
 730
 731 static char *
 732 string_guess_clip (TextChunk *chunk)
 733 {
 734         BoundaryRect b;
 735         char *s = NULL, *sp = chunk->string, *ep;
 736         long start_offset, end_offset, len;
 737         if (sp) {
 738                 AccessibleComponent *component =
 739                         Accessible_getComponent (chunk->source);
 740                 ep = sp + (strlen (sp));
 741                 len = g_utf8_strlen (chunk->string, -1);
 742                 if (component) {
 743                         AccessibleComponent_getExtents (component,
 744                                                         &b.x, &b.y,
 745                                                         &b.width, &b.height,
 746                                                         SPI_COORD_TYPE_SCREEN);
 747                         start_offset = len * (chunk->text_bounds.x - b.x) / b.width;
 748                         end_offset = len * (chunk->text_bounds.x +
 749                                             chunk->text_bounds.width - b.x) / b.width;
 750                         fprintf (stderr, "String len %d, clipped to %d-%d\n",
 751                                  len, start_offset, end_offset);
 752                         len = end_offset - start_offset;
 753                         sp = g_utf8_offset_to_pointer (chunk->string, start_offset);
 754                         ep = g_utf8_offset_to_pointer (chunk->string, end_offset);
 755                 }
 756                 s = g_new0 (char, ep - sp + 1);
 757                 s = g_utf8_strncpy (s, sp, len);
 758                 s [sp - ep] = '\0';
 759                 g_assert (g_utf8_validate (s, -1, NULL));
 760         }
 761         return s;
 762 }
 763
 764 static char*
 765 text_chunk_get_clipped_string (TextChunk *chunk)
 766 {
 767         char *s, *string = "";
 768         int i;
 769         long start = chunk->start_offset, end = chunk->end_offset;
 770         long word_start, word_end, range_end;
 771         BoundaryRect start_bounds, end_bounds;
 772         gboolean start_inside, end_inside;
 773         if (!chunk->text_bounds.isClipped || !chunk->string)
 774                 string = chunk->string;
 775         else if (chunk->source && Accessible_isText (chunk->source)) {
 776                 /* while words at offset lie within the bounds, add them */
 777                 AccessibleText *text = Accessible_getText (chunk->source);
 778 #ifdef CLIP_DEBUG
 779                 fprintf (stderr, "clipping %s\n", chunk->string);
 780 #endif
 781                 do {
 782                     s = AccessibleText_getTextAtOffset (text,
 783                                                         start,
 784                                                 SPI_TEXT_BOUNDARY_WORD_END,
 785                                                         &word_start,
 786                                                         &word_end);
 787                     range_end = word_end;
 788                     s = string_strip_newlines (s, start, &word_start, &word_end);
 789                     AccessibleText_getCharacterExtents (text,
 790                                                         word_start,
 791                                                         &start_bounds.x,
 792                                                         &start_bounds.y,
 793                                                         &start_bounds.width,
 794                                                         &start_bounds.height,
 795                                                         SPI_COORD_TYPE_SCREEN);
 796                     AccessibleText_getCharacterExtents (text,
 797                                                         word_end - 1,
 798                                                         &end_bounds.x,
 799                                                         &end_bounds.y,
 800                                                         &end_bounds.width,
 801                                                         &end_bounds.height,
 802                                                         SPI_COORD_TYPE_SCREEN);
 803                     start_inside = BOUNDS_CONTAIN_X_BOUNDS (chunk->text_bounds,
 804                                                             start_bounds);
 805                     end_inside = BOUNDS_CONTAIN_X_BOUNDS (chunk->text_bounds,
 806                                                           end_bounds);
 807                     if (start_inside && end_inside) {
 808                             /* word is contained in bounds */
 809                             string = g_strconcat (string, s, NULL);
 810                     } else if (start_inside || end_inside) {
 811                             /* one end of word is in */
 812                             if (word_end > end) word_end = end;
 813                             s = text_chunk_get_clipped_substring_by_char (
 814                                     chunk,
 815                                     MAX (word_start, chunk->start_offset),
 816                                     MIN (word_end, chunk->end_offset));
 817                             string = g_strconcat (string, s, NULL);
 818                     } else {
 819                     }
 820                     start = range_end;
 821                 } while (start < chunk->end_offset);
 822         } else { /* we're clipped, but don't implement AccessibleText :-( */
 823                 /* guess for now, maybe we can do better someday */
 824                 string = string_guess_clip (chunk);
 825         }
 826         return string;
 827 }
 828
 829
 830 static char*
 831 text_chunk_pad_string (TextChunk *chunk, char *string, glong offset, const char *pad_chars)
 832 {
 833         char *s = "";
 834         char *cp;
 835         char startbuf[6], padbuf[6], endbuf[6];
 836         int pixels_per_column = 6;
 837         /* this is an arbitrary pixel-to-textcolumn mapping at present */
 838         glong end_padding;
 839         gint howmany;
 840         howmany = g_unichar_to_utf8 (g_utf8_get_char (pad_chars), startbuf);
 841         startbuf[howmany] = '\0';
 842         g_assert (howmany < 7 && howmany > 0);
 843         cp = g_utf8_find_next_char (pad_chars, NULL);
 844         howmany = g_unichar_to_utf8 (g_utf8_get_char (cp), padbuf);
 845         padbuf[howmany] = '\0';
 846         g_assert (howmany < 7 && howmany > 0);
 847         cp = g_utf8_find_next_char (cp, NULL);
 848         howmany = g_unichar_to_utf8 (g_utf8_get_char (cp), endbuf);
 849         endbuf[howmany] = '\0';
 850         g_assert (howmany < 7 && howmany > 0);
 851         end_padding = chunk->clip_bounds.x / pixels_per_column;
 852         while (offset < end_padding - 1) {
 853                 s = g_strconcat (s, padbuf, NULL); /* could be more efficient */
 854                 ++offset;
 855         }
 856         s = g_strconcat (s, startbuf, string, NULL);
 857         offset += g_utf8_strlen (string, -1) + 1;
 858         end_padding = chunk->text_bounds.x / pixels_per_column;
 859         while (offset < end_padding) {
 860                 s = g_strconcat (s, padbuf, NULL); /* could be more efficient */
 861                 ++offset;
 862         }
 863         end_padding = (chunk->clip_bounds.x + chunk->clip_bounds.width) /
 864                 pixels_per_column;
 865         while (offset < end_padding - 1) {
 866                 s = g_strconcat (s, padbuf, NULL); /* could be more efficient */
 867                 ++offset;
 868         }
 869         s = g_strconcat (s, endbuf, NULL);
 870         return s;
 871 }
 872
 873 static char*
 874 text_chunk_to_string (TextChunk *chunk, glong offset)
 875 {
 876         char *s = NULL;
 877         if (chunk->string) {
 878                 s = text_chunk_get_clipped_string (chunk);
 879                 if (chunk->clip_bounds.role == SPI_ROLE_PUSH_BUTTON) {
 880                         s = text_chunk_pad_string (chunk, s, offset, "[ ]");
 881                 } else if (chunk->clip_bounds.role == SPI_ROLE_FRAME) {
 882                         s = text_chunk_pad_string (chunk, s, offset, "| |");
 883                 } else if (chunk->clip_bounds.role == SPI_ROLE_TEXT) {
 884                         s = text_chunk_pad_string (chunk, s, offset, "\" \"");
 885                 } else {
 886                         s = text_chunk_pad_string (chunk, s, offset, "   ");
 887                 }
 888         }
 889         return s;
 890 }
 891
 892 static char*
 893 text_chunk_list_to_string (GList *iter)
 894 {
 895         char *s = "";
 896         char *string;
 897         TextChunk *chunk = NULL;
 898         int offset = 0;
 899         while (iter) {
 900                 chunk = (TextChunk *)iter->data;
 901                 if (chunk) {
 902                         string = text_chunk_to_string (chunk, g_utf8_strlen (s, -1));
 903                         if (string)
 904                                 s = g_strconcat (s, string, NULL);
 905                 }
 906                 iter = iter->next;
 907         }
 908         s = g_strconcat (s, "|", NULL);
 909         return s;
 910 }
 911
 912 #define COMPOSITE_DEBUG
 913
 914 static void
 915 toplevel_composite (ScreenReviewBuffer *buffers[])
 916 {
 917         int i;
 918         GList *chunk_list, *iter;
 919         TextChunk *chunk;
 920
 921         chunk_list = buffers[SPI_LAYER_CANVAS]->text_chunks;
 922         for (i = SPI_LAYER_MDI; i < SPI_LAYER_OVERLAY; ++i) {
 923                 iter = buffers[i]->text_chunks;
 924 #ifdef COMPOSITE_DEBUG
 925                 fprintf (stderr, "layer %d has %d chunks\n",
 926                          i, g_list_length (iter));
 927 #endif
 928                 while (iter) {
 929                         chunk = (TextChunk *) iter->data;
 930                         if (chunk) {
 931 #ifdef COMPOSITE_DEBUG
 932                                 fprintf (stderr, "inserting chunk <%s>\n",
 933                                          chunk->string ? chunk->string : "<null>");
 934 #endif
 935                                 chunk_list =
 936                                         text_chunk_list_insert_chunk (chunk_list,
 937                                                                       chunk);
 938                         }
 939                         iter = iter->next;
 940                 }
 941         }
 942 }
 943
 944 static char*
 945 review_buffer_composite (ScreenReviewBuffer *buffers[])
 946 {
 947         /* TODO: FIXME: something is wrong here, compositing fails */
 948         int i;
 949         GList *chunk_list, *iter;
 950         TextChunk *chunk;
 951         chunk_list = buffers[SPI_LAYER_BACKGROUND]->text_chunks;
 952         for (i = 2; i < SPI_LAYER_LAST_DEFINED; ++i) {
 953                 if (i == SPI_LAYER_WIDGET) i = SPI_LAYER_OVERLAY;
 954                 /*
 955                  * Q: why skip these layers ?
 956                  * A: since layers WIDGET, MDI, and POPUP have already been
 957                  *  composited into layer CANVAS for each toplevel before this
 958                  *  routine is called.
 959                  */
 960                 iter = buffers[i]->text_chunks;
 961 #ifdef CLIP_DEBUG
 962                 fprintf (stderr, "layer %d has %d chunks\n",
 963                          i, g_list_length (iter));
 964 #endif
 965                 while (iter) {
 966                         chunk = (TextChunk *) iter->data;
 967                         if (chunk) {
 968 #ifdef CLIP_DEBUG
 969                                 fprintf (stderr, "inserting chunk <%s>\n",
 970                                          chunk->string ? chunk->string : "<null>");
 971 #endif
 972                                 chunk_list =
 973                                         text_chunk_list_insert_chunk (chunk_list,
 974                                                                       chunk);
 975                         }
 976                         iter = iter->next;
 977                 }
 978         }
 979
 980         chunk_list = buffers[SPI_LAYER_WIDGET]->text_chunks;
 981         return text_chunk_list_to_string (chunk_list);
 982 }
 983
 984 static char *
 985 get_screen_review_line_at (int x, int y)
 986 {
 987   char *string;
 988   Accessible *desktop, *app, *toplevel, *child;
 989   AccessibleComponent *component;
 990   AccessibleStateSet *states;
 991   GList *toplevels = NULL, *actives = NULL, *iter;
 992   ScreenReviewBuffer* reviewBuffers[SPI_LAYER_LAST_DEFINED];
 993   BoundaryRect* clip_bounds[SPI_LAYER_LAST_DEFINED];
 994   BoundaryRect toplevel_bounds;
 995   int n_apps, n_toplevels, n_children, app_n, toplevel_n, child_n;
 996   GTimer *timer = g_timer_new ();
 997   int i;
 998
 999   for (i = 1; i < SPI_LAYER_LAST_DEFINED; ++i) {
1000           reviewBuffers[i] = g_new0 (ScreenReviewBuffer, 1);
1001           clip_bounds[i] = g_new0 (BoundaryRect, 1);
1002           clip_bounds[i]->isClipped = FALSE;
1003           clip_bounds[i]->isEmpty = FALSE;
1004   }
1005
1006   /* how do we decide which desktop ? */
1007   desktop = SPI_getDesktop (0);
1008
1009   /* for each app */
1010   n_apps = Accessible_getChildCount (desktop);
1011   for (app_n = 0; app_n < n_apps; ++app_n) {
1012           /* for each toplevel in app */
1013           app =  Accessible_getChildAtIndex (desktop, app_n);
1014           n_toplevels = Accessible_getChildCount (app);
1015           for (toplevel_n = 0; toplevel_n < n_toplevels; ++toplevel_n) {
1016                   Accessible *toplevel = Accessible_getChildAtIndex (app, toplevel_n);
1017                   if (Accessible_isComponent (toplevel))
1018                           toplevels = g_list_prepend (toplevels, toplevel);
1019                   else {
1020                           Accessible_unref (toplevel);
1021                           fprintf (stderr, "warning, app toplevel not a component.\n");
1022                   }
1023           }
1024   }
1025
1026   /* sort: at the moment we don't have a good way to sort except to put actives on top */
1027   for (iter = g_list_first (toplevels); iter; iter = iter->next) {
1028           Accessible *toplevel =
1029                   (Accessible *) iter->data;
1030           if (AccessibleStateSet_contains (Accessible_getStateSet (toplevel),
1031                                            SPI_STATE_ACTIVE)) {
1032                   actives = g_list_prepend (actives, toplevel);
1033           }
1034   }
1035
1036   for (iter = g_list_first (actives); iter; iter = actives->next) {
1037           toplevels = g_list_remove (toplevels, iter->data); /* place at end */
1038           toplevels = g_list_append (toplevels, iter->data);
1039   }
1040   g_list_free (actives);
1041
1042   /* for each toplevel, ending with the active one(s),
1043    * clip against children, putting results into appropriate charBuffer.
1044    */
1045   for (iter = g_list_first (toplevels); iter; iter = iter->next) {
1046           toplevel = (Accessible *) iter->data;
1047           if (Accessible_isComponent (toplevel)) {
1048               /* make sure toplevel is visible and not iconified or shaded */
1049               states = Accessible_getStateSet (toplevel);
1050               if (AccessibleStateSet_contains (states, SPI_STATE_VISIBLE)
1051                   && !AccessibleStateSet_contains (states, SPI_STATE_ICONIFIED)
1052                   || isJava) { /* isJava hack! */
1053                       component = Accessible_getComponent (toplevel);
1054                       AccessibleComponent_getExtents (component,
1055                                                       &toplevel_bounds.x,
1056                                                       &toplevel_bounds.y,
1057                                                       &toplevel_bounds.width,
1058                                                       &toplevel_bounds.height,
1059                                                       SPI_COORD_TYPE_SCREEN);
1060                       toplevel_bounds.isEmpty = FALSE;
1061                       for (i = 1; i < SPI_LAYER_LAST_DEFINED; ++i) {
1062                               *clip_bounds[i] = toplevel_bounds;
1063                       }
1064                       clip_into_buffers (toplevel, clip_bounds,
1065                                      reviewBuffers, x, y);
1066
1067                       toplevel_composite (reviewBuffers);
1068 #ifdef CHUNK_LIST_DEBUG
1069                       fprintf (stderr, "toplevel clip done\n");
1070                       debug_chunk_list (reviewBuffers[SPI_LAYER_WIDGET]->text_chunks);
1071 #endif
1072               }
1073           }
1074           Accessible_unref (toplevel);
1075   }
1076
1077   string = review_buffer_composite (reviewBuffers);
1078
1079   /* SIMPLE SINGLE-PASS ALGORITHM:*/
1080   /* traverse the tree:
1081    *   keep a pointer to outermost instance of each layer
1082    *   clip against outermost in same layer
1083    *   when this clip occurs, store outermost clipped string in 2d string buffer.
1084    *   string buffer may have attributes to mark component bounds, line art,
1085    *      or attributes of text being reviewed.
1086    *   composite the layers, ignoring NULL chars in the string buffers.
1087    *
1088    * Limitations:
1089    *   sibling clip not correct, text may overwrite if siblings intersect onscreen
1090    *   length of resulting text buffer may vary!
1091    *
1092    * Technical issues:
1093    *   no API for ordering toplevels yet, other than knowing which is ACTIVE.
1094    *   not much implementation for the LAYER API yet, other than menus.
1095    */
1096   g_timer_stop (timer);
1097   fprintf (stderr, "elapsed time = %f s\n", g_timer_elapsed (timer, NULL));
1098
1099   return string;
1100 }
1101
1102 void
1103 report_screen_review_line (const AccessibleEvent *event, void *user_data)
1104 {
1105   static Display *display = NULL;
1106   int x, y, win_x, win_y;
1107   Window root_return, child_return;
1108   unsigned int mask_return;
1109
1110   if (!display) display = XOpenDisplay (getenv ("DISPLAY"));
1111   /*
1112    *  we would prefer to get the x,y info in the above event.
1113    *  At the moment we don't get detail params for "toolkit" events,
1114    *  so for testing purposes we use XQueryPointer.  Actual apps
1115    *  probably shouldn't do this.
1116    */
1117   XQueryPointer (display,
1118                  DefaultRootWindow (display),
1119                  &root_return, &child_return,
1120                  &x, &y,
1121                  &win_x, &win_y,
1122                  &mask_return);
1123
1124   fprintf (stderr, "screen review event %s at %d, %d\n", event->type,
1125            x, y);
1126   fprintf (stderr, "[%s]\n",
1127            get_screen_review_line_at (x, y));
1128 }
1129
1130 void
1131 test_exit ()
1132 {
1133   SPI_deregisterGlobalEventListenerAll (mouseclick_listener);
1134   AccessibleEventListener_unref (mouseclick_listener);
1135 }