Windows implementation of multiline RenderText

ui/gfx/render_text_win.cc

Index: ui/gfx/render_text_win.cc
diff --git a/ui/gfx/render_text_win.cc b/ui/gfx/render_text_win.cc
index 05be785e4a53921c4225a43554f869377b445544..9b854ce260b23f0ada6d7c2bf5e5a2f043b378ed 100644
--- a/ui/gfx/render_text_win.cc
+++ b/ui/gfx/render_text_win.cc
@@ -129,6 +129,27 @@ bool IsUnicodeBidiControlCharacter(char16 c) {
          c == base::i18n::kRightToLeftOverride;
 }
 
+// Returns the corresponding glyph range of the given character range.
+ui::Range CharRangeToGlyphRange(const ui::Range& range,
+                                const internal::TextRun& run) {
+  CHECK(run.range.Contains(ui::Range(range.start() + run.range.start(),
+                                     range.end() + run.range.start())));
+  CHECK(!range.is_reversed());
+  CHECK(!range.is_empty());
+  int start = 0;
+  int end = 0;
+  if (run.script_analysis.fRTL) {
+    start = run.logical_clusters[range.end() - 1];
+    end = range.start() > 0 ? run.logical_clusters[range.start() - 1]
+                            : run.glyph_count;
+  } else {
+    start = run.logical_clusters[range.start()];
+    end = range.end() < run.range.length() ? run.logical_clusters[range.end()]
+                                           : run.glyph_count;
+  }
+  return ui::Range(start, end);
+}
+
 }  // namespace
 
 namespace internal {
@@ -173,6 +194,10 @@ int GetGlyphXBoundary(const internal::TextRun* run,
   return run->preceding_run_widths + x;
 }
 
+struct LineSegmentWin : LineSegment {
+  internal::TextRun* run;
+};
+
 }  // namespace internal
 
 // static
