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 0469c0f5b7a61a6770457d330cb22d6e1c09401b..218b4ba31db9de896ace8e8b1adfbf7827160d80 100644
--- a/ui/gfx/render_text_win.cc
+++ b/ui/gfx/render_text_win.cc
@@ -125,6 +125,27 @@ bool IsUnicodeBidiControlCharacter(char16 c) {
          c == base::i18n::kRightToLeftOverride;
 }
 
+ui::Range CharRangeToGlyphRange(const ui::Range& range,

[Alexei Svitkine (slow), 2013/07/09 15:35:13]

Add a comment.

[ckocagil, 2013/07/13 16:05:10]

Done.

+                                internal::TextRun* run) {

[Alexei Svitkine (slow), 2013/07/09 15:35:13]

This should be const and possibly by ref to prevent NULL from being passed.

[ckocagil, 2013/07/13 16:05:10]

Done.

+  DCHECK_GE(range.start(), 0u);
+  DCHECK_LE(range.end(), run->range.length());

[msw, 2013/07/10 04:01:56]

nit: Can you just [D]CHECK(run->range.Contains(range)) instead?
You might also need to handle reversed or empty |range|s or CHECK against them.
You might want to favor CHECK over DCHECK to avoid using invalid memory.

[ckocagil, 2013/07/13 16:05:10]

Done.
Done.
Done.

+  DCHECK_LE(range.start(), range.end());
+  bool rtl = run->script_analysis.fRTL;

[Alexei Svitkine (slow), 2013/07/09 15:35:13]

Inline this, since you only use it once.

[ckocagil, 2013/07/13 16:05:10]

Done.

+  int start_char = range.start();
+  int end_char = range.end();

[Alexei Svitkine (slow), 2013/07/09 15:35:13]

Nit: You don't need local vars for start_char and end_char, just inline these
below.

[ckocagil, 2013/07/13 16:05:10]

Done.

+  int start, end;

[Alexei Svitkine (slow), 2013/07/09 15:35:13]

Nit: Separate lines.

[msw, 2013/07/10 04:01:56]

Also, explicitly init each to 0.

[ckocagil, 2013/07/13 16:05:10]

Both done.

+  if (rtl) {
+    start = run->logical_clusters[end_char - 1];
+    end = start_char > 0 ? run->logical_clusters[start_char - 1]
+                         : run->glyph_count;
+  } else {
+    start = run->logical_clusters[start_char];
+    end = end_char < run->glyph_count ? run->logical_clusters[end_char]

[msw, 2013/07/10 04:01:56]

Shouldn't this be end_char < run->range.length() ?

[ckocagil, 2013/07/13 16:05:10]

Shame on me, this would be a subtle bug. Thanks! Done.

+                                      : run->glyph_count;
+  }
+  return ui::Range(start, end);
+}
+
 }  // namespace
 
 namespace internal {
@@ -192,7 +213,17 @@ RenderTextWin::~RenderTextWin() {
 
 Size RenderTextWin::GetStringSize() {
   EnsureLayout();
-  return string_size_;
+  // TODO: is this the right place to add +1 for cursor?
+  return Size(string_size_.width() + 1, string_size_.height());

[Alexei Svitkine (slow), 2013/07/09 15:35:13]

Can you explain why this is needed (and why it wasn't before)?

Also, remember that cursor may not be visible, so at the very least this should
be conditional.

Also, TODO should be TODO(ckocagil)

[msw, 2013/07/10 04:01:56]

I think it's already handled by RenderText::GetContentWidth, no?

[ckocagil, 2013/07/13 16:05:10]

Yes, I later noticed it. Removing the +1 here.

+}
+
+Size RenderTextWin::GetMultilineTextSize() {
+  EnsureLayout();
+  if (!multiline())
+    return Size(display_rect().width(), string_size_.height());
+  ComputeLines();

[msw, 2013/07/10 04:01:56]

Do this as needed in EnsureLayout().

[ckocagil, 2013/07/13 16:05:10]

Done.

+  return Size(display_rect().width(),
+      string_size_.height() * lines().size());

[Alexei Svitkine (slow), 2013/07/09 15:35:13]

Are all lines guaranteed to have the same height? What if one line has taller
runs then the others?

[ckocagil, 2013/07/13 16:05:10]

Done, we use per-line heights now.

 }
 
 int RenderTextWin::GetBaseline() {
@@ -359,9 +390,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.
@@ -372,17 +404,20 @@ 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.
+      if (!bounds.empty() && bounds.back().GetMax() == range_x.GetMin()) {

[msw, 2013/07/10 04:01:56]

This will miss cases where range_x.GetMax() == bounds.back().GetMin().
(I'm not sure that happens in practice, but it's worth investigating)

[ckocagil, 2013/07/13 16:05:10]

Added a DCHECK for this case but it doesn't seem to be hit.

+        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], 0);
+    rects.insert(rects.end(), current_rects.begin(), current_rects.end());
+  }
+  return rects;
 }
 
 size_t RenderTextWin::TextIndexToLayoutIndex(size_t index) const {
@@ -420,26 +455,145 @@ bool RenderTextWin::IsCursorablePosition(size_t position) {
 void RenderTextWin::ResetLayout() {
   // Layout is performed lazily as needed for drawing/metrics.
   needs_layout_ = true;
+  set_lines_valid(false); // TODO: do we need this?

[msw, 2013/07/10 04:01:56]

I think lines_valid_ should implicitly be part of needs_layout_.

[ckocagil, 2013/07/13 16:05:10]

Done.

 }
 
 void RenderTextWin::EnsureLayout() {
   if (!needs_layout_)
     return;
+
   // TODO(msw): Skip complex processing if ScriptIsComplex returns false.
   ItemizeLogicalText();
   if (!runs_.empty())
     LayoutVisualText();
+
   needs_layout_ = false;
 }
+
+void RenderTextWin::ComputeLines() {
+  if (lines_valid() || !multiline())
+    return;
+
+  EnsureLayout();
+
+  std::vector<ScopedVector<internal::LineSegment> > lines;

[msw, 2013/07/10 04:01:56]

Should these be LineSegmentWin?

[ckocagil, 2013/07/13 16:05:10]

We now use Line structs here.

+  lines.push_back(ScopedVector<internal::LineSegment>());
+
+  int max_width = display_rect().width();
+
+  std::vector<size_t> breaks = line_breaks();
+  for (size_t i = 0; i < runs_.size(); ++i)
+    breaks.push_back(runs_[i]->range.start());
+  breaks.push_back(0); // TODO: necessary?

[msw, 2013/07/10 04:01:56]

Probably not necessary, resolve the TODO.

[ckocagil, 2013/07/13 16:05:10]

We need at least one element, now I'm only adding 0 if braeks is empty.

+  breaks.push_back(-1);

[msw, 2013/07/10 04:01:56]

What's this unsigned wraparound max size_t used for?
The text length should never equal/exceed this value.

[ckocagil, 2013/07/13 16:05:10]

This was used as an anchor so we didn't go past the vector, but this was too
cryptic, I'm now explicitly checking for that case below.

+  std::sort(breaks.begin(), breaks.end());
+  std::unique(breaks.begin(), breaks.end());

[Alexei Svitkine (slow), 2013/07/09 15:35:13]

Is this needed? If so, perhaps add a test that will cover this case.

[ckocagil, 2013/07/13 16:05:10]

This shouldn't be needed. Removing.

+
+  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;
+
+  for (size_t i = 0; i < runs_.size(); ++i) {

[msw, 2013/07/10 04:01:56]

This function needs comments explaining what it's doing, it's rather tough to
follow. I think formalizing a Line structure and potentially making a
cross-platform notion of a TextRun could yield some clarity here.

[ckocagil, 2013/07/13 16:05:10]

Added a comment explaining what this function does.

+    // TODO: might need |line_break = range.start| to break at run beginnings

[msw, 2013/07/10 04:01:56]

nit: resolve TODO

[ckocagil, 2013/07/13 16:05:10]

Done.

+    run = runs_[visual_to_logical_[i]];
+    bool rtl = run->script_analysis.fRTL;
+    int break_x = 0;
+
+    last_break = &breaks[0];
+
+    segment_start_char = run->range.start();
+    segment_start_pos = text_x;
+
+    int run_beginning_x = text_x;
+    typedef std::pair<internal::LineSegment*, int> RtlWidth;

[msw, 2013/07/10 04:01:56]

Comment here, what's an RtlWidth?

[ckocagil, 2013/07/13 16:05:10]

Done.

+    std::vector<RtlWidth> rtl_widths;
+
+    for (size_t c = 0; c < run->range.length(); ++c) {

[Alexei Svitkine (slow), 2013/07/09 15:35:13]

Use i, j, k for loops, so this should be j and the inner loop again should be k.

[msw, 2013/07/10 04:01:56]

There must be a better approach than fitting lines character by character.
First, the code should try fitting entire runs into a line. Then, only if a run
exceeds some substantial remaining available width of the line, try splitting
the run to fit some portion of its content onto that line before moving to the
next line.

You could either destructively modify the runs to split them up as needed (and
ensure they're rebuilt on edits/display_rect.width changes), or if we don't want
to split runs, draw different clipped portions of the run for each line it
occurs on.

Also, it'd probably be worthwhile to do a binary search to find a suitable
length of the run to use, and/or breaking by word before breaking by character.
And it should start the binary search at some reasonable estimate from the
font's average character width and the remaining available width.

Overall, I think it'd be best to outline a high level strategy and discuss it
with us before implementing the complex and hairy details. This might really be
the right way to go, but I think discussing the alternatives would be
enlightening. I know you must have put a lot of work into this already, and I'm
sorry for letting your work progress this far without more discussion :( That's
my failing, not yours!

[ckocagil, 2013/07/13 16:05:10]

Actually I have thought about most of the stuff you outlined here, including the
binary search part (but for some reason I didn't think of adding runs that fit
without iterating over their characters). It felt like it would be more
complicated without gaining us much in performance. Also, after adding line
segment structs I felt comfortable with going ahead with the most
straightforward implementation since it would be easy to refactor this method
without affecting any other part (and it looks like it is!).

Do you think we need these changes before landing this CL? I have no problems
with having to refactor this method at all. I can refactor, simplify and do the
optimizations you mentioned in this comment.

[ckocagil, 2013/07/13 16:05:10]

Done.

+      size_t offset = c + run->range.start();
+      while (offset >= *(last_break + 1)) {

[Alexei Svitkine (slow), 2013/07/09 15:35:13]

Can you you use ui/gfx/break_list.h or are the semantics different here? (And if
they are, do they have to be?)

[ckocagil, 2013/07/13 16:05:10]

I can use a break list but then every time I use GetBreak it will do a search,
right? It should be faster to use a vector and iterator/pointer, but of course I
can change it to a break list for clarity if you want.

+        ++last_break;
+        break_x = 0;
+      }
+
+      ui::Range glyphs = CharRangeToGlyphRange(ui::Range(c, c + 1), run);
+      int start = glyphs.start();
+      int end = glyphs.end();
+
+      int char_width = 0;
+      for (int g = start; g < end; ++g)
+        char_width += run->advance_widths[g];
+
+      line_x += char_width;
+      text_x += char_width;
+      break_x += char_width;
+
+      if (line_x > max_width) {
+        if (*last_break > line_beginning) {
+          // Roll back to last break.
+          text_x -= break_x;
+          c = *last_break - run->range.start() - 1;
+          offset = *last_break;
+        } else if (line_x != char_width) {
+          // Roll back one character.
+          text_x -= char_width;
+          --c;
+        } // else: Assume the current character fits; continue from next line.
+        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().push_back(segment);
+        lines.push_back(ScopedVector<internal::LineSegment>());
+
+        segment_start_pos = text_x;
+        segment_start_char = offset;
+        continue;
+      }
+    }
+    if (segment_start_char != run->range.end()) {
+      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().push_back(segment);
+      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);
+  set_lines_valid(true);
+}
 
 void RenderTextWin::DrawVisualText(Canvas* canvas) {
   DCHECK(!needs_layout_);
 
-  // Skia will draw glyphs with respect to the baseline.
-  Vector2d offset(GetTextOffset() + Vector2d(0, common_baseline_));
-
-  SkScalar x = SkIntToScalar(offset.x());
-  SkScalar y = SkIntToScalar(offset.y());
+  if (multiline())
+    ComputeLines();

[msw, 2013/07/10 04:01:56]

I think ComputeLines should be done as a step in EnsureLayout.

[ckocagil, 2013/07/13 16:05:10]

Done.

 
   std::vector<SkPoint> pos;
 
@@ -454,30 +608,77 @@ 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;
-
-    // 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]);
+  SkScalar glyph_x = SkIntToScalar(0);
+  SkScalar glyph_y = SkIntToScalar(0);
+
+  if (!multiline()) {
+    // Skia will draw glyphs with respect to the baseline.
+    Vector2d offset(0, common_baseline_);
+    offset += GetTextOffset(GetContentWidth());
+
+    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;
+
+      // Based on WebCore::skiaDrawText.
+      pos.resize(run->glyph_count);
+      SkScalar run_x = glyph_x;
+      for (int glyph = 0; glyph < run->glyph_count; glyph++) {
+        pos[glyph].set(offset.x() + glyph_x + run->offsets[glyph].du,
+                       offset.y() + run->offsets[glyph].dv);
+        glyph_x += SkIntToScalar(run->advance_widths[glyph]);
+      }
+
+      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(run_x, offset.y(), run->width, run->underline,
+                               run->strike, run->diagonal_strike);
     }
+    return;
+  }
 
-    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;
+  for (size_t line = 0; line < lines().size(); ++line) {

[Alexei Svitkine (slow), 2013/07/09 15:35:13]

Ideally, I'd like to see a single codepath that handles both the multline and
single line scenarios (i.e. the singleline scenario will just be the multiline
scenario with a single line), but I'm okay with keeping them separate at this
stage (as this is still being developed).

Can you add a TODO to unify them in the future?

(Also, with that TODO in place, I won't ask you to try to refactor things to
make the two loops share common code since the eventual goal would be them being
unified).

[ckocagil, 2013/07/13 16:05:10]

Done, added TODO.

+    Vector2d offset(0, common_baseline_);
+    offset += GetTextOffset(LineWidth(line));
+    for (size_t i = 0; i < lines()[line].size(); ++i) {
+      const internal::LineSegmentWin* segment =
+          static_cast<const internal::LineSegmentWin*>(lines()[line][i]);
+      if (segment->char_pos.is_empty())
+        continue; // TODO: maybe prevent this from happening in the first place?
+      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(),
+                run->range.start() + run->glyph_count);
+      int start_char = segment->char_pos.start() - run->range.start();
+      int end_char = start_char + segment->char_pos.length();
+      ui::Range glyphs = CharRangeToGlyphRange(ui::Range(start_char, end_char),
+                                               run);
+      int start = glyphs.start();
+      int end = glyphs.end();
+      DCHECK_LE(start, end);
+      pos.resize(end - start);
+      for (int g = start; g < end; ++g) {
+        pos[g - start].set(glyph_x + offset.x() + run->offsets[g].du,
+                           glyph_y + 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(),
+                               glyph_y + offset.y(), segment->x_pos.length(),
+                               run->underline, run->strike,
+                               run->diagonal_strike);
+    }
+    glyph_x = SkIntToScalar(0);
+    glyph_y += SkIntToScalar(string_size_.height());
   }
 }