Stop combining text runs which are connected by 'COMMON' blocks.

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 <set>
 
 #include "base/i18n/bidi_line_iterator.h"
 #include "base/i18n/break_iterator.h"
 #include "base/i18n/char_iterator.h"
 #include "base/profiler/scoped_tracker.h"
 #include "base/strings/string_util.h"
 #include "base/strings/utf_string_conversions.h"
 #include "base/trace_event/trace_event.h"
 #include "third_party/harfbuzz-ng/src/hb.h"
 #include "third_party/icu/source/common/unicode/ubidi.h"
+#include "third_party/icu/source/common/unicode/utf16.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/safe_integer_conversions.h"
 #include "ui/gfx/harfbuzz_font_skia.h"
 #include "ui/gfx/range/range_f.h"
 #include "ui/gfx/utf16_indexing.h"
 
@@ skipping 13 matching lines @@
 // The maximum number of scripts a Unicode character can belong to. This value
 // is arbitrarily chosen to be a good limit because it is unlikely for a single
 // character to belong to more scripts.
 const size_t kMaxScripts = 5;
 
 // Returns true if characters of |block_code| may trigger font fallback.
 // Dingbats and emoticons can be rendered through the color emoji font file,
 // therefore it needs to be trigerred as fallbacks. See crbug.com/448909
 bool IsUnusualBlockCode(UBlockCode block_code) {
   return block_code == UBLOCK_GEOMETRIC_SHAPES ||
-         block_code == UBLOCK_MISCELLANEOUS_SYMBOLS ||
-         block_code == UBLOCK_DINGBATS ||
-         block_code == UBLOCK_EMOTICONS;
+         block_code == UBLOCK_MISCELLANEOUS_SYMBOLS;
 }
 
 bool IsBracket(UChar32 character) {
   static const char kBrackets[] = { '(', ')', '{', '}', '<', '>', };
   static const char* kBracketsEnd = kBrackets + arraysize(kBrackets);
   return std::find(kBrackets, kBracketsEnd, character) != kBracketsEnd;
 }
 
 // Returns the boundary between a special and a regular character. Special
 // characters are brackets or characters that satisfy |IsUnusualBlockCode|.
@@ skipping 18 matching lines @@
     const bool block_break = current_block != first_block &&
         (first_block_unusual || IsUnusualBlockCode(current_block));
     if (block_break || current_char == '\n' ||
         first_bracket != IsBracket(current_char)) {
       return run_start + iter.array_pos();
     }
   }
   return run_break;
 }
 
-// If the given scripts match, returns the one that isn't USCRIPT_COMMON or
-// USCRIPT_INHERITED, i.e. the more specific one. Otherwise returns
-// USCRIPT_INVALID_CODE.
+// If the given scripts match, returns the one that isn't USCRIPT_INHERITED,
+// i.e. the more specific one. Otherwise returns USCRIPT_INVALID_CODE.
 UScriptCode ScriptIntersect(UScriptCode first, UScriptCode second) {
-  if (first == second ||
-      (second > USCRIPT_INVALID_CODE && second <= USCRIPT_INHERITED)) {
+  if (first == second || second == USCRIPT_INHERITED)
     return first;
-  }
-  if (first > USCRIPT_INVALID_CODE && first <= USCRIPT_INHERITED)
+  if (first == USCRIPT_INHERITED)
     return second;
   return USCRIPT_INVALID_CODE;
 }
 
 // Writes the script and the script extensions of the character with the
 // Unicode |codepoint|. Returns the number of written scripts.
 int GetScriptExtensions(UChar32 codepoint, UScriptCode* scripts) {
   UErrorCode icu_error = U_ZERO_ERROR;
   // ICU documentation incorrectly states that the result of
   // |uscript_getScriptExtensions| will contain the regular script property.
@@ skipping 47 matching lines @@
                    UScriptCode* script) {
   DCHECK_GT(length, 0U);
 
   UScriptCode scripts[kMaxScripts] = { USCRIPT_INVALID_CODE };
 
   base::i18n::UTF16CharIterator char_iterator(text.c_str() + start, length);
   size_t scripts_size = GetScriptExtensions(char_iterator.get(), scripts);
   *script = scripts[0];
 
   while (char_iterator.Advance()) {
+    // Special handling to merge white space into the previous run.
+    if (u_isUWhiteSpace(char_iterator.get()))
+      continue;
     ScriptSetIntersect(char_iterator.get(), scripts, &scripts_size);
     if (scripts_size == 0U)
       return char_iterator.array_pos();
     *script = scripts[0];
   }
 
   return length;
 }
 
 // A port of hb_icu_script_to_script because harfbuzz on CrOS is built without
