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"
@@ skipping 31 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
+// If the given scripts match, returns the one that isn't USCRIPT_INHERITED,
+// i.e. the more specific one. Otherwise returns
 // USCRIPT_INVALID_CODE.

[msw, 2015/05/27 17:38:00]

nit: fits on line above.

[xdai1, 2015/06/01 16:51:15]

Done.

 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 37 matching lines @@
 // 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_),

[msw, 2015/05/27 17:37:59]

The segment ranges should probably be RangeF, but that's not critical here.

[xdai1, 2015/06/01 16:51:15]

Yes, we probably should use RangeF for the X coordinates of a line segment. I
can address that in another CL, if you don't mind.

+                              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);

[msw, 2015/05/28 18:16:16]

The old algorithm created one segment per run, or more if the run was split
across multiple lines. This new algorithm creates a segment for every word!
Segments aren't too expensive, but this seems wasteful and may have negative
performance impacts. Would it make sense to add entire runs when the run width
will fit, then resort to word breaking when the whole run doesn't fit?

Hmm, I guess that would break the case where a word is split across multiple
runs... And perhaps we don't actually increase the final number of segments,
since AddLineSegment merges segments from the same run... Perhaps this is okay,
but did you consider any alternative solutions?

[xdai1, 2015/06/01 16:51:15]

Yes, the number of the segments is the same with that in the old algorithm. 

