// 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/macros.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 "build/build_config.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.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/skia_util.h"
#include "ui/gfx/text_utils.h"
#include "ui/gfx/utf16_indexing.h"

#if defined(OS_WIN)
#include "ui/gfx/font_fallback_win.h"
#endif

namespace gfx {

namespace {

// Text length limit. Longer strings are slow and not fully tested.
const size_t kMaxTextLength = 10000;

// 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.
bool IsUnusualBlockCode(UBlockCode block_code) {
  return block_code == UBLOCK_GEOMETRIC_SHAPES ||
         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;
}

// If the given scripts match, returns the one that isn't USCRIPT_INHERITED,
// i.e. the more specific one. Otherwise returns USCRIPT_INVALID_CODE. This
// function is used to split runs between characters of different script codes,
// unless either character has USCRIPT_INHERITED property. See crbug.com/448909.
UScriptCode ScriptIntersect(UScriptCode first, UScriptCode second) {
  if (first == second || second == USCRIPT_INHERITED)
    return first;
  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.
  // Write the character's script property to the first element.
  scripts[0] = uscript_getScript(codepoint, &icu_error);
  if (U_FAILURE(icu_error))
    return 0;
  // Fill the rest of |scripts| with the extensions.
  int count = uscript_getScriptExtensions(codepoint, scripts + 1,
                                          kMaxScripts - 1, &icu_error);
  if (U_FAILURE(icu_error))
    count = 0;
  return count + 1;
}

// Intersects the script extensions set of |codepoint| with |result| and writes
// to |result|, reading and updating |result_size|.
void ScriptSetIntersect(UChar32 codepoint,
                        UScriptCode* result,
                        size_t* result_size) {
  UScriptCode scripts[kMaxScripts] = { USCRIPT_INVALID_CODE };
  int count = GetScriptExtensions(codepoint, scripts);

  size_t out_size = 0;

  for (size_t i = 0; i < *result_size; ++i) {
    for (int j = 0; j < count; ++j) {
      UScriptCode intersection = ScriptIntersect(result[i], scripts[j]);
      if (intersection != USCRIPT_INVALID_CODE) {
        result[out_size++] = intersection;
        break;
      }
    }
  }

  *result_size = out_size;
}

// Returns true if |first_char| and |current_char| both have "COMMON" script
// property but only one of them is an ASCII character. By doing this ASCII
// characters will be put into a separate run and be rendered using its default
// font. See crbug.com/530021 and crbug.com/533721 for more details.
bool AsciiBreak(UChar32 first_char, UChar32 current_char) {
  if (isascii(first_char) == isascii(current_char))
    return false;

  size_t scripts_size = 1;
  UScriptCode scripts[kMaxScripts] = { USCRIPT_COMMON };
  ScriptSetIntersect(first_char, scripts, &scripts_size);
  if (scripts_size == 0)
    return false;
  ScriptSetIntersect(current_char, scripts, &scripts_size);
  return scripts_size != 0;
}

// Returns the boundary between a special and a regular character. Special
// characters are brackets or characters that satisfy |IsUnusualBlockCode|.
size_t FindRunBreakingCharacter(const base::string16& text,
                                size_t run_start,
                                size_t run_break) {
  const int32_t run_length = static_cast<int32_t>(run_break - run_start);
  base::i18n::UTF16CharIterator iter(text.c_str() + run_start, run_length);
  const UChar32 first_char = iter.get();
  // The newline character should form a single run so that the line breaker
  // can handle them easily.
  if (first_char == '\n')
    return run_start + 1;

  const UBlockCode first_block = ublock_getCode(first_char);
  const bool first_block_unusual = IsUnusualBlockCode(first_block);
  const bool first_bracket = IsBracket(first_char);

  while (iter.Advance() && iter.array_pos() < run_length) {
    const UChar32 current_char = iter.get();
    const UBlockCode current_block = ublock_getCode(current_char);
    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) ||
        AsciiBreak(first_char, current_char)) {
      return run_start + iter.array_pos();
    }
  }
  return run_break;
}