@@ skipping 25 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());
 }
 
+// Returns true if the code point |c| is a combining mark character in Unicode.
+bool CharIsMark(UChar32 c) {
+  int8_t char_type = u_charType(c);
+  return char_type == U_NON_SPACING_MARK || char_type == U_ENCLOSING_MARK ||
+         char_type == U_COMBINING_SPACING_MARK;
+}
+
+// Gets the code point of |str| at the given code unit position |index|. If
+// |index| is a surrogate code unit, returns the whole code point (unless the
+// code unit is unpaired, in which case it just returns the surrogate value).
+UChar32 GetCodePointAt(const base::string16& str, size_t index) {
+  UChar32 c;
+  U16_GET(str.data(), 0, index, str.size(), c);
+  return c;
+}
+
 // 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(size_t max_width,
                       int min_baseline,
                       float min_height,
-                      bool multiline,
                       WordWrapBehavior word_wrap_behavior,
                       const base::string16& text,
                       const BreakList<size_t>* words,
                       const internal::TextRunList& run_list)
       : max_width_((max_width == 0) ? SK_ScalarMax : SkIntToScalar(max_width)),
         min_baseline_(min_baseline),
         min_height_(min_height),
-        multiline_(multiline),
         word_wrap_behavior_(word_wrap_behavior),
         text_(text),
         words_(words),
         run_list_(run_list),
+        max_descent_(0),
+        max_ascent_(0),
         text_x_(0),
