Fix up the operation of PangoLayoutIter, especially for Bidi (#89541,

2005-06-21  Owen Taylor  <otaylor@redhat.com>

        Fix up the operation of PangoLayoutIter, especially for Bidi
        (#89541, based on a patch from Amit Aronovitch)

        * pango/pango-layout.c: Many changes to make iteration
        consistently in visual order.

        * pango/pango-layout.c (pango_layout_iter_next_char): Iterate
        through each character in the layout exactly once. (Including
        a hack to get two iterator positions for \r\n)

        * pango/pango-layout.c (pango_layout_iter_next_cluster): Only
        iterate through real clusters: that is, positions in the
        layout that have glyphs.

        * tests/testiter.c tests/Makefile.am: Add a (somewhat reworked)
        test from Amit for the operation of PangoLayoutIter.

5 files changed, 534 insertions, 176 deletions

diff --git a/ChangeLog b/ChangeLog
index 5589af02..f3650d57 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,24 @@
 2005-06-21  Owen Taylor  <otaylor@redhat.com>
-  
+
+	Fix up the operation of PangoLayoutIter, especially for Bidi
+	(#89541, based on a patch from Amit Aronovitch)
+
+	* pango/pango-layout.c: Many changes to make iteration 
+	consistently in visual order.
+
+	* pango/pango-layout.c (pango_layout_iter_next_char): Iterate
+	through each character in the layout exactly once. (Including
+	a hack to get two iterator positions for \r\n)
+
+	* pango/pango-layout.c (pango_layout_iter_next_cluster): Only
+	iterate through real clusters: that is, positions in the 
+	layout that have glyphs.
+
+	* tests/testiter.c tests/Makefile.am: Add a (somewhat reworked) 
+	test from Amit for the operation of PangoLayoutIter.
+
+2005-06-21  Owen Taylor  <otaylor@redhat.com>
+
  	* pango/pangoxft-render.c (get_renderer): Go back to 
  	honoring alpha in the XftColor passed in; it was a 1.6 => 1.8
  	regression. (#169622, based on a patch from Mikael Magnusson)
diff --git a/ChangeLog.pre-1-10 b/ChangeLog.pre-1-10
index 5589af02..f3650d57 100644
--- a/ChangeLog.pre-1-10
+++ b/ChangeLog.pre-1-10
@@ -1,5 +1,24 @@
 2005-06-21  Owen Taylor  <otaylor@redhat.com>
-  
+
+	Fix up the operation of PangoLayoutIter, especially for Bidi
+	(#89541, based on a patch from Amit Aronovitch)
+
+	* pango/pango-layout.c: Many changes to make iteration 
+	consistently in visual order.
+
+	* pango/pango-layout.c (pango_layout_iter_next_char): Iterate
+	through each character in the layout exactly once. (Including
+	a hack to get two iterator positions for \r\n)
+
+	* pango/pango-layout.c (pango_layout_iter_next_cluster): Only
+	iterate through real clusters: that is, positions in the 
+	layout that have glyphs.
+
+	* tests/testiter.c tests/Makefile.am: Add a (somewhat reworked) 
+	test from Amit for the operation of PangoLayoutIter.
+
+2005-06-21  Owen Taylor  <otaylor@redhat.com>
+
  	* pango/pangoxft-render.c (get_renderer): Go back to 
  	honoring alpha in the XftColor passed in; it was a 1.6 => 1.8
  	regression. (#169622, based on a patch from Mikael Magnusson)
diff --git a/pango/pango-layout.c b/pango/pango-layout.c
index 1398e757..a3a5f840 100644
--- a/pango/pango-layout.c
+++ b/pango/pango-layout.c
@@ -82,19 +82,23 @@ struct _PangoLayoutIter
   /* this run is left-to-right */
   gboolean ltr;
 
-  /* X position where cluster begins, where "begins" means left or
-   * right side according to text direction
-   */
+  /* X position of the left side of the current cluster */
   int cluster_x;
 
-  /* Byte index of the cluster start from the run start */
-  int cluster_index;
-  
-  /* Glyph offset to the current cluster start */
+  /* The width of the current cluster */
+  int cluster_width;
+
+  /* glyph offset to the current cluster start */
   int cluster_start;
 
-  /* The next cluster_start */
-  int next_cluster_start;
+  /* first glyph in the next cluster */
+  int next_cluster_glyph;
+
+  /* number of unicode chars in current cluster */
+  int cluster_num_chars;
+
+  /* visual position of current character within the cluster */
+  int character_position;
 };
 
 typedef struct _PangoLayoutLinePrivate PangoLayoutLinePrivate;
@@ -4309,31 +4313,29 @@ next_cluster_start (PangoGlyphString *gs,
       if (gs->glyphs[i].attr.is_cluster_start)
         return i;
       
-      ++i;
+      i++;
     }
 
   return gs->num_glyphs;
 }
 
 static int
-cluster_end_index (PangoLayoutIter *iter)
+cluster_width (PangoGlyphString *gs,
+	       int               cluster_start)
 {
-  PangoGlyphString *gs;
-  
-  gs = iter->run->glyphs;
-  
-  if (iter->next_cluster_start == gs->num_glyphs)
-    {
-      /* Use the left or right end of the run */
-      if (iter->ltr)
-        return iter->run->item->length;
-      else
-        return 0;
-    }
-  else
+  int i;
+  int log_cluster;
+  int width = 0;
+
+  log_cluster = gs->log_clusters[cluster_start];
+  for (i = cluster_start; i < gs->num_glyphs; i++) 
     {
-      return gs->log_clusters[iter->next_cluster_start];
+      if (gs->log_clusters[i] != log_cluster)
+	break;
+      width += gs->glyphs[i].geometry.width;
     }
+
+  return width;
 }
 
 static inline void
@@ -4347,6 +4349,57 @@ offset_y (PangoLayoutIter *iter,
   *y += line_ext->baseline;
 }
 
+/* Sets up the iter for the start of a new cluster. cluster_start_index
+ * is the byte index of the cluster start relative to the run.
+ */
+static void 
+update_cluster (PangoLayoutIter *iter,
+		int              cluster_start_index)
+{
+  char             *cluster_text;
+  PangoGlyphString *gs;
+  int               cluster_length;
+
+  iter->character_position = 0;
+
+  gs = iter->run->glyphs;
+  iter->cluster_width = cluster_width (gs, iter->cluster_start);
+  iter->next_cluster_glyph = next_cluster_start (gs, iter->cluster_start);
+
+  if (iter->ltr)
+    {
+      /* For LTR text, finding the length of the cluster is easy
+       * since logical and visual runs are in the same direction.
+       */
+      if (iter->next_cluster_glyph < gs->num_glyphs)
+	cluster_length = gs->log_clusters[iter->next_cluster_glyph] - cluster_start_index;
+      else
+	cluster_length = iter->run->item->length - cluster_start_index;
+    }
+  else
+    {
+      /* For RTL text, we have to scan backwards to find the previous
+       * visual cluster which is the next logical cluster.
+       */
+      int i = iter->cluster_start;
+      while (i > 0 && gs->log_clusters[i - 1] == cluster_start_index)
+	i--;
+
+      if (i == 0)
+	cluster_length = iter->run->item->length - cluster_start_index;
+      else
+	cluster_length = gs->log_clusters[i - 1] - cluster_start_index;
+    }
+
+  cluster_text = iter->layout->text + iter->run->item->offset + cluster_start_index;
+  iter->cluster_num_chars = g_utf8_strlen (cluster_text, cluster_length);
+
+  if (iter->ltr)
+    iter->index = cluster_text - iter->layout->text;
+  else
+    iter->index = g_utf8_prev_char (cluster_text + cluster_length) - iter->layout->text;
+}
+
 static void
 update_run (PangoLayoutIter *iter,
 	    int              run_start_index)
@@ -4370,13 +4423,15 @@ update_run (PangoLayoutIter *iter,
                                     NULL,
                                     &iter->run_logical_rect);
 
-      /* Fix coordinates of the run extents */
+      /* Fix coordinates of the run extents to be layout-relative*/
       iter->run_logical_rect.x += iter->run_x;
       
       offset_y (iter, &iter->run_logical_rect.y);
     }
   else
     {
+      /* The empty run at the end of a line */
+      
       iter->run_logical_rect.x = iter->run_x;
       iter->run_logical_rect.y = line_ext->logical_rect.y;
       iter->run_logical_rect.width = 0;
@@ -4387,33 +4442,21 @@ update_run (PangoLayoutIter *iter,
     iter->ltr = (iter->run->item->analysis.level % 2) == 0;
   else
     iter->ltr = TRUE;
-  
-  if (iter->ltr)    
-    iter->cluster_x = iter->run_logical_rect.x;
-  else
-    iter->cluster_x = iter->run_logical_rect.x +
-      iter->run_logical_rect.width;
-  
+
   iter->cluster_start = 0;
+  iter->cluster_x = iter->run_logical_rect.x;
 
   if (iter->run)
-    iter->next_cluster_start = next_cluster_start (iter->run->glyphs,
-                                                   iter->cluster_start);
-  else
-    iter->next_cluster_start = 0;
-  
-  /* Index of the first cluster in the glyph string, relative
-   * to the start of the run
-   */
-  if (iter->run)
-    iter->cluster_index = iter->run->glyphs->log_clusters[0];
+    {
+      update_cluster (iter, iter->run->glyphs->log_clusters[0]);
+    }
   else
-    iter->cluster_index = 0;
-  
-  /* Get an overall index, leaving it unchanged for
-   * a the NULL run
-   */
-  iter->index = run_start_index;
+    {
+      iter->cluster_width = 0;
+      iter->character_position = 0;
+      iter->cluster_num_chars = 0;
+      iter->index = run_start_index;
+    }
 }
 
 static PangoLayoutIter *
@@ -4453,9 +4496,13 @@ pango_layout_iter_copy (PangoLayoutIter *iter)
   new->ltr = iter->ltr;
   
   new->cluster_x = iter->cluster_x;
-  new->cluster_index = iter->cluster_index;
+  new->cluster_width = iter->cluster_x;
+
   new->cluster_start = iter->cluster_start;
-  new->next_cluster_start = iter->next_cluster_start;
+  new->next_cluster_glyph = iter->next_cluster_glyph;
+
+  new->cluster_num_chars = iter->cluster_num_chars;
+  new->character_position = iter->character_position;
 
   return new;
 }
@@ -4484,6 +4531,7 @@ pango_layout_iter_get_type (void)
 PangoLayoutIter*
 pango_layout_get_iter (PangoLayout *layout)
 {
+  int run_start_index;
   PangoLayoutIter *iter;
   
   g_return_val_if_fail (PANGO_IS_LAYOUT (layout), NULL);
@@ -4499,10 +4547,14 @@ pango_layout_get_iter (PangoLayout *layout)
   iter->line = iter->line_list_link->data;
   pango_layout_line_ref (iter->line);
 
+  run_start_index = iter->line->start_index;
   iter->run_list_link = iter->line->runs;
 
   if (iter->run_list_link)
-    iter->run = iter->run_list_link->data;
+    {
+      iter->run = iter->run_list_link->data;
+      run_start_index = iter->run->item->offset;
+    }
   else
     iter->run = NULL;
 
@@ -4514,7 +4566,7 @@ pango_layout_get_iter (PangoLayout *layout)
 
   iter->line_extents_link = iter->line_extents;
 
-  update_run (iter, 0);
+  update_run (iter, run_start_index);
 
   return iter;
 }
@@ -4611,6 +4663,108 @@ pango_layout_iter_at_last_line (PangoLayoutIter *iter)
   return iter->line_extents_link->next == NULL;
 }
 
+static gboolean
+line_is_terminated (PangoLayoutIter *iter)
+{
+  /* There is a real terminator at the end of each paragraph other
+   * than the last.
+   */
+  if (iter->line_list_link->next)
+    {
+      PangoLayoutLine *next_line = iter->line_list_link->next->data;
+      if (next_line->is_paragraph_start)
+	return TRUE;
+    }
+
+  return FALSE;
+}
+
+/* Moves to the next non-empty line. If @include_terminators
+ * is set, a line with just an explicit paragraph separator
+ * is considered non-empty.
+ */
+gboolean
+next_nonempty_line (PangoLayoutIter *iter,
+		    gboolean         include_terminators)
+{
+  gboolean result;
+
+  while (TRUE)
+    {
+      result = pango_layout_iter_next_line (iter);
+      if (!result)
+	break;
+      
+      if (iter->line->runs)
+	break;
+      
+      if (include_terminators && line_is_terminated (iter))
+	break;
+    }
+  
+  return result;
+}
+
+/* Moves to the next non-empty line. If @include_terminators
+ * is set, the trailing run at the end of a line with an explicit
+ * paragraph separator is considered non-empty.
+ */
+gboolean
+next_nonempty_run (PangoLayoutIter *iter,
+		    gboolean         include_terminators)
+{
+  gboolean result;
+  
+  while (TRUE)
+    {
+      result = pango_layout_iter_next_run (iter);
+      if (!result)
+	break;
+      
+      if (iter->run)
+	break;
+      
+      if (include_terminators && line_is_terminated (iter))
+	break;
+    }
+  
+  return result;
+}
+
+/* Like pango_layout_next_cluster(), but if @include_terminators
+ * is set, includes the fake runs/clusters for empty lines.
+ * (But not positions introduced by line wrapping).
+ */
+gboolean
+next_cluster_internal (PangoLayoutIter *iter,
+		       gboolean         include_terminators)
+{
+  PangoGlyphString *gs;
+  int               next_start;
+  
+  if (IS_INVALID (iter))
+    return FALSE;
+
+  if (iter->run == NULL)
+    return next_nonempty_line (iter, include_terminators);
+  
+  gs = iter->run->glyphs;
+  
+  next_start = iter->next_cluster_glyph;
+  if (next_start == gs->num_glyphs)
+    {
+      return next_nonempty_run (iter, include_terminators);
+    }
+  else
+    {
+      iter->cluster_start = next_start;
+      iter->cluster_x += iter->cluster_width;
+      update_cluster(iter, gs->log_clusters[iter->cluster_start]);
+
+      return TRUE;
+    }
+}
+
 /**
  * pango_layout_iter_next_char:
  * @iter: a #PangoLayoutIter
@@ -4623,51 +4777,36 @@ pango_layout_iter_at_last_line (PangoLayoutIter *iter)
 gboolean
 pango_layout_iter_next_char (PangoLayoutIter *iter)
 {
-  const char *p;
-  const char *oldp;
-  const char *item_end;
-  int new_index;
-  int next_cluster_index;
-  PangoGlyphString *gs;
-  
+  const char *text;
+
   if (IS_INVALID (iter))
     return FALSE;
 
   if (iter->run == NULL)
-    return pango_layout_iter_next_line (iter);
-  
-  gs = iter->run->glyphs;
-
-  next_cluster_index = iter->run->item->offset + cluster_end_index (iter);
-  
-  oldp = iter->layout->text + iter->index;
-
-  if (iter->ltr)
     {
-      item_end = iter->layout->text +
-        iter->run->item->offset +
-        iter->run->item->length;
-      p = g_utf8_next_char (oldp);
-    }
-  else
-    {
-      item_end = iter->layout->text + iter->run->item->offset;
-      p = g_utf8_prev_char (oldp);
-    }
+      /* We need to fake an iterator position in the middle of a \r\n line terminator */
+      if (line_is_terminated (iter) &&
+	  strncmp (iter->layout->text + iter->line->start_index + iter->line->length, "\r\n", 2) == 0 &&
+	  iter->character_position == 0)
+	{
+	  iter->character_position++;
+	  return TRUE;
+	}
 
-  new_index = iter->index + (p - oldp);
+      return next_nonempty_line (iter, TRUE);
+    }
 
-  /* Make sure we don't go past the next cluster index */
-  g_assert ((iter->ltr && (new_index <= next_cluster_index)) ||
-            (!iter->ltr && (new_index >= next_cluster_index)));
+  iter->character_position++;
+  if (iter->character_position >= iter->cluster_num_chars)
+    return next_cluster_internal (iter, TRUE);
   
-  if (new_index == next_cluster_index)
-    return pango_layout_iter_next_cluster (iter);
+  text = iter->layout->text;
+  if (iter->ltr)
+    iter->index = g_utf8_next_char (text + iter->index) - text;
   else
-    {
-      iter->index = new_index;
-      return TRUE;
-    }
+    iter->index = g_utf8_prev_char (text + iter->index) - text;
+  
+  return TRUE;
 }
 
 /**
@@ -4682,31 +4821,7 @@ pango_layout_iter_next_char (PangoLayoutIter *iter)
 gboolean
 pango_layout_iter_next_cluster (PangoLayoutIter *iter)
 {
-  PangoGlyphString *gs;
-  
-  if (IS_INVALID (iter))
-    return FALSE;
-
-  if (iter->run == NULL)
-    return pango_layout_iter_next_line (iter);
-  
-  gs = iter->run->glyphs;
-  
-  if (iter->next_cluster_start == gs->num_glyphs)
-    return pango_layout_iter_next_run (iter);
-  else
-    {
-      if (iter->ltr)
-        iter->cluster_x += gs->glyphs[iter->cluster_start].geometry.width;
-      else
-        iter->cluster_x -= gs->glyphs[iter->cluster_start].geometry.width;
-        
-      iter->cluster_start = iter->next_cluster_start;
-      iter->next_cluster_start = next_cluster_start (gs, iter->cluster_start);
-      iter->cluster_index = gs->log_clusters[iter->cluster_start];
-      iter->index = iter->run->item->offset + iter->cluster_index;
-      return TRUE;
-    }
+  return next_cluster_internal (iter, FALSE);
 }
 
 /**
@@ -4721,7 +4836,7 @@ pango_layout_iter_next_cluster (PangoLayoutIter *iter)
 gboolean
 pango_layout_iter_next_run (PangoLayoutIter *iter)
 {
-  gint prev_run_end;
+  int next_run_start; /* byte index */
   GSList *next_link;
   
   if (IS_INVALID (iter))
