Add multiline support to RenderTextHarfBuzz.

ui/gfx/render_text_harfbuzz.cc

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "ui/gfx/render_text_harfbuzz.h"
 
 #include <limits>
 #include <map>
 
 #include "base/i18n/bidi_line_iterator.h"
 #include "base/i18n/break_iterator.h"
 #include "base/i18n/char_iterator.h"
 #include "base/lazy_instance.h"
 #include "base/profiler/scoped_tracker.h"
 #include "third_party/harfbuzz-ng/src/hb.h"
 #include "third_party/icu/source/common/unicode/ubidi.h"
 #include "third_party/skia/include/core/SkColor.h"
 #include "third_party/skia/include/core/SkTypeface.h"
 #include "ui/gfx/canvas.h"
 #include "ui/gfx/font_fallback.h"
 #include "ui/gfx/font_render_params.h"
+#include "ui/gfx/geometry/size_conversions.h"
 #include "ui/gfx/utf16_indexing.h"
 
 #if defined(OS_WIN)
 #include "ui/gfx/font_fallback_win.h"
 #endif
 
 using gfx::internal::RangeF;
 using gfx::internal::RoundRangeF;
 
 namespace gfx {
@@ skipping 425 matching lines @@
       reversed ? elements_end - element : element - elements_begin);
   if (reversed)
     *glyphs = Range(glyphs->end(), glyphs->start());
 
   DCHECK(!chars->is_reversed());
   DCHECK(!chars->is_empty());
   DCHECK(!glyphs->is_reversed());
   DCHECK(!glyphs->is_empty());
 }
 