-        line_x_(0),
-        max_descent_(0),
-        max_ascent_(0) {
-    DCHECK_EQ(multiline_, (words_ != nullptr));
+        available_width_(max_width_) {
     AdvanceLine();
   }
 
-  // Breaks the run at given |run_index| into Line structs.
-  void AddRun(int run_index) {
-    const internal::TextRunHarfBuzz* run = run_list_.runs()[run_index];
-    base::char16 first_char = text_[run->range.start()];
-    if (multiline_ && first_char == '\n') {
-      AdvanceLine();
-    } else if (multiline_ && (line_x_ + SkFloatToScalar(run->width)) >
-               max_width_) {
-      BreakRun(run_index);
-    } else {
-      AddSegment(run_index, run->range, run->width);
+  // Constructs a single line for |text_| using |run_list_|.
+  void ConstructSingleLine() {
+    for (size_t i = 0; i < run_list_.size(); i++) {
+      const internal::TextRunHarfBuzz& run = *(run_list_.runs()[i]);
+      internal::LineSegment segment;
+      segment.run = i;
+      segment.char_range = run.range;
+      segment.x_range = Range(SkScalarCeilToInt(text_x_),
+                              SkScalarCeilToInt(text_x_ + run.width));
+      segment.width = run.width;
+      AddLineSegment(segment);
+    }
+  }
+
+  // Constructs multiple lines for |text_| based on words iteration approach.
+  void ConstructMultiLines() {
+    DCHECK(words_);
+    for (auto iter = words_->breaks().begin(); iter != words_->breaks().end();
+         iter++) {
+      const Range word_range = words_->GetRange(iter);
+      std::vector<internal::LineSegment> word_segments;
+      SkScalar word_width = GetWordWidth(word_range, &word_segments);
+
+      // If the last word is '\n', we should advance a new line after adding
+      // the word to the current line.
+      bool new_line = false;
+
+      if (!word_segments.empty() &&
+          text_[word_segments.back().char_range.start()] == '\n') {
+        new_line = true;
+        word_width -= word_segments.back().width;
+        word_segments.pop_back();
+      }
+
+      // If the word is not the first word in the line and it can't fit into
+      // the current line, advance a new line.
+      if (word_width > available_width_ && available_width_ != max_width_)
+        AdvanceLine();
+      AddWordToLine(word_segments);
+      if (new_line)
+        AdvanceLine();
     }
   }
 
   // Finishes line breaking and outputs the results. Can be called at most once.
-  void Finalize(std::vector<internal::Line>* lines, SizeF* size) {
+  void FinalizeLines(std::vector<internal::Line>* lines, SizeF* 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;
 
   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) {
-    const internal::TextRunHarfBuzz& run = *(run_list_.runs()[run_index]);
-    SkScalar 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;
-      size_t end_char = next_char;
-      const bool skip_line =
-          BreakRunAtWidth(run, current_char, &width, &end_char, &next_char);
-      AddSegment(run_index, Range(current_char, end_char),
-                 SkScalarToFloat(width));
-      if (skip_line)
-        AdvanceLine();
-    }
-  }
-
-  // Starting from |start_char|, finds a suitable line break position at or
-  // before available width using word break. 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). It stores the end of the segment range to |end_char|, which can be
-  // smaller than |*next_char| for certain word wrapping behavior.
-  // Returns whether to skip the line before |*next_char|.
-  // 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,
-                       SkScalar* width,
-                       size_t* end_char,
-                       size_t* next_char) {
-    DCHECK(words_);
-    DCHECK(run.range.Contains(Range(start_char, start_char + 1)));
-    SkScalar available_width = 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;
-    *width = 0;
-
-    Range char_range;
-    SkScalar truncated_width = 0;
-    for (size_t i = start_char; i < run.range.end(); i += char_range.length()) {
-      // |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) {
-        if (*width > available_width) {
-          DCHECK_NE(WRAP_LONG_WORDS, word_wrap_behavior_);
-          *next_char = i;
-          if (word_wrap_behavior_ != TRUNCATE_LONG_WORDS)
-            *end_char = *next_char;
-          else
-            *width = truncated_width;
-          return true;
-        }
-        word = next_word++;
-        word_width = 0;
-      }
-
-      Range glyph_range;
-      run.GetClusterAt(i, &char_range, &glyph_range);
-      DCHECK_LT(0U, char_range.length());
-
-      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 += char_width;
-      word_width += char_width;
-
-      // TODO(mukai): implement ELIDE_LONG_WORDS.
-      if (*width > available_width) {
-        if (line_x_ != 0 || word_width < *width) {
-          // Roll back one word.
-          *width -= word_width;
-          *next_char = std::max(word->first, start_char);
-          *end_char = *next_char;
-          return true;
-        } else if (word_wrap_behavior_ == WRAP_LONG_WORDS) {
-          if (char_width < *width) {
-            // Roll back one character.
-            *width -= char_width;
-            *next_char = i;
-          } else {
-            // Continue from the next character.
-            *next_char = i + char_range.length();
-          }
-          *end_char = *next_char;
-          return true;
-        }
-      } else {
-        *end_char = char_range.end();
-        truncated_width = *width;
-      }
-    }
-
-    if (word_wrap_behavior_ == TRUNCATE_LONG_WORDS)
-      *width = truncated_width;
-    *end_char = *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;
-    float 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 float segment_width = segment->width;
-      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();
       std::sort(line->segments.begin(), line->segments.end(),
                 [this](const internal::LineSegment& s1,
                        const internal::LineSegment& s2) -> bool {
                   return run_list_.logical_to_visual(s1.run) <
                          run_list_.logical_to_visual(s2.run);
                 });
       line->size.set_height(std::max(min_height_, max_descent_ + max_ascent_));
-      line->baseline =
-          std::max(min_baseline_, SkScalarRoundToInt(max_ascent_));
+      line->baseline = std::max(min_baseline_, SkScalarRoundToInt(max_ascent_));
       line->preceding_heights = std::ceil(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()));
     }
     max_descent_ = 0;
     max_ascent_ = 0;
