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

ui/gfx/render_text_harfbuzz.cc

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "ui/gfx/render_text_harfbuzz.h"
 
 #include <map>
 
 #include "base/debug/leak_annotations.h"
 #include "base/i18n/bidi_line_iterator.h"
@@ skipping 381 matching lines @@
 }
 
 // A port of hb_icu_script_to_script because harfbuzz on CrOS is built without
 // hb-icu. See http://crbug.com/356929
 inline hb_script_t ICUScriptToHBScript(UScriptCode script) {
   if (script == USCRIPT_INVALID_CODE)
     return HB_SCRIPT_INVALID;
   return hb_script_from_string(uscript_getShortName(script), -1);
 }
 
+template <class Iterator>
+void GetClusterAtImpl(size_t pos,
+                      Range range,
+                      Iterator elements_begin,
+                      Iterator elements_end,
+                      bool reversed,
+                      Range* chars,
+                      Range* glyphs) {
+  Iterator element = std::upper_bound(elements_begin, elements_end, pos);
+  chars->set_end(element == elements_end ? range.end() : *element);
+  glyphs->set_end(reversed ? elements_end - element : element - elements_begin);
+
+  DCHECK(element != elements_begin);

[msw, 2014/06/29 22:29:09]

nit: can you DCHECK_NE?

[ckocagil, 2014/07/24 21:46:56]

It doesn't compile with DCHECK_NE due to some template error.

[msw, 2014/07/25 00:36:59]

Acknowledged.

+  do {
+    --element;

[msw, 2014/06/29 22:29:09]

nit: maybe just make this a one-liner "while(--element != ...);"?

[ckocagil, 2014/07/24 21:46:56]

Done.

+  } while (element != elements_begin && *element == element[-1]);

[msw, 2014/06/29 22:29:09]

nit: Checking for |element[-1]| is a bit odd, can you use *(element - 1)?

[ckocagil, 2014/07/24 21:46:55]

Done.

+  chars->set_start(*element);
+  glyphs->set_start(reversed ?

[msw, 2014/06/29 22:29:10]

nit: move "reversed ?" to the next line.

[ckocagil, 2014/07/24 21:46:55]

Done.

+      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 {
 
 TextRunHarfBuzz::TextRunHarfBuzz()
     : width(0),
       preceding_run_widths(0),
       is_rtl(false),
       level(0),
       script(USCRIPT_INVALID_CODE),
       glyph_count(-1),
       font_size(0),
       font_style(0),
       strike(false),
       diagonal_strike(false),
       underline(false) {}
 
 TextRunHarfBuzz::~TextRunHarfBuzz() {}
 
-size_t TextRunHarfBuzz::CharToGlyph(size_t pos) const {
-  DCHECK(range.start() <= pos && pos < range.end());
+void TextRunHarfBuzz::GetClusterAt(size_t pos,

[msw, 2014/06/29 22:29:09]

Hmm, It might make more sense to just offer GetCharsAt and GetGlyphsAt.
(you could avoid temp Ranges, and might be able to inline the impls)

[ckocagil, 2014/07/24 21:46:55]

But in the cases where we need both, we'd have to make two calls and do twice
the computation. Maybe I should make the pointers non-optional to prevent temps.

I changed the temp here a bit, please take another look.

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

That's fair; it's a careful balance between perf and simplicity sometimes.

+                                   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;
+  scoped_ptr<Range> temp_chars;
+  scoped_ptr<Range> temp_glyphs;
+  if (!chars) {
+    temp_chars.reset(new Range);
+    chars = temp_chars.get();
+  }
+  if (!glyphs) {
+    temp_glyphs.reset(new Range);
+    glyphs = temp_glyphs.get();
   }
 
-  for (size_t i = 0; i < glyph_count; ++i) {
-    if (pos >= glyph_to_char[i])
-      return i;
+  if (is_rtl) {
+    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 {
   DCHECK(range.Contains(char_range));
   DCHECK(!char_range.is_reversed());
   DCHECK(!char_range.is_empty());
 
-  size_t first = 0;
-  size_t last = 0;
+  Range start_glyphs;
+  Range end_glyphs;
+  GetClusterAt(char_range.start(), NULL, &start_glyphs);
+  GetClusterAt(char_range.end() - 1, NULL, &end_glyphs);
 
-  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);
-  }
-
-  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());
 }
 
 // Returns whether the given shaped run contains any missing glyphs.
 bool TextRunHarfBuzz::HasMissingGlyphs() const {
   static const int kMissingGlyphId = 0;
   for (size_t i = 0; i < glyph_count; ++i) {
     if (glyphs[i] == kMissingGlyphId)
       return true;
   }
   return false;
 }
 
-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/06/29 22:29:09]

Perhaps GetGraphemeBounds could also be a RenderText method.
(avoids the need to pass in the text, or an iterator)

[ckocagil, 2014/07/24 21:46:56]

I actually want to move more logic to TextRunHarfBuzz and eventually make it a
proper class, and moving this function to RTHB would be against that direction.

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

Acknowledged.

+                                         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;
+
+  if (chars.length() != 1) {

[msw, 2014/06/29 22:29:09]

This block needs a comment about the bounds treatment of multi-char graphemes.

[ckocagil, 2014/07/24 21:46:56]

Done.

+    base::i18n::BreakIterator* grapheme_iterator = GetGraphemeIterator(text);
+    if (grapheme_iterator) {
+      int before = 0;
+      int total = 0;
+      for (size_t i = chars.start(); i < chars.end(); ++i) {

[msw, 2014/06/29 22:29:09]

Should we instead calculate and store all the grapheme bounds in the run,
instead of doing this extra logic each time the bounds are requested? 

[ckocagil, 2014/07/24 21:46:56]

It seems like ICU is caching bounds internally. Even if I'm wrong and it
doesn't, I would still say this is okay and prefer not doing any optimization
without profiling.

[msw, 2014/07/25 00:36:59]

Acknowledged.

+        if (grapheme_iterator->IsGraphemeBoundary(i - range.start())) {
+          if (i < text_index)
+            ++before;
+          ++total;
+        }
+      }
+
+      if (is_rtl)
+        before = total - before - 1;
+      if (total <= 1) {

[msw, 2014/06/29 22:29:10]

Could total ever really be 0? (DCHECK against that if not). If we are getting
the range of chars for the whole grapheme, and iterating over all of them above,
at least the first char should be a boundary, right?

[ckocagil, 2014/07/24 21:46:56]

You're right, I added a DCHECK.

+        return Range(preceding_run_widths + cluster_begin_x,

[msw, 2014/06/29 22:29:09]

Optionally reverse the conditional to execute the code below, and otherwise fall
through to the return statement at the bottom of the function.

[ckocagil, 2014/07/24 21:46:56]

Done.

+                     preceding_run_widths + cluster_end_x);
+      }
+      DCHECK_GE(before, 0);

[msw, 2014/06/29 22:29:09]

Wouldn't this be false if the index was the first of a multi-char grapheme?

[ckocagil, 2014/07/24 21:46:56]

I don't understand the question. Perhaps you read this as DCHECK_GT?

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

Yeah, I think you're right, ignore that question.

+      DCHECK_LE(before, total);
+
+      const int cluster_width = cluster_end_x - cluster_begin_x;
+      int grapheme_begin_x = cluster_begin_x;
+      if (before > 0) {
+        grapheme_begin_x += static_cast<int>(0.5f +
+            cluster_width * before / static_cast<float>(total));
+      }
+      int grapheme_end_x = cluster_end_x;
+      if (before != total - 1) {
+        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);
+}
+
+base::i18n::BreakIterator* TextRunHarfBuzz::GetGraphemeIterator(

[msw, 2014/06/29 22:29:09]

It seems like the RenderText should have an iterator, not each run.

[ckocagil, 2014/07/24 21:46:55]

Done.

+    const base::string16& text) {
+  if (!grapheme_iterator.get()) {
+    grapheme_iterator.reset(new base::i18n::BreakIterator(
+        base::string16(), base::i18n::BreakIterator::BREAK_CHARACTER));
+    if (!grapheme_iterator->Init() || !grapheme_iterator->SetText(
+            text.c_str() + range.start(), range.length())) {
+      NOTREACHED();
+      return NULL;
+    }
+  }
+  return grapheme_iterator.get();
 }
 
 }  // namespace internal
 
 RenderTextHarfBuzz::RenderTextHarfBuzz()
     : RenderText(),
       needs_layout_(false) {}
 
 RenderTextHarfBuzz::~RenderTextHarfBuzz() {}
 
@@ skipping 125 matching lines @@
           break;
         }
         pos = iter.pos() - iter.GetString().length();
       }
     }
   }
   return SelectionModel(pos, CURSOR_FORWARD);
 }
 
 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(), layout_index);
