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 17package android.text; 18 19import android.annotation.Nullable; 20import android.graphics.BaseCanvas; 21import android.graphics.Paint; 22import android.util.Log; 23 24import com.android.internal.annotations.GuardedBy; 25import com.android.internal.util.ArrayUtils; 26import com.android.internal.util.GrowingArrayUtils; 27 28import libcore.util.EmptyArray; 29 30import java.lang.reflect.Array; 31import java.util.IdentityHashMap; 32 33/** 34 * This is the class for text whose content and markup can both be changed. 35 */ 36public class SpannableStringBuilder implements CharSequence, GetChars, Spannable, Editable, 37 Appendable, GraphicsOperations { 38 private final static String TAG = "SpannableStringBuilder"; 39 /** 40 * Create a new SpannableStringBuilder with empty contents 41 */ 42 public SpannableStringBuilder() { 43 this(""); 44 } 45 46 /** 47 * Create a new SpannableStringBuilder containing a copy of the 48 * specified text, including its spans if any. 49 */ 50 public SpannableStringBuilder(CharSequence text) { 51 this(text, 0, text.length()); 52 } 53 54 /** 55 * Create a new SpannableStringBuilder containing a copy of the 56 * specified slice of the specified text, including its spans if any. 57 */ 58 public SpannableStringBuilder(CharSequence text, int start, int end) { 59 int srclen = end - start; 60 61 if (srclen < 0) throw new StringIndexOutOfBoundsException(); 62 63 mText = ArrayUtils.newUnpaddedCharArray(GrowingArrayUtils.growSize(srclen)); 64 mGapStart = srclen; 65 mGapLength = mText.length - srclen; 66 67 TextUtils.getChars(text, start, end, mText, 0); 68 69 mSpanCount = 0; 70 mSpanInsertCount = 0; 71 mSpans = EmptyArray.OBJECT; 72 mSpanStarts = EmptyArray.INT; 73 mSpanEnds = EmptyArray.INT; 74 mSpanFlags = EmptyArray.INT; 75 mSpanMax = EmptyArray.INT; 76 mSpanOrder = EmptyArray.INT; 77 78 if (text instanceof Spanned) { 79 Spanned sp = (Spanned) text; 80 Object[] spans = sp.getSpans(start, end, Object.class); 81 82 for (int i = 0; i < spans.length; i++) { 83 if (spans[i] instanceof NoCopySpan) { 84 continue; 85 } 86 87 int st = sp.getSpanStart(spans[i]) - start; 88 int en = sp.getSpanEnd(spans[i]) - start; 89 int fl = sp.getSpanFlags(spans[i]); 90 91 if (st < 0) 92 st = 0; 93 if (st > end - start) 94 st = end - start; 95 96 if (en < 0) 97 en = 0; 98 if (en > end - start) 99 en = end - start; 100 101 setSpan(false, spans[i], st, en, fl, false/*enforceParagraph*/); 102 } 103 restoreInvariants(); 104 } 105 } 106 107 public static SpannableStringBuilder valueOf(CharSequence source) { 108 if (source instanceof SpannableStringBuilder) { 109 return (SpannableStringBuilder) source; 110 } else { 111 return new SpannableStringBuilder(source); 112 } 113 } 114 115 /** 116 * Return the char at the specified offset within the buffer. 117 */ 118 public char charAt(int where) { 119 int len = length(); 120 if (where < 0) { 121 throw new IndexOutOfBoundsException("charAt: " + where + " < 0"); 122 } else if (where >= len) { 123 throw new IndexOutOfBoundsException("charAt: " + where + " >= length " + len); 124 } 125 126 if (where >= mGapStart) 127 return mText[where + mGapLength]; 128 else 129 return mText[where]; 130 } 131 132 /** 133 * Return the number of chars in the buffer. 134 */ 135 public int length() { 136 return mText.length - mGapLength; 137 } 138 139 private void resizeFor(int size) { 140 final int oldLength = mText.length; 141 if (size + 1 <= oldLength) { 142 return; 143 } 144 145 char[] newText = ArrayUtils.newUnpaddedCharArray(GrowingArrayUtils.growSize(size)); 146 System.arraycopy(mText, 0, newText, 0, mGapStart); 147 final int newLength = newText.length; 148 final int delta = newLength - oldLength; 149 final int after = oldLength - (mGapStart + mGapLength); 150 System.arraycopy(mText, oldLength - after, newText, newLength - after, after); 151 mText = newText; 152 153 mGapLength += delta; 154 if (mGapLength < 1) 155 new Exception("mGapLength < 1").printStackTrace(); 156 157 if (mSpanCount != 0) { 158 for (int i = 0; i < mSpanCount; i++) { 159 if (mSpanStarts[i] > mGapStart) mSpanStarts[i] += delta; 160 if (mSpanEnds[i] > mGapStart) mSpanEnds[i] += delta; 161 } 162 calcMax(treeRoot()); 163 } 164 } 165 166 private void moveGapTo(int where) { 167 if (where == mGapStart) 168 return; 169 170 boolean atEnd = (where == length()); 171 172 if (where < mGapStart) { 173 int overlap = mGapStart - where; 174 System.arraycopy(mText, where, mText, mGapStart + mGapLength - overlap, overlap); 175 } else /* where > mGapStart */ { 176 int overlap = where - mGapStart; 177 System.arraycopy(mText, where + mGapLength - overlap, mText, mGapStart, overlap); 178 } 179 180 // TODO: be more clever (although the win really isn't that big) 181 if (mSpanCount != 0) { 182 for (int i = 0; i < mSpanCount; i++) { 183 int start = mSpanStarts[i]; 184 int end = mSpanEnds[i]; 185 186 if (start > mGapStart) 187 start -= mGapLength; 188 if (start > where) 189 start += mGapLength; 190 else if (start == where) { 191 int flag = (mSpanFlags[i] & START_MASK) >> START_SHIFT; 192 193 if (flag == POINT || (atEnd && flag == PARAGRAPH)) 194 start += mGapLength; 195 } 196 197 if (end > mGapStart) 198 end -= mGapLength; 199 if (end > where) 200 end += mGapLength; 201 else if (end == where) { 202 int flag = (mSpanFlags[i] & END_MASK); 203 204 if (flag == POINT || (atEnd && flag == PARAGRAPH)) 205 end += mGapLength; 206 } 207 208 mSpanStarts[i] = start; 209 mSpanEnds[i] = end; 210 } 211 calcMax(treeRoot()); 212 } 213 214 mGapStart = where; 215 } 216 217 // Documentation from interface 218 public SpannableStringBuilder insert(int where, CharSequence tb, int start, int end) { 219 return replace(where, where, tb, start, end); 220 } 221 222 // Documentation from interface 223 public SpannableStringBuilder insert(int where, CharSequence tb) { 224 return replace(where, where, tb, 0, tb.length()); 225 } 226 227 // Documentation from interface 228 public SpannableStringBuilder delete(int start, int end) { 229 SpannableStringBuilder ret = replace(start, end, "", 0, 0); 230 231 if (mGapLength > 2 * length()) 232 resizeFor(length()); 233 234 return ret; // == this 235 } 236 237 // Documentation from interface 238 public void clear() { 239 replace(0, length(), "", 0, 0); 240 mSpanInsertCount = 0; 241 } 242 243 // Documentation from interface 244 public void clearSpans() { 245 for (int i = mSpanCount - 1; i >= 0; i--) { 246 Object what = mSpans[i]; 247 int ostart = mSpanStarts[i]; 248 int oend = mSpanEnds[i]; 249 250 if (ostart > mGapStart) 251 ostart -= mGapLength; 252 if (oend > mGapStart) 253 oend -= mGapLength; 254 255 mSpanCount = i; 256 mSpans[i] = null; 257 258 sendSpanRemoved(what, ostart, oend); 259 } 260 if (mIndexOfSpan != null) { 261 mIndexOfSpan.clear(); 262 } 263 mSpanInsertCount = 0; 264 } 265 266 // Documentation from interface 267 public SpannableStringBuilder append(CharSequence text) { 268 int length = length(); 269 return replace(length, length, text, 0, text.length()); 270 } 271 272 /** 273 * Appends the character sequence {@code text} and spans {@code what} over the appended part. 274 * See {@link Spanned} for an explanation of what the flags mean. 275 * @param text the character sequence to append. 276 * @param what the object to be spanned over the appended text. 277 * @param flags see {@link Spanned}. 278 * @return this {@code SpannableStringBuilder}. 279 */ 280 public SpannableStringBuilder append(CharSequence text, Object what, int flags) { 281 int start = length(); 282 append(text); 283 setSpan(what, start, length(), flags); 284 return this; 285 } 286 287 // Documentation from interface 288 public SpannableStringBuilder append(CharSequence text, int start, int end) { 289 int length = length(); 290 return replace(length, length, text, start, end); 291 } 292 293 // Documentation from interface 294 public SpannableStringBuilder append(char text) { 295 return append(String.valueOf(text)); 296 } 297 298 // Returns true if a node was removed (so we can restart search from root) 299 private boolean removeSpansForChange(int start, int end, boolean textIsRemoved, int i) { 300 if ((i & 1) != 0) { 301 // internal tree node 302 if (resolveGap(mSpanMax[i]) >= start && 303 removeSpansForChange(start, end, textIsRemoved, leftChild(i))) { 304 return true; 305 } 306 } 307 if (i < mSpanCount) { 308 if ((mSpanFlags[i] & Spanned.SPAN_EXCLUSIVE_EXCLUSIVE) == 309 Spanned.SPAN_EXCLUSIVE_EXCLUSIVE && 310 mSpanStarts[i] >= start && mSpanStarts[i] < mGapStart + mGapLength && 311 mSpanEnds[i] >= start && mSpanEnds[i] < mGapStart + mGapLength && 312 // The following condition indicates that the span would become empty 313 (textIsRemoved || mSpanStarts[i] > start || mSpanEnds[i] < mGapStart)) { 314 mIndexOfSpan.remove(mSpans[i]); 315 removeSpan(i); 316 return true; 317 } 318 return resolveGap(mSpanStarts[i]) <= end && (i & 1) != 0 && 319 removeSpansForChange(start, end, textIsRemoved, rightChild(i)); 320 } 321 return false; 322 } 323 324 private void change(int start, int end, CharSequence cs, int csStart, int csEnd) { 325 // Can be negative 326 final int replacedLength = end - start; 327 final int replacementLength = csEnd - csStart; 328 final int nbNewChars = replacementLength - replacedLength; 329 330 boolean changed = false; 331 for (int i = mSpanCount - 1; i >= 0; i--) { 332 int spanStart = mSpanStarts[i]; 333 if (spanStart > mGapStart) 334 spanStart -= mGapLength; 335 336 int spanEnd = mSpanEnds[i]; 337 if (spanEnd > mGapStart) 338 spanEnd -= mGapLength; 339 340 if ((mSpanFlags[i] & SPAN_PARAGRAPH) == SPAN_PARAGRAPH) { 341 int ost = spanStart; 342 int oen = spanEnd; 343 int clen = length(); 344 345 if (spanStart > start && spanStart <= end) { 346 for (spanStart = end; spanStart < clen; spanStart++) 347 if (spanStart > end && charAt(spanStart - 1) == '\n') 348 break; 349 } 350 351 if (spanEnd > start && spanEnd <= end) { 352 for (spanEnd = end; spanEnd < clen; spanEnd++) 353 if (spanEnd > end && charAt(spanEnd - 1) == '\n') 354 break; 355 } 356 357 if (spanStart != ost || spanEnd != oen) { 358 setSpan(false, mSpans[i], spanStart, spanEnd, mSpanFlags[i], 359 true/*enforceParagraph*/); 360 changed = true; 361 } 362 } 363 364 int flags = 0; 365 if (spanStart == start) flags |= SPAN_START_AT_START; 366 else if (spanStart == end + nbNewChars) flags |= SPAN_START_AT_END; 367 if (spanEnd == start) flags |= SPAN_END_AT_START; 368 else if (spanEnd == end + nbNewChars) flags |= SPAN_END_AT_END; 369 mSpanFlags[i] |= flags; 370 } 371 if (changed) { 372 restoreInvariants(); 373 } 374 375 moveGapTo(end); 376 377 if (nbNewChars >= mGapLength) { 378 resizeFor(mText.length + nbNewChars - mGapLength); 379 } 380 381 final boolean textIsRemoved = replacementLength == 0; 382 // The removal pass needs to be done before the gap is updated in order to broadcast the 383 // correct previous positions to the correct intersecting SpanWatchers 384 if (replacedLength > 0) { // no need for span fixup on pure insertion 385 while (mSpanCount > 0 && 386 removeSpansForChange(start, end, textIsRemoved, treeRoot())) { 387 // keep deleting spans as needed, and restart from root after every deletion 388 // because deletion can invalidate an index. 389 } 390 } 391 392 mGapStart += nbNewChars; 393 mGapLength -= nbNewChars; 394 395 if (mGapLength < 1) 396 new Exception("mGapLength < 1").printStackTrace(); 397 398 TextUtils.getChars(cs, csStart, csEnd, mText, start); 399 400 if (replacedLength > 0) { // no need for span fixup on pure insertion 401 // TODO potential optimization: only update bounds on intersecting spans 402 final boolean atEnd = (mGapStart + mGapLength == mText.length); 403 404 for (int i = 0; i < mSpanCount; i++) { 405 final int startFlag = (mSpanFlags[i] & START_MASK) >> START_SHIFT; 406 mSpanStarts[i] = updatedIntervalBound(mSpanStarts[i], start, nbNewChars, startFlag, 407 atEnd, textIsRemoved); 408 409 final int endFlag = (mSpanFlags[i] & END_MASK); 410 mSpanEnds[i] = updatedIntervalBound(mSpanEnds[i], start, nbNewChars, endFlag, 411 atEnd, textIsRemoved); 412 } 413 // TODO potential optimization: only fix up invariants when bounds actually changed 414 restoreInvariants(); 415 } 416 417 if (cs instanceof Spanned) { 418 Spanned sp = (Spanned) cs; 419 Object[] spans = sp.getSpans(csStart, csEnd, Object.class); 420 421 for (int i = 0; i < spans.length; i++) { 422 int st = sp.getSpanStart(spans[i]); 423 int en = sp.getSpanEnd(spans[i]); 424 425 if (st < csStart) st = csStart; 426 if (en > csEnd) en = csEnd; 427 428 // Add span only if this object is not yet used as a span in this string 429 if (getSpanStart(spans[i]) < 0) { 430 int copySpanStart = st - csStart + start; 431 int copySpanEnd = en - csStart + start; 432 int copySpanFlags = sp.getSpanFlags(spans[i]) | SPAN_ADDED; 433 434 setSpan(false, spans[i], copySpanStart, copySpanEnd, copySpanFlags, 435 false/*enforceParagraph*/); 436 } 437 } 438 restoreInvariants(); 439 } 440 } 441 442 private int updatedIntervalBound(int offset, int start, int nbNewChars, int flag, boolean atEnd, 443 boolean textIsRemoved) { 444 if (offset >= start && offset < mGapStart + mGapLength) { 445 if (flag == POINT) { 446 // A POINT located inside the replaced range should be moved to the end of the 447 // replaced text. 448 // The exception is when the point is at the start of the range and we are doing a 449 // text replacement (as opposed to a deletion): the point stays there. 450 if (textIsRemoved || offset > start) { 451 return mGapStart + mGapLength; 452 } 453 } else { 454 if (flag == PARAGRAPH) { 455 if (atEnd) { 456 return mGapStart + mGapLength; 457 } 458 } else { // MARK 459 // MARKs should be moved to the start, with the exception of a mark located at 460 // the end of the range (which will be < mGapStart + mGapLength since mGapLength 461 // is > 0, which should stay 'unchanged' at the end of the replaced text. 462 if (textIsRemoved || offset < mGapStart - nbNewChars) { 463 return start; 464 } else { 465 // Move to the end of replaced text (needed if nbNewChars != 0) 466 return mGapStart; 467 } 468 } 469 } 470 } 471 return offset; 472 } 473 474 // Note: caller is responsible for removing the mIndexOfSpan entry. 475 private void removeSpan(int i) { 476 Object object = mSpans[i]; 477 478 int start = mSpanStarts[i]; 479 int end = mSpanEnds[i]; 480 481 if (start > mGapStart) start -= mGapLength; 482 if (end > mGapStart) end -= mGapLength; 483 484 int count = mSpanCount - (i + 1); 485 System.arraycopy(mSpans, i + 1, mSpans, i, count); 486 System.arraycopy(mSpanStarts, i + 1, mSpanStarts, i, count); 487 System.arraycopy(mSpanEnds, i + 1, mSpanEnds, i, count); 488 System.arraycopy(mSpanFlags, i + 1, mSpanFlags, i, count); 489 System.arraycopy(mSpanOrder, i + 1, mSpanOrder, i, count); 490 491 mSpanCount--; 492 493 invalidateIndex(i); 494 mSpans[mSpanCount] = null; 495 496 // Invariants must be restored before sending span removed notifications. 497 restoreInvariants(); 498 499 sendSpanRemoved(object, start, end); 500 } 501 502 // Documentation from interface 503 public SpannableStringBuilder replace(int start, int end, CharSequence tb) { 504 return replace(start, end, tb, 0, tb.length()); 505 } 506 507 // Documentation from interface 508 public SpannableStringBuilder replace(final int start, final int end, 509 CharSequence tb, int tbstart, int tbend) { 510 checkRange("replace", start, end); 511 512 int filtercount = mFilters.length; 513 for (int i = 0; i < filtercount; i++) { 514 CharSequence repl = mFilters[i].filter(tb, tbstart, tbend, this, start, end); 515 516 if (repl != null) { 517 tb = repl; 518 tbstart = 0; 519 tbend = repl.length(); 520 } 521 } 522 523 final int origLen = end - start; 524 final int newLen = tbend - tbstart; 525 526 if (origLen == 0 && newLen == 0 && !hasNonExclusiveExclusiveSpanAt(tb, tbstart)) { 527 // This is a no-op iif there are no spans in tb that would be added (with a 0-length) 528 // Early exit so that the text watchers do not get notified 529 return this; 530 } 531 532 TextWatcher[] textWatchers = getSpans(start, start + origLen, TextWatcher.class); 533 sendBeforeTextChanged(textWatchers, start, origLen, newLen); 534 535 // Try to keep the cursor / selection at the same relative position during 536 // a text replacement. If replaced or replacement text length is zero, this 537 // is already taken care of. 538 boolean adjustSelection = origLen != 0 && newLen != 0; 539 int selectionStart = 0; 540 int selectionEnd = 0; 541 if (adjustSelection) { 542 selectionStart = Selection.getSelectionStart(this); 543 selectionEnd = Selection.getSelectionEnd(this); 544 } 545 546 change(start, end, tb, tbstart, tbend); 547 548 if (adjustSelection) { 549 boolean changed = false; 550 if (selectionStart > start && selectionStart < end) { 551 final long diff = selectionStart - start; 552 final int offset = Math.toIntExact(diff * newLen / origLen); 553 selectionStart = start + offset; 554 555 changed = true; 556 setSpan(false, Selection.SELECTION_START, selectionStart, selectionStart, 557 Spanned.SPAN_POINT_POINT, true/*enforceParagraph*/); 558 } 559 if (selectionEnd > start && selectionEnd < end) { 560 final long diff = selectionEnd - start; 561 final int offset = Math.toIntExact(diff * newLen / origLen); 562 selectionEnd = start + offset; 563 564 changed = true; 565 setSpan(false, Selection.SELECTION_END, selectionEnd, selectionEnd, 566 Spanned.SPAN_POINT_POINT, true/*enforceParagraph*/); 567 } 568 if (changed) { 569 restoreInvariants(); 570 } 571 } 572 573 sendTextChanged(textWatchers, start, origLen, newLen); 574 sendAfterTextChanged(textWatchers); 575 576 // Span watchers need to be called after text watchers, which may update the layout 577 sendToSpanWatchers(start, end, newLen - origLen); 578 579 return this; 580 } 581 582 private static boolean hasNonExclusiveExclusiveSpanAt(CharSequence text, int offset) { 583 if (text instanceof Spanned) { 584 Spanned spanned = (Spanned) text; 585 Object[] spans = spanned.getSpans(offset, offset, Object.class); 586 final int length = spans.length; 587 for (int i = 0; i < length; i++) { 588 Object span = spans[i]; 589 int flags = spanned.getSpanFlags(span); 590 if (flags != Spanned.SPAN_EXCLUSIVE_EXCLUSIVE) return true; 591 } 592 } 593 return false; 594 } 595 596 private void sendToSpanWatchers(int replaceStart, int replaceEnd, int nbNewChars) { 597 for (int i = 0; i < mSpanCount; i++) { 598 int spanFlags = mSpanFlags[i]; 599 600 // This loop handles only modified (not added) spans. 601 if ((spanFlags & SPAN_ADDED) != 0) continue; 602 int spanStart = mSpanStarts[i]; 603 int spanEnd = mSpanEnds[i]; 604 if (spanStart > mGapStart) spanStart -= mGapLength; 605 if (spanEnd > mGapStart) spanEnd -= mGapLength; 606 607 int newReplaceEnd = replaceEnd + nbNewChars; 608 boolean spanChanged = false; 609 610 int previousSpanStart = spanStart; 611 if (spanStart > newReplaceEnd) { 612 if (nbNewChars != 0) { 613 previousSpanStart -= nbNewChars; 614 spanChanged = true; 615 } 616 } else if (spanStart >= replaceStart) { 617 // No change if span start was already at replace interval boundaries before replace 618 if ((spanStart != replaceStart || 619 ((spanFlags & SPAN_START_AT_START) != SPAN_START_AT_START)) && 620 (spanStart != newReplaceEnd || 621 ((spanFlags & SPAN_START_AT_END) != SPAN_START_AT_END))) { 622 // TODO A correct previousSpanStart cannot be computed at this point. 623 // It would require to save all the previous spans' positions before the replace 624 // Using an invalid -1 value to convey this would break the broacast range 625 spanChanged = true; 626 } 627 } 628 629 int previousSpanEnd = spanEnd; 630 if (spanEnd > newReplaceEnd) { 631 if (nbNewChars != 0) { 632 previousSpanEnd -= nbNewChars; 633 spanChanged = true; 634 } 635 } else if (spanEnd >= replaceStart) { 636 // No change if span start was already at replace interval boundaries before replace 637 if ((spanEnd != replaceStart || 638 ((spanFlags & SPAN_END_AT_START) != SPAN_END_AT_START)) && 639 (spanEnd != newReplaceEnd || 640 ((spanFlags & SPAN_END_AT_END) != SPAN_END_AT_END))) { 641 // TODO same as above for previousSpanEnd 642 spanChanged = true; 643 } 644 } 645 646 if (spanChanged) { 647 sendSpanChanged(mSpans[i], previousSpanStart, previousSpanEnd, spanStart, spanEnd); 648 } 649 mSpanFlags[i] &= ~SPAN_START_END_MASK; 650 } 651 652 // Handle added spans 653 for (int i = 0; i < mSpanCount; i++) { 654 int spanFlags = mSpanFlags[i]; 655 if ((spanFlags & SPAN_ADDED) != 0) { 656 mSpanFlags[i] &= ~SPAN_ADDED; 657 int spanStart = mSpanStarts[i]; 658 int spanEnd = mSpanEnds[i]; 659 if (spanStart > mGapStart) spanStart -= mGapLength; 660 if (spanEnd > mGapStart) spanEnd -= mGapLength; 661 sendSpanAdded(mSpans[i], spanStart, spanEnd); 662 } 663 } 664 } 665 666 /** 667 * Mark the specified range of text with the specified object. 668 * The flags determine how the span will behave when text is 669 * inserted at the start or end of the span's range. 670 */ 671 public void setSpan(Object what, int start, int end, int flags) { 672 setSpan(true, what, start, end, flags, true/*enforceParagraph*/); 673 } 674 675 // Note: if send is false, then it is the caller's responsibility to restore 676 // invariants. If send is false and the span already exists, then this method 677 // will not change the index of any spans. 678 private void setSpan(boolean send, Object what, int start, int end, int flags, 679 boolean enforceParagraph) { 680 checkRange("setSpan", start, end); 681 682 int flagsStart = (flags & START_MASK) >> START_SHIFT; 683 if (isInvalidParagraph(start, flagsStart)) { 684 if (!enforceParagraph) { 685 // do not set the span 686 return; 687 } 688 throw new RuntimeException("PARAGRAPH span must start at paragraph boundary" 689 + " (" + start + " follows " + charAt(start - 1) + ")"); 690 } 691 692 int flagsEnd = flags & END_MASK; 693 if (isInvalidParagraph(end, flagsEnd)) { 694 if (!enforceParagraph) { 695 // do not set the span 696 return; 697 } 698 throw new RuntimeException("PARAGRAPH span must end at paragraph boundary" 699 + " (" + end + " follows " + charAt(end - 1) + ")"); 700 } 701 702 // 0-length Spanned.SPAN_EXCLUSIVE_EXCLUSIVE 703 if (flagsStart == POINT && flagsEnd == MARK && start == end) { 704 if (send) { 705 Log.e(TAG, "SPAN_EXCLUSIVE_EXCLUSIVE spans cannot have a zero length"); 706 } 707 // Silently ignore invalid spans when they are created from this class. 708 // This avoids the duplication of the above test code before all the 709 // calls to setSpan that are done in this class 710 return; 711 } 712 713 int nstart = start; 714 int nend = end; 715 716 if (start > mGapStart) { 717 start += mGapLength; 718 } else if (start == mGapStart) { 719 if (flagsStart == POINT || (flagsStart == PARAGRAPH && start == length())) 720 start += mGapLength; 721 } 722 723 if (end > mGapStart) { 724 end += mGapLength; 725 } else if (end == mGapStart) { 726 if (flagsEnd == POINT || (flagsEnd == PARAGRAPH && end == length())) 727 end += mGapLength; 728 } 729 730 if (mIndexOfSpan != null) { 731 Integer index = mIndexOfSpan.get(what); 732 if (index != null) { 733 int i = index; 734 int ostart = mSpanStarts[i]; 735 int oend = mSpanEnds[i]; 736 737 if (ostart > mGapStart) 738 ostart -= mGapLength; 739 if (oend > mGapStart) 740 oend -= mGapLength; 741 742 mSpanStarts[i] = start; 743 mSpanEnds[i] = end; 744 mSpanFlags[i] = flags; 745 746 if (send) { 747 restoreInvariants(); 748 sendSpanChanged(what, ostart, oend, nstart, nend); 749 } 750 751 return; 752 } 753 } 754 755 mSpans = GrowingArrayUtils.append(mSpans, mSpanCount, what); 756 mSpanStarts = GrowingArrayUtils.append(mSpanStarts, mSpanCount, start); 757 mSpanEnds = GrowingArrayUtils.append(mSpanEnds, mSpanCount, end); 758 mSpanFlags = GrowingArrayUtils.append(mSpanFlags, mSpanCount, flags); 759 mSpanOrder = GrowingArrayUtils.append(mSpanOrder, mSpanCount, mSpanInsertCount); 760 invalidateIndex(mSpanCount); 761 mSpanCount++; 762 mSpanInsertCount++; 763 // Make sure there is enough room for empty interior nodes. 764 // This magic formula computes the size of the smallest perfect binary 765 // tree no smaller than mSpanCount. 766 int sizeOfMax = 2 * treeRoot() + 1; 767 if (mSpanMax.length < sizeOfMax) { 768 mSpanMax = new int[sizeOfMax]; 769 } 770 771 if (send) { 772 restoreInvariants(); 773 sendSpanAdded(what, nstart, nend); 774 } 775 } 776 777 private boolean isInvalidParagraph(int index, int flag) { 778 return flag == PARAGRAPH && index != 0 && index != length() && charAt(index - 1) != '\n'; 779 } 780 781 /** 782 * Remove the specified markup object from the buffer. 783 */ 784 public void removeSpan(Object what) { 785 if (mIndexOfSpan == null) return; 786 Integer i = mIndexOfSpan.remove(what); 787 if (i != null) { 788 removeSpan(i.intValue()); 789 } 790 } 791 792 /** 793 * Return externally visible offset given offset into gapped buffer. 794 */ 795 private int resolveGap(int i) { 796 return i > mGapStart ? i - mGapLength : i; 797 } 798 799 /** 800 * Return the buffer offset of the beginning of the specified 801 * markup object, or -1 if it is not attached to this buffer. 802 */ 803 public int getSpanStart(Object what) { 804 if (mIndexOfSpan == null) return -1; 805 Integer i = mIndexOfSpan.get(what); 806 return i == null ? -1 : resolveGap(mSpanStarts[i]); 807 } 808 809 /** 810 * Return the buffer offset of the end of the specified 811 * markup object, or -1 if it is not attached to this buffer. 812 */ 813 public int getSpanEnd(Object what) { 814 if (mIndexOfSpan == null) return -1; 815 Integer i = mIndexOfSpan.get(what); 816 return i == null ? -1 : resolveGap(mSpanEnds[i]); 817 } 818 819 /** 820 * Return the flags of the end of the specified 821 * markup object, or 0 if it is not attached to this buffer. 822 */ 823 public int getSpanFlags(Object what) { 824 if (mIndexOfSpan == null) return 0; 825 Integer i = mIndexOfSpan.get(what); 826 return i == null ? 0 : mSpanFlags[i]; 827 } 828 829 /** 830 * Return an array of the spans of the specified type that overlap 831 * the specified range of the buffer. The kind may be Object.class to get 832 * a list of all the spans regardless of type. 833 */ 834 @SuppressWarnings("unchecked") 835 public <T> T[] getSpans(int queryStart, int queryEnd, @Nullable Class<T> kind) { 836 return getSpans(queryStart, queryEnd, kind, true); 837 } 838 839 /** 840 * Return an array of the spans of the specified type that overlap 841 * the specified range of the buffer. The kind may be Object.class to get 842 * a list of all the spans regardless of type. 843 * 844 * @param queryStart Start index. 845 * @param queryEnd End index. 846 * @param kind Class type to search for. 847 * @param sortByInsertionOrder If true the results are sorted by the insertion order. 848 * @param <T> 849 * @return Array of the spans. Empty array if no results are found. 850 * 851 * @hide 852 */ 853 public <T> T[] getSpans(int queryStart, int queryEnd, @Nullable Class<T> kind, 854 boolean sortByInsertionOrder) { 855 if (kind == null) return (T[]) ArrayUtils.emptyArray(Object.class); 856 if (mSpanCount == 0) return ArrayUtils.emptyArray(kind); 857 int count = countSpans(queryStart, queryEnd, kind, treeRoot()); 858 if (count == 0) { 859 return ArrayUtils.emptyArray(kind); 860 } 861 862 // Safe conversion, but requires a suppressWarning 863 T[] ret = (T[]) Array.newInstance(kind, count); 864 final int[] prioSortBuffer = sortByInsertionOrder ? obtain(count) : EmptyArray.INT; 865 final int[] orderSortBuffer = sortByInsertionOrder ? obtain(count) : EmptyArray.INT; 866 getSpansRec(queryStart, queryEnd, kind, treeRoot(), ret, prioSortBuffer, 867 orderSortBuffer, 0, sortByInsertionOrder); 868 if (sortByInsertionOrder) { 869 sort(ret, prioSortBuffer, orderSortBuffer); 870 recycle(prioSortBuffer); 871 recycle(orderSortBuffer); 872 } 873 return ret; 874 } 875 876 private int countSpans(int queryStart, int queryEnd, Class kind, int i) { 877 int count = 0; 878 if ((i & 1) != 0) { 879 // internal tree node 880 int left = leftChild(i); 881 int spanMax = mSpanMax[left]; 882 if (spanMax > mGapStart) { 883 spanMax -= mGapLength; 884 } 885 if (spanMax >= queryStart) { 886 count = countSpans(queryStart, queryEnd, kind, left); 887 } 888 } 889 if (i < mSpanCount) { 890 int spanStart = mSpanStarts[i]; 891 if (spanStart > mGapStart) { 892 spanStart -= mGapLength; 893 } 894 if (spanStart <= queryEnd) { 895 int spanEnd = mSpanEnds[i]; 896 if (spanEnd > mGapStart) { 897 spanEnd -= mGapLength; 898 } 899 if (spanEnd >= queryStart && 900 (spanStart == spanEnd || queryStart == queryEnd || 901 (spanStart != queryEnd && spanEnd != queryStart)) && 902 (Object.class == kind || kind.isInstance(mSpans[i]))) { 903 count++; 904 } 905 if ((i & 1) != 0) { 906 count += countSpans(queryStart, queryEnd, kind, rightChild(i)); 907 } 908 } 909 } 910 return count; 911 } 912 913 /** 914 * Fills the result array with the spans found under the current interval tree node. 915 * 916 * @param queryStart Start index for the interval query. 917 * @param queryEnd End index for the interval query. 918 * @param kind Class type to search for. 919 * @param i Index of the current tree node. 920 * @param ret Array to be filled with results. 921 * @param priority Buffer to keep record of the priorities of spans found. 922 * @param insertionOrder Buffer to keep record of the insertion orders of spans found. 923 * @param count The number of found spans. 924 * @param sort Flag to fill the priority and insertion order buffers. If false then 925 * the spans with priority flag will be sorted in the result array. 926 * @param <T> 927 * @return The total number of spans found. 928 */ 929 @SuppressWarnings("unchecked") 930 private <T> int getSpansRec(int queryStart, int queryEnd, Class<T> kind, 931 int i, T[] ret, int[] priority, int[] insertionOrder, int count, boolean sort) { 932 if ((i & 1) != 0) { 933 // internal tree node 934 int left = leftChild(i); 935 int spanMax = mSpanMax[left]; 936 if (spanMax > mGapStart) { 937 spanMax -= mGapLength; 938 } 939 if (spanMax >= queryStart) { 940 count = getSpansRec(queryStart, queryEnd, kind, left, ret, priority, 941 insertionOrder, count, sort); 942 } 943 } 944 if (i >= mSpanCount) return count; 945 int spanStart = mSpanStarts[i]; 946 if (spanStart > mGapStart) { 947 spanStart -= mGapLength; 948 } 949 if (spanStart <= queryEnd) { 950 int spanEnd = mSpanEnds[i]; 951 if (spanEnd > mGapStart) { 952 spanEnd -= mGapLength; 953 } 954 if (spanEnd >= queryStart && 955 (spanStart == spanEnd || queryStart == queryEnd || 956 (spanStart != queryEnd && spanEnd != queryStart)) && 957 (Object.class == kind || kind.isInstance(mSpans[i]))) { 958 int spanPriority = mSpanFlags[i] & SPAN_PRIORITY; 959 int target = count; 960 if (sort) { 961 priority[target] = spanPriority; 962 insertionOrder[target] = mSpanOrder[i]; 963 } else if (spanPriority != 0) { 964 //insertion sort for elements with priority 965 int j = 0; 966 for (; j < count; j++) { 967 int p = getSpanFlags(ret[j]) & SPAN_PRIORITY; 968 if (spanPriority > p) break; 969 } 970 System.arraycopy(ret, j, ret, j + 1, count - j); 971 target = j; 972 } 973 ret[target] = (T) mSpans[i]; 974 count++; 975 } 976 if (count < ret.length && (i & 1) != 0) { 977 count = getSpansRec(queryStart, queryEnd, kind, rightChild(i), ret, priority, 978 insertionOrder, count, sort); 979 } 980 } 981 return count; 982 } 983 984 /** 985 * Obtain a temporary sort buffer. 986 * 987 * @param elementCount the size of the int[] to be returned 988 * @return an int[] with elementCount length 989 */ 990 private static int[] obtain(final int elementCount) { 991 int[] result = null; 992 synchronized (sCachedIntBuffer) { 993 // try finding a tmp buffer with length of at least elementCount 994 // if not get the first available one 995 int candidateIndex = -1; 996 for (int i = sCachedIntBuffer.length - 1; i >= 0; i--) { 997 if (sCachedIntBuffer[i] != null) { 998 if (sCachedIntBuffer[i].length >= elementCount) { 999 candidateIndex = i; 1000 break; 1001 } else if (candidateIndex == -1) { 1002 candidateIndex = i; 1003 } 1004 } 1005 } 1006 1007 if (candidateIndex != -1) { 1008 result = sCachedIntBuffer[candidateIndex]; 1009 sCachedIntBuffer[candidateIndex] = null; 1010 } 1011 } 1012 result = checkSortBuffer(result, elementCount); 1013 return result; 1014 } 1015 1016 /** 1017 * Recycle sort buffer. 1018 * 1019 * @param buffer buffer to be recycled 1020 */ 1021 private static void recycle(int[] buffer) { 1022 synchronized (sCachedIntBuffer) { 1023 for (int i = 0; i < sCachedIntBuffer.length; i++) { 1024 if (sCachedIntBuffer[i] == null || buffer.length > sCachedIntBuffer[i].length) { 1025 sCachedIntBuffer[i] = buffer; 1026 break; 1027 } 1028 } 1029 } 1030 } 1031 1032 /** 1033 * Check the size of the buffer and grow if required. 1034 * 1035 * @param buffer buffer to be checked. 1036 * @param size required size. 1037 * @return Same buffer instance if the current size is greater than required size. Otherwise a 1038 * new instance is created and returned. 1039 */ 1040 private static int[] checkSortBuffer(int[] buffer, int size) { 1041 if (buffer == null || size > buffer.length) { 1042 return ArrayUtils.newUnpaddedIntArray(GrowingArrayUtils.growSize(size)); 1043 } 1044 return buffer; 1045 } 1046 1047 /** 1048 * An iterative heap sort implementation. It will sort the spans using first their priority 1049 * then insertion order. A span with higher priority will be before a span with lower 1050 * priority. If priorities are the same, the spans will be sorted with insertion order. A 1051 * span with a lower insertion order will be before a span with a higher insertion order. 1052 * 1053 * @param array Span array to be sorted. 1054 * @param priority Priorities of the spans 1055 * @param insertionOrder Insertion orders of the spans 1056 * @param <T> Span object type. 1057 * @param <T> 1058 */ 1059 private final <T> void sort(T[] array, int[] priority, int[] insertionOrder) { 1060 int size = array.length; 1061 for (int i = size / 2 - 1; i >= 0; i--) { 1062 siftDown(i, array, size, priority, insertionOrder); 1063 } 1064 1065 for (int i = size - 1; i > 0; i--) { 1066 final T tmpSpan = array[0]; 1067 array[0] = array[i]; 1068 array[i] = tmpSpan; 1069 1070 final int tmpPriority = priority[0]; 1071 priority[0] = priority[i]; 1072 priority[i] = tmpPriority; 1073 1074 final int tmpOrder = insertionOrder[0]; 1075 insertionOrder[0] = insertionOrder[i]; 1076 insertionOrder[i] = tmpOrder; 1077 1078 siftDown(0, array, i, priority, insertionOrder); 1079 } 1080 } 1081 1082 /** 1083 * Helper function for heap sort. 1084 * 1085 * @param index Index of the element to sift down. 1086 * @param array Span array to be sorted. 1087 * @param size Current heap size. 1088 * @param priority Priorities of the spans 1089 * @param insertionOrder Insertion orders of the spans 1090 * @param <T> Span object type. 1091 */ 1092 private final <T> void siftDown(int index, T[] array, int size, int[] priority, 1093 int[] insertionOrder) { 1094 int left = 2 * index + 1; 1095 while (left < size) { 1096 if (left < size - 1 && compareSpans(left, left + 1, priority, insertionOrder) < 0) { 1097 left++; 1098 } 1099 if (compareSpans(index, left, priority, insertionOrder) >= 0) { 1100 break; 1101 } 1102 1103 final T tmpSpan = array[index]; 1104 array[index] = array[left]; 1105 array[left] = tmpSpan; 1106 1107 final int tmpPriority = priority[index]; 1108 priority[index] = priority[left]; 1109 priority[left] = tmpPriority; 1110 1111 final int tmpOrder = insertionOrder[index]; 1112 insertionOrder[index] = insertionOrder[left]; 1113 insertionOrder[left] = tmpOrder; 1114 1115 index = left; 1116 left = 2 * index + 1; 1117 } 1118 } 1119 1120 /** 1121 * Compare two span elements in an array. Comparison is based first on the priority flag of 1122 * the span, and then the insertion order of the span. 1123 * 1124 * @param left Index of the element to compare. 1125 * @param right Index of the other element to compare. 1126 * @param priority Priorities of the spans 1127 * @param insertionOrder Insertion orders of the spans 1128 * @return 1129 */ 1130 private final int compareSpans(int left, int right, int[] priority, 1131 int[] insertionOrder) { 1132 int priority1 = priority[left]; 1133 int priority2 = priority[right]; 1134 if (priority1 == priority2) { 1135 return Integer.compare(insertionOrder[left], insertionOrder[right]); 1136 } 1137 // since high priority has to be before a lower priority, the arguments to compare are 1138 // opposite of the insertion order check. 1139 return Integer.compare(priority2, priority1); 1140 } 1141 1142 /** 1143 * Return the next offset after <code>start</code> but less than or 1144 * equal to <code>limit</code> where a span of the specified type 1145 * begins or ends. 1146 */ 1147 public int nextSpanTransition(int start, int limit, Class kind) { 1148 if (mSpanCount == 0) return limit; 1149 if (kind == null) { 1150 kind = Object.class; 1151 } 1152 return nextSpanTransitionRec(start, limit, kind, treeRoot()); 1153 } 1154 1155 private int nextSpanTransitionRec(int start, int limit, Class kind, int i) { 1156 if ((i & 1) != 0) { 1157 // internal tree node 1158 int left = leftChild(i); 1159 if (resolveGap(mSpanMax[left]) > start) { 1160 limit = nextSpanTransitionRec(start, limit, kind, left); 1161 } 1162 } 1163 if (i < mSpanCount) { 1164 int st = resolveGap(mSpanStarts[i]); 1165 int en = resolveGap(mSpanEnds[i]); 1166 if (st > start && st < limit && kind.isInstance(mSpans[i])) 1167 limit = st; 1168 if (en > start && en < limit && kind.isInstance(mSpans[i])) 1169 limit = en; 1170 if (st < limit && (i & 1) != 0) { 1171 limit = nextSpanTransitionRec(start, limit, kind, rightChild(i)); 1172 } 1173 } 1174 1175 return limit; 1176 } 1177 1178 /** 1179 * Return a new CharSequence containing a copy of the specified 1180 * range of this buffer, including the overlapping spans. 1181 */ 1182 public CharSequence subSequence(int start, int end) { 1183 return new SpannableStringBuilder(this, start, end); 1184 } 1185 1186 /** 1187 * Copy the specified range of chars from this buffer into the 1188 * specified array, beginning at the specified offset. 1189 */ 1190 public void getChars(int start, int end, char[] dest, int destoff) { 1191 checkRange("getChars", start, end); 1192 1193 if (end <= mGapStart) { 1194 System.arraycopy(mText, start, dest, destoff, end - start); 1195 } else if (start >= mGapStart) { 1196 System.arraycopy(mText, start + mGapLength, dest, destoff, end - start); 1197 } else { 1198 System.arraycopy(mText, start, dest, destoff, mGapStart - start); 1199 System.arraycopy(mText, mGapStart + mGapLength, 1200 dest, destoff + (mGapStart - start), 1201 end - mGapStart); 1202 } 1203 } 1204 1205 /** 1206 * Return a String containing a copy of the chars in this buffer. 1207 */ 1208 @Override 1209 public String toString() { 1210 int len = length(); 1211 char[] buf = new char[len]; 1212 1213 getChars(0, len, buf, 0); 1214 return new String(buf); 1215 } 1216 1217 /** 1218 * Return a String containing a copy of the chars in this buffer, limited to the 1219 * [start, end[ range. 1220 * @hide 1221 */ 1222 public String substring(int start, int end) { 1223 char[] buf = new char[end - start]; 1224 getChars(start, end, buf, 0); 1225 return new String(buf); 1226 } 1227 1228 /** 1229 * Returns the depth of TextWatcher callbacks. Returns 0 when the object is not handling 1230 * TextWatchers. A return value greater than 1 implies that a TextWatcher caused a change that 1231 * recursively triggered a TextWatcher. 1232 */ 1233 public int getTextWatcherDepth() { 1234 return mTextWatcherDepth; 1235 } 1236 1237 private void sendBeforeTextChanged(TextWatcher[] watchers, int start, int before, int after) { 1238 int n = watchers.length; 1239 1240 mTextWatcherDepth++; 1241 for (int i = 0; i < n; i++) { 1242 watchers[i].beforeTextChanged(this, start, before, after); 1243 } 1244 mTextWatcherDepth--; 1245 } 1246 1247 private void sendTextChanged(TextWatcher[] watchers, int start, int before, int after) { 1248 int n = watchers.length; 1249 1250 mTextWatcherDepth++; 1251 for (int i = 0; i < n; i++) { 1252 watchers[i].onTextChanged(this, start, before, after); 1253 } 1254 mTextWatcherDepth--; 1255 } 1256 1257 private void sendAfterTextChanged(TextWatcher[] watchers) { 1258 int n = watchers.length; 1259 1260 mTextWatcherDepth++; 1261 for (int i = 0; i < n; i++) { 1262 watchers[i].afterTextChanged(this); 1263 } 1264 mTextWatcherDepth--; 1265 } 1266 1267 private void sendSpanAdded(Object what, int start, int end) { 1268 SpanWatcher[] recip = getSpans(start, end, SpanWatcher.class); 1269 int n = recip.length; 1270 1271 for (int i = 0; i < n; i++) { 1272 recip[i].onSpanAdded(this, what, start, end); 1273 } 1274 } 1275 1276 private void sendSpanRemoved(Object what, int start, int end) { 1277 SpanWatcher[] recip = getSpans(start, end, SpanWatcher.class); 1278 int n = recip.length; 1279 1280 for (int i = 0; i < n; i++) { 1281 recip[i].onSpanRemoved(this, what, start, end); 1282 } 1283 } 1284 1285 private void sendSpanChanged(Object what, int oldStart, int oldEnd, int start, int end) { 1286 // The bounds of a possible SpanWatcher are guaranteed to be set before this method is 1287 // called, so that the order of the span does not affect this broadcast. 1288 SpanWatcher[] spanWatchers = getSpans(Math.min(oldStart, start), 1289 Math.min(Math.max(oldEnd, end), length()), SpanWatcher.class); 1290 int n = spanWatchers.length; 1291 for (int i = 0; i < n; i++) { 1292 spanWatchers[i].onSpanChanged(this, what, oldStart, oldEnd, start, end); 1293 } 1294 } 1295 1296 private static String region(int start, int end) { 1297 return "(" + start + " ... " + end + ")"; 1298 } 1299 1300 private void checkRange(final String operation, int start, int end) { 1301 if (end < start) { 1302 throw new IndexOutOfBoundsException(operation + " " + 1303 region(start, end) + " has end before start"); 1304 } 1305 1306 int len = length(); 1307 1308 if (start > len || end > len) { 1309 throw new IndexOutOfBoundsException(operation + " " + 1310 region(start, end) + " ends beyond length " + len); 1311 } 1312 1313 if (start < 0 || end < 0) { 1314 throw new IndexOutOfBoundsException(operation + " " + 1315 region(start, end) + " starts before 0"); 1316 } 1317 } 1318 1319 /* 1320 private boolean isprint(char c) { // XXX 1321 if (c >= ' ' && c <= '~') 1322 return true; 1323 else 1324 return false; 1325 } 1326 1327 private static final int startFlag(int flag) { 1328 return (flag >> 4) & 0x0F; 1329 } 1330 1331 private static final int endFlag(int flag) { 1332 return flag & 0x0F; 1333 } 1334 1335 public void dump() { // XXX 1336 for (int i = 0; i < mGapStart; i++) { 1337 System.out.print('|'); 1338 System.out.print(' '); 1339 System.out.print(isprint(mText[i]) ? mText[i] : '.'); 1340 System.out.print(' '); 1341 } 1342 1343 for (int i = mGapStart; i < mGapStart + mGapLength; i++) { 1344 System.out.print('|'); 1345 System.out.print('('); 1346 System.out.print(isprint(mText[i]) ? mText[i] : '.'); 1347 System.out.print(')'); 1348 } 1349 1350 for (int i = mGapStart + mGapLength; i < mText.length; i++) { 1351 System.out.print('|'); 1352 System.out.print(' '); 1353 System.out.print(isprint(mText[i]) ? mText[i] : '.'); 1354 System.out.print(' '); 1355 } 1356 1357 System.out.print('\n'); 1358 1359 for (int i = 0; i < mText.length + 1; i++) { 1360 int found = 0; 1361 int wfound = 0; 1362 1363 for (int j = 0; j < mSpanCount; j++) { 1364 if (mSpanStarts[j] == i) { 1365 found = 1; 1366 wfound = j; 1367 break; 1368 } 1369 1370 if (mSpanEnds[j] == i) { 1371 found = 2; 1372 wfound = j; 1373 break; 1374 } 1375 } 1376 1377 if (found == 1) { 1378 if (startFlag(mSpanFlags[wfound]) == MARK) 1379 System.out.print("( "); 1380 if (startFlag(mSpanFlags[wfound]) == PARAGRAPH) 1381 System.out.print("< "); 1382 else 1383 System.out.print("[ "); 1384 } else if (found == 2) { 1385 if (endFlag(mSpanFlags[wfound]) == POINT) 1386 System.out.print(") "); 1387 if (endFlag(mSpanFlags[wfound]) == PARAGRAPH) 1388 System.out.print("> "); 1389 else 1390 System.out.print("] "); 1391 } else { 1392 System.out.print(" "); 1393 } 1394 } 1395 1396 System.out.print("\n"); 1397 } 1398 */ 1399 1400 /** 1401 * Don't call this yourself -- exists for Canvas to use internally. 1402 * {@hide} 1403 */ 1404 @Override 1405 public void drawText(BaseCanvas c, int start, int end, float x, float y, Paint p) { 1406 checkRange("drawText", start, end); 1407 1408 if (end <= mGapStart) { 1409 c.drawText(mText, start, end - start, x, y, p); 1410 } else if (start >= mGapStart) { 1411 c.drawText(mText, start + mGapLength, end - start, x, y, p); 1412 } else { 1413 char[] buf = TextUtils.obtain(end - start); 1414 1415 getChars(start, end, buf, 0); 1416 c.drawText(buf, 0, end - start, x, y, p); 1417 TextUtils.recycle(buf); 1418 } 1419 } 1420 1421 1422 /** 1423 * Don't call this yourself -- exists for Canvas to use internally. 1424 * {@hide} 1425 */ 1426 @Override 1427 public void drawTextRun(BaseCanvas c, int start, int end, int contextStart, int contextEnd, 1428 float x, float y, boolean isRtl, Paint p) { 1429 checkRange("drawTextRun", start, end); 1430 1431 int contextLen = contextEnd - contextStart; 1432 int len = end - start; 1433 if (contextEnd <= mGapStart) { 1434 c.drawTextRun(mText, start, len, contextStart, contextLen, x, y, isRtl, p); 1435 } else if (contextStart >= mGapStart) { 1436 c.drawTextRun(mText, start + mGapLength, len, contextStart + mGapLength, 1437 contextLen, x, y, isRtl, p); 1438 } else { 1439 char[] buf = TextUtils.obtain(contextLen); 1440 getChars(contextStart, contextEnd, buf, 0); 1441 c.drawTextRun(buf, start - contextStart, len, 0, contextLen, x, y, isRtl, p); 1442 TextUtils.recycle(buf); 1443 } 1444 } 1445 1446 /** 1447 * Don't call this yourself -- exists for Paint to use internally. 1448 * {@hide} 1449 */ 1450 public float measureText(int start, int end, Paint p) { 1451 checkRange("measureText", start, end); 1452 1453 float ret; 1454 1455 if (end <= mGapStart) { 1456 ret = p.measureText(mText, start, end - start); 1457 } else if (start >= mGapStart) { 1458 ret = p.measureText(mText, start + mGapLength, end - start); 1459 } else { 1460 char[] buf = TextUtils.obtain(end - start); 1461 1462 getChars(start, end, buf, 0); 1463 ret = p.measureText(buf, 0, end - start); 1464 TextUtils.recycle(buf); 1465 } 1466 1467 return ret; 1468 } 1469 1470 /** 1471 * Don't call this yourself -- exists for Paint to use internally. 1472 * {@hide} 1473 */ 1474 public int getTextWidths(int start, int end, float[] widths, Paint p) { 1475 checkRange("getTextWidths", start, end); 1476 1477 int ret; 1478 1479 if (end <= mGapStart) { 1480 ret = p.getTextWidths(mText, start, end - start, widths); 1481 } else if (start >= mGapStart) { 1482 ret = p.getTextWidths(mText, start + mGapLength, end - start, widths); 1483 } else { 1484 char[] buf = TextUtils.obtain(end - start); 1485 1486 getChars(start, end, buf, 0); 1487 ret = p.getTextWidths(buf, 0, end - start, widths); 1488 TextUtils.recycle(buf); 1489 } 1490 1491 return ret; 1492 } 1493 1494 /** 1495 * Don't call this yourself -- exists for Paint to use internally. 1496 * {@hide} 1497 */ 1498 public float getTextRunAdvances(int start, int end, int contextStart, int contextEnd, boolean isRtl, 1499 float[] advances, int advancesPos, Paint p) { 1500 1501 float ret; 1502 1503 int contextLen = contextEnd - contextStart; 1504 int len = end - start; 1505 1506 if (end <= mGapStart) { 1507 ret = p.getTextRunAdvances(mText, start, len, contextStart, contextLen, 1508 isRtl, advances, advancesPos); 1509 } else if (start >= mGapStart) { 1510 ret = p.getTextRunAdvances(mText, start + mGapLength, len, 1511 contextStart + mGapLength, contextLen, isRtl, advances, advancesPos); 1512 } else { 1513 char[] buf = TextUtils.obtain(contextLen); 1514 getChars(contextStart, contextEnd, buf, 0); 1515 ret = p.getTextRunAdvances(buf, start - contextStart, len, 1516 0, contextLen, isRtl, advances, advancesPos); 1517 TextUtils.recycle(buf); 1518 } 1519 1520 return ret; 1521 } 1522 1523 /** 1524 * Returns the next cursor position in the run. This avoids placing the cursor between 1525 * surrogates, between characters that form conjuncts, between base characters and combining 1526 * marks, or within a reordering cluster. 1527 * 1528 * <p>The context is the shaping context for cursor movement, generally the bounds of the metric 1529 * span enclosing the cursor in the direction of movement. 1530 * <code>contextStart</code>, <code>contextEnd</code> and <code>offset</code> are relative to 1531 * the start of the string.</p> 1532 * 1533 * <p>If cursorOpt is CURSOR_AT and the offset is not a valid cursor position, 1534 * this returns -1. Otherwise this will never return a value before contextStart or after 1535 * contextEnd.</p> 1536 * 1537 * @param contextStart the start index of the context 1538 * @param contextEnd the (non-inclusive) end index of the context 1539 * @param dir either DIRECTION_RTL or DIRECTION_LTR 1540 * @param offset the cursor position to move from 1541 * @param cursorOpt how to move the cursor, one of CURSOR_AFTER, 1542 * CURSOR_AT_OR_AFTER, CURSOR_BEFORE, 1543 * CURSOR_AT_OR_BEFORE, or CURSOR_AT 1544 * @param p the Paint object that is requesting this information 1545 * @return the offset of the next position, or -1 1546 * @deprecated This is an internal method, refrain from using it in your code 1547 */ 1548 @Deprecated 1549 public int getTextRunCursor(int contextStart, int contextEnd, int dir, int offset, 1550 int cursorOpt, Paint p) { 1551 1552 int ret; 1553 1554 int contextLen = contextEnd - contextStart; 1555 if (contextEnd <= mGapStart) { 1556 ret = p.getTextRunCursor(mText, contextStart, contextLen, 1557 dir, offset, cursorOpt); 1558 } else if (contextStart >= mGapStart) { 1559 ret = p.getTextRunCursor(mText, contextStart + mGapLength, contextLen, 1560 dir, offset + mGapLength, cursorOpt) - mGapLength; 1561 } else { 1562 char[] buf = TextUtils.obtain(contextLen); 1563 getChars(contextStart, contextEnd, buf, 0); 1564 ret = p.getTextRunCursor(buf, 0, contextLen, 1565 dir, offset - contextStart, cursorOpt) + contextStart; 1566 TextUtils.recycle(buf); 1567 } 1568 1569 return ret; 1570 } 1571 1572 // Documentation from interface 1573 public void setFilters(InputFilter[] filters) { 1574 if (filters == null) { 1575 throw new IllegalArgumentException(); 1576 } 1577 1578 mFilters = filters; 1579 } 1580 1581 // Documentation from interface 1582 public InputFilter[] getFilters() { 1583 return mFilters; 1584 } 1585 1586 // Same as SpannableStringInternal 1587 @Override 1588 public boolean equals(Object o) { 1589 if (o instanceof Spanned && 1590 toString().equals(o.toString())) { 1591 Spanned other = (Spanned) o; 1592 // Check span data 1593 Object[] otherSpans = other.getSpans(0, other.length(), Object.class); 1594 if (mSpanCount == otherSpans.length) { 1595 for (int i = 0; i < mSpanCount; ++i) { 1596 Object thisSpan = mSpans[i]; 1597 Object otherSpan = otherSpans[i]; 1598 if (thisSpan == this) { 1599 if (other != otherSpan || 1600 getSpanStart(thisSpan) != other.getSpanStart(otherSpan) || 1601 getSpanEnd(thisSpan) != other.getSpanEnd(otherSpan) || 1602 getSpanFlags(thisSpan) != other.getSpanFlags(otherSpan)) { 1603 return false; 1604 } 1605 } else if (!thisSpan.equals(otherSpan) || 1606 getSpanStart(thisSpan) != other.getSpanStart(otherSpan) || 1607 getSpanEnd(thisSpan) != other.getSpanEnd(otherSpan) || 1608 getSpanFlags(thisSpan) != other.getSpanFlags(otherSpan)) { 1609 return false; 1610 } 1611 } 1612 return true; 1613 } 1614 } 1615 return false; 1616 } 1617 1618 // Same as SpannableStringInternal 1619 @Override 1620 public int hashCode() { 1621 int hash = toString().hashCode(); 1622 hash = hash * 31 + mSpanCount; 1623 for (int i = 0; i < mSpanCount; ++i) { 1624 Object span = mSpans[i]; 1625 if (span != this) { 1626 hash = hash * 31 + span.hashCode(); 1627 } 1628 hash = hash * 31 + getSpanStart(span); 1629 hash = hash * 31 + getSpanEnd(span); 1630 hash = hash * 31 + getSpanFlags(span); 1631 } 1632 return hash; 1633 } 1634 1635 // Primitives for treating span list as binary tree 1636 1637 // The spans (along with start and end offsets and flags) are stored in linear arrays sorted 1638 // by start offset. For fast searching, there is a binary search structure imposed over these 1639 // arrays. This structure is inorder traversal of a perfect binary tree, a slightly unusual 1640 // but advantageous approach. 1641 1642 // The value-containing nodes are indexed 0 <= i < n (where n = mSpanCount), thus preserving 1643 // logic that accesses the values as a contiguous array. Other balanced binary tree approaches 1644 // (such as a complete binary tree) would require some shuffling of node indices. 1645 1646 // Basic properties of this structure: For a perfect binary tree of height m: 1647 // The tree has 2^(m+1) - 1 total nodes. 1648 // The root of the tree has index 2^m - 1. 1649 // All leaf nodes have even index, all interior nodes odd. 1650 // The height of a node of index i is the number of trailing ones in i's binary representation. 1651 // The left child of a node i of height h is i - 2^(h - 1). 1652 // The right child of a node i of height h is i + 2^(h - 1). 1653 1654 // Note that for arbitrary n, interior nodes of this tree may be >= n. Thus, the general 1655 // structure of a recursive traversal of node i is: 1656 // * traverse left child if i is an interior node 1657 // * process i if i < n 1658 // * traverse right child if i is an interior node and i < n 1659 1660 private int treeRoot() { 1661 return Integer.highestOneBit(mSpanCount) - 1; 1662 } 1663 1664 // (i+1) & ~i is equal to 2^(the number of trailing ones in i) 1665 private static int leftChild(int i) { 1666 return i - (((i + 1) & ~i) >> 1); 1667 } 1668 1669 private static int rightChild(int i) { 1670 return i + (((i + 1) & ~i) >> 1); 1671 } 1672 1673 // The span arrays are also augmented by an mSpanMax[] array that represents an interval tree 1674 // over the binary tree structure described above. For each node, the mSpanMax[] array contains 1675 // the maximum value of mSpanEnds of that node and its descendants. Thus, traversals can 1676 // easily reject subtrees that contain no spans overlapping the area of interest. 1677 1678 // Note that mSpanMax[] also has a valid valuefor interior nodes of index >= n, but which have 1679 // descendants of index < n. In these cases, it simply represents the maximum span end of its 1680 // descendants. This is a consequence of the perfect binary tree structure. 1681 private int calcMax(int i) { 1682 int max = 0; 1683 if ((i & 1) != 0) { 1684 // internal tree node 1685 max = calcMax(leftChild(i)); 1686 } 1687 if (i < mSpanCount) { 1688 max = Math.max(max, mSpanEnds[i]); 1689 if ((i & 1) != 0) { 1690 max = Math.max(max, calcMax(rightChild(i))); 1691 } 1692 } 1693 mSpanMax[i] = max; 1694 return max; 1695 } 1696 1697 // restores binary interval tree invariants after any mutation of span structure 1698 private void restoreInvariants() { 1699 if (mSpanCount == 0) return; 1700 1701 // invariant 1: span starts are nondecreasing 1702 1703 // This is a simple insertion sort because we expect it to be mostly sorted. 1704 for (int i = 1; i < mSpanCount; i++) { 1705 if (mSpanStarts[i] < mSpanStarts[i - 1]) { 1706 Object span = mSpans[i]; 1707 int start = mSpanStarts[i]; 1708 int end = mSpanEnds[i]; 1709 int flags = mSpanFlags[i]; 1710 int insertionOrder = mSpanOrder[i]; 1711 int j = i; 1712 do { 1713 mSpans[j] = mSpans[j - 1]; 1714 mSpanStarts[j] = mSpanStarts[j - 1]; 1715 mSpanEnds[j] = mSpanEnds[j - 1]; 1716 mSpanFlags[j] = mSpanFlags[j - 1]; 1717 mSpanOrder[j] = mSpanOrder[j - 1]; 1718 j--; 1719 } while (j > 0 && start < mSpanStarts[j - 1]); 1720 mSpans[j] = span; 1721 mSpanStarts[j] = start; 1722 mSpanEnds[j] = end; 1723 mSpanFlags[j] = flags; 1724 mSpanOrder[j] = insertionOrder; 1725 invalidateIndex(j); 1726 } 1727 } 1728 1729 // invariant 2: max is max span end for each node and its descendants 1730 calcMax(treeRoot()); 1731 1732 // invariant 3: mIndexOfSpan maps spans back to indices 1733 if (mIndexOfSpan == null) { 1734 mIndexOfSpan = new IdentityHashMap<Object, Integer>(); 1735 } 1736 for (int i = mLowWaterMark; i < mSpanCount; i++) { 1737 Integer existing = mIndexOfSpan.get(mSpans[i]); 1738 if (existing == null || existing != i) { 1739 mIndexOfSpan.put(mSpans[i], i); 1740 } 1741 } 1742 mLowWaterMark = Integer.MAX_VALUE; 1743 } 1744 1745 // Call this on any update to mSpans[], so that mIndexOfSpan can be updated 1746 private void invalidateIndex(int i) { 1747 mLowWaterMark = Math.min(i, mLowWaterMark); 1748 } 1749 1750 private static final InputFilter[] NO_FILTERS = new InputFilter[0]; 1751 1752 @GuardedBy("sCachedIntBuffer") 1753 private static final int[][] sCachedIntBuffer = new int[6][0]; 1754 1755 private InputFilter[] mFilters = NO_FILTERS; 1756 1757 private char[] mText; 1758 private int mGapStart; 1759 private int mGapLength; 1760 1761 private Object[] mSpans; 1762 private int[] mSpanStarts; 1763 private int[] mSpanEnds; 1764 private int[] mSpanMax; // see calcMax() for an explanation of what this array stores 1765 private int[] mSpanFlags; 1766 private int[] mSpanOrder; // store the order of span insertion 1767 private int mSpanInsertCount; // counter for the span insertion 1768 1769 private int mSpanCount; 1770 private IdentityHashMap<Object, Integer> mIndexOfSpan; 1771 private int mLowWaterMark; // indices below this have not been touched 1772 1773 // TextWatcher callbacks may trigger changes that trigger more callbacks. This keeps track of 1774 // how deep the callbacks go. 1775 private int mTextWatcherDepth; 1776 1777 // TODO These value are tightly related to the public SPAN_MARK/POINT values in {@link Spanned} 1778 private static final int MARK = 1; 1779 private static final int POINT = 2; 1780 private static final int PARAGRAPH = 3; 1781 1782 private static final int START_MASK = 0xF0; 1783 private static final int END_MASK = 0x0F; 1784 private static final int START_SHIFT = 4; 1785 1786 // These bits are not (currently) used by SPANNED flags 1787 private static final int SPAN_ADDED = 0x800; 1788 private static final int SPAN_START_AT_START = 0x1000; 1789 private static final int SPAN_START_AT_END = 0x2000; 1790 private static final int SPAN_END_AT_START = 0x4000; 1791 private static final int SPAN_END_AT_END = 0x8000; 1792 private static final int SPAN_START_END_MASK = 0xF000; 1793} 1794