-    line_x_ = 0;
+    available_width_ = max_width_;
     lines_.push_back(internal::Line());
   }
 
-  // Adds a new segment with the given properties to |lines_.back()|.
-  void AddSegment(int run_index, Range char_range, float width) {
-    if (char_range.is_empty()) {
-      DCHECK_EQ(0, width);
+  // Adds word to the current line. A word may contain multiple segments. If the
+  // word is the first word in line and its width exceeds |available_width_|,
+  // ignore/truncate/wrap it according to |word_wrap_behavior_|.
+  void AddWordToLine(const std::vector<internal::LineSegment>& word_segments) {
+    DCHECK(!lines_.empty());
+    if (word_segments.empty())
       return;
+
+    bool has_truncated = false;
+    for (const internal::LineSegment& segment : word_segments) {
+      if (has_truncated)
+        break;
+      if (segment.width <= available_width_ ||
+          word_wrap_behavior_ == IGNORE_LONG_WORDS) {
+        AddLineSegment(segment);
+      } else {
+        DCHECK(word_wrap_behavior_ == TRUNCATE_LONG_WORDS ||
+               word_wrap_behavior_ == WRAP_LONG_WORDS);
+        has_truncated = (word_wrap_behavior_ == TRUNCATE_LONG_WORDS);
+
+        const internal::TextRunHarfBuzz& run = *(run_list_.runs()[segment.run]);
+        internal::LineSegment remaining_segment = segment;
+        while (!remaining_segment.char_range.is_empty()) {
+          size_t cutoff_pos = GetCutoffPos(remaining_segment);
+          // Corrects the boundary position if necessary. The surrogate pair and
+          // combined characters should not be separated.
+          FindValidBoundaryBefore(remaining_segment, &cutoff_pos);

[msw, 2015/06/01 23:27:18]

Can this be part of GetCutoffPos?

[xdai1, 2015/06/02 03:49:56]

Done.

+          SkScalar width =
+              remaining_segment.char_range.start() == cutoff_pos

[msw, 2015/06/01 23:27:18]

nit: put this ==/0 logic in GetGlyphWidthForCharRange

[xdai1, 2015/06/02 03:49:56]

Done.

+                  ? 0
+                  : run.GetGlyphWidthForCharRange(Range(
+                        remaining_segment.char_range.start(), cutoff_pos));
+
+          // |max_width_| might be smaller than a single character. In this case

[msw, 2015/06/01 23:27:18]

Ditto, can this be part of GetCutoffPos?

[xdai1, 2015/06/02 03:49:56]

Done.

+          // we need to put at least one character in the line. Note that, we
+          // should not separate surrogate pair or combined characters.
+          // See RenderTextTest.Multiline_MinWidth for an example.
+          if (width == 0 && available_width_ == max_width_) {
+            // Skip all zero width characters.
+            for (cutoff_pos = remaining_segment.char_range.start();
+                 cutoff_pos < remaining_segment.char_range.end();
+                 cutoff_pos++) {
+              SkScalar char_width = run.GetGlyphWidthForCharRange(
+                  Range(cutoff_pos, cutoff_pos + 1));
+              if (char_width > 0)
+                break;
+            }
+            // Don't separate surrogate pair or combined characters.
+            cutoff_pos = FindValidBoundaryAfter(remaining_segment, cutoff_pos);
+            width = run.GetGlyphWidthForCharRange(
+                Range(remaining_segment.char_range.start(), cutoff_pos));
+          }
+
+          if (width > 0) {
+            internal::LineSegment cut_segment;
+            cut_segment.run = remaining_segment.run;
+            cut_segment.char_range =
+                Range(remaining_segment.char_range.start(), cutoff_pos);
+            cut_segment.width = width;
+            cut_segment.x_range = Range(remaining_segment.x_range.start(),
+                                        SkScalarCeilToInt(text_x_ + width));
+            AddLineSegment(cut_segment);
+            // Updates old segment range.
+            remaining_segment.char_range.set_start(cutoff_pos);
+            remaining_segment.x_range.set_start(SkScalarCeilToInt(text_x_));
+            remaining_segment.width -= width;
+          }
+          if (has_truncated)
+            break;
+          if (!remaining_segment.char_range.is_empty())
+            AdvanceLine();
+        }
+      }
     }
-    const internal::TextRunHarfBuzz& run = *(run_list_.runs()[run_index]);
+  }
 
-    internal::LineSegment segment;
-    segment.run = run_index;
-    segment.char_range = char_range;
-    segment.x_range = Range(
-        SkScalarCeilToInt(text_x_),
-        SkScalarCeilToInt(text_x_ + SkFloatToScalar(width)));
-    segment.width = width;
-
+  // Add a line segment to the current line. Note that, in order to keep the
+  // visual order correct for ltr and rtl language, we need to merge segments
+  // that belong to the same run.
+  void AddLineSegment(const internal::LineSegment& segment) {
+    DCHECK(!lines_.empty());
     internal::Line* line = &lines_.back();
+    const internal::TextRunHarfBuzz& run = *(run_list_.runs()[segment.run]);
+    if (!line->segments.empty()) {
+      internal::LineSegment& last_segment = line->segments.back();
+      // Merge segments that belong to the same run.
+      if (last_segment.run == segment.run) {
+        DCHECK(last_segment.char_range.end() == segment.char_range.start());

[msw, 2015/06/01 23:27:18]

nit: DCHECK_EQ here and below.

[xdai1, 2015/06/02 03:49:56]

Done.

+        DCHECK(last_segment.x_range.end() == segment.x_range.start());
+        last_segment.char_range.set_end(segment.char_range.end());
+        last_segment.width += segment.width;
+        last_segment.x_range.set_end(
+            SkScalarCeilToInt(text_x_ + segment.width));
+        if (run.is_rtl && last_segment.char_range.end() == run.range.end())
+          UpdateRTLSegmentRanges();
+        line->size.set_width(line->size.width() + segment.width);
+        text_x_ += segment.width;
+        available_width_ -= segment.width;
+        return;
+      }
+    }
     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() + width);
+    line->size.set_width(line->size.width() + segment.width);
     // TODO(dschuyler): Account for stylized baselines in string sizing.
     max_descent_ = std::max(max_descent_, metrics.fDescent);
     // fAscent is always negative.
     max_ascent_ = std::max(max_ascent_, -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())
+      if (segment.char_range.end() == run.range.end())
         UpdateRTLSegmentRanges();
     }
-    text_x_ += SkFloatToScalar(width);
-    line_x_ += SkFloatToScalar(width);
+    text_x_ += segment.width;
+    available_width_ -= segment.width;
+  }
+
+  // Finds the end position |end_pos| in |segment| where the preceding width is
+  // no larger than |available_width_|.
+  size_t GetCutoffPos(const internal::LineSegment& segment) const {
+    DCHECK(!segment.char_range.is_empty());
+    const internal::TextRunHarfBuzz& run = *(run_list_.runs()[segment.run]);
+    size_t end_pos = segment.char_range.start();
+    SkScalar width = 0;
+    while (end_pos < segment.char_range.end()) {
+      const SkScalar char_width =
+          run.GetGlyphWidthForCharRange(Range(end_pos, end_pos + 1));
+      if (width + char_width > available_width_)
+        break;
+      width += char_width;
+      end_pos++;
+    }
+    return end_pos;
+  }
+
+  // Finds the first valid position after |start_pos| for |segment|. The
+  // surrogate pair and combined characters should not be separated. If there
+  // is no surrogate pair or combined characters, return |start_pos| + 1.
+  size_t FindValidBoundaryAfter(const internal::LineSegment& segment,

[msw, 2015/06/01 23:27:18]

Can we avoid copying modified versions of text_elider.cc code (CharIsMark,
GetCodePointAt, FindValidBoundary[Before|After]) here? Maybe expose the needed
helpers on StringSlicer or as text_elider/text_util functions?

[xdai1, 2015/06/02 03:49:56]

Put these functions in text_util.h and text_util.cc files.

+                                const size_t start_pos) {
+    DCHECK_GE(start_pos, segment.char_range.start());
+    DCHECK_LT(start_pos, segment.char_range.end());
+
+    size_t index = start_pos;
+    // Check if it is a surrogate pair.
+    if (index <= text_.size() - 2 && U16_IS_LEAD(text_[index]) &&
+        U16_IS_TRAIL(text_[index + 1])) {
+      return index + 2;
+    }
+
+    // Check if it is a combined character.
+    while (index < segment.char_range.end() &&
+           CharIsMark(GetCodePointAt(text_, index))) {
+      index++;
+    }
+    // If |index| straddles a surrogate pair, go forward.
+    U16_SET_CP_LIMIT(text_.data(), 0, index, text_.size());
+
+    return index == start_pos ? start_pos + 1 : index;
+  }
+
+  // Corrects the boundary position |end_pos| if necessary. The surrogate
+  // pair and combined characters should not be separated.
+  void FindValidBoundaryBefore(const internal::LineSegment& segment,
+                               size_t* end_pos) {
+    DCHECK_GE(*end_pos, segment.char_range.start());
+    DCHECK_LE(*end_pos, segment.char_range.end());
+    if (*end_pos == segment.char_range.start())
+      return;
+
+    size_t index = *end_pos;
+    // Check the surrogate pair was separated, go back.
+    if (index > 0 && index < text_.size() - 1 &&
+        U16_IS_LEAD(text_[index - 1]) && U16_IS_TRAIL(text_[index])) {
+      *end_pos = index - 1;
+      return;
+    }
+
+    // Check if it is a combined character.
+    while (index > segment.char_range.start() &&
+           CharIsMark(GetCodePointAt(text_, index - 1))) {
+      index--;
+    }
+    // If |index| straddles a surrogate pair, go back.
+    U16_SET_CP_START(text_.data(), segment.char_range.start(), index);
+
+    *end_pos = index;
+  }
+
+  // Gets the glyph width for |word_range|, and splits the |word| into different
+  // segments based on its runs.
+  SkScalar GetWordWidth(const Range& word_range,
+                        std::vector<internal::LineSegment>* segments) const {
+    DCHECK(words_);
+    if (word_range.is_empty() || segments == nullptr)
+      return 0;
+    size_t run_start_index = run_list_.GetRunIndexAt(word_range.start());
+    size_t run_end_index = run_list_.GetRunIndexAt(word_range.end() - 1);
+    SkScalar width = 0;
+    for (size_t i = run_start_index; i <= run_end_index; i++) {
+      const internal::TextRunHarfBuzz& run = *(run_list_.runs()[i]);
+      const Range char_range = run.range.Intersect(word_range);
+      DCHECK(!char_range.is_empty());
+      const SkScalar char_width = run.GetGlyphWidthForCharRange(char_range);
+      width += char_width;
+
+      internal::LineSegment segment;
+      segment.run = i;
+      segment.char_range = char_range;
+      segment.width = char_width;
+      segment.x_range = Range(SkScalarCeilToInt(text_x_ + width - char_width),
+                              SkScalarCeilToInt(text_x_ + width));
+      segments->push_back(segment);
+    }
+    return width;
+  }
+
+  // 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;
+    float 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 float segment_width = segment->width;
+      segment->x_range = Range(x, x + segment_width);
+      x += segment_width;
+    }
+    rtl_segments_.clear();
   }
 
   const SkScalar max_width_;
   const int min_baseline_;
   const float min_height_;
