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 ac018de3f446226f8e39276ee65f24ebf1e76478..38f3ac9fb0757d8289263a177337bca6339d3695 100644
--- a/ui/gfx/render_text_win.cc
+++ b/ui/gfx/render_text_win.cc
@@ -154,6 +154,61 @@ ui::Range CharRangeToGlyphRange(const internal::TextRun& run,
   return result;
 }
 
+// Starting from |start_char|, finds a suitable line break position at or before
+// |available_width| using word break info from |breaks|. If |empty_line| is
+// true, this function will not roll back to |start_char| and |*pos| will be
+// greater than |start_char|.
+// TODO(ckocagil): Do not break ligatures and diacritics.
+//                 TextRun::logical_clusters might help.
+// TODO(ckocagil): We might have to reshape after breaking at ligatures.
+//                 See whether resolving the TODO above resolves this too.
+// TODO(ckocagil): Do not reserve space for whitespace at the end of lines.
+void BreakRunAtWidth(const internal::TextRun& run,
+                     const BreakList<size_t>& breaks,
+                     size_t start_char,
+                     int available_width,
+                     bool empty_line,
+                     int* width,
+                     size_t* pos) {

[Alexei Svitkine (slow), 2013/08/26 21:34:41]

Nit: Rename |pos| to |next_char|, or better yet |next_char_index| and change
|start_char| to |start_char_index|.

[ckocagil, 2013/08/28 18:01:45]

Done. I made it |next_char| instead of |next_char_index|. The latter looks a bit
too verbose to me. Not sure though, I can change it if you (or Mike) think the
latter looks better.

[msw, 2013/08/30 00:42:28]

|end_char| corresponds w/|start_char| better, but |next_char| is ok.

+  DCHECK(run.range.Contains(ui::Range(start_char, start_char + 1)));
+  BreakList<size_t>::const_iterator word = breaks.GetBreak(start_char);
+  BreakList<size_t>::const_iterator next_word = word + 1;
+  // Width from |std::max(word->first, start_char)|.
+  int word_width = 0;
+  *width = 0;
+
+  for (size_t i = start_char; i < run.range.end(); ++i) {
+    if (next_word != breaks.breaks().end() && i >= next_word->first) {

[Alexei Svitkine (slow), 2013/08/27 15:40:38]

Add a comment above this explaining the logic.

[ckocagil, 2013/08/28 19:16:26]

Done.

+      word = next_word++;
+      word_width = 0;
+    }
+
+    ui::Range glyphs = CharRangeToGlyphRange(run, ui::Range(i, i + 1));

[Alexei Svitkine (slow), 2013/08/27 15:40:38]

Nit: glyph_range

[ckocagil, 2013/08/28 19:16:26]

Done.

+    int char_width = 0;
+    for (size_t j = glyphs.start(); j < glyphs.end(); ++j)
+      char_width += run.advance_widths[j];
+
+    *width += char_width;
+    word_width += char_width;
+
+    if (*width > available_width) {
+      if (!empty_line || word_width < *width) {
+        *width -= word_width;
+        *pos = std::max(word->first, start_char);
+      } else if (char_width < *width) {
+        *width -= char_width;
+        *pos = i;
+      } else {
+        *pos = i + 1;
+      }
+
+      return;
+    }
+  }
+
+  *pos = run.range.end();
+}
+
 }  // namespace
 
 namespace internal {
@@ -197,6 +252,156 @@ int GetGlyphXBoundary(const internal::TextRun* run,
   return run->preceding_run_widths + x;
 }
 
+// Internal class to generate Line structures. If |multiline| is true, the text
+// is broken into lines at |words| boundaries such that each line is no longer
+// than |max_width|. If |multiline| is false, only outputs a single Line from
+// the given runs.

[Alexei Svitkine (slow), 2013/08/27 15:40:38]

Nit: "the given run." -> "a given run."

[ckocagil, 2013/08/28 19:16:26]

I don't understand. A Line can contain multiple runs.

[Alexei Svitkine (slow), 2013/08/28 21:27:46]

Ah right - my comment was wrong. Disregard.

+class LineBreaker {

[Alexei Svitkine (slow), 2013/08/27 15:40:38]

I think it may be worth exposing the interface of this class in the header file,
so that its logic can be tested directly (rather than just through
RenderTextWin) - which should be possible since this class is in the internal
namespace (i.e. like TextRun).

However, I think at this point we can leave that to a follow-up CL, since this
CL is looking quite good now and is getting ready to land.

However, can you add a TODO about it in the comment above? Thanks!

[ckocagil, 2013/08/28 19:16:26]

Good idea, that should make testing easier and better. Adding a TODO here.

+ public:
+  LineBreaker(int max_width,
+              bool multiline,
+              const BreakList<size_t>* words,
+              const ScopedVector<TextRun>& runs)
+      : max_width_(max_width),
+        multiline_(multiline),
+        words_(words),
+        runs_(runs),
+        text_x_(0),
+        line_x_(0),
+        line_ascent_(0),
+        line_descent_(0) {
+    AdvanceLine();
+  }
+
+  // Breaks the run at given |run_index| into Line structs.
+  void AddRun(int run_index) {
+    TextRun* run = runs_[run_index];

[Alexei Svitkine (slow), 2013/08/27 15:40:38]

Nit: const

[ckocagil, 2013/08/28 19:16:26]

Done.

+    if (multiline_ && line_x_ + run->width > max_width_)
+      BreakRun(run_index);
+    else
+      AddSegment(run_index, run->range, run->width);
+  }
+
+  // Finishes line breaking and outputs the results. Can be called at most once.
+  void Finalize(std::vector<Line>* lines, Size* size) {
+    DCHECK(!lines_.empty());
+    // Add an empty line to finish the line size calculation and remove it.
+    AdvanceLine();
+    lines_.pop_back();
+    *size = total_size_;
+    lines->swap(lines_);
+  }
+
+ private:
+  // A (line index, segment index) pair that specifies a segment in |lines_|.
+  typedef std::pair<size_t, size_t> SegmentHandle;
+
+  LineSegment* SegmentFromHandle(const SegmentHandle& handle) {
+    return &lines_[handle.first].segments[handle.second];
+  }
+
+  // Breaks a run into segments of at most |max_width_| width, adds all segments
+  // to |lines_.back()|.

[msw, 2013/08/27 01:30:52]

nit: This doesn't sound right. BreakRun appends lines as needed too.

[ckocagil, 2013/08/28 18:01:45]

Updated.

+  void BreakRun(int run_index) {
+    DCHECK(words_);
+    TextRun* const run = runs_[run_index];
+    int width = 0;
+    size_t next_char = run->range.start();
+
+    // Break the run until it fits the current line.
+    while (next_char < run->range.end()) {
+      const int current_char = next_char;

[msw, 2013/08/27 01:30:52]

nit: size_t ?

[ckocagil, 2013/08/28 18:01:45]

Done.

+      BreakRunAtWidth(*run, *words_, next_char, max_width_ - line_x_,
+                      line_x_ == 0, &width, &next_char);
+      AddSegment(run_index, ui::Range(current_char, next_char), width);
+      if (next_char < run->range.end())
+        AdvanceLine();
+    }
+  }
+
+  // RTL runs are broken in logical order but displayed in visual order. To find
+  // the text-space coordinate (where it would fall in a single-line text)
+  // |x_range| of RTL segments, segment widths are applied in reverse order.
+  // e.g. {[5, 10], [10, 40]} will become {[35, 40], [5, 35]}.
+  void PopRtl() {

[Alexei Svitkine (slow), 2013/08/27 15:40:38]

I think a more descriptive name would be better here.

How about: UpdateRTLSegmentRanges()

[ckocagil, 2013/08/28 19:16:26]

Done.

+    if (rtl_segments_.empty())
+      return;
+    int x = SegmentFromHandle(rtl_segments_[0])->x_range.start();
+    for (size_t i = rtl_segments_.size(); i > 0; --i) {
+      LineSegment* const segment = SegmentFromHandle(rtl_segments_[i - 1]);

[Alexei Svitkine (slow), 2013/08/27 15:40:38]

Nit: Remove const here, since |segment|'s data is changing and marking the
variable itself as const is not very useful here.

[ckocagil, 2013/08/28 19:16:26]

Done.

+      segment->x_range = ui::Range(x, x + segment->x_range.length());

[Alexei Svitkine (slow), 2013/08/27 15:40:38]

Nit: Extract segment->x_range.length() into a local var |segment_width|, since
you use it below too (and it doesn't change).

[ckocagil, 2013/08/28 19:16:26]

Done.

+      x += segment->x_range.length();
+    }
+    rtl_segments_.clear();
+  }
+
+  void AdvanceLine() {

[Alexei Svitkine (slow), 2013/08/27 15:40:38]

Nit: Add a brief comment.

[ckocagil, 2013/08/28 19:16:26]

Done.

+    if (!lines_.empty()) {
+      Line* line = &lines_.back();
+      line->baseline = line_ascent_;
+      line->size.set_height(line_ascent_ + line_descent_);
+      line->preceding_heights = total_size_.height();
+      total_size_.set_height(total_size_.height() + line->size.height());
+      total_size_.set_width(std::max(total_size_.width(), line->size.width()));
+    }
+    line_x_ = 0;
+    line_ascent_ = 0;
+    line_descent_ = 0;
+    lines_.push_back(Line());
+  }
+
+  void AddSegment(int run_index, ui::Range char_range, int width) {

[Alexei Svitkine (slow), 2013/08/27 15:40:38]

Nit: Add a brief comment.

[ckocagil, 2013/08/28 19:16:26]

Done.

+    if (char_range.is_empty()) {
+      DCHECK_EQ(width, 0);
+      return;
+    }
+    const TextRun* run = runs_[run_index];
+    line_ascent_ = std::max(line_ascent_, run->font.GetBaseline());
+    line_descent_ = std::max(line_descent_,
+                             run->font.GetHeight() - run->font.GetBaseline());
+    LineSegment segment;

[Alexei Svitkine (slow), 2013/08/27 15:40:38]

Nit: Add a blank line above this.

[ckocagil, 2013/08/28 19:16:26]

Done.

+    segment.run = run_index;
+    segment.char_range = char_range;
+    segment.x_range = ui::Range(text_x_, text_x_ + width);
+    Line* line = &lines_.back();

[Alexei Svitkine (slow), 2013/08/27 15:40:38]

Nit: Add a blank line above this.

[ckocagil, 2013/08/28 19:16:26]

Done.

+    line->segments.push_back(segment);
+    line->size.set_width(line->size.width() + segment.x_range.length());
+    if (run->script_analysis.fRTL) {
+      rtl_segments_.push_back(SegmentHandle(lines_.size() - 1,
+                                            line->segments.size() - 1));
+      if (char_range.end() == run->range.end())

[Alexei Svitkine (slow), 2013/08/27 15:40:38]

Add a comment about this (i.e. mention that this reprocesses the run ranges at
the end of the run).

[ckocagil, 2013/08/28 19:16:26]

Done.

+        PopRtl();
+    }
+    text_x_ += width;
+    line_x_ += width;
+  }
+
+  const int max_width_;
+  const bool multiline_;
+  const BreakList<size_t>* const words_;
+  const ScopedVector<TextRun>& runs_;
+
+  // Stores the resulting lines.
+  std::vector<Line> lines_;
+
+  // |text_x_| and |line_x_| are text-space and line-space x coordinates of the
+  // next segment to be added.
+  int text_x_;
+  int line_x_;
+
+  // Size of the multi-line text, not including the currently processed line.
+  Size total_size_;
+
+  // Ascent and descent values of the current line, |lines_.back()|.
+  int line_ascent_;
+  int line_descent_;
+
+  // Segments to be applied by |PopRtl()|.

[Alexei Svitkine (slow), 2013/08/27 15:40:38]

Mention that this contains segments of the current run, if it's RTL.

[ckocagil, 2013/08/28 19:16:26]

Done.

+  std::vector<SegmentHandle> rtl_segments_;
+
+  DISALLOW_COPY_AND_ASSIGN(LineBreaker);
+};
+
 }  // namespace internal
 
 // static
@@ -225,6 +430,13 @@ Size RenderTextWin::GetStringSize() {
   return string_size_;
 }
 
+Size RenderTextWin::GetMultilineTextSize() {
+  if (!multiline())
+    return GetStringSize();
+  EnsureLayout();
+  return multiline_string_size_;
+}
+
 int RenderTextWin::GetBaseline() {
   EnsureLayout();
   return common_baseline_;
@@ -383,11 +595,12 @@ 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<Rect> rects;
   if (layout_range.is_empty())
-    return bounds;
+    return rects;
+  std::vector<ui::Range> bounds;
 
-  // Add a Rect for each run/selection intersection.
+  // Add a Range for each run/selection intersection.
   // TODO(msw): The bounds should probably not always be leading the range ends.
   for (size_t i = 0; i < runs_.size(); ++i) {
     const internal::TextRun* run = runs_[visual_to_logical_[i]];
@@ -396,17 +609,23 @@ 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());
+      if (range_x.is_empty())
+        continue;
+      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 = TextBoundsToViewBounds(bounds[i]);
+    rects.insert(rects.end(), current_rects.begin(), current_rects.end());
+  }
+  return rects;
 }
 
 size_t RenderTextWin::TextIndexToLayoutIndex(size_t index) const {
@@ -448,23 +667,34 @@ 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;
+    std::vector<internal::Line> lines;
+    set_lines(&lines);
+  }
+  // Compute lines if they're not valid. This is separate from the layout steps

