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 <map>
   8
   9 #include "base/debug/leak_annotations.h"
  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 "third_party/harfbuzz-ng/src/hb.h"
  15 #include "third_party/icu/source/common/unicode/ubidi.h"
  16 #include "third_party/skia/include/core/SkColor.h"
  17 #include "third_party/skia/include/core/SkTypeface.h"
  18 #include "ui/gfx/canvas.h"
  19 #include "ui/gfx/font_render_params.h"
  20 #include "ui/gfx/utf16_indexing.h"
  21
  22 namespace gfx {
  23
  24 namespace {
  25
  26 // The maximum number of scripts a Unicode character can belong to. This value
  27 // is arbitrarily chosen to be a good limit because it is unlikely for a single
  28 // character to belong to more scripts.
  29 const size_t kMaxScripts = 5;
  30
  31 // Maps from code points to glyph indices in a font.
  32 typedef std::map<uint32_t, uint16_t> GlyphCache;
  33
  34 // Font data provider for HarfBuzz using Skia. Copied from Blink.
  35 // TODO(ckocagil): Eliminate the duplication. http://crbug.com/368375
  36 struct FontData {
  37   FontData(GlyphCache* glyph_cache) : glyph_cache_(glyph_cache) {}
  38
  39   SkPaint paint_;
  40   GlyphCache* glyph_cache_;
  41 };
  42
  43 hb_position_t SkiaScalarToHarfBuzzPosition(SkScalar value) {
  44   return SkScalarToFixed(value);
  45 }
  46
  47 // Deletes the object at the given pointer after casting it to the given type.
  48 template<typename Type>
  49 void DeleteByType(void* data) {
  50   Type* typed_data = reinterpret_cast<Type*>(data);
  51   delete typed_data;
  52 }
  53
  54 template<typename Type>
  55 void DeleteArrayByType(void* data) {
  56   Type* typed_data = reinterpret_cast<Type*>(data);
  57   delete[] typed_data;
  58 }
  59
  60 // Outputs the |width| and |extents| of the glyph with index |codepoint| in
  61 // |paint|'s font.
  62 void GetGlyphWidthAndExtents(SkPaint* paint,
  63                              hb_codepoint_t codepoint,
  64                              hb_position_t* width,
  65                              hb_glyph_extents_t* extents) {
  66   DCHECK_LE(codepoint, 0xFFFFU);
  67   paint->setTextEncoding(SkPaint::kGlyphID_TextEncoding);
  68
  69   SkScalar sk_width;
  70   SkRect sk_bounds;
  71   uint16_t glyph = codepoint;
  72
  73   paint->getTextWidths(&glyph, sizeof(glyph), &sk_width, &sk_bounds);
  74   if (width)
  75     *width = SkiaScalarToHarfBuzzPosition(sk_width);
  76   if (extents) {
  77     // Invert y-axis because Skia is y-grows-down but we set up HarfBuzz to be
  78     // y-grows-up.
  79     extents->x_bearing = SkiaScalarToHarfBuzzPosition(sk_bounds.fLeft);
  80     extents->y_bearing = SkiaScalarToHarfBuzzPosition(-sk_bounds.fTop);
  81     extents->width = SkiaScalarToHarfBuzzPosition(sk_bounds.width());
  82     extents->height = SkiaScalarToHarfBuzzPosition(-sk_bounds.height());
  83   }
  84 }
  85
  86 // Writes the |glyph| index for the given |unicode| code point. Returns whether
  87 // the glyph exists, i.e. it is not a missing glyph.
  88 hb_bool_t GetGlyph(hb_font_t* font,
  89                    void* data,
  90                    hb_codepoint_t unicode,
  91                    hb_codepoint_t variation_selector,
  92                    hb_codepoint_t* glyph,
  93                    void* user_data) {
  94   FontData* font_data = reinterpret_cast<FontData*>(data);
  95   GlyphCache* cache = font_data->glyph_cache_;
  96
  97   bool exists = cache->count(unicode) != 0;
  98   if (!exists) {
  99     SkPaint* paint = &font_data->paint_;
 100     paint->setTextEncoding(SkPaint::kUTF32_TextEncoding);
 101     paint->textToGlyphs(&unicode, sizeof(hb_codepoint_t), &(*cache)[unicode]);
 102   }
 103   *glyph = (*cache)[unicode];
 104   return !!*glyph;
 105 }
 106
 107 // Returns the horizontal advance value of the |glyph|.
 108 hb_position_t GetGlyphHorizontalAdvance(hb_font_t* font,
 109                                         void* data,
 110                                         hb_codepoint_t glyph,
 111                                         void* user_data) {
 112   FontData* font_data = reinterpret_cast<FontData*>(data);
 113   hb_position_t advance = 0;
 114
 115   GetGlyphWidthAndExtents(&font_data->paint_, glyph, &advance, 0);
 116   return advance;
 117 }
 118
 119 hb_bool_t GetGlyphHorizontalOrigin(hb_font_t* font,
 120                                    void* data,
 121                                    hb_codepoint_t glyph,
 122                                    hb_position_t* x,
 123                                    hb_position_t* y,
 124                                    void* user_data) {
 125   // Just return true, like the HarfBuzz-FreeType implementation.
 126   return true;
 127 }
 128
 129 hb_position_t GetGlyphKerning(FontData* font_data,
 130                               hb_codepoint_t first_glyph,
 131                               hb_codepoint_t second_glyph) {
 132   SkTypeface* typeface = font_data->paint_.getTypeface();
 133   const uint16_t glyphs[2] = { static_cast<uint16_t>(first_glyph),
 134                                static_cast<uint16_t>(second_glyph) };
 135   int32_t kerning_adjustments[1] = { 0 };
 136
 137   if (!typeface->getKerningPairAdjustments(glyphs, 2, kerning_adjustments))
 138     return 0;
 139
 140   SkScalar upm = SkIntToScalar(typeface->getUnitsPerEm());
 141   SkScalar size = font_data->paint_.getTextSize();
 142   return SkiaScalarToHarfBuzzPosition(
 143       SkScalarMulDiv(SkIntToScalar(kerning_adjustments[0]), size, upm));
 144 }
 145
 146 hb_position_t GetGlyphHorizontalKerning(hb_font_t* font,
 147                                         void* data,
 148                                         hb_codepoint_t left_glyph,
 149                                         hb_codepoint_t right_glyph,
 150                                         void* user_data) {
 151   FontData* font_data = reinterpret_cast<FontData*>(data);
 152   if (font_data->paint_.isVerticalText()) {
 153     // We don't support cross-stream kerning.
 154     return 0;
 155   }
 156
 157   return GetGlyphKerning(font_data, left_glyph, right_glyph);
 158 }
 159
 160 hb_position_t GetGlyphVerticalKerning(hb_font_t* font,
 161                                       void* data,
 162                                       hb_codepoint_t top_glyph,
 163                                       hb_codepoint_t bottom_glyph,
 164                                       void* user_data) {
 165   FontData* font_data = reinterpret_cast<FontData*>(data);
 166   if (!font_data->paint_.isVerticalText()) {
 167     // We don't support cross-stream kerning.
 168     return 0;
 169   }
 170
 171   return GetGlyphKerning(font_data, top_glyph, bottom_glyph);
 172 }
 173
 174 // Writes the |extents| of |glyph|.
 175 hb_bool_t GetGlyphExtents(hb_font_t* font,
 176                           void* data,
 177                           hb_codepoint_t glyph,
 178                           hb_glyph_extents_t* extents,
 179                           void* user_data) {
 180   FontData* font_data = reinterpret_cast<FontData*>(data);
 181
 182   GetGlyphWidthAndExtents(&font_data->paint_, glyph, 0, extents);
 183   return true;
 184 }
 185
 186 class FontFuncs {
 187  public:
 188   FontFuncs() : font_funcs_(hb_font_funcs_create()) {
 189     hb_font_funcs_set_glyph_func(font_funcs_, GetGlyph, 0, 0);
 190     hb_font_funcs_set_glyph_h_advance_func(
 191         font_funcs_, GetGlyphHorizontalAdvance, 0, 0);
 192     hb_font_funcs_set_glyph_h_kerning_func(
 193         font_funcs_, GetGlyphHorizontalKerning, 0, 0);
 194     hb_font_funcs_set_glyph_h_origin_func(
 195         font_funcs_, GetGlyphHorizontalOrigin, 0, 0);
 196     hb_font_funcs_set_glyph_v_kerning_func(
 197         font_funcs_, GetGlyphVerticalKerning, 0, 0);
 198     hb_font_funcs_set_glyph_extents_func(
 199         font_funcs_, GetGlyphExtents, 0, 0);
 200     hb_font_funcs_make_immutable(font_funcs_);
 201   }
 202
 203   ~FontFuncs() {
 204     hb_font_funcs_destroy(font_funcs_);
 205   }
 206
 207   hb_font_funcs_t* get() { return font_funcs_; }
 208
 209  private:
 210   hb_font_funcs_t* font_funcs_;
 211
 212   DISALLOW_COPY_AND_ASSIGN(FontFuncs);
 213 };
 214
 215 base::LazyInstance<FontFuncs>::Leaky g_font_funcs = LAZY_INSTANCE_INITIALIZER;
 216
 217 // Returns the raw data of the font table |tag|.
 218 hb_blob_t* GetFontTable(hb_face_t* face, hb_tag_t tag, void* user_data) {
 219   SkTypeface* typeface = reinterpret_cast<SkTypeface*>(user_data);
 220
 221   const size_t table_size = typeface->getTableSize(tag);
 222   if (!table_size)
 223     return 0;
 224
 225   scoped_ptr<char[]> buffer(new char[table_size]);
 226   if (!buffer)
 227     return 0;
 228   size_t actual_size = typeface->getTableData(tag, 0, table_size, buffer.get());
 229   if (table_size != actual_size)
 230     return 0;
 231
 232   char* buffer_raw = buffer.release();
 233   return hb_blob_create(buffer_raw, table_size, HB_MEMORY_MODE_WRITABLE,
 234                         buffer_raw, DeleteArrayByType<char>);
 235 }
 236
 237 void UnrefSkTypeface(void* data) {
 238   SkTypeface* skia_face = reinterpret_cast<SkTypeface*>(data);
 239   SkSafeUnref(skia_face);
 240 }
 241
 242 // Creates a HarfBuzz face from the given Skia face.
 243 hb_face_t* CreateHarfBuzzFace(SkTypeface* skia_face) {
 244   SkSafeRef(skia_face);
 245   hb_face_t* face = hb_face_create_for_tables(GetFontTable, skia_face,
 246                                               UnrefSkTypeface);
 247   DCHECK(face);
 248   return face;
 249 }
 250
 251 // Creates a HarfBuzz font from the given Skia face and text size.
 252 hb_font_t* CreateHarfBuzzFont(SkTypeface* skia_face, int text_size) {
 253   typedef std::pair<hb_face_t*, GlyphCache> FaceCache;
 254
 255   // TODO(ckocagil): This shouldn't grow indefinitely. Maybe use base::MRUCache?
 256   static std::map<SkFontID, FaceCache> face_caches;
 257
 258   FaceCache* face_cache = &face_caches[skia_face->uniqueID()];
 259   if (face_cache->first == 0) {
 260     // These HarfBuzz faces live indefinitely and are intentionally leaked.
 261     ANNOTATE_SCOPED_MEMORY_LEAK;
 262     hb_face_t* harfbuzz_face = CreateHarfBuzzFace(skia_face);
 263     *face_cache = FaceCache(harfbuzz_face, GlyphCache());
 264   }
 265
 266   hb_font_t* harfbuzz_font = hb_font_create(face_cache->first);
 267
 268   const int scale = SkScalarToFixed(text_size);
 269   hb_font_set_scale(harfbuzz_font, scale, scale);
 270   FontData* hb_font_data = new FontData(&face_cache->second);
 271   hb_font_data->paint_.setTypeface(skia_face);
 272   hb_font_data->paint_.setTextSize(text_size);
 273   hb_font_set_funcs(harfbuzz_font, g_font_funcs.Get().get(), hb_font_data,
 274                     DeleteByType<FontData>);
 275   hb_font_make_immutable(harfbuzz_font);
 276   return harfbuzz_font;
 277 }
 278
 279 // Returns true if characters of |block_code| may trigger font fallback.
 280 bool IsUnusualBlockCode(UBlockCode block_code) {
 281   return block_code == UBLOCK_GEOMETRIC_SHAPES ||
 282          block_code == UBLOCK_MISCELLANEOUS_SYMBOLS;
 283 }
 284
 285 // Returns the index of the first unusual character after a usual character or
 286 // vice versa. Unusual characters are defined by |IsUnusualBlockCode|.
 287 size_t FindUnusualCharacter(const base::string16& text,
 288                             size_t run_start,
 289                             size_t run_break) {
 290   const int32 run_length = static_cast<int32>(run_break - run_start);
 291   base::i18n::UTF16CharIterator iter(text.c_str() + run_start,
 292                                      run_length);
 293   const UBlockCode first_block_code = ublock_getCode(iter.get());
 294   const bool first_block_unusual = IsUnusualBlockCode(first_block_code);
 295   while (iter.Advance() && iter.array_pos() < run_length) {
 296     const UBlockCode current_block_code = ublock_getCode(iter.get());
 297     if (current_block_code != first_block_code &&
 298         (first_block_unusual || IsUnusualBlockCode(current_block_code))) {
 299       return run_start + iter.array_pos();
 300     }
 301   }
 302   return run_break;
 303 }
 304
 305 // If the given scripts match, returns the one that isn't USCRIPT_COMMON or
 306 // USCRIPT_INHERITED, i.e. the more specific one. Otherwise returns
 307 // USCRIPT_INVALID_CODE.
 308 UScriptCode ScriptIntersect(UScriptCode first, UScriptCode second) {
 309   if (first == second ||
 310       (second > USCRIPT_INVALID_CODE && second <= USCRIPT_INHERITED)) {
 311     return first;
 312   }
 313   if (first > USCRIPT_INVALID_CODE && first <= USCRIPT_INHERITED)
 314     return second;
 315   return USCRIPT_INVALID_CODE;
 316 }
 317
 318 // Writes the script and the script extensions of the character with the
 319 // Unicode |codepoint|. Returns the number of written scripts.
 320 int GetScriptExtensions(UChar32 codepoint, UScriptCode* scripts) {
 321   UErrorCode icu_error = U_ZERO_ERROR;
 322   // ICU documentation incorrectly states that the result of
 323   // |uscript_getScriptExtensions| will contain the regular script property.
 324   // Write the character's script property to the first element.
 325   scripts[0] = uscript_getScript(codepoint, &icu_error);
 326   if (U_FAILURE(icu_error))
 327     return 0;
 328   // Fill the rest of |scripts| with the extensions.
 329   int count = uscript_getScriptExtensions(codepoint, scripts + 1,
 330                                           kMaxScripts - 1, &icu_error);
 331   if (U_FAILURE(icu_error))
 332     count = 0;
 333   return count + 1;
 334 }
 335
 336 // Intersects the script extensions set of |codepoint| with |result| and writes
 337 // to |result|, reading and updating |result_size|.
 338 void ScriptSetIntersect(UChar32 codepoint,
 339                         UScriptCode* result,
 340                         size_t* result_size) {
 341   UScriptCode scripts[kMaxScripts] = { USCRIPT_INVALID_CODE };
 342   int count = GetScriptExtensions(codepoint, scripts);
 343
 344   size_t out_size = 0;
 345
 346   for (size_t i = 0; i < *result_size; ++i) {
 347     for (int j = 0; j < count; ++j) {
 348       UScriptCode intersection = ScriptIntersect(result[i], scripts[j]);
 349       if (intersection != USCRIPT_INVALID_CODE) {
 350         result[out_size++] = intersection;
 351         break;
 352       }
 353     }
 354   }
 355
 356   *result_size = out_size;
 357 }
 358
 359 // Find the longest sequence of characters from 0 and up to |length| that
 360 // have at least one common UScriptCode value. Writes the common script value to
 361 // |script| and returns the length of the sequence. Takes the characters' script
 362 // extensions into account. http://www.unicode.org/reports/tr24/#ScriptX
 363 //
 364 // Consider 3 characters with the script values {Kana}, {Hira, Kana}, {Kana}.
 365 // Without script extensions only the first script in each set would be taken
 366 // into account, resulting in 3 runs where 1 would be enough.
 367 // TODO(ckocagil): Write a unit test for the case above.
 368 int ScriptInterval(const base::string16& text,
 369                    size_t start,
 370                    size_t length,
 371                    UScriptCode* script) {
 372   DCHECK_GT(length, 0U);
 373
 374   UScriptCode scripts[kMaxScripts] = { USCRIPT_INVALID_CODE };
 375
 376   base::i18n::UTF16CharIterator char_iterator(text.c_str() + start, length);
 377   size_t scripts_size = GetScriptExtensions(char_iterator.get(), scripts);
 378   *script = scripts[0];
 379
 380   while (char_iterator.Advance()) {
 381     ScriptSetIntersect(char_iterator.get(), scripts, &scripts_size);
 382     if (scripts_size == 0U)
 383       return char_iterator.array_pos();
 384     *script = scripts[0];
 385   }
 386
 387   return length;
 388 }
 389
 390 // A port of hb_icu_script_to_script because harfbuzz on CrOS is built without
 391 // hb-icu. See http://crbug.com/356929
 392 inline hb_script_t ICUScriptToHBScript(UScriptCode script) {
 393   if (script == USCRIPT_INVALID_CODE)
 394     return HB_SCRIPT_INVALID;
 395   return hb_script_from_string(uscript_getShortName(script), -1);
 396 }
 397
 398 }  // namespace
 399
 400 namespace internal {
 401
 402 TextRunHarfBuzz::TextRunHarfBuzz()
 403     : width(0),
 404       preceding_run_widths(0),
 405       is_rtl(false),
 406       level(0),
 407       script(USCRIPT_INVALID_CODE),
 408       glyph_count(static_cast<size_t>(-1)),
 409       font_size(0),
 410       font_style(0),
 411       strike(false),
 412       diagonal_strike(false),
 413       underline(false) {}
 414
 415 TextRunHarfBuzz::~TextRunHarfBuzz() {}
 416
 417 size_t TextRunHarfBuzz::CharToGlyph(size_t pos) const {
 418   DCHECK(range.start() <= pos && pos < range.end());
 419
 420   if (!is_rtl) {
 421     size_t cluster_start = 0;
 422     for (size_t i = 1; i < glyph_count && pos >= glyph_to_char[i]; ++i)
 423       if (glyph_to_char[i] != glyph_to_char[i - 1])
 424         cluster_start = i;
 425     return cluster_start;
 426   }
 427
 428   for (size_t i = 0; i < glyph_count; ++i) {
 429     if (pos >= glyph_to_char[i])
 430       return i;
 431   }
 432   NOTREACHED();
 433   return 0;
 434 }
 435
 436 Range TextRunHarfBuzz::CharRangeToGlyphRange(const Range& char_range) const {
 437   DCHECK(range.Contains(char_range));
 438   DCHECK(!char_range.is_reversed());
 439   DCHECK(!char_range.is_empty());
 440
 441   size_t first = 0;
 442   size_t last = 0;
 443
 444   if (is_rtl) {
 445     // For RTL runs, we subtract 1 from |char_range| to get the leading edges.
 446     last = CharToGlyph(char_range.end() - 1);
 447     // Loop until we find a non-empty glyph range. For multi-character clusters,
 448     // the loop is needed to find the cluster end. Do the same for LTR below.
 449     for (size_t i = char_range.start(); i > range.start(); --i) {
 450       first = CharToGlyph(i - 1);
 451       if (first != last)
 452         return Range(last, first);
 453     }
 454     return Range(last, glyph_count);
 455   }
 456
 457   first = CharToGlyph(char_range.start());
 458   for (size_t i = char_range.end(); i < range.end(); ++i) {
 459     last = CharToGlyph(i);
 460     if (first != last)
 461       return Range(first, last);
 462   }
 463   return Range(first, glyph_count);
 464 }
 465
 466 // Returns whether the given shaped run contains any missing glyphs.
 467 bool TextRunHarfBuzz::HasMissingGlyphs() const {
 468   static const int kMissingGlyphId = 0;
 469   for (size_t i = 0; i < glyph_count; ++i) {
 470     if (glyphs[i] == kMissingGlyphId)
 471       return true;
 472   }
 473   return false;
 474 }
 475
 476 int TextRunHarfBuzz::GetGlyphXBoundary(size_t text_index, bool trailing) const {
 477   if (text_index == range.end()) {
 478     trailing = true;
 479     --text_index;
 480   }
 481   Range glyph_range = CharRangeToGlyphRange(Range(text_index, text_index + 1));
 482   const size_t glyph_pos = (is_rtl == trailing) ?
 483       glyph_range.start() : glyph_range.end();
 484   const int x = glyph_pos < glyph_count ?
 485       SkScalarRoundToInt(positions[glyph_pos].x()) : width;
 486   return preceding_run_widths + x;
 487 }
 488
 489 }  // namespace internal
 490
 491 RenderTextHarfBuzz::RenderTextHarfBuzz()
 492     : RenderText(),
 493       needs_layout_(false) {}
 494
 495 RenderTextHarfBuzz::~RenderTextHarfBuzz() {}
 496
 497 Size RenderTextHarfBuzz::GetStringSize() {
 498   EnsureLayout();
 499   return lines()[0].size;
 500 }
 501
 502 SelectionModel RenderTextHarfBuzz::FindCursorPosition(const Point& point) {
 503   EnsureLayout();
 504
 505   int x = ToTextPoint(point).x();
 506   int offset = 0;
 507   size_t run_index = GetRunContainingXCoord(x, &offset);
 508   if (run_index >= runs_.size())
 509     return EdgeSelectionModel((x < 0) ? CURSOR_LEFT : CURSOR_RIGHT);
 510   const internal::TextRunHarfBuzz& run = *runs_[run_index];
 511
 512   for (size_t i = 0; i < run.glyph_count; ++i) {
 513     const SkScalar end =
 514         i + 1 == run.glyph_count ? run.width : run.positions[i + 1].x();
 515     const SkScalar middle = (end + run.positions[i].x()) / 2;
 516
 517     if (offset < middle) {
 518       return SelectionModel(LayoutIndexToTextIndex(
 519           run.glyph_to_char[i] + (run.is_rtl ? 1 : 0)),
 520           (run.is_rtl ? CURSOR_BACKWARD : CURSOR_FORWARD));
 521     }
 522     if (offset < end) {
 523       return SelectionModel(LayoutIndexToTextIndex(
 524           run.glyph_to_char[i] + (run.is_rtl ? 0 : 1)),
 525           (run.is_rtl ? CURSOR_FORWARD : CURSOR_BACKWARD));
 526     }
 527   }
 528   return EdgeSelectionModel(CURSOR_RIGHT);
 529 }
 530
 531 std::vector<RenderText::FontSpan> RenderTextHarfBuzz::GetFontSpansForTesting() {
 532   NOTIMPLEMENTED();
 533   return std::vector<RenderText::FontSpan>();
 534 }
 535
 536 int RenderTextHarfBuzz::GetLayoutTextBaseline() {
 537   EnsureLayout();
 538   return lines()[0].baseline;
 539 }
 540
 541 SelectionModel RenderTextHarfBuzz::AdjacentCharSelectionModel(
 542     const SelectionModel& selection,
 543     VisualCursorDirection direction) {
 544   DCHECK(!needs_layout_);
 545   internal::TextRunHarfBuzz* run;
 546   size_t run_index = GetRunContainingCaret(selection);
 547   if (run_index >= runs_.size()) {
 548     // The cursor is not in any run: we're at the visual and logical edge.
 549     SelectionModel edge = EdgeSelectionModel(direction);
 550     if (edge.caret_pos() == selection.caret_pos())
 551       return edge;
 552     int visual_index = (direction == CURSOR_RIGHT) ? 0 : runs_.size() - 1;
 553     run = runs_[visual_to_logical_[visual_index]];
 554   } else {
 555     // If the cursor is moving within the current run, just move it by one
 556     // grapheme in the appropriate direction.
 557     run = runs_[run_index];
 558     size_t caret = selection.caret_pos();
 559     bool forward_motion = run->is_rtl == (direction == CURSOR_LEFT);
 560     if (forward_motion) {
 561       if (caret < LayoutIndexToTextIndex(run->range.end())) {
 562         caret = IndexOfAdjacentGrapheme(caret, CURSOR_FORWARD);
 563         return SelectionModel(caret, CURSOR_BACKWARD);
 564       }
 565     } else {
 566       if (caret > LayoutIndexToTextIndex(run->range.start())) {
 567         caret = IndexOfAdjacentGrapheme(caret, CURSOR_BACKWARD);
 568         return SelectionModel(caret, CURSOR_FORWARD);
 569       }
 570     }
 571     // The cursor is at the edge of a run; move to the visually adjacent run.
 572     int visual_index = logical_to_visual_[run_index];
 573     visual_index += (direction == CURSOR_LEFT) ? -1 : 1;
 574     if (visual_index < 0 || visual_index >= static_cast<int>(runs_.size()))
 575       return EdgeSelectionModel(direction);
 576     run = runs_[visual_to_logical_[visual_index]];
 577   }
 578   bool forward_motion = run->is_rtl == (direction == CURSOR_LEFT);
 579   return forward_motion ? FirstSelectionModelInsideRun(run) :
 580                           LastSelectionModelInsideRun(run);
 581 }
 582
 583 SelectionModel RenderTextHarfBuzz::AdjacentWordSelectionModel(
 584     const SelectionModel& selection,
 585     VisualCursorDirection direction) {
 586   // TODO(ckocagil): This implementation currently matches RenderTextWin, but it
 587   // should match the native behavior on other platforms.
 588   if (obscured())
 589     return EdgeSelectionModel(direction);
 590
 591   base::i18n::BreakIterator iter(text(), base::i18n::BreakIterator::BREAK_WORD);
 592   bool success = iter.Init();
 593   DCHECK(success);
 594   if (!success)
 595     return selection;
 596
 597   size_t pos;
 598   if (direction == CURSOR_RIGHT) {
 599     pos = std::min(selection.caret_pos() + 1, text().length());
 600     while (iter.Advance()) {
 601       pos = iter.pos();
 602       if (iter.IsWord() && pos > selection.caret_pos())
 603         break;
 604     }
 605   } else {  // direction == CURSOR_LEFT
 606     // Notes: We always iterate words from the beginning.
 607     // This is probably fast enough for our usage, but we may
 608     // want to modify WordIterator so that it can start from the
 609     // middle of string and advance backwards.
 610     pos = std::max<int>(selection.caret_pos() - 1, 0);
 611     while (iter.Advance()) {
 612       if (iter.IsWord()) {
 613         size_t begin = iter.pos() - iter.GetString().length();
 614         if (begin == selection.caret_pos()) {
 615           // The cursor is at the beginning of a word.
 616           // Move to previous word.
 617           break;
 618         } else if (iter.pos() >= selection.caret_pos()) {
 619           // The cursor is in the middle or at the end of a word.
 620           // Move to the top of current word.
 621           pos = begin;
 622           break;
 623         }
 624         pos = iter.pos() - iter.GetString().length();
 625       }
 626     }
 627   }
 628   return SelectionModel(pos, CURSOR_FORWARD);
 629 }
 630
 631 Range RenderTextHarfBuzz::GetGlyphBounds(size_t index) {
 632   const size_t run_index =
 633       GetRunContainingCaret(SelectionModel(index, CURSOR_FORWARD));
 634   // Return edge bounds if the index is invalid or beyond the layout text size.
 635   if (run_index >= runs_.size())
 636     return Range(GetStringSize().width());
 637   const size_t layout_index = TextIndexToLayoutIndex(index);
 638   return Range(runs_[run_index]->GetGlyphXBoundary(layout_index, false),
 639                runs_[run_index]->GetGlyphXBoundary(layout_index, true));
 640 }
 641
 642 std::vector<Rect> RenderTextHarfBuzz::GetSubstringBounds(const Range& range) {
 643   DCHECK(!needs_layout_);
 644   DCHECK(Range(0, text().length()).Contains(range));
 645   Range layout_range(TextIndexToLayoutIndex(range.start()),
 646                      TextIndexToLayoutIndex(range.end()));
 647   DCHECK(Range(0, GetLayoutText().length()).Contains(layout_range));
 648
 649   std::vector<Rect> rects;
 650   if (layout_range.is_empty())
 651     return rects;
 652   std::vector<Range> bounds;
 653
 654   // Add a Range for each run/selection intersection.
 655   // TODO(msw): The bounds should probably not always be leading the range ends.
 656   for (size_t i = 0; i < runs_.size(); ++i) {
 657     const internal::TextRunHarfBuzz* run = runs_[visual_to_logical_[i]];
 658     Range intersection = run->range.Intersect(layout_range);
 659     if (intersection.IsValid()) {
 660       DCHECK(!intersection.is_reversed());
 661       Range range_x(run->GetGlyphXBoundary(intersection.start(), false),
 662                     run->GetGlyphXBoundary(intersection.end(), false));
 663       if (range_x.is_empty())
 664         continue;
 665       range_x = Range(range_x.GetMin(), range_x.GetMax());
 666       // Union this with the last range if they're adjacent.
 667       DCHECK(bounds.empty() || bounds.back().GetMax() <= range_x.GetMin());
 668       if (!bounds.empty() && bounds.back().GetMax() == range_x.GetMin()) {
 669         range_x = Range(bounds.back().GetMin(), range_x.GetMax());
 670         bounds.pop_back();
 671       }
 672       bounds.push_back(range_x);
 673     }
 674   }
 675   for (size_t i = 0; i < bounds.size(); ++i) {
 676     std::vector<Rect> current_rects = TextBoundsToViewBounds(bounds[i]);
 677     rects.insert(rects.end(), current_rects.begin(), current_rects.end());
 678   }
 679   return rects;
 680 }
 681
 682 size_t RenderTextHarfBuzz::TextIndexToLayoutIndex(size_t index) const {
 683   DCHECK_LE(index, text().length());
 684   ptrdiff_t i = obscured() ? UTF16IndexToOffset(text(), 0, index) : index;
 685   CHECK_GE(i, 0);
 686   // Clamp layout indices to the length of the text actually used for layout.
 687   return std::min<size_t>(GetLayoutText().length(), i);
 688 }
 689
 690 size_t RenderTextHarfBuzz::LayoutIndexToTextIndex(size_t index) const {
 691   if (!obscured())
 692     return index;
 693
 694   DCHECK_LE(index, GetLayoutText().length());
 695   const size_t text_index = UTF16OffsetToIndex(text(), 0, index);
 696   DCHECK_LE(text_index, text().length());
 697   return text_index;
 698 }
 699
 700 bool RenderTextHarfBuzz::IsValidCursorIndex(size_t index) {
 701   if (index == 0 || index == text().length())
 702     return true;
 703   if (!IsValidLogicalIndex(index))
 704     return false;
 705   EnsureLayout();
 706   // Disallow indices amid multi-character graphemes by checking glyph bounds.
 707   // These characters are not surrogate-pairs, but may yield a single glyph:
 708   //   \x0915\x093f - (ki) - one of many Devanagari biconsonantal conjuncts.
 709   //   \x0e08\x0e33 - (cho chan + sara am) - a Thai consonant and vowel pair.
 710   return GetGlyphBounds(index) != GetGlyphBounds(index - 1);
 711 }
 712
 713 void RenderTextHarfBuzz::ResetLayout() {
 714   needs_layout_ = true;
 715 }
 716
 717 void RenderTextHarfBuzz::EnsureLayout() {
 718   if (needs_layout_) {
 719     runs_.clear();
 720
 721     if (!GetLayoutText().empty()) {
 722       ItemizeText();
 723
 724       for (size_t i = 0; i < runs_.size(); ++i)
 725         ShapeRun(runs_[i]);
 726
 727       // Precalculate run width information.
 728       size_t preceding_run_widths = 0;
 729       for (size_t i = 0; i < runs_.size(); ++i) {
 730         internal::TextRunHarfBuzz* run = runs_[visual_to_logical_[i]];
 731         run->preceding_run_widths = preceding_run_widths;
 732         preceding_run_widths += run->width;
 733       }
 734     }
 735
 736     needs_layout_ = false;
 737     std::vector<internal::Line> empty_lines;
 738     set_lines(&empty_lines);
 739   }
 740
 741   if (lines().empty()) {
 742     std::vector<internal::Line> lines;
 743     lines.push_back(internal::Line());
 744     lines[0].baseline = font_list().GetBaseline();
 745     lines[0].size.set_height(font_list().GetHeight());
 746
 747     int current_x = 0;
 748     SkPaint paint;
 749
 750     for (size_t i = 0; i < runs_.size(); ++i) {
 751       const internal::TextRunHarfBuzz& run = *runs_[visual_to_logical_[i]];
 752       internal::LineSegment segment;
 753       segment.x_range = Range(current_x, current_x + run.width);
 754       segment.char_range = run.range;
 755       segment.run = i;
 756       lines[0].segments.push_back(segment);
 757
 758       paint.setTypeface(run.skia_face.get());
 759       paint.setTextSize(run.font_size);
 760       SkPaint::FontMetrics metrics;
 761       paint.getFontMetrics(&metrics);
 762
 763       lines[0].size.set_width(lines[0].size.width() + run.width);
 764       lines[0].size.set_height(std::max(lines[0].size.height(),
 765           SkScalarRoundToInt(metrics.fDescent - metrics.fAscent)));
 766       lines[0].baseline = std::max(lines[0].baseline,
 767                                    SkScalarRoundToInt(-metrics.fAscent));
 768     }
 769
 770     set_lines(&lines);
 771   }
 772 }
 773
 774 void RenderTextHarfBuzz::DrawVisualText(Canvas* canvas) {
 775   DCHECK(!needs_layout_);
 776   internal::SkiaTextRenderer renderer(canvas);
 777   ApplyFadeEffects(&renderer);
 778   ApplyTextShadows(&renderer);
 779
 780 #if defined(OS_WIN) || defined(OS_LINUX)
 781   renderer.SetFontRenderParams(
 782       font_list().GetPrimaryFont().GetFontRenderParams(),
 783       background_is_transparent());
 784 #endif
 785
 786   ApplyCompositionAndSelectionStyles();
 787
 788   int current_x = 0;
 789   const Vector2d line_offset = GetLineOffset(0);
 790   for (size_t i = 0; i < runs_.size(); ++i) {
 791     const internal::TextRunHarfBuzz& run = *runs_[visual_to_logical_[i]];
 792     renderer.SetTypeface(run.skia_face.get());
 793     renderer.SetTextSize(run.font_size);
 794
 795     Vector2d origin = line_offset + Vector2d(current_x, lines()[0].baseline);
 796     scoped_ptr<SkPoint[]> positions(new SkPoint[run.glyph_count]);
 797     for (size_t j = 0; j < run.glyph_count; ++j) {
 798       positions[j] = run.positions[j];
 799       positions[j].offset(SkIntToScalar(origin.x()), SkIntToScalar(origin.y()));
 800     }
 801
 802     for (BreakList<SkColor>::const_iterator it =
 803              colors().GetBreak(run.range.start());
 804          it != colors().breaks().end() && it->first < run.range.end();
 805          ++it) {
 806       const Range intersection = colors().GetRange(it).Intersect(run.range);
 807       const Range colored_glyphs = run.CharRangeToGlyphRange(intersection);
 808       // The range may be empty if a portion of a multi-character grapheme is
 809       // selected, yielding two colors for a single glyph. For now, this just
 810       // paints the glyph with a single style, but it should paint it twice,
 811       // clipped according to selection bounds. See http://crbug.com/366786
 812       if (colored_glyphs.is_empty())
 813         continue;
 814
 815       renderer.SetForegroundColor(it->second);
 816       renderer.DrawPosText(&positions[colored_glyphs.start()],
 817                            &run.glyphs[colored_glyphs.start()],
 818                            colored_glyphs.length());
 819       int width = (colored_glyphs.end() == run.glyph_count ? run.width :
 820               run.positions[colored_glyphs.end()].x()) -
 821           run.positions[colored_glyphs.start()].x();
 822       renderer.DrawDecorations(origin.x(), origin.y(), width, run.underline,
 823                                run.strike, run.diagonal_strike);
 824     }
 825
 826     current_x += run.width;
 827   }
 828
 829   renderer.EndDiagonalStrike();
 830
 831   UndoCompositionAndSelectionStyles();
 832 }
 833
 834 size_t RenderTextHarfBuzz::GetRunContainingCaret(
 835     const SelectionModel& caret) const {
 836   DCHECK(!needs_layout_);
 837   size_t layout_position = TextIndexToLayoutIndex(caret.caret_pos());
 838   LogicalCursorDirection affinity = caret.caret_affinity();
 839   for (size_t run = 0; run < runs_.size(); ++run) {
 840     if (RangeContainsCaret(runs_[run]->range, layout_position, affinity))
 841       return run;
 842   }
 843   return runs_.size();
 844 }
 845
 846 size_t RenderTextHarfBuzz::GetRunContainingXCoord(int x, int* offset) const {
 847   DCHECK(!needs_layout_);
 848   if (x < 0)
 849     return runs_.size();
 850   // Find the text run containing the argument point (assumed already offset).
 851   int current_x = 0;
 852   for (size_t i = 0; i < runs_.size(); ++i) {
 853     size_t run = visual_to_logical_[i];
 854     current_x += runs_[run]->width;
 855     if (x < current_x) {
 856       *offset = x - (current_x - runs_[run]->width);
 857       return run;
 858     }
 859   }
 860   return runs_.size();
 861 }
 862
 863 SelectionModel RenderTextHarfBuzz::FirstSelectionModelInsideRun(
 864     const internal::TextRunHarfBuzz* run) {
 865   size_t position = LayoutIndexToTextIndex(run->range.start());
 866   position = IndexOfAdjacentGrapheme(position, CURSOR_FORWARD);
 867   return SelectionModel(position, CURSOR_BACKWARD);
 868 }
 869
 870 SelectionModel RenderTextHarfBuzz::LastSelectionModelInsideRun(
 871     const internal::TextRunHarfBuzz* run) {
 872   size_t position = LayoutIndexToTextIndex(run->range.end());
 873   position = IndexOfAdjacentGrapheme(position, CURSOR_BACKWARD);
 874   return SelectionModel(position, CURSOR_FORWARD);
 875 }
 876
 877 void RenderTextHarfBuzz::ItemizeText() {
 878   const base::string16& text = GetLayoutText();
 879   const bool is_text_rtl = GetTextDirection() == base::i18n::RIGHT_TO_LEFT;
 880   DCHECK_NE(0U, text.length());
 881
 882   // If ICU fails to itemize the text, we create a run that spans the entire
 883   // text. This is needed because leaving the runs set empty causes some clients
 884   // to misbehave since they expect non-zero text metrics from a non-empty text.
 885   base::i18n::BiDiLineIterator bidi_iterator;
 886   if (!bidi_iterator.Open(text, is_text_rtl, false)) {
 887     internal::TextRunHarfBuzz* run = new internal::TextRunHarfBuzz;
 888     run->range = Range(0, text.length());
 889     runs_.push_back(run);
 890     visual_to_logical_ = logical_to_visual_ = std::vector<int32_t>(1, 0);
 891     return;
 892   }
 893
 894   // Temporarily apply composition underlines and selection colors.
 895   ApplyCompositionAndSelectionStyles();
 896
 897   // Build the list of runs from the script items and ranged styles. Use an
 898   // empty color BreakList to avoid breaking runs at color boundaries.
 899   BreakList<SkColor> empty_colors;
 900   empty_colors.SetMax(text.length());
 901   internal::StyleIterator style(empty_colors, styles());
 902
 903   for (size_t run_break = 0; run_break < text.length();) {
 904     internal::TextRunHarfBuzz* run = new internal::TextRunHarfBuzz;
 905     run->range.set_start(run_break);
 906     run->font_style = (style.style(BOLD) ? Font::BOLD : 0) |
 907                       (style.style(ITALIC) ? Font::ITALIC : 0);
 908     run->strike = style.style(STRIKE);
 909     run->diagonal_strike = style.style(DIAGONAL_STRIKE);
 910     run->underline = style.style(UNDERLINE);
 911
 912     int32 script_item_break = 0;
 913     bidi_iterator.GetLogicalRun(run_break, &script_item_break, &run->level);
 914     // Odd BiDi embedding levels correspond to RTL runs.
 915     run->is_rtl = (run->level % 2) == 1;
 916     // Find the length and script of this script run.
 917     script_item_break = ScriptInterval(text, run_break,
 918         script_item_break - run_break, &run->script) + run_break;
 919
 920     // Find the next break and advance the iterators as needed.
 921     run_break = std::min(static_cast<size_t>(script_item_break),
 922                          TextIndexToLayoutIndex(style.GetRange().end()));
 923
 924     // Break runs adjacent to character substrings in certain code blocks.
 925     // This avoids using their fallback fonts for more characters than needed,
 926     // in cases like "\x25B6 Media Title", etc. http://crbug.com/278913
 927     if (run_break > run->range.start())
 928       run_break = FindUnusualCharacter(text, run->range.start(), run_break);
 929
 930     DCHECK(IsValidCodePointIndex(text, run_break));
 931     style.UpdatePosition(LayoutIndexToTextIndex(run_break));
 932     run->range.set_end(run_break);
 933
 934     runs_.push_back(run);
 935   }
 936
 937   // Undo the temporarily applied composition underlines and selection colors.
 938   UndoCompositionAndSelectionStyles();
 939
 940   const size_t num_runs = runs_.size();
 941   std::vector<UBiDiLevel> levels(num_runs);
 942   for (size_t i = 0; i < num_runs; ++i)
 943     levels[i] = runs_[i]->level;
 944   visual_to_logical_.resize(num_runs);
 945   ubidi_reorderVisual(&levels[0], num_runs, &visual_to_logical_[0]);
 946   logical_to_visual_.resize(num_runs);
 947   ubidi_reorderLogical(&levels[0], num_runs, &logical_to_visual_[0]);
 948 }
 949
 950 void RenderTextHarfBuzz::ShapeRun(internal::TextRunHarfBuzz* run) {
 951   const base::string16& text = GetLayoutText();
 952   // TODO(ckocagil|yukishiino): Implement font fallback.
 953   const Font& primary_font = font_list().GetPrimaryFont();
 954   run->skia_face = internal::CreateSkiaTypeface(primary_font.GetFontName(),
 955                                                 run->font_style);
 956   run->font_size = primary_font.GetFontSize();
 957
 958   hb_font_t* harfbuzz_font = CreateHarfBuzzFont(run->skia_face.get(),
 959                                                 run->font_size);
 960
 961   // Create a HarfBuzz buffer and add the string to be shaped. The HarfBuzz
 962   // buffer holds our text, run information to be used by the shaping engine,
 963   // and the resulting glyph data.
 964   hb_buffer_t* buffer = hb_buffer_create();
 965   hb_buffer_add_utf16(buffer, reinterpret_cast<const uint16*>(text.c_str()),
 966                       text.length(), run->range.start(), run->range.length());
 967   hb_buffer_set_script(buffer, ICUScriptToHBScript(run->script));
 968   hb_buffer_set_direction(buffer,
 969       run->is_rtl ? HB_DIRECTION_RTL : HB_DIRECTION_LTR);
 970   // TODO(ckocagil): Should we determine the actual language?
 971   hb_buffer_set_language(buffer, hb_language_get_default());
 972
 973   // Shape the text.
 974   hb_shape(harfbuzz_font, buffer, NULL, 0);
 975
 976   // Populate the run fields with the resulting glyph data in the buffer.
 977   unsigned int glyph_count = 0;
 978   hb_glyph_info_t* infos = hb_buffer_get_glyph_infos(buffer, &glyph_count);
 979   hb_glyph_position_t* hb_positions = hb_buffer_get_glyph_positions(buffer,
 980                                                                     NULL);
 981   run->glyph_count = glyph_count;
 982   run->glyphs.reset(new uint16[run->glyph_count]);
 983   run->glyph_to_char.reset(new uint32[run->glyph_count]);
 984   run->positions.reset(new SkPoint[run->glyph_count]);
 985   for (size_t i = 0; i < run->glyph_count; ++i) {
 986     run->glyphs[i] = infos[i].codepoint;
 987     run->glyph_to_char[i] = infos[i].cluster;
 988     const int x_offset =
 989         SkScalarRoundToInt(SkFixedToScalar(hb_positions[i].x_offset));
 990     const int y_offset =
 991         SkScalarRoundToInt(SkFixedToScalar(hb_positions[i].y_offset));
 992     run->positions[i].set(run->width + x_offset, -y_offset);
 993     run->width +=
 994         SkScalarRoundToInt(SkFixedToScalar(hb_positions[i].x_advance));
 995   }
 996
 997   hb_buffer_destroy(buffer);
 998   hb_font_destroy(harfbuzz_font);
 999 }
1000
1001 }  // namespace gfx