/* Pango
* ellipsize.c: Routine to ellipsize layout lines
*
* Copyright (C) 2004 Red Hat Software
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public
* License along with this library; if not, write to the
* Free Software Foundation, Inc., 59 Temple Place - Suite 330,
* Boston, MA 02111-1307, USA.
*/
#include "config.h"
#include <string.h>
#include "pango-glyph-item.h"
#include "pango-layout-private.h"
#include "pango-engine-private.h"
#include "pango-impl-utils.h"
typedef struct _EllipsizeState EllipsizeState;
typedef struct _RunInfo RunInfo;
typedef struct _LineIter LineIter;
/* Overall, the way we ellipsize is we grow a "gap" out from an original
* gap center position until:
*
* line_width - gap_width + ellipsize_width <= goal_width
*
* Line: [-------------------------------------------]
* Runs: [------)[---------------)[------------------]
* Gap center: *
* Gap: [----------------------]
*
* The gap center may be at the start or end in which case the gap grows
* in only one direction.
*
* Note the line and last run are logically closed at the end; this allows
* us to use a gap position at x=line_width and still have it be part of
* of a run.
*
* We grow the gap out one "span" at a time, where a span is simply a
* consecutive run of clusters that we can't interrupt with an ellipsis.
*
* When choosing whether to grow the gap at the start or the end, we
* calculate the next span to remove in both directions and see which
* causes the smaller increase in:
*
* MAX (gap_end - gap_center, gap_start - gap_center)
*
* All computations are done using logical order; the ellipsization
* process occurs before the runs are ordered into visual order.
*/
/* Keeps information about a single run */
struct _RunInfo
{
PangoGlyphItem *run;
int start_offset; /* Character offset of run start */
int width; /* Width of run in Pango units */
};
/* Iterator to a position within the ellipsized line */
struct _LineIter
{
PangoGlyphItemIter run_iter;
int run_index;
};
/* State of ellipsization process */
struct _EllipsizeState
{
PangoLayout *layout; /* Layout being ellipsized */
PangoAttrList *attrs; /* Attributes used for itemization/shaping */
RunInfo *run_info; /* Array of information about each run */
int n_runs;
int total_width; /* Original width of line in Pango units */
int gap_center; /* Goal for center of gap */
PangoGlyphItem *ellipsis_run; /* Run created to hold ellipsis */
int ellipsis_width; /* Width of ellipsis, in Pango units */
int ellipsis_is_cjk; /* Whether the first character in the ellipsized
* is wide; this triggers us to try to use a
* mid-line ellipsis instead of a baseline
*/
PangoAttrIterator *line_start_attr; /* Cached PangoAttrIterator for the start of the run */
LineIter gap_start_iter; /* Iteratator pointig to the first cluster in gap */
int gap_start_x; /* x position of start of gap, in Pango units */
PangoAttrIterator *gap_start_attr; /* Attribute iterator pointing to a range containing
* the first character in gap */
LineIter gap_end_iter; /* Iterator pointing to last cluster in gap */
int gap_end_x; /* x position of end of gap, in Pango units */
};
/* Compute global information needed for the itemization process
*/
static void
init_state (EllipsizeState *state,
PangoLayoutLine *line,
PangoAttrList *attrs)
{
GSList *l;
int i;
int start_offset;
state->layout = line->layout;
state->attrs = attrs;
state->n_runs = g_slist_length (line->runs);
state->run_info = g_new (RunInfo, state->n_runs);
start_offset = pango_utf8_strlen (line->layout->text,
line->start_index);
state->total_width = 0;
for (l = line->runs, i = 0; l; l = l->next, i++)
{
PangoGlyphItem *run = l->data;
int width = pango_glyph_string_get_width (run->glyphs);
state->run_info[i].run = run;
state->run_info[i].width = width;
state->run_info[i].start_offset = start_offset;
state->total_width += width;
start_offset += run->item->num_chars;
}
state->ellipsis_run = NULL;
state->ellipsis_is_cjk = FALSE;
state->line_start_attr = NULL;
state->gap_start_attr = NULL;
}
/* Cleanup memory allocation
*/
static void
free_state (EllipsizeState *state)
{
if (state->line_start_attr)
pango_attr_iterator_destroy (state->line_start_attr);
if (state->gap_start_attr)
pango_attr_iterator_destroy (state->gap_start_attr);
g_free (state->run_info);
}
/* Computes the width of a single cluster
*/
static int
get_cluster_width (LineIter *iter)
{
PangoGlyphItemIter *run_iter = &iter->run_iter;
PangoGlyphString *glyphs = run_iter->glyph_item->glyphs;
int width = 0;
int i;
if (run_iter->start_glyph < run_iter->end_glyph) /* LTR */
{
for (i = run_iter->start_glyph; i < run_iter->end_glyph; i++)
width += glyphs->glyphs[i].geometry.width;
}
else /* RTL */
{
for (i = run_iter->start_glyph; i > run_iter->end_glyph; i--)
width += glyphs->glyphs[i].geometry.width;
}
return width;
}
/* Move forward one cluster. Returns %FALSE if we were already at the end
*/
static gboolean
line_iter_next_cluster (EllipsizeState *state,
LineIter *iter)
{
if (!pango_glyph_item_iter_next_cluster (&iter->run_iter))
{
if (iter->run_index == state->n_runs - 1)
return FALSE;
else
{
iter->run_index++;
pango_glyph_item_iter_init_start (&iter->run_iter,
state->run_info[iter->run_index].run,
state->layout->text);
}
}
return TRUE;
}
/* Move backward one cluster. Returns %FALSE if we were already at the end
*/
static gboolean
line_iter_prev_cluster (EllipsizeState *state,
LineIter *iter)
{
if (!pango_glyph_item_iter_prev_cluster (&iter->run_iter))
{
if (iter->run_index == 0)
return FALSE;
else
{
iter->run_index--;
pango_glyph_item_iter_init_end (&iter->run_iter,
state->run_info[iter->run_index].run,
state->layout->text);
}
}
return TRUE;
}
/*
* An ellipsization boundary is defined by two things
*
* - Starts a cluster - forced by structure of code
* - Starts a grapheme - checked here
*
* In the future we'd also like to add a check for cursive connectivity here.
* This should be an addition to #PangoGlyphVisAttr
*
*/
/* Checks if there is a ellipsization boundary before the cluster @iter points to
*/
static gboolean
starts_at_ellipsization_boundary (EllipsizeState *state,
LineIter *iter)
{
RunInfo *run_info = &state->run_info[iter->run_index];
if (iter->run_iter.start_char == 0 && iter->run_index == 0)
return TRUE;
return state->layout->log_attrs[run_info->start_offset + iter->run_iter.start_char].is_cursor_position;
}
/* Checks if there is a ellipsization boundary after the cluster @iter points to
*/
static gboolean
ends_at_ellipsization_boundary (EllipsizeState *state,
LineIter *iter)
{
RunInfo *run_info = &state->run_info[iter->run_index];
if (iter->run_iter.end_char == run_info->run->item->num_chars && iter->run_index == state->n_runs - 1)
return TRUE;
return state->layout->log_attrs[run_info->start_offset + iter->run_iter.end_char + 1].is_cursor_position;
}
/* Helper function to re-itemize a string of text
*/
static PangoItem *
itemize_text (EllipsizeState *state,
const char *text,
PangoAttrList *attrs)
{
GList *items;
PangoItem *item;
items = pango_itemize (state->layout->context, text, 0, strlen (text), attrs, NULL);
g_assert (g_list_length (items) == 1);
item = items->data;
g_list_free (items);
return item;
}
/* Shapes the ellipsis using the font and is_cjk information computed by
* update_ellipsis_shape() from the first character in the gap.
*/
static void
shape_ellipsis (EllipsizeState *state)
{
PangoAttrList *attrs = pango_attr_list_new ();
GSList *run_attrs;
PangoItem *item;
PangoGlyphString *glyphs;
GSList *l;
PangoAttribute *fallback;
const char *ellipsis_text;
int i;
/* Create/reset state->ellipsis_run
*/
if (!state->ellipsis_run)
{
state->ellipsis_run = g_slice_new (PangoGlyphItem);
state->ellipsis_run->glyphs = pango_glyph_string_new ();
state->ellipsis_run->item = NULL;
}
if (state->ellipsis_run->item)
{
pango_item_free (state->ellipsis_run->item);
state->ellipsis_run->item = NULL;
}
/* Create an attribute list
*/
run_attrs = pango_attr_iterator_get_attrs (state->gap_start_attr);
for (l = run_attrs; l; l = l->next)
{
PangoAttribute *attr = l->data;
attr->start_index = 0;
attr->end_index = G_MAXINT;
pango_attr_list_insert (attrs, attr);
}
g_slist_free (run_attrs);
fallback = pango_attr_fallback_new (FALSE);
fallback->start_index = 0;
fallback->end_index = G_MAXINT;
pango_attr_list_insert (attrs, fallback);
/* First try using a specific ellipsis character in the best matching font
*/
if (state->ellipsis_is_cjk)
ellipsis_text = "\342\213\257"; /* U+22EF: MIDLINE HORIZONTAL ELLIPSIS, used for CJK */
else
ellipsis_text = "\342\200\246"; /* U+2026: HORIZONTAL ELLIPSIS */
item = itemize_text (state, ellipsis_text, attrs);
/* If that fails we use "..." in the first matching font
*/
if (!item->analysis.font ||
!_pango_engine_shape_covers (item->analysis.shape_engine, item->analysis.font,
item->analysis.language, g_utf8_get_char (ellipsis_text)))
{
pango_item_free (item);
/* Modify the fallback iter while it is inside the PangoAttrList; Don't try this at home
*/
((PangoAttrInt *)fallback)->value = TRUE;
ellipsis_text = "...";
item = itemize_text (state, ellipsis_text, attrs);
}
pango_attr_list_unref (attrs);
state->ellipsis_run->item = item;
/* Now shape
*/
glyphs = state->ellipsis_run->glyphs;
pango_shape (ellipsis_text, strlen (ellipsis_text),
&item->analysis, glyphs);
state->ellipsis_width = 0;
for (i = 0; i < glyphs->num_glyphs; i++)
state->ellipsis_width += glyphs->glyphs[i].geometry.width;
}
/* Helper function to advance a PangoAttrIterator to a particular
* byte index.
*/
static void
advance_iterator_to (PangoAttrIterator *iter,
int new_index)
{
int start, end;
do
{
pango_attr_iterator_range (iter, &start, &end);
if (end > new_index)
break;
}
while (pango_attr_iterator_next (iter));
}
/* Updates the shaping of the ellipsis if necessary when we move the
* position of the start of the gap.
*
* The shaping of the ellipsis is determined by two things:
*
* - The font attributes applied to the first character in the gap
* - Whether the first character in the gap is wide or not. If the
* first character is wide, then we assume that we are ellipsizing
* East-Asian text, so prefer a mid-line ellipsizes to a baseline
* ellipsis, since that's typical practice for Chinese/Japanese/Korean.
*/
static void
update_ellipsis_shape (EllipsizeState *state)
{
gboolean recompute = FALSE;
gunichar start_wc;
gboolean is_cjk;
/* Unfortunately, we can only advance PangoAttrIterator forward; so each
* time we back up we need to go forward to find the new position. To make
* this not utterly slow, we cache an iterator at the start of the line
*/
if (!state->line_start_attr)
{
state->line_start_attr = pango_attr_list_get_iterator (state->attrs);
advance_iterator_to (state->line_start_attr, state->run_info[0].run->item->offset);
}
if (state->gap_start_attr)
{
/* See if the current attribute range contains the new start position
*/
int start, end;
pango_attr_iterator_range (state->gap_start_attr, &start, &end);
if (state->gap_start_iter.run_iter.start_index < start)
{
pango_attr_iterator_destroy (state->gap_start_attr);
state->gap_start_attr = NULL;
}
}
/* Check whether we need to recompute the ellipsis because of new font attributes
*/
if (!state->gap_start_attr)
{
state->gap_start_attr = pango_attr_iterator_copy (state->line_start_attr);
advance_iterator_to (state->gap_start_attr,
state->run_info[state->gap_start_iter.run_index].run->item->offset);
recompute = TRUE;
}
/* Check whether we need to recompute the ellipsis because we switch from CJK to not
* or vice-versa
*/
start_wc = g_utf8_get_char (state->layout->text + state->gap_start_iter.run_iter.start_index);
is_cjk = g_unichar_iswide (start_wc);
if (is_cjk != state->ellipsis_is_cjk)
{
state->ellipsis_is_cjk = is_cjk;
recompute = TRUE;
}
if (recompute)
shape_ellipsis (state);
}
/* Computes the position of the gap center and finds the smallest span containing it
*/
static void
find_initial_span (EllipsizeState *state)
{
PangoGlyphItem *glyph_item;
PangoGlyphItemIter *run_iter;
gboolean have_cluster;
int i;
int x;
int cluster_width;
switch (state->layout->ellipsize)
{
case PANGO_ELLIPSIZE_NONE:
default:
g_assert_not_reached ();
case PANGO_ELLIPSIZE_START:
state->gap_center = 0;
break;
case PANGO_ELLIPSIZE_MIDDLE:
state->gap_center = state->total_width / 2;
break;
case PANGO_ELLIPSIZE_END:
state->gap_center = state->total_width;
break;
}
/* Find the run containing the gap center
*/
x = 0;
for (i = 0; i < state->n_runs; i++)
{
if (x + state->run_info[i].width > state->gap_center)
break;
x += state->run_info[i].width;
}
if (i == state->n_runs) /* Last run is a closed interval, so back off one run */
{
i--;
x -= state->run_info[i].width;
}
/* Find the cluster containing the gap center
*/
state->gap_start_iter.run_index = i;
run_iter = &state->gap_start_iter.run_iter;
glyph_item = state->run_info[i].run;
cluster_width = 0; /* Quiet GCC, the line must have at least one cluster */
for (have_cluster = pango_glyph_item_iter_init_start (run_iter, glyph_item, state->layout->text);
have_cluster;
have_cluster = pango_glyph_item_iter_next_cluster (run_iter))
{
cluster_width = get_cluster_width (&state->gap_start_iter);
if (x + cluster_width > state->gap_center)
break;
x += cluster_width;
}
if (!have_cluster) /* Last cluster is a closed interval, so back off one cluster */
x -= cluster_width;
state->gap_end_iter = state->gap_start_iter;
state->gap_start_x = x;
state->gap_end_x = x + cluster_width;
/* Expand the gap to a full span
*/
while (!starts_at_ellipsization_boundary (state, &state->gap_start_iter))
{
line_iter_prev_cluster (state, &state->gap_start_iter);
state->gap_start_x -= get_cluster_width (&state->gap_start_iter);
}
while (!ends_at_ellipsization_boundary (state, &state->gap_end_iter))
{
line_iter_next_cluster (state, &state->gap_end_iter);
state->gap_end_x += get_cluster_width (&state->gap_end_iter);
}
update_ellipsis_shape (state);
}
/* Removes one run from the start or end of the gap. Returns FALSE
* if there's nothing left to remove in either direction.
*/
static gboolean
remove_one_span (EllipsizeState *state)
{
LineIter new_gap_start_iter;
LineIter new_gap_end_iter;
int new_gap_start_x;
int new_gap_end_x;
int width;
/* Find one span backwards and forward from the gap
*/
new_gap_start_iter = state->gap_start_iter;
new_gap_start_x = state->gap_start_x;
do
{
if (!line_iter_prev_cluster (state, &new_gap_start_iter))
break;
width = get_cluster_width (&new_gap_start_iter);
new_gap_start_x -= width;
}
while (!starts_at_ellipsization_boundary (state, &new_gap_start_iter) ||
width == 0);
new_gap_end_iter = state->gap_end_iter;
new_gap_end_x = state->gap_end_x;
do
{
if (!line_iter_next_cluster (state, &new_gap_end_iter))
break;
width = get_cluster_width (&new_gap_end_iter);
new_gap_end_x += width;
}
while (!ends_at_ellipsization_boundary (state, &new_gap_end_iter) ||
width == 0);
if (state->gap_end_x == new_gap_end_x && state->gap_start_x == new_gap_start_x)
return FALSE;
/* In the case where we could remove a span from either end of the
* gap, we look at which causes the smaller increase in the
* MAX (gap_end - gap_center, gap_start - gap_center)
*/
if (state->gap_end_x == new_gap_end_x ||
(state->gap_start_x != new_gap_start_x &&
state->gap_center - new_gap_start_x < new_gap_end_x - state->gap_center))
{
state->gap_start_iter = new_gap_start_iter;
state->gap_start_x = new_gap_start_x;
update_ellipsis_shape (state);
}
else
{
state->gap_end_iter = new_gap_end_iter;
state->gap_end_x = new_gap_end_x;
}
return TRUE;
}
/* Fixes up the properties of the ellipsis run once we've determined the final extents
* of the gap
*/
static void
fixup_ellipsis_run (EllipsizeState *state)
{
PangoGlyphString *glyphs = state->ellipsis_run->glyphs;
PangoItem *item = state->ellipsis_run->item;
int level;
int i;
/* Make the entire glyphstring into a single logical cluster */
for (i = 0; i < glyphs->num_glyphs; i++)
{
glyphs->log_clusters[i] = 0;
glyphs->glyphs[i].attr.is_cluster_start = FALSE;
}
glyphs->glyphs[0].attr.is_cluster_start = TRUE;
/* Fix up the item to point to the entire elided text */
item->offset = state->gap_start_iter.run_iter.start_index;
item->length = state->gap_end_iter.run_iter.end_index - item->offset;
item->num_chars = pango_utf8_strlen (state->layout->text + item->offset, item->length);
/* The level for the item is the minimum level of the elided text */
level = G_MAXINT;
for (i = state->gap_start_iter.run_index; i <= state->gap_end_iter.run_index; i++)
level = MIN (level, state->run_info[i].run->item->analysis.level);
item->analysis.level = level;
item->analysis.flags |= PANGO_ANALYSIS_FLAG_IS_ELLIPSIS;
}
/* Computes the new list of runs for the line
*/
static GSList *
get_run_list (EllipsizeState *state)
{
PangoGlyphItem *partial_start_run = NULL;
PangoGlyphItem *partial_end_run = NULL;
GSList *result = NULL;
RunInfo *run_info;
PangoGlyphItemIter *run_iter;
int i;
/* We first cut out the pieces of the starting and ending runs we want to
* preserve; we do the end first in case the end and the start are
* the same. Doing the start first would disturb the indices for the end.
*/
run_info = &state->run_info[state->gap_end_iter.run_index];
run_iter = &state->gap_end_iter.run_iter;
if (run_iter->end_char != run_info->run->item->num_chars)
{
partial_end_run = run_info->run;
run_info->run = pango_glyph_item_split (run_info->run, state->layout->text,
run_iter->end_index - run_info->run->item->offset);
}
run_info = &state->run_info[state->gap_start_iter.run_index];
run_iter = &state->gap_start_iter.run_iter;
if (run_iter->start_char != 0)
{
partial_start_run = pango_glyph_item_split (run_info->run, state->layout->text,
run_iter->start_index - run_info->run->item->offset);
}
/* Now assemble the new list of runs
*/
for (i = 0; i < state->gap_start_iter.run_index; i++)
result = g_slist_prepend (result, state->run_info[i].run);
if (partial_start_run)
result = g_slist_prepend (result, partial_start_run);
result = g_slist_prepend (result, state->ellipsis_run);
if (partial_end_run)
result = g_slist_prepend (result, partial_end_run);
for (i = state->gap_end_iter.run_index + 1; i < state->n_runs; i++)
result = g_slist_prepend (result, state->run_info[i].run);
/* And free the ones we didn't use
*/
for (i = state->gap_start_iter.run_index; i <= state->gap_end_iter.run_index; i++)
pango_glyph_item_free (state->run_info[i].run);
return g_slist_reverse (result);
}
/* Computes the width of the line as currently ellipsized
*/
static int
current_width (EllipsizeState *state)
{
return state->total_width - (state->gap_end_x - state->gap_start_x) + state->ellipsis_width;
}
/**
* _pango_layout_line_ellipsize:
* @line: a #PangoLayoutLine
* @attrs: Attributes being used for itemization/shaping
*
* Given a #PangoLayoutLine with the runs still in logical order, ellipsize
* it according the layout's policy to fit within the set width of the layout.
*
* Return value: whether the line had to be ellipsized
**/
gboolean
_pango_layout_line_ellipsize (PangoLayoutLine *line,
PangoAttrList *attrs,
int goal_width)
{
EllipsizeState state;
gboolean is_ellipsized = FALSE;
g_return_val_if_fail (line->layout->ellipsize != PANGO_ELLIPSIZE_NONE && goal_width >= 0, is_ellipsized);
init_state (&state, line, attrs);
if (state.total_width <= goal_width)
goto out;
find_initial_span (&state);
while (current_width (&state) > goal_width)
{
if (!remove_one_span (&state))
break;
}
fixup_ellipsis_run (&state);
g_slist_free (line->runs);
line->runs = get_run_list (&state);
is_ellipsized = TRUE;
out:
free_state (&state);
return is_ellipsized;
}