Index: pango/Makefile.am
===================================================================
RCS file: /cvs/gnome/pango/pango/Makefile.am,v
retrieving revision 1.140
diff -u -p -r1.140 Makefile.am
--- pango/Makefile.am	15 May 2006 17:55:30 -0000	1.140
+++ pango/Makefile.am	16 May 2006 20:39:12 -0000
@@ -81,6 +81,7 @@ libpango_1_0_la_SOURCES =			\
 	pango-impl-utils.h			\
 	pango-item.c				\
 	pango-layout.c				\
+	pango-layout-engine.c			\
 	pango-layout-private.h			\
 	pango-markup.c				\
 	pango-matrix.c				\
Index: pango/break.c
===================================================================
RCS file: /cvs/gnome/pango/pango/break.c,v
retrieving revision 1.42
diff -u -p -r1.42 break.c
--- pango/break.c	11 Apr 2006 08:31:43 -0000	1.42
+++ pango/break.c	16 May 2006 20:39:13 -0000
@@ -451,6 +451,22 @@ static const CharJamoProps HangulJamoPro
 #define HANGUL(wc) ((wc) >= 0xAC00 && (wc) <= 0xD7A3)
 #define BACKSPACE_DELETES_CHARACTER(wc) (!LATIN (wc) && !CYRILLIC (wc) && !GREEK (wc) && !KANA(wc) && !HANGUL(wc))
 
+/* Unicode Section 6.1 says the fixed width spaces U+2000-U+200A do not expand
+ * on justification (U+2009 THIN SPACE does sometimes, but not here!).
+ * FIXME: U+1361 ETHIOPIC WORDSPACE is like a ':' between words and expands
+ * when justified, but is not elided at ends of lines, so would need slight
+ * changes to the calculations, as half the space would be trimmed (#138223).
+ * FIXME: U+1680 OGHAM SPACE MARK is rendered as a glyph between words, but
+ * is elided at ends of lines (Unicode TR14). Should it expand? Note that it
+ * is only a historic script so not too important.
+ * FIXME: U+200B ZERO WIDTH SPACE may expand when letter-spacing Thai (S 13.2).
+ *
+ * U+0020 is SPACE, the normal ASCII space character, ' '.
+ * U+00A0 is NO-BREAK SPACE.
+ * U+3000 is IDEOGRAPHIC SPACE.
+ */
+#define IS_RESIZABLE(wc)	\
+	((wc) == 0x0020 || (wc) == 0x00A0 || (wc) == 0x3000)
 
 /* p. 132-133 of Unicode spec table 5-6 will help understand this */
 typedef enum
@@ -627,6 +643,7 @@ pango_default_break (const gchar   *text
        */
       attrs[i].is_white = g_unichar_isspace (wc);
 
+      attrs[i].is_resizable = IS_RESIZABLE (wc);
 
       /* ---- Cursor position breaks (Grapheme breaks) ---- */
 
Index: pango/pango-break.h
===================================================================
RCS file: /cvs/gnome/pango/pango/pango-break.h,v
retrieving revision 1.6
diff -u -p -r1.6 pango-break.h
--- pango/pango-break.h	14 Aug 2003 16:33:36 -0000	1.6
+++ pango/pango-break.h	16 May 2006 20:39:13 -0000
@@ -69,6 +69,11 @@ struct _PangoLogAttr
    * the entire grapheme cluster
    */
   guint backspace_deletes_character : 1;
+
+  /* If the character can be stretched and shrunk for justification, typically
+   * a space character.
+   */
+  guint is_resizable : 1;
 };
 
 /* Determine information about cluster/word/line breaks in a string
Index: pango/pango-layout-private.h
===================================================================
RCS file: /cvs/gnome/pango/pango/pango-layout-private.h,v
retrieving revision 1.1
diff -u -p -r1.1 pango-layout-private.h
--- pango/pango-layout-private.h	14 Jul 2004 22:17:35 -0000	1.1
+++ pango/pango-layout-private.h	16 May 2006 20:39:13 -0000
@@ -26,6 +26,11 @@
 
 G_BEGIN_DECLS
 
+/* Only one character has type G_UNICODE_LINE_SEPARATOR in Unicode 4.0;
+ * update this if that changes.
+ */
+#define PANGO_LINE_SEPARATOR 0x2028
+
 struct _PangoLayout
 {
   GObject parent_instance;
@@ -74,10 +79,46 @@ struct _PangoLayout
   GSList *lines;
 };
 
+typedef struct _ItemProperties ItemProperties;
+struct _ItemProperties
+{
+  PangoUnderline  uline;
+  gboolean        strikethrough;
+  gint            rise;
+  gint            letter_spacing;
+  gboolean        shape_set;
+  PangoRectangle *shape_ink_rect;
+  PangoRectangle *shape_logical_rect;
+};
+
 G_END_DECLS
-
-gboolean _pango_layout_line_ellipsize (PangoLayoutLine *line,
-				   PangoAttrList   *attrs);
-PangoLayoutLine* _pango_layout_iter_get_line_readonly (PangoLayoutIter *iter);
+
+PangoLayoutLine* _pango_layout_line_new	(PangoLayout     *layout);
+void	          _pango_layout_line_reorder	(PangoLayoutLine *line);
+void		  _pango_layout_line_ellipsize	(PangoLayoutLine *line,
+						 PangoAttrList   *attrs);
+PangoLayoutLine* _pango_layout_iter_get_line_readonly
+						(PangoLayoutIter *iter);
+
+void	_pango_layout_get_item_properties	(PangoItem        *item,
+						 ItemProperties   *properties);
+void    _pango_layout_ensure_tab_width          (PangoLayout      *layout);
+int	_pango_layout_get_tab_pos		(PangoLayout	  *layout,
+						 int		   index);
+void	_pango_layout_shape_tab			(PangoLayoutLine  *line,
+						 PangoGlyphString *glyphs);
+void	_pango_layout_imposed_shape		(const char       *text,
+						 gint              n_chars,
+						 PangoRectangle   *shape_ink,
+						 PangoRectangle   *shape_logical,
+						 PangoGlyphString *glyphs);
+PangoDirection _pango_layout_resolve_dir	(PangoDirection    direction);
+
+
+void	_pango_layout_paragraph			(PangoLayout     *layout,
+						 GList           *items,
+						 PangoDirection   base_dir,
+						 gint	          start_char_offset,
+						 PangoAttrList   *attrs);
 
 #endif /* __PANGO_LAYOUT_PRIVATE_H__ */
Index: pango/pango-layout.c
===================================================================
RCS file: /cvs/gnome/pango/pango/pango-layout.c,v
retrieving revision 1.175
diff -u -p -r1.175 pango-layout.c
--- pango/pango-layout.c	29 Apr 2006 19:41:23 -0000	1.175
+++ pango/pango-layout.c	16 May 2006 20:39:14 -0000
@@ -31,7 +31,6 @@
 
 
 typedef struct _Extents Extents;
-typedef struct _ItemProperties ItemProperties;
 typedef struct _ParaBreakState ParaBreakState;
 
 struct _Extents
@@ -44,17 +43,6 @@ struct _Extents
   PangoRectangle logical_rect;
 };
 