-  const bool multiline_;
   const WordWrapBehavior word_wrap_behavior_;
   const base::string16& text_;
   const BreakList<size_t>* const words_;
   const internal::TextRunList& run_list_;
 
   // Stores the resulting lines.
   std::vector<internal::Line> lines_;
 
-  // Text space and line space x coordinates of the next segment to be added.
-  SkScalar text_x_;
-  SkScalar line_x_;
-
   float max_descent_;
   float max_ascent_;
 
+  // Text space x coordinates of the next segment to be added.
+  SkScalar text_x_;
+  // Stores available width in the current line.
+  SkScalar available_width_;
+
   // Size of the multiline text, not including the currently processed line.
   SizeF total_size_;
 
   // The current RTL run segments, to be applied by |UpdateRTLSegmentRanges()|.
   std::vector<SegmentHandle> rtl_segments_;
 
   DISALLOW_COPY_AND_ASSIGN(HarfBuzzLineBreaker);
 };
 
 // Function object for case insensitive string comparison.
@@ skipping 23 matching lines @@
       baseline_offset(0),
       baseline_type(0),
       font_style(0),
       strike(false),
       diagonal_strike(false),
       underline(false) {
 }
 
 TextRunHarfBuzz::~TextRunHarfBuzz() {}
 
-void TextRunHarfBuzz::GetClusterAt(size_t pos,
-                                   Range* chars,
-                                   Range* glyphs) const {
-  DCHECK(range.Contains(Range(pos, pos + 1)));
-  DCHECK(chars);
-  DCHECK(glyphs);
-
-  if (glyph_count == 0) {
-    *chars = range;
-    *glyphs = Range();
-    return;
-  }
-
-  if (is_rtl) {
-    GetClusterAtImpl(pos, range, glyph_to_char.rbegin(), glyph_to_char.rend(),
-        true, chars, glyphs);
-    return;
-  }
-
-  GetClusterAtImpl(pos, range, glyph_to_char.begin(), glyph_to_char.end(),
-      false, chars, glyphs);
-}
-
 Range TextRunHarfBuzz::CharRangeToGlyphRange(const Range& char_range) const {
   DCHECK(range.Contains(char_range));
   DCHECK(!char_range.is_reversed());
   DCHECK(!char_range.is_empty());
 
   Range start_glyphs;
   Range end_glyphs;
   Range temp_range;
   GetClusterAt(char_range.start(), &temp_range, &start_glyphs);
   GetClusterAt(char_range.end() - 1, &temp_range, &end_glyphs);
 
   return is_rtl ? Range(end_glyphs.start(), start_glyphs.end()) :
       Range(start_glyphs.start(), end_glyphs.end());
 }
 
 size_t TextRunHarfBuzz::CountMissingGlyphs() const {
   static const int kMissingGlyphId = 0;
   size_t missing = 0;
   for (size_t i = 0; i < glyph_count; ++i)
     missing += (glyphs[i] == kMissingGlyphId) ? 1 : 0;
   return missing;
 }
 
