Source code

001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      https://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.lang3;
018
019/**
020 * Operations on {@link CharSequence} that are
021 * {@code null} safe.
022 *
023 * @see CharSequence
024 * @since 3.0
025 */
026public class CharSequenceUtils {
027
028    private static final int NOT_FOUND = -1;
029
030    /**
031     * Whether the running JDK folds a supplementary code point split across a surrogate pair when comparing case insensitively in
032     * {@link String#regionMatches(boolean, int, String, int, int)}. JDKs up to and including Java 11 compare surrogate by surrogate and never match such a
033     * pair; later JDKs fold the whole code point. Probing what {@link String} actually does (rather than gating on a version constant) keeps every
034     * {@link CharSequence} type in step with {@link String} on whatever JDK is running. DESERET CAPITAL LETTER LONG I (U+10400) folds to its small form
035     * (U+10428).
036     */
037    private static final boolean STRING_FOLDS_SUPPLEMENTARY_CASE = new String(Character.toChars(0x10400)).regionMatches(true, 0,
038            new String(Character.toChars(0x10428)), 0, 2);
039
040    static final int TO_STRING_LIMIT = 16;
041
042    private static boolean checkLaterThan1(final CharSequence cs, final CharSequence searchChar, final int len2, final int start1) {
043        for (int i = 1, j = len2 - 1; i <= j; i++, j--) {
044            if (cs.charAt(start1 + i) != searchChar.charAt(i) || cs.charAt(start1 + j) != searchChar.charAt(j)) {
045                return false;
046            }
047        }
048        return true;
049    }
050
051    /**
052     * Tests whether two code points are equal ignoring case, matching the folding used by {@link String#regionMatches(boolean, int, String, int, int)}.
053     *
054     * @param cp1 The first code point.
055     * @param cp2 The second code point.
056     * @return whether the code points are equal ignoring case.
057     */
058    private static boolean equalsIgnoreCase(final int cp1, final int cp2) {
059        final int u1 = Character.toUpperCase(cp1);
060        final int u2 = Character.toUpperCase(cp2);
061        return u1 == u2 || Character.toLowerCase(u1) == Character.toLowerCase(u2);
062    }
063
064    /**
065     * Used by the indexOf(CharSequence methods) as a green implementation of indexOf.
066     * <p>
067     * {@link CharSequence} types without a dedicated branch are scanned in place rather than materialized with {@code toString()}: for builder
068     * types (for example {@code org.apache.commons.lang3.text.StrBuilder}), {@code toString()} copies the whole buffer, and callers that invoke
069     * this method once per occurrence (such as {@code deleteAll}/{@code replaceAll}) would multiply that copy into allocation-quadratic churn.
070     * </p>
071     *
072     * @param cs         The {@link CharSequence} to be processed.
073     * @param searchChar The {@link CharSequence} to be searched for.
074     * @param start      The start index.
075     * @return The index where the search sequence was found, or {@code -1} if there is no such occurrence.
076     */
077    static int indexOf(final CharSequence cs, final CharSequence searchChar, final int start) {
078        if (cs == null || searchChar == null) {
079            return StringUtils.INDEX_NOT_FOUND;
080        }
081        if (cs instanceof String) {
082            return ((String) cs).indexOf(searchChar.toString(), start);
083        }
084        if (cs instanceof StringBuilder) {
085            return ((StringBuilder) cs).indexOf(searchChar.toString(), start);
086        }
087        if (cs instanceof StringBuffer) {
088            return ((StringBuffer) cs).indexOf(searchChar.toString(), start);
089        }
090        // Direct scan without copying cs; matches the semantics of String.indexOf(String, int).
091        final int len1 = cs.length();
092        final int len2 = searchChar.length();
093        final int from = Math.max(start, 0);
094        if (len2 == 0) {
095            return Math.min(from, len1);
096        }
097        if (len2 > len1 - from) {
098            return StringUtils.INDEX_NOT_FOUND;
099        }
100        final char char0 = searchChar.charAt(0);
101        final int max = len1 - len2;
102        for (int i = from; i <= max; i++) {
103            if (cs.charAt(i) == char0 && checkLaterThan1(cs, searchChar, len2, i)) {
104                return i;
105            }
106        }
107        return StringUtils.INDEX_NOT_FOUND;
108    }
109
110    /**
111     * Returns the index within {@code cs} of the first occurrence of the specified character, starting the search at the specified index.
112     * <p>
113     * If a character with value {@code searchChar} occurs in the character sequence represented by the {@code cs} object at an index no smaller than
114     * {@code start}, then the index of the first such occurrence is returned. For values of {@code searchChar} in the range from 0 to 0xFFFF (inclusive), this
115     * is the smallest value <em>k</em> such that:
116     * </p>
117     *
118     * <pre>
119     * (this.charAt(<em>k</em>) == searchChar) &amp;&amp; (<em>k</em> &gt;= start)
120     * </pre>
121     * <p>
122     * is true. For other values of {@code searchChar}, it is the smallest value <em>k</em> such that:
123     * </p>
124     *
125     * <pre>
126     * (this.codePointAt(<em>k</em>) == searchChar) &amp;&amp; (<em>k</em> &gt;= start)
127     * </pre>
128     * <p>
129     * is true. In either case, if no such character occurs inm {@code cs} at or after position {@code start}, then {@code -1} is returned.
130     * </p>
131     * <p>
132     * There is no restriction on the value of {@code start}. If it is negative, it has the same effect as if it were zero: the entire {@link CharSequence} may
133     * be searched. If it is greater than the length of {@code cs}, it has the same effect as if it were equal to the length of {@code cs}: {@code -1} is
134     * returned.
135     * </p>
136     * <p>
137     * All indices are specified in {@code char} values (Unicode code units).
138     * </p>
139     *
140     * @param cs         The {@link CharSequence} to be processed, not null.
141     * @param searchChar The char to be searched for.
142     * @param start      The start index, negative starts at the string start.
143     * @return The index where the search char was found, -1 if not found.
144     * @since 3.6 updated to behave more like {@link String}.
145     */
146    static int indexOf(final CharSequence cs, final int searchChar, int start) {
147        if (cs instanceof String) {
148            return ((String) cs).indexOf(searchChar, start);
149        }
150        final int sz = cs.length();
151        if (start < 0) {
152            start = 0;
153        }
154        if (searchChar < Character.MIN_SUPPLEMENTARY_CODE_POINT) {
155            for (int i = start; i < sz; i++) {
156                if (cs.charAt(i) == searchChar) {
157                    return i;
158                }
159            }
160            return NOT_FOUND;
161        }
162        //supplementary characters (LANG1300)
163        if (searchChar <= Character.MAX_CODE_POINT) {
164            final char[] chars = Character.toChars(searchChar);
165            for (int i = start; i < sz - 1; i++) {
166                final char high = cs.charAt(i);
167                final char low = cs.charAt(i + 1);
168                if (high == chars[0] && low == chars[1]) {
169                    return i;
170                }
171            }
172        }
173        return NOT_FOUND;
174    }
175
176    /**
177     * Used by the lastIndexOf(CharSequence methods) as a green implementation of lastIndexOf
178     *
179     * @param cs The {@link CharSequence} to be processed.
180     * @param searchChar The {@link CharSequence} to find.
181     * @param start The start index.
182     * @return The index where the search sequence was found.
183     */
184    static int lastIndexOf(final CharSequence cs, final CharSequence searchChar, int start) {
185        if (searchChar == null || cs == null) {
186            return NOT_FOUND;
187        }
188        if (searchChar instanceof String) {
189            if (cs instanceof String) {
190                return ((String) cs).lastIndexOf((String) searchChar, start);
191            }
192            if (cs instanceof StringBuilder) {
193                return ((StringBuilder) cs).lastIndexOf((String) searchChar, start);
194            }
195            if (cs instanceof StringBuffer) {
196                return ((StringBuffer) cs).lastIndexOf((String) searchChar, start);
197            }
198        }
199
200        final int len1 = cs.length();
201        final int len2 = searchChar.length();
202
203        if (start > len1) {
204            start = len1;
205        }
206
207        if (start < 0 || len2 > len1) {
208            return NOT_FOUND;
209        }
210
211        if (len2 == 0) {
212            return start;
213        }
214
215        if (len2 <= TO_STRING_LIMIT) {
216            if (cs instanceof String) {
217                return ((String) cs).lastIndexOf(searchChar.toString(), start);
218            }
219            if (cs instanceof StringBuilder) {
220                return ((StringBuilder) cs).lastIndexOf(searchChar.toString(), start);
221            }
222            if (cs instanceof StringBuffer) {
223                return ((StringBuffer) cs).lastIndexOf(searchChar.toString(), start);
224            }
225        }
226
227        if (start + len2 > len1) {
228            start = len1 - len2;
229        }
230
231        final char char0 = searchChar.charAt(0);
232
233        int i = start;
234        while (true) {
235            while (cs.charAt(i) != char0) {
236                i--;
237                if (i < 0) {
238                    return NOT_FOUND;
239                }
240            }
241            if (checkLaterThan1(cs, searchChar, len2, i)) {
242                return i;
243            }
244            i--;
245            if (i < 0) {
246                return NOT_FOUND;
247            }
248        }
249    }
250
251    /**
252     * Returns the index within {@code cs} of the last occurrence of the specified character, searching backward starting at the specified index. For values of
253     * {@code searchChar} in the range from 0 to 0xFFFF (inclusive), the index returned is the largest value <em>k</em> such that:
254     *
255     * <pre>
256     * (this.charAt(<em>k</em>) == searchChar) &amp;&amp; (<em>k</em> &lt;= start)
257     * </pre>
258     * <p>
259     * is true. For other values of {@code searchChar}, it is the largest value <em>k</em> such that:
260     * <p>
261     *
262     * <pre>
263     * (this.codePointAt(<em>k</em>) == searchChar) &amp;&amp; (<em>k</em> &lt;= start)
264     * </pre>
265     * <p>
266     * is true. In either case, if no such character occurs in {@code cs} at or before position {@code start}, then {@code -1} is returned.
267     * </p>
268     * <p>
269     * All indices are specified in {@code char} values (Unicode code units).
270     * </p>
271     *
272     * @param cs         The {@link CharSequence} to be processed.
273     * @param searchChar The char to be searched for.
274     * @param start      The start index, negative returns -1, beyond length starts at end.
275     * @return The index where the search char was found, -1 if not found.
276     * @since 3.6 updated to behave more like {@link String}.
277     */
278    static int lastIndexOf(final CharSequence cs, final int searchChar, int start) {
279        if (cs instanceof String) {
280            return ((String) cs).lastIndexOf(searchChar, start);
281        }
282        final int sz = cs.length();
283        if (start < 0) {
284            return NOT_FOUND;
285        }
286        if (start >= sz) {
287            start = sz - 1;
288        }
289        if (searchChar < Character.MIN_SUPPLEMENTARY_CODE_POINT) {
290            for (int i = start; i >= 0; --i) {
291                if (cs.charAt(i) == searchChar) {
292                    return i;
293                }
294            }
295            return NOT_FOUND;
296        }
297        //supplementary characters (LANG1300)
298        //NOTE - we must do a forward traversal for this to avoid duplicating code points
299        if (searchChar <= Character.MAX_CODE_POINT) {
300            final char[] chars = Character.toChars(searchChar);
301            // A supplementary code point spans two chars, so its high surrogate can start no later
302            // than sz - 2; clamp the search origin instead of bailing out when start is the last index.
303            for (int i = Math.min(start, sz - 2); i >= 0; i--) {
304                final char high = cs.charAt(i);
305                final char low = cs.charAt(i + 1);
306                if (chars[0] == high && chars[1] == low) {
307                    return i;
308                }
309            }
310        }
311        return NOT_FOUND;
312    }
313
314    /**
315     * Tests if two string regions are equal.
316     *
317     * @param cs         The {@link CharSequence} to be processed.
318     * @param ignoreCase whether or not to be case-insensitive.
319     * @param thisStart  The index to start on the {@code cs} CharSequence.
320     * @param substring  The {@link CharSequence} to be looked for.
321     * @param start      The index to start on the {@code substring} CharSequence.
322     * @param length     character length of the region.
323     * @return whether the region matched.
324     * @see String#regionMatches(boolean, int, String, int, int)
325     */
326    static boolean regionMatches(final CharSequence cs, final boolean ignoreCase, final int thisStart, final CharSequence substring, final int start,
327            final int length) {
328        // Green implementation of regionMatches.
329        if (cs instanceof String && substring instanceof String) {
330            return ((String) cs).regionMatches(ignoreCase, thisStart, (String) substring, start, length);
331        }
332        // Extract these first so we detect NPEs the same as the java.lang.String version
333        final int srcLen = cs.length() - thisStart;
334        final int otherLen = substring.length() - start;
335        // Check for invalid parameters
336        if (thisStart < 0 || start < 0 || length < 0) {
337            return false;
338        }
339        // Check that the regions are long enough
340        if (srcLen < length || otherLen < length) {
341            return false;
342        }
343        final int end1 = thisStart + length;
344        final int end2 = start + length;
345        int index1 = thisStart;
346        int index2 = start;
347        while (index1 < end1 && index2 < end2) {
348            final char c1 = cs.charAt(index1);
349            final char c2 = substring.charAt(index2);
350            if (c1 == c2) {
351                index1++;
352                index2++;
353                continue;
354            }
355            if (!ignoreCase) {
356                return false;
357            }
358            // The same case-insensitive check as String#regionMatches(boolean, int, String, int, int).
359            if (!equalsIgnoreCase(c1, c2)) {
360                // Only fold a supplementary code point split across a surrogate pair where String itself does, so
361                // every CharSequence type gives the same result that String does on the running JDK (see field).
362                if (!STRING_FOLDS_SUPPLEMENTARY_CASE) {
363                    return false;
364                }
365                int cp1 = c1;
366                if (Character.isHighSurrogate(c1)) {
367                    if (index1 + 1 < end1 && Character.isLowSurrogate(cs.charAt(index1 + 1))) {
368                        cp1 = Character.toCodePoint(c1, cs.charAt(index1 + 1));
369                        index1++;
370                    }
371                } else if (Character.isLowSurrogate(c1) && index1 > thisStart && Character.isHighSurrogate(cs.charAt(index1 - 1))) {
372                    cp1 = Character.toCodePoint(cs.charAt(index1 - 1), c1);
373                }
374                int cp2 = c2;
375                if (Character.isHighSurrogate(c2)) {
376                    if (index2 + 1 < end2 && Character.isLowSurrogate(substring.charAt(index2 + 1))) {
377                        cp2 = Character.toCodePoint(c2, substring.charAt(index2 + 1));
378                        index2++;
379                    }
380                } else if (Character.isLowSurrogate(c2) && index2 > start && Character.isHighSurrogate(substring.charAt(index2 - 1))) {
381                    cp2 = Character.toCodePoint(substring.charAt(index2 - 1), c2);
382                }
383                if (!equalsIgnoreCase(cp1, cp2)) {
384                    return false;
385                }
386            }
387            index1++;
388            index2++;
389        }
390        return true;
391    }
392
393    /**
394     * Returns a new {@link CharSequence} that is a subsequence of this
395     * sequence starting with the {@code char} value at the specified index.
396     *
397     * <p>
398     * This provides the {@link CharSequence} equivalent to {@link String#substring(int)}.
399     * The length (in {@code char}) of the returned sequence is {@code length() - start},
400     * so if {@code start == end} then an empty sequence is returned.
401     * </p>
402     *
403     * @param cs  The specified subsequence, null returns null.
404     * @param start  The start index, inclusive, valid.
405     * @return A new subsequence, may be null.
406     * @throws IndexOutOfBoundsException Thrown if {@code start} is negative or if
407     *  {@code start} is greater than {@code length()}.
408     */
409    public static CharSequence subSequence(final CharSequence cs, final int start) {
410        return cs == null ? null : cs.subSequence(start, cs.length());
411    }
412
413    /**
414     * Converts the given CharSequence to a char[].
415     *
416     * @param source The {@link CharSequence} to be processed.
417     * @return The resulting char array, never null.
418     * @since 3.11
419     */
420    public static char[] toCharArray(final CharSequence source) {
421        // See CharSequenceUtilsBenchmark
422        final int len = StringUtils.length(source);
423        if (len == 0) {
424            return ArrayUtils.EMPTY_CHAR_ARRAY;
425        }
426        if (source instanceof String) {
427            return ((String) source).toCharArray();
428        }
429        if (source instanceof StringBuilder) {
430            final char[] array = new char[len];
431            ((StringBuilder) source).getChars(0, len, array, 0);
432            return array;
433        }
434        if (source instanceof StringBuffer) {
435            final char[] array = new char[len];
436            ((StringBuffer) source).getChars(0, len, array, 0);
437            return array;
438        }
439        final char[] array = new char[len];
440        for (int i = 0; i < len; i++) {
441            array[i] = source.charAt(i);
442        }
443        return array;
444    }
445
446    /**
447     * {@link CharSequenceUtils} instances should NOT be constructed in
448     * standard programming.
449     *
450     * <p>
451     * This constructor is public to permit tools that require a JavaBean
452     * instance to operate.
453     * </p>
454     *
455     * @deprecated TODO Make private in 4.0.
456     */
457    @Deprecated
458    public CharSequenceUtils() {
459        // empty
460    }
461}