@@ -198,7 +223,15 @@ RenderTextWin::~RenderTextWin() {
 
 Size RenderTextWin::GetStringSize() {
   EnsureLayout();
-  return string_size_;
+  return Size(string_size_.width(), string_size_.height());
+}
+
+Size RenderTextWin::GetMultilineTextSize() {
+  EnsureLayout();
+  if (!multiline())
+    return Size(display_rect().width(), string_size_.height());
+  return Size(display_rect().width(),
+              lines().back().preceding_heights + lines().back().height);
 }
 
 int RenderTextWin::GetBaseline() {
@@ -367,9 +400,10 @@ std::vector<Rect> RenderTextWin::GetSubstringBounds(const ui::Range& range) {
                          TextIndexToLayoutIndex(range.end()));
   DCHECK(ui::Range(0, GetLayoutText().length()).Contains(layout_range));
 
-  std::vector<Rect> bounds;
+  std::vector<ui::Range> bounds;
+  std::vector<Rect> rects;
   if (layout_range.is_empty())
-    return bounds;
+    return rects;
 
   // Add a Rect for each run/selection intersection.
   // TODO(msw): The bounds should probably not always be leading the range ends.
@@ -380,17 +414,21 @@ std::vector<Rect> RenderTextWin::GetSubstringBounds(const ui::Range& range) {
       DCHECK(!intersection.is_reversed());
       ui::Range range_x(GetGlyphXBoundary(run, intersection.start(), false),
                         GetGlyphXBoundary(run, intersection.end(), false));
-      Rect rect(range_x.GetMin(), 0, range_x.length(), run->font.GetHeight());
-      rect.set_origin(ToViewPoint(rect.origin()));
-      // Union this with the last rect if they're adjacent.
-      if (!bounds.empty() && rect.SharesEdgeWith(bounds.back())) {
-        rect.Union(bounds.back());
+      range_x = ui::Range(range_x.GetMin(), range_x.GetMax());
+      // Union this with the last range if they're adjacent.
+      DCHECK(bounds.empty() || bounds.back().GetMin() != range_x.GetMax());
+      if (!bounds.empty() && bounds.back().GetMax() == range_x.GetMin()) {
+        range_x = ui::Range(bounds.back().GetMin(), range_x.GetMax());
         bounds.pop_back();
       }
-      bounds.push_back(rect);
+      bounds.push_back(range_x);
     }
   }
-  return bounds;
+  for (size_t i = 0; i < bounds.size(); ++i) {
+    std::vector<Rect> current_rects = RangeToViewRects(bounds[i]);
+    rects.insert(rects.end(), current_rects.begin(), current_rects.end());
+  }
+  return rects;
 }
 
 size_t RenderTextWin::TextIndexToLayoutIndex(size_t index) const {
@@ -428,23 +466,178 @@ void RenderTextWin::ResetLayout() {
 }
 
 void RenderTextWin::EnsureLayout() {
-  if (!needs_layout_)
-    return;
-  // TODO(msw): Skip complex processing if ScriptIsComplex returns false.
-  ItemizeLogicalText();
-  if (!runs_.empty())
-    LayoutVisualText();
-  needs_layout_ = false;
+  if (needs_layout_) {
+    // TODO(msw): Skip complex processing if ScriptIsComplex returns false.
+    ItemizeLogicalText();
+    if (!runs_.empty())
+      LayoutVisualText();
+    needs_layout_ = false;
+    set_lines_valid(false);
+  }
+  if (!lines_valid()) {

[msw, 2013/07/17 06:47:18]

Why is this a separate step at all? I figure multi-line layout should be part of
the layout process. Are you worried about display_rect changes that would
invalidate only the lines and not the text-space layout? I guess that's valid,
but deserves a comment.

[ckocagil, 2013/07/19 19:40:50]

Yes, the separate step is to avoid itemizing, glyph generation and other stuff
every time we resize the display_rect(). Added a comment.

+    ComputeLines();
+    set_lines_valid(true);
+  }
 }
-
-void RenderTextWin::DrawVisualText(Canvas* canvas) {
+
+void RenderTextWin::ComputeLines() {

[ckocagil, 2013/07/19 19:40:50]

I refactored this method, sorry for not doing this earlier. Please review the
new version, thanks!

   DCHECK(!needs_layout_);
 
-  // Skia will draw glyphs with respect to the baseline.
-  Vector2d offset(GetTextOffset() + Vector2d(0, common_baseline_));
+  std::vector<internal::Line> lines;
+  lines.push_back(internal::Line());
+
+  int max_width = display_rect().width();

[msw, 2013/07/17 06:47:18]

nit: const.

+
+  std::vector<size_t> breaks = line_breaks();
+  for (size_t i = 0; i < runs_.size(); ++i)
+    breaks.push_back(runs_[i]->range.start());
+  if (breaks.empty())
+    breaks.push_back(0);
+  std::sort(breaks.begin(), breaks.end());

[msw, 2013/07/17 06:47:18]

Is this necessary? The BreakIterator advancement should keep them in order, and
0 is only added if there are no other breaks.

+
+  size_t* last_break = &breaks[0];
+
+  int line_x = 0; // x from the line beginning
+  int text_x = 0; // x from the text beginning
+  size_t segment_start_char = 0; // offset of current segment beginning
+  int segment_start_pos = 0; // position of current segment beginning
+  internal::TextRun* run;
+  size_t line_beginning = 0;
+  int preceeding_line_heights = 0;
+
+  // Traverse all runs in visual order. If a run doesn't fit the current line,
+  // iterate over each character in the run in logical order until the next
+  // character doesn't fit the current line, then do the one of the following:
+  // - If the last line break before current character is not a line beginning,
+  // roll back there and skip a line.
+  // - If the last line break is at the line beginning and there are more than
+  // one characters in the line, roll back one character and skip a line.
+  // - If neither conditions are met, assume we could fit this character and
+  // skip a line.
+  for (size_t i = 0; i < runs_.size(); ++i) {

[msw, 2013/07/17 06:47:18]

This whole loop is still pretty difficult to follow, even with the top comment.
Though the behavior is complex, additional comments throughout the loop
explaining each step could add a lot of clarity. It might help to factor out
parts of this code into separate functions and ensure all variable names are
consistent and clear.

+    run = runs_[visual_to_logical_[i]];
+
+    if (!multiline() || line_x + run->width <= max_width) {

[msw, 2013/07/17 06:47:18]

nit: an example comment here would be:
// The whole run fits on this line; add a corresponding line segment.

+      internal::LineSegmentWin* segment = new internal::LineSegmentWin;
+      segment->char_pos = run->range;
+      segment->x_pos = ui::Range(text_x, text_x + run->width);
+      segment->run = run;
+      lines.back().segments.push_back(segment);
+      lines.back().width += run->width;
+      lines.back().height = std::max(lines.back().height,

[msw, 2013/07/17 06:47:18]

This height and baseline calculation should work similar to 
https://codereview.chromium.org/19352002/diff/1007/ui/gfx/font_list.cc
(I suppose we'd need to track each line's max ascent too?)

+                                     run->font.GetHeight());
+      lines.back().baseline = std::max(lines.back().baseline,
+                                       run->font.GetBaseline());
+      segment_start_char += run->range.length();
+      segment_start_pos += run->width;
+      line_x += run->width;
+      text_x += run->width;
+      continue;
+    }
+
+    bool rtl = run->script_analysis.fRTL;
+    int break_x = 0;

[msw, 2013/07/17 06:47:18]

Comment on what this is.

+
+    last_break = &breaks[0];
+
+    segment_start_char = run->range.start();
+    segment_start_pos = text_x;
+
+    int run_beginning_x = text_x;
+    // To find the text coordinates of RTL LineSegments, store their widths in a

[msw, 2013/07/17 06:47:18]

I'm still having trouble understanding exactly how this works. I wonder why an
LTR run in a predominantly RTL string doesn't need this same process (e.g.
positioning an english phrase LineSegment amid an arabic sentence). Could you
enlighten me here, extrapolate on this comment (perhaps with a diagram), and/or
revise the code?

+    // vector and apply them after processing all segments in the run.
+    typedef std::pair<internal::LineSegment*, int> RtlWidth;
+    std::vector<RtlWidth> rtl_widths;
+
+    for (size_t j = 0; j < run->range.length(); ++j) {

[msw, 2013/07/17 06:47:18]

I think you'll need to check IsCursorablePosition or use a char iterator or
something that actually breaks by characters instead of incrementing j by one.
This will need to avoid advancing or rolling back by half of a surrogate pair,
etc. If it helps, you could abandon per-character fitting for now and only break
on line breaks. That'd cause excessively long words to overflow the display
rect, but I think it'd solve the most common and simple line wrapping behavior.

+      size_t offset = j + run->range.start();
+      while (last_break != &breaks.back() && offset >= *(last_break + 1)) {

[msw, 2013/07/17 06:47:18]

Comment on what this is doing; it's not obvious.

+        ++last_break;
+        break_x = 0;

[msw, 2013/07/17 06:47:18]

Must this be reset in the loop to correspond with break incrementation?

+      }
+
+      ui::Range glyphs = CharRangeToGlyphRange(ui::Range(j, j + 1), *run);

[msw, 2013/07/17 06:47:18]

CharRangeToGlyphRange is a decent example of a simple abstraction that really
helps clarify the calling code. I think the rest of this code would greatly
benefit from additional helper function building blocks, even if they're only
called once. For example, wouldn't it be awesome to have a function that takes a
char index and a width, and returns the next LineSegment that fits within the
width? That's a reasonably small and self-contained task that could make this
code simpler, and not be too complex itself.

+
+      int char_width = 0;
+      for (size_t k = glyphs.start(); k < glyphs.end(); ++k)
+        char_width += run->advance_widths[k];
+
+      line_x += char_width;
+      text_x += char_width;
+      break_x += char_width;
+
+      if (line_x > max_width) {

[msw, 2013/07/17 06:47:18]

Could this check "|| j == (run.range.length() - 1)" to add the last LineSegment
of a multi-line run onto the current line?

+        if (*last_break > line_beginning) {
+          // Roll back to last break.
+          text_x -= break_x;
+          j = *last_break - run->range.start() - 1;
+          offset = *last_break;
+        } else if (line_x != char_width) {

[msw, 2013/07/17 06:47:18]

nit: should this be line_x > char_width?

+          // Roll back one character.
+          text_x -= char_width;
+          --j;
+        } // else: Assume the current character fits; continue from next line.

[msw, 2013/07/17 06:47:18]

Does this mean that the if last condition failed then a single char did not fit
on the line? Can you clarify and/or move this comment? I don't quite follow.

+        line_beginning = offset;
+        line_x = 0;
+        break_x = 0;
+
+        internal::LineSegmentWin* segment = new internal::LineSegmentWin;
+        if (rtl)
+          rtl_widths.push_back(RtlWidth(segment, text_x - segment_start_pos));
+        else
+          segment->x_pos = ui::Range(segment_start_pos, text_x);
+        segment->char_pos = ui::Range(segment_start_char, offset);
+        segment->run = run;
+        lines.back().segments.push_back(segment);
+        lines.back().width += text_x - segment_start_pos;
+        lines.back().height = std::max(lines.back().height,
+                                       segment->run->font.GetHeight());
+        preceeding_line_heights += lines.back().height;
+        lines.back().baseline = std::max(lines.back().baseline,
+                                         segment->run->font.GetBaseline());
+
+        lines.push_back(internal::Line());
+        lines.back().preceding_heights = preceeding_line_heights;
+
+        segment_start_pos = text_x;
+        segment_start_char = offset;
+        continue;
+      }
+    }
+    if (segment_start_char != run->range.end()) {

[msw, 2013/07/17 06:47:18]

Add a blank line above and comment here, what is this doing? Is it adding the
final remaining run characters that didn't fit on the previous line to the
current Line's first line segment? I'm not sure I follow, sorry. This code would
be much clearer and more maintainable with high-level comments.

+      internal::LineSegmentWin* segment = new internal::LineSegmentWin;
+      if (rtl)
+        rtl_widths.push_back(RtlWidth(segment, text_x - segment_start_pos));
+      else
+        segment->x_pos = ui::Range(segment_start_pos, text_x);
+      segment->char_pos = ui::Range(segment_start_char, run->range.end());
+      segment->run = run;
+      lines.back().segments.push_back(segment);
+      lines.back().width += text_x - segment_start_pos;
+      lines.back().height = std::max(lines.back().height,
+                                     segment->run->font.GetHeight());
+      lines.back().baseline = std::max(lines.back().baseline,
+                                       segment->run->font.GetBaseline());
+      segment_start_char = run->range.end();
+      segment_start_pos = text_x;
+    }
+
+    int rtl_total_widths = 0;
+    while (!rtl_widths.empty()) {
+      const RtlWidth& rtl_width = rtl_widths.back();
+      rtl_width.first->x_pos = ui::Range(run_beginning_x + rtl_total_widths,
+          run_beginning_x + rtl_total_widths + rtl_width.second);
+      rtl_widths.pop_back();
+      rtl_total_widths += rtl_width.second;
+    }
+  }
+
+  set_lines(&lines);
+}
 
-  SkScalar x = SkIntToScalar(offset.x());
-  SkScalar y = SkIntToScalar(offset.y());
+void RenderTextWin::DrawVisualText(Canvas* canvas) {
+  DCHECK(!needs_layout_);
+  DCHECK(!multiline() || lines_valid());
 
   std::vector<SkPoint> pos;
 
@@ -459,30 +652,45 @@ void RenderTextWin::DrawVisualText(Canvas* canvas) {
   renderer.SetFontSmoothingSettings(
       smoothing_enabled, cleartype_enabled && !background_is_transparent());
 
-  for (size_t i = 0; i < runs_.size(); ++i) {
-    // Get the run specified by the visual-to-logical map.
-    internal::TextRun* run = runs_[visual_to_logical_[i]];
-
-    if (run->glyph_count == 0)
-      continue;
+  SkScalar glyph_x = SkIntToScalar(0);
 
-    // Based on WebCore::skiaDrawText.
-    pos.resize(run->glyph_count);
-    SkScalar glyph_x = x;
-    for (int glyph = 0; glyph < run->glyph_count; glyph++) {
-      pos[glyph].set(glyph_x + run->offsets[glyph].du,
-                     y + run->offsets[glyph].dv);
-      glyph_x += SkIntToScalar(run->advance_widths[glyph]);
+  for (size_t line = 0; line < lines().size(); ++line) {
+    Vector2d offset(0, lines()[line].baseline);
+    offset += GetLineOffset(line);
+    for (size_t i = 0; i < lines()[line].segments.size(); ++i) {
+      const internal::LineSegmentWin* segment =
+          static_cast<internal::LineSegmentWin*>(lines()[line].segments[i]);
+      // TODO(ckocagil): necessary? maybe prevent this from happening.

[msw, 2013/07/17 06:47:18]

Does it currently happen? Can you just [D]CHECK against it if not?

[ckocagil, 2013/07/19 19:40:50]

Done.

+      if (segment->char_pos.is_empty())
+        continue;
+      int segment_start_pos = glyph_x;
+      internal::TextRun* run = segment->run;
+      DCHECK_GE(segment->char_pos.start(), run->range.start());
+      DCHECK_LT(segment->char_pos.start(),

[msw, 2013/07/17 06:47:18]

Did you mean segment->char_pos.end()?

[ckocagil, 2013/07/19 19:40:50]

I changed this to use ui::Range::Contains.

+                run->range.start() + run->glyph_count);

[msw, 2013/07/17 06:47:18]

Did you mean run->range.start() + run->range.length()?

[ckocagil, 2013/07/19 19:40:50]

Same as above.

+      int start_char = segment->char_pos.start() - run->range.start();

[msw, 2013/07/17 06:47:18]

nit: const here and for the three ints below too.

[ckocagil, 2013/07/19 19:40:50]

I inlined these three ints.

+      int end_char = start_char + segment->char_pos.length();
+      ui::Range glyphs = CharRangeToGlyphRange(ui::Range(start_char, end_char),
+                                               *run);
+      int start = glyphs.start();

[msw, 2013/07/17 06:47:18]

Consider just inlining use of the |glyphs| range if it's not too ugly.

[ckocagil, 2013/07/19 19:40:50]

Done.

+      int end = glyphs.end();
+      DCHECK_LE(start, end);

[msw, 2013/07/17 06:47:18]

Will this code work okay if start == end?

[ckocagil, 2013/07/19 19:40:50]

It now skips this case and DCHECKs that the segment wasn't empty (which is
something I don't want to see).

+      pos.resize(end - start);
+      for (int g = start; g < end; ++g) {
+        pos[g - start].set(glyph_x + offset.x() + run->offsets[g].du,
+                           offset.y() + run->offsets[g].dv);
+        glyph_x += SkIntToScalar(run->advance_widths[g]);
+      }
+      renderer.SetTextSize(run->font.GetFontSize());
+      renderer.SetFontFamilyWithStyle(run->font.GetFontName(), run->font_style);
+      renderer.SetForegroundColor(run->foreground);
+      renderer.DrawPosText(&pos[0], &run->glyphs[start], end - start);
+      renderer.DrawDecorations(segment_start_pos + offset.x(),
+                               offset.y(), segment->x_pos.length(),
+                               run->underline, run->strike,
+                               run->diagonal_strike);
     }
-
-    renderer.SetTextSize(run->font.GetFontSize());
-    renderer.SetFontFamilyWithStyle(run->font.GetFontName(), run->font_style);
-    renderer.SetForegroundColor(run->foreground);
-    renderer.DrawPosText(&pos[0], run->glyphs.get(), run->glyph_count);
-    renderer.DrawDecorations(x, y, run->width, run->underline, run->strike,
-                             run->diagonal_strike);
-
-    x = glyph_x;
+    glyph_x = SkIntToScalar(0);
   }
 }