+void TextRunHarfBuzz::GetClusterAt(size_t pos,
+                                   Range* chars,
+                                   Range* glyphs) const {
+  DCHECK(range.Contains(Range(pos, pos + 1)));
+  DCHECK(chars);
+  DCHECK(glyphs);
+
+  if (glyph_count == 0) {
+    *chars = range;
+    *glyphs = Range();
+    return;
+  }
+
+  if (is_rtl) {
+    GetClusterAtImpl(pos, range, glyph_to_char.rbegin(), glyph_to_char.rend(),
+                     true, chars, glyphs);
+    return;
+  }
+
+  GetClusterAtImpl(pos, range, glyph_to_char.begin(), glyph_to_char.end(),
+                   false, chars, glyphs);
+}
+
 RangeF TextRunHarfBuzz::GetGraphemeBounds(
     base::i18n::BreakIterator* grapheme_iterator,
     size_t text_index) {
   DCHECK_LT(text_index, range.end());
   if (glyph_count == 0)
     return RangeF(preceding_run_widths, preceding_run_widths + width);
 
   Range chars;
   Range glyphs;
   GetClusterAt(text_index, &chars, &glyphs);
@@ skipping 28 matching lines @@
           cluster_width * (before + 1) / static_cast<float>(total));
       return RangeF(preceding_run_widths + grapheme_begin_x,
                     preceding_run_widths + grapheme_end_x);
     }
   }
 
   return RangeF(preceding_run_widths + cluster_begin_x,
                 preceding_run_widths + cluster_end_x);
 }
 
