content: /*
   * Copyright (C) 2006 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.annotation.UnsupportedAppUsage;
  import android.graphics.Paint;
  import android.graphics.Rect;
  import android.os.Build;
  import android.text.style.ReplacementSpan;
  import android.text.style.UpdateLayout;
  import android.text.style.WrapTogetherSpan;
  import android.util.ArraySet;
  import android.util.Pools.SynchronizedPool;
  
  import com.android.internal.annotations.VisibleForTesting;
  import com.android.internal.util.ArrayUtils;
  import com.android.internal.util.GrowingArrayUtils;
  
  import java.lang.ref.WeakReference;
  
  /**
   * DynamicLayout is a text layout that updates itself as the text is edited.
   * <p>This is used by widgets to control text layout. You should not need
   * to use this class directly unless you are implementing your own widget
   * or custom display object, or need to call
   * {@link android.graphics.Canvas#drawText(java.lang.CharSequence, int, int, float, float, android.graphics.Paint)
   *  Canvas.drawText()} directly.</p>
   */
  public class DynamicLayout extends Layout {
      private static final int PRIORITY = 128;
      private static final int BLOCK_MINIMUM_CHARACTER_LENGTH = 400;
  
      /**
       * Builder for dynamic layouts. The builder is the preferred pattern for constructing
       * DynamicLayout objects and should be preferred over the constructors, particularly to access
       * newer features. To build a dynamic layout, first call {@link #obtain} with the required
       * arguments (base, paint, and width), then call setters for optional parameters, and finally
       * {@link #build} to build the DynamicLayout object. Parameters not explicitly set will get
       * default values.
       */
      public static final class Builder {
          private Builder() {
          }
  
          /**
           * Obtain a builder for constructing DynamicLayout objects.
           */
          @NonNull
          public static Builder obtain(@NonNull CharSequence base, @NonNull TextPaint paint,
                  @IntRange(from = 0) int width) {
              Builder b = sPool.acquire();
              if (b == null) {
                  b = new Builder();
              }
  
              // set default initial values
              b.mBase = base;
              b.mDisplay = base;
              b.mPaint = paint;
              b.mWidth = width;
              b.mAlignment = Alignment.ALIGN_NORMAL;
              b.mTextDir = TextDirectionHeuristics.FIRSTSTRONG_LTR;
              b.mSpacingMult = DEFAULT_LINESPACING_MULTIPLIER;
              b.mSpacingAdd = DEFAULT_LINESPACING_ADDITION;
              b.mIncludePad = true;
              b.mFallbackLineSpacing = false;
              b.mEllipsizedWidth = width;
              b.mEllipsize = null;
              b.mBreakStrategy = Layout.BREAK_STRATEGY_SIMPLE;
              b.mHyphenationFrequency = Layout.HYPHENATION_FREQUENCY_NONE;
              b.mJustificationMode = Layout.JUSTIFICATION_MODE_NONE;
              return b;
          }
  
          /**
           * This method should be called after the layout is finished getting constructed and the
           * builder needs to be cleaned up and returned to the pool.
           */
          private static void recycle(@NonNull Builder b) {
              b.mBase = null;
              b.mDisplay = null;
              b.mPaint = null;
              sPool.release(b);
          }
  
          /**
           * Set the transformed text (password transformation being the primary example of a
           * transformation) that will be updated as the base text is changed. The default is the
           * 'base' text passed to the builder's constructor.
           *
           * @param display the transformed text
           * @return this builder, useful for chaining
           */
          @NonNull
          public Builder setDisplayText(@NonNull CharSequence display) {
              mDisplay = display;
              return this;
          }
  
          /**
           * Set the alignment. The default is {@link Layout.Alignment#ALIGN_NORMAL}.
           *
           * @param alignment Alignment for the resulting {@link DynamicLayout}
           * @return this builder, useful for chaining
           */
          @NonNull
          public Builder setAlignment(@NonNull Alignment alignment) {
              mAlignment = alignment;
              return this;
          }
  
          /**
           * Set the text direction heuristic. The text direction heuristic is used to resolve text
           * direction per-paragraph based on the input text. The default is
           * {@link TextDirectionHeuristics#FIRSTSTRONG_LTR}.
           *
           * @param textDir text direction heuristic for resolving bidi behavior.
           * @return this builder, useful for chaining
           */
          @NonNull
          public Builder setTextDirection(@NonNull TextDirectionHeuristic textDir) {
              mTextDir = textDir;
              return this;
          }
  
          /**
           * Set line spacing parameters. Each line will have its line spacing multiplied by
           * {@code spacingMult} and then increased by {@code spacingAdd}. The default is 0.0 for
           * {@code spacingAdd} and 1.0 for {@code spacingMult}.
           *
           * @param spacingAdd the amount of line spacing addition
           * @param spacingMult the line spacing multiplier
           * @return this builder, useful for chaining
           * @see android.widget.TextView#setLineSpacing
           */
          @NonNull
          public Builder setLineSpacing(float spacingAdd, @FloatRange(from = 0.0) float spacingMult) {
              mSpacingAdd = spacingAdd;
              mSpacingMult = spacingMult;
              return this;
          }
  
          /**
           * Set whether to include extra space beyond font ascent and descent (which is needed to
           * avoid clipping in some languages, such as Arabic and Kannada). The default is
           * {@code true}.
           *
           * @param includePad whether to include padding
           * @return this builder, useful for chaining
           * @see android.widget.TextView#setIncludeFontPadding
           */
          @NonNull
          public Builder setIncludePad(boolean includePad) {
              mIncludePad = includePad;
              return this;
          }
  
          /**
           * Set whether to respect the ascent and descent of the fallback fonts that are used in
           * displaying the text (which is needed to avoid text from consecutive lines running into
           * each other). If set, fallback fonts that end up getting used can increase the ascent
           * and descent of the lines that they are used on.
           *
           * <p>For backward compatibility reasons, the default is {@code false}, but setting this to
           * true is strongly recommended. It is required to be true if text could be in languages
           * like Burmese or Tibetan where text is typically much taller or deeper than Latin text.
           *
           * @param useLineSpacingFromFallbacks whether to expand linespacing based on fallback fonts
           * @return this builder, useful for chaining
           */
          @NonNull
          public Builder setUseLineSpacingFromFallbacks(boolean useLineSpacingFromFallbacks) {
              mFallbackLineSpacing = useLineSpacingFromFallbacks;
              return this;
          }
  
          /**
           * Set the width as used for ellipsizing purposes, if it differs from the normal layout
           * width. The default is the {@code width} passed to {@link #obtain}.
           *
           * @param ellipsizedWidth width used for ellipsizing, in pixels
           * @return this builder, useful for chaining
           * @see android.widget.TextView#setEllipsize
           */
          @NonNull
          public Builder setEllipsizedWidth(@IntRange(from = 0) int ellipsizedWidth) {
              mEllipsizedWidth = ellipsizedWidth;
              return this;
          }
  
          /**
           * Set ellipsizing on the layout. Causes words that are longer than the view is wide, or
           * exceeding the number of lines (see #setMaxLines) in the case of
           * {@link android.text.TextUtils.TruncateAt#END} or
           * {@link android.text.TextUtils.TruncateAt#MARQUEE}, to be ellipsized instead of broken.
           * The default is {@code null}, indicating no ellipsis is to be applied.
           *
           * @param ellipsize type of ellipsis behavior
           * @return this builder, useful for chaining
           * @see android.widget.TextView#setEllipsize
           */
          public Builder setEllipsize(@Nullable TextUtils.TruncateAt ellipsize) {
              mEllipsize = ellipsize;
              return this;
          }
  
          /**
           * Set break strategy, useful for selecting high quality or balanced paragraph layout
           * options. The default is {@link Layout#BREAK_STRATEGY_SIMPLE}.
           *
           * @param breakStrategy break strategy for paragraph layout
           * @return this builder, useful for chaining
           * @see android.widget.TextView#setBreakStrategy
           */
          @NonNull
          public Builder setBreakStrategy(@BreakStrategy int breakStrategy) {
              mBreakStrategy = breakStrategy;
              return this;
          }
  
          /**
           * Set hyphenation frequency, to control the amount of automatic hyphenation used. The
           * possible values are defined in {@link Layout}, by constants named with the pattern
           * {@code HYPHENATION_FREQUENCY_*}. The default is
           * {@link Layout#HYPHENATION_FREQUENCY_NONE}.
           *
           * @param hyphenationFrequency hyphenation frequency for the paragraph
           * @return this builder, useful for chaining
           * @see android.widget.TextView#setHyphenationFrequency
           */
          @NonNull
          public Builder setHyphenationFrequency(@HyphenationFrequency int hyphenationFrequency) {
              mHyphenationFrequency = hyphenationFrequency;
              return this;
          }
  
          /**
           * Set paragraph justification mode. The default value is
           * {@link Layout#JUSTIFICATION_MODE_NONE}. If the last line is too short for justification,
           * the last line will be displayed with the alignment set by {@link #setAlignment}.
           *
           * @param justificationMode justification mode for the paragraph.
           * @return this builder, useful for chaining.
           */
          @NonNull
          public Builder setJustificationMode(@JustificationMode int justificationMode) {
              mJustificationMode = justificationMode;
              return this;
          }
  
          /**
           * Build the {@link DynamicLayout} after options have been set.
           *
           * <p>Note: the builder object must not be reused in any way after calling this method.
           * Setting parameters after calling this method, or calling it a second time on the same
           * builder object, will likely lead to unexpected results.
           *
           * @return the newly constructed {@link DynamicLayout} object
           */
          @NonNull
          public DynamicLayout build() {
              final DynamicLayout result = new DynamicLayout(this);
              Builder.recycle(this);
              return result;
          }
  
          private CharSequence mBase;
          private CharSequence mDisplay;
          private TextPaint mPaint;
          private int mWidth;
          private Alignment mAlignment;
          private TextDirectionHeuristic mTextDir;
          private float mSpacingMult;
          private float mSpacingAdd;
          private boolean mIncludePad;
          private boolean mFallbackLineSpacing;
          private int mBreakStrategy;
          private int mHyphenationFrequency;
          private int mJustificationMode;
          private TextUtils.TruncateAt mEllipsize;
          private int mEllipsizedWidth;
  
          private final Paint.FontMetricsInt mFontMetricsInt = new Paint.FontMetricsInt();
  
          private static final SynchronizedPool<Builder> sPool = new SynchronizedPool<>(3);
      }
  
      /**
       * @deprecated Use {@link Builder} instead.
       */
      @Deprecated
      public DynamicLayout(@NonNull CharSequence base,
                           @NonNull TextPaint paint,
                           @IntRange(from = 0) int width, @NonNull Alignment align,
                           @FloatRange(from = 0.0) float spacingmult, float spacingadd,
                           boolean includepad) {
          this(base, base, paint, width, align, spacingmult, spacingadd,
               includepad);
      }
  
      /**
       * @deprecated Use {@link Builder} instead.
       */
      @Deprecated
      public DynamicLayout(@NonNull CharSequence base, @NonNull CharSequence display,
                           @NonNull TextPaint paint,
                           @IntRange(from = 0) int width, @NonNull Alignment align,
                           @FloatRange(from = 0.0) float spacingmult, float spacingadd,
                           boolean includepad) {
          this(base, display, paint, width, align, spacingmult, spacingadd,
               includepad, null, 0);
      }
  
      /**
       * @deprecated Use {@link Builder} instead.
       */
      @Deprecated
      public DynamicLayout(@NonNull CharSequence base, @NonNull CharSequence display,
                           @NonNull TextPaint paint,
                           @IntRange(from = 0) int width, @NonNull Alignment align,
                           @FloatRange(from = 0.0) float spacingmult, float spacingadd,
                           boolean includepad,
                           @Nullable TextUtils.TruncateAt ellipsize,
                           @IntRange(from = 0) int ellipsizedWidth) {
          this(base, display, paint, width, align, TextDirectionHeuristics.FIRSTSTRONG_LTR,
                  spacingmult, spacingadd, includepad,
                  Layout.BREAK_STRATEGY_SIMPLE, Layout.HYPHENATION_FREQUENCY_NONE,
                  Layout.JUSTIFICATION_MODE_NONE, ellipsize, ellipsizedWidth);
      }
  
      /**
       * Make a layout for the transformed text (password transformation being the primary example of
       * a transformation) that will be updated as the base text is changed. If ellipsize is non-null,
       * the Layout will ellipsize the text down to ellipsizedWidth.
       *
       * @hide
       * @deprecated Use {@link Builder} instead.
       */
      @Deprecated
      @UnsupportedAppUsage(maxTargetSdk = Build.VERSION_CODES.P, trackingBug = 115609023)
      public DynamicLayout(@NonNull CharSequence base, @NonNull CharSequence display,
                           @NonNull TextPaint paint,
                           @IntRange(from = 0) int width,
                           @NonNull Alignment align, @NonNull TextDirectionHeuristic textDir,
                           @FloatRange(from = 0.0) float spacingmult, float spacingadd,
                           boolean includepad, @BreakStrategy int breakStrategy,
                           @HyphenationFrequency int hyphenationFrequency,
                           @JustificationMode int justificationMode,
                           @Nullable TextUtils.TruncateAt ellipsize,
                           @IntRange(from = 0) int ellipsizedWidth) {
          super(createEllipsizer(ellipsize, display),
                paint, width, align, textDir, spacingmult, spacingadd);
  
          final Builder b = Builder.obtain(base, paint, width)
                  .setAlignment(align)
                  .setTextDirection(textDir)
                  .setLineSpacing(spacingadd, spacingmult)
                  .setEllipsizedWidth(ellipsizedWidth)
                  .setEllipsize(ellipsize);
          mDisplay = display;
          mIncludePad = includepad;
          mBreakStrategy = breakStrategy;
          mJustificationMode = justificationMode;
          mHyphenationFrequency = hyphenationFrequency;
  
          generate(b);
  
          Builder.recycle(b);
      }
  
      private DynamicLayout(@NonNull Builder b) {
          super(createEllipsizer(b.mEllipsize, b.mDisplay),
                  b.mPaint, b.mWidth, b.mAlignment, b.mTextDir, b.mSpacingMult, b.mSpacingAdd);
  
          mDisplay = b.mDisplay;
          mIncludePad = b.mIncludePad;
          mBreakStrategy = b.mBreakStrategy;
          mJustificationMode = b.mJustificationMode;
          mHyphenationFrequency = b.mHyphenationFrequency;
  
          generate(b);
      }
  
      @NonNull
      private static CharSequence createEllipsizer(@Nullable TextUtils.TruncateAt ellipsize,
              @NonNull CharSequence display) {
          if (ellipsize == null) {
              return display;
          } else if (display instanceof Spanned) {
              return new SpannedEllipsizer(display);
          } else {
              return new Ellipsizer(display);
          }
      }
  
      private void generate(@NonNull Builder b) {
          mBase = b.mBase;
          mFallbackLineSpacing = b.mFallbackLineSpacing;
          if (b.mEllipsize != null) {
              mInts = new PackedIntVector(COLUMNS_ELLIPSIZE);
              mEllipsizedWidth = b.mEllipsizedWidth;
              mEllipsizeAt = b.mEllipsize;
  
              /*
               * This is annoying, but we can't refer to the layout until superclass construction is
               * finished, and the superclass constructor wants the reference to the display text.
               *
               * In other words, the two Ellipsizer classes in Layout.java need a
               * (Dynamic|Static)Layout as a parameter to do their calculations, but the Ellipsizers
               * also need to be the input to the superclass's constructor (Layout). In order to go
               * around the circular dependency, we construct the Ellipsizer with only one of the
               * parameters, the text (in createEllipsizer). And we fill in the rest of the needed
               * information (layout, width, and method) later, here.
               *
               * This will break if the superclass constructor ever actually cares about the content
               * instead of just holding the reference.
               */
              final Ellipsizer e = (Ellipsizer) getText();
              e.mLayout = this;
              e.mWidth = b.mEllipsizedWidth;
              e.mMethod = b.mEllipsize;
              mEllipsize = true;
          } else {
              mInts = new PackedIntVector(COLUMNS_NORMAL);
              mEllipsizedWidth = b.mWidth;
              mEllipsizeAt = null;
          }
  
          mObjects = new PackedObjectVector<>(1);
  
          // Initial state is a single line with 0 characters (0 to 0), with top at 0 and bottom at
          // whatever is natural, and undefined ellipsis.
  
          int[] start;
  
          if (b.mEllipsize != null) {
              start = new int[COLUMNS_ELLIPSIZE];
              start[ELLIPSIS_START] = ELLIPSIS_UNDEFINED;
          } else {
              start = new int[COLUMNS_NORMAL];
          }
  
          final Directions[] dirs = new Directions[] { DIRS_ALL_LEFT_TO_RIGHT };
  
          final Paint.FontMetricsInt fm = b.mFontMetricsInt;
          b.mPaint.getFontMetricsInt(fm);
          final int asc = fm.ascent;
          final int desc = fm.descent;
  
          start[DIR] = DIR_LEFT_TO_RIGHT << DIR_SHIFT;
          start[TOP] = 0;
          start[DESCENT] = desc;
          mInts.insertAt(0, start);
  
          start[TOP] = desc - asc;
          mInts.insertAt(1, start);
  
          mObjects.insertAt(0, dirs);
  
          final int baseLength = mBase.length();
          // Update from 0 characters to whatever the real text is
          reflow(mBase, 0, 0, baseLength);
  
          if (mBase instanceof Spannable) {
              if (mWatcher == null)
                  mWatcher = new ChangeWatcher(this);
  
              // Strip out any watchers for other DynamicLayouts.
              final Spannable sp = (Spannable) mBase;
              final ChangeWatcher[] spans = sp.getSpans(0, baseLength, ChangeWatcher.class);
              for (int i = 0; i < spans.length; i++) {
                  sp.removeSpan(spans[i]);
              }
  
              sp.setSpan(mWatcher, 0, baseLength,
                         Spannable.SPAN_INCLUSIVE_INCLUSIVE |
                         (PRIORITY << Spannable.SPAN_PRIORITY_SHIFT));
          }
      }
  
      /** @hide */
      @VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE)
      public void reflow(CharSequence s, int where, int before, int after) {
          if (s != mBase)
              return;
  
          CharSequence text = mDisplay;
          int len = text.length();
  
          // seek back to the start of the paragraph
  
          int find = TextUtils.lastIndexOf(text, '\n', where - 1);
          if (find < 0)
              find = 0;
          else
              find = find + 1;
  
          {
              int diff = where - find;
              before += diff;
              after += diff;
              where -= diff;
          }
  
          // seek forward to the end of the paragraph
  
          int look = TextUtils.indexOf(text, '\n', where + after);
          if (look < 0)
              look = len;
          else
              look++; // we want the index after the \n
  
          int change = look - (where + after);
          before += change;
          after += change;
  
          // seek further out to cover anything that is forced to wrap together
  
          if (text instanceof Spanned) {
              Spanned sp = (Spanned) text;
              boolean again;
  
              do {
                  again = false;
  
                  Object[] force = sp.getSpans(where, where + after,
                                               WrapTogetherSpan.class);
  
                  for (int i = 0; i < force.length; i++) {
                      int st = sp.getSpanStart(force[i]);
                      int en = sp.getSpanEnd(force[i]);
  
                      if (st < where) {
                          again = true;
  
                          int diff = where - st;
                          before += diff;
                          after += diff;
                          where -= diff;
                      }
  
                      if (en > where + after) {
                          again = true;
  
                          int diff = en - (where + after);
                          before += diff;
                          after += diff;
                      }
                  }
              } while (again);
          }
  
          // find affected region of old layout
  
          int startline = getLineForOffset(where);
          int startv = getLineTop(startline);
  
          int endline = getLineForOffset(where + before);
          if (where + after == len)
              endline = getLineCount();
          int endv = getLineTop(endline);
          boolean islast = (endline == getLineCount());
  
          // generate new layout for affected text
  
          StaticLayout reflowed;
          StaticLayout.Builder b;
  
          synchronized (sLock) {
              reflowed = sStaticLayout;
              b = sBuilder;
              sStaticLayout = null;
              sBuilder = null;
          }
  
          if (reflowed == null) {
              reflowed = new StaticLayout(null);
              b = StaticLayout.Builder.obtain(text, where, where + after, getPaint(), getWidth());
          }
  
          b.setText(text, where, where + after)
                  .setPaint(getPaint())
                  .setWidth(getWidth())
                  .setTextDirection(getTextDirectionHeuristic())
                  .setLineSpacing(getSpacingAdd(), getSpacingMultiplier())
                  .setUseLineSpacingFromFallbacks(mFallbackLineSpacing)
                  .setEllipsizedWidth(mEllipsizedWidth)
                  .setEllipsize(mEllipsizeAt)
                  .setBreakStrategy(mBreakStrategy)
                  .setHyphenationFrequency(mHyphenationFrequency)
                  .setJustificationMode(mJustificationMode)
                  .setAddLastLineLineSpacing(!islast);
  
          reflowed.generate(b, false /*includepad*/, true /*trackpad*/);
          int n = reflowed.getLineCount();
          // If the new layout has a blank line at the end, but it is not
          // the very end of the buffer, then we already have a line that
          // starts there, so disregard the blank line.
  
          if (where + after != len && reflowed.getLineStart(n - 1) == where + after)
              n--;
  
          // remove affected lines from old layout
          mInts.deleteAt(startline, endline - startline);
          mObjects.deleteAt(startline, endline - startline);
  
          // adjust offsets in layout for new height and offsets
  
          int ht = reflowed.getLineTop(n);
          int toppad = 0, botpad = 0;
  
          if (mIncludePad && startline == 0) {
              toppad = reflowed.getTopPadding();
              mTopPadding = toppad;
              ht -= toppad;
          }
          if (mIncludePad && islast) {
              botpad = reflowed.getBottomPadding();
              mBottomPadding = botpad;
              ht += botpad;
          }
  
          mInts.adjustValuesBelow(startline, START, after - before);
          mInts.adjustValuesBelow(startline, TOP, startv - endv + ht);
  
          // insert new layout
  
          int[] ints;
  
          if (mEllipsize) {
              ints = new int[COLUMNS_ELLIPSIZE];
              ints[ELLIPSIS_START] = ELLIPSIS_UNDEFINED;
          } else {
              ints = new int[COLUMNS_NORMAL];
          }
  
          Directions[] objects = new Directions[1];
  
          for (int i = 0; i < n; i++) {
              final int start = reflowed.getLineStart(i);
              ints[START] = start;
              ints[DIR] |= reflowed.getParagraphDirection(i) << DIR_SHIFT;
              ints[TAB] |= reflowed.getLineContainsTab(i) ? TAB_MASK : 0;
  
              int top = reflowed.getLineTop(i) + startv;
              if (i > 0)
                  top -= toppad;
              ints[TOP] = top;
  
              int desc = reflowed.getLineDescent(i);
              if (i == n - 1)
                  desc += botpad;
  
              ints[DESCENT] = desc;
              ints[EXTRA] = reflowed.getLineExtra(i);
              objects[0] = reflowed.getLineDirections(i);
  
              final int end = (i == n - 1) ? where + after : reflowed.getLineStart(i + 1);
              ints[HYPHEN] = StaticLayout.packHyphenEdit(
                      reflowed.getStartHyphenEdit(i), reflowed.getEndHyphenEdit(i));
              ints[MAY_PROTRUDE_FROM_TOP_OR_BOTTOM] |=
                      contentMayProtrudeFromLineTopOrBottom(text, start, end) ?
                              MAY_PROTRUDE_FROM_TOP_OR_BOTTOM_MASK : 0;
  
              if (mEllipsize) {
                  ints[ELLIPSIS_START] = reflowed.getEllipsisStart(i);
                  ints[ELLIPSIS_COUNT] = reflowed.getEllipsisCount(i);
              }
  
              mInts.insertAt(startline + i, ints);
              mObjects.insertAt(startline + i, objects);
          }
  
          updateBlocks(startline, endline - 1, n);
  
          b.finish();
          synchronized (sLock) {
              sStaticLayout = reflowed;
              sBuilder = b;
          }
      }
  
      private boolean contentMayProtrudeFromLineTopOrBottom(CharSequence text, int start, int end) {
          if (text instanceof Spanned) {
              final Spanned spanned = (Spanned) text;
              if (spanned.getSpans(start, end, ReplacementSpan.class).length > 0) {
                  return true;
              }
          }
          // Spans other than ReplacementSpan can be ignored because line top and bottom are
          // disjunction of all tops and bottoms, although it's not optimal.
          final Paint paint = getPaint();
          if (text instanceof PrecomputedText) {
              PrecomputedText precomputed = (PrecomputedText) text;
              precomputed.getBounds(start, end, mTempRect);
          } else {
              paint.getTextBounds(text, start, end, mTempRect);
          }
          final Paint.FontMetricsInt fm = paint.getFontMetricsInt();
          return mTempRect.top < fm.top || mTempRect.bottom > fm.bottom;
      }
  
      /**
       * Create the initial block structure, cutting the text into blocks of at least
       * BLOCK_MINIMUM_CHARACTER_SIZE characters, aligned on the ends of paragraphs.
       */
      private void createBlocks() {
          int offset = BLOCK_MINIMUM_CHARACTER_LENGTH;
          mNumberOfBlocks = 0;
          final CharSequence text = mDisplay;
  
          while (true) {
              offset = TextUtils.indexOf(text, '\n', offset);
              if (offset < 0) {
                  addBlockAtOffset(text.length());
                  break;
              } else {
                  addBlockAtOffset(offset);
                  offset += BLOCK_MINIMUM_CHARACTER_LENGTH;
              }
          }
  
          // mBlockIndices and mBlockEndLines should have the same length
          mBlockIndices = new int[mBlockEndLines.length];
          for (int i = 0; i < mBlockEndLines.length; i++) {
              mBlockIndices[i] = INVALID_BLOCK_INDEX;
          }
      }
  
      /**
       * @hide
       */
      public ArraySet<Integer> getBlocksAlwaysNeedToBeRedrawn() {
          return mBlocksAlwaysNeedToBeRedrawn;
      }
  
      private void updateAlwaysNeedsToBeRedrawn(int blockIndex) {
          int startLine = blockIndex == 0 ? 0 : (mBlockEndLines[blockIndex - 1] + 1);
          int endLine = mBlockEndLines[blockIndex];
          for (int i = startLine; i <= endLine; i++) {
              if (getContentMayProtrudeFromTopOrBottom(i)) {
                  if (mBlocksAlwaysNeedToBeRedrawn == null) {
                      mBlocksAlwaysNeedToBeRedrawn = new ArraySet<>();
                  }
                  mBlocksAlwaysNeedToBeRedrawn.add(blockIndex);
                  return;
              }
          }
          if (mBlocksAlwaysNeedToBeRedrawn != null) {
              mBlocksAlwaysNeedToBeRedrawn.remove(blockIndex);
          }
      }
  
      /**
       * Create a new block, ending at the specified character offset.
       * A block will actually be created only if has at least one line, i.e. this offset is
       * not on the end line of the previous block.
       */
      private void addBlockAtOffset(int offset) {
          final int line = getLineForOffset(offset);
          if (mBlockEndLines == null) {
              // Initial creation of the array, no test on previous block ending line
              mBlockEndLines = ArrayUtils.newUnpaddedIntArray(1);
              mBlockEndLines[mNumberOfBlocks] = line;
              updateAlwaysNeedsToBeRedrawn(mNumberOfBlocks);
              mNumberOfBlocks++;
              return;
          }
  
          final int previousBlockEndLine = mBlockEndLines[mNumberOfBlocks - 1];
          if (line > previousBlockEndLine) {
              mBlockEndLines = GrowingArrayUtils.append(mBlockEndLines, mNumberOfBlocks, line);
              updateAlwaysNeedsToBeRedrawn(mNumberOfBlocks);
              mNumberOfBlocks++;
          }
      }
  
      /**
       * This method is called every time the layout is reflowed after an edition.
       * It updates the internal block data structure. The text is split in blocks
       * of contiguous lines, with at least one block for the entire text.
       * When a range of lines is edited, new blocks (from 0 to 3 depending on the
       * overlap structure) will replace the set of overlapping blocks.
       * Blocks are listed in order and are represented by their ending line number.
       * An index is associated to each block (which will be used by display lists),
       * this class simply invalidates the index of blocks overlapping a modification.
       *
       * @param startLine the first line of the range of modified lines
       * @param endLine the last line of the range, possibly equal to startLine, lower
       * than getLineCount()
       * @param newLineCount the number of lines that will replace the range, possibly 0
       *
       * @hide
       */
      @VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE)
      public void updateBlocks(int startLine, int endLine, int newLineCount) {
          if (mBlockEndLines == null) {
              createBlocks();
              return;
          }
  
          /*final*/ int firstBlock = -1;
          /*final*/ int lastBlock = -1;
          for (int i = 0; i < mNumberOfBlocks; i++) {
              if (mBlockEndLines[i] >= startLine) {
                  firstBlock = i;
                  break;
              }
          }
          for (int i = firstBlock; i < mNumberOfBlocks; i++) {
              if (mBlockEndLines[i] >= endLine) {
                  lastBlock = i;
                  break;
              }
          }
          final int lastBlockEndLine = mBlockEndLines[lastBlock];
  
          final boolean createBlockBefore = startLine > (firstBlock == 0 ? 0 :
                  mBlockEndLines[firstBlock - 1] + 1);
          final boolean createBlock = newLineCount > 0;
          final boolean createBlockAfter = endLine < mBlockEndLines[lastBlock];
  
          int numAddedBlocks = 0;
          if (createBlockBefore) numAddedBlocks++;
          if (createBlock) numAddedBlocks++;
          if (createBlockAfter) numAddedBlocks++;
  
          final int numRemovedBlocks = lastBlock - firstBlock + 1;
          final int newNumberOfBlocks = mNumberOfBlocks + numAddedBlocks - numRemovedBlocks;
  
          if (newNumberOfBlocks == 0) {
              // Even when text is empty, there is actually one line and hence one block
              mBlockEndLines[0] = 0;
              mBlockIndices[0] = INVALID_BLOCK_INDEX;
              mNumberOfBlocks = 1;
              return;
          }
  
          if (newNumberOfBlocks > mBlockEndLines.length) {
              int[] blockEndLines = ArrayUtils.newUnpaddedIntArray(
                      Math.max(mBlockEndLines.length * 2, newNumberOfBlocks));
              int[] blockIndices = new int[blockEndLines.length];
              System.arraycopy(mBlockEndLines, 0, blockEndLines, 0, firstBlock);
              System.arraycopy(mBlockIndices, 0, blockIndices, 0, firstBlock);
              System.arraycopy(mBlockEndLines, lastBlock + 1,
                      blockEndLines, firstBlock + numAddedBlocks, mNumberOfBlocks - lastBlock - 1);
              System.arraycopy(mBlockIndices, lastBlock + 1,
                      blockIndices, firstBlock + numAddedBlocks, mNumberOfBlocks - lastBlock - 1);
              mBlockEndLines = blockEndLines;
              mBlockIndices = blockIndices;
          } else if (numAddedBlocks + numRemovedBlocks != 0) {
              System.arraycopy(mBlockEndLines, lastBlock + 1,
                      mBlockEndLines, firstBlock + numAddedBlocks, mNumberOfBlocks - lastBlock - 1);
              System.arraycopy(mBlockIndices, lastBlock + 1,
                      mBlockIndices, firstBlock + numAddedBlocks, mNumberOfBlocks - lastBlock - 1);
          }
  
          if (numAddedBlocks + numRemovedBlocks != 0 && mBlocksAlwaysNeedToBeRedrawn != null) {
              final ArraySet<Integer> set = new ArraySet<>();
              final int changedBlockCount = numAddedBlocks - numRemovedBlocks;
              for (int i = 0; i < mBlocksAlwaysNeedToBeRedrawn.size(); i++) {
                  Integer block = mBlocksAlwaysNeedToBeRedrawn.valueAt(i);
                  if (block < firstBlock) {
                      // block index is before firstBlock add it since it did not change
                      set.add(block);
                  }
                  if (block > lastBlock) {
                      // block index is after lastBlock, the index reduced to += changedBlockCount
                      block += changedBlockCount;
                      set.add(block);
                  }
              }
              mBlocksAlwaysNeedToBeRedrawn = set;
          }
  
          mNumberOfBlocks = newNumberOfBlocks;
          int newFirstChangedBlock;
          final int deltaLines = newLineCount - (endLine - startLine + 1);
          if (deltaLines != 0) {
              // Display list whose index is >= mIndexFirstChangedBlock is valid
              // but it needs to update its drawing location.
              newFirstChangedBlock = firstBlock + numAddedBlocks;
              for (int i = newFirstChangedBlock; i < mNumberOfBlocks; i++) {
                  mBlockEndLines[i] += deltaLines;
              }
          } else {
              newFirstChangedBlock = mNumberOfBlocks;
          }
          mIndexFirstChangedBlock = Math.min(mIndexFirstChangedBlock, newFirstChangedBlock);
  
          int blockIndex = firstBlock;
          if (createBlockBefore) {
              mBlockEndLines[blockIndex] = startLine - 1;
              updateAlwaysNeedsToBeRedrawn(blockIndex);
              mBlockIndices[blockIndex] = INVALID_BLOCK_INDEX;
              blockIndex++;
          }
  
          if (createBlock) {
              mBlockEndLines[blockIndex] = startLine + newLineCount - 1;
              updateAlwaysNeedsToBeRedrawn(blockIndex);
              mBlockIndices[blockIndex] = INVALID_BLOCK_INDEX;
              blockIndex++;
          }
  
          if (createBlockAfter) {
              mBlockEndLines[blockIndex] = lastBlockEndLine + deltaLines;
              updateAlwaysNeedsToBeRedrawn(blockIndex);
              mBlockIndices[blockIndex] = INVALID_BLOCK_INDEX;
          }
      }
  
      /**
       * This method is used for test purposes only.
       * @hide
       */
      @VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE)
      public void setBlocksDataForTest(int[] blockEndLines, int[] blockIndices, int numberOfBlocks,
              int totalLines) {
          mBlockEndLines = new int[blockEndLines.length];
          mBlockIndices = new int[blockIndices.length];
          System.arraycopy(blockEndLines, 0, mBlockEndLines, 0, blockEndLines.length);
          System.arraycopy(blockIndices, 0, mBlockIndices, 0, blockIndices.length);
          mNumberOfBlocks = numberOfBlocks;
          while (mInts.size() < totalLines) {
              mInts.insertAt(mInts.size(), new int[COLUMNS_NORMAL]);
          }
      }
  
      /**
       * @hide
       */
      @UnsupportedAppUsage
      public int[] getBlockEndLines() {
          return mBlockEndLines;
      }
  
      /**
       * @hide
       */
      @UnsupportedAppUsage
      public int[] getBlockIndices() {
          return mBlockIndices;
      }
  
      /**
       * @hide
       */
      public int getBlockIndex(int index) {
          return mBlockIndices[index];
      }
  
      /**
       * @hide
       * @param index
       */
      public void setBlockIndex(int index, int blockIndex) {
          mBlockIndices[index] = blockIndex;
      }
  
      /**
       * @hide
       */
      @UnsupportedAppUsage
      public int getNumberOfBlocks() {
          return mNumberOfBlocks;
      }
  
      /**
       * @hide
       */
      @UnsupportedAppUsage
      public int getIndexFirstChangedBlock() {
          return mIndexFirstChangedBlock;
      }
  
      /**
       * @hide
       */
      @UnsupportedAppUsage
      public void setIndexFirstChangedBlock(int i) {
          mIndexFirstChangedBlock = i;
      }
  
      @Override
      public int getLineCount() {
          return mInts.size() - 1;
      }
  
      @Override
      public int getLineTop(int line) {
          return mInts.getValue(line, TOP);
      }
  
      @Override
      public int getLineDescent(int line) {
          return mInts.getValue(line, DESCENT);
      }
  
      /**
       * @hide
       */
      @Override
      public int getLineExtra(int line) {
          return mInts.getValue(line, EXTRA);
      }
  
      @Override
      public int getLineStart(int line) {
          return mInts.getValue(line, START) & START_MASK;
      }
  
      @Override
      public boolean getLineContainsTab(int line) {
          return (mInts.getValue(line, TAB) & TAB_MASK) != 0;
      }
  
      @Override
      public int getParagraphDirection(int line) {
          return mInts.getValue(line, DIR) >> DIR_SHIFT;
      }
  
      @Override
      public final Directions getLineDirections(int line) {
          return mObjects.getValue(line, 0);
      }
  
      @Override
      public int getTopPadding() {
          return mTopPadding;
      }
  
      @Override
      public int getBottomPadding() {
          return mBottomPadding;
      }
  
      /**
       * @hide
       */
      @Override
      public @Paint.StartHyphenEdit int getStartHyphenEdit(int line) {
          return StaticLayout.unpackStartHyphenEdit(mInts.getValue(line, HYPHEN) & HYPHEN_MASK);
      }
  
      /**
       * @hide
       */
      @Override
      public @Paint.EndHyphenEdit int getEndHyphenEdit(int line) {
          return StaticLayout.unpackEndHyphenEdit(mInts.getValue(line, HYPHEN) & HYPHEN_MASK);
      }
  
      private boolean getContentMayProtrudeFromTopOrBottom(int line) {
          return (mInts.getValue(line, MAY_PROTRUDE_FROM_TOP_OR_BOTTOM)
                  & MAY_PROTRUDE_FROM_TOP_OR_BOTTOM_MASK) != 0;
      }
  
      @Override
      public int getEllipsizedWidth() {
          return mEllipsizedWidth;
      }
  
      private static class ChangeWatcher implements TextWatcher, SpanWatcher {
          public ChangeWatcher(DynamicLayout layout) {
              mLayout = new WeakReference<>(layout);
          }
  
          private void reflow(CharSequence s, int where, int before, int after) {
              DynamicLayout ml = mLayout.get();
  
              if (ml != null) {
                  ml.reflow(s, where, before, after);
              } else if (s instanceof Spannable) {
                  ((Spannable) s).removeSpan(this);
              }
          }
  
          public void beforeTextChanged(CharSequence s, int where, int before, int after) {
              // Intentionally empty
          }
  
          public void onTextChanged(CharSequence s, int where, int before, int after) {
              reflow(s, where, before, after);
          }
  
          public void afterTextChanged(Editable s) {
              // Intentionally empty
          }
  
          public void onSpanAdded(Spannable s, Object o, int start, int end) {
              if (o instanceof UpdateLayout)
                  reflow(s, start, end - start, end - start);
          }
  
          public void onSpanRemoved(Spannable s, Object o, int start, int end) {
              if (o instanceof UpdateLayout)
                  reflow(s, start, end - start, end - start);
          }
  
          public void onSpanChanged(Spannable s, Object o, int start, int end, int nstart, int nend) {
              if (o instanceof UpdateLayout) {
                  if (start > end) {
                      // Bug: 67926915 start cannot be determined, fallback to reflow from start
                      // instead of causing an exception
                      start = 0;
                  }
                  reflow(s, start, end - start, end - start);
                  reflow(s, nstart, nend - nstart, nend - nstart);
              }
          }
  
          private WeakReference<DynamicLayout> mLayout;
      }
  
      @Override
      public int getEllipsisStart(int line) {
          if (mEllipsizeAt == null) {
              return 0;
          }
  
          return mInts.getValue(line, ELLIPSIS_START);
      }
  
      @Override
      public int getEllipsisCount(int line) {
          if (mEllipsizeAt == null) {
              return 0;
          }
  
          return mInts.getValue(line, ELLIPSIS_COUNT);
      }
  
      private CharSequence mBase;
      private CharSequence mDisplay;
      private ChangeWatcher mWatcher;
      private boolean mIncludePad;
      private boolean mFallbackLineSpacing;
      private boolean mEllipsize;
      private int mEllipsizedWidth;
      private TextUtils.TruncateAt mEllipsizeAt;
      private int mBreakStrategy;
      private int mHyphenationFrequency;
      private int mJustificationMode;
  
      private PackedIntVector mInts;
      private PackedObjectVector<Directions> mObjects;
  
      /**
       * Value used in mBlockIndices when a block has been created or recycled and indicating that its
       * display list needs to be re-created.
       * @hide
       */
      public static final int INVALID_BLOCK_INDEX = -1;
      // Stores the line numbers of the last line of each block (inclusive)
      private int[] mBlockEndLines;
      // The indices of this block's display list in TextView's internal display list array or
      // INVALID_BLOCK_INDEX if this block has been invalidated during an edition
      private int[] mBlockIndices;
      // Set of blocks that always need to be redrawn.
      private ArraySet<Integer> mBlocksAlwaysNeedToBeRedrawn;
      // Number of items actually currently being used in the above 2 arrays
      private int mNumberOfBlocks;
      // The first index of the blocks whose locations are changed
      private int mIndexFirstChangedBlock;
  
      private int mTopPadding, mBottomPadding;
  
      private Rect mTempRect = new Rect();
  
      @UnsupportedAppUsage
      private static StaticLayout sStaticLayout = null;
      private static StaticLayout.Builder sBuilder = null;
  
      private static final Object[] sLock = new Object[0];
  
      // START, DIR, and TAB share the same entry.
      private static final int START = 0;
      private static final int DIR = START;
      private static final int TAB = START;
      private static final int TOP = 1;
      private static final int DESCENT = 2;
      private static final int EXTRA = 3;
      // HYPHEN and MAY_PROTRUDE_FROM_TOP_OR_BOTTOM share the same entry.
      private static final int HYPHEN = 4;
      private static final int MAY_PROTRUDE_FROM_TOP_OR_BOTTOM = HYPHEN;
      private static final int COLUMNS_NORMAL = 5;
  
      private static final int ELLIPSIS_START = 5;
      private static final int ELLIPSIS_COUNT = 6;
      private static final int COLUMNS_ELLIPSIZE = 7;
  
      private static final int START_MASK = 0x1FFFFFFF;
      private static final int DIR_SHIFT  = 30;
      private static final int TAB_MASK   = 0x20000000;
      private static final int HYPHEN_MASK = 0xFF;
      private static final int MAY_PROTRUDE_FROM_TOP_OR_BOTTOM_MASK = 0x100;
  
      private static final int ELLIPSIS_UNDEFINED = 0x80000000;
  }
  