Optimize GraphemeClusterSegmentFinder performance

This CL utilized minikin:isGraphemeBreak to compute all grapheme break indices when creating GraphemeClusterSegmentFinder. This makes all methods (such as #nextStartBoundary) of GraphemeClusterSegmentFinder O(1) instead of O(n).

Bug: 271004887
Test: atest TextViewHandwritingGestureTest
Change-Id: I61c1f2c45123a584456b4860b72cd4fdc84c5f1c

6 files changed, 179 insertions, 24 deletions

diff --git a/core/java/android/text/GraphemeClusterSegmentFinder.java b/core/java/android/text/GraphemeClusterSegmentFinder.java
index 656774f66792..0f6fdaf23c65 100644
--- a/core/java/android/text/GraphemeClusterSegmentFinder.java
+++ b/core/java/android/text/GraphemeClusterSegmentFinder.java
@@ -18,7 +18,8 @@ package android.text;
 
 import android.annotation.IntRange;
 import android.annotation.NonNull;
-import android.graphics.Paint;
+import android.graphics.TemporaryBuffer;
+import android.graphics.text.GraphemeBreak;
 
 /**
  * Implementation of {@code SegmentFinder} using grapheme clusters as the text segment. Whitespace
@@ -31,8 +32,8 @@ import android.graphics.Paint;
  *     Segmentation - Grapheme Cluster Boundaries</a>
  */
 public class GraphemeClusterSegmentFinder extends SegmentFinder {
-    private final CharSequence mText;
-    private final TextPaint mTextPaint;
+    private static AutoGrowArray.FloatArray sTempAdvances = null;
+    private final boolean[] mIsGraphemeBreak;
 
     /**
      * Constructs a GraphemeClusterSegmentFinder instance for the specified text which uses the
@@ -43,51 +44,73 @@ public class GraphemeClusterSegmentFinder extends SegmentFinder {
      */
     public GraphemeClusterSegmentFinder(
             @NonNull CharSequence text, @NonNull TextPaint textPaint) {
-        mText = text;
-        mTextPaint = textPaint;
+
+        if (sTempAdvances == null) {
+            sTempAdvances = new AutoGrowArray.FloatArray(text.length());
+        } else if (sTempAdvances.size() < text.length()) {
+            sTempAdvances.resize(text.length());
+        }
+
+        mIsGraphemeBreak = new boolean[text.length()];
+        float[] advances = sTempAdvances.getRawArray();
+        char[] chars = TemporaryBuffer.obtain(text.length());
+
+        TextUtils.getChars(text, 0, text.length(), chars, 0);
+
+        textPaint.getTextWidths(chars, 0, text.length(), advances);
+
+        GraphemeBreak.isGraphemeBreak(advances, chars, /* start= */ 0, /* end= */ text.length(),
+                mIsGraphemeBreak);
+        TemporaryBuffer.recycle(chars);
+    }
+
+    private int previousBoundary(@IntRange(from = 0) int offset) {
+        if (offset <= 0) return DONE;
+        do {
+            --offset;
+        } while (offset > 0 && !mIsGraphemeBreak[offset]);
+        return offset;
+    }
+
+    private int nextBoundary(@IntRange(from = 0) int offset) {
+        if (offset >= mIsGraphemeBreak.length) return DONE;
+        do {
+            ++offset;
+        } while (offset < mIsGraphemeBreak.length && !mIsGraphemeBreak[offset]);
+        return offset;
     }
 
     @Override
     public int previousStartBoundary(@IntRange(from = 0) int offset) {
-        if (offset == 0) return DONE;
-        int boundary = mTextPaint.getTextRunCursor(
-                mText, 0, mText.length(), false, offset, Paint.CURSOR_BEFORE);
-        return boundary == -1 ? DONE : boundary;
+        return previousBoundary(offset);
     }
 
     @Override
     public int previousEndBoundary(@IntRange(from = 0) int offset) {
         if (offset == 0) return DONE;
-        int boundary = mTextPaint.getTextRunCursor(
-                mText, 0, mText.length(), false, offset, Paint.CURSOR_BEFORE);
+        int boundary = previousBoundary(offset);
         // Check that there is another cursor position before, otherwise this is not a valid
         // end boundary.
-        if (mTextPaint.getTextRunCursor(
-                mText, 0, mText.length(), false, boundary, Paint.CURSOR_BEFORE) == -1) {
+        if (boundary == DONE || previousBoundary(boundary) == DONE) {
             return DONE;
         }
-        return boundary == -1 ? DONE : boundary;
+        return boundary;
     }
 
     @Override
     public int nextStartBoundary(@IntRange(from = 0) int offset) {
-        if (offset == mText.length()) return DONE;
-        int boundary = mTextPaint.getTextRunCursor(
-                mText, 0, mText.length(), false, offset, Paint.CURSOR_AFTER);
+        if (offset == mIsGraphemeBreak.length) return DONE;
+        int boundary = nextBoundary(offset);
         // Check that there is another cursor position after, otherwise this is not a valid
         // start boundary.
-        if (mTextPaint.getTextRunCursor(
-                mText, 0, mText.length(), false, boundary, Paint.CURSOR_AFTER) == -1) {
+        if (boundary == DONE || nextBoundary(boundary) == DONE) {
             return DONE;
         }
-        return boundary == -1 ? DONE : boundary;
+        return boundary;
     }
 
     @Override
     public int nextEndBoundary(@IntRange(from = 0) int offset) {
-        if (offset == mText.length()) return DONE;
-        int boundary = mTextPaint.getTextRunCursor(
-                mText, 0, mText.length(), false, offset, Paint.CURSOR_AFTER);
-        return boundary == -1 ? DONE : boundary;
+        return nextBoundary(offset);
     }
 }
diff --git a/graphics/java/android/graphics/text/GraphemeBreak.java b/graphics/java/android/graphics/text/GraphemeBreak.java
new file mode 100644
index 000000000000..f82b2fd659cc
--- /dev/null
+++ b/graphics/java/android/graphics/text/GraphemeBreak.java
@@ -0,0 +1,59 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package android.graphics.text;
+
+/** @hide */
+public class GraphemeBreak {
+    private GraphemeBreak() { }
+
+    /**
+     * Util method that checks if the offsets in given range are grapheme break.
+     *
+     * @param advances the advances of characters in the given text. It contains the font
+     *                information used by the algorithm to determine the grapheme break. It's useful
+     *                 when some character is missing in the font. For example, if the smile emoji
+     *                 "0xD83D 0xDE0A" is not found in the font and is displayed as 2 characters.
+     *                 We can't treat it as a single grapheme cluster.
+     * @param text the text to be processed.
+     * @param start the start offset of the queried range, inclusive.
+     * @param end the end offset of the queried range, exclusive.
+     * @param isGraphemeBreak the array to receive the result. The i-th element of the
+     *                       array will be set to true if the offset (start + i) is a grapheme
+     *                       break; otherwise, it will be set to false.
+     */
+    public static void isGraphemeBreak(float[] advances, char[] text, int start, int end,
+            boolean[] isGraphemeBreak) {
+        if (start > end) {
+            throw new IllegalArgumentException("start is greater than end: start = " + start
+                    + " end = " + end);
+        }
+        if (advances.length < end) {
+            throw new IllegalArgumentException("the length of advances is less than end"
+                    + "advances.length = " + advances.length
+                    + " end = " + end);
+        }
+        if (isGraphemeBreak.length < end - start) {
+            throw new IndexOutOfBoundsException("isGraphemeBreak doesn't have enough space to "
+                    + "receive the result, isGraphemeBreak.length: " + isGraphemeBreak.length
+                    + " needed space: " + (end - start));
+        }
+        nIsGraphemeBreak(advances, text, start, end, isGraphemeBreak);
+    }
+
+    private static native void nIsGraphemeBreak(float[] advances, char[] text, int start, int end,
+            boolean[] isGraphemeBreak);
+}
diff --git a/libs/hwui/Android.bp b/libs/hwui/Android.bp
index bcbe706d71a3..baf2d8d0f9cc 100644
--- a/libs/hwui/Android.bp
+++ b/libs/hwui/Android.bp
@@ -374,6 +374,7 @@ cc_defaults {
         "jni/text/LineBreaker.cpp",
         "jni/text/MeasuredText.cpp",
         "jni/text/TextShaper.cpp",
+        "jni/text/GraphemeBreak.cpp",
     ],
 
     header_libs: [
diff --git a/libs/hwui/apex/LayoutlibLoader.cpp b/libs/hwui/apex/LayoutlibLoader.cpp
index b7a15633ff6d..770822a049b7 100644
--- a/libs/hwui/apex/LayoutlibLoader.cpp
+++ b/libs/hwui/apex/LayoutlibLoader.cpp
@@ -66,6 +66,7 @@ extern int register_android_graphics_fonts_FontFamily(JNIEnv* env);
 extern int register_android_graphics_text_LineBreaker(JNIEnv* env);
 extern int register_android_graphics_text_MeasuredText(JNIEnv* env);
 extern int register_android_graphics_text_TextShaper(JNIEnv* env);
+extern int register_android_graphics_text_GraphemeBreak(JNIEnv* env);
 
 extern int register_android_util_PathParser(JNIEnv* env);
 extern int register_android_view_DisplayListCanvas(JNIEnv* env);
@@ -125,6 +126,8 @@ static const std::unordered_map<std::string, RegJNIRec> gRegJNIMap = {
         {"android.graphics.text.MeasuredText",
          REG_JNI(register_android_graphics_text_MeasuredText)},
         {"android.graphics.text.TextRunShaper", REG_JNI(register_android_graphics_text_TextShaper)},
+        {"android.graphics.text.GraphemeBreak",
+         REG_JNI(register_android_graphics_text_GraphemeBreak)},
         {"android.util.PathParser", REG_JNI(register_android_util_PathParser)},
 };
 
diff --git a/libs/hwui/apex/jni_runtime.cpp b/libs/hwui/apex/jni_runtime.cpp
index c509ed4dfd21..09ae7e78fe23 100644
--- a/libs/hwui/apex/jni_runtime.cpp
+++ b/libs/hwui/apex/jni_runtime.cpp
@@ -77,6 +77,7 @@ extern int register_android_graphics_pdf_PdfRenderer(JNIEnv* env);
 extern int register_android_graphics_text_MeasuredText(JNIEnv* env);
 extern int register_android_graphics_text_LineBreaker(JNIEnv *env);
 extern int register_android_graphics_text_TextShaper(JNIEnv *env);
+extern int register_android_graphics_text_GraphemeBreak(JNIEnv* env);
 extern int register_android_graphics_MeshSpecification(JNIEnv* env);
 extern int register_android_graphics_Mesh(JNIEnv* env);
 
@@ -148,6 +149,7 @@ extern int register_android_graphics_HardwareBufferRenderer(JNIEnv* env);
             REG_JNI(register_android_graphics_text_MeasuredText),
             REG_JNI(register_android_graphics_text_LineBreaker),
             REG_JNI(register_android_graphics_text_TextShaper),
+            REG_JNI(register_android_graphics_text_GraphemeBreak),
             REG_JNI(register_android_graphics_MeshSpecification),
             REG_JNI(register_android_graphics_Mesh),
 
diff --git a/libs/hwui/jni/text/GraphemeBreak.cpp b/libs/hwui/jni/text/GraphemeBreak.cpp
new file mode 100644
index 000000000000..55f03bd9f7b1
--- /dev/null
+++ b/libs/hwui/jni/text/GraphemeBreak.cpp
@@ -0,0 +1,67 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#undef LOG_TAG
+#define LOG_TAG "GraphemeBreaker"
+
+#include <minikin/GraphemeBreak.h>
+#include <nativehelper/ScopedPrimitiveArray.h>
+
+#include "GraphicsJNI.h"
+
+namespace android {
+
+static void nIsGraphemeBreak(JNIEnv* env, jclass, jfloatArray advances, jcharArray text, jint start,
+                             jint end, jbooleanArray isGraphemeBreak) {
+    if (start > end || env->GetArrayLength(advances) < end ||
+        env->GetArrayLength(isGraphemeBreak) < end - start) {
+        doThrowAIOOBE(env);
+    }
+
+    if (start == end) {
+        return;
+    }
+
+    ScopedFloatArrayRO advancesArray(env, advances);
+    ScopedCharArrayRO textArray(env, text);
+    ScopedBooleanArrayRW isGraphemeBreakArray(env, isGraphemeBreak);
+
+    size_t count = end - start;
+    for (size_t offset = 0; offset < count; ++offset) {
+        bool isBreak = minikin::GraphemeBreak::isGraphemeBreak(advancesArray.get(), textArray.get(),
+                                                               start, end, start + offset);
+        isGraphemeBreakArray[offset] = isBreak ? JNI_TRUE : JNI_FALSE;
+    }
+}
+
+static const JNINativeMethod gMethods[] = {
+        {"nIsGraphemeBreak",
+         "("
+         "[F"  // advances
+         "[C"  // text
+         "I"   // start
+         "I"   // end
+         "[Z"  // isGraphemeBreak
+         ")V",
+         (void*)nIsGraphemeBreak},
+};
+
+int register_android_graphics_text_GraphemeBreak(JNIEnv* env) {
+    return RegisterMethodsOrDie(env, "android/graphics/text/GraphemeBreak", gMethods,
+                                NELEM(gMethods));
+}
+
+}  // namespace android