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.IntDef;
  import android.annotation.IntRange;
  import android.annotation.UnsupportedAppUsage;
  import android.graphics.Canvas;
  import android.graphics.Paint;
  import android.graphics.Path;
  import android.graphics.Rect;
  import android.graphics.text.LineBreaker;
  import android.text.method.TextKeyListener;
  import android.text.style.AlignmentSpan;
  import android.text.style.LeadingMarginSpan;
  import android.text.style.LeadingMarginSpan.LeadingMarginSpan2;
  import android.text.style.LineBackgroundSpan;
  import android.text.style.ParagraphStyle;
  import android.text.style.ReplacementSpan;
  import android.text.style.TabStopSpan;
  
  import com.android.internal.annotations.VisibleForTesting;
  import com.android.internal.util.ArrayUtils;
  import com.android.internal.util.GrowingArrayUtils;
  
  import java.lang.annotation.Retention;
  import java.lang.annotation.RetentionPolicy;
  import java.util.Arrays;
  
  /**
   * A base class that manages text layout in visual elements on
   * the screen.
   * <p>For text that will be edited, use a {@link DynamicLayout},
   * which will be updated as the text changes.
   * For text that will not change, use a {@link StaticLayout}.
   */
  public abstract class Layout {
      /** @hide */
      @IntDef(prefix = { "BREAK_STRATEGY_" }, value = {
              LineBreaker.BREAK_STRATEGY_SIMPLE,
              LineBreaker.BREAK_STRATEGY_HIGH_QUALITY,
              LineBreaker.BREAK_STRATEGY_BALANCED
      })
      @Retention(RetentionPolicy.SOURCE)
      public @interface BreakStrategy {}
  
      /**
       * Value for break strategy indicating simple line breaking. Automatic hyphens are not added
       * (though soft hyphens are respected), and modifying text generally doesn't affect the layout
       * before it (which yields a more consistent user experience when editing), but layout may not
       * be the highest quality.
       */
      public static final int BREAK_STRATEGY_SIMPLE = LineBreaker.BREAK_STRATEGY_SIMPLE;
  
      /**
       * Value for break strategy indicating high quality line breaking, including automatic
       * hyphenation and doing whole-paragraph optimization of line breaks.
       */
      public static final int BREAK_STRATEGY_HIGH_QUALITY = LineBreaker.BREAK_STRATEGY_HIGH_QUALITY;
  
      /**
       * Value for break strategy indicating balanced line breaking. The breaks are chosen to
       * make all lines as close to the same length as possible, including automatic hyphenation.
       */
      public static final int BREAK_STRATEGY_BALANCED = LineBreaker.BREAK_STRATEGY_BALANCED;
  
      /** @hide */
      @IntDef(prefix = { "HYPHENATION_FREQUENCY_" }, value = {
              HYPHENATION_FREQUENCY_NORMAL,
              HYPHENATION_FREQUENCY_FULL,
              HYPHENATION_FREQUENCY_NONE
      })
      @Retention(RetentionPolicy.SOURCE)
      public @interface HyphenationFrequency {}
  
      /**
       * Value for hyphenation frequency indicating no automatic hyphenation. Useful
       * for backward compatibility, and for cases where the automatic hyphenation algorithm results
       * in incorrect hyphenation. Mid-word breaks may still happen when a word is wider than the
       * layout and there is otherwise no valid break. Soft hyphens are ignored and will not be used
       * as suggestions for potential line breaks.
       */
      public static final int HYPHENATION_FREQUENCY_NONE = LineBreaker.HYPHENATION_FREQUENCY_NONE;
  
      /**
       * Value for hyphenation frequency indicating a light amount of automatic hyphenation, which
       * is a conservative default. Useful for informal cases, such as short sentences or chat
       * messages.
       */
      public static final int HYPHENATION_FREQUENCY_NORMAL = LineBreaker.HYPHENATION_FREQUENCY_NORMAL;
  
      /**
       * Value for hyphenation frequency indicating the full amount of automatic hyphenation, typical
       * in typography. Useful for running text and where it's important to put the maximum amount of
       * text in a screen with limited space.
       */
      public static final int HYPHENATION_FREQUENCY_FULL = LineBreaker.HYPHENATION_FREQUENCY_FULL;
  
      private static final ParagraphStyle[] NO_PARA_SPANS =
          ArrayUtils.emptyArray(ParagraphStyle.class);
  
      /** @hide */
      @IntDef(prefix = { "JUSTIFICATION_MODE_" }, value = {
              LineBreaker.JUSTIFICATION_MODE_NONE,
              LineBreaker.JUSTIFICATION_MODE_INTER_WORD
      })
      @Retention(RetentionPolicy.SOURCE)
      public @interface JustificationMode {}
  
      /**
       * Value for justification mode indicating no justification.
       */
      public static final int JUSTIFICATION_MODE_NONE = LineBreaker.JUSTIFICATION_MODE_NONE;
  
      /**
       * Value for justification mode indicating the text is justified by stretching word spacing.
       */
      public static final int JUSTIFICATION_MODE_INTER_WORD =
              LineBreaker.JUSTIFICATION_MODE_INTER_WORD;
  
      /*
       * Line spacing multiplier for default line spacing.
       */
      public static final float DEFAULT_LINESPACING_MULTIPLIER = 1.0f;
  
      /*
       * Line spacing addition for default line spacing.
       */
      public static final float DEFAULT_LINESPACING_ADDITION = 0.0f;
  
      /**
       * Return how wide a layout must be in order to display the specified text with one line per
       * paragraph.
       *
       * <p>As of O, Uses
       * {@link TextDirectionHeuristics#FIRSTSTRONG_LTR} as the default text direction heuristics. In
       * the earlier versions uses {@link TextDirectionHeuristics#LTR} as the default.</p>
       */
      public static float getDesiredWidth(CharSequence source,
                                          TextPaint paint) {
          return getDesiredWidth(source, 0, source.length(), paint);
      }
  
      /**
       * Return how wide a layout must be in order to display the specified text slice with one
       * line per paragraph.
       *
       * <p>As of O, Uses
       * {@link TextDirectionHeuristics#FIRSTSTRONG_LTR} as the default text direction heuristics. In
       * the earlier versions uses {@link TextDirectionHeuristics#LTR} as the default.</p>
       */
      public static float getDesiredWidth(CharSequence source, int start, int end, TextPaint paint) {
          return getDesiredWidth(source, start, end, paint, TextDirectionHeuristics.FIRSTSTRONG_LTR);
      }
  
      /**
       * Return how wide a layout must be in order to display the
       * specified text slice with one line per paragraph.
       *
       * @hide
       */
      public static float getDesiredWidth(CharSequence source, int start, int end, TextPaint paint,
              TextDirectionHeuristic textDir) {
          return getDesiredWidthWithLimit(source, start, end, paint, textDir, Float.MAX_VALUE);
      }
      /**
       * Return how wide a layout must be in order to display the
       * specified text slice with one line per paragraph.
       *
       * If the measured width exceeds given limit, returns limit value instead.
       * @hide
       */
      public static float getDesiredWidthWithLimit(CharSequence source, int start, int end,
              TextPaint paint, TextDirectionHeuristic textDir, float upperLimit) {
          float need = 0;
  
          int next;
          for (int i = start; i <= end; i = next) {
              next = TextUtils.indexOf(source, '\n', i, end);
  
              if (next < 0)
                  next = end;
  
              // note, omits trailing paragraph char
              float w = measurePara(paint, source, i, next, textDir);
              if (w > upperLimit) {
                  return upperLimit;
              }
  
              if (w > need)
                  need = w;
  
              next++;
          }
  
          return need;
      }
  
      /**
       * Subclasses of Layout use this constructor to set the display text,
       * width, and other standard properties.
       * @param text the text to render
       * @param paint the default paint for the layout.  Styles can override
       * various attributes of the paint.
       * @param width the wrapping width for the text.
       * @param align whether to left, right, or center the text.  Styles can
       * override the alignment.
       * @param spacingMult factor by which to scale the font size to get the
       * default line spacing
       * @param spacingAdd amount to add to the default line spacing
       */
      protected Layout(CharSequence text, TextPaint paint,
                       int width, Alignment align,
                       float spacingMult, float spacingAdd) {
          this(text, paint, width, align, TextDirectionHeuristics.FIRSTSTRONG_LTR,
                  spacingMult, spacingAdd);
      }
  
      /**
       * Subclasses of Layout use this constructor to set the display text,
       * width, and other standard properties.
       * @param text the text to render
       * @param paint the default paint for the layout.  Styles can override
       * various attributes of the paint.
       * @param width the wrapping width for the text.
       * @param align whether to left, right, or center the text.  Styles can
       * override the alignment.
       * @param spacingMult factor by which to scale the font size to get the
       * default line spacing
       * @param spacingAdd amount to add to the default line spacing
       *
       * @hide
       */
      protected Layout(CharSequence text, TextPaint paint,
                       int width, Alignment align, TextDirectionHeuristic textDir,
                       float spacingMult, float spacingAdd) {
  
          if (width < 0)
              throw new IllegalArgumentException("Layout: " + width + " < 0");
  
          // Ensure paint doesn't have baselineShift set.
          // While normally we don't modify the paint the user passed in,
          // we were already doing this in Styled.drawUniformRun with both
          // baselineShift and bgColor.  We probably should reevaluate bgColor.
          if (paint != null) {
              paint.bgColor = 0;
              paint.baselineShift = 0;
          }
  
          mText = text;
          mPaint = paint;
          mWidth = width;
          mAlignment = align;
          mSpacingMult = spacingMult;
          mSpacingAdd = spacingAdd;
          mSpannedText = text instanceof Spanned;
          mTextDir = textDir;
      }
  
      /** @hide */
      protected void setJustificationMode(@JustificationMode int justificationMode) {
          mJustificationMode = justificationMode;
      }
  
      /**
       * Replace constructor properties of this Layout with new ones.  Be careful.
       */
      /* package */ void replaceWith(CharSequence text, TextPaint paint,
                                int width, Alignment align,
                                float spacingmult, float spacingadd) {
          if (width < 0) {
              throw new IllegalArgumentException("Layout: " + width + " < 0");
          }
  
          mText = text;
          mPaint = paint;
          mWidth = width;
          mAlignment = align;
          mSpacingMult = spacingmult;
          mSpacingAdd = spacingadd;
          mSpannedText = text instanceof Spanned;
      }
  
      /**
       * Draw this Layout on the specified Canvas.
       */
      public void draw(Canvas c) {
          draw(c, null, null, 0);
      }
  
      /**
       * Draw this Layout on the specified canvas, with the highlight path drawn
       * between the background and the text.
       *
       * @param canvas the canvas
       * @param highlight the path of the highlight or cursor; can be null
       * @param highlightPaint the paint for the highlight
       * @param cursorOffsetVertical the amount to temporarily translate the
       *        canvas while rendering the highlight
       */
      public void draw(Canvas canvas, Path highlight, Paint highlightPaint,
              int cursorOffsetVertical) {
          final long lineRange = getLineRangeForDraw(canvas);
          int firstLine = TextUtils.unpackRangeStartFromLong(lineRange);
          int lastLine = TextUtils.unpackRangeEndFromLong(lineRange);
          if (lastLine < 0) return;
  
          drawBackground(canvas, highlight, highlightPaint, cursorOffsetVertical,
                  firstLine, lastLine);
          drawText(canvas, firstLine, lastLine);
      }
  
      private boolean isJustificationRequired(int lineNum) {
          if (mJustificationMode == JUSTIFICATION_MODE_NONE) return false;
          final int lineEnd = getLineEnd(lineNum);
          return lineEnd < mText.length() && mText.charAt(lineEnd - 1) != '\n';
      }
  
      private float getJustifyWidth(int lineNum) {
          Alignment paraAlign = mAlignment;
  
          int left = 0;
          int right = mWidth;
  
          final int dir = getParagraphDirection(lineNum);
  
          ParagraphStyle[] spans = NO_PARA_SPANS;
          if (mSpannedText) {
              Spanned sp = (Spanned) mText;
              final int start = getLineStart(lineNum);
  
              final boolean isFirstParaLine = (start == 0 || mText.charAt(start - 1) == '\n');
  
              if (isFirstParaLine) {
                  final int spanEnd = sp.nextSpanTransition(start, mText.length(),
                          ParagraphStyle.class);
                  spans = getParagraphSpans(sp, start, spanEnd, ParagraphStyle.class);
  
                  for (int n = spans.length - 1; n >= 0; n--) {
                      if (spans[n] instanceof AlignmentSpan) {
                          paraAlign = ((AlignmentSpan) spans[n]).getAlignment();
                          break;
                      }
                  }
              }
  
              final int length = spans.length;
              boolean useFirstLineMargin = isFirstParaLine;
              for (int n = 0; n < length; n++) {
                  if (spans[n] instanceof LeadingMarginSpan2) {
                      int count = ((LeadingMarginSpan2) spans[n]).getLeadingMarginLineCount();
                      int startLine = getLineForOffset(sp.getSpanStart(spans[n]));
                      if (lineNum < startLine + count) {
                          useFirstLineMargin = true;
                          break;
                      }
                  }
              }
              for (int n = 0; n < length; n++) {
                  if (spans[n] instanceof LeadingMarginSpan) {
                      LeadingMarginSpan margin = (LeadingMarginSpan) spans[n];
                      if (dir == DIR_RIGHT_TO_LEFT) {
                          right -= margin.getLeadingMargin(useFirstLineMargin);
                      } else {
                          left += margin.getLeadingMargin(useFirstLineMargin);
                      }
                  }
              }
          }
  
          final Alignment align;
          if (paraAlign == Alignment.ALIGN_LEFT) {
              align = (dir == DIR_LEFT_TO_RIGHT) ?  Alignment.ALIGN_NORMAL : Alignment.ALIGN_OPPOSITE;
          } else if (paraAlign == Alignment.ALIGN_RIGHT) {
              align = (dir == DIR_LEFT_TO_RIGHT) ?  Alignment.ALIGN_OPPOSITE : Alignment.ALIGN_NORMAL;
          } else {
              align = paraAlign;
          }
  
          final int indentWidth;
          if (align == Alignment.ALIGN_NORMAL) {
              if (dir == DIR_LEFT_TO_RIGHT) {
                  indentWidth = getIndentAdjust(lineNum, Alignment.ALIGN_LEFT);
              } else {
                  indentWidth = -getIndentAdjust(lineNum, Alignment.ALIGN_RIGHT);
              }
          } else if (align == Alignment.ALIGN_OPPOSITE) {
              if (dir == DIR_LEFT_TO_RIGHT) {
                  indentWidth = -getIndentAdjust(lineNum, Alignment.ALIGN_RIGHT);
              } else {
                  indentWidth = getIndentAdjust(lineNum, Alignment.ALIGN_LEFT);
              }
          } else { // Alignment.ALIGN_CENTER
              indentWidth = getIndentAdjust(lineNum, Alignment.ALIGN_CENTER);
          }
  
          return right - left - indentWidth;
      }
  
      /**
       * @hide
       */
      @UnsupportedAppUsage
      public void drawText(Canvas canvas, int firstLine, int lastLine) {
          int previousLineBottom = getLineTop(firstLine);
          int previousLineEnd = getLineStart(firstLine);
          ParagraphStyle[] spans = NO_PARA_SPANS;
          int spanEnd = 0;
          final TextPaint paint = mWorkPaint;
          paint.set(mPaint);
          CharSequence buf = mText;
  
          Alignment paraAlign = mAlignment;
          TabStops tabStops = null;
          boolean tabStopsIsInitialized = false;
  
          TextLine tl = TextLine.obtain();
  
          // Draw the lines, one at a time.
          // The baseline is the top of the following line minus the current line's descent.
          for (int lineNum = firstLine; lineNum <= lastLine; lineNum++) {
              int start = previousLineEnd;
              previousLineEnd = getLineStart(lineNum + 1);
              final boolean justify = isJustificationRequired(lineNum);
              int end = getLineVisibleEnd(lineNum, start, previousLineEnd);
              paint.setStartHyphenEdit(getStartHyphenEdit(lineNum));
              paint.setEndHyphenEdit(getEndHyphenEdit(lineNum));
  
              int ltop = previousLineBottom;
              int lbottom = getLineTop(lineNum + 1);
              previousLineBottom = lbottom;
              int lbaseline = lbottom - getLineDescent(lineNum);
  
              int dir = getParagraphDirection(lineNum);
              int left = 0;
              int right = mWidth;
  
              if (mSpannedText) {
                  Spanned sp = (Spanned) buf;
                  int textLength = buf.length();
                  boolean isFirstParaLine = (start == 0 || buf.charAt(start - 1) == '\n');
  
                  // New batch of paragraph styles, collect into spans array.
                  // Compute the alignment, last alignment style wins.
                  // Reset tabStops, we'll rebuild if we encounter a line with
                  // tabs.
                  // We expect paragraph spans to be relatively infrequent, use
                  // spanEnd so that we can check less frequently.  Since
                  // paragraph styles ought to apply to entire paragraphs, we can
                  // just collect the ones present at the start of the paragraph.
                  // If spanEnd is before the end of the paragraph, that's not
                  // our problem.
                  if (start >= spanEnd && (lineNum == firstLine || isFirstParaLine)) {
                      spanEnd = sp.nextSpanTransition(start, textLength,
                                                      ParagraphStyle.class);
                      spans = getParagraphSpans(sp, start, spanEnd, ParagraphStyle.class);
  
                      paraAlign = mAlignment;
                      for (int n = spans.length - 1; n >= 0; n--) {
                          if (spans[n] instanceof AlignmentSpan) {
                              paraAlign = ((AlignmentSpan) spans[n]).getAlignment();
                              break;
                          }
                      }
  
                      tabStopsIsInitialized = false;
                  }
  
                  // Draw all leading margin spans.  Adjust left or right according
                  // to the paragraph direction of the line.
                  final int length = spans.length;
                  boolean useFirstLineMargin = isFirstParaLine;
                  for (int n = 0; n < length; n++) {
                      if (spans[n] instanceof LeadingMarginSpan2) {
                          int count = ((LeadingMarginSpan2) spans[n]).getLeadingMarginLineCount();
                          int startLine = getLineForOffset(sp.getSpanStart(spans[n]));
                          // if there is more than one LeadingMarginSpan2, use
                          // the count that is greatest
                          if (lineNum < startLine + count) {
                              useFirstLineMargin = true;
                              break;
                          }
                      }
                  }
                  for (int n = 0; n < length; n++) {
                      if (spans[n] instanceof LeadingMarginSpan) {
                          LeadingMarginSpan margin = (LeadingMarginSpan) spans[n];
                          if (dir == DIR_RIGHT_TO_LEFT) {
                              margin.drawLeadingMargin(canvas, paint, right, dir, ltop,
                                                       lbaseline, lbottom, buf,
                                                       start, end, isFirstParaLine, this);
                              right -= margin.getLeadingMargin(useFirstLineMargin);
                          } else {
                              margin.drawLeadingMargin(canvas, paint, left, dir, ltop,
                                                       lbaseline, lbottom, buf,
                                                       start, end, isFirstParaLine, this);
                              left += margin.getLeadingMargin(useFirstLineMargin);
                          }
                      }
                  }
              }
  
              boolean hasTab = getLineContainsTab(lineNum);
              // Can't tell if we have tabs for sure, currently
              if (hasTab && !tabStopsIsInitialized) {
                  if (tabStops == null) {
                      tabStops = new TabStops(TAB_INCREMENT, spans);
                  } else {
                      tabStops.reset(TAB_INCREMENT, spans);
                  }
                  tabStopsIsInitialized = true;
              }
  
              // Determine whether the line aligns to normal, opposite, or center.
              Alignment align = paraAlign;
              if (align == Alignment.ALIGN_LEFT) {
                  align = (dir == DIR_LEFT_TO_RIGHT) ?
                      Alignment.ALIGN_NORMAL : Alignment.ALIGN_OPPOSITE;
              } else if (align == Alignment.ALIGN_RIGHT) {
                  align = (dir == DIR_LEFT_TO_RIGHT) ?
                      Alignment.ALIGN_OPPOSITE : Alignment.ALIGN_NORMAL;
              }
  
              int x;
              final int indentWidth;
              if (align == Alignment.ALIGN_NORMAL) {
                  if (dir == DIR_LEFT_TO_RIGHT) {
                      indentWidth = getIndentAdjust(lineNum, Alignment.ALIGN_LEFT);
                      x = left + indentWidth;
                  } else {
                      indentWidth = -getIndentAdjust(lineNum, Alignment.ALIGN_RIGHT);
                      x = right - indentWidth;
                  }
              } else {
                  int max = (int)getLineExtent(lineNum, tabStops, false);
                  if (align == Alignment.ALIGN_OPPOSITE) {
                      if (dir == DIR_LEFT_TO_RIGHT) {
                          indentWidth = -getIndentAdjust(lineNum, Alignment.ALIGN_RIGHT);
                          x = right - max - indentWidth;
                      } else {
                          indentWidth = getIndentAdjust(lineNum, Alignment.ALIGN_LEFT);
                          x = left - max + indentWidth;
                      }
                  } else { // Alignment.ALIGN_CENTER
                      indentWidth = getIndentAdjust(lineNum, Alignment.ALIGN_CENTER);
                      max = max & ~1;
                      x = ((right + left - max) >> 1) + indentWidth;
                  }
              }
  
              Directions directions = getLineDirections(lineNum);
              if (directions == DIRS_ALL_LEFT_TO_RIGHT && !mSpannedText && !hasTab && !justify) {
                  // XXX: assumes there's nothing additional to be done
                  canvas.drawText(buf, start, end, x, lbaseline, paint);
              } else {
                  tl.set(paint, buf, start, end, dir, directions, hasTab, tabStops,
                          getEllipsisStart(lineNum),
                          getEllipsisStart(lineNum) + getEllipsisCount(lineNum));
                  if (justify) {
                      tl.justify(right - left - indentWidth);
                  }
                  tl.draw(canvas, x, ltop, lbaseline, lbottom);
              }
          }
  
          TextLine.recycle(tl);
      }
  
      /**
       * @hide
       */
      @UnsupportedAppUsage
      public void drawBackground(Canvas canvas, Path highlight, Paint highlightPaint,
              int cursorOffsetVertical, int firstLine, int lastLine) {
          // First, draw LineBackgroundSpans.
          // LineBackgroundSpans know nothing about the alignment, margins, or
          // direction of the layout or line.  XXX: Should they?
          // They are evaluated at each line.
          if (mSpannedText) {
              if (mLineBackgroundSpans == null) {
                  mLineBackgroundSpans = new SpanSet<LineBackgroundSpan>(LineBackgroundSpan.class);
              }
  
              Spanned buffer = (Spanned) mText;
              int textLength = buffer.length();
              mLineBackgroundSpans.init(buffer, 0, textLength);
  
              if (mLineBackgroundSpans.numberOfSpans > 0) {
                  int previousLineBottom = getLineTop(firstLine);
                  int previousLineEnd = getLineStart(firstLine);
                  ParagraphStyle[] spans = NO_PARA_SPANS;
                  int spansLength = 0;
                  TextPaint paint = mPaint;
                  int spanEnd = 0;
                  final int width = mWidth;
                  for (int i = firstLine; i <= lastLine; i++) {
                      int start = previousLineEnd;
                      int end = getLineStart(i + 1);
                      previousLineEnd = end;
  
                      int ltop = previousLineBottom;
                      int lbottom = getLineTop(i + 1);
                      previousLineBottom = lbottom;
                      int lbaseline = lbottom - getLineDescent(i);
  
                      if (end >= spanEnd) {
                          // These should be infrequent, so we'll use this so that
                          // we don't have to check as often.
                          spanEnd = mLineBackgroundSpans.getNextTransition(start, textLength);
                          // All LineBackgroundSpans on a line contribute to its background.
                          spansLength = 0;
                          // Duplication of the logic of getParagraphSpans
                          if (start != end || start == 0) {
                              // Equivalent to a getSpans(start, end), but filling the 'spans' local
                              // array instead to reduce memory allocation
                              for (int j = 0; j < mLineBackgroundSpans.numberOfSpans; j++) {
                                  // equal test is valid since both intervals are not empty by
                                  // construction
                                  if (mLineBackgroundSpans.spanStarts[j] >= end ||
                                          mLineBackgroundSpans.spanEnds[j] <= start) continue;
                                  spans = GrowingArrayUtils.append(
                                          spans, spansLength, mLineBackgroundSpans.spans[j]);
                                  spansLength++;
                              }
                          }
                      }
  
                      for (int n = 0; n < spansLength; n++) {
                          LineBackgroundSpan lineBackgroundSpan = (LineBackgroundSpan) spans[n];
                          lineBackgroundSpan.drawBackground(canvas, paint, 0, width,
                                  ltop, lbaseline, lbottom,
                                  buffer, start, end, i);
                      }
                  }
              }
              mLineBackgroundSpans.recycle();
          }
  
          // There can be a highlight even without spans if we are drawing
          // a non-spanned transformation of a spanned editing buffer.
          if (highlight != null) {
              if (cursorOffsetVertical != 0) canvas.translate(0, cursorOffsetVertical);
              canvas.drawPath(highlight, highlightPaint);
              if (cursorOffsetVertical != 0) canvas.translate(0, -cursorOffsetVertical);
          }
      }
  
      /**
       * @param canvas
       * @return The range of lines that need to be drawn, possibly empty.
       * @hide
       */
      @UnsupportedAppUsage
      public long getLineRangeForDraw(Canvas canvas) {
          int dtop, dbottom;
  
          synchronized (sTempRect) {
              if (!canvas.getClipBounds(sTempRect)) {
                  // Negative range end used as a special flag
                  return TextUtils.packRangeInLong(0, -1);
              }
  
              dtop = sTempRect.top;
              dbottom = sTempRect.bottom;
          }
  
          final int top = Math.max(dtop, 0);
          final int bottom = Math.min(getLineTop(getLineCount()), dbottom);
  
          if (top >= bottom) return TextUtils.packRangeInLong(0, -1);
          return TextUtils.packRangeInLong(getLineForVertical(top), getLineForVertical(bottom));
      }
  
      /**
       * Return the start position of the line, given the left and right bounds
       * of the margins.
       *
       * @param line the line index
       * @param left the left bounds (0, or leading margin if ltr para)
       * @param right the right bounds (width, minus leading margin if rtl para)
       * @return the start position of the line (to right of line if rtl para)
       */
      private int getLineStartPos(int line, int left, int right) {
          // Adjust the point at which to start rendering depending on the
          // alignment of the paragraph.
          Alignment align = getParagraphAlignment(line);
          int dir = getParagraphDirection(line);
  
          if (align == Alignment.ALIGN_LEFT) {
              align = (dir == DIR_LEFT_TO_RIGHT) ? Alignment.ALIGN_NORMAL : Alignment.ALIGN_OPPOSITE;
          } else if (align == Alignment.ALIGN_RIGHT) {
              align = (dir == DIR_LEFT_TO_RIGHT) ? Alignment.ALIGN_OPPOSITE : Alignment.ALIGN_NORMAL;
          }
  
          int x;
          if (align == Alignment.ALIGN_NORMAL) {
              if (dir == DIR_LEFT_TO_RIGHT) {
                  x = left + getIndentAdjust(line, Alignment.ALIGN_LEFT);
              } else {
                  x = right + getIndentAdjust(line, Alignment.ALIGN_RIGHT);
              }
          } else {
              TabStops tabStops = null;
              if (mSpannedText && getLineContainsTab(line)) {
                  Spanned spanned = (Spanned) mText;
                  int start = getLineStart(line);
                  int spanEnd = spanned.nextSpanTransition(start, spanned.length(),
                          TabStopSpan.class);
                  TabStopSpan[] tabSpans = getParagraphSpans(spanned, start, spanEnd,
                          TabStopSpan.class);
                  if (tabSpans.length > 0) {
                      tabStops = new TabStops(TAB_INCREMENT, tabSpans);
                  }
              }
              int max = (int)getLineExtent(line, tabStops, false);
              if (align == Alignment.ALIGN_OPPOSITE) {
                  if (dir == DIR_LEFT_TO_RIGHT) {
                      x = right - max + getIndentAdjust(line, Alignment.ALIGN_RIGHT);
                  } else {
                      // max is negative here
                      x = left - max + getIndentAdjust(line, Alignment.ALIGN_LEFT);
                  }
              } else { // Alignment.ALIGN_CENTER
                  max = max & ~1;
                  x = (left + right - max) >> 1 + getIndentAdjust(line, Alignment.ALIGN_CENTER);
              }
          }
          return x;
      }
  
      /**
       * Return the text that is displayed by this Layout.
       */
      public final CharSequence getText() {
          return mText;
      }
  
      /**
       * Return the base Paint properties for this layout.
       * Do NOT change the paint, which may result in funny
       * drawing for this layout.
       */
      public final TextPaint getPaint() {
          return mPaint;
      }
  
      /**
       * Return the width of this layout.
       */
      public final int getWidth() {
          return mWidth;
      }
  
      /**
       * Return the width to which this Layout is ellipsizing, or
       * {@link #getWidth} if it is not doing anything special.
       */
      public int getEllipsizedWidth() {
          return mWidth;
      }
  
      /**
       * Increase the width of this layout to the specified width.
       * Be careful to use this only when you know it is appropriate&mdash;
       * it does not cause the text to reflow to use the full new width.
       */
      public final void increaseWidthTo(int wid) {
          if (wid < mWidth) {
              throw new RuntimeException("attempted to reduce Layout width");
          }
  
          mWidth = wid;
      }
  
      /**
       * Return the total height of this layout.
       */
      public int getHeight() {
          return getLineTop(getLineCount());
      }
  
      /**
       * Return the total height of this layout.
       *
       * @param cap if true and max lines is set, returns the height of the layout at the max lines.
       *
       * @hide
       */
      public int getHeight(boolean cap) {
          return getHeight();
      }
  
      /**
       * Return the base alignment of this layout.
       */
      public final Alignment getAlignment() {
          return mAlignment;
      }
  
      /**
       * Return what the text height is multiplied by to get the line height.
       */
      public final float getSpacingMultiplier() {
          return mSpacingMult;
      }
  
      /**
       * Return the number of units of leading that are added to each line.
       */
      public final float getSpacingAdd() {
          return mSpacingAdd;
      }
  
      /**
       * Return the heuristic used to determine paragraph text direction.
       * @hide
       */
      public final TextDirectionHeuristic getTextDirectionHeuristic() {
          return mTextDir;
      }
  
      /**
       * Return the number of lines of text in this layout.
       */
      public abstract int getLineCount();
  
      /**
       * Return the baseline for the specified line (0&hellip;getLineCount() - 1)
       * If bounds is not null, return the top, left, right, bottom extents
       * of the specified line in it.
       * @param line which line to examine (0..getLineCount() - 1)
       * @param bounds Optional. If not null, it returns the extent of the line
       * @return the Y-coordinate of the baseline
       */
      public int getLineBounds(int line, Rect bounds) {
          if (bounds != null) {
              bounds.left = 0;     // ???
              bounds.top = getLineTop(line);
              bounds.right = mWidth;   // ???
              bounds.bottom = getLineTop(line + 1);
          }
          return getLineBaseline(line);
      }
  
      /**
       * Return the vertical position of the top of the specified line
       * (0&hellip;getLineCount()).
       * If the specified line is equal to the line count, returns the
       * bottom of the last line.
       */
      public abstract int getLineTop(int line);
  
      /**
       * Return the descent of the specified line(0&hellip;getLineCount() - 1).
       */
      public abstract int getLineDescent(int line);
  
      /**
       * Return the text offset of the beginning of the specified line (
       * 0&hellip;getLineCount()). If the specified line is equal to the line
       * count, returns the length of the text.
       */
      public abstract int getLineStart(int line);
  
      /**
       * Returns the primary directionality of the paragraph containing the
       * specified line, either 1 for left-to-right lines, or -1 for right-to-left
       * lines (see {@link #DIR_LEFT_TO_RIGHT}, {@link #DIR_RIGHT_TO_LEFT}).
       */
      public abstract int getParagraphDirection(int line);
  
      /**
       * Returns whether the specified line contains one or more
       * characters that need to be handled specially, like tabs.
       */
      public abstract boolean getLineContainsTab(int line);
  
      /**
       * Returns the directional run information for the specified line.
       * The array alternates counts of characters in left-to-right
       * and right-to-left segments of the line.
       *
       * <p>NOTE: this is inadequate to support bidirectional text, and will change.
       */
      public abstract Directions getLineDirections(int line);
  
      /**
       * Returns the (negative) number of extra pixels of ascent padding in the
       * top line of the Layout.
       */
      public abstract int getTopPadding();
  
      /**
       * Returns the number of extra pixels of descent padding in the
       * bottom line of the Layout.
       */
      public abstract int getBottomPadding();
  
      /**
       * Returns the start hyphen edit for a line.
       *
       * @hide
       */
      public @Paint.StartHyphenEdit int getStartHyphenEdit(int line) {
          return Paint.START_HYPHEN_EDIT_NO_EDIT;
      }
  
      /**
       * Returns the end hyphen edit for a line.
       *
       * @hide
       */
      public @Paint.EndHyphenEdit int getEndHyphenEdit(int line) {
          return Paint.END_HYPHEN_EDIT_NO_EDIT;
      }
  
      /**
       * Returns the left indent for a line.
       *
       * @hide
       */
      public int getIndentAdjust(int line, Alignment alignment) {
          return 0;
      }
  
      /**
       * Returns true if the character at offset and the preceding character
       * are at different run levels (and thus there's a split caret).
       * @param offset the offset
       * @return true if at a level boundary
       * @hide
       */
      @UnsupportedAppUsage
      public boolean isLevelBoundary(int offset) {
          int line = getLineForOffset(offset);
          Directions dirs = getLineDirections(line);
          if (dirs == DIRS_ALL_LEFT_TO_RIGHT || dirs == DIRS_ALL_RIGHT_TO_LEFT) {
              return false;
          }
  
          int[] runs = dirs.mDirections;
          int lineStart = getLineStart(line);
          int lineEnd = getLineEnd(line);
          if (offset == lineStart || offset == lineEnd) {
              int paraLevel = getParagraphDirection(line) == 1 ? 0 : 1;
              int runIndex = offset == lineStart ? 0 : runs.length - 2;
              return ((runs[runIndex + 1] >>> RUN_LEVEL_SHIFT) & RUN_LEVEL_MASK) != paraLevel;
          }
  
          offset -= lineStart;
          for (int i = 0; i < runs.length; i += 2) {
              if (offset == runs[i]) {
                  return true;
              }
          }
          return false;
      }
  
      /**
       * Returns true if the character at offset is right to left (RTL).
       * @param offset the offset
       * @return true if the character is RTL, false if it is LTR
       */
      public boolean isRtlCharAt(int offset) {
          int line = getLineForOffset(offset);
          Directions dirs = getLineDirections(line);
          if (dirs == DIRS_ALL_LEFT_TO_RIGHT) {
              return false;
          }
          if (dirs == DIRS_ALL_RIGHT_TO_LEFT) {
              return  true;
          }
          int[] runs = dirs.mDirections;
          int lineStart = getLineStart(line);
          for (int i = 0; i < runs.length; i += 2) {
              int start = lineStart + runs[i];
              int limit = start + (runs[i+1] & RUN_LENGTH_MASK);
              if (offset >= start && offset < limit) {
                  int level = (runs[i+1] >>> RUN_LEVEL_SHIFT) & RUN_LEVEL_MASK;
                  return ((level & 1) != 0);
              }
          }
          // Should happen only if the offset is "out of bounds"
          return false;
      }
  
      /**
       * Returns the range of the run that the character at offset belongs to.
       * @param offset the offset
       * @return The range of the run
       * @hide
       */
      public long getRunRange(int offset) {
          int line = getLineForOffset(offset);
          Directions dirs = getLineDirections(line);
          if (dirs == DIRS_ALL_LEFT_TO_RIGHT || dirs == DIRS_ALL_RIGHT_TO_LEFT) {
              return TextUtils.packRangeInLong(0, getLineEnd(line));
          }
          int[] runs = dirs.mDirections;
          int lineStart = getLineStart(line);
          for (int i = 0; i < runs.length; i += 2) {
              int start = lineStart + runs[i];
              int limit = start + (runs[i+1] & RUN_LENGTH_MASK);
              if (offset >= start && offset < limit) {
                  return TextUtils.packRangeInLong(start, limit);
              }
          }
          // Should happen only if the offset is "out of bounds"
          return TextUtils.packRangeInLong(0, getLineEnd(line));
      }
  
      /**
       * Checks if the trailing BiDi level should be used for an offset
       *
       * This method is useful when the offset is at the BiDi level transition point and determine
       * which run need to be used. For example, let's think about following input: (L* denotes
       * Left-to-Right characters, R* denotes Right-to-Left characters.)
       * Input (Logical Order): L1 L2 L3 R1 R2 R3 L4 L5 L6
       * Input (Display Order): L1 L2 L3 R3 R2 R1 L4 L5 L6
       *
       * Then, think about selecting the range (3, 6). The offset=3 and offset=6 are ambiguous here
       * since they are at the BiDi transition point.  In Android, the offset is considered to be
       * associated with the trailing run if the BiDi level of the trailing run is higher than of the
       * previous run.  In this case, the BiDi level of the input text is as follows:
       *
       * Input (Logical Order): L1 L2 L3 R1 R2 R3 L4 L5 L6
       *              BiDi Run: [ Run 0 ][ Run 1 ][ Run 2 ]
       *            BiDi Level:  0  0  0  1  1  1  0  0  0
       *
       * Thus, offset = 3 is part of Run 1 and this method returns true for offset = 3, since the BiDi
       * level of Run 1 is higher than the level of Run 0.  Similarly, the offset = 6 is a part of Run
       * 1 and this method returns false for the offset = 6 since the BiDi level of Run 1 is higher
       * than the level of Run 2.
       *
       * @returns true if offset is at the BiDi level transition point and trailing BiDi level is
       *          higher than previous BiDi level. See above for the detail.
       * @hide
       */
      @VisibleForTesting
      public boolean primaryIsTrailingPrevious(int offset) {
          int line = getLineForOffset(offset);
          int lineStart = getLineStart(line);
          int lineEnd = getLineEnd(line);
          int[] runs = getLineDirections(line).mDirections;
  
          int levelAt = -1;
          for (int i = 0; i < runs.length; i += 2) {
              int start = lineStart + runs[i];
              int limit = start + (runs[i+1] & RUN_LENGTH_MASK);
              if (limit > lineEnd) {
                  limit = lineEnd;
              }
              if (offset >= start && offset < limit) {
                  if (offset > start) {
                      // Previous character is at same level, so don't use trailing.
                      return false;
                  }
                  levelAt = (runs[i+1] >>> RUN_LEVEL_SHIFT) & RUN_LEVEL_MASK;
                  break;
              }
          }
          if (levelAt == -1) {
              // Offset was limit of line.
              levelAt = getParagraphDirection(line) == 1 ? 0 : 1;
          }
  
          // At level boundary, check previous level.
          int levelBefore = -1;
          if (offset == lineStart) {
              levelBefore = getParagraphDirection(line) == 1 ? 0 : 1;
          } else {
              offset -= 1;
              for (int i = 0; i < runs.length; i += 2) {
                  int start = lineStart + runs[i];
                  int limit = start + (runs[i+1] & RUN_LENGTH_MASK);
                  if (limit > lineEnd) {
                      limit = lineEnd;
                  }
                  if (offset >= start && offset < limit) {
                      levelBefore = (runs[i+1] >>> RUN_LEVEL_SHIFT) & RUN_LEVEL_MASK;
                      break;
                  }
              }
          }
  
          return levelBefore < levelAt;
      }
  
      /**
       * Computes in linear time the results of calling
       * #primaryIsTrailingPrevious for all offsets on a line.
       * @param line The line giving the offsets we compute the information for
       * @return The array of results, indexed from 0, where 0 corresponds to the line start offset
       * @hide
       */
      @VisibleForTesting
      public boolean[] primaryIsTrailingPreviousAllLineOffsets(int line) {
          int lineStart = getLineStart(line);
          int lineEnd = getLineEnd(line);
          int[] runs = getLineDirections(line).mDirections;
  
          boolean[] trailing = new boolean[lineEnd - lineStart + 1];
  
          byte[] level = new byte[lineEnd - lineStart + 1];
          for (int i = 0; i < runs.length; i += 2) {
              int start = lineStart + runs[i];
              int limit = start + (runs[i + 1] & RUN_LENGTH_MASK);
              if (limit > lineEnd) {
                  limit = lineEnd;
              }
              if (limit == start) {
                  continue;
              }
              level[limit - lineStart - 1] =
                      (byte) ((runs[i + 1] >>> RUN_LEVEL_SHIFT) & RUN_LEVEL_MASK);
          }
  
          for (int i = 0; i < runs.length; i += 2) {
              int start = lineStart + runs[i];
              byte currentLevel = (byte) ((runs[i + 1] >>> RUN_LEVEL_SHIFT) & RUN_LEVEL_MASK);
              trailing[start - lineStart] = currentLevel > (start == lineStart
                      ? (getParagraphDirection(line) == 1 ? 0 : 1)
                      : level[start - lineStart - 1]);
          }
  
          return trailing;
      }
  
      /**
       * Get the primary horizontal position for the specified text offset.
       * This is the location where a new character would be inserted in
       * the paragraph's primary direction.
       */
      public float getPrimaryHorizontal(int offset) {
          return getPrimaryHorizontal(offset, false /* not clamped */);
      }
  
      /**
       * Get the primary horizontal position for the specified text offset, but
       * optionally clamp it so that it doesn't exceed the width of the layout.
       * @hide
       */
      @UnsupportedAppUsage
      public float getPrimaryHorizontal(int offset, boolean clamped) {
          boolean trailing = primaryIsTrailingPrevious(offset);
          return getHorizontal(offset, trailing, clamped);
      }
  
      /**
       * Get the secondary horizontal position for the specified text offset.
       * This is the location where a new character would be inserted in
       * the direction other than the paragraph's primary direction.
       */
      public float getSecondaryHorizontal(int offset) {
          return getSecondaryHorizontal(offset, false /* not clamped */);
      }
  
      /**
       * Get the secondary horizontal position for the specified text offset, but
       * optionally clamp it so that it doesn't exceed the width of the layout.
       * @hide
       */
      @UnsupportedAppUsage
      public float getSecondaryHorizontal(int offset, boolean clamped) {
          boolean trailing = primaryIsTrailingPrevious(offset);
          return getHorizontal(offset, !trailing, clamped);
      }
  
      private float getHorizontal(int offset, boolean primary) {
          return primary ? getPrimaryHorizontal(offset) : getSecondaryHorizontal(offset);
      }
  
      private float getHorizontal(int offset, boolean trailing, boolean clamped) {
          int line = getLineForOffset(offset);
  
          return getHorizontal(offset, trailing, line, clamped);
      }
  
      private float getHorizontal(int offset, boolean trailing, int line, boolean clamped) {
          int start = getLineStart(line);
          int end = getLineEnd(line);
          int dir = getParagraphDirection(line);
          boolean hasTab = getLineContainsTab(line);
          Directions directions = getLineDirections(line);
  
          TabStops tabStops = null;
          if (hasTab && mText instanceof Spanned) {
              // Just checking this line should be good enough, tabs should be
              // consistent across all lines in a paragraph.
              TabStopSpan[] tabs = getParagraphSpans((Spanned) mText, start, end, TabStopSpan.class);
              if (tabs.length > 0) {
                  tabStops = new TabStops(TAB_INCREMENT, tabs); // XXX should reuse
              }
          }
  
          TextLine tl = TextLine.obtain();
          tl.set(mPaint, mText, start, end, dir, directions, hasTab, tabStops,
                  getEllipsisStart(line), getEllipsisStart(line) + getEllipsisCount(line));
          float wid = tl.measure(offset - start, trailing, null);
          TextLine.recycle(tl);
  
          if (clamped && wid > mWidth) {
              wid = mWidth;
          }
          int left = getParagraphLeft(line);
          int right = getParagraphRight(line);
  
          return getLineStartPos(line, left, right) + wid;
      }
  
      /**
       * Computes in linear time the results of calling #getHorizontal for all offsets on a line.
       *
       * @param line The line giving the offsets we compute information for
       * @param clamped Whether to clamp the results to the width of the layout
       * @param primary Whether the results should be the primary or the secondary horizontal
       * @return The array of results, indexed from 0, where 0 corresponds to the line start offset
       */
      private float[] getLineHorizontals(int line, boolean clamped, boolean primary) {
          int start = getLineStart(line);
          int end = getLineEnd(line);
          int dir = getParagraphDirection(line);
          boolean hasTab = getLineContainsTab(line);
          Directions directions = getLineDirections(line);
  
          TabStops tabStops = null;
          if (hasTab && mText instanceof Spanned) {
              // Just checking this line should be good enough, tabs should be
              // consistent across all lines in a paragraph.
              TabStopSpan[] tabs = getParagraphSpans((Spanned) mText, start, end, TabStopSpan.class);
              if (tabs.length > 0) {
                  tabStops = new TabStops(TAB_INCREMENT, tabs); // XXX should reuse
              }
          }
  
          TextLine tl = TextLine.obtain();
          tl.set(mPaint, mText, start, end, dir, directions, hasTab, tabStops,
                  getEllipsisStart(line), getEllipsisStart(line) + getEllipsisCount(line));
          boolean[] trailings = primaryIsTrailingPreviousAllLineOffsets(line);
          if (!primary) {
              for (int offset = 0; offset < trailings.length; ++offset) {
                  trailings[offset] = !trailings[offset];
              }
          }
          float[] wid = tl.measureAllOffsets(trailings, null);
          TextLine.recycle(tl);
  
          if (clamped) {
              for (int offset = 0; offset < wid.length; ++offset) {
                  if (wid[offset] > mWidth) {
                      wid[offset] = mWidth;
                  }
              }
          }
          int left = getParagraphLeft(line);
          int right = getParagraphRight(line);
  
          int lineStartPos = getLineStartPos(line, left, right);
          float[] horizontal = new float[end - start + 1];
          for (int offset = 0; offset < horizontal.length; ++offset) {
              horizontal[offset] = lineStartPos + wid[offset];
          }
          return horizontal;
      }
  
      /**
       * Get the leftmost position that should be exposed for horizontal
       * scrolling on the specified line.
       */
      public float getLineLeft(int line) {
          final int dir = getParagraphDirection(line);
          Alignment align = getParagraphAlignment(line);
          // Before Q, StaticLayout.Builder.setAlignment didn't check whether the input alignment
          // is null. And when it is null, the old behavior is the same as ALIGN_CENTER.
          // To keep consistency, we convert a null alignment to ALIGN_CENTER.
          if (align == null) {
              align = Alignment.ALIGN_CENTER;
          }
  
          // First convert combinations of alignment and direction settings to
          // three basic cases: ALIGN_LEFT, ALIGN_RIGHT and ALIGN_CENTER.
          // For unexpected cases, it will fallback to ALIGN_LEFT.
          final Alignment resultAlign;
          switch(align) {
              case ALIGN_NORMAL:
                  resultAlign =
                          dir == DIR_RIGHT_TO_LEFT ? Alignment.ALIGN_RIGHT : Alignment.ALIGN_LEFT;
                  break;
              case ALIGN_OPPOSITE:
                  resultAlign =
                          dir == DIR_RIGHT_TO_LEFT ? Alignment.ALIGN_LEFT : Alignment.ALIGN_RIGHT;
                  break;
              case ALIGN_CENTER:
                  resultAlign = Alignment.ALIGN_CENTER;
                  break;
              case ALIGN_RIGHT:
                  resultAlign = Alignment.ALIGN_RIGHT;
                  break;
              default: /* align == Alignment.ALIGN_LEFT */
                  resultAlign = Alignment.ALIGN_LEFT;
          }
  
          // Here we must use getLineMax() to do the computation, because it maybe overridden by
          // derived class. And also note that line max equals the width of the text in that line
          // plus the leading margin.
          switch (resultAlign) {
              case ALIGN_CENTER:
                  final int left = getParagraphLeft(line);
                  final float max = getLineMax(line);
                  // This computation only works when mWidth equals leadingMargin plus
                  // the width of text in this line. If this condition doesn't meet anymore,
                  // please change here too.
                  return (float) Math.floor(left + (mWidth - max) / 2);
              case ALIGN_RIGHT:
                  return mWidth - getLineMax(line);
              default: /* resultAlign == Alignment.ALIGN_LEFT */
                  return 0;
          }
      }
  
      /**
       * Get the rightmost position that should be exposed for horizontal
       * scrolling on the specified line.
       */
      public float getLineRight(int line) {
          final int dir = getParagraphDirection(line);
          Alignment align = getParagraphAlignment(line);
          // Before Q, StaticLayout.Builder.setAlignment didn't check whether the input alignment
          // is null. And when it is null, the old behavior is the same as ALIGN_CENTER.
          // To keep consistency, we convert a null alignment to ALIGN_CENTER.
          if (align == null) {
              align = Alignment.ALIGN_CENTER;
          }
  
          final Alignment resultAlign;
          switch(align) {
              case ALIGN_NORMAL:
                  resultAlign =
                          dir == DIR_RIGHT_TO_LEFT ? Alignment.ALIGN_RIGHT : Alignment.ALIGN_LEFT;
                  break;
              case ALIGN_OPPOSITE:
                  resultAlign =
                          dir == DIR_RIGHT_TO_LEFT ? Alignment.ALIGN_LEFT : Alignment.ALIGN_RIGHT;
                  break;
              case ALIGN_CENTER:
                  resultAlign = Alignment.ALIGN_CENTER;
                  break;
              case ALIGN_RIGHT:
                  resultAlign = Alignment.ALIGN_RIGHT;
                  break;
              default: /* align == Alignment.ALIGN_LEFT */
                  resultAlign = Alignment.ALIGN_LEFT;
          }
  
          switch (resultAlign) {
              case ALIGN_CENTER:
                  final int right = getParagraphRight(line);
                  final float max = getLineMax(line);
                  // This computation only works when mWidth equals leadingMargin plus width of the
                  // text in this line. If this condition doesn't meet anymore, please change here.
                  return (float) Math.ceil(right - (mWidth - max) / 2);
              case ALIGN_RIGHT:
                  return mWidth;
              default: /* resultAlign == Alignment.ALIGN_LEFT */
                  return getLineMax(line);
          }
      }
  
      /**
       * Gets the unsigned horizontal extent of the specified line, including
       * leading margin indent, but excluding trailing whitespace.
       */
      public float getLineMax(int line) {
          float margin = getParagraphLeadingMargin(line);
          float signedExtent = getLineExtent(line, false);
          return margin + (signedExtent >= 0 ? signedExtent : -signedExtent);
      }
  
      /**
       * Gets the unsigned horizontal extent of the specified line, including
       * leading margin indent and trailing whitespace.
       */
      public float getLineWidth(int line) {
          float margin = getParagraphLeadingMargin(line);
          float signedExtent = getLineExtent(line, true);
          return margin + (signedExtent >= 0 ? signedExtent : -signedExtent);
      }
  
      /**
       * Like {@link #getLineExtent(int,TabStops,boolean)} but determines the
       * tab stops instead of using the ones passed in.
       * @param line the index of the line
       * @param full whether to include trailing whitespace
       * @return the extent of the line
       */
      private float getLineExtent(int line, boolean full) {
          final int start = getLineStart(line);
          final int end = full ? getLineEnd(line) : getLineVisibleEnd(line);
  
          final boolean hasTabs = getLineContainsTab(line);
          TabStops tabStops = null;
          if (hasTabs && mText instanceof Spanned) {
              // Just checking this line should be good enough, tabs should be
              // consistent across all lines in a paragraph.
              TabStopSpan[] tabs = getParagraphSpans((Spanned) mText, start, end, TabStopSpan.class);
              if (tabs.length > 0) {
                  tabStops = new TabStops(TAB_INCREMENT, tabs); // XXX should reuse
              }
          }
          final Directions directions = getLineDirections(line);
          // Returned directions can actually be null
          if (directions == null) {
              return 0f;
          }
          final int dir = getParagraphDirection(line);
  
          final TextLine tl = TextLine.obtain();
          final TextPaint paint = mWorkPaint;
          paint.set(mPaint);
          paint.setStartHyphenEdit(getStartHyphenEdit(line));
          paint.setEndHyphenEdit(getEndHyphenEdit(line));
          tl.set(paint, mText, start, end, dir, directions, hasTabs, tabStops,
                  getEllipsisStart(line), getEllipsisStart(line) + getEllipsisCount(line));
          if (isJustificationRequired(line)) {
              tl.justify(getJustifyWidth(line));
          }
          final float width = tl.metrics(null);
          TextLine.recycle(tl);
          return width;
      }
  
      /**
       * Returns the signed horizontal extent of the specified line, excluding
       * leading margin.  If full is false, excludes trailing whitespace.
       * @param line the index of the line
       * @param tabStops the tab stops, can be null if we know they're not used.
       * @param full whether to include trailing whitespace
       * @return the extent of the text on this line
       */
      private float getLineExtent(int line, TabStops tabStops, boolean full) {
          final int start = getLineStart(line);
          final int end = full ? getLineEnd(line) : getLineVisibleEnd(line);
          final boolean hasTabs = getLineContainsTab(line);
          final Directions directions = getLineDirections(line);
          final int dir = getParagraphDirection(line);
  
          final TextLine tl = TextLine.obtain();
          final TextPaint paint = mWorkPaint;
          paint.set(mPaint);
          paint.setStartHyphenEdit(getStartHyphenEdit(line));
          paint.setEndHyphenEdit(getEndHyphenEdit(line));
          tl.set(paint, mText, start, end, dir, directions, hasTabs, tabStops,
                  getEllipsisStart(line), getEllipsisStart(line) + getEllipsisCount(line));
          if (isJustificationRequired(line)) {
              tl.justify(getJustifyWidth(line));
          }
          final float width = tl.metrics(null);
          TextLine.recycle(tl);
          return width;
      }
  
      /**
       * Get the line number corresponding to the specified vertical position.
       * If you ask for a position above 0, you get 0; if you ask for a position
       * below the bottom of the text, you get the last line.
       */
      // FIXME: It may be faster to do a linear search for layouts without many lines.
      public int getLineForVertical(int vertical) {
          int high = getLineCount(), low = -1, guess;
  
          while (high - low > 1) {
              guess = (high + low) / 2;
  
              if (getLineTop(guess) > vertical)
                  high = guess;
              else
                  low = guess;
          }
  
          if (low < 0)
              return 0;
          else
              return low;
      }
  
      /**
       * Get the line number on which the specified text offset appears.
       * If you ask for a position before 0, you get 0; if you ask for a position
       * beyond the end of the text, you get the last line.
       */
      public int getLineForOffset(int offset) {
          int high = getLineCount(), low = -1, guess;
  
          while (high - low > 1) {
              guess = (high + low) / 2;
  
              if (getLineStart(guess) > offset)
                  high = guess;
              else
                  low = guess;
          }
  
          if (low < 0) {
              return 0;
          } else {
              return low;
          }
      }
  
      /**
       * Get the character offset on the specified line whose position is
       * closest to the specified horizontal position.
       */
      public int getOffsetForHorizontal(int line, float horiz) {
          return getOffsetForHorizontal(line, horiz, true);
      }
  
      /**
       * Get the character offset on the specified line whose position is
       * closest to the specified horizontal position.
       *
       * @param line the line used to find the closest offset
       * @param horiz the horizontal position used to find the closest offset
       * @param primary whether to use the primary position or secondary position to find the offset
       *
       * @hide
       */
      public int getOffsetForHorizontal(int line, float horiz, boolean primary) {
          // TODO: use Paint.getOffsetForAdvance to avoid binary search
          final int lineEndOffset = getLineEnd(line);
          final int lineStartOffset = getLineStart(line);
  
          Directions dirs = getLineDirections(line);
  
          TextLine tl = TextLine.obtain();
          // XXX: we don't care about tabs as we just use TextLine#getOffsetToLeftRightOf here.
          tl.set(mPaint, mText, lineStartOffset, lineEndOffset, getParagraphDirection(line), dirs,
                  false, null,
                  getEllipsisStart(line), getEllipsisStart(line) + getEllipsisCount(line));
          final HorizontalMeasurementProvider horizontal =
                  new HorizontalMeasurementProvider(line, primary);
  
          final int max;
          if (line == getLineCount() - 1) {
              max = lineEndOffset;
          } else {
              max = tl.getOffsetToLeftRightOf(lineEndOffset - lineStartOffset,
                      !isRtlCharAt(lineEndOffset - 1)) + lineStartOffset;
          }
          int best = lineStartOffset;
          float bestdist = Math.abs(horizontal.get(lineStartOffset) - horiz);
  
          for (int i = 0; i < dirs.mDirections.length; i += 2) {
              int here = lineStartOffset + dirs.mDirections[i];
              int there = here + (dirs.mDirections[i+1] & RUN_LENGTH_MASK);
              boolean isRtl = (dirs.mDirections[i+1] & RUN_RTL_FLAG) != 0;
              int swap = isRtl ? -1 : 1;
  
              if (there > max)
                  there = max;
              int high = there - 1 + 1, low = here + 1 - 1, guess;
  
              while (high - low > 1) {
                  guess = (high + low) / 2;
                  int adguess = getOffsetAtStartOf(guess);
  
                  if (horizontal.get(adguess) * swap >= horiz * swap) {
                      high = guess;
                  } else {
                      low = guess;
                  }
              }
  
              if (low < here + 1)
                  low = here + 1;
  
              if (low < there) {
                  int aft = tl.getOffsetToLeftRightOf(low - lineStartOffset, isRtl) + lineStartOffset;
                  low = tl.getOffsetToLeftRightOf(aft - lineStartOffset, !isRtl) + lineStartOffset;
                  if (low >= here && low < there) {
                      float dist = Math.abs(horizontal.get(low) - horiz);
                      if (aft < there) {
                          float other = Math.abs(horizontal.get(aft) - horiz);
  
                          if (other < dist) {
                              dist = other;
                              low = aft;
                          }
                      }
  
                      if (dist < bestdist) {
                          bestdist = dist;
                          best = low;
                      }
                  }
              }
  
              float dist = Math.abs(horizontal.get(here) - horiz);
  
              if (dist < bestdist) {
                  bestdist = dist;
                  best = here;
              }
          }
  
          float dist = Math.abs(horizontal.get(max) - horiz);
  
          if (dist <= bestdist) {
              best = max;
          }
  
          TextLine.recycle(tl);
          return best;
      }
  
      /**
       * Responds to #getHorizontal queries, by selecting the better strategy between:
       * - calling #getHorizontal explicitly for each query
       * - precomputing all #getHorizontal measurements, and responding to any query in constant time
       * The first strategy is used for LTR-only text, while the second is used for all other cases.
       * The class is currently only used in #getOffsetForHorizontal, so reuse with care in other
       * contexts.
       */
      private class HorizontalMeasurementProvider {
          private final int mLine;
          private final boolean mPrimary;
  
          private float[] mHorizontals;
          private int mLineStartOffset;
  
          HorizontalMeasurementProvider(final int line, final boolean primary) {
              mLine = line;
              mPrimary = primary;
              init();
          }
  
          private void init() {
              final Directions dirs = getLineDirections(mLine);
              if (dirs == DIRS_ALL_LEFT_TO_RIGHT) {
                  return;
              }
  
              mHorizontals = getLineHorizontals(mLine, false, mPrimary);
              mLineStartOffset = getLineStart(mLine);
          }
  
          float get(final int offset) {
              final int index = offset - mLineStartOffset;
              if (mHorizontals == null || index < 0 || index >= mHorizontals.length) {
                  return getHorizontal(offset, mPrimary);
              } else {
                  return mHorizontals[index];
              }
          }
      }
  
      /**
       * Return the text offset after the last character on the specified line.
       */
      public final int getLineEnd(int line) {
          return getLineStart(line + 1);
      }
  
      /**
       * Return the text offset after the last visible character (so whitespace
       * is not counted) on the specified line.
       */
      public int getLineVisibleEnd(int line) {
          return getLineVisibleEnd(line, getLineStart(line), getLineStart(line+1));
      }
  
      private int getLineVisibleEnd(int line, int start, int end) {
          CharSequence text = mText;
          char ch;
          if (line == getLineCount() - 1) {
              return end;
          }
  
          for (; end > start; end--) {
              ch = text.charAt(end - 1);
  
              if (ch == '\n') {
                  return end - 1;
              }
  
              if (!TextLine.isLineEndSpace(ch)) {
                  break;
              }
  
          }
  
          return end;
      }
  
      /**
       * Return the vertical position of the bottom of the specified line.
       */
      public final int getLineBottom(int line) {
          return getLineTop(line + 1);
      }
  
      /**
       * Return the vertical position of the bottom of the specified line without the line spacing
       * added.
       *
       * @hide
       */
      public final int getLineBottomWithoutSpacing(int line) {
          return getLineTop(line + 1) - getLineExtra(line);
      }
  
      /**
       * Return the vertical position of the baseline of the specified line.
       */
      public final int getLineBaseline(int line) {
          // getLineTop(line+1) == getLineBottom(line)
          return getLineTop(line+1) - getLineDescent(line);
      }
  
      /**
       * Get the ascent of the text on the specified line.
       * The return value is negative to match the Paint.ascent() convention.
       */
      public final int getLineAscent(int line) {
          // getLineTop(line+1) - getLineDescent(line) == getLineBaseLine(line)
          return getLineTop(line) - (getLineTop(line+1) - getLineDescent(line));
      }
  
      /**
       * Return the extra space added as a result of line spacing attributes
       * {@link #getSpacingAdd()} and {@link #getSpacingMultiplier()}. Default value is {@code zero}.
       *
       * @param line the index of the line, the value should be equal or greater than {@code zero}
       * @hide
       */
      public int getLineExtra(@IntRange(from = 0) int line) {
          return 0;
      }
  
      public int getOffsetToLeftOf(int offset) {
          return getOffsetToLeftRightOf(offset, true);
      }
  
      public int getOffsetToRightOf(int offset) {
          return getOffsetToLeftRightOf(offset, false);
      }
  
      private int getOffsetToLeftRightOf(int caret, boolean toLeft) {
          int line = getLineForOffset(caret);
          int lineStart = getLineStart(line);
          int lineEnd = getLineEnd(line);
          int lineDir = getParagraphDirection(line);
  
          boolean lineChanged = false;
          boolean advance = toLeft == (lineDir == DIR_RIGHT_TO_LEFT);
          // if walking off line, look at the line we're headed to
          if (advance) {
              if (caret == lineEnd) {
                  if (line < getLineCount() - 1) {
                      lineChanged = true;
                      ++line;
                  } else {
                      return caret; // at very end, don't move
                  }
              }
          } else {
              if (caret == lineStart) {
                  if (line > 0) {
                      lineChanged = true;
                      --line;
                  } else {
                      return caret; // at very start, don't move
                  }
              }
          }
  
          if (lineChanged) {
              lineStart = getLineStart(line);
              lineEnd = getLineEnd(line);
              int newDir = getParagraphDirection(line);
              if (newDir != lineDir) {
                  // unusual case.  we want to walk onto the line, but it runs
                  // in a different direction than this one, so we fake movement
                  // in the opposite direction.
                  toLeft = !toLeft;
                  lineDir = newDir;
              }
          }
  
          Directions directions = getLineDirections(line);
  
          TextLine tl = TextLine.obtain();
          // XXX: we don't care about tabs
          tl.set(mPaint, mText, lineStart, lineEnd, lineDir, directions, false, null,
                  getEllipsisStart(line), getEllipsisStart(line) + getEllipsisCount(line));
          caret = lineStart + tl.getOffsetToLeftRightOf(caret - lineStart, toLeft);
          TextLine.recycle(tl);
          return caret;
      }
  
      private int getOffsetAtStartOf(int offset) {
          // XXX this probably should skip local reorderings and
          // zero-width characters, look at callers
          if (offset == 0)
              return 0;
  
          CharSequence text = mText;
          char c = text.charAt(offset);
  
          if (c >= '\uDC00' && c <= '\uDFFF') {
              char c1 = text.charAt(offset - 1);
  
              if (c1 >= '\uD800' && c1 <= '\uDBFF')
                  offset -= 1;
          }
  
          if (mSpannedText) {
              ReplacementSpan[] spans = ((Spanned) text).getSpans(offset, offset,
                                                         ReplacementSpan.class);
  
              for (int i = 0; i < spans.length; i++) {
                  int start = ((Spanned) text).getSpanStart(spans[i]);
                  int end = ((Spanned) text).getSpanEnd(spans[i]);
  
                  if (start < offset && end > offset)
                      offset = start;
              }
          }
  
          return offset;
      }
  
      /**
       * Determine whether we should clamp cursor position. Currently it's
       * only robust for left-aligned displays.
       * @hide
       */
      @UnsupportedAppUsage
      public boolean shouldClampCursor(int line) {
          // Only clamp cursor position in left-aligned displays.
          switch (getParagraphAlignment(line)) {
              case ALIGN_LEFT:
                  return true;
              case ALIGN_NORMAL:
                  return getParagraphDirection(line) > 0;
              default:
                  return false;
          }
  
      }
  
      /**
       * Fills in the specified Path with a representation of a cursor
       * at the specified offset.  This will often be a vertical line
       * but can be multiple discontinuous lines in text with multiple
       * directionalities.
       */
      public void getCursorPath(final int point, final Path dest, final CharSequence editingBuffer) {
          dest.reset();
  
          int line = getLineForOffset(point);
          int top = getLineTop(line);
          int bottom = getLineBottomWithoutSpacing(line);
  
          boolean clamped = shouldClampCursor(line);
          float h1 = getPrimaryHorizontal(point, clamped) - 0.5f;
  
          int caps = TextKeyListener.getMetaState(editingBuffer, TextKeyListener.META_SHIFT_ON) |
                     TextKeyListener.getMetaState(editingBuffer, TextKeyListener.META_SELECTING);
          int fn = TextKeyListener.getMetaState(editingBuffer, TextKeyListener.META_ALT_ON);
          int dist = 0;
  
          if (caps != 0 || fn != 0) {
              dist = (bottom - top) >> 2;
  
              if (fn != 0)
                  top += dist;
              if (caps != 0)
                  bottom -= dist;
          }
  
          if (h1 < 0.5f)
              h1 = 0.5f;
  
          dest.moveTo(h1, top);
          dest.lineTo(h1, bottom);
  
          if (caps == 2) {
              dest.moveTo(h1, bottom);
              dest.lineTo(h1 - dist, bottom + dist);
              dest.lineTo(h1, bottom);
              dest.lineTo(h1 + dist, bottom + dist);
          } else if (caps == 1) {
              dest.moveTo(h1, bottom);
              dest.lineTo(h1 - dist, bottom + dist);
  
              dest.moveTo(h1 - dist, bottom + dist - 0.5f);
              dest.lineTo(h1 + dist, bottom + dist - 0.5f);
  
              dest.moveTo(h1 + dist, bottom + dist);
              dest.lineTo(h1, bottom);
          }
  
          if (fn == 2) {
              dest.moveTo(h1, top);
              dest.lineTo(h1 - dist, top - dist);
              dest.lineTo(h1, top);
              dest.lineTo(h1 + dist, top - dist);
          } else if (fn == 1) {
              dest.moveTo(h1, top);
              dest.lineTo(h1 - dist, top - dist);
  
              dest.moveTo(h1 - dist, top - dist + 0.5f);
              dest.lineTo(h1 + dist, top - dist + 0.5f);
  
              dest.moveTo(h1 + dist, top - dist);
              dest.lineTo(h1, top);
          }
      }
  
      private void addSelection(int line, int start, int end,
              int top, int bottom, SelectionRectangleConsumer consumer) {
          int linestart = getLineStart(line);
          int lineend = getLineEnd(line);
          Directions dirs = getLineDirections(line);
  
          if (lineend > linestart && mText.charAt(lineend - 1) == '\n') {
              lineend--;
          }
  
          for (int i = 0; i < dirs.mDirections.length; i += 2) {
              int here = linestart + dirs.mDirections[i];
              int there = here + (dirs.mDirections[i + 1] & RUN_LENGTH_MASK);
  
              if (there > lineend) {
                  there = lineend;
              }
  
              if (start <= there && end >= here) {
                  int st = Math.max(start, here);
                  int en = Math.min(end, there);
  
                  if (st != en) {
                      float h1 = getHorizontal(st, false, line, false /* not clamped */);
                      float h2 = getHorizontal(en, true, line, false /* not clamped */);
  
                      float left = Math.min(h1, h2);
                      float right = Math.max(h1, h2);
  
                      final @TextSelectionLayout int layout =
                              ((dirs.mDirections[i + 1] & RUN_RTL_FLAG) != 0)
                                      ? TEXT_SELECTION_LAYOUT_RIGHT_TO_LEFT
                                      : TEXT_SELECTION_LAYOUT_LEFT_TO_RIGHT;
  
                      consumer.accept(left, top, right, bottom, layout);
                  }
              }
          }
      }
  
      /**
       * Fills in the specified Path with a representation of a highlight
       * between the specified offsets.  This will often be a rectangle
       * or a potentially discontinuous set of rectangles.  If the start
       * and end are the same, the returned path is empty.
       */
      public void getSelectionPath(int start, int end, Path dest) {
          dest.reset();
          getSelection(start, end, (left, top, right, bottom, textSelectionLayout) ->
                  dest.addRect(left, top, right, bottom, Path.Direction.CW));
      }
  
      /**
       * Calculates the rectangles which should be highlighted to indicate a selection between start
       * and end and feeds them into the given {@link SelectionRectangleConsumer}.
       *
       * @param start    the starting index of the selection
       * @param end      the ending index of the selection
       * @param consumer the {@link SelectionRectangleConsumer} which will receive the generated
       *                 rectangles. It will be called every time a rectangle is generated.
       * @hide
       * @see #getSelectionPath(int, int, Path)
       */
      public final void getSelection(int start, int end, final SelectionRectangleConsumer consumer) {
          if (start == end) {
              return;
          }
  
          if (end < start) {
              int temp = end;
              end = start;
              start = temp;
          }
  
          final int startline = getLineForOffset(start);
          final int endline = getLineForOffset(end);
  
          int top = getLineTop(startline);
          int bottom = getLineBottomWithoutSpacing(endline);
  
          if (startline == endline) {
              addSelection(startline, start, end, top, bottom, consumer);
          } else {
              final float width = mWidth;
  
              addSelection(startline, start, getLineEnd(startline),
                      top, getLineBottom(startline), consumer);
  
              if (getParagraphDirection(startline) == DIR_RIGHT_TO_LEFT) {
                  consumer.accept(getLineLeft(startline), top, 0, getLineBottom(startline),
                          TEXT_SELECTION_LAYOUT_RIGHT_TO_LEFT);
              } else {
                  consumer.accept(getLineRight(startline), top, width, getLineBottom(startline),
                          TEXT_SELECTION_LAYOUT_LEFT_TO_RIGHT);
              }
  
              for (int i = startline + 1; i < endline; i++) {
                  top = getLineTop(i);
                  bottom = getLineBottom(i);
                  if (getParagraphDirection(i) == DIR_RIGHT_TO_LEFT) {
                      consumer.accept(0, top, width, bottom, TEXT_SELECTION_LAYOUT_RIGHT_TO_LEFT);
                  } else {
                      consumer.accept(0, top, width, bottom, TEXT_SELECTION_LAYOUT_LEFT_TO_RIGHT);
                  }
              }
  
              top = getLineTop(endline);
              bottom = getLineBottomWithoutSpacing(endline);
  
              addSelection(endline, getLineStart(endline), end, top, bottom, consumer);
  
              if (getParagraphDirection(endline) == DIR_RIGHT_TO_LEFT) {
                  consumer.accept(width, top, getLineRight(endline), bottom,
                          TEXT_SELECTION_LAYOUT_RIGHT_TO_LEFT);
              } else {
                  consumer.accept(0, top, getLineLeft(endline), bottom,
                          TEXT_SELECTION_LAYOUT_LEFT_TO_RIGHT);
              }
          }
      }
  
      /**
       * Get the alignment of the specified paragraph, taking into account
       * markup attached to it.
       */
      public final Alignment getParagraphAlignment(int line) {
          Alignment align = mAlignment;
  
          if (mSpannedText) {
              Spanned sp = (Spanned) mText;
              AlignmentSpan[] spans = getParagraphSpans(sp, getLineStart(line),
                                                  getLineEnd(line),
                                                  AlignmentSpan.class);
  
              int spanLength = spans.length;
              if (spanLength > 0) {
                  align = spans[spanLength-1].getAlignment();
              }
          }
  
          return align;
      }
  
      /**
       * Get the left edge of the specified paragraph, inset by left margins.
       */
      public final int getParagraphLeft(int line) {
          int left = 0;
          int dir = getParagraphDirection(line);
          if (dir == DIR_RIGHT_TO_LEFT || !mSpannedText) {
              return left; // leading margin has no impact, or no styles
          }
          return getParagraphLeadingMargin(line);
      }
  
      /**
       * Get the right edge of the specified paragraph, inset by right margins.
       */
      public final int getParagraphRight(int line) {
          int right = mWidth;
          int dir = getParagraphDirection(line);
          if (dir == DIR_LEFT_TO_RIGHT || !mSpannedText) {
              return right; // leading margin has no impact, or no styles
          }
          return right - getParagraphLeadingMargin(line);
      }
  
      /**
       * Returns the effective leading margin (unsigned) for this line,
       * taking into account LeadingMarginSpan and LeadingMarginSpan2.
       * @param line the line index
       * @return the leading margin of this line
       */
      private int getParagraphLeadingMargin(int line) {
          if (!mSpannedText) {
              return 0;
          }
          Spanned spanned = (Spanned) mText;
  
          int lineStart = getLineStart(line);
          int lineEnd = getLineEnd(line);
          int spanEnd = spanned.nextSpanTransition(lineStart, lineEnd,
                  LeadingMarginSpan.class);
          LeadingMarginSpan[] spans = getParagraphSpans(spanned, lineStart, spanEnd,
                                                  LeadingMarginSpan.class);
          if (spans.length == 0) {
              return 0; // no leading margin span;
          }
  
          int margin = 0;
  
          boolean useFirstLineMargin = lineStart == 0 || spanned.charAt(lineStart - 1) == '\n';
          for (int i = 0; i < spans.length; i++) {
              if (spans[i] instanceof LeadingMarginSpan2) {
                  int spStart = spanned.getSpanStart(spans[i]);
                  int spanLine = getLineForOffset(spStart);
                  int count = ((LeadingMarginSpan2) spans[i]).getLeadingMarginLineCount();
                  // if there is more than one LeadingMarginSpan2, use the count that is greatest
                  useFirstLineMargin |= line < spanLine + count;
              }
          }
          for (int i = 0; i < spans.length; i++) {
              LeadingMarginSpan span = spans[i];
              margin += span.getLeadingMargin(useFirstLineMargin);
          }
  
          return margin;
      }
  
      private static float measurePara(TextPaint paint, CharSequence text, int start, int end,
              TextDirectionHeuristic textDir) {
          MeasuredParagraph mt = null;
          TextLine tl = TextLine.obtain();
          try {
              mt = MeasuredParagraph.buildForBidi(text, start, end, textDir, mt);
              final char[] chars = mt.getChars();
              final int len = chars.length;
              final Directions directions = mt.getDirections(0, len);
              final int dir = mt.getParagraphDir();
              boolean hasTabs = false;
              TabStops tabStops = null;
              // leading margins should be taken into account when measuring a paragraph
              int margin = 0;
              if (text instanceof Spanned) {
                  Spanned spanned = (Spanned) text;
                  LeadingMarginSpan[] spans = getParagraphSpans(spanned, start, end,
                          LeadingMarginSpan.class);
                  for (LeadingMarginSpan lms : spans) {
                      margin += lms.getLeadingMargin(true);
                  }
              }
              for (int i = 0; i < len; ++i) {
                  if (chars[i] == '\t') {
                      hasTabs = true;
                      if (text instanceof Spanned) {
                          Spanned spanned = (Spanned) text;
                          int spanEnd = spanned.nextSpanTransition(start, end,
                                  TabStopSpan.class);
                          TabStopSpan[] spans = getParagraphSpans(spanned, start, spanEnd,
                                  TabStopSpan.class);
                          if (spans.length > 0) {
                              tabStops = new TabStops(TAB_INCREMENT, spans);
                          }
                      }
                      break;
                  }
              }
              tl.set(paint, text, start, end, dir, directions, hasTabs, tabStops,
                      0 /* ellipsisStart */, 0 /* ellipsisEnd */);
              return margin + Math.abs(tl.metrics(null));
          } finally {
              TextLine.recycle(tl);
              if (mt != null) {
                  mt.recycle();
              }
          }
      }
  
      /**
       * @hide
       */
      @VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE)
      public static class TabStops {
          private float[] mStops;
          private int mNumStops;
          private float mIncrement;
  
          public TabStops(float increment, Object[] spans) {
              reset(increment, spans);
          }
  
          void reset(float increment, Object[] spans) {
              this.mIncrement = increment;
  
              int ns = 0;
              if (spans != null) {
                  float[] stops = this.mStops;
                  for (Object o : spans) {
                      if (o instanceof TabStopSpan) {
                          if (stops == null) {
                              stops = new float[10];
                          } else if (ns == stops.length) {
                              float[] nstops = new float[ns * 2];
                              for (int i = 0; i < ns; ++i) {
                                  nstops[i] = stops[i];
                              }
                              stops = nstops;
                          }
                          stops[ns++] = ((TabStopSpan) o).getTabStop();
                      }
                  }
                  if (ns > 1) {
                      Arrays.sort(stops, 0, ns);
                  }
                  if (stops != this.mStops) {
                      this.mStops = stops;
                  }
              }
              this.mNumStops = ns;
          }
  
          float nextTab(float h) {
              int ns = this.mNumStops;
              if (ns > 0) {
                  float[] stops = this.mStops;
                  for (int i = 0; i < ns; ++i) {
                      float stop = stops[i];
                      if (stop > h) {
                          return stop;
                      }
                  }
              }
              return nextDefaultStop(h, mIncrement);
          }
  
          /**
           * Returns the position of next tab stop.
           */
          public static float nextDefaultStop(float h, float inc) {
              return ((int) ((h + inc) / inc)) * inc;
          }
      }
  
      /**
       * Returns the position of the next tab stop after h on the line.
       *
       * @param text the text
       * @param start start of the line
       * @param end limit of the line
       * @param h the current horizontal offset
       * @param tabs the tabs, can be null.  If it is null, any tabs in effect
       * on the line will be used.  If there are no tabs, a default offset
       * will be used to compute the tab stop.
       * @return the offset of the next tab stop.
       */
      /* package */ static float nextTab(CharSequence text, int start, int end,
                                         float h, Object[] tabs) {
          float nh = Float.MAX_VALUE;
          boolean alltabs = false;
  
          if (text instanceof Spanned) {
              if (tabs == null) {
                  tabs = getParagraphSpans((Spanned) text, start, end, TabStopSpan.class);
                  alltabs = true;
              }
  
              for (int i = 0; i < tabs.length; i++) {
                  if (!alltabs) {
                      if (!(tabs[i] instanceof TabStopSpan))
                          continue;
                  }
  
                  int where = ((TabStopSpan) tabs[i]).getTabStop();
  
                  if (where < nh && where > h)
                      nh = where;
              }
  
              if (nh != Float.MAX_VALUE)
                  return nh;
          }
  
          return ((int) ((h + TAB_INCREMENT) / TAB_INCREMENT)) * TAB_INCREMENT;
      }
  
      protected final boolean isSpanned() {
          return mSpannedText;
      }
  
      /**
       * Returns the same as <code>text.getSpans()</code>, except where
       * <code>start</code> and <code>end</code> are the same and are not
       * at the very beginning of the text, in which case an empty array
       * is returned instead.
       * <p>
       * This is needed because of the special case that <code>getSpans()</code>
       * on an empty range returns the spans adjacent to that range, which is
       * primarily for the sake of <code>TextWatchers</code> so they will get
       * notifications when text goes from empty to non-empty.  But it also
       * has the unfortunate side effect that if the text ends with an empty
       * paragraph, that paragraph accidentally picks up the styles of the
       * preceding paragraph (even though those styles will not be picked up
       * by new text that is inserted into the empty paragraph).
       * <p>
       * The reason it just checks whether <code>start</code> and <code>end</code>
       * is the same is that the only time a line can contain 0 characters
       * is if it is the final paragraph of the Layout; otherwise any line will
       * contain at least one printing or newline character.  The reason for the
       * additional check if <code>start</code> is greater than 0 is that
       * if the empty paragraph is the entire content of the buffer, paragraph
       * styles that are already applied to the buffer will apply to text that
       * is inserted into it.
       */
      /* package */static <T> T[] getParagraphSpans(Spanned text, int start, int end, Class<T> type) {
          if (start == end && start > 0) {
              return ArrayUtils.emptyArray(type);
          }
  
          if(text instanceof SpannableStringBuilder) {
              return ((SpannableStringBuilder) text).getSpans(start, end, type, false);
          } else {
              return text.getSpans(start, end, type);
          }
      }
  
      private void ellipsize(int start, int end, int line,
                             char[] dest, int destoff, TextUtils.TruncateAt method) {
          final int ellipsisCount = getEllipsisCount(line);
          if (ellipsisCount == 0) {
              return;
          }
          final int ellipsisStart = getEllipsisStart(line);
          final int lineStart = getLineStart(line);
  
          final String ellipsisString = TextUtils.getEllipsisString(method);
          final int ellipsisStringLen = ellipsisString.length();
          // Use the ellipsis string only if there are that at least as many characters to replace.
          final boolean useEllipsisString = ellipsisCount >= ellipsisStringLen;
          for (int i = 0; i < ellipsisCount; i++) {
              final char c;
              if (useEllipsisString && i < ellipsisStringLen) {
                  c = ellipsisString.charAt(i);
              } else {
                  c = TextUtils.ELLIPSIS_FILLER;
              }
  
              final int a = i + ellipsisStart + lineStart;
              if (start <= a && a < end) {
                  dest[destoff + a - start] = c;
              }
          }
      }
  
      /**
       * Stores information about bidirectional (left-to-right or right-to-left)
       * text within the layout of a line.
       */
      public static class Directions {
          /**
           * Directions represents directional runs within a line of text. Runs are pairs of ints
           * listed in visual order, starting from the leading margin.  The first int of each pair is
           * the offset from the first character of the line to the start of the run.  The second int
           * represents both the length and level of the run. The length is in the lower bits,
           * accessed by masking with RUN_LENGTH_MASK.  The level is in the higher bits, accessed by
           * shifting by RUN_LEVEL_SHIFT and masking by RUN_LEVEL_MASK. To simply test for an RTL
           * direction, test the bit using RUN_RTL_FLAG, if set then the direction is rtl.
           * @hide
           */
          @VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE)
          public int[] mDirections;
  
          /**
           * @hide
           */
          @VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE)
          public Directions(int[] dirs) {
              mDirections = dirs;
          }
  
          /**
           * Returns number of BiDi runs.
           *
           * @hide
           */
          public @IntRange(from = 0) int getRunCount() {
              return mDirections.length / 2;
          }
  
          /**
           * Returns the start offset of the BiDi run.
           *
           * @param runIndex the index of the BiDi run
           * @return the start offset of the BiDi run.
           * @hide
           */
          public @IntRange(from = 0) int getRunStart(@IntRange(from = 0) int runIndex) {
              return mDirections[runIndex * 2];
          }
  
          /**
           * Returns the length of the BiDi run.
           *
           * Note that this method may return too large number due to reducing the number of object
           * allocations. The too large number means the remaining part is assigned to this run. The
           * caller must clamp the returned value.
           *
           * @param runIndex the index of the BiDi run
           * @return the length of the BiDi run.
           * @hide
           */
          public @IntRange(from = 0) int getRunLength(@IntRange(from = 0) int runIndex) {
              return mDirections[runIndex * 2 + 1] & RUN_LENGTH_MASK;
          }
  
          /**
           * Returns true if the BiDi run is RTL.
           *
           * @param runIndex the index of the BiDi run
           * @return true if the BiDi run is RTL.
           * @hide
           */
          public boolean isRunRtl(int runIndex) {
              return (mDirections[runIndex * 2 + 1] & RUN_RTL_FLAG) != 0;
          }
      }
  
      /**
       * Return the offset of the first character to be ellipsized away,
       * relative to the start of the line.  (So 0 if the beginning of the
       * line is ellipsized, not getLineStart().)
       */
      public abstract int getEllipsisStart(int line);
  
      /**
       * Returns the number of characters to be ellipsized away, or 0 if
       * no ellipsis is to take place.
       */
      public abstract int getEllipsisCount(int line);
  
      /* package */ static class Ellipsizer implements CharSequence, GetChars {
          /* package */ CharSequence mText;
          /* package */ Layout mLayout;
          /* package */ int mWidth;
          /* package */ TextUtils.TruncateAt mMethod;
  
          public Ellipsizer(CharSequence s) {
              mText = s;
          }
  
          public char charAt(int off) {
              char[] buf = TextUtils.obtain(1);
              getChars(off, off + 1, buf, 0);
              char ret = buf[0];
  
              TextUtils.recycle(buf);
              return ret;
          }
  
          public void getChars(int start, int end, char[] dest, int destoff) {
              int line1 = mLayout.getLineForOffset(start);
              int line2 = mLayout.getLineForOffset(end);
  
              TextUtils.getChars(mText, start, end, dest, destoff);
  
              for (int i = line1; i <= line2; i++) {
                  mLayout.ellipsize(start, end, i, dest, destoff, mMethod);
              }
          }
  
          public int length() {
              return mText.length();
          }
  
          public CharSequence subSequence(int start, int end) {
              char[] s = new char[end - start];
              getChars(start, end, s, 0);
              return new String(s);
          }
  
          @Override
          public String toString() {
              char[] s = new char[length()];
              getChars(0, length(), s, 0);
              return new String(s);
          }
  
      }
  
      /* package */ static class SpannedEllipsizer extends Ellipsizer implements Spanned {
          private Spanned mSpanned;
  
          public SpannedEllipsizer(CharSequence display) {
              super(display);
              mSpanned = (Spanned) display;
          }
  
          public <T> T[] getSpans(int start, int end, Class<T> type) {
              return mSpanned.getSpans(start, end, type);
          }
  
          public int getSpanStart(Object tag) {
              return mSpanned.getSpanStart(tag);
          }
  
          public int getSpanEnd(Object tag) {
              return mSpanned.getSpanEnd(tag);
          }
  
          public int getSpanFlags(Object tag) {
              return mSpanned.getSpanFlags(tag);
          }
  
          @SuppressWarnings("rawtypes")
          public int nextSpanTransition(int start, int limit, Class type) {
              return mSpanned.nextSpanTransition(start, limit, type);
          }
  
          @Override
          public CharSequence subSequence(int start, int end) {
              char[] s = new char[end - start];
              getChars(start, end, s, 0);
  
              SpannableString ss = new SpannableString(new String(s));
              TextUtils.copySpansFrom(mSpanned, start, end, Object.class, ss, 0);
              return ss;
          }
      }
  
      private CharSequence mText;
      @UnsupportedAppUsage
      private TextPaint mPaint;
      private TextPaint mWorkPaint = new TextPaint();
      private int mWidth;
      private Alignment mAlignment = Alignment.ALIGN_NORMAL;
      private float mSpacingMult;
      private float mSpacingAdd;
      private static final Rect sTempRect = new Rect();
      private boolean mSpannedText;
      private TextDirectionHeuristic mTextDir;
      private SpanSet<LineBackgroundSpan> mLineBackgroundSpans;
      private int mJustificationMode;
  
      /** @hide */
      @IntDef(prefix = { "DIR_" }, value = {
              DIR_LEFT_TO_RIGHT,
              DIR_RIGHT_TO_LEFT
      })
      @Retention(RetentionPolicy.SOURCE)
      public @interface Direction {}
  
      public static final int DIR_LEFT_TO_RIGHT = 1;
      public static final int DIR_RIGHT_TO_LEFT = -1;
  
      /* package */ static final int DIR_REQUEST_LTR = 1;
      /* package */ static final int DIR_REQUEST_RTL = -1;
      @UnsupportedAppUsage
      /* package */ static final int DIR_REQUEST_DEFAULT_LTR = 2;
      /* package */ static final int DIR_REQUEST_DEFAULT_RTL = -2;
  
      /* package */ static final int RUN_LENGTH_MASK = 0x03ffffff;
      /* package */ static final int RUN_LEVEL_SHIFT = 26;
      /* package */ static final int RUN_LEVEL_MASK = 0x3f;
      /* package */ static final int RUN_RTL_FLAG = 1 << RUN_LEVEL_SHIFT;
  
      public enum Alignment {
          ALIGN_NORMAL,
          ALIGN_OPPOSITE,
          ALIGN_CENTER,
          /** @hide */
          @UnsupportedAppUsage
          ALIGN_LEFT,
          /** @hide */
          @UnsupportedAppUsage
          ALIGN_RIGHT,
      }
  
      private static final float TAB_INCREMENT = 20;
  
      /** @hide */
      @VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE)
      @UnsupportedAppUsage
      public static final Directions DIRS_ALL_LEFT_TO_RIGHT =
          new Directions(new int[] { 0, RUN_LENGTH_MASK });
  
      /** @hide */
      @VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE)
      @UnsupportedAppUsage
      public static final Directions DIRS_ALL_RIGHT_TO_LEFT =
          new Directions(new int[] { 0, RUN_LENGTH_MASK | RUN_RTL_FLAG });
  
      /** @hide */
      @Retention(RetentionPolicy.SOURCE)
      @IntDef(prefix = { "TEXT_SELECTION_LAYOUT_" }, value = {
              TEXT_SELECTION_LAYOUT_RIGHT_TO_LEFT,
              TEXT_SELECTION_LAYOUT_LEFT_TO_RIGHT
      })
      public @interface TextSelectionLayout {}
  
      /** @hide */
      public static final int TEXT_SELECTION_LAYOUT_RIGHT_TO_LEFT = 0;
      /** @hide */
      public static final int TEXT_SELECTION_LAYOUT_LEFT_TO_RIGHT = 1;
  
      /** @hide */
      @FunctionalInterface
      public interface SelectionRectangleConsumer {
          /**
           * Performs this operation on the given rectangle.
           *
           * @param left   the left edge of the rectangle
           * @param top    the top edge of the rectangle
           * @param right  the right edge of the rectangle
           * @param bottom the bottom edge of the rectangle
           * @param textSelectionLayout the layout (RTL or LTR) of the text covered by this
           *                            selection rectangle
           */
          void accept(float left, float top, float right, float bottom,
                  @TextSelectionLayout int textSelectionLayout);
      }
  
  }
  