src/layout.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
   2 /*
   3  * layout.cpp:
   4  *
   5  * Contact:
   6  *   Moonlight List (moonlight-list@lists.ximian.com)
   7  *
   8  * Copyright 2008 Novell, Inc. (http://www.novell.com)
   9  *
  10  * See the LICENSE file included with the distribution for details.
  11  */
  12
  13 #include <config.h>
  14
  15 #include <ctype.h>
  16 #include <math.h>
  17
  18 #include "moon-path.h"
  19 #include "layout.h"
  20 #include "debug.h"
  21
  22
  23 #if DEBUG
  24 #define d(x) if (debug_flags & RUNTIME_DEBUG_LAYOUT) x
  25 #else
  26 #define d(x)
  27 #endif
  28
  29 #if DEBUG
  30 static const char *unicode_break_types[] = {
  31         "G_UNICODE_BREAK_MANDATORY",
  32         "G_UNICODE_BREAK_CARRIAGE_RETURN",
  33         "G_UNICODE_BREAK_LINE_FEED",
  34         "G_UNICODE_BREAK_COMBINING_MARK",
  35         "G_UNICODE_BREAK_SURROGATE",
  36         "G_UNICODE_BREAK_ZERO_WIDTH_SPACE",
  37         "G_UNICODE_BREAK_INSEPARABLE",
  38         "G_UNICODE_BREAK_NON_BREAKING_GLUE",
  39         "G_UNICODE_BREAK_CONTINGENT",
  40         "G_UNICODE_BREAK_SPACE",
  41         "G_UNICODE_BREAK_AFTER",
  42         "G_UNICODE_BREAK_BEFORE",
  43         "G_UNICODE_BREAK_BEFORE_AND_AFTER",
  44         "G_UNICODE_BREAK_HYPHEN",
  45         "G_UNICODE_BREAK_NON_STARTER",
  46         "G_UNICODE_BREAK_OPEN_PUNCTUATION",
  47         "G_UNICODE_BREAK_CLOSE_PUNCTUATION",
  48         "G_UNICODE_BREAK_QUOTATION",
  49         "G_UNICODE_BREAK_EXCLAMATION",
  50         "G_UNICODE_BREAK_IDEOGRAPHIC",
  51         "G_UNICODE_BREAK_NUMERIC",
  52         "G_UNICODE_BREAK_INFIX_SEPARATOR",
  53         "G_UNICODE_BREAK_SYMBOL",
  54         "G_UNICODE_BREAK_ALPHABETIC",
  55         "G_UNICODE_BREAK_PREFIX",
  56         "G_UNICODE_BREAK_POSTFIX",
  57         "G_UNICODE_BREAK_COMPLEX_CONTEXT",
  58         "G_UNICODE_BREAK_AMBIGUOUS",
  59         "G_UNICODE_BREAK_UNKNOWN",
  60         "G_UNICODE_BREAK_NEXT_LINE",
  61         "G_UNICODE_BREAK_WORD_JOINER",
  62         "G_UNICODE_BREAK_HANGUL_L_JAMO",
  63         "G_UNICODE_BREAK_HANGUL_V_JAMO",
  64         "G_UNICODE_BREAK_HANGUL_T_JAMO",
  65         "G_UNICODE_BREAK_HANGUL_LV_SYLLABLE",
  66         "G_UNICODE_BREAK_HANGUL_LVT_SYLLABLE"
  67 };
  68
  69 static const char *unicode_char_types[] = {
  70         "G_UNICODE_CONTROL",
  71         "G_UNICODE_FORMAT",
  72         "G_UNICODE_UNASSIGNED",
  73         "G_UNICODE_PRIVATE_USE",
  74         "G_UNICODE_SURROGATE",
  75         "G_UNICODE_LOWERCASE_LETTER",
  76         "G_UNICODE_MODIFIER_LETTER",
  77         "G_UNICODE_OTHER_LETTER",
  78         "G_UNICODE_TITLECASE_LETTER",
  79         "G_UNICODE_UPPERCASE_LETTER",
  80         "G_UNICODE_COMBINING_MARK",
  81         "G_UNICODE_ENCLOSING_MARK",
  82         "G_UNICODE_NON_SPACING_MARK",
  83         "G_UNICODE_DECIMAL_NUMBER",
  84         "G_UNICODE_LETTER_NUMBER",
  85         "G_UNICODE_OTHER_NUMBER",
  86         "G_UNICODE_CONNECT_PUNCTUATION",
  87         "G_UNICODE_DASH_PUNCTUATION",
  88         "G_UNICODE_CLOSE_PUNCTUATION",
  89         "G_UNICODE_FINAL_PUNCTUATION",
  90         "G_UNICODE_INITIAL_PUNCTUATION",
  91         "G_UNICODE_OTHER_PUNCTUATION",
  92         "G_UNICODE_OPEN_PUNCTUATION",
  93         "G_UNICODE_CURRENCY_SYMBOL",
  94         "G_UNICODE_MODIFIER_SYMBOL",
  95         "G_UNICODE_MATH_SYMBOL",
  96         "G_UNICODE_OTHER_SYMBOL",
  97         "G_UNICODE_LINE_SEPARATOR",
  98         "G_UNICODE_PARAGRAPH_SEPARATOR",
  99         "G_UNICODE_SPACE_SEPARATOR"
 100 };
 101 #endif
 102
 103 #define UnicharIsLineBreak(c) ((c) == '\r' || (c) == '\n' || (c) == 0x2028)
 104
 105 #define BreakSpace(c, btype) (c == '\t' || btype == G_UNICODE_BREAK_SPACE || btype == G_UNICODE_BREAK_ZERO_WIDTH_SPACE)
 106
 107
 108 /*
 109  * Silverlight does not apply any kerning on a DOT, so we exclude them
 110  *      U+002E FULL STOP
 111  *      U+06D4 ARABIC FULL STOP
 112  *      U+3002 IDEOGRAPHIC FULL STOP
 113  * Note: this is different than using the "sliding dot" algorithm from
 114  * http://www.freetype.org/freetype2/docs/glyphs/glyphs-4.html
 115  */
 116 #define APPLY_KERNING(uc)       ((uc != 0x002E) && (uc != 0x06D4) && (uc != 3002))
 117
 118
 119 static inline gunichar
 120 utf8_getc (const char **in, size_t inlen)
 121 {
 122         register const unsigned char *inptr = (const unsigned char *) *in;
 123         const unsigned char *inend = inptr + inlen;
 124         register unsigned char c, r;
 125         register gunichar m, u = 0;
 126
 127         if (inlen == 0)
 128                 return 0;
 129
 130         r = *inptr++;
 131         if (r < 0x80) {
 132                 *in = (const char *) inptr;
 133                 u = r;
 134         } else if (r < 0xfe) { /* valid start char? */
 135                 u = r;
 136                 m = 0x7f80;    /* used to mask out the length bits */
 137                 do {
 138                         if (inptr >= inend) {
 139                                 *in = (const char *) inend;
 140                                 return 0;
 141                         }
 142
 143                         c = *inptr++;
 144                         if ((c & 0xc0) != 0x80)
 145                                 goto error;
 146
 147                         u = (u << 6) | (c & 0x3f);
 148                         r <<= 1;
 149                         m <<= 5;
 150                 } while (r & 0x40);
 151
 152                 *in = (const char *) inptr;
 153
 154                 u &= ~m;
 155         } else {
 156          error:
 157                 u = (gunichar) -1;
 158                 *in = (*in) + 1;
 159         }
 160
 161         return u;
 162 }
 163
 164
 165 //
 166 // TextLayoutGlyphCluster
 167 //
 168
 169 TextLayoutGlyphCluster::TextLayoutGlyphCluster (int _start, int _length)
 170 {
 171         length = _length;
 172         start = _start;
 173         selected = false;
 174         advance = 0.0;
 175         path = NULL;
 176 }
 177
 178 TextLayoutGlyphCluster::~TextLayoutGlyphCluster ()
 179 {
 180         if (path)
 181                 moon_path_destroy (path);
 182 }
 183
 184
 185 //
 186 // TextLayoutRun
 187 //
 188
 189 TextLayoutRun::TextLayoutRun (TextLayoutLine *_line, TextLayoutAttributes *_attrs, int _start)
 190 {
 191         clusters = g_ptr_array_new ();
 192         attrs = _attrs;
 193         start = _start;
 194         line = _line;
 195         advance = 0.0;
 196         length = 0;
 197         count = 0;
 198 }
 199
 200 TextLayoutRun::~TextLayoutRun ()
 201 {
 202         for (guint i = 0; i < clusters->len; i++)
 203                 delete (TextLayoutGlyphCluster *) clusters->pdata[i];
 204
 205         g_ptr_array_free (clusters, true);
 206 }
 207
 208 void
 209 TextLayoutRun::ClearCache ()
 210 {
 211         for (guint i = 0; i < clusters->len; i++)
 212                 delete (TextLayoutGlyphCluster *) clusters->pdata[i];
 213
 214         g_ptr_array_set_size (clusters, 0);
 215 }
 216
 217
 218 //
 219 // TextLayoutLine
 220 //
 221
 222 TextLayoutLine::TextLayoutLine (TextLayout *_layout, int _start, int _offset)
 223 {
 224         runs = g_ptr_array_new ();
 225         layout = _layout;
 226         offset = _offset;
 227         start = _start;
 228         advance = 0.0;
 229         descend = 0.0;
 230         height = 0.0;
 231         width = 0.0;
 232         length = 0;
 233         count = 0;
 234 }
 235
 236 TextLayoutLine::~TextLayoutLine ()
 237 {
 238         for (guint i = 0; i < runs->len; i++)
 239                 delete (TextLayoutRun *) runs->pdata[i];
 240
 241         g_ptr_array_free (runs, true);
 242 }
 243
 244
 245
 246 //
 247 // TextLayout
 248 //
 249
 250 TextLayout::TextLayout ()
 251 {
 252         // Note: TextBlock and TextBox assume their default values match these
 253         strategy = LineStackingStrategyMaxHeight;
 254         alignment = TextAlignmentLeft;
 255         wrapping = TextWrappingNoWrap;
 256         selection_length = 0;
 257         selection_start = 0;
 258         avail_width = INFINITY;
 259         max_height = INFINITY;
 260         max_width = INFINITY;
 261         actual_height = NAN;
 262         actual_width = NAN;
 263         line_height = NAN;
 264         attributes = NULL;
 265         lines = g_ptr_array_new ();
 266         is_wrapped = true;
 267         text = NULL;
 268         length = 0;
 269         count = 0;
 270 }
 271
 272 TextLayout::~TextLayout ()
 273 {
 274         if (attributes) {
 275                 attributes->Clear (true);
 276                 delete attributes;
 277         }
 278
 279         ClearLines ();
 280         g_ptr_array_free (lines, true);
 281
 282         g_free (text);
 283 }
 284
 285 void
 286 TextLayout::ClearLines ()
 287 {
 288         for (guint i = 0; i < lines->len; i++)
 289                 delete (TextLayoutLine *) lines->pdata[i];
 290
 291         g_ptr_array_set_size (lines, 0);
 292 }
 293
 294 void
 295 TextLayout::ResetState ()
 296 {
 297         actual_height = NAN;
 298         actual_width = NAN;
 299 }
 300
 301 bool
 302 TextLayout::SetLineStackingStrategy (LineStackingStrategy mode)
 303 {
 304         if (strategy == mode)
 305                 return false;
 306
 307         strategy = mode;
 308
 309         ResetState ();
 310
 311         return true;
 312 }
 313
 314 bool
 315 TextLayout::SetTextAlignment (TextAlignment align)
 316 {
 317         if (alignment == align)
 318                 return false;
 319
 320         alignment = align;
 321
 322         return false;
 323 }
 324
 325 bool
 326 TextLayout::SetTextWrapping (TextWrapping mode)
 327 {
 328         switch (mode) {
 329         case TextWrappingNoWrap:
 330         case TextWrappingWrap:
 331                 break;
 332         default:
 333                 // Silverlight defaults to Wrap for unknown values
 334                 mode = TextWrappingWrap;
 335                 break;
 336         }
 337
 338         if (wrapping == mode)
 339                 return false;
 340
 341         wrapping = mode;
 342
 343         ResetState ();
 344
 345         return true;
 346 }
 347
 348 bool
 349 TextLayout::SetLineHeight (double height)
 350 {
 351         if (line_height == height)
 352                 return false;
 353
 354         line_height = height;
 355
 356         ResetState ();
 357
 358         return true;
 359 }
 360
 361 bool
 362 TextLayout::SetMaxHeight (double height)
 363 {
 364         if (max_height == height)
 365                 return false;
 366
 367         max_height = height;
 368
 369         ResetState ();
 370
 371         return true;
 372 }
 373
 374 bool
 375 TextLayout::SetMaxWidth (double width)
 376 {
 377         if (width == 0.0)
 378                 width = INFINITY;
 379
 380         if (max_width == width)
 381                 return false;
 382
 383         if (!is_wrapped && (isinf (width) || width > actual_width)) {
 384                 // the new max_width won't change layout
 385                 max_width = width;
 386                 return false;
 387         }
 388
 389         max_width = width;
 390
 391         ResetState ();
 392
 393         return true;
 394 }
 395
 396 bool
 397 TextLayout::SetTextAttributes (List *attrs)
 398 {
 399         if (attributes) {
 400                 attributes->Clear (true);
 401                 delete attributes;
 402         }
 403
 404         attributes = attrs;
 405
 406         ResetState ();
 407
 408         return true;
 409 }
 410
 411 bool
 412 TextLayout::SetText (const char *str, int len)
 413 {
 414         g_free (text);
 415
 416         if (str) {
 417                 length = len == -1 ? strlen (str) : len;
 418                 text = (char *) g_malloc (length + 1);
 419                 memcpy (text, str, length);
 420                 text[length] = '\0';
 421         } else {
 422                 text = NULL;
 423                 length = 0;
 424         }
 425
 426         count = -1;
 427
 428         ResetState ();
 429
 430         return true;
 431 }
 432
 433 void
 434 TextLayout::ClearCache ()
 435 {
 436         TextLayoutLine *line;
 437         TextLayoutRun *run;
 438
 439         for (guint i = 0; i < lines->len; i++) {
 440                 line = (TextLayoutLine *) lines->pdata[i];
 441
 442                 for (guint j = 0; j < line->runs->len; j++) {
 443                         run = (TextLayoutRun *) line->runs->pdata[j];
 444                         run->ClearCache ();
 445                 }
 446         }
 447 }
 448
 449 struct TextRegion {
 450         int start, length;
 451         bool select;
 452 };
 453
 454 static void
 455 UpdateSelection (GPtrArray *lines, TextRegion *pre, TextRegion *post)
 456 {
 457         TextLayoutGlyphCluster *cluster;
 458         TextLayoutLine *line;
 459         TextLayoutRun *run;
 460         guint i, j;
 461
 462         // first update pre-region
 463         for (i = 0; i < lines->len; i++) {
 464                 line = (TextLayoutLine *) lines->pdata[i];
 465
 466                 if (pre->start >= line->start + line->length) {
 467                         // pre-region not on this line...
 468                         continue;
 469                 }
 470
 471                 for (j = 0; j < line->runs->len; j++) {
 472                         run = (TextLayoutRun *) line->runs->pdata[j];
 473
 474                         if (pre->start >= run->start + run->length) {
 475                                 // pre-region not in this run...
 476                                 continue;
 477                         }
 478
 479                         if (pre->start <= run->start) {
 480                                 if (pre->start + pre->length >= run->start + run->length) {
 481                                         // run is fully contained within the pre-region
 482                                         if (run->clusters->len == 1) {
 483                                                 cluster = (TextLayoutGlyphCluster *) run->clusters->pdata[0];
 484                                                 cluster->selected = pre->select;
 485                                         } else {
 486                                                 run->ClearCache ();
 487                                         }
 488                                 } else {
 489                                         run->ClearCache ();
 490                                 }
 491                         } else {
 492                                 run->ClearCache ();
 493                         }
 494
 495                         if (pre->start + pre->length <= run->start + run->length)
 496                                 break;
 497                 }
 498         }
 499
 500         // now update the post region...
 501         for ( ; i < lines->len; i++, j = 0) {
 502                 line = (TextLayoutLine *) lines->pdata[i];
 503
 504                 if (post->start >= line->start + line->length) {
 505                         // pre-region not on this line...
 506                         continue;
 507                 }
 508
 509                 for ( ; j < line->runs->len; j++) {
 510                         run = (TextLayoutRun *) line->runs->pdata[j];
 511
 512                         if (post->start >= run->start + run->length) {
 513                                 // post-region not in this run...
 514                                 continue;
 515                         }
 516
 517                         if (post->start <= run->start) {
 518                                 if (post->start + post->length >= run->start + run->length) {
 519                                         // run is fully contained within the pre-region
 520                                         if (run->clusters->len == 1) {
 521                                                 cluster = (TextLayoutGlyphCluster *) run->clusters->pdata[0];
 522                                                 cluster->selected = post->select;
 523                                         } else {
 524                                                 run->ClearCache ();
 525                                         }
 526                                 } else {
 527                                         run->ClearCache ();
 528                                 }
 529                         } else {
 530                                 run->ClearCache ();
 531                         }
 532
 533                         if (post->start + post->length <= run->start + run->length)
 534                                 break;
 535                 }
 536         }
 537 }
 538
 539 void
 540 TextLayout::Select (int start, int length, bool byte_offsets)
 541 {
 542         int new_selection_length;
 543         int new_selection_start;
 544         int new_selection_end;
 545         int selection_end;
 546         TextRegion pre, post;
 547         const char *inptr;
 548         const char *inend;
 549
 550         if (!text) {
 551                 selection_length = 0;
 552                 selection_start = 0;
 553                 return;
 554         }
 555
 556         if (!byte_offsets) {
 557                 inptr = g_utf8_offset_to_pointer (text, start);
 558                 new_selection_start = inptr - text;
 559
 560                 inend = g_utf8_offset_to_pointer (inptr, length);
 561                 new_selection_length = inend - inptr;
 562         } else {
 563                 new_selection_length = length;
 564                 new_selection_start = start;
 565         }
 566
 567         if (selection_start == new_selection_start &&
 568             selection_length == new_selection_length) {
 569                 // no change in selection...
 570                 return;
 571         }
 572
 573 #if 1
 574         // compute the region between the 2 starts
 575         pre.length = abs (new_selection_start - selection_start);
 576         pre.start = MIN (selection_start, new_selection_start);
 577         pre.select = (new_selection_start < selection_start) && (new_selection_length > 0);
 578
 579         // compute the region between the 2 ends
 580         new_selection_end = new_selection_start + new_selection_length;
 581         selection_end = selection_start + selection_length;
 582         post.length = abs (new_selection_end - selection_end);
 583         post.start = MIN (selection_end, new_selection_end);
 584         post.select = (new_selection_end > selection_end) && (new_selection_length > 0);
 585
 586         UpdateSelection (lines, &pre, &post);
 587
 588         selection_length = new_selection_length;
 589         selection_start = new_selection_start;
 590 #else
 591         if (selection_length || new_selection_length)
 592                 ClearCache ();
 593
 594         selection_length = new_selection_length;
 595         selection_start = new_selection_start;
 596 #endif
 597 }
 598
 599 /**
 600  * TextLayout::GetActualExtents:
 601  * @width:
 602  * @height:
 603  *
 604  * Gets the actual width and height extents required for rendering the
 605  * full text.
 606  **/
 607 void
 608 TextLayout::GetActualExtents (double *width, double *height)
 609 {
 610         *height = actual_height;
 611         *width = actual_width;
 612 }
 613
 614
 615 static int
 616 unichar_combining_class (gunichar c)
 617 {
 618 #if GLIB_CHECK_VERSION (2,14,0)
 619         if (glib_check_version (2,14,0))
 620                 return g_unichar_combining_class (c);
 621         else
 622 #endif
 623
 624         return 0;
 625 }
 626
 627 enum WordType {
 628         WORD_TYPE_UNKNOWN,
 629         WORD_TYPE_ALPHABETIC,
 630         WORD_TYPE_IDEOGRAPHIC,
 631         WORD_TYPE_INSEPARABLE,
 632         WORD_TYPE_NUMERIC,
 633         WORD_TYPE_HANGUL,
 634 };
 635
 636 struct WordBreakOpportunity {
 637         GUnicodeBreakType btype;
 638         const char *inptr;
 639         double advance;
 640         guint32 index;
 641         gunichar c;
 642         int count;
 643 };
 644
 645 struct LayoutWord {
 646         // <internal use>
 647         GArray *break_ops;     // TextWrappingWrap only
 648
 649         WordType type;
 650
 651         // <input>
 652         double line_advance;
 653         TextFont *font;
 654
 655         // <input/output>
 656         GlyphInfo *prev;       // previous glyph; used for kerning
 657
 658         // <output>
 659         double advance;        // the advance-width of the 'word'
 660         int length;            // length of the word in bytes
 661         int count;             // length of the word in unichars
 662 };
 663
 664 typedef bool (* LayoutWordCallback) (LayoutWord *word, const char *in, const char *inend, double max_width);
 665
 666 static inline bool
 667 IsLineBreak (const char *text, size_t left, size_t *n_bytes, size_t *n_chars)
 668 {
 669         const char *inptr = text;
 670         gunichar c;
 671
 672         if ((c = utf8_getc (&inptr, left)) == (gunichar) -1)
 673                 return false;
 674
 675         if (!UnicharIsLineBreak (c))
 676                 return false;
 677
 678         if (c == '\r' && *inptr == '\n') {
 679                 *n_bytes = 2;
 680                 *n_chars = 2;
 681         } else {
 682                 *n_bytes = (size_t) (inptr - text);
 683                 *n_chars = 1;
 684         }
 685
 686         return true;
 687 }
 688
 689 static inline void
 690 layout_word_init (LayoutWord *word, double line_advance, GlyphInfo *prev)
 691 {
 692         word->line_advance = line_advance;
 693         word->prev = prev;
 694 }
 695
 696 /**
 697  * layout_lwsp:
 698  * @word: #LayoutWord context
 699  * @in: input text
 700  * @inend: end of input text
 701  *
 702  * Measures a word containing nothing but LWSP.
 703  **/
 704 static void
 705 layout_lwsp (LayoutWord *word, const char *in, const char *inend)
 706 {
 707         GlyphInfo *prev = word->prev;
 708         GUnicodeBreakType btype;
 709         const char *inptr = in;
 710         const char *start;
 711         GlyphInfo *glyph;
 712         double advance;
 713         gunichar c;
 714
 715         d(printf ("layout_lwsp():\n"));
 716
 717         word->advance = 0.0;
 718         word->count = 0;
 719
 720         while (inptr < inend) {
 721                 start = inptr;
 722                 if ((c = utf8_getc (&inptr, inend - inptr)) == (gunichar) -1) {
 723                         // ignore invalid chars
 724                         continue;
 725                 }
 726
 727                 if (UnicharIsLineBreak (c)) {
 728                         inptr = start;
 729                         break;
 730                 }
 731
 732                 btype = g_unichar_break_type (c);
 733                 if (!BreakSpace (c, btype)) {
 734                         inptr = start;
 735                         break;
 736                 }
 737
 738 #if DEBUG
 739                 if (debug_flags & RUNTIME_DEBUG_LAYOUT) {
 740                         if (c < 128 && isprint ((int) c))
 741                                 printf ("\tunichar = %c; btype = %s, ctype = %s\n", (char) c,
 742                                         unicode_break_types[btype], unicode_char_types[g_unichar_type (c)]);
 743                         else
 744                                 printf ("\tunichar = 0x%.4X; btype = %s, ctype = %s\n", c,
 745                                         unicode_break_types[btype], unicode_char_types[g_unichar_type (c)]);
 746                 }
 747 #endif
 748
 749                 word->count++;
 750
 751                 // treat tab as a single space
 752                 if (c == '\t')
 753                         c = ' ';
 754
 755                 // ignore glyphs the font doesn't contain...
 756                 if (!(glyph = word->font->GetGlyphInfo (c)))
 757                         continue;
 758
 759                 // calculate total glyph advance
 760                 advance = glyph->metrics.horiAdvance;
 761                 if ((prev != NULL) && APPLY_KERNING (c))
 762                         advance += word->font->Kerning (prev, glyph);
 763                 else if (glyph->metrics.horiBearingX < 0)
 764                         advance -= glyph->metrics.horiBearingX;
 765
 766                 word->line_advance += advance;
 767                 word->advance += advance;
 768                 prev = glyph;
 769         }
 770
 771         word->length = (inptr - in);
 772         word->prev = prev;
 773 }
 774
 775 /**
 776  * layout_word_nowrap:
 777  * @word: #LayoutWord context
 778  * @in: input text
 779  * @inend = end of input text
 780  * @max_width: max allowable width for a line
 781  *
 782  * Calculates the advance of the current word.
 783  *
 784  * Returns: %true if the caller should create a new line for the
 785  * remainder of the word or %false otherwise.
 786  **/
 787 static bool
 788 layout_word_nowrap (LayoutWord *word, const char *in, const char *inend, double max_width)
 789 {
 790         GUnicodeBreakType btype = G_UNICODE_BREAK_UNKNOWN;
 791         GlyphInfo *prev = word->prev;
 792         const char *inptr = in;
 793         const char *start;
 794         GlyphInfo *glyph;
 795         double advance;
 796         gunichar c;
 797
 798         // Note: since we don't ever need to wrap, no need to keep track of word-type
 799         word->type = WORD_TYPE_UNKNOWN;
 800         word->advance = 0.0;
 801         word->count = 0;
 802
 803         while (inptr < inend) {
 804                 start = inptr;
 805                 if ((c = utf8_getc (&inptr, inend - inptr)) == (gunichar) -1) {
 806                         // ignore invalid chars
 807                         continue;
 808                 }
 809
 810                 if (UnicharIsLineBreak (c)) {
 811                         inptr = start;
 812                         break;
 813                 }
 814
 815                 if (btype == G_UNICODE_BREAK_COMBINING_MARK) {
 816                         // ignore zero-width spaces
 817                         if ((btype = g_unichar_break_type (c)) == G_UNICODE_BREAK_ZERO_WIDTH_SPACE)
 818                                 btype = G_UNICODE_BREAK_COMBINING_MARK;
 819                 } else {
 820                         btype = g_unichar_break_type (c);
 821                 }
 822
 823                 if (BreakSpace (c, btype)) {
 824                         inptr = start;
 825                         break;
 826                 }
 827
 828                 word->count++;
 829
 830                 // ignore glyphs the font doesn't contain...
 831                 if (!(glyph = word->font->GetGlyphInfo (c)))
 832                         continue;
 833
 834                 // calculate total glyph advance
 835                 advance = glyph->metrics.horiAdvance;
 836                 if ((prev != NULL) && APPLY_KERNING (c))
 837                         advance += word->font->Kerning (prev, glyph);
 838                 else if (glyph->metrics.horiBearingX < 0)
 839                         advance -= glyph->metrics.horiBearingX;
 840
 841                 word->line_advance += advance;
 842                 word->advance += advance;
 843                 prev = glyph;
 844         }
 845
 846         word->length = (inptr - in);
 847         word->prev = prev;
 848
 849         return false;
 850 }
 851
 852 static WordType
 853 word_type (GUnicodeType ctype, GUnicodeBreakType btype)
 854 {
 855         switch (btype) {
 856         case G_UNICODE_BREAK_ALPHABETIC:
 857                 return WORD_TYPE_ALPHABETIC;
 858         case G_UNICODE_BREAK_IDEOGRAPHIC:
 859                 return WORD_TYPE_IDEOGRAPHIC;
 860         case G_UNICODE_BREAK_NUMERIC:
 861                 if (ctype == G_UNICODE_OTHER_PUNCTUATION)
 862                         return WORD_TYPE_UNKNOWN;
 863                 return WORD_TYPE_NUMERIC;
 864         case G_UNICODE_BREAK_INSEPARABLE:
 865                 return WORD_TYPE_INSEPARABLE;
 866 #if GLIB_CHECK_VERSION (2,10,0)
 867         case G_UNICODE_BREAK_HANGUL_LVT_SYLLABLE:
 868         case G_UNICODE_BREAK_HANGUL_LV_SYLLABLE:
 869         case G_UNICODE_BREAK_HANGUL_L_JAMO:
 870         case G_UNICODE_BREAK_HANGUL_V_JAMO:
 871         case G_UNICODE_BREAK_HANGUL_T_JAMO:
 872                 return WORD_TYPE_HANGUL;
 873 #endif
 874         default:
 875                 return WORD_TYPE_UNKNOWN;
 876         }
 877 }
 878
 879 static bool
 880 word_type_changed (WordType wtype, gunichar c, GUnicodeType ctype, GUnicodeBreakType btype)
 881 {
 882         WordType type;
 883
 884         // compare this character's word-type against the current word-type
 885         if ((type = word_type (ctype, btype)) == wtype)
 886                 return false;
 887
 888         if (type == WORD_TYPE_UNKNOWN)
 889                 return false;
 890
 891         // word-types not identical... check if they are compatible
 892         switch (wtype) {
 893         case WORD_TYPE_ALPHABETIC:
 894                 return type != WORD_TYPE_NUMERIC;
 895 #if 0
 896         case WORD_TYPE_IDEOGRAPHIC:
 897                 // this fixes drt #411 but breaks drt #208. I can't win.
 898                 return type != WORD_TYPE_ALPHABETIC;
 899 #endif
 900         default:
 901                 return true;
 902         }
 903 }
 904
 905
 906 /**
 907  * layout_word_wrap:
 908  * @word: word state
 909  * @in: start of word
 910  * @inend = end of word
 911  * @max_width: max allowable width for a line
 912  *
 913  * Calculates the advance of the current word, breaking if needed.
 914  *
 915  * Returns: %true if the caller should create a new line for the
 916  * remainder of the word or %false otherwise.
 917  **/
 918 static bool
 919 layout_word_wrap (LayoutWord *word, const char *in, const char *inend, double max_width)
 920 {
 921         GUnicodeBreakType btype = G_UNICODE_BREAK_UNKNOWN;
 922         bool line_start = word->line_advance == 0.0;
 923         GlyphInfo *prev = word->prev;
 924         WordBreakOpportunity op;
 925         const char *inptr = in;
 926         const char *start;
 927         GUnicodeType ctype;
 928         bool force = false;
 929         bool fixed = false;
 930         bool wrap = false;
 931         GlyphInfo *glyph;
 932 #if DEBUG
 933         GString *debug;
 934 #endif
 935         double advance;
 936         int glyphs = 0;
 937         bool new_glyph;
 938         gunichar c;
 939
 940         g_array_set_size (word->break_ops, 0);
 941         word->type = WORD_TYPE_UNKNOWN;
 942         word->advance = 0.0;
 943         word->count = 0;
 944
 945         d(printf ("layout_word_wrap():\n"));
 946         d(debug = g_string_new (""));
 947
 948         while (inptr < inend) {
 949                 start = inptr;
 950                 if ((c = utf8_getc (&inptr, inend - inptr)) == (gunichar) -1) {
 951                         // ignore invalid chars
 952                         continue;
 953                 }
 954
 955                 if (UnicharIsLineBreak (c)) {
 956                         inptr = start;
 957                         break;
 958                 }
 959
 960                 // check the previous break-type
 961                 if (btype == G_UNICODE_BREAK_CLOSE_PUNCTUATION) {
 962                         // if anything other than an infix separator come after a close-punctuation, then the 'word' is done
 963                         btype = g_unichar_break_type (c);
 964                         if (btype != G_UNICODE_BREAK_INFIX_SEPARATOR) {
 965                                 inptr = start;
 966                                 break;
 967                         }
 968                 } else if (btype == G_UNICODE_BREAK_INFIX_SEPARATOR) {
 969                         btype = g_unichar_break_type (c);
 970                         if (word->type == WORD_TYPE_NUMERIC) {
 971                                 // only accept numbers after the infix
 972                                 if (btype != G_UNICODE_BREAK_NUMERIC) {
 973                                         inptr = start;
 974                                         break;
 975                                 }
 976                         } else if (word->type == WORD_TYPE_UNKNOWN) {
 977                                 // only accept alphanumerics after the infix
 978                                 if (btype != G_UNICODE_BREAK_ALPHABETIC && btype != G_UNICODE_BREAK_NUMERIC) {
 979                                         inptr = start;
 980                                         break;
 981                                 }
 982
 983                                 fixed = true;
 984                         }
 985                 } else if (btype == G_UNICODE_BREAK_WORD_JOINER) {
 986                         btype = g_unichar_break_type (c);
 987                         fixed = true;
 988                 } else {
 989                         btype = g_unichar_break_type (c);
 990                 }
 991
 992                 if (BreakSpace (c, btype)) {
 993                         inptr = start;
 994                         break;
 995                 }
 996
 997                 ctype = g_unichar_type (c);
 998
 999                 if (word->type == WORD_TYPE_UNKNOWN) {
1000                         // record our word-type
1001                         word->type = word_type (ctype, btype);
1002                 } else if (btype == G_UNICODE_BREAK_OPEN_PUNCTUATION) {
1003                         // this is a good place to break
1004                         inptr = start;
1005                         break;
1006                 } else if (word_type_changed (word->type, c, ctype, btype)) {
1007                         // changing word-types, don't continue
1008                         inptr = start;
1009                         break;
1010                 }
1011
1012                 d(g_string_append_unichar (debug, c));
1013                 word->count++;
1014
1015                 // a Combining Class of 0 means start of a new glyph
1016                 if (glyphs > 0 && unichar_combining_class (c) != 0) {
1017                         // this char gets combined with the previous glyph
1018                         new_glyph = false;
1019                 } else {
1020                         new_glyph = true;
1021                         glyphs++;
1022                 }
1023
1024 #if DEBUG
1025                 if (debug_flags & RUNTIME_DEBUG_LAYOUT) {
1026                         if (c < 128 && isprint ((int) c))
1027                                 printf ("\tunichar = %c; btype = %s, new glyph = %s; cc = %d; ctype = %s\n", (char) c,
1028                                         unicode_break_types[btype], new_glyph ? "true" : "false", unichar_combining_class (c),
1029                                         unicode_char_types[ctype]);
1030                         else
1031                                 printf ("\tunichar = 0x%.4X; btype = %s, new glyph = %s; cc = %d; ctype = %s\n", c,
1032                                         unicode_break_types[btype], new_glyph ? "true" : "false", unichar_combining_class (c),
1033                                         unicode_char_types[ctype]);
1034                 }
1035 #endif
1036
1037                 if ((glyph = word->font->GetGlyphInfo (c))) {
1038                         // calculate total glyph advance
1039                         advance = glyph->metrics.horiAdvance;
1040                         if ((prev != NULL) && APPLY_KERNING (c))
1041                                 advance += word->font->Kerning (prev, glyph);
1042                         else if (glyph->metrics.horiBearingX < 0)
1043                                 advance -= glyph->metrics.horiBearingX;
1044
1045                         word->line_advance += advance;
1046                         word->advance += advance;
1047                         prev = glyph;
1048                 } else {
1049                         advance = 0.0;
1050                 }
1051
1052                 if (new_glyph) {
1053                         op.index = glyph ? glyph->index : 0;
1054                         op.advance = word->advance;
1055                         op.count = word->count;
1056                         op.inptr = inptr;
1057                         op.btype = btype;
1058                         op.c = c;
1059                 } else {
1060                         g_array_remove_index (word->break_ops, word->break_ops->len - 1);
1061                         op.advance += advance;
1062                         op.inptr = inptr;
1063                         op.count++;
1064                 }
1065
1066                 g_array_append_val (word->break_ops, op);
1067
1068                 if (!isinf (max_width) && word->line_advance > max_width) {
1069                         d(printf ("\tjust exceeded max width (%fpx): %s\n", max_width, debug->str));
1070                         wrap = true;
1071                         break;
1072                 }
1073         }
1074
1075         if (!wrap) {
1076                 d(g_string_free (debug, true));
1077                 word->length = (inptr - in);
1078                 word->prev = prev;
1079                 return false;
1080         }
1081
1082         d(printf ("\tcollecting any/all decomposed chars and figuring out the break-type for the next glyph\n"));
1083
1084         // pretend btype is SPACE here in case inptr is at the end of the run
1085         if (inptr == inend)
1086                 btype = G_UNICODE_BREAK_SPACE;
1087
1088         // keep going until we reach a new distinct glyph. we also
1089         // need to know the btype of the char after the char that
1090         // exceeded the width limit.
1091         while (inptr < inend) {
1092                 start = inptr;
1093                 if ((c = utf8_getc (&inptr, inend - inptr)) == (gunichar) -1) {
1094                         // ignore invalid chars
1095                         continue;
1096                 }
1097
1098                 if (UnicharIsLineBreak (c)) {
1099                         btype = G_UNICODE_BREAK_SPACE;
1100                         inptr = start;
1101                         break;
1102                 }
1103
1104                 btype = g_unichar_break_type (c);
1105                 if (BreakSpace (c, btype) || unichar_combining_class (c) == 0) {
1106                         inptr = start;
1107                         break;
1108                 }
1109
1110                 d(g_string_append_unichar (debug, c));
1111                 word->count++;
1112
1113                 if ((glyph = word->font->GetGlyphInfo (c))) {
1114                         // calculate total glyph advance
1115                         advance = glyph->metrics.horiAdvance;
1116                         if ((prev != NULL) && APPLY_KERNING (c))
1117                                 advance += word->font->Kerning (prev, glyph);
1118                         else if (glyph->metrics.horiBearingX < 0)
1119                                 advance -= glyph->metrics.horiBearingX;
1120
1121                         word->line_advance += advance;
1122                         word->advance += advance;
1123                         prev = glyph;
1124                 } else {
1125                         advance = 0.0;
1126                 }
1127
1128                 g_array_remove_index (word->break_ops, word->break_ops->len - 1);
1129                 op.advance += advance;
1130                 op.inptr = inptr;
1131                 op.count++;
1132                 g_array_append_val (word->break_ops, op);
1133         }
1134
1135         d(printf ("\tok, at this point we have: %s\n", debug->str));
1136         d(printf ("\tnext break-type is %s\n", unicode_break_types[btype]));
1137         d(g_string_free (debug, true));
1138
1139         // at this point, we're going to break the word so we can reset kerning
1140         word->prev = 0;
1141
1142         // we can't break any smaller than a single glyph
1143         if (line_start && glyphs == 1) {
1144                 d(printf ("\tsince this is the first glyph on the line, can't break any smaller than that...\n"));
1145                 word->length = (inptr - in);
1146                 word->prev = prev;
1147                 return true;
1148         }
1149
1150  retry:
1151
1152         // search backwards for the best break point
1153         d(printf ("\tscanning over %d break opportunities...\n", word->break_ops->len));
1154         for (guint i = word->break_ops->len; i > 0; i--) {
1155                 op = g_array_index (word->break_ops, WordBreakOpportunity, i - 1);
1156
1157 #if DEBUG
1158                 if (debug_flags & RUNTIME_DEBUG_LAYOUT) {
1159                         if (op.c < 128 && isprint ((int) op.c))
1160                                 printf ("\tunichar = %c; btype = %s; i = %d\n", (char) op.c, unicode_break_types[op.btype], i);
1161                         else
1162                                 printf ("\tunichar = 0x%.4X; btype = %s; i = %d\n", op.c, unicode_break_types[op.btype], i);
1163                 }
1164 #endif
1165
1166                 switch (op.btype) {
1167                 case G_UNICODE_BREAK_BEFORE_AND_AFTER:
1168                         if (i > 1 && i == word->break_ops->len) {
1169                                 // break after the previous glyph
1170                                 op = g_array_index (word->break_ops, WordBreakOpportunity, i - 2);
1171                                 word->prev = word->font->GetGlyphInfo (op.c);
1172                                 word->length = (op.inptr - in);
1173                                 word->advance = op.advance;
1174                                 word->count = op.count;
1175
1176                                 return true;
1177                         } else if (i < word->break_ops->len) {
1178                                 // break after this glyph
1179                                 word->prev = word->font->GetGlyphInfo (op.c);
1180                                 word->length = (op.inptr - in);
1181                                 word->advance = op.advance;
1182                                 word->count = op.count;
1183
1184                                 return true;
1185                         }
1186                 case G_UNICODE_BREAK_NON_BREAKING_GLUE:
1187                 case G_UNICODE_BREAK_WORD_JOINER:
1188                         // cannot break before or after this character (unless forced)
1189                         if (force && i < word->break_ops->len) {
1190                                 word->prev = word->font->GetGlyphInfo (op.c);
1191                                 word->length = (op.inptr - in);
1192                                 word->advance = op.advance;
1193                                 word->count = op.count;
1194
1195                                 return true;
1196                         }
1197
1198                         if (i > 1) {
1199                                 // skip past previous glyph
1200                                 op = g_array_index (word->break_ops, WordBreakOpportunity, i - 2);
1201                                 i--;
1202                         }
1203                         break;
1204                 case G_UNICODE_BREAK_INSEPARABLE:
1205                         // only restriction is no breaking between inseparables unless we have to
1206                         if (line_start && i < word->break_ops->len) {
1207                                 word->prev = word->font->GetGlyphInfo (op.c);
1208                                 word->length = (op.inptr - in);
1209                                 word->advance = op.advance;
1210                                 word->count = op.count;
1211
1212                                 return true;
1213                         }
1214                         break;
1215                 case G_UNICODE_BREAK_BEFORE:
1216                         if (i > 1) {
1217                                 // break after the previous glyph
1218                                 op = g_array_index (word->break_ops, WordBreakOpportunity, i - 2);
1219                                 word->prev = word->font->GetGlyphInfo (op.c);
1220                                 word->length = (op.inptr - in);
1221                                 word->advance = op.advance;
1222                                 word->count = op.count;
1223
1224                                 return true;
1225                         }
1226                         break;
1227                 case G_UNICODE_BREAK_CLOSE_PUNCTUATION:
1228                         if (i < word->break_ops->len && (force || btype != G_UNICODE_BREAK_INFIX_SEPARATOR)) {
1229                                 // we can safely break after this character
1230                                 word->prev = word->font->GetGlyphInfo (op.c);
1231                                 word->length = (op.inptr - in);
1232                                 word->advance = op.advance;
1233                                 word->count = op.count;
1234
1235                                 return true;
1236                         }
1237
1238                         if (i > 1 && !force) {
1239                                 // we can never break before a closing punctuation, so skip past prev char
1240                                 op = g_array_index (word->break_ops, WordBreakOpportunity, i - 2);
1241                                 i--;
1242                         }
1243                         break;
1244                 case G_UNICODE_BREAK_INFIX_SEPARATOR:
1245                         if (i < word->break_ops->len && (force || btype != G_UNICODE_BREAK_NUMERIC)) {
1246                                 // we can safely break after this character
1247                                 word->prev = word->font->GetGlyphInfo (op.c);
1248                                 word->length = (op.inptr - in);
1249                                 word->advance = op.advance;
1250                                 word->count = op.count;
1251
1252                                 return true;
1253                         }
1254
1255                         if (i > 1 && !force) {
1256                                 // we can never break before an infix, skip past prev char
1257                                 op = g_array_index (word->break_ops, WordBreakOpportunity, i - 2);
1258                                 if (op.btype == G_UNICODE_BREAK_INFIX_SEPARATOR ||
1259                                     op.btype == G_UNICODE_BREAK_CLOSE_PUNCTUATION) {
1260                                         // unless previous char is one of these special types...
1261                                         op = g_array_index (word->break_ops, WordBreakOpportunity, i - 1);
1262                                 } else {
1263                                         i--;
1264                                 }
1265                         }
1266                         break;
1267                 case G_UNICODE_BREAK_ALPHABETIC:
1268                         // only break if we have no choice...
1269                         if ((line_start || fixed || force) && i < word->break_ops->len) {
1270                                 word->prev = word->font->GetGlyphInfo (op.c);
1271                                 word->length = (op.inptr - in);
1272                                 word->advance = op.advance;
1273                                 word->count = op.count;
1274
1275                                 return true;
1276                         }
1277                         break;
1278                 case G_UNICODE_BREAK_IDEOGRAPHIC:
1279                         if (i < word->break_ops->len && btype != G_UNICODE_BREAK_NON_STARTER) {
1280                                 // we can safely break after this character
1281                                 word->prev = word->font->GetGlyphInfo (op.c);
1282                                 word->length = (op.inptr - in);
1283                                 word->advance = op.advance;
1284                                 word->count = op.count;
1285
1286                                 return true;
1287                         }
1288                         break;
1289                 case G_UNICODE_BREAK_NUMERIC:
1290                         // only break if we have no choice...
1291                         if (line_start && i < word->break_ops->len && (force || btype != G_UNICODE_BREAK_INFIX_SEPARATOR)) {
1292                                 word->prev = word->font->GetGlyphInfo (op.c);
1293                                 word->length = (op.inptr - in);
1294                                 word->advance = op.advance;
1295                                 word->count = op.count;
1296
1297                                 return true;
1298                         }
1299                         break;
1300                 case G_UNICODE_BREAK_OPEN_PUNCTUATION:
1301                 case G_UNICODE_BREAK_COMBINING_MARK:
1302                 case G_UNICODE_BREAK_CONTINGENT:
1303                 case G_UNICODE_BREAK_AMBIGUOUS:
1304                 case G_UNICODE_BREAK_QUOTATION:
1305                 case G_UNICODE_BREAK_PREFIX:
1306                         // do not break after characters with these break-types (unless forced)
1307                         if (force && i < word->break_ops->len) {
1308                                 word->prev = word->font->GetGlyphInfo (op.c);
1309                                 word->length = (op.inptr - in);
1310                                 word->advance = op.advance;
1311                                 word->count = op.count;
1312
1313                                 return true;
1314                         }
1315                         break;
1316                 default:
1317                         d(printf ("Unhandled Unicode break-type: %s\n", unicode_break_types[op.btype]));
1318                         // fall thru to the "default" behavior
1319
1320 #if GLIB_CHECK_VERSION (2,10,0)
1321                 case G_UNICODE_BREAK_HANGUL_LVT_SYLLABLE:
1322                 case G_UNICODE_BREAK_HANGUL_LV_SYLLABLE:
1323                 case G_UNICODE_BREAK_HANGUL_L_JAMO:
1324                 case G_UNICODE_BREAK_HANGUL_V_JAMO:
1325                 case G_UNICODE_BREAK_HANGUL_T_JAMO:
1326 #endif
1327                 case G_UNICODE_BREAK_NON_STARTER:
1328                 case G_UNICODE_BREAK_EXCLAMATION:
1329                 case G_UNICODE_BREAK_MANDATORY:
1330                 case G_UNICODE_BREAK_NEXT_LINE:
1331                 case G_UNICODE_BREAK_UNKNOWN:
1332                 case G_UNICODE_BREAK_POSTFIX:
1333                 case G_UNICODE_BREAK_HYPHEN:
1334                 case G_UNICODE_BREAK_AFTER:
1335                         if (i < word->break_ops->len) {
1336                                 // we can safely break after this character
1337                                 word->prev = word->font->GetGlyphInfo (op.c);
1338                                 word->length = (op.inptr - in);
1339                                 word->advance = op.advance;
1340                                 word->count = op.count;
1341
1342                                 return true;
1343                         }
1344                         break;
1345                 }
1346
1347                 btype = op.btype;
1348                 c = op.c;
1349         }
1350
1351         if (line_start && !force) {
1352                 d(printf ("\tcouldn't find a good place to break but we must force a break, retrying...\n"));
1353                 force = true;
1354                 goto retry;
1355         }
1356
1357         d(printf ("\tcouldn't find a good place to break, defaulting to breaking before the word start\n"));
1358
1359         word->advance = 0.0;
1360         word->length = 0;
1361         word->count = 0;
1362
1363         return true;
1364 }
1365
1366 #if DEBUG
1367 static const char *wrap_modes[3] = {
1368         "WrapWithOverflow",
1369         "NoWrap",
1370         "Wrap"
1371 };
1372
1373 static void
1374 print_lines (GPtrArray *lines)
1375 {
1376         TextLayoutLine *line;
1377         TextLayoutRun *run;
1378         const char *text;
1379         double y = 0.0;
1380
1381         for (guint i = 0; i < lines->len; i++) {
1382                 line = (TextLayoutLine *) lines->pdata[i];
1383
1384                 printf ("Line (top=%f, height=%f, advance=%f, offset=%d, count=%d):\n", y, line->height, line->advance, line->offset, line->count);
1385                 for (guint j = 0; j < line->runs->len; j++) {
1386                         run = (TextLayoutRun *) line->runs->pdata[j];
1387
1388                         text = line->layout->GetText () + run->start;
1389
1390                         printf ("\tRun (advance=%f, start=%d, length=%d): \"", run->advance, run->start, run->length);
1391                         for (const char *s = text; s < text + run->length; s++) {
1392                                 switch (*s) {
1393                                 case '\r':
1394                                         fputs ("\\r", stdout);
1395                                         break;
1396                                 case '\n':
1397                                         fputs ("\\n", stdout);
1398                                         break;
1399                                 case '\t':
1400                                         fputs ("\\t", stdout);
1401                                         break;
1402                                 case '"':
1403                                         fputs ("\\\"", stdout);
1404                                         break;
1405                                 default:
1406                                         fputc (*s, stdout);
1407                                         break;
1408                                 }
1409                         }
1410                         printf ("\"\n");
1411                 }
1412
1413                 y += line->height;
1414         }
1415 }
1416 #endif
1417
1418 static LayoutWordCallback layout_word_behavior[] = {
1419         layout_word_wrap,
1420         layout_word_nowrap,
1421         layout_word_wrap
1422 };
1423
1424 static bool
1425 validate_attrs (List *attributes)
1426 {
1427         TextLayoutAttributes *attrs;
1428
1429         // if no attributes or first attribute doesn't start at 0, we can't layout any text
1430         if (!(attrs = (TextLayoutAttributes *) attributes->First ()) || attrs->start != 0)
1431                 return false;
1432
1433         while (attrs != NULL) {
1434                 if (!attrs->Font ()) {
1435                         // we can't layout any text if any of the attributes
1436                         // weren't able to load their font
1437                         return false;
1438                 }
1439
1440                 attrs = (TextLayoutAttributes *) attrs->next;
1441         }
1442
1443         return true;
1444 }
1445
1446 void
1447 TextLayout::Layout ()
1448 {
1449         TextLayoutAttributes *attrs, *nattrs;
1450         LayoutWordCallback layout_word;
1451         const char *inptr, *inend;
1452         size_t n_bytes, n_chars;
1453         TextLayoutLine *line;
1454         TextLayoutRun *run;
1455         GlyphInfo *prev;
1456         LayoutWord word;
1457         TextFont *font;
1458         bool linebreak;
1459         int offset = 0;
1460         bool wrapped;
1461
1462         if (!isnan (actual_width))
1463                 return;
1464
1465         actual_height = 0.0;
1466         actual_width = 0.0;
1467         is_wrapped = false;
1468         ClearLines ();
1469         count = 0;
1470
1471         if (!text || !validate_attrs (attributes))
1472                 return;
1473
1474         d(printf ("TextLayout::Layout(): wrap mode = %s, wrapping to %f pixels\n", wrap_modes[wrapping], max_width));
1475
1476         if (wrapping == TextWrappingWrap)
1477                 word.break_ops = g_array_new (false, false, sizeof (WordBreakOpportunity));
1478         else
1479                 word.break_ops = NULL;
1480
1481         layout_word = layout_word_behavior[wrapping];
1482
1483         attrs = (TextLayoutAttributes *) attributes->First ();
1484         line = new TextLayoutLine (this, 0, 0);
1485         if (OverrideLineHeight ())
1486                 line->height = line_height;
1487
1488         g_ptr_array_add (lines, line);
1489         inptr = text;
1490
1491         do {
1492                 nattrs = (TextLayoutAttributes *) attrs->next;
1493                 inend = text + (nattrs ? nattrs->start : length);
1494                 run = new TextLayoutRun (line, attrs, inptr - text);
1495                 g_ptr_array_add (line->runs, run);
1496
1497                 word.font = font = attrs->Font ();
1498
1499                 //if (!OverrideLineHeight ()) {
1500                 //      line->descend = MIN (line->descend, font->Descender ());
1501                 //      line->height = MAX (line->height, font->Height ());
1502                 //}
1503
1504                 if (*inptr == '\0') {
1505                         if (!OverrideLineHeight ()) {
1506                                 line->descend = MIN (line->descend, font->Descender ());
1507                                 line->height = MAX (line->height, font->Height ());
1508                         }
1509
1510                         actual_height += line->height;
1511                         break;
1512                 }
1513
1514                 // layout until attrs change
1515                 while (inptr < inend) {
1516                         linebreak = false;
1517                         wrapped = false;
1518                         prev = NULL;
1519
1520                         // layout until eoln or until we reach max_width
1521                         while (inptr < inend) {
1522                                 // check for line-breaks
1523                                 if (IsLineBreak (inptr, inend - inptr, &n_bytes, &n_chars)) {
1524                                         if (line->length == 0 && !OverrideLineHeight ()) {
1525                                                 line->descend = font->Descender ();
1526                                                 line->height = font->Height ();
1527                                         }
1528
1529                                         line->length += n_bytes;
1530                                         run->length += n_bytes;
1531                                         line->count += n_chars;
1532                                         run->count += n_chars;
1533                                         offset += n_chars;
1534                                         inptr += n_bytes;
1535                                         linebreak = true;
1536                                         break;
1537                                 }
1538
1539                                 layout_word_init (&word, line->advance, prev);
1540
1541                                 // lay out the next word
1542                                 if (layout_word (&word, inptr, inend, max_width)) {
1543                                         // force a line wrap...
1544                                         is_wrapped = true;
1545                                         wrapped = true;
1546                                 }
1547
1548                                 if (word.length > 0) {
1549                                         // append the word to the run/line
1550                                         if (!OverrideLineHeight ()) {
1551                                                 line->descend = MIN (line->descend, font->Descender ());
1552                                                 line->height = MAX (line->height, font->Height ());
1553                                         }
1554
1555                                         line->advance += word.advance;
1556                                         run->advance += word.advance;
1557                                         line->width = line->advance;
1558                                         line->length += word.length;
1559                                         run->length += word.length;
1560                                         line->count += word.count;
1561                                         run->count += word.count;
1562
1563                                         offset += word.count;
1564                                         inptr += word.length;
1565                                         prev = word.prev;
1566                                 }
1567
1568                                 if (wrapped)
1569                                         break;
1570
1571                                 // now append any trailing lwsp
1572                                 layout_word_init (&word, line->advance, prev);
1573
1574                                 layout_lwsp (&word, inptr, inend);
1575
1576                                 if (word.length > 0) {
1577                                         if (!OverrideLineHeight ()) {
1578                                                 line->descend = MIN (line->descend, font->Descender ());
1579                                                 line->height = MAX (line->height, font->Height ());
1580                                         }
1581
1582                                         line->advance += word.advance;
1583                                         run->advance += word.advance;
1584                                         line->length += word.length;
1585                                         run->length += word.length;
1586                                         line->count += word.count;
1587                                         run->count += word.count;
1588
1589                                         offset += word.count;
1590                                         inptr += word.length;
1591                                         prev = word.prev;
1592                                 }
1593                         }
1594
1595                         if (linebreak || wrapped || *inptr == '\0') {
1596                                 // update actual width extents
1597                                 if (*inptr == '\0') {
1598                                         // ActualWidth extents only include trailing lwsp on the last line
1599                                         actual_width = MAX (actual_width, line->advance);
1600                                 } else {
1601                                         // not the last line, so don't include trailing lwsp
1602                                         actual_width = MAX (actual_width, line->width);
1603                                 }
1604
1605                                 // update actual height extents
1606                                 actual_height += line->height;
1607
1608                                 if (linebreak || wrapped) {
1609                                         // more text to layout... which means we'll need a new line
1610                                         line = new TextLayoutLine (this, inptr - text, offset);
1611
1612                                         if (!OverrideLineHeight ()) {
1613                                                 if (*inptr == '\0') {
1614                                                         line->descend = font->Descender ();
1615                                                         line->height = font->Height ();
1616                                                 }
1617                                         } else {
1618                                                 line->height = line_height;
1619                                         }
1620
1621                                         if (linebreak && *inptr == '\0')
1622                                                 actual_height += line->height;
1623
1624                                         g_ptr_array_add (lines, line);
1625                                         prev = NULL;
1626                                 }
1627
1628                                 if (inptr < inend) {
1629                                         // more text to layout with the current attrs...
1630                                         run = new TextLayoutRun (line, attrs, inptr - text);
1631                                         g_ptr_array_add (line->runs, run);
1632                                 }
1633                         }
1634                 }
1635
1636                 attrs = nattrs;
1637         } while (*inptr != '\0');
1638
1639         if (word.break_ops != NULL)
1640                 g_array_free (word.break_ops, true);
1641
1642         count = offset;
1643
1644 #if DEBUG
1645         if (debug_flags & RUNTIME_DEBUG_LAYOUT) {
1646                 print_lines (lines);
1647                 printf ("actualWidth = %f, actualHeight = %f\n\n", actual_width, actual_height);
1648         }
1649 #endif
1650 }
1651
1652 static inline TextLayoutGlyphCluster *
1653 GenerateGlyphCluster (TextFont *font, GlyphInfo **pglyph, const char *text, int start, int length)
1654 {
1655         TextLayoutGlyphCluster *cluster = new TextLayoutGlyphCluster (start, length);
1656         const char *inend = text + start + length;
1657         const char *inptr = text + start;
1658         GlyphInfo *prev = *pglyph;
1659         double x0, x1, y0;
1660         GlyphInfo *glyph;
1661         int size = 0;
1662         gunichar c;
1663
1664         // set y0 to the baseline
1665         y0 = font->Ascender ();
1666         x0 = 0.0;
1667         x1 = 0.0;
1668
1669         // count how many path data items we'll need to allocate
1670         while (inptr < inend) {
1671                 if ((c = utf8_getc (&inptr, inend - inptr)) == (gunichar) -1)
1672                         continue;
1673
1674                 if (UnicharIsLineBreak (c))
1675                         break;
1676
1677                 // treat tab as a single space
1678                 if (c == '\t')
1679                         c = ' ';
1680
1681                 if (!(glyph = font->GetGlyphInfo (c)))
1682                         continue;
1683
1684                 if (glyph->path)
1685                         size += glyph->path->cairo.num_data + 1;
1686         }
1687
1688         if (size > 0) {
1689                 // generate the cached path for the cluster
1690                 cluster->path = moon_path_new (size);
1691                 inptr = text + start;
1692
1693                 while (inptr < inend) {
1694                         if ((c = utf8_getc (&inptr, inend - inptr)) == (gunichar) -1)
1695                                 continue;
1696
1697                         if (UnicharIsLineBreak (c))
1698                                 break;
1699
1700                         // treat tab as a single space
1701                         if (c == '\t')
1702                                 c = ' ';
1703
1704                         if (!(glyph = font->GetGlyphInfo (c)))
1705                                 continue;
1706
1707                         if ((prev != NULL) && APPLY_KERNING (c))
1708                                 x0 += font->Kerning (prev, glyph);
1709                         else if (glyph->metrics.horiBearingX < 0)
1710                                 x0 += glyph->metrics.horiBearingX;
1711
1712                         font->AppendPath (cluster->path, glyph, x0, y0);
1713                         x0 += glyph->metrics.horiAdvance;
1714                         prev = glyph;
1715
1716                         if (!g_unichar_isspace (c))
1717                                 x1 = x0;
1718                 }
1719
1720                 moon_close_path (cluster->path);
1721         }
1722
1723         cluster->uadvance = x1;
1724         cluster->advance = x0;
1725
1726         *pglyph = prev;
1727
1728         return cluster;
1729 }
1730
1731 void
1732 TextLayoutRun::GenerateCache ()
1733 {
1734         int selection_length = line->layout->GetSelectionLength ();
1735         int selection_start = line->layout->GetSelectionStart ();
1736         const char *text = line->layout->GetText ();
1737         const char *inend = text + start + length;
1738         const char *inptr = text + start;
1739         TextFont *font = attrs->Font ();
1740         TextLayoutGlyphCluster *cluster;
1741         const char *selection_end;
1742         GlyphInfo *prev = NULL;
1743         int len;
1744
1745         // cache the glyph cluster leading up to the selection
1746         if (selection_length == 0 || start < selection_start) {
1747                 if (selection_length > 0)
1748                         len = MIN (selection_start - start, length);
1749                 else
1750                         len = length;
1751
1752                 cluster = GenerateGlyphCluster (font, &prev, text, start, len);
1753                 g_ptr_array_add (clusters, cluster);
1754                 inptr += len;
1755         }
1756
1757         // cache the selected glyph cluster
1758         selection_end = text + selection_start + selection_length;
1759         if (inptr < inend && inptr < selection_end) {
1760                 len = MIN (inend, selection_end) - inptr;
1761                 cluster = GenerateGlyphCluster (font, &prev, text, inptr - text, len);
1762                 g_ptr_array_add (clusters, cluster);
1763                 cluster->selected = true;
1764                 inptr += len;
1765         }
1766
1767         // cache the glyph cluster following the selection
1768         if (inptr < inend) {
1769                 cluster = GenerateGlyphCluster (font, &prev, text, inptr - text, inend - inptr);
1770                 g_ptr_array_add (clusters, cluster);
1771                 inptr = inend;
1772         }
1773 }
1774
1775 void
1776 TextLayoutGlyphCluster::Render (cairo_t *cr, const Point &origin, TextLayoutAttributes *attrs, const char *text, double x, double y, bool uline_full)
1777 {
1778         TextFont *font = attrs->Font ();
1779         const char *inend, *prev;
1780         GlyphInfo *glyph;
1781         Brush *brush;
1782         gunichar c;
1783         double y0;
1784         Rect area;
1785
1786         if (length == 0 || advance == 0.0)
1787                 return;
1788
1789         // y is the baseline, set the origin to the top-left
1790         cairo_translate (cr, x, y - font->Ascender ());
1791
1792         // set y0 to the baseline relative to the translation matrix
1793         y0 = font->Ascender ();
1794
1795         if (selected && (brush = attrs->Background (true))) {
1796                 area = Rect (origin.x, origin.y, advance, font->Height ());
1797
1798                 // extend the selection background by the width of a SPACE if it includes CRLF
1799                 inend = text + start + length;
1800                 if ((prev = g_utf8_find_prev_char (text + start, inend)))
1801                         c = utf8_getc (&prev, inend - prev);
1802                 else
1803                         c = (gunichar) -1;
1804
1805                 if (UnicharIsLineBreak (c)) {
1806                         if ((glyph = font->GetGlyphInfo (' ')))
1807                                 area.width += glyph->metrics.horiAdvance;
1808                 }
1809
1810                 // render the selection background
1811                 brush->SetupBrush (cr, area);
1812                 cairo_new_path (cr);
1813                 cairo_rectangle (cr, area.x, area.y, area.width, area.height);
1814                 brush->Fill (cr);
1815         }
1816
1817         // setup the foreground brush
1818         if (!(brush = attrs->Foreground (selected)))
1819                 return;
1820
1821         area = Rect (origin.x, origin.y, advance, font->Height ());
1822         brush->SetupBrush (cr, area);
1823         cairo_new_path (cr);
1824
1825         if (path && path->cairo.data)
1826                 cairo_append_path (cr, &path->cairo);
1827
1828         brush->Fill (cr);
1829
1830         if (attrs->IsUnderlined ()) {
1831                 double thickness = font->UnderlineThickness ();
1832                 double pos = y0 + font->UnderlinePosition ();
1833
1834                 cairo_set_line_width (cr, thickness);
1835
1836                 cairo_new_path (cr);
1837                 Rect underline = Rect (0.0, pos - thickness * 0.5, uline_full ? advance : uadvance, thickness);
1838                 underline.Draw (cr);
1839
1840                 brush->Fill (cr);
1841         }
1842 }
1843
1844 void
1845 TextLayoutRun::Render (cairo_t *cr, const Point &origin, double x, double y, bool is_last_run)
1846 {
1847         const char *text = line->layout->GetText ();
1848         TextLayoutGlyphCluster *cluster;
1849         double x0 = x;
1850
1851         if (clusters->len == 0)
1852                 GenerateCache ();
1853
1854         for (guint i = 0; i < clusters->len; i++) {
1855                 cluster = (TextLayoutGlyphCluster *) clusters->pdata[i];
1856
1857                 cairo_save (cr);
1858                 cluster->Render (cr, origin, attrs, text, x0, y, is_last_run && ((i + 1) < clusters->len));
1859                 cairo_restore (cr);
1860
1861                 x0 += cluster->advance;
1862         }
1863 }
1864
1865 void
1866 TextLayoutLine::Render (cairo_t *cr, const Point &origin, double left, double top)
1867 {
1868         TextLayoutRun *run;
1869         double x0, y0;
1870
1871         // set y0 to the line's baseline (descend is a negative value)
1872         y0 = top + height + descend;
1873         x0 = left;
1874
1875         for (guint i = 0; i < runs->len; i++) {
1876                 run = (TextLayoutRun *) runs->pdata[i];
1877                 run->Render (cr, origin, x0, y0, (i + 1) < runs->len);
1878                 x0 += run->advance;
1879         }
1880 }
1881
1882 static double
1883 GetWidthConstraint (double avail_width, double max_width, double actual_width)
1884 {
1885         if (isinf (avail_width)) {
1886                 // find an upper width constraint
1887                 if (isinf (max_width))
1888                         return actual_width;
1889                 else
1890                         return max_width;
1891         }
1892
1893         return avail_width;
1894 }
1895
1896 double
1897 TextLayout::HorizontalAlignment (double line_width)
1898 {
1899         double deltax;
1900         double width;
1901
1902         switch (alignment) {
1903         case TextAlignmentCenter:
1904                 width = GetWidthConstraint (avail_width, max_width, actual_width);
1905                 if (line_width < width)
1906                         deltax = (width - line_width) / 2.0;
1907                 else
1908                         deltax = 0.0;
1909                 break;
1910         case TextAlignmentRight:
1911                 width = GetWidthConstraint (avail_width, max_width, actual_width);
1912                 if (line_width < width)
1913                         deltax = width - line_width;
1914                 else
1915                         deltax = 0.0;
1916                 break;
1917         default:
1918                 deltax = 0.0;
1919                 break;
1920         }
1921
1922         return deltax;
1923 }
1924
1925 void
1926 TextLayout::Render (cairo_t *cr, const Point &origin, const Point &offset)
1927 {
1928         TextLayoutLine *line;
1929         double x, y;
1930
1931         y = offset.y;
1932
1933         Layout ();
1934
1935         for (guint i = 0; i < lines->len; i++) {
1936                 line = (TextLayoutLine *) lines->pdata[i];
1937
1938                 x = offset.x + HorizontalAlignment (line->advance);
1939                 line->Render (cr, origin, x, y);
1940                 y += line->height;
1941         }
1942 }
1943
1944 #ifdef USE_BINARY_SEARCH
1945 /**
1946  * MID:
1947  * @lo: the low bound
1948  * @hi: the high bound
1949  *
1950  * Finds the midpoint between positive integer values, @lo and @hi.
1951  *
1952  * Notes: Typically expressed as '(@lo + @hi) / 2', this is incorrect
1953  * when @lo and @hi are sufficiently large enough that combining them
1954  * would overflow their integer type. To work around this, we use the
1955  * formula, '@lo + ((@hi - @lo) / 2)', thus preventing this problem
1956  * from occuring.
1957  *
1958  * Returns the midpoint between @lo and @hi (rounded down).
1959  **/
1960 #define MID(lo, hi) (lo + ((hi - lo) >> 1))
1961
1962 TextLayoutLine *
1963 TextLayout::GetLineFromY (const Point &offset, double y, int *index)
1964 {
1965         register guint lo, hi;
1966         TextLayoutLine *line;
1967         double y0;
1968         guint m;
1969
1970         if (lines->len == 0)
1971                 return NULL;
1972
1973         lo = 0, hi = lines->len;
1974         y0 = y - offset.y;
1975
1976         do {
1977                 m = MID (lo, hi);
1978
1979                 line = (TextLayoutLine *) lines->pdata[m];
1980
1981                 if (m > 0 && y0 < line->top) {
1982                         // y is on some line above us
1983                         hi = m;
1984                 } else if (y0 > line->top + line->height) {
1985                         // y is on some line below us
1986                         lo = m + 1;
1987                         m = lo;
1988                 } else {
1989                         // y is on this line
1990                         break;
1991                 }
1992
1993                 line = NULL;
1994         } while (lo < hi);
1995
1996         if (line && index)
1997                 *index = m;
1998
1999         return line;
2000 }
2001 #else /* linear search */
2002 TextLayoutLine *
2003 TextLayout::GetLineFromY (const Point &offset, double y, int *index)
2004 {
2005         TextLayoutLine *line = NULL;
2006         double y0, y1;
2007
2008         //printf ("TextLayout::GetLineFromY (%.2g)\n", y);
2009
2010         y0 = offset.y;
2011
2012         for (guint i = 0; i < lines->len; i++) {
2013                 line = (TextLayoutLine *) lines->pdata[i];
2014
2015                 // set y1 the top of the next line
2016                 y1 = y0 + line->height;
2017
2018                 if (y < y1) {
2019                         // we found the line that the point is located on
2020                         if (index)
2021                                 *index = (int) i;
2022
2023                         return line;
2024                 }
2025
2026                 y0 = y1;
2027         }
2028
2029         return NULL;
2030 }
2031 #endif
2032
2033 TextLayoutLine *
2034 TextLayout::GetLineFromIndex (int index)
2035 {
2036         if (index >= (int) lines->len || index < 0)
2037                 return NULL;
2038
2039         return (TextLayoutLine *) lines->pdata[index];
2040 }
2041
2042 int
2043 TextLayoutLine::GetCursorFromX (const Point &offset, double x)
2044 {
2045         const char *text, *inend, *ch, *inptr;
2046         TextLayoutRun *run = NULL;
2047         GlyphInfo *prev, *glyph;
2048         TextFont *font;
2049         int cursor;
2050         gunichar c;
2051         double x0;
2052         double m;
2053         guint i;
2054
2055         // adjust x0 for horizontal alignment
2056         x0 = offset.x + layout->HorizontalAlignment (advance);
2057
2058         text = layout->GetText ();
2059         inptr = text + start;
2060         cursor = this->offset;
2061         prev = NULL;
2062
2063         for (i = 0; i < runs->len; i++) {
2064                 run = (TextLayoutRun *) runs->pdata[i];
2065
2066                 if (x < x0 + run->advance) {
2067                         // x is in somewhere inside this run
2068                         break;
2069                 }
2070
2071                 // x is beyond this run
2072                 cursor += run->count;
2073                 inptr += run->length;
2074                 x0 += run->advance;
2075                 run = NULL;
2076         }
2077
2078         if (run != NULL) {
2079                 inptr = text + run->start;
2080                 inend = inptr + run->length;
2081                 font = run->attrs->Font ();
2082
2083                 while (inptr < inend) {
2084                         ch = inptr;
2085                         if ((c = utf8_getc (&inptr, inend - inptr)) == (gunichar) -1)
2086                                 continue;
2087
2088                         if (UnicharIsLineBreak (c)) {
2089                                 inptr = ch;
2090                                 break;
2091                         }
2092
2093                         cursor++;
2094
2095                         // we treat tabs as a single space
2096                         if (c == '\t')
2097                                 c = ' ';
2098
2099                         if (!(glyph = font->GetGlyphInfo (c)))
2100                                 continue;
2101
2102                         if ((prev != NULL) && APPLY_KERNING (c))
2103                                 x0 += font->Kerning (prev, glyph);
2104                         else if (glyph->metrics.horiBearingX < 0)
2105                                 x0 += glyph->metrics.horiBearingX;
2106
2107                         // calculate midpoint of the character
2108                         m = glyph->metrics.horiAdvance / 2.0;
2109
2110                         // if x is <= the midpoint, then the cursor is
2111                         // considered to be at the start of this character.
2112                         if (x <= x0 + m) {
2113                                 inptr = ch;
2114                                 cursor--;
2115                                 break;
2116                         }
2117
2118                         x0 += glyph->metrics.horiAdvance;
2119                         prev = glyph;
2120                 }
2121         } else if (i > 0) {
2122                 // x is beyond the end of the last run
2123                 run = (TextLayoutRun *) runs->pdata[i - 1];
2124                 inend = text + run->start + run->length;
2125                 inptr = text + run->start;
2126
2127                 if ((ch = g_utf8_find_prev_char (inptr, inend)))
2128                         c = utf8_getc (&ch, inend - ch);
2129                 else
2130                         c = (gunichar) -1;
2131
2132                 if (c == '\n') {
2133                         cursor--;
2134                         inend--;
2135
2136                         if (inend > inptr && inend[-1] == '\r') {
2137                                 cursor--;
2138                                 inend--;
2139                         }
2140                 } else if (UnicharIsLineBreak (c)) {
2141                         cursor--;
2142                         inend--;
2143                 }
2144         }
2145
2146         return cursor;
2147 }
2148
2149 int
2150 TextLayout::GetCursorFromXY (const Point &offset, double x, double y)
2151 {
2152         TextLayoutLine *line;
2153
2154         //printf ("TextLayout::GetCursorFromXY (%.2g, %.2g)\n", x, y);
2155
2156         if (y < offset.y)
2157                 return 0;
2158
2159         if (!(line = GetLineFromY (offset, y)))
2160                 return count;
2161
2162         return line->GetCursorFromX (offset, x);
2163 }
2164
2165 Rect
2166 TextLayout::GetCursor (const Point &offset, int index)
2167 {
2168         const char *inptr, *inend, *pchar;
2169         double height, x0, y0, y1;
2170         GlyphInfo *prev, *glyph;
2171         TextLayoutLine *line;
2172         TextLayoutRun *run;
2173         TextFont *font;
2174         int cursor = 0;
2175         gunichar c;
2176
2177         //printf ("TextLayout::GetCursor (%d)\n", index);
2178
2179         x0 = offset.x;
2180         y0 = offset.y;
2181         height = 0.0;
2182         y1 = 0.0;
2183
2184         for (guint i = 0; i < lines->len; i++) {
2185                 line = (TextLayoutLine *) lines->pdata[i];
2186                 inend = text + line->start + line->length;
2187
2188                 // adjust x0 for horizontal alignment
2189                 x0 = offset.x + HorizontalAlignment (line->advance);
2190
2191                 // set y1 to the baseline (descend is a negative value)
2192                 y1 = y0 + line->height + line->descend;
2193                 height = line->height;
2194
2195                 //printf ("\tline: left=%.2f, top=%.2f, baseline=%.2f, start index=%d\n", x0, y0, y1, line->offset);
2196
2197                 if (index >= cursor + line->count) {
2198                         // maybe the cursor is on the next line...
2199                         if ((i + 1) == lines->len) {
2200                                 // we are on the last line... get the previous unichar
2201                                 inptr = text + line->start;
2202                                 inend = inptr + line->length;
2203
2204                                 if ((pchar = g_utf8_find_prev_char (text + line->start, inend)))
2205                                         c = utf8_getc (&pchar, inend - pchar);
2206                                 else
2207                                         c = (gunichar) -1;
2208
2209                                 if (UnicharIsLineBreak (c)) {
2210                                         // cursor is on the next line by itself
2211                                         x0 = offset.x + HorizontalAlignment (0.0);
2212                                         y0 += line->height;
2213                                 } else {
2214                                         // cursor at the end of the last line
2215                                         x0 += line->advance;
2216                                 }
2217
2218                                 break;
2219                         }
2220
2221                         cursor += line->count;
2222                         y0 += line->height;
2223                         continue;
2224                 }
2225
2226                 // cursor is on this line...
2227                 for (guint j = 0; j < line->runs->len; j++) {
2228                         run = (TextLayoutRun *) line->runs->pdata[j];
2229                         inend = text + run->start + run->length;
2230
2231                         if (index >= cursor + run->count) {
2232                                 // maybe the cursor is in the next run...
2233                                 cursor += run->count;
2234                                 x0 += run->advance;
2235                                 continue;
2236                         }
2237
2238                         // cursor is in this run...
2239                         font = run->attrs->Font ();
2240                         inptr = text + run->start;
2241                         prev = NULL;
2242
2243                         while (cursor < index) {
2244                                 if ((c = utf8_getc (&inptr, inend - inptr)) == (gunichar) -1)
2245                                         continue;
2246
2247                                 cursor++;
2248
2249                                 // we treat tabs as a single space
2250                                 if (c == '\t')
2251                                         c = ' ';
2252
2253                                 if (!(glyph = font->GetGlyphInfo (c)))
2254                                         continue;
2255
2256                                 if ((prev != NULL) && APPLY_KERNING (c))
2257                                         x0 += font->Kerning (prev, glyph);
2258                                 else if (glyph->metrics.horiBearingX < 0)
2259                                         x0 += glyph->metrics.horiBearingX;
2260
2261                                 x0 += glyph->metrics.horiAdvance;
2262                                 prev = glyph;
2263                         }
2264
2265                         break;
2266                 }
2267
2268                 break;
2269         }
2270
2271         return Rect (x0, y0, 1.0, height);
2272 }