Breaking text into lines based on words seems the most natural way to me, which
is also used by many modern word processors, such as OpenOffice and Microsoft
Word (http://en.wikipedia.org/wiki/Line_wrap_and_word_wrap#Algorithm). 

Actually combining these two approach together was what I did in old patches
(see Patch 11): keep the run-level iteration, but resort to word-level approach
when the current run doesn't fit in the current line. As you could see, the
logic is much much more complicated. After discussed with Mukai for several
times, we agreed that it might be better to not mix them up.   

The time complexity of these two approaches should be the same: in worst case we
both need to process each character one by one. 

+
+      bool new_line = false;
+      if (!word_segments.empty()) {
+        // If the word is end with '\n', we should advance a new line after

[msw, 2015/05/28 18:16:16]

nit: s/is end/ends/ or consider "If the last word is '\n'"

[xdai1, 2015/06/01 16:51:14]

Done.

+        // adding the word to current line.

[msw, 2015/05/28 18:16:16]

nit: "to the current"

[xdai1, 2015/06/01 16:51:14]

Done.

+        const internal::LineSegment& last_segment = word_segments.back();
+        const base::char16 last_char = text_[last_segment.char_range.start()];
+        if (last_char == '\n') {

[msw, 2015/05/28 18:16:16]

nit: inline if (text_[word_segments.back().char_range.start()] == '\n')
you can also combine that with the if statement above.

[xdai1, 2015/06/01 16:51:15]

Done.

+          new_line = true;
+          word_width -= last_segment.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())

[msw, 2015/05/28 18:16:15]

nit: this probably shouldn't happen either; make this a dcheck?

[xdai1, 2015/06/01 16:51:14]

This might happen, see test function: RenderTextTest.Multiline_SufficientWidth. 

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

When the overall text is empty? Should the code bail earlier then?

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

For example, if the entire text is "\n" or just "", then we might encounter this
situation (word_segments is empty). But yes, we could make it an early return.

       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);
+
+        internal::LineSegment remain_segment = segment;

[msw, 2015/05/28 18:16:16]

nit: remaining_segment or truncated_segment

[xdai1, 2015/06/01 16:51:15]

Done.

+        while (!remain_segment.char_range.is_empty()) {
+          size_t cutoff_pos = 0;
+          SkScalar width = GetCutoffWidth(remain_segment, &cutoff_pos);
+          if (width == 0 && available_width_ == max_width_) {
+            // |max_width_| might be smaller than a single character. In this
+            // case we need to put at least one character in the line.
+            // See RenderTextTest.Multiline_MinWidth for example.

[msw, 2015/05/28 18:16:16]

nit: for an example

[xdai1, 2015/06/01 16:51:16]

Done.

+            cutoff_pos = remain_segment.char_range.start() + 1;

[msw, 2015/05/28 18:16:16]

I wonder if this is correct/sufficient, what if the character is a surrogate
pair, a zero width character, or something else?

[xdai1, 2015/06/01 16:51:15]

You're right, we should special handle these cases here. 

+            const internal::TextRunHarfBuzz& run =
+                *(run_list_.runs()[remain_segment.run]);
+            width = run.GetGlyphWidthForCharRange(
+                Range(remain_segment.char_range.start(), cutoff_pos));
+          }
+          if (width > 0) {
+            internal::LineSegment cut_segment;
+            cut_segment.run = remain_segment.run;
+            cut_segment.char_range =
+                Range(remain_segment.char_range.start(), cutoff_pos);
+            cut_segment.width = width;
+            cut_segment.x_range = Range(remain_segment.x_range.start(),
+                                        SkScalarCeilToInt(text_x_ + width));

[msw, 2015/05/28 18:16:16]

Should this be remain_segment.x_range.start() + width?

[xdai1, 2015/06/01 16:51:16]

It's preciser to use text_x_ instead of remain_segment.x_range.start() since the
x_range was floored due to type coercion of float -> size_t. 

text_x_ will be updated each time when calling AddLineSegment().

+            AddLineSegment(cut_segment);
+            // Updates old segment range.
+            remain_segment.char_range.set_start(cutoff_pos);
+            remain_segment.x_range.set_start(SkScalarCeilToInt(text_x_));
+            remain_segment.width -= width;
+          }
+          if (has_truncated)
+            break;
+          if (!remain_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 line segment to current line. Note in order to keep the visual order

[msw, 2015/05/27 17:37:59]

nit: "Add a line segment to the current line. Note that, in order..."

[xdai1, 2015/06/01 16:51:15]

Done.

+  // correct for ltr and rtl language, we need to merge segments that belong to
+  // a same run.

[msw, 2015/05/27 17:37:59]

nit: "the same run"

[xdai1, 2015/06/01 16:51:15]

Done.

+  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) {
+        last_segment.char_range.set_end(segment.char_range.end());

[msw, 2015/05/28 18:16:16]

nit: can we dcheck that the segments actually contain adjacent indices (ie.
last_segment.char_range.end() == segment.char_range.start())?

[xdai1, 2015/06/01 16:51:15]

Done.

+        last_segment.width += segment.width;
+        last_segment.x_range.set_end(

[msw, 2015/05/28 18:16:16]

ditto: can we dcheck that the x_ranges are adjacent?

[xdai1, 2015/06/01 16:51:15]

Done.

+            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| that the preceding width is

[msw, 2015/05/28 18:16:16]

nit: s/that/where/

[xdai1, 2015/06/01 16:51:15]

Done.

+  // no larger than |available_width_|, and returns the preceding width.
+  SkScalar GetCutoffWidth(const internal::LineSegment& segment,
+                          size_t* end_pos) const {
+    DCHECK(!segment.char_range.is_empty());
+    const internal::TextRunHarfBuzz& run = *(run_list_.runs()[segment.run]);
+    *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 += 1;

[msw, 2015/05/28 18:16:15]

nit: (*end_pos)++;

[xdai1, 2015/06/01 16:51:15]

Done.

+    }
+    return width;
+  }
+
+  // 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 idx = run_start_index; idx <= run_end_index; idx++) {

[msw, 2015/05/28 18:16:16]

nit: why |idx| instead of |i|?

[xdai1, 2015/06/01 16:51:15]

Done.

+      const internal::TextRunHarfBuzz& run = *(run_list_.runs()[idx]);
+      const Range char_range = run.range.Intersect(word_range);
+      if (char_range.is_empty())

[msw, 2015/05/28 18:16:15]

It seems like this shouldn't be possible, maybe DCHECK instead?

[xdai1, 2015/06/01 16:51:15]

Done.

+        continue;
+      const SkScalar char_width = run.GetGlyphWidthForCharRange(char_range);
+      width += char_width;
+
+      internal::LineSegment segment;
+      segment.run = idx;
+      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_;

[msw, 2015/05/27 17:37:59]

If |available_width_| == |max_width_ - text_x_|, why do we need both?

[xdai1, 2015/06/01 16:51:15]

|available_width_| will be reset when advancing a new line but |text_x_| won't.

+
   // 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)

[msw, 2015/05/27 17:37:59]

When would the glyph range include anything beyond glyph_count? Shouldn't we
DHECK_LE(glyph_range.start(), glyph_count) and DHECK_LE(glyph_range.end(),
glyph_count) or DHECK(Range(0, glyph_count).contains(glyph_range))? 

[xdai1, 2015/06/01 16:51:15]

Yes, it is not possible that glyph_range.end() include anything beyond
glyph_count. It should be better using "==" instead of ">=" in the conditional
ternary operator. Done.

+              ? SkFloatToScalar(width)

[msw, 2015/05/27 17:37:59]

This seems wrong; if the glyph_range is (4, 7) and glyph_count is 7, I don't
think this should return the full run width.

[xdai1, 2015/06/01 16:51:14]

It will not return the full run width, it will return width -
positions[glyph_range.start()].x().

+              : positions[glyph_range.end()].x()) -
+         positions[glyph_range.start()].x();

[msw, 2015/05/27 17:37:59]

nit: this indentation seems wrong.

[xdai1, 2015/06/01 16:51:15]

It seems right. It's not inside of the conditional ternary operator.

+}
+
 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 {

[msw, 2015/05/27 17:37:59]

Hmm, it'd be nice if this could share logic with GetRunContainingCaret or
RangeContainsCaret, but that doesn't seem terribly straightforward.

[xdai1, 2015/06/01 16:51:14]

Sorry, I didn't see how can we do that...

+  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