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