Question

SpannableStringBuilder 与 SpannableString 类似与 String 和 StringBuilder 之间的关系。SpannableStringBuilder 加入了 append, replace, delete 等方法，作用自不用多说，下面我们还是看下他的 setSpan:

public void setSpan(Object what, int start, int end, int flags) {
  setSpan(true, what, start, end, flags);
}

// Note: if send is false, then it is the caller's responsibility to restore
// invariants. If send is false and the span already exists, then this method
// will not change the index of any spans.
private void setSpan(boolean send, Object what, int start, int end, int flags) {
  // 检查 start 和 end 是否合法
  checkRange("setSpan", start, end);
  int flagsStart = (flags & START_MASK) >> START_SHIFT;
  if(isInvalidParagraphStart(start, flagsStart)) {
    throw new RuntimeException("PARAGRAPH span must start at paragraph boundary");
  }
  int flagsEnd = flags & END_MASK;
  if(isInvalidParagraphEnd(end, flagsEnd)) {
    throw new RuntimeException("PARAGRAPH span must end at paragraph boundary");
  }
  // 0-length Spanned.SPAN_EXCLUSIVE_EXCLUSIVE
  if (flagsStart == POINT && flagsEnd == MARK && start == end) {
    if (send) {
      Log.e(TAG, "SPAN_EXCLUSIVE_EXCLUSIVE spans cannot have a zero length");
    }
    // Silently ignore invalid spans when they are created from this class.
    // This avoids the duplication of the above test code before all the
    // calls to setSpan that are done in this class
    return;
  }

  // 到这里都和之前的 SpannableString 没有什么区别

  // gap 的判断
  int nstart = start;
  int nend = end;
  if (start > mGapStart) {
    start += mGapLength;
  } else if (start == mGapStart) {
    if (flagsStart == POINT || (flagsStart == PARAGRAPH && start == length()))
      start += mGapLength;
  }
  if (end > mGapStart) {
    end += mGapLength;
  } else if (end == mGapStart) {
    if (flagsEnd == POINT || (flagsEnd == PARAGRAPH && end == length()))
      end += mGapLength;
  }

  // 检查是否已经添加过
  if (mIndexOfSpan != null) {
    Integer index = mIndexOfSpan.get(what);
    if (index != null) {
      int i = index;
      int ostart = mSpanStarts[i];
      int oend = mSpanEnds[i];
      if (ostart > mGapStart)
        ostart -= mGapLength;
      if (oend > mGapStart)
        oend -= mGapLength;
      mSpanStarts[i] = start;
      mSpanEnds[i] = end;
      mSpanFlags[i] = flags;
      if (send) {
        restoreInvariants();
        sendSpanChanged(what, ostart, oend, nstart, nend);
      }
      return;
    }
  }
  mSpans = GrowingArrayUtils.append(mSpans, mSpanCount, what);
  mSpanStarts = GrowingArrayUtils.append(mSpanStarts, mSpanCount, start);
  mSpanEnds = GrowingArrayUtils.append(mSpanEnds, mSpanCount, end);
  mSpanFlags = GrowingArrayUtils.append(mSpanFlags, mSpanCount, flags);
  mSpanOrder = GrowingArrayUtils.append(mSpanOrder, mSpanCount, mSpanInsertCount);
  invalidateIndex(mSpanCount);
  mSpanCount++;
  mSpanInsertCount++;
  // Make sure there is enough room for empty interior nodes.
  // This magic formula computes the size of the smallest perfect binary
  // tree no smaller than mSpanCount.
  int sizeOfMax = 2 * treeRoot() + 1;
  if (mSpanMax.length < sizeOfMax) {
    mSpanMax = new int[sizeOfMax];
  }
  if (send) {
    restoreInvariants();
    sendSpanAdded(what, nstart, nend);
  }
}

开始的操作依然是检查 start end 越界和 paragraph。接下来是对 gap 缓冲做的处理：

int nstart = start;
int nend = end;
if (start > mGapStart) {
  start += mGapLength;
} else if (start == mGapStart) {
  if (flagsStart == POINT || (flagsStart == PARAGRAPH && start == length()))
    start += mGapLength;
}
if (end > mGapStart) {
  end += mGapLength;
} else if (end == mGapStart) {
  if (flagsEnd == POINT || (flagsEnd == PARAGRAPH && end == length()))
    end += mGapLength;
}

在这里会对 flags 有一个判断，当 flags 前后是 INCLUSIVE 且给的 start 和 end 是开头或结尾的时候，当这 append 的时候结尾或开始的字符串就会自动应用到这个 span。例如下面的代码：

SpannableStringBuilder ssb = new SpannableStringBuilder("abcd");
ssb.setSpan(new UnderlineSpan(), 1, 4, Spanned.SPAN_POINT_POINT);
ssb.append("aaaa");
ssb.append("aaaa");

在 setSpan 的时候是对 "bcd" 部分加了下划线，当后面两次连续 append 之后，新加入的 "aaaaaaaa" 也被自动加入了下划线。

这里对 gap 做一个解释，在 SpannableStringBuilder 创建的时候会建一个名为 mText 的 char[]，数组的 size 经过两个方法的处理就会得到一个合适大小的数组，数组在赋值后剩余出来的空间就是 gap buffer。大小合适的数组可以避免在 append 的过程中对数组频繁的 copy 操作。

