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