+SkScalar TextRunHarfBuzz::GetGlyphWidthForCharRange(
+    const Range& char_range) const {
+  DCHECK(range.Contains(char_range));
+  Range glyph_range = CharRangeToGlyphRange(char_range);
+  return ((glyph_range.end() == glyph_count)
+              ? SkFloatToScalar(width)
+              : positions[glyph_range.end()].x()) -
+         positions[glyph_range.start()].x();
+}
+
 TextRunList::TextRunList() : width_(0.0f) {}
 
 TextRunList::~TextRunList() {}
 
 void TextRunList::Reset() {
   runs_.clear();
   width_ = 0.0f;
 }
 
 void TextRunList::InitIndexMap() {
@@ skipping 14 matching lines @@
 void TextRunList::ComputePrecedingRunWidths() {
   // Precalculate run width information.
   width_ = 0.0f;
   for (size_t i = 0; i < runs_.size(); ++i) {
     TextRunHarfBuzz* run = runs_[visual_to_logical_[i]];
     run->preceding_run_widths = width_;
     width_ += run->width;
   }
 }
 
+size_t TextRunList::GetRunIndexAt(size_t position) const {
+  for (size_t i = 0; i < runs_.size(); ++i) {
+    if (runs_[i]->range.start() <= position && runs_[i]->range.end() > position)
+      return i;
+  }
+  return runs_.size();
+}
+
 }  // namespace internal
 
 RenderTextHarfBuzz::RenderTextHarfBuzz()
     : RenderText(),
       update_layout_run_list_(false),
       update_display_run_list_(false),
       update_grapheme_iterator_(false),
       update_display_text_(false),
       glyph_width_for_test_(0u) {
   set_truncate_length(kMaxTextLength);
@@ skipping 328 matching lines @@
   if (lines().empty()) {
     // TODO(ckocagil): Remove ScopedTracker below once crbug.com/441028 is
     // fixed.
     scoped_ptr<tracked_objects::ScopedTracker> tracking_profile(
         new tracked_objects::ScopedTracker(
             FROM_HERE_WITH_EXPLICIT_FUNCTION("441028 HarfBuzzLineBreaker")));
 
     internal::TextRunList* run_list = GetRunList();
     HarfBuzzLineBreaker line_breaker(
         display_rect().width(), font_list().GetBaseline(),
-        std::max(font_list().GetHeight(), min_line_height()), multiline(),
+        std::max(font_list().GetHeight(), min_line_height()),
         word_wrap_behavior(), GetDisplayText(),
         multiline() ? &GetLineBreaks() : nullptr, *run_list);
 
     tracking_profile.reset();
 
-    for (size_t i = 0; i < run_list->size(); ++i)
-      line_breaker.AddRun(i);
+    if (multiline())
+      line_breaker.ConstructMultiLines();
+    else
+      line_breaker.ConstructSingleLine();
     std::vector<internal::Line> lines;
-    line_breaker.Finalize(&lines, &total_size_);
+    line_breaker.FinalizeLines(&lines, &total_size_);
     set_lines(&lines);
   }
 }
 
 void RenderTextHarfBuzz::DrawVisualText(Canvas* canvas) {
   internal::SkiaTextRenderer renderer(canvas);
   DrawVisualTextInternal(&renderer);
 }
 
 void RenderTextHarfBuzz::DrawVisualTextInternal(
@@ skipping 448 matching lines @@
   DCHECK(!update_layout_run_list_);
   DCHECK(!update_display_run_list_);
   return text_elided() ? display_run_list_.get() : &layout_run_list_;
 }
 
 const internal::TextRunList* RenderTextHarfBuzz::GetRunList() const {
   return const_cast<RenderTextHarfBuzz*>(this)->GetRunList();
 }
 
 }  // namespace gfx