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 com.android.internal.util.ArrayUtils;
20import com.android.internal.util.GrowingArrayUtils;
21
22import libcore.util.EmptyArray;
23
24import java.lang.reflect.Array;
25
26/* package */ abstract class SpannableStringInternal
27{
28    /* package */ SpannableStringInternal(CharSequence source,
29                                          int start, int end) {
30        if (start == 0 && end == source.length())
31            mText = source.toString();
32        else
33            mText = source.toString().substring(start, end);
34
35        mSpans = EmptyArray.OBJECT;
36        // Invariant: mSpanData.length = mSpans.length * COLUMNS
37        mSpanData = EmptyArray.INT;
38
39        if (source instanceof Spanned) {
40            if (source instanceof SpannableStringInternal) {
41                copySpans((SpannableStringInternal) source, start, end);
42            } else {
43                copySpans((Spanned) source, start, end);
44            }
45        }
46    }
47
48    /**
49     * Copies another {@link Spanned} object's spans between [start, end] into this object.
50     *
51     * @param src Source object to copy from.
52     * @param start Start index in the source object.
53     * @param end End index in the source object.
54     */
55    private final void copySpans(Spanned src, int start, int end) {
56        Object[] spans = src.getSpans(start, end, Object.class);
57
58        for (int i = 0; i < spans.length; i++) {
59            int st = src.getSpanStart(spans[i]);
60            int en = src.getSpanEnd(spans[i]);
61            int fl = src.getSpanFlags(spans[i]);
62
63            if (st < start)
64                st = start;
65            if (en > end)
66                en = end;
67
68            setSpan(spans[i], st - start, en - start, fl, false/*enforceParagraph*/);
69        }
70    }
71
72    /**
73     * Copies a {@link SpannableStringInternal} object's spans between [start, end] into this
74     * object.
75     *
76     * @param src Source object to copy from.
77     * @param start Start index in the source object.
78     * @param end End index in the source object.
79     */
80    private final void copySpans(SpannableStringInternal src, int start, int end) {
81        if (start == 0 && end == src.length()) {
82            mSpans = ArrayUtils.newUnpaddedObjectArray(src.mSpans.length);
83            mSpanData = new int[src.mSpanData.length];
84            mSpanCount = src.mSpanCount;
85            System.arraycopy(src.mSpans, 0, mSpans, 0, src.mSpans.length);
86            System.arraycopy(src.mSpanData, 0, mSpanData, 0, mSpanData.length);
87        } else {
88            int count = 0;
89            int[] srcData = src.mSpanData;
90            int limit = src.mSpanCount;
91            for (int i = 0; i < limit; i++) {
92                int spanStart = srcData[i * COLUMNS + START];
93                int spanEnd = srcData[i * COLUMNS + END];
94                if (isOutOfCopyRange(start, end, spanStart, spanEnd)) continue;
95                count++;
96            }
97
98            if (count == 0) return;
99
100            Object[] srcSpans = src.mSpans;
101            mSpanCount = count;
102            mSpans = ArrayUtils.newUnpaddedObjectArray(mSpanCount);
103            mSpanData = new int[mSpans.length * COLUMNS];
104            for (int i = 0, j = 0; i < limit; i++) {
105                int spanStart = srcData[i * COLUMNS + START];
106                int spanEnd = srcData[i * COLUMNS + END];
107                if (isOutOfCopyRange(start, end, spanStart, spanEnd)) continue;
108                if (spanStart < start) spanStart = start;
109                if (spanEnd > end) spanEnd = end;
110
111                mSpans[j] = srcSpans[i];
112                mSpanData[j * COLUMNS + START] = spanStart - start;
113                mSpanData[j * COLUMNS + END] = spanEnd - start;
114                mSpanData[j * COLUMNS + FLAGS] = srcData[i * COLUMNS + FLAGS];
115                j++;
116            }
117        }
118    }
119
120    /**
121     * Checks if [spanStart, spanEnd] interval is excluded from [start, end].
122     *
123     * @return True if excluded, false if included.
124     */
125    private final boolean isOutOfCopyRange(int start, int end, int spanStart, int spanEnd) {
126        if (spanStart > end || spanEnd < start) return true;
127        if (spanStart != spanEnd && start != end) {
128            if (spanStart == end || spanEnd == start) return true;
129        }
130        return false;
131    }
132
133    public final int length() {
134        return mText.length();
135    }
136
137    public final char charAt(int i) {
138        return mText.charAt(i);
139    }
140
141    public final String toString() {
142        return mText;
143    }
144
145    /* subclasses must do subSequence() to preserve type */
146
147    public final void getChars(int start, int end, char[] dest, int off) {
148        mText.getChars(start, end, dest, off);
149    }
150
151    /* package */ void setSpan(Object what, int start, int end, int flags) {
152        setSpan(what, start, end, flags, true/*enforceParagraph*/);
153    }
154
155    private boolean isIndexFollowsNextLine(int index) {
156        return index != 0 && index != length() && charAt(index - 1) != '\n';
157    }
158
159    private void setSpan(Object what, int start, int end, int flags, boolean enforceParagraph) {
160        int nstart = start;
161        int nend = end;
162
163        checkRange("setSpan", start, end);
164
165        if ((flags & Spannable.SPAN_PARAGRAPH) == Spannable.SPAN_PARAGRAPH) {
166            if (isIndexFollowsNextLine(start)) {
167                if (!enforceParagraph) {
168                    // do not set the span
169                    return;
170                }
171                throw new RuntimeException("PARAGRAPH span must start at paragraph boundary"
172                        + " (" + start + " follows " + charAt(start - 1) + ")");
173            }
174
175            if (isIndexFollowsNextLine(end)) {
176                if (!enforceParagraph) {
177                    // do not set the span
178                    return;
179                }
180                throw new RuntimeException("PARAGRAPH span must end at paragraph boundary"
181                        + " (" + end + " follows " + charAt(end - 1) + ")");
182            }
183        }
184
185        int count = mSpanCount;
186        Object[] spans = mSpans;
187        int[] data = mSpanData;
188
189        for (int i = 0; i < count; i++) {
190            if (spans[i] == what) {
191                int ostart = data[i * COLUMNS + START];
192                int oend = data[i * COLUMNS + END];
193
194                data[i * COLUMNS + START] = start;
195                data[i * COLUMNS + END] = end;
196                data[i * COLUMNS + FLAGS] = flags;
197
198                sendSpanChanged(what, ostart, oend, nstart, nend);
199                return;
200            }
201        }
202
203        if (mSpanCount + 1 >= mSpans.length) {
204            Object[] newtags = ArrayUtils.newUnpaddedObjectArray(
205                    GrowingArrayUtils.growSize(mSpanCount));
206            int[] newdata = new int[newtags.length * 3];
207
208            System.arraycopy(mSpans, 0, newtags, 0, mSpanCount);
209            System.arraycopy(mSpanData, 0, newdata, 0, mSpanCount * 3);
210
211            mSpans = newtags;
212            mSpanData = newdata;
213        }
214
215        mSpans[mSpanCount] = what;
216        mSpanData[mSpanCount * COLUMNS + START] = start;
217        mSpanData[mSpanCount * COLUMNS + END] = end;
218        mSpanData[mSpanCount * COLUMNS + FLAGS] = flags;
219        mSpanCount++;
220
221        if (this instanceof Spannable)
222            sendSpanAdded(what, nstart, nend);
223    }
224
225    /* package */ void removeSpan(Object what) {
226        int count = mSpanCount;
227        Object[] spans = mSpans;
228        int[] data = mSpanData;
229
230        for (int i = count - 1; i >= 0; i--) {
231            if (spans[i] == what) {
232                int ostart = data[i * COLUMNS + START];
233                int oend = data[i * COLUMNS + END];
234
235                int c = count - (i + 1);
236
237                System.arraycopy(spans, i + 1, spans, i, c);
238                System.arraycopy(data, (i + 1) * COLUMNS,
239                                 data, i * COLUMNS, c * COLUMNS);
240
241                mSpanCount--;
242
243                sendSpanRemoved(what, ostart, oend);
244                return;
245            }
246        }
247    }
248
249    public int getSpanStart(Object what) {
250        int count = mSpanCount;
251        Object[] spans = mSpans;
252        int[] data = mSpanData;
253
254        for (int i = count - 1; i >= 0; i--) {
255            if (spans[i] == what) {
256                return data[i * COLUMNS + START];
257            }
258        }
259
260        return -1;
261    }
262
263    public int getSpanEnd(Object what) {
264        int count = mSpanCount;
265        Object[] spans = mSpans;
266        int[] data = mSpanData;
267
268        for (int i = count - 1; i >= 0; i--) {
269            if (spans[i] == what) {
270                return data[i * COLUMNS + END];
271            }
272        }
273
274        return -1;
275    }
276
277    public int getSpanFlags(Object what) {
278        int count = mSpanCount;
279        Object[] spans = mSpans;
280        int[] data = mSpanData;
281
282        for (int i = count - 1; i >= 0; i--) {
283            if (spans[i] == what) {
284                return data[i * COLUMNS + FLAGS];
285            }
286        }
287
288        return 0;
289    }
290
291    public <T> T[] getSpans(int queryStart, int queryEnd, Class<T> kind) {
292        int count = 0;
293
294        int spanCount = mSpanCount;
295        Object[] spans = mSpans;
296        int[] data = mSpanData;
297        Object[] ret = null;
298        Object ret1 = null;
299
300        for (int i = 0; i < spanCount; i++) {
301            int spanStart = data[i * COLUMNS + START];
302            int spanEnd = data[i * COLUMNS + END];
303
304            if (spanStart > queryEnd) {
305                continue;
306            }
307            if (spanEnd < queryStart) {
308                continue;
309            }
310
311            if (spanStart != spanEnd && queryStart != queryEnd) {
312                if (spanStart == queryEnd) {
313                    continue;
314                }
315                if (spanEnd == queryStart) {
316                    continue;
317                }
318            }
319
320            // verify span class as late as possible, since it is expensive
321            if (kind != null && kind != Object.class && !kind.isInstance(spans[i])) {
322                continue;
323            }
324
325            if (count == 0) {
326                ret1 = spans[i];
327                count++;
328            } else {
329                if (count == 1) {
330                    ret = (Object[]) Array.newInstance(kind, spanCount - i + 1);
331                    ret[0] = ret1;
332                }
333
334                int prio = data[i * COLUMNS + FLAGS] & Spanned.SPAN_PRIORITY;
335                if (prio != 0) {
336                    int j;
337
338                    for (j = 0; j < count; j++) {
339                        int p = getSpanFlags(ret[j]) & Spanned.SPAN_PRIORITY;
340
341                        if (prio > p) {
342                            break;
343                        }
344                    }
345
346                    System.arraycopy(ret, j, ret, j + 1, count - j);
347                    ret[j] = spans[i];
348                    count++;
349                } else {
350                    ret[count++] = spans[i];
351                }
352            }
353        }
354
355        if (count == 0) {
356            return (T[]) ArrayUtils.emptyArray(kind);
357        }
358        if (count == 1) {
359            ret = (Object[]) Array.newInstance(kind, 1);
360            ret[0] = ret1;
361            return (T[]) ret;
362        }
363        if (count == ret.length) {
364            return (T[]) ret;
365        }
366
367        Object[] nret = (Object[]) Array.newInstance(kind, count);
368        System.arraycopy(ret, 0, nret, 0, count);
369        return (T[]) nret;
370    }
371
372    public int nextSpanTransition(int start, int limit, Class kind) {
373        int count = mSpanCount;
374        Object[] spans = mSpans;
375        int[] data = mSpanData;
376
377        if (kind == null) {
378            kind = Object.class;
379        }
380
381        for (int i = 0; i < count; i++) {
382            int st = data[i * COLUMNS + START];
383            int en = data[i * COLUMNS + END];
384
385            if (st > start && st < limit && kind.isInstance(spans[i]))
386                limit = st;
387            if (en > start && en < limit && kind.isInstance(spans[i]))
388                limit = en;
389        }
390
391        return limit;
392    }
393
394    private void sendSpanAdded(Object what, int start, int end) {
395        SpanWatcher[] recip = getSpans(start, end, SpanWatcher.class);
396        int n = recip.length;
397
398        for (int i = 0; i < n; i++) {
399            recip[i].onSpanAdded((Spannable) this, what, start, end);
400        }
401    }
402
403    private void sendSpanRemoved(Object what, int start, int end) {
404        SpanWatcher[] recip = getSpans(start, end, SpanWatcher.class);
405        int n = recip.length;
406
407        for (int i = 0; i < n; i++) {
408            recip[i].onSpanRemoved((Spannable) this, what, start, end);
409        }
410    }
411
412    private void sendSpanChanged(Object what, int s, int e, int st, int en) {
413        SpanWatcher[] recip = getSpans(Math.min(s, st), Math.max(e, en),
414                                       SpanWatcher.class);
415        int n = recip.length;
416
417        for (int i = 0; i < n; i++) {
418            recip[i].onSpanChanged((Spannable) this, what, s, e, st, en);
419        }
420    }
421
422    private static String region(int start, int end) {
423        return "(" + start + " ... " + end + ")";
424    }
425
426    private void checkRange(final String operation, int start, int end) {
427        if (end < start) {
428            throw new IndexOutOfBoundsException(operation + " " +
429                                                region(start, end) +
430                                                " has end before start");
431        }
432
433        int len = length();
434
435        if (start > len || end > len) {
436            throw new IndexOutOfBoundsException(operation + " " +
437                                                region(start, end) +
438                                                " ends beyond length " + len);
439        }
440
441        if (start < 0 || end < 0) {
442            throw new IndexOutOfBoundsException(operation + " " +
443                                                region(start, end) +
444                                                " starts before 0");
445        }
446    }
447
448    // Same as SpannableStringBuilder
449    @Override
450    public boolean equals(Object o) {
451        if (o instanceof Spanned &&
452                toString().equals(o.toString())) {
453            Spanned other = (Spanned) o;
454            // Check span data
455            Object[] otherSpans = other.getSpans(0, other.length(), Object.class);
456            if (mSpanCount == otherSpans.length) {
457                for (int i = 0; i < mSpanCount; ++i) {
458                    Object thisSpan = mSpans[i];
459                    Object otherSpan = otherSpans[i];
460                    if (thisSpan == this) {
461                        if (other != otherSpan ||
462                                getSpanStart(thisSpan) != other.getSpanStart(otherSpan) ||
463                                getSpanEnd(thisSpan) != other.getSpanEnd(otherSpan) ||
464                                getSpanFlags(thisSpan) != other.getSpanFlags(otherSpan)) {
465                            return false;
466                        }
467                    } else if (!thisSpan.equals(otherSpan) ||
468                            getSpanStart(thisSpan) != other.getSpanStart(otherSpan) ||
469                            getSpanEnd(thisSpan) != other.getSpanEnd(otherSpan) ||
470                            getSpanFlags(thisSpan) != other.getSpanFlags(otherSpan)) {
471                        return false;
472                    }
473                }
474                return true;
475            }
476        }
477        return false;
478    }
479
480    // Same as SpannableStringBuilder
481    @Override
482    public int hashCode() {
483        int hash = toString().hashCode();
484        hash = hash * 31 + mSpanCount;
485        for (int i = 0; i < mSpanCount; ++i) {
486            Object span = mSpans[i];
487            if (span != this) {
488                hash = hash * 31 + span.hashCode();
489            }
490            hash = hash * 31 + getSpanStart(span);
491            hash = hash * 31 + getSpanEnd(span);
492            hash = hash * 31 + getSpanFlags(span);
493        }
494        return hash;
495    }
496
497    private String mText;
498    private Object[] mSpans;
499    private int[] mSpanData;
500    private int mSpanCount;
501
502    /* package */ static final Object[] EMPTY = new Object[0];
503
504    private static final int START = 0;
505    private static final int END = 1;
506    private static final int FLAGS = 2;
507    private static final int COLUMNS = 3;
508}
509