Merge branch 'rewrite-line-breaking' into 'main'

Rewrite process_item

See merge request GNOME/pango!509

3 files changed, 640 insertions, 216 deletions

diff --git a/pango/pango-layout.c b/pango/pango-layout.c
index 471cbb64..f820a6c6 100644
--- a/pango/pango-layout.c
+++ b/pango/pango-layout.c
@@ -3526,31 +3526,16 @@ shape_tab (PangoLayoutLine  *line,
 }
 
 static inline gboolean
-can_break_at (PangoLayout *layout,
-              gint         offset,
-              gboolean     always_wrap_char)
+can_break_at (PangoLayout   *layout,
+              gint           offset,
+              PangoWrapMode  wrap)
 {
-  PangoWrapMode wrap;
-  /* We probably should have a mode where we treat all white-space as
-   * of fungible width - appropriate for typography but not for
-   * editing.
-   */
-  wrap = layout->wrap;
-
-  if (wrap == PANGO_WRAP_WORD_CHAR)
-    wrap = always_wrap_char ? PANGO_WRAP_CHAR : PANGO_WRAP_WORD;
-
   if (offset == layout->n_chars)
     return TRUE;
-  else if (wrap == PANGO_WRAP_WORD)
-    return layout->log_attrs[offset].is_line_break;
   else if (wrap == PANGO_WRAP_CHAR)
     return layout->log_attrs[offset].is_char_break;
   else
-    {
-      g_warning (G_STRLOC": broken PangoLayout");
-      return TRUE;
-    }
+    return layout->log_attrs[offset].is_line_break;
 }
 
 static inline gboolean