+  return run->is_rtl ? Range(bounds.end(), bounds.start()) : bounds;
 }
 
 std::vector<Rect> RenderTextHarfBuzz::GetSubstringBounds(const Range& range) {
   DCHECK(!needs_layout_);
   DCHECK(Range(0, text().length()).Contains(range));
   Range layout_range(TextIndexToLayoutIndex(range.start()),
                      TextIndexToLayoutIndex(range.end()));
   DCHECK(Range(0, GetLayoutText().length()).Contains(layout_range));
 
   std::vector<Rect> rects;
   if (layout_range.is_empty())
     return rects;
   std::vector<Range> bounds;
 
   // Add a Range for each run/selection intersection.
   // TODO(msw): The bounds should probably not always be leading the range ends.
   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));
+      Range range_x(
+          run->GetGraphemeBounds(GetLayoutText(), run->is_rtl ?
+              intersection.end() - 1 : intersection.start()).start(),
+          run->GetGraphemeBounds(GetLayoutText(), run->is_rtl ?
+              intersection.start() : intersection.end() - 1).end());
       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);
@@ skipping 23 matching lines @@
   DCHECK_LE(text_index, text().length());
   return text_index;
 }
 
 bool RenderTextHarfBuzz::IsValidCursorIndex(size_t index) {
   if (index == 0 || index == text().length())
     return true;
   if (!IsValidLogicalIndex(index))
     return false;
   EnsureLayout();
-  // Disallow indices amid multi-character graphemes by checking glyph bounds.

[msw, 2014/06/29 22:29:09]

Please verify that these examples and Issue 327903 haven't regressed.

[ckocagil, 2014/07/24 21:46:56]

Done. Added a test too.

-  // 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))];
+  base::i18n::BreakIterator* grapheme_iterator =

[msw, 2014/06/29 22:29:09]

nit: Name this |iter| for a one-liner and below "return iter && iter->Is...".

[ckocagil, 2014/07/24 21:46:56]

Done. (I made it "return !iter || iter->...") since we return true when iter is
null.

[msw, 2014/07/25 00:36:59]

Acknowledged.

+      run->GetGraphemeIterator(GetLayoutText());
+  if (!grapheme_iterator)
+    return true;
+  return grapheme_iterator->IsGraphemeBoundary(index - run->range.start());
 }
 
 void RenderTextHarfBuzz::ResetLayout() {
   needs_layout_ = true;
 }
 
 void RenderTextHarfBuzz::EnsureLayout() {
   if (needs_layout_) {
     runs_.clear();
 
@@ skipping 257 matching lines @@
   // Shape the text.
   hb_shape(harfbuzz_font, buffer, NULL, 0);
 
   // Populate the run fields with the resulting glyph data in the buffer.
   unsigned int glyph_count = 0;
   hb_glyph_info_t* infos = hb_buffer_get_glyph_infos(buffer, &glyph_count);
   hb_glyph_position_t* hb_positions = hb_buffer_get_glyph_positions(buffer,
                                                                     NULL);
   run->glyph_count = glyph_count;
   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]);
   for (size_t i = 0; i < run->glyph_count; ++i) {
     run->glyphs[i] = infos[i].codepoint;
     run->glyph_to_char[i] = infos[i].cluster;
     const int x_offset =
         SkScalarRoundToInt(SkFixedToScalar(hb_positions[i].x_offset));
     const int y_offset =
         SkScalarRoundToInt(SkFixedToScalar(hb_positions[i].y_offset));
     run->positions[i].set(run->width + x_offset, y_offset);
     run->width +=
         SkScalarRoundToInt(SkFixedToScalar(hb_positions[i].x_advance));
   }
 
   hb_buffer_destroy(buffer);
   hb_font_destroy(harfbuzz_font);
 }
 
 }  // namespace gfx