pango/ellipsize.c

   1 /* Pango
   2  * ellipsize.c: Routine to ellipsize layout lines
   3  *
   4  * Copyright (C) 2004 Red Hat Software
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Library General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Library General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Library General Public
  17  * License along with this library; if not, write to the
  18  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19  * Boston, MA 02111-1307, USA.
  20  */
  21
  22 #include "config.h"
  23 #include <string.h>
  24
  25 #include "pango-glyph-item.h"
  26 #include "pango-layout-private.h"
  27 #include "pango-engine-private.h"
  28 #include "pango-impl-utils.h"
  29
  30 typedef struct _EllipsizeState EllipsizeState;
  31 typedef struct _RunInfo        RunInfo;
  32 typedef struct _LineIter       LineIter;
  33
  34
  35 /* Overall, the way we ellipsize is we grow a "gap" out from an original
  36  * gap center position until:
  37  *
  38  *  line_width - gap_width + ellipsize_width <= goal_width
  39  *
  40  * Line:  [-------------------------------------------]
  41  * Runs:  [------)[---------------)[------------------]
  42  * Gap center:                 *
  43  * Gap:             [----------------------]
  44  *
  45  * The gap center may be at the start or end in which case the gap grows
  46  * in only one direction.
  47  *
  48  * Note the line and last run are logically closed at the end; this allows
  49  * us to use a gap position at x=line_width and still have it be part of
  50  * of a run.
  51  *
  52  * We grow the gap out one "span" at a time, where a span is simply a
  53  * consecutive run of clusters that we can't interrupt with an ellipsis.
  54  *
  55  * When choosing whether to grow the gap at the start or the end, we
  56  * calculate the next span to remove in both directions and see which
  57  * causes the smaller increase in:
  58  *
  59  *  MAX (gap_end - gap_center, gap_start - gap_center)
  60  *
  61  * All computations are done using logical order; the ellipsization
  62  * process occurs before the runs are ordered into visual order.
  63  */
  64
  65 /* Keeps information about a single run */
  66 struct _RunInfo
  67 {
  68   PangoGlyphItem *run;
  69   int start_offset;             /* Character offset of run start */
  70   int width;                    /* Width of run in Pango units */
  71 };
  72
  73 /* Iterator to a position within the ellipsized line */
  74 struct _LineIter
  75 {
  76   PangoGlyphItemIter run_iter;
  77   int run_index;
  78 };
  79
  80 /* State of ellipsization process */
  81 struct _EllipsizeState
  82 {
  83   PangoLayout *layout;          /* Layout being ellipsized */
  84   PangoAttrList *attrs;         /* Attributes used for itemization/shaping */
  85
  86   RunInfo *run_info;            /* Array of information about each run */
  87   int n_runs;
  88
  89   int total_width;              /* Original width of line in Pango units */
  90   int gap_center;               /* Goal for center of gap */
  91
  92   PangoGlyphItem *ellipsis_run; /* Run created to hold ellipsis */
  93   int ellipsis_width;           /* Width of ellipsis, in Pango units */
  94   int ellipsis_is_cjk;          /* Whether the first character in the ellipsized
  95                                  * is wide; this triggers us to try to use a
  96                                  * mid-line ellipsis instead of a baseline
  97                                  */
  98
  99   PangoAttrIterator *line_start_attr; /* Cached PangoAttrIterator for the start of the run */
 100
 101   LineIter gap_start_iter;      /* Iteratator pointig to the first cluster in gap */
 102   int gap_start_x;              /* x position of start of gap, in Pango units */
 103   PangoAttrIterator *gap_start_attr; /* Attribute iterator pointing to a range containing
 104                                       * the first character in gap */
 105
 106   LineIter gap_end_iter;        /* Iterator pointing to last cluster in gap */
 107   int gap_end_x;                /* x position of end of gap, in Pango units */
 108 };
 109
 110 /* Compute global information needed for the itemization process
 111  */
 112 static void
 113 init_state (EllipsizeState  *state,
 114             PangoLayoutLine *line,
 115             PangoAttrList   *attrs)
 116 {
 117   GSList *l;
 118   int i;
 119   int start_offset;
 120
 121   state->layout = line->layout;
 122   state->attrs = attrs;
 123
 124   state->n_runs = g_slist_length (line->runs);
 125   state->run_info = g_new (RunInfo, state->n_runs);
 126
 127   start_offset = pango_utf8_strlen (line->layout->text,
 128                                 line->start_index);
 129
 130   state->total_width = 0;
 131   for (l = line->runs, i = 0; l; l = l->next, i++)
 132     {
 133       PangoGlyphItem *run = l->data;
 134       int width = pango_glyph_string_get_width (run->glyphs);
 135       state->run_info[i].run = run;
 136       state->run_info[i].width = width;
 137       state->run_info[i].start_offset = start_offset;
 138       state->total_width += width;
 139
 140       start_offset += run->item->num_chars;
 141     }
 142
 143   state->ellipsis_run = NULL;
 144   state->ellipsis_is_cjk = FALSE;
 145   state->line_start_attr = NULL;
 146   state->gap_start_attr = NULL;
 147 }
 148
 149 /* Cleanup memory allocation
 150  */
 151 static void
 152 free_state (EllipsizeState *state)
 153 {
 154   if (state->line_start_attr)
 155     pango_attr_iterator_destroy (state->line_start_attr);
 156   if (state->gap_start_attr)
 157     pango_attr_iterator_destroy (state->gap_start_attr);
 158   g_free (state->run_info);
 159 }
 160
 161 /* Computes the width of a single cluster
 162  */
 163 static int
 164 get_cluster_width (LineIter *iter)
 165 {
 166   PangoGlyphItemIter *run_iter = &iter->run_iter;
 167   PangoGlyphString *glyphs = run_iter->glyph_item->glyphs;
 168   int width = 0;
 169   int i;
 170
 171   if (run_iter->start_glyph < run_iter->end_glyph) /* LTR */
 172     {
 173       for (i = run_iter->start_glyph; i < run_iter->end_glyph; i++)
 174         width += glyphs->glyphs[i].geometry.width;
 175     }
 176   else                                   /* RTL */
 177     {
 178       for (i = run_iter->start_glyph; i > run_iter->end_glyph; i--)
 179         width += glyphs->glyphs[i].geometry.width;
 180     }
 181
 182   return width;
 183 }
 184
 185 /* Move forward one cluster. Returns %FALSE if we were already at the end
 186  */
 187 static gboolean
 188 line_iter_next_cluster (EllipsizeState *state,
 189                         LineIter       *iter)
 190 {
 191   if (!pango_glyph_item_iter_next_cluster (&iter->run_iter))
 192     {
 193       if (iter->run_index == state->n_runs - 1)
 194         return FALSE;
 195       else
 196         {
 197           iter->run_index++;
 198           pango_glyph_item_iter_init_start (&iter->run_iter,
 199                                             state->run_info[iter->run_index].run,
 200                                             state->layout->text);
 201         }
 202     }
 203
 204   return TRUE;
 205 }
 206
 207 /* Move backward one cluster. Returns %FALSE if we were already at the end
 208  */
 209 static gboolean
 210 line_iter_prev_cluster (EllipsizeState *state,
 211                         LineIter       *iter)
 212 {
 213   if (!pango_glyph_item_iter_prev_cluster (&iter->run_iter))
 214     {
 215       if (iter->run_index == 0)
 216         return FALSE;
 217       else
 218         {
 219           iter->run_index--;
 220           pango_glyph_item_iter_init_end (&iter->run_iter,
 221                                           state->run_info[iter->run_index].run,
 222                                           state->layout->text);
 223         }
 224     }
 225
 226   return TRUE;
 227 }
 228
 229 /*
 230  * An ellipsization boundary is defined by two things
 231  *
 232  * - Starts a cluster - forced by structure of code
 233  * - Starts a grapheme - checked here
 234  *
 235  * In the future we'd also like to add a check for cursive connectivity here.
 236  * This should be an addition to #PangoGlyphVisAttr
 237  *
 238  */
 239
 240 /* Checks if there is a ellipsization boundary before the cluster @iter points to
 241  */
 242 static gboolean
 243 starts_at_ellipsization_boundary (EllipsizeState *state,
 244                                   LineIter       *iter)
 245 {
 246   RunInfo *run_info = &state->run_info[iter->run_index];
 247
 248   if (iter->run_iter.start_char == 0 && iter->run_index == 0)
 249     return TRUE;
 250
 251   return state->layout->log_attrs[run_info->start_offset + iter->run_iter.start_char].is_cursor_position;
 252 }
 253
 254 /* Checks if there is a ellipsization boundary after the cluster @iter points to
 255  */
 256 static gboolean
 257 ends_at_ellipsization_boundary (EllipsizeState *state,
 258                                 LineIter       *iter)
 259 {
 260   RunInfo *run_info = &state->run_info[iter->run_index];
 261
 262   if (iter->run_iter.end_char == run_info->run->item->num_chars && iter->run_index == state->n_runs - 1)
 263     return TRUE;
 264
 265   return state->layout->log_attrs[run_info->start_offset + iter->run_iter.end_char + 1].is_cursor_position;
 266 }
 267
 268 /* Helper function to re-itemize a string of text
 269  */
 270 static PangoItem *
 271 itemize_text (EllipsizeState *state,
 272               const char     *text,
 273               PangoAttrList  *attrs)
 274 {
 275   GList *items;
 276   PangoItem *item;
 277
 278   items = pango_itemize (state->layout->context, text, 0, strlen (text), attrs, NULL);
 279   g_assert (g_list_length (items) == 1);
 280
 281   item = items->data;
 282   g_list_free (items);
 283
 284   return item;
 285 }
 286
 287 /* Shapes the ellipsis using the font and is_cjk information computed by
 288  * update_ellipsis_shape() from the first character in the gap.
 289  */
 290 static void
 291 shape_ellipsis (EllipsizeState *state)
 292 {
 293   PangoAttrList *attrs = pango_attr_list_new ();
 294   GSList *run_attrs;
 295   PangoItem *item;
 296   PangoGlyphString *glyphs;
 297   GSList *l;
 298   PangoAttribute *fallback;
 299   const char *ellipsis_text;
 300   int i;
 301
 302   /* Create/reset state->ellipsis_run
 303    */
 304   if (!state->ellipsis_run)
 305     {
 306       state->ellipsis_run = g_slice_new (PangoGlyphItem);
 307       state->ellipsis_run->glyphs = pango_glyph_string_new ();
 308       state->ellipsis_run->item = NULL;
 309     }
 310
 311   if (state->ellipsis_run->item)
 312     {
 313       pango_item_free (state->ellipsis_run->item);
 314       state->ellipsis_run->item = NULL;
 315     }
 316
 317   /* Create an attribute list
 318    */
 319   run_attrs = pango_attr_iterator_get_attrs (state->gap_start_attr);
 320   for (l = run_attrs; l; l = l->next)
 321     {
 322       PangoAttribute *attr = l->data;
 323       attr->start_index = 0;
 324       attr->end_index = G_MAXINT;
 325
 326       pango_attr_list_insert (attrs, attr);
 327     }
 328
 329   g_slist_free (run_attrs);
 330
 331   fallback = pango_attr_fallback_new (FALSE);
 332   fallback->start_index = 0;
 333   fallback->end_index = G_MAXINT;
 334   pango_attr_list_insert (attrs, fallback);
 335
 336   /* First try using a specific ellipsis character in the best matching font
 337    */
 338   if (state->ellipsis_is_cjk)
 339     ellipsis_text = "\342\213\257";     /* U+22EF: MIDLINE HORIZONTAL ELLIPSIS, used for CJK */
 340   else
 341     ellipsis_text = "\342\200\246";     /* U+2026: HORIZONTAL ELLIPSIS */
 342
 343   item = itemize_text (state, ellipsis_text, attrs);
 344
 345   /* If that fails we use "..." in the first matching font
 346    */
 347   if (!item->analysis.font ||
 348       !_pango_engine_shape_covers (item->analysis.shape_engine, item->analysis.font,
 349                                    item->analysis.language, g_utf8_get_char (ellipsis_text)))
 350     {
 351       pango_item_free (item);
 352
 353       /* Modify the fallback iter while it is inside the PangoAttrList; Don't try this at home
 354        */
 355       ((PangoAttrInt *)fallback)->value = TRUE;
 356
 357       ellipsis_text = "...";
 358       item = itemize_text (state, ellipsis_text, attrs);
 359     }
 360
 361   pango_attr_list_unref (attrs);
 362
 363   state->ellipsis_run->item = item;
 364
 365   /* Now shape
 366    */
 367   glyphs = state->ellipsis_run->glyphs;
 368
 369   pango_shape (ellipsis_text, strlen (ellipsis_text),
 370                &item->analysis, glyphs);
 371
 372   state->ellipsis_width = 0;
 373   for (i = 0; i < glyphs->num_glyphs; i++)
 374     state->ellipsis_width += glyphs->glyphs[i].geometry.width;
 375 }
 376
 377 /* Helper function to advance a PangoAttrIterator to a particular
 378  * byte index.
 379  */
 380 static void
 381 advance_iterator_to (PangoAttrIterator *iter,
 382                      int                new_index)
 383 {
 384   int start, end;
 385
 386   do
 387     {
 388       pango_attr_iterator_range (iter, &start, &end);
 389       if (end > new_index)
 390         break;
 391     }
 392   while (pango_attr_iterator_next (iter));
 393 }
 394
 395 /* Updates the shaping of the ellipsis if necessary when we move the
 396  * position of the start of the gap.
 397  *
 398  * The shaping of the ellipsis is determined by two things:
 399  *
 400  * - The font attributes applied to the first character in the gap
 401  * - Whether the first character in the gap is wide or not. If the
 402  *   first character is wide, then we assume that we are ellipsizing
 403  *   East-Asian text, so prefer a mid-line ellipsizes to a baseline
 404  *   ellipsis, since that's typical practice for Chinese/Japanese/Korean.
 405  */
 406 static void
 407 update_ellipsis_shape (EllipsizeState *state)
 408 {
 409   gboolean recompute = FALSE;
 410   gunichar start_wc;
 411   gboolean is_cjk;
 412
 413   /* Unfortunately, we can only advance PangoAttrIterator forward; so each
 414    * time we back up we need to go forward to find the new position. To make
 415    * this not utterly slow, we cache an iterator at the start of the line
 416    */
 417   if (!state->line_start_attr)
 418     {
 419       state->line_start_attr = pango_attr_list_get_iterator (state->attrs);
 420       advance_iterator_to (state->line_start_attr, state->run_info[0].run->item->offset);
 421     }
 422
 423   if (state->gap_start_attr)
 424     {
 425       /* See if the current attribute range contains the new start position
 426        */
 427       int start, end;
 428
 429       pango_attr_iterator_range (state->gap_start_attr, &start, &end);
 430
 431       if (state->gap_start_iter.run_iter.start_index < start)
 432         {
 433           pango_attr_iterator_destroy (state->gap_start_attr);
 434           state->gap_start_attr = NULL;
 435         }
 436     }
 437
 438   /* Check whether we need to recompute the ellipsis because of new font attributes
 439    */
 440   if (!state->gap_start_attr)
 441     {
 442       state->gap_start_attr = pango_attr_iterator_copy (state->line_start_attr);
 443       advance_iterator_to (state->gap_start_attr,
 444                            state->run_info[state->gap_start_iter.run_index].run->item->offset);
 445
 446       recompute = TRUE;
 447     }
 448
 449   /* Check whether we need to recompute the ellipsis because we switch from CJK to not
 450    * or vice-versa
 451    */
 452   start_wc = g_utf8_get_char (state->layout->text + state->gap_start_iter.run_iter.start_index);
 453   is_cjk = g_unichar_iswide (start_wc);
 454
 455   if (is_cjk != state->ellipsis_is_cjk)
 456     {
 457       state->ellipsis_is_cjk = is_cjk;
 458       recompute = TRUE;
 459     }
 460
 461   if (recompute)
 462     shape_ellipsis (state);
 463 }
 464
 465 /* Computes the position of the gap center and finds the smallest span containing it
 466  */
 467 static void
 468 find_initial_span (EllipsizeState *state)
 469 {
 470   PangoGlyphItem *glyph_item;
 471   PangoGlyphItemIter *run_iter;
 472   gboolean have_cluster;
 473   int i;
 474   int x;
 475   int cluster_width;
 476
 477   switch (state->layout->ellipsize)
 478     {
 479     case PANGO_ELLIPSIZE_NONE:
 480     default:
 481       g_assert_not_reached ();
 482     case PANGO_ELLIPSIZE_START:
 483       state->gap_center = 0;
 484       break;
 485     case PANGO_ELLIPSIZE_MIDDLE:
 486       state->gap_center = state->total_width / 2;
 487       break;
 488     case PANGO_ELLIPSIZE_END:
 489       state->gap_center = state->total_width;
 490       break;
 491     }
 492
 493   /* Find the run containing the gap center
 494    */
 495   x = 0;
 496   for (i = 0; i < state->n_runs; i++)
 497     {
 498       if (x + state->run_info[i].width > state->gap_center)
 499         break;
 500
 501       x += state->run_info[i].width;
 502     }
 503
 504   if (i == state->n_runs)       /* Last run is a closed interval, so back off one run */
 505     {
 506       i--;
 507       x -= state->run_info[i].width;
 508     }
 509
 510   /* Find the cluster containing the gap center
 511    */
 512   state->gap_start_iter.run_index = i;
 513   run_iter = &state->gap_start_iter.run_iter;
 514   glyph_item = state->run_info[i].run;
 515
 516   cluster_width = 0;            /* Quiet GCC, the line must have at least one cluster */
 517   for (have_cluster = pango_glyph_item_iter_init_start (run_iter, glyph_item, state->layout->text);
 518        have_cluster;
 519        have_cluster = pango_glyph_item_iter_next_cluster (run_iter))
 520     {
 521       cluster_width = get_cluster_width (&state->gap_start_iter);
 522
 523       if (x + cluster_width > state->gap_center)
 524         break;
 525
 526       x += cluster_width;
 527     }
 528
 529   if (!have_cluster)    /* Last cluster is a closed interval, so back off one cluster */
 530     x -= cluster_width;
 531
 532   state->gap_end_iter = state->gap_start_iter;
 533
 534   state->gap_start_x = x;
 535   state->gap_end_x = x + cluster_width;
 536
 537   /* Expand the gap to a full span
 538    */
 539   while (!starts_at_ellipsization_boundary (state, &state->gap_start_iter))
 540     {
 541       line_iter_prev_cluster (state, &state->gap_start_iter);
 542       state->gap_start_x -= get_cluster_width (&state->gap_start_iter);
 543     }
 544
 545   while (!ends_at_ellipsization_boundary (state, &state->gap_end_iter))
 546     {
 547       line_iter_next_cluster (state, &state->gap_end_iter);
 548       state->gap_end_x += get_cluster_width (&state->gap_end_iter);
 549     }
 550
 551   update_ellipsis_shape (state);
 552 }
 553
 554 /* Removes one run from the start or end of the gap. Returns FALSE
 555  * if there's nothing left to remove in either direction.
 556  */
 557 static gboolean
 558 remove_one_span (EllipsizeState *state)
 559 {
 560   LineIter new_gap_start_iter;
 561   LineIter new_gap_end_iter;
 562   int new_gap_start_x;
 563   int new_gap_end_x;
 564   int width;
 565
 566   /* Find one span backwards and forward from the gap
 567    */
 568   new_gap_start_iter = state->gap_start_iter;
 569   new_gap_start_x = state->gap_start_x;
 570   do
 571     {
 572       if (!line_iter_prev_cluster (state, &new_gap_start_iter))
 573         break;
 574       width = get_cluster_width (&new_gap_start_iter);
 575       new_gap_start_x -= width;
 576     }
 577   while (!starts_at_ellipsization_boundary (state, &new_gap_start_iter) ||
 578          width == 0);
 579
 580   new_gap_end_iter = state->gap_end_iter;
 581   new_gap_end_x = state->gap_end_x;
 582   do
 583     {
 584       if (!line_iter_next_cluster (state, &new_gap_end_iter))
 585         break;
 586       width = get_cluster_width (&new_gap_end_iter);
 587       new_gap_end_x += width;
 588     }
 589   while (!ends_at_ellipsization_boundary (state, &new_gap_end_iter) ||
 590          width == 0);
 591
 592   if (state->gap_end_x == new_gap_end_x && state->gap_start_x == new_gap_start_x)
 593     return FALSE;
 594
 595   /* In the case where we could remove a span from either end of the
 596    * gap, we look at which causes the smaller increase in the
 597    * MAX (gap_end - gap_center, gap_start - gap_center)
 598    */
 599   if (state->gap_end_x == new_gap_end_x ||
 600       (state->gap_start_x != new_gap_start_x &&
 601        state->gap_center - new_gap_start_x < new_gap_end_x - state->gap_center))
 602     {
 603       state->gap_start_iter = new_gap_start_iter;
 604       state->gap_start_x = new_gap_start_x;
 605
 606       update_ellipsis_shape (state);
 607     }
 608   else
 609     {
 610       state->gap_end_iter = new_gap_end_iter;
 611       state->gap_end_x = new_gap_end_x;
 612     }
 613
 614   return TRUE;
 615 }
 616
 617 /* Fixes up the properties of the ellipsis run once we've determined the final extents
 618  * of the gap
 619  */
 620 static void
 621 fixup_ellipsis_run (EllipsizeState *state)
 622 {
 623   PangoGlyphString *glyphs = state->ellipsis_run->glyphs;
 624   PangoItem *item = state->ellipsis_run->item;
 625   int level;
 626   int i;
 627
 628   /* Make the entire glyphstring into a single logical cluster */
 629   for (i = 0; i < glyphs->num_glyphs; i++)
 630     {
 631       glyphs->log_clusters[i] = 0;
 632       glyphs->glyphs[i].attr.is_cluster_start = FALSE;
 633     }
 634
 635   glyphs->glyphs[0].attr.is_cluster_start = TRUE;
 636
 637   /* Fix up the item to point to the entire elided text */
 638   item->offset = state->gap_start_iter.run_iter.start_index;
 639   item->length = state->gap_end_iter.run_iter.end_index - item->offset;
 640   item->num_chars = pango_utf8_strlen (state->layout->text + item->offset, item->length);
 641
 642   /* The level for the item is the minimum level of the elided text */
 643   level = G_MAXINT;
 644   for (i = state->gap_start_iter.run_index; i <= state->gap_end_iter.run_index; i++)
 645     level = MIN (level, state->run_info[i].run->item->analysis.level);
 646
 647   item->analysis.level = level;
 648 }
 649
 650 /* Computes the new list of runs for the line
 651  */
 652 static GSList *
 653 get_run_list (EllipsizeState *state)
 654 {
 655   PangoGlyphItem *partial_start_run = NULL;
 656   PangoGlyphItem *partial_end_run = NULL;
 657   GSList *result = NULL;
 658   RunInfo *run_info;
 659   PangoGlyphItemIter *run_iter;
 660   int i;
 661
 662   /* We first cut out the pieces of the starting and ending runs we want to
 663    * preserve; we do the end first in case the end and the start are
 664    * the same. Doing the start first would disturb the indices for the end.
 665    */
 666   run_info = &state->run_info[state->gap_end_iter.run_index];
 667   run_iter = &state->gap_end_iter.run_iter;
 668   if (run_iter->end_char != run_info->run->item->num_chars)
 669     {
 670       partial_end_run = run_info->run;
 671       run_info->run = pango_glyph_item_split (run_info->run, state->layout->text,
 672                                               run_iter->end_index - run_info->run->item->offset);
 673     }
 674
 675   run_info = &state->run_info[state->gap_start_iter.run_index];
 676   run_iter = &state->gap_start_iter.run_iter;
 677   if (run_iter->start_char != 0)
 678     {
 679       partial_start_run = pango_glyph_item_split (run_info->run, state->layout->text,
 680                                                   run_iter->start_index - run_info->run->item->offset);
 681     }
 682
 683   /* Now assemble the new list of runs
 684    */
 685   for (i = 0; i < state->gap_start_iter.run_index; i++)
 686     result = g_slist_prepend (result, state->run_info[i].run);
 687
 688   if (partial_start_run)
 689     result = g_slist_prepend (result, partial_start_run);
 690
 691   result = g_slist_prepend (result, state->ellipsis_run);
 692
 693   if (partial_end_run)
 694     result = g_slist_prepend (result, partial_end_run);
 695
 696   for (i = state->gap_end_iter.run_index + 1; i < state->n_runs; i++)
 697     result = g_slist_prepend (result, state->run_info[i].run);
 698
 699   /* And free the ones we didn't use
 700    */
 701   for (i = state->gap_start_iter.run_index; i <= state->gap_end_iter.run_index; i++)
 702     pango_glyph_item_free (state->run_info[i].run);
 703
 704   return g_slist_reverse (result);
 705 }
 706
 707 /* Computes the width of the line as currently ellipsized
 708  */
 709 static int
 710 current_width (EllipsizeState *state)
 711 {
 712   return state->total_width - (state->gap_end_x - state->gap_start_x) + state->ellipsis_width;
 713 }
 714
 715 /**
 716  * _pango_layout_line_ellipsize:
 717  * @line: a #PangoLayoutLine
 718  * @attrs: Attributes being used for itemization/shaping
 719  *
 720  * Given a #PangoLayoutLine with the runs still in logical order, ellipsize
 721  * it according the layout's policy to fit within the set width of the layout.
 722  *
 723  * Return value: whether the line had to be ellipsized
 724  **/
 725 gboolean
 726 _pango_layout_line_ellipsize (PangoLayoutLine *line,
 727                               PangoAttrList   *attrs,
 728                               int              goal_width)
 729 {
 730   EllipsizeState state;
 731   gboolean is_ellipsized = FALSE;
 732
 733   g_return_val_if_fail (line->layout->ellipsize != PANGO_ELLIPSIZE_NONE && goal_width >= 0, is_ellipsized);
 734
 735   init_state (&state, line, attrs);
 736
 737   if (state.total_width <= goal_width)
 738     goto out;
 739
 740   find_initial_span (&state);
 741
 742   while (current_width (&state) > goal_width)
 743     {
 744       if (!remove_one_span (&state))
 745         break;
 746     }
 747
 748   fixup_ellipsis_run (&state);
 749
 750   g_slist_free (line->runs);
 751   line->runs = get_run_list (&state);
 752   is_ellipsized = TRUE;
 753
 754  out:
 755   free_state (&state);
 756
 757   return is_ellipsized;
 758 }