[Alexei Svitkine (slow), 2013/08/26 21:34:41]

Nit: Add a blank line above this.

[ckocagil, 2013/08/28 18:01:45]

Done.

+  // above to avoid text layout and shaping when we resize |display_rect_|.
+  if (lines().empty()) {
+    DCHECK(!needs_layout_);
+    std::vector<internal::Line> lines;
+    internal::LineBreaker line_breaker(display_rect().width() - 1, multiline(),
+                                       multiline() ? &GetLineBreaks() : NULL,
+                                       runs_);
+    for (size_t i = 0; i < runs_.size(); ++i)
+      line_breaker.AddRun(visual_to_logical_[i]);
+    line_breaker.Finalize(&lines, &multiline_string_size_);
+    DCHECK(!lines.empty());
+    set_lines(&lines);
+  }
 }
 
 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());
+  DCHECK(!multiline() || !lines().empty());
 
   std::vector<SkPoint> pos;
 
@@ -479,54 +709,83 @@ void RenderTextWin::DrawVisualText(Canvas* canvas) {
   renderer.SetFontSmoothingSettings(
       smoothing_enabled, cleartype_enabled && !background_is_transparent());
 
-  ApplyCompositionAndSelectionStyles();
-
-  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]];
-
-    // Skip painting empty runs and runs outside the display rect area.
-    if ((run->glyph_count == 0) || (x >= display_rect().right()) ||
-        (x + run->width <= display_rect().x())) {
-      x += run->width;
+  ApplyCompositionAndSelectionStyles();
+
+  for (size_t i = 0; i < lines().size(); ++i) {
+    const internal::Line& line = lines()[i];
+    Vector2d line_offset = GetLineOffset(i);
+    Vector2d text_offset = line_offset + Vector2d(0, line.baseline);
+    int preceding_segment_widths = 0;
+
+    // Skip painting empty lines or lines outside the display rect area.
+    if (!display_rect().Intersects(Rect(PointAtOffsetFromOrigin(line_offset),
+                                        line.size)))
       continue;
-    }
+
+    for (size_t j = 0; j < line.segments.size(); ++j) {
+      const internal::LineSegment* segment = &line.segments[j];
+      const int segment_width = segment->x_range.length();
+      const internal::TextRun* run = runs_[segment->run];
+      DCHECK(!segment->char_range.is_empty());
+      DCHECK(run->range.Contains(segment->char_range));
+      ui::Range glyphs = CharRangeToGlyphRange(*run, segment->char_range);

[Alexei Svitkine (slow), 2013/08/26 21:34:41]

Nit: |glyph_range|

[ckocagil, 2013/08/28 18:01:45]

Done.

+      if (glyphs.is_empty()) {
+        DCHECK(segment_width == 0);

[Alexei Svitkine (slow), 2013/08/26 21:34:41]

DCHECK_EQ

[ckocagil, 2013/08/28 18:01:45]

Done.

+        continue;
+      }
+      // Skip painting segments outside the display rect area.
+      if (!multiline()) {
+        const Rect segment_bounds(PointAtOffsetFromOrigin(line_offset) +
+                                      Vector2d(preceding_segment_widths, 0),
+                                  Size(segment_width, line.size.height()));
+        if (!display_rect().Intersects(segment_bounds)) {
+          preceding_segment_widths += segment_width;
+          continue;
+        }
+      }
 
-    // Based on WebCore::skiaDrawText. |pos| contains the positions of glyphs.
-    // An extra terminal |pos| entry is added to simplify width calculations.
-    pos.resize(run->glyph_count + 1);
-    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]);
-    }
-    pos.back().set(glyph_x, y);
-
-    renderer.SetTextSize(run->font.GetFontSize());
-    renderer.SetFontFamilyWithStyle(run->font.GetFontName(), run->font_style);
-
-    for (BreakList<SkColor>::const_iterator it =
-             colors().GetBreak(run->range.start());
-         it != colors().breaks().end() && it->first < run->range.end();
-         ++it) {
-      const ui::Range glyph_range = CharRangeToGlyphRange(*run,
-          colors().GetRange(it).Intersect(run->range));
-      if (glyph_range.is_empty())
-        continue;
-      renderer.SetForegroundColor(it->second);
-      renderer.DrawPosText(&pos[glyph_range.start()],
-                           &run->glyphs[glyph_range.start()],
-                           glyph_range.length());
-      const SkScalar width = pos[glyph_range.end()].x() -
-          pos[glyph_range.start()].x();
-      renderer.DrawDecorations(pos[glyph_range.start()].x(), y,
-                               SkScalarCeilToInt(width), run->underline,
-                               run->strike, run->diagonal_strike);
-    }
+      // |pos| contains the positions of glyphs. An extra terminal |pos| entry
+      // is added to simplify width calculations.
+      int segment_x = preceding_segment_widths;
+      pos.resize(glyphs.length() + 1);
+      for (size_t g = glyphs.start(); g < glyphs.end(); ++g) {

[Alexei Svitkine (slow), 2013/08/26 21:34:41]

Either use a descriptive name (like glyph or glyph_index), or use k (following
i, j, k).

[ckocagil, 2013/08/28 18:01:45]

Done, I went with "k".

+        pos[g - glyphs.start()].set(
+            SkIntToScalar(text_offset.x() + segment_x + run->offsets[g].du),
+            SkIntToScalar(text_offset.y() + run->offsets[g].dv));
+        segment_x += run->advance_widths[g];
+      }
+      pos.back().set(
+          SkIntToScalar(text_offset.x() + segment_x),
+          SkIntToScalar(text_offset.y()));
+
+      renderer.SetTextSize(run->font.GetFontSize());
+      renderer.SetFontFamilyWithStyle(run->font.GetFontName(), run->font_style);
+
+      for (BreakList<SkColor>::const_iterator it =
+               colors().GetBreak(run->range.start());
+           it != colors().breaks().end() && it->first < run->range.end();
+           ++it) {
+        const ui::Range intersection =
+            colors().GetRange(it).Intersect(segment->char_range);
+        const ui::Range colored_glyphs =
+            CharRangeToGlyphRange(*run, intersection);
+        DCHECK(glyphs.Contains(colored_glyphs));
+        if (colored_glyphs.is_empty())
+          continue;
+        renderer.SetForegroundColor(it->second);
+        renderer.DrawPosText(&pos[colored_glyphs.start() - glyphs.start()],

[Alexei Svitkine (slow), 2013/08/26 21:34:41]

You repeat |colored_glyphs.start() - glyphs.start()| and |colored_glyphs.end() -
glyphs.start()| a few times below. Please extra things into local variable(s) to
avoid the repetition.

For example:

  const SkPoint& start_pos = &pos[colored_glyphs.start() - glyph_range.start()];
  const SkPoint& end_pos = &pos[colored_glyphs.end() - glyph_range.start()];
  renderer.DrawPosText(&start_pos, ...);
  const int width = SkScalarCeilToInt(end_pos.x() - start_pos.x());
  renderer.DrawDecorations(start_pos.x(), text_offset.y(), width, ...);

[Alexei Svitkine (slow), 2013/08/26 21:35:33]

Er, rather:

   const SkPoint& start_pos = pos[colored_glyphs.start() - glyph_range.start()];
   const SkPoint& end_pos = pos[colored_glyphs.end() - glyph_range.start()];
   renderer.DrawPosText(&start_pos, ...);
   const int width = SkScalarCeilToInt(end_pos.x() - start_pos.x());
   renderer.DrawDecorations(start_pos.x(), text_offset.y(), width, ...);

[ckocagil, 2013/08/28 18:01:45]

Done.

+                             &run->glyphs[colored_glyphs.start()],
+                             colored_glyphs.length());
+        const SkScalar width = pos[colored_glyphs.end() - glyphs.start()].x() -
+            pos[colored_glyphs.start() - glyphs.start()].x();
+        renderer.DrawDecorations(
+            pos[colored_glyphs.start() - glyphs.start()].x(), text_offset.y(),
+            SkScalarCeilToInt(width), run->underline, run->strike,
+            run->diagonal_strike);
+      }
 
-    DCHECK_EQ(glyph_x - x, run->width);
-    x = glyph_x;
+      preceding_segment_widths += segment_width;
+    }
   }
 
   UndoCompositionAndSelectionStyles();