core/java/android/text/Layout.java

   1 /*
   2  * Copyright (C) 2006 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 package android.text;
  18
  19 import android.annotation.IntDef;
  20 import android.graphics.Canvas;
  21 import android.graphics.Paint;
  22 import android.graphics.Path;
  23 import android.graphics.Rect;
  24 import android.text.method.TextKeyListener;
  25 import android.text.style.AlignmentSpan;
  26 import android.text.style.LeadingMarginSpan;
  27 import android.text.style.LeadingMarginSpan.LeadingMarginSpan2;
  28 import android.text.style.LineBackgroundSpan;
  29 import android.text.style.ParagraphStyle;
  30 import android.text.style.ReplacementSpan;
  31 import android.text.style.TabStopSpan;
  32
  33 import com.android.internal.annotations.VisibleForTesting;
  34 import com.android.internal.util.ArrayUtils;
  35 import com.android.internal.util.GrowingArrayUtils;
  36
  37 import java.lang.annotation.Retention;
  38 import java.lang.annotation.RetentionPolicy;
  39 import java.util.Arrays;
  40
  41 /**
  42  * A base class that manages text layout in visual elements on
  43  * the screen.
  44  * <p>For text that will be edited, use a {@link DynamicLayout},
  45  * which will be updated as the text changes.
  46  * For text that will not change, use a {@link StaticLayout}.
  47  */
  48 public abstract class Layout {
  49     /** @hide */
  50     @IntDef({BREAK_STRATEGY_SIMPLE, BREAK_STRATEGY_HIGH_QUALITY, BREAK_STRATEGY_BALANCED})
  51     @Retention(RetentionPolicy.SOURCE)
  52     public @interface BreakStrategy {}
  53
  54     /**
  55      * Value for break strategy indicating simple line breaking. Automatic hyphens are not added
  56      * (though soft hyphens are respected), and modifying text generally doesn't affect the layout
  57      * before it (which yields a more consistent user experience when editing), but layout may not
  58      * be the highest quality.
  59      */
  60     public static final int BREAK_STRATEGY_SIMPLE = 0;
  61
  62     /**
  63      * Value for break strategy indicating high quality line breaking, including automatic
  64      * hyphenation and doing whole-paragraph optimization of line breaks.
  65      */
  66     public static final int BREAK_STRATEGY_HIGH_QUALITY = 1;
  67
  68     /**
  69      * Value for break strategy indicating balanced line breaking. The breaks are chosen to
  70      * make all lines as close to the same length as possible, including automatic hyphenation.
  71      */
  72     public static final int BREAK_STRATEGY_BALANCED = 2;
  73
  74     /** @hide */
  75     @IntDef({HYPHENATION_FREQUENCY_NORMAL, HYPHENATION_FREQUENCY_FULL,
  76              HYPHENATION_FREQUENCY_NONE})
  77     @Retention(RetentionPolicy.SOURCE)
  78     public @interface HyphenationFrequency {}
  79
  80     /**
  81      * Value for hyphenation frequency indicating no automatic hyphenation. Useful
  82      * for backward compatibility, and for cases where the automatic hyphenation algorithm results
  83      * in incorrect hyphenation. Mid-word breaks may still happen when a word is wider than the
  84      * layout and there is otherwise no valid break. Soft hyphens are ignored and will not be used
  85      * as suggestions for potential line breaks.
  86      */
  87     public static final int HYPHENATION_FREQUENCY_NONE = 0;
  88
  89     /**
  90      * Value for hyphenation frequency indicating a light amount of automatic hyphenation, which
  91      * is a conservative default. Useful for informal cases, such as short sentences or chat
  92      * messages.
  93      */
  94     public static final int HYPHENATION_FREQUENCY_NORMAL = 1;
  95
  96     /**
  97      * Value for hyphenation frequency indicating the full amount of automatic hyphenation, typical
  98      * in typography. Useful for running text and where it's important to put the maximum amount of
  99      * text in a screen with limited space.
 100      */
 101     public static final int HYPHENATION_FREQUENCY_FULL = 2;
 102
 103     private static final ParagraphStyle[] NO_PARA_SPANS =
 104         ArrayUtils.emptyArray(ParagraphStyle.class);
 105
 106     /** @hide */
 107     @IntDef({JUSTIFICATION_MODE_NONE, JUSTIFICATION_MODE_INTER_WORD})
 108     @Retention(RetentionPolicy.SOURCE)
 109     public @interface JustificationMode {}
 110
 111     /**
 112      * Value for justification mode indicating no justification.
 113      */
 114     public static final int JUSTIFICATION_MODE_NONE = 0;
 115
 116     /**
 117      * Value for justification mode indicating the text is justified by stretching word spacing.
 118      */
 119     public static final int JUSTIFICATION_MODE_INTER_WORD = 1;
 120
 121     /**
 122      * Return how wide a layout must be in order to display the specified text with one line per
 123      * paragraph.
 124      *
 125      * <p>As of O, Uses
 126      * {@link TextDirectionHeuristics#FIRSTSTRONG_LTR} as the default text direction heuristics. In
 127      * the earlier versions uses {@link TextDirectionHeuristics#LTR} as the default.</p>
 128      */
 129     public static float getDesiredWidth(CharSequence source,
 130                                         TextPaint paint) {
 131         return getDesiredWidth(source, 0, source.length(), paint);
 132     }
 133
 134     /**
 135      * Return how wide a layout must be in order to display the specified text slice with one
 136      * line per paragraph.
 137      *
 138      * <p>As of O, Uses
 139      * {@link TextDirectionHeuristics#FIRSTSTRONG_LTR} as the default text direction heuristics. In
 140      * the earlier versions uses {@link TextDirectionHeuristics#LTR} as the default.</p>
 141      */
 142     public static float getDesiredWidth(CharSequence source, int start, int end, TextPaint paint) {
 143         return getDesiredWidth(source, start, end, paint, TextDirectionHeuristics.FIRSTSTRONG_LTR);
 144     }
 145
 146     /**
 147      * Return how wide a layout must be in order to display the
 148      * specified text slice with one line per paragraph.
 149      *
 150      * @hide
 151      */
 152     public static float getDesiredWidth(CharSequence source, int start, int end, TextPaint paint,
 153             TextDirectionHeuristic textDir) {
 154         float need = 0;
 155
 156         int next;
 157         for (int i = start; i <= end; i = next) {
 158             next = TextUtils.indexOf(source, '\n', i, end);
 159
 160             if (next < 0)
 161                 next = end;
 162
 163             // note, omits trailing paragraph char
 164             float w = measurePara(paint, source, i, next, textDir);
 165
 166             if (w > need)
 167                 need = w;
 168
 169             next++;
 170         }
 171
 172         return need;
 173     }
 174
 175     /**
 176      * Subclasses of Layout use this constructor to set the display text,
 177      * width, and other standard properties.
 178      * @param text the text to render
 179      * @param paint the default paint for the layout.  Styles can override
 180      * various attributes of the paint.
 181      * @param width the wrapping width for the text.
 182      * @param align whether to left, right, or center the text.  Styles can
 183      * override the alignment.
 184      * @param spacingMult factor by which to scale the font size to get the
 185      * default line spacing
 186      * @param spacingAdd amount to add to the default line spacing
 187      */
 188     protected Layout(CharSequence text, TextPaint paint,
 189                      int width, Alignment align,
 190                      float spacingMult, float spacingAdd) {
 191         this(text, paint, width, align, TextDirectionHeuristics.FIRSTSTRONG_LTR,
 192                 spacingMult, spacingAdd);
 193     }
 194
 195     /**
 196      * Subclasses of Layout use this constructor to set the display text,
 197      * width, and other standard properties.
 198      * @param text the text to render
 199      * @param paint the default paint for the layout.  Styles can override
 200      * various attributes of the paint.
 201      * @param width the wrapping width for the text.
 202      * @param align whether to left, right, or center the text.  Styles can
 203      * override the alignment.
 204      * @param spacingMult factor by which to scale the font size to get the
 205      * default line spacing
 206      * @param spacingAdd amount to add to the default line spacing
 207      *
 208      * @hide
 209      */
 210     protected Layout(CharSequence text, TextPaint paint,
 211                      int width, Alignment align, TextDirectionHeuristic textDir,
 212                      float spacingMult, float spacingAdd) {
 213
 214         if (width < 0)
 215             throw new IllegalArgumentException("Layout: " + width + " < 0");
 216
 217         // Ensure paint doesn't have baselineShift set.
 218         // While normally we don't modify the paint the user passed in,
 219         // we were already doing this in Styled.drawUniformRun with both
 220         // baselineShift and bgColor.  We probably should reevaluate bgColor.
 221         if (paint != null) {
 222             paint.bgColor = 0;
 223             paint.baselineShift = 0;
 224         }
 225
 226         mText = text;
 227         mPaint = paint;
 228         mWidth = width;
 229         mAlignment = align;
 230         mSpacingMult = spacingMult;
 231         mSpacingAdd = spacingAdd;
 232         mSpannedText = text instanceof Spanned;
 233         mTextDir = textDir;
 234     }
 235
 236     /** @hide */
 237     protected void setJustificationMode(@JustificationMode int justificationMode) {
 238         mJustificationMode = justificationMode;
 239     }
 240
 241     /**
 242      * Replace constructor properties of this Layout with new ones.  Be careful.
 243      */
 244     /* package */ void replaceWith(CharSequence text, TextPaint paint,
 245                               int width, Alignment align,
 246                               float spacingmult, float spacingadd) {
 247         if (width < 0) {
 248             throw new IllegalArgumentException("Layout: " + width + " < 0");
 249         }
 250
 251         mText = text;
 252         mPaint = paint;
 253         mWidth = width;
 254         mAlignment = align;
 255         mSpacingMult = spacingmult;
 256         mSpacingAdd = spacingadd;
 257         mSpannedText = text instanceof Spanned;
 258     }
 259
 260     /**
 261      * Draw this Layout on the specified Canvas.
 262      */
 263     public void draw(Canvas c) {
 264         draw(c, null, null, 0);
 265     }
 266
 267     /**
 268      * Draw this Layout on the specified canvas, with the highlight path drawn
 269      * between the background and the text.
 270      *
 271      * @param canvas the canvas
 272      * @param highlight the path of the highlight or cursor; can be null
 273      * @param highlightPaint the paint for the highlight
 274      * @param cursorOffsetVertical the amount to temporarily translate the
 275      *        canvas while rendering the highlight
 276      */
 277     public void draw(Canvas canvas, Path highlight, Paint highlightPaint,
 278             int cursorOffsetVertical) {
 279         final long lineRange = getLineRangeForDraw(canvas);
 280         int firstLine = TextUtils.unpackRangeStartFromLong(lineRange);
 281         int lastLine = TextUtils.unpackRangeEndFromLong(lineRange);
 282         if (lastLine < 0) return;
 283
 284         drawBackground(canvas, highlight, highlightPaint, cursorOffsetVertical,
 285                 firstLine, lastLine);
 286         drawText(canvas, firstLine, lastLine);
 287     }
 288
 289     private boolean isJustificationRequired(int lineNum) {
 290         if (mJustificationMode == JUSTIFICATION_MODE_NONE) return false;
 291         final int lineEnd = getLineEnd(lineNum);
 292         return lineEnd < mText.length() && mText.charAt(lineEnd - 1) != '\n';
 293     }
 294
 295     private float getJustifyWidth(int lineNum) {
 296         Alignment paraAlign = mAlignment;
 297         TabStops tabStops = null;
 298         boolean tabStopsIsInitialized = false;
 299
 300         int left = 0;
 301         int right = mWidth;
 302
 303         final int dir = getParagraphDirection(lineNum);
 304
 305         ParagraphStyle[] spans = NO_PARA_SPANS;
 306         if (mSpannedText) {
 307             Spanned sp = (Spanned) mText;
 308             final int start = getLineStart(lineNum);
 309
 310             final boolean isFirstParaLine = (start == 0 || mText.charAt(start - 1) == '\n');
 311
 312             if (isFirstParaLine) {
 313                 final int spanEnd = sp.nextSpanTransition(start, mText.length(),
 314                         ParagraphStyle.class);
 315                 spans = getParagraphSpans(sp, start, spanEnd, ParagraphStyle.class);
 316
 317                 for (int n = spans.length - 1; n >= 0; n--) {
 318                     if (spans[n] instanceof AlignmentSpan) {
 319                         paraAlign = ((AlignmentSpan) spans[n]).getAlignment();
 320                         break;
 321                     }
 322                 }
 323             }
 324
 325             final int length = spans.length;
 326             boolean useFirstLineMargin = isFirstParaLine;
 327             for (int n = 0; n < length; n++) {
 328                 if (spans[n] instanceof LeadingMarginSpan2) {
 329                     int count = ((LeadingMarginSpan2) spans[n]).getLeadingMarginLineCount();
 330                     int startLine = getLineForOffset(sp.getSpanStart(spans[n]));
 331                     if (lineNum < startLine + count) {
 332                         useFirstLineMargin = true;
 333                         break;
 334                     }
 335                 }
 336             }
 337             for (int n = 0; n < length; n++) {
 338                 if (spans[n] instanceof LeadingMarginSpan) {
 339                     LeadingMarginSpan margin = (LeadingMarginSpan) spans[n];
 340                     if (dir == DIR_RIGHT_TO_LEFT) {
 341                         right -= margin.getLeadingMargin(useFirstLineMargin);
 342                     } else {
 343                         left += margin.getLeadingMargin(useFirstLineMargin);
 344                     }
 345                 }
 346             }
 347         }
 348
 349         if (getLineContainsTab(lineNum)) {
 350             tabStops = new TabStops(TAB_INCREMENT, spans);
 351         }
 352
 353         final Alignment align;
 354         if (paraAlign == Alignment.ALIGN_LEFT) {
 355             align = (dir == DIR_LEFT_TO_RIGHT) ?  Alignment.ALIGN_NORMAL : Alignment.ALIGN_OPPOSITE;
 356         } else if (paraAlign == Alignment.ALIGN_RIGHT) {
 357             align = (dir == DIR_LEFT_TO_RIGHT) ?  Alignment.ALIGN_OPPOSITE : Alignment.ALIGN_NORMAL;
 358         } else {
 359             align = paraAlign;
 360         }
 361
 362         final int indentWidth;
 363         if (align == Alignment.ALIGN_NORMAL) {
 364             if (dir == DIR_LEFT_TO_RIGHT) {
 365                 indentWidth = getIndentAdjust(lineNum, Alignment.ALIGN_LEFT);
 366             } else {
 367                 indentWidth = -getIndentAdjust(lineNum, Alignment.ALIGN_RIGHT);
 368             }
 369         } else if (align == Alignment.ALIGN_OPPOSITE) {
 370             if (dir == DIR_LEFT_TO_RIGHT) {
 371                 indentWidth = -getIndentAdjust(lineNum, Alignment.ALIGN_RIGHT);
 372             } else {
 373                 indentWidth = getIndentAdjust(lineNum, Alignment.ALIGN_LEFT);
 374             }
 375         } else { // Alignment.ALIGN_CENTER
 376             indentWidth = getIndentAdjust(lineNum, Alignment.ALIGN_CENTER);
 377         }
 378
 379         return right - left - indentWidth;
 380     }
 381
 382     /**
 383      * @hide
 384      */
 385     public void drawText(Canvas canvas, int firstLine, int lastLine) {
 386         int previousLineBottom = getLineTop(firstLine);
 387         int previousLineEnd = getLineStart(firstLine);
 388         ParagraphStyle[] spans = NO_PARA_SPANS;
 389         int spanEnd = 0;
 390         final TextPaint paint = mPaint;
 391         CharSequence buf = mText;
 392
 393         Alignment paraAlign = mAlignment;
 394         TabStops tabStops = null;
 395         boolean tabStopsIsInitialized = false;
 396
 397         TextLine tl = TextLine.obtain();
 398
 399         // Draw the lines, one at a time.
 400         // The baseline is the top of the following line minus the current line's descent.
 401         for (int lineNum = firstLine; lineNum <= lastLine; lineNum++) {
 402             int start = previousLineEnd;
 403             previousLineEnd = getLineStart(lineNum + 1);
 404             final boolean justify = isJustificationRequired(lineNum);
 405             int end = getLineVisibleEnd(lineNum, start, previousLineEnd);
 406
 407             int ltop = previousLineBottom;
 408             int lbottom = getLineTop(lineNum + 1);
 409             previousLineBottom = lbottom;
 410             int lbaseline = lbottom - getLineDescent(lineNum);
 411
 412             int dir = getParagraphDirection(lineNum);
 413             int left = 0;
 414             int right = mWidth;
 415
 416             if (mSpannedText) {
 417                 Spanned sp = (Spanned) buf;
 418                 int textLength = buf.length();
 419                 boolean isFirstParaLine = (start == 0 || buf.charAt(start - 1) == '\n');
 420
 421                 // New batch of paragraph styles, collect into spans array.
 422                 // Compute the alignment, last alignment style wins.
 423                 // Reset tabStops, we'll rebuild if we encounter a line with
 424                 // tabs.
 425                 // We expect paragraph spans to be relatively infrequent, use
 426                 // spanEnd so that we can check less frequently.  Since
 427                 // paragraph styles ought to apply to entire paragraphs, we can
 428                 // just collect the ones present at the start of the paragraph.
 429                 // If spanEnd is before the end of the paragraph, that's not
 430                 // our problem.
 431                 if (start >= spanEnd && (lineNum == firstLine || isFirstParaLine)) {
 432                     spanEnd = sp.nextSpanTransition(start, textLength,
 433                                                     ParagraphStyle.class);
 434                     spans = getParagraphSpans(sp, start, spanEnd, ParagraphStyle.class);
 435
 436                     paraAlign = mAlignment;
 437                     for (int n = spans.length - 1; n >= 0; n--) {
 438                         if (spans[n] instanceof AlignmentSpan) {
 439                             paraAlign = ((AlignmentSpan) spans[n]).getAlignment();
 440                             break;
 441                         }
 442                     }
 443
 444                     tabStopsIsInitialized = false;
 445                 }
 446
 447                 // Draw all leading margin spans.  Adjust left or right according
 448                 // to the paragraph direction of the line.
 449                 final int length = spans.length;
 450                 boolean useFirstLineMargin = isFirstParaLine;
 451                 for (int n = 0; n < length; n++) {
 452                     if (spans[n] instanceof LeadingMarginSpan2) {
 453                         int count = ((LeadingMarginSpan2) spans[n]).getLeadingMarginLineCount();
 454                         int startLine = getLineForOffset(sp.getSpanStart(spans[n]));
 455                         // if there is more than one LeadingMarginSpan2, use
 456                         // the count that is greatest
 457                         if (lineNum < startLine + count) {
 458                             useFirstLineMargin = true;
 459                             break;
 460                         }
 461                     }
 462                 }
 463                 for (int n = 0; n < length; n++) {
 464                     if (spans[n] instanceof LeadingMarginSpan) {
 465                         LeadingMarginSpan margin = (LeadingMarginSpan) spans[n];
 466                         if (dir == DIR_RIGHT_TO_LEFT) {
 467                             margin.drawLeadingMargin(canvas, paint, right, dir, ltop,
 468                                                      lbaseline, lbottom, buf,
 469                                                      start, end, isFirstParaLine, this);
 470                             right -= margin.getLeadingMargin(useFirstLineMargin);
 471                         } else {
 472                             margin.drawLeadingMargin(canvas, paint, left, dir, ltop,
 473                                                      lbaseline, lbottom, buf,
 474                                                      start, end, isFirstParaLine, this);
 475                             left += margin.getLeadingMargin(useFirstLineMargin);
 476                         }
 477                     }
 478                 }
 479             }
 480
 481             boolean hasTab = getLineContainsTab(lineNum);
 482             // Can't tell if we have tabs for sure, currently
 483             if (hasTab && !tabStopsIsInitialized) {
 484                 if (tabStops == null) {
 485                     tabStops = new TabStops(TAB_INCREMENT, spans);
 486                 } else {
 487                     tabStops.reset(TAB_INCREMENT, spans);
 488                 }
 489                 tabStopsIsInitialized = true;
 490             }
 491
 492             // Determine whether the line aligns to normal, opposite, or center.
 493             Alignment align = paraAlign;
 494             if (align == Alignment.ALIGN_LEFT) {
 495                 align = (dir == DIR_LEFT_TO_RIGHT) ?
 496                     Alignment.ALIGN_NORMAL : Alignment.ALIGN_OPPOSITE;
 497             } else if (align == Alignment.ALIGN_RIGHT) {
 498                 align = (dir == DIR_LEFT_TO_RIGHT) ?
 499                     Alignment.ALIGN_OPPOSITE : Alignment.ALIGN_NORMAL;
 500             }
 501
 502             int x;
 503             final int indentWidth;
 504             if (align == Alignment.ALIGN_NORMAL) {
 505                 if (dir == DIR_LEFT_TO_RIGHT) {
 506                     indentWidth = getIndentAdjust(lineNum, Alignment.ALIGN_LEFT);
 507                     x = left + indentWidth;
 508                 } else {
 509                     indentWidth = -getIndentAdjust(lineNum, Alignment.ALIGN_RIGHT);
 510                     x = right - indentWidth;
 511                 }
 512             } else {
 513                 int max = (int)getLineExtent(lineNum, tabStops, false);
 514                 if (align == Alignment.ALIGN_OPPOSITE) {
 515                     if (dir == DIR_LEFT_TO_RIGHT) {
 516                         indentWidth = -getIndentAdjust(lineNum, Alignment.ALIGN_RIGHT);
 517                         x = right - max - indentWidth;
 518                     } else {
 519                         indentWidth = getIndentAdjust(lineNum, Alignment.ALIGN_LEFT);
 520                         x = left - max + indentWidth;
 521                     }
 522                 } else { // Alignment.ALIGN_CENTER
 523                     indentWidth = getIndentAdjust(lineNum, Alignment.ALIGN_CENTER);
 524                     max = max & ~1;
 525                     x = ((right + left - max) >> 1) + indentWidth;
 526                 }
 527             }
 528
 529             paint.setHyphenEdit(getHyphen(lineNum));
 530             Directions directions = getLineDirections(lineNum);
 531             if (directions == DIRS_ALL_LEFT_TO_RIGHT && !mSpannedText && !hasTab && !justify) {
 532                 // XXX: assumes there's nothing additional to be done
 533                 canvas.drawText(buf, start, end, x, lbaseline, paint);
 534             } else {
 535                 tl.set(paint, buf, start, end, dir, directions, hasTab, tabStops);
 536                 if (justify) {
 537                     tl.justify(right - left - indentWidth);
 538                 }
 539                 tl.draw(canvas, x, ltop, lbaseline, lbottom);
 540             }
 541             paint.setHyphenEdit(0);
 542         }
 543
 544         TextLine.recycle(tl);
 545     }
 546
 547     /**
 548      * @hide
 549      */
 550     public void drawBackground(Canvas canvas, Path highlight, Paint highlightPaint,
 551             int cursorOffsetVertical, int firstLine, int lastLine) {
 552         // First, draw LineBackgroundSpans.
 553         // LineBackgroundSpans know nothing about the alignment, margins, or
 554         // direction of the layout or line.  XXX: Should they?
 555         // They are evaluated at each line.
 556         if (mSpannedText) {
 557             if (mLineBackgroundSpans == null) {
 558                 mLineBackgroundSpans = new SpanSet<LineBackgroundSpan>(LineBackgroundSpan.class);
 559             }
 560
 561             Spanned buffer = (Spanned) mText;
 562             int textLength = buffer.length();
 563             mLineBackgroundSpans.init(buffer, 0, textLength);
 564
 565             if (mLineBackgroundSpans.numberOfSpans > 0) {
 566                 int previousLineBottom = getLineTop(firstLine);
 567                 int previousLineEnd = getLineStart(firstLine);
 568                 ParagraphStyle[] spans = NO_PARA_SPANS;
 569                 int spansLength = 0;
 570                 TextPaint paint = mPaint;
 571                 int spanEnd = 0;
 572                 final int width = mWidth;
 573                 for (int i = firstLine; i <= lastLine; i++) {
 574                     int start = previousLineEnd;
 575                     int end = getLineStart(i + 1);
 576                     previousLineEnd = end;
 577
 578                     int ltop = previousLineBottom;
 579                     int lbottom = getLineTop(i + 1);
 580                     previousLineBottom = lbottom;
 581                     int lbaseline = lbottom - getLineDescent(i);
 582
 583                     if (start >= spanEnd) {
 584                         // These should be infrequent, so we'll use this so that
 585                         // we don't have to check as often.
 586                         spanEnd = mLineBackgroundSpans.getNextTransition(start, textLength);
 587                         // All LineBackgroundSpans on a line contribute to its background.
 588                         spansLength = 0;
 589                         // Duplication of the logic of getParagraphSpans
 590                         if (start != end || start == 0) {
 591                             // Equivalent to a getSpans(start, end), but filling the 'spans' local
 592                             // array instead to reduce memory allocation
 593                             for (int j = 0; j < mLineBackgroundSpans.numberOfSpans; j++) {
 594                                 // equal test is valid since both intervals are not empty by
 595                                 // construction
 596                                 if (mLineBackgroundSpans.spanStarts[j] >= end ||
 597                                         mLineBackgroundSpans.spanEnds[j] <= start) continue;
 598                                 spans = GrowingArrayUtils.append(
 599                                         spans, spansLength, mLineBackgroundSpans.spans[j]);
 600                                 spansLength++;
 601                             }
 602                         }
 603                     }
 604
 605                     for (int n = 0; n < spansLength; n++) {
 606                         LineBackgroundSpan lineBackgroundSpan = (LineBackgroundSpan) spans[n];
 607                         lineBackgroundSpan.drawBackground(canvas, paint, 0, width,
 608                                 ltop, lbaseline, lbottom,
 609                                 buffer, start, end, i);
 610                     }
 611                 }
 612             }
 613             mLineBackgroundSpans.recycle();
 614         }
 615
 616         // There can be a highlight even without spans if we are drawing
 617         // a non-spanned transformation of a spanned editing buffer.
 618         if (highlight != null) {
 619             if (cursorOffsetVertical != 0) canvas.translate(0, cursorOffsetVertical);
 620             canvas.drawPath(highlight, highlightPaint);
 621             if (cursorOffsetVertical != 0) canvas.translate(0, -cursorOffsetVertical);
 622         }
 623     }
 624
 625     /**
 626      * @param canvas
 627      * @return The range of lines that need to be drawn, possibly empty.
 628      * @hide
 629      */
 630     public long getLineRangeForDraw(Canvas canvas) {
 631         int dtop, dbottom;
 632
 633         synchronized (sTempRect) {
 634             if (!canvas.getClipBounds(sTempRect)) {
 635                 // Negative range end used as a special flag
 636                 return TextUtils.packRangeInLong(0, -1);
 637             }
 638
 639             dtop = sTempRect.top;
 640             dbottom = sTempRect.bottom;
 641         }
 642
 643         final int top = Math.max(dtop, 0);
 644         final int bottom = Math.min(getLineTop(getLineCount()), dbottom);
 645
 646         if (top >= bottom) return TextUtils.packRangeInLong(0, -1);
 647         return TextUtils.packRangeInLong(getLineForVertical(top), getLineForVertical(bottom));
 648     }
 649
 650     /**
 651      * Return the start position of the line, given the left and right bounds
 652      * of the margins.
 653      *
 654      * @param line the line index
 655      * @param left the left bounds (0, or leading margin if ltr para)
 656      * @param right the right bounds (width, minus leading margin if rtl para)
 657      * @return the start position of the line (to right of line if rtl para)
 658      */
 659     private int getLineStartPos(int line, int left, int right) {
 660         // Adjust the point at which to start rendering depending on the
 661         // alignment of the paragraph.
 662         Alignment align = getParagraphAlignment(line);
 663         int dir = getParagraphDirection(line);
 664
 665         if (align == Alignment.ALIGN_LEFT) {
 666             align = (dir == DIR_LEFT_TO_RIGHT) ? Alignment.ALIGN_NORMAL : Alignment.ALIGN_OPPOSITE;
 667         } else if (align == Alignment.ALIGN_RIGHT) {
 668             align = (dir == DIR_LEFT_TO_RIGHT) ? Alignment.ALIGN_OPPOSITE : Alignment.ALIGN_NORMAL;
 669         }
 670
 671         int x;
 672         if (align == Alignment.ALIGN_NORMAL) {
 673             if (dir == DIR_LEFT_TO_RIGHT) {
 674                 x = left + getIndentAdjust(line, Alignment.ALIGN_LEFT);
 675             } else {
 676                 x = right + getIndentAdjust(line, Alignment.ALIGN_RIGHT);
 677             }
 678         } else {
 679             TabStops tabStops = null;
 680             if (mSpannedText && getLineContainsTab(line)) {
 681                 Spanned spanned = (Spanned) mText;
 682                 int start = getLineStart(line);
 683                 int spanEnd = spanned.nextSpanTransition(start, spanned.length(),
 684                         TabStopSpan.class);
 685                 TabStopSpan[] tabSpans = getParagraphSpans(spanned, start, spanEnd,
 686                         TabStopSpan.class);
 687                 if (tabSpans.length > 0) {
 688                     tabStops = new TabStops(TAB_INCREMENT, tabSpans);
 689                 }
 690             }
 691             int max = (int)getLineExtent(line, tabStops, false);
 692             if (align == Alignment.ALIGN_OPPOSITE) {
 693                 if (dir == DIR_LEFT_TO_RIGHT) {
 694                     x = right - max + getIndentAdjust(line, Alignment.ALIGN_RIGHT);
 695                 } else {
 696                     // max is negative here
 697                     x = left - max + getIndentAdjust(line, Alignment.ALIGN_LEFT);
 698                 }
 699             } else { // Alignment.ALIGN_CENTER
 700                 max = max & ~1;
 701                 x = (left + right - max) >> 1 + getIndentAdjust(line, Alignment.ALIGN_CENTER);
 702             }
 703         }
 704         return x;
 705     }
 706
 707     /**
 708      * Return the text that is displayed by this Layout.
 709      */
 710     public final CharSequence getText() {
 711         return mText;
 712     }
 713
 714     /**
 715      * Return the base Paint properties for this layout.
 716      * Do NOT change the paint, which may result in funny
 717      * drawing for this layout.
 718      */
 719     public final TextPaint getPaint() {
 720         return mPaint;
 721     }
 722
 723     /**
 724      * Return the width of this layout.
 725      */
 726     public final int getWidth() {
 727         return mWidth;
 728     }
 729
 730     /**
 731      * Return the width to which this Layout is ellipsizing, or
 732      * {@link #getWidth} if it is not doing anything special.
 733      */
 734     public int getEllipsizedWidth() {
 735         return mWidth;
 736     }
 737
 738     /**
 739      * Increase the width of this layout to the specified width.
 740      * Be careful to use this only when you know it is appropriate&mdash;
 741      * it does not cause the text to reflow to use the full new width.
 742      */
 743     public final void increaseWidthTo(int wid) {
 744         if (wid < mWidth) {
 745             throw new RuntimeException("attempted to reduce Layout width");
 746         }
 747
 748         mWidth = wid;
 749     }
 750
 751     /**
 752      * Return the total height of this layout.
 753      */
 754     public int getHeight() {
 755         return getLineTop(getLineCount());
 756     }
 757
 758     /**
 759      * Return the total height of this layout.
 760      *
 761      * @param cap if true and max lines is set, returns the height of the layout at the max lines.
 762      *
 763      * @hide
 764      */
 765     public int getHeight(boolean cap) {
 766         return getHeight();
 767     }
 768
 769     /**
 770      * Return the base alignment of this layout.
 771      */
 772     public final Alignment getAlignment() {
 773         return mAlignment;
 774     }
 775
 776     /**
 777      * Return what the text height is multiplied by to get the line height.
 778      */
 779     public final float getSpacingMultiplier() {
 780         return mSpacingMult;
 781     }
 782
 783     /**
 784      * Return the number of units of leading that are added to each line.
 785      */
 786     public final float getSpacingAdd() {
 787         return mSpacingAdd;
 788     }
 789
 790     /**
 791      * Return the heuristic used to determine paragraph text direction.
 792      * @hide
 793      */
 794     public final TextDirectionHeuristic getTextDirectionHeuristic() {
 795         return mTextDir;
 796     }
 797
 798     /**
 799      * Return the number of lines of text in this layout.
 800      */
 801     public abstract int getLineCount();
 802
 803     /**
 804      * Return the baseline for the specified line (0&hellip;getLineCount() - 1)
 805      * If bounds is not null, return the top, left, right, bottom extents
 806      * of the specified line in it.
 807      * @param line which line to examine (0..getLineCount() - 1)
 808      * @param bounds Optional. If not null, it returns the extent of the line
 809      * @return the Y-coordinate of the baseline
 810      */
 811     public int getLineBounds(int line, Rect bounds) {
 812         if (bounds != null) {
 813             bounds.left = 0;     // ???
 814             bounds.top = getLineTop(line);
 815             bounds.right = mWidth;   // ???
 816             bounds.bottom = getLineTop(line + 1);
 817         }
 818         return getLineBaseline(line);
 819     }
 820
 821     /**
 822      * Return the vertical position of the top of the specified line
 823      * (0&hellip;getLineCount()).
 824      * If the specified line is equal to the line count, returns the
 825      * bottom of the last line.
 826      */
 827     public abstract int getLineTop(int line);
 828
 829     /**
 830      * Return the descent of the specified line(0&hellip;getLineCount() - 1).
 831      */
 832     public abstract int getLineDescent(int line);
 833
 834     /**
 835      * Return the text offset of the beginning of the specified line (
 836      * 0&hellip;getLineCount()). If the specified line is equal to the line
 837      * count, returns the length of the text.
 838      */
 839     public abstract int getLineStart(int line);
 840
 841     /**
 842      * Returns the primary directionality of the paragraph containing the
 843      * specified line, either 1 for left-to-right lines, or -1 for right-to-left
 844      * lines (see {@link #DIR_LEFT_TO_RIGHT}, {@link #DIR_RIGHT_TO_LEFT}).
 845      */
 846     public abstract int getParagraphDirection(int line);
 847
 848     /**
 849      * Returns whether the specified line contains one or more
 850      * characters that need to be handled specially, like tabs.
 851      */
 852     public abstract boolean getLineContainsTab(int line);
 853
 854     /**
 855      * Returns the directional run information for the specified line.
 856      * The array alternates counts of characters in left-to-right
 857      * and right-to-left segments of the line.
 858      *
 859      * <p>NOTE: this is inadequate to support bidirectional text, and will change.
 860      */
 861     public abstract Directions getLineDirections(int line);
 862
 863     /**
 864      * Returns the (negative) number of extra pixels of ascent padding in the
 865      * top line of the Layout.
 866      */
 867     public abstract int getTopPadding();
 868
 869     /**
 870      * Returns the number of extra pixels of descent padding in the
 871      * bottom line of the Layout.
 872      */
 873     public abstract int getBottomPadding();
 874
 875     /**
 876      * Returns the hyphen edit for a line.
 877      *
 878      * @hide
 879      */
 880     public int getHyphen(int line) {
 881         return 0;
 882     }
 883
 884     /**
 885      * Returns the left indent for a line.
 886      *
 887      * @hide
 888      */
 889     public int getIndentAdjust(int line, Alignment alignment) {
 890         return 0;
 891     }
 892
 893     /**
 894      * Returns true if the character at offset and the preceding character
 895      * are at different run levels (and thus there's a split caret).
 896      * @param offset the offset
 897      * @return true if at a level boundary
 898      * @hide
 899      */
 900     public boolean isLevelBoundary(int offset) {
 901         int line = getLineForOffset(offset);
 902         Directions dirs = getLineDirections(line);
 903         if (dirs == DIRS_ALL_LEFT_TO_RIGHT || dirs == DIRS_ALL_RIGHT_TO_LEFT) {
 904             return false;
 905         }
 906
 907         int[] runs = dirs.mDirections;
 908         int lineStart = getLineStart(line);
 909         int lineEnd = getLineEnd(line);
 910         if (offset == lineStart || offset == lineEnd) {
 911             int paraLevel = getParagraphDirection(line) == 1 ? 0 : 1;
 912             int runIndex = offset == lineStart ? 0 : runs.length - 2;
 913             return ((runs[runIndex + 1] >>> RUN_LEVEL_SHIFT) & RUN_LEVEL_MASK) != paraLevel;
 914         }
 915
 916         offset -= lineStart;
 917         for (int i = 0; i < runs.length; i += 2) {
 918             if (offset == runs[i]) {
 919                 return true;
 920             }
 921         }
 922         return false;
 923     }
 924
 925     /**
 926      * Returns true if the character at offset is right to left (RTL).
 927      * @param offset the offset
 928      * @return true if the character is RTL, false if it is LTR
 929      */
 930     public boolean isRtlCharAt(int offset) {
 931         int line = getLineForOffset(offset);
 932         Directions dirs = getLineDirections(line);
 933         if (dirs == DIRS_ALL_LEFT_TO_RIGHT) {
 934             return false;
 935         }
 936         if (dirs == DIRS_ALL_RIGHT_TO_LEFT) {
 937             return  true;
 938         }
 939         int[] runs = dirs.mDirections;
 940         int lineStart = getLineStart(line);
 941         for (int i = 0; i < runs.length; i += 2) {
 942             int start = lineStart + runs[i];
 943             int limit = start + (runs[i+1] & RUN_LENGTH_MASK);
 944             if (offset >= start && offset < limit) {
 945                 int level = (runs[i+1] >>> RUN_LEVEL_SHIFT) & RUN_LEVEL_MASK;
 946                 return ((level & 1) != 0);
 947             }
 948         }
 949         // Should happen only if the offset is "out of bounds"
 950         return false;
 951     }
 952
 953     /**
 954      * Returns the range of the run that the character at offset belongs to.
 955      * @param offset the offset
 956      * @return The range of the run
 957      * @hide
 958      */
 959     public long getRunRange(int offset) {
 960         int line = getLineForOffset(offset);
 961         Directions dirs = getLineDirections(line);
 962         if (dirs == DIRS_ALL_LEFT_TO_RIGHT || dirs == DIRS_ALL_RIGHT_TO_LEFT) {
 963             return TextUtils.packRangeInLong(0, getLineEnd(line));
 964         }
 965         int[] runs = dirs.mDirections;
 966         int lineStart = getLineStart(line);
 967         for (int i = 0; i < runs.length; i += 2) {
 968             int start = lineStart + runs[i];
 969             int limit = start + (runs[i+1] & RUN_LENGTH_MASK);
 970             if (offset >= start && offset < limit) {
 971                 return TextUtils.packRangeInLong(start, limit);
 972             }
 973         }
 974         // Should happen only if the offset is "out of bounds"
 975         return TextUtils.packRangeInLong(0, getLineEnd(line));
 976     }
 977
 978     /**
 979      * Checks if the trailing BiDi level should be used for an offset
 980      *
 981      * This method is useful when the offset is at the BiDi level transition point and determine
 982      * which run need to be used. For example, let's think about following input: (L* denotes
 983      * Left-to-Right characters, R* denotes Right-to-Left characters.)
 984      * Input (Logical Order): L1 L2 L3 R1 R2 R3 L4 L5 L6
 985      * Input (Display Order): L1 L2 L3 R3 R2 R1 L4 L5 L6
 986      *
 987      * Then, think about selecting the range (3, 6). The offset=3 and offset=6 are ambiguous here
 988      * since they are at the BiDi transition point.  In Android, the offset is considered to be
 989      * associated with the trailing run if the BiDi level of the trailing run is higher than of the
 990      * previous run.  In this case, the BiDi level of the input text is as follows:
 991      *
 992      * Input (Logical Order): L1 L2 L3 R1 R2 R3 L4 L5 L6
 993      *              BiDi Run: [ Run 0 ][ Run 1 ][ Run 2 ]
 994      *            BiDi Level:  0  0  0  1  1  1  0  0  0
 995      *
 996      * Thus, offset = 3 is part of Run 1 and this method returns true for offset = 3, since the BiDi
 997      * level of Run 1 is higher than the level of Run 0.  Similarly, the offset = 6 is a part of Run
 998      * 1 and this method returns false for the offset = 6 since the BiDi level of Run 1 is higher
 999      * than the level of Run 2.
1000      *
1001      * @returns true if offset is at the BiDi level transition point and trailing BiDi level is
1002      *          higher than previous BiDi level. See above for the detail.
1003      */
1004     private boolean primaryIsTrailingPrevious(int offset) {
1005         int line = getLineForOffset(offset);
1006         int lineStart = getLineStart(line);
1007         int lineEnd = getLineEnd(line);
1008         int[] runs = getLineDirections(line).mDirections;
1009
1010         int levelAt = -1;
1011         for (int i = 0; i < runs.length; i += 2) {
1012             int start = lineStart + runs[i];
1013             int limit = start + (runs[i+1] & RUN_LENGTH_MASK);
1014             if (limit > lineEnd) {
1015                 limit = lineEnd;
1016             }
1017             if (offset >= start && offset < limit) {
1018                 if (offset > start) {
1019                     // Previous character is at same level, so don't use trailing.
1020                     return false;
1021                 }
1022                 levelAt = (runs[i+1] >>> RUN_LEVEL_SHIFT) & RUN_LEVEL_MASK;
1023                 break;
1024             }
1025         }
1026         if (levelAt == -1) {
1027             // Offset was limit of line.
1028             levelAt = getParagraphDirection(line) == 1 ? 0 : 1;
1029         }
1030
1031         // At level boundary, check previous level.
1032         int levelBefore = -1;
1033         if (offset == lineStart) {
1034             levelBefore = getParagraphDirection(line) == 1 ? 0 : 1;
1035         } else {
1036             offset -= 1;
1037             for (int i = 0; i < runs.length; i += 2) {
1038                 int start = lineStart + runs[i];
1039                 int limit = start + (runs[i+1] & RUN_LENGTH_MASK);
1040                 if (limit > lineEnd) {
1041                     limit = lineEnd;
1042                 }
1043                 if (offset >= start && offset < limit) {
1044                     levelBefore = (runs[i+1] >>> RUN_LEVEL_SHIFT) & RUN_LEVEL_MASK;
1045                     break;
1046                 }
1047             }
1048         }
1049
1050         return levelBefore < levelAt;
1051     }
1052
1053     /**
1054      * Computes in linear time the results of calling
1055      * #primaryIsTrailingPrevious for all offsets on a line.
1056      * @param line The line giving the offsets we compute the information for
1057      * @return The array of results, indexed from 0, where 0 corresponds to the line start offset
1058      */
1059     private boolean[] primaryIsTrailingPreviousAllLineOffsets(int line) {
1060         int lineStart = getLineStart(line);
1061         int lineEnd = getLineEnd(line);
1062         int[] runs = getLineDirections(line).mDirections;
1063
1064         boolean[] trailing = new boolean[lineEnd - lineStart + 1];
1065
1066         byte[] level = new byte[lineEnd - lineStart + 1];
1067         for (int i = 0; i < runs.length; i += 2) {
1068             int start = lineStart + runs[i];
1069             int limit = start + (runs[i + 1] & RUN_LENGTH_MASK);
1070             if (limit > lineEnd) {
1071                 limit = lineEnd;
1072             }
1073             level[limit - lineStart - 1] =
1074                     (byte) ((runs[i + 1] >>> RUN_LEVEL_SHIFT) & RUN_LEVEL_MASK);
1075         }
1076
1077         for (int i = 0; i < runs.length; i += 2) {
1078             int start = lineStart + runs[i];
1079             byte currentLevel = (byte) ((runs[i + 1] >>> RUN_LEVEL_SHIFT) & RUN_LEVEL_MASK);
1080             trailing[start - lineStart] = currentLevel > (start == lineStart
1081                     ? (getParagraphDirection(line) == 1 ? 0 : 1)
1082                     : level[start - lineStart - 1]);
1083         }
1084
1085         return trailing;
1086     }
1087
1088     /**
1089      * Get the primary horizontal position for the specified text offset.
1090      * This is the location where a new character would be inserted in
1091      * the paragraph's primary direction.
1092      */
1093     public float getPrimaryHorizontal(int offset) {
1094         return getPrimaryHorizontal(offset, false /* not clamped */);
1095     }
1096
1097     /**
1098      * Get the primary horizontal position for the specified text offset, but
1099      * optionally clamp it so that it doesn't exceed the width of the layout.
1100      * @hide
1101      */
1102     public float getPrimaryHorizontal(int offset, boolean clamped) {
1103         boolean trailing = primaryIsTrailingPrevious(offset);
1104         return getHorizontal(offset, trailing, clamped);
1105     }
1106
1107     /**
1108      * Get the secondary horizontal position for the specified text offset.
1109      * This is the location where a new character would be inserted in
1110      * the direction other than the paragraph's primary direction.
1111      */
1112     public float getSecondaryHorizontal(int offset) {
1113         return getSecondaryHorizontal(offset, false /* not clamped */);
1114     }
1115
1116     /**
1117      * Get the secondary horizontal position for the specified text offset, but
1118      * optionally clamp it so that it doesn't exceed the width of the layout.
1119      * @hide
1120      */
1121     public float getSecondaryHorizontal(int offset, boolean clamped) {
1122         boolean trailing = primaryIsTrailingPrevious(offset);
1123         return getHorizontal(offset, !trailing, clamped);
1124     }
1125
1126     private float getHorizontal(int offset, boolean primary) {
1127         return primary ? getPrimaryHorizontal(offset) : getSecondaryHorizontal(offset);
1128     }
1129
1130     private float getHorizontal(int offset, boolean trailing, boolean clamped) {
1131         int line = getLineForOffset(offset);
1132
1133         return getHorizontal(offset, trailing, line, clamped);
1134     }
1135
1136     private float getHorizontal(int offset, boolean trailing, int line, boolean clamped) {
1137         int start = getLineStart(line);
1138         int end = getLineEnd(line);
1139         int dir = getParagraphDirection(line);
1140         boolean hasTab = getLineContainsTab(line);
1141         Directions directions = getLineDirections(line);
1142
1143         TabStops tabStops = null;
1144         if (hasTab && mText instanceof Spanned) {
1145             // Just checking this line should be good enough, tabs should be
1146             // consistent across all lines in a paragraph.
1147             TabStopSpan[] tabs = getParagraphSpans((Spanned) mText, start, end, TabStopSpan.class);
1148             if (tabs.length > 0) {
1149                 tabStops = new TabStops(TAB_INCREMENT, tabs); // XXX should reuse
1150             }
1151         }
1152
1153         TextLine tl = TextLine.obtain();
1154         tl.set(mPaint, mText, start, end, dir, directions, hasTab, tabStops);
1155         float wid = tl.measure(offset - start, trailing, null);
1156         TextLine.recycle(tl);
1157
1158         if (clamped && wid > mWidth) {
1159             wid = mWidth;
1160         }
1161         int left = getParagraphLeft(line);
1162         int right = getParagraphRight(line);
1163
1164         return getLineStartPos(line, left, right) + wid;
1165     }
1166
1167     /**
1168      * Computes in linear time the results of calling
1169      * #getHorizontal for all offsets on a line.
1170      * @param line The line giving the offsets we compute information for
1171      * @param clamped Whether to clamp the results to the width of the layout
1172      * @param primary Whether the results should be the primary or the secondary horizontal
1173      * @return The array of results, indexed from 0, where 0 corresponds to the line start offset
1174      */
1175     private float[] getLineHorizontals(int line, boolean clamped, boolean primary) {
1176         int start = getLineStart(line);
1177         int end = getLineEnd(line);
1178         int dir = getParagraphDirection(line);
1179         boolean hasTab = getLineContainsTab(line);
1180         Directions directions = getLineDirections(line);
1181
1182         TabStops tabStops = null;
1183         if (hasTab && mText instanceof Spanned) {
1184             // Just checking this line should be good enough, tabs should be
1185             // consistent across all lines in a paragraph.
1186             TabStopSpan[] tabs = getParagraphSpans((Spanned) mText, start, end, TabStopSpan.class);
1187             if (tabs.length > 0) {
1188                 tabStops = new TabStops(TAB_INCREMENT, tabs); // XXX should reuse
1189             }
1190         }
1191
1192         TextLine tl = TextLine.obtain();
1193         tl.set(mPaint, mText, start, end, dir, directions, hasTab, tabStops);
1194         boolean[] trailings = primaryIsTrailingPreviousAllLineOffsets(line);
1195         if (!primary) {
1196             for (int offset = 0; offset < trailings.length; ++offset) {
1197                 trailings[offset] = !trailings[offset];
1198             }
1199         }
1200         float[] wid = tl.measureAllOffsets(trailings, null);
1201         TextLine.recycle(tl);
1202
1203         if (clamped) {
1204             for (int offset = 0; offset <= wid.length; ++offset) {
1205                 if (wid[offset] > mWidth) {
1206                     wid[offset] = mWidth;
1207                 }
1208             }
1209         }
1210         int left = getParagraphLeft(line);
1211         int right = getParagraphRight(line);
1212
1213         int lineStartPos = getLineStartPos(line, left, right);
1214         float[] horizontal = new float[end - start + 1];
1215         for (int offset = 0; offset < horizontal.length; ++offset) {
1216             horizontal[offset] = lineStartPos + wid[offset];
1217         }
1218         return horizontal;
1219     }
1220
1221     /**
1222      * Get the leftmost position that should be exposed for horizontal
1223      * scrolling on the specified line.
1224      */
1225     public float getLineLeft(int line) {
1226         int dir = getParagraphDirection(line);
1227         Alignment align = getParagraphAlignment(line);
1228
1229         if (align == Alignment.ALIGN_LEFT) {
1230             return 0;
1231         } else if (align == Alignment.ALIGN_NORMAL) {
1232             if (dir == DIR_RIGHT_TO_LEFT)
1233                 return getParagraphRight(line) - getLineMax(line);
1234             else
1235                 return 0;
1236         } else if (align == Alignment.ALIGN_RIGHT) {
1237             return mWidth - getLineMax(line);
1238         } else if (align == Alignment.ALIGN_OPPOSITE) {
1239             if (dir == DIR_RIGHT_TO_LEFT)
1240                 return 0;
1241             else
1242                 return mWidth - getLineMax(line);
1243         } else { /* align == Alignment.ALIGN_CENTER */
1244             int left = getParagraphLeft(line);
1245             int right = getParagraphRight(line);
1246             int max = ((int) getLineMax(line)) & ~1;
1247
1248             return left + ((right - left) - max) / 2;
1249         }
1250     }
1251
1252     /**
1253      * Get the rightmost position that should be exposed for horizontal
1254      * scrolling on the specified line.
1255      */
1256     public float getLineRight(int line) {
1257         int dir = getParagraphDirection(line);
1258         Alignment align = getParagraphAlignment(line);
1259
1260         if (align == Alignment.ALIGN_LEFT) {
1261             return getParagraphLeft(line) + getLineMax(line);
1262         } else if (align == Alignment.ALIGN_NORMAL) {
1263             if (dir == DIR_RIGHT_TO_LEFT)
1264                 return mWidth;
1265             else
1266                 return getParagraphLeft(line) + getLineMax(line);
1267         } else if (align == Alignment.ALIGN_RIGHT) {
1268             return mWidth;
1269         } else if (align == Alignment.ALIGN_OPPOSITE) {
1270             if (dir == DIR_RIGHT_TO_LEFT)
1271                 return getLineMax(line);
1272             else
1273                 return mWidth;
1274         } else { /* align == Alignment.ALIGN_CENTER */
1275             int left = getParagraphLeft(line);
1276             int right = getParagraphRight(line);
1277             int max = ((int) getLineMax(line)) & ~1;
1278
1279             return right - ((right - left) - max) / 2;
1280         }
1281     }
1282
1283     /**
1284      * Gets the unsigned horizontal extent of the specified line, including
1285      * leading margin indent, but excluding trailing whitespace.
1286      */
1287     public float getLineMax(int line) {
1288         float margin = getParagraphLeadingMargin(line);
1289         float signedExtent = getLineExtent(line, false);
1290         return margin + (signedExtent >= 0 ? signedExtent : -signedExtent);
1291     }
1292
1293     /**
1294      * Gets the unsigned horizontal extent of the specified line, including
1295      * leading margin indent and trailing whitespace.
1296      */
1297     public float getLineWidth(int line) {
1298         float margin = getParagraphLeadingMargin(line);
1299         float signedExtent = getLineExtent(line, true);
1300         return margin + (signedExtent >= 0 ? signedExtent : -signedExtent);
1301     }
1302
1303     /**
1304      * Like {@link #getLineExtent(int,TabStops,boolean)} but determines the
1305      * tab stops instead of using the ones passed in.
1306      * @param line the index of the line
1307      * @param full whether to include trailing whitespace
1308      * @return the extent of the line
1309      */
1310     private float getLineExtent(int line, boolean full) {
1311         int start = getLineStart(line);
1312         int end = full ? getLineEnd(line) : getLineVisibleEnd(line);
1313
1314         boolean hasTabs = getLineContainsTab(line);
1315         TabStops tabStops = null;
1316         if (hasTabs && mText instanceof Spanned) {
1317             // Just checking this line should be good enough, tabs should be
1318             // consistent across all lines in a paragraph.
1319             TabStopSpan[] tabs = getParagraphSpans((Spanned) mText, start, end, TabStopSpan.class);
1320             if (tabs.length > 0) {
1321                 tabStops = new TabStops(TAB_INCREMENT, tabs); // XXX should reuse
1322             }
1323         }
1324         Directions directions = getLineDirections(line);
1325         // Returned directions can actually be null
1326         if (directions == null) {
1327             return 0f;
1328         }
1329         int dir = getParagraphDirection(line);
1330
1331         TextLine tl = TextLine.obtain();
1332         mPaint.setHyphenEdit(getHyphen(line));
1333         tl.set(mPaint, mText, start, end, dir, directions, hasTabs, tabStops);
1334         if (isJustificationRequired(line)) {
1335             tl.justify(getJustifyWidth(line));
1336         }
1337         float width = tl.metrics(null);
1338         mPaint.setHyphenEdit(0);
1339         TextLine.recycle(tl);
1340         return width;
1341     }
1342
1343     /**
1344      * Returns the signed horizontal extent of the specified line, excluding
1345      * leading margin.  If full is false, excludes trailing whitespace.
1346      * @param line the index of the line
1347      * @param tabStops the tab stops, can be null if we know they're not used.
1348      * @param full whether to include trailing whitespace
1349      * @return the extent of the text on this line
1350      */
1351     private float getLineExtent(int line, TabStops tabStops, boolean full) {
1352         int start = getLineStart(line);
1353         int end = full ? getLineEnd(line) : getLineVisibleEnd(line);
1354         boolean hasTabs = getLineContainsTab(line);
1355         Directions directions = getLineDirections(line);
1356         int dir = getParagraphDirection(line);
1357
1358         TextLine tl = TextLine.obtain();
1359         mPaint.setHyphenEdit(getHyphen(line));
1360         tl.set(mPaint, mText, start, end, dir, directions, hasTabs, tabStops);
1361         if (isJustificationRequired(line)) {
1362             tl.justify(getJustifyWidth(line));
1363         }
1364         float width = tl.metrics(null);
1365         mPaint.setHyphenEdit(0);
1366         TextLine.recycle(tl);
1367         return width;
1368     }
1369
1370     /**
1371      * Get the line number corresponding to the specified vertical position.
1372      * If you ask for a position above 0, you get 0; if you ask for a position
1373      * below the bottom of the text, you get the last line.
1374      */
1375     // FIXME: It may be faster to do a linear search for layouts without many lines.
1376     public int getLineForVertical(int vertical) {
1377         int high = getLineCount(), low = -1, guess;
1378
1379         while (high - low > 1) {
1380             guess = (high + low) / 2;
1381
1382             if (getLineTop(guess) > vertical)
1383                 high = guess;
1384             else
1385                 low = guess;
1386         }
1387
1388         if (low < 0)
1389             return 0;
1390         else
1391             return low;
1392     }
1393
1394     /**
1395      * Get the line number on which the specified text offset appears.
1396      * If you ask for a position before 0, you get 0; if you ask for a position
1397      * beyond the end of the text, you get the last line.
1398      */
1399     public int getLineForOffset(int offset) {
1400         int high = getLineCount(), low = -1, guess;
1401
1402         while (high - low > 1) {
1403             guess = (high + low) / 2;
1404
1405             if (getLineStart(guess) > offset)
1406                 high = guess;
1407             else
1408                 low = guess;
1409         }
1410
1411         if (low < 0) {
1412             return 0;
1413         } else {
1414             return low;
1415         }
1416     }
1417
1418     /**
1419      * Get the character offset on the specified line whose position is
1420      * closest to the specified horizontal position.
1421      */
1422     public int getOffsetForHorizontal(int line, float horiz) {
1423         return getOffsetForHorizontal(line, horiz, true);
1424     }
1425
1426     /**
1427      * Get the character offset on the specified line whose position is
1428      * closest to the specified horizontal position.
1429      *
1430      * @param line the line used to find the closest offset
1431      * @param horiz the horizontal position used to find the closest offset
1432      * @param primary whether to use the primary position or secondary position to find the offset
1433      *
1434      * @hide
1435      */
1436     public int getOffsetForHorizontal(int line, float horiz, boolean primary) {
1437         // TODO: use Paint.getOffsetForAdvance to avoid binary search
1438         final int lineEndOffset = getLineEnd(line);
1439         final int lineStartOffset = getLineStart(line);
1440
1441         Directions dirs = getLineDirections(line);
1442
1443         TextLine tl = TextLine.obtain();
1444         // XXX: we don't care about tabs as we just use TextLine#getOffsetToLeftRightOf here.
1445         tl.set(mPaint, mText, lineStartOffset, lineEndOffset, getParagraphDirection(line), dirs,
1446                 false, null);
1447         final HorizontalMeasurementProvider horizontal =
1448                 new HorizontalMeasurementProvider(line, primary);
1449
1450         final int max;
1451         if (line == getLineCount() - 1) {
1452             max = lineEndOffset;
1453         } else {
1454             max = tl.getOffsetToLeftRightOf(lineEndOffset - lineStartOffset,
1455                     !isRtlCharAt(lineEndOffset - 1)) + lineStartOffset;
1456         }
1457         int best = lineStartOffset;
1458         float bestdist = Math.abs(horizontal.get(lineStartOffset) - horiz);
1459
1460         for (int i = 0; i < dirs.mDirections.length; i += 2) {
1461             int here = lineStartOffset + dirs.mDirections[i];
1462             int there = here + (dirs.mDirections[i+1] & RUN_LENGTH_MASK);
1463             boolean isRtl = (dirs.mDirections[i+1] & RUN_RTL_FLAG) != 0;
1464             int swap = isRtl ? -1 : 1;
1465
1466             if (there > max)
1467                 there = max;
1468             int high = there - 1 + 1, low = here + 1 - 1, guess;
1469
1470             while (high - low > 1) {
1471                 guess = (high + low) / 2;
1472                 int adguess = getOffsetAtStartOf(guess);
1473
1474                 if (horizontal.get(adguess) * swap >= horiz * swap) {
1475                     high = guess;
1476                 } else {
1477                     low = guess;
1478                 }
1479             }
1480
1481             if (low < here + 1)
1482                 low = here + 1;
1483
1484             if (low < there) {
1485                 int aft = tl.getOffsetToLeftRightOf(low - lineStartOffset, isRtl) + lineStartOffset;
1486                 low = tl.getOffsetToLeftRightOf(aft - lineStartOffset, !isRtl) + lineStartOffset;
1487                 if (low >= here && low < there) {
1488                     float dist = Math.abs(horizontal.get(low) - horiz);
1489                     if (aft < there) {
1490                         float other = Math.abs(horizontal.get(aft) - horiz);
1491
1492                         if (other < dist) {
1493                             dist = other;
1494                             low = aft;
1495                         }
1496                     }
1497
1498                     if (dist < bestdist) {
1499                         bestdist = dist;
1500                         best = low;
1501                     }
1502                 }
1503             }
1504
1505             float dist = Math.abs(horizontal.get(here) - horiz);
1506
1507             if (dist < bestdist) {
1508                 bestdist = dist;
1509                 best = here;
1510             }
1511         }
1512
1513         float dist = Math.abs(horizontal.get(max) - horiz);
1514
1515         if (dist <= bestdist) {
1516             bestdist = dist;
1517             best = max;
1518         }
1519
1520         TextLine.recycle(tl);
1521         return best;
1522     }
1523
1524     /**
1525      * Responds to #getHorizontal queries, by selecting the better strategy between:
1526      * - calling #getHorizontal explicitly for each query
1527      * - precomputing all #getHorizontal measurements, and responding to any query in constant time
1528      * The first strategy is used for LTR-only text, while the second is used for all other cases.
1529      * The class is currently only used in #getOffsetForHorizontal, so reuse with care in other
1530      * contexts.
1531      */
1532     private class HorizontalMeasurementProvider {
1533         private final int mLine;
1534         private final boolean mPrimary;
1535
1536         private float[] mHorizontals;
1537         private int mLineStartOffset;
1538
1539         HorizontalMeasurementProvider(final int line, final boolean primary) {
1540             mLine = line;
1541             mPrimary = primary;
1542             init();
1543         }
1544
1545         private void init() {
1546             final Directions dirs = getLineDirections(mLine);
1547             if (dirs == DIRS_ALL_LEFT_TO_RIGHT) {
1548                 return;
1549             }
1550
1551             mHorizontals = getLineHorizontals(mLine, false, mPrimary);
1552             mLineStartOffset = getLineStart(mLine);
1553         }
1554
1555         float get(final int offset) {
1556             if (mHorizontals == null || offset < mLineStartOffset
1557                     || offset >= mLineStartOffset + mHorizontals.length) {
1558                 return getHorizontal(offset, mPrimary);
1559             } else {
1560                 return mHorizontals[offset - mLineStartOffset];
1561             }
1562         }
1563     }
1564
1565     /**
1566      * Return the text offset after the last character on the specified line.
1567      */
1568     public final int getLineEnd(int line) {
1569         return getLineStart(line + 1);
1570     }
1571
1572     /**
1573      * Return the text offset after the last visible character (so whitespace
1574      * is not counted) on the specified line.
1575      */
1576     public int getLineVisibleEnd(int line) {
1577         return getLineVisibleEnd(line, getLineStart(line), getLineStart(line+1));
1578     }
1579
1580     private int getLineVisibleEnd(int line, int start, int end) {
1581         CharSequence text = mText;
1582         char ch;
1583         if (line == getLineCount() - 1) {
1584             return end;
1585         }
1586
1587         for (; end > start; end--) {
1588             ch = text.charAt(end - 1);
1589
1590             if (ch == '\n') {
1591                 return end - 1;
1592             }
1593
1594             if (!TextLine.isLineEndSpace(ch)) {
1595                 break;
1596             }
1597
1598         }
1599
1600         return end;
1601     }
1602
1603     /**
1604      * Return the vertical position of the bottom of the specified line.
1605      */
1606     public final int getLineBottom(int line) {
1607         return getLineTop(line + 1);
1608     }
1609
1610     /**
1611      * Return the vertical position of the baseline of the specified line.
1612      */
1613     public final int getLineBaseline(int line) {
1614         // getLineTop(line+1) == getLineTop(line)
1615         return getLineTop(line+1) - getLineDescent(line);
1616     }
1617
1618     /**
1619      * Get the ascent of the text on the specified line.
1620      * The return value is negative to match the Paint.ascent() convention.
1621      */
1622     public final int getLineAscent(int line) {
1623         // getLineTop(line+1) - getLineDescent(line) == getLineBaseLine(line)
1624         return getLineTop(line) - (getLineTop(line+1) - getLineDescent(line));
1625     }
1626
1627     public int getOffsetToLeftOf(int offset) {
1628         return getOffsetToLeftRightOf(offset, true);
1629     }
1630
1631     public int getOffsetToRightOf(int offset) {
1632         return getOffsetToLeftRightOf(offset, false);
1633     }
1634
1635     private int getOffsetToLeftRightOf(int caret, boolean toLeft) {
1636         int line = getLineForOffset(caret);
1637         int lineStart = getLineStart(line);
1638         int lineEnd = getLineEnd(line);
1639         int lineDir = getParagraphDirection(line);
1640
1641         boolean lineChanged = false;
1642         boolean advance = toLeft == (lineDir == DIR_RIGHT_TO_LEFT);
1643         // if walking off line, look at the line we're headed to
1644         if (advance) {
1645             if (caret == lineEnd) {
1646                 if (line < getLineCount() - 1) {
1647                     lineChanged = true;
1648                     ++line;
1649                 } else {
1650                     return caret; // at very end, don't move
1651                 }
1652             }
1653         } else {
1654             if (caret == lineStart) {
1655                 if (line > 0) {
1656                     lineChanged = true;
1657                     --line;
1658                 } else {
1659                     return caret; // at very start, don't move
1660                 }
1661             }
1662         }
1663
1664         if (lineChanged) {
1665             lineStart = getLineStart(line);
1666             lineEnd = getLineEnd(line);
1667             int newDir = getParagraphDirection(line);
1668             if (newDir != lineDir) {
1669                 // unusual case.  we want to walk onto the line, but it runs
1670                 // in a different direction than this one, so we fake movement
1671                 // in the opposite direction.
1672                 toLeft = !toLeft;
1673                 lineDir = newDir;
1674             }
1675         }
1676
1677         Directions directions = getLineDirections(line);
1678
1679         TextLine tl = TextLine.obtain();
1680         // XXX: we don't care about tabs
1681         tl.set(mPaint, mText, lineStart, lineEnd, lineDir, directions, false, null);
1682         caret = lineStart + tl.getOffsetToLeftRightOf(caret - lineStart, toLeft);
1683         tl = TextLine.recycle(tl);
1684         return caret;
1685     }
1686
1687     private int getOffsetAtStartOf(int offset) {
1688         // XXX this probably should skip local reorderings and
1689         // zero-width characters, look at callers
1690         if (offset == 0)
1691             return 0;
1692
1693         CharSequence text = mText;
1694         char c = text.charAt(offset);
1695
1696         if (c >= '\uDC00' && c <= '\uDFFF') {
1697             char c1 = text.charAt(offset - 1);
1698
1699             if (c1 >= '\uD800' && c1 <= '\uDBFF')
1700                 offset -= 1;
1701         }
1702
1703         if (mSpannedText) {
1704             ReplacementSpan[] spans = ((Spanned) text).getSpans(offset, offset,
1705                                                        ReplacementSpan.class);
1706
1707             for (int i = 0; i < spans.length; i++) {
1708                 int start = ((Spanned) text).getSpanStart(spans[i]);
1709                 int end = ((Spanned) text).getSpanEnd(spans[i]);
1710
1711                 if (start < offset && end > offset)
1712                     offset = start;
1713             }
1714         }
1715
1716         return offset;
1717     }
1718
1719     /**
1720      * Determine whether we should clamp cursor position. Currently it's
1721      * only robust for left-aligned displays.
1722      * @hide
1723      */
1724     public boolean shouldClampCursor(int line) {
1725         // Only clamp cursor position in left-aligned displays.
1726         switch (getParagraphAlignment(line)) {
1727             case ALIGN_LEFT:
1728                 return true;
1729             case ALIGN_NORMAL:
1730                 return getParagraphDirection(line) > 0;
1731             default:
1732                 return false;
1733         }
1734
1735     }
1736     /**
1737      * Fills in the specified Path with a representation of a cursor
1738      * at the specified offset.  This will often be a vertical line
1739      * but can be multiple discontinuous lines in text with multiple
1740      * directionalities.
1741      */
1742     public void getCursorPath(int point, Path dest,
1743                               CharSequence editingBuffer) {
1744         dest.reset();
1745
1746         int line = getLineForOffset(point);
1747         int top = getLineTop(line);
1748         int bottom = getLineTop(line+1);
1749
1750         boolean clamped = shouldClampCursor(line);
1751         float h1 = getPrimaryHorizontal(point, clamped) - 0.5f;
1752         float h2 = isLevelBoundary(point) ? getSecondaryHorizontal(point, clamped) - 0.5f : h1;
1753
1754         int caps = TextKeyListener.getMetaState(editingBuffer, TextKeyListener.META_SHIFT_ON) |
1755                    TextKeyListener.getMetaState(editingBuffer, TextKeyListener.META_SELECTING);
1756         int fn = TextKeyListener.getMetaState(editingBuffer, TextKeyListener.META_ALT_ON);
1757         int dist = 0;
1758
1759         if (caps != 0 || fn != 0) {
1760             dist = (bottom - top) >> 2;
1761
1762             if (fn != 0)
1763                 top += dist;
1764             if (caps != 0)
1765                 bottom -= dist;
1766         }
1767
1768         if (h1 < 0.5f)
1769             h1 = 0.5f;
1770         if (h2 < 0.5f)
1771             h2 = 0.5f;
1772
1773         if (Float.compare(h1, h2) == 0) {
1774             dest.moveTo(h1, top);
1775             dest.lineTo(h1, bottom);
1776         } else {
1777             dest.moveTo(h1, top);
1778             dest.lineTo(h1, (top + bottom) >> 1);
1779
1780             dest.moveTo(h2, (top + bottom) >> 1);
1781             dest.lineTo(h2, bottom);
1782         }
1783
1784         if (caps == 2) {
1785             dest.moveTo(h2, bottom);
1786             dest.lineTo(h2 - dist, bottom + dist);
1787             dest.lineTo(h2, bottom);
1788             dest.lineTo(h2 + dist, bottom + dist);
1789         } else if (caps == 1) {
1790             dest.moveTo(h2, bottom);
1791             dest.lineTo(h2 - dist, bottom + dist);
1792
1793             dest.moveTo(h2 - dist, bottom + dist - 0.5f);
1794             dest.lineTo(h2 + dist, bottom + dist - 0.5f);
1795
1796             dest.moveTo(h2 + dist, bottom + dist);
1797             dest.lineTo(h2, bottom);
1798         }
1799
1800         if (fn == 2) {
1801             dest.moveTo(h1, top);
1802             dest.lineTo(h1 - dist, top - dist);
1803             dest.lineTo(h1, top);
1804             dest.lineTo(h1 + dist, top - dist);
1805         } else if (fn == 1) {
1806             dest.moveTo(h1, top);
1807             dest.lineTo(h1 - dist, top - dist);
1808
1809             dest.moveTo(h1 - dist, top - dist + 0.5f);
1810             dest.lineTo(h1 + dist, top - dist + 0.5f);
1811
1812             dest.moveTo(h1 + dist, top - dist);
1813             dest.lineTo(h1, top);
1814         }
1815     }
1816
1817     private void addSelection(int line, int start, int end,
1818                               int top, int bottom, Path dest) {
1819         int linestart = getLineStart(line);
1820         int lineend = getLineEnd(line);
1821         Directions dirs = getLineDirections(line);
1822
1823         if (lineend > linestart && mText.charAt(lineend - 1) == '\n')
1824             lineend--;
1825
1826         for (int i = 0; i < dirs.mDirections.length; i += 2) {
1827             int here = linestart + dirs.mDirections[i];
1828             int there = here + (dirs.mDirections[i+1] & RUN_LENGTH_MASK);
1829
1830             if (there > lineend)
1831                 there = lineend;
1832
1833             if (start <= there && end >= here) {
1834                 int st = Math.max(start, here);
1835                 int en = Math.min(end, there);
1836
1837                 if (st != en) {
1838                     float h1 = getHorizontal(st, false, line, false /* not clamped */);
1839                     float h2 = getHorizontal(en, true, line, false /* not clamped */);
1840
1841                     float left = Math.min(h1, h2);
1842                     float right = Math.max(h1, h2);
1843
1844                     dest.addRect(left, top, right, bottom, Path.Direction.CW);
1845                 }
1846             }
1847         }
1848     }
1849
1850     /**
1851      * Fills in the specified Path with a representation of a highlight
1852      * between the specified offsets.  This will often be a rectangle
1853      * or a potentially discontinuous set of rectangles.  If the start
1854      * and end are the same, the returned path is empty.
1855      */
1856     public void getSelectionPath(int start, int end, Path dest) {
1857         dest.reset();
1858
1859         if (start == end)
1860             return;
1861
1862         if (end < start) {
1863             int temp = end;
1864             end = start;
1865             start = temp;
1866         }
1867
1868         int startline = getLineForOffset(start);
1869         int endline = getLineForOffset(end);
1870
1871         int top = getLineTop(startline);
1872         int bottom = getLineBottom(endline);
1873
1874         if (startline == endline) {
1875             addSelection(startline, start, end, top, bottom, dest);
1876         } else {
1877             final float width = mWidth;
1878
1879             addSelection(startline, start, getLineEnd(startline),
1880                          top, getLineBottom(startline), dest);
1881
1882             if (getParagraphDirection(startline) == DIR_RIGHT_TO_LEFT)
1883                 dest.addRect(getLineLeft(startline), top,
1884                               0, getLineBottom(startline), Path.Direction.CW);
1885             else
1886                 dest.addRect(getLineRight(startline), top,
1887                               width, getLineBottom(startline), Path.Direction.CW);
1888
1889             for (int i = startline + 1; i < endline; i++) {
1890                 top = getLineTop(i);
1891                 bottom = getLineBottom(i);
1892                 dest.addRect(0, top, width, bottom, Path.Direction.CW);
1893             }
1894
1895             top = getLineTop(endline);
1896             bottom = getLineBottom(endline);
1897
1898             addSelection(endline, getLineStart(endline), end,
1899                          top, bottom, dest);
1900
1901             if (getParagraphDirection(endline) == DIR_RIGHT_TO_LEFT)
1902                 dest.addRect(width, top, getLineRight(endline), bottom, Path.Direction.CW);
1903             else
1904                 dest.addRect(0, top, getLineLeft(endline), bottom, Path.Direction.CW);
1905         }
1906     }
1907
1908     /**
1909      * Get the alignment of the specified paragraph, taking into account
1910      * markup attached to it.
1911      */
1912     public final Alignment getParagraphAlignment(int line) {
1913         Alignment align = mAlignment;
1914
1915         if (mSpannedText) {
1916             Spanned sp = (Spanned) mText;
1917             AlignmentSpan[] spans = getParagraphSpans(sp, getLineStart(line),
1918                                                 getLineEnd(line),
1919                                                 AlignmentSpan.class);
1920
1921             int spanLength = spans.length;
1922             if (spanLength > 0) {
1923                 align = spans[spanLength-1].getAlignment();
1924             }
1925         }
1926
1927         return align;
1928     }
1929
1930     /**
1931      * Get the left edge of the specified paragraph, inset by left margins.
1932      */
1933     public final int getParagraphLeft(int line) {
1934         int left = 0;
1935         int dir = getParagraphDirection(line);
1936         if (dir == DIR_RIGHT_TO_LEFT || !mSpannedText) {
1937             return left; // leading margin has no impact, or no styles
1938         }
1939         return getParagraphLeadingMargin(line);
1940     }
1941
1942     /**
1943      * Get the right edge of the specified paragraph, inset by right margins.
1944      */
1945     public final int getParagraphRight(int line) {
1946         int right = mWidth;
1947         int dir = getParagraphDirection(line);
1948         if (dir == DIR_LEFT_TO_RIGHT || !mSpannedText) {
1949             return right; // leading margin has no impact, or no styles
1950         }
1951         return right - getParagraphLeadingMargin(line);
1952     }
1953
1954     /**
1955      * Returns the effective leading margin (unsigned) for this line,
1956      * taking into account LeadingMarginSpan and LeadingMarginSpan2.
1957      * @param line the line index
1958      * @return the leading margin of this line
1959      */
1960     private int getParagraphLeadingMargin(int line) {
1961         if (!mSpannedText) {
1962             return 0;
1963         }
1964         Spanned spanned = (Spanned) mText;
1965
1966         int lineStart = getLineStart(line);
1967         int lineEnd = getLineEnd(line);
1968         int spanEnd = spanned.nextSpanTransition(lineStart, lineEnd,
1969                 LeadingMarginSpan.class);
1970         LeadingMarginSpan[] spans = getParagraphSpans(spanned, lineStart, spanEnd,
1971                                                 LeadingMarginSpan.class);
1972         if (spans.length == 0) {
1973             return 0; // no leading margin span;
1974         }
1975
1976         int margin = 0;
1977
1978         boolean isFirstParaLine = lineStart == 0 ||
1979             spanned.charAt(lineStart - 1) == '\n';
1980
1981         boolean useFirstLineMargin = isFirstParaLine;
1982         for (int i = 0; i < spans.length; i++) {
1983             if (spans[i] instanceof LeadingMarginSpan2) {
1984                 int spStart = spanned.getSpanStart(spans[i]);
1985                 int spanLine = getLineForOffset(spStart);
1986                 int count = ((LeadingMarginSpan2) spans[i]).getLeadingMarginLineCount();
1987                 // if there is more than one LeadingMarginSpan2, use the count that is greatest
1988                 useFirstLineMargin |= line < spanLine + count;
1989             }
1990         }
1991         for (int i = 0; i < spans.length; i++) {
1992             LeadingMarginSpan span = spans[i];
1993             margin += span.getLeadingMargin(useFirstLineMargin);
1994         }
1995
1996         return margin;
1997     }
1998
1999     /* package */
2000     static float measurePara(TextPaint paint, CharSequence text, int start, int end,
2001             TextDirectionHeuristic textDir) {
2002         MeasuredText mt = MeasuredText.obtain();
2003         TextLine tl = TextLine.obtain();
2004         try {
2005             mt.setPara(text, start, end, textDir, null);
2006             Directions directions;
2007             int dir;
2008             if (mt.mEasy) {
2009                 directions = DIRS_ALL_LEFT_TO_RIGHT;
2010                 dir = Layout.DIR_LEFT_TO_RIGHT;
2011             } else {
2012                 directions = AndroidBidi.directions(mt.mDir, mt.mLevels,
2013                     0, mt.mChars, 0, mt.mLen);
2014                 dir = mt.mDir;
2015             }
2016             char[] chars = mt.mChars;
2017             int len = mt.mLen;
2018             boolean hasTabs = false;
2019             TabStops tabStops = null;
2020             // leading margins should be taken into account when measuring a paragraph
2021             int margin = 0;
2022             if (text instanceof Spanned) {
2023                 Spanned spanned = (Spanned) text;
2024                 LeadingMarginSpan[] spans = getParagraphSpans(spanned, start, end,
2025                         LeadingMarginSpan.class);
2026                 for (LeadingMarginSpan lms : spans) {
2027                     margin += lms.getLeadingMargin(true);
2028                 }
2029             }
2030             for (int i = 0; i < len; ++i) {
2031                 if (chars[i] == '\t') {
2032                     hasTabs = true;
2033                     if (text instanceof Spanned) {
2034                         Spanned spanned = (Spanned) text;
2035                         int spanEnd = spanned.nextSpanTransition(start, end,
2036                                 TabStopSpan.class);
2037                         TabStopSpan[] spans = getParagraphSpans(spanned, start, spanEnd,
2038                                 TabStopSpan.class);
2039                         if (spans.length > 0) {
2040                             tabStops = new TabStops(TAB_INCREMENT, spans);
2041                         }
2042                     }
2043                     break;
2044                 }
2045             }
2046             tl.set(paint, text, start, end, dir, directions, hasTabs, tabStops);
2047             return margin + Math.abs(tl.metrics(null));
2048         } finally {
2049             TextLine.recycle(tl);
2050             MeasuredText.recycle(mt);
2051         }
2052     }
2053
2054     /**
2055      * @hide
2056      */
2057     /* package */ static class TabStops {
2058         private int[] mStops;
2059         private int mNumStops;
2060         private int mIncrement;
2061
2062         TabStops(int increment, Object[] spans) {
2063             reset(increment, spans);
2064         }
2065
2066         void reset(int increment, Object[] spans) {
2067             this.mIncrement = increment;
2068
2069             int ns = 0;
2070             if (spans != null) {
2071                 int[] stops = this.mStops;
2072                 for (Object o : spans) {
2073                     if (o instanceof TabStopSpan) {
2074                         if (stops == null) {
2075                             stops = new int[10];
2076                         } else if (ns == stops.length) {
2077                             int[] nstops = new int[ns * 2];
2078                             for (int i = 0; i < ns; ++i) {
2079                                 nstops[i] = stops[i];
2080                             }
2081                             stops = nstops;
2082                         }
2083                         stops[ns++] = ((TabStopSpan) o).getTabStop();
2084                     }
2085                 }
2086                 if (ns > 1) {
2087                     Arrays.sort(stops, 0, ns);
2088                 }
2089                 if (stops != this.mStops) {
2090                     this.mStops = stops;
2091                 }
2092             }
2093             this.mNumStops = ns;
2094         }
2095
2096         float nextTab(float h) {
2097             int ns = this.mNumStops;
2098             if (ns > 0) {
2099                 int[] stops = this.mStops;
2100                 for (int i = 0; i < ns; ++i) {
2101                     int stop = stops[i];
2102                     if (stop > h) {
2103                         return stop;
2104                     }
2105                 }
2106             }
2107             return nextDefaultStop(h, mIncrement);
2108         }
2109
2110         public static float nextDefaultStop(float h, int inc) {
2111             return ((int) ((h + inc) / inc)) * inc;
2112         }
2113     }
2114
2115     /**
2116      * Returns the position of the next tab stop after h on the line.
2117      *
2118      * @param text the text
2119      * @param start start of the line
2120      * @param end limit of the line
2121      * @param h the current horizontal offset
2122      * @param tabs the tabs, can be null.  If it is null, any tabs in effect
2123      * on the line will be used.  If there are no tabs, a default offset
2124      * will be used to compute the tab stop.
2125      * @return the offset of the next tab stop.
2126      */
2127     /* package */ static float nextTab(CharSequence text, int start, int end,
2128                                        float h, Object[] tabs) {
2129         float nh = Float.MAX_VALUE;
2130         boolean alltabs = false;
2131
2132         if (text instanceof Spanned) {
2133             if (tabs == null) {
2134                 tabs = getParagraphSpans((Spanned) text, start, end, TabStopSpan.class);
2135                 alltabs = true;
2136             }
2137
2138             for (int i = 0; i < tabs.length; i++) {
2139                 if (!alltabs) {
2140                     if (!(tabs[i] instanceof TabStopSpan))
2141                         continue;
2142                 }
2143
2144                 int where = ((TabStopSpan) tabs[i]).getTabStop();
2145
2146                 if (where < nh && where > h)
2147                     nh = where;
2148             }
2149
2150             if (nh != Float.MAX_VALUE)
2151                 return nh;
2152         }
2153
2154         return ((int) ((h + TAB_INCREMENT) / TAB_INCREMENT)) * TAB_INCREMENT;
2155     }
2156
2157     protected final boolean isSpanned() {
2158         return mSpannedText;
2159     }
2160
2161     /**
2162      * Returns the same as <code>text.getSpans()</code>, except where
2163      * <code>start</code> and <code>end</code> are the same and are not
2164      * at the very beginning of the text, in which case an empty array
2165      * is returned instead.
2166      * <p>
2167      * This is needed because of the special case that <code>getSpans()</code>
2168      * on an empty range returns the spans adjacent to that range, which is
2169      * primarily for the sake of <code>TextWatchers</code> so they will get
2170      * notifications when text goes from empty to non-empty.  But it also
2171      * has the unfortunate side effect that if the text ends with an empty
2172      * paragraph, that paragraph accidentally picks up the styles of the
2173      * preceding paragraph (even though those styles will not be picked up
2174      * by new text that is inserted into the empty paragraph).
2175      * <p>
2176      * The reason it just checks whether <code>start</code> and <code>end</code>
2177      * is the same is that the only time a line can contain 0 characters
2178      * is if it is the final paragraph of the Layout; otherwise any line will
2179      * contain at least one printing or newline character.  The reason for the
2180      * additional check if <code>start</code> is greater than 0 is that
2181      * if the empty paragraph is the entire content of the buffer, paragraph
2182      * styles that are already applied to the buffer will apply to text that
2183      * is inserted into it.
2184      */
2185     /* package */static <T> T[] getParagraphSpans(Spanned text, int start, int end, Class<T> type) {
2186         if (start == end && start > 0) {
2187             return ArrayUtils.emptyArray(type);
2188         }
2189
2190         if(text instanceof SpannableStringBuilder) {
2191             return ((SpannableStringBuilder) text).getSpans(start, end, type, false);
2192         } else {
2193             return text.getSpans(start, end, type);
2194         }
2195     }
2196
2197     private char getEllipsisChar(TextUtils.TruncateAt method) {
2198         return (method == TextUtils.TruncateAt.END_SMALL) ?
2199                 TextUtils.ELLIPSIS_TWO_DOTS[0] :
2200                 TextUtils.ELLIPSIS_NORMAL[0];
2201     }
2202
2203     private void ellipsize(int start, int end, int line,
2204                            char[] dest, int destoff, TextUtils.TruncateAt method) {
2205         int ellipsisCount = getEllipsisCount(line);
2206
2207         if (ellipsisCount == 0) {
2208             return;
2209         }
2210
2211         int ellipsisStart = getEllipsisStart(line);
2212         int linestart = getLineStart(line);
2213
2214         for (int i = ellipsisStart; i < ellipsisStart + ellipsisCount; i++) {
2215             char c;
2216
2217             if (i == ellipsisStart) {
2218                 c = getEllipsisChar(method); // ellipsis
2219             } else {
2220                 c = '\uFEFF'; // 0-width space
2221             }
2222
2223             int a = i + linestart;
2224
2225             if (a >= start && a < end) {
2226                 dest[destoff + a - start] = c;
2227             }
2228         }
2229     }
2230
2231     /**
2232      * Stores information about bidirectional (left-to-right or right-to-left)
2233      * text within the layout of a line.
2234      */
2235     public static class Directions {
2236         // Directions represents directional runs within a line of text.
2237         // Runs are pairs of ints listed in visual order, starting from the
2238         // leading margin.  The first int of each pair is the offset from
2239         // the first character of the line to the start of the run.  The
2240         // second int represents both the length and level of the run.
2241         // The length is in the lower bits, accessed by masking with
2242         // DIR_LENGTH_MASK.  The level is in the higher bits, accessed
2243         // by shifting by DIR_LEVEL_SHIFT and masking by DIR_LEVEL_MASK.
2244         // To simply test for an RTL direction, test the bit using
2245         // DIR_RTL_FLAG, if set then the direction is rtl.
2246
2247         /**
2248          * @hide
2249          */
2250         @VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE)
2251         public int[] mDirections;
2252
2253         /**
2254          * @hide
2255          */
2256         @VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE)
2257         public Directions(int[] dirs) {
2258             mDirections = dirs;
2259         }
2260     }
2261
2262     /**
2263      * Return the offset of the first character to be ellipsized away,
2264      * relative to the start of the line.  (So 0 if the beginning of the
2265      * line is ellipsized, not getLineStart().)
2266      */
2267     public abstract int getEllipsisStart(int line);
2268
2269     /**
2270      * Returns the number of characters to be ellipsized away, or 0 if
2271      * no ellipsis is to take place.
2272      */
2273     public abstract int getEllipsisCount(int line);
2274
2275     /* package */ static class Ellipsizer implements CharSequence, GetChars {
2276         /* package */ CharSequence mText;
2277         /* package */ Layout mLayout;
2278         /* package */ int mWidth;
2279         /* package */ TextUtils.TruncateAt mMethod;
2280
2281         public Ellipsizer(CharSequence s) {
2282             mText = s;
2283         }
2284
2285         public char charAt(int off) {
2286             char[] buf = TextUtils.obtain(1);
2287             getChars(off, off + 1, buf, 0);
2288             char ret = buf[0];
2289
2290             TextUtils.recycle(buf);
2291             return ret;
2292         }
2293
2294         public void getChars(int start, int end, char[] dest, int destoff) {
2295             int line1 = mLayout.getLineForOffset(start);
2296             int line2 = mLayout.getLineForOffset(end);
2297
2298             TextUtils.getChars(mText, start, end, dest, destoff);
2299
2300             for (int i = line1; i <= line2; i++) {
2301                 mLayout.ellipsize(start, end, i, dest, destoff, mMethod);
2302             }
2303         }
2304
2305         public int length() {
2306             return mText.length();
2307         }
2308
2309         public CharSequence subSequence(int start, int end) {
2310             char[] s = new char[end - start];
2311             getChars(start, end, s, 0);
2312             return new String(s);
2313         }
2314
2315         @Override
2316         public String toString() {
2317             char[] s = new char[length()];
2318             getChars(0, length(), s, 0);
2319             return new String(s);
2320         }
2321
2322     }
2323
2324     /* package */ static class SpannedEllipsizer extends Ellipsizer implements Spanned {
2325         private Spanned mSpanned;
2326
2327         public SpannedEllipsizer(CharSequence display) {
2328             super(display);
2329             mSpanned = (Spanned) display;
2330         }
2331
2332         public <T> T[] getSpans(int start, int end, Class<T> type) {
2333             return mSpanned.getSpans(start, end, type);
2334         }
2335
2336         public int getSpanStart(Object tag) {
2337             return mSpanned.getSpanStart(tag);
2338         }
2339
2340         public int getSpanEnd(Object tag) {
2341             return mSpanned.getSpanEnd(tag);
2342         }
2343
2344         public int getSpanFlags(Object tag) {
2345             return mSpanned.getSpanFlags(tag);
2346         }
2347
2348         @SuppressWarnings("rawtypes")
2349         public int nextSpanTransition(int start, int limit, Class type) {
2350             return mSpanned.nextSpanTransition(start, limit, type);
2351         }
2352
2353         @Override
2354         public CharSequence subSequence(int start, int end) {
2355             char[] s = new char[end - start];
2356             getChars(start, end, s, 0);
2357
2358             SpannableString ss = new SpannableString(new String(s));
2359             TextUtils.copySpansFrom(mSpanned, start, end, Object.class, ss, 0);
2360             return ss;
2361         }
2362     }
2363
2364     private CharSequence mText;
2365     private TextPaint mPaint;
2366     private int mWidth;
2367     private Alignment mAlignment = Alignment.ALIGN_NORMAL;
2368     private float mSpacingMult;
2369     private float mSpacingAdd;
2370     private static final Rect sTempRect = new Rect();
2371     private boolean mSpannedText;
2372     private TextDirectionHeuristic mTextDir;
2373     private SpanSet<LineBackgroundSpan> mLineBackgroundSpans;
2374     private int mJustificationMode;
2375
2376     public static final int DIR_LEFT_TO_RIGHT = 1;
2377     public static final int DIR_RIGHT_TO_LEFT = -1;
2378
2379     /* package */ static final int DIR_REQUEST_LTR = 1;
2380     /* package */ static final int DIR_REQUEST_RTL = -1;
2381     /* package */ static final int DIR_REQUEST_DEFAULT_LTR = 2;
2382     /* package */ static final int DIR_REQUEST_DEFAULT_RTL = -2;
2383
2384     /* package */ static final int RUN_LENGTH_MASK = 0x03ffffff;
2385     /* package */ static final int RUN_LEVEL_SHIFT = 26;
2386     /* package */ static final int RUN_LEVEL_MASK = 0x3f;
2387     /* package */ static final int RUN_RTL_FLAG = 1 << RUN_LEVEL_SHIFT;
2388
2389     public enum Alignment {
2390         ALIGN_NORMAL,
2391         ALIGN_OPPOSITE,
2392         ALIGN_CENTER,
2393         /** @hide */
2394         ALIGN_LEFT,
2395         /** @hide */
2396         ALIGN_RIGHT,
2397     }
2398
2399     private static final int TAB_INCREMENT = 20;
2400
2401     /** @hide */
2402     @VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE)
2403     public static final Directions DIRS_ALL_LEFT_TO_RIGHT =
2404         new Directions(new int[] { 0, RUN_LENGTH_MASK });
2405
2406     /** @hide */
2407     @VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE)
2408     public static final Directions DIRS_ALL_RIGHT_TO_LEFT =
2409         new Directions(new int[] { 0, RUN_LENGTH_MASK | RUN_RTL_FLAG });
2410
2411 }