+// 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. |min_baseline| and |min_height| are the minimum baseline and
+// height for each line.
+// TODO(ckocagil): Expose the interface of this class in the header and test
+//                 this class directly.
+class HarfBuzzLineBreaker {
+ public:
+  HarfBuzzLineBreaker(int max_width,
+                      int min_baseline,
+                      int min_height,
+                      bool multiline,
+                      const base::string16& text,
+                      const BreakList<size_t>* words,
+                      const ScopedVector<internal::TextRunHarfBuzz>& runs)
+      : max_width_((max_width == 0) ? kuint32max : max_width),

[msw, 2015/02/04 01:44:18]

This constant is deprecated; use std::numeric_limits<int>::max() instead.

[Jun Mukai, 2015/02/04 23:35:54]

Done.

+        min_baseline_(min_baseline),
+        min_height_(min_height),
+        multiline_(multiline),
+        text_(text),
+        words_(words),
+        runs_(runs),
+        text_x_(0),
+        line_x_(0) {
+    DCHECK_EQ(multiline_, (words_ != nullptr));
+    AdvanceLine();
+  }
+
+  // Breaks the run at given |run_index| into Line structs.
+  void AddRun(int run_index) {
+    const internal::TextRunHarfBuzz* run = runs_[run_index];
+    bool run_fits = !multiline_;
+    if (multiline_ && line_x_ + run->width <= max_width_) {
+      DCHECK(!run->range.is_empty());
+      // Uniscribe always puts newline characters in their own runs.

[msw, 2015/02/04 01:44:18]

This behavior should be re-checked with ICU/HarfBuzz itemization, and this code
or comment should be updated.

[Jun Mukai, 2015/02/04 23:35:54]

Modified itemizing runs a bit so that runs are split at newline character, then
the line breaker code (and this comment) is gone.

+      if (!IsNewline(text_[run->range.start()]))
+        run_fits = true;
+    }
+
+    if (!run_fits)
+      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<internal::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;
+
+  bool IsNewline(base::char16 c) {
+    return U16_IS_SINGLE(c) && c == static_cast<base::char16>('\n');
+  }
+
+  internal::LineSegment* SegmentFromHandle(const SegmentHandle& handle) {
+    return &lines_[handle.first].segments[handle.second];
+  }
+
+  // Breaks a run into segments that fit in the last line in |lines_| and adds
+  // them. Adds a new Line to the back of |lines_| whenever a new segment can't
+  // be added without the Line's width exceeding |max_width_|.
+  void BreakRun(int run_index) {
+    DCHECK(words_);
+    const internal::TextRunHarfBuzz& 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 size_t current_char = next_char;
+      const bool skip_line =
+          BreakRunAtWidth(run, current_char, &width, &next_char);
+      AddSegment(run_index, Range(current_char, next_char), width);
+      if (skip_line)
+        AdvanceLine();
+    }
+  }
+
+  // Starting from |start_char|, finds a suitable line break position at or
+  // before available width using word break info from |breaks|. If the current
+  // position is at the beginning of a line, this function will not roll back to
+  // |start_char| and |*next_char| will be greater than |start_char| (to avoid
+  // constructing empty lines).
+  // Returns whether to skip the line before |*next_char|.
+  // TODO(ckocagil): Do not break ligatures and diacritics.
+  //                 TextRun::logical_clusters might help.

[msw, 2015/02/04 01:44:18]

nit: TextRun::logical_clusters was RenderTextWin specific, this can probably be
re-written generically as "// TODO(ckocagil): Check clusters to avoid breaking
ligatures and diacritics."

[Jun Mukai, 2015/02/04 23:35:54]

Done.

+  // 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 width for whitespace at the end of lines.
+  bool BreakRunAtWidth(const internal::TextRunHarfBuzz& run,
+                       size_t start_char,
+                       int* width,
+                       size_t* next_char) {
+    DCHECK(words_);
+    DCHECK(run.range.Contains(Range(start_char, start_char + 1)));
+    SkScalar available_width = SkIntToScalar(max_width_ - line_x_);
+    BreakList<size_t>::const_iterator word = words_->GetBreak(start_char);
+    BreakList<size_t>::const_iterator next_word = word + 1;
+    // Width from |std::max(word->first, start_char)| to the current character.
+    SkScalar word_width = 0;
+    SkScalar width_scalar = 0;

[msw, 2015/02/04 01:44:18]

Could |width| simply be an SkScalar?

[Jun Mukai, 2015/02/04 23:35:54]

Done.

+    *width = 0;
+
+    for (size_t i = start_char; i < run.range.end(); ++i) {
+      if (IsNewline(text_[i])) {
+        *next_char = i + 1;
+        return true;
+      }
+
+      // |word| holds the word boundary at or before |i|, and |next_word| holds
+      // the word boundary right after |i|. Advance both |word| and |next_word|
+      // when |i| reaches |next_word|.
+      if (next_word != words_->breaks().end() && i >= next_word->first) {
+        word = next_word++;
+        word_width = 0;
+      }
+
+      Range glyph_range = run.CharRangeToGlyphRange(Range(i, i + 1));
+      SkScalar char_width = ((glyph_range.end() >= run.glyph_count)
+                                 ? SkFloatToScalar(run.width)
+                                 : run.positions[glyph_range.end()].x()) -
+                            run.positions[glyph_range.start()].x();
+
+      width_scalar += char_width;
+      word_width += char_width;
+
+      if (width_scalar > available_width) {
+        if (line_x_ != 0 || word_width < width_scalar) {
+          // Roll back one word.
+          *width = SkScalarCeilToInt(width_scalar - word_width);
+          *next_char = std::max(word->first, start_char);
+        } else if (char_width < width_scalar) {
+          // Roll back one character.
+          *width = SkScalarCeilToInt(width_scalar - char_width);
+          *next_char = i;
+        } else {
+          // Continue from the next character.
+          *width = SkScalarCeilToInt(width_scalar);
+          *next_char = i + 1;
+        }
+
+        return true;
+      }
+    }
+
+    *width = SkScalarCeilToInt(width_scalar);
+    *next_char = run.range.end();
+    return false;
+  }
+
+  // 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 UpdateRTLSegmentRanges() {
+    if (rtl_segments_.empty())
+      return;
+    int x = SegmentFromHandle(rtl_segments_[0])->x_range.start();
+    for (size_t i = rtl_segments_.size(); i > 0; --i) {
+      internal::LineSegment* segment = SegmentFromHandle(rtl_segments_[i - 1]);
+      const size_t segment_width = segment->x_range.length();
+      segment->x_range = Range(x, x + segment_width);
+      x += segment_width;
+    }
+    rtl_segments_.clear();
+  }
+
+  // Finishes the size calculations of the last Line in |lines_|. Adds a new
+  // Line to the back of |lines_|.
+  void AdvanceLine() {
+    if (!lines_.empty()) {
+      internal::Line* line = &lines_.back();
+      line->preceding_heights = total_size_.height();
+      const Size line_size(ToCeiledSize(line->size));
+      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;
+    lines_.push_back(internal::Line());
+    lines_.back().baseline = min_baseline_;
+    lines_.back().size.set_height(min_height_);
+  }
+
+  // Adds a new segment with the given properties to |lines_.back()|.
+  void AddSegment(int run_index, Range char_range, int width) {
+    if (char_range.is_empty()) {
+      DCHECK_EQ(width, 0);
+      return;
+    }
+    const internal::TextRunHarfBuzz& run = *runs_[run_index];
+
+    internal::LineSegment segment;
+    segment.run = run_index;
+    segment.char_range = char_range;
+    segment.x_range = Range(text_x_, text_x_ + width);
+
+    internal::Line* line = &lines_.back();
+    line->segments.push_back(segment);
+
+    SkPaint paint;
+    paint.setTypeface(run.skia_face.get());
+    paint.setTextSize(SkIntToScalar(run.font_size));
+    paint.setAntiAlias(run.render_params.antialiasing);
+    SkPaint::FontMetrics metrics;
+    paint.getFontMetrics(&metrics);
+
+    line->size.set_width(line->size.width() + segment.x_range.length());
+    line->size.set_height(
+        std::max(line->size.height(), metrics.fDescent - metrics.fAscent));

[msw, 2015/02/04 01:44:18]

I think you'll need to retain the logic for tracking the maximum descents and
ascents across segments. That will do the proper height calculation and allow
baseline-centering of text across segments; simply taking the maximum height of
the segments in a line isn't sufficient.

[Jun Mukai, 2015/02/04 23:35:54]

Done.

+    line->baseline =
+        std::max(line->baseline, SkScalarRoundToInt(-metrics.fAscent));
+
+    if (run.is_rtl) {
+      rtl_segments_.push_back(
+          SegmentHandle(lines_.size() - 1, line->segments.size() - 1));
+      // If this is the last segment of an RTL run, reprocess the text-space x
+      // ranges of all segments from the run.
+      if (char_range.end() == run.range.end())
+        UpdateRTLSegmentRanges();
+    }
+    text_x_ += width;
+    line_x_ += width;
+  }
+
+  const size_t max_width_;
+  const int min_baseline_;
+  const int min_height_;
+  const bool multiline_;
+  const base::string16& text_;
+  const BreakList<size_t>* const words_;
+  const ScopedVector<internal::TextRunHarfBuzz>& runs_;
+
+  // Stores the resulting lines.
+  std::vector<internal::Line> lines_;
+
+  // Text space and line space x coordinates of the next segment to be added.
+  int text_x_;
+  int line_x_;
+
+  // Size of the multiline text, not including the currently processed line.
+  Size total_size_;
+
+  // The current RTL run segments, to be applied by |UpdateRTLSegmentRanges()|.
+  std::vector<SegmentHandle> rtl_segments_;
+
+  DISALLOW_COPY_AND_ASSIGN(HarfBuzzLineBreaker);
+};
+
 }  // namespace
 
 namespace internal {
 
 Range RoundRangeF(const RangeF& range_f) {
   return Range(std::floor(range_f.first + 0.5f),
                std::floor(range_f.second + 0.5f));
 }
 
 TextRunHarfBuzz::TextRunHarfBuzz()
@@ skipping 113 matching lines @@
   set_truncate_length(kMaxTextLength);
 }
 
 RenderTextHarfBuzz::~RenderTextHarfBuzz() {}
 
 scoped_ptr<RenderText> RenderTextHarfBuzz::CreateInstanceOfSameType() const {
   return scoped_ptr<RenderTextHarfBuzz>(new RenderTextHarfBuzz);
 }
 
 Size RenderTextHarfBuzz::GetStringSize() {
-  const SizeF size_f = GetStringSizeF();
-  return Size(std::ceil(size_f.width()), size_f.height());
+  return gfx::ToCeiledSize(GetStringSizeF());
 }
 
 SizeF RenderTextHarfBuzz::GetStringSizeF() {
   EnsureLayout();
-  return lines()[0].size;
+  return total_size_;
 }
 
 SelectionModel RenderTextHarfBuzz::FindCursorPosition(const Point& point) {
   EnsureLayout();
 
   int x = ToTextPoint(point).x();
   float offset = 0;
   size_t run_index = GetRunContainingXCoord(x, &offset);
   if (run_index >= runs_.size())
     return EdgeSelectionModel((x < 0) ? CURSOR_LEFT : CURSOR_RIGHT);
@@ skipping 303 matching lines @@
     std::vector<internal::Line> empty_lines;
     set_lines(&empty_lines);
   }
 
   if (lines().empty()) {
     // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is fixed.
     tracked_objects::ScopedTracker tracking_profile2(
         FROM_HERE_WITH_EXPLICIT_FUNCTION(
             "431326 RenderTextHarfBuzz::EnsureLayout2"));
 
-    std::vector<internal::Line> lines;
-    lines.push_back(internal::Line());
-    lines[0].baseline = font_list().GetBaseline();
-    lines[0].size.set_height(font_list().GetHeight());
-
-    int current_x = 0;
-    SkPaint paint;
-
     // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is fixed.

[msw, 2015/02/04 01:44:18]

nit: You might be able to collapse EnsureLayout2 and EnsureLayout3.

[Jun Mukai, 2015/02/04 23:35:54]

To keep the consistency with the previous code, I've moved line_breaker
construction between 2 and 3.

     tracked_objects::ScopedTracker tracking_profile3(
         FROM_HERE_WITH_EXPLICIT_FUNCTION(
             "431326 RenderTextHarfBuzz::EnsureLayout3"));
 
-    for (size_t i = 0; i < runs_.size(); ++i) {
-      const internal::TextRunHarfBuzz& run = *runs_[visual_to_logical_[i]];
-      internal::LineSegment segment;
-      segment.x_range = Range(current_x, current_x + run.width);
-      segment.char_range = run.range;
-      segment.run = i;
-      lines[0].segments.push_back(segment);
-
-      paint.setTypeface(run.skia_face.get());
-      paint.setTextSize(SkIntToScalar(run.font_size));
-      paint.setAntiAlias(run.render_params.antialiasing);
-      SkPaint::FontMetrics metrics;
-      paint.getFontMetrics(&metrics);
-
-      lines[0].size.set_width(lines[0].size.width() + run.width);
-      lines[0].size.set_height(std::max(lines[0].size.height(),
-                                        metrics.fDescent - metrics.fAscent));
-      lines[0].baseline = std::max(lines[0].baseline,
-                                   SkScalarRoundToInt(-metrics.fAscent));
-    }
-
+    HarfBuzzLineBreaker line_breaker(
+        display_rect().width(), font_list().GetBaseline(),
+        font_list().GetHeight(), multiline(), GetLayoutText(),
+        multiline() ? &GetLineBreaks() : nullptr, runs_);
+    for (size_t i = 0; i < runs_.size(); ++i)
+      line_breaker.AddRun(visual_to_logical_[i]);
+    std::vector<internal::Line> lines;
+    line_breaker.Finalize(&lines, &total_size_);
     set_lines(&lines);
   }
 }
 
 void RenderTextHarfBuzz::DrawVisualText(Canvas* canvas) {
   DCHECK(!needs_layout_);
+  if (lines().empty())
+    return;
+
   internal::SkiaTextRenderer renderer(canvas);
   ApplyFadeEffects(&renderer);
   ApplyTextShadows(&renderer);
   ApplyCompositionAndSelectionStyles();
 
-  const Vector2d line_offset = GetLineOffset(0);
-  for (size_t i = 0; i < runs_.size(); ++i) {
-    const internal::TextRunHarfBuzz& run = *runs_[visual_to_logical_[i]];
-    renderer.SetTypeface(run.skia_face.get());
-    renderer.SetTextSize(SkIntToScalar(run.font_size));
-    renderer.SetFontRenderParams(run.render_params,
-                                 background_is_transparent());
+  Vector2d origin = GetLineOffset(0) + Vector2d(0, lines()[0].baseline);

[msw, 2015/02/04 01:44:18]

nit: you might be able to actually use GetLineOffset(<line_number>) now.
(otherwise, maybe it's not worth keeping that functionality)

[Jun Mukai, 2015/02/04 23:35:54]

Done.

+  for (const internal::Line& line : lines()) {
+    SkScalar preceding_run_widths = 0;

[msw, 2015/02/04 01:44:18]

nit: rename this |preceding_segment_widths|

[Jun Mukai, 2015/02/04 23:35:54]

Done.

+    for (const internal::LineSegment& segment : line.segments) {
+      const internal::TextRunHarfBuzz& run = *runs_[segment.run];
+      renderer.SetTypeface(run.skia_face.get());
+      renderer.SetTextSize(SkIntToScalar(run.font_size));
+      renderer.SetFontRenderParams(run.render_params,
+                                   background_is_transparent());
+      scoped_ptr<SkPoint[]> positions(new SkPoint[segment.char_range.length()]);

[msw, 2015/02/04 01:44:18]

The length of |positions| should correspond to the number of glyphs, not the
number of characters (it was previously |run.glyph_count|). I don't think
|segment.char_range.length()| is correct, it should be the number of glyphs
corresponding to that char range; try CharRangeToGlyphRange.

[Jun Mukai, 2015/02/04 23:35:54]

Done.

+      size_t segment_start = segment.char_range.start() - run.range.start();
+      SkScalar segment_base_x = run.positions[segment_start].x();
+      for (size_t j = 0; j < segment.char_range.length(); ++j) {
+        positions[j] = run.positions[segment_start + j];

[msw, 2015/02/04 01:44:18]

Yeah, TextRunHarfBuzz::positions is sized to the number of glyphs in the run,
char-based indices may exceed the array length, besides being incorrect.

[Jun Mukai, 2015/02/04 23:35:54]

Done.

+        positions[j].offset(
+            SkIntToScalar(origin.x()) - segment_base_x + preceding_run_widths,
+            SkIntToScalar(origin.y()));
+      }
+      for (BreakList<SkColor>::const_iterator it =
+               colors().GetBreak(segment.char_range.start());
+           it != colors().breaks().end() &&
+               it->first < segment.char_range.end();
+           ++it) {
+        const Range intersection =
+            colors().GetRange(it).Intersect(segment.char_range);
+        const Range colored_glyphs = run.CharRangeToGlyphRange(intersection);
+        // The range may be empty if a portion of a multi-character grapheme is
+        // selected, yielding two colors for a single glyph. For now, this just
+        // paints the glyph with a single style, but it should paint it twice,
+        // clipped according to selection bounds. See http://crbug.com/366786
+        if (colored_glyphs.is_empty())
+          continue;
 
-    Vector2d origin = line_offset + Vector2d(0, lines()[0].baseline);
-    scoped_ptr<SkPoint[]> positions(new SkPoint[run.glyph_count]);
-    for (size_t j = 0; j < run.glyph_count; ++j) {
-      positions[j] = run.positions[j];
-      positions[j].offset(SkIntToScalar(origin.x()) + run.preceding_run_widths,
-                          SkIntToScalar(origin.y()));
+        renderer.SetForegroundColor(it->second);
+        renderer.DrawPosText(&positions[colored_glyphs.start() - segment_start],

[msw, 2015/02/04 01:44:18]

The |segment_start| here should also be in glyph index space.

[Jun Mukai, 2015/02/04 23:35:54]

Done.

+                             &run.glyphs[colored_glyphs.start()],
+                             colored_glyphs.length());
+        int start_x = SkScalarRoundToInt(positions[colored_glyphs.start()].x());

[msw, 2015/02/04 01:44:18]

Should this use the positions[colored_glyphs.start() - segment_start], similar
to above and the old RenderTextWin behavior?

[Jun Mukai, 2015/02/04 23:35:54]

Done.

+        int end_x = SkScalarRoundToInt(
+            (colored_glyphs.end() == run.glyph_count)
+                ? (segment.x_range.length() + preceding_run_widths +
+                   SkIntToScalar(origin.x()))
+                : positions[colored_glyphs.end()].x());

[msw, 2015/02/04 01:44:18]

Should this use the positions[colored_glyphs.end() - segment_start], similar to
above and the old RenderTextWin behavior?

[Jun Mukai, 2015/02/04 23:35:54]

Done.

+        renderer.DrawDecorations(start_x, origin.y(), end_x - start_x,
+                                 run.underline, run.strike,
+                                 run.diagonal_strike);
+      }
+      preceding_run_widths += SkIntToScalar(segment.x_range.length());
     }
-
-    for (BreakList<SkColor>::const_iterator it =
-             colors().GetBreak(run.range.start());
-         it != colors().breaks().end() && it->first < run.range.end();
-         ++it) {
-      const Range intersection = colors().GetRange(it).Intersect(run.range);
-      const Range colored_glyphs = run.CharRangeToGlyphRange(intersection);
-      // The range may be empty if a portion of a multi-character grapheme is
-      // selected, yielding two colors for a single glyph. For now, this just
-      // paints the glyph with a single style, but it should paint it twice,
-      // clipped according to selection bounds. See http://crbug.com/366786
-      if (colored_glyphs.is_empty())
-        continue;
-
-      renderer.SetForegroundColor(it->second);
-      renderer.DrawPosText(&positions[colored_glyphs.start()],
-                           &run.glyphs[colored_glyphs.start()],
-                           colored_glyphs.length());
-      int start_x = SkScalarRoundToInt(positions[colored_glyphs.start()].x());
-      int end_x = SkScalarRoundToInt((colored_glyphs.end() == run.glyph_count) ?
-          (run.width + run.preceding_run_widths + SkIntToScalar(origin.x())) :
-          positions[colored_glyphs.end()].x());
-      renderer.DrawDecorations(start_x, origin.y(), end_x - start_x,
-                               run.underline, run.strike, run.diagonal_strike);
-    }
+    origin += Vector2d(0, line.size.height());
   }
 
   renderer.EndDiagonalStrike();
 
   UndoCompositionAndSelectionStyles();
 }
 
 size_t RenderTextHarfBuzz::GetRunContainingCaret(
     const SelectionModel& caret) const {
   DCHECK(!needs_layout_);
@@ skipping 308 matching lines @@
     if (!run->render_params.subpixel_positioning)
       run->width = std::floor(run->width + 0.5f);
   }
 
   hb_buffer_destroy(buffer);
   hb_font_destroy(harfbuzz_font);
   return true;
 }
 
 }  // namespace gfx