RenderTextHarfBuzz: Allow mid-glyph cursors in multi-grapheme clusters

ui/gfx/render_text_harfbuzz.cc

Index: ui/gfx/render_text_harfbuzz.cc
diff --git a/ui/gfx/render_text_harfbuzz.cc b/ui/gfx/render_text_harfbuzz.cc
index 8d332e3c147b737dfa3a311b6058c16fef1d080a..0b66d5c0c99fae8ed2f07a8884bdf6e1574f1f31 100644
--- a/ui/gfx/render_text_harfbuzz.cc
+++ b/ui/gfx/render_text_harfbuzz.cc
@@ -400,6 +400,32 @@ inline hb_script_t ICUScriptToHBScript(UScriptCode script) {
   return hb_script_from_string(uscript_getShortName(script), -1);
 }
 
+template <class Iterator>
+void GetClusterAtImpl(size_t pos,

[msw, 2014/07/25 00:37:01]

nit: Add a simple comment.

[ckocagil, 2014/07/29 23:13:41]

Done.

+                      Range range,
+                      Iterator elements_begin,
+                      Iterator elements_end,
+                      bool reversed,
+                      Range* chars,
+                      Range* glyphs) {
+  Iterator element = std::upper_bound(elements_begin, elements_end, pos);
+  chars->set_end(element == elements_end ? range.end() : *element);
+  glyphs->set_end(reversed ? elements_end - element : element - elements_begin);
+
+  DCHECK(element != elements_begin);
+  while (--element != elements_begin && *element == *(element - 1));
+  chars->set_start(*element);
+  glyphs->set_start(
+      reversed ? elements_end - element : element - elements_begin);
+  if (reversed)
+    *glyphs = Range(glyphs->end(), glyphs->start());
+
+  DCHECK(!chars->is_reversed());
+  DCHECK(!chars->is_empty());
+  DCHECK(!glyphs->is_reversed());
+  DCHECK(!glyphs->is_empty());
+}
+
 }  // namespace
 
 namespace internal {
@@ -419,23 +445,25 @@ TextRunHarfBuzz::TextRunHarfBuzz()
 
 TextRunHarfBuzz::~TextRunHarfBuzz() {}
 
-size_t TextRunHarfBuzz::CharToGlyph(size_t pos) const {
-  DCHECK(range.start() <= pos && pos < range.end());
+void TextRunHarfBuzz::GetClusterAt(size_t pos,
+                                   Range* chars,
+                                   Range* glyphs) const {
+  DCHECK(range.Contains(Range(pos, pos + 1)));
 
-  if (!is_rtl) {
-    size_t cluster_start = 0;
-    for (size_t i = 1; i < glyph_count && pos >= glyph_to_char[i]; ++i)
-      if (glyph_to_char[i] != glyph_to_char[i - 1])
-        cluster_start = i;
-    return cluster_start;
-  }
+  Range temp_range;

[msw, 2014/07/25 00:37:01]

optional nit: The only NULL being sent in is |chars| from CharRangeToGlyphRange.
Just make that send in an otherwise unused non-NULL Range, then you can remove
this |temp_range| behavior (and maybe DCHECK for |chars| and |glyphs|).

[ckocagil, 2014/07/29 23:13:41]

Done.

+  if (!chars)
+    chars = &temp_range;
+  if (!glyphs)
+    glyphs = &temp_range;
 
-  for (size_t i = 0; i < glyph_count; ++i) {
-    if (pos >= glyph_to_char[i])
-      return i;
+  if (is_rtl) {

[msw, 2014/07/25 00:37:01]

optional nit: instead do:

Iterator begin = glyph_to_char.begin();
Iterator end = glyph_to_char.begin();
if (rtl) {
  begin = glyph_to_char.rbegin();
  end = glyph_to_char.rend();
}

GetClusterAtImpl(pos, range, begin, end, is_rtl, chars, glyphs);

[ckocagil, 2014/07/29 23:13:41]

.begin() and .rbegin() return incompatible types (which is why we have the
template function GetClusterAtImpl).

+    GetClusterAtImpl(pos, range, glyph_to_char.rbegin(), glyph_to_char.rend(),
+        true, chars, glyphs);
+    return;
   }
-  NOTREACHED();
-  return 0;
+
+  GetClusterAtImpl(pos, range, glyph_to_char.begin(), glyph_to_char.end(),
+      false, chars, glyphs);
 }
 
 Range TextRunHarfBuzz::CharRangeToGlyphRange(const Range& char_range) const {
@@ -443,29 +471,13 @@ Range TextRunHarfBuzz::CharRangeToGlyphRange(const Range& char_range) const {
   DCHECK(!char_range.is_reversed());
   DCHECK(!char_range.is_empty());
 
-  size_t first = 0;
-  size_t last = 0;
-
-  if (is_rtl) {
-    // For RTL runs, we subtract 1 from |char_range| to get the leading edges.
-    last = CharToGlyph(char_range.end() - 1);
-    // Loop until we find a non-empty glyph range. For multi-character clusters,
-    // the loop is needed to find the cluster end. Do the same for LTR below.
-    for (size_t i = char_range.start(); i > range.start(); --i) {
-      first = CharToGlyph(i - 1);
-      if (first != last)
-        return Range(last, first);
-    }
-    return Range(last, glyph_count);
-  }
+  Range start_glyphs;
+  Range end_glyphs;
+  GetClusterAt(char_range.start(), NULL, &start_glyphs);
+  GetClusterAt(char_range.end() - 1, NULL, &end_glyphs);
 
-  first = CharToGlyph(char_range.start());
-  for (size_t i = char_range.end(); i < range.end(); ++i) {
-    last = CharToGlyph(i);
-    if (first != last)
-      return Range(first, last);
-  }
-  return Range(first, glyph_count);
+  return is_rtl ? Range(end_glyphs.start(), start_glyphs.end()) :
+      Range(start_glyphs.start(), end_glyphs.end());
 }
 
 size_t TextRunHarfBuzz::CountMissingGlyphs() const {
@@ -476,17 +488,50 @@ size_t TextRunHarfBuzz::CountMissingGlyphs() const {
   return missing;
 }
 
-int TextRunHarfBuzz::GetGlyphXBoundary(size_t text_index, bool trailing) const {
-  if (text_index == range.end()) {
-    trailing = true;
-    --text_index;
+Range TextRunHarfBuzz::GetGraphemeBounds(const base::string16& text,

[msw, 2014/07/25 00:37:01]

Remove |text|, it's no longer used here.

[ckocagil, 2014/07/29 23:13:41]

Done.

+    base::i18n::BreakIterator* grapheme_iterator,
+    size_t text_index) {
+  DCHECK_LT(text_index, range.end());
+
+  Range chars;
+  Range glyphs;
+  GetClusterAt(text_index, &chars, &glyphs);
+  const int cluster_begin_x = SkScalarRoundToInt(positions[glyphs.start()].x());
+  const int cluster_end_x = glyphs.end() < glyph_count ?
+      SkScalarRoundToInt(positions[glyphs.end()].x()) : width;
+
+  // A cluster consists of a number of code points and corresponds to a number
+  // of glyphs that should be drawn together. A cluster can contain multiple
+  // graphemes. In order to place the cursor at a grapheme boundary inside the
+  // cluster, we simple divide the cluster width by the number of graphemes.

[msw, 2014/07/25 00:37:00]

nit: s/simple/simply

[ckocagil, 2014/07/29 23:13:41]

Done.

+  if (chars.length() != 1 && grapheme_iterator) {

[msw, 2014/07/25 00:37:01]

nit: explicitly check |chars.length() > 1|.

[ckocagil, 2014/07/29 23:13:41]

Done.

+    int before = 0;
+    int total = 0;
+    for (size_t i = chars.start(); i < chars.end(); ++i) {
+      if (grapheme_iterator->IsGraphemeBoundary(i)) {
+        if (i < text_index)
+          ++before;
+        ++total;
+      }
+    }
+    DCHECK_GT(total, 0);
+    if (total > 1) {
+      if (is_rtl)
+        before = total - before - 1;
+      DCHECK_GE(before, 0);
+      DCHECK_LT(before, total);
+      const int cluster_width = cluster_end_x - cluster_begin_x;
+      const int grapheme_begin_x = cluster_begin_x + static_cast<int>(0.5f +
+          cluster_width * before / static_cast<float>(total));
+      const int grapheme_end_x = cluster_begin_x + static_cast<int>(0.5f +
+          cluster_width * (before + 1) / static_cast<float>(total));
+      return Range(preceding_run_widths + grapheme_begin_x,
+                   preceding_run_widths + grapheme_end_x);
+    }
   }
-  Range glyph_range = CharRangeToGlyphRange(Range(text_index, text_index + 1));
-  const size_t glyph_pos = (is_rtl == trailing) ?
-      glyph_range.start() : glyph_range.end();
-  const int x = glyph_pos < glyph_count ?
-      SkScalarRoundToInt(positions[glyph_pos].x()) : width;
-  return preceding_run_widths + x;
+
+  return Range(preceding_run_widths + cluster_begin_x,
+               preceding_run_widths + cluster_end_x);
 }
 
 }  // namespace internal
@@ -632,14 +677,17 @@ SelectionModel RenderTextHarfBuzz::AdjacentWordSelectionModel(
 }
 
 Range RenderTextHarfBuzz::GetGlyphBounds(size_t index) {
+  EnsureLayout();
   const size_t run_index =
       GetRunContainingCaret(SelectionModel(index, CURSOR_FORWARD));
   // Return edge bounds if the index is invalid or beyond the layout text size.
   if (run_index >= runs_.size())
     return Range(GetStringSize().width());
   const size_t layout_index = TextIndexToLayoutIndex(index);
-  return Range(runs_[run_index]->GetGlyphXBoundary(layout_index, false),
-               runs_[run_index]->GetGlyphXBoundary(layout_index, true));
+  internal::TextRunHarfBuzz* run = runs_[run_index];
+  Range bounds = run->GetGraphemeBounds(GetLayoutText(), grapheme_iterator(),
+      layout_index);
+  return run->is_rtl ? Range(bounds.end(), bounds.start()) : bounds;
 }
 
 std::vector<Rect> RenderTextHarfBuzz::GetSubstringBounds(const Range& range) {
@@ -657,23 +705,29 @@ std::vector<Rect> RenderTextHarfBuzz::GetSubstringBounds(const Range& range) {
   // Add a Range for each run/selection intersection.
   // TODO(msw): The bounds should probably not always be leading the range ends.

[msw, 2014/07/25 00:37:00]

nit: I think you're resolving this TODO here by getting the outer grapheme
bounds of the range ends; if you concur, you can remove the TODO.

[ckocagil, 2014/07/29 23:13:41]

I don't quite understand this TODO, I will remove it if you can confirm it is
resolved.

[msw, 2014/07/29 23:41:13]

Yeah, you can remove this TODO (at worst the bug will live on for now).

[ckocagil, 2014/07/30 00:15:25]

Done.

   for (size_t i = 0; i < runs_.size(); ++i) {
-    const internal::TextRunHarfBuzz* run = runs_[visual_to_logical_[i]];
+    internal::TextRunHarfBuzz* run = runs_[visual_to_logical_[i]];
     Range intersection = run->range.Intersect(layout_range);
-    if (intersection.IsValid()) {
-      DCHECK(!intersection.is_reversed());
-      Range range_x(run->GetGlyphXBoundary(intersection.start(), false),
-                    run->GetGlyphXBoundary(intersection.end(), false));
-      if (range_x.is_empty())
-        continue;
-      range_x = Range(range_x.GetMin(), range_x.GetMax());
-      // Union this with the last range if they're adjacent.
-      DCHECK(bounds.empty() || bounds.back().GetMax() <= range_x.GetMin());
-      if (!bounds.empty() && bounds.back().GetMax() == range_x.GetMin()) {
-        range_x = Range(bounds.back().GetMin(), range_x.GetMax());
-        bounds.pop_back();
-      }
-      bounds.push_back(range_x);
+    if (!intersection.IsValid())
+      continue;
+    DCHECK(!intersection.is_reversed());
+    const Range leftmost_character_x = run->GetGraphemeBounds(GetLayoutText(),
+        grapheme_iterator(),
+        run->is_rtl ? intersection.end() - 1 : intersection.start());
+    const Range rightmost_character_x = run->GetGraphemeBounds(GetLayoutText(),
+        grapheme_iterator(),
+        run->is_rtl ? intersection.start() : intersection.end() - 1);
+    Range range_x(leftmost_character_x.start(), rightmost_character_x.end());

[msw, 2014/07/25 00:37:01]

nit: It looks like the revised logic should always yield a non-reversed
x-coordinate range; if you concur, please DCHECK(!range_x.is_reversed()) and
remove the line 723 operation to fix reversed ranges.

[ckocagil, 2014/07/29 23:13:41]

Done.

+
+    if (range_x.is_empty())
+      continue;
+    range_x = Range(range_x.GetMin(), range_x.GetMax());
+    // Union this with the last range if they're adjacent.
+    DCHECK(bounds.empty() || bounds.back().GetMax() <= range_x.GetMin());
+    if (!bounds.empty() && bounds.back().GetMax() == range_x.GetMin()) {
+      range_x = Range(bounds.back().GetMin(), range_x.GetMax());
+      bounds.pop_back();
     }
+    bounds.push_back(range_x);
   }
   for (size_t i = 0; i < bounds.size(); ++i) {
     std::vector<Rect> current_rects = TextBoundsToViewBounds(bounds[i]);
@@ -706,11 +760,9 @@ bool RenderTextHarfBuzz::IsValidCursorIndex(size_t index) {
   if (!IsValidLogicalIndex(index))
     return false;
   EnsureLayout();
-  // Disallow indices amid multi-character graphemes by checking glyph bounds.
-  // These characters are not surrogate-pairs, but may yield a single glyph:
-  //   \x0915\x093f - (ki) - one of many Devanagari biconsonantal conjuncts.
-  //   \x0e08\x0e33 - (cho chan + sara am) - a Thai consonant and vowel pair.
-  return GetGlyphBounds(index) != GetGlyphBounds(index - 1);
+  internal::TextRunHarfBuzz* run =
+      runs_[GetRunContainingCaret(SelectionModel(index, CURSOR_BACKWARD))];
+  return !grapheme_iterator() || grapheme_iterator()->IsGraphemeBoundary(index);
 }
 
 void RenderTextHarfBuzz::ResetLayout() {
@@ -1023,7 +1075,7 @@ void RenderTextHarfBuzz::ShapeRunWithFont(internal::TextRunHarfBuzz* run,
   hb_glyph_position_t* hb_positions =
       hb_buffer_get_glyph_positions(buffer, NULL);
   run->glyphs.reset(new uint16[run->glyph_count]);
-  run->glyph_to_char.reset(new uint32[run->glyph_count]);
+  run->glyph_to_char.resize(run->glyph_count);
   run->positions.reset(new SkPoint[run->glyph_count]);
   run->width = 0;
   for (size_t i = 0; i < run->glyph_count; ++i) {