@@ -4729,9 +4844,7 @@ pango_layout_iter_next_run (PangoLayoutIter *iter)
 
   if (iter->run == NULL)
     return pango_layout_iter_next_line (iter);
-  else
-    prev_run_end = iter->run->item->offset + iter->run->item->length;
-  
+
   next_link = iter->run_list_link->next;
 
   if (next_link == NULL)
@@ -4739,6 +4852,7 @@ pango_layout_iter_next_run (PangoLayoutIter *iter)
       /* Moving on to the zero-width "virtual run" at the end of each
        * line
        */
+      next_run_start = iter->run->item->offset + iter->run->item->length; 
       iter->run = NULL;
       iter->run_list_link = NULL;
     }
@@ -4746,9 +4860,10 @@ pango_layout_iter_next_run (PangoLayoutIter *iter)
     {
       iter->run_list_link = next_link;
       iter->run = iter->run_list_link->data;
+      next_run_start = iter->run->item->offset;
     }
   
-  update_run (iter, prev_run_end);
+  update_run (iter, next_run_start);
   
   return TRUE;
 }
@@ -4766,7 +4881,7 @@ gboolean
 pango_layout_iter_next_line (PangoLayoutIter *iter)
 {
   GSList *next_link;
-  
+
   if (IS_INVALID (iter))
     return FALSE;
 
@@ -4790,13 +4905,6 @@ pango_layout_iter_next_line (PangoLayoutIter *iter)
   else
     iter->run = NULL;
 
-  /* FIXME isn't this broken? we can have \r\n etc. */
-  /* If we move on to an empty line (no runs), it means the empty line
-   * represents a '\n' in layout->text, so advance iter->index
-   */
-  if (iter->run == NULL)
-    iter->index += 1; /* 1 is the length of '\n' in UTF-8 */
-
   iter->line_extents_link = iter->line_extents_link->next;
   g_assert (iter->line_extents_link != NULL);  
 
@@ -4821,15 +4929,8 @@ pango_layout_iter_get_char_extents (PangoLayoutIter *iter,
                                     PangoRectangle  *logical_rect)
 {
   PangoRectangle cluster_rect;
-  int end_index;
-  int start_index;
-  const char *p;
-  const char *end;
-  const char *current;
-  int char_count;
-  int cluster_offset;
-  double char_width;
-  
+  double         x0, x1;
+
   if (IS_INVALID (iter))
     return;
 
@@ -4847,46 +4948,15 @@ pango_layout_iter_get_char_extents (PangoLayoutIter *iter,
       return;
     }
   
-  /* count chars in the cluster */
-  end_index = iter->run->item->offset + cluster_end_index (iter);
-  start_index = iter->run->item->offset + iter->cluster_index;
+  g_assert (cluster_rect.width == iter->cluster_width);
 
-  if (end_index < start_index)
-    {
-      int tmp = end_index;
-      end_index = start_index;
-      start_index = tmp;
-    }
-
-  g_assert (start_index < end_index);
-  
-  p = iter->layout->text + start_index;
-  current = iter->layout->text + iter->index;
-  end = iter->layout->text + end_index;
+  x0 = ((double)iter->character_position * cluster_rect.width) / iter->cluster_num_chars;
+  x1 = ((double)(iter->character_position + 1) * cluster_rect.width) / iter->cluster_num_chars;
 
-  g_assert (p < end);
-  g_assert (p <= current);
-  g_assert (current < end);
-  
-  char_count = 0;
-  cluster_offset = 0;
-  while (p != end)
-    {
-      if (p < current)
-        ++cluster_offset;
-      ++char_count;
-      p = g_utf8_next_char (p);
-    }
-
-  char_width = ((double)cluster_rect.width) / char_count;
-  logical_rect->width = char_width;
+  logical_rect->width = (int)x1 - (int)x0;
   logical_rect->height = cluster_rect.height;
   logical_rect->y = cluster_rect.y;
-  
-  if (iter->ltr)
-    logical_rect->x = cluster_rect.x + char_width * cluster_offset;
-  else
-    logical_rect->x = cluster_rect.x + cluster_rect.width - char_width * cluster_offset;
+  logical_rect->x = cluster_rect.x + (int)x0;
 }
 
 /**
@@ -4918,7 +4988,7 @@ pango_layout_iter_get_cluster_extents (PangoLayoutIter *iter,
   
   pango_glyph_string_extents_range (iter->run->glyphs,
                                     iter->cluster_start,
-                                    iter->next_cluster_start,
+                                    iter->next_cluster_glyph,
                                     iter->run->item->analysis.font,
                                     ink_rect,
                                     logical_rect);
diff --git a/tests/Makefile.am b/tests/Makefile.am
index c42d60c2..58175d28 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -3,6 +3,7 @@
 INCLUDES =					\
 	-I$(top_srcdir)				\
 	$(GLIB_CFLAGS)				\
+	$(CAIRO_CFLAGS)				\
 	$(XFT_CFLAGS)				\
 	$(FREETYPE_CFLAGS)			\
 	$(X_CFLAGS)				\
@@ -29,18 +30,25 @@ TESTS_ENVIRONMENT =                    \
    srcdir=$(srcdir)                    \
    PANGO_RC_FILE=./pangorc
 
-noinst_PROGRAMS = gen-all-unicode dump-boundaries
+noinst_PROGRAMS = gen-all-unicode dump-boundaries 
 
 check_PROGRAMS = testboundaries testcolor testscript
 
+if HAVE_CAIRO
+check_PROGRAMS += testiter
+endif
+
 gen_all_unicode_SOURCES = gen-all-unicode.c
 
 testboundaries_SOURCES = testboundaries.c
 
 testcolor_SOURCES = testcolor.c
 
+testiter_SOURCES = testiter.c
+
 testscript_SOURCES = testscript.c
 
+
 dump_boundaries_SOURCES = dump-boundaries.c
 
 gen_all_unicode_LDADD = $(GLIB_LIBS)
@@ -49,6 +57,8 @@ testboundaries_LDADD = ../pango/libpango-$(PANGO_API_VERSION).la
 
 testcolor_LDADD = ../pango/libpango-$(PANGO_API_VERSION).la
 
+testiter_LDADD = ../pango/libpango-$(PANGO_API_VERSION).la ../pango/libpangocairo-$(PANGO_API_VERSION).la 
+
 testscript_LDADD = ../pango/libpango-$(PANGO_API_VERSION).la
 
 dump_boundaries_LDADD = ../pango/libpango-$(PANGO_API_VERSION).la
diff --git a/tests/testiter.c b/tests/testiter.c
new file mode 100644
index 00000000..d0966c91
--- /dev/null
+++ b/tests/testiter.c
@@ -0,0 +1,240 @@
+/* Pango
+ * testiter.c: Test pangolayoutiter.c
+ *
+ * Copyright (C) 2005 Amit Aronovitch
+ * Copyright (C) 2005 Red Hat, Inc
+ *
+ * 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.
+ */
+
+#undef G_DISABLE_ASSERT
+#undef G_LOG_DOMAIN
+
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <glib.h>
+
+#include <pango/pangocairo.h>
+
+#undef VERBOSE
+
+static void
+verbose (const char *format, ...)
+{
+#ifdef VERBOSE  
+  va_list vap;
+  
+  va_start (vap, format);
+  vfprintf (stderr, format, vap);
+  va_end (vap);
+#endif  
+}
+
+#define LAYOUT_WIDTH (80 * PANGO_SCALE)
+
+/* Note: The test expects that any newline sequence is of length 1
+ * use \n (not \r\n) in the test texts.
+ * I think the iterator itself should support \r\n without trouble,
+ * but there are comments in layout-iter.c suggesting otherwise.
+ */
+char *test_texts[] =
+  {
+    /* English with embedded RTL runs (from ancient-hebrew.org) */
+    "The Hebrew word \xd7\x90\xd7\x93\xd7\x9d\xd7\x94 (adamah) is the feminine form of \xd7\x90\xd7\x93\xd7\x9d meaning \"ground\"\n",
+    /* Arabic, with vowel marks (from Sura Al Fatiha) */
+    "\xd8\xa8\xd9\x90\xd8\xb3\xd9\x92\xd9\x85\xd9\x90 \xd8\xa7\xd9\x84\xd9\x84\xd9\x91\xd9\x87\xd9\x90 \xd8\xa7\xd9\x84\xd8\xb1\xd9\x91\xd9\x8e\xd8\xad\xd9\x92\xd9\x85\xd9\x80\xd9\x8e\xd9\x86\xd9\x90 \xd8\xa7\xd9\x84\xd8\xb1\xd9\x91\xd9\x8e\xd8\xad\xd9\x90\xd9\x8a\xd9\x85\xd9\x90\n\xd8\xa7\xd9\x84\xd9\x92\xd8\xad\xd9\x8e\xd9\x85\xd9\x92\xd8\xaf\xd9\x8f \xd9\x84\xd9\x84\xd9\x91\xd9\x87\xd9\x90 \xd8\xb1\xd9\x8e\xd8\xa8\xd9\x91\xd9\x90 \xd8\xa7\xd9\x84\xd9\x92\xd8\xb9\xd9\x8e\xd8\xa7\xd9\x84\xd9\x8e\xd9\x85\xd9\x90\xd9\x8a\xd9\x86\xd9\x8e\n",
+    /* Arabic, with embedded LTR runs (from a Linux guide) */
+    "\xd8\xa7\xd9\x84\xd9\x85\xd8\xaa\xd8\xba\xd9\x8a\xd8\xb1 LC_ALL \xd9\x8a\xd8\xba\xd9\x8a\xd9\x8a\xd8\xb1 \xd9\x83\xd9\x84 \xd8\xa7\xd9\x84\xd9\x85\xd8\xaa\xd8\xba\xd9\x8a\xd8\xb1\xd8\xa7\xd8\xaa \xd8\xa7\xd9\x84\xd8\xaa\xd9\x8a \xd8\xaa\xd8\xa8\xd8\xaf\xd8\xa3 \xd8\xa8\xd8\xa7\xd9\x84\xd8\xb1\xd9\x85\xd8\xb2 LC.",
+    /* Hebrew, with vowel marks (from Genesis) */
+    "\xd7\x91\xd6\xbc\xd6\xb0\xd7\xa8\xd6\xb5\xd7\x90\xd7\xa9\xd7\x81\xd6\xb4\xd7\x99\xd7\xaa, \xd7\x91\xd6\xbc\xd6\xb8\xd7\xa8\xd6\xb8\xd7\x90 \xd7\x90\xd6\xb1\xd7\x9c\xd6\xb9\xd7\x94\xd6\xb4\xd7\x99\xd7\x9d, \xd7\x90\xd6\xb5\xd7\xaa \xd7\x94\xd6\xb7\xd7\xa9\xd6\xbc\xd7\x81\xd6\xb8\xd7\x9e\xd6\xb7\xd7\x99\xd6\xb4\xd7\x9d, \xd7\x95\xd6\xb0\xd7\x90\xd6\xb5\xd7\xaa \xd7\x94\xd6\xb8\xd7\x90\xd6\xb8\xd7\xa8\xd6\xb6\xd7\xa5",
+    /* Hebrew, with embedded LTR runs (from a Linux guide) */
+    "\xd7\x94\xd7\xa7\xd7\x9c\xd7\x93\xd7\x94 \xd7\xa2\xd7\x9c \xd7\xa9\xd7\xa0\xd7\x99 \xd7\x94 SHIFT\xd7\x99\xd7\x9d (\xd7\x99\xd7\x9e\xd7\x99\xd7\x9f \xd7\x95\xd7\xa9\xd7\x9e\xd7\x90\xd7\x9c \xd7\x91\xd7\x99\xd7\x97\xd7\x93) \xd7\x90\xd7\x9e\xd7\x95\xd7\xa8\xd7\x99\xd7\x9d \xd7\x9c\xd7\x94\xd7\x93\xd7\x9c\xd7\x99\xd7\xa7 \xd7\x90\xd7\xaa \xd7\xa0\xd7\x95\xd7\xa8\xd7\xaa \xd7\x94 Scroll Lock , \xd7\x95\xd7\x9c\xd7\x94\xd7\xa2\xd7\x91\xd7\x99\xd7\xa8 \xd7\x90\xd7\x95\xd7\xaa\xd7\xa0\xd7\x95 \xd7\x9c\xd7\x9e\xd7\xa6\xd7\x91 \xd7\x9b\xd7\xaa\xd7\x99\xd7\x91\xd7\x94 \xd7\x91\xd7\xa2\xd7\x91\xd7\xa8\xd7\x99\xd7\xaa.",
+    /* Different line terminators */
+    "AAAA\nBBBB\nCCCC\n",
+    "DDDD\rEEEE\rFFFF\r",
+    "GGGG\r\nHHHH\r\nIIII\r\n",
+    NULL
+  };
+
+void
+iter_char_test (PangoLayout *layout)
+{
+  PangoRectangle   extents, run_extents;
+  PangoLayoutIter *iter;
+  PangoLayoutRun  *run;
+  int              num_chars;
+  int              i, index, offset;
+  int              leading_x, trailing_x, x0, x1;
+  gboolean         iter_next_ok, rtl;
+  const char      *text, *ptr;
+
+  text = pango_layout_get_text (layout);
+  num_chars = g_utf8_strlen (text, -1);
+  
+  iter = pango_layout_get_iter (layout);
+  iter_next_ok = TRUE;
+
+  for (i = 0 ; i < num_chars; ++i)
+    {
+      gchar *char_str;
+      g_assert (iter_next_ok);
+
+      index = pango_layout_iter_get_index (iter);
+      ptr = text + index;
+      char_str = g_strndup (ptr, g_utf8_next_char (ptr) - ptr);
+      verbose ("i=%d (visual), index = %d '%s':\n", 
+	       i, index, char_str);
+      g_free (char_str);
+
+      pango_layout_iter_get_char_extents (iter, &extents);
+      verbose ("  char extents: x=%d,y=%d w=%d,h=%d\n",
+	       extents.x, extents.y, 
+	       extents.width, extents.height);
+      
+      run = pango_layout_iter_get_run (iter);
+
+      if (run)
+	{
+	  /* Get needed data for the GlyphString */
+	  pango_layout_iter_get_run_extents(iter, NULL, &run_extents);
+	  offset = run->item->offset;
+	  rtl = run->item->analysis.level%2;
+	  verbose ("  (current run: offset=%d,x=%d,len=%d,rtl=%d)\n", 
+		   offset, run_extents.x, run->item->length, rtl);
+	  
+	  /* Calculate expected x result using index_to_x */
+	  pango_glyph_string_index_to_x (run->glyphs, 
+					 (char *)(text + offset), run->item->length,
+					 &run->item->analysis,
+					 index - offset, FALSE, &leading_x);
+	  pango_glyph_string_index_to_x (run->glyphs, 
+					 (char *)(text + offset), run->item->length,
+					 &run->item->analysis,
+					 index - offset, TRUE, &trailing_x);
+	  
+	  x0 = run_extents.x + MIN (leading_x, trailing_x);
+	  x1 = run_extents.x + MAX (leading_x, trailing_x);
+	  
+	  verbose ("  (index_to_x ind=%d: expected x=%d, width=%d)\n", 
+		   index - offset, x0, x1 - x0);
+
+	  g_assert (extents.x == x0);
+	  g_assert (extents.width == x1 - x0);
+	}
+      else
+	{
+	  /* We're on a line terminator */
+	}
+      
+      iter_next_ok = pango_layout_iter_next_char (iter);
+      verbose ("more to go? %d\n", iter_next_ok);
+    }
+
+  /* There should be one character position iterator for each character in the
+   * input string */
+  g_assert (!iter_next_ok);
+
+  pango_layout_iter_free (iter);
+}
+
+/* char iteration test:
+ *  - Total num of iterations match number of chars
+ *  - GlyphString's index_to_x positions match those returned by the Iter
+ */
+void
+iter_cluster_test (PangoLayout *layout)
+{
+  PangoRectangle   extents;
+  PangoLayoutIter *iter;
+  int              index;
+  gboolean         iter_next_ok;
+  const char      *text;
+  PangoLayoutLine *last_line = NULL;
+  int              expected_next_x = 0;
+
+  text = pango_layout_get_text (layout);
+
+  iter = pango_layout_get_iter (layout);
+  iter_next_ok = TRUE;
+
+  while (iter_next_ok)
+    {
+      PangoLayoutLine *line = pango_layout_iter_get_line (iter);
+
+      /* Every cluster is part of a run */
+      g_assert (pango_layout_iter_get_run (iter));
+
+      index = pango_layout_iter_get_index (iter);
+      
+      pango_layout_iter_get_cluster_extents (iter, NULL, &extents);
+      
+      iter_next_ok = pango_layout_iter_next_cluster (iter);
+      
+      verbose ("index = %d:\n", index);
+      verbose ("  cluster extents: x=%d,y=%d w=%d,h=%d\n",
+	       extents.x, extents.y, 
+	       extents.width, extents.height);
+      verbose ("more to go? %d\n", iter_next_ok);
+
+      /* All the clusters on a line should be next to each other and occupy
+       * the entire line. They advance linearly from left to right */
+      g_assert (extents.width >= 0);
+      
+      if (last_line == line)
+	g_assert (extents.x == expected_next_x);
+
+      expected_next_x = extents.x + extents.width;      
+
+      last_line = line;
+    }
+  
+  g_assert (!iter_next_ok);
+
+  pango_layout_iter_free (iter);
+}
+
+int
+main (int argc, char *argv[])
+{
+  char        **ptext;
+  PangoFontMap *fontmap;
+  PangoContext *context;
+  PangoLayout  *layout;
+
+  fontmap = pango_cairo_font_map_get_default ();
+  context = pango_cairo_font_map_create_context (PANGO_CAIRO_FONT_MAP (fontmap));
+
+  layout = pango_layout_new (context);
+  pango_layout_set_width (layout, LAYOUT_WIDTH);
+
+  for (ptext = test_texts; *ptext != NULL; ++ptext)
+    {
+      verbose ("--------- checking next text ----------\n");
+      verbose (" <%s>\n", *ptext);
+      verbose ( "len=%d, bytes=%d\n",
+		g_utf8_strlen (*ptext, -1), strlen (*ptext));
+
+      pango_layout_set_text (layout, *ptext, -1);
+      iter_char_test (layout);
+      iter_cluster_test (layout);
+    }
+
+  g_object_unref (layout);
+  return 0;
+}