content: /*
   * Copyright (C) 2010 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.text;
  
  import android.annotation.FloatRange;
  import android.annotation.IntRange;
  import android.annotation.NonNull;
  import android.annotation.Nullable;
  import android.graphics.Paint;
  import android.graphics.Rect;
  import android.graphics.text.MeasuredText;
  import android.text.AutoGrowArray.ByteArray;
  import android.text.AutoGrowArray.FloatArray;
  import android.text.AutoGrowArray.IntArray;
  import android.text.Layout.Directions;
  import android.text.style.MetricAffectingSpan;
  import android.text.style.ReplacementSpan;
  import android.util.Pools.SynchronizedPool;
  
  import java.util.Arrays;
  
  /**
   * MeasuredParagraph provides text information for rendering purpose.
   *
   * The first motivation of this class is identify the text directions and retrieving individual
   * character widths. However retrieving character widths is slower than identifying text directions.
   * Thus, this class provides several builder methods for specific purposes.
   *
   * - buildForBidi:
   *   Compute only text directions.
   * - buildForMeasurement:
   *   Compute text direction and all character widths.
   * - buildForStaticLayout:
   *   This is bit special. StaticLayout also needs to know text direction and character widths for
   *   line breaking, but all things are done in native code. Similarly, text measurement is done
   *   in native code. So instead of storing result to Java array, this keeps the result in native
   *   code since there is no good reason to move the results to Java layer.
   *
   * In addition to the character widths, some additional information is computed for each purposes,
   * e.g. whole text length for measurement or font metrics for static layout.
   *
   * MeasuredParagraph is NOT a thread safe object.
   * @hide
   */
  public class MeasuredParagraph {
      private static final char OBJECT_REPLACEMENT_CHARACTER = '\uFFFC';
  
      private MeasuredParagraph() {}  // Use build static functions instead.
  
      private static final SynchronizedPool<MeasuredParagraph> sPool = new SynchronizedPool<>(1);
  
      private static @NonNull MeasuredParagraph obtain() { // Use build static functions instead.
          final MeasuredParagraph mt = sPool.acquire();
          return mt != null ? mt : new MeasuredParagraph();
      }
  
      /**
       * Recycle the MeasuredParagraph.
       *
       * Do not call any methods after you call this method.
       */
      public void recycle() {
          release();
          sPool.release(this);
      }
  
      // The casted original text.
      //
      // This may be null if the passed text is not a Spanned.
      private @Nullable Spanned mSpanned;
  
      // The start offset of the target range in the original text (mSpanned);
      private @IntRange(from = 0) int mTextStart;
  
      // The length of the target range in the original text.
      private @IntRange(from = 0) int mTextLength;
  
      // The copied character buffer for measuring text.
      //
      // The length of this array is mTextLength.
      private @Nullable char[] mCopiedBuffer;
  
      // The whole paragraph direction.
      private @Layout.Direction int mParaDir;
  
      // True if the text is LTR direction and doesn't contain any bidi characters.
      private boolean mLtrWithoutBidi;
  
      // The bidi level for individual characters.
      //
      // This is empty if mLtrWithoutBidi is true.
      private @NonNull ByteArray mLevels = new ByteArray();
  
      // The whole width of the text.
      // See getWholeWidth comments.
      private @FloatRange(from = 0.0f) float mWholeWidth;
  
      // Individual characters' widths.
      // See getWidths comments.
      private @Nullable FloatArray mWidths = new FloatArray();
  
      // The span end positions.
      // See getSpanEndCache comments.
      private @Nullable IntArray mSpanEndCache = new IntArray(4);
  
      // The font metrics.
      // See getFontMetrics comments.
      private @Nullable IntArray mFontMetrics = new IntArray(4 * 4);
  
      // The native MeasuredParagraph.
      private @Nullable MeasuredText mMeasuredText;
  
      // Following two objects are for avoiding object allocation.
      private @NonNull TextPaint mCachedPaint = new TextPaint();
      private @Nullable Paint.FontMetricsInt mCachedFm;
  
      /**
       * Releases internal buffers.
       */
      public void release() {
          reset();
          mLevels.clearWithReleasingLargeArray();
          mWidths.clearWithReleasingLargeArray();
          mFontMetrics.clearWithReleasingLargeArray();
          mSpanEndCache.clearWithReleasingLargeArray();
      }
  
      /**
       * Resets the internal state for starting new text.
       */
      private void reset() {
          mSpanned = null;
          mCopiedBuffer = null;
          mWholeWidth = 0;
          mLevels.clear();
          mWidths.clear();
          mFontMetrics.clear();
          mSpanEndCache.clear();
          mMeasuredText = null;
      }
  
      /**
       * Returns the length of the paragraph.
       *
       * This is always available.
       */
      public int getTextLength() {
          return mTextLength;
      }
  
      /**
       * Returns the characters to be measured.
       *
       * This is always available.
       */
      public @NonNull char[] getChars() {
          return mCopiedBuffer;
      }
  
      /**
       * Returns the paragraph direction.
       *
       * This is always available.
       */
      public @Layout.Direction int getParagraphDir() {
          return mParaDir;
      }
  
      /**
       * Returns the directions.
       *
       * This is always available.
       */
      public Directions getDirections(@IntRange(from = 0) int start,  // inclusive
                                      @IntRange(from = 0) int end) {  // exclusive
          if (mLtrWithoutBidi) {
              return Layout.DIRS_ALL_LEFT_TO_RIGHT;
          }
  
          final int length = end - start;
          return AndroidBidi.directions(mParaDir, mLevels.getRawArray(), start, mCopiedBuffer, start,
                  length);
      }
  
      /**
       * Returns the whole text width.
       *
       * This is available only if the MeasuredParagraph is computed with buildForMeasurement.
       * Returns 0 in other cases.
       */
      public @FloatRange(from = 0.0f) float getWholeWidth() {
          return mWholeWidth;
      }
  
      /**
       * Returns the individual character's width.
       *
       * This is available only if the MeasuredParagraph is computed with buildForMeasurement.
       * Returns empty array in other cases.
       */
      public @NonNull FloatArray getWidths() {
          return mWidths;
      }
  
      /**
       * Returns the MetricsAffectingSpan end indices.
       *
       * If the input text is not a spanned string, this has one value that is the length of the text.
       *
       * This is available only if the MeasuredParagraph is computed with buildForStaticLayout.
       * Returns empty array in other cases.
       */
      public @NonNull IntArray getSpanEndCache() {
          return mSpanEndCache;
      }
  
      /**
       * Returns the int array which holds FontMetrics.
       *
       * This array holds the repeat of top, bottom, ascent, descent of font metrics value.
       *
       * This is available only if the MeasuredParagraph is computed with buildForStaticLayout.
       * Returns empty array in other cases.
       */
      public @NonNull IntArray getFontMetrics() {
          return mFontMetrics;
      }
  
      /**
       * Returns the native ptr of the MeasuredParagraph.
       *
       * This is available only if the MeasuredParagraph is computed with buildForStaticLayout.
       * Returns null in other cases.
       */
      public MeasuredText getMeasuredText() {
          return mMeasuredText;
      }
  
      /**
       * Returns the width of the given range.
       *
       * This is not available if the MeasuredParagraph is computed with buildForBidi.
       * Returns 0 if the MeasuredParagraph is computed with buildForBidi.
       *
       * @param start the inclusive start offset of the target region in the text
       * @param end the exclusive end offset of the target region in the text
       */
      public float getWidth(int start, int end) {
          if (mMeasuredText == null) {
              // We have result in Java.
              final float[] widths = mWidths.getRawArray();
              float r = 0.0f;
              for (int i = start; i < end; ++i) {
                  r += widths[i];
              }
              return r;
          } else {
              // We have result in native.
              return mMeasuredText.getWidth(start, end);
          }
      }
  
      /**
       * Retrieves the bounding rectangle that encloses all of the characters, with an implied origin
       * at (0, 0).
       *
       * This is available only if the MeasuredParagraph is computed with buildForStaticLayout.
       */
      public void getBounds(@IntRange(from = 0) int start, @IntRange(from = 0) int end,
              @NonNull Rect bounds) {
          mMeasuredText.getBounds(start, end, bounds);
      }
  
      /**
       * Returns a width of the character at the offset.
       *
       * This is available only if the MeasuredParagraph is computed with buildForStaticLayout.
       */
      public float getCharWidthAt(@IntRange(from = 0) int offset) {
          return mMeasuredText.getCharWidthAt(offset);
      }
  
      /**
       * Generates new MeasuredParagraph for Bidi computation.
       *
       * If recycle is null, this returns new instance. If recycle is not null, this fills computed
       * result to recycle and returns recycle.
       *
       * @param text the character sequence to be measured
       * @param start the inclusive start offset of the target region in the text
       * @param end the exclusive end offset of the target region in the text
       * @param textDir the text direction
       * @param recycle pass existing MeasuredParagraph if you want to recycle it.
       *
       * @return measured text
       */
      public static @NonNull MeasuredParagraph buildForBidi(@NonNull CharSequence text,
                                                       @IntRange(from = 0) int start,
                                                       @IntRange(from = 0) int end,
                                                       @NonNull TextDirectionHeuristic textDir,
                                                       @Nullable MeasuredParagraph recycle) {
          final MeasuredParagraph mt = recycle == null ? obtain() : recycle;
          mt.resetAndAnalyzeBidi(text, start, end, textDir);
          return mt;
      }
  
      /**
       * Generates new MeasuredParagraph for measuring texts.
       *
       * If recycle is null, this returns new instance. If recycle is not null, this fills computed
       * result to recycle and returns recycle.
       *
       * @param paint the paint to be used for rendering the text.
       * @param text the character sequence to be measured
       * @param start the inclusive start offset of the target region in the text
       * @param end the exclusive end offset of the target region in the text
       * @param textDir the text direction
       * @param recycle pass existing MeasuredParagraph if you want to recycle it.
       *
       * @return measured text
       */
      public static @NonNull MeasuredParagraph buildForMeasurement(@NonNull TextPaint paint,
                                                              @NonNull CharSequence text,
                                                              @IntRange(from = 0) int start,
                                                              @IntRange(from = 0) int end,
                                                              @NonNull TextDirectionHeuristic textDir,
                                                              @Nullable MeasuredParagraph recycle) {
          final MeasuredParagraph mt = recycle == null ? obtain() : recycle;
          mt.resetAndAnalyzeBidi(text, start, end, textDir);
  
          mt.mWidths.resize(mt.mTextLength);
          if (mt.mTextLength == 0) {
              return mt;
          }
  
          if (mt.mSpanned == null) {
              // No style change by MetricsAffectingSpan. Just measure all text.
              mt.applyMetricsAffectingSpan(
                      paint, null /* spans */, start, end, null /* native builder ptr */);
          } else {
              // There may be a MetricsAffectingSpan. Split into span transitions and apply styles.
              int spanEnd;
              for (int spanStart = start; spanStart < end; spanStart = spanEnd) {
                  spanEnd = mt.mSpanned.nextSpanTransition(spanStart, end, MetricAffectingSpan.class);
                  MetricAffectingSpan[] spans = mt.mSpanned.getSpans(spanStart, spanEnd,
                          MetricAffectingSpan.class);
                  spans = TextUtils.removeEmptySpans(spans, mt.mSpanned, MetricAffectingSpan.class);
                  mt.applyMetricsAffectingSpan(
                          paint, spans, spanStart, spanEnd, null /* native builder ptr */);
              }
          }
          return mt;
      }
  
      /**
       * Generates new MeasuredParagraph for StaticLayout.
       *
       * If recycle is null, this returns new instance. If recycle is not null, this fills computed
       * result to recycle and returns recycle.
       *
       * @param paint the paint to be used for rendering the text.
       * @param text the character sequence to be measured
       * @param start the inclusive start offset of the target region in the text
       * @param end the exclusive end offset of the target region in the text
       * @param textDir the text direction
       * @param computeHyphenation true if need to compute hyphenation, otherwise false
       * @param computeLayout true if need to compute full layout, otherwise false.
       * @param hint pass if you already have measured paragraph.
       * @param recycle pass existing MeasuredParagraph if you want to recycle it.
       *
       * @return measured text
       */
      public static @NonNull MeasuredParagraph buildForStaticLayout(
              @NonNull TextPaint paint,
              @NonNull CharSequence text,
              @IntRange(from = 0) int start,
              @IntRange(from = 0) int end,
              @NonNull TextDirectionHeuristic textDir,
              boolean computeHyphenation,
              boolean computeLayout,
              @Nullable MeasuredParagraph hint,
              @Nullable MeasuredParagraph recycle) {
          final MeasuredParagraph mt = recycle == null ? obtain() : recycle;
          mt.resetAndAnalyzeBidi(text, start, end, textDir);
          final MeasuredText.Builder builder;
          if (hint == null) {
              builder = new MeasuredText.Builder(mt.mCopiedBuffer)
                      .setComputeHyphenation(computeHyphenation)
                      .setComputeLayout(computeLayout);
          } else {
              builder = new MeasuredText.Builder(hint.mMeasuredText);
          }
          if (mt.mTextLength == 0) {
              // Need to build empty native measured text for StaticLayout.
              // TODO: Stop creating empty measured text for empty lines.
              mt.mMeasuredText = builder.build();
          } else {
              if (mt.mSpanned == null) {
                  // No style change by MetricsAffectingSpan. Just measure all text.
                  mt.applyMetricsAffectingSpan(paint, null /* spans */, start, end, builder);
                  mt.mSpanEndCache.append(end);
              } else {
                  // There may be a MetricsAffectingSpan. Split into span transitions and apply
                  // styles.
                  int spanEnd;
                  for (int spanStart = start; spanStart < end; spanStart = spanEnd) {
                      spanEnd = mt.mSpanned.nextSpanTransition(spanStart, end,
                                                               MetricAffectingSpan.class);
                      MetricAffectingSpan[] spans = mt.mSpanned.getSpans(spanStart, spanEnd,
                              MetricAffectingSpan.class);
                      spans = TextUtils.removeEmptySpans(spans, mt.mSpanned,
                                                         MetricAffectingSpan.class);
                      mt.applyMetricsAffectingSpan(paint, spans, spanStart, spanEnd, builder);
                      mt.mSpanEndCache.append(spanEnd);
                  }
              }
              mt.mMeasuredText = builder.build();
          }
  
          return mt;
      }
  
      /**
       * Reset internal state and analyzes text for bidirectional runs.
       *
       * @param text the character sequence to be measured
       * @param start the inclusive start offset of the target region in the text
       * @param end the exclusive end offset of the target region in the text
       * @param textDir the text direction
       */
      private void resetAndAnalyzeBidi(@NonNull CharSequence text,
                                       @IntRange(from = 0) int start,  // inclusive
                                       @IntRange(from = 0) int end,  // exclusive
                                       @NonNull TextDirectionHeuristic textDir) {
          reset();
          mSpanned = text instanceof Spanned ? (Spanned) text : null;
          mTextStart = start;
          mTextLength = end - start;
  
          if (mCopiedBuffer == null || mCopiedBuffer.length != mTextLength) {
              mCopiedBuffer = new char[mTextLength];
          }
          TextUtils.getChars(text, start, end, mCopiedBuffer, 0);
  
          // Replace characters associated with ReplacementSpan to U+FFFC.
          if (mSpanned != null) {
              ReplacementSpan[] spans = mSpanned.getSpans(start, end, ReplacementSpan.class);
  
              for (int i = 0; i < spans.length; i++) {
                  int startInPara = mSpanned.getSpanStart(spans[i]) - start;
                  int endInPara = mSpanned.getSpanEnd(spans[i]) - start;
                  // The span interval may be larger and must be restricted to [start, end)
                  if (startInPara < 0) startInPara = 0;
                  if (endInPara > mTextLength) endInPara = mTextLength;
                  Arrays.fill(mCopiedBuffer, startInPara, endInPara, OBJECT_REPLACEMENT_CHARACTER);
              }
          }
  
          if ((textDir == TextDirectionHeuristics.LTR
                  || textDir == TextDirectionHeuristics.FIRSTSTRONG_LTR
                  || textDir == TextDirectionHeuristics.ANYRTL_LTR)
                  && TextUtils.doesNotNeedBidi(mCopiedBuffer, 0, mTextLength)) {
              mLevels.clear();
              mParaDir = Layout.DIR_LEFT_TO_RIGHT;
              mLtrWithoutBidi = true;
          } else {
              final int bidiRequest;
              if (textDir == TextDirectionHeuristics.LTR) {
                  bidiRequest = Layout.DIR_REQUEST_LTR;
              } else if (textDir == TextDirectionHeuristics.RTL) {
                  bidiRequest = Layout.DIR_REQUEST_RTL;
              } else if (textDir == TextDirectionHeuristics.FIRSTSTRONG_LTR) {
                  bidiRequest = Layout.DIR_REQUEST_DEFAULT_LTR;
              } else if (textDir == TextDirectionHeuristics.FIRSTSTRONG_RTL) {
                  bidiRequest = Layout.DIR_REQUEST_DEFAULT_RTL;
              } else {
                  final boolean isRtl = textDir.isRtl(mCopiedBuffer, 0, mTextLength);
                  bidiRequest = isRtl ? Layout.DIR_REQUEST_RTL : Layout.DIR_REQUEST_LTR;
              }
              mLevels.resize(mTextLength);
              mParaDir = AndroidBidi.bidi(bidiRequest, mCopiedBuffer, mLevels.getRawArray());
              mLtrWithoutBidi = false;
          }
      }
  
      private void applyReplacementRun(@NonNull ReplacementSpan replacement,
                                       @IntRange(from = 0) int start,  // inclusive, in copied buffer
                                       @IntRange(from = 0) int end,  // exclusive, in copied buffer
                                       @Nullable MeasuredText.Builder builder) {
          // Use original text. Shouldn't matter.
          // TODO: passing uninitizlied FontMetrics to developers. Do we need to keep this for
          //       backward compatibility? or Should we initialize them for getFontMetricsInt?
          final float width = replacement.getSize(
                  mCachedPaint, mSpanned, start + mTextStart, end + mTextStart, mCachedFm);
          if (builder == null) {
              // Assigns all width to the first character. This is the same behavior as minikin.
              mWidths.set(start, width);
              if (end > start + 1) {
                  Arrays.fill(mWidths.getRawArray(), start + 1, end, 0.0f);
              }
              mWholeWidth += width;
          } else {
              builder.appendReplacementRun(mCachedPaint, end - start, width);
          }
      }
  
      private void applyStyleRun(@IntRange(from = 0) int start,  // inclusive, in copied buffer
                                 @IntRange(from = 0) int end,  // exclusive, in copied buffer
                                 @Nullable MeasuredText.Builder builder) {
  
          if (mLtrWithoutBidi) {
              // If the whole text is LTR direction, just apply whole region.
              if (builder == null) {
                  mWholeWidth += mCachedPaint.getTextRunAdvances(
                          mCopiedBuffer, start, end - start, start, end - start, false /* isRtl */,
                          mWidths.getRawArray(), start);
              } else {
                  builder.appendStyleRun(mCachedPaint, end - start, false /* isRtl */);
              }
          } else {
              // If there is multiple bidi levels, split into individual bidi level and apply style.
              byte level = mLevels.get(start);
              // Note that the empty text or empty range won't reach this method.
              // Safe to search from start + 1.
              for (int levelStart = start, levelEnd = start + 1;; ++levelEnd) {
                  if (levelEnd == end || mLevels.get(levelEnd) != level) {  // transition point
                      final boolean isRtl = (level & 0x1) != 0;
                      if (builder == null) {
                          final int levelLength = levelEnd - levelStart;
                          mWholeWidth += mCachedPaint.getTextRunAdvances(
                                  mCopiedBuffer, levelStart, levelLength, levelStart, levelLength,
                                  isRtl, mWidths.getRawArray(), levelStart);
                      } else {
                          builder.appendStyleRun(mCachedPaint, levelEnd - levelStart, isRtl);
                      }
                      if (levelEnd == end) {
                          break;
                      }
                      levelStart = levelEnd;
                      level = mLevels.get(levelEnd);
                  }
              }
          }
      }
  
      private void applyMetricsAffectingSpan(
              @NonNull TextPaint paint,
              @Nullable MetricAffectingSpan[] spans,
              @IntRange(from = 0) int start,  // inclusive, in original text buffer
              @IntRange(from = 0) int end,  // exclusive, in original text buffer
              @Nullable MeasuredText.Builder builder) {
          mCachedPaint.set(paint);
          // XXX paint should not have a baseline shift, but...
          mCachedPaint.baselineShift = 0;
  
          final boolean needFontMetrics = builder != null;
  
          if (needFontMetrics && mCachedFm == null) {
              mCachedFm = new Paint.FontMetricsInt();
          }
  
          ReplacementSpan replacement = null;
          if (spans != null) {
              for (int i = 0; i < spans.length; i++) {
                  MetricAffectingSpan span = spans[i];
                  if (span instanceof ReplacementSpan) {
                      // The last ReplacementSpan is effective for backward compatibility reasons.
                      replacement = (ReplacementSpan) span;
                  } else {
                      // TODO: No need to call updateMeasureState for ReplacementSpan as well?
                      span.updateMeasureState(mCachedPaint);
                  }
              }
          }
  
          final int startInCopiedBuffer = start - mTextStart;
          final int endInCopiedBuffer = end - mTextStart;
  
          if (builder != null) {
              mCachedPaint.getFontMetricsInt(mCachedFm);
          }
  
          if (replacement != null) {
              applyReplacementRun(replacement, startInCopiedBuffer, endInCopiedBuffer, builder);
          } else {
              applyStyleRun(startInCopiedBuffer, endInCopiedBuffer, builder);
          }
  
          if (needFontMetrics) {
              if (mCachedPaint.baselineShift < 0) {
                  mCachedFm.ascent += mCachedPaint.baselineShift;
                  mCachedFm.top += mCachedPaint.baselineShift;
              } else {
                  mCachedFm.descent += mCachedPaint.baselineShift;
                  mCachedFm.bottom += mCachedPaint.baselineShift;
              }
  
              mFontMetrics.append(mCachedFm.top);
              mFontMetrics.append(mCachedFm.bottom);
              mFontMetrics.append(mCachedFm.ascent);
              mFontMetrics.append(mCachedFm.descent);
          }
      }
  
      /**
       * Returns the maximum index that the accumulated width not exceeds the width.
       *
       * If forward=false is passed, returns the minimum index from the end instead.
       *
       * This only works if the MeasuredParagraph is computed with buildForMeasurement.
       * Undefined behavior in other case.
       */
      @IntRange(from = 0) int breakText(int limit, boolean forwards, float width) {
          float[] w = mWidths.getRawArray();
          if (forwards) {
              int i = 0;
              while (i < limit) {
                  width -= w[i];
                  if (width < 0.0f) break;
                  i++;
              }
              while (i > 0 && mCopiedBuffer[i - 1] == ' ') i--;
              return i;
          } else {
              int i = limit - 1;
              while (i >= 0) {
                  width -= w[i];
                  if (width < 0.0f) break;
                  i--;
              }
              while (i < limit - 1 && (mCopiedBuffer[i + 1] == ' ' || w[i + 1] == 0.0f)) {
                  i++;
              }
              return limit - i - 1;
          }
      }
  
      /**
       * Returns the length of the substring.
       *
       * This only works if the MeasuredParagraph is computed with buildForMeasurement.
       * Undefined behavior in other case.
       */
      @FloatRange(from = 0.0f) float measure(int start, int limit) {
          float width = 0;
          float[] w = mWidths.getRawArray();
          for (int i = start; i < limit; ++i) {
              width += w[i];
          }
          return width;
      }
  
      /**
       * This only works if the MeasuredParagraph is computed with buildForStaticLayout.
       */
      public @IntRange(from = 0) int getMemoryUsage() {
          return mMeasuredText.getMemoryUsage();
      }
  }
  