1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * https://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.lang3;
18
19 /**
20 * Operations on {@link CharSequence} that are
21 * {@code null} safe.
22 *
23 * @see CharSequence
24 * @since 3.0
25 */
26 public class CharSequenceUtils {
27
28 private static final int NOT_FOUND = -1;
29
30 /**
31 * Whether the running JDK folds a supplementary code point split across a surrogate pair when comparing case insensitively in
32 * {@link String#regionMatches(boolean, int, String, int, int)}. JDKs up to and including Java 11 compare surrogate by surrogate and never match such a
33 * pair; later JDKs fold the whole code point. Probing what {@link String} actually does (rather than gating on a version constant) keeps every
34 * {@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
35 * (U+10428).
36 */
37 private static final boolean STRING_FOLDS_SUPPLEMENTARY_CASE = new String(Character.toChars(0x10400)).regionMatches(true, 0,
38 new String(Character.toChars(0x10428)), 0, 2);
39
40 static final int TO_STRING_LIMIT = 16;
41
42 private static boolean checkLaterThan1(final CharSequence cs, final CharSequence searchChar, final int len2, final int start1) {
43 for (int i = 1, j = len2 - 1; i <= j; i++, j--) {
44 if (cs.charAt(start1 + i) != searchChar.charAt(i) || cs.charAt(start1 + j) != searchChar.charAt(j)) {
45 return false;
46 }
47 }
48 return true;
49 }
50
51 /**
52 * Tests whether two code points are equal ignoring case, matching the folding used by {@link String#regionMatches(boolean, int, String, int, int)}.
53 *
54 * @param cp1 The first code point.
55 * @param cp2 The second code point.
56 * @return whether the code points are equal ignoring case.
57 */
58 private static boolean equalsIgnoreCase(final int cp1, final int cp2) {
59 final int u1 = Character.toUpperCase(cp1);
60 final int u2 = Character.toUpperCase(cp2);
61 return u1 == u2 || Character.toLowerCase(u1) == Character.toLowerCase(u2);
62 }
63
64 /**
65 * Used by the indexOf(CharSequence methods) as a green implementation of indexOf.
66 * <p>
67 * {@link CharSequence} types without a dedicated branch are scanned in place rather than materialized with {@code toString()}: for builder
68 * types (for example {@code org.apache.commons.lang3.text.StrBuilder}), {@code toString()} copies the whole buffer, and callers that invoke
69 * this method once per occurrence (such as {@code deleteAll}/{@code replaceAll}) would multiply that copy into allocation-quadratic churn.
70 * </p>
71 *
72 * @param cs The {@link CharSequence} to be processed.
73 * @param searchChar The {@link CharSequence} to be searched for.
74 * @param start The start index.
75 * @return The index where the search sequence was found, or {@code -1} if there is no such occurrence.
76 */
77 static int indexOf(final CharSequence cs, final CharSequence searchChar, final int start) {
78 if (cs == null || searchChar == null) {
79 return StringUtils.INDEX_NOT_FOUND;
80 }
81 if (cs instanceof String) {
82 return ((String) cs).indexOf(searchChar.toString(), start);
83 }
84 if (cs instanceof StringBuilder) {
85 return ((StringBuilder) cs).indexOf(searchChar.toString(), start);
86 }
87 if (cs instanceof StringBuffer) {
88 return ((StringBuffer) cs).indexOf(searchChar.toString(), start);
89 }
90 // Direct scan without copying cs; matches the semantics of String.indexOf(String, int).
91 final int len1 = cs.length();
92 final int len2 = searchChar.length();
93 final int from = Math.max(start, 0);
94 if (len2 == 0) {
95 return Math.min(from, len1);
96 }
97 if (len2 > len1 - from) {
98 return StringUtils.INDEX_NOT_FOUND;
99 }
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) && (<em>k</em> >= 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) && (<em>k</em> >= 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) && (<em>k</em> <= 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) && (<em>k</em> <= 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 }