-struct _ItemProperties
-{
-  PangoUnderline  uline;
-  gboolean        strikethrough;
-  gint            rise;
-  gint            letter_spacing;
-  gboolean        shape_set;
-  PangoRectangle *shape_ink_rect;
-  PangoRectangle *shape_logical_rect;
-};
-
 struct _PangoLayoutIter
 {
   PangoLayout *layout;
@@ -159,7 +147,6 @@ static void pango_layout_check_lines (Pa
 
 static PangoAttrList *pango_layout_get_effective_attributes (PangoLayout *layout);
 
-static PangoLayoutLine * pango_layout_line_new         (PangoLayout     *layout);
 static void              pango_layout_line_postprocess (PangoLayoutLine *line,
 							ParaBreakState  *state);
 
@@ -172,9 +159,6 @@ static int *pango_layout_line_get_log2vi
 /* doesn't leak line */
 static PangoLayoutLine* _pango_layout_iter_get_line (PangoLayoutIter *iter);
 
-static void pango_layout_get_item_properties (PangoItem      *item,
-					      ItemProperties *properties);
-
 static void pango_layout_finalize    (GObject          *object);
 
 G_DEFINE_TYPE (PangoLayout, pango_layout, G_TYPE_OBJECT)
@@ -621,8 +605,6 @@ pango_layout_get_font_description (Pango
  * done by adding whitespace, but for some scripts (such as Arabic),
  * the justification may be done in more complex ways, like extending
  * the characters.
- *
- * Note that as of Pango-1.16, this functionality is not yet implemented.
  **/
 void
 pango_layout_set_justify (PangoLayout *layout,
@@ -630,7 +612,11 @@ pango_layout_set_justify (PangoLayout *l
 {
   g_return_if_fail (layout != NULL);
 
-  layout->justify = justify;
+  if (layout->justify != justify)
+    {
+      layout->justify = justify;
+      pango_layout_clear_lines (layout);
+    }
 }
 
 /**
@@ -640,7 +626,7 @@ pango_layout_set_justify (PangoLayout *l
  * Gets whether each complete line should be stretched to fill the entire
  * width of the layout.
  *
- * Return value: the justify.
+ * Return value: %TRUE if the lines are justified.
  **/
 gboolean
 pango_layout_get_justify (PangoLayout *layout)
@@ -1356,7 +1342,7 @@ pango_layout_line_index_to_x (PangoLayou
       PangoLayoutRun *run = run_list->data;
       ItemProperties properties;
 
-      pango_layout_get_item_properties (run->item, &properties);
+      _pango_layout_get_item_properties (run->item, &properties);
 
       if (run->item->offset <= index && run->item->offset + run->item->length > index)
 	{
@@ -2046,18 +2032,28 @@ pango_layout_line_get_char_direction (Pa
 				      int              index)
 {
   GSList *run_list;
+  PangoLayoutRun *closest_run = NULL;
 
+  /* Try to find the closest run that starts before index. */
   run_list = layout_line->runs;
+
+  if (!run_list)
+    return PANGO_DIRECTION_LTR;
+
   while (run_list)
     {
       PangoLayoutRun *run = run_list->data;
 
-      if (run->item->offset <= index && run->item->offset + run->item->length > index)
-	return run->item->analysis.level % 2 ? PANGO_DIRECTION_RTL : PANGO_DIRECTION_LTR;
+      if (run->item->offset <= index &&
+	  (!closest_run || run->item->offset > closest_run->item->offset))
+	closest_run = run;
 
       run_list = run_list->next;
     }
 
+  if (closest_run)
+    return closest_run->item->analysis.level % 2 ? PANGO_DIRECTION_RTL : PANGO_DIRECTION_LTR;
+
   g_assert_not_reached ();
 
   return PANGO_DIRECTION_LTR;
@@ -2624,12 +2620,12 @@ pango_layout_clear_lines (PangoLayout *l
  * Some functions for handling PANGO_ATTR_SHAPE *
  ************************************************/
 
-static void
-imposed_shape (const char       *text,
-	       gint              n_chars,
-	       PangoRectangle   *shape_ink,
-	       PangoRectangle   *shape_logical,
-	       PangoGlyphString *glyphs)
+void
+_pango_layout_imposed_shape (const char       *text,
+			     gint              n_chars,
+			     PangoRectangle   *shape_ink,
+			     PangoRectangle   *shape_logical,
+			     PangoGlyphString *glyphs)
 {
   int i;
   const char *p;
@@ -2697,9 +2693,6 @@ imposed_extents (gint              n_cha
  * Line Breaking *
  *****************/
 
-static void shape_tab (PangoLayoutLine  *line,
-		       PangoGlyphString *glyphs);
-
 static void
 free_run (PangoLayoutRun *run, gpointer data)
 {
@@ -2737,8 +2730,8 @@ uninsert_run (PangoLayoutLine *line)
   return item;
 }
 
-static void
-ensure_tab_width (PangoLayout *layout)
+void
+_pango_layout_ensure_tab_width (PangoLayout *layout)
 {
   if (layout->tab_width == -1)
     {
@@ -2808,8 +2801,8 @@ ensure_tab_width (PangoLayout *layout)
 /* For now we only need the tab position, we assume
  * all tabs are left-aligned.
  */
-static int
-get_tab_pos (PangoLayout *layout, int index)
+int
+_pango_layout_get_tab_pos (PangoLayout *layout, int index)
 {
   gint n_tabs;
   gboolean in_pixels;
@@ -2899,9 +2892,9 @@ line_width (PangoLayoutLine *line)
   return width;
 }
 
-static void
-shape_tab (PangoLayoutLine  *line,
-	   PangoGlyphString *glyphs)
+void
+_pango_layout_shape_tab (PangoLayoutLine  *line,
+			 PangoGlyphString *glyphs)
 {
   int i, space_width;
 
@@ -2916,12 +2909,12 @@ shape_tab (PangoLayoutLine  *line,
 
   glyphs->log_clusters[0] = 0;
 
-  ensure_tab_width (line->layout);
+  _pango_layout_ensure_tab_width (line->layout);
   space_width = line->layout->tab_width / 8;
 
   for (i=0;;i++)
     {
-      int tab_pos = get_tab_pos (line->layout, i);
+      int tab_pos = _pango_layout_get_tab_pos (line->layout, i);
       if (tab_pos >= current_width + space_width)
 	{
 	  glyphs->glyphs[0].geometry.width = tab_pos - current_width;
@@ -3009,13 +3002,15 @@ shape_run (PangoLayoutLine *line,
   PangoGlyphString *glyphs = pango_glyph_string_new ();
 
   if (layout->text[item->offset] == '\t')
-    shape_tab (line, glyphs);
+    _pango_layout_shape_tab (line, glyphs);
   else
     {
       if (state->properties.shape_set)
-	imposed_shape (layout->text + item->offset, item->num_chars,
-		       state->properties.shape_ink_rect, state->properties.shape_logical_rect,
-		       glyphs);
+	_pango_layout_imposed_shape (layout->text + item->offset,
+				     item->num_chars,
+				     state->properties.shape_ink_rect,
+				     state->properties.shape_logical_rect,
+				     glyphs);
       else
 	pango_shape (layout->text + item->offset, item->length, &item->analysis, glyphs);
 
@@ -3102,13 +3097,9 @@ process_item (PangoLayout     *layout,
   int i;
   gboolean processing_new_item = FALSE;
 
-  /* Only one character has type G_UNICODE_LINE_SEPARATOR in Unicode 5.0;
-   * update this if that changes. */
-#define LINE_SEPARATOR 0x2028
-
   if (!state->glyphs)
     {
-      pango_layout_get_item_properties (item, &state->properties);
+      _pango_layout_get_item_properties (item, &state->properties);
       state->glyphs = shape_run (line, state, item);
 
       state->log_widths = NULL;
@@ -3118,7 +3109,7 @@ process_item (PangoLayout     *layout,
     }
 
   if (!layout->single_paragraph &&
-      g_utf8_get_char (layout->text + item->offset) == LINE_SEPARATOR)
+      g_utf8_get_char (layout->text + item->offset) == PANGO_LINE_SEPARATOR)
     {
       insert_run (line, state, item, TRUE);
       state->log_widths_offset += item->num_chars;
@@ -3256,10 +3247,11 @@ process_item (PangoLayout     *layout,
 /* The resolved direction for the line is always one
  * of LTR/RTL; not a week or neutral directions
  */
-static void
-line_set_resolved_dir (PangoLayoutLine *line,
-		       PangoDirection   direction)
+PangoDirection
+_pango_layout_resolve_dir (PangoDirection   direction)
 {
+  PangoDirection result;
+
   switch (direction)
     {
     default:
@@ -3267,12 +3259,12 @@ line_set_resolved_dir (PangoLayoutLine *
     case PANGO_DIRECTION_TTB_RTL:
     case PANGO_DIRECTION_WEAK_LTR:
     case PANGO_DIRECTION_NEUTRAL:
-      line->resolved_dir = PANGO_DIRECTION_LTR;
+      result = PANGO_DIRECTION_LTR;
       break;
     case PANGO_DIRECTION_RTL:
     case PANGO_DIRECTION_WEAK_RTL:
     case PANGO_DIRECTION_TTB_LTR:
-      line->resolved_dir = PANGO_DIRECTION_RTL;
+      result = PANGO_DIRECTION_RTL;
       break;
     }
 
@@ -3296,19 +3288,21 @@ line_set_resolved_dir (PangoLayoutLine *
     case PANGO_GRAVITY_SOUTH:
       break;
     case PANGO_GRAVITY_NORTH:
-      line->resolved_dir = PANGO_DIRECTION_LTR
+      result = PANGO_DIRECTION_LTR
 			 + PANGO_DIRECTION_RTL
 			 - line->resolved_dir;
       break;
     case PANGO_GRAVITY_EAST:
       /* This is in fact why deprecated TTB_RTL is LTR */
-      line->resolved_dir = PANGO_DIRECTION_LTR;
+      result = PANGO_DIRECTION_LTR;
       break;
     case PANGO_GRAVITY_WEST:
       /* This is in fact why deprecated TTB_LTR is RTL */
-      line->resolved_dir = PANGO_DIRECTION_RTL;
+      result = PANGO_DIRECTION_RTL;
       break;
     }
+
+    return result;
 }
 
 static void
@@ -3322,10 +3316,10 @@ process_line (PangoLayout    *layout,
   int break_start_offset = 0;	    /* Start width before adding run with break */
   GSList *break_link = NULL;        /* Link holding run before break */
 
-  line = pango_layout_line_new (layout);
+  line = _pango_layout_line_new (layout);
   line->start_index = state->line_start_index;
   line->is_paragraph_start = state->first_line;
-  line_set_resolved_dir (line, state->base_dir);
+  line->resolved_dir = _pango_layout_resolve_dir (state->base_dir);
 
   if (layout->ellipsize != PANGO_ELLIPSIZE_NONE)
     state->remaining_width = -1;
@@ -3636,25 +3630,40 @@ pango_layout_check_lines (PangoLayout *l
 
       if (state.items)
 	{
-	  state.first_line = TRUE;
-	  state.base_dir = base_dir;
-	  state.start_offset = start_offset;
-	  state.line_start_index = start - layout->text;
+#if 0
+	  /* Enable this to use the new layout code for everything. */
+	  _pango_layout_paragraph (layout, state.items, base_dir, start_offset,
+				   state.attrs);
+#else
+	  /* Here we just use the new layout code for justification. */
+	  if (layout->justify)
+	    {
+	      _pango_layout_paragraph (layout, state.items, base_dir,
+				       start_offset, state.attrs);
+	    }
+	  else
+	    {
+	      state.first_line = TRUE;
+	      state.base_dir = base_dir;
+	      state.start_offset = start_offset;
+	      state.line_start_index = start - layout->text;
 
-	  state.glyphs = NULL;
-	  state.log_widths = NULL;
+	      state.glyphs = NULL;
+	      state.log_widths = NULL;
 
-	  while (state.items)
-	    process_line (layout, &state);
+	      while (state.items)
+		process_line (layout, &state);
+	    }
+#endif
 	}
       else
 	{
 	  PangoLayoutLine *empty_line;
 
-	  empty_line = pango_layout_line_new (layout);
+	  empty_line = _pango_layout_line_new (layout);
 	  empty_line->start_index = start - layout->text;
 	  empty_line->is_paragraph_start = TRUE;
-	  line_set_resolved_dir (empty_line, base_dir);
+	  empty_line->resolved_dir = _pango_layout_resolve_dir (base_dir);
 
 	  layout->lines = g_slist_prepend (layout->lines,
 					   empty_line);
@@ -3874,7 +3883,7 @@ pango_layout_line_x_to_index (PangoLayou
       ItemProperties properties;
       int logical_width;
 
-      pango_layout_get_item_properties (run->item, &properties);
+      _pango_layout_get_item_properties (run->item, &properties);
 
       if (properties.shape_set)
 	logical_width = properties.shape_logical_rect->width;
@@ -4455,8 +4464,8 @@ pango_layout_line_get_extents (PangoLayo
     }
 }
 
-static PangoLayoutLine *
-pango_layout_line_new (PangoLayout *layout)
+PangoLayoutLine *
+_pango_layout_line_new (PangoLayout *layout)
 {
   PangoLayoutLinePrivate *private = g_slice_new (PangoLayoutLinePrivate);
 
@@ -4564,8 +4573,8 @@ reorder_runs_recurse (GSList *items, int
   return result;
 }
 
-static void
-pango_layout_line_reorder (PangoLayoutLine *line)
+void
+_pango_layout_line_reorder (PangoLayoutLine *line)
 {
   GSList *logical_runs = line->runs;
   line->runs = reorder_runs_recurse (logical_runs, g_slist_length (logical_runs));
@@ -4577,7 +4586,7 @@ get_item_letter_spacing (PangoItem *item
 {
   ItemProperties properties;
 
-  pango_layout_get_item_properties (item, &properties);
+  _pango_layout_get_item_properties (item, &properties);
 
   return properties.letter_spacing;
 }
@@ -4702,16 +4711,16 @@ pango_layout_line_postprocess (PangoLayo
 
   /* Now convert logical to visual order
    */
-  pango_layout_line_reorder (line);
+  _pango_layout_line_reorder (line);
 
   /* Fixup letter spacing between runs
    */
   adjust_line_letter_spacing (line);
 }
 
-static void
-pango_layout_get_item_properties (PangoItem      *item,
-				  ItemProperties *properties)
+void
+_pango_layout_get_item_properties (PangoItem      *item,
+				   ItemProperties *properties)
 {
   GSList *tmp_list = item->analysis.extra_attrs;
 
--- /dev/null
+++ pango/pango-layout-engine.c
@@ -0,0 +1,2360 @@
+/* Pango
+ * pango-layout-engine.c: Text layout and justification
+ *
+ * Copyright (C) 2005 Damon Chaplin
+ *
+ * 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.
+ */
+
+/*
+ * The toplevel layout function is pango_layout_paragraph(). That simply calls
+ * one of these 3 functions:
+ *
+ * layout_single_paragraph() - used when the layout is in single paragraph
+ *   mode. It creates a single line for the entire text of the PangoLayout.
+ *
+ * layout_with_unlimited_width() - used when the layout width is -1 or
+ *   ellipsization is being used. It only breaks at LINE_SEPARATOR characters.
+ *
+ * layout_with_specific_width() - used in all other cases. This steps through
+ *   the characters in a line, scoring each potential break point. When it
+ *   reaches the end of the line it chooses the best break, and calls
+ *   build_line() to build the PangoLayoutLine. It then starts again at the
+ *   best break position. It repeats this until it reaches the end of the text.
+ *
+ *
+ * build_line() is called by each of the above, to build each PangoLayoutLine,
+ *   given information about the break position. It creates the PangoLayoutRuns
+ *   and splits up the PangoItems as necessary. Finally it calls finish_line()
+ *   or finish_line_without_justification() as appropriate.
+ *
+ * finish_line() calculates the word and letter spacing to use for each script
+ *   group in the line, then calls justify_line() to perform the justification.
+ *
+ * justify_line() adjusts the widths and positions of the glyphs in the line
+ *   to justify it.
+ */
+
+/*
+ * Notes on adding support for justification with kashidas:
+ *
+ * I don't think this would be too difficult. Here's my current ideas.
+ *
+ * 1) Add a bitfield "guint kashida_priority : 3;" to PangoLogAttr, so that
+ *    the arabic pango_break() implementation could return information about
+ *    where kashidas can be placed and their priority. For priorities see:
+ *    http://www.microsoft.com/middleeast/msdn/JustifyingText-CSS.aspx
+ *    We could maybe do this in the default break code, if everything can be
+ *    determined just by looking at the Unicode characters.
+ *
+ * 2) Add a function to get information about kashida glyphs in a given font
+ *    (i.e. the glyph index and its width).
+ *
+ * 3) In finish_line() we divide up the expansion adjustment between kashidas
+ *    and word/letter spacing, if necessary.
+ *    Then we divide the kashida expansion among the possible kashida insertion
+ *    positions, using their priorities.
+ *    Then we insert kashida glyphs at the corresponding positions.
+ *    (Note that we may have to keep kashida information around to be able to
+ *    do this.)
+ */
+
+/*
+ * Notes on tabs:
+ *
+ * Currently we only adjust tabs at the start of the line to take account of
+ * cluster/letter spacing. So any tabs later in the line may be slightly out.
+ * But the fix for this can wait until we support more complex tabs,
+ * i.e. support for center/right/character-alignment and fill characters.
+ *
+ * I think tabs are always raised to the top embedding level, so you don't need
+ * to worry too much about bidirectional issues.
+ *
+ * In future I think we should work on the line in segments, separated by tabs,
+ * and align/justify each separately.
+ */
+
+#include <pango/pango-script.h>
+
+#include "pango-layout-private.h"
+
+
+/* Define this to get debugging output about potential breaks. */
+/*#define DEBUG_BREAKS*/
+/* Define this to get debugging output about line overflows. */
+/*#define DEBUG_LINE_OVERFLOW*/
+
+
+/* This is the maximum fraction we can shrink resizable space, i.e. 1/3. */
+#define WORD_SPACING_MAX_COMPRESSION	3
+
+/*
+ * This is the maximum fraction we can shrink letter spaced text, i.e. 1/10.
+ * Note that we don't do letter spacing normally. It is only used as a last
+ * resort if we are going to overflow the line.
+ */
+#define LETTER_SPACING_MAX_COMPRESSION	10
+
+
+/* The justification settings from CSS3. */
+typedef enum {
+  PANGO_JUSTIFICATION_NONE		= 0,
+  PANGO_JUSTIFICATION_AUTO		= 1,
+  PANGO_JUSTIFICATION_INTER_WORD	= 2,
+  PANGO_JUSTIFICATION_INTER_IDEOGRAPH	= 3,
+  PANGO_JUSTIFICATION_INTER_CHARACTER	= 4,
+  PANGO_JUSTIFICATION_INTER_CLUSTER	= 5,
+  PANGO_JUSTIFICATION_KASHIDA		= 6
+} PangoJustification;
+
+
+/* These are the possible types of spacing used to justify a PangoItem.
+ * Note that kashida spacing isn't implemented yet.
+ */
+typedef enum {
+  PANGO_ITEM_SPACING_NONE		= 0,
+  PANGO_ITEM_SPACING_WORD		= 1 << 0,
+  PANGO_ITEM_SPACING_LETTER		= 1 << 1,
+  PANGO_ITEM_SPACING_KASHIDA		= 1 << 2,
+
+  PANGO_ITEM_SPACING_WORD_LETTER	= PANGO_ITEM_SPACING_WORD
+					  | PANGO_ITEM_SPACING_LETTER
+} PangoItemSpacing;
+
+
+/* These are the script groups used to determine the spacing method to use for
+ * a particular PangoItem, as defined in the CSS3 Text module. The values
+ * are used as indices in spacing_table and auto_justification_table, so update
+ * them if these change.
+ */
+#define NUM_SCRIPT_GROUPS	6
+typedef enum 
+{
+  SCRIPT_GROUP_NONE		= 0,	/* Shapes */
+  SCRIPT_GROUP_DISCRETE		= 1,	/* Latin, Greek, Cyrillic, Hebrew */
+  SCRIPT_GROUP_BLOCK		= 2,	/* CJK (inc Hangul & 1/2 width kana) */
+  SCRIPT_GROUP_CLUSTERED	= 3,	/* Thai, Lao, Khmer, Myanmar */
+  SCRIPT_GROUP_CONNECTED	= 4,	/* Devanagari, Bengali, Gurmukhi */
+  SCRIPT_GROUP_CURSIVE		= 5	/* Arabic */
+} ScriptGroup;
+
+
+/* This holds information about a line within the text, passed in to
+ * build_line().
+ */
+typedef struct _LineInfo LineInfo;
+struct _LineInfo
+{
+  /* The justification setting to use, for the entire paragraph. This will be
+   * the same as layout->justification, except when PANGO_JUSTIFICATION_AUTO
+   * is used, when this will be the actual justification setting chosen, based
+   * on the first non-NONE script group found in the paragraph and the settings
+   * in auto_justification_table[].
+   */
+  PangoJustification justification;
+
+
+  /* The line number, starting from 0. */
+  int line_num;
+
+  /* TRUE if this is the last line in the paragraph. */
+  gboolean is_last_line;
+
+  /* The byte & char offset into the text at the start of the line. */
+  int line_start_byte_offset;
+  int line_start_char_offset;
+
+  /* The byte & char offset of the character immediately after the break. */
+  int line_end_byte_offset;
+  int line_end_char_offset;
+
+  /* The byte & char offset of the start of the next line. This may be a 
+   * few characters after the break, due to trimmed whitespace characters.
+   */
+  int next_line_byte_offset;
+  int next_line_char_offset;
+
+  /* This is the byte offset of the last tab character in the line, or -1 if
+   * there are no tabs in the line. We don't do any justification before tab
+   * characters.
+   */
+  int last_tab_byte_offset;
+
+
+  /*
+   * Information used to calculate word/letter/kashida spacing.
+   */
+
+  /* The required width of the line. */
+  PangoGlyphUnit required_line_width;
+
+  /* This is the minimum letter spacing we've seen on any PangoItem in the
+   * line. We assumed this amount will be trimmed off the ends of the line.
+   * If it turns out to be more than this we need to expand the line a bit.
+   */
+  PangoGlyphUnit min_letter_spacing;
+
+
+  /*
+   * Note that these only count from the last tab in a line, since we can't
+   * justify any text before a tab.
+   */
+
+  /* The width of all the text for each script group. */
+  PangoGlyphUnit total_width[NUM_SCRIPT_GROUPS];
+
+  /* The amount of resizable width for each script group. */
+  PangoGlyphUnit resizable_width[NUM_SCRIPT_GROUPS];
+
+  /* The total number of clusters for each script group. */
+  int num_clusters[NUM_SCRIPT_GROUPS];
+};
+
+
+typedef struct _JustificationInfo JustificationInfo;
+struct _JustificationInfo
+{
+  double space_multiplier[NUM_SCRIPT_GROUPS];
+  PangoGlyphUnit cluster_spacing[NUM_SCRIPT_GROUPS];
+
+  /* These are used while justifying the line. */
+  PangoGlyphUnit total_resizable_width[NUM_SCRIPT_GROUPS];
+  PangoGlyphUnit total_adjusted_width[NUM_SCRIPT_GROUPS];
+
+  /* These are the first and last runs in the line, visually. They are used
+   * to determine the adjustments needed below.
+   */
+  PangoLayoutRun *line_start_run;
+  PangoLayoutRun *line_end_run;
+
+  /* These are used to return the ajustment needed to trim any cluster spacing
+   * off the ends of the line.
+   */
+  int line_start_adjustment;
+  int line_end_adjustment;
+};
+
+
+/* When deciding where to split lines we need to keep some data about each
+ * item.
+ */
+typedef struct _ItemData ItemData;
+struct _ItemData
+{
+  /* This is the item's element in the list of items from pango_break(). */
+  GList *item_node;
+
+  /* This is the character offset of the item within the PangoLayout's text. */
+  int item_char_offset;
+
+  /* This is the original number of characters in the item. As we layout
+   * the paragraph the item may be split into several pieces.
+   */
+  int num_chars;
+
+  /* The glyphs of the item. If the item doesn't need to be split we can use
+   * this for the final runs, otherwise this needs to be freed.
+   */
+  PangoGlyphString *glyphs;
+
+  /* These are the logical widths of each character in the item. */
+  PangoGlyphUnit *log_widths;
+
+  /* Ths script group of the item. */
+  ScriptGroup script_group;
+
+  /* These are the properties like letter spacing, from the attributes. */
+  ItemProperties properties;
+};
+
+
+/* This is the table of spacing methods to use for each of the five script
+ * groups against each of the 7 PangoJustification settings.
+ */
+#define NUM_PRIORITIES	3
+static const PangoItemSpacing spacing_table[NUM_SCRIPT_GROUPS][7][NUM_PRIORITIES] =
+  {
+    {
+      /* SCRIPT_GROUP_NONE */
+      { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 },
+      { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 },
+    },
+
+    {
+      { 0, 0, 0 }, { 0, 0, 0 },
+
+      /* SCRIPT_GROUP_DISCRETE - PANGO_JUSTIFICATION_INTER_WORD */
+      { PANGO_ITEM_SPACING_WORD, PANGO_ITEM_SPACING_LETTER, 0 },
+
+      /* SCRIPT_GROUP_DISCRETE - PANGO_JUSTIFICATION_INTER_IDEOGRAPH */
+      { PANGO_ITEM_SPACING_WORD, PANGO_ITEM_SPACING_LETTER, 0 },
+
+      /* SCRIPT_GROUP_DISCRETE - PANGO_JUSTIFICATION_INTER_CHARACTER */
+      { PANGO_ITEM_SPACING_WORD_LETTER, 0, 0 },
+
+      /* SCRIPT_GROUP_DISCRETE - PANGO_JUSTIFICATION_INTER_CLUSTER */
+      { PANGO_ITEM_SPACING_WORD, PANGO_ITEM_SPACING_LETTER, 0 },
+
+      /* SCRIPT_GROUP_DISCRETE - PANGO_JUSTIFICATION_KASHIDA */
+      { 0, PANGO_ITEM_SPACING_WORD, PANGO_ITEM_SPACING_LETTER }
+    },
+
+    {
+      { 0, 0, 0 }, { 0, 0, 0 },
+
+      /* SCRIPT_GROUP_BLOCK - PANGO_JUSTIFICATION_INTER_WORD */
+      { PANGO_ITEM_SPACING_WORD, PANGO_ITEM_SPACING_LETTER, 0 },
+
+      /* SCRIPT_GROUP_BLOCK - PANGO_JUSTIFICATION_INTER_IDEOGRAPH */
+      { PANGO_ITEM_SPACING_WORD_LETTER, 0, 0 },
+
+      /* SCRIPT_GROUP_BLOCK - PANGO_JUSTIFICATION_INTER_CHARACTER */
+      { PANGO_ITEM_SPACING_WORD_LETTER, 0, 0 },
+
+      /* SCRIPT_GROUP_BLOCK - PANGO_JUSTIFICATION_INTER_CLUSTER */
+      { PANGO_ITEM_SPACING_WORD, PANGO_ITEM_SPACING_LETTER, 0 },
+
+      /* SCRIPT_GROUP_BLOCK - PANGO_JUSTIFICATION_KASHIDA */
+      { 0, PANGO_ITEM_SPACING_WORD, PANGO_ITEM_SPACING_LETTER }
+    },
+
+    {
+      { 0, 0, 0 }, { 0, 0, 0 },
+
+      /* SCRIPT_GROUP_CLUSTERED - PANGO_JUSTIFICATION_INTER_WORD */
+      { PANGO_ITEM_SPACING_WORD, PANGO_ITEM_SPACING_LETTER, 0 },
+
+      /* SCRIPT_GROUP_CLUSTERED - PANGO_JUSTIFICATION_INTER_IDEOGRAPH */
+      { PANGO_ITEM_SPACING_WORD_LETTER, 0, 0 },
+
+      /* SCRIPT_GROUP_CLUSTERED - PANGO_JUSTIFICATION_INTER_CHARACTER */
+      { PANGO_ITEM_SPACING_WORD_LETTER, 0, 0 },
+
+      /* SCRIPT_GROUP_CLUSTERED - PANGO_JUSTIFICATION_INTER_CLUSTER */
+      { PANGO_ITEM_SPACING_WORD_LETTER, 0, 0 },
+
+      /* SCRIPT_GROUP_CLUSTERED - PANGO_JUSTIFICATION_KASHIDA */
+      { 0, PANGO_ITEM_SPACING_WORD, PANGO_ITEM_SPACING_LETTER }
+    },
+
+    {
+      { 0, 0, 0 }, { 0, 0, 0 },
+
+      /* SCRIPT_GROUP_CONNECTED - PANGO_JUSTIFICATION_INTER_WORD */
+      { PANGO_ITEM_SPACING_WORD, 0, 0 },
+
+      /* SCRIPT_GROUP_CONNECTED - PANGO_JUSTIFICATION_INTER_IDEOGRAPH */
+      { PANGO_ITEM_SPACING_WORD, 0, 0 },
+
+      /* SCRIPT_GROUP_CONNECTED - PANGO_JUSTIFICATION_INTER_CHARACTER */
+      { PANGO_ITEM_SPACING_WORD, 0, 0 },
+
+      /* SCRIPT_GROUP_CONNECTED - PANGO_JUSTIFICATION_INTER_CLUSTER */
+      { PANGO_ITEM_SPACING_WORD, 0, 0 },
+
+      /* SCRIPT_GROUP_CONNECTED - PANGO_JUSTIFICATION_KASHIDA */
+      { 0, PANGO_ITEM_SPACING_WORD, 0 }
+    },
+
+    {
+      { 0, 0, 0 }, { 0, 0, 0 },
+
+      /* SCRIPT_GROUP_CURSIVE - PANGO_JUSTIFICATION_INTER_WORD */
+      { PANGO_ITEM_SPACING_WORD, PANGO_ITEM_SPACING_KASHIDA, 0 },
+
+      /* SCRIPT_GROUP_CURSIVE - PANGO_JUSTIFICATION_INTER_IDEOGRAPH */
+      { PANGO_ITEM_SPACING_WORD, PANGO_ITEM_SPACING_KASHIDA, 0 },
+
+      /* SCRIPT_GROUP_CURSIVE - PANGO_JUSTIFICATION_INTER_CHARACTER */
+      { PANGO_ITEM_SPACING_WORD, PANGO_ITEM_SPACING_KASHIDA, 0 },
+
+      /* SCRIPT_GROUP_CURSIVE - PANGO_JUSTIFICATION_INTER_CLUSTER */
+      { PANGO_ITEM_SPACING_WORD, PANGO_ITEM_SPACING_KASHIDA, 0 },
+
+      /* SCRIPT_GROUP_CURSIVE - PANGO_JUSTIFICATION_KASHIDA */
+      { PANGO_ITEM_SPACING_KASHIDA, PANGO_ITEM_SPACING_WORD, 0 }
+    }
+  };
+
+
+/* These are the justification settings to use for PANGO_JUSTIFICATION_AUTO,
+ * and are based on the first non-NONE script group found in the text.
+ */
+static const int auto_justification_table[NUM_SCRIPT_GROUPS] =
+  {
+    PANGO_JUSTIFICATION_INTER_WORD,	/* SCRIPT_GROUP_NONE */
+    PANGO_JUSTIFICATION_INTER_WORD,	/* SCRIPT_GROUP_DISCRETE */
+    PANGO_JUSTIFICATION_INTER_IDEOGRAPH,/* SCRIPT_GROUP_BLOCK */
+    PANGO_JUSTIFICATION_INTER_CLUSTER,	/* SCRIPT_GROUP_CLUSTERED */
+    PANGO_JUSTIFICATION_INTER_WORD,	/* SCRIPT_GROUP_CONNECTED */
+    PANGO_JUSTIFICATION_KASHIDA		/* SCRIPT_GROUP_CURSIVE */
+  };
+
+
+/* This returns the script group of a given PangoItem. It is usually determined
+ * by checking the item's language against a list of languages, but in some
+ * cases the item's language isn't specific enough and we need to look at a
+ * few of the characters in the item to guess the script group.
+ */
+static ScriptGroup
+get_item_script_group (PangoLayout *layout,
+		       PangoItem   *item)
+{
+  static gboolean initialized = FALSE;
+  static PangoLanguage *ja, *ko, *zh_cn, *zh_hk, *zh_mo, *zh_sg, *zh_tw;
+  static PangoLanguage *bh, *bho, *bn, *hi, *kok, *ks, *mr, *ne, *sa;
+  static PangoLanguage *ar, *fa, *syr, *ug, *ur;
+  static PangoLanguage *km, *lo, *my, *th, *xx;
+
+  PangoLanguage *language = item->analysis.language;
+  ScriptGroup group;
+  GSList *l;
+
+  /* We need to compare against lots of languages, so we get the pointers
+   * just the once.
+   */
+  if (!initialized)
+    { 
+      /* SCRIPT_GROUP_BLOCK. */
+      ja = pango_language_from_string ("ja");
+      ko = pango_language_from_string ("ko");
+      zh_cn = pango_language_from_string ("zh-cn");
+      zh_hk = pango_language_from_string ("zh-hk");
+      zh_mo = pango_language_from_string ("zh-mo");
+      zh_sg = pango_language_from_string ("zh-sg");
+      zh_tw = pango_language_from_string ("zh-tw");
+
+      /* SCRIPT_GROUP_CONNECTED */
+      bh = pango_language_from_string ("bh");
+      bho = pango_language_from_string ("bho");
+      bn = pango_language_from_string ("bn");
+      hi = pango_language_from_string ("hi");
+      kok = pango_language_from_string ("kok");
+      ks = pango_language_from_string ("ks");
+      mr = pango_language_from_string ("mr");
+      ne = pango_language_from_string ("ne");
+      sa = pango_language_from_string ("sa");
+
+      /* SCRIPT_GROUP_CURSIVE */
+      ar = pango_language_from_string ("ar");
+      fa = pango_language_from_string ("fa");
+      syr = pango_language_from_string ("syr");
+      ug = pango_language_from_string ("ug");
+      ur = pango_language_from_string ("ur");
+
+      /* SCRIPT_GROUP_CLUSTERED */
+      km = pango_language_from_string ("km");
+      lo = pango_language_from_string ("lo");
+      my = pango_language_from_string ("my");
+      th = pango_language_from_string ("th");
+
+      /* This may be used when the language couldn't be determined exactly
+       * from the script. See compute_derived_language() in pango-context.c
+       */
+      xx = pango_language_from_string ("xx");
+
+      initialized = TRUE;
+    }
+
+  /* First check if it is a shape. */
+  for (l = item->analysis.extra_attrs; l; l = l->next)
+    {
+      PangoAttribute *attr = l->data;
+
+      if (attr->klass->type == PANGO_ATTR_SHAPE)
+	return SCRIPT_GROUP_NONE;
+    }
+
+  /* Determine which of the script groups the item's language is in.
+   * FIXME: Most languages use one script. A few use Latin and Cyrillic
+   * (az, cv, ku, mo), but they are in the same script group so that
+   * doesn't matter. However, Japanese uses Han, Hiragana and Katakana,
+   * and Korean uses Hangul and Han, and I'm not sure if these are in
+   * different script groups, so they may need special treatment.
+   */
+  if (language == ja || language == ko || language == zh_cn ||
+      language == zh_hk || language == zh_mo || language == zh_sg ||
+      language == zh_tw)
+    group = SCRIPT_GROUP_BLOCK;
+  else if (language == bh || language == bho || language == bn ||
+	   language == hi || language == kok || language == ks ||
+	   language == mr || language == ne || language == sa)
+    group = SCRIPT_GROUP_CONNECTED;
+  else if (language == ar || language == fa || language == syr ||
+	   language == ug || language == ur)
+    group = SCRIPT_GROUP_CURSIVE;
+  else if (language == km || language == lo || language == my ||
+	   language == th)
+    group = SCRIPT_GROUP_CLUSTERED;
+  else if (language == xx)
+    {
+      /* The language couldn't be determined exactly, so we have to look at
+       * the scripts of the characters.
+       */
+      const char *pos = layout->text + item->offset;
+      const char *end = pos + item->length;
+
+      group = SCRIPT_GROUP_DISCRETE;
+      while (pos < end)
+	{
+	  gunichar ch = g_utf8_get_char (pos);
+	  PangoScript script = pango_script_for_unichar (ch);
+
+	  if (script > PANGO_SCRIPT_INHERITED)
+	    {
+	      /* Set the group according to the first script found.
+	       * See pango_script_get_sample_language() for all the entries
+	       * with "" as the language that we could check for here if
+	       * necessary. We default to SCRIPT_GROUP_DISCRETE.
+	       */
+	      if (script == PANGO_SCRIPT_HAN)
+		group = SCRIPT_GROUP_BLOCK;
+	      break;
+	    }
+	  pos = g_utf8_next_char (pos);
+	}
+    }
+  else
+    group = SCRIPT_GROUP_DISCRETE;
+
+#if 0
+  g_print ("Language: %s Group: %i\n", pango_language_to_string (language),
+	   group);
+#endif
+
+  return group;
+}
+
+
+/* This adds letter spacing to each glyph in a PangoGlyphString. It adds the
+ * letter spacing to the cluster's width, and moves each glyph to the right
+ * by half of the spacing amount (if it is > 0).
+ */
+static void
+letter_space (PangoGlyphString *glyph_string,
+	      PangoGlyphUnit    letter_spacing)
+{
+  int cluster_x_adjustment = 0, glyph_index, offset = -1;
+
+  if (letter_spacing > 0)
+    cluster_x_adjustment = letter_spacing / 2;
+
+  for (glyph_index = glyph_string->num_glyphs - 1; glyph_index >= 0;
+       glyph_index--)
+    {
+      glyph_string->glyphs[glyph_index].geometry.x_offset += cluster_x_adjustment;
+
+      /* We check the log_clusters byte offset to see if we've moved to the
+       * next cluster. We initialized offset to -1 so it doesn't match on
+       * the first iteration.
+       */
+      if (glyph_string->log_clusters[glyph_index] != offset)
+	{
+	  offset = glyph_string->log_clusters[glyph_index];
+	  glyph_string->glyphs[glyph_index].geometry.width += letter_spacing;
+	}
+    }
+}
+
+
+/* This trims any cluster spacing off the ends of the line, once it has
+ * been reordered into visual order.
+ */
+static void
+trim_line_ends (PangoLayoutRun *line_start_run,
+		PangoGlyphUnit  line_start_letter_spacing,
+		PangoGlyphUnit  line_start_adjustment,
+		PangoLayoutRun *line_end_run,
+		PangoGlyphUnit  line_end_letter_spacing,
+		PangoGlyphUnit  line_end_adjustment)
+{
+  PangoGlyphString *glyph_string;
+  PangoGlyphUnit trim_width;
+  int start_glyph_index, glyph_index, offset;
+
+  /* Trim the left edge of the line. */
+  if (line_start_run)
+    {
+      glyph_string = line_start_run->glyphs;
+      offset = glyph_string->log_clusters[0];
+      start_glyph_index = 0;
+
+      /* Find the first non-empty cluster. */
+      for (glyph_index = 0; glyph_index <= glyph_string->num_glyphs;
+	   glyph_index++)
+	{
+	  if (glyph_index == glyph_string->num_glyphs ||
+	      glyph_string->log_clusters[glyph_index] != offset)
+	    {
+	      if (glyph_string->glyphs[glyph_index - 1].geometry.width != 0)
+		{
+		  /* We need to remove the adjustment due to the item's
+		   * letter spacing setting as well as the adjustment
+		   * from justification.
+		   */
+		  trim_width = line_start_adjustment
+		    + line_start_letter_spacing / 2;
+
+		  /* Adjust the x_offsets of all the glyphs. */
+		  while (start_glyph_index < glyph_index)
+		    {
+		      glyph_string->glyphs[start_glyph_index].geometry.x_offset -= trim_width;
+		      start_glyph_index++;
+		    }
+
+		  /* Adjust the geometry width of the last glyph. */
+		  glyph_string->glyphs[glyph_index - 1].geometry.width -= trim_width;
+		  break;
+		}
+
+	      start_glyph_index = glyph_index;
+	      if (glyph_index != glyph_string->num_glyphs)
+		offset = glyph_string->log_clusters[glyph_index];
+	    }
+	}
+    }
+
+  /* Now trim the right edge of the line. */
+  if (line_end_run)
+    {
+      glyph_string = line_end_run->glyphs;
+      offset = -1;
+
+      /* Find the last non-empty cluster. */
+      for (glyph_index = glyph_string->num_glyphs - 1; glyph_index >= 0;
+	   glyph_index--)
+	{
+	  if (glyph_string->log_clusters[glyph_index] != offset)
+	    {
+	      if (glyph_string->glyphs[glyph_index].geometry.width != 0)
+		{
+		  /* Adjust the geometry width of the last glyph. */
+		  trim_width = line_end_adjustment
+		    + (line_end_letter_spacing - line_end_letter_spacing / 2);
+		  glyph_string->glyphs[glyph_index].geometry.width -= trim_width;
+		  break;
+		}
+
+	      offset = glyph_string->log_clusters[glyph_index];
+	    }
+	}
+    }
+}
+
+
+/* This returns the first and last runs in the line that have non-zero-width
+ * glyphs and their letter spacing settings. We need to know these settings
+ * so we can adjust the line widths before calculating how much to stretch
+ * spaces and clusters by.
+ */
+static void
+get_line_ends (PangoLayout      *layout,
+	       PangoLayoutLine  *line,
+	       PangoLayoutRun  **line_start_run,
+	       PangoGlyphUnit   *line_start_letter_spacing,
+	       ScriptGroup	*line_start_script_group,
+	       PangoLayoutRun  **line_end_run,
+	       PangoGlyphUnit   *line_end_letter_spacing,
+	       ScriptGroup	*line_end_script_group)
+{
+  GSList *l;
+
+  *line_start_run = *line_end_run = NULL;
+  *line_start_letter_spacing = *line_end_letter_spacing = 0;
+
+  /* Look through each run to find the first non-zero-width cluster, and the
+   * last run with a non-zero-width cluster.
+   */
+  for (l = line->runs; l; l = l->next)
+    {
+      PangoLayoutRun *run = l->data;
+      PangoGlyphString *glyph_string = run->glyphs;
+
+      /* Skip tabs and items with no glyphs. */
+      if (*(layout->text + run->item->offset) != '\t' &&
+	  glyph_string->num_glyphs > 0)
+	{
+	  int glyph_index, offset, letter_spacing;
+	  PangoItem *item = run->item;
+	  ItemProperties properties;
+
+	  _pango_layout_get_item_properties (item, &properties);
+	  letter_spacing = properties.letter_spacing;
+
+	  /* Find the left-most, non-zero-width cluster. */
+	  offset = glyph_string->log_clusters[0];
+	  for (glyph_index = 0; glyph_index <= glyph_string->num_glyphs;
+	       glyph_index++)
+	    {
+	      if (glyph_index == glyph_string->num_glyphs ||
+		  glyph_string->log_clusters[glyph_index] != offset)
+		{
+		  if (glyph_string->glyphs[glyph_index - 1].geometry.width != 0)
+		    {
+		      /* Remember this run has a non-zero-width cluster. */
+		      *line_end_run = run;
+		      *line_end_letter_spacing = letter_spacing;
+
+		      if (*line_start_run == NULL)
+			{
+			  *line_start_run = run;
+			  /* We need to remove the adjustment due to the item's
+			   * letter spacing setting as well as the adjustment
+			   * from justification.
+			   */
+			  *line_start_letter_spacing = letter_spacing;
+			}
+
+		      break;
+		    }
+
+		  if (glyph_index != glyph_string->num_glyphs)
+		    offset = glyph_string->log_clusters[glyph_index];
+		}
+	    }
+	}
+    }
+
+  if (line_start_script_group)
+    {
+      if (*line_start_run)
+	*line_start_script_group = get_item_script_group (layout, (*line_start_run)->item);
+      else
+	*line_start_script_group = SCRIPT_GROUP_DISCRETE;
+
+      if (*line_end_run)
+	*line_end_script_group = get_item_script_group (layout, (*line_end_run)->item);
+      else
+	*line_end_script_group = SCRIPT_GROUP_DISCRETE;
+    }
+}
+
+
+/* This takes the PangoLayoutLine created in build_line(), reorders the runs
+ * into visual order, trims any letter spacing off the ends of the line,
+ * and ellipsizes it if required.
+ */
+static void
+finish_line_without_justification (PangoLayout     *layout,
+				   PangoLayoutLine *line,
+				   PangoAttrList   *attrs)
+{
+  PangoLayoutRun *line_start_run, *line_end_run;
+  PangoGlyphUnit line_start_letter_spacing, line_end_letter_spacing;
+
+  /* Reorder the line from logical to visual order. */
+  _pango_layout_line_reorder (line);
+
+  /* Get the first & last run in the line, and the letter space in each. */
+  get_line_ends (layout, line, &line_start_run, &line_start_letter_spacing,
+		 NULL, &line_end_run, &line_end_letter_spacing, NULL);
+
+  /* Trim the space off the ends of the line. */
+  if (line_start_letter_spacing || line_end_letter_spacing)
+    trim_line_ends (line_start_run, line_start_letter_spacing, 0,
+		    line_end_run, line_end_letter_spacing, 0);
+
+  /* FIXME: The old layout code does ellipsization before reordering the line,
+   * but I think it should be done last.
+   */
+  _pango_layout_line_ellipsize (line, attrs);
+}
+
+
+static void
+word_space (PangoLayout		*layout,
+	    JustificationInfo	*justification_info,
+	    PangoLayoutRun	*run,
+	    int			 item_char_offset,
+	    ScriptGroup		 script_group)
+{
+  PangoItem *item = run->item;
+  PangoGlyphString *glyph_string = run->glyphs;
+  double space_multiplier = justification_info->space_multiplier[script_group];
+  int glyph_index, glyph_step, glyph_bound;
+  int char_num;
+  const char *p;
+
+  /* Step through the characters in the item looking for spaces. */
+  if (item->analysis.level % 2 == 0)
+    {
+      /* LTR. The glyphs for the first character are first. */
+      glyph_index = 0;
+      glyph_step = 1;
+      glyph_bound = glyph_string->num_glyphs;
+    }
+  else
+    {
+      /* RTL. The glyphs for the first character are last. */
+      glyph_index = glyph_string->num_glyphs - 1;
+      glyph_step = -1;
+      glyph_bound = -1;
+    }
+
+  p = layout->text + item->offset;
+  for (char_num = 0; char_num < item->num_chars; char_num++)
+    {
+      if (layout->log_attrs[item_char_offset + char_num].is_resizable)
+	{
+	  int offset = p - (layout->text + item->offset);
+	  int old_width, new_width;
+	  int start_glyph_index, change_glyph_index;
+
+	  /* Step through the glyphs until we find this cluster. */
+	  while (glyph_index != glyph_bound &&
+		 glyph_string->log_clusters[glyph_index] < offset)
+	    glyph_index += glyph_step;
+
+	  start_glyph_index = glyph_index;
+
+	  /* Find the glyph at the start of the next cluster. */
+	  while (glyph_index != glyph_bound &&
+		 glyph_string->log_clusters[glyph_index] == offset)
+	    glyph_index += glyph_step;
+
+	  /* Adjust the glyphs in the cluster, if there are any. */
+	  if (start_glyph_index != glyph_index)
+	    {
+	      /* We need to change the geometry width of the last
+	       * glyph in the cluster, which is the first one we
+	       * found in RTL since we are stepping backwards.
+	       */
+	      if (glyph_step == 1)
+		change_glyph_index = glyph_index - 1;
+	      else
+		change_glyph_index = start_glyph_index;
+
+	      /* Calculate the new width of the cluster. */
+	      old_width = glyph_string->glyphs[change_glyph_index].geometry.width;
+	      justification_info->total_resizable_width[script_group] += old_width;
+	      new_width = (justification_info->total_resizable_width[script_group] * space_multiplier) + 0.5;
+	      new_width -= justification_info->total_adjusted_width[script_group];
+	      justification_info->total_adjusted_width[script_group] += new_width;
+
+	      /* Update the width of the appropriate glyph. */
+	      glyph_string->glyphs[change_glyph_index].geometry.width = new_width;
+
+	      /* If the cluster has been expanded, we place the glyphs
+	       * in the middle of the space.
+	       */
+	      if (new_width > old_width)
+		{
+		  int x_offset = (new_width - old_width) / 2;
+
+		  while (start_glyph_index != glyph_index)
+		    {
+		      glyph_string->glyphs[start_glyph_index].geometry.x_offset += x_offset;
+		      start_glyph_index += glyph_step;
+		    }
+		}
+	    }
+	}
+
+      p = g_utf8_next_char (p);
+    }
+}
+
+
+/* This justifies the line of text, using the settings calculated in
+ * finish_line().
+ */
+static void
+justify_line (PangoLayout	*layout,
+	      GSList		*runs,
+	      LineInfo		*line_info,
+	      JustificationInfo *justification_info)
+{
+  ScriptGroup script_group;
+  int item_char_offset;
+  GSList *l;
+
+  /* We keep a running total of the width of resizable glyphs seen so far,
+   * and the total of the adjusted glyphs. By using these for the calculations
+   * we avoid rounding errors, and spread the adjustment evenly across the
+   * line.
+   */
+  for (script_group = 0; script_group < NUM_SCRIPT_GROUPS; script_group++)
+    {
+      justification_info->total_resizable_width[script_group] = 0;
+      justification_info->total_adjusted_width[script_group] = 0;
+    }
+
+  justification_info->line_start_adjustment = 0;
+  justification_info->line_end_adjustment = 0;
+
+  /* Step through the runs in the line. */
+  item_char_offset = line_info->line_start_char_offset;
+  for (l = runs; l; l = l->next)
+    {
+      PangoLayoutRun *run = l->data;
+      PangoItem *item = run->item;
+      PangoGlyphString *glyph_string = run->glyphs;
+      double space_multiplier;
+      PangoGlyphUnit cluster_spacing;
+
+      /* Check if we really need to space the glyphs in the item.
+       * If there are no glyphs, or we are before the last tab in the line
+       * we can skip this run.
+       */
+      if (glyph_string->num_glyphs == 0 ||
+	  item->offset <= line_info->last_tab_byte_offset)
+	{
+	  item_char_offset += item->num_chars;
+	  continue;
+	}
+
+      /* Calculate the script group of the item. */
+      script_group = get_item_script_group (layout, item);
+      space_multiplier = justification_info->space_multiplier[script_group];
+      cluster_spacing = justification_info->cluster_spacing[script_group];
+
+#if 0
+      g_print ("  justifying item offset: %i len: %i chars: %i spc_mult: %g clst_spc: %i\n", item->offset, item->length, item->num_chars, space_multiplier, cluster_spacing);
+#endif
+
+      /* Word spacing. */
+      if (space_multiplier != 1)
+	{
+	  word_space (layout, justification_info, run, item_char_offset,
+		      script_group);
+	}
+
+      /* Letter/cluster spacing. */
+      if (cluster_spacing)
+	{
+	  letter_space (glyph_string, cluster_spacing);
+	  
+	  /* If the run at the start or end of the line is justified with
+	   * letter spacing, we need to trim half the space later.
+	   */
+	  if (cluster_spacing > 0)
+	    {
+	      if (run == justification_info->line_start_run)
+		justification_info->line_start_adjustment = cluster_spacing / 2;
+	      if (run == justification_info->line_end_run)
+		justification_info->line_end_adjustment = cluster_spacing - (cluster_spacing / 2);
+	    }
+	}
+
+      item_char_offset += item->num_chars;
+
+    } /* End of loop stepping through the runs in the line. */
+}
+
+
+/* Steps through the runs in the line, summing all the glyph widths.
+ */
+static PangoGlyphUnit
+recalculate_line_width (PangoLayoutLine *line)
+{
+  PangoGlyphUnit width = 0;
+  GSList *l;
+  int glyph;
+
+  for (l = line->runs; l; l = l->next)
+    {
+      PangoLayoutRun *run = l->data;
+      PangoGlyphString *glyph_string = run->glyphs;
+      PangoGlyphInfo *glyphs = glyph_string->glyphs;
+      int num_glyphs = glyph_string->num_glyphs;
+
+      for (glyph = 0; glyph < num_glyphs; glyph++)
+	width += glyphs[glyph].geometry.width;
+    }
+
+  return width;
+}
+
+
+/* This takes the PangoLayoutLine created in build_line() and reorders the
+ * runs into visual order, and does any justification required.
+ */
+static void
+finish_line (PangoLayout     *layout,
+	     PangoLayoutLine *line,
+	     PangoAttrList   *attrs,
+	     LineInfo	     *line_info)
+{
+  PangoGlyphUnit total_width, total_adjustment;
+  JustificationInfo justification_info;
+  GSList *original_runs;
+  ScriptGroup script_group;
+  int priority;
+
+  /* We gather this information about the ends of the line, so we can trim
+   * any cluster spacing from them in trim_line_ends().
+   */
+  PangoLayoutRun *line_start_run, *line_end_run;
+  ScriptGroup line_start_script_group, line_end_script_group;
+  PangoGlyphUnit line_start_letter_spacing, line_end_letter_spacing;
+
+  /* Copy the list of runs, so we can still use logical order below. */
+  original_runs = g_slist_copy (line->runs);
+
+  /* Reorder the line into visual order, so we can find out the letter
+   * spacing we need to trim from the start and end of the line, if any.
+   */
+  _pango_layout_line_reorder (line);
+
+  /* Get the first & last run in the line, and the letter space in each. */
+  get_line_ends (layout, line, &line_start_run, &line_start_letter_spacing,
+		 &line_start_script_group, &line_end_run,
+		 &line_end_letter_spacing, &line_end_script_group);
+
+  /* Recalculate the natural line width, as it may have changed slightly due
+   * to kerning changes at the breaks.
+   */
+  total_width = recalculate_line_width (line);
+
+  /* Adjust the width of the text to take account of the letter spacing that
+   * we are going to trim from the ends of the line.
+   */
+  total_width -= (line_start_letter_spacing / 2
+		  + line_end_letter_spacing - line_end_letter_spacing / 2);
+
+  /* Calculate the total adjustment we need to make to the line. */
+  total_adjustment = line_info->required_line_width - total_width;
+
+  /* We don't stretch the last line, but we may compress it. For forced
+   * justification (justifying the last line as well) skip this check.
+   */
+  if (line_info->is_last_line && total_adjustment >= 0)
+    {
+      /* Trim the letter spacing at the ends of the line. */
+      trim_line_ends (line_start_run, line_start_letter_spacing, 0,
+		      line_end_run, line_end_letter_spacing, 0);
+
+      g_slist_free (original_runs);
+      return;
+    }
+
+  /* Initialize the justification info for all the script groups. */
+  for (script_group = 0; script_group < NUM_SCRIPT_GROUPS; script_group++)
+    {
+      justification_info.space_multiplier[script_group] = 1;
+      justification_info.cluster_spacing[script_group] = 0;
+    }
+
+  /* We try the justification methods in order of their priority. */
+  for (priority = 0; priority < NUM_PRIORITIES; priority++)
+    {
+      PangoGlyphUnit total_adjustable_width = 0;
+      PangoItemSpacing spacing_method;
+      PangoGlyphUnit adjustable_width[NUM_SCRIPT_GROUPS];
+
+      for (script_group = 0; script_group < NUM_SCRIPT_GROUPS; script_group++)
+	{
+	  spacing_method = spacing_table[script_group][line_info->justification][priority];
+
+	  /* If we have any resizable space or clusters and the matching
+	   * justification setting, add the total width of glyphs in this
+	   * script group.
+	   */
+	  if (((spacing_method & PANGO_ITEM_SPACING_WORD) && line_info->resizable_width[script_group]) ||
+	      ((spacing_method & PANGO_ITEM_SPACING_LETTER) && line_info->num_clusters[script_group] > 1))
+	    {
+	      adjustable_width[script_group] = line_info->total_width[script_group];
+	      total_adjustable_width += line_info->total_width[script_group];
+	    }
+	  else
+	    {
+	      adjustable_width[script_group] = 0;
+	    }
+	}
+
+      /* If we can't adjust anything at this priority, move on to the next. */
+      if (total_adjustable_width == 0)
+	continue;
+
+      for (script_group = 0; script_group < NUM_SCRIPT_GROUPS; script_group++)
+	{
+	  PangoGlyphUnit script_group_adjustment;
+	  PangoGlyphUnit letter_space_adjustment = 0;
+	  PangoGlyphUnit word_space_adjustment = 0;
+
+	  /* Divide up the adjustment according to the proportion of the
+	   * line taken up by glyphs of this script group.
+	   * Do the calculation in floating point to avoid an overflow.
+	   */
+	  script_group_adjustment = (double) adjustable_width[script_group] / total_adjustable_width * total_adjustment;
+	  total_adjustable_width -= adjustable_width[script_group];
+
+	  spacing_method = spacing_table[script_group][line_info->justification][priority];
+
+	  /*
+	   * Calculate letter spacing for the script group.
+	   */
+	  if ((spacing_method & PANGO_ITEM_SPACING_LETTER) &&
+	      line_info->num_clusters[script_group] > 1)
+	    {
+	      double num_clusters = line_info->num_clusters[script_group];
+
+	      /* If both word & letter spacing are being used, we need to
+	       * divide up the adjustment between them. Use a simple fraction
+	       * for now, though a more complex calculation may be better.
+	       */
+	      if ((spacing_method & PANGO_ITEM_SPACING_WORD) &&
+		  line_info->resizable_width[script_group])
+		letter_space_adjustment = script_group_adjustment * 3 / 4;
+	      else
+		letter_space_adjustment = script_group_adjustment;
+
+	      /* Calculate the number of complete cluster spacings that
+	       * will be added. If the clusters at the end of the line are
+	       * using cluster spacing, they only count as half as the
+	       * spacing will be trimmed. But note that if we are
+	       * compressing clusters (i.e. the adjustment is negative), we
+	       * can't compress the ends of the line at all.
+	       */
+	      if (letter_space_adjustment > 0)
+		{
+		  /* We need to check that the items on the ends of the line
+		   * are after any tabs, otherwise they won't be justified
+		   * and we won't need to adjust anything here.
+		   */
+		  if (line_start_script_group == script_group &&
+		      (line_info->last_tab_byte_offset == -1 ||
+		       (line_start_run && line_start_run->item->offset > line_info->last_tab_byte_offset)))
+		    num_clusters -= 0.5;
+
+		  if (line_end_script_group == script_group &&
+		      (line_info->last_tab_byte_offset == -1 ||
+		       (line_end_run && line_end_run->item->offset > line_info->last_tab_byte_offset)))
+		    num_clusters -= 0.5;
+		}
+
+	      /* If there are any clusters left, calculate cluster spacing. */
+	      if (num_clusters > 0.0001)
+		{
+		  PangoGlyphUnit cluster_spacing, min_cluster_spacing;
+
+		  /* Divide the adjustment between the clusters. If the
+		   * adjustment is negative, we need to make sure the cluster
+		   * spacing is rounded down, so we don't overflow.
+		   */
+		  if (letter_space_adjustment > 0)
+		    cluster_spacing = (double) letter_space_adjustment / num_clusters;
+		  else
+		    cluster_spacing = (double) (letter_space_adjustment - (num_clusters - 1)) / num_clusters;
+
+		  /* Calculate the minimum cluster spacing we will allow.
+		   * We don't want the glyphs to start overlapping.
+		   */
+		  min_cluster_spacing = - (line_info->total_width[script_group] / num_clusters) / LETTER_SPACING_MAX_COMPRESSION;
+
+		  if (cluster_spacing < min_cluster_spacing)
+		    cluster_spacing = min_cluster_spacing;
+
+		  justification_info.cluster_spacing[script_group] = cluster_spacing;
+
+		  /* Now recalculate the actual adjustment due to cluster
+		   * spacing, so we can pass on any remainder to word spacing.
+		   */
+		  letter_space_adjustment = cluster_spacing * num_clusters + 0.5;
+		  total_adjustment -= letter_space_adjustment;
+		}
+	      else
+		letter_space_adjustment = 0;
+	    }
+
+	  /*
+	   * Calculate word spacing for the script group.
+	   */
+	  if ((spacing_method & PANGO_ITEM_SPACING_WORD) &&
+	      line_info->resizable_width[script_group])
+	    {
+	      PangoGlyphUnit min_word_space_adjustment;
+
+	      word_space_adjustment = script_group_adjustment - letter_space_adjustment;
+
+	      min_word_space_adjustment = - line_info->resizable_width[script_group] / WORD_SPACING_MAX_COMPRESSION;
+	      if (word_space_adjustment < min_word_space_adjustment)
+		word_space_adjustment = min_word_space_adjustment;
+
+	      justification_info.space_multiplier[script_group] += (double) word_space_adjustment / line_info->resizable_width[script_group];
+
+	      total_adjustment -= word_space_adjustment;
+	    }
+
+	} /* End of loop stepping through script groups. */
+
+      /* If no more adjustment is needed we are done. */
+      if (total_adjustment == 0)
+	break;
+
+    } /* End of loop stepping through priorities. */
+
+#if 0
+  g_print ("Justifying line start_byte_offset: %i length: %i\n",
+	   line->start_index, line->length);
+#endif
+
+  justification_info.line_start_run = line_start_run;
+  justification_info.line_end_run = line_end_run;
+  justify_line (layout, original_runs, line_info, &justification_info);
+
+  /* Trim the letter spacing at the ends of the line. */
+  trim_line_ends (line_start_run, line_start_letter_spacing,
+		  justification_info.line_start_adjustment,
+		  line_end_run, line_end_letter_spacing,
+		  justification_info.line_end_adjustment);
+
+  g_slist_free (original_runs);
+}
+
+
+#ifdef DEBUG_LINE_OVERFLOW
+static void
+check_line_overflow (PangoLayout     *layout,
+		     PangoLayoutLine *line,
+		     LineInfo	     *line_info)
+{
+  GSList *l;
+  PangoGlyphUnit width = 0;
+  int glyph_index;
+
+  /* If we have an unlimited width, we can't overflow. */
+  if (line_info->required_line_width == -1)
+    return;
+
+  /* Step through the runs in the line, summing all the glyph widths. */
+  width =  recalculate_line_width (line);
+
+  if (width > line_info->required_line_width)
+    {
+      g_print ("### Line Overflow Width: %i Desired: %i Overflow: %i\n",
+	       width, line_info->required_line_width,
+	       width - line_info->required_line_width);
+      g_print ("    Text: %.60s\n",
+	       layout->text + line_info->line_start_byte_offset);
+    }
+
+  /* This checks for underflow. Currently using word-spacing we never
+   * underflow, but letter spacing does, since it doesn't try to spread
+   * out any remainder across the line.
+   */
+#if 0
+  if (!line_info->is_last_line && width < line_info->required_line_width)
+    {
+      g_print ("### Line Underflow Width: %i Desired: %i Underflow: %i\n",
+	       width, line_info->required_line_width,
+	       width - line_info->required_line_width);
+      g_print ("    Text: %.60s\n",
+	       layout->text + line_info->line_start_byte_offset);
+    }
+#endif
+}
+#endif
+
+
+/* This builds the PangoLayoutLine, given the LineInfo data about the break
+ * point to use.
+ */
+static void
+build_line (PangoLayout                *layout,
+	    GArray		       *items_data,
+	    int				item_index,
+	    LineInfo		       *line_info,
+	    PangoDirection		base_dir,
+	    PangoAttrList              *attrs)
+{
+  PangoLayoutLine *line = NULL;
+  PangoLayoutRun *run;
+  PangoItem *item, *run_item;
+  PangoGlyphString *glyphs;
+  ItemData *item_data;
+  const char *text = layout->text;
+  int item_char_offset;
+  gboolean last_run = FALSE;
+
+#if 0
+  g_print ("Building line from %i (Char:%i) to %i (%i) Next line: %i (%i)\n",
+	   line_info->line_start_byte_offset, line_info->line_start_char_offset,
+	   line_info->line_end_byte_offset, line_info->line_end_char_offset,
+	   line_info->next_line_byte_offset, line_info->next_line_char_offset);
+#endif
+
+  /* Create a new PangoLayoutLine. */
+  line = _pango_layout_line_new (layout);
+  line->start_index = line_info->line_start_byte_offset;
+  line->length = line_info->line_end_byte_offset - line->start_index;
+  line->is_paragraph_start = (line_info->line_num == 0) ? TRUE : FALSE;
+  line->resolved_dir = _pango_layout_resolve_dir (base_dir);
+
+  /* If the line starts at the end of the text, just add an empty line. */
+  if (item_index >= items_data->len)
+    {
+      layout->lines = g_slist_prepend (layout->lines, line);
+      return;
+    }
+
+  /* Step through each PangoItem in the line. */
+  for (;;)
+    {
+      item_data = &g_array_index (items_data, ItemData, item_index);
+      item = item_data->item_node->data;
+      item_char_offset = item_data->item_char_offset;
+
+      /* Check if this run will complete the line. */
+      if (item->offset + item->length >= line_info->next_line_byte_offset)
+	last_run = TRUE;
+
+      /* Split the item, if needed. The new run_item will cover up to the
+       * start of the next line, and the original item contains the rest.
+       * Note that we may have to trim whitespace off the end of run_item.
+       */
+      if (item->offset + item->length > line_info->next_line_byte_offset)
+	{
+	  int run_item_bytes, run_item_chars;
+
+	  run_item_bytes = line_info->next_line_byte_offset - item->offset;
+	  run_item_chars = line_info->next_line_char_offset - item_char_offset;
+	  run_item = pango_item_split (item, run_item_bytes, run_item_chars);
+
+	  /* Update the ItemData to reflect the split. */
+	  item_data->item_char_offset += run_item_chars;
+
+	  /* Since we split the item, we can't use the glyphstring. */
+	  if (item_data->glyphs)
+	    {
+	      pango_glyph_string_free (item_data->glyphs);
+	      item_data->glyphs = NULL;
+	    }
+	}
+      else
+	run_item = item;
+
+      /* Add the run from the item. */
+      glyphs = NULL;
+      if (text[item->offset] == '\t')
+	{
+	  glyphs = pango_glyph_string_new ();
+	  _pango_layout_shape_tab (line, glyphs);
+	}
+      else if (item_data->properties.shape_set)
+	{
+	  glyphs = item_data->glyphs;
+	  /* Make sure we don't free the glyphs twice. */
+	  item_data->glyphs = NULL;
+	}
+      else if (run_item->offset < line_info->line_end_byte_offset)
+	{
+	  /* We need to cut off any bytes after end_offset. */
+	  if (run_item->offset + run_item->length > line_info->line_end_byte_offset)
+	    {
+	      run_item->length = line_info->line_end_byte_offset - run_item->offset;
+	      run_item->num_chars = line_info->line_end_char_offset - item_char_offset;
+	    }
+
+	  if (run_item->length > 0)
+	    {
+	      /* If we've already created a glyphstring in create_items_data()
+	       * and the item length is still the same, we can reuse it.
+	       */
+	      if (item_data->glyphs &&
+		  run_item->num_chars == item_data->num_chars)
+		{
+		  glyphs = item_data->glyphs;
+		  /* Make sure we don't free the glyphs twice. */
+		  item_data->glyphs = NULL;
+		}
+	      else
+		{
+		  glyphs = pango_glyph_string_new ();
+		  pango_shape (text + run_item->offset, run_item->length,
+			       &run_item->analysis, glyphs);
+		  if (item_data->properties.letter_spacing)
+		    letter_space (glyphs, item_data->properties.letter_spacing);
+		}
+	    }
+	}
+
+      if (glyphs)
+	{
+	  /* If we have some glyphs, create a PangoLayoutRun. */
+	  run = g_slice_new (PangoLayoutRun);
+	  run->item = run_item;
+	  run->glyphs = glyphs;
+	  line->runs = g_slist_prepend (line->runs, run);
+	}
+      else
+	{
+	  /* If there are no glyphs, we don't need run_item, so free it. */
+      	  pango_item_free (run_item);
+	}
+
+      /* If that run completed the line we are done. */
+      if (last_run)
+	break;
+
+      item_index++;
+    }
+
+
+  /* The runs were prepended, so reverse them back to logical order. */
+  line->runs = g_slist_reverse (line->runs);
+
+  /* We don't justify the line in single paragraph mode or when the width
+   * is unlimited, or when ellipsization is being used.
+   */
+  if (layout->single_paragraph || layout->width == -1 ||
+      layout->ellipsize != PANGO_ELLIPSIZE_NONE || !layout->justify)
+    finish_line_without_justification (layout, line, attrs);
+  else
+    finish_line (layout, line, attrs, line_info);
+
+#ifdef DEBUG_LINE_OVERFLOW
+  check_line_overflow (layout, line, line_info);
+#endif
+
+  /* Add the completed line to the layout. */
+  layout->lines = g_slist_prepend (layout->lines, line);
+}
+
+
+/* This creates an array containing a few bits of information about each
+ * PangoItem in the paragraph, e.g. the logical widths of each character.
+ * It is used while we are stepping through the paragraph looking for the
+ * best break positions.
+ */
+static GArray*
+create_items_data (PangoLayout                *layout,
+		   GList                      *items,
+		   int			       start_char_offset,
+		   gboolean		       create_log_widths,
+		   PangoJustification	      *auto_justification,
+		   GArray		      *single_items_data,
+		   ItemData		      *single_item_data)
+{
+
+  GArray *items_data;
+  GList *l;
+  PangoItem *item;
+  ItemData tmp_item_data, *item_data;
+  int item_char_offset;
+  ScriptGroup first_script_group = SCRIPT_GROUP_NONE;
+
+  /* Special case for only one item, to avoid several mallocs. */
+  if (items && items->next == NULL)
+    {
+      items_data = single_items_data;
+      single_items_data->data = (gpointer) single_item_data;
+      single_items_data->len = 1;
+      item_data = single_item_data;
+    }
+  else
+    {
+      items_data = g_array_sized_new (FALSE, FALSE, sizeof (ItemData), 32);
+      item_data = &tmp_item_data;
+    }
+
+  item_char_offset = start_char_offset;
+  for (l = items; l; l = l->next)
+    {
+      item = l->data;
+
+      item_data->item_node = l;
+      item_data->item_char_offset = item_char_offset;
+      item_data->num_chars = item->num_chars;
+      item_data->glyphs = NULL;
+      item_data->log_widths = NULL;
+      item_data->script_group = get_item_script_group (layout, item);
+      _pango_layout_get_item_properties (item, &item_data->properties);
+
+      /* Find the first script group that isn't SCRIPT_GROUP_NONE. */
+      if (first_script_group == SCRIPT_GROUP_NONE &&
+	  item_data->script_group != SCRIPT_GROUP_NONE)
+	first_script_group = item_data->script_group;
+
+      /* Convert the item to glyphs. */
+      if (create_log_widths && layout->text[item->offset] != '\t')
+	{
+	  item_data->glyphs = pango_glyph_string_new ();
+
+	  if (item_data->properties.shape_set)
+	    {
+	      _pango_layout_imposed_shape (layout->text + item->offset,
+					   item->num_chars,
+					   item_data->properties.shape_ink_rect,
+					   item_data->properties.shape_logical_rect,
+					   item_data->glyphs);
+	    }
+	  else
+	    {
+	      pango_shape (layout->text + item->offset, item->length,
+			   &item->analysis, item_data->glyphs);
+	    }
+
+	  if (item_data->properties.letter_spacing)
+	    letter_space (item_data->glyphs,
+			  item_data->properties.letter_spacing);
+
+	  /* Calculate the logical width of each character. */
+	  item_data->log_widths = g_new (PangoGlyphUnit, item->num_chars);
+	  pango_glyph_string_get_logical_widths (item_data->glyphs,
+						 layout->text + item->offset,
+						 item->length,
+						 item->analysis.level,
+						 item_data->log_widths);
+	}
+
+      if (items_data != single_items_data)
+	g_array_append_val (items_data, tmp_item_data);
+      item_char_offset += item->num_chars;
+    }
+
+  /* If the justification setting is currently PANGO_JUSTIFICATION_AUTO, we
+   * choose a reasonable justification setting based on the first non-NONE
+   * script group found in the paragraph.
+   */
+  if (auto_justification && *auto_justification == PANGO_JUSTIFICATION_AUTO)
+    *auto_justification = auto_justification_table[first_script_group];
+
+  return items_data;
+}
+
+
+/* This frees the array created above in create_items_data(). We only need
+ * to free the log_widths and the GArray itself.
+ */
+static void
+free_items_data (GArray *items_data,
+		 GArray	*single_items_data)
+{
+  int i;
+
+  for (i = 0; i < items_data->len; i++)
+    {
+      ItemData *item_data = &g_array_index (items_data, ItemData, i);
+
+      if (item_data->glyphs)
+	pango_glyph_string_free (item_data->glyphs);
+      g_free (item_data->log_widths);
+    }
+
+  if (items_data != single_items_data)
+    g_array_free (items_data, TRUE);
+}
+
+
+/* This returns the next tab position after the given distance.
+ */
+static int
+find_next_tab_position (PangoLayout  *layout,
+			int          distance)
+{
+  int i, tab_pos;
+
+  for (i=0;;i++)
+    {
+      tab_pos = _pango_layout_get_tab_pos (layout, i);
+      if (tab_pos > distance)
+	return tab_pos;
+    }
+}
+
+
+/* This is copied from pango-layout.c
+ */
+static inline int
+direction_simple (PangoDirection d)
+{
+  switch (d)
+    {
+    case PANGO_DIRECTION_LTR :	    return 1;
+    case PANGO_DIRECTION_RTL :	    return -1;
+    case PANGO_DIRECTION_TTB_LTR :  return 1;
+    case PANGO_DIRECTION_TTB_RTL :  return -1;
+    case PANGO_DIRECTION_WEAK_LTR : return 1;
+    case PANGO_DIRECTION_WEAK_RTL : return -1;
+    case PANGO_DIRECTION_NEUTRAL :  return 0;
+    /* no default compiler should complain if a new values is added */
+    }
+  /* not reached */
+  return 0;
+}
+
+
+/* These are the indices into the total_width[], resizable_width[] and
+ * num_clusters[] arrays:
+ *
+ *  PANGO_POS_TOTAL holds the total widths/counts up to the current position.
+ *
+ *  PANGO_POS_TO_BREAK holds the amounts up to the last preferred break
+ *    position, which may be a bit before TOTAL as we normally trim whitespace.
+ *
+ *  PANGO_POS_OVERFLOW may be used to hold the amounts at the point just before
+ *    we overflowed the line. This is used for the last line of the paragraph
+ *    if we want to keep whitespace only up to the point it overflows the line.
+ */
+#define	PANGO_POS_TOTAL		0
+#define	PANGO_POS_TO_BREAK	1
+#define	PANGO_POS_OVERFLOW	2
+
+
+/* This is used in layout_with_specific_width(). It holds data about the
+ * current position in the paragraph, and the best break up to this point.
+ */
+typedef struct _LayoutState LayoutState;
+struct _LayoutState
+{
+  /* The array of ItemData, holding info on each PangoItem. */
+  GArray *items_data;
+
+  /* The current item in items_data, and the item at the start of the line. */
+  int item_index;
+  int line_start_item_index;
+
+  /* The required line width of the current line. */
+  PangoGlyphUnit required_line_width;
+
+  /* The required line width of all the following lines. */
+  PangoGlyphUnit normal_required_line_width;
+
+  /* The character number within the current PangoItem. */
+  int char_num;
+
+  /* The character number in the log_widths array of the current PangoItem. */
+  int log_widths_char_num;
+
+  /* The current byte and char position within the layout text. */
+  const char *byte_pos;
+  int char_offset;
+
+  /* The byte and char position just after the current preferred break. */
+  const char *line_end_byte_pos;
+  int line_end_char_offset;
+
+  /* Whether we use line breaks and/or char breaks to break lines. */
+  gboolean use_line_breaks;
+  gboolean use_char_breaks;
+
+  /* For ragged right LTR text (and ragged left RTL) we allow trailing
+   * whitespace at the end of each line, as long as it doesn't overflow.
+   * This makes it slightly easier to edit the text at the ends of lines.
+   * We can't do this for ragged left or centered text, since the extra
+   * whitespace would mess up the position of the line.
+   */
+  gboolean allow_trailing_whitespace;
+
+  /* The minimum letter spacing we've seen in all the items in the line so far.
+   * We use this to estimate how much letter spacing will be trimmed from the
+   * ends of the line.
+   */
+  PangoGlyphUnit min_letter_spacing;
+
+  /* These are just used as an optimization. If there is only a single item,
+   * we use these to avoid several mallocs.
+   */
+  GArray single_items_data;
+  ItemData single_item_data;
+
+
+  /*
+   * These are are reset before each line with reset_layout_state().
+   */
+
+  /* The total width of all glyphs in the line so far. */
+  PangoGlyphUnit total_distance;
+
+  /* The total width of compressible glyphs in the line so far. */
+  PangoGlyphUnit total_compressible_width;
+
+  /* The width of all the glyphs up to the last preferred break position. */
+  PangoGlyphUnit break_distance;
+
+  /* The width of compressible glyphs at the last preferred break position. */
+  PangoGlyphUnit break_compressible_width;
+
+  /* These are the total widths of glyphs, resizable space and number of
+   * clusters up to the current position, the preferred break position, and
+   * the point we overflowed the line. (See the comments on TOTAL, TO_BREAK
+   * and OVERFLOW above.)
+   */
+  PangoGlyphUnit total_width[NUM_SCRIPT_GROUPS][3];
+  PangoGlyphUnit resizable_width[NUM_SCRIPT_GROUPS][3];
+  int num_clusters[NUM_SCRIPT_GROUPS][3];
+
+  /* This is the information we keep for the best break found so far. */
+  int best_break_item_index;
+  int best_break_score;
+  gboolean best_break_is_line_break;
+  int best_break_log_widths_char_num;
+  PangoGlyphUnit best_break_natural_line_width;
+
+  /* The byte offset of the last tab seen in the current line. */
+  int last_tab_byte_offset;
+
+  /* This is TRUE if we overflowed the line with whitespace. The byte and
+   * char offsets hold the position of the first character that overflows.
+   * This is only used for the last line of the text, where we only trim
+   * trailing whitespace that overflows the line.
+   */
+  gboolean overflowed;
+  int overflow_byte_offset, overflow_char_offset;
+};
+
+
+/* Resets the LayoutState at the start of each line.
+ */
+static void
+reset_layout_state (LayoutState *state)
+{
+  ScriptGroup script_group;
+
+  state->total_distance = 0;
+  state->break_distance = 0;
+  state->total_compressible_width = 0;
+  state->break_compressible_width = 0;
+
+  for (script_group = 0; script_group < NUM_SCRIPT_GROUPS; script_group++)
+    {
+      state->total_width[script_group][PANGO_POS_TOTAL] = 0;
+      state->resizable_width[script_group][PANGO_POS_TOTAL] = 0;
+      state->num_clusters[script_group][PANGO_POS_TOTAL] = 0;
+
+      state->total_width[script_group][PANGO_POS_TO_BREAK] = 0;
+      state->resizable_width[script_group][PANGO_POS_TO_BREAK] = 0;
+      state->num_clusters[script_group][PANGO_POS_TO_BREAK] = 0;
+    }
+
+  state->best_break_item_index = -1;
+  state->best_break_score = G_MAXINT;
+  state->best_break_is_line_break = FALSE;
+  state->best_break_log_widths_char_num = -1;
+  state->best_break_natural_line_width = 0;
+
+  state->last_tab_byte_offset = -1;
+
+  state->overflowed = FALSE;
+  state->overflow_byte_offset = -1;
+  state->overflow_char_offset = -1;
+}
+
+
+/* Initializes the LayoutState and LineInfo structs, ready to start
+ * iterating over the text in layout_with_specific_width().
+ */
+static void
+init_layout_state (PangoLayout		*layout,
+		   GList                *items,
+		   PangoDirection	 base_dir,
+		   int			 start_char_offset,
+		   LayoutState		*state,
+		   LineInfo		*line_info)
+{
+  ItemData *item_data;
+  PangoItem *item;
+
+  reset_layout_state (state);
+
+  /* If the justification setting is AUTO, create_items_data() will set it
+   * according to the text at the start of the paragraph.
+   */
+  line_info->justification = layout->justify ? PANGO_JUSTIFICATION_AUTO : PANGO_JUSTIFICATION_NONE;
+  state->items_data = create_items_data (layout, items, start_char_offset,
+					 TRUE, &line_info->justification,
+					 &state->single_items_data,
+					 &state->single_item_data);
+
+  /* Normally we trim all whitespace from the ends of lines (except for the
+   * last line in the paragraph). But for ragged right LTR text (and ragged
+   * left RTL) we leave the whitespace if possible to make editing easier, and
+   * only trim it if it overflows. But we need to check which alignment is
+   * actually being used. See pango_layout_set_auto_dir().
+   */
+  state->allow_trailing_whitespace = FALSE;
+  if (!layout->justify)
+    {
+      PangoAlignment allow_trailing_whitespace_alignment = PANGO_ALIGN_LEFT;
+
+      if (layout->auto_dir &&
+	  direction_simple (_pango_layout_resolve_dir (base_dir)) == -direction_simple (pango_context_get_base_dir (layout->context)))
+	allow_trailing_whitespace_alignment = PANGO_ALIGN_RIGHT;
+
+      if (layout->alignment == allow_trailing_whitespace_alignment)
+	state->allow_trailing_whitespace = TRUE;
+    }
+
+  /* Calculate the width to use for the first & subsequent lines. */
+  if (layout->indent >= 0)
+    {
+      state->required_line_width = layout->width - layout->indent;
+      state->normal_required_line_width = layout->width;
+    }
+  else
+    {
+      state->required_line_width = layout->width;
+      state->normal_required_line_width = layout->width + layout->indent;
+    }
+
+  /* If the wrap mode is PANGO_WRAP_WORD we don't check for char breaks and if
+   * it is PANGO_WRAP_CHAR we don't check for line breaks.
+   */
+  state->use_line_breaks = state-> use_char_breaks = TRUE;
+  if (layout->wrap == PANGO_WRAP_WORD)
+    state->use_char_breaks = FALSE;
+  else if (layout->wrap == PANGO_WRAP_CHAR)
+    state->use_line_breaks = FALSE;
+
+  item_data = &g_array_index (state->items_data, ItemData, 0);
+  item = item_data->item_node->data;
+
+  state->item_index = state->line_start_item_index = 0;
+  state->char_offset = state->line_end_char_offset = start_char_offset;
+  state->byte_pos = state->line_end_byte_pos = layout->text + item->offset;
+  state->char_num = state->log_widths_char_num = 0;
+  state->min_letter_spacing = item_data->properties.letter_spacing;
+
+  line_info->line_num = 0;
+  line_info->is_last_line = FALSE;
+  line_info->line_start_byte_offset = state->byte_pos - layout->text;
+  line_info->line_start_char_offset = state->char_offset;
+
+#ifdef DEBUG_BREAKS
+  g_print ("##############################################################\n");
+  g_print ("Required Line Width:%7i Text:%.40s\n",
+	   state->required_line_width, byte_pos);
+#endif
+}
+
+
+/* Stores info about the current position into the LineInfo struct, as it is
+ * the preferred break up to this point in the line.
+ */
+static void
+save_break (PangoLayout		*layout,
+	    LayoutState		*state,
+	    LineInfo		*line_info)
+{
+  int i, j = PANGO_POS_TO_BREAK;
+
+  line_info->line_end_byte_offset  = state->line_end_byte_pos - layout->text;
+  line_info->line_end_char_offset  = state->line_end_char_offset;
+  line_info->next_line_byte_offset = state->byte_pos - layout->text;
+  line_info->next_line_char_offset = state->char_offset;
+  line_info->last_tab_byte_offset  = state->last_tab_byte_offset;
+  line_info->required_line_width   = state->required_line_width;
+  line_info->min_letter_spacing    = state->min_letter_spacing;
+
+  /* Check if this is the last line. */
+  if (state->item_index < 0)
+    {
+      line_info->is_last_line = TRUE;
+
+      if (state->overflowed)
+	{
+	  /* If we overflowed the last line (with whitespace), we
+	   * need to trim any whitespace after the overflow.
+	   */
+	  j = PANGO_POS_OVERFLOW;
+	  line_info->line_end_byte_offset = state->overflow_byte_offset;
+	  line_info->line_end_char_offset = state->overflow_char_offset;
+	}
+      else
+	{
+	  /* If we didn't overflow we include all whitespace on the last line.
+	   * But if trailing whitespace is allowed (i.e. ragged right text)
+	   * this has already been handled, so we don't need to do that here.
+	   */
+	  j = PANGO_POS_TOTAL;
+	  if (!state->allow_trailing_whitespace)
+	    {
+	      line_info->line_end_byte_offset = line_info->next_line_byte_offset;
+	      line_info->line_end_char_offset = line_info->next_line_char_offset;
+	    }
+	}
+    }
+
+  for (i = 0; i < NUM_SCRIPT_GROUPS; i++)
+    {
+      line_info->total_width[i]	    = state->total_width[i][j];
+      line_info->resizable_width[i] = state->resizable_width[i][j];
+      line_info->num_clusters[i]    = state->num_clusters[i][j];
+    }
+}
+
+
+/* Handles a tab during layout_with_specific_width(). It moves to the next
+ * tab position and resets all justification info (since we can't justify
+ * text before tabs).
+ */
+static void
+layout_tab (PangoLayout		*layout,
+	    LayoutState		*state)
+{
+  int i;
+
+  state->last_tab_byte_offset = state->byte_pos - layout->text;
+  state->total_distance = find_next_tab_position (layout, state->total_distance);
+  state->break_distance = state->total_distance;
+
+  /* Any resizable space & clusters before the tab is forgotten. */
+  for (i = 0; i < NUM_SCRIPT_GROUPS; i++)
+    {
+      state->total_width[i][PANGO_POS_TOTAL] = 0;
+      state->resizable_width[i][PANGO_POS_TOTAL] = 0;
+      state->num_clusters[i][PANGO_POS_TOTAL] = 0;
+
+      state->total_width[i][PANGO_POS_TO_BREAK] = 0;
+      state->resizable_width[i][PANGO_POS_TO_BREAK] = 0;
+      state->num_clusters[i][PANGO_POS_TO_BREAK] = 0;
+    }
+
+  state->total_compressible_width = state->break_compressible_width = 0;
+  state->byte_pos = g_utf8_next_char (state->byte_pos);
+  state->line_end_byte_pos = state->byte_pos;
+  state->line_end_char_offset = state->char_offset + 1;
+}
+
+
+/* This does the layout when we have a specific layout width. It steps through
+ * the characters in a line, scoring each potential break point. When it
+ * reaches the end of the line it chooses the best break, and calls
+ * build_line() to build the PangoLayoutLine. It then starts again at the
+ * best break position. It repeats this until it reaches the end of the text.
+ */
+static void
+layout_with_specific_width (PangoLayout              *layout,
+			    GList                    *items,
+			    PangoDirection	      base_dir,
+			    int			      start_char_offset,
+			    PangoAttrList            *attrs)
+{
+  LayoutState state;
+  LineInfo line_info = { 0 };
+  ItemData *item_data;
+  PangoItem *item;
+  PangoGlyphUnit max_compression = 0;
+  gboolean need_full_copy = FALSE;
+  int is_line_break = 0, is_char_break = 0;
+  int i;
+
+  init_layout_state (layout, items, base_dir, start_char_offset,
+		     &state, &line_info);
+
+  item_data = &g_array_index (state.items_data, ItemData, 0);
+  item = item_data->item_node->data;
+
+  /* This is the main loop. It steps through the paragraph computing the best
+   * break positions to use.
+   */
+  for (;;)
+    {
+      PangoLogAttr log_attr = layout->log_attrs[state.char_offset];
+
+      /* Check if there is a potential line or char break immediately before
+       * this character.
+       */
+      if (state.use_line_breaks)
+	is_line_break = log_attr.is_line_break;
+      if (state.use_char_breaks)
+	is_char_break = log_attr.is_char_break;
+
+      /* We assume the end of the text is a line & char break position.
+       * (item_index is set to -1 when the end of the text is reached.)
+       */
+      if (state.item_index < 0)
+	{
+	  if (state.use_line_breaks)
+	    is_line_break = TRUE;
+	  if (state.use_char_breaks)
+	    is_char_break = TRUE;
+	}
+
+      /* Check if we can break here. */
+      if (is_line_break || is_char_break)
+	{
+	  PangoGlyphUnit natural_line_width;
+	  int break_score;
+
+	  /* This is the maximum amount we could subtract from the line width
+	   * by compressing all the resizable spaces.
+	   */
+	  if (layout->justify)
+	    max_compression = state.break_compressible_width / WORD_SPACING_MAX_COMPRESSION;
+
+	  /* Calculate the width of the line up to the break, which is just
+	   * the total width of all the clusters, minus the minimum letter
+	   * spacing, since we'll trim the letter spacing off the ends.
+	   * If the letter spacing on either end turns out to be more than the
+	   * minimum we'll have to stretch the line a little.
+	   */
+	  natural_line_width = state.break_distance - state.min_letter_spacing;
+	  if (natural_line_width < 0)
+	    natural_line_width = 0;
+
+	  /* Calculate a score for the break. We just use the difference from
+	   * the natural line width to the required line width.
+	   */
+	  break_score = natural_line_width - state.required_line_width;
+	  if (break_score < 0)
+	    break_score = - break_score;
+
+#ifdef DEBUG_BREAKS
+	  g_print ("Break Natural Width:%7i Score:%7i MaxComp:%6i ResizWidth:%6i Text After:%.20s\n",
+		   natural_line_width, break_score, max_compression,
+		   break_compressible_width, byte_pos);
+#endif
+
+	  /* See if this break is better than the previous one. Note that line
+	   * breaks are preferred over char breaks, and low scores are best.
+	   *
+	   * The last clause with break_score == best_break_score is used to
+	   * trim whitespace off the ends of lines which have overflowed.
+	   * We don't want to start the next line with whitespace.
+	   */
+	  if ((natural_line_width - max_compression <= state.required_line_width &&
+	       (is_line_break || !state.best_break_is_line_break) &&
+	       (break_score <= state.best_break_score)) ||
+	      (state.best_break_score == G_MAXINT) ||
+	      (break_score == state.best_break_score &&
+	       (state.best_break_natural_line_width - max_compression > state.required_line_width)))
+	    {
+	      save_break (layout, &state, &line_info);
+
+	      state.best_break_item_index	   = state.item_index;
+	      state.best_break_is_line_break	   = is_line_break;
+	      state.best_break_score		   = break_score;
+	      state.best_break_natural_line_width  = natural_line_width;
+	      state.best_break_log_widths_char_num = state.log_widths_char_num;
+	    }
+
+	  /* Check if we've definitely gone past the end of the line. This can
+	   * happen if we've reached the end of the text, or we've reached a
+	   * mandatory break, or we've overflowed the required_line_width.
+	   * Note that we don't stop at whitespace characters as we want to
+	   * trim them if at all possible.
+	   */
+	  if (state.item_index < 0 ||
+	      (natural_line_width - max_compression > state.required_line_width && !log_attr.is_white) ||
+	      log_attr.is_mandatory_break)
+	    {
+	      /* Build the line up to the best break we've found. */
+	      build_line (layout, state.items_data,
+			  state.line_start_item_index,
+			  &line_info, base_dir, attrs);
+
+	      /* If we've reached the end of the paragraph, exit the loop. */
+	      if (state.best_break_item_index < 0)
+		break;
+
+	      /* Go back to the break position and carry on from there. */
+	      state.item_index = state.best_break_item_index;
+	      state.log_widths_char_num = state.best_break_log_widths_char_num;
+
+	      item_data = &g_array_index (state.items_data, ItemData,
+					  state.item_index);
+	      item = item_data->item_node->data;
+
+	      reset_layout_state (&state);
+	      state.line_start_item_index = state.item_index;
+	      state.char_num = 0;
+	      state.char_offset = item_data->item_char_offset;
+	      state.byte_pos = layout->text + line_info.next_line_byte_offset;
+	      state.line_end_byte_pos = state.byte_pos;
+	      state.min_letter_spacing = item_data->properties.letter_spacing;
+	      state.required_line_width = state.normal_required_line_width;
+
+	      line_info.line_start_byte_offset = line_info.next_line_byte_offset;
+	      line_info.line_start_char_offset = state.char_offset;
+	      line_info.line_num++;
+
+	      log_attr = layout->log_attrs[state.char_offset];
+	      need_full_copy = FALSE;
+
+#ifdef DEBUG_BREAKS
+	      g_print ("\nRequired Line Width:%7i Text:%.40s\n",
+		       state.required_line_width, byte_pos);
+#endif
+	    }
+
+	} /* if is_line_break or is_char_break. */
+
+      /* If we've reached the end of the paragraph we don't need to adjust
+       * any widths or positions.
+       */
+      if (state.item_index < 0)
+	continue;
+
+      /* Check for a tab character. */
+      if (*state.byte_pos == '\t')
+	{
+	  layout_tab (layout, &state);
+	}
+      else
+	{
+	  /* Add on the width of the current char. */
+	  PangoGlyphUnit log_width = item_data->log_widths[state.log_widths_char_num];
+
+	  state.total_distance += log_width;
+
+	  /* We remember the position we first overflowed, in case this is
+	   * the last line and we need to trim any whitespace overflow.
+	   * But ragged right is handled separately so ignore that here.
+	   */
+	  if (log_attr.is_white && !state.allow_trailing_whitespace &&
+	      !state.overflowed &&
+	      state.total_distance - state.min_letter_spacing - max_compression > state.required_line_width)
+	    {
+	      state.overflowed = TRUE;
+
+	      state.overflow_byte_offset = state.byte_pos - layout->text;
+	      state.overflow_char_offset = state.char_offset;
+
+	      for (i = 0; i < NUM_SCRIPT_GROUPS; i++)
+		{
+		  state.total_width[i][PANGO_POS_OVERFLOW] = state.total_width[i][PANGO_POS_TOTAL];
+		  state.resizable_width[i][PANGO_POS_OVERFLOW] = state.resizable_width[i][PANGO_POS_TOTAL];
+		  state.num_clusters[i][PANGO_POS_OVERFLOW] = state.num_clusters[i][PANGO_POS_TOTAL];
+		}
+	    }
+
+	  state.total_width[item_data->script_group][PANGO_POS_TOTAL] += log_width;
+
+	  state.byte_pos = g_utf8_next_char (state.byte_pos);
+
+	  /* We need to remember how many clusters are in the line, in case we
+	   * need to do letter spacing for justification. Note that we use
+	   * char_offset + 1 since that means we're at the end of a cluster.
+	   */
+	  if (layout->log_attrs[state.char_offset + 1].is_cursor_position)
+	    state.num_clusters[item_data->script_group][PANGO_POS_TOTAL]++;
+
+	  /* We need to remember how much resizable space there is in the line.
+	   */
+	  if (log_attr.is_resizable)
+	    {
+	      /* We only consider scripts that use word spacing in the top
+	       * priority when calculating the maximum compression.
+	       */
+	      if (spacing_table[item_data->script_group][line_info.justification][0] & PANGO_ITEM_SPACING_WORD)
+		state.total_compressible_width += log_width;
+	      state.resizable_width[item_data->script_group][PANGO_POS_TOTAL] += log_width;
+	    }
+
+	  /* Check if this is the preferred break point at this position. We
+	   * normally trim whitespace at the ends of lines, so the preferred
+	   * break point may be a bit behind the current position.
+	   * But for ragged text we allow whitespace at the end of the line
+	   * as long as it fits in the required width.
+	   */
+	  if (!log_attr.is_white ||
+	      (state.allow_trailing_whitespace && state.total_distance /* FIXME: - min_letter_spacing? */ <= state.required_line_width))
+	    {
+	      /* Update the info about the current preferred break point. */
+	      state.break_distance = state.total_distance;
+	      state.break_compressible_width = state.total_compressible_width;
+
+	      state.line_end_byte_pos = state.byte_pos;
+	      state.line_end_char_offset = state.char_offset + 1;
+
+	      /* This is an optimization. We only need to copy all the arrays
+	       * if we've changed to a new PangoItem since the last copy.
+	       * Otherwise we only need to copy the info for the current script
+	       * group, since the others won't have changed at all.
+	       */
+	      if (need_full_copy)
+		{
+		  need_full_copy = FALSE;
+		  for (i = 0; i < NUM_SCRIPT_GROUPS; i++)
+		    {
+		      state.total_width[i][PANGO_POS_TO_BREAK] = state.total_width[i][PANGO_POS_TOTAL];
+		      state.resizable_width[i][PANGO_POS_TO_BREAK] = state.resizable_width[i][PANGO_POS_TOTAL];
+		      state.num_clusters[i][PANGO_POS_TO_BREAK] = state.num_clusters[i][PANGO_POS_TOTAL];
+		    }
+		}
+	      else
+		{
+		  i = item_data->script_group;
+		  state.total_width[i][PANGO_POS_TO_BREAK] = state.total_width[i][PANGO_POS_TOTAL];
+		  state.resizable_width[i][PANGO_POS_TO_BREAK] = state.resizable_width[i][PANGO_POS_TOTAL];
+		  state.num_clusters[i][PANGO_POS_TO_BREAK] = state.num_clusters[i][PANGO_POS_TOTAL];
+		}
+	    }
+	}
+
+      /* Move on to the next char. If we've reached the end of the item we
+       * move on to the next item in the array. When we reach the end of the
+       * array we set item_index to -1, and set item and item_data to NULL.
+       */
+      state.char_offset++;
+      state.log_widths_char_num++;
+      if (++state.char_num == item->num_chars)
+	{
+	  state.item_index++;
+	  state.char_num = state.log_widths_char_num = 0;
+	  need_full_copy = TRUE;
+	  if (state.item_index < state.items_data->len)
+	    {
+	      item_data = &g_array_index (state.items_data, ItemData,
+					  state.item_index);
+	      item = item_data->item_node->data;
+	      if (item_data->properties.letter_spacing < state.min_letter_spacing)
+		state.min_letter_spacing = item_data->properties.letter_spacing;
+	    }
+	  else
+	    {
+	      state.item_index = -1;
+	      item_data = NULL;
+	      item = NULL;
+	    }
+	}
+
+    } /* End of main loop stepping through the paragraph. */
+
+  free_items_data (state.items_data, &state.single_items_data);
+}
+
+
+/* This does the layout for single-paragraph mode, where we want all text in
+ * the entire PangoLayout on one line with no breaks at all (for use in
+ * GtkEntry).
+ */
+static void
+layout_single_paragraph (PangoLayout                *layout,
+			 GList                      *items,
+			 PangoDirection		     base_dir,
+			 PangoAttrList              *attrs)
+{
+  GArray *items_data, single_items_data;
+  ItemData single_item_data;
+  LineInfo line_info = { 0 };
+
+  items_data = create_items_data (layout, items, 0, FALSE, NULL,
+				  &single_items_data, &single_item_data);
+
+  /* Build a single line for the entire paragraph. */
+  line_info.line_num = 0;
+  line_info.is_last_line = TRUE;
+  line_info.line_start_byte_offset = 0;
+  line_info.line_start_char_offset = 0;
+  line_info.line_end_byte_offset = layout->length;
+  line_info.line_end_char_offset = layout->n_chars;
+  line_info.next_line_byte_offset = layout->length;
+  line_info.next_line_char_offset = layout->n_chars;
+
+  build_line (layout, items_data, 0, &line_info, base_dir, attrs);
+
+  free_items_data (items_data, &single_items_data);
+}
+
+
+/* This does the layout when width is set to -1, where we only break at
+ * mandatory breaks. Note that we don't strip trailing whitespace in this
+ * mode. We can do that, but we'd need to use the logical attributes (which
+ * may only be created when needed in future, to speed things up).
+ */
+static void
+layout_with_unlimited_width (PangoLayout                *layout,
+			     GList                      *items,
+			     PangoDirection	         base_dir,
+			     int		         start_char_offset,
+			     PangoAttrList              *attrs)
+{
+  GArray *items_data, single_items_data;
+  ItemData *item_data, single_item_data;
+  LineInfo line_info = { 0 };
+  PangoItem *item;
+  int line_start_item_index = 0, item_index;
+  int next_item_byte_offset = 0, next_item_char_offset = start_char_offset;
+
+  items_data = create_items_data (layout, items, start_char_offset, FALSE,
+				  NULL, &single_items_data, &single_item_data);
+
+  line_info.line_num = 0;
+  line_info.is_last_line = FALSE;
+  line_info.line_start_byte_offset = ((PangoItem*)items->data)->offset;
+  line_info.line_start_char_offset = start_char_offset;
+
+  /* Step through each PangoItem in the paragraph. */
+  for (item_index = 0; item_index < items_data->len; item_index++)
+    {
+      item_data = &g_array_index (items_data, ItemData, item_index);
+      item = item_data->item_node->data;
+
+      next_item_byte_offset = item->offset + item->length;
+      next_item_char_offset += item->num_chars;
+
+      /* We assume each LINE_SEPARATOR char appears in an item of its own. */
+      if (g_utf8_get_char (layout->text + item->offset) == PANGO_LINE_SEPARATOR)
+	{
+	  line_info.line_end_byte_offset = item->offset;
+	  line_info.line_end_char_offset = next_item_char_offset - item->num_chars;
+	  line_info.next_line_byte_offset = next_item_byte_offset;
+	  line_info.next_line_char_offset = next_item_char_offset;
+
+	  build_line (layout, items_data, line_start_item_index, &line_info,
+		      base_dir, attrs);
+
+	  line_info.line_num++;
+	  line_info.line_start_byte_offset = next_item_byte_offset;
+	  line_info.line_start_char_offset = next_item_char_offset;
+	  line_start_item_index = item_index + 1;
+	}
+    }
+
+  /* Add the last line up to the end of the paragraph. */
+  line_info.is_last_line = TRUE;
+  line_info.line_end_byte_offset = next_item_byte_offset;
+  line_info.line_end_char_offset = next_item_char_offset;
+  line_info.next_line_byte_offset = next_item_byte_offset;
+  line_info.next_line_char_offset = next_item_char_offset;
+  build_line (layout, items_data, line_start_item_index, &line_info,
+	      base_dir, attrs);
+
+  free_items_data (items_data, &single_items_data);
+}
+
+
+/* This is the main entry-point to the justification code.
+ */
+void
+_pango_layout_paragraph (PangoLayout     *layout,
+			 GList           *items,
+			 PangoDirection   base_dir,
+			 int		  start_char_offset,
+			 PangoAttrList   *attrs)
+{
+  if (layout->single_paragraph)
+    {
+      /* In single-line mode we don't break anywhere at all. Characters like
+       * newlines will be displayed as special glyphs.
+       */
+      layout_single_paragraph (layout, items, base_dir, attrs);
+    }
+  else if (layout->width == -1 || layout->ellipsize != PANGO_ELLIPSIZE_NONE)
+    {
+      /* If the width is set to -1, or ellipsization is being used, we only
+       * break at mandatory breaks.
+       */
+      layout_with_unlimited_width (layout, items, base_dir, start_char_offset,
+				   attrs);
+    }
+  else
+    {
+      /* This is the more complicated case, where we need to layout the
+       * paragraph text within a specific width.
+       */
+      layout_with_specific_width (layout, items, base_dir, start_char_offset,
+				  attrs);
+    }
+
+  /* The items are now owned by the PangoLayoutRuns created in build_line()
+   * (or they will have been freed if not needed).
+   */
+  g_list_free (items);
+}
