ui/gfx/render_text_harfbuzz.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "ui/gfx/render_text_harfbuzz.h"
   6
   7 #include <limits>
   8 #include <map>
   9
  10 #include "base/i18n/bidi_line_iterator.h"
  11 #include "base/i18n/break_iterator.h"
  12 #include "base/i18n/char_iterator.h"
  13 #include "base/lazy_instance.h"
  14 #include "base/profiler/scoped_tracker.h"
  15 #include "third_party/harfbuzz-ng/src/hb.h"
  16 #include "third_party/icu/source/common/unicode/ubidi.h"
  17 #include "third_party/skia/include/core/SkColor.h"
  18 #include "third_party/skia/include/core/SkTypeface.h"
  19 #include "ui/gfx/canvas.h"
  20 #include "ui/gfx/font_fallback.h"
  21 #include "ui/gfx/font_render_params.h"
  22 #include "ui/gfx/utf16_indexing.h"
  23
  24 #if defined(OS_WIN)
  25 #include "ui/gfx/font_fallback_win.h"
  26 #endif
  27
  28 using gfx::internal::RangeF;
  29 using gfx::internal::RoundRangeF;
  30
  31 namespace gfx {
  32
  33 namespace {
  34
  35 // Text length limit. Longer strings are slow and not fully tested.
  36 const size_t kMaxTextLength = 10000;
  37
  38 // The maximum number of scripts a Unicode character can belong to. This value
  39 // is arbitrarily chosen to be a good limit because it is unlikely for a single
  40 // character to belong to more scripts.
  41 const size_t kMaxScripts = 5;
  42
  43 // Maps from code points to glyph indices in a font.
  44 typedef std::map<uint32_t, uint16_t> GlyphCache;
  45
  46 // Font data provider for HarfBuzz using Skia. Copied from Blink.
  47 // TODO(ckocagil): Eliminate the duplication. http://crbug.com/368375
  48 struct FontData {
  49   FontData(GlyphCache* glyph_cache) : glyph_cache_(glyph_cache) {}
  50
  51   SkPaint paint_;
  52   GlyphCache* glyph_cache_;
  53 };
  54
  55 hb_position_t SkiaScalarToHarfBuzzPosition(SkScalar value) {
  56   return SkScalarToFixed(value);
  57 }
  58
  59 // Deletes the object at the given pointer after casting it to the given type.
  60 template<typename Type>
  61 void DeleteByType(void* data) {
  62   Type* typed_data = reinterpret_cast<Type*>(data);
  63   delete typed_data;
  64 }
  65
  66 template<typename Type>
  67 void DeleteArrayByType(void* data) {
  68   Type* typed_data = reinterpret_cast<Type*>(data);
  69   delete[] typed_data;
  70 }
  71
  72 // Outputs the |width| and |extents| of the glyph with index |codepoint| in
  73 // |paint|'s font.
  74 void GetGlyphWidthAndExtents(SkPaint* paint,
  75                              hb_codepoint_t codepoint,
  76                              hb_position_t* width,
  77                              hb_glyph_extents_t* extents) {
  78   DCHECK_LE(codepoint, std::numeric_limits<uint16>::max());
  79   paint->setTextEncoding(SkPaint::kGlyphID_TextEncoding);
  80
  81   SkScalar sk_width;
  82   SkRect sk_bounds;
  83   uint16_t glyph = static_cast<uint16_t>(codepoint);
  84
  85   paint->getTextWidths(&glyph, sizeof(glyph), &sk_width, &sk_bounds);
  86   if (width)
  87     *width = SkiaScalarToHarfBuzzPosition(sk_width);
  88   if (extents) {
  89     // Invert y-axis because Skia is y-grows-down but we set up HarfBuzz to be
  90     // y-grows-up.
  91     extents->x_bearing = SkiaScalarToHarfBuzzPosition(sk_bounds.fLeft);
  92     extents->y_bearing = SkiaScalarToHarfBuzzPosition(-sk_bounds.fTop);
  93     extents->width = SkiaScalarToHarfBuzzPosition(sk_bounds.width());
  94     extents->height = SkiaScalarToHarfBuzzPosition(-sk_bounds.height());
  95   }
  96 }
  97
  98 // Writes the |glyph| index for the given |unicode| code point. Returns whether
  99 // the glyph exists, i.e. it is not a missing glyph.
 100 hb_bool_t GetGlyph(hb_font_t* font,
 101                    void* data,
 102                    hb_codepoint_t unicode,
 103                    hb_codepoint_t variation_selector,
 104                    hb_codepoint_t* glyph,
 105                    void* user_data) {
 106   FontData* font_data = reinterpret_cast<FontData*>(data);
 107   GlyphCache* cache = font_data->glyph_cache_;
 108
 109   bool exists = cache->count(unicode) != 0;
 110   if (!exists) {
 111     SkPaint* paint = &font_data->paint_;
 112     paint->setTextEncoding(SkPaint::kUTF32_TextEncoding);
 113     paint->textToGlyphs(&unicode, sizeof(hb_codepoint_t), &(*cache)[unicode]);
 114   }
 115   *glyph = (*cache)[unicode];
 116   return !!*glyph;
 117 }
 118
 119 // Returns the horizontal advance value of the |glyph|.
 120 hb_position_t GetGlyphHorizontalAdvance(hb_font_t* font,
 121                                         void* data,
 122                                         hb_codepoint_t glyph,
 123                                         void* user_data) {
 124   FontData* font_data = reinterpret_cast<FontData*>(data);
 125   hb_position_t advance = 0;
 126
 127   GetGlyphWidthAndExtents(&font_data->paint_, glyph, &advance, 0);
 128   return advance;
 129 }
 130
 131 hb_bool_t GetGlyphHorizontalOrigin(hb_font_t* font,
 132                                    void* data,
 133                                    hb_codepoint_t glyph,
 134                                    hb_position_t* x,
 135                                    hb_position_t* y,
 136                                    void* user_data) {
 137   // Just return true, like the HarfBuzz-FreeType implementation.
 138   return true;
 139 }
 140
 141 hb_position_t GetGlyphKerning(FontData* font_data,
 142                               hb_codepoint_t first_glyph,
 143                               hb_codepoint_t second_glyph) {
 144   SkTypeface* typeface = font_data->paint_.getTypeface();
 145   const uint16_t glyphs[2] = { static_cast<uint16_t>(first_glyph),
 146                                static_cast<uint16_t>(second_glyph) };
 147   int32_t kerning_adjustments[1] = { 0 };
 148
 149   if (!typeface->getKerningPairAdjustments(glyphs, 2, kerning_adjustments))
 150     return 0;
 151
 152   SkScalar upm = SkIntToScalar(typeface->getUnitsPerEm());
 153   SkScalar size = font_data->paint_.getTextSize();
 154   return SkiaScalarToHarfBuzzPosition(
 155       SkScalarMulDiv(SkIntToScalar(kerning_adjustments[0]), size, upm));
 156 }
 157
 158 hb_position_t GetGlyphHorizontalKerning(hb_font_t* font,
 159                                         void* data,
 160                                         hb_codepoint_t left_glyph,
 161                                         hb_codepoint_t right_glyph,
 162                                         void* user_data) {
 163   FontData* font_data = reinterpret_cast<FontData*>(data);
 164   if (font_data->paint_.isVerticalText()) {
 165     // We don't support cross-stream kerning.
 166     return 0;
 167   }
 168
 169   return GetGlyphKerning(font_data, left_glyph, right_glyph);
 170 }
 171
 172 hb_position_t GetGlyphVerticalKerning(hb_font_t* font,
 173                                       void* data,
 174                                       hb_codepoint_t top_glyph,
 175                                       hb_codepoint_t bottom_glyph,
 176                                       void* user_data) {
 177   FontData* font_data = reinterpret_cast<FontData*>(data);
 178   if (!font_data->paint_.isVerticalText()) {
 179     // We don't support cross-stream kerning.
 180     return 0;
 181   }
 182
 183   return GetGlyphKerning(font_data, top_glyph, bottom_glyph);
 184 }
 185
 186 // Writes the |extents| of |glyph|.
 187 hb_bool_t GetGlyphExtents(hb_font_t* font,
 188                           void* data,
 189                           hb_codepoint_t glyph,
 190                           hb_glyph_extents_t* extents,
 191                           void* user_data) {
 192   FontData* font_data = reinterpret_cast<FontData*>(data);
 193
 194   GetGlyphWidthAndExtents(&font_data->paint_, glyph, 0, extents);
 195   return true;
 196 }
 197
 198 class FontFuncs {
 199  public:
 200   FontFuncs() : font_funcs_(hb_font_funcs_create()) {
 201     hb_font_funcs_set_glyph_func(font_funcs_, GetGlyph, 0, 0);
 202     hb_font_funcs_set_glyph_h_advance_func(
 203         font_funcs_, GetGlyphHorizontalAdvance, 0, 0);
 204     hb_font_funcs_set_glyph_h_kerning_func(
 205         font_funcs_, GetGlyphHorizontalKerning, 0, 0);
 206     hb_font_funcs_set_glyph_h_origin_func(
 207         font_funcs_, GetGlyphHorizontalOrigin, 0, 0);
 208     hb_font_funcs_set_glyph_v_kerning_func(
 209         font_funcs_, GetGlyphVerticalKerning, 0, 0);
 210     hb_font_funcs_set_glyph_extents_func(
 211         font_funcs_, GetGlyphExtents, 0, 0);
 212     hb_font_funcs_make_immutable(font_funcs_);
 213   }
 214
 215   ~FontFuncs() {
 216     hb_font_funcs_destroy(font_funcs_);
 217   }
 218
 219   hb_font_funcs_t* get() { return font_funcs_; }
 220
 221  private:
 222   hb_font_funcs_t* font_funcs_;
 223
 224   DISALLOW_COPY_AND_ASSIGN(FontFuncs);
 225 };
 226
 227 base::LazyInstance<FontFuncs>::Leaky g_font_funcs = LAZY_INSTANCE_INITIALIZER;
 228
 229 // Returns the raw data of the font table |tag|.
 230 hb_blob_t* GetFontTable(hb_face_t* face, hb_tag_t tag, void* user_data) {
 231   SkTypeface* typeface = reinterpret_cast<SkTypeface*>(user_data);
 232
 233   const size_t table_size = typeface->getTableSize(tag);
 234   if (!table_size)
 235     return 0;
 236
 237   scoped_ptr<char[]> buffer(new char[table_size]);
 238   if (!buffer)
 239     return 0;
 240   size_t actual_size = typeface->getTableData(tag, 0, table_size, buffer.get());
 241   if (table_size != actual_size)
 242     return 0;
 243
 244   char* buffer_raw = buffer.release();
 245   return hb_blob_create(buffer_raw, table_size, HB_MEMORY_MODE_WRITABLE,
 246                         buffer_raw, DeleteArrayByType<char>);
 247 }
 248
 249 void UnrefSkTypeface(void* data) {
 250   SkTypeface* skia_face = reinterpret_cast<SkTypeface*>(data);
 251   SkSafeUnref(skia_face);
 252 }
 253
 254 // Wrapper class for a HarfBuzz face created from a given Skia face.
 255 class HarfBuzzFace {
 256  public:
 257   HarfBuzzFace() : face_(NULL) {}
 258
 259   ~HarfBuzzFace() {
 260     if (face_)
 261       hb_face_destroy(face_);
 262   }
 263
 264   void Init(SkTypeface* skia_face) {
 265     SkSafeRef(skia_face);
 266     face_ = hb_face_create_for_tables(GetFontTable, skia_face, UnrefSkTypeface);
 267     DCHECK(face_);
 268   }
 269
 270   hb_face_t* get() {
 271     return face_;
 272   }
 273
 274  private:
 275   hb_face_t* face_;
 276 };
 277
 278 // Creates a HarfBuzz font from the given Skia face and text size.
 279 hb_font_t* CreateHarfBuzzFont(SkTypeface* skia_face,
 280                               SkScalar text_size,
 281                               const FontRenderParams& params,
 282                               bool background_is_transparent) {
 283   typedef std::pair<HarfBuzzFace, GlyphCache> FaceCache;
 284
 285   // TODO(ckocagil): This shouldn't grow indefinitely. Maybe use base::MRUCache?
 286   static std::map<SkFontID, FaceCache> face_caches;
 287
 288   FaceCache* face_cache = &face_caches[skia_face->uniqueID()];
 289   if (face_cache->first.get() == NULL)
 290     face_cache->first.Init(skia_face);
 291
 292   hb_font_t* harfbuzz_font = hb_font_create(face_cache->first.get());
 293   const int scale = SkScalarToFixed(text_size);
 294   hb_font_set_scale(harfbuzz_font, scale, scale);
 295   FontData* hb_font_data = new FontData(&face_cache->second);
 296   hb_font_data->paint_.setTypeface(skia_face);
 297   hb_font_data->paint_.setTextSize(text_size);
 298   // TODO(ckocagil): Do we need to update these params later?
 299   internal::ApplyRenderParams(params, background_is_transparent,
 300                               &hb_font_data->paint_);
 301   hb_font_set_funcs(harfbuzz_font, g_font_funcs.Get().get(), hb_font_data,
 302                     DeleteByType<FontData>);
 303   hb_font_make_immutable(harfbuzz_font);
 304   return harfbuzz_font;
 305 }
 306
 307 // Returns true if characters of |block_code| may trigger font fallback.
 308 // Dingbats and emoticons can be rendered through the color emoji font file,
 309 // therefore it needs to be trigerred as fallbacks. See crbug.com/448909
 310 bool IsUnusualBlockCode(UBlockCode block_code) {
 311   return block_code == UBLOCK_GEOMETRIC_SHAPES ||
 312          block_code == UBLOCK_MISCELLANEOUS_SYMBOLS ||
 313          block_code == UBLOCK_DINGBATS ||
 314          block_code == UBLOCK_EMOTICONS;
 315 }
 316
 317 bool IsBracket(UChar32 character) {
 318   static const char kBrackets[] = { '(', ')', '{', '}', '<', '>', };
 319   static const char* kBracketsEnd = kBrackets + arraysize(kBrackets);
 320   return std::find(kBrackets, kBracketsEnd, character) != kBracketsEnd;
 321 }
 322
 323 // Returns the boundary between a special and a regular character. Special
 324 // characters are brackets or characters that satisfy |IsUnusualBlockCode|.
 325 size_t FindRunBreakingCharacter(const base::string16& text,
 326                                 size_t run_start,
 327                                 size_t run_break) {
 328   const int32 run_length = static_cast<int32>(run_break - run_start);
 329   base::i18n::UTF16CharIterator iter(text.c_str() + run_start, run_length);
 330   const UChar32 first_char = iter.get();
 331   const UBlockCode first_block = ublock_getCode(first_char);
 332   const bool first_block_unusual = IsUnusualBlockCode(first_block);
 333   const bool first_bracket = IsBracket(first_char);
 334
 335   while (iter.Advance() && iter.array_pos() < run_length) {
 336     const UChar32 current_char = iter.get();
 337     const UBlockCode current_block = ublock_getCode(current_char);
 338     const bool block_break = current_block != first_block &&
 339         (first_block_unusual || IsUnusualBlockCode(current_block));
 340     if (block_break || first_bracket != IsBracket(current_char))
 341       return run_start + iter.array_pos();
 342   }
 343   return run_break;
 344 }
 345
 346 // If the given scripts match, returns the one that isn't USCRIPT_COMMON or
 347 // USCRIPT_INHERITED, i.e. the more specific one. Otherwise returns
 348 // USCRIPT_INVALID_CODE.
 349 UScriptCode ScriptIntersect(UScriptCode first, UScriptCode second) {
 350   if (first == second ||
 351       (second > USCRIPT_INVALID_CODE && second <= USCRIPT_INHERITED)) {
 352     return first;
 353   }
 354   if (first > USCRIPT_INVALID_CODE && first <= USCRIPT_INHERITED)
 355     return second;
 356   return USCRIPT_INVALID_CODE;
 357 }
 358
 359 // Writes the script and the script extensions of the character with the
 360 // Unicode |codepoint|. Returns the number of written scripts.
 361 int GetScriptExtensions(UChar32 codepoint, UScriptCode* scripts) {
 362   UErrorCode icu_error = U_ZERO_ERROR;
 363   // ICU documentation incorrectly states that the result of
 364   // |uscript_getScriptExtensions| will contain the regular script property.
 365   // Write the character's script property to the first element.
 366   scripts[0] = uscript_getScript(codepoint, &icu_error);
 367   if (U_FAILURE(icu_error))
 368     return 0;
 369   // Fill the rest of |scripts| with the extensions.
 370   int count = uscript_getScriptExtensions(codepoint, scripts + 1,
 371                                           kMaxScripts - 1, &icu_error);
 372   if (U_FAILURE(icu_error))
 373     count = 0;
 374   return count + 1;
 375 }
 376
 377 // Intersects the script extensions set of |codepoint| with |result| and writes
 378 // to |result|, reading and updating |result_size|.
 379 void ScriptSetIntersect(UChar32 codepoint,
 380                         UScriptCode* result,
 381                         size_t* result_size) {
 382   UScriptCode scripts[kMaxScripts] = { USCRIPT_INVALID_CODE };
 383   int count = GetScriptExtensions(codepoint, scripts);
 384
 385   size_t out_size = 0;
 386
 387   for (size_t i = 0; i < *result_size; ++i) {
 388     for (int j = 0; j < count; ++j) {
 389       UScriptCode intersection = ScriptIntersect(result[i], scripts[j]);
 390       if (intersection != USCRIPT_INVALID_CODE) {
 391         result[out_size++] = intersection;
 392         break;
 393       }
 394     }
 395   }
 396
 397   *result_size = out_size;
 398 }
 399
 400 // Find the longest sequence of characters from 0 and up to |length| that
 401 // have at least one common UScriptCode value. Writes the common script value to
 402 // |script| and returns the length of the sequence. Takes the characters' script
 403 // extensions into account. http://www.unicode.org/reports/tr24/#ScriptX
 404 //
 405 // Consider 3 characters with the script values {Kana}, {Hira, Kana}, {Kana}.
 406 // Without script extensions only the first script in each set would be taken
 407 // into account, resulting in 3 runs where 1 would be enough.
 408 // TODO(ckocagil): Write a unit test for the case above.
 409 int ScriptInterval(const base::string16& text,
 410                    size_t start,
 411                    size_t length,
 412                    UScriptCode* script) {
 413   DCHECK_GT(length, 0U);
 414
 415   UScriptCode scripts[kMaxScripts] = { USCRIPT_INVALID_CODE };
 416
 417   base::i18n::UTF16CharIterator char_iterator(text.c_str() + start, length);
 418   size_t scripts_size = GetScriptExtensions(char_iterator.get(), scripts);
 419   *script = scripts[0];
 420
 421   while (char_iterator.Advance()) {
 422     ScriptSetIntersect(char_iterator.get(), scripts, &scripts_size);
 423     if (scripts_size == 0U)
 424       return char_iterator.array_pos();
 425     *script = scripts[0];
 426   }
 427
 428   return length;
 429 }
 430
 431 // A port of hb_icu_script_to_script because harfbuzz on CrOS is built without
 432 // hb-icu. See http://crbug.com/356929
 433 inline hb_script_t ICUScriptToHBScript(UScriptCode script) {
 434   if (script == USCRIPT_INVALID_CODE)
 435     return HB_SCRIPT_INVALID;
 436   return hb_script_from_string(uscript_getShortName(script), -1);
 437 }
 438
 439 // Helper template function for |TextRunHarfBuzz::GetClusterAt()|. |Iterator|
 440 // can be a forward or reverse iterator type depending on the text direction.
 441 template <class Iterator>
 442 void GetClusterAtImpl(size_t pos,
 443                       Range range,
 444                       Iterator elements_begin,
 445                       Iterator elements_end,
 446                       bool reversed,
 447                       Range* chars,
 448                       Range* glyphs) {
 449   Iterator element = std::upper_bound(elements_begin, elements_end, pos);
 450   chars->set_end(element == elements_end ? range.end() : *element);
 451   glyphs->set_end(reversed ? elements_end - element : element - elements_begin);
 452
 453   DCHECK(element != elements_begin);
 454   while (--element != elements_begin && *element == *(element - 1));
 455   chars->set_start(*element);
 456   glyphs->set_start(
 457       reversed ? elements_end - element : element - elements_begin);
 458   if (reversed)
 459     *glyphs = Range(glyphs->end(), glyphs->start());
 460
 461   DCHECK(!chars->is_reversed());
 462   DCHECK(!chars->is_empty());
 463   DCHECK(!glyphs->is_reversed());
 464   DCHECK(!glyphs->is_empty());
 465 }
 466
 467 }  // namespace
 468
 469 namespace internal {
 470
 471 Range RoundRangeF(const RangeF& range_f) {
 472   return Range(std::floor(range_f.first + 0.5f),
 473                std::floor(range_f.second + 0.5f));
 474 }
 475
 476 TextRunHarfBuzz::TextRunHarfBuzz()
 477     : width(0.0f),
 478       preceding_run_widths(0.0f),
 479       is_rtl(false),
 480       level(0),
 481       script(USCRIPT_INVALID_CODE),
 482       glyph_count(static_cast<size_t>(-1)),
 483       font_size(0),
 484       font_style(0),
 485       strike(false),
 486       diagonal_strike(false),
 487       underline(false) {}
 488
 489 TextRunHarfBuzz::~TextRunHarfBuzz() {}
 490
 491 void TextRunHarfBuzz::GetClusterAt(size_t pos,
 492                                    Range* chars,
 493                                    Range* glyphs) const {
 494   DCHECK(range.Contains(Range(pos, pos + 1)));
 495   DCHECK(chars);
 496   DCHECK(glyphs);
 497
 498   if (glyph_count == 0) {
 499     *chars = range;
 500     *glyphs = Range();
 501     return;
 502   }
 503
 504   if (is_rtl) {
 505     GetClusterAtImpl(pos, range, glyph_to_char.rbegin(), glyph_to_char.rend(),
 506         true, chars, glyphs);
 507     return;
 508   }
 509
 510   GetClusterAtImpl(pos, range, glyph_to_char.begin(), glyph_to_char.end(),
 511       false, chars, glyphs);
 512 }
 513
 514 Range TextRunHarfBuzz::CharRangeToGlyphRange(const Range& char_range) const {
 515   DCHECK(range.Contains(char_range));
 516   DCHECK(!char_range.is_reversed());
 517   DCHECK(!char_range.is_empty());
 518
 519   Range start_glyphs;
 520   Range end_glyphs;
 521   Range temp_range;
 522   GetClusterAt(char_range.start(), &temp_range, &start_glyphs);
 523   GetClusterAt(char_range.end() - 1, &temp_range, &end_glyphs);
 524
 525   return is_rtl ? Range(end_glyphs.start(), start_glyphs.end()) :
 526       Range(start_glyphs.start(), end_glyphs.end());
 527 }
 528
 529 size_t TextRunHarfBuzz::CountMissingGlyphs() const {
 530   static const int kMissingGlyphId = 0;
 531   size_t missing = 0;
 532   for (size_t i = 0; i < glyph_count; ++i)
 533     missing += (glyphs[i] == kMissingGlyphId) ? 1 : 0;
 534   return missing;
 535 }
 536
 537 RangeF TextRunHarfBuzz::GetGraphemeBounds(
 538     base::i18n::BreakIterator* grapheme_iterator,
 539     size_t text_index) {
 540   DCHECK_LT(text_index, range.end());
 541   if (glyph_count == 0)
 542     return RangeF(preceding_run_widths, preceding_run_widths + width);
 543
 544   Range chars;
 545   Range glyphs;
 546   GetClusterAt(text_index, &chars, &glyphs);
 547   const float cluster_begin_x = positions[glyphs.start()].x();
 548   const float cluster_end_x = glyphs.end() < glyph_count ?
 549       positions[glyphs.end()].x() : SkFloatToScalar(width);
 550
 551   // A cluster consists of a number of code points and corresponds to a number
 552   // of glyphs that should be drawn together. A cluster can contain multiple
 553   // graphemes. In order to place the cursor at a grapheme boundary inside the
 554   // cluster, we simply divide the cluster width by the number of graphemes.
 555   if (chars.length() > 1 && grapheme_iterator) {
 556     int before = 0;
 557     int total = 0;
 558     for (size_t i = chars.start(); i < chars.end(); ++i) {
 559       if (grapheme_iterator->IsGraphemeBoundary(i)) {
 560         if (i < text_index)
 561           ++before;
 562         ++total;
 563       }
 564     }
 565     DCHECK_GT(total, 0);
 566     if (total > 1) {
 567       if (is_rtl)
 568         before = total - before - 1;
 569       DCHECK_GE(before, 0);
 570       DCHECK_LT(before, total);
 571       const int cluster_width = cluster_end_x - cluster_begin_x;
 572       const int grapheme_begin_x = cluster_begin_x + static_cast<int>(0.5f +
 573           cluster_width * before / static_cast<float>(total));
 574       const int grapheme_end_x = cluster_begin_x + static_cast<int>(0.5f +
 575           cluster_width * (before + 1) / static_cast<float>(total));
 576       return RangeF(preceding_run_widths + grapheme_begin_x,
 577                     preceding_run_widths + grapheme_end_x);
 578     }
 579   }
 580
 581   return RangeF(preceding_run_widths + cluster_begin_x,
 582                 preceding_run_widths + cluster_end_x);
 583 }
 584
 585 }  // namespace internal
 586
 587 RenderTextHarfBuzz::RenderTextHarfBuzz()
 588     : RenderText(),
 589       needs_layout_(false) {
 590   set_truncate_length(kMaxTextLength);
 591 }
 592
 593 RenderTextHarfBuzz::~RenderTextHarfBuzz() {}
 594
 595 scoped_ptr<RenderText> RenderTextHarfBuzz::CreateInstanceOfSameType() const {
 596   return scoped_ptr<RenderTextHarfBuzz>(new RenderTextHarfBuzz);
 597 }
 598
 599 Size RenderTextHarfBuzz::GetStringSize() {
 600   const SizeF size_f = GetStringSizeF();
 601   return Size(std::ceil(size_f.width()), size_f.height());
 602 }
 603
 604 SizeF RenderTextHarfBuzz::GetStringSizeF() {
 605   EnsureLayout();
 606   return lines()[0].size;
 607 }
 608
 609 SelectionModel RenderTextHarfBuzz::FindCursorPosition(const Point& point) {
 610   EnsureLayout();
 611
 612   int x = ToTextPoint(point).x();
 613   float offset = 0;
 614   size_t run_index = GetRunContainingXCoord(x, &offset);
 615   if (run_index >= runs_.size())
 616     return EdgeSelectionModel((x < 0) ? CURSOR_LEFT : CURSOR_RIGHT);
 617   const internal::TextRunHarfBuzz& run = *runs_[run_index];
 618
 619   for (size_t i = 0; i < run.glyph_count; ++i) {
 620     const SkScalar end =
 621         i + 1 == run.glyph_count ? run.width : run.positions[i + 1].x();
 622     const SkScalar middle = (end + run.positions[i].x()) / 2;
 623
 624     if (offset < middle) {
 625       return SelectionModel(LayoutIndexToTextIndex(
 626           run.glyph_to_char[i] + (run.is_rtl ? 1 : 0)),
 627           (run.is_rtl ? CURSOR_BACKWARD : CURSOR_FORWARD));
 628     }
 629     if (offset < end) {
 630       return SelectionModel(LayoutIndexToTextIndex(
 631           run.glyph_to_char[i] + (run.is_rtl ? 0 : 1)),
 632           (run.is_rtl ? CURSOR_FORWARD : CURSOR_BACKWARD));
 633     }
 634   }
 635   return EdgeSelectionModel(CURSOR_RIGHT);
 636 }
 637
 638 std::vector<RenderText::FontSpan> RenderTextHarfBuzz::GetFontSpansForTesting() {
 639   EnsureLayout();
 640
 641   std::vector<RenderText::FontSpan> spans;
 642   for (size_t i = 0; i < runs_.size(); ++i) {
 643     SkString family_name;
 644     runs_[i]->skia_face->getFamilyName(&family_name);
 645     Font font(family_name.c_str(), runs_[i]->font_size);
 646     spans.push_back(RenderText::FontSpan(font,
 647         Range(LayoutIndexToTextIndex(runs_[i]->range.start()),
 648               LayoutIndexToTextIndex(runs_[i]->range.end()))));
 649   }
 650
 651   return spans;
 652 }
 653
 654 Range RenderTextHarfBuzz::GetGlyphBounds(size_t index) {
 655   EnsureLayout();
 656   const size_t run_index =
 657       GetRunContainingCaret(SelectionModel(index, CURSOR_FORWARD));
 658   // Return edge bounds if the index is invalid or beyond the layout text size.
 659   if (run_index >= runs_.size())
 660     return Range(GetStringSize().width());
 661   const size_t layout_index = TextIndexToLayoutIndex(index);
 662   internal::TextRunHarfBuzz* run = runs_[run_index];
 663   RangeF bounds =
 664       run->GetGraphemeBounds(grapheme_iterator_.get(), layout_index);
 665   // If cursor is enabled, extend the last glyph up to the rightmost cursor
 666   // position since clients expect them to be contiguous.
 667   if (cursor_enabled() && run_index == runs_.size() - 1 &&
 668       index == (run->is_rtl ? run->range.start() : run->range.end() - 1))
 669     bounds.second = std::ceil(bounds.second);
 670   return RoundRangeF(run->is_rtl ?
 671       RangeF(bounds.second, bounds.first) : bounds);
 672 }
 673
 674 int RenderTextHarfBuzz::GetLayoutTextBaseline() {
 675   EnsureLayout();
 676   return lines()[0].baseline;
 677 }
 678
 679 SelectionModel RenderTextHarfBuzz::AdjacentCharSelectionModel(
 680     const SelectionModel& selection,
 681     VisualCursorDirection direction) {
 682   DCHECK(!needs_layout_);
 683   internal::TextRunHarfBuzz* run;
 684   size_t run_index = GetRunContainingCaret(selection);
 685   if (run_index >= runs_.size()) {
 686     // The cursor is not in any run: we're at the visual and logical edge.
 687     SelectionModel edge = EdgeSelectionModel(direction);
 688     if (edge.caret_pos() == selection.caret_pos())
 689       return edge;
 690     int visual_index = (direction == CURSOR_RIGHT) ? 0 : runs_.size() - 1;
 691     run = runs_[visual_to_logical_[visual_index]];
 692   } else {
 693     // If the cursor is moving within the current run, just move it by one
 694     // grapheme in the appropriate direction.
 695     run = runs_[run_index];
 696     size_t caret = selection.caret_pos();
 697     bool forward_motion = run->is_rtl == (direction == CURSOR_LEFT);
 698     if (forward_motion) {
 699       if (caret < LayoutIndexToTextIndex(run->range.end())) {
 700         caret = IndexOfAdjacentGrapheme(caret, CURSOR_FORWARD);
 701         return SelectionModel(caret, CURSOR_BACKWARD);
 702       }
 703     } else {
 704       if (caret > LayoutIndexToTextIndex(run->range.start())) {
 705         caret = IndexOfAdjacentGrapheme(caret, CURSOR_BACKWARD);
 706         return SelectionModel(caret, CURSOR_FORWARD);
 707       }
 708     }
 709     // The cursor is at the edge of a run; move to the visually adjacent run.
 710     int visual_index = logical_to_visual_[run_index];
 711     visual_index += (direction == CURSOR_LEFT) ? -1 : 1;
 712     if (visual_index < 0 || visual_index >= static_cast<int>(runs_.size()))
 713       return EdgeSelectionModel(direction);
 714     run = runs_[visual_to_logical_[visual_index]];
 715   }
 716   bool forward_motion = run->is_rtl == (direction == CURSOR_LEFT);
 717   return forward_motion ? FirstSelectionModelInsideRun(run) :
 718                           LastSelectionModelInsideRun(run);
 719 }
 720
 721 SelectionModel RenderTextHarfBuzz::AdjacentWordSelectionModel(
 722     const SelectionModel& selection,
 723     VisualCursorDirection direction) {
 724   if (obscured())
 725     return EdgeSelectionModel(direction);
 726
 727   base::i18n::BreakIterator iter(text(), base::i18n::BreakIterator::BREAK_WORD);
 728   bool success = iter.Init();
 729   DCHECK(success);
 730   if (!success)
 731     return selection;
 732
 733   // Match OS specific word break behavior.
 734 #if defined(OS_WIN)
 735   size_t pos;
 736   if (direction == CURSOR_RIGHT) {
 737     pos = std::min(selection.caret_pos() + 1, text().length());
 738     while (iter.Advance()) {
 739       pos = iter.pos();
 740       if (iter.IsWord() && pos > selection.caret_pos())
 741         break;
 742     }
 743   } else {  // direction == CURSOR_LEFT
 744     // Notes: We always iterate words from the beginning.
 745     // This is probably fast enough for our usage, but we may
 746     // want to modify WordIterator so that it can start from the
 747     // middle of string and advance backwards.
 748     pos = std::max<int>(selection.caret_pos() - 1, 0);
 749     while (iter.Advance()) {
 750       if (iter.IsWord()) {
 751         size_t begin = iter.pos() - iter.GetString().length();
 752         if (begin == selection.caret_pos()) {
 753           // The cursor is at the beginning of a word.
 754           // Move to previous word.
 755           break;
 756         } else if (iter.pos() >= selection.caret_pos()) {
 757           // The cursor is in the middle or at the end of a word.
 758           // Move to the top of current word.
 759           pos = begin;
 760           break;
 761         }
 762         pos = iter.pos() - iter.GetString().length();
 763       }
 764     }
 765   }
 766   return SelectionModel(pos, CURSOR_FORWARD);
 767 #else
 768   SelectionModel cur(selection);
 769   for (;;) {
 770     cur = AdjacentCharSelectionModel(cur, direction);
 771     size_t run = GetRunContainingCaret(cur);
 772     if (run == runs_.size())
 773       break;
 774     const bool is_forward = runs_[run]->is_rtl == (direction == CURSOR_LEFT);
 775     size_t cursor = cur.caret_pos();
 776     if (is_forward ? iter.IsEndOfWord(cursor) : iter.IsStartOfWord(cursor))
 777       break;
 778   }
 779   return cur;
 780 #endif
 781 }
 782
 783 std::vector<Rect> RenderTextHarfBuzz::GetSubstringBounds(const Range& range) {
 784   DCHECK(!needs_layout_);
 785   DCHECK(Range(0, text().length()).Contains(range));
 786   Range layout_range(TextIndexToLayoutIndex(range.start()),
 787                      TextIndexToLayoutIndex(range.end()));
 788   DCHECK(Range(0, GetLayoutText().length()).Contains(layout_range));
 789
 790   std::vector<Rect> rects;
 791   if (layout_range.is_empty())
 792     return rects;
 793   std::vector<Range> bounds;
 794
 795   // Add a Range for each run/selection intersection.
 796   for (size_t i = 0; i < runs_.size(); ++i) {
 797     internal::TextRunHarfBuzz* run = runs_[visual_to_logical_[i]];
 798     Range intersection = run->range.Intersect(layout_range);
 799     if (!intersection.IsValid())
 800       continue;
 801     DCHECK(!intersection.is_reversed());
 802     const Range leftmost_character_x = RoundRangeF(run->GetGraphemeBounds(
 803         grapheme_iterator_.get(),
 804         run->is_rtl ? intersection.end() - 1 : intersection.start()));
 805     const Range rightmost_character_x = RoundRangeF(run->GetGraphemeBounds(
 806         grapheme_iterator_.get(),
 807         run->is_rtl ? intersection.start() : intersection.end() - 1));
 808     Range range_x(leftmost_character_x.start(), rightmost_character_x.end());
 809     DCHECK(!range_x.is_reversed());
 810     if (range_x.is_empty())
 811       continue;
 812
 813     // Union this with the last range if they're adjacent.
 814     DCHECK(bounds.empty() || bounds.back().GetMax() <= range_x.GetMin());
 815     if (!bounds.empty() && bounds.back().GetMax() == range_x.GetMin()) {
 816       range_x = Range(bounds.back().GetMin(), range_x.GetMax());
 817       bounds.pop_back();
 818     }
 819     bounds.push_back(range_x);
 820   }
 821   for (size_t i = 0; i < bounds.size(); ++i) {
 822     std::vector<Rect> current_rects = TextBoundsToViewBounds(bounds[i]);
 823     rects.insert(rects.end(), current_rects.begin(), current_rects.end());
 824   }
 825   return rects;
 826 }
 827
 828 size_t RenderTextHarfBuzz::TextIndexToLayoutIndex(size_t index) const {
 829   DCHECK_LE(index, text().length());
 830   ptrdiff_t i = obscured() ? UTF16IndexToOffset(text(), 0, index) : index;
 831   CHECK_GE(i, 0);
 832   // Clamp layout indices to the length of the text actually used for layout.
 833   return std::min<size_t>(GetLayoutText().length(), i);
 834 }
 835
 836 size_t RenderTextHarfBuzz::LayoutIndexToTextIndex(size_t index) const {
 837   if (!obscured())
 838     return index;
 839
 840   DCHECK_LE(index, GetLayoutText().length());
 841   const size_t text_index = UTF16OffsetToIndex(text(), 0, index);
 842   DCHECK_LE(text_index, text().length());
 843   return text_index;
 844 }
 845
 846 bool RenderTextHarfBuzz::IsValidCursorIndex(size_t index) {
 847   if (index == 0 || index == text().length())
 848     return true;
 849   if (!IsValidLogicalIndex(index))
 850     return false;
 851   EnsureLayout();
 852   return !grapheme_iterator_ || grapheme_iterator_->IsGraphemeBoundary(index);
 853 }
 854
 855 void RenderTextHarfBuzz::ResetLayout() {
 856   needs_layout_ = true;
 857 }
 858
 859 void RenderTextHarfBuzz::EnsureLayout() {
 860   // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is fixed.
 861   tracked_objects::ScopedTracker tracking_profile(
 862       FROM_HERE_WITH_EXPLICIT_FUNCTION(
 863           "431326 RenderTextHarfBuzz::EnsureLayout"));
 864
 865   if (needs_layout_) {
 866     runs_.clear();
 867     grapheme_iterator_.reset();
 868
 869     if (!GetLayoutText().empty()) {
 870       // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is
 871       // fixed.
 872       tracked_objects::ScopedTracker tracking_profile1(
 873           FROM_HERE_WITH_EXPLICIT_FUNCTION(
 874               "431326 RenderTextHarfBuzz::EnsureLayout1"));
 875
 876       grapheme_iterator_.reset(new base::i18n::BreakIterator(GetLayoutText(),
 877           base::i18n::BreakIterator::BREAK_CHARACTER));
 878       if (!grapheme_iterator_->Init())
 879         grapheme_iterator_.reset();
 880
 881       // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is
 882       // fixed.
 883       tracked_objects::ScopedTracker tracking_profile11(
 884           FROM_HERE_WITH_EXPLICIT_FUNCTION(
 885               "431326 RenderTextHarfBuzz::EnsureLayout11"));
 886
 887       ItemizeText();
 888
 889       // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is
 890       // fixed.
 891       tracked_objects::ScopedTracker tracking_profile12(
 892           FROM_HERE_WITH_EXPLICIT_FUNCTION(
 893               "431326 RenderTextHarfBuzz::EnsureLayout12"));
 894
 895       for (size_t i = 0; i < runs_.size(); ++i)
 896         ShapeRun(runs_[i]);
 897
 898       // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is
 899       // fixed.
 900       tracked_objects::ScopedTracker tracking_profile13(
 901           FROM_HERE_WITH_EXPLICIT_FUNCTION(
 902               "431326 RenderTextHarfBuzz::EnsureLayout13"));
 903
 904       // Precalculate run width information.
 905       float preceding_run_widths = 0.0f;
 906       for (size_t i = 0; i < runs_.size(); ++i) {
 907         internal::TextRunHarfBuzz* run = runs_[visual_to_logical_[i]];
 908         run->preceding_run_widths = preceding_run_widths;
 909         preceding_run_widths += run->width;
 910       }
 911     }
 912
 913     // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is
 914     // fixed.
 915     tracked_objects::ScopedTracker tracking_profile14(
 916         FROM_HERE_WITH_EXPLICIT_FUNCTION(
 917             "431326 RenderTextHarfBuzz::EnsureLayout14"));
 918
 919     needs_layout_ = false;
 920     std::vector<internal::Line> empty_lines;
 921     set_lines(&empty_lines);
 922   }
 923
 924   if (lines().empty()) {
 925     // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is fixed.
 926     tracked_objects::ScopedTracker tracking_profile2(
 927         FROM_HERE_WITH_EXPLICIT_FUNCTION(
 928             "431326 RenderTextHarfBuzz::EnsureLayout2"));
 929
 930     std::vector<internal::Line> lines;
 931     lines.push_back(internal::Line());
 932     lines[0].baseline = font_list().GetBaseline();
 933     lines[0].size.set_height(font_list().GetHeight());
 934
 935     int current_x = 0;
 936     SkPaint paint;
 937
 938     // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is fixed.
 939     tracked_objects::ScopedTracker tracking_profile3(
 940         FROM_HERE_WITH_EXPLICIT_FUNCTION(
 941             "431326 RenderTextHarfBuzz::EnsureLayout3"));
 942
 943     for (size_t i = 0; i < runs_.size(); ++i) {
 944       const internal::TextRunHarfBuzz& run = *runs_[visual_to_logical_[i]];
 945       internal::LineSegment segment;
 946       segment.x_range = Range(current_x, current_x + run.width);
 947       segment.char_range = run.range;
 948       segment.run = i;
 949       lines[0].segments.push_back(segment);
 950
 951       paint.setTypeface(run.skia_face.get());
 952       paint.setTextSize(SkIntToScalar(run.font_size));
 953       paint.setAntiAlias(run.render_params.antialiasing);
 954       SkPaint::FontMetrics metrics;
 955       paint.getFontMetrics(&metrics);
 956
 957       lines[0].size.set_width(lines[0].size.width() + run.width);
 958       lines[0].size.set_height(std::max(lines[0].size.height(),
 959                                         metrics.fDescent - metrics.fAscent));
 960       lines[0].baseline = std::max(lines[0].baseline,
 961                                    SkScalarRoundToInt(-metrics.fAscent));
 962     }
 963
 964     set_lines(&lines);
 965   }
 966 }
 967
 968 void RenderTextHarfBuzz::DrawVisualText(Canvas* canvas) {
 969   DCHECK(!needs_layout_);
 970   internal::SkiaTextRenderer renderer(canvas);
 971   ApplyFadeEffects(&renderer);
 972   ApplyTextShadows(&renderer);
 973   ApplyCompositionAndSelectionStyles();
 974
 975   const Vector2d line_offset = GetLineOffset(0);
 976   for (size_t i = 0; i < runs_.size(); ++i) {
 977     const internal::TextRunHarfBuzz& run = *runs_[visual_to_logical_[i]];
 978     renderer.SetTypeface(run.skia_face.get());
 979     renderer.SetTextSize(SkIntToScalar(run.font_size));
 980     renderer.SetFontRenderParams(run.render_params,
 981                                  background_is_transparent());
 982
 983     Vector2d origin = line_offset + Vector2d(0, lines()[0].baseline);
 984     scoped_ptr<SkPoint[]> positions(new SkPoint[run.glyph_count]);
 985     for (size_t j = 0; j < run.glyph_count; ++j) {
 986       positions[j] = run.positions[j];
 987       positions[j].offset(SkIntToScalar(origin.x()) + run.preceding_run_widths,
 988                           SkIntToScalar(origin.y()));
 989     }
 990
 991     for (BreakList<SkColor>::const_iterator it =
 992              colors().GetBreak(run.range.start());
 993          it != colors().breaks().end() && it->first < run.range.end();
 994          ++it) {
 995       const Range intersection = colors().GetRange(it).Intersect(run.range);
 996       const Range colored_glyphs = run.CharRangeToGlyphRange(intersection);
 997       // The range may be empty if a portion of a multi-character grapheme is
 998       // selected, yielding two colors for a single glyph. For now, this just
 999       // paints the glyph with a single style, but it should paint it twice,
1000       // clipped according to selection bounds. See http://crbug.com/366786
1001       if (colored_glyphs.is_empty())
1002         continue;
1003
1004       renderer.SetForegroundColor(it->second);
1005       renderer.DrawPosText(&positions[colored_glyphs.start()],
1006                            &run.glyphs[colored_glyphs.start()],
1007                            colored_glyphs.length());
1008       int start_x = SkScalarRoundToInt(positions[colored_glyphs.start()].x());
1009       int end_x = SkScalarRoundToInt((colored_glyphs.end() == run.glyph_count) ?
1010           (run.width + run.preceding_run_widths + SkIntToScalar(origin.x())) :
1011           positions[colored_glyphs.end()].x());
1012       renderer.DrawDecorations(start_x, origin.y(), end_x - start_x,
1013                                run.underline, run.strike, run.diagonal_strike);
1014     }
1015   }
1016
1017   renderer.EndDiagonalStrike();
1018
1019   UndoCompositionAndSelectionStyles();
1020 }
1021
1022 size_t RenderTextHarfBuzz::GetRunContainingCaret(
1023     const SelectionModel& caret) const {
1024   DCHECK(!needs_layout_);
1025   size_t layout_position = TextIndexToLayoutIndex(caret.caret_pos());
1026   LogicalCursorDirection affinity = caret.caret_affinity();
1027   for (size_t run = 0; run < runs_.size(); ++run) {
1028     if (RangeContainsCaret(runs_[run]->range, layout_position, affinity))
1029       return run;
1030   }
1031   return runs_.size();
1032 }
1033
1034 size_t RenderTextHarfBuzz::GetRunContainingXCoord(float x,
1035                                                   float* offset) const {
1036   DCHECK(!needs_layout_);
1037   if (x < 0)
1038     return runs_.size();
1039   // Find the text run containing the argument point (assumed already offset).
1040   float current_x = 0;
1041   for (size_t i = 0; i < runs_.size(); ++i) {
1042     size_t run = visual_to_logical_[i];
1043     current_x += runs_[run]->width;
1044     if (x < current_x) {
1045       *offset = x - (current_x - runs_[run]->width);
1046       return run;
1047     }
1048   }
1049   return runs_.size();
1050 }
1051
1052 SelectionModel RenderTextHarfBuzz::FirstSelectionModelInsideRun(
1053     const internal::TextRunHarfBuzz* run) {
1054   size_t position = LayoutIndexToTextIndex(run->range.start());
1055   position = IndexOfAdjacentGrapheme(position, CURSOR_FORWARD);
1056   return SelectionModel(position, CURSOR_BACKWARD);
1057 }
1058
1059 SelectionModel RenderTextHarfBuzz::LastSelectionModelInsideRun(
1060     const internal::TextRunHarfBuzz* run) {
1061   size_t position = LayoutIndexToTextIndex(run->range.end());
1062   position = IndexOfAdjacentGrapheme(position, CURSOR_BACKWARD);
1063   return SelectionModel(position, CURSOR_FORWARD);
1064 }
1065
1066 void RenderTextHarfBuzz::ItemizeText() {
1067   const base::string16& text = GetLayoutText();
1068   const bool is_text_rtl = GetTextDirection() == base::i18n::RIGHT_TO_LEFT;
1069   DCHECK_NE(0U, text.length());
1070
1071   // If ICU fails to itemize the text, we create a run that spans the entire
1072   // text. This is needed because leaving the runs set empty causes some clients
1073   // to misbehave since they expect non-zero text metrics from a non-empty text.
1074   base::i18n::BiDiLineIterator bidi_iterator;
1075   if (!bidi_iterator.Open(text, is_text_rtl, false)) {
1076     internal::TextRunHarfBuzz* run = new internal::TextRunHarfBuzz;
1077     run->range = Range(0, text.length());
1078     runs_.push_back(run);
1079     visual_to_logical_ = logical_to_visual_ = std::vector<int32_t>(1, 0);
1080     return;
1081   }
1082
1083   // Temporarily apply composition underlines and selection colors.
1084   ApplyCompositionAndSelectionStyles();
1085
1086   // Build the list of runs from the script items and ranged styles. Use an
1087   // empty color BreakList to avoid breaking runs at color boundaries.
1088   BreakList<SkColor> empty_colors;
1089   empty_colors.SetMax(text.length());
1090   internal::StyleIterator style(empty_colors, styles());
1091
1092   for (size_t run_break = 0; run_break < text.length();) {
1093     internal::TextRunHarfBuzz* run = new internal::TextRunHarfBuzz;
1094     run->range.set_start(run_break);
1095     run->font_style = (style.style(BOLD) ? Font::BOLD : 0) |
1096                       (style.style(ITALIC) ? Font::ITALIC : 0);
1097     run->strike = style.style(STRIKE);
1098     run->diagonal_strike = style.style(DIAGONAL_STRIKE);
1099     run->underline = style.style(UNDERLINE);
1100
1101     int32 script_item_break = 0;
1102     bidi_iterator.GetLogicalRun(run_break, &script_item_break, &run->level);
1103     // Odd BiDi embedding levels correspond to RTL runs.
1104     run->is_rtl = (run->level % 2) == 1;
1105     // Find the length and script of this script run.
1106     script_item_break = ScriptInterval(text, run_break,
1107         script_item_break - run_break, &run->script) + run_break;
1108
1109     // Find the next break and advance the iterators as needed.
1110     run_break = std::min(static_cast<size_t>(script_item_break),
1111                          TextIndexToLayoutIndex(style.GetRange().end()));
1112
1113     // Break runs at certain characters that need to be rendered separately to
1114     // prevent either an unusual character from forcing a fallback font on the
1115     // entire run, or brackets from being affected by a fallback font.
1116     // http://crbug.com/278913, http://crbug.com/396776
1117     if (run_break > run->range.start())
1118       run_break = FindRunBreakingCharacter(text, run->range.start(), run_break);
1119
1120     DCHECK(IsValidCodePointIndex(text, run_break));
1121     style.UpdatePosition(LayoutIndexToTextIndex(run_break));
1122     run->range.set_end(run_break);
1123
1124     runs_.push_back(run);
1125   }
1126
1127   // Undo the temporarily applied composition underlines and selection colors.
1128   UndoCompositionAndSelectionStyles();
1129
1130   const size_t num_runs = runs_.size();
1131   std::vector<UBiDiLevel> levels(num_runs);
1132   for (size_t i = 0; i < num_runs; ++i)
1133     levels[i] = runs_[i]->level;
1134   visual_to_logical_.resize(num_runs);
1135   ubidi_reorderVisual(&levels[0], num_runs, &visual_to_logical_[0]);
1136   logical_to_visual_.resize(num_runs);
1137   ubidi_reorderLogical(&levels[0], num_runs, &logical_to_visual_[0]);
1138 }
1139
1140 bool RenderTextHarfBuzz::CompareFamily(
1141     internal::TextRunHarfBuzz* run,
1142     const std::string& family,
1143     const gfx::FontRenderParams& render_params,
1144     std::string* best_family,
1145     gfx::FontRenderParams* best_render_params,
1146     size_t* best_missing_glyphs) {
1147   if (!ShapeRunWithFont(run, family, render_params))
1148     return false;
1149
1150   const size_t missing_glyphs = run->CountMissingGlyphs();
1151   if (missing_glyphs < *best_missing_glyphs) {
1152     *best_family = family;
1153     *best_render_params = render_params;
1154     *best_missing_glyphs = missing_glyphs;
1155   }
1156   return missing_glyphs == 0;
1157 }
1158
1159 void RenderTextHarfBuzz::ShapeRun(internal::TextRunHarfBuzz* run) {
1160   const Font& primary_font = font_list().GetPrimaryFont();
1161   const std::string primary_family = primary_font.GetFontName();
1162   run->font_size = primary_font.GetFontSize();
1163
1164   std::string best_family;
1165   FontRenderParams best_render_params;
1166   size_t best_missing_glyphs = std::numeric_limits<size_t>::max();
1167
1168   for (const Font& font : font_list().GetFonts()) {
1169     if (CompareFamily(run, font.GetFontName(), font.GetFontRenderParams(),
1170                       &best_family, &best_render_params, &best_missing_glyphs))
1171       return;
1172   }
1173
1174 #if defined(OS_WIN)
1175   Font uniscribe_font;
1176   std::string uniscribe_family;
1177   const base::char16* run_text = &(GetLayoutText()[run->range.start()]);
1178   if (GetUniscribeFallbackFont(primary_font, run_text, run->range.length(),
1179                                &uniscribe_font)) {
1180     uniscribe_family = uniscribe_font.GetFontName();
1181     if (CompareFamily(run, uniscribe_family,
1182                       uniscribe_font.GetFontRenderParams(),
1183                       &best_family, &best_render_params, &best_missing_glyphs))
1184       return;
1185   }
1186 #endif
1187
1188   std::vector<std::string> fallback_families =
1189       GetFallbackFontFamilies(primary_family);
1190
1191 #if defined(OS_WIN)
1192   // Append fonts in the fallback list of the Uniscribe font.
1193   if (!uniscribe_family.empty()) {
1194     std::vector<std::string> uniscribe_fallbacks =
1195         GetFallbackFontFamilies(uniscribe_family);
1196     fallback_families.insert(fallback_families.end(),
1197         uniscribe_fallbacks.begin(), uniscribe_fallbacks.end());
1198   }
1199 #endif
1200
1201   // Try shaping with the fallback fonts.
1202   for (const auto& family : fallback_families) {
1203     if (family == primary_family)
1204       continue;
1205 #if defined(OS_WIN)
1206     if (family == uniscribe_family)
1207       continue;
1208 #endif
1209     FontRenderParamsQuery query(false);
1210     query.families.push_back(family);
1211     query.pixel_size = run->font_size;
1212     query.style = run->font_style;
1213     FontRenderParams fallback_render_params = GetFontRenderParams(query, NULL);
1214     if (CompareFamily(run, family, fallback_render_params, &best_family,
1215                       &best_render_params, &best_missing_glyphs))
1216       return;
1217   }
1218
1219   if (!best_family.empty() &&
1220       (best_family == run->family ||
1221        ShapeRunWithFont(run, best_family, best_render_params)))
1222     return;
1223
1224   run->glyph_count = 0;
1225   run->width = 0.0f;
1226 }
1227
1228 bool RenderTextHarfBuzz::ShapeRunWithFont(internal::TextRunHarfBuzz* run,
1229                                           const std::string& font_family,
1230                                           const FontRenderParams& params) {
1231   // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is fixed.
1232   tracked_objects::ScopedTracker tracking_profile0(
1233       FROM_HERE_WITH_EXPLICIT_FUNCTION(
1234           "431326 RenderTextHarfBuzz::ShapeRunWithFont0"));
1235
1236   const base::string16& text = GetLayoutText();
1237   skia::RefPtr<SkTypeface> skia_face =
1238       internal::CreateSkiaTypeface(font_family, run->font_style);
1239   if (skia_face == NULL)
1240     return false;
1241   run->skia_face = skia_face;
1242   run->family = font_family;
1243   run->render_params = params;
1244
1245   // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is fixed.
1246   tracked_objects::ScopedTracker tracking_profile01(
1247       FROM_HERE_WITH_EXPLICIT_FUNCTION(
1248           "431326 RenderTextHarfBuzz::ShapeRunWithFont01"));
1249
1250   hb_font_t* harfbuzz_font = CreateHarfBuzzFont(
1251       run->skia_face.get(), SkIntToScalar(run->font_size), run->render_params,
1252       background_is_transparent());
1253
1254   // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is fixed.
1255   tracked_objects::ScopedTracker tracking_profile1(
1256       FROM_HERE_WITH_EXPLICIT_FUNCTION(
1257           "431326 RenderTextHarfBuzz::ShapeRunWithFont1"));
1258
1259   // Create a HarfBuzz buffer and add the string to be shaped. The HarfBuzz
1260   // buffer holds our text, run information to be used by the shaping engine,
1261   // and the resulting glyph data.
1262   hb_buffer_t* buffer = hb_buffer_create();
1263
1264   // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is fixed.
1265   tracked_objects::ScopedTracker tracking_profile1q(
1266       FROM_HERE_WITH_EXPLICIT_FUNCTION(
1267           "431326 RenderTextHarfBuzz::ShapeRunWithFont11"));
1268
1269   hb_buffer_add_utf16(buffer, reinterpret_cast<const uint16*>(text.c_str()),
1270                       text.length(), run->range.start(), run->range.length());
1271
1272   // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is fixed.
1273   tracked_objects::ScopedTracker tracking_profile12(
1274       FROM_HERE_WITH_EXPLICIT_FUNCTION(
1275           "431326 RenderTextHarfBuzz::ShapeRunWithFont12"));
1276
1277   hb_buffer_set_script(buffer, ICUScriptToHBScript(run->script));
1278
1279   // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is fixed.
1280   tracked_objects::ScopedTracker tracking_profile13(
1281       FROM_HERE_WITH_EXPLICIT_FUNCTION(
1282           "431326 RenderTextHarfBuzz::ShapeRunWithFont13"));
1283
1284   hb_buffer_set_direction(buffer,
1285       run->is_rtl ? HB_DIRECTION_RTL : HB_DIRECTION_LTR);
1286
1287   // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is fixed.
1288   tracked_objects::ScopedTracker tracking_profile14(
1289       FROM_HERE_WITH_EXPLICIT_FUNCTION(
1290           "431326 RenderTextHarfBuzz::ShapeRunWithFont14"));
1291
1292   // TODO(ckocagil): Should we determine the actual language?
1293   hb_buffer_set_language(buffer, hb_language_get_default());
1294
1295   // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is fixed.
1296   tracked_objects::ScopedTracker tracking_profile15(
1297       FROM_HERE_WITH_EXPLICIT_FUNCTION(
1298           "431326 RenderTextHarfBuzz::ShapeRunWithFont15"));
1299
1300   // Shape the text.
1301   hb_shape(harfbuzz_font, buffer, NULL, 0);
1302
1303   // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is fixed.
1304   tracked_objects::ScopedTracker tracking_profile2(
1305       FROM_HERE_WITH_EXPLICIT_FUNCTION(
1306           "431326 RenderTextHarfBuzz::ShapeRunWithFont2"));
1307
1308   // Populate the run fields with the resulting glyph data in the buffer.
1309   unsigned int glyph_count = 0;
1310   hb_glyph_info_t* infos = hb_buffer_get_glyph_infos(buffer, &glyph_count);
1311   run->glyph_count = glyph_count;
1312   hb_glyph_position_t* hb_positions =
1313       hb_buffer_get_glyph_positions(buffer, NULL);
1314   run->glyphs.reset(new uint16[run->glyph_count]);
1315   run->glyph_to_char.resize(run->glyph_count);
1316   run->positions.reset(new SkPoint[run->glyph_count]);
1317   run->width = 0.0f;
1318
1319   // TODO(vadimt): Remove ScopedTracker below once crbug.com/431326 is fixed.
1320   tracked_objects::ScopedTracker tracking_profile3(
1321       FROM_HERE_WITH_EXPLICIT_FUNCTION(
1322           "431326 RenderTextHarfBuzz::ShapeRunWithFont3"));
1323
1324   for (size_t i = 0; i < run->glyph_count; ++i) {
1325     DCHECK_LE(infos[i].codepoint, std::numeric_limits<uint16>::max());
1326     run->glyphs[i] = static_cast<uint16>(infos[i].codepoint);
1327     run->glyph_to_char[i] = infos[i].cluster;
1328     const SkScalar x_offset = SkFixedToScalar(hb_positions[i].x_offset);
1329     const SkScalar y_offset = SkFixedToScalar(hb_positions[i].y_offset);
1330     run->positions[i].set(run->width + x_offset, -y_offset);
1331     run->width += SkFixedToScalar(hb_positions[i].x_advance);
1332     // Round run widths if subpixel positioning is off to match native behavior.
1333     if (!run->render_params.subpixel_positioning)
1334       run->width = std::floor(run->width + 0.5f);
1335   }
1336
1337   hb_buffer_destroy(buffer);
1338   hb_font_destroy(harfbuzz_font);
1339   return true;
1340 }
1341
1342 }  // namespace gfx