// Find the longest sequence of characters from 0 and up to |length| that
// have at least one common UScriptCode value. Writes the common script value to
// |script| and returns the length of the sequence. Takes the characters' script
// extensions into account. http://www.unicode.org/reports/tr24/#ScriptX
//
// Consider 3 characters with the script values {Kana}, {Hira, Kana}, {Kana}.
// Without script extensions only the first script in each set would be taken
// into account, resulting in 3 runs where 1 would be enough.
// TODO(ckocagil): Write a unit test for the case above.
int ScriptInterval(const base::string16& text,
                   size_t start,
                   size_t length,
                   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
// hb-icu. See http://crbug.com/356929
inline hb_script_t ICUScriptToHBScript(UScriptCode script) {
  if (script == USCRIPT_INVALID_CODE)
    return HB_SCRIPT_INVALID;
  return hb_script_from_string(uscript_getShortName(script), -1);
}

// Helper template function for |TextRunHarfBuzz::GetClusterAt()|. |Iterator|
// can be a forward or reverse iterator type depending on the text direction.
template <class Iterator>
void GetClusterAtImpl(size_t pos,
                      Range range,
                      Iterator elements_begin,
                      Iterator elements_end,
                      bool reversed,
                      Range* chars,
                      Range* glyphs) {
  Iterator element = std::upper_bound(elements_begin, elements_end, pos);
  chars->set_end(element == elements_end ? range.end() : *element);
  glyphs->set_end(reversed ? elements_end - element : element - elements_begin);

  DCHECK(element != elements_begin);
  while (--element != elements_begin && *element == *(element - 1));
  chars->set_start(*element);
  glyphs->set_start(
      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(size_t max_width,
                      int min_baseline,
                      float min_height,
                      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),
        word_wrap_behavior_(word_wrap_behavior),
        text_(text),
        words_(words),
        run_list_(run_list),
        max_descent_(0),
        max_ascent_(0),
        text_x_(0),
        available_width_(max_width_) {
    AdvanceLine();
  }

  // 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 = RangeF(SkScalarToFloat(text_x_),
                               SkScalarToFloat(text_x_) + 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();
      if (!word_segments.empty())
        AddWordToLine(word_segments);
      if (new_line)
        AdvanceLine();
    }
  }

  // Finishes line breaking and outputs the results. Can be called at most once.
  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];
  }

  // 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->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;
    available_width_ = max_width_;
    lines_.push_back(internal::Line());
  }

  // 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());
    DCHECK(!word_segments.empty());

    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);
          SkScalar 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.x_range = RangeF(SkScalarToFloat(text_x_),
                                         SkScalarToFloat(text_x_ + width));
            AddLineSegment(cut_segment);
            // Updates old segment range.
            remaining_segment.char_range.set_start(cutoff_pos);
            remaining_segment.x_range.set_start(SkScalarToFloat(text_x_));
          }
          if (has_truncated)
            break;
          if (!remaining_segment.char_range.is_empty())
            AdvanceLine();
        }
      }
    }
  }

  // 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_EQ(last_segment.char_range.end(), segment.char_range.start());
        DCHECK_LE(
            std::abs(last_segment.x_range.end() - segment.x_range.start()),
            std::numeric_limits<float>::epsilon());
        last_segment.char_range.set_end(segment.char_range.end());
        last_segment.x_range.set_end(SkScalarToFloat(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() + 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 (segment.char_range.end() == run.range.end())
        UpdateRTLSegmentRanges();
    }
    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++;
    }

    const size_t valid_end_pos = std::max(
        segment.char_range.start(),
        static_cast<uint32_t>(FindValidBoundaryBefore(text_, end_pos)));
    if (end_pos != valid_end_pos) {
      end_pos = valid_end_pos;
      width = run.GetGlyphWidthForCharRange(
          Range(segment.char_range.start(), end_pos));
    }

    // |max_width_| might be smaller than a single character. In this case we
    // need to put at least one character in the line. Note that, we should
    // not separate surrogate pair or combining characters.
    // See RenderTextTest.Multiline_MinWidth for an example.
    if (width == 0 && available_width_ == max_width_) {
      end_pos = std::min(
          segment.char_range.end(),
          static_cast<uint32_t>(FindValidBoundaryAfter(text_, end_pos + 1)));
    }

    return end_pos;
  }

  // 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.x_range = RangeF(SkScalarToFloat(text_x_ + width - char_width),
                               SkScalarToFloat(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 = RangeF(x, x + segment_width);
      x += segment_width;
    }
    rtl_segments_.clear();
  }

  const SkScalar max_width_;
  const int min_baseline_;
  const float min_height_;
  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_;

  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.
struct CaseInsensitiveCompare {
  bool operator() (const Font& a, const Font& b) const {
    return base::CompareCaseInsensitiveASCII(a.GetFontName(), b.GetFontName()) <
           0;
  }
};

}  // namespace