public SpannableStringBuilder(CharSequence text, int start, int end) {
  int srclen = end - start;
  
  if (srclen < 0) throw new StringIndexOutOfBoundsException();
  
  mText = ArrayUtils.newUnpaddedCharArray(GrowingArrayUtils.growSize(srclen));
  mGapStart = srclen;
  mGapLength = mText.length - srclen;
  ...
}

// GrowingArrayUtils
/**
 * Given the current size of an array, returns an ideal size to which the array should grow.
 * This is typically double the given size, but should not be relied upon to do so in the
 * future.
 */
public static int growSize(int currentSize) {
  return currentSize <= 4 ? 8 : currentSize * 2;
}

// ArrayUtils
public static char[] newUnpaddedCharArray(int minLen) {
  return (char[])VMRuntime.getRuntime().newUnpaddedArray(char.class, minLen);
}

/**
 * Returns an array allocated in an area of the Java heap where it will never be moved.
 * This is used to implement native allocations on the Java heap, such as DirectByteBuffers
 * and Bitmaps.
 */
public native Object newNonMovableArray(Class<?> componentType, int length);

然后就是对 span 的检查，这一点的原理和 SpannableString 类似，也是重复使用的话只会保留最后设置的效果。下面操作就是对新加入的 span 的处理，同样使用构造函数中类似的对数组扩充的方式：

mSpans = GrowingArrayUtils.append(mSpans, mSpanCount, what);
mSpanStarts = GrowingArrayUtils.append(mSpanStarts, mSpanCount, start);
mSpanEnds = GrowingArrayUtils.append(mSpanEnds, mSpanCount, end);
mSpanFlags = GrowingArrayUtils.append(mSpanFlags, mSpanCount, flags);
mSpanOrder = GrowingArrayUtils.append(mSpanOrder, mSpanCount, mSpanInsertCount);
// 更新 mIndexOfSpan 
invalidateIndex(mSpanCount);
mSpanCount++;
mSpanInsertCount++;

// Call this on any update to mSpans[], so that mIndexOfSpan can be updated
private void invalidateIndex(int i) {
  mLowWaterMark = Math.min(i, mLowWaterMark);
}

// GrowingArrayUtils 
public static <T> T[] append(T[] array, int currentSize, T element) {
  assert currentSize <= array.length;
  if (currentSize + 1 > array.length) {
    @SuppressWarnings("unchecked")
    T[] newArray = ArrayUtils.newUnpaddedArray(
        (Class<T>) array.getClass().getComponentType(), growSize(currentSize));
    System.arraycopy(array, 0, newArray, 0, currentSize);
    array = newArray;
  }
  array[currentSize] = element;
  return array;
}

这些 span 被存在一个线性的数组中，数组的排序是按照 start 的值建立的满二叉树来实现的，做成这样也是为了查询的更快。在这里的公式 2 * treeRoot() + 1 可以算出当前树的最大节点数，例如根节点的下标是 3，那么这个满二叉树中节点个数就是 7。完整的二叉树定义以及如何使用可以看 treeRoot 和 calcMax 方法的注释：

// Make sure there is enough room for empty interior nodes.
// This magic formula computes the size of the smallest perfect binary
// tree no smaller than mSpanCount.
int sizeOfMax = 2 * treeRoot() + 1;
if (mSpanMax.length < sizeOfMax) {
  mSpanMax = new int[sizeOfMax];
}
if (send) {
  restoreInvariants();  // 对二叉树进行
  sendSpanAdded(what, nstart, nend);
}

// The spans (along with start and end offsets and flags) are stored in linear arrays sorted
// by start offset. For fast searching, there is a binary search structure imposed over these
// arrays. This structure is inorder traversal of a perfect binary tree, a slightly unusual
// but advantageous approach.

// The value-containing nodes are indexed 0 <= i < n (where n = mSpanCount), thus preserving
// logic that accesses the values as a contiguous array. Other balanced binary tree approaches
// (such as a complete binary tree) would require some shuffling of node indices.

// Basic properties of this structure: For a perfect binary tree of height m:
// The tree has 2^(m+1) - 1 total nodes.
// The root of the tree has index 2^m - 1.
// All leaf nodes have even index, all interior nodes odd.
// The height of a node of index i is the number of trailing ones in i's binary representation.
// The left child of a node i of height h is i - 2^(h - 1).
// The right child of a node i of height h is i + 2^(h - 1).

// Note that for arbitrary n, interior nodes of this tree may be >= n. Thus, the general
// structure of a recursive traversal of node i is:
// * traverse left child if i is an interior node
// * process i if i < n
// * traverse right child if i is an interior node and i < n
private int treeRoot() {
  return Integer.highestOneBit(mSpanCount) - 1;
}

// The span arrays are also augmented by an mSpanMax[] array that represents an interval tree
// over the binary tree structure described above. For each node, the mSpanMax[] array contains
// the maximum value of mSpanEnds of that node and its descendants. Thus, traversals can
// easily reject subtrees that contain no spans overlapping the area of interest.
// Note that mSpanMax[] also has a valid valuefor interior nodes of index >= n, but which have
// descendants of index < n. In these cases, it simply represents the maximum span end of its
// descendants. This is a consequence of the perfect binary tree structure.
private int calcMax(int i) {
  ...
}