@@ -3562,7 +3547,7 @@ can_break_in (PangoLayout *layout,
   int i;
 
   for (i = allow_break_at_start ? 0 : 1; i < num_chars; i++)
-    if (can_break_at (layout, start_offset + i, FALSE))
+    if (can_break_at (layout, start_offset + i, layout->wrap))
       return TRUE;
 
   return FALSE;
@@ -3680,17 +3665,20 @@ shape_run (PangoLayoutLine *line,
 }
 
 static void
-insert_run (PangoLayoutLine *line,
-            ParaBreakState  *state,
-            PangoItem       *run_item,
-            gboolean         last_run)
+insert_run (PangoLayoutLine  *line,
+            ParaBreakState   *state,
+            PangoItem        *run_item,
+            PangoGlyphString *glyphs,
+            gboolean          last_run)
 {
   PangoLayoutRun *run = g_slice_new (PangoLayoutRun);
 
   run->item = run_item;
 
-  if (last_run && state->log_widths_offset == 0 &&
-      !(run_item->analysis.flags & PANGO_ANALYSIS_FLAG_NEED_HYPHEN))
+  if (glyphs)
+    run->glyphs = glyphs;
+  else if (last_run && state->log_widths_offset == 0 &&
+           !(run_item->analysis.flags & PANGO_ANALYSIS_FLAG_NEED_HYPHEN))
     run->glyphs = state->glyphs;
   else
     run->glyphs = shape_run (line, state, run_item);
@@ -3793,6 +3781,22 @@ debug (const char *where, PangoLayoutLine *line, ParaBreakState *state)
 # define DEBUG(where, line, state) do { } while (0)
 #endif
 
+static inline void
+compute_log_widths (PangoLayout    *layout,
+                    ParaBreakState *state)
+{
+  PangoItem *item = state->items->data;
+  PangoGlyphItem glyph_item = { item, state->glyphs };
+
+  if (item->num_chars > state->num_log_widths)
+    {
+      state->log_widths = g_renew (int, state->log_widths, item->num_chars);
+      state->num_log_widths = item->num_chars;
+    }
+
+  pango_glyph_item_get_logical_widths (&glyph_item, layout->text, state->log_widths);
+}
+
 /* Tries to insert as much as possible of the item at the head of
  * state->items onto @line. Five results are possible:
  *
@@ -3811,6 +3815,34 @@ debug (const char *where, PangoLayoutLine *line, ParaBreakState *state)
  * returned even everything fits; the run will be broken earlier,
  * or %BREAK_NONE_FIT returned. This is used when the end of the
  * run is not a break position.
+ *
+ * This function is the core of our line-breaking, and it is long and involved.
+ * Here is an outline of the algorithm, without all the bookkeeping:
+ *
+ * if item appears to fit entirely
+ *   measure it
+ *   if it actually fits
+ *     return BREAK_ALL_FIT
+ *
+ * retry_break:
+ *   for each position p in the item
+ *     if adding more is 'obviously' not going to help and we have a breakpoint
+ *       exit the loop
+ *     if p is a possible break position
+ *       if p is 'obviously' going to fit
+ *         bc = p
+ *       else
+ *         measure breaking at p (taking extra break width into account
+ *         if we don't have a break candidate yet
+ *           bc = p
+ *         else
+ *           if p is better than bc
+ *             bc = p
+ *
+ *   if bc does not fit and we can loosen break conditions
+ *     loosen break conditions and retry break
+ *
+ * return bc
  */
 static BreakResult
 process_item (PangoLayout     *layout,
@@ -3823,29 +3855,55 @@ process_item (PangoLayout     *layout,
   gboolean shape_set = FALSE;
   int width;
   int extra_width;
+  int orig_extra_width;
   int length;
   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
-
+  int processing_new_item;
+  int num_chars;
+  int orig_width;
+  PangoWrapMode wrap;
+  int break_num_chars;
+  int break_width;
+  int break_extra_width;
+  PangoGlyphString *break_glyphs;
+  PangoFontMetrics *metrics;
+  int safe_distance;
+
+  g_debug ("process item '%.*s'. Remaining width %d",
+           item->length, layout->text + item->offset,
+           state->remaining_width);
+
+  /* We don't want to shape more than necessary, so we keep the results
+   * of shaping a new item in state->glyphs, state->log_widths. Once
+   * we break off initial parts of the item, we update state->log_widths_offset
+   * to take that into account. Note that the widths we calculate from the
+   * log_widths are an approximation, because a) log_widths are just
+   * evenly divided for clusters, and b) clusters may change as we
+   * break in the middle (think ff- i).
+   *
+   * We use state->log_widths_offset != 0 to detect if we are dealing
+   * with the original item, or one that has been chopped off.
+   */
   if (!state->glyphs)
     {
       pango_layout_get_item_properties (item, &state->properties);
       state->glyphs = shape_run (line, state, item);
-
       state->log_widths_offset = 0;
-
       processing_new_item = TRUE;
     }
+  else
+    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 (!layout->single_paragraph &&
       g_utf8_get_char (layout->text + item->offset) == LINE_SEPARATOR &&
       !should_ellipsize_current_line (layout, state))
     {
-      insert_run (line, state, item, TRUE);
+      insert_run (line, state, item, NULL, TRUE);
       state->log_widths_offset += item->num_chars;
 
       return BREAK_LINE_SEPARATOR;
@@ -3853,18 +3911,19 @@ process_item (PangoLayout     *layout,
 
   if (state->remaining_width < 0 && !no_break_at_end)  /* Wrapping off */
     {
-      insert_run (line, state, item, TRUE);
+      insert_run (line, state, item, NULL, TRUE);
 
+      g_debug ("no wrapping, all-fit");
       return BREAK_ALL_FIT;
     }
 
-  width = 0;
   if (processing_new_item)
     {
       width = pango_glyph_string_get_width (state->glyphs);
     }
   else
     {
+      width = 0;
       for (i = 0; i < item->num_chars; i++)
         width += state->log_widths[state->log_widths_offset + i];
     }
@@ -3872,7 +3931,9 @@ process_item (PangoLayout     *layout,
   if ((width <= state->remaining_width || (item->num_chars == 1 && !line->runs)) &&
       !no_break_at_end)
     {
-      insert_run (line, state, item, FALSE);
+      g_debug ("%d <= %d", width, state->remaining_width);
+      insert_run (line, state, item, NULL, FALSE);
+
       width = pango_glyph_string_get_width (((PangoGlyphItem *)(line->runs->data))->glyphs);
 
       if (width <= state->remaining_width || (item->num_chars == 1 && !line->runs))
@@ -3880,9 +3941,13 @@ process_item (PangoLayout     *layout,
           state->remaining_width -= width;
           state->remaining_width = MAX (state->remaining_width, 0);
 
+          /* We passed last_run == FALSE to insert_run, so it did not do this */
           pango_glyph_string_free (state->glyphs);
           state->glyphs = NULL;
 
+          g_debug ("early accept '%.*s', all-fit, remaining %d",
+                   item->length, layout->text + item->offset,
+                   state->remaining_width);
           return BREAK_ALL_FIT;
         }
 
@@ -3890,196 +3955,208 @@ process_item (PangoLayout     *layout,
       uninsert_run (line);
     }
 
-    {
-      int num_chars;
-      int break_num_chars = item->num_chars;
-      int break_width = width;
-      int orig_width = width;
-      int break_extra_width = 0;
-      gboolean retrying_with_char_breaks = FALSE;
-      gboolean *break_disabled;
+  /*** From here on, we look for a way to break item ***/
 
-      if (processing_new_item)
-        {
-          PangoGlyphItem glyph_item = {item, state->glyphs};
-          if (item->num_chars > state->num_log_widths)
-            {
-              state->log_widths = g_renew (int, state->log_widths, item->num_chars);
-              state->num_log_widths = item->num_chars;
-            }
-          pango_glyph_item_get_logical_widths (&glyph_item, layout->text, state->log_widths);
-        }
+  orig_width = width;
+  orig_extra_width = extra_width;
+  break_width = width;
+  break_extra_width = extra_width;
+  break_num_chars = item->num_chars;
+  wrap = layout->wrap;
+  break_glyphs = NULL;
+
+  /* Add some safety margin here. If we are farther away from the end of the
+   * line than this, we don't look carefully at a break possibility.
+   */
+  metrics = pango_font_get_metrics (item->analysis.font, item->analysis.language);
+  safe_distance = pango_font_metrics_get_approximate_char_width (metrics) * 3;
+  pango_font_metrics_unref (metrics);
 
-      break_disabled = g_alloca (sizeof (gboolean) * (item->num_chars + 1));
-      memset (break_disabled, 0, sizeof (gboolean) * (item->num_chars + 1));
+  if (processing_new_item)
+    {
+      compute_log_widths (layout, state);
+      processing_new_item = FALSE;
+    }
 
-    retry_break:
+retry_break:
 
-      /* break_extra_width gets normally set from find_break_extra_width inside
-       * the loop, and that takes a space before the break into account. The
-       * one case that is not covered by that is if we end up going all the way
-       * through the loop without ever entering the can_break_at case, and come
-       * out at the other end with the break_extra_width value untouched. So
-       * initialize it here, taking space-before-break into account.
+  for (num_chars = 0, width = 0; num_chars < (no_break_at_end ? item->num_chars : (item->num_chars + 1)); num_chars++)
+    {
+      extra_width = find_break_extra_width (layout, state, num_chars);
+
+      /* We don't want to walk the entire item if we can help it, but
+       * we need to keep going at least until we've found a breakpoint
+       * that 'works' (as in, it doesn't overflow the budget we have,
+       * or there is no hope of finding a better one).
+       *
+       * We rely on the fact that MIN(width + extra_width, width) is
+       * monotonically increasing.
        */
-      if (layout->log_attrs[state->start_offset + break_num_chars - 1].is_white)
+
+      if (MIN (width + extra_width, width) > state->remaining_width + safe_distance &&
+          break_num_chars < item->num_chars)
         {
-          break_extra_width = - state->log_widths[state->log_widths_offset + break_num_chars - 1];
+          g_debug ("at %d, MIN(%d, %d + %d) > %d + MARGIN, breaking at %d",
+                   num_chars, width, extra_width, width, state->remaining_width, break_num_chars);
+          break;
+        }
 
-          /* check one more time if the whole item fits after removing the space */
-          if (width + break_extra_width <= state->remaining_width && !no_break_at_end)
+      /* If there are no previous runs we have to take care to grab at least one char. */
+      if (can_break_at (layout, state->start_offset + num_chars, wrap) &&
+          (num_chars > 0 || line->runs))
+        {
+          g_debug ("possible breakpoint: %d", num_chars);
+          if (num_chars == 0 ||
+              width + extra_width < state->remaining_width - safe_distance)
             {
-              insert_run (line, state, item, FALSE);
-              width = pango_glyph_string_get_width (((PangoGlyphItem *)(line->runs->data))->glyphs);
+              g_debug ("trivial accept");
+              break_num_chars = num_chars;
+              break_width = width;
+              break_extra_width = extra_width;
+            }
+          else
+            {
+              int length;
+              int new_break_width;
+              PangoItem *new_item;
+              PangoGlyphString *glyphs;
 
-              if (width + break_extra_width <= state->remaining_width)
-                {
-                  state->remaining_width -= width + break_extra_width;
-                  state->remaining_width = MAX (state->remaining_width, 0);
+              length = g_utf8_offset_to_pointer (layout->text + item->offset, num_chars) - (layout->text + item->offset);
 
-                  pango_glyph_string_free (state->glyphs);
-                  state->glyphs = NULL;
+              if (num_chars < item->num_chars)
+                {
+                  new_item = pango_item_split (item, length, num_chars);
 
-                  return BREAK_ALL_FIT;
+                  if (break_needs_hyphen (layout, state, num_chars))
+                    new_item->analysis.flags |= PANGO_ANALYSIS_FLAG_NEED_HYPHEN;
+                  else
+                    new_item->analysis.flags &= ~PANGO_ANALYSIS_FLAG_NEED_HYPHEN;
                 }
+              else
+                new_item = item;
 
-              uninsert_run (line);
-            }
-        }
+              glyphs = shape_run (line, state, new_item);
 
-      /* See how much of the item we can stuff in the line. */
-      width = 0;
+              new_break_width = pango_glyph_string_get_width (glyphs);
 
-      for (num_chars = 0; num_chars < item->num_chars; num_chars++)
-        {
-          extra_width = find_break_extra_width (layout, state, num_chars);
-
-          /* We don't want to walk the entire item if we can help it, but
-           * we need to keep going at least until we've found a breakpoint
-           * that 'works' (as in, it doesn't overflow the budget we have,
-           * or there is no hope of finding a better one).
-           *
-           * We rely on the fact that MIN(width + extra_width, width) is
-           * monotonically increasing.
-           */
-          if (MIN (width + extra_width, width) > state->remaining_width &&
-              break_num_chars < item->num_chars &&
-              (break_width + break_extra_width <= state->remaining_width ||
-               MIN (width + extra_width, width) > break_width + break_extra_width))
-            {
-              break;
-            }
+              if (num_chars > 0 &&
+                  layout->log_attrs[state->start_offset + num_chars - 1].is_white)
+                extra_width = - state->log_widths[state->log_widths_offset + num_chars - 1];
+              else
+                extra_width = 0;
 
-          /* If there are no previous runs we have to take care to grab at least one char. */
-          if (!break_disabled[num_chars] &&
-              can_break_at (layout, state->start_offset + num_chars, retrying_with_char_breaks) &&
-              (num_chars > 0 || line->runs))
-            {
-              /* If we had a breakpoint already, we only want to replace it with a better one. */
-              if (width + extra_width <= state->remaining_width ||
-                  width + extra_width < break_width + break_extra_width ||
-                  (width + extra_width == break_width + break_extra_width &&
-                   num_chars > break_num_chars))
+              g_debug ("measured breakpoint %d: %d", num_chars, new_break_width);
+
+              if (new_item != item)
                 {
+                  pango_item_free (new_item);
+                  pango_item_unsplit (item, length, num_chars);
+                }
+
+              if (break_num_chars == item->num_chars ||
+                  new_break_width + extra_width <= state->remaining_width ||
+                  new_break_width + extra_width <= break_width + break_extra_width)
+                {
+                  g_debug ("accept breakpoint %d: %d + %d <= %d + %d",
+                           num_chars, new_break_width, extra_width, break_width, break_extra_width);
+                  g_debug ("replace bp %d by %d", break_num_chars, num_chars);
                   break_num_chars = num_chars;
-                  break_width = width;
+                  break_width = new_break_width;
                   break_extra_width = extra_width;
+
+                  if (break_glyphs)
+                    pango_glyph_string_free (break_glyphs);
+                  break_glyphs = glyphs;
+                }
+              else
+                {
+                  g_debug ("ignore breakpoint %d", num_chars);
+                  pango_glyph_string_free (glyphs);
                 }
             }
-
-          width += state->log_widths[state->log_widths_offset + num_chars];
         }
 
-      if (layout->wrap == PANGO_WRAP_WORD_CHAR && force_fit && break_width + break_extra_width > state->remaining_width && !retrying_with_char_breaks)
+      g_debug ("bp now %d", break_num_chars);
+      if (num_chars < item->num_chars)
+        width += state->log_widths[state->log_widths_offset + num_chars];
+    }
+
+   if (wrap == PANGO_WRAP_WORD_CHAR && force_fit && break_width + break_extra_width > state->remaining_width)
+    {
+      /* Try again, with looser conditions */
+      g_debug ("does not fit, try again with wrap-char");
+      wrap = PANGO_WRAP_CHAR;
+      break_num_chars = item->num_chars;
+      break_width = orig_width;
+      break_extra_width = orig_extra_width;
+      if (break_glyphs)
+        pango_glyph_string_free (break_glyphs);
+      break_glyphs = NULL;
+      goto retry_break;
+    }
+
+  if (force_fit || break_width + break_extra_width <= state->remaining_width)       /* Successfully broke the item */
+    {
+      if (state->remaining_width >= 0)
         {
-          retrying_with_char_breaks = TRUE;
-          break_num_chars = item->num_chars;
-          width = orig_width;
-          break_width = width;
-          goto retry_break;
+          state->remaining_width -= break_width + break_extra_width;
+          state->remaining_width = MAX (state->remaining_width, 0);
         }
 
-      if (force_fit || break_width + break_extra_width <= state->remaining_width)       /* Successfully broke the item */
+      if (break_num_chars == item->num_chars)
         {
-          int remaining = state->remaining_width;
-
-          if (state->remaining_width >= 0)
-            {
-              state->remaining_width -= break_width;
-              state->remaining_width = MAX (state->remaining_width, 0);
-            }
-
-          if (break_num_chars == item->num_chars)
-            {
-              if (break_needs_hyphen (layout, state, break_num_chars))
-                item->analysis.flags |= PANGO_ANALYSIS_FLAG_NEED_HYPHEN;
-              insert_run (line, state, item, TRUE);
+          if (break_needs_hyphen (layout, state, break_num_chars))
+            item->analysis.flags |= PANGO_ANALYSIS_FLAG_NEED_HYPHEN;
 
-              return BREAK_ALL_FIT;
-            }
-          else if (break_num_chars == 0)
-            {
-              return BREAK_EMPTY_FIT;
-            }
-          else
-            {
-              PangoItem *new_item;
-
-              length = g_utf8_offset_to_pointer (layout->text + item->offset, break_num_chars) - (layout->text + item->offset);
-
-              new_item = pango_item_split (item, length, break_num_chars);
-
-              if (break_needs_hyphen (layout, state, break_num_chars))
-                new_item->analysis.flags |= PANGO_ANALYSIS_FLAG_NEED_HYPHEN;
-              else
-                new_item->analysis.flags &= ~PANGO_ANALYSIS_FLAG_NEED_HYPHEN;
+          insert_run (line, state, item, NULL, TRUE);
 
-              /* Add the width back, to the line, reshape, subtract the new width */
-              state->remaining_width = remaining;
-              insert_run (line, state, new_item, FALSE);
+          if (break_glyphs)
+            pango_glyph_string_free (break_glyphs);
 
-              break_width = pango_glyph_string_get_width (((PangoGlyphItem *)(line->runs->data))->glyphs);
-
-              /* After the shaping, break_width includes a possible hyphen.
-               * We subtract break_extra_width to account for that.
-               */
-              if (new_item->analysis.flags & PANGO_ANALYSIS_FLAG_NEED_HYPHEN)
-                break_width -= break_extra_width;
+          g_debug ("all-fit '%.*s', remaining %d",
+                   item->length, layout->text + item->offset,
+                   state->remaining_width);
+          return BREAK_ALL_FIT;
+        }
+      else if (break_num_chars == 0)
+        {
+          if (break_glyphs)
+            pango_glyph_string_free (break_glyphs);
 
-              if (break_width + break_extra_width > state->remaining_width &&
-                  !break_disabled[break_num_chars])
-                {
-                  /* Unsplit the item, disable the breakpoint, try find a better one.
-                   *
-                   * If we can't find a different breakpoint that works better, we'll
-                   * end up here again, with break_disabled being set, and take the break
-                   */
-                  uninsert_run (line);
-                  pango_item_free (new_item);
-                  pango_item_unsplit (item, length, break_num_chars);
+          g_debug ("empty-fit, remaining %d", state->remaining_width);
+          return BREAK_EMPTY_FIT;
+        }
+      else
+        {
+          PangoItem *new_item;
 
-                  break_disabled[break_num_chars] = TRUE;
+          length = g_utf8_offset_to_pointer (layout->text + item->offset, break_num_chars) - (layout->text + item->offset);
 
-                  goto retry_break;
-                }
+          new_item = pango_item_split (item, length, break_num_chars);
 
-              state->remaining_width -= break_width;
+          insert_run (line, state, new_item, break_glyphs, FALSE);
 
-              state->log_widths_offset += break_num_chars;
+          state->log_widths_offset += break_num_chars;
 
-              /* Shaped items should never be broken */
-              g_assert (!shape_set);
+          /* Shaped items should never be broken */
+          g_assert (!shape_set);
 
-              return BREAK_SOME_FIT;
-            }
+          g_debug ("some-fit '%.*s', remaining %d",
+                   new_item->length, layout->text + new_item->offset,
+                   state->remaining_width);
+          return BREAK_SOME_FIT;
         }
-      else
-        {
-          pango_glyph_string_free (state->glyphs);
-          state->glyphs = NULL;
+    }
+  else
+    {
+      pango_glyph_string_free (state->glyphs);
+      state->glyphs = NULL;
 
-          return BREAK_NONE_FIT;
-        }
+      if (break_glyphs)
+        pango_glyph_string_free (break_glyphs);
+
+      g_debug ("none-fit, remaining %d", state->remaining_width);
+      return BREAK_NONE_FIT;
     }
 }
 
@@ -4293,6 +4370,7 @@ process_line (PangoLayout    *layout,
 
  done:
   pango_layout_line_postprocess (line, state, wrapped);
+  g_debug ("line %d done. remaining %d", state->line_of_par, state->remaining_width);
   add_line (line, state);
   state->line_of_par++;
   state->line_start_index += line->length;
@@ -4558,6 +4636,7 @@ pango_layout_check_lines (PangoLayout *layout)
   state.num_log_widths = 0;
   state.baseline_shifts = NULL;
 
+  g_debug ("START layout");
   do
     {
       int delim_len;
@@ -4684,6 +4763,10 @@ pango_layout_check_lines (PangoLayout *layout)
 
   pango_attr_list_unref (shape_attrs);
   pango_attr_list_unref (attrs);
+
+  int w, h;
+  pango_layout_get_size (layout, &w, &h);
+  g_debug ("DONE %d %d", w, h);
 }
 
 #pragma GCC diagnostic pop
@@ -5838,14 +5921,12 @@ is_tab_run (PangoLayout    *layout,
 }
 
 static void
-zero_line_final_space (PangoLayoutLine *line,
-                       ParaBreakState  *state,
-                       PangoLayoutRun  *run)
+add_missing_hyphen (PangoLayoutLine *line,
+                    ParaBreakState  *state,
+                    PangoLayoutRun  *run)
 {
   PangoLayout *layout = line->layout;
   PangoItem *item = run->item;
-  PangoGlyphString *glyphs;
-  int glyph;
   int line_chars;
 
   line_chars = 0;
@@ -5882,25 +5963,46 @@ zero_line_final_space (PangoLayoutLine *line,
 
       state->remaining_width += pango_glyph_string_get_width (run->glyphs) - width;
     }
+}
+
+static void
+zero_line_final_space (PangoLayoutLine *line,
+                       ParaBreakState  *state,
+                       PangoLayoutRun  *run)
+{
+  PangoLayout *layout = line->layout;
+  PangoItem *item = run->item;
+  PangoGlyphString *glyphs;
+  int glyph;
 
   glyphs = run->glyphs;
   glyph = item->analysis.level % 2 ? 0 : glyphs->num_glyphs - 1;
 
   if (glyphs->glyphs[glyph].glyph == PANGO_GET_UNKNOWN_GLYPH (0x2028))
-    return; /* this LS is visible */
+    {
+      g_debug ("zero final space: visible space");
+      return; /* this LS is visible */
+    }
 
   /* if the final char of line forms a cluster, and it's
    * a whitespace char, zero its glyph's width as it's been wrapped
    */
   if (glyphs->num_glyphs < 1 || state->start_offset == 0 ||
       !layout->log_attrs[state->start_offset - 1].is_white)
-    return;
+    {
+      g_debug ("zero final space: not whitespace");
+      return;
+    }
 
   if (glyphs->num_glyphs >= 2 &&
       glyphs->log_clusters[glyph] == glyphs->log_clusters[glyph + (item->analysis.level % 2 ? 1 : -1)])
-    return;
+    {
 
-  state->remaining_width += glyphs->glyphs[glyph].geometry.width;
+      g_debug ("zero final space: its a cluster");
+      return;
+    }
+
+  g_debug ("zero line final space: collapsing the space");
   glyphs->glyphs[glyph].geometry.width = 0;
   glyphs->glyphs[glyph].glyph = PANGO_GLYPH_EMPTY;
 }
@@ -6400,23 +6502,23 @@ pango_layout_line_postprocess (PangoLayoutLine *line,
 {
   gboolean ellipsized = FALSE;
   
-  DEBUG ("postprocessing", line, state);
+  g_debug ("postprocessing line, %s", wrapped ? "wrapped" : "not wrapped");
 
-  /* Truncate the logical-final whitespace in the line if we broke the line at it
-   */
+  add_missing_hyphen (line, state, line->runs->data);
+  DEBUG ("after hyphen addition", line, state);
+
+  /* Truncate the logical-final whitespace in the line if we broke the line at it */
   if (wrapped)
-    /* The runs are in reverse order at this point, since we prepended them to the list.
-     * So, the first run is the last logical run. */
     zero_line_final_space (line, state, line->runs->data);
 
-  /* Reverse the runs
-   */
+  DEBUG ("after removing final space", line, state);
+
+  /* Reverse the runs */
   line->runs = g_slist_reverse (line->runs);
 
   apply_baseline_shift (line, state);
 
-  /* Ellipsize the line if necessary
-   */
+  /* Ellipsize the line if necessary */
   if (G_UNLIKELY (state->line_width >= 0 &&
                   should_ellipsize_current_line (line->layout, state)))
     {
@@ -6428,22 +6530,17 @@ pango_layout_line_postprocess (PangoLayoutLine *line,
       ellipsized = _pango_layout_line_ellipsize (line, state->attrs, shape_flags, state->line_width);
     }
 
-  DEBUG ("after removing final space", line, state);
-
-  /* Now convert logical to visual order
-   */
+  /* Now convert logical to visual order */
   pango_layout_line_reorder (line);
 
   DEBUG ("after reordering", line, state);
 
-  /* Fixup letter spacing between runs
-   */
+  /* Fixup letter spacing between runs */
   adjust_line_letter_spacing (line, state);
 
   DEBUG ("after letter spacing", line, state);
 
-  /* Distribute extra space between words if justifying and line was wrapped
-   */
+  /* Distribute extra space between words if justifying and line was wrapped */
   if (line->layout->justify && (wrapped || ellipsized || line->layout->justify_last_line))
     {
       /* if we ellipsized, we don't have remaining_width set */
diff --git a/tests/meson.build b/tests/meson.build
index 90bb94ba..b5eda3e7 100644
--- a/tests/meson.build
+++ b/tests/meson.build
@@ -52,9 +52,15 @@ if cairo_dep.found()
     [ 'testmisc', [ 'testmisc.c' ], [ libpangocairo_dep, libpangoft2_dep, glib_dep, harfbuzz_dep ] ],
     [ 'cxx-test', [ 'cxx-test.cpp' ], [ libpangocairo_dep, gobject_dep, harfbuzz_dep ] ],
     [ 'test-harfbuzz', [ 'test-harfbuzz.c' ], [ libpangocairo_dep, gobject_dep, harfbuzz_dep ] ],
-    [ 'test-break', [ 'test-break.c', 'test-common.c', 'validate-log-attrs.c' ], [libpangocairo_dep, glib_dep, harfbuzz_dep ] ]
+    [ 'test-break', [ 'test-break.c', 'test-common.c', 'validate-log-attrs.c' ], [libpangocairo_dep, glib_dep, harfbuzz_dep ] ],
   ]
 
+  if host_system != 'darwin'
+    tests += [
+      [ 'testrandom', [ 'testrandom.c' ], [ libpangocairo_dep, gio_dep ] ],
+    ]
+  endif
+
   if pango_cairo_backends.contains('png')
     tests += [
       [ 'test-pangocairo-threads', [ 'test-pangocairo-threads.c' ], [ libpangocairo_dep, cairo_dep ] ],
diff --git a/tests/testrandom.c b/tests/testrandom.c
new file mode 100644
index 00000000..332376b6
--- /dev/null
+++ b/tests/testrandom.c
@@ -0,0 +1,321 @@
+/* Pango
+ * testmisc.c: Test program for miscellaneous things
+ *
+ * Copyright (C) 2021 Benjamin Otte
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#include "config.h"
+
+#include <locale.h>
+#include <gio/gio.h>
+#include <pango/pangocairo.h>
+
+#define N_SENTENCES 20
+
+static char **ltr_words;
+static gsize n_ltr_words;
+static char **rtl_words;
+static gsize n_rtl_words;
+
+static const char *
+random_word (PangoDirection dir)
+{
+  switch (dir)
+    {
+      case PANGO_DIRECTION_LTR:
+        return ltr_words[g_test_rand_int_range (0, n_ltr_words)];
+      case PANGO_DIRECTION_RTL:
+        return rtl_words[g_test_rand_int_range (0, n_rtl_words)];
+      case PANGO_DIRECTION_TTB_LTR:
+      case PANGO_DIRECTION_TTB_RTL:
+      case PANGO_DIRECTION_WEAK_LTR:
+      case PANGO_DIRECTION_WEAK_RTL:
+      case PANGO_DIRECTION_NEUTRAL:
+      default:
+        return random_word (g_test_rand_bit () ? PANGO_DIRECTION_LTR : PANGO_DIRECTION_RTL);
+    }
+}
+
+static char *
+create_random_sentence (PangoDirection dir)
+{
+  GString *string = g_string_new (NULL);
+  gsize i, n_words;
+
+  n_words = g_test_rand_int_range (0, 15);
+  for (i = 0; i < n_words; i++)
+    {
+      if (i > 0)
+        {
+          if (g_random_int_range (0, 10) == 0)
+            g_string_append_c (string, ',');
+          g_string_append_c (string, ' ');
+        }
+      g_string_append (string, random_word (dir));
+    }
+
+  i = g_test_rand_int_range(0, 4);
+  if (i > 0)
+    g_string_append_c (string, "!.?"[i - 1]);
+
+  return g_string_free (string, FALSE);
+}
+
+typedef struct
+{
+  int set_width;
+  int width;
+  int height;
+} Size;
+
+static int
+compare_size (gconstpointer a,
+              gconstpointer b,
+              gpointer      unused)
+{
+  return ((const Size *) a)->set_width - ((const Size *) b)->set_width;
+}
+
+static void
+layout_check_size (PangoLayout *layout,
+                   int          width,
+                   Size        *out_size)
+{
+  out_size->set_width = width;
+  pango_layout_set_width (layout, width);
+  pango_layout_get_size (layout, &out_size->width, &out_size->height);
+}
+
+static void
+test_wrap_char (gconstpointer data)
+{
+  PangoDirection dir = GPOINTER_TO_UINT (data);
+  PangoFontDescription *desc;
+  PangoContext *context;
+  PangoLayout *layout;
+  char *sentence;
+  Size min, max;
+  Size sizes[100];
+  gsize i, j;
+
+  context = pango_font_map_create_context (pango_cairo_font_map_get_default ());
+  desc = pango_font_description_from_string ("Sans 10");
+  layout = pango_layout_new (context);
+  pango_layout_set_font_description (layout, desc);
+  pango_font_description_free (desc);
+  pango_layout_set_wrap (layout, PANGO_WRAP_WORD_CHAR);
+
+  for (j = 0; j < N_SENTENCES; j++)
+    {
+      sentence = create_random_sentence (dir);
+      pango_layout_set_text (layout, sentence, -1);
+      g_test_message ("%s", sentence);
+      g_free (sentence);
+
+      layout_check_size (layout, -1, &max);
+      layout_check_size (layout, 0, &min);
+      g_assert_cmpint (min.width, <=, max.width);
+      g_assert_cmpint (min.height, >=, max.height);
+
+      for (i = 0; i < G_N_ELEMENTS (sizes); i++)
+        {
+          layout_check_size (layout, g_test_rand_int_range (0, min.width + max.width + 1), &sizes[i]);
+        }
+
+      g_qsort_with_data (sizes, G_N_ELEMENTS (sizes), sizeof (Size), compare_size, NULL);
+
+      g_assert_cmpint (sizes[0].width, >=, min.width);
+      g_assert_cmpint (sizes[0].height, <=, min.height);
+
+      for (i = 1; i < G_N_ELEMENTS (sizes); i++)
+        {
+          g_test_message ("widths %u, %u", sizes[i-1].set_width, sizes[i].set_width);
+          g_assert_cmpint (sizes[i-1].set_width, <=, sizes[i].set_width);
+          g_assert_cmpint (sizes[i-1].width, <=, sizes[i].width);
+          g_assert_cmpint (sizes[i-1].height, >=, sizes[i].height);
+          if (sizes[i-1].width == sizes[i].width &&
+              /* need to make sure we're over the min size, otherwise "ll W"
+               * might be broken to "l- l W" or not depending on set width */
+              sizes[i-1].set_width >= min.width)
+            g_assert_cmpint (sizes[i-1].height, ==, sizes[i].height);
+        }
+
+      if (sizes[i-1].set_width >= max.width)
+        {
+          g_assert_cmpint (sizes[i-1].width, ==, max.width);
+          g_assert_cmpint (sizes[i-1].height, ==, max.height);
+        }
+      else
+        {
+          g_assert_cmpint (sizes[i-1].width, <, max.width);
+          g_assert_cmpint (sizes[i-1].height, >, max.height);
+        }
+    }
+
+  g_object_unref (layout);
+  g_object_unref (context);
+}
+
+static void
+test_wrap_char_min_width (gconstpointer data)
+{
+  PangoDirection dir = GPOINTER_TO_UINT (data);
+  PangoFontDescription *desc;
+  PangoContext *context;
+  PangoLayout *test_layout, *ref_layout;
+  char *sentence, *s;
+  GString *ref_string;
+  gsize j;
+  int test_width, ref_width;
+
+  context = pango_font_map_create_context (pango_cairo_font_map_get_default ());
+  desc = pango_font_description_from_string ("Sans 10");
+  ref_layout = pango_layout_new (context);
+  pango_layout_set_font_description (ref_layout, desc);
+  test_layout = pango_layout_new (context);
+  pango_layout_set_font_description (test_layout, desc);
+  pango_layout_set_wrap (test_layout, PANGO_WRAP_WORD_CHAR);
+  pango_layout_set_width (test_layout, 0);
+  pango_font_description_free (desc);
+
+  for (j = 0; j < N_SENTENCES; j++)
+    {
+      sentence = create_random_sentence (dir);
+      pango_layout_set_text (test_layout, sentence, -1);
+      g_test_message ("%s", sentence);
+      ref_string = g_string_new ("");
+      for (s = sentence; *s; s = g_utf8_next_char (s))
+        {
+          g_string_append_unichar (ref_string, g_utf8_get_char (s));
+          g_string_append_unichar (ref_string, g_test_rand_bit () ? 0x2010 : '-');
+          g_string_append_c (ref_string, '\n');
+        }
+      pango_layout_set_text (ref_layout, ref_string->str, ref_string->len);
+      g_string_free (ref_string, TRUE);
+      g_free (sentence);
+
+      pango_layout_get_size (test_layout, &test_width, NULL);
+      pango_layout_get_size (ref_layout, &ref_width, NULL);
+
+      g_assert_cmpint (test_width, <=, ref_width);
+    }
+
+  g_object_unref (test_layout);
+  g_object_unref (ref_layout);
+  g_object_unref (context);
+}
+
+static char **
+load_hunspell_words (const char  *language)
+{
+  char *path;
+  GBytes *bytes;
+  GFile *file;
+  char **words;
+  gsize i;
+
+  path = g_strdup_printf ("/usr/share/myspell/%s.dic", language);
+  file = g_file_new_for_path (path);
+  g_free (path);
+  bytes = g_file_load_bytes (file, NULL, NULL, NULL);
+  g_object_unref (file);
+  if (bytes == NULL)
+    return NULL;
+
+  words = g_strsplit (g_bytes_get_data (bytes, NULL), "\n", -1);
+  g_bytes_unref (bytes);
+
+  if (words == NULL || words[0] == NULL)
+    {
+      g_free (words);
+      return NULL;
+    }
+
+  for (i = 1; words[i]; i++)
+    {
+      char *slash = strchr (words[i], '/');
+      if (slash)
+        *slash = 0;
+    }
+
+  return words;
+}
+
+static char **
+init_ltr_words (void)
+{
+  GFile *file;
+  GBytes *bytes;
+  char **result;
+
+  result = load_hunspell_words ("en_US");
+  if (result)
+    return result;
+
+  file = g_file_new_for_path ("/usr/share/dict/words");
+  bytes = g_file_load_bytes (file, NULL, NULL, NULL);
+  g_object_unref (file);
+  if (bytes)
+    {
+      result = g_strsplit (g_bytes_get_data (bytes, NULL), "\n", -1);
+      g_bytes_unref (bytes);
+      return result;
+    }
+
+  return g_strsplit ("lorem ipsum dolor sit amet consectetur adipisci elit sed eiusmod tempor incidunt labore et dolore magna aliqua ut enim ad minim veniam quis nostrud exercitation ullamco laboris nisi ut aliquid ex ea commodi consequat", " ", -1);
+}
+
+static char **
+init_rtl_words (void)
+{
+  char **result;
+
+  result = load_hunspell_words ("he_IL");
+  if (result)
+    return result;
+
+  return g_strsplit ("לורם איפסום דולור סיט אמט קונסקטטור אדיפיסינג אלית קולורס מונפרד אדנדום סילקוף מרגשי ומרגשח עמחליף לפרומי בלוף קינץ תתיח לרעח לת צשחמי צש בליא מנסוטו צמלח לביקו ננבי צמוקו בלוקריה שיצמה ברורק להאמית קרהשק סכעיט דז מא מנכם למטכין נשואי מנורךגולר מונפרר סוברט לורם שבצק יהול לכנוץ בעריר גק ליץ ושבעגט ושבעגט לבם סולגק בראיט ולחת צורק מונחף בגורמי מגמש תרבנך וסתעד לכנו סתשם השמה - לתכי מורגם בורק? לתיג ישבעס", " ", -1);
+}
+
+int
+main (int argc, char *argv[])
+{
+  int result;
+
+  g_test_init (&argc, &argv, NULL);
+  setlocale (LC_ALL, "");
+
+  ltr_words = init_ltr_words ();
+  n_ltr_words = g_strv_length (ltr_words);
+  rtl_words = init_rtl_words ();
+  n_rtl_words = g_strv_length (rtl_words);
+
+  g_test_add_data_func ("/layout/ltr/wrap-char", GUINT_TO_POINTER (PANGO_DIRECTION_LTR), test_wrap_char);
+  g_test_add_data_func ("/layout/rtl/wrap-char", GUINT_TO_POINTER (PANGO_DIRECTION_RTL), test_wrap_char);
+  g_test_add_data_func ("/layout/any/wrap-char", GUINT_TO_POINTER (PANGO_DIRECTION_NEUTRAL), test_wrap_char);
+  g_test_add_data_func ("/layout/ltr/wrap-char-min-width", GUINT_TO_POINTER (PANGO_DIRECTION_LTR), test_wrap_char_min_width);
+  g_test_add_data_func ("/layout/rtl/wrap-char-min-width", GUINT_TO_POINTER (PANGO_DIRECTION_RTL), test_wrap_char_min_width);
+  g_test_add_data_func ("/layout/any/wrap-char-min-width", GUINT_TO_POINTER (PANGO_DIRECTION_NEUTRAL), test_wrap_char_min_width);
+
+  result = g_test_run ();
+
+  g_strfreev (ltr_words);
+  g_strfreev (rtl_words);
+
+  return result;
+}