namespace internal {

TextRunHarfBuzz::TextRunHarfBuzz()
    : width(0.0f),
      preceding_run_widths(0.0f),
      is_rtl(false),
      level(0),
      script(USCRIPT_INVALID_CODE),
      glyph_count(static_cast<size_t>(-1)),
      font_size(0),
      baseline_offset(0),
      baseline_type(0),
      font_style(0),
      strike(false),
      diagonal_strike(false),
      underline(false) {
}

TextRunHarfBuzz::~TextRunHarfBuzz() {}

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);
  const float cluster_begin_x = positions[glyphs.start()].x();
  const float cluster_end_x = glyphs.end() < glyph_count ?
      positions[glyphs.end()].x() : SkFloatToScalar(width);

  // A cluster consists of a number of code points and corresponds to a number
  // of glyphs that should be drawn together. A cluster can contain multiple
  // graphemes. In order to place the cursor at a grapheme boundary inside the
  // cluster, we simply divide the cluster width by the number of graphemes.
  if (chars.length() > 1 && grapheme_iterator) {
    int before = 0;
    int total = 0;
    for (size_t i = chars.start(); i < chars.end(); ++i) {
      if (grapheme_iterator->IsGraphemeBoundary(i)) {
        if (i < text_index)
          ++before;
        ++total;
      }
    }
    DCHECK_GT(total, 0);
    if (total > 1) {
      if (is_rtl)
        before = total - before - 1;
      DCHECK_GE(before, 0);
      DCHECK_LT(before, total);
      const int cluster_width = cluster_end_x - cluster_begin_x;
      const int grapheme_begin_x = cluster_begin_x + static_cast<int>(0.5f +
          cluster_width * before / static_cast<float>(total));
      const int grapheme_end_x = cluster_begin_x + static_cast<int>(0.5f +
          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 {
  if (char_range.is_empty())
    return 0;

  DCHECK(range.Contains(char_range));
  Range glyph_range = CharRangeToGlyphRange(char_range);

  // The |glyph_range| might be empty or invalid on Windows if a multi-character
  // grapheme is divided into different runs (e.g., there are two font sizes or
  // colors for a single glyph). In this case it might cause the browser crash,
  // see crbug.com/526234.
  if (glyph_range.start() >= glyph_range.end()) {
    NOTREACHED() << "The glyph range is empty or invalid! Its char range: ["
        << char_range.start() << ", " << char_range.end()
        << "], and its glyph range: [" << glyph_range.start() << ", "
        << glyph_range.end() << "].";
    return 0;
  }

  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() {
  if (runs_.size() == 1) {
    visual_to_logical_ = logical_to_visual_ = std::vector<int32_t>(1, 0);
    return;
  }
  const size_t num_runs = runs_.size();
  std::vector<UBiDiLevel> levels(num_runs);
  for (size_t i = 0; i < num_runs; ++i)
    levels[i] = runs_[i]->level;
  visual_to_logical_.resize(num_runs);
  ubidi_reorderVisual(&levels[0], num_runs, &visual_to_logical_[0]);
  logical_to_visual_.resize(num_runs);
  ubidi_reorderLogical(&levels[0], num_runs, &logical_to_visual_[0]);
}

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

RenderTextHarfBuzz::~RenderTextHarfBuzz() {}

scoped_ptr<RenderText> RenderTextHarfBuzz::CreateInstanceOfSameType() const {
  return make_scoped_ptr(new RenderTextHarfBuzz);
}

bool RenderTextHarfBuzz::MultilineSupported() const {
  return true;
}

const base::string16& RenderTextHarfBuzz::GetDisplayText() {
  // TODO(oshima): Consider supporting eliding multi-line text.
  // This requires max_line support first.
  if (multiline() ||
      elide_behavior() == NO_ELIDE ||
      elide_behavior() == FADE_TAIL) {
    // Call UpdateDisplayText to clear |display_text_| and |text_elided_|
    // on the RenderText class.
    UpdateDisplayText(0);
    update_display_text_ = false;
    display_run_list_.reset();
    return layout_text();
  }

  EnsureLayoutRunList();
  DCHECK(!update_display_text_);
  return text_elided() ? display_text() : layout_text();
}

Size RenderTextHarfBuzz::GetStringSize() {
  const SizeF size_f = GetStringSizeF();
  return Size(std::ceil(size_f.width()), size_f.height());
}

SizeF RenderTextHarfBuzz::GetStringSizeF() {
  EnsureLayout();
  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);

  internal::TextRunList* run_list = GetRunList();
  if (run_index >= run_list->size())
    return EdgeSelectionModel((x < 0) ? CURSOR_LEFT : CURSOR_RIGHT);
  const internal::TextRunHarfBuzz& run = *run_list->runs()[run_index];
  for (size_t i = 0; i < run.glyph_count; ++i) {
    const SkScalar end =
        i + 1 == run.glyph_count ? run.width : run.positions[i + 1].x();
    const SkScalar middle = (end + run.positions[i].x()) / 2;

    if (offset < middle) {
      return SelectionModel(DisplayIndexToTextIndex(
          run.glyph_to_char[i] + (run.is_rtl ? 1 : 0)),
          (run.is_rtl ? CURSOR_BACKWARD : CURSOR_FORWARD));
    }
    if (offset < end) {
      return SelectionModel(DisplayIndexToTextIndex(
          run.glyph_to_char[i] + (run.is_rtl ? 0 : 1)),
          (run.is_rtl ? CURSOR_FORWARD : CURSOR_BACKWARD));
    }
  }
  return EdgeSelectionModel(CURSOR_RIGHT);
}

std::vector<RenderText::FontSpan> RenderTextHarfBuzz::GetFontSpansForTesting() {
  EnsureLayout();

  internal::TextRunList* run_list = GetRunList();
  std::vector<RenderText::FontSpan> spans;
  for (auto* run : run_list->runs()) {
    SkString family_name;
    run->skia_face->getFamilyName(&family_name);
    Font font(family_name.c_str(), run->font_size);
    spans.push_back(RenderText::FontSpan(
        font,
        Range(DisplayIndexToTextIndex(run->range.start()),
              DisplayIndexToTextIndex(run->range.end()))));
  }

  return spans;
}

Range RenderTextHarfBuzz::GetGlyphBounds(size_t index) {
  EnsureLayout();
  const size_t run_index =
      GetRunContainingCaret(SelectionModel(index, CURSOR_FORWARD));
  internal::TextRunList* run_list = GetRunList();
  // Return edge bounds if the index is invalid or beyond the layout text size.
  if (run_index >= run_list->size())
    return Range(GetStringSize().width());
  const size_t layout_index = TextIndexToDisplayIndex(index);
  internal::TextRunHarfBuzz* run = run_list->runs()[run_index];
  RangeF bounds =
      run->GetGraphemeBounds(GetGraphemeIterator(), layout_index);
  // If cursor is enabled, extend the last glyph up to the rightmost cursor
  // position since clients expect them to be contiguous.
  if (cursor_enabled() && run_index == run_list->size() - 1 &&
      index == (run->is_rtl ? run->range.start() : run->range.end() - 1))
    bounds.set_end(std::ceil(bounds.end()));
  return run->is_rtl ? RangeF(bounds.end(), bounds.start()).Round()
                     : bounds.Round();
}

int RenderTextHarfBuzz::GetDisplayTextBaseline() {
  EnsureLayout();
  return lines()[0].baseline;
}

SelectionModel RenderTextHarfBuzz::AdjacentCharSelectionModel(
    const SelectionModel& selection,
    VisualCursorDirection direction) {
  DCHECK(!update_display_run_list_);

  internal::TextRunList* run_list = GetRunList();
  internal::TextRunHarfBuzz* run;

  size_t run_index = GetRunContainingCaret(selection);
  if (run_index >= run_list->size()) {
    // The cursor is not in any run: we're at the visual and logical edge.
    SelectionModel edge = EdgeSelectionModel(direction);
    if (edge.caret_pos() == selection.caret_pos())
      return edge;
    int visual_index = (direction == CURSOR_RIGHT) ? 0 : run_list->size() - 1;
    run = run_list->runs()[run_list->visual_to_logical(visual_index)];
  } else {
    // If the cursor is moving within the current run, just move it by one
    // grapheme in the appropriate direction.
    run = run_list->runs()[run_index];
    size_t caret = selection.caret_pos();
    bool forward_motion = run->is_rtl == (direction == CURSOR_LEFT);
    if (forward_motion) {
      if (caret < DisplayIndexToTextIndex(run->range.end())) {
        caret = IndexOfAdjacentGrapheme(caret, CURSOR_FORWARD);
        return SelectionModel(caret, CURSOR_BACKWARD);
      }
    } else {
      if (caret > DisplayIndexToTextIndex(run->range.start())) {
        caret = IndexOfAdjacentGrapheme(caret, CURSOR_BACKWARD);
        return SelectionModel(caret, CURSOR_FORWARD);
      }
    }
    // The cursor is at the edge of a run; move to the visually adjacent run.
    int visual_index = run_list->logical_to_visual(run_index);
    visual_index += (direction == CURSOR_LEFT) ? -1 : 1;
    if (visual_index < 0 || visual_index >= static_cast<int>(run_list->size()))
      return EdgeSelectionModel(direction);
    run = run_list->runs()[run_list->visual_to_logical(visual_index)];
  }
  bool forward_motion = run->is_rtl == (direction == CURSOR_LEFT);
  return forward_motion ? FirstSelectionModelInsideRun(run) :
                          LastSelectionModelInsideRun(run);
}

SelectionModel RenderTextHarfBuzz::AdjacentWordSelectionModel(
    const SelectionModel& selection,
    VisualCursorDirection direction) {
  if (obscured())
    return EdgeSelectionModel(direction);

  base::i18n::BreakIterator iter(text(), base::i18n::BreakIterator::BREAK_WORD);
  bool success = iter.Init();
  DCHECK(success);
  if (!success)
    return selection;

  // Match OS specific word break behavior.
#if defined(OS_WIN)
  size_t pos;
  if (direction == CURSOR_RIGHT) {
    pos = std::min(selection.caret_pos() + 1, text().length());
    while (iter.Advance()) {
      pos = iter.pos();
      if (iter.IsWord() && pos > selection.caret_pos())
        break;
    }
  } else {  // direction == CURSOR_LEFT
    // Notes: We always iterate words from the beginning.
    // This is probably fast enough for our usage, but we may
    // want to modify WordIterator so that it can start from the
    // middle of string and advance backwards.
    pos = std::max<int>(selection.caret_pos() - 1, 0);
    while (iter.Advance()) {
      if (iter.IsWord()) {
        size_t begin = iter.pos() - iter.GetString().length();
        if (begin == selection.caret_pos()) {
          // The cursor is at the beginning of a word.
          // Move to previous word.
          break;
        } else if (iter.pos() >= selection.caret_pos()) {
          // The cursor is in the middle or at the end of a word.
          // Move to the top of current word.
          pos = begin;
          break;
        }
        pos = iter.pos() - iter.GetString().length();
      }
    }
  }
  return SelectionModel(pos, CURSOR_FORWARD);
#else
  internal::TextRunList* run_list = GetRunList();
  SelectionModel cur(selection);
  for (;;) {
    cur = AdjacentCharSelectionModel(cur, direction);
    size_t run = GetRunContainingCaret(cur);
    if (run == run_list->size())
      break;
    const bool is_forward =
        run_list->runs()[run]->is_rtl == (direction == CURSOR_LEFT);
    size_t cursor = cur.caret_pos();
    if (is_forward ? iter.IsEndOfWord(cursor) : iter.IsStartOfWord(cursor))
      break;
  }
  return cur;
#endif
}

std::vector<Rect> RenderTextHarfBuzz::GetSubstringBounds(const Range& range) {
  DCHECK(!update_display_run_list_);
  DCHECK(Range(0, text().length()).Contains(range));
  Range layout_range(TextIndexToDisplayIndex(range.start()),
                     TextIndexToDisplayIndex(range.end()));
  DCHECK(Range(0, GetDisplayText().length()).Contains(layout_range));

  std::vector<Rect> rects;
  if (layout_range.is_empty())
    return rects;
  std::vector<Range> bounds;

  internal::TextRunList* run_list = GetRunList();

  // Add a Range for each run/selection intersection.
  for (size_t i = 0; i < run_list->size(); ++i) {
    internal::TextRunHarfBuzz* run =
        run_list->runs()[run_list->visual_to_logical(i)];
    Range intersection = run->range.Intersect(layout_range);
    if (!intersection.IsValid())
      continue;
    DCHECK(!intersection.is_reversed());
    const size_t left_index =
        run->is_rtl ? intersection.end() - 1 : intersection.start();
    const Range leftmost_character_x =
        run->GetGraphemeBounds(GetGraphemeIterator(), left_index).Round();
    const size_t right_index =
        run->is_rtl ? intersection.start() : intersection.end() - 1;
    const Range rightmost_character_x =
        run->GetGraphemeBounds(GetGraphemeIterator(), right_index).Round();
    Range range_x(leftmost_character_x.start(), rightmost_character_x.end());
    DCHECK(!range_x.is_reversed());
    if (range_x.is_empty())
      continue;

    // Union this with the last range if they're adjacent.
    DCHECK(bounds.empty() || bounds.back().GetMax() <= range_x.GetMin());
    if (!bounds.empty() && bounds.back().GetMax() == range_x.GetMin()) {
      range_x = Range(bounds.back().GetMin(), range_x.GetMax());
      bounds.pop_back();
    }
    bounds.push_back(range_x);
  }
  for (Range& bound : bounds) {
    std::vector<Rect> current_rects = TextBoundsToViewBounds(bound);
    rects.insert(rects.end(), current_rects.begin(), current_rects.end());
  }
  return rects;
}

size_t RenderTextHarfBuzz::TextIndexToDisplayIndex(size_t index) {
  return TextIndexToGivenTextIndex(GetDisplayText(), index);
}

size_t RenderTextHarfBuzz::DisplayIndexToTextIndex(size_t index) {
  if (!obscured())
    return index;
  const size_t text_index = UTF16OffsetToIndex(text(), 0, index);
  DCHECK_LE(text_index, text().length());
  return text_index;
}

bool RenderTextHarfBuzz::IsValidCursorIndex(size_t index) {
  if (index == 0 || index == text().length())
    return true;
  if (!IsValidLogicalIndex(index))
    return false;
  base::i18n::BreakIterator* grapheme_iterator = GetGraphemeIterator();
  return !grapheme_iterator || grapheme_iterator->IsGraphemeBoundary(index);
}

void RenderTextHarfBuzz::OnLayoutTextAttributeChanged(bool text_changed) {
  update_layout_run_list_ = true;
  OnDisplayTextAttributeChanged();
}

void RenderTextHarfBuzz::OnDisplayTextAttributeChanged() {
  update_display_text_ = true;
  update_grapheme_iterator_ = true;
}

void RenderTextHarfBuzz::EnsureLayout() {
  EnsureLayoutRunList();

  if (update_display_run_list_) {
    DCHECK(text_elided());
    const base::string16& display_text = GetDisplayText();
    display_run_list_.reset(new internal::TextRunList);

    if (!display_text.empty()) {
      TRACE_EVENT0("ui", "RenderTextHarfBuzz:EnsureLayout1");

      ItemizeTextToRuns(display_text, display_run_list_.get());

      // TODO(ckocagil): Remove ScopedTracker below once crbug.com/441028 is
      // fixed.
      tracked_objects::ScopedTracker tracking_profile(
          FROM_HERE_WITH_EXPLICIT_FUNCTION("441028 ShapeRunList() 1"));
      ShapeRunList(display_text, display_run_list_.get());
    }
    update_display_run_list_ = false;

    std::vector<internal::Line> empty_lines;
    set_lines(&empty_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()),
        word_wrap_behavior(), GetDisplayText(),
        multiline() ? &GetLineBreaks() : nullptr, *run_list);

    tracking_profile.reset();

    if (multiline())
      line_breaker.ConstructMultiLines();
    else
      line_breaker.ConstructSingleLine();
    std::vector<internal::Line> lines;
    line_breaker.FinalizeLines(&lines, &total_size_);
    set_lines(&lines);
  }
}

void RenderTextHarfBuzz::DrawVisualText(internal::SkiaTextRenderer* renderer) {
  DCHECK(!update_layout_run_list_);
  DCHECK(!update_display_run_list_);
  DCHECK(!update_display_text_);
  if (lines().empty())
    return;

  ApplyFadeEffects(renderer);
  ApplyTextShadows(renderer);
  ApplyCompositionAndSelectionStyles();

  internal::TextRunList* run_list = GetRunList();
  for (size_t i = 0; i < lines().size(); ++i) {
    const internal::Line& line = lines()[i];
    const Vector2d origin = GetLineOffset(i) + Vector2d(0, line.baseline);
    SkScalar preceding_segment_widths = 0;
    for (const internal::LineSegment& segment : line.segments) {
      const internal::TextRunHarfBuzz& run = *run_list->runs()[segment.run];
      renderer->SetTypeface(run.skia_face.get());
      renderer->SetTextSize(SkIntToScalar(run.font_size));
      renderer->SetFontRenderParams(run.render_params,
                                    subpixel_rendering_suppressed());
      Range glyphs_range = run.CharRangeToGlyphRange(segment.char_range);
      scoped_ptr<SkPoint[]> positions(new SkPoint[glyphs_range.length()]);
      SkScalar offset_x = preceding_segment_widths -
                          ((glyphs_range.GetMin() != 0)
                               ? run.positions[glyphs_range.GetMin()].x()
                               : 0);
      for (size_t j = 0; j < glyphs_range.length(); ++j) {
        positions[j] = run.positions[(glyphs_range.is_reversed()) ?
                                     (glyphs_range.start() - j) :
                                     (glyphs_range.start() + j)];
        positions[j].offset(SkIntToScalar(origin.x()) + offset_x,
                            SkIntToScalar(origin.y() + run.baseline_offset));
      }
      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;

        renderer->SetForegroundColor(it->second);
        renderer->DrawPosText(
            &positions[colored_glyphs.start() - glyphs_range.start()],
            &run.glyphs[colored_glyphs.start()], colored_glyphs.length());
        int start_x = SkScalarRoundToInt(
            positions[colored_glyphs.start() - glyphs_range.start()].x());
        int end_x = SkScalarRoundToInt(
            (colored_glyphs.end() == glyphs_range.end())
                ? (SkFloatToScalar(segment.width()) + preceding_segment_widths +
                   SkIntToScalar(origin.x()))
                : positions[colored_glyphs.end() - glyphs_range.start()].x());
        renderer->DrawDecorations(start_x, origin.y(), end_x - start_x,
                                  run.underline, run.strike,
                                  run.diagonal_strike);
      }
      preceding_segment_widths += SkFloatToScalar(segment.width());
    }
  }

  renderer->EndDiagonalStrike();

  UndoCompositionAndSelectionStyles();
}

size_t RenderTextHarfBuzz::GetRunContainingCaret(
    const SelectionModel& caret) {
  DCHECK(!update_display_run_list_);
  size_t layout_position = TextIndexToDisplayIndex(caret.caret_pos());
  LogicalCursorDirection affinity = caret.caret_affinity();
  internal::TextRunList* run_list = GetRunList();
  for (size_t i = 0; i < run_list->size(); ++i) {
    internal::TextRunHarfBuzz* run = run_list->runs()[i];
    if (RangeContainsCaret(run->range, layout_position, affinity))
      return i;
  }
  return run_list->size();
}

size_t RenderTextHarfBuzz::GetRunContainingXCoord(float x,
                                                  float* offset) const {
  DCHECK(!update_display_run_list_);
  const internal::TextRunList* run_list = GetRunList();
  if (x < 0)
    return run_list->size();
  // Find the text run containing the argument point (assumed already offset).
  float current_x = 0;
  for (size_t i = 0; i < run_list->size(); ++i) {
    size_t run = run_list->visual_to_logical(i);
    current_x += run_list->runs()[run]->width;
    if (x < current_x) {
      *offset = x - (current_x - run_list->runs()[run]->width);
      return run;
    }
  }
  return run_list->size();
}

SelectionModel RenderTextHarfBuzz::FirstSelectionModelInsideRun(
    const internal::TextRunHarfBuzz* run) {
  size_t position = DisplayIndexToTextIndex(run->range.start());
  position = IndexOfAdjacentGrapheme(position, CURSOR_FORWARD);
  return SelectionModel(position, CURSOR_BACKWARD);
}

SelectionModel RenderTextHarfBuzz::LastSelectionModelInsideRun(
    const internal::TextRunHarfBuzz* run) {
  size_t position = DisplayIndexToTextIndex(run->range.end());
  position = IndexOfAdjacentGrapheme(position, CURSOR_BACKWARD);
  return SelectionModel(position, CURSOR_FORWARD);
}

void RenderTextHarfBuzz::ItemizeTextToRuns(
    const base::string16& text,
    internal::TextRunList* run_list_out) {
  DCHECK_NE(0U, text.length());

  // If ICU fails to itemize the text, we create a run that spans the entire
  // text. This is needed because leaving the runs set empty causes some clients
  // to misbehave since they expect non-zero text metrics from a non-empty text.
  base::i18n::BiDiLineIterator bidi_iterator;
  if (!bidi_iterator.Open(text, GetTextDirection(text))) {
    internal::TextRunHarfBuzz* run = new internal::TextRunHarfBuzz;
    run->range = Range(0, text.length());
    run_list_out->add(run);
    run_list_out->InitIndexMap();
    return;
  }

  // Temporarily apply composition underlines and selection colors.
  ApplyCompositionAndSelectionStyles();

  // Build the run list from the script items and ranged styles and baselines.
  // Use an empty color BreakList to avoid breaking runs at color boundaries.
  BreakList<SkColor> empty_colors;
  empty_colors.SetMax(text.length());
  DCHECK_LE(text.size(), baselines().max());
  for (const BreakList<bool>& style : styles())
    DCHECK_LE(text.size(), style.max());
  internal::StyleIterator style(empty_colors, baselines(), styles());

  for (size_t run_break = 0; run_break < text.length();) {
    internal::TextRunHarfBuzz* run = new internal::TextRunHarfBuzz;
    run->range.set_start(run_break);
    run->font_style = (style.style(BOLD) ? Font::BOLD : 0) |
                      (style.style(ITALIC) ? Font::ITALIC : 0);
    run->baseline_type = style.baseline();
    run->strike = style.style(STRIKE);
    run->diagonal_strike = style.style(DIAGONAL_STRIKE);
    run->underline = style.style(UNDERLINE);
    int32_t script_item_break = 0;
    bidi_iterator.GetLogicalRun(run_break, &script_item_break, &run->level);
    CHECK_GT(static_cast<size_t>(script_item_break), run_break);
    // Odd BiDi embedding levels correspond to RTL runs.
    run->is_rtl = (run->level % 2) == 1;
    // Find the length and script of this script run.
    script_item_break = ScriptInterval(text, run_break,
        script_item_break - run_break, &run->script) + run_break;

    // Find the next break and advance the iterators as needed.
    const size_t new_run_break = std::min(
        static_cast<size_t>(script_item_break),
        TextIndexToGivenTextIndex(text, style.GetRange().end()));
    CHECK_GT(new_run_break, run_break)
        << "It must proceed! " << text << " " << run_break;
    run_break = new_run_break;

    // Break runs at certain characters that need to be rendered separately to
    // prevent either an unusual character from forcing a fallback font on the
    // entire run, or brackets from being affected by a fallback font.
    // http://crbug.com/278913, http://crbug.com/396776
    if (run_break > run->range.start())
      run_break = FindRunBreakingCharacter(text, run->range.start(), run_break);

    DCHECK(IsValidCodePointIndex(text, run_break));
    style.UpdatePosition(DisplayIndexToTextIndex(run_break));
    run->range.set_end(run_break);

    run_list_out->add(run);
  }

  // Undo the temporarily applied composition underlines and selection colors.
  UndoCompositionAndSelectionStyles();

  run_list_out->InitIndexMap();
}

bool RenderTextHarfBuzz::CompareFamily(
    const base::string16& text,
    const Font& font,
    const gfx::FontRenderParams& render_params,
    internal::TextRunHarfBuzz* run,
    Font* best_font,
    gfx::FontRenderParams* best_render_params,
    size_t* best_missing_glyphs) {
  if (!ShapeRunWithFont(text, font, render_params, run))
    return false;

  const size_t missing_glyphs = run->CountMissingGlyphs();
  if (missing_glyphs < *best_missing_glyphs) {
    *best_font = font;
    *best_render_params = render_params;
    *best_missing_glyphs = missing_glyphs;
  }
  return missing_glyphs == 0;
}

void RenderTextHarfBuzz::ShapeRunList(const base::string16& text,
                                      internal::TextRunList* run_list) {
  for (auto* run : run_list->runs())
    ShapeRun(text, run);
  run_list->ComputePrecedingRunWidths();
}

void RenderTextHarfBuzz::ShapeRun(const base::string16& text,
                                  internal::TextRunHarfBuzz* run) {
  const Font& primary_font = font_list().GetPrimaryFont();
  const std::string primary_family = primary_font.GetFontName();
  run->font_size = primary_font.GetFontSize();
  run->baseline_offset = 0;
  if (run->baseline_type != NORMAL_BASELINE) {
    // Calculate a slightly smaller font. The ratio here is somewhat arbitrary.
    // Proportions from 5/9 to 5/7 all look pretty good.
    const float ratio = 5.0f / 9.0f;
    run->font_size = gfx::ToRoundedInt(primary_font.GetFontSize() * ratio);
    switch (run->baseline_type) {
      case SUPERSCRIPT:
        run->baseline_offset =
            primary_font.GetCapHeight() - primary_font.GetHeight();
        break;
      case SUPERIOR:
        run->baseline_offset =
            gfx::ToRoundedInt(primary_font.GetCapHeight() * ratio) -
            primary_font.GetCapHeight();
        break;
      case SUBSCRIPT:
        run->baseline_offset =
            primary_font.GetHeight() - primary_font.GetBaseline();
        break;
      case INFERIOR:  // Fall through.
      default:
        break;
    }
  }

  Font best_font;
  FontRenderParams best_render_params;
  size_t best_missing_glyphs = std::numeric_limits<size_t>::max();

  for (const Font& font : font_list().GetFonts()) {
    if (CompareFamily(text, font, font.GetFontRenderParams(), run, &best_font,
                      &best_render_params, &best_missing_glyphs))
      return;
  }

#if defined(OS_WIN)
  Font uniscribe_font;
  std::string uniscribe_family;
  const base::char16* run_text = &(text[run->range.start()]);
  if (GetUniscribeFallbackFont(primary_font, run_text, run->range.length(),
                               &uniscribe_font)) {
    uniscribe_family = uniscribe_font.GetFontName();
    if (CompareFamily(text, uniscribe_font,
                      uniscribe_font.GetFontRenderParams(), run,
                      &best_font, &best_render_params, &best_missing_glyphs))
      return;
  }
#endif

  std::vector<Font> fallback_font_list = GetFallbackFonts(primary_font);

#if defined(OS_WIN)
  // Append fonts in the fallback list of the Uniscribe font.
  if (!uniscribe_family.empty()) {
    std::vector<Font> uniscribe_fallbacks = GetFallbackFonts(uniscribe_font);
    fallback_font_list.insert(fallback_font_list.end(),
        uniscribe_fallbacks.begin(), uniscribe_fallbacks.end());
  }

  // Add Segoe UI and its associated linked fonts to the fallback font list to
  // ensure that the fallback list covers the basic cases.
  // http://crbug.com/467459. On some Windows configurations the default font
  // could be a raster font like System, which would not give us a reasonable
  // fallback font list.
  if (!base::LowerCaseEqualsASCII(primary_font.GetFontName(), "segoe ui") &&
      !base::LowerCaseEqualsASCII(uniscribe_family, "segoe ui")) {
    std::vector<Font> default_fallback_families =
        GetFallbackFonts(Font("Segoe UI", 13));
    fallback_font_list.insert(fallback_font_list.end(),
        default_fallback_families.begin(), default_fallback_families.end());
  }
#endif

  // Use a set to track the fallback fonts and avoid duplicate entries.
  std::set<Font, CaseInsensitiveCompare> fallback_fonts;

  // Try shaping with the fallback fonts.
  for (const auto& font : fallback_font_list) {
    std::string font_name = font.GetFontName();

    if (font_name == primary_font.GetFontName())
      continue;
#if defined(OS_WIN)
    if (font_name == uniscribe_family)
      continue;
#endif
    if (fallback_fonts.find(font) != fallback_fonts.end())
      continue;

    fallback_fonts.insert(font);

    FontRenderParamsQuery query;
    query.families.push_back(font_name);
    query.pixel_size = run->font_size;
    query.style = run->font_style;
    FontRenderParams fallback_render_params = GetFontRenderParams(query, NULL);
    if (CompareFamily(text, font, fallback_render_params, run, &best_font,
                      &best_render_params, &best_missing_glyphs))
      return;
  }

  if (best_missing_glyphs != std::numeric_limits<size_t>::max() &&
      (best_font.GetFontName() == run->font.GetFontName() ||
       ShapeRunWithFont(text, best_font, best_render_params, run)))
    return;

  run->glyph_count = 0;
  run->width = 0.0f;
}

bool RenderTextHarfBuzz::ShapeRunWithFont(const base::string16& text,
                                          const gfx::Font& font,
                                          const FontRenderParams& params,
                                          internal::TextRunHarfBuzz* run) {
  skia::RefPtr<SkTypeface> skia_face =
      internal::CreateSkiaTypeface(font, run->font_style);
  if (skia_face == NULL)
    return false;
  run->skia_face = skia_face;
  run->font = font;
  run->render_params = params;

  hb_font_t* harfbuzz_font = CreateHarfBuzzFont(
      run->skia_face.get(), SkIntToScalar(run->font_size), run->render_params,
      subpixel_rendering_suppressed());

  // Create a HarfBuzz buffer and add the string to be shaped. The HarfBuzz
  // buffer holds our text, run information to be used by the shaping engine,
  // and the resulting glyph data.
  hb_buffer_t* buffer = hb_buffer_create();
  hb_buffer_add_utf16(buffer, reinterpret_cast<const uint16_t*>(text.c_str()),
                      text.length(), run->range.start(), run->range.length());
  hb_buffer_set_script(buffer, ICUScriptToHBScript(run->script));
  hb_buffer_set_direction(buffer,
      run->is_rtl ? HB_DIRECTION_RTL : HB_DIRECTION_LTR);
  // TODO(ckocagil): Should we determine the actual language?
  hb_buffer_set_language(buffer, hb_language_get_default());

  {
    // TODO(ckocagil): Remove ScopedTracker below once crbug.com/441028 is
    // fixed.
    tracked_objects::ScopedTracker tracking_profile(
        FROM_HERE_WITH_EXPLICIT_FUNCTION("441028 hb_shape()"));

    // Shape the text.
    hb_shape(harfbuzz_font, buffer, NULL, 0);
  }

  // Populate the run fields with the resulting glyph data in the buffer.
  unsigned int glyph_count = 0;
  hb_glyph_info_t* infos = hb_buffer_get_glyph_infos(buffer, &glyph_count);
  run->glyph_count = glyph_count;
  hb_glyph_position_t* hb_positions =
      hb_buffer_get_glyph_positions(buffer, NULL);
  run->glyphs.reset(new uint16_t[run->glyph_count]);
  run->glyph_to_char.resize(run->glyph_count);
  run->positions.reset(new SkPoint[run->glyph_count]);
  run->width = 0.0f;

  for (size_t i = 0; i < run->glyph_count; ++i) {
    DCHECK_LE(infos[i].codepoint, std::numeric_limits<uint16_t>::max());
    run->glyphs[i] = static_cast<uint16_t>(infos[i].codepoint);
    run->glyph_to_char[i] = infos[i].cluster;
    const SkScalar x_offset =
        HarfBuzzUnitsToSkiaScalar(hb_positions[i].x_offset);
    const SkScalar y_offset =
        HarfBuzzUnitsToSkiaScalar(hb_positions[i].y_offset);
    run->positions[i].set(run->width + x_offset, -y_offset);
    run->width += (glyph_width_for_test_ > 0)
                      ? glyph_width_for_test_
                      : HarfBuzzUnitsToFloat(hb_positions[i].x_advance);
    // Round run widths if subpixel positioning is off to match native behavior.
    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;
}

void RenderTextHarfBuzz::EnsureLayoutRunList() {
  if (update_layout_run_list_) {
    layout_run_list_.Reset();

    const base::string16& text = layout_text();
    if (!text.empty()) {
      TRACE_EVENT0("ui", "RenderTextHarfBuzz:EnsureLayoutRunList");
      ItemizeTextToRuns(text, &layout_run_list_);

      // TODO(ckocagil): Remove ScopedTracker below once crbug.com/441028 is
      // fixed.
      tracked_objects::ScopedTracker tracking_profile(
          FROM_HERE_WITH_EXPLICIT_FUNCTION("441028 ShapeRunList() 2"));
      ShapeRunList(text, &layout_run_list_);
    }

    std::vector<internal::Line> empty_lines;
    set_lines(&empty_lines);
    display_run_list_.reset();
    update_display_text_ = true;
    update_layout_run_list_ = false;
  }
  if (update_display_text_) {
    UpdateDisplayText(multiline() ? 0 : layout_run_list_.width());
    update_display_text_ = false;
    update_display_run_list_ = text_elided();
  }
}

base::i18n::BreakIterator* RenderTextHarfBuzz::GetGraphemeIterator() {
  if (update_grapheme_iterator_) {
    update_grapheme_iterator_ = false;
    grapheme_iterator_.reset(new base::i18n::BreakIterator(
        GetDisplayText(),
        base::i18n::BreakIterator::BREAK_CHARACTER));
    if (!grapheme_iterator_->Init())
      grapheme_iterator_.reset();
  }
  return grapheme_iterator_.get();
}

internal::TextRunList* RenderTextHarfBuzz::GetRunList() {
  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